LCOV - code coverage report
Current view: top level - lib/Analysis - CodeMetrics.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 69 76 90.8 %
Date: 2017-09-14 15:23:50 Functions: 5 5 100.0 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13