[BasicBlockUtils] Allow splitting predecessors with callbr terminators

SplitBlockPredecessors currently asserts if one of the predecessor
terminators is a callbr. This limitation was originally nece

[BasicBlockUtils] Allow splitting predecessors with callbr terminators

SplitBlockPredecessors currently asserts if one of the predecessor
terminators is a callbr. This limitation was originally necessary,
because just like with indirectbr, it was not possible to replace
successors of a callbr. However, this is no longer the case since
D67252. As the requirement nowadays is that callbr must reference
all blockaddrs directly in the call arguments, and these get
automatically updated when setSuccessor() is called, we no longer
need this limitation.

The only thing we need to do here is use replaceSuccessorWith()
instead of replaceUsesOfWith(), because only the former does the
necessary blockaddr updating magic.

I believe there's other similar limitations that can be removed,
e.g. related to critical edge splitting.

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

show more ...

[LICM] Use poison to replace unreachable values instead of undef [NFC]

Fix a misspell. NFC

Recommit "[LICM] Only create load in ph when promoting load or store doesn't exec."

This reverts the revert commit ad95255b9215a.

The updated version also creates a load when the store may not exec

Recommit "[LICM] Only create load in ph when promoting load or store doesn't exec."

This reverts the revert commit ad95255b9215a.

The updated version also creates a load when the store may not execute.
In those cases, we still need to introduce a load in a function where
there may not have been one before, so this doesn't completely resolve
issue #51248.

Original message:

When only a store is sunk, there is no need to create a load in the
pre-header, as the result of the load will never get used.

The dead load can can introduce UB, if the function is marked as
writeonly.

Reviewed By: nikic

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

show more ...

Revert "[LICM] Only create load in pre-header when promoting load."

This reverts commit 4bf3b7dc929c8288e9e5631978ef060d9140b251.

This might be causing another buildbot failure.

Recommit "[LICM] Only create load in pre-header when promoting load."

This reverts the revert commit 1ddc719680c21f3.

This version of the patch sets the initial available value to poison,
which res

Recommit "[LICM] Only create load in pre-header when promoting load."

This reverts the revert commit 1ddc719680c21f3.

This version of the patch sets the initial available value to poison,
which resolves an issue with the SSAUpdater breaking LCSSA form.

show more ...

Revert "[LICM] Only create load in pre-header when promoting load."

This reverts commit 42229b96bf94ec896d5c62fa643d83ba96e86eea.

This appears to cause crashes on multiple bots.

[LICM] Only create load in pre-header when promoting load.

When only a store is sunk, there is no need to create a load in the
pre-header, as the result of the load will never get used.

The dead lo

[LICM] Only create load in pre-header when promoting load.

When only a store is sunk, there is no need to create a load in the
pre-header, as the result of the load will never get used.

The dead load can can introduce UB, if the function is marked as
writeonly.

Fixes #51248.

Reviewed By: nikic

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

show more ...

[LICM] Pass MemorySSAUpdater by referene (NFC)

Make it clearer that this is a required dependency.

[LoopSink] Require MemorySSA

This makes MemorySSA in LoopSink required, and removes the AST-based
implementation, as well as the related support code in LICM.

Differential Revision: https://reviews

[LoopSink] Require MemorySSA

This makes MemorySSA in LoopSink required, and removes the AST-based
implementation, as well as the related support code in LICM.

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

show more ...

NFC: [LICM] Update some stale comments

After removing the MaybePromotable, some comments
became stale. This improves them.

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

[LICM] Handle store of pointer to itself (PR54495)

Rather than iterating over users and comparing operands, iterate
over uses and check operand number. Otherwise, we'll end up
promoting a store twic

[LICM] Handle store of pointer to itself (PR54495)

Rather than iterating over users and comparing operands, iterate
over uses and check operand number. Otherwise, we'll end up
promoting a store twice if it has two equal operands.

This can only happen with opaque pointers, as otherwise both
operands differ by a level of indirection, so a bitcast would have
to be involved.

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

show more ...

