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_elt *	aff_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, ggc_alloc(), 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 ggc_alloc(), and known_le.

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

aff_combination_add()

void aff_combination_add	(	aff_tree *	comb1,
		aff_tree *	comb2 )

Adds COMB2 to COMB1.   

References aff_combination_add_cst(), aff_combination_add_elt(), ggc_alloc(), and i.

Referenced by pcom_worker::aff_combination_dr_offset(), aff_combination_expand(), cand_value_at(), pcom_worker::determine_offset(), difference_cannot_overflow_p(), dr_may_alias_p(), expr_to_aff_combination(), generate_memcpy_builtin(), get_computation_aff(), get_computation_aff_1(), get_inner_reference_aff(), iv_elimination_compare_lt(), mem_refs_may_alias_p(), simplify_peeled_chrec(), tree_to_aff_combination(), and pcom_worker::valid_initializer_p().

aff_combination_add_cst()

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

static

Adds CST to C.   

References ggc_alloc(), aff_tree::offset, aff_tree::type, and wide_int_ext_for_comb().

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

aff_combination_add_elt()

void aff_combination_add_elt	(	aff_tree *	comb,
		tree	elt,
		const widest_int &	scale_in )

Adds ELT * SCALE to COMB.   

References fold_build2, fold_convert, gcc_assert, ggc_alloc(), i, MAX_AFF_ELTS, NULL_TREE, operand_equal_p(), POINTER_TYPE_P, sizetype, type(), wide_int_ext_for_comb(), and wide_int_to_tree().

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

aff_combination_add_product()

