Page MenuHomePhabricator

[Attributor][WIP] Introduce Loop AA
Needs ReviewPublic

Authored by bbn on Aug 27 2020, 4:35 AM.

Details

Summary

This function abstract attribute identifies whether the loops in a function are
"always-endless" or "never-endless". We can use such information to improve
the deduction of "willreturn" and undefined behavior.

Diff Detail

Unit TestsFailed

TimeTest
140 mslinux > LLVM.Transforms/Attributor::depgraph.ll
Script: -- : 'RUN: at line 2'; /mnt/disks/ssd0/agent/llvm-project/build/bin/opt -passes=attributor-cgscc -S < /mnt/disks/ssd0/agent/llvm-project/llvm/test/Transforms/Attributor/depgraph.ll 2>&1 | /mnt/disks/ssd0/agent/llvm-project/build/bin/FileCheck /mnt/disks/ssd0/agent/llvm-project/llvm/test/Transforms/Attributor/depgraph.ll --check-prefixes=CHECK
700 mslinux > LLVM.Transforms/Attributor::dereferenceable-1.ll
Script: -- : 'RUN: at line 2'; /mnt/disks/ssd0/agent/llvm-project/build/bin/opt -attributor -enable-new-pm=0 -attributor-manifest-internal -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=19 -S < /mnt/disks/ssd0/agent/llvm-project/llvm/test/Transforms/Attributor/dereferenceable-1.ll | /mnt/disks/ssd0/agent/llvm-project/build/bin/FileCheck /mnt/disks/ssd0/agent/llvm-project/llvm/test/Transforms/Attributor/dereferenceable-1.ll --check-prefixes=CHECK,NOT_CGSCC_NPM,NOT_CGSCC_OPM,NOT_TUNIT_NPM,IS__TUNIT____,IS________OPM,IS__TUNIT_OPM
690 mslinux > LLVM.Transforms/Attributor::liveness.ll
Script: -- : 'RUN: at line 2'; /mnt/disks/ssd0/agent/llvm-project/build/bin/opt -attributor -enable-new-pm=0 -attributor-manifest-internal -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=39 -S < /mnt/disks/ssd0/agent/llvm-project/llvm/test/Transforms/Attributor/liveness.ll | /mnt/disks/ssd0/agent/llvm-project/build/bin/FileCheck /mnt/disks/ssd0/agent/llvm-project/llvm/test/Transforms/Attributor/liveness.ll --check-prefixes=CHECK,NOT_CGSCC_NPM,NOT_CGSCC_OPM,NOT_TUNIT_NPM,IS__TUNIT____,IS________OPM,IS__TUNIT_OPM
680 mslinux > LLVM.Transforms/Attributor::nonnull.ll
Script: -- : 'RUN: at line 2'; /mnt/disks/ssd0/agent/llvm-project/build/bin/opt -attributor -enable-new-pm=0 -attributor-manifest-internal -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=15 -S < /mnt/disks/ssd0/agent/llvm-project/llvm/test/Transforms/Attributor/nonnull.ll | /mnt/disks/ssd0/agent/llvm-project/build/bin/FileCheck /mnt/disks/ssd0/agent/llvm-project/llvm/test/Transforms/Attributor/nonnull.ll --check-prefixes=CHECK,NOT_CGSCC_NPM,NOT_CGSCC_OPM,NOT_TUNIT_NPM,IS__TUNIT____,IS________OPM,IS__TUNIT_OPM
610 mslinux > LLVM.Transforms/Attributor::noreturn.ll
Script: -- : 'RUN: at line 2'; /mnt/disks/ssd0/agent/llvm-project/build/bin/opt -attributor -enable-new-pm=0 -attributor-manifest-internal -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=1 -S < /mnt/disks/ssd0/agent/llvm-project/llvm/test/Transforms/Attributor/noreturn.ll | /mnt/disks/ssd0/agent/llvm-project/build/bin/FileCheck /mnt/disks/ssd0/agent/llvm-project/llvm/test/Transforms/Attributor/noreturn.ll --check-prefixes=CHECK,NOT_CGSCC_NPM,NOT_CGSCC_OPM,NOT_TUNIT_NPM,IS__TUNIT____,IS________OPM,IS__TUNIT_OPM
View Full Test Results (18 Failed)

Event Timeline

bbn created this revision.Aug 27 2020, 4:35 AM
Herald added a reviewer: homerdin. · View Herald Transcript
Herald added a project: Restricted Project. · View Herald Transcript
bbn requested review of this revision.Aug 27 2020, 4:35 AM
bbn added a comment.Aug 27 2020, 4:35 AM

I am still working on this, tests will be added later.

kuter added inline comments.Aug 27 2020, 5:16 AM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
7948–7952

