acecTree.c 28.5 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
/**CFile****************************************************************

  FileName    [acecTree.c]

  SystemName  [ABC: Logic synthesis and verification system.]

  PackageName [CEC for arithmetic circuits.]

  Synopsis    [Adder tree construction.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

  Date        [Ver. 1.0. Started - June 20, 2005.]

  Revision    [$Id: acecTree.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]

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

#include "acecInt.h"

ABC_NAMESPACE_IMPL_START


////////////////////////////////////////////////////////////////////////
///                        DECLARATIONS                              ///
////////////////////////////////////////////////////////////////////////

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

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

36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62
  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Acec_BoxFree( Acec_Box_t * pBox )
{
    Vec_WecFreeP( &pBox->vAdds );
    Vec_WecFreeP( &pBox->vLeafLits );
    Vec_WecFreeP( &pBox->vRootLits );
    Vec_WecFreeP( &pBox->vUnique );
    Vec_WecFreeP( &pBox->vShared );
    ABC_FREE( pBox );
}
void Acec_BoxFreeP( Acec_Box_t ** ppBox )
{
    if ( *ppBox )
        Acec_BoxFree( *ppBox );
    *ppBox = NULL;
}

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

63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86
  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Acec_VerifyBoxLeaves( Acec_Box_t * pBox, Vec_Bit_t * vIgnore )
{
    Vec_Int_t * vLevel;
    int i, k, iLit, Count = 0;
    if ( vIgnore == NULL )
        return;
    Vec_WecForEachLevel( pBox->vLeafLits, vLevel, i )
        Vec_IntForEachEntry( vLevel, iLit, k )
            if ( Gia_ObjIsAnd(Gia_ManObj(pBox->pGia, Abc_Lit2Var(iLit))) && !Vec_BitEntry(vIgnore, Abc_Lit2Var(iLit)) )
                printf( "Internal node %d of rank %d is not part of PPG.\n", Abc_Lit2Var(iLit), i ), Count++;
    printf( "Detected %d suspicious leaves.\n", Count );
}

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

87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123
  Synopsis    [Filters trees by removing TFO of roots.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Acec_TreeFilterOne( Gia_Man_t * p, Vec_Int_t * vAdds, Vec_Int_t * vTree )
{
    Vec_Bit_t * vIsRoot = Vec_BitStart( Gia_ManObjNum(p) );
    Vec_Bit_t * vMarked = Vec_BitStart( Gia_ManObjNum(p) ) ;
    Gia_Obj_t * pObj;
    int i, k = 0, Box, Rank;
    // mark roots
    Vec_IntForEachEntryDouble( vTree, Box, Rank, i )
    {
        Vec_BitWriteEntry( vIsRoot, Vec_IntEntry(vAdds, 6*Box+3), 1 );
        Vec_BitWriteEntry( vIsRoot, Vec_IntEntry(vAdds, 6*Box+4), 1 );
    }
    Vec_IntForEachEntryDouble( vTree, Box, Rank, i )
    {
        Vec_BitWriteEntry( vIsRoot, Vec_IntEntry(vAdds, 6*Box+0), 0 );
        Vec_BitWriteEntry( vIsRoot, Vec_IntEntry(vAdds, 6*Box+1), 0 );
        Vec_BitWriteEntry( vIsRoot, Vec_IntEntry(vAdds, 6*Box+2), 0 );
    }
    // iterate through nodes to detect TFO of roots
    Gia_ManForEachAnd( p, pObj, i )
    {
        if ( Vec_BitEntry(vIsRoot, Gia_ObjFaninId0(pObj,i)) || Vec_BitEntry(vIsRoot, Gia_ObjFaninId1(pObj,i)) ||
             Vec_BitEntry(vMarked, Gia_ObjFaninId0(pObj,i)) || Vec_BitEntry(vMarked, Gia_ObjFaninId1(pObj,i)) )
            Vec_BitWriteEntry( vMarked, i, 1 );
    }
    // remove those that overlap with roots
    Vec_IntForEachEntryDouble( vTree, Box, Rank, i )
    {
124 125 126 127
        // special case of the first bit
//        if ( i == 0 )
//            continue;

128 129 130 131 132 133 134 135 136 137 138 139
/*
        if ( Vec_IntEntry(vAdds, 6*Box+3) == 24 && Vec_IntEntry(vAdds, 6*Box+4) == 22 )
        {
            printf( "**** removing special one \n" );
            continue;
        }
        if ( Vec_IntEntry(vAdds, 6*Box+3) == 48 && Vec_IntEntry(vAdds, 6*Box+4) == 49 )
        {
            printf( "**** removing special one \n" );
            continue;
        }
*/
140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161
        if ( Vec_BitEntry(vMarked, Vec_IntEntry(vAdds, 6*Box+3)) || Vec_BitEntry(vMarked, Vec_IntEntry(vAdds, 6*Box+4)) )
        {
            printf( "Removing box %d=(%d,%d) of rank %d.\n", Box, Vec_IntEntry(vAdds, 6*Box+3), Vec_IntEntry(vAdds, 6*Box+4), Rank ); 
            continue;
        }
        Vec_IntWriteEntry( vTree, k++, Box );
        Vec_IntWriteEntry( vTree, k++, Rank );
    }
    Vec_IntShrink( vTree, k );
    Vec_BitFree( vIsRoot );
    Vec_BitFree( vMarked );
}
void Acec_TreeFilterTrees( Gia_Man_t * p, Vec_Int_t * vAdds, Vec_Wec_t * vTrees )
{
    Vec_Int_t * vLevel;
    int i;
    Vec_WecForEachLevel( vTrees, vLevel, i )
        Acec_TreeFilterOne( p, vAdds, vLevel );
}

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

