Transforms/Scalar/JumpThreading.h

0001 //===- JumpThreading.h - thread control through conditional BBs -*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 //
0009 /// \file
0010 /// See the comments on JumpThreadingPass.
0011 //
0012 //===----------------------------------------------------------------------===//
0013
0014 #ifndef LLVM_TRANSFORMS_SCALAR_JUMPTHREADING_H
0015 #define LLVM_TRANSFORMS_SCALAR_JUMPTHREADING_H
0016
0017 #include "llvm/ADT/ArrayRef.h"
0018 #include "llvm/ADT/DenseSet.h"
0019 #include "llvm/ADT/SmallSet.h"
0020 #include "llvm/ADT/SmallVector.h"
0021 #include "llvm/Analysis/BlockFrequencyInfo.h"
0022 #include "llvm/Analysis/BranchProbabilityInfo.h"
0023 #include "llvm/Analysis/DomTreeUpdater.h"
0024 #include "llvm/IR/ValueHandle.h"
0025 #include "llvm/Transforms/Utils/ValueMapper.h"
0026 #include <optional>
0027 #include <utility>
0028
0029 namespace llvm {
0030
0031 class AAResults;
0032 class BasicBlock;
0033 class BinaryOperator;
0034 class BranchInst;
0035 class CmpInst;
0036 class Constant;
0037 class Function;
0038 class Instruction;
0039 class IntrinsicInst;
0040 class LazyValueInfo;
0041 class LoadInst;
0042 class PHINode;
0043 class SelectInst;
0044 class SwitchInst;
0045 class TargetLibraryInfo;
0046 class TargetTransformInfo;
0047 class Value;
0048
0049 /// A private "module" namespace for types and utilities used by
0050 /// JumpThreading.
0051 /// These are implementation details and should not be used by clients.
0052 namespace jumpthreading {
0053
0054 // These are at global scope so static functions can use them too.
0055 using PredValueInfo = SmallVectorImpl<std::pair<Constant *, BasicBlock *>>;
0056 using PredValueInfoTy = SmallVector<std::pair<Constant *, BasicBlock *>, 8>;
0057
0058 // This is used to keep track of what kind of constant we're currently hoping
0059 // to find.
0060 enum ConstantPreference { WantInteger, WantBlockAddress };
0061
0062 } // end namespace jumpthreading
0063
0064 /// This pass performs 'jump threading', which looks at blocks that have
0065 /// multiple predecessors and multiple successors.  If one or more of the
0066 /// predecessors of the block can be proven to always jump to one of the
0067 /// successors, we forward the edge from the predecessor to the successor by
0068 /// duplicating the contents of this block.
0069 ///
0070 /// An example of when this can occur is code like this:
0071 ///
0072 ///   if () { ...
0073 ///     X = 4;
0074 ///   }
0075 ///   if (X < 3) {
0076 ///
0077 /// In this case, the unconditional branch at the end of the first if can be
0078 /// revectored to the false side of the second if.
0079 class JumpThreadingPass : public PassInfoMixin<JumpThreadingPass> {
0080   Function *F = nullptr;
0081   FunctionAnalysisManager *FAM = nullptr;
0082   TargetLibraryInfo *TLI = nullptr;
0083   TargetTransformInfo *TTI = nullptr;
0084   LazyValueInfo *LVI = nullptr;
0085   AAResults *AA = nullptr;
0086   std::unique_ptr<DomTreeUpdater> DTU;
0087   std::optional<BlockFrequencyInfo *> BFI;
0088   std::optional<BranchProbabilityInfo *> BPI;
0089   bool ChangedSinceLastAnalysisUpdate = false;
0090   bool HasGuards = false;
0091 #ifndef LLVM_ENABLE_ABI_BREAKING_CHECKS
0092   SmallSet<AssertingVH<const BasicBlock>, 16> LoopHeaders;
0093 #else
0094   SmallPtrSet<const BasicBlock *, 16> LoopHeaders;
0095 #endif
0096
0097   unsigned BBDupThreshold;
0098   unsigned DefaultBBDupThreshold;
0099
0100 public:
0101   JumpThreadingPass(int T = -1);
0102
0103   // Glue for old PM.
0104   bool runImpl(Function &F, FunctionAnalysisManager *FAM,
0105                TargetLibraryInfo *TLI, TargetTransformInfo *TTI,
0106                LazyValueInfo *LVI, AAResults *AA,
0107                std::unique_ptr<DomTreeUpdater> DTU,
0108                std::optional<BlockFrequencyInfo *> BFI,
0109                std::optional<BranchProbabilityInfo *> BPI);
0110
0111   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
0112
0113   DomTreeUpdater *getDomTreeUpdater() const { return DTU.get(); }
0114   void findLoopHeaders(Function &F);
0115   bool processBlock(BasicBlock *BB);
0116   bool maybeMergeBasicBlockIntoOnlyPred(BasicBlock *BB);
0117   void updateSSA(BasicBlock *BB, BasicBlock *NewBB,
0118                  ValueToValueMapTy &ValueMapping);
0119   void cloneInstructions(ValueToValueMapTy &ValueMapping,
0120                          BasicBlock::iterator BI, BasicBlock::iterator BE,
0121                          BasicBlock *NewBB, BasicBlock *PredBB);
0122   bool tryThreadEdge(BasicBlock *BB,
0123                      const SmallVectorImpl<BasicBlock *> &PredBBs,
0124                      BasicBlock *SuccBB);
0125   void threadEdge(BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs,
0126                   BasicBlock *SuccBB);
0127   bool duplicateCondBranchOnPHIIntoPred(
0128       BasicBlock *BB, const SmallVectorImpl<BasicBlock *> &PredBBs);
0129
0130   bool computeValueKnownInPredecessorsImpl(
0131       Value *V, BasicBlock *BB, jumpthreading::PredValueInfo &Result,
0132       jumpthreading::ConstantPreference Preference,
0133       SmallPtrSet<Value *, 4> &RecursionSet, Instruction *CxtI = nullptr);
0134   bool
0135   computeValueKnownInPredecessors(Value *V, BasicBlock *BB,
0136                                   jumpthreading::PredValueInfo &Result,
0137                                   jumpthreading::ConstantPreference Preference,
0138                                   Instruction *CxtI = nullptr) {
0139     SmallPtrSet<Value *, 4> RecursionSet;
0140     return computeValueKnownInPredecessorsImpl(V, BB, Result, Preference,
0141                                                RecursionSet, CxtI);
0142   }
0143
0144   Constant *evaluateOnPredecessorEdge(BasicBlock *BB, BasicBlock *PredPredBB,
0145                                       Value *cond, const DataLayout &DL);
0146   bool maybethreadThroughTwoBasicBlocks(BasicBlock *BB, Value *Cond);
0147   void threadThroughTwoBasicBlocks(BasicBlock *PredPredBB, BasicBlock *PredBB,
0148                                    BasicBlock *BB, BasicBlock *SuccBB);
0149   bool processThreadableEdges(Value *Cond, BasicBlock *BB,
0150                               jumpthreading::ConstantPreference Preference,
0151                               Instruction *CxtI = nullptr);
0152
0153   bool processBranchOnPHI(PHINode *PN);
0154   bool processBranchOnXOR(BinaryOperator *BO);
0155   bool processImpliedCondition(BasicBlock *BB);
0156
0157   bool simplifyPartiallyRedundantLoad(LoadInst *LI);
0158   void unfoldSelectInstr(BasicBlock *Pred, BasicBlock *BB, SelectInst *SI,
0159                          PHINode *SIUse, unsigned Idx);
0160
0161   bool tryToUnfoldSelect(CmpInst *CondCmp, BasicBlock *BB);
0162   bool tryToUnfoldSelect(SwitchInst *SI, BasicBlock *BB);
0163   bool tryToUnfoldSelectInCurrBB(BasicBlock *BB);
0164
0165   bool processGuards(BasicBlock *BB);
0166   bool threadGuard(BasicBlock *BB, IntrinsicInst *Guard, BranchInst *BI);
0167
0168 private:
0169   BasicBlock *splitBlockPreds(BasicBlock *BB, ArrayRef<BasicBlock *> Preds,
0170                               const char *Suffix);
0171   void updateBlockFreqAndEdgeWeight(BasicBlock *PredBB, BasicBlock *BB,
0172                                     BasicBlock *NewBB, BasicBlock *SuccBB,
0173                                     BlockFrequencyInfo *BFI,
0174                                     BranchProbabilityInfo *BPI,
0175                                     bool HasProfile);
0176   /// Check if the block has profile metadata for its outgoing edges.
0177   bool doesBlockHaveProfileData(BasicBlock *BB);
0178
0179   /// Returns analysis preserved by the pass.
0180   PreservedAnalyses getPreservedAnalysis() const;
0181
0182   /// Helper function to run "external" analysis in the middle of JumpThreading.
0183   /// It takes care of updating/invalidating other existing analysis
0184   /// before/after  running the "external" one.
0185   template <typename AnalysisT>
0186   typename AnalysisT::Result *runExternalAnalysis();
0187
0188   /// Returns an existing instance of BPI if any, otherwise nullptr. By
0189   /// "existing" we mean either cached result provided by FunctionAnalysisManger
0190   /// or created by preceding call to 'getOrCreateBPI'.
0191   BranchProbabilityInfo *getBPI();
0192
0193   /// Returns an existing instance of BFI if any, otherwise nullptr. By
0194   /// "existing" we mean either cached result provided by FunctionAnalysisManger
0195   /// or created by preceding call to 'getOrCreateBFI'.
0196   BlockFrequencyInfo *getBFI();
0197
0198   /// Returns an existing instance of BPI if any, otherwise:
0199   ///   if 'HasProfile' is true creates new instance through
0200   ///   FunctionAnalysisManager, otherwise nullptr.
0201   BranchProbabilityInfo *getOrCreateBPI(bool Force = false);
0202
0203   /// Returns an existing instance of BFI if any, otherwise:
0204   ///   if 'HasProfile' is true creates new instance through
0205   ///   FunctionAnalysisManager, otherwise nullptr.
0206   BlockFrequencyInfo *getOrCreateBFI(bool Force = false);
0207 };
0208
0209 } // end namespace llvm
0210
0211 #endif // LLVM_TRANSFORMS_SCALAR_JUMPTHREADING_H