clang emits invalid wasm code when compiling C

[TerrorJack]

Minimal repro:

extern int a;
void* b();
void c(void *);
void f() {
  void *d = b();
e:
  switch (a)
  case 0: {
    b();
    c(d);
    c((void *)*(int *)(d + -sizeof(int)));
    d = d - sizeof(int);
    goto e;
  }
}

The above code, when compiled with --target=wasm32 -O1 using latest clang on main, will produce the following invalid assembly code:

f:                                      # @f
        .functype       f () -> ()
        .local          i32
# %bb.0:
        call    b
        local.set       0
        block
        i32.const       0
        i32.load        a
        br_if           0                               # 0: down to label0
# %bb.1:
        local.get       0
        local.set       0
.LBB0_2:                                # =>This Inner Loop Header: Depth=1
        loop                                            # label1:
        call    b
        drop
        local.get       0
        local.tee       0
        call    c
        local.get       0
        i32.load        -4
        call    c
        local.get       0
        i32.const       -4
        i32.add
        local.set       0
        i32.const       0
        i32.load        a
        i32.eqz
        br_if           0                               # 0: up to label1
.LBB0_3:
        end_loop
        end_block                               # label0:
                                        # fallthrough-return
        end_function

Note the i32.load -4 line. This is invalid per wasm spec, the memarg offset/align must all be non-negative u32 literals. And indeed this code will trigger a memory trap at runtime!

I bisected this bug on master and the first bad commit is 7eca38c. cc @hazzlim

[llvmbot]

@llvm/issue-subscribers-backend-webassembly

Author: Cheng Shao (TerrorJack)

Minimal repro:

extern int a;
void* b();
void c(void *);
void f() {
  void *d = b();
e:
  switch (a)
  case 0: {
    b();
    c(d);
    c((void *)*(int *)(d + -sizeof(int)));
    d = d - sizeof(int);
    goto e;
  }
}

The above code, when compiled with --target=wasm32 -O1 using latest clang on main, will produce the following invalid assembly code:

f:                                      # @<!-- -->f
        .functype       f () -&gt; ()
        .local          i32
# %bb.0:
        call    b
        local.set       0
        block
        i32.const       0
        i32.load        a
        br_if           0                               # 0: down to label0
# %bb.1:
        local.get       0
        local.set       0
.LBB0_2:                                # =&gt;This Inner Loop Header: Depth=1
        loop                                            # label1:
        call    b
        drop
        local.get       0
        local.tee       0
        call    c
        local.get       0
        i32.load        -4
        call    c
        local.get       0
        i32.const       -4
        i32.add
        local.set       0
        i32.const       0
        i32.load        a
        i32.eqz
        br_if           0                               # 0: up to label1
.LBB0_3:
        end_loop
        end_block                               # label0:
                                        # fallthrough-return
        end_function

Note the i32.load -4 line. This is invalid per wasm spec, the memarg offset/align must all be non-negative u32 literals. And indeed this code will trigger a memory trap at runtime!

I bisected this bug on master and the first bad commit is 7eca38c. cc @hazzlim

[aheejin]

