CodeMetrics.cpp revision f3ef5332fa3f4d5ec72c178a2b19dac363a19383
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 28using namespace llvm; 29 30static 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. 64void 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 86void 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/// analyzeBasicBlock - Fill in the current structure with information gleaned 104/// from the specified block. 105void CodeMetrics::analyzeBasicBlock(const BasicBlock *BB, 106 const TargetTransformInfo &TTI, 107 SmallPtrSetImpl<const Value*> &EphValues) { 108 ++NumBlocks; 109 unsigned NumInstsBeforeThisBB = NumInsts; 110 for (BasicBlock::const_iterator II = BB->begin(), E = BB->end(); 111 II != E; ++II) { 112 // Skip ephemeral values. 113 if (EphValues.count(&*II)) 114 continue; 115 116 // Special handling for calls. 117 if (isa<CallInst>(II) || isa<InvokeInst>(II)) { 118 ImmutableCallSite CS(cast<Instruction>(II)); 119 120 if (const Function *F = CS.getCalledFunction()) { 121 // If a function is both internal and has a single use, then it is 122 // extremely likely to get inlined in the future (it was probably 123 // exposed by an interleaved devirtualization pass). 124 if (!CS.isNoInline() && F->hasInternalLinkage() && F->hasOneUse()) 125 ++NumInlineCandidates; 126 127 // If this call is to function itself, then the function is recursive. 128 // Inlining it into other functions is a bad idea, because this is 129 // basically just a form of loop peeling, and our metrics aren't useful 130 // for that case. 131 if (F == BB->getParent()) 132 isRecursive = true; 133 134 if (TTI.isLoweredToCall(F)) 135 ++NumCalls; 136 } else { 137 // We don't want inline asm to count as a call - that would prevent loop 138 // unrolling. The argument setup cost is still real, though. 139 if (!isa<InlineAsm>(CS.getCalledValue())) 140 ++NumCalls; 141 } 142 } 143 144 if (const AllocaInst *AI = dyn_cast<AllocaInst>(II)) { 145 if (!AI->isStaticAlloca()) 146 this->usesDynamicAlloca = true; 147 } 148 149 if (isa<ExtractElementInst>(II) || II->getType()->isVectorTy()) 150 ++NumVectorInsts; 151 152 if (II->getType()->isTokenTy() && II->isUsedOutsideOfBlock(BB)) 153 notDuplicatable = true; 154 155 if (const CallInst *CI = dyn_cast<CallInst>(II)) 156 if (CI->cannotDuplicate()) 157 notDuplicatable = true; 158 159 if (const InvokeInst *InvI = dyn_cast<InvokeInst>(II)) 160 if (InvI->cannotDuplicate()) 161 notDuplicatable = true; 162 163 NumInsts += TTI.getUserCost(&*II); 164 } 165 166 if (isa<ReturnInst>(BB->getTerminator())) 167 ++NumRets; 168 169 // We never want to inline functions that contain an indirectbr. This is 170 // incorrect because all the blockaddress's (in static global initializers 171 // for example) would be referring to the original function, and this indirect 172 // jump would jump from the inlined copy of the function into the original 173 // function which is extremely undefined behavior. 174 // FIXME: This logic isn't really right; we can safely inline functions 175 // with indirectbr's as long as no other function or global references the 176 // blockaddress of a block within the current function. And as a QOI issue, 177 // if someone is using a blockaddress without an indirectbr, and that 178 // reference somehow ends up in another function or global, we probably 179 // don't want to inline this function. 180 notDuplicatable |= isa<IndirectBrInst>(BB->getTerminator()); 181 182 // Remember NumInsts for this BB. 183 NumBBInsts[BB] = NumInsts - NumInstsBeforeThisBB; 184} 185