[LICM] Add allowspeculation pass options.

This adds a new option to control AllowSpeculation added in D119965 when
using `-passes=...`.

This allows reproducing #54023 using opt.

Reviewed By: aeuba

[LICM] Add allowspeculation pass options.

This adds a new option to control AllowSpeculation added in D119965 when
using `-passes=...`.

This allows reproducing #54023 using opt.

Reviewed By: aeubanks

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

show more ...

[MemorySSA] Don't optimize uses during construction

This changes MemorySSA to be constructed in unoptimized form.
MemorySSA::ensureOptimizedUses() can be called to optimize all
uses (once). This sho

[MemorySSA] Don't optimize uses during construction

This changes MemorySSA to be constructed in unoptimized form.
MemorySSA::ensureOptimizedUses() can be called to optimize all
uses (once). This should be done by passes where having optimized
uses is beneficial, either because we're going to query all uses
anyway, or because we're doing def-use walks.

This should help reduce the compile-time impact of MemorySSA for
some use cases (the reason why I started looking into this is
D117926), which can avoid optimizing all uses upfront, and instead
only optimize those that are actually queried.

Actually, we have an existing use-case for this, which is EarlyCSE.
Disabling eager use optimization there gives a significant
compile-time improvement, because EarlyCSE will generally only query
clobbers for a subset of all uses (this change is not included in
this patch).

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

show more ...

Cleanup includes: Transform/Scalar

Estimated impact on preprocessor output line:
before: 1062981579
after: 1062494547

Discourse thread: https://discourse.llvm.org/t/include-what-you-use-include-cl

Cleanup includes: Transform/Scalar

Estimated impact on preprocessor output line:
before: 1062981579
after: 1062494547

Discourse thread: https://discourse.llvm.org/t/include-what-you-use-include-cleanup
Differential Revision: https://reviews.llvm.org/D120817

show more ...

Cleanup includes: TransformsUtils

Estimation on the impact on preprocessor output:
before: 1065307662
after: 1064800684

Discourse thread: https://discourse.llvm.org/t/include-what-you-use-include-

Cleanup includes: TransformsUtils

Estimation on the impact on preprocessor output:
before: 1065307662
after: 1064800684

Discourse thread: https://discourse.llvm.org/t/include-what-you-use-include-cleanup
Differential Revision: https://reviews.llvm.org/D120741

show more ...

[LICM][PhaseOrder] Don't speculate in LICM until after running loop rotate

