This is an archive of the discontinued LLVM Phabricator instance.

[ValueTracking] Use assumptions in computeConstantRange.
ClosedPublic

Authored by fhahn on Mar 15 2020, 5:42 AM.

Details

Summary

This patch updates computeConstantRange to optionally take an assumption
cache as argument and use the available assumptions to limit the range
of the result.

Currently this is limited to assumptions that are comparisons.

Diff Detail

Event Timeline

fhahn created this revision.Mar 15 2020, 5:42 AM
Herald added a project: Restricted Project. · View Herald TranscriptMar 15 2020, 5:42 AM
Herald added a subscriber: hiraditya. · View Herald Transcript
nikic added a comment.Mar 15 2020, 8:12 AM

Can you please provide some context on where this is going to be used? Generally LVI should be quite good at handling these kinds of assumes.

Can you please provide some context on where this is going to be used? Generally LVI should be quite good at handling these kinds of assumes.

Sure, I've linked D76194, which uses it in BasicAA.

nikic added a comment.Mar 16 2020, 1:20 AM

Thanks for providing the context, clearly LVI can't help there...

This looks fine to me technically, only concern is whether this carries its weight in compile time. Together with the linked change, this is a 0.5% regression.

llvm/lib/Analysis/ValueTracking.cpp
6130

Should we also be passing the DT through?

Side note: https://github.com/llvm/llvm-project/blob/56aed6144a16cdd71e03e5855b19dab1fe9331e6/llvm/lib/Analysis/ValueTracking.cpp#L604-L609 needs to be updated to use the new block local dominance checks, instead of doing an instruction scan.

6138

We may need to start passing a Depth parameter through, as this is now recursive. Though, as you don't pass through AC/CtxI here, recursion is implicitly limited to two levels.

llvm/unittests/Analysis/ValueTrackingTest.cpp
1056

Possibly worth checking a contradicting assumption? Which would result in an empty range.

fhahn marked 3 inline comments as done.Mar 16 2020, 6:23 AM

Thanks for providing the context, clearly LVI can't help there...

This looks fine to me technically, only concern is whether this carries its weight in compile time.

Together with the linked change, this is a 0.5% regression.

That's a neat site. It looks very useful. Do you know if there's any more information about the site? Is there a way to also check the patches together with D76228?

With respect to the regression, I am a bit surprised that there are seem to be quite a few assumptions encoded using assume() from clang. I'll check.

llvm/lib/Analysis/ValueTracking.cpp
6130

Should we also be passing the DT through?

We certainly can. Maybe best done as a follow-up?

Side note: https://github.com/llvm/llvm-project/blob/56aed6144a16cdd71e03e5855b19dab1fe9331e6/llvm/lib/Analysis/ValueTracking.cpp#L604-L609 needs to be updated to use the new block local dominance checks, instead of doing an instruction scan.

Agreed, I had the same though when looking at the code for isValudAssumeForContext. I've put it up at D76228.

fhahn updated this revision to Diff 250548.Mar 16 2020, 6:25 AM

Add depth parameter & test case with contradictions.

nikic accepted this revision.Mar 17 2020, 4:11 PM

Thanks for providing the context, clearly LVI can't help there...

This looks fine to me technically, only concern is whether this carries its weight in compile time.

Together with the linked change, this is a 0.5% regression.

That's a neat site. It looks very useful. Do you know if there's any more information about the site? Is there a way to also check the patches together with D76228?

With respect to the regression, I am a bit surprised that there are seem to be quite a few assumptions encoded using assume() from clang. I'll check.

If you push a branch that starts with perf/ to your fork, it should get picked up. I've also done a run with the additional patch: Individual commits and all three combined.

Turns out the change to isValidAssumeForContext() in D76228 is neutral, I guess we don't exercise that code path much. This patch itself is a slight regression (the function is called often enough that the extra params and checks make a measurable difference). The BasicAA patch is a bit larger regression. I doubt this has anything to do with the assume handling, it's probably just the cost of the extra computeConstantRange() calls in a common analysis.

Anyway, this patch looks fine to me technically, so LGTM.

This revision is now accepted and ready to land.Mar 17 2020, 4:11 PM
fhahn added a comment.Apr 1 2020, 4:24 AM

That's a neat site. It looks very useful. Do you know if there's any more information about the site? Is there a way to also check the patches together with D76228?

With respect to the regression, I am a bit surprised that there are seem to be quite a few assumptions encoded using assume() from clang. I'll check.

If you push a branch that starts with perf/ to your fork, it should get picked up. I've also done a run with the additional patch: Individual commits and all three combined.

Awesome I tried with a branch and it seems to get picked up.

Did you consider open-sourcing the scripts/tooling, e.g. as part of LNT/test-suite/llvm-zorg or as standalone project? It would be great if it would be possible to spin up separate instances, to not overload lvm-compile-time-tracker.com ;)

This revision was automatically updated to reflect the committed changes.