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

• Status: RESOLVED
• Resolution: FIXED
• Component: JavaScriptCore

[Filip Pizlo]

...

[Filip Pizlo]

Created attachment 234479 [details]
it begins

[Filip Pizlo]

Created attachment 234523 [details]
more

[Filip Pizlo]

Created attachment 234539 [details]
more

[Filip Pizlo]

Created attachment 234595 [details]
work in progress

[Filip Pizlo]

Created attachment 234619 [details]
more

[Filip Pizlo]

Created attachment 234621 [details]
it is written!

GCSE implemented with clobberizing functors.  How much more nerdy can you get?

[Filip Pizlo]

Created attachment 234656 [details]
rebased

[Filip Pizlo]

Created attachment 234668 [details]
it gcsed some stuff

[Filip Pizlo]

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.

[Filip Pizlo]

Created attachment 234689 [details]
new DFGCSEPhase.cpp

Posting this because the svn diff is messed up.

[Filip Pizlo]

Created attachment 234710 [details]
it passes tests

Passes tests; now on to performance.

[Filip Pizlo]

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.

[Filip Pizlo]

Created attachment 234773 [details]
the patch

Refined the CSEPhase to have a faster path for small blocks.

[Sam Weinig]

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).

[Filip Pizlo]

(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.

[Sam Weinig]

(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.

[Filip Pizlo]

(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.

[Filip Pizlo]

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.

[Filip Pizlo]

Created attachment 234835 [details]
almost ready to land

[Filip Pizlo]

Created attachment 234907 [details]
closer to done

[Filip Pizlo]

Landed in http://trac.webkit.org/changeset/171106