Difference between revisions of "Arrange timed code.cpp"

//// Copyright (c) 2013 Danny Havenith //// Distributed under the Boost Software License, Version 1.0. (See accompanying // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) //

#include <iostream> #include <string> #include <map> #include <vector> #include <algorithm> #include <limits> #include <boost/foreach.hpp>

using namespace std; /// Simple struct that can be used as an input to describe blocks of assembly instructions with jumps and labels struct labelinfo { string label; string jumpto; };

/// a contiguous block of assembly instructions. /// This structure holds information about the size of the block, /// all relative jumps that emanate from this block and all labes that /// are defined in this block. struct block { typedef map<string, int> labelmap; int

labelmap labels; labelmap jumps;

bool operator<( const block &other) const { return name < other.name; } };

/// Parse labelinfo structs and create disjunct blocks. /// This function will traverse the range of labelinfos and create blocks on-the-go. /// The last statement of a block is recognized by the label "END", whenever this label is encountered all /// statements so far will be combined in one block and this block will be appended to the result. vector<block> parse_blocks( labelinfo *begin, labelinfo *end) { vector<block> result;

int current_line = 0; block current_block; while (begin != end) { if (begin->label == "END") { current_block.size = current_line + 1; result.push_back( current_block); current_line = 0; current_block = block(); } else { if (!begin->label.empty()) { if (current_line == 0) current_block.name = begin->label; current_block.labels[begin->label] = current_line; } if (!begin->jumpto.empty()) { current_block.jumps[begin->jumpto] = current_line; } ++current_line; } ++begin; } return result; }

/// Given a sequence of blocks, determine the absolute addresses of the labels that /// appear in each block. block::labelmap map_labels( const vector<block>& blocks) { block::labelmap label_addresses;

// determine absolute labels int current_block_startaddress = 0; BOOST_FOREACH( const block &b, blocks) { BOOST_FOREACH( const block::labelmap::value_type &label, b.labels) { label_addresses[label.first] = label.second + current_block_startaddress; } current_block_startaddress += b.size; }

return label_addresses; }

/// Determine whether a sequence of blocks matches the criterium of valid jumps. /// This criterium is matched if all jumps are close enough to their destination labels. /// Close enough, in this case, means that the offset between jump and destination must fall within [-63,64] /// This function is faster than the calculate_fit() function because it can terminate immediately if it finds a jump /// that does not qualify. bool is_fit( const vector<block> &blocks) { block::labelmap label_addresses = map_labels(blocks);

// see if all jumps are in range. int current_block_startaddress = 0; BOOST_FOREACH( const block &b, blocks) { BOOST_FOREACH( const block::labelmap::value_type &jump, b.jumps) { int offset = label_addresses[jump.first] - (jump.second + current_block_startaddress); if (offset > 64 || offset < -63) return false; } current_block_startaddress += b.size; }

return true; }

/// This is largely a copy of the is_fit() function with some changes. Instead of returning a fit/not-fit boolean, /// this function returns a score that is calculated as the maximum (absolute) jump distance. /// This function is slightly less efficient than that is_fit() function, because it needss to complete the /// calculation, even if the score is higher than the fitness criterium. int calculate_fit( const vector<block> &blocks) { block::labelmap label_addresses = map_labels( blocks);

// calculate the maximum jump offset in this sequence of blocks. int max_offset = 0; int current_block_startaddress = 0; BOOST_FOREACH( const block &b, blocks) { BOOST_FOREACH( const block::labelmap::value_type &jump, b.jumps) { int offset = label_addresses[jump.first] - (jump.second + current_block_startaddress); if (offset > max_offset) max_offset = offset; if (-offset > max_offset) max_offset = -offset; } current_block_startaddress += b.size; }