llvm/lib/Target/Hexagon/HexagonRDFOpt.cpp

   1 //===- HexagonRDFOpt.cpp --------------------------------------------------===//
   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
   9 #include "HexagonInstrInfo.h"
  10 #include "HexagonSubtarget.h"
  11 #include "MCTargetDesc/HexagonBaseInfo.h"
  12 #include "RDFCopy.h"
  13 #include "RDFDeadCode.h"
  14 #include "llvm/ADT/DenseMap.h"
  15 #include "llvm/ADT/STLExtras.h"
  16 #include "llvm/ADT/SetVector.h"
  17 #include "llvm/CodeGen/MachineDominanceFrontier.h"
  18 #include "llvm/CodeGen/MachineDominators.h"
  19 #include "llvm/CodeGen/MachineFunction.h"
  20 #include "llvm/CodeGen/MachineFunctionPass.h"
  21 #include "llvm/CodeGen/MachineInstr.h"
  22 #include "llvm/CodeGen/MachineOperand.h"
  23 #include "llvm/CodeGen/MachineRegisterInfo.h"
  24 #include "llvm/CodeGen/RDFGraph.h"
  25 #include "llvm/CodeGen/RDFLiveness.h"
  26 #include "llvm/CodeGen/RDFRegisters.h"
  27 #include "llvm/InitializePasses.h"
  28 #include "llvm/Pass.h"
  29 #include "llvm/Support/CommandLine.h"
  30 #include "llvm/Support/Compiler.h"
  31 #include "llvm/Support/Debug.h"
  32 #include "llvm/Support/ErrorHandling.h"
  33 #include "llvm/Support/raw_ostream.h"
  34 #include <cassert>
  35 #include <limits>
  36 #include <utility>
  37
  38 using namespace llvm;
  39 using namespace rdf;
  40
  41 namespace llvm {
  42
  43   void initializeHexagonRDFOptPass(PassRegistry&);
  44   FunctionPass *createHexagonRDFOpt();
  45
  46 } // end namespace llvm
  47
  48 static unsigned RDFCount = 0;
  49
  50 static cl::opt<unsigned> RDFLimit("rdf-limit",
  51     cl::init(std::numeric_limits<unsigned>::max()));
  52 static cl::opt<bool> RDFDump("rdf-dump", cl::init(false));
  53
  54 namespace {
  55
  56   class HexagonRDFOpt : public MachineFunctionPass {
  57   public:
  58     HexagonRDFOpt() : MachineFunctionPass(ID) {}
  59
  60     void getAnalysisUsage(AnalysisUsage &AU) const override {
  61       AU.addRequired<MachineDominatorTree>();
  62       AU.addRequired<MachineDominanceFrontier>();
  63       AU.setPreservesAll();
  64       MachineFunctionPass::getAnalysisUsage(AU);
  65     }
  66
  67     StringRef getPassName() const override {
  68       return "Hexagon RDF optimizations";
  69     }
  70
  71     bool runOnMachineFunction(MachineFunction &MF) override;
  72
  73     MachineFunctionProperties getRequiredProperties() const override {
  74       return MachineFunctionProperties().set(
  75           MachineFunctionProperties::Property::NoVRegs);
  76     }
  77
  78     static char ID;
  79
  80   private:
  81     MachineDominatorTree *MDT;
  82     MachineRegisterInfo *MRI;
  83   };
  84
  85 struct HexagonCP : public CopyPropagation {
  86   HexagonCP(DataFlowGraph &G) : CopyPropagation(G) {}
  87
  88   bool interpretAsCopy(const MachineInstr *MI, EqualityMap &EM) override;
  89 };
  90
  91 struct HexagonDCE : public DeadCodeElimination {
  92   HexagonDCE(DataFlowGraph &G, MachineRegisterInfo &MRI)
  93     : DeadCodeElimination(G, MRI) {}
  94
  95   bool rewrite(NodeAddr<InstrNode*> IA, SetVector<NodeId> &Remove);
  96   void removeOperand(NodeAddr<InstrNode*> IA, unsigned OpNum);
  97
  98   bool run();
  99 };
 100
 101 } // end anonymous namespace
 102
 103 char HexagonRDFOpt::ID = 0;
 104
 105 INITIALIZE_PASS_BEGIN(HexagonRDFOpt, "hexagon-rdf-opt",
 106       "Hexagon RDF optimizations", false, false)
 107 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
 108 INITIALIZE_PASS_DEPENDENCY(MachineDominanceFrontier)
 109 INITIALIZE_PASS_END(HexagonRDFOpt, "hexagon-rdf-opt",
 110       "Hexagon RDF optimizations", false, false)
 111
 112 bool HexagonCP::interpretAsCopy(const MachineInstr *MI, EqualityMap &EM) {
 113   auto mapRegs = [&EM] (RegisterRef DstR, RegisterRef SrcR) -> void {
 114     EM.insert(std::make_pair(DstR, SrcR));
 115   };
 116
 117   DataFlowGraph &DFG = getDFG();
 118   unsigned Opc = MI->getOpcode();
 119   switch (Opc) {
 120     case Hexagon::A2_combinew: {
 121       const MachineOperand &DstOp = MI->getOperand(0);
 122       const MachineOperand &HiOp = MI->getOperand(1);
 123       const MachineOperand &LoOp = MI->getOperand(2);
 124       assert(DstOp.getSubReg() == 0 && "Unexpected subregister");
 125       mapRegs(DFG.makeRegRef(DstOp.getReg(), Hexagon::isub_hi),
 126               DFG.makeRegRef(HiOp.getReg(),  HiOp.getSubReg()));
 127       mapRegs(DFG.makeRegRef(DstOp.getReg(), Hexagon::isub_lo),
 128               DFG.makeRegRef(LoOp.getReg(), LoOp.getSubReg()));
 129       return true;
 130     }
 131     case Hexagon::A2_addi: {
 132       const MachineOperand &A = MI->getOperand(2);
 133       if (!A.isImm() || A.getImm() != 0)
 134         return false;
 135       LLVM_FALLTHROUGH;
 136     }
 137     case Hexagon::A2_tfr: {
 138       const MachineOperand &DstOp = MI->getOperand(0);
 139       const MachineOperand &SrcOp = MI->getOperand(1);
 140       mapRegs(DFG.makeRegRef(DstOp.getReg(), DstOp.getSubReg()),
 141               DFG.makeRegRef(SrcOp.getReg(), SrcOp.getSubReg()));
 142       return true;
 143     }
 144   }
 145
 146   return CopyPropagation::interpretAsCopy(MI, EM);
 147 }
 148
 149 bool HexagonDCE::run() {
 150   bool Collected = collect();
 151   if (!Collected)
 152     return false;
 153
 154   const SetVector<NodeId> &DeadNodes = getDeadNodes();
 155   const SetVector<NodeId> &DeadInstrs = getDeadInstrs();
 156
 157   using RefToInstrMap = DenseMap<NodeId, NodeId>;
 158
 159   RefToInstrMap R2I;
 160   SetVector<NodeId> PartlyDead;
 161   DataFlowGraph &DFG = getDFG();
 162
 163   for (NodeAddr<BlockNode*> BA : DFG.getFunc().Addr->members(DFG)) {
 164     for (auto TA : BA.Addr->members_if(DFG.IsCode<NodeAttrs::Stmt>, DFG)) {
 165       NodeAddr<StmtNode*> SA = TA;
 166       for (NodeAddr<RefNode*> RA : SA.Addr->members(DFG)) {
 167         R2I.insert(std::make_pair(RA.Id, SA.Id));
 168         if (DFG.IsDef(RA) && DeadNodes.count(RA.Id))
 169           if (!DeadInstrs.count(SA.Id))
 170             PartlyDead.insert(SA.Id);
 171       }
 172     }
 173   }
 174
 175   // Nodes to remove.
 176   SetVector<NodeId> Remove = DeadInstrs;
 177
 178   bool Changed = false;
 179   for (NodeId N : PartlyDead) {
 180     auto SA = DFG.addr<StmtNode*>(N);
 181     if (trace())
 182       dbgs() << "Partly dead: " << *SA.Addr->getCode();
 183     Changed |= rewrite(SA, Remove);
 184   }
 185
 186   return erase(Remove) || Changed;
 187 }
 188
 189 void HexagonDCE::removeOperand(NodeAddr<InstrNode*> IA, unsigned OpNum) {
 190   MachineInstr *MI = NodeAddr<StmtNode*>(IA).Addr->getCode();
 191
 192   auto getOpNum = [MI] (MachineOperand &Op) -> unsigned {
 193     for (unsigned i = 0, n = MI->getNumOperands(); i != n; ++i)
 194       if (&MI->getOperand(i) == &Op)
 195         return i;
 196     llvm_unreachable("Invalid operand");
 197   };
 198   DenseMap<NodeId,unsigned> OpMap;
 199   DataFlowGraph &DFG = getDFG();
 200   NodeList Refs = IA.Addr->members(DFG);
 201   for (NodeAddr<RefNode*> RA : Refs)
 202     OpMap.insert(std::make_pair(RA.Id, getOpNum(RA.Addr->getOp())));
 203
 204   MI->RemoveOperand(OpNum);
 205
 206   for (NodeAddr<RefNode*> RA : Refs) {
 207     unsigned N = OpMap[RA.Id];
 208     if (N < OpNum)
 209       RA.Addr->setRegRef(&MI->getOperand(N), DFG);
 210     else if (N > OpNum)
 211       RA.Addr->setRegRef(&MI->getOperand(N-1), DFG);
 212   }
 213 }
 214
 215 bool HexagonDCE::rewrite(NodeAddr<InstrNode*> IA, SetVector<NodeId> &Remove) {
 216   if (!getDFG().IsCode<NodeAttrs::Stmt>(IA))
 217     return false;
 218   DataFlowGraph &DFG = getDFG();
 219   MachineInstr &MI = *NodeAddr<StmtNode*>(IA).Addr->getCode();
 220   auto &HII = static_cast<const HexagonInstrInfo&>(DFG.getTII());
 221   if (HII.getAddrMode(MI) != HexagonII::PostInc)
 222     return false;
 223   unsigned Opc = MI.getOpcode();
 224   unsigned OpNum, NewOpc;
 225   switch (Opc) {
 226     case Hexagon::L2_loadri_pi:
 227       NewOpc = Hexagon::L2_loadri_io;
 228       OpNum = 1;
 229       break;
 230     case Hexagon::L2_loadrd_pi:
 231       NewOpc = Hexagon::L2_loadrd_io;
 232       OpNum = 1;
 233       break;
 234     case Hexagon::V6_vL32b_pi:
 235       NewOpc = Hexagon::V6_vL32b_ai;
 236       OpNum = 1;
 237       break;
 238     case Hexagon::S2_storeri_pi:
 239       NewOpc = Hexagon::S2_storeri_io;
 240       OpNum = 0;
 241       break;
 242     case Hexagon::S2_storerd_pi:
 243       NewOpc = Hexagon::S2_storerd_io;
 244       OpNum = 0;
 245       break;
 246     case Hexagon::V6_vS32b_pi:
 247       NewOpc = Hexagon::V6_vS32b_ai;
 248       OpNum = 0;
 249       break;
 250     default:
 251       return false;
 252   }
 253   auto IsDead = [this] (NodeAddr<DefNode*> DA) -> bool {
 254     return getDeadNodes().count(DA.Id);
 255   };
 256   NodeList Defs;
 257   MachineOperand &Op = MI.getOperand(OpNum);
 258   for (NodeAddr<DefNode*> DA : IA.Addr->members_if(DFG.IsDef, DFG)) {
 259     if (&DA.Addr->getOp() != &Op)
 260       continue;
 261     Defs = DFG.getRelatedRefs(IA, DA);
 262     if (!llvm::all_of(Defs, IsDead))
 263       return false;
 264     break;
 265   }
 266
 267   // Mark all nodes in Defs for removal.
 268   for (auto D : Defs)
 269     Remove.insert(D.Id);
 270
 271   if (trace())
 272     dbgs() << "Rewriting: " << MI;
 273   MI.setDesc(HII.get(NewOpc));
 274   MI.getOperand(OpNum+2).setImm(0);
 275   removeOperand(IA, OpNum);
 276   if (trace())
 277     dbgs() << "       to: " << MI;
 278
 279   return true;
 280 }
 281
 282 bool HexagonRDFOpt::runOnMachineFunction(MachineFunction &MF) {
 283   if (skipFunction(MF.getFunction()))
 284     return false;
 285
 286   if (RDFLimit.getPosition()) {
 287     if (RDFCount >= RDFLimit)
 288       return false;
 289     RDFCount++;
 290   }
 291
 292   MDT = &getAnalysis<MachineDominatorTree>();
 293   const auto &MDF = getAnalysis<MachineDominanceFrontier>();
 294   const auto &HII = *MF.getSubtarget<HexagonSubtarget>().getInstrInfo();
 295   const auto &HRI = *MF.getSubtarget<HexagonSubtarget>().getRegisterInfo();
 296   MRI = &MF.getRegInfo();
 297   bool Changed;
 298
 299   if (RDFDump)
 300     MF.print(dbgs() << "Before " << getPassName() << "\n", nullptr);
 301
 302   TargetOperandInfo TOI(HII);
 303   DataFlowGraph G(MF, HII, HRI, *MDT, MDF, TOI);
 304   // Dead phi nodes are necessary for copy propagation: we can add a use
 305   // of a register in a block where it would need a phi node, but which
 306   // was dead (and removed) during the graph build time.
 307   G.build(BuildOptions::KeepDeadPhis);
 308
 309   if (RDFDump)
 310     dbgs() << "Starting copy propagation on: " << MF.getName() << '\n'
 311            << PrintNode<FuncNode*>(G.getFunc(), G) << '\n';
 312   HexagonCP CP(G);
 313   CP.trace(RDFDump);
 314   Changed = CP.run();
 315
 316   if (RDFDump)
 317     dbgs() << "Starting dead code elimination on: " << MF.getName() << '\n'
 318            << PrintNode<FuncNode*>(G.getFunc(), G) << '\n';
 319   HexagonDCE DCE(G, *MRI);
 320   DCE.trace(RDFDump);
 321   Changed |= DCE.run();
 322
 323   if (Changed) {
 324     if (RDFDump)
 325       dbgs() << "Starting liveness recomputation on: " << MF.getName() << '\n';
 326     Liveness LV(*MRI, G);
 327     LV.trace(RDFDump);
 328     LV.computeLiveIns();
 329     LV.resetLiveIns();
 330     LV.resetKills();
 331   }
 332
 333   if (RDFDump)
 334     MF.print(dbgs() << "After " << getPassName() << "\n", nullptr);
 335
 336   return false;
 337 }
 338
 339 FunctionPass *llvm::createHexagonRDFOpt() {
 340   return new HexagonRDFOpt();
 341 }