This is an archive of the discontinued LLVM Phabricator instance.

[BasicAA] Non-equal indices in a GEP of a SequentialType don't overlap

Authored by jmolloy on Sep 11 2015, 6:02 AM.



If the final indices of two GEPs can be proven to not be equal, and the GEP is of a SequentialType (not a StructType), then the two GEPs do not alias.

We have to be careful not to return a false negative when dealing with indices into array types that are larger than the number of elements in the array - in this case there can be a partial alias between the GEPs (it breaks our "must" or "no" assumption). With this patch we're quite conservative about this case and only proceed if all intermediate indices are identical between the two GEPs.

Diff Detail


Event Timeline

jmolloy updated this revision to Diff 34547.Sep 11 2015, 6:02 AM
jmolloy retitled this revision from to [BasicAA] Non-equal indices in a GEP of a SequentialType don't overlap.
jmolloy updated this object.
jmolloy added reviewers: majnemer, hfinkel, chandlerc.
jmolloy set the repository for this revision to rL LLVM.
jmolloy added a subscriber: llvm-commits.
hfinkel accepted this revision.Sep 22 2015, 2:17 PM
hfinkel edited edge metadata.

There are some comment changes, but otherwise, LGTM.


We don't seem to know that here, only below, because of how you've modified the C1,C2 check above. Here, we know only that we don't have equal constants.


final 'that' -> 'the array/pointer', or similar, to eliminate the 'that that'

This revision is now accepted and ready to land.Sep 22 2015, 2:17 PM
jmolloy closed this revision.Oct 26 2015, 3:29 AM