From afff40a62da19be15295c0f8ed5d4d450ccb45a5 Mon Sep 17 00:00:00 2001
From: Evan Cheng <evan.cheng@apple.com>
Date: Tue, 4 May 2010 20:26:52 +0000
Subject: [PATCH] Teach PHI elimination to remove REG_SEQUENCE instructions and
 update references of the source operands with references of the destination
 with subreg indices. e.g. %reg1029<def>, %reg1030<def> = VLD1q16
 %reg1024<kill>, ... %reg1031<def> = REG_SEQUENCE %reg1029<kill>, 5,
 %reg1030<kill>, 6 => %reg1031:5<def>, %reg1031:6<def> = VLD1q16
 %reg1024<kill>, ...

PHI elimination now does more than phi elimination. It is really a de-SSA pass.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@103039 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/CodeGen/LiveIntervalAnalysis.cpp | 24 +++++++++++++++
 lib/CodeGen/PHIElimination.cpp       | 60 ++++++++++++++++++++++++++++++++++++
 lib/CodeGen/PHIElimination.h         |  2 ++
 3 files changed, 86 insertions(+)

diff --git a/lib/CodeGen/LiveIntervalAnalysis.cpp b/lib/CodeGen/LiveIntervalAnalysis.cpp
index 26a7190110f..ca9921cd332 100644
--- a/lib/CodeGen/LiveIntervalAnalysis.cpp
+++ b/lib/CodeGen/LiveIntervalAnalysis.cpp
@@ -262,6 +262,23 @@ static void printRegName(unsigned reg, const TargetRegisterInfo* tri_) {
 }
 #endif
 
+static
+bool MultipleDefsByMI(const MachineInstr &MI, unsigned MOIdx) {
+  unsigned Reg = MI.getOperand(MOIdx).getReg();
+  for (unsigned i = MOIdx+1, e = MI.getNumOperands(); i < e; ++i) {
+    const MachineOperand &MO = MI.getOperand(i);
+    if (!MO.isReg())
+      continue;
+    if (MO.getReg() == Reg && MO.isDef()) {
+      assert(MI.getOperand(MOIdx).getSubReg() != MO.getSubReg() &&
+             MI.getOperand(MOIdx).getSubReg() &&
+             MO.getSubReg());
+      return true;
+    }
+  }
+  return false;
+}
+
 void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
                                              MachineBasicBlock::iterator mi,
                                              SlotIndex MIIdx,
@@ -372,6 +389,13 @@ void LiveIntervals::handleVirtualRegisterDef(MachineBasicBlock *mbb,
     }
 
   } else {
+    if (MultipleDefsByMI(*mi, MOIdx))
+      // Mutple defs of the same virtual register by the same instruction. e.g.
+      // %reg1031:5<def>, %reg1031:6<def> = VLD1q16 %reg1024<kill>, ...
+      // This is likely due to elimination of REG_SEQUENCE instructions. Return
+      // here since there is nothing to do.
+      return;
+
     // If this is the second time we see a virtual register definition, it
     // must be due to phi elimination or two addr elimination.  If this is
     // the result of two address elimination, then the vreg is one of the
diff --git a/lib/CodeGen/PHIElimination.cpp b/lib/CodeGen/PHIElimination.cpp
index 56e4ecdc570..165171998db 100644
--- a/lib/CodeGen/PHIElimination.cpp
+++ b/lib/CodeGen/PHIElimination.cpp
@@ -30,6 +30,7 @@
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/Debug.h"
+#include "llvm/Support/ErrorHandling.h"
 #include <algorithm>
 #include <map>
 using namespace llvm;
@@ -87,6 +88,10 @@ bool llvm::PHIElimination::runOnMachineFunction(MachineFunction &MF) {
   ImpDefs.clear();
   VRegPHIUseCount.clear();
 
+  // Eliminate REG_SEQUENCE instructions. Their whole purpose was to preseve
+  // SSA form.
+  Changed |= EliminateRegSequences(MF);
+
   return Changed;
 }
 
@@ -444,3 +449,58 @@ MachineBasicBlock *PHIElimination::SplitCriticalEdge(MachineBasicBlock *A,
 
   return NMBB;
 }
+
+static void UpdateRegSequenceSrcs(unsigned SrcReg,
+                                  unsigned DstReg, unsigned SrcIdx,
+                                  MachineRegisterInfo *MRI) {
+  for (MachineRegisterInfo::reg_iterator RI = MRI->reg_begin(SrcReg),
+         UE = MRI->reg_end(); RI != UE; ) {
+    MachineOperand &MO = RI.getOperand();
+    ++RI;
+    MO.setReg(DstReg);
+    MO.setSubReg(SrcIdx);
+  }
+}
+
+/// EliminateRegSequences - Eliminate REG_SEQUENCE instructions as second part
+/// of de-ssa process. This replaces sources of REG_SEQUENCE as sub-register
+/// references of the register defined by REG_SEQUENCE. e.g.
+///
+/// %reg1029<def>, %reg1030<def> = VLD1q16 %reg1024<kill>, ...
+/// %reg1031<def> = REG_SEQUENCE %reg1029<kill>, 5, %reg1030<kill>, 6
+/// =>
+/// %reg1031:5<def>, %reg1031:6<def> = VLD1q16 %reg1024<kill>, ...
+bool PHIElimination::EliminateRegSequences(MachineFunction &MF) {
+  bool Changed = false;
+
+  for (MachineFunction::iterator I = MF.begin(), E = MF.end(); I != E; ++I)
+    for (MachineBasicBlock::iterator BBI = I->begin(), BBE = I->end();
+         BBI != BBE; ) {
+      MachineInstr &MI = *BBI;
+      ++BBI;
+      if (MI.getOpcode() != TargetOpcode::REG_SEQUENCE)
+        continue;
+      unsigned DstReg = MI.getOperand(0).getReg();
+      if (MI.getOperand(0).getSubReg() ||
+          TargetRegisterInfo::isPhysicalRegister(DstReg) ||
+          !(MI.getNumOperands() & 1)) {
+        DEBUG(dbgs() << "Illegal REG_SEQUENCE instruction:" << MI);
+        llvm_unreachable(0);
+      }
+      for (unsigned i = 1, e = MI.getNumOperands(); i < e; i += 2) {
+        unsigned SrcReg = MI.getOperand(i).getReg();
+        if (MI.getOperand(i).getSubReg() ||
+            TargetRegisterInfo::isPhysicalRegister(SrcReg)) {
+          DEBUG(dbgs() << "Illegal REG_SEQUENCE instruction:" << MI);
+          llvm_unreachable(0);
+        }
+        unsigned SrcIdx = MI.getOperand(i+1).getImm();
+        UpdateRegSequenceSrcs(SrcReg, DstReg, SrcIdx, MRI);
+      }
+
+      MI.eraseFromParent();
+      Changed = true;
+    }
+
+  return Changed;
+}
diff --git a/lib/CodeGen/PHIElimination.h b/lib/CodeGen/PHIElimination.h
index 7dedf0318a8..3292aa27af6 100644
--- a/lib/CodeGen/PHIElimination.h
+++ b/lib/CodeGen/PHIElimination.h
@@ -94,6 +94,8 @@ namespace llvm {
       return I;
     }
 
+    bool EliminateRegSequences(MachineFunction &MF);
+
     typedef std::pair<unsigned, unsigned> BBVRegPair;
     typedef DenseMap<BBVRegPair, unsigned> VRegPHIUse;
 
-- 
2.11.0