Page MenuHomePhabricator

[BasicAA] An inbounds GEP and an alloca can't alias if the base of the GEP would point "below" the alloca
ClosedPublic

Authored by mkuper on May 20 2016, 3:04 PM.

Details

Summary

This is another attempt to handle situations similar to http://reviews.llvm.org/D8487 , although it won't work for that particular case (because this doesn't appear to be legal for arguments).

The basic idea is that given this code:

define void @struct() {
  %alloca = alloca %struct
  %alloca.i32 = bitcast %struct* %alloca to i32*
  %random = call i32* @random.i32(i32* %alloca.i32)
  %f0 = getelementptr inbounds %struct, %struct* %alloca, i32 0, i32 0
  %p1 = getelementptr inbounds i32, i32* %random, i32 1
  ret void
}

%f0 and %p1 can not alias.
If they did alias, then the underlying object of %p1 - and thus, of %random - must be %alloca. But that would make %random out of bounds (since it'd have a negative offset) w.r.t %alloca, and since the GEP is inbounds, we can just assume noalias. The same logic probably holds for a GlobalVariable (which isn't a GlobalAlias), but not for other identified objects, like arguments, since a negative offset from a noalias argument may still be inbounds. I'd rather do this for Alloca first, and add GV in a separate commit.

The interface is pretty ugly, perhaps wrapping the results of DecomposeGEPExpression in a class and passing that around would make it better, but I'm not entirely sure. Thoughts?

Diff Detail

Repository
rL LLVM

Event Timeline

