projects / yosys.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
history | raw | HEAD
Add first draft of simple C back-end
[yosys.git] / backends / simplec / simplec.cc
1 /*
2 * yosys -- Yosys Open SYnthesis Suite
3 *
4 * Copyright (C) 2012 Clifford Wolf <clifford@clifford.at>
5 *
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.
9 *
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.
17 *
18 */
19
20 #include "kernel/yosys.h"
21 #include "kernel/sigtools.h"
22
23 USING_YOSYS_NAMESPACE
24 PRIVATE_NAMESPACE_BEGIN
25
26 struct HierDirtyFlags;
27
28 struct HierDirtyFlags
29 {
30 int dirty;
31 Module *module;
32 IdString hiername;
33 HierDirtyFlags *parent;
34 pool<SigBit> dirty_bits;
35 pool<Cell*> dirty_cells;
36 dict<IdString, HierDirtyFlags*> children;
37
38 HierDirtyFlags(Module *module, IdString hiername, HierDirtyFlags *parent) : dirty(0), module(module), hiername(hiername), parent(parent)
39 {
40 for (Cell *cell : module->cells()) {
41 Module *mod = module->design->module(cell->type);
42 if (mod) children[cell->name] = new HierDirtyFlags(mod, cell->name, this);
43 }
44 }
45
46 ~HierDirtyFlags()
47 {
48 for (auto &child : children)
49 delete child.second;
50 }
51
52 void set_dirty(SigBit bit)
53 {
54 if (dirty_bits.count(bit))
55 return;
56
57 dirty_bits.insert(bit);
58
59 HierDirtyFlags *p = this;
60 while (p != nullptr) {
61 p->dirty++;
62 p = p->parent;
63 }
64 }
65
66 void unset_dirty(SigBit bit)
67 {
68 if (dirty_bits.count(bit) == 0)
69 return;
70
71 dirty_bits.erase(bit);
72
73 HierDirtyFlags *p = this;
74 while (p != nullptr) {
75 p->dirty--;
76 log_assert(p->dirty >= 0);
77 p = p->parent;
78 }
79 }
80
81 void set_dirty(Cell *cell)
82 {
83 if (dirty_cells.count(cell))
84 return;
85
86 dirty_cells.insert(cell);
87
88 HierDirtyFlags *p = this;
89 while (p != nullptr) {
90 p->dirty++;
91 p = p->parent;
92 }
93 }
94
95 void unset_dirty(Cell *cell)
96 {
97 if (dirty_cells.count(cell) == 0)
98 return;
99
100 dirty_cells.erase(cell);
101
102 HierDirtyFlags *p = this;
103 while (p != nullptr) {
104 p->dirty--;
105 log_assert(p->dirty >= 0);
106 p = p->parent;
107 }
108 }
109 };
110
111 struct SimplecWorker
112 {
113 bool verbose = false;
114 int max_uintsize = 32;
115
116 Design *design;
117 dict<Module*, SigMap> sigmaps;
118 HierDirtyFlags *dirty_flags = nullptr;
119
120 vector<string> signal_declarations;
121 pool<int> generated_sigtypes;
122
123 vector<string> util_declarations;
124 pool<string> generated_utils;
125
126 vector<string> struct_declarations;
127 pool<IdString> generated_structs;
128
129 vector<string> funct_declarations;
130
131 pool<string> reserved_cids;
132 dict<IdString, string> id2cid;
133
134 dict<Module*, dict<SigBit, pool<tuple<Cell*, IdString, int>>>> bit2cell;
135 dict<Module*, dict<SigBit, pool<SigBit>>> bit2output;
136
137 SimplecWorker(Design *design) : design(design)
138 {
139 }
140
141 string sigtype(int n)
142 {
143 string struct_name = stringf("signal%d_t", n);
144
145 if (generated_sigtypes.count(n) == 0)
146 {
147 signal_declarations.push_back("");
148 signal_declarations.push_back(stringf("#ifndef YOSYS_SIMPLEC_SIGNAL%d_T", n));
149 signal_declarations.push_back(stringf("#define YOSYS_SIMPLEC_SIGNAL%d_T", n));
150 signal_declarations.push_back(stringf("typedef struct {"));
151
152 for (int k = 8; k <= max_uintsize; k = 2*k)
153 if (n <= k && k <= max_uintsize) {
154 signal_declarations.push_back(stringf(" uint%d_t value_%d_0 : %d;", k, n-1, n));
155 goto end_struct;
156 }
157
158 for (int k = 0; k < n; k += max_uintsize) {
159 int bits = std::min(max_uintsize, n-k);
160 signal_declarations.push_back(stringf(" uint%d_t value_%d_%d : %d;", max_uintsize, k+bits-1, k, bits));
161 }
162
163 end_struct:
164 signal_declarations.push_back(stringf("} signal%d_t;", n));
165 signal_declarations.push_back(stringf("#endif"));
166 generated_sigtypes.insert(n);
167 }
168
169 return struct_name;
170 }
171
172 void util_ifdef_guard(string s)
173 {
174 for (int i = 0; i < GetSize(s); i++)
175 if ('a' <= s[i] && s[i] <= 'z')
176 s[i] -= 'a' - 'A';
177
178 util_declarations.push_back(stringf("#ifndef %s", s.c_str()));
179 util_declarations.push_back(stringf("#define %s", s.c_str()));
180 }
181
182 string util_get_bit(int n, int idx)
183 {
184 string util_name = stringf("yosys_simplec_get_bit_%d_of_%d", idx, n);
185
186 if (generated_utils.count(util_name) == 0)
187 {
188 util_ifdef_guard(util_name);
189 util_declarations.push_back(stringf("bool %s(const %s *sig)", util_name.c_str(), sigtype(n).c_str()));
190 util_declarations.push_back(stringf("{"));
191
192 int word_idx = idx / max_uintsize, word_offset = idx % max_uintsize;
193 string value_name = stringf("value_%d_%d", std::min(n-1, (word_idx+1)*max_uintsize-1), word_idx*max_uintsize);
194
195 util_declarations.push_back(stringf(" return (sig->%s >> %d) & 1;", value_name.c_str(), word_offset));
196
197 util_declarations.push_back(stringf("}"));
198 util_declarations.push_back(stringf("#endif"));
199 generated_utils.insert(util_name);
200 }
201
202 return util_name;
203 }
204
205 string util_set_bit(int n, int idx)
206 {
207 string util_name = stringf("yosys_simplec_set_bit_%d_of_%d", idx, n);
208
209 if (generated_utils.count(util_name) == 0)
210 {
211 util_ifdef_guard(util_name);
212 util_declarations.push_back(stringf("void %s(%s *sig, bool value)", util_name.c_str(), sigtype(n).c_str()));
213 util_declarations.push_back(stringf("{"));
214
215 int word_idx = idx / max_uintsize, word_offset = idx % max_uintsize;
216 string value_name = stringf("value_%d_%d", std::min(n-1, (word_idx+1)*max_uintsize-1), word_idx*max_uintsize);
217
218 util_declarations.push_back(stringf(" if (value)"));
219 util_declarations.push_back(stringf(" sig->%s |= 1UL << %d;", value_name.c_str(), word_offset));
220 util_declarations.push_back(stringf(" else"));
221 util_declarations.push_back(stringf(" sig->%s &= ~(1UL << %d);", value_name.c_str(), word_offset));
222
223 util_declarations.push_back(stringf("}"));
224 util_declarations.push_back(stringf("#endif"));
225 generated_utils.insert(util_name);
226 }
227
228 return util_name;
229 }
230
231 string cid(IdString id)
232 {
233 if (id2cid.count(id) == 0)
234 {
235 string s = id.str();
236 if (GetSize(s) < 2) log_abort();
237
238 if (s[0] == '\\')
239 s = s.substr(1);
240
241 if ('0' <= s[0] && s[0] <= '9') {
242 s = "_" + s;
243 }
244
245 for (int i = 0; i < GetSize(s); i++) {
246 if ('0' <= s[i] && s[i] <= '9') continue;
247 if ('A' <= s[i] && s[i] <= 'Z') continue;
248 if ('a' <= s[i] && s[i] <= 'z') continue;
249 s[i] = '_';
250 }
251
252 while (reserved_cids.count(s))
253 s += "_";
254
255 reserved_cids.insert(s);
256 id2cid[id] = s;
257 }
258
259 return id2cid.at(id);
260 }
261
262 void create_module_struct(Module *mod)
263 {
264 if (generated_structs.count(mod->name))
265 return;
266
267 generated_structs.insert(mod->name);
268 sigmaps[mod].set(mod);
269
270 for (Wire *w : mod->wires())
271 {
272 if (w->port_output)
273 for (auto bit : SigSpec(w))
274 bit2output[mod][sigmaps.at(mod)(bit)].insert(bit);
275 }
276
277 for (Cell *c : mod->cells())
278 {
279 for (auto &conn : c->connections())
280 {
281 if (!c->input(conn.first))
282 continue;
283
284 int idx = 0;
285 for (auto bit : sigmaps.at(mod)(conn.second))
286 bit2cell[mod][bit].insert(tuple<Cell*, IdString, int>(c, conn.first, idx++));
287 }
288
289 if (design->module(c->type))
290 create_module_struct(design->module(c->type));
291 }
292
293 struct_declarations.push_back("");
294 struct_declarations.push_back(stringf("struct %s_state_t {", cid(mod->name).c_str()));
295
296 for (Wire *w : mod->wires())
297 struct_declarations.push_back(stringf(" %s %s; // %s", sigtype(w->width).c_str(), cid(w->name).c_str(), log_id(w)));
298
299 for (Cell *c : mod->cells())
300 if (design->module(c->type))
301 struct_declarations.push_back(stringf(" struct %s_state_t %s; // %s", cid(c->type).c_str(), cid(c->name).c_str(), log_id(c)));
302
303 struct_declarations.push_back(stringf("};"));
304 }
305
306 void eval_cell(HierDirtyFlags *work, string &prefix, string &/* log_prefix */, Cell *cell)
307 {
308 if (cell->type.in("$_AND_", "$_NAND_", "$_OR_", "$_NOR_", "$_XOR_", "$_XNOR"))
309 {
310 SigBit a = sigmaps.at(work->module)(cell->getPort("\\A"));
311 SigBit b = sigmaps.at(work->module)(cell->getPort("\\B"));
312 SigBit y = sigmaps.at(work->module)(cell->getPort("\\Y"));
313
314 string a_expr = a.wire ? stringf("%s(&%s)", util_get_bit(a.wire->width, a.offset).c_str(), (prefix + cid(a.wire->name)).c_str()) : a.data ? "1" : "0";
315 string b_expr = b.wire ? stringf("%s(&%s)", util_get_bit(b.wire->width, b.offset).c_str(), (prefix + cid(b.wire->name)).c_str()) : b.data ? "1" : "0";
316 string expr;
317
318 if (cell->type == "$_AND_") expr = stringf("%s & %s", a_expr.c_str(), b_expr.c_str());
319 if (cell->type == "$_NAND_") expr = stringf("!(%s & %s)", a_expr.c_str(), b_expr.c_str());
320 if (cell->type == "$_OR_") expr = stringf("%s | %s", a_expr.c_str(), b_expr.c_str());
321 if (cell->type == "$_NOR_") expr = stringf("!(%s | %s)", a_expr.c_str(), b_expr.c_str());
322 if (cell->type == "$_XOR_") expr = stringf("%s ^ %s", a_expr.c_str(), b_expr.c_str());
323 if (cell->type == "$_XNOR_") expr = stringf("!(%s ^ %s)", a_expr.c_str(), b_expr.c_str());
324
325 log_assert(y.wire);
326 funct_declarations.push_back(stringf(" %s(&%s, %s); // %s (%s)", util_set_bit(y.wire->width, y.offset).c_str(),
327 (prefix + cid(y.wire->name)).c_str(), expr.c_str(), log_id(cell), log_id(cell->type)));
328
329 work->set_dirty(y);
330 return;
331 }
332
333 log_error("No C model for %s available at the moment (FIXME).\n", log_id(cell->type));
334 }
335
336 void eval_dirty(HierDirtyFlags *work, string prefix, string log_prefix, string parent_prefix)
337 {
338 while (work->dirty)
339 {
340 while (!work->dirty_bits.empty() || !work->dirty_cells.empty())
341 {
342 if (!work->dirty_bits.empty())
343 {
344 SigSpec dirtysig(work->dirty_bits);
345 dirtysig.sort_and_unify();
346
347 for (SigChunk chunk : dirtysig.chunks())
348 funct_declarations.push_back(stringf(" // New dirty bits in %s: %s", log_prefix.c_str(), log_signal(chunk)));
349
350 for (SigBit bit : dirtysig)
351 {
352 if (bit2output[work->module].count(bit) && work->parent)
353 for (auto outbit : bit2output[work->module][bit])
354 {
355 Module *parent_mod = work->parent->module;
356 Cell *parent_cell = parent_mod->cell(work->hiername);
357
358 IdString port_name = outbit.wire->name;
359 int port_offset = outbit.offset;
360 SigBit parent_bit = sigmaps.at(parent_mod)(parent_cell->getPort(port_name)[port_offset]);
361
362 log_assert(bit.wire && parent_bit.wire);
363 funct_declarations.push_back(stringf(" %s(&%s, %s(&%s));",
364 util_set_bit(parent_bit.wire->width, parent_bit.offset).c_str(),
365 (parent_prefix + cid(parent_bit.wire->name)).c_str(),
366 util_get_bit(bit.wire->width, bit.offset).c_str(),
367 (prefix + cid(bit.wire->name)).c_str()));
368 work->parent->set_dirty(parent_bit);
369 }
370
371 for (auto &port : bit2cell[work->module][bit])
372 {
373 if (work->children.count(std::get<0>(port)->name)) {
374 HierDirtyFlags *child = work->children.at(std::get<0>(port)->name);
375 SigBit child_bit = sigmaps.at(child->module)(SigBit(child->module->wire(std::get<1>(port)), std::get<2>(port)));
376 log_assert(bit.wire && child_bit.wire);
377 funct_declarations.push_back(stringf(" %s(&%s, %s(&%s));",
378 util_set_bit(child_bit.wire->width, child_bit.offset).c_str(),
379 (prefix + cid(child->hiername) + "." + cid(child_bit.wire->name)).c_str(),
380 util_get_bit(bit.wire->width, bit.offset).c_str(),
381 (prefix + cid(bit.wire->name)).c_str()));
382 child->set_dirty(child_bit);
383 } else {
384 work->set_dirty(std::get<0>(port));
385 }
386 }
387 work->unset_dirty(bit);
388 }
389 }
390
391 if (!work->dirty_cells.empty())
392 {
393 Cell *cell = *work->dirty_cells.begin();
394 eval_cell(work, prefix, log_prefix, cell);
395 work->unset_dirty(cell);
396 }
397 }
398
399 for (auto &child : work->children)
400 eval_dirty(child.second, prefix + cid(child.first) + ".", log_prefix + "." + cid(child.first), prefix);
401 }
402 }
403
404 void run(Module *mod)
405 {
406 create_module_struct(mod);
407
408 dirty_flags = new HierDirtyFlags(mod, IdString(), nullptr);
409
410 funct_declarations.push_back("");
411 funct_declarations.push_back(stringf("void %s_init(struct %s_state_t *state)", cid(mod->name).c_str(), cid(mod->name).c_str()));
412 funct_declarations.push_back("{");
413 funct_declarations.push_back("}");
414
415 funct_declarations.push_back("");
416 funct_declarations.push_back(stringf("void %s_eval(struct %s_state_t *state)", cid(mod->name).c_str(), cid(mod->name).c_str()));
417 funct_declarations.push_back("{");
418
419 for (Wire *w : mod->wires()) {
420 if (w->port_input)
421 for (SigBit bit : sigmaps.at(mod)(w))
422 dirty_flags->set_dirty(bit);
423 }
424
425 eval_dirty(dirty_flags, "state->", log_id(mod), "");
426
427 funct_declarations.push_back("}");
428
429 funct_declarations.push_back("");
430 funct_declarations.push_back(stringf("void %s_tick(struct %s_state_t *state)", cid(mod->name).c_str(), cid(mod->name).c_str()));
431 funct_declarations.push_back("{");
432 funct_declarations.push_back("}");
433
434 delete dirty_flags;
435 dirty_flags = nullptr;
436 }
437
438 void write(std::ostream &f)
439 {
440 f << "#include <stdint.h>" << std::endl;
441 f << "#include <stdbool.h>" << std::endl;
442
443 for (auto &line : signal_declarations)
444 f << line << std::endl;
445
446 for (auto &line : util_declarations)
447 f << line << std::endl;
448
449 for (auto &line : struct_declarations)
450 f << line << std::endl;
451
452 for (auto &line : funct_declarations)
453 f << line << std::endl;
454 }
455 };
456
457 struct SimplecBackend : public Backend {
458 SimplecBackend() : Backend("simplec", "convert design to simple C code") { }
459 virtual void help()
460 {
461 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
462 log("\n");
463 log(" write_simplec [options] [filename]\n");
464 log("\n");
465 log("Write simple C code for simulating the design. The C code writen can be used to\n");
466 log("simulate the design in a C environment, but the purpose of this command is to\n");
467 log("generate code that works well with C-based formal verification.\n");
468 log("\n");
469 log(" -verbose\n");
470 log(" this will print the recursive walk used to export the modules.\n");
471 log("\n");
472 log(" -i8, -i16, -i32, -i64\n");
473 log(" set the maximum integer bit width to use in the generated code.\n");
474 log("\n");
475 log("THIS COMMAND IS UNDER CONSTRUCTION\n");
476 log("\n");
477 }
478 virtual void execute(std::ostream *&f, std::string filename, std::vector<std::string> args, RTLIL::Design *design)
479 {
480 SimplecWorker worker(design);
481
482 log_header(design, "Executing SIMPLEC backend.\n");
483
484 size_t argidx;
485 for (argidx = 1; argidx < args.size(); argidx++)
486 {
487 if (args[argidx] == "-verbose") {
488 worker.verbose = true;
489 continue;
490 }
491 if (args[argidx] == "-i8") {
492 worker.max_uintsize = 8;
493 continue;
494 }
495 if (args[argidx] == "-i16") {
496 worker.max_uintsize = 16;
497 continue;
498 }
499 if (args[argidx] == "-i32") {
500 worker.max_uintsize = 32;
501 continue;
502 }
503 if (args[argidx] == "-i64") {
504 worker.max_uintsize = 64;
505 continue;
506 }
507 break;
508 }
509 extra_args(f, filename, args, argidx);
510
511 Module *topmod = design->top_module();
512
513 if (topmod == nullptr)
514 log_error("Current design has no top module.\n");
515
516 worker.run(topmod);
517 worker.write(*f);
518 }
519 } SimplecBackend;
520
521 PRIVATE_NAMESPACE_END