1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
2; RUN: opt -indvars -instcombine -S < %s | FileCheck %s
3
4;; Test that loop's exit value is rewritten to its initial
5;; value from loop preheader
6define i32 @test1(i32* %var) {
7; CHECK-LABEL: @test1(
8; CHECK-NEXT:  entry:
9; CHECK-NEXT:    [[COND:%.*]] = icmp eq i32* [[VAR:%.*]], null
10; CHECK-NEXT:    br label [[HEADER:%.*]]
11; CHECK:       header:
12; CHECK-NEXT:    br i1 [[COND]], label [[LOOP:%.*]], label [[EXIT:%.*]]
13; CHECK:       loop:
14; CHECK-NEXT:    br label [[HEADER]]
15; CHECK:       exit:
16; CHECK-NEXT:    ret i32 0
17;
18entry:
19  %cond = icmp eq i32* %var, null
20  br label %header
21
22header:
23  %phi_indvar = phi i32 [0, %entry], [%indvar, %loop]
24  br i1 %cond, label %loop, label %exit
25
26loop:
27  %indvar = add i32 %phi_indvar, 1
28  br label %header
29
30exit:
31  ret i32 %phi_indvar
32}
33
34;; Test that we can not rewrite loop exit value if it's not
35;; a phi node (%indvar is an add instruction in this test).
36define i32 @test2(i32* %var) {
37; CHECK-LABEL: @test2(
38; CHECK-NEXT:  entry:
39; CHECK-NEXT:    [[COND:%.*]] = icmp eq i32* [[VAR:%.*]], null
40; CHECK-NEXT:    br label [[HEADER:%.*]]
41; CHECK:       header:
42; CHECK-NEXT:    [[PHI_INDVAR:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INDVAR:%.*]], [[HEADER]] ]
43; CHECK-NEXT:    [[INDVAR]] = add i32 [[PHI_INDVAR]], 1
44; CHECK-NEXT:    br i1 [[COND]], label [[HEADER]], label [[EXIT:%.*]]
45; CHECK:       exit:
46; CHECK-NEXT:    ret i32 [[INDVAR]]
47;
48entry:
49  %cond = icmp eq i32* %var, null
50  br label %header
51
52header:
53  %phi_indvar = phi i32 [0, %entry], [%indvar, %header]
54  %indvar = add i32 %phi_indvar, 1
55  br i1 %cond, label %header, label %exit
56
57exit:
58  ret i32 %indvar
59}
60
61;; Test that we can not rewrite loop exit value if the condition
62;; is not in loop header.
63define i32 @test3(i32* %var) {
64; CHECK-LABEL: @test3(
65; CHECK-NEXT:  entry:
66; CHECK-NEXT:    [[COND1:%.*]] = icmp eq i32* [[VAR:%.*]], null
67; CHECK-NEXT:    br label [[HEADER:%.*]]
68; CHECK:       header:
69; CHECK-NEXT:    [[PHI_INDVAR:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INDVAR:%.*]], [[HEADER_BACKEDGE:%.*]] ]
70; CHECK-NEXT:    [[INDVAR]] = add i32 [[PHI_INDVAR]], 1
71; CHECK-NEXT:    [[COND2:%.*]] = icmp eq i32 [[INDVAR]], 10
72; CHECK-NEXT:    br i1 [[COND2]], label [[HEADER_BACKEDGE]], label [[BODY:%.*]]
73; CHECK:       header.backedge:
74; CHECK-NEXT:    br label [[HEADER]]
75; CHECK:       body:
76; CHECK-NEXT:    br i1 [[COND1]], label [[HEADER_BACKEDGE]], label [[EXIT:%.*]]
77; CHECK:       exit:
78; CHECK-NEXT:    ret i32 [[PHI_INDVAR]]
79;
80entry:
81  %cond1 = icmp eq i32* %var, null
82  br label %header
83
84header:
85  %phi_indvar = phi i32 [0, %entry], [%indvar, %header], [%indvar, %body]
86  %indvar = add i32 %phi_indvar, 1
87  %cond2 = icmp eq i32 %indvar, 10
88  br i1 %cond2, label %header, label %body
89
90body:
91  br i1 %cond1, label %header, label %exit
92
93exit:
94  ret i32 %phi_indvar
95}
96
97
98; Multiple exits dominating latch
99define i32 @test4(i1 %cond1, i1 %cond2) {
100; CHECK-LABEL: @test4(
101; CHECK-NEXT:  entry:
102; CHECK-NEXT:    br label [[HEADER:%.*]]
103; CHECK:       header:
104; CHECK-NEXT:    br i1 [[COND1:%.*]], label [[LOOP:%.*]], label [[EXIT:%.*]]
105; CHECK:       loop:
106; CHECK-NEXT:    br i1 [[COND2:%.*]], label [[HEADER]], label [[EXIT]]
107; CHECK:       exit:
108; CHECK-NEXT:    ret i32 0
109;
110entry:
111  br label %header
112
113header:
114  %phi_indvar = phi i32 [0, %entry], [%indvar, %loop]
115  br i1 %cond1, label %loop, label %exit
116
117loop:
118  %indvar = add i32 %phi_indvar, 1
119  br i1 %cond2, label %header, label %exit
120
121exit:
122  ret i32 %phi_indvar
123}
124
125; A conditionally executed exit.
126define i32 @test5(i1* %addr, i1 %cond2) {
127; CHECK-LABEL: @test5(
128; CHECK-NEXT:  entry:
129; CHECK-NEXT:    br label [[HEADER:%.*]]
130; CHECK:       header:
131; CHECK-NEXT:    [[PHI_INDVAR:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INDVAR:%.*]], [[LOOP:%.*]] ]
132; CHECK-NEXT:    [[COND1:%.*]] = load volatile i1, i1* [[ADDR:%.*]], align 1
133; CHECK-NEXT:    br i1 [[COND1]], label [[LOOP]], label [[MAYBE:%.*]]
134; CHECK:       maybe:
135; CHECK-NEXT:    br i1 [[COND2:%.*]], label [[LOOP]], label [[EXIT:%.*]]
136; CHECK:       loop:
137; CHECK-NEXT:    [[INDVAR]] = add i32 [[PHI_INDVAR]], 1
138; CHECK-NEXT:    br label [[HEADER]]
139; CHECK:       exit:
140; CHECK-NEXT:    ret i32 [[PHI_INDVAR]]
141;
142entry:
143  br label %header
144
145header:
146  %phi_indvar = phi i32 [0, %entry], [%indvar, %loop]
147  %cond1 = load volatile i1, i1* %addr
148  br i1 %cond1, label %loop, label %maybe
149
150maybe:
151  br i1 %cond2, label %loop, label %exit
152
153loop:
154  %indvar = add i32 %phi_indvar, 1
155  br label %header
156
157exit:
158  ret i32 %phi_indvar
159}
160
161define i16 @pr57336(i16 %end, i16 %m) mustprogress {
162; CHECK-LABEL: @pr57336(
163; CHECK-NEXT:  entry:
164; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
165; CHECK:       for.body:
166; CHECK-NEXT:    [[INC8:%.*]] = phi i16 [ [[INC:%.*]], [[FOR_BODY]] ], [ 0, [[ENTRY:%.*]] ]
167; CHECK-NEXT:    [[INC]] = add nuw nsw i16 [[INC8]], 1
168; CHECK-NEXT:    [[MUL:%.*]] = mul nsw i16 [[INC8]], [[M:%.*]]
169; CHECK-NEXT:    [[CMP_NOT:%.*]] = icmp sgt i16 [[MUL]], [[END:%.*]]
170; CHECK-NEXT:    br i1 [[CMP_NOT]], label [[CRIT_EDGE:%.*]], label [[FOR_BODY]]
171; CHECK:       crit_edge:
172; CHECK-NEXT:    [[TMP0:%.*]] = call i16 @llvm.smax.i16(i16 [[END]], i16 -1)
173; CHECK-NEXT:    [[SMAX:%.*]] = add nsw i16 [[TMP0]], 1
174; CHECK-NEXT:    [[TMP1:%.*]] = icmp ne i16 [[SMAX]], 0
175; CHECK-NEXT:    [[UMIN:%.*]] = zext i1 [[TMP1]] to i16
176; CHECK-NEXT:    [[TMP2:%.*]] = sub nsw i16 [[SMAX]], [[UMIN]]
177; CHECK-NEXT:    [[UMAX:%.*]] = call i16 @llvm.umax.i16(i16 [[M]], i16 1)
178; CHECK-NEXT:    [[TMP3:%.*]] = udiv i16 [[TMP2]], [[UMAX]]
179; CHECK-NEXT:    [[TMP4:%.*]] = add i16 [[TMP3]], [[UMIN]]
180; CHECK-NEXT:    ret i16 [[TMP4]]
181;
182entry:
183  br label %for.body
184
185for.body:
186  %inc8 = phi i16 [ %inc, %for.body ], [ 0, %entry ]
187  %inc137 = phi i32 [ %inc1, %for.body ], [ 0, %entry ]
188  %inc1 = add nsw i32 %inc137, 1
189  %inc = add nsw i16 %inc8, 1
190  %mul = mul nsw i16 %m, %inc8
191  %cmp.not = icmp slt i16 %end, %mul
192  br i1 %cmp.not, label %crit_edge, label %for.body
193
194crit_edge:
195  %inc137.lcssa = phi i32 [ %inc137, %for.body ]
196  %conv = trunc i32 %inc137.lcssa to i16
197  ret i16 %conv
198}
199
200