GCC Middle and Back End API Reference
Enumerations | Functions | Variables
omega.c File Reference

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

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 eqn_d::coef, conservative, 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.

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

static void bswap ( )
inlinestatic 
Swap values contained in I and J.

Referenced by omega_unprotect_1().

static void chain_unprotect ( )
static 
Transform some wildcard variables to non-safe variables.

References eqn_d::coef, dump_file, dump_flags, free(), omega_pb_d::num_subs, omega_print_problem(), omega_safe_var_p(), omega_unprotect_1(), omega_variable_to_str(), omega_wildcard_p(), and omega_pb_d::subs.

Referenced by omega_problem_reduced(), and omega_unprotect_variable().

static void cleanout_wildcards ( )
static 
Rewrite some non-safe variables in function of protected
   wildcard variables.

References eqn_d::coef, eqn_d::color, divide_eqn_by_gcd(), dump_file, dump_flags, omega_pb_d::eqs, omega_pb_d::geqs, normalize_omega_problem(), omega_pb_d::num_eqs, omega_pb_d::num_geqs, omega_pb_d::num_subs, omega_pb_d::num_vars, omega_black, omega_print_eq(), omega_print_problem(), omega_red, omega_safe_var_p(), omega_pb_d::subs, and eqn_d::touched.

Referenced by omega_problem_has_red_equations(), and resurrect_subs().

static void coalesce ( )
static 
Replace tuples of inequalities, that define upper and lower half
   spaces, with an equation.

References eqn_d::coef, eqn_d::color, dump_file, dump_flags, omega_pb_d::eqs, free(), omega_pb_d::geqs, eqn_d::key, omega_pb_d::num_eqs, omega_pb_d::num_geqs, omega_pb_d::num_vars, omega_copy_eqn(), omega_delete_geq(), omega_print_problem(), omega_red, and eqn_d::touched.

Referenced by omega_problem_has_red_equations(), and omega_problem_reduced().

DEBUG_FUNCTION void debug ( ) 
Dump problem PB.

References omega_print_problem().

DEBUG_FUNCTION void debug_omega_problem ( ) 
Debug problem PB.

References omega_print_problem().

static void divide_eqn_by_gcd ( )
inlinestatic 
Divide the coefficients of EQN by their gcd.  N_VARS is the number
   of variables in EQN.

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

Referenced by cleanout_wildcards().

static void free_red_eliminations ( )
static 
Do free red eliminations.

References eqn_d::coef, eqn_d::color, dump_file, dump_flags, omega_pb_d::eqs, free(), omega_pb_d::geqs, omega_pb_d::num_eqs, omega_pb_d::num_geqs, omega_pb_d::num_subs, omega_pb_d::num_vars, omega_delete_geq(), omega_delete_variable(), omega_print_problem(), omega_red, omega_variable_to_str(), and omega_pb_d::subs.

Referenced by omega_problem_has_red_equations().

static bool implies ( )
inlinestatic

Referenced by omega_eliminate_redundant().

static int int_div ( )
inlinestatic 
Return the integer A divided by B.

Referenced by int_mod(), normalize_omega_problem(), omega_solve_geq(), and smooth_weird_equations().

static int int_mod ( )
inlinestatic 
Return the integer A modulo B.

References int_div().

Referenced by omega_do_mod(), omega_solve_eq(), and query_coupled_variable().

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.

References adding_equality_constraint(), eqn_d::coef, eqn_d::color, create_color, dump_file, dump_flags, omega_pb_d::eqs, g, gcd(), omega_pb_d::geqs, int_div(), eqn_d::key, next_key, normalize_coupled, normalize_false, normalize_uncoupled, omega_pb_d::num_eqs, omega_pb_d::num_geqs, omega_pb_d::num_vars, omega_black, omega_copy_eqn(), omega_delete_geq(), omega_init_eqn_zero(), omega_print_geq(), omega_red, single_var_geq(), and eqn_d::touched.

