3 ms·
> There's no theoretical difference between phis and basic block parameters. I question this claim. Don't basic block parameters allow you to do interesting st
by tom_mellior 6y ago
> There's no theoretical difference between phis and basic block parameters.
I question this claim. Don't basic block parameters allow you to do interesting stuff also at split points, not only at join points?
For example:
if (x == 0) {
y = 2 * x;
} else {
y = 3 * x;
}
In SSA form this is:
if (x == 0) jump B1 else jump B2
B1:
y1 = 2 * x
jump join
B2:
y2 = 3 * x
jump join
join:
y = phi(y1, y2)
You need conditional constant propagation to realize that y1 must be 0.
But with basic block arguments you could do this (improvising notation on the spot):
if (x == 0) jump B1(0) else jump B2(x)
B1(arg1):
y1 = 2 * arg1;
jump join(y1)
B2(arg2):
y2 = 3 * arg2;
jump join(y2)
join(y):
...
Basically, as soon as information becomes available (x is 0 along some path), that is explicit in the IR. Realizing that y1 is 0 only takes simple, non-conditional sparse constant propagation. You might not call that a "theoretical" difference (what theory are we talking about?), but it does give you a simple way to access information that is not explicit in SSA form.
In effect this latter representation is something like Static Single Information (SSI) form: https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.1.9976 https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.1.9...
- jcranmer 6y agoAs I explained in my footnote, you can do the same thing with SSA form: if (x == 0) jump B1 else jump B2 B1: x1 = phi(x) y1 = 2 * x1 jump join B2: x2 = phi(x) y2 = 3 * x2 jump join join: y = phi(y1, y2) And then you can do the same propagation of the x == 0 to the phi in B1 pretty easily. It is somewhat harder than the basic-block argument case, but that's because basic block arguments rely on the data binding being put in the head of the edge and we're pushing data from the head into the edge. The next step of checking if all incoming edges are identically 0 would be easier in the phi-form, since the data binding is in the tail node, and we're pulling data from the edge into the tail.