Require unique names in binaryen IR (#746)

6 files changed, 167 insertions, 65 deletions

diff --git a/src/asm2wasm.h b/src/asm2wasm.h
index d9618d8fd..acf973a69 100644
--- a/src/asm2wasm.h
+++ b/src/asm2wasm.h
@@ -30,6 +30,7 @@
 #include "asm_v_wasm.h"
 #include "passes/passes.h"
 #include "pass.h"
+#include "parsing.h"
 #include "ast_utils.h"
 #include "wasm-builder.h"
 #include "wasm-emscripten.h"
@@ -1106,17 +1107,14 @@ Function* Asm2WasmBuilder::processFunction(Ref ast) {
   Ref params = ast[2];
   Ref body = ast[3];
 
-  unsigned nextId = 0;
-  auto getNextId = [&nextId](std::string prefix) {
-    return IString((prefix + '$' + std::to_string(nextId++)).c_str(), false);
-  };
+  UniqueNameMapper nameMapper;
 
   // given an asm.js label, returns the wasm label for breaks or continues
   auto getBreakLabelName = [](IString label) {
-    return IString((std::string("label$break$") + label.str).c_str(), false);
+    return Name(std::string("label$break$") + label.str);
   };
   auto getContinueLabelName = [](IString label) {
-    return IString((std::string("label$continue$") + label.str).c_str(), false);
+    return Name(std::string("label$continue$") + label.str);
   };
 
   IStringSet functionVariables; // params or vars
@@ -1705,13 +1703,14 @@ Function* Asm2WasmBuilder::processFunction(Ref ast) {
     } else if (what == BLOCK) {
       Name name;
       if (parentLabel.is()) {
-        name = getBreakLabelName(parentLabel);
+        name = nameMapper.pushLabelName(getBreakLabelName(parentLabel));
         parentLabel = IString();
         breakStack.push_back(name);
       }
       auto ret = processStatements(ast[1], 0);
       if (name.is()) {
         breakStack.pop_back();
+        nameMapper.popLabelName(name);
         Block* block = ret->dynCast<Block>();
         if (block && block->name.isNull()) {
           block->name = name;
@@ -1727,12 +1726,12 @@ Function* Asm2WasmBuilder::processFunction(Ref ast) {
     } else if (what == BREAK) {
       auto ret = allocator.alloc<Break>();
       assert(breakStack.size() > 0);
-      ret->name = !!ast[1] ? getBreakLabelName(ast[1]->getIString()) : breakStack.back();
+      ret->name = !!ast[1] ? nameMapper.sourceToUnique(getBreakLabelName(ast[1]->getIString())) : breakStack.back();
       return ret;
     } else if (what == CONTINUE) {
       auto ret = allocator.alloc<Break>();
       assert(continueStack.size() > 0);
-      ret->name = !!ast[1] ? getContinueLabelName(ast[1]->getIString()) : continueStack.back();
+      ret->name = !!ast[1] ? nameMapper.sourceToUnique(getContinueLabelName(ast[1]->getIString())) : continueStack.back();
       return ret;
     } else if (what == WHILE) {
       bool forever = ast[1][0] == NUM && ast[1][1]->getInteger() == 1;
@@ -1743,9 +1742,11 @@ Function* Asm2WasmBuilder::processFunction(Ref ast) {
         in = getContinueLabelName(parentLabel);
         parentLabel = IString();
       } else {
-        out = getNextId("while-out");
-        in = getNextId("while-in");
+        out = "while-out";
+        in = "while-in";
       }
+      out = nameMapper.pushLabelName(out);
+      in = nameMapper.pushLabelName(in);
       ret->name = in;
       breakStack.push_back(out);
       continueStack.push_back(in);
@@ -1774,6 +1775,8 @@ Function* Asm2WasmBuilder::processFunction(Ref ast) {
       ret->finalize();
       continueStack.pop_back();
       breakStack.pop_back();
+      nameMapper.popLabelName(in);
+      nameMapper.popLabelName(out);
       return ret;
     } else if (what == DO) {
       if (ast[1][0] == NUM && ast[1][1]->getNumber() == 0) {
@@ -1783,14 +1786,17 @@ Function* Asm2WasmBuilder::processFunction(Ref ast) {
           stop = getBreakLabelName(parentLabel);
           parentLabel = IString();
         } else {
-          stop = getNextId("do-once");
+          stop = "do-once";
         }
-        IString more = getNextId("unlikely-continue");
+        stop = nameMapper.pushLabelName(stop);
+        Name more = nameMapper.pushLabelName("unlikely-continue");
         breakStack.push_back(stop);
         continueStack.push_back(more);
         auto child = process(ast[2]);
         continueStack.pop_back();
         breakStack.pop_back();
+        nameMapper.popLabelName(more);
+        nameMapper.popLabelName(stop);
         // if we never continued, we don't need a loop
         BreakSeeker breakSeeker(more);
         breakSeeker.walk(child);
@@ -1819,15 +1825,19 @@ Function* Asm2WasmBuilder::processFunction(Ref ast) {
         in = getContinueLabelName(parentLabel);
         parentLabel = IString();
       } else {
-        out = getNextId("do-out");
-        in = getNextId("do-in");
+        out = "do-out";
+        in = "do-in";
       }
+      out = nameMapper.pushLabelName(out);
+      in = nameMapper.pushLabelName(in);
       loop->name = in;
       breakStack.push_back(out);
       continueStack.push_back(in);
       loop->body = process(ast[2]);
       continueStack.pop_back();
       breakStack.pop_back();
+      nameMapper.popLabelName(in);
+      nameMapper.popLabelName(out);
       Break *continuer = allocator.alloc<Break>();
       continuer->name = in;
       continuer->condition = process(ast[1]);
@@ -1847,9 +1857,11 @@ Function* Asm2WasmBuilder::processFunction(Ref ast) {
         in = getContinueLabelName(parentLabel);
         parentLabel = IString();
       } else {
-        out = getNextId("for-out");
-        in = getNextId("for-in");
+        out = "for-out";
+        in = "for-in";
       }
+      out = nameMapper.pushLabelName(out);
+      in = nameMapper.pushLabelName(in);
       ret->name = in;
       breakStack.push_back(out);
       continueStack.push_back(in);
@@ -1873,6 +1885,8 @@ Function* Asm2WasmBuilder::processFunction(Ref ast) {
       ret->finalize();
       continueStack.pop_back();
       breakStack.pop_back();
+      nameMapper.popLabelName(in);
+      nameMapper.popLabelName(out);
       Block *outer = allocator.alloc<Block>();
       // add an outer block for the init as well
       outer->list.push_back(process(finit));
@@ -1957,8 +1971,9 @@ Function* Asm2WasmBuilder::processFunction(Ref ast) {
         name = getBreakLabelName(parentLabel);
         parentLabel = IString();
       } else {
-        name = getNextId("switch");
+        name = "switch";
       }
+      name = nameMapper.pushLabelName(name);
       breakStack.push_back(name);
 
       auto br = allocator.alloc<Switch>();
@@ -2009,14 +2024,14 @@ Function* Asm2WasmBuilder::processFunction(Ref ast) {
         auto case_ = processStatements(body, 0);
         Name name;
         if (condition->isNull()) {
-          name = br->default_ = getNextId("switch-default");
+          name = br->default_ = nameMapper.pushLabelName("switch-default");
         } else {
           auto index = getLiteral(condition).getInteger();
           assert(index >= min);
           index -= min;
           assert(index >= 0);
           uint64_t index_s = index;
-          name = getNextId("switch-case");
+          name = nameMapper.pushLabelName("switch-case");
           if (br->targets.size() <= index_s) {
             br->targets.resize(index_s + 1);
           }
@@ -2028,6 +2043,7 @@ Function* Asm2WasmBuilder::processFunction(Ref ast) {
         next->list.push_back(case_);
         next->finalize();
         top = next;
+        nameMapper.popLabelName(name);
       }
 
       // the outermost block can be branched to to exit the whole switch
@@ -2042,6 +2058,7 @@ Function* Asm2WasmBuilder::processFunction(Ref ast) {
       }
 
       breakStack.pop_back();
+      nameMapper.popLabelName(name);
 
       return top;
     }
diff --git a/src/ast_utils.h b/src/ast_utils.h
index 8124d3a79..861a09aaf 100644
--- a/src/ast_utils.h
+++ b/src/ast_utils.h
@@ -25,8 +25,11 @@
 
 namespace wasm {
 
+// Finds if there are breaks targeting a name. Note that since names are
+// unique in our IR, we just need to look for the name, and do not need
+// to analyze scoping.
 struct BreakSeeker : public PostWalker<BreakSeeker, Visitor<BreakSeeker>> {
-  Name target; // look for this one XXX looking by name may fall prey to duplicate names
+  Name target;
   Index found;
   WasmType valueType;
 
diff --git a/src/cfg/Relooper.cpp b/src/cfg/Relooper.cpp
index 8a5337ed0..d412c7b31 100644
--- a/src/cfg/Relooper.cpp
+++ b/src/cfg/Relooper.cpp
@@ -24,6 +24,7 @@
 #include <string>
 
 #include "ast_utils.h"
+#include "parsing.h"
 
 namespace CFG {
 
@@ -939,7 +940,10 @@ void Relooper::Calculate(Block *Entry) {
 
 wasm::Expression* Relooper::Render(RelooperBuilder& Builder) {
   assert(Root);
-  return Root->Render(Builder, false);
+  auto* ret = Root->Render(Builder, false);
+  // we may use the same name for more than one block in HandleFollowupMultiples
+  wasm::UniqueNameMapper::uniquify(ret);
+  return ret;
 }
 
 #ifdef RELOOPER_DEBUG
diff --git a/src/parsing.h b/src/parsing.h
index c5341c40b..1485dc6eb 100644
--- a/src/parsing.h
+++ b/src/parsing.h
@@ -191,6 +191,91 @@ struct ParseException {
   }
 };
 
+// Helper for parsers that may not have unique label names. This transforms
+// the names into unique ones, as required by Binaryen IR.
+struct UniqueNameMapper {
+  std::vector<Name> labelStack;
+  std::map<Name, std::vector<Name>> labelMappings; // name in source => stack of uniquified names
+  std::map<Name, Name> reverseLabelMapping; // uniquified name => name in source
+
+  Index otherIndex = 0;
+
+  Name getPrefixedName(Name prefix) {
+    if (reverseLabelMapping.find(prefix) == reverseLabelMapping.end()) return prefix;
+    // make sure to return a unique name not already on the stack
+    while (1) {
+      Name ret = Name(prefix.str + std::to_string(otherIndex++));
+      if (reverseLabelMapping.find(ret) == reverseLabelMapping.end()) return ret;
+    }
+  }
+
+  // receives a source name. generates a unique name, pushes it, and returns it
+  Name pushLabelName(Name sName) {
+    Name name = getPrefixedName(sName);
+    labelStack.push_back(name);
+    labelMappings[sName].push_back(name);
+    reverseLabelMapping[name] = sName;
+    return name;
+  }
+
+  void popLabelName(Name name) {
+    assert(labelStack.back() == name);
+    labelStack.pop_back();
+    labelMappings[reverseLabelMapping[name]].pop_back();
+  }
+
+  Name sourceToUnique(Name sName) {
+    return labelMappings.at(sName).back();
+  }
+
+  Name uniqueToSource(Name name) {
+    return reverseLabelMapping.at(name);
+  }
+
+  void clear() {
+    labelStack.clear();
+    labelMappings.clear();
+    reverseLabelMapping.clear();
+  }
+
+  // Given an expression, ensures all names are unique
+  static void uniquify(Expression* curr) {
+    struct Walker : public ControlFlowWalker<Walker, Visitor<Walker>> {
+      UniqueNameMapper mapper;
+
+      static void doPreVisitControlFlow(Walker* self, Expression** currp) {
+        auto* curr = *currp;
+        if (auto* block = curr->dynCast<Block>()) {
+          if (block->name.is()) block->name = self->mapper.pushLabelName(block->name);
+        } else if (auto* loop = curr->dynCast<Loop>()) {
+          if (loop->name.is()) loop->name = self->mapper.pushLabelName(loop->name);
+        }
+      }
+      static void doPostVisitControlFlow(Walker* self, Expression** currp) {
+        auto* curr = *currp;
+        if (auto* block = curr->dynCast<Block>()) {
+          if (block->name.is()) self->mapper.popLabelName(block->name);
+        } else if (auto* loop = curr->dynCast<Loop>()) {
+          if (loop->name.is()) self->mapper.popLabelName(loop->name);
+        }
+      }
+
+      void visitBreak(Break *curr) {
+        curr->name = mapper.sourceToUnique(curr->name);
+      }
+      void visitSwitch(Switch *curr) {
+        for (auto& target : curr->targets) {
+          target = mapper.sourceToUnique(target);
+        }
+        curr->default_ = mapper.sourceToUnique(curr->default_);
+      }
+    };
+
+    Walker walker;
+    walker.walk(curr);
+  }
+};
+
 } // namespace wasm
 
 #endif // wasm_parsing_h
diff --git a/src/wasm-s-parser.h b/src/wasm-s-parser.h
index 72949eb2b..7f5afe8f7 100644
--- a/src/wasm-s-parser.h
+++ b/src/wasm-s-parser.h
@@ -428,16 +428,9 @@ private:
   std::map<Name, WasmType> currLocalTypes;
   size_t localIndex; // params and vars
   size_t otherIndex;
-  std::vector<Name> labelStack;
   bool brokeToAutoBlock;
 
-  Name getPrefixedName(std::string prefix) {
-    // make sure to return a unique name not already on the stack
-    while (1) {
-      Name ret = IString((prefix + std::to_string(otherIndex++)).c_str(), false);
-      if (std::find(labelStack.begin(), labelStack.end(), ret) == labelStack.end()) return ret;
-    }
-  }
+  UniqueNameMapper nameMapper;
 
   Name getFunctionName(Element& s) {
     if (s.dollared()) {
@@ -642,7 +635,7 @@ private:
       wasm.addImport(im.release());
       assert(!currFunction);
       currLocalTypes.clear();
-      labelStack.clear();
+      nameMapper.clear();
       return;
     }
     assert(!preParseImport);
@@ -662,7 +655,7 @@ private:
     currFunction->type = type;
     wasm.addFunction(currFunction.release());
     currLocalTypes.clear();
-    labelStack.clear();
+    nameMapper.clear();
   }
 
   WasmType stringToWasmType(IString str, bool allowError=false, bool prefix=false) {
@@ -1085,18 +1078,18 @@ private:
       stack.emplace_back(sp, curr);
       auto& s = *sp;
       size_t i = 1;
+      Name sName;
       if (i < s.size() && s[i]->isStr()) {
         // could be a name or a type
         if (s[i]->dollared() || stringToWasmType(s[i]->str(), true /* allowError */) == none) {
-          curr->name = s[i]->str();
-          i++;
+          sName = s[i++]->str();
         } else {
-          curr->name = getPrefixedName("block");
+          sName = "block";
         }
       } else {
-        curr->name = getPrefixedName("block");
+        sName = "block";
       }
-      labelStack.push_back(curr->name);
+      curr->name = nameMapper.pushLabelName(sName);
       if (i >= s.size()) break; // empty block
       if (s[i]->isStr()) {
         // block signature
@@ -1133,8 +1126,7 @@ private:
           curr->list.push_back(parseExpression(s[i]));
         }
       }
-      assert(labelStack.back() == curr->name);
-      labelStack.pop_back();
+      nameMapper.popLabelName(curr->name);
       curr->finalize(curr->type);
     }
     return stack[0].second;
@@ -1240,14 +1232,14 @@ private:
   Expression* makeIf(Element& s) {
     auto ret = allocator.alloc<If>();
     Index i = 1;
-    Name label;
+    Name sName;
     if (s[i]->dollared()) {
       // the if is labeled
-      label = s[i++]->str();
+      sName = s[i++]->str();
     } else {
-      label = getPrefixedName("if");
+      sName = "if";
     }
-    labelStack.push_back(label);
+    auto label = nameMapper.pushLabelName(sName);
     WasmType type = none;
     if (s[i]->isStr()) {
       type = stringToWasmType(s[i++]->str());
@@ -1258,7 +1250,7 @@ private:
       ret->ifFalse = parseExpression(*s[i++]);
     }
     ret->finalize(type);
-    labelStack.pop_back();
+    nameMapper.popLabelName(label);
     // create a break target if we must
     if (BreakSeeker::has(ret, label)) {
       auto* block = allocator.alloc<Block>();
@@ -1288,33 +1280,21 @@ private:
   Expression* makeLoop(Element& s) {
     auto ret = allocator.alloc<Loop>();
     size_t i = 1;
-    Name out;
-    if (s.size() > i + 1 && s[i]->dollared() && s[i + 1]->dollared()) { // out can only be named if both are
-      out = s[i]->str();
-      i++;
-    }
+    Name sName;
     if (s.size() > i && s[i]->dollared()) {
-      ret->name = s[i]->str();
-      i++;
+      sName = s[i++]->str();
     } else {
-      ret->name = getPrefixedName("loop-in");
+      sName = "loop-in";
     }
+    ret->name = nameMapper.pushLabelName(sName);
     ret->type = none;
     if (i < s.size() && s[i]->isStr()) {
       // block signature
       ret->type = stringToWasmType(s[i++]->str());
     }
-    labelStack.push_back(ret->name);
     ret->body = makeMaybeBlock(s, i, ret->type);
-    labelStack.pop_back();
+    nameMapper.popLabelName(ret->name);
     ret->finalize(ret->type);
-    if (out.is()) {
-      auto* block = allocator.alloc<Block>();
-      block->name = out;
-      block->list.push_back(ret);
-      block->finalize();
-      return block;
-    }
     return ret;
   }
 
@@ -1367,17 +1347,17 @@ private:
   }
   Name getLabel(Element& s) {
     if (s.dollared()) {
-      return s.str();
+      return nameMapper.sourceToUnique(s.str());
     } else {
       // offset, break to nth outside label
       uint64_t offset = std::stoll(s.c_str(), nullptr, 0);
-      if (offset > labelStack.size()) throw ParseException("invalid label", s.line, s.col);
-      if (offset == labelStack.size()) {
+      if (offset > nameMapper.labelStack.size()) throw ParseException("invalid label", s.line, s.col);
+      if (offset == nameMapper.labelStack.size()) {
         // a break to the function's scope. this means we need an automatic block, with a name
         brokeToAutoBlock = true;
         return FAKE_RETURN;
       }
-      return labelStack[labelStack.size() - 1 - offset];
+      return nameMapper.labelStack[nameMapper.labelStack.size() - 1 - offset];
     }
   }
   Expression* makeBreak(Element& s) {
diff --git a/src/wasm-validator.h b/src/wasm-validator.h
index f17ed16d5..cb226a924 100644
--- a/src/wasm-validator.h
+++ b/src/wasm-validator.h
@@ -37,6 +37,8 @@
 #ifndef wasm_wasm_validator_h
 #define wasm_wasm_validator_h
 
+#include <set>
+
 #include "wasm.h"
 #include "wasm-printing.h"
 
@@ -61,6 +63,14 @@ struct WasmValidator : public PostWalker<WasmValidator, Visitor<WasmValidator>>
 
   WasmType returnType = unreachable; // type used in returns
 
+  std::set<Name> labelNames; // Binaryen IR requires that label names must be unique - IR generators must ensure that
+
+  void noteLabelName(Name name) {
+    if (!name.is()) return;
+    shouldBeTrue(labelNames.find(name) == labelNames.end(), name, "names in Binaren IR must be unique - IR generators must ensure that");
+    labelNames.insert(name);
+  }
+
 public:
   bool validate(Module& module, bool validateWeb_ = false, bool validateGlobally_ = true) {
     validateWeb = validateWeb_;
@@ -82,6 +92,7 @@ public:
   void visitBlock(Block *curr) {
     // if we are break'ed to, then the value must be right for us
     if (curr->name.is()) {
+      noteLabelName(curr->name);
       if (breakInfos.count(curr) > 0) {
         auto& info = breakInfos[curr];
         if (isConcreteWasmType(curr->type)) {
@@ -128,6 +139,7 @@ public:
 
   void visitLoop(Loop *curr) {
     if (curr->name.is()) {
+      noteLabelName(curr->name);
       breakTargets[curr->name].pop_back();
       if (breakInfos.count(curr) > 0) {
         auto& info = breakInfos[curr];
@@ -405,6 +417,7 @@ public:
       }
     }
     returnType = unreachable;
+    labelNames.clear();
   }
 
   bool isConstant(Expression* curr) {