From 594dbc4c93e4370ee07ef85a6c28339be8c8d55a Mon Sep 17 00:00:00 2001 From: Clifford Wolf Date: Wed, 6 Mar 2013 09:38:47 +0100 Subject: Fixed handling of constant values and port swapping in subcircuit library --- libs/subcircuit/subcircuit.cc | 109 +++++++++++++++++++++++++++++++++--------- 1 file changed, 86 insertions(+), 23 deletions(-) (limited to 'libs') diff --git a/libs/subcircuit/subcircuit.cc b/libs/subcircuit/subcircuit.cc index 8cc5e6d9..79aa346b 100644 --- a/libs/subcircuit/subcircuit.cc +++ b/libs/subcircuit/subcircuit.cc @@ -718,38 +718,23 @@ class SubCircuit::SolverWorker // main solver functions - bool matchNodes(const Graph &needle, int needleNodeIdx, const Graph &haystack, int haystackNodeIdx) const + bool matchNodePorts(const Graph &needle, int needleNodeIdx, const Graph &haystack, int haystackNodeIdx, const std::map &swaps) const { - // Rules for matching nodes: - // - // 1. their typeId must be identical or compatible - // (this is checked before calling this function) - // - // 2. they must have the same ports and the haystack port - // widths must match the needle port width range - // - // 3. All edges from the needle must match the haystack: - // a) if the needle edge is extern: - // - the haystack edge must have at least as many components as the needle edge - // b) if the needle edge is not extern: - // - the haystack edge must have the same number of components as the needle edge - // - the haystack edge must not be extern - const Graph::Node &nn = needle.nodes[needleNodeIdx]; const Graph::Node &hn = haystack.nodes[haystackNodeIdx]; - - assert(nn.typeId == hn.typeId || (compatibleTypes.count(nn.typeId) > 0 && compatibleTypes.at(nn.typeId).count(hn.typeId) > 0)); - - if (nn.ports.size() != hn.ports.size()) - return false; + assert(nn.ports.size() == hn.ports.size()); for (int i = 0; i < int(nn.ports.size()); i++) { - if (hn.portMap.count(nn.ports[i].portId) == 0) + std::string hnPortId = nn.ports[i].portId; + if (swaps.count(hnPortId) > 0) + hnPortId = swaps.at(hnPortId); + + if (hn.portMap.count(hnPortId) == 0) return false; const Graph::Port &np = nn.ports[i]; - const Graph::Port &hp = hn.ports[hn.portMap.at(nn.ports[i].portId)]; + const Graph::Port &hp = hn.ports[hn.portMap.at(hnPortId)]; if (int(hp.bits.size()) < np.minWidth || hp.bits.size() > np.bits.size()) return false; @@ -781,6 +766,80 @@ class SubCircuit::SolverWorker return true; } + bool matchNodes(const Graph &needle, int needleNodeIdx, const Graph &haystack, int haystackNodeIdx) const + { + // Rules for matching nodes: + // + // 1. their typeId must be identical or compatible + // (this is checked before calling this function) + // + // 2. they must have the same ports and the haystack port + // widths must match the needle port width range + // + // 3. All edges from the needle must match the haystack: + // a) if the needle edge is extern: + // - the haystack edge must have at least as many components as the needle edge + // b) if the needle edge is not extern: + // - the haystack edge must have the same number of components as the needle edge + // - the haystack edge must not be extern + + const Graph::Node &nn = needle.nodes[needleNodeIdx]; + const Graph::Node &hn = haystack.nodes[haystackNodeIdx]; + + assert(nn.typeId == hn.typeId || (compatibleTypes.count(nn.typeId) > 0 && compatibleTypes.at(nn.typeId).count(hn.typeId) > 0)); + + if (nn.ports.size() != hn.ports.size()) + return false; + + std::map currentCandidate; + + for (const auto &port : needle.nodes[needleNodeIdx].ports) + currentCandidate[port.portId] = port.portId; + + if (swapPorts.count(needle.nodes[needleNodeIdx].typeId) == 0) + { + if (matchNodePorts(needle, needleNodeIdx, haystack, haystackNodeIdx, currentCandidate)) + return true; + + if (swapPermutations.count(needle.nodes[needleNodeIdx].typeId) > 0) + for (const auto &permutation : swapPermutations.at(needle.nodes[needleNodeIdx].typeId)) { + std::map currentSubCandidate = currentCandidate; + applyPermutation(currentSubCandidate, permutation); + if (matchNodePorts(needle, needleNodeIdx, haystack, haystackNodeIdx, currentCandidate)) + return true; + } + } + else + { + std::vector> thisSwapPorts; + for (const auto &ports : swapPorts.at(needle.nodes[needleNodeIdx].typeId)) { + std::vector portsVector; + for (const auto &port : ports) + portsVector.push_back(port); + thisSwapPorts.push_back(portsVector); + } + + int thisPermutations = numberOfPermutationsArray(thisSwapPorts); + for (int i = 0; i < thisPermutations; i++) + { + permutateVectorToMapArray(currentCandidate, thisSwapPorts, i); + + if (matchNodePorts(needle, needleNodeIdx, haystack, haystackNodeIdx, currentCandidate)) + return true; + + if (swapPermutations.count(needle.nodes[needleNodeIdx].typeId) > 0) + for (const auto &permutation : swapPermutations.at(needle.nodes[needleNodeIdx].typeId)) { + std::map currentSubCandidate = currentCandidate; + applyPermutation(currentSubCandidate, permutation); + if (matchNodePorts(needle, needleNodeIdx, haystack, haystackNodeIdx, currentCandidate)) + return true; + } + } + } + + return false; + } + void generateEnumerationMatrix(std::vector> &enumerationMatrix, const GraphData &needle, const GraphData &haystack, const std::map> &initialMappings) const { std::map> haystackNodesByTypeId; @@ -902,6 +961,9 @@ class SubCircuit::SolverWorker assert(enumerationMatrix[idx].size() == 1); int idxHaystack = *enumerationMatrix[idx].begin(); + if (!matchNodePorts(needle.graph, idx, haystack.graph, idxHaystack, currentCandidate)) + return false; + for (const auto &it_needle : needle.adjMatrix.at(idx)) { int needleNeighbour = it_needle.first; @@ -915,6 +977,7 @@ class SubCircuit::SolverWorker if (!diCache.compare(needleEdgeType, haystackEdgeType, currentCandidate, swapPorts, swapPermutations)) return false; } + return true; } -- cgit v1.2.3