contrib/llvm/include/llvm/Transforms/Scalar/JumpThreading.h

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