This is an archive of the discontinued LLVM Phabricator instance.

[Attributor] AAValueConstantRange: Value range analysis using constant range
ClosedPublic

Authored by uenoku on Dec 17 2019, 10:46 AM.

Details

Summary

This patch introduces AAValueConstantRange, which answers a possible range for integer value in a specific program point.
One of the motivations is propagating existing range metadata. (I think we need to change the situation that range metadata cannot be put to Argument).

The state is a tuple of ConstantRange and it is initialized to (known, assumed) = ([-∞, +∞], empty).

Currently, AAValueConstantRange is created in getAssumedConstant method when AAValueSimplify returns nullptr(worst state).

Supported

  • BinaryOperator(add, sub, ...)
  • CmpInst(icmp eq, ...)
  • !range metadata

AAValueConstantRange is not intended to extend to polyhedral range value analysis.

Diff Detail

Event Timeline

uenoku created this revision.Dec 17 2019, 10:46 AM
uenoku updated this revision to Diff 234340.Dec 17 2019, 10:50 AM
uenoku edited the summary of this revision. (Show Details)

Fix typo.

uenoku edited the summary of this revision. (Show Details)Dec 17 2019, 10:53 AM
uenoku updated this revision to Diff 234358.Dec 17 2019, 11:58 AM

Add comment

uenoku updated this revision to Diff 234360.Dec 17 2019, 12:04 PM

Remove unused function

uenoku edited the summary of this revision. (Show Details)Dec 17 2019, 12:10 PM
uenoku updated this revision to Diff 234539.EditedDec 18 2019, 7:55 AM
  • Add test
  • Use SCEV when the value is phi and defined with circular.
  • Create AA for CmpInst.

I have found this is broken now, please wait.

uenoku retitled this revision from [Attributor][WIP] AAValueConstantRange: Value range analysis using constant range to [Attributor] AAValueConstantRange: Value range analysis using constant range.Dec 18 2019, 8:03 AM
uenoku edited the summary of this revision. (Show Details)
uenoku retitled this revision from [Attributor] AAValueConstantRange: Value range analysis using constant range to [Attributor][WIP] AAValueConstantRange: Value range analysis using constant range.Dec 18 2019, 8:38 AM

Sorry for the wait. I wanted to do a proper initial review and I didn't find the right time.

llvm/include/llvm/Transforms/IPO/Attributor.h
1352

Typo: 'an'

Below, can we make the comments start with three '/'?

1421

I think you need to adjust Assumed too otherwise it might not be a proper subset of Known anymore.

1440

Do we need to intersect the known range here as well?

llvm/lib/Transforms/IPO/Attributor.cpp
2590

I formated the file yesterday, rebase and this should be gone.

4966

If you pass the Attributor changeUseAfterManifest should make this simple.

4971

Can we pass the constant range arguments as const references in the various places.

4978

Shouldn't this imply "an invalid state" (= the worst possible state)? If so, it should never be make it to this point (which you should assert instead).

4994

You should use one of the Attributor::doSthAfterManifest helpers (or a new one). We should avoid modifying values/uses while in the manifest stage.

5082

We should probably provide a helper to make sure the type of a value is OK (I guess integer) and check it in the initialize.

5095

With a check in the initializers this would go away.

5132

I don't think we need to look at all loops here.
The problem is also that getSCEVAtScope might silently fail to actually compute the exit value and instead continue computation with the original one.

I think this is OK already: SE->getUnsignedRange(SE->getSCEV())

5134

Style: With early exits we can minimize indention:
if (!SE || !LI || !I) return false;

5135

We should consider putting some of this in helper methods.

5146

Add a TODO to track the known state as well.

5215

Can you move this case to the beginning Inst * I = ...; if (!I) { ... }, so the rest has one level less of indention?

llvm/test/Transforms/Attributor/value-simplify.ll
193

Please add a FIXME here, should be 7.

uenoku updated this revision to Diff 235021.Dec 21 2019, 8:13 AM
uenoku marked 17 inline comments as done.
uenoku retitled this revision from [Attributor][WIP] AAValueConstantRange: Value range analysis using constant range to [Attributor] AAValueConstantRange: Value range analysis using constant range.

Address comments.

  • SCEV is used in initialize.
  • getAssumedConstantRange takes a program point (Instruction I) and returns assumed range in that program point.
