src/calBdd/calBddITE.c File Reference

#include "calInt.h"
Include dependency graph for calBddITE.c:

Go to the source code of this file.

Functions

Cal_Bdd Cal_BddITE (Cal_BddManager bddManager, Cal_Bdd fUserBdd, Cal_Bdd gUserBdd, Cal_Bdd hUserBdd)
void CalRequestNodeListArrayITE (Cal_BddManager_t *bddManager, CalRequestNode_t **requestNodeListArray)
Cal_Bdd_t CalBddOpITEBF (Cal_BddManager_t *bddManager, Cal_Bdd_t f, Cal_Bdd_t g, Cal_Bdd_t h)
void CalHashTableITEApply (Cal_BddManager_t *bddManager, CalHashTable_t *hashTable, CalHashTable_t **reqQueAtPipeDepth)
Cal_Bdd_t CalBddITE (Cal_BddManager_t *bddManager, Cal_Bdd_t F, Cal_Bdd_t G, Cal_Bdd_t H)

Function Documentation

Cal_Bdd Cal_BddITE ( Cal_BddManager  bddManager,
Cal_Bdd  fUserBdd,
Cal_Bdd  gUserBdd,
Cal_Bdd  hUserBdd 
)

CFile***********************************************************************

FileName [calBddITE.c]

PackageName [cal]

Synopsis [Routine for computing ITE of 3 BDD operands.]

Description []

SeeAlso [optional]

Author [Jagesh Sanghavi (sanghavi@eecs.berkeley.edu) Rajeev Ranjan (rajeev@eecs.berkeley.edu)]

Copyright [Copyright (c) 1994-1996 The Regents of the Univ. of California. All rights reserved.

Permission is hereby granted, without written agreement and without license or royalty fees, to use, copy, modify, and distribute this software and its documentation for any purpose, provided that the above copyright notice and the following two paragraphs appear in all copies of this software.

IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.]

Revision [

Id
calBddITE.c,v 1.1.1.3 1998/05/04 00:58:51 hsv Exp

]AutomaticStart AutomaticEnd Function********************************************************************

