[cfg-branch] improved Software Trace Cache
Josef Zlomek
zlomj9am@artax.karlin.mff.cuni.cz
Sun Dec 9 07:20:00 GMT 2001
> > > I guess it is not worthwhile - if you duplicate small BB you may save
> > > considerable portion of time, if you duplicate large BB, the cost of branch
> > > saved is tiny compared to the block itself.
> >
> > Now we are not duplicating large blocks.
>
> There's a bug in copy_bb_p, I'm solving it right now.
Fixed (sometimes it did not duplicate when I wanted to duplicate).
Bootstrapped on i386.
2001-12-09 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 Sun Dec 9 16:12:52 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,486 ----
#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_MIN, prob_higher = INT_MIN;
! int freq_lower = INT_MIN, freq_higher = INT_MIN;
! 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;
! /* Looking from duplicated BB (in this) to visited BB. */
! if (RBI (bb)->original
! && RBI (RBI (bb)->original)->duplicated == *n_traces
! && RBI (e->dest)->visited == *n_traces)
! continue;
!
! /* Get the scaled probability. */
! 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 (1)
! {
! edge e, best_edge;
! int prob_lower, prob_higher;
! int freq_lower, freq_higher;
!
! 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);
}
+ if (size > 8 * uncond_jump_length)
+ return false;
! /* Select the successor. */
! best_edge = NULL;
! prob_lower = INT_MIN;
! freq_lower = INT_MIN;
! prob_higher = INT_MIN;
! freq_higher = INT_MIN;
! 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;
! if (!best_edge || !RBI (best_edge->dest)->visited)
! /* All edges point to EXIT_BLOCK or to the same trace
! OR the selected successor has not been visited yet. */
! {
! 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);
--- 493,500 ----
cfg_layout_initialize ();
! uncond_jump_length = get_uncond_jump_length ();
! find_traces ();
if (rtl_dump_file)
dump_flow_info (rtl_dump_file);
More information about the Gcc-patches
mailing list