GCC Middle and Back End API Reference
Data Structures | Functions
tree-affine.c File Reference

Data Structures

struct  name_expansion

Functions

double_int double_int_ext_for_comb ()
static void aff_combination_zero ()
void aff_combination_const ()
void aff_combination_elt ()
void aff_combination_scale ()
void aff_combination_add_elt ()
static void aff_combination_add_cst ()
void aff_combination_add ()
void aff_combination_convert ()
void tree_to_aff_combination ()
static tree add_elt_to_tree (tree expr, tree type, tree elt, double_int scale, aff_tree *comb)
tree aff_combination_to_tree ()
void unshare_aff_combination ()
void aff_combination_remove_elt ()
static void aff_combination_add_product (aff_tree *c, double_int coef, tree val, aff_tree *r)
void aff_combination_mult ()
static struct aff_comb_elt * aff_combination_find_elt ()
void aff_combination_expand (aff_tree *comb, struct pointer_map_t **cache)
void tree_to_aff_combination_expand (tree expr, tree type, aff_tree *comb, struct pointer_map_t **cache)
static bool free_name_expansion (const void *key, void **value, void *data)
void free_affine_expand_cache ()
static bool double_int_constant_multiple_p (double_int val, double_int div, bool *mult_set, double_int *mult)
bool aff_combination_constant_multiple_p (aff_tree *val, aff_tree *div, double_int *mult)
static void print_aff ()
DEBUG_FUNCTION void debug_aff ()
void get_inner_reference_aff ()
bool aff_comb_cannot_overlap_p ()

Function Documentation

static tree add_elt_to_tree ( tree  expr,
tree  type,
tree  elt,
double_int  scale,
aff_tree *  comb 
)
static 
Creates EXPR + ELT * SCALE in TYPE.  EXPR is taken from affine
   combination COMB.

References double_int_ext_for_comb(), double_int_to_tree(), double_int::is_minus_one(), double_int::is_negative(), double_int::is_one(), and type().

Referenced by aff_combination_to_tree().

bool aff_comb_cannot_overlap_p ( ) 
Returns true if a region of size SIZE1 at position 0 and a region of
   size SIZE2 at position DIFF cannot overlap.

References double_int::is_negative(), affine_tree_combination::n, affine_tree_combination::offset, and double_int::sle().

Referenced by dr_may_alias_p(), and mem_refs_may_alias_p().

void aff_combination_add ( ) 
Adds COMB2 to COMB1.

References aff_combination_add_cst(), aff_combination_add_elt(), aff_comb_elt::coef, affine_tree_combination::elts, affine_tree_combination::n, affine_tree_combination::offset, affine_tree_combination::rest, and aff_comb_elt::val.

Referenced by aff_combination_dr_offset(), aff_combination_expand(), cand_value_at(), determine_offset(), difference_cost(), dr_may_alias_p(), get_computation_aff(), get_computation_cost_at(), get_inner_reference_aff(), get_loop_invariant_expr_id(), iv_elimination_compare_lt(), mem_refs_may_alias_p(), ptr_difference_cost(), tree_to_aff_combination(), and valid_initializer_p().

static void aff_combination_add_cst ( )
static 
Adds CST to C.

References double_int_ext_for_comb(), and affine_tree_combination::offset.

Referenced by aff_combination_add(), aff_combination_add_product(), and tree_to_aff_combination().

void aff_combination_add_elt ( ) 
Adds ELT * SCALE to COMB.

References aff_comb_elt::coef, double_int_ext_for_comb(), double_int_to_tree(), affine_tree_combination::elts, double_int::is_one(), double_int::is_zero(), affine_tree_combination::n, operand_equal_p(), affine_tree_combination::rest, affine_tree_combination::type, type(), and aff_comb_elt::val.

Referenced by aff_combination_add(), aff_combination_add_product(), aff_combination_expand(), and tree_to_aff_combination().

static void aff_combination_add_product ( aff_tree *  c,
double_int  coef,
tree  val,
aff_tree *  r 
)
static 
Adds C * COEF * VAL to R.  VAL may be NULL, in that case only
   C * COEF is added to R.

References aff_combination_add_cst(), aff_combination_add_elt(), aff_comb_elt::coef, affine_tree_combination::elts, affine_tree_combination::n, affine_tree_combination::offset, affine_tree_combination::rest, type(), and aff_comb_elt::val.

Referenced by aff_combination_mult().

void aff_combination_const ( ) 
Sets COMB to CST.

References aff_combination_zero(), double_int_ext_for_comb(), and affine_tree_combination::offset.

