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