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/SmallVector.h" |
20 | #include "llvm/CodeGen/TargetInstrInfo.h" |
21 | #include <utility> |
22 | #include <vector> |
23 | |
24 | namespace llvm { |
25 | |
26 | template <typename T, unsigned int N> class SmallSetVector; |
27 | template <typename Fn> class function_ref; |
28 | class MBFIWrapper; |
29 | class MachineBasicBlock; |
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. |
39 | class TailDuplicator { |
40 | const TargetInstrInfo *TII; |
41 | const TargetRegisterInfo *TRI; |
42 | const MachineBranchProbabilityInfo *MBPI; |
43 | const MachineModuleInfo *MMI; |
44 | MachineRegisterInfo *MRI; |
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 | |
59 | DenseMap<Register, AvailableValsTy> SSAUpdateVals; |
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 |
82 | bool canTailDuplicate(MachineBasicBlock *TailBB, MachineBasicBlock *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. |
91 | bool tailDuplicateAndUpdate( |
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: |
99 | using RegSubRegPair = TargetInstrInfo::RegSubRegPair; |
100 | |
101 | void addSSAUpdateEntry(Register OrigReg, Register NewReg, |
102 | MachineBasicBlock *BB); |
103 | void processPHI(MachineInstr *MI, MachineBasicBlock *TailBB, |
104 | MachineBasicBlock *PredBB, |
105 | DenseMap<Register, RegSubRegPair> &LocalVRMap, |
106 | SmallVectorImpl<std::pair<Register, RegSubRegPair>> &Copies, |
107 | const DenseSet<Register> &UsedByPhi, bool Remove); |
108 | void duplicateInstruction(MachineInstr *MI, MachineBasicBlock *TailBB, |
109 | MachineBasicBlock *PredBB, |
110 | DenseMap<Register, RegSubRegPair> &LocalVRMap, |
111 | const DenseSet<Register> &UsedByPhi); |
112 | void updateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead, |
113 | SmallVectorImpl<MachineBasicBlock *> &TDBBs, |
114 | SmallSetVector<MachineBasicBlock *, 8> &Succs); |
115 | bool canCompletelyDuplicateBB(MachineBasicBlock &BB); |
116 | bool duplicateSimpleBB(MachineBasicBlock *TailBB, |
117 | SmallVectorImpl<MachineBasicBlock *> &TDBBs, |
118 | const DenseSet<Register> &RegsUsedByPhi); |
119 | bool tailDuplicate(bool IsSimple, |
120 | MachineBasicBlock *TailBB, |
121 | MachineBasicBlock *ForcedLayoutPred, |
122 | SmallVectorImpl<MachineBasicBlock *> &TDBBs, |
123 | SmallVectorImpl<MachineInstr *> &Copies, |
124 | SmallVectorImpl<MachineBasicBlock *> *CandidatePtr); |
125 | void appendCopies(MachineBasicBlock *MBB, |
126 | SmallVectorImpl<std::pair<Register, RegSubRegPair>> &CopyInfos, |
127 | SmallVectorImpl<MachineInstr *> &Copies); |
128 | |
129 | void removeDeadBlock( |
130 | MachineBasicBlock *MBB, |
131 | function_ref<void(MachineBasicBlock *)> *RemovalCallback = nullptr); |
132 | }; |
133 | |
134 | } // end namespace llvm |
135 | |
136 | #endif // LLVM_CODEGEN_TAILDUPLICATOR_H |
137 | |