Ttopt::TruthTable Class Reference

Inheritance diagram for Ttopt::TruthTable:

Public Types
typedef std::bitset< 64 >	bsw

Public Member Functions
	TruthTable (int nInputs, int nOutputs)
virtual void	Save (unsigned i)
virtual void	Load (unsigned i)
virtual void	SaveIndices (unsigned i)
virtual void	LoadIndices (unsigned i)
word	GetValue (int index_lev, int lev)
int	IsEq (int index1, int index2, int lev, bool fCompl=false)
bool	Imply (int index1, int index2, int lev)
int	BDDNodeCountLevel (int lev)
int	BDDNodeCount ()
int	BDDFind (int index, int lev)
virtual int	BDDBuildOne (int index, int lev)
virtual void	BDDBuildStartup ()
virtual void	BDDBuildLevel (int lev)
virtual int	BDDBuild ()
virtual int	BDDRebuild (int lev)
virtual void	Swap (int lev)
void	SwapIndex (int &index, int d)
virtual int	BDDSwap (int lev)
int	SiftReo ()
void	Reo (std::vector< int > vLevelsNew)
int	RandomSiftReo (int nRound)
int	BDDGenerateAigRec (Gia_Man_t *pNew, std::vector< int > const &vInputs, std::vector< std::vector< int > > &vvNodes, int index, int lev)
virtual void	BDDGenerateAig (Gia_Man_t *pNew, Vec_Int_t *vSupp)

Public Attributes
int	nInputs
int	nSize
int	nTotalSize
int	nOutputs
std::vector< word >	t
std::vector< std::vector< int > >	vvIndices
std::vector< std::vector< int > >	vvRedundantIndices
std::vector< int >	vLevels
std::vector< std::vector< word > >	savedt
std::vector< std::vector< std::vector< int > > >	vvIndicesSaved
std::vector< std::vector< std::vector< int > > >	vvRedundantIndicesSaved
std::vector< std::vector< int > >	vLevelsSaved

Static Public Attributes
static const int	ww = 64
static const int	lww = 6
static const word	ones []
static const word	swapmask []

Detailed Description

Definition at line 39 of file giaTtopt.cpp.

Member Typedef Documentation

bsw

typedef std::bitset<64> Ttopt::TruthTable::bsw

Definition at line 43 of file giaTtopt.cpp.

Constructor & Destructor Documentation

TruthTable()

Ttopt::TruthTable::TruthTable ( int nInputs, int nOutputs )

inline

Definition at line 63 of file giaTtopt.cpp.

                                       : nInputs(nInputs), nOutputs(nOutputs) {
    srand(0xABC);
    if(nInputs >= lww) {
      nSize = 1 << (nInputs - lww);
      nTotalSize = nSize * nOutputs;
      t.resize(nTotalSize);
    } else {
      nSize = 0;
      nTotalSize = ((1 << nInputs) * nOutputs + ww - 1) / ww;
      t.resize(nTotalSize);
    }
    vLevels.resize(nInputs);
    for(int i = 0; i < nInputs; i++) {
      vLevels[i] = i;
    }
  }

Here is the caller graph for this function:

Member Function Documentation

BDDBuild()

virtual int Ttopt::TruthTable::BDDBuild ( )

inlinevirtual

Reimplemented in Ttopt::TruthTableLevelTSM, and Ttopt::TruthTableReo.

Definition at line 243 of file giaTtopt.cpp.

                         {
    BDDBuildStartup();
    for(int i = 1; i < nInputs; i++) {
      BDDBuildLevel(i);
    }
    return BDDNodeCount();
  }

Here is the call graph for this function:

Here is the caller graph for this function:

BDDBuildLevel()

virtual void Ttopt::TruthTable::BDDBuildLevel ( int lev )

inlinevirtual

Reimplemented in Ttopt::TruthTableReo.

Definition at line 232 of file giaTtopt.cpp.

                                      {
    for(unsigned i = 0; i < vvIndices[lev-1].size(); i++) {
      int index = vvIndices[lev-1][i];
      int cof0 = BDDBuildOne(index << 1, lev);
      int cof1 = BDDBuildOne((index << 1) ^ 1, lev);
      if(cof0 == cof1) {
        vvRedundantIndices[lev-1].push_back(index);
      }
    }
  }

