OpenASIP 2.2
Loading...
Searching...
No Matches
AutomagicTools.cc
Go to the documentation of this file.
1/*
2 Copyright (c) 2002-2017 Tampere University.
3
4 This file is part of TTA-Based Codesign Environment (TCE).
5
6 Permission is hereby granted, free of charge, to any person obtaining a
7 copy of this software and associated documentation files (the "Software"),
8 to deal in the Software without restriction, including without limitation
9 the rights to use, copy, modify, merge, publish, distribute, sublicense,
10 and/or sell copies of the Software, and to permit persons to whom the
11 Software is furnished to do so, subject to the following conditions:
12
13 The above copyright notice and this permission notice shall be included in
14 all copies or substantial portions of the Software.
15
16 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
19 THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21 FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
22 DEALINGS IN THE SOFTWARE.
23 */
24/**
25* @file AutomagicTools.cc
26*
27* Tools for automated TTA generation.
28*
29* @author Lasse Lehtonen 2017 (lasse.lehtonen-no.spam-tut.fi)
30* @author Topi Leppänen 2019 (topi.leppanen-no.spam-tuni.fi)
31*/
32
33#include "StringTools.hh"
34#include "AutomagicTools.hh"
36#include "CachedHDBManager.hh"
37#include "FUArchitecture.hh"
38#include "FUEntry.hh"
39#include "FUImplementation.hh"
40#include "FileSystem.hh"
41#include "HWOperation.hh"
42#include "Operation.hh"
43#include "OperationDAG.hh"
44#include "OperationIndex.hh"
45#include "OperationModule.hh"
46#include "OperationNode.hh"
47#include "OperationPool.hh"
48#include "OperationPool.hh"
49#include "RFArchitecture.hh"
50#include "RFEntry.hh"
51#include "RFImplementation.hh"
52#include "TerminalNode.hh"
53
54/**
55 * Check if given fu can be generated. If so return it in fug.
56 *
57 */
60 const std::vector<IDF::FUGenerated::Info>& infos,
61 const std::vector<IDF::FUGenerated::DAGOperation> dagops) {
62
63 std::vector<TTAMachine::HWOperation*> operations;
64 std::vector<std::string> genops;
65
66 for (int i = 0; i < fu.operationCount(); ++i) {
67 operations.emplace_back(fu.operation(i));
68 }
69
70 for (auto&& op : operations) {
71 int maxLatency;
73 fug.name(), options.fuFrontRegistered, false)) {
74 maxLatency = op->latency() - 1;
76 fug.name(), options.fuMiddleRegistered, false)) {
77 maxLatency = op->latency() - 2;
79 fug.name(), options.fuBackRegistered, false)) {
80 maxLatency = op->latency();
82 fug.name(), options.fuFrontRegistered)) {
83 maxLatency = op->latency() - 1;
85 fug.name(), options.fuMiddleRegistered)) {
86 maxLatency = op->latency() - 2;
87 } else { // Default to back-register
88 maxLatency = op->latency();
89 }
90 for (auto&& info : infos) {
91 if (op->name() == info.operationName
92 && maxLatency >= info.latency) {
93 fug.addOperation(info);
94 genops.emplace_back(info.operationName);
95 break;
96 }
97 }
98 }
99
100 for (auto&& op : operations) {
101 for (auto&& dop : dagops) {
102 if (std::find(genops.begin(), genops.end(), op->name()) ==
103 genops.end() &&
104 op->name() == dop.operationName) {
105 fug.addOperation(dop);
106 genops.emplace_back(dop.operationName);
107 }
108 }
109 }
110
111 size_t neededFUops = fu.operationCount();
112
113 if (genops.size() == neededFUops) {
114 return true;
115 } else {
116 return false;
117 }
118}
119
120/**
121 * Check if option is in the list or list has 'ALL' in it.
122 */
124 const std::string& option, std::vector<std::string> list, bool enableAll) {
125 std::string lowered_option = StringTools::stringToLower(option);
126 for (auto&& item : list) {
127 std::string lowered_item = StringTools::stringToLower(item);
128 if (lowered_item == lowered_option
129 || (enableAll && lowered_item == "all")) {
130 return true;
131 }
132 }
133 return false;
134}
135
136/**
137 * Find out all operations we can generate from DAG.
138 */
139std::vector<IDF::FUGenerated::DAGOperation>
141 const std::vector<IDF::FUGenerated::Info> infos,
142 std::ostream& verbose) {
143 std::vector<IDF::FUGenerated::DAGOperation> dagops;
144 std::set<std::string> opNames;
145
146 verbose << " can implement DAG operations that use:\n ";
147 std::string sep;
148 for (auto&& info : infos) {
149 verbose << sep << info.operationName;
150 sep = ", ";
151 }
152 verbose << "\n";
153
154 OperationPool opPool;
155 OperationIndex& opIndex = opPool.index();
156 for (int i = 0; i < opIndex.moduleCount(); ++i) {
157 OperationModule& module = opIndex.module(i);
158 for (int j = 0; j < opIndex.operationCount(module); ++j) {
159 std::string opName = opIndex.operationName(j, module);
160 if (opNames.count(opName) > 0) {
161 continue;
162 }
163 Operation& op = opPool.operation(opName.c_str());
164 for (int d = 0; d < op.dagCount(); ++d) {
165 std::vector<IDF::FUGenerated::Info> subops;
166 if (canGenerateFromDAG(op.dag(d), infos, &subops)) {
167 opName = StringTools::stringToLower(opName);
168 dagops.emplace_back(IDF::FUGenerated::DAGOperation{opName,
169 subops});
170 opNames.insert(opName);
171 break;
172 }
173 }
174 }
175 }
176
177 verbose << " can implement DAG operations:\n ";
178 sep = "";
179 for (auto&& op : dagops) {
180 verbose << sep << op.operationName;
181 sep = ", ";
182 }
183 verbose << "\n";
184
185 return dagops;
186}
187
188/**
189 * Checks if DAG operation can be implemented, i.e. all basic operations
190 * can be implemented
191 */
192bool
194 const std::vector<IDF::FUGenerated::Info> infos,
195 std::vector<IDF::FUGenerated::Info>* subops) {
196 if (dag.isNull()) {
197 return false;
198 }
199
200 bool canImplement = true;
201 for (int n = 0; n < dag.nodeCount(); ++n) {
202 OperationNode* operationNode =
203 dynamic_cast<OperationNode*>(&dag.node(n));
204 if (operationNode) {
205 std::string operation = operationNode->referencedOperation().name();
206 operation = StringTools::stringToLower(operation);
207
208 bool foundOperation = false;
209 for (auto&& info : infos) {
210 if (info.operationName == operation) {
211 foundOperation = true;
212 if (subops) {
213 subops->emplace_back(info);
214 }
215 break;
216 }
217 }
218 if (foundOperation == false) {
219 canImplement = false;
220 break;
221 }
222
223 }
224 }
225 return canImplement;
226}
227
228/**
229 * Finds the maximum latency of the dag. Uses maxOpLatency for
230 * the node latencies.
231 */
232int
234 const std::unordered_map<std::string, int>& maxOpLatency) {
235 assert(!dag.isNull());
236
237 int maxLatency = 0;
238
239 // To find the global critical path, go through every end terminal's
240 // critical path and find the maximum.
241 auto sinkNodes = dag.sinkNodes();
242 for (auto node : sinkNodes) {
243 int latency = maxLatencyToNode(dag, *node, maxOpLatency);
244 maxLatency = std::max(latency, maxLatency);
245 }
246 return maxLatency;
247}
248
249int
251 OperationDAGNode& node,
252 const std::unordered_map<std::string, int>& maxOpLatency) {
253
254 int latency = 0;
255
256 OperationNode* operationNode = dynamic_cast<OperationNode*>(&node);
257 if (operationNode) {
258 std::string subOpName = operationNode->referencedOperation().name();
259 subOpName = StringTools::stringToLower(subOpName);
260 if (maxOpLatency.find(subOpName) != maxOpLatency.end()) {
261 latency = maxOpLatency.at(subOpName);
262 }
263 }
264
265 return latency;
266}
267
268/*
269 Starting from the given node, find the maximum implementation
270 latency. Used to schedule the starting cycles of node operations.
271*/
272int
274 const OperationDAG& dag, OperationDAGNode& node,
275 const std::unordered_map<std::string, int>& maxOpLatency,
276 bool allowDifference) {
277
278 // Go through all the parents.
279 int maxLeafLatency = -1;
280 for (auto&& e : dag.inEdges(node)) {
281 OperationDAGNode& nextNode = dag.tailNode(*e);
282 // Recursive call to parent nodes
283 int parentLatency = maxLatencyToNode(dag, nextNode, maxOpLatency)
284 + nodeLatency(nextNode, maxOpLatency);
285
286 if (!allowDifference && maxLeafLatency != -1) {
287 assert(maxLeafLatency == parentLatency &&
288 "Two input edges of DAG node have different latency!");
289 }
290
291 maxLeafLatency = std::max(maxLeafLatency, parentLatency);
292 }
293
294 // For nodes without children
295 maxLeafLatency = std::max(maxLeafLatency, 0);
296
297 // Return only the longest leaf latency.
298 return maxLeafLatency;
299}
300
301/**
302 * Parses all given hdbs for operation implementations.
303 */
304std::vector<IDF::FUGenerated::Info>
306 const ProGeOptions& options, std::ostream& verbose) {
307 std::vector<IDF::FUGenerated::Info> infos;
308
309 for (auto&& hdb : options.hdbList) {
310 std::string hdbPath = findHDBPath(hdb);
311 verbose << " searching implementations from " << hdbPath << "\n";
312 HDB::CachedHDBManager& manager =
314 std::set<RowID> rows = manager.OperationImplementationIDs();
315 std::vector<IDF::FUGenerated::Info> newInfos;
316 for (auto&& row : rows) {
317 auto opimpl = manager.OperationImplementationByID(row);
318 newInfos.emplace_back(IDF::FUGenerated::Info{opimpl.name, hdbPath,
319 opimpl.id, opimpl.latency});
320 }
321
322 std::sort(newInfos.begin(), newInfos.end(),
324 { return a.latency > b.latency; });
325
326 infos.insert(infos.end(), newInfos.begin(), newInfos.end());
327 }
328
329 return infos;
330}
331
332/**
333 * Tries to find full path for hdb file.
334 */
335std::string Automagic::findHDBPath(std::string name) {
336
337 if (FileSystem::fileExists(name)) {
338 return name;
339 }
340
341 std::vector<std::string> paths = Environment::hdbPaths();
342 return FileSystem::findFileInSearchPaths(paths, name);
343}
344
345/**
346 * Checks if FU has an implementation in hdbs.
347 */
350 std::ostream& verbose) {
351 (void)verbose;
352 for (auto&& hdb : options.hdbList) {
353 std::string hdbPath = findHDBPath(hdb);
354 HDB::CachedHDBManager& manager =
356 std::set<RowID> rows = manager.fuEntryIDs();
357 for (auto&& row : rows) {
358 auto fuEntry = manager.fuByEntryID(row);
359 if (!fuEntry->hasImplementation() ||
360 !fuEntry->hasArchitecture()) {
361 continue;
362 }
363 auto arch = fuEntry->architecture();
364 auto impl = fuEntry->implementation();
365 // Check that operations match.
366 if (fu.operationCount() !=
367 arch.architecture().operationCount()) {
368 continue;
369 }
370 bool wrongLanguage = false;
371 for (int i = 0; i < impl.implementationFileCount(); ++i) {
372 auto f = impl.file(i);
373 if (f.format() ==
375 options.language == ProGe::HDL::Verilog) {
376 wrongLanguage = true;
377 break;
378 } else if (f.format() == HDB::BlockImplementationFile::
379 Format::Verilog &&
380 options.language == ProGe::HDL::VHDL) {
381 wrongLanguage = true;
382 break;
383 }
384 }
385 if (wrongLanguage) {
386 continue;
387 }
388 bool found = true;
389 for (int i = 0; i < fu.operationCount(); ++i) {
390 auto op = fu.operation(i);
391 if (!arch.architecture().hasOperation(op->name())) {
392 found = false;
393 break;
394 }
395 if (op->latency() !=
396 arch.architecture().operation(op->name())->latency()) {
397 found = false;
398 break;
399 }
400 }
401 if (!found) {
402 continue;
403 }
404
405 loc.setID(row);
406 loc.setHDBFile(hdbPath);
407 return true;
408 }
409 }
410
411 return false;
412}
413
414/**
415 * Checks if RF has an implementation in hdbs.
416 */
419 std::ostream& verbose) {
420 (void)verbose;
421 for (auto&& hdb : options.hdbList) {
422 std::string hdbPath = findHDBPath(hdb);
423 HDB::CachedHDBManager& manager =
425 std::set<RowID> rows = manager.rfEntryIDs();
426 for (auto&& row : rows) {
427 auto rfEntry = manager.rfByEntryID(row);
428 // Exclude these:
429 if (!rfEntry->hasImplementation() ||
430 !rfEntry->hasArchitecture()) {
431 continue;
432 }
433 auto arch = rfEntry->architecture();
434 auto impl = rfEntry->implementation();
435 bool wrongLanguage = false;
436 for (int i = 0; i < impl.implementationFileCount(); ++i) {
437 auto f = impl.file(i);
438 if (f.format() ==
440 options.language == ProGe::HDL::Verilog) {
441 wrongLanguage = true;
442 break;
443 } else if (f.format() == HDB::BlockImplementationFile::
444 Format::Verilog &&
445 options.language == ProGe::HDL::VHDL) {
446 wrongLanguage = true;
447 break;
448 }
449 }
450 if (wrongLanguage) {
451 continue;
452 }
453 if (rf.isUsedAsGuard() != arch.hasGuardSupport()) {
454 continue;
455 }
456 if (rf.outputPortCount() != arch.readPortCount()) {
457 continue;
458 }
459 if (rf.inputPortCount() != arch.writePortCount()) {
460 continue;
461 }
462 if (rf.bidirPortCount() != arch.bidirPortCount()) {
463 continue;
464 }
465 if (1 != arch.latency()) {
466 continue;
467 }
468 if (rf.guardLatency() != arch.guardLatency()) {
469 continue;
470 }
471 if (!arch.hasParameterizedWidth() &&
472 (rf.width() != arch.width())) {
473 continue;
474 }
475 if (!arch.hasParameterizedSize() &&
476 (rf.size() != arch.size())) {
477 continue;
478 }
479 // Must be a perfect choise.
480 loc.setID(row);
481 loc.setHDBFile(hdbPath);
482 return true;
483 }
484 }
485 return false;
486}
487
488/**
489 * Checks if RF has an implementation in hdbs.
490 */
493 std::ostream& verbose) {
494 (void)verbose;
495 for (auto&& hdb : options.hdbList) {
496 std::string hdbPath = findHDBPath(hdb);
497 HDB::CachedHDBManager& manager =
499 std::set<RowID> rows = manager.rfEntryIDs();
500 for (auto&& row : rows) {
501 auto rfEntry = manager.rfByEntryID(row);
502 // Exclude these:
503 if (!rfEntry->hasImplementation() ||
504 !rfEntry->hasArchitecture()) {
505 continue;
506 }
507 auto arch = rfEntry->architecture();
508 auto impl = rfEntry->implementation();
509 bool wrongLanguage = false;
510 for (int i = 0; i < impl.implementationFileCount(); ++i) {
511 auto f = impl.file(i);
512 if (f.format() ==
514 options.language == ProGe::HDL::Verilog) {
515 wrongLanguage = true;
516 break;
517 } else if (f.format() == HDB::BlockImplementationFile::
518 Format::Verilog &&
519 options.language == ProGe::HDL::VHDL) {
520 wrongLanguage = true;
521 break;
522 }
523 }
524 if (wrongLanguage) {
525 continue;
526 }
527 if (iu.isUsedAsGuard() != arch.hasGuardSupport()) {
528 continue;
529 }
530 if (iu.maxReads() != arch.readPortCount()) {
531 continue;
532 }
533 if (1 != arch.writePortCount()) {
534 continue;
535 }
536 if (iu.latency() != arch.latency()) {
537 continue;
538 }
539 if (!arch.hasParameterizedWidth() &&
540 (iu.width() != arch.width())) {
541 continue;
542 }
543 if (!arch.hasParameterizedSize() &&
544 (iu.size() != arch.size())) {
545 continue;
546 }
547 // Must be a perfect choise.
548 loc.setID(row);
549 loc.setHDBFile(hdbPath);
550 return true;
551 }
552 }
553 return false;
554}
#define assert(condition)
static MachInfoCmdLineOptions options
Definition MachInfo.cc:46
int nodeCount() const
Node & node(const int index) const
virtual Node & tailNode(const Edge &edge) const
virtual NodeSet sinkNodes() const
virtual EdgeSet inEdges(const Node &node) const
static std::vector< std::string > hdbPaths(bool libraryPathsOnly=false)
static std::string findFileInSearchPaths(const std::vector< std::string > &searchPaths, const std::string &file)
static bool fileExists(const std::string fileName)
static CachedHDBManager & instance(const std::string &hdbFile)
FUArchitecture & architecture() const
Definition FUEntry.cc:129
FUEntry * fuByEntryID(RowID id) const
std::set< RowID > OperationImplementationIDs() const
OperationImplementation OperationImplementationByID(RowID id) const
std::set< RowID > rfEntryIDs() const
RFEntry * rfByEntryID(RowID id) const
std::set< RowID > fuEntryIDs() const
RFArchitecture & architecture() const
Definition RFEntry.cc:145
void addOperation(const Info &op)
std::string name() const
virtual void setHDBFile(std::string file)
bool isNull() const
std::string operationName(int i, const OperationModule &om)
int operationCount(const OperationModule &om)
int moduleCount() const
Operation & referencedOperation() const
OperationIndex & index()
Operation & operation(const char *name)
virtual OperationDAG & dag(int index) const
Definition Operation.cc:148
virtual TCEString name() const
Definition Operation.cc:93
virtual int dagCount() const
Definition Operation.cc:134
static std::string stringToLower(const std::string &source)
virtual int size() const
virtual int width() const
virtual HWOperation * operation(const std::string &name) const
virtual int operationCount() const
virtual int latency() const
virtual int maxReads() const
virtual int guardLatency() const
virtual bool isUsedAsGuard() const
virtual int bidirPortCount() const
Definition Unit.cc:174
virtual int inputPortCount(bool countBidir=false) const
Definition Unit.cc:160
virtual int outputPortCount(bool countBidir=false) const
Definition Unit.cc:145
int dagLatency(const OperationDAG &dag, const std::unordered_map< std::string, int > &maxOpLatency)
bool checkForSelectableIU(const ProGeOptions &options, TTAMachine::ImmediateUnit &iu, IDF::IUImplementationLocation &loc, std::ostream &verbose)
std::vector< IDF::FUGenerated::DAGOperation > generateableDAGOperations(const std::vector< IDF::FUGenerated::Info > infos, std::ostream &verbose)
std::string findHDBPath(std::string name)
int maxLatencyToNode(const OperationDAG &dag, OperationDAGNode &node, const std::unordered_map< std::string, int > &maxOpLatency, bool allowDifference=true)
bool findInOptionList(const std::string &option, std::vector< std::string > list, bool enableAll=true)
std::vector< IDF::FUGenerated::Info > createFUGeneratableOperationInfos(const ProGeOptions &options, std::ostream &verbose)
int nodeLatency(OperationDAGNode &node, const std::unordered_map< std::string, int > &maxOpLatency)
bool checkForSelectableFU(const ProGeOptions &options, TTAMachine::FunctionUnit &fu, IDF::FUImplementationLocation &loc, std::ostream &verbose)
bool canGenerateFromDAG(const OperationDAG &dag, const std::vector< IDF::FUGenerated::Info > infos, std::vector< IDF::FUGenerated::Info > *subops)
bool checkForGeneratableFU(const ProGeOptions &options, TTAMachine::FunctionUnit &fu, IDF::FUGenerated &fug, const std::vector< IDF::FUGenerated::Info > &infos, const std::vector< IDF::FUGenerated::DAGOperation > dagops)
bool checkForSelectableRF(const ProGeOptions &options, TTAMachine::RegisterFile &rf, IDF::RFImplementationLocation &loc, std::ostream &verbose)
@ Verilog
Verilog.
Definition ProGeTypes.hh:42
@ VHDL
VHDL.
Definition ProGeTypes.hh:41