Bug 154658

Summary: B3 should have global store elimination
Product: WebKit Reporter: Filip Pizlo <fpizlo>
Component: JavaScriptCoreAssignee: Filip Pizlo <fpizlo>
Status: RESOLVED FIXED    
Severity: Normal CC: commit-queue, keith_miller, mark.lam, msaboff, saam
Priority: P2    
Version: WebKit Nightly Build   
Hardware: All   
OS: All   
Bug Depends on: 154782    
Bug Blocks: 154319    
Attachments:
Description Flags
things
none
better approach
none
it compiles
none
maybe the patch
none
the patch benjamin: review+

Description Filip Pizlo 2016-02-24 14:54:35 PST
...
Comment 1 Filip Pizlo 2016-02-24 14:59:08 PST
The main issue here is doing backward dominators: if we have @s = Store(@x, @p) and @t = Store(@y, @p) then we can eliminate @s if it is backward dominated by @t and there does not exist a path from @s to @t that could observe the store.

On the other hand, maybe you could just do this by forward flow. If you do forward flow from @s and we find any number of @t's without ever hitting a side exit, return, read or write, then we can eliminate @s.
Comment 2 Filip Pizlo 2016-02-24 14:59:27 PST
Created attachment 272151 [details]
things
Comment 3 Filip Pizlo 2016-02-25 13:10:26 PST
Created attachment 272227 [details]
better approach
Comment 4 Filip Pizlo 2016-02-25 14:25:58 PST
Created attachment 272240 [details]
it compiles
Comment 5 Filip Pizlo 2016-02-28 13:07:24 PST
Created attachment 272461 [details]
maybe the patch

Still running tests.
Comment 6 WebKit Commit Bot 2016-02-28 13:09:39 PST
Attachment 272461 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/b3/B3EliminateCommonSubexpressions.cpp:296:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
Total errors found: 1 in 4 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 7 Filip Pizlo 2016-02-28 17:51:30 PST
Created attachment 272470 [details]
the patch
Comment 8 WebKit Commit Bot 2016-02-28 17:53:30 PST
Attachment 272470 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/b3/B3EliminateCommonSubexpressions.cpp:296:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
Total errors found: 1 in 11 files


If any of these errors are false positives, please file a bug against check-webkit-style.
Comment 9 Benjamin Poulain 2016-02-29 14:14:26 PST
Comment on attachment 272470 [details]
the patch

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

> Source/JavaScriptCore/b3/B3EliminateCommonSubexpressions.cpp:108
> +            for (Value* candidateValue : *matches) {

MemoryValue* candidateValue?

> Source/JavaScriptCore/b3/B3EliminateCommonSubexpressions.cpp:109
> +                if (MemoryValue* candidateMemory = candidateValue->as<MemoryValue>()) {

When can this be false?
Comment 10 Filip Pizlo 2016-02-29 14:28:36 PST
(In reply to comment #9)
> Comment on attachment 272470 [details]
> the patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=272470&action=review
> 
> > Source/JavaScriptCore/b3/B3EliminateCommonSubexpressions.cpp:108
> > +            for (Value* candidateValue : *matches) {
> 
> MemoryValue* candidateValue?

Something in our list could have been turned into Identity.

We do like this:
1) Summarize things in each block before doing any changes.
2) Do changes (i.e. turn things into Identity's) and look for things in the summaries.

The things that we turn into Identity's are also the things we put into the summaries in (1).  This data structure manages summaries, so it will see Identity's.

Identity does not use MemoryValue (it's just a plain Value), so MemoryValue* here would be wrong.

> 
> > Source/JavaScriptCore/b3/B3EliminateCommonSubexpressions.cpp:109
> > +                if (MemoryValue* candidateMemory = candidateValue->as<MemoryValue>()) {
> 
> When can this be false?

See above! :-)
Comment 11 Filip Pizlo 2016-02-29 14:34:13 PST
Landed in http://trac.webkit.org/changeset/197366