OpenASIP 2.2
Loading...
Searching...
No Matches
BFLateBypasses.cc
Go to the documentation of this file.
1/*
2 Copyright (c) 2002-2014 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/**
26 * @file BFLateBypasses.cc
27 *
28 * Definition of BFLateBypasses class
29 *
30 * Before scheduling a result move, searches for moves which might be a
31 * bypass destinations for this result and then tries to call BFLateBypass
32 * class to bypass these.
33 *
34 * @author Heikki Kultala 2014-2020(heikki.kultala-no.spam-tuni.fi)
35 * @note rating: red
36 */
37#include "BFLateBypasses.hh"
40#include "Move.hh"
41#include "Terminal.hh"
42#include "BFLateBypass.hh"
43#include "BFDRELate.hh"
44#include "ResourceManager.hh"
46#include "Port.hh"
48#include "BFLateBypassGuard.hh"
49#include "Machine.hh"
50
51#include <map>
52
54 BFOptimization(sched), src_(src), lc_(lc), removedSource_(false),
55 bypassDistance_(5) {
58 if (opts != NULL) {
59 if (opts->bypassDistance() > -1) {
61 }
62 }
63}
64
65bool
67
68 int variableDstCount = 0;
69 bool bypassed = false;
70 auto rrDestinations =
72
73 // the boolean specifies whether this is normal or guard bypass.
74 std::map<MoveNode*, bool, MoveNode::Comparator> bypassDestinations;
75
76 int earliestDst = INT_MAX;
77 // first just search all potentials.
78 for (auto i : rrDestinations) {
79 MoveNode* n = i.second;
80 int guardParam = i.first->guardUse() ? 1 : 2;
81 // TODO: the rootgraph here prevents over-loop-edge bypass.
82 // TODO: enable over-loop-edge bypass when it works.
83 // Needs update to ddg.mergeAndKeep() to put backedge
84 // properties and BFOptimization::assign() to keep original
85 // register in prolog. (create copy MN of original for prolog
86 // when bypassing?
87 if ((static_cast<DataDependenceGraph*>(ddg().rootGraph()))->
88 onlyRegisterRawSource(*n, guardParam) == NULL) {
89 continue;
90 }
91
92 // not guard but normal read
93 if (guardParam == 2) {
94 MachineConnectivityCheck::PortSet destinationPorts;
95 destinationPorts.insert(&n->move().destination().port());
96
98 src_, destinationPorts)) {
99 if (n->isScheduled() == false
100 && (static_cast<SimpleResourceManager&>(
101 rm()).initiationInterval() != 0)) {
102 // Found node connected by loop edge, ignore it.
103 continue;
104 }
105#ifdef DEBUG_BUBBLEFISH_SCHEDULER
106 std::cerr << "\t\tFound ok bypass dest: " << n->toString()
107 << std::endl;
108#endif
109
110 if (!ddg().guardsAllowBypass(src_, *n)) {
111#ifdef DEBUG_BUBBLEFISH_SCHEDULER
112 std::cerr << "\t\tGuards do not allow bypass to: "
113 << n->toString() << std::endl;
114#endif
115 continue;
116 }
117
118 assert(n->isScheduled());
119 int originalCycle = n->cycle();
120 int earliestLimit = originalCycle - bypassDistance_;
121 if (lc_ < earliestLimit) {
122#ifdef DEBUG_BUBBLEFISH_SCHEDULER
123 std::cerr << "\t\t\tcycle limites prevent late bypass "
124 << std::endl;
125#endif
126 continue;
127 }
128 earliestDst = std::min(earliestDst, originalCycle);
129 bypassDestinations.insert(std::make_pair(n, false));
130 }
131 } else {
132 // TODO: test if guard bypass possible.
133 // now handled in the guard bypass class itself.
134 assert(n->isScheduled());
135 int originalCycle = n->cycle();
136 int earliestLimit = originalCycle - bypassDistance_;
137 if (lc_ < earliestLimit) {
138#ifdef DEBUG_BUBBLEFISH_SCHEDULER
139 std::cerr << "\t\t\tcycle limites prevent late bypass "
140 << std::endl;
141#endif
142 continue;
143 }
144 earliestDst = std::min(earliestDst, originalCycle);
145 bypassDestinations.insert(std::make_pair(n, true));
146 }
147 }
148
149 // Do the critical one first. This may force the source FU.
150 for (auto n : bypassDestinations) {
151 if (n.first->cycle() == earliestDst) {
152 if (!n.second) {
153
154 // if always write results,
155 // op cannot have more than one register target.
158 n.first->isDestinationVariable() &&
159 variableDstCount>0) {
160 continue;
161 }
162
163 BFLateBypass* lbp =
164 new BFLateBypass(sched_, src_, *n.first, lc_);
165 if (runPreChild(lbp)) {
166 bypassed = true;
167 if (n.first->isDestinationVariable()) {
168 variableDstCount++;
169 }
170 }
171 bypassDestinations.erase(n.first);
172 break;
173 } else {
174#ifdef DEBUG_BUBBLEFISH_SCHEDULER
175 std::cerr << "\nAttempting guard bypass from: " <<
176 src_.toString() << " to: " << n.first->toString()
177 << std::endl;
178#endif
179 // guard bypass
180 BFLateBypassGuard* lbp =
181 new BFLateBypassGuard(sched_, src_, *n.first, lc_);
182 if (runPreChild(lbp)) {
183 bypassed = true;
184#ifdef DEBUG_BUBBLEFISH_SCHEDULER
185 std::cerr << "\tguard bypass ok." << std::endl;
186 } else {
187 std::cerr << "\tGuard bypass failed." << std::endl;
188#endif
189 }
190 bypassDestinations.erase(n.first);
191 break;
192 }
193 }
194 }
195
196 // then actually do the bypass for the other, non-critical moves
197 for (auto n : bypassDestinations) {
198 if (!n.second) {
199 // if always write results,
200 // op cannot have more than one register target.
203 n.first->isDestinationVariable() &&
204 variableDstCount>0) {
205 continue;
206 }
207
208 int originalCycle = n.first->cycle();
209 if (originalCycle > earliestDst + bypassDistance_) {
210 continue;
211 }
212 BFLateBypass* lbp = new BFLateBypass(sched_, src_, *n.first, lc_);
213 if (runPreChild(lbp)) {
214 bypassed = true;
215 if (n.first->isDestinationVariable()) {
216 variableDstCount++;
217 }
218 }
219 }
220 }
221 if (!bypassed) {
222 return false;
223 }
224
225 // if always write results,
226 // op must have exactly one register target.
227 if (targetMachine().alwaysWriteResults() &&
229 // if none of the bypassed are to reg,
230 // may not DRE
231 if (variableDstCount == 0) {
232 return true;
233 }
234 assert(variableDstCount == 1);
235 // if one of the bypasses are to reg,
236 // MUST dre.
237 BFDRELate* dre = new BFDRELate(sched_, src_);
238 if (runPostChild(dre)) {
239 removedSource_ = true;
240 return true;
241 } else {
243 return false;
244 }
245 }
246
247 BFDRELate* dre = new BFDRELate(sched_, src_);
248 if (runPostChild(dre)) {
249 removedSource_ = true;
250#ifdef DEBUG_BUBBLEFISH_SCHEDULER
251 std::cerr << "DRE ok!" << std::endl;
252 } else {
253 std::cerr << "Could not DRE away: " << src_.toString() << std::endl;
254#endif
255 }
256 return true;
257}
#define assert(condition)
find Finds info of the inner loops in the false
static CmdLineOptions * cmdLineOptions()
BFLateBypasses(BF2Scheduler &sched, MoveNode &src, int lc)
virtual bool operator()()
BF2Scheduler & sched_
DataDependenceGraph & ddg()
const TTAMachine::Machine & targetMachine() const
SimpleResourceManager & rm() const
std::map< DataDependenceEdge *, MoveNode *, DataDependenceEdge::Comparator > onlyRegisterRawDestinationsWithEdges(const MoveNode &mn, bool allowBackEdges) const
bool guardsAllowBypass(const MoveNode &defNode, const MoveNode &useNode, bool loopBypass=false)
static int canSourceWriteToAnyDestinationPort(const MoveNode &src, PortSet &ports, bool ignoreGuard=false)
std::set< const TTAMachine::Port *, const TTAMachine::MachinePart::Comparator > PortSet
int cycle() const
Definition MoveNode.cc:421
std::string toString() const
Definition MoveNode.cc:576
TTAProgram::Move & move()
bool isSourceOperation() const
Definition MoveNode.cc:168
bool isScheduled() const
Definition MoveNode.cc:409
bool runPostChild(Reversible *preChild)
void undoAndRemovePreChildren()
Definition Reversible.cc:80
bool runPreChild(Reversible *preChild)
bool alwaysWriteResults() const
Definition Machine.cc:948
Terminal & destination() const
Definition Move.cc:323
virtual const TTAMachine::Port & port() const
Definition Terminal.cc:378