gcc/omega.h

   1 /* Source code for an implementation of the Omega test, an integer
   2    programming algorithm for dependence analysis, by William Pugh,
   3    appeared in Supercomputing '91 and CACM Aug 92.
   4
   5    This code has no license restrictions, and is considered public
   6    domain.
   7
   8    Changes copyright (C) 2005, 2006, 2007 Free Software Foundation, Inc.
   9    Contributed by Sebastian Pop <sebastian.pop@inria.fr>
  10
  11 This file is part of GCC.
  12
  13 GCC is free software; you can redistribute it and/or modify it under
  14 the terms of the GNU General Public License as published by the Free
  15 Software Foundation; either version 2, or (at your option) any later
  16 version.
  17
  18 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  19 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  20 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  21 for more details.
  22
  23 You should have received a copy of the GNU General Public License
  24 along with GCC; see the file COPYING.  If not, write to the Free
  25 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  26 02111-1307, USA.  */
  27
  28 #include "config.h"
  29 #include "params.h"
  30
  31 #ifndef GCC_OMEGA_H
  32 #define GCC_OMEGA_H
  33
  34 #define OMEGA_MAX_VARS PARAM_VALUE (PARAM_OMEGA_MAX_VARS)
  35 #define OMEGA_MAX_GEQS PARAM_VALUE (PARAM_OMEGA_MAX_GEQS)
  36 #define OMEGA_MAX_EQS PARAM_VALUE (PARAM_OMEGA_MAX_EQS)
  37
  38 #define pos_infinity (0x7ffffff)
  39 #define neg_infinity (-0x7ffffff)
  40
  41 /* Results of the Omega solver.  */
  42 enum omega_result {
  43   omega_false = 0,
  44   omega_true = 1,
  45
  46   /* Value returned when the solver is unable to determine an
  47      answer.  */
  48   omega_unknown = 2,
  49
  50   /* Value used for asking the solver to simplify the system.  */
  51   omega_simplify = 3
  52 };
  53
  54 /* Values used for labeling equations.  Private (not used outside the
  55    solver).  */
  56 enum omega_eqn_color {
  57   omega_black = 0,
  58   omega_red = 1
  59 };
  60
  61 /* Structure for equations.  */
  62 typedef struct eqn
  63 {
  64   int key;
  65   int touched;
  66   enum omega_eqn_color color;
  67
  68   /* Array of coefficients for the equation.  The layout of the data
  69      is as follows: coef[0] is the constant, coef[i] for 1 <= i <=
  70      OMEGA_MAX_VARS, are the coefficients for each dimension.  Examples:
  71      the equation 0 = 9 + x + 0y + 5z is encoded as [9 1 0 5], the
  72      inequality 0 <= -8 + x + 2y + 3z is encoded as [-8 1 2 3].  */
  73   int *coef;
  74 } *eqn;
  75
  76 typedef struct omega_pb
  77 {
  78   /* The number of variables in the system of equations.  */
  79   int num_vars;
  80
  81   /* Safe variables are not eliminated during the Fourier-Motzkin
  82      simplification of the system.  Safe variables are all those
  83      variables that are placed at the beginning of the array of
  84      variables: PB->var[1, ..., SAFE_VARS].  PB->var[0] is not used,
  85      as PB->eqs[x]->coef[0] represents the constant of the equation.  */
  86   int safe_vars;
  87
  88   /* Number of elements in eqs[].  */
  89   int num_eqs;
  90   /* Number of elements in geqs[].  */
  91   int num_geqs;
  92   /* Number of elements in subs[].  */
  93   int num_subs;
  94
  95   int hash_version;
  96   bool variables_initialized;
  97   bool variables_freed;
  98
  99   /* Index or name of variables.  Negative integers are reserved for
 100      wildcard variables.  Maps the index of variables in the original
 101      problem to the new index of the variable.  The index for a
 102      variable in the coef array of an equation can change as some
 103      variables are eliminated.  */
 104   int *var;
 105
 106   int *forwarding_address;
 107
 108   /* Inequalities in the system of constraints.  */
 109   eqn geqs;
 110
 111   /* Equations in the system of constraints.  */
 112   eqn eqs;
 113
 114   /* A map of substituted variables.  */
 115   eqn subs;
 116 } *omega_pb;
 117
 118 extern void omega_initialize (void);
 119 extern omega_pb omega_alloc_problem (int, int);
 120 extern enum omega_result omega_solve_problem (omega_pb, enum omega_result);
 121 extern enum omega_result omega_simplify_problem (omega_pb);
 122 extern enum omega_result omega_simplify_approximate (omega_pb);
 123 extern enum omega_result omega_constrain_variable_sign (omega_pb,
 124                                                         enum omega_eqn_color,
 125                                                         int, int);
 126 extern void debug_omega_problem (omega_pb);
 127 extern void omega_print_problem (FILE *, omega_pb);
 128 extern void omega_print_red_equations (FILE *, omega_pb);
 129 extern int omega_count_red_equations (omega_pb);
 130 extern void omega_pretty_print_problem (FILE *, omega_pb);
 131 extern void omega_unprotect_variable (omega_pb, int var);
 132 extern void omega_negate_geq (omega_pb, int);
 133 extern void omega_convert_eq_to_geqs (omega_pb, int eq);
 134 extern void omega_print_eqn (FILE *, omega_pb, eqn, bool, int);
 135 extern bool omega_problem_has_red_equations (omega_pb);
 136 extern enum omega_result omega_eliminate_redundant (omega_pb, bool);
 137 extern void omega_eliminate_red (omega_pb, bool);
 138 extern void omega_constrain_variable_value (omega_pb, enum omega_eqn_color,
 139                                             int, int);
 140 extern bool omega_query_variable (omega_pb, int, int *, int *);
 141 extern int omega_query_variable_signs (omega_pb, int, int, int, int,
 142                                        int, int, bool *, int *);
 143 extern bool omega_query_variable_bounds (omega_pb, int, int *, int *);
 144 extern void (*omega_when_reduced) (omega_pb);
 145 extern void omega_no_procedure (omega_pb);
 146
 147 /* Return true when variable I in problem PB is a wildcard.  */
 148
 149 static inline bool
 150 omega_wildcard_p (omega_pb pb, int i)
 151 {
 152   return (pb->var[i] < 0);
 153 }
 154
 155 /* Return true when variable I in problem PB is a safe variable.  */
 156
 157 static inline bool
 158 omega_safe_var_p (omega_pb pb, int i)
 159 {
 160   /* The constant of an equation is not a variable.  */
 161   gcc_assert (0 < i);
 162   return (i <= pb->safe_vars);
 163 }
 164
 165 /* Print to FILE equality E from PB.  */
 166
 167 static inline void
 168 omega_print_eq (FILE *file, omega_pb pb, eqn e)
 169 {
 170   omega_print_eqn (file, pb, e, false, 0);
 171 }
 172
 173 /* Print to FILE inequality E from PB.  */
 174
 175 static inline void
 176 omega_print_geq (FILE *file, omega_pb pb, eqn e)
 177 {
 178   omega_print_eqn (file, pb, e, true, 0);
 179 }
 180
 181 /* Print to FILE inequality E from PB.  */
 182
 183 static inline void
 184 omega_print_geq_extra (FILE *file, omega_pb pb, eqn e)
 185 {
 186   omega_print_eqn (file, pb, e, true, 1);
 187 }
 188
 189 /* E1 = E2, make a copy of E2 into E1.  Equations contain S variables.  */
 190
 191 static inline void
 192 omega_copy_eqn (eqn e1, eqn e2, int s)
 193 {
 194   e1->key = e2->key;
 195   e1->touched = e2->touched;
 196   e1->color = e2->color;
 197
 198   memcpy (e1->coef, e2->coef, (s + 1) * sizeof (int));
 199 }
 200
 201 /* Initialize E = 0.  Equation E contains S variables.  */
 202
 203 static inline void
 204 omega_init_eqn_zero (eqn e, int s)
 205 {
 206   e->key = 0;
 207   e->touched = 0;
 208   e->color = omega_black;
 209
 210   memset (e->coef, 0, (s + 1) * sizeof (int));
 211 }
 212
 213 /* Allocate N equations with S variables.  */
 214
 215 static inline eqn
 216 omega_alloc_eqns (int s, int n)
 217 {
 218   int i;
 219   eqn res = (eqn) (xcalloc (n, sizeof (struct eqn)));
 220
 221   for (i = n - 1; i >= 0; i--)
 222     {
 223       res[i].coef = (int *) (xcalloc (OMEGA_MAX_VARS + 1, sizeof (int)));
 224       omega_init_eqn_zero (&res[i], s);
 225     }
 226
 227   return res;
 228 }
 229
 230 /* Free N equations from array EQ.  */
 231
 232 static inline void
 233 omega_free_eqns (eqn eq, int n)
 234 {
 235   int i;
 236
 237   for (i = n - 1; i >= 0; i--)
 238     free (eq[i].coef);
 239
 240   free (eq);
 241 }
 242
 243 /* Returns true when E is an inequality with a single variable.  */
 244
 245 static inline bool
 246 single_var_geq (eqn e, int nv ATTRIBUTE_UNUSED)
 247 {
 248   return (e->key != 0
 249           && -OMEGA_MAX_VARS <= e->key && e->key <= OMEGA_MAX_VARS);
 250 }
 251
 252 /* Allocate a new equality with all coefficients 0, and tagged with
 253    COLOR.  Return the index of this equality in problem PB.  */
 254
 255 static inline int
 256 omega_add_zero_eq (omega_pb pb, enum omega_eqn_color color)
 257 {
 258   int idx = pb->num_eqs++;
 259
 260   gcc_assert (pb->num_eqs <= OMEGA_MAX_EQS);
 261   omega_init_eqn_zero (&pb->eqs[idx], pb->num_vars);
 262   pb->eqs[idx].color = color;
 263   return idx;
 264 }
 265
 266 /* Allocate a new inequality with all coefficients 0, and tagged with
 267    COLOR.  Return the index of this inequality in problem PB.  */
 268
 269 static inline int
 270 omega_add_zero_geq (omega_pb pb, enum omega_eqn_color color)
 271 {
 272   int idx = pb->num_geqs;
 273
 274   pb->num_geqs++;
 275   gcc_assert (pb->num_geqs <= OMEGA_MAX_GEQS);
 276   omega_init_eqn_zero (&pb->geqs[idx], pb->num_vars);
 277   pb->geqs[idx].touched = 1;
 278   pb->geqs[idx].color = color;
 279   return idx;
 280 }
 281
 282 /* Initialize variables for problem PB.  */
 283
 284 static inline void
 285 omega_initialize_variables (omega_pb pb)
 286 {
 287   int i;
 288
 289   for (i = pb->num_vars; i >= 0; i--)
 290     pb->forwarding_address[i] = pb->var[i] = i;
 291
 292   pb->variables_initialized = true;
 293 }
 294
 295 /* Free problem PB.  */
 296
 297 static inline void
 298 omega_free_problem (omega_pb pb)
 299 {
 300   free (pb->var);
 301   free (pb->forwarding_address);
 302   omega_free_eqns (pb->geqs, OMEGA_MAX_GEQS);
 303   omega_free_eqns (pb->eqs, OMEGA_MAX_EQS);
 304   omega_free_eqns (pb->subs, OMEGA_MAX_VARS + 1);
 305   free (pb);
 306 }
 307
 308 /* Copy omega problems: P1 = P2.  */
 309
 310 static inline void
 311 omega_copy_problem (omega_pb p1, omega_pb p2)
 312 {
 313   int e, i;
 314
 315   p1->num_vars = p2->num_vars;
 316   p1->hash_version = p2->hash_version;
 317   p1->variables_initialized = p2->variables_initialized;
 318   p1->variables_freed = p2->variables_freed;
 319   p1->safe_vars = p2->safe_vars;
 320   p1->num_eqs = p2->num_eqs;
 321   p1->num_subs = p2->num_subs;
 322   p1->num_geqs = p2->num_geqs;
 323
 324   for (e = p2->num_eqs - 1; e >= 0; e--)
 325     omega_copy_eqn (&(p1->eqs[e]), &(p2->eqs[e]), p2->num_vars);
 326
 327   for (e = p2->num_geqs - 1; e >= 0; e--)
 328     omega_copy_eqn (&(p1->geqs[e]), &(p2->geqs[e]), p2->num_vars);
 329
 330   for (e = p2->num_subs - 1; e >= 0; e--)
 331     omega_copy_eqn (&(p1->subs[e]), &(p2->subs[e]), p2->num_vars);
 332
 333   for (i = p2->num_vars; i >= 0; i--)
 334     p1->var[i] = p2->var[i];
 335
 336   for (i = OMEGA_MAX_VARS; i >= 0; i--)
 337     p1->forwarding_address[i] = p2->forwarding_address[i];
 338 }
 339
 340 #endif /* GCC_OMEGA_H */