[WebAssembly] Add Relooper

[azakai]

Summary

This is just an initial checkin of an implementation of the Relooper algorithm, in preparation for WebAssembly codegen to utilize. It doesn't do anything yet by itself.

The Relooper algorithm takes an arbitrary control flow graph and generates structured control flow from that, utilizing a helper variable when necessary to handle irreducibility. The WebAssembly backend will be able to use this in order to generate an AST for its binary format.

[jfb]

Could you also add the .cpp file to CMakeLists.txt? The Makefile picks it up automatically...

lib/Target/WebAssembly/Relooper.h

19 ↗

(On Diff #31155)

It's more common to include the C++ version:

#include <cassert>
#include <cstdio>
#include <cstdarg>

27 ↗

(On Diff #31155)

You should put everything in a sub-namespace of the llvm namespace.

41 ↗

(On Diff #31155)

nullptr is the new hotness, here and elsewhere.

60 ↗

(On Diff #31155)

Could you use llvm/ADT/SetVector.h instead?

104 ↗

(On Diff #31155)

Could you use llvm/ADT/SetVector.h instead?

[jfb]

I did a first quick LLVM-style-only pass. I stopped midway, because my comments would be the same, so I'll take another look after a code update.

lib/Target/WebAssembly/Relooper.cpp

25 ↗

(On Diff #31155)

Same here on C++ versions.

51 ↗

(On Diff #31155)

Could you just use a std::string here? Or do the const char * even need to be copied? If they don't then you could use a StringRef.

81 ↗

(On Diff #31155)

Can you instead use a std::unique_ptr in the container?

95 ↗

(On Diff #31155)

Same here on std::unique_ptr in the container for the above two.

141 ↗

(On Diff #31155)

With LLVM's containers you should be able to use range-based for loops here and in other places below.

143 ↗

(On Diff #31155)

std::string or StringRef won't require O(n) strlen :-)

147 ↗

(On Diff #31155)

Remove or uncomment. Same in a few other places below.

156 ↗

(On Diff #31155)

Could you make this a command-line option instead, so it can be tuned? See http://llvm.org/docs/CommandLine.html

lib/Target/WebAssembly/Relooper.h

197 ↗

(On Diff #31155)

Would this be a better fit:
http://llvm.org/docs/HowToSetUpLLVMStyleRTTI.html
?

275 ↗

(On Diff #31155)

Instead use the DEBUG macro and LLVM's DEBUG_TYPE:
http://llvm.org/docs/ProgrammersManual.html#the-debug-macro-and-debug-option

[jroelofs]

Would be good to clang-format this before it goes in... I see a lot of places where '{}'s are used when there's a single statement in the body of the if/for.

lib/Target/WebAssembly/Relooper.cpp

467 ↗

(On Diff #31155)

I suspect ToInvalidate should be a SmallPtrSet, not a std::list.

[jroelofs]

lib/Target/WebAssembly/Relooper.cpp

117 ↗

(On Diff #31155)

I suspect ToInvestigate should be a SmallPtrSet, not a std::list.

371 ↗

(On Diff #31155)

I suspect ToInvalidate should be a SmallPtrSet, not a std::list.

413 ↗

(On Diff #31155)

I suspect Queue should be a SmallPtrSet, not a std::list.

755 ↗

(On Diff #31155)

ewww... macros. Mind turning these into functions? In the case of SHAPE_SWITCH, that would mean passing it lambdas for simple, multiple and loop.

798 ↗

(On Diff #31155)

looks like this comment got formatted poorly.

823 ↗

(On Diff #31155)

looks like this block of comment got formatted poorly.

923 ↗

(On Diff #31155)

If the object it self has ownership of this stack instead of just the outermost call of this function, then the memory management would be much simpler.

[azakai]

Thanks for the feedback!

About clang-format, I did run it, but I didn't do so with -style=LLVM, I think that's why it didn't fix all the things you expected it to. However, it doesn't look like clang-format fixes '{}'s when there's a single statement in the body of the if/for, so I have to do that manually.

I'll upload an updated diff.

lib/Target/WebAssembly/Relooper.cpp

51 ↗

(On Diff #31155)

This is actually code that will definitely be changed - we don't want a string of code, but instead some pointer to an LLVM structure. But I thought that removing it at this early time would make it harder to continue to work on this code. In other words, I left it here in order to make it clear what is to be replaced with proper LLVM content, when we get to that point.

81 ↗

(On Diff #31155)

The unique pointer will be destroyed before we want the object to be destroyed, however (the object lives before and after it is used in this object).

The lifetime of all those is kept by the Relooper instance, when it is released, it frees everything inside it.

117 ↗

(On Diff #31155)

I basically need a fifo list here, where I constantly take the first from the front and add to the back. Looking at SmallPtrSet, it seems unsuitable. Am I missing something?

755 ↗

(On Diff #31155)

I worry about performance, since we do traverse the AST in optimization passes quite a bit.

Is there a guarantee that the LLVM optimizer would get rid of the lambda overhead here, if this were written that way?

[azakai]

This should address all the review comments, except for few ones I replied to with further questions or comments.

[arsenm]

lib/Target/WebAssembly/CMakeLists.txt

12 ↗

(On Diff #31182)

Would it be possible to move this into lib/Transforms/Scalar and set up as a target independent pass? I would be interested in evaluating this as an alternative to StructurizeCFG

[arsenm]

lib/Target/WebAssembly/CMakeLists.txt

12 ↗

(On Diff #31182)

This would also have the added advantage of being able to write IR->IR tests

[arsenm]

Will this be eventually structuring the IR or on MachineBasicBlocks?

lib/Target/WebAssembly/Relooper.cpp

525 ↗

(On Diff #31182)

.empti() would be preferrable

[jfb]

lib/Target/WebAssembly/Relooper.cpp

52 ↗

(On Diff #31182)

You mean in this patch, or a later one? It would be good to have a FIXME here.

I'm mostly asking because ew strdup and free :-)

82 ↗

(On Diff #31182)

Hmm, so the lifetime starts in BranchesOut below, but ends elsewhere (ToInvestigate?) while BranchesOut doesn't live for as long?

It's just unusual / undesirable to have manual memory management for algorithms like this. I get confused. Could it maybe instead use a BumpPtrAllocator, which allows you to move the objects around but bounds the lifetime properly? Or do you actually need to delete things during relooping otherwise it would consume too much memory?

I'm asking without understanding the algorithm yet (or rather, I haven't read the code in a while). So I've got my style hat on, feel free to shoo it off if it looks silly.

118 ↗

(On Diff #31182)

If it usually stay small then LLVM's Small* datastructures can just fit on the stack, and grow to the heap if needed. Nicer than std::list because of this. SmallVector can be a good fifo, but it's only suited to small things than don't usually grow bigger than your stack allocated quantity.

[jfb]

lib/Target/WebAssembly/Relooper.cpp

1 ↗

(On Diff #31182)

.cpp

31 ↗

(On Diff #31182)

You should put llvm/ before system #includes:
http://llvm.org/docs/CodingStandards.html#include-style
Same for Relooper.h.

74 ↗

(On Diff #31182)

In many cases you'll want to use for (const auto && or for (const auto &. In this case it's just copying a std::pair of pointers so it's not that bad, but in general you can get some pretty unexpected results with just auto.

95 ↗

(On Diff #31182)

LLVM style capitalizes the I. I know...
But this could be a range-based for loop anyways :-)
Or even better, some std::unique_ptr.

329 ↗

(On Diff #31182)

New is OK.

331 ↗

(On Diff #31182)

You should probably move some of these comments tot he line above, since it looks cramped with 80-column.

482 ↗

(On Diff #31182)

Should this also be configurable?

654 ↗

(On Diff #31182)

switch (var->getKind()) with default: llvm_unreachable(...); ?

756 ↗

(On Diff #31182)

No guarantees, but we're within yelling distance of optimizer people who can fix LLVM's performance :)

[jroelofs]

lib/Target/WebAssembly/Relooper.cpp

118 ↗

(On Diff #31182)

Oh, sorry, I missed that it needed to be a fifo, and not just a bag of things to work on.

138 ↗

(On Diff #31182)

weirdly formatted comment block.

215 ↗

(On Diff #31182)

weirdly formatted comment block.

363 ↗

(On Diff #31182)

weirdly formatted comment block.

406 ↗

(On Diff #31182)

weirdly formatted comment block.

493 ↗

(On Diff #31182)

weirdly formatted comment block.

536 ↗

(On Diff #31182)

weirdly formatted comment block.

572 ↗

(On Diff #31182)

weirdly formatted comment block.

641 ↗

(On Diff #31182)

thanks!

[azakai]

lib/Target/WebAssembly/Relooper.cpp

52 ↗

(On Diff #31182)

Adding FIXMEs.

I think in a later patch makes sense - we still don't have a final plan for how to do it, and also it might end up being someone other than me that writes it.

82 ↗

(On Diff #31182)

Every branch starts out in BranchesOut. Then the algorithm step by step creates the AST, and while doing so, moves them one at a time to ProcessedBranchesOut. This is nice since we often need to iterate over the not-yet-processed ones (so marking them with a flag and ignoring them would be less pleasant).

In theory a shared_ptr could be used in both of those (and in BranchesIn/ProcessedBranchesIn) but the overhead seems pointless to me.

756 ↗

(On Diff #31182)

Could we leave this for future investigation, then? In my experience with lambdas, the overhead is non-trivial (although I do love them for the code clarity, it's just that here, perf is quite important).

[sunfish]

lib/Target/WebAssembly/CMakeLists.txt

12 ↗

(On Diff #31182)

In reply to these two comments, and "Will this be eventually structuring the IR or on MachineBasicBlocks?",

This pass is closer in function to AMDILCFGStructurizer in the AMDGPU backend, and is meant to be run in a very late codegen pass after most everything else is done. At the same time, WebAssembly's control structures are more expressive than AMDGPU's, and this motivates different algorithms.

Also, there are people working to support serialization of MachineFunctions, which will enable the development of fine-grained unit tests.

We're open to generalizing this code so that other backends can share it. At the same time, the big picture here is that that we're adapting some pre-existing code that we developed for other purposes here, and instead of doing all the work out-of-tree and checking it in as a completed artifact, we're doing much of the work in-tree. The code you see here will likely change significantly before we're really ready to think about this.

[azakai]

Thanks again for the comments. This addresses all the latest batch, except for the ones being discussed in inline comments.

[arsenm]

lib/Target/WebAssembly/CMakeLists.txt

12 ↗

(On Diff #31248)

Will this pass purely be doing the structurizing, or will it also be responsible for insertion of the higher level control flow instructions? I think one of the many failings of AMDILCFGStructurizer is that it attempts to do both at the same time / in the same pass.

[jfb]

lib/Target/WebAssembly/CMakeLists.txt

12 ↗

(On Diff #31248)

It identifies the structure, but acts like an AnalysisPass in that it just passes that info onto later code.

lib/Target/WebAssembly/Relooper.cpp

83 ↗

(On Diff #31248)

Yeah I'd like to avoid shared_ptr overheads.

It does seem like either unique_ptr or a BumpPtrAllocator would work though.

757 ↗

(On Diff #31248)

Fine with me, with a FIXME explaining that.

[jfb]

lib/Target/WebAssembly/Relooper.cpp

656 ↗

(On Diff #31248)

break; here and below.

525 ↗

(On Diff #31182)

Agreed on using .empty() instead of .size() == 0 in a few places.

[sunfish]

lib/Target/WebAssembly/CMakeLists.txt

12 ↗

(On Diff #31248)

The current Relooper algorithm works on arbitrary CFGs, so it doesn't need to do any structurizing.

[azakai]

lib/Target/WebAssembly/Relooper.cpp

83 ↗

(On Diff #31248)

unique_ptr can't work for BranchesIn because the blocks are used in more places, the branches also refer to blocks, for example.

[Processed]BranchesOut could use a unique_ptr+swapping, but it would seem a little inconsistent to me to use it only there. What do you think?

The relooper has a list of blocks. That could be a bump allocator in theory, but the API lets people create blocks and then takes ownership of them. These could alternatively be a unique_ptr, but other things will need to point to those same blocks (branches), so all those would be forced to be simple dumb pointers, and the mix of those seems ugly to me personally. But if you prefer it I can do it.

656 ↗

(On Diff #31248)

yikes! thanks!

[azakai]

Latest updates (.empty(), breaks, a TODO on perf)

[jfb]

lib/Target/WebAssembly/Relooper.cpp

84 ↗

(On Diff #31258)

unique_ptr can't work for BranchesIn because the blocks are used in more places, the branches also refer to blocks, for example.

Is there one datastructure that always owns the blocks, and others that have references to them (that don't outlive the owner)? For that you could own with unique_ptr, and have non-owning pointers in the other datastructures.

I just find it hard / unusual to track lifetime manually, but I don't want to pay the cost of shared_ptr. :-)

133 ↗

(On Diff #31258)

!.empty()

158 ↗

(On Diff #31258)

!.empty()

279 ↗

(On Diff #31258)

!.empty()

291 ↗

(On Diff #31258)

!.empty()

340 ↗

(On Diff #31258)

!.empty()

381 ↗

(On Diff #31258)

!.empty()

432 ↗

(On Diff #31258)

!.empty()

511 ↗

(On Diff #31258)

.empty()

542 ↗

(On Diff #31258)

!.empty()

579 ↗

(On Diff #31258)

This and two lines down should probably be size_t (auto would get the right ::size_type).

612 ↗

(On Diff #31258)

!.empty()

725 ↗

(On Diff #31258)

Another customization point?

840 ↗

(On Diff #31258)

!.empty()

[azakai]

More .empty() usage, unique_ptr for block branches, add nesting limit customization.

[jfb]

lib/Target/WebAssembly/Relooper.cpp

98 ↗

(On Diff #31272)

STLExtras.h has the sorely-missing make_unique for this. Same in a few places below.

lib/Target/WebAssembly/Relooper.h

28 ↗

(On Diff #31272)

Sort includes alphabetically.

[azakai]

Use make_unique, fix include ordering.

[azakai]

Fixed the last two comments.

[jfb]

I think this looks pretty good (besides the few other comments). @sunfish and I intend to iterate on this code (he had ideas on how to generate better ASTs), and:

• Add extensive testing using WebAssembly's textual format.
• Tune the code (so I'd ignore std::deque versus std::list discussions for now).
• Make sure to clarify object ownership where possible, instead of using explicit memory management.

I'd still leave the patch open until next week to make sure anyone who wants to comment has a change to. Otherwise, I look forward to having control flow :-)

lib/Target/WebAssembly/Relooper.cpp

758 ↗

(On Diff #31284)

I discussed this with a few LLVM folks, and they'd rather start off with lambdas instead. We'll make sure to measure perf and ensure inlining isn't an issue.

lib/Target/WebAssembly/Relooper.h

116 ↗

(On Diff #31284)

It would be nice to move this to the Shape class, and use doxygen-style comments (same for other classes).

140 ↗

(On Diff #31284)

Could you make this one pure virtual, and implement an override dtor in derived classes?

[azakai]

Now with pure c++11 lambda goodness. Also addresses the other latest comments.

[jfb]

lgtm, with the intent of polishing, testing and performance-tuning the code as we start using it for the WebAssembly backend. We know this code works and does what it's intended to do in the context of Emscripten, so it makes sense to start from there and evolve the code incrementally in-tree for LLVM's/WebAssembly's purpose.

I'll leave this open for now if others want to comment, and I'll commit if it's uncontended.

Thanks!

[hughperkins]

Hi, I have a project to rewrite llvm code as OpenCL https://github.com/hughperkins/cuda-on-cl It currently outputs lots of conditional branches, is labels and gotos, in the output .I want to 'reloop' this into fors/whiles/ etc. To what extent can I use the code in this PR to achieve this? What are the preferred option(s) for me to use this code from my own code? (eg drop the sourcecod into my repo? build as a shared object somehow? some other approach?)

Hugh

[kripken]

In D11691#587616, @hughperkins wrote:

Hi, I have a project to rewrite llvm code as OpenCL https://github.com/hughperkins/cuda-on-cl It currently outputs lots of conditional branches, is labels and gotos, in the output .I want to 'reloop' this into fors/whiles/ etc. To what extent can I use the code in this PR to achieve this? What are the preferred option(s) for me to use this code from my own code? (eg drop the sourcecod into my repo? build as a shared object somehow? some other approach?)

The best option is probably to take the Relooper implementation from Binaryen,

https://github.com/WebAssembly/binaryen/tree/master/src/cfg

In LLVM this PR landed but I'm not sure how much it was used or tested, and it seems to have been removed at some point. In Binaryen the Relooper is in active use, heavily tested and fuzzed, and also has a bunch of optimizations and improvements since the LLVM version.

I would just grab the Relooper.h and Relooper.cpp files from Binaryen and use those (might have some minor dependencies on headers that you can grab too). Happy to help with any questions you have in that process.

[hughperkins]

Awesome, thanks! Will take a look.

llvm/trunk/lib/Target/WebAssembly/CMakeLists.txt

 set(LLVM_TARGET_DEFINITIONS WebAssembly.td)
 
 tablegen(LLVM WebAssemblyGenAsmWriter.inc -gen-asm-writer)
 tablegen(LLVM WebAssemblyGenDAGISel.inc -gen-dag-isel)
 tablegen(LLVM WebAssemblyGenInstrInfo.inc -gen-instr-info)
 tablegen(LLVM WebAssemblyGenMCCodeEmitter.inc -gen-emitter)
 tablegen(LLVM WebAssemblyGenRegisterInfo.inc -gen-register-info)
 tablegen(LLVM WebAssemblyGenSubtargetInfo.inc -gen-subtarget)
 add_public_tablegen_target(WebAssemblyCommonTableGen)
 
 add_llvm_target(WebAssemblyCodeGen
+  Relooper.cpp
   WebAssemblyAsmPrinter.cpp
   WebAssemblyFrameLowering.cpp
   WebAssemblyISelDAGToDAG.cpp
   WebAssemblyISelLowering.cpp
   WebAssemblyInstrInfo.cpp
   WebAssemblyMachineFunctionInfo.cpp
   WebAssemblyRegisterInfo.cpp
   WebAssemblySelectionDAGInfo.cpp

llvm/trunk/lib/Target/WebAssembly/Relooper.h

+//===-- Relooper.h - Top-level interface for WebAssembly  ----*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===-------------------------------------------------------------------===//
+///
+/// \file
+/// \brief This defines an optimized C++ implemention of the Relooper
+/// algorithm, originally developed as part of Emscripten, which
+/// generates a structured AST from arbitrary control flow.
+///
+//===-------------------------------------------------------------------===//
+
+#include <llvm/ADT/MapVector.h>
+#include <llvm/ADT/SetVector.h>
+#include <llvm/Support/Casting.h>
+
+#include <cassert>
+#include <cstdio>
+#include <cstdarg>
+#include <deque>
+#include <list>
+#include <map>
+#include <memory>
+#include <set>
+
+namespace llvm {
+
+namespace Relooper {
+
+struct Block;
+struct Shape;
+
+///
+/// Info about a branching from one block to another
+///
+struct Branch {
+  enum FlowType {
+    Direct = 0, // We will directly reach the right location through other
+                // means, no need for continue or break
+    Break = 1,
+    Continue = 2,
+    Nested = 3 // This code is directly reached, but we must be careful to
+               // ensure it is nested in an if - it is not reached
+    // unconditionally, other code paths exist alongside it that we need to make
+    // sure do not intertwine
+  };
+  Shape
+      *Ancestor; // If not nullptr, this shape is the relevant one for purposes
+                 // of getting to the target block. We break or continue on it
+  Branch::FlowType
+      Type;     // If Ancestor is not nullptr, this says whether to break or
+                // continue
+  bool Labeled; // If a break or continue, whether we need to use a label
+  const char *Condition; // The condition for which we branch. For example,
+                         // "my_var == 1". Conditions are checked one by one.
+                         // One of the conditions should have nullptr as the
+                         // condition, in which case it is the default
+                         // FIXME: move from char* to LLVM data structures
+  const char *Code; // If provided, code that is run right before the branch is
+                    // taken. This is useful for phis
+                    // FIXME: move from char* to LLVM data structures
+
+  Branch(const char *ConditionInit, const char *CodeInit = nullptr);
+  ~Branch();
+};
+
+typedef SetVector<Block *> BlockSet;
+typedef MapVector<Block *, Branch *> BlockBranchMap;
+typedef MapVector<Block *, std::unique_ptr<Branch>> OwningBlockBranchMap;
+
+///
+/// Represents a basic block of code - some instructions that end with a
+/// control flow modifier (a branch, return or throw).
+///
+struct Block {
+  // Branches become processed after we finish the shape relevant to them. For
+  // example, when we recreate a loop, branches to the loop start become
+  // continues and are now processed. When we calculate what shape to generate
+  // from a set of blocks, we ignore processed branches. Blocks own the Branch
+  // objects they use, and destroy them when done.
+  OwningBlockBranchMap BranchesOut;
+  BlockSet BranchesIn;
+  OwningBlockBranchMap ProcessedBranchesOut;
+  BlockSet ProcessedBranchesIn;
+  Shape *Parent; // The shape we are directly inside
+  int Id; // A unique identifier, defined when added to relooper. Note that this
+          // uniquely identifies a *logical* block - if we split it, the two
+          // instances have the same content *and* the same Id
+  const char *Code;      // The string representation of the code in this block.
+                         // Owning pointer (we copy the input)
+                         // FIXME: move from char* to LLVM data structures
+  const char *BranchVar; // A variable whose value determines where we go; if
+                         // this is not nullptr, emit a switch on that variable
+                         // FIXME: move from char* to LLVM data structures
+  bool IsCheckedMultipleEntry; // If true, we are a multiple entry, so reaching
+                               // us requires setting the label variable
+
+  Block(const char *CodeInit, const char *BranchVarInit);
+  ~Block();
+
+  void AddBranchTo(Block *Target, const char *Condition,
+                   const char *Code = nullptr);
+};
+
+///
+/// Represents a structured control flow shape
+///
+struct Shape {
+  int Id; // A unique identifier. Used to identify loops, labels are Lx where x
+          // is the Id. Defined when added to relooper
+  Shape *Next;    // The shape that will appear in the code right after this one
+  Shape *Natural; // The shape that control flow gets to naturally (if there is
+                  // Next, then this is Next)
+
+  /// Discriminator for LLVM-style RTTI (dyn_cast<> et al.)
+  enum ShapeKind { SK_Simple, SK_Multiple, SK_Loop };
+
+private:
+  ShapeKind Kind;
+
+public:
+  ShapeKind getKind() const { return Kind; }
+
+  Shape(ShapeKind KindInit) : Id(-1), Next(nullptr), Kind(KindInit) {}
+};
+
+///
+/// Simple: No control flow at all, just instructions.
+///
+struct SimpleShape : public Shape {
+  Block *Inner;
+
+  SimpleShape() : Shape(SK_Simple), Inner(nullptr) {}
+
+  static bool classof(const Shape *S) { return S->getKind() == SK_Simple; }
+};
+
+///
+/// A shape that may be implemented with a labeled loop.
+///
+struct LabeledShape : public Shape {
+  bool Labeled; // If we have a loop, whether it needs to be labeled
+
+  LabeledShape(ShapeKind KindInit) : Shape(KindInit), Labeled(false) {}
+};
+
+// Blocks with the same id were split and are identical, so we just care about
+// ids in Multiple entries
+typedef std::map<int, Shape *> IdShapeMap;
+
+///
+/// Multiple: A shape with more than one entry. If the next block to
+///           be entered is among them, we run it and continue to
+///           the next shape, otherwise we continue immediately to the
+///           next shape.
+///
+struct MultipleShape : public LabeledShape {
+  IdShapeMap InnerMap; // entry block ID -> shape
+  int Breaks; // If we have branches on us, we need a loop (or a switch). This
+              // is a counter of requirements,
+              // if we optimize it to 0, the loop is unneeded
+  bool UseSwitch; // Whether to switch on label as opposed to an if-else chain
+
+  MultipleShape() : LabeledShape(SK_Multiple), Breaks(0), UseSwitch(false) {}
+
+  static bool classof(const Shape *S) { return S->getKind() == SK_Multiple; }
+};
+
+///
+/// Loop: An infinite loop.
+///
+struct LoopShape : public LabeledShape {
+  Shape *Inner;
+
+  LoopShape() : LabeledShape(SK_Loop), Inner(nullptr) {}
+
+  static bool classof(const Shape *S) { return S->getKind() == SK_Loop; }
+};
+
+///
+/// Implements the relooper algorithm for a function's blocks.
+///
+/// Implementation details: The Relooper instance has
+/// ownership of the blocks and shapes, and frees them when done.
+///
+struct Relooper {
+  std::deque<Block *> Blocks;
+  std::deque<Shape *> Shapes;
+  Shape *Root;
+  bool MinSize;
+  int BlockIdCounter;
+  int ShapeIdCounter;
+
+  Relooper();
+  ~Relooper();
+
+  void AddBlock(Block *New, int Id = -1);
+
+  // Calculates the shapes
+  void Calculate(Block *Entry);
+
+  // Sets us to try to minimize size
+  void SetMinSize(bool MinSize_) { MinSize = MinSize_; }
+};
+
+typedef MapVector<Block *, BlockSet> BlockBlockSetMap;
+
+} // namespace Relooper
+
+} // namespace llvm

llvm/trunk/lib/Target/WebAssembly/Relooper.cpp

+//===-- Relooper.cpp - Top-level interface for WebAssembly  ----*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===---------------------------------------------------------------------===//
+///
+/// \file
+/// \brief This implements the Relooper algorithm. This implementation includes
+/// optimizations added since the original academic paper [1] was published.
+///
+/// [1] Alon Zakai. 2011. Emscripten: an LLVM-to-JavaScript compiler. In
+/// Proceedings of the ACM international conference companion on Object
+/// oriented programming systems languages and applications companion
+/// (SPLASH '11). ACM, New York, NY, USA, 301-312. DOI=10.1145/2048147.2048224
+/// http://doi.acm.org/10.1145/2048147.2048224
+///
+//===-------------------------------------------------------------------===//
+
+#include "Relooper.h"
+
+#include <llvm/ADT/STLExtras.h>
+#include <llvm/Support/raw_ostream.h>
+#include <llvm/Support/CommandLine.h>
+
+#include <cstring>
+#include <cstdlib>
+#include <functional>
+#include <list>
+#include <stack>
+#include <string>
+
+using namespace llvm;
+
+static cl::opt<int> RelooperSplittingFactor(
+    "relooper-splitting-factor",
+    cl::desc(
+        "How much to discount code size when deciding whether to split a node"),
+    cl::init(5));
+
+static cl::opt<unsigned> RelooperMultipleSwitchThreshold(
+    "relooper-multiple-switch-threshold",
+    cl::desc(
+        "How many entries to allow in a multiple before we use a switch"),
+    cl::init(10));
+
+static cl::opt<unsigned> RelooperNestingLimit(
+    "relooper-nesting-limit",
+    cl::desc(
+        "How much nesting is acceptable"),
+    cl::init(20));
+
+namespace llvm {
+
+namespace Relooper {
+
+template <class T, class U>
+static bool contains(const T &container, const U &contained) {
+  return container.count(contained);
+}
+
+// Branch
+
+Branch::Branch(const char *ConditionInit, const char *CodeInit)
+    : Ancestor(nullptr), Labeled(true) {
+  // FIXME: move from char* to LLVM data structures
+  Condition = ConditionInit ? strdup(ConditionInit) : nullptr;
+  Code = CodeInit ? strdup(CodeInit) : nullptr;
+}
+
+Branch::~Branch() {
+  // FIXME: move from char* to LLVM data structures
+  free(static_cast<void *>(const_cast<char *>(Condition)));
+  free(static_cast<void *>(const_cast<char *>(Code)));
+}
+
+// Block
+
+Block::Block(const char *CodeInit, const char *BranchVarInit)
+    : Parent(nullptr), Id(-1), IsCheckedMultipleEntry(false) {
+  // FIXME: move from char* to LLVM data structures
+  Code = strdup(CodeInit);
+  BranchVar = BranchVarInit ? strdup(BranchVarInit) : nullptr;
+}
+
+Block::~Block() {
+  // FIXME: move from char* to LLVM data structures
+  free(static_cast<void *>(const_cast<char *>(Code)));
+  free(static_cast<void *>(const_cast<char *>(BranchVar)));
+}
+
+void Block::AddBranchTo(Block *Target, const char *Condition,
+                        const char *Code) {
+  assert(
+      !contains(BranchesOut,
+                Target)); // cannot add more than one branch to the same target
+  BranchesOut[Target] = make_unique<Branch>(Condition, Code);
+}
+
+// Relooper
+
+Relooper::Relooper()
+    : Root(nullptr), MinSize(false), BlockIdCounter(1),
+      ShapeIdCounter(0) { // block ID 0 is reserved for clearings
+}
+
+Relooper::~Relooper() {
+  for (auto Curr : Blocks)
+    delete Curr;
+  for (auto Curr : Shapes)
+    delete Curr;
+}
+
+void Relooper::AddBlock(Block *New, int Id) {
+  New->Id = Id == -1 ? BlockIdCounter++ : Id;
+  Blocks.push_back(New);
+}
+
+struct RelooperRecursor {
+  Relooper *Parent;
+  RelooperRecursor(Relooper *ParentInit) : Parent(ParentInit) {}
+};
+
+typedef std::list<Block *> BlockList;
+
+void Relooper::Calculate(Block *Entry) {
+  // Scan and optimize the input
+  struct PreOptimizer : public RelooperRecursor {
+    PreOptimizer(Relooper *Parent) : RelooperRecursor(Parent) {}
+    BlockSet Live;
+
+    void FindLive(Block *Root) {
+      BlockList ToInvestigate;
+      ToInvestigate.push_back(Root);
+      while (!ToInvestigate.empty()) {
+        Block *Curr = ToInvestigate.front();
+        ToInvestigate.pop_front();
+        if (contains(Live, Curr))
+          continue;
+        Live.insert(Curr);
+        for (const auto &iter : Curr->BranchesOut)
+          ToInvestigate.push_back(iter.first);
+      }
+    }
+
+    // If a block has multiple entries but no exits, and it is small enough, it
+    // is useful to split it. A common example is a C++ function where
+    // everything ends up at a final exit block and does some RAII cleanup.
+    // Without splitting, we will be forced to introduce labelled loops to
+    // allow reaching the final block
+    void SplitDeadEnds() {
+      unsigned TotalCodeSize = 0;
+      for (const auto &Curr : Live) {
+        TotalCodeSize += strlen(Curr->Code);
+      }
+      BlockSet Splits;
+      BlockSet Removed;
+      for (const auto &Original : Live) {
+        if (Original->BranchesIn.size() <= 1 ||
+            !Original->BranchesOut.empty())
+          continue; // only dead ends, for now
+        if (contains(Original->BranchesOut, Original))
+          continue; // cannot split a looping node
+        if (strlen(Original->Code) * (Original->BranchesIn.size() - 1) >
+            TotalCodeSize / RelooperSplittingFactor)
+          continue; // if splitting increases raw code size by a significant
+                    // amount, abort
+        // Split the node (for simplicity, we replace all the blocks, even
+        // though we could have reused the original)
+        for (const auto &Prior : Original->BranchesIn) {
+          Block *Split = new Block(Original->Code, Original->BranchVar);
+          Parent->AddBlock(Split, Original->Id);
+          Split->BranchesIn.insert(Prior);
+          std::unique_ptr<Branch> Details;
+          Details.swap(Prior->BranchesOut[Original]);
+          Prior->BranchesOut[Split] = make_unique<Branch>(Details->Condition,
+                                                          Details->Code);
+          for (const auto &iter : Original->BranchesOut) {
+            Block *Post = iter.first;
+            Branch *Details = iter.second.get();
+            Split->BranchesOut[Post] = make_unique<Branch>(Details->Condition,
+                                                           Details->Code);
+            Post->BranchesIn.insert(Split);
+          }
+          Splits.insert(Split);
+          Removed.insert(Original);
+        }
+        for (const auto &iter : Original->BranchesOut) {
+          Block *Post = iter.first;
+          Post->BranchesIn.remove(Original);
+        }
+      }
+      for (const auto &iter : Splits)
+        Live.insert(iter);
+      for (const auto &iter : Removed)
+        Live.remove(iter);
+    }
+  };
+  PreOptimizer Pre(this);
+  Pre.FindLive(Entry);
+
+  // Add incoming branches from live blocks, ignoring dead code
+  for (unsigned i = 0; i < Blocks.size(); i++) {
+    Block *Curr = Blocks[i];
+    if (!contains(Pre.Live, Curr))
+      continue;
+    for (const auto &iter : Curr->BranchesOut)
+      iter.first->BranchesIn.insert(Curr);
+  }
+
+  if (!MinSize)
+    Pre.SplitDeadEnds();
+
+  // Recursively process the graph
+
+  struct Analyzer : public RelooperRecursor {
+    Analyzer(Relooper *Parent) : RelooperRecursor(Parent) {}
+
+    // Add a shape to the list of shapes in this Relooper calculation
+    void Notice(Shape *New) {
+      New->Id = Parent->ShapeIdCounter++;
+      Parent->Shapes.push_back(New);
+    }
+
+    // Create a list of entries from a block. If LimitTo is provided, only
+    // results in that set will appear
+    void GetBlocksOut(Block *Source, BlockSet &Entries,
+                      BlockSet *LimitTo = nullptr) {
+      for (const auto &iter : Source->BranchesOut)
+        if (!LimitTo || contains(*LimitTo, iter.first))
+          Entries.insert(iter.first);
+    }
+
+    // Converts/processes all branchings to a specific target
+    void Solipsize(Block *Target, Branch::FlowType Type, Shape *Ancestor,
+                   BlockSet &From) {
+      for (auto iter = Target->BranchesIn.begin();
+           iter != Target->BranchesIn.end();) {
+        Block *Prior = *iter;
+        if (!contains(From, Prior)) {
+          iter++;
+          continue;
+        }
+        std::unique_ptr<Branch> PriorOut;
+        PriorOut.swap(Prior->BranchesOut[Target]);
+        PriorOut->Ancestor = Ancestor;
+        PriorOut->Type = Type;
+        if (MultipleShape *Multiple = dyn_cast<MultipleShape>(Ancestor))
+          Multiple->Breaks++; // We are breaking out of this Multiple, so need a
+                              // loop
+        iter++; // carefully increment iter before erasing
+        Target->BranchesIn.remove(Prior);
+        Target->ProcessedBranchesIn.insert(Prior);
+        Prior->ProcessedBranchesOut[Target].swap(PriorOut);
+      }
+    }
+
+    Shape *MakeSimple(BlockSet &Blocks, Block *Inner, BlockSet &NextEntries) {
+      SimpleShape *Simple = new SimpleShape;
+      Notice(Simple);
+      Simple->Inner = Inner;
+      Inner->Parent = Simple;
+      if (Blocks.size() > 1) {
+        Blocks.remove(Inner);
+        GetBlocksOut(Inner, NextEntries, &Blocks);
+        BlockSet JustInner;
+        JustInner.insert(Inner);
+        for (const auto &iter : NextEntries)
+          Solipsize(iter, Branch::Direct, Simple, JustInner);
+      }
+      return Simple;
+    }
+
+    Shape *MakeLoop(BlockSet &Blocks, BlockSet &Entries,
+                    BlockSet &NextEntries) {
+      // Find the inner blocks in this loop. Proceed backwards from the entries
+      // until
+      // you reach a seen block, collecting as you go.
+      BlockSet InnerBlocks;
+      BlockSet Queue = Entries;
+      while (!Queue.empty()) {
+        Block *Curr = *(Queue.begin());
+        Queue.remove(*Queue.begin());
+        if (!contains(InnerBlocks, Curr)) {
+          // This element is new, mark it as inner and remove from outer
+          InnerBlocks.insert(Curr);
+          Blocks.remove(Curr);
+          // Add the elements prior to it
+          for (const auto &iter : Curr->BranchesIn)
+            Queue.insert(iter);
+        }
+      }
+      assert(!InnerBlocks.empty());
+
+      for (const auto &Curr : InnerBlocks) {
+        for (const auto &iter : Curr->BranchesOut) {
+          Block *Possible = iter.first;
+          if (!contains(InnerBlocks, Possible))
+            NextEntries.insert(Possible);
+        }
+      }
+
+      LoopShape *Loop = new LoopShape();
+      Notice(Loop);
+
+      // Solipsize the loop, replacing with break/continue and marking branches
+      // as Processed (will not affect later calculations)
+      // A. Branches to the loop entries become a continue to this shape
+      for (const auto &iter : Entries)
+        Solipsize(iter, Branch::Continue, Loop, InnerBlocks);
+      // B. Branches to outside the loop (a next entry) become breaks on this
+      // shape
+      for (const auto &iter : NextEntries)
+        Solipsize(iter, Branch::Break, Loop, InnerBlocks);
+      // Finish up
+      Shape *Inner = Process(InnerBlocks, Entries, nullptr);
+      Loop->Inner = Inner;
+      return Loop;
+    }
+
+    // For each entry, find the independent group reachable by it. The
+    // independent group is the entry itself, plus all the blocks it can
+    // reach that cannot be directly reached by another entry. Note that we
+    // ignore directly reaching the entry itself by another entry.
+    //   @param Ignore - previous blocks that are irrelevant
+    void FindIndependentGroups(BlockSet &Entries,
+                               BlockBlockSetMap &IndependentGroups,
+                               BlockSet *Ignore = nullptr) {
+      typedef std::map<Block *, Block *> BlockBlockMap;
+
+      struct HelperClass {
+        BlockBlockSetMap &IndependentGroups;
+        BlockBlockMap Ownership; // For each block, which entry it belongs to.
+                                 // We have reached it from there.
+
+        HelperClass(BlockBlockSetMap &IndependentGroupsInit)
+            : IndependentGroups(IndependentGroupsInit) {}
+        void InvalidateWithChildren(Block *New) {
+          // Being in the list means you need to be invalidated
+          BlockList ToInvalidate;
+          ToInvalidate.push_back(New);
+          while (!ToInvalidate.empty()) {
+            Block *Invalidatee = ToInvalidate.front();
+            ToInvalidate.pop_front();
+            Block *Owner = Ownership[Invalidatee];
+            // Owner may have been invalidated, do not add to
+            // IndependentGroups!
+            if (contains(IndependentGroups, Owner))
+              IndependentGroups[Owner].remove(Invalidatee);
+            if (Ownership[Invalidatee]) { // may have been seen before and
+                                          // invalidated already
+              Ownership[Invalidatee] = nullptr;
+              for (const auto &iter : Invalidatee->BranchesOut) {
+                Block *Target = iter.first;
+                BlockBlockMap::iterator Known = Ownership.find(Target);
+                if (Known != Ownership.end()) {
+                  Block *TargetOwner = Known->second;
+                  if (TargetOwner)
+                    ToInvalidate.push_back(Target);
+                }
+              }
+            }
+          }
+        }
+      };
+      HelperClass Helper(IndependentGroups);
+
+      // We flow out from each of the entries, simultaneously.
+      // When we reach a new block, we add it as belonging to the one we got to
+      // it from.
+      // If we reach a new block that is already marked as belonging to someone,
+      // it is reachable by two entries and is not valid for any of them.
+      // Remove it and all it can reach that have been visited.
+
+      // Being in the queue means we just added this item, and
+      // we need to add its children
+      BlockList Queue;
+      for (const auto &Entry : Entries) {
+        Helper.Ownership[Entry] = Entry;
+        IndependentGroups[Entry].insert(Entry);
+        Queue.push_back(Entry);
+      }
+      while (!Queue.empty()) {
+        Block *Curr = Queue.front();
+        Queue.pop_front();
+        Block *Owner = Helper.Ownership[Curr]; // Curr must be in the ownership
+                                               // map if we are in the queue
+        if (!Owner)
+          continue; // we have been invalidated meanwhile after being reached
+                    // from two entries
+        // Add all children
+        for (const auto &iter : Curr->BranchesOut) {
+          Block *New = iter.first;
+          BlockBlockMap::iterator Known = Helper.Ownership.find(New);
+          if (Known == Helper.Ownership.end()) {
+            // New node. Add it, and put it in the queue
+            Helper.Ownership[New] = Owner;
+            IndependentGroups[Owner].insert(New);
+            Queue.push_back(New);
+            continue;
+          }
+          Block *NewOwner = Known->second;
+          if (!NewOwner)
+            continue; // We reached an invalidated node
+          if (NewOwner != Owner)
+            // Invalidate this and all reachable that we have seen - we reached
+            // this from two locations
+            Helper.InvalidateWithChildren(New);
+          // otherwise, we have the same owner, so do nothing
+        }
+      }
+
+      // Having processed all the interesting blocks, we remain with just one
+      // potential issue:
+      // If a->b, and a was invalidated, but then b was later reached by
+      // someone else, we must invalidate b. To check for this, we go over all
+      // elements in the independent groups, if an element has a parent which
+      // does *not* have the same owner, we/ must remove it and all its
+      // children.
+
+      for (const auto &iter : Entries) {
+        BlockSet &CurrGroup = IndependentGroups[iter];
+        BlockList ToInvalidate;
+        for (const auto &iter : CurrGroup) {
+          Block *Child = iter;
+          for (const auto &iter : Child->BranchesIn) {
+            Block *Parent = iter;
+            if (Ignore && contains(*Ignore, Parent))
+              continue;
+            if (Helper.Ownership[Parent] != Helper.Ownership[Child])
+              ToInvalidate.push_back(Child);
+          }
+        }
+        while (!ToInvalidate.empty()) {
+          Block *Invalidatee = ToInvalidate.front();
+          ToInvalidate.pop_front();
+          Helper.InvalidateWithChildren(Invalidatee);
+        }
+      }
+
+      // Remove empty groups
+      for (const auto &iter : Entries)
+        if (IndependentGroups[iter].empty())
+          IndependentGroups.erase(iter);
+    }
+
+    Shape *MakeMultiple(BlockSet &Blocks, BlockSet &Entries,
+                        BlockBlockSetMap &IndependentGroups, Shape *Prev,
+                        BlockSet &NextEntries) {
+      bool Fused = isa<SimpleShape>(Prev);
+      MultipleShape *Multiple = new MultipleShape();
+      Notice(Multiple);
+      BlockSet CurrEntries;
+      for (auto &iter : IndependentGroups) {
+        Block *CurrEntry = iter.first;
+        BlockSet &CurrBlocks = iter.second;
+        // Create inner block
+        CurrEntries.clear();
+        CurrEntries.insert(CurrEntry);
+        for (const auto &CurrInner : CurrBlocks) {
+          // Remove the block from the remaining blocks
+          Blocks.remove(CurrInner);
+          // Find new next entries and fix branches to them
+          for (auto iter = CurrInner->BranchesOut.begin();
+               iter != CurrInner->BranchesOut.end();) {
+            Block *CurrTarget = iter->first;
+            auto Next = iter;
+            Next++;
+            if (!contains(CurrBlocks, CurrTarget)) {
+              NextEntries.insert(CurrTarget);
+              Solipsize(CurrTarget, Branch::Break, Multiple, CurrBlocks);
+            }
+            iter = Next; // increment carefully because Solipsize can remove us
+          }
+        }
+        Multiple->InnerMap[CurrEntry->Id] =
+            Process(CurrBlocks, CurrEntries, nullptr);
+        // If we are not fused, then our entries will actually be checked
+        if (!Fused)
+          CurrEntry->IsCheckedMultipleEntry = true;
+      }
+      // Add entries not handled as next entries, they are deferred
+      for (const auto &Entry : Entries)
+        if (!contains(IndependentGroups, Entry))
+          NextEntries.insert(Entry);
+      // The multiple has been created, we can decide how to implement it
+      if (Multiple->InnerMap.size() >= RelooperMultipleSwitchThreshold) {
+        Multiple->UseSwitch = true;
+        Multiple->Breaks++; // switch captures breaks
+      }
+      return Multiple;
+    }
+
+    // Main function.
+    // Process a set of blocks with specified entries, returns a shape
+    // The Make* functions receive a NextEntries. If they fill it with data,
+    // those are the entries for the ->Next block on them, and the blocks
+    // are what remains in Blocks (which Make* modify). In this way
+    // we avoid recursing on Next (imagine a long chain of Simples, if we
+    // recursed we could blow the stack).
+    Shape *Process(BlockSet &Blocks, BlockSet &InitialEntries, Shape *Prev) {
+      BlockSet *Entries = &InitialEntries;
+      BlockSet TempEntries[2];
+      int CurrTempIndex = 0;
+      BlockSet *NextEntries;
+      Shape *Ret = nullptr;
+
+      auto Make = [&](Shape *Temp) {
+        if (Prev)
+          Prev->Next = Temp;
+        if (!Ret)
+          Ret = Temp;
+        Prev = Temp;
+        Entries = NextEntries;
+      };
+
+      while (1) {
+        CurrTempIndex = 1 - CurrTempIndex;
+        NextEntries = &TempEntries[CurrTempIndex];
+        NextEntries->clear();
+
+        if (Entries->empty())
+          return Ret;
+        if (Entries->size() == 1) {
+          Block *Curr = *(Entries->begin());
+          if (Curr->BranchesIn.empty()) {
+            // One entry, no looping ==> Simple
+            Make(MakeSimple(Blocks, Curr, *NextEntries));
+            if (NextEntries->empty())
+              return Ret;
+            continue;
+          }
+          // One entry, looping ==> Loop
+          Make(MakeLoop(Blocks, *Entries, *NextEntries));
+          if (NextEntries->empty())
+            return Ret;
+          continue;
+        }
+
+        // More than one entry, try to eliminate through a Multiple groups of
+        // independent blocks from an entry/ies. It is important to remove
+        // through multiples as opposed to looping since the former is more
+        // performant.
+        BlockBlockSetMap IndependentGroups;
+        FindIndependentGroups(*Entries, IndependentGroups);
+
+        if (!IndependentGroups.empty()) {
+          // We can handle a group in a multiple if its entry cannot be reached
+          // by another group.
+          // Note that it might be reachable by itself - a loop. But that is
+          // fine, we will create a loop inside the multiple block (which
+          // is the performant order to do it).
+          for (auto iter = IndependentGroups.begin();
+               iter != IndependentGroups.end();) {
+            Block *Entry = iter->first;
+            BlockSet &Group = iter->second;
+            auto curr = iter++; // iterate carefully, we may delete
+            for (BlockSet::iterator iterBranch = Entry->BranchesIn.begin();
+                 iterBranch != Entry->BranchesIn.end(); iterBranch++) {
+              Block *Origin = *iterBranch;
+              if (!contains(Group, Origin)) {
+                // Reached from outside the group, so we cannot handle this
+                IndependentGroups.erase(curr);
+                break;
+              }
+            }
+          }
+
+          // As an optimization, if we have 2 independent groups, and one is a
+          // small dead end, we can handle only that dead end.
+          // The other then becomes a Next - without nesting in the code and
+          // recursion in the analysis.
+          // TODO: if the larger is the only dead end, handle that too
+          // TODO: handle >2 groups
+          // TODO: handle not just dead ends, but also that do not branch to the
+          // NextEntries. However, must be careful there since we create a
+          // Next, and that Next can prevent eliminating a break (since we no
+          // longer naturally reach the same place), which may necessitate a
+          // one-time loop, which makes the unnesting pointless.
+          if (IndependentGroups.size() == 2) {
+            // Find the smaller one
+            auto iter = IndependentGroups.begin();
+            Block *SmallEntry = iter->first;
+            auto SmallSize = iter->second.size();
+            iter++;
+            Block *LargeEntry = iter->first;
+            auto LargeSize = iter->second.size();
+            if (SmallSize != LargeSize) { // ignore the case where they are
+                                          // identical - keep things symmetrical
+                                          // there
+              if (SmallSize > LargeSize) {
+                Block *Temp = SmallEntry;
+                SmallEntry = LargeEntry;
+                LargeEntry = Temp; // Note: we did not flip the Sizes too, they
+                                   // are now invalid. TODO: use the smaller
+                                   // size as a limit?
+              }
+              // Check if dead end
+              bool DeadEnd = true;
+              BlockSet &SmallGroup = IndependentGroups[SmallEntry];
+              for (const auto &Curr : SmallGroup) {
+                for (const auto &iter : Curr->BranchesOut) {
+                  Block *Target = iter.first;
+                  if (!contains(SmallGroup, Target)) {
+                    DeadEnd = false;
+                    break;
+                  }
+                }
+                if (!DeadEnd)
+                  break;
+              }
+              if (DeadEnd)
+                IndependentGroups.erase(LargeEntry);
+            }
+          }
+
+          if (!IndependentGroups.empty())
+            // Some groups removable ==> Multiple
+            Make(MakeMultiple(Blocks, *Entries, IndependentGroups, Prev,
+                              *NextEntries));
+            if (NextEntries->empty())
+              return Ret;
+            continue;
+        }
+        // No independent groups, must be loopable ==> Loop
+        Make(MakeLoop(Blocks, *Entries, *NextEntries));
+        if (NextEntries->empty())
+          return Ret;
+        continue;
+      }
+    }
+  };
+
+  // Main
+
+  BlockSet AllBlocks;
+  for (const auto &Curr : Pre.Live) {
+    AllBlocks.insert(Curr);
+  }
+
+  BlockSet Entries;
+  Entries.insert(Entry);
+  Root = Analyzer(this).Process(AllBlocks, Entries, nullptr);
+  assert(Root);
+
+  ///
+  /// Relooper post-optimizer
+  ///
+  struct PostOptimizer {
+    Relooper *Parent;
+    std::stack<Shape *> LoopStack;
+
+    PostOptimizer(Relooper *ParentInit) : Parent(ParentInit) {}
+
+    void ShapeSwitch(Shape* var,
+                     std::function<void (SimpleShape*)> simple,
+                     std::function<void (MultipleShape*)> multiple,
+                     std::function<void (LoopShape*)> loop) {
+      switch (var->getKind()) {
+        case Shape::SK_Simple: {
+          simple(cast<SimpleShape>(var));
+          break;
+        }
+        case Shape::SK_Multiple: {
+          multiple(cast<MultipleShape>(var));
+          break;
+        }
+        case Shape::SK_Loop: {
+          loop(cast<LoopShape>(var));
+          break;
+        }
+        default: llvm_unreachable("invalid shape");
+      }
+    }
+
+    // Find the blocks that natural control flow can get us directly to, or
+    // through a multiple that we ignore
+    void FollowNaturalFlow(Shape *S, BlockSet &Out) {
+      ShapeSwitch(S, [&](SimpleShape* Simple) {
+        Out.insert(Simple->Inner);
+      }, [&](MultipleShape* Multiple) {
+        for (const auto &iter : Multiple->InnerMap) {
+          FollowNaturalFlow(iter.second, Out);
+        }
+        FollowNaturalFlow(Multiple->Next, Out);
+      }, [&](LoopShape* Loop) {
+        FollowNaturalFlow(Loop->Inner, Out);
+      });
+    }
+
+    void FindNaturals(Shape *Root, Shape *Otherwise = nullptr) {
+      if (Root->Next) {
+        Root->Natural = Root->Next;
+        FindNaturals(Root->Next, Otherwise);
+      } else {
+        Root->Natural = Otherwise;
+      }
+
+      ShapeSwitch(Root, [](SimpleShape* Simple) {
+      }, [&](MultipleShape* Multiple) {
+        for (const auto &iter : Multiple->InnerMap) {
+          FindNaturals(iter.second, Root->Natural);
+        }
+      }, [&](LoopShape* Loop){
+        FindNaturals(Loop->Inner, Loop->Inner);
+      });
+    }
+
+    // Remove unneeded breaks and continues.
+    // A flow operation is trivially unneeded if the shape we naturally get to
+    // by normal code execution is the same as the flow forces us to.
+    void RemoveUnneededFlows(Shape *Root, Shape *Natural = nullptr,
+                             LoopShape *LastLoop = nullptr,
+                             unsigned Depth = 0) {
+      BlockSet NaturalBlocks;
+      FollowNaturalFlow(Natural, NaturalBlocks);
+      Shape *Next = Root;
+      while (Next) {
+        Root = Next;
+        Next = nullptr;
+        ShapeSwitch(
+            Root,
+            [&](SimpleShape* Simple) {
+              if (Simple->Inner->BranchVar)
+                LastLoop =
+                    nullptr; // a switch clears out the loop (TODO: only for
+                             // breaks, not continue)
+
+              if (Simple->Next) {
+                if (!Simple->Inner->BranchVar &&
+                    Simple->Inner->ProcessedBranchesOut.size() == 2 &&
+                    Depth < RelooperNestingLimit) {
+                  // If there is a next block, we already know at Simple
+                  // creation time to make direct branches, and we can do
+                  // nothing more in general. But, we try to optimize the
+                  // case of a break and a direct: This would normally be
+                  //   if (break?) { break; } ..
+                  // but if we make sure to nest the else, we can save the
+                  // break,
+                  //   if (!break?) { .. }
+                  // This is also better because the more canonical nested
+                  // form is easier to further optimize later. The
+                  // downside is more nesting, which adds to size in builds with
+                  // whitespace.
+                  // Note that we avoid switches, as it complicates control flow
+                  // and is not relevant for the common case we optimize here.
+                  bool Found = false;
+                  bool Abort = false;
+                  for (const auto &iter : Simple->Inner->ProcessedBranchesOut) {
+                    Block *Target = iter.first;
+                    Branch *Details = iter.second.get();
+                    if (Details->Type == Branch::Break) {
+                      Found = true;
+                      if (!contains(NaturalBlocks, Target))
+                        Abort = true;
+                    } else if (Details->Type != Branch::Direct)
+                      Abort = true;
+                  }
+                  if (Found && !Abort) {
+                    for (const auto &iter : Simple->Inner->ProcessedBranchesOut) {
+                      Branch *Details = iter.second.get();
+                      if (Details->Type == Branch::Break) {
+                        Details->Type = Branch::Direct;
+                        if (MultipleShape *Multiple =
+                                dyn_cast<MultipleShape>(Details->Ancestor))
+                          Multiple->Breaks--;
+                      } else {
+                        assert(Details->Type == Branch::Direct);
+                        Details->Type = Branch::Nested;
+                      }
+                    }
+                  }
+                  Depth++; // this optimization increases depth, for us and all
+                           // our next chain (i.e., until this call returns)
+                }
+                Next = Simple->Next;
+              } else {
+                // If there is no next then Natural is where we will
+                // go to by doing nothing, so we can potentially optimize some
+                // branches to direct.
+                for (const auto &iter : Simple->Inner->ProcessedBranchesOut) {
+                  Block *Target = iter.first;
+                  Branch *Details = iter.second.get();
+                  if (Details->Type != Branch::Direct &&
+                      contains(NaturalBlocks,
+                               Target)) { // note: cannot handle split blocks
+                    Details->Type = Branch::Direct;
+                    if (MultipleShape *Multiple =
+                            dyn_cast<MultipleShape>(Details->Ancestor))
+                      Multiple->Breaks--;
+                  } else if (Details->Type == Branch::Break && LastLoop &&
+                             LastLoop->Natural == Details->Ancestor->Natural) {
+                    // it is important to simplify breaks, as simpler breaks
+                    // enable other optimizations
+                    Details->Labeled = false;
+                    if (MultipleShape *Multiple =
+                            dyn_cast<MultipleShape>(Details->Ancestor))
+                      Multiple->Breaks--;
+                  }
+                }
+              }
+            }, [&](MultipleShape* Multiple)
+            {
+              for (const auto &iter : Multiple->InnerMap) {
+                RemoveUnneededFlows(iter.second, Multiple->Next,
+                                    Multiple->Breaks ? nullptr : LastLoop,
+                                    Depth + 1);
+              }
+              Next = Multiple->Next;
+            }, [&](LoopShape* Loop)
+            {
+              RemoveUnneededFlows(Loop->Inner, Loop->Inner, Loop, Depth + 1);
+              Next = Loop->Next;
+            });
+      }
+    }
+
+    // After we know which loops exist, we can calculate which need to be
+    // labeled
+    void FindLabeledLoops(Shape *Root) {
+      Shape *Next = Root;
+      while (Next) {
+        Root = Next;
+        Next = nullptr;
+
+        ShapeSwitch(
+            Root,
+            [&](SimpleShape *Simple) {
+          MultipleShape *Fused = dyn_cast<MultipleShape>(Root->Next);
+          // If we are fusing a Multiple with a loop into this Simple, then
+          // visit it now
+          if (Fused && Fused->Breaks)
+            LoopStack.push(Fused);
+          if (Simple->Inner->BranchVar)
+            LoopStack.push(nullptr); // a switch means breaks are now useless,
+                                     // push a dummy
+          if (Fused) {
+            if (Fused->UseSwitch)
+              LoopStack.push(nullptr); // a switch means breaks are now
+                                       // useless, push a dummy
+            for (const auto &iter : Fused->InnerMap) {
+              FindLabeledLoops(iter.second);
+            }
+          }
+          for (const auto &iter : Simple->Inner->ProcessedBranchesOut) {
+            Branch *Details = iter.second.get();
+            if (Details->Type == Branch::Break ||
+                Details->Type == Branch::Continue) {
+              assert(!LoopStack.empty());
+              if (Details->Ancestor != LoopStack.top() && Details->Labeled) {
+                if (MultipleShape *Multiple =
+                        dyn_cast<MultipleShape>(Details->Ancestor)) {
+                  Multiple->Labeled = true;
+                } else {
+                  LoopShape *Loop = cast<LoopShape>(Details->Ancestor);
+                  Loop->Labeled = true;
+                }
+              } else {
+                Details->Labeled = false;
+              }
+            }
+            if (Fused && Fused->UseSwitch)
+              LoopStack.pop();
+            if (Simple->Inner->BranchVar)
+              LoopStack.pop();
+            if (Fused && Fused->Breaks)
+              LoopStack.pop();
+            if (Fused)
+              Next = Fused->Next;
+            else
+              Next = Root->Next;
+          }
+          }
+          , [&](MultipleShape* Multiple) {
+            if (Multiple->Breaks)
+              LoopStack.push(Multiple);
+            for (const auto &iter : Multiple->InnerMap)
+              FindLabeledLoops(iter.second);
+            if (Multiple->Breaks)
+              LoopStack.pop();
+            Next = Root->Next;
+          }
+          , [&](LoopShape* Loop) {
+            LoopStack.push(Loop);
+            FindLabeledLoops(Loop->Inner);
+            LoopStack.pop();
+            Next = Root->Next;
+          });
+      }
+    }
+
+    void Process(Shape * Root) {
+      FindNaturals(Root);
+      RemoveUnneededFlows(Root);
+      FindLabeledLoops(Root);
+    }
+  };
+
+  PostOptimizer(this).Process(Root);
+}
+
+} // namespace Relooper
+
+} // namespace llvm