Bug 118546 – CodeBlocks should be able to determine bytecode liveness

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

[Mark Hahnenberg]

This would simplify some things in the DFG related to OSR exits and determining which bytecode variables are live at which points during execution. It would also be useful for making our conservative GC scan more precise.

[Mark Hahnenberg]

Created attachment 206423 [details]
Patch

[Mark Hahnenberg]

(In reply to comment #1)
> Created an attachment (id=206423) [details]
> Patch

This is a first draft. There's a couple rough edges still, e.g. some instructions I'm not sure about when calculated uses and defs. I'd like to start getting feedback though.

[Mark Hahnenberg]

> calculated 
calculating

[Mark Hahnenberg]

One thing is that I have two separate maps for liveness-in and liveness-out. An alternative would have been to say that liveness[bytecodeOffset] is for liveness-in at bytecodeOffset and liveness[bytecodeOffset + bytecodeLength] is for liveness-out at bytecodeOffset (which also corresponds to liveness-in for the next bytecode after bytecodeOffset). 

I avoided this because basic block boundaries seem like they pose a problem in that the next bytecode after bytecodeOffset, by virtue of being at the head of a basic block, could have multiple sources for liveness-in and I could potentially overwrite that with the "out" of the last instruction from the preceding block. By maintaining separate maps I side-stepped this issue. I suppose I could unify the maps at the end of processing since there's a lot of duplicate information in them.

[Mark Hahnenberg]

Created attachment 208147 [details]
Patch

[WebKit Commit Bot]

Attachment 208147 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/JavaScriptCore/ChangeLog', u'Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj', u'Source/JavaScriptCore/bytecode/BytecodeBasicBlock.cpp', u'Source/JavaScriptCore/bytecode/BytecodeBasicBlock.h', u'Source/JavaScriptCore/bytecode/BytecodeLivenessAnalysis.cpp', u'Source/JavaScriptCore/bytecode/BytecodeLivenessAnalysis.h', u'Source/JavaScriptCore/bytecode/CodeBlock.cpp', u'Source/JavaScriptCore/bytecode/CodeBlock.h', u'Source/JavaScriptCore/bytecode/PreciseJumpTargets.cpp', u'Source/JavaScriptCore/bytecode/PreciseJumpTargets.h', u'Source/JavaScriptCore/heap/Heap.cpp', u'Source/JavaScriptCore/interpreter/JSStack.cpp', u'Source/JavaScriptCore/runtime/Options.cpp', u'Source/JavaScriptCore/runtime/Options.h']" exit_code: 1
Source/JavaScriptCore/interpreter/JSStack.cpp:33:  Alphabetical sorting problem.  [build/include_order] [4]
Total errors found: 1 in 14 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Early Warning System Bot]

Comment on attachment 208147 [details]
Patch

Attachment 208147 [details] did not pass qt-ews (qt):
Output: http://webkit-queues.appspot.com/results/1363081

[Early Warning System Bot]

Comment on attachment 208147 [details]
Patch

Attachment 208147 [details] did not pass qt-wk2-ews (qt-wk2):
Output: http://webkit-queues.appspot.com/results/1370297

[Filip Pizlo]

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

> Source/JavaScriptCore/bytecode/BytecodeLivenessAnalysis.cpp:75
> +        && (!numberOfCapturedVariables(codeBlock) // If we have no captured variables, we're good to go.
> +        || (operand < captureStart(codeBlock) // If we have captured variables but the operand is outside of the captured range, we're good to go.
> +        || operand >= captureEnd(codeBlock)));

Indent the || four spaces, since it's within the parantheses on line 73.  Also, doesn't CodeBlock have an isCaptured() method?  If it doesn't, it might be cool to give it that.

> Source/JavaScriptCore/bytecode/BytecodeLivenessAnalysis.cpp:501
> +    for (unsigned i = 0; i < basicBlocks.size(); i++) {
> +        if (leaderOffset == basicBlocks[i]->leaderBytecodeOffset())
> +            return basicBlocks[i].get();
> +    }

WTF binary search?

> Source/JavaScriptCore/bytecode/BytecodeLivenessAnalysis.cpp:512
> +    for (unsigned i = 0; i < basicBlocks.size(); i++) {
> +        BytecodeBasicBlock* block = basicBlocks[i].get();
> +        if (bytecodeOffset >= block->leaderBytecodeOffset() && bytecodeOffset < block->leaderBytecodeOffset() + block->totalBytecodeLength())
> +            return block;
> +    }
> +    return 0;

ditto

[Filip Pizlo]

Comment on attachment 208147 [details]
Patch

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

> Source/JavaScriptCore/bytecode/BytecodeLivenessAnalysis.cpp:75
> +        && (!numberOfCapturedVariables(codeBlock) // If we have no captured variables, we're good to go.
> +        || (operand < captureStart(codeBlock) // If we have captured variables but the operand is outside of the captured range, we're good to go.
> +        || operand >= captureEnd(codeBlock)));

