This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[rtlopt] bb-reorder - copy loop header for loops that do not iterate much
- From: Josef Zlomek <zlomj9am at artax dot karlin dot mff dot cuni dot cz>
- To: gcc-patches at gcc dot gnu dot org
- Date: Thu, 5 Dec 2002 15:48:09 +0100
- Subject: [rtlopt] bb-reorder - copy loop header for loops that do not iterate much
Hi,
this patch duplicates loop header of loops that do not iterate much
(less than 4 iterations).
Bootstrapped i386.
Josef
Thu Dec 5 15:40:19 CET 2002 Josef Zlomek <zlomj9am@artax.karlin.mff.cuni.cz>
* bb-reorder.c (array_size): New variable.
(original_last_basic_block): Killed.
(FREE, GET_ARRAY_SIZE): New macro.
(find_traces_1_round): Copy loop header of few-iterating loop.
(copy_bb): Grow the arrays (end_of_trace etc.) when needed.
(connect_traces): Do not check the index since the array is large
enough.
(*): Use FREE, array_size instead of free, original_last_basic_block.
*** gcc-old/gcc/bb-reorder.c 2002-12-05 10:57:27.000000000 +0100
--- gcc-dup/gcc/bb-reorder.c 2002-12-05 15:05:25.000000000 +0100
*************** static int exec_threshold[N_ROUNDS] = {5
*** 89,96 ****
/* Length of unconditional jump instruction. */
static int uncond_jump_length;
! /* Original number (before duplications) of basic blocks. */
! static int original_last_basic_block;
/* Which trace is the bb start of (-1 means it is not a start of a trace). */
static int *start_of_trace;
--- 89,100 ----
/* Length of unconditional jump instruction. */
static int uncond_jump_length;
! /* The current size of the following dynamic arrays. */
! static int array_size;
!
! /* To avoid frequent reallocation the size of arrays is greater than needed,
! the number of elements is (not less than) 1.2 * size_wanted. */
! #define GET_ARRAY_SIZE(X) ((((X) / 5) + 1) * 6)
/* Which trace is the bb start of (-1 means it is not a start of a trace). */
static int *start_of_trace;
*************** static int *end_of_trace;
*** 100,105 ****
--- 104,113 ----
static fibheap_t *bb_heap;
static fibnode_t *bb_node;
+ /* Free the memory and set the pointer to NULL. */
+ #define FREE(P) \
+ do { if (P) { free (P); P = 0; } else { abort (); } } while (0)
+
struct trace
{
/* First and last basic block of the trace. */
*************** find_traces (n_traces, traces)
*** 145,161 ****
edge e;
fibheap_t heap;
- /* We need to remember the old number of basic blocks because
- while connecting traces, blocks can be copied and thus their
- index can be higher than the size of arrays. */
- original_last_basic_block = last_basic_block;
-
/* We need to know some information for each basic block. */
! start_of_trace = xmalloc (original_last_basic_block * sizeof (int));
! end_of_trace = xmalloc (original_last_basic_block * sizeof (int));
! bb_heap = xmalloc (original_last_basic_block * sizeof (fibheap_t));
! bb_node = xmalloc (original_last_basic_block * sizeof (fibnode_t));
! for (i = 0; i < original_last_basic_block; i++)
{
start_of_trace[i] = -1;
end_of_trace[i] = -1;
--- 153,165 ----
edge e;
fibheap_t heap;
/* We need to know some information for each basic block. */
! array_size = GET_ARRAY_SIZE (last_basic_block);
! start_of_trace = xmalloc (array_size * sizeof (int));
! end_of_trace = xmalloc (array_size * sizeof (int));
! bb_heap = xmalloc (array_size * sizeof (fibheap_t));
! bb_node = xmalloc (array_size * sizeof (fibnode_t));
! for (i = 0; i < array_size; i++)
{
start_of_trace[i] = -1;
end_of_trace[i] = -1;
*************** find_traces (n_traces, traces)
*** 195,202 ****
count_threshold, traces, n_traces, i, &heap);
}
fibheap_delete (heap);
! free (bb_node);
! free (bb_heap);
if (rtl_dump_file)
{
--- 199,206 ----
count_threshold, traces, n_traces, i, &heap);
}
fibheap_delete (heap);
! FREE (bb_node);
! FREE (bb_heap);
if (rtl_dump_file)
{
*************** find_traces_1_round (branch_th, exec_th,
*** 512,517 ****
--- 516,525 ----
RBI (bb)->next = best_edge->dest;
bb = rotate_loop (best_edge, trace, *n_traces);
}
+ else if (copy_bb_p (best_edge->dest))
+ {
+ bb = copy_bb (best_edge->dest, best_edge, bb, *n_traces);
+ }
/* Terminate the trace. */
break;
*************** find_traces_1_round (branch_th, exec_th,
*** 608,618 ****
(TRACE is a number of trace which OLD_BB is duplicated to). */
static basic_block
! copy_bb (old_bb, e, bb, n_traces)
basic_block old_bb;
edge e;
basic_block bb;
! int n_traces;
{
basic_block new_bb;
--- 616,626 ----
(TRACE is a number of trace which OLD_BB is duplicated to). */
static basic_block
! copy_bb (old_bb, e, bb, trace)
basic_block old_bb;
edge e;
basic_block bb;
! int trace;
{
basic_block new_bb;
*************** copy_bb (old_bb, e, bb, n_traces)
*** 625,633 ****
fprintf (rtl_dump_file,
"Duplicated bb %d (created bb %d)\n",
old_bb->index, new_bb->index);
! RBI (new_bb)->visited = n_traces;
RBI (bb)->next = new_bb;
return new_bb;
}
--- 633,676 ----
fprintf (rtl_dump_file,
"Duplicated bb %d (created bb %d)\n",
old_bb->index, new_bb->index);
! RBI (new_bb)->visited = trace;
RBI (bb)->next = new_bb;
+ if (new_bb->index >= array_size || last_basic_block > array_size)
+ {
+ int i;
+ int new_size;
+
+ new_size = MAX (last_basic_block, new_bb->index + 1);
+ new_size = GET_ARRAY_SIZE (new_size);
+
+ start_of_trace = xrealloc (start_of_trace, new_size * sizeof (int));
+ end_of_trace = xrealloc (end_of_trace, new_size * sizeof (int));
+ for (i = array_size; i < new_size; i++)
+ {
+ start_of_trace[i] = -1;
+ end_of_trace[i] = -1;
+ }
+ if (bb_heap)
+ {
+ bb_heap = xrealloc (bb_heap, new_size * sizeof (fibheap_t));
+ bb_node = xrealloc (bb_node, new_size * sizeof (fibnode_t));
+ for (i = array_size; i < new_size; i++)
+ {
+ bb_heap[i] = NULL;
+ bb_node[i] = NULL;
+ }
+ }
+ array_size = new_size;
+
+ if (rtl_dump_file)
+ {
+ fprintf (rtl_dump_file,
+ "Growing the dynamic arrays to %d elements.\n",
+ array_size);
+ }
+ }
+
return new_bb;
}
*************** connect_traces (n_traces, traces)
*** 759,765 ****
if (e->src != ENTRY_BLOCK_PTR
&& (e->flags & EDGE_CAN_FALLTHRU)
&& !(e->flags & EDGE_COMPLEX)
- && si < original_last_basic_block
&& end_of_trace[si] >= 0
&& !connected[end_of_trace[si]]
&& (!best
--- 802,807 ----
*************** connect_traces (n_traces, traces)
*** 803,809 ****
if (e->dest != EXIT_BLOCK_PTR
&& (e->flags & EDGE_CAN_FALLTHRU)
&& !(e->flags & EDGE_COMPLEX)
- && di < original_last_basic_block
&& start_of_trace[di] >= 0
&& !connected[start_of_trace[di]]
&& (!best
--- 845,850 ----
*************** connect_traces (n_traces, traces)
*** 846,852 ****
if (e2->dest == EXIT_BLOCK_PTR
|| ((e2->flags & EDGE_CAN_FALLTHRU)
- && di < original_last_basic_block
&& start_of_trace[di] >= 0
&& !connected[start_of_trace[di]]
&& (EDGE_FREQUENCY (e2) >= freq_threshold)
--- 887,892 ----
*************** connect_traces (n_traces, traces)
*** 927,935 ****
fflush (rtl_dump_file);
}
! free (connected);
! free (end_of_trace);
! free (start_of_trace);
}
/* Return true when BB can and should be copied. */
--- 967,975 ----
fflush (rtl_dump_file);
}
! FREE (connected);
! FREE (end_of_trace);
! FREE (start_of_trace);
}
/* Return true when BB can and should be copied. */
*************** reorder_basic_blocks ()
*** 1014,1020 ****
n_traces = 0;
find_traces (&n_traces, traces);
connect_traces (n_traces, traces);
! free (traces);
if (rtl_dump_file)
dump_flow_info (rtl_dump_file);
--- 1054,1060 ----
n_traces = 0;
find_traces (&n_traces, traces);
connect_traces (n_traces, traces);
! FREE (traces);
if (rtl_dump_file)
dump_flow_info (rtl_dump_file);