[ScopBuilder] Introduce -polly-stmt-granularity=scalar-indep option.

The option splits BasicBlocks into minimal statements such that no
additional scalar dependencies are introduced.

The algorithm is based on a union-find structure, and unites sets if
putting them into separate statements would introduce a scalar
dependencies. As a consequence, instructions may be split into separate
statements such their relative order is different than the statements
they are in. This is accounted for instructions whose relative order
matters (e.g. memory accesses).

The algorithm is generic in that heuristic changes can be made
relatively easily. We might relax the order requirement for read-reads
or accesses to different base pointers. Forwardable instructions can be
made to not cause a join.

This implementation gives us a speed-up of 82% in SPEC 2006 456.hmmer
benchmark by allowing loop-distribution in a hot loop such that one of
the loops can be vectorized.

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

llvm-svn: 314983

0 files changed, 0 insertions, 0 deletions