GenericUniformityImpl.h

Go to the documentation of this file.

//===- GenericUniformityImpl.h -----------------------*- C++ -*------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This template implementation resides in a separate file so that it
// does not get injected into every .cpp file that includes the
// generic header.
//
// DO NOT INCLUDE THIS FILE WHEN MERELY USING UNIFORMITYINFO.
//
// This file should only be included by files that implement a
// specialization of the relvant templates. Currently these are:
// - UniformityAnalysis.cpp
//
// Note: The DEBUG_TYPE macro should be defined before using this
// file so that any use of LLVM_DEBUG is associated with the
// including file rather than this file.
//
//===----------------------------------------------------------------------===//
///
/// \file
/// \brief Implementation of uniformity analysis.
///
/// The algorithm is a fixed point iteration that starts with the assumption
/// that all control flow and all values are uniform. Starting from sources of
/// divergence (whose discovery must be implemented by a CFG- or even
/// target-specific derived class), divergence of values is propagated from
/// definition to uses in a straight-forward way. The main complexity lies in
/// the propagation of the impact of divergent control flow on the divergence of
/// values (sync dependencies).
///
/// NOTE: In general, no interface exists for a transform to update
/// (Machine)UniformityInfo. Additionally, (Machine)CycleAnalysis is a
/// transitive dependence, but it also does not provide an interface for
/// updating itself. Given that, transforms should not preserve uniformity in
/// their getAnalysisUsage() callback.
///
//===----------------------------------------------------------------------===//
 
#ifndef LLVM_ADT_GENERICUNIFORMITYIMPL_H
#define LLVM_ADT_GENERICUNIFORMITYIMPL_H
 
#include "llvm/ADT/GenericUniformityInfo.h"
 
#include "llvm/ADT/DenseSet.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SparseBitVector.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/Support/raw_ostream.h"
 
#define DEBUG_TYPE "uniformity"
 
namespace llvm {
 
// Forward decl from llvm/CodeGen/MachineInstr.h
class MachineInstr;
 
/// Construct a specially modified post-order traversal of cycles.
///
/// The ModifiedPO is contructed using a virtually modified CFG as follows:
///
/// 1. The successors of pre-entry nodes (predecessors of an cycle
///    entry that are outside the cycle) are replaced by the
///    successors of the successors of the header.
/// 2. Successors of the cycle header are replaced by the exit blocks
///    of the cycle.
///
/// Effectively, we produce a depth-first numbering with the following
/// properties:
///
/// 1. Nodes after a cycle are numbered earlier than the cycle header.
/// 2. The header is numbered earlier than the nodes in the cycle.
/// 3. The numbering of the nodes within the cycle forms an interval
///    starting with the header.
///
/// Effectively, the virtual modification arranges the nodes in a
/// cycle as a DAG with the header as the sole leaf, and successors of
/// the header as the roots. A reverse traversal of this numbering has
/// the following invariant on the unmodified original CFG:
///
///    Each node is visited after all its predecessors, except if that
///    predecessor is the cycle header.
///
template <typename ContextT> class ModifiedPostOrder {
public:
  using BlockT = typename ContextT::BlockT;
  using FunctionT = typename ContextT::FunctionT;
  using DominatorTreeT = typename ContextT::DominatorTreeT;
 
  using CycleInfoT = GenericCycleInfo<ContextT>;
  using const_iterator = typename std::vector<BlockT *>::const_iterator;
 
  ModifiedPostOrder(const ContextT &C) : Context(C) {}
 
  bool empty() const { return Order.empty(); }
  size_t size() const { return Order.size(); }
 
  void clear() { Order.clear(); }
  void compute(const CycleInfoT &CI);
 
  unsigned count(BlockT *BB) const {
    unsigned Num = GraphTraits<BlockT *>::getNumber(BB);
    return Num < POIndex.size() && POIndex[Num] != InvalidIndex;
  }
  const BlockT *operator[](size_t Idx) const { return Order[Idx]; }
 
  void appendBlock(const BlockT &BB, bool IsReducibleCycleHeader = false) {
    unsigned Num = GraphTraits<const BlockT *>::getNumber(&BB);
    POIndex[Num] = Order.size();
    Order.push_back(&BB);
    LLVM_DEBUG(dbgs() << "ModifiedPO(" << POIndex[Num]
                      << "): " << Context.print(&BB) << "\n");
    if (IsReducibleCycleHeader)
      ReducibleCycleHeaders.insert(&BB);
  }
 
  unsigned getIndex(const BlockT *BB) const {
    unsigned Num = GraphTraits<const BlockT *>::getNumber(BB);
    assert(Num < POIndex.size() && POIndex[Num] != InvalidIndex);
    return POIndex[Num];
  }
 
  bool isReducibleCycleHeader(const BlockT *BB) const {
    return ReducibleCycleHeaders.contains(BB);
  }
 
private:
  static constexpr unsigned InvalidIndex = -1u;
 
  SmallVector<const BlockT *> Order;
  SmallVector<unsigned> POIndex;
  SmallPtrSet<const BlockT *, 32> ReducibleCycleHeaders;
  const ContextT &Context;
 
  void computeCyclePO(const CycleInfoT &CI, CycleRef C,
                      SmallPtrSetImpl<const BlockT *> &Finalized);
 
  void computeStackPO(SmallVectorImpl<const BlockT *> &Stack,
                      const CycleInfoT &CI, CycleRef C,
                      SmallPtrSetImpl<const BlockT *> &Finalized);
};
 
template <typename> class DivergencePropagator;
 
/// \class GenericSyncDependenceAnalysis
///
/// \brief Locate join blocks for disjoint paths starting at a divergent branch.
///
/// An analysis per divergent branch that returns the set of basic
/// blocks whose phi nodes become divergent due to divergent control.
/// These are the blocks that are reachable by two disjoint paths from
/// the branch, or cycle exits reachable along a path that is disjoint
/// from a path to the cycle latch.
 
// --- Above line is not a doxygen comment; intentionally left blank ---
//
// Originally implemented in SyncDependenceAnalysis.cpp for DivergenceAnalysis.
//
// The SyncDependenceAnalysis is used in the UniformityAnalysis to model
// control-induced divergence in phi nodes.
//
// -- Reference --
// The algorithm is an extension of Section 5 of
//
//   An abstract interpretation for SPMD divergence
//       on reducible control flow graphs.
//   Julian Rosemann, Simon Moll and Sebastian Hack
//   POPL '21
//
//
// -- Sync dependence --
// Sync dependence characterizes the control flow aspect of the
// propagation of branch divergence. For example,
//
//   %cond = icmp slt i32 %tid, 10
//   br i1 %cond, label %then, label %else
// then:
//   br label %merge
// else:
//   br label %merge
// merge:
//   %a = phi i32 [ 0, %then ], [ 1, %else ]
//
// Suppose %tid holds the thread ID. Although %a is not data dependent on %tid
// because %tid is not on its use-def chains, %a is sync dependent on %tid
// because the branch "br i1 %cond" depends on %tid and affects which value %a
// is assigned to.
//
//
// -- Reduction to SSA construction --
// There are two disjoint paths from A to X, if a certain variant of SSA
// construction places a phi node in X under the following set-up scheme.
//
// This variant of SSA construction ignores incoming undef values.
// That is paths from the entry without a definition do not result in
// phi nodes.
//
//       entry
//     /      \
//    A        \
//  /   \       Y
// B     C     /
//  \   /  \  /
//    D     E
//     \   /
//       F
//
// Assume that A contains a divergent branch. We are interested
// in the set of all blocks where each block is reachable from A
// via two disjoint paths. This would be the set {D, F} in this
// case.
// To generally reduce this query to SSA construction we introduce
// a virtual variable x and assign to x different values in each
// successor block of A.
//
//           entry
//         /      \
//        A        \
//      /   \       Y
// x = 0   x = 1   /
//      \  /   \  /
//        D     E
//         \   /
//           F
//
// Our flavor of SSA construction for x will construct the following
//
//            entry
//          /      \
//         A        \
//       /   \       Y
// x0 = 0   x1 = 1  /
//       \   /   \ /
//     x2 = phi   E
//         \     /
//         x3 = phi
//
// The blocks D and F contain phi nodes and are thus each reachable
// by two disjoins paths from A.
//
// -- Remarks --
// * In case of cycle exits we need to check for temporal divergence.
//   To this end, we check whether the definition of x differs between the
//   cycle exit and the cycle header (_after_ SSA construction).
//
// * In the presence of irreducible control flow, the fixed point is
//   reached only after multiple iterations. This is because labels
//   reaching the header of a cycle must be repropagated through the
//   cycle. This is true even in a reducible cycle, since the labels
//   may have been produced by a nested irreducible cycle.
//
// * Note that SyncDependenceAnalysis is not concerned with the points
//   of convergence in an irreducible cycle. It's only purpose is to
//   identify join blocks. The "diverged entry" criterion is
//   separately applied on join blocks to determine if an entire
//   irreducible cycle is assumed to be divergent.
//
// * Relevant related work:
//     A simple algorithm for global data flow analysis problems.
//     Matthew S. Hecht and Jeffrey D. Ullman.
//     SIAM Journal on Computing, 4(4):519–532, December 1975.
//
template <typename ContextT> class GenericSyncDependenceAnalysis {
public:
  using BlockT = typename ContextT::BlockT;
  using DominatorTreeT = typename ContextT::DominatorTreeT;
  using FunctionT = typename ContextT::FunctionT;
  using ValueRefT = typename ContextT::ValueRefT;
  using InstructionT = typename ContextT::InstructionT;
 
  using CycleInfoT = GenericCycleInfo<ContextT>;
 
  using ConstBlockSet = SmallPtrSet<const BlockT *, 4>;
  using ModifiedPO = ModifiedPostOrder<ContextT>;
 
  /// Information discovered by the sync dependence analysis for each
  /// divergent branch.
  struct DivergenceDescriptor {
    // Join points of diverged paths.
    ConstBlockSet JoinDivBlocks;
    // Divergent cycle exits
    ConstBlockSet CycleDivBlocks;
  };
 
  using DivergencePropagatorT = DivergencePropagator<ContextT>;
 
  GenericSyncDependenceAnalysis(const ContextT &Context,
                                const DominatorTreeT &DT, const CycleInfoT &CI);
 
  /// \brief Computes divergent join points and cycle exits caused by branch
  /// divergence in \p Term.
  ///
  /// This returns a pair of sets:
  /// * The set of blocks which are reachable by disjoint paths from
  ///   \p Term.
  /// * The set also contains cycle exits if there two disjoint paths:
  ///   one from \p Term to the cycle exit and another from \p Term to
  ///   the cycle header.
  const DivergenceDescriptor &getJoinBlocks(const BlockT *DivTermBlock);
 
private:
  static inline DivergenceDescriptor EmptyDivergenceDesc;
 
  ModifiedPO CyclePO;
 
  const DominatorTreeT &DT;
  const CycleInfoT &CI;
 
  DenseMap<const BlockT *, std::unique_ptr<DivergenceDescriptor>>
      CachedControlDivDescs;
};
 
/// \brief Analysis that identifies uniform values in a data-parallel
/// execution.
///
/// This analysis propagates divergence in a data-parallel context
/// from sources of divergence to all users. It can be instantiated
/// for an IR that provides a suitable SSAContext.
template <typename ContextT> class GenericUniformityAnalysisImpl {
public:
  using BlockT = typename ContextT::BlockT;
  using FunctionT = typename ContextT::FunctionT;
  using ValueRefT = typename ContextT::ValueRefT;
  using ConstValueRefT = typename ContextT::ConstValueRefT;
  using UseT = typename ContextT::UseT;
  using InstructionT = typename ContextT::InstructionT;
  using DominatorTreeT = typename ContextT::DominatorTreeT;
 
  using CycleInfoT = GenericCycleInfo<ContextT>;
 
  using SyncDependenceAnalysisT = GenericSyncDependenceAnalysis<ContextT>;
  using DivergenceDescriptorT =
      typename SyncDependenceAnalysisT::DivergenceDescriptor;
 
  using TemporalDivergenceTuple =
      std::tuple<ConstValueRefT, InstructionT *, CycleRef>;
 
  GenericUniformityAnalysisImpl(const DominatorTreeT &DT, const CycleInfoT &CI,
                                const TargetTransformInfo *TTI)
      : Context(CI.getSSAContext()), F(*Context.getFunction()), CI(CI),
        TTI(TTI), DT(DT), SDA(Context, DT, CI) {}
 
  void initialize();
 
  const FunctionT &getFunction() const { return F; }
 
  const CycleInfoT &getCycleInfo() const { return CI; }
 
  /// \brief Mark \p UniVal as a value that is always uniform.
  void addUniformOverride(const InstructionT &Instr);
 
  /// \brief Examine \p I for divergent outputs and add to the worklist.
  void markDivergent(const InstructionT &I);
 
  /// \brief Mark \p DivVal as a divergent value by removing it from
  /// UniformValues. \returns Whether the tracked divergence state of
  /// \p DivVal changed.
  bool markDivergent(ConstValueRefT DivVal);
 
  /// \brief Mark outputs of \p Instr as divergent.
  /// \returns Whether the tracked divergence state of any output has changed.
  bool markDefsDivergent(const InstructionT &Instr);
 
  /// \brief Propagate divergence to all instructions in the region.
  /// Divergence is seeded by calls to \p markDivergent.
  void compute();
 
  /// \brief Whether \p Val will always return a uniform value regardless of its
  /// operands
  bool isAlwaysUniform(const InstructionT &Instr) const;
 
  bool hasDivergentDefs(const InstructionT &I) const;
 
  bool isDivergentTerminator(const InstructionT &I) const {
    assert(I.isTerminator() && "Expected a terminator instruction!");
    return DivergentTermBlocks.contains(I.getParent());
  };
 
  /// \brief Whether \p Val is divergent at its definition.
  /// When the target has no branch divergence, compute() is never called
  /// and everything is uniform. Otherwise, values not in UniformValues
  /// (e.g. newly created) are conservatively treated as divergent.
  bool isDivergent(ConstValueRefT V) const {
    if (!HasBranchDivergence)
      return false;
    // Only values that were present during analysis are tracked in
    // UniformValues (Instructions/Arguments for IR, Registers for MIR).
    // Other values (e.g. constants, globals) are always uniform but are
    // not added to UniformValues; this check avoids false divergence.
    if (ContextT::isAlwaysUniform(V))
      return false;
    return !UniformValues.contains(V);
  }
 
  bool isDivergentUse(const UseT &U) const;
 
  bool hasDivergentTerminator(const BlockT &B) const {
    return DivergentTermBlocks.contains(&B);
  }
 
  void print(raw_ostream &Out) const;
 
  /// Print divergent arguments and return true if any were found.
  /// IR specialization iterates F.args(); default is a no-op.
  bool printDivergentArgs(raw_ostream &Out) const;
 
  SmallVector<TemporalDivergenceTuple, 8> TemporalDivergenceList;
 
  void recordTemporalDivergence(ConstValueRefT, const InstructionT *, CycleRef);
 
  /// Check if an instruction with Custom uniformity can be proven uniform
  /// based on its operands. This queries the target-specific callback.
  bool isCustomUniform(const InstructionT &I) const;
 
  /// \brief Add an instruction that requires custom uniformity analysis.
  void addCustomUniformityCandidate(const InstructionT *I);
 
protected:
  const ContextT &Context;
  const FunctionT &F;
  const CycleInfoT &CI;
  const TargetTransformInfo *TTI = nullptr;
 
  // Whether the target has branch divergence. Set at the start of compute(),
  // which is only called when the target has branch divergence. When false,
  // isDivergent() returns false for all values.
  bool HasBranchDivergence = false;
 
  SmallPtrSet<const BlockT *, 32> DivergentTermBlocks;
 
  // Values known to be uniform. Populated in initialize() with all values,
  // then values are removed as divergence is propagated. After analysis,
  // values not in this set are conservatively treated as divergent.
  DenseSet<ConstValueRefT> UniformValues;
 
  // Internal worklist for divergence propagation.
  std::vector<const InstructionT *> Worklist;
 
  // Set of instructions that require custom uniformity analysis based on
  // operand uniformity.
  SmallPtrSet<const InstructionT *, 8> CustomUniformityCandidates;
 
  /// \brief Mark \p Term as divergent and push all Instructions that become
  /// divergent as a result on the worklist.
  void analyzeControlDivergence(const InstructionT &Term);
 
private:
  const DominatorTreeT &DT;
 
  // Recognized cycles with divergent exits.
  SmallSetVector<CycleRef, 8> DivergentExitCycles;
 
  // Cycles assumed to be divergent.
  //
  // We don't use a set here because every insertion needs an explicit
  // traversal of all existing members.
  SmallVector<CycleRef> AssumedDivergent;
 
  // The SDA links divergent branches to divergent control-flow joins.
  SyncDependenceAnalysisT SDA;
 
  // Set of known-uniform values.
  SmallPtrSet<const InstructionT *, 32> UniformOverrides;
 
  /// \brief Mark all nodes in \p JoinBlock as divergent and push them on
  /// the worklist.
  void taintAndPushAllDefs(const BlockT &JoinBlock);
 
  /// \brief Mark all phi nodes in \p JoinBlock as divergent and push them on
  /// the worklist.
  void taintAndPushPhiNodes(const BlockT &JoinBlock);
 
  /// \brief Identify all Instructions that become divergent because \p DivExit
  /// is a divergent cycle exit of \p DivCycle. Mark those instructions as
  /// divergent and push them on the worklist.
  void propagateCycleExitDivergence(const BlockT &DivExit, CycleRef DivCycle);
 
  /// Mark as divergent all external uses of values defined in \p DefCycle.
  void analyzeCycleExitDivergence(CycleRef DefCycle);
 
  /// \brief Mark as divergent all uses of \p I that are outside \p DefCycle.
  void propagateTemporalDivergence(const InstructionT &I, CycleRef DefCycle);
 
  /// \brief Push all users of \p Val (in the region) to the worklist.
  void pushUsers(const InstructionT &I);
  void pushUsers(ConstValueRefT V);
 
  bool usesValueFromCycle(const InstructionT &I, CycleRef DefCycle) const;
 
  /// \brief Whether \p Def is divergent when read in \p ObservingBlock.
  bool isTemporalDivergent(const BlockT &ObservingBlock,
                           const InstructionT &Def) const;
};
 
template <typename ImplT>
void GenericUniformityAnalysisImplDeleter<ImplT>::operator()(ImplT *Impl) {
  delete Impl;
}
 
/// Compute divergence starting with a divergent branch.
template <typename ContextT> class DivergencePropagator {
public:
  using BlockT = typename ContextT::BlockT;
  using DominatorTreeT = typename ContextT::DominatorTreeT;
  using FunctionT = typename ContextT::FunctionT;
  using ValueRefT = typename ContextT::ValueRefT;
 
  using CycleInfoT = GenericCycleInfo<ContextT>;
 
  using ModifiedPO = ModifiedPostOrder<ContextT>;
  using SyncDependenceAnalysisT = GenericSyncDependenceAnalysis<ContextT>;
  using DivergenceDescriptorT =
      typename SyncDependenceAnalysisT::DivergenceDescriptor;
 
  const ModifiedPO &CyclePOT;
  const DominatorTreeT &DT;
  const CycleInfoT &CI;
  const BlockT &DivTermBlock;
  const ContextT &Context;
 
  // Track blocks that receive a new label. Every time we relabel a
  // cycle header, we another pass over the modified post-order in
  // order to propagate the header label. The bit vector also allows
  // us to skip labels that have not changed.
  SparseBitVector<> FreshLabels;
 
  // divergent join and cycle exit descriptor.
  std::unique_ptr<DivergenceDescriptorT> DivDesc;
 
  // Dominating definition at each block on diverged paths, indexed by block
  // number. Transient to this propagation; not stored in the descriptor.
  // * label(B) == C       : C is the dominating definition at B
  // * label(B) == nullptr  : we haven't seen B yet
  // * label(B) == B        : B is a join of disjoint paths, an immediate
  //                          successor of the divergent term, or the term
  //                          itself
  SmallVector<const BlockT *> BlockLabels;
 
  const BlockT *&label(const BlockT *BB) {
    return BlockLabels[GraphTraits<const BlockT *>::getNumber(BB)];
  }
 
  DivergencePropagator(const ModifiedPO &CyclePOT, const DominatorTreeT &DT,
                       const CycleInfoT &CI, const BlockT &DivTermBlock)
      : CyclePOT(CyclePOT), DT(DT), CI(CI), DivTermBlock(DivTermBlock),
        Context(CI.getSSAContext()), DivDesc(new DivergenceDescriptorT),
        BlockLabels(
            GraphTraits<const FunctionT *>::getMaxNumber(CI.getFunction()),
            nullptr) {}
 
  void printDefs(raw_ostream &Out) {
    Out << "Propagator::BlockLabels {\n";
    for (int BlockIdx = (int)CyclePOT.size() - 1; BlockIdx >= 0; --BlockIdx) {
      const auto *Block = CyclePOT[BlockIdx];
      const auto *Label = label(Block);
      Out << Context.print(Block) << "(" << BlockIdx << ") : ";
      if (!Label) {
        Out << "<null>\n";
      } else {
        Out << Context.print(Label) << "\n";
      }
    }
    Out << "}\n";
  }
 
  // Push a definition (\p PushedLabel) to \p SuccBlock and return whether this
  // causes a divergent join.
  bool computeJoin(const BlockT &SuccBlock, const BlockT &PushedLabel) {
    const auto *OldLabel = label(&SuccBlock);
 
    LLVM_DEBUG(dbgs() << "labeling " << Context.print(&SuccBlock) << ":\n"
                      << "\tpushed label: " << Context.print(&PushedLabel)
                      << "\n"
                      << "\told label: " << Context.print(OldLabel) << "\n");
 
    // Early exit if there is no change in the label.
    if (OldLabel == &PushedLabel)
      return false;
 
    if (OldLabel != &SuccBlock) {
      auto SuccIdx = CyclePOT.getIndex(&SuccBlock);
      // Assigning a new label, mark this in FreshLabels.
      LLVM_DEBUG(dbgs() << "\tfresh label: " << SuccIdx << "\n");
      FreshLabels.set(SuccIdx);
    }
 
    // This is not a join if the succ was previously unlabeled.
    if (!OldLabel) {
      LLVM_DEBUG(dbgs() << "\tnew label: " << Context.print(&PushedLabel)
                        << "\n");
      label(&SuccBlock) = &PushedLabel;
      return false;
    }
 
    // This is a new join. Label the join block as itself, and not as
    // the pushed label.
    LLVM_DEBUG(dbgs() << "\tnew label: " << Context.print(&SuccBlock) << "\n");
    label(&SuccBlock) = &SuccBlock;
 
    return true;
  }
 
  // visiting a virtual cycle exit edge from the cycle header --> temporal
  // divergence on join
  bool visitCycleExitEdge(const BlockT &ExitBlock, const BlockT &Label) {
    if (!computeJoin(ExitBlock, Label))
      return false;
 
    // Identified a divergent cycle exit
    DivDesc->CycleDivBlocks.insert(&ExitBlock);
    LLVM_DEBUG(dbgs() << "\tDivergent cycle exit: " << Context.print(&ExitBlock)
                      << "\n");
    return true;
  }
 
  // process \p SuccBlock with reaching definition \p Label
  bool visitEdge(const BlockT &SuccBlock, const BlockT &Label) {
    if (!computeJoin(SuccBlock, Label))
      return false;
 
    // Divergent, disjoint paths join.
    DivDesc->JoinDivBlocks.insert(&SuccBlock);
    LLVM_DEBUG(dbgs() << "\tDivergent join: " << Context.print(&SuccBlock)
                      << "\n");
    return true;
  }
 
  std::unique_ptr<DivergenceDescriptorT> computeJoinPoints() {
    assert(DivDesc);
 
    LLVM_DEBUG(dbgs() << "SDA:computeJoinPoints: "
                      << Context.print(&DivTermBlock) << "\n");
 
    int DivTermIdx = CyclePOT.getIndex(&DivTermBlock);
    CycleRef DivTermCycle = CI.getCycle(&DivTermBlock);
 
    // Locate the largest ancestor cycle that is not reducible and does not
    // contain a reducible ancestor. This is done with a lambda that is defined
    // and invoked in the same statement.
    CycleRef IrreducibleAncestor = [this](CycleRef C) -> CycleRef {
      if (!C)
        return CycleRef();
      if (CI.isReducible(C))
        return CycleRef();
      while (CycleRef P = CI.getParentCycle(C)) {
        if (CI.isReducible(P))
          return C;
        C = P;
      }
      assert(!CI.getParentCycle(C));
      assert(!CI.isReducible(C));
      return C;
    }(DivTermCycle);
 
    // Bootstrap with branch targets
    for (const auto *SuccBlock : successors(&DivTermBlock)) {
      if (DivTermCycle && !CI.contains(DivTermCycle, SuccBlock)) {
        // If DivTerm exits the cycle immediately, computeJoin() might
        // not reach SuccBlock with a different label. We need to
        // check for this exit now.
        DivDesc->CycleDivBlocks.insert(SuccBlock);
        LLVM_DEBUG(dbgs() << "\tImmediate divergent cycle exit: "
                          << Context.print(SuccBlock) << "\n");
      }
      visitEdge(*SuccBlock, *SuccBlock);
    }
 
    // Technically propagation can continue until it reaches the last node.
    //
    // For efficiency, propagation can stop if FreshLabels.count()==1. But
    // For irreducible cycles, let propagation continue until it reaches
    // out of irreducible cycles (see code for details.)
    while (true) {
      auto BlockIdx = FreshLabels.find_last();
      if (BlockIdx == -1)
        break;
 
      const auto *Block = CyclePOT[BlockIdx];
      // If no irreducible cycle, stop if freshLable.count() = 1 and Block
      // is the IPD. If it is in any irreducible cycle, continue propagation.
      if (FreshLabels.count() == 1 &&
          (!IrreducibleAncestor || !CI.contains(IrreducibleAncestor, Block)))
        break;
 
      LLVM_DEBUG(dbgs() << "Current labels:\n"; printDefs(dbgs()));
 
      FreshLabels.reset(BlockIdx);
      if (BlockIdx == DivTermIdx) {
        LLVM_DEBUG(dbgs() << "Skipping DivTermBlock\n");
        continue;
      }
 
      LLVM_DEBUG(dbgs() << "visiting " << Context.print(Block) << " at index "
                        << BlockIdx << "\n");
 
      const auto *Label = label(Block);
      assert(Label);
 
      // If the current block is the header of a reducible cycle, then the label
      // should be propagated to the cycle exits. If this cycle contains the
      // branch, then those exits are divergent exits. This is true for any DFS.
      //
      //   If some DFS has a reducible cycle C with header H, then for
      //   any other DFS, H is the header of a cycle C' that is a
      //   superset of C.
      //
      //   - For a divergent branch inside the subgraph C, any join node inside
      //     C is either H, or some node encountered by paths within C, without
      //     passing through H.
      //
      //   - For a divergent branch outside the subgraph C, H is the only node
      //     in C reachable from multiple paths since it is the only entry to C.
      LLVM_DEBUG(dbgs() << "Check for reducible cycle: " << Context.print(Block)
                        << '\n');
      if (CyclePOT.isReducibleCycleHeader(Block)) {
        CycleRef BlockCycle = CI.getCycle(Block);
        LLVM_DEBUG(dbgs() << CI.print(BlockCycle) << '\n');
        SmallVector<BlockT *, 4> BlockCycleExits;
        CI.getExitBlocks(BlockCycle, BlockCycleExits);
        bool BranchIsInside = CI.contains(BlockCycle, &DivTermBlock);
        for (auto *BlockCycleExit : BlockCycleExits) {
          if (BranchIsInside)
            visitCycleExitEdge(*BlockCycleExit, *Label);
          else
            visitEdge(*BlockCycleExit, *Label);
        }
      } else {
        for (const auto *SuccBlock : successors(Block))
          visitEdge(*SuccBlock, *Label);
      }
    }
 
    LLVM_DEBUG(dbgs() << "Final labeling:\n"; printDefs(dbgs()));
 
    // Check every cycle containing DivTermBlock for exit divergence.
    // A cycle has exit divergence if the label of an exit block does
    // not match the label of its header.
    for (auto C = CI.getCycle(&DivTermBlock); C; C = CI.getParentCycle(C)) {
      if (CI.isReducible(C)) {
        // The exit divergence of a reducible cycle is recorded while
        // propagating labels.
        continue;
      }
      SmallVector<BlockT *> Exits;
      CI.getExitBlocks(C, Exits);
      auto *Header = CI.getHeader(C);
      auto *HeaderLabel = label(Header);
      for (const auto *Exit : Exits) {
        if (label(Exit) != HeaderLabel) {
          // Identified a divergent cycle exit
          DivDesc->CycleDivBlocks.insert(Exit);
          LLVM_DEBUG(dbgs() << "\tDivergent cycle exit: " << Context.print(Exit)
                            << "\n");
        }
      }
    }
 
    return std::move(DivDesc);
  }
};
 
template <typename ContextT>
llvm::GenericSyncDependenceAnalysis<ContextT>::GenericSyncDependenceAnalysis(
    const ContextT &Context, const DominatorTreeT &DT, const CycleInfoT &CI)
    : CyclePO(Context), DT(DT), CI(CI) {
  CyclePO.compute(CI);
}
 
template <typename ContextT>
auto llvm::GenericSyncDependenceAnalysis<ContextT>::getJoinBlocks(
    const BlockT *DivTermBlock) -> const DivergenceDescriptor & {
  // trivial case
  if (succ_size(DivTermBlock) <= 1) {
    return EmptyDivergenceDesc;
  }
 
  // already available in cache?
  auto ItCached = CachedControlDivDescs.find(DivTermBlock);
  if (ItCached != CachedControlDivDescs.end())
    return *ItCached->second;
 
  // compute all join points
  DivergencePropagatorT Propagator(CyclePO, DT, CI, *DivTermBlock);
  auto DivDesc = Propagator.computeJoinPoints();
 
  auto PrintBlockSet = [&](ConstBlockSet &Blocks) {
    return Printable([&](raw_ostream &Out) {
      Out << "[";
      ListSeparator LS;
      for (const auto *BB : Blocks) {
        Out << LS << CI.getSSAContext().print(BB);
      }
      Out << "]\n";
    });
  };
 
  LLVM_DEBUG(
      dbgs() << "\nResult (" << CI.getSSAContext().print(DivTermBlock)
             << "):\n  JoinDivBlocks: " << PrintBlockSet(DivDesc->JoinDivBlocks)
             << "  CycleDivBlocks: " << PrintBlockSet(DivDesc->CycleDivBlocks)
             << "\n");
  (void)PrintBlockSet;
 
  auto ItInserted =
      CachedControlDivDescs.try_emplace(DivTermBlock, std::move(DivDesc));
  assert(ItInserted.second);
  return *ItInserted.first->second;
}
 
template <typename ContextT>
void GenericUniformityAnalysisImpl<ContextT>::markDivergent(
    const InstructionT &I) {
  if (isAlwaysUniform(I))
    return;
  // For custom uniformity candidates, check if the instruction can be
  // proven uniform based on which operands are uniform/divergent.
  // The candidate will be re-evaluated as operands become divergent.
  if (CustomUniformityCandidates.contains(&I)) {
    if (isCustomUniform(I))
      return;
  }
  bool Marked = false;
  if (I.isTerminator()) {
    Marked = DivergentTermBlocks.insert(I.getParent()).second;
    if (Marked) {
      LLVM_DEBUG(dbgs() << "marked divergent term block: "
                        << Context.print(I.getParent()) << "\n");
    }
  } else {
    Marked = markDefsDivergent(I);
  }
 
  if (Marked)
    Worklist.push_back(&I);
}
 
template <typename ContextT>
bool GenericUniformityAnalysisImpl<ContextT>::markDivergent(
    ConstValueRefT Val) {
  if (UniformValues.erase(Val)) {
    LLVM_DEBUG(dbgs() << "marked divergent: " << Context.print(Val) << "\n");
    return true;
  }
  return false;
}
 
template <typename ContextT>
void GenericUniformityAnalysisImpl<ContextT>::addUniformOverride(
    const InstructionT &Instr) {
  UniformOverrides.insert(&Instr);
}
 
template <typename ContextT>
void GenericUniformityAnalysisImpl<ContextT>::addCustomUniformityCandidate(
    const InstructionT *I) {
  CustomUniformityCandidates.insert(I);
}
 
// Mark as divergent all external uses of values defined in \p DefCycle.
//
// A value V defined by a block B inside \p DefCycle may be used outside the
// cycle only if the use is a PHI in some exit block, or B dominates some exit
// block. Thus, we check uses as follows:
//
// - Check all PHIs in all exit blocks for inputs defined inside \p DefCycle.
// - For every block B inside \p DefCycle that dominates at least one exit
//   block, check all uses outside \p DefCycle.
//
// FIXME: This function does not distinguish between divergent and uniform
// exits. For each divergent exit, only the values that are live at that exit
// need to be propagated as divergent at their use outside the cycle.
template <typename ContextT>
void GenericUniformityAnalysisImpl<ContextT>::analyzeCycleExitDivergence(
    CycleRef DefCycle) {
  SmallVector<BlockT *> Exits;
  CI.getExitBlocks(DefCycle, Exits);
  for (auto *Exit : Exits) {
    for (auto &Phi : Exit->phis()) {
      if (usesValueFromCycle(Phi, DefCycle)) {
        markDivergent(Phi);
      }
    }
  }
 
  for (auto *BB : CI.getBlocks(DefCycle)) {
    if (!llvm::any_of(Exits,
                     [&](BlockT *Exit) { return DT.dominates(BB, Exit); }))
      continue;
    for (auto &II : *BB) {
      propagateTemporalDivergence(II, DefCycle);
    }
  }
}
 
template <typename ContextT>
void GenericUniformityAnalysisImpl<ContextT>::propagateCycleExitDivergence(
    const BlockT &DivExit, CycleRef InnerDivCycle) {
  LLVM_DEBUG(dbgs() << "\tpropCycleExitDiv " << Context.print(&DivExit)
                    << "\n");
  CycleRef DivCycle = InnerDivCycle;
  CycleRef OuterDivCycle = DivCycle;
  CycleRef ExitLevelCycle = CI.getCycle(&DivExit);
  const unsigned CycleExitDepth =
      ExitLevelCycle ? CI.getDepth(ExitLevelCycle) : 0;
 
  // Find outer-most cycle that does not contain \p DivExit
  while (DivCycle && CI.getDepth(DivCycle) > CycleExitDepth) {
    LLVM_DEBUG(dbgs() << "  Found exiting cycle: "
                      << Context.print(CI.getHeader(DivCycle)) << "\n");
    OuterDivCycle = DivCycle;
    DivCycle = CI.getParentCycle(DivCycle);
  }
  LLVM_DEBUG(dbgs() << "\tOuter-most exiting cycle: "
                    << Context.print(CI.getHeader(OuterDivCycle)) << "\n");
 
  if (!DivergentExitCycles.insert(OuterDivCycle))
    return;
 
  // Exit divergence does not matter if the cycle itself is assumed to
  // be divergent.
  for (auto C : AssumedDivergent) {
    if (CI.contains(C, OuterDivCycle))
      return;
  }
 
  analyzeCycleExitDivergence(OuterDivCycle);
}
 
template <typename ContextT>
void GenericUniformityAnalysisImpl<ContextT>::taintAndPushAllDefs(
    const BlockT &BB) {
  LLVM_DEBUG(dbgs() << "taintAndPushAllDefs " << Context.print(&BB) << "\n");
  for (const auto &I : instrs(BB)) {
    // Terminators do not produce values; they are divergent only if
    // the condition is divergent. That is handled when the divergent
    // condition is placed in the worklist.
    if (I.isTerminator())
      break;
 
    markDivergent(I);
  }
}
 
/// Mark divergent phi nodes in a join block
template <typename ContextT>
void GenericUniformityAnalysisImpl<ContextT>::taintAndPushPhiNodes(
    const BlockT &JoinBlock) {
  LLVM_DEBUG(dbgs() << "taintAndPushPhiNodes in " << Context.print(&JoinBlock)
                    << "\n");
  for (const auto &Phi : JoinBlock.phis()) {
    // FIXME: The non-undef value is not constant per se; it just happens to be
    // uniform and may not dominate this PHI. So assuming that the same value
    // reaches along all incoming edges may itself be undefined behaviour. This
    // particular interpretation of the undef value was added to
    // DivergenceAnalysis in the following review:
    //
    // https://reviews.llvm.org/D19013
    if (ContextT::isConstantOrUndefValuePhi(Phi))
      continue;
    markDivergent(Phi);
  }
}
 
/// Add \p Candidate to \p Cycles if it is not already contained in \p Cycles.
///
/// \return true iff \p Candidate was added to \p Cycles.
template <typename CycleInfoT>
bool insertIfNotContained(const CycleInfoT &CI, SmallVector<CycleRef> &Cycles,
                          CycleRef Candidate) {
  if (llvm::any_of(Cycles,
                   [&](CycleRef C) { return CI.contains(C, Candidate); }))
    return false;
  Cycles.push_back(Candidate);
  return true;
}
 
/// Return the outermost cycle made divergent by branch outside it.
///
/// If two paths that diverged outside an irreducible cycle join
/// inside that cycle, then that whole cycle is assumed to be
/// divergent. This does not apply if the cycle is reducible.
template <typename CycleInfoT, typename BlockT>
CycleRef getExtDivCycle(const CycleInfoT &CI, CycleRef Cycle,
                        const BlockT *DivTermBlock, const BlockT *JoinBlock) {
  assert(Cycle);
  assert(CI.contains(Cycle, JoinBlock));
 
  if (CI.contains(Cycle, DivTermBlock))
    return CycleRef();
 
  CycleRef OriginalCycle = Cycle;
  CycleRef Parent = CI.getParentCycle(Cycle);
  while (Parent && !CI.contains(Parent, DivTermBlock)) {
    Cycle = Parent;
    Parent = CI.getParentCycle(Cycle);
  }
 
  // If the original cycle is not the outermost cycle, then the outermost cycle
  // is irreducible. If the outermost cycle were reducible, then external
  // diverged paths would not reach the original inner cycle.
  (void)OriginalCycle;
  assert(Cycle == OriginalCycle || !CI.isReducible(Cycle));
 
  if (CI.isReducible(Cycle)) {
    assert(CI.getHeader(Cycle) == JoinBlock);
    return CycleRef();
  }
 
  LLVM_DEBUG(dbgs() << "cycle made divergent by external branch\n");
  return Cycle;
}
 
/// Return the outermost cycle made divergent by branch inside it.
///
/// This checks the "diverged entry" criterion defined in the
/// docs/ConvergenceAnalysis.html.
template <typename ContextT, typename CycleInfoT, typename BlockT,
          typename DominatorTreeT>
CycleRef getIntDivCycle(const CycleInfoT &CI, CycleRef Cycle,
                        const BlockT *DivTermBlock, const BlockT *JoinBlock,
                        const DominatorTreeT &DT, ContextT &Context) {
  LLVM_DEBUG(dbgs() << "examine join " << Context.print(JoinBlock)
                    << " for internal branch " << Context.print(DivTermBlock)
                    << "\n");
  if (DT.properlyDominates(DivTermBlock, JoinBlock))
    return CycleRef();
 
  // Find the smallest common cycle, if one exists.
  assert(Cycle && CI.contains(Cycle, JoinBlock));
  while (Cycle && !CI.contains(Cycle, DivTermBlock)) {
    Cycle = CI.getParentCycle(Cycle);
  }
  if (!Cycle || CI.isReducible(Cycle))
    return CycleRef();
 
  if (DT.properlyDominates(CI.getHeader(Cycle), JoinBlock))
    return CycleRef();
 
  LLVM_DEBUG(dbgs() << "  header " << Context.print(CI.getHeader(Cycle))
                    << " does not dominate join\n");
 
  CycleRef Parent = CI.getParentCycle(Cycle);
  while (Parent && !DT.properlyDominates(CI.getHeader(Parent), JoinBlock)) {
    LLVM_DEBUG(dbgs() << "  header " << Context.print(CI.getHeader(Parent))
                      << " does not dominate join\n");
    Cycle = Parent;
    Parent = CI.getParentCycle(Parent);
  }
 
  LLVM_DEBUG(dbgs() << "  cycle made divergent by internal branch\n");
  return Cycle;
}
 
template <typename ContextT, typename CycleInfoT, typename BlockT,
          typename DominatorTreeT>
CycleRef
getOutermostDivergentCycle(const CycleInfoT &CI, CycleRef Cycle,
                           const BlockT *DivTermBlock, const BlockT *JoinBlock,
                           const DominatorTreeT &DT, ContextT &Context) {
  if (!Cycle)
    return CycleRef();
 
  // First try to expand Cycle to the largest that contains JoinBlock
  // but not DivTermBlock.
  CycleRef Ext = getExtDivCycle(CI, Cycle, DivTermBlock, JoinBlock);
 
  // Continue expanding to the largest cycle that contains both.
  CycleRef Int =
      getIntDivCycle(CI, Cycle, DivTermBlock, JoinBlock, DT, Context);
 
  if (Int)
    return Int;
  return Ext;
}
 
template <typename ContextT>
bool GenericUniformityAnalysisImpl<ContextT>::isTemporalDivergent(
    const BlockT &ObservingBlock, const InstructionT &Def) const {
  const BlockT *DefBlock = Def.getParent();
  for (auto C = CI.getCycle(DefBlock); C && !CI.contains(C, &ObservingBlock);
       C = CI.getParentCycle(C)) {
    if (DivergentExitCycles.contains(C)) {
      return true;
    }
  }
  return false;
}
 
template <typename ContextT>
void GenericUniformityAnalysisImpl<ContextT>::analyzeControlDivergence(
    const InstructionT &Term) {
  const auto *DivTermBlock = Term.getParent();
  DivergentTermBlocks.insert(DivTermBlock);
  LLVM_DEBUG(dbgs() << "analyzeControlDiv " << Context.print(DivTermBlock)
                    << "\n");
 
  // Don't propagate divergence from unreachable blocks.
  if (!DT.isReachableFromEntry(DivTermBlock))
    return;
 
  const auto &DivDesc = SDA.getJoinBlocks(DivTermBlock);
  SmallVector<CycleRef> DivCycles;
 
  // Iterate over all blocks now reachable by a disjoint path join
  for (const auto *JoinBlock : DivDesc.JoinDivBlocks) {
    CycleRef C = CI.getCycle(JoinBlock);
    LLVM_DEBUG(dbgs() << "visiting join block " << Context.print(JoinBlock)
                      << "\n");
    if (CycleRef Outermost = getOutermostDivergentCycle(
            CI, C, DivTermBlock, JoinBlock, DT, Context)) {
      LLVM_DEBUG(dbgs() << "found divergent cycle\n");
      DivCycles.push_back(Outermost);
      continue;
    }
    taintAndPushPhiNodes(*JoinBlock);
  }
 
  // Sort by order of decreasing depth. This allows later cycles to be skipped
  // because they are already contained in earlier ones.
  llvm::sort(DivCycles, [this](CycleRef A, CycleRef B) {
    return CI.getDepth(A) > CI.getDepth(B);
  });
 
  // Cycles that are assumed divergent due to the diverged entry
  // criterion potentially contain temporal divergence depending on
  // the DFS chosen. Conservatively, all values produced in such a
  // cycle are assumed divergent. "Cycle invariant" values may be
  // assumed uniform, but that requires further analysis.
  for (auto C : DivCycles) {
    if (!insertIfNotContained(CI, AssumedDivergent, C))
      continue;
    LLVM_DEBUG(dbgs() << "process divergent cycle\n");
    for (const BlockT *BB : CI.getBlocks(C)) {
      taintAndPushAllDefs(*BB);
    }
  }
 
  CycleRef BranchCycle = CI.getCycle(DivTermBlock);
  assert(DivDesc.CycleDivBlocks.empty() || BranchCycle);
  for (const auto *DivExitBlock : DivDesc.CycleDivBlocks) {
    propagateCycleExitDivergence(*DivExitBlock, BranchCycle);
  }
}
 
template <typename ContextT>
void GenericUniformityAnalysisImpl<ContextT>::compute() {
  HasBranchDivergence = true;
 
  // All values on the Worklist are divergent.
  // Their users may not have been updated yet.
  while (!Worklist.empty()) {
    const InstructionT *I = Worklist.back();
    Worklist.pop_back();
 
    LLVM_DEBUG(dbgs() << "worklist pop: " << Context.print(I) << "\n");
 
    if (I->isTerminator()) {
      analyzeControlDivergence(*I);
      continue;
    }
 
    // propagate value divergence to users
    assert(hasDivergentDefs(*I) && "Worklist invariant violated!");
    pushUsers(*I);
  }
}
 
template <typename ContextT>
void GenericUniformityAnalysisImpl<ContextT>::recordTemporalDivergence(
    ConstValueRefT Val, const InstructionT *User, CycleRef C) {
  TemporalDivergenceList.emplace_back(Val, const_cast<InstructionT *>(User), C);
}
 
template <typename ContextT>
bool GenericUniformityAnalysisImpl<ContextT>::isAlwaysUniform(
    const InstructionT &Instr) const {
  return UniformOverrides.contains(&Instr);
}
 
template <typename ContextT>
bool GenericUniformityAnalysisImpl<ContextT>::printDivergentArgs(
    raw_ostream &) const {
  return false;
}
 
template <typename ContextT>
GenericUniformityInfo<ContextT>::GenericUniformityInfo(
    const DominatorTreeT &DT, const CycleInfoT &CI,
    const TargetTransformInfo *TTI) {
  DA.reset(new ImplT{DT, CI, TTI});
}
 
template <typename ContextT>
void GenericUniformityAnalysisImpl<ContextT>::print(raw_ostream &OS) const {
  // When we print Value, LLVM IR instruction, we want to print extra new line.
  // In LLVM IR print function for Value does not print new line at the end.
  // In MIR print for MachineInstr prints new line at the end.
  constexpr bool IsMIR = std::is_same<InstructionT, MachineInstr>::value;
  std::string NewLine = IsMIR ? "" : "\n";
 
  bool FoundDivergence = false;
 
  FoundDivergence |= printDivergentArgs(OS);
 
  if (!AssumedDivergent.empty()) {
    FoundDivergence = true;
    OS << "CYCLES ASSUMED DIVERGENT:\n";
    for (auto C : AssumedDivergent) {
      OS << "  " << CI.print(C) << '\n';
    }
  }
 
  if (!DivergentExitCycles.empty()) {
    FoundDivergence = true;
    OS << "CYCLES WITH DIVERGENT EXIT:\n";
    for (auto C : DivergentExitCycles) {
      OS << "  " << CI.print(C) << '\n';
    }
  }
 
  if (!TemporalDivergenceList.empty()) {
    FoundDivergence = true;
    OS << "\nTEMPORAL DIVERGENCE LIST:\n";
 
    for (auto [Val, UseInst, C] : TemporalDivergenceList) {
      OS << "Value         :" << Context.print(Val) << NewLine
         << "Used by       :" << Context.print(UseInst) << NewLine
         << "Outside cycle :" << CI.print(C) << "\n\n";
    }
  }
 
  for (auto &Block : F) {
    OS << "\nBLOCK " << Context.print(&Block) << '\n';
 
    OS << "DEFINITIONS\n";
    SmallVector<ConstValueRefT, 16> Defs;
    Context.appendBlockDefs(Defs, Block);
    for (auto Value : Defs) {
      if (isDivergent(Value)) {
        FoundDivergence = true;
        OS << "  DIVERGENT: ";
      } else {
        OS << "             ";
      }
      OS << Context.print(Value) << NewLine;
    }
 
    OS << "TERMINATORS\n";
    SmallVector<const InstructionT *, 8> Terms;
    Context.appendBlockTerms(Terms, Block);
    bool DivergentTerminators = hasDivergentTerminator(Block);
    if (DivergentTerminators)
      FoundDivergence = true;
    for (auto *T : Terms) {
      if (DivergentTerminators)
        OS << "  DIVERGENT: ";
      else
        OS << "             ";
      OS << Context.print(T) << NewLine;
    }
 
    OS << "END BLOCK\n";
  }
 
  if (!FoundDivergence)
    OS << "ALL VALUES UNIFORM\n";
}
 
template <typename ContextT>
iterator_range<
    typename GenericUniformityInfo<ContextT>::TemporalDivergenceTuple *>
GenericUniformityInfo<ContextT>::getTemporalDivergenceList() const {
  return make_range(DA->TemporalDivergenceList.begin(),
                    DA->TemporalDivergenceList.end());
}
 
template <typename ContextT>
const typename ContextT::FunctionT &
GenericUniformityInfo<ContextT>::getFunction() const {
  return DA->getFunction();
}
 
template <typename ContextT>
const typename GenericUniformityInfo<ContextT>::CycleInfoT &
GenericUniformityInfo<ContextT>::getCycleInfo() const {
  return DA->getCycleInfo();
}
 
/// Whether \p V is divergent at its definition.
/// A default-constructed instance (no analysis computed) reports everything
/// as uniform, which is conservatively correct for non-divergent targets.
template <typename ContextT>
bool GenericUniformityInfo<ContextT>::isDivergentAtDef(ConstValueRefT V) const {
  return DA && DA->isDivergent(V);
}
 
template <typename ContextT>
bool GenericUniformityInfo<ContextT>::isDivergentTerminator(
    const InstructionT *I) const {
  assert(I->isTerminator() && "Expected a terminator instruction!");
  return DA && DA->isDivergentTerminator(*I);
}
 
template <typename ContextT>
bool GenericUniformityInfo<ContextT>::isDivergentAtUse(const UseT &U) const {
  return DA && DA->isDivergentUse(U);
}
 
template <typename ContextT>
bool GenericUniformityInfo<ContextT>::hasDivergentTerminator(const BlockT &B) {
  return DA && DA->hasDivergentTerminator(B);
}
 
/// \brief T helper function for printing.
template <typename ContextT>
void GenericUniformityInfo<ContextT>::print(raw_ostream &Out) const {
  if (!DA) {
    Out << "  Uniformity analysis not computed (no branch divergence).\n";
    return;
  }
  DA->print(Out);
}
 
template <typename ContextT>
void llvm::ModifiedPostOrder<ContextT>::computeStackPO(
    SmallVectorImpl<const BlockT *> &Stack, const CycleInfoT &CI, CycleRef C,
    SmallPtrSetImpl<const BlockT *> &Finalized) {
  LLVM_DEBUG(dbgs() << "inside computeStackPO\n");
  while (!Stack.empty()) {
    auto *NextBB = Stack.back();
    if (Finalized.count(NextBB)) {
      Stack.pop_back();
      continue;
    }
    LLVM_DEBUG(dbgs() << "  visiting " << CI.getSSAContext().print(NextBB)
                      << "\n");
    CycleRef NestedCycle = CI.getCycle(NextBB);
    if (C != NestedCycle &&
        (!C || (NestedCycle && CI.contains(C, NestedCycle)))) {
      LLVM_DEBUG(dbgs() << "  found a cycle\n");
      while (CI.getParentCycle(NestedCycle) != C)
        NestedCycle = CI.getParentCycle(NestedCycle);
 
      SmallVector<BlockT *, 3> NestedExits;
      CI.getExitBlocks(NestedCycle, NestedExits);
      bool PushedNodes = false;
      for (auto *NestedExitBB : NestedExits) {
        LLVM_DEBUG(dbgs() << "  examine exit: "
                          << CI.getSSAContext().print(NestedExitBB) << "\n");
        if (C && !CI.contains(C, NestedExitBB))
          continue;
        if (Finalized.count(NestedExitBB))
          continue;
        PushedNodes = true;
        Stack.push_back(NestedExitBB);
        LLVM_DEBUG(dbgs() << "  pushed exit: "
                          << CI.getSSAContext().print(NestedExitBB) << "\n");
      }
      if (!PushedNodes) {
        // All loop exits finalized -> finish this node
        Stack.pop_back();
        computeCyclePO(CI, NestedCycle, Finalized);
      }
      continue;
    }
 
    LLVM_DEBUG(dbgs() << "  no nested cycle, going into DAG\n");
    // DAG-style
    bool PushedNodes = false;
    for (auto *SuccBB : successors(NextBB)) {
      LLVM_DEBUG(dbgs() << "  examine succ: "
                        << CI.getSSAContext().print(SuccBB) << "\n");
      if (C && !CI.contains(C, SuccBB))
        continue;
      if (Finalized.count(SuccBB))
        continue;
      PushedNodes = true;
      Stack.push_back(SuccBB);
      LLVM_DEBUG(dbgs() << "  pushed succ: " << CI.getSSAContext().print(SuccBB)
                        << "\n");
    }
    if (!PushedNodes) {
      // Never push nodes twice
      LLVM_DEBUG(dbgs() << "  finishing node: "
                        << CI.getSSAContext().print(NextBB) << "\n");
      Stack.pop_back();
      Finalized.insert(NextBB);
      appendBlock(*NextBB);
    }
  }
  LLVM_DEBUG(dbgs() << "exited computeStackPO\n");
}
 
template <typename ContextT>
void ModifiedPostOrder<ContextT>::computeCyclePO(
    const CycleInfoT &CI, CycleRef C,
    SmallPtrSetImpl<const BlockT *> &Finalized) {
  LLVM_DEBUG(dbgs() << "inside computeCyclePO\n");
  SmallVector<const BlockT *> Stack;
  auto *CycleHeader = CI.getHeader(C);
 
  LLVM_DEBUG(dbgs() << "  noted header: "
                    << CI.getSSAContext().print(CycleHeader) << "\n");
  assert(!Finalized.count(CycleHeader));
  Finalized.insert(CycleHeader);
 
  // Visit the header last
  LLVM_DEBUG(dbgs() << "  finishing header: "
                    << CI.getSSAContext().print(CycleHeader) << "\n");
  appendBlock(*CycleHeader, CI.isReducible(C));
 
  // Initialize with immediate successors
  for (auto *BB : successors(CycleHeader)) {
    LLVM_DEBUG(dbgs() << "  examine succ: " << CI.getSSAContext().print(BB)
                      << "\n");
    if (!CI.contains(C, BB))
      continue;
    if (BB == CycleHeader)
      continue;
    if (!Finalized.count(BB)) {
      LLVM_DEBUG(dbgs() << "  pushed succ: " << CI.getSSAContext().print(BB)
                        << "\n");
      Stack.push_back(BB);
    }
  }
 
  // Compute PO inside region
  computeStackPO(Stack, CI, C, Finalized);
 
  LLVM_DEBUG(dbgs() << "exited computeCyclePO\n");
}
 
/// \brief Generically compute the modified post order.
template <typename ContextT>
void llvm::ModifiedPostOrder<ContextT>::compute(const CycleInfoT &CI) {
  SmallPtrSet<const BlockT *, 32> Finalized;
  SmallVector<const BlockT *> Stack;
  auto *F = CI.getFunction();
  POIndex.assign(GraphTraits<const FunctionT *>::getMaxNumber(F), InvalidIndex);
  Stack.reserve(24); // FIXME made-up number
  Stack.push_back(&F->front());
  computeStackPO(Stack, CI, CycleRef(), Finalized);
}
 
} // namespace llvm
 
#undef DEBUG_TYPE
 
#endif // LLVM_ADT_GENERICUNIFORMITYIMPL_H