[llvm-bugs] [Bug 33837] New: SCEV AA assumes inbounds and non-negative offsets

[via llvm-bugs]

https://bugs.llvm.org/show_bug.cgi?id=33837

            Bug ID: 33837
           Summary: SCEV AA assumes inbounds and non-negative offsets
           Product: libraries
           Version: trunk
          Hardware: All
                OS: All
            Status: NEW
          Keywords: miscompilation
          Severity: normal
          Priority: P
         Component: Global Analyses
          Assignee: unassignedbugs at nondot.org
          Reporter: nunoplopes at sapo.pt
                CC: dan433584 at gmail.com, davide at freebsd.org,
                    dberlin at dberlin.org, gil.hur at sf.snu.ac.kr,
                    hfinkel at anl.gov, jeehoon.kang at sf.snu.ac.kr,
                    juneyoung.lee at sf.snu.ac.kr, llvm-bugs at lists.llvm.org,
                    regehr at cs.utah.edu, sanjoy at playingwithpointers.com

The last rule of SCEV AA to prove no-alias is the following:
if a = x + ...
and no-alias(x, -1, b, s_b)

then no-alias(a, s_a, b, s_b)

where s_a = access size for a


The code is the following:
  if ((AO && AO != LocA.Ptr) || (BO && BO != LocB.Ptr))
    if (alias(MemoryLocation(AO ? AO : LocA.Ptr,
                             AO ? +MemoryLocation::UnknownSize : LocA.Size,
                             AO ? AAMDNodes() : LocA.AATags),
              MemoryLocation(BO ? BO : LocB.Ptr,
                             BO ? +MemoryLocation::UnknownSize : LocB.Size,
                             BO ? AAMDNodes() : LocB.AATags)) == NoAlias)
      return NoAlias;


This is incorrect for the following case:
 1) AO == null || BO == null  (so, we only get an addition for one of the
pointers)
 2) the GEP has no inbounds attribute *OR* the offset (the ... in "a = x +
...") is negative.

I don't have a reproducible test case, but I proved in Z3 that if one of the
above conditions doesn't hold then the code is correct. And if both hold, then
SCEV AA will prove no-alias incorrectly.

So the fix is (for the case AO == null || BO == null):
 - check that the GEP originating the SCEV add expression has inbounds
attribute
 - *and* check that the offset is non-negative

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20170718/e916574c/attachment.html>