projects / yosys.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
history | raw | HEAD
Transform "$.*" to ID("$.*") in passes/techmap
[yosys.git] / passes / techmap / maccmap.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/macc.h"
22
23 USING_YOSYS_NAMESPACE
24 PRIVATE_NAMESPACE_BEGIN
25
26 struct MaccmapWorker
27 {
28 std::vector<std::set<RTLIL::SigBit>> bits;
29 RTLIL::Module *module;
30 int width;
31
32 MaccmapWorker(RTLIL::Module *module, int width) : module(module), width(width)
33 {
34 bits.resize(width);
35 }
36
37 void add(RTLIL::SigBit bit, int position)
38 {
39 if (position >= width || bit == State::S0)
40 return;
41
42 if (bits.at(position).count(bit)) {
43 bits.at(position).erase(bit);
44 add(bit, position+1);
45 } else {
46 bits.at(position).insert(bit);
47 }
48 }
49
50 void add(RTLIL::SigSpec a, bool is_signed, bool do_subtract)
51 {
52 a.extend_u0(width, is_signed);
53
54 if (do_subtract) {
55 a = module->Not(NEW_ID, a);
56 add(State::S1, 0);
57 }
58
59 for (int i = 0; i < width; i++)
60 add(a[i], i);
61 }
62
63 void add(RTLIL::SigSpec a, RTLIL::SigSpec b, bool is_signed, bool do_subtract)
64 {
65 if (GetSize(a) < GetSize(b))
66 std::swap(a, b);
67
68 a.extend_u0(width, is_signed);
69
70 if (GetSize(b) > width)
71 b.extend_u0(width, is_signed);
72
73 for (int i = 0; i < GetSize(b); i++)
74 if (is_signed && i+1 == GetSize(b))
75 {
76 a = {module->Not(NEW_ID, a.extract(i, width-i)), RTLIL::SigSpec(0, i)};
77 add(module->And(NEW_ID, a, RTLIL::SigSpec(b[i], width)), false, do_subtract);
78 add({b[i], RTLIL::SigSpec(0, i)}, false, do_subtract);
79 }
80 else
81 {
82 add(module->And(NEW_ID, a, RTLIL::SigSpec(b[i], width)), false, do_subtract);
83 a = {a.extract(0, width-1), State::S0};
84 }
85 }
86
87 void fulladd(RTLIL::SigSpec &in1, RTLIL::SigSpec &in2, RTLIL::SigSpec &in3, RTLIL::SigSpec &out1, RTLIL::SigSpec &out2)
88 {
89 int start_index = 0, stop_index = GetSize(in1);
90
91 while (start_index < stop_index && in1[start_index] == State::S0 && in2[start_index] == RTLIL::S0 && in3[start_index] == RTLIL::S0)
92 start_index++;
93
94 while (start_index < stop_index && in1[stop_index-1] == State::S0 && in2[stop_index-1] == RTLIL::S0 && in3[stop_index-1] == RTLIL::S0)
95 stop_index--;
96
97 if (start_index == stop_index)
98 {
99 out1 = RTLIL::SigSpec(0, GetSize(in1));
100 out2 = RTLIL::SigSpec(0, GetSize(in1));
101 }
102 else
103 {
104 RTLIL::SigSpec out_zeros_lsb(0, start_index), out_zeros_msb(0, GetSize(in1)-stop_index);
105
106 in1 = in1.extract(start_index, stop_index-start_index);
107 in2 = in2.extract(start_index, stop_index-start_index);
108 in3 = in3.extract(start_index, stop_index-start_index);
109
110 int width = GetSize(in1);
111 RTLIL::Wire *w1 = module->addWire(NEW_ID, width);
112 RTLIL::Wire *w2 = module->addWire(NEW_ID, width);
113
114 RTLIL::Cell *cell = module->addCell(NEW_ID, ID($fa));
115 cell->setParam("\\WIDTH", width);
116 cell->setPort("\\A", in1);
117 cell->setPort("\\B", in2);
118 cell->setPort("\\C", in3);
119 cell->setPort("\\Y", w1);
120 cell->setPort("\\X", w2);
121
122 out1 = {out_zeros_msb, w1, out_zeros_lsb};
123 out2 = {out_zeros_msb, w2, out_zeros_lsb};
124 }
125 }
126
127 int tree_bit_slots(int n)
128 {
129 #if 0
130 int retval = 1;
131 while (n > 2) {
132 retval += n / 3;
133 n = 2*(n / 3) + (n % 3);
134 }
135 return retval;
136 #else
137 return max(n - 1, 0);
138 #endif
139 }
140
141 RTLIL::SigSpec synth()
142 {
143 std::vector<RTLIL::SigSpec> summands;
144 std::vector<RTLIL::SigBit> tree_sum_bits;
145 int unique_tree_bits = 0;
146 int count_tree_words = 0;
147
148 while (1)
149 {
150 RTLIL::SigSpec summand(0, width);
151 bool got_data_bits = false;
152
153 for (int i = 0; i < width; i++)
154 if (!bits.at(i).empty()) {
155 auto it = bits.at(i).begin();
156 summand[i] = *it;
157 bits.at(i).erase(it);
158 got_data_bits = true;
159 }
160
161 if (!got_data_bits)
162 break;
163
164 summands.push_back(summand);
165
166 while (1)
167 {
168 int free_bit_slots = tree_bit_slots(GetSize(summands)) - GetSize(tree_sum_bits);
169
170 int max_depth = 0, max_position = 0;
171 for (int i = 0; i < width; i++)
172 if (max_depth <= GetSize(bits.at(i))) {
173 max_depth = GetSize(bits.at(i));
174 max_position = i;
175 }
176
177 if (max_depth == 0 || max_position > 4)
178 break;
179
180 int required_bits = 0;
181 for (int i = 0; i <= max_position; i++)
182 if (GetSize(bits.at(i)) == max_depth)
183 required_bits += 1 << i;
184
185 if (required_bits > free_bit_slots)
186 break;
187
188 for (int i = 0; i <= max_position; i++)
189 if (GetSize(bits.at(i)) == max_depth) {
190 auto it = bits.at(i).begin();
191 RTLIL::SigBit bit = *it;
192 for (int k = 0; k < (1 << i); k++, free_bit_slots--)
193 tree_sum_bits.push_back(bit);
194 bits.at(i).erase(it);
195 unique_tree_bits++;
196 }
197
198 count_tree_words++;
199 }
200 }
201
202 if (!tree_sum_bits.empty())
203 log(" packed %d (%d) bits / %d words into adder tree\n", GetSize(tree_sum_bits), unique_tree_bits, count_tree_words);
204
205 if (GetSize(summands) == 0) {
206 log_assert(tree_sum_bits.empty());
207 return RTLIL::SigSpec(0, width);
208 }
209
210 if (GetSize(summands) == 1) {
211 log_assert(tree_sum_bits.empty());
212 return summands.front();
213 }
214
215 while (GetSize(summands) > 2)
216 {
217 std::vector<RTLIL::SigSpec> new_summands;
218 for (int i = 0; i < GetSize(summands); i += 3)
219 if (i+2 < GetSize(summands)) {
220 RTLIL::SigSpec in1 = summands[i];
221 RTLIL::SigSpec in2 = summands[i+1];
222 RTLIL::SigSpec in3 = summands[i+2];
223 RTLIL::SigSpec out1, out2;
224 fulladd(in1, in2, in3, out1, out2);
225 RTLIL::SigBit extra_bit = State::S0;
226 if (!tree_sum_bits.empty()) {
227 extra_bit = tree_sum_bits.back();
228 tree_sum_bits.pop_back();
229 }
230 new_summands.push_back(out1);
231 new_summands.push_back({out2.extract(0, width-1), extra_bit});
232 } else {
233 new_summands.push_back(summands[i]);
234 i -= 2;
235 }
236 summands.swap(new_summands);
237 }
238
239
240 RTLIL::Cell *c = module->addCell(NEW_ID, ID($alu));
241 c->setPort("\\A", summands.front());
242 c->setPort("\\B", summands.back());
243 c->setPort("\\CI", State::S0);
244 c->setPort("\\BI", State::S0);
245 c->setPort("\\Y", module->addWire(NEW_ID, width));
246 c->setPort("\\X", module->addWire(NEW_ID, width));
247 c->setPort("\\CO", module->addWire(NEW_ID, width));
248 c->fixup_parameters();
249
250 if (!tree_sum_bits.empty()) {
251 c->setPort("\\CI", tree_sum_bits.back());
252 tree_sum_bits.pop_back();
253 }
254 log_assert(tree_sum_bits.empty());
255
256 return c->getPort("\\Y");
257 }
258 };
259
260 PRIVATE_NAMESPACE_END
261 YOSYS_NAMESPACE_BEGIN
262
263 extern void maccmap(RTLIL::Module *module, RTLIL::Cell *cell, bool unmap = false);
264
265 void maccmap(RTLIL::Module *module, RTLIL::Cell *cell, bool unmap)
266 {
267 int width = GetSize(cell->getPort("\\Y"));
268
269 Macc macc;
270 macc.from_cell(cell);
271
272 RTLIL::SigSpec all_input_bits;
273 all_input_bits.append(cell->getPort("\\A"));
274 all_input_bits.append(cell->getPort("\\B"));
275
276 if (all_input_bits.to_sigbit_set().count(RTLIL::Sx)) {
277 module->connect(cell->getPort("\\Y"), RTLIL::SigSpec(RTLIL::Sx, width));
278 return;
279 }
280
281 for (auto &port : macc.ports)
282 if (GetSize(port.in_b) == 0)
283 log(" %s %s (%d bits, %s)\n", port.do_subtract ? "sub" : "add", log_signal(port.in_a),
284 GetSize(port.in_a), port.is_signed ? "signed" : "unsigned");
285 else
286 log(" %s %s * %s (%dx%d bits, %s)\n", port.do_subtract ? "sub" : "add", log_signal(port.in_a), log_signal(port.in_b),
287 GetSize(port.in_a), GetSize(port.in_b), port.is_signed ? "signed" : "unsigned");
288
289 if (GetSize(macc.bit_ports) != 0)
290 log(" add bits %s (%d bits)\n", log_signal(macc.bit_ports), GetSize(macc.bit_ports));
291
292 if (unmap)
293 {
294 typedef std::pair<RTLIL::SigSpec, bool> summand_t;
295 std::vector<summand_t> summands;
296
297 for (auto &port : macc.ports) {
298 summand_t this_summand;
299 if (GetSize(port.in_b)) {
300 this_summand.first = module->addWire(NEW_ID, width);
301 module->addMul(NEW_ID, port.in_a, port.in_b, this_summand.first, port.is_signed);
302 } else if (GetSize(port.in_a) != width) {
303 this_summand.first = module->addWire(NEW_ID, width);
304 module->addPos(NEW_ID, port.in_a, this_summand.first, port.is_signed);
305 } else {
306 this_summand.first = port.in_a;
307 }
308 this_summand.second = port.do_subtract;
309 summands.push_back(this_summand);
310 }
311
312 for (auto &bit : macc.bit_ports)
313 summands.push_back(summand_t(bit, false));
314
315 if (GetSize(summands) == 0)
316 summands.push_back(summand_t(RTLIL::SigSpec(0, width), false));
317
318 while (GetSize(summands) > 1)
319 {
320 std::vector<summand_t> new_summands;
321 for (int i = 0; i < GetSize(summands); i += 2) {
322 if (i+1 < GetSize(summands)) {
323 summand_t this_summand;
324 this_summand.first = module->addWire(NEW_ID, width);
325 this_summand.second = summands[i].second && summands[i+1].second;
326 if (summands[i].second == summands[i+1].second)
327 module->addAdd(NEW_ID, summands[i].first, summands[i+1].first, this_summand.first);
328 else if (summands[i].second)
329 module->addSub(NEW_ID, summands[i+1].first, summands[i].first, this_summand.first);
330 else if (summands[i+1].second)
331 module->addSub(NEW_ID, summands[i].first, summands[i+1].first, this_summand.first);
332 else
333 log_abort();
334 new_summands.push_back(this_summand);
335 } else
336 new_summands.push_back(summands[i]);
337 }
338 summands.swap(new_summands);
339 }
340
341 if (summands.front().second)
342 module->addNeg(NEW_ID, summands.front().first, cell->getPort("\\Y"));
343 else
344 module->connect(cell->getPort("\\Y"), summands.front().first);
345 }
346 else
347 {
348 MaccmapWorker worker(module, width);
349
350 for (auto &port : macc.ports)
351 if (GetSize(port.in_b) == 0)
352 worker.add(port.in_a, port.is_signed, port.do_subtract);
353 else
354 worker.add(port.in_a, port.in_b, port.is_signed, port.do_subtract);
355
356 for (auto &bit : macc.bit_ports)
357 worker.add(bit, 0);
358
359 module->connect(cell->getPort("\\Y"), worker.synth());
360 }
361 }
362
363 YOSYS_NAMESPACE_END
364 PRIVATE_NAMESPACE_BEGIN
365
366 struct MaccmapPass : public Pass {
367 MaccmapPass() : Pass("maccmap", "mapping macc cells") { }
368 void help() YS_OVERRIDE
369 {
370 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
371 log("\n");
372 log(" maccmap [-unmap] [selection]\n");
373 log("\n");
374 log("This pass maps $macc cells to yosys $fa and $alu cells. When the -unmap option\n");
375 log("is used then the $macc cell is mapped to $add, $sub, etc. cells instead.\n");
376 log("\n");
377 }
378 void execute(std::vector<std::string> args, RTLIL::Design *design) YS_OVERRIDE
379 {
380 bool unmap_mode = false;
381
382 log_header(design, "Executing MACCMAP pass (map $macc cells).\n");
383
384 size_t argidx;
385 for (argidx = 1; argidx < args.size(); argidx++) {
386 if (args[argidx] == "-unmap") {
387 unmap_mode = true;
388 continue;
389 }
390 break;
391 }
392 extra_args(args, argidx, design);
393
394 for (auto mod : design->selected_modules())
395 for (auto cell : mod->selected_cells())
396 if (cell->type == ID($macc)) {
397 log("Mapping %s.%s (%s).\n", log_id(mod), log_id(cell), log_id(cell->type));
398 maccmap(mod, cell, unmap_mode);
399 mod->remove(cell);
400 }
401 }
402 } MaccmapPass;
403
404 PRIVATE_NAMESPACE_END