OpenASIP 2.2
Loading...
Searching...
No Matches
BF2Scheduler.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 BF2Scheduler.cc
27 *
28 * Definition of BF2Scheduler class.
29 *
30 * Bypassing Bottom-up Breadth-First-Search Instruction Scheduler
31 * (BubblefishScheduler)
32 *
33 * @author Heikki Kultala 2014-2020(heikki.kultala-no.spam-tuni.fi)
34 * @note rating: red
35 */
36
37#include "BF2Scheduler.hh"
38//#include "BFFinishFront.hh"
39#include "BF2ScheduleFront.hh"
40
43#include "FunctionUnit.hh"
44#include "Unit.hh"
45#include "Machine.hh"
46#include "Terminal.hh"
47#include "TerminalRegister.hh"
48#include "HWOperation.hh"
49#include "FUPort.hh"
50#include "MoveNodeSet.hh"
51#include "Operation.hh"
52#include "Move.hh"
53#include "ControlUnit.hh"
54#include "BUMoveNodeSelector.hh"
57#include "InterPassData.hh"
58#include "RegisterCopyAdder.hh"
59#include "MoveGuard.hh"
61#include "BasicBlockNode.hh"
62#include "BasicBlock.hh"
65#include "RegisterRenamer.hh"
66#include "MapTools.hh"
67#include "BFScheduleBU.hh"
68#include "ProgramAnnotation.hh"
69#include "MoveNodeDuplicator.hh"
70#include "BFSwapOperands.hh"
71#include "BFShareOperand.hh"
73#include "BFRemoveLoopChecks.hh"
74#include "LoopAnalyzer.hh"
75#include "BFPostpassBypasser.hh"
76
77//#define DEBUG_PRE_SHARE
78//#define DEBUG_BUBBLEFISH_SCHEDULER
79
80#ifdef DEBUG_BUBBLEFISH_SCHEDULER
81#define DEBUG_PRE_SHARE
82#endif
83
84//#define DEBUG_PRE_SHARE
85
86//#define ENABLE_RENAMING
87//define ENABLE_DOT_SPAM
88
89#define REMOVE_LOOP_CHECKS_WITH_LOOPBUFFER
90#define ENABLE_PRE_LOOP_SHARING
91
93 InterPassData& ipd, RegisterRenamer* renamer) :
94 DDGPass(ipd), ddg_(NULL), prologDDG_(nullptr), rm_(NULL),
95 prologRM_(nullptr), latestCycle_(INT_MAX/1024),
96 renamer_(renamer),
97 killDeadResults_(true),
98 jumpNode_(NULL),
99 llResult_(NULL),
100 duplicator_(NULL) {
101 options_ =
103 if (options_ != NULL) {
105 }
106
107}
108
110 InterPassData& ipd, RegisterRenamer* renamer, bool killDeadResults) :
111 DDGPass(ipd), ddg_(NULL), rm_(NULL),
112 latestCycle_(INT_MAX/1024),
113 renamer_(renamer),
114 killDeadResults_(killDeadResults),
115 jumpNode_(NULL),
116 llResult_(NULL),
117 duplicator_(NULL) {
118 options_ =
120}
121
123 if (mn.isDestinationOperation()) {
125 for (int i = 0; i < po.inputMoveCount(); i++) {
126 MoveNode& inputNode = po.inputMove(i);
127 assert( inputNode.isDestinationOperation());
128 if (inputNode.isScheduled()) {
129#ifdef DEBUG_BUBBLEFISH_SCHEDULER
130 std::cerr << "\t\tFound scheduled input: "
131 << inputNode.toString() << std::endl;
132#endif
134 inputNode.move().destination();
135 assert(term.isFUPort());
136 return term.port().parentUnit();
137 }
138 }
139 }
140 return NULL;
141}
142
146 const TTAMachine::Machine& targetMachine) {
147
148 jumpGuardWrite_ = NULL;
149
151 prologRM_ = NULL;
153
154 // scheduling pipeline resources after last cycle may cause problems.
155 // make RM to check for those
156 latestCycle_ = (INT_MAX/1024);
158
160#ifdef DEBUG_BUBBLEFISH_SCHEDULER
161 std::cerr << std::endl << "Handling new ddg: " << ddg.name() << std::endl;
162#endif
163 ddg_ = &ddg;
165 if (duplicator_ != NULL) {
166 delete duplicator_; duplicator_ = NULL;
167 }
168
171 if (renamer_ != NULL) {
174 }
175
176 rm_ = &rm;
177
178 if (options_ != NULL && options_->dumpDDGsDot()) {
180 (boost::format("bb_%s_before_scheduling.dot") %
181 ddg_->name()).str());
182 }
183
185 while (moves.nodeCount() > 0) {
186 MoveNode* mn = NULL;
187 for (int i = 0; i < moves.nodeCount(); i++) {
188 if (!moves.node(i).isScheduled()) {
189 if (isDeadResult(moves.node(i))) {
190 if (ddg_->hasNode(moves.node(i))) {
191 ddg_->dropNode(moves.node(i));
192 }
193 } else {
194 mn = &moves.node(i);
195 }
196 }
197 }
198 if (mn == NULL) {
199 moves = selector.candidates();
200 continue;
201 }
202
203 if (!scheduleFrontFromMove(*mn)) {
204#ifdef DEBUG_BUBBLEFISH_SCHEDULER
205 std::cerr << "Scheduling of front failed! Inducing move: "
206 << mn->toString() << std::endl;
207#endif
209 (boost::format("%s_failed_ddg.dot") %
210 ddg_->name()).str());
211 throw CompileError(__FILE__, __LINE__, __func__,
212 "Bubblefish scheduler failed"
213 "retry count exceeded. Propably broken ADF");
214 }
215#ifdef DEBUG_BUBBLEFISH_SCHEDULER
216 std::cerr << "Whole op scheduled ok? original MN: "
217 << mn->toString() << std::endl;
218#endif
219 moves = selector.candidates();
220 }
221
222 if (ddg_->scheduledNodeCount() != ddg_->nodeCount()) {
224 (boost::format("%s_unscheduled_nodes_in_ddg.dot") %
225 ddg_->name()).str());
226
227 assert(false && "unscheduled nodes in ddg after scheduler");
228 }
229
230 if (options_ != NULL && options_->dumpDDGsDot()) {
232 (boost::format("bb_%s_after_scheduler_ddg.dot") %
233 ddg_->name()).str());
234 }
235
236 if (options_ != NULL && options_->dumpDDGsXML()) {
238 (boost::format("bb_%s_after_scheduler_ddg.dot") %
239 ddg_->name()).str());
240 }
241}
242
243int
246 const TTAMachine::Machine& targetMachine, int, bool testOnly) {
247 loopBufOps_.clear();
248
250
251 int len = rm_->largestCycle() - rm_->smallestCycle()+1;
252
253#ifdef DEBUG_BUBBLEFISH_SCHEDULER
254 std::cerr << "Handled ddg: " <<ddg_->name() << std::endl;
255#endif
256
257 if (testOnly) {
258#ifdef DEBUG_BUBBLEFISH_SCHEDULER
259 ddg_->writeToDotFile("tested_schedule.dot");
260#endif
261 unschedule();
262 } else {
264 }
265 if (duplicator_ != NULL) {
266 delete duplicator_; duplicator_ = NULL;
267 }
268
269 return len;
270}
271
273 BUMoveNodeSelector& selector, bool allowPreLoopOpshare) {
274 loopBufOps_.clear();
275 if (prologRM_ != NULL) {
276 if (allowPreLoopOpshare) {
279 } else {
280 // TODO: should these be undone, not just cleared?
283 }
284
287 } else {
290 }
291
293 while (moves.nodeCount() > 0) {
294 MoveNode* mn = NULL;
295 for (int i = 0; i < moves.nodeCount(); i++) {
296 if (!moves.node(i).isScheduled()) {
297 if (isDeadResult(moves.node(i))) {
298 if (ddg_->hasNode(moves.node(i))) {
299 ddg_->dropNode(moves.node(i));
300 }
301 } else {
302 mn = &moves.node(i);
303 }
304 }
305 }
306 if (mn == NULL) {
307 moves = selector.candidates();
308 continue;
309 }
310
311 if (!scheduleFrontFromMove(*mn)) {
312#ifndef DEBUG_BUBBLEFISH_SCHEDULER
313 if (options_ != NULL && options_->dumpDDGsDot()) {
314#endif
315 if (loopLimitNode() == NULL) {
317 std::string("ii_fail_") +
319 "icount_" +
321 std::string("ops_") +
322 Conversion::toString(allowPreLoopOpshare) +
323 std::string("_dag.dot"));
324 } else {
326 std::string("ii_fail_") +
328 "llNode" +
330 std::string("ops_") +
331 Conversion::toString(allowPreLoopOpshare) +
332 std::string("_dag.dot"));
333 }
334#ifndef DEBUG_BUBBLEFISH_SCHEDULER
335 }
336#endif
337#ifdef DEBUG_BUBBLEFISH_SCHEDULER
338 std::cerr << std::endl << std::endl
339 << "Unscheduling all due scheduling failed at around: "
340 << mn->toString() << std::endl << std::endl;
341#endif
342 unschedule();
343 if (prologRM_ != NULL) {
347 }
348 if (duplicator_ != NULL) {
349 delete duplicator_; duplicator_ = NULL;
350 }
351 return -1;
352 }
353#ifdef DEBUG_BUBBLEFISH_SCHEDULER
354 std::cerr << "Whole op scheduled ok? original MN: "
355 << mn->toString() << std::endl;
356#endif
357 moves = selector.candidates();
358 }
359
360 // Try to schedule pre-loop operand shared moves. if fail, abort.
361 if (prologRM_ && allowPreLoopOpshare) {
362 if (false) {
363#ifdef DEBUG_BUBBLEFISH_SCHEDULER
364 std::cerr << "Scheduling pre-loop opshares fail, undoing all"
365 << std::endl;
366#endif
367 unschedule();
368 if (prologRM_ != NULL) {
372 }
373 if (Application::verboseLevel() > 1) {
374 std::cerr << "Scheduling pre-loop operand shares failed."
375 << std::endl;
376 }
377 if (duplicator_ != NULL) {
378 delete duplicator_; duplicator_ = NULL;
379 }
380 return -1;
381 }
382 }
383
384 //postpass-bypass.
385 auto postBypass = new BFPostpassBypasser(*this);
386 if ((*postBypass)()) {
387 scheduledStack_.push_back(postBypass);
388 } else {
389 delete postBypass;
390 }
391
392 int overlapCount =
394#ifdef DEBUG_BUBBLEFISH_SCHEDULER
395 std::cerr << "inner handleLoopDDG exiting, overlapcount: "
396 << overlapCount << std::endl;
397#endif
398 return overlapCount;
399}
400
401int
404 const TTAMachine::Machine& targetMachine, int tripCount,
405 SimpleResourceManager* prologRM, bool testOnly) {
406#ifndef DEBUG_BUBBLEFISH_SCHEDULER
407 if (options_ != NULL && options_->dumpDDGsDot()) {
408#endif
410 std::string("ii_begin_") +
412 std::string("_dag.dot"));
413#ifndef DEBUG_BUBBLEFISH_SCHEDULER
414 }
415#endif
416
417 rm.setDDG(&ddg);
419#ifdef ENABLE_DOT_SPAM
421 std::string("before_loop_ddg.dot"));
422#endif
423
426 rm_ = &rm;
428
429 // scheduling pipeline resources after last cycle may cause problems.
430 // make RM to check for those
433
434 if (Application::verboseLevel() > 1) {
435 std::cerr << std::endl << "Handling new loop ddg: " << ddg.name()
436 << std::endl;
437 }
438 ddg_ = &ddg;
440
441 if (duplicator_ != NULL) {
442#ifdef DEBUG_BUBBLEFISH_SCHEDULER
443 std::cerr << "Duplicator not null in handleloopddg,"
444 " deleting duplicator" << std::endl;
445#endif
446 delete duplicator_; duplicator_ = NULL;
447 }
448
449 if (!findJump()) {
450 return -1;
451 }
452
454 if (jumpGuardWrite_ == NULL) {
455 return -1;
456 }
457
458#ifdef DEBUG_BUBBLEFISH_SCHEDULER
459 std::cerr << "jumpguard write node is: "
460 << jumpGuardWrite_->toString() << std::endl;
461#endif
462
463 if (prologRM != NULL) {
465 prologDDG_ = static_cast<DataDependenceGraph*>(
466 ddg_->parentGraph())->createSubgraph(empty);
468 // TODO: this is kinda incorrect. should be prolog
469#ifdef DEBUG_BUBBLEFISH_SCHEDULER
470 std::cerr << "prolog RM not null, pre-allocating FUs:"
471 << prologRM << std::endl;
472#endif
473 }
474
475#ifndef DEBUG_BUBBLEFISH_SCHEDULER
476 if (options_ != NULL && options_->dumpDDGsDot()) {
477#endif
479 (boost::format("bb_%s_ii_%d_before_scheduling.dot") %
480 ddg_->name() % rm.initiationInterval()).str());
481#ifndef DEBUG_BUBBLEFISH_SCHEDULER
482 }
483#endif
486 if (renamer_ != NULL) {
488 }
489
490 int overlapCount = handleLoopDDG(selector, true);
491 if (overlapCount == -1) {
492 if (Application::verboseLevel() > 1) {
493 std::cerr << "Loop Sched. fail with pre-loop opshare on with II: "
494 << rm.initiationInterval() << std::endl;
495 }
497 overlapCount = handleLoopDDG(selector, false);
498 if (overlapCount == -1) {
499 if (Application::verboseLevel() > 1) {
500 std::cerr << "Loop Sched. fail without pre-loop opshare, II: "
501 << rm.initiationInterval() << std::endl;
502 }
503 if (duplicator_ != NULL) {
504 delete duplicator_; duplicator_ = NULL;
505 }
506 return -1;
507 } else {
508 if (Application::verboseLevel() > 1) {
509 std::cerr << "Loop Sched. ok without pre-loop opshare, II: "
510 << rm.initiationInterval() << std::endl;
511 }
512 }
513 }
514
515 if (ddg_->scheduledNodeCount() != ddg_->nodeCount()) {
517 (boost::format("%s_unscheduled_nodes_in_ddg.dot") %
518 ddg_->name()).str());
519
520 assert(false && "unscheduled nodes in ddg after scheduler");
521 }
522
523 // loop schedulign did not help.
524 if (testOnly) {
525 if (overlapCount == 0 && Application::verboseLevel() > 1) {
527 << "No overlapping instructions, "
528 << "Should decrease II"
529 << std::endl;
530 }
531 // this have to be calculated before unscheduling.
532#ifdef DEBUG_BUBBLEFISH_SCHEDULER
533 std::cerr << "Unscheduling all due loop sched too slow or testonly"
534 << std::endl;
535#endif
536
537#ifndef DEBUG_BUBBLEFISH_SCHEDULER
538 if (options_ != NULL && options_->dumpDDGsDot()) {
539#endif
541 std::string("ii_test_or_slow_") +
543 std::string("_dag.dot"));
544#ifndef DEBUG_BUBBLEFISH_SCHEDULER
545 }
546#endif
547
548 unschedule();
549
550#ifndef DEBUG_BUBBLEFISH_SCHEDULER
551 if (options_ != NULL && options_->dumpDDGsDot()) {
552#endif
554 std::string("ii_unscheduled_slow") +
556 std::string("_dag.dot"));
557#ifndef DEBUG_BUBBLEFISH_SCHEDULER
558 }
559#endif
560
561 if (prologRM_ != NULL) {
565 }
566 if (duplicator_ != NULL) {
567 delete duplicator_; duplicator_ = NULL;
568 }
569 return overlapCount;
570 }
571
572 if (loopLimitNode() == NULL && tripCount && overlapCount >= tripCount) {
573#ifndef DEBUG_BUBBLEFISH_SCHEDULER
574 if (options_ != NULL && options_->dumpDDGsDot()) {
575#endif
577 std::string("ii_no_overlap") +
579 std::string("_dag.dot"));
580#ifndef DEBUG_BUBBLEFISH_SCHEDULER
581 }
582#endif
583 unschedule();
584
585#ifndef DEBUG_BUBBLEFISH_SCHEDULER
586 if (options_ != NULL && options_->dumpDDGsDot()) {
587#endif
589 std::string("ii_unscheduled_no_overlap") +
591 std::string("_dag.dot"));
592#ifndef DEBUG_BUBBLEFISH_SCHEDULER
593 }
594#endif
595 if (prologRM_ != NULL) {
599 }
600
601 if (duplicator_ != NULL) {
602 delete duplicator_; duplicator_ = NULL;
603 }
604 return -1;
605 }
606
607
608 if (options_ != NULL && options_->dumpDDGsDot()) {
610 (boost::format("bb_%s_after_scheduling.dot") %
611 ddg_->name()).str());
612 }
613
614 if (options_ != NULL && options_->dumpDDGsXML()) {
616 (boost::format("bb_%s_after_scheduling.dot") %
617 ddg_->name()).str());
618 }
619
621
622 if (Application::verboseLevel() > 1) {
623 std::cerr << "Handled loop ddg: " <<ddg_->name() << std::endl;
624 }
625
626#ifndef DEBUG_BUBBLEFISH_SCHEDULER
627 if (options_ != NULL && options_->dumpDDGsDot()) {
628#endif
630 std::string("ii_ok_") +
632 std::string("iters_") +
634 std::string("_dag.dot"));
635#ifndef DEBUG_BUBBLEFISH_SCHEDULER
636 }
637#endif
638 return overlapCount;
639}
640
642 for (auto m: dreRemovedMoves_) {
643 if (m->isScheduled()) {
644 std::cerr << "cannot kill scheduled move: "
645 << m->toString() << std::endl;
646 assert(false);
647 }
648 if (prologRM_) {
649 MoveNode *prologMN = duplicator().getMoveNode(*m);
650 if (prologMN) {
651 if (prologMN->isScheduled()) {
652 std::cerr << "prolog MN: " << prologMN->toString()
653 << "of MN: " << m->toString()
654 << " is scheduled!" << std::endl;
655 assert(false);
656 }
657
658 ddg_->rootGraph()->removeNode(*prologMN);
659 }
660 }
661 ddg_->rootGraph()->removeNode(*m);
662 }
663 for (auto m: removedMoves_) {
664 assert(!m->isScheduled());
665 ddg_->rootGraph()->removeNode(*m);
666 }
667
668 // remove undo information, as cannot be undoed after this
669 while(!scheduledStack_.empty()) {
670 BFOptimization* bfo = scheduledStack_.back();
671 scheduledStack_.pop_back();
672 delete bfo;
673 }
674}
675
676
677#ifdef ENABLE_DOT_SPAM
680 const TCEString& namePrefix, const MoveNode& mn) {
681
682 TCEString dotName;
683 int counter = 0;
684 do {
685 dotName = namePrefix;
686 dotName << "_" << mn.nodeID();
687 dotName << "_" << counter << ".dot";
688 counter++;
689 } while (exists(dotName.c_str()));
690 std::cerr << "\t\t\t\t\tDumping ddg: " << dotName << " mn: "
691 << mn.toString() << std::endl;
692 ddg.writeToDotFile(dotName);
693
694}
695#else
699#endif
700
701
702
705 TTAProgram::Terminal& dest = mn->move().destination();
706 if (!dest.isGPR()) {
707 ddg().writeToDotFile("cannot_revert.dot");
708 std::cerr << "Cannot revert bb live range bookkeeping as "
709 << " dest not gpr: " << mn->toString() << std::endl;
710 std::cerr << "This might be caused by broken connectivity in the ADF."
711 << std::endl;
712
713 }
714 assert(dest.isGPR());
715 int index = dest.index();
716 const TTAMachine::RegisterFile& rf = dest.registerFile();
718
720 bbn.basicBlock().liveRangeData_->regDefines_, reg, mn);
721
724}
725
728 TTAProgram::Terminal& src = mn->move().source();
729 if (!src.isGPR()) {
730 ddg().writeToDotFile("cannot_revert.dot");
731 std::cerr << "Cannot revert bb live range bookkeeping as "
732 << " src not gpr: " << mn->toString() << std::endl;
733 std::cerr << "This might be caused by broken connectivity in the ADF."
734 << std::endl;
735 }
736 assert(src.isGPR());
737 int index = src.index();
738 const TTAMachine::RegisterFile& rf = src.registerFile();
740
742 bbn.basicBlock().liveRangeData_->regLastUses_, reg, mn);
743
745 bbn.basicBlock().liveRangeData_->regFirstUses_, reg, mn);
746}
747
748void
751 const TCEString& reg, MoveNode* mn) {
752 LiveRangeData::MoveNodeUseMapSet::iterator s = mnuMap.find(reg);
753 if (s != mnuMap.end()) {
754 LiveRangeData::MoveNodeUseSet& mnuSet = s->second;
755 LiveRangeData::MoveNodeUseSet::iterator i =
756 mnuSet.find(MoveNodeUse(*mn));
757 if (i!= mnuSet.end()) {
758 mnuSet.erase(i);
759 }
760 }
761}
762
763
764bool
766 if (!mn.isSourceVariable()) {
767 return false;
768 }
769 return mn.move().source().isUniversalMachineRegister();
770}
771
772bool
774 if (!mn.isDestinationVariable()) {
775 return false;
776 }
778}
779
781 while(!scheduledStack_.empty()) {
782 BFOptimization* bfo = scheduledStack_.back();
783 scheduledStack_.pop_back();
784 currentFront_ = dynamic_cast<BF2ScheduleFront*>(bfo);
785#ifdef DEBUG_BUBBLEFISH_SCHEDULER
786 std::cerr << "unscheduling front @ " << bfo
787 << " in unschedule" << std::endl;
788#endif
789 bfo->undo();
790 currentFront_ = NULL;
791 delete bfo;
792 }
793}
794
795
796
797
799 return dreRemovedMoves_.find(&mn) != dreRemovedMoves_.end() ||
800 removedMoves_.find(&mn) != removedMoves_.end();
801}
802
806
808 removedMoves_.insert(&mn);
809}
810
812 removedMoves_.erase(&mn);
813 dreRemovedMoves_.erase(&mn);
814}
815
816/**
817 * Checks whether given movenode is a trigger in given FU
818 */
820 const TTAMachine::FunctionUnit& fu =
821 dynamic_cast<const TTAMachine::FunctionUnit&>(unit);
822
824 int operandNum = term.operationIndex();
825
826 const Operation& op = mn.destinationOperation().operation();
827
828 const TTAMachine::HWOperation* hwop =
829 fu.operation(op.name());
830
831 const TTAMachine::FUPort* port = hwop->port(operandNum);
832 return port->isTriggering();
833}
834
835/**
836 * Finds the source where to bypass from.
837 */
839
841 DataDependenceGraph::EdgeSet::iterator edgeIter = edges.begin();
842 DataDependenceEdge* bypassEdge = NULL;
843
844 // find one incoming raw edge. if multiple, cannot bypass.
845 while (edgeIter != edges.end()) {
846
847 DataDependenceEdge& edge = *(*edgeIter);
848 // if the edge is not a real reg/ra raw edge, skip to next edge
851 edge.guardUse() || edge.headPseudo()) {
852 edgeIter++;
853 continue;
854 }
855
856 if (bypassEdge == NULL) {
857 bypassEdge = &edge;
858 } else {
859 // cannot bypass if multiple inputs
860 return NULL;
861 }
862 edgeIter++;
863 }
864
865 // if no bypassable edge found, cannot bypass
866 if (bypassEdge == NULL) {
867 return 0;
868 }
869
870 if (bypassEdge->isBackEdge()) {
871 if (!rm().initiationInterval()) {
872#ifdef DEBUG_BUBBLEFISH_SCHEDULER
873 std::cerr << "\tbackedge without without loop sched!!"
874 << " not allowed." << std::endl;
875#endif
876 return NULL;
877#ifdef DEBUG_BUBBLEFISH_SCHEDULER
878 } else {
879 std::cerr << "\t\tback edge bypass ok in loop" << std::endl;
880#endif
881 }
882 }
883 return bypassEdge;
884}
885
886
888 return "BubbleFish instruction Scheduler";
889}
890
891
892/**
893 * Find possible temp reg RF's for connectivity of given register.
894 *
895 * This only gives the register files that for the "next register in the
896 * temp reg chain", not the whole chain
897 */
898std::set<const TTAMachine::RegisterFile*, TTAMachine::MachinePart::Comparator>
900 const MoveNode& mn, bool tempRegAfter,
901 const TTAMachine::RegisterFile* forbiddenRF) {
902
903 std::set<const TTAMachine::RegisterFile*,
905 result;
906
907 std::map<int, int> rfDistanceFromSource;
908 std::map<int, int> rfDistanceFromDestination;
909
910 typedef SimpleInterPassDatum<
911 std::vector<std::pair<const TTAMachine::RegisterFile*, int> > >
912 TempRegData;
913
914 std::string srDatumName = "SCRATCH_REGISTERS";
915 if (!DDGPass::interPassData().hasDatum(srDatumName) ||
916 (dynamic_cast<TempRegData&>(
917 DDGPass::interPassData().datum(srDatumName))).size() == 0) {
918 TCEString msg("No scratch registers available for "
919 "temporary moves for move: ");
920 msg << mn.toString();
921 throw IllegalProgram(__FILE__, __LINE__, __func__, msg);
922 }
923 const TempRegData& tempRegs =
924 dynamic_cast<TempRegData&>(
925 DDGPass::interPassData().datum(srDatumName));
926
927
928 for (unsigned int i = 0; i < tempRegs.size(); i++) {
929 rfDistanceFromSource[i] = INT_MAX;
930 rfDistanceFromDestination[i] = INT_MAX;
931 }
932
933
934 for (unsigned int i = 0; i < tempRegs.size(); i++) {
935 const TTAMachine::RegisterFile* rf = tempRegs[i].first;
940 bool srcOk = false;
941
942 if (rf == forbiddenRF) {
943 continue;
944 }
945
947 mn, writePorts)) {
948 rfDistanceFromSource[i] = 1;
949 srcOk = true;
950 }
951
953 readPorts, mn)) {
954 rfDistanceFromDestination[i] = 1;
955 if (srcOk) {
956 // this RF does it!
957 result.insert(rf);
958 }
959 }
960 }
961
962 // modified check to avoid 4ever loop in case of broken machine
963 bool modified = true;
964 if (!tempRegAfter) {
965 while (result.empty() && modified) {
966 int shortest = INT_MAX;
967 modified = false;
968 for (unsigned int i = 0; i < tempRegs.size(); i++) {
969 int srcDist = rfDistanceFromSource[i];
970 if (srcDist != INT_MAX) {
971 const TTAMachine::RegisterFile* rfSrc = tempRegs[i].first;
972 for (unsigned int j = 0; j < tempRegs.size(); j++) {
973 if (rfDistanceFromSource[j] > srcDist + 1) {
974 const TTAMachine::RegisterFile* rfDest =
975 tempRegs[j].first;
976 // ignore rf's which are not wide enough
978 *rfSrc, *rfDest,
979 (mn.move().isUnconditional() ? NULL :
980 &mn.move().guard().guard()))) {
981 rfDistanceFromSource[j] = srcDist + 1;
982 modified = true;
983 if (rfDistanceFromDestination[j] == 1) {
984 int dist = srcDist + 2;
985 if (dist < shortest) {
986 result.clear();
987 shortest = dist;
988 }
989 if (dist == shortest) {
990 result.insert(rfDest);
991 }
992 }
993 }
994 }
995 }
996 }
997 }
998 }
999 return result;
1000 } else {
1001 while (result.empty() && modified) {
1002 int shortest = INT_MAX;
1003 modified = false;
1004 for (unsigned int i = 0; i < tempRegs.size(); i++) {
1005 int dstDist = rfDistanceFromDestination[i];
1006 if (dstDist != INT_MAX) {
1007 const TTAMachine::RegisterFile* rfDst = tempRegs[i].first;
1008 for (unsigned int j = 0; j < tempRegs.size(); j++) {
1009 if (rfDistanceFromDestination[j] > dstDist + 1) {
1010 const TTAMachine::RegisterFile* rfSrc =
1011 tempRegs[j].first;
1013 *rfDst, *rfSrc,
1014 (mn.move().isUnconditional() ? NULL :
1015 &mn.move().guard().guard()))) {
1016 rfDistanceFromDestination[j] = dstDist + 1;
1017 modified = true;
1018 if (rfDistanceFromSource[j] == 1) {
1019 int dst = dstDist + 2;
1020 if (dst < shortest) {
1021 result.clear();
1022 shortest = dst;
1023 }
1024 if (dst == shortest) {
1025 result.insert(rfSrc);
1026 }
1027 }
1028 }
1029 }
1030 }
1031 }
1032 }
1033 }
1034 return result;
1035 }
1036}
1037
1039 BF2ScheduleFront* bfsf = new BF2ScheduleFront(*this, mn, latestCycle_);
1040 currentFront_ = bfsf;
1041 if ((*bfsf)()) {
1042 scheduledStack_.push_back(bfsf);
1043 currentFront_ = NULL;
1044 return true;
1045 } else {
1046 delete bfsf;
1047 currentFront_ = NULL;
1048 return false;
1049 }
1050}
1051
1052
1053
1055
1057 for (auto m: succ) {
1058 if (!m->isScheduled()) {
1059 if (!isDeadResult(*m) && m != &mn) {
1060#ifdef DEBUG_BUBBLEFISH_SCHEDULER
1061 std::cerr << "\t\t\tunsched succ: " << m->toString()
1062 << std::endl;
1063#endif
1064 return true;
1065 }
1066 }
1067 }
1068 return false;
1069}
1070
1071/**
1072 * Finds the jump from the bb.
1073 *
1074 * @return if found a guarded jump.
1075 */
1077 for (int i = 0; i < ddg_->nodeCount(); i++) {
1078 MoveNode& mn = ddg_->node(i);
1079 if (mn.isMove() && mn.move().isJump()) {
1080 jumpNode_ = &mn;
1081 return !mn.move().isUnconditional();
1082 }
1083 }
1084 return false;
1085}
1086
1088 if (jumpNode_->move().isUnconditional()) {
1089 std::cerr << "jump is unconditional: " << jumpNode_->toString()
1090 << std::endl;
1091 }
1093 return &jumpNode_->move().guard();
1094}
1095
1096/**
1097 * @return new operand index of the operand. 0 if not swapped.
1098 */
1100 ProgramOperationPtr po, const Operation& op,
1101 int operandIndex, MoveNode& trig) {
1102 for (int i = 1; i <= op.numberOfInputs(); i++) {
1103 if (i == operandIndex) continue;
1104 if (op.canSwap(i, operandIndex)) {
1105 MoveNodeSet& inputNodeSet = po->inputNode(i);
1106 if (inputNodeSet.count() == 1) {
1107 BFSwapOperands* swapper =
1108 new BFSwapOperands(*this, po, trig,
1109 inputNodeSet.at(0));
1110 if ((*swapper)()) {
1111 scheduledStack_.push_back(swapper);
1112 return i;
1113 break;
1114 } else {
1115 delete swapper;
1116 }
1117 }
1118 }
1119 }
1120 return 0;
1121}
1122
1124 const MoveNode& mn, const ProgramOperation& po) {
1125 const Operation& op = po.operation();
1126 int inputCount = op.numberOfInputs();
1127 if (inputCount < 2) {
1128 return true;
1129 }
1130 MoveNode* trig =
1132 if (trig != &mn) {
1133 return false;
1134 }
1135 int myIdx = mn.move().destination().operationIndex();
1136 for (int i = 1; i <= inputCount; i++) {
1137 if (i != myIdx && op.canSwap(myIdx, i)) {
1138 return false;
1139 }
1140 }
1141 return true;
1142}
1143
1144/**
1145 * Revert last optimization from the optimization stack.
1146 */
1148 assert(!scheduledStack_.empty());
1149 BFOptimization* bfo = scheduledStack_.back();
1150 scheduledStack_.pop_back();
1151 bfo->undo();
1152 delete bfo;
1153}
1154
1156 std::map<TCEString, int> invariantCounts;
1157 std::map<TCEString, int> variableCounts;
1158
1159 invariants_.clear();
1160 invariantsOfCount_.clear();
1161
1162 static int iaCounter= 0;
1163 for (int i = 0; i < ddg().programOperationCount(); i++) {
1165 const Operation& op = po.operation();
1166 if (op.numberOfInputs() == 1) {
1167 continue; // must be trigger
1168 }
1169 for (int k = 1; k <= op.numberOfInputs(); k++) {
1170 MoveNodeSet& inputNodeSet = po.inputNode(k);
1171 assert(inputNodeSet.count() == 1);
1172 MoveNode& inputNode = inputNodeSet.at(0);
1173 TCEString inputVal;
1174 if (mustBeTrigger(inputNode, po)) {
1175 continue;
1176 }
1177
1178 if (inputNode.isSourceVariable()) {
1180 inputNode.move().source());
1181 } else {
1182 if (inputNode.isSourceConstant()) {
1183 if (inputNode.move().source().isInstructionAddress()) {
1184 inputVal << "IADDR" << iaCounter++;
1185 } else {
1186 // todo: imms longer than 32 bits?
1187 inputVal <<
1188 inputNode.move().source().value().intValue();
1189 }
1190 } else {
1191 // unknown?
1192 return;
1193 }
1194 }
1195 if (ddg().isLoopInvariant(inputNode)) {
1196 invariantCounts[inputVal]++;
1197 invariants_.insert(std::make_pair(inputVal, &inputNode));
1198 } else {
1199 if (inputVal == "0") {
1200 std::cerr << "zero not loop invariant: "
1201 << inputNode.toString() << std::endl;
1202 }
1203 variableCounts[inputVal]++;
1204 }
1205
1206 }
1207 }
1208
1209 for (auto p: invariantCounts) {
1210#ifdef DEBUG_PRE_SHARE
1211 std::cerr << "usage count of invariant value: " << p.first
1212 << " is " << p.second << std::endl;
1213#endif
1214 invariantsOfCount_.insert(std::make_pair(p.second, p.first));
1215 }
1216
1217#ifdef DEBUG_PRE_SHARE
1218 for (auto p: invariants_) {
1219 std::cerr << "Invariant value: " << p.first << " used by mn: "
1220 << p.second->toString() << " of po: "
1221 << p.second->destinationOperation().toString() << std::endl;
1222 }
1223 for (auto i = invariantsOfCount_.rbegin();
1224 i != invariantsOfCount_.rend(); i++) {
1225 std::cerr << "Count: " << i->first << " for invariant value: "
1226 << i->second << std::endl;
1227 }
1228#endif
1229}
1230
1231/**
1232 * Allocate function units for pre-loop operand sharing.
1233 */
1235
1237
1238 preSharedOperandPorts_.clear();
1239 preLoopSharedOperands_.clear();
1240
1241 for (auto i = invariantsOfCount_.rbegin();
1242 i != invariantsOfCount_.rend(); i++) {
1243#ifdef DEBUG_PRE_SHARE
1244 std::cerr << "got invariant: " << i->second << " with usage count: "
1245 << i->first << std::endl;
1246#endif
1247 for (auto it = invariants_.lower_bound(i->second),
1248 end = invariants_.upper_bound(i->second); it != end; ++it) {
1249#ifdef DEBUG_PRE_SHARE
1250 std::cerr << "\tgot MN: " << it->second->toString() << " of PO: "
1251 << it->second->destinationOperation().toString()
1252 << std::endl;
1253#endif
1254 preAllocateFunctionUnits(it->second->destinationOperationPtr());
1255 }
1256 }
1257
1258#ifdef DEBUG_PRE_SHARE
1259 std::cerr << "Operand bindings to ports: " << std::endl;
1260#endif
1261 for (auto p : preSharedOperandPorts_) {
1262 auto fup = p.first;
1263 if (p.second != NULL) {
1264 MoveNode* mn = p.second;
1265 preLoopSharedOperands_[mn] = fup;
1266#ifdef DEBUG_PRE_SHARE
1267 TTAMachine::FunctionUnit* fu = fup->parentUnit();
1268 ProgramOperation& po = p.second->destinationOperation(0);
1269 std::cerr << "\tPort: " << fu->name() << "." << fup->name() <<
1270 " move: " << p.second->toString() << " of PO: " <<
1271 po.toString() << std::endl;
1272#endif
1273 } else {
1274#ifdef DEBUG_PRE_SHARE
1275 TTAMachine::FunctionUnit* fu = fup->parentUnit();
1276 std::cerr << "\tPort: " << fu->name() << "." << fup->name() <<
1277 " shared with multiple ops" << std::endl;
1278#endif
1279 }
1280 }
1281}
1282
1284 const Operation& op = po->operation();
1285#ifdef DEBUG_PRE_SHARE
1286 std::cerr << "Trying to preallocate for: " << po->toString()
1287 << std::endl;
1288#endif
1289
1290 // first phase only share port which is already
1291 // shared with same value.
1293 if (rv.state_ == NOT_SHARED) {
1294#ifdef DEBUG_PRE_SHARE
1295 std::cerr << "\t\tDid not find pre-shared, trying again.."
1296 << std::endl;
1297#endif
1298 // second phase, can reserve a new port.
1299 rv = preAllocateFunctionUnitsInner(po, op, false);
1300 }
1301
1302 // could not allocate even with shared ones. must steal from someone
1303 // just take first FU capable of executing the op.
1304 // find the port with least use.
1305 if (rv.state_ == NO_PORT) {
1306 releasePortForOp(op);
1307 }
1308}
1309
1311#ifdef DEBUG_PRE_SHARE
1312 std::cerr << "\tNo free fu for op: " << op.name() <<
1313 " have to revert earlier share" << std::endl;
1314#endif
1317 TCEString opName = op.name();
1318 TTAMachine::FUPort* bestPort = NULL;
1319
1320 int shareOpCount = INT_MAX;
1321 for (int j = 0; j < fuNav.count(); j++) {
1322 const TTAMachine::FunctionUnit& fu = *(fuNav.item(j));
1323 if (!fu.hasOperation(opName)) {
1324 continue;
1325 }
1326 const TTAMachine::HWOperation& hwop = *fu.operation(opName);
1327 for (int k = 1; k <= op.numberOfInputs(); k++) {
1328 TTAMachine::FUPort* port = hwop.port(k);
1329 if (port->isTriggering()) {
1330 continue;
1331 } else {
1332 std::map<TTAMachine::FUPort*, MoveNode*>::iterator i =
1333 preSharedOperandPorts_.find(port);
1334 if (i != preSharedOperandPorts_.end() && i->second != NULL) {
1335 int destOpCount = preSharedOperandPorts_.count(port);
1336#ifdef DEBUG_BUBBLEFISH_SCHEDULER
1337 std::cerr << "\t\t\tReserved port: " <<
1338 port->parentUnit()->name() << "." <<
1339 port->name() << " has " << destOpCount <<
1340 " shared operations using it" << std::endl;
1341#endif
1342 if (destOpCount < shareOpCount) {
1343 bestPort = port;
1344 shareOpCount = destOpCount;
1345 }
1346 }
1347 }
1348 }
1349 }
1350
1351 assert(bestPort != NULL);
1352#ifdef DEBUG_PRE_SHARE
1353 std::cerr << "\t\tPass 3: UnReserved port: " <<
1354 bestPort->parentUnit()->name() << "." <<
1355 bestPort->name() << " because of " <<
1356 op.name() << std::endl;
1357#endif
1358 preSharedOperandPorts_.erase(bestPort);
1359 preSharedOperandPorts_.insert(std::make_pair(bestPort, (MoveNode*)NULL));
1360}
1361
1362
1363
1365 ProgramOperationPtr po, const Operation& op,
1366 bool onlySharedWithAnother) {
1367
1368 TCEString opName = op.name();
1371
1372 bool fuFound = false;
1373 // we have a loop invariant.
1374 // Check which FUs can execute this operation.
1375 for (int j = 0; j < fuNav.count(); j++) {
1376 const TTAMachine::FunctionUnit& fu = *(fuNav.item(j));
1377 if (!fu.hasOperation(opName)) {
1378 continue;
1379 }
1380 const TTAMachine::HWOperation& hwop = *fu.operation(opName);
1382 po, op, hwop, onlySharedWithAnother);
1383 switch(rv.state_) {
1384 case SHARED:
1385 case NO_LOOP_INVARIANT:
1386 return rv;
1387 case NOT_SHARED:
1388#ifdef DEBUG_PRE_SHARE
1389 std::cerr << "\t\tfu found but cannot share: " << fu.name()
1390 << std::endl;
1391#endif
1392 fuFound = true;
1393 default:
1394 break;
1395 }
1396 }
1397 if (targetMachine().controlUnit()->hasOperation(opName)) {
1398 fuFound = true;
1399 }
1400 return fuFound ?
1403}
1404
1406 ProgramOperationPtr po, const Operation& op,
1407 const TTAMachine::HWOperation& hwop, bool onlySharedWithAnother) {
1408
1409 bool hasLoopInvariant = false;
1410 for (int k = 1; k <= op.numberOfInputs(); k++) {
1411 MoveNodeSet& inputNodeSet = po->inputNode(k);
1412 assert(inputNodeSet.count() == 1);
1413 MoveNode& inputNode = inputNodeSet.at(0);
1414 if (!ddg().isLoopInvariant(inputNode)) {
1415 // still need to check if the port is free,
1416 // to not use all FU ports for shared operands.
1417 TTAMachine::FUPort* port = hwop.port(k);
1418 std::multimap<TTAMachine::FUPort*, MoveNode*>::iterator pi=
1419 preSharedOperandPorts_.find(port);
1420 if (pi != preSharedOperandPorts_.end() && pi->second != NULL) {
1421 return PreLoopShareInfo(NO_PORT);
1422 }
1423 continue;
1424 }
1425
1426 // we have a loop invariant.
1427 hasLoopInvariant = true;
1429 po, op, k, hwop, onlySharedWithAnother);
1430 if (rv.state_ == SHARED) {
1431 // Allocated to this FU now.
1432#ifdef DEBUG_PRE_SHARE
1433 std::cerr << "Allocating port for pre-loop opshare: "
1434 << rv.sharedPort_->parentUnit()->name() << "."
1435 << rv.sharedPort_->name() << " move: "
1436 << rv.sharedMN_->toString() << " of po: "
1438 << std::endl;
1439#endif
1441 std::make_pair(rv.sharedPort_,rv.sharedMN_));
1442 return rv;
1443 }
1444 if (rv.state_ == NO_PORT) {
1445 // cannot allocate this op to this FU
1446 return rv;
1447 }
1448 }
1449 return hasLoopInvariant ?
1452
1453}
1454
1456 ProgramOperationPtr po, const Operation& op, int operandIndex,
1457 const TTAMachine::HWOperation& hwop,
1458 bool onlySharedWithAnother) {
1459
1460 MoveNodeSet& inputNodeSet = po->inputNode(operandIndex);
1461 assert(inputNodeSet.count() == 1);
1462 MoveNode& inputNode = inputNodeSet.at(0);
1463
1464 TTAMachine::FUPort* port = hwop.port(operandIndex);
1465 bool isTrigger = port->isTriggering();
1466 int swappedOperandIndex = 0;
1467 if (isTrigger) {
1468 swappedOperandIndex = swapToUntrigger(po, op, operandIndex,inputNode);
1469 // still trigger? then try another FU?
1470 if (swappedOperandIndex) {
1471 port = hwop.port(swappedOperandIndex);
1472 } else {
1473#ifdef DEBUG_BUBBLEFISH_SCHEDULER
1474 std::cerr << "\t\tswap failed" << std::endl;
1475#endif
1477 }
1478 }
1479
1480 std::map<TTAMachine::FUPort*, MoveNode*>::iterator pi=
1481 preSharedOperandPorts_.find(port);
1482 if (pi == preSharedOperandPorts_.end()) {
1483 // if need to share with another use, do not allow reserving new
1484 // port.
1485 if (onlySharedWithAnother) {
1486 if (swappedOperandIndex) {
1487 revertTopOpt();
1488 }
1490 } else {
1491 // create new sharing, use first free
1492 assert(!port->isTriggering());
1493 return PreLoopShareInfo(inputNode, *port);
1494 }
1495 } else {
1496 MoveNode* prev = pi->second;
1497 if (prev == NULL) {
1498 // NULL means reserved for everybody. cannot own it.
1499 if (swappedOperandIndex) {
1500 revertTopOpt();
1501 }
1503 }
1504 // port already used for some operand share..
1505 // but is it same?
1506 if (prev->move().source().equals(
1507 inputNode.move().source())) {
1508 assert(!port->isTriggering());
1509 return PreLoopShareInfo(inputNode, *port);
1510 } else {
1511 // different input value than previous, cannot share or use this fu
1512 if (swappedOperandIndex) {
1513 revertTopOpt();
1514 }
1515#ifdef DEBUG_PRE_SHARE
1516 std::cerr << "\t\t\tport used by another sharing, cannot use"
1517 << std::endl;
1518#endif
1519 return PreLoopShareInfo(NO_PORT);
1520 }
1521 }
1522}
1523
1526 const std::string& payload) {
1527 for (int i = 0; i < po.inputMoveCount(); i++) {
1528 MoveNode& inputNode = po.inputMove(i);
1529 TTAProgram::Move& m = inputNode.move();
1530 m.addAnnotation(
1531 TTAProgram::ProgramAnnotation(id, payload));
1532 }
1533}
1534
1537 const std::string& payload) {
1538 for (int i = 0; i < po.outputMoveCount(); i++) {
1539 MoveNode& outputNode = po.outputMove(i);
1540 TTAProgram::Move& m = outputNode.move();
1541 m.addAnnotation(
1542 TTAProgram::ProgramAnnotation(id, payload));
1543 }
1544}
1545
1547#ifdef DEBUG_BUBBLEFISH_SCHEDULER
1548 std::cerr << "Reserving preallocated fus" << std::endl;
1549#endif
1550 for (int i = 0; i < ddg().programOperationCount(); i++) {
1552 const Operation& op = po.operation();
1553 TCEString opName = op.name();
1554
1555 const TTAMachine::FunctionUnit* preAllocatedFU = NULL;
1556 for (int j = 1; j <= op.numberOfInputs(); j++) {
1557 MoveNodeSet& inputNodes = po.inputNode(j);
1558 if (inputNodes.count() != 1) {
1559 assert(0);
1560 }
1561 MoveNode& inputNode = inputNodes.at(0);
1563 if (fup) {
1564 preAllocatedFU = fup->parentUnit();
1565 break;
1566 }
1567 }
1568 if (preAllocatedFU) {
1569 std::string fuName = preAllocatedFU->name();
1571 po,
1573 fuName);
1574
1577 fuName);
1578 } else {
1579 const TTAMachine::FunctionUnit* prevFU = nullptr;
1580 for (auto p: preSharedOperandPorts_) {
1581 if (p.second == NULL) {
1582 continue;
1583 }
1584 const TTAMachine::FunctionUnit* fu = p.first->parentUnit();
1585 if (fu == prevFU) {
1586 continue;
1587 }
1588 prevFU = fu;
1589 std::string fuName= fu->name();
1590
1593 fuName);
1594
1597 fuName);
1598 }
1599 }
1600 }
1601}
1602
1624
1626 auto i = preLoopSharedOperands_.find(&mn);
1627 if (i == preLoopSharedOperands_.end()) {
1628 return NULL;
1629 }
1630 return i->second;
1631}
1632
1634 currentFront_->deletingNode(deletedNode);
1635}
1636
1637
1639 while(!scheduledStack_.empty()) {
1640 BFOptimization* bfo = scheduledStack_.back();
1641 scheduledStack_.pop_back();
1642 delete bfo;
1643 }
1644}
1645
1647 MoveNodeMap bypasses;
1648 for (auto o : scheduledStack_) {
1649 auto f = dynamic_cast<BF2ScheduleFront*>(o);
1650 if (f != NULL) {
1651 f->appendBypassSources(bypasses);
1652 }
1653 }
1654 return bypasses;
1655}
#define __func__
#define assert(condition)
void annotateAllOutputs(ProgramOperation &po, TTAProgram::ProgramAnnotation::Id id, const std::string &payload)
void annotateAllInputs(ProgramOperation &po, TTAProgram::ProgramAnnotation::Id id, const std::string &payload)
std::shared_ptr< ProgramOperation > ProgramOperationPtr
Definition MoveNode.hh:53
static CmdLineOptions * cmdLineOptions()
static int verboseLevel()
static std::ostream & logStream()
void deletingNode(MoveNode *deletedNode)
void appendBypassSources(MoveNodeMap &map)
bool mustBeTrigger(const MoveNode &mn, const ProgramOperation &po)
void revertBBLiveRangeBookkeepingForDestination(MoveNode *mn)
SimpleResourceManager & rm()
BF2Scheduler(InterPassData &ipd, RegisterRenamer *renamer)
void nodeResurrected(MoveNode &mn)
DataDependenceGraph & ddg()
virtual int handleLoopDDG(DataDependenceGraph &, SimpleResourceManager &, const TTAMachine::Machine &, int tripCount, SimpleResourceManager *, bool testOnly) override
PreLoopShareInfo preAllocateFunctionUnitsInner(ProgramOperationPtr po, const Operation &op, bool onlySharedWithAnother)
static void writeDotWithNameAndNodeID(DataDependenceGraph &ddg, const TCEString &namePrefix, const MoveNode &mn)
std::multimap< TCEString, MoveNode * > invariants_
std::set< const TTAMachine::RegisterFile *, TTAMachine::MachinePart::Comparator > possibleTempRegRFs(const MoveNode &mn, bool tempRegAfter, const TTAMachine::RegisterFile *forbiddenRF=nullptr)
bool isDeadResult(MoveNode &mn) const
SimpleResourceManager * prologRM_
static bool isSourceUniversalReg(const MoveNode &mn)
void reservePreallocatedFUs()
static bool isDestinationUniversalReg(const MoveNode &mn)
std::multimap< TTAMachine::FUPort *, MoveNode * > preSharedOperandPorts_
TTAProgram::MoveGuard * jumpGuard()
void releasePortForOp(const Operation &op)
virtual int handleDDG(DataDependenceGraph &ddg, SimpleResourceManager &rm, const TTAMachine::Machine &targetMachine, int minCycle=0, bool testOnly=false)
bool isTrigger(const TTAMachine::Unit &unit, MoveNode &mn)
void unreservePreallocatedFUs()
SimpleResourceManager * rm_
void countLoopInvariantValueUsages()
RegisterRenamer * renamer_
std::multimap< int, TCEString > invariantsOfCount_
BUMoveNodeSelector & selector()
LLVMTCECmdLineOptions * options_
DataDependenceGraph * prologDDG_
MoveNodeMap bypassNodes()
BF2ScheduleFront * currentFront_
TTAMachine::FUPort * isPreLoopSharedOperand(MoveNode &mn) const
bool hasUnscheduledSuccessors(MoveNode &mn) const
void preAllocateFunctionUnits(ProgramOperationPtr po)
MoveNodeDuplicator & duplicator()
DataDependenceGraph::NodeSet removedMoves_
const TTAMachine::Machine * targetMachine_
TTAMachine::Unit * getDstUnit(MoveNode &mn)
void nodeKilled(MoveNode &mn)
std::list< ProgramOperation * > loopBufOps_
void revertBBLiveRangeBookkeepingForSource(MoveNode *mn)
void scheduleDDG(DataDependenceGraph &ddg, SimpleResourceManager &rm, const TTAMachine::Machine &targetMachine)
DataDependenceGraph::NodeSet dreRemovedMoves_
std::map< MoveNode *, TTAMachine::FUPort *, MoveNode::Comparator > preLoopSharedOperands_
std::map< MoveNode *, MoveNode *, MoveNode::Comparator > MoveNodeMap
void finalizeSchedule()
const TTAMachine::Machine & targetMachine() const
DataDependenceEdge * findBypassEdge(const MoveNode &mn)
void allocateFunctionUnits()
void eraseFromMoveNodeUseSet(LiveRangeData::MoveNodeUseMapSet &mnuMap, const TCEString &reg, MoveNode *mn)
MoveNode * jumpGuardWrite_
void nodeAndCopyKilled(MoveNode &mn)
MoveNode * jumpNode_
SimpleResourceManager * prologRM()
int scheduleFrontFromMove(MoveNode &mn)
virtual std::string shortDescription() const override
MoveNodeDuplicator * duplicator_
std::vector< BFOptimization * > scheduledStack_
BUMoveNodeSelector * selector_
int swapToUntrigger(ProgramOperationPtr po, const Operation &op, int operandIndex, MoveNode &trig)
DataDependenceGraph * ddg_
void deletingNode(MoveNode *deletedNode)
MoveNode * loopLimitNode()
static void clearPrologMoves()
virtual void initializeReadylist()
Initializes ready list from nodes that are ready.
virtual MoveNodeGroup candidates()
TTAProgram::BasicBlock & basicBlock()
static MoveNode * findTrigger(const ProgramOperation &po, const TTAMachine::Machine &mach)
BoostGraph * rootGraph()
int nodeCount() const
BoostGraph * parentGraph()
virtual void removeNode(Node &node)
virtual NodeSet successors(const Node &node, bool ignoreBackEdges=false, bool ignoreForwardEdges=false) const
Node & node(const int index) const
bool hasNode(const Node &) const
virtual void dropNode(Node &node)
virtual const TCEString & name() const
virtual EdgeSet inEdges(const Node &node) const
static std::string toString(const T &source)
DependenceType dependenceType() const
EdgeReason edgeReason() const
ProgramOperation & programOperation(int index)
MoveNode * onlyGuardDefOfMove(MoveNode &moveNode)
const BasicBlockNode & getBasicBlockNode(const MoveNode &mn) const
void writeToXMLFile(std::string fileName) const
void setMachine(const TTAMachine::Machine &machine)
static TCEString registerName(const TTAMachine::RegisterFile &rf, int index, char delim='.')
virtual void writeToDotFile(const TCEString &fileName) const
std::set< GraphNode *, typename GraphNode::Comparator > NodeSet
Definition Graph.hh:53
std::set< GraphEdge *, typename GraphEdge::Comparator > EdgeSet
Definition Graph.hh:54
int nodeID() const
InterPassDatum & datum(const std::string &key)
virtual bool dumpDDGsDot() const
virtual bool dumpDDGsXML() const
static PortSet findWritePorts(const TTAMachine::Unit &rf)
static int canSourceWriteToAnyDestinationPort(const MoveNode &src, PortSet &ports, bool ignoreGuard=false)
static PortSet findReadPorts(const TTAMachine::Unit &rf)
static bool isConnected(const TTAMachine::Port &sourcePort, const TTAMachine::Port &destinationPort, const TTAMachine::Guard *guard=NULL)
static bool canAnyPortWriteToDestination(PortSet &ports, const MoveNode &dest)
std::set< const TTAMachine::Port *, const TTAMachine::MachinePart::Comparator > PortSet
void setBBN(BasicBlockNode &bbn)
MoveNode * getMoveNode(MoveNode &mn)
int nodeCount() const
MoveNode & node(int index) const
int count() const
MoveNode & at(int index)
bool isSourceVariable() const
Definition MoveNode.cc:196
bool isMove() const
bool isDestinationOperation() const
std::string toString() const
Definition MoveNode.cc:576
TTAProgram::Move & move()
bool isScheduled() const
Definition MoveNode.cc:409
bool isSourceConstant() const
Definition MoveNode.cc:238
bool isDestinationVariable() const
Definition MoveNode.cc:264
ProgramOperation & destinationOperation(unsigned int index=0) const
virtual TCEString name() const
Definition Operation.cc:93
virtual int numberOfInputs() const
Definition Operation.cc:192
virtual bool canSwap(int id1, int id2) const
Definition Operation.cc:470
int outputMoveCount() const
const Operation & operation() const
int inputMoveCount() const
MoveNodeSet & inputNode(int in) const
std::string toString() const
MoveNode & inputMove(int index) const
MoveNode & outputMove(int index) const
void setSelector(MoveNodeSelector *selector)
void initialize(DataDependenceGraph &ddg)
virtual void undo()
Definition Reversible.cc:69
virtual bool killDeadResults() const
InterPassData & interPassData()
int intValue() const
Definition SimValue.cc:895
virtual int smallestCycle() const override
void setMaxCycle(unsigned int maxCycle)
virtual unsigned initiationInterval() const
void clear()
Clears all bookkeeping done by this RM. The RM can then be reused for different BB.
void setDDG(const DataDependenceGraph *ddg)
virtual int largestCycle() const override
FunctionUnit * parentUnit() const
Definition BaseFUPort.cc:96
virtual TCEString name() const
virtual bool isTriggering() const
Definition FUPort.cc:182
virtual HWOperation * operation(const std::string &name) const
virtual bool hasOperation(const std::string &name) const
virtual FUPort * port(int operand) const
ComponentType * item(int index) const
virtual FunctionUnitNavigator functionUnitNavigator() const
Definition Machine.cc:380
Unit * parentUnit() const
virtual std::string name() const
Definition Port.cc:141
void removeAnnotations(ProgramAnnotation::Id id=ProgramAnnotation::ANN_UNDEF_ID)
void addAnnotation(const ProgramAnnotation &annotation)
bool hasAnnotations(ProgramAnnotation::Id id=ProgramAnnotation::ANN_UNDEF_ID) const
LiveRangeData * liveRangeData_
const TTAMachine::Guard & guard() const
Definition MoveGuard.cc:86
MoveGuard & guard() const
Definition Move.cc:345
bool isUnconditional() const
Definition Move.cc:154
Terminal & source() const
Definition Move.cc:302
bool isJump() const
Definition Move.cc:164
Terminal & destination() const
Definition Move.cc:323
Id
the ID in TPEF is 24 bits, here enum
@ ANN_REJECTED_UNIT_SRC
Src. unit rejected.
@ ANN_REJECTED_UNIT_DST
Dst. unit rejected.
@ ANN_CONN_CANDIDATE_UNIT_DST
Dst. unit candidate.
@ ANN_CONN_CANDIDATE_UNIT_SRC
Src. unit candidate.
virtual SimValue value() const
Definition Terminal.cc:178
virtual int index() const
Definition Terminal.cc:274
virtual bool equals(const Terminal &other) const =0
virtual bool isGPR() const
Definition Terminal.cc:107
virtual int operationIndex() const
Definition Terminal.cc:364
virtual bool isInstructionAddress() const
Definition Terminal.cc:87
virtual bool isUniversalMachineRegister() const
Definition Terminal.cc:166
virtual const TTAMachine::Port & port() const
Definition Terminal.cc:378
virtual const TTAMachine::RegisterFile & registerFile() const
Definition Terminal.cc:225
virtual bool isFUPort() const
Definition Terminal.cc:118
TTAMachine::FUPort * sharedPort_
MoveNodeUseMapSet regFirstUses_
MoveNodeUseMapSet regLastUses_
std::set< MoveNodeUse > MoveNodeUseSet
MoveNodeUseMapSet regFirstDefines_
std::map< TCEString, MoveNodeUseSet > MoveNodeUseMapSet
MoveNodeUseMapSet regDefines_