Fix LeastCommonAncestor method in Graph module

Solves a problem with Uniformity Analysis in GPUVerify.

"The least common ancestor of two nodes u and v in a rooted tree T is a node w
that is an ancestor of both u and v and that has the greatest depth in T" (CLR).

This is needed when computing the control dependence relation of a CFG. In this
case, we need the least common ancestor of a pair of nodes in the dominator tree
so we can reuse the 'intersect' function given by Cooper et al in "A Simple,
Fast Dominance Algorithm."

The old code picked the ancestor of both u and v that has the *least* depth in
T. This caused uniformity analysis, in GPUVerify, to be imprecise (adding blocks
as non-uniform when they were infact uniform).

0 files changed, 0 insertions, 0 deletions