This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[cfg-branch] improved Software Trace Cache


Hi,

I have improved STC. Now, when it selects the best successor of duplicated BB it ignores the edges to the BBs that are already in the trace. So it creates better traces and duplicates less BBs.
The duplication in the last round (there are 4 rounds with different thresholds) is done only if the code does not grow. This eliminates the majority of duplications.
I have found out that this version duplicates about 5% of BBs on gcc sources (the first version duplicated about 24%). The slowdown on large binaries (gcc, perl) should be none or lower than the first version of STC.

I added 2 elements ('duplicated' and 'original') to struct reorder_block_def. duplicated is a flag whether the BB was duplicated (it is set in the original BB), and original is the original BB (it is set in the child BB).
I guess Honza <jh@suse.cz> will not be happy about this, but I think this is the best solution because I need this information for each BB and the number of BBs grows.


2001-12-07  Josef Zlomek  <zlomek@matfyz.cz>

	* bb-reorder.c: improved Software Trace Cache with duplication of basic
	blocks.
	* cfglayout.h: Added elements 'duplicated' and 'original' to struct
	reorder_block_def.
	* Makefile.in: Added dependencies on fibheap.h.

*** gcc-old/gcc/Makefile.in	Fri Nov 30 21:57:40 2001
--- gcc-new/gcc/Makefile.in	Tue Dec  4 17:55:40 2001
*************** predict.o: predict.c $(CONFIG_H) $(SYSTE
*** 1545,1553 ****
     $(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
  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
  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
--- 1545,1553 ----
     $(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 $(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 $(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/cfglayout.h	Mon Nov 12 17:04:42 2001
--- gcc-new/gcc/cfglayout.h	Wed Nov 28 20:57:00 2001
*************** typedef struct reorder_block_def
*** 29,34 ****
--- 29,36 ----
    scope scope;
    basic_block next;
    int visited;
+   int duplicated;
+   basic_block original;
  } *reorder_block_def;
  
  #define RBI(BB)	((reorder_block_def) (BB)->aux)
*** gcc-old/gcc/bb-reorder.c	Mon Nov 12 16:44:47 2001
--- gcc-new/gcc/bb-reorder.c	Fri Dec  7 18:35:02 2001
***************
*** 19,83 ****
     02111-1307, USA.  */
  
  /* References:
  
-    "Profile Guided Code Positioning"
-    Pettis and Hanson; PLDI '90.
- 
-    TODO:
- 
-    (1) Consider:
- 
- 		if (p) goto A;		// predict taken
- 		foo ();
- 	      A:
- 		if (q) goto B;		// predict taken
- 		bar ();
- 	      B:
- 		baz ();
- 		return;
- 
-        We'll currently reorder this as
- 
- 		if (!p) goto C;
- 	      A:
- 		if (!q) goto D;
- 	      B:
- 		baz ();
- 		return;
- 	      D:
- 		bar ();
- 		goto B;
- 	      C:
- 		foo ();
- 		goto A;
- 
-        A better ordering is
- 
- 		if (!p) goto C;
- 		if (!q) goto D;
- 	      B:
- 		baz ();
- 		return;
- 	      C:
- 		foo ();
- 		if (q) goto B;
- 	      D:
- 		bar ();
- 		goto B;
- 
-        This requires that we be able to duplicate the jump at A, and
-        adjust the graph traversal such that greedy placement doesn't
-        fix D before C is considered.
- 
-    (2) Coordinate with shorten_branches to minimize the number of
-        long branches.
- 
-    (3) Invent a method by which sufficiently non-predicted code can
-        be moved to either the end of the section or another section
-        entirely.  Some sort of NOTE_INSN note would work fine.
- 
-        This completely scroggs all debugging formats, so the user
-        would have to explicitly ask for it.
  */
  
  #include "config.h"
--- 19,29 ----
     02111-1307, USA.  */
  
  /* References:
+   
+    "Software Trace Cache"
+    Ramirez, Larriba-Pey, Navarro, Torrellas and Valero; 1999
+    http://citeseer.nj.nec.com/15361.html
  
  */
  
  #include "config.h"
***************
*** 89,255 ****
  #include "flags.h"
  #include "output.h"
  #include "cfglayout.h"
  
  /* Local function prototypes.  */
! static void make_reorder_chain		PARAMS ((void));
! static basic_block make_reorder_chain_1	PARAMS ((basic_block, basic_block));
  
! /* Compute an ordering for a subgraph beginning with block BB.  Record the
!    ordering in RBI()->index and chained through RBI()->next.  */
  
  static void
! make_reorder_chain ()
  {
!   basic_block prev = NULL;
!   int nbb_m1 = n_basic_blocks - 1;
!   basic_block next;
! 
!   /* Loop until we've placed every block.  */
!   do
      {
!       int i;
  
!       next = NULL;
! 
!       /* Find the next unplaced block.  */
!       /* ??? Get rid of this loop, and track which blocks are not yet
! 	 placed more directly, so as to avoid the O(N^2) worst case.
! 	 Perhaps keep a doubly-linked list of all to-be-placed blocks;
! 	 remove from the list as we place.  The head of that list is
! 	 what we're looking for here.  */
  
!       for (i = 0; i <= nbb_m1 && !next; ++i)
  	{
! 	  basic_block bb = BASIC_BLOCK (i);
! 	  if (! RBI (bb)->visited)
! 	    next = bb;
  	}
!       if (next)
!         prev = make_reorder_chain_1 (next, prev);
      }
!   while (next);
!   RBI (prev)->next = NULL;
  }
  
! /* A helper function for make_reorder_chain.
  
!    We do not follow EH edges, or non-fallthru edges to noreturn blocks.
!    These are assumed to be the error condition and we wish to cluster
!    all of them at the very end of the function for the benefit of cache
!    locality for the rest of the function.
  
!    ??? We could do slightly better by noticing earlier that some subgraph
!    has all paths leading to noreturn functions, but for there to be more
!    than one block in such a subgraph is rare.  */
  
! static basic_block
! make_reorder_chain_1 (bb, prev)
       basic_block bb;
-      basic_block prev;
  {
    edge e;
-   basic_block next;
-   rtx note;
- 
-   /* Mark this block visited.  */
-   if (prev)
-     {
-  restart:
-       RBI (prev)->next = bb;
  
!       if (rtl_dump_file && prev->index + 1 != bb->index)
! 	fprintf (rtl_dump_file, "Reordering block %d after %d\n",
! 		 bb->index, prev->index);
!     }
!   else
!     {
!       if (bb->index != 0)
! 	abort ();
!     }
!   RBI (bb)->visited = 1;
!   prev = bb;
  
!   if (bb->succ == NULL)
!     return prev;
  
!   /* Find the most probable block.  */
  
!   next = NULL;
!   if (any_condjump_p (bb->end)
!       && (note = find_reg_note (bb->end, REG_BR_PROB, 0)) != NULL)
      {
!       int taken, probability;
!       edge e_taken, e_fall;
! 
!       probability = INTVAL (XEXP (note, 0));
!       taken = probability > REG_BR_PROB_BASE / 2;
  
!       /* Find the normal taken edge and the normal fallthru edge.
! 
! 	 Note, conditional jumps with other side effects may not
! 	 be fully optimized.  In this case it is possible for
! 	 the conditional jump to branch to the same location as
! 	 the fallthru path.
  
! 	 We should probably work to improve optimization of that
! 	 case; however, it seems silly not to also deal with such
! 	 problems here if they happen to occur.  */
  
!       e_taken = e_fall = NULL;
!       for (e = bb->succ; e ; e = e->succ_next)
  	{
! 	  if (e->flags & EDGE_FALLTHRU)
! 	    e_fall = e;
! 	  else if (! (e->flags & EDGE_EH))
! 	    e_taken = e;
  	}
  
!       next = (taken ? e_taken : e_fall)->dest;
      }
  
!   /* In the absence of a prediction, disturb things as little as possible
!      by selecting the old "next" block from the list of successors.  If
!      there had been a fallthru edge, that will be the one.  */
!   if (! next)
!     {
!       for (e = bb->succ; e ; e = e->succ_next)
! 	if (e->dest->index == bb->index + 1)
! 	  {
! 	    if ((e->flags & EDGE_FALLTHRU)
! 	        || (e->dest->succ
! 	            && ! (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH))))
! 	      next = e->dest;
! 	    break;
! 	  }
!     }
  
!   /* Make sure we didn't select a silly next block.  */
!   if (! next || next == EXIT_BLOCK_PTR || RBI (next)->visited)
!     next = NULL;
! 
!   /* Recurse on the successors.  Unroll the last call, as the normal
!      case is exactly one or two edges, and we can tail recurse.  */
!   for (e = bb->succ; e; e = e->succ_next)
!     if (e->dest != EXIT_BLOCK_PTR
! 	&& ! RBI (e->dest)->visited
! 	&& e->dest->succ
! 	&& ! (e->flags & (EDGE_ABNORMAL_CALL | EDGE_EH)))
!       {
! 	if (next)
! 	  {
! 	    prev = make_reorder_chain_1 (next, prev);
! 	    next = RBI (e->dest)->visited ? NULL : e->dest;
! 	  }
! 	else
! 	  next = e->dest;
!       }
!   if (next)
!     {
!       bb = next;
!       goto restart;
!     }
  
!   return prev;
  }
  
  /* Reorder basic blocks.  The main entry point to this file.  */
--- 35,474 ----
  #include "flags.h"
  #include "output.h"
  #include "cfglayout.h"
+ #include "fibheap.h"
+ 
+ /* The number of rounds which the code can grow in.  */
+ #define N_CODEGROWING_ROUNDS 3
+ 
+ #define N_THRESHOLD 4
+ 
+ /* Branch thresholds in thousandths (per milles) of the REG_BR_PROB_BASE.  */
+ static int branch_threshold[N_THRESHOLD] = {400, 200, 100, 0};
+   
+ /* Exec thresholds in thousandths (per milles) of the frequency of bb 0.  */
+ static int exec_threshold[N_THRESHOLD] = {500, 200, 50, 0};
+ 
+ /* Length of unconditional jump instruction.  */
+ static int uncond_jump_length;
+ 
+ struct trace
+ {
+   /* First and last basic block of the trace.  */
+   basic_block first, last;
+ 
+   /* The round of the STC creation which this trace was found in.  */
+   int round;
+ };
  
  /* Local function prototypes.  */
! static void find_traces			PARAMS ((void));
! static void find_traces_1_round		PARAMS ((int, int, struct trace *,
! 						 int *, int, fibheap_t *,
! 						 bool));
! static int bb_to_key			PARAMS ((basic_block));
! static bool copy_bb_p			PARAMS ((basic_block, int, bool));
! static bool better_edge_p		PARAMS ((basic_block, edge, int, int,
!                                                  int *, int *, int *, int *));
! static int get_uncond_jump_length	PARAMS ((void));
  
! /* Find the traces for Software Trace Cache.  Record the ordering
!    in RBI()->index and chain it through RBI()->next.  */
  
  static void
! find_traces ()
  {
!   int i;
!   int n_traces;
!   struct trace *traces;
!   basic_block bb0;
!   fibheap_t heap;
!  
!   /* There will be at most N_BASIC_BLOCKS traces because trace can start only
!      in an original (not duplicated) basic block.  */
!   traces = xmalloc (n_basic_blocks * sizeof(struct trace));
!   n_traces = 0;
!  
!   /* Find the traces.  */
!   bb0 = BASIC_BLOCK (0);
!   heap = fibheap_new();
!   fibheap_insert (heap, bb_to_key (bb0), bb0);
!   for (i = 0; i < N_THRESHOLD; i++)
      {
!       if (rtl_dump_file)
!         fprintf (rtl_dump_file, "STC - round %d\n", i);
  
!       find_traces_1_round (branch_threshold[i] * REG_BR_PROB_BASE / 1000,
! 			   exec_threshold[i] * bb0->frequency / 1000,
! 			   traces, &n_traces, i, &heap,
! 			   !optimize_size && i < N_CODEGROWING_ROUNDS);
!     }
!   fibheap_delete (heap);
  
!   if (rtl_dump_file)
!     {
!       for (i = 0; i < n_traces; i++)
  	{
! 	  basic_block bb;
! 	  fprintf(rtl_dump_file, "Trace %d (round %d):  ", i, traces[i].round);
! 	  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);
  }
  
! /* One round of finding traces. Find 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 into traces.  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 the starting basic blocks
!    are in the *HEAP and at the end it deletes *HEAP and stores the starting
!    points for the next round into *HEAP.  SIZE_CAN_GROW is the flag whether 
!    the code is permited to grow.  */
! 
! static void
! find_traces_1_round (branch_th, exec_th, traces, n_traces, round, heap,
!                      size_can_grow)
!      int branch_th;
!      int exec_th;
!      struct trace *traces;
!      int *n_traces;
!      int round;
!      fibheap_t *heap;
!      bool size_can_grow;
! {
!   /* 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;
!       struct trace *trace;
!       edge best_edge, e;
! 
!       bb = fibheap_extract_min (*heap);
!       if (rtl_dump_file)
!         fprintf (rtl_dump_file, "Getting bb %d%s\n", bb->index,
! 	         RBI (bb)->visited ? " (visited)" : "");
!       if (RBI (bb)->visited)
! 	continue;
! 
!       trace = traces + *n_traces;
!       trace->first = bb;
!       trace->last = bb;
!       trace->round = round;
!       (*n_traces)++;
! 
!       do
!         {
! 	  /* If the probability of an edge is between prob_lower and
! 	     prob_higher the edge is considered to be as probable as the
! 	     temporary best edge.  Similar for frequencies of successors.  */
!           int prob_lower = -INT_MAX, prob_higher = -INT_MAX;
!           int freq_lower = -INT_MAX, freq_higher = -INT_MAX;
! 	  int scale, prob;
! 
! 	  best_edge = NULL;
! 	  RBI (bb)->visited = *n_traces;
! 	  if (rtl_dump_file)
! 	    fprintf (rtl_dump_file, "Basic block %d was visited in trace %d\n",
! 	             bb->index, *n_traces - 1);
! 
!           scale = REG_BR_PROB_BASE;
!           if (RBI (bb)->original 
! 	      && RBI (RBI (bb)->original)->duplicated == *n_traces)
! 	    /* We are in a bb which was duplicated in this trace.
! 	       Ignore the probability of edges to basic blocks visited in this
! 	       trace.  */
! 	    {
!               for (e = bb->succ; e; e = e->succ_next)
!                 if (RBI (e->dest)->visited == *n_traces)
!                   scale -= e->probability;
!             }
!           if (rtl_dump_file)
!             fprintf (rtl_dump_file, "BB %d: scale = %d\n", bb->index, scale);
! 
! 	  /* Select the successor that will be placed after BB.  */
! 	  for (e = bb->succ; e; e = e->succ_next)
! 	    {
! 	      int freq;
! 
! 	      if (e->flags & EDGE_FAKE)
! 	        abort();
! 
! 	      if (e->dest == EXIT_BLOCK_PTR)
! 	        continue;
! 	      if (RBI (e->dest)->duplicated == *n_traces)
! 	        continue;
! 
! 	      /* Get the scaled probability.  */
!               if (RBI (bb)->original 
! 		  && RBI (RBI (bb)->original)->duplicated == *n_traces
!                   && RBI (e->dest)->visited == *n_traces)
!                 prob = 0;
!               else if (scale)
!                 prob = REG_BR_PROB_BASE * e->probability / scale;
!               else
!                 prob = REG_BR_PROB_BASE;
! 
! 	      if (RBI (e->dest)->visited)
! 	        {
! 		  if ((e->flags & EDGE_COMPLEX)
! 		      || !copy_bb_p (e->dest, *n_traces, size_can_grow))
! 		    continue;
! 		  freq = bb->frequency * e->probability / REG_BR_PROB_BASE;
! 		}
! 	      else
! 	        {
! 		  freq = e->dest->frequency;
! 		}
! 
! 	      /* Improbable or infrequent successor.  */
! 	      if (prob < branch_th || freq < exec_th)
! 	        {
! 		  if (!RBI (e->dest)->visited)
! 		    /* This bb is not in any trace yet.  */
! 		    {
! 		      /* This successor is possible starting point for next
! 		         round of trace creation.  */
! 		      fibheap_insert (new_heap, bb_to_key (e->dest), e->dest);
! 
! 		      if (rtl_dump_file)
! 		        fprintf (rtl_dump_file,
! 		                 "  Possible start point of next round: %d\n",
! 		                 e->dest->index);
! 		    }
! 		  continue;
! 	        }
! 
! 	      if (better_edge_p (bb, e, prob, freq, &prob_lower, &prob_higher,
! 		                 &freq_lower, &freq_higher))
! 	        {
! 		  if (best_edge && !RBI (best_edge->dest)->visited)
! 		    {
! 		      /* Start a secondary trace from the old temporary best
! 		         successor.  */
! 		      fibheap_insert (*heap, bb_to_key (best_edge->dest),
! 				      best_edge->dest);
! 
! 		      if (rtl_dump_file)
! 		        fprintf (rtl_dump_file, 
! 			         "  Possible start of secondary trace: %d\n",
! 		                 best_edge->dest->index);
! 		    }
! 
! 		  best_edge = e;
! 		}
! 	      else if (!RBI (e->dest)->visited)
! 	        {
! 		  /* Start a secondary trace from this successor.  */
! 		  fibheap_insert (*heap, bb_to_key (e->dest), e->dest);
! 
! 		  if (rtl_dump_file)
! 		    fprintf (rtl_dump_file, 
! 			     "  Possible start of secondary trace: %d\n",
! 		             e->dest->index);
! 		}
! 	    }
! 
! 	  if (best_edge)
! 	    /* Found suitable successor.  */
! 	    {
! 	      if (RBI (best_edge->dest)->visited)
! 	        {
! 		  basic_block new_bb, old_bb;
! 
! 		  old_bb = best_edge->dest;
! 		  new_bb = cfg_layout_duplicate_bb (best_edge->dest, best_edge);
! 	          if (best_edge->dest != new_bb)
! 		    abort ();
! 	          if (RBI (best_edge->dest)->visited)
! 		    abort ();
! 		  if (rtl_dump_file)
! 		    fprintf (rtl_dump_file, "Duplicated bb %d (created bb %d)\n",
! 		             old_bb->index, new_bb->index);
! 	          RBI (old_bb)->duplicated = *n_traces;
! 		  RBI (new_bb)->original = old_bb;
! 	          RBI (bb)->next = new_bb;
! 		  RBI (bb)->visited = *n_traces;
! 		  bb = new_bb;
! 		}
! 	      else
! 	        {
! 	          RBI (bb)->next = best_edge->dest;
! 	          bb = best_edge->dest;
! 		}
! 	    }
! 	}
!       while (best_edge);
!       trace->last = bb;
!     } 
! 
!   fibheap_delete (*heap);
  
!   /* "Return" the new heap.  */
!   *heap = new_heap;
! }
  
! /* Compute and return the key (for the heap) of the basic block BB.  */
  
! static int
! bb_to_key (bb)
       basic_block bb;
  {
    edge e;
  
!   for (e = bb->pred; e; e = e->pred_next)
!     if (!(e->flags & EDGE_DFS_BACK) && !RBI (e->src)->visited)
!       return -bb->frequency;
! 
!   /* All edges to 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 - bb->frequency;
! }
  
! /* Return true when the edge E from basic block BB is better than the temporary
!    best edge (details are in function).  The (scaled) probability of edge E is
!    PROB. The frequency of the successor is FREQ. The *PROB_LOWER and
!    *PROB_HIGHER are the lower and higher bounds of interval which the PROB must
!    be in to be "equivalent" to the probability of the temporary best edge.
!    Similarly the *FREQ_LOWER and *FREQ_HIGHER. 
!    If the edge is considered to be better it changes the values of *PROB_LOWER,
!    *PROB_HIGHER, *FREQ_LOWER and *FREQ_HIGHER to appropriate values.  */
! 
! static bool
! better_edge_p (bb, e, prob, freq, prob_lower, prob_higher, freq_lower, 
!                freq_higher)
!      basic_block bb;
!      edge e;
!      int prob;
!      int freq;
!      int *prob_lower;
!      int *prob_higher;
!      int *freq_lower;
!      int *freq_higher;
! {
!   bool is_better_edge;
  
!   if (prob > *prob_higher)
!     /* The edge has higher probability than the temporary best edge.  */
!     is_better_edge = true;
!   else if (prob < *prob_lower)
!     /* The edge has lower probability than the temporary best edge.  */
!     is_better_edge = false;
!   else if (freq < *freq_lower)
!     /* The edge and the temporary best edge  have almost equivalent
!        probabilities.  The higher frequency of a successor now means 
!        that there is another edge going into that successor.
!        This successor has lower frequency so it is better.  */
!     is_better_edge = true;
!   else if (freq > *freq_higher)
!     /* This successor has higher frequency so it is worse.  */
!     is_better_edge = false;
!   else if (e->dest->index == bb->index + 1)
!     /* The edges have equivalent probabilities and the successors
!        have equivalent frequencies.  Select the previous successor.  */
!     is_better_edge = true;
!   else
!     is_better_edge = false;
  
!   if (is_better_edge)
      {
!       int prob_diff, freq_diff;
  
!       prob_diff = prob / 10;
!       *prob_higher = prob + prob_diff;
!       *prob_lower = prob - prob_diff;
!       freq_diff = freq / 10;
!       *freq_higher = freq + freq_diff;
!       *freq_lower = freq - freq_diff;
!     }
!   return is_better_edge;
! }
  
! /* Return true when BB can and should be copied.  The trace with number TRACE
!    is now being built.  SIZE_CAN_GROW is the flag whether the code is permited
!    to grow.  */
  
! static bool
! copy_bb_p (bb, trace, size_can_grow)
!      basic_block bb;
!      int trace;
!      bool size_can_grow;
! {
!   int size = 0;
!   rtx insn;
!   basic_block first = bb;
!  
!   if (!bb->frequency)
!     return false;
!   if (!bb->pred || !bb->pred->pred_next)
!     return false;
!   while (size < 8 * uncond_jump_length)
!     {
!       edge e, best_edge = NULL;
!       int prob_lower = -INT_MAX, prob_higher = -INT_MAX;
!       int freq_lower = -INT_MAX, freq_higher = -INT_MAX;
! 
!       if (RBI (bb)->original && RBI (RBI (bb)->original)->duplicated == trace)
!         return false;
!       if (!cfg_layout_can_duplicate_bb_p (bb))
!         return false;
!       for (insn = bb->head; insn != NEXT_INSN (bb->end);
! 	   insn = NEXT_INSN (insn))
  	{
! 	  if (INSN_P (insn))
! 	    size += get_attr_length (insn);
  	}
  
!       /* Select the successor.  */
!       for (e = bb->succ; e; e = e->succ_next)
!         {
! 	  if (e->dest == EXIT_BLOCK_PTR)
! 	    continue;
! 	  if (RBI (e->dest)->visited == trace)
! 	    continue;
! 	  if (better_edge_p (bb, e, e->probability, e->dest->frequency,
! 		             &prob_lower, &prob_higher, &freq_lower,
! 			     &freq_higher))
! 	    best_edge = e;
!         }
!       if (best_edge)
! 	bb = best_edge->dest;
!       else if (size_can_grow || size <= uncond_jump_length)
! 	return true;
!       else
! 	return false;
!       if (bb == first)
! 	return false;
      }
+   return false;
+ }
  
! /* Return the maximum length of unconditional jump.  */
  
! static int
! get_uncond_jump_length ()
! {
!   rtx label, jump;
!   int length;
  
!   label = emit_label_before (gen_label_rtx (), get_insns ());
!   jump = emit_jump_insn (gen_jump (label));
!   
!   length = get_attr_length (jump);
! 
!   delete_insn (jump);
!   delete_insn (label);
!   return length;
  }
  
  /* Reorder basic blocks.  The main entry point to this file.  */
*************** reorder_basic_blocks ()
*** 262,268 ****
  
    cfg_layout_initialize ();
  
!   make_reorder_chain ();
  
    if (rtl_dump_file)
      dump_flow_info (rtl_dump_file);
--- 481,488 ----
  
    cfg_layout_initialize ();
  
!   uncond_jump_length = get_uncond_jump_length ();
!   find_traces ();
  
    if (rtl_dump_file)
      dump_flow_info (rtl_dump_file);


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]