Control-Flow Analysis and Optimization
- Avoiding Unconditional Jumps by Code Replication
This is a new code optimization technique which can be employed in the
back-end of an optimizing compiler. It reduces the number of
unconditional jumps considerably by replacing it with a sequence of
basic blocks starting at the branch destination. The method handles
both unconditional branches in loops (which are handled be current
optimizing compilers) and any other unconditional transfer
(if-then-else, switch, goto, etc.) in a uniform fashion. For further
information, see
- Avoiding Conditional Branches by Code Replication
This new code optimization technique reduces the number of conditional
branches considerably by discovering branch corellations due to data
dependencies. Depending on the direction of a previous branch, the
direction of a later branch may be know. Separate control flow paths
are generated for such depdendent branches by code
replication. Furthermore, the replicated code is carefully rearranged
to avoid unconditional jumps. The resulting code exhibits fewer
executions of conditional branches. For more information, see
- Handling Irreducible Loops
Most loops in programs have a single entry point. But sometimes, goto
statements as well as advanced optimizations strategies result in
multiple-entry loops resulting in irreducible code.
We develop a novel analysis technique to detect irreducible loops,
which gives a sound definition of loops in programs, combining both
reducible (natural) and irreducible loops in one paradigm.
Irreducible loops often prevent certain loop optimizations to be
performed in optimizing compiler. We then present an algorithm to
transform irreducible loops into reducible ones. Our contribution is a
reduction in the amount of duplicated code due to node splitting in
comparison to previously published techiniques. For more information,
see
This line of research is being continued with novel research
directions in projects
CAREER and SPARTA.