Revert "[LV] Unconditionally branch from middle to scalar preheader if the scalar loop must execute"

This reverts commit 3e5ce49e5371ce4feadbf97dd5c2b652d9db3d1d.

Tests started failing on PPC, for

Revert "[LV] Unconditionally branch from middle to scalar preheader if the scalar loop must execute"

This reverts commit 3e5ce49e5371ce4feadbf97dd5c2b652d9db3d1d.

Tests started failing on PPC, for example:
http://lab.llvm.org:8011/#/builders/105/builds/5569

show more ...

[LV] Unconditionally branch from middle to scalar preheader if the scalar loop must execute

If we know that the scalar epilogue is required to run, modify the CFG to end the middle block with an unc

[LV] Unconditionally branch from middle to scalar preheader if the scalar loop must execute

If we know that the scalar epilogue is required to run, modify the CFG to end the middle block with an unconditional branch to scalar preheader. This is instead of a conditional branch to either the preheader or the exit block.

The motivation to do this is to support multiple exit blocks. Specifically, the current structure forces us to identify immediate dominators and *which* exit block to branch from in the middle terminator. For the multiple exit case - where we know require scalar will hold - these questions are ill formed.

This is the last change needed to support multiple exit loops, but since the diffs are already large enough, I'm going to land this, and then enable separately. You can think of this as being NFCI-ish prep work, but the changes are a bit too involved for me to feel comfortable tagging the change that way.

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

show more ...

[LoopUtils] Pass SCEVExpander instead SE to addRuntimeChecks.

This gives the user control over which expander to use, which in turn
allows the user to decide what to do with the expanded instruction

[LoopUtils] Pass SCEVExpander instead SE to addRuntimeChecks.

This gives the user control over which expander to use, which in turn
allows the user to decide what to do with the expanded instructions.

Used in D75980.

Reviewed By: lebedev.ri

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

show more ...

[LV] Weaken spuriously strong assert in LoopVersioning

LoopVectorize uses some utilities on LoopVersioning, but doesn't actually use it for, you know, versioning. As a result, the precondition Loop

[LV] Weaken spuriously strong assert in LoopVersioning

LoopVectorize uses some utilities on LoopVersioning, but doesn't actually use it for, you know, versioning. As a result, the precondition LoopVersioning expects is too strong for this user. At the moment, LoopVectorize supports any loop with a unique exit block, so check the same precondition here.

Really, the whole class structure here is a mess. We should separate the actual versioning from the metadata updates, but that's a bigger problem.

show more ...

[LV] Set up branch from middle block earlier.

Previously the branch from the middle block to the scalar preheader & exit
was being set-up at the end of skeleton creation in completeLoopSkeleton.
Ins

[LV] Set up branch from middle block earlier.

Previously the branch from the middle block to the scalar preheader & exit
was being set-up at the end of skeleton creation in completeLoopSkeleton.
Inserting SCEV or runtime checks may result in LCSSA phis being created,
if they are required. Adjusting branches afterwards may break those
PHIs.

To avoid this, we can instead create the branch from the middle block
to the exit after we created the middle block, so we have the final CFG
before potentially adjusting/creating PHIs.

This fixes a crash for the included test case. For the non-crashing
case, this is almost a NFC with respect to the generated code. The
only change is the order of the predecessors of the involved branch
targets.

Note an assertion was moved from LoopVersioning() to
LoopVersioning::versionLoop. Adjusting the branches means loop-simplify
form may be broken before constructing LoopVersioning. But LV only uses
LoopVersioning to annotate the loop instructions with !noalias metadata,
which does not require loop-simplify form.

This is a fix for an existing issue uncovered by D93317.

show more ...

[NFC] Reduce include files dependency and AA header cleanup (part 2).

Continuing work started in https://reviews.llvm.org/D92489:

Removed a bunch of includes from "AliasAnalysis.h" and "LoopPassMan

[NFC] Reduce include files dependency and AA header cleanup (part 2).

Continuing work started in https://reviews.llvm.org/D92489:

Removed a bunch of includes from "AliasAnalysis.h" and "LoopPassManager.h".

Reviewed By: RKSimon

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

show more ...

[LAA] Relax restrictions on early exits in loop structure

his is a preparation patch for supporting multiple exits in the loop vectorizer, by itself it should be mostly NFC. This patch moves the loo

