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