[cfg-branch] Software Trace Cache
Josef Zlomek
zlomj9am@artax.karlin.mff.cuni.cz
Tue Nov 13 15:03:00 GMT 2001
Hi,
I'm sending the Software Trace Cache. It does not duplicate basic blocks yet.
Josef Zlomek
2001-11-20 Josef Zlomek <zlomek@matfyz.cz>
* bb-reorder.c: Software Trace Cache
* cfglayout.h: Extended struct reorder_block_def
--- gcc-old/gcc/bb-reorder.c Mon Nov 12 16:44:47 2001
+++ gcc-new/gcc/bb-reorder.c Tue Nov 20 22:45:57 2001
@@ -89,10 +89,27 @@
#include "flags.h"
#include "output.h"
#include "cfglayout.h"
+#include "fibheap.h"
+
+struct trace {
+ /* First and last basic block of the trace. */
+ basic_block first, last;
+
+ /* The number of the pass of STC creation. */
+ int group_no;
+
+ /* Maximum frequency of basic blocks contained in the trace. */
+ int max_freq;
+};
/* Local function prototypes. */
static void make_reorder_chain PARAMS ((void));
static basic_block make_reorder_chain_1 PARAMS ((basic_block, basic_block));
+
+static edge find_best_succesor PARAMS ((basic_block, int, int));
+static edge find_best_predecesor PARAMS ((basic_block, int, int));
+static void find_traces PARAMS ((void));
+static int find_group_of_traces PARAMS ((int, int, struct trace *, int *, int, fibheap_t));
/* Compute an ordering for a subgraph beginning with block BB. Record the
ordering in RBI()->index and chained through RBI()->next. */
@@ -252,6 +269,247 @@ make_reorder_chain_1 (bb, prev)
return prev;
}
+#define FREQUENCY_TO_KEY(freq) ((BB_FREQ_MAX)-(freq))
+
+/* Compare the two traces by the MAX_FREQ element. */
+static int
+compare_traces (const void *a, const void *b)
+{
+ struct trace *t1 = (struct trace *) a;
+ struct trace *t2 = (struct trace *) b;
+
+ /* Compare the maximum frequency of the basic blocks in the traces. */
+ /* The traces will be sorted in descending order of frequency. */
+ return t2->max_freq - t1->max_freq;
+}
+
+/* Find best non-visited successor. */
+static edge
+find_best_succesor (bb, branch_th, exec_th)
+ basic_block bb;
+ int branch_th;
+ int exec_th;
+{
+ edge e, best_edge = NULL;
+ int max_prob = -1;
+
+ for (e = bb->succ; e; e = e->succ_next)
+ {
+ /* Exit, already visited, improbable or infrequent successor. */
+ if (e->dest == EXIT_BLOCK_PTR || RBI (e->dest)->visited
+ || e->probability < branch_th || e->dest->frequency < exec_th)
+ continue;
+
+ if (e->probability > max_prob
+ || (e->probability == max_prob
+ && e->dest->frequency > best_edge->dest->frequency))
+ {
+ /* Found better successor. */
+ best_edge = e;
+ max_prob = e->probability;
+ }
+ }
+ return best_edge;
+}
+
+/* Find best non-visited predecessor. */
+static edge
+find_best_predecesor (bb, branch_th, exec_th)
+ basic_block bb;
+ int branch_th;
+ int exec_th;
+{
+ edge e, best_edge = NULL;
+ int max_prob = -1;
+
+ for (e = bb->pred; e; e = e->pred_next)
+ {
+ /* Entry, already visited, improbable or infrequent predecessor. */
+ if (e->src == ENTRY_BLOCK_PTR || RBI (e->src)->visited
+ || e->probability < branch_th || e->src->frequency < exec_th)
+ continue;
+
+ if (e->probability > max_prob
+ || (e->probability == max_prob
+ && e->src->frequency > best_edge->src->frequency))
+ {
+ /* Found better predecessor. */
+ best_edge = e;
+ max_prob = e->probability;
+ }
+
+ }
+ return best_edge;
+}
+
+/* Finds a group of traces for BRANCH_TH and EXEC_TH. It gets the basic
+ blocks from the HEAP and stores the new traces into TRACES and modifies the
+ number of traces *N_TRACES. Sets the group (which the trace belongs to) to
+ GROUP_NO. Returns the number of basic blocks added into traces. */
+static int
+find_group_of_traces (branch_th, exec_th, traces, n_traces, group_no, heap)
+ int branch_th;
+ int exec_th;
+ struct trace *traces;
+ int *n_traces;
+ int group_no;
+ fibheap_t heap;
+{
+ int added = 0;
+
+ while (!fibheap_empty (heap))
+ {
+ basic_block bb = fibheap_min (heap);
+ edge e;
+ struct trace *trace;
+
+ if (bb->frequency < exec_th )
+ return added;
+
+ fibheap_extract_min (heap);
+
+ trace = traces + *n_traces;
+ trace->first = bb;
+ trace->last = bb;
+ trace->group_no = group_no;
+ trace->max_freq = bb->frequency;
+ (*n_traces)++;
+ RBI (bb)->visited = 1;
+ added++;
+
+ if (rtl_dump_file)
+ fprintf (rtl_dump_file, "Starting with BB %d\n", bb->index);
+
+ /* Grow the trace forwards. */
+ while ((e = find_best_succesor (bb, branch_th, exec_th)) != NULL )
+ {
+ basic_block bb2 = e->dest;
+ RBI (bb)->next = bb2;
+ RBI (bb2)->visited = 1;
+ trace->last = bb2;
+ fibheap_delete_node (heap, RBI (bb2)->node);
+ added++;
+ bb = bb2;
+
+ if (rtl_dump_file)
+ fprintf (rtl_dump_file, " forward: BB %d\n", bb->index);
+ }
+
+ /* Grow the trace backwards. */
+ bb = trace->first;
+ while ((e = find_best_predecesor (bb, branch_th, exec_th)) != NULL )
+ {
+ basic_block bb2 = e->src;
+ RBI (bb2)->next = bb;
+ RBI (bb2)->visited = 1;
+ trace->first = bb2;
+ fibheap_delete_node (heap, RBI (bb2)->node);
+ added++;
+ bb = bb2;
+
+ if (rtl_dump_file)
+ fprintf (rtl_dump_file, " backward: BB %d\n", bb->index);
+ }
+
+ }
+ return added;
+}
+
+/* Find the traces for Software Trace Cache. */
+static void
+find_traces ()
+{
+ int branch_threshold[] = {400, 200, 100, 50, 0};
+ int exec_threshold[] = {100, 20, 5, 1, 0};
+ int n_threshold = sizeof (branch_threshold) / sizeof (int);
+ int n_visited;
+ int old_n_basic_blocks;
+ int i;
+ basic_block bb;
+ int n_traces;
+ struct trace *traces;
+ fibheap_t heap;
+
+ /* There will be at most N_BASIC_BLOCKS traces. */
+ traces = xmalloc (n_basic_blocks * sizeof(struct trace));
+ n_traces = 0;
+ heap = fibheap_new();
+
+ /* Insert all basic blocks into heap. */
+ for (i = 0; i < n_basic_blocks; i++)
+ {
+ bb = BASIC_BLOCK (i);
+ RBI (bb)->node = fibheap_insert (heap, FREQUENCY_TO_KEY (bb->frequency), bb);
+ }
+
+ /* Find the traces. */
+ old_n_basic_blocks = n_basic_blocks;
+ n_visited = 0;
+ for (i = 0; i < n_threshold && n_visited < old_n_basic_blocks; i++)
+ {
+ n_visited +=
+ find_group_of_traces (branch_threshold[i] * REG_BR_PROB_BASE / 1000,
+ exec_threshold[i] * BB_FREQ_MAX / 1000,
+ traces, &n_traces, i, heap);
+ }
+ fibheap_delete (heap);
+
+ if (rtl_dump_file)
+ {
+ for (i = 0; i < n_traces; i++)
+ {
+ fprintf(rtl_dump_file, "Trace %d (group %d): ", i, traces[i].group_no);
+ for (bb = traces[i].first; bb != traces[i].last; bb = RBI (bb)->next)
+ fprintf(rtl_dump_file, "%d [%d] ", bb->index, bb->frequency);
+ fprintf(rtl_dump_file, "%d [%d]\n", bb->index, bb->frequency);
+ }
+ fflush (rtl_dump_file);
+ }
+
+ /* The trace containing the bb 0 has to be first. */
+ for (i = 1; i < n_traces; i++)
+ if (traces[i].first->index == 0)
+ {
+ struct trace t;
+ t = traces[i];
+ traces[i] = traces[0];
+ traces[0] = t;
+ }
+
+ if (rtl_dump_file)
+ {
+ for (i = 0; i < n_traces; i++)
+ {
+ fprintf(rtl_dump_file, "Trace %d (group %d): ", i, traces[i].group_no);
+ for (bb = traces[i].first; bb != traces[i].last; bb = RBI (bb)->next)
+ fprintf(rtl_dump_file, "%d [%d] ", bb->index, bb->frequency);
+ fprintf(rtl_dump_file, "%d [%d]\n", bb->index, bb->frequency);
+ }
+ fflush (rtl_dump_file);
+ }
+
+ /* Sort the traces by the maximum frequency. */
+ qsort (traces + 1, n_traces - 1, sizeof(struct trace), compare_traces);
+
+ if (rtl_dump_file)
+ {
+ for (i = 0; i < n_traces; i++)
+ {
+ fprintf(rtl_dump_file, "Trace %d (group %d): ", i, traces[i].group_no);
+ for (bb = traces[i].first; bb != traces[i].last; bb = RBI (bb)->next)
+ fprintf(rtl_dump_file, "%d [%d] ", bb->index, bb->frequency);
+ fprintf(rtl_dump_file, "%d [%d]\n", bb->index, bb->frequency);
+ }
+ fflush (rtl_dump_file);
+ }
+
+ /* Connect traces. */
+ for (i = 1; i < n_traces; i++)
+ RBI (traces[i - 1].last)->next = traces[i].first;
+
+ free (traces);
+}
+
/* Reorder basic blocks. The main entry point to this file. */
void
@@ -261,8 +519,7 @@ reorder_basic_blocks ()
return;
cfg_layout_initialize ();
-
- make_reorder_chain ();
+ find_traces ();
if (rtl_dump_file)
dump_flow_info (rtl_dump_file);
--- gcc-old/gcc/cfglayout.h Mon Nov 12 17:14:11 2001
+++ gcc-new/gcc/cfglayout.h Tue Nov 20 21:06:02 2001
@@ -18,6 +18,8 @@
Software Foundation, 59 Temple Place - Suite 330, Boston, MA
02111-1307, USA. */
+#include "fibheap.h"
+
struct scope_def;
typedef struct scope_def *scope;
@@ -29,6 +31,8 @@ typedef struct reorder_block_def
scope scope;
basic_block next;
int visited;
+ int trace_group;
+ fibnode_t node;
} *reorder_block_def;
#define RBI(BB) ((reorder_block_def) (BB)->aux)
More information about the Gcc-patches
mailing list