ABC: A System for Sequential Synthesis and Verification
 
Loading...
Searching...
No Matches
Public Member Functions | List of all members
rrr::AndNetwork Class Reference

#include <rrrAndNetwork.h>

Public Member Functions

 AndNetwork ()
 
 AndNetwork (AndNetwork const &x)
 
AndNetwork & operator= (AndNetwork const &x)
 
void Clear (bool fClearCallbacks=true)
 
void Reserve (int nReserve)
 
int AddPi ()
 
int AddAnd (int id0, int id1, bool c0, bool c1)
 
int AddPo (int id, bool c)
 
template<typename Ntk, typename Reader>
void Read (Ntk *pFrom, Reader &reader, bool fNew=true)
 
bool UseComplementedEdges () const
 
int GetNumNodes () const
 
int GetNumPis () const
 
int GetNumInts () const
 
int GetNumPos () const
 
int GetNumLevels () const
 
int GetConst0 () const
 
int GetPi (int idx) const
 
int GetPo (int idx) const
 
std::vector< int > GetPis () const
 
std::vector< int > GetInts () const
 
std::vector< int > GetPisInts () const
 
std::vector< int > GetPos () const
 
bool IsPi (int id) const
 
bool IsInt (int id) const
 
bool IsPo (int id) const
 
NodeType GetNodeType (int id) const
 
bool IsPoDriver (int id) const
 
int GetPiIndex (int id) const
 
int GetIntIndex (int id) const
 
int GetPoIndex (int id) const
 
int GetNumFanins (int id) const
 
int GetNumFanouts (int id) const
 
int GetFanin (int id, int idx) const
 
bool GetCompl (int id, int idx) const
 
int FindFanin (int id, int fi) const
 
bool IsReconvergent (int id)
 
std::vector< int > GetNeighbors (int id, bool fPis, int nHops)
 
template<template< typename... > typename Container, typename... Ts, template< typename... > typename Container2, typename... Ts2>
bool IsReachable (Container< Ts... > const &srcs, Container2< Ts2... > const &dsts)
 
template<template< typename... > typename Container, typename... Ts, template< typename... > typename Container2, typename... Ts2>
std::vector< int > GetInners (Container< Ts... > const &srcs, Container2< Ts2... > const &dsts)
 
std::set< int > GetExtendedFanins (int id)
 
void ForEachPi (std::function< void(int)> const &func) const
 
void ForEachPiIdx (std::function< void(int, int)> const &func) const
 
void ForEachInt (std::function< void(int)> const &func) const
 
void ForEachIntReverse (std::function< void(int)> const &func) const
 
void ForEachPiInt (std::function< void(int)> const &func) const
 
void ForEachPo (std::function< void(int)> const &func) const
 
template<typename Func>
void ForEachPoDriver (Func const &func) const
 
template<typename Func>
void ForEachFanin (int id, Func const &func) const
 
template<typename Func>
void ForEachFaninIdx (int id, Func const &func) const
 
template<typename Func>
void ForEachFanout (int id, bool fPos, Func const &func) const
 
template<typename Func>
void ForEachFanoutRidx (int id, bool fPos, Func const &func) const
 
void ForEachTfi (int id, bool fPis, std::function< void(int)> const &func)
 
template<template< typename... > typename Container, typename... Ts>
void ForEachTfiEnd (int id, Container< Ts... > const &ends, std::function< void(int)> const &func)
 
void ForEachTfiUpdate (int id, bool fPis, std::function< bool(int)> const &func)
 
template<template< typename... > typename Container, typename... Ts>
void ForEachTfisUpdate (Container< Ts... > const &ids, bool fPis, std::function< bool(int)> const &func)
 
void ForEachTfo (int id, bool fPos, std::function< void(int)> const &func)
 
void ForEachTfoReverse (int id, bool fPos, std::function< void(int)> const &func)
 
void ForEachTfoUpdate (int id, bool fPos, std::function< bool(int)> const &func)
 
template<template< typename... > typename Container, typename... Ts>
void ForEachTfos (Container< Ts... > const &ids, bool fPos, std::function< void(int)> const &func)
 
template<template< typename... > typename Container, typename... Ts>
void ForEachTfosUpdate (Container< Ts... > const &ids, bool fPos, std::function< bool(int)> const &func)
 
template<template< typename... > typename Container, typename... Ts>
AndNetwork * Extract (Container< Ts... > const &ids, std::vector< int > const &vInputs, std::vector< int > const &vOutputs)
 
void RemoveFanin (int id, int idx)
 
void RemoveUnused (int id, bool fRecursive=false, bool fSweeping=false)
 
void RemoveBuffer (int id)
 
void RemoveConst (int id)
 
void AddFanin (int id, int fi, bool c)
 
void TrivialCollapse (int id)
 
void TrivialDecompose (int id)
 
template<typename Func>
void SortFanins (int id, Func const &cost)
 
std::pair< std::vector< int >, std::vector< bool > > Insert (AndNetwork *pNtk, std::vector< int > const &vInputs, std::vector< bool > const &vCompls, std::vector< int > const &vOutputs)
 
void Propagate (int id=-1)
 
void Sweep (bool fPropagate=true)
 
int Save (int slot=-1)
 
void Load (int slot)
 
void PopBack ()
 
void AddCallback (Callback const &callback)
 
void Print () const
 

Detailed Description

Definition at line 15 of file rrrAndNetwork.h.

Constructor & Destructor Documentation

◆ AndNetwork() [1/2]

rrr::AndNetwork::AndNetwork ( )

Definition at line 237 of file rrrAndNetwork.h.

237 :
238 nNodes(0),
239 fLockTrav(false),
240 iTrav(0),
241 fPropagating(false) {
242 // add constant node
243 vvFaninEdges.emplace_back();
244 vRefs.push_back(0);
245 nNodes++;
246 }
Here is the caller graph for this function:

◆ AndNetwork() [2/2]

rrr::AndNetwork::AndNetwork ( AndNetwork const & x)

Definition at line 248 of file rrrAndNetwork.h.

248 :
249 fLockTrav(false),
250 iTrav(0),
251 fPropagating(false) {
252 nNodes = x.nNodes;
253 vPis = x.vPis;
254 lInts = x.lInts;
255 sInts = x.sInts;
256 vPos = x.vPos;
257 vvFaninEdges = x.vvFaninEdges;
258 vRefs = x.vRefs;
259 }
Here is the call graph for this function:

Member Function Documentation

◆ AddAnd()

int rrr::AndNetwork::AddAnd ( int id0,
int id1,
bool c0,
bool c1 )
inline

Definition at line 311 of file rrrAndNetwork.h.

311 {
312 assert(id0 < nNodes);
313 assert(id1 < nNodes);
314 assert(id0 != id1);
315 lInts.push_back(nNodes);
316 sInts.insert(nNodes);
317 vRefs[id0]++;
318 vRefs[id1]++;
319 vvFaninEdges.emplace_back(std::initializer_list<int>({Node2Edge(id0, c0), Node2Edge(id1, c1)}));
320 vRefs.push_back(0);
321 assert(!check_int_max(nNodes));
322 return nNodes++;
323 }
assert
#define assert(ex)
Definition util_old.h:213

◆ AddCallback()

void rrr::AndNetwork::AddCallback ( Callback const & callback)

Definition at line 1608 of file rrrAndNetwork.h.

1608 {
1609 vCallbacks.push_back(callback);
1610 }

◆ AddFanin()

void rrr::AndNetwork::AddFanin ( int id,
int fi,
bool c )

Definition at line 1339 of file rrrAndNetwork.h.

1339 {
1340 assert(FindFanin(id, fi) == -1); // no duplication
1341 assert(fi != GetConst0() || !c); // no const-1
1342 Action action;
1343 action.type = ADD_FANIN;
1344 action.id = id;
1345 action.idx = GetNumFanins(id);
1346 action.fi = fi;
1347 action.c = c;
1348 itr it = std::find(lInts.begin(), lInts.end(), id);
1349 itr it2 = std::find(it, lInts.end(), fi);
1350 if(it2 != lInts.end()) {
1351 lInts.erase(it2);
1352 it2 = lInts.insert(it, fi);
1353 SortInts(it2);
1354 }
1355 vRefs[fi]++;
1356 vvFaninEdges[id].push_back(Node2Edge(fi, c));
1357 TakenAction(action);
1358 }
rrr::AndNetwork::GetNumFanins
int GetNumFanins(int id) const
Definition rrrAndNetwork.h:481
rrr::AndNetwork::FindFanin
int FindFanin(int id, int fi) const
Definition rrrAndNetwork.h:497
rrr::AndNetwork::GetConst0
int GetConst0() const
Definition rrrAndNetwork.h:386
rrr::ADD_FANIN
@ ADD_FANIN
Definition rrrTypes.h:38
Here is the call graph for this function:

◆ AddPi()

int rrr::AndNetwork::AddPi ( )
inline

Definition at line 303 of file rrrAndNetwork.h.

303 {
304 vPis.push_back(nNodes);
305 vvFaninEdges.emplace_back();
306 vRefs.push_back(0);
307 assert(!check_int_max(nNodes));
308 return nNodes++;
309 }
Here is the caller graph for this function:

◆ AddPo()

int rrr::AndNetwork::AddPo ( int id,
bool c )
inline

Definition at line 325 of file rrrAndNetwork.h.

325 {
326 assert(id < nNodes);
327 vPos.push_back(nNodes);
328 vRefs[id]++;
329 vvFaninEdges.emplace_back(std::initializer_list<int>({Node2Edge(id, c)}));
330 vRefs.push_back(0);
331 assert(!check_int_max(nNodes));
332 return nNodes++;
333 }
Here is the caller graph for this function:

◆ Clear()

void rrr::AndNetwork::Clear ( bool fClearCallbacks = true)

Definition at line 276 of file rrrAndNetwork.h.

276 {
277 nNodes = 0;
278 vPis.clear();
279 lInts.clear();
280 sInts.clear();
281 vPos.clear();
282 vvFaninEdges.clear();
283 vRefs.clear();
284 fLockTrav = false;
285 iTrav = 0;
286 vTrav.clear();
287 fPropagating = false;
288 if(fClearCallbacks) {
289 vCallbacks.clear();
290 }
291 vBackups.clear();
292 // add constant node
293 vvFaninEdges.emplace_back();
294 vRefs.push_back(0);
295 nNodes++;
296 }
Here is the caller graph for this function:

◆ Extract()

template<template< typename... > typename Container, typename... Ts>
AndNetwork * rrr::AndNetwork::Extract ( Container< Ts... > const & ids,
std::vector< int > const & vInputs,
std::vector< int > const & vOutputs )

Definition at line 1169 of file rrrAndNetwork.h.

1169 {
1170 AndNetwork *pNtk = new AndNetwork;
1171 pNtk->Reserve(int_size(vInputs) + int_size(ids) + int_size(vOutputs));
1172 std::map<int, int> m;
1173 m[GetConst0()] = pNtk->GetConst0();
1174 for(int id: vInputs) {
1175 m[id] = pNtk->AddPi();
1176 }
1177 StartTraversal();
1178 for(int id: ids) {
1179 vTrav[id] = iTrav;
1180 }
1181 ForEachInt([&](int id) {
1182 if(vTrav[id] == iTrav) {
1183 m[id] = pNtk->CreateNode();
1184 pNtk->lInts.push_back(m[id]);
1185 pNtk->sInts.insert(m[id]);
1186 pNtk->vvFaninEdges[m[id]].resize(GetNumFanins(id));
1187 ForEachFaninIdx(id, [&](int idx, int fi, bool c) {
1188 assert(m.count(fi));
1189 pNtk->vvFaninEdges[m[id]][idx] = pNtk->Node2Edge(m[fi], c);
1190 pNtk->vRefs[m[fi]]++;
1191 });
1192 }
1193 });
1194 EndTraversal();
1195 for(int id: vOutputs) {
1196 assert(m.count(id));
1197 pNtk->AddPo(m[id], false);
1198 }
1199 return pNtk;
1200 }
rrr::AndNetwork::ForEachFaninIdx
void ForEachFaninIdx(int id, Func const &func) const
Definition rrrAndNetwork.h:802
rrr::AndNetwork::ForEachInt
void ForEachInt(std::function< void(int)> const &func) const
Definition rrrAndNetwork.h:750
Here is the call graph for this function:

◆ FindFanin()

int rrr::AndNetwork::FindFanin ( int id,
int fi ) const
inline

Definition at line 497 of file rrrAndNetwork.h.

497 {
498 for(int idx = 0; idx < GetNumFanins(id); idx++) {
499 if(GetFanin(id, idx) == fi) {
500 return idx;
501 }
502 }
503 return -1;
504 }
rrr::AndNetwork::GetFanin
int GetFanin(int id, int idx) const
Definition rrrAndNetwork.h:489
Here is the call graph for this function:
Here is the caller graph for this function:

◆ ForEachFanin()

template<typename Func>
void rrr::AndNetwork::ForEachFanin ( int id,
Func const & func ) const
inline

Definition at line 790 of file rrrAndNetwork.h.

790 {
791 static_assert(is_invokable<Func, int>::value || is_invokable<Func, int, bool>::value, "for each edge function format error");
792 for(int fi_edge: vvFaninEdges[id]) {
793 if constexpr(is_invokable<Func, int>::value) {
794 func(Edge2Node(fi_edge));
795 } else if constexpr(is_invokable<Func, int, bool>::value) {
796 func(Edge2Node(fi_edge), EdgeIsCompl(fi_edge));
797 }
798 }
799 }
Here is the caller graph for this function:

◆ ForEachFaninIdx()

template<typename Func>
void rrr::AndNetwork::ForEachFaninIdx ( int id,
Func const & func ) const
inline

Definition at line 802 of file rrrAndNetwork.h.

802 {
803 static_assert(is_invokable<Func, int, int>::value || is_invokable<Func, int, int, bool>::value, "for each edge function format error");
804 for(int idx = 0; idx < GetNumFanins(id); idx++) {
805 if constexpr(is_invokable<Func, int, int>::value) {
806 func(idx, GetFanin(id, idx));
807 } else if constexpr(is_invokable<Func, int, int, bool>::value) {
808 func(idx, GetFanin(id, idx), GetCompl(id, idx));
809 }
810 }
811 }
rrr::AndNetwork::GetCompl
bool GetCompl(int id, int idx) const
Definition rrrAndNetwork.h:493
Here is the call graph for this function:
Here is the caller graph for this function:

◆ ForEachFanout()

template<typename Func>
void rrr::AndNetwork::ForEachFanout ( int id,
bool fPos,
Func const & func ) const
inline

Definition at line 814 of file rrrAndNetwork.h.

814 {
815 static_assert(is_invokable<Func, int>::value || is_invokable<Func, int, bool>::value, "for each edge function format error");
816 if(vRefs[id] == 0) {
817 return;
818 }
819 citr it = lInts.begin();
820 if(IsInt(id)) {
821 it = std::find(it, lInts.end(), id);
822 assert(it != lInts.end());
823 it++;
824 }
825 int nRefs = vRefs[id];
826 for(; nRefs != 0 && it != lInts.end(); it++) {
827 int idx = FindFanin(*it, id);
828 if(idx >= 0) {
829 if constexpr(is_invokable<Func, int>::value) {
830 func(*it);
831 } else if constexpr(is_invokable<Func, int, bool>::value) {
832 func(*it, GetCompl(*it, idx));
833 }
834 nRefs--;
835 }
836 }
837 if(fPos && nRefs != 0) {
838 for(int po: vPos) {
839 if(GetFanin(po, 0) == id) {
840 if constexpr(is_invokable<Func, int>::value) {
841 func(po);
842 } else if constexpr(is_invokable<Func, int, bool>::value) {
843 func(po, GetCompl(po, 0));
844 }
845 nRefs--;
846 if(nRefs == 0) {
847 break;
848 }
849 }
850 }
851 }
852 assert(!fPos || nRefs == 0);
853 }
rrr::AndNetwork::IsInt
bool IsInt(int id) const
Definition rrrAndNetwork.h:424
Here is the call graph for this function:
Here is the caller graph for this function:

◆ ForEachFanoutRidx()

template<typename Func>
void rrr::AndNetwork::ForEachFanoutRidx ( int id,
bool fPos,
Func const & func ) const
inline

Definition at line 856 of file rrrAndNetwork.h.

856 {
857 static_assert(is_invokable<Func, int, int>::value || is_invokable<Func, int, bool, int>::value, "for each edge function format error");
858 if(vRefs[id] == 0) {
859 return;
860 }
861 citr it = lInts.begin();
862 if(IsInt(id)) {
863 it = std::find(it, lInts.end(), id);
864 assert(it != lInts.end());
865 it++;
866 }
867 int nRefs = vRefs[id];
868 for(; nRefs != 0 && it != lInts.end(); it++) {
869 int idx = FindFanin(*it, id);
870 if(idx >= 0) {
871 if constexpr(is_invokable<Func, int, int>::value) {
872 func(*it, idx);
873 } else if constexpr(is_invokable<Func, int, bool, int>::value) {
874 func(*it, GetCompl(*it, idx), idx);
875 }
876 nRefs--;
877 }
878 }
879 if(fPos && nRefs != 0) {
880 for(int po: vPos) {
881 if(GetFanin(po, 0) == id) {
882 if constexpr(is_invokable<Func, int, int>::value) {
883 func(po, 0);
884 } else if constexpr(is_invokable<Func, int, bool, int>::value) {
885 func(po, GetCompl(po, 0), 0);
886 }
887 nRefs--;
888 if(nRefs == 0) {
889 break;
890 }
891 }
892 }
893 }
894 assert(!fPos || nRefs == 0);
895 }
Here is the call graph for this function:
Here is the caller graph for this function:

◆ ForEachInt()

void rrr::AndNetwork::ForEachInt ( std::function< void(int)> const & func) const
inline

Definition at line 750 of file rrrAndNetwork.h.

750 {
751 for(int id: lInts) {
752 func(id);
753 }
754 }
Here is the caller graph for this function:

◆ ForEachIntReverse()

void rrr::AndNetwork::ForEachIntReverse ( std::function< void(int)> const & func) const
inline

Definition at line 756 of file rrrAndNetwork.h.

756 {
757 for(critr it = lInts.rbegin(); it != lInts.rend(); it++) {
758 func(*it);
759 }
760 }

◆ ForEachPi()

void rrr::AndNetwork::ForEachPi ( std::function< void(int)> const & func) const
inline

Definition at line 738 of file rrrAndNetwork.h.

738 {
739 for(int pi: vPis) {
740 func(pi);
741 }
742 }

◆ ForEachPiIdx()

void rrr::AndNetwork::ForEachPiIdx ( std::function< void(int, int)> const & func) const
inline

Definition at line 744 of file rrrAndNetwork.h.

744 {
745 for(int idx = 0; idx < GetNumPis(); idx++) {
746 func(idx, GetPi(idx));
747 }
748 }
rrr::AndNetwork::GetNumPis
int GetNumPis() const
Definition rrrAndNetwork.h:357
rrr::AndNetwork::GetPi
int GetPi(int idx) const
Definition rrrAndNetwork.h:390
Here is the call graph for this function:

◆ ForEachPiInt()

void rrr::AndNetwork::ForEachPiInt ( std::function< void(int)> const & func) const
inline

Definition at line 762 of file rrrAndNetwork.h.

762 {
763 for(int pi: vPis) {
764 func(pi);
765 }
766 for(int id: lInts) {
767 func(id);
768 }
769 }
Here is the caller graph for this function:

◆ ForEachPo()

void rrr::AndNetwork::ForEachPo ( std::function< void(int)> const & func) const
inline

Definition at line 771 of file rrrAndNetwork.h.

771 {
772 for(int po: vPos) {
773 func(po);
774 }
775 }

◆ ForEachPoDriver()

template<typename Func>
void rrr::AndNetwork::ForEachPoDriver ( Func const & func) const
inline

Definition at line 778 of file rrrAndNetwork.h.

778 {
779 static_assert(is_invokable<Func, int>::value || is_invokable<Func, int, bool>::value, "for each edge function format error");
780 for(int po: vPos) {
781 if constexpr(is_invokable<Func, int>::value) {
782 func(GetFanin(po, 0));
783 } else if constexpr(is_invokable<Func, int, bool>::value) {
784 func(GetFanin(po, 0), GetCompl(po, 0));
785 }
786 }
787 }
Here is the call graph for this function:
Here is the caller graph for this function:

◆ ForEachTfi()

void rrr::AndNetwork::ForEachTfi ( int id,
bool fPis,
std::function< void(int)> const & func )
inline

Definition at line 897 of file rrrAndNetwork.h.

897 {
898 // this does not include id itself
899 StartTraversal();
900 if(!fPis) {
901 for(int pi: vPis) {
902 vTrav[pi] = iTrav;
903 }
904 }
905 ForEachTfiRec(id, func);
906 EndTraversal();
907 }

◆ ForEachTfiEnd()

template<template< typename... > typename Container, typename... Ts>
void rrr::AndNetwork::ForEachTfiEnd ( int id,
Container< Ts... > const & ends,
std::function< void(int)> const & func )
inline

Definition at line 910 of file rrrAndNetwork.h.

910 {
911 // this does not include id itself
912 StartTraversal();
913 for(int end: ends) {
914 vTrav[end] = iTrav;
915 }
916 ForEachTfiRec(id, func);
917 EndTraversal();
918 }

◆ ForEachTfisUpdate()

template<template< typename... > typename Container, typename... Ts>
void rrr::AndNetwork::ForEachTfisUpdate ( Container< Ts... > const & ids,
bool fPis,
std::function< bool(int)> const & func )
inline

Definition at line 951 of file rrrAndNetwork.h.

951 {
952 // this includes ids themselves
953 StartTraversal();
954 for(int id: ids) {
955 vTrav[id] = iTrav;
956 }
957 critr it = lInts.rbegin();
958 while(vTrav[*it] != iTrav && it != lInts.rend()) {
959 it++;
960 }
961 for(; it != lInts.rend(); it++) {
962 if(vTrav[*it] == iTrav) {
963 if(func(*it)) {
964 for(int fi_edge: vvFaninEdges[*it]) {
965 vTrav[Edge2Node(fi_edge)] = iTrav;
966 }
967 }
968 }
969 }
970 if(fPis) {
971 for(int pi: vPis) {
972 if(vTrav[pi] == iTrav) {
973 func(pi);
974 }
975 }
976 }
977 EndTraversal();
978 }

◆ ForEachTfiUpdate()

void rrr::AndNetwork::ForEachTfiUpdate ( int id,
bool fPis,
std::function< bool(int)> const & func )
inline

Definition at line 920 of file rrrAndNetwork.h.

920 {
921 if(GetNumFanins(id) == 0) {
922 return;
923 }
924 StartTraversal();
925 for(int fi_edge: vvFaninEdges[id]) {
926 vTrav[Edge2Node(fi_edge)] = iTrav;
927 }
928 critr it = std::find(lInts.rbegin(), lInts.rend(), id);
929 assert(it != lInts.rend());
930 it++;
931 for(; it != lInts.rend(); it++) {
932 if(vTrav[*it] == iTrav) {
933 if(func(*it)) {
934 for(int fi_edge: vvFaninEdges[*it]) {
935 vTrav[Edge2Node(fi_edge)] = iTrav;
936 }
937 }
938 }
939 }
940 if(fPis) {
941 for(int pi: vPis) {
942 if(vTrav[pi] == iTrav) {
943 func(pi);
944 }
945 }
946 }
947 EndTraversal();
948 }
Here is the call graph for this function:

◆ ForEachTfo()

void rrr::AndNetwork::ForEachTfo ( int id,
bool fPos,
std::function< void(int)> const & func )
inline

Definition at line 980 of file rrrAndNetwork.h.

980 {
981 // this does not include id itself
982 if(vRefs[id] == 0) {
983 return;
984 }
985 StartTraversal();
986 vTrav[id] = iTrav;
987 citr it = std::find(lInts.begin(), lInts.end(), id);
988 assert(it != lInts.end());
989 it++;
990 for(; it != lInts.end(); it++) {
991 for(int fi_edge: vvFaninEdges[*it]) {
992 if(vTrav[Edge2Node(fi_edge)] == iTrav) {
993 func(*it);
994 vTrav[*it] = iTrav;
995 break;
996 }
997 }
998 }
999 if(fPos) {
1000 for(int po: vPos) {
1001 if(vTrav[GetFanin(po, 0)] == iTrav) {
1002 func(po);
1003 vTrav[po] = iTrav;
1004 }
1005 }
1006 }
1007 EndTraversal();
1008 }
Here is the call graph for this function:

◆ ForEachTfoReverse()

void rrr::AndNetwork::ForEachTfoReverse ( int id,
bool fPos,
std::function< void(int)> const & func )
inline

Definition at line 1010 of file rrrAndNetwork.h.

1010 {
1011 // this does not include id itself
1012 if(vRefs[id] == 0) {
1013 return;
1014 }
1015 StartTraversal();
1016 vTrav[id] = iTrav;
1017 citr it = std::find(lInts.begin(), lInts.end(), id);
1018 assert(it != lInts.end());
1019 it++;
1020 for(; it != lInts.end(); it++) {
1021 for(int fi_edge: vvFaninEdges[*it]) {
1022 if(vTrav[Edge2Node(fi_edge)] == iTrav) {
1023 vTrav[*it] = iTrav;
1024 break;
1025 }
1026 }
1027 }
1028 if(fPos) {
1029 for(int po: vPos) {
1030 if(vTrav[GetFanin(po, 0)] == iTrav) {
1031 vTrav[po] = iTrav;
1032 }
1033 }
1034 }
1035 EndTraversal(); // release here so func can call IsReconvergent
1036 unsigned iTravTfo = iTrav;
1037 if(fPos) {
1038 // use reverse order even for POs
1039 for(std::vector<int>::const_reverse_iterator it = vPos.rbegin(); it != vPos.rend(); it++) {
1040 assert(vTrav[*it] <= iTravTfo); // make sure func does not touch vTrav of preceding nodes
1041 if(vTrav[*it] == iTravTfo) {
1042 func(*it);
1043 }
1044 }
1045 }
1046 for(critr it = lInts.rbegin(); *it != id; it++) {
1047 assert(vTrav[*it] <= iTravTfo); // make sure func does not touch vTrav of preceding nodes
1048 if(vTrav[*it] == iTravTfo) {
1049 func(*it);
1050 }
1051 }
1052 }
Here is the call graph for this function:

◆ ForEachTfos()

template<template< typename... > typename Container, typename... Ts>
void rrr::AndNetwork::ForEachTfos ( Container< Ts... > const & ids,
bool fPos,
std::function< void(int)> const & func )
inline

Definition at line 1087 of file rrrAndNetwork.h.

1087 {
1088 // this includes ids themselves
1089 StartTraversal();
1090 for(int id: ids) {
1091 vTrav[id] = iTrav;
1092 }
1093 citr it = lInts.begin();
1094 while(vTrav[*it] != iTrav && it != lInts.end()) {
1095 it++;
1096 }
1097 for(; it != lInts.end(); it++) {
1098 if(vTrav[*it] == iTrav) {
1099 func(*it);
1100 } else {
1101 for(int fi_edge: vvFaninEdges[*it]) {
1102 if(vTrav[Edge2Node(fi_edge)] == iTrav) {
1103 func(*it);
1104 vTrav[*it] = iTrav;
1105 break;
1106 }
1107 }
1108 }
1109 }
1110 if(fPos) {
1111 for(int po: vPos) {
1112 if(vTrav[po] == iTrav || vTrav[GetFanin(po, 0)] == iTrav) {
1113 func(po);
1114 vTrav[po] = iTrav;
1115 }
1116 }
1117 }
1118 EndTraversal();
1119 }
Here is the call graph for this function:

◆ ForEachTfosUpdate()

template<template< typename... > typename Container, typename... Ts>
void rrr::AndNetwork::ForEachTfosUpdate ( Container< Ts... > const & ids,
bool fPos,
std::function< bool(int)> const & func )
inline

Definition at line 1122 of file rrrAndNetwork.h.

1122 {
1123 // this includes ids themselves
1124 StartTraversal();
1125 for(int id: ids) {
1126 vTrav[id] = iTrav;
1127 }
1128 citr it = lInts.begin();
1129 while(vTrav[*it] != iTrav && it != lInts.end()) {
1130 it++;
1131 }
1132 for(; it != lInts.end(); it++) {
1133 if(vTrav[*it] == iTrav) {
1134 if(!func(*it)) {
1135 vTrav[*it] = 0;
1136 }
1137 } else {
1138 for(int fi_edge: vvFaninEdges[*it]) {
1139 if(vTrav[Edge2Node(fi_edge)] == iTrav) {
1140 if(func(*it)) {
1141 vTrav[*it] = iTrav;
1142 }
1143 break;
1144 }
1145 }
1146 }
1147 }
1148 if(fPos) {
1149 for(int po: vPos) {
1150 if(vTrav[po] == iTrav) {
1151 if(!func(po)) {
1152 vTrav[po] = 0;
1153 }
1154 } else if(vTrav[GetFanin(po, 0)] == iTrav) {
1155 if(func(po)) {
1156 vTrav[po] = iTrav;
1157 }
1158 }
1159 }
1160 }
1161 EndTraversal();
1162 }
Here is the call graph for this function:

◆ ForEachTfoUpdate()

void rrr::AndNetwork::ForEachTfoUpdate ( int id,
bool fPos,
std::function< bool(int)> const & func )
inline

Definition at line 1054 of file rrrAndNetwork.h.

1054 {
1055 // this does not include id itself
1056 if(vRefs[id] == 0) {
1057 return;
1058 }
1059 StartTraversal();
1060 vTrav[id] = iTrav;
1061 citr it = std::find(lInts.begin(), lInts.end(), id);
1062 assert(it != lInts.end());
1063 it++;
1064 for(; it != lInts.end(); it++) {
1065 for(int fi_edge: vvFaninEdges[*it]) {
1066 if(vTrav[Edge2Node(fi_edge)] == iTrav) {
1067 if(func(*it)) {
1068 vTrav[*it] = iTrav;
1069 }
1070 break;
1071 }
1072 }
1073 }
1074 if(fPos) {
1075 for(int po: vPos) {
1076 if(vTrav[GetFanin(po, 0)] == iTrav) {
1077 if(func(po)) {
1078 vTrav[po] = iTrav;
1079 }
1080 }
1081 }
1082 }
1083 EndTraversal();
1084 }
Here is the call graph for this function:

◆ GetCompl()

bool rrr::AndNetwork::GetCompl ( int id,
int idx ) const
inline

Definition at line 493 of file rrrAndNetwork.h.

493 {
494 return EdgeIsCompl(vvFaninEdges[id][idx]);
495 }
Here is the caller graph for this function:

◆ GetConst0()

int rrr::AndNetwork::GetConst0 ( ) const
inline

Definition at line 386 of file rrrAndNetwork.h.

386 {
387 return 0;
388 }
Here is the caller graph for this function:

◆ GetExtendedFanins()

std::set< int > rrr::AndNetwork::GetExtendedFanins ( int id)
inline

Definition at line 697 of file rrrAndNetwork.h.

697 {
698 // go to the root of trivially collapsable nodes
699 while(GetNumFanouts(id) == 1) {
700 int id_new = -1;
701 ForEachFanout(id, false, [&](int fo, bool c) {
702 if(!c) {
703 id_new = fo;
704 }
705 });
706 if(id_new != -1) {
707 id = id_new;
708 } else {
709 break;
710 }
711 }
712 // emulate trivial collapse
713 std::vector<int> vFaninEdges = vvFaninEdges[id];
714 for(int idx = 0; idx < int_size(vFaninEdges);) {
715 int fi_edge = vFaninEdges[idx];
716 int fi = Edge2Node(fi_edge);
717 bool c = EdgeIsCompl(fi_edge);
718 if(!IsPi(fi) && !c && vRefs[fi] == 1) {
719 std::vector<int>::iterator it = vFaninEdges.begin() + idx;
720 it = vFaninEdges.erase(it);
721 vFaninEdges.insert(it, vvFaninEdges[fi].begin(), vvFaninEdges[fi].end());
722 } else {
723 idx++;
724 }
725 }
726 // create set
727 std::set<int> sFanins;
728 for(int fi_edge: vFaninEdges) {
729 sFanins.insert(Edge2Node(fi_edge));
730 }
731 return sFanins;
732 }
rrr::AndNetwork::ForEachFanout
void ForEachFanout(int id, bool fPos, Func const &func) const
Definition rrrAndNetwork.h:814
rrr::AndNetwork::GetNumFanouts
int GetNumFanouts(int id) const
Definition rrrAndNetwork.h:485
rrr::AndNetwork::IsPi
bool IsPi(int id) const
Definition rrrAndNetwork.h:420
Here is the call graph for this function:

◆ GetFanin()

int rrr::AndNetwork::GetFanin ( int id,
int idx ) const
inline

Definition at line 489 of file rrrAndNetwork.h.

489 {
490 return Edge2Node(vvFaninEdges[id][idx]);
491 }
Here is the caller graph for this function:

◆ GetInners()

template<template< typename... > typename Container, typename... Ts, template< typename... > typename Container2, typename... Ts2>
std::vector< int > rrr::AndNetwork::GetInners ( Container< Ts... > const & srcs,
Container2< Ts2... > const & dsts )
inline

Definition at line 640 of file rrrAndNetwork.h.

