NewGVN: Sort Dominator Tree in RPO order, and use that for generating order.

[• dberlin]

Summary

The optimal iteration order for this problem is RPO order. We want to
process as many preds of a backedge as we can before we process the
backedge.

At the same time, as we add predicate handling, we want to be able to
touch instructions that are dominated by a given block by
ranges (because a change in value numbering a predicate possibly
affects all users we dominate that are using that predicate).
If we don't do it this way, we can't do value inference over
backedges (the paper covers this in depth).

The newgvn branch currently overshoots the last part, and guarantees
that it will touch *at least* the right set of instructions, but it
does touch more. This is because the bitvector instruction ranges are
currently generated in RPO order (so we take the max and the min of
the ranges of dominated blocks, which means there are some in the
middle we didn't have to touch that we did).

We can do better by sorting the dominator tree, and then just using
dominator tree order.

As a preliminary, the dominator tree has some RPO guarantees, but not
enough. It guarantees that for a given node, your idom must come
before you in the RPO ordering. It guarantees no relative RPO ordering
for siblings. We add siblings in whatever order they appear in the module.

So that is what we fix.

We sort the children array of the domtree into RPO order, and then use
the dominator tree for ordering, instead of RPO, since the dominator
tree is now a valid RPO ordering.

Note: This would help any other pass that iterates a forward problem
in dominator tree order. Most of them are single pass. It will still
maximize whatever result they compute. We could also build the
dominator tree in this order, but our incremental updates would still
put it out of sort order, and recomputing the sort order is almost as
hard as general incremental updates of the domtree.

Also note that the sorting does not affect any tests, etc. Nothing
depends on domtree order, including the verifier, the equals
functions for domtree nodes, etc.

How much could this matter, you ask?
Here are the current numbers.
This is generated by running NewGVN over all files in LLVM.

Note that once we propagate equalities, the differences go up by an
order of magnitude or two (IE instead of 29, the max ends up in the
thousands, since the worst case we add a factor of N, where N is the
number of branch predicates). So while it doesn't look that stark for
the default ordering, it gets *much much* worse. There are also
programs in the wild where the difference is already pretty stark
(2 iterations vs hundreds).

RPO ordering:

759040 Number of iterations is 1
112908 Number of iterations is 2

Default dominator tree ordering:

755081 Number of iterations is 1
116234 Number of iterations is 2

603 Number of iterations is 3
 27 Number of iterations is 4
  2 Number of iterations is 5
  1 Number of iterations is 7

Dominator tree sorted:

759040 Number of iterations is 1
112908 Number of iterations is 2
<yay!>

Really bad ordering (sort domtree siblings in postorder. not quite the
worst possible, but yeah):

754008 Number of iterations is 1

21 Number of iterations is 10
 8 Number of iterations is 11
 6 Number of iterations is 12
 5 Number of iterations is 13
 2 Number of iterations is 14
 2 Number of iterations is 15
 3 Number of iterations is 16
 1 Number of iterations is 17
 2 Number of iterations is 18

96642 Number of iterations is 2

1 Number of iterations is 20
2 Number of iterations is 21
1 Number of iterations is 22
1 Number of iterations is 29

17266 Number of iterations is 3

2598 Number of iterations is 4
 798 Number of iterations is 5
 273 Number of iterations is 6
 186 Number of iterations is 7
  80 Number of iterations is 8
  42 Number of iterations is 9

[davide]

Sorry for the slow response, I'm out('ish) of the office these days. I took a close look at your patch.
I happen to be lucky enough to hit a case in the wild where this already matters. The number of iteration goes down from hundreds to ~10, which makes compile time/me happier.
I'll see if I can investigate
Your reasoning looks good to me, so feel free to check this in (modulo small nits). I'll do some more extensive testing when I'm in back in California early next year (although as you pointed out this is not exposed without predicates handling.

lib/Transforms/Scalar/NewGVN.cpp

1375–1377

I apologize in advance if I'm wrong, as I'm not a native speaker, but it shouldn't be
its parent (at least this is the way I've always seen it written down)?
Please ignore otherwise.

1457

Spurious removal of a newline?

[davide]

In D28129#631695, @davide wrote:

Sorry for the slow response, I'm out('ish) of the office these days. I took a close look at your patch.
I happen to be lucky enough to hit a case in the wild where this already matters. The number of iteration goes down from hundreds to ~10, which makes compile time/me happier.
I'll see if I can investigate

*I'll see if I can investigate the use of this tecnique in other passes in the future.

lib/Transforms/Scalar/NewGVN.cpp

bool NewGVN::runGVN(Function &F, DominatorTree *_DT, AssumptionCache *_AC,
   AA = _AA;
   MSSA = _MSSA;
   DL = &F.getParent()->getDataLayout();
   MSSAWalker = MSSA->getWalker();
 
   // Count number of instructions for sizing of hash tables, and come
   // up with a global dfs numbering for instructions.
   unsigned ICount = 0;
-  SmallPtrSet<BasicBlock *, 16> VisitedBlocks;
-
   // Note: We want RPO traversal of the blocks, which is not quite the same as
   // dominator tree order, particularly with regard whether backedges get
   // visited first or second, given a block with multiple successors.
   // If we visit in the wrong order, we will end up performing N times as many
   // iterations.
+  // The dominator tree does guarantee that, for a given dom tree node, it's
+  // parent must occur before it in the RPO ordering. Thus, we only need to sort
+  // the siblings.
+  DenseMap<const DomTreeNode *, unsigned> RPOOrdering;
   ReversePostOrderTraversal<Function *> RPOT(&F);
+  unsigned Counter = 0;
+  for (auto &B : RPOT) {
+    auto *Node = DT->getNode(B);
+    assert(Node && "RPO and Dominator tree should have same reachability");
+    RPOOrdering[Node] = ++Counter;
+  }
+  // Sort dominator tree children arrays into RPO.
   for (auto &B : RPOT) {
-    VisitedBlocks.insert(B);
+    auto *Node = DT->getNode(B);
+    if (Node->getChildren().size() > 1)
+      std::sort(Node->begin(), Node->end(),
+                [&RPOOrdering](const DomTreeNode *A, const DomTreeNode *B) {
+                  return RPOOrdering[A] < RPOOrdering[B];
+                });
+  }
+
+  // Now a standard depth first ordering of the domtree is equivalent to RPO.
+  auto DFI = df_begin(DT->getRootNode());
+  for (auto DFE = df_end(DT->getRootNode()); DFI != DFE; ++DFI) {
+    BasicBlock *B = DFI->getBlock();
     const auto &BlockRange = assignDFSNumbers(B, ICount);
     BlockInstRange.insert({B, BlockRange});
     ICount += BlockRange.second - BlockRange.first;
   }
 
   // Handle forward unreachable blocks and figure out which blocks
   // have single preds.
   for (auto &B : F) {
     // Assign numbers to unreachable blocks.
-    if (!VisitedBlocks.count(&B)) {
+    if (!DFI.nodeVisited(DT->getNode(&B))) {
       const auto &BlockRange = assignDFSNumbers(&B, ICount);
       BlockInstRange.insert({&B, BlockRange});
       ICount += BlockRange.second - BlockRange.first;
     }
   }
 
   TouchedInstructions.resize(ICount + 1);
   DominatedInstRange.reserve(F.size());
for (int InstrNum = TouchedInstructions.find_first(); InstrNum != -1;
         llvm_unreachable("Should have been a MemoryPhi or Instruction");
       }
       updateProcessedCount(V);
       // Reset after processing (because we may mark ourselves as touched when
       // we propagate equalities).
       TouchedInstructions.reset(InstrNum);
     }
   }
-
   Changed |= eliminateInstructions(F);
 
   // Delete all instructions marked for deletion.
   for (Instruction *ToErase : InstructionsToErase) {
     if (!ToErase->use_empty())
       ToErase->replaceAllUsesWith(UndefValue::get(ToErase->getType()));
 
     ToErase->eraseFromParent();