/* 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 <amacleod@redhat.com>
This file is part of GCC.
#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.
/* 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;
/* 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;
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));
/* Insert a copy instruction from partition SRC to DEST onto edge E. */
static void
-insert_partition_copy_on_edge (edge e, int dest, int src)
+insert_partition_copy_on_edge (edge e, int dest, int src, source_location locus)
{
rtx seq;
if (dump_file && (dump_flags & TDF_DETAILS))
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],
onto edge E. */
static void
-insert_value_copy_on_edge (edge e, int dest, tree src)
+insert_value_copy_on_edge (edge e, int dest, tree src, source_location locus)
{
rtx seq, x;
- enum machine_mode mode;
+ enum machine_mode dest_mode, src_mode;
+ int unsignedp;
+ tree var;
+
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file,
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);
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)));
+
+ 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 ();
onto edge E. */
static void
-insert_rtx_to_part_on_edge (edge e, int dest, rtx src, int unsignedsrcp)
+insert_rtx_to_part_on_edge (edge e, int dest, rtx src, int unsignedsrcp,
+ source_location locus)
{
rtx seq;
if (dump_file && (dump_flags & TDF_DETAILS))
}
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);
seq = emit_partition_copy (SA.partition_to_pseudo[dest],
src,
onto edge E. */
static void
-insert_part_to_rtx_on_edge (edge e, rtx dest, int src)
+insert_part_to_rtx_on_edge (edge e, rtx dest, int src, source_location locus)
{
rtx seq;
if (dump_file && (dump_flags & TDF_DETAILS))
}
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],
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);
{
VEC_truncate (int, g->nodes, 0);
VEC_truncate (int, g->edge_list, 0);
+ VEC_truncate (source_location, g->edge_locus, 0);
}
VEC_free (tree, heap, g->const_copies);
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);
}
/* 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);
}
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;
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;
}
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_; \
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)
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_; \
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)
for (gsi = gsi_start_phis (g->e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
{
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. */
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
on this edge. */
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
{
{
eliminate_name (g, p0);
eliminate_name (g, pi);
- elim_graph_add_edge (g, p0, pi);
+ elim_graph_add_edge (g, p0, pi, locus);
}
}
}
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);
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;
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_partition_copy_on_edge (g->e, P, T);
+ insert_partition_copy_on_edge (g->e, P, T, locus);
}
});
}
{
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);
+ 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))));
elim_create (elim_graph g, int T)
{
int P, S;
+ source_location locus;
if (elim_unvisited_predecessor (g, 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,
+ 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_rtx_to_part_on_edge (g->e, P, U, unsignedsrcp);
+ 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_partition_copy_on_edge (g->e, T, S);
+ insert_partition_copy_on_edge (g->e, T, S, locus);
}
}
}
int x;
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)
{
int dest;
tree src;
+ source_location locus;
+
src = VEC_pop (tree, g->const_copies);
dest = VEC_pop (int, g->const_dests);
- insert_value_copy_on_edge (e, dest, src);
+ locus = VEC_pop (source_location, g->copy_locus);
+ insert_value_copy_on_edge (e, dest, src, locus);
}
}
}
+/* If not already done so for basic block BB, assign increasing uids
+ to each of its instructions. */
+
+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))
+ {
+ gimple stmt = gsi_stmt (gsi);
+ gimple_set_uid (stmt, i);
+ i++;
+ }
+}
+
+
+/* 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;
+}
+
+
/* 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
FOR_EACH_BB (bb)
{
+ /* Mark block as possibly needing calculation of UIDs. */
+ bb->aux = &bb->aux;
+
for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
{
gimple phi = gsi_stmt (gsi);
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 name;
gimple stmt, last = NULL;
name = make_ssa_name (result_var, stmt);
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))
}
}
}
+
+ /* Unmark this block again. */
+ bb->aux = NULL;
}
}
OSDN Git Service
