contrib/llvm/lib/Target/Hexagon/HexagonRDFOpt.cpp

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