From 7fc033a24d5e82674212379ef4d4d67373a03990 Mon Sep 17 00:00:00 2001
From: Evan Cheng <evan.cheng@apple.com>
Date: Fri, 3 Nov 2006 03:06:21 +0000
Subject: [PATCH] Added DAG combiner transformation to generate pre-indexed
 loads.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@31410 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/CodeGen/SelectionDAG/DAGCombiner.cpp | 112 +++++++++++++++++++++++
 1 file changed, 112 insertions(+)

diff --git a/lib/CodeGen/SelectionDAG/DAGCombiner.cpp b/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
index 39090edea21..46aecb859df 100644
--- a/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
+++ b/lib/CodeGen/SelectionDAG/DAGCombiner.cpp
@@ -174,6 +174,114 @@ namespace {
       return true;
     }
 
+    bool CombineToIndexedLoadStore(SDNode *N) {
+      SDOperand Ptr;
+      bool isLoad = true;
+      if (LoadSDNode *LD  = dyn_cast<LoadSDNode>(N)) {
+        Ptr = LD->getBasePtr();
+      } else
+        return false;
+
+      if (AfterLegalize &&
+          (Ptr.getOpcode() == ISD::ADD || Ptr.getOpcode() == ISD::SUB) &&
+          Ptr.Val->use_size() > 1) {
+        SDOperand BasePtr;
+        SDOperand Offset;
+        ISD::MemOpAddrMode AM = ISD::UNINDEXED;
+        if (TLI.getLegalPreIndexedAddressBase(N, BasePtr, Offset, AM, DAG)) {
+          // Try turning it into a pre-indexed load / store except when
+          // 1) Another use of base ptr is a predecessor of N. If ptr is folded
+          //    that would create a cycle.
+          // 2) All uses are load / store ops that use it as base ptr and offset
+          //    is just an addressing mode immediate.
+          // 3) If the would-be new base may not to be dead at N. FIXME: The
+          //    proper check is too expensive (in turns of compile time) to 
+          //    check. Just make sure other uses of the new base are not also
+          //    themselves use of loads / stores.
+
+          bool OffIsAMImm = Offset.getOpcode() == ISD::Constant &&
+            TLI.isLegalAddressImmediate(cast<ConstantSDNode>(Offset)->getValue());
+
+          // Check for #3.
+          if (OffIsAMImm && BasePtr.Val->use_size() > 1) {
+            for (SDNode::use_iterator I = BasePtr.Val->use_begin(),
+                   E = BasePtr.Val->use_end(); I != E; ++I) {
+              SDNode *Use = *I;
+              if (Use == Ptr.Val)
+                continue;
+              if (Use->getOpcode() == ISD::ADD || Use->getOpcode() == ISD::SUB) {
+                for (SDNode::use_iterator II = Use->use_begin(),
+                       EE = Use->use_end(); II != EE; ++II) {
+                  SDNode *UseUse = *II;
+                  if (UseUse->getOpcode() == ISD::LOAD &&
+                      cast<LoadSDNode>(UseUse)->getBasePtr().Val == Use)
+                    return false;
+                  else if (UseUse->getOpcode() == ISD::STORE &&
+                           cast<StoreSDNode>(UseUse)->getBasePtr().Val == Use)
+                    return false;
+                }
+              }
+            }
+          }
+
+          // Now check for #1 and #2.
+          unsigned NumRealUses = 0;
+          for (SDNode::use_iterator I = Ptr.Val->use_begin(),
+                 E = Ptr.Val->use_end(); I != E; ++I) {
+            SDNode *Use = *I;
+            if (Use == N)
+              continue;
+            if (Use->isPredecessor(N))
+              return false;
+
+            if (!OffIsAMImm)
+              NumRealUses++;
+            // FIXME: Do we need a target hook here
+            else if (Use->getOpcode() == ISD::LOAD) {
+              if (cast<LoadSDNode>(Use)->getBasePtr().Val != Ptr.Val)
+                NumRealUses++;
+            } else if (Use->getOpcode() == ISD::STORE) {
+              if (cast<StoreSDNode>(Use)->getBasePtr().Val != Ptr.Val)
+                NumRealUses++;
+            } else
+              NumRealUses++;
+          }
+          if (NumRealUses == 0)
+            return false;
+
+          SDOperand Result =
+            DAG.getIndexedLoad(SDOperand(N,0), BasePtr, Offset, AM);
+          ++NodesCombined;
+          DEBUG(std::cerr << "\nReplacing.4 "; N->dump();
+                std::cerr << "\nWith: "; Result.Val->dump(&DAG);
+                std::cerr << '\n');
+          std::vector<SDNode*> NowDead;
+          DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 0), Result.getValue(0),
+                                        NowDead);
+          DAG.ReplaceAllUsesOfValueWith(SDOperand(N, 1), Result.getValue(2),
+                                        NowDead);
+
+          // Nodes can end up on the worklist more than once.  Make sure we do
+          // not process a node that has been replaced.
+          for (unsigned i = 0, e = NowDead.size(); i != e; ++i)
+            removeFromWorkList(NowDead[i]);
+          // Finally, since the node is now dead, remove it from the graph.
+          DAG.DeleteNode(N);
+
+          // Replace the uses of Ptr with uses of the updated base value.
+          DAG.ReplaceAllUsesOfValueWith(Ptr, Result.getValue(1), NowDead);
+          removeFromWorkList(Ptr.Val);
+          for (unsigned i = 0, e = NowDead.size(); i != e; ++i)
+            removeFromWorkList(NowDead[i]);
+          DAG.DeleteNode(Ptr.Val);
+
+          return true;
+        }
+      }
+
+      return false;
+    }
+
     /// visit - call the node-specific routine that knows how to fold each
     /// particular type of node.
     SDOperand visit(SDNode *N);
@@ -2752,6 +2860,10 @@ SDOperand DAGCombiner::visitLOAD(SDNode *N) {
     }
   }
 
+  // Try transforming N to an indexed load.
+  if (CombineToIndexedLoadStore(N))
+    return SDOperand(N, 0);
+
   return SDOperand();
 }
 
-- 
2.34.1