[NFCI][SimpleLoopUnswitch] Adjust CostKind query

When getUserCost was transitioned to use an explicit CostKind,
TCK_CodeSize was used even though the original kind was implicitly
SizeAndLatency so r

[NFCI][SimpleLoopUnswitch] Adjust CostKind query

When getUserCost was transitioned to use an explicit CostKind,
TCK_CodeSize was used even though the original kind was implicitly
SizeAndLatency so restore this behaviour. We now only query for
CodeSize when optimising for minsize.

I expect this to not change anything as, I think all, targets will
currently return the same value for CodeSize and SizeLatency. Indeed
I see no changes in the test suite for Arm, AArch64 and X86.

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

show more ...

[SimpleLoopUnswitch][NFC] Add option to always drop make.implicit metadata in non-trivial unswitching and save compile time

We might want this if we find out that using of MustExecute analysis is to

[SimpleLoopUnswitch][NFC] Add option to always drop make.implicit metadata in non-trivial unswitching and save compile time

We might want this if we find out that using of MustExecute analysis is too expensive.
By default we do the analysis because its complexity does not exceed the complexity
of whole loop copying in unswitching. Follow-up for D84925.

Differential Revision: https://reviews.llvm.org/D85001
Reviewed By: asbirlea

show more ...

[SimpleLoopUnswitch] Preserve make.implicit in non-trivial unswitch if legal

We can preserve make.implicit metadata in the split block if it is
guaranteed that after following the branch we always r

[SimpleLoopUnswitch] Preserve make.implicit in non-trivial unswitch if legal

We can preserve make.implicit metadata in the split block if it is
guaranteed that after following the branch we always reach the block
where processing of null case happens, which is equivalent to
"initial condition must execute if the loop is entered".

Differential Revision: https://reviews.llvm.org/D84925
Reviewed By: asbirlea

show more ...

[SimpleLoopUnswitch] Drop make.implicit metadata in case of non-trivial unswitching

Non-trivial unswitching simply moves terminator being unswitch from the loop
up to the switch block. It also prese

[SimpleLoopUnswitch] Drop make.implicit metadata in case of non-trivial unswitching

Non-trivial unswitching simply moves terminator being unswitch from the loop
up to the switch block. It also preserves all metadata that was there. It might not
be a correct thing to do for `make.implicit` metadata. Consider case:
```
for (...) {
cond = // computed in loop
if (cond) return X;
if (p == null) throw_npe(); !make implicit
}
```
Before the unswitching, if `p` is null and we reach this check, we are guaranteed
to go to `throw_npe()` block. Now we unswitch on `p == null` condition:
```
if (p == null) !make implicit {
for (...) {
if (cond) return X;
throw_npe()
}
} else {
for (...) {
if (cond) return X;
}
}
```
Now, following `true` branch of `p == null` does not always lead us to
`throw_npe()` because the loop has side exit. Now, if we run ImplicitNullCheck
pass on this code, it may end up making the unswitch condition implicit. This may
lead us to turning normal path to `return X` into signal-throwing path, which is
not efficient.

Note that this does not happen during trivial unswitch: it guarantees that we do not
have side exits before condition being unswitched.

This patch fixes this situation by unconditional dropping of `make.implicit` metadata
when we perform non-trivial unswitch. We could preserve it if we could prove that the
condition always executes. This can be done as a follow-up.

Differential Revision: https://reviews.llvm.org/D84916
Reviewed By: asbirlea

show more ...

[NFC] Remove unused variable

[SimpleLoopUnswitch] Drop uses of instructions before block deletion

Currently if instructions defined in a block are used in unreachable
blocks and SimpleLoopUnswitch attempts deleting the block, i

[SimpleLoopUnswitch] Drop uses of instructions before block deletion

Currently if instructions defined in a block are used in unreachable
blocks and SimpleLoopUnswitch attempts deleting the block, it triggers
assertion "Uses remain when a value is destroyed!".
This patch fixes it by replacing all uses of instructions from BB with
undefs before BB deletion.

Reviewed By: asbirlea

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

show more ...

[SimpleLoopUnswitch] Add non-empty unreachable block check to exit cases removed.

Summary:
Update check to include the check for unreachable.

Basic blocks ending in unreachable are special cased, a

[SimpleLoopUnswitch] Add non-empty unreachable block check to exit cases removed.

Summary:
Update check to include the check for unreachable.

