contrib/gcc/bb-reorder.c

21 /* This (greedy) algorithm constructs traces in several rounds.
26    probable successor to the end of a trace.  Finally it connects the traces.
39    other seeds for this round and the secondary traces will start in them.
50    When connecting traces it first checks whether there is an edge from the
52    When there are still some unconnected traces it checks whether there exists
55    BB is duplicated and the traces are connected through this duplicate.
56    The rest of traces are simply connected so there will be a jump to the
113    block the edge destination is not duplicated while connecting traces.  */
196    collected into traces until the very last round); or 2). There will
220 /* Find the traces for Software Trace Cache.  Chain each trace through
221    RBI()->next.  Store the number of traces to N_TRACES and description of
222    traces to TRACES.  */
225 find_traces (int *n_traces, struct trace *traces)
254   /* Find the traces.  */
269 			   count_threshold, traces, n_traces, i, &heap,
280 		   traces[i].round + 1);
281 	  for (bb = traces[i].first; bb != traces[i].last; bb = bb->aux)
420 /* One round of finding traces. Find traces for BRANCH_TH and EXEC_TH i.e. do
422    frequency is lower than EXEC_TH into traces (or count is lower than
423    COUNT_TH).  It stores the new traces into TRACES and modifies the number of
424    traces *N_TRACES. Sets the round (which the trace belongs to) to ROUND. It
430 		     struct trace *traces, int *n_traces, int round,
471       trace = traces + *n_traces;
549 	     to a trace.  We'll duplicate it when connecting traces.  */
895 /* Connect traces in array TRACES, N_TRACES is the count of traces.  */
898 connect_traces (int n_traces, struct trace *traces)
918   current_partition = BB_PARTITION (traces[0].first);
923       if (BB_PARTITION (traces[0].first)
924 	  != BB_PARTITION (traces[i].first))
950 	  && BB_PARTITION (traces[t].first) != current_partition)
955       /* Find the predecessor traces.  */
961 	  FOR_EACH_EDGE (e, ei, traces[t2].first->preds)
974 			  && traces[bbd[si].end_of_trace].length > best_len)))
977 		  best_len = traces[bbd[si].end_of_trace].length;
997 	traces[last_trace].last->aux = traces[t2].first;
1000       /* Find the successor traces.  */
1007 	  FOR_EACH_EDGE (e, ei, traces[t].last->succs)
1020 			  && traces[bbd[di].start_of_trace].length > best_len)))
1023 		  best_len = traces[bbd[di].start_of_trace].length;
1035 	      traces[last_trace].last->aux = traces[t].first;
1041 	      /* Try to connect the traces by duplication of 1 block.  */
1046 	      FOR_EACH_EDGE (e, ei, traces[t].last->succs)
1060 			&& traces[bbd[e->dest->index].start_of_trace].length
1083 					&& traces[bbd[di].start_of_trace].length
1089 			      best2_len = traces[bbd[di].start_of_trace].length;
1114 			       traces[t].last->index, best->dest->index);
1123 		  new_bb = copy_bb (best->dest, best, traces[t].last, t);
1124 		  traces[t].last = new_bb;
1128 		      traces[last_trace].last->aux = traces[t].first;
1133 		    break;	/* Stop finding the successor traces.  */
1136 		break;	/* Stop finding the successor traces.  */
1146       for (bb = traces[0].first; bb; bb = bb->aux)
1896   struct trace *traces;
1926   traces = XNEWVEC (struct trace, n_basic_blocks);
1928   find_traces (&n_traces, traces);
1929   connect_traces (n_traces, traces);
1930   FREE (traces);