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