OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [gcc/] [omega.h] - Blame information for rev 684

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 684 jeremybenn
/* 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, 2009 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,
43
  omega_true = 1,
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.  */
50
  omega_simplify = 3
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;
65
  enum omega_eqn_color color;
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
 
94
  int hash_version;
95
  bool variables_initialized;
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;
104
 
105
  int *forwarding_address;
106
 
107
  /* Inequalities in the system of constraints.  */
108
  eqn geqs;
109
 
110
  /* Equations in the system of constraints.  */
111
  eqn eqs;
112
 
113
  /* A map of substituted variables.  */
114
  eqn subs;
115
} *omega_pb;
116
 
117
extern void omega_initialize (void);
118
extern omega_pb omega_alloc_problem (int, int);
119
extern enum omega_result omega_solve_problem (omega_pb, enum omega_result);
120
extern enum omega_result omega_simplify_problem (omega_pb);
121
extern enum omega_result omega_simplify_approximate (omega_pb);
122
extern enum omega_result omega_constrain_variable_sign (omega_pb,
123
                                                        enum omega_eqn_color,
124
                                                        int, int);
125
extern void debug_omega_problem (omega_pb);
126
extern void omega_print_problem (FILE *, omega_pb);
127
extern void omega_print_red_equations (FILE *, omega_pb);
128
extern int omega_count_red_equations (omega_pb);
129
extern void omega_pretty_print_problem (FILE *, omega_pb);
130
extern void omega_unprotect_variable (omega_pb, int var);
131
extern void omega_negate_geq (omega_pb, int);
132
extern void omega_convert_eq_to_geqs (omega_pb, int eq);
133
extern void omega_print_eqn (FILE *, omega_pb, eqn, bool, int);
134
extern bool omega_problem_has_red_equations (omega_pb);
135
extern enum omega_result omega_eliminate_redundant (omega_pb, bool);
136
extern void omega_eliminate_red (omega_pb, bool);
137
extern void omega_constrain_variable_value (omega_pb, enum omega_eqn_color,
138
                                            int, int);
139
extern bool omega_query_variable (omega_pb, int, int *, int *);
140
extern int omega_query_variable_signs (omega_pb, int, int, int, int,
141
                                       int, int, bool *, int *);
142
extern bool omega_query_variable_bounds (omega_pb, int, int *, int *);
143
extern void (*omega_when_reduced) (omega_pb);
144
extern void omega_no_procedure (omega_pb);
145
 
146
/* Return true when variable I in problem PB is a wildcard.  */
147
 
148
static inline bool
149
omega_wildcard_p (omega_pb pb, int i)
150
{
151
  return (pb->var[i] < 0);
152
}
153
 
154
/* Return true when variable I in problem PB is a safe variable.  */
155
 
156
static inline bool
157
omega_safe_var_p (omega_pb pb, int i)
158
{
159
  /* The constant of an equation is not a variable.  */
160
  gcc_assert (0 < i);
161
  return (i <= pb->safe_vars);
162
}
163
 
164
/* Print to FILE equality E from PB.  */
165
 
166
static inline void
167
omega_print_eq (FILE *file, omega_pb pb, eqn e)
168
{
169
  omega_print_eqn (file, pb, e, false, 0);
170
}
171
 
172
/* Print to FILE inequality E from PB.  */
173
 
174
static inline void
175
omega_print_geq (FILE *file, omega_pb pb, eqn e)
176
{
177
  omega_print_eqn (file, pb, e, true, 0);
178
}
179
 
180
/* Print to FILE inequality E from PB.  */
181
 
182
static inline void
183
omega_print_geq_extra (FILE *file, omega_pb pb, eqn e)
184
{
185
  omega_print_eqn (file, pb, e, true, 1);
186
}
187
 
188
/* E1 = E2, make a copy of E2 into E1.  Equations contain S variables.  */
189
 
190
static inline void
191
omega_copy_eqn (eqn e1, eqn e2, int s)
192
{
193
  e1->key = e2->key;
194
  e1->touched = e2->touched;
195
  e1->color = e2->color;
196
 
197
  memcpy (e1->coef, e2->coef, (s + 1) * sizeof (int));
198
}
199
 
200
/* Initialize E = 0.  Equation E contains S variables.  */
201
 
202
static inline void
203
omega_init_eqn_zero (eqn e, int s)
204
{
205
  e->key = 0;
206
  e->touched = 0;
207
  e->color = omega_black;
208
 
209
  memset (e->coef, 0, (s + 1) * sizeof (int));
210
}
211
 
212
/* Allocate N equations with S variables.  */
213
 
