lib/CodeGen/BranchFolding.h

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