tree 59d9a41a9a9f58ca0622efc52618e492bbab0f43
parent 84a16eb1cb6c521d68777103e90474f54e91fce3
author Fangrui Song <maskray@google.com> 1550553412 +0000
committer Fangrui Song <maskray@google.com> 1550553412 +0000

[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

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