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 26 using namespace llvm; 27 28 static cl::opt<std::string> CPHoistFn("cphoistfn", cl::Hidden, cl::desc(""), 29 cl::init("")); 30 31 namespace llvm { 32 void initializeHexagonCopyHoistingPass(PassRegistry &Registry); 33 FunctionPass *createHexagonCopyHoisting(); 34 } // namespace llvm 35 36 namespace { 37 38 class HexagonCopyHoisting : public MachineFunctionPass { 39 40 public: 41 static char ID; 42 HexagonCopyHoisting() : MachineFunctionPass(ID), MFN(nullptr), MRI(nullptr) { 43 initializeHexagonCopyHoistingPass(*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 74 char HexagonCopyHoisting::ID = 0; 75 76 namespace llvm { 77 char &HexagonCopyHoistingID = HexagonCopyHoisting::ID; 78 } // namespace llvm 79 80 bool 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<LiveIntervalsWrapperPass>().getLIS(); 111 SlotIndexes *SI = LIS.getSlotIndexes(); 112 SI->reanalyze(Fn); 113 LIS.reanalyze(Fn); 114 } 115 return Changed; 116 } 117 118 //===----------------------------------------------------------------------===// 119 // Save all COPY instructions for each basic block in CopyMIList vector. 120 //===----------------------------------------------------------------------===// 121 void 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); 131 } 132 LLVM_DEBUG(dbgs() << "\tNumber of copies: " << BBCopyInst.size() << "\n"); 133 } 134 } 135 136 void HexagonCopyHoisting::addMItoCopyList(MachineInstr *MI) { 137 unsigned BBNum = MI->getParent()->getNumber(); 138 auto &BBCopyInst = CopyMIList[BBNum]; 139 Register DstReg = MI->getOperand(0).getReg(); 140 Register SrcReg = MI->getOperand(1).getReg(); 141 142 if (!Register::isVirtualRegister(DstReg) || 143 !Register::isVirtualRegister(SrcReg) || 144 MRI->getRegClass(DstReg) != &Hexagon::IntRegsRegClass || 145 MRI->getRegClass(SrcReg) != &Hexagon::IntRegsRegClass) 146 return; 147 148 BBCopyInst.insert(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 //===----------------------------------------------------------------------===// 163 bool 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(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(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(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 217 bool 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(0).getReg(); 222 Register UseR = CandMI->getOperand(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 243 void 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(FirstTI, MI->getParent(), 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(Key); 258 } 259 } 260 261 //===----------------------------------------------------------------------===// 262 // Public Constructor Functions 263 //===----------------------------------------------------------------------===// 264 265 INITIALIZE_PASS(HexagonCopyHoisting, "hexagon-move-phicopy", 266 "Hexagon move phi copy", false, false) 267 268 FunctionPass *llvm::createHexagonCopyHoisting() { 269 return new HexagonCopyHoisting(); 270 } 271