Bug 134677 - [ftlopt] DFG should be able to do GCSE in SSA and this should be unified with the CSE in CPS, and both of these things should use abstract heaps for reasoning about effects
Summary: [ftlopt] DFG should be able to do GCSE in SSA and this should be unified with...
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: JavaScriptCore (show other bugs)
Version: 528+ (Nightly build)
Hardware: All All
: P2 Normal
Assignee: Filip Pizlo
URL:
Keywords:
Depends on: 134730 134739 134742 134870
Blocks: 134737 134797 134876 134893
  Show dependency treegraph
 
Reported: 2014-07-06 22:44 PDT by Filip Pizlo
Modified: 2014-07-15 08:49 PDT (History)
7 users (show)

See Also:


Attachments
it begins (18.33 KB, patch)
2014-07-06 22:46 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
more (37.84 KB, patch)
2014-07-07 15:43 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
more (52.12 KB, patch)
2014-07-07 20:13 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
work in progress (59.37 KB, patch)
2014-07-08 14:14 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
more (63.40 KB, patch)
2014-07-08 21:34 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
it is written! (111.00 KB, patch)
2014-07-08 23:04 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
rebased (105.80 KB, patch)
2014-07-09 14:22 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
it gcsed some stuff (109.23 KB, patch)
2014-07-09 16:37 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
it seems to work (114.15 KB, patch)
2014-07-09 22:10 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
new DFGCSEPhase.cpp (11.24 KB, text/plain)
2014-07-09 22:12 PDT, Filip Pizlo
no flags Details
it passes tests (114.69 KB, patch)
2014-07-10 11:08 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
the patch (128.77 KB, patch)
2014-07-10 18:52 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
the patch (134.04 KB, patch)
2014-07-11 11:47 PDT, Filip Pizlo
sam: review+
Details | Formatted Diff | Diff
almost ready to land (135.32 KB, patch)
2014-07-13 17:00 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
closer to done (143.31 KB, patch)
2014-07-14 23:48 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Filip Pizlo 2014-07-06 22:44:08 PDT
...
Comment 1 Filip Pizlo 2014-07-06 22:46:01 PDT
Created attachment 234479 [details]
it begins
Comment 2 Filip Pizlo 2014-07-07 15:43:02 PDT
Created attachment 234523 [details]
more
Comment 3 Filip Pizlo 2014-07-07 20:13:24 PDT
Created attachment 234539 [details]
more
Comment 4 Filip Pizlo 2014-07-08 14:14:52 PDT
Created attachment 234595 [details]
work in progress
Comment 5 Filip Pizlo 2014-07-08 21:34:07 PDT
Created attachment 234619 [details]
more
Comment 6 Filip Pizlo 2014-07-08 23:04:11 PDT
Created attachment 234621 [details]
it is written!

GCSE implemented with clobberizing functors.  How much more nerdy can you get?
Comment 7 Filip Pizlo 2014-07-09 14:22:53 PDT
Created attachment 234656 [details]
rebased
Comment 8 Filip Pizlo 2014-07-09 16:37:11 PDT
Created attachment 234668 [details]
it gcsed some stuff
Comment 9 Filip Pizlo 2014-07-09 22:10:05 PDT
Created attachment 234688 [details]
it seems to work

Still doing a bunch of testing.  I may yet have to implement a faster HashMap-less LCSE mode for small basic blocks.
Comment 10 Filip Pizlo 2014-07-09 22:12:09 PDT
Created attachment 234689 [details]
new DFGCSEPhase.cpp

Posting this because the svn diff is messed up.
Comment 11 Filip Pizlo 2014-07-10 11:08:13 PDT
Created attachment 234710 [details]
it passes tests

Passes tests; now on to performance.
Comment 12 Filip Pizlo 2014-07-10 18:52:48 PDT
Created attachment 234737 [details]
the patch

Note that when reviewing this, you can use the DFGCSEPhase.cpp file that I uploaded instead of trying to decypher that part of the diff.
Comment 13 Filip Pizlo 2014-07-11 11:47:35 PDT
Created attachment 234773 [details]
the patch

Refined the CSEPhase to have a faster path for small blocks.
Comment 14 Sam Weinig 2014-07-11 20:56:57 PDT
Comment on attachment 234773 [details]
the patch

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

> Source/JavaScriptCore/dfg/DFGCSEPhase.cpp:71
> +    ClobberFilter filter(heap);
> +    map.removeIf(filter);

Instead of using a functor, you could use a lambda:

map.removeIf([heap](const ImpureMap::KeyValuePairType& pair) {  return heap.overlaps(pair.key.heap()); }); or some such jazz.

> Source/JavaScriptCore/dfg/DFGGraph.h:667
> +    void getBlocksInPreOrder(Vector<BasicBlock*>& result);
> +    void getBlocksInPostOrder(Vector<BasicBlock*>& result);

There isn't any reason I can see that these couldn't return a Vector, rather than taking one by reference.  RVO should kick in for them.

> Source/WTF/wtf/HashTable.h:1037
> +    template<typename Functor>
> +    inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeIf(Functor& functor)

