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 14 define i32 @sansCanonical(i32* %base) nounwind { 15 entry: 16 br label %while.body 17 18 while.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 29 exit: 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 42 define i64 @earlyLoopTest(i64* %base) nounwind { 43 entry: 44 br label %loop 45 46 loop: 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 56 tail: 57 %cmp2 = icmp ne i64 %val, 0 58 br i1 %cmp2, label %loop, label %exit2 59 60 exit1: 61 ret i64 %s 62 63 exit2: 64 ret i64 %s.next 65 } 66 67 ; SCEV properly unrolls multi-exit loops. 68 ; 69 ; SCEV cannot currently unroll this loop. 70 ; It should ideally detect a trip count of 5. 71 ; rdar:14038809 [SCEV]: Optimize trip count computation for multi-exit loops. 72 ; CHECK-LABEL: @multiExit( 73 ; CHECKFIXME: getelementptr i32* %base, i32 10 74 ; CHECKFIXME-NEXT: load i32* 75 ; CHECKFIXME: br i1 false, label %l2.10, label %exit1 76 ; CHECKFIXME: l2.10: 77 ; CHECKFIXME-NOT: br 78 ; CHECKFIXME: ret i32 79 define i32 @multiExit(i32* %base) nounwind { 80 entry: 81 br label %l1 82 l1: 83 %iv1 = phi i32 [ 0, %entry ], [ %inc1, %l2 ] 84 %iv2 = phi i32 [ 0, %entry ], [ %inc2, %l2 ] 85 %inc1 = add i32 %iv1, 1 86 %inc2 = add i32 %iv2, 1 87 %adr = getelementptr i32* %base, i32 %iv1 88 %val = load i32* %adr 89 %cmp1 = icmp slt i32 %iv1, 5 90 br i1 %cmp1, label %l2, label %exit1 91 l2: 92 %cmp2 = icmp slt i32 %iv2, 10 93 br i1 %cmp2, label %l1, label %exit2 94 exit1: 95 ret i32 1 96 exit2: 97 ret i32 %val 98 } 99 100 101 ; SCEV should not unroll a multi-exit loops unless the latch block has 102 ; a known trip count, regardless of the early exit trip counts. The 103 ; LoopUnroll utility uses this assumption to optimize the latch 104 ; block's branch. 105 ; 106 ; CHECK-LABEL: @multiExitIncomplete( 107 ; CHECK: l3: 108 ; CHECK-NOT: br 109 ; CHECK: br i1 %cmp3, label %l1, label %exit3 110 define i32 @multiExitIncomplete(i32* %base) nounwind { 111 entry: 112 br label %l1 113 l1: 114 %iv1 = phi i32 [ 0, %entry ], [ %inc1, %l3 ] 115 %iv2 = phi i32 [ 0, %entry ], [ %inc2, %l3 ] 116 %inc1 = add i32 %iv1, 1 117 %inc2 = add i32 %iv2, 1 118 %adr = getelementptr i32* %base, i32 %iv1 119 %val = load i32* %adr 120 %cmp1 = icmp slt i32 %iv1, 5 121 br i1 %cmp1, label %l2, label %exit1 122 l2: 123 %cmp2 = icmp slt i32 %iv2, 10 124 br i1 %cmp2, label %l3, label %exit2 125 l3: 126 %cmp3 = icmp ne i32 %val, 0 127 br i1 %cmp3, label %l1, label %exit3 128 129 exit1: 130 ret i32 1 131 exit2: 132 ret i32 2 133 exit3: 134 ret i32 3 135 } 136 137 ; When loop unroll merges a loop exit with one of its parent loop's 138 ; exits, SCEV must forget its ExitNotTaken info. 139 ; 140 ; CHECK-LABEL: @nestedUnroll( 141 ; CHECK-NOT: br i1 142 ; CHECK: for.body87: 143 define void @nestedUnroll() nounwind { 144 entry: 145 br label %for.inc 146 147 for.inc: 148 br i1 false, label %for.inc, label %for.body38.preheader 149 150 for.body38.preheader: 151 br label %for.body38 152 153 for.body38: 154 %i.113 = phi i32 [ %inc76, %for.inc74 ], [ 0, %for.body38.preheader ] 155 %mul48 = mul nsw i32 %i.113, 6 156 br label %for.body43 157 158 for.body43: 159 %j.011 = phi i32 [ 0, %for.body38 ], [ %inc72, %for.body43 ] 160 %add49 = add nsw i32 %j.011, %mul48 161 %sh_prom50 = zext i32 %add49 to i64 162 %inc72 = add nsw i32 %j.011, 1 163 br i1 false, label %for.body43, label %for.inc74 164 165 for.inc74: 166 %inc76 = add nsw i32 %i.113, 1 167 br i1 false, label %for.body38, label %for.body87.preheader 168 169 for.body87.preheader: 170 br label %for.body87 171 172 for.body87: 173 br label %for.body87 174 } 175 176 ; PR16130: clang produces incorrect code with loop/expression at -O2 177 ; rdar:14036816 loop-unroll makes assumptions about undefined behavior 178 ; 179 ; The loop latch is assumed to exit after the first iteration because 180 ; of the induction variable's NSW flag. However, the loop latch's 181 ; equality test is skipped and the loop exits after the second 182 ; iteration via the early exit. So loop unrolling cannot assume that 183 ; the loop latch's exit count of zero is an upper bound on the number 184 ; of iterations. 185 ; 186 ; CHECK-LABEL: @nsw_latch( 187 ; CHECK: for.body: 188 ; CHECK: %b.03 = phi i32 [ 0, %entry ], [ %add, %for.cond ] 189 ; CHECK: return: 190 ; CHECK: %b.03.lcssa = phi i32 [ %b.03, %for.body ], [ %b.03, %for.cond ] 191 define void @nsw_latch(i32* %a) nounwind { 192 entry: 193 br label %for.body 194 195 for.body: ; preds = %for.cond, %entry 196 %b.03 = phi i32 [ 0, %entry ], [ %add, %for.cond ] 197 %tobool = icmp eq i32 %b.03, 0 198 %add = add nsw i32 %b.03, 8 199 br i1 %tobool, label %for.cond, label %return 200 201 for.cond: ; preds = %for.body 202 %cmp = icmp eq i32 %add, 13 203 br i1 %cmp, label %return, label %for.body 204 205 return: ; preds = %for.body, %for.cond 206 %b.03.lcssa = phi i32 [ %b.03, %for.body ], [ %b.03, %for.cond ] 207 %retval.0 = phi i32 [ 1, %for.body ], [ 0, %for.cond ] 208 store i32 %b.03.lcssa, i32* %a, align 4 209 ret void 210 } 211
