1 //===-- LibCallsShrinkWrap.cpp ----------------------------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This pass shrink-wraps a call to function if the result is not used.
10 // The call can set errno but is otherwise side effect free. For example:
11 // sqrt(val);
12 // is transformed to
13 // if (val < 0)
14 // sqrt(val);
15 // Even if the result of library call is not being used, the compiler cannot
16 // safely delete the call because the function can set errno on error
17 // conditions.
18 // Note in many functions, the error condition solely depends on the incoming
19 // parameter. In this optimization, we can generate the condition can lead to
20 // the errno to shrink-wrap the call. Since the chances of hitting the error
21 // condition is low, the runtime call is effectively eliminated.
22 //
23 // These partially dead calls are usually results of C++ abstraction penalty
24 // exposed by inlining.
25 //
26 //===----------------------------------------------------------------------===//
27
28 #include "llvm/Transforms/Utils/LibCallsShrinkWrap.h"
29 #include "llvm/ADT/SmallVector.h"
30 #include "llvm/ADT/Statistic.h"
31 #include "llvm/Analysis/DomTreeUpdater.h"
32 #include "llvm/Analysis/GlobalsModRef.h"
33 #include "llvm/Analysis/TargetLibraryInfo.h"
34 #include "llvm/IR/Constants.h"
35 #include "llvm/IR/Dominators.h"
36 #include "llvm/IR/Function.h"
37 #include "llvm/IR/IRBuilder.h"
38 #include "llvm/IR/InstVisitor.h"
39 #include "llvm/IR/Instructions.h"
40 #include "llvm/IR/MDBuilder.h"
41 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
42
43 #include <cmath>
44
45 using namespace llvm;
46
47 #define DEBUG_TYPE "libcalls-shrinkwrap"
48
49 STATISTIC(NumWrappedOneCond, "Number of One-Condition Wrappers Inserted");
50 STATISTIC(NumWrappedTwoCond, "Number of Two-Condition Wrappers Inserted");
51
52 namespace {
53 class LibCallsShrinkWrap : public InstVisitor<LibCallsShrinkWrap> {
54 public:
LibCallsShrinkWrap(const TargetLibraryInfo & TLI,DomTreeUpdater & DTU)55 LibCallsShrinkWrap(const TargetLibraryInfo &TLI, DomTreeUpdater &DTU)
56 : TLI(TLI), DTU(DTU){};
visitCallInst(CallInst & CI)57 void visitCallInst(CallInst &CI) { checkCandidate(CI); }
perform()58 bool perform() {
59 bool Changed = false;
60 for (auto &CI : WorkList) {
61 LLVM_DEBUG(dbgs() << "CDCE calls: " << CI->getCalledFunction()->getName()
62 << "\n");
63 if (perform(CI)) {
64 Changed = true;
65 LLVM_DEBUG(dbgs() << "Transformed\n");
66 }
67 }
68 return Changed;
69 }
70
71 private:
72 bool perform(CallInst *CI);
73 void checkCandidate(CallInst &CI);
74 void shrinkWrapCI(CallInst *CI, Value *Cond);
75 bool performCallDomainErrorOnly(CallInst *CI, const LibFunc &Func);
76 bool performCallErrors(CallInst *CI, const LibFunc &Func);
77 bool performCallRangeErrorOnly(CallInst *CI, const LibFunc &Func);
78 Value *generateOneRangeCond(CallInst *CI, const LibFunc &Func);
79 Value *generateTwoRangeCond(CallInst *CI, const LibFunc &Func);
80 Value *generateCondForPow(CallInst *CI, const LibFunc &Func);
81
82 // Create an OR of two conditions with given Arg and Arg2.
createOrCond(CallInst * CI,Value * Arg,CmpInst::Predicate Cmp,float Val,Value * Arg2,CmpInst::Predicate Cmp2,float Val2)83 Value *createOrCond(CallInst *CI, Value *Arg, CmpInst::Predicate Cmp,
84 float Val, Value *Arg2, CmpInst::Predicate Cmp2,
85 float Val2) {
86 IRBuilder<> BBBuilder(CI);
87 auto Cond2 = createCond(BBBuilder, Arg2, Cmp2, Val2);
88 auto Cond1 = createCond(BBBuilder, Arg, Cmp, Val);
89 return BBBuilder.CreateOr(Cond1, Cond2);
90 }
91
92 // Create an OR of two conditions.
createOrCond(CallInst * CI,CmpInst::Predicate Cmp,float Val,CmpInst::Predicate Cmp2,float Val2)93 Value *createOrCond(CallInst *CI, CmpInst::Predicate Cmp, float Val,
94 CmpInst::Predicate Cmp2, float Val2) {
95 Value *Arg = CI->getArgOperand(0);
96 return createOrCond(CI, Arg, Cmp, Val, Arg, Cmp2, Val2);
97 }
98
99 // Create a single condition using IRBuilder.
createCond(IRBuilder<> & BBBuilder,Value * Arg,CmpInst::Predicate Cmp,float Val)100 Value *createCond(IRBuilder<> &BBBuilder, Value *Arg, CmpInst::Predicate Cmp,
101 float Val) {
102 Constant *V = ConstantFP::get(BBBuilder.getContext(), APFloat(Val));
103 if (!Arg->getType()->isFloatTy())
104 V = ConstantFoldCastInstruction(Instruction::FPExt, V, Arg->getType());
105 if (BBBuilder.GetInsertBlock()->getParent()->hasFnAttribute(Attribute::StrictFP))
106 BBBuilder.setIsFPConstrained(true);
107 return BBBuilder.CreateFCmp(Cmp, Arg, V);
108 }
109
110 // Create a single condition with given Arg.
createCond(CallInst * CI,Value * Arg,CmpInst::Predicate Cmp,float Val)111 Value *createCond(CallInst *CI, Value *Arg, CmpInst::Predicate Cmp,
112 float Val) {
113 IRBuilder<> BBBuilder(CI);
114 return createCond(BBBuilder, Arg, Cmp, Val);
115 }
116
117 // Create a single condition.
createCond(CallInst * CI,CmpInst::Predicate Cmp,float Val)118 Value *createCond(CallInst *CI, CmpInst::Predicate Cmp, float Val) {
119 Value *Arg = CI->getArgOperand(0);
120 return createCond(CI, Arg, Cmp, Val);
121 }
122
123 const TargetLibraryInfo &TLI;
124 DomTreeUpdater &DTU;
125 SmallVector<CallInst *, 16> WorkList;
126 };
127 } // end anonymous namespace
128
129 // Perform the transformation to calls with errno set by domain error.
performCallDomainErrorOnly(CallInst * CI,const LibFunc & Func)130 bool LibCallsShrinkWrap::performCallDomainErrorOnly(CallInst *CI,
131 const LibFunc &Func) {
132 Value *Cond = nullptr;
133
134 switch (Func) {
135 case LibFunc_acos: // DomainError: (x < -1 || x > 1)
136 case LibFunc_acosf: // Same as acos
137 case LibFunc_acosl: // Same as acos
138 case LibFunc_asin: // DomainError: (x < -1 || x > 1)
139 case LibFunc_asinf: // Same as asin
140 case LibFunc_asinl: // Same as asin
141 {
142 ++NumWrappedTwoCond;
143 Cond = createOrCond(CI, CmpInst::FCMP_OLT, -1.0f, CmpInst::FCMP_OGT, 1.0f);
144 break;
145 }
146 case LibFunc_cos: // DomainError: (x == +inf || x == -inf)
147 case LibFunc_cosf: // Same as cos
148 case LibFunc_cosl: // Same as cos
149 case LibFunc_sin: // DomainError: (x == +inf || x == -inf)
150 case LibFunc_sinf: // Same as sin
151 case LibFunc_sinl: // Same as sin
152 {
153 ++NumWrappedTwoCond;
154 Cond = createOrCond(CI, CmpInst::FCMP_OEQ, INFINITY, CmpInst::FCMP_OEQ,
155 -INFINITY);
156 break;
157 }
158 case LibFunc_acosh: // DomainError: (x < 1)
159 case LibFunc_acoshf: // Same as acosh
160 case LibFunc_acoshl: // Same as acosh
161 {
162 ++NumWrappedOneCond;
163 Cond = createCond(CI, CmpInst::FCMP_OLT, 1.0f);
164 break;
165 }
166 case LibFunc_sqrt: // DomainError: (x < 0)
167 case LibFunc_sqrtf: // Same as sqrt
168 case LibFunc_sqrtl: // Same as sqrt
169 {
170 ++NumWrappedOneCond;
171 Cond = createCond(CI, CmpInst::FCMP_OLT, 0.0f);
172 break;
173 }
174 default:
175 return false;
176 }
177 shrinkWrapCI(CI, Cond);
178 return true;
179 }
180
181 // Perform the transformation to calls with errno set by range error.
performCallRangeErrorOnly(CallInst * CI,const LibFunc & Func)182 bool LibCallsShrinkWrap::performCallRangeErrorOnly(CallInst *CI,
183 const LibFunc &Func) {
184 Value *Cond = nullptr;
185
186 switch (Func) {
187 case LibFunc_cosh:
188 case LibFunc_coshf:
189 case LibFunc_coshl:
190 case LibFunc_exp:
191 case LibFunc_expf:
192 case LibFunc_expl:
193 case LibFunc_exp10:
194 case LibFunc_exp10f:
195 case LibFunc_exp10l:
196 case LibFunc_exp2:
197 case LibFunc_exp2f:
198 case LibFunc_exp2l:
199 case LibFunc_sinh:
200 case LibFunc_sinhf:
201 case LibFunc_sinhl: {
202 Cond = generateTwoRangeCond(CI, Func);
203 break;
204 }
205 case LibFunc_expm1: // RangeError: (709, inf)
206 case LibFunc_expm1f: // RangeError: (88, inf)
207 case LibFunc_expm1l: // RangeError: (11356, inf)
208 {
209 Cond = generateOneRangeCond(CI, Func);
210 break;
211 }
212 default:
213 return false;
214 }
215 shrinkWrapCI(CI, Cond);
216 return true;
217 }
218
219 // Perform the transformation to calls with errno set by combination of errors.
performCallErrors(CallInst * CI,const LibFunc & Func)220 bool LibCallsShrinkWrap::performCallErrors(CallInst *CI,
221 const LibFunc &Func) {
222 Value *Cond = nullptr;
223
224 switch (Func) {
225 case LibFunc_atanh: // DomainError: (x < -1 || x > 1)
226 // PoleError: (x == -1 || x == 1)
227 // Overall Cond: (x <= -1 || x >= 1)
228 case LibFunc_atanhf: // Same as atanh
229 case LibFunc_atanhl: // Same as atanh
230 {
231 ++NumWrappedTwoCond;
232 Cond = createOrCond(CI, CmpInst::FCMP_OLE, -1.0f, CmpInst::FCMP_OGE, 1.0f);
233 break;
234 }
235 case LibFunc_log: // DomainError: (x < 0)
236 // PoleError: (x == 0)
237 // Overall Cond: (x <= 0)
238 case LibFunc_logf: // Same as log
239 case LibFunc_logl: // Same as log
240 case LibFunc_log10: // Same as log
241 case LibFunc_log10f: // Same as log
242 case LibFunc_log10l: // Same as log
243 case LibFunc_log2: // Same as log
244 case LibFunc_log2f: // Same as log
245 case LibFunc_log2l: // Same as log
246 case LibFunc_logb: // Same as log
247 case LibFunc_logbf: // Same as log
248 case LibFunc_logbl: // Same as log
249 {
250 ++NumWrappedOneCond;
251 Cond = createCond(CI, CmpInst::FCMP_OLE, 0.0f);
252 break;
253 }
254 case LibFunc_log1p: // DomainError: (x < -1)
255 // PoleError: (x == -1)
256 // Overall Cond: (x <= -1)
257 case LibFunc_log1pf: // Same as log1p
258 case LibFunc_log1pl: // Same as log1p
259 {
260 ++NumWrappedOneCond;
261 Cond = createCond(CI, CmpInst::FCMP_OLE, -1.0f);
262 break;
263 }
264 case LibFunc_pow: // DomainError: x < 0 and y is noninteger
265 // PoleError: x == 0 and y < 0
266 // RangeError: overflow or underflow
267 case LibFunc_powf:
268 case LibFunc_powl: {
269 Cond = generateCondForPow(CI, Func);
270 if (Cond == nullptr)
271 return false;
272 break;
273 }
274 default:
275 return false;
276 }
277 assert(Cond && "performCallErrors should not see an empty condition");
278 shrinkWrapCI(CI, Cond);
279 return true;
280 }
281
282 // Checks if CI is a candidate for shrinkwrapping and put it into work list if
283 // true.
checkCandidate(CallInst & CI)284 void LibCallsShrinkWrap::checkCandidate(CallInst &CI) {
285 if (CI.isNoBuiltin())
286 return;
287 // A possible improvement is to handle the calls with the return value being
288 // used. If there is API for fast libcall implementation without setting
289 // errno, we can use the same framework to direct/wrap the call to the fast
290 // API in the error free path, and leave the original call in the slow path.
291 if (!CI.use_empty())
292 return;
293
294 LibFunc Func;
295 Function *Callee = CI.getCalledFunction();
296 if (!Callee)
297 return;
298 if (!TLI.getLibFunc(*Callee, Func) || !TLI.has(Func))
299 return;
300
301 if (CI.arg_empty())
302 return;
303 // TODO: Handle long double in other formats.
304 Type *ArgType = CI.getArgOperand(0)->getType();
305 if (!(ArgType->isFloatTy() || ArgType->isDoubleTy() ||
306 ArgType->isX86_FP80Ty()))
307 return;
308
309 WorkList.push_back(&CI);
310 }
311
312 // Generate the upper bound condition for RangeError.
generateOneRangeCond(CallInst * CI,const LibFunc & Func)313 Value *LibCallsShrinkWrap::generateOneRangeCond(CallInst *CI,
314 const LibFunc &Func) {
315 float UpperBound;
316 switch (Func) {
317 case LibFunc_expm1: // RangeError: (709, inf)
318 UpperBound = 709.0f;
319 break;
320 case LibFunc_expm1f: // RangeError: (88, inf)
321 UpperBound = 88.0f;
322 break;
323 case LibFunc_expm1l: // RangeError: (11356, inf)
324 UpperBound = 11356.0f;
325 break;
326 default:
327 llvm_unreachable("Unhandled library call!");
328 }
329
330 ++NumWrappedOneCond;
331 return createCond(CI, CmpInst::FCMP_OGT, UpperBound);
332 }
333
334 // Generate the lower and upper bound condition for RangeError.
generateTwoRangeCond(CallInst * CI,const LibFunc & Func)335 Value *LibCallsShrinkWrap::generateTwoRangeCond(CallInst *CI,
336 const LibFunc &Func) {
337 float UpperBound, LowerBound;
338 switch (Func) {
339 case LibFunc_cosh: // RangeError: (x < -710 || x > 710)
340 case LibFunc_sinh: // Same as cosh
341 LowerBound = -710.0f;
342 UpperBound = 710.0f;
343 break;
344 case LibFunc_coshf: // RangeError: (x < -89 || x > 89)
345 case LibFunc_sinhf: // Same as coshf
346 LowerBound = -89.0f;
347 UpperBound = 89.0f;
348 break;
349 case LibFunc_coshl: // RangeError: (x < -11357 || x > 11357)
350 case LibFunc_sinhl: // Same as coshl
351 LowerBound = -11357.0f;
352 UpperBound = 11357.0f;
353 break;
354 case LibFunc_exp: // RangeError: (x < -745 || x > 709)
355 LowerBound = -745.0f;
356 UpperBound = 709.0f;
357 break;
358 case LibFunc_expf: // RangeError: (x < -103 || x > 88)
359 LowerBound = -103.0f;
360 UpperBound = 88.0f;
361 break;
362 case LibFunc_expl: // RangeError: (x < -11399 || x > 11356)
363 LowerBound = -11399.0f;
364 UpperBound = 11356.0f;
365 break;
366 case LibFunc_exp10: // RangeError: (x < -323 || x > 308)
367 LowerBound = -323.0f;
368 UpperBound = 308.0f;
369 break;
370 case LibFunc_exp10f: // RangeError: (x < -45 || x > 38)
371 LowerBound = -45.0f;
372 UpperBound = 38.0f;
373 break;
374 case LibFunc_exp10l: // RangeError: (x < -4950 || x > 4932)
375 LowerBound = -4950.0f;
376 UpperBound = 4932.0f;
377 break;
378 case LibFunc_exp2: // RangeError: (x < -1074 || x > 1023)
379 LowerBound = -1074.0f;
380 UpperBound = 1023.0f;
381 break;
382 case LibFunc_exp2f: // RangeError: (x < -149 || x > 127)
383 LowerBound = -149.0f;
384 UpperBound = 127.0f;
385 break;
386 case LibFunc_exp2l: // RangeError: (x < -16445 || x > 11383)
387 LowerBound = -16445.0f;
388 UpperBound = 11383.0f;
389 break;
390 default:
391 llvm_unreachable("Unhandled library call!");
392 }
393
394 ++NumWrappedTwoCond;
395 return createOrCond(CI, CmpInst::FCMP_OGT, UpperBound, CmpInst::FCMP_OLT,
396 LowerBound);
397 }
398
399 // For pow(x,y), We only handle the following cases:
400 // (1) x is a constant && (x >= 1) && (x < MaxUInt8)
401 // Cond is: (y > 127)
402 // (2) x is a value coming from an integer type.
403 // (2.1) if x's bit_size == 8
404 // Cond: (x <= 0 || y > 128)
405 // (2.2) if x's bit_size is 16
406 // Cond: (x <= 0 || y > 64)
407 // (2.3) if x's bit_size is 32
408 // Cond: (x <= 0 || y > 32)
409 // Support for powl(x,y) and powf(x,y) are TBD.
410 //
411 // Note that condition can be more conservative than the actual condition
412 // (i.e. we might invoke the calls that will not set the errno.).
413 //
generateCondForPow(CallInst * CI,const LibFunc & Func)414 Value *LibCallsShrinkWrap::generateCondForPow(CallInst *CI,
415 const LibFunc &Func) {
416 // FIXME: LibFunc_powf and powl TBD.
417 if (Func != LibFunc_pow) {
418 LLVM_DEBUG(dbgs() << "Not handled powf() and powl()\n");
419 return nullptr;
420 }
421
422 Value *Base = CI->getArgOperand(0);
423 Value *Exp = CI->getArgOperand(1);
424
425 // Constant Base case.
426 if (ConstantFP *CF = dyn_cast<ConstantFP>(Base)) {
427 double D = CF->getValueAPF().convertToDouble();
428 if (D < 1.0f || D > APInt::getMaxValue(8).getZExtValue()) {
429 LLVM_DEBUG(dbgs() << "Not handled pow(): constant base out of range\n");
430 return nullptr;
431 }
432
433 ++NumWrappedOneCond;
434 return createCond(CI, Exp, CmpInst::FCMP_OGT, 127.0f);
435 }
436
437 // If the Base value coming from an integer type.
438 Instruction *I = dyn_cast<Instruction>(Base);
439 if (!I) {
440 LLVM_DEBUG(dbgs() << "Not handled pow(): FP type base\n");
441 return nullptr;
442 }
443 unsigned Opcode = I->getOpcode();
444 if (Opcode == Instruction::UIToFP || Opcode == Instruction::SIToFP) {
445 unsigned BW = I->getOperand(0)->getType()->getPrimitiveSizeInBits();
446 float UpperV = 0.0f;
447 if (BW == 8)
448 UpperV = 128.0f;
449 else if (BW == 16)
450 UpperV = 64.0f;
451 else if (BW == 32)
452 UpperV = 32.0f;
453 else {
454 LLVM_DEBUG(dbgs() << "Not handled pow(): type too wide\n");
455 return nullptr;
456 }
457
458 ++NumWrappedTwoCond;
459 return createOrCond(CI, Base, CmpInst::FCMP_OLE, 0.0f, Exp,
460 CmpInst::FCMP_OGT, UpperV);
461 }
462 LLVM_DEBUG(dbgs() << "Not handled pow(): base not from integer convert\n");
463 return nullptr;
464 }
465
466 // Wrap conditions that can potentially generate errno to the library call.
shrinkWrapCI(CallInst * CI,Value * Cond)467 void LibCallsShrinkWrap::shrinkWrapCI(CallInst *CI, Value *Cond) {
468 assert(Cond != nullptr && "ShrinkWrapCI is not expecting an empty call inst");
469 MDNode *BranchWeights =
470 MDBuilder(CI->getContext()).createUnlikelyBranchWeights();
471
472 Instruction *NewInst =
473 SplitBlockAndInsertIfThen(Cond, CI, false, BranchWeights, &DTU);
474 BasicBlock *CallBB = NewInst->getParent();
475 CallBB->setName("cdce.call");
476 BasicBlock *SuccBB = CallBB->getSingleSuccessor();
477 assert(SuccBB && "The split block should have a single successor");
478 SuccBB->setName("cdce.end");
479 CI->removeFromParent();
480 CI->insertInto(CallBB, CallBB->getFirstInsertionPt());
481 LLVM_DEBUG(dbgs() << "== Basic Block After ==");
482 LLVM_DEBUG(dbgs() << *CallBB->getSinglePredecessor() << *CallBB
483 << *CallBB->getSingleSuccessor() << "\n");
484 }
485
486 // Perform the transformation to a single candidate.
perform(CallInst * CI)487 bool LibCallsShrinkWrap::perform(CallInst *CI) {
488 LibFunc Func;
489 Function *Callee = CI->getCalledFunction();
490 assert(Callee && "perform() should apply to a non-empty callee");
491 TLI.getLibFunc(*Callee, Func);
492 assert(Func && "perform() is not expecting an empty function");
493
494 if (performCallDomainErrorOnly(CI, Func) || performCallRangeErrorOnly(CI, Func))
495 return true;
496 return performCallErrors(CI, Func);
497 }
498
runImpl(Function & F,const TargetLibraryInfo & TLI,DominatorTree * DT)499 static bool runImpl(Function &F, const TargetLibraryInfo &TLI,
500 DominatorTree *DT) {
501 if (F.hasFnAttribute(Attribute::OptimizeForSize))
502 return false;
503 DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Lazy);
504 LibCallsShrinkWrap CCDCE(TLI, DTU);
505 CCDCE.visit(F);
506 bool Changed = CCDCE.perform();
507
508 // Verify the dominator after we've updated it locally.
509 assert(!DT ||
510 DTU.getDomTree().verify(DominatorTree::VerificationLevel::Fast));
511 return Changed;
512 }
513
run(Function & F,FunctionAnalysisManager & FAM)514 PreservedAnalyses LibCallsShrinkWrapPass::run(Function &F,
515 FunctionAnalysisManager &FAM) {
516 auto &TLI = FAM.getResult<TargetLibraryAnalysis>(F);
517 auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(F);
518 if (!runImpl(F, TLI, DT))
519 return PreservedAnalyses::all();
520 auto PA = PreservedAnalyses();
521 PA.preserve<DominatorTreeAnalysis>();
522 return PA;
523 }
524