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 "HexagonRDF.h"
  12 #include "HexagonSubtarget.h"
  13 #include "RDFCopy.h"
  14 #include "RDFDeadCode.h"
  15 #include "RDFGraph.h"
  16 #include "RDFLiveness.h"
  17 #include "llvm/ADT/SetVector.h"
  18 #include "llvm/CodeGen/MachineBasicBlock.h"
  19 #include "llvm/CodeGen/MachineDominanceFrontier.h"
  20 #include "llvm/CodeGen/MachineDominators.h"
  21 #include "llvm/CodeGen/MachineFunction.h"
  22 #include "llvm/CodeGen/MachineFunctionPass.h"
  23 #include "llvm/CodeGen/MachineRegisterInfo.h"
  24 #include "llvm/Support/CommandLine.h"
  25 #include "llvm/Support/Format.h"
  26 #include "llvm/Target/TargetInstrInfo.h"
  27 #include "llvm/Target/TargetRegisterInfo.h"
  28
  29 using namespace llvm;
  30 using namespace rdf;
  31
  32 namespace llvm {
  33   void initializeHexagonRDFOptPass(PassRegistry&);
  34   FunctionPass *createHexagonRDFOpt();
  35 }
  36
  37 namespace {
  38   cl::opt<unsigned> RDFLimit("rdf-limit", cl::init(UINT_MAX));
  39   unsigned RDFCount = 0;
  40   cl::opt<bool> RDFDump("rdf-dump", cl::init(false));
  41
  42   class HexagonRDFOpt : public MachineFunctionPass {
  43   public:
  44     HexagonRDFOpt() : MachineFunctionPass(ID) {
  45       initializeHexagonRDFOptPass(*PassRegistry::getPassRegistry());
  46     }
  47     void getAnalysisUsage(AnalysisUsage &AU) const override {
  48       AU.addRequired<MachineDominatorTree>();
  49       AU.addRequired<MachineDominanceFrontier>();
  50       AU.setPreservesAll();
  51       MachineFunctionPass::getAnalysisUsage(AU);
  52     }
  53     const char *getPassName() const override {
  54       return "Hexagon RDF optimizations";
  55     }
  56     bool runOnMachineFunction(MachineFunction &MF) override;
  57
  58     static char ID;
  59
  60   private:
  61     MachineDominatorTree *MDT;
  62     MachineRegisterInfo *MRI;
  63   };
  64
  65   char HexagonRDFOpt::ID = 0;
  66 }
  67
  68 INITIALIZE_PASS_BEGIN(HexagonRDFOpt, "rdfopt", "Hexagon RDF opt", false, false)
  69 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
  70 INITIALIZE_PASS_DEPENDENCY(MachineDominanceFrontier)
  71 INITIALIZE_PASS_END(HexagonRDFOpt, "rdfopt", "Hexagon RDF opt", false, false)
  72
  73
  74 struct HexagonDCE : public DeadCodeElimination {
  75   using DeadCodeElimination::DeadCodeElimination;
  76
  77   bool rewrite(NodeAddr<InstrNode*> IA, SetVector<NodeId> &Remove);
  78   void removeOperand(NodeAddr<InstrNode*> IA, unsigned OpNum);
  79
  80   bool run();
  81 };
  82
  83
  84 bool HexagonDCE::run() {
  85   bool Collected = collect();
  86   if (!Collected)
  87     return false;
  88
  89   const SetVector<NodeId> &DeadNodes = getDeadNodes();
  90   const SetVector<NodeId> &DeadInstrs = getDeadInstrs();
  91
  92   typedef DenseMap<NodeId,NodeId> RefToInstrMap;
  93   RefToInstrMap R2I;
  94   SetVector<NodeId> PartlyDead;
  95   DataFlowGraph &DFG = getDFG();
  96
  97   for (NodeAddr<BlockNode*> BA : DFG.getFunc().Addr->members(DFG)) {
  98     for (auto TA : BA.Addr->members_if(DFG.IsCode<NodeAttrs::Stmt>, DFG)) {
  99       NodeAddr<StmtNode*> SA = TA;
 100       for (NodeAddr<RefNode*> RA : SA.Addr->members(DFG)) {
 101         R2I.insert(std::make_pair(RA.Id, SA.Id));
 102         if (DFG.IsDef(RA) && DeadNodes.count(RA.Id))
 103           if (!DeadInstrs.count(SA.Id))
 104             PartlyDead.insert(SA.Id);
 105       }
 106     }
 107   }
 108
 109   // Nodes to remove.
 110   SetVector<NodeId> Remove = DeadInstrs;
 111
 112   bool Changed = false;
 113   for (NodeId N : PartlyDead) {
 114     auto SA = DFG.addr<StmtNode*>(N);
 115     if (trace())
 116       dbgs() << "Partly dead: " << *SA.Addr->getCode();
 117     Changed |= rewrite(SA, Remove);
 118   }
 119
 120   return erase(Remove) || Changed;
 121 }
 122
 123
 124 void HexagonDCE::removeOperand(NodeAddr<InstrNode*> IA, unsigned OpNum) {
 125   MachineInstr *MI = NodeAddr<StmtNode*>(IA).Addr->getCode();
 126
 127   auto getOpNum = [MI] (MachineOperand &Op) -> unsigned {
 128     for (unsigned i = 0, n = MI->getNumOperands(); i != n; ++i)
 129       if (&MI->getOperand(i) == &Op)
 130         return i;
 131     llvm_unreachable("Invalid operand");
 132   };
 133   DenseMap<NodeId,unsigned> OpMap;
 134   NodeList Refs = IA.Addr->members(getDFG());
 135   for (NodeAddr<RefNode*> RA : Refs)
 136     OpMap.insert(std::make_pair(RA.Id, getOpNum(RA.Addr->getOp())));
 137
 138   MI->RemoveOperand(OpNum);
 139
 140   for (NodeAddr<RefNode*> RA : Refs) {
 141     unsigned N = OpMap[RA.Id];
 142     if (N < OpNum)
 143       RA.Addr->setRegRef(&MI->getOperand(N));
 144     else if (N > OpNum)
 145       RA.Addr->setRegRef(&MI->getOperand(N-1));
 146   }
 147 }
 148
 149
 150 bool HexagonDCE::rewrite(NodeAddr<InstrNode*> IA, SetVector<NodeId> &Remove) {
 151   if (!getDFG().IsCode<NodeAttrs::Stmt>(IA))
 152     return false;
 153   DataFlowGraph &DFG = getDFG();
 154   MachineInstr *MI = NodeAddr<StmtNode*>(IA).Addr->getCode();
 155   auto &HII = static_cast<const HexagonInstrInfo&>(DFG.getTII());
 156   if (HII.getAddrMode(MI) != HexagonII::PostInc)
 157     return false;
 158   unsigned Opc = MI->getOpcode();
 159   unsigned OpNum, NewOpc;
 160   switch (Opc) {
 161     case Hexagon::L2_loadri_pi:
 162       NewOpc = Hexagon::L2_loadri_io;
 163       OpNum = 1;
 164       break;
 165     case Hexagon::L2_loadrd_pi:
 166       NewOpc = Hexagon::L2_loadrd_io;
 167       OpNum = 1;
 168       break;
 169     case Hexagon::V6_vL32b_pi:
 170       NewOpc = Hexagon::V6_vL32b_ai;
 171       OpNum = 1;
 172       break;
 173     case Hexagon::S2_storeri_pi:
 174       NewOpc = Hexagon::S2_storeri_io;
 175       OpNum = 0;
 176       break;
 177     case Hexagon::S2_storerd_pi:
 178       NewOpc = Hexagon::S2_storerd_io;
 179       OpNum = 0;
 180       break;
 181     case Hexagon::V6_vS32b_pi:
 182       NewOpc = Hexagon::V6_vS32b_ai;
 183       OpNum = 0;
 184       break;
 185     default:
 186       return false;
 187   }
 188   auto IsDead = [this] (NodeAddr<DefNode*> DA) -> bool {
 189     return getDeadNodes().count(DA.Id);
 190   };
 191   NodeList Defs;
 192   MachineOperand &Op = MI->getOperand(OpNum);
 193   for (NodeAddr<DefNode*> DA : IA.Addr->members_if(DFG.IsDef, DFG)) {
 194     if (&DA.Addr->getOp() != &Op)
 195       continue;
 196     Defs = DFG.getRelatedRefs(IA, DA);
 197     if (!std::all_of(Defs.begin(), Defs.end(), IsDead))
 198       return false;
 199     break;
 200   }
 201
 202   // Mark all nodes in Defs for removal.
 203   for (auto D : Defs)
 204     Remove.insert(D.Id);
 205
 206   if (trace())
 207     dbgs() << "Rewriting: " << *MI;
 208   MI->setDesc(HII.get(NewOpc));
 209   MI->getOperand(OpNum+2).setImm(0);
 210   removeOperand(IA, OpNum);
 211   if (trace())
 212     dbgs() << "       to: " << *MI;
 213
 214   return true;
 215 }
 216
 217
 218 bool HexagonRDFOpt::runOnMachineFunction(MachineFunction &MF) {
 219   if (RDFLimit.getPosition()) {
 220     if (RDFCount >= RDFLimit)
 221       return false;
 222     RDFCount++;
 223   }
 224
 225   MDT = &getAnalysis<MachineDominatorTree>();
 226   const auto &MDF = getAnalysis<MachineDominanceFrontier>();
 227   const auto &HII = *MF.getSubtarget<HexagonSubtarget>().getInstrInfo();
 228   const auto &HRI = *MF.getSubtarget<HexagonSubtarget>().getRegisterInfo();
 229   MRI = &MF.getRegInfo();
 230
 231   HexagonRegisterAliasInfo HAI(HRI);
 232   TargetOperandInfo TOI(HII);
 233
 234   if (RDFDump)
 235     MF.print(dbgs() << "Before " << getPassName() << "\n", nullptr);
 236   DataFlowGraph G(MF, HII, HRI, *MDT, MDF, HAI, TOI);
 237   G.build();
 238   if (RDFDump) {
 239     dbgs() << PrintNode<FuncNode*>(G.getFunc(), G) << '\n';
 240     dbgs() << MF.getName() << '\n';
 241   }
 242
 243   bool Changed;
 244   CopyPropagation CP(G);
 245   CP.trace(RDFDump);
 246   Changed = CP.run();
 247   if (Changed)
 248     G.build();
 249
 250   HexagonDCE DCE(G, *MRI);
 251   DCE.trace(RDFDump);
 252   Changed |= DCE.run();
 253
 254   if (Changed) {
 255     Liveness LV(*MRI, G);
 256     LV.trace(RDFDump);
 257     LV.computeLiveIns();
 258     LV.resetLiveIns();
 259     LV.resetKills();
 260   }
 261
 262   if (RDFDump)
 263     MF.print(dbgs() << "After " << getPassName() << "\n", nullptr);
 264   return false;
 265 }
 266
 267
 268 FunctionPass *llvm::createHexagonRDFOpt() {
 269   return new HexagonRDFOpt();
 270 }
 271
 272