osprey/kg++fe/gnu/dependence.c File Reference

#include "config.h"
#include "system.h"
#include "rtl.h"
#include "expr.h"
#include "tree.h"
#include "c-common.h"
#include "flags.h"
#include "varray.h"

Include dependency graph for dependence.c:

Go to the source code of this file.

Data Types
type	def_use
type	loop
type	induction
type	dependence
type	subscript
Defines
#define	MAX_SUBSCRIPTS   13
#define	INDEX_LIMIT_CHECK(NODE)
#define	abs(N)   ((N) < 0 ? -(N) : (N))
#define	MEM_DEPENDENCY(RTX)   XCWINT (RTX, 2, MEM)
Enumerations
enum	dependence_type {   dt_flow, dt_anti, dt_output, dt_none,   dt_flow, dt_anti, dt_output, dt_none }
enum	direction_type {   lt, le, eq, gt,   ge, star, independent, undef,   lt, le, eq, gt,   ge, star, independent, undef }
enum	def_use_type {   def, use, init_def_use, def,   use, init_def_use }
enum	du_status_type { seen, unseen, seen, unseen }
enum	loop_status_type { normal, unnormal, normal, unnormal }
enum	complexity_type {   ziv, strong_siv, weak_siv, weak_zero_siv,   weak_crossing_siv, miv, ziv, strong_siv,   weak_siv, weak_zero_siv, weak_crossing_siv, miv }
Functions/Subroutines
void init_dependence_analysis	PARAMS ((tree))
static void build_def_use	PARAMS ((tree, enum def_use_type))
static loop *add_loop	PARAMS ((tree, tree, int))
static int find_induction_variable	PARAMS ((tree, tree, tree, loop *))
static int get_low_bound	PARAMS ((tree, const char *))
static void link_loops	PARAMS ((void))
static void check_node_dependence	PARAMS ((def_use *))
static int get_coefficients	PARAMS ((def_use *, subscript[]))
static int get_one_coefficient	PARAMS ((tree, subscript *, def_use *, enum tree_code *))
static void normalize_coefficients	PARAMS ((subscript[], loop *, int))
static void classify_dependence	PARAMS ((subscript[], subscript[], enum complexity_type[], int *, int))
static void ziv_test	PARAMS ((subscript[], subscript[], enum direction_type[][MAX_SUBSCRIPTS], int[][MAX_SUBSCRIPTS], loop *, int))
static int check_subscript_induction	PARAMS ((subscript *, subscript *, loop *))
static void gcd_test	PARAMS ((subscript[], subscript[], enumdirection_type[][MAX_SUBSCRIPTS], int[][MAX_SUBSCRIPTS], loop *, int))
static int find_gcd	PARAMS ((int, int))
static void merge_dependencies	PARAMS ((enum direction_type[][MAX_SUBSCRIPTS], int[][MAX_SUBSCRIPTS], int, int))
int have_dependence_p	PARAMS ((rtx, rtx, enum direction_type[], int[]))
void	init_dependence_analysis (tree exp)
static void	build_def_use (tree exp, enum def_use_type du_type)
static loop *	add_loop (tree loop_node, tree outer_loop, int nloop)
static int	find_induction_variable (tree init_node, tree cond_node, tree incr_node, loop *loop_def)
static int	get_low_bound (tree node, const char *variable)
static int	have_induction_variable (tree outer_loop, const char *ind_var)
static void	link_loops ()
static void	get_node_dependence ()
static void	check_node_dependence (def_use *du)
static int	get_coefficients (def_use *du, coefficients)
static int	get_one_coefficient (tree node, subscript *coefficients, def_use *du, enum tree_code *type)
static void	normalize_coefficients (coefficients, loop *loop_ptr, int count)
static void	classify_dependence (icoefficients, ocoefficients, complexity, int *separability, int count)
static void	ziv_test (icoefficients, ocoefficients, direction, distance, loop *loop_ptr, int sub)
static void	siv_test (icoefficients, ocoefficients, direction, distance, loop *loop_ptr, int sub)
static int	check_subscript_induction (subscript *icoefficient, subscript *ocoefficient, loop *loop_ptr)
static void	gcd_test (icoefficients, ocoefficients, direction, distance, loop *loop_ptr, int sub)
static int	find_gcd (int x, int y)
static void	merge_dependencies (direction, distance, int loop_count, int subscript_count)
static void	dump_array_ref (tree node)
int	search_dependence (tree node)
void	remember_dest_for_dependence (tree node)
int	have_dependence_p (rtx dest_rtx, rtx src_rtx, direction, distance)
void	end_dependence_analysis ()
Variables
static tree	dest_to_remember
static varray_type	def_use_chain
static varray_type	dep_chain
static varray_type	loop_chain
static varray_type	induction_chain

