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
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 LibCallsShrinkWrap : public InstVisitor<LibCallsShrinkWrap> {
54public:
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
71private:
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, Arg: Arg2, Cmp: Cmp2, Val: Val2);
88 auto Cond1 = createCond(BBBuilder, Arg, Cmp, Val);
89 return BBBuilder.CreateOr(LHS: Cond1, RHS: 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(i: 0);
96 return createOrCond(CI, Arg, Cmp, Val, Arg2: 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(Context&: BBBuilder.getContext(), V: APFloat(Val));
103 if (!Arg->getType()->isFloatTy())
104 V = ConstantFoldCastInstruction(opcode: Instruction::FPExt, V, DestTy: Arg->getType());
105 if (BBBuilder.GetInsertBlock()->getParent()->hasFnAttribute(Kind: Attribute::StrictFP))
106 BBBuilder.setIsFPConstrained(true);
107 return BBBuilder.CreateFCmp(P: Cmp, LHS: Arg, RHS: 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(i: 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.
130bool 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, Cmp: CmpInst::FCMP_OLT, Val: -1.0f, Cmp2: CmpInst::FCMP_OGT, Val2: 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, Cmp: CmpInst::FCMP_OEQ, INFINITY, Cmp2: CmpInst::FCMP_OEQ,
155 Val2: -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, Cmp: CmpInst::FCMP_OLT, Val: 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, Cmp: CmpInst::FCMP_OLT, Val: 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.
182bool 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.
220bool 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, Cmp: CmpInst::FCMP_OLE, Val: -1.0f, Cmp2: CmpInst::FCMP_OGE, Val2: 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, Cmp: CmpInst::FCMP_OLE, Val: 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, Cmp: CmpInst::FCMP_OLE, Val: -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.
284void 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(FDecl: *Callee, F&: Func) || !TLI.has(F: Func))
299 return;
300
301 if (CI.arg_empty())
302 return;
303 // TODO: Handle long double in other formats.
304 Type *ArgType = CI.getArgOperand(i: 0)->getType();
305 if (!(ArgType->isFloatTy() || ArgType->isDoubleTy() ||
306 ArgType->isX86_FP80Ty()))
307 return;
308
309 WorkList.push_back(Elt: &CI);
310}
311
312// Generate the upper bound condition for RangeError.
313Value *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, Cmp: CmpInst::FCMP_OGT, Val: UpperBound);
332}
333
334// Generate the lower and upper bound condition for RangeError.
335Value *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, Cmp: CmpInst::FCMP_OGT, Val: UpperBound, Cmp2: CmpInst::FCMP_OLT,
396 Val2: 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//
414Value *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(i: 0);
423 Value *Exp = CI->getArgOperand(i: 1);
424
425 // Constant Base case.
426 if (ConstantFP *CF = dyn_cast<ConstantFP>(Val: Base)) {
427 double D = CF->getValueAPF().convertToDouble();
428 if (D < 1.0f || D > APInt::getMaxValue(numBits: 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, Arg: Exp, Cmp: CmpInst::FCMP_OGT, Val: 127.0f);
435 }
436
437 // If the Base value coming from an integer type.
438 Instruction *I = dyn_cast<Instruction>(Val: 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(i: 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, Arg: Base, Cmp: CmpInst::FCMP_OLE, Val: 0.0f, Arg2: Exp,
460 Cmp2: CmpInst::FCMP_OGT, Val2: 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.
467void 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, SplitBefore: CI, Unreachable: false, BranchWeights, DTU: &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(ParentBB: CallBB, It: 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.
487bool 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(FDecl: *Callee, F&: 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
499static bool runImpl(Function &F, const TargetLibraryInfo &TLI,
500 DominatorTree *DT) {
501 if (F.hasFnAttribute(Kind: 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
514PreservedAnalyses LibCallsShrinkWrapPass::run(Function &F,
515 FunctionAnalysisManager &FAM) {
516 auto &TLI = FAM.getResult<TargetLibraryAnalysis>(IR&: F);
517 auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(IR&: F);
518 if (!runImpl(F, TLI, DT))
519 return PreservedAnalyses::all();
520 auto PA = PreservedAnalyses();
521 PA.preserve<DominatorTreeAnalysis>();
522 return PA;
523}
524