xref: /llvm-project/llvm/test/Transforms/LoopIdiom/X86/cttz.ll (revision 48c6b2729e2111bec08799c65b8b459e12413546) 
1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
2; RUN: opt -passes=loop-idiom -mtriple=x86_64 -mcpu=core-avx2 < %s -S | FileCheck --check-prefix=ALL %s
3; RUN: opt -passes=loop-idiom -mtriple=x86_64 -mcpu=corei7 < %s -S | FileCheck --check-prefix=ALL %s
4
5; Recognize CTTZ builtin pattern.
6; Here it will replace the loop -
7; assume builtin is always profitable.
8;
9; int cttz_zero_check(int n)
10; {
11;   int i = 0;
12;   while(n) {
13;     n <<= 1;
14;     i++;
15;   }
16;   return i;
17; }
18;
19define i32 @cttz_zero_check(i32 %n) {
20; ALL-LABEL: @cttz_zero_check(
21; ALL-NEXT:  entry:
22; ALL-NEXT:    [[TOBOOL4:%.*]] = icmp eq i32 [[N:%.*]], 0
23; ALL-NEXT:    br i1 [[TOBOOL4]], label [[WHILE_END:%.*]], label [[WHILE_BODY_PREHEADER:%.*]]
24; ALL:       while.body.preheader:
25; ALL-NEXT:    [[TMP0:%.*]] = call i32 @llvm.cttz.i32(i32 [[N]], i1 true)
26; ALL-NEXT:    [[TMP1:%.*]] = sub i32 32, [[TMP0]]
27; ALL-NEXT:    br label [[WHILE_BODY:%.*]]
28; ALL:       while.body:
29; ALL-NEXT:    [[TCPHI:%.*]] = phi i32 [ [[TMP1]], [[WHILE_BODY_PREHEADER]] ], [ [[TCDEC:%.*]], [[WHILE_BODY]] ]
30; ALL-NEXT:    [[I_06:%.*]] = phi i32 [ [[INC:%.*]], [[WHILE_BODY]] ], [ 0, [[WHILE_BODY_PREHEADER]] ]
31; ALL-NEXT:    [[N_ADDR_05:%.*]] = phi i32 [ [[SHL:%.*]], [[WHILE_BODY]] ], [ [[N]], [[WHILE_BODY_PREHEADER]] ]
32; ALL-NEXT:    [[SHL]] = shl i32 [[N_ADDR_05]], 1
33; ALL-NEXT:    [[INC]] = add nsw i32 [[I_06]], 1
34; ALL-NEXT:    [[TCDEC]] = sub nsw i32 [[TCPHI]], 1
35; ALL-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[TCDEC]], 0
36; ALL-NEXT:    br i1 [[TOBOOL]], label [[WHILE_END_LOOPEXIT:%.*]], label [[WHILE_BODY]]
37; ALL:       while.end.loopexit:
38; ALL-NEXT:    [[INC_LCSSA:%.*]] = phi i32 [ [[TMP1]], [[WHILE_BODY]] ]
39; ALL-NEXT:    br label [[WHILE_END]]
40; ALL:       while.end:
41; ALL-NEXT:    [[I_0_LCSSA:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC_LCSSA]], [[WHILE_END_LOOPEXIT]] ]
42; ALL-NEXT:    ret i32 [[I_0_LCSSA]]
43;
44entry:
45  %tobool4 = icmp eq i32 %n, 0
46  br i1 %tobool4, label %while.end, label %while.body.preheader
47
48while.body.preheader:                             ; preds = %entry
49  br label %while.body
50
51while.body:                                       ; preds = %while.body.preheader, %while.body
52  %i.06 = phi i32 [ %inc, %while.body ], [ 0, %while.body.preheader ]
53  %n.addr.05 = phi i32 [ %shl, %while.body ], [ %n, %while.body.preheader ]
54  %shl = shl i32 %n.addr.05, 1
55  %inc = add nsw i32 %i.06, 1
56  %tobool = icmp eq i32 %shl, 0
57  br i1 %tobool, label %while.end.loopexit, label %while.body
58
59while.end.loopexit:                               ; preds = %while.body
60  br label %while.end
61
62while.end:                                        ; preds = %while.end.loopexit, %entry
63  %i.0.lcssa = phi i32 [ 0, %entry ], [ %inc, %while.end.loopexit ]
64  ret i32 %i.0.lcssa
65}
66
67; Recognize CTTZ builtin pattern.
68; Here it will replace the loop -
69; assume builtin is always profitable.
70;
71; int cttz(int n)
72; {
73;   int i = 0;
74;   while(n <<= 1) {
75;     i++;
76;   }
77;   return i;
78; }
79;
80define i32 @cttz(i32 %n) {
81; ALL-LABEL: @cttz(
82; ALL-NEXT:  entry:
83; ALL-NEXT:    [[TMP0:%.*]] = shl i32 [[N:%.*]], 1
84; ALL-NEXT:    [[TMP1:%.*]] = call i32 @llvm.cttz.i32(i32 [[TMP0]], i1 false)
85; ALL-NEXT:    [[TMP2:%.*]] = sub i32 32, [[TMP1]]
86; ALL-NEXT:    [[TMP3:%.*]] = add i32 [[TMP2]], 1
87; ALL-NEXT:    br label [[WHILE_COND:%.*]]
88; ALL:       while.cond:
89; ALL-NEXT:    [[TCPHI:%.*]] = phi i32 [ [[TMP3]], [[ENTRY:%.*]] ], [ [[TCDEC:%.*]], [[WHILE_COND]] ]
90; ALL-NEXT:    [[N_ADDR_0:%.*]] = phi i32 [ [[N]], [[ENTRY]] ], [ [[SHL:%.*]], [[WHILE_COND]] ]
91; ALL-NEXT:    [[I_0:%.*]] = phi i32 [ 0, [[ENTRY]] ], [ [[INC:%.*]], [[WHILE_COND]] ]
92; ALL-NEXT:    [[SHL]] = shl i32 [[N_ADDR_0]], 1
93; ALL-NEXT:    [[TCDEC]] = sub nsw i32 [[TCPHI]], 1
94; ALL-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[TCDEC]], 0
95; ALL-NEXT:    [[INC]] = add nsw i32 [[I_0]], 1
96; ALL-NEXT:    br i1 [[TOBOOL]], label [[WHILE_END:%.*]], label [[WHILE_COND]]
97; ALL:       while.end:
98; ALL-NEXT:    [[I_0_LCSSA:%.*]] = phi i32 [ [[TMP2]], [[WHILE_COND]] ]
99; ALL-NEXT:    ret i32 [[I_0_LCSSA]]
100;
101entry:
102  br label %while.cond
103
104while.cond:                                       ; preds = %while.cond, %entry
105  %n.addr.0 = phi i32 [ %n, %entry ], [ %shl, %while.cond ]
106  %i.0 = phi i32 [ 0, %entry ], [ %inc, %while.cond ]
107  %shl = shl i32 %n.addr.0, 1
108  %tobool = icmp eq i32 %shl, 0
109  %inc = add nsw i32 %i.0, 1
110  br i1 %tobool, label %while.end, label %while.cond
111
112while.end:                                        ; preds = %while.cond
113  ret i32 %i.0
114}
115
116; Recognize CTTZ builtin pattern.
117; Here it will replace the loop -
118; assume builtin is always profitable.
119;
120; int ctlz_decrement(int n)
121; {
122;   int i = 32;
123;   while(n) {
124;     n <<= 1;
125;     i--;
126;   }
127;   return i;
128; }
129;
130define i32 @cttz_decrement(i32 %n) {
131; ALL-LABEL: @cttz_decrement(
132; ALL-NEXT:  entry:
133; ALL-NEXT:    [[TOBOOL4:%.*]] = icmp eq i32 [[N:%.*]], 0
134; ALL-NEXT:    br i1 [[TOBOOL4]], label [[WHILE_END:%.*]], label [[WHILE_BODY_PREHEADER:%.*]]
135; ALL:       while.body.preheader:
136; ALL-NEXT:    [[TMP0:%.*]] = call i32 @llvm.cttz.i32(i32 [[N]], i1 true)
137; ALL-NEXT:    [[TMP1:%.*]] = sub i32 32, [[TMP0]]
138; ALL-NEXT:    [[TMP2:%.*]] = sub i32 32, [[TMP1]]
139; ALL-NEXT:    br label [[WHILE_BODY:%.*]]
140; ALL:       while.body:
141; ALL-NEXT:    [[TCPHI:%.*]] = phi i32 [ [[TMP1]], [[WHILE_BODY_PREHEADER]] ], [ [[TCDEC:%.*]], [[WHILE_BODY]] ]
142; ALL-NEXT:    [[I_06:%.*]] = phi i32 [ [[INC:%.*]], [[WHILE_BODY]] ], [ 32, [[WHILE_BODY_PREHEADER]] ]
143; ALL-NEXT:    [[N_ADDR_05:%.*]] = phi i32 [ [[SHL:%.*]], [[WHILE_BODY]] ], [ [[N]], [[WHILE_BODY_PREHEADER]] ]
144; ALL-NEXT:    [[SHL]] = shl i32 [[N_ADDR_05]], 1
145; ALL-NEXT:    [[INC]] = add nsw i32 [[I_06]], -1
146; ALL-NEXT:    [[TCDEC]] = sub nsw i32 [[TCPHI]], 1
147; ALL-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[TCDEC]], 0
148; ALL-NEXT:    br i1 [[TOBOOL]], label [[WHILE_END_LOOPEXIT:%.*]], label [[WHILE_BODY]]
149; ALL:       while.end.loopexit:
150; ALL-NEXT:    [[INC_LCSSA:%.*]] = phi i32 [ [[TMP2]], [[WHILE_BODY]] ]
151; ALL-NEXT:    br label [[WHILE_END]]
152; ALL:       while.end:
153; ALL-NEXT:    [[I_0_LCSSA:%.*]] = phi i32 [ 32, [[ENTRY:%.*]] ], [ [[INC_LCSSA]], [[WHILE_END_LOOPEXIT]] ]
154; ALL-NEXT:    ret i32 [[I_0_LCSSA]]
155;
156entry:
157  %tobool4 = icmp eq i32 %n, 0
158  br i1 %tobool4, label %while.end, label %while.body.preheader
159
160while.body.preheader:                             ; preds = %entry
161  br label %while.body
162
163while.body:                                       ; preds = %while.body.preheader, %while.body
164  %i.06 = phi i32 [ %inc, %while.body ], [ 32, %while.body.preheader ]
165  %n.addr.05 = phi i32 [ %shl, %while.body ], [ %n, %while.body.preheader ]
166  %shl = shl i32 %n.addr.05, 1
167  %inc = add nsw i32 %i.06, -1
168  %tobool = icmp eq i32 %shl, 0
169  br i1 %tobool, label %while.end.loopexit, label %while.body
170
171while.end.loopexit:                               ; preds = %while.body
172  br label %while.end
173
174while.end:                                        ; preds = %while.end.loopexit, %entry
175  %i.0.lcssa = phi i32 [ 32, %entry ], [ %inc, %while.end.loopexit ]
176  ret i32 %i.0.lcssa
177}
178
179; Recognize CTTZ builtin pattern.
180; Here it will replace the loop -
181; assume builtin is always profitable.
182;
183; int cttz_shl_decrement(int n)
184; {
185;   int i = 31;
186;   while(n <<= 1) {
187;     i--;
188;   }
189;   return i;
190; }
191;
192define i32 @cttz_shl_decrement(i32 %n) {
193; ALL-LABEL: @cttz_shl_decrement(
194; ALL-NEXT:  entry:
195; ALL-NEXT:    [[TMP0:%.*]] = shl i32 [[N:%.*]], 1
196; ALL-NEXT:    [[TMP1:%.*]] = call i32 @llvm.cttz.i32(i32 [[TMP0]], i1 false)
197; ALL-NEXT:    [[TMP2:%.*]] = sub i32 32, [[TMP1]]
198; ALL-NEXT:    [[TMP3:%.*]] = add i32 [[TMP2]], 1
199; ALL-NEXT:    [[TMP4:%.*]] = sub i32 31, [[TMP2]]
200; ALL-NEXT:    br label [[WHILE_COND:%.*]]
201; ALL:       while.cond:
202; ALL-NEXT:    [[TCPHI:%.*]] = phi i32 [ [[TMP3]], [[ENTRY:%.*]] ], [ [[TCDEC:%.*]], [[WHILE_COND]] ]
203; ALL-NEXT:    [[N_ADDR_0:%.*]] = phi i32 [ [[N]], [[ENTRY]] ], [ [[SHL:%.*]], [[WHILE_COND]] ]
204; ALL-NEXT:    [[I_0:%.*]] = phi i32 [ 31, [[ENTRY]] ], [ [[INC:%.*]], [[WHILE_COND]] ]
205; ALL-NEXT:    [[SHL]] = shl i32 [[N_ADDR_0]], 1
206; ALL-NEXT:    [[TCDEC]] = sub nsw i32 [[TCPHI]], 1
207; ALL-NEXT:    [[TOBOOL:%.*]] = icmp eq i32 [[TCDEC]], 0
208; ALL-NEXT:    [[INC]] = add nsw i32 [[I_0]], -1
209; ALL-NEXT:    br i1 [[TOBOOL]], label [[WHILE_END:%.*]], label [[WHILE_COND]]
210; ALL:       while.end:
211; ALL-NEXT:    [[I_0_LCSSA:%.*]] = phi i32 [ [[TMP4]], [[WHILE_COND]] ]
212; ALL-NEXT:    ret i32 [[I_0_LCSSA]]
213;
214entry:
215  br label %while.cond
216
217while.cond:                                       ; preds = %while.cond, %entry
218  %n.addr.0 = phi i32 [ %n, %entry ], [ %shl, %while.cond ]
219  %i.0 = phi i32 [ 31, %entry ], [ %inc, %while.cond ]
220  %shl = shl i32 %n.addr.0, 1
221  %tobool = icmp eq i32 %shl, 0
222  %inc = add nsw i32 %i.0, -1
223  br i1 %tobool, label %while.end, label %while.cond
224
225while.end:                                        ; preds = %while.cond
226  ret i32 %i.0
227}
228