This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [cfg-branch]: Software Trace Cache
> One extra issue - when the probabilities and frequencies are equivalent, choose
> the block that followed the block orriginally, so we don't reorder the code
> for no obvious purpose.
>
> Another trick may be to relax the e->probability == max_prob to accept "nearly
> equivalent" probabilities. This will make nearly balanced if statements to be
> organized in a way that then is on line saving one jump. I guess we can accept
> +-10% in such case. Most of the BB reordering algorithms I've seen implemented
> speccases this situation even when I didn't seen it mentioned in any paper.
Both features implemented.
I bootstrapped the patch on i386 and the regression tests tell the same things as without the patch.
Joe
2001-11-24 Josef Zlomek <zlomek@matfyz.cz>
* bb-reorder.c: Better implementation of Software Trace Cache, removed
the old block reordering code.
* Makefile.in: Added dependencies on fibheap.h
*** gcc-old/gcc/Makefile.in Sat Nov 24 07:31:18 2001
--- gcc-new/gcc/Makefile.in Sat Nov 24 09:31:59 2001
*************** predict.o: predict.c $(CONFIG_H) $(SYSTE
*** 1590,1598 ****
$(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
--- 1590,1598 ----
$(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/bb-reorder.c Sat Nov 24 07:31:18 2001
--- gcc-new/gcc/bb-reorder.c Sat Nov 24 09:35:30 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,270 ----
#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 find_traces PARAMS ((void));
! static int find_group_of_traces PARAMS ((int, gcov_type, struct trace *,
! int *, int, fibheap_t *));
!
! /* Compute the key (for the heap) of the basic block BB. */
! #define BB_TO_KEY(bb) (-((bb)->frequency))
! /* Find the traces for Software Trace Cache. Record the ordering
! in RBI()->index and chained through RBI()->next. */
! static void
! find_traces ()
{
! /* Branch thresholds in thousandths (per milles) of the REG_BR_PROB_BASE. */
! int branch_threshold[] = {400, 200, 100, 0};
!
! /* Exec thresholds in thousandths (per milles) of the frequency of bb 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++)
{
! if (rtl_dump_file)
! fprintf (rtl_dump_file, "STC - round %d\n", 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);
! }
! /* 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;
! struct trace *trace;
! edge best_edge = NULL, e;
!
! bb = fibheap_extract_min (*heap);
! if (RBI (bb)->visited)
! continue;
!
! trace = traces + *n_traces;
! trace->first = bb;
! trace->group_no = group_no;
!
! 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;
! bool is_better_edge;
!
! best_edge = NULL;
! RBI (bb)->visited = 1;
! added++;
!
! /* Select the successor that will be placed after BB. */
! 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);
!
! if (rtl_dump_file)
! fprintf (rtl_dump_file,
! " Possible start point of next round: %d\n",
! e->dest->index);
! continue;
! }
!
! if (e->probability > prob_higher)
! /* The edge has higher probability than the temporary
! best edge. */
! is_better_edge = true;
! else if (e->probability < prob_lower)
! /* The edge has lower probability than the temporary
! best edge. */
! is_better_edge = false;
! else if (e->dest->frequency < freq_lower)
! /* The edge and the temp. 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 (e->dest->frequency > freq_higher)
! /* This successor has higher frequency so it is worse. */
! is_better_edge = false;
! else if (e->flags & EDGE_FALLTHRU)
! /* The edges have equivalent probabilities and the successors
! have equivalent frequencies. The edge e was originally
! FALLTHRU so it is better. */
! is_better_edge = true;
! else
! is_better_edge = false;
!
! if (is_better_edge)
! {
! int prob_diff, freq_diff;
!
! /* 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);
!
! if (rtl_dump_file)
! fprintf (rtl_dump_file,
! " Possible start of secondary trace: %d\n",
! best_edge->dest->index);
! }
!
! best_edge = e;
! prob_diff = e->probability / 10;
! prob_higher = e->probability + prob_diff;
! prob_lower = e->probability - prob_diff;
! freq_diff = e->dest->frequency / 10;
! freq_higher = e->dest->frequency + freq_diff;
! freq_lower = e->dest->frequency - freq_diff;
! }
! else
! {
! /* 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. */
! {
! 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;
}
/* 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);
--- 277,283 ----
cfg_layout_initialize ();
! find_traces ();
if (rtl_dump_file)
dump_flow_info (rtl_dump_file);