[SCEV] Strengthen variance condition in calculateLoopDisposition
authorMax Kazantsev <max.kazantsev@azul.com>
Wed, 22 Nov 2017 06:21:39 +0000 (06:21 +0000)
committerMax Kazantsev <max.kazantsev@azul.com>
Wed, 22 Nov 2017 06:21:39 +0000 (06:21 +0000)
commit23044fa63946909ec21dee0cca5f5a50d83f8262
treeaee0cd5586471a039b54bc98a25d28304ef02fae
parent4999a5fdd7b97d53e4e3432b2b60a5fab6f08473
[SCEV] Strengthen variance condition in calculateLoopDisposition

Given loops `L1` and `L2` with AddRecs `AR1` and `AR2` varying in them respectively.
When identifying loop disposition of `AR2` w.r.t. `L1`, we only say that it is varying if
`L1` contains `L2`. But there is also a possible situation where `L1` and `L2` are
consecutive sibling loops within the parent loop. In this case, `AR2` is also varying
w.r.t. `L1`, but we don't correctly identify it.

It can lead, for exaple, to attempt of incorrect folding. Consider:
  AR1 = {a,+,b}<L1>
  AR2 = {c,+,d}<L2>
  EXAR2 = sext(AR1)
  MUL = mul AR1, EXAR2
If we incorrectly assume that `EXAR2` is invariant w.r.t. `L1`, we can end up trying to
construct something like: `{a * {c,+,d}<L2>,+,b * {c,+,d}<L2>}<L1>`, which is incorrect
because `AR2` is not available on entrance of `L1`.

Both situations "`L1` contains `L2`" and "`L1` preceeds sibling loop `L2`" can be handled
with one check: "header of `L1` dominates header of `L2`". This patch replaces the old
insufficient check with this one.

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

llvm-svn: 318819
llvm/lib/Analysis/ScalarEvolution.cpp
llvm/test/Analysis/ScalarEvolution/different-loops-recs.ll