#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tree.h"
#include "diagnostic-core.h"
#include "dumpfile.h"
#include "omega.h"

Include dependency graph for omega.c:

Macros
#define	HASH_TABLE_SIZE PARAM_VALUE (PARAM_OMEGA_HASH_TABLE_SIZE)
#define	MAX_KEYS PARAM_VALUE (PARAM_OMEGA_MAX_KEYS)

Enumerations
enum	normalize_return_type { normalize_false, normalize_uncoupled, normalize_coupled }

Functions
static int	int_div ()
static int	int_mod ()
static bool	omega_eqn_is_red ()
static char *	omega_var_to_str ()
static char *	omega_variable_to_str ()
void	omega_no_procedure ()
static void	omega_print_term ()
void	omega_print_eqn ()
static void	omega_print_vars ()
DEBUG_FUNCTION void	debug ()
DEBUG_FUNCTION void	debug_omega_problem ()
void	omega_print_problem ()
int	omega_count_red_equations ()
void	omega_print_red_equations ()
void	omega_pretty_print_problem ()
static void	omega_name_wild_card ()
static int	omega_add_new_wild_card ()
static void	omega_delete_geq ()
static void	omega_delete_geq_extra ()
static void	omega_delete_variable ()
static int	setup_packing ()
static void	omega_substitute_red_1 (eqn eq, eqn sub, int var, int c, bool *found_black, int top_var)
static void	omega_substitute_red ()
static void	omega_substitute ()
static void	omega_do_mod ()
void	omega_negate_geq ()
static enum omega_result	verify_omega_pb ()
static void	adding_equality_constraint ()
static normalize_return_type	normalize_omega_problem ()
static void	divide_eqn_by_gcd ()
static void	cleanout_wildcards ()
static void	swap ()
static void	bswap ()
static void	omega_unprotect_1 ()
static void	resurrect_subs ()
static bool	implies ()
enum omega_result	omega_eliminate_redundant ()
static int	smooth_weird_equations ()
static void	coalesce ()
void	omega_eliminate_red ()
static void	chain_unprotect ()
static void	omega_problem_reduced ()
static void	omega_free_eliminations ()
static void	free_red_eliminations ()
void	omega_convert_eq_to_geqs ()
static void	omega_do_elimination ()
static enum omega_result	omega_problem_has_no_solution ()
static enum omega_result	omega_solve_eq ()
static enum omega_result	parallel_splinter (omega_pb pb, int e, int diff, enum omega_result desired_res)
static enum omega_result	omega_solve_geq ()
enum omega_result	omega_solve_problem ()
bool	omega_problem_has_red_equations ()
enum omega_result	omega_simplify_approximate ()
enum omega_result	omega_simplify_problem ()
void	omega_unprotect_variable ()
enum omega_result	omega_constrain_variable_sign (omega_pb pb, enum omega_eqn_color color, int var, int sign)
void	omega_constrain_variable_value (omega_pb pb, enum omega_eqn_color color, int var, int value)
bool	omega_query_variable ()
static void	query_coupled_variable (omega_pb pb, int i, int l, int u, bool *could_be_zero, int lower_bound, int upper_bound)
bool	omega_query_variable_bounds ()
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)
omega_pb	omega_alloc_problem ()
void	omega_initialize ()

Variables
static bool	omega_reduce_with_subs = true
static bool	omega_verify_simplification = false
static bool	omega_single_result = false
static int	return_single_result = 0
static eqn	hash_master
static int	next_key
static int	hash_version = 0
static bool	in_approximate_mode = false
static int	conservative = 0
static enum omega_result	omega_found_reduction
static bool	create_color = false
static int	may_be_red = 0
static int	please_no_equalities_in_simplified_problems = 0
static char	wild_name [200][40]
static omega_pb	no_problem = (omega_pb) 0
static omega_pb	original_problem = (omega_pb) 0
void(*	omega_when_reduced )(omega_pb) = omega_no_procedure
static int	next_wild_card = 0
static int *	packing
static int *	fast_lookup
static int *	fast_lookup_red
static int	omega_solve_depth = 0
static bool	omega_initialized = false

Macro Definition Documentation

#define HASH_TABLE_SIZE PARAM_VALUE (PARAM_OMEGA_HASH_TABLE_SIZE)

Hash table for equations generated by the solver.

Referenced by normalize_omega_problem().

#define MAX_KEYS PARAM_VALUE (PARAM_OMEGA_MAX_KEYS)

Referenced by normalize_omega_problem().

Enumeration Type Documentation

enum normalize_return_type

Enumerator:

normalize_false
normalize_uncoupled
normalize_coupled

Function Documentation

static void adding_equality_constraint ( )

static

Add a new equality to problem PB at last position E.

References omega_pb_d::geqs, and single_var_geq().

static void bswap ( )

inlinestatic

Swap values contained in I and J.

References omega_pb_d::geqs, eqn_d::key, and omega_safe_var_p().

static void chain_unprotect ( )

static

Transform some wildcard variables to non-safe variables.

References eqn_d::coef, omega_pb_d::eqs, omega_pb_d::geqs, omega_pb_d::num_eqs, omega_pb_d::num_geqs, omega_pb_d::num_subs, and omega_pb_d::subs.

static void cleanout_wildcards ( )

static

Rewrite some non-safe variables in function of protected wildcard variables.

         i is the last nonzero non-safe variable.

         j is the next nonzero non-safe variable, or points
         to a safe variable: it is then a wildcard variable.

         Clean it out.

Referenced by omega_problem_has_red_equations().

static void coalesce ( )

static

Replace tuples of inequalities, that define upper and lower half spaces, with an equation.

References dump_file, omega_pb_d::geqs, omega_print_geq(), and omega_variable_to_str().

Referenced by omega_problem_has_red_equations().

DEBUG_FUNCTION void debug ( )

Dump problem PB.

DEBUG_FUNCTION void debug_omega_problem ( )

Debug problem PB.

static void divide_eqn_by_gcd ( )

inlinestatic

Divide the coefficients of EQN by their gcd. N_VARS is the number of variables in EQN.

static void free_red_eliminations ( )

static

Do free red eliminations.

static bool implies ( )

inlinestatic

static int int_div ( )

inlinestatic

Return the integer A divided by B.

References eqn_d::color, omega_red, and omega_simplify.

Referenced by normalize_omega_problem(), and parallel_splinter().

static int int_mod ( )

inlinestatic

Return the integer A modulo B.

static normalize_return_type normalize_omega_problem ( )

static

Normalizes PB by removing redundant constraints. Returns normalize_false when the constraints system has no solution, otherwise returns normalize_coupled or normalize_uncoupled.

Too many hash keys generated.

References eqn_d::coef, dump_file, dump_flags, g, gcc_assert, gcd(), omega_pb_d::geqs, HASH_TABLE_SIZE, int_div(), eqn_d::key, MAX_KEYS, next_key, omega_pb_d::num_vars, omega_init_eqn_zero(), omega_print_geq(), and eqn_d::touched.

Referenced by omega_problem_has_red_equations().

static int omega_add_new_wild_card ( )

static

Return the index of the last protected (or safe) variable in PB, after having added a new wildcard variable.

 Make a free place in the protected (safe) variables, by moving
 the non protected variable pointed by "I" at the end, ie. at
 offset pb->num_vars.

     Move "I" for all the inequalities.

     Move "I" for all the equalities.

     Move "I" for all the substitutions.

     Move the identifier.

 Initialize at zero all the coefficients

 And give it a name.

omega_pb omega_alloc_problem ( )

Initialize PB as an Omega problem with NVARS variables and NPROT safe variables. Safe variables are not eliminated during the Fourier-Motzkin elimination. Safe variables are all those variables that are placed at the beginning of the array of variables: P->var[0, ..., NPROT - 1].

Allocate and initialize PB.

Referenced by omega_setup_subscript(), and subscript_dependence_tester_1().

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

For equation EQ of the form "0 = EQN", insert in PB two inequalities "0 <= EQN" and "0 <= -EQN".

Insert "0 <= EQN".

 Insert "0 <= -EQN".

int omega_count_red_equations ( )

Return the number of equations in PB tagged omega_red.

