GCC Middle and Back End API Reference
tree-affine.c File Reference

Data Structures

struct  name_expansion


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_eltaff_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 
   Creates EXPR + ELT * SCALE in TYPE.  EXPR is taken from affine
   combination COMB.  
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.  
     Unless the difference is a constant, we fail.  
         The second object is before the first one, we succeed if the last
         element of the second object is before the start of the first one.  
         We succeed if the second object starts after the first one ends.  

Referenced by conflict_fn_no_dependence().

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

References aff_combination_add_elt(), and affine_tree_combination::rest.

void aff_combination_const ( )
   Sets COMB to CST.  

Referenced by merge_comps(), and tree_to_aff_combination().

bool aff_combination_constant_multiple_p ( aff_tree val,
aff_tree div,
double_int mult 
void aff_combination_convert ( )
   Converts affine combination COMB to TYPE.  
void aff_combination_elt ( )
   Sets COMB to single element ELT.  

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
         Look through some conversions.  
         We do not know whether the reference retains its value at the
         place where the expansion is used.  
             In principle this is a generally valid folding, but
             it is not unconditionally an optimization, so do it
             here and not in fold_unary.  
             Convert (T1)(X *+- CST) into (T1)X *+- (T1)CST if T1 is wider
             than the type of X and overflow for the type of X is
             Since we follow the definitions in the SSA form, we should not
             enter a cycle unless we pass through a phi node.  
         Accumulate the new terms to TO_ADD, so that we do not modify
         COMB while traversing it; include the term -coef * E, to remove
         it from COMB.  
static struct aff_comb_elt* aff_combination_find_elt ( )
   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

Referenced by double_int_constant_multiple_p().

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

References affine_tree_combination::elts.

void aff_combination_scale ( )
   Scales COMB by SCALE.  
         A coefficient may become zero due to overflow.  Remove the zero

References aff_combination_zero(), and affine_tree_combination::type.

Referenced by conflict_fn_no_dependence(), and tree_to_aff_combination().

tree aff_combination_to_tree ( )
   Makes tree from the affine combination COMB.  
     Ensure that we get x - 1, not x + (-1) or x + 0xff..f if x is

Referenced by aff_combination_add().

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

Referenced by aff_combination_scale().

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

References affine_tree_combination::n.

static bool double_int_constant_multiple_p ( double_int  val,
double_int  div,
bool *  mult_set,
double_int mult 
   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 aff_combination_find_elt(), aff_comb_elt::coef, 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.

double_int double_int_ext_for_comb ( )

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.  

Referenced by aff_combination_add_elt().

void free_affine_expand_cache ( )
   Frees memory allocated for the CACHE used by
static bool free_name_expansion ( const void *  key,
void **  value,
void *  data 
   Frees memory occupied by struct name_expansion in *VALUE.  Callback for

References double_int::is_zero().

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

References double_int::is_negative().

Referenced by conflict_fn_no_dependence().

static void print_aff ( )
   Prints the affine VAL to the FILE. 
void tree_to_aff_combination ( )
   Splits EXPR into an affine combination of parts.  
         ~x = -x - 1 
         Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR.  

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(), integer_zerop(), and tree_to_double_int().

Referenced by aff_combination_add().

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

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

Referenced by merge_comps().

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

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