GCC Middle and Back End API Reference
tree-chrec.h File Reference

Go to the source code of this file.




static bool automatically_generated_chrec_p ()
static bool tree_is_chrec ()
enum ev_direction scev_direction (const_tree)
tree chrec_fold_plus (tree, tree, tree)
tree chrec_fold_minus (tree, tree, tree)
tree chrec_fold_multiply (tree, tree, tree)
tree chrec_convert (tree, tree, gimple)
tree chrec_convert_rhs (tree, tree, gimple)
tree chrec_convert_aggressive (tree, tree)
tree chrec_apply (unsigned, tree, tree)
tree chrec_apply_map (tree, vec< tree >)
tree chrec_replace_initial_condition (tree, tree)
tree initial_condition (tree)
tree initial_condition_in_loop_num (tree, unsigned)
tree evolution_part_in_loop_num (tree, unsigned)
tree hide_evolution_in_other_loops_than_loop (tree, unsigned)
tree reset_evolution_in_loop (unsigned, tree, tree)
tree chrec_merge (tree, tree)
void for_each_scev_op (tree *, bool(*)(tree *, void *), void *)
bool convert_affine_scev (struct loop *, tree, tree *, tree *, gimple, bool)
bool eq_evolutions_p (const_tree, const_tree)
bool is_multivariate_chrec (const_tree)
bool chrec_contains_symbols (const_tree)
bool chrec_contains_symbols_defined_in_loop (const_tree, unsigned)
bool chrec_contains_undetermined (const_tree)
bool tree_contains_chrecs (const_tree, int *)
bool evolution_function_is_affine_multivariate_p (const_tree, int)
bool evolution_function_is_univariate_p (const_tree)
unsigned nb_vars_in_chrec (tree)
bool evolution_function_is_invariant_p (tree, int)
bool scev_is_linear_expression (tree)
bool evolution_function_right_is_integer_cst (const_tree)
static bool chrec_zerop ()
static bool no_evolution_in_loop_p ()
static tree build_polynomial_chrec (unsigned loop_num, tree left, tree right)
static bool evolution_function_is_constant_p ()
static bool evolution_function_is_affine_in_loop ()
static bool evolution_function_is_affine_p ()
static bool tree_does_not_contain_chrecs ()
static tree chrec_type ()
static tree chrec_fold_op ()


tree chrec_not_analyzed_yet
tree chrec_dont_know
tree chrec_known

Enumeration Type Documentation


Function Documentation

static bool automatically_generated_chrec_p ( )
   After having added an automatically generated element, please
   include it in the following function.  

Referenced by chrec_evaluate(), chrec_fold_automatically_generated_operands(), and chrec_fold_plus().

