source: vis_dev/glu-2.3/src/calBdd/calBddITE.c @ 84

Last change on this file since 84 was 13, checked in by cecile, 13 years ago

library glu 2.3
File size: 11.7 KB
Line 
1/**CFile***********************************************************************
2
3  FileName    [calBddITE.c]
4
5  PackageName [cal]
6
7  Synopsis    [Routine for computing ITE of 3 BDD operands.]
8
9  Description []
10
11  SeeAlso     [optional]
12
13  Author      [Jagesh Sanghavi (sanghavi@eecs.berkeley.edu)
14               Rajeev Ranjan   (rajeev@eecs.berkeley.edu)]
15
16  Copyright   [Copyright (c) 1994-1996 The Regents of the Univ. of California.
17  All rights reserved.
18
19  Permission is hereby granted, without written agreement and without license
20  or royalty fees, to use, copy, modify, and distribute this software and its
21  documentation for any purpose, provided that the above copyright notice and
22  the following two paragraphs appear in all copies of this software.
23
24  IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY FOR
25  DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
26  OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
27  CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28
29  THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
30  INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
31  FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS ON AN
32  "AS IS" BASIS, AND THE UNIVERSITY OF CALIFORNIA HAS NO OBLIGATION TO PROVIDE
33  MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.]
34
35  Revision    [$Id: calBddITE.c,v 1.1.1.3 1998/05/04 00:58:51 hsv Exp $]
36
37******************************************************************************/
38
39#include "calInt.h"
40
41/*---------------------------------------------------------------------------*/
42/* Constant declarations                                                     */
43/*---------------------------------------------------------------------------*/
44
45/*---------------------------------------------------------------------------*/
46/* Type declarations                                                         */
47/*---------------------------------------------------------------------------*/
48
49/*---------------------------------------------------------------------------*/
50/* Stucture declarations                                                     */
51/*---------------------------------------------------------------------------*/
52
53
54/*---------------------------------------------------------------------------*/
55/* Variable declarations                                                     */
56/*---------------------------------------------------------------------------*/
57
58/*---------------------------------------------------------------------------*/
59/* Macro declarations                                                        */
60/*---------------------------------------------------------------------------*/
61
62/**AutomaticStart*************************************************************/
63
64/*---------------------------------------------------------------------------*/
65/* Static function prototypes                                                */
66/*---------------------------------------------------------------------------*/
67
68
69/**AutomaticEnd***************************************************************/
70
71/*---------------------------------------------------------------------------*/
72/* Definition of exported functions                                          */
73/*---------------------------------------------------------------------------*/
74/**Function********************************************************************
75
76  Synopsis    [Returns the BDD for logical If-Then-Else
77
78  Description [Returns the BDD for the logical operation IF f THEN g ELSE h
79  - f g + f' h]
80
81  SideEffects [None]
82
83  SeeAlso     [Cal_BddAnd, Cal_BddNand, Cal_BddOr, Cal_BddNor, Cal_BddXor,
84  Cal_BddXnor]
85
86******************************************************************************/
87Cal_Bdd
88Cal_BddITE(Cal_BddManager bddManager, Cal_Bdd fUserBdd, Cal_Bdd gUserBdd,
89           Cal_Bdd hUserBdd)
90{
91  Cal_Bdd_t result;
92  Cal_Bdd userResult;
93  Cal_Bdd_t F, G, H;
94  if (CalBddPreProcessing(bddManager, 3, fUserBdd, gUserBdd, hUserBdd)){
95    F = CalBddGetInternalBdd(bddManager, fUserBdd);
96    G = CalBddGetInternalBdd(bddManager, gUserBdd);
97    H = CalBddGetInternalBdd(bddManager, hUserBdd);
98    result = CalBddOpITEBF(bddManager, F, G, H);
99  }
100  else {
101    return (Cal_Bdd) 0;
102  }
103  userResult =  CalBddGetExternalBdd(bddManager, result);
104  if (CalBddPostProcessing(bddManager) == CAL_BDD_OVERFLOWED){
105    Cal_BddFree(bddManager, userResult);
106    Cal_BddManagerGC(bddManager);
107    return (Cal_Bdd) 0;
108  }
109  return userResult;
110}
111
112/*---------------------------------------------------------------------------*/
113/* Definition of internal functions                                          */
114/*---------------------------------------------------------------------------*/
115
116
117/**Function********************************************************************
118
119  Name        [CalRequestNodeListArrayOp]
120
121  Synopsis    [required]
122
123  Description [This routine is to be used for pipelined and
124  superscalar ITE operations. Currently there is no user interface
125  provided to this routine.]
126
127  SideEffects [required]
128
129  SeeAlso     [optional]
130
131******************************************************************************/
132void
133CalRequestNodeListArrayITE(Cal_BddManager_t *bddManager,
134                          CalRequestNode_t **requestNodeListArray)
135{
136  CalRequestNode_t *requestNode, *ptrIndirect;
137  CalRequest_t F, G, H, result;
138  int pipeDepth, bddId, bddIndex;
139  CalHashTable_t **reqQueAtPipeDepth, *hashTable, *uniqueTableForId;
140  CalHashTable_t ***reqQue = bddManager->reqQue;
141 
142  /* ReqQueInsertUsingReqListArray */
143  for(pipeDepth = 0; pipeDepth < bddManager->depth; pipeDepth++){
144    reqQueAtPipeDepth = reqQue[pipeDepth];
145    for(requestNode = requestNodeListArray[pipeDepth];
146        requestNode != Cal_Nil(CalRequestNode_t);
147        requestNode = CalRequestNodeGetNextRequestNode(requestNode)){
148      CalRequestNodeGetThenRequest(requestNode, F);
149      CalRequestIsForwardedTo(F);
150      ptrIndirect = CalRequestNodeGetElseRequestNode(requestNode);
151      CalRequestNodeGetThenRequest(ptrIndirect, G);
152      CalRequestIsForwardedTo(G);
153      CalRequestNodeGetElseRequest(ptrIndirect, H);
154      CalRequestIsForwardedTo(H);
155      CalNodeManagerFreeNode(bddManager->nodeManagerArray[0], ptrIndirect);
156      result = CalOpITE(bddManager, F, G, H, reqQueAtPipeDepth);
157      CalRequestNodePutThenRequest(requestNode, result);
158      CalRequestNodePutElseRequestNode(requestNode, FORWARD_FLAG);
159    }
160  }
161
162  /* ReqQueApply */
163  for(bddIndex = 0; bddIndex < bddManager->numVars; bddIndex++){
164    bddId = bddManager->indexToId[bddIndex];
165    for(pipeDepth = 0; pipeDepth < bddManager->depth; pipeDepth++){
166      reqQueAtPipeDepth = reqQue[pipeDepth];
167      hashTable = reqQueAtPipeDepth[bddId];
168      if(hashTable->numEntries){
169        CalHashTableITEApply(bddManager, hashTable, reqQueAtPipeDepth);
170      }
171    }
172  }
173
174  /* ReqQueReduce */
175  for(bddIndex = bddManager->numVars - 1; bddIndex >= 0; bddIndex--){
176    bddId = bddManager->indexToId[bddIndex];
177    uniqueTableForId = bddManager->uniqueTable[bddId];
178    for(pipeDepth = 0; pipeDepth < bddManager->depth; pipeDepth++){
179      hashTable = reqQue[pipeDepth][bddId];
180      if(hashTable->numEntries){
181        CalHashTableReduce(bddManager, hashTable, uniqueTableForId);
182      }
183    }
184  }
185
186  /* ReqListArrayReqForward */
187  for(pipeDepth = 0; pipeDepth < bddManager->depth; pipeDepth++){
188    for(requestNode = requestNodeListArray[pipeDepth];
189        requestNode != Cal_Nil(CalRequestNode_t);
190        requestNode = CalRequestNodeGetNextRequestNode(requestNode)){
191      CalRequestNodeGetThenRequest(requestNode, result);
192      CalRequestIsForwardedTo(result);
193      CalRequestNodePutThenRequest(requestNode, result);
194    }
195  }
196
197  /* ReqQueCleanUp */
198  for(pipeDepth = 0; pipeDepth < bddManager->depth; pipeDepth++){
199    reqQueAtPipeDepth = reqQue[pipeDepth];
200    for(bddId = 1; bddId <= bddManager->numVars; bddId++){
201      CalHashTableCleanUp(reqQueAtPipeDepth[bddId]);
202    }
203  }
204}
205
206/**Function********************************************************************
207
208  Synopsis    [required]
209
210  Description [optional]
211
212  SideEffects [required]
213
214  SeeAlso     [optional]
215
216******************************************************************************/
217Cal_Bdd_t
218CalBddOpITEBF(
219  Cal_BddManager_t *bddManager,
220  Cal_Bdd_t  f,
221  Cal_Bdd_t  g,
222  Cal_Bdd_t  h)
223{
224  Cal_Bdd_t result;
225  Cal_BddId_t bddId;
226  /*Cal_BddIndex_t minIndex;*/
227  int minIndex;
228  int bddIndex;
229  CalHashTable_t *hashTable;
230  CalHashTable_t *uniqueTableForId;
231  CalHashTable_t **reqQueForITE = bddManager->reqQue[0];
232 
233  result = CalOpITE(bddManager, f, g, h, reqQueForITE);
234 
235  CalBddGetMinIndex3(bddManager, f, g, h, minIndex);
236  /* ReqQueApply */
237  for(bddIndex = minIndex; bddIndex < bddManager->numVars; bddIndex++){
238    bddId = bddManager->indexToId[bddIndex];
239    hashTable = reqQueForITE[bddId];
240    if(hashTable->numEntries){
241      CalHashTableITEApply(bddManager, hashTable, reqQueForITE);
242    }
243  }
244
245  /* ReqQueReduce */
246  for(bddIndex = bddManager->numVars - 1; bddIndex >= minIndex; bddIndex--){
247    bddId = bddManager->indexToId[bddIndex];
248    uniqueTableForId = bddManager->uniqueTable[bddId];
249    hashTable = reqQueForITE[bddId];
250    if(hashTable->numEntries){
251      CalHashTableReduce(bddManager, hashTable, uniqueTableForId);
252    }
253  }
254
255  CalRequestIsForwardedTo(result);
256
257  /* Clean up */
258  for(bddIndex = minIndex; bddIndex < bddManager->numVars; bddIndex++){
259    bddId = bddManager->indexToId[bddIndex];
260    CalHashTableCleanUp(reqQueForITE[bddId]);
261  }
262
263  return result;
264}
265
266/**Function********************************************************************
267
268  Synopsis    [required]
269
270  Description [optional]
271
272  SideEffects [required]
273
274  SeeAlso     [optional]
275
276******************************************************************************/
277void
278CalHashTableITEApply(
279  Cal_BddManager_t *bddManager,
280  CalHashTable_t *hashTable,
281  CalHashTable_t **reqQueAtPipeDepth)
282{
283  int i, numBins = hashTable->numBins;
284  CalBddNode_t **bins = hashTable->bins;
285  CalRequestNode_t *requestNode;
286  Cal_Bdd_t fx, gx, fxbar, gxbar, hx, hxbar, result;
287  CalNodeManager_t *nodeManager = hashTable->nodeManager;
288 
289  for(i = 0; i < numBins; i++){
290    for(requestNode = bins[i];
291        requestNode != Cal_Nil(CalRequestNode_t);
292        requestNode = CalRequestNodeGetNextRequestNode(requestNode)){
293      /* Process the requestNode */
294      CalITERequestNodeGetCofactors(bddManager, requestNode,
295          fx, fxbar, gx, gxbar, hx, hxbar);
296      result = CalOpITE(bddManager, fx, gx, hx, reqQueAtPipeDepth);
297      CalBddIcrRefCount(result);
298      CalRequestNodePutThenRequest(requestNode, result);
299      result = CalOpITE(bddManager, fxbar, gxbar, hxbar, reqQueAtPipeDepth);
300      CalBddIcrRefCount(result);
301      CalNodeManagerFreeNode(nodeManager,
302          CalRequestNodeGetElseRequestNode(requestNode));
303      CalRequestNodePutElseRequest(requestNode, result);
304    }
305  }
306}
307
308/**Function********************************************************************
309 
310   Synopsis    [Returns the BDD for logical If-Then-Else
311 
312   Description [Returns the BDD for the logical operation IF f THEN g ELSE h
313   - f g + f' h]
314 
315   SideEffects [None]
316 
317   SeeAlso     [Cal_BddAnd, Cal_BddNand, Cal_BddOr, Cal_BddNor, Cal_BddXor,
318   Cal_BddXnor]
319 
320******************************************************************************/
321Cal_Bdd_t
322CalBddITE(Cal_BddManager_t *bddManager, Cal_Bdd_t F, Cal_Bdd_t G,
323          Cal_Bdd_t H)
324{
325  Cal_Bdd_t result;
326  result = CalBddOpITEBF(bddManager, F, G, H);
327  CalBddIcrRefCount(result);
328  return result;
329}
330
331/*---------------------------------------------------------------------------*/
332/* Definition of static functions                                            */
333/*---------------------------------------------------------------------------*/
Note: See TracBrowser for help on using the repository browser.