mkuper updated this revision to Diff 57989.May 20 2016, 3:04 PM
mkuper retitled this revision from to [BasicAA] An inbounds GEP and an alloca can't alias if the base of the GEP would point "below" the alloca.
mkuper updated this object.
mkuper added reviewers: nlewycky, qcolombet, hfinkel.
mkuper added subscribers: llvm-commits, davidxl, wmi, dberlin.
davidxl added inline comments.May 20 2016, 10:42 PM
lib/Analysis/BasicAliasAnalysis.cpp
346 ↗(On Diff #57989)

Document parameter BaseStructOffs, and BaseNonStructOffs.

954 ↗(On Diff #57989)

Probably add an example in C form to demonstrate it. Also document key parameters of the method.

968 ↗(On Diff #57989)

Since this method does not need to update the two limits, it is better to move their checks out of line before the call. i.e.:

if (!GEPMaxLookupReached && !AllocaMaxLookupReached && isGEPBaseAtNegativeOffset(..))
    return NoAlias;

This will help make the interface cleaner.

The limit check can also be combined with the next call:

if (!GEPMaxLookupReached && !AllocaMa... ) {
     if (!isGEP....) 
        return NoAlias;
      if (!isGEP...)
         return NoAlias;
   }
1035 ↗(On Diff #57989)

Perhaps passing the GEPVariableIndices directly to the callee.

Thanks, David!

lib/Analysis/BasicAliasAnalysis.cpp
346 ↗(On Diff #57989)

Right, thanks.

954 ↗(On Diff #57989)

Will do, except that I really think an IR example would be more appropriate here.

968 ↗(On Diff #57989)

I actually wrote that with the checks out of line first, didn't seem prettier. :-\

The problem is that the way checkGEP is currently written, there's no clear separation between (1) cases when the second argument is a GEP or not, and (2) cases when the lookup failure should cause it to bail or not. So I have to add extra checks (in the second option you suggest, an extra isGEP check, I can't put the entire isGEP code under a look success check) no matter what,

1035 ↗(On Diff #57989)

Ditto - I started out with that, and changed it to passing a bool because that's all the helper cares about. Neither version is pretty.

What do you think about wrapping the entire decomposition result in a struct?

davidxl added inline comments.May 23 2016, 10:56 AM
lib/Analysis/BasicAliasAnalysis.cpp
954 ↗(On Diff #57989)

You can treat the example as C like pseudo language to make the description more 'high level' and easier to read.

968 ↗(On Diff #57989)

ok

1035 ↗(On Diff #57989)
  • What do you think about wrapping the entire decomposition result in a struct?

I think that will be cleaner -- enhancing the interface in the future does not require updating all use sites -- perhaps extract that as a NFC refactoring patch.

mkuper updated this revision to Diff 58141.May 23 2016, 1:15 PM

Wrapped the decomposition results in a class, hopefully resulting in a cleaner interface.

davidxl added inline comments.May 23 2016, 1:55 PM
test/Analysis/BasicAA/negoffset.ll
46 ↗(On Diff #58141)

It is also good add a more complex case where we have nested structs/arrays when constant offsets of the accesses can be collapsed (also severs as tests for the new Decompose method)

something like:
struct Inner {

int inner_f1;
int inner_f2;

};

struct Outer {

int outer_f1;
int outer_f2;
struct inner Inner[10];

} Outer_p;

Outer_p[1].Inner[2].f1 vs some local access at offset 0
Outer_p[i].inner[2].f1 vs some local access at offset 0
Outer_p[i].Inner[j].f2 vs some local access at offst 0

mkuper updated this revision to Diff 58152.May 23 2016, 2:28 PM

Added a nested-struct test.
David, is this what you meant?

mkuper updated this revision to Diff 58167.May 23 2016, 3:42 PM

And now, with the right CHECK.

davidxl added inline comments.May 24 2016, 1:59 PM
lib/Analysis/BasicAliasAnalysis.cpp
355 ↗(On Diff #58167)

Also clear the var indices?

996 ↗(On Diff #58167)

Is the VarIndices.empty() check too restrictive?

struct A {

int a[2];
...

};

struct B {

int b1;
int b2;
int b3;

};

struct A a;
B *bp;

bp->b3 vs a.a[i] should produce no aliasing

998 ↗(On Diff #58167)

Extract this unrelated cleanup into separate patch.

1035 ↗(On Diff #58167)

separate out clean up code into different patch.

1085 ↗(On Diff #58167)

Ditto -- cleanup patch.

mkuper added inline comments.May 24 2016, 2:33 PM
lib/Analysis/BasicAliasAnalysis.cpp
355 ↗(On Diff #58167)

The original code doesn't do this, but I think you're right, it's an oversight. Will add.

996 ↗(On Diff #58167)

I'm not sure this is a good example.

Given:

struct __attribute__((packed)) A {
  int a[2]
  int b;
};

struct B {
  int b1;
  int b2;
  int b3;
};

struct A a;
B *bp = (B*)(&a);

I'm not sure we want, in -fno-strict-aliasing mode, to conclude that bp->b3 doesn't alias a.a[2] (which since the struct is packed, is a.b) - and so it may also alias a.a[i].

So, it seems to me that this could be less restrictive - but not too much. I think the most we can do if the alloca has variable indices, is take the maximum values that will still leave the whole gep inbounds w.r.t the alloca, and use that. If you think we actually run into those cases in practice, I can try to do that as a followup patch.

998 ↗(On Diff #58167)

It's not exactly unrelated.

The old code would call DecomposeGEPExpression on-demand only in code paths that were using the decomposition. Which was, I think, the majority - but not 100%. I needed to hoist the calls up - but I don't think that should go in as a stand-alone patch, since if it goes in without the rest of my changes, it incurs compile-time cost without much benefit.

If you think the clean-up is worth that, I can split it into a separate patch, but I'd rather not.

1035 ↗(On Diff #58167)

Same as above.

1085 ↗(On Diff #58167)

Same as above.

davidxl added inline comments.May 24 2016, 2:57 PM
lib/Analysis/BasicAliasAnalysis.cpp
996 ↗(On Diff #58167)

You are right that there is no 'inbound' guarantee for sub/inner array we can leverage here (even though accessing a.a[2] will lead to an error when build with -fsanitiize=undefined). Note GCC handles this with -fstrict-aliasing on.

998 ↗(On Diff #58167)

I mean the part that turns return MayAlias into assert -- not the hoisting part of the change. I think you just need to make that change (lgtm to that part which can be committed first) and rebase this patch. Or perhaps just leaves the FIXME in this patch (in the hoisted code and clean it up as a follow up.

mkuper added inline comments.May 24 2016, 3:14 PM
lib/Analysis/BasicAliasAnalysis.cpp
998 ↗(On Diff #58167)

Oh, yes, that makes perfect sense, but is slightly more annoying than it looks.

In fact, I already committed that as a separate patch a few days ago (r270268) - but reverted it because of unused variable warnings in non-asserts builds. I thought about recommitting it with dummy accesses to silence the warnings, but that seemed silly. (And I can't put the calls under NDEBUG, because only the result of the call is unused, but the output parameters aren't).

Leaving the FIXME in this patch could potentially change behavior, since it would return MayAlais on different code paths, even those that originally didn't care about the bound at all. On the other hand, it should never actually fire, so that should be fine.

I'm not too excited about either option, but if you prefer one of them to the whole thing going in in one piece, let me know which one.

mkuper updated this revision to Diff 58496.May 25 2016, 1:45 PM
dberlin accepted this revision.May 25 2016, 2:26 PM
dberlin added a reviewer: dberlin.

At this point, i think this looks pretty good to me.

This revision is now accepted and ready to land.May 25 2016, 2:26 PM
davidxl accepted this revision.May 25 2016, 2:27 PM
davidxl added a reviewer: davidxl.

lgtm too.

This revision was automatically updated to reflect the committed changes.