hopOper.c 11.1 KB
Newer Older
Alan Mishchenko committed
1 2
/**CFile****************************************************************

Alan Mishchenko committed
3
  FileName    [hopOper.c]
Alan Mishchenko committed
4 5 6 7 8 9 10 11 12 13 14 15 16

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [Minimalistic And-Inverter Graph package.]

  Synopsis    [AIG operations.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

  Date        [Ver. 1.0. Started - May 11, 2006.]

Alan Mishchenko committed
17
  Revision    [$Id: hopOper.c,v 1.00 2006/05/11 00:00:00 alanmi Exp $]
Alan Mishchenko committed
18 19 20

***********************************************************************/

Alan Mishchenko committed
21
#include "hop.h"
Alan Mishchenko committed
22

23 24 25
ABC_NAMESPACE_IMPL_START


Alan Mishchenko committed
26 27 28 29 30
////////////////////////////////////////////////////////////////////////
///                        DECLARATIONS                              ///
////////////////////////////////////////////////////////////////////////

// procedure to detect an EXOR gate
Alan Mishchenko committed
31
static inline int Hop_ObjIsExorType( Hop_Obj_t * p0, Hop_Obj_t * p1, Hop_Obj_t ** ppFan0, Hop_Obj_t ** ppFan1 )
Alan Mishchenko committed
32
{
Alan Mishchenko committed
33
    if ( !Hop_IsComplement(p0) || !Hop_IsComplement(p1) )
Alan Mishchenko committed
34
        return 0;
Alan Mishchenko committed
35 36 37
    p0 = Hop_Regular(p0);
    p1 = Hop_Regular(p1);
    if ( !Hop_ObjIsAnd(p0) || !Hop_ObjIsAnd(p1) )
Alan Mishchenko committed
38
        return 0;
Alan Mishchenko committed
39
    if ( Hop_ObjFanin0(p0) != Hop_ObjFanin0(p1) || Hop_ObjFanin1(p0) != Hop_ObjFanin1(p1) )
Alan Mishchenko committed
40
        return 0;
Alan Mishchenko committed
41
    if ( Hop_ObjFaninC0(p0) == Hop_ObjFaninC0(p1) || Hop_ObjFaninC1(p0) == Hop_ObjFaninC1(p1) )
Alan Mishchenko committed
42
        return 0;
Alan Mishchenko committed
43 44
    *ppFan0 = Hop_ObjChild0(p0);
    *ppFan1 = Hop_ObjChild1(p0);
Alan Mishchenko committed
45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62
    return 1;
}

////////////////////////////////////////////////////////////////////////
///                     FUNCTION DEFINITIONS                         ///
////////////////////////////////////////////////////////////////////////

