Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- GenericUniformAnalysis.cpp --------------------*- 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;

}