GCC Middle and Back End API Reference
omega.c File Reference


enum  normalize_return_type { normalize_false, normalize_uncoupled, normalize_coupled }


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


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


Function Documentation

static void adding_equality_constraint ( )
   Add a new equality to problem PB at last position E.  

References omega_pb_d::geqs, and single_var_geq().

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

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

static void chain_unprotect ( )
   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 ( )
   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 ( )
   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 ( )
   Divide the coefficients of EQN by their gcd.  N_VARS is the number
   of variables in EQN.  
static void free_red_eliminations ( )
   Do free red eliminations.  
static bool implies ( )
static int int_div ( )
   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 ( )
   Return the integer A modulo B.  
static normalize_return_type normalize_omega_problem ( )
   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, gcd(), omega_pb_d::geqs, int_div(), eqn_d::key, 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 ( )
   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".  
static void omega_delete_geq ( )
   Delete inequality E from problem PB that has N_VARS variables.  
static void omega_delete_geq_extra ( )
   Delete extra inequality E from problem PB that has N_VARS

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 ( )
   Remove variable I from problem PB.  
static void omega_do_elimination ( )
   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 ( )
   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 ( )
   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 ( )
   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 ( )
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 ( )
   Print to FILE from PB equation E with all its coefficients
   multiplied by C.  

Referenced by omega_substitute_red().

static void omega_print_vars ( )
   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 ( )
   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(), normalize_false, normalize_omega_problem(), omega_pb_d::num_subs, and resurrect_subs().

static void omega_problem_reduced ( )
   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
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 ( )
   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 ( )
   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
         #ifndef Omega3 
         Trying to produce exact elimination by finding redundant
                     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

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

static void omega_substitute ( )
   Substitute in PB variable VAR with "C * SUB".  
static void omega_substitute_red ( )
   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 
   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 ( )
   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 ( )
   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 ( )
   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 
   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 
   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.  
     Define variable I in terms of variable V.  
static void resurrect_subs ( )
   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 ( )
   Set up the coefficients of PACKING, following the coefficients of
   equation EQN that has NUM_VARS variables.  
static int smooth_weird_equations ( )
   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 ( )
static enum omega_result verify_omega_pb ( )

Variable Documentation

int conservative = 0
   When set to zero, the solver is allowed to add new equalities to
   the problem to be solved.  
bool create_color = false
   Set to true when the solver is allowed to add omega_red equations.  
int* fast_lookup
int* fast_lookup_red
eqn hash_master
int hash_version = 0
bool in_approximate_mode = false
   Set to true for making the solver enter in approximation mode.  
int may_be_red = 0
   Set to nonzero when the problem to be solved can be reduced.  
int next_key

Referenced by normalize_omega_problem().

int next_wild_card = 0
   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
   Pointer to the void problem.  
enum omega_result omega_found_reduction
   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
   Keeps the state of the initialization.  
bool omega_reduce_with_subs = true

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:
   When set to true, keep substitution variables.  When set to false,
   resurrect substitution variables (convert substitutions back to EQs).  
bool omega_single_result = false
   When set to true, only produce a single simplified result.  
int omega_solve_depth = 0
   Because the omega solver is recursive, this counter limits the
   recursion depth.  
bool omega_verify_simplification = false
   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
   Pointer to the problem to be solved.  
int* packing
   Because the coefficients of an equation are sparse, PACKING records
   indices for non null coefficients.  
int please_no_equalities_in_simplified_problems = 0
   When false, there should be no substitution equations in the
   simplified problem.  
int return_single_result = 0
   Set return_single_result to 1 when omega_single_result is true.  
char wild_name[200][40]
   Variables names for pretty printing.