X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Ftree-outof-ssa.c;h=d3901c34f0e76945de53ee25a3995e7aa63e4985;hb=db899978cbb5a0ffe7e7ddf741c5c61f949f28d2;hp=be8a459f40270c7a8964a53f9b8c1abe0a8a00ee;hpb=aa620173eb5c350ab316602f970010b450786b35;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/tree-outof-ssa.c b/gcc/tree-outof-ssa.c index be8a459f402..d3901c34f0e 100644 --- a/gcc/tree-outof-ssa.c +++ b/gcc/tree-outof-ssa.c @@ -1,5 +1,6 @@ /* Convert a program in SSA form into Normal form. - Copyright (C) 2004, 2005, 2006, 2007, 2008 Free Software Foundation, Inc. + Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009 + Free Software Foundation, Inc. Contributed by Andrew Macleod This file is part of GCC. @@ -30,11 +31,15 @@ along with GCC; see the file COPYING3. If not see #include "tree-flow.h" #include "timevar.h" #include "tree-dump.h" -#include "tree-ssa-live.h" #include "tree-pass.h" #include "toplev.h" +#include "expr.h" +#include "ssaexpand.h" +DEF_VEC_I(source_location); +DEF_VEC_ALLOC_I(source_location,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 edges represented as pairs of nodes. @@ -61,11 +66,14 @@ 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; + /* Source locus on each edge */ + VEC(source_location,heap) *edge_locus; + /* Visited vector. */ sbitmap visited; @@ -79,87 +87,225 @@ 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; + + /* Source locations for any constant copies. */ + VEC(source_location,heap) *copy_locus; } *elim_graph; -/* Create a temporary variable based on the type of variable T. Use T's name - as the prefix. */ +/* 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 tree -create_temp (tree t) +static void +set_location_for_edge (edge e) { - tree tmp; - const char *name = NULL; - tree type; + 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; - if (TREE_CODE (t) == SSA_NAME) - t = SSA_NAME_VAR (t); + do + { + for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi)) + { + gimple stmt = gsi_stmt (gsi); + if (is_gimple_debug (stmt)) + continue; + 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); + } +} - gcc_assert (TREE_CODE (t) == VAR_DECL || TREE_CODE (t) == PARM_DECL); +/* Emit insns to copy SRC into DEST converting SRC if necessary. */ - type = TREE_TYPE (t); - tmp = DECL_NAME (t); - if (tmp) - name = IDENTIFIER_POINTER (tmp); +static inline rtx +emit_partition_copy (rtx dest, rtx src, int unsignedsrcp) +{ + rtx seq; + + start_sequence (); + + 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); + + seq = get_insns (); + end_sequence (); + + 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, source_location locus) +{ + 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); + /* If a locus is provided, override the default. */ + if (locus) + set_curr_insn_source_location (locus); + + 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, source_location locus) +{ + rtx seq, x; + enum machine_mode dest_mode, src_mode; + int unsignedp; + tree var; + + 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); - DECL_GIMPLE_REG_P (tmp) = DECL_GIMPLE_REG_P (t); - add_referenced_var (tmp); - - /* add_referenced_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. */ - set_symbol_mem_tag (tmp, symbol_mem_tag (t)); - 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); + /* If a locus is provided, override the default. */ + if (locus) + set_curr_insn_source_location (locus); -/* This helper function fill insert a copy from a constant or variable SRC to - variable DEST on edge E. */ + start_sequence (); + + var = SSA_NAME_VAR (partition_to_var (SA.map, dest)); + src_mode = TYPE_MODE (TREE_TYPE (src)); + dest_mode = promote_decl_mode (var, &unsignedp); + gcc_assert (src_mode == TYPE_MODE (TREE_TYPE (var))); + gcc_assert (dest_mode == GET_MODE (SA.partition_to_pseudo[dest])); + + if (src_mode != dest_mode) + { + x = expand_expr (src, NULL, src_mode, EXPAND_NORMAL); + x = convert_modes (dest_mode, src_mode, x, unsignedp); + } + else + x = expand_expr (src, SA.partition_to_pseudo[dest], + dest_mode, EXPAND_NORMAL); + + 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); +} + +/* 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, + source_location locus) { - 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"); + } + + gcc_assert (SA.partition_to_pseudo[dest]); - copy = build_gimple_modify_stmt (dest, src); - set_is_used (dest); + set_location_for_edge (e); + /* If a locus is provided, override the default. */ + if (locus) + set_curr_insn_source_location (locus); - 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, source_location locus) +{ + 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); + /* If a locus is provided, override the default. */ + if (locus) + set_curr_insn_source_location (locus); + + 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); } @@ -171,9 +317,12 @@ 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->copy_locus = VEC_alloc (source_location, heap, 10); g->edge_list = VEC_alloc (int, heap, 20); + g->edge_locus = VEC_alloc (source_location, heap, 10); g->stack = VEC_alloc (int, heap, 30); g->visited = sbitmap_alloc (size); @@ -187,8 +336,9 @@ 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); + VEC_truncate (source_location, g->edge_locus, 0); } @@ -201,7 +351,11 @@ 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); + VEC_free (source_location, heap, g->copy_locus); + VEC_free (source_location, heap, g->edge_locus); + free (g); } @@ -211,32 +365,33 @@ 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); } /* Add the edge PRED->SUCC to graph G. */ static inline void -elim_graph_add_edge (elim_graph g, int pred, int succ) +elim_graph_add_edge (elim_graph g, int pred, int succ, source_location locus) { VEC_safe_push (int, heap, g->edge_list, pred); VEC_safe_push (int, heap, g->edge_list, succ); + VEC_safe_push (source_location, heap, g->edge_locus, locus); } @@ -244,7 +399,7 @@ elim_graph_add_edge (elim_graph g, int pred, int succ) return the successor node. -1 is returned if there is no such edge. */ static inline int -elim_graph_remove_succ_edge (elim_graph g, int node) +elim_graph_remove_succ_edge (elim_graph g, int node, source_location *locus) { int y; unsigned x; @@ -254,8 +409,11 @@ elim_graph_remove_succ_edge (elim_graph g, int node) VEC_replace (int, g->edge_list, x, -1); y = VEC_index (int, g->edge_list, x + 1); VEC_replace (int, g->edge_list, x + 1, -1); + *locus = VEC_index (source_location, g->edge_locus, x / 2); + VEC_replace (source_location, g->edge_locus, x / 2, UNKNOWN_LOCATION); return y; } + *locus = UNKNOWN_LOCATION; return -1; } @@ -264,7 +422,7 @@ elim_graph_remove_succ_edge (elim_graph g, int node) edge list. VAR will hold the partition number found. CODE is the code fragment executed for every node found. */ -#define FOR_EACH_ELIM_GRAPH_SUCC(GRAPH, NODE, VAR, CODE) \ +#define FOR_EACH_ELIM_GRAPH_SUCC(GRAPH, NODE, VAR, LOCUS, CODE) \ do { \ unsigned x_; \ int y_; \ @@ -274,6 +432,7 @@ do { \ if (y_ != (NODE)) \ continue; \ (VAR) = VEC_index (int, (GRAPH)->edge_list, x_ + 1); \ + (LOCUS) = VEC_index (source_location, (GRAPH)->edge_locus, x_ / 2); \ CODE; \ } \ } while (0) @@ -283,7 +442,7 @@ do { \ GRAPH. VAR will hold the partition number found. CODE is the code fragment executed for every node found. */ -#define FOR_EACH_ELIM_GRAPH_PRED(GRAPH, NODE, VAR, CODE) \ +#define FOR_EACH_ELIM_GRAPH_PRED(GRAPH, NODE, VAR, LOCUS, CODE) \ do { \ unsigned x_; \ int y_; \ @@ -293,6 +452,7 @@ do { \ if (y_ != (NODE)) \ continue; \ (VAR) = VEC_index (int, (GRAPH)->edge_list, x_); \ + (LOCUS) = VEC_index (source_location, (GRAPH)->edge_locus, x_ / 2); \ CODE; \ } \ } while (0) @@ -301,7 +461,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); } @@ -311,23 +471,26 @@ 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); + source_location locus; + + 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); + locus = gimple_phi_arg_location_from_edge (phi, g->e); /* If this argument is a constant, or a SSA_NAME which is being left in SSA form, just queue a copy to be emitted on this @@ -338,19 +501,18 @@ 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); + VEC_safe_push (source_location, heap, g->copy_locus, locus); } 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); - elim_graph_add_edge (g, p0, pi); + eliminate_name (g, p0); + eliminate_name (g, pi); + elim_graph_add_edge (g, p0, pi, locus); } } } @@ -363,8 +525,10 @@ static void elim_forward (elim_graph g, int T) { int S; + source_location locus; + SET_BIT (g->visited, T); - FOR_EACH_ELIM_GRAPH_SUCC (g, T, S, + FOR_EACH_ELIM_GRAPH_SUCC (g, T, S, locus, { if (!TEST_BIT (g->visited, S)) elim_forward (g, S); @@ -379,7 +543,9 @@ static int elim_unvisited_predecessor (elim_graph g, int T) { int P; - FOR_EACH_ELIM_GRAPH_PRED (g, T, P, + source_location locus; + + FOR_EACH_ELIM_GRAPH_PRED (g, T, P, locus, { if (!TEST_BIT (g->visited, P)) return 1; @@ -393,53 +559,69 @@ static void elim_backward (elim_graph g, int T) { int P; + source_location locus; + SET_BIT (g->visited, T); - FOR_EACH_ELIM_GRAPH_PRED (g, T, P, + FOR_EACH_ELIM_GRAPH_PRED (g, T, P, locus, { 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, locus); } }); } +/* 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; + enum machine_mode reg_mode = promote_decl_mode (var, &unsignedp); + 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; + source_location locus; 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)); - FOR_EACH_ELIM_GRAPH_PRED (g, T, P, + 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, UNKNOWN_LOCATION); + FOR_EACH_ELIM_GRAPH_PRED (g, T, P, locus, { 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, locus); } }); } else { - S = elim_graph_remove_succ_edge (g, T); + S = elim_graph_remove_succ_edge (g, T, &locus); 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, locus); } } - } @@ -449,9 +631,9 @@ 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); + gcc_assert (VEC_length (source_location, g->copy_locus) == 0); /* Abnormal edges already have everything coalesced. */ if (e->flags & EDGE_ABNORMAL) @@ -459,20 +641,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); @@ -487,145 +668,82 @@ 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; + source_location locus; + 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); + locus = VEC_pop (source_location, g->copy_locus); + insert_value_copy_on_edge (e, dest, src, locus); } } -/* Take the ssa-name var_map MAP, and assign real variables to each - partition. */ +/* 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 -assign_vars (var_map map) +remove_gimple_phi_args (gimple phi) { - int x, num; - tree var, root; - var_ann_t ann; + use_operand_p arg_p; + ssa_op_iter iter; - num = num_var_partitions (map); - for (x = 0; x < num; x++) + if (dump_file && (dump_flags & TDF_DETAILS)) { - var = partition_to_var (map, x); - if (TREE_CODE (var) != SSA_NAME) - { - ann = var_ann (var); - /* It must already be coalesced. */ - gcc_assert (ann->out_of_ssa_tag == 1); - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "partition %d already has variable ", x); - print_generic_expr (dump_file, var, TDF_SLIM); - fprintf (dump_file, " assigned to it.\n"); - } - } - else - { - root = SSA_NAME_VAR (var); - ann = var_ann (root); - /* If ROOT is already associated, create a new one. */ - if (ann->out_of_ssa_tag) - { - root = create_temp (root); - ann = var_ann (root); - } - /* ROOT has not been coalesced yet, so use it. */ - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "Partition %d is assigned to var ", x); - print_generic_stmt (dump_file, root, TDF_SLIM); - } - change_partition_var (map, root, x); - } + fprintf (dump_file, "Removing Dead PHI definition: "); + print_gimple_stmt (dump_file, phi, 0, TDF_SLIM); } -} - -/* 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. */ - -static inline bool -replace_use_variable (var_map map, use_operand_p p, tree *expr) -{ - tree new_var; - tree var = USE_FROM_PTR (p); - - /* Check if we are replacing this variable with an expression. */ - if (expr) + FOR_EACH_PHI_ARG (arg_p, phi, iter, SSA_OP_USE) { - int version = SSA_NAME_VERSION (var); - if (expr[version]) + tree arg = USE_FROM_PTR (arg_p); + if (TREE_CODE (arg) == SSA_NAME) { - tree new_expr = GIMPLE_STMT_OPERAND (expr[version], 1); - SET_USE (p, new_expr); - - /* Clear the stmt's RHS, or GC might bite us. */ - GIMPLE_STMT_OPERAND (expr[version], 1) = NULL_TREE; - return true; - } - } - - new_var = var_to_partition_to_var (map, var); - if (new_var) - { - SET_USE (p, new_var); - set_is_used (new_var); - 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. */ + /* Remove the reference to the existing argument. */ + SET_USE (arg_p, NULL_TREE); + if (has_zero_uses (arg)) + { + gimple stmt; + gimple_stmt_iterator gsi; -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); + stmt = SSA_NAME_DEF_STMT (arg); - /* Do nothing if we are replacing this variable with an expression. */ - if (expr && expr[SSA_NAME_VERSION (var)]) - return true; + /* Also remove the def if it is a PHI node. */ + if (gimple_code (stmt) == GIMPLE_PHI) + { + remove_gimple_phi_args (stmt); + gsi = gsi_for_stmt (stmt); + remove_phi_node (&gsi, 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. */ +/* Remove any PHI node which is a virtual PHI, or a PHI with no uses. */ static void -eliminate_virtual_phis (void) +eliminate_useless_phis (void) { basic_block bb; - tree phi, next; + gimple_stmt_iterator gsi; + tree result; FOR_EACH_BB (bb) { - for (phi = phi_nodes (bb); phi; phi = next) + for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); ) { - next = PHI_CHAIN (phi); - if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi)))) + gimple phi = gsi_stmt (gsi); + result = gimple_phi_result (phi); + if (!is_gimple_reg (SSA_NAME_VAR (result))) { #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++) + 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 @@ -634,12 +752,23 @@ eliminate_virtual_phis (void) 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); + print_gimple_stmt (stderr, phi, 0, TDF_SLIM); internal_error ("SSA corruption"); } } #endif - remove_phi_node (phi, NULL_TREE, true); + remove_phi_node (&gsi, true); + } + else + { + /* 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); } } } @@ -653,29 +782,24 @@ eliminate_virtual_phis (void) variable. */ static void -rewrite_trees (var_map map, tree *values) +rewrite_trees (var_map map ATTRIBUTE_UNUSED) { - elim_graph g; - basic_block bb; - block_stmt_iterator si; - edge e; - tree phi; - bool changed; - #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) { - tree phi; - for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) + gimple_stmt_iterator gsi; + for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) { - tree T0 = var_to_partition_to_var (map, PHI_RESULT (phi)); + gimple phi = gsi_stmt (gsi); + tree T0 = var_to_partition_to_var (map, gimple_phi_result (phi)); if (T0 == NULL_TREE) { - int i; - for (i = 0; i < PHI_NUM_ARGS (phi); i++) + size_t i; + for (i = 0; i < gimple_phi_num_args (phi); i++) { tree arg = PHI_ARG_DEF (phi, i); @@ -685,7 +809,7 @@ rewrite_trees (var_map map, tree *values) 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); + print_gimple_stmt (stderr, phi, 0, TDF_SLIM); internal_error ("SSA corruption"); } } @@ -693,597 +817,54 @@ rewrite_trees (var_map map, tree *values) } } #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) == GIMPLE_MODIFY_STMT - && (TREE_CODE (GIMPLE_STMT_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 - { - if (changed) - if (maybe_clean_or_replace_eh_stmt (stmt, stmt)) - tree_purge_dead_eh_edges (bb); - 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); -} - -/* 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. E is the - edge to test for a match. */ - -static inline 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 (const_tree s1, const_tree s2) -{ -#ifdef ENABLE_CHECKING - gcc_assert (TREE_CODE (s1) == GIMPLE_MODIFY_STMT); - gcc_assert (TREE_CODE (s2) == GIMPLE_MODIFY_STMT); - gcc_assert (DECL_P (GIMPLE_STMT_OPERAND (s1, 0))); - gcc_assert (DECL_P (GIMPLE_STMT_OPERAND (s2, 0))); -#endif - - if (GIMPLE_STMT_OPERAND (s1, 0) != GIMPLE_STMT_OPERAND (s2, 0)) - return false; - - s1 = GIMPLE_STMT_OPERAND (s1, 1); - s2 = GIMPLE_STMT_OPERAND (s2, 1); - - if (s1 != s2) - return false; - - return true; -} - - -/* Compare the PENDING_STMT list for edges E1 and E2. Return true if the lists - contain the same sequence of copies. */ - -static inline bool -identical_stmt_lists_p (const_edge e1, const_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); -} - -/* A helper function to be called via walk_tree. Return DATA if it is - contained in subtree TP. */ - -static tree -contains_tree_r (tree * tp, int *walk_subtrees, void *data) -{ - if (*tp == data) - { - *walk_subtrees = 0; - return data; - } - else - return NULL_TREE; -} - -/* A threshold for the number of insns contained in the latch block. - It is used to prevent blowing the loop with too many copies from - the latch. */ -#define MAX_STMTS_IN_LATCH 2 - -/* Return TRUE if the stmts on SINGLE-EDGE can be moved to the - body of the loop. This should be permitted only if SINGLE-EDGE is a - single-basic-block latch edge and thus cleaning the latch will help - to create a single-basic-block loop. Otherwise return FALSE. */ - -static bool -process_single_block_loop_latch (edge single_edge) -{ - tree stmts; - basic_block b_exit, b_pheader, b_loop = single_edge->src; - edge_iterator ei; - edge e; - block_stmt_iterator bsi, bsi_exit; - tree_stmt_iterator tsi; - tree expr, stmt; - unsigned int count = 0; - - if (single_edge == NULL || (single_edge->dest != single_edge->src) - || (EDGE_COUNT (b_loop->succs) != 2) - || (EDGE_COUNT (b_loop->preds) != 2)) - return false; - - /* Get the stmts on the latch edge. */ - stmts = PENDING_STMT (single_edge); - - /* Find the successor edge which is not the latch edge. */ - FOR_EACH_EDGE (e, ei, b_loop->succs) - if (e->dest != b_loop) - break; - - b_exit = e->dest; - - /* Check that the exit block has only the loop as a predecessor, - and that there are no pending stmts on that edge as well. */ - if (EDGE_COUNT (b_exit->preds) != 1 || PENDING_STMT (e)) - return false; - - /* Find the predecessor edge which is not the latch edge. */ - FOR_EACH_EDGE (e, ei, b_loop->preds) - if (e->src != b_loop) - break; - - b_pheader = e->src; - - if (b_exit == b_pheader || b_exit == b_loop || b_pheader == b_loop) - return false; - - bsi_exit = bsi_after_labels (b_exit); - - /* Get the last stmt in the loop body. */ - bsi = bsi_last (single_edge->src); - stmt = bsi_stmt (bsi); - - if (TREE_CODE (stmt) != COND_EXPR) - return false; - - expr = COND_EXPR_COND (stmt); - /* Iterate over the insns on the latch and count them. */ - for (tsi = tsi_start (stmts); !tsi_end_p (tsi); tsi_next (&tsi)) - { - tree stmt1 = tsi_stmt (tsi); - tree var; - - count++; - /* Check that the condition does not contain any new definition - created in the latch as the stmts from the latch intended - to precede it. */ - if (TREE_CODE (stmt1) != GIMPLE_MODIFY_STMT) - return false; - var = GIMPLE_STMT_OPERAND (stmt1, 0); - if (TREE_THIS_VOLATILE (var) - || TYPE_VOLATILE (TREE_TYPE (var)) - || walk_tree (&expr, contains_tree_r, var, NULL)) - return false; - } - /* Check that the latch does not contain more than MAX_STMTS_IN_LATCH - insns. The purpose of this restriction is to prevent blowing the - loop with too many copies from the latch. */ - if (count > MAX_STMTS_IN_LATCH) - return false; - - /* Apply the transformation - clean up the latch block: - - var = something; - L1: - x1 = expr; - if (cond) goto L2 else goto L3; - L2: - var = x1; - goto L1 - L3: - ... - - ==> - - var = something; - L1: - x1 = expr; - tmp_var = var; - var = x1; - if (cond) goto L1 else goto L2; - L2: - var = tmp_var; - ... - */ - for (tsi = tsi_start (stmts); !tsi_end_p (tsi); tsi_next (&tsi)) - { - tree stmt1 = tsi_stmt (tsi); - tree var, tmp_var, copy; - - /* Create a new variable to load back the value of var in case - we exit the loop. */ - var = GIMPLE_STMT_OPERAND (stmt1, 0); - tmp_var = create_temp (var); - copy = build2 (GIMPLE_MODIFY_STMT, TREE_TYPE (tmp_var), tmp_var, var); - set_is_used (tmp_var); - bsi_insert_before (&bsi, copy, BSI_SAME_STMT); - copy = build2 (GIMPLE_MODIFY_STMT, TREE_TYPE (tmp_var), var, tmp_var); - bsi_insert_before (&bsi_exit, copy, BSI_SAME_STMT); - } - - PENDING_STMT (single_edge) = 0; - /* Insert the new stmts to the loop body. */ - bsi_insert_before (&bsi, stmts, BSI_NEW_STMT); - - if (dump_file) - fprintf (dump_file, - "\nCleaned-up latch block of loop with single BB: %d\n\n", - single_edge->dest->index); - - return true; -} - -/* 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. */ - -static void -analyze_edges_for_bb (basic_block bb) -{ - 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) - { - /* Add stmts to the edge unless processed specially as a - single-block loop latch edge. */ - if (!process_single_block_loop_latch (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 (dump_file) - fprintf (dump_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 when 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 (dump_file) - { - fprintf (dump_file, "Splitting BB %d for Common stmt list. ", - leader->dest->index); - fprintf (dump_file, "Original block is now BB%d.\n", bb->index); - print_generic_stmt (dump_file, curr_stmt_list, TDF_VOPS); - } - - FOR_EACH_EDGE (e, ei, new_edge->src->preds) - { - e->aux = NULL; - if (dump_file) - fprintf (dump_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); } +/* 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. */ -/* 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. */ - -static void -perform_edge_inserts (void) +void +expand_phi_nodes (struct ssaexpand *sa) { basic_block bb; + elim_graph g = new_elim_graph (sa->map->num_partitions); + g->map = sa->map; - 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); - - analyze_edges_for_bb (EXIT_BLOCK_PTR); - - /* 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_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 (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); + 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); } } - 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 + + delete_elim_graph (g); } @@ -1292,12 +873,11 @@ perform_edge_inserts (void) should also be used. */ static void -remove_ssa_form (bool perform_ter) +remove_ssa_form (bool perform_ter, struct ssaexpand *sa) { - basic_block bb; - tree phi, next; - tree *values = NULL; + bitmap values = NULL; var_map map; + unsigned i; map = coalesce_ssa_name (); @@ -1318,34 +898,82 @@ remove_ssa_form (bool perform_ter) dump_replaceable_exprs (dump_file, values); } - /* Assign real variables to the partitions now. */ - assign_vars (map); + rewrite_trees (map); - if (dump_file && (dump_flags & TDF_DETAILS)) + sa->map = map; + sa->values = values; + sa->partition_has_default_def = BITMAP_ALLOC (NULL); + for (i = 1; i < num_ssa_names; i++) { - fprintf (dump_file, "After Base variable replacement:\n"); - dump_var_map (dump_file, map); + tree t = ssa_name (i); + if (t && SSA_NAME_IS_DEFAULT_DEF (t)) + { + int p = var_to_partition (map, t); + if (p != NO_PARTITION) + bitmap_set_bit (sa->partition_has_default_def, p); + } } +} - rewrite_trees (map, values); - if (values) - free (values); +/* If not already done so for basic block BB, assign increasing uids + to each of its instructions. */ - /* Remove PHI nodes which have been translated back to real variables. */ - FOR_EACH_BB (bb) +static void +maybe_renumber_stmts_bb (basic_block bb) +{ + unsigned i = 0; + gimple_stmt_iterator gsi; + + if (!bb->aux) + return; + bb->aux = NULL; + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) { - for (phi = phi_nodes (bb); phi; phi = next) - { - next = PHI_CHAIN (phi); - remove_phi_node (phi, NULL_TREE, true); - } + gimple stmt = gsi_stmt (gsi); + gimple_set_uid (stmt, i); + i++; } +} - /* If any copies were inserted on edges, analyze and insert them now. */ - perform_edge_inserts (); - delete_var_map (map); +/* 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 bool +trivially_conflicts_p (basic_block bb, tree result, tree arg) +{ + use_operand_p use; + imm_use_iterator imm_iter; + gimple defa = SSA_NAME_DEF_STMT (arg); + + /* If ARG isn't defined in the same block it's too complicated for + our little mind. */ + if (gimple_bb (defa) != bb) + return false; + + FOR_EACH_IMM_USE_FAST (use, imm_iter, result) + { + 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; } @@ -1362,25 +990,28 @@ 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); + 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 @@ -1388,14 +1019,16 @@ insert_backedge_copies (void) needed. */ if ((e->flags & EDGE_DFS_BACK) && (TREE_CODE (arg) != SSA_NAME - || 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. @@ -1416,30 +1049,52 @@ insert_backedge_copies (void) /* Create a new instance of the underlying variable of the PHI result. */ - stmt = build_gimple_modify_stmt (NULL_TREE, - PHI_ARG_DEF (phi, i)); + stmt = gimple_build_assign (result_var, + gimple_phi_arg_def (phi, i)); name = make_ssa_name (result_var, stmt); - GIMPLE_STMT_OPERAND (stmt, 0) = name; + gimple_assign_set_lhs (stmt, name); + + /* copy location if present. */ + if (gimple_phi_arg_has_location (phi, i)) + gimple_set_location (stmt, + gimple_phi_arg_location (phi, i)); /* 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; } } +/* 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 unsigned int -rewrite_out_of_ssa (void) +unsigned int +rewrite_out_of_ssa (struct ssaexpand *sa) { /* If elimination of a PHI requires inserting a copy on a backedge, then we will have to split the backedge which has numerous @@ -1449,40 +1104,17 @@ rewrite_out_of_ssa (void) copies into the loop itself. */ insert_backedge_copies (); - eliminate_virtual_phis (); + + /* Eliminate PHIs which are of no use, such as virtual or dead phis. */ + eliminate_useless_phis (); 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); - remove_ssa_form (flag_tree_ter && !flag_mudflap); + 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); - cfun->gimple_df->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 */ -};