Skip to content
Permalink

Comparing changes

Choose two branches to see what’s changed or to start a new pull request. If you need to, you can also or learn more about diff comparisons.

Open a pull request

Create a new pull request by comparing changes across two branches. If you need to, you can also . Learn more about diff comparisons here.
base repository: azonenberg/yosys
Failed to load repositories. Confirm that selected base ref is valid, then try again.
Loading
base: e52436ad56f0
Choose a base ref
...
head repository: azonenberg/yosys
Failed to load repositories. Confirm that selected head ref is valid, then try again.
Loading
compare: bd58923157a5
Choose a head ref
  • 12 commits
  • 5 files changed
  • 3 contributors

Commits on Aug 27, 2017

  1. recover_reduce_core: Initial commit

    Conflicts:
    	passes/techmap/Makefile.inc
    ArcaneNibble committed Aug 27, 2017
    Copy the full SHA
    fa310c9 View commit details
  2. Copy the full SHA
    8b7dc79 View commit details
  3. recover_reduce: Add driver script for the $reduce_* recover feature

    Conflicts:
    	passes/techmap/Makefile.inc
    ArcaneNibble committed Aug 27, 2017
    Copy the full SHA
    99dad40 View commit details
  4. recover_reduce: Rename recover_reduce_core to recover_reduce

    Clifford has commented on PR YosysHQ#387 stating that he does not like the
    driver script and would prefer to only have the core script with
    appropriate notes in the documentation.
    
    Also rename to .cc (rather than .cpp) for consistency.
    ArcaneNibble committed Aug 27, 2017
    Copy the full SHA
    8a58874 View commit details
  5. Copy the full SHA
    74d0f17 View commit details
  6. recover_reduce: Update documentation

    The documentation now describes the commands performed in the deleted
    recover_reduce script.
    ArcaneNibble committed Aug 27, 2017
    Copy the full SHA
    849b885 View commit details

Commits on Aug 28, 2017

  1. Copy the full SHA
    ebbb0e9 View commit details
  2. Merge branch 'recover-reduce' of https://github.com/azonenberg/yosys

    …into azonenberg-recover-reduce
    cliffordwolf committed Aug 28, 2017
    Copy the full SHA
    3aad3ed View commit details
  3. Copy the full SHA
    908f34a View commit details
  4. Copy the full SHA
    393b18e View commit details
  5. Copy the full SHA
    7208c6c View commit details
  6. Copy the full SHA
    bd58923 View commit details
Showing with 282 additions and 322 deletions.
  1. +1 −2 passes/techmap/Makefile.inc
  2. +42 −1 passes/techmap/extract_fa.cc
  3. +239 −0 passes/techmap/extract_reduce.cc
  4. +0 −100 passes/techmap/recover_reduce.cpp
  5. +0 −219 passes/techmap/recover_reduce_core.cpp
3 changes: 1 addition & 2 deletions passes/techmap/Makefile.inc
Original file line number Diff line number Diff line change
@@ -21,11 +21,10 @@ $(eval $(call add_share_file,share/untechmap,passes/techmap/adder_untechmap.lib)
$(eval $(call add_share_file,share/untechmap,passes/techmap/adder_untechmap.v))
$(eval $(call add_share_file,share/untechmap,passes/techmap/adder_untechmap_gates.v))
OBJS += passes/techmap/recover_adder_core.o
OBJS += passes/techmap/recover_reduce.o
OBJS += passes/techmap/recover_reduce_core.o
OBJS += passes/techmap/recover_tff.o
$(eval $(call add_share_file,share/untechmap,passes/techmap/tff_untechmap.v))
OBJS += passes/techmap/extract_fa.o
OBJS += passes/techmap/extract_reduce.o
OBJS += passes/techmap/alumacc.o
OBJS += passes/techmap/dff2dffe.o
OBJS += passes/techmap/dffinit.o
43 changes: 42 additions & 1 deletion passes/techmap/extract_fa.cc
Original file line number Diff line number Diff line change
@@ -28,6 +28,9 @@ struct ExtractFaConfig
{
bool enable_fa = false;
bool enable_ha = false;
bool verbose = false;
int maxdepth = 20;
int maxbreadth = 6;
};

// http://svn.clifford.at/handicraft/2016/bindec/bindec.c
@@ -63,6 +66,9 @@ struct ExtractFaWorker
dict<tuple<SigBit, SigBit>, dict<int, pool<SigBit>>> func2;
dict<tuple<SigBit, SigBit, SigBit>, dict<int, pool<SigBit>>> func3;

int count_func2;
int count_func3;

struct func2_and_info_t {
bool inv_a, inv_b, inv_y;
};
@@ -182,6 +188,7 @@ struct ExtractFaWorker
if (func == xor2_func || func == xnor2_func)
xorxnor2.insert(tuple<SigBit, SigBit>(A, B));

count_func2++;
func2[tuple<SigBit, SigBit>(A, B)][func].insert(root);
}

