HomePhabricator

[LCSSA] Efficiently compute blocks dominating at least one exit.

Description

[LCSSA] Efficiently compute blocks dominating at least one exit.

For LCSSA purposes, loop BBs not dominating any of the exits aren't
interesting, as none of the values defined in these blocks can be
used outside the loop.

The way the code computed this information was by comparing each
BB of the loop with each of the exit blocks and ask the dominator tree
about their dominance relation. This is slow.

A more efficient way, implemented here, is that of starting from the
exit blocks and walking the dom upwards until we hit an header. By
transitivity, all the blocks we encounter in our path dominate an exit.

For the testcase provided in PR31851, this reduces compile time on
opt -O2 by ~25%, going from 1m47s to 1m22s.

Thanks to Dan/MichaelZ for discussions/suggesting the approach/review.

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

Details

Committed
davideApr 13 2017, 1:36 PM
Differential Revision
D31843: [LCSSA] Try to not walk the dominator tree more than necessary
Parents
rL300254: Fix -Wunused-value warning
Branches
Unknown
Tags
Unknown