Bug 150961 - B3 should have CSE
Summary: B3 should have CSE
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: JavaScriptCore (show other bugs)
Version: WebKit Nightly Build
Hardware: All All
: P2 Normal
Assignee: Filip Pizlo
URL:
Keywords:
Depends on:
Blocks: 150507
  Show dependency treegraph
 
Reported: 2015-11-05 15:12 PST by Filip Pizlo
Modified: 2015-12-11 15:21 PST (History)
5 users (show)

See Also:


Attachments
the patch (6.45 KB, patch)
2015-12-11 13:23 PST, Filip Pizlo
benjamin: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
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