GCC Middle and Back End API Reference
tree-ssa-alias.c File Reference
#include "ggc.h"
Include dependency graph for tree-ssa-alias.c:

Functions

void dump_alias_stats ()
bool ptr_deref_may_alias_global_p ()
static bool ptr_deref_may_alias_decl_p ()
bool ptr_derefs_may_alias_p ()
static bool ptr_deref_may_alias_ref_p_1 ()
bool ref_may_alias_global_p ()
bool stmt_may_clobber_global_p ()
void dump_alias_info ()
DEBUG_FUNCTION void debug_alias_info ()
void dump_points_to_solution ()
DEBUG_FUNCTION void debug ()
void dump_points_to_info_for ()
DEBUG_FUNCTION void debug_points_to_info_for ()
void ao_ref_init ()
tree ao_ref_base ()
static alias_set_type ao_ref_base_alias_set ()
alias_set_type ao_ref_alias_set ()
void ao_ref_init_from_ptr_and_size ()
static int same_type_for_tbaa ()
static bool aliasing_component_refs_p (tree ref1, alias_set_type ref1_alias_set, alias_set_type base1_alias_set, HOST_WIDE_INT offset1, HOST_WIDE_INT max_size1, tree ref2, alias_set_type ref2_alias_set, alias_set_type base2_alias_set, HOST_WIDE_INT offset2, HOST_WIDE_INT max_size2, bool ref2_is_decl)
static bool nonoverlapping_component_refs_of_decl_p ()
static bool decl_refs_may_alias_p (tree ref1, tree base1, HOST_WIDE_INT offset1, HOST_WIDE_INT max_size1, tree ref2, tree base2, HOST_WIDE_INT offset2, HOST_WIDE_INT max_size2)
static bool indirect_ref_may_alias_decl_p (tree ref1, tree base1, HOST_WIDE_INT offset1, HOST_WIDE_INT max_size1, alias_set_type ref1_alias_set, alias_set_type base1_alias_set, tree ref2, tree base2, HOST_WIDE_INT offset2, HOST_WIDE_INT max_size2, alias_set_type ref2_alias_set, alias_set_type base2_alias_set, bool tbaa_p)
static bool indirect_refs_may_alias_p (tree ref1, tree base1, HOST_WIDE_INT offset1, HOST_WIDE_INT max_size1, alias_set_type ref1_alias_set, alias_set_type base1_alias_set, tree ref2, tree base2, HOST_WIDE_INT offset2, HOST_WIDE_INT max_size2, alias_set_type ref2_alias_set, alias_set_type base2_alias_set, bool tbaa_p)
bool refs_may_alias_p_1 ()
bool refs_may_alias_p ()
bool refs_anti_dependent_p ()
bool refs_output_dependent_p ()
static bool ref_maybe_used_by_call_p_1 ()
static bool ref_maybe_used_by_call_p ()
bool ref_maybe_used_by_stmt_p ()
static bool call_may_clobber_ref_p_1 ()
bool call_may_clobber_ref_p ()
bool stmt_may_clobber_ref_p_1 ()
bool stmt_may_clobber_ref_p ()
static bool stmt_kills_ref_p_1 ()
bool stmt_kills_ref_p ()
static bool maybe_skip_until (gimple phi, tree target, ao_ref *ref, tree vuse, unsigned int *cnt, bitmap *visited, bool abort_on_visited)
static tree get_continuation_for_phi_1 (gimple phi, tree arg0, tree arg1, ao_ref *ref, unsigned int *cnt, bitmap *visited, bool abort_on_visited)
tree get_continuation_for_phi (gimple phi, ao_ref *ref, unsigned int *cnt, bitmap *visited, bool abort_on_visited)
void * walk_non_aliased_vuses (ao_ref *ref, tree vuse, void *(*walker)(ao_ref *, tree, unsigned int, void *), void *(*translate)(ao_ref *, tree, void *), void *data)
static unsigned int walk_aliased_vdefs_1 (ao_ref *ref, tree vdef, bool(*walker)(ao_ref *, tree, void *), void *data, bitmap *visited, unsigned int cnt)
unsigned int walk_aliased_vdefs (ao_ref *ref, tree vdef, bool(*walker)(ao_ref *, tree, void *), void *data, bitmap *visited)

Variables

