omega.h File Reference

Go to the source code of this file.

Data Structures
struct	eqn_d
struct	omega_pb_d

Typedefs
typedef struct eqn_d *	eqn
typedef struct omega_pb_d *	omega_pb

Enumerations
enum	omega_result { omega_false = 0, omega_true = 1, omega_unknown = 2, omega_simplify = 3 }
enum	omega_eqn_color { omega_black = 0, omega_red = 1 }

Functions
void	omega_initialize (void)
omega_pb	omega_alloc_problem (int, int)
enum omega_result	omega_solve_problem (omega_pb, enum omega_result)
enum omega_result	omega_simplify_problem (omega_pb)
enum omega_result	omega_simplify_approximate (omega_pb)
enum omega_result	omega_constrain_variable_sign (omega_pb, enum omega_eqn_color, int, int)
void	debug (omega_pb_d &ref)
void	debug (omega_pb_d *ptr)
void	debug_omega_problem (omega_pb)
void	omega_print_problem (FILE *, omega_pb)
void	omega_print_red_equations (FILE *, omega_pb)
int	omega_count_red_equations (omega_pb)
void	omega_pretty_print_problem (FILE *, omega_pb)
void	omega_unprotect_variable (omega_pb, int var)
void	omega_negate_geq (omega_pb, int)
void	omega_convert_eq_to_geqs (omega_pb, int eq)
void	omega_print_eqn (FILE *, omega_pb, eqn, bool, int)
bool	omega_problem_has_red_equations (omega_pb)
enum omega_result	omega_eliminate_redundant (omega_pb, bool)
void	omega_eliminate_red (omega_pb, bool)
void	omega_constrain_variable_value (omega_pb, enum omega_eqn_color, int, int)
bool	omega_query_variable (omega_pb, int, int *, int *)
int	omega_query_variable_signs (omega_pb, int, int, int, int, int, int, bool *, int *)
bool	omega_query_variable_bounds (omega_pb, int, int *, int *)
void	omega_no_procedure (omega_pb)
static bool	omega_wildcard_p ()
static bool	omega_safe_var_p ()
static void	omega_print_eq ()
static void	omega_print_geq ()
static void	omega_print_geq_extra ()
static void	omega_copy_eqn ()
static void	omega_init_eqn_zero ()
static eqn	omega_alloc_eqns ()
static void	omega_free_eqns ()
static bool	single_var_geq ()
static int	omega_add_zero_eq ()
static int	omega_add_zero_geq ()
static void	omega_initialize_variables ()
static void	omega_free_problem ()
static void	omega_copy_problem ()

Variables
void(*	omega_when_reduced )(omega_pb)

---

Typedef Documentation

typedef struct eqn_d * eqn

Structure for equations.   

typedef struct omega_pb_d * omega_pb

---

Enumeration Type Documentation

enum omega_eqn_color

Values used for labeling equations.  Private (not used outside the
   solver).   

Enumerator:

omega_black
omega_red

enum omega_result

Results of the Omega solver.   

Enumerator:

omega_false
omega_true
omega_unknown
omega_simplify

---

Function Documentation

void debug

(

omega_pb_d &

ref

)

void debug

(

omega_pb_d *

ptr

)

void debug_omega_problem

(

omega_pb

)

static int omega_add_zero_eq ( )

inlinestatic

Allocate a new equality with all coefficients 0, and tagged with
   COLOR.  Return the index of this equality in problem PB.   

References eqn_d::color, color(), omega_pb_d::eqs, omega_pb_d::num_eqs, omega_pb_d::num_vars, and omega_init_eqn_zero().

Referenced by omega_extract_distance_vectors(), and omega_setup_subscript().

static int omega_add_zero_geq ( )

inlinestatic

Allocate a new inequality with all coefficients 0, and tagged with
   COLOR.  Return the index of this inequality in problem PB.   

References eqn_d::color, color(), omega_pb_d::geqs, omega_pb_d::num_geqs, omega_pb_d::num_vars, omega_init_eqn_zero(), and eqn_d::touched.

Referenced by init_omega_for_ddr_1(), and omega_extract_distance_vectors().

static eqn omega_alloc_eqns ( )

inlinestatic

Allocate N equations with S variables.   

References eqn_d::coef, and omega_init_eqn_zero().