References eqn_d::color, omega_pb_d::eqs, omega_pb_d::geqs, eqn_d::key, omega_pb_d::num_eqs, omega_pb_d::num_geqs, omega_pb_d::num_subs, omega_initialize_variables(), omega_print_eq(), omega_print_geq(), omega_print_vars(), omega_red, omega_var_to_str(), omega_pb_d::subs, and omega_pb_d::variables_initialized.

static void omega_delete_geq ( )

static

Delete inequality E from problem PB that has N_VARS variables.

static void omega_delete_geq_extra ( )

static

Delete extra inequality E from problem PB that has N_VARS variables.

References eqn_d::coef, omega_pb_d::eqs, omega_pb_d::geqs, omega_pb_d::num_eqs, omega_pb_d::num_geqs, omega_pb_d::num_subs, omega_pb_d::subs, eqn_d::touched, and omega_pb_d::var.

static void omega_delete_variable ( )

static

Remove variable I from problem PB.

static void omega_do_elimination ( )

static

Eliminates variable I from PB.

References dump_file, dump_flags, and omega_false.

Referenced by omega_problem_has_no_solution().

static void omega_do_mod ( )

static

Solve e = factor alpha for x_j and substitute.

void omega_eliminate_red ( )

Eliminate red inequalities from PB. When ELIMINATE_ALL is true, continue to eliminate all the red inequalities.

omega_simplify_problem (pb);

References dump_file, dump_flags, omega_pb_d::geqs, omega_pb_d::num_geqs, and omega_print_geq().

enum omega_result omega_eliminate_redundant ( )

Eliminate redundant equations in PB. When EXPENSIVE is true, an extra step is performed. Returns omega_false when there exist no solution, omega_true otherwise.

 {P,Z,N}EQS = {Positive,Zero,Negative} Equations.

 PP = Possible Positives, PZ = Possible Zeros, PN = Possible Negatives

                     Trying to prove e3 is redundant.

                     Trying to prove e3 <= 0 and therefore e3 = 0,
                    or trying to prove e3 < 0, and therefore the
                    problem has no solutions.

                     verify alpha1*v1+alpha2*v2 = alpha3*v3

                         We just proved e3 < 0, so no solutions exist.

                         We just proved that e3 <=0, so e3 = 0.

 Delete the inequalities that were marked as dead.

static bool omega_eqn_is_red ( )

inlinestatic

Test whether equation E is red.

References omega_var_to_str(), and omega_pb_d::var.

Referenced by parallel_splinter().

static void omega_free_eliminations ( )

static

Eliminates all the free variables for problem PB, that is all the variables from FV to PB->NUM_VARS.

References eqn_d::coef, eqn_d::color, omega_pb_d::geqs, and omega_red.

void omega_initialize ( void )

Initialization of the Omega solver.

static void omega_name_wild_card ( )

static

void omega_negate_geq ( )

Multiplies by -1 inequality E.

void omega_no_procedure ( )

Do nothing function: used for default initializations.

void omega_pretty_print_problem ( )

Pretty print PB to FILE.

                   Not a partial order relation.

                   Relation is v1 <= v2 or v1 < v2.

         Just in case pb->num_vars <= 0.

         Caught in cycle.

         Chain starts at v.

         Find chain.

             Print chain.

         Print last_links.

void omega_print_eqn ( )

Print to FILE the equation E of problem PB.

Referenced by omega_safe_var_p(), and omega_wildcard_p().

void omega_print_problem ( )

Print to FILE problem PB.

Referenced by omega_print_vars(), swap(), and verify_omega_pb().

void omega_print_red_equations ( )

Print to FILE all the equations in PB that are tagged omega_red.

static void omega_print_term ( )

static

Print to FILE from PB equation E with all its coefficients multiplied by C.

Referenced by omega_substitute_red().

static void omega_print_vars ( )

static

Print to FILE all the variables of problem PB.

References omega_print_problem().

Referenced by omega_count_red_equations().

static enum omega_result omega_problem_has_no_solution ( )

inlinestatic

Helper function for printing "sorry, no solution".

References omega_pb_d::num_eqs, and omega_do_elimination().

bool omega_problem_has_red_equations ( )

Return true if red equations constrain the set of possible solutions. We assume that there are solutions to the black equations by themselves, so if there is no solution to the combined problem, we return true.

