LLVM  9.0.0svn
BranchFolding.h
Go to the documentation of this file.
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"
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 
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;
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:
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;
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,
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
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Various leaf nodes.
Definition: ISDOpcodes.h:59
amdgpu Simplify well known AMD library false FunctionCallee Value const Twine & Name
MachineBlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate machine basic b...
unsigned const TargetRegisterInfo * TRI
F(f)
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:80
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:57
#define LLVM_LIBRARY_VISIBILITY
LLVM_LIBRARY_VISIBILITY - If a class marked with this attribute is linked into a shared library...
Definition: Compiler.h:107
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:417
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:48
#define I(x, y, z)
Definition: MD5.cpp:58
bool operator<(int64_t V1, const APSInt &V2)
Definition: APSInt.h:325
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
This class keeps track of branch frequencies of newly created blocks and tail-merged blocks...
This class contains meta information specific to a module.