[IR] Remove unused includes (NFC) (#114679)

Identified with misc-include-cleaner.

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

[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 header dependencies in LLVMCore

Based on the output of include-what-you-use.

This is a big chunk of changes. It is very likely to break downstream code
unless they took a lot of care in avo

Cleanup header dependencies in LLVMCore

Based on the output of include-what-you-use.

This is a big chunk of changes. It is very likely to break downstream code
unless they took a lot of care in avoiding hidden ehader dependencies, something
the LLVM codebase doesn't do that well :-/

I've tried to summarize the biggest change below:

- llvm/include/llvm-c/Core.h: no longer includes llvm-c/ErrorHandling.h
- llvm/IR/DIBuilder.h no longer includes llvm/IR/DebugInfo.h
- llvm/IR/IRBuilder.h no longer includes llvm/IR/IntrinsicInst.h
- llvm/IR/LLVMRemarkStreamer.h no longer includes llvm/Support/ToolOutputFile.h
- llvm/IR/LegacyPassManager.h no longer include llvm/Pass.h
- llvm/IR/Type.h no longer includes llvm/ADT/SmallPtrSet.h
- llvm/IR/PassManager.h no longer includes llvm/Pass.h nor llvm/Support/Debug.h

And the usual count of preprocessed lines:
$ clang++ -E -Iinclude -I../llvm/include ../llvm/lib/IR/*.cpp -std=c++14 -fno-rtti -fno-exceptions | wc -l
before: 6400831
after: 6189948

200k lines less to process is no that bad ;-)

Discourse thread on the topic: https://llvm.discourse.group/t/include-what-you-use-include-cleanup

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

show more ...

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