1; RUN: opt < %s -S -indvars -loop-unroll -verify-loop-info | FileCheck %s 2; 3; Unit tests for loop unrolling using ScalarEvolution to compute trip counts. 4; 5; Indvars is run first to generate an "old" SCEV result. Some unit 6; tests may check that SCEV is properly invalidated between passes. 7 8; Completely unroll loops without a canonical IV. 9; 10; CHECK-LABEL: @sansCanonical( 11; CHECK-NOT: phi 12; CHECK-NOT: icmp 13; CHECK: ret 14define i32 @sansCanonical(i32* %base) nounwind { 15entry: 16 br label %while.body 17 18while.body: 19 %iv = phi i64 [ 10, %entry ], [ %iv.next, %while.body ] 20 %sum = phi i32 [ 0, %entry ], [ %sum.next, %while.body ] 21 %iv.next = add i64 %iv, -1 22 %adr = getelementptr inbounds i32* %base, i64 %iv.next 23 %tmp = load i32* %adr, align 8 24 %sum.next = add i32 %sum, %tmp 25 %iv.narrow = trunc i64 %iv.next to i32 26 %cmp.i65 = icmp sgt i32 %iv.narrow, 0 27 br i1 %cmp.i65, label %while.body, label %exit 28 29exit: 30 ret i32 %sum 31} 32 33; SCEV unrolling properly handles loops with multiple exits. In this 34; case, the computed trip count based on a canonical IV is *not* for a 35; latch block. Canonical unrolling incorrectly unrolls it, but SCEV 36; unrolling does not. 37; 38; CHECK-LABEL: @earlyLoopTest( 39; CHECK: tail: 40; CHECK-NOT: br 41; CHECK: br i1 %cmp2, label %loop, label %exit2 42define i64 @earlyLoopTest(i64* %base) nounwind { 43entry: 44 br label %loop 45 46loop: 47 %iv = phi i64 [ 0, %entry ], [ %inc, %tail ] 48 %s = phi i64 [ 0, %entry ], [ %s.next, %tail ] 49 %adr = getelementptr i64* %base, i64 %iv 50 %val = load i64* %adr 51 %s.next = add i64 %s, %val 52 %inc = add i64 %iv, 1 53 %cmp = icmp ne i64 %inc, 4 54 br i1 %cmp, label %tail, label %exit1 55 56tail: 57 %cmp2 = icmp ne i64 %val, 0 58 br i1 %cmp2, label %loop, label %exit2 59 60exit1: 61 ret i64 %s 62 63exit2: 64 ret i64 %s.next 65} 66 67; SCEV properly unrolls multi-exit loops. 68; 69; CHECK-LABEL: @multiExit( 70; CHECK: getelementptr i32* %base, i32 10 71; CHECK-NEXT: load i32* 72; CHECK: br i1 false, label %l2.10, label %exit1 73; CHECK: l2.10: 74; CHECK-NOT: br 75; CHECK: ret i32 76define i32 @multiExit(i32* %base) nounwind { 77entry: 78 br label %l1 79l1: 80 %iv1 = phi i32 [ 0, %entry ], [ %inc1, %l2 ] 81 %iv2 = phi i32 [ 0, %entry ], [ %inc2, %l2 ] 82 %inc1 = add i32 %iv1, 1 83 %inc2 = add i32 %iv2, 1 84 %adr = getelementptr i32* %base, i32 %iv1 85 %val = load i32* %adr 86 %cmp1 = icmp slt i32 %iv1, 5 87 br i1 %cmp1, label %l2, label %exit1 88l2: 89 %cmp2 = icmp slt i32 %iv2, 10 90 br i1 %cmp2, label %l1, label %exit2 91exit1: 92 ret i32 1 93exit2: 94 ret i32 %val 95} 96 97 98; SCEV should not unroll a multi-exit loops unless the latch block has 99; a known trip count, regardless of the early exit trip counts. The 100; LoopUnroll utility uses this assumption to optimize the latch 101; block's branch. 102; 103; CHECK-LABEL: @multiExitIncomplete( 104; CHECK: l3: 105; CHECK-NOT: br 106; CHECK: br i1 %cmp3, label %l1, label %exit3 107define i32 @multiExitIncomplete(i32* %base) nounwind { 108entry: 109 br label %l1 110l1: 111 %iv1 = phi i32 [ 0, %entry ], [ %inc1, %l3 ] 112 %iv2 = phi i32 [ 0, %entry ], [ %inc2, %l3 ] 113 %inc1 = add i32 %iv1, 1 114 %inc2 = add i32 %iv2, 1 115 %adr = getelementptr i32* %base, i32 %iv1 116 %val = load i32* %adr 117 %cmp1 = icmp slt i32 %iv1, 5 118 br i1 %cmp1, label %l2, label %exit1 119l2: 120 %cmp2 = icmp slt i32 %iv2, 10 121 br i1 %cmp2, label %l3, label %exit2 122l3: 123 %cmp3 = icmp ne i32 %val, 0 124 br i1 %cmp3, label %l1, label %exit3 125 126exit1: 127 ret i32 1 128exit2: 129 ret i32 2 130exit3: 131 ret i32 3 132} 133 134; When loop unroll merges a loop exit with one of its parent loop's 135; exits, SCEV must forget its ExitNotTaken info. 136; 137; CHECK-LABEL: @nestedUnroll( 138; CHECK-NOT: br i1 139; CHECK: for.body87: 140define void @nestedUnroll() nounwind { 141entry: 142 br label %for.inc 143 144for.inc: 145 br i1 false, label %for.inc, label %for.body38.preheader 146 147for.body38.preheader: 148 br label %for.body38 149 150for.body38: 151 %i.113 = phi i32 [ %inc76, %for.inc74 ], [ 0, %for.body38.preheader ] 152 %mul48 = mul nsw i32 %i.113, 6 153 br label %for.body43 154 155for.body43: 156 %j.011 = phi i32 [ 0, %for.body38 ], [ %inc72, %for.body43 ] 157 %add49 = add nsw i32 %j.011, %mul48 158 %sh_prom50 = zext i32 %add49 to i64 159 %inc72 = add nsw i32 %j.011, 1 160 br i1 false, label %for.body43, label %for.inc74 161 162for.inc74: 163 %inc76 = add nsw i32 %i.113, 1 164 br i1 false, label %for.body38, label %for.body87.preheader 165 166for.body87.preheader: 167 br label %for.body87 168 169for.body87: 170 br label %for.body87 171} 172 173; PR16130: clang produces incorrect code with loop/expression at -O2 174; rdar:14036816 loop-unroll makes assumptions about undefined behavior 175; 176; The loop latch is assumed to exit after the first iteration because 177; of the induction variable's NSW flag. However, the loop latch's 178; equality test is skipped and the loop exits after the second 179; iteration via the early exit. So loop unrolling cannot assume that 180; the loop latch's exit count of zero is an upper bound on the number 181; of iterations. 182; 183; CHECK-LABEL: @nsw_latch( 184; CHECK: for.body: 185; CHECK: %b.03 = phi i32 [ 0, %entry ], [ %add, %for.cond ] 186; CHECK: return: 187; CHECK: %b.03.lcssa = phi i32 [ %b.03, %for.body ], [ %b.03, %for.cond ] 188define void @nsw_latch(i32* %a) nounwind { 189entry: 190 br label %for.body 191 192for.body: ; preds = %for.cond, %entry 193 %b.03 = phi i32 [ 0, %entry ], [ %add, %for.cond ] 194 %tobool = icmp eq i32 %b.03, 0 195 %add = add nsw i32 %b.03, 8 196 br i1 %tobool, label %for.cond, label %return 197 198for.cond: ; preds = %for.body 199 %cmp = icmp eq i32 %add, 13 200 br i1 %cmp, label %return, label %for.body 201 202return: ; preds = %for.body, %for.cond 203 %b.03.lcssa = phi i32 [ %b.03, %for.body ], [ %b.03, %for.cond ] 204 %retval.0 = phi i32 [ 1, %for.body ], [ 0, %for.cond ] 205 store i32 %b.03.lcssa, i32* %a, align 4 206 ret void 207} 208