planner.c

/*
 * Copyright (c) 2000 Matteo Frigo
 * Copyright (c) 2000 Massachusetts Institute of Technology
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
 *
 */

#include "kernel/ifftw.h"
#include <string.h>

/* GNU Coding Standards, Sec. 5.2: "Please write the comments in a GNU
   program in English, because English is the one language that nearly
   all programmers in all countries can read."

                    ingemisco tanquam reus
		    culpa rubet vultus meus
		    supplicanti parce [rms]
*/

#define VALIDP(solution) ((solution)->flags.hash_info & H_VALID)
#define LIVEP(solution) ((solution)->flags.hash_info & H_LIVE)
#define SLVNDX(solution) ((solution)->flags.slvndx)
#define BLISS(flags) (((flags).hash_info) & BLESSING)
#define INFEASIBLE_SLVNDX ((1U<<BITS_FOR_SLVNDX)-1)


#define MAXNAM 64  /* maximum length of registrar's name.
		      Used for reading wisdom.  There is no point
		      in doing this right */


#ifdef FFTW_DEBUG
static void check(hashtab *ht);
#endif

/* x <= y */
#define LEQ(x, y) (((x) & (y)) == (x))

/* A subsumes B */
static int subsumes(const flags_t *a, unsigned slvndx_a, const flags_t *b)
{
     if (slvndx_a != INFEASIBLE_SLVNDX) {
	  A(a->timelimit_impatience == 0);
	  return (LEQ(a->u, b->u) && LEQ(b->l, a->l));
     } else {
	  return (LEQ(a->l, b->l) 
		  && a->timelimit_impatience <= b->timelimit_impatience);
     }
}

static unsigned addmod(unsigned a, unsigned b, unsigned p)
{
     /* gcc-2.95/sparc produces incorrect code for the fast version below. */
#if defined(__sparc__) && defined(__GNUC__)
     /* slow version  */
     return (a + b) % p;
#else
     /* faster version */
     unsigned c = a + b;
     return c >= p ? c - p : c;
#endif
}

/*
  slvdesc management:
*/
static void sgrow(planner *ego)
{
     unsigned osiz = ego->slvdescsiz, nsiz = 1 + osiz + osiz / 4;
     slvdesc *ntab = (slvdesc *)MALLOC(nsiz * sizeof(slvdesc), SLVDESCS);
     slvdesc *otab = ego->slvdescs;
     unsigned i;

     ego->slvdescs = ntab;
     ego->slvdescsiz = nsiz;
     for (i = 0; i < osiz; ++i)
	  ntab[i] = otab[i];
     X(ifree0)(otab);
}

static void register_solver(planner *ego, solver *s)
{
     slvdesc *n;
     int kind;

     if (s) { /* add s to solver list */
	  X(solver_use)(s);

	  A(ego->nslvdesc < INFEASIBLE_SLVNDX);
	  if (ego->nslvdesc >= ego->slvdescsiz)
	       sgrow(ego);

	  n = ego->slvdescs + ego->nslvdesc;

	  n->slv = s;
	  n->reg_nam = ego->cur_reg_nam;
	  n->reg_id = ego->cur_reg_id++;
	  
	  A(strlen(n->reg_nam) < MAXNAM);
	  n->nam_hash = X(hash)(n->reg_nam);

	  kind = s->adt->problem_kind;
	  n->next_for_same_problem_kind = ego->slvdescs_for_problem_kind[kind];
	  ego->slvdescs_for_problem_kind[kind] = (int)/*from unsigned*/ego->nslvdesc;

	  ego->nslvdesc++;
     }
}

static unsigned slookup(planner *ego, char *nam, int id)
{
     unsigned h = X(hash)(nam); /* used to avoid strcmp in the common case */
     FORALL_SOLVERS(ego, s, sp, {
	  UNUSED(s);
	  if (sp->reg_id == id && sp->nam_hash == h
	      && !strcmp(sp->reg_nam, nam))
	       return (unsigned)/*from ptrdiff_t*/(sp - ego->slvdescs);
     });
     return INFEASIBLE_SLVNDX;
}

