10b57cec5SDimitry Andric //===- CodeMetrics.cpp - Code cost measurements ---------------------------===// 20b57cec5SDimitry Andric // 30b57cec5SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 40b57cec5SDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 50b57cec5SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 60b57cec5SDimitry Andric // 70b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 80b57cec5SDimitry Andric // 90b57cec5SDimitry Andric // This file implements code cost measurement utilities. 100b57cec5SDimitry Andric // 110b57cec5SDimitry Andric //===----------------------------------------------------------------------===// 120b57cec5SDimitry Andric 130b57cec5SDimitry Andric #include "llvm/Analysis/CodeMetrics.h" 145ffd83dbSDimitry Andric #include "llvm/ADT/SmallPtrSet.h" 150b57cec5SDimitry Andric #include "llvm/Analysis/AssumptionCache.h" 160b57cec5SDimitry Andric #include "llvm/Analysis/LoopInfo.h" 170b57cec5SDimitry Andric #include "llvm/Analysis/TargetTransformInfo.h" 180b57cec5SDimitry Andric #include "llvm/Analysis/ValueTracking.h" 190b57cec5SDimitry Andric #include "llvm/IR/Function.h" 200b57cec5SDimitry Andric #include "llvm/Support/Debug.h" 210b57cec5SDimitry Andric 220b57cec5SDimitry Andric #define DEBUG_TYPE "code-metrics" 230b57cec5SDimitry Andric 240b57cec5SDimitry Andric using namespace llvm; 250b57cec5SDimitry Andric 260b57cec5SDimitry Andric static void 270b57cec5SDimitry Andric appendSpeculatableOperands(const Value *V, 280b57cec5SDimitry Andric SmallPtrSetImpl<const Value *> &Visited, 290b57cec5SDimitry Andric SmallVectorImpl<const Value *> &Worklist) { 300b57cec5SDimitry Andric const User *U = dyn_cast<User>(V); 310b57cec5SDimitry Andric if (!U) 320b57cec5SDimitry Andric return; 330b57cec5SDimitry Andric 340b57cec5SDimitry Andric for (const Value *Operand : U->operands()) 350b57cec5SDimitry Andric if (Visited.insert(Operand).second) 360b57cec5SDimitry Andric if (isSafeToSpeculativelyExecute(Operand)) 370b57cec5SDimitry Andric Worklist.push_back(Operand); 380b57cec5SDimitry Andric } 390b57cec5SDimitry Andric 400b57cec5SDimitry Andric static void completeEphemeralValues(SmallPtrSetImpl<const Value *> &Visited, 410b57cec5SDimitry Andric SmallVectorImpl<const Value *> &Worklist, 420b57cec5SDimitry Andric SmallPtrSetImpl<const Value *> &EphValues) { 430b57cec5SDimitry Andric // Note: We don't speculate PHIs here, so we'll miss instruction chains kept 440b57cec5SDimitry Andric // alive only by ephemeral values. 450b57cec5SDimitry Andric 460b57cec5SDimitry Andric // Walk the worklist using an index but without caching the size so we can 470b57cec5SDimitry Andric // append more entries as we process the worklist. This forms a queue without 480b57cec5SDimitry Andric // quadratic behavior by just leaving processed nodes at the head of the 490b57cec5SDimitry Andric // worklist forever. 500b57cec5SDimitry Andric for (int i = 0; i < (int)Worklist.size(); ++i) { 510b57cec5SDimitry Andric const Value *V = Worklist[i]; 520b57cec5SDimitry Andric 530b57cec5SDimitry Andric assert(Visited.count(V) && 540b57cec5SDimitry Andric "Failed to add a worklist entry to our visited set!"); 550b57cec5SDimitry Andric 560b57cec5SDimitry Andric // If all uses of this value are ephemeral, then so is this value. 570b57cec5SDimitry Andric if (!all_of(V->users(), [&](const User *U) { return EphValues.count(U); })) 580b57cec5SDimitry Andric continue; 590b57cec5SDimitry Andric 600b57cec5SDimitry Andric EphValues.insert(V); 610b57cec5SDimitry Andric LLVM_DEBUG(dbgs() << "Ephemeral Value: " << *V << "\n"); 620b57cec5SDimitry Andric 630b57cec5SDimitry Andric // Append any more operands to consider. 640b57cec5SDimitry Andric appendSpeculatableOperands(V, Visited, Worklist); 650b57cec5SDimitry Andric } 660b57cec5SDimitry Andric } 670b57cec5SDimitry Andric 680b57cec5SDimitry Andric // Find all ephemeral values. 690b57cec5SDimitry Andric void CodeMetrics::collectEphemeralValues( 700b57cec5SDimitry Andric const Loop *L, AssumptionCache *AC, 710b57cec5SDimitry Andric SmallPtrSetImpl<const Value *> &EphValues) { 720b57cec5SDimitry Andric SmallPtrSet<const Value *, 32> Visited; 730b57cec5SDimitry Andric SmallVector<const Value *, 16> Worklist; 740b57cec5SDimitry Andric 750b57cec5SDimitry Andric for (auto &AssumeVH : AC->assumptions()) { 760b57cec5SDimitry Andric if (!AssumeVH) 770b57cec5SDimitry Andric continue; 780b57cec5SDimitry Andric Instruction *I = cast<Instruction>(AssumeVH); 790b57cec5SDimitry Andric 800b57cec5SDimitry Andric // Filter out call sites outside of the loop so we don't do a function's 810b57cec5SDimitry Andric // worth of work for each of its loops (and, in the common case, ephemeral 820b57cec5SDimitry Andric // values in the loop are likely due to @llvm.assume calls in the loop). 830b57cec5SDimitry Andric if (!L->contains(I->getParent())) 840b57cec5SDimitry Andric continue; 850b57cec5SDimitry Andric 860b57cec5SDimitry Andric if (EphValues.insert(I).second) 870b57cec5SDimitry Andric appendSpeculatableOperands(I, Visited, Worklist); 880b57cec5SDimitry Andric } 890b57cec5SDimitry Andric 900b57cec5SDimitry Andric completeEphemeralValues(Visited, Worklist, EphValues); 910b57cec5SDimitry Andric } 920b57cec5SDimitry Andric 930b57cec5SDimitry Andric void CodeMetrics::collectEphemeralValues( 940b57cec5SDimitry Andric const Function *F, AssumptionCache *AC, 950b57cec5SDimitry Andric SmallPtrSetImpl<const Value *> &EphValues) { 960b57cec5SDimitry Andric SmallPtrSet<const Value *, 32> Visited; 970b57cec5SDimitry Andric SmallVector<const Value *, 16> Worklist; 980b57cec5SDimitry Andric 990b57cec5SDimitry Andric for (auto &AssumeVH : AC->assumptions()) { 1000b57cec5SDimitry Andric if (!AssumeVH) 1010b57cec5SDimitry Andric continue; 1020b57cec5SDimitry Andric Instruction *I = cast<Instruction>(AssumeVH); 1030b57cec5SDimitry Andric assert(I->getParent()->getParent() == F && 1040b57cec5SDimitry Andric "Found assumption for the wrong function!"); 1050b57cec5SDimitry Andric 1060b57cec5SDimitry Andric if (EphValues.insert(I).second) 1070b57cec5SDimitry Andric appendSpeculatableOperands(I, Visited, Worklist); 1080b57cec5SDimitry Andric } 1090b57cec5SDimitry Andric 1100b57cec5SDimitry Andric completeEphemeralValues(Visited, Worklist, EphValues); 1110b57cec5SDimitry Andric } 1120b57cec5SDimitry Andric 1130b57cec5SDimitry Andric /// Fill in the current structure with information gleaned from the specified 1140b57cec5SDimitry Andric /// block. 115e8d8bef9SDimitry Andric void CodeMetrics::analyzeBasicBlock( 116e8d8bef9SDimitry Andric const BasicBlock *BB, const TargetTransformInfo &TTI, 117e8d8bef9SDimitry Andric const SmallPtrSetImpl<const Value *> &EphValues, bool PrepareForLTO) { 1180b57cec5SDimitry Andric ++NumBlocks; 1190b57cec5SDimitry Andric unsigned NumInstsBeforeThisBB = NumInsts; 1200b57cec5SDimitry Andric for (const Instruction &I : *BB) { 1210b57cec5SDimitry Andric // Skip ephemeral values. 1220b57cec5SDimitry Andric if (EphValues.count(&I)) 1230b57cec5SDimitry Andric continue; 1240b57cec5SDimitry Andric 1250b57cec5SDimitry Andric // Special handling for calls. 1260b57cec5SDimitry Andric if (const auto *Call = dyn_cast<CallBase>(&I)) { 1270b57cec5SDimitry Andric if (const Function *F = Call->getCalledFunction()) { 128e8d8bef9SDimitry Andric bool IsLoweredToCall = TTI.isLoweredToCall(F); 1290b57cec5SDimitry Andric // If a function is both internal and has a single use, then it is 1300b57cec5SDimitry Andric // extremely likely to get inlined in the future (it was probably 1310b57cec5SDimitry Andric // exposed by an interleaved devirtualization pass). 132e8d8bef9SDimitry Andric // When preparing for LTO, liberally consider calls as inline 133e8d8bef9SDimitry Andric // candidates. 134e8d8bef9SDimitry Andric if (!Call->isNoInline() && IsLoweredToCall && 135e8d8bef9SDimitry Andric ((F->hasInternalLinkage() && F->hasOneUse()) || PrepareForLTO)) { 1360b57cec5SDimitry Andric ++NumInlineCandidates; 137e8d8bef9SDimitry Andric } 1380b57cec5SDimitry Andric 1390b57cec5SDimitry Andric // If this call is to function itself, then the function is recursive. 1400b57cec5SDimitry Andric // Inlining it into other functions is a bad idea, because this is 1410b57cec5SDimitry Andric // basically just a form of loop peeling, and our metrics aren't useful 1420b57cec5SDimitry Andric // for that case. 1430b57cec5SDimitry Andric if (F == BB->getParent()) 1440b57cec5SDimitry Andric isRecursive = true; 1450b57cec5SDimitry Andric 146e8d8bef9SDimitry Andric if (IsLoweredToCall) 1470b57cec5SDimitry Andric ++NumCalls; 1480b57cec5SDimitry Andric } else { 1490b57cec5SDimitry Andric // We don't want inline asm to count as a call - that would prevent loop 1500b57cec5SDimitry Andric // unrolling. The argument setup cost is still real, though. 1510b57cec5SDimitry Andric if (!Call->isInlineAsm()) 1520b57cec5SDimitry Andric ++NumCalls; 1530b57cec5SDimitry Andric } 1540b57cec5SDimitry Andric } 1550b57cec5SDimitry Andric 1560b57cec5SDimitry Andric if (const AllocaInst *AI = dyn_cast<AllocaInst>(&I)) { 1570b57cec5SDimitry Andric if (!AI->isStaticAlloca()) 1580b57cec5SDimitry Andric this->usesDynamicAlloca = true; 1590b57cec5SDimitry Andric } 1600b57cec5SDimitry Andric 1610b57cec5SDimitry Andric if (isa<ExtractElementInst>(I) || I.getType()->isVectorTy()) 1620b57cec5SDimitry Andric ++NumVectorInsts; 1630b57cec5SDimitry Andric 1640b57cec5SDimitry Andric if (I.getType()->isTokenTy() && I.isUsedOutsideOfBlock(BB)) 1650b57cec5SDimitry Andric notDuplicatable = true; 1660b57cec5SDimitry Andric 1670b57cec5SDimitry Andric if (const CallInst *CI = dyn_cast<CallInst>(&I)) { 1680b57cec5SDimitry Andric if (CI->cannotDuplicate()) 1690b57cec5SDimitry Andric notDuplicatable = true; 1700b57cec5SDimitry Andric if (CI->isConvergent()) 1710b57cec5SDimitry Andric convergent = true; 1720b57cec5SDimitry Andric } 1730b57cec5SDimitry Andric 1740b57cec5SDimitry Andric if (const InvokeInst *InvI = dyn_cast<InvokeInst>(&I)) 1750b57cec5SDimitry Andric if (InvI->cannotDuplicate()) 1760b57cec5SDimitry Andric notDuplicatable = true; 1770b57cec5SDimitry Andric 1785ffd83dbSDimitry Andric NumInsts += TTI.getUserCost(&I, TargetTransformInfo::TCK_CodeSize); 1790b57cec5SDimitry Andric } 1800b57cec5SDimitry Andric 1810b57cec5SDimitry Andric if (isa<ReturnInst>(BB->getTerminator())) 1820b57cec5SDimitry Andric ++NumRets; 1830b57cec5SDimitry Andric 1840b57cec5SDimitry Andric // We never want to inline functions that contain an indirectbr. This is 1850b57cec5SDimitry Andric // incorrect because all the blockaddress's (in static global initializers 1860b57cec5SDimitry Andric // for example) would be referring to the original function, and this indirect 1870b57cec5SDimitry Andric // jump would jump from the inlined copy of the function into the original 1880b57cec5SDimitry Andric // function which is extremely undefined behavior. 1890b57cec5SDimitry Andric // FIXME: This logic isn't really right; we can safely inline functions 1900b57cec5SDimitry Andric // with indirectbr's as long as no other function or global references the 1910b57cec5SDimitry Andric // blockaddress of a block within the current function. And as a QOI issue, 1920b57cec5SDimitry Andric // if someone is using a blockaddress without an indirectbr, and that 1930b57cec5SDimitry Andric // reference somehow ends up in another function or global, we probably 1940b57cec5SDimitry Andric // don't want to inline this function. 1950b57cec5SDimitry Andric notDuplicatable |= isa<IndirectBrInst>(BB->getTerminator()); 1960b57cec5SDimitry Andric 1970b57cec5SDimitry Andric // Remember NumInsts for this BB. 1980b57cec5SDimitry Andric NumBBInsts[BB] = NumInsts - NumInstsBeforeThisBB; 1990b57cec5SDimitry Andric } 200