Referenced by cleanout_wildcards(), omega_problem_has_red_equations(), and omega_solve_geq().

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.

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::num_vars, omega_name_wild_card(), omega_pb_d::safe_vars, omega_pb_d::subs, eqn_d::touched, and omega_pb_d::var.

Referenced by omega_do_mod(), and omega_solve_eq().

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

References omega_pb_d::eqs, omega_pb_d::forwarding_address, omega_pb_d::geqs, hash_version, 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_alloc_eqns(), omega_initialize(), 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 init_omega_for_ddr(), omega_extract_distance_vectors(), and omega_solve_geq().

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 ( ) 
For equation EQ of the form "0 = EQN", insert in PB two
   inequalities "0 <= EQN" and "0 <= -EQN".

References eqn_d::coef, dump_file, dump_flags, omega_pb_d::eqs, omega_pb_d::geqs, omega_pb_d::num_geqs, omega_pb_d::num_vars, omega_copy_eqn(), omega_print_problem(), and eqn_d::touched.

Referenced by omega_do_elimination().

int omega_count_red_equations ( ) 
Return the number of equations in PB tagged omega_red.

References eqn_d::coef, eqn_d::color, 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::num_vars, omega_red, and omega_pb_d::subs.

static void omega_delete_geq ( )
static 
Delete inequality E from problem PB that has N_VARS variables.

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

Referenced by coalesce(), free_red_eliminations(), normalize_omega_problem(), omega_eliminate_red(), omega_eliminate_redundant(), omega_free_eliminations(), and omega_solve_geq().

static void omega_delete_geq_extra ( )
static 
Delete extra inequality E from problem PB that has N_VARS
   variables.

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

Referenced by omega_solve_geq().

static void omega_delete_variable ( )
static 
Remove variable I from problem PB.

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::num_vars, omega_safe_var_p(), omega_pb_d::safe_vars, omega_pb_d::subs, eqn_d::touched, and omega_pb_d::var.

Referenced by free_red_eliminations(), omega_do_elimination(), omega_do_mod(), and omega_free_eliminations().

static void omega_do_elimination ( )
static 
Eliminates variable I from PB.

References eqn_d::coef, eqn_d::color, dump_file, dump_flags, omega_pb_d::eqs, omega_pb_d::geqs, in_approximate_mode, omega_pb_d::num_eqs, omega_pb_d::num_geqs, omega_pb_d::num_subs, omega_pb_d::num_vars, omega_alloc_eqns(), omega_black, omega_convert_eq_to_geqs(), omega_copy_eqn(), omega_delete_variable(), omega_free_eqns(), omega_red, omega_substitute(), omega_substitute_red(), omega_variable_to_str(), omega_pb_d::subs, and eqn_d::touched.

Referenced by omega_solve_eq().

static void omega_do_mod ( )
static 
Solve e = factor alpha for x_j and substitute.

References eqn_d::coef, dump_file, dump_flags, omega_pb_d::eqs, int_mod(), omega_pb_d::num_vars, omega_add_new_wild_card(), omega_alloc_eqns(), omega_copy_eqn(), omega_delete_variable(), omega_free_eqns(), omega_name_wild_card(), omega_print_problem(), omega_safe_var_p(), omega_substitute(), and omega_wildcard_p().

Referenced by omega_solve_eq().

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

References eqn_d::coef, eqn_d::color, conservative, dump_file, dump_flags, free(), omega_pb_d::geqs, omega_pb_d::num_eqs, omega_pb_d::num_geqs, omega_pb_d::num_subs, omega_pb_d::num_vars, omega_black, omega_copy_problem(), omega_delete_geq(), omega_false, omega_negate_geq(), omega_print_geq(), omega_print_problem(), omega_red, omega_reduce_with_subs, omega_simplify_problem(), omega_solve_problem(), omega_variable_to_str(), omega_verify_simplification, please_no_equalities_in_simplified_problems, omega_pb_d::safe_vars, omega_pb_d::variables_freed, and verify_omega_pb().

