Intermodule constant propagation

Intermodule constant propagation

[Mircea Namolaru]

We would like to add several interprocedural optimizations to gcc, starting
with constant propagation.

We are thinking of implementing a flow insensitive form of the
interprocedural
constant propagation algorithm described in [1][2], based on the new
intermodule code (http://gcc.gnu.org/ml/gcc-patches/2003-05/msg01665.html).

We would appreciate any feedback regarding gcc interprocedural
optimizations
(work done or in development, potential problems etc).

[1]Callahan, D., Cooper, K.D., Kennedy, K., and Torczon, L. Interprocedural
constant propagation. ACM SIGPLAN Notices 1986, pp. 152-161.
[2]Grove, D.,and Torczon,L,Interprocedural Constant Propagation: A Study of
Jump Function Implementations. PLDI 1993, pp. 90-99.

Mircea

Re: Intermodule constant propagation

[Andrew Pinski]

On Nov 24, 2003, at 00:13, Mircea Namolaru wrote:
> We would like to add several interprocedural optimizations to gcc, 
> starting
> with constant propagation.
>
> We are thinking of implementing a flow insensitive form of the
> interprocedural
> constant propagation algorithm described in [1][2], based on the new
> intermodule code 
> (http://gcc.gnu.org/ml/gcc-patches/2003-05/msg01665.html).
>
> We would appreciate any feedback regarding gcc interprocedural
> optimizations
> (work done or in development, potential problems etc).


Jan Hubicka and I were just talking about this on IRC today.

Here is the ideas both Jan and I agreed on (for the tree-ssa branch):
Have a flag called -fwhole-prgram which tells GCC that the whole
program is being compiled at this point and have variables which
were global be static.

Have the code in callgraph (aka cgraph.c) do some of the work:
Have cgraph_analyze_function to collect the assigments and uses
of variables.

And have any changes to the functions happen in cgraph_expand_fuction.

The down side at this point is that the trees here are in generic and 
not
gimple but Jan is working on getting this problem solved.

I might have some work done by the end of the week on this front and 
basic
constant propagation IPA.

Thanks,
Andrew Pinski
pinskia@physics.uc.edu
pinskia@gcc.gnu.org
apinski@apple.com

Re: Intermodule constant propagation

[Jan Hubicka]

> On Nov 24, 2003, at 00:13, Mircea Namolaru wrote:
> >We would like to add several interprocedural optimizations to gcc, 
> >starting
> >with constant propagation.
> >
> >We are thinking of implementing a flow insensitive form of the
> >interprocedural
> >constant propagation algorithm described in [1][2], based on the new
> >intermodule code 
> >(http://gcc.gnu.org/ml/gcc-patches/2003-05/msg01665.html).
> >
> >We would appreciate any feedback regarding gcc interprocedural
> >optimizations
> >(work done or in development, potential problems etc).
> 
> 
> Jan Hubicka and I were just talking about this on IRC today.
> 
> Here is the ideas both Jan and I agreed on (for the tree-ssa branch):
> Have a flag called -fwhole-prgram which tells GCC that the whole
> program is being compiled at this point and have variables which
> were global be static.
Hi,
here is the patch I was experimenting with on whole program
optimizations.  It does not make the functions/variables to become
local, but it does make the optimizations to happen (it global functions
are elliminated, inlined once, changed calling conventions and so on).
This is not nice, so first I would like to see this solved before I will
consider applying this.

What are the opinions about this?  Shall cgraph code simply remove
PUBLIC flags or shall we maintain this information somewhere separately
so we don't confuse it with pretty well defined PUBLIC flag comming out
from front-end?

The patch is also just a start - it does not elliminate unused variables
and does not take any effort for backends to use this...

The program makes quite considerable difference on byte benchmark as
many of tests are simply optimized out :)
It would be nice to run it on SPEC, but I first need to figure out how
to hook our current intermodule code into SPEC build system...
Any hints here?

Honza

	* cgraphunit.c (decide_is_function_needed): Support flag_whole_program
	(cgraph_mark_local_functions): Do not check TREE_PUBLIC
	* common.opt (fwhole-program): New option.
	* flags.h (flag_whole_program): Declare.
	* opts.c (common_handle_option): Handle -fwhole-program
Index: common.opt
===================================================================
RCS file: /cvs/gcc/gcc/gcc/common.opt,v
retrieving revision 1.21
diff -c -3 -p -r1.21 common.opt
*** common.opt	21 Nov 2003 04:05:04 -0000	1.21
--- common.opt	24 Nov 2003 17:51:26 -0000
*************** fweb
*** 719,724 ****
--- 719,728 ----
  Common
  Construct webs and split unrelated uses of single variable
  
+ fwhole-program
+ Common
+ Perform whole program optimizations
+ 
  fwrapv
  Common
  Assume signed arithmetic overflow wraps around
Index: flags.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/flags.h,v
retrieving revision 1.126
diff -c -3 -p -r1.126 flags.h
*** flags.h	20 Oct 2003 21:46:33 -0000	1.126
--- flags.h	24 Nov 2003 17:51:29 -0000
*************** extern int flag_signaling_nans;
*** 717,722 ****
--- 717,725 ----
  
  extern int flag_unit_at_a_time;
  
+ /* Perform whole program optimizations.  */
+ extern int flag_whole_program;
+ 
  extern int flag_web;
  
  /* Nonzero means that we defer emitting functions until they are actually
Index: opts.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/opts.c,v
retrieving revision 1.46
diff -c -3 -p -r1.46 opts.c
*** opts.c	21 Nov 2003 04:05:05 -0000	1.46
--- opts.c	24 Nov 2003 17:52:10 -0000
*************** common_handle_option (size_t scode, cons
*** 1404,1409 ****
--- 1404,1413 ----
      case OPT_fweb:
        flag_web = value;
        break;
+ 
+     case OPT_fwhole_program:
+       flag_whole_program = value;
+       break;
        
      case OPT_fwrapv:
        flag_wrapv = value;
Index: doc/invoke.texi
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doc/invoke.texi,v
retrieving revision 1.364
diff -c -3 -p -r1.364 invoke.texi
*** doc/invoke.texi	21 Nov 2003 11:42:58 -0000	1.364
--- doc/invoke.texi	24 Nov 2003 17:53:22 -0000
*************** in the following sections.
*** 295,301 ****
  -fstrength-reduce  -fstrict-aliasing  -ftracer  -fthread-jumps @gol
  -funroll-all-loops  -funroll-loops  -fpeel-loops @gol
  -funswitch-loops  -fold-unroll-loops  -fold-unroll-all-loops @gol
! --param @var{name}=@var{value}
  -O  -O0  -O1  -O2  -O3  -Os}
  
  @item Preprocessor Options
--- 295,301 ----
  -fstrength-reduce  -fstrict-aliasing  -ftracer  -fthread-jumps @gol
  -funroll-all-loops  -funroll-loops  -fpeel-loops @gol
  -funswitch-loops  -fold-unroll-loops  -fold-unroll-all-loops @gol
! -fwhole-program --param @var{name}=@var{value}
  -O  -O0  -O1  -O2  -O3  -Os}
  
  @item Preprocessor Options
*************** better job.
*** 4587,4592 ****
--- 4587,4599 ----
  Parse the whole compilation unit before starting to produce code.
  This allows some extra optimizations to take place but consumes more
  memory.
+ 
+ @item -fwhole-program
+ @opindex fwhole-program
+ Assume that the whole program is exposed in the current compialation unit.
+ All public symbols defined by program with exception of function main and those
+ marged by attribute @code{used} are assumed to be local and may be altered by
+ compiler.
  
  @item -funroll-loops
  @opindex funroll-loops
Index: cgraphunit.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cgraphunit.c,v
retrieving revision 1.39
diff -c -3 -p -r1.39 cgraphunit.c
*** cgraphunit.c	21 Nov 2003 06:52:22 -0000	1.39
--- cgraphunit.c	24 Nov 2003 17:57:52 -0000
*************** decide_is_function_needed (struct cgraph
*** 79,85 ****
  
    /* Externally visible functions must be output.  The exception is
       COMDAT functions that must be output only when they are needed.  */
!   if (TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))
      return true;
  
    /* Constructors and destructors are reachable from the runtime by
--- 79,88 ----
  
    /* Externally visible functions must be output.  The exception is
       COMDAT functions that must be output only when they are needed.  */
!   if ((TREE_PUBLIC (decl) && !flag_whole_program)
!       && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))
!     return true;
!   if (MAIN_NAME_P (DECL_NAME (decl)))
      return true;
  
    /* Constructors and destructors are reachable from the runtime by
*************** cgraph_mark_local_functions (void)
*** 1338,1346 ****
    /* Figure out functions we want to assemble.  */
    for (node = cgraph_nodes; node; node = node->next)
      {
!       node->local.local = (!node->needed
! 		           && DECL_SAVED_TREE (node->decl)
! 		           && !TREE_PUBLIC (node->decl));
        if (cgraph_dump_file && node->local.local)
  	fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
      }
