Bug 145820 – [DFG] Avoid OSR exit in the middle of string concatenation

• Status: RESOLVED
• Resolution: FIXED
• Component: JavaScriptCore

[Yusuke Suzuki]

From June 5, (as long as I can check in buildbot's history), JSC test: tagged-templates.js tes fails occasionally.
Picking up some failure samples, dfg-eager / ftl-eager fail.

https://build.webkit.org/builders/Apple%20Yosemite%20Release%20JSC%20%28Tests%29?numbuilds=200

[Yusuke Suzuki]

Reproduced by the following test.


function shouldBe(actual, expected) {
    if (actual !== expected)
        throw new Error('bad value: ' + JSON.stringify(actual));
}

function raw(siteObject) {
    var result = '';
    for (var i = 0; i < siteObject.raw.length; ++i) {
        result += siteObject.raw[i];
        if ((i + 1) < arguments.length) {
            result += arguments[i + 1];
        }
    }
    return result;
}

function Counter() {
    var count = 0;
    return {
        toString() {
            return count++;
        }
    };
}

for (var i = 0; i < 10000; ++i) {
    print(i);
    var c = Counter();
    shouldBe(raw`Hello ${c} World ${c}`, `Hello 0 World 1`);
}

[Yusuke Suzuki]

Now investigating...

[Yusuke Suzuki]

Hm, it looks this issue exists from the long ago. I'll check the compiled code.

[Yusuke Suzuki]

It fails in DFG phase. --useDFGJIT=false --useFTLJIT=false makes silent.

[Yusuke Suzuki]

tagged-template-less reproducing code.

function shouldBe(actual, expected) {
    if (actual !== expected)
        throw new Error('bad value: ' + JSON.stringify(actual));
}

function raw(siteObject) {
    var result = '';
    for (var i = 0; i < siteObject.raw.length; ++i) {
        result += siteObject.raw[i];
        if ((i + 1) < arguments.length) {
            result += arguments[i + 1];
        }
    }
    return result;
}

function Counter() {
    var count = 0;
    return {
        count: 0,
        toString() {
            return this.count++;
        }
    };
}

for (var i = 0; i < 10000; ++i) {
    var c = Counter();
    shouldBe(raw({ raw: ['Hello ', ' World ', ''] }, c, c), "Hello 0 World 1");
}

[Yusuke Suzuki]

Smaller code for reproduce

function shouldBe(actual, expected) {
    if (actual !== expected)
        throw new Error('bad value: ' + JSON.stringify(actual));
}

function raw(siteObject) {
    var result = '';
    for (var i = 0; i < arguments.length; ++i) {
        result += arguments[i];
    }
    return result;
}

function Counter() {
    return {
        count: 0,
        toString() {
            return this.count++;
        }
    };
}

for (var i = 0; i < 10000; ++i) {
    var c = Counter();
    shouldBe(raw(c, c), "01");
}

[Yusuke Suzuki]

Created attachment 254714 [details]
Patch

[Yusuke Suzuki]

Created attachment 254715 [details]
Patch

[Darin Adler]

Comment on attachment 254715 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=254715&action=review

I’m not the right reviewer for the strategy change here, but I do have one small comment.

> Source/JavaScriptCore/bytecode/SpeculatedType.h:87
> +static const SpeculatedType SpecPrimitive          = SpecFullNumber | SpecMisc | SpecString | SpecSymbol;

All the other combinations are written out in hex, not as expressions. Lets not be so different here.

[Yusuke Suzuki]

Created attachment 254843 [details]
Patch

[Yusuke Suzuki]

Comment on attachment 254715 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=254715&action=review

Thank you!

>> Source/JavaScriptCore/bytecode/SpeculatedType.h:87
>> +static const SpeculatedType SpecPrimitive          = SpecFullNumber | SpecMisc | SpecString | SpecSymbol;
> 
> All the other combinations are written out in hex, not as expressions. Lets not be so different here.

Fixed.

[Yusuke Suzuki]

Created attachment 254908 [details]
Patch

[Yusuke Suzuki]

The root cause of this issue is that,

ArithAdd for String:left is converted into

MakeRope(left, ToString(ToPrimitive(right)))

However, `ToPrimitive` may have observable side effect. (calling object.{valueOf,toString})
So if it is converted into

MakeRope(left, Check(String, ToPrimitive(right)))

And Check failed, OSR exit will be performed to the original ArithAdd bytecode point and it redundantly performs ToPrimitive observable execution.



To fix this issue fundamentally, I think we should introduce ToStringToPrimitive DFG bytecode because the above ToPrimitive and ToString is not splittable.
But this patch could fix the current situation because of the following 3 reasons.

1. ToPrimitive(SpecObject) case

When performing ToPrimitive(SpecObject), we speculate the result as the all primitive values conservatively in this patch. So ToString & ToPrimitive are not converted into Identity(Check:...) in Fixup phase. So OSR exit doesn't occur.

2. ToPrimitive(SpecString), but object comes

ToPrimitive(SpecString) will be converted into Check:String.
So before executing the observable side effect, OSR exit will be executed.

3. ToPrimitive(SpecString  | SpecInt32), but object comes

ToPrimitive and ToString have the almost same fixup in DFG Fixup phase.
And ToPrimitive(SpecString | SpecInt32) will propagate the same `SpecString | SpecInt32` as the result of ToPrimitive.
So, as a result, when ToString is converted into Check, ToPrimitive is also converted into Check. So before executing the observable side effect in ToPrimitive, OSR exit always occurs.

The problematic situation is (1) ToPrimitive performs observable side effect and it doesn't raise OSR exit, but, (2) ToString performs OSR exit. By this patch, this situation is avoided.

[Yusuke Suzuki]

Could anyone take a look?

[Filip Pizlo]

(In reply to comment #13)
> The root cause of this issue is that,
> 
> ArithAdd for String:left is converted into
> 
> MakeRope(left, ToString(ToPrimitive(right)))
> 
> However, `ToPrimitive` may have observable side effect. (calling
> object.{valueOf,toString})
> So if it is converted into
> 
> MakeRope(left, Check(String, ToPrimitive(right)))
> 
> And Check failed, OSR exit will be performed to the original ArithAdd
> bytecode point and it redundantly performs ToPrimitive observable execution.

The bug here is that ToString shouldn't have been converted to Check.

> 
> 
> 
> To fix this issue fundamentally, I think we should introduce
> ToStringToPrimitive DFG bytecode because the above ToPrimitive and ToString
> is not splittable.
> But this patch could fix the current situation because of the following 3
> reasons.
> 
> 1. ToPrimitive(SpecObject) case
> 
> When performing ToPrimitive(SpecObject), we speculate the result as the all
> primitive values conservatively in this patch. So ToString & ToPrimitive are
> not converted into Identity(Check:...) in Fixup phase. So OSR exit doesn't
> occur.
> 
> 2. ToPrimitive(SpecString), but object comes
> 
> ToPrimitive(SpecString) will be converted into Check:String.
> So before executing the observable side effect, OSR exit will be executed.
> 
> 3. ToPrimitive(SpecString  | SpecInt32), but object comes
> 
> ToPrimitive and ToString have the almost same fixup in DFG Fixup phase.
> And ToPrimitive(SpecString | SpecInt32) will propagate the same `SpecString
> | SpecInt32` as the result of ToPrimitive.
> So, as a result, when ToString is converted into Check, ToPrimitive is also
> converted into Check. So before executing the observable side effect in
> ToPrimitive, OSR exit always occurs.
> 
> The problematic situation is (1) ToPrimitive performs observable side effect
> and it doesn't raise OSR exit, but, (2) ToString performs OSR exit. By this
> patch, this situation is avoided.

Another possible correct solution is to use ValueAdd for cases like this.

[Filip Pizlo]

Comment on attachment 254908 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=254908&action=review

It's not obvious to me what bug this particular patch fixes.

> Source/JavaScriptCore/dfg/DFGFixupPhase.cpp:1481
> +            // FIXME: Since ToString and ToPrimitive are originated from the same bytecode and ToPrimitive
> +            // may have an observable side effect, inherently these DFG bytecodes are unsplittable; after
> +            // performing an observable side effect on ToPrimitive, ToString should not perform OSR exit.
> +            // Introducing combined, unsplittable DFG node ToPrimitiveToString could solve this situation.

No, we don't need a new node type.  The solution is just for FixupPhase not to turn the ToString into a check.

You don't have to worry about any phase after FixupPhase to turn the ToString into a check.  So, you only need to worry about what FixupPhase does.  You don't need new node types.

Also, it's likely that the best solution is just to use ValueAdd in cases where this problem would arise.

[Yusuke Suzuki]

Created attachment 255009 [details]
Patch

[Yusuke Suzuki]

Created attachment 255010 [details]
Patch

[Yusuke Suzuki]

Comment on attachment 254908 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=254908&action=review

Thanks!!

>> Source/JavaScriptCore/dfg/DFGFixupPhase.cpp:1481
>> +            // Introducing combined, unsplittable DFG node ToPrimitiveToString could solve this situation.
> 
> No, we don't need a new node type.  The solution is just for FixupPhase not to turn the ToString into a check.
> 
> You don't have to worry about any phase after FixupPhase to turn the ToString into a check.  So, you only need to worry about what FixupPhase does.  You don't need new node types.
> 
> Also, it's likely that the best solution is just to use ValueAdd in cases where this problem would arise.

Ah! I misunderstood about Fixup phase.
I thought fixup is iterated until it gets a fixed-point, but it iterate blocks only once.
So by avoiding fixing up onto ToString when generating it, we can solve this problem.

I think, using MakeRope(left, ToString(ToPrimitive(left))) is efficient than ValueAdd and keeping it is nice.

[Yusuke Suzuki]

Updated, could you take a look?

[WebKit Commit Bot]

Comment on attachment 255010 [details]
Patch

Clearing flags on attachment: 255010

Committed r185728: <http://trac.webkit.org/changeset/185728>

[WebKit Commit Bot]

All reviewed patches have been landed.  Closing bug.