Use scev to estimate number of iterations in profile
Jan Hubicka
jh@suse.cz
Mon Sep 13 17:34:00 GMT 2004
Hi,
this patch makes use of scev based number of iterations predictors to set
number of iterations for loops. To my surprise it does not make GCC slower in
measurable way at least on the GCC modules compilation test and compared to old
implementation it now predicts 3% of executed conditionals instead of 1%
and on the tree-profiling branch made about 0.8% improvements on SPEC scores.
Bootstrapped/regtested i686-pc-gnu-linux and I will commit it day or two unless
there will be some comments/complains
Honza
2004-09-12 Jan Hubicka <jh@suse.cz>
* Makefile.in (predict.o): Depend on tree-scalar-evolution.h
* predict.c: Include tree-scalar-evolution.h and cfgloop.h
(predict_loops): Use number_of_iterations_exit to predict
number of iterations on trees.
Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.1384
diff -c -3 -p -r1.1384 Makefile.in
*** Makefile.in 11 Sep 2004 04:22:14 -0000 1.1384
--- Makefile.in 13 Sep 2004 11:42:59 -0000
*************** sreal.o: sreal.c $(CONFIG_H) $(SYSTEM_H)
*** 2138,2144 ****
predict.o: predict.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) $(TREE_H) \
$(FLAGS_H) insn-config.h $(BASIC_BLOCK_H) $(REGS_H) hard-reg-set.h output.h toplev.h \
$(RECOG_H) function.h except.h $(EXPR_H) $(TM_P_H) $(PREDICT_H) sreal.h \
! $(PARAMS_H) $(TARGET_H) $(CFGLOOP_H) $(COVERAGE_H)
lists.o: lists.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) toplev.h $(RTL_H) $(GGC_H)
bb-reorder.o : bb-reorder.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
$(RTL_H) $(BASIC_BLOCK_H) $(FLAGS_H) $(TIMEVAR_H) output.h $(CFGLAYOUT_H) $(FIBHEAP_H) \
--- 2138,2144 ----
predict.o: predict.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) $(TREE_H) \
$(FLAGS_H) insn-config.h $(BASIC_BLOCK_H) $(REGS_H) hard-reg-set.h output.h toplev.h \
$(RECOG_H) function.h except.h $(EXPR_H) $(TM_P_H) $(PREDICT_H) sreal.h \
! $(PARAMS_H) $(TARGET_H) $(CFGLOOP_H) $(COVERAGE_H) tree-scalar-evolution.h
lists.o: lists.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) toplev.h $(RTL_H) $(GGC_H)
bb-reorder.o : bb-reorder.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
$(RTL_H) $(BASIC_BLOCK_H) $(FLAGS_H) $(TIMEVAR_H) output.h $(CFGLAYOUT_H) $(FIBHEAP_H) \
Index: predict.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/predict.c,v
retrieving revision 1.116
diff -c -3 -p -r1.116 predict.c
*** predict.c 10 Sep 2004 11:02:26 -0000 1.116
--- predict.c 13 Sep 2004 11:42:59 -0000
*************** Software Foundation, 59 Temple Place - S
*** 58,63 ****
--- 58,65 ----
#include "tree-dump.h"
#include "tree-pass.h"
#include "timevar.h"
+ #include "tree-scalar-evolution.h"
+ #include "cfgloop.h"
/* real constants: 0, 1, 1-1/REG_BR_PROB_BASE, REG_BR_PROB_BASE,
1/REG_BR_PROB_BASE, 0.5, BB_FREQ_MAX. */
*************** combine_predictions_for_bb (FILE *file,
*** 552,564 ****
}
/* Predict edge probabilities by exploiting loop structure.
! When SIMPLELOOPS is set, attempt to count number of iterations by analyzing
! RTL. */
static void
! predict_loops (struct loops *loops_info, bool simpleloops)
{
unsigned i;
/* Try to predict out blocks in a loop that are not part of a
natural loop. */
for (i = 1; i < loops_info->num; i++)
--- 554,572 ----
}
/* Predict edge probabilities by exploiting loop structure.
! When RTLSIMPLELOOPS is set, attempt to count number of iterations by analyzing
! RTL otherwise use tree based approach. */
static void
! predict_loops (struct loops *loops_info, bool rtlsimpleloops)
{
unsigned i;
+ if (!rtlsimpleloops)
+ {
+ scev_initialize (loops_info);
+ estimate_numbers_of_iterations (loops_info);
+ }
+
/* Try to predict out blocks in a loop that are not part of a
natural loop. */
for (i = 1; i < loops_info->num; i++)
*************** predict_loops (struct loops *loops_info,
*** 573,579 ****
flow_loop_scan (loop, LOOP_EXIT_EDGES);
exits = loop->num_exits;
! if (simpleloops)
{
iv_analysis_loop_init (loop);
find_simple_exit (loop, &desc);
--- 581,587 ----
flow_loop_scan (loop, LOOP_EXIT_EDGES);
exits = loop->num_exits;
! if (rtlsimpleloops)
{
iv_analysis_loop_init (loop);
find_simple_exit (loop, &desc);
*************** predict_loops (struct loops *loops_info,
*** 595,600 ****
--- 603,644 ----
prob);
}
}
+ else
+ {
+ edge *exits;
+ unsigned j, n_exits;
+ struct tree_niter_desc niter_desc;
+
+ exits = get_loop_exit_edges (loop, &n_exits);
+ for (j = 0; j < n_exits; j++)
+ {
+ tree niter = NULL;
+
+ if (number_of_iterations_exit (loop, exits[j], &niter_desc))
+ niter = niter_desc.niter;
+ if (!niter || TREE_CODE (niter_desc.niter) != INTEGER_CST)
+ niter = loop_niter_by_eval (loop, exits[j]);
+
+ if (TREE_CODE (niter) == INTEGER_CST)
+ {
+ int probability;
+ if (host_integerp (niter, 1)
+ && tree_int_cst_lt (niter,
+ build_int_cstu (NULL_TREE,
+ REG_BR_PROB_BASE - 1)))
+ {
+ HOST_WIDE_INT nitercst = tree_low_cst (niter, 1) + 1;
+ probability = (REG_BR_PROB_BASE + nitercst / 2) / nitercst;
+ }
+ else
+ probability = 1;
+
+ predict_edge (exits[j], PRED_LOOP_ITERATIONS, probability);
+ }
+ }
+
+ free (exits);
+ }
bbs = get_loop_body (loop);
*************** predict_loops (struct loops *loops_info,
*** 609,615 ****
statements construct loops via "non-loop" constructs
in the source language and are better to be handled
separately. */
! if ((simpleloops && !can_predict_insn_p (BB_END (bb)))
|| predicted_by_p (bb, PRED_CONTINUE))
continue;
--- 653,659 ----
statements construct loops via "non-loop" constructs
in the source language and are better to be handled
separately. */
! if ((rtlsimpleloops && !can_predict_insn_p (BB_END (bb)))
|| predicted_by_p (bb, PRED_CONTINUE))
continue;
*************** predict_loops (struct loops *loops_info,
*** 639,644 ****
--- 683,694 ----
/* Free basic blocks from get_loop_body. */
free (bbs);
}
+
+ if (!rtlsimpleloops)
+ {
+ free_numbers_of_iterations_estimates (loops_info);
+ scev_reset ();
+ }
}
/* Attempt to predict probabilities of BB outgoing edges using local
More information about the Gcc-patches
mailing list