References cleanout_wildcards(), coalesce(), gcc_assert, normalize_false, normalize_omega_problem(), omega_pb_d::num_subs, and resurrect_subs().

static void omega_problem_reduced ( )

static

Reduce problem PB.

bool omega_query_variable ( )

Return false when the upper and lower bounds are not coupled. Initialize the bounds LOWER_BOUND and UPPER_BOUND for the values of variable I.

bool omega_query_variable_bounds ( )

Return false when a lower bound L and an upper bound U for variable I in problem PB have been initialized.

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.

enum omega_result omega_simplify_approximate ( )

Calls omega_simplify_problem in approximate mode.

enum omega_result omega_simplify_problem ( )

Simplifies problem PB by eliminating redundant constraints and reducing the constraints system to a minimal form. Returns omega_true when the problem was successfully reduced, omega_unknown when the solver is unable to determine an answer.

References eqn_d::coef, omega_pb_d::num_vars, omega_pb_d::safe_vars, and omega_pb_d::subs.

Referenced by subscript_dependence_tester_1().

static enum omega_result omega_solve_eq ( )

static

Helper function: solve equations in PB one at a time, following the DESIRED_RES result.

 Eliminate all EQ equations

     i is the position of last nonzero coefficient,
     g is the coefficient of i,
     j is the position of next nonzero coefficient.

         Find variable to eliminate.

             Go back and try this equation again.

References eqn_d::coef, g, gcd(), and omega_safe_var_p().

static enum omega_result omega_solve_geq ( )

static

Helper function: solve equations one at a time.

   Verify that there are not too many inequalities.

           Our equation is ax + c >= 0, or ax >= -c, or c >= -ax.

     #ifdef Omega3

     Trying to produce exact elimination by finding redundant
     constraints.

     #endif

     #ifndef Omega3

     Trying to produce exact elimination by finding redundant
     constraints.

     #endif

                 An equality constraint must have been found

             Sort array LOWER_BOUND.

                 max_incr += 2;

References eqn_d::coef, eqn_d::color, omega_pb_d::geqs, eqn_d::key, omega_pb_d::num_geqs, and eqn_d::touched.

enum omega_result omega_solve_problem ( )

Return omega_true when the problem PB has a solution following the DESIRED_RES.

References eqn_d::coef, eqn_d::color, omega_pb_d::geqs, and omega_red.

static void omega_substitute ( )

static

Substitute in PB variable VAR with "C * SUB".

static void omega_substitute_red ( )

static

Substitute in PB variable VAR with "C * SUB".

References dump_file, eqn_d::key, omega_print_term(), and omega_var_to_str().

static void omega_substitute_red_1	(	eqn	eq,
		eqn	sub,
		int	var,
		int	c,
		bool *	found_black,
		int	top_var
	)

inlinestatic

Computes a linear combination of EQ and SUB at VAR with coefficient C, such that EQ->coef[VAR] is set to 0. TOP_VAR is the number of non null indices of SUB stored in PACKING.

static void omega_unprotect_1 ( )

inlinestatic

Make variable IDX unprotected in PB, by swapping its index at the PB->safe_vars rank.

 If IDX is protected...

     ... swap its index with the last non protected index.

 The variable at pb->safe_vars is also unprotected now.

References eqn_d::coef, omega_pb_d::eqs, omega_pb_d::geqs, omega_pb_d::num_eqs, omega_pb_d::num_geqs, omega_pb_d::num_subs, omega_pb_d::subs, and omega_pb_d::var.

void omega_unprotect_variable ( )

Make variable VAR unprotected: it then can be eliminated.

static char* omega_var_to_str ( )

inlinestatic

Return a string for VARIABLE.

Collapse all the entries that would have overflowed.

Referenced by omega_count_red_equations(), omega_eqn_is_red(), and omega_substitute_red().

static char* omega_variable_to_str ( )

inlinestatic

Return a string for variable I in problem PB.

Referenced by coalesce().

static enum omega_result parallel_splinter	(	omega_pb	pb,
		int	e,
		int	diff,
		enum omega_result	desired_res
	)

static

Transform an inequation E to an equality, then solve DIFF problems based on PB, and only differing by the constant part that is diminished by one, trying to figure out which of the constants satisfies PB.

