compute dominator tree children in a deterministic order that does not depend

on the address of BasicBlock objects in memory.  This eliminates stuff like this:

 Inorder Dominator Tree:
   [1]  %entry
     [2]  %loopentry
-      [3]  %loopexit
       [3]  %no_exit
-        [4]  %endif
         [4]  %then
+        [4]  %endif
+      [3]  %loopexit
       [3]  %return


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

1 files changed, 12 insertions, 11 deletions

diff --git a/lib/VMCore/Dominators.cpp b/lib/VMCore/Dominators.cpp
index 76ad59b..b9eee7f 100644
--- a/lib/VMCore/Dominators.cpp
+++ b/lib/VMCore/Dominators.cpp
@@ -373,19 +373,20 @@ void DominatorTree::calculate(const ImmediateDominators &ID) {
   BasicBlock *Root = Roots[0];
   Nodes[Root] = RootNode = new Node(Root, 0); // Add a node for the root...
 
+  Function *F = Root->getParent();
   // Loop over all of the reachable blocks in the function...
-  for (ImmediateDominators::const_iterator I = ID.begin(), E = ID.end();
-       I != E; ++I) {
-    Node *&BBNode = Nodes[I->first];
-    if (!BBNode) {  // Haven't calculated this node yet?
-      // Get or calculate the node for the immediate dominator
-      Node *IDomNode = getNodeForBlock(I->second);
-
-      // Add a new tree node for this BasicBlock, and link it as a child of
-      // IDomNode
-      BBNode = IDomNode->addChild(new Node(I->first, IDomNode));
+  for (Function::iterator I = F->begin(), E = F->end(); I != E; ++I)
+    if (BasicBlock *ImmDom = ID.get(I)) {  // Reachable block.
+      Node *&BBNode = Nodes[I];
+      if (!BBNode) {  // Haven't calculated this node yet?
+        // Get or calculate the node for the immediate dominator
+        Node *IDomNode = getNodeForBlock(ImmDom);
+
+        // Add a new tree node for this BasicBlock, and link it as a child of
+        // IDomNode
+        BBNode = IDomNode->addChild(new Node(I, IDomNode));
+      }
     }
-  }
 }
 
 static std::ostream &operator<<(std::ostream &o,