Where Online Learning is simpler!

The C and C++ Include Header Files

cat -n /usr/include/wabt/decompiler-ast.h

     1	/*
     2	 * Copyright 2016 WebAssembly Community Group participants
     3	 *
     4	 * Licensed under the Apache License, Version 2.0 (the "License");
     5	 * you may not use this file except in compliance with the License.
     6	 * You may obtain a copy of the License at
     7	 *
     8	 *     http://www.apache.org/licenses/LICENSE-2.0
     9	 *
    10	 * Unless required by applicable law or agreed to in writing, software
    11	 * distributed under the License is distributed on an "AS IS" BASIS,
    12	 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    13	 * See the License for the specific language governing permissions and
    14	 * limitations under the License.
    15	 */
    16	
    17	#ifndef WABT_DECOMPILER_AST_H_
    18	#define WABT_DECOMPILER_AST_H_
    19	
    20	#include "wabt/cast.h"
    21	#include "wabt/generate-names.h"
    22	#include "wabt/ir-util.h"
    23	#include "wabt/ir.h"
    24	
    25	#include <map>
    26	
    27	namespace wabt {
    28	
    29	enum class NodeType {
    30	  Uninitialized,
    31	  FlushToVars,
    32	  FlushedVar,
    33	  Statements,
    34	  EndReturn,
    35	  Decl,
    36	  DeclInit,
    37	  Expr
    38	};
    39	
    40	// The AST we're going to convert the standard IR into.
    41	struct Node {
    42	  NodeType ntype;
    43	  ExprType etype;  // Only if ntype == Expr.
    44	  const Expr* e;
    45	  std::vector<Node> children;
    46	  // Node specific annotations.
    47	  union {
    48	    struct {
    49	      Index var_start, var_count;  // FlushedVar/FlushToVars
    50	    };
    51	    const Var* var;  // Decl/DeclInit.
    52	    LabelType lt;    // br/br_if target.
    53	  } u;
    54	
    55	  Node() : ntype(NodeType::Uninitialized), etype(ExprType::Nop), e(nullptr) {}
    56	  Node(NodeType ntype, ExprType etype, const Expr* e, const Var* v)
    57	      : ntype(ntype), etype(etype), e(e) {
    58	    u.var = v;
    59	  }
    60	
    61	  // This value should really never be copied, only moved.
    62	  Node(const Node& rhs) = delete;
    63	  Node& operator=(const Node& rhs) = delete;
    64	
    65	  Node(Node&& rhs) { *this = std::move(rhs); }
    66	  Node& operator=(Node&& rhs) {
    67	    ntype = rhs.ntype;
    68	    // Reset ntype to avoid moved from values still being used.
    69	    rhs.ntype = NodeType::Uninitialized;
    70	    etype = rhs.etype;
    71	    rhs.etype = ExprType::Nop;
    72	    e = rhs.e;
    73	    std::swap(children, rhs.children);
    74	    u = rhs.u;
    75	    return *this;
    76	  }
    77	};
    78	
    79	struct AST {
    80	  AST(ModuleContext& mc, const Func* f) : mc(mc), f(f) {
    81	    if (f) {
    82	      mc.BeginFunc(*f);
    83	      for (Index i = 0; i < f->GetNumParams(); i++) {
    84	        auto name = "$" + IndexToAlphaName(i);
    85	        vars_defined.insert({name, {0, false}});
    86	      }
    87	    }
    88	  }
    89	
    90	  ~AST() {
    91	    if (f) {
    92	      mc.EndFunc();
    93	    }
    94	  }
    95	
    96	  // Create a new node, take nargs existing nodes on the exp stack as children.
    97	  Node& InsertNode(NodeType ntype, ExprType etype, const Expr* e, Index nargs) {
    98	    assert(exp_stack.size() >= nargs);
    99	    Node n{ntype, etype, e, nullptr};
   100	    n.children.reserve(nargs);
   101	    std::move(exp_stack.end() - nargs, exp_stack.end(),
   102	              std::back_inserter(n.children));
   103	    exp_stack.erase(exp_stack.end() - nargs, exp_stack.end());
   104	    exp_stack.push_back(std::move(n));
   105	    return exp_stack.back();
   106	  }
   107	
   108	  template <ExprType T>
   109	  void PreDecl(const VarExpr<T>& ve) {
   110	    // FIXME: this is slow, and would be better to avoid in callers.
   111	    // See https://github.com/WebAssembly/wabt/issues/1565
   112	    // And https://github.com/WebAssembly/wabt/issues/1665
   113	    for (auto& n : predecls) {
   114	      if (n.u.var->name() == ve.var.name()) {
   115	        return;
   116	      }
   117	    }
   118	    predecls.emplace_back(NodeType::Decl, ExprType::Nop, nullptr, &ve.var);
   119	  }
   120	
   121	  template <ExprType T>
   122	  void Get(const VarExpr<T>& ve, bool local) {
   123	    if (local) {
   124	      auto ret = vars_defined.insert({ve.var.name(), {cur_block_id, false}});
   125	      if (ret.second) {
   126	        // Use before def, may happen since locals are guaranteed 0.
   127	        PreDecl(ve);
   128	      } else if (blocks_closed[ret.first->second.block_id]) {
   129	        // This is a use of a variable that was defined in a block that has
   130	        // already ended. This happens rarely, but we should cater for this
   131	        // case by lifting it to the top scope.
   132	        PreDecl(ve);
   133	      }
   134	    }
   135	    InsertNode(NodeType::Expr, T, &ve, 0);
   136	  }
   137	
   138	  template <ExprType T>
   139	  void Set(const VarExpr<T>& ve, bool local) {
   140	    // Seen this var before?
   141	    if (local &&
   142	        vars_defined.insert({ve.var.name(), {cur_block_id, false}}).second) {
   143	      if (value_stack_depth == 1) {
   144	        // Top level, declare it here.
   145	        InsertNode(NodeType::DeclInit, ExprType::Nop, nullptr, 1).u.var =
   146	            &ve.var;
   147	        return;
   148	      } else {
   149	        // Inside exp, better leave it as assignment exp and lift the decl out.
   150	        PreDecl(ve);
   151	      }
   152	    }
   153	    InsertNode(NodeType::Expr, T, &ve, 1);
   154	  }
   155	
   156	  template <ExprType T>
   157	  void Block(const BlockExprBase<T>& be, LabelType label) {
   158	    mc.BeginBlock(label, be.block);
   159	    Construct(be.block.exprs, be.block.decl.GetNumResults(),
   160	              be.block.decl.GetNumParams(), false);
   161	    mc.EndBlock();
   162	    InsertNode(NodeType::Expr, T, &be, 1);
   163	  }
   164	
   165	  void Construct(const Expr& e) {
   166	    auto arity = mc.GetExprArity(e);
   167	    switch (e.type()) {
   168	      case ExprType::LocalGet: {
   169	        Get(*cast<LocalGetExpr>(&e), true);
   170	        return;
   171	      }
   172	      case ExprType::GlobalGet: {
   173	        Get(*cast<GlobalGetExpr>(&e), false);
   174	        return;
   175	      }
   176	      case ExprType::LocalSet: {
   177	        Set(*cast<LocalSetExpr>(&e), true);
   178	        return;
   179	      }
   180	      case ExprType::GlobalSet: {
   181	        Set(*cast<GlobalSetExpr>(&e), false);
   182	        return;
   183	      }
   184	      case ExprType::LocalTee: {
   185	        auto& lt = *cast<LocalTeeExpr>(&e);
   186	        Set(lt, true);
   187	        if (value_stack_depth == 1) {  // Tee is the only thing on there.
   188	          Get(lt, true);               // Now Set + Get instead.
   189	        } else {
   190	          // Things are above us on the stack so the Tee can't be eliminated.
   191	          // The Set makes this work as a Tee when consumed by a parent.
   192	        }
   193	        return;
   194	      }
   195	      case ExprType::If: {
   196	        auto ife = cast<IfExpr>(&e);
   197	        value_stack_depth--;  // Condition.
   198	        mc.BeginBlock(LabelType::Block, ife->true_);
   199	        Construct(ife->true_.exprs, ife->true_.decl.GetNumResults(),
   200	                  ife->true_.decl.GetNumParams(), false);
   201	        if (!ife->false_.empty()) {
   202	          Construct(ife->false_, ife->true_.decl.GetNumResults(),
   203	                    ife->true_.decl.GetNumParams(), false);
   204	        }
   205	        mc.EndBlock();
   206	        value_stack_depth++;  // Put Condition back.
   207	        InsertNode(NodeType::Expr, ExprType::If, &e,
   208	                   ife->false_.empty() ? 2 : 3);
   209	        return;
   210	      }
   211	      case ExprType::Block: {
   212	        Block(*cast<BlockExpr>(&e), LabelType::Block);
   213	        return;
   214	      }
   215	      case ExprType::Loop: {
   216	        Block(*cast<LoopExpr>(&e), LabelType::Loop);
   217	        return;
   218	      }
   219	      case ExprType::Br: {
   220	        InsertNode(NodeType::Expr, ExprType::Br, &e, 0).u.lt =
   221	            mc.GetLabel(cast<BrExpr>(&e)->var)->label_type;
   222	        return;
   223	      }
   224	      case ExprType::BrIf: {
   225	        InsertNode(NodeType::Expr, ExprType::BrIf, &e, 1).u.lt =
   226	            mc.GetLabel(cast<BrIfExpr>(&e)->var)->label_type;
   227	        return;
   228	      }
   229	      case ExprType::BrTable: {
   230	        InsertNode(NodeType::Expr, ExprType::BrTable, &e, 1).u.lt =
   231	            mc.GetLabel(cast<BrTableExpr>(&e)->default_target)->label_type;
   232	        return;
   233	      }
   234	      default: {
   235	        InsertNode(NodeType::Expr, e.type(), &e, arity.nargs);
   236	        return;
   237	      }
   238	    }
   239	  }
   240	
   241	  void Construct(const ExprList& es,
   242	                 Index nresults,
   243	                 Index nparams,
   244	                 bool is_function_body) {
   245	    block_stack.push_back(cur_block_id);
   246	    cur_block_id = blocks_closed.size();
   247	    blocks_closed.push_back(false);
   248	    auto start = exp_stack.size();
   249	    int value_stack_depth_start = value_stack_depth - nparams;
   250	    auto value_stack_in_variables = value_stack_depth;
   251	    bool unreachable = false;
   252	    for (auto& e : es) {
   253	      Construct(e);
   254	      auto arity = mc.GetExprArity(e);
   255	      value_stack_depth -= arity.nargs;
   256	      value_stack_in_variables =
   257	          std::min(value_stack_in_variables, value_stack_depth);
   258	      unreachable = unreachable || arity.unreachable;
   259	      assert(unreachable || value_stack_depth >= value_stack_depth_start);
   260	      value_stack_depth += arity.nreturns;
   261	      // We maintain the invariant that a value_stack_depth of N is represented
   262	      // by the last N exp_stack items (each of which returning exactly 1
   263	      // value), all exp_stack items before it return void ("statements").
   264	      // In particular for the wasm stack:
   265	      // - The values between 0 and value_stack_depth_start are part of the
   266	      //   parent block, and not touched here.
   267	      // - The values from there up to value_stack_in_variables are variables
   268	      //   to be used, representing previous statements that flushed the
   269	      //   stack into variables.
   270	      // - Values on top of that up to value_stack_depth are exps returning
   271	      //   a single value.
   272	      // The code below maintains the above invariants. With this in place
   273	      // code "falls into place" the way you expect it.
   274	      if (arity.nreturns != 1) {
   275	        auto num_vars = value_stack_in_variables - value_stack_depth_start;
   276	        auto num_vals = value_stack_depth - value_stack_in_variables;
   277	        auto GenFlushVars = [&](int nargs) {
   278	          auto& ftv =
   279	              InsertNode(NodeType::FlushToVars, ExprType::Nop, nullptr, nargs);
   280	          ftv.u.var_start = flushed_vars;
   281	          ftv.u.var_count = num_vals;
   282	        };
   283	        auto MoveStatementsBelowVars = [&](size_t amount) {
   284	          std::rotate(exp_stack.end() - num_vars - amount,
   285	                      exp_stack.end() - amount, exp_stack.end());
   286	        };
   287	        auto GenFlushedVars = [&]() {
   288	          // Re-generate these values as vars.
   289	          for (int i = 0; i < num_vals; i++) {
   290	            auto& fv =
   291	                InsertNode(NodeType::FlushedVar, ExprType::Nop, nullptr, 0);
   292	            fv.u.var_start = flushed_vars++;
   293	            fv.u.var_count = 1;
   294	          }
   295	        };
   296	        if (arity.nreturns == 0 &&
   297	            value_stack_depth > value_stack_depth_start) {
   298	          // We have a void item on top of the exp_stack, so we must "lift" the
   299	          // previous values around it.
   300	          // We track what part of the stack is in variables to avoid doing
   301	          // this unnecessarily.
   302	          if (num_vals > 0) {
   303	            // We have actual new values that need lifting.
   304	            // This puts the part of the stack that wasn't already a variable
   305	            // (before the current void exp) into a FlushToVars.
   306	            auto void_exp = std::move(exp_stack.back());
   307	            exp_stack.pop_back();
   308	            GenFlushVars(num_vals);
   309	            exp_stack.push_back(std::move(void_exp));
   310	            // Put this flush statement + void statement before any
   311	            // existing variables.
   312	            MoveStatementsBelowVars(2);
   313	            // Now re-generate these values after the void exp as vars.
   314	            GenFlushedVars();
   315	          } else {
   316	            // We have existing variables that need lifting, but no need to
   317	            // create them anew.
   318	            std::rotate(exp_stack.end() - num_vars - 1, exp_stack.end() - 1,
   319	                        exp_stack.end());
   320	          }
   321	          value_stack_in_variables = value_stack_depth;
   322	        } else if (arity.nreturns > 1) {
   323	          // Multivalue: we flush the stack also.
   324	          // Number of other non-variable values that may be present:
   325	          assert(num_vals >= static_cast<int>(arity.nreturns));
   326	          // Flush multi-value exp + others.
   327	          GenFlushVars(num_vals - arity.nreturns + 1);
   328	          // Put this flush statement before any existing variables.
   329	          MoveStatementsBelowVars(1);
   330	          GenFlushedVars();
   331	          value_stack_in_variables = value_stack_depth;
   332	        }
   333	      } else {
   334	        // Special optimisation: for constant instructions, we can mark these
   335	        // as if they were variables, so they can be re-ordered for free with
   336	        // the above code, without needing new variables!
   337	        // TODO: this would be nice to also do for local.get and maybe others,
   338	        // though that needs a way to ensure there's no local.set in between
   339	        // when they get lifted, so complicates matters a bit.
   340	        if (e.type() == ExprType::Const &&
   341	            value_stack_in_variables == value_stack_depth - 1) {
   342	          value_stack_in_variables++;
   343	        }
   344	      }
   345	    }
   346	    assert(unreachable || value_stack_depth - value_stack_depth_start ==
   347	                              static_cast<int>(nresults));
   348	    // Undo any changes to value_stack_depth, since parent takes care of arity
   349	    // changes.
   350	    value_stack_depth = value_stack_depth_start;
   351	    auto end = exp_stack.size();
   352	    assert(end >= start);
   353	    if (is_function_body) {
   354	      if (!exp_stack.empty()) {
   355	        if (exp_stack.back().etype == ExprType::Return) {
   356	          if (exp_stack.back().children.empty()) {
   357	            // Return statement at the end of a void function.
   358	            exp_stack.pop_back();
   359	          }
   360	        } else if (nresults) {
   361	          // Combine nresults into a return statement, for when this is used as
   362	          // a function body.
   363	          // TODO: if this is some other kind of block and >1 value is being
   364	          // returned, probably need some kind of syntax to make that clearer.
   365	          InsertNode(NodeType::EndReturn, ExprType::Nop, nullptr, nresults);
   366	        }
   367	      }
   368	      // TODO: these predecls are always at top level, but in the case of
   369	      // use inside an exp, it be nice to do it in the current block. Can't
   370	      // do that for predecls that are "out if scope" however.
   371	      std::move(predecls.begin(), predecls.end(),
   372	                std::back_inserter(exp_stack));
   373	      std::rotate(exp_stack.begin(), exp_stack.end() - predecls.size(),
   374	                  exp_stack.end());
   375	      predecls.clear();
   376	    }
   377	    end = exp_stack.size();
   378	    assert(end >= start);
   379	    auto size = end - start;
   380	    if (size != 1) {
   381	      InsertNode(NodeType::Statements, ExprType::Nop, nullptr, size);
   382	    }
   383	    blocks_closed[cur_block_id] = true;
   384	    cur_block_id = block_stack.back();
   385	    block_stack.pop_back();
   386	  }
   387	
   388	  ModuleContext& mc;
   389	  std::vector<Node> exp_stack;
   390	  std::vector<Node> predecls;
   391	  const Func* f;
   392	  int value_stack_depth = 0;
   393	  struct Variable {
   394	    size_t block_id;
   395	    bool defined;
   396	  };
   397	  std::map<std::string, Variable> vars_defined;
   398	  Index flushed_vars = 0;
   399	  size_t cur_block_id = 0;
   400	  std::vector<size_t> block_stack;
   401	  std::vector<bool> blocks_closed;
   402	};
   403	
   404	}  // namespace wabt
   405	
   406	#endif  // WABT_DECOMPILER_AST_H_