References eqn_d::color, omega_pb_d::geqs, int_div(), and omega_eqn_is_red().

static void query_coupled_variable	(	omega_pb	pb,
		int	i,
		int *	l,
		int *	u,
		bool *	could_be_zero,
		int	lower_bound,
		int	upper_bound
	)

static

Sets the lower bound L and upper bound U for the values of variable I, and sets COULD_BE_ZERO to true if variable I might take value zero. LOWER_BOUND and UPPER_BOUND are bounds on the values of variable I.

Preconditions.

 Define variable I in terms of variable V.

static void resurrect_subs ( )

static

During the Fourier-Motzkin elimination some variables are substituted with other variables. This function resurrects the substituted variables in PB.

Referenced by omega_problem_has_red_equations().

static int setup_packing ( )

inlinestatic

Set up the coefficients of PACKING, following the coefficients of equation EQN that has NUM_VARS variables.

static int smooth_weird_equations ( )

static

For each inequality that has coefficients bigger than 20, try to create a new constraint that cannot be derived from the original constraint and that has smaller coefficients. Add the new constraint at the end of geqs. Return the number of inequalities that have been added to PB.

       Magic number.

           Magic number.

                     Try to prove e3 is redundant: verify
                     alpha1*v1 + alpha2*v2 = alpha3*v3.

static void swap ( )

inlinestatic

Swap values contained in I and J.

References dump_file, and omega_print_problem().

Referenced by commutative_optab_p(), insert_gimplified_predicates(), remove_name_from_operation(), and shift_optab_p().

static enum omega_result verify_omega_pb ( )

static

Returns OMEGA_TRUE when problem PB has a solution.

References eqn_d::coef, dump_file, dump_flags, omega_pb_d::eqs, omega_pb_d::num_eqs, omega_pb_d::num_vars, omega_init_eqn_zero(), omega_print_problem(), and omega_pb_d::var.

Variable Documentation

int conservative = 0

static

When set to zero, the solver is allowed to add new equalities to the problem to be solved.

bool create_color = false

static

Set to true when the solver is allowed to add omega_red equations.

int* fast_lookup

static

int* fast_lookup_red

static

eqn hash_master

static

int hash_version = 0

static

bool in_approximate_mode = false

static

Set to true for making the solver enter in approximation mode.

int may_be_red = 0

static

Set to nonzero when the problem to be solved can be reduced.

int next_key

static

Referenced by normalize_omega_problem().

int next_wild_card = 0

static

Assign to variable I in PB the next wildcard name. The name of a wildcard is a negative number.

omega_pb no_problem = (omega_pb) 0

static

Pointer to the void problem.

enum omega_result omega_found_reduction

static

Set to omega_true when the problem was successfully reduced, set to omega_unknown when the solver is unable to determine an answer.

bool omega_initialized = false

static

Keeps the state of the initialization.

bool omega_reduce_with_subs = true

static

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/. For a detailed description, see "Constraint-Based Array Dependence Analysis" William Pugh, David Wonnacott, TOPLAS'98 and David Wonnacott's thesis: ftp://ftp.cs.umd.edu/pub/omega/davewThesis/davewThesis.ps.gz When set to true, keep substitution variables. When set to false, resurrect substitution variables (convert substitutions back to EQs).

bool omega_single_result = false

static

When set to true, only produce a single simplified result.

int omega_solve_depth = 0

static

Because the omega solver is recursive, this counter limits the recursion depth.

bool omega_verify_simplification = false

static

When set to true, omega_simplify_problem checks for problem with no solutions, calling verify_omega_pb.

void(* omega_when_reduced)(omega_pb) = omega_no_procedure

omega_pb original_problem = (omega_pb) 0

static

Pointer to the problem to be solved.

int* packing

static

Because the coefficients of an equation are sparse, PACKING records indices for non null coefficients.

int please_no_equalities_in_simplified_problems = 0

static

When false, there should be no substitution equations in the simplified problem.

int return_single_result = 0

static

Set return_single_result to 1 when omega_single_result is true.

char wild_name[200][40]

static

Variables names for pretty printing.

Macros

Enumerations

Functions

Variables

Macro Definition Documentation

Enumeration Type Documentation

Function Documentation

Variable Documentation