/* Compute a MD5 hash of the configuration of the planner.
   We store it into the wisdom file to make absolutely sure that
   we are reading wisdom that is applicable */
static void signature_of_configuration(md5 *m, planner *ego)
{
     X(md5begin)(m);
     X(md5unsigned)(m, sizeof(R)); /* so we don't mix different precisions */
     FORALL_SOLVERS(ego, s, sp, {
	  UNUSED(s);
	  X(md5int)(m, sp->reg_id);
	  X(md5puts)(m, sp->reg_nam);
     });
     X(md5end)(m);
}

/*
  md5-related stuff:
*/

/* first hash function */
static unsigned h1(const hashtab *ht, const md5sig s)
{
     unsigned h = s[0] % ht->hashsiz;
     A(h == (s[0] % ht->hashsiz));
     return h;
}

/* second hash function (for double hashing) */
static unsigned h2(const hashtab *ht, const md5sig s)
{
     unsigned h = 1U + s[1] % (ht->hashsiz - 1);
     A(h == (1U + s[1] % (ht->hashsiz - 1)));
     return h;
}

static void md5hash(md5 *m, const problem *p, const planner *plnr)
{
     X(md5begin)(m);
     X(md5unsigned)(m, sizeof(R)); /* so we don't mix different precisions */
     X(md5int)(m, plnr->nthr);
     p->adt->hash(p, m);
     X(md5end)(m);
}

static int md5eq(const md5sig a, const md5sig b)
{
     return a[0] == b[0] && a[1] == b[1] && a[2] == b[2] && a[3] == b[3];
}

static void sigcpy(const md5sig a, md5sig b)
{
     b[0] = a[0]; b[1] = a[1]; b[2] = a[2]; b[3] = a[3];
}

/*
  memoization routines :
*/

/*
   liber scriptus proferetur
   in quo totum continetur
   unde mundus iudicetur
*/
struct solution_s {
     md5sig s;
     flags_t flags;
};

static solution *htab_lookup(hashtab *ht, const md5sig s, 
			     const flags_t *flagsp)
{
     unsigned g, h = h1(ht, s), d = h2(ht, s);
     solution *best = 0;

     ++ht->lookup;

     /* search all entries that match; select the one with
	the lowest flags.u */
     /* This loop may potentially traverse the whole table, since at
	least one element is guaranteed to be !LIVEP, but all elements
	may be VALIDP.  Hence, we stop after at the first invalid
	element or after traversing the whole table. */
     g = h;
     do {
	  solution *l = ht->solutions + g;
	  ++ht->lookup_iter;
	  if (VALIDP(l)) {
	       if (LIVEP(l)
		   && md5eq(s, l->s)
		   && subsumes(&l->flags, SLVNDX(l), flagsp) ) { 
		    if (!best || LEQ(l->flags.u, best->flags.u))
			 best = l;
	       }
	  } else 
	       break;

	  g = addmod(g, d, ht->hashsiz);
     } while (g != h);

     if (best) 
	  ++ht->succ_lookup;
     return best;
}

static solution *hlookup(planner *ego, const md5sig s, 
			 const flags_t *flagsp)
{
     solution *sol = htab_lookup(&ego->htab_blessed, s, flagsp);
     if (!sol) sol = htab_lookup(&ego->htab_unblessed, s, flagsp);
     return sol;
}

static void fill_slot(hashtab *ht, const md5sig s, const flags_t *flagsp,
		      unsigned slvndx, solution *slot)
{
     ++ht->insert;
     ++ht->nelem;
     A(!LIVEP(slot));
     slot->flags.u = flagsp->u;
     slot->flags.l = flagsp->l;
     slot->flags.timelimit_impatience = flagsp->timelimit_impatience;
     slot->flags.hash_info |= H_VALID | H_LIVE;
     SLVNDX(slot) = slvndx;

     /* keep this check enabled in case we add so many solvers
	that the bitfield overflows */
     CK(SLVNDX(slot) == slvndx);     
     sigcpy(s, slot->s);
}

