2 * yosys -- Yosys Open SYnthesis Suite
4 * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at>
6 * Permission to use, copy, modify, and/or distribute this software for any
7 * purpose with or without fee is hereby granted, provided that the above
8 * copyright notice and this permission notice appear in all copies.
10 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
11 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
12 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
13 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
14 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
15 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
20 // This file contains various c++ utility routines and helper classes that
21 // do not depend on any other components of yosys (except stuff like log_*).
23 #include "kernel/yosys.h"
30 // ------------------------------------------------
31 // A map-like container, but you can save and restore the state
32 // ------------------------------------------------
34 template<typename Key
, typename T
, typename OPS
= hash_ops
<Key
>>
38 std::vector
<dict
<Key
, T
*, OPS
>> backup_state
;
39 dict
<Key
, T
, OPS
> current_state
;
44 stackmap(const dict
<Key
, T
, OPS
> &other
) : current_state(other
) { }
46 template<typename Other
>
47 void operator=(const Other
&other
)
49 for (auto &it
: current_state
)
50 if (!backup_state
.empty() && backup_state
.back().count(it
.first
) == 0)
51 backup_state
.back()[it
.first
] = new T(it
.second
);
52 current_state
.clear();
54 for (auto &it
: other
)
55 set(it
.first
, it
.second
);
58 bool has(const Key
&k
)
60 return current_state
.count(k
) != 0;
63 void set(const Key
&k
, const T
&v
)
65 if (!backup_state
.empty() && backup_state
.back().count(k
) == 0)
66 backup_state
.back()[k
] = current_state
.count(k
) ? new T(current_state
.at(k
)) : nullptr;
70 void unset(const Key
&k
)
72 if (!backup_state
.empty() && backup_state
.back().count(k
) == 0)
73 backup_state
.back()[k
] = current_state
.count(k
) ? new T(current_state
.at(k
)) : nullptr;
74 current_state
.erase(k
);
77 const T
&get(const Key
&k
)
79 if (current_state
.count(k
) == 0)
81 return current_state
.at(k
);
84 void reset(const Key
&k
)
86 for (int i
= GetSize(backup_state
)-1; i
>= 0; i
--)
87 if (backup_state
[i
].count(k
) != 0) {
88 if (backup_state
[i
].at(k
) == nullptr)
89 current_state
.erase(k
);
91 current_state
[k
] = *backup_state
[i
].at(k
);
94 current_state
.erase(k
);
97 const dict
<Key
, T
, OPS
> &stdmap()
104 backup_state
.resize(backup_state
.size()+1);
109 log_assert(!backup_state
.empty());
110 for (auto &it
: backup_state
.back())
111 if (it
.second
!= nullptr) {
112 current_state
[it
.first
] = *it
.second
;
115 current_state
.erase(it
.first
);
116 backup_state
.pop_back();
121 while (!backup_state
.empty())
127 // ------------------------------------------------
128 // A simple class for topological sorting
129 // ------------------------------------------------
131 template<typename T
, typename C
= std::less
<T
>>
134 bool analyze_loops
, found_loops
;
135 std::map
<T
, std::set
<T
, C
>, C
> database
;
136 std::set
<std::set
<T
, C
>> loops
;
137 std::vector
<T
> sorted
;
141 analyze_loops
= true;
147 if (database
.count(n
) == 0)
148 database
[n
] = std::set
<T
, C
>();
151 void edge(T left
, T right
)
154 database
[right
].insert(left
);
157 void sort_worker(const T
&n
, std::set
<T
, C
> &marked_cells
, std::set
<T
, C
> &active_cells
, std::vector
<T
> &active_stack
)
159 if (active_cells
.count(n
)) {
163 for (int i
= GetSize(active_stack
)-1; i
>= 0; i
--) {
164 loop
.insert(active_stack
[i
]);
165 if (active_stack
[i
] == n
)
173 if (marked_cells
.count(n
))
176 if (!database
.at(n
).empty())
179 active_stack
.push_back(n
);
180 active_cells
.insert(n
);
182 for (auto &left_n
: database
.at(n
))
183 sort_worker(left_n
, marked_cells
, active_cells
, active_stack
);
186 active_stack
.pop_back();
187 active_cells
.erase(n
);
190 marked_cells
.insert(n
);
200 std::set
<T
, C
> marked_cells
;
201 std::set
<T
, C
> active_cells
;
202 std::vector
<T
> active_stack
;
204 for (auto &it
: database
)
205 sort_worker(it
.first
, marked_cells
, active_cells
, active_stack
);
207 log_assert(GetSize(sorted
) == GetSize(database
));