---

Define Documentation

#define abs

(

N

)

((N) < 0 ? -(N) : (N))

Definition at line 1146 of file dependence.c.

#define INDEX_LIMIT_CHECK

(

NODE

)

Value:

(TREE_CODE_CLASS (TREE_CODE (NODE)) == '<') \
  && (TREE_CODE (TREE_OPERAND (NODE, 0)) == VAR_DECL \
      && (IDENTIFIER_POINTER (DECL_NAME (TREE_OPERAND (NODE, 0))) \
    == IDENTIFIER_POINTER (DECL_NAME (TREE_OPERAND (incr_node, 0))))) \
      ? 1 : 0

Referenced by find_induction_variable().

#define MAX_SUBSCRIPTS   13

Definition at line 36 of file dependence.c.

Referenced by check_node_dependence().

#define MEM_DEPENDENCY

(

RTX

)

XCWINT (RTX, 2, MEM)

Definition at line 1418 of file dependence.c.

Referenced by have_dependence_p().

---

Enumeration Type Documentation

enum complexity_type

Enumerator:

ziv
strong_siv
weak_siv
weak_zero_siv
weak_crossing_siv
miv
ziv
strong_siv
weak_siv
weak_zero_siv
weak_crossing_siv
miv

Definition at line 77 of file dependence.c.

enum def_use_type

Enumerator:

def
use
init_def_use
def
use
init_def_use

Definition at line 71 of file dependence.c.

enum dependence_type

Enumerator:

dt_flow
dt_anti
dt_output
dt_none
dt_flow
dt_anti
dt_output
dt_none

Definition at line 62 of file dependence.c.

enum direction_type

Enumerator:

lt
le
eq
gt
ge
star
independent
undef
lt
le
eq
gt
ge
star
independent
undef

Definition at line 66 of file dependence.c.

enum du_status_type

Enumerator:

seen
unseen
seen
unseen

Definition at line 73 of file dependence.c.

enum loop_status_type

Enumerator:

normal
unnormal
normal
unnormal

Definition at line 75 of file dependence.c.

---

Function Documentation

static loop* add_loop	(	tree	loop_node,
		tree	outer_loop,
		int	nloop
	)			[static]

Definition at line 414 of file dependence.c.

References loop::containing_loop, loop::depth, loop::ind, loop_chain, loop::next_nest, normal, loop::outer_loop, loop::status, VARRAY_PUSH_GENERIC_PTR, VARRAY_TOP, and xmalloc().

Referenced by build_def_use(), and loopify().

static void build_def_use	(	tree	exp,
		enum def_use_type	du_type
	)			[static]

Definition at line 261 of file dependence.c.

References add_loop(), def_use::containing_loop, current_loop, DECL_NAME, def_use_chain, def_use::dep, def_use::expression, find_induction_variable(), have_induction_variable(), i, IDENTIFIER_POINTER, init_def_use, def_use::next, node, null_string, def_use::outer_loop, loop::outer_loop, loop::status, def_use::status, strcmp(), TREE_CHAIN, TREE_CODE, TREE_CODE_CLASS, TREE_OPERAND, TREE_TYPE, TREE_VALUE, def_use::type, unnormal, unseen, def_use::variable, VARRAY_GENERIC_PTR, VARRAY_PUSH_GENERIC_PTR, and xmalloc().

Referenced by build_def_use(), init_dependence_analysis(), and regrename_optimize().

static void check_node_dependence

(

def_use *

du

)

[static]

Definition at line 648 of file dependence.c.

References classify_dependence(), def_use::dep, dep_chain, dependence::dependence, dependence::destination, dependence::direction, dependence::distance, subscript::distance, dt_anti, dt_flow, dt_none, dt_output, def_use::expression, gcd_test(), get_coefficients(), gt, i, independent, INT_MAX, loop_chain, lt, MAX_SUBSCRIPTS, merge_dependencies(), def_use::next, dependence::next, loop::next_nest, normalize_coefficients(), def_use::outer_loop, loop::outer_loop, seen, siv_test(), dependence::source, star, loop::status, def_use::status, strong_siv, def_use::type, undef, unnormal, VARRAY_GENERIC_PTR, VARRAY_PUSH_GENERIC_PTR, VARRAY_SIZE, VARRAY_TOP, weak_crossing_siv, weak_zero_siv, xmalloc(), ziv, and ziv_test().

Referenced by get_node_dependence().

static int check_subscript_induction	(	subscript *	icoefficient,
		subscript *	ocoefficient,
		loop *	loop_ptr
	)			[static]

Definition at line 1124 of file dependence.c.

References loop::ind, induction::next, induction::variable, and subscript::variable.