static void kill_slot(hashtab *ht, solution *slot)
{
     A(LIVEP(slot)); /* ==> */ A(VALIDP(slot));

     --ht->nelem;
     slot->flags.hash_info = H_VALID;
}

static void hinsert0(hashtab *ht, const md5sig s, const flags_t *flagsp, 
		     unsigned slvndx)
{
     solution *l;
     unsigned g, h = h1(ht, s), d = h2(ht, s); 

     ++ht->insert_unknown;

     /* search for nonfull slot */
     for (g = h; ; g = addmod(g, d, ht->hashsiz)) {
	  ++ht->insert_iter;
	  l = ht->solutions + g;
	  if (!LIVEP(l)) break;
	  A((g + d) % ht->hashsiz != h);
     }

     fill_slot(ht, s, flagsp, slvndx, l);
}

static void rehash(hashtab *ht, unsigned nsiz)
{
     unsigned osiz = ht->hashsiz, h;
     solution *osol = ht->solutions, *nsol;

     nsiz = (unsigned)X(next_prime)((INT)nsiz);
     nsol = (solution *)MALLOC(nsiz * sizeof(solution), HASHT);
     ++ht->nrehash;

     /* init new table */
     for (h = 0; h < nsiz; ++h) 
	  nsol[h].flags.hash_info = 0;

     /* install new table */
     ht->hashsiz = nsiz;
     ht->solutions = nsol;
     ht->nelem = 0;

     /* copy table */
     for (h = 0; h < osiz; ++h) {
	  solution *l = osol + h;
	  if (LIVEP(l))
	       hinsert0(ht, l->s, &l->flags, SLVNDX(l));
     }

     X(ifree0)(osol);
}

static unsigned minsz(unsigned nelem)
{
     return 1U + nelem + nelem / 8U;
}

static unsigned nextsz(unsigned nelem)
{
     return minsz(minsz(nelem));
}

static void hgrow(hashtab *ht)
{
     unsigned nelem = ht->nelem;
     if (minsz(nelem) >= ht->hashsiz)
	  rehash(ht, nextsz(nelem));
}

#if 0
/* shrink the hash table, never used */
static void hshrink(hashtab *ht)
{
     unsigned nelem = ht->nelem;
     /* always rehash after deletions */
     rehash(ht, nextsz(nelem));
}
#endif

static void htab_insert(hashtab *ht, const md5sig s, const flags_t *flagsp,
			unsigned slvndx)
{
     unsigned g, h = h1(ht, s), d = h2(ht, s);
     solution *first = 0;

     /* Remove all entries that are subsumed by the new one.  */
     /* This loop may potentially traverse the whole table, since at
	least one element is guaranteed to be !LIVEP, but all elements
	may be VALIDP.  Hence, we stop after at the first invalid
	element or after traversing the whole table. */
     g = h;
     do {
	  solution *l = ht->solutions + g;
	  ++ht->insert_iter;
	  if (VALIDP(l)) {
	       if (LIVEP(l) && md5eq(s, l->s)) {
		    if (subsumes(flagsp, slvndx, &l->flags)) {
			 if (!first) first = l;
			 kill_slot(ht, l);
		    } else {
			 /* It is an error to insert an element that
			    is subsumed by an existing entry. */
			 A(!subsumes(&l->flags, SLVNDX(l), flagsp));
		    }
	       }
	  } else 
	       break;

	  g = addmod(g, d, ht->hashsiz);
     } while (g != h);

     if (first) {
	  /* overwrite FIRST */
	  fill_slot(ht, s, flagsp, slvndx, first);
     } else {
	  /* create a new entry */
 	  hgrow(ht);
	  hinsert0(ht, s, flagsp, slvndx);
     }
}

static void hinsert(planner *ego, const md5sig s, const flags_t *flagsp, 
		    unsigned slvndx)
{
     htab_insert(BLISS(*flagsp) ? &ego->htab_blessed : &ego->htab_unblessed,
		 s, flagsp, slvndx );
}


static void invoke_hook(planner *ego, plan *pln, const problem *p, 
			int optimalp)
{
     if (ego->hook)
	  ego->hook(ego, pln, p, optimalp);
}