640 {
641 // this includes sources and destinations that are connected
642 if(srcs.empty() || dsts.empty()) {
643 return std::vector<int>();
644 }
645 unsigned iTravStart = StartTraversal(4);
646 unsigned iDst = iTravStart;
647 unsigned iTfo = iTravStart + 1;
648 unsigned iInner = iTravStart + 2;
649 // mark destinations (to prevent nodes between destinations to sources being included)
650 for(int id: dsts) {
651 vTrav[id] = iDst;
652 }
653 // mark TFOs of sources until destinations, which will be marekd as inner
654 for(int id: srcs) {
655 if(vTrav[id] == iDst) {
656 vTrav[id] = iInner;
657 } else {
658 vTrav[id] = iTfo;
659 }
660 }
661 citr it = lInts.begin();
662 while(vTrav[*it] != iTfo && it != lInts.end()) {
663 it++;
664 }
665 for(; it != lInts.end(); it++) {
666 if(vTrav[*it] >= iTfo) { // TFO or inner
667 continue;
668 }
669 for(int fi_edge: vvFaninEdges[*it]) {
670 if(vTrav[Edge2Node(fi_edge)] == iTfo) {
671 if(vTrav[*it] == iDst) {
672 vTrav[*it] = iInner;
673 } else {
674 vTrav[*it] = iTfo;
675 }
676 break;
677 }
678 }
679 }
680 // traverse TFIs of connected destinations
681 std::vector<int> vInners;
682 for(int id: dsts) {
683 if(vTrav[id] == iInner) {
684 vInners.push_back(id);
685 vTrav[id] = iTrav;
686 ForEachTfiRec(id, [&](int fi) {
687 if(vTrav[fi] == iTfo || vTrav[fi] == iInner) {
688 vInners.push_back(fi);
689 }
690 });
691 }
692 }
693 EndTraversal();
694 return vInners;
695 }

◆ GetIntIndex()

int rrr::AndNetwork::GetIntIndex ( int id) const
inline

Definition at line 459 of file rrrAndNetwork.h.

459 {
460 assert(check_int_size(lInts));
461 int index = 0;
462 citr it = lInts.begin();
463 for(; it != lInts.end(); it++) {
464 if(*it == id) {
465 break;
466 }
467 index++;
468 }
469 assert(it != lInts.end());
470 return index;
471 }

◆ GetInts()

std::vector< int > rrr::AndNetwork::GetInts ( ) const
inline

Definition at line 402 of file rrrAndNetwork.h.

402 {
403 return std::vector<int>(lInts.begin(), lInts.end());
404 }

◆ GetNeighbors()

std::vector< int > rrr::AndNetwork::GetNeighbors ( int id,
bool fPis,
int nHops )
inline

Definition at line 542 of file rrrAndNetwork.h.

542 {
543 StartTraversal();
544 vTrav[id] = iTrav;
545 std::vector<int> vPrevs, vNexts;
546 vNexts.push_back(id);
547 for(int i = 0; i < nHops; i++) {
548 vPrevs.swap(vNexts);
549 for(int id: vPrevs) {
550 ForEachFanin(id, [&](int fi) {
551 if(vTrav[fi] != iTrav) {
552 vNexts.push_back(fi);
553 vTrav[fi] = iTrav;
554 }
555 });
556 ForEachFanout(id, false, [&](int fo) {
557 if(vTrav[fo] != iTrav) {
558 vNexts.push_back(fo);
559 vTrav[fo] = iTrav;
560 }
561 });
562 }
563 vPrevs.clear();
564 }
565 vTrav[id] = 0;
566 std::vector<int> v;
567 if(fPis) {
568 ForEachPiInt([&](int id) {
569 if(vTrav[id] == iTrav) {
570 v.push_back(id);
571 }
572 });
573 } else {
574 ForEachInt([&](int id) {
575 if(vTrav[id] == iTrav) {
576 v.push_back(id);
577 }
578 });
579 }
580 EndTraversal();
581 return v;
582 }
rrr::AndNetwork::ForEachPiInt
void ForEachPiInt(std::function< void(int)> const &func) const
Definition rrrAndNetwork.h:762
rrr::AndNetwork::ForEachFanin
void ForEachFanin(int id, Func const &func) const
Definition rrrAndNetwork.h:790
Here is the call graph for this function:

◆ GetNodeType()

NodeType rrr::AndNetwork::GetNodeType ( int id) const
inline

Definition at line 432 of file rrrAndNetwork.h.

432 {
433 if(IsPi(id)) {
434 return PI;
435 }
436 if(IsPo(id)) {
437 return PO;
438 }
439 return AND;
440 }
rrr::AndNetwork::IsPo
bool IsPo(int id) const
Definition rrrAndNetwork.h:428
rrr::AND
@ AND
Definition rrrTypes.h:13
rrr::PI
@ PI
Definition rrrTypes.h:11
rrr::PO
@ PO
Definition rrrTypes.h:12
Here is the call graph for this function:

◆ GetNumFanins()

int rrr::AndNetwork::GetNumFanins ( int id) const
inline

Definition at line 481 of file rrrAndNetwork.h.

481 {
482 return int_size(vvFaninEdges[id]);
483 }
Here is the caller graph for this function:

◆ GetNumFanouts()

int rrr::AndNetwork::GetNumFanouts ( int id) const
inline

Definition at line 485 of file rrrAndNetwork.h.

485 {
486 return vRefs[id];
487 }
Here is the caller graph for this function:

◆ GetNumInts()

int rrr::AndNetwork::GetNumInts ( ) const
inline

Definition at line 361 of file rrrAndNetwork.h.

361 {
362 return int_size(lInts);
363 }
Here is the caller graph for this function:

◆ GetNumLevels()

int rrr::AndNetwork::GetNumLevels ( ) const

Definition at line 369 of file rrrAndNetwork.h.

369 {
370 int nMaxLevel = 0;
371 std::vector<int> vLevels(nNodes);
372 ForEachInt([&](int id) {
373 ForEachFanin(id, [&](int fi) {
374 if(vLevels[id] < vLevels[fi]) {
375 vLevels[id] = vLevels[fi];
376 }
377 });
378 vLevels[id] += 1;
379 if(nMaxLevel < vLevels[id]) {
380 nMaxLevel = vLevels[id];
381 }
382 });
383 return nMaxLevel;
384 }
Here is the call graph for this function:

◆ GetNumNodes()

int rrr::AndNetwork::GetNumNodes ( ) const
inline

Definition at line 353 of file rrrAndNetwork.h.

353 {
354 return nNodes;
355 }

◆ GetNumPis()

int rrr::AndNetwork::GetNumPis ( ) const
inline

Definition at line 357 of file rrrAndNetwork.h.

357 {
358 return int_size(vPis);
359 }
Here is the caller graph for this function:

◆ GetNumPos()

int rrr::AndNetwork::GetNumPos ( ) const
inline

Definition at line 365 of file rrrAndNetwork.h.

365 {
366 return int_size(vPos);
367 }
Here is the caller graph for this function:

◆ GetPi()

int rrr::AndNetwork::GetPi ( int idx) const
inline

Definition at line 390 of file rrrAndNetwork.h.

390 {
391 return vPis[idx];
392 }
Here is the caller graph for this function:

◆ GetPiIndex()

int rrr::AndNetwork::GetPiIndex ( int id) const
inline

Definition at line 451 of file rrrAndNetwork.h.

451 {
452 assert(IsPi(id));
453 assert(check_int_size(vPis));
454 std::vector<int>::const_iterator it = std::find(vPis.begin(), vPis.end(), id);
455 assert(it != vPis.end());
456 return std::distance(vPis.begin(), it);
457 }
Here is the call graph for this function:

◆ GetPis()

std::vector< int > rrr::AndNetwork::GetPis ( ) const
inline

Definition at line 398 of file rrrAndNetwork.h.

398 {
399 return vPis;
400 }

◆ GetPisInts()

std::vector< int > rrr::AndNetwork::GetPisInts ( ) const
inline

Definition at line 406 of file rrrAndNetwork.h.

406 {
407 std::vector<int> vPisInts = vPis;
408 vPisInts.insert(vPisInts.end(), lInts.begin(), lInts.end());
409 return vPisInts;
410 }

◆ GetPo()

int rrr::AndNetwork::GetPo ( int idx) const
inline

Definition at line 394 of file rrrAndNetwork.h.

394 {
395 return vPos[idx];
396 }
Here is the caller graph for this function:

◆ GetPoIndex()

int rrr::AndNetwork::GetPoIndex ( int id) const
inline

Definition at line 473 of file rrrAndNetwork.h.

473 {
474 assert(IsPo(id));
475 assert(check_int_size(vPos));
476 std::vector<int>::const_iterator it = std::find(vPos.begin(), vPos.end(), id);
477 assert(it != vPos.end());
478 return std::distance(vPos.begin(), it);
479 }
Here is the call graph for this function:

◆ GetPos()

std::vector< int > rrr::AndNetwork::GetPos ( ) const
inline

Definition at line 412 of file rrrAndNetwork.h.

412 {
413 return vPos;
414 }

◆ Insert()

std::pair< std::vector< int >, std::vector< bool > > rrr::AndNetwork::Insert ( AndNetwork * pNtk,
std::vector< int > const & vInputs,
std::vector< bool > const & vCompls,
std::vector< int > const & vOutputs )

Definition at line 1440 of file rrrAndNetwork.h.

