X-Git-Url: http://git.sourceforge.jp/view?p=pf3gnuchains%2Fgcc-fork.git;a=blobdiff_plain;f=gcc%2Ftree-outof-ssa.c;h=4ed8e9fbdf063f736a12132c6316a7c7d77d1947;hp=2f36cc6cc818319fe08abf62a73e787f3efecdd3;hb=04c7e80fcbbadda46ac89b091751993bda47cc96;hpb=7bbb6ff8a2c6a4b9be50769f8b7bce25ef3f75c9 diff --git a/gcc/tree-outof-ssa.c b/gcc/tree-outof-ssa.c index 2f36cc6cc81..4ed8e9fbdf0 100644 --- a/gcc/tree-outof-ssa.c +++ b/gcc/tree-outof-ssa.c @@ -1,12 +1,12 @@ /* Convert a program in SSA form into Normal form. - Copyright (C) 2004, 2005 Free Software Foundation, Inc. + Copyright (C) 2004, 2005, 2006, 2007, 2008 Free Software Foundation, Inc. Contributed by Andrew Macleod 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, @@ -15,46 +15,26 @@ 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. */ +along with GCC; see the file COPYING3. If not see +. */ #include "config.h" #include "system.h" #include "coretypes.h" #include "tm.h" #include "tree.h" -#include "flags.h" -#include "rtl.h" -#include "tm_p.h" #include "ggc.h" -#include "langhooks.h" -#include "hard-reg-set.h" #include "basic-block.h" -#include "output.h" -#include "expr.h" -#include "function.h" #include "diagnostic.h" #include "bitmap.h" #include "tree-flow.h" -#include "tree-gimple.h" -#include "tree-inline.h" -#include "varray.h" #include "timevar.h" -#include "hashtab.h" #include "tree-dump.h" -#include "tree-ssa-live.h" #include "tree-pass.h" #include "toplev.h" +#include "expr.h" +#include "ssaexpand.h" -/* Flags to pass to remove_ssa_form. */ - -#define SSANORM_PERFORM_TER 0x1 -#define SSANORM_COMBINE_TEMPS 0x2 -#define SSANORM_COALESCE_PARTITIONS 0x4 - -DEF_VEC_I(int); -DEF_VEC_ALLOC_I(int,heap); /* Used to hold all the components required to do SSA PHI elimination. The node and pred/succ list is a simple linear list of nodes and @@ -82,7 +62,7 @@ typedef struct _elim_graph { int size; /* List of nodes in the elimination graph. */ - VEC(tree,heap) *nodes; + VEC(int,heap) *nodes; /* The predecessor and successor edge list. */ VEC(int,heap) *edge_list; @@ -100,116 +80,194 @@ typedef struct _elim_graph { edge e; /* List of constant copies to emit. These are pushed on in pairs. */ + VEC(int,heap) *const_dests; VEC(tree,heap) *const_copies; } *elim_graph; -/* Local functions. */ -static tree create_temp (tree); -static void insert_copy_on_edge (edge, tree, tree); -static elim_graph new_elim_graph (int); -static inline void delete_elim_graph (elim_graph); -static inline void clear_elim_graph (elim_graph); -static inline int elim_graph_size (elim_graph); -static inline void elim_graph_add_node (elim_graph, tree); -static inline void elim_graph_add_edge (elim_graph, int, int); -static inline int elim_graph_remove_succ_edge (elim_graph, int); - -static inline void eliminate_name (elim_graph, tree); -static void eliminate_build (elim_graph, basic_block); -static void elim_forward (elim_graph, int); -static int elim_unvisited_predecessor (elim_graph, int); -static void elim_backward (elim_graph, int); -static void elim_create (elim_graph, int); -static void eliminate_phi (edge, elim_graph); -static tree_live_info_p coalesce_ssa_name (var_map, int); -static void assign_vars (var_map); -static bool replace_use_variable (var_map, use_operand_p, tree *); -static bool replace_def_variable (var_map, def_operand_p, tree *); -static void eliminate_virtual_phis (void); -static void coalesce_abnormal_edges (var_map, conflict_graph, root_var_p); -static void print_exprs (FILE *, const char *, tree, const char *, tree, - const char *); -static void print_exprs_edge (FILE *, edge, const char *, tree, const char *, - tree); - - -/* Create a temporary variable based on the type of variable T. Use T's name - as the prefix. */ - -static tree -create_temp (tree t) +/* For an edge E find out a good source location to associate with + instructions inserted on edge E. If E has an implicit goto set, + use its location. Otherwise search instructions in predecessors + of E for a location, and use that one. That makes sense because + we insert on edges for PHI nodes, and effects of PHIs happen on + the end of the predecessor conceptually. */ + +static void +set_location_for_edge (edge e) +{ + if (e->goto_locus) + { + set_curr_insn_source_location (e->goto_locus); + set_curr_insn_block (e->goto_block); + } + else + { + basic_block bb = e->src; + gimple_stmt_iterator gsi; + + do + { + for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi)) + { + gimple stmt = gsi_stmt (gsi); + if (gimple_has_location (stmt) || gimple_block (stmt)) + { + set_curr_insn_source_location (gimple_location (stmt)); + set_curr_insn_block (gimple_block (stmt)); + return; + } + } + /* Nothing found in this basic block. Make a half-assed attempt + to continue with another block. */ + if (single_pred_p (bb)) + bb = single_pred (bb); + else + bb = e->src; + } + while (bb != e->src); + } +} + +/* Emit insns to copy SRC into DEST converting SRC if necessary. */ + +static inline rtx +emit_partition_copy (rtx dest, rtx src, int unsignedsrcp) { - tree tmp; - const char *name = NULL; - tree type; + rtx seq; + + start_sequence (); - if (TREE_CODE (t) == SSA_NAME) - t = SSA_NAME_VAR (t); + if (GET_MODE (src) != VOIDmode && GET_MODE (src) != GET_MODE (dest)) + src = convert_to_mode (GET_MODE (dest), src, unsignedsrcp); + emit_move_insn (dest, src); - gcc_assert (TREE_CODE (t) == VAR_DECL || TREE_CODE (t) == PARM_DECL); + seq = get_insns (); + end_sequence (); - type = TREE_TYPE (t); - tmp = DECL_NAME (t); - if (tmp) - name = IDENTIFIER_POINTER (tmp); + return seq; +} - if (name == NULL) - name = "temp"; - tmp = create_tmp_var (type, name); +/* Insert a copy instruction from partition SRC to DEST onto edge E. */ - if (DECL_DEBUG_EXPR_IS_FROM (t) && DECL_DEBUG_EXPR (t)) +static void +insert_partition_copy_on_edge (edge e, int dest, int src) +{ + rtx seq; + if (dump_file && (dump_flags & TDF_DETAILS)) { - SET_DECL_DEBUG_EXPR (tmp, DECL_DEBUG_EXPR (t)); - DECL_DEBUG_EXPR_IS_FROM (tmp) = 1; + fprintf (dump_file, + "Inserting a partition copy on edge BB%d->BB%d :" + "PART.%d = PART.%d", + e->src->index, + e->dest->index, dest, src); + fprintf (dump_file, "\n"); } - else if (!DECL_IGNORED_P (t)) + + gcc_assert (SA.partition_to_pseudo[dest]); + gcc_assert (SA.partition_to_pseudo[src]); + + set_location_for_edge (e); + + seq = emit_partition_copy (SA.partition_to_pseudo[dest], + SA.partition_to_pseudo[src], + TYPE_UNSIGNED (TREE_TYPE ( + partition_to_var (SA.map, src)))); + + insert_insn_on_edge (seq, e); +} + +/* Insert a copy instruction from expression SRC to partition DEST + onto edge E. */ + +static void +insert_value_copy_on_edge (edge e, int dest, tree src) +{ + rtx seq, x; + enum machine_mode mode; + if (dump_file && (dump_flags & TDF_DETAILS)) { - SET_DECL_DEBUG_EXPR (tmp, t); - DECL_DEBUG_EXPR_IS_FROM (tmp) = 1; + fprintf (dump_file, + "Inserting a value copy on edge BB%d->BB%d : PART.%d = ", + e->src->index, + e->dest->index, dest); + print_generic_expr (dump_file, src, TDF_SLIM); + fprintf (dump_file, "\n"); } - DECL_ARTIFICIAL (tmp) = DECL_ARTIFICIAL (t); - DECL_IGNORED_P (tmp) = DECL_IGNORED_P (t); - add_referenced_tmp_var (tmp); - - /* add_referenced_tmp_var will create the annotation and set up some - of the flags in the annotation. However, some flags we need to - inherit from our original variable. */ - var_ann (tmp)->type_mem_tag = var_ann (t)->type_mem_tag; - if (is_call_clobbered (t)) - mark_call_clobbered (tmp, var_ann (t)->escape_mask); - - return tmp; -} + gcc_assert (SA.partition_to_pseudo[dest]); + + set_location_for_edge (e); + + start_sequence (); + mode = GET_MODE (SA.partition_to_pseudo[dest]); + x = expand_expr (src, SA.partition_to_pseudo[dest], mode, EXPAND_NORMAL); + if (GET_MODE (x) != VOIDmode && GET_MODE (x) != mode) + x = convert_to_mode (mode, x, TYPE_UNSIGNED (TREE_TYPE (src))); + if (CONSTANT_P (x) && GET_MODE (x) == VOIDmode + && mode != TYPE_MODE (TREE_TYPE (src))) + x = convert_modes (mode, TYPE_MODE (TREE_TYPE (src)), + x, TYPE_UNSIGNED (TREE_TYPE (src))); + if (x != SA.partition_to_pseudo[dest]) + emit_move_insn (SA.partition_to_pseudo[dest], x); + seq = get_insns (); + end_sequence (); + + insert_insn_on_edge (seq, e); +} -/* This helper function fill insert a copy from a constant or variable SRC to - variable DEST on edge E. */ +/* Insert a copy instruction from RTL expression SRC to partition DEST + onto edge E. */ static void -insert_copy_on_edge (edge e, tree dest, tree src) +insert_rtx_to_part_on_edge (edge e, int dest, rtx src, int unsignedsrcp) { - tree copy; + rtx seq; + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, + "Inserting a temp copy on edge BB%d->BB%d : PART.%d = ", + e->src->index, + e->dest->index, dest); + print_simple_rtl (dump_file, src); + fprintf (dump_file, "\n"); + } - copy = build2 (MODIFY_EXPR, TREE_TYPE (dest), dest, src); - set_is_used (dest); + gcc_assert (SA.partition_to_pseudo[dest]); + set_location_for_edge (e); - if (TREE_CODE (src) == ADDR_EXPR) - src = TREE_OPERAND (src, 0); - if (TREE_CODE (src) == VAR_DECL || TREE_CODE (src) == PARM_DECL) - set_is_used (src); + seq = emit_partition_copy (SA.partition_to_pseudo[dest], + src, + unsignedsrcp); + insert_insn_on_edge (seq, e); +} + +/* Insert a copy instruction from partition SRC to RTL lvalue DEST + onto edge E. */ + +static void +insert_part_to_rtx_on_edge (edge e, rtx dest, int src) +{ + rtx seq; if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, - "Inserting a copy on edge BB%d->BB%d :", + "Inserting a temp copy on edge BB%d->BB%d : ", e->src->index, e->dest->index); - print_generic_expr (dump_file, copy, dump_flags); - fprintf (dump_file, "\n"); + print_simple_rtl (dump_file, dest); + fprintf (dump_file, "= PART.%d\n", src); } - bsi_insert_on_edge (e, copy); + gcc_assert (SA.partition_to_pseudo[src]); + set_location_for_edge (e); + + seq = emit_partition_copy (dest, + SA.partition_to_pseudo[src], + TYPE_UNSIGNED (TREE_TYPE ( + partition_to_var (SA.map, src)))); + + insert_insn_on_edge (seq, e); } @@ -221,7 +279,8 @@ new_elim_graph (int size) { elim_graph g = (elim_graph) xmalloc (sizeof (struct _elim_graph)); - g->nodes = VEC_alloc (tree, heap, 30); + g->nodes = VEC_alloc (int, heap, 30); + g->const_dests = VEC_alloc (int, heap, 20); g->const_copies = VEC_alloc (tree, heap, 20); g->edge_list = VEC_alloc (int, heap, 20); g->stack = VEC_alloc (int, heap, 30); @@ -237,7 +296,7 @@ new_elim_graph (int size) static inline void clear_elim_graph (elim_graph g) { - VEC_truncate (tree, g->nodes, 0); + VEC_truncate (int, g->nodes, 0); VEC_truncate (int, g->edge_list, 0); } @@ -251,7 +310,8 @@ delete_elim_graph (elim_graph g) VEC_free (int, heap, g->stack); VEC_free (int, heap, g->edge_list); VEC_free (tree, heap, g->const_copies); - VEC_free (tree, heap, g->nodes); + VEC_free (int, heap, g->const_dests); + VEC_free (int, heap, g->nodes); free (g); } @@ -261,22 +321,22 @@ delete_elim_graph (elim_graph g) static inline int elim_graph_size (elim_graph g) { - return VEC_length (tree, g->nodes); + return VEC_length (int, g->nodes); } /* Add NODE to graph G, if it doesn't exist already. */ static inline void -elim_graph_add_node (elim_graph g, tree node) +elim_graph_add_node (elim_graph g, int node) { int x; - tree t; + int t; - for (x = 0; VEC_iterate (tree, g->nodes, x, t); x++) + for (x = 0; VEC_iterate (int, g->nodes, x, t); x++) if (t == node) return; - VEC_safe_push (tree, heap, g->nodes, node); + VEC_safe_push (int, heap, g->nodes, node); } @@ -351,7 +411,7 @@ do { \ /* Add T to elimination graph G. */ static inline void -eliminate_name (elim_graph g, tree T) +eliminate_name (elim_graph g, int T) { elim_graph_add_node (g, T); } @@ -361,20 +421,21 @@ eliminate_name (elim_graph g, tree T) G->e. */ static void -eliminate_build (elim_graph g, basic_block B) +eliminate_build (elim_graph g) { - tree phi; - tree T0, Ti; + tree Ti; int p0, pi; + gimple_stmt_iterator gsi; clear_elim_graph (g); - for (phi = phi_nodes (B); phi; phi = PHI_CHAIN (phi)) + for (gsi = gsi_start_phis (g->e->dest); !gsi_end_p (gsi); gsi_next (&gsi)) { - T0 = var_to_partition_to_var (g->map, PHI_RESULT (phi)); - + gimple phi = gsi_stmt (gsi); + + p0 = var_to_partition (g->map, gimple_phi_result (phi)); /* Ignore results which are not in partitions. */ - if (T0 == NULL_TREE) + if (p0 == NO_PARTITION) continue; Ti = PHI_ARG_DEF (phi, g->e->dest_idx); @@ -388,18 +449,16 @@ eliminate_build (elim_graph g, basic_block B) { /* Save constant copies until all other copies have been emitted on this edge. */ - VEC_safe_push (tree, heap, g->const_copies, T0); + VEC_safe_push (int, heap, g->const_dests, p0); VEC_safe_push (tree, heap, g->const_copies, Ti); } else { - Ti = var_to_partition_to_var (g->map, Ti); - if (T0 != Ti) + pi = var_to_partition (g->map, Ti); + if (p0 != pi) { - eliminate_name (g, T0); - eliminate_name (g, Ti); - p0 = var_to_partition (g->map, T0); - pi = var_to_partition (g->map, Ti); + eliminate_name (g, p0); + eliminate_name (g, pi); elim_graph_add_edge (g, p0, pi); } } @@ -449,32 +508,49 @@ elim_backward (elim_graph g, int T) if (!TEST_BIT (g->visited, P)) { elim_backward (g, P); - insert_copy_on_edge (g->e, - partition_to_var (g->map, P), - partition_to_var (g->map, T)); + insert_partition_copy_on_edge (g->e, P, T); } }); } +/* Allocate a new pseudo register usable for storing values sitting + in NAME (a decl or SSA name), i.e. with matching mode and attributes. */ + +static rtx +get_temp_reg (tree name) +{ + tree var = TREE_CODE (name) == SSA_NAME ? SSA_NAME_VAR (name) : name; + tree type = TREE_TYPE (var); + int unsignedp = TYPE_UNSIGNED (type); + enum machine_mode reg_mode + = promote_mode (type, DECL_MODE (var), &unsignedp, 0); + rtx x = gen_reg_rtx (reg_mode); + if (POINTER_TYPE_P (type)) + mark_reg_pointer (x, TYPE_ALIGN (TREE_TYPE (TREE_TYPE (var)))); + return x; +} + /* Insert required copies for T in graph G. Check for a strongly connected region, and create a temporary to break the cycle if one is found. */ static void elim_create (elim_graph g, int T) { - tree U; int P, S; if (elim_unvisited_predecessor (g, T)) { - U = create_temp (partition_to_var (g->map, T)); - insert_copy_on_edge (g->e, U, partition_to_var (g->map, T)); + tree var = partition_to_var (g->map, T); + rtx U = get_temp_reg (var); + int unsignedsrcp = TYPE_UNSIGNED (TREE_TYPE (var)); + + insert_part_to_rtx_on_edge (g->e, U, T); FOR_EACH_ELIM_GRAPH_PRED (g, T, P, { if (!TEST_BIT (g->visited, P)) { elim_backward (g, P); - insert_copy_on_edge (g->e, partition_to_var (g->map, P), U); + insert_rtx_to_part_on_edge (g->e, P, U, unsignedsrcp); } }); } @@ -484,21 +560,18 @@ elim_create (elim_graph g, int T) if (S != -1) { SET_BIT (g->visited, T); - insert_copy_on_edge (g->e, - partition_to_var (g->map, T), - partition_to_var (g->map, S)); + insert_partition_copy_on_edge (g->e, T, S); } } - } + /* Eliminate all the phi nodes on edge E in graph G. */ static void eliminate_phi (edge e, elim_graph g) { int x; - basic_block B = e->dest; gcc_assert (VEC_length (tree, g->const_copies) == 0); @@ -508,20 +581,19 @@ eliminate_phi (edge e, elim_graph g) g->e = e; - eliminate_build (g, B); + eliminate_build (g); if (elim_graph_size (g) != 0) { - tree var; + int part; sbitmap_zero (g->visited); VEC_truncate (int, g->stack, 0); - for (x = 0; VEC_iterate (tree, g->nodes, x, var); x++) + for (x = 0; VEC_iterate (int, g->nodes, x, part); x++) { - int p = var_to_partition (g->map, var); - if (!TEST_BIT (g->visited, p)) - elim_forward (g, p); + if (!TEST_BIT (g->visited, part)) + elim_forward (g, part); } sbitmap_zero (g->visited); @@ -536,1925 +608,368 @@ eliminate_phi (edge e, elim_graph g) /* If there are any pending constant copies, issue them now. */ while (VEC_length (tree, g->const_copies) > 0) { - tree src, dest; + int dest; + tree src; src = VEC_pop (tree, g->const_copies); - dest = VEC_pop (tree, g->const_copies); - insert_copy_on_edge (e, dest, src); + dest = VEC_pop (int, g->const_dests); + insert_value_copy_on_edge (e, dest, src); } } -/* Shortcut routine to print messages to file F of the form: - "STR1 EXPR1 STR2 EXPR2 STR3." */ - -static void -print_exprs (FILE *f, const char *str1, tree expr1, const char *str2, - tree expr2, const char *str3) -{ - fprintf (f, "%s", str1); - print_generic_expr (f, expr1, TDF_SLIM); - fprintf (f, "%s", str2); - print_generic_expr (f, expr2, TDF_SLIM); - fprintf (f, "%s", str3); -} - - -/* Shortcut routine to print abnormal edge messages to file F of the form: - "STR1 EXPR1 STR2 EXPR2 across edge E. */ - -static void -print_exprs_edge (FILE *f, edge e, const char *str1, tree expr1, - const char *str2, tree expr2) -{ - print_exprs (f, str1, expr1, str2, expr2, " across an abnormal edge"); - fprintf (f, " from BB%d->BB%d\n", e->src->index, - e->dest->index); -} - - -/* Coalesce partitions in MAP which are live across abnormal edges in GRAPH. - RV is the root variable groupings of the partitions in MAP. Since code - cannot be inserted on these edges, failure to coalesce something across - an abnormal edge is an error. */ +/* Remove each argument from PHI. If an arg was the last use of an SSA_NAME, + check to see if this allows another PHI node to be removed. */ static void -coalesce_abnormal_edges (var_map map, conflict_graph graph, root_var_p rv) +remove_gimple_phi_args (gimple phi) { - basic_block bb; - edge e; - tree phi, var, tmp; - int x, y, z; - edge_iterator ei; - - /* Code cannot be inserted on abnormal edges. Look for all abnormal - edges, and coalesce any PHI results with their arguments across - that edge. */ - - FOR_EACH_BB (bb) - FOR_EACH_EDGE (e, ei, bb->succs) - if (e->dest != EXIT_BLOCK_PTR && e->flags & EDGE_ABNORMAL) - for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi)) - { - /* Visit each PHI on the destination side of this abnormal - edge, and attempt to coalesce the argument with the result. */ - var = PHI_RESULT (phi); - x = var_to_partition (map, var); - - /* Ignore results which are not relevant. */ - if (x == NO_PARTITION) - continue; - - tmp = PHI_ARG_DEF (phi, e->dest_idx); -#ifdef ENABLE_CHECKING - if (!phi_ssa_name_p (tmp)) - { - print_exprs_edge (stderr, e, - "\nConstant argument in PHI. Can't insert :", - var, " = ", tmp); - internal_error ("SSA corruption"); - } -#else - gcc_assert (phi_ssa_name_p (tmp)); -#endif - y = var_to_partition (map, tmp); - gcc_assert (x != NO_PARTITION); - gcc_assert (y != NO_PARTITION); -#ifdef ENABLE_CHECKING - if (root_var_find (rv, x) != root_var_find (rv, y)) - { - print_exprs_edge (stderr, e, "\nDifferent root vars: ", - root_var (rv, root_var_find (rv, x)), - " and ", - root_var (rv, root_var_find (rv, y))); - internal_error ("SSA corruption"); - } -#else - gcc_assert (root_var_find (rv, x) == root_var_find (rv, y)); -#endif - - if (x != y) - { -#ifdef ENABLE_CHECKING - if (conflict_graph_conflict_p (graph, x, y)) - { - print_exprs_edge (stderr, e, "\n Conflict ", - partition_to_var (map, x), - " and ", partition_to_var (map, y)); - internal_error ("SSA corruption"); - } -#else - gcc_assert (!conflict_graph_conflict_p (graph, x, y)); -#endif - - /* Now map the partitions back to their real variables. */ - var = partition_to_var (map, x); - tmp = partition_to_var (map, y); - if (dump_file && (dump_flags & TDF_DETAILS)) - { - print_exprs_edge (dump_file, e, - "ABNORMAL: Coalescing ", - var, " and ", tmp); - } - z = var_union (map, var, tmp); -#ifdef ENABLE_CHECKING - if (z == NO_PARTITION) - { - print_exprs_edge (stderr, e, "\nUnable to coalesce", - partition_to_var (map, x), " and ", - partition_to_var (map, y)); - internal_error ("SSA corruption"); - } -#else - gcc_assert (z != NO_PARTITION); -#endif - gcc_assert (z == x || z == y); - if (z == x) - conflict_graph_merge_regs (graph, x, y); - else - conflict_graph_merge_regs (graph, y, x); - } - } -} - -/* Coalesce potential copies via PHI arguments. */ + use_operand_p arg_p; + ssa_op_iter iter; -static void -coalesce_phi_operands (var_map map, coalesce_list_p cl) -{ - basic_block bb; - tree phi; + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Removing Dead PHI definition: "); + print_gimple_stmt (dump_file, phi, 0, TDF_SLIM); + } - FOR_EACH_BB (bb) + FOR_EACH_PHI_ARG (arg_p, phi, iter, SSA_OP_USE) { - for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) - { - tree res = PHI_RESULT (phi); - int p = var_to_partition (map, res); - int x; + tree arg = USE_FROM_PTR (arg_p); + if (TREE_CODE (arg) == SSA_NAME) + { + /* Remove the reference to the existing argument. */ + SET_USE (arg_p, NULL_TREE); + if (has_zero_uses (arg)) + { + gimple stmt; + gimple_stmt_iterator gsi; - if (p == NO_PARTITION) - continue; + stmt = SSA_NAME_DEF_STMT (arg); - for (x = 0; x < PHI_NUM_ARGS (phi); x++) - { - tree arg = PHI_ARG_DEF (phi, x); - int p2; - - if (TREE_CODE (arg) != SSA_NAME) - continue; - if (SSA_NAME_VAR (res) != SSA_NAME_VAR (arg)) - continue; - p2 = var_to_partition (map, PHI_ARG_DEF (phi, x)); - if (p2 != NO_PARTITION) + /* Also remove the def if it is a PHI node. */ + if (gimple_code (stmt) == GIMPLE_PHI) { - edge e = PHI_ARG_EDGE (phi, x); - add_coalesce (cl, p, p2, - coalesce_cost (EDGE_FREQUENCY (e), - maybe_hot_bb_p (bb), - EDGE_CRITICAL_P (e))); + remove_gimple_phi_args (stmt); + gsi = gsi_for_stmt (stmt); + remove_phi_node (&gsi, true); } + } } } } -/* Coalesce all the result decls together. */ +/* Remove any PHI node which is a virtual PHI, or a PHI with no uses. */ static void -coalesce_result_decls (var_map map, coalesce_list_p cl) +eliminate_useless_phis (void) { - unsigned int i, x; - tree var = NULL; + basic_block bb; + gimple_stmt_iterator gsi; + tree result; - for (i = x = 0; x < num_var_partitions (map); x++) + FOR_EACH_BB (bb) { - tree p = partition_to_var (map, x); - if (TREE_CODE (SSA_NAME_VAR (p)) == RESULT_DECL) - { - if (var == NULL_TREE) + for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); ) + { + gimple phi = gsi_stmt (gsi); + result = gimple_phi_result (phi); + if (!is_gimple_reg (SSA_NAME_VAR (result))) + { +#ifdef ENABLE_CHECKING + size_t i; + /* There should be no arguments which are not virtual, or the + results will be incorrect. */ + for (i = 0; i < gimple_phi_num_args (phi); i++) + { + tree arg = PHI_ARG_DEF (phi, i); + if (TREE_CODE (arg) == SSA_NAME + && is_gimple_reg (SSA_NAME_VAR (arg))) + { + fprintf (stderr, "Argument of PHI is not virtual ("); + print_generic_expr (stderr, arg, TDF_SLIM); + fprintf (stderr, "), but the result is :"); + print_gimple_stmt (stderr, phi, 0, TDF_SLIM); + internal_error ("SSA corruption"); + } + } +#endif + remove_phi_node (&gsi, true); + } + else { - var = p; - i = x; + /* Also remove real PHIs with no uses. */ + if (has_zero_uses (result)) + { + remove_gimple_phi_args (phi); + remove_phi_node (&gsi, true); + } + else + gsi_next (&gsi); } - else - add_coalesce (cl, i, x, - coalesce_cost (EXIT_BLOCK_PTR->frequency, - maybe_hot_bb_p (EXIT_BLOCK_PTR), - false)); } } } -/* Coalesce matching constraints in asms. */ + +/* This function will rewrite the current program using the variable mapping + found in MAP. If the replacement vector VALUES is provided, any + occurrences of partitions with non-null entries in the vector will be + replaced with the expression in the vector instead of its mapped + variable. */ static void -coalesce_asm_operands (var_map map, coalesce_list_p cl) +rewrite_trees (var_map map ATTRIBUTE_UNUSED) { +#ifdef ENABLE_CHECKING basic_block bb; - + /* Search for PHIs where the destination has no partition, but one + or more arguments has a partition. This should not happen and can + create incorrect code. */ FOR_EACH_BB (bb) { - block_stmt_iterator bsi; - for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) + gimple_stmt_iterator gsi; + for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) { - tree stmt = bsi_stmt (bsi); - unsigned long noutputs, i; - tree *outputs, link; - - if (TREE_CODE (stmt) != ASM_EXPR) - continue; - - noutputs = list_length (ASM_OUTPUTS (stmt)); - outputs = (tree *) alloca (noutputs * sizeof (tree)); - for (i = 0, link = ASM_OUTPUTS (stmt); link; - ++i, link = TREE_CHAIN (link)) - outputs[i] = TREE_VALUE (link); - - for (link = ASM_INPUTS (stmt); link; link = TREE_CHAIN (link)) + gimple phi = gsi_stmt (gsi); + tree T0 = var_to_partition_to_var (map, gimple_phi_result (phi)); + if (T0 == NULL_TREE) { - const char *constraint - = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link))); - tree input = TREE_VALUE (link); - char *end; - unsigned long match; - int p1, p2; - - if (TREE_CODE (input) != SSA_NAME && !DECL_P (input)) - continue; - - match = strtoul (constraint, &end, 10); - if (match >= noutputs || end == constraint) - continue; - - if (TREE_CODE (outputs[match]) != SSA_NAME - && !DECL_P (outputs[match])) - continue; - - p1 = var_to_partition (map, outputs[match]); - if (p1 == NO_PARTITION) - continue; - p2 = var_to_partition (map, input); - if (p2 == NO_PARTITION) - continue; - - add_coalesce (cl, p1, p2, coalesce_cost (REG_BR_PROB_BASE, - maybe_hot_bb_p (bb), - false)); + size_t i; + for (i = 0; i < gimple_phi_num_args (phi); i++) + { + tree arg = PHI_ARG_DEF (phi, i); + + if (TREE_CODE (arg) == SSA_NAME + && var_to_partition (map, arg) != NO_PARTITION) + { + fprintf (stderr, "Argument of PHI is in a partition :("); + print_generic_expr (stderr, arg, TDF_SLIM); + fprintf (stderr, "), but the result is not :"); + print_gimple_stmt (stderr, phi, 0, TDF_SLIM); + internal_error ("SSA corruption"); + } + } } } } +#endif } -/* Reduce the number of live ranges in MAP. Live range information is - returned if FLAGS indicates that we are combining temporaries, otherwise - NULL is returned. The only partitions which are associated with actual - variables at this point are those which are forced to be coalesced for - various reason. (live on entry, live across abnormal edges, etc.). */ +/* Given the out-of-ssa info object SA (with prepared partitions) + eliminate all phi nodes in all basic blocks. Afterwards no + basic block will have phi nodes anymore and there are possibly + some RTL instructions inserted on edges. */ -static tree_live_info_p -coalesce_ssa_name (var_map map, int flags) +void +expand_phi_nodes (struct ssaexpand *sa) { - unsigned num, x; - sbitmap live; - root_var_p rv; - tree_live_info_p liveinfo; - conflict_graph graph; - coalesce_list_p cl = NULL; - sbitmap_iterator sbi; - - if (num_var_partitions (map) <= 1) - return NULL; - - liveinfo = calculate_live_on_entry (map); - calculate_live_on_exit (liveinfo); - rv = root_var_init (map); - - /* Remove single element variable from the list. */ - root_var_compact (rv); - - cl = create_coalesce_list (map); - - coalesce_phi_operands (map, cl); - coalesce_result_decls (map, cl); - coalesce_asm_operands (map, cl); + basic_block bb; + elim_graph g = new_elim_graph (sa->map->num_partitions); + g->map = sa->map; - /* Build a conflict graph. */ - graph = build_tree_conflict_graph (liveinfo, rv, cl); + FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb, EXIT_BLOCK_PTR, next_bb) + if (!gimple_seq_empty_p (phi_nodes (bb))) + { + edge e; + edge_iterator ei; + FOR_EACH_EDGE (e, ei, bb->preds) + eliminate_phi (e, g); + set_phi_nodes (bb, NULL); + /* We can't redirect EH edges in RTL land, so we need to do this + here. Redirection happens only when splitting is necessary, + which it is only for critical edges, normally. For EH edges + it might also be necessary when the successor has more than + one predecessor. In that case the edge is either required to + be fallthru (which EH edges aren't), or the predecessor needs + to end with a jump (which again, isn't the case with EH edges). + Hence, split all EH edges on which we inserted instructions + and whose successor has multiple predecessors. */ + for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); ) + { + if (e->insns.r && (e->flags & EDGE_EH) + && !single_pred_p (e->dest)) + { + rtx insns = e->insns.r; + basic_block bb; + e->insns.r = NULL_RTX; + bb = split_edge (e); + single_pred_edge (bb)->insns.r = insns; + } + else + ei_next (&ei); + } + } - if (cl) - { - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "Before sorting:\n"); - dump_coalesce_list (dump_file, cl); - } + delete_elim_graph (g); +} - sort_coalesce_list (cl); - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "\nAfter sorting:\n"); - dump_coalesce_list (dump_file, cl); - } - } +/* Remove the ssa-names in the current function and translate them into normal + compiler variables. PERFORM_TER is true if Temporary Expression Replacement + should also be used. */ - /* Put the single element variables back in. */ - root_var_decompact (rv); +static void +remove_ssa_form (bool perform_ter, struct ssaexpand *sa) +{ + bitmap values = NULL; + var_map map; + unsigned i; - /* First, coalesce all live on entry variables to their root variable. - This will ensure the first use is coming from the correct location. */ + map = coalesce_ssa_name (); - num = num_var_partitions (map); - live = sbitmap_alloc (num); - sbitmap_zero (live); + /* Return to viewing the variable list as just all reference variables after + coalescing has been performed. */ + partition_view_normal (map, false); - /* Set 'live' vector to indicate live on entry partitions. */ - for (x = 0 ; x < num; x++) + if (dump_file && (dump_flags & TDF_DETAILS)) { - tree var = partition_to_var (map, x); - if (default_def (SSA_NAME_VAR (var)) == var) - SET_BIT (live, x); + fprintf (dump_file, "After Coalescing:\n"); + dump_var_map (dump_file, map); } - if ((flags & SSANORM_COMBINE_TEMPS) == 0) + if (perform_ter) { - delete_tree_live_info (liveinfo); - liveinfo = NULL; + values = find_replaceable_exprs (map); + if (values && dump_file && (dump_flags & TDF_DETAILS)) + dump_replaceable_exprs (dump_file, values); } - /* Assign root variable as partition representative for each live on entry - partition. */ - EXECUTE_IF_SET_IN_SBITMAP (live, 0, x, sbi) + rewrite_trees (map); + + sa->map = map; + sa->values = values; + sa->partition_has_default_def = BITMAP_ALLOC (NULL); + for (i = 1; i < num_ssa_names; i++) { - tree var = root_var (rv, root_var_find (rv, x)); - var_ann_t ann = var_ann (var); - /* If these aren't already coalesced... */ - if (partition_to_var (map, x) != var) + tree t = ssa_name (i); + if (t && SSA_NAME_IS_DEFAULT_DEF (t)) { - /* This root variable should have not already been assigned - to another partition which is not coalesced with this one. */ - gcc_assert (!ann->out_of_ssa_tag); - - if (dump_file && (dump_flags & TDF_DETAILS)) - { - print_exprs (dump_file, "Must coalesce ", - partition_to_var (map, x), - " with the root variable ", var, ".\n"); - } - - change_partition_var (map, var, x); + int p = var_to_partition (map, t); + if (p != NO_PARTITION) + bitmap_set_bit (sa->partition_has_default_def, p); } } - - sbitmap_free (live); - - /* Coalesce partitions live across abnormal edges. */ - coalesce_abnormal_edges (map, graph, rv); - - if (dump_file && (dump_flags & TDF_DETAILS)) - dump_var_map (dump_file, map); - - /* Coalesce partitions. */ - coalesce_tpa_members (rv, graph, map, cl, - ((dump_flags & TDF_DETAILS) ? dump_file - : NULL)); - - if (flags & SSANORM_COALESCE_PARTITIONS) - coalesce_tpa_members (rv, graph, map, NULL, - ((dump_flags & TDF_DETAILS) ? dump_file - : NULL)); - if (cl) - delete_coalesce_list (cl); - root_var_delete (rv); - conflict_graph_delete (graph); - - return liveinfo; } -/* Take the ssa-name var_map MAP, and assign real variables to each - partition. */ +/* If not already done so for basic block BB, assign increasing uids + to each of its instructions. */ static void -assign_vars (var_map map) +maybe_renumber_stmts_bb (basic_block bb) { - int x, i, num, rep; - tree t, var; - var_ann_t ann; - root_var_p rv; - - rv = root_var_init (map); - if (!rv) + unsigned i = 0; + gimple_stmt_iterator gsi; + + if (!bb->aux) return; - - /* Coalescing may already have forced some partitions to their root - variable. Find these and tag them. */ - - num = num_var_partitions (map); - for (x = 0; x < num; x++) - { - var = partition_to_var (map, x); - if (TREE_CODE (var) != SSA_NAME) - { - /* Coalescing will already have verified that more than one - partition doesn't have the same root variable. Simply marked - the variable as assigned. */ - ann = var_ann (var); - ann->out_of_ssa_tag = 1; - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "partition %d has variable ", x); - print_generic_expr (dump_file, var, TDF_SLIM); - fprintf (dump_file, " assigned to it.\n"); - } - - } - } - - num = root_var_num (rv); - for (x = 0; x < num; x++) + bb->aux = NULL; + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) { - var = root_var (rv, x); - ann = var_ann (var); - for (i = root_var_first_partition (rv, x); - i != ROOT_VAR_NONE; - i = root_var_next_partition (rv, i)) - { - t = partition_to_var (map, i); - - if (t == var || TREE_CODE (t) != SSA_NAME) - continue; - - rep = var_to_partition (map, t); - - if (!ann->out_of_ssa_tag) - { - if (dump_file && (dump_flags & TDF_DETAILS)) - print_exprs (dump_file, "", t, " --> ", var, "\n"); - change_partition_var (map, var, rep); - continue; - } - - if (dump_file && (dump_flags & TDF_DETAILS)) - print_exprs (dump_file, "", t, " not coalesced with ", var, - ""); - - var = create_temp (t); - change_partition_var (map, var, rep); - ann = var_ann (var); - - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, " --> New temp: '"); - print_generic_expr (dump_file, var, TDF_SLIM); - fprintf (dump_file, "'\n"); - } - } + gimple stmt = gsi_stmt (gsi); + gimple_set_uid (stmt, i); + i++; } - - root_var_delete (rv); } -/* Replace use operand P with whatever variable it has been rewritten to based - on the partitions in MAP. EXPR is an optional expression vector over SSA - versions which is used to replace P with an expression instead of a variable. - If the stmt is changed, return true. */ +/* Return true if we can determine that the SSA_NAMEs RESULT (a result + of a PHI node) and ARG (one of its arguments) conflict. Return false + otherwise, also when we simply aren't sure. */ -static inline bool -replace_use_variable (var_map map, use_operand_p p, tree *expr) +static bool +trivially_conflicts_p (basic_block bb, tree result, tree arg) { - tree new_var; - tree var = USE_FROM_PTR (p); + use_operand_p use; + imm_use_iterator imm_iter; + gimple defa = SSA_NAME_DEF_STMT (arg); - /* Check if we are replacing this variable with an expression. */ - if (expr) - { - int version = SSA_NAME_VERSION (var); - if (expr[version]) - { - tree new_expr = TREE_OPERAND (expr[version], 1); - SET_USE (p, new_expr); - /* Clear the stmt's RHS, or GC might bite us. */ - TREE_OPERAND (expr[version], 1) = NULL_TREE; - return true; - } - } + /* If ARG isn't defined in the same block it's too complicated for + our little mind. */ + if (gimple_bb (defa) != bb) + return false; - new_var = var_to_partition_to_var (map, var); - if (new_var) + FOR_EACH_IMM_USE_FAST (use, imm_iter, result) { - SET_USE (p, new_var); - set_is_used (new_var); - return true; + gimple use_stmt = USE_STMT (use); + /* Now, if there's a use of RESULT that lies outside this basic block, + then there surely is a conflict with ARG. */ + if (gimple_bb (use_stmt) != bb) + return true; + if (gimple_code (use_stmt) == GIMPLE_PHI) + continue; + /* The use now is in a real stmt of BB, so if ARG was defined + in a PHI node (like RESULT) both conflict. */ + if (gimple_code (defa) == GIMPLE_PHI) + return true; + maybe_renumber_stmts_bb (bb); + /* If the use of RESULT occurs after the definition of ARG, + the two conflict too. */ + if (gimple_uid (defa) < gimple_uid (use_stmt)) + return true; } + return false; } -/* Replace def operand DEF_P with whatever variable it has been rewritten to - based on the partitions in MAP. EXPR is an optional expression vector over - SSA versions which is used to replace DEF_P with an expression instead of a - variable. If the stmt is changed, return true. */ +/* Search every PHI node for arguments associated with backedges which + we can trivially determine will need a copy (the argument is either + not an SSA_NAME or the argument has a different underlying variable + than the PHI result). -static inline bool -replace_def_variable (var_map map, def_operand_p def_p, tree *expr) -{ - tree new_var; - tree var = DEF_FROM_PTR (def_p); - - /* Check if we are replacing this variable with an expression. */ - if (expr) - { - int version = SSA_NAME_VERSION (var); - if (expr[version]) - { - tree new_expr = TREE_OPERAND (expr[version], 1); - SET_DEF (def_p, new_expr); - /* Clear the stmt's RHS, or GC might bite us. */ - TREE_OPERAND (expr[version], 1) = NULL_TREE; - return true; - } - } - - new_var = var_to_partition_to_var (map, var); - if (new_var) - { - SET_DEF (def_p, new_var); - set_is_used (new_var); - return true; - } - return false; -} - - -/* Remove any PHI node which is a virtual PHI. */ - -static void -eliminate_virtual_phis (void) -{ - basic_block bb; - tree phi, next; - - FOR_EACH_BB (bb) - { - for (phi = phi_nodes (bb); phi; phi = next) - { - next = PHI_CHAIN (phi); - if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi)))) - { -#ifdef ENABLE_CHECKING - int i; - /* There should be no arguments of this PHI which are in - the partition list, or we get incorrect results. */ - for (i = 0; i < PHI_NUM_ARGS (phi); i++) - { - tree arg = PHI_ARG_DEF (phi, i); - if (TREE_CODE (arg) == SSA_NAME - && is_gimple_reg (SSA_NAME_VAR (arg))) - { - fprintf (stderr, "Argument of PHI is not virtual ("); - print_generic_expr (stderr, arg, TDF_SLIM); - fprintf (stderr, "), but the result is :"); - print_generic_stmt (stderr, phi, TDF_SLIM); - internal_error ("SSA corruption"); - } - } -#endif - remove_phi_node (phi, NULL_TREE); - } - } - } -} - - -/* This routine will coalesce variables in MAP of the same type which do not - interfere with each other. LIVEINFO is the live range info for variables - of interest. This will both reduce the memory footprint of the stack, and - allow us to coalesce together local copies of globals and scalarized - component refs. */ - -static void -coalesce_vars (var_map map, tree_live_info_p liveinfo) -{ - basic_block bb; - type_var_p tv; - tree var; - unsigned x, p, p2; - coalesce_list_p cl; - conflict_graph graph; - - cl = create_coalesce_list (map); - - /* Merge all the live on entry vectors for coalesced partitions. */ - for (x = 0; x < num_var_partitions (map); x++) - { - var = partition_to_var (map, x); - p = var_to_partition (map, var); - if (p != x) - live_merge_and_clear (liveinfo, p, x); - } - - /* When PHI nodes are turned into copies, the result of each PHI node - becomes live on entry to the block. Mark these now. */ - FOR_EACH_BB (bb) - { - tree phi, arg; - unsigned p; - - for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) - { - p = var_to_partition (map, PHI_RESULT (phi)); - - /* Skip virtual PHI nodes. */ - if (p == (unsigned)NO_PARTITION) - continue; - - make_live_on_entry (liveinfo, bb, p); - - /* Each argument is a potential copy operation. Add any arguments - which are not coalesced to the result to the coalesce list. */ - for (x = 0; x < (unsigned)PHI_NUM_ARGS (phi); x++) - { - arg = PHI_ARG_DEF (phi, x); - if (!phi_ssa_name_p (arg)) - continue; - p2 = var_to_partition (map, arg); - if (p2 == (unsigned)NO_PARTITION) - continue; - if (p != p2) - { - edge e = PHI_ARG_EDGE (phi, x); - - add_coalesce (cl, p, p2, - coalesce_cost (EDGE_FREQUENCY (e), - maybe_hot_bb_p (bb), - EDGE_CRITICAL_P (e))); - } - } - } - } - - - /* Re-calculate live on exit info. */ - calculate_live_on_exit (liveinfo); - - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "Live range info for variable memory coalescing.\n"); - dump_live_info (dump_file, liveinfo, LIVEDUMP_ALL); - - fprintf (dump_file, "Coalesce list from phi nodes:\n"); - dump_coalesce_list (dump_file, cl); - } - - - tv = type_var_init (map); - if (dump_file) - type_var_dump (dump_file, tv); - type_var_compact (tv); - if (dump_file) - type_var_dump (dump_file, tv); - - graph = build_tree_conflict_graph (liveinfo, tv, cl); - - type_var_decompact (tv); - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "type var list now looks like:n"); - type_var_dump (dump_file, tv); - - fprintf (dump_file, "Coalesce list after conflict graph build:\n"); - dump_coalesce_list (dump_file, cl); - } - - sort_coalesce_list (cl); - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "Coalesce list after sorting:\n"); - dump_coalesce_list (dump_file, cl); - } - - coalesce_tpa_members (tv, graph, map, cl, - ((dump_flags & TDF_DETAILS) ? dump_file : NULL)); - - type_var_delete (tv); - delete_coalesce_list (cl); -} - - -/* Temporary Expression Replacement (TER) - - Replace SSA version variables during out-of-ssa with their defining - expression if there is only one use of the variable. - - A pass is made through the function, one block at a time. No cross block - information is tracked. - - Variables which only have one use, and whose defining stmt is considered - a replaceable expression (see check_replaceable) are entered into - consideration by adding a list of dependent partitions to the version_info - vector for that ssa_name_version. This information comes from the partition - mapping for each USE. At the same time, the partition_dep_list vector for - these partitions have this version number entered into their lists. - - When the use of a replaceable ssa_variable is encountered, the dependence - list in version_info[] is moved to the "pending_dependence" list in case - the current expression is also replaceable. (To be determined later in - processing this stmt.) version_info[] for the version is then updated to - point to the defining stmt and the 'replaceable' bit is set. - - Any partition which is defined by a statement 'kills' any expression which - is dependent on this partition. Every ssa version in the partitions' - dependence list is removed from future consideration. - - All virtual references are lumped together. Any expression which is - dependent on any virtual variable (via a VUSE) has a dependence added - to the special partition defined by VIRTUAL_PARTITION. - - Whenever a V_MAY_DEF is seen, all expressions dependent this - VIRTUAL_PARTITION are removed from consideration. - - At the end of a basic block, all expression are removed from consideration - in preparation for the next block. - - The end result is a vector over SSA_NAME_VERSION which is passed back to - rewrite_out_of_ssa. As the SSA variables are being rewritten, instead of - replacing the SSA_NAME tree element with the partition it was assigned, - it is replaced with the RHS of the defining expression. */ - - -/* Dependency list element. This can contain either a partition index or a - version number, depending on which list it is in. */ - -typedef struct value_expr_d -{ - int value; - struct value_expr_d *next; -} *value_expr_p; - - -/* Temporary Expression Replacement (TER) table information. */ - -typedef struct temp_expr_table_d -{ - var_map map; - void **version_info; - value_expr_p *partition_dep_list; - bitmap replaceable; - bool saw_replaceable; - int virtual_partition; - bitmap partition_in_use; - value_expr_p free_list; - value_expr_p pending_dependence; -} *temp_expr_table_p; - -/* Used to indicate a dependency on V_MAY_DEFs. */ -#define VIRTUAL_PARTITION(table) (table->virtual_partition) - -static temp_expr_table_p new_temp_expr_table (var_map); -static tree *free_temp_expr_table (temp_expr_table_p); -static inline value_expr_p new_value_expr (temp_expr_table_p); -static inline void free_value_expr (temp_expr_table_p, value_expr_p); -static inline value_expr_p find_value_in_list (value_expr_p, int, - value_expr_p *); -static inline void add_value_to_list (temp_expr_table_p, value_expr_p *, int); -static inline void add_info_to_list (temp_expr_table_p, value_expr_p *, - value_expr_p); -static value_expr_p remove_value_from_list (value_expr_p *, int); -static void add_dependance (temp_expr_table_p, int, tree); -static bool check_replaceable (temp_expr_table_p, tree); -static void finish_expr (temp_expr_table_p, int, bool); -static void mark_replaceable (temp_expr_table_p, tree); -static inline void kill_expr (temp_expr_table_p, int, bool); -static inline void kill_virtual_exprs (temp_expr_table_p, bool); -static void find_replaceable_in_bb (temp_expr_table_p, basic_block); -static tree *find_replaceable_exprs (var_map); -static void dump_replaceable_exprs (FILE *, tree *); - - -/* Create a new TER table for MAP. */ - -static temp_expr_table_p -new_temp_expr_table (var_map map) -{ - temp_expr_table_p t; - - t = XNEW (struct temp_expr_table_d); - t->map = map; - - t->version_info = XCNEWVEC (void *, num_ssa_names + 1); - t->partition_dep_list = XCNEWVEC (value_expr_p, - num_var_partitions (map) + 1); - - t->replaceable = BITMAP_ALLOC (NULL); - t->partition_in_use = BITMAP_ALLOC (NULL); - - t->saw_replaceable = false; - t->virtual_partition = num_var_partitions (map); - t->free_list = NULL; - t->pending_dependence = NULL; - - return t; -} - - -/* Free TER table T. If there are valid replacements, return the expression - vector. */ - -static tree * -free_temp_expr_table (temp_expr_table_p t) -{ - value_expr_p p; - tree *ret = NULL; - -#ifdef ENABLE_CHECKING - unsigned x; - for (x = 0; x <= num_var_partitions (t->map); x++) - gcc_assert (!t->partition_dep_list[x]); -#endif - - while ((p = t->free_list)) - { - t->free_list = p->next; - free (p); - } - - BITMAP_FREE (t->partition_in_use); - BITMAP_FREE (t->replaceable); - - free (t->partition_dep_list); - if (t->saw_replaceable) - ret = (tree *)t->version_info; - else - free (t->version_info); - - free (t); - return ret; -} - - -/* Allocate a new value list node. Take it from the free list in TABLE if - possible. */ - -static inline value_expr_p -new_value_expr (temp_expr_table_p table) -{ - value_expr_p p; - if (table->free_list) - { - p = table->free_list; - table->free_list = p->next; - } - else - p = (value_expr_p) xmalloc (sizeof (struct value_expr_d)); - - return p; -} - - -/* Add value list node P to the free list in TABLE. */ - -static inline void -free_value_expr (temp_expr_table_p table, value_expr_p p) -{ - p->next = table->free_list; - table->free_list = p; -} - - -/* Find VALUE if it's in LIST. Return a pointer to the list object if found, - else return NULL. If LAST_PTR is provided, it will point to the previous - item upon return, or NULL if this is the first item in the list. */ - -static inline value_expr_p -find_value_in_list (value_expr_p list, int value, value_expr_p *last_ptr) -{ - value_expr_p curr; - value_expr_p last = NULL; - - for (curr = list; curr; last = curr, curr = curr->next) - { - if (curr->value == value) - break; - } - if (last_ptr) - *last_ptr = last; - return curr; -} - - -/* Add VALUE to LIST, if it isn't already present. TAB is the expression - table */ - -static inline void -add_value_to_list (temp_expr_table_p tab, value_expr_p *list, int value) -{ - value_expr_p info; - - if (!find_value_in_list (*list, value, NULL)) - { - info = new_value_expr (tab); - info->value = value; - info->next = *list; - *list = info; - } -} - - -/* Add value node INFO if it's value isn't already in LIST. Free INFO if - it is already in the list. TAB is the expression table. */ - -static inline void -add_info_to_list (temp_expr_table_p tab, value_expr_p *list, value_expr_p info) -{ - if (find_value_in_list (*list, info->value, NULL)) - free_value_expr (tab, info); - else - { - info->next = *list; - *list = info; - } -} - - -/* Look for VALUE in LIST. If found, remove it from the list and return it's - pointer. */ - -static value_expr_p -remove_value_from_list (value_expr_p *list, int value) -{ - value_expr_p info, last; - - info = find_value_in_list (*list, value, &last); - if (!info) - return NULL; - if (!last) - *list = info->next; - else - last->next = info->next; - - return info; -} - - -/* Add a dependency between the def of ssa VERSION and VAR. If VAR is - replaceable by an expression, add a dependence each of the elements of the - expression. These are contained in the pending list. TAB is the - expression table. */ - -static void -add_dependance (temp_expr_table_p tab, int version, tree var) -{ - int i, x; - value_expr_p info; - - i = SSA_NAME_VERSION (var); - if (bitmap_bit_p (tab->replaceable, i)) - { - /* This variable is being substituted, so use whatever dependences - were queued up when we marked this as replaceable earlier. */ - while ((info = tab->pending_dependence)) - { - tab->pending_dependence = info->next; - /* Get the partition this variable was dependent on. Reuse this - object to represent the current expression instead. */ - x = info->value; - info->value = version; - add_info_to_list (tab, &(tab->partition_dep_list[x]), info); - add_value_to_list (tab, - (value_expr_p *)&(tab->version_info[version]), x); - bitmap_set_bit (tab->partition_in_use, x); - } - } - else - { - i = var_to_partition (tab->map, var); - gcc_assert (i != NO_PARTITION); - add_value_to_list (tab, &(tab->partition_dep_list[i]), version); - add_value_to_list (tab, - (value_expr_p *)&(tab->version_info[version]), i); - bitmap_set_bit (tab->partition_in_use, i); - } -} - - -/* Check if expression STMT is suitable for replacement in table TAB. If so, - create an expression entry. Return true if this stmt is replaceable. */ - -static bool -check_replaceable (temp_expr_table_p tab, tree stmt) -{ - tree var, def; - int version; - var_map map = tab->map; - ssa_op_iter iter; - tree call_expr; - - if (TREE_CODE (stmt) != MODIFY_EXPR) - return false; - - /* Punt if there is more than 1 def, or more than 1 use. */ - def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF); - if (!def) - return false; - - if (version_ref_count (map, def) != 1) - return false; - - /* There must be no V_MAY_DEFS or V_MUST_DEFS. */ - if (!(ZERO_SSA_OPERANDS (stmt, (SSA_OP_VMAYDEF | SSA_OP_VMUSTDEF)))) - return false; - - /* Float expressions must go through memory if float-store is on. */ - if (flag_float_store && FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (stmt, 1)))) - return false; - - /* Calls to functions with side-effects cannot be replaced. */ - if ((call_expr = get_call_expr_in (stmt)) != NULL_TREE) - { - int call_flags = call_expr_flags (call_expr); - if (TREE_SIDE_EFFECTS (call_expr) - && !(call_flags & (ECF_PURE | ECF_CONST | ECF_NORETURN))) - return false; - } - - version = SSA_NAME_VERSION (def); - - /* Add this expression to the dependency list for each use partition. */ - FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE) - { - add_dependance (tab, version, var); - } - - /* If there are VUSES, add a dependence on virtual defs. */ - if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VUSE)) - { - add_value_to_list (tab, (value_expr_p *)&(tab->version_info[version]), - VIRTUAL_PARTITION (tab)); - add_value_to_list (tab, - &(tab->partition_dep_list[VIRTUAL_PARTITION (tab)]), - version); - bitmap_set_bit (tab->partition_in_use, VIRTUAL_PARTITION (tab)); - } - - return true; -} - - -/* This function will remove the expression for VERSION from replacement - consideration.n table TAB If 'replace' is true, it is marked as - replaceable, otherwise not. */ - -static void -finish_expr (temp_expr_table_p tab, int version, bool replace) -{ - value_expr_p info, tmp; - int partition; - - /* Remove this expression from its dependent lists. The partition dependence - list is retained and transfered later to whomever uses this version. */ - for (info = (value_expr_p) tab->version_info[version]; info; info = tmp) - { - partition = info->value; - gcc_assert (tab->partition_dep_list[partition]); - tmp = remove_value_from_list (&(tab->partition_dep_list[partition]), - version); - gcc_assert (tmp); - free_value_expr (tab, tmp); - /* Only clear the bit when the dependency list is emptied via - a replacement. Otherwise kill_expr will take care of it. */ - if (!(tab->partition_dep_list[partition]) && replace) - bitmap_clear_bit (tab->partition_in_use, partition); - tmp = info->next; - if (!replace) - free_value_expr (tab, info); - } - - if (replace) - { - tab->saw_replaceable = true; - bitmap_set_bit (tab->replaceable, version); - } - else - { - gcc_assert (!bitmap_bit_p (tab->replaceable, version)); - tab->version_info[version] = NULL; - } -} - - -/* Mark the expression associated with VAR as replaceable, and enter - the defining stmt into the version_info table TAB. */ - -static void -mark_replaceable (temp_expr_table_p tab, tree var) -{ - value_expr_p info; - int version = SSA_NAME_VERSION (var); - finish_expr (tab, version, true); - - /* Move the dependence list to the pending list. */ - if (tab->version_info[version]) - { - info = (value_expr_p) tab->version_info[version]; - for ( ; info->next; info = info->next) - continue; - info->next = tab->pending_dependence; - tab->pending_dependence = (value_expr_p)tab->version_info[version]; - } - - tab->version_info[version] = SSA_NAME_DEF_STMT (var); -} - - -/* This function marks any expression in TAB which is dependent on PARTITION - as NOT replaceable. CLEAR_BIT is used to determine whether partition_in_use - should have its bit cleared. Since this routine can be called within an - EXECUTE_IF_SET_IN_BITMAP, the bit can't always be cleared. */ - -static inline void -kill_expr (temp_expr_table_p tab, int partition, bool clear_bit) -{ - value_expr_p ptr; - - /* Mark every active expr dependent on this var as not replaceable. */ - while ((ptr = tab->partition_dep_list[partition]) != NULL) - finish_expr (tab, ptr->value, false); - - if (clear_bit) - bitmap_clear_bit (tab->partition_in_use, partition); -} - - -/* This function kills all expressions in TAB which are dependent on virtual - DEFs. CLEAR_BIT determines whether partition_in_use gets cleared. */ - -static inline void -kill_virtual_exprs (temp_expr_table_p tab, bool clear_bit) -{ - kill_expr (tab, VIRTUAL_PARTITION (tab), clear_bit); -} - - -/* This function processes basic block BB, and looks for variables which can - be replaced by their expressions. Results are stored in TAB. */ - -static void -find_replaceable_in_bb (temp_expr_table_p tab, basic_block bb) -{ - block_stmt_iterator bsi; - tree stmt, def; - stmt_ann_t ann; - int partition; - var_map map = tab->map; - value_expr_p p; - ssa_op_iter iter; - - for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) - { - stmt = bsi_stmt (bsi); - ann = stmt_ann (stmt); - - /* Determine if this stmt finishes an existing expression. */ - FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_USE) - { - if (tab->version_info[SSA_NAME_VERSION (def)]) - { - bool same_root_var = false; - tree def2; - ssa_op_iter iter2; - - /* See if the root variables are the same. If they are, we - do not want to do the replacement to avoid problems with - code size, see PR tree-optimization/17549. */ - FOR_EACH_SSA_TREE_OPERAND (def2, stmt, iter2, SSA_OP_DEF) - if (SSA_NAME_VAR (def) == SSA_NAME_VAR (def2)) - { - same_root_var = true; - break; - } - - /* Mark expression as replaceable unless stmt is volatile - or DEF sets the same root variable as STMT. */ - if (!ann->has_volatile_ops && !same_root_var) - mark_replaceable (tab, def); - else - finish_expr (tab, SSA_NAME_VERSION (def), false); - } - } - - /* Next, see if this stmt kills off an active expression. */ - FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF) - { - partition = var_to_partition (map, def); - if (partition != NO_PARTITION && tab->partition_dep_list[partition]) - kill_expr (tab, partition, true); - } - - /* Now see if we are creating a new expression or not. */ - if (!ann->has_volatile_ops) - check_replaceable (tab, stmt); - - /* Free any unused dependency lists. */ - while ((p = tab->pending_dependence)) - { - tab->pending_dependence = p->next; - free_value_expr (tab, p); - } - - /* A V_{MAY,MUST}_DEF kills any expression using a virtual operand. */ - if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS)) - kill_virtual_exprs (tab, true); - } -} - - -/* This function is the driver routine for replacement of temporary expressions - in the SSA->normal phase, operating on MAP. If there are replaceable - expressions, a table is returned which maps SSA versions to the - expressions they should be replaced with. A NULL_TREE indicates no - replacement should take place. If there are no replacements at all, - NULL is returned by the function, otherwise an expression vector indexed - by SSA_NAME version numbers. */ - -static tree * -find_replaceable_exprs (var_map map) -{ - basic_block bb; - unsigned i; - temp_expr_table_p table; - tree *ret; - - table = new_temp_expr_table (map); - FOR_EACH_BB (bb) - { - bitmap_iterator bi; - - find_replaceable_in_bb (table, bb); - EXECUTE_IF_SET_IN_BITMAP ((table->partition_in_use), 0, i, bi) - { - kill_expr (table, i, false); - } - } - - ret = free_temp_expr_table (table); - return ret; -} - - -/* Dump TER expression table EXPR to file F. */ - -static void -dump_replaceable_exprs (FILE *f, tree *expr) -{ - tree stmt, var; - int x; - fprintf (f, "\nReplacing Expressions\n"); - for (x = 0; x < (int)num_ssa_names + 1; x++) - if (expr[x]) - { - stmt = expr[x]; - var = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF); - gcc_assert (var != NULL_TREE); - print_generic_expr (f, var, TDF_SLIM); - fprintf (f, " replace with --> "); - print_generic_expr (f, TREE_OPERAND (stmt, 1), TDF_SLIM); - fprintf (f, "\n"); - } - fprintf (f, "\n"); -} - - -/* This function will rewrite the current program using the variable mapping - found in MAP. If the replacement vector VALUES is provided, any - occurrences of partitions with non-null entries in the vector will be - replaced with the expression in the vector instead of its mapped - variable. */ - -static void -rewrite_trees (var_map map, tree *values) -{ - elim_graph g; - basic_block bb; - block_stmt_iterator si; - edge e; - tree phi; - bool changed; - -#ifdef ENABLE_CHECKING - /* Search for PHIs where the destination has no partition, but one - or more arguments has a partition. This should not happen and can - create incorrect code. */ - FOR_EACH_BB (bb) - { - tree phi; - - for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) - { - tree T0 = var_to_partition_to_var (map, PHI_RESULT (phi)); - - if (T0 == NULL_TREE) - { - int i; - - for (i = 0; i < PHI_NUM_ARGS (phi); i++) - { - tree arg = PHI_ARG_DEF (phi, i); - - if (TREE_CODE (arg) == SSA_NAME - && var_to_partition (map, arg) != NO_PARTITION) - { - fprintf (stderr, "Argument of PHI is in a partition :("); - print_generic_expr (stderr, arg, TDF_SLIM); - fprintf (stderr, "), but the result is not :"); - print_generic_stmt (stderr, phi, TDF_SLIM); - internal_error ("SSA corruption"); - } - } - } - } - } -#endif - - /* Replace PHI nodes with any required copies. */ - g = new_elim_graph (map->num_partitions); - g->map = map; - FOR_EACH_BB (bb) - { - for (si = bsi_start (bb); !bsi_end_p (si); ) - { - tree stmt = bsi_stmt (si); - use_operand_p use_p, copy_use_p; - def_operand_p def_p; - bool remove = false, is_copy = false; - int num_uses = 0; - stmt_ann_t ann; - ssa_op_iter iter; - - ann = stmt_ann (stmt); - changed = false; - - if (TREE_CODE (stmt) == MODIFY_EXPR - && (TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME)) - is_copy = true; - - copy_use_p = NULL_USE_OPERAND_P; - FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE) - { - if (replace_use_variable (map, use_p, values)) - changed = true; - copy_use_p = use_p; - num_uses++; - } - - if (num_uses != 1) - is_copy = false; - - def_p = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF); - - if (def_p != NULL) - { - /* Mark this stmt for removal if it is the list of replaceable - expressions. */ - if (values && values[SSA_NAME_VERSION (DEF_FROM_PTR (def_p))]) - remove = true; - else - { - if (replace_def_variable (map, def_p, NULL)) - changed = true; - /* If both SSA_NAMEs coalesce to the same variable, - mark the now redundant copy for removal. */ - if (is_copy) - { - gcc_assert (copy_use_p != NULL_USE_OPERAND_P); - if (DEF_FROM_PTR (def_p) == USE_FROM_PTR (copy_use_p)) - remove = true; - } - } - } - else - FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_DEF) - if (replace_def_variable (map, def_p, NULL)) - changed = true; - - /* Remove any stmts marked for removal. */ - if (remove) - bsi_remove (&si, true); - else - bsi_next (&si); - } - - phi = phi_nodes (bb); - if (phi) - { - edge_iterator ei; - FOR_EACH_EDGE (e, ei, bb->preds) - eliminate_phi (e, g); - } - } - - delete_elim_graph (g); -} - - -DEF_VEC_ALLOC_P(edge,heap); - -/* These are the local work structures used to determine the best place to - insert the copies that were placed on edges by the SSA->normal pass.. */ -static VEC(edge,heap) *edge_leader; -static VEC(tree,heap) *stmt_list; -static bitmap leader_has_match = NULL; -static edge leader_match = NULL; - - -/* Pass this function to make_forwarder_block so that all the edges with - matching PENDING_STMT lists to 'curr_stmt_list' get redirected. */ -static bool -same_stmt_list_p (edge e) -{ - return (e->aux == (PTR) leader_match) ? true : false; -} - - -/* Return TRUE if S1 and S2 are equivalent copies. */ -static inline bool -identical_copies_p (tree s1, tree s2) -{ -#ifdef ENABLE_CHECKING - gcc_assert (TREE_CODE (s1) == MODIFY_EXPR); - gcc_assert (TREE_CODE (s2) == MODIFY_EXPR); - gcc_assert (DECL_P (TREE_OPERAND (s1, 0))); - gcc_assert (DECL_P (TREE_OPERAND (s2, 0))); -#endif - - if (TREE_OPERAND (s1, 0) != TREE_OPERAND (s2, 0)) - return false; - - s1 = TREE_OPERAND (s1, 1); - s2 = TREE_OPERAND (s2, 1); - - if (s1 != s2) - return false; - - return true; -} - - -/* Compare the PENDING_STMT list for two edges, and return true if the lists - contain the same sequence of copies. */ - -static inline bool -identical_stmt_lists_p (edge e1, edge e2) -{ - tree t1 = PENDING_STMT (e1); - tree t2 = PENDING_STMT (e2); - tree_stmt_iterator tsi1, tsi2; - - gcc_assert (TREE_CODE (t1) == STATEMENT_LIST); - gcc_assert (TREE_CODE (t2) == STATEMENT_LIST); - - for (tsi1 = tsi_start (t1), tsi2 = tsi_start (t2); - !tsi_end_p (tsi1) && !tsi_end_p (tsi2); - tsi_next (&tsi1), tsi_next (&tsi2)) - { - if (!identical_copies_p (tsi_stmt (tsi1), tsi_stmt (tsi2))) - break; - } - - if (!tsi_end_p (tsi1) || ! tsi_end_p (tsi2)) - return false; - - return true; -} - - -/* Allocate data structures used in analyze_edges_for_bb. */ - -static void -init_analyze_edges_for_bb (void) -{ - edge_leader = VEC_alloc (edge, heap, 25); - stmt_list = VEC_alloc (tree, heap, 25); - leader_has_match = BITMAP_ALLOC (NULL); -} - - -/* Free data structures used in analyze_edges_for_bb. */ - -static void -fini_analyze_edges_for_bb (void) -{ - VEC_free (edge, heap, edge_leader); - VEC_free (tree, heap, stmt_list); - BITMAP_FREE (leader_has_match); -} - - -/* Look at all the incoming edges to block BB, and decide where the best place - to insert the stmts on each edge are, and perform those insertions. Output - any debug information to DEBUG_FILE. */ - -static void -analyze_edges_for_bb (basic_block bb, FILE *debug_file) -{ - edge e; - edge_iterator ei; - int count; - unsigned int x; - bool have_opportunity; - block_stmt_iterator bsi; - tree stmt; - edge single_edge = NULL; - bool is_label; - edge leader; - - count = 0; - - /* Blocks which contain at least one abnormal edge cannot use - make_forwarder_block. Look for these blocks, and commit any PENDING_STMTs - found on edges in these block. */ - have_opportunity = true; - FOR_EACH_EDGE (e, ei, bb->preds) - if (e->flags & EDGE_ABNORMAL) - { - have_opportunity = false; - break; - } - - if (!have_opportunity) - { - FOR_EACH_EDGE (e, ei, bb->preds) - if (PENDING_STMT (e)) - bsi_commit_one_edge_insert (e, NULL); - return; - } - /* Find out how many edges there are with interesting pending stmts on them. - Commit the stmts on edges we are not interested in. */ - FOR_EACH_EDGE (e, ei, bb->preds) - { - if (PENDING_STMT (e)) - { - gcc_assert (!(e->flags & EDGE_ABNORMAL)); - if (e->flags & EDGE_FALLTHRU) - { - bsi = bsi_start (e->src); - if (!bsi_end_p (bsi)) - { - stmt = bsi_stmt (bsi); - bsi_next (&bsi); - gcc_assert (stmt != NULL_TREE); - is_label = (TREE_CODE (stmt) == LABEL_EXPR); - /* Punt if it has non-label stmts, or isn't local. */ - if (!is_label || DECL_NONLOCAL (TREE_OPERAND (stmt, 0)) - || !bsi_end_p (bsi)) - { - bsi_commit_one_edge_insert (e, NULL); - continue; - } - } - } - single_edge = e; - count++; - } - } - - /* If there aren't at least 2 edges, no sharing will happen. */ - if (count < 2) - { - if (single_edge) - bsi_commit_one_edge_insert (single_edge, NULL); - return; - } - - /* Ensure that we have empty worklists. */ -#ifdef ENABLE_CHECKING - gcc_assert (VEC_length (edge, edge_leader) == 0); - gcc_assert (VEC_length (tree, stmt_list) == 0); - gcc_assert (bitmap_empty_p (leader_has_match)); -#endif - - /* Find the "leader" block for each set of unique stmt lists. Preference is - given to FALLTHRU blocks since they would need a GOTO to arrive at another - block. The leader edge destination is the block which all the other edges - with the same stmt list will be redirected to. */ - have_opportunity = false; - FOR_EACH_EDGE (e, ei, bb->preds) - { - if (PENDING_STMT (e)) - { - bool found = false; - - /* Look for the same stmt list in edge leaders list. */ - for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++) - { - if (identical_stmt_lists_p (leader, e)) - { - /* Give this edge the same stmt list pointer. */ - PENDING_STMT (e) = NULL; - e->aux = leader; - bitmap_set_bit (leader_has_match, x); - have_opportunity = found = true; - break; - } - } - - /* If no similar stmt list, add this edge to the leader list. */ - if (!found) - { - VEC_safe_push (edge, heap, edge_leader, e); - VEC_safe_push (tree, heap, stmt_list, PENDING_STMT (e)); - } - } - } - - /* If there are no similar lists, just issue the stmts. */ - if (!have_opportunity) - { - for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++) - bsi_commit_one_edge_insert (leader, NULL); - VEC_truncate (edge, edge_leader, 0); - VEC_truncate (tree, stmt_list, 0); - bitmap_clear (leader_has_match); - return; - } - - - if (debug_file) - fprintf (debug_file, "\nOpportunities in BB %d for stmt/block reduction:\n", - bb->index); - - - /* For each common list, create a forwarding block and issue the stmt's - in that block. */ - for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++) - if (bitmap_bit_p (leader_has_match, x)) - { - edge new_edge; - block_stmt_iterator bsi; - tree curr_stmt_list; - - leader_match = leader; - - /* The tree_* cfg manipulation routines use the PENDING_EDGE field - for various PHI manipulations, so it gets cleared whhen calls are - made to make_forwarder_block(). So make sure the edge is clear, - and use the saved stmt list. */ - PENDING_STMT (leader) = NULL; - leader->aux = leader; - curr_stmt_list = VEC_index (tree, stmt_list, x); - - new_edge = make_forwarder_block (leader->dest, same_stmt_list_p, - NULL); - bb = new_edge->dest; - if (debug_file) - { - fprintf (debug_file, "Splitting BB %d for Common stmt list. ", - leader->dest->index); - fprintf (debug_file, "Original block is now BB%d.\n", bb->index); - print_generic_stmt (debug_file, curr_stmt_list, TDF_VOPS); - } - - FOR_EACH_EDGE (e, ei, new_edge->src->preds) - { - e->aux = NULL; - if (debug_file) - fprintf (debug_file, " Edge (%d->%d) lands here.\n", - e->src->index, e->dest->index); - } - - bsi = bsi_last (leader->dest); - bsi_insert_after (&bsi, curr_stmt_list, BSI_NEW_STMT); - - leader_match = NULL; - /* We should never get a new block now. */ - } - else - { - PENDING_STMT (leader) = VEC_index (tree, stmt_list, x); - bsi_commit_one_edge_insert (leader, NULL); - } - - - /* Clear the working data structures. */ - VEC_truncate (edge, edge_leader, 0); - VEC_truncate (tree, stmt_list, 0); - bitmap_clear (leader_has_match); -} - - -/* This function will analyze the insertions which were performed on edges, - and decide whether they should be left on that edge, or whether it is more - efficient to emit some subset of them in a single block. All stmts are - inserted somewhere, and if non-NULL, debug information is printed via - DUMP_FILE. */ - -static void -perform_edge_inserts (FILE *dump_file) -{ - basic_block bb; - - if (dump_file) - fprintf(dump_file, "Analyzing Edge Insertions.\n"); - - /* analyze_edges_for_bb calls make_forwarder_block, which tries to - incrementally update the dominator information. Since we don't - need dominator information after this pass, go ahead and free the - dominator information. */ - free_dominance_info (CDI_DOMINATORS); - free_dominance_info (CDI_POST_DOMINATORS); - - /* Allocate data structures used in analyze_edges_for_bb. */ - init_analyze_edges_for_bb (); - - FOR_EACH_BB (bb) - analyze_edges_for_bb (bb, dump_file); - - analyze_edges_for_bb (EXIT_BLOCK_PTR, dump_file); - - /* Free data structures used in analyze_edges_for_bb. */ - fini_analyze_edges_for_bb (); - -#ifdef ENABLE_CHECKING - { - edge_iterator ei; - edge e; - FOR_EACH_BB (bb) - { - FOR_EACH_EDGE (e, ei, bb->preds) - { - if (PENDING_STMT (e)) - error (" Pending stmts not issued on PRED edge (%d, %d)\n", - e->src->index, e->dest->index); - } - FOR_EACH_EDGE (e, ei, bb->succs) - { - if (PENDING_STMT (e)) - error (" Pending stmts not issued on SUCC edge (%d, %d)\n", - e->src->index, e->dest->index); - } - } - FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs) - { - if (PENDING_STMT (e)) - error (" Pending stmts not issued on ENTRY edge (%d, %d)\n", - e->src->index, e->dest->index); - } - FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds) - { - if (PENDING_STMT (e)) - error (" Pending stmts not issued on EXIT edge (%d, %d)\n", - e->src->index, e->dest->index); - } - } -#endif -} - - -/* Remove the variables specified in MAP from SSA form. Any debug information - is sent to DUMP. FLAGS indicate what options should be used. */ - -static void -remove_ssa_form (FILE *dump, var_map map, int flags) -{ - tree_live_info_p liveinfo; - basic_block bb; - tree phi, next; - FILE *save; - tree *values = NULL; - - save = dump_file; - dump_file = dump; - - /* If we are not combining temps, don't calculate live ranges for variables - with only one SSA version. */ - if ((flags & SSANORM_COMBINE_TEMPS) == 0) - compact_var_map (map, VARMAP_NO_SINGLE_DEFS); - else - compact_var_map (map, VARMAP_NORMAL); - - if (dump_file && (dump_flags & TDF_DETAILS)) - dump_var_map (dump_file, map); - - liveinfo = coalesce_ssa_name (map, flags); - - /* Make sure even single occurrence variables are in the list now. */ - if ((flags & SSANORM_COMBINE_TEMPS) == 0) - compact_var_map (map, VARMAP_NORMAL); - - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "After Coalescing:\n"); - dump_var_map (dump_file, map); - } - - if (flags & SSANORM_PERFORM_TER) - { - values = find_replaceable_exprs (map); - if (values && dump_file && (dump_flags & TDF_DETAILS)) - dump_replaceable_exprs (dump_file, values); - } - - /* Assign real variables to the partitions now. */ - assign_vars (map); - - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "After Root variable replacement:\n"); - dump_var_map (dump_file, map); - } - - if ((flags & SSANORM_COMBINE_TEMPS) && liveinfo) - { - coalesce_vars (map, liveinfo); - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "After variable memory coalescing:\n"); - dump_var_map (dump_file, map); - } - } - - if (liveinfo) - delete_tree_live_info (liveinfo); - - rewrite_trees (map, values); - - if (values) - free (values); - - /* Remove phi nodes which have been translated back to real variables. */ - FOR_EACH_BB (bb) - { - for (phi = phi_nodes (bb); phi; phi = next) - { - next = PHI_CHAIN (phi); - remove_phi_node (phi, NULL_TREE); - } - } - - /* we no longer maintain the SSA operand cache at this point. */ - fini_ssa_operands (); - - /* If any copies were inserted on edges, analyze and insert them now. */ - perform_edge_inserts (dump_file); - - dump_file = save; -} - -/* Search every PHI node for arguments associated with backedges which - we can trivially determine will need a copy (the argument is either - not an SSA_NAME or the argument has a different underlying variable - than the PHI result). - - Insert a copy from the PHI argument to a new destination at the - end of the block with the backedge to the top of the loop. Update - the PHI argument to reference this new destination. */ + Insert a copy from the PHI argument to a new destination at the + end of the block with the backedge to the top of the loop. Update + the PHI argument to reference this new destination. */ static void insert_backedge_copies (void) { basic_block bb; + gimple_stmt_iterator gsi; FOR_EACH_BB (bb) { - tree phi; + /* Mark block as possibly needing calculation of UIDs. */ + bb->aux = &bb->aux; - for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) + for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) { - tree result = PHI_RESULT (phi); + gimple phi = gsi_stmt (gsi); + tree result = gimple_phi_result (phi); tree result_var; - int i; + size_t i; if (!is_gimple_reg (result)) continue; result_var = SSA_NAME_VAR (result); - for (i = 0; i < PHI_NUM_ARGS (phi); i++) + for (i = 0; i < gimple_phi_num_args (phi); i++) { - tree arg = PHI_ARG_DEF (phi, i); - edge e = PHI_ARG_EDGE (phi, i); - - /* If the argument is not an SSA_NAME, then we will - need a constant initialization. If the argument is - an SSA_NAME with a different underlying variable and - we are not combining temporaries, then we will - need a copy statement. */ + tree arg = gimple_phi_arg_def (phi, i); + edge e = gimple_phi_arg_edge (phi, i); + + /* If the argument is not an SSA_NAME, then we will need a + constant initialization. If the argument is an SSA_NAME with + a different underlying variable then a copy statement will be + needed. */ if ((e->flags & EDGE_DFS_BACK) && (TREE_CODE (arg) != SSA_NAME - || (!flag_tree_combine_temps - && SSA_NAME_VAR (arg) != result_var))) + || SSA_NAME_VAR (arg) != result_var + || trivially_conflicts_p (bb, result, arg))) { - tree stmt, name, last = NULL; - block_stmt_iterator bsi; + tree name; + gimple stmt, last = NULL; + gimple_stmt_iterator gsi2; - bsi = bsi_last (PHI_ARG_EDGE (phi, i)->src); - if (!bsi_end_p (bsi)) - last = bsi_stmt (bsi); + gsi2 = gsi_last_bb (gimple_phi_arg_edge (phi, i)->src); + if (!gsi_end_p (gsi2)) + last = gsi_stmt (gsi2); /* In theory the only way we ought to get back to the start of a loop should be with a COND_EXPR or GOTO_EXPR. However, better safe than sorry. - If the block ends with a control statement or something that might throw, then we have to insert this assignment before the last @@ -2469,37 +984,50 @@ insert_backedge_copies (void) continue; } - /* Create a new instance of the underlying - variable of the PHI result. */ - stmt = build2 (MODIFY_EXPR, TREE_TYPE (result_var), - NULL_TREE, PHI_ARG_DEF (phi, i)); + /* Create a new instance of the underlying variable of the + PHI result. */ + stmt = gimple_build_assign (result_var, + gimple_phi_arg_def (phi, i)); name = make_ssa_name (result_var, stmt); - TREE_OPERAND (stmt, 0) = name; + gimple_assign_set_lhs (stmt, name); /* Insert the new statement into the block and update the PHI node. */ if (last && stmt_ends_bb_p (last)) - bsi_insert_before (&bsi, stmt, BSI_NEW_STMT); + gsi_insert_before (&gsi2, stmt, GSI_NEW_STMT); else - bsi_insert_after (&bsi, stmt, BSI_NEW_STMT); + gsi_insert_after (&gsi2, stmt, GSI_NEW_STMT); SET_PHI_ARG_DEF (phi, i, name); } } } + + /* Unmark this block again. */ + bb->aux = NULL; } } -/* Take the current function out of SSA form, as described in +/* Free all memory associated with going out of SSA form. SA is + the outof-SSA info object. */ + +void +finish_out_of_ssa (struct ssaexpand *sa) +{ + free (sa->partition_to_pseudo); + if (sa->values) + BITMAP_FREE (sa->values); + delete_var_map (sa->map); + BITMAP_FREE (sa->partition_has_default_def); + memset (sa, 0, sizeof *sa); +} + +/* Take the current function out of SSA form, translating PHIs as described in R. Morgan, ``Building an Optimizing Compiler'', Butterworth-Heinemann, Boston, MA, 1998. pp 176-186. */ -static void -rewrite_out_of_ssa (void) +unsigned int +rewrite_out_of_ssa (struct ssaexpand *sa) { - var_map map; - int var_flags = 0; - int ssa_flags = 0; - /* If elimination of a PHI requires inserting a copy on a backedge, then we will have to split the backedge which has numerous undesirable performance effects. @@ -2508,56 +1036,17 @@ rewrite_out_of_ssa (void) copies into the loop itself. */ insert_backedge_copies (); - if (!flag_tree_live_range_split) - ssa_flags |= SSANORM_COALESCE_PARTITIONS; - - eliminate_virtual_phis (); - - if (dump_file && (dump_flags & TDF_DETAILS)) - dump_tree_cfg (dump_file, dump_flags & ~TDF_DETAILS); - - /* We cannot allow unssa to un-gimplify trees before we instrument them. */ - if (flag_tree_ter && !flag_mudflap) - var_flags = SSA_VAR_MAP_REF_COUNT; - map = create_ssa_var_map (var_flags); + /* Eliminate PHIs which are of no use, such as virtual or dead phis. */ + eliminate_useless_phis (); - if (flag_tree_combine_temps) - ssa_flags |= SSANORM_COMBINE_TEMPS; - if (flag_tree_ter && !flag_mudflap) - ssa_flags |= SSANORM_PERFORM_TER; + if (dump_file && (dump_flags & TDF_DETAILS)) + gimple_dump_cfg (dump_file, dump_flags & ~TDF_DETAILS); - remove_ssa_form (dump_file, map, ssa_flags); + remove_ssa_form (flag_tree_ter, sa); if (dump_file && (dump_flags & TDF_DETAILS)) - dump_tree_cfg (dump_file, dump_flags & ~TDF_DETAILS); + gimple_dump_cfg (dump_file, dump_flags & ~TDF_DETAILS); - /* Flush out flow graph and SSA data. */ - delete_var_map (map); - - in_ssa_p = false; + return 0; } - - -/* Define the parameters of the out of SSA pass. */ - -struct tree_opt_pass pass_del_ssa = -{ - "optimized", /* name */ - NULL, /* gate */ - rewrite_out_of_ssa, /* execute */ - NULL, /* sub */ - NULL, /* next */ - 0, /* static_pass_number */ - TV_TREE_SSA_TO_NORMAL, /* tv_id */ - PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ - 0, /* properties_provided */ - /* ??? If TER is enabled, we also kill gimple. */ - PROP_ssa, /* properties_destroyed */ - TODO_verify_ssa | TODO_verify_flow - | TODO_verify_stmts, /* todo_flags_start */ - TODO_dump_func - | TODO_ggc_collect - | TODO_remove_unused_locals, /* todo_flags_finish */ - 0 /* letter */ -};