LICM will speculatively hoist code outside of loops. This requires removing information, like alias analysis (https://githu

[LICM][PhaseOrder] Don't speculate in LICM until after running loop rotate

LICM will speculatively hoist code outside of loops. This requires removing information, like alias analysis (https://github.com/llvm/llvm-project/issues/53794), range information (https://bugs.llvm.org/show_bug.cgi?id=50550), among others. Prior to https://reviews.llvm.org/D99249 , LICM would only be run after LoopRotate. Running Loop Rotate prior to LICM prevents a instruction hoist from being speculative, if it was conditionally executed by the iteration (as is commonly emitted by clang and other frontends). Adding the additional LICM pass first, however, forces all of these instructions to be considered speculative, even if they are not speculative after LoopRotate. This destroys information, resulting in performance losses for discarding this additional information.

This PR modifies LICM to accept a ``speculative'' parameter which allows LICM to be set to perform information-loss speculative hoists or not. Phase ordering is then modified to not perform the information-losing speculative hoists until after loop rotate is performed, preserving this additional information.

Reviewed By: lebedev.ri

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

show more ...

[LICM] Generalize unwinding check during scalar promotion

This extract a common isNotVisibleOnUnwind() helper into
AliasAnalysis, which handles allocas, byval arguments and noalias
calls. After D116

[LICM] Generalize unwinding check during scalar promotion

This extract a common isNotVisibleOnUnwind() helper into
AliasAnalysis, which handles allocas, byval arguments and noalias
calls. After D116998 this could also handle sret arguments. We
have similar logic in DSE and MemCpyOpt, which will be switched
to use this helper as well.

The noalias call case is a bit different from the others, because
it also requires that the object is not captured. The caller is
responsible for doing the appropriate check.

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

show more ...

[NFC] Test commit.

This is just a test commit to check whether I got commit permission.

[LICM] Update comments related to escape check (NFC)

The comments here were outdated and a bit confusing without the
knowledge that we're only guarding against reads on unwind.

[LICM] Check for noalias call instead of alloc like fn

When determining whether the memory is local to the function (and
we can thus introduce spurious writes without thread-safety issues),
check fo

[LICM] Check for noalias call instead of alloc like fn

When determining whether the memory is local to the function (and
we can thus introduce spurious writes without thread-safety issues),
check for a noalias call rather than the hardcoded list of memory
allocation functions. Noalias calls are the more general way to
determine allocation functions, as long as we're only interested
in the property that the returned value is distinct from any other
accessible memory.

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

show more ...

[LICM] Remove profile driven restriction on hoisting

This reverts change 2c391a5/D87551. As noted in the llvm-dev thread "LICM as canonical form" sent earlier today, introducing this was a major de

[LICM] Remove profile driven restriction on hoisting

This reverts change 2c391a5/D87551. As noted in the llvm-dev thread "LICM as canonical form" sent earlier today, introducing this was a major design change made without sufficient cause.

A profile driven LICM is not an unreasonable design, it simply is not what we have. Switching to such a model requires a lot more work than just this patch, and broad aggeement that is the right direction for the optimizer as a whole.

Worth noting is that all the tests included in the reverted changed are probably handled if we allow running unconstrained LICM, and later run LoopSink. As such, we have no public examples which motivate a profit based hoisting approach.

show more ...

Reland "[LICM] Hoist LOAD without sinking the STORE"

When doing load/store promotion within LICM, if we
cannot prove that it is safe to sink the store we won't
hoist the load, even though we can pro

Reland "[LICM] Hoist LOAD without sinking the STORE"

When doing load/store promotion within LICM, if we
cannot prove that it is safe to sink the store we won't
hoist the load, even though we can prove the load could
be dereferenced and moved outside the loop. This patch
implements the load promotion by moving it in the loop
preheader by inserting proper PHI in the loop. The store
is kept as is in the loop. By doing this, we avoid doing
the load from a memory location in each iteration.

Please consider this small example:

loop {
var = *ptr;
if (var) break;
*ptr= var + 1;
}
After this patch, it will be:

var0 = *ptr;
loop {
var1 = phi (var0, var2);
if (var1) break;
var2 = var1 + 1;
*ptr = var2;
}
This addresses some problems from [0].

[0] https://bugs.llvm.org/show_bug.cgi?id=51193

Differential revision: https://reviews.llvm.org/D113289

show more ...

Revert "[LICM] Hoist LOAD without sinking the STORE"

This reverts commit ecb9d8e4e3c4623c2edcd2c50727103927d31508.

I'll reland this as soon as the failing tests are fixed/updated.

[LICM] Hoist LOAD without sinking the STORE

When doing load/store promotion within LICM, if we
cannot prove that it is safe to sink the store we won't
hoist the load, even though we can prove the lo

[LICM] Hoist LOAD without sinking the STORE

When doing load/store promotion within LICM, if we
cannot prove that it is safe to sink the store we won't
hoist the load, even though we can prove the load could
be dereferenced and moved outside the loop. This patch
implements the load promotion by moving it in the loop
preheader by inserting proper PHI in the loop. The store
is kept as is in the loop. By doing this, we avoid doing
the load from a memory location in each iteration.

Please consider this small example:

loop {
var = *ptr;
if (var) break;
*ptr= var + 1;
}
After this patch, it will be:

var0 = *ptr;
loop {
var1 = phi (var0, var2);
if (var1) break;
var2 = var1 + 1;
*ptr = var2;
}
This addresses some problems from [0].

[0] https://bugs.llvm.org/show_bug.cgi?id=51193

Differential revision: https://reviews.llvm.org/D113289

show more ...