Add control dependence computation that computes control dependence equivalence classes.

[• dberlin]

Summary

Unlike other implementations commonly found, this does not require either a post-dominator
tree or post-dominance frontiers.
It computes the relationship in linear time and space, and in fact, requires less time
that computing post-dominators!

If we wanted to, we could make this incrementally updated in O(sqrt(N) log n) time.

(This is currently used by newgvn to solve a problem GVN has of trying to figure out where it can propagate edge equivalences to)

[• dberlin]

• Sigh, here are the tests

Updating D8568: Add control dependence computation that computes control dependence equivalence classes.

Unlike other implementations commonly found, this does not require either a post-dominator
tree or post-dominance frontiers.
It computes the relationship in...

[anemet]

test/Analysis/ControlDependence/testdiamond.ll

5–15

Hi Danny,

Quick question, is this control equivalence or control dependence? Without looking at the details, it looks more like control equiv to me. Can this analysis also provide control dependence?

Also probably a silly question, but aren't 'different' and 'same' control-equiv here? They both seem to be control-depended on start, no?

[• dberlin]

Update documentation, handle capping backedges

[• dberlin]

Actually, I thought of a case that won't work with that formulation:

Given
int a, b;
int main(void)
{

do {
    do {
       b = a +1;
   }
        while (b);
} while (a);
return 0;

}

b = a+ 1 is control dependent on both the while test edges.
Both both loops are in the same CDEQ set (for the same reason. In fact,
simplifycfg will just make one single huge loop out of this. )

So when you have things that are control dependent on multiple nodes in
nested loops, you won't be able to determine both of the edges it's
dependent on, since the equivalence class is essentially the set that is
result of an equality query. So you can't recover CD directly from it.
You can recover info about CONDS from it, you just don' t know what the
answer is.

That is, CDEQ(w) is exactly the set of of things {for all blocks v in CFG |
CONDS(v) == CONDS(w)}

So you know that things in the same set must have the same CONDS, you just
don't know what that CONDS is.

However, you do know the answer to what CONDS is limited to the edges
between the CDEQ blocks, and the boundary edges of the CDEQ blocks (IE the
edges to a different equivalence class).

I would bet you could compute this in linear time from CDEQ.
From CONDS, you can get CD.

Though I admit, i'm curious what you would want the CD sets for.
Most things i've seen really want control-region info (so they can treat
all things equivalent as one large basic block) or things like SESE regions
(which can be computed in linear time from these sets) or the program
structure tree or whatever.
These are all computable directly from these sets.

[anemet]

In D8568#149015, @dberlin wrote:

Actually, I thought of a case that won't work with that formulation:

Given
int a, b;
int main(void)
{

do {
    do {
       b = a +1;
   }
        while (b);
} while (a);
return 0;

}

b = a+ 1 is control dependent on both the while test edges.
Both both loops are in the same CDEQ set (for the same reason. In fact,
simplifycfg will just make one single huge loop out of this. )

So when you have things that are control dependent on multiple nodes in
nested loops, you won't be able to determine both of the edges it's
dependent on, since the equivalence class is essentially the set that is
result of an equality query. So you can't recover CD directly from it.
You can recover info about CONDS from it, you just don' t know what the
answer is.

That is, CDEQ(w) is exactly the set of of things {for all blocks v in CFG |
CONDS(v) == CONDS(w)}

So you know that things in the same set must have the same CONDS, you just
don't know what that CONDS is.

However, you do know the answer to what CONDS is limited to the edges
between the CDEQ blocks, and the boundary edges of the CDEQ blocks (IE the
edges to a different equivalence class).

I would bet you could compute this in linear time from CDEQ.
From CONDS, you can get CD.

Though I admit, i'm curious what you would want the CD sets for.

It would be for Loop Distribution where a partition is made up of the transitive closure of the dependent (data and control) instructions of the original seeding instructions.

Thanks,
Adam

Most things i've seen really want control-region info (so they can treat
all things equivalent as one large basic block) or things like SESE regions
(which can be computed in linear time from these sets) or the program
structure tree or whatever.
These are all computable directly from these sets.

[• dberlin]

Ah. I wouldn't try to do this kind of thing outside of polly, which
uses SCoP's (which is essentially a variant of the progarm structure
tree).
At the point you are doing loop distribution, you'd be better off
eating the cost of post-dominators or something.

The reason, as i understand it, that post-dominators is disfavored, is
that nobody preserves/updates it so it stays slow :)
If we fixed that problem, you'd get control dependence without issue.

Note that control dependence equivalence is much easier to maintain if
we wanted to, separately, (it can be maintained in sqrt(n) log n per
edge insertion/deletion) time

[Gerolf]

Hi Daniel,
Is avoiding pdom cost your major motivator for choosing the cycle equivalence/PST algorithm?
If the pdom issues were solved would you pick APT over PST?

No preference implied. I’m only curious about what motivated your choice

Also, is nGVN the only client you envision currently?

Thanks
Gerolf

[chandlerc]

I can't comment on the algorithmic side, but am happy to review the basic code.

First comment would be that if this is really only providing equivalence classes, it should be named appropriately. Probably ControlDependenceEquivalence or some such. Do that last though so the in-line comments aren't lost.

include/llvm/Analysis/ControlDependence.h

9–12 ↗

