...

Created attachment 234479 [details] it begins

Created attachment 234523 [details] more

Created attachment 234539 [details] more

Created attachment 234595 [details] work in progress

Created attachment 234619 [details] more

Created attachment 234621 [details] it is written! GCSE implemented with clobberizing functors. How much more nerdy can you get?

Created attachment 234656 [details] rebased

Created attachment 234668 [details] it gcsed some stuff

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.

Created attachment 234689 [details] new DFGCSEPhase.cpp Posting this because the svn diff is messed up.

Created attachment 234710 [details] it passes tests Passes tests; now on to performance.

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.

Created attachment 234773 [details] the patch Refined the CSEPhase to have a faster path for small blocks.

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

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

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

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

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.

Created attachment 234835 [details] almost ready to land

Created attachment 234907 [details] closer to done

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