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
24namespace llvm {
25
26struct CodeGenOptions;
27template <typename T, unsigned int N> class SmallSetVector;
28template <typename Fn> class function_ref;
29class MBFIWrapper;
30class MachineBasicBlock;
31class MachineBranchProbabilityInfo;
32class MachineFunction;
33class MachineInstr;
34class MachineModuleInfo;
35class MachineRegisterInfo;
36class ProfileSummaryInfo;
37class TargetRegisterInfo;
38
39/// Utility class to perform tail duplication.
40class TailDuplicator {
41 const CodeGenOptions *Opts;
42 const TargetInstrInfo *TII;
43 const TargetRegisterInfo *TRI;
44 const MachineBranchProbabilityInfo *MBPI;
45 MachineRegisterInfo *MRI;
46 MachineFunction *MF;
47 MBFIWrapper *MBFI;
48 ProfileSummaryInfo *PSI;
49 bool PreRegAlloc;
50 bool LayoutMode;
51 unsigned TailDupSize;
52
53 // A list of virtual registers for which to update SSA form.
54 SmallVector<Register, 16> SSAUpdateVRs;
55
56 // For each virtual register in SSAUpdateVals keep a list of source virtual
57 // registers.
58 using AvailableValsTy = std::vector<std::pair<MachineBasicBlock *, Register>>;
59
60 DenseMap<Register, AvailableValsTy> SSAUpdateVals;
61
62public:
63 /// Prepare to run on a specific machine function.
64 /// @param MF - Function that will be processed
65 /// @param PreRegAlloc - true if used before register allocation
66 /// @param MBPI - Branch Probability Info. Used to propagate correct
67 /// probabilities when modifying the CFG.
68 /// @param LayoutMode - When true, don't use the existing layout to make
69 /// decisions.
70 /// @param TailDupSize - Maxmimum size of blocks to tail-duplicate. Zero
71 /// default implies using the command line value TailDupSize.
72 LLVM_ABI void initMF(MachineFunction &MF, bool PreRegAlloc,
73 const MachineBranchProbabilityInfo *MBPI,
74 MBFIWrapper *MBFI, ProfileSummaryInfo *PSI,
75 bool LayoutMode, unsigned TailDupSize = 0);
76
77 LLVM_ABI bool tailDuplicateBlocks();
78 LLVM_ABI static bool isSimpleBB(MachineBasicBlock *TailBB);
79 LLVM_ABI bool shouldTailDuplicate(bool IsSimple, MachineBasicBlock &TailBB);
80
81 /// Returns true if TailBB can successfully be duplicated into PredBB
82 LLVM_ABI bool canTailDuplicate(MachineBasicBlock *TailBB,
83 MachineBasicBlock *PredBB);
84
85 /// Tail duplicate a single basic block into its predecessors, and then clean
86 /// up.
87 /// If \p DuplicatePreds is not null, it will be updated to contain the list
88 /// of predecessors that received a copy of \p MBB.
89 /// If \p RemovalCallback is non-null. It will be called before MBB is
90 /// deleted.
91 /// If \p CandidatePtr is not null, duplicate into these blocks only.
92 LLVM_ABI bool tailDuplicateAndUpdate(
93 bool IsSimple, MachineBasicBlock *MBB,
94 MachineBasicBlock *ForcedLayoutPred,
95 SmallVectorImpl<MachineBasicBlock *> *DuplicatedPreds = nullptr,
96 function_ref<void(MachineBasicBlock *)> *RemovalCallback = nullptr,
97 SmallVectorImpl<MachineBasicBlock *> *CandidatePtr = nullptr);
98
99private:
100 using RegSubRegPair = TargetInstrInfo::RegSubRegPair;
101
102 void addSSAUpdateEntry(Register OrigReg, Register NewReg,
103 MachineBasicBlock *BB);
104 void processPHI(MachineInstr *MI, MachineBasicBlock *TailBB,
105 MachineBasicBlock *PredBB,
106 DenseMap<Register, RegSubRegPair> &LocalVRMap,
107 SmallVectorImpl<std::pair<Register, RegSubRegPair>> &Copies,
108 const DenseSet<Register> &UsedByPhi, bool Remove);
109 void duplicateInstruction(MachineInstr *MI, MachineBasicBlock *TailBB,
110 MachineBasicBlock *PredBB,
111 DenseMap<Register, RegSubRegPair> &LocalVRMap,
112 const DenseSet<Register> &UsedByPhi);
113 void updateSuccessorsPHIs(MachineBasicBlock *FromBB, bool isDead,
114 SmallVectorImpl<MachineBasicBlock *> &TDBBs,
115 SmallSetVector<MachineBasicBlock *, 8> &Succs);
116 bool canCompletelyDuplicateBB(MachineBasicBlock &BB);
117 bool duplicateSimpleBB(MachineBasicBlock *TailBB,
118 SmallVectorImpl<MachineBasicBlock *> &TDBBs,
119 const DenseSet<Register> &RegsUsedByPhi);
120 bool tailDuplicate(bool IsSimple,
121 MachineBasicBlock *TailBB,
122 MachineBasicBlock *ForcedLayoutPred,
123 SmallVectorImpl<MachineBasicBlock *> &TDBBs,
124 SmallVectorImpl<MachineInstr *> &Copies,
125 SmallVectorImpl<MachineBasicBlock *> *CandidatePtr);
126 void appendCopies(MachineBasicBlock *MBB,
127 SmallVectorImpl<std::pair<Register, RegSubRegPair>> &CopyInfos,
128 SmallVectorImpl<MachineInstr *> &Copies);
129
130 void removeDeadBlock(
131 MachineBasicBlock *MBB,
132 function_ref<void(MachineBasicBlock *)> *RemovalCallback = nullptr);
133};
134
135} // end namespace llvm
136
137#endif // LLVM_CODEGEN_TAILDUPLICATOR_H
138