Skip to content

Commit b08862c

Browse files
adibiagioadibiagio
committedFeb 12, 2015
[TTI] Teach the cost heuristic how to query TLI to check if a zext/trunc is 'free' for the target.
Now that SimplifyCFG uses TTI for the cost heuristic, we can teach BasicTTIImpl how to query TLI in order to get a more accurate cost for truncates and zero-extends. Before this patch, the basic cost heuristic in TargetTransformInfoImplCRTPBase would have conservatively returned a 'default' TCC_Basic for all zero-extends, and TCC_Free for truncates on native types. This patch improves the heuristic so that we query TLI (if available) to get more accurate answers. If TLI is available, then methods 'isZExtFree' and 'isTruncateFree' can be used to check if a zext/trunc is free for the target. Added more test cases to SimplifyCFG/X86/speculate-cttz-ctlz.ll. With this change, SimplifyCFG is now able to speculate a 'cheap' cttz/ctlz immediately followed by a free zext/trunc. Differential Revision: http://reviews.llvm.org/D7585 llvm-svn: 228923
1 parent fe41288 commit b08862c

File tree

3 files changed

+209
-2
lines changed

3 files changed

+209
-2
lines changed
 

Diff for: ‎llvm/include/llvm/Analysis/TargetTransformInfoImpl.h

+1-2
Original file line numberDiff line numberDiff line change
@@ -421,8 +421,7 @@ class TargetTransformInfoImplCRTPBase : public TargetTransformInfoImplBase {
421421
return TTI::TCC_Free;
422422
}
423423

424-
// Otherwise delegate to the fully generic implementations.
425-
return getOperationCost(
424+
return static_cast<T *>(this)->getOperationCost(
426425
Operator::getOpcode(U), U->getType(),
427426
U->getNumOperands() == 1 ? U->getOperand(0)->getType() : nullptr);
428427
}

Diff for: ‎llvm/include/llvm/CodeGen/BasicTTIImpl.h

+19
Original file line numberDiff line numberDiff line change
@@ -195,6 +195,25 @@ class BasicTTIImplBase : public TargetTransformInfoImplCRTPBase<T> {
195195
return TargetTransformInfo::TCC_Basic;
196196
}
197197

198+
unsigned getOperationCost(unsigned Opcode, Type *Ty, Type *OpTy) {
199+
const TargetLoweringBase *TLI = getTLI();
200+
switch (Opcode) {
201+
default: break;
202+
case Instruction::Trunc: {
203+
if (TLI->isTruncateFree(OpTy, Ty))
204+
return TargetTransformInfo::TCC_Free;
205+
return TargetTransformInfo::TCC_Basic;
206+
}
207+
case Instruction::ZExt: {
208+
if (TLI->isZExtFree(OpTy, Ty))
209+
return TargetTransformInfo::TCC_Free;
210+
return TargetTransformInfo::TCC_Basic;
211+
}
212+
}
213+
214+
return BaseT::getOperationCost(Opcode, Ty, OpTy);
215+
}
216+
198217
void getUnrollingPreferences(Loop *L, TTI::UnrollingPreferences &UP) {
199218
// This unrolling functionality is target independent, but to provide some
200219
// motivation for its intended use, for x86:

Diff for: ‎llvm/test/Transforms/SimplifyCFG/X86/speculate-cttz-ctlz.ll

+189
Original file line numberDiff line numberDiff line change
@@ -133,6 +133,195 @@ cond.end: ; preds = %entry, %cond.true
133133
ret i16 %cond
134134
}
135135

