OpenASIP  2.0
BasicBlockNode.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 BasicBlockNode.cc
26  *
27  * Prototype control flow graph of TTA program representation:
28  * implementation of graph node (basic block).
29  *
30  * @author Andrea Cilio 2005 (cilio-no.spam-cs.tut.fi)
31  * @author Vladimir Guzma 2006 (vladimir.guzma-no.spam-tut.fi)
32  * @note rating: red
33  */
34 
35 #include "BasicBlockNode.hh"
36 
37 #include <climits>
38 
39 #include "BasicBlock.hh"
40 #include "Conversion.hh"
41 #include "Exception.hh"
42 #include "Instruction.hh"
44 #include "Move.hh"
45 #include "POMDisassembler.hh"
46 #include "Program.hh"
47 #include "TCEString.hh"
48 #include "Terminal.hh"
49 #include "TerminalImmediate.hh"
50 /**
51  * Constructor.
52  *
53  * @param originalStartAddress The starting address of the basic block in
54  * the original program (address of the first instruction).
55  * @param originalEndAddress The ending address of the basic block in
56  * the original program (address of the last instruction).
57  * @param entry True if the basic block is a (pseudo) entry basic block.
58  * @param exit True if the basic block is a (pseudo) exit basic block.
59  */
61  InstructionAddress originalStartAddress,
62  InstructionAddress originalEndAddress,
63  bool entry,
64  bool exit) :
65  originalStartAddress_(originalStartAddress),
66  originalEndAddress_(originalEndAddress),
67  hasOriginalAddress_(true),
68  basicBlock_(new TTAProgram::BasicBlock(originalStartAddress)),
69  bbOwned_(true),
70  entry_(entry), exit_(exit),
71  scheduled_(false), refsUpdated_(false), loopScheduled_(false),
72  isHardwareLoop_(false),
73  successor_(NULL), predecessor_(NULL), maximumSize_(INT_MAX) {
74 
75  if (entry || exit) {
76  hasOriginalAddress_ = false;
77  } else {
79  throw InvalidData(
80  __FILE__, __LINE__, __func__,
81  "Basic block start address is higher then it's end address");
82  }
83  }
84 }
85 
86 /**
87  * Constructor.
88  *
89  * A wrapper for BasicBlock. When constructed with this one, the given bb
90  * will not be deleted in the destructor.
91  */
93  TTAProgram::BasicBlock& bb, bool scheduled, bool refsUpdated,
94  int originalStartAddress, bool loopScheduled) :
95  originalStartAddress_(originalStartAddress), originalEndAddress_(0),
96  hasOriginalAddress_(false), basicBlock_(&bb), bbOwned_(false),
97  entry_(false), exit_(false),
98  scheduled_(scheduled), refsUpdated_(refsUpdated),
99  loopScheduled_(loopScheduled),
100  isHardwareLoop_(false),
101  successor_(NULL), predecessor_(NULL), maximumSize_(INT_MAX) {
102 }
103 
104 /**
105  * Destructor.
106  */
108  if (bbOwned_)
109  delete basicBlock_;
110  basicBlock_ = NULL;
111 
112  if (successor_ != nullptr && successor_->predecessor_ == this) {
114  }
115  if (predecessor_ != nullptr && predecessor_->successor_ == this) {
117  }
118 }
119 
120 /**
121  * Returns the basic block object this node represents.
122  *
123  * @return The basic block object (can be modified).
124  */
127  return *basicBlock_;
128 }
129 
130 /**
131  * Returns the basic block object this node represents (const version).
132  *
133  * @return The basic block object (can be modified).
134  */
137  return *basicBlock_;
138 }
139 
140 /**
141  * Returns true if the original adress of this basic block is known.
142  *
143  * The basic block might not have original program address in case it's a
144  * pseudo basic block, or a completely new basic block which did not exist
145  * in the original program.
146  *
147  * @return True in case original address is known.
148  */
149 bool
151  return hasOriginalAddress_;
152 }
153 
154 /**
155  * The starting address of the basic block in the original program.
156  *
157  * Returned value is undefined in case hasOriginalAddress() returns false.
158  *
159  * @return The original starting address of the basic block.
160  */
163  return originalStartAddress_;
164 }
165 
166 /**
167  * The end address of the basic block in the original program.
168  *
169  * Returned value is undefined in case hasOriginalAddress() returns false.
170  *
171  * @return The original ending address of the basic block.
172  */
175  return originalEndAddress_;
176 }
177 
178 /**
179  * Returns the description of basic block as string.
180  *
181  * @note Used in writting graph to .dot file.
182  * @return The description of basic block
183  */
184 std::string
186 
187  if (isNormalBB()) {
188  TCEString content = "";
189  int iCount = basicBlock().instructionCount();
190  if (iCount > basicBlock().skippedFirstInstructions()) {
191  const TTAProgram::Instruction& first =
193  basicBlock().skippedFirstInstructions());
194  if (first.moveCount() > 0 &&
195  first.move(0).hasSourceLineNumber())
196  content << " srclines: " << first.move(0).sourceLineNumber();
197 
198  const TTAProgram::Instruction& last =
200  if (last.moveCount() > 0 &&
201  last.move(0).hasSourceLineNumber())
202  content << "-" << last.move(0).sourceLineNumber();
203 
204  content << "\\n0: ";
205  content << first.toString();
206 
207  // print at most last 4 instructions to (usually) print out the
208  for (int i = 3; i >= 0; --i) {
209  int loc = iCount - i - 1;
210  if (loc <= basicBlock().skippedFirstInstructions())
211  continue;
212  const TTAProgram::Instruction& instr =
214  if (i == 3)
215  content << "\\n...\\n";
216  content << "\\n";
217  content << loc << ": ";
218  content << instr.toString();
219  }
220  }
221  return content;
222  } else if (isEntryBB()) {
223  return "Entry";
224  } else if (isExitBB()) {
225  return "Exit";
226  }
227  return "";
228 }
229 
230 
231 
232 /**
233  * Returns true if object is ordinary basic block containing
234  * code snippet with instructions.
235  *
236  * @return True if the basic block is normal storage for instructions.
237  */
238 bool
240  return (!entry_) && (!exit_);
241 }
242 /**
243  * Returns true if the basic block is representing artificial Entry node.
244  *
245  * @return True if the basic block is artificially added Entry node.
246  */
247 bool
249  return entry_;
250 }
251 /**
252  * Return true if basic block is representing artificial Exit node.
253  *
254  * @return True if basic block is Exit node.
255  */
256 bool
258  return exit_;
259 }
260 
261 /**
262  * Updates and returns the statistics about Basic Block
263  *
264  * @return refrence to structure with information about basic block
265  */
268  if (isNormalBB()) {
269  return basicBlock_->statistics();
270  }
273  return *bbs;
274 }
275 
276 /**
277  * Finds jumps from a BasicBlockNode.
278  *
279  * @return second is last jump or NULL if no jumps, first NULL or first jump
280  * if the BB has two jumps
281  */
282 std::pair<TTAProgram::Move*,TTAProgram::Move*>
284  std::pair<TTAProgram::Move*, TTAProgram::Move*> moves(NULL,NULL);
285  for (int i = basicBlock_->instructionCount()-1; i >= 0; i--) {
287  for (int j = 0; j < ins.moveCount(); j++) {
288  TTAProgram::Move& move = ins.move(j);
289  if (move.isJump()) {
290  if (moves.second == NULL) {
291  moves.second = &move;
292  } else {
293  moves.first = &move;
294  return moves;
295  break;
296  }
297  }
298  }
299  }
300  return moves;
301 }
302 
303 /**
304  * Update hwloop instruction count.
305  *
306  */
307 void
309  for (int i = 0; i < basicBlock_->instructionCount(); i++) {
311  for (int j = 0; j < ins.moveCount(); j++) {
312  TTAProgram::Move& move = ins.move(j);
313  if (move.toString().find("hwloop") != std::string::npos &&
314  move.isTriggering()) {
315  // Only process hwloop instr-length setting
316  auto& s = move.source();
317  assert(s.isImmediate() && "hwloop instruction should be imm");
318  move.setSource(
320  }
321  }
322  }
323 }
324 
325 /**
326  * Updates instruction references to this BB from procedure to cfg
327  *
328  * @param prog program where instructions are.
329  */
330 void
332 
333  if (refsUpdated_) {
334  return;
335  }
338 
339  if (isNormalBB()) {
340  if (basicBlock_->instructionCount() > 0) {
342  TTAProgram::Instruction& oldIns = prog.instructionAt(
344  if (refManager.hasReference(oldIns)) {
345  refManager.replace(oldIns, newIns);
346  }
347  }
348  }
349  refsUpdated_ = true;
350 }
351 
353  // this is already the successor!
354  if (successor == successor_) {
355  assert(successor_->predecessor_ == this);
356  return;
357  }
358 
359  // link the new one between previous successor
360  if (successor_) {
361  auto oldSucc = successor_;
362  oldSucc->predecessor_ = successor;
363  successor->successor_ = oldSucc;
364  }
365 
366  if (successor != NULL) {
367  // make sure no inconsistent links.
368  if (successor->predecessor_ != NULL &&
371  }
372  successor->predecessor_ = this;
373  }
375 }
376 
377 /**
378  *
379  * Returns maximum size of a basic block.
380  * If scheduled, return the actual size.
381  *
382  * If not scheduled, return the size stored in max size field.
383  */
385  return scheduled_ ?
388  maximumSize_;
389 }
TTAProgram
Definition: Estimator.hh:65
TTAProgram::BasicBlock::statistics
const BasicBlockStatistics & statistics()
Definition: BasicBlock.cc:111
TTAProgram::Program
Definition: Program.hh:63
TTAProgram::Move::isTriggering
bool isTriggering() const
Definition: Move.cc:284
BasicBlockNode::isExitBB
bool isExitBB() const
Definition: BasicBlockNode.cc:257
InstructionAddress
UInt32 InstructionAddress
Definition: BaseType.hh:175
TTAProgram::CodeSnippet::firstInstruction
virtual Instruction & firstInstruction() const
Definition: CodeSnippet.cc:216
BasicBlockNode::predecessor_
BasicBlockNode * predecessor_
Definition: BasicBlockNode.hh:156
BasicBlockNode::hasOriginalAddress_
bool hasOriginalAddress_
not all basic blocks have original addresses (completely new basic blocks, etc.), this flag is true i...
Definition: BasicBlockNode.hh:138
TTAProgram::Instruction::move
Move & move(int i) const
Definition: Instruction.cc:193
BasicBlockNode::findJumps
std::pair< TTAProgram::Move *, TTAProgram::Move * > findJumps()
Definition: BasicBlockNode.cc:283
Exception.hh
BasicBlockNode::originalEndAddress
InstructionAddress originalEndAddress() const
Definition: BasicBlockNode.cc:174
BasicBlockNode::successor_
BasicBlockNode * successor_
Definition: BasicBlockNode.hh:155
TTAProgram::Instruction
Definition: Instruction.hh:57
TTAProgram::Move::sourceLineNumber
int sourceLineNumber() const
Definition: Move.cc:459
BasicBlockNode.hh
BasicBlockNode::link
void link(BasicBlockNode *succ)
Definition: BasicBlockNode.cc:352
TTAProgram::Instruction::toString
std::string toString() const
Definition: Instruction.cc:576
TTAProgram::Move::toString
std::string toString() const
Definition: Move.cc:436
BasicBlockNode::originalEndAddress_
InstructionAddress originalEndAddress_
end address of the original basic block, used for reconstructing the original program after modifying...
Definition: BasicBlockNode.hh:135
Terminal.hh
BasicBlockNode::originalStartAddress_
InstructionAddress originalStartAddress_
start address of the original basic block, used for reconstructing the original program after modifyi...
Definition: BasicBlockNode.hh:132
SimValue
Definition: SimValue.hh:96
BasicBlockNode::statistics
const TTAProgram::BasicBlockStatistics & statistics()
Definition: BasicBlockNode.cc:267
POMDisassembler.hh
TCEString.hh
BasicBlockNode::basicBlock
TTAProgram::BasicBlock & basicBlock()
Definition: BasicBlockNode.cc:126
assert
#define assert(condition)
Definition: Application.hh:86
TTAProgram::Program::instructionAt
Instruction & instructionAt(InstructionAddress address) const
Definition: Program.cc:374
TTAProgram::BasicBlockStatistics
Definition: BasicBlock.hh:55
BasicBlockNode::updateHWloopLength
void updateHWloopLength(unsigned len)
Definition: BasicBlockNode.cc:308
BasicBlockNode::maximumSize
int maximumSize() const
Definition: BasicBlockNode.cc:384
TTAProgram::BasicBlock::skippedFirstInstructions
int skippedFirstInstructions() const
Definition: BasicBlock.cc:88
InvalidData
Definition: Exception.hh:149
Instruction.hh
TTAProgram::CodeSnippet::instructionCount
virtual int instructionCount() const
Definition: CodeSnippet.cc:205
BasicBlockNode::successor
const BasicBlockNode * successor() const
Definition: BasicBlockNode.hh:120
Conversion.hh
TTAProgram::InstructionReferenceManager::hasReference
bool hasReference(Instruction &ins) const
Definition: InstructionReferenceManager.cc:143
TTAProgram::InstructionReferenceManager::replace
void replace(Instruction &insA, Instruction &insB)
Definition: InstructionReferenceManager.cc:96
__func__
#define __func__
Definition: Application.hh:67
BasicBlockNode::updateReferencesFromProcToCfg
void updateReferencesFromProcToCfg(TTAProgram::Program &prog)
Definition: BasicBlockNode.cc:331
BasicBlockNode
Definition: BasicBlockNode.hh:64
BasicBlockNode::isEntryBB
bool isEntryBB() const
Definition: BasicBlockNode.cc:248
BasicBlockNode::~BasicBlockNode
virtual ~BasicBlockNode()
Definition: BasicBlockNode.cc:107
BasicBlockNode::isNormalBB
bool isNormalBB() const
Definition: BasicBlockNode.cc:239
TTAProgram::CodeSnippet::lastInstruction
virtual Instruction & lastInstruction() const
Definition: CodeSnippet.cc:387
BasicBlockNode::refsUpdated_
bool refsUpdated_
Definition: BasicBlockNode.hh:149
TTAProgram::Move
Definition: Move.hh:55
BasicBlockNode::BasicBlockNode
BasicBlockNode(InstructionAddress originalStartAddress, InstructionAddress originalEndAddress, bool entry=false, bool exit=false)
Definition: BasicBlockNode.cc:60
BasicBlockNode::bbOwned_
bool bbOwned_
true if the BasicBlock is owned by the BasicBlockNode
Definition: BasicBlockNode.hh:142
BasicBlockNode::basicBlock_
TTAProgram::BasicBlock * basicBlock_
the actual payload data of the graph node (the basic block)
Definition: BasicBlockNode.hh:140
TTAProgram::TerminalImmediate
Definition: TerminalImmediate.hh:44
BasicBlockNode::scheduled_
bool scheduled_
Definition: BasicBlockNode.hh:148
TTAProgram::BasicBlock
Definition: BasicBlock.hh:85
BasicBlockNode::exit_
bool exit_
true if this is an exit basic block (not real one)
Definition: BasicBlockNode.hh:146
TTAProgram::Move::hasSourceLineNumber
bool hasSourceLineNumber() const
Definition: Move.cc:445
TTAProgram::InstructionReferenceManager
Definition: InstructionReferenceManager.hh:82
TTAProgram::Program::instructionReferenceManager
InstructionReferenceManager & instructionReferenceManager() const
Definition: Program.cc:688
Program.hh
TerminalImmediate.hh
false
find Finds info of the inner loops in the false
Definition: InnerLoopFinder.cc:81
TCEString
Definition: TCEString.hh:53
BasicBlock.hh
BasicBlockNode::hasOriginalAddress
bool hasOriginalAddress() const
Definition: BasicBlockNode.cc:150
InstructionReferenceManager.hh
TTAProgram::CodeSnippet::instructionAtIndex
virtual Instruction & instructionAtIndex(int index) const
Definition: CodeSnippet.cc:285
TTAProgram::Move::source
Terminal & source() const
Definition: Move.cc:302
TTAProgram::Move::isJump
bool isJump() const
Definition: Move.cc:164
Move.hh
BasicBlockNode::maximumSize_
int maximumSize_
Maximum number of instructions this can consume when scheduled.
Definition: BasicBlockNode.hh:159
BasicBlockNode::entry_
bool entry_
true if this is an entry basic block (not real one)
Definition: BasicBlockNode.hh:144
BasicBlockNode::originalStartAddress
InstructionAddress originalStartAddress() const
Definition: BasicBlockNode.cc:162
TTAProgram::Instruction::moveCount
int moveCount() const
Definition: Instruction.cc:176
BasicBlockNode::toString
std::string toString() const
Definition: BasicBlockNode.cc:185
TTAProgram::Move::setSource
void setSource(Terminal *src)
Definition: Move.cc:312