1 //===-- Relooper.h - Top-level interface for WebAssembly ----*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===-------------------------------------------------------------------===//
11 /// \brief This defines an optimized C++ implemention of the Relooper
12 /// algorithm, originally developed as part of Emscripten, which
13 /// generates a structured AST from arbitrary control flow.
15 //===-------------------------------------------------------------------===//
17 #include "llvm/ADT/MapVector.h"
18 #include "llvm/ADT/SetVector.h"
19 #include "llvm/Support/Casting.h"
38 /// Info about a branching from one block to another
42 Direct = 0, // We will directly reach the right location through other
43 // means, no need for continue or break
46 Nested = 3 // This code is directly reached, but we must be careful to
47 // ensure it is nested in an if - it is not reached
48 // unconditionally, other code paths exist alongside it that we need to make
49 // sure do not intertwine
52 *Ancestor; // If not nullptr, this shape is the relevant one for purposes
53 // of getting to the target block. We break or continue on it
55 Type; // If Ancestor is not nullptr, this says whether to break or
57 bool Labeled; // If a break or continue, whether we need to use a label
58 const char *Condition; // The condition for which we branch. For example,
59 // "my_var == 1". Conditions are checked one by one.
60 // One of the conditions should have nullptr as the
61 // condition, in which case it is the default
62 // FIXME: move from char* to LLVM data structures
63 const char *Code; // If provided, code that is run right before the branch is
64 // taken. This is useful for phis
65 // FIXME: move from char* to LLVM data structures
67 Branch(const char *ConditionInit, const char *CodeInit = nullptr);
71 typedef SetVector<Block *> BlockSet;
72 typedef MapVector<Block *, Branch *> BlockBranchMap;
73 typedef MapVector<Block *, std::unique_ptr<Branch>> OwningBlockBranchMap;
76 /// Represents a basic block of code - some instructions that end with a
77 /// control flow modifier (a branch, return or throw).
80 // Branches become processed after we finish the shape relevant to them. For
81 // example, when we recreate a loop, branches to the loop start become
82 // continues and are now processed. When we calculate what shape to generate
83 // from a set of blocks, we ignore processed branches. Blocks own the Branch
84 // objects they use, and destroy them when done.
85 OwningBlockBranchMap BranchesOut;
87 OwningBlockBranchMap ProcessedBranchesOut;
88 BlockSet ProcessedBranchesIn;
89 Shape *Parent; // The shape we are directly inside
90 int Id; // A unique identifier, defined when added to relooper. Note that this
91 // uniquely identifies a *logical* block - if we split it, the two
92 // instances have the same content *and* the same Id
93 const char *Code; // The string representation of the code in this block.
94 // Owning pointer (we copy the input)
95 // FIXME: move from char* to LLVM data structures
96 const char *BranchVar; // A variable whose value determines where we go; if
97 // this is not nullptr, emit a switch on that variable
98 // FIXME: move from char* to LLVM data structures
99 bool IsCheckedMultipleEntry; // If true, we are a multiple entry, so reaching
100 // us requires setting the label variable
102 Block(const char *CodeInit, const char *BranchVarInit);
105 void AddBranchTo(Block *Target, const char *Condition,
106 const char *Code = nullptr);
110 /// Represents a structured control flow shape
113 int Id; // A unique identifier. Used to identify loops, labels are Lx where x
114 // is the Id. Defined when added to relooper
115 Shape *Next; // The shape that will appear in the code right after this one
116 Shape *Natural; // The shape that control flow gets to naturally (if there is
117 // Next, then this is Next)
119 /// Discriminator for LLVM-style RTTI (dyn_cast<> et al.)
120 enum ShapeKind { SK_Simple, SK_Multiple, SK_Loop };
126 ShapeKind getKind() const { return Kind; }
128 Shape(ShapeKind KindInit) : Id(-1), Next(nullptr), Kind(KindInit) {}
132 /// Simple: No control flow at all, just instructions.
134 struct SimpleShape : public Shape {
137 SimpleShape() : Shape(SK_Simple), Inner(nullptr) {}
139 static bool classof(const Shape *S) { return S->getKind() == SK_Simple; }
143 /// A shape that may be implemented with a labeled loop.
145 struct LabeledShape : public Shape {
146 bool Labeled; // If we have a loop, whether it needs to be labeled
148 LabeledShape(ShapeKind KindInit) : Shape(KindInit), Labeled(false) {}
151 // Blocks with the same id were split and are identical, so we just care about
152 // ids in Multiple entries
153 typedef std::map<int, Shape *> IdShapeMap;
156 /// Multiple: A shape with more than one entry. If the next block to
157 /// be entered is among them, we run it and continue to
158 /// the next shape, otherwise we continue immediately to the
161 struct MultipleShape : public LabeledShape {
162 IdShapeMap InnerMap; // entry block ID -> shape
163 int Breaks; // If we have branches on us, we need a loop (or a switch). This
164 // is a counter of requirements,
165 // if we optimize it to 0, the loop is unneeded
166 bool UseSwitch; // Whether to switch on label as opposed to an if-else chain
168 MultipleShape() : LabeledShape(SK_Multiple), Breaks(0), UseSwitch(false) {}
170 static bool classof(const Shape *S) { return S->getKind() == SK_Multiple; }
174 /// Loop: An infinite loop.
176 struct LoopShape : public LabeledShape {
179 LoopShape() : LabeledShape(SK_Loop), Inner(nullptr) {}
181 static bool classof(const Shape *S) { return S->getKind() == SK_Loop; }
184 } // namespace Relooper