677143 - IonMonkey: GVN does not quite follow the algorithm in the paper.

Status: RESOLVED DUPLICATE of bug 1004363

(Core :: JavaScript Engine, defect)

Description

[Ryan Pearl [:rpearl]]

In the paper, when we hash an expression (say, x = y op z), we put a mapping from (op, VN[y], VN[z]) => some VN, into the hashtable.

However, in the current implementation, the table maps an MDefinition pointer to a value number. This means that if any of the operands of the MDefinition change, then the expression in the table has effectively changed. If we put Add(id 3, id 4) into the table, and the id of 3 changes, then the expression in the table changes.

Since we iterate in reverse postorder, we will see the operands of a def before the def, so this isn't an issue, except at the back-edges in the CFG. So, we will need to special-case phis to "capture" the value numbers seen when we put them in the table.

Comment 1

[Dan Gohman [:sunfish]]

The new GVN implementation (bug 1004363) fixes this. It also iterates in RPO, but it has a special-case for phis in loop headers. When it reaches the backedge of a loop, it examines the phis in the loop header to see if any of them that weren't previously optimized have become optimizable. Since this is relatively uncommon, it just restarts the entire algorithm rather than maintaining the bookkeeping needed to roll back to an earlier state.