Referenced by gcd_test(), and siv_test().

static void classify_dependence	(	icoefficients	,
		ocoefficients	,
		complexity	,
		int *	separability,
		int	count
	)			[static]

Definition at line 980 of file dependence.c.

References idx, memset, miv, strong_siv, weak_crossing_siv, weak_siv, weak_zero_siv, and ziv.

Referenced by check_node_dependence().

static void dump_array_ref

(

tree

node

)

[static]

Definition at line 1266 of file dependence.c.

References DECL_NAME, IDENTIFIER_POINTER, printf(), TREE_CODE, TREE_INT_CST_LOW, and TREE_OPERAND.

Referenced by dump_array_ref().

void end_dependence_analysis

(

)

Definition at line 1464 of file dependence.c.

References dep_chain, and VARRAY_FREE.

static int find_gcd	(	int	x,
		int	y
	)			[static]

Definition at line 1186 of file dependence.c.

References abs, g, and r.

Referenced by gcd_test().

static int find_induction_variable	(	tree	init_node,
		tree	cond_node,
		tree	incr_node,
		loop *	loop_def
	)			[static]

Definition at line 436 of file dependence.c.

References DECL_NAME, get_low_bound(), induction::high_bound, IDENTIFIER_POINTER, induction::increment, loop::ind, INDEX_LIMIT_CHECK, induction_chain, INT_MAX, INT_MIN, induction::low_bound, induction::next, TREE_CODE, TREE_CODE_CLASS, TREE_INT_CST_LOW, TREE_OPERAND, TREE_VALUE, induction::variable, VARRAY_PUSH_GENERIC_PTR, VARRAY_TOP, and xmalloc().

Referenced by build_def_use().

static void gcd_test	(	icoefficients	,
		ocoefficients	,
		direction	,
		distance	,
		loop *	loop_ptr,
		int	sub
	)			[static]

Definition at line 1153 of file dependence.c.

References check_subscript_induction(), subscript::coefficient, loop::depth, find_gcd(), g, and independent.

Referenced by check_node_dependence().

static int get_coefficients	(	def_use *	du,
		coefficients
	)			[static]

Definition at line 810 of file dependence.c.

References get_one_coefficient(), i, idx, INT_MIN, offset, TREE_CODE, TREE_INT_CST_LOW, and TREE_OPERAND.

Referenced by check_node_dependence().

static int get_low_bound	(	tree	node,
		const char *	variable
	)			[static]

Definition at line 545 of file dependence.c.

References DECL_NAME, IDENTIFIER_POINTER, INT_MIN, TREE_CHAIN, TREE_CODE, TREE_INT_CST_LOW, and TREE_OPERAND.

Referenced by find_induction_variable().

static void get_node_dependence

(

)

[static]

Definition at line 630 of file dependence.c.

References check_node_dependence(), def_use_chain, def_use::status, unseen, VARRAY_GENERIC_PTR, and VARRAY_SIZE.

Referenced by init_dependence_analysis().

static int get_one_coefficient	(	tree	node,
		subscript *	coefficients,
		def_use *	du,
		enum tree_code *	type
	)			[static]

Definition at line 854 of file dependence.c.

References subscript::coefficient, DECL_NAME, have_induction_variable(), IDENTIFIER_POINTER, index(), INT_MIN, subscript::offset, def_use::outer_loop, subscript::position, TREE_CODE, TREE_INT_CST_LOW, TREE_OPERAND, and subscript::variable.

Referenced by get_coefficients(), and get_one_coefficient().

int have_dependence_p	(	rtx	dest_rtx,
		rtx	src_rtx,
		direction	,
		distance
	)

Definition at line 1425 of file dependence.c.

References dep_chain, dest, dependence::direction, dependence::distance, subscript::distance, GET_CODE, MEM, MEM_DEPENDENCY, dependence::next, PATTERN, SET_DEST, SET_SRC, src, and VARRAY_GENERIC_PTR.

static int have_induction_variable	(	tree	outer_loop,
		const char *	ind_var
	)			[static]

Definition at line 582 of file dependence.c.

References loop::ind, induction_chain, loop_chain, induction::next, loop::outer_loop, strcmp(), induction::variable, VARRAY_GENERIC_PTR, and VARRAY_SIZE.

Referenced by build_def_use(), and get_one_coefficient().

void init_dependence_analysis

(

tree

exp

)

Definition at line 227 of file dependence.c.

References build_def_use(), def_use_chain, dep_chain, free(), get_node_dependence(), induction_chain, init_def_use, link_loops(), loop_chain, VARRAY_FREE, VARRAY_GENERIC_PTR_INIT, VARRAY_POP, and VARRAY_TOP.

static void link_loops

(

)

[static]

