include/llvm/Transforms/Scalar/JumpThreading.h

   1 //===- JumpThreading.h - thread control through conditional BBs -*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   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/ArrayRef.h"
  18 #include "llvm/ADT/DenseSet.h"
  19 #include "llvm/ADT/SmallPtrSet.h"
  20 #include "llvm/ADT/SmallSet.h"
  21 #include "llvm/ADT/SmallVector.h"
  22 #include "llvm/Analysis/AliasAnalysis.h"
  23 #include "llvm/Analysis/BlockFrequencyInfo.h"
  24 #include "llvm/Analysis/BranchProbabilityInfo.h"
  25 #include "llvm/Analysis/DomTreeUpdater.h"
  26 #include "llvm/IR/ValueHandle.h"
  27 #include <memory>
  28 #include <utility>
  29
  30 namespace llvm {
  31
  32 class BasicBlock;
  33 class BinaryOperator;
  34 class BranchInst;
  35 class CmpInst;
  36 class Constant;
  37 class DomTreeUpdater;
  38 class Function;
  39 class Instruction;
  40 class IntrinsicInst;
  41 class LazyValueInfo;
  42 class LoadInst;
  43 class PHINode;
  44 class TargetLibraryInfo;
  45 class Value;
  46
  47 /// A private "module" namespace for types and utilities used by
  48 /// JumpThreading.
  49 /// These are implementation details and should not be used by clients.
  50 namespace jumpthreading {
  51
  52 // These are at global scope so static functions can use them too.
  53 using PredValueInfo = SmallVectorImpl<std::pair<Constant *, BasicBlock *>>;
  54 using PredValueInfoTy = SmallVector<std::pair<Constant *, BasicBlock *>, 8>;
  55
  56 // This is used to keep track of what kind of constant we're currently hoping
  57 // to find.
  58 enum ConstantPreference { WantInteger, WantBlockAddress };
  59
  60 } // end namespace jumpthreading
  61
  62 /// This pass performs 'jump threading', which looks at blocks that have
  63 /// multiple predecessors and multiple successors.  If one or more of the
  64 /// predecessors of the block can be proven to always jump to one of the
  65 /// successors, we forward the edge from the predecessor to the successor by
  66 /// duplicating the contents of this block.
  67 ///
  68 /// An example of when this can occur is code like this:
  69 ///
  70 ///   if () { ...
  71 ///     X = 4;
  72 ///   }
  73 ///   if (X < 3) {
  74 ///
  75 /// In this case, the unconditional branch at the end of the first if can be
  76 /// revectored to the false side of the second if.
  77 class JumpThreadingPass : public PassInfoMixin<JumpThreadingPass> {
  78   TargetLibraryInfo *TLI;
  79   LazyValueInfo *LVI;
  80   AliasAnalysis *AA;
  81   DomTreeUpdater *DTU;
  82   std::unique_ptr<BlockFrequencyInfo> BFI;
  83   std::unique_ptr<BranchProbabilityInfo> BPI;
  84   bool HasProfileData = false;
  85   bool HasGuards = false;
  86 #ifdef NDEBUG
  87   SmallPtrSet<const BasicBlock *, 16> LoopHeaders;
  88 #else
  89   SmallSet<AssertingVH<const BasicBlock>, 16> LoopHeaders;
  90 #endif
  91
  92   unsigned BBDupThreshold;
  93
  94 public:
  95   JumpThreadingPass(int T = -1);
  96
  97   // Glue for old PM.
  98   bool runImpl(Function &F, TargetLibraryInfo *TLI_, LazyValueInfo *LVI_,
  99                AliasAnalysis *AA_, DomTreeUpdater *DTU_, bool HasProfileData_,
 100                std::unique_ptr<BlockFrequencyInfo> BFI_,
 101                std::unique_ptr<BranchProbabilityInfo> BPI_);
 102
 103   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 104
 105   void releaseMemory() {
 106     BFI.reset();
 107     BPI.reset();
 108   }
 109
 110   void FindLoopHeaders(Function &F);
 111   bool ProcessBlock(BasicBlock *BB);
 112   bool ThreadEdge(BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs,
 113                   BasicBlock *SuccBB);
 114   bool DuplicateCondBranchOnPHIIntoPred(
 115       BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs);
 116
 117   bool ComputeValueKnownInPredecessorsImpl(
 118       Value *V, BasicBlock *BB, jumpthreading::PredValueInfo &Result,
 119       jumpthreading::ConstantPreference Preference,
 120       DenseSet<std::pair<Value *, BasicBlock *>> &RecursionSet,
 121       Instruction *CxtI = nullptr);
 122   bool
 123   ComputeValueKnownInPredecessors(Value *V, BasicBlock *BB,
 124                                   jumpthreading::PredValueInfo &Result,
 125                                   jumpthreading::ConstantPreference Preference,
 126                                   Instruction *CxtI = nullptr) {
 127     DenseSet<std::pair<Value *, BasicBlock *>> RecursionSet;
 128     return ComputeValueKnownInPredecessorsImpl(V, BB, Result, Preference,
 129                                                RecursionSet, CxtI);
 130   }
 131
 132   bool ProcessThreadableEdges(Value *Cond, BasicBlock *BB,
 133                               jumpthreading::ConstantPreference Preference,
 134                               Instruction *CxtI = nullptr);
 135
 136   bool ProcessBranchOnPHI(PHINode *PN);
 137   bool ProcessBranchOnXOR(BinaryOperator *BO);
 138   bool ProcessImpliedCondition(BasicBlock *BB);
 139
 140   bool SimplifyPartiallyRedundantLoad(LoadInst *LI);
 141   void UnfoldSelectInstr(BasicBlock *Pred, BasicBlock *BB, SelectInst *SI,
 142                          PHINode *SIUse, unsigned Idx);
 143
 144   bool TryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB);
 145   bool TryToUnfoldSelect(SwitchInst *SI, 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