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" 16d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/STLExtras.h" 17d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/SetVector.h" 18d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/SmallPtrSet.h" 19d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/SmallVector.h" 20d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/Statistic.h" 21f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth#include "llvm/Analysis/ConstantFolding.h" 22f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth#include "llvm/Analysis/InstructionSimplify.h" 238d6c0f4deeb0f2ff671df7ae92b75ee1e39acd37Chandler Carruth#include "llvm/Analysis/TargetTransformInfo.h" 240b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/CallingConv.h" 250b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/DataLayout.h" 260b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/GlobalAlias.h" 270b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/IntrinsicInst.h" 280b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Operator.h" 2984bcf93e0fd225de2217d1b712c01586a633a6d8Chandler Carruth#include "llvm/InstVisitor.h" 30d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Support/CallSite.h" 31d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Support/Debug.h" 32d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Support/GetElementPtrTypeIterator.h" 33d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Support/raw_ostream.h" 344e8af6db184118638c21f713ad98e3292c6891c9Eric Christopher 35e4aeec003f82a5263ffb168e175e6fca8b6f681dDan Gohmanusing namespace llvm; 36e4aeec003f82a5263ffb168e175e6fca8b6f681dDan Gohman 37d6fc26217e194372cabe4ef9e2514beac511a943Chandler CarruthSTATISTIC(NumCallsAnalyzed, "Number of call sites analyzed"); 38d6fc26217e194372cabe4ef9e2514beac511a943Chandler Carruth 39f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthnamespace { 40f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 41f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthclass CallAnalyzer : public InstVisitor<CallAnalyzer, bool> { 42f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth typedef InstVisitor<CallAnalyzer, bool> Base; 43f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth friend class InstVisitor<CallAnalyzer, bool>; 44f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 453574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow // DataLayout if available, or null. 463574eca1b02600bac4e625297f4ecf745f4c4f32Micah Villmow const DataLayout *const TD; 47f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 488d6c0f4deeb0f2ff671df7ae92b75ee1e39acd37Chandler Carruth /// The TargetTransformInfo available for this compilation. 498d6c0f4deeb0f2ff671df7ae92b75ee1e39acd37Chandler Carruth const TargetTransformInfo &TTI; 508d6c0f4deeb0f2ff671df7ae92b75ee1e39acd37Chandler Carruth 51f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // The called function. 52f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Function &F; 53f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 54f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth int Threshold; 55f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth int Cost; 56f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 5792df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem bool IsCallerRecursive; 5892df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem bool IsRecursiveCall; 59f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool ExposesReturnsTwice; 60f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool HasDynamicAlloca; 6167ae13575900e8efd056672987249fd0adbf5e73James Molloy bool ContainsNoDuplicateCall; 6267ae13575900e8efd056672987249fd0adbf5e73James Molloy 6392df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem /// Number of bytes allocated statically by the callee. 6492df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem uint64_t AllocatedSize; 65f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth unsigned NumInstructions, NumVectorInstructions; 66f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth int FiftyPercentVectorBonus, TenPercentVectorBonus; 67f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth int VectorBonus; 68f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 69f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // While we walk the potentially-inlined instructions, we build up and 70f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // maintain a mapping of simplified values specific to this callsite. The 71f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // idea is to propagate any special information we have about arguments to 72f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // this call through the inlinable section of the function, and account for 73f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // likely simplifications post-inlining. The most important aspect we track 74f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // is CFG altering simplifications -- when we prove a basic block dead, that 75f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // can cause dramatic shifts in the cost of inlining a function. 76f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DenseMap<Value *, Constant *> SimplifiedValues; 77f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 78f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Keep track of the values which map back (through function arguments) to 79f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // allocas on the caller stack which could be simplified through SROA. 80f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DenseMap<Value *, Value *> SROAArgValues; 81f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 82f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // The mapping of caller Alloca values to their accumulated cost savings. If 83f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // we have to disable SROA for one of the allocas, this tells us how much 84f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // cost must be added. 85f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DenseMap<Value *, int> SROAArgCosts; 86f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 87f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Keep track of values which map to a pointer base and constant offset. 88f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DenseMap<Value *, std::pair<Value *, APInt> > ConstantOffsetPtrs; 89f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 90f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Custom simplification helper routines. 91f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool isAllocaDerivedArg(Value *V); 92f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool lookupSROAArgAndCost(Value *V, Value *&Arg, 93f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DenseMap<Value *, int>::iterator &CostIt); 94f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth void disableSROA(DenseMap<Value *, int>::iterator CostIt); 95f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth void disableSROA(Value *V); 96f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth void accumulateSROACost(DenseMap<Value *, int>::iterator CostIt, 97f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth int InstructionCost); 98f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool handleSROACandidate(bool IsSROAValid, 99f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DenseMap<Value *, int>::iterator CostIt, 100f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth int InstructionCost); 101f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool isGEPOffsetConstant(GetElementPtrInst &GEP); 102f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool accumulateGEPOffset(GEPOperator &GEP, APInt &Offset); 103ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth bool simplifyCallSite(Function *F, CallSite CS); 104f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth ConstantInt *stripAndComputeInBoundsConstantOffsets(Value *&V); 105f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 106f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Custom analysis routines. 107f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool analyzeBlock(BasicBlock *BB); 108f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 109f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Disable several entry points to the visitor so we don't accidentally use 110f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // them by declaring but not defining them here. 111f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth void visit(Module *); void visit(Module &); 112f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth void visit(Function *); void visit(Function &); 113f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth void visit(BasicBlock *); void visit(BasicBlock &); 114f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 115f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Provide base case for our instruction visit. 116f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool visitInstruction(Instruction &I); 117f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 118f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Our visit overrides. 119f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool visitAlloca(AllocaInst &I); 120f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool visitPHI(PHINode &I); 121f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool visitGetElementPtr(GetElementPtrInst &I); 122f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool visitBitCast(BitCastInst &I); 123f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool visitPtrToInt(PtrToIntInst &I); 124f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool visitIntToPtr(IntToPtrInst &I); 125f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool visitCastInst(CastInst &I); 126f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool visitUnaryInstruction(UnaryInstruction &I); 127ff29d235ed70d8d7aa03b2d9f9665d2b85f0e195Matt Arsenault bool visitCmpInst(CmpInst &I); 128f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool visitSub(BinaryOperator &I); 129f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool visitBinaryOperator(BinaryOperator &I); 130f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool visitLoad(LoadInst &I); 131f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool visitStore(StoreInst &I); 132ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth bool visitExtractValue(ExtractValueInst &I); 133ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth bool visitInsertValue(InsertValueInst &I); 134f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool visitCallSite(CallSite CS); 135f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 136f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthpublic: 1378d6c0f4deeb0f2ff671df7ae92b75ee1e39acd37Chandler Carruth CallAnalyzer(const DataLayout *TD, const TargetTransformInfo &TTI, 1388d6c0f4deeb0f2ff671df7ae92b75ee1e39acd37Chandler Carruth Function &Callee, int Threshold) 1398d6c0f4deeb0f2ff671df7ae92b75ee1e39acd37Chandler Carruth : TD(TD), TTI(TTI), F(Callee), Threshold(Threshold), Cost(0), 1408d6c0f4deeb0f2ff671df7ae92b75ee1e39acd37Chandler Carruth IsCallerRecursive(false), IsRecursiveCall(false), 1418d6c0f4deeb0f2ff671df7ae92b75ee1e39acd37Chandler Carruth ExposesReturnsTwice(false), HasDynamicAlloca(false), 1428d6c0f4deeb0f2ff671df7ae92b75ee1e39acd37Chandler Carruth ContainsNoDuplicateCall(false), AllocatedSize(0), NumInstructions(0), 1438d6c0f4deeb0f2ff671df7ae92b75ee1e39acd37Chandler Carruth NumVectorInstructions(0), FiftyPercentVectorBonus(0), 1448d6c0f4deeb0f2ff671df7ae92b75ee1e39acd37Chandler Carruth TenPercentVectorBonus(0), VectorBonus(0), NumConstantArgs(0), 1458d6c0f4deeb0f2ff671df7ae92b75ee1e39acd37Chandler Carruth NumConstantOffsetPtrArgs(0), NumAllocaArgs(0), NumConstantPtrCmps(0), 1468d6c0f4deeb0f2ff671df7ae92b75ee1e39acd37Chandler Carruth NumConstantPtrDiffs(0), NumInstructionsSimplified(0), 1478d6c0f4deeb0f2ff671df7ae92b75ee1e39acd37Chandler Carruth SROACostSavings(0), SROACostSavingsLost(0) {} 1483d1d895c866b76ac4d862301f36e2b95d803f0abChandler Carruth 149f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool analyzeCall(CallSite CS); 150082bf2a977b6bb91d61ac5155e1906ecc6ba47bfOwen Anderson 151f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth int getThreshold() { return Threshold; } 152f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth int getCost() { return Cost; } 153082bf2a977b6bb91d61ac5155e1906ecc6ba47bfOwen Anderson 154f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Keep a bunch of stats about the cost savings found so we can print them 155f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // out when debugging. 156f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth unsigned NumConstantArgs; 157f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth unsigned NumConstantOffsetPtrArgs; 158f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth unsigned NumAllocaArgs; 159f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth unsigned NumConstantPtrCmps; 160f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth unsigned NumConstantPtrDiffs; 161f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth unsigned NumInstructionsSimplified; 162f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth unsigned SROACostSavings; 163f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth unsigned SROACostSavingsLost; 164082bf2a977b6bb91d61ac5155e1906ecc6ba47bfOwen Anderson 165f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth void dump(); 166f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth}; 167082bf2a977b6bb91d61ac5155e1906ecc6ba47bfOwen Anderson 168f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth} // namespace 169e8187e02949571e8a610644762b843ef2891f011Chandler Carruth 170f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// \brief Test whether the given value is an Alloca-derived function argument. 171f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthbool CallAnalyzer::isAllocaDerivedArg(Value *V) { 172f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return SROAArgValues.count(V); 173f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth} 174e8187e02949571e8a610644762b843ef2891f011Chandler Carruth 175f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// \brief Lookup the SROA-candidate argument and cost iterator which V maps to. 176f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// Returns false if V does not map to a SROA-candidate. 177f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthbool CallAnalyzer::lookupSROAArgAndCost( 178f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Value *V, Value *&Arg, DenseMap<Value *, int>::iterator &CostIt) { 179f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (SROAArgValues.empty() || SROAArgCosts.empty()) 180f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return false; 181e8187e02949571e8a610644762b843ef2891f011Chandler Carruth 182f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DenseMap<Value *, Value *>::iterator ArgIt = SROAArgValues.find(V); 183f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (ArgIt == SROAArgValues.end()) 184f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return false; 185e8187e02949571e8a610644762b843ef2891f011Chandler Carruth 186f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Arg = ArgIt->second; 187f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth CostIt = SROAArgCosts.find(Arg); 188f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return CostIt != SROAArgCosts.end(); 189e8187e02949571e8a610644762b843ef2891f011Chandler Carruth} 190e8187e02949571e8a610644762b843ef2891f011Chandler Carruth 191f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// \brief Disable SROA for the candidate marked by this cost iterator. 192e8187e02949571e8a610644762b843ef2891f011Chandler Carruth/// 193d9b0b025612992a0b724eeca8bdf10b1d7a5c355Benjamin Kramer/// This marks the candidate as no longer viable for SROA, and adds the cost 194f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// savings associated with it back into the inline cost measurement. 195f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthvoid CallAnalyzer::disableSROA(DenseMap<Value *, int>::iterator CostIt) { 196f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // If we're no longer able to perform SROA we need to undo its cost savings 197f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // and prevent subsequent analysis. 198f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Cost += CostIt->second; 199f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SROACostSavings -= CostIt->second; 200f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SROACostSavingsLost += CostIt->second; 201f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SROAArgCosts.erase(CostIt); 202f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth} 203f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 204f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// \brief If 'V' maps to a SROA candidate, disable SROA for it. 205f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthvoid CallAnalyzer::disableSROA(Value *V) { 206f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Value *SROAArg; 207f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DenseMap<Value *, int>::iterator CostIt; 208f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (lookupSROAArgAndCost(V, SROAArg, CostIt)) 209f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth disableSROA(CostIt); 210f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth} 211f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 212f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// \brief Accumulate the given cost for a particular SROA candidate. 213f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthvoid CallAnalyzer::accumulateSROACost(DenseMap<Value *, int>::iterator CostIt, 214f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth int InstructionCost) { 215f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth CostIt->second += InstructionCost; 216f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SROACostSavings += InstructionCost; 217f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth} 218f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 219f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// \brief Helper for the common pattern of handling a SROA candidate. 220f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// Either accumulates the cost savings if the SROA remains valid, or disables 221f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// SROA for the candidate. 222f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthbool CallAnalyzer::handleSROACandidate(bool IsSROAValid, 223f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DenseMap<Value *, int>::iterator CostIt, 224f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth int InstructionCost) { 225f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (IsSROAValid) { 226f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth accumulateSROACost(CostIt, InstructionCost); 227e8187e02949571e8a610644762b843ef2891f011Chandler Carruth return true; 228e8187e02949571e8a610644762b843ef2891f011Chandler Carruth } 229e8187e02949571e8a610644762b843ef2891f011Chandler Carruth 230f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth disableSROA(CostIt); 231f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return false; 232f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth} 233f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 234f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// \brief Check whether a GEP's indices are all constant. 235f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// 236f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// Respects any simplified values known during the analysis of this callsite. 237f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthbool CallAnalyzer::isGEPOffsetConstant(GetElementPtrInst &GEP) { 238f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth for (User::op_iterator I = GEP.idx_begin(), E = GEP.idx_end(); I != E; ++I) 239f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (!isa<Constant>(*I) && !SimplifiedValues.lookup(*I)) 240e8187e02949571e8a610644762b843ef2891f011Chandler Carruth return false; 241e8187e02949571e8a610644762b843ef2891f011Chandler Carruth 242f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return true; 243f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth} 244f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 245f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// \brief Accumulate a constant GEP offset into an APInt if possible. 246f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// 247f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// Returns false if unable to compute the offset for any reason. Respects any 248f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// simplified values known during the analysis of this callsite. 249f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthbool CallAnalyzer::accumulateGEPOffset(GEPOperator &GEP, APInt &Offset) { 250f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (!TD) 251f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return false; 252f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 253426c2bf5cdd2173e4a33aea8cb92cf684a724f4bChandler Carruth unsigned IntPtrWidth = TD->getPointerSizeInBits(); 254f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth assert(IntPtrWidth == Offset.getBitWidth()); 255f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 256f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth for (gep_type_iterator GTI = gep_type_begin(GEP), GTE = gep_type_end(GEP); 257f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth GTI != GTE; ++GTI) { 258f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth ConstantInt *OpC = dyn_cast<ConstantInt>(GTI.getOperand()); 259f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (!OpC) 260f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (Constant *SimpleOp = SimplifiedValues.lookup(GTI.getOperand())) 261f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth OpC = dyn_cast<ConstantInt>(SimpleOp); 262f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (!OpC) 263e8187e02949571e8a610644762b843ef2891f011Chandler Carruth return false; 264f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (OpC->isZero()) continue; 265e8187e02949571e8a610644762b843ef2891f011Chandler Carruth 266f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Handle a struct index, which adds its field offset to the pointer. 267f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (StructType *STy = dyn_cast<StructType>(*GTI)) { 268f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth unsigned ElementIdx = OpC->getZExtValue(); 269f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth const StructLayout *SL = TD->getStructLayout(STy); 270f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Offset += APInt(IntPtrWidth, SL->getElementOffset(ElementIdx)); 271f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth continue; 272f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 273f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 274f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth APInt TypeSize(IntPtrWidth, TD->getTypeAllocSize(GTI.getIndexedType())); 275f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Offset += OpC->getValue().sextOrTrunc(IntPtrWidth) * TypeSize; 276e8187e02949571e8a610644762b843ef2891f011Chandler Carruth } 277f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return true; 278f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth} 279f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 280f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthbool CallAnalyzer::visitAlloca(AllocaInst &I) { 281f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // FIXME: Check whether inlining will turn a dynamic alloca into a static 282f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // alloca, and handle that case. 283e8187e02949571e8a610644762b843ef2891f011Chandler Carruth 28492df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem // Accumulate the allocated size. 28592df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem if (I.isStaticAlloca()) { 28692df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem Type *Ty = I.getAllocatedType(); 28792df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem AllocatedSize += (TD ? TD->getTypeAllocSize(Ty) : 28892df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem Ty->getPrimitiveSizeInBits()); 28992df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem } 29092df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem 29128f872f8a1945635f30763805c1418a90c6b345eBob Wilson // We will happily inline static alloca instructions. 29228f872f8a1945635f30763805c1418a90c6b345eBob Wilson if (I.isStaticAlloca()) 293f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return Base::visitAlloca(I); 294f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 295f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // FIXME: This is overly conservative. Dynamic allocas are inefficient for 296f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // a variety of reasons, and so we would like to not inline them into 297f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // functions which don't currently have a dynamic alloca. This simply 298f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // disables inlining altogether in the presence of a dynamic alloca. 299f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth HasDynamicAlloca = true; 300f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return false; 301f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth} 302f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 303f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthbool CallAnalyzer::visitPHI(PHINode &I) { 304f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // FIXME: We should potentially be tracking values through phi nodes, 305f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // especially when they collapse to a single value due to deleted CFG edges 306f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // during inlining. 307f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 308f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // FIXME: We need to propagate SROA *disabling* through phi nodes, even 309f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // though we don't want to propagate it's bonuses. The idea is to disable 310f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // SROA if it *might* be used in an inappropriate manner. 311f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 312f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Phi nodes are always zero-cost. 313f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return true; 314f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth} 315f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 316f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthbool CallAnalyzer::visitGetElementPtr(GetElementPtrInst &I) { 317f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Value *SROAArg; 318f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DenseMap<Value *, int>::iterator CostIt; 319f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool SROACandidate = lookupSROAArgAndCost(I.getPointerOperand(), 320f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SROAArg, CostIt); 321f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 322f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Try to fold GEPs of constant-offset call site argument pointers. This 323f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // requires target data and inbounds GEPs. 324f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (TD && I.isInBounds()) { 325f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Check if we have a base + offset for the pointer. 326f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Value *Ptr = I.getPointerOperand(); 327f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth std::pair<Value *, APInt> BaseAndOffset = ConstantOffsetPtrs.lookup(Ptr); 328f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (BaseAndOffset.first) { 329f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Check if the offset of this GEP is constant, and if so accumulate it 330f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // into Offset. 331f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (!accumulateGEPOffset(cast<GEPOperator>(I), BaseAndOffset.second)) { 332f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Non-constant GEPs aren't folded, and disable SROA. 333f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (SROACandidate) 334f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth disableSROA(CostIt); 335e8187e02949571e8a610644762b843ef2891f011Chandler Carruth return false; 336f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 337f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 338f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Add the result as a new mapping to Base + Offset. 339f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth ConstantOffsetPtrs[&I] = BaseAndOffset; 340f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 341f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Also handle SROA candidates here, we already know that the GEP is 342f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // all-constant indexed. 343f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (SROACandidate) 344f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SROAArgValues[&I] = SROAArg; 345f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 346f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return true; 347e8187e02949571e8a610644762b843ef2891f011Chandler Carruth } 348f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 349f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 350f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (isGEPOffsetConstant(I)) { 351f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (SROACandidate) 352f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SROAArgValues[&I] = SROAArg; 353f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 354f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Constant GEPs are modeled as free. 355e8187e02949571e8a610644762b843ef2891f011Chandler Carruth return true; 356e8187e02949571e8a610644762b843ef2891f011Chandler Carruth } 357e8187e02949571e8a610644762b843ef2891f011Chandler Carruth 358f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Variable GEPs will require math and will disable SROA. 359f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (SROACandidate) 360f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth disableSROA(CostIt); 361f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return false; 362f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth} 363f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 364f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthbool CallAnalyzer::visitBitCast(BitCastInst &I) { 365f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Propagate constants through bitcasts. 36673527d30cddd9b542a01a33c333bc707504fd05fChandler Carruth Constant *COp = dyn_cast<Constant>(I.getOperand(0)); 36773527d30cddd9b542a01a33c333bc707504fd05fChandler Carruth if (!COp) 36873527d30cddd9b542a01a33c333bc707504fd05fChandler Carruth COp = SimplifiedValues.lookup(I.getOperand(0)); 36973527d30cddd9b542a01a33c333bc707504fd05fChandler Carruth if (COp) 370f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (Constant *C = ConstantExpr::getBitCast(COp, I.getType())) { 371f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SimplifiedValues[&I] = C; 372e8187e02949571e8a610644762b843ef2891f011Chandler Carruth return true; 373e8187e02949571e8a610644762b843ef2891f011Chandler Carruth } 374f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 375f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Track base/offsets through casts 376f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth std::pair<Value *, APInt> BaseAndOffset 377f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth = ConstantOffsetPtrs.lookup(I.getOperand(0)); 378f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Casts don't change the offset, just wrap it up. 379f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (BaseAndOffset.first) 380f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth ConstantOffsetPtrs[&I] = BaseAndOffset; 381f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 382f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Also look for SROA candidates here. 383f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Value *SROAArg; 384f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DenseMap<Value *, int>::iterator CostIt; 385f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt)) 386f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SROAArgValues[&I] = SROAArg; 387f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 388f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Bitcasts are always zero cost. 389f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return true; 390f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth} 391f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 392f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthbool CallAnalyzer::visitPtrToInt(PtrToIntInst &I) { 393f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Propagate constants through ptrtoint. 39473527d30cddd9b542a01a33c333bc707504fd05fChandler Carruth Constant *COp = dyn_cast<Constant>(I.getOperand(0)); 39573527d30cddd9b542a01a33c333bc707504fd05fChandler Carruth if (!COp) 39673527d30cddd9b542a01a33c333bc707504fd05fChandler Carruth COp = SimplifiedValues.lookup(I.getOperand(0)); 39773527d30cddd9b542a01a33c333bc707504fd05fChandler Carruth if (COp) 398f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (Constant *C = ConstantExpr::getPtrToInt(COp, I.getType())) { 399f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SimplifiedValues[&I] = C; 400f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return true; 401f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 402f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 403f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Track base/offset pairs when converted to a plain integer provided the 404f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // integer is large enough to represent the pointer. 405f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth unsigned IntegerSize = I.getType()->getScalarSizeInBits(); 406426c2bf5cdd2173e4a33aea8cb92cf684a724f4bChandler Carruth if (TD && IntegerSize >= TD->getPointerSizeInBits()) { 407f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth std::pair<Value *, APInt> BaseAndOffset 408f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth = ConstantOffsetPtrs.lookup(I.getOperand(0)); 409f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (BaseAndOffset.first) 410f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth ConstantOffsetPtrs[&I] = BaseAndOffset; 411e8187e02949571e8a610644762b843ef2891f011Chandler Carruth } 412e8187e02949571e8a610644762b843ef2891f011Chandler Carruth 413f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // This is really weird. Technically, ptrtoint will disable SROA. However, 414f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // unless that ptrtoint is *used* somewhere in the live basic blocks after 415f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // inlining, it will be nuked, and SROA should proceed. All of the uses which 416f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // would block SROA would also block SROA if applied directly to a pointer, 417f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // and so we can just add the integer in here. The only places where SROA is 418f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // preserved either cannot fire on an integer, or won't in-and-of themselves 419f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // disable SROA (ext) w/o some later use that we would see and disable. 420f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Value *SROAArg; 421f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DenseMap<Value *, int>::iterator CostIt; 422f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt)) 423f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SROAArgValues[&I] = SROAArg; 424f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 425b5da8a4ae1fbd8e4ffab06cfeb5b32a94d0381bbChandler Carruth return TargetTransformInfo::TCC_Free == TTI.getUserCost(&I); 426e8187e02949571e8a610644762b843ef2891f011Chandler Carruth} 427e8187e02949571e8a610644762b843ef2891f011Chandler Carruth 428f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthbool CallAnalyzer::visitIntToPtr(IntToPtrInst &I) { 429f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Propagate constants through ptrtoint. 43073527d30cddd9b542a01a33c333bc707504fd05fChandler Carruth Constant *COp = dyn_cast<Constant>(I.getOperand(0)); 43173527d30cddd9b542a01a33c333bc707504fd05fChandler Carruth if (!COp) 43273527d30cddd9b542a01a33c333bc707504fd05fChandler Carruth COp = SimplifiedValues.lookup(I.getOperand(0)); 43373527d30cddd9b542a01a33c333bc707504fd05fChandler Carruth if (COp) 434f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (Constant *C = ConstantExpr::getIntToPtr(COp, I.getType())) { 435f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SimplifiedValues[&I] = C; 436f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return true; 437f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 4386977e79526a6342b9408c358bca21c3b0c7e61d5Nick Lewycky 439f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Track base/offset pairs when round-tripped through a pointer without 440f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // modifications provided the integer is not too large. 441f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Value *Op = I.getOperand(0); 442f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth unsigned IntegerSize = Op->getType()->getScalarSizeInBits(); 443426c2bf5cdd2173e4a33aea8cb92cf684a724f4bChandler Carruth if (TD && IntegerSize <= TD->getPointerSizeInBits()) { 444f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth std::pair<Value *, APInt> BaseAndOffset = ConstantOffsetPtrs.lookup(Op); 445f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (BaseAndOffset.first) 446f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth ConstantOffsetPtrs[&I] = BaseAndOffset; 447f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 448e8187e02949571e8a610644762b843ef2891f011Chandler Carruth 449f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // "Propagate" SROA here in the same manner as we do for ptrtoint above. 450f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Value *SROAArg; 451f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DenseMap<Value *, int>::iterator CostIt; 452f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (lookupSROAArgAndCost(Op, SROAArg, CostIt)) 453f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SROAArgValues[&I] = SROAArg; 454e8187e02949571e8a610644762b843ef2891f011Chandler Carruth 455b5da8a4ae1fbd8e4ffab06cfeb5b32a94d0381bbChandler Carruth return TargetTransformInfo::TCC_Free == TTI.getUserCost(&I); 456f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth} 457f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 458f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthbool CallAnalyzer::visitCastInst(CastInst &I) { 459f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Propagate constants through ptrtoint. 46073527d30cddd9b542a01a33c333bc707504fd05fChandler Carruth Constant *COp = dyn_cast<Constant>(I.getOperand(0)); 46173527d30cddd9b542a01a33c333bc707504fd05fChandler Carruth if (!COp) 46273527d30cddd9b542a01a33c333bc707504fd05fChandler Carruth COp = SimplifiedValues.lookup(I.getOperand(0)); 46373527d30cddd9b542a01a33c333bc707504fd05fChandler Carruth if (COp) 464f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (Constant *C = ConstantExpr::getCast(I.getOpcode(), COp, I.getType())) { 465f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SimplifiedValues[&I] = C; 466f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return true; 467082bf2a977b6bb91d61ac5155e1906ecc6ba47bfOwen Anderson } 468082bf2a977b6bb91d61ac5155e1906ecc6ba47bfOwen Anderson 469f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Disable SROA in the face of arbitrary casts we don't whitelist elsewhere. 470f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth disableSROA(I.getOperand(0)); 471f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 472b5da8a4ae1fbd8e4ffab06cfeb5b32a94d0381bbChandler Carruth return TargetTransformInfo::TCC_Free == TTI.getUserCost(&I); 473082bf2a977b6bb91d61ac5155e1906ecc6ba47bfOwen Anderson} 474082bf2a977b6bb91d61ac5155e1906ecc6ba47bfOwen Anderson 475f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthbool CallAnalyzer::visitUnaryInstruction(UnaryInstruction &I) { 476f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Value *Operand = I.getOperand(0); 477b6aebf1cf31232d6b5d4f5060a2ee9fcdbfc6f03Jakub Staszak Constant *COp = dyn_cast<Constant>(Operand); 478b6aebf1cf31232d6b5d4f5060a2ee9fcdbfc6f03Jakub Staszak if (!COp) 479b6aebf1cf31232d6b5d4f5060a2ee9fcdbfc6f03Jakub Staszak COp = SimplifiedValues.lookup(Operand); 480b6aebf1cf31232d6b5d4f5060a2ee9fcdbfc6f03Jakub Staszak if (COp) 481f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (Constant *C = ConstantFoldInstOperands(I.getOpcode(), I.getType(), 482b6aebf1cf31232d6b5d4f5060a2ee9fcdbfc6f03Jakub Staszak COp, TD)) { 483f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SimplifiedValues[&I] = C; 484f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return true; 485f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 486274d377ea68195989c3238fe96ce2ca812a12fafChandler Carruth 487f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Disable any SROA on the argument to arbitrary unary operators. 488f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth disableSROA(Operand); 489f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 490f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return false; 491f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth} 492f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 493ff29d235ed70d8d7aa03b2d9f9665d2b85f0e195Matt Arsenaultbool CallAnalyzer::visitCmpInst(CmpInst &I) { 494f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); 495f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // First try to handle simplified comparisons. 496f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (!isa<Constant>(LHS)) 497f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (Constant *SimpleLHS = SimplifiedValues.lookup(LHS)) 498f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth LHS = SimpleLHS; 499f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (!isa<Constant>(RHS)) 500f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (Constant *SimpleRHS = SimplifiedValues.lookup(RHS)) 501f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth RHS = SimpleRHS; 502ff29d235ed70d8d7aa03b2d9f9665d2b85f0e195Matt Arsenault if (Constant *CLHS = dyn_cast<Constant>(LHS)) { 503f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (Constant *CRHS = dyn_cast<Constant>(RHS)) 504ff29d235ed70d8d7aa03b2d9f9665d2b85f0e195Matt Arsenault if (Constant *C = ConstantExpr::getCompare(I.getPredicate(), CLHS, CRHS)) { 505f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SimplifiedValues[&I] = C; 506f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return true; 507274d377ea68195989c3238fe96ce2ca812a12fafChandler Carruth } 508ff29d235ed70d8d7aa03b2d9f9665d2b85f0e195Matt Arsenault } 509ff29d235ed70d8d7aa03b2d9f9665d2b85f0e195Matt Arsenault 510ff29d235ed70d8d7aa03b2d9f9665d2b85f0e195Matt Arsenault if (I.getOpcode() == Instruction::FCmp) 511ff29d235ed70d8d7aa03b2d9f9665d2b85f0e195Matt Arsenault return false; 512274d377ea68195989c3238fe96ce2ca812a12fafChandler Carruth 513f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Otherwise look for a comparison between constant offset pointers with 514f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // a common base. 515f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Value *LHSBase, *RHSBase; 516f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth APInt LHSOffset, RHSOffset; 517f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth llvm::tie(LHSBase, LHSOffset) = ConstantOffsetPtrs.lookup(LHS); 518f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (LHSBase) { 519f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth llvm::tie(RHSBase, RHSOffset) = ConstantOffsetPtrs.lookup(RHS); 520f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (RHSBase && LHSBase == RHSBase) { 521f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // We have common bases, fold the icmp to a constant based on the 522f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // offsets. 523f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Constant *CLHS = ConstantInt::get(LHS->getContext(), LHSOffset); 524f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Constant *CRHS = ConstantInt::get(RHS->getContext(), RHSOffset); 525f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (Constant *C = ConstantExpr::getICmp(I.getPredicate(), CLHS, CRHS)) { 526f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SimplifiedValues[&I] = C; 527f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth ++NumConstantPtrCmps; 528f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return true; 529274d377ea68195989c3238fe96ce2ca812a12fafChandler Carruth } 530f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 531f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 532274d377ea68195989c3238fe96ce2ca812a12fafChandler Carruth 533f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // If the comparison is an equality comparison with null, we can simplify it 534f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // for any alloca-derived argument. 535f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (I.isEquality() && isa<ConstantPointerNull>(I.getOperand(1))) 536f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (isAllocaDerivedArg(I.getOperand(0))) { 537f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // We can actually predict the result of comparisons between an 538f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // alloca-derived value and null. Note that this fires regardless of 539f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // SROA firing. 540f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool IsNotEqual = I.getPredicate() == CmpInst::ICMP_NE; 541f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SimplifiedValues[&I] = IsNotEqual ? ConstantInt::getTrue(I.getType()) 542f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth : ConstantInt::getFalse(I.getType()); 543f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return true; 544f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 545274d377ea68195989c3238fe96ce2ca812a12fafChandler Carruth 546f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Finally check for SROA candidates in comparisons. 547f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Value *SROAArg; 548f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DenseMap<Value *, int>::iterator CostIt; 549f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt)) { 550f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (isa<ConstantPointerNull>(I.getOperand(1))) { 551f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth accumulateSROACost(CostIt, InlineConstants::InstrCost); 552f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return true; 553274d377ea68195989c3238fe96ce2ca812a12fafChandler Carruth } 554274d377ea68195989c3238fe96ce2ca812a12fafChandler Carruth 555f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth disableSROA(CostIt); 556274d377ea68195989c3238fe96ce2ca812a12fafChandler Carruth } 557e4aeec003f82a5263ffb168e175e6fca8b6f681dDan Gohman 558f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return false; 55942c7d23c6d56e0743169d94025264eaf17eb799dKenneth Uildriks} 56074fa7327d690e6ceda6ce77e4e5b8ef75cb12538Kenneth Uildriks 561f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthbool CallAnalyzer::visitSub(BinaryOperator &I) { 562f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Try to handle a special case: we can fold computing the difference of two 563f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // constant-related pointers. 564f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); 565f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Value *LHSBase, *RHSBase; 566f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth APInt LHSOffset, RHSOffset; 567f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth llvm::tie(LHSBase, LHSOffset) = ConstantOffsetPtrs.lookup(LHS); 568f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (LHSBase) { 569f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth llvm::tie(RHSBase, RHSOffset) = ConstantOffsetPtrs.lookup(RHS); 570f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (RHSBase && LHSBase == RHSBase) { 571f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // We have common bases, fold the subtract to a constant based on the 572f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // offsets. 573f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Constant *CLHS = ConstantInt::get(LHS->getContext(), LHSOffset); 574f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Constant *CRHS = ConstantInt::get(RHS->getContext(), RHSOffset); 575f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (Constant *C = ConstantExpr::getSub(CLHS, CRHS)) { 576f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SimplifiedValues[&I] = C; 577f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth ++NumConstantPtrDiffs; 578f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return true; 579f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 580f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 581f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 5825c655413cf9466c29e38204ab3f19b33fffd7996Andrew Trick 583f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Otherwise, fall back to the generic logic for simplifying and handling 584f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // instructions. 585f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return Base::visitSub(I); 586f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth} 587f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 588f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthbool CallAnalyzer::visitBinaryOperator(BinaryOperator &I) { 589f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); 590f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (!isa<Constant>(LHS)) 591f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (Constant *SimpleLHS = SimplifiedValues.lookup(LHS)) 592f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth LHS = SimpleLHS; 593f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (!isa<Constant>(RHS)) 594f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (Constant *SimpleRHS = SimplifiedValues.lookup(RHS)) 595f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth RHS = SimpleRHS; 596f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Value *SimpleV = SimplifyBinOp(I.getOpcode(), LHS, RHS, TD); 597f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (Constant *C = dyn_cast_or_null<Constant>(SimpleV)) { 598f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SimplifiedValues[&I] = C; 599f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return true; 600f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 6015c655413cf9466c29e38204ab3f19b33fffd7996Andrew Trick 602f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Disable any SROA on arguments to arbitrary, unsimplified binary operators. 603f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth disableSROA(LHS); 604f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth disableSROA(RHS); 6055c655413cf9466c29e38204ab3f19b33fffd7996Andrew Trick 606f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return false; 6074e8af6db184118638c21f713ad98e3292c6891c9Eric Christopher} 6084e8af6db184118638c21f713ad98e3292c6891c9Eric Christopher 609f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthbool CallAnalyzer::visitLoad(LoadInst &I) { 610f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Value *SROAArg; 611f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DenseMap<Value *, int>::iterator CostIt; 612f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt)) { 613f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (I.isSimple()) { 614f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth accumulateSROACost(CostIt, InlineConstants::InstrCost); 615f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return true; 6168e2da0ce9d70606e10889d17f481842586132d88Eric Christopher } 6178e2da0ce9d70606e10889d17f481842586132d88Eric Christopher 618f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth disableSROA(CostIt); 619f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 6208e2da0ce9d70606e10889d17f481842586132d88Eric Christopher 621f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return false; 622f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth} 623f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 624f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthbool CallAnalyzer::visitStore(StoreInst &I) { 625f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Value *SROAArg; 626f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DenseMap<Value *, int>::iterator CostIt; 627f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (lookupSROAArgAndCost(I.getOperand(0), SROAArg, CostIt)) { 628f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (I.isSimple()) { 629f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth accumulateSROACost(CostIt, InlineConstants::InstrCost); 630f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return true; 6318e2da0ce9d70606e10889d17f481842586132d88Eric Christopher } 632f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 633f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth disableSROA(CostIt); 6348e2da0ce9d70606e10889d17f481842586132d88Eric Christopher } 6355c655413cf9466c29e38204ab3f19b33fffd7996Andrew Trick 636f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return false; 6374e8af6db184118638c21f713ad98e3292c6891c9Eric Christopher} 6384e8af6db184118638c21f713ad98e3292c6891c9Eric Christopher 639ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruthbool CallAnalyzer::visitExtractValue(ExtractValueInst &I) { 640ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth // Constant folding for extract value is trivial. 641ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth Constant *C = dyn_cast<Constant>(I.getAggregateOperand()); 642ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth if (!C) 643ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth C = SimplifiedValues.lookup(I.getAggregateOperand()); 644ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth if (C) { 645ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth SimplifiedValues[&I] = ConstantExpr::getExtractValue(C, I.getIndices()); 646ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth return true; 647ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth } 648ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth 649ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth // SROA can look through these but give them a cost. 650ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth return false; 651ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth} 652ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth 653ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruthbool CallAnalyzer::visitInsertValue(InsertValueInst &I) { 654ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth // Constant folding for insert value is trivial. 655ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth Constant *AggC = dyn_cast<Constant>(I.getAggregateOperand()); 656ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth if (!AggC) 657ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth AggC = SimplifiedValues.lookup(I.getAggregateOperand()); 658ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth Constant *InsertedC = dyn_cast<Constant>(I.getInsertedValueOperand()); 659ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth if (!InsertedC) 660ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth InsertedC = SimplifiedValues.lookup(I.getInsertedValueOperand()); 661ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth if (AggC && InsertedC) { 662ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth SimplifiedValues[&I] = ConstantExpr::getInsertValue(AggC, InsertedC, 663ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth I.getIndices()); 664ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth return true; 665ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth } 666ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth 667ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth // SROA can look through these but give them a cost. 668ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth return false; 669ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth} 670ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth 671ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth/// \brief Try to simplify a call site. 672ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth/// 673ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth/// Takes a concrete function and callsite and tries to actually simplify it by 674ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth/// analyzing the arguments and call itself with instsimplify. Returns true if 675ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth/// it has simplified the callsite to some other entity (a constant), making it 676ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth/// free. 677ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruthbool CallAnalyzer::simplifyCallSite(Function *F, CallSite CS) { 678ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth // FIXME: Using the instsimplify logic directly for this is inefficient 679ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth // because we have to continually rebuild the argument list even when no 680ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth // simplifications can be performed. Until that is fixed with remapping 681ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth // inside of instsimplify, directly constant fold calls here. 682ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth if (!canConstantFoldCallTo(F)) 683ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth return false; 684ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth 685ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth // Try to re-map the arguments to constants. 686ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth SmallVector<Constant *, 4> ConstantArgs; 687ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth ConstantArgs.reserve(CS.arg_size()); 688ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth for (CallSite::arg_iterator I = CS.arg_begin(), E = CS.arg_end(); 689ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth I != E; ++I) { 690ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth Constant *C = dyn_cast<Constant>(*I); 691ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth if (!C) 692ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth C = dyn_cast_or_null<Constant>(SimplifiedValues.lookup(*I)); 693ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth if (!C) 694ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth return false; // This argument doesn't map to a constant. 695ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth 696ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth ConstantArgs.push_back(C); 697ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth } 698ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth if (Constant *C = ConstantFoldCall(F, ConstantArgs)) { 699ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth SimplifiedValues[CS.getInstruction()] = C; 700ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth return true; 701ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth } 702ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth 703ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth return false; 704ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth} 705ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth 706f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthbool CallAnalyzer::visitCallSite(CallSite CS) { 707f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (CS.isCall() && cast<CallInst>(CS.getInstruction())->canReturnTwice() && 708831737d329a727f53a1fb0572f7b7a8127208881Bill Wendling !F.getAttributes().hasAttribute(AttributeSet::FunctionIndex, 709831737d329a727f53a1fb0572f7b7a8127208881Bill Wendling Attribute::ReturnsTwice)) { 710f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // This aborts the entire analysis. 711f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth ExposesReturnsTwice = true; 712f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return false; 7134e8af6db184118638c21f713ad98e3292c6891c9Eric Christopher } 71467ae13575900e8efd056672987249fd0adbf5e73James Molloy if (CS.isCall() && 71567ae13575900e8efd056672987249fd0adbf5e73James Molloy cast<CallInst>(CS.getInstruction())->hasFnAttr(Attribute::NoDuplicate)) 71667ae13575900e8efd056672987249fd0adbf5e73James Molloy ContainsNoDuplicateCall = true; 7175c655413cf9466c29e38204ab3f19b33fffd7996Andrew Trick 718ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth if (Function *F = CS.getCalledFunction()) { 719ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth // When we have a concrete function, first try to simplify it directly. 720ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth if (simplifyCallSite(F, CS)) 721ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth return true; 722274d377ea68195989c3238fe96ce2ca812a12fafChandler Carruth 723ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth // Next check if it is an intrinsic we know about. 724ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth // FIXME: Lift this into part of the InstVisitor. 725ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth if (IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction())) { 726ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth switch (II->getIntrinsicID()) { 727ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth default: 728ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth return Base::visitCallSite(CS); 729ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth 730ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth case Intrinsic::memset: 731ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth case Intrinsic::memcpy: 732ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth case Intrinsic::memmove: 733ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth // SROA can usually chew through these intrinsics, but they aren't free. 734ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth return false; 735ba94204e94ba88f7c897a5a59d1c770b7dc3d04eChandler Carruth } 736f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 7374e8af6db184118638c21f713ad98e3292c6891c9Eric Christopher 738f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (F == CS.getInstruction()->getParent()->getParent()) { 739f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // This flag will fully abort the analysis, so don't bother with anything 740f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // else. 74192df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem IsRecursiveCall = true; 742f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return false; 743f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 7444e8af6db184118638c21f713ad98e3292c6891c9Eric Christopher 74513086a658ae06046ded902229f9918b8bad505bdChandler Carruth if (TTI.isLoweredToCall(F)) { 746f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // We account for the average 1 instruction per call argument setup 747f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // here. 748f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Cost += CS.arg_size() * InlineConstants::InstrCost; 7494e8af6db184118638c21f713ad98e3292c6891c9Eric Christopher 750f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Everything other than inline ASM will also have a significant cost 751f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // merely from making the call. 752f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (!isa<InlineAsm>(CS.getCalledValue())) 753f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Cost += InlineConstants::CallPenalty; 754f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 7555c655413cf9466c29e38204ab3f19b33fffd7996Andrew Trick 756f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return Base::visitCallSite(CS); 757f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 758f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 759f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Otherwise we're in a very special case -- an indirect function call. See 760f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // if we can be particularly clever about this. 761f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Value *Callee = CS.getCalledValue(); 762f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 763f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // First, pay the price of the argument setup. We account for the average 764f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // 1 instruction per call argument setup here. 765f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Cost += CS.arg_size() * InlineConstants::InstrCost; 766f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 767f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Next, check if this happens to be an indirect function call to a known 768f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // function in this inline context. If not, we've done all we can. 769f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Function *F = dyn_cast_or_null<Function>(SimplifiedValues.lookup(Callee)); 770f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (!F) 771f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return Base::visitCallSite(CS); 772f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 773f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // If we have a constant that we are calling as a function, we can peer 774f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // through it and see the function target. This happens not infrequently 775f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // during devirtualization and so we want to give it a hefty bonus for 776f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // inlining, but cap that bonus in the event that inlining wouldn't pan 777f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // out. Pretend to inline the function, with a custom threshold. 7788d6c0f4deeb0f2ff671df7ae92b75ee1e39acd37Chandler Carruth CallAnalyzer CA(TD, TTI, *F, InlineConstants::IndirectCallThreshold); 779f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (CA.analyzeCall(CS)) { 780f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // We were able to inline the indirect call! Subtract the cost from the 781f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // bonus we want to apply, but don't go below zero. 782f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Cost -= std::max(0, InlineConstants::IndirectCallThreshold - CA.getCost()); 783f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 784f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 785f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return Base::visitCallSite(CS); 7864e8af6db184118638c21f713ad98e3292c6891c9Eric Christopher} 7874e8af6db184118638c21f713ad98e3292c6891c9Eric Christopher 788f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthbool CallAnalyzer::visitInstruction(Instruction &I) { 789d5003cafd6fc86acaf8e09ef0ca1dc899da8850eChandler Carruth // Some instructions are free. All of the free intrinsics can also be 790d5003cafd6fc86acaf8e09ef0ca1dc899da8850eChandler Carruth // handled by SROA, etc. 791b5da8a4ae1fbd8e4ffab06cfeb5b32a94d0381bbChandler Carruth if (TargetTransformInfo::TCC_Free == TTI.getUserCost(&I)) 792d5003cafd6fc86acaf8e09ef0ca1dc899da8850eChandler Carruth return true; 793d5003cafd6fc86acaf8e09ef0ca1dc899da8850eChandler Carruth 794f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // We found something we don't understand or can't handle. Mark any SROA-able 795f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // values in the operand list as no longer viable. 796f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth for (User::op_iterator OI = I.op_begin(), OE = I.op_end(); OI != OE; ++OI) 797f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth disableSROA(*OI); 798f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 799f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return false; 8008e2da0ce9d70606e10889d17f481842586132d88Eric Christopher} 80174fa7327d690e6ceda6ce77e4e5b8ef75cb12538Kenneth Uildriks 802f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 803f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// \brief Analyze a basic block for its contribution to the inline cost. 804f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// 805f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// This method walks the analyzer over every instruction in the given basic 806f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// block and accounts for their cost during inlining at this callsite. It 807f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// aborts early if the threshold has been exceeded or an impossible to inline 808f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// construct has been detected. It returns false if inlining is no longer 809f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// viable, and true if inlining remains viable. 810f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthbool CallAnalyzer::analyzeBlock(BasicBlock *BB) { 811f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth for (BasicBlock::iterator I = BB->begin(), E = llvm::prior(BB->end()); 812f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth I != E; ++I) { 813f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth ++NumInstructions; 814f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (isa<ExtractElementInst>(I) || I->getType()->isVectorTy()) 815f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth ++NumVectorInstructions; 816f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 817f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // If the instruction simplified to a constant, there is no cost to this 818f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // instruction. Visit the instructions using our InstVisitor to account for 819f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // all of the per-instruction logic. The visit tree returns true if we 820f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // consumed the instruction in any way, and false if the instruction's base 821f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // cost should count against inlining. 822f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (Base::visit(I)) 823f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth ++NumInstructionsSimplified; 824f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth else 825f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Cost += InlineConstants::InstrCost; 826f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 827f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // If the visit this instruction detected an uninlinable pattern, abort. 82892df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem if (IsRecursiveCall || ExposesReturnsTwice || HasDynamicAlloca) 82992df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem return false; 83092df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem 83192df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem // If the caller is a recursive function then we don't want to inline 83292df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem // functions which allocate a lot of stack space because it would increase 83392df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem // the caller stack usage dramatically. 83492df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem if (IsCallerRecursive && 83592df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem AllocatedSize > InlineConstants::TotalAllocaSizeRecursiveCaller) 836f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return false; 837f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 838f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (NumVectorInstructions > NumInstructions/2) 839f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth VectorBonus = FiftyPercentVectorBonus; 840f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth else if (NumVectorInstructions > NumInstructions/10) 841f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth VectorBonus = TenPercentVectorBonus; 842f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth else 843f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth VectorBonus = 0; 844f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 845f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Check if we've past the threshold so we don't spin in huge basic 846f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // blocks that will never inline. 84728f872f8a1945635f30763805c1418a90c6b345eBob Wilson if (Cost > (Threshold + VectorBonus)) 848f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return false; 849f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 850f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 851f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return true; 852752e2590585227f6f10e80978f587915d9adb2adDavid Chisnall} 853752e2590585227f6f10e80978f587915d9adb2adDavid Chisnall 854f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// \brief Compute the base pointer and cumulative constant offsets for V. 855f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// 856f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// This strips all constant offsets off of V, leaving it the base pointer, and 857f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// accumulates the total constant offset applied in the returned constant. It 858f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// returns 0 if V is not a pointer, and returns the constant '0' if there are 859f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// no constant offsets applied. 860f2286b0152f0b942e82d8e809186e5cc0d247131Chandler CarruthConstantInt *CallAnalyzer::stripAndComputeInBoundsConstantOffsets(Value *&V) { 861f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (!TD || !V->getType()->isPointerTy()) 862f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return 0; 863f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 864426c2bf5cdd2173e4a33aea8cb92cf684a724f4bChandler Carruth unsigned IntPtrWidth = TD->getPointerSizeInBits(); 865f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth APInt Offset = APInt::getNullValue(IntPtrWidth); 866f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 867f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Even though we don't look through PHI nodes, we could be called on an 868f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // instruction in an unreachable block, which may be on a cycle. 869f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SmallPtrSet<Value *, 4> Visited; 870f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Visited.insert(V); 871f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth do { 872f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (GEPOperator *GEP = dyn_cast<GEPOperator>(V)) { 873f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (!GEP->isInBounds() || !accumulateGEPOffset(*GEP, Offset)) 874f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return 0; 875f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth V = GEP->getPointerOperand(); 876f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } else if (Operator::getOpcode(V) == Instruction::BitCast) { 877f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth V = cast<Operator>(V)->getOperand(0); 878f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } else if (GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) { 879f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (GA->mayBeOverridden()) 880f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth break; 881f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth V = GA->getAliasee(); 882f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } else { 883f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth break; 884f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 885f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth assert(V->getType()->isPointerTy() && "Unexpected operand type!"); 886f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } while (Visited.insert(V)); 887e4aeec003f82a5263ffb168e175e6fca8b6f681dDan Gohman 888ece6c6bb6329748b92403c06ac87f45c43485911Chandler Carruth Type *IntPtrTy = TD->getIntPtrType(V->getContext()); 889f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return cast<ConstantInt>(ConstantInt::get(IntPtrTy, Offset)); 890f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth} 891e4aeec003f82a5263ffb168e175e6fca8b6f681dDan Gohman 892f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// \brief Analyze a call site for potential inlining. 893f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// 894f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// Returns true if inlining this call is viable, and false if it is not 895f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// viable. It computes the cost and adjusts the threshold based on numerous 896f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// factors and heuristics. If this method returns false but the computed cost 897f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// is below the computed threshold, then inlining was forcibly disabled by 898593423f7461fbbbf752ff013bf20c19ef95d3435Bob Wilson/// some artifact of the routine. 899f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthbool CallAnalyzer::analyzeCall(CallSite CS) { 900d6fc26217e194372cabe4ef9e2514beac511a943Chandler Carruth ++NumCallsAnalyzed; 901d6fc26217e194372cabe4ef9e2514beac511a943Chandler Carruth 902f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Track whether the post-inlining function would have more than one basic 903f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // block. A single basic block is often intended for inlining. Balloon the 904f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // threshold by 50% until we pass the single-BB phase. 905f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool SingleBB = true; 906f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth int SingleBBBonus = Threshold / 2; 907f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Threshold += SingleBBBonus; 908f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 90928f872f8a1945635f30763805c1418a90c6b345eBob Wilson // Perform some tweaks to the cost and threshold based on the direct 91028f872f8a1945635f30763805c1418a90c6b345eBob Wilson // callsite information. 91128f872f8a1945635f30763805c1418a90c6b345eBob Wilson 91228f872f8a1945635f30763805c1418a90c6b345eBob Wilson // We want to more aggressively inline vector-dense kernels, so up the 91328f872f8a1945635f30763805c1418a90c6b345eBob Wilson // threshold, and we'll lower it if the % of vector instructions gets too 91428f872f8a1945635f30763805c1418a90c6b345eBob Wilson // low. 91528f872f8a1945635f30763805c1418a90c6b345eBob Wilson assert(NumInstructions == 0); 91628f872f8a1945635f30763805c1418a90c6b345eBob Wilson assert(NumVectorInstructions == 0); 91728f872f8a1945635f30763805c1418a90c6b345eBob Wilson FiftyPercentVectorBonus = Threshold; 91828f872f8a1945635f30763805c1418a90c6b345eBob Wilson TenPercentVectorBonus = Threshold / 2; 91928f872f8a1945635f30763805c1418a90c6b345eBob Wilson 92028f872f8a1945635f30763805c1418a90c6b345eBob Wilson // Give out bonuses per argument, as the instructions setting them up will 92128f872f8a1945635f30763805c1418a90c6b345eBob Wilson // be gone after inlining. 92228f872f8a1945635f30763805c1418a90c6b345eBob Wilson for (unsigned I = 0, E = CS.arg_size(); I != E; ++I) { 92328f872f8a1945635f30763805c1418a90c6b345eBob Wilson if (TD && CS.isByValArgument(I)) { 92428f872f8a1945635f30763805c1418a90c6b345eBob Wilson // We approximate the number of loads and stores needed by dividing the 92528f872f8a1945635f30763805c1418a90c6b345eBob Wilson // size of the byval type by the target's pointer size. 92628f872f8a1945635f30763805c1418a90c6b345eBob Wilson PointerType *PTy = cast<PointerType>(CS.getArgument(I)->getType()); 92728f872f8a1945635f30763805c1418a90c6b345eBob Wilson unsigned TypeSize = TD->getTypeSizeInBits(PTy->getElementType()); 92828f872f8a1945635f30763805c1418a90c6b345eBob Wilson unsigned PointerSize = TD->getPointerSizeInBits(); 92928f872f8a1945635f30763805c1418a90c6b345eBob Wilson // Ceiling division. 93028f872f8a1945635f30763805c1418a90c6b345eBob Wilson unsigned NumStores = (TypeSize + PointerSize - 1) / PointerSize; 93128f872f8a1945635f30763805c1418a90c6b345eBob Wilson 93228f872f8a1945635f30763805c1418a90c6b345eBob Wilson // If it generates more than 8 stores it is likely to be expanded as an 93328f872f8a1945635f30763805c1418a90c6b345eBob Wilson // inline memcpy so we take that as an upper bound. Otherwise we assume 93428f872f8a1945635f30763805c1418a90c6b345eBob Wilson // one load and one store per word copied. 93528f872f8a1945635f30763805c1418a90c6b345eBob Wilson // FIXME: The maxStoresPerMemcpy setting from the target should be used 93628f872f8a1945635f30763805c1418a90c6b345eBob Wilson // here instead of a magic number of 8, but it's not available via 93728f872f8a1945635f30763805c1418a90c6b345eBob Wilson // DataLayout. 93828f872f8a1945635f30763805c1418a90c6b345eBob Wilson NumStores = std::min(NumStores, 8U); 93928f872f8a1945635f30763805c1418a90c6b345eBob Wilson 94028f872f8a1945635f30763805c1418a90c6b345eBob Wilson Cost -= 2 * NumStores * InlineConstants::InstrCost; 94128f872f8a1945635f30763805c1418a90c6b345eBob Wilson } else { 94228f872f8a1945635f30763805c1418a90c6b345eBob Wilson // For non-byval arguments subtract off one instruction per call 94328f872f8a1945635f30763805c1418a90c6b345eBob Wilson // argument. 94428f872f8a1945635f30763805c1418a90c6b345eBob Wilson Cost -= InlineConstants::InstrCost; 945b6fdd022b7414f916ba7b08560a0f55e14863326Benjamin Kramer } 94628f872f8a1945635f30763805c1418a90c6b345eBob Wilson } 947f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 94828f872f8a1945635f30763805c1418a90c6b345eBob Wilson // If there is only one call of the function, and it has internal linkage, 94928f872f8a1945635f30763805c1418a90c6b345eBob Wilson // the cost of inlining it drops dramatically. 95067ae13575900e8efd056672987249fd0adbf5e73James Molloy bool OnlyOneCallAndLocalLinkage = F.hasLocalLinkage() && F.hasOneUse() && 95167ae13575900e8efd056672987249fd0adbf5e73James Molloy &F == CS.getCalledFunction(); 95267ae13575900e8efd056672987249fd0adbf5e73James Molloy if (OnlyOneCallAndLocalLinkage) 95328f872f8a1945635f30763805c1418a90c6b345eBob Wilson Cost += InlineConstants::LastCallToStaticBonus; 95428f872f8a1945635f30763805c1418a90c6b345eBob Wilson 95528f872f8a1945635f30763805c1418a90c6b345eBob Wilson // If the instruction after the call, or if the normal destination of the 95628f872f8a1945635f30763805c1418a90c6b345eBob Wilson // invoke is an unreachable instruction, the function is noreturn. As such, 95728f872f8a1945635f30763805c1418a90c6b345eBob Wilson // there is little point in inlining this unless there is literally zero 95828f872f8a1945635f30763805c1418a90c6b345eBob Wilson // cost. 95928f872f8a1945635f30763805c1418a90c6b345eBob Wilson Instruction *Instr = CS.getInstruction(); 96028f872f8a1945635f30763805c1418a90c6b345eBob Wilson if (InvokeInst *II = dyn_cast<InvokeInst>(Instr)) { 96128f872f8a1945635f30763805c1418a90c6b345eBob Wilson if (isa<UnreachableInst>(II->getNormalDest()->begin())) 962f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Threshold = 1; 96328f872f8a1945635f30763805c1418a90c6b345eBob Wilson } else if (isa<UnreachableInst>(++BasicBlock::iterator(Instr))) 96428f872f8a1945635f30763805c1418a90c6b345eBob Wilson Threshold = 1; 965f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 96628f872f8a1945635f30763805c1418a90c6b345eBob Wilson // If this function uses the coldcc calling convention, prefer not to inline 96728f872f8a1945635f30763805c1418a90c6b345eBob Wilson // it. 96828f872f8a1945635f30763805c1418a90c6b345eBob Wilson if (F.getCallingConv() == CallingConv::Cold) 96928f872f8a1945635f30763805c1418a90c6b345eBob Wilson Cost += InlineConstants::ColdccPenalty; 970f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 97128f872f8a1945635f30763805c1418a90c6b345eBob Wilson // Check if we're done. This can happen due to bonuses and penalties. 97228f872f8a1945635f30763805c1418a90c6b345eBob Wilson if (Cost > Threshold) 97328f872f8a1945635f30763805c1418a90c6b345eBob Wilson return false; 9745c655413cf9466c29e38204ab3f19b33fffd7996Andrew Trick 975f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (F.empty()) 976f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return true; 977e4aeec003f82a5263ffb168e175e6fca8b6f681dDan Gohman 97892df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem Function *Caller = CS.getInstruction()->getParent()->getParent(); 97992df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem // Check if the caller function is recursive itself. 98092df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem for (Value::use_iterator U = Caller->use_begin(), E = Caller->use_end(); 98192df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem U != E; ++U) { 98292df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem CallSite Site(cast<Value>(*U)); 98392df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem if (!Site) 98492df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem continue; 98592df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem Instruction *I = Site.getInstruction(); 98692df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem if (I->getParent()->getParent() == Caller) { 98792df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem IsCallerRecursive = true; 98892df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem break; 98992df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem } 99092df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem } 99192df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem 992f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Track whether we've seen a return instruction. The first return 993f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // instruction is free, as at least one will usually disappear in inlining. 994f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool HasReturn = false; 995f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 996f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Populate our simplified values by mapping from function arguments to call 997f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // arguments with known important simplifications. 998f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth CallSite::arg_iterator CAI = CS.arg_begin(); 999f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth for (Function::arg_iterator FAI = F.arg_begin(), FAE = F.arg_end(); 1000f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth FAI != FAE; ++FAI, ++CAI) { 1001f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth assert(CAI != CS.arg_end()); 1002f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (Constant *C = dyn_cast<Constant>(CAI)) 1003f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SimplifiedValues[FAI] = C; 1004f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 1005f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Value *PtrArg = *CAI; 1006f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (ConstantInt *C = stripAndComputeInBoundsConstantOffsets(PtrArg)) { 1007f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth ConstantOffsetPtrs[FAI] = std::make_pair(PtrArg, C->getValue()); 1008f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 1009f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // We can SROA any pointer arguments derived from alloca instructions. 1010f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (isa<AllocaInst>(PtrArg)) { 1011f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SROAArgValues[FAI] = PtrArg; 1012f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SROAArgCosts[PtrArg] = 0; 1013f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 1014f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 1015f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 1016f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth NumConstantArgs = SimplifiedValues.size(); 1017f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth NumConstantOffsetPtrArgs = ConstantOffsetPtrs.size(); 1018f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth NumAllocaArgs = SROAArgValues.size(); 1019f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 1020f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // The worklist of live basic blocks in the callee *after* inlining. We avoid 1021f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // adding basic blocks of the callee which can be proven to be dead for this 1022f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // particular call site in order to get more accurate cost estimates. This 1023f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // requires a somewhat heavyweight iteration pattern: we need to walk the 1024f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // basic blocks in a breadth-first order as we insert live successors. To 1025f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // accomplish this, prioritizing for small iterations because we exit after 1026f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // crossing our threshold, we use a small-size optimized SetVector. 1027f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth typedef SetVector<BasicBlock *, SmallVector<BasicBlock *, 16>, 1028f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SmallPtrSet<BasicBlock *, 16> > BBSetVector; 1029f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth BBSetVector BBWorklist; 1030f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth BBWorklist.insert(&F.getEntryBlock()); 1031f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Note that we *must not* cache the size, this loop grows the worklist. 1032f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth for (unsigned Idx = 0; Idx != BBWorklist.size(); ++Idx) { 1033f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Bail out the moment we cross the threshold. This means we'll under-count 1034f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // the cost, but only when undercounting doesn't matter. 103528f872f8a1945635f30763805c1418a90c6b345eBob Wilson if (Cost > (Threshold + VectorBonus)) 1036f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth break; 1037f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 1038f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth BasicBlock *BB = BBWorklist[Idx]; 1039f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (BB->empty()) 1040f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth continue; 1041e4aeec003f82a5263ffb168e175e6fca8b6f681dDan Gohman 1042f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Handle the terminator cost here where we can track returns and other 1043f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // function-wide constructs. 1044f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth TerminatorInst *TI = BB->getTerminator(); 1045f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 1046f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // We never want to inline functions that contain an indirectbr. This is 1047f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // incorrect because all the blockaddress's (in static global initializers 104892df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem // for example) would be referring to the original function, and this 104992df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem // indirect jump would jump from the inlined copy of the function into the 105092df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem // original function which is extremely undefined behavior. 1051f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // FIXME: This logic isn't really right; we can safely inline functions 1052f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // with indirectbr's as long as no other function or global references the 1053f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // blockaddress of a block within the current function. And as a QOI issue, 1054f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // if someone is using a blockaddress without an indirectbr, and that 1055f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // reference somehow ends up in another function or global, we probably 1056f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // don't want to inline this function. 1057f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (isa<IndirectBrInst>(TI)) 1058f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return false; 10595c655413cf9466c29e38204ab3f19b33fffd7996Andrew Trick 1060f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (!HasReturn && isa<ReturnInst>(TI)) 1061f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth HasReturn = true; 1062f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth else 1063f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Cost += InlineConstants::InstrCost; 1064e4aeec003f82a5263ffb168e175e6fca8b6f681dDan Gohman 1065f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Analyze the cost of this block. If we blow through the threshold, this 1066f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // returns false, and we can bail on out. 1067f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (!analyzeBlock(BB)) { 106892df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem if (IsRecursiveCall || ExposesReturnsTwice || HasDynamicAlloca) 1069f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return false; 107092df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem 107192df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem // If the caller is a recursive function then we don't want to inline 107292df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem // functions which allocate a lot of stack space because it would increase 107392df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem // the caller stack usage dramatically. 107492df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem if (IsCallerRecursive && 107592df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem AllocatedSize > InlineConstants::TotalAllocaSizeRecursiveCaller) 107692df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem return false; 107792df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem 1078f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth break; 1079f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 10805c655413cf9466c29e38204ab3f19b33fffd7996Andrew Trick 1081f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Add in the live successors by first checking whether we have terminator 1082f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // that may be simplified based on the values simplified by this call. 1083f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { 1084f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (BI->isConditional()) { 1085f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Value *Cond = BI->getCondition(); 1086f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (ConstantInt *SimpleCond 1087f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth = dyn_cast_or_null<ConstantInt>(SimplifiedValues.lookup(Cond))) { 1088f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth BBWorklist.insert(BI->getSuccessor(SimpleCond->isZero() ? 1 : 0)); 1089f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth continue; 1090f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 1091f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 1092f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { 1093f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Value *Cond = SI->getCondition(); 1094f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (ConstantInt *SimpleCond 1095f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth = dyn_cast_or_null<ConstantInt>(SimplifiedValues.lookup(Cond))) { 1096f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth BBWorklist.insert(SI->findCaseValue(SimpleCond).getCaseSuccessor()); 1097f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth continue; 1098f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 1099f84755b8360d13b1d19df821d9e8692aac7e9b87Chris Lattner } 1100e4aeec003f82a5263ffb168e175e6fca8b6f681dDan Gohman 1101f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // If we're unable to select a particular successor, just count all of 1102f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // them. 110392df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem for (unsigned TIdx = 0, TSize = TI->getNumSuccessors(); TIdx != TSize; 110492df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem ++TIdx) 1105f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth BBWorklist.insert(TI->getSuccessor(TIdx)); 1106f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth 1107f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // If we had any successors at this point, than post-inlining is likely to 1108f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // have them as well. Note that we assume any basic blocks which existed 1109f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // due to branches or switches which folded above will also fold after 1110f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // inlining. 1111f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (SingleBB && TI->getNumSuccessors() > 1) { 1112f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Take off the bonus we applied to the threshold. 1113f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Threshold -= SingleBBBonus; 1114f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth SingleBB = false; 1115f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth } 1116e4aeec003f82a5263ffb168e175e6fca8b6f681dDan Gohman } 1117e4aeec003f82a5263ffb168e175e6fca8b6f681dDan Gohman 111867ae13575900e8efd056672987249fd0adbf5e73James Molloy // If this is a noduplicate call, we can still inline as long as 111967ae13575900e8efd056672987249fd0adbf5e73James Molloy // inlining this would cause the removal of the caller (so the instruction 112067ae13575900e8efd056672987249fd0adbf5e73James Molloy // is not actually duplicated, just moved). 112167ae13575900e8efd056672987249fd0adbf5e73James Molloy if (!OnlyOneCallAndLocalLinkage && ContainsNoDuplicateCall) 112267ae13575900e8efd056672987249fd0adbf5e73James Molloy return false; 112367ae13575900e8efd056672987249fd0adbf5e73James Molloy 1124f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth Threshold += VectorBonus; 1125e4aeec003f82a5263ffb168e175e6fca8b6f681dDan Gohman 112628f872f8a1945635f30763805c1418a90c6b345eBob Wilson return Cost < Threshold; 1127f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth} 11285c655413cf9466c29e38204ab3f19b33fffd7996Andrew Trick 1129286c4dc355b8be6806081b23c3097485821c7642Manman Ren#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 1130f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth/// \brief Dump stats about this call's analysis. 1131f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruthvoid CallAnalyzer::dump() { 1132f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth#define DEBUG_PRINT_STAT(x) llvm::dbgs() << " " #x ": " << x << "\n" 1133f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DEBUG_PRINT_STAT(NumConstantArgs); 1134f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DEBUG_PRINT_STAT(NumConstantOffsetPtrArgs); 1135f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DEBUG_PRINT_STAT(NumAllocaArgs); 1136f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DEBUG_PRINT_STAT(NumConstantPtrCmps); 1137f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DEBUG_PRINT_STAT(NumConstantPtrDiffs); 1138f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DEBUG_PRINT_STAT(NumInstructionsSimplified); 1139f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DEBUG_PRINT_STAT(SROACostSavings); 1140f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DEBUG_PRINT_STAT(SROACostSavingsLost); 114167ae13575900e8efd056672987249fd0adbf5e73James Molloy DEBUG_PRINT_STAT(ContainsNoDuplicateCall); 1142f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth#undef DEBUG_PRINT_STAT 1143e4aeec003f82a5263ffb168e175e6fca8b6f681dDan Gohman} 1144cc77eece74c8db09acc2af425e7e6c88a5bb30d1Manman Ren#endif 1145f7477470d37ee2ab9075eaee4745fa084d424ab8Jakob Stoklund Olesen 114686953b5795007eaa98838297360a6987e33e92e7Chandler CarruthINITIALIZE_PASS_BEGIN(InlineCostAnalysis, "inline-cost", "Inline Cost Analysis", 114786953b5795007eaa98838297360a6987e33e92e7Chandler Carruth true, true) 11488d6c0f4deeb0f2ff671df7ae92b75ee1e39acd37Chandler CarruthINITIALIZE_AG_DEPENDENCY(TargetTransformInfo) 114986953b5795007eaa98838297360a6987e33e92e7Chandler CarruthINITIALIZE_PASS_END(InlineCostAnalysis, "inline-cost", "Inline Cost Analysis", 115086953b5795007eaa98838297360a6987e33e92e7Chandler Carruth true, true) 115186953b5795007eaa98838297360a6987e33e92e7Chandler Carruth 115286953b5795007eaa98838297360a6987e33e92e7Chandler Carruthchar InlineCostAnalysis::ID = 0; 115386953b5795007eaa98838297360a6987e33e92e7Chandler Carruth 115486953b5795007eaa98838297360a6987e33e92e7Chandler CarruthInlineCostAnalysis::InlineCostAnalysis() : CallGraphSCCPass(ID), TD(0) {} 115586953b5795007eaa98838297360a6987e33e92e7Chandler Carruth 115686953b5795007eaa98838297360a6987e33e92e7Chandler CarruthInlineCostAnalysis::~InlineCostAnalysis() {} 115786953b5795007eaa98838297360a6987e33e92e7Chandler Carruth 115886953b5795007eaa98838297360a6987e33e92e7Chandler Carruthvoid InlineCostAnalysis::getAnalysisUsage(AnalysisUsage &AU) const { 115986953b5795007eaa98838297360a6987e33e92e7Chandler Carruth AU.setPreservesAll(); 11608d6c0f4deeb0f2ff671df7ae92b75ee1e39acd37Chandler Carruth AU.addRequired<TargetTransformInfo>(); 116186953b5795007eaa98838297360a6987e33e92e7Chandler Carruth CallGraphSCCPass::getAnalysisUsage(AU); 116286953b5795007eaa98838297360a6987e33e92e7Chandler Carruth} 116386953b5795007eaa98838297360a6987e33e92e7Chandler Carruth 116486953b5795007eaa98838297360a6987e33e92e7Chandler Carruthbool InlineCostAnalysis::runOnSCC(CallGraphSCC &SCC) { 116586953b5795007eaa98838297360a6987e33e92e7Chandler Carruth TD = getAnalysisIfAvailable<DataLayout>(); 11668d6c0f4deeb0f2ff671df7ae92b75ee1e39acd37Chandler Carruth TTI = &getAnalysis<TargetTransformInfo>(); 116786953b5795007eaa98838297360a6987e33e92e7Chandler Carruth return false; 116886953b5795007eaa98838297360a6987e33e92e7Chandler Carruth} 116986953b5795007eaa98838297360a6987e33e92e7Chandler Carruth 117086953b5795007eaa98838297360a6987e33e92e7Chandler CarruthInlineCost InlineCostAnalysis::getInlineCost(CallSite CS, int Threshold) { 1171b381578fcb5fea988f661dbbee9747b8fd55c5fbDavid Chisnall return getInlineCost(CS, CS.getCalledFunction(), Threshold); 1172b381578fcb5fea988f661dbbee9747b8fd55c5fbDavid Chisnall} 1173f7477470d37ee2ab9075eaee4745fa084d424ab8Jakob Stoklund Olesen 117486953b5795007eaa98838297360a6987e33e92e7Chandler CarruthInlineCost InlineCostAnalysis::getInlineCost(CallSite CS, Function *Callee, 1175b381578fcb5fea988f661dbbee9747b8fd55c5fbDavid Chisnall int Threshold) { 117628f872f8a1945635f30763805c1418a90c6b345eBob Wilson // Cannot inline indirect calls. 117728f872f8a1945635f30763805c1418a90c6b345eBob Wilson if (!Callee) 117828f872f8a1945635f30763805c1418a90c6b345eBob Wilson return llvm::InlineCost::getNever(); 117928f872f8a1945635f30763805c1418a90c6b345eBob Wilson 118028f872f8a1945635f30763805c1418a90c6b345eBob Wilson // Calls to functions with always-inline attributes should be inlined 118128f872f8a1945635f30763805c1418a90c6b345eBob Wilson // whenever possible. 1182831737d329a727f53a1fb0572f7b7a8127208881Bill Wendling if (Callee->getAttributes().hasAttribute(AttributeSet::FunctionIndex, 1183831737d329a727f53a1fb0572f7b7a8127208881Bill Wendling Attribute::AlwaysInline)) { 118428f872f8a1945635f30763805c1418a90c6b345eBob Wilson if (isInlineViable(*Callee)) 118528f872f8a1945635f30763805c1418a90c6b345eBob Wilson return llvm::InlineCost::getAlways(); 118628f872f8a1945635f30763805c1418a90c6b345eBob Wilson return llvm::InlineCost::getNever(); 118728f872f8a1945635f30763805c1418a90c6b345eBob Wilson } 118828f872f8a1945635f30763805c1418a90c6b345eBob Wilson 1189f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Don't inline functions which can be redefined at link-time to mean 1190f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // something else. Don't inline functions marked noinline or call sites 1191f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // marked noinline. 119228f872f8a1945635f30763805c1418a90c6b345eBob Wilson if (Callee->mayBeOverridden() || 1193831737d329a727f53a1fb0572f7b7a8127208881Bill Wendling Callee->getAttributes().hasAttribute(AttributeSet::FunctionIndex, 1194831737d329a727f53a1fb0572f7b7a8127208881Bill Wendling Attribute::NoInline) || 11956765834754cbb3cb0f15b4b15e98c5e73fa50066Bill Wendling CS.isNoInline()) 1196f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return llvm::InlineCost::getNever(); 1197f7477470d37ee2ab9075eaee4745fa084d424ab8Jakob Stoklund Olesen 119892df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem DEBUG(llvm::dbgs() << " Analyzing call of " << Callee->getName() 119992df026f0da91dc65ef6186e97ff87b1f53e8cd0Nadav Rotem << "...\n"); 120044b04a5f4ac8a2b9b3208a937f2ba36bcf7aa40fChris Lattner 12018d6c0f4deeb0f2ff671df7ae92b75ee1e39acd37Chandler Carruth CallAnalyzer CA(TD, *TTI, *Callee, Threshold); 1202f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth bool ShouldInline = CA.analyzeCall(CS); 12035c655413cf9466c29e38204ab3f19b33fffd7996Andrew Trick 1204f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth DEBUG(CA.dump()); 120544b04a5f4ac8a2b9b3208a937f2ba36bcf7aa40fChris Lattner 1206f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth // Check if there was a reason to force inlining or no inlining. 1207f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth if (!ShouldInline && CA.getCost() < CA.getThreshold()) 1208f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return InlineCost::getNever(); 120928f872f8a1945635f30763805c1418a90c6b345eBob Wilson if (ShouldInline && CA.getCost() >= CA.getThreshold()) 1210f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return InlineCost::getAlways(); 12115c655413cf9466c29e38204ab3f19b33fffd7996Andrew Trick 1212f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth return llvm::InlineCost::get(CA.getCost(), CA.getThreshold()); 1213f2286b0152f0b942e82d8e809186e5cc0d247131Chandler Carruth} 121428f872f8a1945635f30763805c1418a90c6b345eBob Wilson 121586953b5795007eaa98838297360a6987e33e92e7Chandler Carruthbool InlineCostAnalysis::isInlineViable(Function &F) { 121686953b5795007eaa98838297360a6987e33e92e7Chandler Carruth bool ReturnsTwice = 121786953b5795007eaa98838297360a6987e33e92e7Chandler Carruth F.getAttributes().hasAttribute(AttributeSet::FunctionIndex, 121886953b5795007eaa98838297360a6987e33e92e7Chandler Carruth Attribute::ReturnsTwice); 121928f872f8a1945635f30763805c1418a90c6b345eBob Wilson for (Function::iterator BI = F.begin(), BE = F.end(); BI != BE; ++BI) { 122028f872f8a1945635f30763805c1418a90c6b345eBob Wilson // Disallow inlining of functions which contain an indirect branch. 122128f872f8a1945635f30763805c1418a90c6b345eBob Wilson if (isa<IndirectBrInst>(BI->getTerminator())) 122228f872f8a1945635f30763805c1418a90c6b345eBob Wilson return false; 122328f872f8a1945635f30763805c1418a90c6b345eBob Wilson 122428f872f8a1945635f30763805c1418a90c6b345eBob Wilson for (BasicBlock::iterator II = BI->begin(), IE = BI->end(); II != IE; 122528f872f8a1945635f30763805c1418a90c6b345eBob Wilson ++II) { 122628f872f8a1945635f30763805c1418a90c6b345eBob Wilson CallSite CS(II); 122728f872f8a1945635f30763805c1418a90c6b345eBob Wilson if (!CS) 122828f872f8a1945635f30763805c1418a90c6b345eBob Wilson continue; 122928f872f8a1945635f30763805c1418a90c6b345eBob Wilson 123028f872f8a1945635f30763805c1418a90c6b345eBob Wilson // Disallow recursive calls. 123128f872f8a1945635f30763805c1418a90c6b345eBob Wilson if (&F == CS.getCalledFunction()) 123228f872f8a1945635f30763805c1418a90c6b345eBob Wilson return false; 123328f872f8a1945635f30763805c1418a90c6b345eBob Wilson 123428f872f8a1945635f30763805c1418a90c6b345eBob Wilson // Disallow calls which expose returns-twice to a function not previously 123528f872f8a1945635f30763805c1418a90c6b345eBob Wilson // attributed as such. 123628f872f8a1945635f30763805c1418a90c6b345eBob Wilson if (!ReturnsTwice && CS.isCall() && 123728f872f8a1945635f30763805c1418a90c6b345eBob Wilson cast<CallInst>(CS.getInstruction())->canReturnTwice()) 123828f872f8a1945635f30763805c1418a90c6b345eBob Wilson return false; 123928f872f8a1945635f30763805c1418a90c6b345eBob Wilson } 124028f872f8a1945635f30763805c1418a90c6b345eBob Wilson } 124128f872f8a1945635f30763805c1418a90c6b345eBob Wilson 124228f872f8a1945635f30763805c1418a90c6b345eBob Wilson return true; 124328f872f8a1945635f30763805c1418a90c6b345eBob Wilson} 1244