#ifdef FFTW_RANDOM_ESTIMATOR
/* a "random" estimate, used for debugging to generate "random"
   plans, albeit from a deterministic seed. */

unsigned X(random_estimate_seed) = 0;

static double random_estimate(const planner *ego, const plan *pln, 
			      const problem *p)
{
     md5 m;
     X(md5begin)(&m);
     X(md5unsigned)(&m, X(random_estimate_seed));
     X(md5int)(&m, ego->nthr);
     p->adt->hash(p, &m);
     X(md5putb)(&m, &pln->ops, sizeof(pln->ops));
     X(md5putb)(&m, &pln->adt, sizeof(pln->adt));
     X(md5end)(&m);
     return ego->cost_hook ? ego->cost_hook(p, m.s[0], COST_MAX) : m.s[0];
}

#endif

double X(iestimate_cost)(const planner *ego, const plan *pln, const problem *p)
{
     double cost =
	  + pln->ops.add
	  + pln->ops.mul
	  
#if HAVE_FMA
	  + pln->ops.fma
#else
	  + 2 * pln->ops.fma
#endif
	  
	  + pln->ops.other;
     if (ego->cost_hook)
	  cost = ego->cost_hook(p, cost, COST_MAX);
     return cost;
}

static void evaluate_plan(planner *ego, plan *pln, const problem *p)
{
     if (ESTIMATEP(ego) || !BELIEVE_PCOSTP(ego) || pln->pcost == 0.0) {
	  ego->nplan++;

	  if (ESTIMATEP(ego)) {
	  estimate:
	       /* heuristic */
#ifdef FFTW_RANDOM_ESTIMATOR
	       pln->pcost = random_estimate(ego, pln, p);
	       ego->epcost += X(iestimate_cost)(ego, pln, p);
#else
	       pln->pcost = X(iestimate_cost)(ego, pln, p);
	       ego->epcost += pln->pcost;
#endif
	  } else {
	       double t = X(measure_execution_time)(ego, pln, p);
	       
	       if (t < 0) {  /* unavailable cycle counter */
		    /* Real programmers can write FORTRAN in any language */
		    goto estimate;
	       }

	       pln->pcost = t;
	       ego->pcost += t;
	       ego->need_timeout_check = 1;
	  }
     }
     
     invoke_hook(ego, pln, p, 0);
}

/* maintain dynamic scoping of flags, nthr: */
static plan *invoke_solver(planner *ego, const problem *p, solver *s, 
			   const flags_t *nflags)
{
     flags_t flags = ego->flags;
     int nthr = ego->nthr;
     plan *pln;
     ego->flags = *nflags;
     PLNR_TIMELIMIT_IMPATIENCE(ego) = 0;
     A(p->adt->problem_kind == s->adt->problem_kind);
     pln = s->adt->mkplan(s, p, ego);
     ego->nthr = nthr;
     ego->flags = flags;
     return pln;
}

/* maintain the invariant TIMED_OUT ==> NEED_TIMEOUT_CHECK */
static int timeout_p(planner *ego, const problem *p)
{
     /* do not timeout when estimating.  First, the estimator is the
	planner of last resort.  Second, calling X(elapsed_since)() is
	slower than estimating */
     if (!ESTIMATEP(ego)) {
	  /* do not assume that X(elapsed_since)() is monotonic */
	  if (ego->timed_out) {
	       A(ego->need_timeout_check);
	       return 1;
	  }

	  if (ego->timelimit >= 0 &&
	      X(elapsed_since)(ego, p, ego->start_time) >= ego->timelimit) {
	       ego->timed_out = 1;
	       ego->need_timeout_check = 1;
	       return 1;
	  }
     }

     A(!ego->timed_out);
     ego->need_timeout_check = 0;
     return 0;
}