Basic blocks ending in unreachable are special cased, as these blocks may be already unswitched. Before this patch this check is only done for the default destination.
The condition for the exit cases and the default case must be the same, because we should never leave edges from the switch instruction to a basic block that we are unswitching. In PR45355 we still have a remaining edge (that we're attempting to remove from the DT) because its the default edge to an unreachable-terminated block where we unswitch a case edge to that block.

Resolves PR45355.

Reviewers: chandlerc

Subscribers: hiraditya, uabelho, llvm-commits

Tags: #llvm

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

show more ...

[SimpleLoopUnswitch] Update DefaultExit condition to check unreachable is not empty.

Summary:
Update the check for the default exit block to not only check that the
terminator is not unreachable, bu

[SimpleLoopUnswitch] Update DefaultExit condition to check unreachable is not empty.

Summary:
Update the check for the default exit block to not only check that the
terminator is not unreachable, but also check that unreachable block has
*only* the unreachable instruction.

Reviewers: chandlerc

Subscribers: hiraditya, uabelho, llvm-commits

Tags: #llvm

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

show more ...

[TTI] Add TargetCostKind argument to getUserCost

There are several different types of cost that TTI tries to provide
explicit information for: throughput, latency, code size along with
a vague 'inte

[TTI] Add TargetCostKind argument to getUserCost

There are several different types of cost that TTI tries to provide
explicit information for: throughput, latency, code size along with
a vague 'intersection of code-size cost and execution cost'.

The vectorizer is a keen user of RecipThroughput and there's at least
'getInstructionThroughput' and 'getArithmeticInstrCost' designed to
help with this cost. The latency cost has a single use and a single
implementation. The intersection cost appears to cover most of the
rest of the API.

getUserCost is explicitly called from within TTI when the user has
been explicit in wanting the code size (also only one use) as well
as a few passes which are concerned with a mixture of size and/or
a relative cost. In many cases these costs are closely related, such
as when multiple instructions are required, but one evident diverging
cost in this function is for div/rem.

This patch adds an argument so that the cost required is explicit,
so that we can make the important distinction when necessary.

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

show more ...

[CallSite removal][SimpleLoopUnswitch] Use CallBase instead of CallSite. NFC

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

[IVDescriptors] Remove IRBuilder.h include; NFC

IVDescriptors.h itself does not reference IRBuilder at all.
Move the include into transformation passes that do.

Revert "[SimpleLoopUnswitch] Fix introduction of UB when hoisted condition may be undef or poison"

.. due to performance regression.

This patch is reverted until infrastructore for CSE/LICM support

Revert "[SimpleLoopUnswitch] Fix introduction of UB when hoisted condition may be undef or poison"

.. due to performance regression.

This patch is reverted until infrastructore for CSE/LICM support for freeze is
added.

This reverts commit 181628b

show more ...

[SimpleLoopUnswitch] Remove unnecessary include; NFC

[SimpleLoopUnswitch] Canonicalize variable names

[SimpleLoopUnswitch] Fix introduction of UB when hoisted condition may be undef or poison

Summary:
Loop unswitch hoists branches on loop-invariant conditions. However, if this
condition is poison/un

[SimpleLoopUnswitch] Fix introduction of UB when hoisted condition may be undef or poison

Summary:
Loop unswitch hoists branches on loop-invariant conditions. However, if this
condition is poison/undef and the branch wasn't originally reachable, loop
unswitch introduces UB (since the optimized code will branch on poison/undef and
the original one didn't)).
We fix this problem by freezing the condition to ensure we don't introduce UB.

We will now transform the following:
while (...) {
if (C) { A }
else { B }
}

Into:
C' = freeze(C)
if (C') {
while (...) { A }
} else {
while (...) { B }
}

This patch fixes the root cause of the following bug reports (which use the old loop unswitch, but can be reproduced with minor changes in the code and -enable-nontrivial-unswitch):
- https://llvm.org/bugs/show_bug.cgi?id=27506
- https://llvm.org/bugs/show_bug.cgi?id=31652

Reviewers: reames, majnemer, chenli, sanjoy, hfinkel

Reviewed By: reames

Subscribers: hiraditya, jvesely, nhaehnle, filcab, regehr, trentxintong, nlopes, llvm-commits, mzolotukhin

Tags: #llvm

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

show more ...

[NFCI] Update according to style.

clang-tidy + clang-format

Make llvm::StringRef to std::string conversions explicit.

This is how it should've been and brings it more in line with
std::string_view. There should be no functional change here.

This is mostly m

Make llvm::StringRef to std::string conversions explicit.

This is how it should've been and brings it more in line with
std::string_view. There should be no functional change here.

This is mostly mechanical from a custom clang-tidy check, with a lot of
manual fixups. It uncovers a lot of minor inefficiencies.

This doesn't actually modify StringRef yet, I'll do that in a follow-up.

show more ...

NFC. Remove obsolete SimpleAnalysis infrastructure

Apparently cache of AliasSetTrackers held by LICM was the only user of
SimpleAnalysis infrastructure. Now, given that we no longer have that
cache,

NFC. Remove obsolete SimpleAnalysis infrastructure

Apparently cache of AliasSetTrackers held by LICM was the only user of
SimpleAnalysis infrastructure. Now, given that we no longer have that
cache, this infrastructure is obsolete and, taking into account its
nature, we don't want any new solutions to be based on it.

Reviewers: asbirlea, fhahn, efriedma, reames

Reviewed-By: asbirlea

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

show more ...

[LCSSA] Don't use VH callbacks to invalidate SCEV when creating LCSSA phis

In general ValueHandleBase::ValueIsRAUWd shouldn't be called when not
all uses of the value were actually replaced, though,

[LCSSA] Don't use VH callbacks to invalidate SCEV when creating LCSSA phis

In general ValueHandleBase::ValueIsRAUWd shouldn't be called when not
all uses of the value were actually replaced, though, currently
formLCSSAForInstructions calls it when it inserts LCSSA-phis.

Calls of ValueHandleBase::ValueIsRAUWd were added to LCSSA specifically
to update/invalidate SCEV. In the best case these calls duplicate some
of the work already done by SE->forgetValue, though in case when SCEV of
the value is SCEVUnknown, SCEV replaces the underlying value of
SCEVUnknown with the new value (i.e. acts like LCSSA-phi actually fully
replaces the value it is created for), which leads to SCEV being
corrupted because LCSSA-phi rarely dominates all uses of its inputs.

Fixes bug https://bugs.llvm.org/show_bug.cgi?id=44058.

Reviewers: fhahn, efriedma, reames, sanjoy.google

Reviewed By: fhahn

Subscribers: hiraditya, javed.absar, llvm-commits

Tags: #llvm

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

show more ...

[SimpleLoopUnswitch] Invalidate the topmost loop with ExitBB as exiting.

SCEV caches the exiting blocks when computing exit counts. In
SimpleLoopUnswitch, we split the exit block of the loop to unsw

[SimpleLoopUnswitch] Invalidate the topmost loop with ExitBB as exiting.

SCEV caches the exiting blocks when computing exit counts. In
SimpleLoopUnswitch, we split the exit block of the loop to unswitch.

Currently we only invalidate the loop containing that exit block, but if
that block is the exiting block for a parent loop, we have stale cache
entries. We have to invalidate the top-most loop that contains the exit
block as exiting block. We might also be able to skip invalidating the
loop containing the exit block, if the exit block is not an exiting
block of that loop.

There are also 2 more places in SimpleLoopUnswitch, that use a similar
problematic approach to get the loop to invalidate. If the patch makes
sense, I will also update those places to a similar approach (they deal
with multiple exit blocks, so we cannot directly re-use
getTopMostExitingLoop).

Fixes PR43972.

Reviewers: skatkov, reames, asbirlea, chandlerc

Reviewed By: asbirlea

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

show more ...

[MemorySSA] Moving at the end often means before terminator.

Moving accesses in MemorySSA at InsertionPlace::End, when an instruction is
moved into a block, almost always means insert at the end of

[MemorySSA] Moving at the end often means before terminator.

Moving accesses in MemorySSA at InsertionPlace::End, when an instruction is
moved into a block, almost always means insert at the end of the block, but
before the block terminator. This matters when the block terminator is a
MemoryAccess itself (an invoke), and the insertion must be done before
the terminator for the update to be correct.

Insert an additional position: InsertionPlace:BeforeTerminator and update
current usages where this applies.

Resolves PR44027.

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

SimpleLoopUnswitch - fix uninitialized variable and null dereference warnings. NFCI.

llvm-svn: 374986

[MemorySSA] Update DomTree before applying MSSA updates.

Update on the fix in rL374850.

llvm-svn: 374918