[Hexagon] Implement RDF-based post-RA optimizations

- Handle simple cases of register copies (what current RDF CP allows).
- Hexagon-specific dead code elimination: handles dead address updates
  in post-increment instructions.

llvm-svn: 257504

5 files changed, 372 insertions, 2 deletions

diff --git a/llvm/lib/Target/Hexagon/CMakeLists.txt b/llvm/lib/Target/Hexagon/CMakeLists.txt
index 414aa6963b1..333ca6a757a 100644
--- a/llvm/lib/Target/Hexagon/CMakeLists.txt
+++ b/llvm/lib/Target/Hexagon/CMakeLists.txt
@@ -39,6 +39,8 @@ add_llvm_target(HexagonCodeGen
   HexagonNewValueJump.cpp
   HexagonOptimizeSZextends.cpp
   HexagonPeephole.cpp
+  HexagonRDF.cpp
+  HexagonRDFOpt.cpp
   HexagonRegisterInfo.cpp
   HexagonSelectionDAGInfo.cpp
   HexagonSplitConst32AndConst64.cpp
diff --git a/llvm/lib/Target/Hexagon/HexagonRDF.cpp b/llvm/lib/Target/Hexagon/HexagonRDF.cpp
new file mode 100644
index 00000000000..06719cddf4b
--- /dev/null
+++ b/llvm/lib/Target/Hexagon/HexagonRDF.cpp
@@ -0,0 +1,60 @@
+//===--- HexagonRDF.cpp ---------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "HexagonRDF.h"
+#include "HexagonInstrInfo.h"
+#include "HexagonRegisterInfo.h"
+
+#include "llvm/CodeGen/MachineInstr.h"
+
+using namespace llvm;
+using namespace rdf;
+
+bool HexagonRegisterAliasInfo::covers(RegisterRef RA, RegisterRef RB) const {
+  if (RA == RB)
+    return true;
+
+  if (TargetRegisterInfo::isVirtualRegister(RA.Reg) &&
+      TargetRegisterInfo::isVirtualRegister(RB.Reg)) {
+    // Hexagon-specific cases.
+    if (RA.Reg == RB.Reg) {
+      if (RA.Sub == 0)
+        return true;
+      if (RB.Sub == 0)
+        return false;
+    }
+  }
+
+  return RegisterAliasInfo::covers(RA, RB);
+}
+
+bool HexagonRegisterAliasInfo::covers(const RegisterSet &RRs, RegisterRef RR)
+      const {
+  if (RRs.count(RR))
+    return true;
+
+  if (!TargetRegisterInfo::isPhysicalRegister(RR.Reg)) {
+    assert(TargetRegisterInfo::isVirtualRegister(RR.Reg));
+    // Check if both covering subregisters are present.
+    bool HasLo = RRs.count({RR.Reg, Hexagon::subreg_loreg});
+    bool HasHi = RRs.count({RR.Reg, Hexagon::subreg_hireg});
+    if (HasLo && HasHi)
+      return true;
+  }
+
+  if (RR.Sub == 0) {
+    // Check if both covering subregisters are present.
+    unsigned Lo = TRI.getSubReg(RR.Reg, Hexagon::subreg_loreg);
+    unsigned Hi = TRI.getSubReg(RR.Reg, Hexagon::subreg_hireg);
+    if (RRs.count({Lo, 0}) && RRs.count({Hi, 0}))
+      return true;
+  }
+
+  return RegisterAliasInfo::covers(RRs, RR);
+}
diff --git a/llvm/lib/Target/Hexagon/HexagonRDF.h b/llvm/lib/Target/Hexagon/HexagonRDF.h
new file mode 100644
index 00000000000..00c1889e8eb
--- /dev/null
+++ b/llvm/lib/Target/Hexagon/HexagonRDF.h
@@ -0,0 +1,28 @@
+//===--- HexagonRDF.h -----------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef HEXAGON_RDF_H
+#define HEXAGON_RDF_H
+#include "RDFGraph.h"
+
+namespace llvm {
+  class TargetRegisterInfo;
+}
+
+namespace rdf {
+  struct HexagonRegisterAliasInfo : public RegisterAliasInfo {
+    HexagonRegisterAliasInfo(const TargetRegisterInfo &TRI)
+      : RegisterAliasInfo(TRI) {}
+    bool covers(RegisterRef RA, RegisterRef RR) const override;
+    bool covers(const RegisterSet &RRs, RegisterRef RR) const override;
+  };
+}
+
+#endif
+
diff --git a/llvm/lib/Target/Hexagon/HexagonRDFOpt.cpp b/llvm/lib/Target/Hexagon/HexagonRDFOpt.cpp
new file mode 100644
index 00000000000..e820b49e047
--- /dev/null
+++ b/llvm/lib/Target/Hexagon/HexagonRDFOpt.cpp
@@ -0,0 +1,272 @@
+//===--- HexagonRDFOpt.cpp ------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "HexagonInstrInfo.h"
+#include "HexagonRDF.h"
+#include "HexagonSubtarget.h"
+#include "RDFCopy.h"
+#include "RDFDeadCode.h"
+#include "RDFGraph.h"
+#include "RDFLiveness.h"
+#include "llvm/ADT/SetVector.h"
+#include "llvm/CodeGen/MachineBasicBlock.h"
+#include "llvm/CodeGen/MachineDominanceFrontier.h"
+#include "llvm/CodeGen/MachineDominators.h"
+#include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/CodeGen/MachineFunctionPass.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Format.h"
+#include "llvm/Target/TargetInstrInfo.h"
+#include "llvm/Target/TargetRegisterInfo.h"
+
+using namespace llvm;
+using namespace rdf;
+
+namespace llvm {
+  void initializeHexagonRDFOptPass(PassRegistry&);
+  FunctionPass *createHexagonRDFOpt();
+}
+
+namespace {
+  cl::opt<unsigned> RDFLimit("rdf-limit", cl::init(UINT_MAX));
+  unsigned RDFCount = 0;
+  cl::opt<bool> RDFDump("rdf-dump", cl::init(false));
+
+  class HexagonRDFOpt : public MachineFunctionPass {
+  public:
+    HexagonRDFOpt() : MachineFunctionPass(ID) {
+      initializeHexagonRDFOptPass(*PassRegistry::getPassRegistry());
+    }
+    void getAnalysisUsage(AnalysisUsage &AU) const override {
+      AU.addRequired<MachineDominatorTree>();
+      AU.addRequired<MachineDominanceFrontier>();
+      AU.setPreservesAll();
+      MachineFunctionPass::getAnalysisUsage(AU);
+    }
+    const char *getPassName() const override {
+      return "Hexagon RDF optimizations";
+    }
+    bool runOnMachineFunction(MachineFunction &MF) override;
+
+    static char ID;
+
+  private:
+    MachineDominatorTree *MDT;
+    MachineRegisterInfo *MRI;
+  };
+
+  char HexagonRDFOpt::ID = 0;
+}
+
+INITIALIZE_PASS_BEGIN(HexagonRDFOpt, "rdfopt", "Hexagon RDF opt", false, false)
+INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
+INITIALIZE_PASS_DEPENDENCY(MachineDominanceFrontier)
+INITIALIZE_PASS_END(HexagonRDFOpt, "rdfopt", "Hexagon RDF opt", false, false)
+
+
+struct HexagonDCE : public DeadCodeElimination {
+  using DeadCodeElimination::DeadCodeElimination;
+
+  bool rewrite(NodeAddr<InstrNode*> IA, SetVector<NodeId> &Remove);
+  void removeOperand(NodeAddr<InstrNode*> IA, unsigned OpNum);
+
+  bool run();
+};
+
+
+bool HexagonDCE::run() {
+  bool Collected = collect();
+  if (!Collected)
+    return false;
+
+  const SetVector<NodeId> &DeadNodes = getDeadNodes();
+  const SetVector<NodeId> &DeadInstrs = getDeadInstrs();
+
+  typedef DenseMap<NodeId,NodeId> RefToInstrMap;
+  RefToInstrMap R2I;
+  SetVector<NodeId> PartlyDead;
+  DataFlowGraph &DFG = getDFG();
+
+  for (NodeAddr<BlockNode*> BA : DFG.getFunc().Addr->members(DFG)) {
+    for (auto TA : BA.Addr->members_if(DFG.IsCode<NodeAttrs::Stmt>, DFG)) {
+      NodeAddr<StmtNode*> SA = TA;
+      for (NodeAddr<RefNode*> RA : SA.Addr->members(DFG)) {
+        R2I.insert(std::make_pair(RA.Id, SA.Id));
+        if (DFG.IsDef(RA) && DeadNodes.count(RA.Id))
+          if (!DeadInstrs.count(SA.Id))
+            PartlyDead.insert(SA.Id);
+      }
+    }
+  }
+
+  // Nodes to remove.
+  SetVector<NodeId> Remove = DeadInstrs;
+
+  bool Changed = false;
+  for (NodeId N : PartlyDead) {
+    auto SA = DFG.addr<StmtNode*>(N);
+    if (trace())
+      dbgs() << "Partly dead: " << *SA.Addr->getCode();
+    Changed |= rewrite(SA, Remove);
+  }
+
+  return erase(Remove) || Changed;
+}
+
+
+void HexagonDCE::removeOperand(NodeAddr<InstrNode*> IA, unsigned OpNum) {
+  MachineInstr *MI = NodeAddr<StmtNode*>(IA).Addr->getCode();
+
+  auto getOpNum = [MI] (MachineOperand &Op) -> unsigned {
+    for (unsigned i = 0, n = MI->getNumOperands(); i != n; ++i)
+      if (&MI->getOperand(i) == &Op)
+        return i;
+    llvm_unreachable("Invalid operand");
+  };
+  DenseMap<NodeId,unsigned> OpMap;
+  NodeList Refs = IA.Addr->members(getDFG());
+  for (NodeAddr<RefNode*> RA : Refs)
+    OpMap.insert(std::make_pair(RA.Id, getOpNum(RA.Addr->getOp())));
+
+  MI->RemoveOperand(OpNum);
+
+  for (NodeAddr<RefNode*> RA : Refs) {
+    unsigned N = OpMap[RA.Id];
+    if (N < OpNum)
+      RA.Addr->setRegRef(&MI->getOperand(N));
+    else if (N > OpNum)
+      RA.Addr->setRegRef(&MI->getOperand(N-1));
+  }
+}
+
+
+bool HexagonDCE::rewrite(NodeAddr<InstrNode*> IA, SetVector<NodeId> &Remove) {
+  if (!getDFG().IsCode<NodeAttrs::Stmt>(IA))
+    return false;
+  DataFlowGraph &DFG = getDFG();
+  MachineInstr *MI = NodeAddr<StmtNode*>(IA).Addr->getCode();
+  auto &HII = static_cast<const HexagonInstrInfo&>(DFG.getTII());
+  if (HII.getAddrMode(MI) != HexagonII::PostInc)
+    return false;
+  unsigned Opc = MI->getOpcode();
+  unsigned OpNum, NewOpc;
+  switch (Opc) {
+    case Hexagon::L2_loadri_pi:
+      NewOpc = Hexagon::L2_loadri_io;
+      OpNum = 1;
+      break;
+    case Hexagon::L2_loadrd_pi:
+      NewOpc = Hexagon::L2_loadrd_io;
+      OpNum = 1;
+      break;
+    case Hexagon::V6_vL32b_pi:
+      NewOpc = Hexagon::V6_vL32b_ai;
+      OpNum = 1;
+      break;
+    case Hexagon::S2_storeri_pi:
+      NewOpc = Hexagon::S2_storeri_io;
+      OpNum = 0;
+      break;
+    case Hexagon::S2_storerd_pi:
+      NewOpc = Hexagon::S2_storerd_io;
+      OpNum = 0;
+      break;
+    case Hexagon::V6_vS32b_pi:
+      NewOpc = Hexagon::V6_vS32b_ai;
+      OpNum = 0;
+      break;
+    default:
+      return false;
+  }
+  auto IsDead = [this] (NodeAddr<DefNode*> DA) -> bool {
+    return getDeadNodes().count(DA.Id);
+  };
+  NodeList Defs;
+  MachineOperand &Op = MI->getOperand(OpNum);
+  for (NodeAddr<DefNode*> DA : IA.Addr->members_if(DFG.IsDef, DFG)) {
+    if (&DA.Addr->getOp() != &Op)
+      continue;
+    Defs = DFG.getRelatedRefs(IA, DA);
+    if (!std::all_of(Defs.begin(), Defs.end(), IsDead))
+      return false;
+    break;
+  }
+
+  // Mark all nodes in Defs for removal.
+  for (auto D : Defs)
+    Remove.insert(D.Id);
+
+  if (trace())
+    dbgs() << "Rewriting: " << *MI;
+  MI->setDesc(HII.get(NewOpc));
+  MI->getOperand(OpNum+2).setImm(0);
+  removeOperand(IA, OpNum);
+  if (trace())
+    dbgs() << "       to: " << *MI;
+
+  return true;
+}
+
+
+bool HexagonRDFOpt::runOnMachineFunction(MachineFunction &MF) {
+  if (RDFLimit.getPosition()) {
+    if (RDFCount >= RDFLimit)
+      return false;
+    RDFCount++;
+  }
+
+  MDT = &getAnalysis<MachineDominatorTree>();
+  const auto &MDF = getAnalysis<MachineDominanceFrontier>();
+  const auto &HII = *MF.getSubtarget<HexagonSubtarget>().getInstrInfo();
+  const auto &HRI = *MF.getSubtarget<HexagonSubtarget>().getRegisterInfo();
+  MRI = &MF.getRegInfo();
+
+  HexagonRegisterAliasInfo HAI(HRI);
+  TargetOperandInfo TOI(HII);
+
+  if (RDFDump)
+    MF.print(dbgs() << "Before " << getPassName() << "\n", nullptr);
+  DataFlowGraph G(MF, HII, HRI, *MDT, MDF, HAI, TOI);
+  G.build();
+  if (RDFDump) {
+    dbgs() << PrintNode<FuncNode*>(G.getFunc(), G) << '\n';
+    dbgs() << MF.getName() << '\n';
+  }
+
+  bool Changed;
+  CopyPropagation CP(G);
+  CP.trace(RDFDump);
+  Changed = CP.run();
+  if (Changed)
+    G.build();
+
+  HexagonDCE DCE(G, *MRI);
+  DCE.trace(RDFDump);
+  Changed |= DCE.run();
+
+  if (Changed) {
+    Liveness LV(*MRI, G);
+    LV.trace(RDFDump);
+    LV.computeLiveIns();
+    LV.resetLiveIns();
+    LV.resetKills();
+  }
+
+  if (RDFDump)
+    MF.print(dbgs() << "After " << getPassName() << "\n", nullptr);
+  return false;
+}
+
+
+FunctionPass *llvm::createHexagonRDFOpt() {
+  return new HexagonRDFOpt();
+}
+
+
diff --git a/llvm/lib/Target/Hexagon/HexagonTargetMachine.cpp b/llvm/lib/Target/Hexagon/HexagonTargetMachine.cpp
index 9dccd696c98..34b03fb74ce 100644
--- a/llvm/lib/Target/Hexagon/HexagonTargetMachine.cpp
+++ b/llvm/lib/Target/Hexagon/HexagonTargetMachine.cpp
@@ -26,7 +26,11 @@
 
 using namespace llvm;
 
-static cl:: opt<bool> DisableHardwareLoops("disable-hexagon-hwloops",
+
+static cl::opt<bool> EnableRDFOpt("rdf-opt", cl::Hidden, cl::ZeroOrMore,
+  cl::init(true), cl::desc("Enable RDF-based optimizations"));
+
+static cl::opt<bool> DisableHardwareLoops("disable-hexagon-hwloops",
   cl::Hidden, cl::desc("Disable Hardware Loops for Hexagon target"));
 
 static cl::opt<bool> DisableHexagonCFGOpt("disable-hexagon-cfgopt",
@@ -111,6 +115,7 @@ namespace llvm {
   FunctionPass *createHexagonOptimizeSZextends();
   FunctionPass *createHexagonPacketizer();
   FunctionPass *createHexagonPeephole();
+  FunctionPass *createHexagonRDFOpt();
   FunctionPass *createHexagonSplitConst32AndConst64();
   FunctionPass *createHexagonSplitDoubleRegs();
   FunctionPass *createHexagonStoreWidening();
@@ -262,9 +267,12 @@ void HexagonPassConfig::addPreRegAlloc() {
 }
 
 void HexagonPassConfig::addPostRegAlloc() {
-  if (getOptLevel() != CodeGenOpt::None)
+  if (getOptLevel() != CodeGenOpt::None) {
+    if (EnableRDFOpt)
+      addPass(createHexagonRDFOpt());
     if (!DisableHexagonCFGOpt)
       addPass(createHexagonCFGOptimizer(), false);
+  }
 }
 
 void HexagonPassConfig::addPreSched2() {