ByteCode Updward Exposed mismatch after DeadStore

[shsirk]

Git Commit: 861a276
Ubuntu 18.04

PoC:

  const obj = { };

  var a = { toString: ()=> {} };

  function opt(o, zz) {
    function foo () {
      String.prototype.replace.call(o, zz, obj);
    }
    foo ();
  }
  opt({}, "zzz");
  for (let xi = 0; xi < 500; xi++) {
    opt({}, "kkkk");
  }

opt(a, "llll")

Assertion failed in debug and segfault in release (possible null pointer dereference)

ByteCode Updward Exposed mismatch after DeadStore
Mismatch Instr:
    s32.var         =  Coerce_StrOrRegex  s21[LikelyCanBeTaggedValue_String].var! #0029 

ByteCode Updward Exposed mismatch after DeadStore
 Mismatch Instr:
 Bailout: #0029   (BailOutOnImplicitCallsPreOp)
   ByteCode Register list present before Backward pass missing in DeadStore pass:
s53    R5
ASSERT.ION var26087: ( /tmp/media/code/ChakraCore/lib/Backend/BackwardPass.cpp, line  8936) ByteCode Updward Exposed Used Mismatch
 Failure:  (false)
     Illegal instruction

stack:

#0  0x000055555a82bd66 in BackwardPass::VerifyByteCodeUpwardExposed (this=0x154d4dbf4e00, block=0x15554ea562b0, func=0x154d4dbf6d00, trackingByteCodeUpwardExposedUsed=0x15554ea584a0, instr=0x15554ea5ac40, bytecodeOffset=41) at /tmp/media/code/ChakraCore/lib/Backend/BackwardPass.cpp:8936
#1  0x000055555a820c0f in BackwardPass::ProcessBailOutInfo (this=0x154d4dbf4e00, instr=0x15554ea5ac40, bailOutInfo=0x15554ea5ab20) at /tmp/media/code/ChakraCore/lib/Backend/BackwardPass.cpp:2714
#2  0x000055555a82b0bd in BackwardPass::ProcessPendingPreOpBailOutInfo (this=0x154d4dbf4e00, currentInstr=0x15554ea5ac40) at /tmp/media/code/ChakraCore/lib/Backend/BackwardPass.cpp:2612
#3  0x000055555a812e4a in BackwardPass::ProcessBlock (this=0x154d4dbf4e00, block=0x15554ea562b0) at /tmp/media/code/ChakraCore/lib/Backend/BackwardPass.cpp:3886
#4  0x000055555a7f5f25 in BackwardPass::OptBlock (this=0x154d4dbf4e00, block=0x15554ea562b0) at /tmp/media/code/ChakraCore/lib/Backend/BackwardPass.cpp:1711
#5  0x000055555a7f5168 in BackwardPass::Optimize (this=0x154d4dbf4e00) at /tmp/media/code/ChakraCore/lib/Backend/BackwardPass.cpp:430
#6  0x000055555a1a20fb in GlobOpt::BackwardPass (this=0x154d4dbf5aa0, tag=Js::Phase::DeadStorePhase) at /tmp/media/code/ChakraCore/lib/Backend/GlobOpt.cpp:159
#7  0x000055555a1a3087 in GlobOpt::Optimize (this=0x154d4dbf5aa0) at /tmp/media/code/ChakraCore/lib/Backend/GlobOpt.cpp:212
#8  0x000055555a13a586 in Func::TryCodegen (this=0x154d4dbf6d00) at /tmp/media/code/ChakraCore/lib/Backend/Func.cpp:456
#9  0x000055555a138da2 in Func::Codegen (alloc=0x154d4dbf75a0, workItem=0x15554ea41030, threadContextInfo=0x623000000198, scriptContextInfo=0x622000000158, outputData=0x154d4dbf7b90, epInfo=0x15554ec381b0, runtimeInfo=0x0, polymorphicInlineCacheInfo=0x15554ea88420, codeGenAllocators=0x61a0000006d8, codeGenProfiler=0x0, isBackgroundJIT=true) at /tmp/media/code/ChakraCore/lib/Backend/Func.cpp:324
#10 0x0000555559b323c3 in NativeCodeGenerator::CodeGen (this=0x613000000798, pageAllocator=0x615000002678, workItemData=0x612000000540, jitWriteData=..., foreground=false, epInfo=0x15554ec381b0) at /tmp/media/code/ChakraCore/lib/Backend/NativeCodeGenerator.cpp:894
#11 0x0000555559b3658f in NativeCodeGenerator::CodeGen (this=0x613000000798, pageAllocator=0x615000002678, workItem=0x612000000518, foreground=false) at /tmp/media/code/ChakraCore/lib/Backend/NativeCodeGenerator.cpp:1011
#12 0x0000555559b3d6d8 in NativeCodeGenerator::Process (this=0x613000000798, job=0x612000000520, threadData=0x615000002658) at /tmp/media/code/ChakraCore/lib/Backend/NativeCodeGenerator.cpp:1911
#13 0x0000555559c800b4 in JsUtil::BackgroundJobProcessor::Process (this=0x612000000218, job=0x612000000520, threadData=0x615000002658) at /tmp/media/code/ChakraCore/lib/Common/Common/Jobs.cpp:1037
#14 0x0000555559c810ca in JsUtil::BackgroundJobProcessor::Run (this=0x612000000218, threadData=0x615000002658) at /tmp/media/code/ChakraCore/lib/Common/Common/Jobs.cpp:1135
#15 0x0000555559c77f3f in JsUtil::BackgroundJobProcessor::StaticThreadProc (lpParam=0x615000002658) at /tmp/media/code/ChakraCore/lib/Common/Common/Jobs.cpp:1319
#16 0x000055555666c87d in CorUnix::CPalThread::ThreadEntry (pvParam=0x61c000001880) at /tmp/media/code/ChakraCore/pal/src/thread/pal_thread.cpp:1605
#17 0x00001555548bb6db in start_thread (arg=0x154d4dbf9700) at pthread_create.c:463
#18 0x0000155553c22a3f in clone () at ../sysdeps/unix/sysv/linux/x86_64/clone.S:95