Referenced by aff_combination_dr_offset(), get_inner_reference_aff(), and tree_to_aff_combination().

bool aff_combination_constant_multiple_p ( aff_tree *  val,
aff_tree *  div,
double_int *  mult 
) 
Returns true if VAL = X * DIV for some constant X.  If this is the case,
   X is stored to MULT.

References aff_combination_find_elt(), aff_comb_elt::coef, double_int_constant_multiple_p(), affine_tree_combination::elts, double_int::is_zero(), affine_tree_combination::n, affine_tree_combination::offset, affine_tree_combination::rest, and aff_comb_elt::val.

Referenced by determine_offset(), and valid_initializer_p().

void aff_combination_convert ( ) 
Converts affine combination COMB to TYPE.

References aff_combination_to_tree(), aff_comb_elt::coef, double_int_ext_for_comb(), affine_tree_combination::elts, double_int::is_zero(), affine_tree_combination::n, affine_tree_combination::offset, affine_tree_combination::rest, tree_to_aff_combination(), affine_tree_combination::type, type(), and aff_comb_elt::val.

Referenced by cand_value_at(), and get_computation_aff().

void aff_combination_elt ( ) 
Sets COMB to single element ELT.

References aff_combination_zero(), aff_comb_elt::coef, affine_tree_combination::elts, affine_tree_combination::n, and aff_comb_elt::val.

Referenced by tree_to_aff_combination().

void aff_combination_expand ( aff_tree *  comb,
struct pointer_map_t **  cache 
) 
Expands SSA names in COMB recursively.  CACHE is used to cache the
   results.

References aff_combination_add(), aff_combination_add_elt(), aff_combination_scale(), aff_combination_zero(), cache, exp(), name_expansion::expansion, get_gimple_rhs_class(), gimple_assign_lhs(), gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs_code(), gimple_assign_rhs_to_tree(), GIMPLE_SINGLE_RHS, name_expansion::in_progress, is_gimple_assign(), is_gimple_min_invariant(), pointer_map_create(), pointer_map_insert(), tcc_reference, tree_to_aff_combination_expand(), affine_tree_combination::type, and type().

Referenced by mem_refs_may_alias_p(), and tree_to_aff_combination_expand().

static struct aff_comb_elt* aff_combination_find_elt ( )
staticread 
Returns the element of COMB whose value is VAL, or NULL if no such
   element exists.  If IDX is not NULL, it is set to the index of VAL in
   COMB.

References affine_tree_combination::elts, affine_tree_combination::n, operand_equal_p(), and aff_comb_elt::val.

Referenced by aff_combination_constant_multiple_p().

void aff_combination_mult ( ) 
Multiplies C1 by C2, storing the result to R

References aff_combination_add_product(), aff_combination_zero(), aff_comb_elt::coef, affine_tree_combination::elts, affine_tree_combination::n, affine_tree_combination::offset, affine_tree_combination::rest, affine_tree_combination::type, and aff_comb_elt::val.

Referenced by cand_value_at().

void aff_combination_remove_elt ( ) 
Remove M-th element from COMB.

References aff_comb_elt::coef, affine_tree_combination::elts, affine_tree_combination::n, affine_tree_combination::rest, and aff_comb_elt::val.

Referenced by move_fixed_address_to_symbol(), move_hint_to_base(), move_pointer_to_base(), and move_variant_to_index().

void aff_combination_scale ( ) 
Scales COMB by SCALE.

References aff_combination_zero(), aff_comb_elt::coef, double_int_ext_for_comb(), double_int_to_tree(), affine_tree_combination::elts, double_int::is_one(), double_int::is_zero(), affine_tree_combination::n, affine_tree_combination::offset, affine_tree_combination::rest, affine_tree_combination::type, and aff_comb_elt::val.

Referenced by aff_combination_expand(), determine_offset(), difference_cost(), dr_may_alias_p(), get_computation_aff(), get_loop_invariant_expr_id(), iv_elimination_compare_lt(), mem_refs_may_alias_p(), ptr_difference_cost(), tree_to_aff_combination(), and valid_initializer_p().

tree aff_combination_to_tree ( ) 
Makes tree from the affine combination COMB.

References add_elt_to_tree(), aff_comb_elt::coef, double_int_to_tree(), affine_tree_combination::elts, double_int::is_negative(), affine_tree_combination::n, affine_tree_combination::offset, affine_tree_combination::rest, affine_tree_combination::type, type(), and aff_comb_elt::val.

