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