Referenced by omega_problem_has_red_equations().

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.

References adding_equality_constraint(), eqn_d::coef, eqn_d::color, conservative, dump_file, dump_flags, omega_pb_d::eqs, free(), omega_pb_d::geqs, implies(), omega_pb_d::num_eqs, omega_pb_d::num_geqs, omega_pb_d::num_subs, omega_pb_d::num_vars, omega_black, omega_copy_eqn(), omega_copy_problem(), omega_delete_geq(), omega_false, omega_negate_geq(), omega_print_geq(), omega_print_problem(), omega_red, omega_reduce_with_subs, omega_solve_problem(), omega_true, please_no_equalities_in_simplified_problems, resurrect_subs(), omega_pb_d::safe_vars, and omega_pb_d::variables_freed.

Referenced by omega_pretty_print_problem(), omega_problem_reduced(), and omega_solve_geq().

static bool omega_eqn_is_red ( )
inlinestatic 
Test whether equation E is red.

References eqn_d::color, omega_red, and omega_simplify.

Referenced by omega_solve_eq(), and omega_solve_geq().

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, dump_file, dump_flags, 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::num_vars, omega_delete_geq(), omega_delete_variable(), omega_print_problem(), omega_variable_to_str(), and omega_pb_d::subs.

Referenced by omega_simplify_problem(), 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_name_wild_card ( )
static

References next_wild_card, and omega_pb_d::var.

Referenced by omega_add_new_wild_card(), omega_do_mod(), and omega_solve_eq().

void omega_negate_geq ( ) 
Multiplies by -1 inequality E.

References eqn_d::coef, omega_pb_d::geqs, omega_pb_d::num_vars, and eqn_d::touched.

Referenced by omega_eliminate_red(), and omega_eliminate_redundant().

void omega_no_procedure ( ) 
Do nothing function: used for default initializations.
void omega_pretty_print_problem ( ) 
Pretty print PB to FILE.

References eqn_d::coef, omega_pb_d::eqs, first, free(), omega_pb_d::geqs, eqn_d::key, live, none, omega_pb_d::num_eqs, omega_pb_d::num_geqs, omega_pb_d::num_subs, omega_pb_d::num_vars, omega_eliminate_redundant(), omega_initialize_variables(), omega_print_eq(), omega_print_geq(), omega_print_term(), omega_var_to_str(), omega_variable_to_str(), omega_pb_d::subs, and omega_pb_d::variables_initialized.

void omega_print_eqn ( ) 
Print to FILE the equation E of problem PB.

References eqn_d::coef, eqn_d::color, first, eqn_d::key, omega_pb_d::num_vars, omega_red, omega_variable_to_str(), and eqn_d::touched.

Referenced by omega_print_eq(), omega_print_geq(), and omega_print_geq_extra().

void omega_print_problem ( ) 
Print to FILE problem PB.

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_term(), omega_print_vars(), omega_red, omega_var_to_str(), omega_pb_d::subs, and omega_pb_d::variables_initialized.

Referenced by adding_equality_constraint(), chain_unprotect(), cleanout_wildcards(), coalesce(), debug(), debug_omega_problem(), free_red_eliminations(), omega_convert_eq_to_geqs(), omega_do_mod(), omega_eliminate_red(), omega_eliminate_redundant(), omega_free_eliminations(), omega_problem_has_red_equations(), omega_problem_reduced(), omega_solve_eq(), omega_solve_geq(), omega_solve_problem(), omega_substitute(), parallel_splinter(), resurrect_subs(), smooth_weird_equations(), and verify_omega_pb().

void omega_print_red_equations ( ) 
Print to FILE all the equations in PB that are 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_term(), omega_print_vars(), omega_red, omega_var_to_str(), omega_pb_d::subs, and omega_pb_d::variables_initialized.