[ppenzin]

Confirming on both Windows and Linux. Edit: I am going to investigate, though cannot promise that it would be very quick.

[rhuanjl]

This likely stems from this PR #6232

The method for tracking register lifetimes in the JIT was changed there and this test case seems to be hitting a code path that was missed in those changes.

Following that change I think the JIT is meant to rely slightly more on info from the bytecode BUT Coerce_StrOrRegex is a backend only opcode - added in the optimiser - so perhaps whatever info is needed from the bytecode isn't there/needs to be sorted when the opcode is added.

Bizarrely running the snippet with -dump:backend to print out all the optimiser steps suppresses the error, considering this is not meant to do anything different other than add logging that doesn't make much sense.

[rhuanjl]

In my testing of jitting Async Generators I have hit a very similar looking assert jitting yield* my fix was this:
d1a02a5

A set of changes that add several lines to the bytecode but do nothing detectably different in the interpretor - however in the JIT this prevented segfaulting/hitting an assert about register lifetimes.

The Coerce_StrOrRegex is likely added here: https://github.com/microsoft/ChakraCore/blob/7d4bdd821d452d6b91a21936257d7e352ea7dc4b/lib/Backend/Inline.cpp#L3871

But without more digging I don't know what would need to be changed to ensure the registers associated with that instruction get matching lifetimes.

[ppenzin]

Slightly reduced test:

function opt(o, zz) {
  function foo () {
    String.prototype.replace.call(o, zz, {});
  }
  foo ();
}

for (let xi = 0; xi < 500; xi++) {
  opt({}, "kkkk");
}

[rhuanjl]

Could this be related to these which hit similar assertions: #6181 #6487

Extra note: done some more digging into these 3 issues - in all 3 it seems that the assertion is that information being tracked for use in BailOut paths has the wrong lifetime - so on a release/test build if you then hit the bailout you end up with nullptr de-ref after dropping into the interpreter.

In the original example here steps for segfault:

1. The last call of opt: opt(a, "llll"); Results in supplying a as the this value for String.prototype.replace.call
2. String.prototype.replace was inlined so begins with a coerce_str instruction on its this which is a
3. BUT as a has a toString method we hit a BailOutOnImplicitCallsPreOp.
4. Having dropped down into the interpreter it attempts a normal call of String.prototype.replace.call
5. BUT the this value supplied to String.prototype.replace is a nullptr - presumably due to the mismatched lifetime.

EDIT: whilst I got somewhat carried away looking at this and can explain the result of the problem I've still got no idea as to why it's going wrong - beyond noting that this error doesn't appear to be in 1.11 and my best guess remains that it was somehow introduced by #6232

[rhuanjl]

A bit more thinking about this - #6181 is exactly the same idea - inlining a regex related call, adding the coercion methods and losing the register tracking for bailout. #6487 worries me a little more because it's a register for a bailonnoprofile that it's losing but I can't work out which bailonnoprofile - so don't even know where it's going wrong.

As a related point the commit I linked above for Async Generators was again the same concept though in that case I think it was a register for the NewAsyncFromSyncIterator opcode that was getting lost in the bailoutpath - that did not involve string or regex coercion - though possibly relevant the version that failed involved an op with the same register for it's source and destination, the fix (I haven't merged) was adding in extra registers so that source and destination were not the same - I don't however see why this should be a problem.

What's alarming about all of these taken together is it feels like we have a category of errors here not a single obvious issue - and I'd be surprised if there aren't many more we haven't located yet.

[ppenzin]

#6181 looks suspiciously similar to this one, I still need to take a closer look at #6487. Obvious question - are we releasing this when we inline a regex call, as if it can only be invoked as str.foo(...) (forgetting that it is possible to do foo.call(str, ...)).

By the way, what is the expected optimization "lifecycle" in this case - wouldn't ending up with a bailout defeat the purpose of inlining the call?

[rhuanjl]

The bailout in this one is a BailOnImplicitCall - the optimisation becomes invalid if converting to a string has an implicit call (that may have a side effect).

The optimised code works for:
opt({}, "kkkk");

The bailout is hit with the later call:
opt(a, "llll")

The assertion is when creating the bailout warning that it’s going to have a problem.

My speculation is that this is an example of a wider issue whenever there is a bailout path related to an operation which uses the same register as both src and dst - hence the link with the async generator related commit I linked as well as #6487

[ppenzin]

I agree, there might be something more fundamental here. Part of the problem is that we set liveness in a semi-manual way, which is somewhat error prone.

[rhuanjl]

I had guessed wrong on the PR that introduced this bug. I've now done git bisect to locate it.

This crash was introduced by this PR: #5854

The PR worked on inlining more functions invoked by .call() and .apply() so it looks like this issue really just relates to .call() and hence is the same issue as #6181 but is not related to #6487 I'll look at that one separately.

[ppenzin]

I've narrowed the it down to BytecodeArgOutCapture or the load after it getting eliminated by deadstore. #5854 seems to be closer to home than what we originally thought, thanks for finding it!

[ppenzin]

Changing the parameter to ...replace.call to explicit argument makes the error disappear:

function opt(o, zz) {
  function foo (o) {
    String.prototype.replace.call(o, zz, {});
  }
  foo (o);
}

for (let xi = 0; xi < 500; xi++) {
  opt({}, "kkkk");
}

AFAIK this is the same reg that is getting deleted by backward pass later.

[rhuanjl]

I've taken another little look at this, still not solved it BUT I think I understand it slightly more...

When .match() .replace or .exec() is being inlined the logic here wraps some of its arguments with Coerce_Str OR Coerce_Regex or Coerce_StrOrRegex, these methods attach a PreOp bailout, so that if converting the argument into a String or Regex (depending on which method) is going to have any side-effect the jitted code will bail out.

ChakraCore/lib/Backend/Inline.cpp