struct {
   unsigned HOST_WIDE_INT   refs_may_alias_p_may_alias
   unsigned HOST_WIDE_INT   refs_may_alias_p_no_alias
   unsigned HOST_WIDE_INT   ref_maybe_used_by_call_p_may_alias
   unsigned HOST_WIDE_INT   ref_maybe_used_by_call_p_no_alias
   unsigned HOST_WIDE_INT   call_may_clobber_ref_p_may_alias
   unsigned HOST_WIDE_INT   call_may_clobber_ref_p_no_alias
alias_stats

Function Documentation

static bool aliasing_component_refs_p ( tree  ref1,
alias_set_type  ref1_alias_set,
alias_set_type  base1_alias_set,
HOST_WIDE_INT  offset1,
HOST_WIDE_INT  max_size1,
tree  ref2,
alias_set_type  ref2_alias_set,
alias_set_type  base2_alias_set,
HOST_WIDE_INT  offset2,
HOST_WIDE_INT  max_size2,
bool  ref2_is_decl 
)
static
Determine if the two component references REF1 and REF2 which are
   based on access types TYPE1 and TYPE2 and of which at least one is based
   on an indirect reference may alias.  REF2 is the only one that can
   be a decl in which case REF2_IS_DECL is true.
   REF1_ALIAS_SET, BASE1_ALIAS_SET, REF2_ALIAS_SET and BASE2_ALIAS_SET
   are the respective alias sets.   

References alias_set_subset_of(), get_ref_base_and_extent(), handled_component_p(), HOST_WIDE_INT, ranges_overlap_p(), and same_type_for_tbaa().

Referenced by indirect_ref_may_alias_decl_p(), and indirect_refs_may_alias_p().

alias_set_type ao_ref_alias_set ( )
Returns the reference alias set of the memory reference *REF.   

References get_alias_set(), ao_ref_s::ref, and ao_ref_s::ref_alias_set.

Referenced by refs_may_alias_p_1().

static alias_set_type ao_ref_base_alias_set ( )
static
Returns the base object alias set of the memory reference *REF.   

References ao_ref_s::base_alias_set, get_alias_set(), handled_component_p(), and ao_ref_s::ref.

Referenced by refs_may_alias_p_1().

void ao_ref_init_from_ptr_and_size ( )
Init an alias-oracle reference representation from a gimple pointer
   PTR and a gimple size SIZE in bytes.  If SIZE is NULL_TREE the the
   size is assumed to be unknown.  The access is assumed to be only
   to or after of the pointer target, not before it.   

References ao_ref_s::base, ao_ref_s::base_alias_set, get_ref_base_and_extent(), host_integerp(), HOST_WIDE_INT, ao_ref_s::max_size, ao_ref_s::offset, ao_ref_s::ref, ao_ref_s::ref_alias_set, ao_ref_s::size, and ao_ref_s::volatile_p.

Referenced by call_may_clobber_ref_p_1(), determine_known_aggregate_parts(), fold_builtin_memory_op(), maybe_invalidate(), parm_ref_data_pass_through_p(), and ref_maybe_used_by_call_p_1().

bool call_may_clobber_ref_p ( )
If the call in statement CALL may clobber the memory reference REF
   return true, otherwise return false.   

References alias_stats, ao_ref_init(), and call_may_clobber_ref_p_1().

Referenced by dest_safe_for_nrv_p(), and find_tail_calls().

DEBUG_FUNCTION void debug ( )
Unified dump function for pt_solution.   

References dump_points_to_solution().

DEBUG_FUNCTION void debug_alias_info ( void  )
Dump alias information on stderr.   

References dump_alias_info().

DEBUG_FUNCTION void debug_points_to_info_for ( )
Dump points-to information for VAR into stderr.   

References dump_points_to_info_for().

static bool decl_refs_may_alias_p ( tree  ref1,
tree  base1,
HOST_WIDE_INT  offset1,
HOST_WIDE_INT  max_size1,
tree  ref2,
tree  base2,
HOST_WIDE_INT  offset2,
HOST_WIDE_INT  max_size2 
)
static
Return true if two memory references based on the variables BASE1
   and BASE2 constrained to [OFFSET1, OFFSET1 + MAX_SIZE1) and
   [OFFSET2, OFFSET2 + MAX_SIZE2) may alias.  REF1 and REF2
   if non-NULL are the complete memory reference trees.   

References handled_component_p(), nonoverlapping_component_refs_of_decl_p(), and ranges_overlap_p().

Referenced by refs_may_alias_p_1().

void dump_alias_stats ( )

References alias_stats, and HOST_WIDE_INT_PRINT_DEC.

Referenced by dump_memory_report().

void dump_points_to_info_for ( )
Dump points-to information for SSA_NAME PTR into FILE.   

References dump_flags, dump_points_to_solution(), print_generic_expr(), and ptr_info_def::pt.

Referenced by debug_points_to_info_for(), dump_alias_info(), and dump_variable().

tree get_continuation_for_phi ( gimple  phi,
ao_ref ref,
unsigned int *  cnt,
bitmap visited,
bool  abort_on_visited 
)
Starting from a PHI node for the virtual operand of the memory reference
   REF find a continuation virtual operand that allows to continue walking
   statements dominating PHI skipping only statements that cannot possibly
   clobber REF.  Increments *CNT for each alias disambiguation done.
   Returns NULL_TREE if no suitable virtual operand can be found.   

References CDI_DOMINATORS, dominated_by_p(), get_continuation_for_phi_1(), and gimple_phi_num_args().

Referenced by maybe_skip_until(), translate_vuse_through_block(), and walk_non_aliased_vuses().

static tree get_continuation_for_phi_1 ( gimple  phi,
tree  arg0,
tree  arg1,
ao_ref ref,
unsigned int *  cnt,
bitmap visited,
bool  abort_on_visited 
)
static
For two PHI arguments ARG0 and ARG1 try to skip non-aliasing code
   until we hit the phi argument definition that dominates the other one.
   Return that, or NULL_TREE if there is no such definition.   

References CDI_DOMINATORS, dominated_by_p(), gimple_nop_p(), gimple_vuse(), maybe_skip_until(), and stmt_may_clobber_ref_p_1().

Referenced by get_continuation_for_phi().

static bool indirect_ref_may_alias_decl_p ( tree  ref1,
tree  base1,
HOST_WIDE_INT  offset1,
HOST_WIDE_INT  max_size1,
alias_set_type  ref1_alias_set,
alias_set_type  base1_alias_set,
tree  ref2,
tree  base2,
HOST_WIDE_INT  offset2,
HOST_WIDE_INT  max_size2,
alias_set_type  ref2_alias_set,
alias_set_type  base2_alias_set,
bool  tbaa_p 
)
static
Return true if an indirect reference based on *PTR1 constrained
   to [OFFSET1, OFFSET1 + MAX_SIZE1) may alias a variable based on BASE2
   constrained to [OFFSET2, OFFSET2 + MAX_SIZE2).  *PTR1 and BASE2 have
   the alias sets BASE1_ALIAS_SET and BASE2_ALIAS_SET which can be -1
   in which case they are computed on-demand.  REF1 and REF2
   if non-NULL are the complete memory reference trees.   

References alias_sets_conflict_p(), aliasing_component_refs_p(), exact_log2(), get_alias_set(), get_deref_alias_set(), handled_component_p(), HOST_WIDE_INT, double_int::is_negative(), double_int::low, double_int::lshift(), mem_ref_offset(), ptr_deref_may_alias_decl_p(), ranges_overlap_p(), same_type_for_tbaa(), and tree_int_cst_lt().

Referenced by refs_may_alias_p_1().

static bool indirect_refs_may_alias_p ( tree  ref1,
tree  base1,
HOST_WIDE_INT  offset1,
HOST_WIDE_INT  max_size1,
alias_set_type  ref1_alias_set,
alias_set_type  base1_alias_set,
tree  ref2,
tree  base2,
HOST_WIDE_INT  offset2,
HOST_WIDE_INT  max_size2,
alias_set_type  ref2_alias_set,
alias_set_type  base2_alias_set,
bool  tbaa_p 
)
static
Return true if two indirect references based on *PTR1
   and *PTR2 constrained to [OFFSET1, OFFSET1 + MAX_SIZE1) and
   [OFFSET2, OFFSET2 + MAX_SIZE2) may alias.  *PTR1 and *PTR2 have
   the alias sets BASE1_ALIAS_SET and BASE2_ALIAS_SET which can be -1
   in which case they are computed on-demand.  REF1 and REF2
   if non-NULL are the complete memory reference trees.  

References alias_sets_conflict_p(), aliasing_component_refs_p(), cfun, exact_log2(), get_deref_alias_set(), gimple_in_ssa_p(), handled_component_p(), double_int::is_negative(), double_int::low, double_int::lshift(), mem_ref_offset(), operand_equal_p(), ptr_derefs_may_alias_p(), ranges_overlap_p(), and same_type_for_tbaa().

Referenced by refs_may_alias_p_1().

static bool maybe_skip_until ( gimple  phi,
tree  target,
ao_ref ref,
tree  vuse,
unsigned int *  cnt,
bitmap visited,
bool  abort_on_visited 
)
static
Walk the virtual use-def chain of VUSE until hitting the virtual operand
   TARGET or a statement clobbering the memory reference REF in which
   case false is returned.  The walk starts with VUSE, one argument of PHI.   

References bitmap_bit_p(), bitmap_set_bit(), get_continuation_for_phi(), gimple_bb(), gimple_nop_p(), gimple_vuse(), and stmt_may_clobber_ref_p_1().

Referenced by get_continuation_for_phi_1().

static bool nonoverlapping_component_refs_of_decl_p ( )
static
Return true if we can determine that component references REF1 and REF2,
   that are within a common DECL, cannot overlap.   

References handled_component_p(), and integer_zerop().

Referenced by decl_refs_may_alias_p().

static bool ptr_deref_may_alias_decl_p ( )
static
Return true if dereferencing PTR may alias DECL.
   The caller is responsible for applying TBAA to see if PTR
   may access DECL at all.   

References get_base_address(), may_be_aliased(), ptr_info_def::pt, and pt_solution_includes().

Referenced by indirect_ref_may_alias_decl_p(), ptr_deref_may_alias_ref_p_1(), and ptr_derefs_may_alias_p().

bool ptr_deref_may_alias_global_p ( )
Return true, if dereferencing PTR may alias with a global variable.   

References ptr_info_def::pt, and pt_solution_includes_global().

Referenced by check_op(), ref_may_alias_global_p(), ref_maybe_used_by_stmt_p(), and thread_private_new_memory().

static bool ptr_deref_may_alias_ref_p_1 ( )
static
Return true if dereferencing PTR may alias *REF.
   The caller is responsible for applying TBAA to see if PTR
   may access *REF at all.   

References ao_ref_base(), ptr_deref_may_alias_decl_p(), and ptr_derefs_may_alias_p().

Referenced by call_may_clobber_ref_p_1(), and ref_maybe_used_by_call_p_1().

bool ptr_derefs_may_alias_p ( )
Return true if dereferenced PTR1 and PTR2 may alias.
   The caller is responsible for applying TBAA to see if accesses
   through PTR1 and PTR2 may conflict at all.   

References get_base_address(), ptr_info_def::pt, pt_solutions_intersect(), and ptr_deref_may_alias_decl_p().

Referenced by dr_may_alias_p(), generate_memcpy_builtin(), indirect_refs_may_alias_p(), and ptr_deref_may_alias_ref_p_1().

bool ref_may_alias_global_p ( )
Return true whether REF may refer to global memory.   

References get_base_address(), is_global_var(), and ptr_deref_may_alias_global_p().

Referenced by stmt_may_clobber_global_p().

static bool ref_maybe_used_by_call_p ( )
static
bool refs_anti_dependent_p ( )
Returns true if there is a anti-dependence for the STORE that
   executes after the LOAD.   

References ao_ref_init(), and refs_may_alias_p_1().

Referenced by dr_may_alias_p().

bool refs_output_dependent_p ( )
Returns true if there is a output dependence for the stores
   STORE1 and STORE2.   

References ao_ref_init(), and refs_may_alias_p_1().

Referenced by dr_may_alias_p().

static int same_type_for_tbaa ( )
inlinestatic
Return 1 if TYPE1 and TYPE2 are to be considered equivalent for the
   purpose of TBAA.  Return 0 if they are distinct and -1 if we cannot
   decide.   

References get_alias_set().

Referenced by aliasing_component_refs_p(), indirect_ref_may_alias_decl_p(), and indirect_refs_may_alias_p().

bool stmt_kills_ref_p ( )
bool stmt_may_clobber_global_p ( )
Return true whether STMT may clobber global memory.   

References gimple_assign_lhs(), gimple_vdef(), and ref_may_alias_global_p().

Referenced by dse_possible_dead_store_p(), and mark_stmt_if_obviously_necessary().

bool stmt_may_clobber_ref_p ( )
static unsigned int walk_aliased_vdefs_1 ( ao_ref ref,
tree  vdef,
bool(*)(ao_ref *, tree, void *)  walker,
void *  data,
bitmap visited,
unsigned int  cnt 
)
static
Based on the memory reference REF call WALKER for each vdef which
   defining statement may clobber REF, starting with VDEF.  If REF
   is NULL_TREE, each defining statement is visited.