Definition at line 608 of file dependence.c.

References loop::depth, loop_chain, loop::next_nest, loop::outer_loop, VARRAY_GENERIC_PTR, and VARRAY_SIZE.

Referenced by init_dependence_analysis().

static void merge_dependencies	(	direction	,
		distance	,
		int	loop_count,
		int	subscript_count
	)			[static]

Definition at line 1222 of file dependence.c.

References abs, subscript::distance, eq, ge, gt, i, independent, int, INT_MAX, le, lt, and star.

Referenced by check_node_dependence().

static void normalize_coefficients	(	coefficients	,
		loop *	loop_ptr,
		int	count
	)			[static]

Definition at line 943 of file dependence.c.

References induction::high_bound, i, loop::ind, INT_MIN, induction::low_bound, induction::next, loop::next_nest, and induction::variable.

Referenced by check_node_dependence().

int have_dependence_p PARAMS

(

(rtx, rtx, enum direction_type[], int[])

)

static void merge_dependencies PARAMS

(

(enum direction_type[][MAX_SUBSCRIPTS], int[][MAX_SUBSCRIPTS], int, int)

)

[static]

static int find_gcd PARAMS

(

(int, int)

)

[static]

static void gcd_test PARAMS

(

(subscript[], subscript[], enumdirection_type[][MAX_SUBSCRIPTS], int[][MAX_SUBSCRIPTS], loop *, int)

)

[static]

static int check_subscript_induction PARAMS

(

(subscript *, subscript *, loop *)

)

[static]

static void ziv_test PARAMS

(

(subscript[], subscript[], enum direction_type[][MAX_SUBSCRIPTS], int[][MAX_SUBSCRIPTS], loop *, int)

)

[static]

static void classify_dependence PARAMS

(

(subscript[], subscript[], enum complexity_type[], int *, int)

)

[static]

static void normalize_coefficients PARAMS

(

(subscript[], loop *, int)

)

[static]

static int get_one_coefficient PARAMS

(

(tree, subscript *, def_use *, enum tree_code *)

)

[static]

static int get_coefficients PARAMS

(

(def_use *, subscript[])

)

[static]

static void check_node_dependence PARAMS

(

(def_use *)

)

[static]

static void link_loops PARAMS

(

(void)

)

[static, read]

Definition at line 77 of file cplus-dem.c.

static int get_low_bound PARAMS

(

(tree, const char *)

)

[static]

static int find_induction_variable PARAMS

(

(tree, tree, tree, loop *)

)

[static]

static loop* add_loop PARAMS

(

(tree, tree, int)

)

[static]

static void build_def_use PARAMS

(

(tree, enum def_use_type)

)

[static]

void init_dependence_analysis PARAMS

(

(tree)

)

void remember_dest_for_dependence

(

tree

node

)

Definition at line 1405 of file dependence.c.

References dest_to_remember, TREE_CODE, and TREE_OPERAND.

int search_dependence

(

tree

node

)

Definition at line 1376 of file dependence.c.

References dep_chain, dest_to_remember, dependence::destination, dependence::source, TREE_CODE, TREE_OPERAND, and VARRAY_GENERIC_PTR.

static void siv_test	(	icoefficients	,
		ocoefficients	,
		direction	,
		distance	,
		loop *	loop_ptr,
		int	sub
	)			[static]

Definition at line 1072 of file dependence.c.

References abs, check_subscript_induction(), subscript::coefficient, loop::depth, subscript::distance, eq, gcd(), gt, independent, INT_MIN, and lt.

Referenced by check_node_dependence().

static void ziv_test	(	icoefficients	,
		ocoefficients	,
		direction	,
		distance	,
		loop *	loop_ptr,
		int	sub
	)			[static]

Definition at line 1054 of file dependence.c.

References loop::depth, independent, and offset.

Referenced by check_node_dependence().

---

Variable Documentation

varray_type def_use_chain [static]

Definition at line 175 of file dependence.c.

Referenced by build_def_use(), get_node_dependence(), and init_dependence_analysis().

varray_type dep_chain [static]

Definition at line 178 of file dependence.c.

Referenced by check_node_dependence(), end_dependence_analysis(), have_dependence_p(), init_dependence_analysis(), and search_dependence().

tree dest_to_remember [static]

Definition at line 172 of file dependence.c.

Referenced by remember_dest_for_dependence(), and search_dependence().

varray_type induction_chain [static]

Definition at line 184 of file dependence.c.

Referenced by find_induction_variable(), have_induction_variable(), and init_dependence_analysis().

varray_type loop_chain [static]

Definition at line 181 of file dependence.c.

Referenced by add_loop(), check_node_dependence(), have_induction_variable(), init_dependence_analysis(), and link_loops().