decode_tree.cpp

這是一個arm模擬器 以C++實做 主要模擬ARM9架構

/*************************************************************************
    Copyright (C) 2002 - 2007 Wei Qin
    See file COPYING for more information.

    This program is free software; you can redistribute it and/or modify    
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.
*************************************************************************/

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <cassert>
#include "decode_tree.h"

#define DEBUG 0

using namespace std;

extern bool do_onebit;

DecodeTreeNode::~decode_tree_node()
{
	delete table;
	/* delete children */
	vector<DecodeTreeNode *>::iterator it;
	for (it=children.begin(); it!=children.end(); it++)
		delete *it;
}

/* main decoding entrance */
void DecodeTreeNode::decode(double minUtilization)
{
	this->gamma = minUtilization;

	InstWord mask = this->table->getMask();

	this->totalTableSize = 0;
	this->totalNodeCount = 0;

	/* check if this is a trivial node */
	if (this->table->getUSize()<=1 || this->table->getHTreeHeight()==0.0) {
		this->scheme = DECODE_NULL;
		this->height = 0.0;
		this->maxHeight = 0;
		this->minHeight = 0;
		return;
	}

#if DEBUG>0
	cout << *(this->table);
#endif

	/* first, see if any pattern works well
	 * starting from empty, we grow a pattern bit by bit
	 */
	double minPatternHeight = 1e+200;
	double maxPatternGain = -1e+200;
	double minPatternRatio = 1.0;
	InstWord minPatternSignature = 0u;
	InstWord minPatternMask = 0u;

	/* 1 bit case is symmetric, both positive and negative signature
	 * will generate the same height, we need to try out more bits from both */
	unsigned int numBits = 0;
	bool moveOn = true;
	while (moveOn) {

		moveOn = false;
		double maxGain = -1e+200;
		double minRatio = 0.0;
		double minHeight = 0.0;
		InstWord minMask;
		InstWord minSignature;

		for (unsigned int bitPos=0; bitPos<INSTBITS; bitPos++) {

			InstWord theBit = power2(bitPos);

			/* if the bit is already within current pattern, or
			 * if the bit is a don't care for the table, we skip
			 */
			if ((theBit&minPatternMask)!=0u || (theBit&mask)==0u) continue;

			/* when numBits = 0, 1 bit pattern, symmetric, test only one case */
			/* when numBits = 1, 2 bit pattern, test four cases */
			/* when numBits > 1, test only two cases */
			int ntry = (numBits==0)?1:(numBits==1)?4:2;
			for (int k=0; k<ntry; k++) {

				InstWord currentMask = minPatternMask|theBit;
				InstWord currentSignature = minPatternSignature;

				/* two bit pattern has four cases */
				if (numBits==1) {
					switch (k) {
						case 0:
							currentSignature = 0u; break;
						case 1:
							currentSignature = theBit; break;
						case 2:
							currentSignature = minPatternMask; break;
						case 3:
							currentSignature = currentMask; break;
						default: /*no such case */ break;
					}
				}
				else {
					if (k) currentSignature |= theBit;
				}

				/* try to split the table based on the pattern */
				vector<DecodeTable *> subs = this->table->divide_by_pattern
					(currentMask, currentSignature);

				/* check if the pattern is useless */
				if (subs[1]->getSize()==0 || subs[0]->getSize()==0) {
					delete subs[0];
					delete subs[1];
					continue;
				}

				/* calc. the new average decoding height */
				double height = subs[0]->getProb()*subs[0]->getHTreeHeight() +
					subs[1]->getProb()*subs[1]->getHTreeHeight() + 1;

				/* calc. the utilization ratio as 1/mr (see paper) */
				double totalSize = 1;
				totalSize += subs[0]->getUSize()?(subs[0]->getUSize()-1):0;
				totalSize += subs[1]->getUSize()?(subs[1]->getUSize()-1):0;
				double uratio = (double)(this->table->getUSize()-1)/totalSize;

				/* calc. the gain as the negation of Hc (see paper) */
				double gain = - height;
				gain += minUtilization*(log(uratio)/log(2.0));
				if (gain>maxGain && uratio>MINUTILRATE) {
					maxGain = gain;
					minMask = currentMask;
					minSignature = currentSignature;
					minHeight = height;
					minRatio = uratio;
#if 0
					cout << "***" << minMask << "***"; 
					cout << "***" << minSignature << "***";
					cout << "***" << minHeight << "***";
					cout << "***" << minRatio << "***" << endl;
#endif
				}

				delete subs[0];
				delete subs[1];
			}
		}

		/* check if worthwhile to grow the new bit */
		if (maxGain>maxPatternGain) {
			minPatternHeight = minHeight;
			minPatternSignature = minSignature;
			minPatternMask = minMask;
			minPatternRatio = minRatio;
			maxPatternGain = maxGain;
			if (minPatternHeight!=1.0) moveOn = true;
		}

#if DEBUG>1
		cout << dec << numBits << " bit patterns: "
			<< " minHeight "
			<< minPatternHeight
			<< " minMask "
			<< PADDEDHEX << minPatternMask
			<< " minSignature "
			<< PADDEDHEX << minPatternSignature
			<< " uratio " << minRatio
			<< endl;
#endif
		numBits++;

		if (do_onebit) break;
	}

	/* next, see how table works */
	unsigned int minTableShift = 0, minTableBits = 0;
	double minTableHeight = minPatternHeight;
	double minTableRatio = 1.0;
	double maxTableGain =  -1e+200;
	InstWord minTableMask;

	/* table has at least 4 entries */
	numBits = 1;
	moveOn = true;
	while (moveOn && (!do_onebit)) {

		moveOn = false;
		numBits++;

		double minHeight = 1e+200;
		double maxGain = -1e+200;
		double minRatio =0.0;
		InstWord minMask;
		unsigned int minShift =0;

		InstWord tableMask = n_ones(numBits);
		for (unsigned int tableShift=0; tableShift<=INSTBITS-numBits;
			tableShift++) {

			InstWord msk = tableMask<<tableShift;

			/* if msk contains don't care bits, skip */
			if ((msk&mask)!=msk) continue;
#if 0
			cout << "***" << msk << "***" << endl;
#endif

			/* split into 2^numBits tables */
			vector<DecodeTable *> subs = this->table->divide_by_table(msk,
				numBits, tableShift);

			/* calc. table size
			 * calc. average decoding height
			 */
			unsigned int totalSize = 1;
			double height = 1.0;
			vector<DecodeTable *>::iterator it;
			for (it=subs.begin(); it!=subs.end(); it++) {
				height += (*it)->getProb()*(*it)->getHTreeHeight();
				totalSize += (*it)->getUSize()?(*it)->getUSize():1;
				delete *it;
			}

			/* calc. the utilization ratio as 1/mr */
			double uratio = (double)(this->table->getUSize()-1)/totalSize;

			/* calc. the gain as -Hc */
			double gain = - height;
			gain += minUtilization*(log(uratio)/log(2.0));

			if (gain>maxGain && uratio>MINUTILRATE) {
				maxGain = gain;
				minHeight = height;
				minMask = msk;
				minShift = tableShift;
				minRatio = uratio;
			}
		}

#if DEBUG>1
		cout << dec << numBits << " bit tables :"
			<< " minHeight " << minHeight
			<< " minMask " << PADDEDHEX << minMask
			<< " uratio " << minRatio
			<< endl;
#endif
		if (maxGain>maxTableGain) {
			minTableHeight = minHeight;
			minTableMask = minMask;
			minTableShift = minShift;
			minTableBits = numBits;
			minTableRatio = minRatio;
			maxTableGain = maxGain;
			if (minTableHeight!=1.0) moveOn = true;
		}
	}

	/* now decode recursively */
	if (maxPatternGain>=maxTableGain) {
		this->scheme = DECODE_PATTERN;
#if DEBUG>0
		cout << "decode by pattern: " 
			<< " mask " << PADDEDHEX << minPatternMask
			<< " signature " << PADDEDHEX << minPatternSignature
			<< endl;
#endif
	} else {
		this->scheme = DECODE_TABLE;
#if DEBUG>0
		cout << "decode by table: "
			<< " mask " << PADDEDHEX << minTableMask