Bug 174750 – B3 should do LICM

• Component: JavaScriptCore
• Status: RESOLVED FIXED

[Filip Pizlo]

Patch forthcoming.

[Filip Pizlo]

Created attachment 316175 [details]
it's a start

[Filip Pizlo]

Created attachment 316194 [details]
more

[Filip Pizlo]

Created attachment 316195 [details]
more

The LICM itself is written, now I need to write the pre-header creator.

[Filip Pizlo]

Created attachment 316196 [details]
wrote the pre-header creation

[Filip Pizlo]

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.

[Filip Pizlo]

Created attachment 316223 [details]
more

[Filip Pizlo]

Created attachment 316229 [details]
better version

I realized that InnerMostLoopIndices should be managed by a typename Graph::template Map.

[Filip Pizlo]

Created attachment 316230 [details]
added comprehensive tests and made them pass

[Filip Pizlo]

Created attachment 316231 [details]
added changelog

[Filip Pizlo]

Created attachment 316232 [details]
rebased

[Filip Pizlo]

Created attachment 316241 [details]
the patch

[Keith Miller]

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.

[Saam Barati]

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

[Saam Barati]

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.

[Keith Miller]

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

[Filip Pizlo]

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

[Filip Pizlo]

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.

[Filip Pizlo]

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

[Filip Pizlo]

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

[Filip Pizlo]

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

[Filip Pizlo]

Landed in https://trac.webkit.org/changeset/219898/webkit