Indent the || four spaces, since it's within the parantheses on line 73.  Also, doesn't CodeBlock have an isCaptured() method?  If it doesn't, it might be cool to give it that.

> Source/JavaScriptCore/bytecode/BytecodeLivenessAnalysis.cpp:501
> +    for (unsigned i = 0; i < basicBlocks.size(); i++) {
> +        if (leaderOffset == basicBlocks[i]->leaderBytecodeOffset())
> +            return basicBlocks[i].get();
> +    }

WTF binary search?

> Source/JavaScriptCore/bytecode/BytecodeLivenessAnalysis.cpp:512
> +    for (unsigned i = 0; i < basicBlocks.size(); i++) {
> +        BytecodeBasicBlock* block = basicBlocks[i].get();
> +        if (bytecodeOffset >= block->leaderBytecodeOffset() && bytecodeOffset < block->leaderBytecodeOffset() + block->totalBytecodeLength())
> +            return block;
> +    }
> +    return 0;

ditto

[EFL EWS Bot]

Comment on attachment 208147 [details]
Patch

Attachment 208147 [details] did not pass efl-wk2-ews (efl-wk2):
Output: http://webkit-queues.appspot.com/results/1346078

[EFL EWS Bot]

Comment on attachment 208147 [details]
Patch

Attachment 208147 [details] did not pass efl-ews (efl):
Output: http://webkit-queues.appspot.com/results/1362055

[kov's GTK+ EWS bot]

Comment on attachment 208147 [details]
Patch

Attachment 208147 [details] did not pass gtk-ews (gtk):
Output: http://webkit-queues.appspot.com/results/1397010

[kov's GTK+ EWS bot]

Comment on attachment 208147 [details]
Patch

Attachment 208147 [details] did not pass gtk-wk2-ews (gtk-wk2):
Output: http://webkit-queues.appspot.com/results/1351016

[Mark Hahnenberg]

Created attachment 208295 [details]
Patch

[WebKit Commit Bot]

Attachment 208295 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/JavaScriptCore/CMakeLists.txt', u'Source/JavaScriptCore/ChangeLog', u'Source/JavaScriptCore/GNUmakefile.list.am', u'Source/JavaScriptCore/JavaScriptCore.vcxproj/JavaScriptCore.vcxproj', u'Source/JavaScriptCore/JavaScriptCore.vcxproj/JavaScriptCore.vcxproj.filters', u'Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj', u'Source/JavaScriptCore/Target.pri', u'Source/JavaScriptCore/bytecode/BytecodeBasicBlock.cpp', u'Source/JavaScriptCore/bytecode/BytecodeBasicBlock.h', u'Source/JavaScriptCore/bytecode/BytecodeLivenessAnalysis.cpp', u'Source/JavaScriptCore/bytecode/BytecodeLivenessAnalysis.h', u'Source/JavaScriptCore/bytecode/CodeBlock.cpp', u'Source/JavaScriptCore/bytecode/CodeBlock.h', u'Source/JavaScriptCore/bytecode/PreciseJumpTargets.cpp', u'Source/JavaScriptCore/bytecode/PreciseJumpTargets.h', u'Source/JavaScriptCore/heap/Heap.cpp', u'Source/JavaScriptCore/interpreter/JSStack.cpp', u'Source/JavaScriptCore/runtime/Options.h']" exit_code: 1
Source/JavaScriptCore/interpreter/JSStack.cpp:33:  Alphabetical sorting problem.  [build/include_order] [4]
Total errors found: 1 in 18 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Early Warning System Bot]

Comment on attachment 208295 [details]
Patch

Attachment 208295 [details] did not pass qt-ews (qt):
Output: http://webkit-queues.appspot.com/results/1382307

[Early Warning System Bot]

Comment on attachment 208295 [details]
Patch

Attachment 208295 [details] did not pass qt-wk2-ews (qt-wk2):
Output: http://webkit-queues.appspot.com/results/1382306

[EFL EWS Bot]

Comment on attachment 208295 [details]
Patch

Attachment 208295 [details] did not pass efl-wk2-ews (efl-wk2):
Output: http://webkit-queues.appspot.com/results/1377336

[Mark Hahnenberg]

Created attachment 208296 [details]
Patch

[WebKit Commit Bot]

Attachment 208296 [details] did not pass style-queue:

Failed to run "['Tools/Scripts/check-webkit-style', '--diff-files', u'Source/JavaScriptCore/CMakeLists.txt', u'Source/JavaScriptCore/ChangeLog', u'Source/JavaScriptCore/GNUmakefile.list.am', u'Source/JavaScriptCore/JavaScriptCore.vcxproj/JavaScriptCore.vcxproj', u'Source/JavaScriptCore/JavaScriptCore.vcxproj/JavaScriptCore.vcxproj.filters', u'Source/JavaScriptCore/JavaScriptCore.xcodeproj/project.pbxproj', u'Source/JavaScriptCore/Target.pri', u'Source/JavaScriptCore/bytecode/BytecodeBasicBlock.cpp', u'Source/JavaScriptCore/bytecode/BytecodeBasicBlock.h', u'Source/JavaScriptCore/bytecode/BytecodeLivenessAnalysis.cpp', u'Source/JavaScriptCore/bytecode/BytecodeLivenessAnalysis.h', u'Source/JavaScriptCore/bytecode/CodeBlock.cpp', u'Source/JavaScriptCore/bytecode/CodeBlock.h', u'Source/JavaScriptCore/bytecode/PreciseJumpTargets.cpp', u'Source/JavaScriptCore/bytecode/PreciseJumpTargets.h', u'Source/JavaScriptCore/heap/Heap.cpp', u'Source/JavaScriptCore/interpreter/JSStack.cpp', u'Source/JavaScriptCore/runtime/Options.h', u'Source/WTF/wtf/FastBitVector.h']" exit_code: 1
Source/JavaScriptCore/interpreter/JSStack.cpp:33:  Alphabetical sorting problem.  [build/include_order] [4]
Total errors found: 1 in 19 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[EFL EWS Bot]

Comment on attachment 208296 [details]
Patch

Attachment 208296 [details] did not pass efl-wk2-ews (efl-wk2):
Output: http://webkit-queues.appspot.com/results/1379360

[Oliver Hunt]

Comment on attachment 208296 [details]
Patch

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

r=me, but remove the silly bits :0

> Source/JavaScriptCore/heap/Heap.cpp:57
> +#define ENABLE_GC_LOGGING 1

nope :)

