LCOV - code coverage report
Current view: top level - lib/Analysis - CodeMetrics.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 56 59 94.9 %
Date: 2018-10-20 13:21:21 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         127 : 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         394 :   for (const Value *Operand : U->operands())
      38         267 :     if (Visited.insert(Operand).second)
      39         190 :       if (isSafeToSpeculativelyExecute(Operand))
      40         105 :         Worklist.push_back(Operand);
      41             : }
      42             : 
      43      345281 : 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      345386 :   for (int i = 0; i < (int)Worklist.size(); ++i) {
      54         105 :     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         323 :     if (!all_of(V->users(), [&](const User *U) { return EphValues.count(U); }))
      61             :       continue;
      62             : 
      63         105 :     EphValues.insert(V);
      64             :     LLVM_DEBUG(dbgs() << "Ephemeral Value: " << *V << "\n");
      65             : 
      66             :     // Append any more operands to consider.
      67         105 :     appendSpeculatableOperands(V, Visited, Worklist);
      68             :   }
      69      345281 : }
      70             : 
      71             : // Find all ephemeral values.
      72       26530 : 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       26542 :   for (auto &AssumeVH : AC->assumptions()) {
      79          12 :     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          12 :     if (!L->contains(I->getParent()))
      87             :       continue;
      88             : 
      89          12 :     if (EphValues.insert(I).second)
      90          12 :       appendSpeculatableOperands(I, Visited, Worklist);
      91             :   }
      92             : 
      93       26530 :   completeEphemeralValues(Visited, Worklist, EphValues);
      94       26530 : }
      95             : 
      96      318751 : 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      318762 :   for (auto &AssumeVH : AC->assumptions()) {
     103          11 :     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          10 :     if (EphValues.insert(I).second)
     110          10 :       appendSpeculatableOperands(I, Visited, Worklist);
     111             :   }
     112             : 
     113      318751 :   completeEphemeralValues(Visited, Worklist, EphValues);
     114      318751 : }
     115             : 
     116             : /// Fill in the current structure with information gleaned from the specified
     117             : /// block.
     118      120675 : void CodeMetrics::analyzeBasicBlock(const BasicBlock *BB,
     119             :                                     const TargetTransformInfo &TTI,
     120             :                                     const SmallPtrSetImpl<const Value*> &EphValues) {
     121      120675 :   ++NumBlocks;
     122      120675 :   unsigned NumInstsBeforeThisBB = NumInsts;
     123     1439416 :   for (const Instruction &I : *BB) {
     124             :     // Skip ephemeral values.
     125     1318741 :     if (EphValues.count(&I))
     126             :       continue;
     127             : 
     128             :     // Special handling for calls.
     129     1318713 :     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      205579 :         if (!CS.isNoInline() && F->hasInternalLinkage() && F->hasOneUse())
     137           1 :           ++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      205579 :         if (F == BB->getParent())
     144         348 :           isRecursive = true;
     145             : 
     146      205579 :         if (TTI.isLoweredToCall(F))
     147       37374 :           ++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        4904 :         if (!isa<InlineAsm>(CS.getCalledValue()))
     152        4452 :           ++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     1318713 :     if (isa<ExtractElementInst>(I) || I.getType()->isVectorTy())
     162       41591 :       ++NumVectorInsts;
     163             : 
     164     2637426 :     if (I.getType()->isTokenTy() && I.isUsedOutsideOfBlock(BB))
     165           0 :       notDuplicatable = true;
     166             : 
     167             :     if (const CallInst *CI = dyn_cast<CallInst>(&I)) {
     168      185305 :       if (CI->cannotDuplicate())
     169           7 :         notDuplicatable = true;
     170      185305 :       if (CI->isConvergent())
     171          15 :         convergent = true;
     172             :     }
     173             : 
     174             :     if (const InvokeInst *InvI = dyn_cast<InvokeInst>(&I))
     175       25178 :       if (InvI->cannotDuplicate())
     176           0 :         notDuplicatable = true;
     177             : 
     178     1318713 :     NumInsts += TTI.getUserCost(&I);
     179             :   }
     180             : 
     181      241350 :   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      120675 :   notDuplicatable |= isa<IndirectBrInst>(BB->getTerminator());
     196             : 
     197             :   // Remember NumInsts for this BB.
     198      120675 :   NumBBInsts[BB] = NumInsts - NumInstsBeforeThisBB;
     199      120675 : }

Generated by: LCOV version 1.13