[LoopInterchange] Fix legality for triangular loops
authorCongzhe Cao <congzhe.cao@huawei.com>
Tue, 11 May 2021 14:59:50 +0000 (10:59 -0400)
committerCongzheUalberta <congzhecao@gmail.com>
Tue, 11 May 2021 15:00:46 +0000 (11:00 -0400)
commit29342291d25b83da97e74d75004b177ba41114fc
tree5948c608b00527fd4af45072964f429518fd9536
parentc58912eca743c612fd2a22c03b64a1bda3d2180f
[LoopInterchange] Fix legality for triangular loops

This is a bug fix in legality check.

When we encounter triangular loops such as the following form:
    for (int i = 0; i < m; i++)
      for (int j = 0; j < i; j++), or

    for (int i = 0; i < m; i++)
      for (int j = 0; j*i < n; j++),

we should not perform interchange since the number of executions of the loop body
will be different before and after interchange, resulting in incorrect results.

Reviewed By: bmahjour

Differential Revision: https://reviews.llvm.org/D101305
llvm/lib/Transforms/Scalar/LoopInterchange.cpp
llvm/test/Transforms/LoopInterchange/inner-indvar-depend-on-outer-indvar.ll [new file with mode: 0644]