@@ -221,6 +228,7 @@ struct ExtractFaWorker
if (func == xor3_func || func == xnor3_func)
xorxnor3.insert(tuple<SigBit, SigBit, SigBit>(A, B, C));

count_func3++;
func3[tuple<SigBit, SigBit, SigBit>(A, B, C)][func].insert(root);
}
}
@@ -284,7 +292,19 @@ struct ExtractFaWorker
pool<SigBit> leaves = { root };
pool<pool<SigBit>> cache;

find_partitions(root, leaves, cache, 20, 10);
if (config.verbose)
log(" checking %s\n", log_signal(it.first));

count_func2 = 0;
count_func3 = 0;

find_partitions(root, leaves, cache, config.maxdepth, config.maxbreadth);

if (config.verbose && count_func2 > 0)
log(" extracted %d two-input functions\n", count_func2);

if (config.verbose && count_func3 > 0)
log(" extracted %d three-input functions\n", count_func3);
}

for (auto &key : xorxnor3)
@@ -460,6 +480,15 @@ struct ExtractFaPass : public Pass {
log(" Enable cell types (fa=full adder, ha=half adder)\n");
log(" All types are enabled if none of this options is used\n");
log("\n");
log(" -d <int>\n");
log(" Set maximum depth for extracted logic cones (default=20)\n");
log("\n");
log(" -b <int>\n");
log(" Set maximum breadth for extracted logic cones (default=6)\n");
log("\n");
log(" -v\n");
log(" Verbose output\n");
log("\n");
}
virtual void execute(std::vector<std::string> args, RTLIL::Design *design)
{
@@ -479,6 +508,18 @@ struct ExtractFaPass : public Pass {
config.enable_ha = true;
continue;
}
if (args[argidx] == "-v") {
config.verbose = true;
continue;
}
if (args[argidx] == "-d" && argidx+2 < args.size()) {
config.maxdepth = atoi(args[++argidx].c_str());
continue;
}
if (args[argidx] == "-b" && argidx+2 < args.size()) {
config.maxbreadth = atoi(args[++argidx].c_str());
continue;
}
break;
}
extra_args(args, argidx, design);
239 changes: 239 additions & 0 deletions passes/techmap/extract_reduce.cc
Original file line number Diff line number Diff line change
@@ -0,0 +1,239 @@
/*
* yosys -- Yosys Open SYnthesis Suite
*
* Copyright (C) 2017 Robert Ou <rqou@robertou.com>
*
* Permission to use, copy, modify, and/or distribute this software for any
* purpose with or without fee is hereby granted, provided that the above
* copyright notice and this permission notice appear in all copies.
*
* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
* ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
* ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
* OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
*
*/

#include "kernel/yosys.h"
#include "kernel/sigtools.h"

USING_YOSYS_NAMESPACE
PRIVATE_NAMESPACE_BEGIN

