/* Data flow functions for trees.
- Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
+ Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007 Free Software Foundation, Inc.
Contributed by Diego Novillo <dnovillo@redhat.com>
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, 51 Franklin Street, Fifth Floor,
-Boston, MA 02110-1301, USA. */
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
#include "config.h"
#include "system.h"
return 0;
}
-struct tree_opt_pass pass_referenced_vars =
+struct gimple_opt_pass pass_referenced_vars =
{
+ {
+ GIMPLE_PASS,
NULL, /* name */
NULL, /* gate */
find_referenced_vars, /* execute */
PROP_referenced_vars, /* properties_provided */
0, /* properties_destroyed */
0, /* todo_flags_start */
- 0, /* todo_flags_finish */
- 0 /* letter */
+ 0 /* todo_flags_finish */
+ }
};
}
-/* Dump sub-variables for VAR to FILE. */
-
-void
-dump_subvars_for (FILE *file, tree var)
-{
- subvar_t sv = get_subvars_for_var (var);
-
- if (!sv)
- return;
-
- fprintf (file, "{ ");
-
- for (; sv; sv = sv->next)
- {
- print_generic_expr (file, sv->var, dump_flags);
- fprintf (file, " ");
- }
-
- fprintf (file, "}");
-}
-
-
-/* Dumb sub-variables for VAR to stderr. */
-
-void
-debug_subvars_for (tree var)
-{
- dump_subvars_for (stderr, var);
-}
-
-
/* Dump variable VAR and its may-aliases to FILE. */
void
ann = var_ann (var);
- fprintf (file, ", UID %u", (unsigned) DECL_UID (var));
+ fprintf (file, ", UID D.%u", (unsigned) DECL_UID (var));
fprintf (file, ", ");
print_generic_expr (file, TREE_TYPE (var), dump_flags);
print_generic_expr (file, ann->symbol_mem_tag, dump_flags);
}
- if (ann && ann->is_aliased)
- fprintf (file, ", is aliased");
-
if (TREE_ADDRESSABLE (var))
fprintf (file, ", is addressable");
if (TREE_THIS_VOLATILE (var))
fprintf (file, ", is volatile");
+ dump_mem_sym_stats_for_var (file, var);
+
if (is_call_clobbered (var))
{
+ const char *s = "";
var_ann_t va = var_ann (var);
unsigned int escape_mask = va->escape_mask;
fprintf (file, ", call clobbered");
fprintf (file, " (");
if (escape_mask & ESCAPE_STORED_IN_GLOBAL)
- fprintf (file, ", stored in global");
+ { fprintf (file, "%sstored in global", s); s = ", "; }
if (escape_mask & ESCAPE_TO_ASM)
- fprintf (file, ", goes through ASM");
+ { fprintf (file, "%sgoes through ASM", s); s = ", "; }
if (escape_mask & ESCAPE_TO_CALL)
- fprintf (file, ", passed to call");
+ { fprintf (file, "%spassed to call", s); s = ", "; }
if (escape_mask & ESCAPE_BAD_CAST)
- fprintf (file, ", bad cast");
+ { fprintf (file, "%sbad cast", s); s = ", "; }
if (escape_mask & ESCAPE_TO_RETURN)
- fprintf (file, ", returned from func");
+ { fprintf (file, "%sreturned from func", s); s = ", "; }
if (escape_mask & ESCAPE_TO_PURE_CONST)
- fprintf (file, ", passed to pure/const");
+ { fprintf (file, "%spassed to pure/const", s); s = ", "; }
if (escape_mask & ESCAPE_IS_GLOBAL)
- fprintf (file, ", is global var");
+ { fprintf (file, "%sis global var", s); s = ", "; }
if (escape_mask & ESCAPE_IS_PARM)
- fprintf (file, ", is incoming pointer");
+ { fprintf (file, "%sis incoming pointer", s); s = ", "; }
if (escape_mask & ESCAPE_UNKNOWN)
- fprintf (file, ", unknown escape");
- fprintf (file, " )");
+ { fprintf (file, "%sunknown escape", s); s = ", "; }
+ fprintf (file, ")");
}
+ if (ann->noalias_state == NO_ALIAS)
+ fprintf (file, ", NO_ALIAS (does not alias other NO_ALIAS symbols)");
+ else if (ann->noalias_state == NO_ALIAS_GLOBAL)
+ fprintf (file, ", NO_ALIAS_GLOBAL (does not alias other NO_ALIAS symbols"
+ " and global vars)");
+ else if (ann->noalias_state == NO_ALIAS_ANYTHING)
+ fprintf (file, ", NO_ALIAS_ANYTHING (does not alias any other symbols)");
+
if (gimple_default_def (cfun, var))
{
fprintf (file, ", default def: ");
print_generic_expr (file, gimple_default_def (cfun, var), dump_flags);
}
- if (may_aliases (var))
+ if (MTAG_P (var) && may_aliases (var))
{
fprintf (file, ", may aliases: ");
dump_may_aliases_for (file, var);
}
- if (get_subvars_for_var (var))
- {
- fprintf (file, ", sub-vars: ");
- dump_subvars_for (file, var);
- }
-
if (!is_gimple_reg (var))
{
if (memory_partition (var))
tree
referenced_var_lookup (unsigned int uid)
{
- struct int_tree_map *h, in;
+ tree h;
+ struct tree_decl_minimal in;
in.uid = uid;
- h = (struct int_tree_map *) htab_find_with_hash (gimple_referenced_vars (cfun),
- &in, uid);
+ h = (tree) htab_find_with_hash (gimple_referenced_vars (cfun), &in, uid);
gcc_assert (h || uid == 0);
- if (h)
- return h->to;
- return NULL_TREE;
+ return h;
}
/* Check if TO is in the referenced_vars hash table and insert it if not.
bool
referenced_var_check_and_insert (tree to)
{
- struct int_tree_map *h, in;
- void **loc;
+ tree h, *loc;
+ struct tree_decl_minimal in;
unsigned int uid = DECL_UID (to);
in.uid = uid;
- in.to = to;
- h = (struct int_tree_map *) htab_find_with_hash (gimple_referenced_vars (cfun),
- &in, uid);
-
+ h = (tree) htab_find_with_hash (gimple_referenced_vars (cfun), &in, uid);
if (h)
{
/* DECL_UID has already been entered in the table. Verify that it is
the same entry as TO. See PR 27793. */
- gcc_assert (h->to == to);
+ gcc_assert (h == to);
return false;
}
- h = GGC_NEW (struct int_tree_map);
- h->uid = uid;
- h->to = to;
- loc = htab_find_slot_with_hash (gimple_referenced_vars (cfun),
- h, uid, INSERT);
- *(struct int_tree_map **) loc = h;
+ loc = (tree *) htab_find_slot_with_hash (gimple_referenced_vars (cfun),
+ &in, uid, INSERT);
+ *loc = to;
return true;
}
tree
gimple_default_def (struct function *fn, tree var)
{
- struct int_tree_map *h, in;
+ struct tree_decl_minimal ind;
+ struct tree_ssa_name in;
gcc_assert (SSA_VAR_P (var));
- in.uid = DECL_UID (var);
- h = (struct int_tree_map *) htab_find_with_hash (DEFAULT_DEFS (fn),
- &in,
- DECL_UID (var));
- if (h)
- return h->to;
- return NULL_TREE;
+ in.var = (tree)&ind;
+ ind.uid = DECL_UID (var);
+ return (tree) htab_find_with_hash (DEFAULT_DEFS (fn), &in, DECL_UID (var));
}
/* Insert the pair VAR's UID, DEF into the default_defs hashtable. */
void
set_default_def (tree var, tree def)
{
- struct int_tree_map in;
- struct int_tree_map *h;
+ struct tree_decl_minimal ind;
+ struct tree_ssa_name in;
void **loc;
gcc_assert (SSA_VAR_P (var));
- in.uid = DECL_UID (var);
- if (!def && gimple_default_def (cfun, var))
+ in.var = (tree)&ind;
+ ind.uid = DECL_UID (var);
+ if (!def)
{
loc = htab_find_slot_with_hash (DEFAULT_DEFS (cfun), &in,
DECL_UID (var), INSERT);
+ gcc_assert (*loc);
htab_remove_elt (DEFAULT_DEFS (cfun), *loc);
return;
}
- gcc_assert (!def || TREE_CODE (def) == SSA_NAME);
+ gcc_assert (TREE_CODE (def) == SSA_NAME && SSA_NAME_VAR (def) == var);
loc = htab_find_slot_with_hash (DEFAULT_DEFS (cfun), &in,
DECL_UID (var), INSERT);
/* Default definition might be changed by tail call optimization. */
- if (!*loc)
- {
- h = GGC_NEW (struct int_tree_map);
- h->uid = DECL_UID (var);
- h->to = def;
- *(struct int_tree_map **) loc = h;
- }
- else
- {
- h = (struct int_tree_map *) *loc;
- SSA_NAME_IS_DEFAULT_DEF (h->to) = false;
- h->to = def;
- }
+ if (*loc)
+ SSA_NAME_IS_DEFAULT_DEF (*(tree *) loc) = false;
+ *(tree *) loc = def;
/* Mark DEF as the default definition for VAR. */
SSA_NAME_IS_DEFAULT_DEF (def) = true;
remove_referenced_var (tree var)
{
var_ann_t v_ann;
- struct int_tree_map in;
+ struct tree_decl_minimal in;
void **loc;
unsigned int uid = DECL_UID (var);
clear_call_clobbered (var);
- v_ann = get_var_ann (var);
- ggc_free (v_ann);
+ if ((v_ann = var_ann (var)))
+ ggc_free (v_ann);
var->base.ann = NULL;
gcc_assert (DECL_P (var));
in.uid = uid;
- in.to = var;
loc = htab_find_slot_with_hash (gimple_referenced_vars (cfun), &in, uid,
NO_INSERT);
- ggc_free (*loc);
htab_clear_slot (gimple_referenced_vars (cfun), loc);
}
HOST_WIDE_INT bitsize = -1;
HOST_WIDE_INT maxsize = -1;
tree size_tree = NULL_TREE;
- tree bit_offset = bitsize_zero_node;
+ HOST_WIDE_INT bit_offset = 0;
bool seen_variable_array_ref = false;
gcc_assert (!SSA_VAR_P (exp));
switch (TREE_CODE (exp))
{
case BIT_FIELD_REF:
- bit_offset = size_binop (PLUS_EXPR, bit_offset,
- TREE_OPERAND (exp, 2));
+ bit_offset += tree_low_cst (TREE_OPERAND (exp, 2), 0);
break;
case COMPONENT_REF:
if (this_offset && TREE_CODE (this_offset) == INTEGER_CST)
{
- this_offset = size_binop (MULT_EXPR,
- fold_convert (bitsizetype,
- this_offset),
- bitsize_unit_node);
- bit_offset = size_binop (PLUS_EXPR,
- bit_offset, this_offset);
- bit_offset = size_binop (PLUS_EXPR, bit_offset,
- DECL_FIELD_BIT_OFFSET (field));
+ HOST_WIDE_INT hthis_offset = tree_low_cst (this_offset, 0);
+
+ hthis_offset *= BITS_PER_UNIT;
+ bit_offset += hthis_offset;
+ bit_offset += tree_low_cst (DECL_FIELD_BIT_OFFSET (field), 0);
}
else
{
/* We need to adjust maxsize to the whole structure bitsize.
But we can subtract any constant offset seen sofar,
because that would get us out of the structure otherwise. */
- if (maxsize != -1
- && csize && host_integerp (csize, 1))
- {
- maxsize = (TREE_INT_CST_LOW (csize)
- - TREE_INT_CST_LOW (bit_offset));
- }
+ if (maxsize != -1 && csize && host_integerp (csize, 1))
+ maxsize = TREE_INT_CST_LOW (csize) - bit_offset;
else
maxsize = -1;
}
tree low_bound = array_ref_low_bound (exp);
tree unit_size = array_ref_element_size (exp);
- if (! integer_zerop (low_bound))
- index = fold_build2 (MINUS_EXPR, TREE_TYPE (index),
- index, low_bound);
- index = size_binop (MULT_EXPR,
- fold_convert (sizetype, index), unit_size);
- if (TREE_CODE (index) == INTEGER_CST)
+ /* If the resulting bit-offset is constant, track it. */
+ if (host_integerp (index, 0)
+ && host_integerp (low_bound, 0)
+ && host_integerp (unit_size, 1))
{
- index = size_binop (MULT_EXPR,
- fold_convert (bitsizetype, index),
- bitsize_unit_node);
- bit_offset = size_binop (PLUS_EXPR, bit_offset, index);
+ HOST_WIDE_INT hindex = tree_low_cst (index, 0);
+
+ hindex -= tree_low_cst (low_bound, 0);
+ hindex *= tree_low_cst (unit_size, 1);
+ hindex *= BITS_PER_UNIT;
+ bit_offset += hindex;
/* An array ref with a constant index up in the structure
hierarchy will constrain the size of any variable array ref
/* We need to adjust maxsize to the whole array bitsize.
But we can subtract any constant offset seen sofar,
because that would get us outside of the array otherwise. */
- if (maxsize != -1
- && asize && host_integerp (asize, 1))
- {
- maxsize = (TREE_INT_CST_LOW (asize)
- - TREE_INT_CST_LOW (bit_offset));
- }
+ if (maxsize != -1 && asize && host_integerp (asize, 1))
+ maxsize = TREE_INT_CST_LOW (asize) - bit_offset;
else
maxsize = -1;
break;
case IMAGPART_EXPR:
- bit_offset = size_binop (PLUS_EXPR, bit_offset,
- bitsize_int (bitsize));
+ bit_offset += bitsize;
break;
case VIEW_CONVERT_EXPR:
if (seen_variable_array_ref
&& maxsize != -1
&& host_integerp (TYPE_SIZE (TREE_TYPE (exp)), 1)
- && TREE_INT_CST_LOW (bit_offset) + maxsize
- == TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (exp))))
+ && bit_offset + maxsize
+ == (signed)TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (exp))))
maxsize = -1;
/* ??? Due to negative offsets in ARRAY_REF we can end up with
negative bit_offset here. We might want to store a zero offset
in this case. */
- *poffset = TREE_INT_CST_LOW (bit_offset);
+ *poffset = bit_offset;
*psize = bitsize;
*pmax_size = maxsize;
return exp;
}
+
+/* Returns true if STMT references an SSA_NAME that has
+ SSA_NAME_OCCURS_IN_ABNORMAL_PHI set, otherwise false. */
+
+bool
+stmt_references_abnormal_ssa_name (tree stmt)
+{
+ ssa_op_iter oi;
+ use_operand_p use_p;
+
+ FOR_EACH_SSA_USE_OPERAND (use_p, stmt, oi, SSA_OP_USE)
+ {
+ if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (use_p)))
+ return true;
+ }
+
+ return false;
+}
+
+/* Return true, if the two memory references REF1 and REF2 may alias. */
+
+bool
+refs_may_alias_p (tree ref1, tree ref2)
+{
+ tree base1, base2;
+ HOST_WIDE_INT offset1 = 0, offset2 = 0;
+ HOST_WIDE_INT size1 = -1, size2 = -1;
+ HOST_WIDE_INT max_size1 = -1, max_size2 = -1;
+
+ gcc_assert ((SSA_VAR_P (ref1)
+ || handled_component_p (ref1)
+ || TREE_CODE (ref1) == INDIRECT_REF)
+ && (SSA_VAR_P (ref2)
+ || handled_component_p (ref2)
+ || TREE_CODE (ref2) == INDIRECT_REF));
+
+ /* Defer to TBAA if possible. */
+ if (flag_strict_aliasing
+ && !alias_sets_conflict_p (get_alias_set (ref1), get_alias_set (ref2)))
+ return false;
+
+ /* Decompose the references into their base objects and the access. */
+ base1 = ref1;
+ if (handled_component_p (ref1))
+ base1 = get_ref_base_and_extent (ref1, &offset1, &size1, &max_size1);
+ base2 = ref2;
+ if (handled_component_p (ref2))
+ base2 = get_ref_base_and_extent (ref2, &offset2, &size2, &max_size2);
+
+ /* If both references are based on different variables, they cannot alias.
+ If both references are based on the same variable, they cannot alias if
+ if the accesses do not overlap. */
+ if (SSA_VAR_P (base1)
+ && SSA_VAR_P (base2)
+ && (!operand_equal_p (base1, base2, 0)
+ || !ranges_overlap_p (offset1, max_size1, offset2, max_size2)))
+ return false;
+
+ /* If both references are through pointers and both pointers are equal
+ then they do not alias if the accesses do not overlap. */
+ if (TREE_CODE (base1) == INDIRECT_REF
+ && TREE_CODE (base2) == INDIRECT_REF
+ && operand_equal_p (TREE_OPERAND (base1, 0),
+ TREE_OPERAND (base2, 0), 0)
+ && !ranges_overlap_p (offset1, max_size1, offset2, max_size2))
+ return false;
+
+ return true;
+}
+
+/* Given a stmt STMT that references memory, return the single stmt
+ that is reached by following the VUSE -> VDEF link. Returns
+ NULL_TREE, if there is no single stmt that defines all VUSEs of
+ STMT.
+ Note that for a stmt with a single virtual operand this may return
+ a PHI node as well. Note that if all VUSEs are default definitions
+ this function will return an empty statement. */
+
+tree
+get_single_def_stmt (tree stmt)
+{
+ tree def_stmt = NULL_TREE;
+ tree use;
+ ssa_op_iter iter;
+
+ FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_VIRTUAL_USES)
+ {
+ tree tmp = SSA_NAME_DEF_STMT (use);
+
+ /* ??? This is too simplistic for multiple virtual operands
+ reaching different PHI nodes of the same basic blocks or for
+ reaching all default definitions. */
+ if (def_stmt
+ && def_stmt != tmp
+ && !(IS_EMPTY_STMT (def_stmt)
+ && IS_EMPTY_STMT (tmp)))
+ return NULL_TREE;
+
+ def_stmt = tmp;
+ }
+
+ return def_stmt;
+}
+
+/* Given a PHI node of virtual operands, tries to eliminate cyclic
+ reached definitions if they do not alias REF and returns the
+ defining statement of the single virtual operand that flows in
+ from a non-backedge. Returns NULL_TREE if such statement within
+ the above conditions cannot be found. */
+
+tree
+get_single_def_stmt_from_phi (tree ref, tree phi)
+{
+ tree def_arg = NULL_TREE;
+ int i;
+
+ /* Find the single PHI argument that is not flowing in from a
+ back edge and verify that the loop-carried definitions do
+ not alias the reference we look for. */
+ for (i = 0; i < PHI_NUM_ARGS (phi); ++i)
+ {
+ tree arg = PHI_ARG_DEF (phi, i);
+ tree def_stmt;
+
+ if (!(PHI_ARG_EDGE (phi, i)->flags & EDGE_DFS_BACK))
+ {
+ /* Multiple non-back edges? Do not try to handle this. */
+ if (def_arg)
+ return NULL_TREE;
+ def_arg = arg;
+ continue;
+ }
+
+ /* Follow the definitions back to the original PHI node. Bail
+ out once a definition is found that may alias REF. */
+ def_stmt = SSA_NAME_DEF_STMT (arg);
+ do
+ {
+ if (TREE_CODE (def_stmt) != GIMPLE_MODIFY_STMT
+ || refs_may_alias_p (ref, GIMPLE_STMT_OPERAND (def_stmt, 0)))
+ return NULL_TREE;
+ /* ??? This will only work, reaching the PHI node again if
+ there is a single virtual operand on def_stmt. */
+ def_stmt = get_single_def_stmt (def_stmt);
+ if (!def_stmt)
+ return NULL_TREE;
+ }
+ while (def_stmt != phi);
+ }
+
+ return SSA_NAME_DEF_STMT (def_arg);
+}
+
+/* Return the single reference statement defining all virtual uses
+ on STMT or NULL_TREE, if there are multiple defining statements.
+ Take into account only definitions that alias REF if following
+ back-edges when looking through a loop PHI node. */
+
+tree
+get_single_def_stmt_with_phi (tree ref, tree stmt)
+{
+ switch (NUM_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_USES))
+ {
+ case 0:
+ gcc_unreachable ();
+
+ case 1:
+ {
+ tree def_stmt = SSA_NAME_DEF_STMT (SINGLE_SSA_TREE_OPERAND
+ (stmt, SSA_OP_VIRTUAL_USES));
+ /* We can handle lookups over PHI nodes only for a single
+ virtual operand. */
+ if (TREE_CODE (def_stmt) == PHI_NODE)
+ return get_single_def_stmt_from_phi (ref, def_stmt);
+ return def_stmt;
+ }
+
+ default:
+ return get_single_def_stmt (stmt);
+ }
+}