MachineUniformityAnalysis: Improve isConstantOrUndefValuePhi (#112866)

Change existing code for G_PHI to match what LLVM-IR version is doing
via PHINode::hasConstantOrUndefValue. This is not safe f

MachineUniformityAnalysis: Improve isConstantOrUndefValuePhi (#112866)

Change existing code for G_PHI to match what LLVM-IR version is doing
via PHINode::hasConstantOrUndefValue. This is not safe for regular PHI
since it may appear with an undef operand and getVRegDef can fail.
Most notably this improves number of values that can be allocated
to sgpr in AMDGPURegBankSelect.
Common case here are phis that appear in structurize-cfg lowering
for cycles with multiple exits:
Undef incoming value is coming from block that reached cycle exit
condition, if other incoming is uniform keep the phi uniform despite
the fact it is joining values from pair of blocks that are entered
via divergent condition branch.

show more ...

Restore "[LLVM] move verification of convergence control to a class template""

The refactored template can now be used with MachineVerifier.

Resubmitted after fixing build errors:

- Shared librari

Restore "[LLVM] move verification of convergence control to a class template""

The refactored template can now be used with MachineVerifier.

Resubmitted after fixing build errors:

- Shared libraries build failed with undefined references due to "extern
template" declarations.
- Modules build failed due to a cycle dependence between llvm/ADT and llvm/IR.
The Generic*Impl.h files should be in llvm/IR to prevent this.

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

This restores commit 93a3706711fd46d4d487640d91b16c2eec747c9e.
Originally reverted in 466bd9981150906552a1f2308e3c9065bfcb6741.

show more ...

Revert "[LLVM] move verification of convergence control to a class template"

This reverts commit 93a3706711fd46d4d487640d91b16c2eec747c9e.

The "extern template" declaration of CycleInfo caused prob

Revert "[LLVM] move verification of convergence control to a class template"

This reverts commit 93a3706711fd46d4d487640d91b16c2eec747c9e.

The "extern template" declaration of CycleInfo caused problems in a shared build
when CycleInfo was removed from Verifier.cpp. There needs to be an explicit
instantiation corresponding to an extern template in every SO.

show more ...

[LLVM] move verification of convergence control to a class template

The refactored template can now be used with MachineVerifier.

Reviewed By: arsenm

Differential Revision: https://reviews.llvm.or

[LLVM] move verification of convergence control to a class template

The refactored template can now be used with MachineVerifier.

Reviewed By: arsenm

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

show more ...

[LLVM] refactor GenericSSAContext and its specializations

Fix the GenericSSAContext template so that it actually declares all the
necessary typenames and the methods that must be implemented by its

[LLVM] refactor GenericSSAContext and its specializations

Fix the GenericSSAContext template so that it actually declares all the
necessary typenames and the methods that must be implemented by its
specializations SSAContext and MachineSSAContext.

Reviewed By: arsenm

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

show more ...

[llvm] minor cleanup in GenericSSAContext

- update comments to reflect actual state
- use (implicitly inline) constexpr for a const static member

[CodeGen] Make use of MachineInstr::all_defs and all_uses. NFCI.

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

[llvm][Uniformity] A phi with an undef argument is not always divergent

The uniformity analysis treated an undef argument to phi to be distinct from any
other argument, equivalent to calling PHINode

[llvm][Uniformity] A phi with an undef argument is not always divergent

The uniformity analysis treated an undef argument to phi to be distinct from any
other argument, equivalent to calling PHINode::hasConstantValue() instead of
PHINode::hasConstantOrUndefValue(). Such a phi was reported as divergent. This
is different from the older divergence analysis which treats such a phi as
uniform. Fixed uniformity analysis to match the older behaviour.

The original behaviour was added to DivergenceAnalysis in D19013. But it is not
clear if relying on the undef value is safe. The defined values are not constant
per se; they just happen to be uniform and the non-constant uniform value may
not dominate the PHI.

Reviewed By: ruiling

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

show more ...

RFC: Uniformity Analysis for Irreducible Control Flow

Uniformity analysis is a generalization of divergence analysis to
include irreducible control flow:

1. The proposed spec presents a notion of

RFC: Uniformity Analysis for Irreducible Control Flow

Uniformity analysis is a generalization of divergence analysis to
include irreducible control flow:

1. The proposed spec presents a notion of "maximal convergence" that
captures the existing convention of converging threads at the
headers of natual loops.

2. Maximal convergence is then extended to irreducible cycles. The
identity of irreducible cycles is determined by the choices made
in a depth-first traversal of the control flow graph. Uniformity
analysis uses criteria that depend only on closed paths and not
cycles, to determine maximal convergence. This makes it a
conservative analysis that is independent of the effect of DFS on
CycleInfo.

3. The analysis is implemented as a template that can be
instantiated for both LLVM IR and Machine IR.

Validation:
- passes existing tests for divergence analysis
- passes new tests with irreducible control flow
- passes equivalent tests in MIR and GMIR

Based on concepts originally outlined by
Nicolai Haehnle <nicolai.haehnle@amd.com>

With contributions from Ruiling Song <ruiling.song@amd.com> and
Jay Foad <jay.foad@amd.com>.

Support for GMIR and lit tests for GMIR/MIR added by
Yashwant Singh <yashwant.singh@amd.com>.

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

show more ...

Cleanup codegen includes

This is a (fixed) recommit of https://reviews.llvm.org/D121169

after: 1061034926
before: 1063332844

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

Cleanup codegen includes

This is a (fixed) recommit of https://reviews.llvm.org/D121169

after: 1061034926
before: 1063332844

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

show more ...

Revert "Cleanup codegen includes"

This reverts commit 7f230feeeac8a67b335f52bd2e900a05c6098f20.
Breaks CodeGenCUDA/link-device-bitcode.cu in check-clang,
and many LLVM tests, see comments on https:/

Revert "Cleanup codegen includes"

This reverts commit 7f230feeeac8a67b335f52bd2e900a05c6098f20.
Breaks CodeGenCUDA/link-device-bitcode.cu in check-clang,
and many LLVM tests, see comments on https://reviews.llvm.org/D121169

show more ...

Cleanup codegen includes

after: 1061034926
before: 1063332844

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

Reapply CycleInfo: Introduce cycles as a generalization of loops

Reverts 02940d6d2202. Fixes breakage in the modules build.

LLVM loops cannot represent irreducible structures in the CFG. This
chang

Reapply CycleInfo: Introduce cycles as a generalization of loops

Reverts 02940d6d2202. Fixes breakage in the modules build.

LLVM loops cannot represent irreducible structures in the CFG. This
change introduce the concept of cycles as a generalization of loops,
along with a CycleInfo analysis that discovers a nested
hierarchy of such cycles. This is based on Havlak (1997), Nesting of
Reducible and Irreducible Loops.

The cycle analysis is implemented as a generic template and then
instatiated for LLVM IR and Machine IR. The template relies on a new
GenericSSAContext template which must be specialized when used for
each IR.

This review is a restart of an older review request:
https://reviews.llvm.org/D83094

Original implementation by Nicolai Hähnle <nicolai.haehnle@amd.com>,
with recent refactoring by Sameer Sahasrabuddhe <sameer.sahasrabuddhe@amd.com>

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

show more ...

CycleInfo: Introduce cycles as a generalization of loops

LLVM loops cannot represent irreducible structures in the CFG. This
change introduce the concept of cycles as a generalization of loops,
alon

CycleInfo: Introduce cycles as a generalization of loops

LLVM loops cannot represent irreducible structures in the CFG. This
change introduce the concept of cycles as a generalization of loops,
along with a CycleInfo analysis that discovers a nested
hierarchy of such cycles. This is based on Havlak (1997), Nesting of
Reducible and Irreducible Loops.

The cycle analysis is implemented as a generic template and then
instatiated for LLVM IR and Machine IR. The template relies on a new
GenericSSAContext template which must be specialized when used for
each IR.

This review is a restart of an older review request:
https://reviews.llvm.org/D83094

Original implementation by Nicolai Hähnle <nicolai.haehnle@amd.com>,
with recent refactoring by Sameer Sahasrabuddhe <sameer.sahasrabuddhe@amd.com>

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

show more ...