   WALKER is called with REF, the current vdef and DATA.  If WALKER
   returns true the walk is stopped, otherwise it continues.

   At PHI nodes walk_aliased_vdefs forks into one walk for reach
   PHI argument (but only one walk continues on merge points), the
   return value is true if any of the walks was successful.

   The function returns the number of statements walked.   

References bitmap_set_bit(), gimple_nop_p(), gimple_phi_arg_def(), gimple_phi_num_args(), gimple_vuse(), stmt_may_clobber_ref_p_1(), and visited.

Referenced by walk_aliased_vdefs().

void* walk_non_aliased_vuses ( ao_ref ref,
tree  vuse,
void *(*)(ao_ref *, tree, unsigned int, void *)  walker,
void *(*)(ao_ref *, tree, void *)  translate,
void *  data 
)
Based on the memory reference REF and its virtual use VUSE call
   WALKER for each virtual use that is equivalent to VUSE, including VUSE
   itself.  That is, for each virtual use for which its defining statement
   does not clobber REF.

   WALKER is called with REF, the current virtual use and DATA.  If
   WALKER returns non-NULL the walk stops and its result is returned.
   At the end of a non-successful walk NULL is returned.

   TRANSLATE if non-NULL is called with a pointer to REF, the virtual
   use which definition is a statement that may clobber REF and DATA.
   If TRANSLATE returns (void *)-1 the walk stops and NULL is returned.
   If TRANSLATE returns non-NULL the walk stops and its result is returned.
   If TRANSLATE returns NULL the walk continues and TRANSLATE is supposed
   to adjust REF and *DATA to make that valid.

