This series replace the current SSA conversion by one using the 'classical' way, via the iterated dominance frontier. This code is already decently tested and fixes numerous problems (helped by all the preparatory series). The only kind of regressions I saw was for kernel checks where, in the configs I use, there is 23 more "context imbalance" warnings. These may be genuine or not, they still need to be investigated. The performance is almost exactly the same as before (but depends surely on the input, I only measured for kernel checks). This is a big step toward correct SSA but more is needed: - Fix or rewrite simplify_loads() which suffer the same problems as the current SSA conversion. Ideally, it should reuse the code in this series but the situation/context is quite different more concerned about pointers than with 'simple' variables. - SSA is broken, probably in several ways, during BB simplification. - Some incorrect phi-nodes may be created during linearization when some branches are inactive/never reachable. Also: - there is also a lot of polishing and optimization that can be done on the current implementation. - a lot of places can make good use of the dominance tree. - UNDEFs must be handled, several things are possible but no more "crazy programmer" warnings and no more infinite loops! This series is available for review & testing in the Git repository at: git://github.com/lucvoo/sparse-dev.git ssa-v1 https://github.com/lucvoo/sparse-dev/tree/ssa-v1 Constructive feedback is more than welcome. ---------------------------------------------------------------- Luc Van Oostenryck (18): graph: build the CFG reverse postorder traversal graph: add debugging for (reverse) postorder traversal dom: calculate the dominance tree dom: add some debugging for the dominance tree dom: add support for dominance queries dom: build the domtree before optimization dom: use domtree for bb_dominates() sset: add implementation of sparse sets idf: compute the iterated dominance frontier idf: add test/debug/example add new helper: is_integral_type() add PSEUDO_UNDEF & undef_pseudo() add insert_phi_node() ptrmap: core implementation ptrmap: add type-safe interface ssa: SSA conversion, the classical way ssa: remove unused simplify_symbol_usage() ssa: phi worklist Documentation/dev-options.md | 2 + Makefile | 5 + cse.c | 27 +-- dominate.c | 153 +++++++++++++++ dominate.h | 9 + flow.c | 278 -------------------------- flowgraph.c | 219 +++++++++++++++++++++ flowgraph.h | 13 ++ lib.c | 4 + lib.h | 2 + linearize.c | 45 +++++ linearize.h | 21 +- optimize.c | 6 +- ptrmap.c | 109 +++++++++++ ptrmap.h | 28 +++ sparse-llvm.c | 6 + ssa.c | 401 ++++++++++++++++++++++++++++++++++++++ ssa.h | 6 + sset.c | 28 +++ sset.h | 56 ++++++ symbol.h | 19 ++ validation/mem2reg/broken-phi02.c | 1 - validation/mem2reg/broken-phi03.c | 1 - validation/mem2reg/cond-expr5.c | 1 - validation/mem2reg/quadra00.c | 1 - validation/mem2reg/stray-phisrc.c | 1 - validation/mem2reg/undef00.c | 1 - validation/optim/cse-size.c | 3 +- validation/optim/missing-select.c | 1 - validation/var-undef-partial.c | 1 - 30 files changed, 1133 insertions(+), 315 deletions(-) create mode 100644 dominate.c create mode 100644 dominate.h create mode 100644 flowgraph.c create mode 100644 flowgraph.h create mode 100644 ptrmap.c create mode 100644 ptrmap.h create mode 100644 ssa.c create mode 100644 ssa.h create mode 100644 sset.c create mode 100644 sset.h -- To unsubscribe from this list: send the line "unsubscribe linux-sparse" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