uenoku marked an inline comment as done.Dec 21 2019, 8:17 AM
uenoku added inline comments.
llvm/include/llvm/Transforms/IPO/Attributor.h
1421

Fixed.

1440

In my understanding, "Clamp" should only modify the assumption.

llvm/lib/Transforms/IPO/Attributor.cpp
4978

Yes, I changed to assert.

5132

Yes, you are right. I changed to use SE->getUnsignedRange(SE->getSCEV()) as known range. And if a program point (Instrution *I)is given, SCEV->getSCEVAtScope(I->getParent()) is used.

uenoku marked an inline comment as done.Dec 21 2019, 8:18 AM
uenoku added inline comments.
llvm/lib/Transforms/IPO/Attributor.cpp
5135

I'll do.

uenoku added inline comments.Dec 21 2019, 8:21 AM
llvm/test/Transforms/Attributor/range.ll
235 ↗(On Diff #235021)

I'll add FIXME here because block 4 should be regarded as dead.

I still have to go over the changes properly later, sorry for the wait again.

We should copy the LazyValueInfo analysis test lvi-after-jumpthreading.ll lvi-for-ashr.ll if we can use them to verify the ranges.

Add a TODO that AADereferenceable should use this too.

uenoku updated this revision to Diff 235224.Dec 24 2019, 9:10 AM

Address comment.

  • Use LazyValueInfo as known information
  • Add test(lvi-*.ll)

I think the final round of comments.

llvm/lib/Transforms/IPO/Attributor.cpp
4909

Nit: I'd move this into the state as a static member (getWorstState) taking a bit width. That makes it consistent with the IntegerStates.

4981

Shouldn't we merge the SCEV and LVI information into the known state during intialization and then be done with it?

5002

As mentioned above, if we merge the SCEV and LVI results into known there is no need to do anything but return the assumed value. The TODO should stay though.

5055

I don't think we have a test which checks the metadata, right? We should create one if possible or add a TODO here explaining why it's not possible yet.

5218

I doubt this works to prevent PHI circles. If you have %phi = phi [0, ...], [%bo1, ...]; ...; %bo0 = add %phi, 1; ...; %bo1 = add %bo0, %bo0 there is a circle but of size 3, which should not cause this check to trigger.

That said, do we really need it? If so, do we have a test to show that?

5227

I don't think we should do that. The Attributor will fix states without dependences and this seems risky given that the genericValueTraversal could look phi nodes and selects and stuff.

5278

As above.

6067

I'm not even sure we need this. Shouldn't AAValueSimplify call AAValueConstantRange if necessary?
Instead, I would create AAValueConstantRange for calls with integer return type (and add a TODO for load instructions). Here we can come up with metadata which is otherwise not derived.

llvm/test/Transforms/Attributor/lvi-after-jumpthreading.ll
34 ↗(On Diff #235224)

I know I suggested this test but now I wonder:
The LVI test prints some internal stuff after it runs jump-threading, which we have not integrated yet. We should either add a FIXME to integrate jump-threading, add some way of testing the range analysis e.g., through an array access that we can prove dereferenceable, or remove the test.

Now after writing this I realize we actually optimize the branch away! So we should keep the test but maybe add a pointer access with a FIXME for dereferencebaility anyway somewhere.

uenoku marked 3 inline comments as done.Dec 26 2019, 12:49 AM
uenoku added inline comments.
llvm/lib/Transforms/IPO/Attributor.cpp
4909

Will do.

4981

I didn't merge the SCEV and LVI information into initialization because I want to utilize the position where the value is used(=CtxI). I mean,

int abs(int u){
  if(u>=0){
    return u;
  }
  else 
    return -u;
}

In this case, the argument u has a different known range in each uses.
Do you have a better way to handle these kinds of flow- and context-sensitive information?

5218

I agree that it seems we don't this check. I'll remove.

jdoerfert added inline comments.Dec 26 2019, 8:46 AM
llvm/lib/Transforms/IPO/Attributor.cpp
4981

We can do both, right? I mean you already call the SCEV in some initialize I think. Let's call both in all initializations with the getCtxI() context. If the context changes I'm fine with calling it again though.

uenoku marked an inline comment as done.Dec 26 2019, 9:03 AM
uenoku added inline comments.
llvm/lib/Transforms/IPO/Attributor.cpp
4981

I understand. Thanks.

uenoku updated this revision to Diff 235517.EditedDec 29 2019, 12:03 PM
uenoku marked 9 inline comments as done.
uenoku edited the summary of this revision. (Show Details)

Address comments.

  • add a helper function for floating value updateImpl
  • add test
    • range metadata (range.ll @test0-range-check)
    • dereferenceable (dereferenceable-1.ll @fill_range_inbounds/not_inbounds)
  • query to AAValueConstantRange when AAValueSimplify gives up
  • call LVI and SCEV in initialize as known information
  • create AA for integer returned value
uenoku marked 5 inline comments as done.Dec 29 2019, 12:11 PM
uenoku added inline comments.
llvm/lib/Transforms/IPO/Attributor.cpp
3973

I'll add a comment here later.

5055

I create a test for metadata(range.ll/test0-range-check.ll)

jdoerfert accepted this revision.Dec 29 2019, 12:20 PM

LGTM. Once we use AAValueSimplify more aggressively in other AAs to get simplified values instead of the ones in the IR, this will be triggered automatically :)

llvm/lib/Transforms/IPO/Attributor.cpp
4988

Nit: The second TODO is outdated.

This revision is now accepted and ready to land.Dec 29 2019, 12:20 PM
uenoku updated this revision to Diff 235745.Dec 31 2019, 9:51 PM
uenoku marked an inline comment as done.

Minor update.

uenoku updated this revision to Diff 235747.Dec 31 2019, 10:17 PM

Remove outdated todos.

This revision was automatically updated to reflect the committed changes.

This breaks top-of-tree from building and testing itself with optimizations and without asserts. Can we revert this for now?

FAIL: LLVM :: Transforms/Attributor/liveness.ll (43906 of 60305)
******************** TEST 'LLVM :: Transforms/Attributor/liveness.ll' FAILED ********************
Script:
--
: 'RUN: at line 2';   /tmp/_update_lc/r/bin/opt -attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=4 -S < /home/dave/s/lp/llvm/test/Transforms/Attributor/liveness.ll | /tmp/_update_lc/r/bin/FileCheck /home/dave/s/lp/llvm/test/Transforms/Attributor/liveness.ll --check-prefixes=CHECK,OLDPM
: 'RUN: at line 3';   /tmp/_update_lc/r/bin/opt -passes=attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=4 -S < /home/dave/s/lp/llvm/test/Transforms/Attributor/liveness.ll | /tmp/_update_lc/r/bin/FileCheck /home/dave/s/lp/llvm/test/Transforms/Attributor/liveness.ll --check-prefixes=CHECK,NEWPM
--
Exit Code: 2

Command Output (stderr):
--
Called function must be a pointer!
  call addrspace(1792) void <badref>(i32* nofree readnone undef) #10
in function useless_arg_almost_sink
LLVM ERROR: Broken function found, compilation aborted!
FileCheck error: '-' is empty.
FileCheck command line:  /tmp/_update_lc/r/bin/FileCheck /home/dave/s/lp/llvm/test/Transforms/Attributor/liveness.ll --check-prefixes=CHECK,OLDPM
phosek added a subscriber: phosek.Jan 2 2020, 4:54 PM

We're seeing a slightly different test failure on aarch64-linux-gnu:

FAIL: LLVM :: Transforms/Attributor/liveness.ll (27821 of 35033)
******************** TEST 'LLVM :: Transforms/Attributor/liveness.ll' FAILED ********************
Script:
--
: 'RUN: at line 2';   /b/s/w/ir/k/recipe_cleanup/clange57EIw/llvm_build_dir/bin/opt -attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=4 -S < /b/s/w/ir/k/llvm-project/llvm/test/Transforms/Attributor/liveness.ll | /b/s/w/ir/k/recipe_cleanup/clange57EIw/llvm_build_dir/bin/FileCheck /b/s/w/ir/k/llvm-project/llvm/test/Transforms/Attributor/liveness.ll --check-prefixes=CHECK,OLDPM
: 'RUN: at line 3';   /b/s/w/ir/k/recipe_cleanup/clange57EIw/llvm_build_dir/bin/opt -passes=attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-annotate-decl-cs -attributor-max-iterations=4 -S < /b/s/w/ir/k/llvm-project/llvm/test/Transforms/Attributor/liveness.ll | /b/s/w/ir/k/recipe_cleanup/clange57EIw/llvm_build_dir/bin/FileCheck /b/s/w/ir/k/llvm-project/llvm/test/Transforms/Attributor/liveness.ll --check-prefixes=CHECK,NEWPM
--
Exit Code: 2

Command Output (stderr):
--
opt: /b/s/w/ir/k/llvm-project/llvm/lib/Transforms/IPO/Attributor.cpp:6475: llvm::ChangeStatus llvm::Attributor::rewriteFunctionSignatures(): Assertion `OldFn->getNumUses() == 0 && "Unexpected leftover uses!"' failed.
FileCheck error: '-' is empty.
FileCheck command line:  /b/s/w/ir/k/recipe_cleanup/clange57EIw/llvm_build_dir/bin/FileCheck /b/s/w/ir/k/llvm-project/llvm/test/Transforms/Attributor/liveness.ll --check-prefixes=CHECK,OLDPM
uenoku added a comment.EditedJan 2 2020, 6:06 PM

I have reverted the commit. Sorry for the mess.

I couldn't reproduce those test failures locally.

uenoku added a comment.Jan 3 2020, 1:10 AM

It seems the failure occurs when old pm is used.
I couldn't find what is causing this error.

@jdoerfert Could you take a look at this?

It seems the failure occurs when old pm is used.
I couldn't find what is causing this error.

@jdoerfert Could you take a look at this?

opt: /b/s/w/ir/k/llvm-project/llvm/lib/Transforms/IPO/Attributor.cpp:6475: llvm::ChangeStatus llvm::Attributor::rewriteFunctionSignatures(): Assertion `OldFn->getNumUses() == 0 && "Unexpected leftover uses!"' failed.

Should have been fixed by rGd2d2fb19f7ea.

Called function must be a pointer! call addrspace(1792) void <badref>(i32* nofree readnone undef) #10

I haven't seen this running the test suite. I'll apply your patch and take a look.

uenoku reopened this revision.Jan 4 2020, 12:02 AM

It seems the failure occurs when old pm is used.
I couldn't find what is causing this error.

@jdoerfert Could you take a look at this?

opt: /b/s/w/ir/k/llvm-project/llvm/lib/Transforms/IPO/Attributor.cpp:6475: llvm::ChangeStatus llvm::Attributor::rewriteFunctionSignatures(): Assertion `OldFn->getNumUses() == 0 && "Unexpected leftover uses!"' failed.

Should have been fixed by rGd2d2fb19f7ea.

Called function must be a pointer! call addrspace(1792) void <badref>(i32* nofree readnone undef) #10

I haven't seen this running the test suite. I'll apply your patch and take a look.

Thank you.

This revision is now accepted and ready to land.Jan 4 2020, 12:02 AM
jdoerfert requested changes to this revision.Jan 8 2020, 11:19 AM

I'll push some fixes that should address the issues people saw (I hope) but there is at least one bug that the test suite exposed.

For the code below we should not replace the %add with 1. Can you look into that and add the test?

define dso_local i32 @test() {
entry:
  %call = call i32 @rec(i32 0)
  ret i32 %call
}
define internal i32 @rec(i32 %depth) {
entry:
  %call = call i32 @foo(i32 %depth)
  %tobool = icmp ne i32 %call, 0
  br i1 %tobool, label %if.then, label %if.end

if.then:                                          ; preds = %entry
  br label %return

if.end:                                           ; preds = %entry
  %cmp = icmp slt i32 %depth, 10
  br i1 %cmp, label %if.then1, label %if.end3

if.then1:                                         ; preds = %if.end
  %add = add nsw i32 %depth, 1
  %call2 = call i32 @rec(i32 %add)
  br label %if.end3

if.end3:                                          ; preds = %if.then1, %if.end
  br label %return

return:                                           ; preds = %if.end3, %if.then
  %retval.0 = phi i32 [ 0, %if.then ], [ 1, %if.end3 ]
  ret i32 %retval.0
}
declare dso_local i32 @foo(i32)
This revision now requires changes to proceed.Jan 8 2020, 11:19 AM
uenoku updated this revision to Diff 237940.EditedJan 14 2020, 5:06 AM

Add the test. Sorry for the delay.

For the code below we should not replace the %add with 1. Can you look into that and add the test?

As far as I see it, %add is not replaced.

This revision is now accepted and ready to land.Jan 14 2020, 12:43 PM
This revision was automatically updated to reflect the committed changes.