A visualization of GCC's passes, as a subway map

A visualization of GCC's passes, as a subway map

[David Malcolm]

For fun over the weekend I wrote a python script (using my
gcc-python-plugin[1]) to render an SVG diagram of GCC's optimization
passes (or, at least, based on my understanding of them).

This diagram shows the various GCC optimization passes, arranged
vertically, showing child passes via indentation.

The lifetime of the various properties that they maintain is shown,
giving the pass that initially creates the data (if any), the pass that
destroys it (if any), and each pass that requires a particular property
(based on the PROP_* flags).  I've attempted to make it look a little
like a subway train schematic map, where the properties are train lines,
and the passes are the stations they stop at; the initial/final passes
are the termini.

The resulting SVG can be seen at the top of:
http://readthedocs.org/docs/gcc-python-plugin/en/latest/tables-of-passes.html

Direct link to SVG, in case the above gets mangled on your browser:
http://readthedocs.org/docs/gcc-python-plugin/en/latest/_images/passes.svg
(550 x 3302 pixels; about 250k in size).

The script can be seen here (it uses pycairo to abstract the drawing
operations):
http://git.fedorahosted.org/git/?p=gcc-python-plugin.git;a=blob;f=generate-passes-svg.py

Hope this is fun/helpful (and that I'm correctly interpreting the data!)
Dave

[1] https://fedorahosted.org/gcc-python-plugin/

Re: A visualization of GCC's passes, as a subway map

[Mingjie Xing]

2011/7/12 David Malcolm <dmalcolm@redhat.com>:
> For fun over the weekend I wrote a python script (using my
> gcc-python-plugin[1]) to render an SVG diagram of GCC's optimization
> passes (or, at least, based on my understanding of them).
>
> This diagram shows the various GCC optimization passes, arranged
> vertically, showing child passes via indentation.

Interesting.  I also have a plugin
(http://code.google.com/p/gcc-vcg-plugin) which can be used to dump
the gcc pass lists in vcg format.

Cheers,
Mingjie

Re: A visualization of GCC's passes, as a subway map

[Paolo Bonzini]

On 07/11/2011 07:56 PM, David Malcolm wrote:
> Hope this is fun/helpful (and that I'm correctly interpreting the data!)

You are, and it shows some bugs even.  gimple_lcx is obviously destroyed 
by expand, and I find it unlikely that no pass ever introduces a 
critical edge...

Paolo

Re: A visualization of GCC's passes, as a subway map

[Paulo J. Matos]

On 12/07/11 08:22, Paolo Bonzini wrote:
> On 07/11/2011 07:56 PM, David Malcolm wrote:
>> Hope this is fun/helpful (and that I'm correctly interpreting the data!)
>
> You are, and it shows some bugs even. gimple_lcx is obviously destroyed
> by expand, and I find it unlikely that no pass ever introduces a
> critical edge...
>

But the diagram shows gimple_lcx stopping at expand but continuing its 
lifetime through RTL passes (so gimple_lcx according to the diagram is 
_not_ destroyed by expand). So, I am left wondering if the bug is in the 
diagram or GCC.

-- 
PMatos

Re: A visualization of GCC's passes, as a subway map

[Joel Sherrill]

On 07/12/2011 02:22 AM, Paolo Bonzini wrote:
> On 07/11/2011 07:56 PM, David Malcolm wrote:
>> Hope this is fun/helpful (and that I'm correctly interpreting the data!)
> You are, and it shows some bugs even.  gimple_lcx is obviously destroyed
> by expand, and I find it unlikely that no pass ever introduces a
> critical edge...
>
David deserves a pat on the back.  This is a nice way to
visualize this.  It is complicated and hard to grok otherwise.

This would be a great addition to gcc internals documentation.
Especially if you could click on each pass and get to a description.
> Paolo


-- 
Joel Sherrill, Ph.D.             Director of Research&  Development
joel.sherrill@OARcorp.com        On-Line Applications Research
Ask me about RTEMS: a free RTOS  Huntsville AL 35805
    Support Available             (256) 722-9985

Re: A visualization of GCC's passes, as a subway map

[Paolo Bonzini]

On 07/12/2011 10:43 AM, Paulo J. Matos wrote:
>>
>>> Hope this is fun/helpful (and that I'm correctly interpreting the data!)
>>
>> You are, and it shows some bugs even. gimple_lcx is obviously destroyed
>> by expand, and I find it unlikely that no pass ever introduces a
>> critical edge...
>>
>
> But the diagram shows gimple_lcx stopping at expand but continuing its
> lifetime through RTL passes (so gimple_lcx according to the diagram is
> _not_ destroyed by expand). So, I am left wondering if the bug is in the
> diagram or GCC.

It shows bugs in GCC's pass description, to be clear.

Paolo

Re: A visualization of GCC's passes, as a subway map

[Paulo J. Matos]

On 12/07/11 17:04, Paolo Bonzini wrote:
>
> It shows bugs in GCC's pass description, to be clear.
>
> Paolo
>

That makes sense.

-- 
PMatos

Re: A visualization of GCC's passes, as a subway map

[David Malcolm]

On Tue, 2011-07-12 at 09:43 +0100, Paulo J. Matos wrote:
> On 12/07/11 08:22, Paolo Bonzini wrote:
> > On 07/11/2011 07:56 PM, David Malcolm wrote:
> >> Hope this is fun/helpful (and that I'm correctly interpreting the data!)
> >
> > You are, and it shows some bugs even. gimple_lcx is obviously destroyed
> > by expand, and I find it unlikely that no pass ever introduces a
> > critical edge...
> >
> 
> But the diagram shows gimple_lcx stopping at expand but continuing its 
> lifetime through RTL passes (so gimple_lcx according to the diagram is 
> _not_ destroyed by expand). So, I am left wondering if the bug is in the 
> diagram or GCC.


On this build of GCC (standard Fedora 15 gcc package of 4.6.0), the
relevant part of cfgexpand.c looks like this:

struct rtl_opt_pass pass_expand =
{
 {
  RTL_PASS,
  "expand",				/* name */

[...snip...]

  PROP_ssa | PROP_gimple_leh | PROP_cfg
    | PROP_gimple_lcx,			/* properties_required */
  PROP_rtl,                             /* properties_provided */
  PROP_ssa | PROP_trees,		/* properties_destroyed */

[...snip...]

}

and gcc/tree-pass.h has:
  #define PROP_trees \
    (PROP_gimple_any | PROP_gimple_lcf | PROP_gimple_leh |  PROP_gimple_lomp)

and that matches up with both the diagram, and the entry for "expand" in
the table below [1].

So it seems that the diagram is correctly accessing the
"properties_destroyed" data for the "expand" pass; does PROP_gimple_lcx
need to be added somewhere?  (or should the diagram we taught to
specialcase some things, perhaps?)

Note that the diagram doesn't take the RTL_* enum into account.

FWIW, I added some more notes on passes here:
http://readthedocs.org/docs/gcc-python-plugin/en/latest/passes.html
which tries to summarize what the PROP_* flags mean (as I understand
them).

and there's a higher-level summary of GCC's insides (from the
perspective of a Python coder new to GCC) here:
http://readthedocs.org/docs/gcc-python-plugin/en/latest/gcc-overview.html

As before, caveat lector: I may have misunderstood things; I'm
relatively new to GCC.

Hope this is helpful
Dave
[1]
http://readthedocs.org/docs/gcc-python-plugin/en/latest/tables-of-passes.html#the-all-other-passes-catch-all

Re: A visualization of GCC's passes, as a subway map

[Xinliang David Li]

FYI. If you just want text dump of gcc passes and their on|off
settings, option -fdump-passes can be used. This can be enhanced to
dump properties and TODOs.

David

On Tue, Jul 12, 2011 at 9:07 AM, David Malcolm <dmalcolm@redhat.com> wrote:
> On Tue, 2011-07-12 at 09:43 +0100, Paulo J. Matos wrote:
>> On 12/07/11 08:22, Paolo Bonzini wrote:
>> > On 07/11/2011 07:56 PM, David Malcolm wrote:
>> >> Hope this is fun/helpful (and that I'm correctly interpreting the data!)
>> >
>> > You are, and it shows some bugs even. gimple_lcx is obviously destroyed
>> > by expand, and I find it unlikely that no pass ever introduces a
>> > critical edge...
>> >
>>
>> But the diagram shows gimple_lcx stopping at expand but continuing its
>> lifetime through RTL passes (so gimple_lcx according to the diagram is
>> _not_ destroyed by expand). So, I am left wondering if the bug is in the
>> diagram or GCC.
>
>
> On this build of GCC (standard Fedora 15 gcc package of 4.6.0), the
> relevant part of cfgexpand.c looks like this:
>
> struct rtl_opt_pass pass_expand =
> {
>  {
>  RTL_PASS,
>  "expand",                             /* name */
>
> [...snip...]
>
>  PROP_ssa | PROP_gimple_leh | PROP_cfg
>    | PROP_gimple_lcx,                  /* properties_required */
>  PROP_rtl,                             /* properties_provided */
>  PROP_ssa | PROP_trees,                /* properties_destroyed */
>
> [...snip...]
>
> }
>
> and gcc/tree-pass.h has:
>  #define PROP_trees \
>    (PROP_gimple_any | PROP_gimple_lcf | PROP_gimple_leh |  PROP_gimple_lomp)
>
> and that matches up with both the diagram, and the entry for "expand" in
> the table below [1].
>
> So it seems that the diagram is correctly accessing the
> "properties_destroyed" data for the "expand" pass; does PROP_gimple_lcx
> need to be added somewhere?  (or should the diagram we taught to
> specialcase some things, perhaps?)
>
> Note that the diagram doesn't take the RTL_* enum into account.
>
> FWIW, I added some more notes on passes here:
> http://readthedocs.org/docs/gcc-python-plugin/en/latest/passes.html
> which tries to summarize what the PROP_* flags mean (as I understand
> them).
>
> and there's a higher-level summary of GCC's insides (from the
> perspective of a Python coder new to GCC) here:
> http://readthedocs.org/docs/gcc-python-plugin/en/latest/gcc-overview.html
>
> As before, caveat lector: I may have misunderstood things; I'm
> relatively new to GCC.
>
> Hope this is helpful
> Dave
> [1]
> http://readthedocs.org/docs/gcc-python-plugin/en/latest/tables-of-passes.html#the-all-other-passes-catch-all
>
>
>

Re: A visualization of GCC's passes, as a subway map

[David Malcolm]

On Tue, 2011-07-12 at 11:43 +0800, Mingjie Xing wrote:
> 2011/7/12 David Malcolm <dmalcolm@redhat.com>:
> > For fun over the weekend I wrote a python script (using my
> > gcc-python-plugin[1]) to render an SVG diagram of GCC's optimization
> > passes (or, at least, based on my understanding of them).
> >
> > This diagram shows the various GCC optimization passes, arranged
> > vertically, showing child passes via indentation.
> 
> Interesting.  I also have a plugin
> (http://code.google.com/p/gcc-vcg-plugin) which can be used to dump
> the gcc pass lists in vcg format.

Thanks!  This looks useful; I'm getting rather tired of dealing with
graphviz's almost-HTML-but-not-quite format :(

FWIW, your plugin's page links to http://code.google.com/p/vcgviewer/
but that's currently giving me a 403 permissions error.  I don't know if
this is a bug at google's end or not.


Dave

Re: A visualization of GCC's passes, as a subway map

[David Malcolm]

On Tue, 2011-07-12 at 09:15 -0700, Xinliang David Li wrote:
> FYI. If you just want text dump of gcc passes and their on|off
> settings, option -fdump-passes can be used. This can be enhanced to
> dump properties and TODOs.

Thanks! 

I got a bit mystified by:

  $ gcc -fdump-passes test.c
  cc1: error: unrecognized command line option ‘-fdump-passes’

but it turns out I'm still stuck on 4.6.0 (though that's a restriction
I've imposed on myself), and that you added it in 4.7, if I'm reading
the history right:
http://gcc.gnu.org/viewcvs?view=revision&revision=174930

FWIW, the analagous python code I used to generate my tables of passes
is here:
http://git.fedorahosted.org/git/?p=gcc-python-plugin.git;a=blob;f=generate-tables-of-passes-rst.py

I don't know if it's sane in 4.6 to expose the "is_on" and
"is_really_on" booleans as (readonly) attributes of the Python gcc.Pass
objects; there seem to have been a lot of cleanups to that code in 4.7

[snip]

Dave

Re: A visualization of GCC's passes, as a subway map

[Xinliang David Li]

On Tue, Jul 12, 2011 at 10:55 AM, David Malcolm <dmalcolm@redhat.com> wrote:
> On Tue, 2011-07-12 at 09:15 -0700, Xinliang David Li wrote:
>> FYI. If you just want text dump of gcc passes and their on|off
>> settings, option -fdump-passes can be used. This can be enhanced to
>> dump properties and TODOs.
>
> Thanks!
>
> I got a bit mystified by:
>
>  $ gcc -fdump-passes test.c
>  cc1: error: unrecognized command line option ‘-fdump-passes’
>
> but it turns out I'm still stuck on 4.6.0 (though that's a restriction
> I've imposed on myself), and that you added it in 4.7, if I'm reading
> the history right:
> http://gcc.gnu.org/viewcvs?view=revision&revision=174930
>

Right, it is in trunk compiler only.


> FWIW, the analagous python code I used to generate my tables of passes
> is here:
> http://git.fedorahosted.org/git/?p=gcc-python-plugin.git;a=blob;f=generate-tables-of-passes-rst.py
>
> I don't know if it's sane in 4.6 to expose the "is_on" and
> "is_really_on" booleans as (readonly) attributes of the Python gcc.Pass
> objects; there seem to have been a lot of cleanups to that code in 4.7
>

Other related pass related infrastructure changes include

1) -fenable-xxx=<func_ranges>, -fdisable-xxx=<func_ranges> to disable
or enable any gcc passes
2) Removing IR/debug dump as a TODO.

David

> [snip]
>
> Dave
>
>

Re: A visualization of GCC's passes, as a subway map

[David Malcolm]

On Tue, 2011-07-12 at 08:34 -0500, Joel Sherrill wrote:
> On 07/12/2011 02:22 AM, Paolo Bonzini wrote:
> > On 07/11/2011 07:56 PM, David Malcolm wrote:
> >> Hope this is fun/helpful (and that I'm correctly interpreting the data!)
> > You are, and it shows some bugs even.  gimple_lcx is obviously destroyed
> > by expand, and I find it unlikely that no pass ever introduces a
> > critical edge...
> >
> David deserves a pat on the back.  This is a nice way to
> visualize this.  It is complicated and hard to grok otherwise.

Thanks!

> This would be a great addition to gcc internals documentation.
> Especially if you could click on each pass and get to a description.

This would be good.  However, looking at, say, 
http://gcc.gnu.org/onlinedocs/gccint/Tree-SSA-passes.html#Tree-SSA-passes
I don't see meaningful per-pass anchors there.  I'm not familiar with
gcc's documentation toolchain; is there a way to add the necessary
anchors to the generated HTML?

(I assume that that page and its sisters from
http://gcc.gnu.org/onlinedocs/gccint/Passes.html
are the canonical documentation on each pass).

(FWIW, currently all I have at the python end is the "name" field of the
plugin; I don't have the C identifier of the function that implements
the pass - though perhaps that could be scraped at plugin build time,
which would of course be ugly)

Dave

Re: A visualization of GCC's passes, as a subway map

[Tom Tromey]

>>>>> "David" == David Malcolm <dmalcolm@redhat.com> writes:

David> This would be good.  However, looking at, say, 
David> http://gcc.gnu.org/onlinedocs/gccint/Tree-SSA-passes.html#Tree-SSA-passes
David> I don't see meaningful per-pass anchors there.  I'm not familiar with
David> gcc's documentation toolchain; is there a way to add the necessary
David> anchors to the generated HTML?

Yes, you can use @anchor in Texinfo.

Tom

Re: A visualization of GCC's passes, as a subway map

[Paolo Bonzini]

On 07/12/2011 06:07 PM, David Malcolm wrote:
> On this build of GCC (standard Fedora 15 gcc package of 4.6.0), the
> relevant part of cfgexpand.c looks like this:
>
> struct rtl_opt_pass pass_expand =
> {
>   {
>    RTL_PASS,
>    "expand",				/* name */
>
> [...snip...]
>
>    PROP_ssa | PROP_gimple_leh | PROP_cfg
>      | PROP_gimple_lcx,			/* properties_required */
>    PROP_rtl,                             /* properties_provided */
>    PROP_ssa | PROP_trees,		/* properties_destroyed */
>
> [...snip...]
>
> }
>
> and gcc/tree-pass.h has:
>    #define PROP_trees \
>      (PROP_gimple_any | PROP_gimple_lcf | PROP_gimple_leh |  PROP_gimple_lomp)
>
> and that matches up with both the diagram, and the entry for "expand" in
> the table below [1].
>
> So it seems that the diagram is correctly accessing the
> "properties_destroyed" data for the "expand" pass; does PROP_gimple_lcx
> need to be added somewhere?  (or should the diagram we taught to
> specialcase some things, perhaps?)

Yes, PROP_gimple_lcx needs to be added to PROP_trees.  I cannot approve 
the patch, unfortunately.

Also, several passes are likely lacking PROP_crited in their 
properties_destroyed.  At least all those that can be followed by 
TODO_cleanup_cfg:

* pass_split_functions
* pass_call_cdcen
* pass_build_cfg
* pass_cleanup_eh
* pass_if_conversion
* pass_ipa_inline
* pass_early_inline
* pass_fixup_cfg
* pass_cse_sincos
* pass_predcom
* pass_lim
* pass_loop_prefetch
* pass_vectorize
* pass_iv_canon
* pass_tree_unswitch
* pass_vrp
* pass_sra_early
* pass_sra
* pass_early_ipa_sra
* pass_ccp
* pass_fold_builtins
* pass_copy_prop
* pass_dce
* pass_dce_loop
* pass_cd_dce
* pass_dominator
* pass_phi_only_cprop
* pass_forwprop
* pass_tree_ifcombine
* pass_scev_cprop
* pass_parallelize_loops
* pass_ch
* pass_cselim
* pass_pre
* pass_fre
* pass_tail_recursion
* pass_tail_calls

Paolo

Re: A visualization of GCC's passes, as a subway map

[Richard Guenther]

On Wed, Jul 13, 2011 at 11:49 AM, Paolo Bonzini <bonzini@gnu.org> wrote:
> On 07/12/2011 06:07 PM, David Malcolm wrote:
>>
>> On this build of GCC (standard Fedora 15 gcc package of 4.6.0), the
>> relevant part of cfgexpand.c looks like this:
>>
>> struct rtl_opt_pass pass_expand =
>> {
>>  {
>>   RTL_PASS,
>>   "expand",                            /* name */
>>
>> [...snip...]
>>
>>   PROP_ssa | PROP_gimple_leh | PROP_cfg
>>     | PROP_gimple_lcx,                 /* properties_required */
>>   PROP_rtl,                             /* properties_provided */
>>   PROP_ssa | PROP_trees,               /* properties_destroyed */
>>
>> [...snip...]
>>
>> }
>>
>> and gcc/tree-pass.h has:
>>   #define PROP_trees \
>>     (PROP_gimple_any | PROP_gimple_lcf | PROP_gimple_leh |
>>  PROP_gimple_lomp)
>>
>> and that matches up with both the diagram, and the entry for "expand" in
>> the table below [1].
>>
>> So it seems that the diagram is correctly accessing the
>> "properties_destroyed" data for the "expand" pass; does PROP_gimple_lcx
>> need to be added somewhere?  (or should the diagram we taught to
>> specialcase some things, perhaps?)
>
> Yes, PROP_gimple_lcx needs to be added to PROP_trees.  I cannot approve the
> patch, unfortunately.

Hm, why?  complex operations are lowered after a complex lowering pass
has executed.  they are still lowered on RTL, so I don't see why we need
to destroy them technically.

> Also, several passes are likely lacking PROP_crited in their
> properties_destroyed.  At least all those that can be followed by
> TODO_cleanup_cfg:

Yeah, well - most PROPerties are for informational purposes only right
now - things like critical edge splitting should possibly be automatically
managed by the pass manager via properties (likewise dominator info
for which we don't have a property right now).  Of course we'd like to
have a verifier for each property.

Richard.

> * pass_split_functions
> * pass_call_cdcen
> * pass_build_cfg
> * pass_cleanup_eh
> * pass_if_conversion
> * pass_ipa_inline
> * pass_early_inline
> * pass_fixup_cfg
> * pass_cse_sincos
> * pass_predcom
> * pass_lim
> * pass_loop_prefetch
> * pass_vectorize
> * pass_iv_canon
> * pass_tree_unswitch
> * pass_vrp
> * pass_sra_early
> * pass_sra
> * pass_early_ipa_sra
> * pass_ccp
> * pass_fold_builtins
> * pass_copy_prop
> * pass_dce
> * pass_dce_loop
> * pass_cd_dce
> * pass_dominator
> * pass_phi_only_cprop
> * pass_forwprop
> * pass_tree_ifcombine
> * pass_scev_cprop
> * pass_parallelize_loops
> * pass_ch
> * pass_cselim
> * pass_pre
> * pass_fre
> * pass_tail_recursion
> * pass_tail_calls
>
> Paolo
>

Re: A visualization of GCC's passes, as a subway map

[Paolo Bonzini]

On 07/13/2011 12:54 PM, Richard Guenther wrote:
> >  Yes, PROP_gimple_lcx needs to be added to PROP_trees.  I cannot approve the
> >  patch, unfortunately.
>
> Hm, why?  complex operations are lowered after a complex lowering pass
> has executed.  they are still lowered on RTL, so I don't see why we need
> to destroy them technically.

Because it's PROP_*gimple*_lcx. :)

Paolo

Re: A visualization of GCC's passes, as a subway map

[Richard Guenther]

On Wed, Jul 13, 2011 at 3:15 PM, Paolo Bonzini <bonzini@gnu.org> wrote:
> On 07/13/2011 12:54 PM, Richard Guenther wrote:
>>
>> >  Yes, PROP_gimple_lcx needs to be added to PROP_trees.  I cannot approve
>> > the
>> >  patch, unfortunately.
>>
>> Hm, why?  complex operations are lowered after a complex lowering pass
>> has executed.  they are still lowered on RTL, so I don't see why we need
>> to destroy them technically.
>
> Because it's PROP_*gimple*_lcx. :)

Shouldn't it then be PROP_*gimple* instead of PROP_*trees*? ;)

We should drop all PROP_trees after gimplification it seems ;)

Richard.

> Paolo
>

Re: A visualization of GCC's passes, as a subway map

[Paolo Bonzini]

On 07/14/2011 11:11 AM, Richard Guenther wrote:
>>> >>  Hm, why?  complex operations are lowered after a complex lowering pass
>>> >>  has executed.  they are still lowered on RTL, so I don't see why we need
>>> >>  to destroy them technically.
>> >
>> >  Because it's PROP_*gimple*_lcx.:)
> Shouldn't it then be PROP_*gimple*  instead of PROP_*trees*?;)

Heh, you have a point!

Paolo

Re: A visualization of GCC's passes, as a subway map

[Michael Matz]

Hi,

On Thu, 14 Jul 2011, Paolo Bonzini wrote:

> On 07/14/2011 11:11 AM, Richard Guenther wrote:
> > > > > >  Hm, why?  complex operations are lowered after a complex lowering
> > > > > >  pass
> > > > > >  has executed.  they are still lowered on RTL, so I don't see why we
> > > > > >  need
> > > > > >  to destroy them technically.
> > > >
> > > >  Because it's PROP_*gimple*_lcx.:)
> > Shouldn't it then be PROP_*gimple*  instead of PROP_*trees*?;)
> 
> Heh, you have a point!

I think until and unless we have verifiers for the properties, and 
automatic (re)setting them for at least the common ones, it's all just 
wasted work.  They don't provide any useful info whatsoever.  The only 
useful ones are: PROP_cfg, PROP_rtl, PROP_trees (for adjusting what is 
dumped, arguably possible to check differently) and PROP_ssa (for 
remove_unused_locals).  The rest is just snake oil.


Ciao,
Michael.