162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203
  Synopsis    [Filters trees by removing TFO of roots.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Acec_TreeMarkTFI_rec( Gia_Man_t * p, int Id, Vec_Bit_t * vMarked )
{
    Gia_Obj_t * pObj = Gia_ManObj(p, Id);
    if ( Vec_BitEntry(vMarked, Id) )
        return;
    Vec_BitWriteEntry( vMarked, Id, 1 );
    if ( !Gia_ObjIsAnd(pObj) )
        return;
    Acec_TreeMarkTFI_rec( p, Gia_ObjFaninId0(pObj, Id), vMarked );
    Acec_TreeMarkTFI_rec( p, Gia_ObjFaninId1(pObj, Id), vMarked );
}
void Acec_TreeFilterOne2( Gia_Man_t * p, Vec_Int_t * vAdds, Vec_Int_t * vTree )
{
    Vec_Bit_t * vIsLeaf = Vec_BitStart( Gia_ManObjNum(p) );
    Vec_Bit_t * vMarked = Vec_BitStart( Gia_ManObjNum(p) ) ;
    Gia_Obj_t * pObj;
    int i, k = 0, Box, Rank;
    // mark leaves
    Vec_IntForEachEntryDouble( vTree, Box, Rank, i )
    {
        Vec_BitWriteEntry( vIsLeaf, Vec_IntEntry(vAdds, 6*Box+0), 1 );
        Vec_BitWriteEntry( vIsLeaf, Vec_IntEntry(vAdds, 6*Box+1), 1 );
        Vec_BitWriteEntry( vIsLeaf, Vec_IntEntry(vAdds, 6*Box+2), 1 );
    }
    Vec_IntForEachEntryDouble( vTree, Box, Rank, i )
    {
        Vec_BitWriteEntry( vIsLeaf, Vec_IntEntry(vAdds, 6*Box+3), 0 );
        Vec_BitWriteEntry( vIsLeaf, Vec_IntEntry(vAdds, 6*Box+4), 0 );
    }
    // mark TFI of leaves
    Gia_ManForEachAnd( p, pObj, i )
        if ( Vec_BitEntry(vIsLeaf, i) )
            Acec_TreeMarkTFI_rec( p, i, vMarked );
204 205 206
    // additional one
//if ( 10942 < Gia_ManObjNum(p) )
//    Acec_TreeMarkTFI_rec( p, 10942, vMarked );
207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231
    // remove those that overlap with the marked TFI
    Vec_IntForEachEntryDouble( vTree, Box, Rank, i )
    {
        if ( Vec_BitEntry(vMarked, Vec_IntEntry(vAdds, 6*Box+3)) || Vec_BitEntry(vMarked, Vec_IntEntry(vAdds, 6*Box+4)) )
        {
            printf( "Removing box %d=(%d,%d) of rank %d.\n", Box, Vec_IntEntry(vAdds, 6*Box+3), Vec_IntEntry(vAdds, 6*Box+4), Rank ); 
            continue;
        }
        Vec_IntWriteEntry( vTree, k++, Box );
        Vec_IntWriteEntry( vTree, k++, Rank );
    }
    Vec_IntShrink( vTree, k );
    Vec_BitFree( vIsLeaf );
    Vec_BitFree( vMarked );
}
void Acec_TreeFilterTrees2( Gia_Man_t * p, Vec_Int_t * vAdds, Vec_Wec_t * vTrees )
{
    Vec_Int_t * vLevel;
    int i;
    Vec_WecForEachLevel( vTrees, vLevel, i )
        Acec_TreeFilterOne2( p, vAdds, vLevel );
}

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

232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259
  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Acec_TreeVerifyPhaseOne_rec( Gia_Man_t * p, Gia_Obj_t * pObj )
{
    int Truth0, Truth1;
    if ( Gia_ObjIsTravIdCurrent(p, pObj) )
        return pObj->Value;
    Gia_ObjSetTravIdCurrent(p, pObj);
    assert( Gia_ObjIsAnd(pObj) );
    assert( !Gia_ObjIsXor(pObj) );
    Truth0 = Acec_TreeVerifyPhaseOne_rec( p, Gia_ObjFanin0(pObj) );
    Truth1 = Acec_TreeVerifyPhaseOne_rec( p, Gia_ObjFanin1(pObj) );
    Truth0 = Gia_ObjFaninC0(pObj) ? 0xFF & ~Truth0 : Truth0;
    Truth1 = Gia_ObjFaninC1(pObj) ? 0xFF & ~Truth1 : Truth1;
    return (pObj->Value = Truth0 & Truth1);
}
void Acec_TreeVerifyPhaseOne( Gia_Man_t * p, Vec_Int_t * vAdds, int iBox )
{
    Gia_Obj_t * pObj;
    unsigned TruthXor, TruthMaj, Truths[3] = { 0xAA, 0xCC, 0xF0 };
    int k, iObj, fFadd = Vec_IntEntry(vAdds, 6*iBox+2) > 0;
260
    int fFlip = !fFadd && Acec_SignBit2(vAdds, iBox, 2);
261 262 263 264 265 266 267 268

    Gia_ManIncrementTravId( p );
    for ( k = 0; k < 3; k++ )
    {
        iObj = Vec_IntEntry( vAdds, 6*iBox+k );
        if ( iObj == 0 )
            continue;
        pObj = Gia_ManObj( p, iObj );
269
        pObj->Value = (Acec_SignBit2(vAdds, iBox, k) ^ fFlip) ? 0xFF & ~Truths[k] : Truths[k];
270 271 272 273 274
        Gia_ObjSetTravIdCurrent( p, pObj );
    }

    iObj = Vec_IntEntry( vAdds, 6*iBox+3 );
    TruthXor = Acec_TreeVerifyPhaseOne_rec( p, Gia_ManObj(p, iObj) );
275
    TruthXor = (Acec_SignBit2(vAdds, iBox, 3) ^ fFlip) ? 0xFF & ~TruthXor : TruthXor;
276 277 278

    iObj = Vec_IntEntry( vAdds, 6*iBox+4 );
    TruthMaj = Acec_TreeVerifyPhaseOne_rec( p, Gia_ManObj(p, iObj) );
279
    TruthMaj = (Acec_SignBit2(vAdds, iBox, 4) ^ fFlip) ? 0xFF & ~TruthMaj : TruthMaj;
280 281 282 283 284 285 286 287 288 289

    if ( fFadd ) // FADD
    {
        if ( TruthXor != 0x96 )
            printf( "Fadd %d sum %d is wrong.\n", iBox, Vec_IntEntry( vAdds, 6*iBox+3 ) );
        if ( TruthMaj != 0xE8 )
            printf( "Fadd %d carry %d is wrong.\n", iBox, Vec_IntEntry( vAdds, 6*iBox+4 ) );
    }
    else
    {
290 291
        //printf( "Sign1 = %d%d%d %d\n", Acec_SignBit(vAdds, iBox, 0), Acec_SignBit(vAdds, iBox, 1), Acec_SignBit(vAdds, iBox, 2), Acec_SignBit(vAdds, iBox, 3) );
        //printf( "Sign2 = %d%d%d %d%d\n", Acec_SignBit2(vAdds, iBox, 0), Acec_SignBit2(vAdds, iBox, 1), Acec_SignBit2(vAdds, iBox, 2), Acec_SignBit2(vAdds, iBox, 3), Acec_SignBit2(vAdds, iBox, 4) );
292 293 294 295 296 297 298 299 300 301 302 303 304 305
        if ( TruthXor != 0x66 )
            printf( "Hadd %d sum %d is wrong.\n", iBox, Vec_IntEntry( vAdds, 6*iBox+3 ) );
        if ( TruthMaj != 0x88 )
            printf( "Hadd %d carry %d is wrong.\n", iBox, Vec_IntEntry( vAdds, 6*iBox+4 ) );
    }
}
void Acec_TreeVerifyPhases( Gia_Man_t * p, Vec_Int_t * vAdds, Vec_Wec_t * vBoxes )
{
    Vec_Int_t * vLevel;
    int i, k, Box;
    Vec_WecForEachLevel( vBoxes, vLevel, i )
        Vec_IntForEachEntry( vLevel, Box, k )
            Acec_TreeVerifyPhaseOne( p, vAdds, Box );
}
306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335
void Acec_TreeVerifyPhases2( Gia_Man_t * p, Vec_Int_t * vAdds, Vec_Wec_t * vBoxes )
{
    Vec_Bit_t * vPhase = Vec_BitStart( Gia_ManObjNum(p) );
    Vec_Bit_t * vRoots = Vec_BitStart( Gia_ManObjNum(p) );
    Vec_Int_t * vLevel;
    int i, k, n, Box;
    // mark all output points and their values
    Vec_WecForEachLevel( vBoxes, vLevel, i )
        Vec_IntForEachEntry( vLevel, Box, k )
        {
            Vec_BitWriteEntry( vRoots, Vec_IntEntry( vAdds, 6*Box+3 ), 1 );
            Vec_BitWriteEntry( vRoots, Vec_IntEntry( vAdds, 6*Box+4 ), 1 );
            Vec_BitWriteEntry( vPhase, Vec_IntEntry( vAdds, 6*Box+3 ), Acec_SignBit2(vAdds, Box, 3) );
            Vec_BitWriteEntry( vPhase, Vec_IntEntry( vAdds, 6*Box+4 ), Acec_SignBit2(vAdds, Box, 4) );
        }
    // compare with input points
    Vec_WecForEachLevel( vBoxes, vLevel, i )
        Vec_IntForEachEntry( vLevel, Box, k )
            for ( n = 0; n < 3; n++ )
            {
                if ( !Vec_BitEntry(vRoots, Vec_IntEntry(vAdds, 6*Box+n)) )
                    continue;
                if ( Vec_BitEntry(vPhase, Vec_IntEntry(vAdds, 6*Box+n)) == Acec_SignBit2(vAdds, Box, n) )
                    continue;
                printf( "Phase of input %d=%d is mismatched in box %d=(%d,%d).\n",
                    n, Vec_IntEntry(vAdds, 6*Box+n), Box, Vec_IntEntry(vAdds, 6*Box+3), Vec_IntEntry(vAdds, 6*Box+4) );
            }
    Vec_BitFree( vPhase );
    Vec_BitFree( vRoots );
}
336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366
void Acec_TreeVerifyConnections( Gia_Man_t * p, Vec_Int_t * vAdds, Vec_Wec_t * vBoxes )
{
    Vec_Int_t * vCounts = Vec_IntStartFull( Gia_ManObjNum(p) );
    Vec_Int_t * vLevel;
    int i, k, n, Box;
    // mark outputs
    Vec_WecForEachLevel( vBoxes, vLevel, i )
        Vec_IntForEachEntry( vLevel, Box, k )
        {
            Vec_IntWriteEntry( vCounts, Vec_IntEntry( vAdds, 6*Box+3 ), 0 );
            Vec_IntWriteEntry( vCounts, Vec_IntEntry( vAdds, 6*Box+4 ), 0 );
        }
    // count fanouts
    Vec_WecForEachLevel( vBoxes, vLevel, i )
        Vec_IntForEachEntry( vLevel, Box, k )
            for ( n = 0; n < 3; n++ )
                if ( Vec_IntEntry( vCounts, Vec_IntEntry(vAdds, 6*Box+n) ) != -1 )
                    Vec_IntAddToEntry( vCounts, Vec_IntEntry(vAdds, 6*Box+n), 1 );
    // print out
    printf( "The adder tree has %d internal cut points. ", Vec_IntCountLarger(vCounts, -1) );
    if ( Vec_IntCountLarger(vCounts, 1) == 0 )
        printf( "There is no internal fanouts.\n" );
    else
    {
        printf( "These %d points have more than one fanout:\n", Vec_IntCountLarger(vCounts, 1) );
        Vec_IntForEachEntry( vCounts, Box, i )
            if ( Box > 1 )
                printf( "Node %d(lev %d) has fanout %d.\n", i, Gia_ObjLevelId(p, i), Box );
    }
    Vec_IntFree( vCounts );
}
367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388

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

  Synopsis    [Creates polarity.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
Vec_Int_t * Acec_TreeCarryMap( Gia_Man_t * p, Vec_Int_t * vAdds, Vec_Wec_t * vBoxes )
{
    Vec_Int_t * vMap = Vec_IntStartFull( Gia_ManObjNum(p) );
    Vec_Int_t * vLevel;
    int i, k, Box;
    Vec_WecForEachLevel( vBoxes, vLevel, i )
        Vec_IntForEachEntry( vLevel, Box, k )
            Vec_IntWriteEntry( vMap, Vec_IntEntry(vAdds, 6*Box+4), Box );
    return vMap;
}
389
void Acec_TreePhases_rec( Gia_Man_t * p, Vec_Int_t * vAdds, Vec_Int_t * vMap, int Node, int fPhase, Vec_Bit_t * vVisit )
390
{
391
    int k, iBox, iXor, fXorPhase, fPhaseThis;
392 393 394 395 396
    assert( Node != 0 );
    iBox = Vec_IntEntry( vMap, Node );
    if ( iBox == -1 )
        return;
    assert( Node == Vec_IntEntry( vAdds, 6*iBox+4 ) );
397 398 399
    if ( Vec_BitEntry(vVisit, iBox) )
        return;
    Vec_BitWriteEntry( vVisit, iBox, 1 );
400
    iXor = Vec_IntEntry( vAdds, 6*iBox+3 );
401
    fXorPhase = Acec_SignBit(vAdds, iBox, 3);
402 403
    if ( Vec_IntEntry(vAdds, 6*iBox+2) == 0 )
    {
404 405 406 407 408 409
        //fPhaseThis = Acec_SignBit( vAdds, iBox, 2 ) ^ fPhase;
        //fXorPhase ^= fPhaseThis;
        //Acec_SignSetBit2( vAdds, iBox, 2, fPhaseThis ); // complemented HADD -- create const1 input
        fPhase ^= Acec_SignBit( vAdds, iBox, 2 );
        fXorPhase ^= fPhase;
        Acec_SignSetBit2( vAdds, iBox, 2, fPhase ); // complemented HADD -- create const1 input
410 411 412 413 414 415
    }
    for ( k = 0; k < 3; k++ )
    {
        int iObj = Vec_IntEntry( vAdds, 6*iBox+k );
        if ( iObj == 0 )
            continue;
416
        fPhaseThis = Acec_SignBit(vAdds, iBox, k) ^ fPhase;
417
        fXorPhase ^= fPhaseThis;
418 419
        Acec_TreePhases_rec( p, vAdds, vMap, iObj, fPhaseThis, vVisit );
        Acec_SignSetBit2( vAdds, iBox, k, fPhaseThis );
420
    }
421 422
    Acec_SignSetBit2( vAdds, iBox, 3, fXorPhase );
    Acec_SignSetBit2( vAdds, iBox, 4, fPhase );
423 424 425 426
}

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

427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443
  Synopsis    [Find internal cut points with exactly one adder fanin/fanout.]

  Description [Returns a map of point into its input/output adder.]
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
void Acec_TreeAddInOutPoint( Vec_Int_t * vMap, int iObj, int iAdd, int fOut )
{
    int * pPlace = Vec_IntEntryP( vMap, Abc_Var2Lit(iObj, fOut) );
    if ( *pPlace == -1 )
        *pPlace = iAdd;
    else if ( *pPlace >= 0 )
        *pPlace = -2;
}
444
Vec_Int_t * Acec_TreeFindPoints( Gia_Man_t * p, Vec_Int_t * vAdds, Vec_Bit_t * vIgnore )
445 446 447 448 449
{
    Vec_Int_t * vMap = Vec_IntStartFull( 2*Gia_ManObjNum(p) );
    int i;
    for ( i = 0; 6*i < Vec_IntSize(vAdds); i++ )
    {
450
        if ( vIgnore && (Vec_BitEntry(vIgnore, Vec_IntEntry(vAdds, 6*i+3)) || Vec_BitEntry(vIgnore, Vec_IntEntry(vAdds, 6*i+4))) )
451
            continue;
452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502
        Acec_TreeAddInOutPoint( vMap, Vec_IntEntry(vAdds, 6*i+0), i, 0 );
        Acec_TreeAddInOutPoint( vMap, Vec_IntEntry(vAdds, 6*i+1), i, 0 );
        Acec_TreeAddInOutPoint( vMap, Vec_IntEntry(vAdds, 6*i+2), i, 0 );
        Acec_TreeAddInOutPoint( vMap, Vec_IntEntry(vAdds, 6*i+3), i, 1 );
        Acec_TreeAddInOutPoint( vMap, Vec_IntEntry(vAdds, 6*i+4), i, 1 );
    }
    return vMap;
}

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

  Synopsis    [Find adder trees as groups of adders connected vis cut-points.]

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
int Acec_TreeWhichPoint( Vec_Int_t * vAdds, int iAdd, int iObj )
{
    int k;
    for ( k = 0; k < 5; k++ )
        if ( Vec_IntEntry(vAdds, 6*iAdd+k) == iObj )
            return k;
    assert( 0 );
    return -1;
}
void Acec_TreeFindTrees2_rec( Vec_Int_t * vAdds, Vec_Int_t * vMap, int iAdd, int Rank, Vec_Int_t * vTree, Vec_Bit_t * vFound )
{
    extern void Acec_TreeFindTrees_rec( Vec_Int_t * vAdds, Vec_Int_t * vMap, int iObj, int Rank, Vec_Int_t * vTree, Vec_Bit_t * vFound );
    int k;
    if ( Vec_BitEntry(vFound, iAdd) )
        return;
    Vec_BitWriteEntry( vFound, iAdd, 1 );
    Vec_IntPush( vTree, iAdd );
    Vec_IntPush( vTree, Rank );
    //printf( "Assigning rank %d to (%d:%d).\n", Rank, Vec_IntEntry(vAdds, 6*iAdd+3), Vec_IntEntry(vAdds, 6*iAdd+4) );
    for ( k = 0; k < 5; k++ )
        Acec_TreeFindTrees_rec( vAdds, vMap, Vec_IntEntry(vAdds, 6*iAdd+k), k == 4 ? Rank + 1 : Rank, vTree, vFound );
}
void Acec_TreeFindTrees_rec( Vec_Int_t * vAdds, Vec_Int_t * vMap, int iObj, int Rank, Vec_Int_t * vTree, Vec_Bit_t * vFound )
{
    int In  = Vec_IntEntry( vMap, Abc_Var2Lit(iObj, 1) );
    int Out = Vec_IntEntry( vMap, Abc_Var2Lit(iObj, 0) );
    if ( In < 0 || Out < 0 )
        return;
    Acec_TreeFindTrees2_rec( vAdds, vMap, In,  Acec_TreeWhichPoint(vAdds, In, iObj) == 4 ? Rank-1 : Rank, vTree, vFound );
    Acec_TreeFindTrees2_rec( vAdds, vMap, Out, Rank, vTree, vFound );
}
503
Vec_Wec_t * Acec_TreeFindTrees( Gia_Man_t * p, Vec_Int_t * vAdds, Vec_Bit_t * vIgnore, int fFilterIn, int fFilterOut )
504 505
{
    Vec_Wec_t * vTrees = Vec_WecAlloc( 10 );
506
    Vec_Int_t * vMap   = Acec_TreeFindPoints( p, vAdds, vIgnore );
507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528
    Vec_Bit_t * vFound = Vec_BitStart( Vec_IntSize(vAdds)/6 );
    Vec_Int_t * vTree;
    int i, k, In, Out, Box, Rank, MinRank;
    // go through the cut-points
    Vec_IntForEachEntryDouble( vMap, In, Out, i )
    {
        if ( In < 0 || Out < 0 )
            continue;
        assert( Vec_BitEntry(vFound, In) == Vec_BitEntry(vFound, Out) );
        if ( Vec_BitEntry(vFound, In) )
            continue;
        vTree = Vec_WecPushLevel( vTrees );
        Acec_TreeFindTrees_rec( vAdds, vMap, i/2, 0, vTree, vFound );
        // normalize rank
        MinRank = ABC_INFINITY;
        Vec_IntForEachEntryDouble( vTree, Box, Rank, k )
            MinRank = Abc_MinInt( MinRank, Rank );
        Vec_IntForEachEntryDouble( vTree, Box, Rank, k )
            Vec_IntWriteEntry( vTree, k+1, Rank - MinRank );
    }
    Vec_BitFree( vFound );
    Vec_IntFree( vMap );
529
    // filter trees
530 531 532 533
    if ( fFilterIn )
        Acec_TreeFilterTrees2( p, vAdds, vTrees );
    else if ( fFilterOut )
        Acec_TreeFilterTrees( p, vAdds, vTrees );
534 535 536 537 538 539 540 541 542 543 544 545 546 547 548
    // sort by size
    Vec_WecSort( vTrees, 1 );
    return vTrees;
}
void Acec_TreeFindTreesTest( Gia_Man_t * p )
{
    Vec_Wec_t * vTrees;

    abctime clk = Abc_Clock();
    Vec_Int_t * vAdds = Ree_ManComputeCuts( p, NULL, 1 );
    int nFadds = Ree_ManCountFadds( vAdds );
    printf( "Detected %d adders (%d FAs and %d HAs).  ", Vec_IntSize(vAdds)/6, nFadds, Vec_IntSize(vAdds)/6-nFadds );
    Abc_PrintTime( 1, "Time", Abc_Clock() - clk );

    clk = Abc_Clock();
549
    vTrees = Acec_TreeFindTrees( p, vAdds, NULL, 0, 0 );
550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567
    printf( "Collected %d trees with %d adders in them.  ", Vec_WecSize(vTrees), Vec_WecSizeSize(vTrees)/2 );
    Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
    Vec_WecPrint( vTrees, 0 );

    Vec_WecFree( vTrees );
    Vec_IntFree( vAdds );
}


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

  Synopsis    [Derives one adder tree.]

  Description []
               
  SideEffects []

  SeeAlso     []
568
`
569
***********************************************************************/
570 571 572 573 574 575
void Acec_PrintAdders( Vec_Wec_t * vBoxes, Vec_Int_t * vAdds )
{
    Vec_Int_t * vLevel;
    int i, k, iBox;
    Vec_WecForEachLevel( vBoxes, vLevel, i )
    {
576
        printf( " %4d : %2d  {", i, Vec_IntSize(vLevel) );
577
        Vec_IntForEachEntry( vLevel, iBox, k )
578
        {
579 580
            printf( " %s%d=(%d,%d)", Vec_IntEntry(vAdds, 6*iBox+2) == 0 ? "*":"", iBox, 
                                     Vec_IntEntry(vAdds, 6*iBox+3), Vec_IntEntry(vAdds, 6*iBox+4) );
581 582
            //printf( "(%d,%d,%d)", Vec_IntEntry(vAdds, 6*iBox+0), Vec_IntEntry(vAdds, 6*iBox+1), Vec_IntEntry(vAdds, 6*iBox+2) );
        }
583 584 585
        printf( " }\n" );
    }
}
586
void Acec_TreePrintBox( Acec_Box_t * pBox, Vec_Int_t * vAdds )
587 588 589 590 591 592 593
{
    printf( "Adders:\n" );
    Acec_PrintAdders( pBox->vAdds, vAdds );
    printf( "Inputs:\n" );
    Vec_WecPrintLits( pBox->vLeafLits );
    printf( "Outputs:\n" );
    Vec_WecPrintLits( pBox->vRootLits );
594 595 596 597
//    printf( "Node %d has level %d.\n", 3715, Gia_ObjLevelId(pBox->pGia, 3715) );
//    printf( "Node %d has level %d.\n", 167, Gia_ObjLevelId(pBox->pGia, 167) );
//    printf( "Node %d has level %d.\n", 278, Gia_ObjLevelId(pBox->pGia, 278) );
//    printf( "Node %d has level %d.\n", 597, Gia_ObjLevelId(pBox->pGia, 597) );
598 599
}

600 601 602 603 604 605 606
int Acec_CreateBoxMaxRank( Vec_Int_t * vTree )
{
    int k, Box, Rank, MaxRank = 0;
    Vec_IntForEachEntryDouble( vTree, Box, Rank, k )
        MaxRank = Abc_MaxInt( MaxRank, Rank );
    return MaxRank;
}
607 608
Acec_Box_t * Acec_CreateBox( Gia_Man_t * p, Vec_Int_t * vAdds, Vec_Int_t * vTree )
{
609
    int MaxRank = Acec_CreateBoxMaxRank(vTree);
610
    Vec_Bit_t * vVisit  = Vec_BitStart( Vec_IntSize(vAdds)/6 );
611 612 613
    Vec_Bit_t * vIsLeaf = Vec_BitStart( Gia_ManObjNum(p) );
    Vec_Bit_t * vIsRoot = Vec_BitStart( Gia_ManObjNum(p) );
    Vec_Int_t * vLevel, * vMap;
614
    int i, j, k, Box, Rank;//, Count = 0;
615

616
    Acec_Box_t * pBox = ABC_CALLOC( Acec_Box_t, 1 );
617 618 619 620
    pBox->pGia        = p;
    pBox->vAdds       = Vec_WecStart( MaxRank + 1 );
    pBox->vLeafLits   = Vec_WecStart( MaxRank + 1 );
    pBox->vRootLits   = Vec_WecStart( MaxRank + 2 );
621

622 623 624
    // collect boxes; mark inputs/outputs
    Vec_IntForEachEntryDouble( vTree, Box, Rank, i )
    {
625 626 627 628 629
//        if ( 37 == Box && 6 == Rank )
//        {
//            printf( "Skipping one adder...\n" );
//            continue;
//        }
630 631 632 633 634
        Vec_BitWriteEntry( vIsLeaf, Vec_IntEntry(vAdds, 6*Box+0), 1 );
        Vec_BitWriteEntry( vIsLeaf, Vec_IntEntry(vAdds, 6*Box+1), 1 );
        Vec_BitWriteEntry( vIsLeaf, Vec_IntEntry(vAdds, 6*Box+2), 1 );
        Vec_BitWriteEntry( vIsRoot, Vec_IntEntry(vAdds, 6*Box+3), 1 );
        Vec_BitWriteEntry( vIsRoot, Vec_IntEntry(vAdds, 6*Box+4), 1 );
635
        Vec_WecPush( pBox->vAdds, Rank, Box );
636 637 638 639
    }
    // sort each level
    Vec_WecForEachLevel( pBox->vAdds, vLevel, i )
        Vec_IntSort( vLevel, 0 );
640

641
    // set phases starting from roots
642
    vMap = Acec_TreeCarryMap( p, vAdds, pBox->vAdds );
643 644 645
    Vec_WecForEachLevelReverse( pBox->vAdds, vLevel, i )
        Vec_IntForEachEntry( vLevel, Box, k )
            if ( !Vec_BitEntry( vIsLeaf, Vec_IntEntry(vAdds, 6*Box+4) ) )
646 647
            {
                //printf( "Pushing phase of output %d of box %d\n", Vec_IntEntry(vAdds, 6*Box+4), Box );
648
                Acec_TreePhases_rec( p, vAdds, vMap, Vec_IntEntry(vAdds, 6*Box+4), Vec_IntEntry(vAdds, 6*Box+2) != 0, vVisit );
649
            }
650
    Acec_TreeVerifyPhases( p, vAdds, pBox->vAdds );
651 652
    Acec_TreeVerifyPhases2( p, vAdds, pBox->vAdds );
    Vec_BitFree( vVisit );
653
    Vec_IntFree( vMap );
654

655
    // collect inputs/outputs
656 657 658 659 660 661 662 663 664
    Vec_BitWriteEntry( vIsRoot, 0, 1 );
    Vec_WecForEachLevel( pBox->vAdds, vLevel, i )
        Vec_IntForEachEntry( vLevel, Box, j )
        {
            for ( k = 0; k < 3; k++ )
                if ( !Vec_BitEntry( vIsRoot, Vec_IntEntry(vAdds, 6*Box+k) ) )
                    Vec_WecPush( pBox->vLeafLits, i, Abc_Var2Lit(Vec_IntEntry(vAdds, 6*Box+k), Acec_SignBit2(vAdds, Box, k)) );
            for ( k = 3; k < 5; k++ )
                if ( !Vec_BitEntry( vIsLeaf, Vec_IntEntry(vAdds, 6*Box+k) ) )
665 666 667 668 669 670
                {
                    //if ( Vec_IntEntry(vAdds, 6*Box+k) == 10942 )
                    //{
                    //    printf( "++++++++++++ Skipping special\n" );
                    //    continue;
                    //}
671
                    Vec_WecPush( pBox->vRootLits, k == 4 ? i + 1 : i, Abc_Var2Lit(Vec_IntEntry(vAdds, 6*Box+k), Acec_SignBit2(vAdds, Box, k)) );
672
                }
673 674 675
            if ( Vec_IntEntry(vAdds, 6*Box+2) == 0 && Acec_SignBit2(vAdds, Box, 2) )
                Vec_WecPush( pBox->vLeafLits, i, 1 );
        }
676 677 678 679 680 681
    Vec_BitFree( vIsLeaf );
    Vec_BitFree( vIsRoot );
    // sort each level
    Vec_WecForEachLevel( pBox->vLeafLits, vLevel, i )
        Vec_IntSort( vLevel, 0 );
    Vec_WecForEachLevel( pBox->vRootLits, vLevel, i )
682
        Vec_IntSort( vLevel, 1 );
683
    //return pBox;
684
/*
685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706
    // push literals forward
    //Vec_WecPrint( pBox->vLeafLits, 0 );
    Vec_WecForEachLevel( pBox->vLeafLits, vLevel, i )
    {
        int This, Prev = Vec_IntEntry(vLevel, 0);
        Vec_IntForEachEntryStart( vLevel, This, j, 1 )
        {
            if ( Prev != This )
            {
                Prev = This;
                continue;
            }
            if ( i+1 >= Vec_WecSize(pBox->vLeafLits) )
                continue;
            Vec_IntPushOrder( Vec_WecEntry(pBox->vLeafLits, i+1), This );
            Vec_IntDrop( vLevel, j-- );
            Vec_IntDrop( vLevel, j-- );
            Prev = -1;
            Count++;
        }
    }
    printf( "Pushed forward %d input literals.\n", Count );
707
*/
708
    //Vec_WecPrint( pBox->vLeafLits, 0 );
709 710 711 712 713 714
    return pBox;
}
void Acec_CreateBoxTest( Gia_Man_t * p )
{
    Acec_Box_t * pBox;
    Vec_Wec_t * vTrees;
715
    Vec_Int_t * vTree;
716 717 718

    abctime clk = Abc_Clock();
    Vec_Int_t * vAdds = Ree_ManComputeCuts( p, NULL, 1 );
719
    int i, nFadds = Ree_ManCountFadds( vAdds );
720 721 722 723
    printf( "Detected %d adders (%d FAs and %d HAs).  ", Vec_IntSize(vAdds)/6, nFadds, Vec_IntSize(vAdds)/6-nFadds );
    Abc_PrintTime( 1, "Time", Abc_Clock() - clk );

    clk = Abc_Clock();
724
    vTrees = Acec_TreeFindTrees( p, vAdds, NULL, 0, 0 );
725 726
    printf( "Collected %d trees with %d adders in them.  ", Vec_WecSize(vTrees), Vec_WecSizeSize(vTrees)/2 );
    Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
727
    //Vec_WecPrint( vTrees, 0 );
728

729 730 731 732 733 734
    Vec_WecForEachLevel( vTrees, vTree, i )
    {
        pBox = Acec_CreateBox( p, vAdds, Vec_WecEntry(vTrees, i) );
        printf( "Processing tree %d:  Ranks = %d.  Adders = %d.  Leaves = %d.  Roots = %d.\n", 
            i, Vec_WecSize(pBox->vAdds), Vec_WecSizeSize(pBox->vAdds), 
            Vec_WecSizeSize(pBox->vLeafLits), Vec_WecSizeSize(pBox->vRootLits)  );
735
        Acec_TreePrintBox( pBox, vAdds );
736
        Acec_BoxFreeP( &pBox );
737
    }
738 739 740 741 742 743 744

    Vec_WecFree( vTrees );
    Vec_IntFree( vAdds );
}

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

745 746 747 748 749 750 751 752 753
  Synopsis    []

  Description []
               
  SideEffects []

  SeeAlso     []

***********************************************************************/
754
Acec_Box_t * Acec_DeriveBox( Gia_Man_t * p, Vec_Bit_t * vIgnore, int fFilterIn, int fFilterOut, int fVerbose )
755
{
756 757
    Acec_Box_t * pBox = NULL;
    Vec_Int_t * vAdds = Ree_ManComputeCuts( p, NULL, fVerbose );
758
    Vec_Wec_t * vTrees = Acec_TreeFindTrees( p, vAdds, vIgnore, fFilterIn, fFilterOut );
759
    if ( vTrees && Vec_WecSize(vTrees) > 0 )
760
    {
761
        pBox = Acec_CreateBox( p, vAdds, Vec_WecEntry(vTrees, 0) );
762 763
        Acec_VerifyBoxLeaves( pBox, vIgnore );
    }
764 765 766 767 768
    if ( pBox )//&& fVerbose )
        printf( "Processing tree %d:  Ranks = %d.  Adders = %d.  Leaves = %d.  Roots = %d.\n", 
            0, Vec_WecSize(pBox->vAdds), Vec_WecSizeSize(pBox->vAdds), 
            Vec_WecSizeSize(pBox->vLeafLits), Vec_WecSizeSize(pBox->vRootLits)  );
    if ( pBox && fVerbose )
769
        Acec_TreePrintBox( pBox, vAdds );
770
    //Acec_PrintAdders( pBox0->vAdds, vAdds );
771
    //Acec_MultDetectInputs( p, pBox->vLeafLits, pBox->vRootLits );
772 773 774
    Vec_WecFreeP( &vTrees );
    Vec_IntFree( vAdds );
    return pBox;
775 776 777 778 779 780 781 782 783
}

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


ABC_NAMESPACE_IMPL_END