[LAA] Relax restrictions on early exits in loop structure

his is a preparation patch for supporting multiple exits in the loop vectorizer, by itself it should be mostly NFC. This patch moves the loop structure checks from LAA to their respective consumers (where duplicates don't already exist). Moving the checks does end up changing some of the optimization warnings and debug output slightly, but nothing that appears to be a regression.

Why do this? Well, after auditing the code, I can't actually find anything in LAA itself which relies on having all instructions within a loop execute an equal number of times. This patch simply makes this explicit so that if one consumer - say LV in the near future (hopefully) - wants to handle a broader class of loops, it can do so.

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

show more ...

[LoopVersioning] Form dedicated exits for versioned loop to preserve simplify form

The exit blocks of the versioned and non-versioned loops are not dedicated and thus the two loops are not in simpli

[LoopVersioning] Form dedicated exits for versioned loop to preserve simplify form

The exit blocks of the versioned and non-versioned loops are not dedicated and thus the two loops are not in simplify form.
Insert dummy exit blocks after loop versioning with `formDedicatedExits()` to preserve the simplify form for subsequence passes.

Reviewed By: aeubanks

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

show more ...

[LoopVersion] Unify SCEVChecks and alias check handling (NFC).

This is an initial cleanup of the way LoopVersioning interacts with LAA.

Currently LoopVersioning has 2 ways of initializing things:

[LoopVersion] Unify SCEVChecks and alias check handling (NFC).

This is an initial cleanup of the way LoopVersioning interacts with LAA.

Currently LoopVersioning has 2 ways of initializing things:

1. Passing LAI and passing UseLAIChecks = true
2. Passing UseLAIChecks = false, followed by calling setSCEVChecks and
setAliasChecks.

Both ways of initializing lead to the same result and the duplication
seems more complicated than necessary.

This patch removes the UseLAIChecks flag from the constructor and the
setSCEVChecks & setAliasChecks helpers and move initialization
exclusively to the constructor.

This simplifies things, by providing a single way to initialize
LoopVersioning and reducing duplication.

Reviewed By: Meinersbur, lebedev.ri

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

show more ...

[LoopInfo] empty() -> isInnermost(), add isOutermost()

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

[BFI] Make BFI information available through loop passes inside LoopStandardAnalysisResults

~~D65060 uncovered that trying to use BFI in loop passes can lead to non-deterministic behavior when block

[BFI] Make BFI information available through loop passes inside LoopStandardAnalysisResults

~~D65060 uncovered that trying to use BFI in loop passes can lead to non-deterministic behavior when blocks are re-used while retaining old BFI data.~~

~~To make sure BFI is preserved through loop passes a Value Handle (VH) callback is registered on blocks themselves. When a block is freed it now also wipes out the accompanying BFI entry such that stale BFI data can no longer persist resolving the determinism issue. ~~

~~An optimistic approach would be to incrementally update BFI information throughout the loop passes rather than only invalidating them on removed blocks. The issues with that are:~~
~~1. It is not clear how BFI information should be incrementally updated: If a block is duplicated does its BFI information come with? How about if it's split/modified/moved around? ~~
~~2. Assuming we can address these problems the implementation here will be a massive undertaking. ~~

~~There's a known need of BFI in LICM analysis which requires correct but not incrementally updated BFI data. A follow-up change can register BFI in all loop passes so this preserved but potentially lossy data is available to any loop pass that wants it.~~

See: D75341 for an identical implementation of preserving BFI via VH callbacks. The previous statements do still apply but this change no longer has to be in this diff because it's already upstream �� .

This diff also moves BFI to be a part of LoopStandardAnalysisResults since the previous method using getCachedResults now (correctly!) statically asserts (D72893) that this data isn't static through the loop passes.

Testing
Ninja check

Reviewed By: asbirlea, nikic

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

show more ...

Fix layering violation Transforms/Utils -> Scalar

Introduced in D85063.

[NewPM][LoopVersioning] Port LoopVersioning to NPM

Reviewed By: ychen, fhahn

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

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

[LoopVersioning] Update setAliasChecks to take ArrayRef argument (NFC).

This cleanup was suggested as part of D78458.

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

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

This reverts commit 51ef53f3bd23559203fe9af82ff2facbfedc1db3, as it
breaks some bots.

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

Reviewers: sanjoy.google, efriedma, reames

Reviewed By: sanjoy.google

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

show more ...

Add missing includes needed to prune LLVMContext.h include, NFC

These are a pre-requisite to removing #include "llvm/Support/Options.h"
from LLVMContext.h: https://reviews.llvm.org/D70280

Sink all InitializePasses.h includes

This file lists every pass in LLVM, and is included by Pass.h, which is
very popular. Every time we add, remove, or rename a pass in LLVM, it
caused lots of reco

Sink all InitializePasses.h includes

This file lists every pass in LLVM, and is included by Pass.h, which is
very popular. Every time we add, remove, or rename a pass in LLVM, it
caused lots of recompilation.

I found this fact by looking at this table, which is sorted by the
number of times a file was changed over the last 100,000 git commits
multiplied by the number of object files that depend on it in the
current checkout:
recompiles touches affected_files header
342380 95 3604 llvm/include/llvm/ADT/STLExtras.h
314730 234 1345 llvm/include/llvm/InitializePasses.h
307036 118 2602 llvm/include/llvm/ADT/APInt.h
213049 59 3611 llvm/include/llvm/Support/MathExtras.h
170422 47 3626 llvm/include/llvm/Support/Compiler.h
162225 45 3605 llvm/include/llvm/ADT/Optional.h
158319 63 2513 llvm/include/llvm/ADT/Triple.h
140322 39 3598 llvm/include/llvm/ADT/StringRef.h
137647 59 2333 llvm/include/llvm/Support/Error.h
131619 73 1803 llvm/include/llvm/Support/FileSystem.h

Before this change, touching InitializePasses.h would cause 1345 files
to recompile. After this change, touching it only causes 550 compiles in
an incremental rebuild.

Reviewers: bkramer, asbirlea, bollu, jdoerfert

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

show more ...

[BasicBlockUtils] Add optional BBName argument, in line with BB:splitBasicBlock

Reviewers: spatel, asbirlea, craig.topper

Reviewed By: asbirlea

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

[BasicBlockUtils] Add optional BBName argument, in line with BB:splitBasicBlock

Reviewers: spatel, asbirlea, craig.topper

Reviewed By: asbirlea

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

llvm-svn: 371819

show more ...

LoopVersioning: Respect convergent

This changes the standalone pass only. Arguably the utility class
itself should assert there are no convergent calls. However, a target
pass with additional contex

LoopVersioning: Respect convergent

This changes the standalone pass only. Arguably the utility class
itself should assert there are no convergent calls. However, a target
pass with additional context may still be able to version a loop if
all of the dynamic conditions are sufficiently uniform.

llvm-svn: 363165

show more ...

Update the file headers across all of the LLVM projects in the monorepo
to reflect the new license.

We understand that people may be surprised that we're moving the header
entirely to discuss the ne

Update the file headers across all of the LLVM projects in the monorepo
to reflect the new license.

We understand that people may be surprised that we're moving the header
entirely to discuss the new license. We checked this carefully with the
Foundation's lawyer and we believe this is the correct approach.

Essentially, all code in the project is now made available by the LLVM
project under our new license, so you will see that the license headers
include that license only. Some of our contributors have contributed
code under our old license, and accordingly, we have retained a copy of
our old license notice in the top-level files in each project and
repository.

llvm-svn: 351636

show more ...

[LoopVersioning] Don't modify the list that we iterate over in addPHINodes

Summary:
In LoopVersioning::addPHINodes we need to iterate over all
users for a value "Inst", and if the user is outside of

[LoopVersioning] Don't modify the list that we iterate over in addPHINodes

Summary:
In LoopVersioning::addPHINodes we need to iterate over all
users for a value "Inst", and if the user is outside of the
VersionedLoop we should replace the use of "Inst" by using
the value "PN" instead.

Replacing the use of "Inst" for a user of "Inst" also means
that Inst->users() is modified. So it is not safe to do the
replace while iterating over Inst->users() as we used to do.
This patch splits the task into two steps. First we iterate
over Inst->users() to find all users that should be updated.
Those users are saved into a local data structure on the stack.
And then, in the second step, we do the actual updates. This
time iterating over the local data structure.

Reviewers: mzolotukhin, anemet

Reviewed By: mzolotukhin

Subscribers: llvm-commits

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

llvm-svn: 332958

show more ...