[Dominators] Use a custom DFS implementation
[Dominators] Use a custom DFS implementation

Summary:
Custom DFS implementation allows us to skip over certain nodes without adding them to the visited map, which is not easily doable with llvm's dfs iterators. What's more, caching predecessors becomes easy.

This patch implements a single DFS function (template) for both forward and reverse DFS, which should be easier to maintain then separate two ones.

Skipping over nodes based on a predicate will be necessary later to implement incremental updates.

There also seems to be a very slight performance improved when bootstrapping clang with this patch on my machine (3:28s -> 3:26s) .

Reviewers: dberlin, sanjoy, davide, grosser

Reviewed By: dberlin

Subscribers: llvm-commits

Differential Revision: https://reviews.llvm.org/D34651

git-svn-id: 0ff597fd157e6f4fc38580e8d64ab130330d2411@307727 91177308-0d34-0410-b5e6-96231b3b80d8

GPUOpen-Drivers/llvm,apple/swift-llvm,apple/swift-llvm,GPUOpen-Drivers/llvm,apple/swift-llvm,GPUOpen-Drivers/llvm,apple/swift-llvm,apple/swift-llvm,apple/swift-llvm,GPUOpen-Drivers/llvm,apple/swift-llvm,llvm-mirror/llvm,llvm-mirror/llvm,GPUOpen-Drivers/llvm,llvm-mirror/llvm,apple/swift-llvm,llvm-mirror/llvm,llvm-mirror/llvm,GPUOpen-Drivers/llvm,llvm-mirror/llvm,GPUOpen-Drivers/llvm,llvm-mirror/llvm,llvm-mirror/llvm,GPUOpen-Drivers/llvm,llvm-mirror/llvm