Page MenuHomePhabricator

[LoopPredication] Handle the case when the guard and the latch IV have different offsets
ClosedPublic

Authored by apilipenko on Oct 19 2017, 9:27 AM.

Details

Summary

This is a follow up change for D37569.

Currently the transformation is limited to the case when:

  • The loop has a single latch with the condition of the form: ++i <pred> latchLimit, where <pred> is u<, u<=, s<, or s<=.
  • The step of the IV used in the latch condition is 1.
  • The IV of the latch condition is the same as the post increment IV of the guard condition.
  • The guard condition is of the form i u< guardLimit.

This patch enables the transform in the case when the latch is

latchStart + i <pred> latchLimit, where <pred> is u<, u<=, s<, or s<=.

And the guard is

guardStart + i u< guardLimit

This is the last change in this chain.

Diff Detail

Repository
rL LLVM

Event Timeline

apilipenko created this revision.Oct 19 2017, 9:27 AM
anna edited edge metadata.Oct 19 2017, 10:14 AM

@apilipenko please add patch with full context.

Upload diff with context. Minor fix in the header comment.

anna requested changes to this revision.Oct 24 2017, 7:16 AM

Artur, before this patch, we were checking whether RangeCheckIV's postIncExpr is latchCheckIV.

Now, the header comments and proof seems to point to the fact that the guard and latch are using the same offset (lines 103 - 110), but the code does not have any check that we are using the same offset. Or, is it that the offset is the same, but the difference in the latchCheckIV versus rangeCheckIV is caught in their respective start values, and the offset for both latch and guard remains the same?

Pls see inline comment for more clarification and specific example.

lib/Transforms/Scalar/LoopPredication.cpp
61 ↗(On Diff #119652)

Now that arbitrary offsets are supported for both guard and latch, the guard can even be guard(G(I.INC)), while the backedge condition can be B(I)?
In other words, do we need the same offset 'i' for both guard and latch?

Please add a testcase when the guard uses the I.INC and backedge uses I.

This revision now requires changes to proceed.Oct 24 2017, 7:16 AM
apilipenko edited edge metadata.

Clarified the description, added the requested test case.

In D39097#905174, @anna wrote:

Artur, before this patch, we were checking whether RangeCheckIV's postIncExpr is latchCheckIV.

Now, the header comments and proof seems to point to the fact that the guard and latch are using the same offset (lines 103 - 110), but the code does not have any check that we are using the same offset. Or, is it that the offset is the same, but the difference in the latchCheckIV versus rangeCheckIV is caught in their respective start values, and the offset for both latch and guard remains the same?

I changed the loop in the description so it doesn't use Start. Instead the offsets are sunk into predicates G and B.

I also explicitly specified the predicates for the supported cases.

lib/Transforms/Scalar/LoopPredication.cpp
61 ↗(On Diff #119652)

No, we don't. I changed the loop so to make this clear, added the requested test case.

anna accepted this revision.Oct 27 2017, 5:47 AM

LGTM.

lib/Transforms/Scalar/LoopPredication.cpp
56 ↗(On Diff #120437)

I'm not sure if this is clearer :)
My concern was that this loop makes it look like we support only the case where B and G use the same value of I.

It becomes clearer when we define what B and G predicates are.

103 ↗(On Diff #120437)

The key point here is that latchStart and guardStart can be different values.
So, B(X) can be X, while G(X) is X+1. Various different combinations are allowed.

This revision is now accepted and ready to land.Oct 27 2017, 5:47 AM
This revision was automatically updated to reflect the committed changes.