From 44f498639c0cdfd08c184f834ebae07b8dc51831 Mon Sep 17 00:00:00 2001 From: Jan Hubicka Date: Sat, 23 Jun 2001 01:19:22 +0200 Subject: [PATCH] predict.c (block_info_def): Add nvisited. * predict.c (block_info_def): Add nvisited. (propagate_freq): Count nvisited; re-queue delayed blocks; handle irreducible regions. * flow.c (dump_edge_info): Dump the probability of edge. (combine_predictions_for_insn): Dump the basic block. From-SVN: r43522 --- gcc/ChangeLog | 9 +++++++++ gcc/flow.c | 3 +++ gcc/predict.c | 39 +++++++++++++++++++++++++++++++++++++-- 3 files changed, 49 insertions(+), 2 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 2f80724e815..48cffe46405 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,12 @@ +Sat Jun 23 01:16:42 CEST 2001 Jan Hubicka + + * predict.c (block_info_def): Add nvisited. + (propagate_freq): Count nvisited; re-queue delayed blocks; handle + irreducible regions. + + * flow.c (dump_edge_info): Dump the probability of edge. + (combine_predictions_for_insn): Dump the basic block. + 2001-06-22 Joseph S. Myers * doc/gcc.texi: Update documentation of source files of C diff --git a/gcc/flow.c b/gcc/flow.c index 2d7ee8047d9..5c0c6d72ad4 100644 --- a/gcc/flow.c +++ b/gcc/flow.c @@ -6405,6 +6405,9 @@ dump_edge_info (file, e, do_succ) else fprintf (file, " %d", side->index); + if (e->probability) + fprintf (file, " [%.1f%%] ", e->probability * 100.0 / REG_BR_PROB_BASE); + if (e->count) { fprintf (file, " count:"); diff --git a/gcc/predict.c b/gcc/predict.c index 4b29e592093..2bf13b3c537 100644 --- a/gcc/predict.c +++ b/gcc/predict.c @@ -215,7 +215,8 @@ combine_predictions_for_insn (insn, bb) int best_predictor = END_PREDICTORS; if (rtl_dump_file) - fprintf (rtl_dump_file, "Predictions for insn %i\n", INSN_UID (insn)); + fprintf (rtl_dump_file, "Predictions for insn %i bb %i\n", INSN_UID (insn), + bb->index); /* We implement "first match" heuristics and use probability guessed by predictor with smallest index. In future we will use better @@ -541,6 +542,10 @@ typedef struct block_info_def /* True if block already converted. */ int visited:1; + + /* Number of block proceeded before adding basic block to the queue. Used + to recognize irregular regions. */ + int nvisited; } *block_info; /* Similar information for edges. */ @@ -567,6 +572,7 @@ propagate_freq (head) basic_block last = bb; edge e; basic_block nextbb; + int nvisited = 0; BLOCK_INFO (head)->frequency = 1; for (; bb; bb = nextbb) @@ -581,12 +587,39 @@ propagate_freq (head) { for (e = bb->pred; e; e = e->pred_next) if (!BLOCK_INFO (e->src)->visited && !EDGE_INFO (e)->back_edge) + break; + + /* We didn't proceeded all predecesors of edge e yet. These may + be waiting in the queue or we may hit irreducible region. + + To avoid infinite looping on irrecudible regions, count number + of block proceeded at the time basic block has been queued. In the + case number didn't changed, we've hit irreducible region and we + forget the backward edge. This can increase time complexity + by the number of irreducible blocks, but in same way standard the + loop does, so it should not result in noticeable slowodwn. + + Alternativly we may distinquish backward and cross edges in the + DFS tree by preprocesing pass and ignore existence of non-loop + backward edges. */ + if (e && BLOCK_INFO (bb)->nvisited != nvisited) + { + if (!nextbb) + nextbb = e->dest; + else + BLOCK_INFO (last)->next = e->dest; + BLOCK_INFO (last)->nvisited = nvisited; + last = e->dest; continue; + } + else if (e && rtl_dump_file) + fprintf (rtl_dump_file, "Irreducible region hit, ignoring edge to bb %i\n", + bb->index); for (e = bb->pred; e; e = e->pred_next) if (EDGE_INFO (e)->back_edge) cyclic_probability += EDGE_INFO (e)->back_edge_prob; - else + else if (BLOCK_INFO (e->src)->visited) frequency += (e->probability * BLOCK_INFO (e->src)->frequency / REG_BR_PROB_BASE); @@ -616,8 +649,10 @@ propagate_freq (head) nextbb = e->dest; else BLOCK_INFO (last)->next = e->dest; + BLOCK_INFO (last)->nvisited = nvisited; last = e->dest; } + nvisited ++; } } -- 2.30.2