GCC Middle and Back End API Reference
omega.h File Reference
#include "config.h"
#include "params.h"
Include dependency graph for omega.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of 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_deqn
typedef struct omega_pb_domega_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.

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

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

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

Enumerator:
omega_black 
omega_red 

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)