/**Function*************************************************************

  Synopsis    [Returns i-th elementary variable.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Alan Mishchenko committed
63
Hop_Obj_t * Hop_IthVar( Hop_Man_t * p, int i )
Alan Mishchenko committed
64 65
{
    int v;
Alan Mishchenko committed
66 67
    for ( v = Hop_ManPiNum(p); v <= i; v++ )
        Hop_ObjCreatePi( p );
Alan Mishchenko committed
68
    assert( i < Vec_PtrSize(p->vPis) );
Alan Mishchenko committed
69
    return Hop_ManPi( p, i );
Alan Mishchenko committed
70 71 72 73 74 75 76 77 78 79 80 81 82
}

/**Function*************************************************************

  Synopsis    [Perform one operation.]

  Description [The argument nodes can be complemented.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Alan Mishchenko committed
83
Hop_Obj_t * Hop_Oper( Hop_Man_t * p, Hop_Obj_t * p0, Hop_Obj_t * p1, Hop_Type_t Type )
Alan Mishchenko committed
84 85
{
    if ( Type == AIG_AND )
Alan Mishchenko committed
86
        return Hop_And( p, p0, p1 );
Alan Mishchenko committed
87
    if ( Type == AIG_EXOR )
Alan Mishchenko committed
88
        return Hop_Exor( p, p0, p1 );
Alan Mishchenko committed
89 90 91 92 93 94 95 96 97 98 99 100 101 102 103
    assert( 0 );
    return NULL;
}

/**Function*************************************************************

  Synopsis    [Performs canonicization step.]

  Description [The argument nodes can be complemented.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Alan Mishchenko committed
104
Hop_Obj_t * Hop_And( Hop_Man_t * p, Hop_Obj_t * p0, Hop_Obj_t * p1 )
Alan Mishchenko committed
105
{
Alan Mishchenko committed
106 107
    Hop_Obj_t * pGhost, * pResult;
//    Hop_Obj_t * pFan0, * pFan1;
Alan Mishchenko committed
108 109 110
    // check trivial cases
    if ( p0 == p1 )
        return p0;
Alan Mishchenko committed
111 112 113 114 115 116
    if ( p0 == Hop_Not(p1) )
        return Hop_Not(p->pConst1);
    if ( Hop_Regular(p0) == p->pConst1 )
        return p0 == p->pConst1 ? p1 : Hop_Not(p->pConst1);
    if ( Hop_Regular(p1) == p->pConst1 )
        return p1 == p->pConst1 ? p0 : Hop_Not(p->pConst1);
Alan Mishchenko committed
117
    // check if it can be an EXOR gate
Alan Mishchenko committed
118 119
//    if ( Hop_ObjIsExorType( p0, p1, &pFan0, &pFan1 ) )
//        return Hop_Exor( p, pFan0, pFan1 );
Alan Mishchenko committed
120
    // check the table
Alan Mishchenko committed
121
    pGhost = Hop_ObjCreateGhost( p, p0, p1, AIG_AND );
Alan Mishchenko committed
122
    if ( (pResult = Hop_TableLookup( p, pGhost )) )
Alan Mishchenko committed
123
        return pResult;
Alan Mishchenko committed
124
    return Hop_ObjCreate( p, pGhost );
Alan Mishchenko committed
125 126 127 128 129 130 131 132 133 134 135 136 137
}

/**Function*************************************************************

  Synopsis    [Performs canonicization step.]

  Description [The argument nodes can be complemented.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Alan Mishchenko committed
138
Hop_Obj_t * Hop_Exor( Hop_Man_t * p, Hop_Obj_t * p0, Hop_Obj_t * p1 )
Alan Mishchenko committed
139 140
{
/*
Alan Mishchenko committed
141
    Hop_Obj_t * pGhost, * pResult;
Alan Mishchenko committed
142 143
    // check trivial cases
    if ( p0 == p1 )
Alan Mishchenko committed
144 145
        return Hop_Not(p->pConst1);
    if ( p0 == Hop_Not(p1) )
Alan Mishchenko committed
146
        return p->pConst1;
Alan Mishchenko committed
147 148 149 150
    if ( Hop_Regular(p0) == p->pConst1 )
        return Hop_NotCond( p1, p0 == p->pConst1 );
    if ( Hop_Regular(p1) == p->pConst1 )
        return Hop_NotCond( p0, p1 == p->pConst1 );
Alan Mishchenko committed
151
    // check the table
Alan Mishchenko committed
152 153
    pGhost = Hop_ObjCreateGhost( p, p0, p1, AIG_EXOR );
    if ( pResult = Hop_TableLookup( p, pGhost ) )
Alan Mishchenko committed
154
        return pResult;
Alan Mishchenko committed
155
    return Hop_ObjCreate( p, pGhost );
Alan Mishchenko committed
156
*/
Alan Mishchenko committed
157
    return Hop_Or( p, Hop_And(p, p0, Hop_Not(p1)), Hop_And(p, Hop_Not(p0), p1) );
Alan Mishchenko committed
158 159 160 161 162 163 164 165 166 167 168 169 170
}

