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