cannam@95: /* cannam@95: * Copyright (c) 2000 Matteo Frigo cannam@95: * Copyright (c) 2000 Massachusetts Institute of Technology cannam@95: * cannam@95: * This program is free software; you can redistribute it and/or modify cannam@95: * it under the terms of the GNU General Public License as published by cannam@95: * the Free Software Foundation; either version 2 of the License, or cannam@95: * (at your option) any later version. cannam@95: * cannam@95: * This program is distributed in the hope that it will be useful, cannam@95: * but WITHOUT ANY WARRANTY; without even the implied warranty of cannam@95: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the cannam@95: * GNU General Public License for more details. cannam@95: * cannam@95: * You should have received a copy of the GNU General Public License cannam@95: * along with this program; if not, write to the Free Software cannam@95: * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA cannam@95: * cannam@95: */ cannam@95: cannam@95: #include "ifftw.h" cannam@95: #include cannam@95: cannam@95: /* GNU Coding Standards, Sec. 5.2: "Please write the comments in a GNU cannam@95: program in English, because English is the one language that nearly cannam@95: all programmers in all countries can read." cannam@95: cannam@95: ingemisco tanquam reus cannam@95: culpa rubet vultus meus cannam@95: supplicanti parce [rms] cannam@95: */ cannam@95: cannam@95: #define VALIDP(solution) ((solution)->flags.hash_info & H_VALID) cannam@95: #define LIVEP(solution) ((solution)->flags.hash_info & H_LIVE) cannam@95: #define SLVNDX(solution) ((solution)->flags.slvndx) cannam@95: #define BLISS(flags) (((flags).hash_info) & BLESSING) cannam@95: #define INFEASIBLE_SLVNDX ((1U<timelimit_impatience == 0); cannam@95: return (LEQ(a->u, b->u) && LEQ(b->l, a->l)); cannam@95: } else { cannam@95: return (LEQ(a->l, b->l) cannam@95: && a->timelimit_impatience <= b->timelimit_impatience); cannam@95: } cannam@95: } cannam@95: cannam@95: static unsigned addmod(unsigned a, unsigned b, unsigned p) cannam@95: { cannam@95: /* gcc-2.95/sparc produces incorrect code for the fast version below. */ cannam@95: #if defined(__sparc__) && defined(__GNUC__) cannam@95: /* slow version */ cannam@95: return (a + b) % p; cannam@95: #else cannam@95: /* faster version */ cannam@95: unsigned c = a + b; cannam@95: return c >= p ? c - p : c; cannam@95: #endif cannam@95: } cannam@95: cannam@95: /* cannam@95: slvdesc management: cannam@95: */ cannam@95: static void sgrow(planner *ego) cannam@95: { cannam@95: unsigned osiz = ego->slvdescsiz, nsiz = 1 + osiz + osiz / 4; cannam@95: slvdesc *ntab = (slvdesc *)MALLOC(nsiz * sizeof(slvdesc), SLVDESCS); cannam@95: slvdesc *otab = ego->slvdescs; cannam@95: unsigned i; cannam@95: cannam@95: ego->slvdescs = ntab; cannam@95: ego->slvdescsiz = nsiz; cannam@95: for (i = 0; i < osiz; ++i) cannam@95: ntab[i] = otab[i]; cannam@95: X(ifree0)(otab); cannam@95: } cannam@95: cannam@95: static void register_solver(planner *ego, solver *s) cannam@95: { cannam@95: slvdesc *n; cannam@95: int kind; cannam@95: cannam@95: if (s) { /* add s to solver list */ cannam@95: X(solver_use)(s); cannam@95: cannam@95: A(ego->nslvdesc < INFEASIBLE_SLVNDX); cannam@95: if (ego->nslvdesc >= ego->slvdescsiz) cannam@95: sgrow(ego); cannam@95: cannam@95: n = ego->slvdescs + ego->nslvdesc; cannam@95: cannam@95: n->slv = s; cannam@95: n->reg_nam = ego->cur_reg_nam; cannam@95: n->reg_id = ego->cur_reg_id++; cannam@95: cannam@95: A(strlen(n->reg_nam) < MAXNAM); cannam@95: n->nam_hash = X(hash)(n->reg_nam); cannam@95: cannam@95: kind = s->adt->problem_kind; cannam@95: n->next_for_same_problem_kind = ego->slvdescs_for_problem_kind[kind]; cannam@95: ego->slvdescs_for_problem_kind[kind] = ego->nslvdesc; cannam@95: cannam@95: ego->nslvdesc++; cannam@95: } cannam@95: } cannam@95: cannam@95: static unsigned slookup(planner *ego, char *nam, int id) cannam@95: { cannam@95: unsigned h = X(hash)(nam); /* used to avoid strcmp in the common case */ cannam@95: FORALL_SOLVERS(ego, s, sp, { cannam@95: UNUSED(s); cannam@95: if (sp->reg_id == id && sp->nam_hash == h cannam@95: && !strcmp(sp->reg_nam, nam)) cannam@95: return sp - ego->slvdescs; cannam@95: }); cannam@95: return INFEASIBLE_SLVNDX; cannam@95: } cannam@95: cannam@95: /* Compute a MD5 hash of the configuration of the planner. cannam@95: We store it into the wisdom file to make absolutely sure that cannam@95: we are reading wisdom that is applicable */ cannam@95: static void signature_of_configuration(md5 *m, planner *ego) cannam@95: { cannam@95: X(md5begin)(m); cannam@95: X(md5unsigned)(m, sizeof(R)); /* so we don't mix different precisions */ cannam@95: FORALL_SOLVERS(ego, s, sp, { cannam@95: UNUSED(s); cannam@95: X(md5int)(m, sp->reg_id); cannam@95: X(md5puts)(m, sp->reg_nam); cannam@95: }); cannam@95: X(md5end)(m); cannam@95: } cannam@95: cannam@95: /* cannam@95: md5-related stuff: cannam@95: */ cannam@95: cannam@95: /* first hash function */ cannam@95: static unsigned h1(const hashtab *ht, const md5sig s) cannam@95: { cannam@95: unsigned h = s[0] % ht->hashsiz; cannam@95: A(h == (s[0] % ht->hashsiz)); cannam@95: return h; cannam@95: } cannam@95: cannam@95: /* second hash function (for double hashing) */ cannam@95: static unsigned h2(const hashtab *ht, const md5sig s) cannam@95: { cannam@95: unsigned h = 1U + s[1] % (ht->hashsiz - 1); cannam@95: A(h == (1U + s[1] % (ht->hashsiz - 1))); cannam@95: return h; cannam@95: } cannam@95: cannam@95: static void md5hash(md5 *m, const problem *p, const planner *plnr) cannam@95: { cannam@95: X(md5begin)(m); cannam@95: X(md5unsigned)(m, sizeof(R)); /* so we don't mix different precisions */ cannam@95: X(md5int)(m, plnr->nthr); cannam@95: p->adt->hash(p, m); cannam@95: X(md5end)(m); cannam@95: } cannam@95: cannam@95: static int md5eq(const md5sig a, const md5sig b) cannam@95: { cannam@95: return a[0] == b[0] && a[1] == b[1] && a[2] == b[2] && a[3] == b[3]; cannam@95: } cannam@95: cannam@95: static void sigcpy(const md5sig a, md5sig b) cannam@95: { cannam@95: b[0] = a[0]; b[1] = a[1]; b[2] = a[2]; b[3] = a[3]; cannam@95: } cannam@95: cannam@95: /* cannam@95: memoization routines : cannam@95: */ cannam@95: cannam@95: /* cannam@95: liber scriptus proferetur cannam@95: in quo totum continetur cannam@95: unde mundus iudicetur cannam@95: */ cannam@95: struct solution_s { cannam@95: md5sig s; cannam@95: flags_t flags; cannam@95: }; cannam@95: cannam@95: static solution *htab_lookup(hashtab *ht, const md5sig s, cannam@95: const flags_t *flagsp) cannam@95: { cannam@95: unsigned g, h = h1(ht, s), d = h2(ht, s); cannam@95: solution *best = 0; cannam@95: cannam@95: ++ht->lookup; cannam@95: cannam@95: /* search all entries that match; select the one with cannam@95: the lowest flags.u */ cannam@95: /* This loop may potentially traverse the whole table, since at cannam@95: least one element is guaranteed to be !LIVEP, but all elements cannam@95: may be VALIDP. Hence, we stop after at the first invalid cannam@95: element or after traversing the whole table. */ cannam@95: g = h; cannam@95: do { cannam@95: solution *l = ht->solutions + g; cannam@95: ++ht->lookup_iter; cannam@95: if (VALIDP(l)) { cannam@95: if (LIVEP(l) cannam@95: && md5eq(s, l->s) cannam@95: && subsumes(&l->flags, SLVNDX(l), flagsp) ) { cannam@95: if (!best || LEQ(l->flags.u, best->flags.u)) cannam@95: best = l; cannam@95: } cannam@95: } else cannam@95: break; cannam@95: cannam@95: g = addmod(g, d, ht->hashsiz); cannam@95: } while (g != h); cannam@95: cannam@95: if (best) cannam@95: ++ht->succ_lookup; cannam@95: return best; cannam@95: } cannam@95: cannam@95: static solution *hlookup(planner *ego, const md5sig s, cannam@95: const flags_t *flagsp) cannam@95: { cannam@95: solution *sol = htab_lookup(&ego->htab_blessed, s, flagsp); cannam@95: if (!sol) sol = htab_lookup(&ego->htab_unblessed, s, flagsp); cannam@95: return sol; cannam@95: } cannam@95: cannam@95: static void fill_slot(hashtab *ht, const md5sig s, const flags_t *flagsp, cannam@95: unsigned slvndx, solution *slot) cannam@95: { cannam@95: ++ht->insert; cannam@95: ++ht->nelem; cannam@95: A(!LIVEP(slot)); cannam@95: slot->flags.u = flagsp->u; cannam@95: slot->flags.l = flagsp->l; cannam@95: slot->flags.timelimit_impatience = flagsp->timelimit_impatience; cannam@95: slot->flags.hash_info |= H_VALID | H_LIVE; cannam@95: SLVNDX(slot) = slvndx; cannam@95: cannam@95: /* keep this check enabled in case we add so many solvers cannam@95: that the bitfield overflows */ cannam@95: CK(SLVNDX(slot) == slvndx); cannam@95: sigcpy(s, slot->s); cannam@95: } cannam@95: cannam@95: static void kill_slot(hashtab *ht, solution *slot) cannam@95: { cannam@95: A(LIVEP(slot)); /* ==> */ A(VALIDP(slot)); cannam@95: cannam@95: --ht->nelem; cannam@95: slot->flags.hash_info = H_VALID; cannam@95: } cannam@95: cannam@95: static void hinsert0(hashtab *ht, const md5sig s, const flags_t *flagsp, cannam@95: unsigned slvndx) cannam@95: { cannam@95: solution *l; cannam@95: unsigned g, h = h1(ht, s), d = h2(ht, s); cannam@95: cannam@95: ++ht->insert_unknown; cannam@95: cannam@95: /* search for nonfull slot */ cannam@95: for (g = h; ; g = addmod(g, d, ht->hashsiz)) { cannam@95: ++ht->insert_iter; cannam@95: l = ht->solutions + g; cannam@95: if (!LIVEP(l)) break; cannam@95: A((g + d) % ht->hashsiz != h); cannam@95: } cannam@95: cannam@95: fill_slot(ht, s, flagsp, slvndx, l); cannam@95: } cannam@95: cannam@95: static void rehash(hashtab *ht, unsigned nsiz) cannam@95: { cannam@95: unsigned osiz = ht->hashsiz, h; cannam@95: solution *osol = ht->solutions, *nsol; cannam@95: cannam@95: nsiz = (unsigned)X(next_prime)((INT)nsiz); cannam@95: nsol = (solution *)MALLOC(nsiz * sizeof(solution), HASHT); cannam@95: ++ht->nrehash; cannam@95: cannam@95: /* init new table */ cannam@95: for (h = 0; h < nsiz; ++h) cannam@95: nsol[h].flags.hash_info = 0; cannam@95: cannam@95: /* install new table */ cannam@95: ht->hashsiz = nsiz; cannam@95: ht->solutions = nsol; cannam@95: ht->nelem = 0; cannam@95: cannam@95: /* copy table */ cannam@95: for (h = 0; h < osiz; ++h) { cannam@95: solution *l = osol + h; cannam@95: if (LIVEP(l)) cannam@95: hinsert0(ht, l->s, &l->flags, SLVNDX(l)); cannam@95: } cannam@95: cannam@95: X(ifree0)(osol); cannam@95: } cannam@95: cannam@95: static unsigned minsz(unsigned nelem) cannam@95: { cannam@95: return 1U + nelem + nelem / 8U; cannam@95: } cannam@95: cannam@95: static unsigned nextsz(unsigned nelem) cannam@95: { cannam@95: return minsz(minsz(nelem)); cannam@95: } cannam@95: cannam@95: static void hgrow(hashtab *ht) cannam@95: { cannam@95: unsigned nelem = ht->nelem; cannam@95: if (minsz(nelem) >= ht->hashsiz) cannam@95: rehash(ht, nextsz(nelem)); cannam@95: } cannam@95: cannam@95: #if 0 cannam@95: /* shrink the hash table, never used */ cannam@95: static void hshrink(hashtab *ht) cannam@95: { cannam@95: unsigned nelem = ht->nelem; cannam@95: /* always rehash after deletions */ cannam@95: rehash(ht, nextsz(nelem)); cannam@95: } cannam@95: #endif cannam@95: cannam@95: static void htab_insert(hashtab *ht, const md5sig s, const flags_t *flagsp, cannam@95: unsigned slvndx) cannam@95: { cannam@95: unsigned g, h = h1(ht, s), d = h2(ht, s); cannam@95: solution *first = 0; cannam@95: cannam@95: /* Remove all entries that are subsumed by the new one. */ cannam@95: /* This loop may potentially traverse the whole table, since at cannam@95: least one element is guaranteed to be !LIVEP, but all elements cannam@95: may be VALIDP. Hence, we stop after at the first invalid cannam@95: element or after traversing the whole table. */ cannam@95: g = h; cannam@95: do { cannam@95: solution *l = ht->solutions + g; cannam@95: ++ht->insert_iter; cannam@95: if (VALIDP(l)) { cannam@95: if (LIVEP(l) && md5eq(s, l->s)) { cannam@95: if (subsumes(flagsp, slvndx, &l->flags)) { cannam@95: if (!first) first = l; cannam@95: kill_slot(ht, l); cannam@95: } else { cannam@95: /* It is an error to insert an element that cannam@95: is subsumed by an existing entry. */ cannam@95: A(!subsumes(&l->flags, SLVNDX(l), flagsp)); cannam@95: } cannam@95: } cannam@95: } else cannam@95: break; cannam@95: cannam@95: g = addmod(g, d, ht->hashsiz); cannam@95: } while (g != h); cannam@95: cannam@95: if (first) { cannam@95: /* overwrite FIRST */ cannam@95: fill_slot(ht, s, flagsp, slvndx, first); cannam@95: } else { cannam@95: /* create a new entry */ cannam@95: hgrow(ht); cannam@95: hinsert0(ht, s, flagsp, slvndx); cannam@95: } cannam@95: } cannam@95: cannam@95: static void hinsert(planner *ego, const md5sig s, const flags_t *flagsp, cannam@95: unsigned slvndx) cannam@95: { cannam@95: htab_insert(BLISS(*flagsp) ? &ego->htab_blessed : &ego->htab_unblessed, cannam@95: s, flagsp, slvndx ); cannam@95: } cannam@95: cannam@95: cannam@95: static void invoke_hook(planner *ego, plan *pln, const problem *p, cannam@95: int optimalp) cannam@95: { cannam@95: if (ego->hook) cannam@95: ego->hook(ego, pln, p, optimalp); cannam@95: } cannam@95: cannam@95: #ifdef FFTW_RANDOM_ESTIMATOR cannam@95: /* a "random" estimate, used for debugging to generate "random" cannam@95: plans, albeit from a deterministic seed. */ cannam@95: cannam@95: unsigned X(random_estimate_seed) = 0; cannam@95: cannam@95: static double random_estimate(const planner *ego, const plan *pln, cannam@95: const problem *p) cannam@95: { cannam@95: md5 m; cannam@95: X(md5begin)(&m); cannam@95: X(md5unsigned)(&m, X(random_estimate_seed)); cannam@95: X(md5int)(&m, ego->nthr); cannam@95: p->adt->hash(p, &m); cannam@95: X(md5putb)(&m, &pln->ops, sizeof(pln->ops)); cannam@95: X(md5putb)(&m, &pln->adt, sizeof(pln->adt)); cannam@95: X(md5end)(&m); cannam@95: return ego->cost_hook ? ego->cost_hook(p, m.s[0], COST_MAX) : m.s[0]; cannam@95: } cannam@95: cannam@95: #endif cannam@95: cannam@95: double X(iestimate_cost)(const planner *ego, const plan *pln, const problem *p) cannam@95: { cannam@95: double cost = cannam@95: + pln->ops.add cannam@95: + pln->ops.mul cannam@95: cannam@95: #if HAVE_FMA cannam@95: + pln->ops.fma cannam@95: #else cannam@95: + 2 * pln->ops.fma cannam@95: #endif cannam@95: cannam@95: + pln->ops.other; cannam@95: if (ego->cost_hook) cannam@95: cost = ego->cost_hook(p, cost, COST_MAX); cannam@95: return cost; cannam@95: } cannam@95: cannam@95: static void evaluate_plan(planner *ego, plan *pln, const problem *p) cannam@95: { cannam@95: if (ESTIMATEP(ego) || !BELIEVE_PCOSTP(ego) || pln->pcost == 0.0) { cannam@95: ego->nplan++; cannam@95: cannam@95: if (ESTIMATEP(ego)) { cannam@95: estimate: cannam@95: /* heuristic */ cannam@95: #ifdef FFTW_RANDOM_ESTIMATOR cannam@95: pln->pcost = random_estimate(ego, pln, p); cannam@95: ego->epcost += X(iestimate_cost)(ego, pln, p); cannam@95: #else cannam@95: pln->pcost = X(iestimate_cost)(ego, pln, p); cannam@95: ego->epcost += pln->pcost; cannam@95: #endif cannam@95: } else { cannam@95: double t = X(measure_execution_time)(ego, pln, p); cannam@95: cannam@95: if (t < 0) { /* unavailable cycle counter */ cannam@95: /* Real programmers can write FORTRAN in any language */ cannam@95: goto estimate; cannam@95: } cannam@95: cannam@95: pln->pcost = t; cannam@95: ego->pcost += t; cannam@95: ego->need_timeout_check = 1; cannam@95: } cannam@95: } cannam@95: cannam@95: invoke_hook(ego, pln, p, 0); cannam@95: } cannam@95: cannam@95: /* maintain dynamic scoping of flags, nthr: */ cannam@95: static plan *invoke_solver(planner *ego, const problem *p, solver *s, cannam@95: const flags_t *nflags) cannam@95: { cannam@95: flags_t flags = ego->flags; cannam@95: int nthr = ego->nthr; cannam@95: plan *pln; cannam@95: ego->flags = *nflags; cannam@95: PLNR_TIMELIMIT_IMPATIENCE(ego) = 0; cannam@95: A(p->adt->problem_kind == s->adt->problem_kind); cannam@95: pln = s->adt->mkplan(s, p, ego); cannam@95: ego->nthr = nthr; cannam@95: ego->flags = flags; cannam@95: return pln; cannam@95: } cannam@95: cannam@95: /* maintain the invariant TIMED_OUT ==> NEED_TIMEOUT_CHECK */ cannam@95: static int timeout_p(planner *ego, const problem *p) cannam@95: { cannam@95: /* do not timeout when estimating. First, the estimator is the cannam@95: planner of last resort. Second, calling X(elapsed_since)() is cannam@95: slower than estimating */ cannam@95: if (!ESTIMATEP(ego)) { cannam@95: /* do not assume that X(elapsed_since)() is monotonic */ cannam@95: if (ego->timed_out) { cannam@95: A(ego->need_timeout_check); cannam@95: return 1; cannam@95: } cannam@95: cannam@95: if (ego->timelimit >= 0 && cannam@95: X(elapsed_since)(ego, p, ego->start_time) >= ego->timelimit) { cannam@95: ego->timed_out = 1; cannam@95: ego->need_timeout_check = 1; cannam@95: return 1; cannam@95: } cannam@95: } cannam@95: cannam@95: A(!ego->timed_out); cannam@95: ego->need_timeout_check = 0; cannam@95: return 0; cannam@95: } cannam@95: cannam@95: static plan *search0(planner *ego, const problem *p, unsigned *slvndx, cannam@95: const flags_t *flagsp) cannam@95: { cannam@95: plan *best = 0; cannam@95: int best_not_yet_timed = 1; cannam@95: cannam@95: /* Do not start a search if the planner timed out. This check is cannam@95: necessary, lest the relaxation mechanism kick in */ cannam@95: if (timeout_p(ego, p)) cannam@95: return 0; cannam@95: cannam@95: FORALL_SOLVERS_OF_KIND(p->adt->problem_kind, ego, s, sp, { cannam@95: plan *pln; cannam@95: cannam@95: pln = invoke_solver(ego, p, s, flagsp); cannam@95: cannam@95: if (ego->need_timeout_check) cannam@95: if (timeout_p(ego, p)) { cannam@95: X(plan_destroy_internal)(pln); cannam@95: X(plan_destroy_internal)(best); cannam@95: return 0; cannam@95: } cannam@95: cannam@95: if (pln) { cannam@95: /* read COULD_PRUNE_NOW_P because PLN may be destroyed cannam@95: before we use COULD_PRUNE_NOW_P */ cannam@95: int could_prune_now_p = pln->could_prune_now_p; cannam@95: cannam@95: if (best) { cannam@95: if (best_not_yet_timed) { cannam@95: evaluate_plan(ego, best, p); cannam@95: best_not_yet_timed = 0; cannam@95: } cannam@95: evaluate_plan(ego, pln, p); cannam@95: if (pln->pcost < best->pcost) { cannam@95: X(plan_destroy_internal)(best); cannam@95: best = pln; cannam@95: *slvndx = sp - ego->slvdescs; cannam@95: } else { cannam@95: X(plan_destroy_internal)(pln); cannam@95: } cannam@95: } else { cannam@95: best = pln; cannam@95: *slvndx = sp - ego->slvdescs; cannam@95: } cannam@95: cannam@95: if (ALLOW_PRUNINGP(ego) && could_prune_now_p) cannam@95: break; cannam@95: } cannam@95: }); cannam@95: cannam@95: return best; cannam@95: } cannam@95: cannam@95: static plan *search(planner *ego, const problem *p, unsigned *slvndx, cannam@95: flags_t *flagsp) cannam@95: { cannam@95: plan *pln = 0; cannam@95: unsigned i; cannam@95: cannam@95: /* relax impatience in this order: */ cannam@95: static const unsigned relax_tab[] = { cannam@95: 0, /* relax nothing */ cannam@95: NO_VRECURSE, cannam@95: NO_FIXED_RADIX_LARGE_N, cannam@95: NO_SLOW, cannam@95: NO_UGLY cannam@95: }; cannam@95: cannam@95: unsigned l_orig = flagsp->l; cannam@95: unsigned x = flagsp->u; cannam@95: cannam@95: /* guaranteed to be different from X */ cannam@95: unsigned last_x = ~x; cannam@95: cannam@95: for (i = 0; i < sizeof(relax_tab) / sizeof(relax_tab[0]); ++i) { cannam@95: if (LEQ(l_orig, x & ~relax_tab[i])) cannam@95: x = x & ~relax_tab[i]; cannam@95: cannam@95: if (x != last_x) { cannam@95: last_x = x; cannam@95: flagsp->l = x; cannam@95: pln = search0(ego, p, slvndx, flagsp); cannam@95: if (pln) break; cannam@95: } cannam@95: } cannam@95: cannam@95: if (!pln) { cannam@95: /* search [L_ORIG, U] */ cannam@95: if (l_orig != last_x) { cannam@95: last_x = l_orig; cannam@95: flagsp->l = l_orig; cannam@95: pln = search0(ego, p, slvndx, flagsp); cannam@95: } cannam@95: } cannam@95: cannam@95: return pln; cannam@95: } cannam@95: cannam@95: #define CHECK_FOR_BOGOSITY \ cannam@95: if ((ego->bogosity_hook ? \ cannam@95: (ego->wisdom_state = ego->bogosity_hook(ego->wisdom_state, p)) \ cannam@95: : ego->wisdom_state) == WISDOM_IS_BOGUS) \ cannam@95: goto wisdom_is_bogus; cannam@95: cannam@95: static plan *mkplan(planner *ego, const problem *p) cannam@95: { cannam@95: plan *pln; cannam@95: md5 m; cannam@95: unsigned slvndx; cannam@95: flags_t flags_of_solution; cannam@95: solution *sol; cannam@95: solver *s; cannam@95: cannam@95: ASSERT_ALIGNED_DOUBLE; cannam@95: A(LEQ(PLNR_L(ego), PLNR_U(ego))); cannam@95: cannam@95: if (ESTIMATEP(ego)) cannam@95: PLNR_TIMELIMIT_IMPATIENCE(ego) = 0; /* canonical form */ cannam@95: cannam@95: cannam@95: #ifdef FFTW_DEBUG cannam@95: check(&ego->htab_blessed); cannam@95: check(&ego->htab_unblessed); cannam@95: #endif cannam@95: cannam@95: pln = 0; cannam@95: cannam@95: CHECK_FOR_BOGOSITY; cannam@95: cannam@95: ego->timed_out = 0; cannam@95: cannam@95: ++ego->nprob; cannam@95: md5hash(&m, p, ego); cannam@95: cannam@95: flags_of_solution = ego->flags; cannam@95: cannam@95: if (ego->wisdom_state != WISDOM_IGNORE_ALL) { cannam@95: if ((sol = hlookup(ego, m.s, &flags_of_solution))) { cannam@95: /* wisdom is acceptable */ cannam@95: wisdom_state_t owisdom_state = ego->wisdom_state; cannam@95: cannam@95: /* this hook is mainly for MPI, to make sure that cannam@95: wisdom is in sync across all processes for MPI problems */ cannam@95: if (ego->wisdom_ok_hook && !ego->wisdom_ok_hook(p, sol->flags)) cannam@95: goto do_search; /* ignore not-ok wisdom */ cannam@95: cannam@95: slvndx = SLVNDX(sol); cannam@95: cannam@95: if (slvndx == INFEASIBLE_SLVNDX) { cannam@95: if (ego->wisdom_state == WISDOM_IGNORE_INFEASIBLE) cannam@95: goto do_search; cannam@95: else cannam@95: return 0; /* known to be infeasible */ cannam@95: } cannam@95: cannam@95: flags_of_solution = sol->flags; cannam@95: cannam@95: /* inherit blessing either from wisdom cannam@95: or from the planner */ cannam@95: flags_of_solution.hash_info |= BLISS(ego->flags); cannam@95: cannam@95: ego->wisdom_state = WISDOM_ONLY; cannam@95: cannam@95: s = ego->slvdescs[slvndx].slv; cannam@95: if (p->adt->problem_kind != s->adt->problem_kind) cannam@95: goto wisdom_is_bogus; cannam@95: cannam@95: pln = invoke_solver(ego, p, s, &flags_of_solution); cannam@95: cannam@95: CHECK_FOR_BOGOSITY; /* catch error in child solvers */ cannam@95: cannam@95: sol = 0; /* Paranoia: SOL may be dangling after cannam@95: invoke_solver(); make sure we don't accidentally cannam@95: reuse it. */ cannam@95: cannam@95: if (!pln) cannam@95: goto wisdom_is_bogus; cannam@95: cannam@95: ego->wisdom_state = owisdom_state; cannam@95: cannam@95: goto skip_search; cannam@95: } cannam@95: else if (ego->nowisdom_hook) /* for MPI, make sure lack of wisdom */ cannam@95: ego->nowisdom_hook(p); /* is in sync across all processes */ cannam@95: } cannam@95: cannam@95: do_search: cannam@95: /* cannot search in WISDOM_ONLY mode */ cannam@95: if (ego->wisdom_state == WISDOM_ONLY) cannam@95: goto wisdom_is_bogus; cannam@95: cannam@95: flags_of_solution = ego->flags; cannam@95: pln = search(ego, p, &slvndx, &flags_of_solution); cannam@95: CHECK_FOR_BOGOSITY; /* catch error in child solvers */ cannam@95: cannam@95: if (ego->timed_out) { cannam@95: A(!pln); cannam@95: if (PLNR_TIMELIMIT_IMPATIENCE(ego) != 0) { cannam@95: /* record (below) that this plan has failed because of cannam@95: timeout */ cannam@95: flags_of_solution.hash_info |= BLESSING; cannam@95: } else { cannam@95: /* this is not the top-level problem or timeout is not cannam@95: active: record no wisdom. */ cannam@95: return 0; cannam@95: } cannam@95: } else { cannam@95: /* canonicalize to infinite timeout */ cannam@95: flags_of_solution.timelimit_impatience = 0; cannam@95: } cannam@95: cannam@95: skip_search: cannam@95: if (ego->wisdom_state == WISDOM_NORMAL || cannam@95: ego->wisdom_state == WISDOM_ONLY) { cannam@95: if (pln) { cannam@95: hinsert(ego, m.s, &flags_of_solution, slvndx); cannam@95: invoke_hook(ego, pln, p, 1); cannam@95: } else { cannam@95: hinsert(ego, m.s, &flags_of_solution, INFEASIBLE_SLVNDX); cannam@95: } cannam@95: } cannam@95: cannam@95: return pln; cannam@95: cannam@95: wisdom_is_bogus: cannam@95: X(plan_destroy_internal)(pln); cannam@95: ego->wisdom_state = WISDOM_IS_BOGUS; cannam@95: return 0; cannam@95: } cannam@95: cannam@95: static void htab_destroy(hashtab *ht) cannam@95: { cannam@95: X(ifree)(ht->solutions); cannam@95: ht->solutions = 0; cannam@95: ht->nelem = 0U; cannam@95: } cannam@95: cannam@95: static void mkhashtab(hashtab *ht) cannam@95: { cannam@95: ht->nrehash = 0; cannam@95: ht->succ_lookup = ht->lookup = ht->lookup_iter = 0; cannam@95: ht->insert = ht->insert_iter = ht->insert_unknown = 0; cannam@95: cannam@95: ht->solutions = 0; cannam@95: ht->hashsiz = ht->nelem = 0U; cannam@95: hgrow(ht); /* so that hashsiz > 0 */ cannam@95: } cannam@95: cannam@95: /* destroy hash table entries. If FORGET_EVERYTHING, destroy the whole cannam@95: table. If FORGET_ACCURSED, then destroy entries that are not blessed. */ cannam@95: static void forget(planner *ego, amnesia a) cannam@95: { cannam@95: switch (a) { cannam@95: case FORGET_EVERYTHING: cannam@95: htab_destroy(&ego->htab_blessed); cannam@95: mkhashtab(&ego->htab_blessed); cannam@95: /* fall through */ cannam@95: case FORGET_ACCURSED: cannam@95: htab_destroy(&ego->htab_unblessed); cannam@95: mkhashtab(&ego->htab_unblessed); cannam@95: break; cannam@95: default: cannam@95: break; cannam@95: } cannam@95: } cannam@95: cannam@95: /* FIXME: what sort of version information should we write? */ cannam@95: #define WISDOM_PREAMBLE PACKAGE "-" VERSION " " STRINGIZE(X(wisdom)) cannam@95: static const char stimeout[] = "TIMEOUT"; cannam@95: cannam@95: /* tantus labor non sit cassus */ cannam@95: static void exprt(planner *ego, printer *p) cannam@95: { cannam@95: unsigned h; cannam@95: hashtab *ht = &ego->htab_blessed; cannam@95: md5 m; cannam@95: cannam@95: signature_of_configuration(&m, ego); cannam@95: cannam@95: p->print(p, cannam@95: "(" WISDOM_PREAMBLE " #x%M #x%M #x%M #x%M\n", cannam@95: m.s[0], m.s[1], m.s[2], m.s[3]); cannam@95: cannam@95: for (h = 0; h < ht->hashsiz; ++h) { cannam@95: solution *l = ht->solutions + h; cannam@95: if (LIVEP(l)) { cannam@95: const char *reg_nam; cannam@95: int reg_id; cannam@95: cannam@95: if (SLVNDX(l) == INFEASIBLE_SLVNDX) { cannam@95: reg_nam = stimeout; cannam@95: reg_id = 0; cannam@95: } else { cannam@95: slvdesc *sp = ego->slvdescs + SLVNDX(l); cannam@95: reg_nam = sp->reg_nam; cannam@95: reg_id = sp->reg_id; cannam@95: } cannam@95: cannam@95: /* qui salvandos salvas gratis cannam@95: salva me fons pietatis */ cannam@95: p->print(p, " (%s %d #x%x #x%x #x%x #x%M #x%M #x%M #x%M)\n", cannam@95: reg_nam, reg_id, cannam@95: l->flags.l, l->flags.u, l->flags.timelimit_impatience, cannam@95: l->s[0], l->s[1], l->s[2], l->s[3]); cannam@95: } cannam@95: } cannam@95: p->print(p, ")\n"); cannam@95: } cannam@95: cannam@95: /* mors stupebit et natura cannam@95: cum resurget creatura */ cannam@95: static int imprt(planner *ego, scanner *sc) cannam@95: { cannam@95: char buf[MAXNAM + 1]; cannam@95: md5uint sig[4]; cannam@95: unsigned l, u, timelimit_impatience; cannam@95: flags_t flags; cannam@95: int reg_id; cannam@95: unsigned slvndx; cannam@95: hashtab *ht = &ego->htab_blessed; cannam@95: hashtab old; cannam@95: md5 m; cannam@95: cannam@95: if (!sc->scan(sc, cannam@95: "(" WISDOM_PREAMBLE " #x%M #x%M #x%M #x%M\n", cannam@95: sig + 0, sig + 1, sig + 2, sig + 3)) cannam@95: return 0; /* don't need to restore hashtable */ cannam@95: cannam@95: signature_of_configuration(&m, ego); cannam@95: if (m.s[0] != sig[0] || m.s[1] != sig[1] || cannam@95: m.s[2] != sig[2] || m.s[3] != sig[3]) { cannam@95: /* invalid configuration */ cannam@95: return 0; cannam@95: } cannam@95: cannam@95: /* make a backup copy of the hash table (cache the hash) */ cannam@95: { cannam@95: unsigned h, hsiz = ht->hashsiz; cannam@95: old = *ht; cannam@95: old.solutions = (solution *)MALLOC(hsiz * sizeof(solution), HASHT); cannam@95: for (h = 0; h < hsiz; ++h) cannam@95: old.solutions[h] = ht->solutions[h]; cannam@95: } cannam@95: cannam@95: while (1) { cannam@95: if (sc->scan(sc, ")")) cannam@95: break; cannam@95: cannam@95: /* qua resurget ex favilla */ cannam@95: if (!sc->scan(sc, "(%*s %d #x%x #x%x #x%x #x%M #x%M #x%M #x%M)", cannam@95: MAXNAM, buf, ®_id, &l, &u, &timelimit_impatience, cannam@95: sig + 0, sig + 1, sig + 2, sig + 3)) cannam@95: goto bad; cannam@95: cannam@95: if (!strcmp(buf, stimeout) && reg_id == 0) { cannam@95: slvndx = INFEASIBLE_SLVNDX; cannam@95: } else { cannam@95: if (timelimit_impatience != 0) cannam@95: goto bad; cannam@95: cannam@95: slvndx = slookup(ego, buf, reg_id); cannam@95: if (slvndx == INFEASIBLE_SLVNDX) cannam@95: goto bad; cannam@95: } cannam@95: cannam@95: /* inter oves locum praesta */ cannam@95: flags.l = l; cannam@95: flags.u = u; cannam@95: flags.timelimit_impatience = timelimit_impatience; cannam@95: flags.hash_info = BLESSING; cannam@95: cannam@95: CK(flags.l == l); cannam@95: CK(flags.u == u); cannam@95: CK(flags.timelimit_impatience == timelimit_impatience); cannam@95: cannam@95: if (!hlookup(ego, sig, &flags)) cannam@95: hinsert(ego, sig, &flags, slvndx); cannam@95: } cannam@95: cannam@95: X(ifree0)(old.solutions); cannam@95: return 1; cannam@95: cannam@95: bad: cannam@95: /* ``The wisdom of FFTW must be above suspicion.'' */ cannam@95: X(ifree0)(ht->solutions); cannam@95: *ht = old; cannam@95: return 0; cannam@95: } cannam@95: cannam@95: /* cannam@95: * create a planner cannam@95: */ cannam@95: planner *X(mkplanner)(void) cannam@95: { cannam@95: int i; cannam@95: cannam@95: static const planner_adt padt = { cannam@95: register_solver, mkplan, forget, exprt, imprt cannam@95: }; cannam@95: cannam@95: planner *p = (planner *) MALLOC(sizeof(planner), PLANNERS); cannam@95: cannam@95: p->adt = &padt; cannam@95: p->nplan = p->nprob = 0; cannam@95: p->pcost = p->epcost = 0.0; cannam@95: p->hook = 0; cannam@95: p->cost_hook = 0; cannam@95: p->wisdom_ok_hook = 0; cannam@95: p->nowisdom_hook = 0; cannam@95: p->bogosity_hook = 0; cannam@95: p->cur_reg_nam = 0; cannam@95: p->wisdom_state = WISDOM_NORMAL; cannam@95: cannam@95: p->slvdescs = 0; cannam@95: p->nslvdesc = p->slvdescsiz = 0; cannam@95: cannam@95: p->flags.l = 0; cannam@95: p->flags.u = 0; cannam@95: p->flags.timelimit_impatience = 0; cannam@95: p->flags.hash_info = 0; cannam@95: p->nthr = 1; cannam@95: p->need_timeout_check = 1; cannam@95: p->timelimit = -1; cannam@95: cannam@95: mkhashtab(&p->htab_blessed); cannam@95: mkhashtab(&p->htab_unblessed); cannam@95: cannam@95: for (i = 0; i < PROBLEM_LAST; ++i) cannam@95: p->slvdescs_for_problem_kind[i] = -1; cannam@95: cannam@95: return p; cannam@95: } cannam@95: cannam@95: void X(planner_destroy)(planner *ego) cannam@95: { cannam@95: /* destroy hash table */ cannam@95: htab_destroy(&ego->htab_blessed); cannam@95: htab_destroy(&ego->htab_unblessed); cannam@95: cannam@95: /* destroy solvdesc table */ cannam@95: FORALL_SOLVERS(ego, s, sp, { cannam@95: UNUSED(sp); cannam@95: X(solver_destroy)(s); cannam@95: }); cannam@95: cannam@95: X(ifree0)(ego->slvdescs); cannam@95: X(ifree)(ego); /* dona eis requiem */ cannam@95: } cannam@95: cannam@95: plan *X(mkplan_d)(planner *ego, problem *p) cannam@95: { cannam@95: plan *pln = ego->adt->mkplan(ego, p); cannam@95: X(problem_destroy)(p); cannam@95: return pln; cannam@95: } cannam@95: cannam@95: /* like X(mkplan_d), but sets/resets flags as well */ cannam@95: plan *X(mkplan_f_d)(planner *ego, problem *p, cannam@95: unsigned l_set, unsigned u_set, unsigned u_reset) cannam@95: { cannam@95: flags_t oflags = ego->flags; cannam@95: plan *pln; cannam@95: cannam@95: PLNR_U(ego) &= ~u_reset; cannam@95: PLNR_L(ego) &= ~u_reset; cannam@95: PLNR_L(ego) |= l_set; cannam@95: PLNR_U(ego) |= u_set | l_set; cannam@95: pln = X(mkplan_d)(ego, p); cannam@95: ego->flags = oflags; cannam@95: return pln; cannam@95: } cannam@95: cannam@95: /* cannam@95: * Debugging code: cannam@95: */ cannam@95: #ifdef FFTW_DEBUG cannam@95: static void check(hashtab *ht) cannam@95: { cannam@95: unsigned live = 0; cannam@95: unsigned i; cannam@95: cannam@95: A(ht->nelem < ht->hashsiz); cannam@95: cannam@95: for (i = 0; i < ht->hashsiz; ++i) { cannam@95: solution *l = ht->solutions + i; cannam@95: if (LIVEP(l)) cannam@95: ++live; cannam@95: } cannam@95: cannam@95: A(ht->nelem == live); cannam@95: cannam@95: for (i = 0; i < ht->hashsiz; ++i) { cannam@95: solution *l1 = ht->solutions + i; cannam@95: int foundit = 0; cannam@95: if (LIVEP(l1)) { cannam@95: unsigned g, h = h1(ht, l1->s), d = h2(ht, l1->s); cannam@95: cannam@95: g = h; cannam@95: do { cannam@95: solution *l = ht->solutions + g; cannam@95: if (VALIDP(l)) { cannam@95: if (l1 == l) cannam@95: foundit = 1; cannam@95: else if (LIVEP(l) && md5eq(l1->s, l->s)) { cannam@95: A(!subsumes(&l->flags, SLVNDX(l), &l1->flags)); cannam@95: A(!subsumes(&l1->flags, SLVNDX(l1), &l->flags)); cannam@95: } cannam@95: } else cannam@95: break; cannam@95: g = addmod(g, d, ht->hashsiz); cannam@95: } while (g != h); cannam@95: cannam@95: A(foundit); cannam@95: } cannam@95: } cannam@95: } cannam@95: #endif