236 lines · cpp
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-exception6//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/IR/Function.h"19#include "llvm/IR/IntrinsicInst.h"20#include "llvm/Support/Debug.h"21#include "llvm/Support/InstructionCost.h"22 23#define DEBUG_TYPE "code-metrics"24 25using namespace llvm;26 27static void28appendSpeculatableOperands(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 (const auto *I = dyn_cast<Instruction>(Operand))38 if (!I->mayHaveSideEffects() && !I->isTerminator())39 Worklist.push_back(I);40}41 42static void completeEphemeralValues(SmallPtrSetImpl<const Value *> &Visited,43 SmallVectorImpl<const Value *> &Worklist,44 SmallPtrSetImpl<const Value *> &EphValues) {45 // Note: We don't speculate PHIs here, so we'll miss instruction chains kept46 // alive only by ephemeral values.47 48 // Walk the worklist using an index but without caching the size so we can49 // append more entries as we process the worklist. This forms a queue without50 // quadratic behavior by just leaving processed nodes at the head of the51 // worklist forever.52 for (int i = 0; i < (int)Worklist.size(); ++i) {53 const Value *V = Worklist[i];54 55 assert(Visited.count(V) &&56 "Failed to add a worklist entry to our visited set!");57 58 // If all uses of this value are ephemeral, then so is this value.59 if (!all_of(V->users(), [&](const User *U) { return EphValues.count(U); }))60 continue;61 62 EphValues.insert(V);63 LLVM_DEBUG(dbgs() << "Ephemeral Value: " << *V << "\n");64 65 // Append any more operands to consider.66 appendSpeculatableOperands(V, Visited, Worklist);67 }68}69 70// Find all ephemeral values.71void CodeMetrics::collectEphemeralValues(72 const Loop *L, AssumptionCache *AC,73 SmallPtrSetImpl<const Value *> &EphValues) {74 SmallPtrSet<const Value *, 32> Visited;75 SmallVector<const Value *, 16> Worklist;76 77 for (auto &AssumeVH : AC->assumptions()) {78 if (!AssumeVH)79 continue;80 Instruction *I = cast<Instruction>(AssumeVH);81 82 // Filter out call sites outside of the loop so we don't do a function's83 // worth of work for each of its loops (and, in the common case, ephemeral84 // values in the loop are likely due to @llvm.assume calls in the loop).85 if (!L->contains(I->getParent()))86 continue;87 88 if (EphValues.insert(I).second)89 appendSpeculatableOperands(I, Visited, Worklist);90 }91 92 completeEphemeralValues(Visited, Worklist, EphValues);93}94 95void CodeMetrics::collectEphemeralValues(96 const Function *F, AssumptionCache *AC,97 SmallPtrSetImpl<const Value *> &EphValues) {98 SmallPtrSet<const Value *, 32> Visited;99 SmallVector<const Value *, 16> Worklist;100 101 for (auto &AssumeVH : AC->assumptions()) {102 if (!AssumeVH)103 continue;104 Instruction *I = cast<Instruction>(AssumeVH);105 assert(I->getParent()->getParent() == F &&106 "Found assumption for the wrong function!");107 108 if (EphValues.insert(I).second)109 appendSpeculatableOperands(I, Visited, Worklist);110 }111 112 completeEphemeralValues(Visited, Worklist, EphValues);113}114 115static bool extendsConvergenceOutsideLoop(const Instruction &I, const Loop *L) {116 if (!L)117 return false;118 if (!isa<ConvergenceControlInst>(I))119 return false;120 for (const auto *U : I.users()) {121 if (!L->contains(cast<Instruction>(U)))122 return true;123 }124 return false;125}126 127/// Fill in the current structure with information gleaned from the specified128/// block.129void CodeMetrics::analyzeBasicBlock(130 const BasicBlock *BB, const TargetTransformInfo &TTI,131 const SmallPtrSetImpl<const Value *> &EphValues, bool PrepareForLTO,132 const Loop *L) {133 ++NumBlocks;134 InstructionCost NumInstsBeforeThisBB = NumInsts;135 for (const Instruction &I : *BB) {136 // Skip ephemeral values.137 if (EphValues.count(&I))138 continue;139 140 // Special handling for calls.141 if (const auto *Call = dyn_cast<CallBase>(&I)) {142 if (const Function *F = Call->getCalledFunction()) {143 bool IsLoweredToCall = TTI.isLoweredToCall(F);144 // If a function is both internal and has a single use, then it is145 // extremely likely to get inlined in the future (it was probably146 // exposed by an interleaved devirtualization pass).147 // When preparing for LTO, liberally consider calls as inline148 // candidates.149 if (!Call->isNoInline() && IsLoweredToCall &&150 ((F->hasInternalLinkage() && F->hasOneLiveUse()) ||151 PrepareForLTO)) {152 ++NumInlineCandidates;153 }154 155 // If this call is to function itself, then the function is recursive.156 // Inlining it into other functions is a bad idea, because this is157 // basically just a form of loop peeling, and our metrics aren't useful158 // for that case.159 if (F == BB->getParent())160 isRecursive = true;161 162 if (IsLoweredToCall)163 ++NumCalls;164 } else {165 // We don't want inline asm to count as a call - that would prevent loop166 // unrolling. The argument setup cost is still real, though.167 if (!Call->isInlineAsm())168 ++NumCalls;169 }170 }171 172 if (const AllocaInst *AI = dyn_cast<AllocaInst>(&I)) {173 if (!AI->isStaticAlloca())174 this->usesDynamicAlloca = true;175 }176 177 if (isa<ExtractElementInst>(I) || I.getType()->isVectorTy())178 ++NumVectorInsts;179 180 if (I.getType()->isTokenTy() && !isa<ConvergenceControlInst>(I) &&181 I.isUsedOutsideOfBlock(BB)) {182 LLVM_DEBUG(dbgs() << I183 << "\n Cannot duplicate a token value used outside "184 "the current block (except convergence control).\n");185 notDuplicatable = true;186 }187 188 if (const CallBase *CB = dyn_cast<CallBase>(&I)) {189 if (CB->cannotDuplicate())190 notDuplicatable = true;191 // Compute a meet over the visited blocks for the following partial order:192 //193 // None -> { Controlled, ExtendedLoop, Uncontrolled}194 // Controlled -> ExtendedLoop195 if (Convergence <= ConvergenceKind::Controlled && CB->isConvergent()) {196 if (isa<ConvergenceControlInst>(CB) ||197 CB->getConvergenceControlToken()) {198 assert(Convergence != ConvergenceKind::Uncontrolled);199 LLVM_DEBUG(dbgs() << "Found controlled convergence:\n" << I << "\n");200 if (extendsConvergenceOutsideLoop(I, L))201 Convergence = ConvergenceKind::ExtendedLoop;202 else {203 assert(Convergence != ConvergenceKind::ExtendedLoop);204 Convergence = ConvergenceKind::Controlled;205 }206 } else {207 assert(Convergence == ConvergenceKind::None);208 Convergence = ConvergenceKind::Uncontrolled;209 }210 }211 }212 213 NumInsts += TTI.getInstructionCost(&I, TargetTransformInfo::TCK_CodeSize);214 }215 216 if (isa<ReturnInst>(BB->getTerminator()))217 ++NumRets;218 219 // We never want to inline functions that contain an indirectbr. This is220 // incorrect because all the blockaddress's (in static global initializers221 // for example) would be referring to the original function, and this indirect222 // jump would jump from the inlined copy of the function into the original223 // function which is extremely undefined behavior.224 // FIXME: This logic isn't really right; we can safely inline functions225 // with indirectbr's as long as no other function or global references the226 // blockaddress of a block within the current function. And as a QOI issue,227 // if someone is using a blockaddress without an indirectbr, and that228 // reference somehow ends up in another function or global, we probably229 // don't want to inline this function.230 notDuplicatable |= isa<IndirectBrInst>(BB->getTerminator());231 232 // Remember NumInsts for this BB.233 InstructionCost NumInstsThisBB = NumInsts - NumInstsBeforeThisBB;234 NumBBInsts[BB] = NumInstsThisBB;235}236