Bug 103727 – Unset NodeMustGenerate flag for Call nodes of few String.prototype.* pure functions

• Status: UNCONFIRMED
• Component: JavaScriptCore

[Dmitry Melnik]

Function calls have NodeMustGenerate flag set, but this is redundant in case the function has no side effects.  This patch aims to remove NodeMustGenerate flag for Call nodes of String.replace, String.split, and String.indexOf, if their argument types imply no side effects. This would allow to eliminate such calls, if their result is unused.

Example:

function foo() {
  var str = "split it up";
  var i;
  for (i = 0; i < 10000; i++) {
    var x = str.split(" ");
  }
}

var i;
for (i = 0; i < 1000; i++)
  foo();

Run time w/o patch: 1.756s
With the patch: 0.032s

Is it, in general, the right way to eliminate redundant calls?
I admit that using strcmp is not the best way to check for function names -- probably it would be better to create a hashtable with mapping of function names to argument checking routines, but for now I just would like to get some feedback to know whether this optimization is correct and if the WebKit community is interested in it.

[Dmitry Melnik]

Created attachment 176931 [details]
patch

[Filip Pizlo]

Comment on attachment 176931 [details]
patch

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

> Source/JavaScriptCore/dfg/DFGAbstractState.cpp:2045
> +    node.clearFlags(NodeMustGenerate);

It's not correct to do this inside AbstractState - since you have no way of knowing , yet, if the CFA has converged and if the function value you're relying upon is accurate. 

Instead, you should just move this whole method to the constant folding phase. (I know, really bad name for a phase since it does more than constant folding.). That phase runs after CFA converges so you can be sure that the function is accurate.

[Filip Pizlo]

(In reply to comment #0)
> Function calls have NodeMustGenerate flag set, but this is redundant in case the function has no side effects.  This patch aims to remove NodeMustGenerate flag for Call nodes of String.replace, String.split, and String.indexOf, if their argument types imply no side effects. This would allow to eliminate such calls, if their result is unused.
> 
> Example:
> 
> function foo() {
>   var str = "split it up";
>   var i;
>   for (i = 0; i < 10000; i++) {
>     var x = str.split(" ");
>   }
> }
> 
> var i;
> for (i = 0; i < 1000; i++)
>   foo();
> 
> Run time w/o patch: 1.756s
> With the patch: 0.032s
> 
> Is it, in general, the right way to eliminate redundant calls?
> I admit that using strcmp is not the best way to check for function names -- probably it would be better to create a hashtable with mapping of function names to argument checking routines, but for now I just would like to get some feedback to know whether this optimization is correct and if the WebKit community is interested in it.

I believe that what you are doing is broadly correct. You should just fix the bug regarding not making graph changes from AbstractState.

I'm also wondering if maye we should clear the NodeClobbersWorld flag...

Final thought: we would have previously used intrinsically to accomplish what you're doing. But I don't think that makes your approach wrong; particularly since your approach doesn't require new node types or any other special treatment of the fictions in question.

[Dmitry Melnik]

Created attachment 177258 [details]
updated patch

I moved the code to Constant Folding phase, and also added clearing of NodeClobbersWorld flag.

[Darin Adler]

Comment on attachment 177258 [details]
updated patch

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

> Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp:41
> +extern const HashTable stringTable;

This is an anti-pattern. If we want to use an external symbol, we should include the header it’s declared in, not re-declare it inside a file that’s using it.

[EFL EWS Bot]

Comment on attachment 177258 [details]
updated patch

Attachment 177258 [details] did not pass efl-wk2-ews (efl-wk2):
Output: http://webkit-queues.appspot.com/results/50311

[Filip Pizlo]

Comment on attachment 177258 [details]
updated patch

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

I think this will be unsound if we exit prior to where the call used to be, and the baseline JIT uses callee and this in the call. It'll probably crap out with an exception like that 'undefined' isn't callable. You should figure out what you want to do about that. One option is to convert the Call to a Phantom. A potentially better solution is to just make those functions intrinsic. That would save you from a lot of the trouble.

> Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp:89
> +        const HashTableValue& fEntry = JSC::stringTable.values[i];

I don't think we want this to become a pattern. It would be much better to make split and friends into intrinsics and detect this in the parser. It will conserve compile times, among other things.

[Valery Ignatyev]

Created attachment 217942 [details]
patch for discussion

This is the preliminary patch posted to discuss the suggested approach.  Regarding your proposal to use intrinsics, we would like to implement more general approach. Please let us know any feedback.

Also, we have successfully used m_graph.deref(nodeIndex) to remove instructions from DFG in the older webkit, but at the moment this approach doesn't work.  Could you please suggest the correct way for removing instructions? In function  bool performRedundantCallElimination(Node *callNode) we've tried different combinations of
          callNode->clearFlags(NodeMustGenerate | NodeClobbersWorld);                                                                                       
          callNode->children.reset();                                                                                                           
          callNode->convertToPhantomUnchecked();                                                                      
          callNode->setRefCount(0)
without success.