Bug 143073 – Object cycles should not prevent allocation elimination/sinking

• Component: JavaScriptCore
• Status: RESOLVED FIXED

[Filip Pizlo]

...

[Basile Clement]

Created attachment 252332 [details]
Patch

First draft, does not handle OSR exit and needs testing (obviously WIP)

[Basile Clement]

Created attachment 252425 [details]
Patch

[Basile Clement]

(In reply to comment #2)
> Created attachment 252425 [details]
> Patch

Still WIP, needs lots of cleaning.

[Basile Clement]

Created attachment 252500 [details]
Patch

Cleanup, OSR exit, proper MovHints, probably needs StoreBarriers somewhere

[Basile Clement]

Created attachment 254886 [details]
Patch

[WebKit Commit Bot]

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


ERROR: Source/JavaScriptCore/dfg/DFGValidate.cpp:558:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGObjectAllocationEliminationPhase.cpp:621:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGObjectAllocationEliminationPhase.cpp:628:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGObjectAllocationEliminationPhase.cpp:653:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGObjectAllocationEliminationPhase.cpp:677:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGObjectAllocationEliminationPhase.cpp:825:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGObjectAllocationEliminationPhase.cpp:843:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGObjectAllocationEliminationPhase.cpp:865:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGObjectAllocationEliminationPhase.cpp:868:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGObjectAllocationEliminationPhase.cpp:870:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGObjectAllocationEliminationPhase.cpp:886:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGObjectAllocationEliminationPhase.cpp:929:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGObjectAllocationEliminationPhase.cpp:956:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGObjectAllocationEliminationPhase.cpp:1142:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGObjectAllocationEliminationPhase.cpp:1146:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGObjectAllocationEliminationPhase.cpp:1195:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGObjectAllocationEliminationPhase.cpp:1248:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGObjectAllocationEliminationPhase.cpp:1252:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
Total errors found: 18 in 17 files


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

[Basile Clement]

Created attachment 255679 [details]
Patch

[Basile Clement]

Not asking for review right now since I realized ChangeLogs are not ready and I spend a lot of time fighting absurd benchmarking problems.

If the following results can be trusted (I don't even know anymore ; I spent the afternoon seeing slower results with the Options::enableAllocationCycleSinking() check than when forcing it to either true *or* false), looks like a nice speedup on Octane/earley (but this might be the adding of GetScope/SkipScope/GetExecutable as non-escaping, which could be easily backported to the old sinking phase).
Otherwise, no real change - which kind of makes sense, I suppose, since people creating cyclic object graphs locally without ever using them is probably pretty rare. It might also be due to patterns such as:

  var o = {};
  if (foo)
    o.x = { x: val, y: val };
  else
    o.x = { x: val, y: val };

which currently kill the analysis. I will investigate if that's the case, because adding support for this in the new sinking phase should be much easier than in the old one.

(Posting the bench result in another comment due to hitting the comment size limit)

[Basile Clement]

Created attachment 255681 [details]
Benchmark results

[Filip Pizlo]

Comment on attachment 255679 [details]
Patch

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

> Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:285
> +    Node* m_identifier;

m_identifier points to the node that does the allocation, right?  If so, it would be useful to document this in a brief comment, probably here.

> Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:311
> +    // argument a node-as-node. In the example graph above, at head
> +    // of block #1, getAllocation(#@1) is ObjectAllocation(#@1, [{}])
> +    // while onlyLocalAllocation(@1) is null (but
> +    // onlyLocalAllocation(@2) = getAllocation(#@1))

Which example graph?  You have two above, and both have @1 that is a NewObject.

(Note to self: LGTM up to here so far.)

> Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:841
> +            target = m_heap.onlyLocalAllocation(node->child2().node());

Why is this onlyLocalAllocation() rather than just getAllocation()?

(I guess I'm having a hard time understanding the difference.)

[Filip Pizlo]

Comment on attachment 255679 [details]
Patch

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

>> Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:311
>> +    // onlyLocalAllocation(@2) = getAllocation(#@1))
> 
> Which example graph?  You have two above, and both have @1 that is a NewObject.
> 
> (Note to self: LGTM up to here so far.)

Hmmm, I think I get it.  getAllocation() takes a node that is an actual allocation node, and gives us the allocation object for that node.  onlyLocalAllocation() takes any node that points to the allocation.

Now that I understand it, the names make sense to me.  I think this can be clarified in by:

- Making this comment have a copy of the example graph.  The redundancy is useful because the comment above may change, and because it's nice to read this comment without having to scroll to see the other one.
- Make it clear in the comment that getAllocation() takes a node that actually allocates.  The phrase "node-as-identifier" kind of says this, but you should clarify it.
- Add a comment on onlyLocalAllocation().

> Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:344
> +    Allocation* onlyLocalAllocation(Node* node)

Add a comment here to indicate that this gives a solution to the points-to problem.  Given a node, which may be a heap read or an allocation, it gives us the allocation.  It would be cool to add a comment that hints how you are meant to use this - for example when abstractly executing a GetByOffset(@node, field).  Explain why getAllocation() would not be appropriate for that use case.

> Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:365
> +    void setWantEscapees()
> +    {
> +        m_wantEscapees = true;
> +    }

You should explain what this is.  I guess it's a performance optimization to only compute the escapees when necessary?  If so, then it would be useful to note this here.

> Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:371
> +        HashMap<Node*, Allocation> result;
> +        result.swap(m_escapees);
> +        return result;

Hmmm, shouldn't "return WTF::move(m_escapees)" work here?

> Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:428
> +                for (const auto& pair : my.fields()) {
> +                    auto iter = their.fields().find(pair.key);
> +                    if (iter == their.fields().end()) {
> +                        toEscape.add(pair.value);
> +                        toRemove.append(pair.key);
> +                    } else if (iter->value != pair.value) {
> +                        toEscape.add(pair.value);
> +                        toEscape.add(iter->value);
> +                        toRemove.append(pair.key);
> +                    }
> +                }

So, if we have Phi(allocation1, allocation2), then all of the things that the fields of allocation1,allocation2 point to get escaped unless they point to the same thing?  I think a short blurb saying that this is what happens here would be useful.

Also, I find the reuse of "pair" and "iter" super confusing.  Could you rename them to say what they are.  Also I think that the term "entry" would be more correct for our HashMaps (which don't use std::pair).  So, you could rename this inner pair to "fieldEntry" and this inner iter to "fieldIter".  The outer pair/iter could be renamed to "allocationEntry" and "allocationIter".

> Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:458
> +        Vector<Node*> toRemove;
> +        for (const auto& pair : m_pointers) {
> +            auto iter = other.m_pointers.find(pair.key);
> +            if (iter == other.m_pointers.end()) {
> +                toEscape.add(pair.value);
> +                toRemove.append(pair.key);
> +            } else if (iter->value != pair.value) {
> +                toEscape.add(pair.value);
> +                toEscape.add(iter->value);
> +                toRemove.append(pair.key);
> +            }
> +        }
> +        for (const auto& pair : other.m_pointers) {
> +            if (m_pointers.contains(pair.key))
> +                continue;
> +            toEscape.add(pair.value);
> +        }
> +        for (Node* pointer : toRemove)
> +            m_pointers.remove(pointer);

Hmmm, this look super similar to the three loops above for fields. :-)  Did you consider capturing this in some template stuff?

> Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:475
> +    }

Note to self: LGTM up to here.

>> Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:841
>> +            target = m_heap.onlyLocalAllocation(node->child2().node());
> 
> Why is this onlyLocalAllocation() rather than just getAllocation()?
> 
> (I guess I'm having a hard time understanding the difference.)

I think I get it now. :-)

[Basile Clement]

Created attachment 255756 [details]
Patch

[Basile Clement]

(In reply to comment #10)
> > Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:285
> > +    Node* m_identifier;
> 
> m_identifier points to the node that does the allocation, right?  If so, it
> would be useful to document this in a brief comment, probably here.

Yes. Added a comment there.

> 
> > Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:311
> > +    // argument a node-as-node. In the example graph above, at head
> > +    // of block #1, getAllocation(#@1) is ObjectAllocation(#@1, [{}])
> > +    // while onlyLocalAllocation(@1) is null (but
> > +    // onlyLocalAllocation(@2) = getAllocation(#@1))
> 
> Which example graph?  You have two above, and both have @1 that is a
> NewObject.

There was an example graph at "class LocalHeap" at the time I wrote this that then got removed because it was trying to get across something that was actually irrelevant. I put back an example graph here, and tried to clarify the comments.
 
> > Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:841
> > +            target = m_heap.onlyLocalAllocation(node->child2().node());
> 
> Why is this onlyLocalAllocation() rather than just getAllocation()?
> 
> (I guess I'm having a hard time understanding the difference.)

Cf new comments for getAllocation and follow/onlyLocalAllocation.

(In reply to comment #11)
> >> Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:311
> >> +    // onlyLocalAllocation(@2) = getAllocation(#@1))
> > 
> > Which example graph?  You have two above, and both have @1 that is a NewObject.
> > 
> > (Note to self: LGTM up to here so far.)
> 
> Hmmm, I think I get it.  getAllocation() takes a node that is an actual
> allocation node, and gives us the allocation object for that node. 
> onlyLocalAllocation() takes any node that points to the allocation.
> 
> Now that I understand it, the names make sense to me.  I think this can be
> clarified in by:
> 
> - Making this comment have a copy of the example graph.  The redundancy is
> useful because the comment above may change, and because it's nice to read
> this comment without having to scroll to see the other one.
> - Make it clear in the comment that getAllocation() takes a node that
> actually allocates.  The phrase "node-as-identifier" kind of says this, but
> you should clarify it.
> - Add a comment on onlyLocalAllocation().

Done, done and done.

> 
> > Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:344
> > +    Allocation* onlyLocalAllocation(Node* node)
> 
> Add a comment here to indicate that this gives a solution to the points-to
> problem.  Given a node, which may be a heap read or an allocation, it gives
> us the allocation.  It would be cool to add a comment that hints how you are
> meant to use this - for example when abstractly executing a
> GetByOffset(@node, field).  Explain why getAllocation() would not be
> appropriate for that use case.

Done (although part of the explanation has rather been put in the comment above getAllocation()).

> 
> > Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:365
> > +    void setWantEscapees()
> > +    {
> > +        m_wantEscapees = true;
> > +    }
> 
> You should explain what this is.  I guess it's a performance optimization to
> only compute the escapees when necessary?  If so, then it would be useful to
> note this here.

Yes, added a comment.

> 
> > Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:371
> > +        HashMap<Node*, Allocation> result;
> > +        result.swap(m_escapees);
> > +        return result;
> 
> Hmmm, shouldn't "return WTF::move(m_escapees)" work here?

I am not a big fan of move'ing things that then get reused without being explicitly restored to a specific state first. No strong feeling here since WTF::HashTable would always restore m_escapees to an empty state, so I changed this.

> 
> > Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:428
> > +                for (const auto& pair : my.fields()) {
> > +                    auto iter = their.fields().find(pair.key);
> > +                    if (iter == their.fields().end()) {
> > +                        toEscape.add(pair.value);
> > +                        toRemove.append(pair.key);
> > +                    } else if (iter->value != pair.value) {
> > +                        toEscape.add(pair.value);
> > +                        toEscape.add(iter->value);
> > +                        toRemove.append(pair.key);
> > +                    }
> > +                }
> 
> So, if we have Phi(allocation1, allocation2), then all of the things that
> the fields of allocation1,allocation2 point to get escaped unless they point
> to the same thing?  I think a short blurb saying that this is what happens
> here would be useful.

I added an explanation at top of the mergePointerSets template function that now abstracts this. Note that we don't handle Phi(allocation1, allocation2) right now, but only Phi(allocation1, allocation1), which is admittedly less interesting. I talk about the possibility of handling Phi(allocation1, allocation2) in the blurb at head of file, and that would require the following:

 - Stop identifying allocations by the node that created them and use some abstract identifier instead (e.g. an integer would work fine). We could still use an allocation node, but it would now be completely meaningless (see below).
 - When merging heaps, build an renaming table identifying allocations in both heaps through pointers, then through fields of unified allocations etc, escaping things as needed on the fly
 - Store into allocations the block in which they were last part of a renaming, because we will need a Phantom allocation node when merging allocations that don't come from the same block (instead of the Phi node we would have had otherwise)
 - Ensure that we store or recompute the renaming mappings when creating Upsilon nodes so that we can adequately redirect them

> 
> Also, I find the reuse of "pair" and "iter" super confusing.  Could you
> rename them to say what they are.  Also I think that the term "entry" would
> be more correct for our HashMaps (which don't use std::pair).  So, you could
> rename this inner pair to "fieldEntry" and this inner iter to "fieldIter". 
> The outer pair/iter could be renamed to "allocationEntry" and
> "allocationIter".

Now called entry/iter in mergePointerSets. 

> 
> > Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:458
> > +        Vector<Node*> toRemove;
> > +        for (const auto& pair : m_pointers) {
> > +            auto iter = other.m_pointers.find(pair.key);
> > +            if (iter == other.m_pointers.end()) {
> > +                toEscape.add(pair.value);
> > +                toRemove.append(pair.key);
> > +            } else if (iter->value != pair.value) {
> > +                toEscape.add(pair.value);
> > +                toEscape.add(iter->value);
> > +                toRemove.append(pair.key);
> > +            }
> > +        }
> > +        for (const auto& pair : other.m_pointers) {
> > +            if (m_pointers.contains(pair.key))
> > +                continue;
> > +            toEscape.add(pair.value);
> > +        }
> > +        for (Node* pointer : toRemove)
> > +            m_pointers.remove(pointer);
> 
> Hmmm, this look super similar to the three loops above for fields. :-)  Did
> you consider capturing this in some template stuff?

See above.

[Basile Clement]

Created attachment 255867 [details]
Patch

[WebKit Commit Bot]

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


ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:455:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:458:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:466:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:469:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:996:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1015:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1101:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1274:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1292:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1304:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1450:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1528:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1685:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1735:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp:847:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGValidate.cpp:558:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
Total errors found: 16 in 25 files


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

[Filip Pizlo]

Comment on attachment 255867 [details]
Patch

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

> Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:503
> +    bool isValid() const

The only use of this is ASSERT(isValid()).  That means that if an error occurs, this method will return false, and the assertion will fire - but you won't know what about *this wasn't valid.

Maybe you can replace all uses of ASSERT(isValid()) with a call like assertIsValid(), rename this to assertIsValid(), have it return void, and put "if (ASSERT_DISABLED) return" at the top.

> Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1075
> +        // However, these rules allow for a sunk objet to be put into

*object

> Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1131
> +        // Implement the closure rule

This would be clearer as "Find the closure of sink candidates" or something like that.  When I see this comment in isolation from the one above, it seems like this has to do with actual closures (i.e. activations).

> Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1255
> +        HashMap<Node*, HashSet<Node*>> deps;
> +        HashMap<Node*, HashSet<Node*>> rdeps;

I recommend better variables names here.  We usually don't use abbreviations.  How about dependencies and reverseDependencies?

> Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1332
> +                int64_t maxEdges = 0;

Is it clear that you need int64_t here?  It seems like this is an unsigned quantity, and it's bounded by the number of nodes.  The number of nodes us usually unsigned, i.e. 32-bit.

> Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1390
> +    }

(Note to self: LGTM to here.)

[Basile Clement]

Created attachment 255926 [details]
Patch

[Basile Clement]

> > Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:503
> > +    bool isValid() const
> 
> The only use of this is ASSERT(isValid()).  That means that if an error
> occurs, this method will return false, and the assertion will fire - but you
> won't know what about *this wasn't valid.
> 
> Maybe you can replace all uses of ASSERT(isValid()) with a call like
> assertIsValid(), rename this to assertIsValid(), have it return void, and
> put "if (ASSERT_DISABLED) return" at the top.

Changed this.

> 
> > Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1075
> > +        // However, these rules allow for a sunk objet to be put into
> 
> *object

Fixed.

> 
> > Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1131
> > +        // Implement the closure rule
> 
> This would be clearer as "Find the closure of sink candidates" or something
> like that.  When I see this comment in isolation from the one above, it
> seems like this has to do with actual closures (i.e. activations).

Changed to "Ensure that the set of sink candidates is closed for put operations".

> 
> > Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1255
> > +        HashMap<Node*, HashSet<Node*>> deps;
> > +        HashMap<Node*, HashSet<Node*>> rdeps;
> 
> I recommend better variables names here.  We usually don't use
> abbreviations.  How about dependencies and reverseDependencies?

Changed this, here and in determineSinkCandidates.

> 
> > Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1332
> > +                int64_t maxEdges = 0;
> 
> Is it clear that you need int64_t here?  It seems like this is an unsigned
> quantity, and it's bounded by the number of nodes.  The number of nodes us
> usually unsigned, i.e. 32-bit.

The variable name is a misnomer from when I used the sum of incoming + outgoing edges (i.e. Put into this object and Put of this object into another) as a heuristic, while I now use the product of both, as it should reflect better of the "centrality" of the allocation w.r.t. others.
As a product of two 32-bit values we do need it to be 64-bit, but it should indeed be uint64_t. Changed that, and renamed it to maxEvaluation (and numEdges to evaluation).

> 
> > Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1390
> > +    }
> 
> (Note to self: LGTM to here.)

[WebKit Commit Bot]

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


ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:458:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:461:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:469:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:472:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:995:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1014:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1100:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1273:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1291:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1303:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1449:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1527:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1684:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1734:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp:847:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGValidate.cpp:558:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
Total errors found: 16 in 25 files


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

[Filip Pizlo]

Comment on attachment 255926 [details]
Patch

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

LGTM.  Please try to think of more correctness tests and add them in tests/stress.

You should split the ftl-no-cjit test run mode in run-jsc-stress-tests into ftl-no-cjit-experimental and ftl-no-cjit, where the -experimental one enables your phase.  You should do something similar for the internal spot check tests.  That way, while we still have both phases, our tests will test both of them.

> Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1308
> +        Vector<PromotedHeapLocation> toRecover;

Is there a better name?  Or add a comment that this is the cycle breaking.

> Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1329
> +            // We have an actual cycle

This appears to select what to materialize based on a heuristic.  Can you at least mention the fact that it is a heuristic in the comment?

> Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1379
> +            m_materializationSiteToRecoveries.add(
> +                where, Vector<PromotedHeapLocation>()).iterator->value.appendRange(
> +                    toRecover.begin(), toRecover.end());

Why not m_materializationSiteToRecoveries.add(where, toRecover)?

> Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1387
> +            m_materializationSiteToRecoveries.add(
> +                where, Vector<PromotedHeapLocation>()).iterator->value.appendRange(
> +                    hints.begin(), hints.end());

Ditto.

> Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp.orig:26
> +/*
> + * Copyright (C) 2014, 2015 Apple Inc. All rights reserved.
> + *
> + * Redistribution and use in source and binary forms, with or without
> + * modification, are permitted provided that the following conditions
> + * are met:
> + * 1. Redistributions of source code must retain the above copyright
> + *    notice, this list of conditions and the following disclaimer.
> + * 2. Redistributions in binary form must reproduce the above copyright
> + *    notice, this list of conditions and the following disclaimer in the
> + *    documentation and/or other materials provided with the distribution.
> + *
> + * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
> + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
> + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
> + * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
> + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
> + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
> + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
> + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
> + * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
> + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
> + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
> + */
> +
> +#include "config.h"

Seems like this file shouldn't be added?

[Basile Clement]

(In reply to comment #20)
> Comment on attachment 255926 [details]
> Patch
> 
> View in context:
> https://bugs.webkit.org/attachment.cgi?id=255926&action=review
> 
> LGTM.  Please try to think of more correctness tests and add them in
> tests/stress.

Oh, it looks like the tests I talked about have been lost somewhere. Disregard what I said offline ; there are 5-6 more tests that belong in tests/stress that I will add back.

> 
> You should split the ftl-no-cjit test run mode in run-jsc-stress-tests into
> ftl-no-cjit-experimental and ftl-no-cjit, where the -experimental one
> enables your phase.  You should do something similar for the internal spot
> check tests.  That way, while we still have both phases, our tests will test
> both of them.

I will look at this. Submitting a new patch tomorrow or next week with all these.

> 
> > Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1308
> > +        Vector<PromotedHeapLocation> toRecover;
> 
> Is there a better name?  Or add a comment that this is the cycle breaking.

I'll try to think about a better name and add a comment.

> 
> > Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1329
> > +            // We have an actual cycle
> 
> This appears to select what to materialize based on a heuristic.  Can you at
> least mention the fact that it is a heuristic in the comment?

There is a small explanation on the comment at 1218-1249 ; I'll add a comment for this.

> 
> > Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1379
> > +            m_materializationSiteToRecoveries.add(
> > +                where, Vector<PromotedHeapLocation>()).iterator->value.appendRange(
> > +                    toRecover.begin(), toRecover.end());
> 
> Why not m_materializationSiteToRecoveries.add(where, toRecover)?
> 
> > Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1387
> > +            m_materializationSiteToRecoveries.add(
> > +                where, Vector<PromotedHeapLocation>()).iterator->value.appendRange(
> > +                    hints.begin(), hints.end());
> 
> Ditto.


Because we could have recoveries at the same node for several reasons. Off the top of my head I can only think of two cases (a terminal node that escapes an allocation and follows up to an edge that also escapes other allocations, and allocations that escape on two different outgoing edges) where this would happen, and I believe that those are not possible right now.
I preferred using the safe approach rather than introducing super subtle bugs when one day we end up with a Branch on a NewObject or something.

> 
> > Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp.orig:26
> > +/*
> > + * Copyright (C) 2014, 2015 Apple Inc. All rights reserved.
> > + *
> > + * Redistribution and use in source and binary forms, with or without
> > + * modification, are permitted provided that the following conditions
> > + * are met:
> > + * 1. Redistributions of source code must retain the above copyright
> > + *    notice, this list of conditions and the following disclaimer.
> > + * 2. Redistributions in binary form must reproduce the above copyright
> > + *    notice, this list of conditions and the following disclaimer in the
> > + *    documentation and/or other materials provided with the distribution.
> > + *
> > + * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
> > + * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
> > + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
> > + * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
> > + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
> > + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
> > + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
> > + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
> > + * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
> > + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
> > + * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
> > + */
> > +
> > +#include "config.h"
> 
> Seems like this file shouldn't be added?

Oops, indeed.

[Basile Clement]

Created attachment 256018 [details]
Patch

[WebKit Commit Bot]

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


ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:458:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:461:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:469:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:472:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:995:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1014:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1100:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1273:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1291:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1303:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1459:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1537:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1694:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1744:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp:847:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGValidate.cpp:558:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
Total errors found: 16 in 38 files


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

[Basile Clement]

Created attachment 256041 [details]
Patch

[WebKit Commit Bot]

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


ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:458:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:461:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:469:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:472:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:995:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1014:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1100:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1273:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1291:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1303:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1457:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1535:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1692:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGAllocationCycleSinkingPhase.cpp:1742:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp:847:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGValidate.cpp:558:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
Total errors found: 16 in 38 files


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

[Basile Clement]

Created attachment 256721 [details]
Patch for landing

[WebKit Commit Bot]

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


ERROR: Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp:458:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp:461:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp:469:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp:472:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp:995:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp:1014:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp:1100:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp:1273:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp:1291:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp:1303:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp:1457:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp:1535:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp:1692:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGObjectAllocationSinkingPhase.cpp:1742:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
ERROR: Source/JavaScriptCore/dfg/DFGValidate.cpp:562:  Place brace on its own line for function definitions.  [whitespace/braces] [4]
Total errors found: 15 in 28 files


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

[Basile Clement]

Committed r186795: <http://trac.webkit.org/changeset/186795>