[WebAssembly] Make assembler check for proper nesting of control flow.

[aardappel]

Summary

It does so using a simple nesting stack, and gives clear errors upon
violation. This is unique to wasm, since most CPUs do not have
any nested constructs.

Had to add an end of file check to the general assembler for this.

Note: if/else/end instructions are not currently supported in our
tablegen defs, so these tests will be enabled in a follow-up.
They already pass the nesting check.

[aheejin]

• Function names should begin with a lowercase letter
• Is there a test case that actually generates an error so we can test the error is correctly generated? It looks like we don't have a test here (Test changes here don't look relevant to this CL)

[aheejin]

test/MC/WebAssembly/basic-assembly.s

66 ↗

(On Diff #178564)

I guess this is not relevant to this CL?

141 ↗

(On Diff #178564)

Here too

test/MC/WebAssembly/simd-encodings.s

4 ↗

(On Diff #178564)

I guess this is not relevant to this CL?

[aheejin]

Nevermind these two comments, but still think a error-generating test case would be great

test/MC/WebAssembly/basic-assembly.s

66 ↗

(On Diff #178564)

Oh nevermind, it is.

141 ↗

(On Diff #178564)

Nevermind again

[aheejin]

FYI you can check error message of an invalid test case by appending not in the RUN line and redirect the stderr to stdout, like this test.

lib/Target/WebAssembly/AsmParser/WebAssemblyAsmParser.cpp

183 ↗

(On Diff #178564)

We have Try now too

230 ↗

(On Diff #178564)

+ try handling

241 ↗

(On Diff #178564)

Nit: Maybe add " or " between to strings to clarify we require only one of them?

246 ↗

(On Diff #178564)

Nit: Maybe add " or " between to strings to clarify we require only one of them?

403 ↗

(On Diff #178564)

We have end_try too

405 ↗

(On Diff #178564)

Did you mean to use &&? Not sure if || makes sense here

559 ↗

(On Diff #178564)

Nit: Given that this is not a function end but rather a function start, how about renaming the function to something like ensureEmptyControlFlowStack or something and change the error message accordingly?

[aardappel]

Added a test that tests the errors too.

lib/Target/WebAssembly/AsmParser/WebAssemblyAsmParser.cpp

403 ↗

(On Diff #178564)

Ok, added support for try/catch/catch_all/end_try

405 ↗

(On Diff #178564)

in the parser, functions return true on failure.. which is a bit odd, yes.

559 ↗

(On Diff #178564)

It is also possibly the end of the previous function (if end_function was forgotten. But sure, I'll change the name.

test/MC/WebAssembly/simd-encodings.s

4 ↗

(On Diff #178564)

It is.. it had an end_function without a start of a function

[aardappel]

Addressed code review.

[aheejin]

lib/Target/WebAssembly/AsmParser/WebAssemblyAsmParser.cpp

405 ↗

(On Diff #178564)

Ah I see.

test/MC/WebAssembly/basic-assembly-errors.s

16 ↗

(On Diff #179184)

Indent the same way with other lines

22 ↗

(On Diff #179184)

These error messages are a little confusing, because we have end_loop in the code but the error message says "we got loop". The same for all other messages. I guess we should change the message to reflect the actual instructions in the test?

[aardappel]

Addressed code review.

[aheejin]

• It looks like even if an error occurs, the parsing continues. Is this an expected behavior?

• If it is, is a mismatched instruction supposed to pop the stack? For example,

try
loop
block
end_loop    // stray incorrect instruction
end_block
end_loop
end_try

In this case, there is a stray end_loop instruction in the middle of an otherwise correct sequence of instructions. When we parse end_loop, we pop block and compare that with end_loop and emit an error, which is fine. But next we parse end_block, but block was incorrectly popped when we parse loop, it is going to fail. The next instruction as well, and this ends up failing all the instructions. But if we don't pop the stack when an incorrect match occurs, there is gonna be only one error, other than four. I'm not sure what the right behavior is, so I'm asking.

test/MC/WebAssembly/basic-assembly-errors.s

1 ↗

(On Diff #179207)

This is ok as is, but it looks like usually people append not in front of the command (in which way you don't need || true)

13 ↗

(On Diff #179207)

By the way, can we parse if? You commented these out in the other test case saying they are not supported in tablegen.

16 ↗

(On Diff #179207)

Looks like this line is indented with a tab, while others with spaces.

22 ↗

(On Diff #179207)

How about interleaving these lines within the test case, so we can easily see which lines match which instruction? In that way we may not need inline comments for those instructions as well

[aardappel]

@aheejin
Yes, the parser normally continues after an error, that is out of my control.. unless I put in a hack like consuming all tokens until EOF.

I can make it not pop if there is an error, which is indeed slightly better behavior. Do note that not popping equally can cause unwanted errors:

try
loop
block
end_if  // I meant to write end_block, error.
end_loop // now also error
end_try // now also error

But that should be slightly less likely than your example. Does require a different structure in basic-assembly-errors.s

test/MC/WebAssembly/basic-assembly-errors.s

13 ↗

(On Diff #179207)

Yes, they will be added in the next CL. dschuff suggested it was nicer to keep them seperate.

[aardappel]

More code review fixes.

[aheejin]

lib/Target/WebAssembly/AsmParser/WebAssemblyAsmParser.cpp

258 ↗

(On Diff #179514)

This looks nice!

[• shagitoramsil]

In D55797#1338387, @aardappel wrote:

Addressed code review.

[• shagitoramsil]

Aahhhhh don't meke me mad I will found you

llvm/trunk/include/llvm/MC/MCParser/MCTargetAsmParser.h

public:
   /// output streamer, if the target does not emit them immediately.
   virtual void flushPendingInstructions(MCStreamer &Out) {}
 
   virtual const MCExpr *createTargetUnaryExpr(const MCExpr *E,
                                               AsmToken::TokenKind OperatorToken,
                                               MCContext &Ctx) {
     return nullptr;
   }
+
+  // For any checks or cleanups at the end of parsing.
+  virtual void onEndOfFile() {}
 };
 
 } // end namespace llvm
 
 #endif // LLVM_MC_MCPARSER_MCTARGETASMPARSER_H

llvm/trunk/lib/MC/MCParser/AsmParser.cpp

while (Lexer.isNot(AsmToken::Eof)) {
     // parseStatement returned true so may need to emit an error.
     printPendingErrors();
 
     // Skipping to the next line if needed.
     if (!getLexer().isAtStartOfStatement())
       eatToEndOfStatement();
   }
 
+  getTargetParser().onEndOfFile();
+  printPendingErrors();
+
   // All errors should have been emitted.
   assert(!hasPendingError() && "unexpected error from parseStatement");
 
   getTargetParser().flushPendingInstructions(getStreamer());
 
   if (TheCondState.TheCond != StartingCondState.TheCond ||
       TheCondState.Ignore != StartingCondState.Ignore)
     printError(getTok().getLoc(), "unmatched .ifs or .elses");

llvm/trunk/lib/Target/WebAssembly/AsmParser/WebAssemblyAsmParser.cpp

class WebAssemblyAsmParser final : public MCTargetAsmParser {
   enum ParserState {
     FileStart,
     Label,
     FunctionStart,
     FunctionLocals,
     Instructions,
   } CurrentState = FileStart;
 
+  // For ensuring blocks are properly nested.
+  enum NestingType {
+    Function,
+    Block,
+    Loop,
+    Try,
+    If,
+    Else,
+    Undefined,
+  };
+  std::vector<NestingType> NestingStack;
+
   // We track this to see if a .functype following a label is the same,
   // as this is how we recognize the start of a function.
   MCSymbol *LastLabel = nullptr;
 
 public:
   WebAssemblyAsmParser(const MCSubtargetInfo &STI, MCAsmParser &Parser,
                        const MCInstrInfo &MII, const MCTargetOptions &Options)
       : MCTargetAsmParser(Options, STI, MII), Parser(Parser),
         Lexer(Parser.getLexer()) {
     setAvailableFeatures(ComputeAvailableFeatures(STI.getFeatureBits()));
   }
 
-  void addSignature(std::unique_ptr<wasm::WasmSignature> &&Sig) {
-    Signatures.push_back(std::move(Sig));
-  }
-
 #define GET_ASSEMBLER_HEADER
 #include "WebAssemblyGenAsmMatcher.inc"
 
   // TODO: This is required to be implemented, but appears unused.
   bool ParseRegister(unsigned & /*RegNo*/, SMLoc & /*StartLoc*/,
                      SMLoc & /*EndLoc*/) override {
     llvm_unreachable("ParseRegister is not implemented.");
   }
 
-  bool error(const StringRef &Msg, const AsmToken &Tok) {
+  bool error(const Twine &Msg, const AsmToken &Tok) {
     return Parser.Error(Tok.getLoc(), Msg + Tok.getString());
   }
 
+  bool error(const Twine &Msg) {
+    return Parser.Error(Lexer.getTok().getLoc(), Msg);
+  }
+
+  void addSignature(std::unique_ptr<wasm::WasmSignature> &&Sig) {
+    Signatures.push_back(std::move(Sig));
+  }
+
+  std::pair<StringRef, StringRef> nestingString(NestingType NT) {
+    switch (NT) {
+    case Function:
+      return {"function", "end_function"};
+    case Block:
+      return {"block", "end_block"};
+    case Loop:
+      return {"loop", "end_loop"};
+    case Try:
+      return {"try", "end_try"};
+    case If:
+      return {"if", "end_if"};
+    case Else:
+      return {"else", "end_if"};
+    default:
+      llvm_unreachable("unknown NestingType");
+    }
+  }
+
+  void push(NestingType NT) { NestingStack.push_back(NT); }
+
+  bool pop(StringRef Ins, NestingType NT1, NestingType NT2 = Undefined) {
+    if (NestingStack.empty())
+      return error(Twine("End of block construct with no start: ") + Ins);
+    auto Top = NestingStack.back();
+    if (Top != NT1 && Top != NT2)
+      return error(Twine("Block construct type mismatch, expected: ") +
+                   nestingString(Top).second + ", instead got: " + Ins);
+    NestingStack.pop_back();
+    return false;
+  }
+
+  bool ensureEmptyNestingStack() {
+    auto err = !NestingStack.empty();
+    while (!NestingStack.empty()) {
+      error(Twine("Unmatched block construct(s) at function end: ") +
+            nestingString(NestingStack.back()).first);
+      NestingStack.pop_back();
+    }
+    return err;
+  }
+
   bool isNext(AsmToken::TokenKind Kind) {
     auto Ok = Lexer.is(Kind);
     if (Ok)
       Parser.Lex();
     return Ok;
   }
 
   bool expect(AsmToken::TokenKind Kind, const char *KindName) {
bool ParseInstruction(ParseInstructionInfo & /*Info*/, StringRef Name,
     // Now construct the name as first operand.
     Operands.push_back(make_unique<WebAssemblyOperand>(
         WebAssemblyOperand::Token, NameLoc, SMLoc::getFromPointer(Name.end()),
         WebAssemblyOperand::TokOp{Name}));
     auto NamePair = Name.split('.');
     // If no '.', there is no type prefix.
     auto BaseName = NamePair.second.empty() ? NamePair.first : NamePair.second;
 
+    // If this instruction is part of a control flow structure, ensure
+    // proper nesting.
+    if (BaseName == "block") {
+      push(Block);
+    } else if (BaseName == "loop") {
+      push(Loop);
+    } else if (BaseName == "try") {
+      push(Try);
+    } else if (BaseName == "if") {
+      push(If);
+    } else if (BaseName == "else") {
+      if (pop(BaseName, If))
+        return true;
+      push(Else);
+    } else if (BaseName == "catch") {
+      if (pop(BaseName, Try))
+        return true;
+      push(Try);
+    } else if (BaseName == "catch_all") {
+      if (pop(BaseName, Try))
+        return true;
+      push(Try);
+    } else if (BaseName == "end_if") {
+      if (pop(BaseName, If, Else))
+        return true;
+    } else if (BaseName == "end_try") {
+      if (pop(BaseName, Try))
+        return true;
+    } else if (BaseName == "end_loop") {
+      if (pop(BaseName, Loop))
+        return true;
+    } else if (BaseName == "end_block") {
+      if (pop(BaseName, Block))
+        return true;
+    } else if (BaseName == "end_function") {
+      if (pop(BaseName, Function) || ensureEmptyNestingStack())
+        return true;
+    }
+
     while (Lexer.isNot(AsmToken::EndOfStatement)) {
       auto &Tok = Lexer.getTok();
       switch (Tok.getKind()) {
       case AsmToken::Identifier: {
         auto &Id = Lexer.getTok();
         const MCExpr *Val;
         SMLoc End;
         if (Parser.parsePrimaryExpr(Val, End))
if (DirectiveID.getString() == ".functype") {
       // parses the locals seperately.
       auto SymName = expectIdent();
       if (SymName.empty())
         return true;
       auto WasmSym = cast<MCSymbolWasm>(
           TOut.getStreamer().getContext().getOrCreateSymbol(SymName));
       if (CurrentState == Label && WasmSym == LastLabel) {
         // This .functype indicates a start of a function.
+        if (ensureEmptyNestingStack())
+          return true;
         CurrentState = FunctionStart;
+        push(Function);
       }
       auto Signature = make_unique<wasm::WasmSignature>();
       if (parseSignature(Signature.get()))
         return true;
       WasmSym->setSignature(Signature.get());
       addSignature(std::move(Signature));
       WasmSym->setType(wasm::WASM_SYMBOL_TYPE_FUNCTION);
       TOut.emitFunctionType(WasmSym);
case Match_InvalidOperand: {
         if (ErrorLoc == SMLoc())
           ErrorLoc = IDLoc;
       }
       return Parser.Error(ErrorLoc, "invalid operand for instruction");
     }
     }
     llvm_unreachable("Implement any new match types added!");
   }
+
+  void onEndOfFile() override { ensureEmptyNestingStack(); }
 };
 } // end anonymous namespace
 
 // Force static initialization.
 extern "C" void LLVMInitializeWebAssemblyAsmParser() {
   RegisterMCAsmParser<WebAssemblyAsmParser> X(getTheWebAssemblyTarget32());
   RegisterMCAsmParser<WebAssemblyAsmParser> Y(getTheWebAssemblyTarget64());
 }
 
 #define GET_REGISTER_MATCHER
 #define GET_MATCHER_IMPLEMENTATION
 #include "WebAssemblyGenAsmMatcher.inc"

llvm/trunk/test/MC/WebAssembly/basic-assembly-errors.s

+# RUN: not llvm-mc -triple=wasm32-unknown-unknown -mattr=+simd128,+nontrapping-fptoint,+exception-handling < %s 2>&1 | FileCheck %s
+
+    .text
+    .section    .text.main,"",@
+    .type       test0,@function
+# CHECK: End of block construct with no start: end_try
+    end_try
+test0:
+    .functype   test0 () -> ()
+# CHECK: Block construct type mismatch, expected: end_function, instead got: end_loop
+    end_loop
+    block
+# CHECK: Block construct type mismatch, expected: end_block, instead got: end_if
+    end_if
+    try
+    loop
+# CHECK: Block construct type mismatch, expected: end_loop, instead got: end_function
+# CHECK: error: Unmatched block construct(s) at function end: loop
+# CHECK: error: Unmatched block construct(s) at function end: try
+# CHECK: error: Unmatched block construct(s) at function end: block
+# CHECK: error: Unmatched block construct(s) at function end: function
+    end_function
+.Lfunc_end0:
+    .size       test0, .Lfunc_end0-test0
+

llvm/trunk/test/MC/WebAssembly/basic-assembly.s

.LBB0_2:
     i32.const 1
     br 2
     end_block            # second entry jumps here.
     i32.const 2
     br 1
     end_block            # default jumps here.
     i32.const 3
     end_block            # "switch" exit.
+    #if                  # These are not in tablegen defs yet..
+    #if
+    #end_if
+    #else
+    #end_if
     f32x4.add
     # Test correct parsing of instructions with / and : in them:
     # TODO: enable once instruction has been added.
     #i32x4.trunc_s/f32x4:sat
     i32.trunc_s/f32
     try
 .LBB0_3:
     i32.catch   0

 # CHECK-NEXT:      i32.const 1
 # CHECK-NEXT:      br 2                # 2: down to label2
 # CHECK-NEXT:      end_block           # label4:
 # CHECK-NEXT:      i32.const 2
 # CHECK-NEXT:      br 1                # 1: down to label2
 # CHECK-NEXT:      end_block           # label3:
 # CHECK-NEXT:      i32.const 3
 # CHECK-NEXT:      end_block           # label2:
+# DONT-CHECK-NEXT:      if
+# DONT-CHECK-NEXT:      if
+# DONT-CHECK-NEXT:      end_if
+# DONT-CHECK-NEXT:      else
+# DONT-CHECK-NEXT:      end_if
 # CHECK-NEXT:      f32x4.add
 # CHECK-NEXT:      i32.trunc_s/f32
 # CHECK-NEXT:      try
 # CHECK-NEXT:  .LBB0_3:
 # CHECK-NEXT:      i32.catch   0
 # CHECK-NEXT:  .LBB0_4:
 # CHECK-NEXT:      catch_all
 # CHECK-NEXT:  .LBB0_5:
 # CHECK-NEXT:      end_try
 # CHECK-NEXT:      get_global  __stack_pointer@GLOBAL
 # CHECK-NEXT:      end_function
 
 # CHECK:           .globaltype  __stack_pointer, i32

llvm/trunk/test/MC/WebAssembly/simd-encodings.s

 # RUN: llvm-mc -show-encoding -triple=wasm32-unkown-unknown -mattr=+sign-ext,+simd128 < %s | FileCheck %s
 
+main:
+    .functype main () -> ()
+
     # CHECK: v128.load 48:p2align=0 # encoding: [0xfd,0x00,0x00,0x30]
     v128.load 48
 
     # CHECK: v128.store 48:p2align=0 # encoding: [0xfd,0x01,0x00,0x30]
     v128.store 48
 
     # CHECK: v128.const 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
     # CHECK-SAME: # encoding: [0xfd,0x02,