Revert "[StructurizeCFG] Improve basic block ordering"

This reverts commit f1b05a0a2bbbea160002be709f8a1c59de366761.

Need to revert to due to issues identified with testing. The
transformation is i

Revert "[StructurizeCFG] Improve basic block ordering"

This reverts commit f1b05a0a2bbbea160002be709f8a1c59de366761.

Need to revert to due to issues identified with testing. The
transformation is incorrect for blocks that contain convergent
instructions.

show more ...

[StructurizeCFG] Improve basic block ordering

StructurizeCFG linearizes the successors of branching basic block
by adding Flow blocks to record the true/false path for branches
and back edges. This

[StructurizeCFG] Improve basic block ordering

StructurizeCFG linearizes the successors of branching basic block
by adding Flow blocks to record the true/false path for branches
and back edges. This patch reduces the number of Phi values needed
to capture the control flow path by improving the basic block
ordering.

Previously, StructurizeCFG adds loop exit blocks outside of the
loop. StructurizeCFG sets a boolean value to indicate the path
taken, and all exit block live values extend to after the loop.
For loops with a large number of exits blocks, this creates a
huge number of values that are maintained, which increases
compilation time and register pressure. This is problem
especially with ASAN, which adds early exits to blocks with
unreachable instructions for each instrumented check in the loop.

In specific cases, this patch reduces the number of values needed
after the loop by moving the exit block into the loop. This is
done for blocks that have a single predecessor and single successor
by moving the block to appear just after the predecessor.

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

show more ...

[NFC] format InstructionSimplify & lowerCaseFunctionNames

Clang-format InstructionSimplify and convert all "FunctionName"s to
"functionName". This patch does touch a lot of files but gets done with

[NFC] format InstructionSimplify & lowerCaseFunctionNames

Clang-format InstructionSimplify and convert all "FunctionName"s to
"functionName". This patch does touch a lot of files but gets done with
the cleanup of InstructionSimplify in one commit.

This is the alternative to the less invasive clang-format only patch: D126783

Reviewed By: spatel, rengolin

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

show more ...

Cleanup includes: Transform/Scalar

Estimated impact on preprocessor output line:
before: 1062981579
after: 1062494547

Discourse thread: https://discourse.llvm.org/t/include-what-you-use-include-cl

Cleanup includes: Transform/Scalar

Estimated impact on preprocessor output line:
before: 1062981579
after: 1062494547

Discourse thread: https://discourse.llvm.org/t/include-what-you-use-include-cleanup
Differential Revision: https://reviews.llvm.org/D120817

show more ...

[StructurizeCFG] Fix boolean not bug

D118623 added code to fold not-of-compare into a compare
with the inverted predicate, if the compare had no other
uses. This relies on accurate use lists in the

[StructurizeCFG] Fix boolean not bug

D118623 added code to fold not-of-compare into a compare
with the inverted predicate, if the compare had no other
uses. This relies on accurate use lists in the IR but it
was run before setPhiValues, when some phi inputs are still
stored in a data structure on the side, instead of being
real uses in the IR. The effect was that a phi that should
be using the original compare result would now get an
inverted result instead.

Fix this by moving simplifyConditions after setPhiValues.

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

show more ...

[StructurizeCFG] Clean up some boolean not instructions

In some cases StructurizeCFG inserts i1 xor instructions to invert
predicates. Add a quick loop to clean these up afterwards if we can get
awa

[StructurizeCFG] Clean up some boolean not instructions

In some cases StructurizeCFG inserts i1 xor instructions to invert
predicates. Add a quick loop to clean these up afterwards if we can get
away with modifying an existing compare instruction instead.
(StructurizeCFG is generally run late in the pipeline so instcombine
does not clean them up for us.)

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

show more ...

[Scalar] Use range-based for loops (NFC)

[Transforms/Scalar] Use range-based for loops (NFC)

static const char *const foo => const char foo[]

By default, a non-template variable of non-volatile const-qualified type
having namespace-scope has internal linkage, so no need for `static`.

[StructurizeCFG][NewPM] Port -structurizecfg to NPM

This doesn't support -structurizecfg-skip-uniform-regions since that
would require porting LegacyDivergenceAnalysis.

The NPM doesn't support addi

[StructurizeCFG][NewPM] Port -structurizecfg to NPM

This doesn't support -structurizecfg-skip-uniform-regions since that
would require porting LegacyDivergenceAnalysis.

The NPM doesn't support adding a non-analysis pass as a dependency of
another, so I had to add -lowerswitch to some tests or pin them to the
legacy PM.

This is the only RegionPass in tree, so I simply copied the logic for
finding all Regions from the legacy PM's RGManager into
StructurizeCFG::run().

Reviewed By: arsenm

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

show more ...

[LowerSwitch][NewPM] Port lowerswitch to NPM

Reviewed By: ychen

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

Revert rG5dd566b7c7b78bd- "PassManager.h - remove unnecessary Function.h/Module.h includes. NFCI."

This reverts commit 5dd566b7c7b78bd385418c72d63c79895be9ae97.

Causing some buildbot failures that

Revert rG5dd566b7c7b78bd- "PassManager.h - remove unnecessary Function.h/Module.h includes. NFCI."

This reverts commit 5dd566b7c7b78bd385418c72d63c79895be9ae97.

