#include "config.h"
#include "params.h"

Include dependency graph for omega.h:

This graph shows which files directly or indirectly include this file:

Data Structures
struct	eqn_d
struct	omega_pb_d

Macros
#define	OMEGA_MAX_VARS PARAM_VALUE (PARAM_OMEGA_MAX_VARS)
#define	OMEGA_MAX_GEQS PARAM_VALUE (PARAM_OMEGA_MAX_GEQS)
#define	OMEGA_MAX_EQS PARAM_VALUE (PARAM_OMEGA_MAX_EQS)
#define	pos_infinity (0x7ffffff)
#define	neg_infinity (-0x7ffffff)

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)

Macro Definition Documentation

#define neg_infinity (-0x7ffffff)

#define OMEGA_MAX_EQS PARAM_VALUE (PARAM_OMEGA_MAX_EQS)

Referenced by omega_add_zero_geq().

#define OMEGA_MAX_GEQS PARAM_VALUE (PARAM_OMEGA_MAX_GEQS)

Referenced by omega_add_zero_geq().

#define OMEGA_MAX_VARS PARAM_VALUE (PARAM_OMEGA_MAX_VARS)

Source code for an implementation of the Omega test, an integer programming algorithm for dependence analysis, by William Pugh, appeared in Supercomputing '91 and CACM Aug 92.

This code has no license restrictions, and is considered public domain.

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

Referenced by omega_add_zero_geq(), and omega_copy_eqn().

#define pos_infinity (0x7ffffff)

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	Value returned when the solver is unable to determine an answer.
omega_simplify	Value used for asking the solver to simplify the system.

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 omega_pb_d::forwarding_address, omega_pb_d::num_vars, omega_pb_d::var, and omega_pb_d::variables_initialized.

Referenced by subscript_dependence_tester_1().

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 omega_pb_d::eqs, omega_pb_d::forwarding_address, omega_pb_d::geqs, omega_free_eqns(), OMEGA_MAX_EQS, OMEGA_MAX_GEQS, OMEGA_MAX_VARS, omega_pb_d::subs, and omega_pb_d::var.

Referenced by subscript_dependence_tester_1().

static eqn omega_alloc_eqns ( )

inlinestatic

Allocate N equations with S variables.

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.

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, and omega_pb_d::eqs.

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, omega_init_eqn_zero(), and OMEGA_MAX_VARS.

static void omega_copy_problem ( )

inlinestatic

Copy omega problems: P1 = P2.

Referenced by subscript_dependence_tester_1().

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.

Referenced by omega_add_zero_geq().

static void omega_free_problem ( )

inlinestatic

Free problem PB.

Referenced by omega_setup_subscript().

static void omega_init_eqn_zero ( )

inlinestatic

Initialize E = 0. Equation E contains S variables.

Referenced by normalize_omega_problem(), omega_copy_eqn(), and verify_omega_pb().

void omega_initialize ( void )

Initialization of the Omega solver.

static void omega_initialize_variables ( )

inlinestatic

Initialize variables for problem PB.

Referenced by omega_count_red_equations().

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 eqn_d::color, eqn_d::key, and eqn_d::touched.

Referenced by omega_count_red_equations().

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

static void omega_print_geq ( )

inlinestatic

Print to FILE inequality E from PB.

Referenced by coalesce(), normalize_omega_problem(), omega_count_red_equations(), and omega_eliminate_red().

static void omega_print_geq_extra ( )

inlinestatic

Print to FILE inequality E from PB.

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.

static bool omega_safe_var_p ( )

inlinestatic

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

The constant of an equation is not a variable.

References omega_print_eqn().

Referenced by bswap(), and omega_solve_eq().

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

static bool single_var_geq ( )

inlinestatic

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

Referenced by adding_equality_constraint().

Variable Documentation

void(* omega_when_reduced)(omega_pb)

Data Structures

Macros

Typedefs

Enumerations

Functions

Variables

Macro Definition Documentation

Typedef Documentation

Enumeration Type Documentation

Function Documentation

Variable Documentation