LLVM  6.0.0svn
BranchFolding.h
Go to the documentation of this file.
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"
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 
36  public:
37  class MBFIWrapper;
38 
39  explicit BranchFolder(bool defaultEnableTailMerge,
40  bool CommonHoist,
41  MBFIWrapper &MBFI,
42  const MachineBranchProbabilityInfo &MBPI,
43  // Min tail length to merge. Defaults to commandline
44  // flag. Ignored for optsize.
45  unsigned MinCommonTailLength = 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;
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  /// \brief This class keeps track of branch frequencies of newly created
136  /// blocks and tail-merged blocks.
137  class MBFIWrapper {
138  public:
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;
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,
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
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
Various leaf nodes.
Definition: ISDOpcodes.h:60
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
F(f)
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
const HexagonInstrInfo * TII
static bool isSimple(Instruction *I)
TargetInstrInfo - Interface to description of machine instruction set.
unsigned const MachineRegisterInfo * MRI
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
#define LLVM_LIBRARY_VISIBILITY
LLVM_LIBRARY_VISIBILITY - If a class marked with this attribute is linked into a shared library...
Definition: Compiler.h:105
MBFIWrapper(const MachineBlockFrequencyInfo &I)
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
This file implements the LivePhysRegs utility for tracking liveness of physical registers.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:418
MachineRegisterInfo - Keep track of information for virtual and physical registers, including vreg register classes, use/def chains for registers, etc.
A set of physical registers with utility functions to track liveness when walking backward/forward th...
Definition: LivePhysRegs.h:49
#define I(x, y, z)
Definition: MD5.cpp:58
bool operator<(int64_t V1, const APSInt &V2)
Definition: APSInt.h:326
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
This class keeps track of branch frequencies of newly created blocks and tail-merged blocks...
This class contains meta information specific to a module.