LCOV - code coverage report
Current view: top level - include/llvm/Transforms/Scalar - JumpThreading.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 4 4 100.0 %
Date: 2018-10-17 09:37:48 Functions: 1 1 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- JumpThreading.h - thread control through conditional BBs -*- C++ -*-===//
       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             : /// \file
      11             : /// See the comments on JumpThreadingPass.
      12             : //
      13             : //===----------------------------------------------------------------------===//
      14             : 
      15             : #ifndef LLVM_TRANSFORMS_SCALAR_JUMPTHREADING_H
      16             : #define LLVM_TRANSFORMS_SCALAR_JUMPTHREADING_H
      17             : 
      18             : #include "llvm/ADT/ArrayRef.h"
      19             : #include "llvm/ADT/DenseSet.h"
      20             : #include "llvm/ADT/SmallPtrSet.h"
      21             : #include "llvm/ADT/SmallSet.h"
      22             : #include "llvm/ADT/SmallVector.h"
      23             : #include "llvm/Analysis/AliasAnalysis.h"
      24             : #include "llvm/Analysis/BlockFrequencyInfo.h"
      25             : #include "llvm/Analysis/BranchProbabilityInfo.h"
      26             : #include "llvm/IR/DomTreeUpdater.h"
      27             : #include "llvm/IR/ValueHandle.h"
      28             : #include <memory>
      29             : #include <utility>
      30             : 
      31             : namespace llvm {
      32             : 
      33             : class BasicBlock;
      34             : class BinaryOperator;
      35             : class BranchInst;
      36             : class CmpInst;
      37             : class Constant;
      38             : class DomTreeUpdater;
      39             : class Function;
      40             : class Instruction;
      41             : class IntrinsicInst;
      42             : class LazyValueInfo;
      43             : class LoadInst;
      44             : class PHINode;
      45             : class TargetLibraryInfo;
      46             : class Value;
      47             : 
      48             : /// A private "module" namespace for types and utilities used by
      49             : /// JumpThreading.
      50             : /// These are implementation details and should not be used by clients.
      51             : namespace jumpthreading {
      52             : 
      53             : // These are at global scope so static functions can use them too.
      54             : using PredValueInfo = SmallVectorImpl<std::pair<Constant *, BasicBlock *>>;
      55             : using PredValueInfoTy = SmallVector<std::pair<Constant *, BasicBlock *>, 8>;
      56             : 
      57             : // This is used to keep track of what kind of constant we're currently hoping
      58             : // to find.
      59             : enum ConstantPreference { WantInteger, WantBlockAddress };
      60             : 
      61             : } // end namespace jumpthreading
      62             : 
      63             : /// This pass performs 'jump threading', which looks at blocks that have
      64             : /// multiple predecessors and multiple successors.  If one or more of the
      65             : /// predecessors of the block can be proven to always jump to one of the
      66             : /// successors, we forward the edge from the predecessor to the successor by
      67             : /// duplicating the contents of this block.
      68             : ///
      69             : /// An example of when this can occur is code like this:
      70             : ///
      71             : ///   if () { ...
      72             : ///     X = 4;
      73             : ///   }
      74             : ///   if (X < 3) {
      75             : ///
      76             : /// In this case, the unconditional branch at the end of the first if can be
      77             : /// revectored to the false side of the second if.
      78             : class JumpThreadingPass : public PassInfoMixin<JumpThreadingPass> {
      79             :   TargetLibraryInfo *TLI;
      80             :   LazyValueInfo *LVI;
      81             :   AliasAnalysis *AA;
      82             :   DomTreeUpdater *DTU;
      83             :   std::unique_ptr<BlockFrequencyInfo> BFI;
      84             :   std::unique_ptr<BranchProbabilityInfo> BPI;
      85             :   bool HasProfileData = false;
      86             :   bool HasGuards = false;
      87             : #ifdef NDEBUG
      88             :   SmallPtrSet<const BasicBlock *, 16> LoopHeaders;
      89             : #else
      90             :   SmallSet<AssertingVH<const BasicBlock>, 16> LoopHeaders;
      91             : #endif
      92             :   DenseSet<std::pair<Value *, BasicBlock *>> RecursionSet;
      93             : 
      94             :   unsigned BBDupThreshold;
      95             : 
      96             :   // RAII helper for updating the recursion stack.
      97             :   struct RecursionSetRemover {
      98             :     DenseSet<std::pair<Value *, BasicBlock *>> &TheSet;
      99             :     std::pair<Value *, BasicBlock *> ThePair;
     100             : 
     101             :     RecursionSetRemover(DenseSet<std::pair<Value *, BasicBlock *>> &S,
     102             :                         std::pair<Value *, BasicBlock *> P)
     103      327811 :         : TheSet(S), ThePair(P) {}
     104             : 
     105      327811 :     ~RecursionSetRemover() { TheSet.erase(ThePair); }
     106             :   };
     107             : 
     108             : public:
     109             :   JumpThreadingPass(int T = -1);
     110             : 
     111             :   // Glue for old PM.
     112             :   bool runImpl(Function &F, TargetLibraryInfo *TLI_, LazyValueInfo *LVI_,
     113             :                AliasAnalysis *AA_, DomTreeUpdater *DTU_, bool HasProfileData_,
     114             :                std::unique_ptr<BlockFrequencyInfo> BFI_,
     115             :                std::unique_ptr<BranchProbabilityInfo> BPI_);
     116             : 
     117             :   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
     118             : 
     119       88174 :   void releaseMemory() {
     120             :     BFI.reset();
     121             :     BPI.reset();
     122       88174 :   }
     123             : 
     124             :   void FindLoopHeaders(Function &F);
     125             :   bool ProcessBlock(BasicBlock *BB);
     126             :   bool ThreadEdge(BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs,
     127             :                   BasicBlock *SuccBB);
     128             :   bool DuplicateCondBranchOnPHIIntoPred(
     129             :       BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs);
     130             : 
     131             :   bool
     132             :   ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB,
     133             :                                   jumpthreading::PredValueInfo &Result,
     134             :                                   jumpthreading::ConstantPreference Preference,
     135             :                                   Instruction *CxtI = nullptr);
     136             :   bool ProcessThreadableEdges(Value *Cond, BasicBlock *BB,
     137             :                               jumpthreading::ConstantPreference Preference,
     138             :                               Instruction *CxtI = nullptr);
     139             : 
     140             :   bool ProcessBranchOnPHI(PHINode *PN);
     141             :   bool ProcessBranchOnXOR(BinaryOperator *BO);
     142             :   bool ProcessImpliedCondition(BasicBlock *BB);
     143             : 
     144             :   bool SimplifyPartiallyRedundantLoad(LoadInst *LI);
     145             :   bool TryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB);
     146             :   bool TryToUnfoldSelectInCurrBB(BasicBlock *BB);
     147             : 
     148             :   bool ProcessGuards(BasicBlock *BB);
     149             :   bool ThreadGuard(BasicBlock *BB, IntrinsicInst *Guard, BranchInst *BI);
     150             : 
     151             : private:
     152             :   BasicBlock *SplitBlockPreds(BasicBlock *BB, ArrayRef<BasicBlock *> Preds,
     153             :                               const char *Suffix);
     154             :   void UpdateBlockFreqAndEdgeWeight(BasicBlock *PredBB, BasicBlock *BB,
     155             :                                     BasicBlock *NewBB, BasicBlock *SuccBB);
     156             :   /// Check if the block has profile metadata for its outgoing edges.
     157             :   bool doesBlockHaveProfileData(BasicBlock *BB);
     158             : };
     159             : 
     160             : } // end namespace llvm
     161             : 
     162             : #endif // LLVM_TRANSFORMS_SCALAR_JUMPTHREADING_H

Generated by: LCOV version 1.13