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