Page MenuHomePhabricator

[BasicAliasAnalysis] Fix computation for arrays > half of address space
Needs ReviewPublic

Authored by eush on Mar 21 2019, 8:46 AM.

Details

Summary

This fixes alias analysis rules to support arrays larger than half of
the address space by teaching BasicAliasAnalysis about offset
wraparound.

The problem is that BasicAliasAnalysis reduces all pointer offsets to
APInt with PointerSize bits (by calling adjustToPointerSize), but then
performs arithmetic operations in APInt with MaxPointerSize bits. In the
case when PointerSize is not equal to MaxPointerSize, this leads to all
offsets larger than half of the address space size being treated as
negative integers, and certain heuristics producing incorrect results if
such offsets are involved.

This fixes PR34344 and the test reported on llvm-dev in 118901 [1].

[1]: http://lists.llvm.org/pipermail/llvm-dev/2017-November/118901.html

Diff Detail

Event Timeline

eush created this revision.Mar 21 2019, 8:46 AM
Herald added a project: Restricted Project. · View Herald TranscriptMar 21 2019, 8:46 AM
Herald added a subscriber: jdoerfert. · View Herald Transcript
eush edited the summary of this revision. (Show Details)Mar 21 2019, 8:48 AM
eush retitled this revision from [BasicAliasAnalysis] Fix computation for large arrays to [BasicAliasAnalysis] Fix computation for arrays > half of address space.
bjope added a subscriber: uabelho.Apr 11 2019, 12:17 AM
bjope added a subscriber: bjope.
hfinkel added inline comments.Apr 12 2019, 12:01 PM
lib/Analysis/BasicAliasAnalysis.cpp
1453

You use:

(GEP1BaseOffset.isNonNegative() ? GEP1BaseOffset : GEP1BaseOffset + ASSize)

or it's negation, several times here. Can we add a variable, or lambda function, etc. to make this repetition unnecessary?

1518

Can you please document better what's going on here?

test/Analysis/BasicAA/cs-cs.ll
276

Why did this change?

The change doesn't look wrong, but it's also unrelated to the half-the-address-space issue (AFAIKT, this test has 32-bit pointers), so it will be useful to understand what fixed this.

eush updated this revision to Diff 200016.May 17 2019, 4:15 AM

I updated the diff as per the comments.

  • [Basicaliasanalysis] Factor out modular arithmetic to reduce repetition
  • [BasicAliasAnalysis] Expand the comments on MaxVarOffset
eush marked 2 inline comments as done.May 17 2019, 4:30 AM
eush added inline comments.
test/Analysis/BasicAA/cs-cs.ll
276

This change is caused by the fact that the wraparound semantics implemented in
this diff makes %p and %q MayAlias aliases of each other. The object
pointed to by %q has unknown size, and with wraparound it can very well span
until %p.

Previously, without wraparound, the object could only span until the end of
the address space.