static void aff_combination_add_product ( aff_tree * c, const widest_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, poly_int< N, C >::coeffs, aff_tree::elts, fold_build2, fold_convert, ggc_alloc(), i, poly_int< N, C >::is_constant(), aff_tree::n, offset, aff_tree::offset, r, aff_tree::rest, TREE_TYPE, type(), aff_comb_elt::val, and wide_int_to_tree().

Referenced by aff_combination_mult().

aff_combination_const()

void aff_combination_const	(	aff_tree *	comb,
		tree	type,
		const poly_widest_int &	cst )

Sets COMB to CST.   

References aff_combination_zero(), ggc_alloc(), and wide_int_ext_for_comb().

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

aff_combination_constant_multiple_p()

bool aff_combination_constant_multiple_p	(	aff_tree *	val,
		aff_tree *	div,
		poly_widest_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, aff_tree::elts, gcc_assert, ggc_alloc(), i, known_eq, mult, aff_tree::n, NULL, aff_tree::offset, aff_tree::rest, aff_comb_elt::val, and wide_int_constant_multiple_p().

Referenced by pcom_worker::determine_offset(), and pcom_worker::valid_initializer_p().

aff_combination_convert()

void aff_combination_convert	(	aff_tree *	comb,
		tree	type )

Converts affine combination COMB to TYPE.   

References aff_combination_to_tree(), fold_convert, ggc_alloc(), i, MAX_AFF_ELTS, NULL_TREE, POINTER_TYPE_P, tree_to_aff_combination(), type(), TYPE_PRECISION, and wide_int_ext_for_comb().

Referenced by aff_combination_expand(), cand_value_at(), get_computation_aff_1(), get_computation_cost(), and tree_to_aff_combination().

aff_combination_elt()

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

Sets COMB to single element ELT.   

References aff_combination_zero(), and ggc_alloc().

Referenced by aff_combination_expand(), and tree_to_aff_combination().

aff_combination_expand()

void aff_combination_expand	(	aff_tree *	comb,
		hash_map< tree, name_expansion * > **	cache )

Expands SSA names in COMB recursively.  CACHE is used to cache the
results.   

References aff_combination_add(), aff_combination_add_elt(), aff_combination_convert(), aff_combination_elt(), aff_combination_expand(), aff_combination_scale(), aff_combination_zero(), cache, CASE_CONVERT, CONVERT_EXPR_P, exp(), expr_to_aff_combination(), fold_convert, gcc_assert, get_gimple_rhs_class(), ggc_alloc(), gimple_assign_lhs(), gimple_assign_rhs1(), gimple_assign_rhs2(), gimple_assign_rhs_code(), GIMPLE_SINGLE_RHS, i, IS_EXPR_CODE_CLASS, is_gimple_assign(), is_gimple_min_invariant(), NULL, hash_map< KeyId, Value, Traits >::put(), SSA_NAME_DEF_STMT, tcc_reference, TREE_CODE, TREE_CODE_CLASS, TREE_OPERAND, tree_to_aff_combination(), TREE_TYPE, type(), aff_tree::type, TYPE_PRECISION, and useless_type_conversion_p().

Referenced by aff_combination_expand(), mem_refs_may_alias_p(), and tree_to_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 ggc_alloc(), i, NULL, operand_equal_p(), and aff_comb_elt::val.

Referenced by aff_combination_constant_multiple_p().

aff_combination_mult()

void aff_combination_mult	(	aff_tree *	c1,
		aff_tree *	c2,
		aff_tree *	r )

Multiplies C1 by C2, storing the result to R   

References aff_combination_add_product(), aff_combination_zero(), gcc_assert, ggc_alloc(), i, NULL, offset, r, TYPE_PRECISION, and wide_int_to_tree().

Referenced by cand_value_at().

aff_combination_remove_elt()

void aff_combination_remove_elt	(	aff_tree *	comb,
		unsigned	m )

Remove M-th element from COMB.   

References ggc_alloc(), and NULL_TREE.

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

aff_combination_scale()

void aff_combination_scale	(	aff_tree *	comb,
		const widest_int &	scale_in )

Scales COMB by SCALE.   

References aff_combination_zero(), fold_build2, ggc_alloc(), i, MAX_AFF_ELTS, NULL_TREE, POINTER_TYPE_P, sizetype, wide_int_ext_for_comb(), and wide_int_to_tree().

Referenced by aff_combination_expand(), pcom_worker::determine_offset(), difference_cannot_overflow_p(), dr_may_alias_p(), expr_to_aff_combination(), generate_memcpy_builtin(), get_computation_aff_1(), iv_elimination_compare_lt(), mem_refs_may_alias_p(), simplify_peeled_chrec(), and pcom_worker::valid_initializer_p().

aff_combination_to_tree()

tree aff_combination_to_tree

(

aff_tree *

comb

)

Makes tree from the affine combination COMB.   

References add_elt_to_tree(), fold_build_pointer_plus, fold_convert, gcc_assert, ggc_alloc(), i, known_lt, MAX_AFF_ELTS, NULL_TREE, POINTER_TYPE_P, sizetype, TREE_TYPE, and wide_int_to_tree().

Referenced by aff_combination_convert(), alloc_iv(), get_address_cost(), get_alternative_base(), get_computation_at(), get_computation_cost(), may_eliminate_iv(), and rewrite_use_nonlinear_expr().

aff_combination_zero()

static void aff_combination_zero ( aff_tree * comb, tree type )

static

Initializes affine combination COMB so that its value is zero in TYPE.   

References ggc_alloc(), i, MAX_AFF_ELTS, NULL_TREE, and type().

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

debug_aff()

DEBUG_FUNCTION void debug_aff

(

aff_tree *

val

)

Prints the affine VAL to the standard error, used for debugging.   

References ggc_alloc(), print_aff(), and aff_comb_elt::val.

expr_to_aff_combination()

static bool expr_to_aff_combination ( aff_tree * comb, tree_code code, tree type, tree op0, tree op1 = NULL_TREE )

static

Tries to handle OP0 CODE OP1 as affine combination of parts.  Returns
true when that was successful and returns the combination in COMB.   

References wi::add(), aff_combination_add(), aff_combination_add_cst(), aff_combination_scale(), CASE_CONVERT, cfun, expr_to_aff_combination(), fold_convert, get_range_query(), ggc_alloc(), irange::lower_bound(), wi::mul(), operand_equal_p(), wi::OVF_NONE, sizetype, wi::sub(), wi::to_wide(), wi::to_widest(), TREE_CODE, tree_nop_conversion_p(), TREE_OPERAND, tree_to_aff_combination(), TREE_TYPE, type(), TYPE_OVERFLOW_UNDEFINED, TYPE_OVERFLOW_WRAPS, TYPE_PRECISION, TYPE_UNSIGNED, vrange::undefined_p(), UNSIGNED, irange::upper_bound(), and vrange::varying_p().

Referenced by aff_combination_expand(), expr_to_aff_combination(), and tree_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(), ggc_alloc(), 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 ggc_alloc(), 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()

void tree_to_aff_combination	(	tree	expr,
		tree	type,
		aff_tree *	comb )

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_convert(), aff_combination_elt(), build_fold_addr_expr, CASE_CONVERT, expr_to_aff_combination(), get_inner_reference(), ggc_alloc(), poly_int_tree_p(), sizetype, STRIP_NOPS, wi::to_poly_widest(), TREE_CODE, TREE_OPERAND, tree_to_aff_combination(), and TREE_TYPE.

Referenced by aff_combination_convert(), aff_combination_expand(), alloc_iv(), cand_value_at(), expr_to_aff_combination(), generate_memcpy_builtin(), get_computation_aff_1(), get_inner_reference_aff(), iv_elimination_compare_lt(), tree_to_aff_combination(), and tree_to_aff_combination_expand().

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, ggc_alloc(), 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 ggc_alloc(), i, and unshare_expr().

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 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 ggc_alloc(), 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 ggc_alloc(), 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 ggc_alloc(), 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().