Here is the call graph for this function:

Here is the caller graph for this function:

BDDBuildOne()

virtual int Ttopt::TruthTable::BDDBuildOne ( int index, int lev )

inlinevirtual

Reimplemented in Ttopt::TruthTableCare, and Ttopt::TruthTableLevelTSM.

Definition at line 213 of file giaTtopt.cpp.

                                              {
    int r = BDDFind(index, lev);
    if(r >= -2) {
      return r;
    }
    vvIndices[lev].push_back(index);
    return (vvIndices[lev].size() - 1) << 1;
  }

Here is the call graph for this function:

Here is the caller graph for this function:

BDDBuildStartup()

virtual void Ttopt::TruthTable::BDDBuildStartup ( )

inlinevirtual

Reimplemented in Ttopt::TruthTableCare, and Ttopt::TruthTableReo.

Definition at line 222 of file giaTtopt.cpp.

                                 {
    vvIndices.clear();
    vvIndices.resize(nInputs);
    vvRedundantIndices.clear();
    vvRedundantIndices.resize(nInputs);
    for(int i = 0; i < nOutputs; i++) {
      BDDBuildOne(i, 0);
    }
  }

Here is the call graph for this function:

Here is the caller graph for this function:

BDDFind()

int Ttopt::TruthTable::BDDFind ( int index, int lev )

inline

Definition at line 165 of file giaTtopt.cpp.

                                  {
    int logwidth = nInputs - lev;
    if(logwidth > lww) {
      int nScopeSize = 1 << (logwidth - lww);
      bool fZero = true;
      bool fOne = true;
      for(int i = 0; i < nScopeSize && (fZero || fOne); i++) {
        word value = t[nScopeSize * index + i];
        fZero &= !value;
        fOne &= !(~value);
      }
      if(fZero || fOne) {
        return -2 ^ (int)fOne;
      }
      for(unsigned j = 0; j < vvIndices[lev].size(); j++) {
        int index2 = vvIndices[lev][j];
        bool fEq = true;
        bool fCompl = true;
        for(int i = 0; i < nScopeSize && (fEq || fCompl); i++) {
          fEq &= (t[nScopeSize * index + i] == t[nScopeSize * index2 + i]);
          fCompl &= (t[nScopeSize * index + i] == ~t[nScopeSize * index2 + i]);
        }
        if(fEq || fCompl) {
          return (j << 1) ^ (int)fCompl;
        }
      }
    } else {
      word value = GetValue(index, lev);
      if(!value) {
        return -2;
      }
      if(!(value ^ ones[logwidth])) {
        return -1;
      }
      for(unsigned j = 0; j < vvIndices[lev].size(); j++) {
        int index2 = vvIndices[lev][j];
        word value2 = value ^ GetValue(index2, lev);
        if(!(value2)) {
          return j << 1;
        }
        if(!(value2 ^ ones[logwidth])) {
          return (j << 1) ^ 1;
        }
      }
    }
    return -3;
  }

Here is the call graph for this function:

Here is the caller graph for this function:

BDDGenerateAig()

virtual void Ttopt::TruthTable::BDDGenerateAig ( Gia_Man_t * pNew, Vec_Int_t * vSupp )

inlinevirtual

Reimplemented in Ttopt::TruthTableReo.

Definition at line 446 of file giaTtopt.cpp.

                                                                 {
    vvIndices.clear();
    vvIndices.resize(nInputs);
    std::vector<std::vector<int> > vvNodes(nInputs);
    std::vector<int> vInputs(nInputs);
    int i;
    for(i = 0; i < nInputs; i++) {
      vInputs[vLevels[i]] = Vec_IntEntry(vSupp, nInputs - i - 1) << 1;
    }
    for(i = 0; i < nOutputs; i++) {
      int node = BDDGenerateAigRec(pNew, vInputs, vvNodes, i, 0);
      Gia_ManAppendCo(pNew, node);
    }
  }

Here is the call graph for this function:

Here is the caller graph for this function:

