/* Alias analysis for GNU C
- Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004
+ Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005
Free Software Foundation, Inc.
Contributed by John Carr (jfc@mit.edu).
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. */
+Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301, USA. */
#include "config.h"
#include "system.h"
#include "target.h"
#include "cgraph.h"
#include "varray.h"
+#include "tree-pass.h"
+#include "ipa-type-escape.h"
+
+/* The aliasing API provided here solves related but different problems:
+
+ Say there exists (in c)
+
+ struct X {
+ struct Y y1;
+ struct Z z2;
+ } x1, *px1, *px2;
+
+ struct Y y2, *py;
+ struct Z z2, *pz;
+
+
+ py = &px1.y1;
+ px2 = &x1;
+
+ Consider the four questions:
+
+ Can a store to x1 interfere with px2->y1?
+ Can a store to x1 interfere with px2->z2?
+ (*px2).z2
+ Can a store to x1 change the value pointed to by with py?
+ Can a store to x1 change the value pointed to by with pz?
+
+ The answer to these questions can be yes, yes, yes, and maybe.
+
+ The first two questions can be answered with a simple examination
+ of the type system. If structure X contains a field of type Y then
+ a store thru a pointer to an X can overwrite any field that is
+ contained (recursively) in an X (unless we know that px1 != px2).
+
+ The last two of the questions can be solved in the same way as the
+ first two questions but this is too conservative. The observation
+ is that in some cases analysis we can know if which (if any) fields
+ are addressed and if those addresses are used in bad ways. This
+ analysis may be language specific. In C, arbitrary operations may
+ be applied to pointers. However, there is some indication that
+ this may be too conservative for some C++ types.
+
+ The pass ipa-type-escape does this analysis for the types whose
+ instances do not escape across the compilation boundary.
+
+ Historically in GCC, these two problems were combined and a single
+ data structure was used to represent the solution to these
+ problems. We now have two similar but different data structures,
+ The data structure to solve the last two question is similar to the
+ first, but does not contain have the fields in it whose address are
+ never taken. For types that do escape the compilation unit, the
+ data structures will have identical information.
+*/
/* The alias sets assigned to MEMs assist the back-end in determining
which MEMs can alias which other MEMs. In general, two MEMs in
static int nonoverlapping_memrefs_p (rtx, rtx);
static int write_dependence_p (rtx, rtx, int);
-static int nonlocal_mentioned_p_1 (rtx *, void *);
-static int nonlocal_mentioned_p (rtx);
-static int nonlocal_referenced_p_1 (rtx *, void *);
-static int nonlocal_referenced_p (rtx);
-static int nonlocal_set_p_1 (rtx *, void *);
-static int nonlocal_set_p (rtx);
static void memory_modified_1 (rtx, rtx, void *);
+static void record_alias_subset (HOST_WIDE_INT, HOST_WIDE_INT);
/* Set up all info needed to perform alias analysis on memory references. */
if (t == 0 || t == error_mark_node || ! POINTER_TYPE_P (TREE_TYPE (t)))
return 0;
- /* If this is a declaration, return it. */
+ /* If this is a declaration, return it. If T is based on a restrict
+ qualified decl, return that decl. */
if (DECL_P (t))
- return t;
+ {
+ if (TREE_CODE (t) == VAR_DECL && DECL_BASED_ON_RESTRICT_P (t))
+ t = DECL_GET_RESTRICT_BASE (t);
+ return t;
+ }
/* Handle general expressions. It would be nice to deal with
COMPONENT_REFs here. If we could tell that `a' and `b' were the
}
}
-/* Return 1 if all the nested component references handled by
- get_inner_reference in T are such that we can address the object in T. */
+/* Return true if all nested component references handled by
+ get_inner_reference in T are such that we should use the alias set
+ provided by the object at the heart of T.
-int
-can_address_p (tree t)
+ This is true for non-addressable components (which don't have their
+ own alias set), as well as components of objects in alias set zero.
+ This later point is a special case wherein we wish to override the
+ alias set used by the component, but we don't have per-FIELD_DECL
+ assignable alias sets. */
+
+bool
+component_uses_parent_alias_set (tree t)
{
- /* If we're at the end, it is vacuously addressable. */
- if (! handled_component_p (t))
- return 1;
+ while (1)
+ {
+ /* If we're at the end, it vacuously uses its own alias set. */
+ if (!handled_component_p (t))
+ return false;
- /* Bitfields are never addressable. */
- else if (TREE_CODE (t) == BIT_FIELD_REF)
- return 0;
+ switch (TREE_CODE (t))
+ {
+ case COMPONENT_REF:
+ if (DECL_NONADDRESSABLE_P (TREE_OPERAND (t, 1)))
+ return true;
+ break;
- /* Fields are addressable unless they are marked as nonaddressable or
- the containing type has alias set 0. */
- else if (TREE_CODE (t) == COMPONENT_REF
- && ! DECL_NONADDRESSABLE_P (TREE_OPERAND (t, 1))
- && get_alias_set (TREE_TYPE (TREE_OPERAND (t, 0))) != 0
- && can_address_p (TREE_OPERAND (t, 0)))
- return 1;
+ case ARRAY_REF:
+ case ARRAY_RANGE_REF:
+ if (TYPE_NONALIASED_COMPONENT (TREE_TYPE (TREE_OPERAND (t, 0))))
+ return true;
+ break;
- /* Likewise for arrays. */
- else if ((TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
- && ! TYPE_NONALIASED_COMPONENT (TREE_TYPE (TREE_OPERAND (t, 0)))
- && get_alias_set (TREE_TYPE (TREE_OPERAND (t, 0))) != 0
- && can_address_p (TREE_OPERAND (t, 0)))
- return 1;
+ case REALPART_EXPR:
+ case IMAGPART_EXPR:
+ break;
- return 0;
+ default:
+ /* Bitfields and casts are never addressable. */
+ return true;
+ }
+
+ t = TREE_OPERAND (t, 0);
+ if (get_alias_set (TREE_TYPE (t)) == 0)
+ return true;
+ }
}
/* Return the alias set for T, which may be either a type or an
}
/* Check for accesses through restrict-qualified pointers. */
- if (TREE_CODE (inner) == INDIRECT_REF)
+ if (INDIRECT_REF_P (inner))
{
tree decl = find_base_decl (TREE_OPERAND (inner, 0));
type, then we would believe that other subsets
of the pointed-to type (such as fields of that
type) do not conflict with the type pointed to
- by the restricted pointer. */
+ by the restricted pointer. */
DECL_POINTER_ALIAS_SET (decl)
= pointed_to_alias_set;
else
/* Otherwise, pick up the outermost object that we could have a pointer
to, processing conversions as above. */
- while (handled_component_p (t) && ! can_address_p (t))
+ while (component_uses_parent_alias_set (t))
{
t = TREE_OPERAND (t, 0);
STRIP_NOPS (t);
It is illegal for SUPERSET to be zero; everything is implicitly a
subset of alias set zero. */
-void
+static void
record_alias_subset (HOST_WIDE_INT superset, HOST_WIDE_INT subset)
{
alias_set_entry superset_entry;
where SIZE is the size in bytes of the memory reference. If ADDR
is not modified by the memory reference then ADDR is returned. */
-rtx
+static rtx
addr_side_effect_eval (rtx addr, int size, int n_refs)
{
int offset = 0;
aliases_everything_p (rtx mem)
{
if (GET_CODE (XEXP (mem, 0)) == AND)
- /* If the address is an AND, its very hard to know at what it is
+ /* If the address is an AND, it's very hard to know at what it is
actually pointing. */
return 1;
do
{
fieldx = TREE_OPERAND (x, 1);
- typex = DECL_FIELD_CONTEXT (fieldx);
+ typex = TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (fieldx));
y = orig_y;
do
{
fieldy = TREE_OPERAND (y, 1);
- typey = DECL_FIELD_CONTEXT (fieldy);
+ typey = TYPE_MAIN_VARIANT (DECL_FIELD_CONTEXT (fieldy));
if (typex == typey)
goto found;
x = TREE_OPERAND (x, 0);
}
while (x && TREE_CODE (x) == COMPONENT_REF);
-
/* Never found a common type. */
return false;
/* Unless both have exprs, we can't tell anything. */
if (exprx == 0 || expry == 0)
return 0;
-
+
/* If both are field references, we may be able to determine something. */
if (TREE_CODE (exprx) == COMPONENT_REF
&& TREE_CODE (expry) == COMPONENT_REF
&& nonoverlapping_component_refs_p (exprx, expry))
return 1;
+
/* If the field reference test failed, look at the DECLs involved. */
moffsetx = MEM_OFFSET (x);
if (TREE_CODE (exprx) == COMPONENT_REF)
{
- tree t = decl_for_component_ref (exprx);
- if (! t)
- return 0;
- moffsetx = adjust_offset_for_component_ref (exprx, moffsetx);
- exprx = t;
+ if (TREE_CODE (expry) == VAR_DECL
+ && POINTER_TYPE_P (TREE_TYPE (expry)))
+ {
+ tree field = TREE_OPERAND (exprx, 1);
+ tree fieldcontext = DECL_FIELD_CONTEXT (field);
+ if (ipa_type_escape_field_does_not_clobber_p (fieldcontext,
+ TREE_TYPE (field)))
+ return 1;
+ }
+ {
+ tree t = decl_for_component_ref (exprx);
+ if (! t)
+ return 0;
+ moffsetx = adjust_offset_for_component_ref (exprx, moffsetx);
+ exprx = t;
+ }
}
- else if (TREE_CODE (exprx) == INDIRECT_REF)
+ else if (INDIRECT_REF_P (exprx))
{
exprx = TREE_OPERAND (exprx, 0);
if (flag_argument_noalias < 2
moffsety = MEM_OFFSET (y);
if (TREE_CODE (expry) == COMPONENT_REF)
{
- tree t = decl_for_component_ref (expry);
- if (! t)
- return 0;
- moffsety = adjust_offset_for_component_ref (expry, moffsety);
- expry = t;
+ if (TREE_CODE (exprx) == VAR_DECL
+ && POINTER_TYPE_P (TREE_TYPE (exprx)))
+ {
+ tree field = TREE_OPERAND (expry, 1);
+ tree fieldcontext = DECL_FIELD_CONTEXT (field);
+ if (ipa_type_escape_field_does_not_clobber_p (fieldcontext,
+ TREE_TYPE (field)))
+ return 1;
+ }
+ {
+ tree t = decl_for_component_ref (expry);
+ if (! t)
+ return 0;
+ moffsety = adjust_offset_for_component_ref (expry, moffsety);
+ expry = t;
+ }
}
- else if (TREE_CODE (expry) == INDIRECT_REF)
+ else if (INDIRECT_REF_P (expry))
{
expry = TREE_OPERAND (expry, 0);
if (flag_argument_noalias < 2
/* Read-only memory is by definition never modified, and therefore can't
conflict with anything. We don't expect to find read-only set on MEM,
- but stupid user tricks can produce them, so don't abort. */
+ but stupid user tricks can produce them, so don't die. */
if (MEM_READONLY_P (x))
return 0;
/* Read-only memory is by definition never modified, and therefore can't
conflict with anything. We don't expect to find read-only set on MEM,
- but stupid user tricks can produce them, so don't abort. */
+ but stupid user tricks can produce them, so don't die. */
if (MEM_READONLY_P (x))
return 0;
return write_dependence_p (mem, x, /*writep=*/1);
}
\f
-/* A subroutine of nonlocal_mentioned_p, returns 1 if *LOC mentions
- something which is not local to the function and is not constant. */
-
-static int
-nonlocal_mentioned_p_1 (rtx *loc, void *data ATTRIBUTE_UNUSED)
-{
- rtx x = *loc;
- rtx base;
- int regno;
-
- if (! x)
- return 0;
-
- switch (GET_CODE (x))
- {
- case SUBREG:
- if (REG_P (SUBREG_REG (x)))
- {
- /* Global registers are not local. */
- if (REGNO (SUBREG_REG (x)) < FIRST_PSEUDO_REGISTER
- && global_regs[subreg_regno (x)])
- return 1;
- return 0;
- }
- break;
-
- case REG:
- regno = REGNO (x);
- /* Global registers are not local. */
- if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
- return 1;
- return 0;
-
- case SCRATCH:
- case PC:
- case CC0:
- case CONST_INT:
- case CONST_DOUBLE:
- case CONST_VECTOR:
- case CONST:
- case LABEL_REF:
- return 0;
-
- case SYMBOL_REF:
- /* Constants in the function's constants pool are constant. */
- if (CONSTANT_POOL_ADDRESS_P (x))
- return 0;
- return 1;
-
- case CALL:
- /* Non-constant calls and recursion are not local. */
- return 1;
-
- case MEM:
- /* Be overly conservative and consider any volatile memory
- reference as not local. */
- if (MEM_VOLATILE_P (x))
- return 1;
- base = find_base_term (XEXP (x, 0));
- if (base)
- {
- /* A Pmode ADDRESS could be a reference via the structure value
- address or static chain. Such memory references are nonlocal.
-
- Thus, we have to examine the contents of the ADDRESS to find
- out if this is a local reference or not. */
- if (GET_CODE (base) == ADDRESS
- && GET_MODE (base) == Pmode
- && (XEXP (base, 0) == stack_pointer_rtx
- || XEXP (base, 0) == arg_pointer_rtx
-#if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
- || XEXP (base, 0) == hard_frame_pointer_rtx
-#endif
- || XEXP (base, 0) == frame_pointer_rtx))
- return 0;
- /* Constants in the function's constant pool are constant. */
- if (GET_CODE (base) == SYMBOL_REF && CONSTANT_POOL_ADDRESS_P (base))
- return 0;
- }
- return 1;
-
- case UNSPEC_VOLATILE:
- case ASM_INPUT:
- return 1;
-
- case ASM_OPERANDS:
- if (MEM_VOLATILE_P (x))
- return 1;
-
- /* Fall through. */
-
- default:
- break;
- }
-
- return 0;
-}
-
-/* Returns nonzero if X might mention something which is not
- local to the function and is not constant. */
-
-static int
-nonlocal_mentioned_p (rtx x)
-{
- if (INSN_P (x))
- {
- if (CALL_P (x))
- {
- if (! CONST_OR_PURE_CALL_P (x))
- return 1;
- x = CALL_INSN_FUNCTION_USAGE (x);
- if (x == 0)
- return 0;
- }
- else
- x = PATTERN (x);
- }
-
- return for_each_rtx (&x, nonlocal_mentioned_p_1, NULL);
-}
-
-/* A subroutine of nonlocal_referenced_p, returns 1 if *LOC references
- something which is not local to the function and is not constant. */
-
-static int
-nonlocal_referenced_p_1 (rtx *loc, void *data ATTRIBUTE_UNUSED)
-{
- rtx x = *loc;
-
- if (! x)
- return 0;
-
- switch (GET_CODE (x))
- {
- case MEM:
- case REG:
- case SYMBOL_REF:
- case SUBREG:
- return nonlocal_mentioned_p (x);
-
- case CALL:
- /* Non-constant calls and recursion are not local. */
- return 1;
-
- case SET:
- if (nonlocal_mentioned_p (SET_SRC (x)))
- return 1;
-
- if (MEM_P (SET_DEST (x)))
- return nonlocal_mentioned_p (XEXP (SET_DEST (x), 0));
-
- /* If the destination is anything other than a CC0, PC,
- MEM, REG, or a SUBREG of a REG that occupies all of
- the REG, then X references nonlocal memory if it is
- mentioned in the destination. */
- if (GET_CODE (SET_DEST (x)) != CC0
- && GET_CODE (SET_DEST (x)) != PC
- && !REG_P (SET_DEST (x))
- && ! (GET_CODE (SET_DEST (x)) == SUBREG
- && REG_P (SUBREG_REG (SET_DEST (x)))
- && (((GET_MODE_SIZE (GET_MODE (SUBREG_REG (SET_DEST (x))))
- + (UNITS_PER_WORD - 1)) / UNITS_PER_WORD)
- == ((GET_MODE_SIZE (GET_MODE (SET_DEST (x)))
- + (UNITS_PER_WORD - 1)) / UNITS_PER_WORD))))
- return nonlocal_mentioned_p (SET_DEST (x));
- return 0;
-
- case CLOBBER:
- if (MEM_P (XEXP (x, 0)))
- return nonlocal_mentioned_p (XEXP (XEXP (x, 0), 0));
- return 0;
-
- case USE:
- return nonlocal_mentioned_p (XEXP (x, 0));
-
- case ASM_INPUT:
- case UNSPEC_VOLATILE:
- return 1;
-
- case ASM_OPERANDS:
- if (MEM_VOLATILE_P (x))
- return 1;
-
- /* Fall through. */
-
- default:
- break;
- }
-
- return 0;
-}
-
-/* Returns nonzero if X might reference something which is not
- local to the function and is not constant. */
-
-static int
-nonlocal_referenced_p (rtx x)
-{
- if (INSN_P (x))
- {
- if (CALL_P (x))
- {
- if (! CONST_OR_PURE_CALL_P (x))
- return 1;
- x = CALL_INSN_FUNCTION_USAGE (x);
- if (x == 0)
- return 0;
- }
- else
- x = PATTERN (x);
- }
-
- return for_each_rtx (&x, nonlocal_referenced_p_1, NULL);
-}
-
-/* A subroutine of nonlocal_set_p, returns 1 if *LOC sets
- something which is not local to the function and is not constant. */
-
-static int
-nonlocal_set_p_1 (rtx *loc, void *data ATTRIBUTE_UNUSED)
-{
- rtx x = *loc;
-
- if (! x)
- return 0;
-
- switch (GET_CODE (x))
- {
- case CALL:
- /* Non-constant calls and recursion are not local. */
- return 1;
-
- case PRE_INC:
- case PRE_DEC:
- case POST_INC:
- case POST_DEC:
- case PRE_MODIFY:
- case POST_MODIFY:
- return nonlocal_mentioned_p (XEXP (x, 0));
-
- case SET:
- if (nonlocal_mentioned_p (SET_DEST (x)))
- return 1;
- return nonlocal_set_p (SET_SRC (x));
-
- case CLOBBER:
- return nonlocal_mentioned_p (XEXP (x, 0));
-
- case USE:
- return 0;
-
- case ASM_INPUT:
- case UNSPEC_VOLATILE:
- return 1;
-
- case ASM_OPERANDS:
- if (MEM_VOLATILE_P (x))
- return 1;
-
- /* Fall through. */
-
- default:
- break;
- }
-
- return 0;
-}
-
-/* Returns nonzero if X might set something which is not
- local to the function and is not constant. */
-
-static int
-nonlocal_set_p (rtx x)
-{
- if (INSN_P (x))
- {
- if (CALL_P (x))
- {
- if (! CONST_OR_PURE_CALL_P (x))
- return 1;
- x = CALL_INSN_FUNCTION_USAGE (x);
- if (x == 0)
- return 0;
- }
- else
- x = PATTERN (x);
- }
-
- return for_each_rtx (&x, nonlocal_set_p_1, NULL);
-}
-
-/* Mark the function if it is pure or constant. */
-
-void
-mark_constant_function (void)
-{
- rtx insn;
- int nonlocal_memory_referenced;
-
- if (TREE_READONLY (current_function_decl)
- || DECL_IS_PURE (current_function_decl)
- || TREE_THIS_VOLATILE (current_function_decl)
- || current_function_has_nonlocal_goto
- || !targetm.binds_local_p (current_function_decl))
- return;
-
- /* A loop might not return which counts as a side effect. */
- if (mark_dfs_back_edges ())
- return;
-
- nonlocal_memory_referenced = 0;
-
- init_alias_analysis ();
-
- /* Determine if this is a constant or pure function. */
-
- for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
- {
- if (! INSN_P (insn))
- continue;
-
- if (nonlocal_set_p (insn) || global_reg_mentioned_p (insn)
- || volatile_refs_p (PATTERN (insn)))
- break;
-
- if (! nonlocal_memory_referenced)
- nonlocal_memory_referenced = nonlocal_referenced_p (insn);
- }
-
- end_alias_analysis ();
-
- /* Mark the function. */
-
- if (insn)
- ;
- else if (nonlocal_memory_referenced)
- {
- cgraph_rtl_info (current_function_decl)->pure_function = 1;
- DECL_IS_PURE (current_function_decl) = 1;
- }
- else
- {
- cgraph_rtl_info (current_function_decl)->const_function = 1;
- TREE_READONLY (current_function_decl) = 1;
- }
-}
-\f
void
init_alias_once (void)
/* Return true when INSN possibly modify memory contents of MEM
- (ie address can be modified). */
+ (i.e. address can be modified). */
bool
memory_modified_in_insn_p (rtx mem, rtx insn)
{
alias_invariant_size = 0;
}
}
+\f
+/* Do control and data flow analysis; write some of the results to the
+ dump file. */
+static void
+rest_of_handle_cfg (void)
+{
+ if (dump_file)
+ dump_flow_info (dump_file);
+ if (optimize)
+ cleanup_cfg (CLEANUP_EXPENSIVE
+ | (flag_thread_jumps ? CLEANUP_THREADING : 0));
+}
+
+struct tree_opt_pass pass_cfg =
+{
+ "cfg", /* name */
+ NULL, /* gate */
+ rest_of_handle_cfg, /* execute */
+ NULL, /* sub */
+ NULL, /* next */
+ 0, /* static_pass_number */
+ TV_FLOW, /* tv_id */
+ 0, /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ TODO_dump_func, /* todo_flags_finish */
+ 'f' /* letter */
+};
+
#include "gt-alias.h"
OSDN Git Service