   TODO: Cache the vector of equivalent vuses per ref, vuse pair.   

References get_continuation_for_phi(), gimple_nop_p(), gimple_vuse(), stmt_may_clobber_ref_p_1(), timevar_pop(), timevar_push(), and visited.

Referenced by vn_reference_lookup(), and vn_reference_lookup_pieces().


Variable Documentation

struct { ... } alias_stats
@verbatim Alias analysis for trees.

Copyright (C) 2004-2013 Free Software Foundation, Inc. Contributed by Diego Novillo dnovi.nosp@m.llo@.nosp@m.redha.nosp@m.t.co.nosp@m.m

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 3, or (at your option) any later version.

GCC is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 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 COPYING3. If not see http://www.gnu.org/licenses/.

Broad overview of how alias analysis on gimple works:

   Statements clobbering or using memory are linked through the
   virtual operand factored use-def chain.  The virtual operand
   is unique per function, its symbol is accessible via gimple_vop (cfun).
   Virtual operands are used for efficiently walking memory statements
   in the gimple IL and are useful for things like value-numbering as
   a generation count for memory references.

   SSA_NAME pointers may have associated points-to information
   accessible via the SSA_NAME_PTR_INFO macro.  Flow-insensitive
   points-to information is (re-)computed by the TODO_rebuild_alias
   pass manager todo.  Points-to information is also used for more
   precise tracking of call-clobbered and call-used variables and
   related disambiguations.