BDDGenerateAigRec()

int Ttopt::TruthTable::BDDGenerateAigRec ( Gia_Man_t * pNew, std::vector< int > const & vInputs, std::vector< std::vector< int > > & vvNodes, int index, int lev )

inline

Definition at line 420 of file giaTtopt.cpp.

                                                                                                                                 {
    int r = BDDFind(index, lev);
    if(r >= 0) {
      return vvNodes[lev][r >> 1] ^ (r & 1);
    }
    if(r >= -2) {
      return r + 2;
    }
    int cof0 = BDDGenerateAigRec(pNew, vInputs, vvNodes, index << 1, lev + 1);
    int cof1 = BDDGenerateAigRec(pNew, vInputs, vvNodes, (index << 1) ^ 1, lev + 1);
    if(cof0 == cof1) {
      return cof0;
    }
    int node;
    if(Imply(index << 1, (index << 1) ^ 1, lev + 1)) {
      node = Gia_ManHashOr(pNew, Gia_ManHashAnd(pNew, vInputs[lev], cof1), cof0);
    } else if(Imply((index << 1) ^ 1, index << 1, lev + 1)) {
      node = Gia_ManHashOr(pNew, Gia_ManHashAnd(pNew, vInputs[lev] ^ 1, cof0), cof1);
    } else {
      node = Gia_ManHashMux(pNew, vInputs[lev], cof1, cof0);
    }
    vvIndices[lev].push_back(index);
    vvNodes[lev].push_back(node);
    return node;
  }

Here is the call graph for this function:

Here is the caller graph for this function:

BDDNodeCount()

int Ttopt::TruthTable::BDDNodeCount ( )

inline

Definition at line 157 of file giaTtopt.cpp.

                     {
    int count = 1; // const node
    for(int i = 0; i < nInputs; i++) {
      count += BDDNodeCountLevel(i);
    }
    return count;
  }

Here is the call graph for this function:

Here is the caller graph for this function:

BDDNodeCountLevel()

int Ttopt::TruthTable::BDDNodeCountLevel ( int lev )

inline

Definition at line 153 of file giaTtopt.cpp.

                                 {
    return vvIndices[lev].size() - vvRedundantIndices[lev].size();
  }

Here is the caller graph for this function:

BDDRebuild()

virtual int Ttopt::TruthTable::BDDRebuild ( int lev )

inlinevirtual

Reimplemented in Ttopt::TruthTableCare, Ttopt::TruthTableLevelTSM, and Ttopt::TruthTableReo.

Definition at line 251 of file giaTtopt.cpp.

                                  {
    vvIndices[lev].clear();
    vvIndices[lev+1].clear();
    for(int i = lev; i < lev + 2; i++) {
      if(!i) {
        for(int j = 0; j < nOutputs; j++) {
          BDDBuildOne(j, 0);
        }
      } else {
        vvRedundantIndices[i-1].clear();
        BDDBuildLevel(i);
      }
    }
    if(lev < nInputs - 2) {
      vvRedundantIndices[lev+1].clear();
      for(unsigned i = 0; i < vvIndices[lev+1].size(); i++) {
        int index = vvIndices[lev+1][i];
        if(IsEq(index << 1, (index << 1) ^ 1, lev + 2)) {
          vvRedundantIndices[lev+1].push_back(index);
        }
      }
    }
    return BDDNodeCount();
  }

Here is the call graph for this function:

Here is the caller graph for this function:

BDDSwap()

virtual int Ttopt::TruthTable::BDDSwap ( int lev )

inlinevirtual

Reimplemented in Ttopt::TruthTableCare, and Ttopt::TruthTableReo.

Definition at line 313 of file giaTtopt.cpp.

                               {
    Swap(lev);
    for(int i = lev + 2; i < nInputs; i++) {
      for(unsigned j = 0; j < vvIndices[i].size(); j++) {
        SwapIndex(vvIndices[i][j], i - (lev + 2));
      }
    }
    // swapping vvRedundantIndices is unnecessary for node counting
    return BDDRebuild(lev);
  }

Here is the call graph for this function:

Here is the caller graph for this function:

GetValue()

