Home | History | Annotate | Download | only in Hexagon 
      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   unsigned RDFCount = 0;
     39   cl::opt<unsigned> RDFLimit("rdf-limit", cl::init(UINT_MAX));
     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     MachineFunctionProperties getRequiredProperties() const override {
     59       return MachineFunctionProperties().set(
     60           MachineFunctionProperties::Property::AllVRegsAllocated);
     61     }
     62 
     63     static char ID;
     64 
     65   private:
     66     MachineDominatorTree *MDT;
     67     MachineRegisterInfo *MRI;
     68   };
     69 
     70   char HexagonRDFOpt::ID = 0;
     71 }
     72 
     73 INITIALIZE_PASS_BEGIN(HexagonRDFOpt, "rdfopt", "Hexagon RDF opt", false, false)
     74 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
     75 INITIALIZE_PASS_DEPENDENCY(MachineDominanceFrontier)
     76 INITIALIZE_PASS_END(HexagonRDFOpt, "rdfopt", "Hexagon RDF opt", false, false)
     77 
     78 
     79 namespace {
     80 struct HexagonCP : public CopyPropagation {
     81   HexagonCP(DataFlowGraph &G) : CopyPropagation(G) {}
     82   bool interpretAsCopy(const MachineInstr *MI, EqualityMap &EM) override;
     83 };
     84 
     85 
     86 struct HexagonDCE : public DeadCodeElimination {
     87   HexagonDCE(DataFlowGraph &G, MachineRegisterInfo &MRI)
     88     : DeadCodeElimination(G, MRI) {}
     89   bool rewrite(NodeAddr<InstrNode*> IA, SetVector<NodeId> &Remove);
     90   void removeOperand(NodeAddr<InstrNode*> IA, unsigned OpNum);
     91 
     92   bool run();
     93 };
     94 } // end anonymous namespace
     95 
     96 
     97 bool HexagonCP::interpretAsCopy(const MachineInstr *MI, EqualityMap &EM) {
     98   auto mapRegs = [MI,&EM] (RegisterRef DstR, RegisterRef SrcR) -> void {
     99     EM.insert(std::make_pair(DstR, SrcR));
    100   };
    101 
    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({ DstOp.getReg(), Hexagon::subreg_hireg },
    110               { HiOp.getReg(), HiOp.getSubReg() });
    111       mapRegs({ DstOp.getReg(), Hexagon::subreg_loreg },
    112               { 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     }
    120     // Fall through.
    121     case Hexagon::A2_tfr: {
    122       const MachineOperand &DstOp = MI->getOperand(0);
    123       const MachineOperand &SrcOp = MI->getOperand(1);
    124       mapRegs({ DstOp.getReg(), DstOp.getSubReg() },
    125               { 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   NodeList Refs = IA.Addr->members(getDFG());
    186   for (NodeAddr<RefNode*> RA : Refs)
    187     OpMap.insert(std::make_pair(RA.Id, getOpNum(RA.Addr->getOp())));
    188 
    189   MI->RemoveOperand(OpNum);
    190 
    191   for (NodeAddr<RefNode*> RA : Refs) {
    192     unsigned N = OpMap[RA.Id];
    193     if (N < OpNum)
    194       RA.Addr->setRegRef(&MI->getOperand(N));
    195     else if (N > OpNum)
    196       RA.Addr->setRegRef(&MI->getOperand(N-1));
    197   }
    198 }
    199 
    200 
    201 bool HexagonDCE::rewrite(NodeAddr<InstrNode*> IA, SetVector<NodeId> &Remove) {
    202   if (!getDFG().IsCode<NodeAttrs::Stmt>(IA))
    203     return false;
    204   DataFlowGraph &DFG = getDFG();
    205   MachineInstr *MI = NodeAddr<StmtNode*>(IA).Addr->getCode();
    206   auto &HII = static_cast<const HexagonInstrInfo&>(DFG.getTII());
    207   if (HII.getAddrMode(MI) != HexagonII::PostInc)
    208     return false;
    209   unsigned Opc = MI->getOpcode();
    210   unsigned OpNum, NewOpc;
    211   switch (Opc) {
    212     case Hexagon::L2_loadri_pi:
    213       NewOpc = Hexagon::L2_loadri_io;
    214       OpNum = 1;
    215       break;
    216     case Hexagon::L2_loadrd_pi:
    217       NewOpc = Hexagon::L2_loadrd_io;
    218       OpNum = 1;
    219       break;
    220     case Hexagon::V6_vL32b_pi:
    221       NewOpc = Hexagon::V6_vL32b_ai;
    222       OpNum = 1;
    223       break;
    224     case Hexagon::S2_storeri_pi:
    225       NewOpc = Hexagon::S2_storeri_io;
    226       OpNum = 0;
    227       break;
    228     case Hexagon::S2_storerd_pi:
    229       NewOpc = Hexagon::S2_storerd_io;
    230       OpNum = 0;
    231       break;
    232     case Hexagon::V6_vS32b_pi:
    233       NewOpc = Hexagon::V6_vS32b_ai;
    234       OpNum = 0;
    235       break;
    236     default:
    237       return false;
    238   }
    239   auto IsDead = [this] (NodeAddr<DefNode*> DA) -> bool {
    240     return getDeadNodes().count(DA.Id);
    241   };
    242   NodeList Defs;
    243   MachineOperand &Op = MI->getOperand(OpNum);
    244   for (NodeAddr<DefNode*> DA : IA.Addr->members_if(DFG.IsDef, DFG)) {
    245     if (&DA.Addr->getOp() != &Op)
    246       continue;
    247     Defs = DFG.getRelatedRefs(IA, DA);
    248     if (!std::all_of(Defs.begin(), Defs.end(), IsDead))
    249       return false;
    250     break;
    251   }
    252 
    253   // Mark all nodes in Defs for removal.
    254   for (auto D : Defs)
    255     Remove.insert(D.Id);
    256 
    257   if (trace())
    258     dbgs() << "Rewriting: " << *MI;
    259   MI->setDesc(HII.get(NewOpc));
    260   MI->getOperand(OpNum+2).setImm(0);
    261   removeOperand(IA, OpNum);
    262   if (trace())
    263     dbgs() << "       to: " << *MI;
    264 
    265   return true;
    266 }
    267 
    268 
    269 bool HexagonRDFOpt::runOnMachineFunction(MachineFunction &MF) {
    270   if (skipFunction(*MF.getFunction()))
    271     return false;
    272 
    273   if (RDFLimit.getPosition()) {
    274     if (RDFCount >= RDFLimit)
    275       return false;
    276     RDFCount++;
    277   }
    278 
    279   MDT = &getAnalysis<MachineDominatorTree>();
    280   const auto &MDF = getAnalysis<MachineDominanceFrontier>();
    281   const auto &HII = *MF.getSubtarget<HexagonSubtarget>().getInstrInfo();
    282   const auto &HRI = *MF.getSubtarget<HexagonSubtarget>().getRegisterInfo();
    283   MRI = &MF.getRegInfo();
    284   bool Changed;
    285 
    286   if (RDFDump)
    287     MF.print(dbgs() << "Before " << getPassName() << "\n", nullptr);
    288 
    289   HexagonRegisterAliasInfo HAI(HRI);
    290   TargetOperandInfo TOI(HII);
    291   DataFlowGraph G(MF, HII, HRI, *MDT, MDF, HAI, 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 }
    331