[RDF] Improvements to copy propagation

- Allow any instruction to define equality between registers.
- Keep the DFG updated.

llvm-svn: 258075

2 files changed, 145 insertions, 72 deletions

diff --git a/llvm/lib/Target/Hexagon/RDFCopy.cpp b/llvm/lib/Target/Hexagon/RDFCopy.cpp
index c547c719507..251e175e228 100644
--- a/llvm/lib/Target/Hexagon/RDFCopy.cpp
+++ b/llvm/lib/Target/Hexagon/RDFCopy.cpp
@@ -7,16 +7,17 @@
 //
 //===----------------------------------------------------------------------===//
 //
-// Simplistic RDF-based copy propagation.
+// 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/CodeGen/MachineRegisterInfo.h"
 #include "llvm/Support/CommandLine.h"
-
-#include <atomic>
+#include "llvm/Target/TargetInstrInfo.h"
+#include "llvm/Target/TargetRegisterInfo.h"
 
 #ifndef NDEBUG
 static cl::opt<unsigned> CpLimit("rdf-cp-limit", cl::init(0), cl::Hidden);
@@ -26,18 +27,66 @@ static unsigned CpCount = 0;
 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;
+bool CopyPropagation::interpretAsCopy(const MachineInstr *MI, EqualityMap &EM) {
+  unsigned Opc = MI->getOpcode();
+  switch (Opc) {
+    case TargetOpcode::COPY: {
+      const MachineOperand &Dst = MI->getOperand(0);
+      const MachineOperand &Src = MI->getOperand(1);
+      RegisterRef DstR = { Dst.getReg(), Dst.getSubReg() };
+      RegisterRef SrcR = { Src.getReg(), Src.getSubReg() };
+      if (TargetRegisterInfo::isVirtualRegister(DstR.Reg)) {
+        if (!TargetRegisterInfo::isVirtualRegister(SrcR.Reg))
+          return false;
+        MachineRegisterInfo &MRI = DFG.getMF().getRegInfo();
+        if (MRI.getRegClass(DstR.Reg) != MRI.getRegClass(SrcR.Reg))
+          return false;
+      } else if (TargetRegisterInfo::isPhysicalRegister(DstR.Reg)) {
+        if (!TargetRegisterInfo::isPhysicalRegister(SrcR.Reg))
+          return false;
+        const TargetRegisterInfo &TRI = DFG.getTRI();
+        if (TRI.getMinimalPhysRegClass(DstR.Reg) !=
+            TRI.getMinimalPhysRegClass(SrcR.Reg))
+          return false;
+      } else {
+        // Copy between some unknown objects.
+        return false;
+      }
+      EM.insert(std::make_pair(DstR, SrcR));
+      return true;
+    }
+    case TargetOpcode::REG_SEQUENCE: {
+      const MachineOperand &Dst = MI->getOperand(0);
+      RegisterRef DefR = { Dst.getReg(), Dst.getSubReg() };
+      SmallVector<TargetInstrInfo::RegSubRegPairAndIdx,2> Inputs;
+      const TargetInstrInfo &TII = DFG.getTII();
+      if (!TII.getRegSequenceInputs(*MI, 0, Inputs))
+        return false;
+      for (auto I : Inputs) {
+        unsigned S = DFG.getTRI().composeSubRegIndices(DefR.Sub, I.SubIdx);
+        RegisterRef DR = { DefR.Reg, S };
+        RegisterRef SR = { I.Reg, I.SubReg };
+        EM.insert(std::make_pair(DR, SR));
+      }
+      return true;
+    }
+  }
+  return false;
+}
+
+
+void CopyPropagation::recordCopy(NodeAddr<StmtNode*> SA, EqualityMap &EM) {
+  CopyMap.insert(std::make_pair(SA.Id, EM));
   Copies.push_back(SA.Id);
-  RDefMap[SrcR][SA.Id] = FS->second.top()->Id;
-  // Insert DstR into the map.
-  RDefMap[DstR];
+
+  for (auto I : EM) {
+    auto FS = DefM.find(I.second);
+    if (FS == DefM.end() || FS->second.empty())
+      continue; // Undefined source
+    RDefMap[I.second][SA.Id] = FS->second.top()->Id;
+    // Insert DstR into the map.
+    RDefMap[I.first];
+  }
 }
 
 
@@ -74,9 +123,9 @@ bool CopyPropagation::scanBlock(MachineBasicBlock *B) {
   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);
+      EqualityMap EM;
+      if (interpretAsCopy(SA.Addr->getCode(), EM))
+        recordCopy(SA, EM);
     }
 
     updateMap(IA);