/**Function*************************************************************

  Synopsis    [Implements Boolean OR.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Alan Mishchenko committed
171
Hop_Obj_t * Hop_Or( Hop_Man_t * p, Hop_Obj_t * p0, Hop_Obj_t * p1 )
Alan Mishchenko committed
172
{
Alan Mishchenko committed
173
    return Hop_Not( Hop_And( p, Hop_Not(p0), Hop_Not(p1) ) );
Alan Mishchenko committed
174 175 176 177 178 179 180 181 182 183 184 185 186
}

/**Function*************************************************************

  Synopsis    [Implements ITE operation.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Alan Mishchenko committed
187
Hop_Obj_t * Hop_Mux( Hop_Man_t * p, Hop_Obj_t * pC, Hop_Obj_t * p1, Hop_Obj_t * p0 )
Alan Mishchenko committed
188 189
{
/*    
Alan Mishchenko committed
190
    Hop_Obj_t * pTempA1, * pTempA2, * pTempB1, * pTempB2, * pTemp;
Alan Mishchenko committed
191 192
    int Count0, Count1;
    // consider trivial cases
Alan Mishchenko committed
193 194
    if ( p0 == Hop_Not(p1) )
        return Hop_Exor( p, pC, p0 );
Alan Mishchenko committed
195 196 197 198 199
    // other cases can be added
    // implement the first MUX (F = C * x1 + C' * x0)

    // check for constants here!!!

Alan Mishchenko committed
200 201
    pTempA1 = Hop_TableLookup( p, Hop_ObjCreateGhost(p, pC,          p1, AIG_AND) );
    pTempA2 = Hop_TableLookup( p, Hop_ObjCreateGhost(p, Hop_Not(pC), p0, AIG_AND) );
Alan Mishchenko committed
202 203
    if ( pTempA1 && pTempA2 )
    {
Alan Mishchenko committed
204 205
        pTemp = Hop_TableLookup( p, Hop_ObjCreateGhost(p, Hop_Not(pTempA1), Hop_Not(pTempA2), AIG_AND) );
        if ( pTemp ) return Hop_Not(pTemp);
Alan Mishchenko committed
206 207 208
    }
    Count0 = (pTempA1 != NULL) + (pTempA2 != NULL);
    // implement the second MUX (F' = C * x1' + C' * x0')
Alan Mishchenko committed
209 210
    pTempB1 = Hop_TableLookup( p, Hop_ObjCreateGhost(p, pC,          Hop_Not(p1), AIG_AND) );
    pTempB2 = Hop_TableLookup( p, Hop_ObjCreateGhost(p, Hop_Not(pC), Hop_Not(p0), AIG_AND) );
Alan Mishchenko committed
211 212
    if ( pTempB1 && pTempB2 )
    {
Alan Mishchenko committed
213
        pTemp = Hop_TableLookup( p, Hop_ObjCreateGhost(p, Hop_Not(pTempB1), Hop_Not(pTempB2), AIG_AND) );
Alan Mishchenko committed
214 215 216 217 218 219
        if ( pTemp ) return pTemp;
    }
    Count1 = (pTempB1 != NULL) + (pTempB2 != NULL);
    // compare and decide which one to implement
    if ( Count0 >= Count1 )
    {
Alan Mishchenko committed
220 221 222
        pTempA1 = pTempA1? pTempA1 : Hop_And(p, pC,          p1);
        pTempA2 = pTempA2? pTempA2 : Hop_And(p, Hop_Not(pC), p0);
        return Hop_Or( p, pTempA1, pTempA2 );
Alan Mishchenko committed
223
    }
Alan Mishchenko committed
224 225 226
    pTempB1 = pTempB1? pTempB1 : Hop_And(p, pC,          Hop_Not(p1));
    pTempB2 = pTempB2? pTempB2 : Hop_And(p, Hop_Not(pC), Hop_Not(p0));
    return Hop_Not( Hop_Or( p, pTempB1, pTempB2 ) );
Alan Mishchenko committed
227
*/
Alan Mishchenko committed
228
    return Hop_Or( p, Hop_And(p, pC, p1), Hop_And(p, Hop_Not(pC), p0) );
Alan Mishchenko committed
229 230 231 232 233 234 235 236 237 238 239 240 241
}

