[LV] Record GEP widening decisions in recipe (NFCI)

InnerLoopVectorizer's code called during VPlan execution still relies on
original IR's def-use relations to decide which vector code to generate,

[LV] Record GEP widening decisions in recipe (NFCI)

InnerLoopVectorizer's code called during VPlan execution still relies on
original IR's def-use relations to decide which vector code to generate,
limiting VPlan transformations ability to modify def-use relations and still
have ILV generate the vector code.
This commit moves GEP operand queries controlling how GEPs are widened to a
dedicated recipe and extracts GEP widening code to its own ILV method taking
those recorded decisions as arguments. This reduces ingredient def-use usage by
ILV as a step towards full VPlan-based def-use relations.

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

show more ...

[VPlan] Add dump function to VPlan class.

This adds a dump() function to VPlan, which uses the existing
operator<<.

This method provides a convenient way to dump a VPlan while debugging,
e.g. from

[VPlan] Add dump function to VPlan class.

This adds a dump() function to VPlan, which uses the existing
operator<<.

This method provides a convenient way to dump a VPlan while debugging,
e.g. from lldb.

Reviewers: hsaito, Ayal, gilr, rengolin

Reviewed By: hsaito

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

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

[LV] Apply sink-after & interleave-groups as VPlan transformations (NFCI)

