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.

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.

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.

The refactored template can now be used with MachineVerifier.

Reviewed By: arsenm

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

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

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

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

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

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