Bug 91188 - DFG CFA may get overzealous in loops that have code that must exit
Summary: DFG CFA may get overzealous in loops that have code that must exit
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: JavaScriptCore (show other bugs)
Version: 528+ (Nightly build)
Hardware: All All
: P2 Normal
Assignee: Filip Pizlo
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2012-07-12 20:57 PDT by Filip Pizlo
Modified: 2012-07-12 22:31 PDT (History)
0 users

See Also:


Attachments
the patch (18.05 KB, patch)
2012-07-12 21:00 PDT, Filip Pizlo
fpizlo: review-
Details | Formatted Diff | Diff
the patch (25.97 KB, patch)
2012-07-12 21:07 PDT, Filip Pizlo
no flags Details | Formatted Diff | Diff
the patch (26.39 KB, patch)
2012-07-12 21:56 PDT, Filip Pizlo
barraclough: 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 2012-07-12 20:57:31 PDT
This is quite convoluted, but awesome.  Say that the CFA proves that some operation:

c: MyNode(@a, @b)

must exit because the predictions of @a and/or @b are incompatible with our implementation of NyNode.

But say that the CFA also proves that @a is Int32(0) and @b is Int32(1).  The CFA is very precise - often more precise than our prediction propagation.  So it could be that @a and @b have wacky predictions but can be proved to be something more specific.

And say that c:MyNode is in a loop, and that the result of @c feeds into @a because of an in-loop assignment to some variable.  But since the CFA proved that @c terminates, it ignored its output when computing the proof of @a.  If @c had executed, then @a would have been some variant of TOP.

Now you've got a situation where:

1) The CFA aggressively set the value of @a based on the assumption that @c terminates.
2) The fact that @a and @b were pinpointed to be values caused the backend, and subsequent executions of the CFA, to happily compile @c into a non-terminating instruction.

The result? You've now got a loop in which some variable appears to never be updated. This often manifests as a loop that runs forever because the variable in question is the loop's induction variable.

Furthermore, because of http://trac.webkit.org/changeset/119464, even if we fix this problem we're left with a deeper problem: CFG simplification may then lead OSR exit to believe that the body of the loop only sets but does not read the variable.  In fact it doesn't read it in the DFG code (since it's constant folded) but it does read it in the baseline code - so OSR must assume as such.  That's particularly important since this loop will OSR exit every time.

Fix and test on the way.
Comment 1 Filip Pizlo 2012-07-12 21:00:32 PDT
Created attachment 152145 [details]
the patch

I will post the test shortly.  Still computing the expected result.
Comment 2 Filip Pizlo 2012-07-12 21:01:29 PDT
Comment on attachment 152145 [details]
the patch

Ooops.  Never mind.
Comment 3 Filip Pizlo 2012-07-12 21:07:51 PDT
Created attachment 152149 [details]
the patch
Comment 4 Gavin Barraclough 2012-07-12 21:41:58 PDT
Comment on attachment 152149 [details]
the patch

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

> Source/JavaScriptCore/dfg/DFGConstantFoldingPhase.cpp:60
> +            m_insertionSetForFolding.execute(*block);

This may insert the phantoms in the wrong place, Phi will fix.
Comment 5 Filip Pizlo 2012-07-12 21:56:31 PDT
Created attachment 152152 [details]
the patch
Comment 6 Filip Pizlo 2012-07-12 22:31:30 PDT
Landed in http://trac.webkit.org/changeset/122541