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
12#include "HexagonTargetMachine.h"
13#include "llvm/ADT/DenseMap.h"
14#include "llvm/ADT/PostOrderIterator.h"
15#include "llvm/ADT/StringRef.h"
16#include "llvm/ADT/Twine.h"
17#include "llvm/CodeGen/LiveInterval.h"
18#include "llvm/CodeGen/LiveIntervals.h"
19#include "llvm/CodeGen/MachineDominators.h"
20#include "llvm/CodeGen/MachineRegisterInfo.h"
21#include "llvm/Support/CommandLine.h"
22#include "llvm/Support/Debug.h"
23
24#define DEBUG_TYPE "CopyHoist"
25
26using namespace llvm;
27
28static cl::opt<std::string> CPHoistFn("cphoistfn", cl::Hidden, cl::desc(""),
29 cl::init(Val: ""));
30
31namespace llvm {
32void initializeHexagonCopyHoistingPass(PassRegistry &Registry);
33FunctionPass *createHexagonCopyHoisting();
34} // namespace llvm
35
36namespace {
37
38class HexagonCopyHoisting : public MachineFunctionPass {
39
40public:
41 static char ID;
42 HexagonCopyHoisting() : MachineFunctionPass(ID), MFN(nullptr), MRI(nullptr) {
43 initializeHexagonCopyHoistingPass(Registry&: *PassRegistry::getPassRegistry());
44 }
45
46 StringRef getPassName() const override { return "Hexagon Copy Hoisting"; }
47
48 void getAnalysisUsage(AnalysisUsage &AU) const override {
49 AU.addRequired<SlotIndexesWrapperPass>();
50 AU.addRequired<LiveIntervalsWrapperPass>();
51 AU.addPreserved<SlotIndexesWrapperPass>();
52 AU.addPreserved<LiveIntervalsWrapperPass>();
53 AU.addRequired<MachineDominatorTreeWrapperPass>();
54 AU.addPreserved<MachineDominatorTreeWrapperPass>();
55 MachineFunctionPass::getAnalysisUsage(AU);
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;
67 MachineRegisterInfo *MRI;
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(new_size: 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(G: &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: *BB->pred_begin());
106 }
107 }
108 // Re-compute liveness
109 if (Changed) {
110 LiveIntervals &LIS = getAnalysis<LiveIntervalsWrapperPass>().getLIS();
111 SlotIndexes *SI = LIS.getSlotIndexes();
112 SI->reanalyze(MF&: Fn);
113 LIS.reanalyze(MF&: Fn);
114 }
115 return Changed;
116}
117
118//===----------------------------------------------------------------------===//
119// Save all COPY instructions for each basic block in CopyMIList vector.
120//===----------------------------------------------------------------------===//
121void HexagonCopyHoisting::collectCopyInst() {
122 for (MachineBasicBlock &BB : *MFN) {
123#ifndef NDEBUG
124 auto &BBCopyInst = CopyMIList[BB.getNumber()];
125 LLVM_DEBUG(dbgs() << "Visiting BB#" << BB.getNumber() << ":\n");
126#endif
127
128 for (MachineInstr &MI : BB) {
129 if (MI.getOpcode() == TargetOpcode::COPY)
130 addMItoCopyList(MI: &MI);
131 }
132 LLVM_DEBUG(dbgs() << "\tNumber of copies: " << BBCopyInst.size() << "\n");
133 }
134}
135
136void HexagonCopyHoisting::addMItoCopyList(MachineInstr *MI) {
137 unsigned BBNum = MI->getParent()->getNumber();
138 auto &BBCopyInst = CopyMIList[BBNum];
139 Register DstReg = MI->getOperand(i: 0).getReg();
140 Register SrcReg = MI->getOperand(i: 1).getReg();
141
142 if (!Register::isVirtualRegister(Reg: DstReg) ||
143 !Register::isVirtualRegister(Reg: SrcReg) ||
144 MRI->getRegClass(Reg: DstReg) != &Hexagon::IntRegsRegClass ||
145 MRI->getRegClass(Reg: SrcReg) != &Hexagon::IntRegsRegClass)
146 return;
147
148 BBCopyInst.insert(KV: std::pair(std::pair(SrcReg, DstReg), MI));
149#ifndef NDEBUG
150 LLVM_DEBUG(dbgs() << "\tAdding Copy Instr to the list: " << MI << "\n");
151 for (auto II : BBCopyInst) {
152 MachineInstr *TempMI = II.getSecond();
153 LLVM_DEBUG(dbgs() << "\tIn the list: " << TempMI << "\n");
154 }
155#endif
156}
157
158//===----------------------------------------------------------------------===//
159// Look at the COPY instructions of all the successors of BB. If the same
160// instruction is present in every successor and can be safely moved,
161// pull it into BB.
162//===----------------------------------------------------------------------===//
163bool HexagonCopyHoisting::analyzeCopy(MachineBasicBlock *BB) {
164
165 bool Changed = false;
166 if (BB->succ_size() < 2)
167 return false;
168
169 for (MachineBasicBlock *SB : BB->successors()) {
170 if (SB->pred_size() != 1 || SB->isEHPad() || SB->hasAddressTaken())
171 return false;
172 }
173
174 MachineBasicBlock *SBB1 = *BB->succ_begin();
175 auto &BBCopyInst1 = CopyMIList[SBB1->getNumber()];
176
177 for (auto II : BBCopyInst1) {
178 std::pair<Register, Register> Key = II.getFirst();
179 MachineInstr *MI = II.getSecond();
180 bool IsSafetoMove = true;
181 for (MachineBasicBlock *SuccBB : BB->successors()) {
182 auto &SuccBBCopyInst = CopyMIList[SuccBB->getNumber()];
183 if (!SuccBBCopyInst.count(Val: Key)) {
184 // Same copy not present in this successor
185 IsSafetoMove = false;
186 break;
187 }
188 // If present, make sure that it's safe to pull this copy instruction
189 // into the predecessor.
190 MachineInstr *SuccMI = SuccBBCopyInst[Key];
191 if (!isSafetoMove(CandMI: SuccMI)) {
192 IsSafetoMove = false;
193 break;
194 }
195 }
196 // If we have come this far, this copy instruction can be safely
197 // moved to the predecessor basic block.
198 if (IsSafetoMove) {
199 LLVM_DEBUG(dbgs() << "\t\t Moving instr to BB#" << BB->getNumber() << ": "
200 << MI << "\n");
201 moveCopyInstr(DestBB: BB, Key, MI);
202 // Add my into BB copyMI list.
203 Changed = true;
204 }
205 }
206
207#ifndef NDEBUG
208 auto &BBCopyInst = CopyMIList[BB->getNumber()];
209 for (auto II : BBCopyInst) {
210 MachineInstr *TempMI = II.getSecond();
211 LLVM_DEBUG(dbgs() << "\tIn the list: " << TempMI << "\n");
212 }
213#endif
214 return Changed;
215}
216
217bool HexagonCopyHoisting::isSafetoMove(MachineInstr *CandMI) {
218 // Make sure that it's safe to move this 'copy' instruction to the predecessor
219 // basic block.
220 assert(CandMI->getOperand(0).isReg() && CandMI->getOperand(1).isReg());
221 Register DefR = CandMI->getOperand(i: 0).getReg();
222 Register UseR = CandMI->getOperand(i: 1).getReg();
223
224 MachineBasicBlock *BB = CandMI->getParent();
225 // There should not be a def/use of DefR between the start of BB and CandMI.
226 MachineBasicBlock::iterator MII, MIE;
227 for (MII = BB->begin(), MIE = CandMI; MII != MIE; ++MII) {
228 MachineInstr *OtherMI = &*MII;
229 for (const MachineOperand &Mo : OtherMI->operands())
230 if (Mo.isReg() && Mo.getReg() == DefR)
231 return false;
232 }
233 // There should not be a def of UseR between the start of BB and CandMI.
234 for (MII = BB->begin(), MIE = CandMI; MII != MIE; ++MII) {
235 MachineInstr *OtherMI = &*MII;
236 for (const MachineOperand &Mo : OtherMI->operands())
237 if (Mo.isReg() && Mo.isDef() && Mo.getReg() == UseR)
238 return false;
239 }
240 return true;
241}
242
243void HexagonCopyHoisting::moveCopyInstr(MachineBasicBlock *DestBB,
244 std::pair<Register, Register> Key,
245 MachineInstr *MI) {
246 MachineBasicBlock::iterator FirstTI = DestBB->getFirstTerminator();
247 assert(FirstTI != DestBB->end());
248
249 DestBB->splice(Where: FirstTI, Other: MI->getParent(), From: MI);
250
251 addMItoCopyList(MI);
252 for (auto I = ++(DestBB->succ_begin()), E = DestBB->succ_end(); I != E; ++I) {
253 MachineBasicBlock *SuccBB = *I;
254 auto &BBCopyInst = CopyMIList[SuccBB->getNumber()];
255 MachineInstr *SuccMI = BBCopyInst[Key];
256 SuccMI->eraseFromParent();
257 BBCopyInst.erase(Val: Key);
258 }
259}
260
261//===----------------------------------------------------------------------===//
262// Public Constructor Functions
263//===----------------------------------------------------------------------===//
264
265INITIALIZE_PASS(HexagonCopyHoisting, "hexagon-move-phicopy",
266 "Hexagon move phi copy", false, false)
267
268FunctionPass *llvm::createHexagonCopyHoisting() {
269 return new HexagonCopyHoisting();
270}
271