I really like this, and was just telling Tim Horton we needed this the other day.  If you wanted to be awesome, you would land this separate (and in trunk).
Comment 15 Filip Pizlo 2014-07-12 11:17:40 PDT
(In reply to comment #14)
> (From update of attachment 234773 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=234773&action=review
> 
> > Source/JavaScriptCore/dfg/DFGCSEPhase.cpp:71
> > +    ClobberFilter filter(heap);
> > +    map.removeIf(filter);
> 
> Instead of using a functor, you could use a lambda:
> 
> map.removeIf([heap](const ImpureMap::KeyValuePairType& pair) {  return heap.overlaps(pair.key.heap()); }); or some such jazz.

Is this always guaranteed to have the same performance as a functor?

> 
> > Source/JavaScriptCore/dfg/DFGGraph.h:667
> > +    void getBlocksInPreOrder(Vector<BasicBlock*>& result);
> > +    void getBlocksInPostOrder(Vector<BasicBlock*>& result);
> 
> There isn't any reason I can see that these couldn't return a Vector, rather than taking one by reference.  RVO should kick in for them.

Eventually, we can change this.  Note that what I'm doing is renaming DepthFirstOrder to PreOrder; that method already returned its result via the result argument.

> 
> > Source/WTF/wtf/HashTable.h:1037
> > +    template<typename Functor>
> > +    inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeIf(Functor& functor)
> 
> I really like this, and was just telling Tim Horton we needed this the other day.  If you wanted to be awesome, you would land this separate (and in trunk).

I'll land it separately and on trunk.
Comment 16 Sam Weinig 2014-07-12 12:47:18 PDT
(In reply to comment #15)
> (In reply to comment #14)
> > (From update of attachment 234773 [details] [details])
> > View in context: https://bugs.webkit.org/attachment.cgi?id=234773&action=review
> > 
> > > Source/JavaScriptCore/dfg/DFGCSEPhase.cpp:71
> > > +    ClobberFilter filter(heap);
> > > +    map.removeIf(filter);
> > 
> > Instead of using a functor, you could use a lambda:
> > 
> > map.removeIf([heap](const ImpureMap::KeyValuePairType& pair) {  return heap.overlaps(pair.key.heap()); }); or some such jazz.
> 
> Is this always guaranteed to have the same performance as a functor?

It is supposed to, though I have not verified this. (My recollection is that clang essentially implements lambdas as a sort of sugary-functor).

> 
> > 
> > > Source/JavaScriptCore/dfg/DFGGraph.h:667
> > > +    void getBlocksInPreOrder(Vector<BasicBlock*>& result);
> > > +    void getBlocksInPostOrder(Vector<BasicBlock*>& result);
> > 
> > There isn't any reason I can see that these couldn't return a Vector, rather than taking one by reference.  RVO should kick in for them.
> 
> Eventually, we can change this.  Note that what I'm doing is renaming DepthFirstOrder to PreOrder; that method already returned its result via the result argument.

Ok.

> 
> > 
> > > Source/WTF/wtf/HashTable.h:1037
> > > +    template<typename Functor>
> > > +    inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeIf(Functor& functor)
> > 
> > I really like this, and was just telling Tim Horton we needed this the other day.  If you wanted to be awesome, you would land this separate (and in trunk).
> 
> I'll land it separately and on trunk.

Thanks.
Comment 17 Filip Pizlo 2014-07-12 22:18:37 PDT
(In reply to comment #16)
> (In reply to comment #15)
> > (In reply to comment #14)
> > > (From update of attachment 234773 [details] [details] [details])
> > > View in context: https://bugs.webkit.org/attachment.cgi?id=234773&action=review
> > > 
> > > > Source/JavaScriptCore/dfg/DFGCSEPhase.cpp:71
> > > > +    ClobberFilter filter(heap);
> > > > +    map.removeIf(filter);
> > > 
> > > Instead of using a functor, you could use a lambda:
> > > 
> > > map.removeIf([heap](const ImpureMap::KeyValuePairType& pair) {  return heap.overlaps(pair.key.heap()); }); or some such jazz.
> > 
> > Is this always guaranteed to have the same performance as a functor?
> 
> It is supposed to, though I have not verified this. (My recollection is that clang essentially implements lambdas as a sort of sugary-functor).

That makes sense.  However, my numbers indicate that there *is* a performance difference.  I'll keep the functor.

> 
> > 
> > > 
> > > > Source/JavaScriptCore/dfg/DFGGraph.h:667
> > > > +    void getBlocksInPreOrder(Vector<BasicBlock*>& result);
> > > > +    void getBlocksInPostOrder(Vector<BasicBlock*>& result);
> > > 
> > > There isn't any reason I can see that these couldn't return a Vector, rather than taking one by reference.  RVO should kick in for them.
> > 
> > Eventually, we can change this.  Note that what I'm doing is renaming DepthFirstOrder to PreOrder; that method already returned its result via the result argument.
> 
> Ok.
> 
> > 
> > > 
> > > > Source/WTF/wtf/HashTable.h:1037
> > > > +    template<typename Functor>
> > > > +    inline void HashTable<Key, Value, Extractor, HashFunctions, Traits, KeyTraits>::removeIf(Functor& functor)
> > > 
> > > I really like this, and was just telling Tim Horton we needed this the other day.  If you wanted to be awesome, you would land this separate (and in trunk).
> > 
> > I'll land it separately and on trunk.
> 
> Thanks.
Comment 18 Filip Pizlo 2014-07-12 22:30:15 PDT
Right now I'm fine-tuning how the CSE operates.  I've got one version that always uses HashMaps and another that has LCSE use HashMaps for smallish blocks (what Sam reviewed).  It's not clear that the latter is a win; in fact it's sometimes a loss.

I'm using large numbers of iterations on a very quiet machine to do these measurements. This is where my conclusion that the version that used a lambda instead of a traditional functor was slower came from.

I'm going to do one more run to try to figure out which is better - dual-specialized LCSE versus always-HashMap LCSE - and then I'll land the winner.
Comment 19 Filip Pizlo 2014-07-13 17:00:58 PDT
Created attachment 234835 [details]
almost ready to land
Comment 20 Filip Pizlo 2014-07-14 23:48:03 PDT
Created attachment 234907 [details]
closer to done
Comment 21 Filip Pizlo 2014-07-15 08:49:42 PDT
Landed in http://trac.webkit.org/changeset/171106