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/AssumptionTracker.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
  25 #define DEBUG_TYPE "code-metrics"
  26
  27 using namespace llvm;
  28
  29 static void completeEphemeralValues(SmallVector<const Value *, 16> &WorkSet,
  30                                     SmallPtrSetImpl<const Value*> &EphValues) {
  31   SmallPtrSet<const Value *, 32> Visited;
  32
  33   // Make sure that all of the items in WorkSet are in our EphValues set.
  34   EphValues.insert(WorkSet.begin(), WorkSet.end());
  35
  36   // Note: We don't speculate PHIs here, so we'll miss instruction chains kept
  37   // alive only by ephemeral values.
  38
  39   while (!WorkSet.empty()) {
  40     const Value *V = WorkSet.pop_back_val();
  41     if (!Visited.insert(V))
  42       continue;
  43
  44     // If all uses of this value are ephemeral, then so is this value.
  45     bool FoundNEUse = false;
  46     for (const User *I : V->users())
  47       if (!EphValues.count(I)) {
  48         FoundNEUse = true;
  49         break;
  50       }
  51
  52     if (FoundNEUse)
  53       continue;
  54
  55     EphValues.insert(V);
  56     DEBUG(dbgs() << "Ephemeral Value: " << *V << "\n");
  57
  58     if (const User *U = dyn_cast<User>(V))
  59       for (const Value *J : U->operands()) {
  60         if (isSafeToSpeculativelyExecute(J))
  61           WorkSet.push_back(J);
  62       }
  63   }
  64 }
  65
  66 // Find all ephemeral values.
  67 void CodeMetrics::collectEphemeralValues(const Loop *L, AssumptionTracker *AT,
  68                                          SmallPtrSetImpl<const Value*> &EphValues) {
  69   SmallVector<const Value *, 16> WorkSet;
  70
  71   for (auto &I : AT->assumptions(L->getHeader()->getParent())) {
  72     // Filter out call sites outside of the loop so we don't to a function's
  73     // worth of work for each of its loops (and, in the common case, ephemeral
  74     // values in the loop are likely due to @llvm.assume calls in the loop).
  75     if (!L->contains(I->getParent()))
  76       continue;
  77
  78     WorkSet.push_back(I);
  79   }
  80
  81   completeEphemeralValues(WorkSet, EphValues);
  82 }
  83
  84 void CodeMetrics::collectEphemeralValues(const Function *F, AssumptionTracker *AT,
  85                                          SmallPtrSetImpl<const Value*> &EphValues) {
  86   SmallVector<const Value *, 16> WorkSet;
  87
  88   for (auto &I : AT->assumptions(const_cast<Function*>(F)))
  89     WorkSet.push_back(I);
  90
  91   completeEphemeralValues(WorkSet, EphValues);
  92 }
  93
  94 /// analyzeBasicBlock - Fill in the current structure with information gleaned
  95 /// from the specified block.
  96 void CodeMetrics::analyzeBasicBlock(const BasicBlock *BB,
  97                                     const TargetTransformInfo &TTI,
  98                                     SmallPtrSetImpl<const Value*> &EphValues) {
  99   ++NumBlocks;
 100   unsigned NumInstsBeforeThisBB = NumInsts;
 101   for (BasicBlock::const_iterator II = BB->begin(), E = BB->end();
 102        II != E; ++II) {
 103     // Skip ephemeral values.
 104     if (EphValues.count(II))
 105       continue;
 106
 107     // Special handling for calls.
 108     if (isa<CallInst>(II) || isa<InvokeInst>(II)) {
 109       ImmutableCallSite CS(cast<Instruction>(II));
 110
 111       if (const Function *F = CS.getCalledFunction()) {
 112         // If a function is both internal and has a single use, then it is
 113         // extremely likely to get inlined in the future (it was probably
 114         // exposed by an interleaved devirtualization pass).
 115         if (!CS.isNoInline() && F->hasInternalLinkage() && F->hasOneUse())
 116           ++NumInlineCandidates;
 117
 118         // If this call is to function itself, then the function is recursive.
 119         // Inlining it into other functions is a bad idea, because this is
 120         // basically just a form of loop peeling, and our metrics aren't useful
 121         // for that case.
 122         if (F == BB->getParent())
 123           isRecursive = true;
 124
 125         if (TTI.isLoweredToCall(F))
 126           ++NumCalls;
 127       } else {
 128         // We don't want inline asm to count as a call - that would prevent loop
 129         // unrolling. The argument setup cost is still real, though.
 130         if (!isa<InlineAsm>(CS.getCalledValue()))
 131           ++NumCalls;
 132       }
 133     }
 134
 135     if (const AllocaInst *AI = dyn_cast<AllocaInst>(II)) {
 136       if (!AI->isStaticAlloca())
 137         this->usesDynamicAlloca = true;
 138     }
 139
 140     if (isa<ExtractElementInst>(II) || II->getType()->isVectorTy())
 141       ++NumVectorInsts;
 142
 143     if (const CallInst *CI = dyn_cast<CallInst>(II))
 144       if (CI->cannotDuplicate())
 145         notDuplicatable = true;
 146
 147     if (const InvokeInst *InvI = dyn_cast<InvokeInst>(II))
 148       if (InvI->cannotDuplicate())
 149         notDuplicatable = true;
 150
 151     NumInsts += TTI.getUserCost(&*II);
 152   }
 153
 154   if (isa<ReturnInst>(BB->getTerminator()))
 155     ++NumRets;
 156
 157   // We never want to inline functions that contain an indirectbr.  This is
 158   // incorrect because all the blockaddress's (in static global initializers
 159   // for example) would be referring to the original function, and this indirect
 160   // jump would jump from the inlined copy of the function into the original
 161   // function which is extremely undefined behavior.
 162   // FIXME: This logic isn't really right; we can safely inline functions
 163   // with indirectbr's as long as no other function or global references the
 164   // blockaddress of a block within the current function.  And as a QOI issue,
 165   // if someone is using a blockaddress without an indirectbr, and that
 166   // reference somehow ends up in another function or global, we probably
 167   // don't want to inline this function.
 168   notDuplicatable |= isa<IndirectBrInst>(BB->getTerminator());
 169
 170   // Remember NumInsts for this BB.
 171   NumBBInsts[BB] = NumInsts - NumInstsBeforeThisBB;
 172 }