static void omega_print_term ( )
static 
Print to FILE from PB equation E with all its coefficients
   multiplied by C.

References eqn_d::coef, first, omega_pb_d::num_vars, and omega_variable_to_str().

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

static void omega_print_vars ( )
static 
Print to FILE all the variables of problem PB.

References omega_pb_d::num_vars, omega_variable_to_str(), and omega_pb_d::safe_vars.

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

static enum omega_result omega_problem_has_no_solution ( )
inlinestatic 
Helper function for printing "sorry, no solution".

References dump_file, dump_flags, and omega_false.

Referenced by omega_solve_eq(), and omega_solve_geq().

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(), eqn_d::coef, eqn_d::color, create_color, dump_file, dump_flags, omega_pb_d::eqs, free_red_eliminations(), omega_pb_d::geqs, may_be_red, normalize_false, normalize_omega_problem(), omega_pb_d::num_eqs, omega_pb_d::num_geqs, omega_pb_d::num_subs, omega_pb_d::num_vars, omega_eliminate_red(), omega_false, omega_print_problem(), omega_red, omega_reduce_with_subs, omega_simplify_problem(), omega_single_result, please_no_equalities_in_simplified_problems, resurrect_subs(), return_single_result, and omega_pb_d::safe_vars.

static void omega_problem_reduced ( )
static 
Reduce problem PB.

References chain_unprotect(), coalesce(), dump_file, dump_flags, omega_pb_d::forwarding_address, in_approximate_mode, eqn_d::key, omega_pb_d::num_subs, omega_eliminate_redundant(), omega_false, omega_found_reduction, omega_print_problem(), omega_reduce_with_subs, omega_safe_var_p(), omega_true, omega_verify_simplification, omega_when_reduced, please_no_equalities_in_simplified_problems, resurrect_subs(), return_single_result, omega_pb_d::subs, omega_pb_d::var, and verify_omega_pb().

Referenced by omega_solve_geq(), and omega_solve_problem().

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.

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

Referenced by omega_query_variable_bounds(), and omega_query_variable_signs().

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.

References omega_pb_d::forwarding_address, omega_pb_d::num_eqs, omega_pb_d::num_subs, omega_pb_d::num_vars, omega_query_variable(), and query_coupled_variable().

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

enum omega_result omega_simplify_approximate ( ) 
Calls omega_simplify_problem in approximate mode.

References dump_file, dump_flags, in_approximate_mode, omega_pb_d::num_subs, omega_pb_d::num_vars, omega_reduce_with_subs, omega_simplify_problem(), and omega_pb_d::safe_vars.

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 omega_pb_d::forwarding_address, omega_pb_d::geqs, hash_version, omega_pb_d::hash_version, eqn_d::key, may_be_red, next_key, omega_pb_d::num_eqs, omega_pb_d::num_geqs, omega_pb_d::num_subs, omega_pb_d::num_vars, omega_false, omega_found_reduction, omega_free_eliminations(), omega_initialize_variables(), omega_reduce_with_subs, omega_safe_var_p(), omega_simplify, omega_solve_problem(), omega_unknown, please_no_equalities_in_simplified_problems, return_single_result, omega_pb_d::safe_vars, omega_pb_d::subs, eqn_d::touched, omega_pb_d::var, and omega_pb_d::variables_initialized.

Referenced by omega_constrain_variable_sign(), omega_eliminate_red(), omega_extract_distance_vectors(), omega_problem_has_red_equations(), and omega_simplify_approximate().

static enum omega_result omega_solve_eq ( )
static 
Helper function: solve equations in PB one at a time, following the
   DESIRED_RES result.

