This is an archive of the discontinued LLVM Phabricator instance.

[BasicAA] Use known lower bounds for index values for size based check.
ClosedPublic

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

Details

Summary

Currently, BasicAA does not exploit information about value ranges of
indexes. For example, consider the 2 pointers %a = %base and
%b = %base + %stride below, assuming they are used to access 4 elements.

If we know that %stride >= 4, we know the accesses do not alias. If
%stride is a constant, BasicAA currently gets that. But if the >= 4
constraint is encoded using an assume, it misses the NoAlias.

This patch extends DecomposedGEP to include an additional MinOtherOffset
field, which tracks the constant offset similar to the existing
OtherOffset, which the difference that it also includes non-negative
lower bounds on the range of the index value. When checking if the
distance between 2 accesses exceeds the access size, we can use this
improved bound.

For now this is limited to using non-negative lower bounds for indices,
as this conveniently skips cases where we do not have a useful lower
bound (because it is not constrained). We potential miss out in cases
where the lower bound is constrained but negative, but that can be
exploited in the future.

Diff Detail

Event Timeline

fhahn created this revision.Mar 15 2020, 5:49 AM
Herald added a project: Restricted Project. · View Herald TranscriptMar 15 2020, 5:49 AM
asbirlea accepted this revision.May 21 2020, 5:25 PM

lgtm.

llvm/lib/Analysis/BasicAliasAnalysis.cpp
613

s/We we find/If we find

This revision is now accepted and ready to land.May 21 2020, 5:25 PM
fhahn updated this revision to Diff 265777.May 22 2020, 11:10 AM
fhahn marked an inline comment as done.

lgtm.

Thank you very much for taking a look! Rebased and comment addressed.

This revision was automatically updated to reflect the committed changes.
nikic added a subscriber: nikic.May 30 2020, 1:48 PM

This change caused a 0.5% compile-time regression. The largest regression is 1.6% for lencod (with the q_matrix.c file at 3-4%). As the code-size changes are <= 0.01%, this optimization does not seem to trigger much in practice (and not at all for lencod). This seems like a somewhat unfavorable trade-off between compile-time and optimization power.

fhahn added a comment.May 31 2020, 5:19 AM

This change caused a 0.5% compile-time regression. The largest regression is 1.6% for lencod (with the q_matrix.c file at 3-4%). As the code-size changes are <= 0.01%, this optimization does not seem to trigger much in practice (and not at all for lencod). This seems like a somewhat unfavorable trade-off between compile-time and optimization power.

Hm yeah that does not look great. I'll check to see if there's something we can do to limit the amount of extra work.

Carrot added a subscriber: Carrot.Jun 19 2020, 12:22 PM

@fhahn, could you help to take a look at https://bugs.llvm.org/show_bug.cgi?id=46335? It may be caused by this patch.

fhahn added a comment.Jun 19 2020, 1:23 PM

@fhahn, could you help to take a look at https://bugs.llvm.org/show_bug.cgi?id=46335? It may be caused by this patch.

Oh right, from the bug description I initially thought the issue is actually how another pass uses the result. But I was planning on taking a closer look at the compile-time impact and reverting the patch in the meantime. I'll take a closer look in the following days.

I think it would be best to revert while investigating; it looks like it would unblock folks, and it's a reasonably small change to recommit.

fhahn added a comment.Jun 22 2020, 8:45 AM

I've reverted it for now: 9a7d80a32c8d