Adding upstream version 124.0.1.upstream/124.0.1

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 406 insertions, 0 deletions

diff --git a/third_party/wasm2c/include/wabt/decompiler-ast.h b/third_party/wasm2c/include/wabt/decompiler-ast.h
new file mode 100644
index 0000000000..33cc26c113
--- /dev/null
+++ b/third_party/wasm2c/include/wabt/decompiler-ast.h
@@ -0,0 +1,406 @@
+/*
+ * Copyright 2016 WebAssembly Community Group participants
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef WABT_DECOMPILER_AST_H_
+#define WABT_DECOMPILER_AST_H_
+
+#include "wabt/cast.h"
+#include "wabt/generate-names.h"
+#include "wabt/ir-util.h"
+#include "wabt/ir.h"
+
+#include <map>
+
+namespace wabt {
+
+enum class NodeType {
+  Uninitialized,
+  FlushToVars,
+  FlushedVar,
+  Statements,
+  EndReturn,
+  Decl,
+  DeclInit,
+  Expr
+};
+
+// The AST we're going to convert the standard IR into.
+struct Node {
+  NodeType ntype;
+  ExprType etype;  // Only if ntype == Expr.
+  const Expr* e;
+  std::vector<Node> children;
+  // Node specific annotations.
+  union {
+    struct {
+      Index var_start, var_count;  // FlushedVar/FlushToVars
+    };
+    const Var* var;  // Decl/DeclInit.
+    LabelType lt;    // br/br_if target.
+  } u;
+
+  Node() : ntype(NodeType::Uninitialized), etype(ExprType::Nop), e(nullptr) {}
+  Node(NodeType ntype, ExprType etype, const Expr* e, const Var* v)
+      : ntype(ntype), etype(etype), e(e) {
+    u.var = v;
+  }
+
+  // This value should really never be copied, only moved.
+  Node(const Node& rhs) = delete;
+  Node& operator=(const Node& rhs) = delete;
+
+  Node(Node&& rhs) { *this = std::move(rhs); }
+  Node& operator=(Node&& rhs) {
+    ntype = rhs.ntype;
+    // Reset ntype to avoid moved from values still being used.
+    rhs.ntype = NodeType::Uninitialized;
+    etype = rhs.etype;
+    rhs.etype = ExprType::Nop;
+    e = rhs.e;
+    std::swap(children, rhs.children);
+    u = rhs.u;
+    return *this;
+  }
+};
+
+struct AST {
+  AST(ModuleContext& mc, const Func* f) : mc(mc), f(f) {
+    if (f) {
+      mc.BeginFunc(*f);
+      for (Index i = 0; i < f->GetNumParams(); i++) {
+        auto name = "$" + IndexToAlphaName(i);
+        vars_defined.insert({name, {0, false}});
+      }
+    }
+  }
+
+  ~AST() {
+    if (f) {
+      mc.EndFunc();
+    }
+  }
+
+  // Create a new node, take nargs existing nodes on the exp stack as children.
+  Node& InsertNode(NodeType ntype, ExprType etype, const Expr* e, Index nargs) {
+    assert(exp_stack.size() >= nargs);
+    Node n{ntype, etype, e, nullptr};
+    n.children.reserve(nargs);
+    std::move(exp_stack.end() - nargs, exp_stack.end(),
+              std::back_inserter(n.children));
+    exp_stack.erase(exp_stack.end() - nargs, exp_stack.end());
+    exp_stack.push_back(std::move(n));
+    return exp_stack.back();
+  }
+
+  template <ExprType T>
+  void PreDecl(const VarExpr<T>& ve) {
+    // FIXME: this is slow, and would be better to avoid in callers.
+    // See https://github.com/WebAssembly/wabt/issues/1565
+    // And https://github.com/WebAssembly/wabt/issues/1665
+    for (auto& n : predecls) {
+      if (n.u.var->name() == ve.var.name()) {
+        return;
+      }
+    }
+    predecls.emplace_back(NodeType::Decl, ExprType::Nop, nullptr, &ve.var);
+  }
+
+  template <ExprType T>
+  void Get(const VarExpr<T>& ve, bool local) {
+    if (local) {
+      auto ret = vars_defined.insert({ve.var.name(), {cur_block_id, false}});
+      if (ret.second) {
+        // Use before def, may happen since locals are guaranteed 0.
+        PreDecl(ve);
+      } else if (blocks_closed[ret.first->second.block_id]) {
+        // This is a use of a variable that was defined in a block that has
+        // already ended. This happens rarely, but we should cater for this
+        // case by lifting it to the top scope.
+        PreDecl(ve);
+      }
+    }
+    InsertNode(NodeType::Expr, T, &ve, 0);
+  }
+
+  template <ExprType T>
+  void Set(const VarExpr<T>& ve, bool local) {
+    // Seen this var before?
+    if (local &&
+        vars_defined.insert({ve.var.name(), {cur_block_id, false}}).second) {
+      if (value_stack_depth == 1) {
+        // Top level, declare it here.
+        InsertNode(NodeType::DeclInit, ExprType::Nop, nullptr, 1).u.var =
+            &ve.var;
+        return;
+      } else {
+        // Inside exp, better leave it as assignment exp and lift the decl out.
+        PreDecl(ve);
+      }
+    }
+    InsertNode(NodeType::Expr, T, &ve, 1);
+  }
+
+  template <ExprType T>
+  void Block(const BlockExprBase<T>& be, LabelType label) {
+    mc.BeginBlock(label, be.block);
+    Construct(be.block.exprs, be.block.decl.GetNumResults(),
+              be.block.decl.GetNumParams(), false);
+    mc.EndBlock();
+    InsertNode(NodeType::Expr, T, &be, 1);
+  }
+
+  void Construct(const Expr& e) {
+    auto arity = mc.GetExprArity(e);
+    switch (e.type()) {
+      case ExprType::LocalGet: {
+        Get(*cast<LocalGetExpr>(&e), true);
+        return;
+      }
+      case ExprType::GlobalGet: {
+        Get(*cast<GlobalGetExpr>(&e), false);
+        return;
+      }
+      case ExprType::LocalSet: {
+        Set(*cast<LocalSetExpr>(&e), true);
+        return;
+      }
+      case ExprType::GlobalSet: {
+        Set(*cast<GlobalSetExpr>(&e), false);
+        return;
+      }
+      case ExprType::LocalTee: {
+        auto& lt = *cast<LocalTeeExpr>(&e);
+        Set(lt, true);
+        if (value_stack_depth == 1) {  // Tee is the only thing on there.
+          Get(lt, true);               // Now Set + Get instead.
+        } else {
+          // Things are above us on the stack so the Tee can't be eliminated.
+          // The Set makes this work as a Tee when consumed by a parent.
+        }
+        return;
+      }
+      case ExprType::If: {
+        auto ife = cast<IfExpr>(&e);
+        value_stack_depth--;  // Condition.
+        mc.BeginBlock(LabelType::Block, ife->true_);
+        Construct(ife->true_.exprs, ife->true_.decl.GetNumResults(),
+                  ife->true_.decl.GetNumParams(), false);
+        if (!ife->false_.empty()) {
+          Construct(ife->false_, ife->true_.decl.GetNumResults(),
+                    ife->true_.decl.GetNumParams(), false);
+        }
+        mc.EndBlock();
+        value_stack_depth++;  // Put Condition back.
+        InsertNode(NodeType::Expr, ExprType::If, &e,
+                   ife->false_.empty() ? 2 : 3);
+        return;
+      }
+      case ExprType::Block: {
+        Block(*cast<BlockExpr>(&e), LabelType::Block);
+        return;
+      }
+      case ExprType::Loop: {
+        Block(*cast<LoopExpr>(&e), LabelType::Loop);
+        return;
+      }
+      case ExprType::Br: {
+        InsertNode(NodeType::Expr, ExprType::Br, &e, 0).u.lt =
+            mc.GetLabel(cast<BrExpr>(&e)->var)->label_type;
+        return;
+      }
+      case ExprType::BrIf: {
+        InsertNode(NodeType::Expr, ExprType::BrIf, &e, 1).u.lt =
+            mc.GetLabel(cast<BrIfExpr>(&e)->var)->label_type;
+        return;
+      }
+      case ExprType::BrTable: {
+        InsertNode(NodeType::Expr, ExprType::BrTable, &e, 1).u.lt =
+            mc.GetLabel(cast<BrTableExpr>(&e)->default_target)->label_type;
+        return;
+      }
+      default: {
+        InsertNode(NodeType::Expr, e.type(), &e, arity.nargs);
+        return;
+      }
+    }
+  }
+
+  void Construct(const ExprList& es,
+                 Index nresults,
+                 Index nparams,
+                 bool is_function_body) {
+    block_stack.push_back(cur_block_id);
+    cur_block_id = blocks_closed.size();
+    blocks_closed.push_back(false);
+    auto start = exp_stack.size();
+    int value_stack_depth_start = value_stack_depth - nparams;
+    auto value_stack_in_variables = value_stack_depth;
+    bool unreachable = false;
+    for (auto& e : es) {
+      Construct(e);
+      auto arity = mc.GetExprArity(e);
+      value_stack_depth -= arity.nargs;
+      value_stack_in_variables =
+          std::min(value_stack_in_variables, value_stack_depth);
+      unreachable = unreachable || arity.unreachable;
+      assert(unreachable || value_stack_depth >= value_stack_depth_start);
+      value_stack_depth += arity.nreturns;
+      // We maintain the invariant that a value_stack_depth of N is represented
+      // by the last N exp_stack items (each of which returning exactly 1
+      // value), all exp_stack items before it return void ("statements").
+      // In particular for the wasm stack:
+      // - The values between 0 and value_stack_depth_start are part of the
+      //   parent block, and not touched here.
+      // - The values from there up to value_stack_in_variables are variables
+      //   to be used, representing previous statements that flushed the
+      //   stack into variables.
+      // - Values on top of that up to value_stack_depth are exps returning
+      //   a single value.
+      // The code below maintains the above invariants. With this in place
+      // code "falls into place" the way you expect it.
+      if (arity.nreturns != 1) {
+        auto num_vars = value_stack_in_variables - value_stack_depth_start;
+        auto num_vals = value_stack_depth - value_stack_in_variables;
+        auto GenFlushVars = [&](int nargs) {
+          auto& ftv =
+              InsertNode(NodeType::FlushToVars, ExprType::Nop, nullptr, nargs);
+          ftv.u.var_start = flushed_vars;
+          ftv.u.var_count = num_vals;
+        };
+        auto MoveStatementsBelowVars = [&](size_t amount) {
+          std::rotate(exp_stack.end() - num_vars - amount,
+                      exp_stack.end() - amount, exp_stack.end());
+        };
+        auto GenFlushedVars = [&]() {
+          // Re-generate these values as vars.
+          for (int i = 0; i < num_vals; i++) {
+            auto& fv =
+                InsertNode(NodeType::FlushedVar, ExprType::Nop, nullptr, 0);
+            fv.u.var_start = flushed_vars++;
+            fv.u.var_count = 1;
+          }
+        };
+        if (arity.nreturns == 0 &&
+            value_stack_depth > value_stack_depth_start) {
+          // We have a void item on top of the exp_stack, so we must "lift" the
+          // previous values around it.
+          // We track what part of the stack is in variables to avoid doing
+          // this unnecessarily.
+          if (num_vals > 0) {
+            // We have actual new values that need lifting.
+            // This puts the part of the stack that wasn't already a variable
+            // (before the current void exp) into a FlushToVars.
+            auto void_exp = std::move(exp_stack.back());
+            exp_stack.pop_back();
+            GenFlushVars(num_vals);
+            exp_stack.push_back(std::move(void_exp));
+            // Put this flush statement + void statement before any
+            // existing variables.
+            MoveStatementsBelowVars(2);
+            // Now re-generate these values after the void exp as vars.
+            GenFlushedVars();
+          } else {
+            // We have existing variables that need lifting, but no need to
+            // create them anew.
+            std::rotate(exp_stack.end() - num_vars - 1, exp_stack.end() - 1,
+                        exp_stack.end());
+          }
+          value_stack_in_variables = value_stack_depth;
+        } else if (arity.nreturns > 1) {
+          // Multivalue: we flush the stack also.
+          // Number of other non-variable values that may be present:
+          assert(num_vals >= static_cast<int>(arity.nreturns));
+          // Flush multi-value exp + others.
+          GenFlushVars(num_vals - arity.nreturns + 1);
+          // Put this flush statement before any existing variables.
+          MoveStatementsBelowVars(1);
+          GenFlushedVars();
+          value_stack_in_variables = value_stack_depth;
+        }
+      } else {
+        // Special optimisation: for constant instructions, we can mark these
+        // as if they were variables, so they can be re-ordered for free with
+        // the above code, without needing new variables!
+        // TODO: this would be nice to also do for local.get and maybe others,
+        // though that needs a way to ensure there's no local.set in between
+        // when they get lifted, so complicates matters a bit.
+        if (e.type() == ExprType::Const &&
+            value_stack_in_variables == value_stack_depth - 1) {
+          value_stack_in_variables++;
+        }
+      }
+    }
+    assert(unreachable || value_stack_depth - value_stack_depth_start ==
+                              static_cast<int>(nresults));
+    // Undo any changes to value_stack_depth, since parent takes care of arity
+    // changes.
+    value_stack_depth = value_stack_depth_start;
+    auto end = exp_stack.size();
+    assert(end >= start);
+    if (is_function_body) {
+      if (!exp_stack.empty()) {
+        if (exp_stack.back().etype == ExprType::Return) {
+          if (exp_stack.back().children.empty()) {
+            // Return statement at the end of a void function.
+            exp_stack.pop_back();
+          }
+        } else if (nresults) {
+          // Combine nresults into a return statement, for when this is used as
+          // a function body.
+          // TODO: if this is some other kind of block and >1 value is being
+          // returned, probably need some kind of syntax to make that clearer.
+          InsertNode(NodeType::EndReturn, ExprType::Nop, nullptr, nresults);
+        }
+      }
+      // TODO: these predecls are always at top level, but in the case of
+      // use inside an exp, it be nice to do it in the current block. Can't
+      // do that for predecls that are "out if scope" however.
+      std::move(predecls.begin(), predecls.end(),
+                std::back_inserter(exp_stack));
+      std::rotate(exp_stack.begin(), exp_stack.end() - predecls.size(),
+                  exp_stack.end());
+      predecls.clear();
+    }
+    end = exp_stack.size();
+    assert(end >= start);
+    auto size = end - start;
+    if (size != 1) {
+      InsertNode(NodeType::Statements, ExprType::Nop, nullptr, size);
+    }
+    blocks_closed[cur_block_id] = true;
+    cur_block_id = block_stack.back();
+    block_stack.pop_back();
+  }
+
+  ModuleContext& mc;
+  std::vector<Node> exp_stack;
+  std::vector<Node> predecls;
+  const Func* f;
+  int value_stack_depth = 0;
+  struct Variable {
+    size_t block_id;
+    bool defined;
+  };
+  std::map<std::string, Variable> vars_defined;
+  Index flushed_vars = 0;
+  size_t cur_block_id = 0;
+  std::vector<size_t> block_stack;
+  std::vector<bool> blocks_closed;
+};
+
+}  // namespace wabt
+
+#endif  // WABT_DECOMPILER_AST_H_