lib/Analysis/CodeMetrics.cpp

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