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