Referenced by omega_alloc_problem(), omega_do_elimination(), omega_do_mod(), omega_initialize(), omega_solve_eq(), and omega_solve_geq().

omega_pb omega_alloc_problem	(	int	,
		int
	)

enum omega_result omega_constrain_variable_sign	(	omega_pb	pb,
		enum omega_eqn_color	color,
		int	var,
		int	sign
	)

Unprotects VAR and simplifies PB.   

References eqn_d::coef, eqn_d::color, color(), omega_pb_d::eqs, omega_pb_d::forwarding_address, omega_pb_d::geqs, omega_pb_d::num_eqs, omega_pb_d::num_geqs, omega_pb_d::num_vars, omega_copy_eqn(), omega_init_eqn_zero(), omega_simplify_problem(), omega_unprotect_variable(), omega_pb_d::subs, and eqn_d::touched.

void omega_constrain_variable_value	(	omega_pb	pb,
		enum omega_eqn_color	color,
		int	var,
		int	value
	)

Add an equation "VAR = VALUE" with COLOR to PB.   

References eqn_d::coef, eqn_d::color, color(), omega_pb_d::eqs, omega_pb_d::forwarding_address, omega_pb_d::num_eqs, omega_pb_d::num_vars, omega_copy_eqn(), omega_init_eqn_zero(), and omega_pb_d::subs.

void omega_convert_eq_to_geqs	(	omega_pb	,
		int	eq
	)

static void omega_copy_eqn ( )

inlinestatic

E1 = E2, make a copy of E2 into E1.  Equations contain S variables.   

References eqn_d::coef, eqn_d::color, eqn_d::key, memcpy(), and eqn_d::touched.

Referenced by coalesce(), normalize_omega_problem(), omega_constrain_variable_sign(), omega_constrain_variable_value(), omega_convert_eq_to_geqs(), omega_copy_problem(), omega_delete_geq(), omega_delete_geq_extra(), omega_do_elimination(), omega_do_mod(), omega_eliminate_redundant(), omega_solve_eq(), omega_solve_geq(), omega_unprotect_variable(), parallel_splinter(), and resurrect_subs().

static void omega_copy_problem ( )

inlinestatic

Copy omega problems: P1 = P2.   

References omega_pb_d::eqs, omega_pb_d::forwarding_address, omega_pb_d::geqs, omega_pb_d::hash_version, omega_pb_d::num_eqs, omega_pb_d::num_geqs, omega_pb_d::num_subs, omega_pb_d::num_vars, omega_copy_eqn(), omega_pb_d::safe_vars, omega_pb_d::subs, omega_pb_d::var, omega_pb_d::variables_freed, and omega_pb_d::variables_initialized.

Referenced by omega_eliminate_red(), omega_eliminate_redundant(), omega_extract_distance_vectors(), omega_solve_geq(), parallel_splinter(), and verify_omega_pb().

int omega_count_red_equations

(

omega_pb

)

void omega_eliminate_red	(	omega_pb	,
		bool
	)

enum omega_result omega_eliminate_redundant	(	omega_pb	,
		bool
	)

static void omega_free_eqns ( )

inlinestatic

Free N equations from array EQ.   

References free().

Referenced by omega_do_elimination(), omega_do_mod(), omega_free_problem(), omega_solve_eq(), and omega_solve_geq().

static void omega_free_problem ( )

inlinestatic

Free problem PB.   

References omega_pb_d::eqs, omega_pb_d::forwarding_address, free(), omega_pb_d::geqs, omega_free_eqns(), omega_pb_d::subs, and omega_pb_d::var.

Referenced by init_omega_for_ddr(), and omega_extract_distance_vectors().

static void omega_init_eqn_zero ( )

inlinestatic

Initialize E = 0.  Equation E contains S variables.   

References eqn_d::coef, eqn_d::color, eqn_d::key, memset(), omega_black, and eqn_d::touched.

Referenced by adding_equality_constraint(), normalize_omega_problem(), omega_add_zero_eq(), omega_add_zero_geq(), omega_alloc_eqns(), omega_constrain_variable_sign(), omega_constrain_variable_value(), omega_solve_eq(), and omega_solve_geq().

void omega_initialize

(

void

)

