Re: [cfg-branch]: Software Trace Cache

[Josef Zlomek <zlomj9am at artax dot karlin dot mff dot cuni dot cz>]

Hi,

I'm sending again the Software Trace Cache. It now finds traces "exactly" like described in http://citeseer.nj.nec.com/15361.html

I have also added dependency on fibheap.h for tracer.c which was forgotten.


2001-11-21  Josef Zlomek  <zlomek@matfyz.cz>

	* bb-reorder.c: Code for Software Trace Cache
	* Makefile.in: bb-reorder.c and tracer.c depend on fibheap.h


--- gcc-old/gcc/Makefile.in	Wed Nov 21 17:19:26 2001
+++ gcc-new/gcc/Makefile.in	Wed Nov 21 17:26:40 2001
@@ -1588,9 +1588,9 @@ predict.o: predict.c $(CONFIG_H) $(SYSTE
    $(RECOG_H) function.h except.h $(EXPR_H) $(TM_P_H) $(PREDICT_H)
 lists.o: lists.c $(CONFIG_H) $(SYSTEM_H) toplev.h $(RTL_H) $(GGC_H)
 bb-reorder.o : bb-reorder.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) $(TREE_H) flags.h \
-   $(BASIC_BLOCK_H) hard-reg-set.h output.h cfglayout.h
+   $(BASIC_BLOCK_H) hard-reg-set.h output.h cfglayout.h $(FIBHEAP_H)
 tracer.o : tracer.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) $(TREE_H) \
-   $(BASIC_BLOCK_H) hard-reg-set.h output.h cfglayout.h flags.h
+   $(BASIC_BLOCK_H) hard-reg-set.h output.h cfglayout.h flags.h $(FIBHEAP_H)
 cfglayout.o : cfglayout.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) $(TREE_H) \
    insn-config.h $(BASIC_BLOCK_H) hard-reg-set.h output.h function.h \
    cfglayout.h
--- gcc-old/gcc/bb-reorder.c	Wed Nov 21 17:19:26 2001
+++ gcc-new/gcc/bb-reorder.c	Wed Nov 21 21:39:43 2001
@@ -89,10 +89,23 @@
 #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;
+};
 
 /* Local function prototypes.  */
 static void make_reorder_chain		PARAMS ((void));
 static basic_block make_reorder_chain_1	PARAMS ((basic_block, basic_block));
+
+static void find_traces			PARAMS ((void));
+static int find_group_of_traces		PARAMS ((int, gcov_type, 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 +265,164 @@ make_reorder_chain_1 (bb, prev)
   return prev;
 }
 
+/* Compute the key (for the heap) of the basic block BB.  */
+#define BB_TO_KEY(bb) ((BB_FREQ_MAX)-((bb)->frequency))
+
+/* Finds a group of traces for BRANCH_TH and EXEC_TH i.e. do not include basic
+   blocks their probability is lower than BRANCH_TH or threir frequency is
+   lower than EXEC_TH.  It 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. It expects that the starting basic blocks are in the *HEAP and at
+   the end stores the starting points for the next round into *HEAP.
+   Returns the number of (original) basic blocks added into traces.  */
+static int
+find_group_of_traces (branch_th, exec_th, traces, n_traces, group_no, heap)
+     int branch_th;
+     gcov_type exec_th;
+     struct trace *traces;
+     int *n_traces;
+     int group_no;
+     fibheap_t *heap;
+{
+  int added = 0;
+  /* Heap for discarded basic blocks which are possible starting points for
+     the next round.  */
+  fibheap_t new_heap = fibheap_new ();
+ 
+  while (!fibheap_empty (*heap))
+    {
+      basic_block bb;
+      edge best_edge, e;
+      int max_prob;
+      struct trace *trace;
+
+      bb = fibheap_extract_min (*heap);
+      if (RBI (bb)->visited)
+	continue;
+
+      trace = traces + *n_traces;
+      trace->first = bb;
+      trace->group_no = group_no;
+
+      do {
+	best_edge = NULL;
+	max_prob = -1;
+
+	RBI (bb)->visited = 1;
+	added++;
+       
+	/* Find the best successor.  */
+	for (e = bb->succ; e; e = e->succ_next)
+	  {
+	    /* Exit or already visited successor.  */
+	    if (e->dest == EXIT_BLOCK_PTR || RBI (e->dest)->visited)
+	      continue;
+
+	    /* Improbable or infrequent successor.  */
+	    if (e->probability < branch_th || e->dest->frequency < exec_th)
+	      {
+		/* This successor is possible starting point for next round
+		   of trace creation.  */
+		fibheap_insert (new_heap, BB_TO_KEY (e->dest), e->dest);
+		continue;
+	      }
+
+	    if (e->probability > max_prob 
+		|| (e->probability == max_prob
+		    && e->dest->frequency < best_edge->dest->frequency))
+		/* If the edge has the same probability like the temporary
+		   best edge take the basic block with lower frequency
+		   because the higher frequency is caused by other edge
+		   going to that block.  */
+	      {
+		/* Start a secondary trace from the old temporary best 
+		   successor.  */
+		if (best_edge)
+		  fibheap_insert (*heap, BB_TO_KEY (best_edge->dest), 
+				  best_edge->dest);
+		best_edge = e;
+		max_prob = e->probability;
+	      }
+	    else
+	      {
+		/* Start a secondary trace from this successor.  */
+		fibheap_insert (*heap, BB_TO_KEY (e->dest), e->dest);
+	      }
+	  }
+	if (best_edge)	/* Found suitable successor.  */
+	  {
+	    RBI (bb)->next = best_edge->dest;
+	    bb = best_edge->dest;
+	  }
+
+      } while (best_edge);
+
+      trace->last = bb;
+      (*n_traces)++;
+    } 
+
+  fibheap_delete (*heap);
+
+  /* "Return" the new heap.  */
+  *heap = new_heap;
+
+  return added;
+}
+
+/* Find the traces for Software Trace Cache.  */
+static void
+find_traces ()
+{
+  int branch_threshold[] = {400, 200, 100, 0};
+  int exec_threshold[] = {500, 200, 50, 0};
+  int n_threshold = sizeof (branch_threshold) / sizeof (int);
+  int n_visited;
+  int old_n_basic_blocks;
+  int i;
+  basic_block bb0;
+  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;
+ 
+  /* Find the traces.  */
+  heap = fibheap_new();
+  bb0 = BASIC_BLOCK (0);
+  fibheap_insert (heap, BB_TO_KEY (bb0), bb0);
+  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] * bb0->frequency / 1000,
+			      traces, &n_traces, i, &heap);
+    }
+  fibheap_delete (heap);
+
+  if (rtl_dump_file)
+    {
+      for (i = 0; i < n_traces; i++)
+	{
+	  basic_block bb;
+	  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
@@ -262,7 +433,8 @@ reorder_basic_blocks ()
 
   cfg_layout_initialize ();
 
-  make_reorder_chain ();
+  /* make_reorder_chain (); */
+  find_traces ();
 
   if (rtl_dump_file)
     dump_flow_info (rtl_dump_file);