LCOV - code coverage report
Current view: top level - lib/Analysis - CodeMetrics.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 57 64 89.1 %
Date: 2018-02-23 15:42:53 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/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         115 : 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         601 :   for (const Value *Operand : U->operands())
      38         243 :     if (Visited.insert(Operand).second)
      39         166 :       if (isSafeToSpeculativelyExecute(Operand))
      40          97 :         Worklist.push_back(Operand);
      41             : }
      42             : 
      43      266231 : 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      266425 :   for (int i = 0; i < (int)Worklist.size(); ++i) {
      54         194 :     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         299 :     if (!all_of(V->users(), [&](const User *U) { return EphValues.count(U); }))
      61           0 :       continue;
      62             : 
      63          97 :     EphValues.insert(V);
      64             :     DEBUG(dbgs() << "Ephemeral Value: " << *V << "\n");
      65             : 
      66             :     // Append any more operands to consider.
      67          97 :     appendSpeculatableOperands(V, Visited, Worklist);
      68             :   }
      69      266231 : }
      70             : 
      71             : // Find all ephemeral values.
      72       19896 : 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       19914 :   for (auto &AssumeVH : AC->assumptions()) {
      79           9 :     if (!AssumeVH)
      80           0 :       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          18 :     if (!L->contains(I->getParent()))
      87           0 :       continue;
      88             : 
      89           9 :     if (EphValues.insert(I).second)
      90           9 :       appendSpeculatableOperands(I, Visited, Worklist);
      91             :   }
      92             : 
      93       19896 :   completeEphemeralValues(Visited, Worklist, EphValues);
      94       19896 : }
      95             : 
      96      246335 : 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      246356 :   for (auto &AssumeVH : AC->assumptions()) {
     103          10 :     if (!AssumeVH)
     104           1 :       continue;
     105             :     Instruction *I = cast<Instruction>(AssumeVH);
     106             :     assert(I->getParent()->getParent() == F &&
     107             :            "Found assumption for the wrong function!");
     108             : 
     109           9 :     if (EphValues.insert(I).second)
     110           9 :       appendSpeculatableOperands(I, Visited, Worklist);
     111             :   }
     112             : 
     113      246336 :   completeEphemeralValues(Visited, Worklist, EphValues);
     114      246336 : }
     115             : 
     116             : /// Fill in the current structure with information gleaned from the specified
     117             : /// block.
     118       80046 : void CodeMetrics::analyzeBasicBlock(const BasicBlock *BB,
     119             :                                     const TargetTransformInfo &TTI,
     120             :                                     const SmallPtrSetImpl<const Value*> &EphValues) {
     121       80046 :   ++NumBlocks;
     122       80046 :   unsigned NumInstsBeforeThisBB = NumInsts;
     123     1156776 :   for (const Instruction &I : *BB) {
     124             :     // Skip ephemeral values.
     125      996684 :     if (EphValues.count(&I))
     126          24 :       continue;
     127             : 
     128             :     // Special handling for calls.
     129      996660 :     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      286966 :         if (!CS.isNoInline() && F->hasInternalLinkage() && F->hasOneUse())
     137           0 :           ++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      154360 :         if (F == BB->getParent())
     144         156 :           isRecursive = true;
     145             : 
     146      154360 :         if (TTI.isLoweredToCall(F))
     147       57478 :           ++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         756 :         if (!isa<InlineAsm>(CS.getCalledValue()))
     152         304 :           ++NumCalls;
     153             :       }
     154             :     }
     155             : 
     156             :     if (const AllocaInst *AI = dyn_cast<AllocaInst>(&I)) {
     157           1 :       if (!AI->isStaticAlloca())
     158           1 :         this->usesDynamicAlloca = true;
     159             :     }
     160             : 
     161     1993244 :     if (isa<ExtractElementInst>(I) || I.getType()->isVectorTy())
     162       35680 :       ++NumVectorInsts;
     163             : 
     164     1993320 :     if (I.getType()->isTokenTy() && I.isUsedOutsideOfBlock(BB))
     165           0 :       notDuplicatable = true;
     166             : 
     167             :     if (const CallInst *CI = dyn_cast<CallInst>(&I)) {
     168      271466 :       if (CI->cannotDuplicate())
     169           6 :         notDuplicatable = true;
     170      135733 :       if (CI->isConvergent())
     171          10 :         convergent = true;
     172             :     }
     173             : 
     174             :     if (const InvokeInst *InvI = dyn_cast<InvokeInst>(&I))
     175       38766 :       if (InvI->cannotDuplicate())
     176           0 :         notDuplicatable = true;
     177             : 
     178      996660 :     NumInsts += TTI.getUserCost(&I);
     179             :   }
     180             : 
     181      160092 :   if (isa<ReturnInst>(BB->getTerminator()))
     182           0 :     ++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      160092 :   notDuplicatable |= isa<IndirectBrInst>(BB->getTerminator());
     196             : 
     197             :   // Remember NumInsts for this BB.
     198      160092 :   NumBBInsts[BB] = NumInsts - NumInstsBeforeThisBB;
     199       80046 : }

Generated by: LCOV version 1.13