llvm/lib/Target/Hexagon/HexagonCopyHoisting.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-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 (MachineBasicBlock *SuccBB : drop_begin(DestBB->successors())) {
 253     auto &BBCopyInst = CopyMIList[SuccBB->getNumber()];
 254     MachineInstr *SuccMI = BBCopyInst[Key];
 255     SuccMI->eraseFromParent();
 256     BBCopyInst.erase(Key);
 257   }
 258 }
 259
 260 //===----------------------------------------------------------------------===//
 261 //                         Public Constructor Functions
 262 //===----------------------------------------------------------------------===//
 263
 264 INITIALIZE_PASS(HexagonCopyHoisting, "hexagon-move-phicopy",
 265                 "Hexagon move phi copy", false, false)
 266
 267 FunctionPass *llvm::createHexagonCopyHoisting() {
 268   return new HexagonCopyHoisting();
 269 }