3 ms·
I don’t think the compilers recognize the specific idiom here, but instead (what you also say) perform normalizations (e.g. into static single assignment form),
by layer8 5y ago
I don’t think the compilers recognize the specific idiom here, but instead (what you also say) perform normalizations (e.g. into static single assignment form), expression analysis and elimination, yielding the same result. For the present case, I’d imagine a sequence of transformations like this:
Convert into SSA:
c = a + b;
d = c - b;
e = c - d;
b’ = d;
a’ = e;
Eliminate c:
d = a + b - b;
e = a + b - d;
b’ = d;
a’ = e;
Simplify d:
d = a;
e = a + b - d;
b’ = d;
a’ = e;
Eliminate dependency of e on d:
d = a;
e = a + b - a;
b’ = d;
a’ = e;
Simplify e:
d = a;
e = b;
b’ = d;
a’ = e;
Eliminate d:
e = b;
b’ = a;
a’ = e;
…resulting in the normal swap.
- a_e_k 5y agoTrue; I probably overstated it in terms of idiom recognition (compiler enthusiast, but by no means expert). I suspect that a similar SSA or data flow analysis combined with some judicious rewrite rules like (X ^ Y) ^ Y -> X [0] are enough for the xor swap trick as well. [0] https://github.com/gcc-mirror/gcc/blob/9fdac7e16c940fb6264e6ddaf99c761f1a64a054/gcc/match.pd#L1492 https://github.com/gcc-mirror/gcc/blob/9fdac7e16c940fb6264e6...
- civilized 5y agoThis is fascinating.
- tialaramex 5y agoIdiom recognition has been a thing in compilers for decades, so certainly don't rule it out.