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