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