word Ttopt::TruthTable::GetValue ( int index_lev, int lev )

inline

Definition at line 109 of file giaTtopt.cpp.

                                        {
    assert(index_lev >= 0);
    assert(nInputs - lev <= lww);
    int logwidth = nInputs - lev;
    int index = index_lev >> (lww - logwidth);
    int pos = (index_lev % (1 << (lww - logwidth))) << logwidth;
    return (t[index] >> pos) & ones[logwidth];
  }

Here is the caller graph for this function:

Imply()

bool Ttopt::TruthTable::Imply ( int index1, int index2, int lev )

inline

Definition at line 137 of file giaTtopt.cpp.

                                              {
    assert(index1 >= 0);
    assert(index2 >= 0);
    int logwidth = nInputs - lev;
    if(logwidth > lww) {
      int nScopeSize = 1 << (logwidth - lww);
      for(int i = 0; i < nScopeSize; i++) {
        if(t[nScopeSize * index1 + i] & ~t[nScopeSize * index2 + i]) {
          return false;
        }
      }
      return true;
    }
    return !(GetValue(index1, lev) & (GetValue(index2, lev) ^ ones[logwidth]));
  }

Here is the call graph for this function:

Here is the caller graph for this function:

IsEq()

int Ttopt::TruthTable::IsEq ( int index1, int index2, int lev, bool fCompl = false )

inline

Definition at line 118 of file giaTtopt.cpp.

                                                                 {
    assert(index1 >= 0);
    assert(index2 >= 0);
    int logwidth = nInputs - lev;
    bool fEq = true;
    if(logwidth > lww) {
      int nScopeSize = 1 << (logwidth - lww);
      for(int i = 0; i < nScopeSize && (fEq || fCompl); i++) {
        fEq &= (t[nScopeSize * index1 + i] == t[nScopeSize * index2 + i]);
        fCompl &= (t[nScopeSize * index1 + i] == ~t[nScopeSize * index2 + i]);
      }
    } else {
      word value = GetValue(index1, lev) ^ GetValue(index2, lev);
      fEq &= !value;
      fCompl &= !(value ^ ones[logwidth]);
    }
    return 2 * fCompl + fEq;
  }

Here is the call graph for this function:

Here is the caller graph for this function:

Load()

virtual void Ttopt::TruthTable::Load ( unsigned i )

inlinevirtual

Reimplemented in Ttopt::TruthTableCare, and Ttopt::TruthTableReo.

Definition at line 89 of file giaTtopt.cpp.

                                {
    assert(i < savedt.size());
    t = savedt[i];
    vLevels = vLevelsSaved[i];
  }

Here is the caller graph for this function:

LoadIndices()

virtual void Ttopt::TruthTable::LoadIndices ( unsigned i )

inlinevirtual

Reimplemented in Ttopt::TruthTableCare, and Ttopt::TruthTableReo.

Definition at line 104 of file giaTtopt.cpp.

                                       {
    vvIndices = vvIndicesSaved[i];
    vvRedundantIndices = vvRedundantIndicesSaved[i];
  }

Here is the caller graph for this function:

RandomSiftReo()

int Ttopt::TruthTable::RandomSiftReo ( int nRound )

inline

Definition at line 396 of file giaTtopt.cpp.

                                {
    int best = SiftReo();
    Save(2);
    for(int i = 0; i < nRound; i++) {
      std::vector<int> vLevelsNew(nInputs);
      int j;
      for(j = 0; j < nInputs; j++) {
        vLevelsNew[j] = j;
      }
      for(j = nInputs - 1; j > 0; j--) {
        int d = rand() % j;
        std::swap(vLevelsNew[j], vLevelsNew[d]);
      }
      Reo(vLevelsNew);
      int r = SiftReo();
      if(best > r) {
        best = r;
        Save(2);
      }
    }
    Load(2);
    return best;
  }

Here is the call graph for this function:

Here is the caller graph for this function:

Reo()

void Ttopt::TruthTable::Reo ( std::vector< int > vLevelsNew )

inline

