OpenASIP  2.0
BasicBlockPass.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 BasicBlockPass.cc
26  *
27  * Definition of BasicBlockPass class.
28  *
29  * @author Pekka Jääskeläinen 2007 (pjaaskel-no.spam-cs.tut.fi)
30  * @note rating: red
31  */
32 
33 #include "BasicBlockPass.hh"
34 #include "Application.hh"
35 #include "BasicBlock.hh"
36 #include "Machine.hh"
38 #include "SimpleResourceManager.hh"
39 #include "ControlUnit.hh"
40 #include "DDGPass.hh"
41 #include "POMDisassembler.hh"
43 #include "BasicBlockScheduler.hh"
44 #include "Instruction.hh"
45 #include "FunctionUnit.hh"
46 #include "UniversalMachine.hh"
47 
48 /**
49  * Constructor.
50  */
52  SchedulerPass(data), ddgBuilder_(data) {
53 }
54 
55 /**
56  * Destructor.
57  */
59 }
60 
61 /**
62  * Handles a single basic block.
63  *
64  * Modifies the given basic block, so if the old one is to be preserved,
65  * client should copy the original. Does not restore the BB even though
66  * handling was not successful.
67  *
68  * @todo: Why both BB and BBN as arguments? If BBN is needed then I think
69  * BB argument can be replaced with a BBN one. We always should have it
70  * anyways.
71  *
72  * @param basicBlock The basic block to handle.
73  * @param machine The target machine if any. (NullMachine::instance() if
74  * target machine is irrelevant).
75  * @exception In case handling is unsuccesful for any reason (basicBlock
76  * might still get modified).
77  */
78 void
80  TTAProgram::BasicBlock& basicBlock,
81  const TTAMachine::Machine& targetMachine,
83  if (basicBlock.instructionCount() == 0)
84  return;
85 
86  DDGPass* ddgPass = dynamic_cast<DDGPass*>(this);
87  std::vector<DDGPass*> ddgPasses;
88  ddgPasses.push_back(ddgPass);
89  if (ddgPass != NULL) {
90  executeDDGPass(basicBlock, targetMachine, irm, ddgPasses, bbn);
91  } else {
92  abortWithError("basic block pass is not also a ddg pass so you "
93  "must overload handleBasicBlock method!");
94  }
95 }
96 
97 /**
98  * Creates a DDG from the given basic block and executes a DDG pass for that.
99  */
100 void
102  TTAProgram::BasicBlock& bb, const TTAMachine::Machine& targetMachine,
104  std::vector<DDGPass*> ddgPasses, BasicBlockNode*) {
105  std::cerr << "Calling bbpass::executedgpass." << std::endl;
106 
107  DataDependenceGraph* ddg = createDDGFromBB(bb, targetMachine);
108 
109  // Used for live info dumping.
110  static int bbNumber = 0;
111 
112 #ifdef DDG_SNAPSHOTS
113  std::string name = "scheduling";
114  ddgSnapshot(ddg, name, false);
115 #endif
116 
118  ddgPasses[0]->handleDDG(*ddg, *rm, targetMachine);
119 
120 #ifdef DDG_SNAPSHOTS
121  std::string name = "scheduling";
122  ddgSnapshot(ddg, name, true);
123 #endif
124 
125  copyRMToBB(*rm, bb, targetMachine, irm);
126 
127  // Print the live range count for each cycle for the sched_yield emitting
128  // paper.
129  if (Application::verboseLevel() > 1 ||
130  getenv("TCE_DUMP_LIVE_INFO") != NULL) {
131  for (int index = 0; index < bb.instructionCount(); ++index) {
132  if (bb.liveRangeData_ != NULL) {
134  << "liveinfo:" << bbNumber << ":" << index + rm->smallestCycle() << ":"
136  rm->smallestCycle()+index, targetMachine.controlUnit()->delaySlots(), *ddg).
137  size()
138  << std::endl;
139  }
140  }
141  bbNumber++;
142  }
143 
144  delete ddg;
146 }
147 
148 /**
149  * Creates a DDG from the given basic block and executes a Loop pass for that.
150  */
151 bool
154  TTAProgram::InstructionReferenceManager&, std::vector<DDGPass*>,
155  BasicBlockNode*) {
156  // not implemented
157  assert(0 && "should not be here?");
158  return false;
159 }
160 
161 /**
162  * Prints DDG to a dot file before and after scheudling
163  *
164  * @param ddg to print
165  * @param name operation name for ddg
166  * @param final specify if ddg is after scheduling
167  * @param format format of the file
168  * @return number of cycles/instructions copied.
169  */
170 
171 void
173  DataDependenceGraph* ddg,
174  std::string& name,
176  bool final) {
177  static int bbCounter = 0;
178 
179  if (final) {
180  if (format == DataDependenceGraph::DUMP_DOT) {
181  ddg->writeToDotFile(
182  (boost::format("bb_%.4d_1_after_%2%.dot") % bbCounter % name).str());
183  } else {
184  ddg->writeToXMLFile(
185  (boost::format("bb_%.4d_1_after_%2%.xml") % bbCounter % name).str());
186  }
187  ++bbCounter;
188  } else {
189  if (format == DataDependenceGraph::DUMP_DOT) {
190  ddg->writeToDotFile(
191  (boost::format("bb_%.4d_0_before_%2%.dot") % bbCounter % name).str());
192  } else {
193  ddg->writeToXMLFile(
194  (boost::format("bb_%.4d_0_before_%2%.xml") % bbCounter % name).str());
195  }
196  Application::logStream() << "\nBB " << bbCounter << std::endl;
197  }
198 }
199 
200 /**
201  * Copies moves back from resourcemanager to basicblock,
202  * putting them to correct instructions based in their cycle,
203  * and adding the final delay slots.
204  *
205  * @param rm the resourcemanager
206  * @param bb the basicblock
207  * @param targetMachine machine we are scheduling for.
208  * @param irm IRM to keep book of the instruction references.
209  * @param lastCycle the last instruction cycle of BB to copy.
210  * @return number of cycles/instructions copied.
211  */
212 void
215  const TTAMachine::Machine& targetMachine,
216  TTAProgram::InstructionReferenceManager& irm, int lastCycle) {
217 
218  // find the largest cycle any of a pipelines is still used
219  if (lastCycle == -1) {
220  const int rmLastCycle = rm.largestCycle();
221  lastCycle = rmLastCycle;
222  }
223 
224  // only first ins of bb may have incoming references
225  for (int i = 1; i < bb.instructionCount(); i++) {
226  if (irm.hasReference(bb.instructionAtIndex(i))) {
227  std::cerr << "non-first has ref:, index: " << i <<
228  " bb size: " << bb.instructionCount() << std::endl;
229  }
230  assert (!irm.hasReference(bb.instructionAtIndex(i)));
231  }
232 
233  TTAProgram::Instruction refHolder;
234  if (bb.instructionCount() && irm.hasReference(bb.instructionAtIndex(0))) {
235  irm.replace(bb.instructionAtIndex(0), refHolder);
236  }
237 
238  int moveCount = 0;
239 
240  // update the BB with the new instructions
241  bb.clear();
242 
243  int index = rm.smallestCycle();
244  if (rm.initiationInterval() > 0 && rm.initiationInterval() != INT_MAX) {
245  lastCycle = rm.initiationInterval() -1;
246  index = 0;
247  }
248 
249  for (; index <= lastCycle; ++index) {
250  TTAProgram::Instruction* newInstruction = rm.instruction(index);
251  if (newInstruction->hasControlFlowMove()) {
252  // Add delay slots of the last control flow instruction
253  // to loop end count. There can be multiple control
254  // flow instructions in a basic block in case thread yield
255  // emitter is enabled and it has inserted one or more
256  // calls to thread_yield().
257 
258  // only this this when not modulo-scheduling.
259  if (rm.initiationInterval() < 1 ||
260  rm.initiationInterval() == INT_MAX) {
261  lastCycle =
262  std::max(
263  lastCycle,
264  index + targetMachine.controlUnit()->delaySlots());
265 // assert(lastCycle >= rmLastCycle);
266  }
267  }
268 
269  moveCount += newInstruction->moveCount();
270  bb.add(newInstruction);
271 #if 0
273  << newInstruction->instructionTemplate().name() << ": "
274  << newInstruction->toString() << std::endl;
275 #endif
276  rm.loseInstructionOwnership(index);
277  }
278 
279  if (irm.hasReference(refHolder)) {
280  irm.replace(refHolder, bb.firstInstruction());
281  }
282 
283  const int instructionCount = lastCycle + 1 - rm.smallestCycle();
284  if (Application::verboseLevel() > 1 && bb.isInInnerLoop()) {
285  const int busCount = targetMachine.busNavigator().count();
286  const int moveSlotCount = busCount * instructionCount;
288  << "BB -- inner loop with trip count: " << bb.tripCount()
289  << std::endl
290  << "BB -- instruction count: " << instructionCount << std::endl;
292  << "BB -- move slots used: " << moveCount << " of "
293  << moveSlotCount << " (" << (float)moveCount * 100 / moveSlotCount
294  << "%)" << std::endl;
295  }
296 
297  return;
298 }
299 
300 
303  TTAProgram::BasicBlock& bb, const TTAMachine::Machine& mach) {
304  return ddgBuilder().build(
305  bb, DataDependenceGraph::INTRA_BB_ANTIDEPS, mach, "unknown_bb");
306 }
SchedulerPass
Definition: SchedulerPass.hh:43
TTAProgram::CodeSnippet::firstInstruction
virtual Instruction & firstInstruction() const
Definition: CodeSnippet.cc:216
TTAMachine::Component::name
virtual TCEString name() const
Definition: MachinePart.cc:125
SimpleResourceManager::largestCycle
virtual int largestCycle() const override
Definition: SimpleResourceManager.cc:463
TTAProgram::Instruction
Definition: Instruction.hh:57
SimpleResourceManager::smallestCycle
virtual int smallestCycle() const override
Definition: SimpleResourceManager.cc:480
TTAProgram::Instruction::toString
std::string toString() const
Definition: Instruction.cc:576
BasicBlockPass::ddgBuilder
virtual DataDependenceGraphBuilder & ddgBuilder()
Definition: BasicBlockPass.hh:86
Application::verboseLevel
static int verboseLevel()
Definition: Application.hh:176
Application::logStream
static std::ostream & logStream()
Definition: Application.cc:155
TTAMachine::Machine::Navigator::count
int count() const
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
SimpleResourceManager::initiationInterval
virtual unsigned initiationInterval() const
Definition: SimpleResourceManager.hh:135
BasicBlockScheduler.hh
POMDisassembler.hh
LiveRangeData::registersAlive
std::set< TCEString > registersAlive(int cycle, int delaySlots, class DataDependenceGraph &ddg)
Definition: LiveRangeData.cc:127
BasicBlockPass::~BasicBlockPass
virtual ~BasicBlockPass()
Definition: BasicBlockPass.cc:58
assert
#define assert(condition)
Definition: Application.hh:86
UniversalMachine.hh
DataDependenceGraphBuilder.hh
DataDependenceGraph::writeToXMLFile
void writeToXMLFile(std::string fileName) const
Definition: DataDependenceGraph.cc:1747
TTAMachine::Machine::controlUnit
virtual ControlUnit * controlUnit() const
Definition: Machine.cc:345
abortWithError
#define abortWithError(message)
Definition: Application.hh:72
Instruction.hh
TTAProgram::BasicBlock::liveRangeData_
LiveRangeData * liveRangeData_
Definition: BasicBlock.hh:111
TTAProgram::CodeSnippet::instructionCount
virtual int instructionCount() const
Definition: CodeSnippet.cc:205
BasicBlockPass::handleBasicBlock
virtual void handleBasicBlock(TTAProgram::BasicBlock &basicBlock, const TTAMachine::Machine &targetMachine, TTAProgram::InstructionReferenceManager &irm, BasicBlockNode *bbn=NULL)
Definition: BasicBlockPass.cc:79
BasicBlockPass::executeDDGPass
virtual void executeDDGPass(TTAProgram::BasicBlock &bb, const TTAMachine::Machine &targetMachine, TTAProgram::InstructionReferenceManager &irm, std::vector< DDGPass * > ddgPasses, BasicBlockNode *bbn=NULL)
Definition: BasicBlockPass.cc:101
TTAProgram::CodeSnippet::add
virtual void add(Instruction *ins)
Definition: CodeSnippet.cc:432
DataDependenceGraph::INTRA_BB_ANTIDEPS
@ INTRA_BB_ANTIDEPS
Definition: DataDependenceGraph.hh:80
TTAProgram::InstructionReferenceManager::hasReference
bool hasReference(Instruction &ins) const
Definition: InstructionReferenceManager.cc:143
BasicBlockPass.hh
TTAProgram::InstructionReferenceManager::replace
void replace(Instruction &insA, Instruction &insB)
Definition: InstructionReferenceManager.cc:96
Application.hh
BasicBlockNode
Definition: BasicBlockNode.hh:64
InterPassData
Definition: InterPassData.hh:48
SimpleResourceManager::disposeRM
static void disposeRM(SimpleResourceManager *rm, bool allowReuse=true)
Definition: SimpleResourceManager.cc:92
BasicBlockPass::BasicBlockPass
BasicBlockPass(InterPassData &data)
Definition: BasicBlockPass.cc:51
DataDependenceGraph::DUMP_DOT
@ DUMP_DOT
Definition: DataDependenceGraph.hh:86
TTAMachine::ControlUnit::delaySlots
int delaySlots() const
Machine.hh
BasicBlockPass::copyRMToBB
static void copyRMToBB(SimpleResourceManager &rm, TTAProgram::BasicBlock &bb, const TTAMachine::Machine &targetMachine, TTAProgram::InstructionReferenceManager &irm, int lastCycle=-1)
Definition: BasicBlockPass.cc:213
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
TTAProgram::Instruction::instructionTemplate
const TTAMachine::InstructionTemplate & instructionTemplate() const
Definition: Instruction.cc:523
TTAProgram::BasicBlock
Definition: BasicBlock.hh:85
DDGPass
Definition: DDGPass.hh:51
TTAProgram::InstructionReferenceManager
Definition: InstructionReferenceManager.hh:82
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
BasicBlock.hh
DDGPass.hh
ControlUnit.hh
DataDependenceGraph
Definition: DataDependenceGraph.hh:67
TTAMachine::Machine::busNavigator
virtual BusNavigator busNavigator() const
Definition: Machine.cc:356
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
InstructionReferenceManager.hh
SimpleResourceManager::loseInstructionOwnership
virtual void loseInstructionOwnership(int cycle)
Definition: SimpleResourceManager.cc:498
SimpleResourceManager.hh
TTAProgram::CodeSnippet::instructionAtIndex
virtual Instruction & instructionAtIndex(int index) const
Definition: CodeSnippet.cc:285
SimpleResourceManager
Definition: SimpleResourceManager.hh:58
TTAProgram::Instruction::hasControlFlowMove
bool hasControlFlowMove() const
Definition: Instruction.cc:471
BasicBlockPass::ddgSnapshot
void ddgSnapshot(DataDependenceGraph *ddg, std::string &name, DataDependenceGraph::DumpFileFormat format, bool final)
Definition: BasicBlockPass.cc:172
TTAProgram::BasicBlock::isInInnerLoop
bool isInInnerLoop() const
returns true in case the BB is known to be inside an inner loop
Definition: BasicBlock.hh:103
DataDependenceGraph::DumpFileFormat
DumpFileFormat
Definition: DataDependenceGraph.hh:85
TTAProgram::BasicBlock::clear
virtual void clear()
Definition: BasicBlock.cc:152
BasicBlockPass::createDDGFromBB
virtual DataDependenceGraph * createDDGFromBB(TTAProgram::BasicBlock &bb, const TTAMachine::Machine &mach)
Definition: BasicBlockPass.cc:302
TTAProgram::Instruction::moveCount
int moveCount() const
Definition: Instruction.cc:176
TTAMachine::Machine
Definition: Machine.hh:73
FunctionUnit.hh
SimpleResourceManager::instruction
virtual TTAProgram::Instruction * instruction(int cycle) const override
Definition: SimpleResourceManager.cc:442