Out of bounds memory access with Os & BINARYEN_IGNORE_IMPLICIT_TRAPS=1

[tklajnscek]

Compiling the following program with 1.38.37 fastcomp using
emcc -Os -s BINARYEN_IGNORE_IMPLICIT_TRAPS=1 test.cpp -o test.js
causes the program to misbehave and crash with
RuntimeError: memory access out of bounds

The optimizer removes the conditional surrounding the access to dontAccess and merges it all into one block.

Here's the minimal repro code:

int len = 0;
unsigned* dontAccess = 0;

int main() {
   if (len == 0 || dontAccess[len - 1]) {
      len += 1;
   }
   return 0;
}

Omitting BINARYEN_IGNORE_IMPLICIT_TRAPS or changing the optimization level to e.g. O3 fixes it.
Here's the WAST output of the working version. Notice the nested ifs.

func (result i32)
(local i32)
  i32.const 1024
  i32.load offset=0 align=4
  tee_local 0
  if <== CHECK IF LEN IS NON-ZERO AND AVOID ACCESSING THE ARRAY
    get_local 0
    i32.const -1
    i32.add
    i32.const 2
    i32.shl
    i32.load offset=0 align=4
    i32.eqz
    if
      i32.const 0
      return
    end
  end
  i32.const 1024
  get_local 0
  i32.const 1
  i32.add
  i32.store offset=0 align=4
  i32.const 0
end

Here's the WAST output from the failing case. The ifs have been flattened and both memory accesses always happen unconditionally (to len and to the start of dontAccess) causing an invalid memory read.

func (result i32)
(local i32)
  i32.const 1024
  i32.load offset=0 align=4
  tee_local 0
  i32.eqz <== CHECK IF LEN IS ZERO 
  get_local 0
  i32.const -1
  i32.add
  i32.const 2
  i32.shl
  i32.load offset=0 align=4 <== THIS CRASHES
  i32.or <== NAIVELY OR THE RESULTS OF BOTH COMPARISONS
  if
    i32.const 1024
    get_local 0
    i32.const 1
    i32.add
    i32.store offset=0 align=4
  end
  i32.const 0
end

This does work with the latest upstream Clang 9 based Emscripten, but I think it's still worth investigating since the upstream doesn't seem to be read for prime time yet.

[sbc100]

Upstream clang should be ready for prime time now. Please start using it if you can.

We are hoping to start the process of deprecating fastcomp as soon as possible. For this reason I think its unlikely this will get fixed.

[kripken]

Yes, as @sbc100 said, upstream should be ready now.

But going back to the testcase, this is actually that BINARYEN_IGNORE_IMPLICIT_TRAPS flag behaving as expected on fastcomp: it is ignoring the possible trap from the load, which allows it to compress the code more. But this code is exactly a case of where that option can lead to bad results.

So it's actually surprising that the wasm backend doesn't show the bug! Looking into that, there are 2 issues:

• We forgot to pass the flag there :( fix in Support BINARYEN_IGNORE_IMPLICIT_TRAPS in the wasm backend #8946
• The binaryen optimizer happens to not optimize the specific pattern seen here - in asm2wasm we have br_if br_if, which with the wasm backend it's if br_if - I'll look into adding support for that.

[tklajnscek]

First of all, thanks for the quick response guys!

We're definitely eager to switch to upstream, but still waiting on a few fixes before we go all in on it (e.g. #8905 & #8879).

As for the BINARYEN_IGNORE_IMPLICIT_TRAPS flag it was our understanding that it was about ignoring e.g. loads out of bounds that are not checked for and not emitting code that would handle those to settle any differences between ASM.JS/WASM and C/C++. What you're saying is that it's actually changing the behavior of the language in breaking ways - i.e. in this case it's removing short circuiting guarantees made by the C/C++ standards, making this a very dangerous option that should probably not be used on any non-trivial piece of code.

E.g. from the C++ standard, 5.14.1:
(The && operator groups left-to-right. The operands are both contextually converted to type bool (Clause 4). The result is true if both operands are true and false otherwise. Unlike &, && guarantees left-to-right evaluation: the second operand is not evaluated if the first operand is false.

I guess for us it just means we turn this flag off, but you might want to make the comment in settings a bit more explicit about it breaking the standard, giving more warning to potential users that this flag is likely to cause perfectly valid code to fail unexpectedly :)

Can you comment a bit more on what the intended use cases for this flag were and what we're losing out on by not using it?

Thanks again!

[kripken]

it's removing short circuiting guarantees made by the C/C++ standards, making this a very dangerous option that should probably not be used on any non-trivial piece of code.

Correct - this flag is not safe in general. It simply tells the binaryen optimizer "nothing will trap, ever" (except for an explicit unreachable instruction, but nothing implicit). So as you said, it is not safe for general C/C++ code, you must be very careful in using it.

Note that it doesn't break the && semantics in a general sense - we still handle side effects, that is, f() && g() will not unconditionally do both calls. The only change is that we assume there are no implicit traps, which means we ignore a specific set of side effects. In this case, we assume that loads have no side effects.

You aren't missing much by not enabling this feature - maybe a percent or so of code, last I checked. That's why it's off by default, and we don't recommend people enable it. But there are small/simple codebases where it is helpful and every byte matters.

[kripken]

And thanks, yes, the docs were not clear enough. I opened #8957 for that.