As I write this issue, I am concurrently landing a change which makes Node DFS iterative rather than recursive. The discussion in code review revealed some ways in which a visitor that mutates the IR can expose implementation details of the DFS.
In particular, it was suggested to have a simpler DFS that didn't keep an iterator pointing to a Node's current operand and to instead push all operands on the stack. This would give the same order on static IR, but if a visitor mutates the IR it could give a different order. Consider:
q = op()
x = op()
y = op()
z = op(y)
ret out = op(z, x)
When we visit out, a DFS that pushes all operands (as opposed to having an iterator) has the largest stack be [out, x, z, y].
Let's say when visiting y, we replace x with q for some reason. When the original recursive implementation finished visiting z, it would move on to the next operand and visit q. With an implementation that pushes everything on the stack, you will first visit x and then either check every operand again and visit qor not check every operand and not visit q. In the first case, you will potentially visit other replaced nodes the original implementation wouldn't have visited. In the second case, you visit a node the original wouldn't have (x) and you won't visit a node the original would have (q). This is especially hairy if visiting any of these (before or after) replaced nodes throws an error.
It's not clear what the ideal behavior should be. We should revisit (heh) this eventually and evaluate alternatives- perhaps the visitor should describe how it anticipates mutating the IR and you can dispatch based on that.
grebe
commented
3 weeks ago
As I write this issue, I am concurrently landing a change which makes Node DFS iterative rather than recursive. The discussion in code review revealed some ways in which a visitor that mutates the IR can expose implementation details of the DFS.
In particular, it was suggested to have a simpler DFS that didn't keep an iterator pointing to a Node's current operand and to instead push all operands on the stack. This would give the same order on static IR, but if a visitor mutates the IR it could give a different order. Consider:
When we visit
out, a DFS that pushes all operands (as opposed to having an iterator) has the largest stack be[out, x, z, y].Let's say when visiting y, we replace
xwithqfor some reason. When the original recursive implementation finished visitingz, it would move on to the next operand and visitq. With an implementation that pushes everything on the stack, you will first visitxand then either check every operand again and visitqor not check every operand and not visitq. In the first case, you will potentially visit other replaced nodes the original implementation wouldn't have visited. In the second case, you visit a node the original wouldn't have (x) and you won't visit a node the original would have (q). This is especially hairy if visiting any of these (before or after) replaced nodes throws an error.It's not clear what the ideal behavior should be. We should revisit (heh) this eventually and evaluate alternatives- perhaps the visitor should describe how it anticipates mutating the IR and you can dispatch based on that.