llvm/lib/Analysis/CodeMetrics.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-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/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
  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 (const auto *I = dyn_cast<Instruction>(Operand))
  38         if (!I->mayHaveSideEffects() && !I->isTerminator())
  39           Worklist.push_back(I);
  40 }
  41
  42 static 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 kept
  46   // alive only by ephemeral values.
  47
  48   // Walk the worklist using an index but without caching the size so we can
  49   // append more entries as we process the worklist. This forms a queue without
  50   // quadratic behavior by just leaving processed nodes at the head of the
  51   // 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.
  71 void 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's
  83     // worth of work for each of its loops (and, in the common case, ephemeral
  84     // 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
  95 void 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
 115 static 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 specified
 128 /// block.
 129 void 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 is
 145         // extremely likely to get inlined in the future (it was probably
 146         // exposed by an interleaved devirtualization pass).
 147         // When preparing for LTO, liberally consider calls as inline
 148         // 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 is
 157         // basically just a form of loop peeling, and our metrics aren't useful
 158         // 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 loop
 166         // 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() << I
 183                         << "\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 -> ExtendedLoop
 195       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 is
 220   // incorrect because all the blockaddress's (in static global initializers
 221   // for example) would be referring to the original function, and this indirect
 222   // jump would jump from the inlined copy of the function into the original
 223   // function which is extremely undefined behavior.
 224   // FIXME: This logic isn't really right; we can safely inline functions
 225   // with indirectbr's as long as no other function or global references the
 226   // blockaddress of a block within the current function.  And as a QOI issue,
 227   // if someone is using a blockaddress without an indirectbr, and that
 228   // reference somehow ends up in another function or global, we probably
 229   // 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 }