[BasicAA] Migrate "same base pointer" logic to decomposed GEPs
authorNikita Popov <nikita.ppv@gmail.com>
Sat, 5 Dec 2020 16:26:33 +0000 (17:26 +0100)
committerNikita Popov <nikita.ppv@gmail.com>
Sun, 6 Dec 2020 09:27:35 +0000 (10:27 +0100)
commit5e69e2ebad9db2af44362ebe1755c08af002798f
tree466da9fce143b9a23f63e10779f407426ef884d3
parent467b6699155ed1d0385eb4e0b03b1715a6d5f0e5
[BasicAA] Migrate "same base pointer" logic to decomposed GEPs

BasicAA has some special bit of logic for "same base pointer" GEPs
that performs a structural comparison: It only looks at two GEPs
with the same base (as opposed to two GEP chains with a MustAlias
base) and compares their indexes in a limited way. I generalized
part of this code in D91027, and this patch merges the remainder
into the normal decomposed GEP logic.

What this code ultimately wants to do is to determine that
gep %base, %idx1 and gep %base, %idx2 don't alias if %idx1 != %idx2,
and the access size fits within the stride.

We can express this in terms of a decomposed GEP expression with
two indexes scale*%idx1 + -scale*%idx2 where %idx1 != %idx2, and
some appropriate checks for sizes and offsets.

This makes the reasoning slightly more powerful, and more
importantly brings all the GEP logic under a common umbrella.

Differential Revision: https://reviews.llvm.org/D92723
llvm/include/llvm/Analysis/BasicAliasAnalysis.h
llvm/lib/Analysis/BasicAliasAnalysis.cpp
llvm/test/Analysis/BasicAA/fallback-mayalias.ll
llvm/test/Analysis/BasicAA/sequential-gep.ll