OpenASIP  2.0
BBSchedulerController.cc
Go to the documentation of this file.
1 /*
2  Copyright (c) 2002-2020 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 BBSchedulerController.cc
26  *
27  * Definition of BBSchedulerController class.
28  *
29  * @author Pekka Jääskeläinen 2006-2011 (pjaaskel-no.spam-cs.tut.fi)
30  * @author Heikki Kultala 2009 (hkultala-no.spam-cs.tut.fi)
31  * @note rating: red
32  */
33 
34 #include <set>
35 #include <string>
36 #include <cstdlib>
37 
38 #include <boost/timer.hpp>
39 
40 #include "BBSchedulerController.hh"
41 #include "ControlFlowGraph.hh"
42 #include "DataDependenceGraph.hh"
44 #include "SimpleResourceManager.hh"
45 #include "Procedure.hh"
46 #include "ControlUnit.hh"
47 #include "Machine.hh"
48 #include "Instruction.hh"
49 #include "BasicBlock.hh"
50 #include "ControlFlowGraphPass.hh"
51 #include "SchedulerPass.hh"
52 #include "SoftwareBypasser.hh"
54 #include "Program.hh"
55 #include "TCEString.hh"
56 #include "Application.hh"
57 #include "LLVMTCECmdLineOptions.hh"
61 #include "InterPassData.hh"
63 #include "BasicBlockScheduler.hh"
64 #include "RegisterRenamer.hh"
65 #include "BUBasicBlockScheduler.hh"
66 #include "BF2Scheduler.hh"
67 #include "DisassemblyRegister.hh"
68 
69 #include "LoopAnalyzer.hh"
70 #include "ScheduleEstimator.hh"
71 
72 namespace TTAMachine {
73  class UniversalMachine;
74 }
75 
76 //#define DEBUG_OUTPUT
77 //#define CFG_SNAPSHOTS
78 //#define BIG_DDG_SNAPSHOTS
79 //#define SW_BYPASSING_STATISTICS
80 
81 // getting slow with very big II's. limit it. TODO: make this cmdline param.
82 static const int MAXIMUM_II = 60;
83 static const int DEFAULT_LOWMEM_MODE_THRESHOLD = 200000;
84 
85 /**
86  * Constructs the basic block scheduler.
87  *
88  * @param data Interpass data
89  * @param bypasser Helper module implementing software bypassing
90  * @param delaySlotFiller Helper module implementing jump delay slot filling
91  */
93  const TTAMachine::Machine& targetMachine,
94  InterPassData& data,
95  SoftwareBypasser* bypasser,
96  CopyingDelaySlotFiller* delaySlotFiller,
97  DataDependenceGraph* bigDDG) :
99  ProgramPass(data), targetMachine_(targetMachine),
100  scheduledProcedure_(NULL), bigDDG_(bigDDG),
101  softwareBypasser_(bypasser), delaySlotFiller_(delaySlotFiller),
102  basicBlocksScheduled_(0), totalBasicBlocks_(0), progressBar_(NULL) {
103 
104  CmdLineOptions *cmdLineOptions = Application::cmdLineOptions();
105  options_ = dynamic_cast<LLVMTCECmdLineOptions*>(cmdLineOptions);
106 
107 }
108 
110  delete progressBar_;
111  progressBar_ = NULL;
112 }
113 
114 /**
115  * Schedules a single basic block.
116  *
117  * @param bb The basic block to schedule.
118  * @param targetMachine The target machine.
119  * @exception Exception several TCE exceptions can be thrown in case of
120  * a scheduling error.
121  */
122 void
124  TTAProgram::BasicBlock& bb, const TTAMachine::Machine& targetMachine,
126  // TODO: define them somewhere in one place.
127  static const TCEString SP_DATUM = "STACK_POINTER";
128  static const TCEString FP_DATUM = "FRAME_POINTER";
129  static const TCEString RV_DATUM = "RV_REGISTER";
130  // high part of 64-bit return values.
131  static const TCEString RV_HIGH_DATUM = "RV_HIGH_REGISTER";
132 
133  if (bb.instructionCount() == 0)
134  return;
135 
136  bool bbScheduled = false;
137 
138  RegisterRenamer* rr = NULL;
139 
141  dynamic_cast<SchedulerCmdLineOptions*>(
143 
144  // create register renamer if enabled and we know the
145  // reserved registers.
146  if (options != NULL && options->renameRegisters() && bigDDG_ != NULL
147  && BasicBlockPass::interPassData().hasDatum(SP_DATUM) &&
151  rr = new RegisterRenamer(targetMachine, bbn->basicBlock());
152  }
153 
154  std::vector<DDGPass*> bbSchedulers;
155 
156  if (options_ != NULL && options_->useBubbleFish2Scheduler()) {
157  bbSchedulers.push_back(new BF2Scheduler(
159  } else if (options_ != NULL && options_->useBUScheduler()) {
160  bbSchedulers.push_back(new BUBasicBlockScheduler(
162  } else if (options_ != NULL && options_->useTDScheduler()) {
163  bbSchedulers.push_back(new BasicBlockScheduler(
165  } else {
166  bbSchedulers.push_back(new BF2Scheduler(
168  }
169 
170  if (options_->isLoopOptDefined() &&
171  cfg_->isSingleBBLoop(*bbn) &&
172  bb.lastInstruction().hasJump() &&
173  bigDDG_ != NULL) {
174 
175  LoopAnalyzer::LoopAnalysisResult* analysis = NULL;
176  if (Application::verboseLevel() > 1) {
178  << "CFG detects single BB loop" << std::endl
179  << "tripcount: " << bb.tripCount() << std::endl;
180  }
181  if (bigDDG_ && bb.tripCount() == 0 && options_->useBubbleFish2Scheduler()) {
182  analysis = LoopAnalyzer::analyze(*bbn, *bigDDG_);
183  if (analysis != NULL) {
184  bb.setTripCount(analysis->iterationCount);
185  if (analysis->counterValueNode == NULL) {
186  if (Application::verboseLevel() > 1) {
188  << "loop analyzis analyzed loop to have fixed trip count"
189  << analysis->iterationCount << std::endl;
190  }
191  } else {
192  if (Application::verboseLevel() > 1) {
194  << "loop analyzis analyzed loop to have variable trip count"
195  << analysis->counterValueNode->toString()
196  << " + "
197  << analysis->iterationCount << " divided by"
198  << analysis->counterMultiplier << std::endl;
199  }
200  }
201  }
202  }
203 
204  if ((((bb.tripCount() > 0 || (analysis && analysis->counterValueNode)) &&
205  MachineConnectivityCheck::tempRegisterFiles(targetMachine).empty()) ||
207  if (analysis) {
208  (static_cast<BF2Scheduler*>(bbSchedulers[0]))->
209  setLoopLimits(analysis);
210  }
211  // software pipeline instead of calling the flat BB scheduler
212  if (Application::verboseLevel() > 1) {
214  << "executing loop pass with trip count " << bb.tripCount()
215  << std::endl;
216  }
217 
218  if (executeLoopPass(
219  bb, targetMachine, irm, bbSchedulers, bbn) ) {
220  bbScheduled = true;
221  } else {
222  if (Application::verboseLevel() > 1) {
224  << "loop scheduler failed, using basic block "
225  << "scheduler instead" << std::endl;
226  }
227  bbScheduled = false;
228  }
229  }
230  // if not scheduled yet (or loop scheduling failed)
231  }
232  if (!bbScheduled) {
233 
235  bb, targetMachine, irm, bbSchedulers, bbn);
236 
237  if (Application::verboseLevel() > 0) {
238  if (progressBar_ != NULL)
239  ++(*progressBar_);
240  }
241 
243  }
244  if (rr != NULL) {
245  delete rr;
246  }
247 
248  // these are no longer needed. delete them to save memory.
249  if (bb.liveRangeData_ != NULL) {
250  bb.liveRangeData_->regFirstDefines_.clear();
251  bb.liveRangeData_->regDefines_.clear();
252  bb.liveRangeData_->regLastUses_.clear();
253 
254  bb.liveRangeData_->regDefReaches_.clear();
256  bb.liveRangeData_->regFirstUses_.clear();
257  bb.liveRangeData_->regDefines_.clear();
258  } else {
259  std::cerr << "Wargning: BB liverange data null for: "
260  << bbn->toString() << std::endl;
261  }
262  for (unsigned int i = 0; i < bbSchedulers.size(); i++)
263  delete bbSchedulers[i];
264 }
265 
266 #ifdef DEBUG_REG_COPY_ADDER
267 static int graphCount = 0;
268 #endif
269 
270 /**
271  * Schedules a procedure.
272  *
273  * The original procedure is modified during scheduling.
274  *
275  * @param procedure The procedure to schedule.
276  * @param targetMachine The target machine.
277  * @todo remove the targetMachine argument. The machine is given in the
278  * constructor and assumed to be the same for whole lifetime of the
279  * scheduler instance.
280  * @exception Exception In case of an error during scheduling. The exception
281  * type can be any subtype of Exception.
282  */
283 void
285  TTAProgram::Procedure& procedure,
286  const TTAMachine::Machine& targetMachine) {
288 
289  if (Application::verboseLevel() > 0) {
290  totalBasicBlocks_ = cfg.nodeCount() - 3;
292  << " -- " << totalBasicBlocks_ << " basic blocks" << std::endl;
294 
295  const bool enableProgressBar = false;
296  if (progressBar_ == NULL) {
297  if (enableProgressBar) {
298  progressBar_ =
299  new boost::progress_display(totalBasicBlocks_ + 1);
300  }
301  } else {
302  progressBar_->restart(totalBasicBlocks_ + 1);
303  }
304  }
305 
306 #ifdef CFG_SNAPSHOTS
307  cfg.writeToDotFile(procedure.name() + "_cfg.dot");
308 #endif
309 
312  int lowMemThreshold = DEFAULT_LOWMEM_MODE_THRESHOLD;
313 
314  if (opts != NULL && opts->lowMemModeThreshold() > -1) {
315  lowMemThreshold = opts->lowMemModeThreshold();
316  }
317 
318  if (procedure.instructionCount() < lowMemThreshold) {
319  // create the procedure-wide ddg.
322 
323  if (options_ != NULL && options_->dumpDDGsDot()) {
325  (boost::format("proc_%s_before_scheduling.dot") %
326  bigDDG_->name()).str());
327  }
328 
329  if (options_ != NULL && options_->dumpDDGsXML()) {
331  (boost::format("proc_%s_before_scheduling.xml") %
332  bigDDG_->name()).str());
333  }
334  }
335 
336  if (delaySlotFiller_ != NULL && bigDDG_ != NULL) {
337  delaySlotFiller_->initialize(cfg, *bigDDG_, targetMachine);
338  }
339 
340 #ifdef BIG_DDG_SNAPSHOTS
341  bigDDG_->writeToDotFile(bigDDG_->name() + "_unscheduled_ddg.dot");
342 #endif
343  scheduledProcedure_ = &procedure;
344 
345  // dsf also called between scheduling.. have to update these before it.
346  // delay slot filler needs refs to be into instrs in cfg, not in
347  // original program
349 
350  procedure.clear();
351 
352  handleControlFlowGraph(cfg, targetMachine);
353 
354  if (delaySlotFiller_ != NULL && bigDDG_ != NULL) {
355  delaySlotFiller_->fillDelaySlots(cfg, *bigDDG_, targetMachine);
356  }
357 
358 #ifdef CFG_SNAPSHOTS
359  cfg.writeToDotFile(procedure.name() + "_cfg_after.dot");
360 #endif
361 
362  // now all basic blocks are scheduled, let's put them back to the
363  // original procedure
364  cfg.copyToProcedure(procedure);
365  if (bigDDG_ != NULL) {
366 
367  if (options_ != NULL && options_->dumpDDGsDot()) {
369  (boost::format("proc_%s_after_scheduling.dot") % bigDDG_->name())
370  .str());
371  }
372 
373  if (options_ != NULL && options_->dumpDDGsXML()) {
375  (boost::format("proc_%s_after_scheduling.xml") % bigDDG_->name())
376  .str());
377  }
378  delete bigDDG_;
379  bigDDG_ = NULL;
380  }
381  if (delaySlotFiller_ != NULL) {
383  }
384  scheduledProcedure_ = NULL;
385 }
386 
387 /**
388  * Schedules all nodes in a control flow graph.
389  *
390  * The original control flow graph nodes are modified during scheduling.
391  *
392  * @param cfg The control flow graph to schedule.
393  * @param targetMachine The target machine.
394  * @exception Exception In case of an error during scheduling. The exception
395  * type can be any subtype of Exception.
396  */
397 void
399  ControlFlowGraph& cfg, const TTAMachine::Machine& targetMachine) {
400  return handleCFGDDG(cfg, bigDDG_, targetMachine);
401 }
402 
403 /**
404  * Schedules a program.
405  *
406  * The original program is modified during scheduling.
407  *
408  * @param program The program to schedule.
409  * @param targetMachine The target machine.
410  * @exception Exception In case of an error during scheduling. The exception
411  * type can be any subtype of Exception.
412  */
413 void
415  TTAProgram::Program& program, const TTAMachine::Machine& targetMachine) {
416  ProgramPass::executeProcedurePass(program, targetMachine, *this);
417 }
418 
419 /**
420  * A short description of the pass, usually the optimization name,
421  * such as "basic block scheduler".
422  *
423  * @return The description as a string.
424  */
425 std::string
427  return "Instruction scheduler with a basic block scope.";
428 }
429 
430 /**
431  * Optional longer description of the pass.
432  *
433  * This description can include usage instructions, details of choice of
434  * algorithmic details, etc.
435  *
436  * @return The description as a string.
437  */
438 std::string
440  return
441  "Basic block scheduler that uses the longest path information of "
442  "data dependency graph to prioritize the ready list. Assumes that "
443  "the input has registers allocated and no connectivity missing.";
444 }
445 
446 
447 /**
448  * Helper function used to create DDG for BBPass.
449  *
450  * Overrided version in order to use subgraphs.
451  *
452  * @param bb BasicBlock where DDG is to be created from
453  */
456  TTAProgram::BasicBlock& bb, const TTAMachine::Machine& mach) {
457  if (bigDDG_ != NULL) {
458  return bigDDG_->createSubgraph(bb);
459  } else {
460  return this->ddgBuilder().build(
462  scheduledProcedure_->name() + '_' +
464  }
465 }
466 
467 /**
468  * Creates a DDG from the given basic block and executes the set of DDG passes
469  * for that.
470  */
471 void
473  TTAProgram::BasicBlock& bb, const TTAMachine::Machine& targetMachine,
475  std::vector<DDGPass*> ddgPasses, BasicBlockNode* bbn) {
476  int minCycle = 0;
477  DataDependenceGraph* ddg = NULL;
478  SimpleResourceManager* rm = NULL;
479  // Used for live info dumping.
480  static int bbNumber = 0;
481  int min = INT_MAX;
482  int fastest = 0;
483  if (ddgPasses.size() > 1) {
484  for (unsigned int i = 0; i < ddgPasses.size(); i++) {
485  ddg = createDDGFromBB(bb, targetMachine);
486  rm = SimpleResourceManager::createRM(targetMachine);
487  rm->setDDG(ddg);
488  rm->setCFG(cfg_);
489  rm->setBBN(bbn);
490 
491  int size =
492  ddgPasses[i]->handleDDG(*ddg, *rm, targetMachine, minCycle, true);
493  if (size < min) {
494  min = size;
495  fastest = i;
496  }
498  delete ddg;
499  ddg = NULL;
500  }
501  }
502  ddg = createDDGFromBB(bb, targetMachine);
503  rm = SimpleResourceManager::createRM(targetMachine);
504  rm->setDDG(static_cast<DataDependenceGraph*>(ddg->rootGraph()));
505  rm->setCFG(cfg_);
506  rm->setBBN(bbn);
507 
508  if (options_ != NULL && options_->printResourceConstraints()) {
509  TCEString ddgName = ddg->name();
510  // Use the BBN id if possible so it's easier to find the matching BBs when
511  // looking at the if-conversion CFGs.
512  if (bbn != NULL)
513  ddgName << bbn->nodeID();
514  else
515  ddgName << bbNumber;
516  ResourceConstraintAnalyzer rcAnalyzer(*ddg, *rm, ddgName);
517  rcAnalyzer.analyzePreSchedule();
518  }
519 
520 
521 #ifdef DDG_SNAPSHOTS
522  std::string name = "scheduling";
523  ddgSnapshot(ddg, name, false);
524 #endif
525 
526  try {
527  ddgPasses[fastest]->handleDDG(*ddg, *rm, targetMachine, minCycle);
528  if (bbn->isHWLoop()) {
530  ddg->largestCycle() + 1 - ddg->smallestCycle());
531  }
532  } catch (const Exception &e) {
534  abortWithError("Scheduling failed!");
535  }
536 
537 #ifdef DDG_SNAPSHOTS
538  std::string name = "scheduling";
539  ddgSnapshot(ddg, name, true);
540 #endif
541 
542  copyRMToBB(*rm, bb, targetMachine, irm);
543 
544  bbNumber++;
545 
546  if (options_ != NULL && options_->printResourceConstraints()) {
547  TCEString ddgName = ddg->name();
548  // Use the BBN id if possible so it's easier to find the matching BBs when
549  // looking at the if-conversion CFGs.
550  if (bbn != NULL)
551  ddgName << bbn->nodeID();
552  else
553  ddgName << bbNumber;
554  ResourceConstraintAnalyzer rcAnalyzer(*ddg, *rm, ddgName);
555  rcAnalyzer.analyze();
556  }
557 
558  if (delaySlotFiller_ != NULL && bigDDG_ != NULL) {
559  rm->clearOldResources();
561  } else {
563  }
564 
565  // print some stats about the loop kernel body DDGs
566  if (Application::verboseLevel() > 1 && bb.isInInnerLoop()) {
568  << "DDG height " << ddg->height() << std::endl;
569  }
570 
571  delete ddg;
572 }
573 
574 /* Returns true if node count changed */
577  const TTAMachine::Machine& targetMachine, int nodeCount) {
578 
579  TCEString procName = cfg.procedureName();
580  if (procName == "") procName = cfg.name();
581 
582  if (!bb.isNormalBB() || bb.isScheduled()) {
583  return false;
584  }
585 
587  bb.basicBlock(), targetMachine,
588  cfg.instructionReferenceManager(), &bb);
589  bb.setScheduled();
590 
591  if (delaySlotFiller_ != NULL && bigDDG_ != NULL) {
593  }
594 
595  // if some node is removed, make sure does not skip some node and
596  // then try to handle too many nodes.
597  if (cfg.nodeCount() != nodeCount) {
598  return true;
599  }
600  return false;
601 }
602 void
604  ControlFlowGraph& cfg,
605  DataDependenceGraph* ddg,
606  const TTAMachine::Machine& targetMachine) {
607  cfg_ = &cfg;
608  bigDDG_ = ddg;
609 
611  est.handleControlFlowGraph(cfg, targetMachine);
612 
613  int nodeCount = cfg.nodeCount();
614 
615  // for handle single-BB-loops
616  for (int bbIndex = 0; bbIndex < nodeCount; ++bbIndex) {
617  BasicBlockNode& bb = cfg.node(bbIndex);
618  if (!cfg.isSingleBBLoop(bb)) {
619  continue;
620  }
621 
622  if (handleBBNode(cfg, bb, targetMachine, nodeCount)) {
623  nodeCount = cfg.nodeCount();
624  bbIndex = 0;
625  }
626  }
627 
628  // then handle BBs which do not have outgoing jumps.
629  for (int bbIndex = 0; bbIndex < nodeCount; ++bbIndex) {
630  BasicBlockNode& bb = cfg.node(bbIndex);
631  auto jumpDest = cfg.jumpSuccessor(bb);
632  if (jumpDest != nullptr && jumpDest->isNormalBB()) {
633  continue;
634  }
635 
636  if (handleBBNode(cfg, bb, targetMachine, nodeCount)) {
637  nodeCount = cfg.nodeCount();
638  bbIndex = 0;
639  }
640  }
641 
642 
643  for (int bbIndex = cfg.nodeCount() -1; bbIndex >= 0; --bbIndex) {
644  BasicBlockNode& bb = cfg.node(bbIndex);
645  auto jumpDest = cfg.jumpSuccessor(bb);
646  if (jumpDest == nullptr || !jumpDest->isNormalBB()) {
647  continue;
648  }
649 
650  if (cfg.allScheduledInBetween(bb, *jumpDest)) {
651  if (handleBBNode(cfg, bb, targetMachine, nodeCount)) {
652  nodeCount = cfg.nodeCount();
653  bbIndex = nodeCount -1;
654  }
655  }
656  }
657 
658  for (int bbIndex = cfg.nodeCount() -1; bbIndex >= 0; --bbIndex) {
659  BasicBlockNode& bb = cfg.node(bbIndex);
660  if (handleBBNode(cfg, bb, targetMachine, nodeCount)) {
661  nodeCount = cfg.nodeCount();
662  bbIndex = nodeCount -1;
663  }
664  }
665 }
666 
CopyingDelaySlotFiller::addResourceManager
void addResourceManager(TTAProgram::BasicBlock &bbn, SimpleResourceManager &rm)
Definition: CopyingDelaySlotFiller.cc:691
ProcedurePass
Definition: ProcedurePass.hh:53
DataDependenceGraph::SINGLE_BB_LOOP_ANTIDEPS
@ SINGLE_BB_LOOP_ANTIDEPS
Definition: DataDependenceGraph.hh:81
TTAProgram::Program
Definition: Program.hh:63
SchedulerCmdLineOptions::isLoopOptDefined
virtual bool isLoopOptDefined() const
Definition: SchedulerCmdLineOptions.cc:237
CopyingDelaySlotFiller.hh
ResourceConstraintAnalyzer
Definition: ResourceConstraintAnalyzer.hh:49
BBSchedulerController::handleCFGDDG
virtual void handleCFGDDG(ControlFlowGraph &cfg, DataDependenceGraph *ddg, const TTAMachine::Machine &targetMachine)
Definition: BBSchedulerController.cc:603
MoveNode::toString
std::string toString() const
Definition: MoveNode.cc:576
MachineConnectivityCheck.hh
ControlFlowGraph::copyToProcedure
void copyToProcedure(TTAProgram::Procedure &proc, TTAProgram::InstructionReferenceManager *irm=NULL)
Definition: ControlFlowGraph.cc:1448
BoostGraph::node
Node & node(const int index) const
SchedulerPass.hh
CopyingDelaySlotFiller::bbnScheduled
void bbnScheduled(BasicBlockNode &bbn)
Definition: CopyingDelaySlotFiller.cc:640
BBSchedulerController::bigDDG_
DataDependenceGraph * bigDDG_
whole-procedure DDG.
Definition: BBSchedulerController.hh:123
BBSchedulerController::handleProgram
virtual void handleProgram(TTAProgram::Program &program, const TTAMachine::Machine &targetMachine) override
Definition: BBSchedulerController.cc:414
Procedure.hh
ProgramPass
Definition: ProgramPass.hh:52
LiveRangeData::regDefines_
MoveNodeUseMapSet regDefines_
Definition: LiveRangeData.hh:78
BBSchedulerController::options_
LLVMTCECmdLineOptions * options_
Definition: BBSchedulerController.hh:137
ControlFlowGraph::updateReferencesFromProcToCfg
void updateReferencesFromProcToCfg()
Definition: ControlFlowGraph.cc:2207
SimpleResourceManager::setCFG
void setCFG(const ControlFlowGraph *cfg)
Definition: SimpleResourceManager.cc:634
GraphNode::nodeID
int nodeID() const
DataDependenceGraph.hh
BasicBlockPass::ddgBuilder
virtual DataDependenceGraphBuilder & ddgBuilder()
Definition: BasicBlockPass.hh:86
Application::verboseLevel
static int verboseLevel()
Definition: Application.hh:176
BUBasicBlockScheduler
Definition: BUBasicBlockScheduler.hh:61
Application::logStream
static std::ostream & logStream()
Definition: Application.cc:155
BasicBlockNode::isScheduled
bool isScheduled() const
Definition: BasicBlockNode.hh:93
BasicBlockPass::executeLoopPass
virtual bool executeLoopPass(TTAProgram::BasicBlock &bb, const TTAMachine::Machine &targetMachine, TTAProgram::InstructionReferenceManager &irm, std::vector< DDGPass * > ddgPasses, BasicBlockNode *bbn=NULL)
Definition: BasicBlockPass.cc:152
CopyingDelaySlotFiller::initialize
void initialize(ControlFlowGraph &cfg, DataDependenceGraph &ddg, const TTAMachine::Machine &machine)
Definition: CopyingDelaySlotFiller.cc:1937
ControlFlowGraph::instructionReferenceManager
TTAProgram::InstructionReferenceManager & instructionReferenceManager()
Definition: ControlFlowGraph.cc:2401
LiveRangeData::regDefReaches_
MoveNodeUseMapSet regDefReaches_
Definition: LiveRangeData.hh:90
BasicBlockScheduler.hh
LoopAnalyzer::analyze
static LoopAnalysisResult * analyze(BasicBlockNode &bbn, DataDependenceGraph &ddg)
Definition: LoopAnalyzer.cc:14
LLVMTCECmdLineOptions::dumpDDGsDot
virtual bool dumpDDGsDot() const
Definition: LLVMTCECmdLineOptions.cc:359
SchedulerCmdLineOptions
Definition: SchedulerCmdLineOptions.hh:45
Conversion::toString
static std::string toString(const T &source)
MAXIMUM_II
static const int MAXIMUM_II
Definition: BBSchedulerController.cc:82
LLVMTCECmdLineOptions::useBUScheduler
bool useBUScheduler() const
Definition: LLVMTCECmdLineOptions.cc:374
SchedulerCmdLineOptions.hh
ScheduleEstimator.hh
SimpleResourceManager::clearOldResources
virtual void clearOldResources()
Definition: SimpleResourceManager.cc:610
TCEString.hh
BBSchedulerController::longDescription
virtual std::string longDescription() const override
Definition: BBSchedulerController.cc:439
BBSchedulerController::handleBBNode
bool handleBBNode(ControlFlowGraph &cfg, BasicBlockNode &bbn, const TTAMachine::Machine &targetMachine, int nodeCount)
Definition: BBSchedulerController.cc:575
BasicBlockNode::basicBlock
TTAProgram::BasicBlock & basicBlock()
Definition: BasicBlockNode.cc:126
BasicBlockPass
Definition: BasicBlockPass.hh:60
DEFAULT_LOWMEM_MODE_THRESHOLD
static const int DEFAULT_LOWMEM_MODE_THRESHOLD
Definition: BBSchedulerController.cc:83
DataDependenceGraph::createSubgraph
DataDependenceGraph * createSubgraph(NodeSet &nodes, bool includeLoops=false)
Definition: DataDependenceGraph.cc:3377
DataDependenceGraphBuilder.hh
DataDependenceGraph::writeToXMLFile
void writeToXMLFile(std::string fileName) const
Definition: DataDependenceGraph.cc:1747
BasicBlockNode::updateHWloopLength
void updateHWloopLength(unsigned len)
Definition: BasicBlockNode.cc:308
SchedulerCmdLineOptions::lowMemModeThreshold
virtual int lowMemModeThreshold() const
Definition: SchedulerCmdLineOptions.cc:310
LLVMTCECmdLineOptions::useBubbleFish2Scheduler
bool useBubbleFish2Scheduler() const
Definition: LLVMTCECmdLineOptions.cc:379
CopyingDelaySlotFiller::fillDelaySlots
void fillDelaySlots(ControlFlowGraph &cfg, DataDependenceGraph &ddg, const TTAMachine::Machine &machine)
Definition: CopyingDelaySlotFiller.cc:405
abortWithError
#define abortWithError(message)
Definition: Application.hh:72
TTAProgram::BasicBlock::setTripCount
void setTripCount(unsigned count)
Definition: BasicBlock.hh:109
BF2Scheduler.hh
DataDependenceGraph::largestCycle
int largestCycle() const
Definition: DataDependenceGraph.cc:1838
BoostGraph::rootGraph
BoostGraph * rootGraph()
LoopAnalyzer::LoopAnalysisResult::counterValueNode
MoveNode * counterValueNode
Definition: LoopAnalyzer.hh:16
BBSchedulerController::~BBSchedulerController
virtual ~BBSchedulerController()
Definition: BBSchedulerController.cc:109
Instruction.hh
TTAProgram::BasicBlock::liveRangeData_
LiveRangeData * liveRangeData_
Definition: BasicBlock.hh:111
TTAProgram::CodeSnippet::instructionCount
virtual int instructionCount() const
Definition: CodeSnippet.cc:205
ControlFlowGraph.hh
UniversalMachine
Definition: UniversalMachine.hh:56
DataDependenceGraph::INTRA_BB_ANTIDEPS
@ INTRA_BB_ANTIDEPS
Definition: DataDependenceGraph.hh:80
BUBasicBlockScheduler.hh
LLVMTCECmdLineOptions.hh
BBSchedulerController::delaySlotFiller_
CopyingDelaySlotFiller * delaySlotFiller_
Definition: BBSchedulerController.hh:127
CmdLineOptions
Definition: CmdLineOptions.hh:54
Application.hh
Application::cmdLineOptions
static CmdLineOptions * cmdLineOptions()
Definition: Application.cc:397
BBSchedulerController::cfg_
ControlFlowGraph * cfg_
Control flow graph of the procedure.
Definition: BBSchedulerController.hh:120
LiveRangeData::regFirstDefines_
MoveNodeUseMapSet regFirstDefines_
Definition: LiveRangeData.hh:87
LoopPrologAndEpilogBuilder.hh
BBSchedulerController::progressBar_
boost::progress_display * progressBar_
Fancy progress bar. Pointer because creation outputs the initial progress bar and we want it only on ...
Definition: BBSchedulerController.hh:135
BasicBlockScheduler
Definition: BasicBlockScheduler.hh:66
CopyingDelaySlotFiller
Definition: CopyingDelaySlotFiller.hh:71
CopyingDelaySlotFiller::finalizeProcedure
void finalizeProcedure()
Definition: CopyingDelaySlotFiller.cc:460
BasicBlockNode
Definition: BasicBlockNode.hh:64
LiveRangeData::regLastUses_
MoveNodeUseMapSet regLastUses_
Definition: LiveRangeData.hh:79
BBSchedulerController::executeDDGPass
virtual void executeDDGPass(TTAProgram::BasicBlock &bb, const TTAMachine::Machine &targetMachine, TTAProgram::InstructionReferenceManager &irm, std::vector< DDGPass * > ddgPasses, BasicBlockNode *bbn=NULL) override
Definition: BBSchedulerController.cc:472
BasicBlockNode::isNormalBB
bool isNormalBB() const
Definition: BasicBlockNode.cc:239
BasicBlockNode::isHWLoop
bool isHWLoop() const
Definition: BasicBlockNode.hh:114
BF2Scheduler
Definition: BF2Scheduler.hh:74
TTAProgram::CodeSnippet::lastInstruction
virtual Instruction & lastInstruction() const
Definition: CodeSnippet.cc:387
LoopAnalyzer::LoopAnalysisResult::iterationCount
long iterationCount
Definition: LoopAnalyzer.hh:17
InterPassData
Definition: InterPassData.hh:48
Exception::errorMessageStack
std::string errorMessageStack(bool messagesOnly=false) const
Definition: Exception.cc:138
DataDependenceGraph::smallestCycle
int smallestCycle() const
Definition: DataDependenceGraph.cc:1818
SimpleResourceManager::disposeRM
static void disposeRM(SimpleResourceManager *rm, bool allowReuse=true)
Definition: SimpleResourceManager.cc:92
ResourceConstraintAnalyzer.hh
TTAProgram::Procedure::clear
void clear()
Definition: Procedure.cc:345
ControlFlowGraph::jumpSuccessor
BasicBlockNode * jumpSuccessor(BasicBlockNode &bbn)
Definition: ControlFlowGraph.cc:2411
Machine.hh
Exception
Definition: Exception.hh:54
ControlFlowGraph::isSingleBBLoop
bool isSingleBBLoop(const BasicBlockNode &node) const
Definition: ControlFlowGraph.cc:2919
ControlFlowGraph::allScheduledInBetween
bool allScheduledInBetween(const BasicBlockNode &src, const BasicBlockNode &dst) const
Definition: ControlFlowGraph.cc:3178
InterPassData::hasDatum
bool hasDatum(const std::string &key) const
Definition: InterPassData.cc:75
LLVMTCECmdLineOptions
Definition: LLVMTCECmdLineOptions.hh:48
LLVMTCECmdLineOptions::dumpDDGsXML
virtual bool dumpDDGsXML() const
Definition: LLVMTCECmdLineOptions.cc:364
BasicBlockPass::copyRMToBB
static void copyRMToBB(SimpleResourceManager &rm, TTAProgram::BasicBlock &bb, const TTAMachine::Machine &targetMachine, TTAProgram::InstructionReferenceManager &irm, int lastCycle=-1)
Definition: BasicBlockPass.cc:213
BoostGraph::height
int height() const
SimpleResourceManager::createRM
static SimpleResourceManager * createRM(const TTAMachine::Machine &machine, unsigned int ii=0)
Definition: SimpleResourceManager.cc:73
GraphBase::writeToDotFile
virtual void writeToDotFile(const TCEString &fileName) const
MachineConnectivityCheck::tempRegisterFiles
static std::set< const TTAMachine::RegisterFile *, TTAMachine::MachinePart::Comparator > tempRegisterFiles(const TTAMachine::Machine &machine)
Definition: MachineConnectivityCheck.cc:1038
BBSchedulerController::shortDescription
virtual std::string shortDescription() const override
Definition: BBSchedulerController.cc:426
TTAProgram::Instruction::hasJump
bool hasJump() const
Definition: Instruction.cc:422
options
static MachInfoCmdLineOptions options
Definition: MachInfo.cc:46
LoopAnalyzer::LoopAnalysisResult
Definition: LoopAnalyzer.hh:13
BasicBlockNode::setScheduled
void setScheduled(bool state=true)
Definition: BasicBlockNode.hh:94
TTAProgram::BasicBlock
Definition: BasicBlock.hh:85
SchedulerPass::interPassData
InterPassData & interPassData()
Definition: SchedulerPass.cc:53
LiveRangeData::registersUsedAfter_
std::set< TCEString > registersUsedAfter_
Definition: LiveRangeData.hh:121
DisassemblyRegister.hh
TTAProgram::InstructionReferenceManager
Definition: InstructionReferenceManager.hh:82
BasicBlockNode::predecessor
const BasicBlockNode * predecessor() const
Definition: BasicBlockNode.hh:121
ResourceConstraintAnalyzer::analyzePreSchedule
void analyzePreSchedule()
Definition: ResourceConstraintAnalyzer.cc:50
Program.hh
ResourceConstraintAnalyzer::analyze
bool analyze()
Definition: ResourceConstraintAnalyzer.cc:62
TTAProgram::BasicBlock::tripCount
unsigned tripCount() const
in case the BB is inside a loop and trip count is known, returns it, otherwise returns 0
Definition: BasicBlock.hh:108
InterPassData.hh
BBSchedulerController::handleControlFlowGraph
virtual void handleControlFlowGraph(ControlFlowGraph &cfg, const TTAMachine::Machine &targetMachine) override
Definition: BBSchedulerController.cc:398
SimpleResourceManager::setDDG
void setDDG(const DataDependenceGraph *ddg)
Definition: SimpleResourceManager.cc:629
LLVMTCECmdLineOptions::useTDScheduler
bool useTDScheduler() const
Definition: LLVMTCECmdLineOptions.cc:384
BBSchedulerController::BBSchedulerController
BBSchedulerController(const TTAMachine::Machine &targetMachine, InterPassData &data, SoftwareBypasser *bypasser=NULL, CopyingDelaySlotFiller *delaySlotFiller=NULL, DataDependenceGraph *bigDDG=NULL)
Definition: BBSchedulerController.cc:92
TCEString
Definition: TCEString.hh:53
BasicBlock.hh
ControlFlowGraphPass.hh
ControlUnit.hh
DataDependenceGraph
Definition: DataDependenceGraph.hh:67
SoftwareBypasser
Definition: SoftwareBypasser.hh:52
DataDependenceGraphBuilder::build
virtual DataDependenceGraph * build(ControlFlowGraph &cGraph, DataDependenceGraph::AntidependenceLevel antidependenceLevel, const TTAMachine::Machine &mach, const UniversalMachine *um=NULL, bool createMemAndFUDeps=true, bool createDeathInformation=true, llvm::AliasAnalysis *AA=NULL)
Definition: DataDependenceGraphBuilder.cc:2120
BBSchedulerController::totalBasicBlocks_
int totalBasicBlocks_
Total basic blocks in the CFG currently being scheduled.
Definition: BBSchedulerController.hh:132
BBSchedulerController::createDDGFromBB
virtual DataDependenceGraph * createDDGFromBB(TTAProgram::BasicBlock &bb, const TTAMachine::Machine &mach)
Definition: BBSchedulerController.cc:455
SimpleResourceManager::setBBN
void setBBN(const BasicBlockNode *bbn)
Definition: SimpleResourceManager.cc:639
TTAProgram::Procedure::name
TCEString name() const
Definition: Procedure.hh:66
BBSchedulerController::softwareBypasser_
SoftwareBypasser * softwareBypasser_
The software bypasser to use to bypass registers when possible.
Definition: BBSchedulerController.hh:125
SchedulerCmdLineOptions::printResourceConstraints
bool printResourceConstraints() const
Definition: SchedulerCmdLineOptions.cc:271
ControlFlowGraph::procedureName
TCEString procedureName() const
Definition: ControlFlowGraph.cc:1150
SimpleResourceManager.hh
SimpleResourceManager
Definition: SimpleResourceManager.hh:58
BBSchedulerController.hh
LoopAnalyzer::LoopAnalysisResult::counterMultiplier
int counterMultiplier
Definition: LoopAnalyzer.hh:18
ControlFlowGraphPass
Definition: ControlFlowGraphPass.hh:50
BasicBlockPass::ddgSnapshot
void ddgSnapshot(DataDependenceGraph *ddg, std::string &name, DataDependenceGraph::DumpFileFormat format, bool final)
Definition: BasicBlockPass.cc:172
program
find Finds info of the inner loops in the program
Definition: InnerLoopFinder.cc:80
TTAProgram::BasicBlock::isInInnerLoop
bool isInInnerLoop() const
returns true in case the BB is known to be inside an inner loop
Definition: BasicBlock.hh:103
BBSchedulerController::scheduledProcedure_
TTAProgram::Procedure * scheduledProcedure_
The currently scheduled procedure.
Definition: BBSchedulerController.hh:117
BBSchedulerController::basicBlocksScheduled_
int basicBlocksScheduled_
Number of basic blocks scheduled so far.
Definition: BBSchedulerController.hh:130
TTAMachine
Definition: Assembler.hh:48
LoopAnalyzer.hh
BoostGraph::name
virtual const TCEString & name() const
ScheduleEstimator
Definition: ScheduleEstimator.hh:46
debugLog
#define debugLog(text)
Definition: Application.hh:95
BBSchedulerController::handleProcedure
virtual void handleProcedure(TTAProgram::Procedure &procedure, const TTAMachine::Machine &targetMachine) override
Definition: BBSchedulerController.cc:284
BoostGraph::nodeCount
int nodeCount() const
BBSchedulerController::handleBasicBlock
virtual void handleBasicBlock(TTAProgram::BasicBlock &bb, const TTAMachine::Machine &targetMachine, TTAProgram::InstructionReferenceManager &irm, BasicBlockNode *bbn=NULL) override
Definition: BBSchedulerController.cc:123
TTAProgram::Procedure
Definition: Procedure.hh:55
ScheduleEstimator::handleControlFlowGraph
virtual void handleControlFlowGraph(ControlFlowGraph &cfg, const TTAMachine::Machine &mach) override
Definition: ScheduleEstimator.cc:85
RegisterRenamer
Definition: RegisterRenamer.hh:59
SoftwareBypasser.hh
RegisterRenamer.hh
ProgramPass::executeProcedurePass
static void executeProcedurePass(TTAProgram::Program &program, const TTAMachine::Machine &targetMachine, ProcedurePass &procedurePass)
Definition: ProgramPass.cc:72
LiveRangeData::regFirstUses_
MoveNodeUseMapSet regFirstUses_
Definition: LiveRangeData.hh:86
BasicBlockNode::toString
std::string toString() const
Definition: BasicBlockNode.cc:185
ControlFlowGraph
Definition: ControlFlowGraph.hh:100
TTAMachine::Machine
Definition: Machine.hh:73