1 //===- InlineCost.cpp - Cost analysis for inliner -------------------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file implements inline cost analysis. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "llvm/Analysis/InlineCost.h" 15 #include "llvm/ADT/STLExtras.h" 16 #include "llvm/ADT/SetVector.h" 17 #include "llvm/ADT/SmallPtrSet.h" 18 #include "llvm/ADT/SmallVector.h" 19 #include "llvm/ADT/Statistic.h" 20 #include "llvm/Analysis/AssumptionCache.h" 21 #include "llvm/Analysis/CodeMetrics.h" 22 #include "llvm/Analysis/ConstantFolding.h" 23 #include "llvm/Analysis/InstructionSimplify.h" 24 #include "llvm/Analysis/TargetTransformInfo.h" 25 #include "llvm/IR/CallSite.h" 26 #include "llvm/IR/CallingConv.h" 27 #include "llvm/IR/DataLayout.h" 28 #include "llvm/IR/GetElementPtrTypeIterator.h" 29 #include "llvm/IR/GlobalAlias.h" 30 #include "llvm/IR/InstVisitor.h" 31 #include "llvm/IR/IntrinsicInst.h" 32 #include "llvm/IR/Operator.h" 33 #include "llvm/Support/Debug.h" 34 #include "llvm/Support/raw_ostream.h" 35 36 using namespace llvm; 37 38 #define DEBUG_TYPE "inline-cost" 39 40 STATISTIC(NumCallsAnalyzed, "Number of call sites analyzed"); 41 42 namespace { 43 44 class CallAnalyzer : public InstVisitor<CallAnalyzer, bool> { 45 typedef InstVisitor<CallAnalyzer, bool> Base; 46 friend class InstVisitor<CallAnalyzer, bool>; 47 48 /// The TargetTransformInfo available for this compilation. 49 const TargetTransformInfo &TTI; 50 51 /// The cache of @llvm.assume intrinsics. 52 AssumptionCacheTracker *ACT; 53 54 // The called function. 55 Function &F; 56 57 int Threshold; 58 int Cost; 59 60 bool IsCallerRecursive; 61 bool IsRecursiveCall; 62 bool ExposesReturnsTwice; 63 bool HasDynamicAlloca; 64 bool ContainsNoDuplicateCall; 65 bool HasReturn; 66 bool HasIndirectBr; 67 bool HasFrameEscape; 68 69 /// Number of bytes allocated statically by the callee. 70 uint64_t AllocatedSize; 71 unsigned NumInstructions, NumVectorInstructions; 72 int FiftyPercentVectorBonus, TenPercentVectorBonus; 73 int VectorBonus; 74 75 // While we walk the potentially-inlined instructions, we build up and 76 // maintain a mapping of simplified values specific to this callsite. The 77 // idea is to propagate any special information we have about arguments to 78 // this call through the inlinable section of the function, and account for 79 // likely simplifications post-inlining. The most important aspect we track 80 // is CFG altering simplifications -- when we prove a basic block dead, that 81 // can cause dramatic shifts in the cost of inlining a function. 82 DenseMap<Value *, Constant *> SimplifiedValues; 83 84 // Keep track of the values which map back (through function arguments) to 85 // allocas on the caller stack which could be simplified through SROA. 86 DenseMap<Value *, Value *> SROAArgValues; 87 88 // The mapping of caller Alloca values to their accumulated cost savings. If 89 // we have to disable SROA for one of the allocas, this tells us how much 90 // cost must be added. 91 DenseMap<Value *, int> SROAArgCosts; 92 93 // Keep track of values which map to a pointer base and constant offset. 94 DenseMap<Value *, std::pair<Value *, APInt> > ConstantOffsetPtrs; 95 96 // Custom simplification helper routines. 97 bool isAllocaDerivedArg(Value *V); 98 bool lookupSROAArgAndCost(Value *V, Value *&Arg, 99 DenseMap<Value *, int>::iterator &CostIt); 100 void disableSROA(DenseMap<Value *, int>::iterator CostIt); 101 void disableSROA(Value *V); 102 void accumulateSROACost(DenseMap<Value *, int>::iterator CostIt, 103 int InstructionCost); 104 bool isGEPOffsetConstant(GetElementPtrInst &GEP); 105 bool accumulateGEPOffset(GEPOperator &GEP, APInt &Offset); 106 bool simplifyCallSite(Function *F, CallSite CS); 107 ConstantInt *stripAndComputeInBoundsConstantOffsets(Value *&V); 108 109 // Custom analysis routines. 110 bool analyzeBlock(BasicBlock *BB, SmallPtrSetImpl<const Value *> &EphValues); 111 112 // Disable several entry points to the visitor so we don't accidentally use 113 // them by declaring but not defining them here. 114 void visit(Module *); void visit(Module &); 115 void visit(Function *); void visit(Function &); 116 void visit(BasicBlock *); void visit(BasicBlock &); 117 118 // Provide base case for our instruction visit. 119 bool visitInstruction(Instruction &I); 120 121 // Our visit overrides. 122 bool visitAlloca(AllocaInst &I); 123 bool visitPHI(PHINode &I); 124 bool visitGetElementPtr(GetElementPtrInst &I); 125 bool visitBitCast(BitCastInst &I); 126 bool visitPtrToInt(PtrToIntInst &I); 127 bool visitIntToPtr(IntToPtrInst &I); 128 bool visitCastInst(CastInst &I); 129 bool visitUnaryInstruction(UnaryInstruction &I); 130 bool visitCmpInst(CmpInst &I); 131 bool visitSub(BinaryOperator &I); 132 bool visitBinaryOperator(BinaryOperator &I); 133 bool visitLoad(LoadInst &I); 134 bool visitStore(StoreInst &I); 135 bool visitExtractValue(ExtractValueInst &I); 136 bool visitInsertValue(InsertValueInst &I); 137 bool visitCallSite(CallSite CS); 138 bool visitReturnInst(ReturnInst &RI); 139 bool visitBranchInst(BranchInst &BI); 140 bool visitSwitchInst(SwitchInst &SI); 141 bool visitIndirectBrInst(IndirectBrInst &IBI); 142 bool visitResumeInst(ResumeInst &RI); 143 bool visitUnreachableInst(UnreachableInst &I); 144 145 public: 146 CallAnalyzer(const TargetTransformInfo &TTI, AssumptionCacheTracker *ACT, 147 Function &Callee, int Threshold) 148 : TTI(TTI), ACT(ACT), F(Callee), Threshold(Threshold), Cost(0), 149 IsCallerRecursive(false), IsRecursiveCall(false), 150 ExposesReturnsTwice(false), HasDynamicAlloca(false), 151 ContainsNoDuplicateCall(false), HasReturn(false), HasIndirectBr(false), 152 HasFrameEscape(false), AllocatedSize(0), NumInstructions(0), 153 NumVectorInstructions(0), FiftyPercentVectorBonus(0), 154 TenPercentVectorBonus(0), VectorBonus(0), NumConstantArgs(0), 155 NumConstantOffsetPtrArgs(0), NumAllocaArgs(0), NumConstantPtrCmps(0), 156 NumConstantPtrDiffs(0), NumInstructionsSimplified(0), 157 SROACostSavings(0), SROACostSavingsLost(0) {} 158 159 bool analyzeCall(CallSite CS); 160 161 int getThreshold() { return Threshold; } 162 int getCost() { return Cost; } 163 164 // Keep a bunch of stats about the cost savings found so we can print them 165 // out when debugging. 166 unsigned NumConstantArgs; 167 unsigned NumConstantOffsetPtrArgs; 168 unsigned NumAllocaArgs; 169 unsigned NumConstantPtrCmps; 170 unsigned NumConstantPtrDiffs; 171 unsigned NumInstructionsSimplified; 172 unsigned SROACostSavings; 173 unsigned SROACostSavingsLost; 174 175 void dump(); 176 }; 177 178 } // namespace 179 180 /// \brief Test whether the given value is an Alloca-derived function argument. 181 bool CallAnalyzer::isAllocaDerivedArg(Value *V) { 182 return SROAArgValues.count(V); 183 } 184 185 /// \brief Lookup the SROA-candidate argument and cost iterator which V maps to. 186 /// Returns false if V does not map to a SROA-candidate. 187 bool CallAnalyzer::lookupSROAArgAndCost( 188 Value *V, Value *&Arg, DenseMap<Value *, int>::iterator &CostIt) { 189 if (SROAArgValues.empty() || SROAArgCosts.empty()) 190 return false; 191 192 DenseMap<Value *, Value *>::iterator ArgIt = SROAArgValues.find(V); 193 if (ArgIt == SROAArgValues.end()) 194 return false; 195 196 Arg = ArgIt->second; 197 CostIt = SROAArgCosts.find(Arg); 198 return CostIt != SROAArgCosts.end(); 199 } 200 201 /// \brief Disable SROA for the candidate marked by this cost iterator. 202 /// 203 /// This marks the candidate as no longer viable for SROA, and adds the cost 204 /// savings associated with it back into the inline cost measurement. 205 void CallAnalyzer::disableSROA(DenseMap<Value *, int>::iterator CostIt) { 206 // If we're no longer able to perform SROA we need to undo its cost savings 207 // and prevent subsequent analysis. 208 Cost += CostIt->second; 209 SROACostSavings -= CostIt->second; 210 SROACostSavingsLost += CostIt->second; 211 SROAArgCosts.erase(CostIt); 212 } 213 214 /// \brief If 'V' maps to a SROA candidate, disable SROA for it. 215 void CallAnalyzer::disableSROA(Value *V) { 216 Value *SROAArg; 217 DenseMap<Value *, int>::iterator CostIt; 218 if (lookupSROAArgAndCost(V, SROAArg, CostIt)) 219 disableSROA(CostIt); 220 } 221 222 /// \brief Accumulate the given cost for a particular SROA candidate. 223 void CallAnalyzer::accumulateSROACost(DenseMap<Value *, int>::iterator CostIt, 224 int InstructionCost) { 225 CostIt->second += InstructionCost; 226 SROACostSavings += InstructionCost; 227 } 228 229 /// \brief Check whether a GEP's indices are all constant. 230 /// 231 /// Respects any simplified values known during the analysis of this callsite. 232 bool CallAnalyzer::isGEPOffsetConstant(GetElementPtrInst &GEP) { 233 for (User::op_iterator I = GEP.idx_begin(), E = GEP.idx_end(); I != E; ++I) 234 if (!isa<Constant>(*I) && !SimplifiedValues.lookup(*I)) 235 return false; 236 237 return true; 238 } 239 240 /// \brief Accumulate a constant GEP offset into an APInt if possible. 241 /// 242 /// Returns false if unable to compute the offset for any reason. Respects any 243 /// simplified values known during the analysis of this callsite. 244 bool CallAnalyzer::accumulateGEPOffset(GEPOperator &GEP, APInt &Offset) { 245 const DataLayout &DL = F.getParent()->getDataLayout(); 246 unsigned IntPtrWidth = DL.getPointerSizeInBits(); 247 assert(IntPtrWidth == Offset.getBitWidth()); 248 249 for (gep_type_iterator GTI = gep_type_begin(GEP), GTE = gep_type_end(GEP); 250 GTI != GTE; ++GTI) { 251 ConstantInt *OpC = dyn_cast<ConstantInt>(GTI.getOperand()); 252 if (!OpC) 253 if (Constant *SimpleOp = SimplifiedValues.lookup(GTI.getOperand())) 254 OpC = dyn_cast<ConstantInt>(SimpleOp); 255 if (!OpC) 256 return false; 257 if (OpC->isZero()) continue; 258 259 // Handle a struct index, which adds its field offset to the pointer. 260 if (StructType *STy = dyn_cast<StructType>(*GTI)) { 261 unsigned ElementIdx = OpC->getZExtValue(); 262 const StructLayout *SL = DL.getStructLayout(STy); 263 Offset += APInt(IntPtrWidth, SL->getElementOffset(ElementIdx)); 264 continue; 265 } 266 267 APInt TypeSize(IntPtrWidth, DL.getTypeAllocSize(GTI.getIndexedType())); 268 Offset += OpC->getValue().sextOrTrunc(IntPtrWidth) * TypeSize; 269 } 270 return true; 271 } 272 273 bool CallAnalyzer::visitAlloca(AllocaInst &I) { 274 // Check whether inlining will turn a dynamic alloca into a static 275 // alloca, and handle that case. 276 if (I.isArrayAllocation()) { 277 if (Constant *Size = SimplifiedValues.lookup(I.getArraySize())) { 278 ConstantInt *AllocSize = dyn_cast<ConstantInt>(Size); 279 assert(AllocSize && "Allocation size not a constant int?"); 280 Type *Ty = I.getAllocatedType(); 281 AllocatedSize += Ty->getPrimitiveSizeInBits() * AllocSize->getZExtValue(); 282 return Base::visitAlloca(I); 283 } 284 } 285 286 // Accumulate the allocated size. 287 if (I.isStaticAlloca()) { 288 const DataLayout &DL = F.getParent()->getDataLayout(); 289 Type *Ty = I.getAllocatedType(); 290 AllocatedSize += DL.getTypeAllocSize(Ty); 291 } 292 293 // We will happily inline static alloca instructions. 294 if (I.isStaticAlloca()) 295 return Base::visitAlloca(I); 296 297 // FIXME: This is overly conservative. Dynamic allocas are inefficient for 298 // a variety of reasons, and so we would like to not inline them into 299 // functions which don't currently have a dynamic alloca. This simply 300 // disables inlining altogether in the presence of a dynamic alloca. 301 HasDynamicAlloca = true; 302 return false; 303 } 304 305 bool CallAnalyzer::visitPHI(PHINode &I) { 306 // FIXME: We should potentially be tracking values through phi nodes, 307 // especially when they collapse to a single value due to deleted CFG edges 308 // during inlining. 309 310 // FIXME: We need to propagate SROA *disabling* through phi nodes, even 311 // though we don't want to propagate it's bonuses. The idea is to disable 312 // SROA if it *might* be used in an inappropriate manner. 313 314 // Phi nodes are always zero-cost. 315 return true; 316 } 317 318 bool CallAnalyzer::visitGetElementPtr(GetElementPtrInst &I) { 319 Value *SROAArg; 320 DenseMap<Value *, int>::iterator CostIt; 321 bool SROACandidate = lookupSROAArgAndCost(I.getPointerOperand(), 322 SROAArg, CostIt); 323 324 // Try to fold GEPs of constant-offset call site argument pointers. This 325 // requires target data and inbounds GEPs. 326 if (I.isInBounds()) { 327 // Check if we have a base + offset for the pointer. 328 Value *Ptr = I.getPointerOperand(); 329 std::pair<Value *, APInt> BaseAndOffset = ConstantOffsetPtrs.lookup(Ptr); 330 if (BaseAndOffset.first) { 331 // Check if the offset of this GEP is constant, and if so accumulate it 332 // into Offset. 333 if (!accumulateGEPOffset(cast<GEPOperator>(I), BaseAndOffset.second)) { 334 // Non-constant GEPs aren't folded, and disable SROA. 335 if (SROACandidate) 336 disableSROA(CostIt); 337 return false; 338 } 339 340 // Add the result as a new mapping to Base + Offset. 341 ConstantOffsetPtrs[&I] = BaseAndOffset; 342 343 // Also handle SROA candidates here, we already know that the GEP is 344 // all-constant indexed. 345 if (SROACandidate) 346 SROAArgValues[&I] = SROAArg; 347 348 return true; 349 } 350 } 351 352 if (isGEPOffsetConstant(I)) { 353 if (SROACandidate) 354 SROAArgValues[&I] = SROAArg; 355 356 // Constant GEPs are modeled as free. 357 return true; 358 } 359 360 // Variable GEPs will require math and will disable SROA. 361 if (SROACandidate) 362 disableSROA(CostIt); 363 return false; 364 } 365 366 bool CallAnalyzer::visitBitCast(BitCastInst &I) { 367 // Propagate constants through bitcasts. 368 Constant *COp = dyn_cast<Constant>(I.getOperand(0)); 369 if (!COp) 370 COp = SimplifiedValues.lookup(I.getOperand(0)); 371 if (COp) 372 if (Constant *C = ConstantExpr::getBitCast(COp, I.getType())) { 373 SimplifiedValues[&I] = C; 374 return true; 375 } 376 377 // Track base/offsets through casts 378 std::pair<Value *, APInt> BaseAndOffset 379 = ConstantOffsetPtrs.lookup(I.getOperand(0)); 380 // Casts don't change the offset, just wrap it up. 381 if (BaseAndOffset.first) 382 ConstantOffsetPtrs[&I] = BaseAndOffset; 383 384 // Also look for SROA candidates here. 385 Value *SROAArg; 386 DenseMap<Value *, int>::iterator CostIt; 387 if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt)) 388 SROAArgValues[&I] = SROAArg; 389 390 // Bitcasts are always zero cost. 391 return true; 392 } 393 394 bool CallAnalyzer::visitPtrToInt(PtrToIntInst &I) { 395 // Propagate constants through ptrtoint. 396 Constant *COp = dyn_cast<Constant>(I.getOperand(0)); 397 if (!COp) 398 COp = SimplifiedValues.lookup(I.getOperand(0)); 399 if (COp) 400 if (Constant *C = ConstantExpr::getPtrToInt(COp, I.getType())) { 401 SimplifiedValues[&I] = C; 402 return true; 403 } 404 405 // Track base/offset pairs when converted to a plain integer provided the 406 // integer is large enough to represent the pointer. 407 unsigned IntegerSize = I.getType()->getScalarSizeInBits(); 408 const DataLayout &DL = F.getParent()->getDataLayout(); 409 if (IntegerSize >= DL.getPointerSizeInBits()) { 410 std::pair<Value *, APInt> BaseAndOffset 411 = ConstantOffsetPtrs.lookup(I.getOperand(0)); 412 if (BaseAndOffset.first) 413 ConstantOffsetPtrs[&I] = BaseAndOffset; 414 } 415 416 // This is really weird. Technically, ptrtoint will disable SROA. However, 417 // unless that ptrtoint is *used* somewhere in the live basic blocks after 418 // inlining, it will be nuked, and SROA should proceed. All of the uses which 419 // would block SROA would also block SROA if applied directly to a pointer, 420 // and so we can just add the integer in here. The only places where SROA is 421 // preserved either cannot fire on an integer, or won't in-and-of themselves 422 // disable SROA (ext) w/o some later use that we would see and disable. 423 Value *SROAArg; 424 DenseMap<Value *, int>::iterator CostIt; 425 if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt)) 426 SROAArgValues[&I] = SROAArg; 427 428 return TargetTransformInfo::TCC_Free == TTI.getUserCost(&I); 429 } 430 431 bool CallAnalyzer::visitIntToPtr(IntToPtrInst &I) { 432 // Propagate constants through ptrtoint. 433 Constant *COp = dyn_cast<Constant>(I.getOperand(0)); 434 if (!COp) 435 COp = SimplifiedValues.lookup(I.getOperand(0)); 436 if (COp) 437 if (Constant *C = ConstantExpr::getIntToPtr(COp, I.getType())) { 438 SimplifiedValues[&I] = C; 439 return true; 440 } 441 442 // Track base/offset pairs when round-tripped through a pointer without 443 // modifications provided the integer is not too large. 444 Value *Op = I.getOperand(0); 445 unsigned IntegerSize = Op->getType()->getScalarSizeInBits(); 446 const DataLayout &DL = F.getParent()->getDataLayout(); 447 if (IntegerSize <= DL.getPointerSizeInBits()) { 448 std::pair<Value *, APInt> BaseAndOffset = ConstantOffsetPtrs.lookup(Op); 449 if (BaseAndOffset.first) 450 ConstantOffsetPtrs[&I] = BaseAndOffset; 451 } 452 453 // "Propagate" SROA here in the same manner as we do for ptrtoint above. 454 Value *SROAArg; 455 DenseMap<Value *, int>::iterator CostIt; 456 if (lookupSROAArgAndCost(Op, SROAArg, CostIt)) 457 SROAArgValues[&I] = SROAArg; 458 459 return TargetTransformInfo::TCC_Free == TTI.getUserCost(&I); 460 } 461 462 bool CallAnalyzer::visitCastInst(CastInst &I) { 463 // Propagate constants through ptrtoint. 464 Constant *COp = dyn_cast<Constant>(I.getOperand(0)); 465 if (!COp) 466 COp = SimplifiedValues.lookup(I.getOperand(0)); 467 if (COp) 468 if (Constant *C = ConstantExpr::getCast(I.getOpcode(), COp, I.getType())) { 469 SimplifiedValues[&I] = C; 470 return true; 471 } 472 473 // Disable SROA in the face of arbitrary casts we don't whitelist elsewhere. 474 disableSROA(I.getOperand(0)); 475 476 return TargetTransformInfo::TCC_Free == TTI.getUserCost(&I); 477 } 478 479 bool CallAnalyzer::visitUnaryInstruction(UnaryInstruction &I) { 480 Value *Operand = I.getOperand(0); 481 Constant *COp = dyn_cast<Constant>(Operand); 482 if (!COp) 483 COp = SimplifiedValues.lookup(Operand); 484 if (COp) { 485 const DataLayout &DL = F.getParent()->getDataLayout(); 486 if (Constant *C = ConstantFoldInstOperands(I.getOpcode(), I.getType(), 487 COp, DL)) { 488 SimplifiedValues[&I] = C; 489 return true; 490 } 491 } 492 493 // Disable any SROA on the argument to arbitrary unary operators. 494 disableSROA(Operand); 495 496 return false; 497 } 498 499 bool CallAnalyzer::visitCmpInst(CmpInst &I) { 500 Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); 501 // First try to handle simplified comparisons. 502 if (!isa<Constant>(LHS)) 503 if (Constant *SimpleLHS = SimplifiedValues.lookup(LHS)) 504 LHS = SimpleLHS; 505 if (!isa<Constant>(RHS)) 506 if (Constant *SimpleRHS = SimplifiedValues.lookup(RHS)) 507 RHS = SimpleRHS; 508 if (Constant *CLHS = dyn_cast<Constant>(LHS)) { 509 if (Constant *CRHS = dyn_cast<Constant>(RHS)) 510 if (Constant *C = ConstantExpr::getCompare(I.getPredicate(), CLHS, CRHS)) { 511 SimplifiedValues[&I] = C; 512 return true; 513 } 514 } 515 516 if (I.getOpcode() == Instruction::FCmp) 517 return false; 518 519 // Otherwise look for a comparison between constant offset pointers with 520 // a common base. 521 Value *LHSBase, *RHSBase; 522 APInt LHSOffset, RHSOffset; 523 std::tie(LHSBase, LHSOffset) = ConstantOffsetPtrs.lookup(LHS); 524 if (LHSBase) { 525 std::tie(RHSBase, RHSOffset) = ConstantOffsetPtrs.lookup(RHS); 526 if (RHSBase && LHSBase == RHSBase) { 527 // We have common bases, fold the icmp to a constant based on the 528 // offsets. 529 Constant *CLHS = ConstantInt::get(LHS->getContext(), LHSOffset); 530 Constant *CRHS = ConstantInt::get(RHS->getContext(), RHSOffset); 531 if (Constant *C = ConstantExpr::getICmp(I.getPredicate(), CLHS, CRHS)) { 532 SimplifiedValues[&I] = C; 533 ++NumConstantPtrCmps; 534 return true; 535 } 536 } 537 } 538 539 // If the comparison is an equality comparison with null, we can simplify it 540 // for any alloca-derived argument. 541 if (I.isEquality() && isa<ConstantPointerNull>(I.getOperand(1))) 542 if (isAllocaDerivedArg(I.getOperand(0))) { 543 // We can actually predict the result of comparisons between an 544 // alloca-derived value and null. Note that this fires regardless of 545 // SROA firing. 546 bool IsNotEqual = I.getPredicate() == CmpInst::ICMP_NE; 547 SimplifiedValues[&I] = IsNotEqual ? ConstantInt::getTrue(I.getType()) 548 : ConstantInt::getFalse(I.getType()); 549 return true; 550 } 551 552 // Finally check for SROA candidates in comparisons. 553 Value *SROAArg; 554 DenseMap<Value *, int>::iterator CostIt; 555 if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt)) { 556 if (isa<ConstantPointerNull>(I.getOperand(1))) { 557 accumulateSROACost(CostIt, InlineConstants::InstrCost); 558 return true; 559 } 560 561 disableSROA(CostIt); 562 } 563 564 return false; 565 } 566 567 bool CallAnalyzer::visitSub(BinaryOperator &I) { 568 // Try to handle a special case: we can fold computing the difference of two 569 // constant-related pointers. 570 Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); 571 Value *LHSBase, *RHSBase; 572 APInt LHSOffset, RHSOffset; 573 std::tie(LHSBase, LHSOffset) = ConstantOffsetPtrs.lookup(LHS); 574 if (LHSBase) { 575 std::tie(RHSBase, RHSOffset) = ConstantOffsetPtrs.lookup(RHS); 576 if (RHSBase && LHSBase == RHSBase) { 577 // We have common bases, fold the subtract to a constant based on the 578 // offsets. 579 Constant *CLHS = ConstantInt::get(LHS->getContext(), LHSOffset); 580 Constant *CRHS = ConstantInt::get(RHS->getContext(), RHSOffset); 581 if (Constant *C = ConstantExpr::getSub(CLHS, CRHS)) { 582 SimplifiedValues[&I] = C; 583 ++NumConstantPtrDiffs; 584 return true; 585 } 586 } 587 } 588 589 // Otherwise, fall back to the generic logic for simplifying and handling 590 // instructions. 591 return Base::visitSub(I); 592 } 593 594 bool CallAnalyzer::visitBinaryOperator(BinaryOperator &I) { 595 Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); 596 const DataLayout &DL = F.getParent()->getDataLayout(); 597 if (!isa<Constant>(LHS)) 598 if (Constant *SimpleLHS = SimplifiedValues.lookup(LHS)) 599 LHS = SimpleLHS; 600 if (!isa<Constant>(RHS)) 601 if (Constant *SimpleRHS = SimplifiedValues.lookup(RHS)) 602 RHS = SimpleRHS; 603 Value *SimpleV = nullptr; 604 if (auto FI = dyn_cast<FPMathOperator>(&I)) 605 SimpleV = 606 SimplifyFPBinOp(I.getOpcode(), LHS, RHS, FI->getFastMathFlags(), DL); 607 else 608 SimpleV = SimplifyBinOp(I.getOpcode(), LHS, RHS, DL); 609 610 if (Constant *C = dyn_cast_or_null<Constant>(SimpleV)) { 611 SimplifiedValues[&I] = C; 612 return true; 613 } 614 615 // Disable any SROA on arguments to arbitrary, unsimplified binary operators. 616 disableSROA(LHS); 617 disableSROA(RHS); 618 619 return false; 620 } 621 622 bool CallAnalyzer::visitLoad(LoadInst &I) { 623 Value *SROAArg; 624 DenseMap<Value *, int>::iterator CostIt; 625 if (lookupSROAArgAndCost(I.getPointerOperand(), SROAArg, CostIt)) { 626 if (I.isSimple()) { 627 accumulateSROACost(CostIt, InlineConstants::InstrCost); 628 return true; 629 } 630 631 disableSROA(CostIt); 632 } 633 634 return false; 635 } 636 637 bool CallAnalyzer::visitStore(StoreInst &I) { 638 Value *SROAArg; 639 DenseMap<Value *, int>::iterator CostIt; 640 if (lookupSROAArgAndCost(I.getPointerOperand(), SROAArg, CostIt)) { 641 if (I.isSimple()) { 642 accumulateSROACost(CostIt, InlineConstants::InstrCost); 643 return true; 644 } 645 646 disableSROA(CostIt); 647 } 648 649 return false; 650 } 651 652 bool CallAnalyzer::visitExtractValue(ExtractValueInst &I) { 653 // Constant folding for extract value is trivial. 654 Constant *C = dyn_cast<Constant>(I.getAggregateOperand()); 655 if (!C) 656 C = SimplifiedValues.lookup(I.getAggregateOperand()); 657 if (C) { 658 SimplifiedValues[&I] = ConstantExpr::getExtractValue(C, I.getIndices()); 659 return true; 660 } 661 662 // SROA can look through these but give them a cost. 663 return false; 664 } 665 666 bool CallAnalyzer::visitInsertValue(InsertValueInst &I) { 667 // Constant folding for insert value is trivial. 668 Constant *AggC = dyn_cast<Constant>(I.getAggregateOperand()); 669 if (!AggC) 670 AggC = SimplifiedValues.lookup(I.getAggregateOperand()); 671 Constant *InsertedC = dyn_cast<Constant>(I.getInsertedValueOperand()); 672 if (!InsertedC) 673 InsertedC = SimplifiedValues.lookup(I.getInsertedValueOperand()); 674 if (AggC && InsertedC) { 675 SimplifiedValues[&I] = ConstantExpr::getInsertValue(AggC, InsertedC, 676 I.getIndices()); 677 return true; 678 } 679 680 // SROA can look through these but give them a cost. 681 return false; 682 } 683 684 /// \brief Try to simplify a call site. 685 /// 686 /// Takes a concrete function and callsite and tries to actually simplify it by 687 /// analyzing the arguments and call itself with instsimplify. Returns true if 688 /// it has simplified the callsite to some other entity (a constant), making it 689 /// free. 690 bool CallAnalyzer::simplifyCallSite(Function *F, CallSite CS) { 691 // FIXME: Using the instsimplify logic directly for this is inefficient 692 // because we have to continually rebuild the argument list even when no 693 // simplifications can be performed. Until that is fixed with remapping 694 // inside of instsimplify, directly constant fold calls here. 695 if (!canConstantFoldCallTo(F)) 696 return false; 697 698 // Try to re-map the arguments to constants. 699 SmallVector<Constant *, 4> ConstantArgs; 700 ConstantArgs.reserve(CS.arg_size()); 701 for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); 702 I != E; ++I) { 703 Constant *C = dyn_cast<Constant>(*I); 704 if (!C) 705 C = dyn_cast_or_null<Constant>(SimplifiedValues.lookup(*I)); 706 if (!C) 707 return false; // This argument doesn't map to a constant. 708 709 ConstantArgs.push_back(C); 710 } 711 if (Constant *C = ConstantFoldCall(F, ConstantArgs)) { 712 SimplifiedValues[CS.getInstruction()] = C; 713 return true; 714 } 715 716 return false; 717 } 718 719 bool CallAnalyzer::visitCallSite(CallSite CS) { 720 if (CS.hasFnAttr(Attribute::ReturnsTwice) && 721 !F.hasFnAttribute(Attribute::ReturnsTwice)) { 722 // This aborts the entire analysis. 723 ExposesReturnsTwice = true; 724 return false; 725 } 726 if (CS.isCall() && 727 cast<CallInst>(CS.getInstruction())->cannotDuplicate()) 728 ContainsNoDuplicateCall = true; 729 730 if (Function *F = CS.getCalledFunction()) { 731 // When we have a concrete function, first try to simplify it directly. 732 if (simplifyCallSite(F, CS)) 733 return true; 734 735 // Next check if it is an intrinsic we know about. 736 // FIXME: Lift this into part of the InstVisitor. 737 if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction())) { 738 switch (II->getIntrinsicID()) { 739 default: 740 return Base::visitCallSite(CS); 741 742 case Intrinsic::memset: 743 case Intrinsic::memcpy: 744 case Intrinsic::memmove: 745 // SROA can usually chew through these intrinsics, but they aren't free. 746 return false; 747 case Intrinsic::frameescape: 748 HasFrameEscape = true; 749 return false; 750 } 751 } 752 753 if (F == CS.getInstruction()->getParent()->getParent()) { 754 // This flag will fully abort the analysis, so don't bother with anything 755 // else. 756 IsRecursiveCall = true; 757 return false; 758 } 759 760 if (TTI.isLoweredToCall(F)) { 761 // We account for the average 1 instruction per call argument setup 762 // here. 763 Cost += CS.arg_size() * InlineConstants::InstrCost; 764 765 // Everything other than inline ASM will also have a significant cost 766 // merely from making the call. 767 if (!isa<InlineAsm>(CS.getCalledValue())) 768 Cost += InlineConstants::CallPenalty; 769 } 770 771 return Base::visitCallSite(CS); 772 } 773 774 // Otherwise we're in a very special case -- an indirect function call. See 775 // if we can be particularly clever about this. 776 Value *Callee = CS.getCalledValue(); 777 778 // First, pay the price of the argument setup. We account for the average 779 // 1 instruction per call argument setup here. 780 Cost += CS.arg_size() * InlineConstants::InstrCost; 781 782 // Next, check if this happens to be an indirect function call to a known 783 // function in this inline context. If not, we've done all we can. 784 Function *F = dyn_cast_or_null<Function>(SimplifiedValues.lookup(Callee)); 785 if (!F) 786 return Base::visitCallSite(CS); 787 788 // If we have a constant that we are calling as a function, we can peer 789 // through it and see the function target. This happens not infrequently 790 // during devirtualization and so we want to give it a hefty bonus for 791 // inlining, but cap that bonus in the event that inlining wouldn't pan 792 // out. Pretend to inline the function, with a custom threshold. 793 CallAnalyzer CA(TTI, ACT, *F, InlineConstants::IndirectCallThreshold); 794 if (CA.analyzeCall(CS)) { 795 // We were able to inline the indirect call! Subtract the cost from the 796 // bonus we want to apply, but don't go below zero. 797 Cost -= std::max(0, InlineConstants::IndirectCallThreshold - CA.getCost()); 798 } 799 800 return Base::visitCallSite(CS); 801 } 802 803 bool CallAnalyzer::visitReturnInst(ReturnInst &RI) { 804 // At least one return instruction will be free after inlining. 805 bool Free = !HasReturn; 806 HasReturn = true; 807 return Free; 808 } 809 810 bool CallAnalyzer::visitBranchInst(BranchInst &BI) { 811 // We model unconditional branches as essentially free -- they really 812 // shouldn't exist at all, but handling them makes the behavior of the 813 // inliner more regular and predictable. Interestingly, conditional branches 814 // which will fold away are also free. 815 return BI.isUnconditional() || isa<ConstantInt>(BI.getCondition()) || 816 dyn_cast_or_null<ConstantInt>( 817 SimplifiedValues.lookup(BI.getCondition())); 818 } 819 820 bool CallAnalyzer::visitSwitchInst(SwitchInst &SI) { 821 // We model unconditional switches as free, see the comments on handling 822 // branches. 823 if (isa<ConstantInt>(SI.getCondition())) 824 return true; 825 if (Value *V = SimplifiedValues.lookup(SI.getCondition())) 826 if (isa<ConstantInt>(V)) 827 return true; 828 829 // Otherwise, we need to accumulate a cost proportional to the number of 830 // distinct successor blocks. This fan-out in the CFG cannot be represented 831 // for free even if we can represent the core switch as a jumptable that 832 // takes a single instruction. 833 // 834 // NB: We convert large switches which are just used to initialize large phi 835 // nodes to lookup tables instead in simplify-cfg, so this shouldn't prevent 836 // inlining those. It will prevent inlining in cases where the optimization 837 // does not (yet) fire. 838 SmallPtrSet<BasicBlock *, 8> SuccessorBlocks; 839 SuccessorBlocks.insert(SI.getDefaultDest()); 840 for (auto I = SI.case_begin(), E = SI.case_end(); I != E; ++I) 841 SuccessorBlocks.insert(I.getCaseSuccessor()); 842 // Add cost corresponding to the number of distinct destinations. The first 843 // we model as free because of fallthrough. 844 Cost += (SuccessorBlocks.size() - 1) * InlineConstants::InstrCost; 845 return false; 846 } 847 848 bool CallAnalyzer::visitIndirectBrInst(IndirectBrInst &IBI) { 849 // We never want to inline functions that contain an indirectbr. This is 850 // incorrect because all the blockaddress's (in static global initializers 851 // for example) would be referring to the original function, and this 852 // indirect jump would jump from the inlined copy of the function into the 853 // original function which is extremely undefined behavior. 854 // FIXME: This logic isn't really right; we can safely inline functions with 855 // indirectbr's as long as no other function or global references the 856 // blockaddress of a block within the current function. 857 HasIndirectBr = true; 858 return false; 859 } 860 861 bool CallAnalyzer::visitResumeInst(ResumeInst &RI) { 862 // FIXME: It's not clear that a single instruction is an accurate model for 863 // the inline cost of a resume instruction. 864 return false; 865 } 866 867 bool CallAnalyzer::visitUnreachableInst(UnreachableInst &I) { 868 // FIXME: It might be reasonably to discount the cost of instructions leading 869 // to unreachable as they have the lowest possible impact on both runtime and 870 // code size. 871 return true; // No actual code is needed for unreachable. 872 } 873 874 bool CallAnalyzer::visitInstruction(Instruction &I) { 875 // Some instructions are free. All of the free intrinsics can also be 876 // handled by SROA, etc. 877 if (TargetTransformInfo::TCC_Free == TTI.getUserCost(&I)) 878 return true; 879 880 // We found something we don't understand or can't handle. Mark any SROA-able 881 // values in the operand list as no longer viable. 882 for (User::op_iterator OI = I.op_begin(), OE = I.op_end(); OI != OE; ++OI) 883 disableSROA(*OI); 884 885 return false; 886 } 887 888 889 /// \brief Analyze a basic block for its contribution to the inline cost. 890 /// 891 /// This method walks the analyzer over every instruction in the given basic 892 /// block and accounts for their cost during inlining at this callsite. It 893 /// aborts early if the threshold has been exceeded or an impossible to inline 894 /// construct has been detected. It returns false if inlining is no longer 895 /// viable, and true if inlining remains viable. 896 bool CallAnalyzer::analyzeBlock(BasicBlock *BB, 897 SmallPtrSetImpl<const Value *> &EphValues) { 898 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { 899 // FIXME: Currently, the number of instructions in a function regardless of 900 // our ability to simplify them during inline to constants or dead code, 901 // are actually used by the vector bonus heuristic. As long as that's true, 902 // we have to special case debug intrinsics here to prevent differences in 903 // inlining due to debug symbols. Eventually, the number of unsimplified 904 // instructions shouldn't factor into the cost computation, but until then, 905 // hack around it here. 906 if (isa<DbgInfoIntrinsic>(I)) 907 continue; 908 909 // Skip ephemeral values. 910 if (EphValues.count(I)) 911 continue; 912 913 ++NumInstructions; 914 if (isa<ExtractElementInst>(I) || I->getType()->isVectorTy()) 915 ++NumVectorInstructions; 916 917 // If the instruction is floating point, and the target says this operation is 918 // expensive or the function has the "use-soft-float" attribute, this may 919 // eventually become a library call. Treat the cost as such. 920 if (I->getType()->isFloatingPointTy()) { 921 bool hasSoftFloatAttr = false; 922 923 // If the function has the "use-soft-float" attribute, mark it as expensive. 924 if (F.hasFnAttribute("use-soft-float")) { 925 Attribute Attr = F.getFnAttribute("use-soft-float"); 926 StringRef Val = Attr.getValueAsString(); 927 if (Val == "true") 928 hasSoftFloatAttr = true; 929 } 930 931 if (TTI.getFPOpCost(I->getType()) == TargetTransformInfo::TCC_Expensive || 932 hasSoftFloatAttr) 933 Cost += InlineConstants::CallPenalty; 934 } 935 936 // If the instruction simplified to a constant, there is no cost to this 937 // instruction. Visit the instructions using our InstVisitor to account for 938 // all of the per-instruction logic. The visit tree returns true if we 939 // consumed the instruction in any way, and false if the instruction's base 940 // cost should count against inlining. 941 if (Base::visit(I)) 942 ++NumInstructionsSimplified; 943 else 944 Cost += InlineConstants::InstrCost; 945 946 // If the visit this instruction detected an uninlinable pattern, abort. 947 if (IsRecursiveCall || ExposesReturnsTwice || HasDynamicAlloca || 948 HasIndirectBr || HasFrameEscape) 949 return false; 950 951 // If the caller is a recursive function then we don't want to inline 952 // functions which allocate a lot of stack space because it would increase 953 // the caller stack usage dramatically. 954 if (IsCallerRecursive && 955 AllocatedSize > InlineConstants::TotalAllocaSizeRecursiveCaller) 956 return false; 957 958 if (NumVectorInstructions > NumInstructions/2) 959 VectorBonus = FiftyPercentVectorBonus; 960 else if (NumVectorInstructions > NumInstructions/10) 961 VectorBonus = TenPercentVectorBonus; 962 else 963 VectorBonus = 0; 964 965 // Check if we've past the threshold so we don't spin in huge basic 966 // blocks that will never inline. 967 if (Cost > (Threshold + VectorBonus)) 968 return false; 969 } 970 971 return true; 972 } 973 974 /// \brief Compute the base pointer and cumulative constant offsets for V. 975 /// 976 /// This strips all constant offsets off of V, leaving it the base pointer, and 977 /// accumulates the total constant offset applied in the returned constant. It 978 /// returns 0 if V is not a pointer, and returns the constant '0' if there are 979 /// no constant offsets applied. 980 ConstantInt *CallAnalyzer::stripAndComputeInBoundsConstantOffsets(Value *&V) { 981 if (!V->getType()->isPointerTy()) 982 return nullptr; 983 984 const DataLayout &DL = F.getParent()->getDataLayout(); 985 unsigned IntPtrWidth = DL.getPointerSizeInBits(); 986 APInt Offset = APInt::getNullValue(IntPtrWidth); 987 988 // Even though we don't look through PHI nodes, we could be called on an 989 // instruction in an unreachable block, which may be on a cycle. 990 SmallPtrSet<Value *, 4> Visited; 991 Visited.insert(V); 992 do { 993 if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) { 994 if (!GEP->isInBounds() || !accumulateGEPOffset(*GEP, Offset)) 995 return nullptr; 996 V = GEP->getPointerOperand(); 997 } else if (Operator::getOpcode(V) == Instruction::BitCast) { 998 V = cast<Operator>(V)->getOperand(0); 999 } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) { 1000 if (GA->mayBeOverridden()) 1001 break; 1002 V = GA->getAliasee(); 1003 } else { 1004 break; 1005 } 1006 assert(V->getType()->isPointerTy() && "Unexpected operand type!"); 1007 } while (Visited.insert(V).second); 1008 1009 Type *IntPtrTy = DL.getIntPtrType(V->getContext()); 1010 return cast<ConstantInt>(ConstantInt::get(IntPtrTy, Offset)); 1011 } 1012 1013 /// \brief Analyze a call site for potential inlining. 1014 /// 1015 /// Returns true if inlining this call is viable, and false if it is not 1016 /// viable. It computes the cost and adjusts the threshold based on numerous 1017 /// factors and heuristics. If this method returns false but the computed cost 1018 /// is below the computed threshold, then inlining was forcibly disabled by 1019 /// some artifact of the routine. 1020 bool CallAnalyzer::analyzeCall(CallSite CS) { 1021 ++NumCallsAnalyzed; 1022 1023 // Track whether the post-inlining function would have more than one basic 1024 // block. A single basic block is often intended for inlining. Balloon the 1025 // threshold by 50% until we pass the single-BB phase. 1026 bool SingleBB = true; 1027 int SingleBBBonus = Threshold / 2; 1028 Threshold += SingleBBBonus; 1029 1030 // Perform some tweaks to the cost and threshold based on the direct 1031 // callsite information. 1032 1033 // We want to more aggressively inline vector-dense kernels, so up the 1034 // threshold, and we'll lower it if the % of vector instructions gets too 1035 // low. 1036 assert(NumInstructions == 0); 1037 assert(NumVectorInstructions == 0); 1038 FiftyPercentVectorBonus = Threshold; 1039 TenPercentVectorBonus = Threshold / 2; 1040 const DataLayout &DL = F.getParent()->getDataLayout(); 1041 1042 // Give out bonuses per argument, as the instructions setting them up will 1043 // be gone after inlining. 1044 for (unsigned I = 0, E = CS.arg_size(); I != E; ++I) { 1045 if (CS.isByValArgument(I)) { 1046 // We approximate the number of loads and stores needed by dividing the 1047 // size of the byval type by the target's pointer size. 1048 PointerType *PTy = cast<PointerType>(CS.getArgument(I)->getType()); 1049 unsigned TypeSize = DL.getTypeSizeInBits(PTy->getElementType()); 1050 unsigned PointerSize = DL.getPointerSizeInBits(); 1051 // Ceiling division. 1052 unsigned NumStores = (TypeSize + PointerSize - 1) / PointerSize; 1053 1054 // If it generates more than 8 stores it is likely to be expanded as an 1055 // inline memcpy so we take that as an upper bound. Otherwise we assume 1056 // one load and one store per word copied. 1057 // FIXME: The maxStoresPerMemcpy setting from the target should be used 1058 // here instead of a magic number of 8, but it's not available via 1059 // DataLayout. 1060 NumStores = std::min(NumStores, 8U); 1061 1062 Cost -= 2 * NumStores * InlineConstants::InstrCost; 1063 } else { 1064 // For non-byval arguments subtract off one instruction per call 1065 // argument. 1066 Cost -= InlineConstants::InstrCost; 1067 } 1068 } 1069 1070 // If there is only one call of the function, and it has internal linkage, 1071 // the cost of inlining it drops dramatically. 1072 bool OnlyOneCallAndLocalLinkage = F.hasLocalLinkage() && F.hasOneUse() && 1073 &F == CS.getCalledFunction(); 1074 if (OnlyOneCallAndLocalLinkage) 1075 Cost += InlineConstants::LastCallToStaticBonus; 1076 1077 // If the instruction after the call, or if the normal destination of the 1078 // invoke is an unreachable instruction, the function is noreturn. As such, 1079 // there is little point in inlining this unless there is literally zero 1080 // cost. 1081 Instruction *Instr = CS.getInstruction(); 1082 if (InvokeInst *II = dyn_cast<InvokeInst>(Instr)) { 1083 if (isa<UnreachableInst>(II->getNormalDest()->begin())) 1084 Threshold = 1; 1085 } else if (isa<UnreachableInst>(++BasicBlock::iterator(Instr))) 1086 Threshold = 1; 1087 1088 // If this function uses the coldcc calling convention, prefer not to inline 1089 // it. 1090 if (F.getCallingConv() == CallingConv::Cold) 1091 Cost += InlineConstants::ColdccPenalty; 1092 1093 // Check if we're done. This can happen due to bonuses and penalties. 1094 if (Cost > Threshold) 1095 return false; 1096 1097 if (F.empty()) 1098 return true; 1099 1100 Function *Caller = CS.getInstruction()->getParent()->getParent(); 1101 // Check if the caller function is recursive itself. 1102 for (User *U : Caller->users()) { 1103 CallSite Site(U); 1104 if (!Site) 1105 continue; 1106 Instruction *I = Site.getInstruction(); 1107 if (I->getParent()->getParent() == Caller) { 1108 IsCallerRecursive = true; 1109 break; 1110 } 1111 } 1112 1113 // Populate our simplified values by mapping from function arguments to call 1114 // arguments with known important simplifications. 1115 CallSite::arg_iterator CAI = CS.arg_begin(); 1116 for (Function::arg_iterator FAI = F.arg_begin(), FAE = F.arg_end(); 1117 FAI != FAE; ++FAI, ++CAI) { 1118 assert(CAI != CS.arg_end()); 1119 if (Constant *C = dyn_cast<Constant>(CAI)) 1120 SimplifiedValues[FAI] = C; 1121 1122 Value *PtrArg = *CAI; 1123 if (ConstantInt *C = stripAndComputeInBoundsConstantOffsets(PtrArg)) { 1124 ConstantOffsetPtrs[FAI] = std::make_pair(PtrArg, C->getValue()); 1125 1126 // We can SROA any pointer arguments derived from alloca instructions. 1127 if (isa<AllocaInst>(PtrArg)) { 1128 SROAArgValues[FAI] = PtrArg; 1129 SROAArgCosts[PtrArg] = 0; 1130 } 1131 } 1132 } 1133 NumConstantArgs = SimplifiedValues.size(); 1134 NumConstantOffsetPtrArgs = ConstantOffsetPtrs.size(); 1135 NumAllocaArgs = SROAArgValues.size(); 1136 1137 // FIXME: If a caller has multiple calls to a callee, we end up recomputing 1138 // the ephemeral values multiple times (and they're completely determined by 1139 // the callee, so this is purely duplicate work). 1140 SmallPtrSet<const Value *, 32> EphValues; 1141 CodeMetrics::collectEphemeralValues(&F, &ACT->getAssumptionCache(F), EphValues); 1142 1143 // The worklist of live basic blocks in the callee *after* inlining. We avoid 1144 // adding basic blocks of the callee which can be proven to be dead for this 1145 // particular call site in order to get more accurate cost estimates. This 1146 // requires a somewhat heavyweight iteration pattern: we need to walk the 1147 // basic blocks in a breadth-first order as we insert live successors. To 1148 // accomplish this, prioritizing for small iterations because we exit after 1149 // crossing our threshold, we use a small-size optimized SetVector. 1150 typedef SetVector<BasicBlock *, SmallVector<BasicBlock *, 16>, 1151 SmallPtrSet<BasicBlock *, 16> > BBSetVector; 1152 BBSetVector BBWorklist; 1153 BBWorklist.insert(&F.getEntryBlock()); 1154 // Note that we *must not* cache the size, this loop grows the worklist. 1155 for (unsigned Idx = 0; Idx != BBWorklist.size(); ++Idx) { 1156 // Bail out the moment we cross the threshold. This means we'll under-count 1157 // the cost, but only when undercounting doesn't matter. 1158 if (Cost > (Threshold + VectorBonus)) 1159 break; 1160 1161 BasicBlock *BB = BBWorklist[Idx]; 1162 if (BB->empty()) 1163 continue; 1164 1165 // Disallow inlining a blockaddress. A blockaddress only has defined 1166 // behavior for an indirect branch in the same function, and we do not 1167 // currently support inlining indirect branches. But, the inliner may not 1168 // see an indirect branch that ends up being dead code at a particular call 1169 // site. If the blockaddress escapes the function, e.g., via a global 1170 // variable, inlining may lead to an invalid cross-function reference. 1171 if (BB->hasAddressTaken()) 1172 return false; 1173 1174 // Analyze the cost of this block. If we blow through the threshold, this 1175 // returns false, and we can bail on out. 1176 if (!analyzeBlock(BB, EphValues)) { 1177 if (IsRecursiveCall || ExposesReturnsTwice || HasDynamicAlloca || 1178 HasIndirectBr || HasFrameEscape) 1179 return false; 1180 1181 // If the caller is a recursive function then we don't want to inline 1182 // functions which allocate a lot of stack space because it would increase 1183 // the caller stack usage dramatically. 1184 if (IsCallerRecursive && 1185 AllocatedSize > InlineConstants::TotalAllocaSizeRecursiveCaller) 1186 return false; 1187 1188 break; 1189 } 1190 1191 TerminatorInst *TI = BB->getTerminator(); 1192 1193 // Add in the live successors by first checking whether we have terminator 1194 // that may be simplified based on the values simplified by this call. 1195 if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 1196 if (BI->isConditional()) { 1197 Value *Cond = BI->getCondition(); 1198 if (ConstantInt *SimpleCond 1199 = dyn_cast_or_null<ConstantInt>(SimplifiedValues.lookup(Cond))) { 1200 BBWorklist.insert(BI->getSuccessor(SimpleCond->isZero() ? 1 : 0)); 1201 continue; 1202 } 1203 } 1204 } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 1205 Value *Cond = SI->getCondition(); 1206 if (ConstantInt *SimpleCond 1207 = dyn_cast_or_null<ConstantInt>(SimplifiedValues.lookup(Cond))) { 1208 BBWorklist.insert(SI->findCaseValue(SimpleCond).getCaseSuccessor()); 1209 continue; 1210 } 1211 } 1212 1213 // If we're unable to select a particular successor, just count all of 1214 // them. 1215 for (unsigned TIdx = 0, TSize = TI->getNumSuccessors(); TIdx != TSize; 1216 ++TIdx) 1217 BBWorklist.insert(TI->getSuccessor(TIdx)); 1218 1219 // If we had any successors at this point, than post-inlining is likely to 1220 // have them as well. Note that we assume any basic blocks which existed 1221 // due to branches or switches which folded above will also fold after 1222 // inlining. 1223 if (SingleBB && TI->getNumSuccessors() > 1) { 1224 // Take off the bonus we applied to the threshold. 1225 Threshold -= SingleBBBonus; 1226 SingleBB = false; 1227 } 1228 } 1229 1230 // If this is a noduplicate call, we can still inline as long as 1231 // inlining this would cause the removal of the caller (so the instruction 1232 // is not actually duplicated, just moved). 1233 if (!OnlyOneCallAndLocalLinkage && ContainsNoDuplicateCall) 1234 return false; 1235 1236 Threshold += VectorBonus; 1237 1238 return Cost < Threshold; 1239 } 1240 1241 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 1242 /// \brief Dump stats about this call's analysis. 1243 void CallAnalyzer::dump() { 1244 #define DEBUG_PRINT_STAT(x) dbgs() << " " #x ": " << x << "\n" 1245 DEBUG_PRINT_STAT(NumConstantArgs); 1246 DEBUG_PRINT_STAT(NumConstantOffsetPtrArgs); 1247 DEBUG_PRINT_STAT(NumAllocaArgs); 1248 DEBUG_PRINT_STAT(NumConstantPtrCmps); 1249 DEBUG_PRINT_STAT(NumConstantPtrDiffs); 1250 DEBUG_PRINT_STAT(NumInstructionsSimplified); 1251 DEBUG_PRINT_STAT(SROACostSavings); 1252 DEBUG_PRINT_STAT(SROACostSavingsLost); 1253 DEBUG_PRINT_STAT(ContainsNoDuplicateCall); 1254 DEBUG_PRINT_STAT(Cost); 1255 DEBUG_PRINT_STAT(Threshold); 1256 DEBUG_PRINT_STAT(VectorBonus); 1257 #undef DEBUG_PRINT_STAT 1258 } 1259 #endif 1260 1261 INITIALIZE_PASS_BEGIN(InlineCostAnalysis, "inline-cost", "Inline Cost Analysis", 1262 true, true) 1263 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) 1264 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) 1265 INITIALIZE_PASS_END(InlineCostAnalysis, "inline-cost", "Inline Cost Analysis", 1266 true, true) 1267 1268 char InlineCostAnalysis::ID = 0; 1269 1270 InlineCostAnalysis::InlineCostAnalysis() : CallGraphSCCPass(ID) {} 1271 1272 InlineCostAnalysis::~InlineCostAnalysis() {} 1273 1274 void InlineCostAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 1275 AU.setPreservesAll(); 1276 AU.addRequired<AssumptionCacheTracker>(); 1277 AU.addRequired<TargetTransformInfoWrapperPass>(); 1278 CallGraphSCCPass::getAnalysisUsage(AU); 1279 } 1280 1281 bool InlineCostAnalysis::runOnSCC(CallGraphSCC &SCC) { 1282 TTIWP = &getAnalysis<TargetTransformInfoWrapperPass>(); 1283 ACT = &getAnalysis<AssumptionCacheTracker>(); 1284 return false; 1285 } 1286 1287 InlineCost InlineCostAnalysis::getInlineCost(CallSite CS, int Threshold) { 1288 return getInlineCost(CS, CS.getCalledFunction(), Threshold); 1289 } 1290 1291 /// \brief Test that two functions either have or have not the given attribute 1292 /// at the same time. 1293 template<typename AttrKind> 1294 static bool attributeMatches(Function *F1, Function *F2, AttrKind Attr) { 1295 return F1->getFnAttribute(Attr) == F2->getFnAttribute(Attr); 1296 } 1297 1298 /// \brief Test that there are no attribute conflicts between Caller and Callee 1299 /// that prevent inlining. 1300 static bool functionsHaveCompatibleAttributes(Function *Caller, 1301 Function *Callee) { 1302 return attributeMatches(Caller, Callee, "target-cpu") && 1303 attributeMatches(Caller, Callee, "target-features") && 1304 attributeMatches(Caller, Callee, Attribute::SanitizeAddress) && 1305 attributeMatches(Caller, Callee, Attribute::SanitizeMemory) && 1306 attributeMatches(Caller, Callee, Attribute::SanitizeThread); 1307 } 1308 1309 InlineCost InlineCostAnalysis::getInlineCost(CallSite CS, Function *Callee, 1310 int Threshold) { 1311 // Cannot inline indirect calls. 1312 if (!Callee) 1313 return llvm::InlineCost::getNever(); 1314 1315 // Calls to functions with always-inline attributes should be inlined 1316 // whenever possible. 1317 if (CS.hasFnAttr(Attribute::AlwaysInline)) { 1318 if (isInlineViable(*Callee)) 1319 return llvm::InlineCost::getAlways(); 1320 return llvm::InlineCost::getNever(); 1321 } 1322 1323 // Never inline functions with conflicting attributes (unless callee has 1324 // always-inline attribute). 1325 if (!functionsHaveCompatibleAttributes(CS.getCaller(), Callee)) 1326 return llvm::InlineCost::getNever(); 1327 1328 // Don't inline this call if the caller has the optnone attribute. 1329 if (CS.getCaller()->hasFnAttribute(Attribute::OptimizeNone)) 1330 return llvm::InlineCost::getNever(); 1331 1332 // Don't inline functions which can be redefined at link-time to mean 1333 // something else. Don't inline functions marked noinline or call sites 1334 // marked noinline. 1335 if (Callee->mayBeOverridden() || 1336 Callee->hasFnAttribute(Attribute::NoInline) || CS.isNoInline()) 1337 return llvm::InlineCost::getNever(); 1338 1339 DEBUG(llvm::dbgs() << " Analyzing call of " << Callee->getName() 1340 << "...\n"); 1341 1342 CallAnalyzer CA(TTIWP->getTTI(*Callee), ACT, *Callee, Threshold); 1343 bool ShouldInline = CA.analyzeCall(CS); 1344 1345 DEBUG(CA.dump()); 1346 1347 // Check if there was a reason to force inlining or no inlining. 1348 if (!ShouldInline && CA.getCost() < CA.getThreshold()) 1349 return InlineCost::getNever(); 1350 if (ShouldInline && CA.getCost() >= CA.getThreshold()) 1351 return InlineCost::getAlways(); 1352 1353 return llvm::InlineCost::get(CA.getCost(), CA.getThreshold()); 1354 } 1355 1356 bool InlineCostAnalysis::isInlineViable(Function &F) { 1357 bool ReturnsTwice = F.hasFnAttribute(Attribute::ReturnsTwice); 1358 for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE; ++BI) { 1359 // Disallow inlining of functions which contain indirect branches or 1360 // blockaddresses. 1361 if (isa<IndirectBrInst>(BI->getTerminator()) || BI->hasAddressTaken()) 1362 return false; 1363 1364 for (BasicBlock::iterator II = BI->begin(), IE = BI->end(); II != IE; 1365 ++II) { 1366 CallSite CS(II); 1367 if (!CS) 1368 continue; 1369 1370 // Disallow recursive calls. 1371 if (&F == CS.getCalledFunction()) 1372 return false; 1373 1374 // Disallow calls which expose returns-twice to a function not previously 1375 // attributed as such. 1376 if (!ReturnsTwice && CS.isCall() && 1377 cast<CallInst>(CS.getInstruction())->canReturnTwice()) 1378 return false; 1379 1380 // Disallow inlining functions that call @llvm.frameescape. Doing this 1381 // correctly would require major changes to the inliner. 1382 if (CS.getCalledFunction() && 1383 CS.getCalledFunction()->getIntrinsicID() == 1384 llvm::Intrinsic::frameescape) 1385 return false; 1386 } 1387 } 1388 1389 return true; 1390 } 1391