struct ExtractReducePass : public Pass
{
enum GateType {
And,
Or,
Xor
};

ExtractReducePass() : Pass("extract_reduce", "converts gate chains into $reduce_* cells") { }

virtual void help()
{
// |---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|---v---|
log("\n");
log(" extract_reduce [selection]\n");
log("\n");
log("converts gate chains into $reduce_* cells\n");
log("\n");
log("This command finds chains of $_AND_, $_OR_, and $_XOR_ cells and replaces them\n");
log("with their corresponding $reduce_* cells. Because this command only operates on\n");
log("these cell types, it is recommended to map the design to only these cell types\n");
log("using the `abc -g` command. Note that, in some cases, it may be more effective\n");
log("to map the design to only $_AND_ cells, run extract_reduce, map the remaining\n");
log("parts of the design to AND/OR/XOR cells, and run extract_reduce a second time.\n");
log("\n");
}

virtual void execute(std::vector<std::string> args, RTLIL::Design *design)
{
log_header(design, "Executing EXTRACT_REDUCE pass.\n");
log_push();

size_t argidx;
for (argidx = 1; argidx < args.size(); argidx++)
{
// if (args[argidx] == "-v") {
// verbose = true;
// continue;
// }
break;
}
extra_args(args, argidx, design);

for (auto module : design->selected_modules())
{
SigMap sigmap(module);

// Index all of the nets in the module
dict<SigBit, Cell*> sig_to_driver;
dict<SigBit, pool<Cell*>> sig_to_sink;
for (auto cell : module->selected_cells())
{
for (auto &conn : cell->connections())
{
if (cell->output(conn.first))
for (auto bit : sigmap(conn.second))
sig_to_driver[bit] = cell;

if (cell->input(conn.first))
{
for (auto bit : sigmap(conn.second))
{
if (sig_to_sink.count(bit) == 0)
sig_to_sink[bit] = pool<Cell*>();
sig_to_sink[bit].insert(cell);
}
}
}
}

// Need to check if any wires connect to module ports
pool<SigBit> port_sigs;
for (auto wire : module->selected_wires())
if (wire->port_input || wire->port_output)
for (auto bit : sigmap(wire))
port_sigs.insert(bit);

// Actual logic starts here
pool<Cell*> consumed_cells;
for (auto cell : module->selected_cells())
{
if (consumed_cells.count(cell))
continue;

GateType gt;

if (cell->type == "$_AND_")
gt = GateType::And;
else if (cell->type == "$_OR_")
gt = GateType::Or;
else if (cell->type == "$_XOR_")
gt = GateType::Xor;
else
continue;

log("Working on cell %s...\n", cell->name.c_str());

// Go all the way to the sink
Cell* head_cell = cell;
Cell* x = cell;
while (true)
{
if (!((x->type == "$_AND_" && gt == GateType::And) ||
(x->type == "$_OR_" && gt == GateType::Or) ||
(x->type == "$_XOR_" && gt == GateType::Xor)))
break;

head_cell = x;

auto y = sigmap(x->getPort("\\Y"));
log_assert(y.size() == 1);

// Should only continue if there is one fanout back into a cell (not to a port)
if (sig_to_sink[y[0]].size() != 1)
break;

x = *sig_to_sink[y[0]].begin();
}

log(" Head cell is %s\n", head_cell->name.c_str());

pool<Cell*> cur_supercell;
std::deque<Cell*> bfs_queue = {head_cell};
while (bfs_queue.size())
{
Cell* x = bfs_queue.front();
bfs_queue.pop_front();

cur_supercell.insert(x);

auto a = sigmap(x->getPort("\\A"));
log_assert(a.size() == 1);
// Must have only one sink
// XXX: Check that it is indeed this node?
if (sig_to_sink[a[0]].size() + port_sigs.count(a[0]) == 1)
{
Cell* cell_a = sig_to_driver[a[0]];
if (((cell_a->type == "$_AND_" && gt == GateType::And) ||
(cell_a->type == "$_OR_" && gt == GateType::Or) ||
(cell_a->type == "$_XOR_" && gt == GateType::Xor)))
{
// The cell here is the correct type, and it's definitely driving only
// this current cell.
bfs_queue.push_back(cell_a);
}
}

auto b = sigmap(x->getPort("\\B"));
log_assert(b.size() == 1);
// Must have only one sink
// XXX: Check that it is indeed this node?
if (sig_to_sink[b[0]].size() + port_sigs.count(b[0]) == 1)
{
Cell* cell_b = sig_to_driver[b[0]];
if (((cell_b->type == "$_AND_" && gt == GateType::And) ||
(cell_b->type == "$_OR_" && gt == GateType::Or) ||
(cell_b->type == "$_XOR_" && gt == GateType::Xor)))
{
// The cell here is the correct type, and it's definitely driving only
// this current cell.
bfs_queue.push_back(cell_b);
}
}
}

log(" Cells:\n");
for (auto x : cur_supercell)
log(" %s\n", x->name.c_str());

if (cur_supercell.size() > 1)
{
// Worth it to create reduce cell
log(" Creating $reduce_* cell!\n");

pool<SigBit> input_pool;
pool<SigBit> input_pool_intermed;
for (auto x : cur_supercell)
{
input_pool.insert(sigmap(x->getPort("\\A"))[0]);
input_pool.insert(sigmap(x->getPort("\\B"))[0]);
input_pool_intermed.insert(sigmap(x->getPort("\\Y"))[0]);
}
SigSpec input;
for (auto b : input_pool)
if (input_pool_intermed.count(b) == 0)
input.append_bit(b);

SigBit output = sigmap(head_cell->getPort("\\Y")[0]);

auto new_reduce_cell = module->addCell(NEW_ID,
gt == GateType::And ? "$reduce_and" :
gt == GateType::Or ? "$reduce_or" :
gt == GateType::Xor ? "$reduce_xor" : "");
new_reduce_cell->setParam("\\A_SIGNED", 0);
new_reduce_cell->setParam("\\A_WIDTH", input.size());
new_reduce_cell->setParam("\\Y_WIDTH", 1);
new_reduce_cell->setPort("\\A", input);
new_reduce_cell->setPort("\\Y", output);

for (auto x : cur_supercell)
consumed_cells.insert(x);
}
}

// Remove every cell that we've used up
for (auto cell : consumed_cells)
module->remove(cell);
}

log_pop();
}
} ExtractReducePass;

PRIVATE_NAMESPACE_END
Loading