--- 1341,1348 ----
    /* Figure out functions we want to assemble.  */
    for (node = cgraph_nodes; node; node = node->next)
      {
!       node->local.local = (!node->needed && DECL_SAVED_TREE (node->decl)
! 			   && !DECL_COMDAT (node->decl))
        if (cgraph_dump_file && node->local.local)
  	fprintf (cgraph_dump_file, " %s", cgraph_node_name (node));
      }

Re: Intermodule constant propagation

[Dan Nicolaescu]

Jan Hubicka <hubicka@ucw.cz> writes:

  > It would be nice to run it on SPEC, but I first need to figure out how
  > to hook our current intermodule code into SPEC build system...
  > Any hints here?

I think you just need to add 
ONESTEP = 1
line to your SPEC .cfg file  and the compiler will be called with all
the source files  on the command line. 

Re: Intermodule constant propagation

[Andrew Pinski]

On Nov 24, 2003, at 11:13, Dan Nicolaescu wrote:

> Jan Hubicka <hubicka@ucw.cz> writes:
>
>> It would be nice to run it on SPEC, but I first need to figure out how
>> to hook our current intermodule code into SPEC build system...
>> Any hints here?
>
> I think you just need to add
> ONESTEP = 1
> line to your SPEC .cfg file  and the compiler will be called with all
> the source files  on the command line.


