Reapply "[VPlan] Update scalar induction resume values in VPlan. (#110577)"

This reverts commit f09b16e2671cbcdf7cb7dc7ed705db092a9deda1.

The crash when building llvm-test-suite with stage2 should

Reapply "[VPlan] Update scalar induction resume values in VPlan. (#110577)"

This reverts commit f09b16e2671cbcdf7cb7dc7ed705db092a9deda1.

The crash when building llvm-test-suite with stage2 should have been
fixed by 1091fad31a83d5ab87eb6fa11fe3bdb3f0d152ea.

show more ...

Revert "[VPlan] Update scalar induction resume values in VPlan. (#110577)"

This reverts commit 0678e2058364ec10b94560d27ec7138dfa003287.
This reverts commit 1091fad31a83d5ab87eb6fa11fe3bdb3f0d152ea.

Revert "[VPlan] Update scalar induction resume values in VPlan. (#110577)"

This reverts commit 0678e2058364ec10b94560d27ec7138dfa003287.
This reverts commit 1091fad31a83d5ab87eb6fa11fe3bdb3f0d152ea.

Causes crashes in llvm-test-suite when using stage 2 clang.

show more ...

[VPlan] Update scalar induction resume values in VPlan. (#110577)

Updated ILV.createInductionResumeValues (now createInductionResumeVPValue)
to directly update the VPIRInstructions wrapping the ori

[VPlan] Update scalar induction resume values in VPlan. (#110577)

Updated ILV.createInductionResumeValues (now createInductionResumeVPValue)
to directly update the VPIRInstructions wrapping the original phis with the
created resume values.

This is the first step towards modeling them completely in VPlan.
Subsequent patches will move creation of the resume values completely
into VPlan.

Depends on https://github.com/llvm/llvm-project/pull/109975.

PR: https://github.com/llvm/llvm-project/pull/110577

show more ...

[InstCombine] Infer nusw + nneg -> nuw for getelementptr (#111144)

If the gep is nusw (usually via inbounds) and the offset is
non-negative, we can infer nuw.

Proof: https://alive2.llvm.org/ce/z

[InstCombine] Infer nusw + nneg -> nuw for getelementptr (#111144)

If the gep is nusw (usually via inbounds) and the offset is
non-negative, we can infer nuw.

Proof: https://alive2.llvm.org/ce/z/ihztLy

show more ...

[LLVM][IR] Use splat syntax when printing Constant[Data]Vector. (#112548)

[LV] Regenerate check-lines for some tests.

[VPlan] Fix incorrect argument for CreateBinOp after 06c3a7d2d764.

06c3a7d2d764 incorrectly updated CreateBinOp to pass the debug location,
which gets interpreted as FPMath node. Remove the argument.

[VPlan] Run DCE after unrolling.

This cleans up a number of dead recipes after unrolling if only their
first or last parts are used. This simplifies a number of tests.

Fixes https://github.com/llvm

[VPlan] Run DCE after unrolling.

This cleans up a number of dead recipes after unrolling if only their
first or last parts are used. This simplifies a number of tests.

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

show more ...

[VPlan] Implement unrolling as VPlan-to-VPlan transform. (#95842)

This patch implements explicit unrolling by UF as VPlan transform. In
follow up patches this will allow simplifying VPTransform st

[VPlan] Implement unrolling as VPlan-to-VPlan transform. (#95842)

This patch implements explicit unrolling by UF as VPlan transform. In
follow up patches this will allow simplifying VPTransform state (no need
to store unrolled parts) as well as recipe execution (no need to
generate code for multiple parts in an each recipe). It also allows for
more general optimziations (e.g. avoid generating code for recipes that
are uniform-across parts).

It also unifies the logic dealing with unrolled parts in a single place,
rather than spreading it out across multiple places (e.g. VPlan post
processing for header-phi recipes previously.)

In the initial implementation, a number of recipes still take the
unrolled part as additional, optional argument, if their execution
depends on the unrolled part.

The computation for start/step values for scalable inductions changed
slightly. Previously the step would be computed as scalar and then
splatted, now vscale gets splatted and multiplied by the step in a
vector mul.

This has been split off https://github.com/llvm/llvm-project/pull/94339
which also includes changes to simplify VPTransfomState and recipes'
::execute.

The current version mostly leaves existing ::execute untouched and
instead sets VPTransfomState::UF to 1.

A follow-up patch will clean up all references to VPTransformState::UF.

Another follow-up patch will simplify VPTransformState to only store a
single vector value per VPValue.

PR: https://github.com/llvm/llvm-project/pull/95842

show more ...

[InstCombine] Remove some of the complexity-based canonicalization (#91185)

The idea behind this canonicalization is that it allows us to handle less
patterns, because we know that some will be can

[InstCombine] Remove some of the complexity-based canonicalization (#91185)

The idea behind this canonicalization is that it allows us to handle less
patterns, because we know that some will be canonicalized away. This is
indeed very useful to e.g. know that constants are always on the right.

However, this is only useful if the canonicalization is actually
reliable. This is the case for constants, but not for arguments: Moving
these to the right makes it look like the "more complex" expression is
guaranteed to be on the left, but this is not actually the case in
practice. It fails as soon as you replace the argument with another
instruction.

The end result is that it looks like things correctly work in tests,
while they actually don't. We use the "thwart complexity-based
canonicalization" trick to handle this in tests, but it's often a
challenge for new contributors to get this right, and based on the
regressions this PR originally exposed, we clearly don't get this right
in many cases.

For this reason, I think that it's better to remove this complexity
canonicalization. It will make it much easier to write tests for
commuted cases and make sure that they are handled.

show more ...

[InstCombine] Add canonicalization of `sitofp` -> `uitofp nneg`

This is essentially the same as #82404 but has the `nneg` flag which
allows the backend to reliably undo the transform.

Closes #88299

Revert "[InstCombine] Canonicalize `(sitofp x)` -> `(uitofp x)` if `x >= 0`"

This reverts commit d80d5b923c6f611590a12543bdb33e0c16044d44.

It wasn't a particularly important transform to begin with

Revert "[InstCombine] Canonicalize `(sitofp x)` -> `(uitofp x)` if `x >= 0`"

This reverts commit d80d5b923c6f611590a12543bdb33e0c16044d44.

It wasn't a particularly important transform to begin with and caused
some codegen regressions on targets that prefer `sitofp` so dropping.

Might re-visit along with adding `nneg` flag to `uitofp` so its easily
reversable for the backend.

show more ...

[InstCombine] Canonicalize `(sitofp x)` -> `(uitofp x)` if `x >= 0`

Just a standard canonicalization.

Proofs: https://alive2.llvm.org/ce/z/9W4VFm

Closes #82404

[VPlan] Preserve original induction order when creating scalar steps.

Update createScalarIVSteps to take an insert point as parameter. This
ensures that the inserted scalar steps are in the same ord

[VPlan] Preserve original induction order when creating scalar steps.

Update createScalarIVSteps to take an insert point as parameter. This
ensures that the inserted scalar steps are in the same order as the
recipes they replace (vs in reverse order as currently). This helps to
reduce the diff for follow-up changes.

show more ...

[InstCombine] Canonicalize constant GEPs to i8 source element type (#68882)

This patch canonicalizes getelementptr instructions with constant
indices to use the `i8` source element type. This makes

[InstCombine] Canonicalize constant GEPs to i8 source element type (#68882)

This patch canonicalizes getelementptr instructions with constant
indices to use the `i8` source element type. This makes it easier for
optimizations to recognize that two GEPs are identical, because they
don't need to see past many different ways to express the same offset.

This is a first step towards
https://discourse.llvm.org/t/rfc-replacing-getelementptr-with-ptradd/68699.
This is limited to constant GEPs only for now, as they have a clear
canonical form, while we're not yet sure how exactly to deal with
variable indices.

The test llvm/test/Transforms/PhaseOrdering/switch_with_geps.ll gives
two representative examples of the kind of optimization improvement we
expect from this change. In the first test SimplifyCFG can now realize
that all switch branches are actually the same. In the second test it
can convert it into simple arithmetic. These are representative of
common optimization failures we see in Rust.

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

show more ...

[InstCombine] Revert the `signed icmp -> unsigned icmp` canonicalization when folding `icmp Pred min|max(X, Y), Z` (#76685)

This patch tries to flip the signedness of predicates when folding an
uns

[InstCombine] Revert the `signed icmp -> unsigned icmp` canonicalization when folding `icmp Pred min|max(X, Y), Z` (#76685)

This patch tries to flip the signedness of predicates when folding an
unsigned icmp with a signed min/max. It will enable more optimizations
as we canonicalizes a signed icmp into an unsigned icmp when both
operands are known to have the same sign.
Fixes #76672.

Compile-time impact:
http://llvm-compile-time-tracker.com/compare.php?from=949ec83eaf6fa6dbffb94c2ea9c0a4d5efdbd239&to=2deca1aea8a4e13609bab72c522a97d424f0fc2d&stat=instructions:u


|stage1-O3|stage1-ReleaseThinLTO|stage1-ReleaseLTO-g|stage1-O0-g|stage2-O3|stage2-O0-g|stage2-clang|
|--|--|--|--|--|--|--|
|-0.00%|+0.01%|+0.05%|-0.12%|-0.01%|-0.03%|-0.00%|

NOTE: We can flip the signedness of predicate if both operands are
negative. But I don't see the benefit of handling these cases.

show more ...

[VPlan] Model address separately. (#72164)

Move vector pointer generation to a separate VPVectorPointerRecipe.
This untangles address computation from the memory recipes future
and is also needed

[VPlan] Model address separately. (#72164)

Move vector pointer generation to a separate VPVectorPointerRecipe.
This untangles address computation from the memory recipes future
and is also needed to enable explicit unrolling in VPlan.

https://github.com/llvm/llvm-project/pull/72164

show more ...

[ValueTracking] Add dominating condition support in computeKnownBits() (#73662)

This adds support for using dominating conditions in computeKnownBits()
when called from InstCombine. The implementat

[ValueTracking] Add dominating condition support in computeKnownBits() (#73662)

This adds support for using dominating conditions in computeKnownBits()
when called from InstCombine. The implementation uses a
DomConditionCache, which stores which branches may provide information
that is relevant for a given value.

DomConditionCache is similar to AssumptionCache, but does not try to do
any kind of automatic tracking. Relevant branches have to be explicitly
registered and invalidated values explicitly removed. The necessary
tracking is done inside InstCombine.

The reason why this doesn't just do exactly the same thing as
AssumptionCache is that a lot more transforms touch branches and branch
conditions than assumptions. AssumptionCache is an immutable analysis
and mostly gets away with this because only a handful of places have to
register additional assumptions (mostly as a result of cloning). This is
very much not the case for branches.

This change regresses compile-time by about ~0.2%. It also improves
stage2-O0-g builds by about ~0.2%, which indicates that this change results
in additional optimizations inside clang itself.

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

show more ...

[InstCombine] Set disjoint flag when turning Add into Or. (#72702)

The disjoint flag was recently added to IR in #72583

Recommit "[LV] Re-use existing broadcast value for live-ins."

This reverts commit 245ec675a4e41f7ec24dfc998720bffdc46a6c53.

Recommits eea9258648ce with a fix to only erase the instruction from the

Recommit "[LV] Re-use existing broadcast value for live-ins."

This reverts commit 245ec675a4e41f7ec24dfc998720bffdc46a6c53.

Recommits eea9258648ce with a fix to only erase the instruction from the
first part if it is defined outside the loop. This fixes a
use-after-free error reported.

show more ...

Revert "[LV] Re-use existing broadcast value for live-ins."

This reverts commit eea9258648ce73507f6f85c395de978af659d498.

That commit triggered crashes in the following testcase:

$ cat reduced.c
t

Revert "[LV] Re-use existing broadcast value for live-ins."

This reverts commit eea9258648ce73507f6f85c395de978af659d498.

That commit triggered crashes in the following testcase:

$ cat reduced.c
typedef struct {
int a[8]
} b;
typedef struct {
b *c;
short d
} e;
void f() {
int g;
char *h;
e *i = f;
short j = i->d;
int a = i->c->a[0];
for (;;)
for (; g < a; g++) {
*h = j * i->d >> 8;
h++;
}
}
$ clang -target aarch64-linux-gnu -w -c -O2 reduced.c

show more ...

[LV] Re-use existing broadcast value for live-ins.

When requesting a vector value for a live-in, we can re-use the
broadcast of the live-in of part 0 for parts > 0.

[InstCombine][LV] Fold (add (zext (add X, -1)), 1) -> (zext X) if X is non-zero.

This artifact can appear from the vectorizer. (add X, -1) is the
backedge taken count. It gets zero extended and then

[InstCombine][LV] Fold (add (zext (add X, -1)), 1) -> (zext X) if X is non-zero.

This artifact can appear from the vectorizer. (add X, -1) is the
backedge taken count. It gets zero extended and then 1 is added to
it to get the trip count.

There is usually a dominating branch that rules out X being zero.

Alive: https://alive2.llvm.org/ce/z/NsRDwX

show more ...

[VPlan] Keep entries in worklist in sinkScalarOperands.

Not removing the entries ensures that duplicates are avoided,
reducing the number of iterations.

[LoopVectorize] Convert some tests to opaque pointers (NFC)