[LoopUnroll] Add RuntimeUnrollMultiExit to loop unroll options (NFC) (#124462)

Add an extra knob to RuntimeUnrollMultiExit to let backends control
whether to allow multi-exit unrolling on a per-loo

[LoopUnroll] Add RuntimeUnrollMultiExit to loop unroll options (NFC) (#124462)

Add an extra knob to RuntimeUnrollMultiExit to let backends control
whether to allow multi-exit unrolling on a per-loop basis.

This gives backends more fine-grained control on deciding if multi-exit
unrolling is profitable for a given loop and uarch. Similar to
4226e0a0c75.

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

show more ...

[LLVM] Fix various cl::desc typos and whitespace issues (NFC) (#121955)

[TTI] Add SCEVExpansionBudget to loop unrolling options. (#118316)

Add an extra know to UnrollingPreferences to let backends control the
maximum budget for SCEV expansions.

This gives backends m

[TTI] Add SCEVExpansionBudget to loop unrolling options. (#118316)

Add an extra know to UnrollingPreferences to let backends control the
maximum budget for SCEV expansions.

This gives backends more fine-grained control on the cost of the runtime
checks for runtime unrolling.

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

show more ...

[Scalar] Remove unused includes (NFC) (#114645)

Identified with misc-include-cleaner.

[LoopUnroll] Consider convergence control tokens when unrolling (#91715)

- There is no restriction on a loop with controlled convergent
operations when
the relevant tokens are defined and used w

[LoopUnroll] Consider convergence control tokens when unrolling (#91715)

- There is no restriction on a loop with controlled convergent
operations when
the relevant tokens are defined and used within the loop.

- When a token defined outside a loop is used inside (also called a loop
convergence heart), unrolling is allowed only in the absence of
remainder or
runtime checks.

- When a token defined inside a loop is used outside, such a loop is
said to be
"extended". This loop can only be unrolled by also duplicating the
extended part
lying outside the loop. Such unrolling is disabled for now.

- Clean up loop hearts: When unrolling a loop with a heart, duplicating
the
heart will introduce multiple static uses of a convergence control token
in a
cycle that does not contain its definition. This violates the static
rules for
tokens, and needs to be cleaned up into a single occurrence of the
intrinsic.

- Spell out the initializer for UnrollLoopOptions to improve
readability.


Original implementation [D85605] by Nicolai Haehnle
<nicolai.haehnle@amd.com>.

show more ...

[LoopUnroll] Add CSE to remove redundant loads after unrolling. (#83860)

This patch adds loadCSE support to simplifyLoopAfterUnroll. It is based
on EarlyCSE's implementation using ScopeHashTable an

[LoopUnroll] Add CSE to remove redundant loads after unrolling. (#83860)

This patch adds loadCSE support to simplifyLoopAfterUnroll. It is based
on EarlyCSE's implementation using ScopeHashTable and is using SCEV for
accessed pointers to check to find redundant loads after unrolling.

This applies to the late unroll pass only, for full unrolling those
redundant loads will be cleaned up by the regular pipeline.

The current approach constructs MSSA on-demand per-loop, but there is
still small but notable compile-time impact:

stage1-O3 +0.04%
stage1-ReleaseThinLTO +0.06%
stage1-ReleaseLTO-g +0.05%
stage1-O0-g +0.02%
stage2-O3 +0.09%
stage2-O0-g +0.04%
stage2-clang +0.02%


https://llvm-compile-time-tracker.com/compare.php?from=c089fa5a729e217d0c0d4647656386dac1a1b135&to=ec7c0f27cb5c12b600d9adfc8543d131765ec7be&stat=instructions:u

This benefits some workloads with runtime-unrolling disabled,
where users use pragmas to force unrolling, as well as with
runtime unrolling enabled.

On SPEC/MultiSource, this removes a number of loads after unrolling
on AArch64 with runtime unrolling enabled.

```
External/S...te/526.blender_r/526.blender_r 96
MultiSourc...rks/mediabench/gsm/toast/toast 39
SingleSource/Benchmarks/Misc/ffbench 4
External/SPEC/CINT2006/403.gcc/403.gcc 18
MultiSourc.../Applications/JM/ldecod/ldecod 4
MultiSourc.../mediabench/jpeg/jpeg-6a/cjpeg 6
MultiSourc...OE-ProxyApps-C/miniGMG/miniGMG 9
MultiSourc...e/Applications/ClamAV/clamscan 4
MultiSourc.../MallocBench/espresso/espresso 3
MultiSourc...dence-flt/LinearDependence-flt 2
MultiSourc...ch/office-ispell/office-ispell 4
MultiSourc...ch/consumer-jpeg/consumer-jpeg 6
MultiSourc...ench/security-sha/security-sha 11
MultiSourc...chmarks/McCat/04-bisect/bisect 3
SingleSour...tTests/2020-01-06-coverage-009 12
MultiSourc...ench/telecomm-gsm/telecomm-gsm 39
MultiSourc...lds-flt/CrossingThresholds-flt 24
MultiSourc...dence-dbl/LinearDependence-dbl 2
External/S...C/CINT2006/445.gobmk/445.gobmk 6
MultiSourc...enchmarks/mafft/pairlocalalign 53
External/S...31.deepsjeng_r/531.deepsjeng_r 3
External/S...rate/510.parest_r/510.parest_r 58
External/S...NT2006/464.h264ref/464.h264ref 29
External/S...NT2017rate/502.gcc_r/502.gcc_r 45
External/S...C/CINT2006/456.hmmer/456.hmmer 6
External/S...te/538.imagick_r/538.imagick_r 18
External/S.../CFP2006/447.dealII/447.dealII 4
MultiSourc...OE-ProxyApps-C++/miniFE/miniFE 12
External/S...2017rate/525.x264_r/525.x264_r 36
MultiSourc...Benchmarks/7zip/7zip-benchmark 33
MultiSourc...hmarks/ASC_Sequoia/AMGmk/AMGmk 2
MultiSourc...chmarks/VersaBench/8b10b/8b10b 1
MultiSourc.../Applications/JM/lencod/lencod 116
MultiSourc...lds-dbl/CrossingThresholds-dbl 24
MultiSource/Benchmarks/McCat/05-eks/eks 15
```

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

show more ...

[LoopUnroll] Consider simplified operands while retrieving TTI instruction cost (#70929)

Get more precise cost of instruction after LoopUnroll considering that
some operands of it can be simplified

[LoopUnroll] Consider simplified operands while retrieving TTI instruction cost (#70929)

Get more precise cost of instruction after LoopUnroll considering that
some operands of it can be simplified, e.g. induction variable will be
replaced by constant after full unrolling.

show more ...

[LoopUnroll] Introduce PragmaUnrollFullMaxIterations as a hard cap on how many iterations we try to unroll (#78648)

Fixes [PR77842](https://github.com/llvm/llvm-project/issues/77842) where
UBSAN ca

[LoopUnroll] Introduce PragmaUnrollFullMaxIterations as a hard cap on how many iterations we try to unroll (#78648)

Fixes [PR77842](https://github.com/llvm/llvm-project/issues/77842) where
UBSAN causes pragma full unroll to try and unroll INT_MAX times. This
sets a cap to make sure we don't attempt this and crash the compiler.

Testing:
ninja check-all with new test

---------

Co-authored-by: Nikita Popov <github@npopov.com>

show more ...

[LoopUnroll] Make UnrollMaxUpperBound to be overridable by target (#76029)

The UnrollMaxUpperBound should be target dependent, since different
chips provide different register set which brings diff

[LoopUnroll] Make UnrollMaxUpperBound to be overridable by target (#76029)

The UnrollMaxUpperBound should be target dependent, since different
chips provide different register set which brings different ability of
storing more temporary values of a program. So I add a MaxUpperBound
value in UnrollingPreference which can be override by targets. All uses
of UnrollMaxUpperBound are replaced with UP.MaxUpperBound.

The default value is still 8 and the command line argument
'--unroll-max-upperbound' takes final effect if provided.

show more ...

[LoopUnroll] Make use of MaxTripCount for loops with "#pragma unroll" (#74703)

Fix loop unroll fail caused by branches folding.

For example:
SimplifyCFG foldloop branches then cause loop unroll

[LoopUnroll] Make use of MaxTripCount for loops with "#pragma unroll" (#74703)

Fix loop unroll fail caused by branches folding.

For example:
SimplifyCFG foldloop branches then cause loop unroll failed for "#program unroll" loop.
```
#program unroll
for (int I = 0; I < ConstNum; ++I) { // folding "I < ConstNum" and "Cond2"
if (Cond2) {
break;
}
xxx loop body;
}
```

The pragma unroll metadata only takes effect if there is an exact trip
count, but not if there is an upper bound trip count. This patch make it
work with an upper bound trip count as well in shouldPragmaUnroll().

Loop unroll is important in stack nervous devices (e.g. GPU, and that is
why a lot of GPU code mark loop with "#program unroll").
It usually much simplify the address (offset) calculations in old
iterations, then we can do a lot of others optimizations, e.g, SROA, for
these simplifed address (escape alloca the whole aggregates).

show more ...

[LoopUnroll] Store more information in UnrollCostEstimator (NFCI)

Instead of having ApproximateLoopSize() use a bunch of out parameters,
from which we later construct an UnrollCostEstimator, directl

[LoopUnroll] Store more information in UnrollCostEstimator (NFCI)

Instead of having ApproximateLoopSize() use a bunch of out parameters,
from which we later construct an UnrollCostEstimator, directly
construct UnrollCostEstimator which holds all the information
derived from loop analysis. This makes it easier to add additional
metrics in the future.

show more ...

[Transforms] Remove unused function createSimpleLoopUnrollPass

The last use was removed by:

commit d623b2f95fd559901f008a0588dddd0949a8db01
Author: Arthur Eubanks <aeubanks@google.com>
Date:

[Transforms] Remove unused function createSimpleLoopUnrollPass

The last use was removed by:

commit d623b2f95fd559901f008a0588dddd0949a8db01
Author: Arthur Eubanks <aeubanks@google.com>
Date: Fri Mar 10 17:24:19 2023 -0800

show more ...

Revert "[LCSSA] Remove unused ScalarEvolution argument (NFC)"

This reverts commit 5362a0d859d8e96b3f7c0437b7866e17a818a4f7.

In preparation for reverting a dependent revision.

[LCSSA] Remove unused ScalarEvolution argument (NFC)

After D149435, LCSSA formation no longer needs access to
ScalarEvolution, so remove the argument from the utilities.

[LoopUnroll] Prevent LoopFullUnrollPass to perform partial/runtime unrolling

FullLoopUnroll was performing runtime unrolling in certain cases when
'#pragma unroll' was specified. Patch to fix this b

[LoopUnroll] Prevent LoopFullUnrollPass to perform partial/runtime unrolling

FullLoopUnroll was performing runtime unrolling in certain cases when
'#pragma unroll' was specified. Patch to fix this by introducing new parameter
to tryToUnrollLoop() to differentiate between LoopUnrollPass and
FullLoopUnrollPass. Based on the discussion here
(https://discourse.llvm.org/t/loop-unroller-fails-to-unroll-loop/69834)

Reviewed By: nikic

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

show more ...

[NFC] Use single quotes for single char output during `printPipline`

Reviewed By: arsenm

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

[LoopPeel] Expose ValueMap of last peeled iteration. NFC

The value map of last peeled iteration is computed within peelLoop API.
This patch exposes it for callers of peelLoop.
While this is not curr

[LoopPeel] Expose ValueMap of last peeled iteration. NFC

The value map of last peeled iteration is computed within peelLoop API.
This patch exposes it for callers of peelLoop.
While this is not currently used by upstream passes, we have a usecase
downstream which benefits from this API update. Future users of peelLoop
can also use the ValueMap if needed.

Similar value maps are exposed by other loop utilities such as loop
cloning.

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

show more ...

[Transforms,CodeGen] std::optional::value => operator*/operator->

value() has undesired exception checking semantics and calls
__throw_bad_optional_access in libc++. Moreover, the API is unavailable

[Transforms,CodeGen] std::optional::value => operator*/operator->

value() has undesired exception checking semantics and calls
__throw_bad_optional_access in libc++. Moreover, the API is unavailable without
_LIBCPP_NO_EXCEPTIONS on older Mach-O platforms (see
_LIBCPP_AVAILABILITY_BAD_OPTIONAL_ACCESS).

show more ...

Don't include Optional.h

These files no longer use llvm::Optional.

[Transforms/Scalar] llvm::Optional => std::optional

Transforms/Utils: llvm::Optional => std::optional

Don't include None.h (NFC)

I've converted all known uses of None to std::nullopt, so we no longer
need to include None.h.

This is part of an effort to migrate from llvm::Optional to
std::optional:

Don't include None.h (NFC)

I've converted all known uses of None to std::nullopt, so we no longer
need to include None.h.

This is part of an effort to migrate from llvm::Optional to
std::optional:

https://discourse.llvm.org/t/deprecating-llvm-optional-x-hasvalue-getvalue-getvalueor/63716

show more ...

[llvm] Use std::nullopt instead of None in comments (NFC)

This is part of an effort to migrate from llvm::Optional to
std::optional:

https://discourse.llvm.org/t/deprecating-llvm-optional-x-hasvalu

[llvm] Use std::nullopt instead of None in comments (NFC)

This is part of an effort to migrate from llvm::Optional to
std::optional:

https://discourse.llvm.org/t/deprecating-llvm-optional-x-hasvalue-getvalue-getvalueor/63716

show more ...

[Transforms] Use std::nullopt instead of None (NFC)

This patch mechanically replaces None with std::nullopt where the
compiler would warn if None were deprecated. The intent is to reduce
the amount

[Transforms] Use std::nullopt instead of None (NFC)

This patch mechanically replaces None with std::nullopt where the
compiler would warn if None were deprecated. The intent is to reduce
the amount of manual work required in migrating from Optional to
std::optional.

This is part of an effort to migrate from llvm::Optional to
std::optional:

https://discourse.llvm.org/t/deprecating-llvm-optional-x-hasvalue-getvalue-getvalueor/63716

show more ...

[Scalar] Use std::optional in LoopUnrollPass.cpp (NFC)

This is part of an effort to migrate from llvm::Optional to
std::optional:

https://discourse.llvm.org/t/deprecating-llvm-optional-x-hasvalue-g

[Scalar] Use std::optional in LoopUnrollPass.cpp (NFC)

This is part of an effort to migrate from llvm::Optional to
std::optional:

https://discourse.llvm.org/t/deprecating-llvm-optional-x-hasvalue-getvalue-getvalueor/63716

show more ...