OpenASIP 2.2
Loading...
Searching...
No Matches
OperationDAGSelector.cc
Go to the documentation of this file.
1/*
2 Copyright (c) 2002-2009 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 OperationDAGSelector.cc
26 *
27 * Definition of OperationDAGSelector class.
28 *
29 * @author Mikael Lepistö 2008 (mikael.lepisto-no.spam-tut.fi)
30 * @note rating: red
31 */
32
34#include "OperationPool.hh"
35#include "Operation.hh"
36#include "OperationNode.hh"
37#include "ConstantNode.hh"
38#include "TCEString.hh"
39#include "ImmInfo.hh"
40
41/**
42 * Returns a list of dags of an operation, which use only
43 * given set of operations.
44 *
45 * Additionally, immediate info can be provided to this function. The info
46 * describes immediate transport capabilities to the operands of the (known)
47 * operations. ImmInfo discards dags that have constant values bound to operand
48 * that can not have the immediate transported to.
49 *
50 * @param opName Name of operation whose DAGs are requested.
51 * @param opSet Set of operations that are allowed to be referred by
52 * the returned DAGs.
53 * @param immInfo The immediate info.
54 * @return List of DAGs which comply the search parameters.
55 */
58 const std::string& opName,
59 OperationSet opSet,
60 const ImmInfo* immInfo) {
61
62 OperationDAGList retDags;
63 OperationPool opPool;
64 Operation& op = opPool.operation(opName.c_str());
65
66 for (int i = 0; i < op.dagCount(); i++) {
67 OperationDAG& currDag = op.dag(i);
68
69 if (op.dagError(i) != "") {
70 throw IllegalParameters(__FILE__,__LINE__,__func__,
71 TCEString("Operation:") + op.name()
72 + " has invalid dag, index: " + Conversion::toString(i)
73 + "\n\tError: " + op.dagError(i));
74 }
75
76 if (countUnknownOperations(currDag, opSet) != 0) {
77 continue; // Discard the dag with unsupported operations
78 }
79
80 if (immInfo) {
81 bool discardDag = false;
82 for (int i = 0; i < currDag.nodeCount(); i++) {
83 const ConstantNode* cNode =
84 dynamic_cast<ConstantNode*>(&currDag.node(i));
85 if (cNode == nullptr) continue;
86
87 for (auto& edge : currDag.outEdges(*cNode)) {
88 const OperationNode* opNode = dynamic_cast<OperationNode*>(
89 &currDag.headNode(*edge));
90 assert(opNode &&
91 "Operation DAG node is other than OperationNode.");
92
93 if (immInfo->count(
94 opNode->referencedOperation(),
95 edge->dstOperand())) {
96 // TODO check if constant can be encoded as short
97 // immediate.
98
99 // TODO: should check if the operand can be swapped.
100 // If so, alter the dag to get the better immediate
101 // transport support.
102 } else {
103 discardDag = true;
104 break;
105 }
106 }
107 if (discardDag) break;
108 }
109 if (discardDag) {
110 continue;
111 }
112 }
113 retDags.push_back(&currDag);
114 }
115
116 return retDags;
117}
118
119/**
120 * Returns number of operations that DAG contains which are
121 * not in given opset.
122 *
123 * Currently does not check recursively, but only one level used operations.
124 *
125 * @param dag DAG which is checked.
126 * @param opSet Operations that are found.
127 * @return Number of operations that DAG contains that did not exist in opset.
128 */
129int
131 OperationDAG& dag, OperationSet& opSet) {
132
133 int strangeOpCount = 0;
134
135 for (int i = 0; i < dag.nodeCount(); i++) {
136 OperationNode* node = dynamic_cast<OperationNode*>(&dag.node(i));
137
138 // check if operation was found from opset
139 if (node != NULL) {
140 Operation& refOp = node->referencedOperation();
141
142 if (opSet.find(refOp.name()) == opSet.end()) {
143 strangeOpCount++;
144 }
145 }
146 }
147
148 return strangeOpCount;
149}
150
151/**
152 * Tries to find simplest graph that is expanded with given opset.
153 *
154 * @todo Implement function when neccessary. Right now returns DAG for
155 * operation that has smallest number of operations that are not
156 * found in given opset.
157 *
158 * @param op Operation whose expanded dag is requested.
159 * @param opSet Operation names which are allowed to use for expanding.
160 * @return Dynamically allocated DAG for operation expanded with given opset.
161 * OperationDAG::null if there is no dag for operation.
162 */
165 const Operation& op, OperationSet& opSet) {
166
167 OperationDAGList foundDags;
168 int lastUnknownOperations = INT_MAX;
169
170 // find DAG that has lowest cont of operations that are not in opset
171 for (int i = 0; i < op.dagCount(); i++) {
172 OperationDAG& currDag = op.dag(i);
173 int strangeCount = countUnknownOperations(currDag, opSet);
174
175 if (strangeCount <= lastUnknownOperations) {
176
177 if (strangeCount < lastUnknownOperations) {
178 lastUnknownOperations = strangeCount;
179 foundDags.clear();
180 }
181
182 foundDags.push_back(&currDag);
183 }
184 }
185
186 OperationDAG& selectedDag = foundDags.smallestNodeCount();
187
188 if (selectedDag.isNull()) {
189 return &selectedDag;
190 } else {
191 return new OperationDAG(selectedDag);
192 }
193}
#define __func__
#define assert(condition)
virtual Node & headNode(const Edge &edge) const
int nodeCount() const
Node & node(const int index) const
virtual EdgeSet outEdges(const Node &node) const
static std::string toString(const T &source)
size_t count(const ImmInfoKey &key) const
Definition ImmInfo.hh:87
static OperationDAG * createExpandedDAG(const Operation &op, OperationSet &opSet)
static int countUnknownOperations(OperationDAG &dag, OperationSet &opSet)
TCETools::CIStringSet OperationSet
static OperationDAGList findDags(const std::string &opName, OperationSet opSet, const ImmInfo *immInfo=nullptr)
bool isNull() const
Operation & referencedOperation() const
Operation & operation(const char *name)
virtual OperationDAG & dag(int index) const
Definition Operation.cc:148
virtual TCEString name() const
Definition Operation.cc:93
virtual TCEString dagError(int index) const
Definition Operation.cc:182
virtual int dagCount() const
Definition Operation.cc:134