214
static inline eqn
215
omega_alloc_eqns (int s, int n)
216
{
217
  int i;
218
  eqn res = (eqn) (xcalloc (n, sizeof (struct eqn_d)));
219
 
220
  for (i = n - 1; i >= 0; i--)
221
    {
222
      res[i].coef = (int *) (xcalloc (OMEGA_MAX_VARS + 1, sizeof (int)));
223
      omega_init_eqn_zero (&res[i], s);
224
    }
225
 
226
  return res;
227
}
228
 
229
/* Free N equations from array EQ.  */
230
 
231
static inline void
232
omega_free_eqns (eqn eq, int n)
233
{
234
  int i;
235
 
236
  for (i = n - 1; i >= 0; i--)
237
    free (eq[i].coef);
238
 
239
  free (eq);
240
}
241
 
242
/* Returns true when E is an inequality with a single variable.  */
243
 
244
static inline bool
245
single_var_geq (eqn e, int nv ATTRIBUTE_UNUSED)
246
{
247
  return (e->key != 0
248
          && -OMEGA_MAX_VARS <= e->key && e->key <= OMEGA_MAX_VARS);
249
}
250
 
251
/* Allocate a new equality with all coefficients 0, and tagged with
252
   COLOR.  Return the index of this equality in problem PB.  */
253
 
254
static inline int
255
omega_add_zero_eq (omega_pb pb, enum omega_eqn_color color)
256
{
257
  int idx = pb->num_eqs++;
258
 
259
  gcc_assert (pb->num_eqs <= OMEGA_MAX_EQS);
260
  omega_init_eqn_zero (&pb->eqs[idx], pb->num_vars);
261
  pb->eqs[idx].color = color;
262
  return idx;
263
}
264
 
265
/* Allocate a new inequality with all coefficients 0, and tagged with
266
   COLOR.  Return the index of this inequality in problem PB.  */
267
 
268
static inline int
269
omega_add_zero_geq (omega_pb pb, enum omega_eqn_color color)
270
{
271
  int idx = pb->num_geqs;
272
 
273
  pb->num_geqs++;
274
  gcc_assert (pb->num_geqs <= OMEGA_MAX_GEQS);
275
  omega_init_eqn_zero (&pb->geqs[idx], pb->num_vars);
276
  pb->geqs[idx].touched = 1;
277
  pb->geqs[idx].color = color;
278
  return idx;
279
}
280
 
281
/* Initialize variables for problem PB.  */
282
 
283
static inline void
284
omega_initialize_variables (omega_pb pb)
285
{
286
  int i;
287
 
288
  for (i = pb->num_vars; i >= 0; i--)
289
    pb->forwarding_address[i] = pb->var[i] = i;
290
 
291
  pb->variables_initialized = true;
292
}
293
 
294
/* Free problem PB.  */
295
 
296
static inline void
297
omega_free_problem (omega_pb pb)
298
{
299
  free (pb->var);
300
  free (pb->forwarding_address);
301
  omega_free_eqns (pb->geqs, OMEGA_MAX_GEQS);
302
  omega_free_eqns (pb->eqs, OMEGA_MAX_EQS);
303
  omega_free_eqns (pb->subs, OMEGA_MAX_VARS + 1);
304
  free (pb);
305
}
306
 
307
/* Copy omega problems: P1 = P2.  */
308
 
309
static inline void
310
omega_copy_problem (omega_pb p1, omega_pb p2)
311
{
312
  int e, i;
313
 
314
  p1->num_vars = p2->num_vars;
315
  p1->hash_version = p2->hash_version;
316
  p1->variables_initialized = p2->variables_initialized;
317
  p1->variables_freed = p2->variables_freed;
318
  p1->safe_vars = p2->safe_vars;
319
  p1->num_eqs = p2->num_eqs;
320
  p1->num_subs = p2->num_subs;
321
  p1->num_geqs = p2->num_geqs;
322
 
323
  for (e = p2->num_eqs - 1; e >= 0; e--)
324
    omega_copy_eqn (&(p1->eqs[e]), &(p2->eqs[e]), p2->num_vars);
325
 
326
  for (e = p2->num_geqs - 1; e >= 0; e--)
327
    omega_copy_eqn (&(p1->geqs[e]), &(p2->geqs[e]), p2->num_vars);
328
 
329
  for (e = p2->num_subs - 1; e >= 0; e--)
330
    omega_copy_eqn (&(p1->subs[e]), &(p2->subs[e]), p2->num_vars);
331
 
332
  for (i = p2->num_vars; i >= 0; i--)
333
    p1->var[i] = p2->var[i];
334
 
335
  for (i = OMEGA_MAX_VARS; i >= 0; i--)
336
    p1->forwarding_address[i] = p2->forwarding_address[i];
337
}
338
 
339
#endif /* GCC_OMEGA_H */

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.