References eqn_d::coef, eqn_d::color, color(), dump_file, dump_flags, omega_pb_d::eqs, g, gcd(), omega_pb_d::geqs, in_approximate_mode, int_mod(), may_be_red, omega_pb_d::num_eqs, omega_pb_d::num_geqs, omega_pb_d::num_subs, omega_pb_d::num_vars, omega_add_new_wild_card(), omega_alloc_eqns(), omega_black, omega_copy_eqn(), omega_do_elimination(), omega_do_mod(), omega_eqn_is_red(), omega_free_eqns(), omega_init_eqn_zero(), omega_name_wild_card(), omega_print_eq(), omega_print_problem(), omega_print_vars(), omega_problem_has_no_solution(), omega_red, omega_safe_var_p(), omega_unknown, omega_variable_to_str(), omega_wildcard_p(), omega_pb_d::safe_vars, and omega_pb_d::subs.

Referenced by omega_solve_problem().

static enum omega_result omega_solve_geq ( )
static 
Helper function: solve equations one at a time.

References adding_equality_constraint(), eqn_d::coef, eqn_d::color, conservative, dump_file, dump_flags, omega_pb_d::eqs, free(), omega_pb_d::geqs, in_approximate_mode, int_div(), eqn_d::key, mul_hwi(), no_problem, normalize_coupled, normalize_false, normalize_omega_problem(), normalize_uncoupled, omega_pb_d::num_eqs, omega_pb_d::num_geqs, omega_pb_d::num_subs, omega_pb_d::num_vars, omega_alloc_eqns(), omega_alloc_problem(), omega_black, omega_copy_eqn(), omega_copy_problem(), omega_delete_geq(), omega_delete_geq_extra(), omega_eliminate_redundant(), omega_eqn_is_red(), omega_false, omega_free_eliminations(), omega_free_eqns(), omega_init_eqn_zero(), omega_print_geq(), omega_print_geq_extra(), omega_print_problem(), omega_problem_has_no_solution(), omega_problem_reduced(), omega_red, omega_safe_var_p(), omega_simplify, omega_solve_problem(), omega_true, omega_unknown, omega_variable_to_str(), parallel_splinter(), please_no_equalities_in_simplified_problems, pos_mul_hwi(), return_single_result, omega_pb_d::safe_vars, single_var_geq(), smooth_weird_equations(), omega_pb_d::subs, swap(), eqn_d::touched, omega_pb_d::var, omega_pb_d::variables_freed, and omega_pb_d::variables_initialized.

Referenced by omega_solve_problem().

enum omega_result omega_solve_problem ( ) 
Return omega_true when the problem PB has a solution following the
   DESIRED_RES.

References dump_file, dump_flags, in_approximate_mode, omega_pb_d::num_geqs, omega_pb_d::num_subs, omega_pb_d::num_vars, omega_false, omega_print_problem(), omega_problem_reduced(), omega_reduce_with_subs, omega_simplify, omega_solve_eq(), omega_solve_geq(), omega_true, please_no_equalities_in_simplified_problems, resurrect_subs(), and omega_pb_d::safe_vars.

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

static void omega_substitute ( )
static 
Substitute in PB variable VAR with "C * SUB".

References eqn_d::coef, eqn_d::color, dump_file, dump_flags, 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_pb_d::num_vars, omega_black, omega_print_eq(), omega_print_geq(), omega_print_problem(), omega_print_term(), omega_print_vars(), omega_safe_var_p(), omega_var_to_str(), omega_variable_to_str(), omega_wildcard_p(), setup_packing(), omega_pb_d::subs, eqn_d::touched, and omega_pb_d::var.

Referenced by omega_do_elimination(), and omega_do_mod().

static void omega_substitute_red ( )
static 
Substitute in PB variable VAR with "C * SUB".

References eqn_d::coef, eqn_d::color, dump_file, dump_flags, 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_pb_d::num_vars, omega_print_eq(), omega_print_geq(), omega_print_term(), omega_print_vars(), omega_red, omega_safe_var_p(), omega_substitute_red_1(), omega_var_to_str(), omega_variable_to_str(), omega_wildcard_p(), setup_packing(), omega_pb_d::subs, and eqn_d::touched.

