Handle non-unique edges in edge-dominance

This removes a quadratic behavior in assert-enabled builds.

GVN propagates the equivalence from a condition into the blocks guarded by the
condition.  E.g. for 'if (a == 7) { ... }', 'a' will be replaced in the block
with 7.  It does this by replacing all the uses of 'a' that are dominated by
the true edge.

For a switch with N cases and U uses of the value, this will mean N * U calls
to 'dominates'.  Asserting isSingleEdge in 'dominates' make this N^2 * U
because this function checks for the uniqueness of the edge. I.e. traverses
each edge between the SwitchInst's block and the cases.

The change removes the assert and makes 'dominates' works correctly in the
presence of non-unique edges.

This brings build time down by an order of magnitude for an input that has
~10k cases in a switch statement.

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

llvm-svn: 304721

0 files changed, 0 insertions, 0 deletions