From 400433dfea29af8b826db9abb24a7c0fe3c0c894 Mon Sep 17 00:00:00 2001
From: Chris Lattner <sabre@nondot.org>
Date: Tue, 11 Nov 2003 05:08:59 +0000
Subject: [PATCH] Add new method for computing node mappings. This is used by
 the pool allocator

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@9880 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Analysis/DataStructure/DataStructure.cpp | 31 ++++++++++++++++++++
 1 file changed, 31 insertions(+)

diff --git a/lib/Analysis/DataStructure/DataStructure.cpp b/lib/Analysis/DataStructure/DataStructure.cpp
index c20299e0bb2..2883899b1c3 100644
--- a/lib/Analysis/DataStructure/DataStructure.cpp
+++ b/lib/Analysis/DataStructure/DataStructure.cpp
@@ -1638,3 +1638,34 @@ void DSGraph::mergeInGlobalsGraph() {
   OldRetNodes.clear();
   removeTriviallyDeadNodes();
 }
+
+/// computeNodeMapping - Given roots in two different DSGraphs, traverse the
+/// nodes reachable from the two graphs, computing the mapping of nodes from
+/// the first to the second graph.
+///
+void DSGraph::computeNodeMapping(const DSNodeHandle &NH1,
+                                 const DSNodeHandle &NH2, NodeMapTy &NodeMap) {
+  DSNode *N1 = NH1.getNode(), *N2 = NH2.getNode();
+  if (N1 == 0 || N2 == 0) return;
+
+  DSNodeHandle &Entry = NodeMap[N1];
+  if (Entry.getNode()) {
+    // Termination of recursion!
+    assert(Entry.getNode() == N2 &&
+           Entry.getOffset() == (NH1.getOffset()+NH2.getOffset()) &&
+           "Inconsistent mapping detected!");
+    return;
+  }
+  
+  Entry.setNode(N2);
+  Entry.setOffset(NH1.getOffset()+NH2.getOffset());
+
+  // Loop over all of the fields that N1 and N2 have in common, recursively
+  // mapping the edges together now.
+  int N2Idx = NH2.getOffset()-NH1.getOffset();
+  unsigned N2Size = N2->getSize();
+  for (unsigned i = 0, e = N1->getSize(); i < e; i += DS::PointerSize)
+    if (unsigned(N2Idx)+i < N2Size)
+      computeNodeMapping(N1->getLink(i), N2->getLink(N2Idx+i), NodeMap);
+}
+
-- 
2.34.1