1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py 2; RUN: opt -S -indvars < %s | FileCheck %s 3target datalayout = "n8:16:32:64" 4@G = external global i32 5 6; Basic case where we know the value of an induction variable along one 7; exit edge, but not another. 8define i32 @test(i32 %n) { 9; CHECK-LABEL: @test( 10; CHECK-NEXT: entry: 11; CHECK-NEXT: [[TMP0:%.*]] = add i32 [[N:%.*]], 1 12; CHECK-NEXT: br label [[HEADER:%.*]] 13; CHECK: header: 14; CHECK-NEXT: [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LATCH:%.*]] ] 15; CHECK-NEXT: [[V:%.*]] = load volatile i32, i32* @G 16; CHECK-NEXT: [[CMP1:%.*]] = icmp eq i32 [[V]], 0 17; CHECK-NEXT: br i1 [[CMP1]], label [[LATCH]], label [[EXIT1:%.*]] 18; CHECK: latch: 19; CHECK-NEXT: [[IV_NEXT]] = add i32 [[IV]], 1 20; CHECK-NEXT: [[EXITCOND:%.*]] = icmp ne i32 [[IV_NEXT]], [[TMP0]] 21; CHECK-NEXT: br i1 [[EXITCOND]], label [[HEADER]], label [[EXIT2:%.*]] 22; CHECK: exit1: 23; CHECK-NEXT: [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[HEADER]] ] 24; CHECK-NEXT: ret i32 [[IV_LCSSA]] 25; CHECK: exit2: 26; CHECK-NEXT: ret i32 [[N]] 27; 28entry: 29 br label %header 30header: 31 %iv = phi i32 [0, %entry], [%iv.next, %latch] 32 %v = load volatile i32, i32* @G 33 %cmp1 = icmp eq i32 %v, 0 34 br i1 %cmp1, label %latch, label %exit1 35 36latch: 37 %iv.next = add i32 %iv, 1 38 %cmp2 = icmp ult i32 %iv, %n 39 br i1 %cmp2, label %header, label %exit2 40exit1: 41 ret i32 %iv 42exit2: 43 ret i32 %iv 44} 45 46define i32 @test2(i32 %n) { 47; CHECK-LABEL: @test2( 48; CHECK-NEXT: entry: 49; CHECK-NEXT: [[TMP0:%.*]] = add i32 [[N:%.*]], 1 50; CHECK-NEXT: br label [[HEADER:%.*]] 51; CHECK: header: 52; CHECK-NEXT: [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LATCH:%.*]] ] 53; CHECK-NEXT: [[V:%.*]] = load volatile i32, i32* @G 54; CHECK-NEXT: [[CMP1:%.*]] = icmp eq i32 [[V]], 0 55; CHECK-NEXT: br i1 [[CMP1]], label [[LATCH]], label [[EXIT1:%.*]] 56; CHECK: latch: 57; CHECK-NEXT: [[IV_NEXT]] = add i32 [[IV]], 1 58; CHECK-NEXT: [[EXITCOND:%.*]] = icmp ne i32 [[IV_NEXT]], [[TMP0]] 59; CHECK-NEXT: br i1 [[EXITCOND]], label [[HEADER]], label [[EXIT2:%.*]] 60; CHECK: exit1: 61; CHECK-NEXT: [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[HEADER]] ] 62; CHECK-NEXT: ret i32 [[IV_LCSSA]] 63; CHECK: exit2: 64; CHECK-NEXT: ret i32 [[TMP0]] 65; 66entry: 67 br label %header 68header: 69 %iv = phi i32 [0, %entry], [%iv.next, %latch] 70 %v = load volatile i32, i32* @G 71 %cmp1 = icmp eq i32 %v, 0 72 br i1 %cmp1, label %latch, label %exit1 73 74latch: 75 %iv.next = add i32 %iv, 1 76 %cmp2 = icmp ult i32 %iv, %n 77 br i1 %cmp2, label %header, label %exit2 78exit1: 79 ret i32 %iv 80exit2: 81 ret i32 %iv.next 82} 83 84define i32 @neg_wrong_loop(i32 %n) { 85; CHECK-LABEL: @neg_wrong_loop( 86; CHECK-NEXT: entry: 87; CHECK-NEXT: br label [[WRONG_LOOP:%.*]] 88; CHECK: wrong_loop: 89; CHECK-NEXT: [[IV2:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV2_NEXT:%.*]], [[WRONG_LOOP]] ] 90; CHECK-NEXT: [[IV2_NEXT]] = add i32 [[IV2]], 1 91; CHECK-NEXT: [[UNKNOWN:%.*]] = load volatile i32, i32* @G 92; CHECK-NEXT: [[CMP_UNK:%.*]] = icmp eq i32 [[UNKNOWN]], 0 93; CHECK-NEXT: br i1 [[CMP_UNK]], label [[HEADER_PREHEADER:%.*]], label [[WRONG_LOOP]] 94; CHECK: header.preheader: 95; CHECK-NEXT: [[IV2_LCSSA:%.*]] = phi i32 [ [[IV2]], [[WRONG_LOOP]] ] 96; CHECK-NEXT: [[TMP0:%.*]] = add i32 [[N:%.*]], 1 97; CHECK-NEXT: br label [[HEADER:%.*]] 98; CHECK: header: 99; CHECK-NEXT: [[IV:%.*]] = phi i32 [ 0, [[HEADER_PREHEADER]] ], [ [[IV_NEXT:%.*]], [[LATCH:%.*]] ] 100; CHECK-NEXT: [[V:%.*]] = load volatile i32, i32* @G 101; CHECK-NEXT: [[CMP1:%.*]] = icmp eq i32 [[V]], 0 102; CHECK-NEXT: br i1 [[CMP1]], label [[LATCH]], label [[EXIT1:%.*]] 103; CHECK: latch: 104; CHECK-NEXT: [[IV_NEXT]] = add i32 [[IV]], 1 105; CHECK-NEXT: [[EXITCOND:%.*]] = icmp ne i32 [[IV_NEXT]], [[TMP0]] 106; CHECK-NEXT: br i1 [[EXITCOND]], label [[HEADER]], label [[EXIT2:%.*]] 107; CHECK: exit1: 108; CHECK-NEXT: [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[HEADER]] ] 109; CHECK-NEXT: ret i32 [[IV_LCSSA]] 110; CHECK: exit2: 111; CHECK-NEXT: [[EXITVAL:%.*]] = phi i32 [ [[IV2_LCSSA]], [[LATCH]] ] 112; CHECK-NEXT: ret i32 [[EXITVAL]] 113; 114entry: 115 br label %wrong_loop 116 117wrong_loop: 118 %iv2 = phi i32 [0, %entry], [%iv2.next, %wrong_loop] 119 %iv2.next = add i32 %iv2, 1 120 %unknown = load volatile i32, i32* @G 121 %cmp_unk = icmp eq i32 %unknown, 0 122 br i1 %cmp_unk, label %header.preheader, label %wrong_loop 123 124header.preheader: 125 %iv2.lcssa = phi i32 [%iv2, %wrong_loop] 126 br label %header 127 128header: 129 %iv = phi i32 [0, %header.preheader], [%iv.next, %latch] 130 %v = load volatile i32, i32* @G 131 %cmp1 = icmp eq i32 %v, 0 132 br i1 %cmp1, label %latch, label %exit1 133 134latch: 135 %iv.next = add i32 %iv, 1 136 %cmp2 = icmp ult i32 %iv, %n 137 br i1 %cmp2, label %header, label %exit2 138exit1: 139 ret i32 %iv 140exit2: 141 %exitval = phi i32 [%iv2.lcssa, %latch] 142 ret i32 %exitval 143} 144 145; TODO: Generalize the code to handle other SCEV expressions 146define i32 @test3(i32 %n) { 147; CHECK-LABEL: @test3( 148; CHECK-NEXT: entry: 149; CHECK-NEXT: [[TMP0:%.*]] = add i32 [[N:%.*]], 1 150; CHECK-NEXT: br label [[HEADER:%.*]] 151; CHECK: header: 152; CHECK-NEXT: [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LATCH:%.*]] ] 153; CHECK-NEXT: [[EXPR:%.*]] = udiv i32 [[IV]], 5 154; CHECK-NEXT: [[V:%.*]] = load volatile i32, i32* @G 155; CHECK-NEXT: [[CMP1:%.*]] = icmp eq i32 [[V]], 0 156; CHECK-NEXT: br i1 [[CMP1]], label [[LATCH]], label [[EXIT1:%.*]] 157; CHECK: latch: 158; CHECK-NEXT: [[IV_NEXT]] = add i32 [[IV]], 1 159; CHECK-NEXT: [[EXITCOND:%.*]] = icmp ne i32 [[IV_NEXT]], [[TMP0]] 160; CHECK-NEXT: br i1 [[EXITCOND]], label [[HEADER]], label [[EXIT2:%.*]] 161; CHECK: exit1: 162; CHECK-NEXT: [[EXPR_LCSSA:%.*]] = phi i32 [ [[EXPR]], [[HEADER]] ] 163; CHECK-NEXT: ret i32 [[EXPR_LCSSA]] 164; CHECK: exit2: 165; CHECK-NEXT: [[EXPR_LCSSA1:%.*]] = phi i32 [ [[EXPR]], [[LATCH]] ] 166; CHECK-NEXT: ret i32 [[EXPR_LCSSA1]] 167; 168entry: 169 br label %header 170header: 171 %iv = phi i32 [0, %entry], [%iv.next, %latch] 172 %expr = udiv i32 %iv, 5 173 %v = load volatile i32, i32* @G 174 %cmp1 = icmp eq i32 %v, 0 175 br i1 %cmp1, label %latch, label %exit1 176 177latch: 178 %iv.next = add i32 %iv, 1 179 %cmp2 = icmp ult i32 %iv, %n 180 br i1 %cmp2, label %header, label %exit2 181exit1: 182 ret i32 %expr 183exit2: 184 ret i32 %expr 185} 186 187 188; A slightly more real example where we're searching for either a) the first 189; non-zero element, or b) the end of a memory region. 190define i32 @bounded_find(i32 %n) { 191; CHECK-LABEL: @bounded_find( 192; CHECK-NEXT: entry: 193; CHECK-NEXT: [[TMP0:%.*]] = add i32 [[N:%.*]], 1 194; CHECK-NEXT: br label [[HEADER:%.*]] 195; CHECK: header: 196; CHECK-NEXT: [[IV:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LATCH:%.*]] ] 197; CHECK-NEXT: [[ADDR:%.*]] = getelementptr i32, i32* @G, i32 [[IV]] 198; CHECK-NEXT: [[V:%.*]] = load i32, i32* [[ADDR]] 199; CHECK-NEXT: [[CMP1:%.*]] = icmp eq i32 [[V]], 0 200; CHECK-NEXT: br i1 [[CMP1]], label [[LATCH]], label [[EXIT1:%.*]] 201; CHECK: latch: 202; CHECK-NEXT: [[IV_NEXT]] = add i32 [[IV]], 1 203; CHECK-NEXT: [[EXITCOND:%.*]] = icmp ne i32 [[IV_NEXT]], [[TMP0]] 204; CHECK-NEXT: br i1 [[EXITCOND]], label [[HEADER]], label [[EXIT2:%.*]] 205; CHECK: exit1: 206; CHECK-NEXT: [[IV_LCSSA:%.*]] = phi i32 [ [[IV]], [[HEADER]] ] 207; CHECK-NEXT: ret i32 [[IV_LCSSA]] 208; CHECK: exit2: 209; CHECK-NEXT: ret i32 [[N]] 210; 211entry: 212 br label %header 213header: 214 %iv = phi i32 [0, %entry], [%iv.next, %latch] 215 %addr = getelementptr i32, i32* @G, i32 %iv 216 %v = load i32, i32* %addr 217 %cmp1 = icmp eq i32 %v, 0 218 br i1 %cmp1, label %latch, label %exit1 219 220latch: 221 %iv.next = add i32 %iv, 1 222 %cmp2 = icmp ult i32 %iv, %n 223 br i1 %cmp2, label %header, label %exit2 224exit1: 225 ret i32 %iv 226exit2: 227 ret i32 %iv 228} 229