GCC Middle and Back End API Reference
omega.h
Go to the documentation of this file.
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-2013 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 3, 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 COPYING3. If not see
25 <http://www.gnu.org/licenses/>. */
26 
27 #include "config.h"
28 #include "params.h"
29 
30 #ifndef GCC_OMEGA_H
31 #define GCC_OMEGA_H
32 
33 #define OMEGA_MAX_VARS PARAM_VALUE (PARAM_OMEGA_MAX_VARS)
34 #define OMEGA_MAX_GEQS PARAM_VALUE (PARAM_OMEGA_MAX_GEQS)
35 #define OMEGA_MAX_EQS PARAM_VALUE (PARAM_OMEGA_MAX_EQS)
36 
37 #define pos_infinity (0x7ffffff)
38 #define neg_infinity (-0x7ffffff)
39 
40 /* Results of the Omega solver. */
41 enum omega_result {
42  omega_false = 0,
44 
45  /* Value returned when the solver is unable to determine an
46  answer. */
47  omega_unknown = 2,
48 
49  /* Value used for asking the solver to simplify the system. */
51 };
52 
53 /* Values used for labeling equations. Private (not used outside the
54  solver). */
55 enum omega_eqn_color {
56  omega_black = 0,
57  omega_red = 1
58 };
59 
60 /* Structure for equations. */
61 typedef struct eqn_d
62 {
63  int key;
64  int touched;
66 
67  /* Array of coefficients for the equation. The layout of the data
68  is as follows: coef[0] is the constant, coef[i] for 1 <= i <=
69  OMEGA_MAX_VARS, are the coefficients for each dimension. Examples:
70  the equation 0 = 9 + x + 0y + 5z is encoded as [9 1 0 5], the
71  inequality 0 <= -8 + x + 2y + 3z is encoded as [-8 1 2 3]. */
72  int *coef;
73 } *eqn;
74 
75 typedef struct omega_pb_d
76 {
77  /* The number of variables in the system of equations. */
78  int num_vars;
79 
80  /* Safe variables are not eliminated during the Fourier-Motzkin
81  simplification of the system. Safe variables are all those
82  variables that are placed at the beginning of the array of
83  variables: PB->var[1, ..., SAFE_VARS]. PB->var[0] is not used,
84  as PB->eqs[x]->coef[0] represents the constant of the equation. */
85  int safe_vars;
86 
87  /* Number of elements in eqs[]. */
88  int num_eqs;
89  /* Number of elements in geqs[]. */
90  int num_geqs;
91  /* Number of elements in subs[]. */
92  int num_subs;
93 
96  bool variables_freed;
97 
98  /* Index or name of variables. Negative integers are reserved for
99  wildcard variables. Maps the index of variables in the original
100  problem to the new index of the variable. The index for a
101  variable in the coef array of an equation can change as some
102  variables are eliminated. */
103  int *var;
105  int *forwarding_address;
107  /* Inequalities in the system of constraints. */
109 
110  /* Equations in the system of constraints. */
111  eqn eqs;
112 
113  /* A map of substituted variables. */
114  eqn subs;
115 } *omega_pb;
117 extern void omega_initialize (void);
118 extern omega_pb omega_alloc_problem (int, int);
123  enum omega_eqn_color,
124  int, int);
125 extern void debug (omega_pb_d &ref);
126 extern void debug (omega_pb_d *ptr);
127 extern void debug_omega_problem (omega_pb);
128 extern void omega_print_problem (FILE *, omega_pb);
129 extern void omega_print_red_equations (FILE *, omega_pb);
131 extern void omega_pretty_print_problem (FILE *, omega_pb);
132 extern void omega_unprotect_variable (omega_pb, int var);
133 extern void omega_negate_geq (omega_pb, int);
134 extern void omega_convert_eq_to_geqs (omega_pb, int eq);
135 extern void omega_print_eqn (FILE *, omega_pb, eqn, bool, int);
138 extern void omega_eliminate_red (omega_pb, bool);
140  int, int);
141 extern bool omega_query_variable (omega_pb, int, int *, int *);
142 extern int omega_query_variable_signs (omega_pb, int, int, int, int,
143  int, int, bool *, int *);
144 extern bool omega_query_variable_bounds (omega_pb, int, int *, int *);
145 extern void (*omega_when_reduced) (omega_pb);
146 extern void omega_no_procedure (omega_pb);
147 
148 /* Return true when variable I in problem PB is a wildcard. */
149 
150 static inline bool
151 omega_wildcard_p (omega_pb pb, int i)
152 {
153  return (pb->var[i] < 0);
154 }
155 
156 /* Return true when variable I in problem PB is a safe variable. */
157 
158 static inline bool
159 omega_safe_var_p (omega_pb pb, int i)
160 {
161  /* The constant of an equation is not a variable. */
162  gcc_assert (0 < i);
163  return (i <= pb->safe_vars);
164 }
165 
166 /* Print to FILE equality E from PB. */
167 
168 static inline void
169 omega_print_eq (FILE *file, omega_pb pb, eqn e)
170 {
171  omega_print_eqn (file, pb, e, false, 0);
172 }
173 
174 /* Print to FILE inequality E from PB. */
175 
176 static inline void
178 {
179  omega_print_eqn (file, pb, e, true, 0);
180 }
181 
182 /* Print to FILE inequality E from PB. */
183 
184 static inline void
185 omega_print_geq_extra (FILE *file, omega_pb pb, eqn e)
186 {
187  omega_print_eqn (file, pb, e, true, 1);
188 }
190 /* E1 = E2, make a copy of E2 into E1. Equations contain S variables. */
191 
192 static inline void
193 omega_copy_eqn (eqn e1, eqn e2, int s)
194 {
195  e1->key = e2->key;
196  e1->touched = e2->touched;
197  e1->color = e2->color;
199  memcpy (e1->coef, e2->coef, (s + 1) * sizeof (int));
200 }
201 
202 /* Initialize E = 0. Equation E contains S variables. */
203 
204 static inline void
205 omega_init_eqn_zero (eqn e, int s)
206 {
207  e->key = 0;
208  e->touched = 0;
209  e->color = omega_black;
210 
211  memset (e->coef, 0, (s + 1) * sizeof (int));
212 }
213 
214 /* Allocate N equations with S variables. */
215 
216 static inline eqn
217 omega_alloc_eqns (int s, int n)
218 {
219  int i;
220  eqn res = (eqn) (xcalloc (n, sizeof (struct eqn_d)));
221 
222  for (i = n - 1; i >= 0; i--)
223  {
224  res[i].coef = (int *) (xcalloc (OMEGA_MAX_VARS + 1, sizeof (int)));
225  omega_init_eqn_zero (&res[i], s);
226  }
227 
228  return res;
229 }
230 
231 /* Free N equations from array EQ. */
232 
233 static inline void
234 omega_free_eqns (eqn eq, int n)
235 {
236  int i;
237 
238  for (i = n - 1; i >= 0; i--)
239  free (eq[i].coef);
240 
241  free (eq);
242 }
243 
244 /* Returns true when E is an inequality with a single variable. */
245 
246 static inline bool
247 single_var_geq (eqn e, int nv ATTRIBUTE_UNUSED)
248 {
249  return (e->key != 0
250  && -OMEGA_MAX_VARS <= e->key && e->key <= OMEGA_MAX_VARS);
251 }
252 
253 /* Allocate a new equality with all coefficients 0, and tagged with
254  COLOR. Return the index of this equality in problem PB. */
255 
256 static inline int
258 {
259  int idx = pb->num_eqs++;
262  omega_init_eqn_zero (&pb->eqs[idx], pb->num_vars);
263  pb->eqs[idx].color = color;
264  return idx;
265 }
266 
267 /* Allocate a new inequality with all coefficients 0, and tagged with
268  COLOR. Return the index of this inequality in problem PB. */
269 
270 static inline int
272 {
273  int idx = pb->num_geqs;
275  pb->num_geqs++;
277  omega_init_eqn_zero (&pb->geqs[idx], pb->num_vars);
278  pb->geqs[idx].touched = 1;
279  pb->geqs[idx].color = color;
280  return idx;
281 }
282 
283 /* Initialize variables for problem PB. */
284 
285 static inline void
287 {
288  int i;
289 
290  for (i = pb->num_vars; i >= 0; i--)
291  pb->forwarding_address[i] = pb->var[i] = i;
292 
293  pb->variables_initialized = true;
294 }
295 
296 /* Free problem PB. */
297 
298 static inline void
300 {
301  free (pb->var);
302  free (pb->forwarding_address);
306  free (pb);
307 }
308 
309 /* Copy omega problems: P1 = P2. */
310 
311 static inline void
313 {
314  int e, i;
315 
316  p1->num_vars = p2->num_vars;
317  p1->hash_version = p2->hash_version;
320  p1->safe_vars = p2->safe_vars;
321  p1->num_eqs = p2->num_eqs;
322  p1->num_subs = p2->num_subs;
323  p1->num_geqs = p2->num_geqs;
324 
325  for (e = p2->num_eqs - 1; e >= 0; e--)
326  omega_copy_eqn (&(p1->eqs[e]), &(p2->eqs[e]), p2->num_vars);
327 
328  for (e = p2->num_geqs - 1; e >= 0; e--)
329  omega_copy_eqn (&(p1->geqs[e]), &(p2->geqs[e]), p2->num_vars);
331  for (e = p2->num_subs - 1; e >= 0; e--)
332  omega_copy_eqn (&(p1->subs[e]), &(p2->subs[e]), p2->num_vars);
333 
334  for (i = p2->num_vars; i >= 0; i--)
335  p1->var[i] = p2->var[i];
336 
337  for (i = OMEGA_MAX_VARS; i >= 0; i--)
338  p1->forwarding_address[i] = p2->forwarding_address[i];
339 }
340 
341 #endif /* GCC_OMEGA_H */