Synopsis [Returns the BDD for logical If-Then-Else

Description [Returns the BDD for the logical operation IF f THEN g ELSE h

  • f g + f' h]

SideEffects [None]

SeeAlso [Cal_BddAnd, Cal_BddNand, Cal_BddOr, Cal_BddNor, Cal_BddXor, Cal_BddXnor]

Definition at line 88 of file calBddITE.c.

00090 {
00091   Cal_Bdd_t result;
00092   Cal_Bdd userResult;
00093   Cal_Bdd_t F, G, H;
00094   if (CalBddPreProcessing(bddManager, 3, fUserBdd, gUserBdd, hUserBdd)){
00095     F = CalBddGetInternalBdd(bddManager, fUserBdd);
00096     G = CalBddGetInternalBdd(bddManager, gUserBdd);
00097     H = CalBddGetInternalBdd(bddManager, hUserBdd);
00098     result = CalBddOpITEBF(bddManager, F, G, H);
00099   }
00100   else {
00101     return (Cal_Bdd) 0;
00102   }
00103   userResult =  CalBddGetExternalBdd(bddManager, result);
00104   if (CalBddPostProcessing(bddManager) == CAL_BDD_OVERFLOWED){
00105     Cal_BddFree(bddManager, userResult);
00106     Cal_BddManagerGC(bddManager);
00107     return (Cal_Bdd) 0;
00108   }
00109   return userResult;
00110 }

Cal_Bdd_t CalBddITE ( Cal_BddManager_t *  bddManager,
Cal_Bdd_t  F,
Cal_Bdd_t  G,
Cal_Bdd_t  H 
)

Function********************************************************************

Synopsis [Returns the BDD for logical If-Then-Else

Description [Returns the BDD for the logical operation IF f THEN g ELSE h

  • f g + f' h]

SideEffects [None]

SeeAlso [Cal_BddAnd, Cal_BddNand, Cal_BddOr, Cal_BddNor, Cal_BddXor, Cal_BddXnor]

Definition at line 322 of file calBddITE.c.

00324 {
00325   Cal_Bdd_t result;
00326   result = CalBddOpITEBF(bddManager, F, G, H);
00327   CalBddIcrRefCount(result);
00328   return result;
00329 }

Cal_Bdd_t CalBddOpITEBF ( Cal_BddManager_t *  bddManager,
Cal_Bdd_t  f,
Cal_Bdd_t  g,
Cal_Bdd_t  h 
)

Function********************************************************************

Synopsis [required]

Description [optional]

SideEffects [required]

SeeAlso [optional]

Definition at line 218 of file calBddITE.c.

00223 {
00224   Cal_Bdd_t result;
00225   Cal_BddId_t bddId;
00226   /*Cal_BddIndex_t minIndex;*/
00227   int minIndex;
00228   int bddIndex;
00229   CalHashTable_t *hashTable;
00230   CalHashTable_t *uniqueTableForId;
00231   CalHashTable_t **reqQueForITE = bddManager->reqQue[0];
00232   
00233   result = CalOpITE(bddManager, f, g, h, reqQueForITE);
00234   
00235   CalBddGetMinIndex3(bddManager, f, g, h, minIndex);
00236   /* ReqQueApply */
00237   for(bddIndex = minIndex; bddIndex < bddManager->numVars; bddIndex++){
00238     bddId = bddManager->indexToId[bddIndex];
00239     hashTable = reqQueForITE[bddId];
00240     if(hashTable->numEntries){
00241       CalHashTableITEApply(bddManager, hashTable, reqQueForITE);
00242     }
00243   }
00244 
00245   /* ReqQueReduce */
00246   for(bddIndex = bddManager->numVars - 1; bddIndex >= minIndex; bddIndex--){
00247     bddId = bddManager->indexToId[bddIndex];
00248     uniqueTableForId = bddManager->uniqueTable[bddId];
00249     hashTable = reqQueForITE[bddId];
00250     if(hashTable->numEntries){
00251       CalHashTableReduce(bddManager, hashTable, uniqueTableForId);
00252     }
00253   }
00254 
00255   CalRequestIsForwardedTo(result);
00256 
00257   /* Clean up */
00258   for(bddIndex = minIndex; bddIndex < bddManager->numVars; bddIndex++){
00259     bddId = bddManager->indexToId[bddIndex];
00260     CalHashTableCleanUp(reqQueForITE[bddId]);
00261   }
00262 
00263   return result;
00264 }

void CalHashTableITEApply ( Cal_BddManager_t *  bddManager,
CalHashTable_t *  hashTable,
CalHashTable_t **  reqQueAtPipeDepth 
)

Function********************************************************************

Synopsis [required]

Description [optional]

SideEffects [required]

SeeAlso [optional]

Definition at line 278 of file calBddITE.c.

00282 {
00283   int i, numBins = hashTable->numBins;
00284   CalBddNode_t **bins = hashTable->bins;
00285   CalRequestNode_t *requestNode;
00286   Cal_Bdd_t fx, gx, fxbar, gxbar, hx, hxbar, result;
00287   CalNodeManager_t *nodeManager = hashTable->nodeManager;
00288   
00289   for(i = 0; i < numBins; i++){
00290     for(requestNode = bins[i];
00291         requestNode != Cal_Nil(CalRequestNode_t);
00292         requestNode = CalRequestNodeGetNextRequestNode(requestNode)){
00293       /* Process the requestNode */
00294       CalITERequestNodeGetCofactors(bddManager, requestNode,
00295           fx, fxbar, gx, gxbar, hx, hxbar);
00296       result = CalOpITE(bddManager, fx, gx, hx, reqQueAtPipeDepth);
00297       CalBddIcrRefCount(result);
00298       CalRequestNodePutThenRequest(requestNode, result);
00299       result = CalOpITE(bddManager, fxbar, gxbar, hxbar, reqQueAtPipeDepth);
00300       CalBddIcrRefCount(result);
00301       CalNodeManagerFreeNode(nodeManager,
00302           CalRequestNodeGetElseRequestNode(requestNode));
00303       CalRequestNodePutElseRequest(requestNode, result);
00304     }
00305   }
00306 }

void CalRequestNodeListArrayITE ( Cal_BddManager_t *  bddManager,
CalRequestNode_t **  requestNodeListArray 
)

Function********************************************************************

Name [CalRequestNodeListArrayOp]

Synopsis [required]

Description [This routine is to be used for pipelined and superscalar ITE operations. Currently there is no user interface provided to this routine.]

SideEffects [required]

SeeAlso [optional]

Definition at line 133 of file calBddITE.c.

00135 {
00136   CalRequestNode_t *requestNode, *ptrIndirect;
00137   CalRequest_t F, G, H, result;
00138   int pipeDepth, bddId, bddIndex;
00139   CalHashTable_t **reqQueAtPipeDepth, *hashTable, *uniqueTableForId;
00140   CalHashTable_t ***reqQue = bddManager->reqQue;
00141   
00142   /* ReqQueInsertUsingReqListArray */
00143   for(pipeDepth = 0; pipeDepth < bddManager->depth; pipeDepth++){
00144     reqQueAtPipeDepth = reqQue[pipeDepth];
00145     for(requestNode = requestNodeListArray[pipeDepth];
00146         requestNode != Cal_Nil(CalRequestNode_t);
00147         requestNode = CalRequestNodeGetNextRequestNode(requestNode)){
00148       CalRequestNodeGetThenRequest(requestNode, F);
00149       CalRequestIsForwardedTo(F);
00150       ptrIndirect = CalRequestNodeGetElseRequestNode(requestNode);
00151       CalRequestNodeGetThenRequest(ptrIndirect, G);
00152       CalRequestIsForwardedTo(G);
00153       CalRequestNodeGetElseRequest(ptrIndirect, H);
00154       CalRequestIsForwardedTo(H);
00155       CalNodeManagerFreeNode(bddManager->nodeManagerArray[0], ptrIndirect);
00156       result = CalOpITE(bddManager, F, G, H, reqQueAtPipeDepth);
00157       CalRequestNodePutThenRequest(requestNode, result);
00158       CalRequestNodePutElseRequestNode(requestNode, FORWARD_FLAG);
00159     }
00160   }
00161 
00162   /* ReqQueApply */
00163   for(bddIndex = 0; bddIndex < bddManager->numVars; bddIndex++){
00164     bddId = bddManager->indexToId[bddIndex];
00165     for(pipeDepth = 0; pipeDepth < bddManager->depth; pipeDepth++){
00166       reqQueAtPipeDepth = reqQue[pipeDepth];
00167       hashTable = reqQueAtPipeDepth[bddId];
00168       if(hashTable->numEntries){
00169         CalHashTableITEApply(bddManager, hashTable, reqQueAtPipeDepth);
00170       }
00171     }
00172   }
00173 
00174   /* ReqQueReduce */
00175   for(bddIndex = bddManager->numVars - 1; bddIndex >= 0; bddIndex--){
00176     bddId = bddManager->indexToId[bddIndex];
00177     uniqueTableForId = bddManager->uniqueTable[bddId];
00178     for(pipeDepth = 0; pipeDepth < bddManager->depth; pipeDepth++){
00179       hashTable = reqQue[pipeDepth][bddId];
00180       if(hashTable->numEntries){
00181         CalHashTableReduce(bddManager, hashTable, uniqueTableForId);
00182       }
00183     }
00184   }
00185 
00186   /* ReqListArrayReqForward */
00187   for(pipeDepth = 0; pipeDepth < bddManager->depth; pipeDepth++){
00188     for(requestNode = requestNodeListArray[pipeDepth];
00189         requestNode != Cal_Nil(CalRequestNode_t);
00190         requestNode = CalRequestNodeGetNextRequestNode(requestNode)){
00191       CalRequestNodeGetThenRequest(requestNode, result);
00192       CalRequestIsForwardedTo(result);
00193       CalRequestNodePutThenRequest(requestNode, result);
00194     }
00195   }
00196 
00197   /* ReqQueCleanUp */
00198   for(pipeDepth = 0; pipeDepth < bddManager->depth; pipeDepth++){
00199     reqQueAtPipeDepth = reqQue[pipeDepth];
00200     for(bddId = 1; bddId <= bddManager->numVars; bddId++){
00201       CalHashTableCleanUp(reqQueAtPipeDepth[bddId]);
00202     }
00203   }
00204 }

Generated on Tue Jan 12 13:57:10 2010 for glu-2.2 by  doxygen 1.6.1