From 1bc5aee63eb72b341f506ad058502cd0361f0d10 Mon Sep 17 00:00:00 2001 From: Ben Cheng Date: Tue, 25 Mar 2014 22:37:19 -0700 Subject: Initial checkin of GCC 4.9.0 from trunk (r208799). Change-Id: I48a3c08bb98542aa215912a75f03c0890e497dba --- gcc-4.9/gcc/omega.h | 341 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 341 insertions(+) create mode 100644 gcc-4.9/gcc/omega.h (limited to 'gcc-4.9/gcc/omega.h') diff --git a/gcc-4.9/gcc/omega.h b/gcc-4.9/gcc/omega.h new file mode 100644 index 000000000..903ec058f --- /dev/null +++ b/gcc-4.9/gcc/omega.h @@ -0,0 +1,341 @@ +/* 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-2014 Free Software Foundation, Inc. + Contributed by Sebastian Pop + +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 +. */ + +#include "config.h" +#include "params.h" + +#ifndef GCC_OMEGA_H +#define GCC_OMEGA_H + +#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) + +/* Results of the Omega solver. */ +enum omega_result { + omega_false = 0, + omega_true = 1, + + /* Value returned when the solver is unable to determine an + answer. */ + omega_unknown = 2, + + /* Value used for asking the solver to simplify the system. */ + omega_simplify = 3 +}; + +/* Values used for labeling equations. Private (not used outside the + solver). */ +enum omega_eqn_color { + omega_black = 0, + omega_red = 1 +}; + +/* Structure for equations. */ +typedef struct eqn_d +{ + int key; + int touched; + enum omega_eqn_color color; + + /* Array of coefficients for the equation. The layout of the data + is as follows: coef[0] is the constant, coef[i] for 1 <= i <= + OMEGA_MAX_VARS, are the coefficients for each dimension. Examples: + the equation 0 = 9 + x + 0y + 5z is encoded as [9 1 0 5], the + inequality 0 <= -8 + x + 2y + 3z is encoded as [-8 1 2 3]. */ + int *coef; +} *eqn; + +typedef struct omega_pb_d +{ + /* The number of variables in the system of equations. */ + int num_vars; + + /* Safe variables are not eliminated during the Fourier-Motzkin + simplification of the system. Safe variables are all those + variables that are placed at the beginning of the array of + variables: PB->var[1, ..., SAFE_VARS]. PB->var[0] is not used, + as PB->eqs[x]->coef[0] represents the constant of the equation. */ + int safe_vars; + + /* Number of elements in eqs[]. */ + int num_eqs; + /* Number of elements in geqs[]. */ + int num_geqs; + /* Number of elements in subs[]. */ + int num_subs; + + int hash_version; + bool variables_initialized; + bool variables_freed; + + /* Index or name of variables. Negative integers are reserved for + wildcard variables. Maps the index of variables in the original + problem to the new index of the variable. The index for a + variable in the coef array of an equation can change as some + variables are eliminated. */ + int *var; + + int *forwarding_address; + + /* Inequalities in the system of constraints. */ + eqn geqs; + + /* Equations in the system of constraints. */ + eqn eqs; + + /* A map of substituted variables. */ + eqn subs; +} *omega_pb; + +extern void omega_initialize (void); +extern omega_pb omega_alloc_problem (int, int); +extern enum omega_result omega_solve_problem (omega_pb, enum omega_result); +extern enum omega_result omega_simplify_problem (omega_pb); +extern enum omega_result omega_simplify_approximate (omega_pb); +extern enum omega_result omega_constrain_variable_sign (omega_pb, + enum omega_eqn_color, + int, int); +extern void debug (omega_pb_d &ref); +extern void debug (omega_pb_d *ptr); +extern void debug_omega_problem (omega_pb); +extern void omega_print_problem (FILE *, omega_pb); +extern void omega_print_red_equations (FILE *, omega_pb); +extern int omega_count_red_equations (omega_pb); +extern void omega_pretty_print_problem (FILE *, omega_pb); +extern void omega_unprotect_variable (omega_pb, int var); +extern void omega_negate_geq (omega_pb, int); +extern void omega_convert_eq_to_geqs (omega_pb, int eq); +extern void omega_print_eqn (FILE *, omega_pb, eqn, bool, int); +extern bool omega_problem_has_red_equations (omega_pb); +extern enum omega_result omega_eliminate_redundant (omega_pb, bool); +extern void omega_eliminate_red (omega_pb, bool); +extern void omega_constrain_variable_value (omega_pb, enum omega_eqn_color, + int, int); +extern bool omega_query_variable (omega_pb, int, int *, int *); +extern int omega_query_variable_signs (omega_pb, int, int, int, int, + int, int, bool *, int *); +extern bool omega_query_variable_bounds (omega_pb, int, int *, int *); +extern void (*omega_when_reduced) (omega_pb); +extern void omega_no_procedure (omega_pb); + +/* Return true when variable I in problem PB is a wildcard. */ + +static inline bool +omega_wildcard_p (omega_pb pb, int i) +{ + return (pb->var[i] < 0); +} + +/* Return true when variable I in problem PB is a safe variable. */ + +static inline bool +omega_safe_var_p (omega_pb pb, int i) +{ + /* The constant of an equation is not a variable. */ + gcc_assert (0 < i); + return (i <= pb->safe_vars); +} + +/* Print to FILE equality E from PB. */ + +static inline void +omega_print_eq (FILE *file, omega_pb pb, eqn e) +{ + omega_print_eqn (file, pb, e, false, 0); +} + +/* Print to FILE inequality E from PB. */ + +static inline void +omega_print_geq (FILE *file, omega_pb pb, eqn e) +{ + omega_print_eqn (file, pb, e, true, 0); +} + +/* Print to FILE inequality E from PB. */ + +static inline void +omega_print_geq_extra (FILE *file, omega_pb pb, eqn e) +{ + omega_print_eqn (file, pb, e, true, 1); +} + +/* E1 = E2, make a copy of E2 into E1. Equations contain S variables. */ + +static inline void +omega_copy_eqn (eqn e1, eqn e2, int s) +{ + e1->key = e2->key; + e1->touched = e2->touched; + e1->color = e2->color; + + memcpy (e1->coef, e2->coef, (s + 1) * sizeof (int)); +} + +/* Initialize E = 0. Equation E contains S variables. */ + +static inline void +omega_init_eqn_zero (eqn e, int s) +{ + e->key = 0; + e->touched = 0; + e->color = omega_black; + + memset (e->coef, 0, (s + 1) * sizeof (int)); +} + +/* Allocate N equations with S variables. */ + +static inline eqn +omega_alloc_eqns (int s, int n) +{ + int i; + eqn res = (eqn) (xcalloc (n, sizeof (struct eqn_d))); + + for (i = n - 1; i >= 0; i--) + { + res[i].coef = (int *) (xcalloc (OMEGA_MAX_VARS + 1, sizeof (int))); + omega_init_eqn_zero (&res[i], s); + } + + return res; +} + +/* Free N equations from array EQ. */ + +static inline void +omega_free_eqns (eqn eq, int n) +{ + int i; + + for (i = n - 1; i >= 0; i--) + free (eq[i].coef); + + free (eq); +} + +/* Returns true when E is an inequality with a single variable. */ + +static inline bool +single_var_geq (eqn e, int nv ATTRIBUTE_UNUSED) +{ + return (e->key != 0 + && -OMEGA_MAX_VARS <= e->key && e->key <= OMEGA_MAX_VARS); +} + +/* Allocate a new equality with all coefficients 0, and tagged with + COLOR. Return the index of this equality in problem PB. */ + +static inline int +omega_add_zero_eq (omega_pb pb, enum omega_eqn_color color) +{ + int idx = pb->num_eqs++; + + gcc_assert (pb->num_eqs <= OMEGA_MAX_EQS); + omega_init_eqn_zero (&pb->eqs[idx], pb->num_vars); + pb->eqs[idx].color = color; + return idx; +} + +/* Allocate a new inequality with all coefficients 0, and tagged with + COLOR. Return the index of this inequality in problem PB. */ + +static inline int +omega_add_zero_geq (omega_pb pb, enum omega_eqn_color color) +{ + int idx = pb->num_geqs; + + pb->num_geqs++; + gcc_assert (pb->num_geqs <= OMEGA_MAX_GEQS); + omega_init_eqn_zero (&pb->geqs[idx], pb->num_vars); + pb->geqs[idx].touched = 1; + pb->geqs[idx].color = color; + return idx; +} + +/* Initialize variables for problem PB. */ + +static inline void +omega_initialize_variables (omega_pb pb) +{ + int i; + + for (i = pb->num_vars; i >= 0; i--) + pb->forwarding_address[i] = pb->var[i] = i; + + pb->variables_initialized = true; +} + +/* Free problem PB. */ + +static inline void +omega_free_problem (omega_pb pb) +{ + free (pb->var); + free (pb->forwarding_address); + omega_free_eqns (pb->geqs, OMEGA_MAX_GEQS); + omega_free_eqns (pb->eqs, OMEGA_MAX_EQS); + omega_free_eqns (pb->subs, OMEGA_MAX_VARS + 1); + free (pb); +} + +/* Copy omega problems: P1 = P2. */ + +static inline void +omega_copy_problem (omega_pb p1, omega_pb p2) +{ + int e, i; + + p1->num_vars = p2->num_vars; + p1->hash_version = p2->hash_version; + p1->variables_initialized = p2->variables_initialized; + p1->variables_freed = p2->variables_freed; + p1->safe_vars = p2->safe_vars; + p1->num_eqs = p2->num_eqs; + p1->num_subs = p2->num_subs; + p1->num_geqs = p2->num_geqs; + + for (e = p2->num_eqs - 1; e >= 0; e--) + omega_copy_eqn (&(p1->eqs[e]), &(p2->eqs[e]), p2->num_vars); + + for (e = p2->num_geqs - 1; e >= 0; e--) + omega_copy_eqn (&(p1->geqs[e]), &(p2->geqs[e]), p2->num_vars); + + for (e = p2->num_subs - 1; e >= 0; e--) + omega_copy_eqn (&(p1->subs[e]), &(p2->subs[e]), p2->num_vars); + + for (i = p2->num_vars; i >= 0; i--) + p1->var[i] = p2->var[i]; + + for (i = OMEGA_MAX_VARS; i >= 0; i--) + p1->forwarding_address[i] = p2->forwarding_address[i]; +} + +#endif /* GCC_OMEGA_H */ -- cgit v1.2.3