Page MenuHomePhabricator

Improve BasicAA Pass Using zext Information

Authored by njw45 on Sep 28 2014, 12:06 PM.


  1. Fixes a bug when calculating the offset in GetLinearExpression. The code previously used zext to extend the offset, so negative offsets were converted to large positive ones.
  2. Enhance aliasGEP to deduce that, if the difference between two GEP allocations is positive and all the variables that govern the offset are also positive (i.e. the offset is strictly after the higher base pointer), then allocations that fit in the gap between the two base pointers are NoAlias.

Diff Detail

Event Timeline

njw45 updated this revision to Diff 14148.Sep 28 2014, 12:06 PM
njw45 retitled this revision from to Improve BasicAA Pass Using zext Information.
njw45 updated this object.
njw45 edited the test plan for this revision. (Show Details)
njw45 added a subscriber: test.
njw45 updated this object.Sep 28 2014, 12:07 PM
njw45 edited the test plan for this revision. (Show Details)
hfinkel added a subscriber: Unknown Object (MLST).Sep 28 2014, 3:09 PM
hfinkel added a subscriber: hfinkel.
hfinkel added inline comments.

Start sentence with a capital w (similar with other comments below).


To note a possible follow-up, we might also be able to determine this by using ComputeSignBit from ValueTracking.h


Add a space in between the if and the (


I think you can remove the ("don't know") next to MayAlias.

More importantly, please also explain in the comment what the loop below actually checks and why that ensures the condition you explain above.

Also, an example of this would be helpful.


Space after the if.

njw45 updated this revision to Diff 14169.Sep 29 2014, 9:03 AM

Updating D5514: Improve BasicAA Pass Using zext Information

njw45 added a comment.Sep 29 2014, 9:05 AM

@hfinkel Thanks for the review - I've updated the patch to fix this issues you mentioned.

hfinkel added inline comments.Sep 29 2014, 11:06 AM

As you've written the example, %phi and %idx don't alias, because %idx == %phi+1. If you take out the add and store the original value (or don't update*%somewhere at all), then they will alias.


When you see "we can see that", you mean that without this check we'd return NoAlias, right? That does not seem right. Without this patch (current trunk), if I take this function:

define void @test1(i64* noalias %somewhere, i32* noalias %memory) {
  br label %for.body

   %phi = phi i32* [%idx, %for.body], [null, %entry]
   %i = load i64* %somewhere
   %idx = getelementptr inbounds i32* %memory, i64 %i
   %i.plus1 = add nsw nuw i64 %i, 1
   store i64 %i.plus1, i64* %somewhere
   br label %for.body

and run it through:

opt < -basicaa -aa-eval -print-all-alias-modref-info -disable-output

I get:

Function: test1: 4 pointers, 0 call sites
  NoAlias:      i32* %memory, i64* %somewhere
  NoAlias:      i32* %phi, i64* %somewhere
  MayAlias:     i32* %memory, i32* %phi
  NoAlias:      i32* %idx, i64* %somewhere
  PartialAlias: i32* %idx, i32* %memory
  MayAlias:     i32* %idx, i32* %phi

which already gives "MayAlias: i32* %idx, i32* %phi".

In short, I'm still not entirely sure I understand the problem you're trying to fix here.


What do you mean by "tightened" here?


Space after the if.

njw45 added a comment.Sep 30 2014, 6:38 AM

@hfinkel - thanks for your patience, I understand it now. I was basically trying to re-invent isValueEqualInPotentialCycles, so I've cut that bit completely from the patch. I've also added the ComputeSignBit check you suggested, and a test using lshr to demonstrate that it works.

hfinkel accepted this revision.Sep 30 2014, 3:15 PM
hfinkel added a reviewer: hfinkel.

LGTM, thanks! Do you have commit access?

This revision is now accepted and ready to land.Sep 30 2014, 3:15 PM
njw45 added a comment.Sep 30 2014, 3:38 PM

No, I don't -

hfinkel closed this revision.Sep 30 2014, 3:55 PM


njw45 edited the test plan for this revision. (Show Details)Oct 4 2014, 10:26 AM
njw45 edited edge metadata.