@@ -97,8 +146,14 @@ bool CopyPropagation::run() {
 
   if (trace()) {
     dbgs() << "Copies:\n";
-    for (auto I : Copies)
-      dbgs() << *DFG.addr<StmtNode*>(I).Addr->getCode();
+    for (auto I : Copies) {
+      dbgs() << "Instr: " << *DFG.addr<StmtNode*>(I).Addr->getCode();
+      dbgs() << "   eq: {";
+      for (auto J : CopyMap[I])
+        dbgs() << ' ' << Print<RegisterRef>(J.first, DFG) << '='
+               << Print<RegisterRef>(J.second, DFG);
+      dbgs() << " }\n";
+    }
     dbgs() << "\nRDef map:\n";
     for (auto R : RDefMap) {
       dbgs() << Print<RegisterRef>(R.first, DFG) << " -> {";
@@ -110,70 +165,82 @@ bool CopyPropagation::run() {
   }
 
   bool Changed = false;
-  NodeSet Deleted;
 #ifndef NDEBUG
   bool HasLimit = CpLimit.getNumOccurrences() > 0;
 #endif
 
-  for (auto I : Copies) {
+  for (auto C : 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)
+    auto SA = DFG.addr<InstrNode*>(C);
+    auto FS = CopyMap.find(SA.Id);
+    if (FS == CopyMap.end())
       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)
+
+    EqualityMap &EM = FS->second;
+    for (NodeAddr<DefNode*> DA : SA.Addr->members_if(DFG.IsDef, DFG)) {
+      RegisterRef DR = DA.Addr->getRegRef();
+      auto FR = EM.find(DR);
+      if (FR == EM.end())
         continue;
-      MachineOperand &Op = UA.Addr->getOp();
-      if (Op.isTied())
+      RegisterRef SR = FR->second;
+      if (DR == SR)
         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);
-      }
-    }
-  }
+      auto &RDefSR = RDefMap[SR];
+      NodeId RDefSR_SA = RDefSR[SA.Id];
+
+      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() != DR)
+          continue;
+
+        NodeAddr<InstrNode*> IA = UA.Addr->getOwner(DFG);
+        assert(DFG.IsCode<NodeAttrs::Stmt>(IA));
+        if (RDefSR[IA.Id] != RDefSR_SA)
+          continue;
+
+        MachineOperand &Op = UA.Addr->getOp();
+        if (Op.isTied())
+          continue;
+        if (trace()) {
+          dbgs() << "Can replace " << Print<RegisterRef>(DR, DFG)
+                 << " with " << Print<RegisterRef>(SR, DFG) << " in "
+                 << *NodeAddr<StmtNode*>(IA).Addr->getCode();
+        }
+
+        Op.setReg(SR.Reg);
+        Op.setSubReg(SR.Sub);
+        DFG.unlinkUse(UA, false);
+        UA.Addr->linkToDef(UA.Id, DFG.addr<DefNode*>(RDefSR_SA));
+
+        Changed = true;
+  #ifndef NDEBUG
+        if (HasLimit && CpCount >= CpLimit)
+          break;
+        CpCount++;
+  #endif
+
+        auto FC = CopyMap.find(IA.Id);
+        if (FC != CopyMap.end()) {
+          // Update the EM map in the copy's entry.
+          auto &M = FC->second;
+          for (auto &J : M) {
+            if (J.second != DR)
+              continue;
+            J.second = SR;
+            break;
+          }
+        }
+      } // for (N in reached-uses)
+    } // for (DA in defs)
+  } // for (C in Copies)
 
   return Changed;
 }
diff --git a/llvm/lib/Target/Hexagon/RDFCopy.h b/llvm/lib/Target/Hexagon/RDFCopy.h
index 02531b94c9b..6a3ac67fbbc 100644
--- a/llvm/lib/Target/Hexagon/RDFCopy.h
+++ b/llvm/lib/Target/Hexagon/RDFCopy.h
@@ -24,11 +24,15 @@ namespace rdf {
   struct CopyPropagation {
     CopyPropagation(DataFlowGraph &dfg) : MDT(dfg.getDT()), DFG(dfg),
         Trace(false) {}
+    virtual ~CopyPropagation() {}
 
     bool run();
     void trace(bool On) { Trace = On; }
     bool trace() const { return Trace; }
 
+    typedef std::map<RegisterRef, RegisterRef> EqualityMap;
+    virtual bool interpretAsCopy(const MachineInstr *MI, EqualityMap &EM);
+
   private:
     const MachineDominatorTree &MDT;
     DataFlowGraph &DFG;
@@ -37,9 +41,11 @@ namespace rdf {
 
     // map: register -> (map: stmt -> reaching def)
     std::map<RegisterRef,std::map<NodeId,NodeId>> RDefMap;
+    // map: statement -> (map: dst reg -> src reg)
+    std::map<NodeId, EqualityMap> CopyMap;
     std::vector<NodeId> Copies;
 
-    void recordCopy(NodeAddr<StmtNode*> SA, MachineInstr *MI);
+    void recordCopy(NodeAddr<StmtNode*> SA, EqualityMap &EM);
     void updateMap(NodeAddr<InstrNode*> IA);
     bool scanBlock(MachineBasicBlock *B);
   };