/**Function*************************************************************

  Synopsis    [Implements ITE operation.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Alan Mishchenko committed
242
Hop_Obj_t * Hop_Maj( Hop_Man_t * p, Hop_Obj_t * pA, Hop_Obj_t * pB, Hop_Obj_t * pC )
Alan Mishchenko committed
243
{
Alan Mishchenko committed
244
    return Hop_Or( p, Hop_Or(p, Hop_And(p, pA, pB), Hop_And(p, pA, pC)), Hop_And(p, pB, pC) );
Alan Mishchenko committed
245 246 247 248 249 250 251 252 253 254 255 256 257
}

/**Function*************************************************************

  Synopsis    [Constructs the well-balanced tree of gates.]

  Description [Disregards levels and possible logic sharing.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Alan Mishchenko committed
258
Hop_Obj_t * Hop_Multi_rec( Hop_Man_t * p, Hop_Obj_t ** ppObjs, int nObjs, Hop_Type_t Type )
Alan Mishchenko committed
259
{
Alan Mishchenko committed
260
    Hop_Obj_t * pObj1, * pObj2;
Alan Mishchenko committed
261 262
    if ( nObjs == 1 )
        return ppObjs[0];
Alan Mishchenko committed
263 264 265
    pObj1 = Hop_Multi_rec( p, ppObjs,           nObjs/2,         Type );
    pObj2 = Hop_Multi_rec( p, ppObjs + nObjs/2, nObjs - nObjs/2, Type );
    return Hop_Oper( p, pObj1, pObj2, Type );
Alan Mishchenko committed
266 267 268 269 270 271 272 273 274 275 276 277 278
}

/**Function*************************************************************

  Synopsis    [Old code.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Alan Mishchenko committed
279
Hop_Obj_t * Hop_Multi( Hop_Man_t * p, Hop_Obj_t ** pArgs, int nArgs, Hop_Type_t Type )
Alan Mishchenko committed
280 281 282
{
    assert( Type == AIG_AND || Type == AIG_EXOR );
    assert( nArgs > 0 );
Alan Mishchenko committed
283
    return Hop_Multi_rec( p, pArgs, nArgs, Type );
Alan Mishchenko committed
284 285 286 287 288 289 290 291 292 293 294 295 296
}

/**Function*************************************************************

  Synopsis    [Implements the miter.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Alan Mishchenko committed
297
Hop_Obj_t * Hop_Miter( Hop_Man_t * p, Vec_Ptr_t * vPairs )
Alan Mishchenko committed
298 299 300 301 302 303
{
    int i;
    assert( vPairs->nSize > 0 );
    assert( vPairs->nSize % 2 == 0 );
    // go through the cubes of the node's SOP
    for ( i = 0; i < vPairs->nSize; i += 2 )
304
        vPairs->pArray[i/2] = Hop_Not( Hop_Exor( p, (Hop_Obj_t *)vPairs->pArray[i], (Hop_Obj_t *)vPairs->pArray[i+1] ) );
Alan Mishchenko committed
305
    vPairs->nSize = vPairs->nSize/2;
Alan Mishchenko committed
306
    return Hop_Not( Hop_Multi_rec( p, (Hop_Obj_t **)vPairs->pArray, vPairs->nSize, AIG_AND ) );
Alan Mishchenko committed
307 308 309 310 311 312 313 314 315 316 317 318 319
}

/**Function*************************************************************

  Synopsis    [Creates AND function with nVars inputs.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Alan Mishchenko committed
320
Hop_Obj_t * Hop_CreateAnd( Hop_Man_t * p, int nVars )
Alan Mishchenko committed
321
{
Alan Mishchenko committed
322
    Hop_Obj_t * pFunc;
Alan Mishchenko committed
323
    int i;
Alan Mishchenko committed
324
    pFunc = Hop_ManConst1( p );
Alan Mishchenko committed
325
    for ( i = 0; i < nVars; i++ )
Alan Mishchenko committed
326
        pFunc = Hop_And( p, pFunc, Hop_IthVar(p, i) );
Alan Mishchenko committed
327 328 329 330 331 332 333 334 335 336 337 338 339 340
    return pFunc;
}

/**Function*************************************************************

  Synopsis    [Creates AND function with nVars inputs.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Alan Mishchenko committed
341
Hop_Obj_t * Hop_CreateOr( Hop_Man_t * p, int nVars )
Alan Mishchenko committed
342
{
Alan Mishchenko committed
343
    Hop_Obj_t * pFunc;
Alan Mishchenko committed
344
    int i;
Alan Mishchenko committed
345
    pFunc = Hop_ManConst0( p );
Alan Mishchenko committed
346
    for ( i = 0; i < nVars; i++ )
Alan Mishchenko committed
347
        pFunc = Hop_Or( p, pFunc, Hop_IthVar(p, i) );
Alan Mishchenko committed
348 349 350 351 352 353 354 355 356 357 358 359 360 361
    return pFunc;
}

/**Function*************************************************************

  Synopsis    [Creates AND function with nVars inputs.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Alan Mishchenko committed
362
Hop_Obj_t * Hop_CreateExor( Hop_Man_t * p, int nVars )
Alan Mishchenko committed
363
{
Alan Mishchenko committed
364
    Hop_Obj_t * pFunc;
Alan Mishchenko committed
365
    int i;
Alan Mishchenko committed
366
    pFunc = Hop_ManConst0( p );
Alan Mishchenko committed
367
    for ( i = 0; i < nVars; i++ )
Alan Mishchenko committed
368
        pFunc = Hop_Exor( p, pFunc, Hop_IthVar(p, i) );
Alan Mishchenko committed
369 370 371 372 373 374 375 376
    return pFunc;
}

////////////////////////////////////////////////////////////////////////
///                       END OF FILE                                ///
////////////////////////////////////////////////////////////////////////


377 378
ABC_NAMESPACE_IMPL_END