[Dominators] Fix and optimize edge insertion of depth-based search

Summary:
After (x,y) is inserted, depth-based search finds all affected v that satisfies:

depth(nca(x,y))+1 < depth(v) && there exists a path P from y to v where every w on P satisfies depth(v) <= depth(w)

This reduces to a widest path problem (maximizing the depth of the
minimum vertex in the path) which can be solved by a modified version of
Dijkstra with a bucket queue (named depth-based search in the paper).

The algorithm visits vertices in decreasing order of bucket number.
However, the current code misused priority_queue to extract them in
increasing order. I cannot think of a failing scenario but it surely may
process vertices more than once due to the local usage of Processed.

This patch fixes this bug and simplifies/optimizes the code a bit. Also
add more comments.

Reviewers: kuhar

Reviewed By: kuhar

Subscribers: kristina, jdoerfert, llvm-commits, NutshellySima, brzycki

Tags: #llvm

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

llvm-svn: 354306

0 files changed, 0 insertions, 0 deletions