1 ; RUN: opt < %s -S -indvars -loop-unroll -verify-loop-info | FileCheck %s
3 ; Unit tests for loop unrolling using ScalarEvolution to compute trip counts.
5 ; Indvars is run first to generate an "old" SCEV result. Some unit
6 ; tests may check that SCEV is properly invalidated between passes.
8 ; Completely unroll loops without a canonical IV.
10 ; CHECK-LABEL: @sansCanonical(
14 define i32 @sansCanonical(i32* %base) nounwind {
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
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
38 ; CHECK-LABEL: @earlyLoopTest(
41 ; CHECK: br i1 %cmp2, label %loop, label %exit2
42 define i64 @earlyLoopTest(i64* %base) nounwind {
47 %iv = phi i64 [ 0, %entry ], [ %inc, %tail ]
48 %s = phi i64 [ 0, %entry ], [ %s.next, %tail ]
49 %adr = getelementptr i64* %base, i64 %iv
51 %s.next = add i64 %s, %val
53 %cmp = icmp ne i64 %inc, 4
54 br i1 %cmp, label %tail, label %exit1
57 %cmp2 = icmp ne i64 %val, 0
58 br i1 %cmp2, label %loop, label %exit2
67 ; SCEV properly unrolls multi-exit loops.
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
79 define i32 @multiExit(i32* %base) nounwind {
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
89 %cmp1 = icmp slt i32 %iv1, 5
90 br i1 %cmp1, label %l2, label %exit1
92 %cmp2 = icmp slt i32 %iv2, 10
93 br i1 %cmp2, label %l1, label %exit2
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
106 ; CHECK-LABEL: @multiExitIncomplete(
109 ; CHECK: br i1 %cmp3, label %l1, label %exit3
110 define i32 @multiExitIncomplete(i32* %base) nounwind {
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
123 %cmp2 = icmp slt i32 %iv2, 10
124 br i1 %cmp2, label %l3, label %exit2
126 %cmp3 = icmp ne i32 %val, 0
127 br i1 %cmp3, label %l1, label %exit3
137 ; When loop unroll merges a loop exit with one of its parent loop's
138 ; exits, SCEV must forget its ExitNotTaken info.
140 ; CHECK-LABEL: @nestedUnroll(
143 define void @nestedUnroll() nounwind {
148 br i1 false, label %for.inc, label %for.body38.preheader
150 for.body38.preheader:
154 %i.113 = phi i32 [ %inc76, %for.inc74 ], [ 0, %for.body38.preheader ]
155 %mul48 = mul nsw i32 %i.113, 6
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
166 %inc76 = add nsw i32 %i.113, 1
167 br i1 false, label %for.body38, label %for.body87.preheader
169 for.body87.preheader:
176 ; PR16130: clang produces incorrect code with loop/expression at -O2
177 ; rdar:14036816 loop-unroll makes assumptions about undefined behavior
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
186 ; CHECK-LABEL: @nsw_latch(
188 ; CHECK: %b.03 = phi i32 [ 0, %entry ], [ %add, %for.cond ]
190 ; CHECK: %b.03.lcssa = phi i32 [ %b.03, %for.body ], [ %b.03, %for.cond ]
191 define void @nsw_latch(i32* %a) nounwind {
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
201 for.cond: ; preds = %for.body
202 %cmp = icmp eq i32 %add, 13
203 br i1 %cmp, label %return, label %for.body
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