Definition at line 379 of file giaTtopt.cpp.

                                      {
    for(int i = 0; i < nInputs; i++) {
      int var = std::find(vLevelsNew.begin(), vLevelsNew.end(), i) - vLevelsNew.begin();
      int lev = vLevels[var];
      if(lev < i) {
        for(int j = lev; j < i; j++) {
          Swap(j);
        }
      } else if(lev > i) {
        for(int j = lev - 1; j >= i; j--) {
          Swap(j);
        }
      }
    }
    assert(vLevels == vLevelsNew);
  }

Here is the call graph for this function:

Here is the caller graph for this function:

Save()

virtual void Ttopt::TruthTable::Save ( unsigned i )

inlinevirtual

Reimplemented in Ttopt::TruthTableCare, and Ttopt::TruthTableReo.

Definition at line 80 of file giaTtopt.cpp.

                                {
    if(savedt.size() < i + 1) {
      savedt.resize(i + 1);
      vLevelsSaved.resize(i + 1);
    }
    savedt[i] = t;
    vLevelsSaved[i] = vLevels;
  }

Here is the caller graph for this function:

SaveIndices()

virtual void Ttopt::TruthTable::SaveIndices ( unsigned i )

inlinevirtual

Reimplemented in Ttopt::TruthTableCare, and Ttopt::TruthTableReo.

Definition at line 95 of file giaTtopt.cpp.

                                       {
    if(vvIndicesSaved.size() < i + 1) {
      vvIndicesSaved.resize(i + 1);
      vvRedundantIndicesSaved.resize(i + 1);
    }
    vvIndicesSaved[i] = vvIndices;
    vvRedundantIndicesSaved[i] = vvRedundantIndices;
  }

Here is the caller graph for this function:

SiftReo()

int Ttopt::TruthTable::SiftReo ( )

inline

Definition at line 324 of file giaTtopt.cpp.

                {
    int best = BDDBuild();
    Save(0);
    SaveIndices(0);
    std::vector<int> vars(nInputs);
    int i;
    for(i = 0; i < nInputs; i++) {
      vars[i] = i;
    }
    std::vector<unsigned> vCounts(nInputs);
    for(i = 0; i < nInputs; i++) {
      vCounts[i] = BDDNodeCountLevel(vLevels[i]);
    }
    for(i = 1; i < nInputs; i++) {
      int j = i;
      while(j > 0 && vCounts[vars[j-1]] < vCounts[vars[j]]) {
        std::swap(vars[j], vars[j-1]);
        j--;
      }
    }
    bool turn = true;
    unsigned j;
    for(j = 0; j < vars.size(); j++) {
      int var = vars[j];
      bool updated = false;
      int lev = vLevels[var];
      for(int i = lev; i < nInputs - 1; i++) {
        int count = BDDSwap(i);
        if(best > count) {
          best = count;
          updated = true;
          Save(turn);
          SaveIndices(turn);
        }
      }
      if(lev) {
        Load(!turn);
        LoadIndices(!turn);
        for(int i = lev - 1; i >= 0; i--) {
          int count = BDDSwap(i);
          if(best > count) {
            best = count;
            updated = true;
            Save(turn);
            SaveIndices(turn);
          }
        }
      }
      turn ^= updated;
      Load(!turn);
      LoadIndices(!turn);
    }
    return best;
  }

Here is the call graph for this function:

Here is the caller graph for this function:

Swap()

virtual void Ttopt::TruthTable::Swap ( int lev )

inlinevirtual

Reimplemented in Ttopt::TruthTableCare, and Ttopt::TruthTableReo.

