OSDN Git Service

[BasicAA] Use known lower bounds for index values for size based check.
authorFlorian Hahn <flo@fhahn.com>
Sat, 30 May 2020 15:20:42 +0000 (16:20 +0100)
committerFlorian Hahn <flo@fhahn.com>
Sat, 30 May 2020 15:20:42 +0000 (16:20 +0100)
commitd99a1848c4f8ca164c0c0768e10eafc850b2a68a
tree04fb9baba3a8dafed4cea22e6c9d9558f370395b
parente6aba43cda848f4a8cfa5ce9f174b77def10e9df
[BasicAA] Use known lower bounds for index values for size based check.

Currently, BasicAA does not exploit information about value ranges of
indexes. For example, consider the 2 pointers %a = %base and
%b = %base + %stride below, assuming they are used to access 4 elements.

If we know that %stride >= 4, we know the accesses do not alias. If
%stride is a constant, BasicAA currently gets that. But if the >= 4
constraint is encoded using an assume, it misses the NoAlias.

This patch extends DecomposedGEP to include an additional MinOtherOffset
field, which tracks the constant offset similar to the existing
OtherOffset, which the difference that it also includes non-negative
lower bounds on the range of the index value. When checking if the
distance between 2 accesses exceeds the access size, we can use this
improved bound.

For now this is limited to using non-negative lower bounds for indices,
as this conveniently skips cases where we do not have a useful lower
bound (because it is not constrained). We potential miss out in cases
where the lower bound is constrained but negative, but that can be
exploited in the future.

Reviewers: sanjoy, hfinkel, reames, asbirlea

Reviewed By: asbirlea

Differential Revision: https://reviews.llvm.org/D76194
llvm/include/llvm/Analysis/BasicAliasAnalysis.h
llvm/lib/Analysis/BasicAliasAnalysis.cpp
llvm/test/Analysis/BasicAA/assume-index-positive.ll
llvm/test/Analysis/BasicAA/bug.23626.ll