Referenced by aff_combination_convert(), difference_cost(), get_computation_at(), get_computation_cost_at(), get_loop_invariant_expr_id(), may_eliminate_iv(), and ptr_difference_cost().

static void aff_combination_zero ( )
static 
Initializes affine combination COMB so that its value is zero in TYPE.

References affine_tree_combination::n, affine_tree_combination::offset, affine_tree_combination::rest, affine_tree_combination::type, and type().

Referenced by aff_combination_const(), aff_combination_elt(), aff_combination_expand(), aff_combination_mult(), and aff_combination_scale().

DEBUG_FUNCTION void debug_aff ( ) 
Prints the affine VAL to the standard error, used for debugging.

References print_aff().

static bool double_int_constant_multiple_p ( double_int  val,
double_int  div,
bool *  mult_set,
double_int *  mult 
)
static 
If VAL != CST * DIV for any constant CST, returns false.
   Otherwise, if *MULT_SET is true, additionally compares CST and MULT,
   and if they are different, returns false.  Finally, if neither of these
   two cases occur, true is returned, and CST is stored to MULT and MULT_SET
   is set to true.

References double_int::is_zero(), and double_int::sdivmod().

Referenced by aff_combination_constant_multiple_p().

double_int double_int_ext_for_comb ( ) 
@verbatim Operations with affine combinations of trees.

Copyright (C) 2005-2013 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 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/. 

Extends CST as appropriate for the affine combinations COMB.

References double_int::sext(), and affine_tree_combination::type.

Referenced by add_elt_to_tree(), aff_combination_add_cst(), aff_combination_add_elt(), aff_combination_const(), aff_combination_convert(), aff_combination_scale(), and most_expensive_mult_to_index().

void free_affine_expand_cache ( ) 
Frees memory allocated for the CACHE used by
   tree_to_aff_combination_expand.

References free_name_expansion(), pointer_map_destroy(), and pointer_map_traverse().

Referenced by tree_predictive_commoning_loop(), and tree_ssa_lim_finalize().

static bool free_name_expansion ( const void *  key,
void **  value,
void *  data 
)
static 
Frees memory occupied by struct name_expansion in *VALUE.  Callback for
   pointer_map_traverse.

References exp(), and free().

Referenced by free_affine_expand_cache().

void get_inner_reference_aff ( ) 
Returns address of the reference REF in ADDR.  The size of the accessed
   location is stored to SIZE.

References aff_combination_add(), aff_combination_const(), double_int::from_shwi(), get_inner_reference(), HOST_WIDE_INT, and tree_to_aff_combination().

Referenced by dr_may_alias_p(), and mem_refs_may_alias_p().

static void print_aff ( )
static 
Prints the affine VAL to the FILE.

References aff_comb_elt::coef, dump_double_int(), affine_tree_combination::elts, affine_tree_combination::n, affine_tree_combination::offset, print_generic_expr(), affine_tree_combination::rest, affine_tree_combination::type, and aff_comb_elt::val.

Referenced by debug_aff().

void tree_to_aff_combination ( ) 
Splits EXPR into an affine combination of parts.

References aff_combination_add(), aff_combination_add_cst(), aff_combination_add_elt(), aff_combination_const(), aff_combination_elt(), aff_combination_scale(), build_int_cst(), double_int::from_uhwi(), get_inner_reference(), HOST_WIDE_INT, integer_zerop(), and tree_to_double_int().

Referenced by aff_combination_convert(), cand_value_at(), difference_cost(), get_computation_aff(), get_computation_cost_at(), get_inner_reference_aff(), get_loop_invariant_expr_id(), iv_elimination_compare_lt(), ptr_difference_cost(), and tree_to_aff_combination_expand().

void tree_to_aff_combination_expand ( tree  expr,
tree  type,
aff_tree *  comb,
struct pointer_map_t **  cache 
) 
Similar to tree_to_aff_combination, but follows SSA name definitions
   and expands them recursively.  CACHE is used to cache the expansions
   of the ssa names, to avoid exponential time complexity for cases
   like

   a1 = a0 + a0;
   a2 = a1 + a1;
   a3 = a2 + a2;
   ...

References aff_combination_expand(), and tree_to_aff_combination().

Referenced by aff_combination_dr_offset(), aff_combination_expand(), determine_offset(), and valid_initializer_p().

void unshare_aff_combination ( ) 
Copies the tree elements of COMB to ensure that they are not shared.

References affine_tree_combination::elts, affine_tree_combination::n, affine_tree_combination::rest, unshare_expr(), and aff_comb_elt::val.

Referenced by get_computation_at(), and rewrite_use_address().