I don't think this is correct.
for known endless, range can contain 1 if the range is in [0,1].
I don't think you can prove a loop is endless by looking at the range (except for it always being 0)
IMHO you should look at the SCEV, what does other people think ?
@jdoerfert

kuter added inline comments.Aug 27 2020, 5:34 AM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
7948–7952

I am sorry I ment never endless. in the 3th line phab won't let me change the inline comment.

baziotis added inline comments.Aug 27 2020, 5:52 AM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
7942

Instead of looping every instruction, you can use getTerminator() and check if it's a branch.

7943

For that to make sense, you have to verify that the branch isConditional(). Also, note that loops
may be rotated. In that case, the condition is not in the header block, but in the latch.

Generally, loops can get quite complicated and so, as Kuter said, you probably want to use
SCEV (for example, backedge taken count etc.) I'll have to think that again because SCEV
won't benefit from Attributor, meaning, at a high-level, using constant range AA when it makes
sense seems reasonable.

uenoku added inline comments.Aug 27 2020, 5:57 AM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
7943

FWIW, AAConstantRange actually uses SCEV internally but I agree that using AAConstantRange might make things complicated as a starting point. So you can use SCEV first.

baziotis added inline comments.Aug 27 2020, 6:17 AM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
7943

Yes, but the point is that using constant range directly makes things difficult because we have to re-deduce information and loop structure that SCEV is supposed to handle (e.g. the code above is doing something similar to backedge taken count).

bbn added inline comments.Aug 28 2020, 8:19 AM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
7943

Thanks for the idea.

  1. I think even if the loop is rotated, we can use such method to determine whether a loop is endless or not, right?
  2. I think SCEV could be a good idea, but I cannot find a reasonable test for this. The range I get is always "full-set", can you give an example for this? Thanks
uenoku added inline comments.Aug 28 2020, 8:39 AM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
7943

I think SCEV could be a good idea, but I cannot find a reasonable test for this. The range I get is always "full-set", can you give an example for this?

We have tests for loop terminations in a test for willreturn (I guess)

baziotis added inline comments.Aug 28 2020, 8:48 AM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
7943
  1. Well, it gets really complicated (and hacky) really fast. You have to have two code paths; one for rotated and one for not. Also, I agree with Kuter in the other comment. For an "always true" condition, the range has to be _equal_ to 1, not just contain it.

But even with an always true condition, you're not sure the loop is endless.
Because the loop might have some kind of control
flow inside that makes the loop stop. For example:

while (some condition that is always true) {
  if (some condition that makes the loop stop at some point)
    break;
}

Which brings us again to the initial point: It seems using SCEV is the only sane way. SCEV is
supposed to handle all that and other analyses / transformations to use it, instead of replicating
part of its functionality.

I think SCEV could be a good idea, but I cannot find a reasonable test for this

For what ?

The range I get is always "full-set", can you give an example for this?

@uenoku should be able to help you here.

uenoku added inline comments.Aug 28 2020, 8:57 AM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
7943

I think even if the loop is rotated, we can use such method to determine whether a loop is endless or not, right

Maybe we can first check the loop is canonicalized or not. If the loop is LCSSA, things get easier.
But as @baziotis says we need to replicate the code so it's not clear we should do similar things here.
One solution would be adding callbacks to SCEV and using Attributor information from SCEV but it would be (really) complicated and difficult.

bbn added inline comments.Aug 28 2020, 9:01 AM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
7943

Thanks for the idea here. I will take a look at it.

baziotis added inline comments.Aug 28 2020, 9:37 AM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
7943

Maybe we can first check the loop is canonicalized or not. If the loop is LCSSA, things get easier.

How would LCSSA help ? Btw, @bbn if you want to read about LCSSA or other canonical forms, you can check this: https://llvm.org/docs/LoopTerminology.html

One solution would be adding callbacks to SCEV and using Attributor information from SCEV but it would be (really) complicated and difficult.

I mean yes, ideally SCEV would do its thing by taking advantage of the Attributor. But right now, it's certainly a bad idea unless we have a good plan for it.

uenoku added inline comments.Aug 28 2020, 10:58 AM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
7943

I thought we can use SCEV more easily and discuss the exit conditions more simply by restricting the loop form. However, Come to think of it, LCSSA itself doesn't help the dedication. Sorry for confusion;)

I mean yes, ideally SCEV would do its thing by taking advantage of the Attributor. But right now, it's certainly a bad idea unless we have a good plan for it.

Yes, I agree

baziotis added inline comments.Aug 28 2020, 1:07 PM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
7943

Great and np. So, @bbn you can try SCEV and don't hesitate to ask if you have any problem. SCEV is a beast, I know from experience :)