X-Git-Url: http://git.sourceforge.jp/view?p=pf3gnuchains%2Fgcc-fork.git;a=blobdiff_plain;f=gcc%2Ftracer.c;h=918ed7845374b9978dd4b541bc9e72d2834849e7;hp=529f9f9d84dbaebeb412873c58dd78974ca47f8b;hb=e2675c1c71dc387908f953a999b102cf85b6c29f;hpb=207c7ab2c1713db4d5f71073a1cbb7caa6266442 diff --git a/gcc/tracer.c b/gcc/tracer.c index 529f9f9d84d..918ed784537 100644 --- a/gcc/tracer.c +++ b/gcc/tracer.c @@ -1,12 +1,14 @@ /* The tracer pass for the GNU compiler. Contributed by Jan Hubicka, SuSE Labs. - Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc. + Adapted to work on GIMPLE instead of RTL by Robert Kidd, UIUC. + Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008 + Free Software Foundation, Inc. This file is part of GCC. 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) + the Free Software Foundation; either version 3, or (at your option) any later version. GCC is distributed in the hope that it will be useful, but WITHOUT @@ -15,9 +17,8 @@ License for more details. You should have received a copy of the GNU General Public License - along with GCC; see the file COPYING. If not, write to the Free - Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA - 02110-1301, USA. */ + along with GCC; see the file COPYING3. If not see + . */ /* This pass performs the tail duplication needed for superblock formation. For more information see: @@ -49,32 +50,49 @@ #include "params.h" #include "coverage.h" #include "tree-pass.h" +#include "tree-flow.h" +#include "tree-inline.h" static int count_insns (basic_block); -static bool ignore_bb_p (basic_block); -static bool better_p (edge, edge); +static bool ignore_bb_p (const_basic_block); +static bool better_p (const_edge, const_edge); static edge find_best_successor (basic_block); static edge find_best_predecessor (basic_block); static int find_trace (basic_block, basic_block *); static void tail_duplicate (void); -static void layout_superblocks (void); /* Minimal outgoing edge probability considered for superblock formation. */ static int probability_cutoff; static int branch_ratio_cutoff; -/* Return true if BB has been seen - it is connected to some trace - already. */ +/* A bit BB->index is set if BB has already been seen, i.e. it is + connected to some trace already. */ +sbitmap bb_seen; -#define seen(bb) (bb->il.rtl->visited || bb->aux) +static inline void +mark_bb_seen (basic_block bb) +{ + unsigned int size = SBITMAP_SIZE_BYTES (bb_seen) * 8; + + if ((unsigned int)bb->index >= size) + bb_seen = sbitmap_resize (bb_seen, size * 2, 0); + + SET_BIT (bb_seen, bb->index); +} + +static inline bool +bb_seen_p (basic_block bb) +{ + return TEST_BIT (bb_seen, bb->index); +} /* Return true if we should ignore the basic block for purposes of tracing. */ static bool -ignore_bb_p (basic_block bb) +ignore_bb_p (const_basic_block bb) { if (bb->index < NUM_FIXED_BLOCKS) return true; - if (!maybe_hot_bb_p (bb)) + if (optimize_bb_for_size_p (bb)) return true; return false; } @@ -84,20 +102,21 @@ ignore_bb_p (basic_block bb) static int count_insns (basic_block bb) { - rtx insn; + gimple_stmt_iterator gsi; + gimple stmt; int n = 0; - for (insn = BB_HEAD (bb); - insn != NEXT_INSN (BB_END (bb)); - insn = NEXT_INSN (insn)) - if (active_insn_p (insn)) - n++; + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + { + stmt = gsi_stmt (gsi); + n += estimate_num_insns (stmt, &eni_size_weights); + } return n; } /* Return true if E1 is more frequent than E2. */ static bool -better_p (edge e1, edge e2) +better_p (const_edge e1, const_edge e2) { if (e1->count != e2->count) return e1->count > e2->count; @@ -166,7 +185,7 @@ find_trace (basic_block bb, basic_block *trace) while ((e = find_best_predecessor (bb)) != NULL) { basic_block bb2 = e->src; - if (seen (bb2) || (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX)) + if (bb_seen_p (bb2) || (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX)) || find_best_successor (bb2) != e) break; if (dump_file) @@ -181,7 +200,7 @@ find_trace (basic_block bb, basic_block *trace) while ((e = find_best_successor (bb)) != NULL) { bb = e->dest; - if (seen (bb) || (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX)) + if (bb_seen_p (bb) || (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX)) || find_best_predecessor (bb) != e) break; if (dump_file) @@ -209,6 +228,12 @@ tail_duplicate (void) int max_dup_insns; basic_block bb; + /* Create an oversized sbitmap to reduce the chance that we need to + resize it. */ + bb_seen = sbitmap_alloc (last_basic_block * 2); + sbitmap_zero (bb_seen); + initialize_original_copy_tables (); + if (profile_info && flag_branch_probabilities) probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY_FEEDBACK); else @@ -240,7 +265,7 @@ tail_duplicate (void) while (traced_insns < cover_insns && nduplicated < max_dup_insns && !fibheap_empty (heap)) { - basic_block bb = fibheap_extract_min (heap); + basic_block bb = (basic_block) fibheap_extract_min (heap); int n, pos; if (!bb) @@ -250,7 +275,7 @@ tail_duplicate (void) if (ignore_bb_p (bb)) continue; - gcc_assert (!seen (bb)); + gcc_assert (!bb_seen_p (bb)); n = find_trace (bb, trace); @@ -276,25 +301,30 @@ tail_duplicate (void) && can_duplicate_block_p (bb2)) { edge e; - basic_block old = bb2; + basic_block copy; + + nduplicated += counts [bb2->index]; e = find_edge (bb, bb2); - nduplicated += counts [bb2->index]; - bb2 = duplicate_block (bb2, e, bb); + copy = duplicate_block (bb2, e, bb); + flush_pending_stmts (e); + + add_phi_args_after_copy (©, 1, NULL); /* Reconsider the original copy of block we've duplicated. Removing the most common predecessor may make it to be head. */ - blocks[old->index] = - fibheap_insert (heap, -old->frequency, old); + blocks[bb2->index] = + fibheap_insert (heap, -bb2->frequency, bb2); if (dump_file) fprintf (dump_file, "Duplicated %i as %i [%i]\n", - old->index, bb2->index, bb2->frequency); + bb2->index, copy->index, copy->frequency); + + bb2 = copy; } - bb->aux = bb2; - bb2->il.rtl->visited = 1; + mark_bb_seen (bb2); bb = bb2; /* In case the trace became infrequent, stop duplicating. */ if (ignore_bb_p (bb)) @@ -308,101 +338,53 @@ tail_duplicate (void) fprintf (dump_file, "Duplicated %i insns (%i%%)\n", nduplicated, nduplicated * 100 / ninsns); + free_original_copy_tables (); + sbitmap_free (bb_seen); free (blocks); free (trace); free (counts); fibheap_delete (heap); } -/* Connect the superblocks into linear sequence. At the moment we attempt to keep - the original order as much as possible, but the algorithm may be made smarter - later if needed. BB reordering pass should void most of the benefits of such - change though. */ - -static void -layout_superblocks (void) -{ - basic_block end = single_succ (ENTRY_BLOCK_PTR); - basic_block bb = end->next_bb; - - while (bb != EXIT_BLOCK_PTR) - { - edge_iterator ei; - edge e, best = NULL; - while (end->aux) - end = end->aux; - - FOR_EACH_EDGE (e, ei, end->succs) - if (e->dest != EXIT_BLOCK_PTR - && e->dest != single_succ (ENTRY_BLOCK_PTR) - && !e->dest->il.rtl->visited - && (!best || EDGE_FREQUENCY (e) > EDGE_FREQUENCY (best))) - best = e; - - if (best) - { - end->aux = best->dest; - best->dest->il.rtl->visited = 1; - } - else - for (; bb != EXIT_BLOCK_PTR; bb = bb->next_bb) - { - if (!bb->il.rtl->visited) - { - end->aux = bb; - bb->il.rtl->visited = 1; - break; - } - } - } -} - /* Main entry point to this file. */ -void +static unsigned int tracer (void) { - gcc_assert (current_ir_type () == IR_RTL_CFGLAYOUT); + gcc_assert (current_ir_type () == IR_GIMPLE); if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1) - return; + return 0; mark_dfs_back_edges (); if (dump_file) dump_flow_info (dump_file, dump_flags); + + /* Trace formation is done on the fly inside tail_duplicate */ tail_duplicate (); - layout_superblocks (); - relink_block_chain (/*stay_in_cfglayout_mode=*/true); - + + /* FIXME: We really only need to do this when we know tail duplication + has altered the CFG. */ + free_dominance_info (CDI_DOMINATORS); if (dump_file) dump_flow_info (dump_file, dump_flags); - /* Merge basic blocks in duplicated traces. */ - cleanup_cfg (CLEANUP_EXPENSIVE); + return 0; } static bool -gate_handle_tracer (void) +gate_tracer (void) { - return (optimize > 0 && flag_tracer); + return (optimize > 0 && flag_tracer && flag_reorder_blocks); } -/* Run tracer. */ -static unsigned int -rest_of_handle_tracer (void) -{ - if (dump_file) - dump_flow_info (dump_file, dump_flags); - tracer (); - reg_scan (get_insns (), max_reg_num ()); - return 0; -} - -struct tree_opt_pass pass_tracer = +struct gimple_opt_pass pass_tracer = { + { + GIMPLE_PASS, "tracer", /* name */ - gate_handle_tracer, /* gate */ - rest_of_handle_tracer, /* execute */ + gate_tracer, /* gate */ + tracer, /* execute */ NULL, /* sub */ NULL, /* next */ 0, /* static_pass_number */ @@ -411,7 +393,8 @@ struct tree_opt_pass pass_tracer = 0, /* properties_provided */ 0, /* properties_destroyed */ 0, /* todo_flags_start */ - TODO_dump_func, /* todo_flags_finish */ - 'T' /* letter */ + TODO_dump_func + | TODO_update_ssa + | TODO_verify_ssa /* todo_flags_finish */ + } }; -