static plan *search0(planner *ego, const problem *p, unsigned *slvndx, 
		     const flags_t *flagsp)
{
     plan *best = 0;
     int best_not_yet_timed = 1;

     /* Do not start a search if the planner timed out. This check is
	necessary, lest the relaxation mechanism kick in */
     if (timeout_p(ego, p))
	  return 0;

     FORALL_SOLVERS_OF_KIND(p->adt->problem_kind, ego, s, sp, {
	  plan *pln;

	  pln = invoke_solver(ego, p, s, flagsp);

	  if (ego->need_timeout_check) 
	       if (timeout_p(ego, p)) {
		    X(plan_destroy_internal)(pln);
		    X(plan_destroy_internal)(best);
		    return 0;
	       }

	  if (pln) {
	       /* read COULD_PRUNE_NOW_P because PLN may be destroyed
		  before we use COULD_PRUNE_NOW_P */
	       int could_prune_now_p = pln->could_prune_now_p;

	       if (best) {
		    if (best_not_yet_timed) {
			 evaluate_plan(ego, best, p);
			 best_not_yet_timed = 0;
		    }
		    evaluate_plan(ego, pln, p);
		    if (pln->pcost < best->pcost) {
			 X(plan_destroy_internal)(best);
			 best = pln;
                         *slvndx = (unsigned)/*from ptrdiff_t*/(sp - ego->slvdescs);
		    } else {
			 X(plan_destroy_internal)(pln);
		    }
	       } else {
		    best = pln;
                    *slvndx = (unsigned)/*from ptrdiff_t*/(sp - ego->slvdescs);                    
	       }

	       if (ALLOW_PRUNINGP(ego) && could_prune_now_p) 
		    break;
	  }
     });

     return best;
}

static plan *search(planner *ego, const problem *p, unsigned *slvndx, 
		    flags_t *flagsp)
{
     plan *pln = 0;
     unsigned i;

     /* relax impatience in this order: */
     static const unsigned relax_tab[] = {
	  0, /* relax nothing */
	  NO_VRECURSE,
	  NO_FIXED_RADIX_LARGE_N,
	  NO_SLOW,
	  NO_UGLY
     };

     unsigned l_orig = flagsp->l;
     unsigned x = flagsp->u;

     /* guaranteed to be different from X */
     unsigned last_x = ~x; 

     for (i = 0; i < sizeof(relax_tab) / sizeof(relax_tab[0]); ++i) {
	  if (LEQ(l_orig, x & ~relax_tab[i]))
	       x = x & ~relax_tab[i];

	  if (x != last_x) {
	       last_x = x;
	       flagsp->l = x;
	       pln = search0(ego, p, slvndx, flagsp);
	       if (pln) break;
	  }
     }

     if (!pln) {
	  /* search [L_ORIG, U] */
	  if (l_orig != last_x) {
	       last_x = l_orig;
	       flagsp->l = l_orig;
	       pln = search0(ego, p, slvndx, flagsp);
	  }
     }

     return pln;
}

#define CHECK_FOR_BOGOSITY						\
     if ((ego->bogosity_hook ?						\
	  (ego->wisdom_state = ego->bogosity_hook(ego->wisdom_state, p)) \
	  : ego->wisdom_state) == WISDOM_IS_BOGUS)			\
	  goto wisdom_is_bogus;

