This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[rtlopt,hammer] update of comments in bb-reorder.c
- From: Josef Zlomek <zlomj9am at artax dot karlin dot mff dot cuni dot cz>
- To: gcc-patches at gcc dot gnu dot org
- Date: Sun, 15 Dec 2002 18:24:13 +0100
- Subject: [rtlopt,hammer] update of comments in bb-reorder.c
Hi!
This patch updates comments in bb-reorder.c and fixes coding style.
I'm commiting it as obvious to rtlopt and hammer-3_3 branch.
Josef
Sun Dec 15 18:22:59 CET 2002 Josef Zlomek <zlomj9am@artax.karlin.mff.cuni.cz>
* bb-reorder.c: Update comments, fix coding style.
Index: bb-reorder.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/bb-reorder.c,v
retrieving revision 1.50.2.15
diff -c -3 -p -r1.50.2.15 bb-reorder.c
*** bb-reorder.c 11 Dec 2002 16:42:40 -0000 1.50.2.15
--- bb-reorder.c 15 Dec 2002 17:19:51 -0000
***************
*** 37,46 ****
successors and successors that have been added to this trace.
The other successors (that has not been "sent" to the next round) will be
other seeds for this round and the secondary traces will start in them.
! If the successor has been visited in this trace the algorithm rotates
! the loop if it is profitable, and terminates the construction of the trace;
! otherwise it is added to the trace (however, there is some heuristic for
! simple branches).
When connecting traces it first checks whether there is an edge from the
last block of one trace to the first block of another trace.
--- 37,51 ----
successors and successors that have been added to this trace.
The other successors (that has not been "sent" to the next round) will be
other seeds for this round and the secondary traces will start in them.
! If the successor has not been visited in this trace it is added to the trace
! (however, there is some heuristic for simple branches).
! If the successor has been visited in this trace the loop has been found.
! If the loop has many iterations the loop is rotated so that the
! source block of the most probable edge going out from the loop
! is the last block of the trace.
! If the loop has few iterations and there is no edge from the last block of
! the loop going out from loop the loop header is duplicated.
! Finally, the construction of the trace is terminated.
When connecting traces it first checks whether there is an edge from the
last block of one trace to the first block of another trace.
***************
*** 55,61 ****
References:
"Software Trace Cache"
! Ramirez, Larriba-Pey, Navarro, Torrellas and Valero; 1999
http://citeseer.nj.nec.com/15361.html
*/
--- 60,66 ----
References:
"Software Trace Cache"
! A. Ramirez, J. Larriba-Pey, C. Navarro, J. Torrellas and M. Valero; 1999
http://citeseer.nj.nec.com/15361.html
*/
***************
*** 78,90 ****
/* The number of rounds. */
#define N_ROUNDS 4
! /* Branch thresholds in thousandths (per milles) of the REG_BR_PROB_BASE. */
static int branch_threshold[N_ROUNDS] = {400, 200, 100, 0};
! /* Exec thresholds in thousandths (per milles) of the frequency of bb 0. */
static int exec_threshold[N_ROUNDS] = {500, 200, 50, 0};
! /* If edge frequency is lower than DUPLICATION_THRESHOLD per milles of entry
block the edge destination is not duplicated while connecting traces. */
#define DUPLICATION_THRESHOLD 100
--- 83,95 ----
/* The number of rounds. */
#define N_ROUNDS 4
! /* Branch thresholds in thousandths (per mille) of the REG_BR_PROB_BASE. */
static int branch_threshold[N_ROUNDS] = {400, 200, 100, 0};
! /* Exec thresholds in thousandths (per mille) of the frequency of bb 0. */
static int exec_threshold[N_ROUNDS] = {500, 200, 50, 0};
! /* If edge frequency is lower than DUPLICATION_THRESHOLD per mille of entry
block the edge destination is not duplicated while connecting traces. */
#define DUPLICATION_THRESHOLD 100
*************** static fibnode_t *bb_node;
*** 110,115 ****
--- 115,121 ----
#define FREE(P) \
do { if (P) { free (P); P = 0; } else { abort (); } } while (0)
+ /* Structure for holding information about a trace. */
struct trace
{
/* First and last basic block of the trace. */
*************** find_traces (n_traces, traces)
*** 196,201 ****
--- 202,208 ----
count_threshold = max_entry_count * exec_threshold[i] / 1000;
else
count_threshold = max_entry_count / 1000 * exec_threshold[i];
+
find_traces_1_round (REG_BR_PROB_BASE * branch_threshold[i] / 1000,
max_entry_frequency * exec_threshold[i] / 1000,
count_threshold, traces, n_traces, i, &heap);
*************** find_traces (n_traces, traces)
*** 219,226 ****
}
}
! /* Rotate loop in the tail of trace (with sequential number TRACE) beginning in
! basic block BB. */
static basic_block
rotate_loop (back_edge, trace, trace_n)
--- 226,233 ----
}
}
! /* Rotate loop whose back edge is BACK_EDGE in the tail of trace TRACE
! (with sequential number TRACE_N). */
static basic_block
rotate_loop (back_edge, trace, trace_n)
*************** mark_bb_visited (bb, trace)
*** 345,351 ****
COUNT_TH). It stores the new traces into TRACES and modifies the number of
traces *N_TRACES. Sets the round (which the trace belongs to) to ROUND. It
expects that starting basic blocks are in *HEAP and at the end it deletes
! *HEAP and stores starting points for the next round into *HEAP. */
static void
find_traces_1_round (branch_th, exec_th, count_th, traces, n_traces, round,
--- 352,358 ----
COUNT_TH). It stores the new traces into TRACES and modifies the number of
traces *N_TRACES. Sets the round (which the trace belongs to) to ROUND. It
expects that starting basic blocks are in *HEAP and at the end it deletes
! *HEAP and stores starting points for the next round into new *HEAP. */
static void
find_traces_1_round (branch_th, exec_th, count_th, traces, n_traces, round,
*************** find_traces_1_round (branch_th, exec_th,
*** 376,383 ****
if (rtl_dump_file)
fprintf (rtl_dump_file, "Getting bb %d\n", bb->index);
- if (RBI (bb)->visited)
- abort (); /* For debugging purposes. */
/* If the BB's frequency is too low send BB to the next round. */
if (bb->frequency < exec_th || bb->count < count_th
--- 383,388 ----
*************** find_traces_1_round (branch_th, exec_th,
*** 421,426 ****
--- 426,432 ----
{
if (e->flags & EDGE_FAKE)
abort ();
+
if (e->dest == EXIT_BLOCK_PTR)
continue;
*************** find_traces_1_round (branch_th, exec_th,
*** 445,451 ****
}
}
! /* Add all nonselected successors to the heaps. */
for (e = bb->succ; e; e = e->succ_next)
{
if (e == best_edge
--- 451,457 ----
}
}
! /* Add all non-selected successors to the heaps. */
for (e = bb->succ; e; e = e->succ_next)
{
if (e == best_edge
*************** find_traces_1_round (branch_th, exec_th,
*** 478,484 ****
prob = e->probability;
freq = EDGE_FREQUENCY (e);
! if (!(e->flags & EDGE_CAN_FALLTHRU) || (e->flags & EDGE_COMPLEX)
|| prob < branch_th || freq < exec_th
|| e->count < count_th)
{
--- 484,491 ----
prob = e->probability;
freq = EDGE_FREQUENCY (e);
! if (!(e->flags & EDGE_CAN_FALLTHRU)
! || (e->flags & EDGE_COMPLEX)
|| prob < branch_th || freq < exec_th
|| e->count < count_th)
{
*************** find_traces_1_round (branch_th, exec_th,
*** 500,506 ****
}
}
! if (best_edge) /* Found suitable successor. */
{
if (RBI (best_edge->dest)->visited == *n_traces)
{
--- 507,513 ----
}
}
! if (best_edge) /* Suitable successor was found. */
{
if (RBI (best_edge->dest)->visited == *n_traces)
{
*************** find_traces_1_round (branch_th, exec_th,
*** 518,524 ****
{
if (rtl_dump_file)
{
! fprintf (rtl_dump_file, "Rotating loop %d - %d\n",
best_edge->dest->index, bb->index);
}
RBI (bb)->next = best_edge->dest;
--- 525,532 ----
{
if (rtl_dump_file)
{
! fprintf (rtl_dump_file,
! "Rotating loop %d - %d\n",
best_edge->dest->index, bb->index);
}
RBI (bb)->next = best_edge->dest;
*************** find_traces_1_round (branch_th, exec_th,
*** 602,609 ****
end_of_trace[trace->last->index] = *n_traces - 1;
/* The trace is terminated so we have to recount the keys in heap
! (some block can have a lower key because now one of its predecessors is
! an end of trace. */
for (e = bb->succ; e; e = e->succ_next)
{
if (e->dest == EXIT_BLOCK_PTR
--- 610,617 ----
end_of_trace[trace->last->index] = *n_traces - 1;
/* The trace is terminated so we have to recount the keys in heap
! (some block can have a lower key because now one of its predecessors
! is an end of the trace). */
for (e = bb->succ; e; e = e->succ_next)
{
if (e->dest == EXIT_BLOCK_PTR
*************** find_traces_1_round (branch_th, exec_th,
*** 636,642 ****
}
/* Create a duplicate of the basic block OLD_BB and redirect edge E to it, add
! it to trace after BB, mark OLD_BB visited and update pass' datastructures
(TRACE is a number of trace which OLD_BB is duplicated to). */
static basic_block
--- 644,650 ----
}
/* Create a duplicate of the basic block OLD_BB and redirect edge E to it, add
! it to trace after BB, mark OLD_BB visited and update pass' data structures
(TRACE is a number of trace which OLD_BB is duplicated to). */
static basic_block
*************** bb_to_key (bb)
*** 708,716 ****
--- 716,726 ----
int priority = 2;
+ /* Do not start in probably never executed blocks. */
if (probably_never_executed_bb_p (bb))
return BB_FREQ_MAX;
+ /* Decrease the priority if there is an unvisited predecessor. */
for (e = bb->pred; e; e = e->pred_next)
if (!(e->flags & EDGE_DFS_BACK) && !RBI (e->src)->visited)
{
*************** bb_to_key (bb)
*** 718,723 ****
--- 728,735 ----
break;
}
+ /* Increase the priority if there is a predecessor which is an end of some
+ trace. */
for (e = bb->pred; e; e = e->pred_next)
{
int index = e->src->index;
*************** bb_to_key (bb)
*** 728,735 ****
}
}
- /* All edges from predecessors of BB are DFS back edges or the predecessors
- of BB are visited. I want such basic blocks first. */
return -100 * BB_FREQ_MAX * priority - bb->frequency;
}
--- 740,745 ----
*************** connect_traces (n_traces, traces)
*** 920,926 ****
|| (e2->probability
== best2->probability
&& traces[end_of_trace[di]].length
! > best2_len))))
{
best = e;
best2 = e2;
--- 930,936 ----
|| (e2->probability
== best2->probability
&& traces[end_of_trace[di]].length
! > best2_len))))
{
best = e;
best2 = e2;
*************** copy_bb_p (bb)
*** 1036,1042 ****
return false;
}
! /* Return the maximum length of unconditional jump. */
static int
get_uncond_jump_length ()
--- 1046,1052 ----
return false;
}
! /* Return the maximum length of unconditional jump instruction. */
static int
get_uncond_jump_length ()