GCC Middle and Back End API Reference
tree-affine.cc File Reference
#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "backend.h"
#include "rtl.h"
#include "tree.h"
#include "gimple.h"
#include "ssa.h"
#include "tree-pretty-print.h"
#include "fold-const.h"
#include "tree-affine.h"
#include "gimplify.h"
#include "dumpfile.h"
#include "cfgexpand.h"
#include "value-query.h"
Include dependency graph for tree-affine.cc:

Data Structures

class  name_expansion
 

Functions

static widest_int wide_int_ext_for_comb (const widest_int &cst, tree type)
 
static poly_widest_int wide_int_ext_for_comb (const poly_widest_int &cst, tree type)
 
static void aff_combination_zero (aff_tree *comb, tree type)
 
void aff_combination_const (aff_tree *comb, tree type, const poly_widest_int &cst)
 
void aff_combination_elt (aff_tree *comb, tree type, tree elt)
 
void aff_combination_scale (aff_tree *comb, const widest_int &scale_in)
 
void aff_combination_add_elt (aff_tree *comb, tree elt, const widest_int &scale_in)
 
static void aff_combination_add_cst (aff_tree *c, const poly_widest_int &cst)
 
void aff_combination_add (aff_tree *comb1, aff_tree *comb2)
 
void aff_combination_convert (aff_tree *comb, tree type)
 
static bool expr_to_aff_combination (aff_tree *comb, tree_code code, tree type, tree op0, tree op1=NULL_TREE)
 
void tree_to_aff_combination (tree expr, tree type, aff_tree *comb)
 
static tree add_elt_to_tree (tree expr, tree type, tree elt, const widest_int &scale_in)
 
tree aff_combination_to_tree (aff_tree *comb)
 
void unshare_aff_combination (aff_tree *comb)
 
void aff_combination_remove_elt (aff_tree *comb, unsigned m)
 
static void aff_combination_add_product (aff_tree *c, const widest_int &coef, tree val, aff_tree *r)
 
void aff_combination_mult (aff_tree *c1, aff_tree *c2, aff_tree *r)
 
static class aff_comb_eltaff_combination_find_elt (aff_tree *comb, tree val, unsigned *idx)
 
void aff_combination_expand (aff_tree *comb, hash_map< tree, name_expansion * > **cache)
 
void tree_to_aff_combination_expand (tree expr, tree type, aff_tree *comb, hash_map< tree, name_expansion * > **cache)
 
bool free_name_expansion (tree const &, name_expansion **value, void *)
 
void free_affine_expand_cache (hash_map< tree, name_expansion * > **cache)
 
static bool wide_int_constant_multiple_p (const poly_widest_int &val, const poly_widest_int &div, bool *mult_set, poly_widest_int *mult)
 
bool aff_combination_constant_multiple_p (aff_tree *val, aff_tree *div, poly_widest_int *mult)
 
static void print_aff (FILE *file, aff_tree *val)
 
DEBUG_FUNCTION void debug_aff (aff_tree *val)
 
tree get_inner_reference_aff (tree ref, aff_tree *addr, poly_widest_int *size)
 
bool aff_comb_cannot_overlap_p (aff_tree *diff, const poly_widest_int &size1, const poly_widest_int &size2)
 

Function Documentation

◆ add_elt_to_tree()

static tree add_elt_to_tree ( tree expr,
tree type,
tree elt,
const widest_int & scale_in )
static
Creates EXPR + ELT * SCALE in TYPE.  EXPR is taken from affine
combination COMB.   

References fold_build1, fold_build2, fold_convert, wi::neg_p(), wide_int_ext_for_comb(), and wide_int_to_tree().

Referenced by aff_combination_to_tree().

◆ aff_comb_cannot_overlap_p()

bool aff_comb_cannot_overlap_p ( aff_tree * diff,
const poly_widest_int & size1,
const poly_widest_int & size2 )
Returns true if a region of size SIZE1 at position 0 and a region of
size SIZE2 at position DIFF cannot overlap.   

References known_le.

Referenced by dr_may_alias_p(), generate_memcpy_builtin(), and mem_refs_may_alias_p().

◆ aff_combination_add()

◆ aff_combination_add_cst()

static void aff_combination_add_cst ( aff_tree * c,
const poly_widest_int & cst )
static

◆ aff_combination_add_elt()

◆ aff_combination_add_product()

static void aff_combination_add_product ( aff_tree * c,
const widest_int & coef,
tree val,
aff_tree * r )
static

◆ aff_combination_const()

