OpenASIP 2.2
Loading...
Searching...
No Matches
InstructionBitVector.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 InstructionBitVector.cc
26 *
27 * Implementation of InstructionBitVector class.
28 *
29 * @author Lasse Laasonen 2005 (lasse.laasonen-no.spam-tut.fi)
30 * @note rating: red
31 */
32
33#include <string>
34
36#include "MapTools.hh"
37#include "MathTools.hh"
38#include "Application.hh"
39
40using std::string;
42
43/**
44 * The constructor.
45 */
47 BitVector(), currentTable_(NULL) {
48}
49
50
51/**
52 * The copy constructor.
53 *
54 * @param toCopy Bit vector to copy.
55 */
57 const InstructionBitVector& toCopy) :
58 BitVector(toCopy), currentTable_(NULL),
59 instructionBoundaries_(toCopy.instructionBoundaries_),
60 instructionAddresses_(toCopy.instructionAddresses_) {
61
62 // copy reference map
63 for (ReferenceMap::const_iterator iter = toCopy.references_.begin();
64 iter != toCopy.references_.end(); iter++) {
65 const Instruction* instruction = (*iter).first;
66 IndexBoundSet* indexBounds = (*iter).second;
67 IndexBoundSet* newSet = new IndexBoundSet;
68 for (IndexBoundSet::const_iterator iter = indexBounds->begin();
69 iter != indexBounds->end(); iter++) {
70 IndexBoundTable* table = *iter;
71 IndexBoundTable* newTable = new IndexBoundTable(*table);
72 newSet->insert(newTable);
73 if (toCopy.currentTable_ == table) {
74 currentTable_ = newTable;
75 }
76 }
77 references_.insert(
78 std::pair<const Instruction*, IndexBoundSet*>(
79 instruction, newSet));
80 }
81}
82
83
84/**
85 * The destructor.
86 */
89
90
91/**
92 * Concatenates the given instruction bit vector to this vector.
93 *
94 * Fixes the instruction references of the given bit vector with the known
95 * instruction addresses.
96 *
97 * @param bits The bit vector to be concatenated to this vector.
98 * @exception OutOfRange If some of the instruction references cannot be
99 * fixed due to insufficient bit width.
100 */
101void
103 for (ReferenceMap::const_iterator iter = bits.references_.begin();
104 iter != bits.references_.end(); iter++) {
105 const Instruction* instruction = (*iter).first;
106 IndexBoundSet* indexBoundSet = (*iter).second;
107 if (!MapTools::containsKey(references_, instruction)) {
108 IndexBoundSet* newSet = new IndexBoundSet;
109 addIndexBoundTables(*indexBoundSet, *newSet);
110 references_.insert(
111 std::pair<const Instruction*, IndexBoundSet*>(
112 instruction, newSet));
113 } else {
115 references_, instruction);
116 addIndexBoundTables(*indexBoundSet, *oldSet);
117 }
118 }
119
120 InstructionBitVector bitsCopy(bits);
121
122 // fix the instruction references of the given bit vector
123 for (ReferenceMap::const_iterator iter = bits.references_.begin();
124 iter != bits.references_.end(); iter++) {
125 const Instruction* instruction = iter->first;
126 IndexBoundSet* indexBoundSet = iter->second;
128 for (IndexBoundSet::const_iterator setIter =
129 indexBoundSet->begin();
130 setIter != indexBoundSet->end(); setIter++) {
131 IndexBoundTable* table = *setIter;
132 bitsCopy.fixBits(
133 *table,
135 instructionAddresses_, instruction));
136 }
137 }
138 }
139
140 insert(end(), bitsCopy.begin(), bitsCopy.end());
141}
142
143/**
144 * Concatenates the given bit vector to this vector.
145 *
146 * @param bits The bit vector to be concatenated to this vector.
147 */
148void
152
153
154/**
155 * Starts setting an instruction reference.
156 *
157 * @param instruction The instruction being referenced.
158 */
159void
161 const TTAProgram::Instruction& instruction) {
162
163 IndexBoundSet& setForInstruction = indexBounds(instruction);
164 IndexBoundTable* newTable = new IndexBoundTable;
165 currentTable_ = newTable;
166 setForInstruction.insert(newTable);
167}
168
169
170/**
171 * Adds a pair of indexes that bound a part of the bit vector that refer
172 * to address of another instruction (given in
173 * startSettingInstructionReference).
174 *
175 * @param start The start index (included in the boundary).
176 * @param end The end index (included in the boundary).
177 */
178void
180
181 assert(currentTable_ != NULL);
182 assert(bounds.slotStartIndex() <= bounds.slotEndIndex());
183 currentTable_->push_back(bounds);
184}
185
186
187/**
188 * Fixes the address of the given instruction.
189 *
190 * When this is called, all the references to the given instruction are
191 * fixed with the given value of the address.
192 *
193 * @param instruction The instruction.
194 * @param address The address of the instruction.
195 * @exception OutOfRange If the given value is too large to fit to a boundary
196 * that refers to the instruction.
197 */
198void
200 const TTAProgram::Instruction& instruction, unsigned int address) {
202 std::pair<const Instruction*, unsigned int>(&instruction, address));
203 if (!MapTools::containsKey(references_, &instruction)) {
204 return;
205 } else {
206 IndexBoundSet& setForInstruction = indexBounds(instruction);
207 for (IndexBoundSet::const_iterator iter = setForInstruction.begin();
208 iter != setForInstruction.end(); iter++) {
209 IndexBoundTable* table = *iter;
210 fixBits(*table, address);
211 }
212 }
213}
214
215/**
216 * Marks the instruction starting point.
217 *
218 * The instruction starting point should be marked to the position of
219 * the first bit (the smallest index in the vector) of instruction.
220 *
221 * @param position The position of the starting point.
222 */
223void
225 if (instructionBoundaries_.size() == 0) {
226 instructionBoundaries_.push_back(position);
227 } else {
228 if (instructionBoundaries_.back() < position) {
229 instructionBoundaries_.push_back(position);
230 } else {
231 for (BoundaryTable::iterator iter = instructionBoundaries_.begin();
232 iter != instructionBoundaries_.end(); iter++) {
233 if (*iter > position) {
234 instructionBoundaries_.insert(iter, position);
235 return;
236 } else if (*iter == position) {
237 return;
238 }
239 }
240 assert(false);
241 }
242 }
243}
244
245
246/**
247 * Returns the number of instructions in the vector.
248 *
249 * The count is determined by means of the number of instruction boundaries.
250 *
251 * @return The number of instructions.
252 */
253unsigned int
257
258
259/**
260 * Returns the instruction starting point at the given position.
261 *
262 * The boundaries are returned in the correct order, that is, if parameter 0 is
263 * given, the starting point of the first instruction is returned.
264 *
265 * @return The instruction starting point at the given position.
266 * @exception OutOfRange If the given index is too large.
267 */
268unsigned int
270 if (index >= instructionBoundaries_.size()) {
271 const string procName = "InstructionBitVector::instructionBoundary";
272 throw OutOfRange(__FILE__, __LINE__, procName);
273 } else {
274 return instructionBoundaries_[index];
275 }
276}
277
278/**
279 * Returns the set of index bounds that refer to the given instruction.
280 *
281 * @param instruction The instruction.
282 */
285 const TTAProgram::Instruction& instruction) {
286
287 if (!MapTools::containsKey(references_, &instruction)) {
288 IndexBoundSet* newSet = new IndexBoundSet;
289 std::pair<const Instruction*, IndexBoundSet*> newPair(
290 &instruction, newSet);
291 references_.insert(newPair);
292 return *newSet;
293 } else {
295 references_, &instruction);
296 }
297}
298
299
300/**
301 * Adds the IndexBoundTables from the given IndexBoundSet to the given
302 * IndexBoundSet.
303 *
304 * @param from The IndexBoundSet from which the tables are copied.
305 * @param to The IndexBoundSet to which the tables are added.
306 */
307void
309 const IndexBoundSet& from,
310 IndexBoundSet& to) {
311
312 for (IndexBoundSet::const_iterator iter = from.begin();
313 iter != from.end(); iter++) {
314
315 const IndexBoundTable* fromTable = *iter;
316 IndexBoundTable* newTable = new IndexBoundTable(*fromTable);
317
318 for (IndexBoundTable::iterator iter = newTable->begin();
319 iter != newTable->end(); iter++) {
320 (*iter).incrStartIndex(size());
321 (*iter).incrEndIndex(size());
322 }
323
324 to.insert(newTable);
325 }
326}
327
328
329/**
330 * Fixes the sections given in the IndexBoundTable of the bit vector with
331 * the given value.
332 *
333 * @param indexes The table of section being fixed.
334 * @param value The value.
335 * @exception OutOfRange If the value is too large to fit to the boundary.
336 */
337void
339 const IndexBoundTable& indexes, unsigned int value) {
340 int requiredSize = MathTools::requiredBits(value);
341 int availableSize = this->availableSize(indexes);
342 if (requiredSize > availableSize) {
343 string errorMsg = "Unable to fix instruction reference with the "
344 "correct instruction address due to insuffient space reserved "
345 "for the immediate.";
346 throw OutOfRange(__FILE__, __LINE__, __func__, errorMsg);
347 }
348
349 int currentBit = 0;
350 int stopBit = requiredSize;
351
352 for (IndexBoundTable::const_reverse_iterator iter = indexes.rbegin();
353 iter != indexes.rend(); iter++) {
354
355 const IndexBound& iBound = *iter;
356
357 unsigned int startIndex = iBound.slotStartIndex();
358 unsigned int endIndex = iBound.slotEndIndex();
359
360 if ((*iter).isLimmEncoded()) {
361 // Check limm slice indices and update iteration boundaries.
362 // LIMM is written from LSB to MSB. Start from the rightmost bit
363 // of *this* limm slot.
364 currentBit = iBound.limmRightIndex();
365 stopBit = iBound.limmLeftIndex();
366 assert((stopBit-currentBit) == (iBound.limmWidth()-1));
367 }
368 for (unsigned int index = endIndex; index >= startIndex; index--) {
369 // Rewrite with new value required bits, zero the higher ones
370 if (currentBit <= stopBit) {
371 operator[](index) = MathTools::bit(value, currentBit);
372 } else {
373 operator[](index) = false;
374 }
375 currentBit++;
376 }
377 }
378}
379
380/**
381 * Returns the number of bits available in the given IndexBoundTable.
382 *
383 * @param indexes The IndexBoundTable.
384 * @return The number of bits.
385 */
386unsigned int
388
389 unsigned int size(0);
390 for (IndexBoundTable::const_iterator iter = indexes.begin();
391 iter != indexes.end(); iter++) {
392 size += (*iter).slotEndIndex() - (*iter).slotStartIndex() + 1;
393 }
394 return size;
395}
#define __func__
#define assert(condition)
void pushBack(long long unsigned int integer, int size)
Definition BitVector.cc:94
unsigned int slotEndIndex() const
Definition IndexBound.cc:81
unsigned int slotStartIndex() const
Definition IndexBound.cc:70
int limmWidth() const
int limmRightIndex() const
int limmLeftIndex() const
void markInstructionStartingPoint(unsigned int position)
void addIndexBoundTables(const IndexBoundSet &from, IndexBoundSet &to)
static unsigned int availableSize(const IndexBoundTable &indexes)
InstructionAddressTable instructionAddresses_
Addresses of the instructions.
void startSettingInstructionReference(const TTAProgram::Instruction &instruction)
unsigned int instructionCount() const
void fixBits(const IndexBoundTable &indexes, unsigned int value)
IndexBoundSet & indexBounds(const TTAProgram::Instruction &instruction)
unsigned int instructionStartingPoint(unsigned int index) const
IndexBoundTable * currentTable_
IndexBoundTable being under construction.
void pushBack(const InstructionBitVector &bits)
BoundaryTable instructionBoundaries_
Stores the instruction boundaries.
void fixInstructionAddress(const TTAProgram::Instruction &instruction, unsigned int address)
std::set< IndexBoundTable * > IndexBoundSet
A set type that stores IndexBoundTables.
void addIndexBoundsForReference(IndexBound bounds)
ReferenceMap references_
Contains information of the parts of the bit vector that refer to an instruction address.
std::vector< IndexBound > IndexBoundTable
A vector type that stores index bounds.
static KeyType keyForValue(const MapType &aMap, const ValueType &aValue)
static bool containsKey(const MapType &aMap, const KeyType &aKey)
static int requiredBits(unsigned long int number)
static bool bit(ULongWord integer, unsigned int index)