Bug 170102 – Air::Liveness shouldn't need HashSets

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

[Filip Pizlo]

Patch forthcoming.

[Filip Pizlo]

Created attachment 305400 [details]
it begins

[Filip Pizlo]

It works, but it looks like a slow-down!

[Filip Pizlo]

Created attachment 305410 [details]
the patch

[Build Bot]

Attachment 305410 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/b3/B3TimingScope.cpp:60:  More than one command on the same line  [whitespace/newline] [4]
ERROR: Source/WTF/wtf/Vector.h:1516:  More than one command on the same line  [whitespace/newline] [4]
Total errors found: 2 in 15 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Filip Pizlo]

Created attachment 305411 [details]
the patch

[Build Bot]

Attachment 305411 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/b3/B3TimingScope.cpp:60:  More than one command on the same line  [whitespace/newline] [4]
ERROR: Source/WTF/wtf/Vector.h:1516:  More than one command on the same line  [whitespace/newline] [4]
Total errors found: 2 in 13 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Filip Pizlo]

Created attachment 305435 [details]
the patch

[Build Bot]

Attachment 305435 [details] did not pass style-queue:


ERROR: Source/JavaScriptCore/b3/B3TimingScope.cpp:60:  More than one command on the same line  [whitespace/newline] [4]
ERROR: Source/WTF/wtf/Vector.h:1516:  More than one command on the same line  [whitespace/newline] [4]
Total errors found: 2 in 15 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Yusuke Suzuki]

Comment on attachment 305435 [details]
the patch

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

r=me

> Source/JavaScriptCore/ChangeLog:11
> +        compile time progression on WasmBench.

Cool.

> Source/JavaScriptCore/b3/air/AirLiveness.h:133
>              dirtyBlocks.set(blockIndex);

Cool.

> Source/JavaScriptCore/b3/air/AirLiveness.h:188
> +                        liveAtTail = m_workset.values();

OK, m_workset.values() is already sorted.

> Source/JavaScriptCore/b3/air/AirLiveness.h:202
> +                        mergeBuffer.resize(0);
> +                        mergeBuffer.reserveCapacity(liveAtTail.size() + m_workset.size());
> +                        auto iter = mergeDeduplicatedSorted(
> +                            liveAtTail.begin(), liveAtTail.end(),
> +                            m_workset.begin(), m_workset.end(),
> +                            mergeBuffer.begin());
> +                        mergeBuffer.resize(iter - mergeBuffer.begin());
> +                        
> +                        if (mergeBuffer.size() == liveAtTail.size())
> +                            continue;
> +                    
> +                        RELEASE_ASSERT(mergeBuffer.size() > liveAtTail.size());
> +                        liveAtTail = mergeBuffer;

OK, merging 2 sorted sequence into one sorted mergeBuffer.

> Source/JavaScriptCore/b3/air/AirTmp.h:95
> +

Is this used?

> Source/JavaScriptCore/b3/air/AirTmp.h:149
> +    }

Ditto.

[Filip Pizlo]

(In reply to Yusuke Suzuki from comment #9)
> Comment on attachment 305435 [details]
> the patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=305435&action=review
> 
> r=me
> 
> > Source/JavaScriptCore/ChangeLog:11
> > +        compile time progression on WasmBench.
> 
> Cool.
> 
> > Source/JavaScriptCore/b3/air/AirLiveness.h:133
> >              dirtyBlocks.set(blockIndex);
> 
> Cool.
> 
> > Source/JavaScriptCore/b3/air/AirLiveness.h:188
> > +                        liveAtTail = m_workset.values();
> 
> OK, m_workset.values() is already sorted.
> 
> > Source/JavaScriptCore/b3/air/AirLiveness.h:202
> > +                        mergeBuffer.resize(0);
> > +                        mergeBuffer.reserveCapacity(liveAtTail.size() + m_workset.size());
> > +                        auto iter = mergeDeduplicatedSorted(
> > +                            liveAtTail.begin(), liveAtTail.end(),
> > +                            m_workset.begin(), m_workset.end(),
> > +                            mergeBuffer.begin());
> > +                        mergeBuffer.resize(iter - mergeBuffer.begin());
> > +                        
> > +                        if (mergeBuffer.size() == liveAtTail.size())
> > +                            continue;
> > +                    
> > +                        RELEASE_ASSERT(mergeBuffer.size() > liveAtTail.size());
> > +                        liveAtTail = mergeBuffer;
> 
> OK, merging 2 sorted sequence into one sorted mergeBuffer.
> 
> > Source/JavaScriptCore/b3/air/AirTmp.h:95
> > +
> 
> Is this used?

It's meant to be a replacement for when we say Arg(tmp).bank().  I think I may have used it in an earlier version of this patch.

> 
> > Source/JavaScriptCore/b3/air/AirTmp.h:149
> > +    }
> 
> Ditto.

Same thing, earlier version of this patch.

[Filip Pizlo]

Landed in r214409.

[Yusuke Suzuki]

Comment on attachment 305435 [details]
the patch

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

Oops, one nit comment.

> Source/JavaScriptCore/b3/air/AirLiveness.h:191
> +                        mergeBuffer.reserveCapacity(liveAtTail.size() + m_workset.size());

I think this just allocates capacity(), but the size() of mergeBuffer is still zero.
So, I think the following mergeDeduplicatedSorted is not safe especially in regards of ASAN.
I think we need to perform `resize(liveAtTail.size() + m_workset.size()` here.

[Filip Pizlo]

(In reply to Yusuke Suzuki from comment #12)
> Comment on attachment 305435 [details]
> the patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=305435&action=review
> 
> Oops, one nit comment.
> 
> > Source/JavaScriptCore/b3/air/AirLiveness.h:191
> > +                        mergeBuffer.reserveCapacity(liveAtTail.size() + m_workset.size());
> 
> I think this just allocates capacity(), but the size() of mergeBuffer is
> still zero.
> So, I think the following mergeDeduplicatedSorted is not safe especially in
> regards of ASAN.
> I think we need to perform `resize(liveAtTail.size() + m_workset.size()`
> here.

You're right!  Previously this was OK because I was using uncheckedAppend but then I switched to insertion iterators.

[Filip Pizlo]

(In reply to Filip Pizlo from comment #13)
> (In reply to Yusuke Suzuki from comment #12)
> > Comment on attachment 305435 [details]
> > the patch
> > 
> > View in context:
> > https://bugs.webkit.org/attachment.cgi?id=305435&action=review
> > 
> > Oops, one nit comment.
> > 
> > > Source/JavaScriptCore/b3/air/AirLiveness.h:191
> > > +                        mergeBuffer.reserveCapacity(liveAtTail.size() + m_workset.size());
> > 
> > I think this just allocates capacity(), but the size() of mergeBuffer is
> > still zero.
> > So, I think the following mergeDeduplicatedSorted is not safe especially in
> > regards of ASAN.
> > I think we need to perform `resize(liveAtTail.size() + m_workset.size()`
> > here.
> 
> You're right!  Previously this was OK because I was using uncheckedAppend
> but then I switched to insertion iterators.

Fixed in https://bugs.webkit.org/show_bug.cgi?id=170111