#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tree.h"
#include "tree-pretty-print.h"
#include "pointer-set.h"
#include "tree-affine.h"
#include "gimple.h"
#include "flags.h"
#include "dumpfile.h"

Include dependency graph for tree-affine.c:

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.

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 ( )

Adds COMB2 to COMB1.

References aff_combination_to_tree(), fold_convert, tree_to_aff_combination(), affine_tree_combination::type, and TYPE_PRECISION.

Referenced by conflict_fn_no_dependence(), merge_comps(), and tree_to_aff_combination().

static void aff_combination_add_cst ( )

static

Adds CST to C.

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

Referenced by 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_one, affine_tree_combination::elts, gcc_assert, double_int::is_zero(), MAX_AFF_ELTS, affine_tree_combination::n, NULL_TREE, affine_tree_combination::rest, and aff_comb_elt::val.

Referenced by aff_combination_add_cst(), aff_combination_add_product(), aff_combination_remove_elt(), 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_elt(), fold_build2, fold_convert, affine_tree_combination::rest, and TREE_TYPE.

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
	)

Returns true if VAL = X * DIV for some constant X. If this is the case, X is stored to MULT.

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

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 results.

     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
         undefined.

         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 ( )

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.

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_remove_elt ( )

Remove M-th element from COMB.

References aff_combination_add_elt(), aff_comb_elt::coef, affine_tree_combination::elts, fold_build2, fold_convert, affine_tree_combination::n, affine_tree_combination::rest, TREE_TYPE, type(), and aff_comb_elt::val.

Referenced by move_pointer_to_base().

void aff_combination_scale ( )

Scales COMB by SCALE.

A coefficient may become zero due to overflow. Remove the zero elements.

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 unsigned.

Referenced by aff_combination_add().

static void aff_combination_zero ( )

static

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
	)

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 aff_combination_find_elt(), aff_comb_elt::coef, double_int_zero, affine_tree_combination::elts, gcc_assert, double_int::is_zero(), affine_tree_combination::n, NULL, affine_tree_combination::offset, affine_tree_combination::rest, and aff_comb_elt::val.

double_int double_int_ext_for_comb ( )

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 tree_to_aff_combination_expand.

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 double_int_zero, and 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.

ADDR = &BASE + TOFF + BITPOS / BITS_PER_UNIT.

References double_int_minus_one, and double_int::is_negative().

Referenced by conflict_fn_no_dependence().

static void print_aff ( )

static

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(), BITS_PER_UNIT, build2, build_fold_addr_expr, build_int_cst(), double_int_minus_one, double_int_one, double_int::from_uhwi(), get_inner_reference(), integer_zerop(), sizetype, TREE_CODE, TREE_OPERAND, tree_to_double_int(), and TREE_TYPE.

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 like

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, double_int_one, affine_tree_combination::elts, affine_tree_combination::n, NULL_TREE, affine_tree_combination::rest, and aff_comb_elt::val.

Data Structures

Functions

Function Documentation