diff options
author | tpearson <tpearson@283d02a7-25f6-0310-bc7c-ecb5cbfe19da> | 2010-02-24 01:49:02 +0000 |
---|---|---|
committer | tpearson <tpearson@283d02a7-25f6-0310-bc7c-ecb5cbfe19da> | 2010-02-24 01:49:02 +0000 |
commit | 5de3dd4762ca33a0f92e79ffa4fe2ff67069d531 (patch) | |
tree | bad482b7afa4cdf47422d60a5dd2c61c7e333b09 /microbe/optimizer.cpp | |
download | ktechlab-5de3dd4762ca33a0f92e79ffa4fe2ff67069d531.tar.gz ktechlab-5de3dd4762ca33a0f92e79ffa4fe2ff67069d531.zip |
Added KDE3 version of ktechlab
git-svn-id: svn://anonsvn.kde.org/home/kde/branches/trinity/applications/ktechlab@1095338 283d02a7-25f6-0310-bc7c-ecb5cbfe19da
Diffstat (limited to 'microbe/optimizer.cpp')
-rw-r--r-- | microbe/optimizer.cpp | 512 |
1 files changed, 512 insertions, 0 deletions
diff --git a/microbe/optimizer.cpp b/microbe/optimizer.cpp new file mode 100644 index 0000000..33b0bcd --- /dev/null +++ b/microbe/optimizer.cpp @@ -0,0 +1,512 @@ +/*************************************************************************** + * Copyright (C) 2005 by David Saxton * + * david@bluehaze.org * + * * + * 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. * + ***************************************************************************/ + +#include "instruction.h" +#include "optimizer.h" + +#include <kdebug.h> + +#include <assert.h> +#include <iostream> +using namespace std; + + +QString binary( uchar val ) +{ + QString bin = QString::number( val, 2 ); + QString pad; + pad.fill( '0', 8-bin.length() ); + return pad + bin; +} + + +Optimizer::Optimizer() +{ + m_pCode = 0l; +} + + +Optimizer::~Optimizer() +{ +} + + +void Optimizer::optimize( Code * code ) +{ +// return; + m_pCode = code; + + bool changed; + do + { + changed = false; + + // Repeatedly generate links and states until + // we know as much as possible about the system. + propagateLinksAndStates(); + + // Remove instructions without input links + changed |= pruneInstructions(); + + // Perform optimizations based on processor states + changed |= optimizeInstructions(); + } + while ( changed ); +} + + +void Optimizer::propagateLinksAndStates() +{ + int count = 0; + + do + { + count++; + m_pCode->generateLinksAndStates(); + } + while ( giveInputStates() ); + +// cout << "count="<<count<<endl; +} + + +bool Optimizer::giveInputStates() +{ + bool changed = false; + + Code::iterator end = m_pCode->end(); + for ( Code::iterator it = m_pCode->begin(); it != end; ++it ) + { + // Now, build up the most specific known processor state from the instructins + // that could be executed immediately before this instruction. + // This is done by taking the output state of the first input link, and + // then reducing it to the greatest common denominator of all the input states. + + const InstructionList list = (*it)->inputLinks(); + if ( list.isEmpty() ) + continue; + + InstructionList::const_iterator inputIt = list.begin(); + InstructionList::const_iterator inputsEnd = list.end(); + + ProcessorState input = (*(inputIt++))->outputState(); + + while ( inputIt != inputsEnd ) + input.merge( (*inputIt++)->outputState() ); + + if ( !changed ) + { + ProcessorState before = (*it)->inputState(); + bool stateChanged = ( before != input ); + changed |= stateChanged; + } + + (*it)->setInputState( input ); + } + return changed; +} + + +bool Optimizer::pruneInstructions() +{ + bool removed = false; + + //BEGIN remove instructions without any input links + Code::iterator it = m_pCode->begin(); + Code::iterator end = m_pCode->end(); + + // Jump past the first instruction, as nothing (necessarily) points to that + if ( it != end ) + ++it; + + while ( it != end ) + { + if ( (*it)->inputLinks().isEmpty() ) + { +// cout << "Removing: " << (*it)->code() << endl; + it.removeAndIncrement(); + removed = true; + } + else + ++it; + } + end = m_pCode->end(); // Reset end as instructions may have been removed + //END remove instructions without any input links + + + //BEGIN remove labels without any reference to them + // First: build up a list of labels which are referenced + QStringList referencedLabels; + for ( it = m_pCode->begin(); it != end; ++it ) + { + if ( Instr_goto * ins = dynamic_cast<Instr_goto*>(*it) ) + referencedLabels << ins->label(); + else if ( Instr_call * ins = dynamic_cast<Instr_call*>(*it) ) + referencedLabels << ins->label(); + } + + // Now remove labels from instructions that aren't in the referencedLabels list + for ( it = m_pCode->begin(); it != end; ++it ) + { + QStringList labels = (*it)->labels(); + + QStringList::iterator labelsEnd = labels.end(); + for ( QStringList::iterator labelsIt = labels.begin(); labelsIt != labelsEnd; ) + { + if ( !referencedLabels.contains( *labelsIt ) ) + { + labelsIt = labels.erase( labelsIt ); + removed = true; + } + else + ++labelsIt; + } + + (*it)->setLabels( labels); + } + //END remove labels without any reference to them + + return removed; +} + + +bool Optimizer::optimizeInstructions() +{ + //BEGIN Optimization 1: Concatenate chained GOTOs + // We go through the instructions looking for GOTO statements. If we find any, then + // we trace back through their input links to any other GOTO statements - any that + // are found are then redirected to point to the label that the original GOTO statement + // was pointing at. + Code::iterator end = m_pCode->end(); + for ( Code::iterator it = m_pCode->begin(); it != end; ++it ) + { + Instr_goto * gotoIns = dynamic_cast<Instr_goto*>(*it); + if ( !gotoIns ) + continue; + + if ( redirectGotos( gotoIns, gotoIns->label() ) ) + return true; + m_pCode->setAllUnused(); + } + //END Optimization 1: Concatenate chained GOTOs + + + //BEGIN Optimization 2: Remove GOTOs when jumping to the subsequent instruction + // Any GOTO instructions that just jump to the next instruction can be removed. + for ( Code::iterator it = m_pCode->begin(); it != end; ++it ) + { + Instruction * next = *(++Code::iterator(it)); + Instruction * gotoIns = dynamic_cast<Instr_goto*>(*it); + if ( !gotoIns || !next || (gotoIns->outputLinks().first() != next) ) + continue; + +// cout << "Removing: " << gotoIns->code() << endl; + it.removeAndIncrement(); + return true; + } + end = m_pCode->end(); + //END Optimization 2: Remove GOTOs when jumping to the subsequent instruction + + + //BEGIN Optimization 3: Replace MOVWF with CLRF with W is 0 + // We look for MOVWF instructions where the working register holds zero. + // We then replace the MOVWf instruction with a CLRF instruction. + for ( Code::iterator it = m_pCode->begin(); it != end; ++it ) + { + Instr_movwf * ins = dynamic_cast<Instr_movwf*>(*it); + if ( !ins ) + continue; + + ProcessorState inputState = ins->inputState(); + RegisterState working = inputState.working; + if ( (working.value != 0x0) || (working.known != 0xff) ) + continue; + + // CLRF sets the Z flag of STATUS to 1, but MOVWF does not set any flags. + // So we need to check for dependence of the Z flag if we are possibly + // changing the flag by replacing the instruction. + if ( !(inputState.status.definiteOnes() & (1 << RegisterBit::Z)) ) + { + // Input state of Z flag is either unknown or low. + + uchar depends = generateRegisterDepends( *it, Register::STATUS ); + if ( depends & (1 << RegisterBit::Z) ) + { + // Looks like there's some instruction that depends on the zero bit, + // and we about potentially about to change it. + continue; + } + } + + + Instr_clrf * instr_clrf = new Instr_clrf( ins->file() ); +// cout << "Replacing \""<<(*it)->code()<<"\" with \""<<instr_clrf->code()<<"\"\n"; + it.insertBefore( instr_clrf ); + it.removeAndIncrement(); + return true; + } + //END Optimization 3: Replace MOVWF with CLRF with W is 0 + + + //BEGIN Optimization 4: Replace writes to W with MOVLW when value is known + // We look for instructions with AssemblyType either WorkingOriented, or FileOriented + // and writing to W. Then, if the value is known and there are no instructions that + // depend on the STATUS bits set by the instruction, then we replace it with a MOVLW + for ( Code::iterator it = m_pCode->begin(); it != end; ++it ) + { + if ( dynamic_cast<Instr_movlw*>(*it) ) + { + // If we don't catch this condition, we'll end up in an infinite loop, + // repeatedly replacing the first MOVLW that we come across. + continue; + } + + bool workingOriented = (*it)->assemblyType() == Instruction::WorkingOriented; + bool fileOriented = (*it)->assemblyType() == Instruction::FileOriented; + if ( !workingOriented && (!fileOriented || ((*it)->dest() != 0)) ) + continue; + + // So can now assume that workingOriented and fileOriented are logical opposites + + RegisterState outputState = (*it)->outputState().working; + if ( outputState.known != 0xff ) + continue; + + ProcessorBehaviour behaviour = (*it)->behaviour(); + + // MOVLW does not set any STATUS flags, but the instruction that we are replacing + // might. So we must check if any of these STATUS flags are depended upon, and if so + // only allow replacement if the STATUS flags are not being changed. + if ( !canRemove( *it, Register::STATUS, behaviour.reg( Register::STATUS ).indep ) ) + continue; + + Instr_movlw * movlw = new Instr_movlw( outputState.value ); +// cout << "Replacing \""<<(*it)->code()<<"\" with \""<<movlw->code()<<"\"\n"; + it.insertBefore( movlw ); + it.removeAndIncrement(); + return true; + } + //END Optimization 4: Replace writes to W with MOVLW when value is known + + + //BEGIN Optimization 5: Remove writes to a bit when the value is ignored and overwritten again + // We go through the instructions looking for statements that write to a bit (bcf, bsf). + // If we find any, then we trace through their output links to see if their value is + // overwritten before it is used - and if so, the instruction can be removed. + for ( Code::iterator it = m_pCode->begin(); it != end; ++it ) + { + if ( (*it)->assemblyType() != Instruction::BitOriented ) + continue; + + const Register regSet = (*it)->file(); + + if ( regSet.affectsExternal() ) + continue; + + uchar bitPos = (*it)->bit().bitPos(); + + ProcessorState inputState = (*it)->inputState(); + ProcessorState outputState = (*it)->outputState(); + ProcessorBehaviour behaviour = (*it)->behaviour(); + + // Are we rewriting over a bit that already has the same value? + // (Note this check is just for the bit changing instructions, as there is a similar + // check for register changing actions later on when we know which bits care about + // being overwritten). + if ( inputState.reg( regSet ).known & (1 << bitPos) ) + { + bool beforeVal = (inputState.reg( regSet ).value & (1 << bitPos)); + bool afterVal = (outputState.reg( regSet ).value & (1 << bitPos)); + if ( beforeVal == afterVal ) + { +// cout << "Removing: " << (*it)->code() << endl; + it.removeAndIncrement(); + return true; + } + } + + uchar depends = generateRegisterDepends( *it, regSet ); + if ( !(depends & (1 << bitPos)) ) + { + // Bit is overwritten before being used - so lets remove this instruction :) +// cout << "Removing: " << (*it)->code() << endl; + it.removeAndIncrement(); + return true; + } + } + m_pCode->setAllUnused(); + //END Optimization 5: Remove writes to a bit when the value is ignored and overwritten again + + + //BEGIN Optimization 6: Remove writes to a register when the value is ignored and overwritten again + // We go through the instructions looking for statements that write to a register (such as MOVLW). + // If we find any, then we trace through their output links to see if their value is + // overwritten before it is used - and if so, the instruction can be removed. + for ( Code::iterator it = m_pCode->begin(); it != end; ++it ) + { + bool noFile = false; + + switch ( (*it)->assemblyType() ) + { + case Instruction::WorkingOriented: + noFile = true; + // (no break) + + case Instruction::FileOriented: + break; + + case Instruction::BitOriented: + case Instruction::Other: + case Instruction::None: + continue; + } + + const Register regSet = noFile ? Register( Register::WORKING ) : (*it)->outputReg(); + + if ( regSet.affectsExternal() ) + continue; + + ProcessorState inputState = (*it)->inputState(); + ProcessorState outputState = (*it)->outputState(); + ProcessorBehaviour behaviour = (*it)->behaviour(); + + // All ins_file instructions will affect at most two registers; the + // register it is writing to (regSet) and the status register. + // In i==0, test regSet + // In i==1, test STATUS + bool ok = true; + for ( unsigned i = 0; i < 2; ++ i) + { + // If we are testing STATUS, then we assume that the bits changed + // are only those that are marked as independent. + uchar bitmask = ( i == 1 ) ? behaviour.reg( Register::STATUS ).indep : 0xff; + if ( !canRemove( *it, (i == 0) ? regSet : Register::STATUS, bitmask ) ) + { + ok = false; + break; + } + } + + if ( !ok ) + continue; + + // Looks like we're free to remove the instruction :); +// cout << "Removing: " << (*it)->code() << endl; + it.removeAndIncrement(); + return true; + } + m_pCode->setAllUnused(); + //END Optimization 6: Remove writes to a register when the value is ignored and overwritten again + + return false; +} + + +bool Optimizer::redirectGotos( Instruction * current, const QString & label ) +{ + if ( current->isUsed() ) + return false; + + current->setUsed( true ); + + bool changed = false; + + const InstructionList list = current->inputLinks(); + InstructionList::const_iterator end = list.end(); + for ( InstructionList::const_iterator it = list.begin(); it != end; ++it ) + { + Instr_goto * gotoIns = dynamic_cast<Instr_goto*>(*it); + if ( !gotoIns || (gotoIns->label() == label) ) + continue; + +// cout << "Redirecting goto to label \"" << label << "\" : " << gotoIns->code() << endl; + gotoIns->setLabel( label ); + changed = true; + } + + return changed; +} + + +uchar Optimizer::generateRegisterDepends( Instruction * current, const Register & reg ) +{ + m_pCode->setAllUnused(); + + const InstructionList list = current->outputLinks(); + InstructionList::const_iterator listEnd = list.end(); + + uchar depends = 0x0; + + for ( InstructionList::const_iterator listIt = list.begin(); listIt != listEnd; ++listIt ) + depends |= registerDepends( *listIt, reg ); + + return depends; +} + + +uchar Optimizer::registerDepends( Instruction * current, const Register & reg ) +{ + if ( current->isUsed() ) + return current->registerDepends( reg ); + + current->setUsed( true ); + + uchar depends = 0x0; + + const InstructionList list = current->outputLinks(); + InstructionList::const_iterator end = list.end(); + for ( InstructionList::const_iterator it = list.begin(); it != end; ++it ) + depends |= registerDepends( *it, reg ); + + RegisterBehaviour behaviour = current->behaviour().reg( reg ); + depends &= ~(behaviour.indep); // Get rid of depend bits that are set in this instruction + depends |= behaviour.depends; // And add the ones that are dependent in this instruction + + current->setRegisterDepends( depends, reg ); + return depends; +} + + +bool Optimizer::canRemove( Instruction * ins, const Register & reg, uchar bitMask ) +{ + // The bits that are depended upon in the future for this register + uchar depends = generateRegisterDepends( ins, reg ); + + // Only interested in those bits allowed by the bit mask + depends &= bitMask; + + RegisterState inputState = ins->inputState().reg( reg ); + RegisterState outputState = ins->outputState().reg( reg ); + + if ( inputState.unknown() & depends ) + { + // There's at least one bit whose value is depended on, but is not known before this + // instruction is executed. Therefore, it is not safe to remove this instruction. + return false; + } + + if ( outputState.unknown() & depends ) + { + // There's at least one bit whose value is depended on, but is not known after this + // instruction is executed. Therefore, it is not safe to remove this instruction. + return false; + } + + uchar dependsInput = inputState.value & depends; + uchar dependsOutput = outputState.value & depends; + if ( dependsInput != dependsOutput ) + { + // At least one bit whose value is depended upon was changed. + return false; + } + + return true; +} + |