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:
55   LibCallsShrinkWrap(const TargetLibraryInfo &TLI, DomTreeUpdater &DTU)
56       : TLI(TLI), DTU(DTU){};
57   void visitCallInst(CallInst &CI) { checkCandidate(CI); }
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.
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.
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.
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 = ConstantExpr::getFPExtend(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.
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.
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.
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.
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.
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.
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.
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.
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 //
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.
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()).createBranchWeights(1, 2000);
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.
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 
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 
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