/* Miscellaneous SSA utility functions.
- Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
+ Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007 Free Software Foundation, Inc.
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
-the Free Software Foundation; either version 2, or (at your option)
+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,
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, 59 Temple Place - Suite 330,
-Boston, MA 02111-1307, USA. */
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
#include "config.h"
#include "system.h"
#include "hard-reg-set.h"
#include "basic-block.h"
#include "output.h"
-#include "errors.h"
#include "expr.h"
#include "function.h"
#include "diagnostic.h"
#include "hashtab.h"
#include "tree-dump.h"
#include "tree-pass.h"
+#include "toplev.h"
+
+/* Pointer map of variable mappings, keyed by edge. */
+static struct pointer_map_t *edge_var_maps;
+
+
+/* Add a mapping with PHI RESULT and PHI DEF associated with edge E. */
+
+void
+redirect_edge_var_map_add (edge e, tree result, tree def)
+{
+ void **slot;
+ edge_var_map_vector old_head, head;
+ edge_var_map new_node;
+
+ if (edge_var_maps == NULL)
+ edge_var_maps = pointer_map_create ();
+
+ slot = pointer_map_insert (edge_var_maps, e);
+ old_head = head = *slot;
+ if (!head)
+ {
+ head = VEC_alloc (edge_var_map, heap, 5);
+ *slot = head;
+ }
+ new_node.def = def;
+ new_node.result = result;
+
+ VEC_safe_push (edge_var_map, heap, head, &new_node);
+ if (old_head != head)
+ {
+ /* The push did some reallocation. Update the pointer map. */
+ *slot = head;
+ }
+}
+
+
+/* Clear the var mappings in edge E. */
+
+void
+redirect_edge_var_map_clear (edge e)
+{
+ void **slot;
+ edge_var_map_vector head;
+
+ if (!edge_var_maps)
+ return;
+
+ slot = pointer_map_contains (edge_var_maps, e);
+
+ if (slot)
+ {
+ head = *slot;
+ VEC_free (edge_var_map, heap, head);
+ *slot = NULL;
+ }
+}
+
+
+/* Duplicate the redirected var mappings in OLDE in NEWE.
+
+ Since we can't remove a mapping, let's just duplicate it. This assumes a
+ pointer_map can have multiple edges mapping to the same var_map (many to
+ one mapping), since we don't remove the previous mappings. */
+
+void
+redirect_edge_var_map_dup (edge newe, edge olde)
+{
+ void **new_slot, **old_slot; edge_var_map_vector head;
+
+ if (!edge_var_maps)
+ return;
+
+ new_slot = pointer_map_insert (edge_var_maps, newe);
+ old_slot = pointer_map_contains (edge_var_maps, olde);
+ if (!old_slot)
+ return;
+ head = *old_slot;
+
+ if (head)
+ *new_slot = VEC_copy (edge_var_map, heap, head);
+ else
+ *new_slot = VEC_alloc (edge_var_map, heap, 5);
+}
+
+
+/* Return the varable mappings for a given edge. If there is none, return
+ NULL. */
+
+edge_var_map_vector
+redirect_edge_var_map_vector (edge e)
+{
+ void **slot;
+
+ /* Hey, what kind of idiot would... you'd be surprised. */
+ if (!edge_var_maps)
+ return NULL;
+
+ slot = pointer_map_contains (edge_var_maps, e);
+ if (!slot)
+ return NULL;
+
+ return (edge_var_map_vector) *slot;
+}
+
+
+/* Clear the edge variable mappings. */
+
+void
+redirect_edge_var_map_destroy (void)
+{
+ if (edge_var_maps)
+ {
+ pointer_map_destroy (edge_var_maps);
+ edge_var_maps = NULL;
+ }
+}
+
/* Remove the corresponding arguments from the PHI nodes in E's
destination block and redirect it to DEST. Return redirected edge.
- The list of removed arguments is stored in PENDING_STMT (e). */
+ The list of removed arguments is stored in a vector accessed
+ through edge_var_maps. */
edge
ssa_redirect_edge (edge e, basic_block dest)
{
- tree phi, next;
- tree list = NULL, *last = &list;
- tree src, dst, node;
+ tree phi;
+
+ redirect_edge_var_map_clear (e);
/* Remove the appropriate PHI arguments in E's destination block. */
- for (phi = phi_nodes (e->dest); phi; phi = next)
+ for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
{
- next = PHI_CHAIN (phi);
+ tree def = PHI_ARG_DEF (phi, e->dest_idx);
- if (PHI_ARG_DEF (phi, e->dest_idx) == NULL_TREE)
+ if (def == NULL_TREE)
continue;
- src = PHI_ARG_DEF (phi, e->dest_idx);
- dst = PHI_RESULT (phi);
- node = build_tree_list (dst, src);
- *last = node;
- last = &TREE_CHAIN (node);
+ redirect_edge_var_map_add (e, PHI_RESULT (phi), def);
}
e = redirect_edge_succ_nodup (e, dest);
- PENDING_STMT (e) = list;
return e;
}
-/* Add PHI arguments queued in PENDINT_STMT list on edge E to edge
+/* Add PHI arguments queued in PENDING_STMT list on edge E to edge
E->dest. */
void
flush_pending_stmts (edge e)
{
- tree phi, arg;
+ tree phi;
+ edge_var_map_vector v;
+ edge_var_map *vm;
+ int i;
- if (!PENDING_STMT (e))
+ v = redirect_edge_var_map_vector (e);
+ if (!v)
return;
- for (phi = phi_nodes (e->dest), arg = PENDING_STMT (e);
- phi;
- phi = PHI_CHAIN (phi), arg = TREE_CHAIN (arg))
+ for (phi = phi_nodes (e->dest), i = 0;
+ phi && VEC_iterate (edge_var_map, v, i, vm);
+ phi = PHI_CHAIN (phi), i++)
{
- tree def = TREE_VALUE (arg);
+ tree def = redirect_edge_var_map_def (vm);
add_phi_arg (phi, def, e);
}
- PENDING_STMT (e) = NULL;
+ redirect_edge_var_map_clear (e);
}
/* Return true if SSA_NAME is malformed and mark it visited.
static bool
verify_ssa_name (tree ssa_name, bool is_virtual)
{
- TREE_VISITED (ssa_name) = 1;
-
if (TREE_CODE (ssa_name) != SSA_NAME)
{
- error ("Expected an SSA_NAME object");
+ error ("expected an SSA_NAME object");
return true;
}
if (TREE_TYPE (ssa_name) != TREE_TYPE (SSA_NAME_VAR (ssa_name)))
{
- error ("Type mismatch between an SSA_NAME and its symbol.");
+ error ("type mismatch between an SSA_NAME and its symbol");
return true;
}
if (SSA_NAME_IN_FREE_LIST (ssa_name))
{
- error ("Found an SSA_NAME that had been released into the free pool");
+ error ("found an SSA_NAME that had been released into the free pool");
return true;
}
if (is_virtual && is_gimple_reg (ssa_name))
{
- error ("Found a virtual definition for a GIMPLE register");
+ error ("found a virtual definition for a GIMPLE register");
return true;
}
if (!is_virtual && !is_gimple_reg (ssa_name))
{
- error ("Found a real definition for a non-register");
+ error ("found a real definition for a non-register");
+ return true;
+ }
+
+ if (is_virtual && var_ann (SSA_NAME_VAR (ssa_name))
+ && get_subvars_for_var (SSA_NAME_VAR (ssa_name)) != NULL)
+ {
+ error ("found real variable when subvariables should have appeared");
+ return true;
+ }
+
+ if (SSA_NAME_IS_DEFAULT_DEF (ssa_name)
+ && !IS_EMPTY_STMT (SSA_NAME_DEF_STMT (ssa_name)))
+ {
+ error ("found a default name with a non-empty defining statement");
return true;
}
it means that the block in that array slot contains the
definition of SSA_NAME.
- IS_VIRTUAL is true if SSA_NAME is created by a V_MAY_DEF or a
- V_MUST_DEF. */
+ IS_VIRTUAL is true if SSA_NAME is created by a VDEF. */
static bool
verify_def (basic_block bb, basic_block *definition_block, tree ssa_name,
is flowing through an abnormal edge (only used when checking PHI
arguments).
- IS_VIRTUAL is true if SSA_NAME is created by a V_MAY_DEF or a
- V_MUST_DEF.
-
If NAMES_DEFINED_IN_BB is not NULL, it contains a bitmap of ssa names
that are defined before STMT in basic block BB. */
static bool
-verify_use (basic_block bb, basic_block def_bb, tree ssa_name,
- tree stmt, bool check_abnormal, bool is_virtual,
- bitmap names_defined_in_bb)
+verify_use (basic_block bb, basic_block def_bb, use_operand_p use_p,
+ tree stmt, bool check_abnormal, bitmap names_defined_in_bb)
{
bool err = false;
+ tree ssa_name = USE_FROM_PTR (use_p);
+
+ if (!TREE_VISITED (ssa_name))
+ if (verify_imm_links (stderr, ssa_name))
+ err = true;
- err = verify_ssa_name (ssa_name, is_virtual);
+ TREE_VISITED (ssa_name) = 1;
if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (ssa_name))
- && var_ann (SSA_NAME_VAR (ssa_name))->default_def == ssa_name)
+ && SSA_NAME_IS_DEFAULT_DEF (ssa_name))
; /* Default definitions have empty statements. Nothing to do. */
else if (!def_bb)
{
- error ("Missing definition");
+ error ("missing definition");
err = true;
}
else if (bb != def_bb
&& !dominated_by_p (CDI_DOMINATORS, bb, def_bb))
{
- error ("Definition in block %i does not dominate use in block %i",
+ error ("definition in block %i does not dominate use in block %i",
def_bb->index, bb->index);
err = true;
}
&& names_defined_in_bb != NULL
&& !bitmap_bit_p (names_defined_in_bb, SSA_NAME_VERSION (ssa_name)))
{
- error ("Definition in block %i follows the use", def_bb->index);
+ error ("definition in block %i follows the use", def_bb->index);
err = true;
}
err = true;
}
+ /* Make sure the use is in an appropriate list by checking the previous
+ element to make sure it's the same. */
+ if (use_p->prev == NULL)
+ {
+ error ("no immediate_use list");
+ err = true;
+ }
+ else
+ {
+ tree listvar ;
+ if (use_p->prev->use == NULL)
+ listvar = use_p->prev->stmt;
+ else
+ listvar = USE_FROM_PTR (use_p->prev);
+ if (listvar != ssa_name)
+ {
+ error ("wrong immediate use list");
+ err = true;
+ }
+ }
+
if (err)
{
fprintf (stderr, "for SSA_NAME: ");
print_generic_expr (stderr, ssa_name, TDF_VOPS);
- fprintf (stderr, "in statement:\n");
+ fprintf (stderr, " in statement:\n");
print_generic_stmt (stderr, stmt, TDF_VOPS);
}
/* Return true if any of the arguments for PHI node PHI at block BB is
malformed.
- DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME version
- numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set, it means that the
- block in that array slot contains the definition of SSA_NAME. */
+ DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME
+ version numbers. If DEFINITION_BLOCK[SSA_NAME_VERSION] is set,
+ it means that the block in that array slot contains the
+ definition of SSA_NAME. */
static bool
verify_phi_args (tree phi, basic_block bb, basic_block *definition_block)
if (EDGE_COUNT (bb->preds) != phi_num_args)
{
- error ("Incoming edge count does not match number of PHI arguments\n");
+ error ("incoming edge count does not match number of PHI arguments");
err = true;
goto error;
}
for (i = 0; i < phi_num_args; i++)
{
- tree op = PHI_ARG_DEF (phi, i);
+ use_operand_p op_p = PHI_ARG_DEF_PTR (phi, i);
+ tree op = USE_FROM_PTR (op_p);
e = EDGE_PRED (bb, i);
if (op == NULL_TREE)
{
- error ("PHI argument is missing for edge %d->%d\n",
+ error ("PHI argument is missing for edge %d->%d",
e->src->index,
e->dest->index);
err = true;
}
if (TREE_CODE (op) == SSA_NAME)
- err = verify_use (e->src, definition_block[SSA_NAME_VERSION (op)], op,
- phi, e->flags & EDGE_ABNORMAL,
- !is_gimple_reg (PHI_RESULT (phi)),
- NULL);
+ {
+ err = verify_ssa_name (op, !is_gimple_reg (PHI_RESULT (phi)));
+ err |= verify_use (e->src, definition_block[SSA_NAME_VERSION (op)],
+ op_p, phi, e->flags & EDGE_ABNORMAL, NULL);
+ }
if (e->dest != bb)
{
- error ("Wrong edge %d->%d for PHI argument\n",
- e->src->index, e->dest->index, bb->index);
+ error ("wrong edge %d->%d for PHI argument",
+ e->src->index, e->dest->index);
err = true;
}
if (err)
{
fprintf (stderr, "for PHI node\n");
- print_generic_stmt (stderr, phi, TDF_VOPS);
+ print_generic_stmt (stderr, phi, TDF_VOPS|TDF_MEMSYMS);
}
static void
verify_flow_insensitive_alias_info (void)
{
- size_t i;
tree var;
- bitmap visited = BITMAP_XMALLOC ();
+ referenced_var_iterator rvi;
- for (i = 0; i < num_referenced_vars; i++)
+ FOR_EACH_REFERENCED_VAR (var, rvi)
{
- size_t j;
- var_ann_t ann;
- varray_type may_aliases;
+ unsigned int j;
+ bitmap aliases;
+ tree alias;
+ bitmap_iterator bi;
- var = referenced_var (i);
- ann = var_ann (var);
- may_aliases = ann->may_aliases;
+ if (!MTAG_P (var) || !MTAG_ALIASES (var))
+ continue;
+
+ aliases = MTAG_ALIASES (var);
- for (j = 0; may_aliases && j < VARRAY_ACTIVE_SIZE (may_aliases); j++)
+ EXECUTE_IF_SET_IN_BITMAP (aliases, 0, j, bi)
{
- tree alias = VARRAY_TREE (may_aliases, j);
+ alias = referenced_var (j);
- bitmap_set_bit (visited, var_ann (alias)->uid);
-
- if (!may_be_aliased (alias))
+ if (TREE_CODE (alias) != MEMORY_PARTITION_TAG
+ && !may_be_aliased (alias))
{
- error ("Non-addressable variable inside an alias set.");
+ error ("non-addressable variable inside an alias set");
debug_variable (alias);
goto err;
}
}
}
- for (i = 0; i < num_referenced_vars; i++)
- {
- var_ann_t ann;
-
- var = referenced_var (i);
- ann = var_ann (var);
-
- if (ann->mem_tag_kind == NOT_A_TAG
- && ann->is_alias_tag
- && !bitmap_bit_p (visited, ann->uid))
- {
- error ("Addressable variable that is an alias tag but is not in any alias set.");
- goto err;
- }
- }
-
- BITMAP_XFREE (visited);
return;
err:
debug_variable (var);
- internal_error ("verify_flow_insensitive_alias_info failed.");
+ internal_error ("verify_flow_insensitive_alias_info failed");
}
continue;
ann = var_ann (var);
- if (pi->is_dereferenced && !pi->name_mem_tag && !ann->type_mem_tag)
+ if (pi->is_dereferenced && !pi->name_mem_tag && !ann->symbol_mem_tag)
{
- error ("Dereferenced pointers should have a name or a type tag");
+ error ("dereferenced pointers should have a name or a symbol tag");
goto err;
}
if (pi->name_mem_tag
- && !pi->pt_malloc
&& (pi->pt_vars == NULL || bitmap_empty_p (pi->pt_vars)))
{
- error ("Pointers with a memory tag, should have points-to sets or point to malloc");
+ error ("pointers with a memory tag, should have points-to sets");
goto err;
}
- if (pi->value_escapes_p
- && pi->name_mem_tag
- && !is_call_clobbered (pi->name_mem_tag))
+ if (pi->value_escapes_p && pi->name_mem_tag)
{
- error ("Pointer escapes but its name tag is not call-clobbered.");
- goto err;
+ tree t = memory_partition (pi->name_mem_tag);
+ if (t == NULL_TREE)
+ t = pi->name_mem_tag;
+
+ if (!is_call_clobbered (t))
+ {
+ error ("pointer escapes but its name tag is not call-clobbered");
+ goto err;
+ }
}
}
err:
debug_variable (ptr);
- internal_error ("verify_flow_sensitive_alias_info failed.");
+ internal_error ("verify_flow_sensitive_alias_info failed");
}
-DEF_VEC_MALLOC_P (bitmap);
-/* Verify that all name tags have different points to sets.
- This algorithm takes advantage of the fact that every variable with the
- same name tag must have the same points-to set.
- So we check a single variable for each name tag, and verify that its
- points-to set is different from every other points-to set for other name
- tags.
-
- Additionally, given a pointer P_i with name tag NMT and type tag
- TMT, this function verified the alias set of TMT is a superset of
- the alias set of NMT. */
+/* Verify the consistency of call clobbering information. */
static void
-verify_name_tags (void)
+verify_call_clobbering (void)
{
- size_t i;
- size_t j;
- bitmap first, second;
- VEC (tree) *name_tag_reps = NULL;
- VEC (bitmap) *pt_vars_for_reps = NULL;
- bitmap type_aliases = BITMAP_XMALLOC ();
-
- /* First we compute the name tag representatives and their points-to sets. */
- for (i = 0; i < num_ssa_names; i++)
+ unsigned int i;
+ bitmap_iterator bi;
+ tree var;
+ referenced_var_iterator rvi;
+
+ /* At all times, the result of the call_clobbered flag should
+ match the result of the call_clobbered_vars bitmap. Verify both
+ that everything in call_clobbered_vars is marked
+ call_clobbered, and that everything marked
+ call_clobbered is in call_clobbered_vars. */
+ EXECUTE_IF_SET_IN_BITMAP (gimple_call_clobbered_vars (cfun), 0, i, bi)
{
- struct ptr_info_def *pi;
- tree tmt, ptr = ssa_name (i);
+ var = referenced_var (i);
- if (ptr == NULL_TREE)
- continue;
-
- pi = SSA_NAME_PTR_INFO (ptr);
+ if (memory_partition (var))
+ var = memory_partition (var);
- if (!TREE_VISITED (ptr)
- || !POINTER_TYPE_P (TREE_TYPE (ptr))
- || !pi
- || !pi->name_mem_tag
- || TREE_VISITED (pi->name_mem_tag))
- continue;
-
- TREE_VISITED (pi->name_mem_tag) = 1;
+ if (!MTAG_P (var) && !var_ann (var)->call_clobbered)
+ {
+ error ("variable in call_clobbered_vars but not marked "
+ "call_clobbered");
+ debug_variable (var);
+ goto err;
+ }
+ }
- if (pi->pt_vars == NULL)
+ FOR_EACH_REFERENCED_VAR (var, rvi)
+ {
+ if (is_gimple_reg (var))
continue;
- VEC_safe_push (tree, name_tag_reps, ptr);
- VEC_safe_push (bitmap, pt_vars_for_reps, pi->pt_vars);
+ if (memory_partition (var))
+ var = memory_partition (var);
- /* Verify that alias set of PTR's type tag is a superset of the
- alias set of PTR's name tag. */
- tmt = var_ann (SSA_NAME_VAR (ptr))->type_mem_tag;
- if (tmt)
+ if (!MTAG_P (var)
+ && var_ann (var)->call_clobbered
+ && !bitmap_bit_p (gimple_call_clobbered_vars (cfun), DECL_UID (var)))
{
- size_t i;
- varray_type aliases = var_ann (tmt)->may_aliases;
- bitmap_clear (type_aliases);
- for (i = 0; aliases && i < VARRAY_ACTIVE_SIZE (aliases); i++)
- {
- tree alias = VARRAY_TREE (aliases, i);
- bitmap_set_bit (type_aliases, var_ann (alias)->uid);
- }
+ error ("variable marked call_clobbered but not in "
+ "call_clobbered_vars bitmap.");
+ debug_variable (var);
+ goto err;
+ }
+ }
+
+ return;
+
+ err:
+ internal_error ("verify_call_clobbering failed");
+}
- /* When grouping, we may have added PTR's type tag into the
- alias set of PTR's name tag. To prevent a false
- positive, pretend that TMT is in its own alias set. */
- bitmap_set_bit (type_aliases, var_ann (tmt)->uid);
- if (bitmap_equal_p (type_aliases, pi->pt_vars))
- continue;
+/* Verify invariants in memory partitions. */
- if (!bitmap_intersect_compl_p (type_aliases, pi->pt_vars))
+static void
+verify_memory_partitions (void)
+{
+ unsigned i;
+ tree mpt;
+ VEC(tree,heap) *mpt_table = gimple_ssa_operands (cfun)->mpt_table;
+ struct pointer_set_t *partitioned_syms = pointer_set_create ();
+
+ for (i = 0; VEC_iterate (tree, mpt_table, i, mpt); i++)
+ {
+ unsigned j;
+ bitmap_iterator bj;
+
+ if (MPT_SYMBOLS (mpt) == NULL)
+ {
+ error ("Memory partitions should have at least one symbol");
+ debug_variable (mpt);
+ goto err;
+ }
+
+ EXECUTE_IF_SET_IN_BITMAP (MPT_SYMBOLS (mpt), 0, j, bj)
+ {
+ tree var = referenced_var (j);
+ if (pointer_set_insert (partitioned_syms, var))
{
- error ("Alias set of a pointer's type tag should be a superset of the corresponding name tag");
- debug_variable (tmt);
- debug_variable (pi->name_mem_tag);
+ error ("Partitioned symbols should belong to exactly one "
+ "partition");
+ debug_variable (var);
goto err;
}
}
}
-
- /* Now compare all the representative bitmaps with all other representative
- bitmaps, to verify that they are all different. */
- for (i = 0; VEC_iterate (bitmap, pt_vars_for_reps, i, first); i++)
- {
- for (j = i + 1; VEC_iterate (bitmap, pt_vars_for_reps, j, second); j++)
- {
- if (bitmap_equal_p (first, second))
- {
- error ("Two different pointers with identical points-to sets but different name tags");
- debug_variable (VEC_index (tree, name_tag_reps, j));
- goto err;
- }
- }
- }
- /* Lastly, clear out the visited flags. */
- for (i = 0; i < num_ssa_names; i++)
- {
- if (ssa_name (i))
- {
- tree ptr = ssa_name (i);
- struct ptr_info_def *pi = SSA_NAME_PTR_INFO (ptr);
- if (!TREE_VISITED (ptr)
- || !POINTER_TYPE_P (TREE_TYPE (ptr))
- || !pi
- || !pi->name_mem_tag)
- continue;
- TREE_VISITED (pi->name_mem_tag) = 0;
- }
- }
+ pointer_set_destroy (partitioned_syms);
- VEC_free (bitmap, pt_vars_for_reps);
- BITMAP_FREE (type_aliases);
return;
-
+
err:
- debug_variable (VEC_index (tree, name_tag_reps, i));
- internal_error ("verify_name_tags failed");
+ internal_error ("verify_memory_partitions failed");
}
verify_alias_info (void)
{
verify_flow_sensitive_alias_info ();
- verify_name_tags ();
+ verify_call_clobbering ();
verify_flow_insensitive_alias_info ();
+ verify_memory_partitions ();
}
TODO: verify the variable annotations. */
void
-verify_ssa (void)
+verify_ssa (bool check_modified_stmt)
{
size_t i;
basic_block bb;
- basic_block *definition_block = xcalloc (num_ssa_names, sizeof (basic_block));
+ basic_block *definition_block = XCNEWVEC (basic_block, num_ssa_names);
ssa_op_iter iter;
tree op;
- enum dom_state orig_dom_state = dom_computed[CDI_DOMINATORS];
- bitmap names_defined_in_bb = BITMAP_XMALLOC ();
+ enum dom_state orig_dom_state = dom_info_state (CDI_DOMINATORS);
+ bitmap names_defined_in_bb = BITMAP_ALLOC (NULL);
+
+ gcc_assert (!need_ssa_update_p ());
+
+ verify_stmts ();
timevar_push (TV_TREE_SSA_VERIFY);
{
if (e->aux)
{
- error ("AUX pointer initialized for edge %d->%d\n", e->src->index,
+ error ("AUX pointer initialized for edge %d->%d", e->src->index,
e->dest->index);
goto err;
}
{
if (verify_phi_args (phi, bb, definition_block))
goto err;
+
bitmap_set_bit (names_defined_in_bb,
SSA_NAME_VERSION (PHI_RESULT (phi)));
}
for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
{
tree stmt = bsi_stmt (bsi);
+ use_operand_p use_p;
- get_stmt_operands (stmt);
+ if (check_modified_stmt && stmt_modified_p (stmt))
+ {
+ error ("stmt (%p) marked modified after optimization pass: ",
+ (void *)stmt);
+ print_generic_stmt (stderr, stmt, TDF_VOPS);
+ goto err;
+ }
+
+ if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
+ && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 0)) != SSA_NAME)
+ {
+ tree lhs, base_address;
- if (stmt_ann (stmt)->makes_aliased_stores
- && NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt)) == 0)
+ lhs = GIMPLE_STMT_OPERAND (stmt, 0);
+ base_address = get_base_address (lhs);
+
+ if (base_address
+ && gimple_aliases_computed_p (cfun)
+ && SSA_VAR_P (base_address)
+ && !stmt_ann (stmt)->has_volatile_ops
+ && ZERO_SSA_OPERANDS (stmt, SSA_OP_VDEF))
{
- error ("Statement makes aliased stores, but has no V_MAY_DEFS");
+ error ("statement makes a memory store, but has no VDEFS");
print_generic_stmt (stderr, stmt, TDF_VOPS);
goto err;
}
+ }
+
+ FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_VIRTUALS)
+ {
+ if (verify_ssa_name (op, true))
+ {
+ error ("in statement");
+ print_generic_stmt (stderr, stmt, TDF_VOPS|TDF_MEMSYMS);
+ goto err;
+ }
+ }
- FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_USES | SSA_OP_ALL_KILLS)
+ FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_USE|SSA_OP_DEF)
{
+ if (verify_ssa_name (op, false))
+ {
+ error ("in statement");
+ print_generic_stmt (stderr, stmt, TDF_VOPS|TDF_MEMSYMS);
+ goto err;
+ }
+ }
+
+ FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE|SSA_OP_VUSE)
+ {
+ op = USE_FROM_PTR (use_p);
if (verify_use (bb, definition_block[SSA_NAME_VERSION (op)],
- op, stmt, false, !is_gimple_reg (op),
- names_defined_in_bb))
+ use_p, stmt, false, names_defined_in_bb))
goto err;
}
FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_DEFS)
- {
- bitmap_set_bit (names_defined_in_bb, SSA_NAME_VERSION (op));
- }
+ bitmap_set_bit (names_defined_in_bb, SSA_NAME_VERSION (op));
}
bitmap_clear (names_defined_in_bb);
}
/* Finally, verify alias information. */
- verify_alias_info ();
+ if (gimple_aliases_computed_p (cfun))
+ verify_alias_info ();
free (definition_block);
+
/* Restore the dominance information to its prior known state, so
that we do not perturb the compiler's subsequent behavior. */
if (orig_dom_state == DOM_NONE)
free_dominance_info (CDI_DOMINATORS);
else
- dom_computed[CDI_DOMINATORS] = orig_dom_state;
+ set_dom_info_availability (CDI_DOMINATORS, orig_dom_state);
- BITMAP_XFREE (names_defined_in_bb);
+ BITMAP_FREE (names_defined_in_bb);
timevar_pop (TV_TREE_SSA_VERIFY);
return;
err:
- internal_error ("verify_ssa failed.");
+ internal_error ("verify_ssa failed");
+}
+
+/* Return true if the uid in both int tree maps are equal. */
+
+int
+int_tree_map_eq (const void *va, const void *vb)
+{
+ const struct int_tree_map *a = (const struct int_tree_map *) va;
+ const struct int_tree_map *b = (const struct int_tree_map *) vb;
+ return (a->uid == b->uid);
+}
+
+/* Hash a UID in a int_tree_map. */
+
+unsigned int
+int_tree_map_hash (const void *item)
+{
+ return ((const struct int_tree_map *)item)->uid;
+}
+
+/* Return true if the DECL_UID in both trees are equal. */
+
+int
+uid_decl_map_eq (const void *va, const void *vb)
+{
+ const_tree a = (const_tree) va;
+ const_tree b = (const_tree) vb;
+ return (a->decl_minimal.uid == b->decl_minimal.uid);
+}
+
+/* Hash a tree in a uid_decl_map. */
+
+unsigned int
+uid_decl_map_hash (const void *item)
+{
+ return ((const_tree)item)->decl_minimal.uid;
+}
+
+/* Return true if the uid in both int tree maps are equal. */
+
+static int
+var_ann_eq (const void *va, const void *vb)
+{
+ const struct static_var_ann_d *a = (const struct static_var_ann_d *) va;
+ const_tree const b = (const_tree) vb;
+ return (a->uid == DECL_UID (b));
+}
+
+/* Hash a UID in a int_tree_map. */
+
+static unsigned int
+var_ann_hash (const void *item)
+{
+ return ((const struct static_var_ann_d *)item)->uid;
+}
+
+/* Return true if the DECL_UID in both trees are equal. */
+
+static int
+uid_ssaname_map_eq (const void *va, const void *vb)
+{
+ const_tree a = (const_tree) va;
+ const_tree b = (const_tree) vb;
+ return (a->ssa_name.var->decl_minimal.uid == b->ssa_name.var->decl_minimal.uid);
+}
+
+/* Hash a tree in a uid_decl_map. */
+
+static unsigned int
+uid_ssaname_map_hash (const void *item)
+{
+ return ((const_tree)item)->ssa_name.var->decl_minimal.uid;
}
void
init_tree_ssa (void)
{
- VARRAY_TREE_INIT (referenced_vars, 20, "referenced_vars");
- call_clobbered_vars = BITMAP_XMALLOC ();
- addressable_vars = BITMAP_XMALLOC ();
- init_ssa_operands ();
+ cfun->gimple_df = GGC_CNEW (struct gimple_df);
+ cfun->gimple_df->referenced_vars = htab_create_ggc (20, uid_decl_map_hash,
+ uid_decl_map_eq, NULL);
+ cfun->gimple_df->default_defs = htab_create_ggc (20, uid_ssaname_map_hash,
+ uid_ssaname_map_eq, NULL);
+ cfun->gimple_df->var_anns = htab_create_ggc (20, var_ann_hash,
+ var_ann_eq, NULL);
+ cfun->gimple_df->call_clobbered_vars = BITMAP_GGC_ALLOC ();
+ cfun->gimple_df->addressable_vars = BITMAP_GGC_ALLOC ();
init_ssanames ();
init_phinodes ();
- global_var = NULL_TREE;
}
size_t i;
basic_block bb;
block_stmt_iterator bsi;
+ referenced_var_iterator rvi;
+ tree var;
+
+ /* Release any ssa_names still in use. */
+ for (i = 0; i < num_ssa_names; i++)
+ {
+ tree var = ssa_name (i);
+ if (var && TREE_CODE (var) == SSA_NAME)
+ {
+ SSA_NAME_IMM_USE_NODE (var).prev = &(SSA_NAME_IMM_USE_NODE (var));
+ SSA_NAME_IMM_USE_NODE (var).next = &(SSA_NAME_IMM_USE_NODE (var));
+ }
+ release_ssa_name (var);
+ }
/* Remove annotations from every tree in the function. */
FOR_EACH_BB (bb)
- for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
- {
- tree stmt = bsi_stmt (bsi);
- release_defs (stmt);
- ggc_free (stmt->common.ann);
- stmt->common.ann = NULL;
- }
-
- /* Remove annotations from every referenced variable. */
- if (referenced_vars)
{
- for (i = 0; i < num_referenced_vars; i++)
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
{
- tree var = referenced_var (i);
- ggc_free (var->common.ann);
- var->common.ann = NULL;
+ tree stmt = bsi_stmt (bsi);
+ stmt_ann_t ann = get_stmt_ann (stmt);
+
+ free_ssa_operands (&ann->operands);
+ ann->addresses_taken = 0;
+ mark_stmt_modified (stmt);
}
- referenced_vars = NULL;
+ set_phi_nodes (bb, NULL);
+ }
+
+ /* Remove annotations from every referenced variable. */
+ FOR_EACH_REFERENCED_VAR (var, rvi)
+ {
+ if (var->base.ann)
+ ggc_free (var->base.ann);
+ var->base.ann = NULL;
}
+ htab_delete (gimple_referenced_vars (cfun));
+ cfun->gimple_df->referenced_vars = NULL;
fini_ssanames ();
fini_phinodes ();
- fini_ssa_operands ();
+ /* we no longer maintain the SSA operand cache at this point. */
+ if (ssa_operands_active ())
+ fini_ssa_operands ();
- global_var = NULL_TREE;
- BITMAP_XFREE (call_clobbered_vars);
- call_clobbered_vars = NULL;
- BITMAP_XFREE (addressable_vars);
- addressable_vars = NULL;
-}
+ cfun->gimple_df->global_var = NULL_TREE;
+
+ htab_delete (cfun->gimple_df->default_defs);
+ cfun->gimple_df->default_defs = NULL;
+ htab_delete (cfun->gimple_df->var_anns);
+ cfun->gimple_df->var_anns = NULL;
+ cfun->gimple_df->call_clobbered_vars = NULL;
+ cfun->gimple_df->addressable_vars = NULL;
+ cfun->gimple_df->modified_noreturn_calls = NULL;
+ if (gimple_aliases_computed_p (cfun))
+ {
+ delete_alias_heapvars ();
+ gcc_assert (!need_ssa_update_p ());
+ }
+ cfun->gimple_df->aliases_computed_p = false;
+ delete_mem_ref_stats (cfun);
+ cfun->gimple_df = NULL;
-/* Return true if EXPR is a useless type conversion, otherwise return
- false. */
+ /* We no longer need the edge variable maps. */
+ redirect_edge_var_map_destroy ();
+}
-bool
-tree_ssa_useless_type_conversion_1 (tree outer_type, tree inner_type)
+/* Helper function for useless_type_conversion_p. */
+
+static bool
+useless_type_conversion_p_1 (tree outer_type, tree inner_type)
{
- /* If the inner and outer types are effectively the same, then
- strip the type conversion and enter the equivalence into
- the table. */
- if (inner_type == outer_type
- || (lang_hooks.types_compatible_p (inner_type, outer_type)))
- return true;
+ /* Qualifiers on value types do not matter. */
+ inner_type = TYPE_MAIN_VARIANT (inner_type);
+ outer_type = TYPE_MAIN_VARIANT (outer_type);
- /* If both types are pointers and the outer type is a (void *), then
- the conversion is not necessary. The opposite is not true since
- that conversion would result in a loss of information if the
- equivalence was used. Consider an indirect function call where
- we need to know the exact type of the function to correctly
- implement the ABI. */
- else if (POINTER_TYPE_P (inner_type)
- && POINTER_TYPE_P (outer_type)
- && TYPE_MODE (inner_type) == TYPE_MODE (outer_type)
- && TYPE_REF_CAN_ALIAS_ALL (inner_type)
- == TYPE_REF_CAN_ALIAS_ALL (outer_type)
- && TREE_CODE (TREE_TYPE (outer_type)) == VOID_TYPE)
+ if (inner_type == outer_type)
return true;
- /* Pointers and references are equivalent once we get to GENERIC,
- so strip conversions that just switch between them. */
- else if (POINTER_TYPE_P (inner_type)
- && POINTER_TYPE_P (outer_type)
- && TYPE_MODE (inner_type) == TYPE_MODE (outer_type)
- && TYPE_REF_CAN_ALIAS_ALL (inner_type)
- == TYPE_REF_CAN_ALIAS_ALL (outer_type)
- && lang_hooks.types_compatible_p (TREE_TYPE (inner_type),
- TREE_TYPE (outer_type)))
+ /* If we know the canonical types, compare them. */
+ if (TYPE_CANONICAL (inner_type)
+ && TYPE_CANONICAL (inner_type) == TYPE_CANONICAL (outer_type))
return true;
+ /* Changes in machine mode are never useless conversions. */
+ if (TYPE_MODE (inner_type) != TYPE_MODE (outer_type))
+ return false;
+
/* If both the inner and outer types are integral types, then the
conversion is not necessary if they have the same mode and
- signedness and precision, and both or neither are boolean. Some
- code assumes an invariant that boolean types stay boolean and do
- not become 1-bit bit-field types. Note that types with precision
- not using all bits of the mode (such as bit-field types in C)
- mean that testing of precision is necessary. */
- else if (INTEGRAL_TYPE_P (inner_type)
- && INTEGRAL_TYPE_P (outer_type)
- && TYPE_MODE (inner_type) == TYPE_MODE (outer_type)
- && TYPE_UNSIGNED (inner_type) == TYPE_UNSIGNED (outer_type)
- && TYPE_PRECISION (inner_type) == TYPE_PRECISION (outer_type))
+ signedness and precision, and both or neither are boolean. */
+ if (INTEGRAL_TYPE_P (inner_type)
+ && INTEGRAL_TYPE_P (outer_type))
+ {
+ /* Preserve changes in signedness or precision. */
+ if (TYPE_UNSIGNED (inner_type) != TYPE_UNSIGNED (outer_type)
+ || TYPE_PRECISION (inner_type) != TYPE_PRECISION (outer_type))
+ return false;
+
+ /* Conversions from a non-base to a base type are not useless.
+ This way we preserve the invariant to do arithmetic in
+ base types only. */
+ if (TREE_TYPE (inner_type)
+ && TREE_TYPE (inner_type) != inner_type
+ && (TREE_TYPE (outer_type) == outer_type
+ || TREE_TYPE (outer_type) == NULL_TREE))
+ return false;
+
+ /* We don't need to preserve changes in the types minimum or
+ maximum value in general as these do not generate code
+ unless the types precisions are different. */
+
+ return true;
+ }
+
+ /* Scalar floating point types with the same mode are compatible. */
+ else if (SCALAR_FLOAT_TYPE_P (inner_type)
+ && SCALAR_FLOAT_TYPE_P (outer_type))
+ return true;
+
+ /* We need to take special care recursing to pointed-to types. */
+ else if (POINTER_TYPE_P (inner_type)
+ && POINTER_TYPE_P (outer_type))
{
- bool first_boolean = (TREE_CODE (inner_type) == BOOLEAN_TYPE);
- bool second_boolean = (TREE_CODE (outer_type) == BOOLEAN_TYPE);
- if (first_boolean == second_boolean)
- return true;
+ /* Don't lose casts between pointers to volatile and non-volatile
+ qualified types. Doing so would result in changing the semantics
+ of later accesses. */
+ if ((TYPE_VOLATILE (TREE_TYPE (outer_type))
+ != TYPE_VOLATILE (TREE_TYPE (inner_type)))
+ && TYPE_VOLATILE (TREE_TYPE (outer_type)))
+ return false;
+
+ /* Do not lose casts between pointers with different
+ TYPE_REF_CAN_ALIAS_ALL setting or alias sets. */
+ if ((TYPE_REF_CAN_ALIAS_ALL (inner_type)
+ != TYPE_REF_CAN_ALIAS_ALL (outer_type))
+ || (get_alias_set (TREE_TYPE (inner_type))
+ != get_alias_set (TREE_TYPE (outer_type))))
+ return false;
+
+ /* We do not care for const qualification of the pointed-to types
+ as const qualification has no semantic value to the middle-end. */
+
+ /* Do not lose casts to restrict qualified pointers. */
+ if ((TYPE_RESTRICT (outer_type)
+ != TYPE_RESTRICT (inner_type))
+ && TYPE_RESTRICT (outer_type))
+ return false;
+
+ /* Otherwise pointers/references are equivalent if their pointed
+ to types are effectively the same. We can strip qualifiers
+ on pointed-to types for further comparison, which is done in
+ the callee. */
+ return useless_type_conversion_p_1 (TREE_TYPE (outer_type),
+ TREE_TYPE (inner_type));
}
/* Recurse for complex types. */
else if (TREE_CODE (inner_type) == COMPLEX_TYPE
- && TREE_CODE (outer_type) == COMPLEX_TYPE
- && tree_ssa_useless_type_conversion_1 (TREE_TYPE (outer_type),
- TREE_TYPE (inner_type)))
- return true;
+ && TREE_CODE (outer_type) == COMPLEX_TYPE)
+ return useless_type_conversion_p_1 (TREE_TYPE (outer_type),
+ TREE_TYPE (inner_type));
+
+ /* Recurse for vector types with the same number of subparts. */
+ else if (TREE_CODE (inner_type) == VECTOR_TYPE
+ && TREE_CODE (outer_type) == VECTOR_TYPE
+ && TYPE_PRECISION (inner_type) == TYPE_PRECISION (outer_type))
+ return useless_type_conversion_p_1 (TREE_TYPE (outer_type),
+ TREE_TYPE (inner_type));
+
+ /* For aggregates we may need to fall back to structural equality
+ checks. */
+ else if (AGGREGATE_TYPE_P (inner_type)
+ && AGGREGATE_TYPE_P (outer_type))
+ {
+ /* Different types of aggregates are incompatible. */
+ if (TREE_CODE (inner_type) != TREE_CODE (outer_type))
+ return false;
+
+ /* ??? Add structural equivalence check. */
+
+ /* ??? This should eventually just return false. */
+ return lang_hooks.types_compatible_p (inner_type, outer_type);
+ }
return false;
}
+/* Return true if the conversion from INNER_TYPE to OUTER_TYPE is a
+ useless type conversion, otherwise return false.
+
+ This function implicitly defines the middle-end type system. With
+ the notion of 'a < b' meaning that useless_type_conversion_p (a, b)
+ holds and 'a > b' meaning that useless_type_conversion_p (b, a) holds,
+ the following invariants shall be fulfilled:
+
+ 1) useless_type_conversion_p is transitive.
+ If a < b and b < c then a < c.
+
+ 2) useless_type_conversion_p is not symmetric.
+ From a < b does not follow a > b.
+
+ 3) Types define the available set of operations applicable to values.
+ A type conversion is useless if the operations for the target type
+ is a subset of the operations for the source type. For example
+ casts to void* are useless, casts from void* are not (void* can't
+ be dereferenced or offsetted, but copied, hence its set of operations
+ is a strict subset of that of all other data pointer types). Casts
+ to const T* are useless (can't be written to), casts from const T*
+ to T* are not. */
+
+bool
+useless_type_conversion_p (tree outer_type, tree inner_type)
+{
+ /* If the outer type is (void *), then the conversion is not
+ necessary. We have to make sure to not apply this while
+ recursing though. */
+ if (POINTER_TYPE_P (inner_type)
+ && POINTER_TYPE_P (outer_type)
+ && TREE_CODE (TREE_TYPE (outer_type)) == VOID_TYPE)
+ return true;
+
+ return useless_type_conversion_p_1 (outer_type, inner_type);
+}
+
+/* Return true if a conversion from either type of TYPE1 and TYPE2
+ to the other is not required. Otherwise return false. */
+
+bool
+types_compatible_p (tree type1, tree type2)
+{
+ return (type1 == type2
+ || (useless_type_conversion_p (type1, type2)
+ && useless_type_conversion_p (type2, type1)));
+}
+
/* Return true if EXPR is a useless type conversion, otherwise return
false. */
if (TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR
|| TREE_CODE (expr) == VIEW_CONVERT_EXPR
|| TREE_CODE (expr) == NON_LVALUE_EXPR)
- return tree_ssa_useless_type_conversion_1 (TREE_TYPE (expr),
- TREE_TYPE (TREE_OPERAND (expr,
- 0)));
-
+ /* FIXME: Use of GENERIC_TREE_TYPE here is a temporary measure to work
+ around known bugs with GIMPLE_MODIFY_STMTs appearing in places
+ they shouldn't. See PR 30391. */
+ return useless_type_conversion_p
+ (TREE_TYPE (expr),
+ GENERIC_TREE_TYPE (TREE_OPERAND (expr, 0)));
return false;
}
-/* Returns true if statement STMT may read memory. */
-
-bool
-stmt_references_memory_p (tree stmt)
-{
- stmt_ann_t ann;
-
- get_stmt_operands (stmt);
- ann = stmt_ann (stmt);
-
- if (ann->has_volatile_ops)
- return true;
-
- return (NUM_VUSES (VUSE_OPS (ann)) > 0
- || NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann)) > 0
- || NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann)) > 0);
-}
/* Internal helper for walk_use_def_chains. VAR, FN and DATA are as
described in walk_use_def_chains.
for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
{
tree arg = PHI_ARG_DEF (def_stmt, i);
- if (TREE_CODE (arg) == SSA_NAME
+
+ /* ARG may be NULL for newly introduced PHI nodes. */
+ if (arg
+ && TREE_CODE (arg) == SSA_NAME
&& walk_use_def_chains_1 (arg, fn, data, visited, is_dfs))
return true;
}
If IS_DFS is false, the two steps above are done in reverse order
(i.e., a breadth-first search). */
-
void
walk_use_def_chains (tree var, walk_use_def_chains_fn fn, void *data,
bool is_dfs)
}
}
+\f
+/* Return true if T, an SSA_NAME, has an undefined value. */
-/* Replaces VAR with REPL in memory reference expression *X in
- statement STMT. */
-
-static void
-propagate_into_addr (tree stmt, tree var, tree *x, tree repl)
-{
- tree new_var, ass_stmt, addr_var;
- basic_block bb;
- block_stmt_iterator bsi;
-
- /* There is nothing special to handle in the other cases. */
- if (TREE_CODE (repl) != ADDR_EXPR)
- return;
- addr_var = TREE_OPERAND (repl, 0);
-
- while (handled_component_p (*x)
- || TREE_CODE (*x) == REALPART_EXPR
- || TREE_CODE (*x) == IMAGPART_EXPR)
- x = &TREE_OPERAND (*x, 0);
-
- if (TREE_CODE (*x) != INDIRECT_REF
- || TREE_OPERAND (*x, 0) != var)
- return;
-
- if (TREE_TYPE (*x) == TREE_TYPE (addr_var))
- {
- *x = addr_var;
- mark_new_vars_to_rename (stmt, vars_to_rename);
- return;
- }
-
-
- /* Frontends sometimes produce expressions like *&a instead of a[0].
- Create a temporary variable to handle this case. */
- ass_stmt = build2 (MODIFY_EXPR, void_type_node, NULL_TREE, repl);
- new_var = duplicate_ssa_name (var, ass_stmt);
- TREE_OPERAND (*x, 0) = new_var;
- TREE_OPERAND (ass_stmt, 0) = new_var;
-
- bb = bb_for_stmt (stmt);
- tree_block_label (bb);
- bsi = bsi_after_labels (bb);
- bsi_insert_after (&bsi, ass_stmt, BSI_NEW_STMT);
-
- mark_new_vars_to_rename (stmt, vars_to_rename);
-}
-
-/* Replaces immediate uses of VAR by REPL. */
-
-static void
-replace_immediate_uses (tree var, tree repl)
-{
- int i, j, n;
- dataflow_t df;
- tree stmt;
- bool mark_new_vars;
- ssa_op_iter iter;
- use_operand_p use_p;
-
- df = get_immediate_uses (SSA_NAME_DEF_STMT (var));
- n = num_immediate_uses (df);
-
- for (i = 0; i < n; i++)
- {
- stmt = immediate_use (df, i);
-
- if (TREE_CODE (stmt) == PHI_NODE)
- {
- for (j = 0; j < PHI_NUM_ARGS (stmt); j++)
- if (PHI_ARG_DEF (stmt, j) == var)
- {
- SET_PHI_ARG_DEF (stmt, j, repl);
- if (TREE_CODE (repl) == SSA_NAME
- && PHI_ARG_EDGE (stmt, j)->flags & EDGE_ABNORMAL)
- SSA_NAME_OCCURS_IN_ABNORMAL_PHI (repl) = 1;
- }
-
- continue;
- }
-
- get_stmt_operands (stmt);
- mark_new_vars = false;
- if (is_gimple_reg (SSA_NAME_VAR (var)))
- {
- if (TREE_CODE (stmt) == MODIFY_EXPR)
- {
- propagate_into_addr (stmt, var, &TREE_OPERAND (stmt, 0), repl);
- propagate_into_addr (stmt, var, &TREE_OPERAND (stmt, 1), repl);
- }
-
- FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
- if (USE_FROM_PTR (use_p) == var)
- {
- propagate_value (use_p, repl);
- mark_new_vars = POINTER_TYPE_P (TREE_TYPE (repl));
- }
- }
- else
- {
- FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter,
- SSA_OP_VIRTUAL_USES | SSA_OP_VIRTUAL_KILLS)
- if (USE_FROM_PTR (use_p) == var)
- propagate_value (use_p, repl);
- }
-
- /* FIXME. If REPL is a constant, we need to fold STMT.
- However, fold_stmt wants a pointer to the statement, because
- it may happen that it needs to replace the whole statement
- with a new expression. Since the current def-use machinery
- does not return pointers to statements, we call fold_stmt
- with the address of a local temporary, if that call changes
- the temporary then we fallback on looking for a proper
- pointer to STMT by scanning STMT's basic block.
-
- Note that all this will become unnecessary soon. This
- pass is being replaced with a proper copy propagation pass
- for 4.1 (dnovillo, 2004-09-17). */
- if (TREE_CODE (repl) != SSA_NAME)
- {
- tree tmp = stmt;
- fold_stmt (&tmp);
- mark_new_vars = true;
- if (tmp != stmt)
- {
- block_stmt_iterator si = bsi_for_stmt (stmt);
- bsi_replace (&si, tmp, true);
- stmt = bsi_stmt (si);
- }
- }
-
- /* If REPL is a pointer, it may have different memory tags associated
- with it. For instance, VAR may have had a name tag while REPL
- only had a type tag. In these cases, the virtual operands (if
- any) in the statement will refer to different symbols which need
- to be renamed. */
- if (mark_new_vars)
- mark_new_vars_to_rename (stmt, vars_to_rename);
- else
- modify_stmt (stmt);
- }
-}
-
-/* Gets the value VAR is equivalent to according to EQ_TO. */
-
-static tree
-get_eq_name (tree *eq_to, tree var)
-{
- unsigned ver;
- tree val = var;
-
- while (TREE_CODE (val) == SSA_NAME)
- {
- ver = SSA_NAME_VERSION (val);
- if (!eq_to[ver])
- break;
-
- val = eq_to[ver];
- }
-
- while (TREE_CODE (var) == SSA_NAME)
- {
- ver = SSA_NAME_VERSION (var);
- if (!eq_to[ver])
- break;
-
- var = eq_to[ver];
- eq_to[ver] = val;
- }
-
- return val;
-}
-
-/* Checks whether phi node PHI is redundant and if it is, records the ssa name
- its result is redundant to to EQ_TO array. */
-
-static void
-check_phi_redundancy (tree phi, tree *eq_to)
-{
- tree val = NULL_TREE, def, res = PHI_RESULT (phi), stmt;
- unsigned i, ver = SSA_NAME_VERSION (res), n;
- dataflow_t df;
-
- /* It is unlikely that such large phi node would be redundant. */
- if (PHI_NUM_ARGS (phi) > 16)
- return;
-
- for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
- {
- def = PHI_ARG_DEF (phi, i);
-
- if (TREE_CODE (def) == SSA_NAME)
- {
- def = get_eq_name (eq_to, def);
- if (def == res)
- continue;
- }
-
- if (val
- && !operand_equal_for_phi_arg_p (val, def))
- return;
-
- val = def;
- }
-
- /* At least one of the arguments should not be equal to the result, or
- something strange is happening. */
- gcc_assert (val);
-
- if (get_eq_name (eq_to, res) == val)
- return;
-
- if (!may_propagate_copy (res, val))
- return;
-
- eq_to[ver] = val;
-
- df = get_immediate_uses (SSA_NAME_DEF_STMT (res));
- n = num_immediate_uses (df);
-
- for (i = 0; i < n; i++)
- {
- stmt = immediate_use (df, i);
-
- if (TREE_CODE (stmt) == PHI_NODE)
- check_phi_redundancy (stmt, eq_to);
- }
-}
-
-/* Removes redundant phi nodes.
-
- A redundant PHI node is a PHI node where all of its PHI arguments
- are the same value, excluding any PHI arguments which are the same
- as the PHI result.
-
- A redundant PHI node is effectively a copy, so we forward copy propagate
- which removes all uses of the destination of the PHI node then
- finally we delete the redundant PHI node.
-
- Note that if we can not copy propagate the PHI node, then the PHI
- will not be removed. Thus we do not have to worry about dependencies
- between PHIs and the problems serializing PHIs into copies creates.
-
- The most important effect of this pass is to remove degenerate PHI
- nodes created by removing unreachable code. */
-
-void
-kill_redundant_phi_nodes (void)
+bool
+ssa_undefined_value_p (tree t)
{
- tree *eq_to;
- unsigned i, old_num_ssa_names;
- basic_block bb;
- tree phi, var, repl, stmt;
-
- /* The EQ_TO[VER] holds the value by that the ssa name VER should be
- replaced. If EQ_TO[VER] is ssa name and it is decided to replace it by
- other value, it may be necessary to follow the chain till the final value.
- We perform path shortening (replacing the entries of the EQ_TO array with
- heads of these chains) whenever we access the field to prevent quadratic
- complexity (probably would not occur in practice anyway, but let us play
- it safe). */
- eq_to = xcalloc (num_ssa_names, sizeof (tree));
-
- /* We have had cases where computing immediate uses takes a
- significant amount of compile time. If we run into such
- problems here, we may want to only compute immediate uses for
- a subset of all the SSA_NAMEs instead of computing it for
- all of the SSA_NAMEs. */
- compute_immediate_uses (TDFA_USE_OPS | TDFA_USE_VOPS, NULL);
- old_num_ssa_names = num_ssa_names;
-
- FOR_EACH_BB (bb)
- {
- for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
- {
- var = PHI_RESULT (phi);
- check_phi_redundancy (phi, eq_to);
- }
- }
-
- /* Now propagate the values. */
- for (i = 0; i < old_num_ssa_names; i++)
- {
- if (!ssa_name (i))
- continue;
-
- repl = get_eq_name (eq_to, ssa_name (i));
- if (repl != ssa_name (i))
- replace_immediate_uses (ssa_name (i), repl);
- }
+ tree var = SSA_NAME_VAR (t);
- /* And remove the dead phis. */
- for (i = 0; i < old_num_ssa_names; i++)
- {
- if (!ssa_name (i))
- continue;
+ /* Parameters get their initial value from the function entry. */
+ if (TREE_CODE (var) == PARM_DECL)
+ return false;
- repl = get_eq_name (eq_to, ssa_name (i));
- if (repl != ssa_name (i))
- {
- stmt = SSA_NAME_DEF_STMT (ssa_name (i));
- remove_phi_node (stmt, NULL_TREE, bb_for_stmt (stmt));
- }
- }
+ /* Hard register variables get their initial value from the ether. */
+ if (TREE_CODE (var) == VAR_DECL && DECL_HARD_REGISTER (var))
+ return false;
- free_df ();
- free (eq_to);
+ /* The value is undefined iff its definition statement is empty. */
+ return IS_EMPTY_STMT (SSA_NAME_DEF_STMT (t));
}
-struct tree_opt_pass pass_redundant_phi =
-{
- "redphi", /* name */
- NULL, /* gate */
- kill_redundant_phi_nodes, /* execute */
- NULL, /* sub */
- NULL, /* next */
- 0, /* static_pass_number */
- TV_TREE_REDPHI, /* tv_id */
- PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */
- 0, /* properties_provided */
- 0, /* properties_destroyed */
- 0, /* todo_flags_start */
- TODO_dump_func | TODO_rename_vars
- | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */
- 0 /* letter */
-};
-\f
/* Emit warnings for uninitialized variables. This is done in two passes.
- The first pass notices real uses of SSA names with default definitions.
+ The first pass notices real uses of SSA names with undefined values.
Such uses are unconditionally uninitialized, and we can be certain that
such a use is a mistake. This pass is run before most optimizations,
so that we catch as many as we can.
warning text is in MSGID and LOCUS may contain a location or be null. */
static void
-warn_uninit (tree t, const char *msgid, location_t *locus)
+warn_uninit (tree t, const char *gmsgid, void *data)
{
tree var = SSA_NAME_VAR (t);
- tree def = SSA_NAME_DEF_STMT (t);
-
- /* Default uses (indicated by an empty definition statement),
- are uninitialized. */
- if (!IS_EMPTY_STMT (def))
- return;
-
- /* Except for PARMs of course, which are always initialized. */
- if (TREE_CODE (var) == PARM_DECL)
- return;
+ tree context = (tree) data;
+ location_t *locus;
+ expanded_location xloc, floc;
- /* Hard register variables get their initial value from the ether. */
- if (TREE_CODE (var) == VAR_DECL && DECL_HARD_REGISTER (var))
+ if (!ssa_undefined_value_p (t))
return;
/* TREE_NO_WARNING either means we already warned, or the front end
if (TREE_NO_WARNING (var))
return;
- if (!locus)
- locus = &DECL_SOURCE_LOCATION (var);
- warning (msgid, locus, var);
+ locus = (context != NULL && EXPR_HAS_LOCATION (context)
+ ? EXPR_LOCUS (context)
+ : &DECL_SOURCE_LOCATION (var));
+ warning (OPT_Wuninitialized, gmsgid, locus, var);
+ xloc = expand_location (*locus);
+ floc = expand_location (DECL_SOURCE_LOCATION (cfun->decl));
+ if (xloc.file != floc.file
+ || xloc.line < floc.line
+ || xloc.line > LOCATION_LINE (cfun->function_end_locus))
+ inform ("%J%qD was declared here", var, var);
+
TREE_NO_WARNING (var) = 1;
}
-
+
+struct walk_data {
+ tree stmt;
+ bool always_executed;
+};
+
/* Called via walk_tree, look for SSA_NAMEs that have empty definitions
and warn about them. */
static tree
-warn_uninitialized_var (tree *tp, int *walk_subtrees, void *data)
+warn_uninitialized_var (tree *tp, int *walk_subtrees, void *data_)
{
- location_t *locus = data;
+ struct walk_data *data = (struct walk_data *)data_;
tree t = *tp;
- /* We only do data flow with SSA_NAMEs, so that's all we can warn about. */
- if (TREE_CODE (t) == SSA_NAME)
+ switch (TREE_CODE (t))
{
- warn_uninit (t, "%H%qD is used uninitialized in this function", locus);
+ case SSA_NAME:
+ /* We only do data flow with SSA_NAMEs, so that's all we
+ can warn about. */
+ if (data->always_executed)
+ warn_uninit (t, "%H%qD is used uninitialized in this function",
+ data->stmt);
+ else
+ warn_uninit (t, "%H%qD may be used uninitialized in this function",
+ data->stmt);
*walk_subtrees = 0;
+ break;
+
+ case REALPART_EXPR:
+ case IMAGPART_EXPR:
+ /* The total store transformation performed during gimplification
+ creates uninitialized variable uses. If all is well, these will
+ be optimized away, so don't warn now. */
+ if (TREE_CODE (TREE_OPERAND (t, 0)) == SSA_NAME)
+ *walk_subtrees = 0;
+ break;
+
+ default:
+ if (IS_TYPE_OR_DECL_P (t))
+ *walk_subtrees = 0;
+ break;
}
- else if (IS_TYPE_OR_DECL_P (t))
- *walk_subtrees = 0;
return NULL_TREE;
}
}
}
-static void
+static unsigned int
execute_early_warn_uninitialized (void)
{
block_stmt_iterator bsi;
basic_block bb;
+ struct walk_data data;
+
+ calculate_dominance_info (CDI_POST_DOMINATORS);
FOR_EACH_BB (bb)
- for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
- walk_tree (bsi_stmt_ptr (bsi), warn_uninitialized_var,
- EXPR_LOCUS (bsi_stmt (bsi)), NULL);
+ {
+ data.always_executed = dominated_by_p (CDI_POST_DOMINATORS,
+ single_succ (ENTRY_BLOCK_PTR), bb);
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ {
+ data.stmt = bsi_stmt (bsi);
+ walk_tree (bsi_stmt_ptr (bsi), warn_uninitialized_var,
+ &data, NULL);
+ }
+ }
+ return 0;
}
-static void
+static unsigned int
execute_late_warn_uninitialized (void)
{
basic_block bb;
FOR_EACH_BB (bb)
for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
warn_uninitialized_phi (phi);
+ return 0;
}
static bool
return warn_uninitialized != 0;
}
-struct tree_opt_pass pass_early_warn_uninitialized =
+struct gimple_opt_pass pass_early_warn_uninitialized =
{
+ {
+ GIMPLE_PASS,
NULL, /* name */
gate_warn_uninitialized, /* gate */
execute_early_warn_uninitialized, /* execute */
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- 0, /* todo_flags_finish */
- 0 /* letter */
+ 0 /* todo_flags_finish */
+ }
};
-struct tree_opt_pass pass_late_warn_uninitialized =
+struct gimple_opt_pass pass_late_warn_uninitialized =
{
+ {
+ GIMPLE_PASS,
NULL, /* name */
gate_warn_uninitialized, /* gate */
execute_late_warn_uninitialized, /* execute */
0, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- 0, /* todo_flags_finish */
- 0 /* letter */
+ 0 /* todo_flags_finish */
+ }
+};
+
+/* Compute TREE_ADDRESSABLE for local variables. */
+
+static unsigned int
+execute_update_addresses_taken (void)
+{
+ tree var;
+ referenced_var_iterator rvi;
+ block_stmt_iterator bsi;
+ basic_block bb;
+ bitmap addresses_taken = BITMAP_ALLOC (NULL);
+ bitmap vars_updated = BITMAP_ALLOC (NULL);
+ bool update_vops = false;
+ tree phi;
+
+ /* Collect into ADDRESSES_TAKEN all variables whose address is taken within
+ the function body. */
+ FOR_EACH_BB (bb)
+ {
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ {
+ stmt_ann_t s_ann = stmt_ann (bsi_stmt (bsi));
+
+ if (s_ann->addresses_taken)
+ bitmap_ior_into (addresses_taken, s_ann->addresses_taken);
+ }
+ for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
+ {
+ unsigned i, phi_num_args = PHI_NUM_ARGS (phi);
+ for (i = 0; i < phi_num_args; i++)
+ {
+ tree op = PHI_ARG_DEF (phi, i), var;
+ if (TREE_CODE (op) == ADDR_EXPR
+ && (var = get_base_address (TREE_OPERAND (op, 0))) != NULL_TREE
+ && DECL_P (var))
+ bitmap_set_bit (addresses_taken, DECL_UID (var));
+ }
+ }
+ }
+
+ /* When possible, clear ADDRESSABLE bit and mark variable for conversion into
+ SSA. */
+ FOR_EACH_REFERENCED_VAR (var, rvi)
+ if (!is_global_var (var)
+ && TREE_CODE (var) != RESULT_DECL
+ && TREE_ADDRESSABLE (var)
+ && !bitmap_bit_p (addresses_taken, DECL_UID (var)))
+ {
+ TREE_ADDRESSABLE (var) = 0;
+ if (is_gimple_reg (var))
+ mark_sym_for_renaming (var);
+ update_vops = true;
+ bitmap_set_bit (vars_updated, DECL_UID (var));
+ if (dump_file)
+ {
+ fprintf (dump_file, "No longer having address taken ");
+ print_generic_expr (dump_file, var, 0);
+ fprintf (dump_file, "\n");
+ }
+ }
+
+ /* Operand caches needs to be recomputed for operands referencing the updated
+ variables. */
+ if (update_vops)
+ FOR_EACH_BB (bb)
+ for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ {
+ tree stmt = bsi_stmt (bsi);
+
+ if ((LOADED_SYMS (stmt)
+ && bitmap_intersect_p (LOADED_SYMS (stmt), vars_updated))
+ || (STORED_SYMS (stmt)
+ && bitmap_intersect_p (STORED_SYMS (stmt), vars_updated)))
+ update_stmt (stmt);
+ }
+ BITMAP_FREE (addresses_taken);
+ BITMAP_FREE (vars_updated);
+ return 0;
+}
+
+struct gimple_opt_pass pass_update_address_taken =
+{
+ {
+ GIMPLE_PASS,
+ "addressables", /* name */
+ NULL, /* gate */
+ execute_update_addresses_taken, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ 0, /* tv_id */
+ PROP_ssa, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_update_ssa /* todo_flags_finish */
+ }
};
-
OSDN Git Service
