1031412 - GVN should mine unreachable blocks for newly dead definitions

Status: RESOLVED DUPLICATE of bug 1029830

(Core :: JavaScript Engine: JIT, enhancement)

Description

[Dan Gohman [:sunfish]]

When GVN removes a basic block, it deletes all the instructions and phis in the block. However, it doesn't currently scan the use-def subgraphs of those instructions and phis which will become dead as a result. In practice, when this happens, GVN usually ends up rerunning for other reasons anyway, but there are cases where it doesn't and it misses opportunities for further optimization.

Comment 1

[Shashank VRSN Sabniveesu]

Hi! I have done a few 'Good First Bugs' and am interested in taking this up as a challenge. Can I have a few specifics as in:

* What components (of C++ as well as Firefox codebase) should I be familiar with to work on this?
* How to detect what parts of code are currently being missed?
* What files to look at?
* Any other details you beleive I need to know

Comment 2

[Dan Gohman [:sunfish]]

Ok! As a caveat, I didn't mark this a 'Good First Bug' because there are some parts of this that will be tricky to get right. Also, this is in IonMonkey, and it will require some compiler familiarity, such as Control-Flow Graphs and SSA form, and of course GVN. I believe these things are learnable, and I can help you (here in this bug and on irc -- #ionmonkey), but just be prepared.

The main file involved here in Firefox is js/src/jit/ValueNumbering.cpp. This is where the GVN implementation lives.

One way to look for dead code which the GVN pass is missing is to run the GVN pass twice in a row, instead of just once (passes are scheduled in OptimizeMIR in Ion.cpp). You can set the environment variable IONFLAGS=gvn to get a trace of what GVN is doing. In theory, a second GVN pass shouldn't find anything to do. If it does find something, it's something that the first pass missed.

Comment 3

[Dan Gohman [:sunfish]]

GVN won't actually remove any blocks until bug 1029830 lands, so I'm marking that bug as a dependency.

Also, the dominator refinement check is currently triggering re-runs more often than it needs to. When a re-run is triggered, it masks this bug because the re-run will clean up any newly dead instructions. I filed bug 1049172 to track that, since it's desirable to reduce the number of re-runs in any case.

Once these two bugs are fixed, the problem described in this bug will become more visible, because there will be more situations where blocks are removed without triggering re-runs.

Comment 4

[Dan Gohman [:sunfish]]

The example in bug 1049172 is the example for this bug too:

        t = ...;
        if (a) {
            if (false) {
                ... = t;
            } else {
                foo();
            }
            // empty merge block
        }
        // final merge block

When the if is folded, the then block is discarded. If t has no other uses, it will become dead. If GVN avoids triggering a re-run after folding the if, then the assignment to t will not be discarded, because GVN doesn't currently mine the contents of the removed block for newly-dead definitions.

Comment 5

[Dan Gohman [:sunfish]]

I've now put the example code above into a full testcase, attached to bug 1049172. With GVN hacked to not re-run, the assignment to t isn't discarded.

Comment 6

[Dan Gohman [:sunfish]]

I ended up implementing this as part of some code reorganization in the patch in bug 1029830 comment 17.