LLVM 19.0.0git
HexagonCopyHoisting.cpp
Go to the documentation of this file.
1//===--------- HexagonCopyHoisting.cpp - Hexagon Copy Hoisting ----------===//
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// The purpose of this pass is to move the copy instructions that are
9// present in all the successor of a basic block (BB) to the end of BB.
10//===----------------------------------------------------------------------===//
11
13#include "llvm/ADT/DenseMap.h"
15#include "llvm/ADT/StringRef.h"
16#include "llvm/ADT/Twine.h"
22#include "llvm/Support/Debug.h"
23
24#define DEBUG_TYPE "CopyHoist"
25
26using namespace llvm;
27
29 cl::init(""));
30
31namespace llvm {
34} // namespace llvm
35
36namespace {
37
38class HexagonCopyHoisting : public MachineFunctionPass {
39
40public:
41 static char ID;
42 HexagonCopyHoisting() : MachineFunctionPass(ID), MFN(nullptr), MRI(nullptr) {
44 }
45
46 StringRef getPassName() const override { return "Hexagon Copy Hoisting"; }
47
48 void getAnalysisUsage(AnalysisUsage &AU) const override {
56 }
57
58 bool runOnMachineFunction(MachineFunction &Fn) override;
59 void collectCopyInst();
60 void addMItoCopyList(MachineInstr *MI);
61 bool analyzeCopy(MachineBasicBlock *BB);
62 bool isSafetoMove(MachineInstr *CandMI);
63 void moveCopyInstr(MachineBasicBlock *DestBB,
64 std::pair<Register, Register> Key, MachineInstr *MI);
65
66 MachineFunction *MFN;
68 std::vector<DenseMap<std::pair<Register, Register>, MachineInstr *>>
69 CopyMIList;
70};
71
72} // namespace
73
74char HexagonCopyHoisting::ID = 0;
75
76namespace llvm {
77char &HexagonCopyHoistingID = HexagonCopyHoisting::ID;
78} // namespace llvm
79
80bool HexagonCopyHoisting::runOnMachineFunction(MachineFunction &Fn) {
81
82 if ((CPHoistFn != "") && (CPHoistFn != Fn.getFunction().getName()))
83 return false;
84
85 MFN = &Fn;
86 MRI = &Fn.getRegInfo();
87
88 LLVM_DEBUG(dbgs() << "\nCopy Hoisting:" << "\'" << Fn.getName() << "\'\n");
89
90 CopyMIList.clear();
91 CopyMIList.resize(Fn.getNumBlockIDs());
92
93 // Traverse through all basic blocks and collect copy instructions.
94 collectCopyInst();
95
96 // Traverse through the basic blocks again and move the COPY instructions
97 // that are present in all the successors of BB to BB.
98 bool Changed = false;
99 for (MachineBasicBlock *BB : post_order(&Fn)) {
100 if (!BB->empty()) {
101 if (BB->pred_size() != 1)
102 continue;
103 auto &BBCopyInst = CopyMIList[BB->getNumber()];
104 if (BBCopyInst.size() > 0)
105 Changed |= analyzeCopy(*BB->pred_begin());
106 }
107 }
108 // Re-compute liveness
109 if (Changed) {
110 LiveIntervals &LIS = getAnalysis<LiveIntervals>();
112 SI->releaseMemory();
113 SI->runOnMachineFunction(Fn);
114 LIS.releaseMemory();
115 LIS.runOnMachineFunction(Fn);
116 }
117 return Changed;
118}
119
120//===----------------------------------------------------------------------===//
121// Save all COPY instructions for each basic block in CopyMIList vector.
122//===----------------------------------------------------------------------===//
123void HexagonCopyHoisting::collectCopyInst() {
124 for (MachineBasicBlock &BB : *MFN) {
125#ifndef NDEBUG
126 auto &BBCopyInst = CopyMIList[BB.getNumber()];
127 LLVM_DEBUG(dbgs() << "Visiting BB#" << BB.getNumber() << ":\n");
128#endif
129
130 for (MachineInstr &MI : BB) {
131 if (MI.getOpcode() == TargetOpcode::COPY)
132 addMItoCopyList(&MI);
133 }
134 LLVM_DEBUG(dbgs() << "\tNumber of copies: " << BBCopyInst.size() << "\n");
135 }
136}
137
138void HexagonCopyHoisting::addMItoCopyList(MachineInstr *MI) {
139 unsigned BBNum = MI->getParent()->getNumber();
140 auto &BBCopyInst = CopyMIList[BBNum];
141 Register DstReg = MI->getOperand(0).getReg();
142 Register SrcReg = MI->getOperand(1).getReg();
143
144 if (!Register::isVirtualRegister(DstReg) ||
146 MRI->getRegClass(DstReg) != &Hexagon::IntRegsRegClass ||
147 MRI->getRegClass(SrcReg) != &Hexagon::IntRegsRegClass)
148 return;
149
150 BBCopyInst.insert(std::pair(std::pair(SrcReg, DstReg), MI));
151#ifndef NDEBUG
152 LLVM_DEBUG(dbgs() << "\tAdding Copy Instr to the list: " << MI << "\n");
153 for (auto II : BBCopyInst) {
154 MachineInstr *TempMI = II.getSecond();
155 LLVM_DEBUG(dbgs() << "\tIn the list: " << TempMI << "\n");
156 }
157#endif
158}
159
160//===----------------------------------------------------------------------===//
161// Look at the COPY instructions of all the successors of BB. If the same
162// instruction is present in every successor and can be safely moved,
163// pull it into BB.
164//===----------------------------------------------------------------------===//
165bool HexagonCopyHoisting::analyzeCopy(MachineBasicBlock *BB) {
166
167 bool Changed = false;
168 if (BB->succ_size() < 2)
169 return false;
170
171 for (MachineBasicBlock *SB : BB->successors()) {
172 if (SB->pred_size() != 1 || SB->isEHPad() || SB->hasAddressTaken())
173 return false;
174 }
175
176 MachineBasicBlock *SBB1 = *BB->succ_begin();
177 auto &BBCopyInst1 = CopyMIList[SBB1->getNumber()];
178
179 for (auto II : BBCopyInst1) {
180 std::pair<Register, Register> Key = II.getFirst();
181 MachineInstr *MI = II.getSecond();
182 bool IsSafetoMove = true;
183 for (MachineBasicBlock *SuccBB : BB->successors()) {
184 auto &SuccBBCopyInst = CopyMIList[SuccBB->getNumber()];
185 if (!SuccBBCopyInst.count(Key)) {
186 // Same copy not present in this successor
187 IsSafetoMove = false;
188 break;
189 }
190 // If present, make sure that it's safe to pull this copy instruction
191 // into the predecessor.
192 MachineInstr *SuccMI = SuccBBCopyInst[Key];
193 if (!isSafetoMove(SuccMI)) {
194 IsSafetoMove = false;
195 break;
196 }
197 }
198 // If we have come this far, this copy instruction can be safely
199 // moved to the predecessor basic block.
200 if (IsSafetoMove) {
201 LLVM_DEBUG(dbgs() << "\t\t Moving instr to BB#" << BB->getNumber() << ": "
202 << MI << "\n");
203 moveCopyInstr(BB, Key, MI);
204 // Add my into BB copyMI list.
205 Changed = true;
206 }
207 }
208
209#ifndef NDEBUG
210 auto &BBCopyInst = CopyMIList[BB->getNumber()];
211 for (auto II : BBCopyInst) {
212 MachineInstr *TempMI = II.getSecond();
213 LLVM_DEBUG(dbgs() << "\tIn the list: " << TempMI << "\n");
214 }
215#endif
216 return Changed;
217}
218
219bool HexagonCopyHoisting::isSafetoMove(MachineInstr *CandMI) {
220 // Make sure that it's safe to move this 'copy' instruction to the predecessor
221 // basic block.
222 assert(CandMI->getOperand(0).isReg() && CandMI->getOperand(1).isReg());
223 Register DefR = CandMI->getOperand(0).getReg();
224 Register UseR = CandMI->getOperand(1).getReg();
225
226 MachineBasicBlock *BB = CandMI->getParent();
227 // There should not be a def/use of DefR between the start of BB and CandMI.
229 for (MII = BB->begin(), MIE = CandMI; MII != MIE; ++MII) {
230 MachineInstr *OtherMI = &*MII;
231 for (const MachineOperand &Mo : OtherMI->operands())
232 if (Mo.isReg() && Mo.getReg() == DefR)
233 return false;
234 }
235 // There should not be a def of UseR between the start of BB and CandMI.
236 for (MII = BB->begin(), MIE = CandMI; MII != MIE; ++MII) {
237 MachineInstr *OtherMI = &*MII;
238 for (const MachineOperand &Mo : OtherMI->operands())
239 if (Mo.isReg() && Mo.isDef() && Mo.getReg() == UseR)
240 return false;
241 }
242 return true;
243}
244
245void HexagonCopyHoisting::moveCopyInstr(MachineBasicBlock *DestBB,
246 std::pair<Register, Register> Key,
247 MachineInstr *MI) {
249 assert(FirstTI != DestBB->end());
250
251 DestBB->splice(FirstTI, MI->getParent(), MI);
252
253 addMItoCopyList(MI);
254 for (auto I = ++(DestBB->succ_begin()), E = DestBB->succ_end(); I != E; ++I) {
255 MachineBasicBlock *SuccBB = *I;
256 auto &BBCopyInst = CopyMIList[SuccBB->getNumber()];
257 MachineInstr *SuccMI = BBCopyInst[Key];
258 SuccMI->eraseFromParent();
259 BBCopyInst.erase(Key);
260 }
261}
262
263//===----------------------------------------------------------------------===//
264// Public Constructor Functions
265//===----------------------------------------------------------------------===//
266
267INITIALIZE_PASS(HexagonCopyHoisting, "hexagon-move-phicopy",
268 "Hexagon move phi copy", false, false)
269
271 return new HexagonCopyHoisting();
272}
unsigned const MachineRegisterInfo * MRI
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file defines the DenseMap class.
static cl::opt< std::string > CPHoistFn("cphoistfn", cl::Hidden, cl::desc(""), cl::init(""))
IRTranslator LLVM IR MI
#define I(x, y, z)
Definition: MD5.cpp:58
uint64_t IntrinsicInst * II
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:38
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:311
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
SlotIndexes * getSlotIndexes() const
bool runOnMachineFunction(MachineFunction &) override
Pass entry point; Calculates LiveIntervals.
int getNumber() const
MachineBasicBlocks are uniquely numbered at the function level, unless they're not in a MachineFuncti...
iterator getFirstTerminator()
Returns an iterator to the first terminator instruction of this basic block.
unsigned succ_size() const
iterator_range< succ_iterator > successors()
void splice(iterator Where, MachineBasicBlock *Other, iterator From)
Take an instruction from MBB 'Other' at the position From, and insert it into this MBB right before '...
Analysis pass which computes a MachineDominatorTree.
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
virtual bool runOnMachineFunction(MachineFunction &MF)=0
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Function & getFunction()
Return the LLVM function that this machine code represents.
unsigned getNumBlockIDs() const
getNumBlockIDs - Return the number of MBB ID's allocated.
Representation of each machine instruction.
Definition: MachineInstr.h:69
const MachineBasicBlock * getParent() const
Definition: MachineInstr.h:343
iterator_range< mop_iterator > operands()
Definition: MachineInstr.h:682
void eraseFromParent()
Unlink 'this' from the containing basic block and delete it.
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:576
MachineOperand class - Representation of each machine instruction operand.
bool isReg() const
isReg - Tests if this is a MO_Register operand.
Register getReg() const
getReg - Returns the register number.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...
Definition: PassRegistry.h:37
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
Definition: Pass.cpp:81
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
static constexpr bool isVirtualRegister(unsigned Reg)
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:71
A global registry used in conjunction with static constructors to make pluggable components (like tar...
Definition: Registry.h:44
SlotIndexes pass.
Definition: SlotIndexes.h:300
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
Key
PAL metadata keys.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:443
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
FunctionPass * createHexagonCopyHoisting()
iterator_range< po_iterator< T > > post_order(const T &G)
void initializeHexagonCopyHoistingPass(PassRegistry &Registry)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
char & HexagonCopyHoistingID