OpenASIP 2.2
Loading...
Searching...
No Matches
CycleLookBackSoftwareBypasser.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 CycleLookBackSoftwareBypasser.cc
26 *
27 * Definition of CycleLookBackSoftwareBypasser interface.
28 *
29 * @author Pekka Jääskeläinen 2007 (pjaaskel-no.spam-cs.tut.fi)
30 * @author Vladmír Guzma 2008 (vg-no.spam-cs.tut.fi)
31 * @author Heikki Kultala 2008 (hkultala-no.spam-cs.tut.fi)
32 * @note rating: red
33 */
34
36
37#include "MoveNodeGroup.hh"
39#include "ResourceManager.hh"
40#include "MapTools.hh"
41#include "TerminalFUPort.hh"
43#include "MoveNodeSelector.hh"
44#include "MoveGuard.hh"
45#include "Guard.hh"
46#include "Bus.hh"
49#include "ProgramOperation.hh"
50#include "Move.hh"
51// DEBUG:
53#include "Instruction.hh"
54#include "POMDisassembler.hh"
55#include "TerminalImmediate.hh"
56
57//#define MOVE_BYPASSER
58/**
59 * Constructor.
60 *
61 */
63 cyclesToLookBack_(5), cyclesToLookBackNoDRE_(1),
64 killDeadResults_(true), bypassFromRegs_(true), bypassToRegs_(true),
65 selector_(NULL) {
66
69 if (opts != NULL) {
70 if (opts->bypassDistance() > -1) {
72 }
73 if (opts->noDreBypassDistance() > -1) {
75 }
77 }
78}
79
80/**
81 * Empty destructor.
82 */
85
86/**
87 * Tries to bypass a MoveNode.
88 *
89 * @param moveNode MoveNode to bypass.
90 * @param lastOperandCycle in which contains last cycle of operands of the
91 * operation
92 * @param ddg The data dependence graph in which the movenodes belong to.
93 * @param rm The resource manager which is used to check for resource
94 * availability.
95 * @return -1 if failed and need fixup, 1 is succeeded, 0 if did not bypass.
96 */
97int
99 MoveNode& moveNode,
100 int& lastOperandCycle,
102 ResourceManager& rm) {
103
104 int cyclesToLookBack = cyclesToLookBack_;
105 if (moveNode.isDestinationVariable() && !bypassToRegs_) {
106 return 0;
107 }
108
109 int originalCycle = moveNode.cycle();
110 int latestCycle = originalCycle;
111
112 DataDependenceGraph::EdgeSet edges = ddg.inEdges(moveNode);
113 DataDependenceGraph::EdgeSet::iterator edgeIter = edges.begin();
114 DataDependenceEdge* bypassEdge = NULL;
115
116 // find one incoming raw edge. if multiple, cannot bypass.
117 while (edgeIter != edges.end()) {
118
119 DataDependenceEdge& edge = *(*edgeIter);
120 // if the edge is not a real reg/ra raw edge, skip to next edge
123 edge.guardUse() || edge.headPseudo()) {
124 edgeIter++;
125 continue;
126 }
127
128 if (bypassEdge == NULL) {
129 bypassEdge = &edge;
130 } else {
131 // cannot bypass if multiple inputs
132 return 0;
133 }
134 edgeIter++;
135 }
136
137 // if no bypassable edge found, cannot bypass
138 if (bypassEdge == NULL || bypassEdge->isBackEdge()) {
139 return 0;
140 }
141
142 MoveNode& source = ddg.tailNode(*bypassEdge);
143
144 if (!source.isScheduled()) {
145 return 0;
146 }
147
148 // don't bypass from incoming tempregcopies of immediates
149 if (source.isSourceConstant() &&
150 source.move().hasAnnotations(
152 return 0;
153 }
154
155 // if cannot kill dead result, divide bypass dist by 2
156 if (source.isSourceOperation() &&
157 moveNode.isDestinationOperation() &&
158 cyclesToLookBack != INT_MAX &&
159 cyclesToLookBack > cyclesToLookBackNoDRE_ &&
160 (ddg.regRawSuccessorCount(source, true) > 1 ||
161 ddg.regRawSuccessorCount(source, false) <
162 static_cast<DataDependenceGraph*>(ddg.rootGraph())->
163 regRawSuccessorCount(source, false))) {
164 cyclesToLookBack = cyclesToLookBackNoDRE_;
165 }
166
167 // source node is too far for our purposes
168 // do not bypass this operand
169 if (cyclesToLookBack != INT_MAX &&
170 source.cycle() + cyclesToLookBack < moveNode.cycle()) {
171 return 0;
172 }
173
174 if (!ddg.guardsAllowBypass(source, moveNode)) {
175 return 0;
176 }
177
178 // if dest register, only allow input from reg or imm.
179 // and limit the read to same as original read
180 // in order to not make live ranges longer, limiting schdule
181 if (!moveNode.isDestinationOperation()) {
182 latestCycle = source.cycle();
183 }
184 if (!(source.isSourceOperation() || source.isSourceConstant())) {
185 if (!bypassFromRegs_) {
186 return 0;
187 }
188 // handle antidependencies from reg-reg moves.
190 ddg.regWarSuccessors(source);
191 for (DataDependenceGraph::NodeSet::iterator i = warSuccs.begin();
192 i != warSuccs.end();i++) {
193 MoveNode& mn = **i;
194 if (mn.isScheduled()) {
195 if (mn.cycle() < latestCycle) {
196 latestCycle = std::min(latestCycle, mn.cycle());
197 }
198 }
199 }
200
201 // redundant latest check to prevent loops in ddg.
202 for (edgeIter = edges.begin(); edgeIter != edges.end(); edgeIter++) {
203 DataDependenceEdge& edge = **edgeIter;
204 if (&edge != bypassEdge) {
205 MoveNode& tail = ddg.tailNode(edge);
206 if (!tail.isScheduled()) {
207 return 0;
208 }
210 if (tail.cycle() > latestCycle) {
211 return 0;
212 }
213 } else {
214 if (tail.cycle() > latestCycle-1) {
215 return 0;
216 }
217 }
218 }
219 }
220 }
221 rm.unassign(moveNode);
222 storedSources_.insert(
223 std::pair<MoveNode*, MoveNode*>(&moveNode, &source));
224
225 // if mergeandkeep fails, undo bypass and return 0
226 if (!ddg.mergeAndKeepUser(source, moveNode)) {
227 rm.assign(originalCycle, moveNode);
228 assert(moveNode.isScheduled());
229 storedSources_.erase(&moveNode);
230 return 0;
231 }
232
233 if (moveNode.move().source().isImmediateRegister()) {
234 moveNode.move().setSource(
235 static_cast<SimpleResourceManager&>(rm).immediateValue(source)->copy());
236 }
237
238 // then try to assign the bypassed node..
239 int ddgCycle = ddg.earliestCycle(moveNode);
240 if (!moveNode.move().isUnconditional()) {
241 ddgCycle = std::max(ddgCycle, moveNode.guardLatency() - 1);
242 }
243 if (ddgCycle != INT_MAX) {
244#ifdef MOVE_BYPASSER
245 ddgCycle = originalCycle;
246#endif
247 // remove dead results now?
248 int sourceCycle = source.cycle();
249 bool sourceRemoved = false;
250 // Check if machine is forcing disabling DRE,
251 // if so disable when first move is bypassed.
252 if (killDeadResults_ &&
253 source.move().bus().machine()->alwaysWriteResults()) {
254 killDeadResults_ = false;
255 }
256 // disable DRE if ii != 0
257 // only kill if dest is op
258
259 // >8058 fails
260 // >8059 works
261 if (killDeadResults_ && !ddg.resultUsed(source)) { // && source.nodeID() > 8058) {
262 // if restoring lated
263 sourceCycles_[&source] = sourceCycle;
264 sourceRemoved = true;
265 // results that has no "use" later and are overwritten are
266 // dead if there are some other edges we don't do anything
267 // Resuls is positively death
268 // we need to properly get rid of it
269 sourceBuses_[&source] = &source.move().bus();
270 rm.unassign(source);
271 }
272
273 int cycle = rm.earliestCycle(ddgCycle, moveNode);
274 if (cycle != -1 && cycle <= latestCycle) {
275 rm.assign(cycle, moveNode);
276 if (!moveNode.isScheduled()){
277 throw InvalidData(
278 __FILE__, __LINE__, __func__,
279 "Move assignment failed");
280 }
281 lastOperandCycle = std::max(lastOperandCycle, cycle);
282 // only one bypass per operand is possible, no point to
283 // test other edges of same moveNode
284 if (sourceRemoved) {
285 ddg.copyDepsOver(source, true, false);
286 }
287 bypassCount_++;
288 return 1;
289 } else {
290 // undo only this bypass.
291 // allow other moves of same po to be bypassed.
292 ddg.unMergeUser(source, moveNode);
293 if (!rm.canAssign(originalCycle, moveNode)) {
294 // Cannot return to original position. getting problematic.
295 // return source to it's position
296 if (sourceRemoved) {
297 assert(sourceBuses_[&source] != NULL);
298 source.move().setBus(*sourceBuses_[&source]);
299 assert(rm.canAssign(sourceCycle, source));
300 rm.assign(sourceCycle, source);
301 sourceCycles_.erase(&source);
302 sourceBuses_.erase(&source);
303 }
304 // Try if we can assign it to some earlier place.
305 ddgCycle = ddg.earliestCycle(moveNode);
306 if (!moveNode.move().isUnconditional()) {
307 ddgCycle = std::max(ddgCycle, moveNode.guardLatency()-1);
308 }
309 int ec = rm.earliestCycle(ddgCycle, moveNode);
310 if (ec != -1 && ec < originalCycle) {
311 rm.assign(ec, moveNode);
312 return 0;
313 } else {
314 // Need to abort bypassing.
315 return -1;
316 }
317 }
318 rm.assign(originalCycle, moveNode);
319 assert(moveNode.isScheduled());
320 storedSources_.erase(&moveNode);
321
322 // return source to it's position
323 if (sourceRemoved) {
324 assert(sourceBuses_[&source] != NULL);
325 source.move().setBus(*sourceBuses_[&source]);
326 assert(rm.canAssign(sourceCycle, source));
327 rm.assign(sourceCycle, source);
328 sourceCycles_.erase(&source);
329 sourceBuses_.erase(&source);
330 }
331 return 0;
332 }
333 }
334 // if node could not be bypassed, we return -1 and let
335 // BBScheduler call removeBypass
336 return -1;
337}
338
339/**
340 * Apply software bypassing to as many moves in the given MoveNodeGroup
341 * as possible.
342 *
343 * This implementation works only if all operand writes have been scheduled.
344 * It tries to bypass all the operand write moves.
345 *
346 * @param candidates The moves to which apply software bypassing, if possible.
347 * @param ddg The data dependence graph in which the movenodes belong to.
348 * @param rm The resource manager which is used to check for resource
349 * availability.
350 * @return The count of bypassed moves.
351 */
352int
354 MoveNodeGroup& candidates,
356 ResourceManager& rm,
357 bool bypassTrigger) {
358
359 // bypassing disabled with 0
360 if (cyclesToLookBack_ <= 0) {
361 return 0;
362 }
363#ifdef MOVE_BYPASSER
365#endif
366 int bypassCounter = 0;
367
368 MoveNode* trigger = NULL;
369 int lastOperandCycle = 0;
370
371 for (int i = 0; i < candidates.nodeCount(); i++) {
372 MoveNode& moveNode = candidates.node(i);
373
374 // result value or already bypassed - don't bypass this
375 if (moveNode.isSourceOperation()) {
376 continue;
377 }
378
379 // find the trigger, will try to bypass it as the last one
380 if (moveNode.move().isTriggering()) {
381 trigger = &moveNode;
382 continue;
383 }
384
385 // bypass this node.
386 int rv = bypassNode(moveNode, lastOperandCycle, ddg, rm);
387 if (rv == -1) {
388 return -1; // failed, need cleanup
389 } else {
390 bypassCounter += rv;
391 }
392 }
393 // Try to bypass triggering move, if possible ok, if not
394 // it will be rescheduled at the end after all not bypassed
395 // moves are tried to be rescheduled
396 bool triggerWasBypassed = false;
397 if (trigger != NULL && !trigger->move().isControlFlowMove() &&
398 !trigger->isSourceOperation() && bypassTrigger) {
399 int rv = bypassNode(*trigger, lastOperandCycle, ddg, rm);
400 if (rv == -1) {
401 return -1; // failed, need cleanup
402 } else {
403 bypassCounter += rv;
404 if (rv == 1) {
405 triggerWasBypassed = true;
406 }
407 }
408 }
409 // at this point the schedule might be broken in case we
410 // managed to bypass the trigger and it got pushed above
411 // an operand move
412
413 // try to reschedule the moves that were not bypassed because
414 // earlier operand moves might allow scheduling also the trigger
415 // earlier thus shorten the schedule
416
417 // this might fix the schedule in case the previous loop
418 // managed to push trigger above an operand move
419 // if not, the last loop fixes the situation
420
421 for (int i = 0; i < candidates.nodeCount(); i++) {
422 MoveNode& moveNode = candidates.node(i);
423 if (!moveNode.isDestinationOperation() ||
424 moveNode.move().isControlFlowMove()) {
425 continue;
426 }
427 // Bypassed moves and bypassed trigger are not rescheduled here
428 if (moveNode.isBypass() ||
429 (trigger == &moveNode && triggerWasBypassed)) {
430 lastOperandCycle =
431 std::max(lastOperandCycle, moveNode.cycle());
432 continue;
433 }
434 int oldCycle = moveNode.cycle();
435 int earliestCycleDDG = ddg.earliestCycle(moveNode);
436
437 if (earliestCycleDDG >= oldCycle) {
438 continue;
439 }
440 rm.unassign(moveNode);
441 int earliestCycle = earliestCycleDDG;
442
443 if (!moveNode.move().isUnconditional()) {
444 earliestCycle =
445 std::max(earliestCycleDDG, moveNode.guardLatency() - 1);
446 }
447 earliestCycle = rm.earliestCycle(earliestCycle, moveNode);
448 if ((oldCycle > earliestCycle && earliestCycle != -1) ||
449 (trigger == &moveNode && earliestCycle != -1)){
450 try {
451 rm.assign(earliestCycle, moveNode);
452 } catch (const Exception& e) {
453 throw ModuleRunTimeError(__FILE__, __LINE__, __func__,
455 }
456 } else {
457 try {
458 if (!rm.canAssign(oldCycle, moveNode)) {
459 return -1;
460 }
461 rm.assign(oldCycle, moveNode);
462 } catch (const Exception& e) {
463 throw ModuleRunTimeError(__FILE__, __LINE__, __func__,
465 }
466 }
467 lastOperandCycle =
468 std::max(lastOperandCycle, moveNode.cycle());
469 if (!moveNode.isScheduled()){
470 throw InvalidData(
471 __FILE__, __LINE__, __func__, "Move assignment failed");
472 }
473
474 }
475 // Traditional test if trigger is not earlier then some operand,
476 // could happen due to bypass of trigger
477 // todo: this could be optimized by trying to uxchange cycles of
478 // trigger and operand in this case.
479 if (trigger != NULL) {
480 try{
481 if (trigger->cycle() < lastOperandCycle) {
482 rm.unassign(*trigger);
483 int newCycle = rm.earliestCycle(lastOperandCycle, *trigger);
484 int latestDDG = ddg.latestCycle(*trigger);
485 if (newCycle == -1 || newCycle > latestDDG) {
487 // BBScheduler will call removeBypass
488 return -1;
489 }
490 rm.assign(newCycle, *trigger);
491 if (!trigger->isScheduled()){
492 throw InvalidData(
493 __FILE__, __LINE__, __func__,"Trigger assignment failed");
494 }
495 }
496 } catch (const Exception& e) {
497 throw ModuleRunTimeError(
498 __FILE__, __LINE__, __func__,e.errorMessageStack());
499 }
500 }
501 return bypassCounter;
502}
503
504/**
505 * Remove software bypassing from all moves in the given MoveNodeGroup
506 * if possible.
507 *
508 * @param candidates The moves from which to remove software bypassing, if
509 * possible.
510 * @param ddg The data dependence grap in which the movenodes belong to.
511 * @param rm The resource manager which is used to check for resource
512 * availability.
513 */
514void
516 MoveNodeGroup& candidates,
518 ResourceManager& rm) {
519
520 // bypassing disabled
521 if (cyclesToLookBack_ <= 0) {
522 return;
523 }
524
525 // Some of operand bypassing attempts failed
526 // Unschedule all operands, unassign them also since in BBSched
527 // this is followed by another attempt to schedule operands
528
529 for (int i = 0; i < candidates.nodeCount(); i++) {
530 MoveNode& moveNode = candidates.node(i);
531 if (moveNode.isScheduled()) {
532 rm.unassign(moveNode);
533 }
534 }
535
536 for (int k = 0; k < candidates.nodeCount(); k++) {
537 MoveNode& moveNode = candidates.node(k);
538 removeBypass(moveNode, ddg, rm);
539 }
540}
541
542void
544 MoveNode& moveNode,
546 ResourceManager& rm, bool restoreSource) {
547
548 // bypassing disabled
549 if (cyclesToLookBack_ <= 0) {
550 return;
551 }
552
553 if (MapTools::containsKey(storedSources_, &moveNode)) {
554 // if node was bypassed, find a original source
555 // and restore it, also unassign if bypass was
556 // assigned
557 MoveNode* tempSource =
559 assert(tempSource != NULL);
560 storedSources_.erase(&moveNode);
561 // if it was bypass and was scheduled we
562 // need to unassign and restore, should allways be a case
563 if (moveNode.isScheduled()) {
564 rm.unassign(moveNode);
565 }
566
567 // if we unassigned the source of the bypass, restore it.
568 if (!tempSource->isScheduled()) {
569 std::map<MoveNode*, int>::iterator cycleIter =
570 sourceCycles_.find(tempSource);
571 if (cycleIter != sourceCycles_.end()) {
572 if (restoreSource) {
573 assert(sourceBuses_[tempSource] != NULL);
574 tempSource->move().setBus(*sourceBuses_[tempSource]);
575 assert(rm.canAssign(cycleIter->second, *tempSource));
576 rm.assign(cycleIter->second, *tempSource); // fails here. somebody else uses the bus?
577 }
578 sourceCycles_.erase(cycleIter);
579 sourceBuses_.erase(tempSource);
580 }
581 }
582 ddg.unMergeUser(*tempSource, moveNode);
583 bypassCount_--;
584 }
585 // this is only for afterwards cleanup.
587 MoveNode* tempSource =
589 assert(tempSource != NULL);
590 removedStoredSources_.erase(&moveNode);
591
592 if (moveNode.isScheduled()) {
593 rm.unassign(moveNode);
594 }
595 ddg.unMergeUser(*tempSource, moveNode);
596 }
597}
598
599int
601 MoveNodeGroup& candidates,
603 ResourceManager& rm,
604 std::set<std::pair<TTAProgram::Move*, int> >& removedMoves) {
605
606 for (int i = 0; i < candidates.nodeCount(); i++) {
607 // For now, this version is called after operands AND results
608 // were scheduled
609 if (!candidates.node(i).isScheduled()) {
610 return 0;
611 }
612 }
613
614 // For each of bypassed moves, look for its original source and
615 // if that one has no more outgoing RAW edges and will be
616 // overwritten in same basic block (WAW edge) remove it
617
618 int resultsRemoved = 0;
619 for (int i = 0; i < candidates.nodeCount(); i++) {
620 MoveNode& moveNode = candidates.node(i);
621 // Results in candidates are freshly scheduled so they have no
622 // bypasses so far
623 if (!MapTools::containsKey(storedSources_, &moveNode)) {
624 // In case the result was already removed by other move from same
625 // candidates set (both operands were bypassed from same result
626 // move) we continue
627 continue;
628 }
629
630 // the original result move for the bypassed move
631 MoveNode& resultMove =
633
634 // if killed this one, finish the kill
635
636 // try to get the original cycle of the result move
637 std::map<MoveNode*, int>::iterator srcIter =
638 sourceCycles_.find(&resultMove);
639 if (srcIter != sourceCycles_.end()) {
640
641 // we lose edges so our notifyScheduled does not notify
642 // some antidependencies, store them for notification.
644 ddg.successors(resultMove);
645
646 successors.erase(&resultMove); // if WaW to itself, remove it.
647
648 ddg.dropNode(resultMove);
649 removedNodes_.insert(&resultMove);
650
651 // remove dead result also from map of sources and bypassed
652 // moves, it should not by tried to get removed second time
653 // by some other bypassed move from same candidate set
654 for (std::map<MoveNode*, MoveNode*, MoveNode::Comparator>::
655 iterator j = storedSources_.begin();
656 j != storedSources_.end();) {
657 if (j->second == &resultMove) {
658 removedStoredSources_[j->first] = &resultMove;
659 storedSources_.erase(j++);
660 } else {
661 j++;
662 }
663 }
664
665 removedMoves.insert(
666 std::make_pair(&resultMove.move(), (*srcIter).second));
667
668 sourceCycles_.erase(srcIter);
669 resultsRemoved++;
671
672 // we lost edges so our notifyScheduled does not notify
673 // some antidependencies. notify them.
674 if (selector_ != NULL) {
675 for (DataDependenceGraph::NodeSet::iterator iter =
676 successors.begin();
677 iter != successors.end(); iter++) {
678 // don't notify other dead results
679 if (sourceCycles_.find(*iter) == sourceCycles_.end()) {
680 selector_->mightBeReady(**iter);
681 }
682 }
683 }
684 } else {
685 // we might have some orhpan nodes because some antideps have moved
686 // from user node to source node,
687 // so make sure notify the scheduler about them.
688 if (ddg.hasNode(resultMove)) {
690 ddg.regWawSuccessors(resultMove);
691 if (selector_ != NULL) {
692 for (DataDependenceGraph::NodeSet::iterator iter =
693 successors.begin();
694 iter != successors.end(); iter++) {
695 // don't notify other dead results
696 if (sourceCycles_.find(*iter) == sourceCycles_.end()) {
697 selector_->mightBeReady(**iter);
698 }
699 }
700 }
701 }
702 }
703
704 // also remove dummy move to itself moves, as the bypassed move.
705 if (moveNode.move().source().equals(
706 moveNode.move().destination())) {
707
708 // we lost edges so our notifyScheduled does not notify
709 // some antidependencies. store them for notification.
711 ddg.successors(moveNode);
712
713 successors.erase(&moveNode); // if WaW to itself, rremove it.
714
715 rm.unassign(moveNode);
716
717 // this may lead to extra raw edges.
718 static_cast<DataDependenceGraph*>(ddg.rootGraph())->
719 copyDepsOver(moveNode, true, true);
720
721 ddg.dropNode(moveNode);
722 removedNodes_.insert(&moveNode);
723
724 // we lost edges so our notifyScheduled does not notify
725 // some antidependencies. notify them.
726 if (selector_ != NULL) {
727 for (DataDependenceGraph::NodeSet::iterator iter =
728 successors.begin();
729 iter != successors.end(); iter++) {
730 // don't notify other dead results
731 if (sourceCycles_.find(*iter) == sourceCycles_.end()) {
732 selector_->mightBeReady(**iter);
733 }
734 }
735 }
736 }
737 }
738
739
740 assert(sourceCycles_.empty());
741
742 return resultsRemoved;
743}
744
745/*
746 * Registers the selector being used to the bypasser.
747 *
748 * If the bypasser has been registered to the selector,
749 * bypasses can notify the selector about dependence changes.
750 * Currently it notifies the successors of a node being removed due
751 * dead result elimination.
752 *
753 * @param selector selector which bypasser notifies on some dependence changes.
754 */
755void
759
760/**
761 * Clears the storedSources data structure, when the old values in it are
762 * not needed anymore, allowing them to be deleted by the objects who
763 * own them.
764 *
765 * Delete node from sourceCycles structure, as thesse are not deleted
766 * elsewhere.
767 */
768void
770 bool removeDeletedResults) {
771 storedSources_.clear();
772 sourceBuses_.clear();
773 if (removeDeletedResults) {
774 // TODO: somebody should also delete these
775 for (DataDependenceGraph::NodeSet::iterator i = removedNodes_.begin();
776 i != removedNodes_.end(); i++) {
777 if (ddg.rootGraph() != &ddg) {
778 ddg.rootGraph()->removeNode(**i);
779 }
780 delete *i;
781 }
782 }
783 removedNodes_.clear();
784 removedStoredSources_.clear();
785}
786
787void
789 std::cerr << "Bypasser statistics: " << std::endl
790 << "\tBypasses: " << bypassCount_ << std::endl
791 << "\tKilled results: " << deadResultCount_ << std::endl
792 << "\tTrigger too early aborts: " << triggerAbortCount_ << std::endl;
793}
794
#define __func__
#define assert(condition)
static CmdLineOptions * cmdLineOptions()
BoostGraph * rootGraph()
virtual void removeNode(Node &node)
virtual NodeSet successors(const Node &node, bool ignoreBackEdges=false, bool ignoreForwardEdges=false) const
bool hasNode(const Node &) const
virtual void dropNode(Node &node)
virtual Node & tailNode(const Edge &edge) const
virtual EdgeSet inEdges(const Node &node) const
int cyclesToLookBack_
count of cycles before the operand write to look for the producer of the read value
int bypassNode(MoveNode &nodeToBypass, int &lastOperandCycle, DataDependenceGraph &ddg, ResourceManager &rm)
virtual void clearCaches(DataDependenceGraph &ddg, bool removeDeadResults)
std::map< MoveNode *, const TTAMachine::Bus * > sourceBuses_
virtual void removeBypass(MoveNodeGroup &candidates, DataDependenceGraph &ddg, ResourceManager &rm)
virtual int removeDeadResults(MoveNodeGroup &candidates, DataDependenceGraph &ddg, ResourceManager &rm, std::set< std::pair< TTAProgram::Move *, int > > &removedMoves)
int cyclesToLookBackNoDRE_
count of cycles before the operand write to look for the producer of the read value when cannot kill ...
std::map< MoveNode *, MoveNode *, MoveNode::Comparator > removedStoredSources_
void setSelector(MoveNodeSelector *selector)
virtual int bypass(MoveNodeGroup &candidates, DataDependenceGraph &ddg, ResourceManager &rm, bool bypassTrigger)
std::map< MoveNode *, MoveNode *, MoveNode::Comparator > storedSources_
Stores sources and bypassed moves in case they have to be unassigned (case when operands are schedule...
DependenceType dependenceType() const
EdgeReason edgeReason() const
NodeSet regWawSuccessors(const MoveNode &node) const
int latestCycle(const MoveNode &moveNode, unsigned int ii=UINT_MAX, bool ignoreRegAntideps=false, bool ignoreUnscheduledSuccessors=true, bool ignoreGuards=false, bool ignoreFUDeps=false, bool ignoreSameOperationEdges=false) const
int earliestCycle(const MoveNode &moveNode, unsigned int ii=UINT_MAX, bool ignoreRegWaRs=false, bool ignoreRegWaWs=false, bool ignoreGuards=false, bool ignoreFUDeps=false, bool ignoreSameOperationEdges=false, bool assumeBypassing=false) const
void unMergeUser(MoveNode &resultNode, MoveNode &mergedNode, bool loopBypass=false)
bool mergeAndKeepUser(MoveNode &resultNode, MoveNode &userNode, bool force=false)
int regRawSuccessorCount(const MoveNode &mn, bool onlyScheduled)
bool resultUsed(MoveNode &resultNode)
EdgeSet copyDepsOver(MoveNode &node, bool anti, bool raw)
NodeSet regWarSuccessors(const MoveNode &node) const
bool guardsAllowBypass(const MoveNode &defNode, const MoveNode &useNode, bool loopBypass=false)
std::string errorMessageStack(bool messagesOnly=false) const
Definition Exception.cc:138
std::set< GraphNode *, typename GraphNode::Comparator > NodeSet
Definition Graph.hh:53
std::set< GraphEdge *, typename GraphEdge::Comparator > EdgeSet
Definition Graph.hh:54
static KeyType keyForValue(const MapType &aMap, const ValueType &aValue)
static bool containsKey(const MapType &aMap, const KeyType &aKey)
int nodeCount() const
MoveNode & node(int index) const
virtual void mightBeReady(MoveNode &node)=0
int cycle() const
Definition MoveNode.cc:421
int guardLatency() const
Definition MoveNode.cc:779
bool isBypass() const
Definition MoveNode.cc:280
bool isDestinationOperation() const
TTAProgram::Move & move()
bool isSourceOperation() const
Definition MoveNode.cc:168
bool isScheduled() const
Definition MoveNode.cc:409
bool isSourceConstant() const
Definition MoveNode.cc:238
bool isDestinationVariable() const
Definition MoveNode.cc:264
virtual int earliestCycle(MoveNode &node, const TTAMachine::Bus *bus=nullptr, const TTAMachine::FunctionUnit *srcFU=nullptr, const TTAMachine::FunctionUnit *dstFU=nullptr, int immWriteCycle=-1, const TTAMachine::ImmediateUnit *immu=nullptr, int immRegIndex=-1) const =0
virtual bool canAssign(int cycle, MoveNode &node, const TTAMachine::Bus *bus=nullptr, const TTAMachine::FunctionUnit *srcFU=nullptr, const TTAMachine::FunctionUnit *dstFU=nullptr, int immWriteCycle=-1, const TTAMachine::ImmediateUnit *immu=nullptr, int immRegIndex=-1) const =0
virtual void unassign(MoveNode &node)=0
virtual void assign(int cycle, MoveNode &node, const TTAMachine::Bus *bus=nullptr, const TTAMachine::FunctionUnit *srcFU=nullptr, const TTAMachine::FunctionUnit *dstFU=nullptr, int immWriteCycle=-1, const TTAMachine::ImmediateUnit *immu=nullptr, int immRegIndex=-1)=0
virtual bool killDeadResults() const
virtual int noDreBypassDistance() const
virtual Machine * machine() const
bool alwaysWriteResults() const
Definition Machine.cc:948
bool hasAnnotations(ProgramAnnotation::Id id=ProgramAnnotation::ANN_UNDEF_ID) const
void setSource(Terminal *src)
Definition Move.cc:312
bool isControlFlowMove() const
Definition Move.cc:233
bool isUnconditional() const
Definition Move.cc:154
Terminal & source() const
Definition Move.cc:302
bool isTriggering() const
Definition Move.cc:284
void setBus(const TTAMachine::Bus &bus)
Definition Move.cc:383
Terminal & destination() const
Definition Move.cc:323
const TTAMachine::Bus & bus() const
Definition Move.cc:373
@ ANN_CONNECTIVITY_MOVE
A reg to reg move that was added because of missing connectivity between the original target and dest...
virtual bool equals(const Terminal &other) const =0
virtual bool isImmediateRegister() const
Definition Terminal.cc:97