   This file contains functions for disambiguating memory references,
   the so called alias-oracle and tools for walking of the gimple IL.

   The main alias-oracle entry-points are

   bool stmt_may_clobber_ref_p (gimple, tree)

     This function queries if a statement may invalidate (parts of)
     the memory designated by the reference tree argument.

   bool ref_maybe_used_by_stmt_p (gimple, tree)

     This function queries if a statement may need (parts of) the
     memory designated by the reference tree argument.

   There are variants of these functions that only handle the call
   part of a statement, call_may_clobber_ref_p and ref_maybe_used_by_call_p.
   Note that these do not disambiguate against a possible call lhs.

   bool refs_may_alias_p (tree, tree)

     This function tries to disambiguate two reference trees.

   bool ptr_deref_may_alias_global_p (tree)

     This function queries if dereferencing a pointer variable may
     alias global memory.

   More low-level disambiguators are available and documented in
   this file.  Low-level disambiguators dealing with points-to
   information are in tree-ssa-structalias.c.   
Query statistics for the different low-level disambiguators.
   A high-level query may trigger multiple of them.   

Referenced by call_may_clobber_ref_p(), dump_alias_stats(), ref_maybe_used_by_call_p(), and refs_may_alias_p().

unsigned HOST_WIDE_INT call_may_clobber_ref_p_may_alias
unsigned HOST_WIDE_INT call_may_clobber_ref_p_no_alias
unsigned HOST_WIDE_INT ref_maybe_used_by_call_p_may_alias
unsigned HOST_WIDE_INT ref_maybe_used_by_call_p_no_alias
unsigned HOST_WIDE_INT refs_may_alias_p_may_alias
unsigned HOST_WIDE_INT refs_may_alias_p_no_alias