>> Source/JavaScriptCore/interpreter/JSStack.cpp:33
>> +#include "CallFrameInlines.h"
> 
> Alphabetical sorting problem.  [build/include_order] [4]

fix :)

[Mark Hahnenberg]

Created attachment 216700 [details]
Patch

[EFL EWS Bot]

Comment on attachment 216700 [details]
Patch

Attachment 216700 [details] did not pass efl-ews (efl):
Output: http://webkit-queues.appspot.com/results/22779678

[Filip Pizlo]

Comment on attachment 216700 [details]
Patch

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

> Source/JavaScriptCore/bytecode/BytecodeLivenessAnalysis.cpp:674
> +        if (virtualRegisterForLocal(i).offset() > captureStart(m_codeBlock))
> +            result.set(i);
> +        else 
> +            result.set(numCapturedVars + i);

Is this arithmetic right for the stack flipping that we did?

[EFL EWS Bot]

Comment on attachment 216700 [details]
Patch

Attachment 216700 [details] did not pass efl-wk2-ews (efl-wk2):
Output: http://webkit-queues.appspot.com/results/22749590

[Filip Pizlo]

(In reply to comment #26)
> (From update of attachment 216700 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=216700&action=review
> 
> > Source/JavaScriptCore/bytecode/BytecodeLivenessAnalysis.cpp:674
> > +        if (virtualRegisterForLocal(i).offset() > captureStart(m_codeBlock))
> > +            result.set(i);
> > +        else 
> > +            result.set(numCapturedVars + i);
> 
> Is this arithmetic right for the stack flipping that we did?

(I'm not saying it's wrong - I just to make sure you checked it.)

[Mark Hahnenberg]

Comment on attachment 216700 [details]
Patch

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

>>> Source/JavaScriptCore/bytecode/BytecodeLivenessAnalysis.cpp:674
>>> +            result.set(numCapturedVars + i);
>> 
>> Is this arithmetic right for the stack flipping that we did?
> 
> (I'm not saying it's wrong - I just to make sure you checked it.)

I think it's right. I went back and changed the old logic from before the stack was flipped. captureStart() and captureEnd() return offsets which will all be negative now for locals, so if the offset is greater than the captureStart() offset then we're not captured, and if it's less than or equal to the captureEnd() offset then we're also outside the captured range. I ran tests with the analysis enabled and it didn't crash and the dumped output of the analysis seemed reasonable.

[Filip Pizlo]

(In reply to comment #29)
> (From update of attachment 216700 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=216700&action=review
> 
> >>> Source/JavaScriptCore/bytecode/BytecodeLivenessAnalysis.cpp:674
> >>> +            result.set(numCapturedVars + i);
> >> 
> >> Is this arithmetic right for the stack flipping that we did?
> > 
> > (I'm not saying it's wrong - I just to make sure you checked it.)
> 
> I think it's right. I went back and changed the old logic from before the stack was flipped. captureStart() and captureEnd() return offsets which will all be negative now for locals, so if the offset is greater than the captureStart() offset then we're not captured, and if it's less than or equal to the captureEnd() offset then we're also outside the captured range. I ran tests with the analysis enabled and it didn't crash and the dumped output of the analysis seemed reasonable.

Sweet!

[Filip Pizlo]

I think your build errors can be fixed by adding this to FastBitVector:

#include <string.h>

[Mark Hahnenberg]

(In reply to comment #31)
> I think your build errors can be fixed by adding this to FastBitVector:
> 
> #include <string.h>

Yep. About to land...

[Mark Hahnenberg]

Committed r159136: <http://trac.webkit.org/changeset/159136>