(On Diff #22893)

You need three '/'s for the doxygen stuff.

59–64 ↗

(On Diff #22893)

Is 'unsigned' enough? (I can believe it is, I just want to surface the question.)

lib/Analysis/ControlDependence.cpp

21–24 ↗

(On Diff #22893)

Why are these jammed in here with headers and usings?

29 ↗

(On Diff #22893)

Weird whitspace...

122–134 ↗

(On Diff #22893)

This looks like it could be cleaned up with early-continue patterns.

200–201 ↗

(On Diff #22893)

Missing vertical whitespace.

260–261 ↗

(On Diff #22893)

Keep braces symmetric.

311–321 ↗

(On Diff #22893)

Variable naming: Hi1Iter

376–377 ↗

(On Diff #22893)

Again, missing whitespace.

390–402 ↗

(On Diff #22893)

This code seems completely duplicated with the above?

410 ↗

(On Diff #22893)

TODO what?

433–434 ↗

(On Diff #22893)

Missing whitespace.

[• dberlin]

include/llvm/Analysis/ControlDependence.h

59–64 ↗

(On Diff #22893)

It should be.
We will never have more classes than basic blocks, and we already assume O(BasicBlocks) fits in unsigned elsewhere in the compiler.

lib/Analysis/ControlDependence.cpp

21–24 ↗

(On Diff #22893)

Fixed.

29 ↗

(On Diff #22893)

Fixed.

122–134 ↗

(On Diff #22893)

I'll take a looksee and see what can be done

200–201 ↗

(On Diff #22893)

fixed

260–261 ↗

(On Diff #22893)

fixed

311–321 ↗

(On Diff #22893)

Fixed these

376–377 ↗

(On Diff #22893)

Fixed

390–402 ↗

(On Diff #22893)

Yes, moved to a helper function

410 ↗

(On Diff #22893)

Fixed
(incomplete deletion, it used to be "make this O(1)")

433–434 ↗

(On Diff #22893)

Fixed

[• dberlin]

I'll also rename it to ControlDependenceEquivalence.

[• dberlin]

Update for review comments (whitespace fixes, refactoring of helpers and main DFS walk).

[chandlerc]

include/llvm/Analysis/ControlDependenceEquivalence.h

1–14

This header block needs lots of fixes...

32

Need a line break here. You can omit the '\brief' now apparently, but I don't care either way.

96–101

I suggest using include/llvm/ADT/iterator.h and iterator_facade_base to stub out much of the boiler plate here. Also, I would use 'BaseT' rather than 'super'.

109

No need for the inline keyword.

248

BlockData is *huge*. It doesn't belong in a densemap.

I think you want a DenseMap for the class numbers, and maybe some of the other *very* hot data, and a separate DenseMap<..., std::unique_ptr<BlockData>> for the rest.

lib/Analysis/ControlDependenceEquivalence.cpp

11

Missing line break.

327

'hi0iter'?

354–356

Why is this interesting?

include/llvm/Analysis/ControlDependenceEquivalence.h

+//===- ControlDependenceEquivalence.h - Compute Control Equivalence-------*- C++
+//-*---===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+// \file
+// \brief Determines control dependence equivalence classes for basic
+// blocks. Any two blocks having the same set of control dependences land in one
+// class.
+// ===---------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_CONTROLDEPENDENCEEQUIV_H
+#define LLVM_ANALYSIS_CONTROLDEPENDENCEEQUIV_H
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/IR/CFG.h"
+#include "llvm/IR/Function.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/raw_ostream.h"
+#include <list>
+#include <stack>
+
+namespace llvm {
+class BasicBlock;
+
+/// \brief Compute control dependence equivalence classes for all nodes of the
+/// CFG.
+/// Note that this implementation actually uses cycle equivalence to establish
+/// class numbers. Any two nodes are cycle equivalent if they occur in the same
+/// set of cycles. It can be shown that control dependence equivalence reduces
+/// to undirected cycle equivalence for strongly connected control flow graphs.
+///
+/// The algorithm is based on the paper, "The program structure tree: computing
+/// control regions in linear time" by Johnson, Pearson & Pingali (PLDI94) which
+/// also contains proofs for the aforementioned equivalence. References to line
+/// numbers in the algorithm from figure 4 have been added [line:x].
+class ControlDependenceEquivalence : public FunctionPass {
+public:
+  ControlDependenceEquivalence()
+      : FunctionPass(ID), Computed(false), FakeStart(nullptr),
+        FakeEnd(nullptr) {
+    initializeControlDependenceEquivalencePass(
+        *PassRegistry::getPassRegistry());
+  }
+  static char ID;
+
+  bool runOnFunction(Function &F) override;
+
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.setPreservesAll();
+  }
+  void releaseMemory() override;
+
+  void print(raw_ostream &O, const Module * = nullptr) const override;
+
+  /// \brief Return the control dependence class number for \p BB.  All basic
+  /// blocks with the same class number have the same control dependences
+  unsigned getClassNumber(BasicBlock *BB) {
+    assert(Computed && "Trying to get equivalence classes before computation");
+    return BlockInfo[BB].ClassNumber;
+  }
+
+private:
+  typedef enum { PredDirection, SuccDirection } DFSDirection;
+  struct Bracket;
+  typedef std::list<Bracket> BracketList;
+  struct Bracket {
+    // Direction in which this bracket was added.
+    DFSDirection Direction;
+    // Cached class when bracket was topmost.
+    unsigned RecentClass;
+    // Cached set-size when bracket was topmost.
+    unsigned RecentSize;
+    // Block that this bracket originates from.
+    const BasicBlock *From;
+    // Block that this bracket points to.
+    const BasicBlock *To;
+    // Whether this is a capping bracket
+    bool Capping;
+  };
+  typedef SmallVector<const BasicBlock *, 4> FakeEdgeListType;
+
+  /// \brief A combined iterator class that walks both real CFG edges, and ones
+  /// from a vector of CFG edges.
+  ///
+  /// We use combined iterators to allow fake and real edges to be next to each
+  /// other. This is used to connect entry/exit blocks, and other edges.  We do
+  /// not expect these will work for anything but our use.
+  template <class RealType, class FakeType>
+  class const_combined_iterator
+      : public std::iterator<std::forward_iterator_tag, const BasicBlock,
+                             ptrdiff_t, const BasicBlock *,
+                             const BasicBlock *> {
+    typedef std::iterator<std::forward_iterator_tag, const BasicBlock *,
+                          ptrdiff_t, const BasicBlock *,
+                          const BasicBlock *> super;
+
+  public:
+    typedef typename super::pointer pointer;
+    typedef typename super::reference reference;
+
+    // We need to know when we hit the end, so we have to have the end
+    // iterator too
+    inline const_combined_iterator(RealType Begin, RealType End,
+                                   FakeType FBegin, FakeType FEnd)
+        : Real(Begin), RealEnd(End), Fake(FBegin), FakeEnd(FEnd) {}
+    inline bool operator==(const_combined_iterator &x) const {
+      return Real == x.Real && Fake == x.Fake;
+    }
+    inline bool operator!=(const_combined_iterator &x) const {
+      return !operator==(x);
+    }
+    inline reference operator*() const {
+      if (Real != RealEnd)
+        return *Real;
+      if (Fake != FakeEnd)
+        return *Fake;
+      llvm_unreachable("Tried to access past the end of our iterator");
+    }
+    inline pointer *operator->() const { return &operator*(); }
+
+    inline const_combined_iterator &operator++() {
+      if (Real != RealEnd) {
+        ++Real;
+        return *this;
+      }
+      if (Fake != FakeEnd) {
+        ++Fake;
+        return *this;
+      }
+      llvm_unreachable("Fell off the end of the iterator");
+    }
+
+  private:
+    RealType Real;
+    RealType RealEnd;
+    FakeType Fake;
+    FakeType FakeEnd;
+  };
+
+  typedef const_combined_iterator<const_pred_iterator,
+                                  FakeEdgeListType::const_iterator>
+      const_combined_pred_iterator;
+  typedef const_combined_iterator<succ_const_iterator,
+                                  FakeEdgeListType::const_iterator>
+      const_combined_succ_iterator;
+  inline const_combined_pred_iterator
+  combined_pred_begin(const BasicBlock *B, const FakeEdgeListType &EL) {
+    return const_combined_pred_iterator(pred_begin(B), pred_end(B), EL.begin(),
+                                        EL.end());
+  }
+
+  inline const_combined_pred_iterator
+  combined_pred_end(const BasicBlock *B, const FakeEdgeListType &EL) {
+    return const_combined_pred_iterator(pred_end(B), pred_end(B), EL.end(),
+                                        EL.end());
+  }
+  inline const_combined_succ_iterator
+  combined_succ_begin(const BasicBlock *B, const FakeEdgeListType &EL) {
+    return const_combined_succ_iterator(succ_begin(B), succ_end(B), EL.begin(),
+                                        EL.end());
+  }
+
+  inline const_combined_succ_iterator
+  combined_succ_end(const BasicBlock *B, const FakeEdgeListType &EL) {
+    return const_combined_succ_iterator(succ_end(B), succ_end(B), EL.end(),
+                                        EL.end());
+  }
+
+  struct BlockData {
+    // Equivalence class number assigned to Block.
+    unsigned ClassNumber;
+    // Pre-order DFS number assigned to Block.
+    unsigned DFSNumber;
+    // Indicates Block has already been visited.
+    bool Visited;
+    // Indicates Block is on DFS stack during walk.
+    bool OnStack;
+    // List of brackets per Block.
+    BracketList BList;
+    // List of fake successor edges, if any
+    FakeEdgeListType FakeSuccEdges;
+    // List of fake predecessor edges, if any
+    FakeEdgeListType FakePredEdges;
+    // List of bracket iterators that point to us
+    std::list<BracketList::iterator> BracketIterators;
+    // Immediate child list
+    SmallVector<const BasicBlock *, 8> Children;
+    // Backedges List. This is backedges to other nodes, not to our node.
+    SmallVector<const BasicBlock *, 8> Backedges;
+    // Hi node value
+    const BasicBlock *Hi;
+    BlockData()
+        : ClassNumber(0), DFSNumber(0), Visited(false), OnStack(false) {}
+    ~BlockData() {}
+  };
+  struct DFSStackEntry {
+    // Direction currently used in DFS walk.
+    DFSDirection Direction;
+    // Iterator used for "pred" direction.
+    const_combined_pred_iterator Pred;
+    // Iterator end for "pred" direction
+    const_combined_pred_iterator PredEnd;
+    // Iterator used for "succ" direction.
+    const_combined_succ_iterator Succ;
+    // Iterator end for "succ" direction.
+    const_combined_succ_iterator SuccEnd;
+    // Parent Block of entry during DFS walk.
+    const BasicBlock *ParentBlock;
+    // Basic Block that this stack entry belongs to
+    const BasicBlock *Block;
+  };
+  // The stack is used during the undirected DFS walk.
+  typedef std::stack<DFSStackEntry> DFSStack;
+  void runUndirectedDFS(const BasicBlock *);
+
+  // Called during the undirected DFS, these functions are helpers for the
+  // walk. 
+  bool visitInPredDirection(DFSStack &, DFSStackEntry &);
+  bool visitInSuccDirection(DFSStack &, DFSStackEntry &);
+  void visitHelper(DFSStack &, DFSStackEntry &, const BasicBlock *,
+                   const BasicBlock *, DFSDirection);
+  
+  // Called at pre-visit during DFS walk.
+  void visitPre(const BasicBlock *);
+
+  // Called at mid-visit during DFS walk.
+  void visitMid(const BasicBlock *, DFSDirection);
+
+  // Called at post-visit during DFS walk.
+  void visitPost(const BasicBlock *, const BasicBlock *, DFSDirection);
+
+  // Called when visiting a backedge during DFS walk.
+  void visitBackedge(const BasicBlock *, const BasicBlock *, DFSDirection);
+
+  void pushDFS(DFSStack &, const BasicBlock *, const BasicBlock *,
+               DFSDirection);
+  void popDFS(DFSStack &, const BasicBlock *);
+  void debugBracketList(const BracketList &);
+  void removeBracketsPointingTo(BlockData &, const BasicBlock *, DFSDirection);
+  unsigned DFSNumber;
+  unsigned ClassNumber;
+  SmallDenseMap<const BasicBlock *, BlockData, 8> BlockInfo;
+  bool Computed;
+  const BasicBlock *FakeStart;
+  const BasicBlock *FakeEnd;
+};
+}
+
+#endif

include/llvm/Analysis/Passes.h

namespace llvm {
 
   //===--------------------------------------------------------------------===//
   //
   // createMemDerefPrinter - This pass collects memory dereferenceability
   // information and prints it with -analyze.
   //
   FunctionPass *createMemDerefPrinter();
 
+  //===--------------------------------------------------------------------===//
+  //
+  // createControlDependenceEquivalencePass - This pass collects control dependence info
+  // information
+  //
+  FunctionPass *createControlDependenceEquivalencePass();
+
+  //===--------------------------------------------------------------------===//
+  //
+  // createControlDependenceEquivalencePrinter - This pass collects control dependence info
+  // information and prints it with -print-controldeps
+  //
+  FunctionPass *createControlDependenceEquivalencePrinter();
+
 }
 
 #endif

include/llvm/InitializePasses.h

 void initializeForwardControlFlowIntegrityPass(PassRegistry&);
 void initializeFlattenCFGPassPass(PassRegistry&);
 void initializeStructurizeCFGPass(PassRegistry&);
 void initializeCFGViewerPass(PassRegistry&);
 void initializeConstantHoistingPass(PassRegistry&);
 void initializeCodeGenPreparePass(PassRegistry&);
 void initializeConstantMergePass(PassRegistry&);
 void initializeConstantPropagationPass(PassRegistry&);
+void initializeControlDependenceEquivalencePass(PassRegistry&);
+void initializeControlDependenceEquivalencePrinterPass(PassRegistry&);
 void initializeMachineCopyPropagationPass(PassRegistry&);
 void initializeCostModelAnalysisPass(PassRegistry&);
 void initializeCorrelatedValuePropagationPass(PassRegistry&);
 void initializeDAEPass(PassRegistry&);
 void initializeDAHPass(PassRegistry&);
 void initializeDCEPass(PassRegistry&);
 void initializeDSEPass(PassRegistry&);
 void initializeDeadInstEliminationPass(PassRegistry&);

include/llvm/LinkAllPasses.h

ForcePassLinking() {
       (void) llvm::createBreakCriticalEdgesPass();
       (void) llvm::createCallGraphPrinterPass();
       (void) llvm::createCallGraphViewerPass();
       (void) llvm::createCFGSimplificationPass();
       (void) llvm::createCFLAliasAnalysisPass();
       (void) llvm::createStructurizeCFGPass();
       (void) llvm::createConstantMergePass();
       (void) llvm::createConstantPropagationPass();
+      (void) llvm::createControlDependenceEquivalencePass();
+      (void) llvm::createControlDependenceEquivalencePrinter();
       (void) llvm::createCostModelAnalysisPass();
       (void) llvm::createDeadArgEliminationPass();
       (void) llvm::createDeadCodeEliminationPass();
       (void) llvm::createDeadInstEliminationPass();
       (void) llvm::createDeadStoreEliminationPass();
       (void) llvm::createDependenceAnalysisPass();
       (void) llvm::createDivergenceAnalysisPass();
       (void) llvm::createDomOnlyPrinterPass();

lib/Analysis/Analysis.cpp

void llvm::initializeAnalysis(PassRegistry &Registry) {
   initializeBlockFrequencyInfoPass(Registry);
   initializeBranchProbabilityInfoPass(Registry);
   initializeCostModelAnalysisPass(Registry);
   initializeCFGViewerPass(Registry);
   initializeCFGPrinterPass(Registry);
   initializeCFGOnlyViewerPass(Registry);
   initializeCFGOnlyPrinterPass(Registry);
   initializeCFLAliasAnalysisPass(Registry);
+  initializeControlDependenceEquivalencePass(Registry);
+  initializeControlDependenceEquivalencePrinterPass(Registry);
   initializeDependenceAnalysisPass(Registry);
   initializeDelinearizationPass(Registry);
   initializeDivergenceAnalysisPass(Registry);
   initializeDominanceFrontierPass(Registry);
   initializeDomViewerPass(Registry);
   initializeDomPrinterPass(Registry);
   initializeDomOnlyViewerPass(Registry);
   initializePostDomViewerPass(Registry);

lib/Analysis/CMakeLists.txt

add_llvm_library(LLVMAnalysis
   CFG.cpp
   CFGPrinter.cpp
   CFLAliasAnalysis.cpp
   CGSCCPassManager.cpp
   CaptureTracking.cpp
   CostModel.cpp
   CodeMetrics.cpp
   ConstantFolding.cpp
+  ControlDependenceEquivalence.cpp
   Delinearization.cpp
   DependenceAnalysis.cpp
   DivergenceAnalysis.cpp
   DomPrinter.cpp
   DominanceFrontier.cpp
   IVUsers.cpp
   InstCount.cpp
   InstructionSimplify.cpp

lib/Analysis/ControlDependenceEquivalence.cpp

+//===- ControlDependenceEquivalence.cpp - Compute Control Equivalence------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///\brief  This implements a pass to compute control dependence equivalence
+/// classes.
+//===----------------------------------------------------------------------===//
+#include "llvm/Analysis/ControlDependenceEquivalence.h"
+#include "llvm/Analysis/Passes.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/SmallVector.h"
+#include "llvm/Support/Debug.h"
+#include <queue>
+#include <utility>
+#include <algorithm>
+using namespace llvm;
+
+#define DEBUG_TYPE "controlequiv"
+
+char ControlDependenceEquivalence::ID = 0;
+
+INITIALIZE_PASS(ControlDependenceEquivalence, "controldep",
+                "Control Dependence Construction", true, true);
+
+/// \brief Run the main algorithm starting from the exit blocks. We proceed to
+/// perform an undirected depth-first backwards traversal that determines class
+/// numbers for all participating blocks. Takes O(E) time and O(N) space.
+bool ControlDependenceEquivalence::runOnFunction(Function &F) {
+  Computed = false;
+  DFSNumber = 0;
+  ClassNumber = 1;
+  // The algorithm requires we transform the CFG into a strongly connected
+  // component. We make a fake end and fake start, connect exiting blocks to the
+  // fake end, and then connect the fake start and the real start.  We then
+  // start the DFS walk from the fake start block.
+  // The fake start also ensures that, for single block functions, we hit a
+  // backedge.  If we did not have a fake start, we would have to special case
+  // the single block functions.
+  FakeStart = BasicBlock::Create(F.getContext(), "FakeStart");
+  FakeEnd = BasicBlock::Create(F.getContext(), "FakeEnd");
+  BlockInfo[FakeStart].FakePredEdges.push_back(FakeEnd);
+  BlockInfo[FakeEnd].FakeSuccEdges.push_back(FakeStart);
+  BlockInfo[&F.getEntryBlock()].FakePredEdges.push_back(FakeStart);
+  BlockInfo[FakeStart].FakeSuccEdges.push_back(&F.getEntryBlock());
+
+  for (auto &B : F) {
+    BlockData &Info = BlockInfo[&B];
+    // If this is a reverse-unreachable block, connect it to fake start
+    // If we don't do this, we can end up in situations where we never hit a
+    // backedge, triggering an assert below
+    if (pred_empty(&B) && &B != &F.getEntryBlock()) {
+      Info.FakePredEdges.push_back(FakeStart);
+      BlockInfo[FakeStart].FakeSuccEdges.push_back(&B);
+    }
+    // If there are no successors, or it only connects to itself,  we need to
+    // connect it to the exit block
+    if (succ_empty(&B)) {
+      // Connect leaves to fake end
+      Info.FakeSuccEdges.push_back(FakeEnd);
+      BlockInfo[FakeEnd].FakePredEdges.push_back(&B);
+    }
+  }
+  runUndirectedDFS(FakeEnd);
+  Computed = true;
+  return false;
+}
+
+void ControlDependenceEquivalence::releaseMemory() {
+  if (Computed) {
+    BlockInfo.clear();
+    delete FakeStart;
+    FakeStart = nullptr;
+    delete FakeEnd;
+    FakeEnd = nullptr;
+  }
+  Computed = false;
+}
+
+void ControlDependenceEquivalence::print(raw_ostream &O,
+                                         const Module *M) const {}
+
+/// \brief Perform the common part of the successor and predecessor visits.
+///
+/// Different iterator types make sharing all of the pred/successor visitation
+/// code hard, this is the part that can be shared between the two.
+void ControlDependenceEquivalence::visitHelper(DFSStack &Stack,
+                                               DFSStackEntry &Entry,
+                                               const BasicBlock *Block,
+                                               const BasicBlock *Next,
+                                               DFSDirection Direction) {
+  BlockData &Info = BlockInfo.find(Next)->second;
+  if (Info.Visited)
+    return;
+  // If it's on the stack, we've found a backedge, otherwise, push it
+  // and preorder-visit
+  if (Info.OnStack) {
+    DEBUG(dbgs() << "Maybe visit succ backedge\n");
+    if (Block != Entry.ParentBlock) {
+      BlockInfo[Block].Backedges.push_back(Next);
+      visitBackedge(Block, Next, Direction);
+    }
+  } else {
+    BlockInfo[Block].Children.push_back(Next);
+    pushDFS(Stack, Next, Block, Direction);
+    visitPre(Next);
+  }
+}
+
+/// \brief Perform the successor visit part of the undirected DFS.
+///
+/// \return True if we are completely done with the stack entry.
+bool ControlDependenceEquivalence::visitInSuccDirection(DFSStack &Stack,
+                                                        DFSStackEntry &Entry) {
+  const BasicBlock *B = Entry.Block;
+
+  if (Entry.Succ != Entry.SuccEnd) {
+    const BasicBlock *Succ = *Entry.Succ;
+    ++(Entry.Succ);
+    visitHelper(Stack, Entry, B, Succ, SuccDirection);
+    return false;
+  }
+  // Swap directions to predecessors
+  if (Entry.Pred != Entry.PredEnd) {
+    Entry.Direction = PredDirection;
+    visitMid(B, SuccDirection);
+    return false;
+  }
+  return true;
+}
+
+/// \brief Perform the predecessor visit part of the undirected DFS.
+///
+/// \return True if we are completely done with the stack entry.
+bool ControlDependenceEquivalence::visitInPredDirection(DFSStack &Stack,
+                                                        DFSStackEntry &Entry) {
+  const BasicBlock *B = Entry.Block;
+
+  if (Entry.Pred != Entry.PredEnd) {
+    const BasicBlock *Pred = *Entry.Pred;
+    ++(Entry.Pred);
+    visitHelper(Stack, Entry, B, Pred, PredDirection);
+    return false;
+  }
+  // Swap directions to successors
+  if (Entry.Succ != Entry.SuccEnd) {
+    Entry.Direction = SuccDirection;
+    visitMid(B, PredDirection);
+    return false;
+  }
+  return true;
+}
+
+/// \brief Performs and undirected DFS walk of the CFG.
+///
+/// Conceptually all nodes are expanded, splitting "predecessors" and
+/// "successors" out into separate nodes.  During the traversal, edges towards
+/// the representative type are preferred.
+///
+///   \ /        - Pre-visit: When N1 is visited in direction D the preferred
+///    x   N1      edge towards N is taken next, calling VisitPre(N).
+///    |         - Mid-visit: After all edges out of N2 in direction D have
+///    |   N       been visited, we switch the direction and start considering
+///    |           edges out of N1 now, and we call VisitMid(N).
+///    x   N2    - Post-visit: After all edges out of N1 in direction opposite
+///   / \          to D have been visited, we pop N and call VisitPost(N).
+///
+/// This will yield a true spanning tree (without cross or forward edges) and
+/// also discover proper back edges in both directions.
+void ControlDependenceEquivalence::runUndirectedDFS(
+    const BasicBlock *StartBlock) {
+  DFSStack Stack;
+  // Start out walking backwards
+  pushDFS(Stack, StartBlock, nullptr, PredDirection);
+
+  while (!Stack.empty()) {
+    DFSStackEntry &Entry = Stack.top();
+    const BasicBlock *B = Entry.Block;
+    DEBUG(dbgs() << "Starting from block ");
+    DEBUG(B->printAsOperand(dbgs()));
+    DEBUG(dbgs() << "\n");
+    // First visit in pred direction, then swap directions, then visit in succ
+    // direction, and swap back.  Swapping is handling by the visit functins.
+    if (Entry.Direction == PredDirection) {
+      if (!visitInPredDirection(Stack, Entry))
+        continue;
+    }
+    if (Entry.Direction == SuccDirection) {
+      if (!visitInSuccDirection(Stack, Entry))
+        continue;
+    }
+    // Pop block from stack when done with all preds and succs.
+    assert(Entry.Pred == Entry.PredEnd &&
+           "Did not finish predecessors before popping");
+    assert(Entry.Succ == Entry.SuccEnd &&
+           "Did not finish successors before popping");
+    popDFS(Stack, B);
+    visitPost(B, Entry.ParentBlock, Entry.Direction);
+  }
+}
+
+/// \brief Push an entry onto the DFS stack.
+void ControlDependenceEquivalence::pushDFS(DFSStack &Stack, const BasicBlock *B,
+                                           const BasicBlock *From,
+                                           DFSDirection Direction) {
+  auto BlockResult = BlockInfo.find(B);
+  assert(BlockResult != BlockInfo.end() && "Should have found block data");
+
+  auto &BlockResultData = BlockResult->second;
+  assert(!BlockResultData.Visited && "Should not have been visited yet");
+
+  BlockResultData.OnStack = true;
+  Stack.push(DFSStackEntry{
+      Direction, combined_pred_begin(B, BlockResultData.FakePredEdges),
+      combined_pred_end(B, BlockResultData.FakePredEdges),
+      combined_succ_begin(B, BlockResultData.FakeSuccEdges),
+      combined_succ_end(B, BlockResultData.FakeSuccEdges), From, B});
+}
+
+/// \brief Pop an entry from the DFS stack.
+void ControlDependenceEquivalence::popDFS(DFSStack &Stack,
+                                          const BasicBlock *B) {
+  assert(Stack.top().Block == B && "Stack top is wrong");
+  auto BlockResult = BlockInfo.find(B);
+
+  assert(BlockResult != BlockInfo.end() && "Should have found block data");
+  auto &BlockResultData = BlockResult->second;
+  BlockResultData.OnStack = false;
+  BlockResultData.Visited = true;
+  Stack.pop();
+}
+
+/// \brief Pre-order visitation is only used to generate DFS numbers for the
+/// blocks.
+void ControlDependenceEquivalence::visitPre(const BasicBlock *B) {
+  DEBUG(dbgs() << "pre-order visit of block ");
+  DEBUG(B->printAsOperand(dbgs()));
+  DEBUG(dbgs() << "\n");
+
+  BlockInfo[B].DFSNumber = ++DFSNumber;
+  DEBUG(dbgs() << "Assigned DFS Number " << BlockInfo[B].DFSNumber << "\n");
+}
+
+void ControlDependenceEquivalence::debugBracketList(const BracketList &BList) {
+  dbgs() << "{";
+  for (auto &Bracket : BList) {
+    dbgs() << "(";
+    Bracket.From->printAsOperand(dbgs());
+    dbgs() << ",";
+    Bracket.To->printAsOperand(dbgs());
+    dbgs() << ") ";
+    if (Bracket.Capping)
+      dbgs() << "[capping]";
+  }
+  dbgs() << "}";
+}
+
+void ControlDependenceEquivalence::removeBracketsPointingTo(
+    BlockData &Info, const BasicBlock *B, DFSDirection Direction) {
+  for (auto BII = Info.BracketIterators.begin(),
+            BIE = Info.BracketIterators.end();
+       BII != BIE;) {
+    BracketList::iterator &BLI = *BII;
+    Bracket &BR = *BLI;
+    if (BR.To == B && BR.Direction != Direction) {
+      Info.BList.erase(BLI);
+      BII = Info.BracketIterators.erase(BII);
+    } else {
+      ++BII;
+    }
+  }
+}
+
+void ControlDependenceEquivalence::visitMid(const BasicBlock *B,
+                                            DFSDirection Direction) {
+  DEBUG(dbgs() << "mid-order visit of block ");
+  DEBUG(B->printAsOperand(dbgs()));
+  DEBUG(dbgs() << "\n");
+  BlockData &Info = BlockInfo[B];
+  BracketList &BList = Info.BList;
+  // Remove brackets pointing to this node [line:19].
+  DEBUG(dbgs() << "Removing brackets pointing to ");
+  DEBUG(B->printAsOperand(dbgs()));
+  DEBUG(dbgs() << "\n");
+
+  // By the time we hit this node, we are guaranteed these iterators will point
+  // into our list, because it must have been spliced into us.
+  removeBracketsPointingTo(Info, B, Direction);
+
+  // Potentially introduce artificial dependency from this to start or this to
+  // end. This case happens when we hit things like unconnected infinite
+  // loops, or other similar situations.  Rather than attempt to connect every
+  // possible situation to fake start or fake end ahead of time, it's a lot
+  // easier to just do it here.
+  if (BList.empty()) {
+    // The backedge goes to the opposite place of the direction, IE start for
+    // succs, end for preds
+    if (Direction == PredDirection)
+      visitBackedge(B, FakeEnd, PredDirection);
+    else
+      visitBackedge(B, FakeStart, SuccDirection);
+  }
+
+  assert(!BList.empty() && "This should have never happened at this point, we "
+                           "should have hit at least one backedge");
+
+  // Handle capping brackets. This is a corrected version of the algorithm, from
+  // "The Static Single Information Form", by C. Scott Ananian.  The basic
+  // notion of capping brackets is as follows: The algorithm depends on <topmost
+  // bracket, bracket size> being a compact name for the equivalence
+  // class. Normally, in even unstructured trees (remember, we are really
+  // working on a DFS spanning tree), the innermost bracket will end up as the
+  // topmost bracket, so there is no need to store all of the bracket info for
+  // that edge.  However, when you merge two children's bracket sets, it's not
+  // clear which one is really the innermost anymore, and thus, what the new
+  // topmost bracket should be.  If you choose "the wrong" one, you will end up
+  // saying things are not cycle equivalent that are.  To solve this, capping
+  // brackets are added, which are the new "topmost" bracket, so that the
+  // children can be concatenated in any order, and still give the right answer.
+  // Very few real CFGs depend on capping edges being correct.
+
+  const BasicBlock *Hi0 = nullptr;
+  if (Info.Backedges.size() > 0) {
+    auto hi0iter = std::max_element(
+        Info.Backedges.begin(), Info.Backedges.end(),
+        [this](const BasicBlock *A, const BasicBlock *B) {
+          return BlockInfo[A].DFSNumber < BlockInfo[B].DFSNumber;
+        });
+    Hi0 = *hi0iter;
+  }
+  const BasicBlock *Hi1 = nullptr;
+  const BasicBlock *Hi2 = nullptr;
+  if (Info.Children.size() > 0) {
+    if (Info.Children.size() == 1)
+      Hi1 = Info.Children[0];
+    else {
+      // Get the min and the max through our children
+      auto Hi1Iter = std::min_element(
+          Info.Children.begin(), Info.Children.end(),
+          [this](const BasicBlock *A, const BasicBlock *B) {
+            return BlockInfo[A].DFSNumber < BlockInfo[B].DFSNumber;
+          });
+      auto Hi2Iter = std::max_element(
+          Info.Children.begin(), Info.Children.end(),
+          [this](const BasicBlock *A, const BasicBlock *B) {
+            return BlockInfo[A].DFSNumber < BlockInfo[B].DFSNumber;
+          });
+      Hi1 = *Hi1Iter;
+      Hi2 = *Hi2Iter;
+
+      // This is the original algorithm's version of this
+      // // Get the lowest two elements by DFS number, which in turn are the
+      // // highest two points in the tree.
+      // std::nth_element(Info.Children.begin(), Info.Children.begin() + 1,
+      // Info.Children.end(),
+      //                  [this](const BasicBlock *A, const BasicBlock *B) {
+      //                    return BlockInfo[A].DFSNumber <
+      //                    BlockInfo[B].DFSNumber;
+      //                  });
+      // Hi1 = Info.Children[0];
+      // Hi2 = Info.Children[1];
+    }
+  }
+  if (Hi0 == nullptr)
+    Info.Hi = Hi1;
+  else if (Hi1 == nullptr)
+    Info.Hi = Hi0;
+  else
+    Info.Hi = BlockInfo[Hi0].DFSNumber < BlockInfo[Hi1].DFSNumber ? Hi0 : Hi1;
+
+  // This is the original version of the algorithm (line 27)
+  // if (Hi2 && (Hi0 == nullptr || BlockInfo[Hi2].DFSNumber <
+  // BlockInfo[Hi0].DFSNumber)) {
+  if (Info.Children.size() > 1) {
+    // Push capping backedge onto the bracket list [line:29].
+    BlockData &Info = BlockInfo[B];
+    BracketList &BList = Info.BList;
+    auto Place =
+        BList.insert(BList.end(), Bracket{Direction, 0, 0, B, Hi2, true});
+    BlockInfo[Hi2].BracketIterators.push_back(Place);
+  }
+  // Capping backedges are specific to the non-representative nodes, so when we
+  // switch directions (and thus, switch non-representative nodes from N1 to N2,
+  // above), we need to
+  // reset for the new children and backedges
+  Info.Children.clear();
+  Info.Backedges.clear();
+
+  DEBUG(dbgs() << "Bracket list is ");
+  DEBUG(debugBracketList(BList));
+  DEBUG(dbgs() << "\n");
+
+  // Potentially start a new equivalence class [line:37]
+  Bracket &Recent = BList.back();
+  if (Recent.RecentSize != BList.size()) {
+    Recent.RecentSize = BList.size();
+    Recent.RecentClass = ++ClassNumber;
+  }
+  Info.ClassNumber = Recent.RecentClass;
+
+  DEBUG(dbgs() << "Assigned class number is " << Info.ClassNumber << "\n");
+}
+
+void ControlDependenceEquivalence::visitPost(const BasicBlock *B,
+                                             const BasicBlock *ParentBlock,
+                                             DFSDirection Direction) {
+  DEBUG(dbgs() << "post-order visit of block ");
+  DEBUG(B->printAsOperand(dbgs()));
+  DEBUG(dbgs() << "\n");
+  BlockData &Info = BlockInfo[B];
+  BracketList &BList = Info.BList;
+  // Remove brackets pointing to this node [line:19].
+  DEBUG(dbgs() << "Removing brackets pointing to ");
+  DEBUG(B->printAsOperand(dbgs()));
+  DEBUG(dbgs() << "\n");
+
+  // By the time we hit this node, we are guaranteed these iterators will point
+  // into our list, because it must have been spliced into us.
+  removeBracketsPointingTo(Info, B, Direction);
+
+  // Propagate bracket list up the DFS tree [line:13].
+  if (ParentBlock != nullptr) {
+    DEBUG(dbgs() << "Splicing bracket into ");
+    DEBUG(ParentBlock->printAsOperand(dbgs()));
+    DEBUG(dbgs() << "\n");
+    BracketList &ParentBList = BlockInfo[ParentBlock].BList;
+    ParentBList.splice(ParentBList.end(), BList);
+    DEBUG(dbgs() << "Parent bracket list is now");
+    DEBUG(debugBracketList(ParentBList));
+    DEBUG(dbgs() << "\n");
+  }
+}
+
+void ControlDependenceEquivalence::visitBackedge(const BasicBlock *From,
+                                                 const BasicBlock *To,
+                                                 DFSDirection Direction) {
+  DEBUG(dbgs() << "visit backedge from block ");
+  DEBUG(From->printAsOperand(dbgs()));
+  DEBUG(dbgs() << " to block ");
+  DEBUG(To->printAsOperand(dbgs()));
+  DEBUG(dbgs() << "\n");
+
+  // Push backedge onto the bracket list [line:25].
+  BlockData &Info = BlockInfo[From];
+  BracketList &BList = Info.BList;
+  auto Place =
+      BList.insert(BList.end(), Bracket{Direction, 0, 0, From, To, false});
+  BlockInfo[To].BracketIterators.push_back(Place);
+}
+
+FunctionPass *llvm::createControlDependenceEquivalencePass() {
+  return new ControlDependenceEquivalence();
+}
+
+namespace {
+
+class ControlDependenceEquivalencePrinter : public FunctionPass {
+  const Function *F;
+
+public:
+  ControlDependenceEquivalencePrinter() : FunctionPass(ID) {
+    initializeControlDependenceEquivalencePrinterPass(
+        *PassRegistry::getPassRegistry());
+  }
+  // run - Calculate control Equivalence for this function
+  bool runOnFunction(Function &F) override;
+
+  // getAnalysisUsage - Implement the Pass API
+  void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.addRequired<ControlDependenceEquivalence>();
+    AU.setPreservesAll();
+  }
+  // releaseMemory - Reset state back to before function was analyzed
+  void releaseMemory() override {
+    F = nullptr;
+    EquivClasses.clear();
+  }
+
+  // print - Show contents in human readable format...
+  void print(raw_ostream &O, const Module * = nullptr) const override;
+
+  static char ID;
+  std::vector<std::vector<const BasicBlock *>> EquivClasses;
+};
+}
+char ControlDependenceEquivalencePrinter::ID = 0;
+
+INITIALIZE_PASS_BEGIN(ControlDependenceEquivalencePrinter, "print-controldep",
+                      "Print Control Dependence of function", true, true)
+INITIALIZE_PASS_DEPENDENCY(ControlDependenceEquivalence)
+INITIALIZE_PASS_END(ControlDependenceEquivalencePrinter, "print-controldep",
+                    "Print Control Dependence of function", true, true)
+
+FunctionPass *llvm::createControlDependenceEquivalencePrinter() {
+  return new ControlDependenceEquivalencePrinter();
+}
+
+void ControlDependenceEquivalencePrinter::print(raw_ostream &OS,
+                                                const Module *) const {
+  OS << "Equivalence classes: (";
+  for (auto &V : EquivClasses) {
+    OS << "{";
+    for (auto &B : V) {
+      if (B->hasName())
+        OS << B->getName();
+      else
+        B->printAsOperand(OS);
+      if (&B != &V.back())
+        OS << ",";
+    }
+    OS << "}";
+    if (&V != &EquivClasses.back())
+      OS << ",";
+  }
+  OS << ")\n";
+}
+
+bool ControlDependenceEquivalencePrinter::runOnFunction(Function &F) {
+  this->F = &F;
+  ControlDependenceEquivalence &CD =
+      getAnalysis<ControlDependenceEquivalence>();
+  // Make a nice map from class number to vectors of bb's
+  std::map<unsigned, std::vector<const BasicBlock *>> ClassSets;
+  for (auto &BB : F) {
+    unsigned ClassNum = CD.getClassNumber(&BB);
+    ClassSets[ClassNum].push_back(&BB);
+  }
+
+  // Sort each vector by bb name, putting named bbs before unnamed ones, then
+  // add it to the equivalence class list
+  for (auto &V : ClassSets) {
+    std::stable_sort(V.second.begin(), V.second.end(),
+                     [](const BasicBlock *A, const BasicBlock *B) {
+                       if (A->hasName() && !B->hasName())
+                         return true;
+                       if (B->hasName() && !A->hasName())
+                         return false;
+                       if (!A->hasName() && !B->hasName())
+                         return false;
+                       return A->getName() < B->getName();
+                     });
+    EquivClasses.push_back(V.second);
+  }
+  // Now stable sort by size and then name
+  std::stable_sort(EquivClasses.begin(), EquivClasses.end(),
+                   [](const std::vector<const BasicBlock *> &A,
+                      const std::vector<const BasicBlock *> &B) {
+                     if (A.size() < B.size())
+                       return true;
+                     if (A.size() > B.size())
+                       return false;
+                     // The same block can't be in multiple equivalence classes,
+                     // so we know that the above sorting means we can just
+                     // compare the first elements
+                     if (A[0]->hasName() && !B[0]->hasName())
+                       return true;
+                     if (B[0]->hasName() && !A[0]->hasName())
+                       return false;
+                     return A[0]->getName() < B[0]->getName();
+                   });
+  return false;
+}

test/Analysis/ControlDependence/testdiamond.ll

+; RUN: opt < %s -print-controldep -analyze | FileCheck %s
+
+target datalayout = "e-i64:64-f80:128-n8:16:32:64-S128"
+define void @testdiamond() {
+start:
+    br i1 true, label %same, label %different
+same:
+    br label %returnit
+different:
+    br label %returnit
+returnit:
+    ret void
+}
+; CHECK: ({different},{same},{returnit,start})
+

test/Analysis/ControlDependence/testembeddeddiamond.ll

+; RUN: opt < %s -print-controldep -analyze | FileCheck %s
+
+target datalayout = "e-i64:64-f80:128-n8:16:32:64-S128"
+define void @testembeddeddiamond() {
+start:
+ br i1 true, label %same, label %different
+same: 
+ br i1 true, label %samepart1, label %samepart2
+samepart1:
+ br label %samemergepoint
+samepart2:
+ br label %samemergepoint
+samemergepoint:
+ br label %returnit
+different:
+ br label %returnit
+returnit:
+    ret void
+}
+; CHECK: ({different},{samepart1},{samepart2},{returnit,start},{same,samemergepoint})

test/Analysis/ControlDependence/testifinloop.ll

+; RUN: opt < %s -print-controldep -analyze | FileCheck %s
+
+target datalayout = "e-i64:64-f80:128-n8:16:32:64-S128"
+define void @testifinloop() {
+start:
+  br label %loop
+loop:
+  br label %loopbody
+loopbody:
+  br label %loopif
+loopif:
+  br i1 true, label %looptrue, label %loopfalse
+looptrue:
+  br label %loopifmerge
+loopfalse:
+  br label %loopifmerge
+loopifmerge:
+  br label %looptest
+looptest:
+  br i1 true, label %loop, label %returnit
+returnit:
+  ret void
+}
+; CHECK: ({loopfalse},{looptrue},{returnit},{start},{loop,loopbody,loopif,loopifmerge,looptest})

test/Analysis/ControlDependence/testloop.ll

+; RUN: opt < %s -print-controldep -analyze | FileCheck %s
+
+target datalayout = "e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @testbasicloop() {
+start:
+  br label %loop
+loop:
+  br label %loopbody
+loopbody:
+  br label %looptest
+looptest:
+  br i1 true, label %loop, label %returnit
+returnit:
+  ret void
+}
+; CHECK: ({returnit},{start},{loop,loopbody,looptest})

test/Analysis/ControlDependence/testnomergebranch.ll

+; RUN: opt < %s -print-controldep -analyze | FileCheck %s
+
+target datalayout = "e-i64:64-f80:128-n8:16:32:64-S128"
+define void @testnomergebranch() {
+start:
+    br i1 true, label %same, label %different
+same:
+    ret void
+different:
+    ret void
+}
+; CHECK: ({different},{same},{start})
+

test/Analysis/ControlDependence/teststraightline.ll

+; RUN: opt < %s -print-controldep -analyze | FileCheck %s
+
+target datalayout = "e-i64:64-f80:128-n8:16:32:64-S128"
+define void @teststraightline() {
+start:
+    br label %next
+next:
+    br label %returnit
+returnit:
+    ret void
+}
+; CHECK: ({next,returnit,start})
+

test/Analysis/ControlDependence/testunreachableinfiniteloop.ll

+; RUN: opt < %s -print-controldep -analyze | FileCheck %s
+target datalayout = "e-i64:64-f80:128-n8:16:32:64-S128"
+
+; Function Attrs: nounwind uwtable
+define hidden void @zot() #0 align 2 {
+bb:
+  br label %bb168
+
+bb168:                                            ; preds = %bb168, %bb
+  br label %bb168
+}
+;CHECK: ({bb},{bb168})