That does not work (at this point), see PR 13087.

Thanks,
Andrew Pinski

Re: Intermodule constant propagation

[Geoff Keating]

Andrew Pinski <pinskia@physics.uc.edu> writes:

> On Nov 24, 2003, at 11:13, Dan Nicolaescu wrote:
> 
> > Jan Hubicka <hubicka@ucw.cz> writes:
> >
> >> It would be nice to run it on SPEC, but I first need to figure out how
> >> to hook our current intermodule code into SPEC build system...
> >> Any hints here?
> >
> > I think you just need to add
> > ONESTEP = 1
> > line to your SPEC .cfg file  and the compiler will be called with all
> > the source files  on the command line.
> 
> 
> That does not work (at this point), see PR 13087.

If anyone wants to work on this (it's mostly a question of taking a
patch to gcc.c from Apple's compiler, porting it to FSF GCC, and
tidying it up), I can point them at the appropriate code...

-- 
- Geoffrey Keating <geoffk@geoffk.org>

Re: Intermodule constant propagation

[Andrew Pinski]

On Nov 24, 2003, at 13:52, Geoff Keating wrote:
> If anyone wants to work on this (it's mostly a question of taking a
> patch to gcc.c from Apple's compiler, porting it to FSF GCC, and
> tidying it up), I can point them at the appropriate code...


I will do it, just point me to where.


Thanks,
Andrew Pinski

Re: Intermodule constant propagation

[Andrew Pinski]

