[IR] Add getDataLayout() helpers to BasicBlock and Instruction (#96902)

This is a helper to avoid writing `getModule()->getDataLayout()`. I
regularly try to use this method only to remember it does

[IR] Add getDataLayout() helpers to BasicBlock and Instruction (#96902)

This is a helper to avoid writing `getModule()->getDataLayout()`. I
regularly try to use this method only to remember it doesn't exist...

`getModule()->getDataLayout()` is also a common (the most common?)
reason why code has to include the Module.h header.

show more ...

[llvm] format and terminate namespaces with closing comment (#94917)

Namespaces are terminated with a closing comment in the majority of the
codebase so do the same here for consistency. Also forma

[llvm] format and terminate namespaces with closing comment (#94917)

Namespaces are terminated with a closing comment in the majority of the
codebase so do the same here for consistency. Also format code within
some namespaces to make clang-format happy.

show more ...

[CaptureTracking] Treat vector GEPs as captures

Because AA does not support vectors of pointers, we have to
treat pointers that are inserted into a vector as captures. We
mostly already do so, but m

[CaptureTracking] Treat vector GEPs as captures

Because AA does not support vectors of pointers, we have to
treat pointers that are inserted into a vector as captures. We
mostly already do so, but missed the case where getelementptr
is used to produce a vector.

show more ...

Revert "[CaptureTracking] Ignore ephemeral values when determining po… (#71066)

Unfortunately the commit (D123162) introduced a mis-compile
(https://github.com/llvm/llvm-project/issues/70547), whic

Revert "[CaptureTracking] Ignore ephemeral values when determining po… (#71066)

Unfortunately the commit (D123162) introduced a mis-compile
(https://github.com/llvm/llvm-project/issues/70547), which wasn't fixed
by the alternative fix (c0de28b92e98acbeb73)

I think as long as the call considered as ephemeral is not removed, we
need to be conservative. To address the correctness issue quickly, I
think we should revert the patch (as this patch does, it doens't revert
cleanly)

This reverts commit 17fdaccccfad9b143e4aadbcdda7f645de127153.

Fixes https://github.com/llvm/llvm-project/issues/70547

show more ...

[AA] Make LI and EphValues option in EarliestEscapeInfo (NFC)

To allow using it in places where these may not be available.

[Core][FIX] Do not assume instruction users in DetermineUseCaptureKind

[CaptureTracking] Don't consider comparison of inbounds GEP with nonnull non-capturing

This is required to bring CaptureTracking in line with the new
semantics from D154051, as gep inbounds p, 0 is

[CaptureTracking] Don't consider comparison of inbounds GEP with nonnull non-capturing

This is required to bring CaptureTracking in line with the new
semantics from D154051, as gep inbounds p, 0 is now always non-poison.

There are many ways in which the inbounds special case could be
preserved: If the index is known non-zero, or there is an inbounds
chain down to an identified object, etc. However, I have opted to
drop the special case entirely, as it appears to be low value:
In cases where we can determine such things (e.g. the affected test
cases) we would end up removing the compare via isGEPKnownNonNull()
logic anyway.

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

show more ...

[NFC] Add some debug printouts to CaptureTracking

[InstSimplify][CaptureTracking] Reduce scope of special case

As described in PR54002, the "icmp of load from global" special
case in CaptureTracking is incorrect, as is the InstSimplify code
that ma

[InstSimplify][CaptureTracking] Reduce scope of special case

As described in PR54002, the "icmp of load from global" special
case in CaptureTracking is incorrect, as is the InstSimplify code
that makes use of it.

This moves the special case from CaptureTracking into InstSimplify
to limit its scope to the buggy transform only, and not affect
other code using CaptureTracking as well.

show more ...

Reapply [Dominators] Add findNearestCommonDominator() for Instructions (NFC)

Reapply with checks for instructions in unreachable blocks. A test
case for this was added in 1ee4a93b15bb.

-----

This

Reapply [Dominators] Add findNearestCommonDominator() for Instructions (NFC)

Reapply with checks for instructions in unreachable blocks. A test
case for this was added in 1ee4a93b15bb.

-----

This is a recurring pattern: We want to find the nearest common
dominator (instruction) for two instructions, but currently only
provide an API for the nearest common dominator of two basic blocks.

Add an overload that accepts and return instructions.

show more ...

Revert "[Dominator] Add findNearestCommonDominator() for Instructions (NFC)"

This reverts commit 7f0de9573f758f5f9108795850337a5acbd17eef.

This is missing handling for !isReachableFromEntry() block

Revert "[Dominator] Add findNearestCommonDominator() for Instructions (NFC)"

This reverts commit 7f0de9573f758f5f9108795850337a5acbd17eef.

This is missing handling for !isReachableFromEntry() blocks, which
may be relevant for some callers. Revert for now.

show more ...

[Dominator] Add findNearestCommonDominator() for Instructions (NFC)

This is a recurring pattern: We want to find the nearest common
dominator (instruction) for two instructions, but currently only
p

[Dominator] Add findNearestCommonDominator() for Instructions (NFC)

This is a recurring pattern: We want to find the nearest common
dominator (instruction) for two instructions, but currently only
provide an API for the nearest common dominator of two basic blocks.

Add an overload that accepts and return instructions.

show more ...

[CaptureTracking] Increase limit and use it for all visited uses.

Currently the MaxUsesToExplore limit only applies to the number of users
per value, not the total number of users to explore.

The c

[CaptureTracking] Increase limit and use it for all visited uses.

Currently the MaxUsesToExplore limit only applies to the number of users
per value, not the total number of users to explore.

The current limit of 20 pessimizes IR with opaque pointers in some
cases. Without opaque pointers, we have deeper pointer def-use chains in
general due to extra bitcasts and geps for structs with index 0.

With opaque pointers the def-use chain is not as deep but wider, due to
bitcasts & 0-geps missing.

To improve the situation for opaque pointers, this patch does 2 things:

1. Apply the limit to the total number of uses visited. From the
wording in the description of the option it seems like this may be
the original intention. With the current implementation we could
still end up walking a lot of uses.
2. Increase the limit to 100. This is quite arbitrary, but enables
a good number of additional optimizations.

Those adjustments have a noticeable compile-time impact though. In part
that is likely due to additional transformations (and conversely
the current baseline misses optimizations after switching to opaque
pointers).

This recovers some regressions that showed up after enabling opaque
pointers.

Limit=100:

* NewPM-O3: +0.21%
* NewPM-ReleaseThinLTO: +0.87%
* NewPM-ReleaseLTO-g: +0.46%

https://llvm-compile-time-tracker.com/compare.php?from=2e50ecb2ef4e1da1aeab05bcf66380068e680991&to=7e6fbe519d958d09f32f01d5d44a622f551e2031&stat=instructions

Limit=60:

* NewPM-O3: +0.14%
* NewPM-ReleaseThinLTO: +0.41%
* NewPM-ReleaseLTO-g: +0.21%

https://llvm-compile-time-tracker.com/compare.php?from=aeb19817d66f1a15754163c7f48e01e9ebdd6d45&to=520563fdc146319aae90d06f88d87f2e9e1247b7&stat=instructions

Limit=40:
* NewPM-O3: +0.11%
* NewPM-ReleaseThinLTO: +0.12%
* NewPM-ReleaseLTO-g: +0.09%

https://llvm-compile-time-tracker.com/compare.php?from=aeb19817d66f1a15754163c7f48e01e9ebdd6d45&to=c9182576e9fe3f1c84a71479665aef91a416318c&stat=instructions

Reviewed By: nikic

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

show more ...

[CaptureTracking] Ignore ephemeral values in EarliestEscapeInfo

And thread DSE's ephemeral values to EarliestEscapeInfo.

This allows more precise analysis in DSEState::isReadClobber() via BatchAA.

[CaptureTracking] Ignore ephemeral values in EarliestEscapeInfo

And thread DSE's ephemeral values to EarliestEscapeInfo.

This allows more precise analysis in DSEState::isReadClobber() via BatchAA.

Followup to D123162.

Reviewed By: nikic

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

show more ...

[CaptureTracking] Ignore ephemeral values when determining pointer escapeness

Ephemeral values cannot cause a pointer to escape.

No change in compile time:
https://llvm-compile-time-tracker.com/com

[CaptureTracking] Ignore ephemeral values when determining pointer escapeness

Ephemeral values cannot cause a pointer to escape.

No change in compile time:
https://llvm-compile-time-tracker.com/compare.php?from=4371710085ba1c376a094948b806ddd3b88319de&to=c5ddbcc4866f38026737762ee8d7b9b00395d4f4&stat=instructions

This partially fixes some regressions caused by more calls to `__builtin_assume` (D122397).

Reviewed By: asbirlea

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

show more ...

[CaptureTracking][NFCI] Expose capture tracking logic

The logic exposed by this patch via `llvm::DetermineUseCaptureKind` was
part of `llvm::PointerMayBeCaptured`. In the Attributor we want to keep

[CaptureTracking][NFCI] Expose capture tracking logic

The logic exposed by this patch via `llvm::DetermineUseCaptureKind` was
part of `llvm::PointerMayBeCaptured`. In the Attributor we want to keep
track of the work list items but still reuse the logic if a use might
capture a value. A follow up for the Attributor removes ~100 lines of
code and complexity while making future handling of simplified values
possible.

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

show more ...

[llvm] Use = default (NFC)

[Analysis] Use default member initialization (NFC)

Identified with modernize-use-default-member-init.

[capturetracking] Explicitly check for callee operand [NFC]

Pull out an explicit check rather than relying on the fact that the callee operand is not a data operand. The only real value is it gives

[capturetracking] Explicitly check for callee operand [NFC]

Pull out an explicit check rather than relying on the fact that the callee operand is not a data operand. The only real value is it gives us a clear place to move the comment, and makes the code slightly more understandable.

show more ...

Recommit "[DSE] Track earliest escape, use for loads in isReadClobber."

This reverts the revert commit df56fc6ebbee6c458b0473185277b7860f7e3408.

This version of the patch adjusts the location where

Recommit "[DSE] Track earliest escape, use for loads in isReadClobber."

This reverts the revert commit df56fc6ebbee6c458b0473185277b7860f7e3408.

This version of the patch adjusts the location where the EarliestEscapes
cache is cleared when an instruction gets removed. The earliest escaping
instruction does not have to be a memory instruction.

It could be a ptrtoint instruction like in the added test
@earliest_escape_ptrtoint, which subsequently gets removed. We need to
invalidate the EarliestEscape entry referring to the ptrtoint when
deleting it.

This fixes the crash mentioned in
https://bugs.chromium.org/p/chromium/issues/detail?id=1252762#c6

show more ...

Revert "[DSE] Track earliest escape, use for loads in isReadClobber."

This reverts commit 5ce89279c0986d0bcbe526dce52f91dd0c16427c.
Makes clang crash, see comments on https://reviews.llvm.org/D109844

[DSE] Track earliest escape, use for loads in isReadClobber.

At the moment, DSE only considers whether a pointer may be captured at
all in a function. This leads to cases where we fail to remove sto

[DSE] Track earliest escape, use for loads in isReadClobber.

At the moment, DSE only considers whether a pointer may be captured at
all in a function. This leads to cases where we fail to remove stores to
local objects because we do not check if they escape before potential
read-clobbers or after.

Doing context-sensitive escape queries in isReadClobber has been removed
a while ago in d1a1cce5b130 to save compile-time. See PR50220 for more
context.

This patch introduces a new capture tracker, which keeps track of the
'earliest' capture. An instruction A is considered earlier than instruction
B, if A dominates B. If 2 escapes do not dominate each other, the
terminator of the common dominator is chosen. If not all uses cannot be
analyzed, the earliest escape is set to the first instruction in the
function entry block.

If the query instruction dominates the earliest escape and is not in a
cycle, then pointer does not escape before the query instruction.

This patch uses this information when checking if a load of a loaded
underlying object may alias a write to a stack object. If the stack
object does not escape before the load, they do not alias.

I will share a follow-up patch to also use the information for call
instructions to fix PR50220.

In terms of compile-time, the impact is low in general,
NewPM-O3: +0.05%
NewPM-ReleaseThinLTO: +0.05%
NewPM-ReleaseLTO-g: +0.03

with the largest change being tramp3d-v4 (+0.30%)
http://llvm-compile-time-tracker.com/compare.php?from=1a3b3301d7aa9ab25a8bdf045c77298b087e3930&to=bc6c6899cae757c3480f4ad4874a76fc1eafb0be&stat=instructions

Compared to always computing the capture information on demand, we get
the following benefits from the caching:
NewPM-O3: -0.03%
NewPM-ReleaseThinLTO: -0.08%
NewPM-ReleaseLTO-g: -0.04%

The biggest speedup is tramp3d-v4 (-0.21%).
http://llvm-compile-time-tracker.com/compare.php?from=0b0c99177d1511469c633282ef67f20c851f58b1&to=bc6c6899cae757c3480f4ad4874a76fc1eafb0be&stat=instructions

Overall there is a small, but noticeable benefit from caching. I am not
entirely sure if the speedups warrant the extra complexity of caching.
The way the caching works also means that we might miss a few cases, as
it is less precise. Also, there may be a better way to cache things.

Reviewed By: nikic

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

show more ...

[CaptureTracking] Allow passing LI to PointerMayBeCapturedBefore (NFC).

isPotentiallyReachable can use LoopInfo to return earlier. This patch
allows passing an optional LI to PointerMayBeCapturedBef

[CaptureTracking] Allow passing LI to PointerMayBeCapturedBefore (NFC).

isPotentiallyReachable can use LoopInfo to return earlier. This patch
allows passing an optional LI to PointerMayBeCapturedBefore. Used in
D109844.

Reviewed By: nikic, asbirlea

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

show more ...

[CaptureTracking] Simplify reachability check (NFCI)

This code was re-implementing the same-BB case of
isPotentiallyReachable(). Historically, this was done because
CaptureTracking used additional c

[CaptureTracking] Simplify reachability check (NFCI)

This code was re-implementing the same-BB case of
isPotentiallyReachable(). Historically, this was done because
CaptureTracking used additional caching for local dominance
queries. Now that it is no longer needed, the code is effectively
the same as isPotentiallyReachable().

The only difference are extra checks for invoke/phis. These are
misleading checks related to dominance in the value availability
sense that are not relevant for control reachability. The invoke
check was correct but redundant in that invokes are always
terminators, so `I` could never come before the invoke. The phi
check is a matter of interpretation (should an earlier phi node be
considered reachable from a later phi node in the same block?)
but ultimately doesn't matter because phis don't capture anyway.

show more ...

Reapply [CaptureTracking] Do not check domination

Reapply after adjusting the synchronized.m test case, where the
TODO is now resolved. The pointer is only captured on the exception
handling path.

Reapply [CaptureTracking] Do not check domination

Reapply after adjusting the synchronized.m test case, where the
TODO is now resolved. The pointer is only captured on the exception
handling path.

-----

For the CapturesBefore tracker, it is sufficient to check that
I can not reach BeforeHere. This does not necessarily require
that BeforeHere dominates I, it can also occur if the capture
happens on an entirely disjoint path.

This change was previously accepted in D90688, but had to be
reverted due to large compile-time impact in some cases: It
increases the number of reachability queries that are performed.

After recent changes, the compile-time impact is largely mitigated,
so I'm reapplying this patch. The remaining compile-time impact
is largely proportional to changes in code-size.

show more ...