Initialization of the Omega solver.   

References next_key, omega_alloc_eqns(), and wild_name.

Referenced by omega_alloc_problem().

static void omega_initialize_variables ( )

inlinestatic

Initialize variables for problem PB.   

References omega_pb_d::forwarding_address, omega_pb_d::num_vars, omega_pb_d::var, and omega_pb_d::variables_initialized.

Referenced by omega_pretty_print_problem(), omega_print_problem(), omega_print_red_equations(), and omega_simplify_problem().

void omega_negate_geq	(	omega_pb	,
		int
	)

void omega_no_procedure

(

omega_pb

)

void omega_pretty_print_problem	(	FILE *	,
		omega_pb
	)

static void omega_print_eq ( )

inlinestatic

Print to FILE equality E from PB.   

References omega_print_eqn().

Referenced by cleanout_wildcards(), omega_pretty_print_problem(), omega_print_problem(), omega_print_red_equations(), omega_solve_eq(), omega_substitute(), omega_substitute_red(), and resurrect_subs().

void omega_print_eqn	(	FILE *	,
		omega_pb	,
		eqn	,
		bool	,
		int
	)

static void omega_print_geq ( )

inlinestatic

Print to FILE inequality E from PB.   

References omega_print_eqn().

Referenced by normalize_omega_problem(), omega_delete_geq(), omega_eliminate_red(), omega_eliminate_redundant(), omega_pretty_print_problem(), omega_print_problem(), omega_print_red_equations(), omega_solve_geq(), omega_substitute(), omega_substitute_red(), and smooth_weird_equations().

static void omega_print_geq_extra ( )

inlinestatic

Print to FILE inequality E from PB.   

References omega_print_eqn().

Referenced by omega_delete_geq_extra(), and omega_solve_geq().

void omega_print_problem	(	FILE *	,
		omega_pb
	)

void omega_print_red_equations	(	FILE *	,
		omega_pb
	)

bool omega_problem_has_red_equations

(

omega_pb

)

bool omega_query_variable	(	omega_pb	,
		int	,
		int *	,
		int *
	)

bool omega_query_variable_bounds	(	omega_pb	,
		int	,
		int *	,
		int *
	)

int omega_query_variable_signs	(	omega_pb	pb,
		int	i,
		int	dd_lt,
		int	dd_eq,
		int	dd_gt,
		int	lower_bound,
		int	upper_bound,
		bool *	dist_known,
		int *	dist
	)

For problem PB, return an integer that represents the classic data
   dependence direction in function of the DD_LT, DD_EQ and DD_GT bit
   masks that are added to the result.  When DIST_KNOWN is true, DIST
   is set to the classic data dependence distance.  LOWER_BOUND and
   UPPER_BOUND are bounds on the value of variable I, for example, it
   is possible to narrow the iteration domain with safe approximations
   of loop counts, and thus discard some data dependences that cannot
   occur.   

References omega_query_variable(), and query_coupled_variable().

static bool omega_safe_var_p ( )

inlinestatic

Return true when variable I in problem PB is a safe variable.   

Referenced by chain_unprotect(), cleanout_wildcards(), omega_delete_variable(), omega_do_mod(), omega_problem_reduced(), omega_simplify_problem(), omega_solve_eq(), omega_solve_geq(), omega_substitute(), omega_substitute_red(), and resurrect_subs().

enum omega_result omega_simplify_approximate

(

omega_pb

)

enum omega_result omega_simplify_problem

(

omega_pb

)

enum omega_result omega_solve_problem	(	omega_pb	,
		enum	omega_result
	)

void omega_unprotect_variable	(	omega_pb	,
		int	var
	)

static bool omega_wildcard_p ( )

inlinestatic

Return true when variable I in problem PB is a wildcard.   

References omega_pb_d::var.

Referenced by chain_unprotect(), omega_do_mod(), omega_solve_eq(), omega_substitute(), omega_substitute_red(), and resurrect_subs().

static bool single_var_geq ( )

inlinestatic

Returns true when E is an inequality with a single variable.   

References eqn_d::key.

Referenced by normalize_omega_problem(), omega_solve_geq(), and resurrect_subs().

---

Variable Documentation

void(* omega_when_reduced)(omega_pb)

Referenced by omega_problem_reduced().