|Summary:||DFG should have control flow graph simplification|
|Product:||WebKit||Reporter:||Filip Pizlo <fpizlo>|
|Version:||528+ (Nightly build)|
|Bug Depends on:|
|Bug Blocks:||86918, 86939|
Description Filip Pizlo 2012-04-22 15:09:58 PDT
Comment 2 Filip Pizlo 2012-04-22 17:06:19 PDT
Created attachment 138280 [details] it seems to work There appear to still be some issues, like that the fixpoint is not converging as fast as it probably should. I'll investigate more and then start running bigger tests.
Comment 3 Filip Pizlo 2012-04-22 17:58:19 PDT
Created attachment 138281 [details] getting close Fixed the convergence problem, which was due to constant abstract values being deconstantified upon inter-block merging. This then revealed a bunch of bugs in constant folding of GetLocal. So I fixed them. Right now the code is kind of performing as expected for simple code. But I still need to test it more and do more investigation to ensure that I haven't introduced some horrible problems.
Comment 4 Filip Pizlo 2012-04-22 19:48:55 PDT
Found some fun issues: - Merging the taken successor when the branch condition is known is wrong if that successor has multiple predecessors. We should convert the branch to a jump in that case, and insert phantoms for those things that were live in the not-taken successor. - The handling of constant folding on GetLocal is wrong. First, it fails to deref the child of the GetLocal, which means that the original SetLocal is still executed even if it need not be. This leads to the graph being in an inconsistent state where the SetLocal will have a ref count than is greater than the number of nodes using it. Second, it's not clear that it will correctly inform OSR exit of the value of the local, if the original SetLocal is killed. Likely the best way to fix this would be that for any block in which the valueAtHead is a constant, we insert a JSConstant/dead-SetLocal pair at the top of the block, and link variablesAtHead to that SetLocal. Link variablesAtTail to that SetLocal also, if variablesAtTail was equal to variablesAtHead. Constant folding a GetLocal ought to assert that the local has been relinked in this fashion in this basic block. But this appears to be dangerous, since a subsequent run of the CFA might get massively confused. Consider that we might have a block that does not use a variable but knows that the variable is a constant. Then it will have a dead SetLocal at the top. But since it's dead, the CFA will assume that the block kills the variable. So the constant value that flowed through this block will not be propagated correctly. Ouch! I need to think about this more. All of this does bring up an interesting question: could we perform constant propagation as a block-local analysis separate from CFA, and then propagate results between blocks by observing when a block uses a GetLocal that is linked to SetLocal of a JSConstant. The problem with that approach is that it won't work cleanly with value speculation or sparse conditional constant propagation, since it will depend too much on interleaving with CFG simplification.
Comment 5 Filip Pizlo 2012-04-24 01:33:11 PDT
I've decided that: - We should have Phantom nodes in place of GetLocals in the constant folder. This means that Phantom nodes participate in operand-related liveness. So you may have Phantom(SetLocal), Phantom(Flush), Phantom(SetArgument), or Phantom(Phi). The control flow simplification will forward Phantom(operand instruction) to Phantom(source of the operand instruction) if the operand's value is known locally due to a SetLocal. - We need to clean up unreachable blocks correctly. This means removing dead Phi edges. More subtly, it means that if we jettison a block - which may not render it unreachable, yet - then we must remove those Phi edges outgoing from that block that targeted the predecessor that we are killing. - We need IR verification. Many of the invariants that we're allegedly upholding in this phase are not documented anywhere and may already be invalidated by bugs in other parts of the compiler. We need a phase that enforces the invariants that we're interested in. We can disable this phase for release builds, but it should always be on in debug builds.
Comment 6 Filip Pizlo 2012-04-24 01:35:09 PDT
Created attachment 138517 [details] getting closer - Implemented (hopefully) correct handling of Phantom keep-alive for children of GetLocals killed by constant folding. - Implemented (hopefully) correct handling of Branch(constant), in that we now only merge blocks if the taken successor of the branch has only one predecessor. - Implemented (hopefully) correct unreachable block destruction. - Started to implement, but did not finish, the handling of jettisoned blocks with respect to Phi edges.
Comment 7 Filip Pizlo 2012-04-24 01:54:03 PDT
Created attachment 138519 [details] more - Implemented more of the handling of removing a block from the predecessors list. - Also chose to rely on redundant phi elimination not being run, since that would only make things more complicated.
Comment 8 Filip Pizlo 2012-04-24 16:35:41 PDT
Created attachment 138683 [details] more - Ensured that the state of variablesAtHead/variablesAtTail after constant folding and CFG simplification complies with our DFG-style CPS conventions. - Fixed a bug where the value of the condition passed to Branch was not being interpreted correctly.
Comment 9 Filip Pizlo 2012-04-24 19:27:23 PDT
Created attachment 138720 [details] starting to run SunSpider Fixed miscellaneous bugs. I can now run some of the SunSpider benchmarks.
Comment 10 Filip Pizlo 2012-04-24 20:32:52 PDT
Created attachment 138729 [details] it appears to work Runs SunSpider, V8, and Kraken. Still need to test performance and run more tests.
Comment 11 Filip Pizlo 2012-04-25 22:17:28 PDT
Created attachment 138934 [details] almost there This appears to work, and is performance neutral, except on Kraken, where it is an ever-so-slight win. Still running more tests. Will set to r? if I find it to work on all the relevant ones, otherwise it's back to work for me.
Comment 12 Filip Pizlo 2012-04-25 22:41:59 PDT
Yup, I found another bug. Consider that we have block A that branches to blocks B and C. Both blocks B and C then jump to block D. We notice that block A will always jump to block B, so we jettison block C. We currently successfully clean up C's phis so that they do not point to A anymore. But let's assume that there are no other jumps to C, so C is unreachable now. We will fail to clean up D's incoming phis to reflect this. Ooops!
Comment 13 Filip Pizlo 2012-04-26 19:37:49 PDT
Created attachment 139123 [details] and now, passing more tests than ever!
Comment 15 Oliver Hunt 2012-04-27 10:50:26 PDT
Comment 16 Filip Pizlo 2012-04-27 11:38:27 PDT
Comment 17 Filip Pizlo 2012-04-27 15:06:08 PDT
(In reply to comment #15) > (From update of attachment 139140 [details]) > View in context: https://bugs.webkit.org/attachment.cgi?id=139140&action=review > > r=me, but make sure we don't have any custom toBoolean(CallFrame*) overrides in WebCore -- I recall that there was one, something like document.all -- but it's possible we hanlde that with the MasqueradesAsUndefined flag. Would overrides be possible, given that toBoolean() is not in the methodTable?