1e4aeec003f82a5263ffb168e175e6fca8b6f681dDan Gohman//===- InlineCost.cpp - Cost analysis for inliner -------------------------===// 2e4aeec003f82a5263ffb168e175e6fca8b6f681dDan Gohman// 3e4aeec003f82a5263ffb168e175e6fca8b6f681dDan Gohman// The LLVM Compiler Infrastructure 4e4aeec003f82a5263ffb168e175e6fca8b6f681dDan Gohman// 5e4aeec003f82a5263ffb168e175e6fca8b6f681dDan Gohman// This file is distributed under the University of Illinois Open Source 6e4aeec003f82a5263ffb168e175e6fca8b6f681dDan Gohman// License. See LICENSE.TXT for details. 7e4aeec003f82a5263ffb168e175e6fca8b6f681dDan Gohman// 8e4aeec003f82a5263ffb168e175e6fca8b6f681dDan Gohman//===----------------------------------------------------------------------===// 9e4aeec003f82a5263ffb168e175e6fca8b6f681dDan Gohman// 10e4aeec003f82a5263ffb168e175e6fca8b6f681dDan Gohman// This file implements inline cost analysis. 11e4aeec003f82a5263ffb168e175e6fca8b6f681dDan Gohman// 12e4aeec003f82a5263ffb168e175e6fca8b6f681dDan Gohman//===----------------------------------------------------------------------===// 13e4aeec003f82a5263ffb168e175e6fca8b6f681dDan Gohman 14f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth#define DEBUG_TYPE "inline-cost" 15e4aeec003f82a5263ffb168e175e6fca8b6f681dDan Gohman#include "llvm/Analysis/InlineCost.h" 16f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth#include "llvm/Analysis/ConstantFolding.h" 17f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth#include "llvm/Analysis/InstructionSimplify.h" 18e4aeec003f82a5263ffb168e175e6fca8b6f681dDan Gohman#include "llvm/Support/CallSite.h" 19f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth#include "llvm/Support/Debug.h" 20f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth#include "llvm/Support/InstVisitor.h" 21f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth#include "llvm/Support/GetElementPtrTypeIterator.h" 22f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth#include "llvm/Support/raw_ostream.h" 23e4aeec003f82a5263ffb168e175e6fca8b6f681dDan Gohman#include "llvm/CallingConv.h" 24e4aeec003f82a5263ffb168e175e6fca8b6f681dDan Gohman#include "llvm/IntrinsicInst.h" 25f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth#include "llvm/Operator.h" 26f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth#include "llvm/GlobalAlias.h" 27b2ab2fa524f3f90376639037bd81924483cca0afAndrew Trick#include "llvm/Target/TargetData.h" 28f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth#include "llvm/ADT/STLExtras.h" 29f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth#include "llvm/ADT/SetVector.h" 30f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth#include "llvm/ADT/SmallVector.h" 31e4aeec003f82a5263ffb168e175e6fca8b6f681dDan Gohman#include "llvm/ADT/SmallPtrSet.h" 32d6fc26217e194372cabe4ef9e2514beac511a943Chandler Carruth#include "llvm/ADT/Statistic.h" 334e8af6db184118638c21f713ad98e3292c6891c9Eric Christopher 34e4aeec003f82a5263ffb168e175e6fca8b6f681dDan Gohmanusing namespace llvm; 35e4aeec003f82a5263ffb168e175e6fca8b6f681dDan Gohman 36d6fc26217e194372cabe4ef9e2514beac511a943Chandler CarruthSTATISTIC(NumCallsAnalyzed, "Number of call sites analyzed"); 37d6fc26217e194372cabe4ef9e2514beac511a943Chandler Carruth 38f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthnamespace { 39f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 40f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthclass CallAnalyzer : public InstVisitor<CallAnalyzer, bool> { 41f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth typedef InstVisitor<CallAnalyzer, bool> Base; 42f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth friend class InstVisitor<CallAnalyzer, bool>; 43f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 44f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // TargetData if available, or null. 45f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth const TargetData *const TD; 46f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 47f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // The called function. 48f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Function &F; 49f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 50f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth int Threshold; 51f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth int Cost; 52f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth const bool AlwaysInline; 53f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 54f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool IsRecursive; 55f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool ExposesReturnsTwice; 56f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool HasDynamicAlloca; 57f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth unsigned NumInstructions, NumVectorInstructions; 58f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth int FiftyPercentVectorBonus, TenPercentVectorBonus; 59f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth int VectorBonus; 60f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 61f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // While we walk the potentially-inlined instructions, we build up and 62f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // maintain a mapping of simplified values specific to this callsite. The 63f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // idea is to propagate any special information we have about arguments to 64f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // this call through the inlinable section of the function, and account for 65f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // likely simplifications post-inlining. The most important aspect we track 66f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // is CFG altering simplifications -- when we prove a basic block dead, that 67f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // can cause dramatic shifts in the cost of inlining a function. 68f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DenseMap<Value *, Constant *> SimplifiedValues; 69f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 70f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Keep track of the values which map back (through function arguments) to 71f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // allocas on the caller stack which could be simplified through SROA. 72f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DenseMap<Value *, Value *> SROAArgValues; 73f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 74f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // The mapping of caller Alloca values to their accumulated cost savings. If 75f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // we have to disable SROA for one of the allocas, this tells us how much 76f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // cost must be added. 77f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DenseMap<Value *, int> SROAArgCosts; 78f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 79f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Keep track of values which map to a pointer base and constant offset. 80f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DenseMap<Value *, std::pair<Value *, APInt> > ConstantOffsetPtrs; 81f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 82f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Custom simplification helper routines. 83f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool isAllocaDerivedArg(Value *V); 84f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool lookupSROAArgAndCost(Value *V, Value *&Arg, 85f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DenseMap<Value *, int>::iterator &CostIt); 86f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth void disableSROA(DenseMap<Value *, int>::iterator CostIt); 87f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth void disableSROA(Value *V); 88f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth void accumulateSROACost(DenseMap<Value *, int>::iterator CostIt, 89f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth int InstructionCost); 90f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool handleSROACandidate(bool IsSROAValid, 91f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DenseMap<Value *, int>::iterator CostIt, 92f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth int InstructionCost); 93f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool isGEPOffsetConstant(GetElementPtrInst &GEP); 94f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool accumulateGEPOffset(GEPOperator &GEP, APInt &Offset); 95f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth ConstantInt *stripAndComputeInBoundsConstantOffsets(Value *&V); 96f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 97f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Custom analysis routines. 98f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool analyzeBlock(BasicBlock *BB); 99f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 100f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Disable several entry points to the visitor so we don't accidentally use 101f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // them by declaring but not defining them here. 102f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth void visit(Module *); void visit(Module &); 103f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth void visit(Function *); void visit(Function &); 104f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth void visit(BasicBlock *); void visit(BasicBlock &); 105f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 106f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Provide base case for our instruction visit. 107f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool visitInstruction(Instruction &I); 108f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 109f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Our visit overrides. 110f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool visitAlloca(AllocaInst &I); 111f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool visitPHI(PHINode &I); 112f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool visitGetElementPtr(GetElementPtrInst &I); 113f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool visitBitCast(BitCastInst &I); 114f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool visitPtrToInt(PtrToIntInst &I); 115f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool visitIntToPtr(IntToPtrInst &I); 116f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool visitCastInst(CastInst &I); 117f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool visitUnaryInstruction(UnaryInstruction &I); 118f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool visitICmp(ICmpInst &I); 119f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool visitSub(BinaryOperator &I); 120f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool visitBinaryOperator(BinaryOperator &I); 121f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool visitLoad(LoadInst &I); 122f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool visitStore(StoreInst &I); 123f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool visitCallSite(CallSite CS); 124f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 125f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthpublic: 126f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth CallAnalyzer(const TargetData *TD, Function &Callee, int Threshold) 127f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth : TD(TD), F(Callee), Threshold(Threshold), Cost(0), 128f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth AlwaysInline(F.hasFnAttr(Attribute::AlwaysInline)), 129f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth IsRecursive(false), ExposesReturnsTwice(false), HasDynamicAlloca(false), 130f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth NumInstructions(0), NumVectorInstructions(0), 131f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth FiftyPercentVectorBonus(0), TenPercentVectorBonus(0), VectorBonus(0), 132f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth NumConstantArgs(0), NumConstantOffsetPtrArgs(0), NumAllocaArgs(0), 133f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth NumConstantPtrCmps(0), NumConstantPtrDiffs(0), 134f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth NumInstructionsSimplified(0), SROACostSavings(0), SROACostSavingsLost(0) { 135f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 1363d1d895c866b76ac4d862301f36e2b95d803f0abChandler Carruth 137f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool analyzeCall(CallSite CS); 138082bf2a977b6bb91d61ac5155e1906ecc6ba47bfOwen Anderson 139f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth int getThreshold() { return Threshold; } 140f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth int getCost() { return Cost; } 141082bf2a977b6bb91d61ac5155e1906ecc6ba47bfOwen Anderson 142f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Keep a bunch of stats about the cost savings found so we can print them 143f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // out when debugging. 144f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth unsigned NumConstantArgs; 145f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth unsigned NumConstantOffsetPtrArgs; 146f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth unsigned NumAllocaArgs; 147f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth unsigned NumConstantPtrCmps; 148f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth unsigned NumConstantPtrDiffs; 149f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth unsigned NumInstructionsSimplified; 150f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth unsigned SROACostSavings; 151f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth unsigned SROACostSavingsLost; 152082bf2a977b6bb91d61ac5155e1906ecc6ba47bfOwen Anderson 153f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth void dump(); 154f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth}; 155082bf2a977b6bb91d61ac5155e1906ecc6ba47bfOwen Anderson 156f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth} // namespace 157e8187e02949571e8a610644762b843ef2891f011Chandler Carruth 158f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// \brief Test whether the given value is an Alloca-derived function argument. 159f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthbool CallAnalyzer::isAllocaDerivedArg(Value *V) { 160f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return SROAArgValues.count(V); 161f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth} 162e8187e02949571e8a610644762b843ef2891f011Chandler Carruth 163f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// \brief Lookup the SROA-candidate argument and cost iterator which V maps to. 164f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// Returns false if V does not map to a SROA-candidate. 165f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthbool CallAnalyzer::lookupSROAArgAndCost( 166f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Value *V, Value *&Arg, DenseMap<Value *, int>::iterator &CostIt) { 167f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (SROAArgValues.empty() || SROAArgCosts.empty()) 168f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return false; 169e8187e02949571e8a610644762b843ef2891f011Chandler Carruth 170f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DenseMap<Value *, Value *>::iterator ArgIt = SROAArgValues.find(V); 171f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (ArgIt == SROAArgValues.end()) 172f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return false; 173e8187e02949571e8a610644762b843ef2891f011Chandler Carruth 174f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Arg = ArgIt->second; 175f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth CostIt = SROAArgCosts.find(Arg); 176f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return CostIt != SROAArgCosts.end(); 177e8187e02949571e8a610644762b843ef2891f011Chandler Carruth} 178e8187e02949571e8a610644762b843ef2891f011Chandler Carruth 179f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// \brief Disable SROA for the candidate marked by this cost iterator. 180e8187e02949571e8a610644762b843ef2891f011Chandler Carruth/// 181f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// This markes the candidate as no longer viable for SROA, and adds the cost 182f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// savings associated with it back into the inline cost measurement. 183f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthvoid CallAnalyzer::disableSROA(DenseMap<Value *, int>::iterator CostIt) { 184f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // If we're no longer able to perform SROA we need to undo its cost savings 185f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // and prevent subsequent analysis. 186f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Cost += CostIt->second; 187f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SROACostSavings -= CostIt->second; 188f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SROACostSavingsLost += CostIt->second; 189f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SROAArgCosts.erase(CostIt); 190f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth} 191f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 192f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// \brief If 'V' maps to a SROA candidate, disable SROA for it. 193f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthvoid CallAnalyzer::disableSROA(Value *V) { 194f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Value *SROAArg; 195f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DenseMap<Value *, int>::iterator CostIt; 196f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (lookupSROAArgAndCost(V, SROAArg, CostIt)) 197f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth disableSROA(CostIt); 198f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth} 199f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 200f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// \brief Accumulate the given cost for a particular SROA candidate. 201f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthvoid CallAnalyzer::accumulateSROACost(DenseMap<Value *, int>::iterator CostIt, 202f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth int InstructionCost) { 203f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth CostIt->second += InstructionCost; 204f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SROACostSavings += InstructionCost; 205f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth} 206f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 207f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// \brief Helper for the common pattern of handling a SROA candidate. 208f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// Either accumulates the cost savings if the SROA remains valid, or disables 209f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// SROA for the candidate. 210f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthbool CallAnalyzer::handleSROACandidate(bool IsSROAValid, 211f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DenseMap<Value *, int>::iterator CostIt, 212f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth int InstructionCost) { 213f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (IsSROAValid) { 214f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth accumulateSROACost(CostIt, InstructionCost); 215e8187e02949571e8a610644762b843ef2891f011Chandler Carruth return true; 216e8187e02949571e8a610644762b843ef2891f011Chandler Carruth } 217e8187e02949571e8a610644762b843ef2891f011Chandler Carruth 218f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth disableSROA(CostIt); 219f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return false; 220f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth} 221f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 222f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// \brief Check whether a GEP's indices are all constant. 223f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// 224f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// Respects any simplified values known during the analysis of this callsite. 225f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthbool CallAnalyzer::isGEPOffsetConstant(GetElementPtrInst &GEP) { 226f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth for (User::op_iterator I = GEP.idx_begin(), E = GEP.idx_end(); I != E; ++I) 227f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (!isa<Constant>(*I) && !SimplifiedValues.lookup(*I)) 228e8187e02949571e8a610644762b843ef2891f011Chandler Carruth return false; 229e8187e02949571e8a610644762b843ef2891f011Chandler Carruth 230f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return true; 231f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth} 232f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 233f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// \brief Accumulate a constant GEP offset into an APInt if possible. 234f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// 235f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// Returns false if unable to compute the offset for any reason. Respects any 236f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// simplified values known during the analysis of this callsite. 237f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthbool CallAnalyzer::accumulateGEPOffset(GEPOperator &GEP, APInt &Offset) { 238f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (!TD) 239f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return false; 240f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 241f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth unsigned IntPtrWidth = TD->getPointerSizeInBits(); 242f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth assert(IntPtrWidth == Offset.getBitWidth()); 243f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 244f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth for (gep_type_iterator GTI = gep_type_begin(GEP), GTE = gep_type_end(GEP); 245f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth GTI != GTE; ++GTI) { 246f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth ConstantInt *OpC = dyn_cast<ConstantInt>(GTI.getOperand()); 247f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (!OpC) 248f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (Constant *SimpleOp = SimplifiedValues.lookup(GTI.getOperand())) 249f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth OpC = dyn_cast<ConstantInt>(SimpleOp); 250f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (!OpC) 251e8187e02949571e8a610644762b843ef2891f011Chandler Carruth return false; 252f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (OpC->isZero()) continue; 253e8187e02949571e8a610644762b843ef2891f011Chandler Carruth 254f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Handle a struct index, which adds its field offset to the pointer. 255f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (StructType *STy = dyn_cast<StructType>(*GTI)) { 256f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth unsigned ElementIdx = OpC->getZExtValue(); 257f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth const StructLayout *SL = TD->getStructLayout(STy); 258f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Offset += APInt(IntPtrWidth, SL->getElementOffset(ElementIdx)); 259f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth continue; 260f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 261f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 262f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth APInt TypeSize(IntPtrWidth, TD->getTypeAllocSize(GTI.getIndexedType())); 263f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Offset += OpC->getValue().sextOrTrunc(IntPtrWidth) * TypeSize; 264e8187e02949571e8a610644762b843ef2891f011Chandler Carruth } 265f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return true; 266f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth} 267f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 268f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthbool CallAnalyzer::visitAlloca(AllocaInst &I) { 269f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // FIXME: Check whether inlining will turn a dynamic alloca into a static 270f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // alloca, and handle that case. 271e8187e02949571e8a610644762b843ef2891f011Chandler Carruth 272f5f256cffd7535d31dc24e7c9166f2084fe66e47Chandler Carruth // We will happily inline static alloca instructions or dynamic alloca 273f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // instructions in always-inline situations. 274f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (AlwaysInline || I.isStaticAlloca()) 275f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return Base::visitAlloca(I); 276f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 277f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // FIXME: This is overly conservative. Dynamic allocas are inefficient for 278f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // a variety of reasons, and so we would like to not inline them into 279f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // functions which don't currently have a dynamic alloca. This simply 280f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // disables inlining altogether in the presence of a dynamic alloca. 281f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth HasDynamicAlloca = true; 282f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return false; 283f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth} 284f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 285f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthbool CallAnalyzer::visitPHI(PHINode &I) { 286f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // FIXME: We should potentially be tracking values through phi nodes, 287f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // especially when they collapse to a single value due to deleted CFG edges 288f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // during inlining. 289f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 290f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // FIXME: We need to propagate SROA *disabling* through phi nodes, even 291f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // though we don't want to propagate it's bonuses. The idea is to disable 292f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // SROA if it *might* be used in an inappropriate manner. 293f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 294f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Phi nodes are always zero-cost. 295f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return true; 296f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth} 297f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 298f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthbool CallAnalyzer::visitGetElementPtr(GetElementPtrInst &I) { 299f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Value *SROAArg; 300f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DenseMap<Value *, int>::iterator CostIt; 301f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool SROACandidate = lookupSROAArgAndCost(I.getPointerOperand(), 302f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SROAArg, CostIt); 303f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 304f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Try to fold GEPs of constant-offset call site argument pointers. This 305f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // requires target data and inbounds GEPs. 306f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (TD && I.isInBounds()) { 307f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Check if we have a base + offset for the pointer. 308f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Value *Ptr = I.getPointerOperand(); 309f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth std::pair<Value *, APInt> BaseAndOffset = ConstantOffsetPtrs.lookup(Ptr); 310f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (BaseAndOffset.first) { 311f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Check if the offset of this GEP is constant, and if so accumulate it 312f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // into Offset. 313f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (!accumulateGEPOffset(cast<GEPOperator>(I), BaseAndOffset.second)) { 314f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Non-constant GEPs aren't folded, and disable SROA. 315f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (SROACandidate) 316f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth disableSROA(CostIt); 317e8187e02949571e8a610644762b843ef2891f011Chandler Carruth return false; 318f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 319f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 320f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Add the result as a new mapping to Base + Offset. 321f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth ConstantOffsetPtrs[&I] = BaseAndOffset; 322f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 323f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Also handle SROA candidates here, we already know that the GEP is 324f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // all-constant indexed. 325f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (SROACandidate) 326f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SROAArgValues[&I] = SROAArg; 327f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 328f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return true; 329e8187e02949571e8a610644762b843ef2891f011Chandler Carruth } 330f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 331f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 332f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (isGEPOffsetConstant(I)) { 333f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (SROACandidate) 334f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SROAArgValues[&I] = SROAArg; 335f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 336f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Constant GEPs are modeled as free. 337e8187e02949571e8a610644762b843ef2891f011Chandler Carruth return true; 338e8187e02949571e8a610644762b843ef2891f011Chandler Carruth } 339e8187e02949571e8a610644762b843ef2891f011Chandler Carruth 340f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Variable GEPs will require math and will disable SROA. 341f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (SROACandidate) 342f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth disableSROA(CostIt); 343f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return false; 344f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth} 345f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 346f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthbool CallAnalyzer::visitBitCast(BitCastInst &I) { 347f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Propagate constants through bitcasts. 348f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (Constant *COp = dyn_cast<Constant>(I.getOperand(0))) 349f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (Constant *C = ConstantExpr::getBitCast(COp, I.getType())) { 350f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SimplifiedValues[&I] = C; 351e8187e02949571e8a610644762b843ef2891f011Chandler Carruth return true; 352e8187e02949571e8a610644762b843ef2891f011Chandler Carruth } 353f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 354f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Track base/offsets through casts 355f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth std::pair<Value *, APInt> BaseAndOffset 356f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth = ConstantOffsetPtrs.lookup(I.getOperand(0)); 357f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Casts don't change the offset, just wrap it up. 358f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (BaseAndOffset.first) 359f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth ConstantOffsetPtrs[&I] = BaseAndOffset; 360f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 361f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Also look for SROA candidates here. 362f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Value *SROAArg; 363f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DenseMap<Value *, int>::iterator CostIt; 364f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt)) 365f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SROAArgValues[&I] = SROAArg; 366f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 367f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Bitcasts are always zero cost. 368f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return true; 369f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth} 370f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 371f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthbool CallAnalyzer::visitPtrToInt(PtrToIntInst &I) { 372f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Propagate constants through ptrtoint. 373f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (Constant *COp = dyn_cast<Constant>(I.getOperand(0))) 374f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (Constant *C = ConstantExpr::getPtrToInt(COp, I.getType())) { 375f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SimplifiedValues[&I] = C; 376f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return true; 377f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 378f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 379f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Track base/offset pairs when converted to a plain integer provided the 380f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // integer is large enough to represent the pointer. 381f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth unsigned IntegerSize = I.getType()->getScalarSizeInBits(); 382f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (TD && IntegerSize >= TD->getPointerSizeInBits()) { 383f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth std::pair<Value *, APInt> BaseAndOffset 384f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth = ConstantOffsetPtrs.lookup(I.getOperand(0)); 385f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (BaseAndOffset.first) 386f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth ConstantOffsetPtrs[&I] = BaseAndOffset; 387e8187e02949571e8a610644762b843ef2891f011Chandler Carruth } 388e8187e02949571e8a610644762b843ef2891f011Chandler Carruth 389f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // This is really weird. Technically, ptrtoint will disable SROA. However, 390f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // unless that ptrtoint is *used* somewhere in the live basic blocks after 391f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // inlining, it will be nuked, and SROA should proceed. All of the uses which 392f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // would block SROA would also block SROA if applied directly to a pointer, 393f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // and so we can just add the integer in here. The only places where SROA is 394f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // preserved either cannot fire on an integer, or won't in-and-of themselves 395f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // disable SROA (ext) w/o some later use that we would see and disable. 396f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Value *SROAArg; 397f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DenseMap<Value *, int>::iterator CostIt; 398f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt)) 399f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SROAArgValues[&I] = SROAArg; 400f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 401f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // A ptrtoint cast is free so long as the result is large enough to store the 402f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // pointer, and a legal integer type. 403f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return TD && TD->isLegalInteger(IntegerSize) && 404f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth IntegerSize >= TD->getPointerSizeInBits(); 405e8187e02949571e8a610644762b843ef2891f011Chandler Carruth} 406e8187e02949571e8a610644762b843ef2891f011Chandler Carruth 407f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthbool CallAnalyzer::visitIntToPtr(IntToPtrInst &I) { 408f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Propagate constants through ptrtoint. 409f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (Constant *COp = dyn_cast<Constant>(I.getOperand(0))) 410f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (Constant *C = ConstantExpr::getIntToPtr(COp, I.getType())) { 411f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SimplifiedValues[&I] = C; 412f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return true; 413f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 4146977e79526a6342b9408c358bca21c3b0c7e61d5Nick Lewycky 415f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Track base/offset pairs when round-tripped through a pointer without 416f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // modifications provided the integer is not too large. 417f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Value *Op = I.getOperand(0); 418f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth unsigned IntegerSize = Op->getType()->getScalarSizeInBits(); 419f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (TD && IntegerSize <= TD->getPointerSizeInBits()) { 420f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth std::pair<Value *, APInt> BaseAndOffset = ConstantOffsetPtrs.lookup(Op); 421f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (BaseAndOffset.first) 422f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth ConstantOffsetPtrs[&I] = BaseAndOffset; 423f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 424e8187e02949571e8a610644762b843ef2891f011Chandler Carruth 425f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // "Propagate" SROA here in the same manner as we do for ptrtoint above. 426f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Value *SROAArg; 427f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DenseMap<Value *, int>::iterator CostIt; 428f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (lookupSROAArgAndCost(Op, SROAArg, CostIt)) 429f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SROAArgValues[&I] = SROAArg; 430e8187e02949571e8a610644762b843ef2891f011Chandler Carruth 431f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // An inttoptr cast is free so long as the input is a legal integer type 432f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // which doesn't contain values outside the range of a pointer. 433f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return TD && TD->isLegalInteger(IntegerSize) && 434f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth IntegerSize <= TD->getPointerSizeInBits(); 435f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth} 436f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 437f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthbool CallAnalyzer::visitCastInst(CastInst &I) { 438f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Propagate constants through ptrtoint. 439f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (Constant *COp = dyn_cast<Constant>(I.getOperand(0))) 440f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (Constant *C = ConstantExpr::getCast(I.getOpcode(), COp, I.getType())) { 441f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SimplifiedValues[&I] = C; 442f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return true; 443082bf2a977b6bb91d61ac5155e1906ecc6ba47bfOwen Anderson } 444082bf2a977b6bb91d61ac5155e1906ecc6ba47bfOwen Anderson 445f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Disable SROA in the face of arbitrary casts we don't whitelist elsewhere. 446f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth disableSROA(I.getOperand(0)); 447f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 448f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // No-op casts don't have any cost. 449f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (I.isLosslessCast()) 450f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return true; 451f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 452f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // trunc to a native type is free (assuming the target has compare and 453f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // shift-right of the same width). 454f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (TD && isa<TruncInst>(I) && 455f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth TD->isLegalInteger(TD->getTypeSizeInBits(I.getType()))) 456f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return true; 457f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 458f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Result of a cmp instruction is often extended (to be used by other 459f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // cmp instructions, logical or return instructions). These are usually 460f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // no-ops on most sane targets. 461f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (isa<CmpInst>(I.getOperand(0))) 462f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return true; 463f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 464f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Assume the rest of the casts require work. 465f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return false; 466082bf2a977b6bb91d61ac5155e1906ecc6ba47bfOwen Anderson} 467082bf2a977b6bb91d61ac5155e1906ecc6ba47bfOwen Anderson 468f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthbool CallAnalyzer::visitUnaryInstruction(UnaryInstruction &I) { 469f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Value *Operand = I.getOperand(0); 470f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Constant *Ops[1] = { dyn_cast<Constant>(Operand) }; 471f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (Ops[0] || (Ops[0] = SimplifiedValues.lookup(Operand))) 472f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (Constant *C = ConstantFoldInstOperands(I.getOpcode(), I.getType(), 473f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Ops, TD)) { 474f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SimplifiedValues[&I] = C; 475f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return true; 476f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 477274d377ea68195989c3238fe96ce2ca812a12fafChandler Carruth 478f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Disable any SROA on the argument to arbitrary unary operators. 479f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth disableSROA(Operand); 480f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 481f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return false; 482f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth} 483f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 484f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthbool CallAnalyzer::visitICmp(ICmpInst &I) { 485f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); 486f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // First try to handle simplified comparisons. 487f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (!isa<Constant>(LHS)) 488f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (Constant *SimpleLHS = SimplifiedValues.lookup(LHS)) 489f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth LHS = SimpleLHS; 490f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (!isa<Constant>(RHS)) 491f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (Constant *SimpleRHS = SimplifiedValues.lookup(RHS)) 492f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth RHS = SimpleRHS; 493f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (Constant *CLHS = dyn_cast<Constant>(LHS)) 494f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (Constant *CRHS = dyn_cast<Constant>(RHS)) 495f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (Constant *C = ConstantExpr::getICmp(I.getPredicate(), CLHS, CRHS)) { 496f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SimplifiedValues[&I] = C; 497f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return true; 498274d377ea68195989c3238fe96ce2ca812a12fafChandler Carruth } 499274d377ea68195989c3238fe96ce2ca812a12fafChandler Carruth 500f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Otherwise look for a comparison between constant offset pointers with 501f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // a common base. 502f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Value *LHSBase, *RHSBase; 503f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth APInt LHSOffset, RHSOffset; 504f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth llvm::tie(LHSBase, LHSOffset) = ConstantOffsetPtrs.lookup(LHS); 505f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (LHSBase) { 506f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth llvm::tie(RHSBase, RHSOffset) = ConstantOffsetPtrs.lookup(RHS); 507f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (RHSBase && LHSBase == RHSBase) { 508f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // We have common bases, fold the icmp to a constant based on the 509f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // offsets. 510f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Constant *CLHS = ConstantInt::get(LHS->getContext(), LHSOffset); 511f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Constant *CRHS = ConstantInt::get(RHS->getContext(), RHSOffset); 512f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (Constant *C = ConstantExpr::getICmp(I.getPredicate(), CLHS, CRHS)) { 513f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SimplifiedValues[&I] = C; 514f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth ++NumConstantPtrCmps; 515f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return true; 516274d377ea68195989c3238fe96ce2ca812a12fafChandler Carruth } 517f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 518f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 519274d377ea68195989c3238fe96ce2ca812a12fafChandler Carruth 520f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // If the comparison is an equality comparison with null, we can simplify it 521f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // for any alloca-derived argument. 522f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (I.isEquality() && isa<ConstantPointerNull>(I.getOperand(1))) 523f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (isAllocaDerivedArg(I.getOperand(0))) { 524f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // We can actually predict the result of comparisons between an 525f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // alloca-derived value and null. Note that this fires regardless of 526f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // SROA firing. 527f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool IsNotEqual = I.getPredicate() == CmpInst::ICMP_NE; 528f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SimplifiedValues[&I] = IsNotEqual ? ConstantInt::getTrue(I.getType()) 529f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth : ConstantInt::getFalse(I.getType()); 530f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return true; 531f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 532274d377ea68195989c3238fe96ce2ca812a12fafChandler Carruth 533f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Finally check for SROA candidates in comparisons. 534f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Value *SROAArg; 535f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DenseMap<Value *, int>::iterator CostIt; 536f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt)) { 537f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (isa<ConstantPointerNull>(I.getOperand(1))) { 538f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth accumulateSROACost(CostIt, InlineConstants::InstrCost); 539f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return true; 540274d377ea68195989c3238fe96ce2ca812a12fafChandler Carruth } 541274d377ea68195989c3238fe96ce2ca812a12fafChandler Carruth 542f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth disableSROA(CostIt); 543274d377ea68195989c3238fe96ce2ca812a12fafChandler Carruth } 544e4aeec003f82a5263ffb168e175e6fca8b6f681dDan Gohman 545f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return false; 54642c7d23c6d56e0743169d94025264eaf17eb799dKenneth Uildriks} 54774fa7327d690e6ceda6ce77e4e5b8ef75cb12538Kenneth Uildriks 548f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthbool CallAnalyzer::visitSub(BinaryOperator &I) { 549f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Try to handle a special case: we can fold computing the difference of two 550f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // constant-related pointers. 551f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); 552f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Value *LHSBase, *RHSBase; 553f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth APInt LHSOffset, RHSOffset; 554f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth llvm::tie(LHSBase, LHSOffset) = ConstantOffsetPtrs.lookup(LHS); 555f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (LHSBase) { 556f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth llvm::tie(RHSBase, RHSOffset) = ConstantOffsetPtrs.lookup(RHS); 557f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (RHSBase && LHSBase == RHSBase) { 558f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // We have common bases, fold the subtract to a constant based on the 559f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // offsets. 560f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Constant *CLHS = ConstantInt::get(LHS->getContext(), LHSOffset); 561f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Constant *CRHS = ConstantInt::get(RHS->getContext(), RHSOffset); 562f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (Constant *C = ConstantExpr::getSub(CLHS, CRHS)) { 563f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SimplifiedValues[&I] = C; 564f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth ++NumConstantPtrDiffs; 565f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return true; 566f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 567f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 568f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 5695c655413cf9466c29e38204ab3f19b33fffd7996Andrew Trick 570f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Otherwise, fall back to the generic logic for simplifying and handling 571f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // instructions. 572f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return Base::visitSub(I); 573f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth} 574f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 575f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthbool CallAnalyzer::visitBinaryOperator(BinaryOperator &I) { 576f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); 577f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (!isa<Constant>(LHS)) 578f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (Constant *SimpleLHS = SimplifiedValues.lookup(LHS)) 579f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth LHS = SimpleLHS; 580f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (!isa<Constant>(RHS)) 581f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (Constant *SimpleRHS = SimplifiedValues.lookup(RHS)) 582f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth RHS = SimpleRHS; 583f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Value *SimpleV = SimplifyBinOp(I.getOpcode(), LHS, RHS, TD); 584f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (Constant *C = dyn_cast_or_null<Constant>(SimpleV)) { 585f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SimplifiedValues[&I] = C; 586f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return true; 587f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 5885c655413cf9466c29e38204ab3f19b33fffd7996Andrew Trick 589f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Disable any SROA on arguments to arbitrary, unsimplified binary operators. 590f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth disableSROA(LHS); 591f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth disableSROA(RHS); 5925c655413cf9466c29e38204ab3f19b33fffd7996Andrew Trick 593f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return false; 5944e8af6db184118638c21f713ad98e3292c6891c9Eric Christopher} 5954e8af6db184118638c21f713ad98e3292c6891c9Eric Christopher 596f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthbool CallAnalyzer::visitLoad(LoadInst &I) { 597f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Value *SROAArg; 598f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DenseMap<Value *, int>::iterator CostIt; 599f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt)) { 600f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (I.isSimple()) { 601f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth accumulateSROACost(CostIt, InlineConstants::InstrCost); 602f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return true; 6038e2da0ce9d70606e10889d17f481842586132d88Eric Christopher } 6048e2da0ce9d70606e10889d17f481842586132d88Eric Christopher 605f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth disableSROA(CostIt); 606f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 6078e2da0ce9d70606e10889d17f481842586132d88Eric Christopher 608f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return false; 609f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth} 610f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 611f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthbool CallAnalyzer::visitStore(StoreInst &I) { 612f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Value *SROAArg; 613f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DenseMap<Value *, int>::iterator CostIt; 614f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt)) { 615f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (I.isSimple()) { 616f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth accumulateSROACost(CostIt, InlineConstants::InstrCost); 617f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return true; 6188e2da0ce9d70606e10889d17f481842586132d88Eric Christopher } 619f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 620f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth disableSROA(CostIt); 6218e2da0ce9d70606e10889d17f481842586132d88Eric Christopher } 6225c655413cf9466c29e38204ab3f19b33fffd7996Andrew Trick 623f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return false; 6244e8af6db184118638c21f713ad98e3292c6891c9Eric Christopher} 6254e8af6db184118638c21f713ad98e3292c6891c9Eric Christopher 626f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthbool CallAnalyzer::visitCallSite(CallSite CS) { 627f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (CS.isCall() && cast<CallInst>(CS.getInstruction())->canReturnTwice() && 628f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth !F.hasFnAttr(Attribute::ReturnsTwice)) { 629f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // This aborts the entire analysis. 630f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth ExposesReturnsTwice = true; 631f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return false; 6324e8af6db184118638c21f713ad98e3292c6891c9Eric Christopher } 6335c655413cf9466c29e38204ab3f19b33fffd7996Andrew Trick 634f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction())) { 635f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth switch (II->getIntrinsicID()) { 636f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth default: 637f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return Base::visitCallSite(CS); 638274d377ea68195989c3238fe96ce2ca812a12fafChandler Carruth 639f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth case Intrinsic::dbg_declare: 640f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth case Intrinsic::dbg_value: 641f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth case Intrinsic::invariant_start: 642f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth case Intrinsic::invariant_end: 643f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth case Intrinsic::lifetime_start: 644f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth case Intrinsic::lifetime_end: 645f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth case Intrinsic::memset: 646f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth case Intrinsic::memcpy: 647f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth case Intrinsic::memmove: 648f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth case Intrinsic::objectsize: 649f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth case Intrinsic::ptr_annotation: 650f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth case Intrinsic::var_annotation: 651f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // SROA can usually chew through these intrinsics and they have no cost 652f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // so don't pay the price of analyzing them in detail. 653f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return true; 654f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 655f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 6564e8af6db184118638c21f713ad98e3292c6891c9Eric Christopher 657f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (Function *F = CS.getCalledFunction()) { 658f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (F == CS.getInstruction()->getParent()->getParent()) { 659f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // This flag will fully abort the analysis, so don't bother with anything 660f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // else. 661f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth IsRecursive = true; 662f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return false; 663f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 6644e8af6db184118638c21f713ad98e3292c6891c9Eric Christopher 665f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (!callIsSmall(F)) { 666f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // We account for the average 1 instruction per call argument setup 667f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // here. 668f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Cost += CS.arg_size() * InlineConstants::InstrCost; 6694e8af6db184118638c21f713ad98e3292c6891c9Eric Christopher 670f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Everything other than inline ASM will also have a significant cost 671f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // merely from making the call. 672f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (!isa<InlineAsm>(CS.getCalledValue())) 673f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Cost += InlineConstants::CallPenalty; 674f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 6755c655413cf9466c29e38204ab3f19b33fffd7996Andrew Trick 676f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return Base::visitCallSite(CS); 677f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 678f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 679f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Otherwise we're in a very special case -- an indirect function call. See 680f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // if we can be particularly clever about this. 681f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Value *Callee = CS.getCalledValue(); 682f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 683f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // First, pay the price of the argument setup. We account for the average 684f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // 1 instruction per call argument setup here. 685f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Cost += CS.arg_size() * InlineConstants::InstrCost; 686f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 687f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Next, check if this happens to be an indirect function call to a known 688f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // function in this inline context. If not, we've done all we can. 689f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Function *F = dyn_cast_or_null<Function>(SimplifiedValues.lookup(Callee)); 690f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (!F) 691f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return Base::visitCallSite(CS); 692f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 693f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // If we have a constant that we are calling as a function, we can peer 694f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // through it and see the function target. This happens not infrequently 695f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // during devirtualization and so we want to give it a hefty bonus for 696f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // inlining, but cap that bonus in the event that inlining wouldn't pan 697f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // out. Pretend to inline the function, with a custom threshold. 698f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth CallAnalyzer CA(TD, *F, InlineConstants::IndirectCallThreshold); 699f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (CA.analyzeCall(CS)) { 700f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // We were able to inline the indirect call! Subtract the cost from the 701f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // bonus we want to apply, but don't go below zero. 702f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Cost -= std::max(0, InlineConstants::IndirectCallThreshold - CA.getCost()); 703f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 704f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 705f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return Base::visitCallSite(CS); 7064e8af6db184118638c21f713ad98e3292c6891c9Eric Christopher} 7074e8af6db184118638c21f713ad98e3292c6891c9Eric Christopher 708f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthbool CallAnalyzer::visitInstruction(Instruction &I) { 709f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // We found something we don't understand or can't handle. Mark any SROA-able 710f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // values in the operand list as no longer viable. 711f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth for (User::op_iterator OI = I.op_begin(), OE = I.op_end(); OI != OE; ++OI) 712f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth disableSROA(*OI); 713f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 714f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return false; 7158e2da0ce9d70606e10889d17f481842586132d88Eric Christopher} 71674fa7327d690e6ceda6ce77e4e5b8ef75cb12538Kenneth Uildriks 717f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 718f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// \brief Analyze a basic block for its contribution to the inline cost. 719f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// 720f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// This method walks the analyzer over every instruction in the given basic 721f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// block and accounts for their cost during inlining at this callsite. It 722f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// aborts early if the threshold has been exceeded or an impossible to inline 723f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// construct has been detected. It returns false if inlining is no longer 724f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// viable, and true if inlining remains viable. 725f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthbool CallAnalyzer::analyzeBlock(BasicBlock *BB) { 726f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth for (BasicBlock::iterator I = BB->begin(), E = llvm::prior(BB->end()); 727f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth I != E; ++I) { 728f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth ++NumInstructions; 729f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (isa<ExtractElementInst>(I) || I->getType()->isVectorTy()) 730f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth ++NumVectorInstructions; 731f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 732f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // If the instruction simplified to a constant, there is no cost to this 733f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // instruction. Visit the instructions using our InstVisitor to account for 734f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // all of the per-instruction logic. The visit tree returns true if we 735f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // consumed the instruction in any way, and false if the instruction's base 736f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // cost should count against inlining. 737f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (Base::visit(I)) 738f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth ++NumInstructionsSimplified; 739f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth else 740f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Cost += InlineConstants::InstrCost; 741f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 742f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // If the visit this instruction detected an uninlinable pattern, abort. 743f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (IsRecursive || ExposesReturnsTwice || HasDynamicAlloca) 744f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return false; 745f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 746f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (NumVectorInstructions > NumInstructions/2) 747f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth VectorBonus = FiftyPercentVectorBonus; 748f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth else if (NumVectorInstructions > NumInstructions/10) 749f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth VectorBonus = TenPercentVectorBonus; 750f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth else 751f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth VectorBonus = 0; 752f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 753f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Check if we've past the threshold so we don't spin in huge basic 754f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // blocks that will never inline. 755f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (!AlwaysInline && Cost > (Threshold + VectorBonus)) 756f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return false; 757f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 758f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 759f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return true; 760752e2590585227f6f10e80978f587915d9adb2adDavid Chisnall} 761752e2590585227f6f10e80978f587915d9adb2adDavid Chisnall 762f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// \brief Compute the base pointer and cumulative constant offsets for V. 763f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// 764f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// This strips all constant offsets off of V, leaving it the base pointer, and 765f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// accumulates the total constant offset applied in the returned constant. It 766f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// returns 0 if V is not a pointer, and returns the constant '0' if there are 767f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// no constant offsets applied. 768f2286b0152f0b942e82d8e809186e5cc0d247131Chandler CarruthConstantInt *CallAnalyzer::stripAndComputeInBoundsConstantOffsets(Value *&V) { 769f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (!TD || !V->getType()->isPointerTy()) 770f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return 0; 771f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 772f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth unsigned IntPtrWidth = TD->getPointerSizeInBits(); 773f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth APInt Offset = APInt::getNullValue(IntPtrWidth); 774f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 775f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Even though we don't look through PHI nodes, we could be called on an 776f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // instruction in an unreachable block, which may be on a cycle. 777f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SmallPtrSet<Value *, 4> Visited; 778f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Visited.insert(V); 779f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth do { 780f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) { 781f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (!GEP->isInBounds() || !accumulateGEPOffset(*GEP, Offset)) 782f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return 0; 783f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth V = GEP->getPointerOperand(); 784f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } else if (Operator::getOpcode(V) == Instruction::BitCast) { 785f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth V = cast<Operator>(V)->getOperand(0); 786f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) { 787f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (GA->mayBeOverridden()) 788f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth break; 789f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth V = GA->getAliasee(); 790f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } else { 791f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth break; 792f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 793f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth assert(V->getType()->isPointerTy() && "Unexpected operand type!"); 794f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } while (Visited.insert(V)); 795e4aeec003f82a5263ffb168e175e6fca8b6f681dDan Gohman 796f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Type *IntPtrTy = TD->getIntPtrType(V->getContext()); 797f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return cast<ConstantInt>(ConstantInt::get(IntPtrTy, Offset)); 798f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth} 799e4aeec003f82a5263ffb168e175e6fca8b6f681dDan Gohman 800f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// \brief Analyze a call site for potential inlining. 801f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// 802f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// Returns true if inlining this call is viable, and false if it is not 803f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// viable. It computes the cost and adjusts the threshold based on numerous 804f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// factors and heuristics. If this method returns false but the computed cost 805f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// is below the computed threshold, then inlining was forcibly disabled by 806f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// some artifact of the rountine. 807f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthbool CallAnalyzer::analyzeCall(CallSite CS) { 808d6fc26217e194372cabe4ef9e2514beac511a943Chandler Carruth ++NumCallsAnalyzed; 809d6fc26217e194372cabe4ef9e2514beac511a943Chandler Carruth 810f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Track whether the post-inlining function would have more than one basic 811f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // block. A single basic block is often intended for inlining. Balloon the 812f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // threshold by 50% until we pass the single-BB phase. 813f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool SingleBB = true; 814f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth int SingleBBBonus = Threshold / 2; 815f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Threshold += SingleBBBonus; 816f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 817f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Unless we are always-inlining, perform some tweaks to the cost and 818f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // threshold based on the direct callsite information. 819f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (!AlwaysInline) { 820f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // We want to more aggressively inline vector-dense kernels, so up the 821f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // threshold, and we'll lower it if the % of vector instructions gets too 822f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // low. 823f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth assert(NumInstructions == 0); 824f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth assert(NumVectorInstructions == 0); 825f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth FiftyPercentVectorBonus = Threshold; 826f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth TenPercentVectorBonus = Threshold / 2; 827f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 828f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Subtract off one instruction per call argument as those will be free after 829f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // inlining. 830f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Cost -= CS.arg_size() * InlineConstants::InstrCost; 831f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 832f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // If there is only one call of the function, and it has internal linkage, 833f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // the cost of inlining it drops dramatically. 834f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (F.hasLocalLinkage() && F.hasOneUse() && &F == CS.getCalledFunction()) 835f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Cost += InlineConstants::LastCallToStaticBonus; 836f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 837f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // If the instruction after the call, or if the normal destination of the 838f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // invoke is an unreachable instruction, the function is noreturn. As such, 839f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // there is little point in inlining this unless there is literally zero cost. 840f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (InvokeInst *II = dyn_cast<InvokeInst>(CS.getInstruction())) { 841f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (isa<UnreachableInst>(II->getNormalDest()->begin())) 842f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Threshold = 1; 843f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } else if (isa<UnreachableInst>(++BasicBlock::iterator(CS.getInstruction()))) 844f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Threshold = 1; 845f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 846f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // If this function uses the coldcc calling convention, prefer not to inline 847f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // it. 848f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (F.getCallingConv() == CallingConv::Cold) 849f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Cost += InlineConstants::ColdccPenalty; 850f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 851f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Check if we're done. This can happen due to bonuses and penalties. 852f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (Cost > Threshold) 853f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return false; 854f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 8555c655413cf9466c29e38204ab3f19b33fffd7996Andrew Trick 856f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (F.empty()) 857f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return true; 858e4aeec003f82a5263ffb168e175e6fca8b6f681dDan Gohman 859f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Track whether we've seen a return instruction. The first return 860f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // instruction is free, as at least one will usually disappear in inlining. 861f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool HasReturn = false; 862f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 863f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Populate our simplified values by mapping from function arguments to call 864f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // arguments with known important simplifications. 865f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth CallSite::arg_iterator CAI = CS.arg_begin(); 866f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth for (Function::arg_iterator FAI = F.arg_begin(), FAE = F.arg_end(); 867f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth FAI != FAE; ++FAI, ++CAI) { 868f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth assert(CAI != CS.arg_end()); 869f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (Constant *C = dyn_cast<Constant>(CAI)) 870f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SimplifiedValues[FAI] = C; 871f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 872f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Value *PtrArg = *CAI; 873f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (ConstantInt *C = stripAndComputeInBoundsConstantOffsets(PtrArg)) { 874f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth ConstantOffsetPtrs[FAI] = std::make_pair(PtrArg, C->getValue()); 875f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 876f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // We can SROA any pointer arguments derived from alloca instructions. 877f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (isa<AllocaInst>(PtrArg)) { 878f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SROAArgValues[FAI] = PtrArg; 879f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SROAArgCosts[PtrArg] = 0; 880f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 881f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 882f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 883f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth NumConstantArgs = SimplifiedValues.size(); 884f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth NumConstantOffsetPtrArgs = ConstantOffsetPtrs.size(); 885f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth NumAllocaArgs = SROAArgValues.size(); 886f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 887f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // The worklist of live basic blocks in the callee *after* inlining. We avoid 888f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // adding basic blocks of the callee which can be proven to be dead for this 889f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // particular call site in order to get more accurate cost estimates. This 890f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // requires a somewhat heavyweight iteration pattern: we need to walk the 891f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // basic blocks in a breadth-first order as we insert live successors. To 892f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // accomplish this, prioritizing for small iterations because we exit after 893f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // crossing our threshold, we use a small-size optimized SetVector. 894f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth typedef SetVector<BasicBlock *, SmallVector<BasicBlock *, 16>, 895f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SmallPtrSet<BasicBlock *, 16> > BBSetVector; 896f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth BBSetVector BBWorklist; 897f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth BBWorklist.insert(&F.getEntryBlock()); 898f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Note that we *must not* cache the size, this loop grows the worklist. 899f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth for (unsigned Idx = 0; Idx != BBWorklist.size(); ++Idx) { 900f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Bail out the moment we cross the threshold. This means we'll under-count 901f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // the cost, but only when undercounting doesn't matter. 902f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (!AlwaysInline && Cost > (Threshold + VectorBonus)) 903f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth break; 904f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 905f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth BasicBlock *BB = BBWorklist[Idx]; 906f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (BB->empty()) 907f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth continue; 908e4aeec003f82a5263ffb168e175e6fca8b6f681dDan Gohman 909f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Handle the terminator cost here where we can track returns and other 910f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // function-wide constructs. 911f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth TerminatorInst *TI = BB->getTerminator(); 912f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 913f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // We never want to inline functions that contain an indirectbr. This is 914f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // incorrect because all the blockaddress's (in static global initializers 915f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // for example) would be referring to the original function, and this indirect 916f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // jump would jump from the inlined copy of the function into the original 917f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // function which is extremely undefined behavior. 918f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // FIXME: This logic isn't really right; we can safely inline functions 919f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // with indirectbr's as long as no other function or global references the 920f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // blockaddress of a block within the current function. And as a QOI issue, 921f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // if someone is using a blockaddress without an indirectbr, and that 922f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // reference somehow ends up in another function or global, we probably 923f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // don't want to inline this function. 924f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (isa<IndirectBrInst>(TI)) 925f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return false; 9265c655413cf9466c29e38204ab3f19b33fffd7996Andrew Trick 927f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (!HasReturn && isa<ReturnInst>(TI)) 928f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth HasReturn = true; 929f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth else 930f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Cost += InlineConstants::InstrCost; 931e4aeec003f82a5263ffb168e175e6fca8b6f681dDan Gohman 932f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Analyze the cost of this block. If we blow through the threshold, this 933f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // returns false, and we can bail on out. 934f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (!analyzeBlock(BB)) { 935f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (IsRecursive || ExposesReturnsTwice || HasDynamicAlloca) 936f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return false; 937f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth break; 938f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 9395c655413cf9466c29e38204ab3f19b33fffd7996Andrew Trick 940f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Add in the live successors by first checking whether we have terminator 941f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // that may be simplified based on the values simplified by this call. 942f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 943f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (BI->isConditional()) { 944f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Value *Cond = BI->getCondition(); 945f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (ConstantInt *SimpleCond 946f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth = dyn_cast_or_null<ConstantInt>(SimplifiedValues.lookup(Cond))) { 947f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth BBWorklist.insert(BI->getSuccessor(SimpleCond->isZero() ? 1 : 0)); 948f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth continue; 949f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 950f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 951f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 952f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Value *Cond = SI->getCondition(); 953f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (ConstantInt *SimpleCond 954f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth = dyn_cast_or_null<ConstantInt>(SimplifiedValues.lookup(Cond))) { 955f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth BBWorklist.insert(SI->findCaseValue(SimpleCond).getCaseSuccessor()); 956f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth continue; 957f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 958f84755b8360d13b1d19df821d9e8692aac7e9b87Chris Lattner } 959e4aeec003f82a5263ffb168e175e6fca8b6f681dDan Gohman 960f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // If we're unable to select a particular successor, just count all of 961f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // them. 962f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth for (unsigned TIdx = 0, TSize = TI->getNumSuccessors(); TIdx != TSize; ++TIdx) 963f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth BBWorklist.insert(TI->getSuccessor(TIdx)); 964f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 965f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // If we had any successors at this point, than post-inlining is likely to 966f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // have them as well. Note that we assume any basic blocks which existed 967f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // due to branches or switches which folded above will also fold after 968f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // inlining. 969f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (SingleBB && TI->getNumSuccessors() > 1) { 970f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Take off the bonus we applied to the threshold. 971f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Threshold -= SingleBBBonus; 972f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SingleBB = false; 973f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 974e4aeec003f82a5263ffb168e175e6fca8b6f681dDan Gohman } 975e4aeec003f82a5263ffb168e175e6fca8b6f681dDan Gohman 976f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Threshold += VectorBonus; 977e4aeec003f82a5263ffb168e175e6fca8b6f681dDan Gohman 978f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return AlwaysInline || Cost < Threshold; 979f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth} 9805c655413cf9466c29e38204ab3f19b33fffd7996Andrew Trick 981f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// \brief Dump stats about this call's analysis. 982f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthvoid CallAnalyzer::dump() { 983f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth#define DEBUG_PRINT_STAT(x) llvm::dbgs() << " " #x ": " << x << "\n" 984f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DEBUG_PRINT_STAT(NumConstantArgs); 985f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DEBUG_PRINT_STAT(NumConstantOffsetPtrArgs); 986f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DEBUG_PRINT_STAT(NumAllocaArgs); 987f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DEBUG_PRINT_STAT(NumConstantPtrCmps); 988f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DEBUG_PRINT_STAT(NumConstantPtrDiffs); 989f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DEBUG_PRINT_STAT(NumInstructionsSimplified); 990f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DEBUG_PRINT_STAT(SROACostSavings); 991f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DEBUG_PRINT_STAT(SROACostSavingsLost); 992f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth#undef DEBUG_PRINT_STAT 993e4aeec003f82a5263ffb168e175e6fca8b6f681dDan Gohman} 994f7477470d37ee2ab9075eaee4745fa084d424ab8Jakob Stoklund Olesen 995f2286b0152f0b942e82d8e809186e5cc0d247131Chandler CarruthInlineCost InlineCostAnalyzer::getInlineCost(CallSite CS, int Threshold) { 996b381578fcb5fea988f661dbbee9747b8fd55c5fbDavid Chisnall return getInlineCost(CS, CS.getCalledFunction(), Threshold); 997b381578fcb5fea988f661dbbee9747b8fd55c5fbDavid Chisnall} 998f7477470d37ee2ab9075eaee4745fa084d424ab8Jakob Stoklund Olesen 999b381578fcb5fea988f661dbbee9747b8fd55c5fbDavid ChisnallInlineCost InlineCostAnalyzer::getInlineCost(CallSite CS, Function *Callee, 1000b381578fcb5fea988f661dbbee9747b8fd55c5fbDavid Chisnall int Threshold) { 1001f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Don't inline functions which can be redefined at link-time to mean 1002f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // something else. Don't inline functions marked noinline or call sites 1003f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // marked noinline. 1004f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (!Callee || Callee->mayBeOverridden() || 1005f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Callee->hasFnAttr(Attribute::NoInline) || CS.isNoInline()) 1006f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return llvm::InlineCost::getNever(); 1007f7477470d37ee2ab9075eaee4745fa084d424ab8Jakob Stoklund Olesen 1008f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DEBUG(llvm::dbgs() << " Analyzing call of " << Callee->getName() << "...\n"); 100944b04a5f4ac8a2b9b3208a937f2ba36bcf7aa40fChris Lattner 1010f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth CallAnalyzer CA(TD, *Callee, Threshold); 1011f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool ShouldInline = CA.analyzeCall(CS); 10125c655413cf9466c29e38204ab3f19b33fffd7996Andrew Trick 1013f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DEBUG(CA.dump()); 101444b04a5f4ac8a2b9b3208a937f2ba36bcf7aa40fChris Lattner 1015f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Check if there was a reason to force inlining or no inlining. 1016f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (!ShouldInline && CA.getCost() < CA.getThreshold()) 1017f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return InlineCost::getNever(); 1018f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (ShouldInline && CA.getCost() >= CA.getThreshold()) 1019f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return InlineCost::getAlways(); 10205c655413cf9466c29e38204ab3f19b33fffd7996Andrew Trick 1021f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return llvm::InlineCost::get(CA.getCost(), CA.getThreshold()); 1022f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth} 1023