llvm/lib/CodeGen/BranchFolding.h

   1 //===- BranchFolding.h - Fold machine code branch instructions --*- 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 #ifndef LLVM_LIB_CODEGEN_BRANCHFOLDING_H
  10 #define LLVM_LIB_CODEGEN_BRANCHFOLDING_H
  11
  12 #include "llvm/ADT/DenseMap.h"
  13 #include "llvm/ADT/SmallPtrSet.h"
  14 #include "llvm/CodeGen/LivePhysRegs.h"
  15 #include "llvm/CodeGen/MachineBasicBlock.h"
  16 #include "llvm/Support/Compiler.h"
  17 #include <vector>
  18
  19 namespace llvm {
  20
  21 class BasicBlock;
  22 class MachineBranchProbabilityInfo;
  23 class MachineFunction;
  24 class MachineLoopInfo;
  25 class MachineRegisterInfo;
  26 class MBFIWrapper;
  27 class ProfileSummaryInfo;
  28 class TargetInstrInfo;
  29 class TargetRegisterInfo;
  30
  31   class LLVM_LIBRARY_VISIBILITY BranchFolder {
  32   public:
  33     explicit BranchFolder(bool DefaultEnableTailMerge, bool CommonHoist,
  34                           MBFIWrapper &FreqInfo,
  35                           const MachineBranchProbabilityInfo &ProbInfo,
  36                           ProfileSummaryInfo *PSI,
  37                           // Min tail length to merge. Defaults to commandline
  38                           // flag. Ignored for optsize.
  39                           unsigned MinTailLength = 0);
  40
  41     /// Perhaps branch folding, tail merging and other CFG optimizations on the
  42     /// given function.  Block placement changes the layout and may create new
  43     /// tail merging opportunities.
  44     bool OptimizeFunction(MachineFunction &MF, const TargetInstrInfo *tii,
  45                           const TargetRegisterInfo *tri,
  46                           MachineLoopInfo *mli = nullptr,
  47                           bool AfterPlacement = false);
  48
  49   private:
  50     class MergePotentialsElt {
  51       unsigned Hash;
  52       MachineBasicBlock *Block;
  53       DebugLoc BranchDebugLoc;
  54
  55     public:
  56       MergePotentialsElt(unsigned h, MachineBasicBlock *b, DebugLoc bdl)
  57           : Hash(h), Block(b), BranchDebugLoc(std::move(bdl)) {}
  58
  59       unsigned getHash() const { return Hash; }
  60       MachineBasicBlock *getBlock() const { return Block; }
  61
  62       void setBlock(MachineBasicBlock *MBB) {
  63         Block = MBB;
  64       }
  65
  66       const DebugLoc &getBranchDebugLoc() { return BranchDebugLoc; }
  67
  68       bool operator<(const MergePotentialsElt &) const;
  69     };
  70
  71     using MPIterator = std::vector<MergePotentialsElt>::iterator;
  72
  73     std::vector<MergePotentialsElt> MergePotentials;
  74     SmallPtrSet<const MachineBasicBlock*, 2> TriedMerging;
  75     DenseMap<const MachineBasicBlock *, int> EHScopeMembership;
  76
  77     class SameTailElt {
  78       MPIterator MPIter;
  79       MachineBasicBlock::iterator TailStartPos;
  80
  81     public:
  82       SameTailElt(MPIterator mp, MachineBasicBlock::iterator tsp)
  83         : MPIter(mp), TailStartPos(tsp) {}
  84
  85       MPIterator getMPIter() const {
  86         return MPIter;
  87       }
  88
  89       MergePotentialsElt &getMergePotentialsElt() const {
  90         return *getMPIter();
  91       }
  92
  93       MachineBasicBlock::iterator getTailStartPos() const {
  94         return TailStartPos;
  95       }
  96
  97       unsigned getHash() const {
  98         return getMergePotentialsElt().getHash();
  99       }
 100
 101       MachineBasicBlock *getBlock() const {
 102         return getMergePotentialsElt().getBlock();
 103       }
 104
 105       bool tailIsWholeBlock() const {
 106         return TailStartPos == getBlock()->begin();
 107       }
 108
 109       void setBlock(MachineBasicBlock *MBB) {
 110         getMergePotentialsElt().setBlock(MBB);
 111       }
 112
 113       void setTailStartPos(MachineBasicBlock::iterator Pos) {
 114         TailStartPos = Pos;
 115       }
 116     };
 117     std::vector<SameTailElt> SameTails;
 118
 119     bool AfterBlockPlacement = false;
 120     bool EnableTailMerge = false;
 121     bool EnableHoistCommonCode = false;
 122     bool UpdateLiveIns = false;
 123     unsigned MinCommonTailLength;
 124     const TargetInstrInfo *TII = nullptr;
 125     const MachineRegisterInfo *MRI = nullptr;
 126     const TargetRegisterInfo *TRI = nullptr;
 127     MachineLoopInfo *MLI = nullptr;
 128     LivePhysRegs LiveRegs;
 129
 130   private:
 131     MBFIWrapper &MBBFreqInfo;
 132     const MachineBranchProbabilityInfo &MBPI;
 133     ProfileSummaryInfo *PSI;
 134
 135     bool TailMergeBlocks(MachineFunction &MF);
 136     bool TryTailMergeBlocks(MachineBasicBlock* SuccBB,
 137                        MachineBasicBlock* PredBB,
 138                        unsigned MinCommonTailLength);
 139     void setCommonTailEdgeWeights(MachineBasicBlock &TailMBB);
 140
 141     /// Delete the instruction OldInst and everything after it, replacing it
 142     /// with an unconditional branch to NewDest.
 143     void replaceTailWithBranchTo(MachineBasicBlock::iterator OldInst,
 144                                  MachineBasicBlock &NewDest);
 145
 146     /// Given a machine basic block and an iterator into it, split the MBB so
 147     /// that the part before the iterator falls into the part starting at the
 148     /// iterator.  This returns the new MBB.
 149     MachineBasicBlock *SplitMBBAt(MachineBasicBlock &CurMBB,
 150                                   MachineBasicBlock::iterator BBI1,
 151                                   const BasicBlock *BB);
 152
 153     /// Look through all the blocks in MergePotentials that have hash CurHash
 154     /// (guaranteed to match the last element).  Build the vector SameTails of
 155     /// all those that have the (same) largest number of instructions in common
 156     /// of any pair of these blocks.  SameTails entries contain an iterator into
 157     /// MergePotentials (from which the MachineBasicBlock can be found) and a
 158     /// MachineBasicBlock::iterator into that MBB indicating the instruction
 159     /// where the matching code sequence begins.  Order of elements in SameTails
 160     /// is the reverse of the order in which those blocks appear in
 161     /// MergePotentials (where they are not necessarily consecutive).
 162     unsigned ComputeSameTails(unsigned CurHash, unsigned minCommonTailLength,
 163                               MachineBasicBlock *SuccBB,
 164                               MachineBasicBlock *PredBB);
 165
 166     /// Remove all blocks with hash CurHash from MergePotentials, restoring
 167     /// branches at ends of blocks as appropriate.
 168     void RemoveBlocksWithHash(unsigned CurHash, MachineBasicBlock *SuccBB,
 169                               MachineBasicBlock *PredBB,
 170                               const DebugLoc &BranchDL);
 171
 172     /// None of the blocks to be tail-merged consist only of the common tail.
 173     /// Create a block that does by splitting one.
 174     bool CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB,
 175                                    MachineBasicBlock *SuccBB,
 176                                    unsigned maxCommonTailLength,
 177                                    unsigned &commonTailIndex);
 178
 179     /// Create merged DebugLocs of identical instructions across SameTails and
 180     /// assign it to the instruction in common tail; merge MMOs and undef flags.
 181     void mergeCommonTails(unsigned commonTailIndex);
 182
 183     bool OptimizeBranches(MachineFunction &MF);
 184
 185     /// Analyze and optimize control flow related to the specified block. This
 186     /// is never called on the entry block.
 187     bool OptimizeBlock(MachineBasicBlock *MBB);
 188
 189     /// Remove the specified dead machine basic block from the function,
 190     /// updating the CFG.
 191     void RemoveDeadBlock(MachineBasicBlock *MBB);
 192
 193     /// Hoist common instruction sequences at the start of basic blocks to their
 194     /// common predecessor.
 195     bool HoistCommonCode(MachineFunction &MF);
 196
 197     /// If the successors of MBB has common instruction sequence at the start of
 198     /// the function, move the instructions before MBB terminator if it's legal.
 199     bool HoistCommonCodeInSuccs(MachineBasicBlock *MBB);
 200   };
 201
 202 } // end namespace llvm
 203
 204 #endif // LLVM_LIB_CODEGEN_BRANCHFOLDING_H