On Nov 24, 2003, at 13:52, Geoff Keating wrote:
> If anyone wants to work on this (it's mostly a question of taking a
> patch to gcc.c from Apple's compiler, porting it to FSF GCC, and
> tidying it up), I can point them at the appropriate code...


I will do it, just point me to where.


Thanks,
Andrew Pinski

Re: Intermodule constant propagation

[Jan Hubicka]

> On Nov 24, 2003, at 13:52, Geoff Keating wrote:
> >If anyone wants to work on this (it's mostly a question of taking a
> >patch to gcc.c from Apple's compiler, porting it to FSF GCC, and
> >tidying it up), I can point them at the appropriate code...
> 
> 
> I will do it, just point me to where.
Please let me know once you do have something.
I would like to consider reducing inline limits somewhat again the
current setting of 500 has been intentionally set a bit up as I wanted
to see responses from people complaining about too little/too much
inlining.  It looks like no one is complailing about too little inlining
and Gerald's testcase would always benefiting from setting it bit less.
Also SPEC performance has suffered somewhat from this change on Athlons
with relatively small cache, so it seems to me that 250 would be good
value.  It may be very nice to benchmark it on SPECs with intermodule
inlining so we see more.
Given that the mainline is in stage3 I think I should do more tests
soon.

Honza
> 
> 
> Thanks,
> Andrew Pinski

Re: Intermodule constant propagation

[Geoff Keating]

> From: Andrew Pinski <pinskia@physics.uc.edu>
> Date: Mon, 24 Nov 2003 15:17:58 -0800

> On Nov 24, 2003, at 13:52, Geoff Keating wrote:
> > If anyone wants to work on this (it's mostly a question of taking a
> > patch to gcc.c from Apple's compiler, porting it to FSF GCC, and
> > tidying it up), I can point them at the appropriate code...
> 
> 
> I will do it, just point me to where.

It's more-or-less these changes to Apple's tree available at
cvs -d :pserver:anonymous@anoncvs.opensource.apple.com:/cvs/root \
  co gcc3/gcc/gcc.c
with this entry in .cvspass:
:pserver:anonymous@anoncvs.opensource.apple.com:/cvs/root Ay=0=a%0bZ

----------------------------
revision 1.164.2.12.2.8
date: 2003/07/16 22:34:23;  author: ctice;  state: Exp;  lines: +158
-50
Radar 3289013.  Fix spec-branch driver to deal properly with compiling
multiple
source files at once:  end restrictions of extensions for extra link
files;
allow mixing of different language source files on command line; only
attempt
to compile multiple files at once for C or objective-C; make
-save-temps flag
work properly with this stuff.

Approved by Mike Stump.
----------------------------
revision 1.164.2.12.2.5
date: 2003/06/15 18:48:21;  author: ctice;  state: Exp;  lines: +16
-12
Fix driver problem so that IMI link files fix is only applied when
multiple sour
ce
files are passed to driver.

Approved by Dale Johannesen
----------------------------
revision 1.164.2.12.2.4
date: 2003/06/14 22:32:24;  author: ctice;  state: Exp;  lines: +37 -6
This addresses the problem (introduced with IMI) of the driver
attempting to han
d
the link files to the compiler along with the source files; now it
sends the lin
k
files to the linker instead.  It addresses radars 3176533 and 3289013.

Approved by Geoff, Dale, & Stuart (in some combination).
----------------------------
revision 1.164.2.12.2.1
date: 2003/05/20 19:17:14;  author: gkeating;  state: Exp;  lines: +52
-8
Inter-Module Inlining.
Bug #: 3197786
Reviewed by: dale
----------------------------

I think there might be a few bugs left, but it basically works,
certainly it works well enough for spec.  What it's supposed to do is:

- 'gcc foo.c bar.c -o foo' takes the two .c files, builds a single .s
  file, sends that to the assembler and the resulting .o to the
  linker.
- 'gcc -save-temps foo.c bar.c -o foo' turns each .c file into a .i
  file, producing foo.i and bar.i, then builds a single .s file from them.
