[LoopDeletion] Forget loop before setting values to undef

After D71539, we need to forget the loop before setting the incoming
values of phi nodes in exit blocks, because we are looking through thos

[LoopDeletion] Forget loop before setting values to undef

After D71539, we need to forget the loop before setting the incoming
values of phi nodes in exit blocks, because we are looking through those
phi nodes now and the SCEV expression could depend on the loop phi. If
we update the phi nodes before forgetting the loop, we miss those users
during invalidation.

Reviewed By: reames

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

show more ...

[NFC] GetUnderlyingObject -> getUnderlyingObject

I am going to touch them in the next patch anyway

DomTree: Remove getChildren() accessor

Summary:
Avoid exposing details about how children are stored. This will enable
subsequent type-erasure changes.

New methods are introduced to cover common ac

DomTree: Remove getChildren() accessor

Summary:
Avoid exposing details about how children are stored. This will enable
subsequent type-erasure changes.

New methods are introduced to cover common access patterns.

Change-Id: Idb5f4b1b9c84e4cc71ddb39bb52a388682f5674f

Reviewers: arsenm, RKSimon, mehdi_amini, courbet

Subscribers: qcolombet, sdardis, wdng, hiraditya, jrtc27, zzheng, atanasyan, asbirlea, llvm-commits

Tags: #llvm

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

show more ...

Revert "[Peeling] Extend the scope of peeling a bit"

This reverts commit 29b2c1ca72096ca06415b5e626e6728c42ef1e74.

The patch causes the DT verifier failure like:
DominatorTree is different than a f

Revert "[Peeling] Extend the scope of peeling a bit"

This reverts commit 29b2c1ca72096ca06415b5e626e6728c42ef1e74.

The patch causes the DT verifier failure like:
DominatorTree is different than a freshly computed one!

Not sure the patch itself it wrong but revert to investigate the failure.

show more ...

[Peeling] Extend the scope of peeling a bit

Currently we allow peeling of the loops if there is a exiting latch block
and all other exits are blocks ending with deopt.

Actually we want that exit wo

[Peeling] Extend the scope of peeling a bit

Currently we allow peeling of the loops if there is a exiting latch block
and all other exits are blocks ending with deopt.

Actually we want that exit would end up with deopt unconditionally but
it is not required that exit itself ends with deopt.

Reviewers: reames, ashlykov, fhahn, apilipenko, fedor.sergeev
Reviewed By: apilipenko
Subscribers: hiraditya, zzheng, dantrushin, llvm-commits
Differential Revision: https://reviews.llvm.org/D81140

show more ...

[SVE] Remove calls to VectorType::getNumElements from Transforms/Utils

Reviewers: efriedma, c-rhodes, david-arm, Tyker, asbirlea

Reviewed By: david-arm

Subscribers: tschuett, hiraditya, rkruppe, p

[SVE] Remove calls to VectorType::getNumElements from Transforms/Utils

Reviewers: efriedma, c-rhodes, david-arm, Tyker, asbirlea

Reviewed By: david-arm

Subscribers: tschuett, hiraditya, rkruppe, psnobl, llvm-commits

Tags: #llvm

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

show more ...

[IRBuilder] add/use wrapper to create a generic compare based on predicate type; NFC

The predicate can always be used to distinguish between icmp and fcmp,
so we don't need to keep repeating this ch

[IRBuilder] add/use wrapper to create a generic compare based on predicate type; NFC

The predicate can always be used to distinguish between icmp and fcmp,
so we don't need to keep repeating this check in the callers.

show more ...

Verify MemorySSA after all updates.

Verify after completing all updates.
Resolves PR46275.

[LoopUtils] Use llvm::find

Summary: Fixes this build error:

llvm/lib/Transforms/Utils/LoopUtils.cpp:679:26: error: no matching
function for call to 'find'
Loop::iterator I = find(ParentLoop->

[LoopUtils] Use llvm::find

Summary: Fixes this build error:

llvm/lib/Transforms/Utils/LoopUtils.cpp:679:26: error: no matching
function for call to 'find'
Loop::iterator I = find(ParentLoop->begin(), ParentLoop->end(),
L);
^~~~
Authored By: orivej
Reviewer: Whitney
Reviewed By: Whitney
Subscribers: hiraditya, llvm-commits
Tag: LLVM
Differential Revision: https://reviews.llvm.org/D80473

show more ...

[IndVarSimplify][LoopUtils] Avoid TOCTOU/ordering issues (PR45835)

Summary:
Currently, `rewriteLoopExitValues()`'s logic is roughly as following:
> Loop over each incoming value in each PHI node.
>

[IndVarSimplify][LoopUtils] Avoid TOCTOU/ordering issues (PR45835)

Summary:
Currently, `rewriteLoopExitValues()`'s logic is roughly as following:
> Loop over each incoming value in each PHI node.
> Query whether the SCEV for that incoming value is high-cost.
> Expand the SCEV.
> Perform sanity check (`isValidRewrite()`, D51582)
> Record the info
> Afterwards, see if we can drop the loop given replacements.
> Maybe perform replacements.

The problem is that we interleave SCEV cost checking and expansion.
This is A Problem, because `isHighCostExpansion()` takes special care
to not bill for the expansions that were already expanded, and we can reuse.

While it makes sense in general - if we know that we will expand some SCEV,
all the other SCEV's costs should account for that, which might cause
some of them to become non-high-cost too, and cause chain reaction.

But that isn't what we are doing here. We expand *all* SCEV's, unconditionally.
So every next SCEV's cost will be affected by the already-performed expansions
for previous SCEV's. Even if we are not planning on keeping
some of the expansions we performed.

Worse yet, this current "bonus" depends on the exact PHI node
incoming value processing order. This is completely wrong.

As an example of an issue, see @dmajor's `pr45835.ll` - if we happen to have
a PHI node with two(!) identical high-cost incoming values for the same basic blocks,
we would decide first time around that it is high-cost, expand it,
and immediately decide that it is not high-cost because we have an expansion
that we could reuse (because we expanded it right before, temporarily),
and replace the second incoming value but not the first one;
thus resulting in a broken PHI.

What we instead should do for now, is not perform any expansions
until after we've queried all the costs.

Later, in particular after `isValidRewrite()` is an assertion (D51582)
we could improve upon that, but in a more coherent fashion.

See [[ https://bugs.llvm.org/show_bug.cgi?id=45835 | PR45835 ]]

Reviewers: dmajor, reames, mkazantsev, fhahn, efriedma

Reviewed By: dmajor, mkazantsev

Subscribers: smeenai, nikic, hiraditya, javed.absar, llvm-commits, dmajor

Tags: #llvm

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

show more ...

[SCEV] Move ScalarEvolutionExpander.cpp to Transforms/Utils (NFC).

SCEVExpander modifies the underlying function so it is more suitable in
Transforms/Utils, rather than Analysis. This allows using o

[SCEV] Move ScalarEvolutionExpander.cpp to Transforms/Utils (NFC).

SCEVExpander modifies the underlying function so it is more suitable in
Transforms/Utils, rather than Analysis. This allows using other
transform utils in SCEVExpander.

This patch was originally committed as b8a3c34eee06, but broke the
modules build, as LoopAccessAnalysis was using the Expander.

The code-gen part of LAA was moved to lib/Transforms recently, so this
patch can be landed again.

Reviewers: sanjoy.google, efriedma, reames

Reviewed By: sanjoy.google

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

show more ...

[LAA] Move runtime-check generation to Transforms/Utils/loopUtils (NFC)

Currently LAA's uses of ScalarEvolutionExpander blocks moving the
expander from Analysis to Transforms. Conceptually the expan

[LAA] Move runtime-check generation to Transforms/Utils/loopUtils (NFC)

Currently LAA's uses of ScalarEvolutionExpander blocks moving the
expander from Analysis to Transforms. Conceptually the expander does not
fit into Analysis (it is only used for code generation) and
runtime-check generation also seems to be better suited as a
transformation utility.

Reviewers: Ayal, anemet

Reviewed By: Ayal

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

show more ...

[LAA] Move CheckingPtrGroup/PointerCheck outside class (NFC).

This allows forward declarations of PointerCheck, which in turn reduce
the number of times LoopAccessAnalysis needs to be included.

Ult

[LAA] Move CheckingPtrGroup/PointerCheck outside class (NFC).

This allows forward declarations of PointerCheck, which in turn reduce
the number of times LoopAccessAnalysis needs to be included.

Ultimately this helps with moving runtime check generation to
Transforms/Utils/LoopUtils.h, without having to include it there.

Reviewers: anemet, Ayal

Reviewed By: Ayal

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

show more ...

[LoopUtils] Clean up includes, use forward decls if appropriate (NFC).

Most of the includes in LoopUtils.h are not required in the header and
they can be replaced by forward declarations.

Unfortuna

[LoopUtils] Clean up includes, use forward decls if appropriate (NFC).

Most of the includes in LoopUtils.h are not required in the header and
they can be replaced by forward declarations.

Unfortunately includes of TargetTransformInfo.h and IVDescriptors.h pull
in a bunch of additional things, but there is no easy way to get rid of
them at the moment I think.

show more ...

Upgrade calls to CreateShuffleVector to use the preferred form of passing an array of ints

No functionality change intended.

Clean up usages of asserting vector getters in Type

Summary:
Remove usages of asserting vector getters in Type in preparation for the
VectorType refactor. The existence of these functions complicate

Clean up usages of asserting vector getters in Type

Summary:
Remove usages of asserting vector getters in Type in preparation for the
VectorType refactor. The existence of these functions complicates the
refactor while adding little value.

Reviewers: rriddle, sdesmalen, efriedma

Reviewed By: sdesmalen

Subscribers: hiraditya, llvm-commits

Tags: #llvm

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

show more ...

Revert "[SCEV] rewriteLoopExitValues(): even if have hard uses, still rewrite if cheap (PR44668)"

As discussed in post-commit review in https://reviews.llvm.org/D73501
if the goal of this is to help

Revert "[SCEV] rewriteLoopExitValues(): even if have hard uses, still rewrite if cheap (PR44668)"

As discussed in post-commit review in https://reviews.llvm.org/D73501
if the goal of this is to help vectorizer, then we should actually
be teaching vectorizer to do this, because right now this rewrite
is still budget-limited, which isn't what we'd want.

Additionally, while the rest of the patch series was universally profitable,
this particular patch is reportedly (https://reviews.llvm.org/D73501#1905171)
exposing cost-modeling issues on ARM.

So let's just back this particular patch out. Once there's an undo transform,
this could be considered for reintegration.

This reverts commit 44edc6fd2c63b7db43e13cc8caf1fee79bebdb5f.

show more ...

[LoopVectorizer] Add reduction tests for inloop reductions. NFC

Also adds a force-reduction-intrinsics option for testing, for forcing
the generation of reduction intrinsics even when the backend is

[LoopVectorizer] Add reduction tests for inloop reductions. NFC

Also adds a force-reduction-intrinsics option for testing, for forcing
the generation of reduction intrinsics even when the backend is not
requesting them.

show more ...

[Loop Peeling] Add possibility to enable peeling on loop nests.

Summary:
Current peeling implementation bails out in case of loop nests.
The patch introduces a field in TargetTransformInfo structure

[Loop Peeling] Add possibility to enable peeling on loop nests.

Summary:
Current peeling implementation bails out in case of loop nests.
The patch introduces a field in TargetTransformInfo structure that
certain targets can use to relax the constraints if it's
profitable (disabled by default).
Also additional option is added to enable peeling manually for
experimenting and testing purposes.

Reviewers: fhahn, lebedev.ri, xbolva00

Reviewed By: xbolva00

Subscribers: RKSimon, xbolva00, hiraditya, zzheng, llvm-commits

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

show more ...

[SCEV] rewriteLoopExitValues(): even if have hard uses, still rewrite if cheap (PR44668)

Summary:
Replacing uses of IV outside of the loop is likely generally useful,
but `rewriteLoopExitValues()` i

[SCEV] rewriteLoopExitValues(): even if have hard uses, still rewrite if cheap (PR44668)

Summary:
Replacing uses of IV outside of the loop is likely generally useful,
but `rewriteLoopExitValues()` is cautious, and if it isn't told to always
perform the replacement, and there are hard uses of IV in loop,
it doesn't replace.

In [[ https://bugs.llvm.org/show_bug.cgi?id=44668 | PR44668 ]],
that prevents `-indvars` from replacing uses of induction variable
after the loop, which might be one of the optimization failures
preventing that code from being vectorized.

Instead, now that the cost model is fixed, i believe we should be
a little bit more optimistic, and also perform replacement
if we believe it is within our budget.

Fixes [[ https://bugs.llvm.org/show_bug.cgi?id=44668 | PR44668 ]].

Reviewers: reames, mkazantsev, asbirlea, fhahn, skatkov

Reviewed By: mkazantsev

Subscribers: nikic, hiraditya, zzheng, javed.absar, dmgreen, llvm-commits

Tags: #llvm

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

show more ...

[NFC][SCEV] Piping to pass new SCEVCheapExpansionBudget option into SCEVExpander::isHighCostExpansionHelper()

Summary:
In future patches`SCEVExpander::isHighCostExpansionHelper()` will respect the b

[NFC][SCEV] Piping to pass new SCEVCheapExpansionBudget option into SCEVExpander::isHighCostExpansionHelper()

Summary:
In future patches`SCEVExpander::isHighCostExpansionHelper()` will respect the budget allocated by performing TTI cost modelling.
This is a fully NFC patch to make things reviewable.

Reviewers: reames, mkazantsev, wmi, sanjoy

Reviewed By: mkazantsev

Subscribers: hiraditya, zzheng, javed.absar, llvm-commits

Tags: #llvm

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

show more ...

[NFC][SCEV] Piping to pass TTI into SCEVExpander::isHighCostExpansionHelper()

Summary:
Future patches will make use of TTI to perform cost-model-driven `SCEVExpander::isHighCostExpansionHelper()`
Th

[NFC][SCEV] Piping to pass TTI into SCEVExpander::isHighCostExpansionHelper()

Summary:
Future patches will make use of TTI to perform cost-model-driven `SCEVExpander::isHighCostExpansionHelper()`
This is a fully NFC patch to make things reviewable.

Reviewers: reames, mkazantsev, wmi, sanjoy

Reviewed By: mkazantsev

Subscribers: hiraditya, zzheng, javed.absar, dmgreen, llvm-commits

Tags: #llvm

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

show more ...

[LoopUtils] Accept IRBuilderBase; NFC

[IRCE] Make IRCE a Function pass.

Summary: Make InductiveRangeCheckElimination a FunctionPass.

Reviewers: reames, mkazantsev

Subscribers: hiraditya, llvm-commits

Tags: #llvm

Differential Revisio

[IRCE] Make IRCE a Function pass.

Summary: Make InductiveRangeCheckElimination a FunctionPass.

Reviewers: reames, mkazantsev

Subscribers: hiraditya, llvm-commits

Tags: #llvm

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

show more ...

[LoopUtils] Make duplicate method a utility. [NFCI]

Summary:
Method appendLoopsToWorklist is duplicate in LoopUnroll and in the
LoopPassManager as an internal method. Make it an utility.

Reviewers:

[LoopUtils] Make duplicate method a utility. [NFCI]

Summary:
Method appendLoopsToWorklist is duplicate in LoopUnroll and in the
LoopPassManager as an internal method. Make it an utility.

Reviewers: dmgreen, chandlerc, fedor.sergeev, yamauchi

Subscribers: mehdi_amini, hiraditya, zzheng, llvm-commits

Tags: #llvm

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

show more ...