[MemorySSA] Update for partial unswitch.

Update MSSA for blocks cloned when doing partial unswitching.
Enable additional testing with MSSA.
Resolves PR43641.

llvm-svn: 374850

[MemorySSA] Loop passes should mark MSSA preserved when available.

This patch applies only to the new pass manager.
Currently, when MSSA Analysis is available, and pass to each loop pass, it will be

[MemorySSA] Loop passes should mark MSSA preserved when available.

This patch applies only to the new pass manager.
Currently, when MSSA Analysis is available, and pass to each loop pass, it will be preserved by that loop pass.
Hence, mark the analysis preserved based on that condition, vs the current `EnableMSSALoopDependency`. This leaves the global flag to affect only the entry point in the loop pass manager (in FunctionToLoopPassAdaptor).

llvm-svn: 369181

show more ...

[MemorySSA] Use SetVector to avoid nondeterminism.

Summary:
Use a SetVector for DeadBlockSet.
Resolves PR42574.

Reviewers: george.burgess.iv, uabelho, dblaikie

Subscribers: jlebar, Prazek, mgrang,

[MemorySSA] Use SetVector to avoid nondeterminism.

Summary:
Use a SetVector for DeadBlockSet.
Resolves PR42574.

Reviewers: george.burgess.iv, uabelho, dblaikie

Subscribers: jlebar, Prazek, mgrang, llvm-commits

Tags: #llvm

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

llvm-svn: 365970

show more ...

[SimpleLoopUnswitch] Don't consider unswitching `switch` insructions with one unique successor

Only instructions with two or more unique successors should be considered for unswitching.

Patch Autho

[SimpleLoopUnswitch] Don't consider unswitching `switch` insructions with one unique successor

Only instructions with two or more unique successors should be considered for unswitching.

Patch Author: Daniil Suchkov.

Reviewers: reames, asbirlea, skatkov
Reviewed By: skatkov
Subscribers: hiraditya, llvm-commits
Differential Revision: https://reviews.llvm.org/D64404

llvm-svn: 365611

show more ...

[IRBuilder] Introduce helpers for and/or of multiple values at once

We had versions of this code scattered around, so consolidate into one location.

Not strictly NFC since the order of intermediate

[IRBuilder] Introduce helpers for and/or of multiple values at once

We had versions of this code scattered around, so consolidate into one location.

Not strictly NFC since the order of intermediate results may change in some places, but since these operations are associatives, should not change results.

llvm-svn: 365259

show more ...

[SimpleLoopUnswitch] Implement handling of prof branch_weights metadata for SwitchInst

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

llvm-svn: 364734

Only passes that preserve MemorySSA must mark it as preserved.

Summary:
The method `getLoopPassPreservedAnalyses` should not mark MemorySSA as
preserved, because it's being called in a lot of passes

Only passes that preserve MemorySSA must mark it as preserved.

Summary:
The method `getLoopPassPreservedAnalyses` should not mark MemorySSA as
preserved, because it's being called in a lot of passes that do not
preserve MemorySSA.
Instead, mark the MemorySSA analysis as preserved by each pass that does
preserve it.
These changes only affect the new pass mananger.

Reviewers: chandlerc

Subscribers: mehdi_amini, jlebar, Prazek, george.burgess.iv, llvm-commits

Tags: #llvm

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

llvm-svn: 363091

show more ...

Use llvm::stable_sort

While touching the code, simplify if feasible.

llvm-svn: 358996

[MemorySSA & LoopPassManager] Resolve PR40038.

The correct edge being deleted is not to the unswitched exit block, but to the
original block before it was split. That's the key in the map, not the
v

[MemorySSA & LoopPassManager] Resolve PR40038.

The correct edge being deleted is not to the unswitched exit block, but to the
original block before it was split. That's the key in the map, not the
value.
The insert is correct. The new edge is to the .split block.

The splitting turns OriginalBB into:
OriginalBB -> OriginalBB.split.
Assuming the orignal CFG edge: ParentBB->OriginalBB, we must now delete
ParentBB->OriginalBB, not ParentBB->OriginalBB.split.

llvm-svn: 354656

show more ...

[MemorySSA & LoopPassManager] Update MemorySSA in formDedicatedExitBlocks.

MemorySSA is now updated when forming dedicated exit blocks.
Resolves PR40037.

llvm-svn: 354623

[NFC] Rename DontDeleteUselessPHIs --> KeepOneInputPHIs

llvm-svn: 353801

[SimpleLoopUnswitch] Early check exit for trivial unswitch with MemorySSA.

Summary:
If MemorySSA is avaiable, we can skip checking all instructions if block has any Defs.
(volatile loads are also De

[SimpleLoopUnswitch] Early check exit for trivial unswitch with MemorySSA.

Summary:
If MemorySSA is avaiable, we can skip checking all instructions if block has any Defs.
(volatile loads are also Defs).
We still need to check all instructions for "canThrow", even if no Defs are found.

Reviewers: chandlerc

Subscribers: sanjoy, jlebar, Prazek, george.burgess.iv, llvm-commits

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

llvm-svn: 352393

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

[SimpleLoopUnswitch] Increment stats counter for unswitching switch instruction

Increment statistics counter NumSwitches at unswitchNontrivialInvariants() for
unswitching a non-trivial switch instru

[SimpleLoopUnswitch] Increment stats counter for unswitching switch instruction

Increment statistics counter NumSwitches at unswitchNontrivialInvariants() for
unswitching a non-trivial switch instruction. This is to fix a bug that it
increments NumBranches even for the case of switch instruction.
There is no functional change in this patch.

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

llvm-svn: 351193

show more ...

[SimpleLoopUnswitch] Remove debug dump.

llvm-svn: 348267

Update MemorySSA in SimpleLoopUnswitch.

Summary:
Teach SimpleLoopUnswitch to preserve MemorySSA.

Subscribers: sanjoy, jlebar, Prazek, george.burgess.iv, llvm-commits

Differential Revision: https:/

Update MemorySSA in SimpleLoopUnswitch.

Summary:
Teach SimpleLoopUnswitch to preserve MemorySSA.

Subscribers: sanjoy, jlebar, Prazek, george.burgess.iv, llvm-commits

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

llvm-svn: 348263

show more ...

[SimpleLoopUnswitch] adding cost multiplier to cap exponential unswitch with

We need to control exponential behavior of loop-unswitch so we do not get
run-away compilation.

Suggested solution is to

[SimpleLoopUnswitch] adding cost multiplier to cap exponential unswitch with

We need to control exponential behavior of loop-unswitch so we do not get
run-away compilation.

Suggested solution is to introduce a multiplier for an unswitch cost that
makes cost prohibitive as soon as there are too many candidates and too
many sibling loops (meaning we have already started duplicating loops
by unswitching).

It does solve the currently known problem with compile-time degradation
(PR 39544).

Tests are built on top of a recently implemented CHECK-COUNT-<num>
FileCheck directives.

Reviewed By: chandlerc, mkazantsev
Differential Revision: https://reviews.llvm.org/D54223

llvm-svn: 347097

show more ...

[SimpleLoopUnswitch] partial unswitch needs to be careful when replacing invariants with constants

When partial unswitch operates on multiple conditions at once, .e.g:
if (Cond1 || Cond2 || NonIn

[SimpleLoopUnswitch] partial unswitch needs to be careful when replacing invariants with constants

When partial unswitch operates on multiple conditions at once, .e.g:
if (Cond1 || Cond2 || NonInv) ...

it should infer (and replace) values for individual conditions only on one
side of unswitch and not another.

More precisely only these derivations hold true:
(Cond1 || Cond2) == false => Cond1 == Cond2 == false
(Cond1 && Cond2) == true => Cond1 == Cond2 == true

By the way we organize unswitching it means only replacing on "continue" blocks
and never on "unswitched" ones. Since trivial unswitch does not have "unswitched"
blocks it does not have this problem.

Fixes PR 39568.

Reviewers: chandlerc, asbirlea
Differential Revision: https://reviews.llvm.org/D54211

llvm-svn: 346350

show more ...

Fix -Wdocumentation warning. NFCI.

llvm-svn: 345454

[SimpleLoopUnswitch] Unswitch by experimental.guard intrinsics

This patch adds support of `llvm.experimental.guard` intrinsics to non-trivial
simple loop unswitching. These intrinsics represent impl

[SimpleLoopUnswitch] Unswitch by experimental.guard intrinsics

This patch adds support of `llvm.experimental.guard` intrinsics to non-trivial
simple loop unswitching. These intrinsics represent implicit control flow which
has pretty much the same semantics as usual conditional branches. The
algorithm of dealing with them is following:

- Consider guards as unswitching candidates;
- If a guard is considered the best candidate, turn it into a branch;
- Apply normal unswitching algorithm on this branch.

The patch has no compile time effect on code that does not contain any guards.

Differential Revision: https://reviews.llvm.org/D53744
Reviewed By: chandlerc

llvm-svn: 345387

show more ...

[SimpleLoopUnswitch] Make all checks before actual non-trivial unswitch

We should be able to make all relevant checks before we actually start the non-trivial
unswitching, so that we could guarantee

[SimpleLoopUnswitch] Make all checks before actual non-trivial unswitch

We should be able to make all relevant checks before we actually start the non-trivial
unswitching, so that we could guarantee that once we have started the transform,
it will always succeed.

Reviewed By: chandlerc
Differential Revision: https://reviews.llvm.org/D53747

llvm-svn: 345375

show more ...

[TI removal] Switch simple loop unswitch to `Instruction`.

llvm-svn: 344719

[TI removal] Make variables declared as `TerminatorInst` and initialized
by `getTerminator()` calls instead be declared as `Instruction`.

This is the biggest remaining chunk of the usage of `getTerm

[TI removal] Make variables declared as `TerminatorInst` and initialized
by `getTerminator()` calls instead be declared as `Instruction`.

This is the biggest remaining chunk of the usage of `getTerminator()`
that insists on the narrow type and so is an easy batch of updates.
Several files saw more extensive updates where this would cascade to
requiring API updates within the file to use `Instruction` instead of
`TerminatorInst`. All of these were trivial in nature (pervasively using
`Instruction` instead just worked).

llvm-svn: 344502

show more ...

llvm::sort(C.begin(), C.end(), ...) -> llvm::sort(C, ...)

Summary: The convenience wrapper in STLExtras is available since rL342102.

Reviewers: dblaikie, javed.absar, JDevlieghere, andreadb

Subscr

llvm::sort(C.begin(), C.end(), ...) -> llvm::sort(C, ...)

Summary: The convenience wrapper in STLExtras is available since rL342102.

Reviewers: dblaikie, javed.absar, JDevlieghere, andreadb

Subscribers: MatzeB, sanjoy, arsenm, dschuff, mehdi_amini, sdardis, nemanjai, jvesely, nhaehnle, sbc100, jgravelle-google, eraman, aheejin, kbarton, JDevlieghere, javed.absar, gbedwell, jrtc27, mgrang, atanasyan, steven_wu, george.burgess.iv, dexonsmith, kristina, jsji, llvm-commits

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

llvm-svn: 343163

show more ...

[SimpleLoopUnswitch] remove a chain of dead blocks at once

Recent change to deleteDeadBlocksFromLoop was not enough to
fix all the problems related to dead blocks after nontrivial
unswitching of swi

[SimpleLoopUnswitch] remove a chain of dead blocks at once

Recent change to deleteDeadBlocksFromLoop was not enough to
fix all the problems related to dead blocks after nontrivial
unswitching of switches.

We need to delete all the dead blocks that were created during
unswitching, otherwise we will keep having problems with phi's
or dead blocks.

This change removes all the dead blocks that are reachable from the loop,
not trying to track whether these blocks are newly created by unswitching
or not. While not completely correct, we are unlikely to get loose but
reachable dead blocks that do not belong to our loop nest.

It does fix all the failures currently known, in particular PR38778.

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

llvm-svn: 341398

show more ...