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 {
32
33class HexagonCopyHoisting : public MachineFunctionPass {
34
35public:
36 static char ID;
37 HexagonCopyHoisting() : MachineFunctionPass(ID) {}
38
39 StringRef getPassName() const override { return "Hexagon Copy Hoisting"; }
40
41 void getAnalysisUsage(AnalysisUsage &AU) const override {
42 AU.addRequired<SlotIndexesWrapperPass>();
43 AU.addRequired<LiveIntervalsWrapperPass>();
44 AU.addPreserved<SlotIndexesWrapperPass>();
45 AU.addPreserved<LiveIntervalsWrapperPass>();
46 AU.addPreserved<MachineDominatorTreeWrapperPass>();
47 MachineFunctionPass::getAnalysisUsage(AU);
48 }
49
50 bool runOnMachineFunction(MachineFunction &Fn) override;
51 void collectCopyInst();
52 void addMItoCopyList(MachineInstr *MI);
53 bool analyzeCopy(MachineBasicBlock *BB);
54 bool isSafetoMove(MachineInstr *CandMI);
55 void moveCopyInstr(MachineBasicBlock *DestBB,
56 std::pair<Register, Register> Key, MachineInstr *MI);
57
58 MachineFunction *MFN = nullptr;
59 MachineRegisterInfo *MRI = nullptr;
60 std::vector<DenseMap<std::pair<Register, Register>, MachineInstr *>>
61 CopyMIList;
62};
63
64} // namespace
65
66char HexagonCopyHoisting::ID = 0;
67
68namespace llvm {
69char &HexagonCopyHoistingID = HexagonCopyHoisting::ID;
70} // namespace llvm
71
72bool HexagonCopyHoisting::runOnMachineFunction(MachineFunction &Fn) {
73
74 if ((CPHoistFn != "") && (CPHoistFn != Fn.getFunction().getName()))
75 return false;
76
77 MFN = &Fn;
78 MRI = &Fn.getRegInfo();
79
80 LLVM_DEBUG(dbgs() << "\nCopy Hoisting:" << "\'" << Fn.getName() << "\'\n");
81
82 CopyMIList.clear();
83 CopyMIList.resize(new_size: Fn.getNumBlockIDs());
84
85 // Traverse through all basic blocks and collect copy instructions.
86 collectCopyInst();
87
88 // Traverse through the basic blocks again and move the COPY instructions
89 // that are present in all the successors of BB to BB.
90 bool Changed = false;
91 for (MachineBasicBlock *BB : post_order(G: &Fn)) {
92 if (!BB->empty()) {
93 if (BB->pred_size() != 1)
94 continue;
95 auto &BBCopyInst = CopyMIList[BB->getNumber()];
96 if (BBCopyInst.size() > 0)
97 Changed |= analyzeCopy(BB: *BB->pred_begin());
98 }
99 }
100 // Re-compute liveness
101 if (Changed) {
102 LiveIntervals &LIS = getAnalysis<LiveIntervalsWrapperPass>().getLIS();
103 SlotIndexes *SI = LIS.getSlotIndexes();
104 SI->reanalyze(MF&: Fn);
105 LIS.reanalyze(MF&: Fn);
106 }
107 return Changed;
108}
109
110//===----------------------------------------------------------------------===//
111// Save all COPY instructions for each basic block in CopyMIList vector.
112//===----------------------------------------------------------------------===//
113void HexagonCopyHoisting::collectCopyInst() {
114 for (MachineBasicBlock &BB : *MFN) {
115#ifndef NDEBUG
116 auto &BBCopyInst = CopyMIList[BB.getNumber()];
117 LLVM_DEBUG(dbgs() << "Visiting BB#" << BB.getNumber() << ":\n");
118#endif
119
120 for (MachineInstr &MI : BB) {
121 if (MI.getOpcode() == TargetOpcode::COPY)
122 addMItoCopyList(MI: &MI);
123 }
124 LLVM_DEBUG(dbgs() << "\tNumber of copies: " << BBCopyInst.size() << "\n");
125 }
126}
127
128void HexagonCopyHoisting::addMItoCopyList(MachineInstr *MI) {
129 unsigned BBNum = MI->getParent()->getNumber();
130 auto &BBCopyInst = CopyMIList[BBNum];
131 Register DstReg = MI->getOperand(i: 0).getReg();
132 Register SrcReg = MI->getOperand(i: 1).getReg();
133
134 if (!Register::isVirtualRegister(Reg: DstReg) ||
135 !Register::isVirtualRegister(Reg: SrcReg) ||
136 MRI->getRegClass(Reg: DstReg) != &Hexagon::IntRegsRegClass ||
137 MRI->getRegClass(Reg: SrcReg) != &Hexagon::IntRegsRegClass)
138 return;
139
140 BBCopyInst.insert(KV: std::pair(std::pair(SrcReg, DstReg), MI));
141#ifndef NDEBUG
142 LLVM_DEBUG(dbgs() << "\tAdding Copy Instr to the list: " << MI << "\n");
143 for (auto II : BBCopyInst) {
144 MachineInstr *TempMI = II.getSecond();
145 LLVM_DEBUG(dbgs() << "\tIn the list: " << TempMI << "\n");
146 }
147#endif
148}
149
150//===----------------------------------------------------------------------===//
151// Look at the COPY instructions of all the successors of BB. If the same
152// instruction is present in every successor and can be safely moved,
153// pull it into BB.
154//===----------------------------------------------------------------------===//
155bool HexagonCopyHoisting::analyzeCopy(MachineBasicBlock *BB) {
156
157 bool Changed = false;
158 if (BB->succ_size() < 2)
159 return false;
160
161 for (MachineBasicBlock *SB : BB->successors()) {
162 if (SB->pred_size() != 1 || SB->isEHPad() || SB->hasAddressTaken())
163 return false;
164 }
165
166 MachineBasicBlock *SBB1 = *BB->succ_begin();
167 auto &BBCopyInst1 = CopyMIList[SBB1->getNumber()];
168
169 for (auto II : BBCopyInst1) {
170 std::pair<Register, Register> Key = II.getFirst();
171 MachineInstr *MI = II.getSecond();
172 bool IsSafetoMove = true;
173 for (MachineBasicBlock *SuccBB : BB->successors()) {
174 auto &SuccBBCopyInst = CopyMIList[SuccBB->getNumber()];
175 auto It = SuccBBCopyInst.find(Val: Key);
176 if (It == SuccBBCopyInst.end()) {
177 // Same copy not present in this successor
178 IsSafetoMove = false;
179 break;
180 }
181 // If present, make sure that it's safe to pull this copy instruction
182 // into the predecessor.
183 MachineInstr *SuccMI = It->second;
184 if (!isSafetoMove(CandMI: SuccMI)) {
185 IsSafetoMove = false;
186 break;
187 }
188 }
189 // If we have come this far, this copy instruction can be safely
190 // moved to the predecessor basic block.
191 if (IsSafetoMove) {
192 LLVM_DEBUG(dbgs() << "\t\t Moving instr to BB#" << BB->getNumber() << ": "
193 << MI << "\n");
194 moveCopyInstr(DestBB: BB, Key, MI);
195 // Add my into BB copyMI list.
196 Changed = true;
197 }
198 }
199
200#ifndef NDEBUG
201 auto &BBCopyInst = CopyMIList[BB->getNumber()];
202 for (auto II : BBCopyInst) {
203 MachineInstr *TempMI = II.getSecond();
204 LLVM_DEBUG(dbgs() << "\tIn the list: " << TempMI << "\n");
205 }
206#endif
207 return Changed;
208}
209
210bool HexagonCopyHoisting::isSafetoMove(MachineInstr *CandMI) {
211 // Make sure that it's safe to move this 'copy' instruction to the predecessor
212 // basic block.
213 assert(CandMI->getOperand(0).isReg() && CandMI->getOperand(1).isReg());
214 Register DefR = CandMI->getOperand(i: 0).getReg();
215 Register UseR = CandMI->getOperand(i: 1).getReg();
216
217 MachineBasicBlock *BB = CandMI->getParent();
218 // There should not be a def/use of DefR between the start of BB and CandMI.
219 MachineBasicBlock::iterator MII, MIE;
220 for (MII = BB->begin(), MIE = CandMI; MII != MIE; ++MII) {
221 MachineInstr *OtherMI = &*MII;
222 for (const MachineOperand &Mo : OtherMI->operands())
223 if (Mo.isReg() && Mo.getReg() == DefR)
224 return false;
225 }
226 // There should not be a def of UseR between the start of BB and CandMI.
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.isDef() && Mo.getReg() == UseR)
231 return false;
232 }
233 return true;
234}
235
236void HexagonCopyHoisting::moveCopyInstr(MachineBasicBlock *DestBB,
237 std::pair<Register, Register> Key,
238 MachineInstr *MI) {
239 MachineBasicBlock::iterator FirstTI = DestBB->getFirstTerminator();
240 assert(FirstTI != DestBB->end());
241
242 DestBB->splice(Where: FirstTI, Other: MI->getParent(), From: MI);
243
244 addMItoCopyList(MI);
245 for (MachineBasicBlock *SuccBB : drop_begin(RangeOrContainer: DestBB->successors())) {
246 auto &BBCopyInst = CopyMIList[SuccBB->getNumber()];
247 MachineInstr *SuccMI = BBCopyInst[Key];
248 SuccMI->eraseFromParent();
249 BBCopyInst.erase(Val: Key);
250 }
251}
252
253//===----------------------------------------------------------------------===//
254// Public Constructor Functions
255//===----------------------------------------------------------------------===//
256
257INITIALIZE_PASS(HexagonCopyHoisting, "hexagon-move-phicopy",
258 "Hexagon move phi copy", false, false)
259
260FunctionPass *llvm::createHexagonCopyHoisting() {
261 return new HexagonCopyHoisting();
262}
263