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