This recommits 11ed1c0239fd51fd2f064311dc7725277ed0a994 (reverted in
9f08ce0d2197d4f163dfa4633eae2347ce8fc881 for failing an

[LV] Apply sink-after & interleave-groups as VPlan transformations (NFCI)

This recommits 11ed1c0239fd51fd2f064311dc7725277ed0a994 (reverted in
9f08ce0d2197d4f163dfa4633eae2347ce8fc881 for failing an assert) with a fix:
tryToWidenMemory() now first checks if the widening decision is to interleave,
thus maintaining previous behavior where tryToInterleaveMemory() was called
first, giving priority to interleave decisions over widening/scalarization. This
commit adds the test case that exposed this bug as a LIT.

show more ...

Revert "[LV] Apply sink-after & interleave-groups as VPlan transformations (NFCI)"

This reverts commit 11ed1c0239fd51fd2f064311dc7725277ed0a994 - causes an assert failure.

[LV] Apply sink-after & interleave-groups as VPlan transformations (NFCI)

This recommits 100e797adb433724a17c9b42b6533cd634cb796b (reverted in
009e032634b3bd7fc32071ac2344b12142286477 for failing an

[LV] Apply sink-after & interleave-groups as VPlan transformations (NFCI)

This recommits 100e797adb433724a17c9b42b6533cd634cb796b (reverted in
009e032634b3bd7fc32071ac2344b12142286477 for failing an assert). While the
root cause was independently reverted in eaff3004019f97c64c88ab76da6b25106b659b30,
this commit includes a LIT to make sure IVDescriptor's SinkAfter logic does not
try to sink branch instructions.

show more ...

Temporarily Revert "[LV] Apply sink-after & interleave-groups as VPlan transformations (NFC)"
as it's causing assert failures.

This reverts commit 100e797adb433724a17c9b42b6533cd634cb796b.

[LV] Apply sink-after & interleave-groups as VPlan transformations (NFC)

This recommits 2be17087f8c38934b7fc9208ae6cf4e9b4d44f4b (reverted in
d3ec06d219788801380af1948c7f7ef9d3c6100b for heap-use-af

[LV] Apply sink-after & interleave-groups as VPlan transformations (NFC)

This recommits 2be17087f8c38934b7fc9208ae6cf4e9b4d44f4b (reverted in
d3ec06d219788801380af1948c7f7ef9d3c6100b for heap-use-after-free) with a fix
in IAI's reset() which was not clearing the set of interleave groups after
deleting them.

show more ...

Revert "[LV] Apply sink-after & interleave-groups as VPlan transformations (NFC)"

This reverts commit 2be17087f8c38934b7fc9208ae6cf4e9b4d44f4b. Fails ASAN.

[LV] Apply sink-after & interleave-groups as VPlan transformations (NFC)

The sink-after and interleave-group vectorization decisions were so far applied to
VPlan during initial VPlan construction, w

[LV] Apply sink-after & interleave-groups as VPlan transformations (NFC)

The sink-after and interleave-group vectorization decisions were so far applied to
VPlan during initial VPlan construction, which complicates VPlan construction – also because of
their inter-dependence. This patch refactors buildVPlanWithRecipes() to construct a simpler
initial VPlan and later apply both these vectorization decisions, in order, as VPlan-to-VPlan
transformations.

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

show more ...

[VPlan] Add moveAfter to VPRecipeBase.

This patch adds a moveAfter method to VPRecipeBase, which can be used to
move elements after other elements, across VPBasicBlocks, if necessary.

Reviewers: dc

[VPlan] Add moveAfter to VPRecipeBase.

This patch adds a moveAfter method to VPRecipeBase, which can be used to
move elements after other elements, across VPBasicBlocks, if necessary.

Reviewers: dcaballe, hsaito, rengolin, hfinkel

Reviewed By: dcaballe

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

llvm-svn: 374565

show more ...

[Alignment][NFC] Make VectorUtils uas llvm::Align

Summary:
This is patch is part of a series to introduce an Alignment type.
See this thread for context: http://lists.llvm.org/pipermail/llvm-dev/201

[Alignment][NFC] Make VectorUtils uas llvm::Align

Summary:
This is patch is part of a series to introduce an Alignment type.
See this thread for context: http://lists.llvm.org/pipermail/llvm-dev/2019-July/133851.html
See this patch for the introduction of the type: https://reviews.llvm.org/D64790

Reviewers: courbet

Subscribers: hiraditya, rogfer01, llvm-commits

Tags: #llvm

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

llvm-svn: 374330

show more ...

[LV] Fold tail by masking - handle reductions

Allow vectorizing loops that have reductions when tail is folded by masking.
A select is introduced in VPlan, choosing between the last value carried by

[LV] Fold tail by masking - handle reductions

Allow vectorizing loops that have reductions when tail is folded by masking.
A select is introduced in VPlan, choosing between the last value carried by the
loop-exit/live-out instruction of the reduction, and the penultimate value
carried by the reduction phi, according to the "i < n" mask of fold-tail.
This select replaces the last value as the live-out value of the loop.

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

llvm-svn: 370173

show more ...

[VPlan] Fix "value never used" static analyzer warning. NFCI.

llvm-svn: 360241

[LV][VPlan] Change to implement VPlan based predication for
VPlan-native path

Context: Patch Series #2 for outer loop vectorization support in LV
using VPlan. (RFC:
http://lists.llvm.org/pipermail/l

[LV][VPlan] Change to implement VPlan based predication for
VPlan-native path

Context: Patch Series #2 for outer loop vectorization support in LV
using VPlan. (RFC:
http://lists.llvm.org/pipermail/llvm-dev/2017-December/119523.html).

Patch series #2 checks that inner loops are still trivially lock-step
among all vector elements. Non-loop branches are blindly assumed as
divergent.

Changes here implement VPlan based predication algorithm to compute
predicates for blocks that need predication. Predicates are computed
for the VPLoop region in reverse post order. A block's predicate is
computed as OR of the masks of all incoming edges. The mask for an
incoming edge is computed as AND of predecessor block's predicate and
either predecessor's Condition bit or NOT(Condition bit) depending on
whether the edge from predecessor block to the current block is true
or false edge.

Reviewers: fhahn, rengolin, hsaito, dcaballe

Reviewed By: fhahn

Patch by Satish Guggilla, thanks!

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

llvm-svn: 351990

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

[IR] Add hasNPredecessors, hasNPredecessorsOrMore to BasicBlock

Add methods to BasicBlock which make it easier to efficiently check
whether a block has N (or more) predecessors.

This can be more ef

[IR] Add hasNPredecessors, hasNPredecessorsOrMore to BasicBlock

Add methods to BasicBlock which make it easier to efficiently check
whether a block has N (or more) predecessors.

This can be more efficient than using pred_size(), which is a linear
time operation.

We might consider adding similar methods for successors. I haven't done
so in this patch because succ_size() is already O(1).

With this patch applied, I measured a 0.065% compile-time reduction in
user time for running `opt -O3` on the sqlite3 amalgamation (30 trials).
The change in mergeStoreIntoSuccessor alone saves 45 million linked list
iterations in a stage2 Release build of llc.

See llvm.org/PR39702 for a harder but more general way of achieving
similar results.

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

llvm-svn: 347256

show more ...

[VPlan, SLP] Add simple SLP analysis on top of VPlan.

This patch adds an initial implementation of the look-ahead SLP tree
construction described in 'Look-Ahead SLP: Auto-vectorization in the Presen

[VPlan, SLP] Add simple SLP analysis on top of VPlan.

This patch adds an initial implementation of the look-ahead SLP tree
construction described in 'Look-Ahead SLP: Auto-vectorization in the Presence
of Commutative Operations, CGO 2018 by Vasileios Porpodas, Rodrigo C. O. Rocha,
Luís F. W. Góes'.

It returns an SLP tree represented as VPInstructions, with combined
instructions represented as a single, wider VPInstruction.

This initial version does not support instructions with multiple
different users (either inside or outside the SLP tree) or
non-instruction operands; it won't generate any shuffles or
insertelement instructions.

It also just adds the analysis that builds an SLP tree rooted in a set
of stores. It does not include any cost modeling or memory legality
checks. The plan is to integrate it with VPlan based cost modeling, once
available and to only apply it to operations that can be widened.

A follow-up patch will add a support for replacing instructions in a
VPlan with their SLP counter parts.

Reviewers: Ayal, mssimpso, rengolin, mkuper, hfinkel, hsaito, dcaballe, vporpo, RKSimon, ABataev

Reviewed By: rengolin

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

llvm-svn: 346857

show more ...

[VPlan] VPlan version of InterleavedAccessInfo.

This patch turns InterleaveGroup into a template with the instruction type
being a template parameter. It also adds a VPInterleavedAccessInfo class, w

[VPlan] VPlan version of InterleavedAccessInfo.

This patch turns InterleaveGroup into a template with the instruction type
being a template parameter. It also adds a VPInterleavedAccessInfo class, which
only contains a mapping from VPInstructions to their respective InterleaveGroup.
As we do not have access to scalar evolution in VPlan, we can re-use
convert InterleavedAccessInfo to VPInterleavedAccess info.


Reviewers: Ayal, mssimpso, hfinkel, dcaballe, rengolin, mkuper, hsaito

Reviewed By: rengolin

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

llvm-svn: 346758

show more ...

[LV] Fold tail by masking to vectorize loops of arbitrary trip count under opt for size

When optimizing for size, a loop is vectorized only if the resulting vector loop
completely replaces the origi

[LV] Fold tail by masking to vectorize loops of arbitrary trip count under opt for size

When optimizing for size, a loop is vectorized only if the resulting vector loop
completely replaces the original scalar loop. This holds if no runtime guards
are needed, if the original trip-count TC does not overflow, and if TC is a
known constant that is a multiple of the VF. The last two TC-related conditions
can be overcome by
1. rounding the trip-count of the vector loop up from TC to a multiple of VF;
2. masking the vector body under a newly introduced "if (i <= TC-1)" condition.

The patch allows loops with arbitrary trip counts to be vectorized under -Os,
subject to the existing cost model considerations. It also applies to loops with
small trip counts (under -O2) which are currently handled as if under -Os.

The patch does not handle loops with reductions, live-outs, or w/o a primary
induction variable, and disallows interleave groups.

(Third, final and main part of -)
Differential Revision: https://reviews.llvm.org/D50480

llvm-svn: 344743

show more ...

[VPlan] Fix CondBit quoting in dumpBasicBlock

Quotes were being printed for VPInstructions but not the rest.

llvm-svn: 344161

Fix for the buildbot failure http://lab.llvm.org:8011/builders/sanitizer-x86_64-linux-fast/builds/23635
from the commit (r342197) of https://reviews.llvm.org/D50820.

llvm-svn: 342201

[VPlan] Implement initial vector code generation support for simple outer loops.

Summary:
[VPlan] Implement vector code generation support for simple outer loops.

Context: Patch Series #1 for outer

[VPlan] Implement initial vector code generation support for simple outer loops.

Summary:
[VPlan] Implement vector code generation support for simple outer loops.

Context: Patch Series #1 for outer loop vectorization support in LV using VPlan. (RFC: http://lists.llvm.org/pipermail/llvm-dev/2017-December/119523.html).

This patch introduces vector code generation support for simple outer loops that are currently supported in the VPlanNativePath. Changes here essentially do the following:

- force vector code generation using explicit vectorize_width

- add conservative early returns in cost model and other places for VPlanNativePath

- add code for setting up outer loop inductions

- support for widening non-induction PHIs that can result from inner loops and uniform conditional branches

- support for generating uniform inner branches

We plan to add a handful C outer loop executable tests once the initial code generation support is committed. This patch is expected to be NFC for the inner loop vectorizer path. Since we are moving in the direction of supporting outer loop vectorization in LV, it may also be time to rename classes such as InnerLoopVectorizer.

Reviewers: fhahn, rengolin, hsaito, dcaballe, mkuper, hfinkel, Ayal

Reviewed By: fhahn, hsaito

Subscribers: dmgreen, bollu, tschuett, rkruppe, rogfer01, llvm-commits

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

llvm-svn: 342197

show more ...

[VPlan] Introduce VPlan-based dominator analysis.

The patch introduces dominator analysis for VPBlockBases and extend
VPlan's GraphTraits specialization with the required interfaces. Dominator
analy

[VPlan] Introduce VPlan-based dominator analysis.

The patch introduces dominator analysis for VPBlockBases and extend
VPlan's GraphTraits specialization with the required interfaces. Dominator
analysis will be necessary to perform some H-CFG transformations and
to introduce VPLoopInfo (LoopInfo analysis on top of the VPlan representation).

Reviewers: fhahn, rengolin, mkuper, hfinkel, mssimpso

Reviewed By: fhahn

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

llvm-svn: 338310

show more ...

[VPlan][LV] Introduce condition bit in VPBlockBase

This patch introduces a VPValue in VPBlockBase to represent the condition
bit that is used as successor selector when a block has multiple successo

[VPlan][LV] Introduce condition bit in VPBlockBase

This patch introduces a VPValue in VPBlockBase to represent the condition
bit that is used as successor selector when a block has multiple successors.
This information wasn't necessary until now, when we are about to introduce
outer loop vectorization support in VPlan code gen.

Reviewers: fhahn, rengolin, mkuper, hfinkel, mssimpso

Reviewed By: fhahn

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

llvm-svn: 336554

show more ...