5 ms·

What 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 loa

by qznc 13y ago

What 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 ago
Yes, 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 ago
  Thanks 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 ago
    Minor correction: LibFirm also generates pruned SSA, which is the property that guarantees lack of dead phis. Minimal SSA roughly means "no superfluous live phis".
    - DannyBee 13y ago
      Let me know if you still do this once you integrate a polyhedral code generator and try to do incremental SSA renaming on the nested loop outputs :) Note that dead phis are actually useful in some contexts, particularly around loop updates This is why things like loop-closed ssa (http://gcc.gnu.org/onlinedocs/gccint/LCSSA.html http://gcc.gnu.org/onlinedocs/gccint/LCSSA.html) exist, and phi nodes are generated even if the variable is never initially used outside the loop (makes sinking easier)

by qznc 13y ago

DannyBee 13y ago

Yes, 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 ago
Thanks 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 ago
  Minor correction: LibFirm also generates pruned SSA, which is the property that guarantees lack of dead phis. Minimal SSA roughly means "no superfluous live phis".
  - DannyBee 13y ago
    Let me know if you still do this once you integrate a polyhedral code generator and try to do incremental SSA renaming on the nested loop outputs :) Note that dead phis are actually useful in some contexts, particularly around loop updates This is why things like loop-closed ssa (http://gcc.gnu.org/onlinedocs/gccint/LCSSA.html http://gcc.gnu.org/onlinedocs/gccint/LCSSA.html) exist, and phi nodes are generated even if the variable is never initially used outside the loop (makes sinking easier)