[ast-optimizer-branch] Goto/Break/Continue/Switch elimination

[Roger Sayle]

One possible solution to the potential performance pitfalls is to
implement a "Break/Continue/Switch induction" pass.

This pass should hopefully transform SIMPLE back into a higher-level
structured control flow.  These techniques are normally used to improve
code readability in reverse engineering projects, for example making
the AST pretty printer output much easier to comprehend.  For GCC, it
would allow simplification of control flow for some optimizations,
whilst reducing the size of a program's representation for others.

>From a code generation perspective there are many reasons for keeping
a switch statement intact all the way to the backend, including to make
use of the hardware's "casei" and "tablejump" instructions.  The current
scheme already performs switch statement decomposition too early, i.e.
before the bounds have been modified by VRP.  Indeed, rather than
decompose switches to perfectly balanced binary trees, a backend should
skew the branches based upon the ratio of branch-taken/branch-not-taken
timings including prediction hints.  [The current scheme of using
sequential tests for switch statements with very few cases is really
just a special case of tree skewing!]

Much like SSA, the ability to transform the AST into SIMPLE to apply
certain transformations, and then convert it back would allow
investigations of which optimizations are best performed in which
representations.

See, for example, http://citeseer.nj.nec.com/cifuentes99recovery.html

Does such an approach sound reasonable/plausible?

Roger
--
Roger Sayle,                         E-mail: roger@eyesopen.com
OpenEye Scientific Software,         WWW: http://www.eyesopen.com/
Suite 1107, 3600 Cerrillos Road,     Tel: (+1) 505-473-7385
Santa Fe, New Mexico, 87507.         Fax: (+1) 505-473-0833