Bug 174750 - B3 should do LICM
Summary: B3 should do LICM
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: 174762 174763
  Show dependency treegraph
 
Reported: 2017-07-21 22:46 PDT by Filip Pizlo
Modified: 2017-07-25 18:59 PDT (History)
7 users (show)

See Also:


Attachments
it's a start (29.00 KB, patch)
2017-07-21 22:47 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
more (66.03 KB, patch)
2017-07-22 08:26 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
more (70.48 KB, patch)
2017-07-22 09:00 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
wrote the pre-header creation (76.93 KB, patch)
2017-07-22 09:56 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
more (80.28 KB, patch)
2017-07-22 21:11 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
better version (78.79 KB, patch)
2017-07-23 11:26 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
added comprehensive tests and made them pass (93.27 KB, patch)
2017-07-23 13:00 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
added changelog (100.49 KB, patch)
2017-07-23 13:10 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
rebased (98.51 KB, patch)
2017-07-23 13:18 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
the patch (99.13 KB, patch)
2017-07-23 15:38 PDT, Filip Pizlo
keith_miller: 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 2017-07-21 22:46:25 PDT
Patch forthcoming.
Comment 1 Filip Pizlo 2017-07-21 22:47:33 PDT
Created attachment 316175 [details]
it's a start
Comment 2 Filip Pizlo 2017-07-22 08:26:09 PDT
Created attachment 316194 [details]
more
Comment 3 Filip Pizlo 2017-07-22 09:00:24 PDT
Created attachment 316195 [details]
more

The LICM itself is written, now I need to write the pre-header creator.
Comment 4 Filip Pizlo 2017-07-22 09:56:21 PDT
Created attachment 316196 [details]
wrote the pre-header creation
Comment 5 Filip Pizlo 2017-07-22 10:03:02 PDT
Actually, as awesome as this is, I don't think this is the way we want to handle optimizing caging.  If a butterfly is used both caged and uncaged, we want to do the caging once and drop the uncaged value just to relieve register pressure.
Comment 6 Filip Pizlo 2017-07-22 21:11:44 PDT
Created attachment 316223 [details]
more
Comment 7 Filip Pizlo 2017-07-23 11:26:19 PDT
Created attachment 316229 [details]
better version

I realized that InnerMostLoopIndices should be managed by a typename Graph::template Map.
Comment 8 Filip Pizlo 2017-07-23 13:00:41 PDT
Created attachment 316230 [details]
added comprehensive tests and made them pass
Comment 9 Filip Pizlo 2017-07-23 13:10:19 PDT
Created attachment 316231 [details]
added changelog
Comment 10 Filip Pizlo 2017-07-23 13:18:31 PDT
Created attachment 316232 [details]
rebased
Comment 11 Filip Pizlo 2017-07-23 15:38:47 PDT
Created attachment 316241 [details]
the patch
Comment 12 Keith Miller 2017-07-25 00:34:37 PDT
Comment on attachment 316241 [details]
the patch

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

r=me with some nits.

> Source/JavaScriptCore/ChangeLog:8
> +        Added a LICM phase to B3. This phase is called hoistLoopInvariantValues, to conform to the B3 naming

I dunno HLIV doesn't roll off the tongue the same way LICM does...

> Source/JavaScriptCore/b3/B3BasicBlock.cpp:60
> -    m_values[m_values.size() - 1] = value;
> +    m_values[m_values.size() - 2] = value;

legit...

> Source/JavaScriptCore/b3/B3CFG.h:62
> +    

revert please.

> Source/JavaScriptCore/b3/B3EnsureLoopPreHeaders.cpp:71
> +        loop.header()->addPredecessor(preHeader);

Nit: It would probably be a little clearer if you moved this line to where you set the successor of the preHeader.
Comment 13 Saam Barati 2017-07-25 11:13:45 PDT
Comment on attachment 316241 [details]
the patch

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

> Source/WTF/wtf/NaturalLoops.h:279
> +            return 0;

Nit: nullptr

> Source/WTF/wtf/NaturalLoops.h:293
> +            return 0;

ditto

> Source/WTF/wtf/NaturalLoops.h:300
> +            return 0;

ditto
Comment 14 Saam Barati 2017-07-25 12:15:51 PDT
Comment on attachment 316241 [details]
the patch

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

LGTM too

> Source/JavaScriptCore/ChangeLog:20
> +        This isn't super important. It's perf-neutral on JS benchmarks. FTL already does LICM on DFG SSA IR, and
> +        probably all current WebAssembly content has had LICM done to it. That being said, this is a cheap phase
> +        so it doesn't hurt to have it.

