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/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 CycleT = typename CycleInfoT::CycleT;
  using const_iterator = typename std::vector<BlockT *>::const_iterator;
 
  ModifiedPostOrder(const ContextT &C) : Context(C) {}
 
  bool empty() const { return m_order.empty(); }
  size_t size() const { return m_order.size(); }
 
  void clear() { m_order.clear(); }
  void compute(const CycleInfoT &CI);
 
  unsigned count(BlockT *BB) const { return POIndex.count(BB); }
  const BlockT *operator[](size_t idx) const { return m_order[idx]; }
 
  void appendBlock(const BlockT &BB, bool isReducibleCycleHeader = false) {
    POIndex[&BB] = m_order.size();
    m_order.push_back(&BB);
    LLVM_DEBUG(dbgs() << "ModifiedPO(" << POIndex[&BB]
                      << "): " << Context.print(&BB) << "\n");
    if (isReducibleCycleHeader)
      ReducibleCycleHeaders.insert(&BB);
  }
 
  unsigned getIndex(const BlockT *BB) const {
    assert(POIndex.count(BB));
    return POIndex.lookup(BB);
  }
 
  bool isReducibleCycleHeader(const BlockT *BB) const {
    return ReducibleCycleHeaders.contains(BB);
  }
 
private:
  SmallVector<const BlockT *> m_order;
  DenseMap<const BlockT *, unsigned> POIndex;
  SmallPtrSet<const BlockT *, 32> ReducibleCycleHeaders;
  const ContextT &Context;
 
  void computeCyclePO(const CycleInfoT &CI, const CycleT *Cycle,
                      SmallPtrSetImpl<const BlockT *> &Finalized);
 
  void computeStackPO(SmallVectorImpl<const BlockT *> &Stack,
                      const CycleInfoT &CI, const CycleT *Cycle,
                      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 CycleT = typename CycleInfoT::CycleT;
 
  using ConstBlockSet = SmallPtrSet<const BlockT *, 4>;
  using ModifiedPO = ModifiedPostOrder<ContextT>;
 
  // * if BlockLabels[B] == C then C is the dominating definition at
  //   block B
  // * if BlockLabels[B] == nullptr then we haven't seen B yet
  // * if BlockLabels[B] == B then:
  //   - B is a join point of disjoint paths from X, or,
  //   - B is an immediate successor of X (initial value), or,
  //   - B is X
  using BlockLabelMap = DenseMap<const BlockT *, const BlockT *>;
 
  /// 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;
    // Labels assigned to blocks on diverged paths.
    BlockLabelMap BlockLabels;
  };
 
  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 CycleT = typename CycleInfoT::CycleT;
 
  using SyncDependenceAnalysisT = GenericSyncDependenceAnalysis<ContextT>;
  using DivergenceDescriptorT =
      typename SyncDependenceAnalysisT::DivergenceDescriptor;
  using BlockLabelMapT = typename SyncDependenceAnalysisT::BlockLabelMap;
 
  using TemporalDivergenceTuple =
      std::tuple<ConstValueRefT, InstructionT *, const CycleT *>;
 
  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; }
 
  /// \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.
  /// \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 any value was marked or analyzed to be divergent.
  bool hasDivergence() const { return !DivergentValues.empty(); }
 
  /// \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 isDivergent(const InstructionT &I) const {
    if (I.isTerminator()) {
      return DivergentTermBlocks.contains(I.getParent());
    }
    return hasDivergentDefs(I);
  };
 
  /// \brief Whether \p Val is divergent at its definition.
  bool isDivergent(ConstValueRefT V) const { return DivergentValues.count(V); }
 
  bool isDivergentUse(const UseT &U) const;
 
  bool hasDivergentTerminator(const BlockT &B) const {
    return DivergentTermBlocks.contains(&B);
  }
 
  void print(raw_ostream &out) const;
 
  SmallVector<TemporalDivergenceTuple, 8> TemporalDivergenceList;
 
  void recordTemporalDivergence(ConstValueRefT, const InstructionT *,
                                const CycleT *);
 
protected:
  const ContextT &Context;
  const FunctionT &F;
  const CycleInfoT &CI;
  const TargetTransformInfo *TTI = nullptr;
 
  // Detected/marked divergent values.
  DenseSet<ConstValueRefT> DivergentValues;
  SmallPtrSet<const BlockT *, 32> DivergentTermBlocks;
 
  // Internal worklist for divergence propagation.
  std::vector<const InstructionT *> Worklist;
 
  /// \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.
  SmallPtrSet<const CycleT *, 16> 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<const CycleT *> 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,
                                    const CycleT &DivCycle);
 
  /// Mark as divergent all external uses of values defined in \p DefCycle.
  void analyzeCycleExitDivergence(const CycleT &DefCycle);
 
  /// \brief Mark as divergent all uses of \p I that are outside \p DefCycle.
  void propagateTemporalDivergence(const InstructionT &I,
                                   const CycleT &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, const CycleT &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 CycleT = typename CycleInfoT::CycleT;
 
  using ModifiedPO = ModifiedPostOrder<ContextT>;
  using SyncDependenceAnalysisT = GenericSyncDependenceAnalysis<ContextT>;
  using DivergenceDescriptorT =
      typename SyncDependenceAnalysisT::DivergenceDescriptor;
  using BlockLabelMapT = typename SyncDependenceAnalysisT::BlockLabelMap;
 
  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;
  BlockLabelMapT &BlockLabels;
 
  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(DivDesc->BlockLabels) {}
 
  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 = BlockLabels[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 = BlockLabels[&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");
      BlockLabels[&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");
    BlockLabels[&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);
    auto const *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.
    const CycleT *IrreducibleAncestor = [](const CycleT *C) -> const CycleT * {
      if (!C)
        return nullptr;
      if (C->isReducible())
        return nullptr;
      while (const CycleT *P = C->getParentCycle()) {
        if (P->isReducible())
          return C;
        C = P;
      }
      assert(!C->getParentCycle());
      assert(!C->isReducible());
      return C;
    }(DivTermCycle);
 
    // Bootstrap with branch targets
    for (const auto *SuccBlock : successors(&DivTermBlock)) {
      if (DivTermCycle && !DivTermCycle->contains(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 || !IrreducibleAncestor->contains(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 = BlockLabels[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)) {
        const auto *BlockCycle = CI.getCycle(Block);
        LLVM_DEBUG(dbgs() << BlockCycle->print(Context) << '\n');
        SmallVector<BlockT *, 4> BlockCycleExits;
        BlockCycle->getExitBlocks(BlockCycleExits);
        bool BranchIsInside = BlockCycle->contains(&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 (const auto *Cycle = CI.getCycle(&DivTermBlock); Cycle;
         Cycle = Cycle->getParentCycle()) {
      if (Cycle->isReducible()) {
        // The exit divergence of a reducible cycle is recorded while
        // propagating labels.
        continue;
      }
      SmallVector<BlockT *> Exits;
      Cycle->getExitBlocks(Exits);
      auto *Header = Cycle->getHeader();
      auto *HeaderLabel = BlockLabels[Header];
      for (const auto *Exit : Exits) {
        if (BlockLabels[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;
  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 (DivergentValues.insert(Val).second) {
    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);
}
 
// 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(
    const CycleT &DefCycle) {
  SmallVector<BlockT *> Exits;
  DefCycle.getExitBlocks(Exits);
  for (auto *Exit : Exits) {
    for (auto &Phi : Exit->phis()) {
      if (usesValueFromCycle(Phi, DefCycle)) {
        markDivergent(Phi);
      }
    }
  }
 
  for (auto *BB : DefCycle.blocks()) {
    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, const CycleT &InnerDivCycle) {
  LLVM_DEBUG(dbgs() << "\tpropCycleExitDiv " << Context.print(&DivExit)
                    << "\n");
  auto *DivCycle = &InnerDivCycle;
  auto *OuterDivCycle = DivCycle;
  auto *ExitLevelCycle = CI.getCycle(&DivExit);
  const unsigned CycleExitDepth =
      ExitLevelCycle ? ExitLevelCycle->getDepth() : 0;
 
  // Find outer-most cycle that does not contain \p DivExit
  while (DivCycle && DivCycle->getDepth() > CycleExitDepth) {
    LLVM_DEBUG(dbgs() << "  Found exiting cycle: "
                      << Context.print(DivCycle->getHeader()) << "\n");
    OuterDivCycle = DivCycle;
    DivCycle = DivCycle->getParentCycle();
  }
  LLVM_DEBUG(dbgs() << "\tOuter-most exiting cycle: "
                    << Context.print(OuterDivCycle->getHeader()) << "\n");
 
  if (!DivergentExitCycles.insert(OuterDivCycle).second)
    return;
 
  // Exit divergence does not matter if the cycle itself is assumed to
  // be divergent.
  for (const auto *C : AssumedDivergent) {
    if (C->contains(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 CycleT>
static bool insertIfNotContained(SmallVector<CycleT *> &Cycles,
                                 CycleT *Candidate) {
  if (llvm::any_of(Cycles,
                   [Candidate](CycleT *C) { return C->contains(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 CycleT, typename BlockT>
static const CycleT *getExtDivCycle(const CycleT *Cycle,
                                    const BlockT *DivTermBlock,
                                    const BlockT *JoinBlock) {
  assert(Cycle);
  assert(Cycle->contains(JoinBlock));
 
  if (Cycle->contains(DivTermBlock))
    return nullptr;
 
  const auto *OriginalCycle = Cycle;
  const auto *Parent = Cycle->getParentCycle();
  while (Parent && !Parent->contains(DivTermBlock)) {
    Cycle = Parent;
    Parent = Cycle->getParentCycle();
  }
 
  // 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 || !Cycle->isReducible());
 
  if (Cycle->isReducible()) {
    assert(Cycle->getHeader() == JoinBlock);
    return nullptr;
  }
 
  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 CycleT, typename BlockT,
          typename DominatorTreeT>
static const CycleT *
getIntDivCycle(const CycleT *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 nullptr;
 
  // Find the smallest common cycle, if one exists.
  assert(Cycle && Cycle->contains(JoinBlock));
  while (Cycle && !Cycle->contains(DivTermBlock)) {
    Cycle = Cycle->getParentCycle();
  }
  if (!Cycle || Cycle->isReducible())
    return nullptr;
 
  if (DT.properlyDominates(Cycle->getHeader(), JoinBlock))
    return nullptr;
 
  LLVM_DEBUG(dbgs() << "  header " << Context.print(Cycle->getHeader())
                    << " does not dominate join\n");
 
  const auto *Parent = Cycle->getParentCycle();
  while (Parent && !DT.properlyDominates(Parent->getHeader(), JoinBlock)) {
    LLVM_DEBUG(dbgs() << "  header " << Context.print(Parent->getHeader())
                      << " does not dominate join\n");
    Cycle = Parent;
    Parent = Parent->getParentCycle();
  }
 
  LLVM_DEBUG(dbgs() << "  cycle made divergent by internal branch\n");
  return Cycle;
}
 
template <typename ContextT, typename CycleT, typename BlockT,
          typename DominatorTreeT>
static const CycleT *
getOutermostDivergentCycle(const CycleT *Cycle, const BlockT *DivTermBlock,
                           const BlockT *JoinBlock, const DominatorTreeT &DT,
                           ContextT &Context) {
  if (!Cycle)
    return nullptr;
 
  // First try to expand Cycle to the largest that contains JoinBlock
  // but not DivTermBlock.
  const auto *Ext = getExtDivCycle(Cycle, DivTermBlock, JoinBlock);
 
  // Continue expanding to the largest cycle that contains both.
  const auto *Int = getIntDivCycle(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 (const CycleT *Cycle = CI.getCycle(DefBlock);
       Cycle && !Cycle->contains(&ObservingBlock);
       Cycle = Cycle->getParentCycle()) {
    if (DivergentExitCycles.contains(Cycle)) {
      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<const CycleT *> DivCycles;
 
  // Iterate over all blocks now reachable by a disjoint path join
  for (const auto *JoinBlock : DivDesc.JoinDivBlocks) {
    const auto *Cycle = CI.getCycle(JoinBlock);
    LLVM_DEBUG(dbgs() << "visiting join block " << Context.print(JoinBlock)
                      << "\n");
    if (const auto *Outermost = getOutermostDivergentCycle(
            Cycle, 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, [](const CycleT *A, const CycleT *B) {
    return A->getDepth() > B->getDepth();
  });
 
  // 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(AssumedDivergent, C))
      continue;
    LLVM_DEBUG(dbgs() << "process divergent cycle\n");
    for (const BlockT *BB : C->blocks()) {
      taintAndPushAllDefs(*BB);
    }
  }
 
  const auto *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() {
  // Initialize worklist.
  auto DivValuesCopy = DivergentValues;
  for (const auto DivVal : DivValuesCopy) {
    assert(isDivergent(DivVal) && "Worklist invariant violated!");
    pushUsers(DivVal);
  }
 
  // 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(isDivergent(*I) && "Worklist invariant violated!");
    pushUsers(*I);
  }
}
 
template <typename ContextT>
void GenericUniformityAnalysisImpl<ContextT>::recordTemporalDivergence(
    ConstValueRefT Val, const InstructionT *User, const CycleT *Cycle) {
  TemporalDivergenceList.emplace_back(Val, const_cast<InstructionT *>(User),
                                      Cycle);
}
 
template <typename ContextT>
bool GenericUniformityAnalysisImpl<ContextT>::isAlwaysUniform(
    const InstructionT &Instr) const {
  return UniformOverrides.contains(&Instr);
}
 
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 {
  bool haveDivergentArgs = false;
 
  // 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";
 
  // Control flow instructions may be divergent even if their inputs are
  // uniform. Thus, although exceedingly rare, it is possible to have a program
  // with no divergent values but with divergent control structures.
  if (DivergentValues.empty() && DivergentTermBlocks.empty() &&
      DivergentExitCycles.empty()) {
    OS << "ALL VALUES UNIFORM\n";
    return;
  }
 
  for (const auto &entry : DivergentValues) {
    const BlockT *parent = Context.getDefBlock(entry);
    if (!parent) {
      if (!haveDivergentArgs) {
        OS << "DIVERGENT ARGUMENTS:\n";
        haveDivergentArgs = true;
      }
      OS << "  DIVERGENT: " << Context.print(entry) << '\n';
    }
  }
 
  if (!AssumedDivergent.empty()) {
    OS << "CYCLES ASSUMED DIVERGENT:\n";
    for (const CycleT *cycle : AssumedDivergent) {
      OS << "  " << cycle->print(Context) << '\n';
    }
  }
 
  if (!DivergentExitCycles.empty()) {
    OS << "CYCLES WITH DIVERGENT EXIT:\n";
    for (const CycleT *cycle : DivergentExitCycles) {
      OS << "  " << cycle->print(Context) << '\n';
    }
  }
 
  if (!TemporalDivergenceList.empty()) {
    OS << "\nTEMPORAL DIVERGENCE LIST:\n";
 
    for (auto [Val, UseInst, Cycle] : TemporalDivergenceList) {
      OS << "Value         :" << Context.print(Val) << NewLine
         << "Used by       :" << Context.print(UseInst) << NewLine
         << "Outside cycle :" << Cycle->print(Context) << "\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))
        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);
    for (auto *T : terms) {
      if (divergentTerminators)
        OS << "  DIVERGENT: ";
      else
        OS << "             ";
      OS << Context.print(T) << NewLine;
    }
 
    OS << "END BLOCK\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>
bool GenericUniformityInfo<ContextT>::hasDivergence() const {
  return DA->hasDivergence();
}
 
template <typename ContextT>
const typename ContextT::FunctionT &
GenericUniformityInfo<ContextT>::getFunction() const {
  return DA->getFunction();
}
 
/// Whether \p V is divergent at its definition.
template <typename ContextT>
bool GenericUniformityInfo<ContextT>::isDivergent(ConstValueRefT V) const {
  return DA->isDivergent(V);
}
 
template <typename ContextT>
bool GenericUniformityInfo<ContextT>::isDivergent(const InstructionT *I) const {
  return DA->isDivergent(*I);
}
 
template <typename ContextT>
bool GenericUniformityInfo<ContextT>::isDivergentUse(const UseT &U) const {
  return DA->isDivergentUse(U);
}
 
template <typename ContextT>
bool GenericUniformityInfo<ContextT>::hasDivergentTerminator(const BlockT &B) {
  return DA->hasDivergentTerminator(B);
}
 
/// \brief T helper function for printing.
template <typename ContextT>
void GenericUniformityInfo<ContextT>::print(raw_ostream &out) const {
  DA->print(out);
}
 
template <typename ContextT>
void llvm::ModifiedPostOrder<ContextT>::computeStackPO(
    SmallVectorImpl<const BlockT *> &Stack, const CycleInfoT &CI,
    const CycleT *Cycle, 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");
    auto *NestedCycle = CI.getCycle(NextBB);
    if (Cycle != NestedCycle && (!Cycle || Cycle->contains(NestedCycle))) {
      LLVM_DEBUG(dbgs() << "  found a cycle\n");
      while (NestedCycle->getParentCycle() != Cycle)
        NestedCycle = NestedCycle->getParentCycle();
 
      SmallVector<BlockT *, 3> NestedExits;
      NestedCycle->getExitBlocks(NestedExits);
      bool PushedNodes = false;
      for (auto *NestedExitBB : NestedExits) {
        LLVM_DEBUG(dbgs() << "  examine exit: "
                          << CI.getSSAContext().print(NestedExitBB) << "\n");
        if (Cycle && !Cycle->contains(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 (Cycle && !Cycle->contains(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, const CycleT *Cycle,
    SmallPtrSetImpl<const BlockT *> &Finalized) {
  LLVM_DEBUG(dbgs() << "inside computeCyclePO\n");
  SmallVector<const BlockT *> Stack;
  auto *CycleHeader = Cycle->getHeader();
 
  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, Cycle->isReducible());
 
  // Initialize with immediate successors
  for (auto *BB : successors(CycleHeader)) {
    LLVM_DEBUG(dbgs() << "  examine succ: " << CI.getSSAContext().print(BB)
                      << "\n");
    if (!Cycle->contains(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, Cycle, 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();
  Stack.reserve(24); // FIXME made-up number
  Stack.push_back(&F->front());
  computeStackPO(Stack, CI, nullptr, Finalized);
}
 
} // namespace llvm
 
#undef DEBUG_TYPE
 
#endif // LLVM_ADT_GENERICUNIFORMITYIMPL_H