LLVM 19.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"
21#include <utility>
22#include <vector>
23
24namespace llvm {
25
26template <typename T, unsigned int N> class SmallSetVector;
27template <typename Fn> class function_ref;
28class MBFIWrapper;
29class MachineBasicBlock;
30class MachineBranchProbabilityInfo;
31class MachineFunction;
32class MachineInstr;
33class MachineModuleInfo;
34class MachineRegisterInfo;
35class ProfileSummaryInfo;
36class TargetRegisterInfo;
37
38/// Utility class to perform tail duplication.
40 const TargetInstrInfo *TII;
41 const TargetRegisterInfo *TRI;
43 const MachineModuleInfo *MMI;
46 MBFIWrapper *MBFI;
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
61public:
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,
73 MBFIWrapper *MBFI,
75 bool LayoutMode, unsigned TailDupSize = 0);
76
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
98private:
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);
119 bool tailDuplicate(bool IsSimple,
120 MachineBasicBlock *TailBB,
121 MachineBasicBlock *ForcedLayoutPred,
125 void appendCopies(MachineBasicBlock *MBB,
126 SmallVectorImpl<std::pair<Register, RegSubRegPair>> &CopyInfos,
128
129 void removeDeadBlock(
131 function_ref<void(MachineBasicBlock *)> *RemovalCallback = nullptr);
132};
133
134} // end namespace llvm
135
136#endif // LLVM_CODEGEN_TAILDUPLICATOR_H
MachineBasicBlock & MBB
This file defines the DenseMap class.
This file defines the DenseSet and SmallDenseSet classes.
IRTranslator LLVM IR MI
SI Lower i1 Copies
This file defines the SmallVector class.
Implements a dense probed hash-table based set.
Definition: DenseSet.h:271
Representation of each machine instruction.
Definition: MachineInstr.h:68
This class contains meta information specific to a module.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Analysis providing profile information.
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:370
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: SmallVector.h:586
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
Utility class to perform tail duplication.
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.
bool tailDuplicateBlocks()
Look for small blocks that are unconditionally branched to and do not fall through.
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.
static bool isSimpleBB(MachineBasicBlock *TailBB)
True if this BB has only one unconditional jump.
bool canTailDuplicate(MachineBasicBlock *TailBB, MachineBasicBlock *PredBB)
Returns true if TailBB can successfully be duplicated into PredBB.
bool shouldTailDuplicate(bool IsSimple, MachineBasicBlock &TailBB)
Determine if it is profitable to duplicate this block.
TargetInstrInfo - Interface to description of machine instruction set.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
An efficient, type-erasing, non-owning reference to a callable.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
A pair composed of a register and a sub-register index.