Another bug was reported recently regarding this commit (#107257 (comment)), which has been fixed by 940f892. Can you check if 940f892 fixes your bug too?

[nikic]

@aheejin That's an unrelated issue. I expect that

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

Lines 328 to 332 in 76b54df

	// WebAssembly constant offsets are performed as unsigned with infinite
	// precision, so we need to check for NoUnsignedWrap so that we don't fold an
	// offset for an add that needs wrapping.
	if (N.getOpcode() == ISD::ADD && !N.getNode()->getFlags().hasNoUnsignedWrap())
	return false;

needs an adjustment to also check for non-negative offset, instead of assuming that nuw implies that (which it never did, but previously it was harder to get one with a negative offset).

[aheejin]

@nikic Thanks for the pointer!

I think this code (added in #107257) is adding nuw to the getelementptr:

llvm-project/clang/lib/CodeGen/CGExprScalar.cpp

Lines 5774 to 5775 in 41f1b46

	if (!SignedIndices && !IsSubtraction)
	NWFlags |= llvm::GEPNoWrapFlags::noUnsignedWrap();

But the condition there says !SignedIndices. Why wouldn't a negative RHS value make that SignedIndices true?
I traced where that SignedIndices comes from. It's from

llvm-project/clang/lib/CodeGen/CGExprScalar.cpp

Line 3966 in 41f1b46

bool isSigned = indexOperand->getType()->isSignedIntegerOrEnumerationType();

where that Type is set in (see resultType = ... line)

llvm-project/clang/lib/Sema/SemaExpr.cpp

Lines 15393 to 15409 in 41f1b46

	case UO_Plus:
	case UO_Minus:
	CanOverflow = Opc == UO_Minus &&
	isOverflowingIntegerType(Context, Input.get()->getType());
	Input = UsualUnaryConversions(Input.get());
	if (Input.isInvalid())
	return ExprError();
	// Unary plus and minus require promoting an operand of half vector to a
	// float vector and truncating the result back to a half vector. For now,
	// we do this only when HalfArgsAndReturns is set (that is, when the
	// target is arm or arm64).
	ConvertHalfVec = needsConversionOfHalfVec(true, Context, Input.get());
	// If the operand is a half vector, promote it to a float vector.
	if (ConvertHalfVec)
	Input = convertVector(Input.get(), Context.FloatTy, *this);
	resultType = Input.get()->getType();

So the type of the value apparently does not depend on the signs (UO_PLUS or UO_MINUS). I'm not very familiar with Clang internals. Do you know why the minus sign doesn't make the type signed?

[nikic]

@aheejin Basically, because -unsigned is still unsigned, or -size_t is size_t in this particular case. (But -unsigned short is int due to promotion rules.)

[aheejin]

But we actually have a test case that tests folding a negative offset.. and it looks you added it 0564d06

[nikic]

Right. When I added that test wasm was just a convenient testing vector for the underlying SDAG representation, I didn't really consider whether there is anything wasm-specific to take into account here. Sorry about that.

Now that I re-read the bug report, it's possible that I misunderstood what the report is about. So let me try to clarify this: Is load with a "negative" number (alternative reading: a large unsigned number) malformed wasm, as in, will it result in some kind of validation or verifier error prior to execution? If yes, then we should prevent that with an additional non-negativity check. Or is it just that it does not have the semantics of performing negative indexing? If so, then there is nothing to do here -- the memory trap reported by OP is the expected outcome, because the code has undefined behavior.

[nikic]

Per https://webassembly.github.io/spec/core/syntax/instructions.html#memory-instructions it looks to me like the memarg offset is interpreted as u32, in which case current codegen would be correct. But maybe I'm reading the spec wrong.

[aheejin]

I think you are right. Negative values are read as a very large positive numbers, and that itself is not a validation failure. But it will trap if the resulting range exceeds the memory's size. See Step 10 in https://webassembly.github.io/spec/core/exec/instructions.html#t-mathsf-xref-syntax-instructions-syntax-instr-memory-mathsf-load-xref-syntax-instructions-syntax-memarg-mathit-memarg-and-t-mathsf-xref-syntax-instructions-syntax-instr-memory-mathsf-load-n-mathsf-xref-syntax-instructions-syntax-sx-mathit-sx-xref-syntax-instructions-syntax-memarg-mathit-memarg

Will close this as working as intended. @TerrorJack Feel free to reopen if there are things not addressed.

[TerrorJack]

Sorry, but would you re-open this issue since I don't have the rights to do so? @aheejin This is not working as intended, see the following assembly program:

.functype foo () -> (i32)
.globl foo
.export_name foo, foo
.section .text.f,"",@
foo:
  .functype foo () -> (i32)
  i32.const 8
  i32.load -4
  end_function

You can compile it with clang --target=wasm32 test.s -o test.wasm -nostdlib -Wl,--no-entry and run the exported foo function. Unfortunately, it produces a memory trap with both nodejs(v8) and bun(javascriptcore). There is no automatic wrapping of arithmetic plus of memory address and offset.