/* Basic block reordering routines for the GNU compiler.
- Copyright (C) 2000 Free Software Foundation, Inc.
+ Copyright (C) 2000, 2002, 2003 Free Software Foundation, Inc.
- This file is part of GNU CC.
+ This file is part of GCC.
- GNU CC is free software; you can redistribute it and/or modify
- it under the terms of the GNU General Public License as published by
+ GCC is free software; you can redistribute it and/or modify it
+ under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2, or (at your option)
any later version.
- GNU CC is distributed in the hope that it will be useful,
- but WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- GNU General Public License for more details.
+ GCC is distributed in the hope that it will be useful, but WITHOUT
+ ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
+ or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
+ License for more details.
You should have received a copy of the GNU General Public License
- along with GNU CC; see the file COPYING. If not, write to
- the Free Software Foundation, 59 Temple Place - Suite 330,
- Boston, MA 02111-1307, USA. */
+ along with GCC; see the file COPYING. If not, write to the Free
+ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+ 02111-1307, USA. */
+
+/* This (greedy) algorithm constructs traces in several rounds.
+ The construction starts from "seeds". The seed for the first round
+ is the entry point of function. When there are more than one seed
+ that one is selected first that has the lowest key in the heap
+ (see function bb_to_key). Then the algorithm repeatedly adds the most
+ probable successor to the end of a trace. Finally it connects the traces.
+
+ There are two parameters: Branch Threshold and Exec Threshold.
+ If the edge to a successor of the actual basic block is lower than
+ Branch Threshold or the frequency of the successor is lower than
+ Exec Threshold the successor will be the seed in one of the next rounds.
+ Each round has these parameters lower than the previous one.
+ The last round has to have these parameters set to zero
+ so that the remaining blocks are picked up.
+
+ The algorithm selects the most probable successor from all unvisited
+ successors and successors that have been added to this trace.
+ The other successors (that has not been "sent" to the next round) will be
+ other seeds for this round and the secondary traces will start in them.
+ If the successor has not been visited in this trace it is added to the trace
+ (however, there is some heuristic for simple branches).
+ If the successor has been visited in this trace the loop has been found.
+ If the loop has many iterations the loop is rotated so that the
+ source block of the most probable edge going out from the loop
+ is the last block of the trace.
+ If the loop has few iterations and there is no edge from the last block of
+ the loop going out from loop the loop header is duplicated.
+ Finally, the construction of the trace is terminated.
+
+ When connecting traces it first checks whether there is an edge from the
+ last block of one trace to the first block of another trace.
+ When there are still some unconnected traces it checks whether there exists
+ a basic block BB such that BB is a successor of the last bb of one trace
+ and BB is a predecessor of the first block of another trace. In this case,
+ BB is duplicated and the traces are connected through this duplicate.
+ The rest of traces are simply connected so there will be a jump to the
+ beginning of the rest of trace.
+
+
+ References:
+
+ "Software Trace Cache"
+ A. Ramirez, J. Larriba-Pey, C. Navarro, J. Torrellas and M. Valero; 1999
+ http://citeseer.nj.nec.com/15361.html
-/* References:
-
- "Profile Guided Code Positioning"
- Pettis and Hanson; PLDI '90.
*/
#include "config.h"
#include "system.h"
-#include "tree.h"
+#include "coretypes.h"
+#include "tm.h"
#include "rtl.h"
-#include "tm_p.h"
#include "basic-block.h"
-#include "insn-config.h"
-#include "regs.h"
-#include "hard-reg-set.h"
#include "flags.h"
#include "output.h"
-#include "function.h"
-#include "except.h"
-#include "toplev.h"
-#include "recog.h"
-#include "insn-flags.h"
-#include "expr.h"
-#include "obstack.h"
-
-
-/* The contents of the current function definition are allocated
- in this obstack, and all are freed at the end of the function.
- For top-level functions, this is temporary_obstack.
- Separate obstacks are made for nested functions. */
-
-extern struct obstack *function_obstack;
-
-
-/* Structure to hold information about lexical scopes. */
-typedef struct scope_def
-{
- int level;
+#include "cfglayout.h"
+#include "fibheap.h"
+#include "target.h"
- /* The NOTE_INSN_BLOCK_BEG that started this scope. */
- rtx note_beg;
+/* The number of rounds. */
+#define N_ROUNDS 4
- /* The NOTE_INSN_BLOCK_END that ended this scope. */
- rtx note_end;
+/* Branch thresholds in thousandths (per mille) of the REG_BR_PROB_BASE. */
+static int branch_threshold[N_ROUNDS] = {400, 200, 100, 0};
- /* The bb containing note_beg (if any). */
- basic_block bb_beg;
+/* Exec thresholds in thousandths (per mille) of the frequency of bb 0. */
+static int exec_threshold[N_ROUNDS] = {500, 200, 50, 0};
- /* The bb containing note_end (if any). */
- basic_block bb_end;
+/* If edge frequency is lower than DUPLICATION_THRESHOLD per mille of entry
+ block the edge destination is not duplicated while connecting traces. */
+#define DUPLICATION_THRESHOLD 100
- /* List of basic blocks contained within this scope. */
- basic_block *bbs;
+/* Length of unconditional jump instruction. */
+static int uncond_jump_length;
- /* Number of blocks contained within this scope. */
- int num_bbs;
-
- /* The outer scope or NULL if outermost scope. */
- struct scope_def *outer;
-
- /* The first inner scope or NULL if innermost scope. */
- struct scope_def *inner;
-
- /* The last inner scope or NULL if innermost scope. */
- struct scope_def *inner_last;
-
- /* Link to the next (sibling) scope. */
- struct scope_def *next;
-} *scope;
-
-/* Structure to hold information about the scope forest. */
-typedef struct
+/* Structure to hold needed information for each basic block. */
+typedef struct bbro_basic_block_data_def
{
- /* Number of trees in forest. */
- int num_trees;
-
- /* List of tree roots. */
- scope *trees;
-} scope_forest_info;
-
-
-typedef struct reorder_block_def {
- int flags;
- int index;
- basic_block add_jump;
- edge succ;
- rtx eff_head;
- rtx eff_end;
- scope scope;
-} *reorder_block_def;
-
-static struct reorder_block_def rbd_init
-= {
- 0, /* flags */
- 0, /* index */
- NULL, /* add_jump */
- NULL, /* succ */
- NULL_RTX, /* eff_head */
- NULL_RTX, /* eff_end */
- NULL /* scope */
-};
-
+ /* Which trace is the bb start of (-1 means it is not a start of a trace). */
+ int start_of_trace;
-#define REORDER_BLOCK_HEAD 0x1
-#define REORDER_BLOCK_VISITED 0x2
-
-#define REORDER_BLOCK_FLAGS(bb) \
- ((reorder_block_def) (bb)->aux)->flags
+ /* Which trace is the bb end of (-1 means it is not an end of a trace). */
+ int end_of_trace;
-#define REORDER_BLOCK_INDEX(bb) \
- ((reorder_block_def) (bb)->aux)->index
+ /* Which heap is BB in (if any)? */
+ fibheap_t heap;
-#define REORDER_BLOCK_ADD_JUMP(bb) \
- ((reorder_block_def) (bb)->aux)->add_jump
+ /* Which heap node is BB in (if any)? */
+ fibnode_t node;
+} bbro_basic_block_data;
-#define REORDER_BLOCK_SUCC(bb) \
- ((reorder_block_def) (bb)->aux)->succ
+/* The current size of the following dynamic array. */
+static int array_size;
-#define REORDER_BLOCK_EFF_HEAD(bb) \
- ((reorder_block_def) (bb)->aux)->eff_head
+/* The array which holds needed information for basic blocks. */
+static bbro_basic_block_data *bbd;
-#define REORDER_BLOCK_EFF_END(bb) \
- ((reorder_block_def) (bb)->aux)->eff_end
+/* To avoid frequent reallocation the size of arrays is greater than needed,
+ the number of elements is (not less than) 1.25 * size_wanted. */
+#define GET_ARRAY_SIZE(X) ((((X) / 4) + 1) * 5)
-#define REORDER_BLOCK_SCOPE(bb) \
- ((reorder_block_def) (bb)->aux)->scope
+/* Free the memory and set the pointer to NULL. */
+#define FREE(P) \
+ do { if (P) { free (P); P = 0; } else { abort (); } } while (0)
+/* Structure for holding information about a trace. */
+struct trace
+{
+ /* First and last basic block of the trace. */
+ basic_block first, last;
-static int reorder_index;
-static basic_block reorder_last_visited;
+ /* The round of the STC creation which this trace was found in. */
+ int round;
-enum reorder_skip_type {REORDER_SKIP_BEFORE, REORDER_SKIP_AFTER,
- REORDER_SKIP_BLOCK_END};
+ /* The length (i.e. the number of basic blocks) of the trace. */
+ int length;
+};
+/* Maximum frequency and count of one of the entry blocks. */
+int max_entry_frequency;
+gcov_type max_entry_count;
/* Local function prototypes. */
-static rtx skip_insns_between_block PARAMS ((basic_block,
- enum reorder_skip_type));
-static basic_block get_common_dest PARAMS ((basic_block, basic_block));
-static basic_block chain_reorder_blocks PARAMS ((edge, basic_block));
-static void make_reorder_chain PARAMS ((basic_block));
-static void fixup_reorder_chain PARAMS ((void));
-#ifdef ENABLE_CHECKING
-static void verify_insn_chain PARAMS ((void));
-#endif
-static void relate_bbs_with_scopes PARAMS ((scope));
-static scope make_new_scope PARAMS ((int, rtx));
-static void build_scope_forest PARAMS ((scope_forest_info *));
-static void remove_scope_notes PARAMS ((void));
-static void insert_intra_1 PARAMS ((scope, rtx *));
-static void insert_intra_bb_scope_notes PARAMS ((basic_block));
-static void insert_inter_bb_scope_notes PARAMS ((basic_block, basic_block));
-static void rebuild_scope_notes PARAMS ((scope_forest_info *));
-static void free_scope_forest_1 PARAMS ((scope));
-static void free_scope_forest PARAMS ((scope_forest_info *));
-void dump_scope_forest PARAMS ((scope_forest_info *));
-static void dump_scope_forest_1 PARAMS ((scope, int));
-
-/* Skip over insns BEFORE or AFTER BB which are typically associated with
- basic block BB. */
-
-static rtx
-skip_insns_between_block (bb, skip_type)
- basic_block bb;
- enum reorder_skip_type skip_type;
+static void find_traces (int *, struct trace *);
+static basic_block rotate_loop (edge, struct trace *, int);
+static void mark_bb_visited (basic_block, int);
+static void find_traces_1_round (int, int, gcov_type, struct trace *, int *,
+ int, fibheap_t *);
+static basic_block copy_bb (basic_block, edge, basic_block, int);
+static fibheapkey_t bb_to_key (basic_block);
+static bool better_edge_p (basic_block, edge, int, int, int, int);
+static void connect_traces (int, struct trace *);
+static bool copy_bb_p (basic_block, int);
+static int get_uncond_jump_length (void);
+\f
+/* Find the traces for Software Trace Cache. Chain each trace through
+ RBI()->next. Store the number of traces to N_TRACES and description of
+ traces to TRACES. */
+
+static void
+find_traces (int *n_traces, struct trace *traces)
{
- rtx insn, last_insn;
+ int i;
+ edge e;
+ fibheap_t heap;
- if (skip_type == REORDER_SKIP_BEFORE)
+ /* Insert entry points of function into heap. */
+ heap = fibheap_new ();
+ max_entry_frequency = 0;
+ max_entry_count = 0;
+ for (e = ENTRY_BLOCK_PTR->succ; e; e = e->succ_next)
{
- if (bb == ENTRY_BLOCK_PTR)
- return 0;
-
- last_insn = bb->head;
- for (insn = PREV_INSN (bb->head);
- insn && insn != BASIC_BLOCK (bb->index - 1)->end;
- last_insn = insn, insn = PREV_INSN (insn))
- {
- if (NEXT_INSN (insn) != last_insn)
- break;
-
- if (GET_CODE (insn) == NOTE
- && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_END
- && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BASIC_BLOCK
- && NOTE_LINE_NUMBER (insn) != NOTE_INSN_BLOCK_END)
- continue;
-
- break;
- }
+ bbd[e->dest->index].heap = heap;
+ bbd[e->dest->index].node = fibheap_insert (heap, bb_to_key (e->dest),
+ e->dest);
+ if (e->dest->frequency > max_entry_frequency)
+ max_entry_frequency = e->dest->frequency;
+ if (e->dest->count > max_entry_count)
+ max_entry_count = e->dest->count;
}
- else
- {
- last_insn = bb->end;
-
- if (bb == EXIT_BLOCK_PTR)
- return 0;
-
- for (insn = NEXT_INSN (bb->end);
- insn;
- last_insn = insn, insn = NEXT_INSN (insn))
- {
- if (bb->index + 1 != n_basic_blocks
- && insn == BASIC_BLOCK (bb->index + 1)->head)
- break;
-
- if (GET_CODE (insn) == BARRIER
- || GET_CODE (insn) == JUMP_INSN
- || (GET_CODE (insn) == NOTE
- && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END
- || NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_END)))
- continue;
-
- if (GET_CODE (insn) == CODE_LABEL
- && GET_CODE (NEXT_INSN (insn)) == JUMP_INSN
- && (GET_CODE (PATTERN (NEXT_INSN (insn))) == ADDR_VEC
- || GET_CODE (PATTERN
- (NEXT_INSN (insn))) == ADDR_DIFF_VEC))
- {
- insn = NEXT_INSN (insn);
- continue;
- }
-
- /* Skip to next non-deleted insn. */
- if (GET_CODE (insn) == NOTE
- && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED
- || NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED_LABEL))
- continue;
-
- break;
- }
- if (skip_type == REORDER_SKIP_BLOCK_END)
- {
- int found_block_end = 0;
-
- for (; insn; last_insn = insn, insn = NEXT_INSN (insn))
- {
- if (bb->index + 1 != n_basic_blocks
- && insn == BASIC_BLOCK (bb->index + 1)->head)
- break;
-
- if (GET_CODE (insn) == NOTE
- && NOTE_LINE_NUMBER (insn) == NOTE_INSN_BLOCK_END)
- {
- found_block_end = 1;
- continue;
- }
+ /* Find the traces. */
+ for (i = 0; i < N_ROUNDS; i++)
+ {
+ gcov_type count_threshold;
- if (GET_CODE (insn) == NOTE
- && NOTE_LINE_NUMBER (insn) == NOTE_INSN_DELETED)
- continue;
+ if (rtl_dump_file)
+ fprintf (rtl_dump_file, "STC - round %d\n", i + 1);
- if (GET_CODE (insn) == NOTE
- && NOTE_LINE_NUMBER (insn) >= 0
- && NEXT_INSN (insn)
- && GET_CODE (NEXT_INSN (insn)) == NOTE
- && (NOTE_LINE_NUMBER (NEXT_INSN (insn))
- == NOTE_INSN_BLOCK_END))
- continue;
- break;
- }
+ if (max_entry_count < INT_MAX / 1000)
+ count_threshold = max_entry_count * exec_threshold[i] / 1000;
+ else
+ count_threshold = max_entry_count / 1000 * exec_threshold[i];
- if (! found_block_end)
- last_insn = 0;
- }
+ find_traces_1_round (REG_BR_PROB_BASE * branch_threshold[i] / 1000,
+ max_entry_frequency * exec_threshold[i] / 1000,
+ count_threshold, traces, n_traces, i, &heap);
}
+ fibheap_delete (heap);
- return last_insn;
-}
-
-
-/* Return common destination for blocks BB0 and BB1. */
-
-static basic_block
-get_common_dest (bb0, bb1)
- basic_block bb0, bb1;
-{
- edge e0, e1;
-
- for (e0 = bb0->succ; e0; e0 = e0->succ_next)
+ if (rtl_dump_file)
{
- for (e1 = bb1->succ; e1; e1 = e1->succ_next)
+ for (i = 0; i < *n_traces; i++)
{
- if (e0->dest == e1->dest)
- {
- return e0->dest;
- }
+ basic_block bb;
+ fprintf (rtl_dump_file, "Trace %d (round %d): ", i + 1,
+ traces[i].round + 1);
+ for (bb = traces[i].first; bb != traces[i].last; bb = bb->rbi->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);
}
- return 0;
}
-
-/* Move the destination block for edge E after chain end block CEB
- Adding jumps and labels is deferred until fixup_reorder_chain. */
+/* Rotate loop whose back edge is BACK_EDGE in the tail of trace TRACE
+ (with sequential number TRACE_N). */
static basic_block
-chain_reorder_blocks (e, ceb)
- edge e;
- basic_block ceb;
+rotate_loop (edge back_edge, struct trace *trace, int trace_n)
{
- basic_block sb = e->src;
- basic_block db = e->dest;
- rtx cebe_insn, dbh_insn, dbe_insn;
- edge ee, last_edge;
-
- enum cond_types {NO_COND, PREDICT_THEN_WITH_ELSE, PREDICT_ELSE,
- PREDICT_THEN_NO_ELSE, PREDICT_NOT_THEN_NO_ELSE};
- enum cond_types cond_type;
- enum cond_block_types {NO_COND_BLOCK, THEN_BLOCK, ELSE_BLOCK,
- NO_ELSE_BLOCK};
- enum cond_block_types cond_block_type;
-
- if (rtl_dump_file)
- fprintf (rtl_dump_file,
- "Edge from basic block %d to basic block %d last visited %d\n",
- sb->index, db->index, ceb->index);
- cebe_insn = REORDER_BLOCK_EFF_END (ceb);
-
- /* Blocks are in original order. */
- if (sb->index == ceb->index
- && ceb->index + 1 == db->index && NEXT_INSN (cebe_insn))
- return db;
-
- /* Get the type of block and type of condition. */
- cond_type = NO_COND;
- cond_block_type = NO_COND_BLOCK;
- if (GET_CODE (sb->end) == JUMP_INSN && ! simplejump_p (sb->end)
- && condjump_p (sb->end))
+ basic_block bb;
+
+ /* Information about the best end (end after rotation) of the loop. */
+ basic_block best_bb = NULL;
+ edge best_edge = NULL;
+ int best_freq = -1;
+ gcov_type best_count = -1;
+ /* The best edge is preferred when its destination is not visited yet
+ or is a start block of some trace. */
+ bool is_preferred = false;
+
+ /* Find the most frequent edge that goes out from current trace. */
+ bb = back_edge->dest;
+ do
{
- if (e->flags & EDGE_FALLTHRU)
- cond_block_type = THEN_BLOCK;
- else if (get_common_dest (sb->succ->dest, sb))
- cond_block_type = NO_ELSE_BLOCK;
- else
- cond_block_type = ELSE_BLOCK;
-
- if (sb->succ->succ_next
- && get_common_dest (sb->succ->dest, sb))
- {
- if (cond_block_type == THEN_BLOCK)
- {
- if (! (REORDER_BLOCK_FLAGS (sb->succ->succ_next->dest)
- & REORDER_BLOCK_VISITED))
- cond_type = PREDICT_THEN_NO_ELSE;
- else
- cond_type = PREDICT_NOT_THEN_NO_ELSE;
- }
- else if (cond_block_type == NO_ELSE_BLOCK)
- {
- if (! (REORDER_BLOCK_FLAGS (sb->succ->dest)
- & REORDER_BLOCK_VISITED))
- cond_type = PREDICT_NOT_THEN_NO_ELSE;
- else
- cond_type = PREDICT_THEN_NO_ELSE;
- }
- }
- else
+ edge e;
+ for (e = bb->succ; e; e = e->succ_next)
+ if (e->dest != EXIT_BLOCK_PTR
+ && e->dest->rbi->visited != trace_n
+ && (e->flags & EDGE_CAN_FALLTHRU)
+ && !(e->flags & EDGE_COMPLEX))
{
- if (cond_block_type == THEN_BLOCK)
+ if (is_preferred)
{
- if (! (REORDER_BLOCK_FLAGS (sb->succ->succ_next->dest)
- & REORDER_BLOCK_VISITED))
- cond_type = PREDICT_THEN_WITH_ELSE;
- else
- cond_type = PREDICT_ELSE;
+ /* The best edge is preferred. */
+ if (!e->dest->rbi->visited
+ || bbd[e->dest->index].start_of_trace >= 0)
+ {
+ /* The current edge E is also preferred. */
+ int freq = EDGE_FREQUENCY (e);
+ if (freq > best_freq || e->count > best_count)
+ {
+ best_freq = freq;
+ best_count = e->count;
+ best_edge = e;
+ best_bb = bb;
+ }
+ }
}
- else if (cond_block_type == ELSE_BLOCK
- && sb->succ->dest != EXIT_BLOCK_PTR)
+ else
{
- if (! (REORDER_BLOCK_FLAGS (sb->succ->dest)
- & REORDER_BLOCK_VISITED))
- cond_type = PREDICT_ELSE;
+ if (!e->dest->rbi->visited
+ || bbd[e->dest->index].start_of_trace >= 0)
+ {
+ /* The current edge E is preferred. */
+ is_preferred = true;
+ best_freq = EDGE_FREQUENCY (e);
+ best_count = e->count;
+ best_edge = e;
+ best_bb = bb;
+ }
else
- cond_type = PREDICT_THEN_WITH_ELSE;
+ {
+ int freq = EDGE_FREQUENCY (e);
+ if (!best_edge || freq > best_freq || e->count > best_count)
+ {
+ best_freq = freq;
+ best_count = e->count;
+ best_edge = e;
+ best_bb = bb;
+ }
+ }
}
}
+ bb = bb->rbi->next;
}
-
- if (rtl_dump_file)
- {
- static const char * cond_type_str [] = {"not cond jump", "predict then",
- "predict else",
- "predict then w/o else",
- "predict not then w/o else"};
- static const char * cond_block_type_str [] = {"not then or else block",
- "then block",
- "else block",
- "then w/o else block"};
-
- fprintf (rtl_dump_file, " %s (looking at %s)\n",
- cond_type_str[(int)cond_type],
- cond_block_type_str[(int)cond_block_type]);
- }
-
- /* Reflect that then block will move and we'll jump to it. */
- if (cond_block_type != THEN_BLOCK
- && (cond_type == PREDICT_ELSE
- || cond_type == PREDICT_NOT_THEN_NO_ELSE))
- {
- if (rtl_dump_file)
- fprintf (rtl_dump_file,
- " then jump from block %d to block %d\n",
- sb->index, sb->succ->dest->index);
+ while (bb != back_edge->dest);
- /* Jump to reordered then block. */
- REORDER_BLOCK_ADD_JUMP (sb) = sb->succ->dest;
- }
-
- /* Reflect that then block will jump back when we have no else. */
- if (cond_block_type != THEN_BLOCK
- && cond_type == PREDICT_NOT_THEN_NO_ELSE)
+ if (best_bb)
{
- for (ee = sb->succ->dest->succ;
- ee && ! (ee->flags & EDGE_FALLTHRU);
- ee = ee->succ_next)
- continue;
-
- if (ee && ! (GET_CODE (sb->succ->dest->end) == JUMP_INSN
- && ! simplejump_p (sb->succ->dest->end)))
+ /* Rotate the loop so that the BEST_EDGE goes out from the last block of
+ the trace. */
+ if (back_edge->dest == trace->first)
{
- REORDER_BLOCK_ADD_JUMP (sb->succ->dest) = ee->dest;
+ trace->first = best_bb->rbi->next;
}
- }
+ else
+ {
+ basic_block prev_bb;
- /* Reflect that else block will jump back. */
- if (cond_block_type == ELSE_BLOCK
- && (cond_type == PREDICT_THEN_WITH_ELSE || cond_type == PREDICT_ELSE))
- {
- last_edge=db->succ;
+ for (prev_bb = trace->first;
+ prev_bb->rbi->next != back_edge->dest;
+ prev_bb = prev_bb->rbi->next)
+ ;
+ prev_bb->rbi->next = best_bb->rbi->next;
- if (last_edge
- && last_edge->dest != EXIT_BLOCK_PTR
- && GET_CODE (last_edge->dest->head) == CODE_LABEL
- && ! (GET_CODE (db->end) == JUMP_INSN))
- {
- if (rtl_dump_file)
- fprintf (rtl_dump_file,
- " else jump from block %d to block %d\n",
- db->index, last_edge->dest->index);
+ /* Try to get rid of uncond jump to cond jump. */
+ if (prev_bb->succ && !prev_bb->succ->succ_next)
+ {
+ basic_block header = prev_bb->succ->dest;
- REORDER_BLOCK_ADD_JUMP (db) = last_edge->dest;
+ /* Duplicate HEADER if it is a small block containing cond jump
+ in the end. */
+ if (any_condjump_p (header->end) && copy_bb_p (header, 0))
+ {
+ copy_bb (header, prev_bb->succ, prev_bb, trace_n);
+ }
+ }
}
}
-
- /* This block's successor has already been reordered. This can happen
- when we reorder a chain starting at a then or else. */
- for (last_edge = db->succ;
- last_edge && ! (last_edge->flags & EDGE_FALLTHRU);
- last_edge = last_edge->succ_next)
- continue;
-
- if (last_edge
- && last_edge->dest != EXIT_BLOCK_PTR
- && (REORDER_BLOCK_FLAGS (last_edge->dest)
- & REORDER_BLOCK_VISITED))
+ else
{
- if (rtl_dump_file)
- fprintf (rtl_dump_file,
- " end of chain jump from block %d to block %d\n",
- db->index, last_edge->dest->index);
-
- REORDER_BLOCK_ADD_JUMP (db) = last_edge->dest;
+ /* We have not found suitable loop tail so do no rotation. */
+ best_bb = back_edge->src;
}
-
- dbh_insn = REORDER_BLOCK_EFF_HEAD (db);
- cebe_insn = REORDER_BLOCK_EFF_END (ceb);
- dbe_insn = REORDER_BLOCK_EFF_END (db);
-
- /* Rechain predicted block. */
- NEXT_INSN (cebe_insn) = dbh_insn;
- PREV_INSN (dbh_insn) = cebe_insn;
-
- if (db->index != n_basic_blocks - 1)
- NEXT_INSN (dbe_insn) = 0;
-
- return db;
+ best_bb->rbi->next = NULL;
+ return best_bb;
}
-
-/* Reorder blocks starting at block BB. */
+/* This function marks BB that it was visited in trace number TRACE. */
static void
-make_reorder_chain (bb)
- basic_block bb;
+mark_bb_visited (basic_block bb, int trace)
{
- edge e;
- basic_block visited_edge = NULL;
- rtx block_end;
- int probability;
-
- if (bb == EXIT_BLOCK_PTR)
- return;
-
- /* Find the most probable block. */
- e = bb->succ;
- block_end = bb->end;
- if (GET_CODE (block_end) == JUMP_INSN && condjump_p (block_end))
+ bb->rbi->visited = trace;
+ if (bbd[bb->index].heap)
{
- rtx note = find_reg_note (block_end, REG_BR_PROB, 0);
+ fibheap_delete_node (bbd[bb->index].heap, bbd[bb->index].node);
+ bbd[bb->index].heap = NULL;
+ bbd[bb->index].node = NULL;
+ }
+}
- if (note)
- probability = INTVAL (XEXP (note, 0));
- else
- probability = 0;
+/* 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 their
+ frequency is lower than EXEC_TH into traces (or count is lower than
+ COUNT_TH). 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 starting basic blocks are in *HEAP and at the end it deletes
+ *HEAP and stores starting points for the next round into new *HEAP. */
- if (probability >= REG_BR_PROB_BASE / 2)
- e = bb->succ->succ_next;
- }
+static void
+find_traces_1_round (int branch_th, int exec_th, gcov_type count_th,
+ struct trace *traces, int *n_traces, int round,
+ fibheap_t *heap)
+{
+ /* Heap for discarded basic blocks which are possible starting points for
+ the next round. */
+ fibheap_t new_heap = fibheap_new ();
- /* Add chosen successor to chain and recurse on it. */
- if (e && e->dest != EXIT_BLOCK_PTR
- && e->dest != e->src
- && (! (REORDER_BLOCK_FLAGS (e->dest) & REORDER_BLOCK_VISITED)
- || (REORDER_BLOCK_FLAGS (e->dest) == REORDER_BLOCK_HEAD)))
+ while (!fibheap_empty (*heap))
{
- if (! (REORDER_BLOCK_FLAGS (bb) & REORDER_BLOCK_VISITED))
- {
- REORDER_BLOCK_FLAGS (bb) |= REORDER_BLOCK_HEAD;
- REORDER_BLOCK_INDEX (bb) = reorder_index++;
- REORDER_BLOCK_FLAGS (bb) |= REORDER_BLOCK_VISITED;
- }
+ basic_block bb;
+ struct trace *trace;
+ edge best_edge, e;
+ fibheapkey_t key;
- if (REORDER_BLOCK_FLAGS (e->dest) & REORDER_BLOCK_VISITED)
- REORDER_BLOCK_FLAGS (e->dest) &= ~REORDER_BLOCK_HEAD;
-
- REORDER_BLOCK_SUCC (bb) = e;
+ bb = fibheap_extract_min (*heap);
+ bbd[bb->index].heap = NULL;
+ bbd[bb->index].node = NULL;
- visited_edge = e->dest;
-
- reorder_last_visited = chain_reorder_blocks (e, bb);
+ if (rtl_dump_file)
+ fprintf (rtl_dump_file, "Getting bb %d\n", bb->index);
- if (e->dest
- && ! (REORDER_BLOCK_FLAGS (e->dest)
- & REORDER_BLOCK_VISITED))
- make_reorder_chain (e->dest);
- }
- else
- {
- if (! (REORDER_BLOCK_FLAGS (bb) & REORDER_BLOCK_VISITED))
+ /* If the BB's frequency is too low send BB to the next round. */
+ if (round < N_ROUNDS - 1
+ && (bb->frequency < exec_th || bb->count < count_th
+ || probably_never_executed_bb_p (bb)))
{
- REORDER_BLOCK_INDEX (bb) = reorder_index++;
- REORDER_BLOCK_FLAGS (bb) |= REORDER_BLOCK_VISITED;
- }
- }
-
- /* Recurse on the successors. */
- for (e = bb->succ; e; e = e->succ_next)
- {
- if (e->dest && e->dest == EXIT_BLOCK_PTR)
- continue;
+ int key = bb_to_key (bb);
+ bbd[bb->index].heap = new_heap;
+ bbd[bb->index].node = fibheap_insert (new_heap, key, bb);
- if (e->dest
- && e->dest != e->src
- && e->dest != visited_edge
- && ! (REORDER_BLOCK_FLAGS (e->dest)
- & REORDER_BLOCK_VISITED))
- {
- reorder_last_visited
- = chain_reorder_blocks (e, reorder_last_visited);
- make_reorder_chain (e->dest);
+ if (rtl_dump_file)
+ fprintf (rtl_dump_file,
+ " Possible start point of next round: %d (key: %d)\n",
+ bb->index, key);
+ continue;
}
- }
-}
-
-/* Fixup jumps and labels after reordering basic blocks. */
+ trace = traces + *n_traces;
+ trace->first = bb;
+ trace->round = round;
+ trace->length = 0;
+ (*n_traces)++;
-static void
-fixup_reorder_chain ()
-{
- int i, j;
- rtx insn;
- int orig_num_blocks = n_basic_blocks;
-
- /* Set the new last insn. */
- {
- int max_val = 0;
- int max_index = 0;
- for (j = 0; j < n_basic_blocks; j++)
- {
- int val = REORDER_BLOCK_INDEX (BASIC_BLOCK (j));
- if (val > max_val)
- {
- max_val = val;
- max_index = j;
- }
- }
- insn = REORDER_BLOCK_EFF_END (BASIC_BLOCK (max_index));
- NEXT_INSN (insn) = NULL_RTX;
- set_last_insn (insn);
- }
-
- /* Add jumps and labels to fixup blocks. */
- for (i = 0; i < orig_num_blocks; i++)
- {
- int need_block = 0;
- basic_block bbi = BASIC_BLOCK (i);
- if (REORDER_BLOCK_ADD_JUMP (bbi))
+ do
{
- rtx label_insn, jump_insn, barrier_insn;
+ int prob, freq;
- if (GET_CODE (REORDER_BLOCK_ADD_JUMP (bbi)->head) == CODE_LABEL)
- label_insn = REORDER_BLOCK_ADD_JUMP (bbi)->head;
- else
- {
- rtx new_label = gen_label_rtx ();
- label_insn = emit_label_before (new_label,
- REORDER_BLOCK_ADD_JUMP (bbi)->head);
- REORDER_BLOCK_ADD_JUMP (bbi)->head = label_insn;
- }
+ /* The probability and frequency of the best edge. */
+ int best_prob = INT_MIN / 2;
+ int best_freq = INT_MIN / 2;
- if (GET_CODE (bbi->end) != JUMP_INSN)
- {
- jump_insn = emit_jump_insn_after (gen_jump (label_insn),
- bbi->end);
- bbi->end = jump_insn;
- need_block = 0;
- }
- else
- {
- jump_insn = emit_jump_insn_after (gen_jump (label_insn),
- REORDER_BLOCK_EFF_END (bbi));
- need_block = 1;
- }
+ best_edge = NULL;
+ mark_bb_visited (bb, *n_traces);
+ trace->length++;
- JUMP_LABEL (jump_insn) = label_insn;
- ++LABEL_NUSES (label_insn);
- barrier_insn = emit_barrier_after (jump_insn);
+ if (rtl_dump_file)
+ fprintf (rtl_dump_file, "Basic block %d was visited in trace %d\n",
+ bb->index, *n_traces - 1);
- /* Add block for jump. Typically this is when a then is not
- predicted and we are jumping to the moved then block. */
- if (need_block)
+ /* Select the successor that will be placed after BB. */
+ for (e = bb->succ; e; e = e->succ_next)
{
- basic_block nb;
-
- VARRAY_GROW (basic_block_info, ++n_basic_blocks);
- create_basic_block (n_basic_blocks - 1, jump_insn,
- jump_insn, NULL);
- nb = BASIC_BLOCK (n_basic_blocks - 1);
- nb->global_live_at_start
- = OBSTACK_ALLOC_REG_SET (function_obstack);
- nb->global_live_at_end
- = OBSTACK_ALLOC_REG_SET (function_obstack);
-
- COPY_REG_SET (nb->global_live_at_start,
- bbi->global_live_at_start);
- COPY_REG_SET (nb->global_live_at_end,
- bbi->global_live_at_start);
- BASIC_BLOCK (nb->index)->local_set = 0;
-
- nb->aux = xcalloc (1, sizeof (struct reorder_block_def));
- REORDER_BLOCK_INDEX (nb) = REORDER_BLOCK_INDEX (bbi) + 1;
- /* Relink to new block. */
- nb->succ = bbi->succ;
- nb->succ->src = nb;
-
- make_edge (NULL, bbi, nb, 0);
- bbi->succ->succ_next
- = bbi->succ->succ_next->succ_next;
- nb->succ->succ_next = 0;
- /* Fix reorder block index to reflect new block. */
- for (j = 0; j < n_basic_blocks - 1; j++)
- {
- basic_block bbj = BASIC_BLOCK (j);
- if (REORDER_BLOCK_INDEX (bbj)
- >= REORDER_BLOCK_INDEX (bbi) + 1)
- REORDER_BLOCK_INDEX (bbj)++;
- }
- REORDER_BLOCK_SCOPE (nb) = REORDER_BLOCK_SCOPE (bbi);
- REORDER_BLOCK_EFF_HEAD (nb) = nb->head;
- REORDER_BLOCK_EFF_END (nb) = barrier_insn;
- }
- else
- REORDER_BLOCK_EFF_END (bbi) = barrier_insn;
- }
- }
-}
+ if (e->flags & EDGE_FAKE)
+ abort ();
+ if (e->dest == EXIT_BLOCK_PTR)
+ continue;
-/* Perform sanity checks on the insn chain.
- 1. Check that next/prev pointers are consistent in both the forward and
- reverse direction.
- 2. Count insns in chain, going both directions, and check if equal.
- 3. Check that get_last_insn () returns the actual end of chain. */
-#ifdef ENABLE_CHECKING
-static void
-verify_insn_chain ()
-{
- rtx x,
- prevx,
- nextx;
- int insn_cnt1,
- insn_cnt2;
-
- prevx = NULL;
- insn_cnt1 = 1;
- for (x = get_insns (); x; x = NEXT_INSN (x))
- {
- if (PREV_INSN (x) != prevx)
- {
- fprintf (stderr, "Forward traversal: insn chain corrupt.\n");
- fprintf (stderr, "previous insn:\n");
- debug_rtx (prevx);
- fprintf (stderr, "current insn:\n");
- debug_rtx (x);
- abort ();
- }
- ++insn_cnt1;
- prevx = x;
- }
+ if (e->dest->rbi->visited
+ && e->dest->rbi->visited != *n_traces)
+ continue;
- if (prevx != get_last_insn ())
- {
- fprintf (stderr, "last_insn corrupt.\n");
- abort ();
- }
+ prob = e->probability;
+ freq = EDGE_FREQUENCY (e);
- nextx = NULL;
- insn_cnt2 = 1;
- for (x = get_last_insn (); x; x = PREV_INSN (x))
- {
- if (NEXT_INSN (x) != nextx)
- {
- fprintf (stderr, "Reverse traversal: insn chain corrupt.\n");
- fprintf (stderr, "current insn:\n");
- debug_rtx (x);
- fprintf (stderr, "next insn:\n");
- debug_rtx (nextx);
- abort ();
- }
- ++insn_cnt2;
- nextx = x;
- }
+ /* Edge that cannot be fallthru or improbable or infrequent
+ successor (ie. it is unsuitable successor). */
+ if (!(e->flags & EDGE_CAN_FALLTHRU) || (e->flags & EDGE_COMPLEX)
+ || prob < branch_th || freq < exec_th || e->count < count_th)
+ continue;
- if (insn_cnt1 != insn_cnt2)
- {
- fprintf (stderr, "insn_cnt1 (%d) not equal to insn_cnt2 (%d).\n",
- insn_cnt1, insn_cnt2);
- abort ();
- }
-}
-#endif
+ if (better_edge_p (bb, e, prob, freq, best_prob, best_freq))
+ {
+ best_edge = e;
+ best_prob = prob;
+ best_freq = freq;
+ }
+ }
-static rtx
-get_next_bb_note (x)
- rtx x;
-{
- while (x)
- {
- if (GET_CODE (x) == NOTE
- && NOTE_LINE_NUMBER (x) == NOTE_INSN_BASIC_BLOCK)
- return x;
- x = NEXT_INSN (x);
- }
- return NULL;
-}
+ /* If the best destination has multiple predecessors, and can be
+ duplicated cheaper than a jump, don't allow it to be added
+ to a trace. We'll duplicate it when connecting traces. */
+ if (best_edge && best_edge->dest->pred->pred_next
+ && copy_bb_p (best_edge->dest, 0))
+ best_edge = NULL;
+ /* Add all non-selected successors to the heaps. */
+ for (e = bb->succ; e; e = e->succ_next)
+ {
+ if (e == best_edge
+ || e->dest == EXIT_BLOCK_PTR
+ || e->dest->rbi->visited)
+ continue;
-static rtx
-get_prev_bb_note (x)
- rtx x;
-{
- while (x)
- {
- if (GET_CODE (x) == NOTE
- && NOTE_LINE_NUMBER (x) == NOTE_INSN_BASIC_BLOCK)
- return x;
- x = PREV_INSN (x);
- }
- return NULL;
-}
+ key = bb_to_key (e->dest);
+ if (bbd[e->dest->index].heap)
+ {
+ /* E->DEST is already in some heap. */
+ if (key != bbd[e->dest->index].node->key)
+ {
+ if (rtl_dump_file)
+ {
+ fprintf (rtl_dump_file,
+ "Changing key for bb %d from %ld to %ld.\n",
+ e->dest->index,
+ (long) bbd[e->dest->index].node->key,
+ key);
+ }
+ fibheap_replace_key (bbd[e->dest->index].heap,
+ bbd[e->dest->index].node, key);
+ }
+ }
+ else
+ {
+ fibheap_t which_heap = *heap;
-/* Determine and record the relationships between basic blocks and
- scopes in scope tree S. */
+ prob = e->probability;
+ freq = EDGE_FREQUENCY (e);
-static void
-relate_bbs_with_scopes (s)
- scope s;
-{
- scope p;
- int i, bbi1, bbi2, bbs_spanned;
- rtx bbnote;
+ if (!(e->flags & EDGE_CAN_FALLTHRU)
+ || (e->flags & EDGE_COMPLEX)
+ || prob < branch_th || freq < exec_th
+ || e->count < count_th)
+ {
+ if (round < N_ROUNDS - 1)
+ which_heap = new_heap;
+ }
- for (p = s->inner; p; p = p->next)
- relate_bbs_with_scopes (p);
+ bbd[e->dest->index].heap = which_heap;
+ bbd[e->dest->index].node = fibheap_insert (which_heap,
+ key, e->dest);
- bbi1 = bbi2 = -1;
- bbs_spanned = 0;
+ if (rtl_dump_file)
+ {
+ fprintf (rtl_dump_file,
+ " Possible start of %s round: %d (key: %ld)\n",
+ (which_heap == new_heap) ? "next" : "this",
+ e->dest->index, (long) key);
+ }
- /* If the begin and end notes are both inside the same basic block,
- or if they are both outside of basic blocks, then we know immediately
- how they are related. Otherwise, we need to poke around to make the
- determination. */
- if (s->bb_beg != s->bb_end)
- {
- if (s->bb_beg && s->bb_end)
- {
- /* Both notes are in different bbs. This implies that all the
- basic blocks spanned by the pair of notes are contained in
- this scope. */
- bbi1 = s->bb_beg->index;
- bbi2 = s->bb_end->index;
- bbs_spanned = 1;
- }
- else if (! s->bb_beg)
- {
- /* First note is outside of a bb. If the scope spans more than
- one basic block, then they all are contained within this
- scope. Otherwise, this scope is contained within the basic
- block. */
- bbnote = get_next_bb_note (s->note_beg);
- if (! bbnote)
- abort ();
- if (NOTE_BASIC_BLOCK (bbnote) == s->bb_end)
- {
- bbs_spanned = 0;
- s->bb_beg = NOTE_BASIC_BLOCK (bbnote);
- }
- else
- {
- bbi1 = NOTE_BASIC_BLOCK (bbnote)->index;
- bbi2 = s->bb_end->index;
- s->bb_end = NULL;
- bbs_spanned = 1;
- }
- }
- else /* ! s->bb_end */
- {
- /* Second note is outside of a bb. If the scope spans more than
- one basic block, then they all are contained within this
- scope. Otherwise, this scope is contained within the basic
- block. */
- bbnote = get_prev_bb_note (s->note_end);
- if (! bbnote)
- abort ();
- if (NOTE_BASIC_BLOCK (bbnote) == s->bb_beg)
- {
- bbs_spanned = 0;
- s->bb_end = NOTE_BASIC_BLOCK (bbnote);
+ }
}
- else
+
+ if (best_edge) /* Suitable successor was found. */
{
- bbi1 = s->bb_beg->index;
- bbi2 = NOTE_BASIC_BLOCK (bbnote)->index;
- s->bb_beg = NULL;
- bbs_spanned = 1;
+ if (best_edge->dest->rbi->visited == *n_traces)
+ {
+ /* We do nothing with one basic block loops. */
+ if (best_edge->dest != bb)
+ {
+ if (EDGE_FREQUENCY (best_edge)
+ > 4 * best_edge->dest->frequency / 5)
+ {
+ /* The loop has at least 4 iterations. If the loop
+ header is not the first block of the function
+ we can rotate the loop. */
+
+ if (best_edge->dest != ENTRY_BLOCK_PTR->next_bb)
+ {
+ if (rtl_dump_file)
+ {
+ fprintf (rtl_dump_file,
+ "Rotating loop %d - %d\n",
+ best_edge->dest->index, bb->index);
+ }
+ bb->rbi->next = best_edge->dest;
+ bb = rotate_loop (best_edge, trace, *n_traces);
+ }
+ }
+ else
+ {
+ /* The loop has less than 4 iterations. */
+
+ /* Check whether there is another edge from BB. */
+ edge another_edge;
+ for (another_edge = bb->succ;
+ another_edge;
+ another_edge = another_edge->succ_next)
+ if (another_edge != best_edge)
+ break;
+
+ if (!another_edge && copy_bb_p (best_edge->dest,
+ !optimize_size))
+ {
+ bb = copy_bb (best_edge->dest, best_edge, bb,
+ *n_traces);
+ }
+ }
+ }
+
+ /* Terminate the trace. */
+ break;
+ }
+ else
+ {
+ /* Check for a situation
+
+ A
+ /|
+ B |
+ \|
+ C
+
+ where
+ EDGE_FREQUENCY (AB) + EDGE_FREQUENCY (BC)
+ >= EDGE_FREQUENCY (AC).
+ (i.e. 2 * B->frequency >= EDGE_FREQUENCY (AC) )
+ Best ordering is then A B C.
+
+ This situation is created for example by:
+
+ if (A) B;
+ C;
+
+ */
+
+ for (e = bb->succ; e; e = e->succ_next)
+ if (e != best_edge
+ && (e->flags & EDGE_CAN_FALLTHRU)
+ && !(e->flags & EDGE_COMPLEX)
+ && !e->dest->rbi->visited
+ && !e->dest->pred->pred_next
+ && e->dest->succ
+ && (e->dest->succ->flags & EDGE_CAN_FALLTHRU)
+ && !(e->dest->succ->flags & EDGE_COMPLEX)
+ && !e->dest->succ->succ_next
+ && e->dest->succ->dest == best_edge->dest
+ && 2 * e->dest->frequency >= EDGE_FREQUENCY (best_edge))
+ {
+ best_edge = e;
+ if (rtl_dump_file)
+ fprintf (rtl_dump_file, "Selecting BB %d\n",
+ best_edge->dest->index);
+ break;
+ }
+
+ bb->rbi->next = best_edge->dest;
+ bb = best_edge->dest;
+ }
}
}
- }
- else
- {
- if (s->bb_beg)
- /* Both notes are in the same bb, which implies the block
- contains this scope. */
- bbs_spanned = 0;
- else
+ while (best_edge);
+ trace->last = bb;
+ bbd[trace->first->index].start_of_trace = *n_traces - 1;
+ bbd[trace->last->index].end_of_trace = *n_traces - 1;
+
+ /* The trace is terminated so we have to recount the keys in heap
+ (some block can have a lower key because now one of its predecessors
+ is an end of the trace). */
+ for (e = bb->succ; e; e = e->succ_next)
{
- rtx x1, x2;
- /* Both notes are outside of any bbs. This implies that all the
- basic blocks spanned by the pair of notes are contained in
- this scope.
- There is a degenerate case to consider. If the notes do not
- span any basic blocks, then it is an empty scope that can
- safely be deleted or ignored. Mark these with level = -1. */
-
- x1 = get_next_bb_note (s->note_beg);
- x2 = get_prev_bb_note (s->note_end);
- if (! (x1 && x2))
- {
- s->level = -1;
- bbs_spanned = 0;
- }
- else
+ if (e->dest == EXIT_BLOCK_PTR
+ || e->dest->rbi->visited)
+ continue;
+
+ if (bbd[e->dest->index].heap)
{
- bbi1 = NOTE_BASIC_BLOCK (x1)->index;
- bbi2 = NOTE_BASIC_BLOCK (x2)->index;
- bbs_spanned = 1;
+ key = bb_to_key (e->dest);
+ if (key != bbd[e->dest->index].node->key)
+ {
+ if (rtl_dump_file)
+ {
+ fprintf (rtl_dump_file,
+ "Changing key for bb %d from %ld to %ld.\n",
+ e->dest->index,
+ (long) bbd[e->dest->index].node->key, key);
+ }
+ fibheap_replace_key (bbd[e->dest->index].heap,
+ bbd[e->dest->index].node,
+ key);
+ }
}
}
}
+ fibheap_delete (*heap);
- /* If the scope spans one or more basic blocks, we record them. We
- only record the bbs that are immediately contained within this
- scope. Note that if a scope is contained within a bb, we can tell
- by checking that bb_beg = bb_end and that they are non-null. */
- if (bbs_spanned)
- {
- int j = 0;
-
- s->num_bbs = 0;
- for (i = bbi1; i <= bbi2; i++)
- if (! REORDER_BLOCK_SCOPE (BASIC_BLOCK (i)))
- s->num_bbs++;
-
- s->bbs = xcalloc (s->num_bbs, sizeof (struct basic_block_def));
- for (i = bbi1; i <= bbi2; i++)
- {
- basic_block curr_bb = BASIC_BLOCK (i);
- if (! REORDER_BLOCK_SCOPE (curr_bb))
- {
- s->bbs[j++] = curr_bb;
- REORDER_BLOCK_SCOPE (curr_bb) = s;
- }
- }
- }
- else
- s->num_bbs = 0;
+ /* "Return" the new heap. */
+ *heap = new_heap;
}
+/* Create a duplicate of the basic block OLD_BB and redirect edge E to it, add
+ it to trace after BB, mark OLD_BB visited and update pass' data structures
+ (TRACE is a number of trace which OLD_BB is duplicated to). */
-/* Allocate and initialize a new scope structure with scope level LEVEL,
- and record the NOTE beginning the scope. */
-
-static scope
-make_new_scope (level, note)
- int level;
- rtx note;
+static basic_block
+copy_bb (basic_block old_bb, edge e, basic_block bb, int trace)
{
- scope new_scope = xcalloc (1, sizeof (struct scope_def));
- new_scope->level = level;
- new_scope->note_beg = note;
- new_scope->note_end = NULL;
- new_scope->bb_beg = NULL;
- new_scope->bb_end = NULL;
- new_scope->inner = NULL;
- new_scope->inner_last = NULL;
- new_scope->outer = NULL;
- new_scope->next = NULL;
- new_scope->num_bbs = 0;
- new_scope->bbs = NULL;
- return new_scope;
-}
-
+ basic_block new_bb;
-/* Build a forest representing the scope structure of the function.
- Return a pointer to a structure describing the forest. */
+ new_bb = cfg_layout_duplicate_bb (old_bb, e);
+ if (e->dest != new_bb)
+ abort ();
+ if (e->dest->rbi->visited)
+ abort ();
+ if (rtl_dump_file)
+ fprintf (rtl_dump_file,
+ "Duplicated bb %d (created bb %d)\n",
+ old_bb->index, new_bb->index);
+ new_bb->rbi->visited = trace;
+ new_bb->rbi->next = bb->rbi->next;
+ bb->rbi->next = new_bb;
-static void
-build_scope_forest (forest)
- scope_forest_info *forest;
-{
- rtx x;
- int level, bbi, i;
- basic_block curr_bb;
- scope root, curr_scope;
-
- forest->num_trees = 0;
- forest->trees = NULL;
- level = -1;
- root = NULL;
- curr_bb = NULL;
- bbi = 0;
- for (x = get_insns (); x; x = NEXT_INSN (x))
+ if (new_bb->index >= array_size || last_basic_block > array_size)
{
- if (bbi < n_basic_blocks && x == BASIC_BLOCK (bbi)->head)
- curr_bb = BASIC_BLOCK (bbi);
+ int i;
+ int new_size;
- if (GET_CODE (x) == NOTE)
+ new_size = MAX (last_basic_block, new_bb->index + 1);
+ new_size = GET_ARRAY_SIZE (new_size);
+ bbd = xrealloc (bbd, new_size * sizeof (bbro_basic_block_data));
+ for (i = array_size; i < new_size; i++)
{
- if (NOTE_LINE_NUMBER (x) == NOTE_INSN_BLOCK_BEG)
- {
- if (root)
- {
- scope new_scope;
- if (! curr_scope)
- abort();
- level++;
- new_scope = make_new_scope (level, x);
- new_scope->outer = curr_scope;
- new_scope->next = NULL;
- if (! curr_scope->inner)
- {
- curr_scope->inner = new_scope;
- curr_scope->inner_last = new_scope;
- }
- else
- {
- curr_scope->inner_last->next = new_scope;
- curr_scope->inner_last = new_scope;
- }
- curr_scope = curr_scope->inner_last;
- }
- else
- {
- int ntrees = forest->num_trees;
- level++;
- curr_scope = make_new_scope (level, x);
- root = curr_scope;
- if (ntrees == 0)
- forest->trees = xcalloc (1, sizeof (scope));
- else
- forest->trees = xrealloc (forest->trees,
- sizeof (scope) * (ntrees + 1));
- forest->trees[forest->num_trees++] = root;
- }
- curr_scope->bb_beg = curr_bb;
- }
- else if (NOTE_LINE_NUMBER (x) == NOTE_INSN_BLOCK_END)
- {
- curr_scope->bb_end = curr_bb;
- curr_scope->note_end = x;
- level--;
- curr_scope = curr_scope->outer;
- if (level == -1)
- root = NULL;
- }
- } /* if note */
+ bbd[i].start_of_trace = -1;
+ bbd[i].end_of_trace = -1;
+ bbd[i].heap = NULL;
+ bbd[i].node = NULL;
+ }
+ array_size = new_size;
- if (curr_bb && curr_bb->end == x)
+ if (rtl_dump_file)
{
- curr_bb = NULL;
- bbi++;
+ fprintf (rtl_dump_file,
+ "Growing the dynamic array to %d elements.\n",
+ array_size);
}
+ }
- } /* for */
-
- for (i = 0; i < forest->num_trees; i++)
- relate_bbs_with_scopes (forest->trees[i]);
+ return new_bb;
}
+/* Compute and return the key (for the heap) of the basic block BB. */
-/* Remove all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes from
- the insn chain. */
-
-static void
-remove_scope_notes ()
+static fibheapkey_t
+bb_to_key (basic_block bb)
{
- rtx x, next;
- basic_block currbb = NULL;
+ edge e;
+
+ int priority = 0;
+
+ /* Do not start in probably never executed blocks. */
+ if (probably_never_executed_bb_p (bb))
+ return BB_FREQ_MAX;
- for (x = get_insns (); x; x = next)
+ /* Prefer blocks whose predecessor is an end of some trace
+ or whose predecessor edge is EDGE_DFS_BACK. */
+ for (e = bb->pred; e; e = e->pred_next)
{
- next = NEXT_INSN (x);
- if (GET_CODE (x) == NOTE
- && NOTE_LINE_NUMBER (x) == NOTE_INSN_BASIC_BLOCK)
- currbb = NOTE_BASIC_BLOCK (x);
-
- if (GET_CODE (x) == NOTE
- && (NOTE_LINE_NUMBER (x) == NOTE_INSN_BLOCK_BEG
- || NOTE_LINE_NUMBER (x) == NOTE_INSN_BLOCK_END))
+ if ((e->src != ENTRY_BLOCK_PTR && bbd[e->src->index].end_of_trace >= 0)
+ || (e->flags & EDGE_DFS_BACK))
{
- /* Check if the scope note happens to be the end of a bb. */
- if (currbb && x == currbb->end)
- currbb->end = PREV_INSN (x);
- if (currbb && x == currbb->head)
- abort ();
+ int edge_freq = EDGE_FREQUENCY (e);
- if (PREV_INSN (x))
- {
- NEXT_INSN (PREV_INSN (x)) = next;
- PREV_INSN (next) = PREV_INSN (x);
-
- NEXT_INSN (x) = NULL;
- PREV_INSN (x) = NULL;
- }
- else
- abort ();
+ if (edge_freq > priority)
+ priority = edge_freq;
}
}
+
+ if (priority)
+ /* The block with priority should have significantly lower key. */
+ return -(100 * BB_FREQ_MAX + 100 * priority + bb->frequency);
+ return -bb->frequency;
}
+/* Return true when the edge E from basic block BB is better than the temporary
+ best edge (details are in function). The probability of edge E is PROB. The
+ frequency of the successor is FREQ. The current best probability is
+ BEST_PROB, the best frequency is BEST_FREQ.
+ The edge is considered to be equivalent when PROB does not differ much from
+ BEST_PROB; similarly for frequency. */
-/* Insert scope note pairs for a contained scope tree S after insn IP. */
-static void
-insert_intra_1 (s, ip)
- scope s;
- rtx *ip;
+static bool
+better_edge_p (basic_block bb, edge e, int prob, int freq, int best_prob,
+ int best_freq)
{
- scope p;
-
- if (NOTE_BLOCK (s->note_beg))
- {
- *ip = emit_note_after (NOTE_INSN_BLOCK_BEG, *ip);
- NOTE_BLOCK (*ip) = NOTE_BLOCK (s->note_beg);
- }
-
- for (p = s->inner; p; p = p->next)
- insert_intra_1 (p, ip);
+ bool is_better_edge;
+
+ /* The BEST_* values do not have to be best, but can be a bit smaller than
+ maximum values. */
+ int diff_prob = best_prob / 10;
+ int diff_freq = best_freq / 10;
+
+ if (prob > best_prob + diff_prob)
+ /* The edge has higher probability than the temporary best edge. */
+ is_better_edge = true;
+ else if (prob < best_prob - diff_prob)
+ /* The edge has lower probability than the temporary best edge. */
+ is_better_edge = false;
+ else if (freq < best_freq - diff_freq)
+ /* 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 > best_freq + diff_freq)
+ /* This successor has higher frequency so it is worse. */
+ is_better_edge = false;
+ else if (e->dest->prev_bb == bb)
+ /* 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 (NOTE_BLOCK (s->note_beg))
- {
- *ip = emit_note_after (NOTE_INSN_BLOCK_END, *ip);
- NOTE_BLOCK (*ip) = NOTE_BLOCK (s->note_end);
- }
+ return is_better_edge;
}
-
-/* Insert NOTE_INSN_BLOCK_END notes and NOTE_INSN_BLOCK_BEG notes for
- scopes that are contained within BB. */
+/* Connect traces in array TRACES, N_TRACES is the count of traces. */
static void
-insert_intra_bb_scope_notes (bb)
- basic_block bb;
+connect_traces (int n_traces, struct trace *traces)
{
- scope s = REORDER_BLOCK_SCOPE (bb);
- scope p;
- rtx ip;
-
- if (! s)
- return;
-
- ip = bb->head;
- if (GET_CODE (ip) == CODE_LABEL)
- ip = NEXT_INSN (ip);
+ int i;
+ bool *connected;
+ int last_trace;
+ int freq_threshold;
+ gcov_type count_threshold;
+
+ freq_threshold = max_entry_frequency * DUPLICATION_THRESHOLD / 1000;
+ if (max_entry_count < INT_MAX / 1000)
+ count_threshold = max_entry_count * DUPLICATION_THRESHOLD / 1000;
+ else
+ count_threshold = max_entry_count / 1000 * DUPLICATION_THRESHOLD;
- for (p = s->inner; p; p = p->next)
+ connected = xcalloc (n_traces, sizeof (bool));
+ last_trace = -1;
+ for (i = 0; i < n_traces; i++)
{
- if (p->bb_beg != NULL && p->bb_beg == p->bb_end && p->bb_beg == bb)
- insert_intra_1 (p, &ip);
- }
-}
-
+ int t = i;
+ int t2;
+ edge e, best;
+ int best_len;
-/* Given two consecutive basic blocks BB1 and BB2 with different scopes,
- insert NOTE_INSN_BLOCK_END notes after BB1 and NOTE_INSN_BLOCK_BEG
- notes before BB2 such that the notes are correctly balanced. If BB1 or
- BB2 is NULL, we are inserting scope notes for the first and last basic
- blocks, respectively. */
+ if (connected[t])
+ continue;
-static void
-insert_inter_bb_scope_notes (bb1, bb2)
- basic_block bb1;
- basic_block bb2;
-{
- rtx ip;
- scope com;
+ connected[t] = true;
- /* It is possible that a basic block is not contained in any scope.
- In that case, we either open or close a scope but not both. */
- if (bb1 && bb2)
- {
- scope s1 = REORDER_BLOCK_SCOPE (bb1);
- scope s2 = REORDER_BLOCK_SCOPE (bb2);
- if (! s1 && ! s2)
- return;
- if (! s1)
- bb1 = NULL;
- else if (! s2)
- bb2 = NULL;
- }
-
- /* Find common ancestor scope. */
- if (bb1 && bb2)
- {
- scope s1 = REORDER_BLOCK_SCOPE (bb1);
- scope s2 = REORDER_BLOCK_SCOPE (bb2);
- while (s1 != s2)
+ /* Find the predecessor traces. */
+ for (t2 = t; t2 > 0;)
{
- if (! (s1 && s2))
- abort ();
- if (s1->level > s2->level)
- s1 = s1->outer;
- else if (s2->level > s1->level)
- s2 = s2->outer;
- else
+ best = NULL;
+ best_len = 0;
+ for (e = traces[t2].first->pred; e; e = e->pred_next)
{
- s1 = s1->outer;
- s2 = s2->outer;
+ int si = e->src->index;
+
+ if (e->src != ENTRY_BLOCK_PTR
+ && (e->flags & EDGE_CAN_FALLTHRU)
+ && !(e->flags & EDGE_COMPLEX)
+ && bbd[si].end_of_trace >= 0
+ && !connected[bbd[si].end_of_trace]
+ && (!best
+ || e->probability > best->probability
+ || (e->probability == best->probability
+ && traces[bbd[si].end_of_trace].length > best_len)))
+ {
+ best = e;
+ best_len = traces[bbd[si].end_of_trace].length;
+ }
}
- }
- com = s1;
- }
- else
- com = NULL;
-
- /* Close scopes. */
- if (bb1)
- {
- scope s = REORDER_BLOCK_SCOPE (bb1);
- ip = REORDER_BLOCK_EFF_END (bb1);
- while (s != com)
- {
- if (NOTE_BLOCK (s->note_beg))
- {
- ip = emit_note_after (NOTE_INSN_BLOCK_END, ip);
- NOTE_BLOCK (ip) = NOTE_BLOCK (s->note_end);
+ if (best)
+ {
+ best->src->rbi->next = best->dest;
+ t2 = bbd[best->src->index].end_of_trace;
+ connected[t2] = true;
+ if (rtl_dump_file)
+ {
+ fprintf (rtl_dump_file, "Connection: %d %d\n",
+ best->src->index, best->dest->index);
+ }
}
- s = s->outer;
+ else
+ break;
}
- }
- /* Open scopes. */
- if (bb2)
- {
- scope s = REORDER_BLOCK_SCOPE (bb2);
- ip = bb2->head;
- while (s != com)
+ if (last_trace >= 0)
+ traces[last_trace].last->rbi->next = traces[t2].first;
+ last_trace = t;
+
+ /* Find the successor traces. */
+ while (1)
{
- if (NOTE_BLOCK (s->note_beg))
- {
- ip = emit_note_before (NOTE_INSN_BLOCK_BEG, ip);
- NOTE_BLOCK (ip) = NOTE_BLOCK (s->note_beg);
+ /* Find the continuation of the chain. */
+ best = NULL;
+ best_len = 0;
+ for (e = traces[t].last->succ; e; e = e->succ_next)
+ {
+ int di = e->dest->index;
+
+ if (e->dest != EXIT_BLOCK_PTR
+ && (e->flags & EDGE_CAN_FALLTHRU)
+ && !(e->flags & EDGE_COMPLEX)
+ && bbd[di].start_of_trace >= 0
+ && !connected[bbd[di].start_of_trace]
+ && (!best
+ || e->probability > best->probability
+ || (e->probability == best->probability
+ && traces[bbd[di].start_of_trace].length > best_len)))
+ {
+ best = e;
+ best_len = traces[bbd[di].start_of_trace].length;
+ }
}
- s = s->outer;
- }
- }
-}
-
-/* Rebuild all the NOTE_INSN_BLOCK_BEG and NOTE_INSN_BLOCK_END notes based
- on the scope forest and the newly reordered basic blocks. */
-
-static void
-rebuild_scope_notes (forest)
- scope_forest_info *forest;
-{
- int i;
+ if (best)
+ {
+ if (rtl_dump_file)
+ {
+ fprintf (rtl_dump_file, "Connection: %d %d\n",
+ best->src->index, best->dest->index);
+ }
+ t = bbd[best->dest->index].start_of_trace;
+ traces[last_trace].last->rbi->next = traces[t].first;
+ connected[t] = true;
+ last_trace = t;
+ }
+ else
+ {
+ /* Try to connect the traces by duplication of 1 block. */
+ edge e2;
+ basic_block next_bb = NULL;
+ bool try_copy = false;
+
+ for (e = traces[t].last->succ; e; e = e->succ_next)
+ if (e->dest != EXIT_BLOCK_PTR
+ && (e->flags & EDGE_CAN_FALLTHRU)
+ && !(e->flags & EDGE_COMPLEX)
+ && (!best || e->probability > best->probability))
+ {
+ edge best2 = NULL;
+ int best2_len = 0;
+
+ /* If the destination is a start of a trace which is only
+ one block long, then no need to search the successor
+ blocks of the trace. Accept it. */
+ if (bbd[e->dest->index].start_of_trace >= 0
+ && traces[bbd[e->dest->index].start_of_trace].length
+ == 1)
+ {
+ best = e;
+ try_copy = true;
+ continue;
+ }
+
+ for (e2 = e->dest->succ; e2; e2 = e2->succ_next)
+ {
+ int di = e2->dest->index;
+
+ if (e2->dest == EXIT_BLOCK_PTR
+ || ((e2->flags & EDGE_CAN_FALLTHRU)
+ && !(e2->flags & EDGE_COMPLEX)
+ && bbd[di].start_of_trace >= 0
+ && !connected[bbd[di].start_of_trace]
+ && (EDGE_FREQUENCY (e2) >= freq_threshold)
+ && (e2->count >= count_threshold)
+ && (!best2
+ || e2->probability > best2->probability
+ || (e2->probability == best2->probability
+ && traces[bbd[di].start_of_trace].length
+ > best2_len))))
+ {
+ best = e;
+ best2 = e2;
+ if (e2->dest != EXIT_BLOCK_PTR)
+ best2_len = traces[bbd[di].start_of_trace].length;
+ else
+ best2_len = INT_MAX;
+ next_bb = e2->dest;
+ try_copy = true;
+ }
+ }
+ }
+
+ /* Copy tiny blocks always; copy larger blocks only when the
+ edge is traversed frequently enough. */
+ if (try_copy
+ && copy_bb_p (best->dest,
+ !optimize_size
+ && EDGE_FREQUENCY (best) >= freq_threshold
+ && best->count >= count_threshold))
+ {
+ basic_block new_bb;
- if (forest->num_trees == 0)
- return;
+ if (rtl_dump_file)
+ {
+ fprintf (rtl_dump_file, "Connection: %d %d ",
+ traces[t].last->index, best->dest->index);
+ if (!next_bb)
+ fputc ('\n', rtl_dump_file);
+ else if (next_bb == EXIT_BLOCK_PTR)
+ fprintf (rtl_dump_file, "exit\n");
+ else
+ fprintf (rtl_dump_file, "%d\n", next_bb->index);
+ }
- /* Start by opening the scopes before the first basic block. */
- insert_inter_bb_scope_notes (NULL, BASIC_BLOCK (0));
+ new_bb = copy_bb (best->dest, best, traces[t].last, t);
+ traces[t].last = new_bb;
+ if (next_bb && next_bb != EXIT_BLOCK_PTR)
+ {
+ t = bbd[next_bb->index].start_of_trace;
+ traces[last_trace].last->rbi->next = traces[t].first;
+ connected[t] = true;
+ last_trace = t;
+ }
+ else
+ break; /* Stop finding the successor traces. */
+ }
+ else
+ break; /* Stop finding the successor traces. */
+ }
+ }
+ }
- /* Then, open and close scopes as needed between blocks. */
- for (i = 0; i < n_basic_blocks - 1; i++)
+ if (rtl_dump_file)
{
- basic_block bb1 = BASIC_BLOCK (i);
- basic_block bb2 = BASIC_BLOCK (i + 1);
- if (REORDER_BLOCK_SCOPE (bb1) != REORDER_BLOCK_SCOPE (bb2))
- insert_inter_bb_scope_notes (bb1, bb2);
- insert_intra_bb_scope_notes (bb1);
+ basic_block bb;
+
+ fprintf (rtl_dump_file, "Final order:\n");
+ for (bb = traces[0].first; bb; bb = bb->rbi->next)
+ fprintf (rtl_dump_file, "%d ", bb->index);
+ fprintf (rtl_dump_file, "\n");
+ fflush (rtl_dump_file);
}
- /* Finally, close the scopes after the last basic block. */
- insert_inter_bb_scope_notes (BASIC_BLOCK (n_basic_blocks - 1), NULL);
- insert_intra_bb_scope_notes (BASIC_BLOCK (n_basic_blocks - 1));
+ FREE (connected);
}
+/* Return true when BB can and should be copied. CODE_MAY_GROW is true
+ when code size is allowed to grow by duplication. */
-/* Free the storage associated with the scope tree at S. */
-
-static void
-free_scope_forest_1 (s)
- scope s;
+static bool
+copy_bb_p (basic_block bb, int code_may_grow)
{
- scope p, next;
-
- for (p = s->inner; p; p = next)
- {
- next = p->next;
- free_scope_forest_1 (p);
- }
-
- if (s->bbs)
- free (s->bbs);
- free (s);
-}
+ int size = 0;
+ int max_size = uncond_jump_length;
+ rtx insn;
+ if (!bb->frequency)
+ return false;
+ if (!bb->pred || !bb->pred->pred_next)
+ return false;
+ if (!cfg_layout_can_duplicate_bb_p (bb))
+ return false;
-/* Free the storage associated with the scope forest. */
-
-static void
-free_scope_forest (forest)
- scope_forest_info *forest;
-{
- int i;
- for (i = 0; i < forest->num_trees; i++)
- free_scope_forest_1 (forest->trees[i]);
-}
+ if (code_may_grow && maybe_hot_bb_p (bb))
+ max_size *= 8;
+ for (insn = bb->head; insn != NEXT_INSN (bb->end);
+ insn = NEXT_INSN (insn))
+ {
+ if (INSN_P (insn))
+ size += get_attr_length (insn);
+ }
-/* Visualize the scope forest. */
+ if (size <= max_size)
+ return true;
-void
-dump_scope_forest (forest)
- scope_forest_info *forest;
-{
- if (forest->num_trees == 0)
- fprintf (stderr, "\n< Empty scope forest >\n");
- else
+ if (rtl_dump_file)
{
- int i;
- fprintf (stderr, "\n< Scope forest >\n");
- for (i = 0; i < forest->num_trees; i++)
- dump_scope_forest_1 (forest->trees[i], 0);
+ fprintf (rtl_dump_file,
+ "Block %d can't be copied because its size = %d.\n",
+ bb->index, size);
}
-}
+ return false;
+}
-/* Recursive portion of dump_scope_forest. */
+/* Return the length of unconditional jump instruction. */
-static void
-dump_scope_forest_1 (s, indent)
- scope s;
- int indent;
+static int
+get_uncond_jump_length (void)
{
- scope p;
- int i;
+ rtx label, jump;
+ int length;
- if (s->bb_beg != NULL && s->bb_beg == s->bb_end
- && REORDER_BLOCK_SCOPE (s->bb_beg)
- && REORDER_BLOCK_SCOPE (s->bb_beg)->level + 1 == s->level)
- {
- fprintf (stderr, "%*s", indent, "");
- fprintf (stderr, "BB%d:\n", s->bb_beg->index);
- }
+ label = emit_label_before (gen_label_rtx (), get_insns ());
+ jump = emit_jump_insn (gen_jump (label));
- fprintf (stderr, "%*s", indent, "");
- fprintf (stderr, "{ level %d (block %p)\n", s->level,
- NOTE_BLOCK (s->note_beg));
+ length = get_attr_length (jump);
- fprintf (stderr, "%*s%s", indent, "", "bbs:");
- for (i = 0; i < s->num_bbs; i++)
- fprintf (stderr, " %d", s->bbs[i]->index);
- fprintf (stderr, "\n");
-
- for (p = s->inner; p; p = p->next)
- dump_scope_forest_1 (p, indent + 2);
-
- fprintf (stderr, "%*s", indent, "");
- fprintf (stderr, "}\n");
+ delete_insn (jump);
+ delete_insn (label);
+ return length;
}
-
-/* Reorder basic blocks. */
+/* Reorder basic blocks. The main entry point to this file. */
void
-reorder_basic_blocks ()
+reorder_basic_blocks (void)
{
- int i, j;
- struct loops loops_info;
- int num_loops;
- scope_forest_info forest;
-
- if (profile_arc_flag)
- return;
+ int n_traces;
+ int i;
+ struct trace *traces;
if (n_basic_blocks <= 1)
return;
- /* Exception edges are not currently handled. */
- for (i = 0; i < n_basic_blocks; i++)
- {
- edge e;
-
- for (e = BASIC_BLOCK (i)->succ; e && ! (e->flags & EDGE_EH);
- e = e->succ_next)
- continue;
-
- if (e && (e->flags & EDGE_EH))
- return;
- }
-
- reorder_index = 0;
-
- /* Find natural loops using the CFG. */
- num_loops = flow_loops_find (&loops_info);
-
- /* Dump loop information. */
- flow_loops_dump (&loops_info, rtl_dump_file, 0);
-
- reorder_last_visited = BASIC_BLOCK (0);
-
- for (i = 0; i < n_basic_blocks; i++)
- {
- basic_block bbi = BASIC_BLOCK (i);
- bbi->aux = xcalloc (1, sizeof (struct reorder_block_def));
- *((struct reorder_block_def *)bbi->aux) = rbd_init;
- }
-
- build_scope_forest (&forest);
- remove_scope_notes ();
-
- for (i = 0; i < n_basic_blocks; i++)
- {
- basic_block bbi = BASIC_BLOCK (i);
- REORDER_BLOCK_EFF_END (bbi)
- = skip_insns_between_block (bbi, REORDER_SKIP_AFTER);
- if (i == 0)
- REORDER_BLOCK_EFF_HEAD (bbi) = get_insns ();
- else
- {
- rtx prev_eff_end = REORDER_BLOCK_EFF_END (BASIC_BLOCK (i - 1));
- REORDER_BLOCK_EFF_HEAD (bbi) = NEXT_INSN (prev_eff_end);
- }
- }
-
- /* If we've not got epilogue in RTL, we must fallthru to the exit.
- Force the last block to be at the end. */
- /* ??? Some ABIs (e.g. MIPS) require the return insn to be at the
- end of the function for stack unwinding purposes. */
+ if ((* targetm.cannot_modify_jumps_p) ())
+ return;
-#ifndef HAVE_epilogue
-#define HAVE_epilogue 0
-#endif
+ cfg_layout_initialize ();
- if (! HAVE_epilogue)
- {
- basic_block last = BASIC_BLOCK (n_basic_blocks - 1);
- REORDER_BLOCK_INDEX (last) = n_basic_blocks - 1;
- REORDER_BLOCK_FLAGS (last) |= REORDER_BLOCK_VISITED;
- }
-
- make_reorder_chain (BASIC_BLOCK (0));
+ set_edge_can_fallthru_flag ();
+ mark_dfs_back_edges ();
- fixup_reorder_chain ();
+ /* We are estimating the length of uncond jump insn only once since the code
+ for getting the insn length always returns the minimal length now. */
+ if (uncond_jump_length == 0)
+ uncond_jump_length = get_uncond_jump_length ();
-#ifdef ENABLE_CHECKING
- verify_insn_chain ();
-#endif
-
- /* Put basic_block_info in new order. */
- for (i = 0; i < n_basic_blocks - 1; i++)
+ /* We need to know some information for each basic block. */
+ array_size = GET_ARRAY_SIZE (last_basic_block);
+ bbd = xmalloc (array_size * sizeof (bbro_basic_block_data));
+ for (i = 0; i < array_size; i++)
{
- for (j = i; i != REORDER_BLOCK_INDEX (BASIC_BLOCK (j)); j++)
- continue;
-
- if (REORDER_BLOCK_INDEX (BASIC_BLOCK (j)) == i
- && i != j)
- {
- basic_block tempbb;
- int temprbi;
- int rbi = REORDER_BLOCK_INDEX (BASIC_BLOCK (j));
-
- temprbi = BASIC_BLOCK (rbi)->index;
- BASIC_BLOCK (rbi)->index = BASIC_BLOCK (j)->index;
- BASIC_BLOCK (j)->index = temprbi;
- tempbb = BASIC_BLOCK (rbi);
- BASIC_BLOCK (rbi) = BASIC_BLOCK (j);
- BASIC_BLOCK (j) = tempbb;
- }
+ bbd[i].start_of_trace = -1;
+ bbd[i].end_of_trace = -1;
+ bbd[i].heap = NULL;
+ bbd[i].node = NULL;
}
- rebuild_scope_notes (&forest);
- free_scope_forest (&forest);
- reorder_blocks ();
-
-#ifdef ENABLE_CHECKING
- verify_flow_info ();
-#endif
+ traces = xmalloc (n_basic_blocks * sizeof (struct trace));
+ n_traces = 0;
+ find_traces (&n_traces, traces);
+ connect_traces (n_traces, traces);
+ FREE (traces);
+ FREE (bbd);
- for (i = 0; i < n_basic_blocks; i++)
- free (BASIC_BLOCK (i)->aux);
-
- /* Free loop information. */
- flow_loops_free (&loops_info);
+ if (rtl_dump_file)
+ dump_flow_info (rtl_dump_file);
+ cfg_layout_finalize ();
}
-