Bug 145820 - [DFG] Avoid OSR exit in the middle of string concatenation
Summary: [DFG] Avoid OSR exit in the middle of string concatenation
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: JavaScriptCore (show other bugs)
Version: 528+ (Nightly build)
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Yusuke Suzuki
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2015-06-09 15:13 PDT by Yusuke Suzuki
Modified: 2015-06-18 16:45 PDT (History)
9 users (show)

See Also:


Attachments
Patch (6.69 KB, patch)
2015-06-11 04:49 PDT, Yusuke Suzuki
no flags Details | Formatted Diff | Diff
Patch (6.70 KB, patch)
2015-06-11 04:53 PDT, Yusuke Suzuki
no flags Details | Formatted Diff | Diff
Patch (6.71 KB, patch)
2015-06-12 18:08 PDT, Yusuke Suzuki
no flags Details | Formatted Diff | Diff
Patch (9.77 KB, patch)
2015-06-15 17:05 PDT, Yusuke Suzuki
no flags Details | Formatted Diff | Diff
Patch (3.83 KB, patch)
2015-06-17 02:50 PDT, Yusuke Suzuki
no flags Details | Formatted Diff | Diff
Patch (3.84 KB, patch)
2015-06-17 02:52 PDT, Yusuke Suzuki
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Yusuke Suzuki 2015-06-09 15:13:56 PDT
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
Comment 1 Yusuke Suzuki 2015-06-09 15:54:53 PDT
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`);
}
Comment 2 Yusuke Suzuki 2015-06-09 16:00:42 PDT
Now investigating...
Comment 3 Yusuke Suzuki 2015-06-09 16:04:50 PDT
Hm, it looks this issue exists from the long ago. I'll check the compiled code.
Comment 4 Yusuke Suzuki 2015-06-09 16:09:03 PDT
It fails in DFG phase. --useDFGJIT=false --useFTLJIT=false makes silent.
Comment 5 Yusuke Suzuki 2015-06-09 16:29:28 PDT
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");
}
Comment 6 Yusuke Suzuki 2015-06-09 16:34:45 PDT
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");
}
Comment 7 Yusuke Suzuki 2015-06-11 04:49:51 PDT
Created attachment 254714 [details]
Patch
Comment 8 Yusuke Suzuki 2015-06-11 04:53:25 PDT
Created attachment 254715 [details]
Patch
Comment 9 Darin Adler 2015-06-12 09:56:15 PDT
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.
Comment 10 Yusuke Suzuki 2015-06-12 18:08:41 PDT
Created attachment 254843 [details]
Patch
Comment 11 Yusuke Suzuki 2015-06-12 18:09:19 PDT
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.
Comment 12 Yusuke Suzuki 2015-06-15 17:05:30 PDT
Created attachment 254908 [details]
Patch
Comment 13 Yusuke Suzuki 2015-06-15 17:05:49 PDT
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.
Comment 14 Yusuke Suzuki 2015-06-16 16:55:15 PDT
Could anyone take a look?
Comment 15 Filip Pizlo 2015-06-16 17:08:56 PDT
(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.
Comment 16 Filip Pizlo 2015-06-16 17:12:21 PDT
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.
Comment 17 Yusuke Suzuki 2015-06-17 02:50:41 PDT
Created attachment 255009 [details]
Patch
Comment 18 Yusuke Suzuki 2015-06-17 02:52:14 PDT
Created attachment 255010 [details]
Patch
Comment 19 Yusuke Suzuki 2015-06-17 02:54:07 PDT
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.
Comment 20 Yusuke Suzuki 2015-06-18 11:46:04 PDT
Updated, could you take a look?
Comment 21 WebKit Commit Bot 2015-06-18 16:45:49 PDT
Comment on attachment 255010 [details]
Patch

Clearing flags on attachment: 255010

Committed r185728: <http://trac.webkit.org/changeset/185728>
Comment 22 WebKit Commit Bot 2015-06-18 16:45:54 PDT
All reviewed patches have been landed.  Closing bug.