[Analysis] Make LocationSizes carry an 'imprecise' bit

There are places where we need to merge multiple LocationSizes of
different sizes into one, and get a sensible result.

There are other places

[Analysis] Make LocationSizes carry an 'imprecise' bit

There are places where we need to merge multiple LocationSizes of
different sizes into one, and get a sensible result.

There are other places where we want to optimize aggressively based on
the value of a LocationSizes (e.g. how can a store of four bytes be to
an area of storage that's only two bytes large?)

This patch makes LocationSize hold an 'imprecise' bit to note whether
the LocationSize can be treated as an upper-bound and lower-bound for
the size of a location, or just an upper-bound.

This concludes the series of patches leading up to this. The most recent
of which is r344108.

Fixes PR36228.

Differential Revision: https://reviews.llvm.org/D44748

llvm-svn: 344114

show more ...

Make LocationSize a proper Optional type; NFC

This is the second in a series of changes intended to make
https://reviews.llvm.org/D44748 more easily reviewable. Please see that
patch for more contex

Make LocationSize a proper Optional type; NFC

This is the second in a series of changes intended to make
https://reviews.llvm.org/D44748 more easily reviewable. Please see that
patch for more context. The first change being r344012.

Since I was requested to do all of this with post-commit review, this is
about as small as I can make this patch.

This patch makes LocationSize into an actual type that wraps a uint64_t;
users are required to call getValue() in order to get the size now. If
the LocationSize has an Unknown size (e.g. if LocSize ==
MemoryLocation::UnknownSize), getValue() will assert.

This also adds DenseMap specializations for LocationInfo, which required
taking two more values from the set of values LocationInfo can
represent. Hence, heavy users of multi-exabyte arrays or structs may
observe slightly lower-quality code as a result of this change.

The intent is for getValue()s to be very close to a corresponding
hasValue() (which is often spelled `!= MemoryLocation::UnknownSize`).
Sadly, small diff context appears to crop that out sometimes, and the
last change in DSE does require a bit of nonlocal reasoning about
control-flow. :/

This also removes an assert, since it's now redundant with the assert in
getValue().

llvm-svn: 344013

show more ...

Use locals instead of struct fields; NFC

This is one of a series of changes intended to make
https://reviews.llvm.org/D44748 more easily reviewable. Please see that
patch for more context.

Since I

Use locals instead of struct fields; NFC

This is one of a series of changes intended to make
https://reviews.llvm.org/D44748 more easily reviewable. Please see that
patch for more context.

Since I was requested to do all of this with post-commit review, this is
about as small as I can make it (beyond committing changes to these few
files separately, but they're incredibly similar in spirit, so...)

On its own, this change doesn't make a great deal of sense. I plan on
having a follow-up Real Soon Now(TM) to make the bits here make more
sense. :)

In particular, the next change in this series is meant to make
LocationSize an actual type, which you have to call .getValue() on in
order to get at the uint64_t inside. Hence, this change refactors code
so that:
- we only need to call the soon-to-come getValue() once in most cases,
and
- said call to getValue() happens very closely to a piece of code that
checks if the LocationSize has a value (e.g. if it's != UnknownSize).

llvm-svn: 344012

show more ...

[BasicAA] Don't assume tail calls with byval don't alias allocas

Summary:
Calls marked 'tail' cannot read or write allocas from the current frame
because the current frame might be destroyed by the

[BasicAA] Don't assume tail calls with byval don't alias allocas

Summary:
Calls marked 'tail' cannot read or write allocas from the current frame
because the current frame might be destroyed by the time they run.
However, a tail call may use an alloca with byval. Calling with byval
copies the contents of the alloca into argument registers or stack
slots, so there is no lifetime issue. Tail calls never modify allocas,
so we can return just ModRefInfo::Ref.

Fixes PR38466, a longstanding bug.

Reviewers: hfinkel, nlewycky, gbiv, george.burgess.iv

Subscribers: hiraditya, llvm-commits

Differential Revision: https://reviews.llvm.org/D50679

llvm-svn: 339636

show more ...

[BasicAA] Use PhiValuesAnalysis if available when handling phi alias

By using PhiValuesAnalysis we can get all the values reachable from a phi, so
we can be more precise instead of giving up when a

[BasicAA] Use PhiValuesAnalysis if available when handling phi alias

By using PhiValuesAnalysis we can get all the values reachable from a phi, so
we can be more precise instead of giving up when a phi has phi operands. We
can't make BaseicAA directly use PhiValuesAnalysis though, as the user of
BasicAA may modify the function in ways that PhiValuesAnalysis can't cope with.

For this optional usage to work correctly BasicAAWrapperPass now needs to be not
marked as CFG-only (i.e. it is now invalidated even when CFG is preserved) due
to how the legacy pass manager handles dependent passes being invalidated,
namely the depending pass still has a pointer to the now-dead dependent pass.

Differential Revision: https://reviews.llvm.org/D44564

llvm-svn: 338242

show more ...

llvm: Add support for "-fno-delete-null-pointer-checks"

Summary:
Support for this option is needed for building Linux kernel.
This is a very frequently requested feature by kernel developers.

More

llvm: Add support for "-fno-delete-null-pointer-checks"

Summary:
Support for this option is needed for building Linux kernel.
This is a very frequently requested feature by kernel developers.

More details : https://lkml.org/lkml/2018/4/4/601

GCC option description for -fdelete-null-pointer-checks:
This Assume that programs cannot safely dereference null pointers,
and that no code or data element resides at address zero.

-fno-delete-null-pointer-checks is the inverse of this implying that
null pointer dereferencing is not undefined.

This feature is implemented in LLVM IR in this CL as the function attribute
"null-pointer-is-valid"="true" in IR (Under review at D47894).
The CL updates several passes that assumed null pointer dereferencing is
undefined to not optimize when the "null-pointer-is-valid"="true"
attribute is present.

Reviewers: t.p.northover, efriedma, jyknight, chandlerc, rnk, srhines, void, george.burgess.iv

Reviewed By: efriedma, george.burgess.iv

Subscribers: eraman, haicheng, george.burgess.iv, drinkcat, theraven, reames, sanjoy, xbolva00, llvm-commits

Differential Revision: https://reviews.llvm.org/D47895

llvm-svn: 336613

show more ...

Implement strip.invariant.group

Summary:
This patch introduce new intrinsic -
strip.invariant.group that was described in the
RFC: Devirtualization v2

Reviewers: rsmith, hfinkel, nlopes, sanjoy, am

Implement strip.invariant.group

Summary:
This patch introduce new intrinsic -
strip.invariant.group that was described in the
RFC: Devirtualization v2

Reviewers: rsmith, hfinkel, nlopes, sanjoy, amharc, kuhar

Subscribers: arsenm, nhaehnle, JDevlieghere, hiraditya, xbolva00, llvm-commits

Differential Revision: https://reviews.llvm.org/D47103

Co-authored-by: Krzysztof Pszeniczny <krzysztof.pszeniczny@gmail.com>
llvm-svn: 336073

show more ...

[BasicAA] Teach the analysis about atomic memcpy

Summary:
A simple change to derive mod/ref info from the atomic memcpy
intrinsic in the same way as from the regular memcpy intrinsic.

llvm-svn: 333

[BasicAA] Teach the analysis about atomic memcpy

Summary:
A simple change to derive mod/ref info from the atomic memcpy
intrinsic in the same way as from the regular memcpy intrinsic.

llvm-svn: 333454

show more ...

Replace AA's uses of uint64_t with LocationSize; NFC.

The uint64_ts that we pass around AA to represent MemoryLocation sizes
are logically an Optional<uint64_t>. In D44748, we want to add an extra
'

Replace AA's uses of uint64_t with LocationSize; NFC.

The uint64_ts that we pass around AA to represent MemoryLocation sizes
are logically an Optional<uint64_t>. In D44748, we want to add an extra
'imprecise' bit to this Optional<uint64_t> to represent whether a given
MemoryLocation size is an upper-bound or an exact size. For more context
on why, please see D44748.

That patch is quite large, but reviewers seem to be OK with the
approach. In D45581 (my first attempt to split 'noise' out of D44748),
reames asked that I land a precursor that is solely replacing uint64_t
with LocationSize, which starts out as `using LocationSize = uint64_t;`.
He also gave me the OK to submit this rename without further review.

llvm-svn: 333314

show more ...

Fix aliasing of launder.invariant.group

Summary:
Patch for capture tracking broke
bootstrap of clang with -fstict-vtable-pointers
which resulted in debbugging nightmare. It was fixed
https://reviews

Fix aliasing of launder.invariant.group

Summary:
Patch for capture tracking broke
bootstrap of clang with -fstict-vtable-pointers
which resulted in debbugging nightmare. It was fixed
https://reviews.llvm.org/D46900 but as it turned
out, there were other parts like inliner (computing of
noalias metadata) that I found after bootstraping with enabled
assertions.

Reviewers: hfinkel, rsmith, chandlerc, amharc, kuhar

Subscribers: JDevlieghere, eraman, llvm-commits, hiraditya

Differential Revision: https://reviews.llvm.org/D47088

llvm-svn: 333070

show more ...

[BasicAA] Fix handling of invariant group launders

Summary:
A recent patch ([[ https://reviews.llvm.org/rL331587 | rL331587 ]]) to Capture Tracking taught it that the `launder_invariant_group` intri

[BasicAA] Fix handling of invariant group launders

Summary:
A recent patch ([[ https://reviews.llvm.org/rL331587 | rL331587 ]]) to Capture Tracking taught it that the `launder_invariant_group` intrinsic captures its argument only by returning it. Unfortunately, BasicAA still considered every call instruction as a possible escape source and hence concluded that the result of a `launder_invariant_group` call cannot alias any local non-escaping value. This led to [[ https://bugs.llvm.org/show_bug.cgi?id=37458 | bug 37458 ]].

This patch updates the relevant check for escape sources in BasicAA.

Reviewers: Prazek, kuhar, rsmith, hfinkel, sanjoy, xbolva00

Reviewed By: hfinkel, xbolva00

Subscribers: JDevlieghere, hiraditya, llvm-commits

Differential Revision: https://reviews.llvm.org/D46900

llvm-svn: 332466

show more ...

Rename invariant.group.barrier to launder.invariant.group

Summary:
This is one of the initial commit of "RFC: Devirtualization v2" proposal:
https://docs.google.com/document/d/16GVtCpzK8sIHNc2qZz6RN

Rename invariant.group.barrier to launder.invariant.group

Summary:
This is one of the initial commit of "RFC: Devirtualization v2" proposal:
https://docs.google.com/document/d/16GVtCpzK8sIHNc2qZz6RN8amICNBtvjWUod2SujZVEo/edit?usp=sharing

Reviewers: rsmith, amharc, kuhar, sanjoy

Subscribers: arsenm, nhaehnle, javed.absar, hiraditya, llvm-commits

Differential Revision: https://reviews.llvm.org/D45111

llvm-svn: 331448

show more ...

[BasicAA] Return MayAlias for the pointer plus variable offset to
structure object member

Differential Revision: https://reviews.llvm.org/D45510

llvm-svn: 330106

[ModRefInfo] Return NoModRef for Must and NoModRef.

Summary:
In ModRefInfo "Must" was introduced to track presence of MustAlias, but we still want to return NoModRef when there is neither Mod or Ref

[ModRefInfo] Return NoModRef for Must and NoModRef.

Summary:
In ModRefInfo "Must" was introduced to track presence of MustAlias, but we still want to return NoModRef when there is neither Mod or Ref, even when MustAlias is found. Patch has small fixes to ensure this happens.
Minor cleanup to remove nesting for 2 if statements when calling getModRefInfo for 2 ImmutableCallSites.

Reviewers: sanjoy

Subscribers: jlebar, llvm-commits

Differential Revision: https://reviews.llvm.org/D42209

llvm-svn: 322932

show more ...

[BasicAA] Stop crashing when dealing with pointers > 64 bits.

An alternative (and probably better) fix would be that of
making `Scale` an APInt, and there's a patch floating around
to do this. As we

[BasicAA] Stop crashing when dealing with pointers > 64 bits.

An alternative (and probably better) fix would be that of
making `Scale` an APInt, and there's a patch floating around
to do this. As we're still discussing it, at least stop crashing
in the meanwhile (added bonus, we now have a regression test for
this situation).

Fixes PR35843.

Thanks to Eli for suggesting the fix and Simon for reporting and
reducing the bug.

llvm-svn: 322467

show more ...

[BasicAA] Fix linearization of shifts beyond the bitwidth.

Thanks to Simon Pilgrim for the reduced testcase.
Fixes PR35821.

llvm-svn: 321873

[ModRefInfo] Add must alias info to ModRefInfo.

Summary:
Add an additional bit to ModRefInfo, ModRefInfo::Must, to be cleared for known must aliases.
Shift existing Mod/Ref/ModRef values to include

[ModRefInfo] Add must alias info to ModRefInfo.

Summary:
Add an additional bit to ModRefInfo, ModRefInfo::Must, to be cleared for known must aliases.
Shift existing Mod/Ref/ModRef values to include an additional most
significant bit. Update wrappers that modify ModRefInfo values to
reflect the change.

Notes:
* ModRefInfo::Must is almost entirely cleared in the AAResults methods, the remaining changes are trying to preserve it.
* Only some small changes to make custom AA passes set ModRefInfo::Must (BasicAA).
* GlobalsModRef already declares a bit, who's meaning overlaps with the most significant bit in ModRefInfo (MayReadAnyGlobal). No changes to shift the value of MayReadAnyGlobal (see AlignedMap). FunctionInfo.getModRef() ajusts most significant bit so correctness is preserved, but the Must info is lost.
* There are cases where the ModRefInfo::Must is not set, e.g. 2 calls that only read will return ModRefInfo::NoModRef, though they may read from exactly the same location.

Reviewers: dberlin, hfinkel, george.burgess.iv

Subscribers: llvm-commits, sanjoy

Differential Revision: https://reviews.llvm.org/D38862

llvm-svn: 321309

show more ...

[ModRefInfo] Make enum ModRefInfo an enum class [NFC].

Summary:
Make enum ModRefInfo an enum class. Changes to ModRefInfo values should
be done using inline wrappers.
This should prevent future bit-

[ModRefInfo] Make enum ModRefInfo an enum class [NFC].

Summary:
Make enum ModRefInfo an enum class. Changes to ModRefInfo values should
be done using inline wrappers.
This should prevent future bit-wise opearations from being added, which can be more error-prone.

Reviewers: sanjoy, dberlin, hfinkel, george.burgess.iv

Subscribers: llvm-commits

Differential Revision: https://reviews.llvm.org/D40933

llvm-svn: 320107

show more ...

[ModRefInfo] Replace remaining bit-wise operations with wrappers.

llvm-svn: 319993

[ModRefInfo] Use createModRefInfo wrapper to create a ModRefInfo from FunctionModRefBehavior.

llvm-svn: 319941

Modify ModRefInfo values using static inline method abstractions [NFC].

Summary:
The aim is to make ModRefInfo checks and changes more intuitive
and less error prone using inline methods that abstra

Modify ModRefInfo values using static inline method abstractions [NFC].

Summary:
The aim is to make ModRefInfo checks and changes more intuitive
and less error prone using inline methods that abstract the bit operations.

Ideally ModRefInfo would become an enum class, but that change will require
a wider set of changes into FunctionModRefBehavior.

Reviewers: sanjoy, george.burgess.iv, dberlin, hfinkel

Subscribers: nlopes, llvm-commits

Differential Revision: https://reviews.llvm.org/D40749

llvm-svn: 319821

show more ...

revert r317812 [BasicAA] fix build break by converting the previously introduced assert into an if stmt

The code has a bug, but some tests regress.
I'll discuss this further on the mailing list.

ll

revert r317812 [BasicAA] fix build break by converting the previously introduced assert into an if stmt

The code has a bug, but some tests regress.
I'll discuss this further on the mailing list.

llvm-svn: 317815

show more ...

[BasicAA] fix build break by converting the previously introduced assert into an if stmt
Apparently V1Size == -1 doest imply V2Size == -1, which is a bit surprising to me.

llvm-svn: 317812

[BasicAA] add assertion for corner case in aliasGEP()

llvm-svn: 317803

BasicAA: fix bug where we would return partialalias instead of noalias
My fix is conservative and will make us return may-alias instead.

The test case is:
check(gep(x, 0), n, gep(x, n), -1) with n

BasicAA: fix bug where we would return partialalias instead of noalias
My fix is conservative and will make us return may-alias instead.

The test case is:
check(gep(x, 0), n, gep(x, n), -1) with n == sizeof(x)

Here, the first value accesses the whole object, but the second access
doesn't access anything. The semantics of -1 is read until the end of the
object, which in this case means read nothing.

No test case, since isn't trivial to exploit this one, but I've proved it correct.

llvm-svn: 317680

show more ...