[wasm] Add loop assignment analysis.

src/wasm/ast-decoder.cc

 // Copyright 2015 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/base/platform/elapsed-timer.h"
 #include "src/signature.h"
 
+#include "src/bit-vector.h"
 #include "src/flags.h"
 #include "src/handles.h"
 #include "src/zone-containers.h"
 
 #include "src/wasm/ast-decoder.h"
 #include "src/wasm/decoder.h"
 #include "src/wasm/wasm-module.h"
 #include "src/wasm/wasm-opcodes.h"
 
 #include "src/compiler/wasm-compiler.h"
@@ skipping 72 matching lines @@
 };
 
 
 // Macros that build nodes only if there is a graph and the current SSA
 // environment is reachable from start. This avoids problems with malformed
 // TF graphs when decoding inputs that have unreachable code.
 #define BUILD(func, ...) (build() ? builder_->func(__VA_ARGS__) : nullptr)
 #define BUILD0(func) (build() ? builder_->func() : nullptr)
 
 
+// Generic Wasm bytecode decoder with utilities for decoding operands,
+// lengths, etc.
+class WasmDecoder : public Decoder {
+ public:
+  WasmDecoder() : Decoder(nullptr, nullptr), function_env_(nullptr) {}

[bradnelson, 2016/01/22 06:28:33]

Are you planning to pull this out into it's own file once all the loose
functions with the TODO's are inside?

+
+ protected:
+  FunctionEnv* function_env_;
+
+  void Reset(FunctionEnv* function_env, const byte* start, const byte* end) {
+    Decoder::Reset(start, end);
+    function_env_ = function_env;
+  }
+
+  // Load an operand at [pc + 1].
+  template <typename V>
+  V Operand(const byte* pc) {
+    if ((limit_ - pc) < static_cast<int>(1 + sizeof(V))) {
+      const char* msg = "Expected operand following opcode";
+      switch (sizeof(V)) {
+        case 1:
+          msg = "Expected 1-byte operand following opcode";
+          break;
+        case 2:
+          msg = "Expected 2-byte operand following opcode";
+          break;
+        case 4:
+          msg = "Expected 4-byte operand following opcode";
+          break;
+        default:
+          break;
+      }
+      error(pc, msg);
+      return -1;
+    }
+    return *reinterpret_cast<const V*>(pc + 1);
+  }
+
+  LocalType LocalOperand(const byte* pc, uint32_t* index, int* length) {
+    *index = UnsignedLEB128Operand(pc, length);
+    if (function_env_->IsValidLocal(*index)) {
+      return function_env_->GetLocalType(*index);
+    }
+    error(pc, "invalid local variable index");
+    return kAstStmt;
+  }
+
+  LocalType GlobalOperand(const byte* pc, uint32_t* index, int* length) {
+    *index = UnsignedLEB128Operand(pc, length);
+    if (function_env_->module->IsValidGlobal(*index)) {
+      return WasmOpcodes::LocalTypeFor(
+          function_env_->module->GetGlobalType(*index));
+    }
+    error(pc, "invalid global variable index");
+    return kAstStmt;
+  }
+
+  FunctionSig* FunctionSigOperand(const byte* pc, uint32_t* index,
+                                  int* length) {
+    *index = UnsignedLEB128Operand(pc, length);
+    if (function_env_->module->IsValidFunction(*index)) {
+      return function_env_->module->GetFunctionSignature(*index);
+    }
+    error(pc, "invalid function index");
+    return nullptr;
+  }
+
+  FunctionSig* SigOperand(const byte* pc, uint32_t* index, int* length) {
+    *index = UnsignedLEB128Operand(pc, length);
+    if (function_env_->module->IsValidSignature(*index)) {
+      return function_env_->module->GetSignature(*index);
+    }
+    error(pc, "invalid signature index");
+    return nullptr;
+  }
+
+  uint32_t UnsignedLEB128Operand(const byte* pc, int* length) {
+    uint32_t result = 0;
+    ReadUnsignedLEB128ErrorCode error_code =
+        ReadUnsignedLEB128Operand(pc + 1, limit_, length, &result);
+    if (error_code == kInvalidLEB128) error(pc, "invalid LEB128 varint");
+    if (error_code == kMissingLEB128) error(pc, "expected LEB128 varint");
+    (*length)++;
+    return result;
+  }
+
+  void MemoryAccessOperand(const byte* pc, int* length, uint32_t* offset) {
+    byte bitfield = Operand<uint8_t>(pc);
+    if (MemoryAccess::OffsetField::decode(bitfield)) {
+      *offset = UnsignedLEB128Operand(pc + 1, length);
+      (*length)++;  // to account for the memory access byte
+    } else {
+      *offset = 0;
+      *length = 2;
+    }
+  }
+};
+
+
 // A shift-reduce-parser strategy for decoding Wasm code that uses an explicit
 // shift-reduce strategy with multiple internal stacks.
