Bug 150961

Summary: B3 should have CSE
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:    
Bug Blocks: 150507    
Attachments:
Description Flags
the patch benjamin: review+

Description Filip Pizlo 2015-11-05 15:12:58 PST 
Fun!
Comment 1 Filip Pizlo 2015-12-11 13:23:04 PST 
Created attachment 267183 [details]
the patch
Comment 2 WebKit Commit Bot 2015-12-11 13:25:20 PST 
Attachment 267183 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/b3/B3ReduceStrength.cpp:41:  Alphabetical sorting problem.  [build/include_order] [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 3 Benjamin Poulain 2015-12-11 15:00:27 PST 
Comment on attachment 267183 [details]
the patch

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

> Source/JavaScriptCore/b3/B3ReduceStrength.cpp:112
> +            m_dominators = &m_proc.dominators(); // Recompute if necessary.

This is a tiny bit scary :)

> Source/JavaScriptCore/b3/B3Value.cpp:448
> +    case BitwiseCast:

Oops
Comment 4 Filip Pizlo 2015-12-11 15:02:53 PST 
(In reply to comment #3)
> Comment on attachment 267183 [details]
> the patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=267183&action=review
> 
> > Source/JavaScriptCore/b3/B3ReduceStrength.cpp:112
> > +            m_dominators = &m_proc.dominators(); // Recompute if necessary.
> 
> This is a tiny bit scary :)
> 
> > Source/JavaScriptCore/b3/B3Value.cpp:448
> > +    case BitwiseCast:
> 
> Oops

Why oops?  BitwiseCast is a pure value, and so should have a value key.
Comment 5 Filip Pizlo 2015-12-11 15:16:58 PST 
(In reply to comment #4)
> (In reply to comment #3)
> > Comment on attachment 267183 [details]
> > the patch
> > 
> > View in context:
> > https://bugs.webkit.org/attachment.cgi?id=267183&action=review
> > 
> > > Source/JavaScriptCore/b3/B3ReduceStrength.cpp:112
> > > +            m_dominators = &m_proc.dominators(); // Recompute if necessary.
> > 
> > This is a tiny bit scary :)
> > 
> > > Source/JavaScriptCore/b3/B3Value.cpp:448
> > > +    case BitwiseCast:
> > 
> > Oops
> 
> Why oops?  BitwiseCast is a pure value, and so should have a value key.

Never mind. :-)
Comment 6 Filip Pizlo 2015-12-11 15:19:00 PST 
(In reply to comment #3)
> Comment on attachment 267183 [details]
> the patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=267183&action=review
> 
> > Source/JavaScriptCore/b3/B3ReduceStrength.cpp:112
> > +            m_dominators = &m_proc.dominators(); // Recompute if necessary.
> 
> This is a tiny bit scary :)

What is scary about it?  The cost?

It's true that CSE adds cost to reduceStrength.  About half of that cost is dominators.  Interestingly, this code doesn't need a dominator tree; it only wants dominance queries.  For most CFGs, computing dominance using the data flow fixpoint is cheaper than the Lengauer-Tarjan algorithm that we use, so long as you just want dominance queries and not the tree.  So, we could reduce that cost if we felt that we needed to.

But half of the cost of the CSE is just the HashMap, of course. ;-)

> 
> > Source/JavaScriptCore/b3/B3Value.cpp:448
> > +    case BitwiseCast:
> 
> Oops
Comment 7 Filip Pizlo 2015-12-11 15:21:07 PST 
Landed in http://trac.webkit.org/changeset/193987