[WebAssembly] AsmTypeCheck does not handle block return values of unreachable block end

[aheejin]

AsmTypeCheck does not handle block/loop's concrete return values when their end is not reachable, for example,

block i32
i32.const 0
br 0
end

This is a valid wasm program but does not pass AsmTypeCheck.

Currently Wasm backend does not generate block/loop return types, but one exception is, the ones generated by WebAssemblyCFGStackify::fixEndsAtEndOfFunction:

llvm-project/llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp

Lines 1460 to 1520 in 093b8bf

	/// In normal assembly languages, when the end of a function is unreachable,
	/// because the function ends in an infinite loop or a noreturn call or similar,
	/// it isn't necessary to worry about the function return type at the end of
	/// the function, because it's never reached. However, in WebAssembly, blocks
	/// that end at the function end need to have a return type signature that
	/// matches the function signature, even though it's unreachable. This function
	/// checks for such cases and fixes up the signatures.
	void WebAssemblyCFGStackify::fixEndsAtEndOfFunction(MachineFunction &MF) {
	const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
	if (MFI.getResults().empty())
	return;
	// MCInstLower will add the proper types to multivalue signatures based on the
	// function return type
	WebAssembly::BlockType RetType =
	MFI.getResults().size() > 1
	? WebAssembly::BlockType::Multivalue
	: WebAssembly::BlockType(
	WebAssembly::toValType(MFI.getResults().front()));
	SmallVector<MachineBasicBlock::reverse_iterator, 4> Worklist;
	Worklist.push_back(MF.rbegin()->rbegin());
	auto Process = [&](MachineBasicBlock::reverse_iterator It) {
	auto *MBB = It->getParent();
	while (It != MBB->rend()) {
	MachineInstr &MI = *It++;
	if (MI.isPosition() || MI.isDebugInstr())
	continue;
	switch (MI.getOpcode()) {
	case WebAssembly::END_TRY: {
	// If a 'try''s return type is fixed, both its try body and catch body
	// should satisfy the return type, so we need to search 'end'
	// instructions before its corresponding 'catch' too.
	auto *EHPad = TryToEHPad.lookup(EndToBegin[&MI]);
	assert(EHPad);
	auto NextIt =
	std::next(WebAssembly::findCatch(EHPad)->getReverseIterator());
	if (NextIt != EHPad->rend())
	Worklist.push_back(NextIt);
	[[fallthrough]];
	}
	case WebAssembly::END_BLOCK:
	case WebAssembly::END_LOOP:
	case WebAssembly::DELEGATE:
	EndToBegin[&MI]->getOperand(0).setImm(int32_t(RetType));
	continue;
	default:
	// Something other than an `end`. We're done for this BB.
	return;
	}
	}
	// We've reached the beginning of a BB. Continue the search in the previous
	// BB.
	Worklist.push_back(MBB->getPrevNode()->rbegin());
	};
	while (!Worklist.empty())
	Process(Worklist.pop_back_val());
	}

An example program that would generate this case is

;; test.ll
target triple = "wasm32-unknown-unknown"

define i32 @loop_i32() {
entry:
  br label %header
header:
  br label %header
}

which generates

loop i32
br 0
end

The reproducing commands:

$ llc test.ll
$ llvm-mc -triple=wasm32-unknown-unknown test.s

The error will be

...
        loop            i32                             # label0:
        br              0                               # 0: up to label0
.LBB0_2:
b.s:15:2: error: end: insufficient values on the type stack
        end_loop
        ^
        end_function
...

[llvmbot]

@llvm/issue-subscribers-backend-webassembly

Author: Heejin Ahn (aheejin)

`AsmTypeCheck` does not handle block/loop's concrete return values when their end is not reachable, for example, ```s block i32 br 0 end ``` This is a valid wasm program but does not pass `AsmTypeCheck`.

Currently Wasm backend does not generate block/loop return types, but one exception is, the ones generated by WebAssemblyCFGStackify::fixEndsAtEndOfFunction:

llvm-project/llvm/lib/Target/WebAssembly/WebAssemblyCFGStackify.cpp

Lines 1460 to 1520 in 093b8bf

	/// In normal assembly languages, when the end of a function is unreachable,
	/// because the function ends in an infinite loop or a noreturn call or similar,
	/// it isn't necessary to worry about the function return type at the end of
	/// the function, because it's never reached. However, in WebAssembly, blocks
	/// that end at the function end need to have a return type signature that
	/// matches the function signature, even though it's unreachable. This function
	/// checks for such cases and fixes up the signatures.
	void WebAssemblyCFGStackify::fixEndsAtEndOfFunction(MachineFunction &MF) {
	const auto &MFI = *MF.getInfo<WebAssemblyFunctionInfo>();
	if (MFI.getResults().empty())
	return;
	// MCInstLower will add the proper types to multivalue signatures based on the
	// function return type
	WebAssembly::BlockType RetType =
	MFI.getResults().size() > 1
	? WebAssembly::BlockType::Multivalue
	: WebAssembly::BlockType(
	WebAssembly::toValType(MFI.getResults().front()));
	SmallVector<MachineBasicBlock::reverse_iterator, 4> Worklist;
	Worklist.push_back(MF.rbegin()->rbegin());
	auto Process = [&](MachineBasicBlock::reverse_iterator It) {
	auto *MBB = It->getParent();
	while (It != MBB->rend()) {
	MachineInstr &MI = *It++;
	if (MI.isPosition() || MI.isDebugInstr())
	continue;
	switch (MI.getOpcode()) {
	case WebAssembly::END_TRY: {
	// If a 'try''s return type is fixed, both its try body and catch body
	// should satisfy the return type, so we need to search 'end'
	// instructions before its corresponding 'catch' too.
	auto *EHPad = TryToEHPad.lookup(EndToBegin[&MI]);
	assert(EHPad);
	auto NextIt =
	std::next(WebAssembly::findCatch(EHPad)->getReverseIterator());
	if (NextIt != EHPad->rend())
	Worklist.push_back(NextIt);
	[[fallthrough]];
	}
	case WebAssembly::END_BLOCK:
	case WebAssembly::END_LOOP:
	case WebAssembly::DELEGATE:
	EndToBegin[&MI]->getOperand(0).setImm(int32_t(RetType));
	continue;
	default:
	// Something other than an `end`. We're done for this BB.
	return;
	}
	}
	// We've reached the beginning of a BB. Continue the search in the previous
	// BB.
	Worklist.push_back(MBB->getPrevNode()->rbegin());
	};
	while (!Worklist.empty())
	Process(Worklist.pop_back_val());
	}

An example program that would generate this case is

;; test.ll
target triple = "wasm32-unknown-unknown"

define i32 @<!-- -->loop_i32() {
entry:
  br label %header
header:
  br label %header
}

which generates

loop i32
br 0
end

The reproducing commands:

$ llc test.ll
$ llvm-mc -triple=wasm32-unknown-unknown test.s