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/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
  28 using namespace llvm;
  29
  30 static 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.
  64 void 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
  86 void 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.
 105 void 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 }