Re: [rtlopt] Value profiling and optimalizations

[Jan Hubicka <jh at suse dot cz>]

> Hello,
> 
> this patch adds the means to measure profiles of variables and use them
> for optimalizations. More concretely it gives you possibility to measure
>   * histogram of value inside some specified interval
>   * (untested) histogram of belonging to one of several ranges
>   * how often the value is a power of 2 (and what)
>   * whether the value is equal to a constant most of the time (and what)
> 
> The new vpt (Value Profile based Transformations) pass is added that
> uses the data to optimize the code. For now it just does elimination
> of divs and mods, but there are more simmilar transformations possible.
> 
> Zdenek
> 
> Changelog:
> 	* Makefile.in (vpt.o): New file.
> 	(toplev.o, profile.o): Add vpt.h dependecy.
> 	* vpt.h: New.
> 	* vpt.c: New.
> 	* combine.c (distribute_notes): Handle REG_VALUE_HISTOGRAM note.
> 	* flags.h (flag_value_histograms): Declare.
> 	* gcov-io.h (GCOV_TAG_VALUE_HISTOGRAMS): New.
> 	(struct function_info): Add n_value_histogram_counters field.
> 	(struct gcov_info): Add value_counts and n_value_counts fields.
> 	* libgcc2.c (gcov_exit, __gcov_flush): Write out value histograms.
> 	* profile.c: Include vpt.h.
> 	(struct function_list): Add value_counters field.
> 	(value_histograms_label): New.
> 	(gen_loop_profiler): Deleted.
> 	(gen_interval_profiler, gen_range_profiler, gen_pow2_profiler,
> 	gen_one_value_profiler): New.
> 	(get_histogram_counts, instrument_loops, compute_loop_histograms,
> 	init_branch_prob): Modified.
> 	(index_counts_file): Fix mistakes.
> 	(instrument_values, compute_value_histograms): New.
> 	(branch_prob): Call them.
> 	(create_profiler): Emit requiered structures.
> 	* profile.h (struct profile_info): Add count_value_counters,
> 	count_value_counters_now and have_value_histograms fields.
> 	* rtl.c (reg_note_name): Add REG_VALUE_HISTOGRAM.
> 	* rtl.h (enum reg_note): Ditto.
> 	* toplev.c: Include vpt.h.
> 	(enum dump_file_index, dump_file): Add vpt dump file.
> 	(flag_value_histograms, flag_value_profile_transformations): New.
> 	(lang_independent_options): Add them.
> 	(rest_of_compilation): Add vpt pass.
> 
> Index: Makefile.in
> ===================================================================
> RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
> retrieving revision 1.937.2.7
> diff -c -3 -p -r1.937.2.7 Makefile.in
> *** Makefile.in	16 Nov 2002 17:32:16 -0000	1.937.2.7
> --- Makefile.in	21 Nov 2002 19:38:32 -0000
> *************** OBJS = alias.o bb-reorder.o bitmap.o bui
> *** 755,762 ****
>    sbitmap.o sched-deps.o sched-ebb.o sched-rgn.o sched-vis.o sdbout.o	   \
>    sibcall.o simplify-rtx.o ssa.o ssa-ccp.o ssa-dce.o stmt.o		   \
>    stor-layout.o stringpool.o timevar.o toplev.o tracer.o tree.o tree-dump.o \
> !  tree-inline.o unroll.o varasm.o varray.o version.o vmsdbgout.o xcoffout.o \
> !  et-forest.o $(GGC) $(out_object_file) $(EXTRA_OBJS)
>   
>   BACKEND = main.o libbackend.a
>   
> --- 755,762 ----
>    sbitmap.o sched-deps.o sched-ebb.o sched-rgn.o sched-vis.o sdbout.o	   \
>    sibcall.o simplify-rtx.o ssa.o ssa-ccp.o ssa-dce.o stmt.o		   \
>    stor-layout.o stringpool.o timevar.o toplev.o tracer.o tree.o tree-dump.o \
> !  tree-inline.o unroll.o varasm.o varray.o version.o vmsdbgout.o vpt.o	   \
> !  xcoffout.o et-forest.o $(GGC) $(out_object_file) $(EXTRA_OBJS)
>   
>   BACKEND = main.o libbackend.a
>   
> *************** toplev.o : toplev.c $(CONFIG_H) $(SYSTEM
> *** 1391,1397 ****
>      debug.h insn-config.h intl.h $(RECOG_H) Makefile toplev.h \
>      dwarf2out.h sdbout.h dbxout.h $(EXPR_H) hard-reg-set.h $(BASIC_BLOCK_H) \
>      graph.h $(LOOP_H) except.h $(REGS_H) $(TIMEVAR_H) $(lang_options_files) \
> !    ssa.h $(PARAMS_H) $(TM_P_H) reload.h dwarf2asm.h $(TARGET_H) \
>      langhooks.h insn-flags.h options.h cfglayout.h gcse-globals.h real.h
>   	$(CC) $(ALL_CFLAGS) $(ALL_CPPFLAGS) $(INCLUDES) \
>   	  -DTARGET_NAME=\"$(target_alias)\" \
> --- 1391,1397 ----
>      debug.h insn-config.h intl.h $(RECOG_H) Makefile toplev.h \
>      dwarf2out.h sdbout.h dbxout.h $(EXPR_H) hard-reg-set.h $(BASIC_BLOCK_H) \
>      graph.h $(LOOP_H) except.h $(REGS_H) $(TIMEVAR_H) $(lang_options_files) \
> !    ssa.h $(PARAMS_H) $(TM_P_H) reload.h dwarf2asm.h $(TARGET_H) vpt.h \
>      langhooks.h insn-flags.h options.h cfglayout.h gcse-globals.h real.h
>   	$(CC) $(ALL_CFLAGS) $(ALL_CPPFLAGS) $(INCLUDES) \
>   	  -DTARGET_NAME=\"$(target_alias)\" \
> *************** profile.o : profile.c $(CONFIG_H) $(SYST
> *** 1549,1555 ****
>      insn-config.h output.h $(REGS_H) $(EXPR_H) function.h \
>      gcov-io.h gcov-iov.h toplev.h $(GGC_H) hard-reg-set.h $(BASIC_BLOCK_H) \
>      $(TARGET_H) langhooks.h profile.h libfuncs.h gt-profile.h cfgloop.h \
> !    params.h $(HASHTAB_H)
>   loop.o : loop.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) flags.h $(LOOP_H) \
>      insn-config.h $(REGS_H) hard-reg-set.h $(RECOG_H) $(EXPR_H) \
>      real.h $(PREDICT_H) $(BASIC_BLOCK_H) function.h \
> --- 1549,1557 ----
>      insn-config.h output.h $(REGS_H) $(EXPR_H) function.h \
>      gcov-io.h gcov-iov.h toplev.h $(GGC_H) hard-reg-set.h $(BASIC_BLOCK_H) \
>      $(TARGET_H) langhooks.h profile.h libfuncs.h gt-profile.h cfgloop.h \
> !    params.h $(HASHTAB_H) vpt.h
> ! vpt.o : vpt.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) $(BASIC_BLOCK_H) profile.h \
> !    hard-reg-set.h vpt.h $(EXPR_H) output.h
>   loop.o : loop.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) flags.h $(LOOP_H) \
>      insn-config.h $(REGS_H) hard-reg-set.h $(RECOG_H) $(EXPR_H) \
>      real.h $(PREDICT_H) $(BASIC_BLOCK_H) function.h \
> Index: combine.c
> ===================================================================
> RCS file: /cvs/gcc/gcc/gcc/combine.c,v
> retrieving revision 1.310.2.4
> diff -c -3 -p -r1.310.2.4 combine.c
> *** combine.c	16 Nov 2002 17:32:19 -0000	1.310.2.4
> --- combine.c	21 Nov 2002 19:38:32 -0000
> *************** distribute_notes (notes, from_insn, i3, 
> *** 12238,12243 ****
> --- 12238,12248 ----
>   	  place = i3;
>   	  break;
>   
> + 	case REG_VALUE_HISTOGRAM:
> + 	  /* Given that I don't understand what's going on here at all,
> + 	     just get rid of this.  */
> + 	  break;
Killing it here is definitly good idea.  We don't want to keep these
updated post register allocation anyway.
What the code does is to put notes to proper places when 3 instructions
has been combined into 2.
> Index: gcov-io.h
> ===================================================================
> RCS file: /cvs/gcc/gcc/gcc/gcov-io.h,v
> retrieving revision 1.16.6.2
> diff -c -3 -p -r1.16.6.2 gcov-io.h
> *** gcov-io.h	8 Nov 2002 20:47:11 -0000	1.16.6.2
> --- gcov-io.h	21 Nov 2002 19:38:33 -0000
> *************** typedef long long gcov_type;
> *** 176,181 ****
> --- 176,182 ----
>   #define GCOV_TAG_LINES		 ((unsigned)0x01450000)
>   #define GCOV_TAG_ARC_COUNTS  	 ((unsigned)0x01a10000)
>   #define GCOV_TAG_LOOP_HISTOGRAMS ((unsigned)0x01a30000)
> + #define GCOV_TAG_VALUE_HISTOGRAMS ((unsigned)0x01a50000)
What makes value histograms different from loop histograms for gcov?
It would perhaps make sense to comonize more of the loop and value
histograms code.

Otherwise the patch looks fine to me.  You forgot to include the vpt.c

Honza