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