SSA pass (#1049)

 * Add SSA pass which ensures a single assign for each local, except for merged locals where we ensure exactly a single assign from one of the paths leading to that use

 * Also add InstrumentLocals pass, useful for debugging locals (similar to InstrumentMemory but for locals)

 * Fix a PickLoadSigns bug with tees not being ignored, which was not noticed until now because we ran it on flatter output by default, but the ssa pass uncovered the bug

13 files changed, 698 insertions, 29 deletions

diff --git a/src/asm2wasm.h b/src/asm2wasm.h
index b8439bdbf..f6d0443ec 100644
--- a/src/asm2wasm.h
+++ b/src/asm2wasm.h
@@ -1162,6 +1162,9 @@ void Asm2WasmBuilder::processAsm(Ref ast) {
     } else if (curr[0] == DEFUN) {
       // function
       auto* func = processFunction(curr);
+      if (wasm.getFunctionOrNull(func->name)) {
+        Fatal() << "duplicate function: " << func->name;
+      }
       if (runOptimizationPasses) {
         optimizingBuilder->addFunction(func);
       } else {
diff --git a/src/ast/literal-utils.h b/src/ast/literal-utils.h
new file mode 100644
index 000000000..7e75e8bc8
--- /dev/null
+++ b/src/ast/literal-utils.h
@@ -0,0 +1,46 @@
+/*
+ * Copyright 2017 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 wasm_ast_literl_utils_h
+#define wasm_ast_literl_utils_h
+
+#include "wasm.h"
+
+namespace wasm {
+
+namespace LiteralUtils {
+
+inline Expression* makeZero(WasmType type, Module& wasm) {
+  Literal value;
+  switch (type) {
+    case i32: value = Literal(int32_t(0)); break;
+    case i64: value = Literal(int64_t(0)); break;
+    case f32: value = Literal(float(0)); break;
+    case f64: value = Literal(double(0)); break;
+    default: WASM_UNREACHABLE();
+  }
+  auto* ret = wasm.allocator.alloc<Const>();
+  ret->value = value;
+  ret->type = value.type;
+  return ret;
+}
+
+} // namespace LiteralUtils
+
+} // namespace wasm
+
+#endif // wasm_ast_literl_utils_h
+
diff --git a/src/passes/CMakeLists.txt b/src/passes/CMakeLists.txt
index 66f86a02f..f1411f190 100644
--- a/src/passes/CMakeLists.txt
+++ b/src/passes/CMakeLists.txt
@@ -10,6 +10,7 @@ SET(passes_SOURCES
   LegalizeJSInterface.cpp
   LocalCSE.cpp
   LogExecution.cpp
+  InstrumentLocals.cpp
   InstrumentMemory.cpp
   MemoryPacking.cpp
   MergeBlocks.cpp
@@ -32,6 +33,7 @@ SET(passes_SOURCES
   ReorderLocals.cpp
   ReorderFunctions.cpp
   SimplifyLocals.cpp
+  SSAify.cpp
   Vacuum.cpp
 )
 ADD_LIBRARY(passes STATIC ${passes_SOURCES})
diff --git a/src/passes/CoalesceLocals.cpp b/src/passes/CoalesceLocals.cpp
index 2828c9955..fb81a5981 100644
--- a/src/passes/CoalesceLocals.cpp
+++ b/src/passes/CoalesceLocals.cpp
@@ -32,6 +32,7 @@
 #include "cfg/cfg-traversal.h"
 #include "wasm-builder.h"
 #include "support/learning.h"
+#include "support/permutations.h"
 #ifdef CFG_PROFILE
 #include "support/timing.h"
 #endif
@@ -533,35 +534,6 @@ void CoalesceLocals::pickIndicesFromOrder(std::vector<Index>& order, std::vector
   }
 }
 
-// Utilities for operating on permutation vectors
-
-static std::vector<Index> makeIdentity(Index num) {
-  std::vector<Index> ret;
-  ret.resize(num);
-  for (Index i = 0; i < num; i++) {
-    ret[i] = i;
-  }
-  return ret;
-}
-
-static void setIdentity(std::vector<Index>& ret) {
-  auto num = ret.size();
-  assert(num > 0); // must already be of the right size
-  for (Index i = 0; i < num; i++) {
-    ret[i] = i;
-  }
-}
-
-static std::vector<Index> makeReversed(std::vector<Index>& original) {
-  std::vector<Index> ret;
-  auto num = original.size();
-  ret.resize(num);
-  for (Index i = 0; i < num; i++) {
-    ret[original[i]] = i;
-  }
-  return ret;
-}
-
 // given a baseline order, adjust it based on an important order of priorities (higher values
 // are higher priority). The priorities take precedence, unless they are equal and then
 // the original order should be kept.
diff --git a/src/passes/InstrumentLocals.cpp b/src/passes/InstrumentLocals.cpp
new file mode 100644
index 000000000..22b8ebf70
--- /dev/null
+++ b/src/passes/InstrumentLocals.cpp
@@ -0,0 +1,140 @@
+/*
+ * Copyright 2017 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.
+ */
+
+//
+// Instruments the build with code to intercept all local reads and writes.
+//
+// gets:
+//
+//  Before:
+//   (get_local $x)
+//
+//  After:
+//    (call $get_TYPE
+//     (i32.const n) // call id
+//     (i32.const n) // local id
+//     (get_local $x)
+//    )
+//
+// sets:
+//
+//  Before:
+//   (set_local $x (i32.const 1))
+//
+//  After:
+//   (set_local $x
+//    (call $set_TYPE
+//     (i32.const n) // call id
+//     (i32.const n) // local id
+//     (i32.const 1) // value
+//    )
+//   )
+
+#include <wasm.h>
+#include <wasm-builder.h>
+#include <pass.h>
+#include "shared-constants.h"
+#include "asmjs/shared-constants.h"
+#include "asm_v_wasm.h"
+
+namespace wasm {
+
+Name get_i32("get_i32");
+Name get_i64("get_i64");
+Name get_f32("get_f32");
+Name get_f64("get_f64");
+
+Name set_i32("set_i32");
+Name set_i64("set_i64");
+Name set_f32("set_f32");
+Name set_f64("set_f64");
+
+struct InstrumentLocals : public WalkerPass<PostWalker<InstrumentLocals>> {
+  void visitGetLocal(GetLocal* curr) {
+    Builder builder(*getModule());
+    Name import;
+    switch (curr->type) {
+      case i32: import = get_i32; break;
+      case i64: return; // TODO
+      case f32: import = get_f32; break;
+      case f64: import = get_f64; break;
+      default: WASM_UNREACHABLE();
+    }
+    replaceCurrent(
+      builder.makeCallImport(
+        import,
+        {
+          builder.makeConst(Literal(int32_t(id++))),
+          builder.makeConst(Literal(int32_t(curr->index))),
+          curr
+        },
+        curr->type
+      )
+    );
+  }
+
+  void visitSetLocal(SetLocal* curr) {
+    Builder builder(*getModule());
+    Name import;
+    switch (curr->value->type) {
+      case i32: import = set_i32; break;
+      case i64: return; // TODO
+      case f32: import = set_f32; break;
+      case f64: import = set_f64; break;
+      case unreachable: return; // nothing to do here
+      default: WASM_UNREACHABLE();
+    }
+    curr->value = builder.makeCallImport(
+      import,
+      {
+        builder.makeConst(Literal(int32_t(id++))),
+        builder.makeConst(Literal(int32_t(curr->index))),
+        curr->value
+      },
+      curr->value->type
+    );
+  }
+
+  void visitModule(Module* curr) {
+    addImport(curr, get_i32,  "iiii");
+    addImport(curr, get_i64,  "jiij");
+    addImport(curr, get_f32,  "fiif");
+    addImport(curr, get_f64,  "diid");
+    addImport(curr, set_i32,  "iiii");
+    addImport(curr, set_i64,  "jiij");
+    addImport(curr, set_f32,  "fiif");
+    addImport(curr, set_f64,  "diid");
+  }
+
+private:
+  Index id = 0;
+
+  void addImport(Module* wasm, Name name, std::string sig) {
+    auto import = new Import;
+    import->name = name;
+    import->module = INSTRUMENT;
+    import->base = name;
+    import->functionType = ensureFunctionType(sig, wasm)->name;
+    import->kind = ExternalKind::Function;
+    wasm->addImport(import);
+  }
+};
+
+Pass* createInstrumentLocalsPass() {
+  return new InstrumentLocals();
+}
+
+} // namespace wasm
diff --git a/src/passes/PickLoadSigns.cpp b/src/passes/PickLoadSigns.cpp
index 6ead0cc4e..d7947960c 100644
--- a/src/passes/PickLoadSigns.cpp
+++ b/src/passes/PickLoadSigns.cpp
@@ -94,6 +94,10 @@ struct PickLoadSigns : public WalkerPass<ExpressionStackWalker<PickLoadSigns>> {
   }
 
   void visitSetLocal(SetLocal* curr) {
+    if (curr->isTee()) {
+      // we can't modify a tee, the value is used elsewhere
+      return;
+    }
     if (auto* load = curr->value->dynCast<Load>()) {
       loads[load] = curr->index;
     }
diff --git a/src/passes/SSAify.cpp b/src/passes/SSAify.cpp
new file mode 100644
index 000000000..9c9aeb573
--- /dev/null
+++ b/src/passes/SSAify.cpp
@@ -0,0 +1,395 @@
+/*
+ * 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.
+ */
+
+//
+// Transforms code into SSA form. That ensures each variable has a
+// single assignment.
+//
+// Note that "SSA form" usually means SSA + phis. This pass does not
+// create phis, we still emit something in our AST, which does not
+// have a phi instruction. What we emit when control flow joins
+// require more than one input to a value is multiple assignments
+// to the same local, with the SSA guarantee that one and only one
+// of those assignments will arrive at the uses of that "merge local".
+// TODO: consider adding a "proper" phi node to the AST, that passes
+//       can utilize
+//
+
+#include <iterator>
+
+#include "wasm.h"
+#include "pass.h"
+#include "wasm-builder.h"
+#include "support/permutations.h"
+#include "ast/literal-utils.h"
+
+namespace wasm {
+
+// A set we know is impossible / not in the ast
+SetLocal IMPOSSIBLE_SET;
+
+// Tracks assignments to locals, assuming single-assignment form, i.e.,
+// each assignment creates a new variable.
+
+struct SSAify : public WalkerPass<PostWalker<SSAify>> {
+  bool isFunctionParallel() override { return true; }
+
+  Pass* create() override { return new SSAify; }
+
+  // the set_locals relevant for an index or a get. we use
+  // as set as merges of control flow mean more than 1 may
+  // be relevant; we create a phi on demand when necessary for those
+  typedef std::set<SetLocal*> Sets;
+
+  // we map (old local index) => the set_locals for that index.
+  // a nullptr set means there is a virtual set, from a param
+  // initial value or the zero init initial value.
+  typedef std::vector<Sets> Mapping;
+
+  Index numLocals;
+  Mapping currMapping;
+  Index nextIndex;
+  std::vector<Mapping> mappingStack; // used in ifs, loops
+  std::map<Name, std::vector<Mapping>> breakMappings; // break target => infos that reach it
+  std::vector<std::vector<GetLocal*>> loopGetStack; //  stack of loops, all the gets in each, so we can update them for back branches
+  std::vector<Expression*> functionPrepends; // things we add to the function prologue
+  std::map<GetLocal*, Sets> getSetses; // the sets for each get
+  std::map<GetLocal*, Expression**> getLocations;
+
+  void doWalkFunction(Function* func) {
+    numLocals = func->getNumLocals();
+    if (numLocals == 0) return; // nothing to do
+    // We begin with each param being assigned from the incoming value, and the zero-init for the locals,
+    // so the initial state is the identity permutation
+    currMapping.resize(numLocals);
+    for (auto& set : currMapping) {
+      set = { nullptr };
+    }
+    nextIndex = numLocals;
+    WalkerPass<PostWalker<SSAify>>::walk(func->body);
+    // apply - we now know the sets for each get
+    computeGetsAndPhis();
+    // add prepends
+    if (functionPrepends.size() > 0) {
+      Builder builder(*getModule());
+      auto* block = builder.makeBlock();
+      for (auto* pre : functionPrepends) {
+        block->list.push_back(pre);
+      }
+      block->list.push_back(func->body);
+      block->finalize(func->body->type);
+      func->body = block;
+    }
+  }
+
+  // control flow
+
+  void visitBlock(Block* curr) {
+    if (curr->name.is() && breakMappings.find(curr->name) != breakMappings.end()) {
+      auto& infos = breakMappings[curr->name];
+      infos.emplace_back(std::move(currMapping));
+      currMapping = std::move(merge(infos));
+      breakMappings.erase(curr->name);
+    }
+  }
+
+  void finishIf() {
+    // that's it for this if, merge
+    std::vector<Mapping> breaks;
+    breaks.emplace_back(std::move(currMapping));
+    breaks.emplace_back(std::move(mappingStack.back()));
+    mappingStack.pop_back();
+    currMapping = std::move(merge(breaks));
+  }
+
+  static void afterIfCondition(SSAify* self, Expression** currp) {
+    self->mappingStack.push_back(self->currMapping);
+  }
+  static void afterIfTrue(SSAify* self, Expression** currp) {
+    auto* curr = (*currp)->cast<If>();
+    if (curr->ifFalse) {
+      auto afterCondition = std::move(self->mappingStack.back());
+      self->mappingStack.back() = std::move(self->currMapping);
+      self->currMapping = std::move(afterCondition);
+    } else {
+      self->finishIf();
+    }
+  }
+  static void afterIfFalse(SSAify* self, Expression** currp) {
+    self->finishIf();
+  }
+  static void beforeLoop(SSAify* self, Expression** currp) {
+    // save the state before entering the loop, for calculation later of the merge at the loop top
+    self->mappingStack.push_back(self->currMapping);
+    self->loopGetStack.push_back({});
+  }
+  void visitLoop(Loop* curr) {
+    if (curr->name.is() && breakMappings.find(curr->name) != breakMappings.end()) {
+      auto& infos = breakMappings[curr->name];
+      infos.emplace_back(std::move(mappingStack.back()));
+      auto before = infos.back();
+      auto& merged = merge(infos);
+      // every local we created a phi for requires us to update get_local operations in
+      // the loop - the branch back has means that gets in the loop have potentially
+      // more sets reaching them.
+      // we can detect this as follows: if a get of oldIndex has the same sets
+      // as the sets at the entrance to the loop, then it is affected by the loop
+      // header sets, and we can add to there sets that looped back
+      auto linkLoopTop = [&](Index i, Sets& getSets) {
+        auto& beforeSets = before[i];
+        if (getSets.size() < beforeSets.size()) {
+          // the get trivially has fewer sets, so it overrode the loop entry sets
+          return;
+        }
+        std::vector<SetLocal*> intersection;
+        std::set_intersection(beforeSets.begin(), beforeSets.end(),
+                              getSets.begin(), getSets.end(),
+                              std::back_inserter(intersection));
+        if (intersection.size() < beforeSets.size()) {
+          // the get has not the same sets as in the loop entry
+          return;
+        }
+        // the get has the entry sets, so add any new ones
+        for (auto* set : merged[i]) {
+          getSets.insert(set);
+        }
+      };
+      auto& gets = loopGetStack.back();
+      for (auto* get : gets) {
+        linkLoopTop(get->index, getSetses[get]);
+      }
+      // and the same for the loop fallthrough: any local that still has the
+      // entry sets should also have the loop-back sets as well
+      for (Index i = 0; i < numLocals; i++) {
+        linkLoopTop(i, currMapping[i]);
+      }
+      // finally, breaks still in flight must be updated too
+      for (auto& iter : breakMappings) {
+        auto name = iter.first;
+        if (name == curr->name) continue; // skip our own (which is still in use)
+        auto& mappings = iter.second;
+        for (auto& mapping : mappings) {
+          for (Index i = 0; i < numLocals; i++) {
+            linkLoopTop(i, mapping[i]);
+          }
+        }
+      }
+      // now that we are done with using the mappings, erase our own
+      breakMappings.erase(curr->name);
+    }
+    mappingStack.pop_back();
+    loopGetStack.pop_back();
+  }
+  void visitBreak(Break* curr) {
+    if (curr->condition) {
+      breakMappings[curr->name].emplace_back(currMapping);
+    } else {
+      breakMappings[curr->name].emplace_back(std::move(currMapping));
+      setUnreachable(currMapping);
+    }
+  }
+  void visitSwitch(Switch* curr) {
+    std::set<Name> all;
+    for (auto target : curr->targets) {
+      all.insert(target);
+    }
+    all.insert(curr->default_);
+    for (auto target : all) {
+      breakMappings[target].emplace_back(currMapping);
+    }
+    setUnreachable(currMapping);
+  }
+  void visitReturn(Return *curr) {
+    setUnreachable(currMapping);
+  }
+  void visitUnreachable(Unreachable *curr) {
+    setUnreachable(currMapping);
+  }
+
+  // local usage
+
+  void visitGetLocal(GetLocal* curr) {
+    assert(currMapping.size() == numLocals);
+    assert(curr->index < numLocals);
+    for (auto& loopGets : loopGetStack) {
+      loopGets.push_back(curr);
+    }
+    // current sets are our sets
+    getSetses[curr] = currMapping[curr->index];
+    getLocations[curr] = getCurrentPointer();
+  }
+  void visitSetLocal(SetLocal* curr) {
+    assert(currMapping.size() == numLocals);
+    assert(curr->index < numLocals);
+    // current sets are just this set
+    currMapping[curr->index] = { curr }; // TODO optimize?
+    curr->index = addLocal(getFunction()->getLocalType(curr->index));
+  }
+
+  // traversal
+
+  static void scan(SSAify* self, Expression** currp) {
+    if (auto* iff = (*currp)->dynCast<If>()) {
+      // if needs special handling
+      if (iff->ifFalse) {
+        self->pushTask(SSAify::afterIfFalse, currp);
+        self->pushTask(SSAify::scan, &iff->ifFalse);
+      }
+      self->pushTask(SSAify::afterIfTrue, currp);
+      self->pushTask(SSAify::scan, &iff->ifTrue);
+      self->pushTask(SSAify::afterIfCondition, currp);
+      self->pushTask(SSAify::scan, &iff->condition);
+    } else {
+      WalkerPass<PostWalker<SSAify>>::scan(self, currp);
+    }
+
+    // loops need pre-order visiting too
+    if ((*currp)->is<Loop>()) {
+      self->pushTask(SSAify::beforeLoop, currp);
+    }
+  }
+
+  // helpers
+
+  void setUnreachable(Mapping& mapping) {
+    mapping.resize(numLocals); // may have been emptied by a move
+    mapping[0].clear();
+  }
+
+  bool isUnreachable(Mapping& mapping) {
+    // we must have some set for each index, if only the zero init, so empty means we emptied it for unreachable code
+    return mapping[0].empty();
+  }
+
+  // merges a bunch of infos into one.
+  // if we need phis, writes them into the provided vector. the caller should
+  // ensure those are placed in the right location
+  Mapping& merge(std::vector<Mapping>& mappings) {
+    assert(mappings.size() > 0);
+    auto& out = mappings[0];
+    if (mappings.size() == 1) {
+      return out;
+    }
+    // merge into the first
+    for (Index j = 1; j < mappings.size(); j++) {
+      auto& other = mappings[j];
+      for (Index i = 0; i < numLocals; i++) {
+        auto& outSets = out[i];
+        for (auto* set : other[i]) {
+          outSets.insert(set);
+        }
+      }
+    }
+    return out;
+  }
+
+  // After we traversed it all, we can compute gets and phis
+  void computeGetsAndPhis() {
+    for (auto& iter : getSetses) {
+      auto* get = iter.first;
+      auto& sets = iter.second;
+      if (sets.size() == 0) {
+        continue; // unreachable, ignore
+      }
+      if (sets.size() == 1) {
+        // TODO: add tests for this case
+        // easy, just one set, use it's index
+        auto* set = *sets.begin();
+        if (set) {
+          get->index = set->index;
+        } else {
+          // no set, assign param or zero
+          if (getFunction()->isParam(get->index)) {
+            // leave it, it's fine
+          } else {
+            // zero it out
+            (*getLocations[get]) = LiteralUtils::makeZero(get->type, *getModule());
+          }
+        }
+        continue;
+      }
+      // more than 1 set, need a phi: a new local written to at each of the sets
+      // if there is already a local with that property, reuse it
+      auto gatherIndexes = [](SetLocal* set) {
+        std::set<Index> ret;
+        while (set) {
+          ret.insert(set->index);
+          set = set->value->dynCast<SetLocal>();
+        }
+        return ret;
+      };
+      auto indexes = gatherIndexes(*sets.begin());
+      for (auto* set : sets) {
+        if (set == *sets.begin()) continue;
+        auto currIndexes = gatherIndexes(set);
+        std::vector<Index> intersection;
+        std::set_intersection(indexes.begin(), indexes.end(),
+                              currIndexes.begin(), currIndexes.end(),
+                              std::back_inserter(intersection));
+        indexes.clear();
+        if (intersection.empty()) break;
+        // TODO: or keep sorted vectors?
+        for (Index i : intersection) {
+          indexes.insert(i);
+        }
+      }
+      if (!indexes.empty()) {
+        // we found an index, use it
+        get->index = *indexes.begin();
+      } else {
+        // we need to create a local for this phi'ing
+        auto new_ = addLocal(get->type);
+        auto old = get->index;
+        get->index = new_;
+        Builder builder(*getModule());
+        // write to the local in each of our sets
+        for (auto* set : sets) {
+          if (set) {
+            // a set exists, just add a tee of its value
+            set->value = builder.makeTeeLocal(
+              new_,
+              set->value
+            );
+          } else {
+            // this is a param or the zero init value.
+            if (getFunction()->isParam(old)) {
+              // we add a set with the proper
+              // param value at the beginning of the function
+              auto* set = builder.makeSetLocal(
+                new_,
+                builder.makeGetLocal(old, getFunction()->getLocalType(old))
+              );
+              functionPrepends.push_back(set);
+            } else {
+              // this is a zero init, so we don't need to do anything actually
+            }
+          }
+        }
+      }
+    }
+  }
+
+  Index addLocal(WasmType type) {
+    return Builder::addVar(getFunction(), type);
+  }
+};
+
+Pass *createSSAifyPass() {
+  return new SSAify();
+}
+
+} // namespace wasm
+
diff --git a/src/passes/pass.cpp b/src/passes/pass.cpp
index 2fb0d5c3b..f494378cb 100644
--- a/src/passes/pass.cpp
+++ b/src/passes/pass.cpp
@@ -75,6 +75,7 @@ void PassRegistry::registerPasses() {
   registerPass("legalize-js-interface", "legalizes i64 types on the import/export boundary", createLegalizeJSInterfacePass);
   registerPass("local-cse", "common subexpression elimination inside basic blocks", createLocalCSEPass);
   registerPass("log-execution", "instrument the build with logging of where execution goes", createLogExecutionPass);
+  registerPass("instrument-locals", "instrument the build with code to intercept all loads and stores", createInstrumentLocalsPass);
   registerPass("instrument-memory", "instrument the build with code to intercept all loads and stores", createInstrumentMemoryPass);
   registerPass("memory-packing", "packs memory into separate segments, skipping zeros", createMemoryPackingPass);
   registerPass("merge-blocks", "merges blocks to their parents", createMergeBlocksPass);
@@ -101,6 +102,7 @@ void PassRegistry::registerPasses() {
   registerPass("simplify-locals-notee", "miscellaneous locals-related optimizations", createSimplifyLocalsNoTeePass);
   registerPass("simplify-locals-nostructure", "miscellaneous locals-related optimizations", createSimplifyLocalsNoStructurePass);
   registerPass("simplify-locals-notee-nostructure", "miscellaneous locals-related optimizations", createSimplifyLocalsNoTeeNoStructurePass);
+  registerPass("ssa", "ssa-ify variables so that they have a single assignment", createSSAifyPass);
   registerPass("vacuum", "removes obviously unneeded code", createVacuumPass);
   registerPass("precompute", "computes compile-time evaluatable expressions", createPrecomputePass);
 //  registerPass("lower-i64", "lowers i64 into pairs of i32s", createLowerInt64Pass);
diff --git a/src/passes/passes.h b/src/passes/passes.h
index 6322aad3c..e1ba286ad 100644
--- a/src/passes/passes.h
+++ b/src/passes/passes.h
@@ -34,6 +34,7 @@ Pass *createInliningPass();
 Pass *createLegalizeJSInterfacePass();
 Pass *createLocalCSEPass();
 Pass *createLogExecutionPass();
+Pass *createInstrumentLocalsPass();
 Pass *createInstrumentMemoryPass();
 Pass *createMemoryPackingPass();
 Pass *createMergeBlocksPass();
@@ -59,6 +60,7 @@ Pass *createSimplifyLocalsPass();
 Pass *createSimplifyLocalsNoTeePass();
 Pass *createSimplifyLocalsNoStructurePass();
 Pass *createSimplifyLocalsNoTeeNoStructurePass();
+Pass *createSSAifyPass();
 Pass *createVacuumPass();
 Pass *createPrecomputePass();
 //Pass *createLowerInt64Pass();
diff --git a/src/support/permutations.h b/src/support/permutations.h
new file mode 100644
index 000000000..214063058
--- /dev/null
+++ b/src/support/permutations.h
@@ -0,0 +1,55 @@
+/*
+ * 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.
+ */
+
+// Utilities for operating on permutation vectors
+
+#ifndef wasm_support_permutations_h
+#define wasm_support_permutations_h
+
+#include "wasm.h"
+
+namespace wasm {
+
+inline std::vector<Index> makeIdentity(Index num) {
+  std::vector<Index> ret;
+  ret.resize(num);
+  for (Index i = 0; i < num; i++) {
+    ret[i] = i;
+  }
+  return ret;
+}
+
+inline void setIdentity(std::vector<Index>& ret) {
+  auto num = ret.size();
+  assert(num > 0); // must already be of the right size
+  for (Index i = 0; i < num; i++) {
+    ret[i] = i;
+  }
+}
+
+inline std::vector<Index> makeReversed(std::vector<Index>& original) {
+  std::vector<Index> ret;
+  auto num = original.size();
+  ret.resize(num);
+  for (Index i = 0; i < num; i++) {
+    ret[original[i]] = i;
+  }
+  return ret;
+}
+
+} // namespace wasm
+
+#endif // permutations
diff --git a/src/tools/tool-utils.h b/src/tools/tool-utils.h
new file mode 100644
index 000000000..a897e01f0
--- /dev/null
+++ b/src/tools/tool-utils.h
@@ -0,0 +1,37 @@
+/*
+ * Copyright 2017 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.
+ */
+
+//
+// Shared utilities for commandline tools
+//
+
+#include <string>
+
+namespace wasm {
+
+// Removes a specific suffix if it is present, otherwise no-op
+inline std::string removeSpecificSuffix(std::string str, std::string suffix) {
+  if (str.size() <= suffix.size()) {
+    return str;
+  }
+  if (str.substr(str.size() - suffix.size()).compare(suffix) == 0) {
+    return str.substr(0, str.size() - suffix.size());
+  }
+  return str;
+}
+
+} // namespace wasm
+
diff --git a/src/tools/wasm-as.cpp b/src/tools/wasm-as.cpp
index e8003a5ca..d4b495562 100644
--- a/src/tools/wasm-as.cpp
+++ b/src/tools/wasm-as.cpp
@@ -24,6 +24,8 @@
 #include "wasm-binary.h"
 #include "wasm-s-parser.h"
 
+#include "tool-utils.h"
+
 using namespace cashew;
 using namespace wasm;
 
@@ -68,6 +70,11 @@ int main(int argc, const char *argv[]) {
                       });
   options.parse(argc, argv);
 
+  // default output is infile with changed suffix
+  if (options.extra.find("output") == options.extra.end()) {
+    options.extra["output"] = removeSpecificSuffix(options.extra["infile"], ".wast") + ".wasm";
+  }
+
   auto input(read_file<std::string>(options.extra["infile"], Flags::Text, options.debug ? Flags::Debug : Flags::Release));
 
   Module wasm;
diff --git a/src/wasm-traversal.h b/src/wasm-traversal.h
index f49407cad..aa8e008ad 100644
--- a/src/wasm-traversal.h
+++ b/src/wasm-traversal.h
@@ -164,6 +164,10 @@ struct Walker : public VisitorType {
     return *replacep;
   }
 
+  Expression** getCurrentPointer() {
+    return replacep;
+  }
+
   // Get the current module
   Module* getModule() {
     return currModule;