◆ aff_combination_constant_multiple_p()

bool aff_combination_constant_multiple_p ( aff_tree * val,
aff_tree * div,
poly_widest_int * mult )

◆ aff_combination_convert()

◆ aff_combination_elt()

void aff_combination_elt ( aff_tree * comb,
tree type,
tree elt )

◆ aff_combination_expand()

◆ aff_combination_find_elt()

static class aff_comb_elt * aff_combination_find_elt ( aff_tree * comb,
tree val,
unsigned * idx )
static
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 aff_tree::elts, i, aff_tree::n, NULL, operand_equal_p(), and aff_comb_elt::val.

Referenced by aff_combination_constant_multiple_p().

◆ aff_combination_mult()

◆ aff_combination_remove_elt()

void aff_combination_remove_elt ( aff_tree * comb,
unsigned m )

◆ aff_combination_scale()

◆ aff_combination_to_tree()

◆ aff_combination_zero()

static void aff_combination_zero ( aff_tree * comb,
tree type )
static

◆ debug_aff()

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

References print_aff(), and aff_comb_elt::val.

◆ expr_to_aff_combination()

◆ free_affine_expand_cache()

void free_affine_expand_cache ( hash_map< tree, name_expansion * > ** cache)
Frees memory allocated for the CACHE used by
tree_to_aff_combination_expand.   

References cache, free_name_expansion(), and NULL.

Referenced by simplify_peeled_chrec(), tree_ssa_iv_optimize_finalize(), tree_ssa_lim_finalize(), and pcom_worker::~pcom_worker().

◆ free_name_expansion()

bool free_name_expansion ( tree const & ,
name_expansion ** value,
void *  )
Frees memory occupied by struct name_expansion in *VALUE.  Callback for
hash_map::traverse.   

References free().

Referenced by free_affine_expand_cache().

◆ get_inner_reference_aff()

tree get_inner_reference_aff ( tree ref,
aff_tree * addr,
poly_widest_int * size )
Computes address of the reference REF in ADDR.  The size of the accessed
location is stored to SIZE.  Returns the ultimate containing object to
which REF refers.   

References aff_combination_add(), aff_combination_const(), bits_to_bytes_round_down, bits_to_bytes_round_up, build_fold_addr_expr, get_inner_reference(), sizetype, and tree_to_aff_combination().

Referenced by dr_may_alias_p(), and mem_refs_may_alias_p().

◆ print_aff()

static void print_aff ( FILE * file,
aff_tree * val )
static
Prints the affine VAL to the FILE.  

References i, POINTER_TYPE_P, print_dec(), print_generic_expr(), SIGNED, TDF_MEMSYMS, TDF_VOPS, TYPE_SIGN, and aff_comb_elt::val.

Referenced by debug_aff().

◆ tree_to_aff_combination()

◆ tree_to_aff_combination_expand()

void tree_to_aff_combination_expand ( tree expr,
tree type,
aff_tree * comb,
hash_map< tree, name_expansion * > ** 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(), cache, and tree_to_aff_combination().

Referenced by pcom_worker::aff_combination_dr_offset(), pcom_worker::determine_offset(), difference_cannot_overflow_p(), get_alternative_base(), simplify_peeled_chrec(), and pcom_worker::valid_initializer_p().

◆ unshare_aff_combination()

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

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

Referenced by get_computation_at(), rewrite_use_address(), and rewrite_use_nonlinear_expr().

◆ wide_int_constant_multiple_p()

static bool wide_int_constant_multiple_p ( const poly_widest_int & val,
const poly_widest_int & div,
bool * mult_set,
poly_widest_int * mult )
static
If VAL == CST * DIV for any constant CST, returns true.
and if *MULT_SET is true, additionally compares CST and MULT
and if they are different, returns false.  If true is returned, CST is
stored to MULT and MULT_SET is set to true unless VAL and DIV are both zero
in which case neither MULT nor MULT_SET are updated.   

References known_eq, and mult.

Referenced by aff_combination_constant_multiple_p().

◆ wide_int_ext_for_comb() [1/2]

static poly_widest_int wide_int_ext_for_comb ( const poly_widest_int & cst,
tree type )
static
Likewise for polynomial offsets.   

References wi::sext(), and TYPE_PRECISION.

◆ wide_int_ext_for_comb() [2/2]

static widest_int wide_int_ext_for_comb ( const widest_int & cst,
tree type )
static
Operations with affine combinations of trees.
   Copyright (C) 2005-2024 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 wi::sext(), and TYPE_PRECISION.

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