glu-2.2: src/cmuBdd/bddcache.c Source File

00001 /* BDD system cache routines */
00002 
00003 
00004 #include "bddint.h"
00005 
00006 
00007 #define HASH1(d1) ((INT_PTR)d1)
00008 #define HASH2(d1, d2) ((INT_PTR)(d1)+(((INT_PTR)(d2)) << 1))
00009 #define HASH3(d1, d2, d3) ((INT_PTR)(d1)+(((INT_PTR)(d2)) << 1)+(((INT_PTR)(d3)) << 2))
00010 
00011 
00012 static
00013 void
00014 bdd_purge_entry(cmu_bdd_manager bddm, cache_entry *bin)
00015 {
00016   void (*purge_fn)(cmu_bdd_manager, cache_entry);
00017   cache_entry p;
00018 
00019   p= *bin;
00020   purge_fn=bddm->op_cache.purge_fn[TAG(p)];
00021   p=CACHE_POINTER(p);
00022   if (purge_fn)
00023     (*purge_fn)(bddm, p);
00024   bddm->op_cache.entries--;
00025   BDD_FREE_REC(bddm, (pointer)p, sizeof(struct cache_entry_));
00026   *bin=0;
00027 }
00028 
00029 
00030 static
00031 void
00032 bdd_purge_lru(cmu_bdd_manager bddm, cache_entry *bin)
00033 {
00034   if (bin[1])
00035     bdd_purge_entry(bddm, bin+1);
00036   bin[1]=bin[0];
00037 }
00038 
00039 
00040 static
00041 cache_entry
00042 bdd_get_entry(cmu_bdd_manager bddm, int tag, cache_entry *bin)
00043 {
00044   void (*purge_fn)(cmu_bdd_manager, cache_entry);
00045   cache_entry p;
00046 
00047   if (bin[0] && bin[1])
00048     {
00049       p=bin[1];
00050       purge_fn=bddm->op_cache.purge_fn[TAG(p)];
00051       p=CACHE_POINTER(p);
00052       if (purge_fn)
00053         (*purge_fn)(bddm, p);
00054       bddm->op_cache.collisions++;
00055       if (bddm->op_cache.cache_level == 0)
00056         bin[1]=bin[0];
00057       else
00058         ++bin;
00059     }
00060   else
00061     {
00062       p=(cache_entry)BDD_NEW_REC(bddm, sizeof(struct cache_entry_));
00063       bddm->op_cache.entries++;
00064       if (bin[0])
00065         ++bin;
00066     }
00067   *bin=(cache_entry)SET_TAG(p, tag);
00068   return (p);
00069 }
00070 
00071 
00072 static
00073 long
00074 bdd_rehash1(cmu_bdd_manager bddm, cache_entry p)
00075 {
00076   return (HASH1(p->slot[0]));
00077 }
00078 
00079 
00080 static
00081 long
00082 bdd_rehash2(cmu_bdd_manager bddm, cache_entry p)
00083 {
00084   return (HASH2(p->slot[0], p->slot[1]));
00085 }
00086 
00087 
00088 static
00089 long
00090 bdd_rehash3(cmu_bdd_manager bddm, cache_entry p)
00091 {
00092   return (HASH3(p->slot[0], p->slot[1], p->slot[2]));
00093 }
00094 
00095 
00096 void
00097 bdd_rehash_cache(cmu_bdd_manager bddm, int grow)
00098 {
00099   long i;
00100   long hash;
00101   int j;
00102   long oldsize;
00103   cache_bin *newtable;
00104   cache_entry *bin;
00105   cache_entry *newbin;
00106   cache_entry p;
00107   cache_entry q;
00108 
00109   oldsize=bddm->op_cache.size;
00110   if (grow)
00111     bddm->op_cache.size_index++;
00112   else
00113     bddm->op_cache.size_index--;
00114   bddm->op_cache.size=TABLE_SIZE(bddm->op_cache.size_index);
00115   newtable=(cache_bin *)mem_get_block((SIZE_T)(bddm->op_cache.size*sizeof(struct cache_bin_)));
00116   for (i=0; i < bddm->op_cache.size; ++i)
00117     for (j=0; j < 2; ++j)
00118       newtable[i].entry[j]=0;
00119   /* Rehash LRU first. */
00120   for (j=1; j >= 0; --j)
00121     for (i=0; i < oldsize; ++i)
00122       {
00123         bin=bddm->op_cache.table[i].entry;
00124         if ((p=bin[j]))
00125           {
00126             q=CACHE_POINTER(p);
00127             hash=(*bddm->op_cache.rehash_fn[TAG(p)])(bddm, q);
00128             BDD_REDUCE(hash, bddm->op_cache.size);
00129             newbin=newtable[hash].entry;
00130             bdd_purge_lru(bddm, newbin);
00131             newbin[0]=p;
00132           }
00133     }
00134   mem_free_block((pointer)(bddm->op_cache.table));
00135   bddm->op_cache.table=newtable;
00136 }
00137 
00138 
00139 /* The routines bdd_insert_in_cachex insert things in the cache. */
00140 /* The routines bdd_lookup_in_cachex look up things in the cache. */
00141 
00142 void
00143 bdd_insert_in_cache31(cmu_bdd_manager bddm, int tag, INT_PTR d1, INT_PTR d2, INT_PTR d3, INT_PTR result)
00144 {
00145   long hash;
00146   cache_entry p;
00147 
00148   hash=HASH3(d1, d2, d3);
00149   BDD_REDUCE(hash, bddm->op_cache.size);
00150   if (hash < 0)
00151     hash= -hash;
00152   p=bdd_get_entry(bddm, tag, bddm->op_cache.table[hash].entry);
00153   p->slot[0]=d1;
00154   p->slot[1]=d2;
00155   p->slot[2]=d3;
00156   p->slot[3]=result;
00157   bddm->op_cache.inserts++;
00158 }
00159 
00160 
00161 #define RETURN_BDD_FN ((void (*)(cmu_bdd_manager, cache_entry))-1)
00162 
00163 
00164 int
00165 bdd_lookup_in_cache31(cmu_bdd_manager bddm, int tag, INT_PTR d1, INT_PTR d2, INT_PTR d3, INT_PTR *result)
00166 {
00167   long hash;
00168   cache_entry *bin;
00169   cache_entry p;
00170   cache_entry q;
00171   bdd f;
00172   void (*return_fn)(cmu_bdd_manager, cache_entry);
00173 
00174   bddm->op_cache.lookups++;
00175   hash=HASH3(d1, d2, d3);
00176   BDD_REDUCE(hash, bddm->op_cache.size);
00177   bin=bddm->op_cache.table[hash].entry;
00178   if ((p=bin[0]))
00179     {
00180       q=CACHE_POINTER(p);
00181       if (q->slot[0] != d1 || q->slot[1] != d2 || q->slot[2] != d3 || TAG(p) != tag)
00182         {
00183         if ((p=bin[1]))
00184           {
00185             q=CACHE_POINTER(p);
00186             if (q->slot[0] != d1 || q->slot[1] != d2 || q->slot[2] != d3 || TAG(p) != tag)
00187               return (0);
00188             bin[1]=bin[0];
00189             bin[0]=p;
00190           }
00191         else
00192           return (0);
00193         }
00194     }
00195   else
00196     return (0);
00197   bddm->op_cache.hits++;
00198   if ((return_fn=bddm->op_cache.return_fn[TAG(p)]))
00199     {
00200     if (return_fn == RETURN_BDD_FN)
00201       {
00202         f=(bdd)q->slot[3];
00203         {
00204           BDD_SETUP(f);
00205           BDD_TEMP_INCREFS(f);
00206         }
00207       }
00208     else
00209       (*return_fn)(bddm, q);
00210     }
00211   *result=q->slot[3];
00212   return (1);
00213 }
00214 
00215 
00216 void
00217 bdd_insert_in_cache22(cmu_bdd_manager bddm, int tag, INT_PTR d1, INT_PTR d2, INT_PTR result1, INT_PTR result2)
00218 {
00219   long hash;
00220   cache_entry p;
00221 
00222   hash=HASH2(d1, d2);
00223   BDD_REDUCE(hash, bddm->op_cache.size);
00224   p=bdd_get_entry(bddm, tag, bddm->op_cache.table[hash].entry);
00225   p->slot[0]=d1;
00226   p->slot[1]=d2;
00227   p->slot[2]=result1;
00228   p->slot[3]=result2;
00229   bddm->op_cache.inserts++;
00230 }
00231 
00232 
00233 int
00234 bdd_lookup_in_cache22(cmu_bdd_manager bddm, int tag, INT_PTR d1, INT_PTR d2, INT_PTR *result1, INT_PTR *result2)
00235 {
00236   long hash;
00237   cache_entry *bin;
00238   cache_entry p;
00239   cache_entry q;
00240   void (*return_fn)(cmu_bdd_manager, cache_entry);
00241 
00242   bddm->op_cache.lookups++;
00243   hash=HASH2(d1, d2);
00244   BDD_REDUCE(hash, bddm->op_cache.size);
00245   bin=bddm->op_cache.table[hash].entry;
00246   if ((p=bin[0]))
00247     {
00248       q=CACHE_POINTER(p);
00249       if (q->slot[0] != d1 || q->slot[1] != d2 || TAG(p) != tag)
00250         {
00251         if ((p=bin[1]))
00252           {
00253             q=CACHE_POINTER(p);
00254             if (q->slot[0] != d1 || q->slot[1] != d2 || TAG(p) != tag)
00255               return (0);
00256             bin[1]=bin[0];
00257             bin[0]=p;
00258           }
00259         else
00260           return (0);
00261         }
00262     }
00263   else
00264     return (0);
00265   bddm->op_cache.hits++;
00266   if ((return_fn=bddm->op_cache.return_fn[TAG(p)]))
00267     (*return_fn)(bddm, q);
00268   *result1=q->slot[2];
00269   *result2=q->slot[3];
00270   return (1);
00271 }
00272 
00273 
00274 void
00275 bdd_insert_in_cache13(cmu_bdd_manager bddm, int tag, INT_PTR d1, INT_PTR result1, INT_PTR result2, INT_PTR result3)
00276 {
00277   long hash;
00278   cache_entry p;
00279 
00280   hash=HASH1(d1);
00281   BDD_REDUCE(hash, bddm->op_cache.size);
00282   p=bdd_get_entry(bddm, tag, bddm->op_cache.table[hash].entry);
00283   p->slot[0]=d1;
00284   p->slot[1]=result1;
00285   p->slot[2]=result2;
00286   p->slot[3]=result3;
00287   bddm->op_cache.inserts++;
00288 }
00289 
00290 
00291 int
00292 bdd_lookup_in_cache13(cmu_bdd_manager bddm, int tag, INT_PTR d1, INT_PTR *result1, INT_PTR *result2, INT_PTR *result3)
00293 {
00294   long hash;
00295   cache_entry *bin;
00296   cache_entry p;
00297   cache_entry q;
00298   void (*return_fn)(cmu_bdd_manager, cache_entry);
00299 
00300   bddm->op_cache.lookups++;
00301   hash=HASH1(d1);
00302   BDD_REDUCE(hash, bddm->op_cache.size);
00303   bin=bddm->op_cache.table[hash].entry;
00304   if ((p=bin[0]))
00305     {
00306       q=CACHE_POINTER(p);
00307       if (q->slot[0] != d1 || TAG(p) != tag)
00308         {
00309         if ((p=bin[1]))
00310           {
00311             q=CACHE_POINTER(p);
00312             if (q->slot[0] != d1 || TAG(p) != tag)
00313               return (0);
00314             bin[1]=bin[0];
00315             bin[0]=p;
00316           }
00317         else
00318           return (0);
00319         }
00320     }
00321   else
00322     return (0);
00323   bddm->op_cache.hits++;
00324   if ((return_fn=bddm->op_cache.return_fn[TAG(p)]))
00325     (*return_fn)(bddm, q);
00326   *result1=q->slot[1];
00327   *result2=q->slot[2];
00328   *result3=q->slot[3];
00329   return (1);
00330 }
00331 
00332 
00333 static
00334 int
00335 cmu_bdd_ite_gc_fn(cmu_bdd_manager bddm, cache_entry p)
00336 {
00337   int i;
00338   bdd f;
00339 
00340   for (i=0; i < 4; ++i)
00341     {
00342       f=(bdd)p->slot[i];
00343       {
00344         BDD_SETUP(f);
00345         if (!BDD_IS_USED(f))
00346           return (1);
00347       }
00348     }
00349   return (0);
00350 }
00351 
00352 
00353 static
00354 int
00355 bdd_two_gc_fn(cmu_bdd_manager bddm, cache_entry p)
00356 {
00357   int i;
00358   bdd f;
00359 
00360   for (i=1; i < 4; ++i)
00361     {
00362       f=(bdd)p->slot[i];
00363       {
00364         BDD_SETUP(f);
00365         if (!BDD_IS_USED(f))
00366           return (1);
00367       }
00368     }
00369   return (0);
00370 }
00371 
00372 
00373 static
00374 int
00375 bdd_two_data_gc_fn(cmu_bdd_manager bddm, cache_entry p)
00376 {
00377   int i;
00378   bdd f;
00379 
00380   for (i=1; i < 3; ++i)
00381     {
00382       f=(bdd)p->slot[i];
00383       {
00384         BDD_SETUP(f);
00385         if (!BDD_IS_USED(f))
00386           return (1);
00387       }
00388     }
00389   return (0);
00390 }
00391 
00392 
00393 static
00394 int
00395 cmu_bdd_one_data_gc_fn(cmu_bdd_manager bddm, cache_entry p)
00396 {
00397   bdd f;
00398 
00399   f=(bdd)p->slot[1];
00400   {
00401     BDD_SETUP(f);
00402     return (!BDD_IS_USED(f));
00403   }
00404 }
00405 
00406 
00407 /* bdd_purge_cache(bddm) purges the cache of any entries which mention */
00408 /* a BDD node that is about to be garbage collected. */
00409 
00410 void
00411 bdd_purge_cache(cmu_bdd_manager bddm)
00412 {
00413   long i;
00414   int j;
00415   cache_entry *bin;
00416   cache_entry p;
00417   cache_entry q;
00418 
00419   for (i=0; i < bddm->op_cache.size; ++i)
00420     {
00421       bin= &bddm->op_cache.table[i].entry[0];
00422       for (j=0; j < 2; ++j)
00423         if ((p=bin[j]))
00424           {
00425             q=CACHE_POINTER(p);
00426             if ((*bddm->op_cache.gc_fn[TAG(p)])(bddm, q))
00427               bdd_purge_entry(bddm, bin+j);
00428             else if (j == 1 && !bin[0])
00429               {
00430                 bin[0]=bin[1];  /* LRU is only one left */
00431                 bin[1]=0;
00432               }
00433           }
00434         else
00435           break;
00436     }
00437 }
00438 
00439 
00440 /* bdd_flush_cache(bddm, flush_fn, closure) purges all entries for which */
00441 /* the given function returns true. */
00442 
00443 void
00444 bdd_flush_cache(cmu_bdd_manager bddm, int (*flush_fn)(cmu_bdd_manager, cache_entry, pointer), pointer closure)
00445 {
00446   long i;
00447   int j;
00448   cache_entry *bin;
00449 
00450   for (i=0; i < bddm->op_cache.size; ++i)
00451     {
00452       bin=bddm->op_cache.table[i].entry;
00453       for (j=0; j < 2; ++j)
00454         if (bin[j])
00455           {
00456             if ((*flush_fn)(bddm, bin[j], closure))
00457               bdd_purge_entry(bddm, bin+j);
00458             else if (j == 1 && !bin[0])
00459               {
00460                 bin[0]=bin[1];  /* LRU is only one left */
00461                 bin[1]=0;
00462               }
00463           }
00464         else
00465           break;
00466     }
00467 }
00468 
00469 
00470 /* bdd_flush_all(bddm) flushes the entire cache. */
00471 
00472 void
00473 bdd_flush_all(cmu_bdd_manager bddm)
00474 {
00475   long i;
00476   int j;
00477   cache_entry *bin;
00478 
00479   for (i=0; i < bddm->op_cache.size; ++i)
00480     {
00481       bin=bddm->op_cache.table[i].entry;
00482       for (j=0; j < 2; ++j)
00483         if (bin[j])
00484           bdd_purge_entry(bddm, bin+j);
00485         else
00486           break;
00487     }
00488 }
00489 
00490 
00491 /* bdd_cache_functions(bddm, args, gc_fn, purge_fn, return_fn, flush_fn) */
00492 /* controls the user cache types.  Allocates an unused cache entry type */
00493 /* tag and returns the tag, or -1 if no more tags are available. */
00494 
00495 int
00496 bdd_cache_functions(cmu_bdd_manager bddm,
00497                     int args,
00498                     int (*gc_fn)(cmu_bdd_manager, cache_entry),
00499                     void (*purge_fn)(cmu_bdd_manager, cache_entry),
00500                     void (*return_fn)(cmu_bdd_manager, cache_entry),
00501                     int (*flush_fn)(cmu_bdd_manager, cache_entry, pointer))
00502 {
00503   long (*rehash_fn)(cmu_bdd_manager, cache_entry);
00504   int i;
00505 
00506   if (args == 1)
00507     rehash_fn=bdd_rehash1;
00508   else if (args == 2)
00509     rehash_fn=bdd_rehash2;
00510   else if (args == 3)
00511     rehash_fn=bdd_rehash3;
00512   else
00513     {
00514       rehash_fn=0;
00515       cmu_bdd_fatal("bdd_cache_functions: illegal number of cache arguments");
00516     }
00517   for (i=CACHE_TYPE_USER1; i < CACHE_TYPE_USER1+USER_ENTRY_TYPES; ++i)
00518     if (!bddm->op_cache.rehash_fn[i])
00519       break;
00520   if (i == CACHE_TYPE_USER1+USER_ENTRY_TYPES)
00521     return (-1);
00522   bddm->op_cache.rehash_fn[i]=rehash_fn;
00523   bddm->op_cache.gc_fn[i]=gc_fn;
00524   bddm->op_cache.purge_fn[i]=purge_fn;
00525   bddm->op_cache.return_fn[i]=return_fn;
00526   bddm->op_cache.flush_fn[i]=flush_fn;
00527   return (i);
00528 }
00529 
00530 
00531 static
00532 int
00533 bdd_flush_tag(cmu_bdd_manager bddm, cache_entry p, pointer tag)
00534 {
00535   /*return (TAG(p) == (int)tag);*/
00536   return (TAG(p) == (long)tag);
00537 }
00538 
00539 
00540 /* cmu_bdd_free_cache_tag(bddm, tag) frees a previously allocated user */
00541 /* cache tag. */
00542 
00543 void
00544 cmu_bdd_free_cache_tag(cmu_bdd_manager bddm, long tag)
00545 {
00546   if (tag < CACHE_TYPE_USER1 ||
00547       tag >= CACHE_TYPE_USER1+USER_ENTRY_TYPES ||
00548       !bddm->op_cache.rehash_fn[(long)tag])
00549     cmu_bdd_fatal("cmu_bdd_free_cache_tag: attempt to free unallocated tag");
00550   bdd_flush_cache(bddm, bdd_flush_tag, (pointer)tag);
00551   bddm->op_cache.rehash_fn[tag]=0;
00552   bddm->op_cache.gc_fn[tag]=0;
00553   bddm->op_cache.purge_fn[tag]=0;
00554   bddm->op_cache.return_fn[tag]=0;
00555   bddm->op_cache.flush_fn[tag]=0;
00556 }
00557 
00558 
00559 static
00560 int
00561 bdd_two_flush_fn(cmu_bdd_manager bddm, cache_entry p, pointer closure)
00562 {
00563   int id_to_nuke;
00564 
00565   id_to_nuke=(long)closure;
00566   return (p->slot[0] == OP_RELPROD+id_to_nuke ||
00567           p->slot[0] == OP_QNT+id_to_nuke ||
00568           p->slot[0] == OP_SUBST+id_to_nuke);
00569 }
00570 
00571 
00572 /* cmu_bdd_init_cache(bddm) initializes the cache for a BDD manager. */
00573 
00574 void
00575 cmu_bdd_init_cache(cmu_bdd_manager bddm)
00576 {
00577   long i;
00578   int j;
00579 
00580   bddm->op_cache.size_index=13;
00581   bddm->op_cache.size=TABLE_SIZE(bddm->op_cache.size_index);
00582   bddm->op_cache.table=(cache_bin *)mem_get_block((SIZE_T)(bddm->op_cache.size*sizeof(cache_bin)));
00583   for (i=0; i < bddm->op_cache.size; ++i)
00584     for (j=0; j < 2; ++j)
00585       bddm->op_cache.table[i].entry[j]=0;
00586   /* ITE cache control functions. */
00587   bddm->op_cache.rehash_fn[CACHE_TYPE_ITE]=bdd_rehash3;
00588   bddm->op_cache.gc_fn[CACHE_TYPE_ITE]=cmu_bdd_ite_gc_fn;
00589   bddm->op_cache.purge_fn[CACHE_TYPE_ITE]=0;
00590   bddm->op_cache.return_fn[CACHE_TYPE_ITE]=RETURN_BDD_FN;
00591   bddm->op_cache.flush_fn[CACHE_TYPE_ITE]=0;
00592   /* Two argument op cache control functions. */
00593   bddm->op_cache.rehash_fn[CACHE_TYPE_TWO]=bdd_rehash3;
00594   bddm->op_cache.gc_fn[CACHE_TYPE_TWO]=bdd_two_gc_fn;
00595   bddm->op_cache.purge_fn[CACHE_TYPE_TWO]=0;
00596   bddm->op_cache.return_fn[CACHE_TYPE_TWO]=RETURN_BDD_FN;
00597   bddm->op_cache.flush_fn[CACHE_TYPE_TWO]=bdd_two_flush_fn;
00598   /* One argument op w/ data result cache control functions. */
00599   bddm->op_cache.rehash_fn[CACHE_TYPE_ONEDATA]=bdd_rehash2;
00600   bddm->op_cache.gc_fn[CACHE_TYPE_ONEDATA]=cmu_bdd_one_data_gc_fn;
00601   bddm->op_cache.purge_fn[CACHE_TYPE_ONEDATA]=0;
00602   bddm->op_cache.return_fn[CACHE_TYPE_ONEDATA]=0;
00603   bddm->op_cache.flush_fn[CACHE_TYPE_ONEDATA]=0;
00604   /* Two argument op w/ data result cache control functions. */
00605   bddm->op_cache.rehash_fn[CACHE_TYPE_TWODATA]=bdd_rehash3;
00606   bddm->op_cache.gc_fn[CACHE_TYPE_TWODATA]=bdd_two_data_gc_fn;
00607   bddm->op_cache.purge_fn[CACHE_TYPE_TWODATA]=0;
00608   bddm->op_cache.return_fn[CACHE_TYPE_TWODATA]=0;
00609   bddm->op_cache.flush_fn[CACHE_TYPE_TWODATA]=0;
00610   /* User-defined cache control functions. */
00611   for (j=CACHE_TYPE_USER1; j < CACHE_TYPE_USER1+USER_ENTRY_TYPES; ++j)
00612     {
00613       bddm->op_cache.rehash_fn[j]=0;
00614       bddm->op_cache.gc_fn[j]=0;
00615       bddm->op_cache.purge_fn[j]=0;
00616       bddm->op_cache.return_fn[j]=0;
00617       bddm->op_cache.flush_fn[j]=0;
00618     }
00619   bddm->op_cache.cache_ratio=4;
00620   bddm->op_cache.cache_level=0;
00621   bddm->op_cache.entries=0;
00622   bddm->op_cache.lookups=0;
00623   bddm->op_cache.hits=0;
00624   bddm->op_cache.inserts=0;
00625   bddm->op_cache.collisions=0;
00626 }
00627 
00628 
00629 /* cmu_bdd_free_cache(bddm) frees the storage associated with the cache of */
00630 /* the indicated BDD manager. */
00631 
00632 void
00633 cmu_bdd_free_cache(cmu_bdd_manager bddm)
00634 {
00635   bdd_flush_all(bddm);
00636   mem_free_block((pointer)bddm->op_cache.table);
00637 }