static plan *mkplan(planner *ego, const problem *p)
{
     plan *pln;
     md5 m;
     unsigned slvndx;
     flags_t flags_of_solution;
     solution *sol;
     solver *s;

     ASSERT_ALIGNED_DOUBLE;
     A(LEQ(PLNR_L(ego), PLNR_U(ego)));

     if (ESTIMATEP(ego))
	  PLNR_TIMELIMIT_IMPATIENCE(ego) = 0; /* canonical form */


#ifdef FFTW_DEBUG
     check(&ego->htab_blessed);
     check(&ego->htab_unblessed);
#endif

     pln = 0;

     CHECK_FOR_BOGOSITY;

     ego->timed_out = 0;

     ++ego->nprob;
     md5hash(&m, p, ego);

     flags_of_solution = ego->flags;

     if (ego->wisdom_state != WISDOM_IGNORE_ALL) {
	  if ((sol = hlookup(ego, m.s, &flags_of_solution))) { 
	       /* wisdom is acceptable */
	       wisdom_state_t owisdom_state = ego->wisdom_state;
	       
	       /* this hook is mainly for MPI, to make sure that
		  wisdom is in sync across all processes for MPI problems */
	       if (ego->wisdom_ok_hook && !ego->wisdom_ok_hook(p, sol->flags))
		    goto do_search; /* ignore not-ok wisdom */
	       
	       slvndx = SLVNDX(sol);
	       
	       if (slvndx == INFEASIBLE_SLVNDX) {
		    if (ego->wisdom_state == WISDOM_IGNORE_INFEASIBLE)
			 goto do_search;
		    else
			 return 0;   /* known to be infeasible */
	       }
	       
	       flags_of_solution = sol->flags;
	       
	       /* inherit blessing either from wisdom
		  or from the planner */
	       flags_of_solution.hash_info |= BLISS(ego->flags);
	       
	       ego->wisdom_state = WISDOM_ONLY;
	       
	       s = ego->slvdescs[slvndx].slv;
	       if (p->adt->problem_kind != s->adt->problem_kind)
		    goto wisdom_is_bogus;
	       
	       pln = invoke_solver(ego, p, s, &flags_of_solution);
	       
	       CHECK_FOR_BOGOSITY; 	  /* catch error in child solvers */
	       
	       sol = 0; /* Paranoia: SOL may be dangling after
			   invoke_solver(); make sure we don't accidentally
			   reuse it. */
	       
	       if (!pln)
		    goto wisdom_is_bogus;
	       
	       ego->wisdom_state = owisdom_state;
	       
	       goto skip_search;
	  }
	  else if (ego->nowisdom_hook) /* for MPI, make sure lack of wisdom */
	       ego->nowisdom_hook(p);  /*   is in sync across all processes */
     }

 do_search:
     /* cannot search in WISDOM_ONLY mode */
     if (ego->wisdom_state == WISDOM_ONLY)
	  goto wisdom_is_bogus;

     flags_of_solution = ego->flags;
     pln = search(ego, p, &slvndx, &flags_of_solution);
     CHECK_FOR_BOGOSITY; 	  /* catch error in child solvers */

     if (ego->timed_out) {
	  A(!pln);
	  if (PLNR_TIMELIMIT_IMPATIENCE(ego) != 0) {
	       /* record (below) that this plan has failed because of
		  timeout */
	       flags_of_solution.hash_info |= BLESSING;
	  } else {
	       /* this is not the top-level problem or timeout is not
		  active: record no wisdom. */
	       return 0;
	  }
     } else {
	  /* canonicalize to infinite timeout */
	  flags_of_solution.timelimit_impatience = 0;
     }

 skip_search:
     if (ego->wisdom_state == WISDOM_NORMAL ||
	 ego->wisdom_state == WISDOM_ONLY) {
	  if (pln) {
	       hinsert(ego, m.s, &flags_of_solution, slvndx);
	       invoke_hook(ego, pln, p, 1);
	  } else {
	       hinsert(ego, m.s, &flags_of_solution, INFEASIBLE_SLVNDX);
	  }
     }

     return pln;

 wisdom_is_bogus:
     X(plan_destroy_internal)(pln);
     ego->wisdom_state = WISDOM_IS_BOGUS;
     return 0;
}

static void htab_destroy(hashtab *ht)
{
     X(ifree)(ht->solutions);
     ht->solutions = 0;
     ht->nelem = 0U;
}

static void mkhashtab(hashtab *ht)
{
     ht->nrehash = 0;
     ht->succ_lookup = ht->lookup = ht->lookup_iter = 0;
     ht->insert = ht->insert_iter = ht->insert_unknown = 0;

     ht->solutions = 0;
     ht->hashsiz = ht->nelem = 0U;
     hgrow(ht);			/* so that hashsiz > 0 */
}

/* destroy hash table entries.  If FORGET_EVERYTHING, destroy the whole
   table.  If FORGET_ACCURSED, then destroy entries that are not blessed. */
static void forget(planner *ego, amnesia a)
{
     switch (a) {
	 case FORGET_EVERYTHING:
	      htab_destroy(&ego->htab_blessed);
	      mkhashtab(&ego->htab_blessed);
	      /* fall through */
	 case FORGET_ACCURSED:
	      htab_destroy(&ego->htab_unblessed);
	      mkhashtab(&ego->htab_unblessed);
	      break;
	 default:
	      break;
     }
}

