4 ms·
http://www.cs.ucla.edu/~palsberg/paper/cc09.pdf http://www.cs.ucla.edu/~palsberg/paper/cc09.pdf spill free phi elimination in polynomial time :) There are oth
by DannyBee 13y ago
http://www.cs.ucla.edu/~palsberg/paper/cc09.pdf http://www.cs.ucla.edu/~palsberg/paper/cc09.pdf
spill free phi elimination in polynomial time :)
There are other algorithms that may coalesce more phis, and can be done in linear time, but do not have such guarantee.
If your concern is dead phis, all dead phis (where dead is defined as unused, or only used by dead instructions) can be eliminated in linear time by performing a single linear time backwards-DCE pass on the graph.
This will get all phis and instructions that are dead, or only used by instructions that are themselves dead.
If your concern is useless phis and instructions (for lack of a better term, there are papers, and they use the word "dead" differently, so i'm defining a term here for you), where you define useless as "side-effects do not matter", such that in
*a = 5
c = a
*a = 5
c = a
the second store and assignment is useless,
This type of elimination is O(N^3) normally, and unproven bounds in SSA (AFAIK).
- aidenn0 13y agoThanks for that info; I have more reading to do. The actual work I get paid to do isn't on an SSA compiler, so keeping up-to-date on SSA is more of a hobby.
- qznc 13y agoWhat exactly is "this type of elimination"? Within our compiler [0] your concrete example is optimized by an O(1) mechanism and then there is a more complex load-store-optimization which is O(n^2) I think. [0] http://pp.ipd.kit.edu/firm/ http://pp.ipd.kit.edu/firm/
- DannyBee 13y agoYes, I should have given a partially dead example. You must not mean O(1) because you at least must be walking the instructions to eliminate them (looking at your code, you do). If you include partial dead store elimination, it will be N^3 at least on non-SSA. see http://www.cs.ucr.edu/~gupta/teaching/201-12/Papers/pde.pdf http://www.cs.ucr.edu/~gupta/teaching/201-12/Papers/pde.pdf and friends Looking at your code, libfirm's DCE the standard SSA backwards DCE algorithm without control dependence computation to eliminate dead phis. It will be O(n). The load store optimization looks like a modification of stuff i helped Thomas VanDrunen with. It is O(N^2), but will miss loads/stores depending entirely on the strength of your memory dependence calculation. In fact, it will miss a lot, particularly around loop dependent store/load values that are equivalent. It will catch my particular example, but GCC's testsuite has load/store examples (see gcc/testsuite/gcc.dg/tree-ssa) that it should fail at without help from other phase ordering/etc.
- qznc 13y agoThanks for the clarification. You are right, our load-store-opt cannot handle loops. Dead code elimination technically [0] is O(n). However, it should be called "copying garbage collection" instead. LibFirms SSA construction is minimal [1], it does not create dead phis. Or course, phis might die due to optimizations, in which case they become unreachable and get garbage collected at some point (see above). However, Firm does not model memory (global variables) as SSA, only registers (local variables). [0] https://github.com/MatzeB/libfirm/blob/master/ir/opt/dead_code_elimination.c https://github.com/MatzeB/libfirm/blob/master/ir/opt/dead_co... [1] https://pp.info.uni-karlsruhe.de/publication.php?id=braun13cc https://pp.info.uni-karlsruhe.de/publication.php?id=braun13c...
- qznc 13y agoMinor correction: LibFirm also generates pruned SSA, which is the property that guarantees lack of dead phis. Minimal SSA roughly means "no superfluous live phis".
- 13y ago