Re: [wwwdocs] Add page about CFG branch

[Jan Hubicka <jh at suse dot cz>]

> 
> Thanks Zack for the excellent review.  I've added most of your
> suggestions to the page.
> 
> Honza, could you please go over the appended page and tell me whether
> it is still correct - and whether I've incorporated Zack's suggestions
> in the right way?  Please also read again over Zack's comments, I'm
> sure there're some questions open.
> 
> Following Zack's suggestions, I've added also a section explaining the
> concepts/new optimizations  that you like to add.  I've started with
> filling in the Loop Peeling information:
> 
> ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
> <h2>Concepts</h2>
> 
> Some ideas that the cfg-branch will implement are known in the
> compiler research literature but are new concepts for GCC.  We'd like
> to explain the concepts briefly and point to the research literature.
> 
> <h3>Loop Peeling</h3>
> 
> <p> <em>Loop Peeling</em> is a form of loop unrolling where the
> <em>first</em> iterations from a loop are unrolled.  It removes
> <code>i</code> iterations from the beginning of a loop and adds
> <code>i</code>copies of the loop body directly before the loop head.
> </p>
> 
<h3>Tracer<h3>
<p> <em>Tracer</em> also known as <em>tail duplication</em> or <em>superblock
formation</em> pass identifies traces - commonly executed sequences of basic
blocks and duplicates the blocks in order to avoid side entrances to those
sequences - forming the so called superblocks.  The superblocks are easier
to optimize by conventional passes - such as CSE and scheduled.  In case no
extra optimizations apply, our crossjumping pass merges the code patch again
after register allocation.
<p>
We plan to do loop peeling and superblock formation in single pass as described
in [3].

<h3>Software Trace Cache</h3>
<p><em>Software Trace Cache</em> is basic block reordering algorithm allowing
to do code duplication at the progress.  While optimal code layout is NP
complette problem, allowing limited amount of duplication should elliminate the
common drawbacks of current algorithm and keep the code size under control.
See [6] for detailed description.
> 
<h3>Web Construction Pass</h3>
<p>This pass constructs webs as commonly used for register allocation purposes.
After that each web gets assigned individual pseudo.  This allows our register
allocation pass to operate on pseudos directly, but also strengthens several
other optimization passes, such as CSE, loop optimizer, trivial dead code
removal etc.
<p>
While future SSE pass will have same effect in the lowlevel RTL generation, we
still believe this pass to be usefull right before register allocation or after
code duplication passes, such as tracer or loop unroller that needs to unshare
temporaries.
> 
> I'm considering rearranging the text so that the optimizations and the
> status are together, e.g. like the following (this is just an example,
> I'm not sure whether this text is correct):
The rest looks OK for me.  Thanks a lot for caring this!

Honza