reoswap.c

主要进行大规模的电路综合

/**CFile****************************************************************

  FileName    [reoSwap.c]

  PackageName [REO: A specialized DD reordering engine.]

  Synopsis    [Implementation of the two-variable swap.]

  Author      [Alan Mishchenko]
  
  Affiliation [UC Berkeley]

  Date        [Ver. 1.0. Started - October 15, 2002.]

  Revision    [$Id: reoSwap.c,v 1.2 2003/05/26 15:46:33 alanmi Exp $]

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

#include "reo.h"

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

#define AddToLinkedList( ppList, pLink )   (((pLink)->Next = *(ppList)), (*(ppList) = (pLink)))

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

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

  Synopsis    []

  Description [Takes the level (lev0) of the plane, which should be swapped 
  with the next plane. Returns the gain using the current cost function.]

  SideEffects []

  SeeAlso     []

***********************************************************************/
double reoReorderSwapAdjacentVars( reo_man * p, int lev0, int fMovingUp )
{
	// the levels in the decision diagram
	int lev1 = lev0 + 1, lev2 = lev0 + 2;
	// the new nodes on lev0
	reo_unit * pLoop, * pUnit;
	// the new nodes on lev1
	reo_unit * pNewPlane20, * pNewPlane21, * pNewPlane20R;
	reo_unit * pUnitE, * pUnitER, * pUnitT;
	// the nodes below lev1
	reo_unit * pNew1E, * pNew1T, * pNew2E, * pNew2T;
	reo_unit * pNew1ER, * pNew2ER;
	// the old linked lists
	reo_unit * pListOld0 = p->pPlanes[lev0].pHead;
	reo_unit * pListOld1 = p->pPlanes[lev1].pHead;
	// working planes and one more temporary plane
	reo_unit * pListNew0 = NULL, ** ppListNew0 = &pListNew0;
	reo_unit * pListNew1 = NULL, ** ppListNew1 = &pListNew1; 
	reo_unit * pListTemp = NULL, ** ppListTemp = &pListTemp; 
	// various integer variables
	int fComp, fCompT, fFound, nWidthCofs, HKey, fInteract, temp, c;
	// statistical variables
	int nNodesUpMovedDown  = 0;
	int nNodesDownMovedUp  = 0;
	int nNodesUnrefRemoved = 0;
	int nNodesUnrefAdded   = 0;
	int nWidthReduction    = 0;
	double AplWeightTotalLev0;
	double AplWeightTotalLev1;
	double AplWeightHalf;
	double AplWeightPrev;
	double AplWeightAfter;
	double nCostGain;     

	// set the old lists
	assert( lev0 >= 0 && lev1 < p->nSupp );
	pListOld0 = p->pPlanes[lev0].pHead;
	pListOld1 = p->pPlanes[lev1].pHead;

	// make sure the planes have nodes
	assert( p->pPlanes[lev0].statsNodes && p->pPlanes[lev1].statsNodes );
	assert( pListOld0 && pListOld1 );

	if ( p->fMinWidth )
	{
		// verify that the width parameters are set correctly
		reoProfileWidthVerifyLevel( p->pPlanes + lev0, lev0 );
		reoProfileWidthVerifyLevel( p->pPlanes + lev1, lev1 );
		// start the storage for cofactors
		nWidthCofs = 0;
	}
	else if ( p->fMinApl )
	{
		AplWeightPrev      = p->nAplCur;
		AplWeightAfter     = p->nAplCur;
		AplWeightTotalLev0 = 0.0;
		AplWeightTotalLev1 = 0.0;
	}

	// check if the planes interact
	fInteract = 0; // assume that they do not interact
	for ( pUnit = pListOld0; pUnit; pUnit = pUnit->Next )
	{
		if ( pUnit->pT->lev == lev1 || Unit_Regular(pUnit->pE)->lev == lev1 )
		{
			fInteract = 1;
			break;
		}
		// change the level now, this is done for efficiency reasons
		pUnit->lev = lev1;
	}

	// set the new signature for hashing
	p->nSwaps++;
	if ( !fInteract )
//	if ( 0 )
	{
		// perform the swap without interaction
		p->nNISwaps++;

		// change the levels
		if ( p->fMinWidth )
		{
			// go through the current lower level, which will become upper
			for ( pUnit = pListOld1; pUnit; pUnit = pUnit->Next )
			{
				pUnit->lev = lev0;

				pUnitER = Unit_Regular(pUnit->pE);
				if ( pUnitER->TopRef > lev0 )
				{
					if ( pUnitER->Sign != p->nSwaps )
					{
						if ( pUnitER->TopRef == lev2 )
						{
							pUnitER->TopRef = lev1;
							nWidthReduction--;
						}
						else
						{
							assert( pUnitER->TopRef == lev1 );
						}
						pUnitER->Sign   = p->nSwaps;
					}
				}

				pUnitT  = pUnit->pT;
				if ( pUnitT->TopRef > lev0 )
				{
					if ( pUnitT->Sign != p->nSwaps )
					{
						if ( pUnitT->TopRef == lev2 )
						{
							pUnitT->TopRef = lev1;
							nWidthReduction--;
						}
						else
						{
							assert( pUnitT->TopRef == lev1 );
						}
						pUnitT->Sign   = p->nSwaps;
					}
				}

			}

			// go through the current upper level, which will become lower
			for ( pUnit = pListOld0; pUnit; pUnit = pUnit->Next )
			{
				pUnit->lev = lev1;

				pUnitER = Unit_Regular(pUnit->pE);
				if ( pUnitER->TopRef > lev0 )
				{
					if ( pUnitER->Sign != p->nSwaps )
					{
						assert( pUnitER->TopRef == lev1 );
						pUnitER->TopRef = lev2;
						pUnitER->Sign   = p->nSwaps;
						nWidthReduction++;
					}
				}

				pUnitT  = pUnit->pT;
				if ( pUnitT->TopRef > lev0 )
				{
					if ( pUnitT->Sign != p->nSwaps )
					{
						assert( pUnitT->TopRef == lev1 );
						pUnitT->TopRef = lev2;
						pUnitT->Sign   = p->nSwaps;
						nWidthReduction++;
					}
				}
			}
		}
		else
		{
//			for ( pUnit = pListOld0; pUnit; pUnit = pUnit->Next )
//				pUnit->lev = lev1;
			for ( pUnit = pListOld1; pUnit; pUnit = pUnit->Next )
				pUnit->lev = lev0;
		}

		// set the new linked lists, which will be attached to the planes
		pListNew0 = pListOld1;
		pListNew1 = pListOld0;

		if ( p->fMinApl )
		{
			AplWeightTotalLev0 = p->pPlanes[lev1].statsCost;
			AplWeightTotalLev1 = p->pPlanes[lev0].statsCost;
		}
		
		// set the changes in terms of nodes
		nNodesUpMovedDown = p->pPlanes[lev0].statsNodes; 
		nNodesDownMovedUp = p->pPlanes[lev1].statsNodes; 
		goto finish;
	}
	p->Signature++;


	// two-variable swap is done in three easy steps
	// previously I thought that steps (1) and (2) can be merged into one step
	// now it is clear that this cannot be done without changing a lot of other stuff...

	// (1) walk through the upper level, find units without cofactors in the lower level 
	//     and move them to the new lower level (while adding to the cache)
	// (2) walk through the uppoer level, and tranform all the remaning nodes 
	//     while employing cache for the new lower level
	// (3) walk through the old lower level, find those nodes whose ref counters are not zero, 
	//     and move them to the new uppoer level, free other nodes

	// (1) walk through the upper level, find units without cofactors in the lower level 
	//     and move them to the new lower level (while adding to the cache)
	for ( pLoop = pListOld0; pLoop; )
	{
		pUnit = pLoop;
		pLoop = pLoop->Next;

		pUnitE  = pUnit->pE;
		pUnitER = Unit_Regular(pUnitE);
		pUnitT  = pUnit->pT;

		if ( pUnitER->lev != lev1 && pUnitT->lev != lev1 )
		{
			//                before                        after
			//
			//                 <p1>           
			//              0 /    \ 1         
			//               /      \          
			//              /        \         
			//             /          \                     <p2n>   
			//            /            \                  0 /  \ 1 
			//           /              \                  /    \  
			//          /                \                /      \ 
			//         F0                F1              F0      F1

			// move to plane-2-new
			// nothing changes in the process (cofactors, ref counter, APL weight)
			pUnit->lev = lev1;
			AddToLinkedList( ppListNew1, pUnit );
			if ( p->fMinApl )
				AplWeightTotalLev1 += pUnit->Weight;

			// add to cache - find the cell with different signature (not the current one!)
			for (  HKey = hashKey3(p->Signature, pUnitE, pUnitT, p->nTableSize);
			       p->HTable[HKey].Sign == p->Signature;
				   HKey = (HKey+1) % p->nTableSize );
			assert( p->HTable[HKey].Sign != p->Signature );
			p->HTable[HKey].Sign = p->Signature;
			p->HTable[HKey].Arg1 = (unsigned)pUnitE;
			p->HTable[HKey].Arg2 = (unsigned)pUnitT;
			p->HTable[HKey].Arg3 = (unsigned)pUnit;

			nNodesUpMovedDown++;

			if ( p->fMinWidth )
			{
				// update the cofactors's top ref
				if ( pUnitER->TopRef > lev0 ) // the cofactor's top ref level is one of the current two levels
				{
					assert( pUnitER->TopRef == lev1 );
					pUnitER->TopRefNew = lev2;
					if ( pUnitER->Sign != p->nSwaps )
					{
						pUnitER->Sign      = p->nSwaps;  // set the current signature
						p->pWidthCofs[ nWidthCofs++ ] = pUnitER;
					}
				}
				if ( pUnitT->TopRef > lev0 ) // the cofactor's top ref level is one of the current two levels
				{
					assert( pUnitT->TopRef == lev1 );
					pUnitT->TopRefNew = lev2;
					if ( pUnitT->Sign != p->nSwaps )
					{
						pUnitT->Sign      = p->nSwaps;  // set the current signature
						p->pWidthCofs[ nWidthCofs++ ] = pUnitT;
					}
				}
			}
		}
		else
		{
			// add to the temporary plane
			AddToLinkedList( ppListTemp, pUnit );
		}
	}


	// (2) walk through the uppoer level, and tranform all the remaning nodes 
	//     while employing cache for the new lower level
	for ( pLoop = pListTemp; pLoop; )
	{
		pUnit = pLoop;
		pLoop = pLoop->Next;

		pUnitE  = pUnit->pE;
		pUnitER = Unit_Regular(pUnitE);
		pUnitT  = pUnit->pT;
		fComp   = (int)(pUnitER != pUnitE);

		// count the amount of weight to reduce the APL of the children of this node
		if ( p->fMinApl )
			AplWeightHalf = 0.5 * pUnit->Weight;

		// determine what situation is this
		if ( pUnitER->lev == lev1 && pUnitT->lev == lev1 )
		{
			if ( fComp == 0 )
			{
				//                before                        after
				//
				//                 <p1>                          <p1n>
				//              0 /    \ 1                    0 /    \ 1            
				//               /      \                      /      \           
				//              /        \                    /        \         
				//           <p2>        <p2>              <p2n>       <p2n>          
				//        0 /   \ 1    0 /  \ 1          0 /  \ 1    0 /   \ 1    
				//         /     \      /    \            /    \      /     \   
				//        /       \    /      \          /      \    /       \   
				//       F0       F1  F2      F3        F0      F2  F1       F3  
				//                                 pNew1E   pNew1T  pNew2E   pNew2T
				//
				pNew1E = pUnitE->pE;   // F0
				pNew1T = pUnitT->pE;   // F2

				pNew2E = pUnitE->pT;   // F1
				pNew2T = pUnitT->pT;   // F3
			}
			else
			{
				//                before                        after
				//
				//                 <p1>                          <p1n>
				//              0 .    \ 1                    0 /    \ 1            
				//               .      \                      /      \           
				//              .        \                    /        \         
				//           <p2>        <p2>              <p2n>       <p2n>          
				//        0 /   \ 1    0 /  \ 1          0 .  \ 1    0 .   \ 1    
				//         /     \      /    \            .    \      .     \   
				//        /       \    /      \          .      \    .       \   
				//       F0       F1  F2      F3        F0      F2  F1       F3  
				//                                 pNew1E   pNew1T  pNew2E   pNew2T
				//
				pNew1E = Unit_Not(pUnitER->pE);  // F0
				pNew1T =          pUnitT->pE;    // F2

				pNew2E = Unit_Not(pUnitER->pT);  // F1
				pNew2T =          pUnitT->pT;    // F3
			}
			// subtract ref counters - on the level P2
			pUnitER->n--;
			pUnitT->n--;

			// mark the change in the APL weights
			if ( p->fMinApl )
			{
				pUnitER->Weight -= AplWeightHalf;
				pUnitT->Weight  -= AplWeightHalf;
				AplWeightAfter  -= pUnit->Weight;
			}
		}
		else if ( pUnitER->lev == lev1 )
		{
			if ( fComp == 0 )
			{
				//                before                        after
				//
				//                 <p1>                          <p1n>
				//              0 /    \ 1                    0 /    \ 1            
				//               /      \                      /      \           
				//              /        \                    /        \         
				//           <p2>         \               <p2n>       <p2n>           
				//        0 /   \ 1        \            0 /  \ 1    0 /   \ 1    
				//         /     \          \            /    \      /     \   
				//        /       \          \          /      \    /       \   
				//       F0       F1         F3        F0      F3  F1       F3  
				//                                 pNew1E   pNew1T  pNew2E   pNew2T
				//
				pNew1E = pUnitER->pE;	  // F0
				pNew1T = pUnitT;          // F3

				pNew2E = pUnitER->pT;     // F1
				pNew2T = pUnitT;          // F3
			}
			else
			{
				//                before                        after
				//
				//                 <p1>                          <p1n>
				//              0 .    \ 1                    0 /    \ 1            
				//               .      \                      /      \           
				//              .        \                    /        \         
				//           <p2>         \                <p2n>       <p2n>          
				//        0 /   \ 1        \            0 .  \ 1    0 .   \ 1    
				//         /     \          \            .    \      .     \   
				//        /       \          \          .      \    .       \   
				//       F0       F1         F3        F0      F3  F1       F3  
				//                                 pNew1E   pNew1T  pNew2E   pNew2T
				//
				pNew1E = Unit_Not(pUnitER->pE);  // F0
				pNew1T =          pUnitT;        // F3

				pNew2E = Unit_Not(pUnitER->pT);  // F1
				pNew2T =          pUnitT;        // F3
			}
			// subtract ref counter - on the level P2
			pUnitER->n--;
			// subtract ref counter - on other levels
			pUnitT->n--;  ///

			// mark the change in the APL weights
			if ( p->fMinApl )
			{
				pUnitER->Weight -= AplWeightHalf;
				AplWeightAfter  -= AplWeightHalf;
			}
		}
		else if ( pUnitT->lev == lev1 )
		{
			//                before                        after
			//
			//                 <p1>                          <p1n>
			//              0 /    \ 1                    0 /    \ 1            
			//               /      \                      /      \           
			//              /        \                    /        \         
			//             /         <p2>              <p2n>       <p2n>