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