1 //===- CodeMetrics.cpp - Code cost measurements ---------------------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file implements code cost measurement utilities. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "llvm/Analysis/CodeMetrics.h" 15 #include "llvm/Analysis/AssumptionCache.h" 16 #include "llvm/Analysis/LoopInfo.h" 17 #include "llvm/Analysis/TargetTransformInfo.h" 18 #include "llvm/Analysis/ValueTracking.h" 19 #include "llvm/IR/CallSite.h" 20 #include "llvm/IR/DataLayout.h" 21 #include "llvm/IR/Function.h" 22 #include "llvm/Support/Debug.h" 23 #include "llvm/Support/raw_ostream.h" 24 25 #define DEBUG_TYPE "code-metrics" 26 27 using namespace llvm; 28 29 static void 30 appendSpeculatableOperands(const Value *V, 31 SmallPtrSetImpl<const Value *> &Visited, 32 SmallVectorImpl<const Value *> &Worklist) { 33 const User *U = dyn_cast<User>(V); 34 if (!U) 35 return; 36 37 for (const Value *Operand : U->operands()) 38 if (Visited.insert(Operand).second) 39 if (isSafeToSpeculativelyExecute(Operand)) 40 Worklist.push_back(Operand); 41 } 42 43 static void completeEphemeralValues(SmallPtrSetImpl<const Value *> &Visited, 44 SmallVectorImpl<const Value *> &Worklist, 45 SmallPtrSetImpl<const Value *> &EphValues) { 46 // Note: We don't speculate PHIs here, so we'll miss instruction chains kept 47 // alive only by ephemeral values. 48 49 // Walk the worklist using an index but without caching the size so we can 50 // append more entries as we process the worklist. This forms a queue without 51 // quadratic behavior by just leaving processed nodes at the head of the 52 // worklist forever. 53 for (int i = 0; i < (int)Worklist.size(); ++i) { 54 const Value *V = Worklist[i]; 55 56 assert(Visited.count(V) && 57 "Failed to add a worklist entry to our visited set!"); 58 59 // If all uses of this value are ephemeral, then so is this value. 60 if (!all_of(V->users(), [&](const User *U) { return EphValues.count(U); })) 61 continue; 62 63 EphValues.insert(V); 64 LLVM_DEBUG(dbgs() << "Ephemeral Value: " << *V << "\n"); 65 66 // Append any more operands to consider. 67 appendSpeculatableOperands(V, Visited, Worklist); 68 } 69 } 70 71 // Find all ephemeral values. 72 void CodeMetrics::collectEphemeralValues( 73 const Loop *L, AssumptionCache *AC, 74 SmallPtrSetImpl<const Value *> &EphValues) { 75 SmallPtrSet<const Value *, 32> Visited; 76 SmallVector<const Value *, 16> Worklist; 77 78 for (auto &AssumeVH : AC->assumptions()) { 79 if (!AssumeVH) 80 continue; 81 Instruction *I = cast<Instruction>(AssumeVH); 82 83 // Filter out call sites outside of the loop so we don't do a function's 84 // worth of work for each of its loops (and, in the common case, ephemeral 85 // values in the loop are likely due to @llvm.assume calls in the loop). 86 if (!L->contains(I->getParent())) 87 continue; 88 89 if (EphValues.insert(I).second) 90 appendSpeculatableOperands(I, Visited, Worklist); 91 } 92 93 completeEphemeralValues(Visited, Worklist, EphValues); 94 } 95 96 void CodeMetrics::collectEphemeralValues( 97 const Function *F, AssumptionCache *AC, 98 SmallPtrSetImpl<const Value *> &EphValues) { 99 SmallPtrSet<const Value *, 32> Visited; 100 SmallVector<const Value *, 16> Worklist; 101 102 for (auto &AssumeVH : AC->assumptions()) { 103 if (!AssumeVH) 104 continue; 105 Instruction *I = cast<Instruction>(AssumeVH); 106 assert(I->getParent()->getParent() == F && 107 "Found assumption for the wrong function!"); 108 109 if (EphValues.insert(I).second) 110 appendSpeculatableOperands(I, Visited, Worklist); 111 } 112 113 completeEphemeralValues(Visited, Worklist, EphValues); 114 } 115 116 /// Fill in the current structure with information gleaned from the specified 117 /// block. 118 void CodeMetrics::analyzeBasicBlock(const BasicBlock *BB, 119 const TargetTransformInfo &TTI, 120 const SmallPtrSetImpl<const Value*> &EphValues) { 121 ++NumBlocks; 122 unsigned NumInstsBeforeThisBB = NumInsts; 123 for (const Instruction &I : *BB) { 124 // Skip ephemeral values. 125 if (EphValues.count(&I)) 126 continue; 127 128 // Special handling for calls. 129 if (isa<CallInst>(I) || isa<InvokeInst>(I)) { 130 ImmutableCallSite CS(&I); 131 132 if (const Function *F = CS.getCalledFunction()) { 133 // If a function is both internal and has a single use, then it is 134 // extremely likely to get inlined in the future (it was probably 135 // exposed by an interleaved devirtualization pass). 136 if (!CS.isNoInline() && F->hasInternalLinkage() && F->hasOneUse()) 137 ++NumInlineCandidates; 138 139 // If this call is to function itself, then the function is recursive. 140 // Inlining it into other functions is a bad idea, because this is 141 // basically just a form of loop peeling, and our metrics aren't useful 142 // for that case. 143 if (F == BB->getParent()) 144 isRecursive = true; 145 146 if (TTI.isLoweredToCall(F)) 147 ++NumCalls; 148 } else { 149 // We don't want inline asm to count as a call - that would prevent loop 150 // unrolling. The argument setup cost is still real, though. 151 if (!isa<InlineAsm>(CS.getCalledValue())) 152 ++NumCalls; 153 } 154 } 155 156 if (const AllocaInst *AI = dyn_cast<AllocaInst>(&I)) { 157 if (!AI->isStaticAlloca()) 158 this->usesDynamicAlloca = true; 159 } 160 161 if (isa<ExtractElementInst>(I) || I.getType()->isVectorTy()) 162 ++NumVectorInsts; 163 164 if (I.getType()->isTokenTy() && I.isUsedOutsideOfBlock(BB)) 165 notDuplicatable = true; 166 167 if (const CallInst *CI = dyn_cast<CallInst>(&I)) { 168 if (CI->cannotDuplicate()) 169 notDuplicatable = true; 170 if (CI->isConvergent()) 171 convergent = true; 172 } 173 174 if (const InvokeInst *InvI = dyn_cast<InvokeInst>(&I)) 175 if (InvI->cannotDuplicate()) 176 notDuplicatable = true; 177 178 NumInsts += TTI.getUserCost(&I); 179 } 180 181 if (isa<ReturnInst>(BB->getTerminator())) 182 ++NumRets; 183 184 // We never want to inline functions that contain an indirectbr. This is 185 // incorrect because all the blockaddress's (in static global initializers 186 // for example) would be referring to the original function, and this indirect 187 // jump would jump from the inlined copy of the function into the original 188 // function which is extremely undefined behavior. 189 // FIXME: This logic isn't really right; we can safely inline functions 190 // with indirectbr's as long as no other function or global references the 191 // blockaddress of a block within the current function. And as a QOI issue, 192 // if someone is using a blockaddress without an indirectbr, and that 193 // reference somehow ends up in another function or global, we probably 194 // don't want to inline this function. 195 notDuplicatable |= isa<IndirectBrInst>(BB->getTerminator()); 196 197 // Remember NumInsts for this BB. 198 NumBBInsts[BB] = NumInsts - NumInstsBeforeThisBB; 199 } 200
