cutNode.c File Reference

#include "cutInt.h"

Include dependency graph for cutNode.c:

Go to the source code of this file.

Functions
Cut_Cut_t *	Cut_NodeComputeCuts (Cut_Man_t *p, int Node, int Node0, int Node1, int fCompl0, int fCompl1, int fTriv, int TreeCode)
int	Cut_ManMappingArea_rec (Cut_Man_t *p, int Node)
void	Cut_NodeDoComputeCuts (Cut_Man_t *p, Cut_List_t *pSuper, int Node, int fCompl0, int fCompl1, Cut_Cut_t *pList0, Cut_Cut_t *pList1, int fTriv, int TreeCode)
Cut_Cut_t *	Cut_NodeUnionCuts (Cut_Man_t *p, Vec_Int_t *vNodes)
Cut_Cut_t *	Cut_NodeUnionCutsSeq (Cut_Man_t *p, Vec_Int_t *vNodes, int CutSetNum, int fFirst)
int	Cut_CutListVerify (Cut_Cut_t *pList)

Function Documentation

Cut_CutListVerify()

int Cut_CutListVerify

(

Cut_Cut_t *

pList

)

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

Synopsis [Verifies that the list contains only non-dominated cuts.]

Description []

SideEffects []

SeeAlso []

Definition at line 979 of file cutNode.c.

{ 
    Cut_Cut_t * pCut, * pDom;
    Cut_ListForEachCut( pList, pCut )
    {
        Cut_ListForEachCutStop( pList, pDom, pCut )
        {
            if ( Cut_CutCheckDominance( pDom, pCut ) )
            {
                printf( "******************* These are contained cuts:\n" );
                Cut_CutPrint( pDom, 1 );
                Cut_CutPrint( pDom, 1 );
                return 0;
            }
        }
    }
    return 1;
}

Here is the call graph for this function:

Cut_ManMappingArea_rec()

int Cut_ManMappingArea_rec	(	Cut_Man_t *	p,
		int	Node )

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

Synopsis [Computes area after mapping.]

Description []

SideEffects []

SeeAlso []

Definition at line 544 of file cutNode.c.