-class LR_WasmDecoder : public Decoder {
+class LR_WasmDecoder : public WasmDecoder {
  public:
   LR_WasmDecoder(Zone* zone, TFBuilder* builder)
-      : Decoder(nullptr, nullptr),
-        zone_(zone),
+      : zone_(zone),
         builder_(builder),
         trees_(zone),
         stack_(zone),
         blocks_(zone),
         ifs_(zone) {}
 
   TreeResult Decode(FunctionEnv* function_env, const byte* base, const byte* pc,
                     const byte* end) {
     base::ElapsedTimer decode_timer;
     if (FLAG_trace_wasm_decode_time) {
       decode_timer.Start();
     }
     trees_.clear();
     stack_.clear();
     blocks_.clear();
     ifs_.clear();
 
     if (end < pc) {
       error(pc, "function body end < start");
       return result_;
     }
 
     base_ = base;
-    Reset(pc, end);
-    function_env_ = function_env;
+    Reset(function_env, pc, end);
 
     InitSsaEnv();
     DecodeFunctionBody();
 
     Tree* tree = nullptr;
     if (ok()) {
       if (ssa_env_->go()) {
         if (stack_.size() > 0) {
           error(stack_.back().pc(), end, "fell off end of code");
         }
@@ skipping 28 matching lines @@
 
  private:
   static const size_t kErrorMsgSize = 128;
 
   Zone* zone_;
   TFBuilder* builder_;
   const byte* base_;
   TreeResult result_;
 
   SsaEnv* ssa_env_;
-  FunctionEnv* function_env_;
 
   ZoneVector<Tree*> trees_;
   ZoneVector<Production> stack_;
   ZoneVector<Block> blocks_;
   ZoneVector<IfEnv> ifs_;
 
   inline bool build() { return builder_ && ssa_env_->go(); }
 
   void InitSsaEnv() {
     FunctionSig* sig = function_env_->sig;
@@ skipping 1093 matching lines @@
   // Create an unreachable environment.
   SsaEnv* UnreachableEnv() {
     SsaEnv* result = reinterpret_cast<SsaEnv*>(zone_->New(sizeof(SsaEnv)));
     result->state = SsaEnv::kUnreachable;
     result->control = nullptr;
     result->effect = nullptr;
     result->locals = nullptr;
     return result;
   }
 
-  // Load an operand at [pc + 1].
-  template <typename V>
-  V Operand(const byte* pc) {
-    if ((limit_ - pc) < static_cast<int>(1 + sizeof(V))) {
-      const char* msg = "Expected operand following opcode";
-      switch (sizeof(V)) {
-        case 1:
-          msg = "Expected 1-byte operand following opcode";
-          break;
-        case 2:
-          msg = "Expected 2-byte operand following opcode";
-          break;
-        case 4:
-          msg = "Expected 4-byte operand following opcode";
-          break;
-        default:
-          break;
-      }
-      error(pc, msg);
-      return -1;
-    }
-    return *reinterpret_cast<const V*>(pc + 1);
-  }
-
   int EnvironmentCount() {
     if (builder_) return static_cast<int>(function_env_->GetLocalCount());
     return 0;  // if we aren't building a graph, don't bother with SSA renaming.
   }
 
-  LocalType LocalOperand(const byte* pc, uint32_t* index, int* length) {
-    *index = UnsignedLEB128Operand(pc, length);
-    if (function_env_->IsValidLocal(*index)) {
-      return function_env_->GetLocalType(*index);
-    }
-    error(pc, "invalid local variable index");
-    return kAstStmt;
-  }
-
-  LocalType GlobalOperand(const byte* pc, uint32_t* index, int* length) {
-    *index = UnsignedLEB128Operand(pc, length);
-    if (function_env_->module->IsValidGlobal(*index)) {
-      return WasmOpcodes::LocalTypeFor(
-          function_env_->module->GetGlobalType(*index));
-    }
-    error(pc, "invalid global variable index");
-    return kAstStmt;
-  }
-
-  FunctionSig* FunctionSigOperand(const byte* pc, uint32_t* index,
-                                  int* length) {
-    *index = UnsignedLEB128Operand(pc, length);
-    if (function_env_->module->IsValidFunction(*index)) {
-      return function_env_->module->GetFunctionSignature(*index);
-    }
-    error(pc, "invalid function index");
-    return nullptr;
-  }
-
-  FunctionSig* SigOperand(const byte* pc, uint32_t* index, int* length) {
-    *index = UnsignedLEB128Operand(pc, length);
-    if (function_env_->module->IsValidSignature(*index)) {
-      return function_env_->module->GetSignature(*index);
-    }
-    error(pc, "invalid signature index");
-    return nullptr;
-  }
-
-  uint32_t UnsignedLEB128Operand(const byte* pc, int* length) {
-    uint32_t result = 0;
-    ReadUnsignedLEB128ErrorCode error_code =
-        ReadUnsignedLEB128Operand(pc + 1, limit_, length, &result);
-    if (error_code == kInvalidLEB128) error(pc, "invalid LEB128 varint");
-    if (error_code == kMissingLEB128) error(pc, "expected LEB128 varint");
-    (*length)++;
-    return result;
-  }
-
-  void MemoryAccessOperand(const byte* pc, int* length, uint32_t* offset) {
-    byte bitfield = Operand<uint8_t>(pc);
-    if (MemoryAccess::OffsetField::decode(bitfield)) {
-      *offset = UnsignedLEB128Operand(pc + 1, length);
-      (*length)++;  // to account for the memory access byte
-    } else {
-      *offset = 0;
-      *length = 2;
-    }
-  }
-
   virtual void onFirstError() {
     limit_ = start_;     // Terminate decoding loop.
     builder_ = nullptr;  // Don't build any more nodes.
 #if DEBUG
     PrintStackForDebugging();
 #endif
   }
 
 #if DEBUG
   void PrintStackForDebugging() { PrintProduction(0); }
@@ skipping 77 matching lines @@
   if (ptr == end && (b & 0x80)) {
     return kInvalidLEB128;
   } else if (*length == 0) {
     return kMissingLEB128;
   } else {
     return kNoError;
   }
 }
 
 
+// TODO(titzer): move this into WasmDecoder and bounds check accesses.
 int OpcodeLength(const byte* pc) {
   switch (static_cast<WasmOpcode>(*pc)) {
 #define DECLARE_OPCODE_CASE(name, opcode, sig) case kExpr##name:
     FOREACH_LOAD_MEM_OPCODE(DECLARE_OPCODE_CASE)
     FOREACH_STORE_MEM_OPCODE(DECLARE_OPCODE_CASE)
 #undef DECLARE_OPCODE_CASE
     {
       // Loads and stores have an optional offset.
       byte bitfield = pc[1];
       if (MemoryAccess::OffsetField::decode(bitfield)) {
@@ skipping 31 matching lines @@
       uint16_t table_count = *reinterpret_cast<const uint16_t*>(pc + 3);
       return 5 + table_count * 2;
     }
 
     default:
       return 1;
   }
 }
 
 
+// TODO(titzer): move this into WasmDecoder and bounds check accesses.
 int OpcodeArity(FunctionEnv* env, const byte* pc) {
 #define DECLARE_ARITY(name, ...)                          \
   static const LocalType kTypes_##name[] = {__VA_ARGS__}; \
   static const int kArity_##name =                        \
       static_cast<int>(arraysize(kTypes_##name) - 1);
 
   FOREACH_SIGNATURE(DECLARE_ARITY);
 #undef DECLARE_ARITY
 
   switch (static_cast<WasmOpcode>(*pc)) {
@@ skipping 48 matching lines @@
       FOREACH_STORE_MEM_OPCODE(DECLARE_OPCODE_CASE)
       FOREACH_MISC_MEM_OPCODE(DECLARE_OPCODE_CASE)
       FOREACH_SIMPLE_OPCODE(DECLARE_OPCODE_CASE)
 #undef DECLARE_OPCODE_CASE
   }
   UNREACHABLE();
   return 0;
 }
 
 
+
 void PrintAst(FunctionEnv* env, const byte* start, const byte* end) {
   const byte* pc = start;
   std::vector<int> arity_stack;
   while (pc < end) {
     int arity = OpcodeArity(env, pc);
     size_t length = OpcodeLength(pc);
 
     for (auto arity : arity_stack) {
       printf("  ");
       USE(arity);
     }
 
     WasmOpcode opcode = static_cast<WasmOpcode>(*pc);
     printf("k%s,", WasmOpcodes::OpcodeName(opcode));
 
     for (size_t i = 1; i < length; i++) {
       printf(" 0x%02x,", pc[i]);
     }
     pc += length;
     printf("\n");
 
     arity_stack.push_back(arity);
     while (arity_stack.back() == 0) {
       arity_stack.pop_back();
       if (arity_stack.empty()) break;
       arity_stack.back()--;
     }
   }
 }
+
+
+// Analyzes loop bodies for static assignments to locals, which helps in
+// reducing the number of phis introduced at loop headers.
+class LoopAssignmentAnalyzer : public WasmDecoder {
+ public:
+  LoopAssignmentAnalyzer(Zone* zone, FunctionEnv* function_env) : zone_(zone) {
+    function_env_ = function_env;
+  }
+
+  BitVector* Analyze(const byte* pc, const byte* limit) {
+    Decoder::Reset(pc, limit);
+    if (pc_ >= limit_) return nullptr;
+    if (*pc_ != kExprLoop) return nullptr;
+
+    BitVector* assigned =
+        new (zone_) BitVector(function_env_->total_locals, zone_);
+    // Keep a stack to model the nesting of expressions.
+    std::vector<int> arity_stack;
+    arity_stack.push_back(OpcodeArity(function_env_, pc_));
+    pc_ += OpcodeLength(pc_);
+
+    // Iteratively process all AST nodes nested inside the loop.
+    while (pc_ < limit_) {
+      WasmOpcode opcode = static_cast<WasmOpcode>(*pc_);
+      int arity = 0;
+      int length = 1;
+      if (opcode == kExprSetLocal) {
+        uint32_t index;
+        LocalOperand(pc_, &index, &length);
+        if (index < assigned->length()) assigned->Add(index);

[ahaas, 2016/01/22 06:53:26]

How could index >= assigned-length() even be possible? Wouldn't there be an
error in LocalOperand()?

[titzer, 2016/01/23 16:20:37]

This is because I plan to use it while decoding, when the decoder first hits the
kExprLoop bytecode. Thus this will run over unverified bytecode, which might
have errors. Also, LocalOperand() returns 0 on error, and there actually could
legally be 0 locals (which reminds me I should probably check that in the
decoder itself!).

+        arity = 1;

[bradnelson, 2016/01/22 06:28:33]

Why bake in the arity again?
Pull the else block out instead?

[titzer, 2016/01/23 16:20:37]

Ah, just a micro-optimization.

+      } else {
+        arity = OpcodeArity(function_env_, pc_);
+        length = OpcodeLength(pc_);
+      }
+
+      pc_ += length;
+      arity_stack.push_back(arity);
+      while (arity_stack.back() == 0) {
+        arity_stack.pop_back();
+        if (arity_stack.empty()) return assigned;  // reached end of loop
+        arity_stack.back()--;
+      }
+    }
+    return assigned;

[bradnelson, 2016/01/22 06:28:33]

In a well formed program, shouldn't we always hit the return above?
A DCHECK here perhaps?

[titzer, 2016/01/23 16:20:37]

As mentioned above, I'm assuming not assuming the loop body is well-formed.

+  }
+
+ private:
+  Zone* zone_;
+};
+
+
+BitVector* AnalyzeLoopAssignmentForTesting(Zone* zone, FunctionEnv* env,
+                                           const byte* start, const byte* end) {
+  LoopAssignmentAnalyzer analyzer(zone, env);
+  return analyzer.Analyze(start, end);
+}
+
 }  // namespace wasm
 }  // namespace internal
 }  // namespace v8