Causing some buildbot failures that I'm not seeing on MSVC builds.

show more ...

PassManager.h - remove unnecessary Function.h/Module.h includes. NFCI.

PassManager.h is one of the top headers in the ClangBuildAnalyzer frontend worst offenders list.

This exposes a large number o

PassManager.h - remove unnecessary Function.h/Module.h includes. NFCI.

PassManager.h is one of the top headers in the ClangBuildAnalyzer frontend worst offenders list.

This exposes a large number of implicit dependencies on various forward declarations/includes in other headers that need addressing.

show more ...

[StructurizeCFG] Fix an incorrect comment, NFC.

[StructurizeCFG] Fix region nodes ordering

This is a reimplementation of the `orderNodes` function, as the old
implementation didn't take into account all cases.
The new implementation uses SCCs ins

[StructurizeCFG] Fix region nodes ordering

This is a reimplementation of the `orderNodes` function, as the old
implementation didn't take into account all cases.
The new implementation uses SCCs instead of Loops to take account of
irreducible loops.

Fix PR41509

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

show more ...

Revert "[StructurizeCFG] Fix region nodes ordering"

This reverts commit 897d8ee5cd693e17f95a7e84194bca4c089a520b,
due to causing an infinite loop when encountering a loop with
a sub-region with an i

Revert "[StructurizeCFG] Fix region nodes ordering"

This reverts commit 897d8ee5cd693e17f95a7e84194bca4c089a520b,
due to causing an infinite loop when encountering a loop with
a sub-region with an inner loop.

show more ...

[StructurizeCFG] Fix region nodes ordering

This is a reimplementation of the `orderNodes` function, as the old
implementation didn't take into account all cases.

Fix PR41509

Differential Revision:

[StructurizeCFG] Fix region nodes ordering

This is a reimplementation of the `orderNodes` function, as the old
implementation didn't take into account all cases.

Fix PR41509

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

show more ...

Introduce unify-loop-exits pass.

For each natural loop with multiple exit blocks, this pass creates a
new block N such that all exiting blocks now branch to N, and then
control flow is redistributed

Introduce unify-loop-exits pass.

For each natural loop with multiple exit blocks, this pass creates a
new block N such that all exiting blocks now branch to N, and then
control flow is redistributed to all the original exit blocks.

The bulk of the tranformation is a new function introduced in
BasicBlockUtils that an redirect control flow from a set of incoming
blocks to a set of outgoing blocks via a common "hub".

This is a useful workaround for a limitation in the structurizer which
incorrectly orders blocks when processing a nest of loops. This pass
bypasses that issue by ensuring that each natural loop is recognized
as a separate region. Since the structurizer is a region pass, it no
longer sees a nest of loops in a single region, and instead processes
each "level" in the nesting as a separate region.

The AMDGPU backend provides a new option to enable this pass before
the structurizer, which may eventually be enabled by default.

Reviewers: madhur13490, arsenm, nhaehnle

Reviewed By: nhaehnle

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

show more ...

StructurizeCFG: simplify phi nodes when possible

After structurization, some phi nodes can have a single incoming edge
and can be simplified away. This change runs a simplify query on all
phis that

StructurizeCFG: simplify phi nodes when possible

After structurization, some phi nodes can have a single incoming edge
and can be simplified away. This change runs a simplify query on all
phis that are either modified or added by the structurizer. This also
moves some phis closer to their use as a side benefit.

Reviewed By: arsenm

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

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

[StructurizeCFG] Enable -structurizecfg-relaxed-uniform-regions by default

D62198 introduced an option to relax the checks for
hasOnlyUniformBranches. This commit turns the option on by default, for

[StructurizeCFG] Enable -structurizecfg-relaxed-uniform-regions by default

D62198 introduced an option to relax the checks for
hasOnlyUniformBranches. This commit turns the option on by default, for
better code generation in some cases in AMDGPU.

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

Change-Id: I9cbff002a1e74d3b7eb96b4192dc8129936d537d
llvm-svn: 368042

show more ...

PHINode: introduce setIncomingValueForBlock() function, and use it.

Summary:
There is PHINode::getBasicBlockIndex() and PHINode::setIncomingValue()
but no function to replace incoming value for a sp

PHINode: introduce setIncomingValueForBlock() function, and use it.

Summary:
There is PHINode::getBasicBlockIndex() and PHINode::setIncomingValue()
but no function to replace incoming value for a specified BasicBlock*
predecessor.
Clearly, there are a lot of places that could use that functionality.

Reviewer: craig.topper, lebedev.ri, Meinersbur, kbarton, fhahn
Reviewed By: Meinersbur, fhahn
Subscribers: fhahn, hiraditya, zzheng, jsji, llvm-commits
Tag: LLVM
Differential Revision: https://reviews.llvm.org/D63338

llvm-svn: 363566

show more ...

StructurizeCFG: Relax uniformity checks.

This change relaxes the checks for hasOnlyUniformBranches such that our
region is uniform if:

1. All conditional branches that are direct children are unifo

StructurizeCFG: Relax uniformity checks.

This change relaxes the checks for hasOnlyUniformBranches such that our
region is uniform if:

1. All conditional branches that are direct children are uniform.
2. And either:
a. All sub-regions are uniform.
b. There is one or less conditional branches among the direct
children.

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

llvm-svn: 361610

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