RDF: Copy propagation

This is a very limited implementation of DFG-based copy propagation.
It only handles actual COPY instructions (does not handle other equivalents
such as add-immediate with a 0 operand).
The major limitation is that it does not update the DFG: that will be the
change required to make it more robust (hopefully coming up soon).

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@257490 91177308-0d34-0410-b5e6-96231b3b80d8

diff --git a/lib/Target/Hexagon/CMakeLists.txt b/lib/Target/Hexagon/CMakeLists.txt
index a9be39880fcc5ba4806b6ef4529dbebe1cc369ed..414aa6963b136f597ee7ddff2e6e9b5a6f5646a2 100644 (file)
--- a/lib/Target/Hexagon/CMakeLists.txt
+++ b/lib/Target/Hexagon/CMakeLists.txt
@@ -49,6 +49,7 @@ add_llvm_target(HexagonCodeGen
   HexagonTargetObjectFile.cpp
   HexagonTargetTransformInfo.cpp
   HexagonVLIWPacketizer.cpp
+  RDFCopy.cpp
   RDFDeadCode.cpp
   RDFGraph.cpp
   RDFLiveness.cpp

diff --git a/lib/Target/Hexagon/RDFCopy.cpp b/lib/Target/Hexagon/RDFCopy.cpp
new file mode 100644 (file)
index 0000000..c547c71
--- /dev/null
+++ b/lib/Target/Hexagon/RDFCopy.cpp
@@ -0,0 +1,180 @@
+//===--- RDFCopy.cpp ------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Simplistic RDF-based copy propagation.
+
+#include "RDFCopy.h"
+#include "RDFGraph.h"
+#include "llvm/CodeGen/MachineBasicBlock.h"
+#include "llvm/CodeGen/MachineDominators.h"
+#include "llvm/CodeGen/MachineInstr.h"
+#include "llvm/Support/CommandLine.h"
+
+#include <atomic>
+
+#ifndef NDEBUG
+static cl::opt<unsigned> CpLimit("rdf-cp-limit", cl::init(0), cl::Hidden);
+static unsigned CpCount = 0;
+#endif
+
+using namespace llvm;
+using namespace rdf;
+
+void CopyPropagation::recordCopy(NodeAddr<StmtNode*> SA, MachineInstr *MI) {
+  assert(MI->getOpcode() == TargetOpcode::COPY);
+  const MachineOperand &Op0 = MI->getOperand(0), &Op1 = MI->getOperand(1);
+  RegisterRef DstR = { Op0.getReg(), Op0.getSubReg() };
+  RegisterRef SrcR = { Op1.getReg(), Op1.getSubReg() };
+  auto FS = DefM.find(SrcR);
+  if (FS == DefM.end() || FS->second.empty())
+    return;
+  Copies.push_back(SA.Id);
+  RDefMap[SrcR][SA.Id] = FS->second.top()->Id;
+  // Insert DstR into the map.
+  RDefMap[DstR];
+}
+
+
+void CopyPropagation::updateMap(NodeAddr<InstrNode*> IA) {
+  RegisterSet RRs;
+  for (NodeAddr<RefNode*> RA : IA.Addr->members(DFG))
+    RRs.insert(RA.Addr->getRegRef());
+  bool Common = false;
+  for (auto &R : RDefMap) {
+    if (!RRs.count(R.first))
+      continue;
+    Common = true;
+    break;
+  }
+  if (!Common)
+    return;
+
+  for (auto &R : RDefMap) {
+    if (!RRs.count(R.first))
+      continue;
+    auto F = DefM.find(R.first);
+    if (F == DefM.end() || F->second.empty())
+      continue;
+    R.second[IA.Id] = F->second.top()->Id;
+  }
+}
+
+
+bool CopyPropagation::scanBlock(MachineBasicBlock *B) {
+  bool Changed = false;
+  auto BA = DFG.getFunc().Addr->findBlock(B, DFG);
+  DFG.markBlock(BA.Id, DefM);
+
+  for (NodeAddr<InstrNode*> IA : BA.Addr->members(DFG)) {
+    if (DFG.IsCode<NodeAttrs::Stmt>(IA)) {
+      NodeAddr<StmtNode*> SA = IA;
+      MachineInstr *MI = SA.Addr->getCode();
+      if (MI->isCopy())
+        recordCopy(SA, MI);
+    }
+
+    updateMap(IA);
+    DFG.pushDefs(IA, DefM);
+  }
+
+  MachineDomTreeNode *N = MDT.getNode(B);
+  for (auto I : *N)
+    Changed |= scanBlock(I->getBlock());
+
+  DFG.releaseBlock(BA.Id, DefM);
+  return Changed;
+}
+
+
+bool CopyPropagation::run() {
+  scanBlock(&DFG.getMF().front());
+
+  if (trace()) {
+    dbgs() << "Copies:\n";
+    for (auto I : Copies)
+      dbgs() << *DFG.addr<StmtNode*>(I).Addr->getCode();
+    dbgs() << "\nRDef map:\n";
+    for (auto R : RDefMap) {
+      dbgs() << Print<RegisterRef>(R.first, DFG) << " -> {";
+      for (auto &M : R.second)
+        dbgs() << ' ' << Print<NodeId>(M.first, DFG) << ':'
+               << Print<NodeId>(M.second, DFG);
+      dbgs() << " }\n";
+    }
+  }
+
+  bool Changed = false;
+  NodeSet Deleted;
+#ifndef NDEBUG
+  bool HasLimit = CpLimit.getNumOccurrences() > 0;
+#endif
+
+  for (auto I : Copies) {
+#ifndef NDEBUG
+    if (HasLimit && CpCount >= CpLimit)
+      break;
+#endif
+    if (Deleted.count(I))
+      continue;
+    auto SA = DFG.addr<InstrNode*>(I);
+    NodeList Ds = SA.Addr->members_if(DFG.IsDef, DFG);
+    if (Ds.size() != 1)
+      continue;
+    NodeAddr<DefNode*> DA = Ds[0];
+    RegisterRef DR0 = DA.Addr->getRegRef();
+    NodeList Us = SA.Addr->members_if(DFG.IsUse, DFG);
+    if (Us.size() != 1)
+      continue;
+    NodeAddr<UseNode*> UA0 = Us[0];
+    RegisterRef UR0 = UA0.Addr->getRegRef();
+    NodeId RD0 = UA0.Addr->getReachingDef();
+
+    for (NodeId N = DA.Addr->getReachedUse(), NextN; N; N = NextN) {
+      auto UA = DFG.addr<UseNode*>(N);
+      NextN = UA.Addr->getSibling();
+      uint16_t F = UA.Addr->getFlags();
+      if ((F & NodeAttrs::PhiRef) || (F & NodeAttrs::Fixed))
+        continue;
+      if (UA.Addr->getRegRef() != DR0)
+        continue;
+      NodeAddr<InstrNode*> IA = UA.Addr->getOwner(DFG);
+      assert(DFG.IsCode<NodeAttrs::Stmt>(IA));
+      MachineInstr *MI = NodeAddr<StmtNode*>(IA).Addr->getCode();
+      if (RDefMap[UR0][IA.Id] != RD0)
+        continue;
+      MachineOperand &Op = UA.Addr->getOp();
+      if (Op.isTied())
+        continue;
+      if (trace()) {
+        dbgs() << "can replace " << Print<RegisterRef>(DR0, DFG)
+               << " with " << Print<RegisterRef>(UR0, DFG) << " in "
+               << *NodeAddr<StmtNode*>(IA).Addr->getCode();
+      }
+
+      Op.setReg(UR0.Reg);
+      Op.setSubReg(UR0.Sub);
+      Changed = true;
+#ifndef NDEBUG
+      if (HasLimit && CpCount >= CpLimit)
+        break;
+      CpCount++;
+#endif
+
+      if (MI->isCopy()) {
+        MachineOperand &Op0 = MI->getOperand(0), &Op1 = MI->getOperand(1);
+        if (Op0.getReg() == Op1.getReg() && Op0.getSubReg() == Op1.getSubReg())
+          MI->eraseFromParent();
+        Deleted.insert(IA.Id);
+      }
+    }
+  }
+
+  return Changed;
+}
+

diff --git a/lib/Target/Hexagon/RDFCopy.h b/lib/Target/Hexagon/RDFCopy.h
new file mode 100644 (file)
index 0000000..02531b9
--- /dev/null
+++ b/lib/Target/Hexagon/RDFCopy.h
@@ -0,0 +1,48 @@
+//===--- RDFCopy.h --------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef RDF_COPY_H
+#define RDF_COPY_H
+
+#include "RDFGraph.h"
+#include <map>
+#include <vector>
+
+namespace llvm {
+  class MachineBasicBlock;
+  class MachineDominatorTree;
+  class MachineInstr;
+}
+
+namespace rdf {
+  struct CopyPropagation {
+    CopyPropagation(DataFlowGraph &dfg) : MDT(dfg.getDT()), DFG(dfg),
+        Trace(false) {}
+
+    bool run();
+    void trace(bool On) { Trace = On; }
+    bool trace() const { return Trace; }
+
+  private:
+    const MachineDominatorTree &MDT;
+    DataFlowGraph &DFG;
+    DataFlowGraph::DefStackMap DefM;
+    bool Trace;
+
+    // map: register -> (map: stmt -> reaching def)
+    std::map<RegisterRef,std::map<NodeId,NodeId>> RDefMap;
+    std::vector<NodeId> Copies;
+
+    void recordCopy(NodeAddr<StmtNode*> SA, MachineInstr *MI);
+    void updateMap(NodeAddr<InstrNode*> IA);
+    bool scanBlock(MachineBasicBlock *B);
+  };
+}
+
+#endif