/* FIXME: what sort of version information should we write? */
#define WISDOM_PREAMBLE PACKAGE "-" VERSION " " STRINGIZE(X(wisdom))
static const char stimeout[] = "TIMEOUT";

/* tantus labor non sit cassus */
static void exprt(planner *ego, printer *p)
{
     unsigned h;
     hashtab *ht = &ego->htab_blessed;
     md5 m;

     signature_of_configuration(&m, ego);

     p->print(p, 
	      "(" WISDOM_PREAMBLE " #x%M #x%M #x%M #x%M\n",
	      m.s[0], m.s[1], m.s[2], m.s[3]);

     for (h = 0; h < ht->hashsiz; ++h) {
	  solution *l = ht->solutions + h;
	  if (LIVEP(l)) {
	       const char *reg_nam;
	       int reg_id;

	       if (SLVNDX(l) == INFEASIBLE_SLVNDX) {
		    reg_nam = stimeout;
		    reg_id = 0;
	       } else {
		    slvdesc *sp = ego->slvdescs + SLVNDX(l);
		    reg_nam = sp->reg_nam;
		    reg_id = sp->reg_id;
	       }

	       /* qui salvandos salvas gratis
		  salva me fons pietatis */
	       p->print(p, "  (%s %d #x%x #x%x #x%x #x%M #x%M #x%M #x%M)\n",
			reg_nam, reg_id, 
			l->flags.l, l->flags.u, l->flags.timelimit_impatience, 
			l->s[0], l->s[1], l->s[2], l->s[3]);
	  }
     }
     p->print(p, ")\n");
}

/* mors stupebit et natura
   cum resurget creatura */
static int imprt(planner *ego, scanner *sc)
{
     char buf[MAXNAM + 1];
     md5uint sig[4];
     unsigned l, u, timelimit_impatience;
     flags_t flags;
     int reg_id;
     unsigned slvndx;
     hashtab *ht = &ego->htab_blessed;
     hashtab old;
     md5 m;

     if (!sc->scan(sc, 
		   "(" WISDOM_PREAMBLE " #x%M #x%M #x%M #x%M\n",
		   sig + 0, sig + 1, sig + 2, sig + 3))
	  return 0; /* don't need to restore hashtable */

     signature_of_configuration(&m, ego);
     if (m.s[0] != sig[0] || m.s[1] != sig[1] ||
	 m.s[2] != sig[2] || m.s[3] != sig[3]) {
	  /* invalid configuration */
	  return 0;
     }
     
     /* make a backup copy of the hash table (cache the hash) */
     {
	  unsigned h, hsiz = ht->hashsiz;
	  old = *ht;
	  old.solutions = (solution *)MALLOC(hsiz * sizeof(solution), HASHT);
	  for (h = 0; h < hsiz; ++h)
	       old.solutions[h] = ht->solutions[h];
     }

     while (1) {
	  if (sc->scan(sc, ")"))
	       break;

	  /* qua resurget ex favilla */
	  if (!sc->scan(sc, "(%*s %d #x%x #x%x #x%x #x%M #x%M #x%M #x%M)",
			MAXNAM, buf, &reg_id, &l, &u, &timelimit_impatience,
			sig + 0, sig + 1, sig + 2, sig + 3))
	       goto bad;

	  if (!strcmp(buf, stimeout) && reg_id == 0) {
	       slvndx = INFEASIBLE_SLVNDX;
	  } else {
	       if (timelimit_impatience != 0)
		    goto bad;

	       slvndx = slookup(ego, buf, reg_id);
	       if (slvndx == INFEASIBLE_SLVNDX)
		    goto bad;
	  }

	  /* inter oves locum praesta */
	  flags.l = l;
	  flags.u = u;
	  flags.timelimit_impatience = timelimit_impatience;
	  flags.hash_info = BLESSING;

	  CK(flags.l == l);
	  CK(flags.u == u);
	  CK(flags.timelimit_impatience == timelimit_impatience);

	  if (!hlookup(ego, sig, &flags))
	       hinsert(ego, sig, &flags, slvndx);
     }

     X(ifree0)(old.solutions);
     return 1;

 bad:
     /* ``The wisdom of FFTW must be above suspicion.'' */
     X(ifree0)(ht->solutions);
     *ht = old;
     return 0;
}

