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 #include "kernel/yosys.h"
21 #include "kernel/macc.h"
24 PRIVATE_NAMESPACE_BEGIN
28 std::vector
<std::set
<RTLIL::SigBit
>> bits
;
29 RTLIL::Module
*module
;
32 MaccmapWorker(RTLIL::Module
*module
, int width
) : module(module
), width(width
)
37 void add(RTLIL::SigBit bit
, int position
)
39 if (position
>= width
|| bit
== RTLIL::S0
)
42 if (bits
.at(position
).count(bit
)) {
43 bits
.at(position
).erase(bit
);
46 bits
.at(position
).insert(bit
);
50 void add(RTLIL::SigSpec a
, bool is_signed
, bool do_subtract
)
52 a
.extend_u0(width
, is_signed
);
55 a
= module
->Not(NEW_ID
, a
);
59 for (int i
= 0; i
< width
; i
++)
63 void add(RTLIL::SigSpec a
, RTLIL::SigSpec b
, bool is_signed
, bool do_subtract
)
65 if (GetSize(a
) < GetSize(b
))
68 a
.extend_u0(width
, is_signed
);
70 if (GetSize(b
) > width
)
71 b
.extend_u0(width
, is_signed
);
73 for (int i
= 0; i
< GetSize(b
); i
++)
74 if (is_signed
&& i
+1 == GetSize(b
))
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
);
82 add(module
->And(NEW_ID
, a
, RTLIL::SigSpec(b
[i
], width
)), false, do_subtract
);
83 a
= {a
.extract(0, width
-1), RTLIL::S0
};
87 void fulladd(RTLIL::SigSpec
&in1
, RTLIL::SigSpec
&in2
, RTLIL::SigSpec
&in3
, RTLIL::SigSpec
&out1
, RTLIL::SigSpec
&out2
)
89 int start_index
= 0, stop_index
= GetSize(in1
);
91 while (start_index
< stop_index
&& in1
[start_index
] == RTLIL::S0
&& in2
[start_index
] == RTLIL::S0
&& in3
[start_index
] == RTLIL::S0
)
94 while (start_index
< stop_index
&& in1
[stop_index
-1] == RTLIL::S0
&& in2
[stop_index
-1] == RTLIL::S0
&& in3
[stop_index
-1] == RTLIL::S0
)
97 if (start_index
== stop_index
)
99 out1
= RTLIL::SigSpec(0, GetSize(in1
));
100 out2
= RTLIL::SigSpec(0, GetSize(in1
));
104 RTLIL::SigSpec
out_zeros_lsb(0, start_index
), out_zeros_msb(0, GetSize(in1
)-stop_index
);
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
);
110 int width
= GetSize(in1
);
111 RTLIL::Wire
*w1
= module
->addWire(NEW_ID
, width
);
112 RTLIL::Wire
*w2
= module
->addWire(NEW_ID
, width
);
114 RTLIL::Cell
*cell
= module
->addCell(NEW_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
);
122 out1
= {out_zeros_msb
, w1
, out_zeros_lsb
};
123 out2
= {out_zeros_msb
, w2
, out_zeros_lsb
};
127 int tree_bit_slots(int n
)
133 n
= 2*(n
/ 3) + (n
% 3);
137 return max(n
- 1, 0);
141 RTLIL::SigSpec
synth()
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;
150 RTLIL::SigSpec
summand(0, width
);
151 bool got_data_bits
= false;
153 for (int i
= 0; i
< width
; i
++)
154 if (!bits
.at(i
).empty()) {
155 auto it
= bits
.at(i
).begin();
157 bits
.at(i
).erase(it
);
158 got_data_bits
= true;
164 summands
.push_back(summand
);
168 int free_bit_slots
= tree_bit_slots(GetSize(summands
)) - GetSize(tree_sum_bits
);
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
));
177 if (max_depth
== 0 || max_position
> 4)
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
;
185 if (required_bits
> free_bit_slots
)
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
);
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
);
205 if (GetSize(summands
) == 0) {
206 log_assert(tree_sum_bits
.empty());
207 return RTLIL::SigSpec(0, width
);
210 if (GetSize(summands
) == 1) {
211 log_assert(tree_sum_bits
.empty());
212 return summands
.front();
215 while (GetSize(summands
) > 2)
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
= RTLIL::S0
;
226 if (!tree_sum_bits
.empty()) {
227 extra_bit
= tree_sum_bits
.back();
228 tree_sum_bits
.pop_back();
230 new_summands
.push_back(out1
);
231 new_summands
.push_back({out2
.extract(0, width
-1), extra_bit
});
233 new_summands
.push_back(summands
[i
]);
236 summands
.swap(new_summands
);
240 RTLIL::Cell
*c
= module
->addCell(NEW_ID
, "$alu");
241 c
->setPort("\\A", summands
.front());
242 c
->setPort("\\B", summands
.back());
243 c
->setPort("\\CI", RTLIL::S0
);
244 c
->setPort("\\BI", RTLIL::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();
250 if (!tree_sum_bits
.empty()) {
251 c
->setPort("\\CI", tree_sum_bits
.back());
252 tree_sum_bits
.pop_back();
254 log_assert(tree_sum_bits
.empty());
256 return c
->getPort("\\Y");
260 PRIVATE_NAMESPACE_END
261 YOSYS_NAMESPACE_BEGIN
263 extern void maccmap(RTLIL::Module
*module
, RTLIL::Cell
*cell
, bool unmap
= false);
265 void maccmap(RTLIL::Module
*module
, RTLIL::Cell
*cell
, bool unmap
)
267 int width
= GetSize(cell
->getPort("\\Y"));
270 macc
.from_cell(cell
);
272 RTLIL::SigSpec all_input_bits
;
273 all_input_bits
.append(cell
->getPort("\\A"));
274 all_input_bits
.append(cell
->getPort("\\B"));
276 if (all_input_bits
.to_sigbit_set().count(RTLIL::Sx
)) {
277 module
->connect(cell
->getPort("\\Y"), RTLIL::SigSpec(RTLIL::Sx
, width
));
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");
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");
289 if (GetSize(macc
.bit_ports
) != 0)
290 log(" add bits %s (%d bits)\n", log_signal(macc
.bit_ports
), GetSize(macc
.bit_ports
));
294 typedef std::pair
<RTLIL::SigSpec
, bool> summand_t
;
295 std::vector
<summand_t
> summands
;
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
);
306 this_summand
.first
= port
.in_a
;
308 this_summand
.second
= port
.do_subtract
;
309 summands
.push_back(this_summand
);
312 for (auto &bit
: macc
.bit_ports
)
313 summands
.push_back(summand_t(bit
, false));
315 if (GetSize(summands
) == 0)
316 summands
.push_back(summand_t(RTLIL::SigSpec(0, width
), false));
318 while (GetSize(summands
) > 1)
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
);
334 new_summands
.push_back(this_summand
);
336 new_summands
.push_back(summands
[i
]);
338 summands
.swap(new_summands
);
341 if (summands
.front().second
)
342 module
->addNeg(NEW_ID
, summands
.front().first
, cell
->getPort("\\Y"));
344 module
->connect(cell
->getPort("\\Y"), summands
.front().first
);
348 MaccmapWorker
worker(module
, width
);
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
);
354 worker
.add(port
.in_a
, port
.in_b
, port
.is_signed
, port
.do_subtract
);
356 for (auto &bit
: macc
.bit_ports
)
359 module
->connect(cell
->getPort("\\Y"), worker
.synth());
364 PRIVATE_NAMESPACE_BEGIN
366 struct MaccmapPass
: public Pass
{
367 MaccmapPass() : Pass("maccmap", "mapping macc cells") { }
368 void help() YS_OVERRIDE
370 // |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
372 log(" maccmap [-unmap] [selection]\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");
378 void execute(std::vector
<std::string
> args
, RTLIL::Design
*design
) YS_OVERRIDE
380 bool unmap_mode
= false;
382 log_header(design
, "Executing MACCMAP pass (map $macc cells).\n");
385 for (argidx
= 1; argidx
< args
.size(); argidx
++) {
386 if (args
[argidx
] == "-unmap") {
392 extra_args(args
, argidx
, design
);
394 for (auto mod
: design
->selected_modules())
395 for (auto cell
: mod
->selected_cells())
396 if (cell
->type
== "$macc") {
397 log("Mapping %s.%s (%s).\n", log_id(mod
), log_id(cell
), log_id(cell
->type
));
398 maccmap(mod
, cell
, unmap_mode
);
404 PRIVATE_NAMESPACE_END