It'd be interesting to compile some Wasm using -O0 and see if this is a speedup. I'd bet it is.
Comment 15 Keith Miller 2017-07-25 12:17:54 PDT
(In reply to Saam Barati from comment #14)
> Comment on attachment 316241 [details]
> the patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=316241&action=review
> 
> LGTM too
> 
> > Source/JavaScriptCore/ChangeLog:20
> > +        This isn't super important. It's perf-neutral on JS benchmarks. FTL already does LICM on DFG SSA IR, and
> > +        probably all current WebAssembly content has had LICM done to it. That being said, this is a cheap phase
> > +        so it doesn't hurt to have it.
> 
> It'd be interesting to compile some Wasm using -O0 and see if this is a
> speedup. I'd bet it is.

I'm not sure it would be since we don't have abstract heaps yet in wasm. That was on my todo but I never got around to it. But we should totally do this...
Comment 16 Filip Pizlo 2017-07-25 12:37:15 PDT
(In reply to Keith Miller from comment #15)
> (In reply to Saam Barati from comment #14)
> > Comment on attachment 316241 [details]
> > the patch
> > 
> > View in context:
> > https://bugs.webkit.org/attachment.cgi?id=316241&action=review
> > 
> > LGTM too
> > 
> > > Source/JavaScriptCore/ChangeLog:20
> > > +        This isn't super important. It's perf-neutral on JS benchmarks. FTL already does LICM on DFG SSA IR, and
> > > +        probably all current WebAssembly content has had LICM done to it. That being said, this is a cheap phase
> > > +        so it doesn't hurt to have it.
> > 
> > It'd be interesting to compile some Wasm using -O0 and see if this is a
> > speedup. I'd bet it is.
> 
> I'm not sure it would be since we don't have abstract heaps yet in wasm.
> That was on my todo but I never got around to it. But we should totally do
> this...

It'll be a speed-up if we hoist division or multiplication.  Also, for float code, if you can hoist basically anything then you get faster.
Comment 17 Filip Pizlo 2017-07-25 12:39:53 PDT
Comment on attachment 316241 [details]
the patch

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

>> Source/JavaScriptCore/b3/B3EnsureLoopPreHeaders.cpp:71
>> +        loop.header()->addPredecessor(preHeader);
> 
> Nit: It would probably be a little clearer if you moved this line to where you set the successor of the preHeader.

Good point.  Will do.
Comment 18 Filip Pizlo 2017-07-25 18:24:24 PDT
(In reply to Saam Barati from comment #13)
> Comment on attachment 316241 [details]
> the patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=316241&action=review
> 
> > Source/WTF/wtf/NaturalLoops.h:279
> > +            return 0;
> 
> Nit: nullptr
> 
> > Source/WTF/wtf/NaturalLoops.h:293
> > +            return 0;
> 
> ditto
> 
> > Source/WTF/wtf/NaturalLoops.h:300
> > +            return 0;
> 
> ditto

Fixed.
Comment 19 Filip Pizlo 2017-07-25 18:25:27 PDT
(In reply to Keith Miller from comment #12)
> Comment on attachment 316241 [details]
> the patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=316241&action=review
> 
> r=me with some nits.
> 
> > Source/JavaScriptCore/ChangeLog:8
> > +        Added a LICM phase to B3. This phase is called hoistLoopInvariantValues, to conform to the B3 naming
> 
> I dunno HLIV doesn't roll off the tongue the same way LICM does...
> 
> > Source/JavaScriptCore/b3/B3BasicBlock.cpp:60
> > -    m_values[m_values.size() - 1] = value;
> > +    m_values[m_values.size() - 2] = value;
> 
> legit...
> 
> > Source/JavaScriptCore/b3/B3CFG.h:62
> > +    
> 
> revert please.

Fixed.

> 
> > Source/JavaScriptCore/b3/B3EnsureLoopPreHeaders.cpp:71
> > +        loop.header()->addPredecessor(preHeader);
> 
> Nit: It would probably be a little clearer if you moved this line to where
> you set the successor of the preHeader.

Fixed.
Comment 20 Filip Pizlo 2017-07-25 18:26:48 PDT
(In reply to Filip Pizlo from comment #19)
> (In reply to Keith Miller from comment #12)
> > Comment on attachment 316241 [details]
> > the patch
> > 
> > View in context:
> > https://bugs.webkit.org/attachment.cgi?id=316241&action=review
> > 
> > r=me with some nits.
> > 
> > > Source/JavaScriptCore/ChangeLog:8
> > > +        Added a LICM phase to B3. This phase is called hoistLoopInvariantValues, to conform to the B3 naming
> > 
> > I dunno HLIV doesn't roll off the tongue the same way LICM does...
> > 
> > > Source/JavaScriptCore/b3/B3BasicBlock.cpp:60
> > > -    m_values[m_values.size() - 1] = value;
> > > +    m_values[m_values.size() - 2] = value;
> > 
> > legit...
> > 
> > > Source/JavaScriptCore/b3/B3CFG.h:62
> > > +    
> > 
> > revert please.
> 
> Fixed.
> 
> > 
> > > Source/JavaScriptCore/b3/B3EnsureLoopPreHeaders.cpp:71
> > > +        loop.header()->addPredecessor(preHeader);
> > 
> > Nit: It would probably be a little clearer if you moved this line to where
> > you set the successor of the preHeader.
> 
> Fixed.

Actually no!  My original ordering means that we first remove predecessors and then add.  Your reordering, while clearer, would mean adding and then removing.  It's a bit more efficient to remove then add, so I'll keep the current ordering.
Comment 21 Filip Pizlo 2017-07-25 18:59:00 PDT
Landed in https://trac.webkit.org/changeset/219898/webkit