From 988374dbebafea52188cb77c352c48cca81307fd Mon Sep 17 00:00:00 2001 From: Roberto Costa Date: Thu, 4 Jan 2007 17:30:12 +0000 Subject: Merge from ST 20070104 git-svn-id: https://gcc.gnu.org/svn/gcc/branches/st/cli@120446 138bc75d-0d04-0410-961f-82ee72b054a4 --- cil32-crosstool.sh | 7 +- gcc/Makefile.in | 3 +- gcc/bb-layout.c | 206 +++++++++++++++++++++++++++++ gcc/config/cil32/gen-cil.c | 41 +++--- gcc/config/cil32/t-cil32 | 4 +- gcc/config/cil32/tree-simp-cil.c | 272 ++++++++++++++++++++++++++++----------- gcc/passes.c | 1 + gcc/timevar.def | 1 + gcc/tree-pass.h | 2 + 9 files changed, 435 insertions(+), 102 deletions(-) create mode 100644 gcc/bb-layout.c diff --git a/cil32-crosstool.sh b/cil32-crosstool.sh index 73b53eb30d9..992ef1602db 100755 --- a/cil32-crosstool.sh +++ b/cil32-crosstool.sh @@ -42,13 +42,18 @@ _prepare_dirs() # Install Binutils _binutils() { - CIL_AS=${CIL_AS-`which ilasm`} + CIL_AS=${CIL_AS-`which ilasm.pnet`} CIL_LD=${CIL_LD-`which ilalink`} echo "Tools:" echo " CIL ASSEMBLER: " ${CIL_AS} echo " CIL LINKER: " ${CIL_LD} + if [ "x$CIL_AS" == x ] ; then + echo "Error I cannot find DotGnu ilasm, you can specify it by defining an env variable called CIL_AS" + exit 1 + fi + echo "" echo "Installing Bin Utils" diff --git a/gcc/Makefile.in b/gcc/Makefile.in index db1619c8c00..98522edff8a 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1016,7 +1016,7 @@ OBJS-common = \ lambda-trans.o lambda-code.o tree-loop-linear.o tree-ssa-sink.o \ tree-vrp.o tree-stdarg.o tree-cfgcleanup.o tree-ssa-reassoc.o \ tree-ssa-structalias.o tree-object-size.o \ - rtl-factoring.o + rtl-factoring.o bb-layout.o OBJS-md = $(out_object_file) @@ -1942,6 +1942,7 @@ tree-cfgcleanup.o : tree-cfgcleanup.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \ rtl-factoring.o : rtl-factoring.c $(CONFIG_H) $(SYSTEM_H) $(RTL_H) \ coretypes.h $(TM_H) $(BASIC_BLOCK_H) $(GGC_H) $(REGS_H) $(PARAMS_H) $(EXPR_H) \ addresses.h $(TM_P_H) tree-pass.h $(TREE_FLOW_H) $(TIMEVAR_H) output.h +bb-layout.o : bb-layout.c $(CONFIG_H) $(SYSTEM_H) $(TM_H) $(TREE_H) $(DIAGNOSTIC_H) $(HASHTAB_H) $(TREE_FLOW_H) langhooks.h tree-pass.h $(TIMEVAR_H) tree-tailcall.o : tree-tailcall.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \ $(RTL_H) $(TREE_H) $(TM_P_H) $(FUNCTION_H) $(TM_H) coretypes.h \ $(TREE_DUMP_H) $(DIAGNOSTIC_H) except.h tree-pass.h $(FLAGS_H) langhooks.h \ diff --git a/gcc/bb-layout.c b/gcc/bb-layout.c new file mode 100644 index 00000000000..a8636d2630a --- /dev/null +++ b/gcc/bb-layout.c @@ -0,0 +1,206 @@ +/* Layout of basic blocks. + + Copyright (C) 2006, 2007 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) any later +version. + +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 GCC; see the file COPYING. If not, write to the Free +Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA +02110-1301, USA. + +Authors: + Andrea Bona + Andrea Ornstein + Erven Rohou + Roberto Costa + +Contact information at STMicroelectronics: +Roberto Costa */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "tm.h" +#include "tree.h" +#include "diagnostic.h" +#include "hashtab.h" +#include "tree-flow.h" +#include "langhooks.h" +#include "tree-pass.h" +#include "timevar.h" +#include "assert.h" + + +/* Hijacking the BB_RTL flag. Should not be used since we do not use RTL + passes. */ +#define VISITED BB_RTL + +static inline void +visit_block (basic_block bb) +{ + bb->flags |= VISITED; +} + +static inline bool +visited (basic_block bb) +{ + return ((bb->flags & VISITED) != 0); +} + + +/* used to walk the blocks in original order, so that we can detect if the + layout changes */ +static basic_block current_bb_at_pos = NULL; + + +/* Compute a simple layout for the CFG, placing a node after all its + predecessors have been placed. When a block has two successors, we place + the one with the highest probability first. + + 'bb_order' is an array of basic_blocks, allocated by the caller and large + enough to hold all the blocks. 'num_so_far' is the number of placed blocks. +*/ +static void +compute_layout (basic_block bb, basic_block* bb_order, int* num_so_far, + bool* changed) +{ + bool all_visited; + int num_edges, i; + int edge_pos = 0, edge_dir = 1; + + visit_block (bb); + bb_order[*num_so_far] = bb; + + /* check if we change the order */ + if (current_bb_at_pos != bb) + *changed = true; + current_bb_at_pos = current_bb_at_pos->next_bb; + + ++*num_so_far; + + num_edges = EDGE_COUNT (bb->succs); + + /* Consider only the case of two edges: one edge is straightforward; more + than two is a switch, we leave it alone. */ + if (num_edges == 2) + { + edge e1 = EDGE_SUCC (bb, 0); + edge e2 = EDGE_SUCC (bb, 1); + /* In case the second edge is heavier than the first one, we invert the + scanning order. */ + if (e1->probability < e2->probability) + { + edge_pos = 1; /* start from second edge */ + edge_dir = -1; /* and go backwards */ + } + } + + for(i = 0; i < num_edges; ++i) + { + edge pred_edge; + edge_iterator pred_it; + edge e = EDGE_SUCC (bb, edge_pos); + basic_block succ = e->dest; + + edge_pos += edge_dir; + if ((succ == EXIT_BLOCK_PTR) || /* Skip EXIT block */ + (e->flags & EDGE_DFS_BACK) || /* Skip back edges */ + (visited (succ))) /* Already visited */ + continue; + + /* Check if successor has all its predecessors visited, not considering + backedges. */ + all_visited = true; + for (pred_it = ei_start (succ->preds); + ei_cond (pred_it, &pred_edge); + ei_next (&pred_it)) + { + if (pred_edge->flags & EDGE_DFS_BACK) + continue; + + if ((visited (pred_edge->src)) == 0) + { + all_visited = false; + break; + } + } + if (all_visited) + compute_layout (succ, bb_order, num_so_far, changed); + } +} + + +static unsigned int +bblayout (void) +{ + bool layout_changed = false; + int bb_num = 0; + int i; + basic_block* bb_order = NULL; + + mark_dfs_back_edges (); + bb_order = (basic_block*) alloca (n_basic_blocks * sizeof (basic_block)); + current_bb_at_pos = ENTRY_BLOCK_PTR; + compute_layout (ENTRY_BLOCK_PTR, bb_order, &bb_num, &layout_changed); + bb_order[bb_num++] = EXIT_BLOCK_PTR; + gcc_assert (bb_num == n_basic_blocks); + + if (layout_changed) + { + bb_order[0]->prev_bb = NULL; + bb_order[0]->next_bb = bb_order[1]; + for(i=1; i < bb_num-1; ++i) + { + bb_order[i]->prev_bb = bb_order[i-1]; + bb_order[i]->next_bb = bb_order[i+1]; + } + bb_order[bb_num-1]->prev_bb = bb_order[bb_num-2]; + bb_order[bb_num-1]->next_bb = NULL; + } + return 0; +} + + +static bool +bblayout_gate (void) +{ + return current_function_decl != NULL; +} + + +/* Define the parameters of the bb layout pass. */ + +struct tree_opt_pass pass_bb_layout = +{ + "bblayout", /* name */ + bblayout_gate, /* gate */ + bblayout, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + TV_BB_LAYOUT, /* tv_id */ + PROP_cfg, /* properties_required */ + 0, /* properties_provided */ + /* ??? If TER is enabled, we also kill gimple. */ + 0, /* properties_destroyed */ + 0, + 0, + 0 /* letter */ +}; + +/* + * Local variables: + * eval: (c-set-style "gnu") + * End: + */ diff --git a/gcc/config/cil32/gen-cil.c b/gcc/config/cil32/gen-cil.c index ce300186f87..65f347cefbb 100644 --- a/gcc/config/cil32/gen-cil.c +++ b/gcc/config/cil32/gen-cil.c @@ -1,6 +1,6 @@ /* Dump of the GENERIC trees in CIL. - Copyright (C) 2006 Free Software Foundation, Inc. + Copyright (C) 2006, 2007 Free Software Foundation, Inc. This file is part of GCC. @@ -94,6 +94,7 @@ static unsigned int get_string_cst_id (tree); static void dump_decl_name (FILE *, tree); static void dump_string_name (FILE *, tree); static void dump_label_name (FILE *, tree); +static void dump_entry_label_name (FILE *, basic_block); static void dump_fun_type (FILE *, tree, tree, const char *, bool); static void dump_valuetype_name (FILE *, tree); static void compute_addr_expr (FILE *, tree); @@ -2990,7 +2991,7 @@ gen_cil_node (FILE *file, tree node) gcc_assert (! DECL_BIT_FIELD (fld)); compute_addr_expr (file, obj); - if (TREE_THIS_VOLATILE (fld)) + if (TREE_THIS_VOLATILE (node)) fputs ("\n\tvolatile.", file); fputs ("\n\tldfld\t", file); dump_type (file, fld_type, true, false); @@ -3182,7 +3183,7 @@ gen_cil_modify_expr (FILE *file, tree node) compute_addr_expr (file, obj); gen_cil_node (file, rhs); mark_referenced_type (obj_type); - if (TREE_THIS_VOLATILE (fld)) + if (TREE_THIS_VOLATILE (lhs)) fputs ("\n\tvolatile.", file); fputs ("\n\tstfld\t", file); dump_type (file, fld_type, true, false); @@ -3776,7 +3777,7 @@ gen_cil_vcg (FILE *vcg_stream) fun_name, EXIT_BLOCK); fprintf (vcg_stream, "edge:{sourcename: \"%sBB%d\" targetname: \"%sBB%d\"}\n", fun_name, ENTRY_BLOCK, - fun_name, single_succ (BASIC_BLOCK (ENTRY_BLOCK))->index); + fun_name, single_succ (ENTRY_BLOCK_PTR)->index); FOR_EACH_BB (bb) { @@ -3838,11 +3839,18 @@ gen_cil_vcg (FILE *vcg_stream) for (ei = ei_start (bb->succs); ei_cond (ei, &e); ei_next (&ei)) { if (e->flags & EDGE_DFS_BACK) - fprintf (vcg_stream, "backedge: { color: red "); + fprintf (vcg_stream, "backedge: { color: red"); + else if (e->flags & EDGE_LOOP_EXIT) + fprintf (vcg_stream, "edge: { color: blue"); else - fprintf (vcg_stream, "edge: { "); + fprintf (vcg_stream, "edge: {"); + + fprintf (vcg_stream, " label:\"%d", e->probability); + if (e->flags & EDGE_LOOP_EXIT) - fprintf (vcg_stream, "color: blue label:\"loop_exit\""); + fprintf (vcg_stream, " loop_exit"); + + fprintf (vcg_stream, "\""); fprintf (vcg_stream, " sourcename: \"%sBB%d\" targetname: \"%sBB%d\" }\n", @@ -4025,7 +4033,7 @@ gen_cil_1 (FILE *stream) if (TARGET_EMIT_GIMPLE_COMMENTS) { - fprintf (stream, "\n\t/* Basic block frequency: %d */\n", + fprintf (stream, "\n\n\t/* Basic block frequency: %d */", bb->frequency * 100 / BB_FREQ_MAX); } @@ -4064,8 +4072,7 @@ gen_cil_1 (FILE *stream) /* The last part of the test (succ != bb->next_bb) is a HACK. It avoids generating a branch to the successor in case of a fallthrough. To be fixed when we have a proper layout of basic - blocks. Note that branches from COND_EXPR are still generated, - even to a fallthrough. */ + blocks. */ if ((succ->index != EXIT_BLOCK) && (succ != bb->next_bb)) { tree label = tree_block_label (succ); @@ -4077,15 +4084,16 @@ gen_cil_1 (FILE *stream) if (TARGET_EMIT_GIMPLE_COMMENTS) { - fprintf (stream, "\n\t/* Edge probabilities: "); - edge_iterator ei; edge e; + edge_iterator ei; + + fputs ("\n\t/* Edge probabilities: ", stream); FOR_EACH_EDGE (e, ei, bb->succs) { dump_entry_label_name (stream, e->dest); fprintf (stream, ": %d ", e->probability * 100 / REG_BR_PROB_BASE); } - fprintf (stream, "*/"); + fputs ("*/", stream); } } @@ -4190,10 +4198,6 @@ gen_cil_init (void) fputs ("\n.assembly '_C_MONO_ASSEMBLY' {}", stream); fputs ("\n.module ''", stream); - if (TARGET_EMIT_EXTERNAL_ASSEMBLY) - fputs ("\n.class public '_C_MONO_MODULE'" - "\n{", stream); - if (TARGET_OPENSYSTEMC) fputs ("\n.custom instance " "void ['OpenSystem.C']'OpenSystem.C'.ModuleAttribute::.ctor() " @@ -4247,9 +4251,6 @@ gen_cil_fini (void) VARRAY_CLEAR (referenced_strings); pointer_set_destroy (referenced_string_ptrs); - if (TARGET_EMIT_EXTERNAL_ASSEMBLY) - fputs ("\n} // _C_MONO_MODULE\n", stream); - /* There may be distinct tree types that correspond to identical types. In order not to slow down mark_referenced_type(...) function (which may typically be called several times for the same type), insertion diff --git a/gcc/config/cil32/t-cil32 b/gcc/config/cil32/t-cil32 index 78bb2c5c78c..4467433aabb 100644 --- a/gcc/config/cil32/t-cil32 +++ b/gcc/config/cil32/t-cil32 @@ -1,6 +1,6 @@ # Hi emacs, use Makefile syntax mode. -*-mode: Makefile; -*- -# Copyright (C) 2006 Free Software Foundation, Inc. +# Copyright (C) 2006, 2007 Free Software Foundation, Inc. # # This file is part of GCC. # @@ -30,7 +30,7 @@ gen-cil.o: $(srcdir)/config/cil32/gen-cil.c $(srcdir)/config/cil32/gen-cil.h \ - $(srcdir)/config/cil32/tree-simp-cil.h gt-gen-cil.h\ + $(srcdir)/config/cil32/tree-simp-cil.h gt-gen-cil.h \ $(CONFIG_H) $(SYSTEM_H) \ $(TREE_H) $(DIAGNOSTIC_H) real.h $(HASHTAB_H) $(TREE_FLOW_H) \ $(TM_H) coretypes.h tree-iterator.h tree-chrec.h langhooks.h tree-pass.h diff --git a/gcc/config/cil32/tree-simp-cil.c b/gcc/config/cil32/tree-simp-cil.c index 388aeeee4c9..87dcaca7de0 100644 --- a/gcc/config/cil32/tree-simp-cil.c +++ b/gcc/config/cil32/tree-simp-cil.c @@ -1,6 +1,6 @@ /* Simplify GENERIC trees before CIL emission. - Copyright (C) 2006 Free Software Foundation, Inc. + Copyright (C) 2006, 2007 Free Software Foundation, Inc. This file is part of GCC. @@ -193,6 +193,7 @@ static bool is_copy_required (tree); static bool mostly_zeros_p (tree); static bool all_zeros_p (tree); static void simp_cond_stmt (block_stmt_iterator, tree); +static void rescale_out_edge_probabilities (basic_block, int); static void simp_switch (block_stmt_iterator *, tree *); static void simp_trivial_switch (block_stmt_iterator *, tree *); static void simp_builtin_call (block_stmt_iterator, tree); @@ -304,7 +305,7 @@ simp_cil_node (block_stmt_iterator *bsi, tree *node_ptr) tree node = *node_ptr; if (node == NULL_TREE) - return; /* ER: was spc */ + return; switch (TREE_CODE (node)) { @@ -604,7 +605,7 @@ simp_cond_stmt (block_stmt_iterator bsi, tree node) { basic_block bb = bb_for_stmt (bsi_stmt (bsi)); tree cond_expr, then_expr; - enum tree_code cond_code; + enum tree_code cond_code, rev_code; tree cond_type; /* The condition targets are lowered in gimplify.c, we should never have @@ -616,28 +617,20 @@ simp_cond_stmt (block_stmt_iterator bsi, tree node) cond_expr = COND_EXPR_COND (node); then_expr = COND_EXPR_THEN (node); - cond_code = TREE_CODE (cond_expr); - /* Do something only for a set of handled conditions */ - if (cond_code != LE_EXPR - && cond_code != LT_EXPR - && cond_code != GE_EXPR - && cond_code != GT_EXPR - && cond_code != EQ_EXPR - && cond_code != NE_EXPR - && cond_code != UNORDERED_EXPR - && cond_code != ORDERED_EXPR) + /* Nothing to do if the condition is not a comparison */ + if (! COMPARISON_CLASS_P (cond_expr)) return; + /* Do something only when the condition can be inverted */ + cond_code = TREE_CODE (cond_expr); cond_type = TREE_TYPE (TREE_OPERAND (cond_expr, 0)); - if ((INTEGRAL_TYPE_P (cond_type) || POINTER_TYPE_P (cond_type)) + rev_code = invert_tree_comparison (cond_code, FLOAT_TYPE_P (cond_type)); + if (rev_code != ERROR_MARK && label_to_block (GOTO_DESTINATION (then_expr)) == bb->next_bb) { - enum tree_code rev_code = invert_tree_comparison (cond_code, false); edge e; - gcc_assert (rev_code != ERROR_MARK); - /* Invert the targets of the COND_EXPR */ TREE_SET_CODE (COND_EXPR_COND (node), rev_code); COND_EXPR_THEN (node) = COND_EXPR_ELSE (node); @@ -651,6 +644,35 @@ simp_cond_stmt (block_stmt_iterator bsi, tree node) } } +/* Rescale the probabilities of the out-edge of basic block BB + by assuming TOT_PROB as the sum of the current probabilities. */ + +static void +rescale_out_edge_probabilities (basic_block bb, int tot_prob) +{ + edge e; + edge_iterator ei; + + if (tot_prob <= 0) + { + EDGE_SUCC (bb, 0)->probability = REG_BR_PROB_BASE; + ei = ei_start (bb->succs); + ei_next (&ei); + for (; (e = ei_safe_edge (ei)); ei_next (&ei)) + e->probability = 0; + } + else if (tot_prob != REG_BR_PROB_BASE) + { + int scale = (65536 * REG_BR_PROB_BASE) / tot_prob; + + FOR_EACH_EDGE (e, ei, bb->succs) + { + e->probability = (e->probability * scale) / 65536; + gcc_assert (e->probability <= REG_BR_PROB_BASE); + } + } +} + /* Expand the SWITCH_EXPR pointed by NODE_PTR by inserting compare trees. The expansion occurs only if heuristics say it is profitable; the current heuristic is based on case label @@ -681,6 +703,7 @@ simp_switch (block_stmt_iterator *bsi, tree *node_ptr) tree label1_decl, label2_decl, label1, label2; edge_iterator ei; edge e1, e2, tmp_edge; + int bb1_probs, bb2_probs; /* The switch body is lowered in gimplify.c, we should never have switches with a non-NULL SWITCH_BODY here. */ @@ -688,8 +711,8 @@ simp_switch (block_stmt_iterator *bsi, tree *node_ptr) vec_len = TREE_VEC_LENGTH (vec); - /* Switches made of one case are always separately (they are always - transformed into if ... then ... else ... */ + /* Switches made of one case are always separately handled + (they are transformed into if ... then ... else ...). */ if (vec_len == 2) { simp_trivial_switch (bsi, node_ptr); @@ -796,8 +819,41 @@ simp_switch (block_stmt_iterator *bsi, tree *node_ptr) if (! sw1_last_int_cst) sw1_last_int_cst = CASE_LOW (TREE_VEC_ELT (vec, sw1_last)); - /* Build a COND_EXPR, replace the switch with the COND_EXPR */ + /* For each out-going edge of the original switch basic block, + mark whether it is going to be replicated in the first newly + created switch block, in the second, or in both. + This is needed in order to update counts, frequencies and + probabilities. + In order to do that, use the following edge flags: + EDGE_FALSE_VALUE: 1st block + EDGE_TRUE_VALUE: 2nd block + This is fine because these edges are removed later on. */ bb_orig_sw = bb_for_stmt (bsi_stmt (*bsi)); + for (i = 0; i < vec_len; ++i) + { + tree elt = TREE_VEC_ELT (vec, i); + basic_block target_bb = label_to_block (CASE_LABEL (elt)); + edge e = find_edge (bb_orig_sw, target_bb); + + gcc_assert (e); + e->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE); + } + for (i = 0; i < vec_len; ++i) + { + tree elt = TREE_VEC_ELT (vec, i); + basic_block target_bb = label_to_block (CASE_LABEL (elt)); + edge e = find_edge (bb_orig_sw, target_bb); + + gcc_assert (e); + if (i <= sw1_last) + e->flags |= EDGE_FALSE_VALUE; + else if (i != vec_len - 1) + e->flags |= EDGE_TRUE_VALUE; + else + e->flags |= (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE); + } + + /* Build a COND_EXPR, replace the switch with the COND_EXPR */ label1_decl = create_artificial_label (); label2_decl = create_artificial_label (); cmp_stmt = build3 (COND_EXPR, void_type_node, @@ -817,7 +873,6 @@ simp_switch (block_stmt_iterator *bsi, tree *node_ptr) /* Generate a basic block with the first switch */ bb1 = create_empty_bb (bb_orig_sw); - bb1->count = bb_orig_sw->count / 2; label1 = build1 (LABEL_EXPR, void_type_node, label1_decl); vec1 = make_tree_vec (sw1_last + 2); sw1_stmt = build3 (SWITCH_EXPR, TREE_TYPE (node), @@ -829,7 +884,6 @@ simp_switch (block_stmt_iterator *bsi, tree *node_ptr) /* Generate a basic block with the second switch */ bb2 = create_empty_bb (bb1); - bb2->count = bb_orig_sw->count - bb1->count; label2 = build1 (LABEL_EXPR, void_type_node, label2_decl); vec2 = make_tree_vec (vec_len - sw1_last - 1); sw2_stmt = build3 (SWITCH_EXPR, TREE_TYPE (node), @@ -845,29 +899,29 @@ simp_switch (block_stmt_iterator *bsi, tree *node_ptr) { tree elt = TREE_VEC_ELT (vec, i); basic_block target_bb = label_to_block (CASE_LABEL (elt)); - edge e = make_edge (bb1, target_bb, 0); + edge e = find_edge (bb1, target_bb); if (!e) - e = find_edge (bb1, target_bb); + { + edge old_e = find_edge (bb_orig_sw, target_bb); - e->count = 0; - e->probability = 0; + e = make_edge (bb1, target_bb, 0); + gcc_assert (e); + gcc_assert (old_e && (old_e->flags & EDGE_FALSE_VALUE) != 0); + if (old_e->flags & EDGE_TRUE_VALUE) + { + e->count = old_e->count / 2; + e->probability = old_e->probability / 2; + } + else + { + e->count = old_e->count; + e->probability = old_e->probability; + } + } TREE_VEC_ELT (vec1, i) = elt; } - { - tree elt = TREE_VEC_ELT (vec, vec_len - 1); - basic_block target_bb = label_to_block (CASE_LABEL (elt)); - edge e = make_edge (bb1, target_bb, 0); - - if (!e) - e = find_edge (bb1, target_bb); - - e->count = bb1->count; - e->probability = REG_BR_PROB_BASE; - - TREE_VEC_ELT (vec1, sw1_last + 1) = elt; - } /* Build the case labels for the 2nd new switch and the out-edges of its basic block. */ @@ -875,36 +929,94 @@ simp_switch (block_stmt_iterator *bsi, tree *node_ptr) { tree elt = TREE_VEC_ELT (vec, i); basic_block target_bb = label_to_block (CASE_LABEL (elt)); - edge e = make_edge (bb2, target_bb, 0); + edge e = find_edge (bb2, target_bb); if (!e) - e = find_edge (bb2, target_bb); + { + edge old_e = find_edge (bb_orig_sw, target_bb); - e->count = 0; - e->probability = 0; + e = make_edge (bb2, target_bb, 0); + gcc_assert (e); + gcc_assert (old_e && (old_e->flags & EDGE_TRUE_VALUE) != 0); + if (old_e->flags & EDGE_FALSE_VALUE) + { + e->count = old_e->count - old_e->count / 2; + e->probability = old_e->probability - old_e->probability / 2; + } + else + { + e->count = old_e->count; + e->probability = old_e->probability; + } + } TREE_VEC_ELT (vec2, i - sw1_last - 1) = elt; } + + /* Build the default labels for both new switches and the out-edges + of their basic blocks. */ { tree elt = TREE_VEC_ELT (vec, vec_len - 1); - basic_block target_bb = label_to_block (CASE_LABEL (elt)); - edge e = make_edge (bb2, target_bb, 0); tree new_elt; + basic_block target_bb = label_to_block (CASE_LABEL (elt)); + edge e1 = find_edge (bb1, target_bb); + edge e2 = find_edge (bb2, target_bb); + edge old_e = NULL; - if (!e) - e = find_edge (bb2, target_bb); + if (!e1 || !e2) + { + old_e = find_edge (bb_orig_sw, target_bb); + gcc_assert (old_e + && (old_e->flags & EDGE_TRUE_VALUE) != 0 + && (old_e->flags & EDGE_FALSE_VALUE) != 0); + } + + if (!e1) + { + e1 = make_edge (bb1, target_bb, 0); + gcc_assert (e1); + e1->count = old_e->count / 2; + e1->probability = old_e->probability / 2; + } + + if (!e2) + { + e2 = make_edge (bb2, target_bb, 0); + gcc_assert (e2); + e2->count = old_e->count - old_e->count / 2; + e2->probability = old_e->probability - old_e->probability / 2; + } - e->count = bb2->count; - e->probability = REG_BR_PROB_BASE; + TREE_VEC_ELT (vec1, sw1_last + 1) = elt; /* Duplicate this case label expression, since it is used in the first switch. */ new_elt = build3 (CASE_LABEL_EXPR, TREE_TYPE (elt), CASE_LOW (elt), CASE_HIGH (elt), CASE_LABEL (elt)); - TREE_VEC_ELT (vec2, vec_len - sw1_last - 2) = new_elt; } + /* Re-scale probabilities of the out-going edges of the new blocks + and compute counts of such blocks. */ + bb1_probs = 0; + bb1->count = 0; + FOR_EACH_EDGE (tmp_edge, ei, bb1->succs) + { + bb1->count += tmp_edge->count; + bb1_probs += tmp_edge->probability; + } + rescale_out_edge_probabilities (bb1, bb1_probs); + + bb2_probs = 0; + bb2->count = 0; + FOR_EACH_EDGE (tmp_edge, ei, bb2->succs) + { + bb2->count += tmp_edge->count; + bb2_probs += tmp_edge->probability; + } + rescale_out_edge_probabilities (bb2, bb2_probs); + gcc_assert (bb1->count + bb2->count == bb_orig_sw->count); + /* Update out-edges of original switch basic block */ for (ei = ei_start (bb_orig_sw->succs); (tmp_edge = ei_safe_edge (ei)); ) { @@ -912,19 +1024,16 @@ simp_switch (block_stmt_iterator *bsi, tree *node_ptr) } e1 = unchecked_make_edge (bb_orig_sw, bb1, EDGE_FALSE_VALUE); e2 = unchecked_make_edge (bb_orig_sw, bb2, EDGE_TRUE_VALUE); - e1->probability = REG_BR_PROB_BASE / 2; + if (bb1_probs + bb2_probs > 0) + e1->probability = ((bb1_probs * 256 * REG_BR_PROB_BASE) / + (bb1_probs + bb2_probs)) / 256; + else + e1->probability = REG_BR_PROB_BASE / 2; e1->count = bb1->count; e2->probability = REG_BR_PROB_BASE - e1->probability; e2->count = bb2->count; - - /* TODO: probabilities of the out-edges of the new basic blocks - currently do not reflect those of the out-edges of the - original switch basic block. - In order to "preserve" them, the new edges should be given - probabilities based on the original edges, but normalized. */ - - /* TODO: basic block frequencies are not updated, this makes - the profile information sanity check to fail. */ + bb1->frequency = EDGE_FREQUENCY (e1); + bb2->frequency = EDGE_FREQUENCY (e2); } /* Expand the SWITCH_EXPR pointed by NODE_PTR, composed of just @@ -1188,7 +1297,7 @@ simp_abs (block_stmt_iterator *bsi, tree *node_ptr) tree sel_var; tree orig_stmt, cmp_stmt, asn_op_stmt, asn_neg_stmt; basic_block bb_comp, bb_neg, bb_sel; - edge tmp_edge; + edge tmp_edge, edge_comp_neg, edge_comp_sel; block_stmt_iterator tmp_bsi; gcov_type count; @@ -1219,11 +1328,16 @@ simp_abs (block_stmt_iterator *bsi, tree *node_ptr) tmp_edge = split_block (bb_comp, cmp_stmt); bb_sel = tmp_edge->dest; bb_sel->count = count; + bb_sel->frequency = bb_comp->frequency; remove_edge (tmp_edge); bb_neg = create_empty_bb (bb_comp); bb_neg->count = count / 2; - unchecked_make_edge (bb_comp, bb_neg, EDGE_FALSE_VALUE); + edge_comp_neg = unchecked_make_edge (bb_comp, bb_neg, EDGE_FALSE_VALUE); + edge_comp_neg->probability = REG_BR_PROB_BASE / 2; + edge_comp_sel = unchecked_make_edge (bb_comp, bb_sel, EDGE_TRUE_VALUE); + edge_comp_sel->probability = REG_BR_PROB_BASE - edge_comp_neg->probability; make_single_succ_edge (bb_neg, bb_sel, EDGE_FALLTHRU); + bb_neg->frequency = EDGE_FREQUENCY (edge_comp_neg); /* Insert labels and statements into neg bb */ label_neg = build1 (LABEL_EXPR, void_type_node, label_decl_neg); @@ -1270,7 +1384,7 @@ simp_min_max (block_stmt_iterator *bsi, tree *node_ptr) tree sel_var; tree orig_stmt, cmp_stmt, asn_op0_stmt, asn_op1_stmt; basic_block bb_comp, bb_op0, bb_op1, bb_sel; - edge tmp_edge; + edge tmp_edge, edge_comp_op0, edge_comp_op1; block_stmt_iterator tmp_bsi; gcov_type count; @@ -1317,15 +1431,20 @@ simp_min_max (block_stmt_iterator *bsi, tree *node_ptr) tmp_edge = split_block (bb_comp, cmp_stmt); bb_sel = tmp_edge->dest; bb_sel->count = count; + bb_sel->frequency = bb_comp->frequency; remove_edge (tmp_edge); bb_op0 = create_empty_bb (bb_comp); bb_op1 = create_empty_bb (bb_op0); bb_op0->count = count / 2; bb_op1->count = count - bb_op0->count; - unchecked_make_edge (bb_comp, bb_op0, EDGE_TRUE_VALUE); + edge_comp_op0 = unchecked_make_edge (bb_comp, bb_op0, EDGE_TRUE_VALUE); + edge_comp_op0->probability = REG_BR_PROB_BASE / 2; make_single_succ_edge (bb_op0, bb_sel, EDGE_FALLTHRU); - unchecked_make_edge (bb_comp, bb_op1, EDGE_FALSE_VALUE); + edge_comp_op1 = unchecked_make_edge (bb_comp, bb_op1, EDGE_FALSE_VALUE); + edge_comp_op1->probability = REG_BR_PROB_BASE - edge_comp_op0->probability; make_single_succ_edge (bb_op1, bb_sel, EDGE_FALLTHRU); + bb_op0->frequency = EDGE_FREQUENCY (edge_comp_op0); + bb_op1->frequency = EDGE_FREQUENCY (edge_comp_op1); /* Insert labels and statements into op0 bb */ sel_var = create_tmp_var (TREE_TYPE (node), "cilsimp"); @@ -1373,7 +1492,7 @@ simp_cond_expr (block_stmt_iterator *bsi, tree *node_ptr) tree sel_var; tree orig_stmt, cmp_stmt, asn_then_stmt, asn_else_stmt; basic_block bb_comp, bb_then, bb_else, bb_sel; - edge tmp_edge; + edge tmp_edge, edge_comp_then, edge_comp_else; block_stmt_iterator tmp_bsi; gcov_type count; @@ -1419,15 +1538,20 @@ simp_cond_expr (block_stmt_iterator *bsi, tree *node_ptr) tmp_edge = split_block (bb_comp, cmp_stmt); bb_sel = tmp_edge->dest; bb_sel->count = count; + bb_sel->frequency = bb_comp->frequency; remove_edge (tmp_edge); bb_then = create_empty_bb (bb_comp); bb_else = create_empty_bb (bb_then); bb_then->count = count / 2; bb_else->count = count - bb_then->count; - unchecked_make_edge (bb_comp, bb_then, EDGE_TRUE_VALUE); + edge_comp_then = unchecked_make_edge (bb_comp, bb_then, EDGE_TRUE_VALUE); + edge_comp_then->probability = REG_BR_PROB_BASE / 2; make_single_succ_edge (bb_then, bb_sel, EDGE_FALLTHRU); - unchecked_make_edge (bb_comp, bb_else, EDGE_FALSE_VALUE); + edge_comp_else = unchecked_make_edge (bb_comp, bb_else, EDGE_FALSE_VALUE); + edge_comp_else->probability = REG_BR_PROB_BASE - edge_comp_then->probability; make_single_succ_edge (bb_else, bb_sel, EDGE_FALLTHRU); + bb_then->frequency = EDGE_FREQUENCY (edge_comp_then); + bb_else->frequency = EDGE_FREQUENCY (edge_comp_else); /* Insert labels and statements into then bb */ sel_var = create_tmp_var (TREE_TYPE (node), "cilsimp"); @@ -1584,8 +1708,7 @@ simp_ltgt_expr (block_stmt_iterator *bsi, tree *node_ptr) by inserting shifts and bit operations. BSI points to the iterator of the statement that contains *NODE_PTR (in order to allow insertion of new statements). - BSI is passed by reference because instructions are inserted, - new basic blocks created... + BSI is passed by reference because instructions are inserted. NODE is passed by reference because simplification requires replacing the node. */ @@ -2950,13 +3073,6 @@ simp_cil (void) } } -#if 0 - FOR_EACH_BB (bb) - { - dump_generic_bb (stdout, bb, 4, 0); - } -#endif - return 0; } @@ -2984,7 +3100,7 @@ struct tree_opt_pass pass_simp_cil = /* ??? If TER is enabled, we also kill gimple. */ 0, /* properties_destroyed */ 0, - 0, + TODO_dump_func, /* todo_flags_finish */ 0 /* letter */ }; diff --git a/gcc/passes.c b/gcc/passes.c index e037f8169d4..4f90fd2a4c7 100644 --- a/gcc/passes.c +++ b/gcc/passes.c @@ -481,6 +481,7 @@ init_optimization_passes (void) NEXT_PASS (pass_warn_function_noreturn); NEXT_PASS (pass_mudflap_2); #if defined(DISABLE_RTL_PASSES) + NEXT_PASS (pass_bb_layout); NEXT_PASS (pass_simp_cil); NEXT_PASS (pass_gen_cil); /* <--- CIL */ NEXT_PASS (pass_free_datastructures); diff --git a/gcc/timevar.def b/gcc/timevar.def index 28b0b766eba..711554edcbb 100644 --- a/gcc/timevar.def +++ b/gcc/timevar.def @@ -168,6 +168,7 @@ DEFTIMEVAR (TV_REG_STACK , "reg stack") DEFTIMEVAR (TV_FINAL , "final") DEFTIMEVAR (TV_SYMOUT , "symout") DEFTIMEVAR (TV_VAR_TRACKING , "variable tracking") +DEFTIMEVAR (TV_BB_LAYOUT , "block layout") /* Everything else in rest_of_compilation not included above. */ DEFTIMEVAR (TV_REST_OF_COMPILATION , "rest of compilation") diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h index 8a553021706..c59754cf0e3 100644 --- a/gcc/tree-pass.h +++ b/gcc/tree-pass.h @@ -395,6 +395,8 @@ extern struct tree_opt_pass pass_set_nothrow_function_flags; extern struct tree_opt_pass pass_final; extern struct tree_opt_pass pass_rtl_seqabstr; +extern struct tree_opt_pass pass_bb_layout; + /* The root of the compilation pass tree, once constructed. */ extern struct tree_opt_pass *all_passes, *all_ipa_passes, *all_lowering_passes; -- cgit v1.2.3