1440 {
1441 Reserve(nNodes + pNtk->GetNumInts());
1442 std::map<int, std::pair<int, bool>> m;
1443 m[pNtk->GetConst0()] = std::make_pair(GetConst0(), false);
1444 assert(pNtk->GetNumPis() == int_size(vInputs));
1445 assert(vInputs.size() == vCompls.size());
1446 for(int i = 0; i < pNtk->GetNumPis(); i++) {
1447 assert(IsInt(vInputs[i]) || IsPi(vInputs[i]));
1448 m[pNtk->GetPi(i)] = std::make_pair(vInputs[i], vCompls[i]);
1449 }
1450 pNtk->ForEachInt([&](int id) {
1451 int id2 = CreateNode();
1452 lInts.push_back(id2);
1453 sInts.insert(id2);
1454 vvFaninEdges[id2].resize(pNtk->GetNumFanins(id));
1455 pNtk->ForEachFaninIdx(id, [&](int idx, int fi, bool c) {
1456 assert(m.count(fi));
1457 vvFaninEdges[id2][idx] = Node2Edge(m[fi].first, c ^ m[fi].second);
1458 vRefs[m[fi].first]++;
1459 });
1460 m[id] = std::make_pair(id2, false);
1461 });
1462 assert(pNtk->GetNumPos() == int_size(vOutputs));
1463 std::vector<int> vNewOutputs(pNtk->GetNumPos());
1464 std::vector<bool> vNewCompls(pNtk->GetNumPos());
1465 for(int i = 0; i < pNtk->GetNumPos(); i++) {
1466 int id = vOutputs[i];
1467 int po = pNtk->GetPo(i);
1468 assert(m.count(pNtk->GetFanin(po, 0)));
1469 int fi = m[pNtk->GetFanin(po, 0)].first;
1470 bool c = pNtk->GetCompl(po, 0) ^ m[pNtk->GetFanin(po, 0)].second;
1471 assert(id != fi);
1472 vNewOutputs[i] = fi;
1473 vNewCompls[i] = c;
1474 // remove if substitution would lead to duplication with the same polarity
1475 ForEachFanoutRidx(id, false, [&](int fo, bool foc, int idx) {
1476 int idx2 = FindFanin(fo, fi);
1477 if(idx2 != -1 && GetCompl(fo, idx2) == (c ^ foc)) {
1478 RemoveFanin(fo, idx);
1479 }
1480 });
1481 ForEachFanoutRidx(id, true, [&](int fo, bool foc, int idx) {
1482 int idx2 = FindFanin(fo, fi);
1483 if(idx2 != -1) { // substitute with const-0 in case of duplication
1484 assert(GetCompl(fo, idx2) != (c ^ foc)); // of a different polarity
1485 vRefs[GetConst0()]++;
1486 vvFaninEdges[fo][idx] = Node2Edge(GetConst0(), 0);
1487 } else { // otherwise, substitute with fanin
1488 vvFaninEdges[fo][idx] = Node2Edge(fi, c ^ foc);
1489 vRefs[fi]++;
1490 // sort internal nodes
1491 itr it = std::find(lInts.begin(), lInts.end(), id);
1492 itr it2 = std::find(it, lInts.end(), fi);
1493 if(it2 != lInts.end()) {
1494 lInts.erase(it2);
1495 it2 = lInts.insert(it, fi);
1496 SortInts(it2);
1497 }
1498 }
1499 });
1500 vRefs[id] = 0;
1501 }
1502 Action action;
1503 action.type = INSERT;
1504 action.vFanins = vInputs;
1505 action.vFanouts = vOutputs;
1506 TakenAction(action);
1507 for(int id: vOutputs) {
1508 RemoveUnused(id, true);
1509 }
1510 return std::make_pair(std::move(vNewOutputs), std::move(vNewCompls));
1511 }
rrr::AndNetwork::RemoveUnused
void RemoveUnused(int id, bool fRecursive=false, bool fSweeping=false)
Definition rrrAndNetwork.h:1220
rrr::AndNetwork::RemoveFanin
void RemoveFanin(int id, int idx)
Definition rrrAndNetwork.h:1206
rrr::AndNetwork::Reserve
void Reserve(int nReserve)
Definition rrrAndNetwork.h:298
rrr::AndNetwork::ForEachFanoutRidx
void ForEachFanoutRidx(int id, bool fPos, Func const &func) const
Definition rrrAndNetwork.h:856
rrr::INSERT
@ INSERT
Definition rrrTypes.h:46
Here is the call graph for this function:

◆ IsInt()

bool rrr::AndNetwork::IsInt ( int id) const
inline

Definition at line 424 of file rrrAndNetwork.h.

424 {
425 return sInts.count(id);
426 }
Here is the caller graph for this function:

◆ IsPi()

bool rrr::AndNetwork::IsPi ( int id) const
inline

Definition at line 420 of file rrrAndNetwork.h.

420 {
421 return GetNumFanins(id) == 0 && std::find(vPis.begin(), vPis.end(), id) != vPis.end();
422 }
Here is the call graph for this function:
Here is the caller graph for this function:

◆ IsPo()

bool rrr::AndNetwork::IsPo ( int id) const
inline

Definition at line 428 of file rrrAndNetwork.h.

428 {
429 return GetNumFanouts(id) == 0 && std::find(vPos.begin(), vPos.end(), id) != vPos.end();
430 }
Here is the call graph for this function:
Here is the caller graph for this function:

◆ IsPoDriver()

bool rrr::AndNetwork::IsPoDriver ( int id) const
inline

Definition at line 442 of file rrrAndNetwork.h.

442 {
443 for(int po: vPos) {
444 if(GetFanin(po, 0) == id) {
445 return true;
446 }
447 }
448 return false;
449 }
Here is the call graph for this function:

◆ IsReachable()

template<template< typename... > typename Container, typename... Ts, template< typename... > typename Container2, typename... Ts2>
bool rrr::AndNetwork::IsReachable ( Container< Ts... > const & srcs,
Container2< Ts2... > const & dsts )
inline

Definition at line 585 of file rrrAndNetwork.h.

585 {
586 if(srcs.empty() || dsts.empty()) {
587 return false;
588 }
589 // mark destinations
590 unsigned iTravStart = StartTraversal(2);
591 for(int id: dsts) {
592 vTrav[id] = iTravStart;
593 }
594 // mark sources
595 for(int id: srcs) {
596 if(vTrav[id] == iTravStart) {
597 EndTraversal();
598 return true;
599 }
600 vTrav[id] = iTrav;
601 }
602 // find the first source
603 citr it = lInts.begin();
604 while(vTrav[*it] != iTrav && it != lInts.end()) {
605 it++;
606 }
607 // check if sources are reachable to destinations
608 for(; it != lInts.end(); it++) {
609 if(vTrav[*it] == iTrav) {
610 continue;
611 }
612 for(int fi_edge: vvFaninEdges[*it]) {
613 if(vTrav[Edge2Node(fi_edge)] == iTrav) {
614 if(vTrav[*it] == iTravStart) {
615 EndTraversal();
616 return true;
617 }
618 vTrav[*it] = iTrav;
619 break;
620 }
621 }
622 }
623 for(int po: vPos) {
624 if(vTrav[po] == iTrav) {
625 continue;
626 }
627 if(vTrav[GetFanin(po, 0)] == iTrav) {
628 if(vTrav[po] == iTravStart) {
629 EndTraversal();
630 return true;
631 }
632 vTrav[po] = iTrav;
633 }
634 }
635 EndTraversal();
636 return false;
637 }
Here is the call graph for this function:

◆ IsReconvergent()

bool rrr::AndNetwork::IsReconvergent ( int id)
inline

Definition at line 506 of file rrrAndNetwork.h.

506 {
507 if(GetNumFanouts(id) <= 1) {
508 return false;
509 }
510 unsigned iTravStart = StartTraversal(GetNumFanouts(id));
511 int idx = 0;
512 ForEachFanout(id, false, [&](int fo) {
513 vTrav[fo] = iTravStart + idx;
514 idx++;
515 });
516 if(idx <= 1) {
517 // less than two fanouts excluding POs
518 EndTraversal();
519 return false;
520 }
521 citr it = lInts.begin();
522 while(vTrav[*it] < iTravStart && it != lInts.end()) {
523 it++;
524 }
525 it++;
526 for(; it != lInts.end(); it++) {
527 for(int fi_edge: vvFaninEdges[*it]) {
528 int fi = Edge2Node(fi_edge);
529 if(vTrav[fi] >= iTravStart) {
530 if(vTrav[*it] >= iTravStart && vTrav[*it] != vTrav[fi]) {
531 EndTraversal();
532 return true;
533 }
534 vTrav[*it] = vTrav[fi];
535 }
536 }
537 }
538 EndTraversal();
539 return false;
540 }
Here is the call graph for this function:

◆ Load()

void rrr::AndNetwork::Load ( int slot)