static tree build_polynomial_chrec ( unsigned  loop_num,
tree  left,
tree  right 
   Build a polynomial chain of recurrence.  
     Types of left and right sides of a chrec should be compatible, but
     pointer CHRECs are special in that the evolution is of ptroff type.  
         Pointer types should occur only on the left hand side, i.e. in
         the base of the chrec, and not in the step.  

Referenced by chrec_evaluate(), chrec_replace_initial_condition(), and hide_evolution_in_other_loops_than_loop().

tree chrec_apply ( unsigned  var,
tree  chrec,
tree  x 

Evaluates "CHREC (X)" when the varying variable is VAR. Example: Given the following parameters,

var = 1 chrec = {3, +, 4}_1 x = 10

The result is given by the Newton's interpolating formula: 3 * {10}{0} + 4 * {10}{1}.

         When the symbols are defined in an outer loop, it is possible
         to symbolically compute the apply, since the symbols are
         constants with respect to the varying loop.  
             "{a, +, b} (x)"  ->  "a + b*x".  

Referenced by analyze_ziv_subscript(), chrec_evaluate(), and compute_overall_effect_of_inner_loop().

tree chrec_apply_map ( tree  ,
vec< tree  
bool chrec_contains_symbols ( const_tree  )
bool chrec_contains_symbols_defined_in_loop ( const_tree  ,
bool chrec_contains_undetermined ( const_tree  )
tree chrec_convert ( tree  ,
tree  ,
tree chrec_convert_aggressive ( tree  ,
tree chrec_convert_rhs ( tree  ,
tree  ,
tree chrec_fold_minus ( tree  type,
tree  op0,
tree  op1 
   Fold the subtraction of two chrecs.  

Referenced by analyze_ziv_subscript(), instantiate_scev_binary(), and max_stmt_executions_tree().

tree chrec_fold_multiply ( tree  type,
tree  op0,
tree  op1 
   Fold the multiplication of two chrecs.  

Referenced by chrec_evaluate(), and instantiate_scev_binary().

static tree chrec_fold_op ( )
tree chrec_fold_plus ( tree  type,
tree  op0,
tree  op1 
tree chrec_merge ( tree  chrec1,
tree  chrec2 
   Merges two evolution functions that were found by following two
   alternate paths of a conditional expression.  

Referenced by analyze_evolution_in_loop().

tree chrec_replace_initial_condition ( tree  chrec,
tree  init_cond 
   Replaces the initial condition in CHREC with INIT_COND.  

References build_polynomial_chrec(), flow_loop_nested_p(), get_chrec_loop(), hide_evolution_in_other_loops_than_loop(), and initial_condition().

static tree chrec_type ( )
   Returns the type of the chrec.  

Referenced by chrec_evaluate(), and instantiate_scev_3().

static bool chrec_zerop ( )
   Determines whether CHREC is equal to zero.  
bool convert_affine_scev ( struct loop loop,
tree  type,
tree base,
tree step,
gimple  at_stmt,
bool  use_overflow_semantics 
   Converts BASE and STEP of affine scev to TYPE.  LOOP is the loop whose iv
   the scev corresponds to.  AT_STMT is the statement at that the scev is
   evaluated.  USE_OVERFLOW_SEMANTICS is true if this function should assume that
   the rules for overflow of the given language apply (e.g., that signed
   arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary
   tests, but also to enforce that the result follows them.  Returns true if the
   conversion succeeded, false otherwise.  
     In general,
     (TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE -- sign extend) STEP * i,
     but we must check some assumptions.

     1) If [BASE, +, STEP] wraps, the equation is not valid when precision
        of CT is smaller than the precision of TYPE.  For example, when we
        cast unsigned char [254, +, 1] to unsigned, the values on left side
        are 254, 255, 0, 1, ..., but those on the right side are
        254, 255, 256, 257, ...
     2) In case that we must also preserve the fact that signed ivs do not
        overflow, we must additionally check that the new iv does not wrap.
        For example, unsigned char [125, +, 1] casted to signed char could
        become a wrapping variable with values 125, 126, 127, -128, -127, ...,
        which would confuse optimizers that assume that this does not
         We can avoid checking whether the result overflows in the following

         -- must_check_src_overflow is true, and the range of TYPE is superset
            of the range of CT -- i.e., in all cases except if CT signed and
            TYPE unsigned.
         -- both CT and TYPE have the same precision and signedness, and we
            verify instead that the source does not overflow (this may be
            easier than verifying it for the result, as we may use the
            information about the semantics of overflow in CT).  
     The step must be sign extended, regardless of the signedness
     of CT and TYPE.  This only needs to be handled specially when
     CT is unsigned -- to avoid e.g. unsigned char [100, +, 255]
     (with values 100, 99, 98, ...) from becoming signed or unsigned
     [100, +, 255] with values 100, 355, ...; the sign-extension is
     performed by default when CT is signed.  
         Note that in this case we cannot use the fact that signed variables
         do not overflow, as this is what we are verifying for the new iv.  
bool eq_evolutions_p ( const_tree  ,
static bool evolution_function_is_affine_in_loop ( )
   Determine whether CHREC is an affine evolution function in LOOPNUM.  
bool evolution_function_is_affine_multivariate_p ( const_tree  ,
static bool evolution_function_is_affine_p ( )
   Determine whether CHREC is an affine evolution function or not.  

Referenced by analyze_ziv_subscript(), and chrec_evaluate().

static bool evolution_function_is_constant_p ( )
   Determines whether the expression CHREC is a constant.  

Referenced by free_conflict_function().

bool evolution_function_is_invariant_p ( tree  ,
bool evolution_function_is_univariate_p ( const_tree  )
bool evolution_function_right_is_integer_cst ( const_tree  )
tree evolution_part_in_loop_num ( tree  chrec,
unsigned  loop_num 
   Returns the evolution part in LOOP_NUM.  Example: the call
   evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns
   {1, +, 2}_1  

Referenced by extract_range_from_comparison().

void for_each_scev_op ( tree scev,
bool(*)(tree *, void *)  cbck,
void *  data 
   Iterates over all the components of SCEV, and calls CBCK.  
tree hide_evolution_in_other_loops_than_loop ( tree  chrec,
unsigned  loop_num 
   Returns a univariate function that represents the evolution in
   LOOP_NUM.  Mask the evolution of any other loop.  
           There is no evolution in this loop.  

References build_polynomial_chrec(), chrec_component_in_loop_num(), flow_loop_nested_p(), and get_chrec_loop().

Referenced by chrec_replace_initial_condition().

tree initial_condition ( tree  )
tree initial_condition_in_loop_num ( tree  chrec,
unsigned  loop_num 
   Returns the initial condition in LOOP_NUM.  Example: the call
   initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns
   {0, +, 1}_1  

Referenced by extract_range_from_comparison().

bool is_multivariate_chrec ( const_tree  )
unsigned nb_vars_in_chrec ( tree  )
static bool no_evolution_in_loop_p ( )
   Determines whether CHREC is a loop invariant with respect to LOOP_NUM.
   Set the result in RES and return true when the property can be computed.  

Referenced by analyze_scalar_evolution().

tree reset_evolution_in_loop ( unsigned  loop_num,
tree  chrec,
tree  new_evol 
   Set or reset the evolution of CHREC to NEW_EVOL in loop LOOP_NUM.
   This function is essentially used for setting the evolution to
   chrec_dont_know, for example after having determined that it is
   impossible to say how many times a loop will execute.  
enum ev_direction scev_direction ( const_tree  )
bool scev_is_linear_expression ( tree  )
bool tree_contains_chrecs ( const_tree  ,
int *   
static bool tree_does_not_contain_chrecs ( )
   Determines whether EXPR does not contains chrec expressions.  

References chrec_fold_plus().

static bool tree_is_chrec ( )
   The tree nodes aka. CHRECs.  

Referenced by vect_can_advance_ivs_p().

Variable Documentation

tree chrec_known
   When the analyzer has detected that a property will never
   happen, then it qualifies it with chrec_known.  

Referenced by analyze_overlapping_iterations(), instantiate_scev_3(), omega_extract_distance_vectors(), and vect_analyze_data_ref_dependences().

tree chrec_not_analyzed_yet
   The following trees are unique elements.  Thus the comparison of another
   element to these elements should be done on the pointer to these trees,
   and not on their value.  
   The following trees are unique elements.  Thus the comparison of
   another element to these elements should be done on the pointer to
   these trees, and not on their value.  
   The SSA_NAMEs that are not yet analyzed are qualified with NULL_TREE.  

Referenced by analyze_evolution_in_loop().