Redundant branch elimination based on SSA form, global value numbers,
and dominance relationships.
The following are sufficient conditions for a conditional branch cb1
to be eliminated as redundant
- It is equivalent (has the same value number) as another
conditional branch cb2
- Either (a) the target of the taken branch of cb2 dominates cb1
and said target block has exactly one in edge or (b)
the not-taken continuation of cb2 dominates cb1 and
said continuation block has exactly one in edge.
NOTE: the check for exactly one in edge is used to rule out
situations like the following:
if (C) goto L2 // cb2
x = x + 1;
L2: x = x + 1;
if (C) goto L3. // cb1
Consider redundant branch elimination for cb1.
Here L2 (the target of cb2) dominates cb1, but it
is not correct to eliminate cb1 because it is also
reachable (but not dominated) from the continuation
block of cb2!