Definition at line 1585 of file rrrAndNetwork.h.

1585 {
1586 assert(slot >= 0);
1587 assert(slot < int_size(vBackups));
1588 Action action;
1589 action.type = LOAD;
1590 action.idx = slot;
1591 *this = vBackups[slot];
1592 TakenAction(action);
1593 }
rrr::LOAD
@ LOAD
Definition rrrTypes.h:44

◆ operator=()

AndNetwork & rrr::AndNetwork::operator= ( AndNetwork const & x)

Definition at line 261 of file rrrAndNetwork.h.

261 {
262 nNodes = x.nNodes;
263 vPis = x.vPis;
264 lInts = x.lInts;
265 sInts = x.sInts;
266 vPos = x.vPos;
267 vvFaninEdges = x.vvFaninEdges;
268 vRefs = x.vRefs;
269 return *this;
270 }
Here is the call graph for this function:

◆ PopBack()

void rrr::AndNetwork::PopBack ( )

Definition at line 1595 of file rrrAndNetwork.h.

1595 {
1596 assert(!vBackups.empty());
1597 Action action;
1598 action.type = POP_BACK;
1599 action.idx = int_size(vBackups) - 1;
1600 vBackups.pop_back();
1601 TakenAction(action);
1602 }
rrr::POP_BACK
@ POP_BACK
Definition rrrTypes.h:45

◆ Print()

void rrr::AndNetwork::Print ( ) const

Definition at line 1612 of file rrrAndNetwork.h.

1612 {
1613 std::cout << "inputs: " << vPis << std::endl;
1614 ForEachInt([&](int id) {
1615 std::cout << "node " << id << ": ";
1616 PrintComplementedEdges(std::bind(&AndNetwork::ForEachFanin<std::function<void(int, bool)>>, this, id, std::placeholders::_1));
1617 std::cout << " (ref = " << vRefs[id] << ")";
1618 std::cout << std::endl;
1619 });
1620 std::cout << "outputs: ";
1621 PrintComplementedEdges(std::bind(&AndNetwork::ForEachPoDriver<std::function<void(int, bool)>>, this, std::placeholders::_1));
1622 std::cout << std::endl;
1623 }
rrr::AndNetwork::ForEachPoDriver
void ForEachPoDriver(Func const &func) const
Definition rrrAndNetwork.h:778
rrr::PrintComplementedEdges
void PrintComplementedEdges(std::function< void(std::function< void(int, bool)> const &)> const &ForEachEdge)
Definition rrrUtils.h:85
Here is the call graph for this function:

◆ Propagate()

void rrr::AndNetwork::Propagate ( int id = -1)

Definition at line 1517 of file rrrAndNetwork.h.

1517 {
1518 StartTraversal();
1519 itr it;
1520 if(id == -1) {
1521 ForEachInt([&](int id) {
1522 if(GetNumFanins(id) <= 1 || FindFanin(id, GetConst0()) != -1) {
1523 vTrav[id] = iTrav;
1524 }
1525 });
1526 it = lInts.begin();
1527 while(vTrav[*it] != iTrav && it != lInts.end()) {
1528 it++;
1529 }
1530 } else {
1531 vTrav[id] = iTrav;
1532 it = std::find(lInts.begin(), lInts.end(), id);
1533 }
1534 fPropagating = true;
1535 while(it != lInts.end()) {
1536 if(vTrav[*it] == iTrav) {
1537 if(GetNumFanins(*it) == 1) {
1538 RemoveBuffer(*it);
1539 } else {
1540 RemoveConst(*it);
1541 }
1542 it = lInts.erase(it);
1543 } else {
1544 it++;
1545 }
1546 }
1547 fPropagating = false;
1548 EndTraversal();
1549 }
rrr::AndNetwork::RemoveConst
void RemoveConst(int id)
Definition rrrAndNetwork.h:1298
rrr::AndNetwork::RemoveBuffer
void RemoveBuffer(int id)
Definition rrrAndNetwork.h:1245
Here is the call graph for this function:
Here is the caller graph for this function:

◆ Read()

template<typename Ntk, typename Reader>
void rrr::AndNetwork::Read ( Ntk * pFrom,
Reader & reader,
bool fNew = true )

Definition at line 336 of file rrrAndNetwork.h.

336 {
337 Clear(false);
338 reader(pFrom, this);
339 Action action;
340 action.type = READ;
341 action.fNew = fNew;
342 TakenAction(action);
343 }
rrr::AndNetwork::Clear
void Clear(bool fClearCallbacks=true)
Definition rrrAndNetwork.h:276
rrr::READ
@ READ
Definition rrrTypes.h:42
Here is the call graph for this function:
Here is the caller graph for this function:

◆ RemoveBuffer()

void rrr::AndNetwork::RemoveBuffer ( int id)

Definition at line 1245 of file rrrAndNetwork.h.

1245 {
1246 assert(GetNumFanins(id) == 1);
1247 assert(!fPropagating || fLockTrav);
1248 int fi = GetFanin(id, 0);
1249 bool c = GetCompl(id, 0);
1250 // check if it is buffering constant
1251 if(fi == GetConst0()) {
1252 RemoveConst(id);
1253 return;
1254 }
1255 // remove if substitution would lead to duplication with the same polarity
1256 ForEachFanoutRidx(id, false, [&](int fo, bool foc, int idx) {
1257 int idx2 = FindFanin(fo, fi);
1258 if(idx2 != -1 && GetCompl(fo, idx2) == (c ^ foc)) {
1259 RemoveFanin(fo, idx);
1260 if(fPropagating && GetNumFanins(fo) == 1) {
1261 vTrav[fo] = iTrav;
1262 }
1263 }
1264 });
1265 // substitute node with fanin or const-0
1266 Action action;
1267 action.type = REMOVE_BUFFER;
1268 action.id = id;
1269 action.fi = fi;
1270 action.c = c;
1271 ForEachFanoutRidx(id, true, [&](int fo, bool foc, int idx) {
1272 action.vFanouts.push_back(fo);
1273 int idx2 = FindFanin(fo, fi);
1274 if(idx2 != -1) { // substitute with const-0 in case of duplication
1275 assert(GetCompl(fo, idx2) != (c ^ foc)); // of a different polarity
1276 vRefs[GetConst0()]++;
1277 vvFaninEdges[fo][idx] = Node2Edge(GetConst0(), 0);
1278 if(fPropagating) {
1279 vTrav[fo] = iTrav;
1280 }
1281 } else { // otherwise, substitute with fanin
1282 vvFaninEdges[fo][idx] = Node2Edge(fi, c ^ foc);
1283 vRefs[fi]++;
1284 }
1285 });
1286 // remove node
1287 vRefs[id] = 0;
1288 vRefs[fi]--;
1289 vvFaninEdges[id].clear();
1290 if(!fPropagating) {
1291 itr it = std::find(lInts.begin(), lInts.end(), id);
1292 lInts.erase(it);
1293 }
1294 sInts.erase(id);
1295 TakenAction(action);
1296 }
rrr::REMOVE_BUFFER
@ REMOVE_BUFFER
Definition rrrTypes.h:36
Here is the call graph for this function:
Here is the caller graph for this function:

◆ RemoveConst()

void rrr::AndNetwork::RemoveConst ( int id)

Definition at line 1298 of file rrrAndNetwork.h.

1298 {
1299 assert(GetNumFanins(id) == 0 || FindFanin(id, GetConst0()) != -1);
1300 assert(!fPropagating || fLockTrav);
1301 bool c = (GetNumFanins(id) == 0);
1302 // just remove immediately if polarity is true but not PO
1303 ForEachFanoutRidx(id, false, [&](int fo, bool foc, int idx) {
1304 if(c ^ foc) {
1305 assert(!IsPo(fo));
1306 RemoveFanin(fo, idx);
1307 if(fPropagating && GetNumFanins(fo) <= 1) {
1308 vTrav[fo] = iTrav;
1309 }
1310 }
1311 });
1312 // substitute with constant
1313 Action action;
1314 action.type = REMOVE_CONST;
1315 action.id = id;
1316 ForEachFanoutRidx(id, true, [&](int fo, bool foc, int idx) {
1317 action.vFanouts.push_back(fo);
1318 vRefs[GetConst0()]++;
1319 vvFaninEdges[fo][idx] = Node2Edge(GetConst0(), c ^ foc);
1320 if(fPropagating) {
1321 vTrav[fo] = iTrav;
1322 }
1323 });
1324 // remove node
1325 vRefs[id] = 0;
1326 ForEachFanin(id, [&](int fi) {
1327 vRefs[fi]--;
1328 action.vFanins.push_back(fi);
1329 });
1330 vvFaninEdges[id].clear();
1331 if(!fPropagating) {
1332 itr it = std::find(lInts.begin(), lInts.end(), id);
1333 lInts.erase(it);
1334 }
1335 sInts.erase(id);
1336 TakenAction(action);
1337 }
rrr::REMOVE_CONST
@ REMOVE_CONST
Definition rrrTypes.h:37
Here is the call graph for this function:
Here is the caller graph for this function:

◆ RemoveFanin()

void rrr::AndNetwork::RemoveFanin ( int id,
int idx )

Definition at line 1206 of file rrrAndNetwork.h.

1206 {
1207 Action action;
1208 action.type = REMOVE_FANIN;
1209 action.id = id;
1210 action.idx = idx;
1211 int fi = GetFanin(id, idx);
1212 bool c = GetCompl(id, idx);
1213 action.fi = fi;
1214 action.c = c;
1215 vRefs[fi]--;
1216 vvFaninEdges[id].erase(vvFaninEdges[id].begin() + idx);
1217 TakenAction(action);
1218 }
rrr::REMOVE_FANIN
@ REMOVE_FANIN
Definition rrrTypes.h:34
Here is the call graph for this function:
Here is the caller graph for this function:

◆ RemoveUnused()

void rrr::AndNetwork::RemoveUnused ( int id,
bool fRecursive = false,
bool fSweeping = false )

Definition at line 1220 of file rrrAndNetwork.h.

1220 {
1221 assert(vRefs[id] == 0);
1222 Action action;
1223 action.type = REMOVE_UNUSED;
1224 action.id = id;
1225 ForEachFanin(id, [&](int fi) {
1226 action.vFanins.push_back(fi);
1227 vRefs[fi]--;
1228 });
1229 vvFaninEdges[id].clear();
1230 if(!fSweeping) {
1231 itr it = std::find(lInts.begin(), lInts.end(), id);
1232 lInts.erase(it);
1233 }
1234 sInts.erase(id);
1235 TakenAction(action);
1236 if(fRecursive) {
1237 for(int fi: action.vFanins) {
1238 if(vRefs[fi] == 0 && IsInt(fi)) {
1239 RemoveUnused(fi, fRecursive, fSweeping);
1240 }
1241 }
1242 }
1243 }
rrr::REMOVE_UNUSED
@ REMOVE_UNUSED
Definition rrrTypes.h:35
Here is the call graph for this function:
Here is the caller graph for this function:

◆ Reserve()

void rrr::AndNetwork::Reserve ( int nReserve)

Definition at line 298 of file rrrAndNetwork.h.

298 {
299 vvFaninEdges.reserve(nReserve);
300 vRefs.reserve(nReserve);
301 }
Here is the caller graph for this function:

◆ Save()

int rrr::AndNetwork::Save ( int slot = -1)

Definition at line 1569 of file rrrAndNetwork.h.

1569 {
1570 Action action;
1571 action.type = SAVE;
1572 if(slot < 0) {
1573 slot = int_size(vBackups);
1574 vBackups.push_back(*this);
1575 assert(check_int_size(vBackups));
1576 } else {
1577 assert(slot < int_size(vBackups));
1578 vBackups[slot] = *this;
1579 }
1580 action.idx = slot;
1581 TakenAction(action);
1582 return slot;
1583 }
rrr::SAVE
@ SAVE
Definition rrrTypes.h:43

◆ SortFanins()

template<typename Func>
void rrr::AndNetwork::SortFanins ( int id,
Func const & cost )

Definition at line 1416 of file rrrAndNetwork.h.

1416 {
1417 static_assert(is_invokable<Func, int, int>::value || is_invokable<Func, int, bool, int, bool>::value, "fanin cost function format error");
1418 std::vector<int> vFaninEdges = vvFaninEdges[id];
1419 std::sort(vvFaninEdges[id].begin(), vvFaninEdges[id].end(), [&](int i, int j) {
1420 if constexpr(is_invokable<Func, int, int>::value) {
1421 return comp(Edge2Node(i), Edge2Node(j));
1422 } else if constexpr(is_invokable<Func, int, bool, int, bool>::value) {
1423 return comp(Edge2Node(i), EdgeIsCompl(i), Edge2Node(j), EdgeIsCompl(j));
1424 }
1425 });
1426 if(vFaninEdges == vvFaninEdges[id]) {
1427 return;
1428 }
1429 Action action;
1430 action.type = SORT_FANINS;
1431 action.id = id;
1432 assert(check_int_size(vFaninEdges));
1433 for(int fanin_edge: vvFaninEdges[id]) {
1434 std::vector<int>::const_iterator it = std::find(vFaninEdges.begin(), vFaninEdges.end(), fanin_edge);
1435 action.vIndices.push_back(std::distance(vFaninEdges.cbegin(), it));
1436 }
1437 TakenAction(action);
1438 }
rrr::SORT_FANINS
@ SORT_FANINS
Definition rrrTypes.h:41

◆ Sweep()

void rrr::AndNetwork::Sweep ( bool fPropagate = true)

Definition at line 1551 of file rrrAndNetwork.h.

1551 {
1552 if(fPropagate) {
1553 Propagate();
1554 }
1555 for(ritr it = lInts.rbegin(); it != lInts.rend();) {
1556 if(vRefs[*it] == 0) {
1557 RemoveUnused(*it, false, true);
1558 it = ritr(lInts.erase(--it.base()));
1559 } else {
1560 it++;
1561 }
1562 }
1563 }
rrr::AndNetwork::Propagate
void Propagate(int id=-1)
Definition rrrAndNetwork.h:1517
Here is the call graph for this function:

◆ TrivialCollapse()

void rrr::AndNetwork::TrivialCollapse ( int id)

Definition at line 1360 of file rrrAndNetwork.h.

1360 {
1361 for(int idx = 0; idx < GetNumFanins(id);) {
1362 int fi_edge = vvFaninEdges[id][idx];
1363 int fi = Edge2Node(fi_edge);
1364 bool c = EdgeIsCompl(fi_edge);
1365 if(!IsPi(fi) && !c && vRefs[fi] == 1) {
1366 Action action;
1367 action.type = TRIVIAL_COLLAPSE;
1368 action.id = id;
1369 action.idx = idx;
1370 action.fi = fi;
1371 action.c = c;
1372 std::vector<int>::iterator it = vvFaninEdges[id].begin() + idx;
1373 it = vvFaninEdges[id].erase(it);
1374 vvFaninEdges[id].insert(it, vvFaninEdges[fi].begin(), vvFaninEdges[fi].end());
1375 ForEachFanin(fi, [&](int fi) {
1376 action.vFanins.push_back(fi);
1377 });
1378 // remove collapsed fanin
1379 vRefs[fi] = 0;
1380 vvFaninEdges[fi].clear();
1381 lInts.erase(std::find(lInts.begin(), lInts.end(), fi));
1382 sInts.erase(fi);
1383 TakenAction(action);
1384 } else {
1385 idx++;
1386 }
1387 }
1388 }
rrr::TRIVIAL_COLLAPSE
@ TRIVIAL_COLLAPSE
Definition rrrTypes.h:39
Here is the call graph for this function:

◆ TrivialDecompose()

void rrr::AndNetwork::TrivialDecompose ( int id)

Definition at line 1390 of file rrrAndNetwork.h.

1390 {
1391 while(GetNumFanins(id) > 2) {
1392 Action action;
1393 action.type = TRIVIAL_DECOMPOSE;
1394 action.id = id;
1395 action.idx = GetNumFanins(id) - 2;
1396 int new_fi = CreateNode();
1397 action.fi = new_fi;
1398 int fi_edge1 = vvFaninEdges[id].back();
1399 vvFaninEdges[id].pop_back();
1400 int fi_edge0 = vvFaninEdges[id].back();
1401 vvFaninEdges[id].pop_back();
1402 vvFaninEdges[new_fi].push_back(fi_edge0);
1403 action.vFanins.push_back(Edge2Node(fi_edge0));
1404 vvFaninEdges[new_fi].push_back(fi_edge1);
1405 action.vFanins.push_back(Edge2Node(fi_edge1));
1406 vvFaninEdges[id].push_back(Node2Edge(new_fi, false));
1407 vRefs[new_fi]++;
1408 itr it = std::find(lInts.begin(), lInts.end(), id);
1409 lInts.insert(it, new_fi);
1410 sInts.insert(new_fi);
1411 TakenAction(action);
1412 }
1413 }
rrr::TRIVIAL_DECOMPOSE
@ TRIVIAL_DECOMPOSE
Definition rrrTypes.h:40
Here is the call graph for this function:

◆ UseComplementedEdges()

bool rrr::AndNetwork::UseComplementedEdges ( ) const
inline

Definition at line 349 of file rrrAndNetwork.h.

349 {
350 return true;
351 }
The documentation for this class was generated from the following file: