GenericUniformityImpl.h

//===- 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).
///
//===----------------------------------------------------------------------===//

#ifndef LLVM_ADT_GENERICUNIFORMITYIMPL_H
#define LLVM_ADT_GENERICUNIFORMITYIMPL_H

#include "llvm/ADT/GenericUniformityInfo.h"

#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SparseBitVector.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/Support/raw_ostream.h"

#include <set>

#define DEBUG_TYPE "uniformity"

using namespace llvm;

namespace llvm {

template <typename Range> auto unique(Range &&R) {
  return std::unique(adl_begin(R), adl_end(R));
}

/// 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<BlockT *> &Finalized);

  void computeStackPO(SmallVectorImpl<BlockT *> &Stack, const CycleInfoT &CI,
                      const CycleT *Cycle,
                      SmallPtrSetImpl<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 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 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;

  GenericUniformityAnalysisImpl(const FunctionT &F, const DominatorTreeT &DT,
                                const CycleInfoT &CI,
                                const TargetTransformInfo *TTI)
      : Context(CI.getSSAContext()), F(F), 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 Mark \p DivVal as a value that is always divergent.
  /// \returns Whether the tracked divergence state of \p DivVal changed.
  bool markDivergent(const InstructionT &I);
  bool markDivergent(ConstValueRefT DivVal);
  bool markDefsDivergent(const InstructionT &Instr,
                         bool AllDefsDivergent = true);

  /// \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 hasDivergentTerminator(const BlockT &B) const {
    return DivergentTermBlocks.contains(&B);
  }

  void print(raw_ostream &out) const;

protected:
  /// \brief Value/block pair representing a single phi input.
  struct PhiInput {
    ConstValueRefT value;
    BlockT *predBlock;

    PhiInput(ConstValueRefT value, BlockT *predBlock)
        : value(value), predBlock(predBlock) {}
  };

  const ContextT &Context;
  const FunctionT &F;
  const CycleInfoT &CI;
  const TargetTransformInfo *TTI = nullptr;

  // Detected/marked divergent values.
  std::set<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);

  /// \brief Internal implementation function for propagateCycleExitDivergence.
  void analyzeCycleExitDivergence(const CycleT &OuterDivCycle);

  /// \brief Mark all instruction as divergent that use a value defined in \p
  /// OuterDivCycle. Push their users on the worklist.
  void analyzeTemporalDivergence(const InstructionT &I,
                                 const CycleT &OuterDivCycle);

  /// \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 Val is divergent when read in \p ObservingBlock.
  bool isTemporalDivergent(const BlockT &ObservingBlock,
                           ConstValueRefT Val) 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");

    // Early stopping criterion
    int FloorIdx = CyclePOT.size() - 1;
    const BlockT *FloorLabel = nullptr;
    int DivTermIdx = CyclePOT.getIndex(&DivTermBlock);

    // Bootstrap with branch targets
    auto const *DivTermCycle = CI.getCycle(&DivTermBlock);
    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");
      }
      auto SuccIdx = CyclePOT.getIndex(SuccBlock);
      visitEdge(*SuccBlock, *SuccBlock);
      FloorIdx = std::min<int>(FloorIdx, SuccIdx);
    }

    while (true) {
      auto BlockIdx = FreshLabels.find_last();
      if (BlockIdx == -1 || BlockIdx < FloorIdx)
        break;

      LLVM_DEBUG(dbgs() << "Current labels:\n"; printDefs(dbgs()));

      FreshLabels.reset(BlockIdx);
      if (BlockIdx == DivTermIdx) {
        LLVM_DEBUG(dbgs() << "Skipping DivTermBlock\n");
        continue;
      }

      const auto *Block = CyclePOT[BlockIdx];
      LLVM_DEBUG(dbgs() << "visiting " << Context.print(Block) << " at index "
                        << BlockIdx << "\n");

      const auto *Label = BlockLabels[Block];
      assert(Label);

      bool CausedJoin = false;
      int LoweredFloorIdx = FloorIdx;

      // If the current block is the header of a reducible cycle that
      // contains the divergent branch, then the label should be
      // propagated to the cycle exits. Such a header is the "last
      // possible join" of any disjoint paths within this cycle. This
      // prevents detection of spurious joins at the entries of any
      // irreducible child cycles.
      //
      // This conclusion about the header is true for any choice of 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 without passing through H.
      //
      auto getReducibleParent = [&](const BlockT *Block) -> const CycleT * {
        if (!CyclePOT.isReducibleCycleHeader(Block))
          return nullptr;
        const auto *BlockCycle = CI.getCycle(Block);
        if (BlockCycle->contains(&DivTermBlock))
          return BlockCycle;
        return nullptr;
      };

      if (const auto *BlockCycle = getReducibleParent(Block)) {
        SmallVector<BlockT *, 4> BlockCycleExits;
        BlockCycle->getExitBlocks(BlockCycleExits);
        for (auto *BlockCycleExit : BlockCycleExits) {
          CausedJoin |= visitCycleExitEdge(*BlockCycleExit, *Label);
          LoweredFloorIdx =
              std::min<int>(LoweredFloorIdx, CyclePOT.getIndex(BlockCycleExit));
        }
      } else {
        for (const auto *SuccBlock : successors(Block)) {
          CausedJoin |= visitEdge(*SuccBlock, *Label);
          LoweredFloorIdx =
              std::min<int>(LoweredFloorIdx, CyclePOT.getIndex(SuccBlock));
        }
      }

      // Floor update
      if (CausedJoin) {
        // 1. Different labels pushed to successors
        FloorIdx = LoweredFloorIdx;
      } else if (FloorLabel != Label) {
        // 2. No join caused BUT we pushed a label that is different than the
        // last pushed label
        FloorIdx = LoweredFloorIdx;
        FloorLabel = 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>
typename llvm::GenericSyncDependenceAnalysis<ContextT>::DivergenceDescriptor
    llvm::GenericSyncDependenceAnalysis<ContextT>::EmptyDivergenceDesc;

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>
bool GenericUniformityAnalysisImpl<ContextT>::markDivergent(
    const InstructionT &I) {
  if (I.isTerminator()) {
    if (DivergentTermBlocks.insert(I.getParent()).second) {
      LLVM_DEBUG(dbgs() << "marked divergent term block: "
                        << Context.print(I.getParent()) << "\n");
      return true;
    }
    return false;
  }

  return markDefsDivergent(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);
}

template <typename ContextT>
void GenericUniformityAnalysisImpl<ContextT>::analyzeTemporalDivergence(
    const InstructionT &I, const CycleT &OuterDivCycle) {
  if (isDivergent(I))
    return;

  LLVM_DEBUG(dbgs() << "Analyze temporal divergence: " << Context.print(&I)
                    << "\n");
  if (!usesValueFromCycle(I, OuterDivCycle))
    return;

  if (isAlwaysUniform(I))
    return;

  if (markDivergent(I))
    Worklist.push_back(&I);
}

// Mark all external users of values defined inside \param
// OuterDivCycle as divergent.
//
// This follows all live out edges wherever they may lead. Potential
// users of values defined inside DivCycle could be anywhere in the
// dominance region of DivCycle (including its fringes for phi nodes).
// A cycle C dominates a block B iff every path from the entry block
// to B must pass through a block contained in C. If C is a reducible
// cycle (or natural loop), C dominates B iff the header of C
// dominates B. But in general, we iteratively examine cycle cycle
// exits and their successors.
template <typename ContextT>
void GenericUniformityAnalysisImpl<ContextT>::analyzeCycleExitDivergence(
    const CycleT &OuterDivCycle) {
  // Set of blocks that are dominated by the cycle, i.e., each is only
  // reachable from paths that pass through the cycle.
  SmallPtrSet<BlockT *, 16> DomRegion;

  // The boundary of DomRegion, formed by blocks that are not
  // dominated by the cycle.
  SmallVector<BlockT *> DomFrontier;
  OuterDivCycle.getExitBlocks(DomFrontier);

  // Returns true if BB is dominated by the cycle.
  auto isInDomRegion = [&](BlockT *BB) {
    for (auto *P : predecessors(BB)) {
      if (OuterDivCycle.contains(P))
        continue;
      if (DomRegion.count(P))
        continue;
      return false;
    }
    return true;
  };

  // Keep advancing the frontier along successor edges, while
  // promoting blocks to DomRegion.
  while (true) {
    bool Promoted = false;
    SmallVector<BlockT *> Temp;
    for (auto *W : DomFrontier) {
      if (!isInDomRegion(W)) {
        Temp.push_back(W);
        continue;
      }
      DomRegion.insert(W);
      Promoted = true;
      for (auto *Succ : successors(W)) {
        if (DomRegion.contains(Succ))
          continue;
        Temp.push_back(Succ);
      }
    }
    if (!Promoted)
      break;
    DomFrontier = Temp;
  }

  // At DomFrontier, only the PHI nodes are affected by temporal
  // divergence.
  for (const auto *UserBlock : DomFrontier) {
    LLVM_DEBUG(dbgs() << "Analyze phis after cycle exit: "
                      << Context.print(UserBlock) << "\n");
    for (const auto &Phi : UserBlock->phis()) {
      LLVM_DEBUG(dbgs() << "  " << Context.print(&Phi) << "\n");
      analyzeTemporalDivergence(Phi, OuterDivCycle);
    }
  }

  // All instructions inside the dominance region are affected by
  // temporal divergence.
  for (const auto *UserBlock : DomRegion) {
    LLVM_DEBUG(dbgs() << "Analyze non-phi users after cycle exit: "
                      << Context.print(UserBlock) << "\n");
    for (const auto &I : *UserBlock) {
      LLVM_DEBUG(dbgs() << "  " << Context.print(&I) << "\n");
      analyzeTemporalDivergence(I, OuterDivCycle);
    }
  }
}

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;

    // Mark this as divergent. We don't check if the instruction is
    // always uniform. In a cycle where the thread convergence is not
    // statically known, the instruction is not statically converged,
    // and its outputs cannot be statically uniform.
    if (markDivergent(I))
      Worklist.push_back(&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;
    if (markDivergent(Phi))
      Worklist.push_back(&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;

  if (Cycle->isReducible()) {
    assert(Cycle->getHeader() == JoinBlock);
    return nullptr;
  }

  const auto *Parent = Cycle->getParentCycle();
  while (Parent && !Parent->contains(DivTermBlock)) {
    // If the join is inside a child, then the parent must be
    // irreducible. The only join in a reducible cyle is its own
    // header.
    assert(!Parent->isReducible());
    Cycle = Parent;
    Parent = Cycle->getParentCycle();
  }

  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>
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>
bool GenericUniformityAnalysisImpl<ContextT>::isAlwaysUniform(
    const InstructionT &Instr) const {
  return UniformOverrides.contains(&Instr);
}

template <typename ContextT>
GenericUniformityInfo<ContextT>::GenericUniformityInfo(
    FunctionT &Func, const DominatorTreeT &DT, const CycleInfoT &CI,
    const TargetTransformInfo *TTI)
    : F(&Func) {
  DA.reset(new ImplT{Func, DT, CI, TTI});
  DA->initialize();
  DA->compute();
}

template <typename ContextT>
void GenericUniformityAnalysisImpl<ContextT>::print(raw_ostream &OS) const {
  bool haveDivergentArgs = false;

  if (DivergentValues.empty()) {
    assert(DivergentTermBlocks.empty());
    assert(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 ASSSUMED 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';
    }
  }

  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) << '\n';
    }

    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) << '\n';
    }

    OS << "END BLOCK\n";
  }
}

template <typename ContextT>
bool GenericUniformityInfo<ContextT>::hasDivergence() const {
  return DA->hasDivergence();
}

/// 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>::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<BlockT *> &Stack, const CycleInfoT &CI, const CycleT *Cycle,
    SmallPtrSetImpl<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<BlockT *> &Finalized) {
  LLVM_DEBUG(dbgs() << "inside computeCyclePO\n");
  SmallVector<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<BlockT *, 32> Finalized;
  SmallVector<BlockT *> Stack;
  auto *F = CI.getFunction();
  Stack.reserve(24); // FIXME made-up number
  Stack.push_back(GraphTraits<FunctionT *>::getEntryNode(F));
  computeStackPO(Stack, CI, nullptr, Finalized);
}

} // namespace llvm

#undef DEBUG_TYPE

#endif // LLVM_ADT_GENERICUNIFORMITYIMPL_H