136+
; The following tests verify that calls to cttz/ctlz are speculated even if
137+
; basic block %cond.true has an extra zero extend/truncate which is "free"
138+
; for the target.
139+
140+
define i64 @test1e(i32 %x) {
141+
; ALL-LABEL: @test1e(
142+
; ALL: [[COND:%[A-Za-z0-9]+]] = icmp eq i32 %x, 0
143+
; ALL: [[CTTZ:%[A-Za-z0-9]+]] = tail call i32 @llvm.cttz.i32(i32 %x, i1 true)
144+
; ALL: [[ZEXT:%[A-Za-z0-9]+]] = zext i32 [[CTTZ]] to i64
145+
; BMI-NEXT: select i1 [[COND]], i64 32, i64 [[ZEXT]]
146+
; LZCNT-NOT: select
147+
; GENERIC-NOT: select
148+
; ALL: ret
149+
entry:
150+
%tobool = icmp eq i32 %x, 0
151+
br i1 %tobool, label %cond.end, label %cond.true
152+
153+
cond.true: ; preds = %entry
154+
%0 = tail call i32 @llvm.cttz.i32(i32 %x, i1 true)
155+
%phitmp2 = zext i32 %0 to i64
156+
br label %cond.end
157+
158+
cond.end: ; preds = %entry, %cond.true
159+
%cond = phi i64 [ %phitmp2, %cond.true ], [ 32, %entry ]
160+
ret i64 %cond
161+
}
162+
163+
define i32 @test2e(i64 %x) {
164+
; ALL-LABEL: @test2e(
165+
; ALL: [[COND:%[A-Za-z0-9]+]] = icmp eq i64 %x, 0
166+
; ALL: [[CTTZ:%[A-Za-z0-9]+]] = tail call i64 @llvm.cttz.i64(i64 %x, i1 true)
167+
; ALL: [[TRUNC:%[A-Za-z0-9]+]] = trunc i64 [[CTTZ]] to i32
168+
; BMI-NEXT: select i1 [[COND]], i32 64, i32 [[TRUNC]]
169+
; LZCNT-NOT: select
170+
; GENERIC-NOT: select
171+
; ALL: ret
172+
entry:
173+
%tobool = icmp eq i64 %x, 0
174+
br i1 %tobool, label %cond.end, label %cond.true
175+
176+
cond.true: ; preds = %entry
177+
%0 = tail call i64 @llvm.cttz.i64(i64 %x, i1 true)
178+
%cast = trunc i64 %0 to i32
179+
br label %cond.end
180+
181+
cond.end: ; preds = %entry, %cond.true
182+
%cond = phi i32 [ %cast, %cond.true ], [ 64, %entry ]
183+
ret i32 %cond
184+
}
185+
186+
define i64 @test3e(i32 %x) {
187+
; ALL-LABEL: @test3e(
188+
; ALL: [[COND:%[A-Za-z0-9]+]] = icmp eq i32 %x, 0
189+
; ALL: [[CTLZ:%[A-Za-z0-9]+]] = tail call i32 @llvm.ctlz.i32(i32 %x, i1 true)
190+
; ALL: [[ZEXT:%[A-Za-z0-9]+]] = zext i32 [[CTLZ]] to i64
191+
; LZCNT-NEXT: select i1 [[COND]], i64 32, i64 [[ZEXT]]
192+
; BMI-NOT: select
193+
; GENERIC-NOT: select
194+
; ALL: ret
195+
entry:
196+
%tobool = icmp eq i32 %x, 0
197+
br i1 %tobool, label %cond.end, label %cond.true
198+
199+
cond.true: ; preds = %entry
200+
%0 = tail call i32 @llvm.ctlz.i32(i32 %x, i1 true)
201+
%phitmp2 = zext i32 %0 to i64
202+
br label %cond.end
203+
204+
cond.end: ; preds = %entry, %cond.true
205+
%cond = phi i64 [ %phitmp2, %cond.true ], [ 32, %entry ]
206+
ret i64 %cond
207+
}
208+
209+
define i32 @test4e(i64 %x) {
210+
; ALL-LABEL: @test4e(
211+
; ALL: [[COND:%[A-Za-z0-9]+]] = icmp eq i64 %x, 0
212+
; ALL: [[CTLZ:%[A-Za-z0-9]+]] = tail call i64 @llvm.ctlz.i64(i64 %x, i1 true)
213+
; ALL: [[TRUNC:%[A-Za-z0-9]+]] = trunc i64 [[CTLZ]] to i32
214+
; LZCNT-NEXT: select i1 [[COND]], i32 64, i32 [[TRUNC]]
215+
; BMI-NOT: select
216+
; GENERIC-NOT: select
217+
; ALL: ret
218+
entry:
219+
%tobool = icmp eq i64 %x, 0
220+
br i1 %tobool, label %cond.end, label %cond.true
221+
222+
cond.true: ; preds = %entry
223+
%0 = tail call i64 @llvm.ctlz.i64(i64 %x, i1 true)
224+
%cast = trunc i64 %0 to i32
225+
br label %cond.end
226+
227+
cond.end: ; preds = %entry, %cond.true
228+
%cond = phi i32 [ %cast, %cond.true ], [ 64, %entry ]
229+
ret i32 %cond
230+
}
231+
232+
define i16 @test5e(i64 %x) {
233+
; ALL-LABEL: @test5e(
234+
; ALL: [[COND:%[A-Za-z0-9]+]] = icmp eq i64 %x, 0
235+
; ALL: [[CTLZ:%[A-Za-z0-9]+]] = tail call i64 @llvm.ctlz.i64(i64 %x, i1 true)
236+
; ALL: [[TRUNC:%[A-Za-z0-9]+]] = trunc i64 [[CTLZ]] to i16
237+
; LZCNT-NEXT: select i1 [[COND]], i16 64, i16 [[TRUNC]]
238+
; BMI-NOT: select
239+
; GENERIC-NOT: select
240+
; ALL: ret
241+
entry:
242+
%tobool = icmp eq i64 %x, 0
243+
br i1 %tobool, label %cond.end, label %cond.true
244+
245+
cond.true: ; preds = %entry
246+
%0 = tail call i64 @llvm.ctlz.i64(i64 %x, i1 true)
247+
%cast = trunc i64 %0 to i16
248+
br label %cond.end
249+
250+
cond.end: ; preds = %entry, %cond.true
251+
%cond = phi i16 [ %cast, %cond.true ], [ 64, %entry ]
252+
ret i16 %cond
253+
}
254+
255+
define i16 @test6e(i32 %x) {
256+
; ALL-LABEL: @test6e(
257+
; ALL: [[COND:%[A-Za-z0-9]+]] = icmp eq i32 %x, 0
258+
; ALL: [[CTLZ:%[A-Za-z0-9]+]] = tail call i32 @llvm.ctlz.i32(i32 %x, i1 true)
259+
; ALL: [[TRUNC:%[A-Za-z0-9]+]] = trunc i32 [[CTLZ]] to i16
260+
; LZCNT-NEXT: select i1 [[COND]], i16 32, i16 [[TRUNC]]
261+
; BMI-NOT: select
262+
; GENERIC-NOT: select
263+
; ALL: ret
264+
entry:
265+
%tobool = icmp eq i32 %x, 0
266+
br i1 %tobool, label %cond.end, label %cond.true
267+
268+
cond.true: ; preds = %entry
269+
%0 = tail call i32 @llvm.ctlz.i32(i32 %x, i1 true)
270+
%cast = trunc i32 %0 to i16
271+
br label %cond.end
272+
273+
cond.end: ; preds = %entry, %cond.true
274+
%cond = phi i16 [ %cast, %cond.true ], [ 32, %entry ]
275+
ret i16 %cond
276+
}
277+
278+
define i16 @test7e(i64 %x) {
279+
; ALL-LABEL: @test7e(
280+
; ALL: [[COND:%[A-Za-z0-9]+]] = icmp eq i64 %x, 0
281+
; ALL: [[CTTZ:%[A-Za-z0-9]+]] = tail call i64 @llvm.cttz.i64(i64 %x, i1 true)
282+
; ALL: [[TRUNC:%[A-Za-z0-9]+]] = trunc i64 [[CTTZ]] to i16
283+
; BMI-NEXT: select i1 [[COND]], i16 64, i16 [[TRUNC]]
284+
; LZCNT-NOT: select
285+
; GENERIC-NOT: select
286+
; ALL: ret
287+
entry:
288+
%tobool = icmp eq i64 %x, 0
289+
br i1 %tobool, label %cond.end, label %cond.true
290+
291+
cond.true: ; preds = %entry
292+
%0 = tail call i64 @llvm.cttz.i64(i64 %x, i1 true)
293+
%cast = trunc i64 %0 to i16
294+
br label %cond.end
295+
296+
cond.end: ; preds = %entry, %cond.true
297+
%cond = phi i16 [ %cast, %cond.true ], [ 64, %entry ]
298+
ret i16 %cond
299+
}
300+
301+
define i16 @test8e(i32 %x) {
302+
; ALL-LABEL: @test8e(
303+
; ALL: [[COND:%[A-Za-z0-9]+]] = icmp eq i32 %x, 0
304+
; ALL: [[CTTZ:%[A-Za-z0-9]+]] = tail call i32 @llvm.cttz.i32(i32 %x, i1 true)
305+
; ALL: [[TRUNC:%[A-Za-z0-9]+]] = trunc i32 [[CTTZ]] to i16
306+
; BMI-NEXT: select i1 [[COND]], i16 32, i16 [[TRUNC]]
307+
; LZCNT-NOT: select
308+
; GENERIC-NOT: select
309+
; ALL: ret
310+
entry:
311+
%tobool = icmp eq i32 %x, 0
312+
br i1 %tobool, label %cond.end, label %cond.true
313+
314+
cond.true: ; preds = %entry
315+
%0 = tail call i32 @llvm.cttz.i32(i32 %x, i1 true)
316+
%cast = trunc i32 %0 to i16
317+
br label %cond.end
318+
319+
cond.end: ; preds = %entry, %cond.true
320+
%cond = phi i16 [ %cast, %cond.true ], [ 32, %entry ]
321+
ret i16 %cond
322+
}
323+
324+
136325
declare i64 @llvm.ctlz.i64(i64, i1)
137326
declare i32 @llvm.ctlz.i32(i32, i1)
138327
declare i16 @llvm.ctlz.i16(i16, i1)

0 commit comments

Comments
 (0)
Please sign in to comment.