[VPlan] Remove reverse() of predecessors from VPInstruction::generate.

This was originally done to reduce the diff for the change. Remove it
and update the remaining tests. NFC modulo reordering of

[VPlan] Remove reverse() of predecessors from VPInstruction::generate.

This was originally done to reduce the diff for the change. Remove it
and update the remaining tests. NFC modulo reordering of incoming
values.

Clean up after https://github.com/llvm/llvm-project/pull/114292.

show more ...

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

[LLVM][VPlan] Pick more optimal initial value for VPBlend. (#104019)

By choosing an initial value whose mask is only used by the blend we can
remove the need for the mask entirely.

[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 ...

[LLVM] Regenerate some test outputs for llvm/test/Transforms/LoopVectorize.

[LV] Create block in mask up-front if needed. (#76635)

At the moment, block and edge masks are created on demand, which means
that they are inserted at the point where they are demanded and then
c

[LV] Create block in mask up-front if needed. (#76635)

At the moment, block and edge masks are created on demand, which means
that they are inserted at the point where they are demanded and then
cached. It is possible that the mask for a block is looked up later at a
point that's not dominated by the point where the mask has been
inserted.

To avoid this, create masks up front on entry to the corresponding basic
block and leave it to VPlan simplification to remove unneeded masks.

Note that we need to create masks for all blocks, if any of the blocks
in the loop needs predication, as computing the mask of a block depends
on the masks of its predecessor.

Needed for #76090.

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

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 ...

Regenerate a couple of auto-gen tests to reduce diffs in upcoming change [nfc]

[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 ...

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

For these tests update_test_checks.py had to be rerun.

[NFC] Port all LoopVectorize tests to `-passes=` syntax

[NFC] Port all runlines for LoopVectorize pass tests to -passes syntax

[InstCombine] Fold ult(add(x,-1),c) -> ule(x,c) iff x != 0 (PR57635)

Alive2: https://alive2.llvm.org/ce/z/sZ6wwS

As detailed on Issue #57635 and #37628 - for unsigned comparisons, we can compare pr

[InstCombine] Fold ult(add(x,-1),c) -> ule(x,c) iff x != 0 (PR57635)

Alive2: https://alive2.llvm.org/ce/z/sZ6wwS

As detailed on Issue #57635 and #37628 - for unsigned comparisons, we can compare prior to a decrement iff the value is known never to be zero.

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

show more ...

[InstCombine] remove multi-use add demanded constant fold

This was originally part of D133788. There are no visible
regressions. All of the diffs show a large unsigned constant
becoming a small nega

[InstCombine] remove multi-use add demanded constant fold

This was originally part of D133788. There are no visible
regressions. All of the diffs show a large unsigned constant
becoming a small negative constant. This should be better
for analysis (and slightly less compile-time) and codegen.

show more ...

Revert "[NFCI] Regenerate SROA/LoopVectorize test checks"

This reverts commit 14e3450fb57305aa9ff3e9e60687b458e43835c9.

[NFCI] Regenerate LoopVectorize test checks

[LV] Mark increment of main vector loop induction variable as NUW.

This patch marks the induction increment of the main induction variable
of the vector loop as NUW when not folding the tail.

If th

[LV] Mark increment of main vector loop induction variable as NUW.

This patch marks the induction increment of the main induction variable
of the vector loop as NUW when not folding the tail.

If the tail is not folded, we know that End - Start >= Step (either
statically or through the minimum iteration checks). We also know that both
Start % Step == 0 and End % Step == 0. We exit the vector loop if %IV +
%Step == %End. Hence we must exit the loop before %IV + %Step unsigned
overflows and we can mark the induction increment as NUW.

This should make SCEV return more precise bounds for the created vector
loops, used by later optimizations, like late unrolling.

At the moment quite a few tests still need to be updated, but before
doing so I'd like to get initial feedback to make sure I am not missing
anything.

Note that this could probably be further improved by using information
from the original IV.

Attempt of modeling of the assumption in Alive2:
https://alive2.llvm.org/ce/z/H_DL_g

Part of a set of fixes required for PR50412.

Reviewed By: mkazantsev

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

show more ...

[LoopVectorize] Fix VPRecipeBuilder::createEdgeMask to correctly generate the mask

This patch fixes pr48832 by correctly generating the mask when a poison value is involved.

Consider this CFG (whic

[LoopVectorize] Fix VPRecipeBuilder::createEdgeMask to correctly generate the mask

This patch fixes pr48832 by correctly generating the mask when a poison value is involved.

Consider this CFG (which is a part of the input):

```
for.body: ; preds = %for.cond
br i1 true, label %cond.false, label %land.rhs

land.rhs: ; preds = %for.body
br i1 poison, label %cond.end, label %cond.false

cond.false: ; preds = %for.body, %land.rhs
br label %cond.end

cond.end: ; preds = %land.rhs, %cond.false
%cond = phi i32 [ 0, %cond.false ], [ 1, %land.rhs ]

```

The path for.body -> land.rhs -> cond.end should be taken when 'select i1 false, i1 poison, i1 false' holds (which means it's never taken); but VPRecipeBuilder::createEdgeMask was emitting 'and i1 false, poison' instead.
The former one successfully blocks poison propagation whereas the latter one doesn't, making the condition poison and thus causing the miscompilation.

SimplifyCFG has a similar bug (which didn't expose a real-world bug yet), and a patch for this is also ongoing (see https://reviews.llvm.org/D95026).

Reviewed By: bjope

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

show more ...

Revert "[InstCombine] add multi-use demanded bits fold for add with low-bit mask"

This reverts commit e56103d25016c9ce4e98f652ac1a09379793ccf5.
There is a stage2 msan failure blamed on this commit:

Revert "[InstCombine] add multi-use demanded bits fold for add with low-bit mask"

This reverts commit e56103d25016c9ce4e98f652ac1a09379793ccf5.
There is a stage2 msan failure blamed on this commit:
http://lab.llvm.org:8011/#/builders/74/builds/888/steps/9/logs/stdio

show more ...

[InstCombine] add multi-use demanded bits fold for add with low-bit mask

I noticed an add example like the one from D91343, so here's a similar patch.
The logic is based on existing code for the sin

[InstCombine] add multi-use demanded bits fold for add with low-bit mask

I noticed an add example like the one from D91343, so here's a similar patch.
The logic is based on existing code for the single-use demanded bits fold.
But I only matched a constant instead of using compute known bits on the
operands because that was the motivating patterni that I noticed.

I think this will allow removing a special-case (but incomplete) dedicated
fold within visitAnd(), but I need to untangle the existing code to be sure.

https://rise4fun.com/Alive/V6fP

Name: add with low mask
Pre: (C1 & (-1 u>> countLeadingZeros(C2))) == 0
%a = add i8 %x, C1
%r = and i8 %a, C2
=>
%r = and i8 %x, C2

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

show more ...

[LoopVectorize] regenerate test checks; NFC

[InstCombine] Revert rL341831: relax one-use check in foldICmpAddConstant() (PR44100)

rL341831 moved one-use check higher up, restricting a few folds
that produced a single instruction from two inst

[InstCombine] Revert rL341831: relax one-use check in foldICmpAddConstant() (PR44100)

rL341831 moved one-use check higher up, restricting a few folds
that produced a single instruction from two instructions to the case
where the inner instruction would go away.

Original commit message:
> InstCombine: move hasOneUse check to the top of foldICmpAddConstant
>
> There were two combines not covered by the check before now,
> neither of which actually differed from normal in the benefit analysis.
>
> The most recent seems to be because it was just added at the top of the
> function (naturally). The older is from way back in 2008 (r46687)
> when we just didn't put those checks in so routinely, and has been
> diligently maintained since.

From the commit message alone, there doesn't seem to be a
deeper motivation, deeper problem that was trying to solve,
other than 'fixing the wrong one-use check'.

As i have briefly discusses in IRC with Tim, the original motivation
can no longer be recovered, too much time has passed.

However i believe that the original fold was doing the right thing,
we should be performing such a transformation even if the inner `add`
will not go away - that will still unchain the comparison from `add`,
it will no longer need to wait for `add` to compute.

Doing so doesn't seem to break any particular idioms,
as least as far as i can see.

References https://bugs.llvm.org/show_bug.cgi?id=44100

show more ...

Revert "Temporarily Revert "Add basic loop fusion pass.""

The reversion apparently deleted the test/Transforms directory.

Will be re-reverting again.

llvm-svn: 358552

[InstCombine] Don't transform ((C1 OP zext(X)) & C2) -> zext((C1 OP X) & C2) if either zext or OP has another use.

If they have other users we'll just end up increasing the instruction count.

We mi

[InstCombine] Don't transform ((C1 OP zext(X)) & C2) -> zext((C1 OP X) & C2) if either zext or OP has another use.

If they have other users we'll just end up increasing the instruction count.

We might be able to weaken this to only one of them having a single use if we can prove that the and will be removed.

Fixes PR41164.

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

llvm-svn: 356690

show more ...

InstCombine: move hasOneUse check to the top of foldICmpAddConstant

There were two combines not covered by the check before now, neither of which
actually differed from normal in the benefit analysi

InstCombine: move hasOneUse check to the top of foldICmpAddConstant

There were two combines not covered by the check before now, neither of which
actually differed from normal in the benefit analysis.

The most recent seems to be because it was just added at the top of the
function (naturally). The older is from way back in 2008 (r46687) when we just
didn't put those checks in so routinely, and has been diligently maintained
since.

llvm-svn: 341831

show more ...