summaryrefslogtreecommitdiffstats
path: root/src/opt/sbd/sbdLut.c
diff options
context:
space:
mode:
authorBruno Schmitt <bruno@oschmitt.com>2017-01-25 13:40:31 +0900
committerBruno Schmitt <bruno@oschmitt.com>2017-01-25 13:40:31 +0900
commit876eb5a52e67911ccc19d5f732aa9e1c9279fd26 (patch)
tree4a78999c29676235f613b4e1f8e1d1d0983107ba /src/opt/sbd/sbdLut.c
parent123b425052636beceaa52e47ea695d35b75fb40a (diff)
parent51f4dab475af1ffd22d23b5aeb8d7cf243739f75 (diff)
downloadabc-876eb5a52e67911ccc19d5f732aa9e1c9279fd26.tar.gz
abc-876eb5a52e67911ccc19d5f732aa9e1c9279fd26.tar.bz2
abc-876eb5a52e67911ccc19d5f732aa9e1c9279fd26.zip
Merged alanmi/abc into default
Diffstat (limited to 'src/opt/sbd/sbdLut.c')
-rw-r--r--src/opt/sbd/sbdLut.c311
1 files changed, 311 insertions, 0 deletions
diff --git a/src/opt/sbd/sbdLut.c b/src/opt/sbd/sbdLut.c
new file mode 100644
index 00000000..ffcb71f8
--- /dev/null
+++ b/src/opt/sbd/sbdLut.c
@@ -0,0 +1,311 @@
+/**CFile****************************************************************
+
+ FileName [sbdLut.c]
+
+ SystemName [ABC: Logic synthesis and verification system.]
+
+ PackageName [SAT-based optimization using internal don't-cares.]
+
+ Synopsis [CNF computation.]
+
+ Author [Alan Mishchenko]
+
+ Affiliation [UC Berkeley]
+
+ Date [Ver. 1.0. Started - June 20, 2005.]
+
+ Revision [$Id: sbdLut.c,v 1.00 2005/06/20 00:00:00 alanmi Exp $]
+
+***********************************************************************/
+
+#include "sbdInt.h"
+#include "misc/util/utilTruth.h"
+
+ABC_NAMESPACE_IMPL_START
+
+////////////////////////////////////////////////////////////////////////
+/// DECLARATIONS ///
+////////////////////////////////////////////////////////////////////////
+
+////////////////////////////////////////////////////////////////////////
+/// FUNCTION DEFINITIONS ///
+////////////////////////////////////////////////////////////////////////
+
+/**Function*************************************************************
+
+ Synopsis []
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+// count the number of parameter variables in the structure
+int Sbd_ProblemCountParams( int nStrs, Sbd_Str_t * pStr0 )
+{
+ Sbd_Str_t * pStr; int nPars = 0;
+ for ( pStr = pStr0; pStr < pStr0 + nStrs; pStr++ )
+ nPars += pStr->fLut ? 1 << pStr->nVarIns : pStr->nVarIns;
+ return nPars;
+}
+// add clauses for the structure
+int Sbd_ProblemAddClauses( sat_solver * pSat, int nVars, int nStrs, int * pVars, Sbd_Str_t * pStr0 )
+{
+ // variable order: inputs, structure outputs, parameters
+ Sbd_Str_t * pStr;
+ int VarOut = nVars;
+ int VarPar = nVars + nStrs;
+ int m, k, n, status, pLits[SBD_SIZE_MAX+2];
+//printf( "Start par = %d. ", VarPar );
+ for ( pStr = pStr0; pStr < pStr0 + nStrs; pStr++, VarOut++ )
+ {
+ if ( pStr->fLut )
+ {
+ int nMints = 1 << pStr->nVarIns;
+ assert( pStr->nVarIns <= 6 );
+ for ( m = 0; m < nMints; m++, VarPar++ )
+ {
+ for ( k = 0; k < pStr->nVarIns; k++ )
+ pLits[k] = Abc_Var2Lit( pVars[pStr->VarIns[k]], (m >> k) & 1 );
+ for ( n = 0; n < 2; n++ )
+ {
+ pLits[pStr->nVarIns] = Abc_Var2Lit( pVars[VarPar], n );
+ pLits[pStr->nVarIns+1] = Abc_Var2Lit( pVars[VarOut], !n );
+ status = sat_solver_addclause( pSat, pLits, pLits + pStr->nVarIns + 2 );
+ if ( !status )
+ return 0;
+ }
+ }
+ }
+ else
+ {
+ assert( pStr->nVarIns <= SBD_DIV_MAX );
+ for ( k = 0; k < pStr->nVarIns; k++, VarPar++ )
+ {
+ for ( n = 0; n < 2; n++ )
+ {
+ pLits[0] = Abc_Var2Lit( pVars[VarPar], 1 );
+ pLits[1] = Abc_Var2Lit( pVars[VarOut], n );
+ pLits[2] = Abc_Var2Lit( pVars[pStr->VarIns[k]], !n );
+ status = sat_solver_addclause( pSat, pLits, pLits + 3 );
+ if ( !status )
+ return 0;
+ }
+ }
+ }
+ }
+ return 1;
+}
+void Sbd_ProblemAddClausesInit( sat_solver * pSat, int nVars, int nStrs, int * pVars, Sbd_Str_t * pStr0 )
+{
+ Sbd_Str_t * pStr;
+ int VarPar = nVars + nStrs;
+ int m, m2, status, pLits[SBD_DIV_MAX];
+ // make sure selector parameters are mutually exclusive
+ for ( pStr = pStr0; pStr < pStr0 + nStrs; VarPar += pStr->fLut ? 1 << pStr->nVarIns : pStr->nVarIns, pStr++ )
+ {
+ if ( pStr->fLut )
+ continue;
+ // one variable should be selected
+ assert( pStr->nVarIns <= SBD_DIV_MAX );
+ for ( m = 0; m < pStr->nVarIns; m++ )
+ pLits[m] = Abc_Var2Lit( pVars[VarPar + m], 0 );
+ status = sat_solver_addclause( pSat, pLits, pLits + pStr->nVarIns );
+ assert( status );
+ // two variables cannot be selected
+ for ( m = 0; m < pStr->nVarIns; m++ )
+ for ( m2 = m+1; m2 < pStr->nVarIns; m2++ )
+ {
+ pLits[0] = Abc_Var2Lit( pVars[VarPar + m], 1 );
+ pLits[1] = Abc_Var2Lit( pVars[VarPar + m2], 1 );
+ status = sat_solver_addclause( pSat, pLits, pLits + 2 );
+ assert( status );
+ }
+ }
+}
+void Sbd_ProblemPrintSolution( int nStrs, Sbd_Str_t * pStr0, Vec_Int_t * vLits )
+{
+ Sbd_Str_t * pStr;
+ int m, nIters, iLit = 0;
+ printf( "Solution found:\n" );
+ for ( pStr = pStr0; pStr < pStr0 + nStrs; pStr++ )
+ {
+ nIters = pStr->fLut ? 1 << pStr->nVarIns : pStr->nVarIns;
+ printf( "%s%d : ", pStr->fLut ? "LUT":"SEL", (int)(pStr-pStr0) );
+ for ( m = 0; m < nIters; m++, iLit++ )
+ printf( "%d", !Abc_LitIsCompl(Vec_IntEntry(vLits, iLit)) );
+ printf( " {" );
+ for ( m = 0; m < pStr->nVarIns; m++ )
+ printf( " %d", pStr->VarIns[m] );
+ printf( " }\n" );
+ }
+ assert( iLit == Vec_IntSize(vLits) );
+}
+void Sbd_ProblemCollectSolution( int nStrs, Sbd_Str_t * pStr0, Vec_Int_t * vLits )
+{
+ Sbd_Str_t * pStr;
+ int m, nIters, iLit = 0;
+ for ( pStr = pStr0; pStr < pStr0 + nStrs; pStr++ )
+ {
+ pStr->Res = 0;
+ if ( pStr->fLut )
+ {
+ nIters = 1 << pStr->nVarIns;
+ for ( m = 0; m < nIters; m++, iLit++ )
+ if ( !Abc_LitIsCompl(Vec_IntEntry(vLits, iLit)) )
+ Abc_TtSetBit( &pStr->Res, m );
+ pStr->Res = Abc_Tt6Stretch( pStr->Res, pStr->nVarIns );
+ }
+ else
+ {
+ nIters = 0;
+ for ( m = 0; m < pStr->nVarIns; m++, iLit++ )
+ if ( !Abc_LitIsCompl(Vec_IntEntry(vLits, iLit)) )
+ {
+ pStr->Res = pStr->VarIns[m];
+ nIters++;
+ }
+ assert( nIters == 1 );
+ }
+ }
+ assert( iLit == Vec_IntSize(vLits) );
+}
+
+/**Function*************************************************************
+
+ Synopsis [Solves QBF problem for the given window.]
+
+ Description []
+
+ SideEffects []
+
+ SeeAlso []
+
+***********************************************************************/
+int Sbd_ProblemSolve( Gia_Man_t * p, Vec_Int_t * vMirrors,
+ int Pivot, Vec_Int_t * vWinObjs, Vec_Int_t * vObj2Var,
+ Vec_Int_t * vTfo, Vec_Int_t * vRoots,
+ Vec_Int_t * vDivSet, int nStrs, Sbd_Str_t * pStr0 ) // divisors, structures
+{
+ extern sat_solver * Sbd_ManSatSolver( sat_solver * pSat, Gia_Man_t * p, Vec_Int_t * vMirrors, int Pivot, Vec_Int_t * vWinObjs, Vec_Int_t * vObj2Var, Vec_Int_t * vTfo, Vec_Int_t * vRoots, int fQbf );
+
+ int fVerbose = 0;
+ abctime clk = Abc_Clock();
+ Vec_Int_t * vLits = Vec_IntAlloc( 100 );
+ sat_solver * pSatCec = Sbd_ManSatSolver( NULL, p, vMirrors, Pivot, vWinObjs, vObj2Var, vTfo, vRoots, 1 );
+ sat_solver * pSatQbf = sat_solver_new();
+
+ int nVars = Vec_IntSize( vDivSet );
+ int nPars = Sbd_ProblemCountParams( nStrs, pStr0 );
+
+ int VarCecOut = Vec_IntSize(vWinObjs) + Vec_IntSize(vTfo) + Vec_IntSize(vRoots);
+ int VarCecPar = VarCecOut + nStrs;
+
+ int VarQbfPar = 0;
+ int VarQbfFree = nPars;
+
+ int pVarsCec[256];
+ int pVarsQbf[256];
+ int i, iVar, iLit, nIters;
+ int RetValue = 0;
+
+ assert( Vec_IntSize(vDivSet) <= SBD_DIV_MAX );
+ assert( nVars + nStrs + nPars <= 256 );
+
+ // collect CEC variables
+ Vec_IntForEachEntry( vDivSet, iVar, i )
+ pVarsCec[i] = iVar;
+ for ( i = 0; i < nStrs; i++ )
+ pVarsCec[nVars + i] = VarCecOut + i;
+ for ( i = 0; i < nPars; i++ )
+ pVarsCec[nVars + nStrs + i] = VarCecPar + i;
+
+ // collect QBF variables
+ for ( i = 0; i < nVars + nStrs; i++ )
+ pVarsQbf[i] = -1;
+ for ( i = 0; i < nPars; i++ )
+ pVarsQbf[nVars + nStrs + i] = VarQbfPar + i;
+
+ // add clauses to the CEC problem
+ Sbd_ProblemAddClauses( pSatCec, nVars, nStrs, pVarsCec, pStr0 );
+
+ // create QBF solver
+ sat_solver_setnvars( pSatQbf, 1000 );
+ Sbd_ProblemAddClausesInit( pSatQbf, nVars, nStrs, pVarsQbf, pStr0 );
+
+ // assume all parameter variables are 0
+ Vec_IntClear( vLits );
+ for ( i = 0; i < nPars; i++ )
+ Vec_IntPush( vLits, Abc_Var2Lit(VarCecPar + i, 1) );
+ for ( nIters = 0; nIters < (1 << nVars); nIters++ )
+ {
+ // check if these parameters solve the problem
+ int status = sat_solver_solve( pSatCec, Vec_IntArray(vLits), Vec_IntLimit(vLits), 0, 0, 0, 0 );
+ if ( status == l_False ) // solution found
+ break;
+ assert( status == l_True );
+
+ if ( fVerbose )
+ {
+ printf( "Iter %3d : ", nIters );
+ for ( i = 0; i < nPars; i++ )
+ printf( "%d", !Abc_LitIsCompl(Vec_IntEntry(vLits, i)) );
+ printf( " " );
+ }
+
+ Vec_IntClear( vLits );
+ // create new QBF variables
+ for ( i = 0; i < nVars + nStrs; i++ )
+ pVarsQbf[i] = VarQbfFree++;
+ // set their values
+ Vec_IntForEachEntry( vDivSet, iVar, i )
+ {
+ iLit = Abc_Var2Lit( pVarsQbf[i], !sat_solver_var_value(pSatCec, iVar) );
+ status = sat_solver_addclause( pSatQbf, &iLit, &iLit + 1 );
+ assert( status );
+ if ( fVerbose )
+ printf( "%d", sat_solver_var_value(pSatCec, iVar) );
+ }
+ iLit = Abc_Var2Lit( pVarsQbf[nVars], sat_solver_var_value(pSatCec, VarCecOut) );
+ status = sat_solver_addclause( pSatQbf, &iLit, &iLit + 1 );
+ assert( status );
+ if ( fVerbose )
+ printf( " %d\n", !sat_solver_var_value(pSatCec, VarCecOut) );
+ // add clauses to the QBF problem
+ if ( !Sbd_ProblemAddClauses( pSatQbf, nVars, nStrs, pVarsQbf, pStr0 ) )
+ break; // solution does not exist
+ // check if solution still exists
+ status = sat_solver_solve( pSatQbf, NULL, NULL, 0, 0, 0, 0 );
+ if ( status == l_False ) // solution does not exist
+ break;
+ assert( status == l_True );
+ // find the new values of parameters
+ assert( Vec_IntSize(vLits) == 0 );
+ for ( i = 0; i < nPars; i++ )
+ Vec_IntPush( vLits, Abc_Var2Lit(VarCecPar + i, !sat_solver_var_value(pSatQbf, VarQbfPar + i)) );
+ }
+ if ( Vec_IntSize(vLits) > 0 )
+ {
+ //Sbd_ProblemPrintSolution( nStrs, pStr0, vLits );
+ Sbd_ProblemCollectSolution( nStrs, pStr0, vLits );
+ RetValue = 1;
+ }
+ sat_solver_delete( pSatCec );
+ sat_solver_delete( pSatQbf );
+ Vec_IntFree( vLits );
+
+ if ( fVerbose )
+ Abc_PrintTime( 1, "Time", Abc_Clock() - clk );
+ return RetValue;
+}
+
+
+////////////////////////////////////////////////////////////////////////
+/// END OF FILE ///
+////////////////////////////////////////////////////////////////////////
+
+
+ABC_NAMESPACE_IMPL_END
+