[MERGE][1.0] Fixes for find_differences() and get_parents_map()

[John S. Yates, Jr.]

I suggested:
> Have you investigated algorithms for computing the "dominance frontier"?
> You might find that those are exactly the nodes of interest.

Aaron Bentley replied:
> I think those are not precisely the same as the dominance frontier.
>
> Given the graph (from oldest to newest)
>
>   A
>  / \
> B   C
> | X |
> D   E
>
>
>
> The dominance frontier of A is (B, C, D, E).  But the only nodes in the
> graph difference are D and E.

Aaron does not specify an actual definition of the dominance frontier.
I always found the name somewhat counter-intuitive.  I wonder whether
Aaron simply tried to guess its significance.  The actual definition is

    The dominance frontier of X is the set of nodes DF such that
    for every node Y in DF:
      X dominates a predecessor of Y, but
      X does not strictly dominate Y.

Given that A dominates every node in Aaron's sample graph by this
definition it has no meaningful dominance frontier.

The classic use of the dominance frontier is in compiler optimization.
It is used to identify the highest point in a control flow graph where
differing definitions of a given variable "merge".  (In compiler jargon
this is termed "phi-node placement" during "conversion to SSA".)

Perhaps my original posting should have clarified that I was imagining
considering edges from child to parent.  I assume a classic VC ancestry
graph, namely a DAG rooted at NULL and having two "tips", leaf nodes,
or nodes without successors.  This is essentially the example that JAM
shows in

http://bundlebuggy.aaronbentley.com/request/%3C475B50C1.3020909%40arbash-meinel.com%3E

My suggestion amounted simply to considering the dominance frontier of
the tips looking back up the graph toward the root.  Each tip has a
region of the DAG which it dominates.  The dominance frontier is the
boundary at which backwards exploration from either tip would first
overlap.  All nodes beyond the frontier are common.

I particularly recommend Bilardi and Pingali's  "Algorithms for
Computing the Static Single Assignment Form"

http://citeseer.ist.psu.edu/727701.html

/john