Mercurial > hg > sv-dependency-builds

annotate src/fftw-3.3.5/kernel/planner.c @ 83:ae30d91d2ffe

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Replace these with versions built using an older toolset (so as to avoid ABI compatibilities when linking on Ubuntu 14.04 for packaging purposes)
author Chris Cannam
date Fri, 07 Feb 2020 11:51:13 +0000
parents 2cd0e3b3e1fd
children
rev   line source
Chris@42 1 /*
Chris@42 2 * Copyright (c) 2000 Matteo Frigo
Chris@42 3 * Copyright (c) 2000 Massachusetts Institute of Technology
Chris@42 4 *
Chris@42 5 * This program is free software; you can redistribute it and/or modify
Chris@42 6 * it under the terms of the GNU General Public License as published by
Chris@42 7 * the Free Software Foundation; either version 2 of the License, or
Chris@42 8 * (at your option) any later version.
Chris@42 9 *
Chris@42 10 * This program is distributed in the hope that it will be useful,
Chris@42 11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
Chris@42 12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
Chris@42 13 * GNU General Public License for more details.
Chris@42 14 *
Chris@42 15 * You should have received a copy of the GNU General Public License
Chris@42 16 * along with this program; if not, write to the Free Software
Chris@42 17 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
Chris@42 18 *
Chris@42 19 */
Chris@42 20
Chris@42 21 #include "ifftw.h"
Chris@42 22 #include <string.h>
Chris@42 23
Chris@42 24 /* GNU Coding Standards, Sec. 5.2: "Please write the comments in a GNU
Chris@42 25 program in English, because English is the one language that nearly
Chris@42 26 all programmers in all countries can read."
Chris@42 27
Chris@42 28 ingemisco tanquam reus
Chris@42 29 culpa rubet vultus meus
Chris@42 30 supplicanti parce [rms]
Chris@42 31 */
Chris@42 32
Chris@42 33 #define VALIDP(solution) ((solution)->flags.hash_info & H_VALID)
Chris@42 34 #define LIVEP(solution) ((solution)->flags.hash_info & H_LIVE)
Chris@42 35 #define SLVNDX(solution) ((solution)->flags.slvndx)
Chris@42 36 #define BLISS(flags) (((flags).hash_info) & BLESSING)
Chris@42 37 #define INFEASIBLE_SLVNDX ((1U<<BITS_FOR_SLVNDX)-1)
Chris@42 38
Chris@42 39
Chris@42 40 #define MAXNAM 64 /* maximum length of registrar's name.
Chris@42 41 Used for reading wisdom. There is no point
Chris@42 42 in doing this right */
Chris@42 43
Chris@42 44
Chris@42 45 #ifdef FFTW_DEBUG
Chris@42 46 static void check(hashtab *ht);
Chris@42 47 #endif
Chris@42 48
Chris@42 49 /* x <= y */
Chris@42 50 #define LEQ(x, y) (((x) & (y)) == (x))
Chris@42 51
Chris@42 52 /* A subsumes B */
Chris@42 53 static int subsumes(const flags_t *a, unsigned slvndx_a, const flags_t *b)
Chris@42 54 {
Chris@42 55 if (slvndx_a != INFEASIBLE_SLVNDX) {
Chris@42 56 A(a->timelimit_impatience == 0);
Chris@42 57 return (LEQ(a->u, b->u) && LEQ(b->l, a->l));
Chris@42 58 } else {
Chris@42 59 return (LEQ(a->l, b->l)
Chris@42 60 && a->timelimit_impatience <= b->timelimit_impatience);
Chris@42 61 }
Chris@42 62 }
Chris@42 63
Chris@42 64 static unsigned addmod(unsigned a, unsigned b, unsigned p)
Chris@42 65 {
Chris@42 66 /* gcc-2.95/sparc produces incorrect code for the fast version below. */
Chris@42 67 #if defined(__sparc__) && defined(__GNUC__)
Chris@42 68 /* slow version */
Chris@42 69 return (a + b) % p;
Chris@42 70 #else
Chris@42 71 /* faster version */
Chris@42 72 unsigned c = a + b;
Chris@42 73 return c >= p ? c - p : c;
Chris@42 74 #endif
Chris@42 75 }
Chris@42 76
Chris@42 77 /*
Chris@42 78 slvdesc management:
Chris@42 79 */
Chris@42 80 static void sgrow(planner *ego)
Chris@42 81 {
Chris@42 82 unsigned osiz = ego->slvdescsiz, nsiz = 1 + osiz + osiz / 4;
Chris@42 83 slvdesc *ntab = (slvdesc *)MALLOC(nsiz * sizeof(slvdesc), SLVDESCS);
Chris@42 84 slvdesc *otab = ego->slvdescs;
Chris@42 85 unsigned i;
Chris@42 86
Chris@42 87 ego->slvdescs = ntab;
Chris@42 88 ego->slvdescsiz = nsiz;
Chris@42 89 for (i = 0; i < osiz; ++i)
Chris@42 90 ntab[i] = otab[i];
Chris@42 91 X(ifree0)(otab);
Chris@42 92 }
Chris@42 93
Chris@42 94 static void register_solver(planner *ego, solver *s)
Chris@42 95 {
Chris@42 96 slvdesc *n;
Chris@42 97 int kind;
Chris@42 98
Chris@42 99 if (s) { /* add s to solver list */
Chris@42 100 X(solver_use)(s);
Chris@42 101
Chris@42 102 A(ego->nslvdesc < INFEASIBLE_SLVNDX);
Chris@42 103 if (ego->nslvdesc >= ego->slvdescsiz)
Chris@42 104 sgrow(ego);
Chris@42 105
Chris@42 106 n = ego->slvdescs + ego->nslvdesc;
Chris@42 107
Chris@42 108 n->slv = s;
Chris@42 109 n->reg_nam = ego->cur_reg_nam;
Chris@42 110 n->reg_id = ego->cur_reg_id++;
Chris@42 111
Chris@42 112 A(strlen(n->reg_nam) < MAXNAM);
Chris@42 113 n->nam_hash = X(hash)(n->reg_nam);
Chris@42 114
Chris@42 115 kind = s->adt->problem_kind;
Chris@42 116 n->next_for_same_problem_kind = ego->slvdescs_for_problem_kind[kind];
Chris@42 117 ego->slvdescs_for_problem_kind[kind] = (int)/*from unsigned*/ego->nslvdesc;
Chris@42 118
Chris@42 119 ego->nslvdesc++;
Chris@42 120 }
Chris@42 121 }
Chris@42 122
Chris@42 123 static unsigned slookup(planner *ego, char *nam, int id)
Chris@42 124 {
Chris@42 125 unsigned h = X(hash)(nam); /* used to avoid strcmp in the common case */
Chris@42 126 FORALL_SOLVERS(ego, s, sp, {
Chris@42 127 UNUSED(s);
Chris@42 128 if (sp->reg_id == id && sp->nam_hash == h
Chris@42 129 && !strcmp(sp->reg_nam, nam))
Chris@42 130 return (unsigned)/*from ptrdiff_t*/(sp - ego->slvdescs);
Chris@42 131 });
Chris@42 132 return INFEASIBLE_SLVNDX;
Chris@42 133 }
Chris@42 134
Chris@42 135 /* Compute a MD5 hash of the configuration of the planner.
Chris@42 136 We store it into the wisdom file to make absolutely sure that
Chris@42 137 we are reading wisdom that is applicable */
Chris@42 138 static void signature_of_configuration(md5 *m, planner *ego)
Chris@42 139 {
Chris@42 140 X(md5begin)(m);
Chris@42 141 X(md5unsigned)(m, sizeof(R)); /* so we don't mix different precisions */
Chris@42 142 FORALL_SOLVERS(ego, s, sp, {
Chris@42 143 UNUSED(s);
Chris@42 144 X(md5int)(m, sp->reg_id);
Chris@42 145 X(md5puts)(m, sp->reg_nam);
Chris@42 146 });
Chris@42 147 X(md5end)(m);
Chris@42 148 }
Chris@42 149
Chris@42 150 /*
Chris@42 151 md5-related stuff:
Chris@42 152 */
Chris@42 153
Chris@42 154 /* first hash function */
Chris@42 155 static unsigned h1(const hashtab *ht, const md5sig s)
Chris@42 156 {
Chris@42 157 unsigned h = s[0] % ht->hashsiz;
Chris@42 158 A(h == (s[0] % ht->hashsiz));
Chris@42 159 return h;
Chris@42 160 }
Chris@42 161
Chris@42 162 /* second hash function (for double hashing) */
Chris@42 163 static unsigned h2(const hashtab *ht, const md5sig s)
Chris@42 164 {
Chris@42 165 unsigned h = 1U + s[1] % (ht->hashsiz - 1);
Chris@42 166 A(h == (1U + s[1] % (ht->hashsiz - 1)));
Chris@42 167 return h;
Chris@42 168 }
Chris@42 169
Chris@42 170 static void md5hash(md5 *m, const problem *p, const planner *plnr)
Chris@42 171 {
Chris@42 172 X(md5begin)(m);
Chris@42 173 X(md5unsigned)(m, sizeof(R)); /* so we don't mix different precisions */
Chris@42 174 X(md5int)(m, plnr->nthr);
Chris@42 175 p->adt->hash(p, m);
Chris@42 176 X(md5end)(m);
Chris@42 177 }
Chris@42 178
Chris@42 179 static int md5eq(const md5sig a, const md5sig b)
Chris@42 180 {
Chris@42 181 return a[0] == b[0] && a[1] == b[1] && a[2] == b[2] && a[3] == b[3];
Chris@42 182 }
Chris@42 183
Chris@42 184 static void sigcpy(const md5sig a, md5sig b)
Chris@42 185 {
Chris@42 186 b[0] = a[0]; b[1] = a[1]; b[2] = a[2]; b[3] = a[3];
Chris@42 187 }
Chris@42 188
Chris@42 189 /*
Chris@42 190 memoization routines :
Chris@42 191 */
Chris@42 192
Chris@42 193 /*
Chris@42 194 liber scriptus proferetur
Chris@42 195 in quo totum continetur
Chris@42 196 unde mundus iudicetur
Chris@42 197 */
Chris@42 198 struct solution_s {
Chris@42 199 md5sig s;
Chris@42 200 flags_t flags;
Chris@42 201 };
Chris@42 202
Chris@42 203 static solution *htab_lookup(hashtab *ht, const md5sig s,
Chris@42 204 const flags_t *flagsp)
Chris@42 205 {
Chris@42 206 unsigned g, h = h1(ht, s), d = h2(ht, s);
Chris@42 207 solution *best = 0;
Chris@42 208
Chris@42 209 ++ht->lookup;
Chris@42 210
Chris@42 211 /* search all entries that match; select the one with
Chris@42 212 the lowest flags.u */
Chris@42 213 /* This loop may potentially traverse the whole table, since at
Chris@42 214 least one element is guaranteed to be !LIVEP, but all elements
Chris@42 215 may be VALIDP. Hence, we stop after at the first invalid
Chris@42 216 element or after traversing the whole table. */
Chris@42 217 g = h;
Chris@42 218 do {
Chris@42 219 solution *l = ht->solutions + g;
Chris@42 220 ++ht->lookup_iter;
Chris@42 221 if (VALIDP(l)) {
Chris@42 222 if (LIVEP(l)
Chris@42 223 && md5eq(s, l->s)
Chris@42 224 && subsumes(&l->flags, SLVNDX(l), flagsp) ) {
Chris@42 225 if (!best || LEQ(l->flags.u, best->flags.u))
Chris@42 226 best = l;
Chris@42 227 }
Chris@42 228 } else
Chris@42 229 break;
Chris@42 230
Chris@42 231 g = addmod(g, d, ht->hashsiz);
Chris@42 232 } while (g != h);
Chris@42 233
Chris@42 234 if (best)
Chris@42 235 ++ht->succ_lookup;
Chris@42 236 return best;
Chris@42 237 }
Chris@42 238
Chris@42 239 static solution *hlookup(planner *ego, const md5sig s,
Chris@42 240 const flags_t *flagsp)
Chris@42 241 {
Chris@42 242 solution *sol = htab_lookup(&ego->htab_blessed, s, flagsp);
Chris@42 243 if (!sol) sol = htab_lookup(&ego->htab_unblessed, s, flagsp);
Chris@42 244 return sol;
Chris@42 245 }
Chris@42 246
Chris@42 247 static void fill_slot(hashtab *ht, const md5sig s, const flags_t *flagsp,
Chris@42 248 unsigned slvndx, solution *slot)
Chris@42 249 {
Chris@42 250 ++ht->insert;
Chris@42 251 ++ht->nelem;
Chris@42 252 A(!LIVEP(slot));
Chris@42 253 slot->flags.u = flagsp->u;
Chris@42 254 slot->flags.l = flagsp->l;
Chris@42 255 slot->flags.timelimit_impatience = flagsp->timelimit_impatience;
Chris@42 256 slot->flags.hash_info |= H_VALID | H_LIVE;
Chris@42 257 SLVNDX(slot) = slvndx;
Chris@42 258
Chris@42 259 /* keep this check enabled in case we add so many solvers
Chris@42 260 that the bitfield overflows */
Chris@42 261 CK(SLVNDX(slot) == slvndx);
Chris@42 262 sigcpy(s, slot->s);
Chris@42 263 }
Chris@42 264
Chris@42 265 static void kill_slot(hashtab *ht, solution *slot)
Chris@42 266 {
Chris@42 267 A(LIVEP(slot)); /* ==> */ A(VALIDP(slot));
Chris@42 268
Chris@42 269 --ht->nelem;
Chris@42 270 slot->flags.hash_info = H_VALID;
Chris@42 271 }
Chris@42 272
Chris@42 273 static void hinsert0(hashtab *ht, const md5sig s, const flags_t *flagsp,
Chris@42 274 unsigned slvndx)
Chris@42 275 {
Chris@42 276 solution *l;
Chris@42 277 unsigned g, h = h1(ht, s), d = h2(ht, s);
Chris@42 278
Chris@42 279 ++ht->insert_unknown;
Chris@42 280
Chris@42 281 /* search for nonfull slot */
Chris@42 282 for (g = h; ; g = addmod(g, d, ht->hashsiz)) {
Chris@42 283 ++ht->insert_iter;
Chris@42 284 l = ht->solutions + g;
Chris@42 285 if (!LIVEP(l)) break;
Chris@42 286 A((g + d) % ht->hashsiz != h);
Chris@42 287 }
Chris@42 288
Chris@42 289 fill_slot(ht, s, flagsp, slvndx, l);
Chris@42 290 }
Chris@42 291
Chris@42 292 static void rehash(hashtab *ht, unsigned nsiz)
Chris@42 293 {
Chris@42 294 unsigned osiz = ht->hashsiz, h;
Chris@42 295 solution *osol = ht->solutions, *nsol;
Chris@42 296
Chris@42 297 nsiz = (unsigned)X(next_prime)((INT)nsiz);
Chris@42 298 nsol = (solution *)MALLOC(nsiz * sizeof(solution), HASHT);
Chris@42 299 ++ht->nrehash;
Chris@42 300
Chris@42 301 /* init new table */
Chris@42 302 for (h = 0; h < nsiz; ++h)
Chris@42 303 nsol[h].flags.hash_info = 0;
Chris@42 304
Chris@42 305 /* install new table */
Chris@42 306 ht->hashsiz = nsiz;
Chris@42 307 ht->solutions = nsol;
Chris@42 308 ht->nelem = 0;
Chris@42 309
Chris@42 310 /* copy table */
Chris@42 311 for (h = 0; h < osiz; ++h) {
Chris@42 312 solution *l = osol + h;
Chris@42 313 if (LIVEP(l))
Chris@42 314 hinsert0(ht, l->s, &l->flags, SLVNDX(l));
Chris@42 315 }
Chris@42 316
Chris@42 317 X(ifree0)(osol);
Chris@42 318 }
Chris@42 319
Chris@42 320 static unsigned minsz(unsigned nelem)
Chris@42 321 {
Chris@42 322 return 1U + nelem + nelem / 8U;
Chris@42 323 }
Chris@42 324
Chris@42 325 static unsigned nextsz(unsigned nelem)
Chris@42 326 {
Chris@42 327 return minsz(minsz(nelem));
Chris@42 328 }
Chris@42 329
Chris@42 330 static void hgrow(hashtab *ht)
Chris@42 331 {
Chris@42 332 unsigned nelem = ht->nelem;
Chris@42 333 if (minsz(nelem) >= ht->hashsiz)
Chris@42 334 rehash(ht, nextsz(nelem));
Chris@42 335 }
Chris@42 336
Chris@42 337 #if 0
Chris@42 338 /* shrink the hash table, never used */
Chris@42 339 static void hshrink(hashtab *ht)
Chris@42 340 {
Chris@42 341 unsigned nelem = ht->nelem;
Chris@42 342 /* always rehash after deletions */
Chris@42 343 rehash(ht, nextsz(nelem));
Chris@42 344 }
Chris@42 345 #endif
Chris@42 346
Chris@42 347 static void htab_insert(hashtab *ht, const md5sig s, const flags_t *flagsp,
Chris@42 348 unsigned slvndx)
Chris@42 349 {
Chris@42 350 unsigned g, h = h1(ht, s), d = h2(ht, s);
Chris@42 351 solution *first = 0;
Chris@42 352
Chris@42 353 /* Remove all entries that are subsumed by the new one. */
Chris@42 354 /* This loop may potentially traverse the whole table, since at
Chris@42 355 least one element is guaranteed to be !LIVEP, but all elements
Chris@42 356 may be VALIDP. Hence, we stop after at the first invalid
Chris@42 357 element or after traversing the whole table. */
Chris@42 358 g = h;
Chris@42 359 do {
Chris@42 360 solution *l = ht->solutions + g;
Chris@42 361 ++ht->insert_iter;
Chris@42 362 if (VALIDP(l)) {
Chris@42 363 if (LIVEP(l) && md5eq(s, l->s)) {
Chris@42 364 if (subsumes(flagsp, slvndx, &l->flags)) {
Chris@42 365 if (!first) first = l;
Chris@42 366 kill_slot(ht, l);
Chris@42 367 } else {
Chris@42 368 /* It is an error to insert an element that
Chris@42 369 is subsumed by an existing entry. */
Chris@42 370 A(!subsumes(&l->flags, SLVNDX(l), flagsp));
Chris@42 371 }
Chris@42 372 }
Chris@42 373 } else
Chris@42 374 break;
Chris@42 375
Chris@42 376 g = addmod(g, d, ht->hashsiz);
Chris@42 377 } while (g != h);
Chris@42 378
Chris@42 379 if (first) {
Chris@42 380 /* overwrite FIRST */
Chris@42 381 fill_slot(ht, s, flagsp, slvndx, first);
Chris@42 382 } else {
Chris@42 383 /* create a new entry */
Chris@42 384 hgrow(ht);
Chris@42 385 hinsert0(ht, s, flagsp, slvndx);
Chris@42 386 }
Chris@42 387 }
Chris@42 388
Chris@42 389 static void hinsert(planner *ego, const md5sig s, const flags_t *flagsp,
Chris@42 390 unsigned slvndx)
Chris@42 391 {
Chris@42 392 htab_insert(BLISS(*flagsp) ? &ego->htab_blessed : &ego->htab_unblessed,
Chris@42 393 s, flagsp, slvndx );
Chris@42 394 }
Chris@42 395
Chris@42 396
Chris@42 397 static void invoke_hook(planner *ego, plan *pln, const problem *p,
Chris@42 398 int optimalp)
Chris@42 399 {
Chris@42 400 if (ego->hook)
Chris@42 401 ego->hook(ego, pln, p, optimalp);
Chris@42 402 }
Chris@42 403
Chris@42 404 #ifdef FFTW_RANDOM_ESTIMATOR
Chris@42 405 /* a "random" estimate, used for debugging to generate "random"
Chris@42 406 plans, albeit from a deterministic seed. */
Chris@42 407
Chris@42 408 unsigned X(random_estimate_seed) = 0;
Chris@42 409
Chris@42 410 static double random_estimate(const planner *ego, const plan *pln,
Chris@42 411 const problem *p)
Chris@42 412 {
Chris@42 413 md5 m;
Chris@42 414 X(md5begin)(&m);
Chris@42 415 X(md5unsigned)(&m, X(random_estimate_seed));
Chris@42 416 X(md5int)(&m, ego->nthr);
Chris@42 417 p->adt->hash(p, &m);
Chris@42 418 X(md5putb)(&m, &pln->ops, sizeof(pln->ops));
Chris@42 419 X(md5putb)(&m, &pln->adt, sizeof(pln->adt));
Chris@42 420 X(md5end)(&m);
Chris@42 421 return ego->cost_hook ? ego->cost_hook(p, m.s[0], COST_MAX) : m.s[0];
Chris@42 422 }
Chris@42 423
Chris@42 424 #endif
Chris@42 425
Chris@42 426 double X(iestimate_cost)(const planner *ego, const plan *pln, const problem *p)
Chris@42 427 {
Chris@42 428 double cost =
Chris@42 429 + pln->ops.add
Chris@42 430 + pln->ops.mul
Chris@42 431
Chris@42 432 #if HAVE_FMA
Chris@42 433 + pln->ops.fma
Chris@42 434 #else
Chris@42 435 + 2 * pln->ops.fma
Chris@42 436 #endif
Chris@42 437
Chris@42 438 + pln->ops.other;
Chris@42 439 if (ego->cost_hook)
Chris@42 440 cost = ego->cost_hook(p, cost, COST_MAX);
Chris@42 441 return cost;
Chris@42 442 }
Chris@42 443
Chris@42 444 static void evaluate_plan(planner *ego, plan *pln, const problem *p)
Chris@42 445 {
Chris@42 446 if (ESTIMATEP(ego) || !BELIEVE_PCOSTP(ego) || pln->pcost == 0.0) {
Chris@42 447 ego->nplan++;
Chris@42 448
Chris@42 449 if (ESTIMATEP(ego)) {
Chris@42 450 estimate:
Chris@42 451 /* heuristic */
Chris@42 452 #ifdef FFTW_RANDOM_ESTIMATOR
Chris@42 453 pln->pcost = random_estimate(ego, pln, p);
Chris@42 454 ego->epcost += X(iestimate_cost)(ego, pln, p);
Chris@42 455 #else
Chris@42 456 pln->pcost = X(iestimate_cost)(ego, pln, p);
Chris@42 457 ego->epcost += pln->pcost;
Chris@42 458 #endif
Chris@42 459 } else {
Chris@42 460 double t = X(measure_execution_time)(ego, pln, p);
Chris@42 461
Chris@42 462 if (t < 0) { /* unavailable cycle counter */
Chris@42 463 /* Real programmers can write FORTRAN in any language */
Chris@42 464 goto estimate;
Chris@42 465 }
Chris@42 466
Chris@42 467 pln->pcost = t;
Chris@42 468 ego->pcost += t;
Chris@42 469 ego->need_timeout_check = 1;
Chris@42 470 }
Chris@42 471 }
Chris@42 472
Chris@42 473 invoke_hook(ego, pln, p, 0);
Chris@42 474 }
Chris@42 475
Chris@42 476 /* maintain dynamic scoping of flags, nthr: */
Chris@42 477 static plan *invoke_solver(planner *ego, const problem *p, solver *s,
Chris@42 478 const flags_t *nflags)
Chris@42 479 {
Chris@42 480 flags_t flags = ego->flags;
Chris@42 481 int nthr = ego->nthr;
Chris@42 482 plan *pln;
Chris@42 483 ego->flags = *nflags;
Chris@42 484 PLNR_TIMELIMIT_IMPATIENCE(ego) = 0;
Chris@42 485 A(p->adt->problem_kind == s->adt->problem_kind);
Chris@42 486 pln = s->adt->mkplan(s, p, ego);
Chris@42 487 ego->nthr = nthr;
Chris@42 488 ego->flags = flags;
Chris@42 489 return pln;
Chris@42 490 }
Chris@42 491
Chris@42 492 /* maintain the invariant TIMED_OUT ==> NEED_TIMEOUT_CHECK */
Chris@42 493 static int timeout_p(planner *ego, const problem *p)
Chris@42 494 {
Chris@42 495 /* do not timeout when estimating. First, the estimator is the
Chris@42 496 planner of last resort. Second, calling X(elapsed_since)() is
Chris@42 497 slower than estimating */
Chris@42 498 if (!ESTIMATEP(ego)) {
Chris@42 499 /* do not assume that X(elapsed_since)() is monotonic */
Chris@42 500 if (ego->timed_out) {
Chris@42 501 A(ego->need_timeout_check);
Chris@42 502 return 1;
Chris@42 503 }
Chris@42 504
Chris@42 505 if (ego->timelimit >= 0 &&
Chris@42 506 X(elapsed_since)(ego, p, ego->start_time) >= ego->timelimit) {
Chris@42 507 ego->timed_out = 1;
Chris@42 508 ego->need_timeout_check = 1;
Chris@42 509 return 1;
Chris@42 510 }
Chris@42 511 }
Chris@42 512
Chris@42 513 A(!ego->timed_out);
Chris@42 514 ego->need_timeout_check = 0;
Chris@42 515 return 0;
Chris@42 516 }
Chris@42 517
Chris@42 518 static plan *search0(planner *ego, const problem *p, unsigned *slvndx,
Chris@42 519 const flags_t *flagsp)
Chris@42 520 {
Chris@42 521 plan *best = 0;
Chris@42 522 int best_not_yet_timed = 1;
Chris@42 523
Chris@42 524 /* Do not start a search if the planner timed out. This check is
Chris@42 525 necessary, lest the relaxation mechanism kick in */
Chris@42 526 if (timeout_p(ego, p))
Chris@42 527 return 0;
Chris@42 528
Chris@42 529 FORALL_SOLVERS_OF_KIND(p->adt->problem_kind, ego, s, sp, {
Chris@42 530 plan *pln;
Chris@42 531
Chris@42 532 pln = invoke_solver(ego, p, s, flagsp);
Chris@42 533
Chris@42 534 if (ego->need_timeout_check)
Chris@42 535 if (timeout_p(ego, p)) {
Chris@42 536 X(plan_destroy_internal)(pln);
Chris@42 537 X(plan_destroy_internal)(best);
Chris@42 538 return 0;
Chris@42 539 }
Chris@42 540
Chris@42 541 if (pln) {
Chris@42 542 /* read COULD_PRUNE_NOW_P because PLN may be destroyed
Chris@42 543 before we use COULD_PRUNE_NOW_P */
Chris@42 544 int could_prune_now_p = pln->could_prune_now_p;
Chris@42 545
Chris@42 546 if (best) {
Chris@42 547 if (best_not_yet_timed) {
Chris@42 548 evaluate_plan(ego, best, p);
Chris@42 549 best_not_yet_timed = 0;
Chris@42 550 }
Chris@42 551 evaluate_plan(ego, pln, p);
Chris@42 552 if (pln->pcost < best->pcost) {
Chris@42 553 X(plan_destroy_internal)(best);
Chris@42 554 best = pln;
Chris@42 555 *slvndx = (unsigned)/*from ptrdiff_t*/(sp - ego->slvdescs);
Chris@42 556 } else {
Chris@42 557 X(plan_destroy_internal)(pln);
Chris@42 558 }
Chris@42 559 } else {
Chris@42 560 best = pln;
Chris@42 561 *slvndx = (unsigned)/*from ptrdiff_t*/(sp - ego->slvdescs);
Chris@42 562 }
Chris@42 563
Chris@42 564 if (ALLOW_PRUNINGP(ego) && could_prune_now_p)
Chris@42 565 break;
Chris@42 566 }
Chris@42 567 });
Chris@42 568
Chris@42 569 return best;
Chris@42 570 }
Chris@42 571
Chris@42 572 static plan *search(planner *ego, const problem *p, unsigned *slvndx,
Chris@42 573 flags_t *flagsp)
Chris@42 574 {
Chris@42 575 plan *pln = 0;
Chris@42 576 unsigned i;
Chris@42 577
Chris@42 578 /* relax impatience in this order: */
Chris@42 579 static const unsigned relax_tab[] = {
Chris@42 580 0, /* relax nothing */
Chris@42 581 NO_VRECURSE,
Chris@42 582 NO_FIXED_RADIX_LARGE_N,
Chris@42 583 NO_SLOW,
Chris@42 584 NO_UGLY
Chris@42 585 };
Chris@42 586
Chris@42 587 unsigned l_orig = flagsp->l;
Chris@42 588 unsigned x = flagsp->u;
Chris@42 589
Chris@42 590 /* guaranteed to be different from X */
Chris@42 591 unsigned last_x = ~x;
Chris@42 592
Chris@42 593 for (i = 0; i < sizeof(relax_tab) / sizeof(relax_tab[0]); ++i) {
Chris@42 594 if (LEQ(l_orig, x & ~relax_tab[i]))
Chris@42 595 x = x & ~relax_tab[i];
Chris@42 596
Chris@42 597 if (x != last_x) {
Chris@42 598 last_x = x;
Chris@42 599 flagsp->l = x;
Chris@42 600 pln = search0(ego, p, slvndx, flagsp);
Chris@42 601 if (pln) break;
Chris@42 602 }
Chris@42 603 }
Chris@42 604
Chris@42 605 if (!pln) {
Chris@42 606 /* search [L_ORIG, U] */
Chris@42 607 if (l_orig != last_x) {
Chris@42 608 last_x = l_orig;
Chris@42 609 flagsp->l = l_orig;
Chris@42 610 pln = search0(ego, p, slvndx, flagsp);
Chris@42 611 }
Chris@42 612 }
Chris@42 613
Chris@42 614 return pln;
Chris@42 615 }
Chris@42 616
Chris@42 617 #define CHECK_FOR_BOGOSITY \
Chris@42 618 if ((ego->bogosity_hook ? \
Chris@42 619 (ego->wisdom_state = ego->bogosity_hook(ego->wisdom_state, p)) \
Chris@42 620 : ego->wisdom_state) == WISDOM_IS_BOGUS) \
Chris@42 621 goto wisdom_is_bogus;
Chris@42 622
Chris@42 623 static plan *mkplan(planner *ego, const problem *p)
Chris@42 624 {
Chris@42 625 plan *pln;
Chris@42 626 md5 m;
Chris@42 627 unsigned slvndx;
Chris@42 628 flags_t flags_of_solution;
Chris@42 629 solution *sol;
Chris@42 630 solver *s;
Chris@42 631
Chris@42 632 ASSERT_ALIGNED_DOUBLE;
Chris@42 633 A(LEQ(PLNR_L(ego), PLNR_U(ego)));
Chris@42 634
Chris@42 635 if (ESTIMATEP(ego))
Chris@42 636 PLNR_TIMELIMIT_IMPATIENCE(ego) = 0; /* canonical form */
Chris@42 637
Chris@42 638
Chris@42 639 #ifdef FFTW_DEBUG
Chris@42 640 check(&ego->htab_blessed);
Chris@42 641 check(&ego->htab_unblessed);
Chris@42 642 #endif
Chris@42 643
Chris@42 644 pln = 0;
Chris@42 645
Chris@42 646 CHECK_FOR_BOGOSITY;
Chris@42 647
Chris@42 648 ego->timed_out = 0;
Chris@42 649
Chris@42 650 ++ego->nprob;
Chris@42 651 md5hash(&m, p, ego);
Chris@42 652
Chris@42 653 flags_of_solution = ego->flags;
Chris@42 654
Chris@42 655 if (ego->wisdom_state != WISDOM_IGNORE_ALL) {
Chris@42 656 if ((sol = hlookup(ego, m.s, &flags_of_solution))) {
Chris@42 657 /* wisdom is acceptable */
Chris@42 658 wisdom_state_t owisdom_state = ego->wisdom_state;
Chris@42 659
Chris@42 660 /* this hook is mainly for MPI, to make sure that
Chris@42 661 wisdom is in sync across all processes for MPI problems */
Chris@42 662 if (ego->wisdom_ok_hook && !ego->wisdom_ok_hook(p, sol->flags))
Chris@42 663 goto do_search; /* ignore not-ok wisdom */
Chris@42 664
Chris@42 665 slvndx = SLVNDX(sol);
Chris@42 666
Chris@42 667 if (slvndx == INFEASIBLE_SLVNDX) {
Chris@42 668 if (ego->wisdom_state == WISDOM_IGNORE_INFEASIBLE)
Chris@42 669 goto do_search;
Chris@42 670 else
Chris@42 671 return 0; /* known to be infeasible */
Chris@42 672 }
Chris@42 673
Chris@42 674 flags_of_solution = sol->flags;
Chris@42 675
Chris@42 676 /* inherit blessing either from wisdom
Chris@42 677 or from the planner */
Chris@42 678 flags_of_solution.hash_info |= BLISS(ego->flags);
Chris@42 679
Chris@42 680 ego->wisdom_state = WISDOM_ONLY;
Chris@42 681
Chris@42 682 s = ego->slvdescs[slvndx].slv;
Chris@42 683 if (p->adt->problem_kind != s->adt->problem_kind)
Chris@42 684 goto wisdom_is_bogus;
Chris@42 685
Chris@42 686 pln = invoke_solver(ego, p, s, &flags_of_solution);
Chris@42 687
Chris@42 688 CHECK_FOR_BOGOSITY; /* catch error in child solvers */
Chris@42 689
Chris@42 690 sol = 0; /* Paranoia: SOL may be dangling after
Chris@42 691 invoke_solver(); make sure we don't accidentally
Chris@42 692 reuse it. */
Chris@42 693
Chris@42 694 if (!pln)
Chris@42 695 goto wisdom_is_bogus;
Chris@42 696
Chris@42 697 ego->wisdom_state = owisdom_state;
Chris@42 698
Chris@42 699 goto skip_search;
Chris@42 700 }
Chris@42 701 else if (ego->nowisdom_hook) /* for MPI, make sure lack of wisdom */
Chris@42 702 ego->nowisdom_hook(p); /* is in sync across all processes */
Chris@42 703 }
Chris@42 704
Chris@42 705 do_search:
Chris@42 706 /* cannot search in WISDOM_ONLY mode */
Chris@42 707 if (ego->wisdom_state == WISDOM_ONLY)
Chris@42 708 goto wisdom_is_bogus;
Chris@42 709
Chris@42 710 flags_of_solution = ego->flags;
Chris@42 711 pln = search(ego, p, &slvndx, &flags_of_solution);
Chris@42 712 CHECK_FOR_BOGOSITY; /* catch error in child solvers */
Chris@42 713
Chris@42 714 if (ego->timed_out) {
Chris@42 715 A(!pln);
Chris@42 716 if (PLNR_TIMELIMIT_IMPATIENCE(ego) != 0) {
Chris@42 717 /* record (below) that this plan has failed because of
Chris@42 718 timeout */
Chris@42 719 flags_of_solution.hash_info |= BLESSING;
Chris@42 720 } else {
Chris@42 721 /* this is not the top-level problem or timeout is not
Chris@42 722 active: record no wisdom. */
Chris@42 723 return 0;
Chris@42 724 }
Chris@42 725 } else {
Chris@42 726 /* canonicalize to infinite timeout */
Chris@42 727 flags_of_solution.timelimit_impatience = 0;
Chris@42 728 }
Chris@42 729
Chris@42 730 skip_search:
Chris@42 731 if (ego->wisdom_state == WISDOM_NORMAL ||
Chris@42 732 ego->wisdom_state == WISDOM_ONLY) {
Chris@42 733 if (pln) {
Chris@42 734 hinsert(ego, m.s, &flags_of_solution, slvndx);
Chris@42 735 invoke_hook(ego, pln, p, 1);
Chris@42 736 } else {
Chris@42 737 hinsert(ego, m.s, &flags_of_solution, INFEASIBLE_SLVNDX);
Chris@42 738 }
Chris@42 739 }
Chris@42 740
Chris@42 741 return pln;
Chris@42 742
Chris@42 743 wisdom_is_bogus:
Chris@42 744 X(plan_destroy_internal)(pln);
Chris@42 745 ego->wisdom_state = WISDOM_IS_BOGUS;
Chris@42 746 return 0;
Chris@42 747 }
Chris@42 748
Chris@42 749 static void htab_destroy(hashtab *ht)
Chris@42 750 {
Chris@42 751 X(ifree)(ht->solutions);
Chris@42 752 ht->solutions = 0;
Chris@42 753 ht->nelem = 0U;
Chris@42 754 }
Chris@42 755
Chris@42 756 static void mkhashtab(hashtab *ht)
Chris@42 757 {
Chris@42 758 ht->nrehash = 0;
Chris@42 759 ht->succ_lookup = ht->lookup = ht->lookup_iter = 0;
Chris@42 760 ht->insert = ht->insert_iter = ht->insert_unknown = 0;
Chris@42 761
Chris@42 762 ht->solutions = 0;
Chris@42 763 ht->hashsiz = ht->nelem = 0U;
Chris@42 764 hgrow(ht); /* so that hashsiz > 0 */
Chris@42 765 }
Chris@42 766
Chris@42 767 /* destroy hash table entries. If FORGET_EVERYTHING, destroy the whole
Chris@42 768 table. If FORGET_ACCURSED, then destroy entries that are not blessed. */
Chris@42 769 static void forget(planner *ego, amnesia a)
Chris@42 770 {
Chris@42 771 switch (a) {
Chris@42 772 case FORGET_EVERYTHING:
Chris@42 773 htab_destroy(&ego->htab_blessed);
Chris@42 774 mkhashtab(&ego->htab_blessed);
Chris@42 775 /* fall through */
Chris@42 776 case FORGET_ACCURSED:
Chris@42 777 htab_destroy(&ego->htab_unblessed);
Chris@42 778 mkhashtab(&ego->htab_unblessed);
Chris@42 779 break;
Chris@42 780 default:
Chris@42 781 break;
Chris@42 782 }
Chris@42 783 }
Chris@42 784
Chris@42 785 /* FIXME: what sort of version information should we write? */
Chris@42 786 #define WISDOM_PREAMBLE PACKAGE "-" VERSION " " STRINGIZE(X(wisdom))
Chris@42 787 static const char stimeout[] = "TIMEOUT";
Chris@42 788
Chris@42 789 /* tantus labor non sit cassus */
Chris@42 790 static void exprt(planner *ego, printer *p)
Chris@42 791 {
Chris@42 792 unsigned h;
Chris@42 793 hashtab *ht = &ego->htab_blessed;
Chris@42 794 md5 m;
Chris@42 795
Chris@42 796 signature_of_configuration(&m, ego);
Chris@42 797
Chris@42 798 p->print(p,
Chris@42 799 "(" WISDOM_PREAMBLE " #x%M #x%M #x%M #x%M\n",
Chris@42 800 m.s[0], m.s[1], m.s[2], m.s[3]);
Chris@42 801
Chris@42 802 for (h = 0; h < ht->hashsiz; ++h) {
Chris@42 803 solution *l = ht->solutions + h;
Chris@42 804 if (LIVEP(l)) {
Chris@42 805 const char *reg_nam;
Chris@42 806 int reg_id;
Chris@42 807
Chris@42 808 if (SLVNDX(l) == INFEASIBLE_SLVNDX) {
Chris@42 809 reg_nam = stimeout;
Chris@42 810 reg_id = 0;
Chris@42 811 } else {
Chris@42 812 slvdesc *sp = ego->slvdescs + SLVNDX(l);
Chris@42 813 reg_nam = sp->reg_nam;
Chris@42 814 reg_id = sp->reg_id;
Chris@42 815 }
Chris@42 816
Chris@42 817 /* qui salvandos salvas gratis
Chris@42 818 salva me fons pietatis */
Chris@42 819 p->print(p, " (%s %d #x%x #x%x #x%x #x%M #x%M #x%M #x%M)\n",
Chris@42 820 reg_nam, reg_id,
Chris@42 821 l->flags.l, l->flags.u, l->flags.timelimit_impatience,
Chris@42 822 l->s[0], l->s[1], l->s[2], l->s[3]);
Chris@42 823 }
Chris@42 824 }
Chris@42 825 p->print(p, ")\n");
Chris@42 826 }
Chris@42 827
Chris@42 828 /* mors stupebit et natura
Chris@42 829 cum resurget creatura */
Chris@42 830 static int imprt(planner *ego, scanner *sc)
Chris@42 831 {
Chris@42 832 char buf[MAXNAM + 1];
Chris@42 833 md5uint sig[4];
Chris@42 834 unsigned l, u, timelimit_impatience;
Chris@42 835 flags_t flags;
Chris@42 836 int reg_id;
Chris@42 837 unsigned slvndx;
Chris@42 838 hashtab *ht = &ego->htab_blessed;
Chris@42 839 hashtab old;
Chris@42 840 md5 m;
Chris@42 841
Chris@42 842 if (!sc->scan(sc,
Chris@42 843 "(" WISDOM_PREAMBLE " #x%M #x%M #x%M #x%M\n",
Chris@42 844 sig + 0, sig + 1, sig + 2, sig + 3))
Chris@42 845 return 0; /* don't need to restore hashtable */
Chris@42 846
Chris@42 847 signature_of_configuration(&m, ego);
Chris@42 848 if (m.s[0] != sig[0] || m.s[1] != sig[1] ||
Chris@42 849 m.s[2] != sig[2] || m.s[3] != sig[3]) {
Chris@42 850 /* invalid configuration */
Chris@42 851 return 0;
Chris@42 852 }
Chris@42 853
Chris@42 854 /* make a backup copy of the hash table (cache the hash) */
Chris@42 855 {
Chris@42 856 unsigned h, hsiz = ht->hashsiz;
Chris@42 857 old = *ht;
Chris@42 858 old.solutions = (solution *)MALLOC(hsiz * sizeof(solution), HASHT);
Chris@42 859 for (h = 0; h < hsiz; ++h)
Chris@42 860 old.solutions[h] = ht->solutions[h];
Chris@42 861 }
Chris@42 862
Chris@42 863 while (1) {
Chris@42 864 if (sc->scan(sc, ")"))
Chris@42 865 break;
Chris@42 866
Chris@42 867 /* qua resurget ex favilla */
Chris@42 868 if (!sc->scan(sc, "(%*s %d #x%x #x%x #x%x #x%M #x%M #x%M #x%M)",
Chris@42 869 MAXNAM, buf, &reg_id, &l, &u, &timelimit_impatience,
Chris@42 870 sig + 0, sig + 1, sig + 2, sig + 3))
Chris@42 871 goto bad;
Chris@42 872
Chris@42 873 if (!strcmp(buf, stimeout) && reg_id == 0) {
Chris@42 874 slvndx = INFEASIBLE_SLVNDX;
Chris@42 875 } else {
Chris@42 876 if (timelimit_impatience != 0)
Chris@42 877 goto bad;
Chris@42 878
Chris@42 879 slvndx = slookup(ego, buf, reg_id);
Chris@42 880 if (slvndx == INFEASIBLE_SLVNDX)
Chris@42 881 goto bad;
Chris@42 882 }
Chris@42 883
Chris@42 884 /* inter oves locum praesta */
Chris@42 885 flags.l = l;
Chris@42 886 flags.u = u;
Chris@42 887 flags.timelimit_impatience = timelimit_impatience;
Chris@42 888 flags.hash_info = BLESSING;
Chris@42 889
Chris@42 890 CK(flags.l == l);
Chris@42 891 CK(flags.u == u);
Chris@42 892 CK(flags.timelimit_impatience == timelimit_impatience);
Chris@42 893
Chris@42 894 if (!hlookup(ego, sig, &flags))
Chris@42 895 hinsert(ego, sig, &flags, slvndx);
Chris@42 896 }
Chris@42 897
Chris@42 898 X(ifree0)(old.solutions);
Chris@42 899 return 1;
Chris@42 900
Chris@42 901 bad:
Chris@42 902 /* ``The wisdom of FFTW must be above suspicion.'' */
Chris@42 903 X(ifree0)(ht->solutions);
Chris@42 904 *ht = old;
Chris@42 905 return 0;
Chris@42 906 }
Chris@42 907
Chris@42 908 /*
Chris@42 909 * create a planner
Chris@42 910 */
Chris@42 911 planner *X(mkplanner)(void)
Chris@42 912 {
Chris@42 913 int i;
Chris@42 914
Chris@42 915 static const planner_adt padt = {
Chris@42 916 register_solver, mkplan, forget, exprt, imprt
Chris@42 917 };
Chris@42 918
Chris@42 919 planner *p = (planner *) MALLOC(sizeof(planner), PLANNERS);
Chris@42 920
Chris@42 921 p->adt = &padt;
Chris@42 922 p->nplan = p->nprob = 0;
Chris@42 923 p->pcost = p->epcost = 0.0;
Chris@42 924 p->hook = 0;
Chris@42 925 p->cost_hook = 0;
Chris@42 926 p->wisdom_ok_hook = 0;
Chris@42 927 p->nowisdom_hook = 0;
Chris@42 928 p->bogosity_hook = 0;
Chris@42 929 p->cur_reg_nam = 0;
Chris@42 930 p->wisdom_state = WISDOM_NORMAL;
Chris@42 931
Chris@42 932 p->slvdescs = 0;
Chris@42 933 p->nslvdesc = p->slvdescsiz = 0;
Chris@42 934
Chris@42 935 p->flags.l = 0;
Chris@42 936 p->flags.u = 0;
Chris@42 937 p->flags.timelimit_impatience = 0;
Chris@42 938 p->flags.hash_info = 0;
Chris@42 939 p->nthr = 1;
Chris@42 940 p->need_timeout_check = 1;
Chris@42 941 p->timelimit = -1;
Chris@42 942
Chris@42 943 mkhashtab(&p->htab_blessed);
Chris@42 944 mkhashtab(&p->htab_unblessed);
Chris@42 945
Chris@42 946 for (i = 0; i < PROBLEM_LAST; ++i)
Chris@42 947 p->slvdescs_for_problem_kind[i] = -1;
Chris@42 948
Chris@42 949 return p;
Chris@42 950 }
Chris@42 951
Chris@42 952 void X(planner_destroy)(planner *ego)
Chris@42 953 {
Chris@42 954 /* destroy hash table */
Chris@42 955 htab_destroy(&ego->htab_blessed);
Chris@42 956 htab_destroy(&ego->htab_unblessed);
Chris@42 957
Chris@42 958 /* destroy solvdesc table */
Chris@42 959 FORALL_SOLVERS(ego, s, sp, {
Chris@42 960 UNUSED(sp);
Chris@42 961 X(solver_destroy)(s);
Chris@42 962 });
Chris@42 963
Chris@42 964 X(ifree0)(ego->slvdescs);
Chris@42 965 X(ifree)(ego); /* dona eis requiem */
Chris@42 966 }
Chris@42 967
Chris@42 968 plan *X(mkplan_d)(planner *ego, problem *p)
Chris@42 969 {
Chris@42 970 plan *pln = ego->adt->mkplan(ego, p);
Chris@42 971 X(problem_destroy)(p);
Chris@42 972 return pln;
Chris@42 973 }
Chris@42 974
Chris@42 975 /* like X(mkplan_d), but sets/resets flags as well */
Chris@42 976 plan *X(mkplan_f_d)(planner *ego, problem *p,
Chris@42 977 unsigned l_set, unsigned u_set, unsigned u_reset)
Chris@42 978 {
Chris@42 979 flags_t oflags = ego->flags;
Chris@42 980 plan *pln;
Chris@42 981
Chris@42 982 PLNR_U(ego) &= ~u_reset;
Chris@42 983 PLNR_L(ego) &= ~u_reset;
Chris@42 984 PLNR_L(ego) |= l_set;
Chris@42 985 PLNR_U(ego) |= u_set | l_set;
Chris@42 986 pln = X(mkplan_d)(ego, p);
Chris@42 987 ego->flags = oflags;
Chris@42 988 return pln;
Chris@42 989 }
Chris@42 990
Chris@42 991 /*
Chris@42 992 * Debugging code:
Chris@42 993 */
Chris@42 994 #ifdef FFTW_DEBUG
Chris@42 995 static void check(hashtab *ht)
Chris@42 996 {
Chris@42 997 unsigned live = 0;
Chris@42 998 unsigned i;
Chris@42 999
Chris@42 1000 A(ht->nelem < ht->hashsiz);
Chris@42 1001
Chris@42 1002 for (i = 0; i < ht->hashsiz; ++i) {
Chris@42 1003 solution *l = ht->solutions + i;
Chris@42 1004 if (LIVEP(l))
Chris@42 1005 ++live;
Chris@42 1006 }
Chris@42 1007
Chris@42 1008 A(ht->nelem == live);
Chris@42 1009
Chris@42 1010 for (i = 0; i < ht->hashsiz; ++i) {
Chris@42 1011 solution *l1 = ht->solutions + i;
Chris@42 1012 int foundit = 0;
Chris@42 1013 if (LIVEP(l1)) {
Chris@42 1014 unsigned g, h = h1(ht, l1->s), d = h2(ht, l1->s);
Chris@42 1015
Chris@42 1016 g = h;
Chris@42 1017 do {
Chris@42 1018 solution *l = ht->solutions + g;
Chris@42 1019 if (VALIDP(l)) {
Chris@42 1020 if (l1 == l)
Chris@42 1021 foundit = 1;
Chris@42 1022 else if (LIVEP(l) && md5eq(l1->s, l->s)) {
Chris@42 1023 A(!subsumes(&l->flags, SLVNDX(l), &l1->flags));
Chris@42 1024 A(!subsumes(&l1->flags, SLVNDX(l1), &l->flags));
Chris@42 1025 }
Chris@42 1026 } else
Chris@42 1027 break;
Chris@42 1028 g = addmod(g, d, ht->hashsiz);
Chris@42 1029 } while (g != h);
Chris@42 1030
Chris@42 1031 A(foundit);
Chris@42 1032 }
Chris@42 1033 }
Chris@42 1034 }
Chris@42 1035 #endif