Lines 3829 to 3912 in 5f53f55

	Inline::WrapArgsOutWithCoerse(Js::BuiltinFunction builtInId, IR::Instr* callInstr)
	{
	switch (builtInId)
	{
	case Js::BuiltinFunction::JavascriptString_Match:
	callInstr->ForEachCallDirectArgOutInstrBackward([&](IR::Instr *argOutInstr, uint argNum)
	{
	IR::Instr * newInstr = nullptr;
	bool isPreOpBailOutNeeded = false;
	if (argNum == 0)
	{
	newInstr = argOutInstr->HoistSrc1(Js::OpCode::Coerce_Str);
	isPreOpBailOutNeeded = true;
	newInstr->GetDst()->SetValueType(ValueType::String);
	newInstr->SetSrc2(IR::AddrOpnd::New(newInstr->m_func->GetThreadContextInfo()->GetStringMatchNameAddr(), IR::AddrOpndKindSz, newInstr->m_func));
	argOutInstr->GetSrc1()->SetValueType(ValueType::String);
	}
	else if (argNum == 1)
	{
	newInstr = argOutInstr->HoistSrc1(Js::OpCode::Coerce_Regex);
	isPreOpBailOutNeeded = true;
	}
	if (isPreOpBailOutNeeded)
	{
	newInstr->SetByteCodeOffset(argOutInstr);
	newInstr->forcePreOpBailOutIfNeeded = true;
	}
	return false;
	}, 2);
	break;
	case Js::BuiltinFunction::JavascriptString_Replace:
	callInstr->ForEachCallDirectArgOutInstrBackward([&](IR::Instr *argOutInstr, uint argNum)
	{
	IR::Instr * newInstr = nullptr;
	bool isPreOpBailOutNeeded = false;
	if (argNum == 0)
	{
	newInstr = argOutInstr->HoistSrc1(Js::OpCode::Coerce_Str);
	isPreOpBailOutNeeded = true;
	newInstr->GetDst()->SetValueType(ValueType::String);
	newInstr->SetSrc2(IR::AddrOpnd::New(newInstr->m_func->GetThreadContextInfo()->GetStringReplaceNameAddr(), IR::AddrOpndKindSz, newInstr->m_func));
	argOutInstr->GetSrc1()->SetValueType(ValueType::String);
	}
	if (argNum == 1)
	{
	newInstr = argOutInstr->HoistSrc1(Js::OpCode::Coerce_StrOrRegex);
	isPreOpBailOutNeeded = true;
	}
	if (isPreOpBailOutNeeded)
	{
	newInstr->SetByteCodeOffset(argOutInstr);
	newInstr->forcePreOpBailOutIfNeeded = true;
	}
	return false;
	}, 3);
	break;
	case Js::BuiltinFunction::JavascriptRegExp_Exec:
	callInstr->ForEachCallDirectArgOutInstrBackward([&](IR::Instr *argOutInstr, uint argNum)
	{
	IR::Instr * newInstr = nullptr;
	bool isPreOpBailOutNeeded = false;
	if (argNum == 0)
	{
	newInstr = argOutInstr->HoistSrc1(Js::OpCode::Coerce_Regex);
	isPreOpBailOutNeeded = true;
	}
	else if (argNum == 1)
	{
	newInstr = argOutInstr->HoistSrc1(Js::OpCode::Conv_Str);
	newInstr->GetDst()->SetValueType(ValueType::String);
	argOutInstr->GetSrc1()->SetValueType(ValueType::String);
	isPreOpBailOutNeeded = true;
	}
	if (isPreOpBailOutNeeded)
	{
	newInstr->SetByteCodeOffset(argOutInstr);
	newInstr->forcePreOpBailOutIfNeeded = true;
	}
	return false;
	}, 2);
	break;
	}
	}

If the jitted code bails out then the values of the original arguments need to be available for the interpreter to call the original function. They are marked with ByteCodeUses so that they're not completely optimised away.

However I think wrapping them in these coercion methods somehow messes up the bookkeeping for whether ByteCodeUses is necessary. The BackwardPass thinks it is not BUT a debug assertion has information that proves that it is and hence complains.

In a non-debug build the jitted code will be produced and run AND all is fine unless it BailsOut, upon bailout you hit a segfault (which is what the Assertion is warning about).