This is an archive of the discontinued LLVM Phabricator instance.

[LoopPeel] Peel iterations based on and, or conditions
Needs ReviewPublic

Authored by caojoshua on May 24 2023, 8:42 PM.

Details

Reviewers
nikic
fhahn
Summary

This allows us to peel this loop with a and:

for (int i = 0; i < N; ++i) {
  if (i % 2 == 0 && i < 3) // can peel based on || as well
    f1();
  f2();

into:

for (int i = 0; i < 3; ++i) { // peel three iterations
  if (i % 2 == 0)
    f1();
  f2();
}
for (int i = 3; i < N; ++i)
  f2();

Diff Detail

Event Timeline

caojoshua created this revision.May 24 2023, 8:42 PM
Herald added a project: Restricted Project. · View Herald TranscriptMay 24 2023, 8:42 PM

This patch looks at ALL and/or's in the loop. In https://reviews.llvm.org/D151052, @nikic recommended that we only look at and/or's that are used by selects and branches. I think its beneficial to look at the ALL and/or's for the following reasons:

  1. We can look at nested and/or's, which won't be used directly by branch/select.
  2. We can look at and/or's used in other ways. For example, it can be passed to a function.

I have some examples in https://godbolt.org/z/WzE5P1jca.

caojoshua published this revision for review.May 24 2023, 9:10 PM
Herald added a project: Restricted Project. · View Herald TranscriptMay 24 2023, 9:10 PM
nikic added a comment.May 25 2023, 6:58 AM

This patch looks at ALL and/or's in the loop. In https://reviews.llvm.org/D151052, @nikic recommended that we only look at and/or's that are used by selects and branches. I think its beneficial to look at the ALL and/or's for the following reasons:

  1. We can look at nested and/or's, which won't be used directly by branch/select.

We can still inspect the whole and/or tree rooted at a condition.

  1. We can look at and/or's used in other ways. For example, it can be passed to a function.

I believe we should explicitly *not* peel such cases. Peeling is an aggressive transform that trades code size for potential simplification opportunities. If the peeled comparison is not used as a branch or select condition, we likely will not get any worthwhile simplification out of it. There is not much value in making a function argument constant true/false, at least not at this pipeline position.

If we did want to peel such cases, then the way to do that would be to forget about branches, selects, and/ors completely and simply peel all icmps.

I believe we should explicitly *not* peel such cases. Peeling is an aggressive transform that trades code size for potential simplification opportunities. If the peeled comparison is not used as a branch or select condition, we likely will not get any worthwhile simplification out of it. There is not much value in making a function argument constant true/false, at least not at this pipeline position.

If we did want to peel such cases, then the way to do that would be to forget about branches, selects, and/ors completely and simply peel all icmps.

There is value in making an argument of a and/or constant, since it always folds the and/or in peeled loops. This would be similar to peeling select conditions. We won't necessarily eliminate any branches in the loop, but we can at least fold the select/and/or instruction.

For code size, maybe it would be good to have some cost function to only peel small loops (don't think this is a thing right now).

I believe we should explicitly *not* peel such cases. Peeling is an aggressive transform that trades code size for potential simplification opportunities. If the peeled comparison is not used as a branch or select condition, we likely will not get any worthwhile simplification out of it. There is not much value in making a function argument constant true/false, at least not at this pipeline position.

If we did want to peel such cases, then the way to do that would be to forget about branches, selects, and/ors completely and simply peel all icmps.

There is value in making an argument of a and/or constant, since it always folds the and/or in peeled loops. This would be similar to peeling select conditions. We won't necessarily eliminate any branches in the loop, but we can at least fold the select/and/or instruction.

Yes, we can fold away a single instruction. Is that worth duplicating the loop N times? I don't think so. Now, if we can fold the whole and/or tree to true/false and remove a branch based on that, that's going to be worthwhile...

caojoshua updated this revision to Diff 525935.May 25 2023, 8:49 PM

Only peel and/or's that are used as branch/select instructions