Referenced by omega_do_elimination().

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.

References eqn_d::coef, eqn_d::color, and omega_black.

Referenced by omega_substitute_red().

static void omega_unprotect_1 ( )
inlinestatic 
Make variable IDX unprotected in PB, by swapping its index at the
   PB->safe_vars rank.

References bswap(), eqn_d::coef, 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_subs, omega_pb_d::safe_vars, omega_pb_d::subs, swap(), eqn_d::touched, and omega_pb_d::var.

Referenced by chain_unprotect(), omega_unprotect_variable(), and resurrect_subs().

void omega_unprotect_variable ( ) 
Make variable VAR unprotected: it then can be eliminated.

References chain_unprotect(), eqn_d::coef, omega_pb_d::eqs, omega_pb_d::forwarding_address, free(), omega_pb_d::geqs, eqn_d::key, omega_pb_d::num_eqs, omega_pb_d::num_geqs, omega_pb_d::num_subs, omega_pb_d::num_vars, omega_copy_eqn(), omega_unprotect_1(), omega_pb_d::safe_vars, omega_pb_d::subs, and omega_pb_d::var.

Referenced by omega_constrain_variable_sign().

static char* omega_var_to_str ( )
inlinestatic 
Return a string for VARIABLE.

References wild_name.

Referenced by omega_pretty_print_problem(), omega_print_problem(), omega_print_red_equations(), omega_substitute(), omega_substitute_red(), and omega_variable_to_str().

static char* omega_variable_to_str ( )
inlinestatic 
Return a string for variable I in problem PB.

References omega_var_to_str(), and omega_pb_d::var.

Referenced by chain_unprotect(), free_red_eliminations(), omega_do_elimination(), omega_eliminate_red(), omega_free_eliminations(), omega_pretty_print_problem(), omega_print_eqn(), omega_print_term(), omega_print_vars(), omega_solve_eq(), omega_solve_geq(), omega_substitute(), and omega_substitute_red().

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::coef, dump_file, dump_flags, omega_pb_d::eqs, free(), omega_pb_d::geqs, omega_pb_d::num_eqs, omega_pb_d::num_vars, omega_copy_eqn(), omega_copy_problem(), omega_false, omega_print_problem(), omega_solve_problem(), and omega_true.

Referenced by omega_solve_geq().

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.

References eqn_d::coef, omega_pb_d::eqs, omega_pb_d::forwarding_address, omega_pb_d::geqs, int_mod(), omega_pb_d::num_eqs, omega_pb_d::num_geqs, omega_pb_d::num_subs, omega_pb_d::num_vars, and omega_pb_d::subs.

Referenced by omega_query_variable_bounds(), and omega_query_variable_signs().

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.

References cleanout_wildcards(), eqn_d::coef, eqn_d::color, dump_file, dump_flags, 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_pb_d::num_vars, omega_black, omega_copy_eqn(), omega_print_eq(), omega_print_problem(), omega_safe_var_p(), omega_unprotect_1(), omega_wildcard_p(), please_no_equalities_in_simplified_problems, omega_pb_d::safe_vars, single_var_geq(), omega_pb_d::subs, eqn_d::touched, and omega_pb_d::var.

Referenced by omega_eliminate_redundant(), omega_problem_has_red_equations(), omega_problem_reduced(), and omega_solve_problem().

static int setup_packing ( )
inlinestatic 
Set up the coefficients of PACKING, following the coefficients of
   equation EQN that has NUM_VARS variables.

References eqn_d::coef.

Referenced by omega_substitute(), and omega_substitute_red().

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.

References eqn_d::coef, eqn_d::color, dump_file, dump_flags, g, omega_pb_d::geqs, int_div(), omega_pb_d::num_geqs, omega_pb_d::num_vars, omega_black, omega_print_geq(), omega_print_problem(), and eqn_d::touched.