Definition at line 276 of file giaTtopt.cpp.

                             {
    assert(lev < nInputs - 1);
    std::vector<int>::iterator it0 = std::find(vLevels.begin(), vLevels.end(), lev);
    std::vector<int>::iterator it1 = std::find(vLevels.begin(), vLevels.end(), lev + 1);
    std::swap(*it0, *it1);
    if(nInputs - lev - 1 > lww) {
      int nScopeSize = 1 << (nInputs - lev - 2 - lww);
      for(int i = nScopeSize; i < nTotalSize; i += (nScopeSize << 2)) {
        for(int j = 0; j < nScopeSize; j++) {
          std::swap(t[i + j], t[i + nScopeSize + j]);
        }
      }
    } else if(nInputs - lev - 1 == lww) {
      for(int i = 0; i < nTotalSize; i += 2) {
        t[i+1] ^= t[i] >> (ww / 2);
        t[i] ^= t[i+1] << (ww / 2);
        t[i+1] ^= t[i] >> (ww / 2);
      }
    } else {
      for(int i = 0; i < nTotalSize; i++) {
        int d = nInputs - lev - 2;
        int shamt = 1 << d;
        t[i] ^= (t[i] >> shamt) & swapmask[d];
        t[i] ^= (t[i] & swapmask[d]) << shamt;
        t[i] ^= (t[i] >> shamt) & swapmask[d];
      }
    }
  }

Here is the caller graph for this function:

SwapIndex()

void Ttopt::TruthTable::SwapIndex ( int & index, int d )

inline

Definition at line 305 of file giaTtopt.cpp.

                                    {
    if((index >> d) % 4 == 1) {
      index += 1 << d;
    } else if((index >> d) % 4 == 2) {
      index -= 1 << d;
    }
  }

Here is the caller graph for this function:

Member Data Documentation

lww

const int Ttopt::TruthTable::lww = 6

static

Definition at line 42 of file giaTtopt.cpp.

nInputs

int Ttopt::TruthTable::nInputs

Definition at line 45 of file giaTtopt.cpp.

nOutputs

int Ttopt::TruthTable::nOutputs

Definition at line 48 of file giaTtopt.cpp.

nSize

int Ttopt::TruthTable::nSize

Definition at line 46 of file giaTtopt.cpp.

nTotalSize

int Ttopt::TruthTable::nTotalSize

Definition at line 47 of file giaTtopt.cpp.

ones

const word Ttopt::TruthTable::ones

static

Initial value:

= {ABC_CONST(0x0000000000000001),
                                  ABC_CONST(0x0000000000000003),
                                  ABC_CONST(0x000000000000000f),
                                  ABC_CONST(0x00000000000000ff),
                                  ABC_CONST(0x000000000000ffff),
                                  ABC_CONST(0x00000000ffffffff),
                                  ABC_CONST(0xffffffffffffffff)}

Definition at line 60 of file giaTtopt.cpp.

savedt

std::vector<std::vector<word> > Ttopt::TruthTable::savedt

Definition at line 55 of file giaTtopt.cpp.

swapmask

const word Ttopt::TruthTable::swapmask

static

Initial value:

= {ABC_CONST(0x2222222222222222),
                                      ABC_CONST(0x0c0c0c0c0c0c0c0c),
                                      ABC_CONST(0x00f000f000f000f0),
                                      ABC_CONST(0x0000ff000000ff00),
                                      ABC_CONST(0x00000000ffff0000)}

Definition at line 61 of file giaTtopt.cpp.

t

std::vector<word> Ttopt::TruthTable::t

Definition at line 49 of file giaTtopt.cpp.

vLevels

std::vector<int> Ttopt::TruthTable::vLevels

Definition at line 53 of file giaTtopt.cpp.

vLevelsSaved

std::vector<std::vector<int> > Ttopt::TruthTable::vLevelsSaved

Definition at line 58 of file giaTtopt.cpp.

vvIndices

std::vector<std::vector<int> > Ttopt::TruthTable::vvIndices

Definition at line 51 of file giaTtopt.cpp.

vvIndicesSaved

std::vector<std::vector<std::vector<int> > > Ttopt::TruthTable::vvIndicesSaved

Definition at line 56 of file giaTtopt.cpp.

vvRedundantIndices

std::vector<std::vector<int> > Ttopt::TruthTable::vvRedundantIndices

Definition at line 52 of file giaTtopt.cpp.

vvRedundantIndicesSaved

std::vector<std::vector<std::vector<int> > > Ttopt::TruthTable::vvRedundantIndicesSaved

Definition at line 57 of file giaTtopt.cpp.

ww

const int Ttopt::TruthTable::ww = 64

static

Definition at line 41 of file giaTtopt.cpp.

---

The documentation for this class was generated from the following file:

• src/aig/gia/giaTtopt.cpp