LLVM  14.0.0git
TailDuplicator.h
Go to the documentation of this file.
1 //===- llvm/CodeGen/TailDuplicator.h ----------------------------*- 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 // This file defines the TailDuplicator class. Used by the
10 // TailDuplication pass, and MachineBlockPlacement.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_CODEGEN_TAILDUPLICATOR_H
15 #define LLVM_CODEGEN_TAILDUPLICATOR_H
16 
17 #include "llvm/ADT/DenseMap.h"
18 #include "llvm/ADT/DenseSet.h"
19 #include "llvm/ADT/SetVector.h"
20 #include "llvm/ADT/SmallVector.h"
23 #include <utility>
24 #include <vector>
25 
26 namespace llvm {
27 
28 class MachineBasicBlock;
29 class MachineBlockFrequencyInfo;
30 class MachineBranchProbabilityInfo;
31 class MachineFunction;
32 class MachineInstr;
33 class MachineModuleInfo;
34 class MachineRegisterInfo;
35 class ProfileSummaryInfo;
36 class TargetRegisterInfo;
37 
38 /// Utility class to perform tail duplication.
40  const TargetInstrInfo *TII;
41  const TargetRegisterInfo *TRI;
42  const MachineBranchProbabilityInfo *MBPI;
43  const MachineModuleInfo *MMI;
45  MachineFunction *MF;
46  MBFIWrapper *MBFI;
47  ProfileSummaryInfo *PSI;
48  bool PreRegAlloc;
49  bool LayoutMode;
50  unsigned TailDupSize;
51 
52  // A list of virtual registers for which to update SSA form.
53  SmallVector<Register, 16> SSAUpdateVRs;
54 
55  // For each virtual register in SSAUpdateVals keep a list of source virtual
56  // registers.
57  using AvailableValsTy = std::vector<std::pair<MachineBasicBlock *, Register>>;
58 
60 
61 public:
62  /// Prepare to run on a specific machine function.
63  /// @param MF - Function that will be processed
64  /// @param PreRegAlloc - true if used before register allocation
65  /// @param MBPI - Branch Probability Info. Used to propagate correct
66  /// probabilities when modifying the CFG.
67  /// @param LayoutMode - When true, don't use the existing layout to make
68  /// decisions.
69  /// @param TailDupSize - Maxmimum size of blocks to tail-duplicate. Zero
70  /// default implies using the command line value TailDupSize.
71  void initMF(MachineFunction &MF, bool PreRegAlloc,
72  const MachineBranchProbabilityInfo *MBPI,
73  MBFIWrapper *MBFI,
74  ProfileSummaryInfo *PSI,
75  bool LayoutMode, unsigned TailDupSize = 0);
76 
77  bool tailDuplicateBlocks();
78  static bool isSimpleBB(MachineBasicBlock *TailBB);
79  bool shouldTailDuplicate(bool IsSimple, MachineBasicBlock &TailBB);
80 
81  /// Returns true if TailBB can successfully be duplicated into PredBB
83 
84  /// Tail duplicate a single basic block into its predecessors, and then clean
85  /// up.
86  /// If \p DuplicatePreds is not null, it will be updated to contain the list
87  /// of predecessors that received a copy of \p MBB.
88  /// If \p RemovalCallback is non-null. It will be called before MBB is
89  /// deleted.
90  /// If \p CandidatePtr is not null, duplicate into these blocks only.
92  bool IsSimple, MachineBasicBlock *MBB,
93  MachineBasicBlock *ForcedLayoutPred,
94  SmallVectorImpl<MachineBasicBlock*> *DuplicatedPreds = nullptr,
95  function_ref<void(MachineBasicBlock *)> *RemovalCallback = nullptr,
96  SmallVectorImpl<MachineBasicBlock *> *CandidatePtr = nullptr);
97 
98 private:
100 
101  void addSSAUpdateEntry(Register OrigReg, Register NewReg,
103  void processPHI(MachineInstr *MI, MachineBasicBlock *TailBB,
104  MachineBasicBlock *PredBB,
106  SmallVectorImpl<std::pair<Register, RegSubRegPair>> &Copies,
107  const DenseSet<Register> &UsedByPhi, bool Remove);
108  void duplicateInstruction(MachineInstr *MI, MachineBasicBlock *TailBB,
109  MachineBasicBlock *PredBB,
111  const DenseSet<Register> &UsedByPhi);
112  void updateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead,
115  bool canCompletelyDuplicateBB(MachineBasicBlock &BB);
116  bool duplicateSimpleBB(MachineBasicBlock *TailBB,
118  const DenseSet<Register> &RegsUsedByPhi,
120  bool tailDuplicate(bool IsSimple,
121  MachineBasicBlock *TailBB,
122  MachineBasicBlock *ForcedLayoutPred,
126  void appendCopies(MachineBasicBlock *MBB,
127  SmallVectorImpl<std::pair<Register, RegSubRegPair>> &CopyInfos,
129 
130  void removeDeadBlock(
132  function_ref<void(MachineBasicBlock *)> *RemovalCallback = nullptr);
133 };
134 
135 } // end namespace llvm
136 
137 #endif // LLVM_CODEGEN_TAILDUPLICATOR_H
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:103
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::TailDuplicator::initMF
void initMF(MachineFunction &MF, bool PreRegAlloc, const MachineBranchProbabilityInfo *MBPI, MBFIWrapper *MBFI, ProfileSummaryInfo *PSI, bool LayoutMode, unsigned TailDupSize=0)
Prepare to run on a specific machine function.
Definition: TailDuplicator.cpp:81
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:52
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:233
DenseMap.h
TargetInstrInfo.h
llvm::TailDuplicator::shouldTailDuplicate
bool shouldTailDuplicate(bool IsSimple, MachineBasicBlock &TailBB)
Determine if it is profitable to duplicate this block.
Definition: TailDuplicator.cpp:554
MBFIWrapper.h
llvm::TargetInstrInfo::RegSubRegPair
A pair composed of a register and a sub-register index.
Definition: TargetInstrInfo.h:477
llvm::TailDuplicator::isSimpleBB
static bool isSimpleBB(MachineBasicBlock *TailBB)
True if this BB has only one unconditional jump.
Definition: TailDuplicator.cpp:684
llvm::TargetInstrInfo
TargetInstrInfo - Interface to description of machine instruction set.
Definition: TargetInstrInfo.h:97
llvm::MachineBranchProbabilityInfo
Definition: MachineBranchProbabilityInfo.h:24
DenseSet.h
llvm::MachineModuleInfo
This class contains meta information specific to a module.
Definition: MachineModuleInfo.h:78
Copies
SI Lower i1 Copies
Definition: SILowerI1Copies.cpp:406
llvm::MBFIWrapper
Definition: MBFIWrapper.h:26
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
llvm::ProfileSummaryInfo
Analysis providing profile information.
Definition: ProfileSummaryInfo.h:39
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLExtras.h:168
llvm::DenseSet
Implements a dense probed hash-table based set.
Definition: DenseSet.h:268
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:64
llvm::DenseMap
Definition: DenseMap.h:714
llvm::TailDuplicator::tailDuplicateAndUpdate
bool tailDuplicateAndUpdate(bool IsSimple, MachineBasicBlock *MBB, MachineBasicBlock *ForcedLayoutPred, SmallVectorImpl< MachineBasicBlock * > *DuplicatedPreds=nullptr, function_ref< void(MachineBasicBlock *)> *RemovalCallback=nullptr, SmallVectorImpl< MachineBasicBlock * > *CandidatePtr=nullptr)
Tail duplicate a single basic block into its predecessors, and then clean up.
Definition: TailDuplicator.cpp:157
RegSubRegPair
TargetInstrInfo::RegSubRegPair RegSubRegPair
Definition: PeepholeOptimizer.cpp:101
llvm::MachineFunction
Definition: MachineFunction.h:230
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::TailDuplicator::canTailDuplicate
bool canTailDuplicate(MachineBasicBlock *TailBB, MachineBasicBlock *PredBB)
Returns true if TailBB can successfully be duplicated into PredBB.
Definition: TailDuplicator.cpp:793
SmallVector.h
llvm::TailDuplicator
Utility class to perform tail duplication.
Definition: TailDuplicator.h:39
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:43
llvm::SmallSetVector
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:307
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
SetVector.h
llvm::TailDuplicator::tailDuplicateBlocks
bool tailDuplicateBlocks()
Look for small blocks that are unconditionally branched to and do not fall through.
Definition: TailDuplicator.cpp:273