Referenced by omega_solve_geq().

static void swap ( )
inlinestatic 
Swap values contained in I and J.

Referenced by combine_chains(), expand_binop_directly(), fold_plusminus_mult_expr(), forward_propagate_into_cond(), maybe_canonicalize_comparison_1(), omega_solve_geq(), omega_unprotect_1(), predicate_mem_writes(), sreal_add(), and sreal_mul().

static enum omega_result verify_omega_pb ( )
static 
Returns OMEGA_TRUE when problem PB has a solution.

References eqn_d::color, dump_file, dump_flags, free(), omega_pb_d::geqs, no_problem, omega_pb_d::num_geqs, omega_pb_d::num_subs, omega_copy_problem(), omega_false, omega_print_problem(), omega_red, omega_solve_problem(), omega_unknown, please_no_equalities_in_simplified_problems, and omega_pb_d::safe_vars.

Referenced by omega_eliminate_red(), and omega_problem_reduced().

Variable Documentation

int conservative = 0
static 
When set to zero, the solver is allowed to add new equalities to
   the problem to be solved.

Referenced by adding_equality_constraint(), omega_eliminate_red(), omega_eliminate_redundant(), and omega_solve_geq().

bool create_color = false
static 
Set to true when the solver is allowed to add omega_red equations.

Referenced by normalize_omega_problem(), and omega_problem_has_red_equations().

int* fast_lookup
static
int* fast_lookup_red
static
eqn hash_master
static
int hash_version = 0
static

Referenced by omega_alloc_problem(), and omega_simplify_problem().

bool in_approximate_mode = false
static 
Set to true for making the solver enter in approximation mode.

Referenced by omega_do_elimination(), omega_problem_reduced(), omega_simplify_approximate(), omega_solve_eq(), omega_solve_geq(), and omega_solve_problem().

int may_be_red = 0
static 
Set to nonzero when the problem to be solved can be reduced.

Referenced by omega_problem_has_red_equations(), omega_simplify_problem(), and omega_solve_eq().

int next_key
static

Referenced by normalize_omega_problem(), omega_initialize(), and omega_simplify_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.

Referenced by omega_name_wild_card().

omega_pb no_problem = (omega_pb) 0
static 
Pointer to the void problem.

Referenced by omega_solve_geq(), and verify_omega_pb().

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.

Referenced by omega_problem_reduced(), and omega_simplify_problem().

bool omega_initialized = false
static 
Keeps the state of the initialization.
bool omega_reduce_with_subs = true
static 
@verbatim 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.

Changes copyright (C) 2005-2013 Free Software Foundation, Inc. Contributed by Sebastian Pop sebas.nosp@m.tian.nosp@m..pop@.nosp@m.inri.nosp@m.a.fr

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

Referenced by omega_eliminate_red(), omega_eliminate_redundant(), omega_problem_has_red_equations(), omega_problem_reduced(), omega_simplify_approximate(), omega_simplify_problem(), and omega_solve_problem().

bool omega_single_result = false
static 
When set to true, only produce a single simplified result.

Referenced by omega_problem_has_red_equations().

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.

Referenced by omega_eliminate_red(), and omega_problem_reduced().

void(* omega_when_reduced)(omega_pb) = omega_no_procedure

Referenced by omega_problem_reduced().

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.

Referenced by omega_eliminate_red(), omega_eliminate_redundant(), omega_problem_has_red_equations(), omega_problem_reduced(), omega_simplify_problem(), omega_solve_geq(), omega_solve_problem(), resurrect_subs(), and verify_omega_pb().

int return_single_result = 0
static 
Set return_single_result to 1 when omega_single_result is true.

Referenced by omega_problem_has_red_equations(), omega_problem_reduced(), omega_simplify_problem(), and omega_solve_geq().

char wild_name[200][40]
static 
Variables names for pretty printing.

Referenced by omega_initialize(), and omega_var_to_str().