/*
 * create a planner
 */
planner *X(mkplanner)(void)
{
     int i;

     static const planner_adt padt = {
	  register_solver, mkplan, forget, exprt, imprt
     };

     planner *p = (planner *) MALLOC(sizeof(planner), PLANNERS);

     p->adt = &padt;
     p->nplan = p->nprob = 0;
     p->pcost = p->epcost = 0.0;
     p->hook = 0;
     p->cost_hook = 0;
     p->wisdom_ok_hook = 0;
     p->nowisdom_hook = 0;
     p->bogosity_hook = 0;
     p->cur_reg_nam = 0;
     p->wisdom_state = WISDOM_NORMAL;

     p->slvdescs = 0;
     p->nslvdesc = p->slvdescsiz = 0;

     p->flags.l = 0;
     p->flags.u = 0;
     p->flags.timelimit_impatience = 0;
     p->flags.hash_info = 0;
     p->nthr = 1;
     p->need_timeout_check = 1;
     p->timelimit = -1;

     mkhashtab(&p->htab_blessed);
     mkhashtab(&p->htab_unblessed);

     for (i = 0; i < PROBLEM_LAST; ++i)
	  p->slvdescs_for_problem_kind[i] = -1;

     return p;
}

void X(planner_destroy)(planner *ego)
{
     /* destroy hash table */
     htab_destroy(&ego->htab_blessed);
     htab_destroy(&ego->htab_unblessed);

     /* destroy solvdesc table */
     FORALL_SOLVERS(ego, s, sp, {
	  UNUSED(sp);
	  X(solver_destroy)(s);
     });

     X(ifree0)(ego->slvdescs);
     X(ifree)(ego); /* dona eis requiem */
}

plan *X(mkplan_d)(planner *ego, problem *p)
{
     plan *pln = ego->adt->mkplan(ego, p);
     X(problem_destroy)(p);
     return pln;
}

/* like X(mkplan_d), but sets/resets flags as well */
plan *X(mkplan_f_d)(planner *ego, problem *p, 
		    unsigned l_set, unsigned u_set, unsigned u_reset)
{
     flags_t oflags = ego->flags;
     plan *pln;

     PLNR_U(ego) &= ~u_reset;
     PLNR_L(ego) &= ~u_reset;
     PLNR_L(ego) |= l_set;
     PLNR_U(ego) |= u_set | l_set;
     pln = X(mkplan_d)(ego, p);
     ego->flags = oflags;
     return pln;
}

/*
 * Debugging code:
 */
#ifdef FFTW_DEBUG
static void check(hashtab *ht)
{
     unsigned live = 0;
     unsigned i;

     A(ht->nelem < ht->hashsiz);

     for (i = 0; i < ht->hashsiz; ++i) {
	  solution *l = ht->solutions + i; 
	  if (LIVEP(l)) 
	       ++live; 
     }

     A(ht->nelem == live);

     for (i = 0; i < ht->hashsiz; ++i) {
	  solution *l1 = ht->solutions + i; 
	  int foundit = 0;
	  if (LIVEP(l1)) {
	       unsigned g, h = h1(ht, l1->s), d = h2(ht, l1->s);

	       g = h;
	       do {
		    solution *l = ht->solutions + g;
		    if (VALIDP(l)) {
			 if (l1 == l)
			      foundit = 1;
			 else if (LIVEP(l) && md5eq(l1->s, l->s)) {
			      A(!subsumes(&l->flags, SLVNDX(l), &l1->flags));
			      A(!subsumes(&l1->flags, SLVNDX(l1), &l->flags));
			 }
		    } else 
			 break;
		    g = addmod(g, d, ht->hashsiz);
	       } while (g != h);

	       A(foundit);
	  }
     }
}
#endif