LLVM  14.0.0git
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"
16 #include "llvm/Support/Compiler.h"
17 #include <cstdint>
18 #include <vector>
19 
20 namespace llvm {
21 
22 class BasicBlock;
23 class MachineBranchProbabilityInfo;
24 class MachineFunction;
25 class MachineLoopInfo;
26 class MachineRegisterInfo;
27 class MBFIWrapper;
28 class ProfileSummaryInfo;
29 class TargetInstrInfo;
30 class TargetRegisterInfo;
31 
33  public:
34  explicit BranchFolder(bool DefaultEnableTailMerge, bool CommonHoist,
35  MBFIWrapper &FreqInfo,
36  const MachineBranchProbabilityInfo &ProbInfo,
37  ProfileSummaryInfo *PSI,
38  // Min tail length to merge. Defaults to commandline
39  // flag. Ignored for optsize.
40  unsigned MinTailLength = 0);
41 
42  /// Perhaps branch folding, tail merging and other CFG optimizations on the
43  /// given function. Block placement changes the layout and may create new
44  /// tail merging opportunities.
45  bool OptimizeFunction(MachineFunction &MF, const TargetInstrInfo *tii,
46  const TargetRegisterInfo *tri,
47  MachineLoopInfo *mli = nullptr,
48  bool AfterPlacement = false);
49 
50  private:
51  class MergePotentialsElt {
52  unsigned Hash;
53  MachineBasicBlock *Block;
54 
55  public:
56  MergePotentialsElt(unsigned h, MachineBasicBlock *b)
57  : Hash(h), Block(b) {}
58 
59  unsigned getHash() const { return Hash; }
60  MachineBasicBlock *getBlock() const { return Block; }
61 
62  void setBlock(MachineBasicBlock *MBB) {
63  Block = MBB;
64  }
65 
66  bool operator<(const MergePotentialsElt &) const;
67  };
68 
69  using MPIterator = std::vector<MergePotentialsElt>::iterator;
70 
71  std::vector<MergePotentialsElt> MergePotentials;
74 
75  class SameTailElt {
76  MPIterator MPIter;
77  MachineBasicBlock::iterator TailStartPos;
78 
79  public:
80  SameTailElt(MPIterator mp, MachineBasicBlock::iterator tsp)
81  : MPIter(mp), TailStartPos(tsp) {}
82 
83  MPIterator getMPIter() const {
84  return MPIter;
85  }
86 
87  MergePotentialsElt &getMergePotentialsElt() const {
88  return *getMPIter();
89  }
90 
91  MachineBasicBlock::iterator getTailStartPos() const {
92  return TailStartPos;
93  }
94 
95  unsigned getHash() const {
96  return getMergePotentialsElt().getHash();
97  }
98 
99  MachineBasicBlock *getBlock() const {
100  return getMergePotentialsElt().getBlock();
101  }
102 
103  bool tailIsWholeBlock() const {
104  return TailStartPos == getBlock()->begin();
105  }
106 
107  void setBlock(MachineBasicBlock *MBB) {
108  getMergePotentialsElt().setBlock(MBB);
109  }
110 
111  void setTailStartPos(MachineBasicBlock::iterator Pos) {
112  TailStartPos = Pos;
113  }
114  };
115  std::vector<SameTailElt> SameTails;
116 
117  bool AfterBlockPlacement;
118  bool EnableTailMerge;
119  bool EnableHoistCommonCode;
120  bool UpdateLiveIns;
121  unsigned MinCommonTailLength;
122  const TargetInstrInfo *TII;
123  const MachineRegisterInfo *MRI;
124  const TargetRegisterInfo *TRI;
125  MachineLoopInfo *MLI;
126  LivePhysRegs LiveRegs;
127 
128  private:
129  MBFIWrapper &MBBFreqInfo;
130  const MachineBranchProbabilityInfo &MBPI;
131  ProfileSummaryInfo *PSI;
132 
133  bool TailMergeBlocks(MachineFunction &MF);
134  bool TryTailMergeBlocks(MachineBasicBlock* SuccBB,
135  MachineBasicBlock* PredBB,
136  unsigned MinCommonTailLength);
137  void setCommonTailEdgeWeights(MachineBasicBlock &TailMBB);
138 
139  /// Delete the instruction OldInst and everything after it, replacing it
140  /// with an unconditional branch to NewDest.
141  void replaceTailWithBranchTo(MachineBasicBlock::iterator OldInst,
142  MachineBasicBlock &NewDest);
143 
144  /// Given a machine basic block and an iterator into it, split the MBB so
145  /// that the part before the iterator falls into the part starting at the
146  /// iterator. This returns the new MBB.
147  MachineBasicBlock *SplitMBBAt(MachineBasicBlock &CurMBB,
149  const BasicBlock *BB);
150 
151  /// Look through all the blocks in MergePotentials that have hash CurHash
152  /// (guaranteed to match the last element). Build the vector SameTails of
153  /// all those that have the (same) largest number of instructions in common
154  /// of any pair of these blocks. SameTails entries contain an iterator into
155  /// MergePotentials (from which the MachineBasicBlock can be found) and a
156  /// MachineBasicBlock::iterator into that MBB indicating the instruction
157  /// where the matching code sequence begins. Order of elements in SameTails
158  /// is the reverse of the order in which those blocks appear in
159  /// MergePotentials (where they are not necessarily consecutive).
160  unsigned ComputeSameTails(unsigned CurHash, unsigned minCommonTailLength,
161  MachineBasicBlock *SuccBB,
162  MachineBasicBlock *PredBB);
163 
164  /// Remove all blocks with hash CurHash from MergePotentials, restoring
165  /// branches at ends of blocks as appropriate.
166  void RemoveBlocksWithHash(unsigned CurHash, MachineBasicBlock* SuccBB,
167  MachineBasicBlock* PredBB);
168 
169  /// None of the blocks to be tail-merged consist only of the common tail.
170  /// Create a block that does by splitting one.
171  bool CreateCommonTailOnlyBlock(MachineBasicBlock *&PredBB,
172  MachineBasicBlock *SuccBB,
173  unsigned maxCommonTailLength,
174  unsigned &commonTailIndex);
175 
176  /// Create merged DebugLocs of identical instructions across SameTails and
177  /// assign it to the instruction in common tail; merge MMOs and undef flags.
178  void mergeCommonTails(unsigned commonTailIndex);
179 
180  bool OptimizeBranches(MachineFunction &MF);
181 
182  /// Analyze and optimize control flow related to the specified block. This
183  /// is never called on the entry block.
184  bool OptimizeBlock(MachineBasicBlock *MBB);
185 
186  /// Remove the specified dead machine basic block from the function,
187  /// updating the CFG.
188  void RemoveDeadBlock(MachineBasicBlock *MBB);
189 
190  /// Hoist common instruction sequences at the start of basic blocks to their
191  /// common predecessor.
192  bool HoistCommonCode(MachineFunction &MF);
193 
194  /// If the successors of MBB has common instruction sequence at the start of
195  /// the function, move the instructions before MBB terminator if it's legal.
196  bool HoistCommonCodeInSuccs(MachineBasicBlock *MBB);
197  };
198 
199 } // end namespace llvm
200 
201 #endif // LLVM_LIB_CODEGEN_BRANCHFOLDING_H
llvm::BranchFolder
Definition: BranchFolding.h:32
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AllocatorList.h:23
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:52
MachineBasicBlock.h
llvm::LivePhysRegs
A set of physical registers with utility functions to track liveness when walking backward/forward th...
Definition: LivePhysRegs.h:48
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:233
DenseMap.h
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:449
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1559
llvm::MachineLoopInfo
Definition: MachineLoopInfo.h:90
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
llvm::TargetInstrInfo
TargetInstrInfo - Interface to description of machine instruction set.
Definition: TargetInstrInfo.h:97
llvm::MachineBranchProbabilityInfo
Definition: MachineBranchProbabilityInfo.h:24
b
the resulting code requires compare and branches when and if the revised code is with conditional branches instead of More there is a byte word extend before each where there should be only and the condition codes are not remembered when the same two values are compared twice More LSR enhancements i8 and i32 load store addressing modes are identical int b
Definition: README.txt:418
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:127
SmallPtrSet.h
llvm::MBFIWrapper
Definition: MBFIWrapper.h:26
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
llvm::ProfileSummaryInfo
Analysis providing profile information.
Definition: ProfileSummaryInfo.h:39
llvm::DenseMap
Definition: DenseMap.h:714
llvm::operator<
bool operator<(int64_t V1, const APSInt &V2)
Definition: APSInt.h:338
llvm::ISD::BasicBlock
@ BasicBlock
Various leaf nodes.
Definition: ISDOpcodes.h:71
llvm::MachineFunction
Definition: MachineFunction.h:241
Compiler.h
LLVM_LIBRARY_VISIBILITY
#define LLVM_LIBRARY_VISIBILITY
LLVM_LIBRARY_VISIBILITY - If a class marked with this attribute is linked into a shared library,...
Definition: Compiler.h:135
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
h
the multiplication has a latency of four as opposed to two cycles for the movl lea variant It appears gcc place string data with linkonce linkage in section coalesced instead of section coalesced Take a look at darwin h
Definition: README.txt:261
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::MachineInstrBundleIterator< MachineInstr >
LivePhysRegs.h