1 //===-- Relooper.h - Top-level interface for WebAssembly ----*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===-------------------------------------------------------------------===// 9 /// 10 /// \file 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. 14 /// 15 //===-------------------------------------------------------------------===// 16 17 #include "llvm/ADT/MapVector.h" 18 #include "llvm/ADT/SetVector.h" 19 #include "llvm/Support/Casting.h" 20 21 #include <cassert> 22 #include <cstdarg> 23 #include <cstdio> 24 #include <deque> 25 #include <list> 26 #include <map> 27 #include <memory> 28 #include <set> 29 30 namespace llvm { 31 32 namespace Relooper { 33 34 struct Block; 35 struct Shape; 36 37 /// 38 /// Info about a branching from one block to another 39 /// 40 struct Branch { 41 enum FlowType { 42 Direct = 0, // We will directly reach the right location through other 43 // means, no need for continue or break 44 Break = 1, 45 Continue = 2, 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 50 }; 51 Shape 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 54 Branch::FlowType 55 Type; // If Ancestor is not nullptr, this says whether to break or 56 // continue 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 66 67 Branch(const char *ConditionInit, const char *CodeInit = nullptr); 68 ~Branch(); 69 }; 70 71 typedef SetVector<Block *> BlockSet; 72 typedef MapVector<Block *, Branch *> BlockBranchMap; 73 typedef MapVector<Block *, std::unique_ptr<Branch>> OwningBlockBranchMap; 74 75 /// 76 /// Represents a basic block of code - some instructions that end with a 77 /// control flow modifier (a branch, return or throw). 78 /// 79 struct Block { 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; 86 BlockSet BranchesIn; 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 101 102 Block(const char *CodeInit, const char *BranchVarInit); 103 ~Block(); 104 105 void AddBranchTo(Block *Target, const char *Condition, 106 const char *Code = nullptr); 107 }; 108 109 /// 110 /// Represents a structured control flow shape 111 /// 112 struct 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) 118 119 /// Discriminator for LLVM-style RTTI (dyn_cast<> et al.) 120 enum ShapeKind { SK_Simple, SK_Multiple, SK_Loop }; 121 122 private: 123 ShapeKind Kind; 124 125 public: 126 ShapeKind getKind() const { return Kind; } 127 128 Shape(ShapeKind KindInit) : Id(-1), Next(nullptr), Kind(KindInit) {} 129 }; 130 131 /// 132 /// Simple: No control flow at all, just instructions. 133 /// 134 struct SimpleShape : public Shape { 135 Block *Inner; 136 137 SimpleShape() : Shape(SK_Simple), Inner(nullptr) {} 138 139 static bool classof(const Shape *S) { return S->getKind() == SK_Simple; } 140 }; 141 142 /// 143 /// A shape that may be implemented with a labeled loop. 144 /// 145 struct LabeledShape : public Shape { 146 bool Labeled; // If we have a loop, whether it needs to be labeled 147 148 LabeledShape(ShapeKind KindInit) : Shape(KindInit), Labeled(false) {} 149 }; 150 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; 154 155 /// 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 159 /// next shape. 160 /// 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 167 168 MultipleShape() : LabeledShape(SK_Multiple), Breaks(0), UseSwitch(false) {} 169 170 static bool classof(const Shape *S) { return S->getKind() == SK_Multiple; } 171 }; 172 173 /// 174 /// Loop: An infinite loop. 175 /// 176 struct LoopShape : public LabeledShape { 177 Shape *Inner; 178 179 LoopShape() : LabeledShape(SK_Loop), Inner(nullptr) {} 180 181 static bool classof(const Shape *S) { return S->getKind() == SK_Loop; } 182 }; 183 184 } // namespace Relooper 185 186 } // namespace llvm 187
