Mercurial > hg > CbC > CbC_gcc
annotate gcc/omega.h @ 55:77e2b8dfacca gcc-4.4.5
update it from 4.4.3 to 4.5.0
| author | ryoma <e075725@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Fri, 12 Feb 2010 23:39:51 +0900 |
| parents | a06113de4d67 |
| children |
| rev | line source |
|---|---|
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
1 /* Source code for an implementation of the Omega test, an integer |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
2 programming algorithm for dependence analysis, by William Pugh, |
| 0 | 3 appeared in Supercomputing '91 and CACM Aug 92. |
| 4 | |
| 5 This code has no license restrictions, and is considered public | |
| 6 domain. | |
| 7 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
8 Changes copyright (C) 2005, 2006, 2007, 2009 Free Software Foundation, Inc. |
| 0 | 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
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
55 enum omega_eqn_color { |
| 0 | 56 omega_black = 0, |
| 57 omega_red = 1 | |
| 58 }; | |
| 59 | |
| 60 /* Structure for equations. */ | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
61 typedef struct eqn_d |
| 0 | 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 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
75 typedef struct omega_pb_d |
| 0 | 76 { |
| 77 /* The number of variables in the system of equations. */ | |
| 78 int num_vars; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
79 |
| 0 | 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; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
218 eqn res = (eqn) (xcalloc (n, sizeof (struct eqn_d))); |
| 0 | 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 */ |