- 'gcc foo.c bar.c -S' produces two .s files, foo.s and bar.s.
- likewise, 'gcc foo.c bar.c -c' produces two .o files.
- 'gcc foo.c bar.c -S -o result.s' produces one .s file.
- likewise, 'gcc foo.c bar.c -c -o result.o' produces one .o file
- 'gcc foo.c bar.c -E' is an error, just like now (I hope)
- 'gcc foo.c bar.c -E -o result.i' is an error, just like now

Note that none of this has anything to do with optimisation levels.  It's
done because more error checking is possible when the compiler can see
multiple source files at a time; this fixes the age-old problem of
'how can I check that my prototypes are consistent between source
files', and the brand-new problem of 'my program built fine when I
didn't use intermodule inlining, but the compiler complained when I
switched it on, and my build takes 8 hours and 3G of RAM at -O3,
please help!'

- This happens for objc files too.  the behaviour with C++ files is
  not changed, since we don't have IMA for C++ yet.  (One day we will,
  but it's a much-different implementation, because C++ has the One
  Definition Rule.)

-- 
- Geoffrey Keating <geoffk@geoffk.org>

Re: Intermodule constant propagation

[Andrew Pinski]

On Nov 25, 2003, at 13:29, Geoff Keating wrote:

> I think there might be a few bugs left, but it basically works,
> certainly it works well enough for spec.  What it's supposed to do is:
>
> - 'gcc foo.c bar.c -o foo' takes the two .c files, builds a single .s
>   file, sends that to the assembler and the resulting .o to the
>   linker.
> - 'gcc -save-temps foo.c bar.c -o foo' turns each .c file into a .i
>   file, producing foo.i and bar.i, then builds a single .s file from 
> them.
> - 'gcc foo.c bar.c -S' produces two .s files, foo.s and bar.s.
> - likewise, 'gcc foo.c bar.c -c' produces two .o files.
> - 'gcc foo.c bar.c -S -o result.s' produces one .s file.
> - likewise, 'gcc foo.c bar.c -c -o result.o' produces one .o file


The two without -o were not working in Apple's compiler so I fixed 
those and
I will post a patch for this tomorrow after it gets tested.

Also Apple's compiler does not error out if you supply two different 
languages
on the command line so I fixed that also.

This one is not an error right now and has not been ever (at least 
since 2.95.3)
and outputs to the stdout:
> - 'gcc foo.c bar.c -E' is an error, just like now (I hope)

This one has not be either, it always picked the last one for 
preprocessing:
> - 'gcc foo.c bar.c -E -o result.i' is an error, just like now

Should we change them into errors anyway?


Thanks,
Andrew Pinski

Re: Intermodule constant propagation

[Geoff Keating]

Andrew Pinski <pinskia@physics.uc.edu> writes:

> This one is not an error right now and has not been ever (at least
> since 2.95.3)
> and outputs to the stdout:
> > - 'gcc foo.c bar.c -E' is an error, just like now (I hope)
> 
> This one has not be either, it always picked the last one for
> preprocessing:
> > - 'gcc foo.c bar.c -E -o result.i' is an error, just like now
> 
> Should we change them into errors anyway?

Yes, I think they should be errors, especially the second one.

-- 
- Geoffrey Keating <geoffk@geoffk.org>

Re: Intermodule constant propagation

[Mircea Namolaru]

Good. So I understand that whole-program analysis and optimizations
can be developed in gcc based on -fwhole-program. My plans are to
implement interprocedural (whole program) constant propagation using
a context insensitive approach. I want to apply this to the stage
where the call-graph is available, prior to (and possibly guiding)
inlining; right now (gcc3.4) it seems best to work at the generic
tree level (where the call-graph is available), but maybe it's better
to work on gimple in tree-ssa branch?

Mircea

Re: Intermodule constant propagation

[Diego Novillo]

On Mon, 2003-12-08 at 10:16, Mircea Namolaru wrote:

> but maybe it's better to work on gimple in tree-ssa branch?
> 
That would be my recommendation.


Diego.