Bug 118546 - CodeBlocks should be able to determine bytecode liveness
Summary: CodeBlocks should be able to determine bytecode liveness
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: JavaScriptCore (show other bugs)
Version: 528+ (Nightly build)
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: Mark Hahnenberg
URL:
Keywords:
Depends on:
Blocks: 124181
  Show dependency treegraph
 
Reported: 2013-07-10 18:27 PDT by Mark Hahnenberg
Modified: 2013-11-12 12:33 PST (History)
11 users (show)

See Also:


Attachments
Patch (62.61 KB, patch)
2013-07-10 18:47 PDT, Mark Hahnenberg
no flags Details | Formatted Diff | Diff
Patch (68.69 KB, patch)
2013-08-05 14:26 PDT, Mark Hahnenberg
no flags Details | Formatted Diff | Diff
Patch (74.03 KB, patch)
2013-08-07 13:17 PDT, Mark Hahnenberg
no flags Details | Formatted Diff | Diff
Patch (74.43 KB, patch)
2013-08-07 13:41 PDT, Mark Hahnenberg
no flags Details | Formatted Diff | Diff
Patch (70.20 KB, patch)
2013-11-12 12:01 PST, Mark Hahnenberg
fpizlo: review+
eflews.bot: commit-queue-
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Mark Hahnenberg 2013-07-10 18:27:02 PDT
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.
Comment 1 Mark Hahnenberg 2013-07-10 18:47:19 PDT
Created attachment 206423 [details]
Patch
Comment 2 Mark Hahnenberg 2013-07-10 18:48:16 PDT
(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.
Comment 3 Mark Hahnenberg 2013-07-10 18:49:01 PDT
> calculated 
calculating
Comment 4 Mark Hahnenberg 2013-07-10 18:54:21 PDT
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.
Comment 5 Mark Hahnenberg 2013-08-05 14:26:39 PDT
Created attachment 208147 [details]
Patch
Comment 6 WebKit Commit Bot 2013-08-05 14:27:54 PDT
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.
Comment 7 Early Warning System Bot 2013-08-05 14:38:27 PDT
Comment on attachment 208147 [details]
Patch

Attachment 208147 [details] did not pass qt-ews (qt):
Output: http://webkit-queues.appspot.com/results/1363081
Comment 8 Early Warning System Bot 2013-08-05 14:38:59 PDT
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
Comment 9 Filip Pizlo 2013-08-05 14:40:51 PDT
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
Comment 10 Filip Pizlo 2013-08-05 14:40:57 PDT
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
Comment 11 EFL EWS Bot 2013-08-05 15:01:02 PDT
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
Comment 12 EFL EWS Bot 2013-08-05 15:12:32 PDT
Comment on attachment 208147 [details]
Patch

Attachment 208147 [details] did not pass efl-ews (efl):
Output: http://webkit-queues.appspot.com/results/1362055
Comment 13 kov's GTK+ EWS bot 2013-08-05 15:53:30 PDT
Comment on attachment 208147 [details]
Patch

Attachment 208147 [details] did not pass gtk-ews (gtk):
Output: http://webkit-queues.appspot.com/results/1397010
Comment 14 kov's GTK+ EWS bot 2013-08-05 16:03:30 PDT
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
Comment 15 Mark Hahnenberg 2013-08-07 13:17:45 PDT
Created attachment 208295 [details]
Patch
Comment 16 WebKit Commit Bot 2013-08-07 13:20:22 PDT
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.
Comment 17 Early Warning System Bot 2013-08-07 13:25:26 PDT
Comment on attachment 208295 [details]
Patch

Attachment 208295 [details] did not pass qt-ews (qt):
Output: http://webkit-queues.appspot.com/results/1382307
Comment 18 Early Warning System Bot 2013-08-07 13:25:50 PDT
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
Comment 19 EFL EWS Bot 2013-08-07 13:29:21 PDT
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
Comment 20 Mark Hahnenberg 2013-08-07 13:41:20 PDT
Created attachment 208296 [details]
Patch
Comment 21 WebKit Commit Bot 2013-08-07 13:43:56 PDT
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.
Comment 22 EFL EWS Bot 2013-08-07 14:03:26 PDT
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
Comment 23 Oliver Hunt 2013-10-31 13:34:34 PDT
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 :)
Comment 24 Mark Hahnenberg 2013-11-12 12:01:18 PST
Created attachment 216700 [details]
Patch
Comment 25 EFL EWS Bot 2013-11-12 12:06:44 PST
Comment on attachment 216700 [details]
Patch

Attachment 216700 [details] did not pass efl-ews (efl):
Output: http://webkit-queues.appspot.com/results/22779678
Comment 26 Filip Pizlo 2013-11-12 12:08:41 PST
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?
Comment 27 EFL EWS Bot 2013-11-12 12:08:54 PST
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
Comment 28 Filip Pizlo 2013-11-12 12:09:11 PST
(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.)
Comment 29 Mark Hahnenberg 2013-11-12 12:13:49 PST
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.
Comment 30 Filip Pizlo 2013-11-12 12:14:20 PST
(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!
Comment 31 Filip Pizlo 2013-11-12 12:31:26 PST
I think your build errors can be fixed by adding this to FastBitVector:

#include <string.h>
Comment 32 Mark Hahnenberg 2013-11-12 12:31:49 PST
(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...
Comment 33 Mark Hahnenberg 2013-11-12 12:33:31 PST
Committed r159136: <http://trac.webkit.org/changeset/159136>