[LoopInterchange] Disallow interchange when memory accesses are guarded by control flow (PR48057)

[TaWeiTu]

Summary

If instructions that have side effects are guarded by control flow,
the order of execution might differ after interchanging the loops
and results in incorrect behaviour (the branch condition may depends
on the execution order).

This fixes https://bugs.llvm.org/show_bug.cgi?id=48057

[TaWeiTu]

This comment was removed by TaWeiTu.

[TaWeiTu]

This comment was removed by TaWeiTu.

[TaWeiTu]

• Remove unnecessary lines in the test case

[Whitney]

This comment was removed by Whitney.

[fhahn]

Is this fixing a similar issue to D91228 /D87879?

[TaWeiTu]

In D97828#2607047, @fhahn wrote:

Is this fixing a similar issue to D91228 /D87879?

Yes, the intention is the same.
I didn't know about these patches before, and I just test the reproducer PR47523 (the one D87879 is trying to address) against my patch, and the issue is indeed resolved (D91228 is addressing the exact same PR as this one does).

[TaWeiTu]

The following test in lcssa.ll is failing:

define void @lcssa_05(i32* %ptr) {
entry:
  br label %outer.header

outer.header:                                     ; preds = %outer.inc, %entry
  %iv.outer = phi i64 [ 1, %entry ], [ %iv.outer.next, %outer.inc ]
  br label %for.body3

for.body3:                                        ; preds = %bb3, %outer.header
  %iv.inner = phi i64 [ %iv.inner.next, %bb3 ], [ 1, %outer.header ]
  br i1 undef, label %bb2, label %bb3

bb2:                                              ; preds = %for.body3
  %arrayidx5 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @A, i64 0, i64 %iv.inner, i64 %iv.outer
  %vA = load i32, i32* %arrayidx5
  %arrayidx9 = getelementptr inbounds [100 x [100 x i32]], [100 x [100 x i32]]* @C, i64 0, i64 %iv.inner, i64 %iv.outer
  %vC = load i32, i32* %arrayidx9
  %add = add nsw i32 %vA, %vC
  br label %bb3

bb3:                                              ; preds = %bb2, %for.body3
  %addp = phi i32 [ %add, %bb2 ], [ 0, %for.body3 ]
  store i32 %addp, i32* %ptr
  %iv.inner.next = add nuw nsw i64 %iv.inner, 1
  %exitcond = icmp eq i64 %iv.inner.next, 100
  br i1 %exitcond, label %outer.inc, label %for.body3

outer.inc:                                        ; preds = %bb3
  %iv.inner.lcssa = phi i64 [ %iv.inner, %bb3 ]
  %iv.outer.next = add nsw i64 %iv.outer, 1
  %cmp = icmp eq i64 %iv.outer.next, 100
  br i1 %cmp, label %outer.header, label %for.exit

for.exit:                                         ; preds = %outer.inc
  %iv.inner.lcssa.lcssa = phi i64 [ %iv.inner.lcssa, %outer.inc ]
  store i64 %iv.inner.lcssa.lcssa, i64* @Y
  br label %for.end16

for.end16:                                        ; preds = %for.exit
  ret void
}

The test is expecting the loops to be interchanged, but judging from br i1 undef, label %bb2, label %bb3 I think the interchange should probabily be considered invalid in this case?

[TaWeiTu]

• Add testcase of PR47523

[Whitney]

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

1153

can use getLoopFor?
https://llvm.org/doxygen/classllvm_1_1LoopInfoBase.html#a7a7c8e0e4f836c13c015b62e18f386bd

[TaWeiTu]

• Use LoopInfo::getLoopFor

[Whitney]

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

1150

In what scenario, outer loop contains instructions guarded by control flow?
(I assume loop interchange operate on tight loops.)

[TaWeiTu]

• Only check basic blocks in the inner loop

[TaWeiTu]

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

1150

Thanks for pointing that out! I think you are right.

[TaWeiTu]

ping

[Whitney]

Have you considered the case where the blocks guarded by control flow doesn't have memory operation, but affect memory operation through phi?

bb1:
  br %cond, bb2, bb3
bb2:
  br bb4
bb3:
  br bb4
bb4:
  %t = phi [ %t2, %bb2 ], [ %t3, %bb3 ]
  store %t, %p

[TaWeiTu]

Consider instructions that are indirectly affected by the control flow

[TaWeiTu]

In D97828#2624775, @Whitney wrote:

Have you considered the case where the blocks guarded by control flow doesn't have memory operation, but affect memory operation through phi?

bb1:
  br %cond, bb2, bb3
bb2:
  br bb4
bb3:
  br bb4
bb4:
  %t = phi [ %t2, %bb2 ], [ %t3, %bb3 ]
  store %t, %p

I've updated the patch to perform a more comprehensive check that consider instructions that are indirectly guarded by the control flow.

[TaWeiTu]

Gentle ping

[TaWeiTu]

Ping

[TaWeiTu]

Ping

[Whitney]

@TaWeiTu How do you want to handle the lcssa.ll failure? Maybe we can only disallow memory accesses that are guarded by loop variant condition?

[TaWeiTu]

• Skip loop-invariant-guarded blocks

[TaWeiTu]

In D97828#2674875, @Whitney wrote:

@TaWeiTu How do you want to handle the lcssa.ll failure? Maybe we can only disallow memory accesses that are guarded by loop variant condition?

Now only loop-variant-guarded blocks are considered "bad". lcssa.ll should be fixed.
We should probably also add logic to check whether the orders of memory accesses actually change after interchanging the loop, but I think it's beyond the scope of this patch and can be improved in the future.

[Whitney]

llvm/lib/Transforms/Scalar/LoopInterchange.cpp

989

  br cond, BB1, BB2
BB1:
  br BB3
BB2
  br BB3

BB3 should not guarded by a loop variant block, but this function would return BB1, BB2, and BB3.