{
    Cut_Cut_t * pCut;
    int i, Counter;
    if ( p->vCutsMax == NULL )
        return 0;
    pCut = (Cut_Cut_t *)Vec_PtrEntry( p->vCutsMax, Node );
    if ( pCut == NULL || pCut->nLeaves == 1 )
        return 0;
    Counter = 0;
    for ( i = 0; i < (int)pCut->nLeaves; i++ )
        Counter += Cut_ManMappingArea_rec( p, pCut->pLeaves[i] );
    Vec_PtrWriteEntry( p->vCutsMax, Node, NULL );
    return 1 + Counter;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Cut_NodeComputeCuts()

Cut_Cut_t * Cut_NodeComputeCuts	(	Cut_Man_t *	p,
		int	Node,
		int	Node0,
		int	Node1,
		int	fCompl0,
		int	fCompl1,
		int	fTriv,
		int	TreeCode )

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

Synopsis [Computes the cuts by merging cuts at two nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 369 of file cutNode.c.

{
    Cut_List_t Super, * pSuper = &Super;
    Cut_Cut_t * pList, * pCut;
    abctime clk;
    // start the number of cuts at the node
    p->nNodes++;
    p->nNodeCuts = 0;
    // prepare information for recording
    if ( p->pParams->fRecord )
    {
        Cut_CutNumberList( Cut_NodeReadCutsNew(p, Node0) );
        Cut_CutNumberList( Cut_NodeReadCutsNew(p, Node1) );
    }
    // compute the cuts
clk = Abc_Clock();
    Cut_ListStart( pSuper );
    Cut_NodeDoComputeCuts( p, pSuper, Node, fCompl0, fCompl1, Cut_NodeReadCutsNew(p, Node0), Cut_NodeReadCutsNew(p, Node1), fTriv, TreeCode );
    pList = Cut_ListFinish( pSuper );
p->timeMerge += Abc_Clock() - clk;
    // verify the result of cut computation
//    Cut_CutListVerify( pList );
    // performing the recording
    if ( p->pParams->fRecord )
    {
        Vec_IntWriteEntry( p->vNodeStarts, Node, Vec_IntSize(p->vCutPairs) );
        Cut_ListForEachCut( pList, pCut )
            Vec_IntPush( p->vCutPairs, ((pCut->Num1 << 16) | pCut->Num0) );
        Vec_IntWriteEntry( p->vNodeCuts, Node, Vec_IntSize(p->vCutPairs) - Vec_IntEntry(p->vNodeStarts, Node) );
    }
    if ( p->pParams->fRecordAig )
    {
        extern void Aig_RManRecord( unsigned * pTruth, int nVarsInit );
        Cut_ListForEachCut( pList, pCut )
            if ( Cut_CutReadLeaveNum(pCut) > 4 )
                Aig_RManRecord( Cut_CutReadTruth(pCut), Cut_CutReadLeaveNum(pCut) );
    }
    // check if the node is over the list
    if ( p->nNodeCuts == p->pParams->nKeepMax )
        p->nCutsLimit++;
    // set the list at the node
    Vec_PtrFillExtra( p->vCutsNew, Node + 1, NULL );
    assert( Cut_NodeReadCutsNew(p, Node) == NULL );
//    pList->pNext = NULL;
    Cut_NodeWriteCutsNew( p, Node, pList );
    // filter the cuts
//clk = Abc_Clock();
//    if ( p->pParams->fFilter )
//        Cut_CutFilter( p, pList0 );
//p->timeFilter += Abc_Clock() - clk;
    // perform mapping of this node with these cuts
clk = Abc_Clock();
    if ( p->pParams->fMap && !p->pParams->fSeq )
    {
//        int Delay1, Delay2;
//        Delay1 = Cut_NodeMapping( p, pList, Node, Node0, Node1 );    
//        Delay2 = Cut_NodeMapping2( p, pList, Node, Node0, Node1 );   
//        assert( Delay1 >= Delay2 );
        Cut_NodeMapping( p, pList, Node, Node0, Node1 );
    }
p->timeMap += Abc_Clock() - clk;
    return pList;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Cut_NodeDoComputeCuts()

void Cut_NodeDoComputeCuts	(	Cut_Man_t *	p,
		Cut_List_t *	pSuper,
		int	Node,
		int	fCompl0,
		int	fCompl1,
		Cut_Cut_t *	pList0,
		Cut_Cut_t *	pList1,
		int	fTriv,
		int	TreeCode )

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

Synopsis [Computes the cuts by merging cuts at two nodes.]

Description []

SideEffects []

SeeAlso []

Definition at line 572 of file cutNode.c.

{
    Cut_Cut_t * pStop0, * pStop1, * pTemp0, * pTemp1;
    Cut_Cut_t * pStore0 = NULL, * pStore1 = NULL; // Suppress "might be used uninitialized"
    int i, nCutsOld, Limit;
    // start with the elementary cut
    if ( fTriv ) 
    {
//        printf( "Creating trivial cut %d.\n", Node );
        pTemp0 = Cut_CutCreateTriv( p, Node );
        Cut_ListAdd( pSuper, pTemp0 );
        p->nNodeCuts++;
    }
    // get the cut lists of children
    if ( pList0 == NULL || pList1 == NULL || (p->pParams->fLocal && TreeCode)  )
        return;
 
    // remember the old number of cuts
    nCutsOld = p->nCutsCur;
    Limit = p->pParams->nVarsMax;
    // get the simultation bit of the node
    p->fSimul = (fCompl0 ^ pList0->fSimul) & (fCompl1 ^ pList1->fSimul);
    // set temporary variables
    p->fCompl0 = fCompl0;
    p->fCompl1 = fCompl1;
    // if tree cuts are computed, make sure only the unit cuts propagate over the DAG nodes
    if ( TreeCode & 1 )
    {
        assert( pList0->nLeaves == 1 );
        pStore0 = pList0->pNext;
        pList0->pNext = NULL;
    }
    if ( TreeCode & 2 )
    {
        assert( pList1->nLeaves == 1 );
        pStore1 = pList1->pNext;
        pList1->pNext = NULL;
    }
    // find the point in the list where the max-var cuts begin
    Cut_ListForEachCut( pList0, pStop0 )
        if ( pStop0->nLeaves == (unsigned)Limit )
            break;
    Cut_ListForEachCut( pList1, pStop1 )
        if ( pStop1->nLeaves == (unsigned)Limit )
            break;
 
    // small by small
    Cut_ListForEachCutStop( pList0, pTemp0, pStop0 )
    Cut_ListForEachCutStop( pList1, pTemp1, pStop1 )
    {
        if ( Cut_CutProcessTwo( p, pTemp0, pTemp1, pSuper ) )
            goto Quits;
    }
    // small by large
    Cut_ListForEachCutStop( pList0, pTemp0, pStop0 )
    Cut_ListForEachCut( pStop1, pTemp1 )
    {
        if ( (pTemp0->uSign & pTemp1->uSign) != pTemp0->uSign )
            continue;
        if ( Cut_CutProcessTwo( p, pTemp0, pTemp1, pSuper ) )
            goto Quits;
    }
    // small by large
    Cut_ListForEachCutStop( pList1, pTemp1, pStop1 )
    Cut_ListForEachCut( pStop0, pTemp0 )
    {
        if ( (pTemp0->uSign & pTemp1->uSign) != pTemp1->uSign )
            continue;
        if ( Cut_CutProcessTwo( p, pTemp0, pTemp1, pSuper ) )
            goto Quits;
    }
    // large by large
    Cut_ListForEachCut( pStop0, pTemp0 )
    Cut_ListForEachCut( pStop1, pTemp1 )
    {
        assert( pTemp0->nLeaves == (unsigned)Limit && pTemp1->nLeaves == (unsigned)Limit );
        if ( pTemp0->uSign != pTemp1->uSign )
            continue;
        for ( i = 0; i < Limit; i++ )
            if ( pTemp0->pLeaves[i] != pTemp1->pLeaves[i] )
                break;
        if ( i < Limit )
            continue;
        if ( Cut_CutProcessTwo( p, pTemp0, pTemp1, pSuper ) )
            goto Quits;
    } 
    if ( p->nNodeCuts == 0 )
        p->nNodesNoCuts++;
Quits:
    if ( TreeCode & 1 )
        pList0->pNext = pStore0;
    if ( TreeCode & 2 )
        pList1->pNext = pStore1;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Cut_NodeUnionCuts()

Cut_Cut_t * Cut_NodeUnionCuts	(	Cut_Man_t *	p,
		Vec_Int_t *	vNodes )

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

Synopsis [Computes the cuts by unioning cuts at a choice node.]

Description []

SideEffects []

SeeAlso []

Definition at line 678 of file cutNode.c.

{
    Cut_List_t Super, * pSuper = &Super;
    Cut_Cut_t * pList, * pListStart, * pCut, * pCut2;
    Cut_Cut_t * pTop = NULL; // Suppress "might be used uninitialized"
    int i, k, Node, Root, Limit = p->pParams->nVarsMax;
    abctime clk = Abc_Clock();
 
    // start the new list
    Cut_ListStart( pSuper );
 
    // remember the root node to save the resulting cuts
    Root = Vec_IntEntry( vNodes, 0 );
    p->nNodeCuts = 1;
 
    // collect small cuts first
    Vec_PtrClear( p->vTemp );
    Vec_IntForEachEntry( vNodes, Node, i )
    {
        // get the cuts of this node
        pList = Cut_NodeReadCutsNew( p, Node );
        Cut_NodeWriteCutsNew( p, Node, NULL );
        assert( pList );
        // remember the starting point
        pListStart = pList->pNext;
        pList->pNext = NULL;
        // save or recycle the elementary cut
        if ( i == 0 )
            Cut_ListAdd( pSuper, pList ), pTop = pList;
        else
            Cut_CutRecycle( p, pList );
        // save all the cuts that are smaller than the limit
        Cut_ListForEachCutSafe( pListStart, pCut, pCut2 )
        {
            if ( pCut->nLeaves == (unsigned)Limit )
            {
                Vec_PtrPush( p->vTemp, pCut );
                break;
            }
            // check containment
            if ( p->pParams->fFilter && Cut_CutFilterOne( p, pSuper, pCut ) )
                continue;
            // set the complemented bit by comparing the first cut with the current cut
            pCut->fCompl = pTop->fSimul ^ pCut->fSimul;
            pListStart = pCut->pNext;
            pCut->pNext = NULL;
            // add to the list
            Cut_ListAdd( pSuper, pCut );
            if ( ++p->nNodeCuts == p->pParams->nKeepMax )
            {
                // recycle the rest of the cuts of this node
                Cut_ListForEachCutSafe( pListStart, pCut, pCut2 )
                    Cut_CutRecycle( p, pCut );
                // recycle all cuts of other nodes
                Vec_IntForEachEntryStart( vNodes, Node, k, i+1 )
                    Cut_NodeFreeCuts( p, Node );
                // recycle the saved cuts of other nodes
                Vec_PtrForEachEntry( Cut_Cut_t *, p->vTemp, pList, k )
                    Cut_ListForEachCutSafe( pList, pCut, pCut2 )
                        Cut_CutRecycle( p, pCut );
                goto finish;
            }
        }
    } 
    // collect larger cuts next
    Vec_PtrForEachEntry( Cut_Cut_t *, p->vTemp, pList, i )
    {
        Cut_ListForEachCutSafe( pList, pCut, pCut2 )
        {
            // check containment
            if ( p->pParams->fFilter && Cut_CutFilterOne( p, pSuper, pCut ) )
                continue;
            // set the complemented bit
            pCut->fCompl = pTop->fSimul ^ pCut->fSimul;
            pListStart = pCut->pNext;
            pCut->pNext = NULL;
            // add to the list
            Cut_ListAdd( pSuper, pCut );
            if ( ++p->nNodeCuts == p->pParams->nKeepMax )
            {
                // recycle the rest of the cuts
                Cut_ListForEachCutSafe( pListStart, pCut, pCut2 )
                    Cut_CutRecycle( p, pCut );
                // recycle the saved cuts of other nodes
                Vec_PtrForEachEntryStart( Cut_Cut_t *, p->vTemp, pList, k, i+1 )
                    Cut_ListForEachCutSafe( pList, pCut, pCut2 )
                        Cut_CutRecycle( p, pCut );
                goto finish;
            }
        }
    }
finish :
    // set the cuts at the node
    assert( Cut_NodeReadCutsNew(p, Root) == NULL );
    pList = Cut_ListFinish( pSuper );
    Cut_NodeWriteCutsNew( p, Root, pList );
p->timeUnion += Abc_Clock() - clk;
    // filter the cuts
//clk = Abc_Clock();
//    if ( p->pParams->fFilter )
//        Cut_CutFilter( p, pList );
//p->timeFilter += Abc_Clock() - clk;
    p->nNodes -= vNodes->nSize - 1;
    return pList;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Cut_NodeUnionCutsSeq()

Cut_Cut_t * Cut_NodeUnionCutsSeq	(	Cut_Man_t *	p,
		Vec_Int_t *	vNodes,
		int	CutSetNum,
		int	fFirst )

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

Synopsis [Computes the cuts by unioning cuts at a choice node.]

Description []

SideEffects []

SeeAlso []

Definition at line 795 of file cutNode.c.

{
    Cut_List_t Super, * pSuper = &Super;
    Cut_Cut_t * pList, * pListStart, * pCut, * pCut2, * pTop;
    int i, k, Node, Root, Limit = p->pParams->nVarsMax;
    abctime clk = Abc_Clock();
 
    // start the new list
    Cut_ListStart( pSuper );
 
    // remember the root node to save the resulting cuts
    Root = Vec_IntEntry( vNodes, 0 );
    p->nNodeCuts = 1;
 
    // store the original lists for comparison
    p->pCompareOld = Cut_NodeReadCutsOld( p, Root );
    p->pCompareNew = (CutSetNum >= 0)? Cut_NodeReadCutsNew( p, Root ) : NULL;
 
    // get the topmost cut
    pTop = NULL;
    if ( (pTop = Cut_NodeReadCutsOld( p, Root )) == NULL )
        pTop = Cut_NodeReadCutsNew( p, Root );
    assert( pTop != NULL );
 
    // collect small cuts first
    Vec_PtrClear( p->vTemp );
    Vec_IntForEachEntry( vNodes, Node, i )
    {
        // get the cuts of this node
        if ( i == 0 && CutSetNum >= 0 )
        {
            pList = Cut_NodeReadCutsTemp( p, CutSetNum );
            Cut_NodeWriteCutsTemp( p, CutSetNum, NULL );
        }
        else
        {
            pList = Cut_NodeReadCutsNew( p, Node );
            Cut_NodeWriteCutsNew( p, Node, NULL );
        }
        if ( pList == NULL )
            continue;
 
        // process the cuts
        if ( fFirst )
        {
            // remember the starting point
            pListStart = pList->pNext;
            pList->pNext = NULL;
            // save or recycle the elementary cut
            if ( i == 0 )
                Cut_ListAdd( pSuper, pList );
            else
                Cut_CutRecycle( p, pList );
        }
        else
            pListStart = pList;
 
        // save all the cuts that are smaller than the limit
        Cut_ListForEachCutSafe( pListStart, pCut, pCut2 )
        {
            if ( pCut->nLeaves == (unsigned)Limit )
            {
                Vec_PtrPush( p->vTemp, pCut );
                break;
            }
            // check containment
//            if ( p->pParams->fFilter && Cut_CutFilterOne( p, pSuper, pCut ) )
//                continue;
            if ( p->pParams->fFilter )
            {
                if ( Cut_CutFilterOne(p, pSuper, pCut) )
                    continue;
                if ( p->pParams->fSeq )
                {
                    if ( p->pCompareOld && Cut_CutFilterOld(p, p->pCompareOld, pCut) )
                        continue;
                    if ( p->pCompareNew && Cut_CutFilterOld(p, p->pCompareNew, pCut) )
                        continue;
                }
            }
 
            // set the complemented bit by comparing the first cut with the current cut
            pCut->fCompl = pTop->fSimul ^ pCut->fSimul;
            pListStart = pCut->pNext;
            pCut->pNext = NULL;
            // add to the list
            Cut_ListAdd( pSuper, pCut );
            if ( ++p->nNodeCuts == p->pParams->nKeepMax )
            {
                // recycle the rest of the cuts of this node
                Cut_ListForEachCutSafe( pListStart, pCut, pCut2 )
                    Cut_CutRecycle( p, pCut );
                // recycle all cuts of other nodes
                Vec_IntForEachEntryStart( vNodes, Node, k, i+1 )
                    Cut_NodeFreeCuts( p, Node );
                // recycle the saved cuts of other nodes
                Vec_PtrForEachEntry( Cut_Cut_t *, p->vTemp, pList, k )
                    Cut_ListForEachCutSafe( pList, pCut, pCut2 )
                        Cut_CutRecycle( p, pCut );
                goto finish;
            }
        }
    } 
    // collect larger cuts next
    Vec_PtrForEachEntry( Cut_Cut_t *, p->vTemp, pList, i )
    {
        Cut_ListForEachCutSafe( pList, pCut, pCut2 )
        {
            // check containment
//            if ( p->pParams->fFilter && Cut_CutFilterOne( p, pSuper, pCut ) )
//                continue;
            if ( p->pParams->fFilter )
            {
                if ( Cut_CutFilterOne(p, pSuper, pCut) )
                    continue;
                if ( p->pParams->fSeq )
                {
                    if ( p->pCompareOld && Cut_CutFilterOld(p, p->pCompareOld, pCut) )
                        continue;
                    if ( p->pCompareNew && Cut_CutFilterOld(p, p->pCompareNew, pCut) )
                        continue;
                }
            }
 
            // set the complemented bit
            pCut->fCompl = pTop->fSimul ^ pCut->fSimul;
            pListStart   = pCut->pNext;
            pCut->pNext  = NULL;
            // add to the list
            Cut_ListAdd( pSuper, pCut );
            if ( ++p->nNodeCuts == p->pParams->nKeepMax )
            {
                // recycle the rest of the cuts
                Cut_ListForEachCutSafe( pListStart, pCut, pCut2 )
                    Cut_CutRecycle( p, pCut );
                // recycle the saved cuts of other nodes
                Vec_PtrForEachEntryStart( Cut_Cut_t *, p->vTemp, pList, k, i+1 )
                    Cut_ListForEachCutSafe( pList, pCut, pCut2 )
                        Cut_CutRecycle( p, pCut );
                goto finish;
            }
        }
    }
finish :
    // set the cuts at the node
    pList = Cut_ListFinish( pSuper );
 
    // set the lists at the node
//    assert( Cut_NodeReadCutsNew(p, Root) == NULL );
//    Cut_NodeWriteCutsNew( p, Root, pList );
    if ( CutSetNum >= 0 )
    {
        assert( Cut_NodeReadCutsTemp(p, CutSetNum) == NULL );
        Cut_NodeWriteCutsTemp( p, CutSetNum, pList );
    }
    else
    {
        assert( Cut_NodeReadCutsNew(p, Root) == NULL );
        Cut_NodeWriteCutsNew( p, Root, pList );
    }
 
p->timeUnion += Abc_Clock() - clk;
    // filter the cuts
//clk = Abc_Clock();
//    if ( p->pParams->fFilter )
//        Cut_CutFilter( p, pList );
//p->timeFilter += Abc_Clock() - clk;
//    if ( fFirst )
//        p->nNodes -= vNodes->nSize - 1;
    return pList;
}

Here is the call graph for this function: