Optimize generated AST

[soywiz]

Haxe generated code is a simple machine state while + switch which is not as fast as it should be. In order to generate small and optimized code, we should transform the control flow graph into plain haxe structures: if, for, while...

Relevant concepts and links:

CFG=Control Flow Graph
DFS=Depth First
Dominator
DT=Dominator Tree
DFS and DT are acyclic graphs
We can normalize DFS adding an extra node and all exit points branching to that node
Reductible CFG=

https://en.wikipedia.org/wiki/Control_flow_graph
https://en.wikipedia.org/wiki/Data-flow_analysis
https://en.wikipedia.org/wiki/Depth-first_search
https://en.wikipedia.org/wiki/Directed_acyclic_graph
https://en.wikipedia.org/wiki/Dominator_(graph_theory)
http://infolab.stanford.edu/~ullman/dragon/w06/lectures/dfa3.pdf
http://www.cs.rice.edu/~keith/Embed/dom.pdf
http://pages.cs.wisc.edu/~fischer/cs701.f08/lectures/Lecture19.4up.pdf
http://compilers.cs.uni-saarland.de/ssasem/talks/Dibyendu.Das.pdf
http://dragonbook.stanford.edu/lecture-notes/Columbia-COMS-W4117/07-09-27.html
Relooper: https://github.com/kripken/emscripten/blob/master/docs/paper.pdf?raw=true

[soywiz]

Interesting post, with DFG, register allocation stuff and optimizations:
https://webkit.org/blog/5852/introducing-the-b3-jit-compiler/

[soywiz]

SSA without dominators: http://compilers.cs.uni-saarland.de/papers/bbhlmz13cc.pdf

[soywiz]

Transform irreductible cfgs
Handling Irreducible Loops: Optimized Node Splitting vs. DJ-Graphs
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.470.3729&rep=rep1&type=pdf

Loops:
http://www.cs.colostate.edu/~mstrout/CS553Fall07/Slides/lecture15-control.pdf
https://www.cs.utexas.edu/~pingali/CS375/2010Sp/lectures/LoopOptimizations.pdf

A loop is a strong component in the cfg digraph. Multiple entry points means that there are gotos (it is irreductible). Dominators can help to determine irreductibility.
Normal "continue, break" produce reductible cfgs.

[soywiz]

Already implemented this in previous commit: https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm

Initial strategy for "relooping":

Irreductible cfgs will use the current implementation (state machine) with while + switch for the moment which should be just a few functions await/async transformations or other languages.

• Decompose CFG into a graph of strong components (recursively)
• Loops are strong components with one single entrypoint/incoming edge from other strong component (several incoming edges would mean an irreductible CFG)
• Conditionals (ifs, switch): a node in the strong component graph that has two or more edges that eventually converge.

[soywiz]

Split in two tasks: #77 and #78