File indexing completed on 2024-07-21 08:05:26

0001 /***************************************************************************
0002  *   Copyright (C) 2005 by David Saxton                                    *
0003  *   david@bluehaze.org                                                    *
0004  *                                                                         *
0005  *   This program is free software; you can redistribute it and/or modify  *
0006  *   it under the terms of the GNU General Public License as published by  *
0007  *   the Free Software Foundation; either version 2 of the License, or     *
0008  *   (at your option) any later version.                                   *
0009  ***************************************************************************/
0010 
0011 #include "instruction.h"
0012 #include "optimizer.h"
0013 
0014 #include <KLocalizedString>
0015 
0016 #include <QDebug>
0017 
0018 #include <cassert>
0019 #include <iostream>
0020 using namespace std;
0021 
0022 
0023 QString binary( uchar val )
0024 {
0025     QString bin = QString::number( val, 2 );
0026     QString pad;
0027     pad.fill( '0', 8-bin.length() );
0028     return pad + bin;
0029 }
0030 
0031 
0032 Optimizer::Optimizer()
0033 {
0034     m_pCode = nullptr;
0035 }
0036 
0037 
0038 Optimizer::~Optimizer()
0039 {
0040 }
0041 
0042 
0043 void Optimizer::optimize( Code * code )
0044 {
0045 //  return;
0046     m_pCode = code;
0047 
0048     const int maxIterations = 10000; // selected randomly
0049 
0050     bool changed;
0051     int iterationNumber = 0;
0052     do
0053     {
0054         ++iterationNumber;
0055         changed = false;
0056 
0057         // Repeatedly generate links and states until
0058         // we know as much as possible about the system.
0059         propagateLinksAndStates();
0060 
0061         // Remove instructions without input links
0062         changed |= pruneInstructions();
0063 
0064         // Perform optimizations based on processor states
0065         changed |= optimizeInstructions();
0066     }
0067     while ( changed && (iterationNumber < maxIterations) );
0068 
0069     if (iterationNumber >= maxIterations) {
0070         QString warnMessage( i18n(
0071             "Internal issue: Optimization has not finished in %1 iterations.",
0072             iterationNumber) );
0073         //qDebug() << warnMessage; // qDebug or qWarning generates "compilation failed" message in ktechlab
0074         std::cout << warnMessage.toStdString();
0075     }
0076 }
0077 
0078 
0079 void Optimizer::propagateLinksAndStates()
0080 {
0081     int count = 0;
0082 
0083     do
0084     {
0085         count++;
0086         m_pCode->generateLinksAndStates();
0087     }
0088     while ( giveInputStates() );
0089 
0090 //  cout << "count="<<count<<endl;
0091 }
0092 
0093 
0094 bool Optimizer::giveInputStates()
0095 {
0096     bool changed = false;
0097 
0098     Code::iterator end = m_pCode->end();
0099     for ( Code::iterator it = m_pCode->begin(); it != end; ++it )
0100     {
0101         // Now, build up the most specific known processor state from the instructins
0102         // that could be executed immediately before this instruction.
0103         // This is done by taking the output state of the first input link, and
0104         // then reducing it to the greatest common denominator of all the input states.
0105 
0106         const InstructionList list = (*it)->inputLinks();
0107         if ( list.isEmpty() )
0108             continue;
0109 
0110         InstructionList::const_iterator inputIt = list.begin();
0111         InstructionList::const_iterator inputsEnd = list.end();
0112 
0113         ProcessorState input = (*(inputIt++))->outputState();
0114 
0115         while ( inputIt != inputsEnd )
0116             input.merge( (*inputIt++)->outputState() );
0117 
0118         if ( !changed )
0119         {
0120             ProcessorState before = (*it)->inputState();
0121             bool stateChanged = ( before != input );
0122             changed |= stateChanged;
0123         }
0124 
0125         (*it)->setInputState( input );
0126     }
0127     return changed;
0128 }
0129 
0130 
0131 bool Optimizer::pruneInstructions()
0132 {
0133     bool removed = false;
0134 
0135     //BEGIN remove instructions without any input links
0136     Code::iterator it = m_pCode->begin();
0137     Code::iterator end = m_pCode->end();
0138 
0139     // Jump past the first instruction, as nothing (necessarily) points to that
0140     if ( it != end )
0141         ++it;
0142 
0143     while ( it != end )
0144     {
0145         if ( (*it)->inputLinks().isEmpty() )
0146         {
0147 //          cout << "Removing: " << (*it)->code() << endl;
0148             it.removeAndIncrement();
0149             removed = true;
0150         }
0151         else
0152             ++it;
0153     }
0154     end = m_pCode->end(); // Reset end as instructions may have been removed
0155     //END remove instructions without any input links
0156 
0157 
0158     //BEGIN remove labels without any reference to them
0159     // First: build up a list of labels which are referenced
0160     QStringList referencedLabels;
0161     for ( it = m_pCode->begin(); it != end; ++it )
0162     {
0163         if ( Instr_goto * ins = dynamic_cast<Instr_goto*>(*it) )
0164             referencedLabels << ins->label();
0165         else if ( Instr_call * ins = dynamic_cast<Instr_call*>(*it) )
0166             referencedLabels << ins->label();
0167     }
0168 
0169     // Now remove labels from instructions that aren't in the referencedLabels list
0170     for ( it = m_pCode->begin(); it != end; ++it )
0171     {
0172         QStringList labels = (*it)->labels();
0173 
0174         for ( QStringList::iterator labelsIt = labels.begin(); labelsIt != labels.end(); )
0175         {
0176             if ( !referencedLabels.contains( *labelsIt ) )
0177             {
0178                 labelsIt = labels.erase( labelsIt );
0179                 removed = true;
0180             }
0181             else
0182                 ++labelsIt;
0183         }
0184 
0185         (*it)->setLabels( labels);
0186     }
0187     //END remove labels without any reference to them
0188 
0189     return removed;
0190 }
0191 
0192 
0193 bool Optimizer::optimizeInstructions()
0194 {
0195     //BEGIN Optimization 1: Concatenate chained GOTOs
0196     // We go through the instructions looking for GOTO statements. If we find any, then
0197     // we trace back through their input links to any other GOTO statements - any that
0198     // are found are then redirected to point to the label that the original GOTO statement
0199     // was pointing at.
0200     Code::iterator end = m_pCode->end();
0201     for ( Code::iterator it = m_pCode->begin(); it != end; ++it )
0202     {
0203         Instr_goto * gotoIns = dynamic_cast<Instr_goto*>(*it);
0204         if ( !gotoIns )
0205             continue;
0206 
0207         if ( redirectGotos( gotoIns, gotoIns->label() ) )
0208             return true;
0209         m_pCode->setAllUnused();
0210     }
0211     //END Optimization 1: Concatenate chained GOTOs
0212 
0213 
0214     //BEGIN Optimization 2: Remove GOTOs when jumping to the subsequent instruction
0215     // Any GOTO instructions that just jump to the next instruction can be removed.
0216     for ( Code::iterator it = m_pCode->begin(); it != end; ++it )
0217     {
0218         Instruction * next = *(++Code::iterator(it));
0219         Instruction * gotoIns = dynamic_cast<Instr_goto*>(*it);
0220         if ( !gotoIns || !next || (gotoIns->outputLinks().first() != next) )
0221             continue;
0222 
0223 //      cout << "Removing: " << gotoIns->code() << endl;
0224         it.removeAndIncrement();
0225         return true;
0226     }
0227     end = m_pCode->end();
0228     //END Optimization 2: Remove GOTOs when jumping to the subsequent instruction
0229 
0230 
0231     //BEGIN Optimization 3: Replace MOVWF with CLRF with W is 0
0232     // We look for MOVWF instructions where the working register holds zero.
0233     // We then replace the MOVWf instruction with a CLRF instruction.
0234     for ( Code::iterator it = m_pCode->begin(); it != end; ++it )
0235     {
0236         Instr_movwf * ins = dynamic_cast<Instr_movwf*>(*it);
0237         if ( !ins )
0238             continue;
0239 
0240         ProcessorState inputState = ins->inputState();
0241         RegisterState working = inputState.working;
0242         if ( (working.value != 0x0) || (working.known != 0xff) )
0243             continue;
0244 
0245         // CLRF sets the Z flag of STATUS to 1, but MOVWF does not set any flags.
0246         // So we need to check for dependence of the Z flag if we are possibly
0247         // changing the flag by replacing the instruction.
0248         if ( !(inputState.status.definiteOnes() & (1 << RegisterBit::Z)) )
0249         {
0250             // Input state of Z flag is either unknown or low.
0251 
0252             uchar depends = generateRegisterDepends( *it, Register::STATUS );
0253             if ( depends & (1 << RegisterBit::Z) )
0254             {
0255                 // Looks like there's some instruction that depends on the zero bit,
0256                 // and we about potentially about to change it.
0257                 continue;
0258             }
0259         }
0260 
0261 
0262         Instr_clrf * instr_clrf = new Instr_clrf( ins->file() );
0263 //      cout << "Replacing \""<<(*it)->code()<<"\" with \""<<instr_clrf->code()<<"\"\n";
0264         it.insertBefore( instr_clrf );
0265         it.removeAndIncrement();
0266         return true;
0267     }
0268     //END Optimization 3: Replace MOVWF with CLRF with W is 0
0269 
0270 
0271     //BEGIN Optimization 4: Replace writes to W with MOVLW when value is known
0272     // We look for instructions with AssemblyType either WorkingOriented, or FileOriented
0273     // and writing to W. Then, if the value is known and there are no instructions that
0274     // depend on the STATUS bits set by the instruction, then we replace it with a MOVLW
0275     for ( Code::iterator it = m_pCode->begin(); it != end; ++it )
0276     {
0277         if ( dynamic_cast<Instr_movlw*>(*it) )
0278         {
0279             // If we don't catch this condition, we'll end up in an infinite loop,
0280             // repeatedly replacing the first MOVLW that we come across.
0281             continue;
0282         }
0283 
0284         bool workingOriented = (*it)->assemblyType() == Instruction::WorkingOriented;
0285         bool fileOriented = (*it)->assemblyType() == Instruction::FileOriented;
0286         if ( !workingOriented && (!fileOriented || ((*it)->dest() != 0)) )
0287             continue;
0288 
0289         // So can now assume that workingOriented and fileOriented are logical opposites
0290 
0291         RegisterState outputState = (*it)->outputState().working;
0292         if ( outputState.known != 0xff )
0293             continue;
0294 
0295         ProcessorBehaviour behaviour = (*it)->behaviour();
0296 
0297         // MOVLW does not set any STATUS flags, but the instruction that we are replacing
0298         // might. So we must check if any of these STATUS flags are depended upon, and if so
0299         // only allow replacement if the STATUS flags are not being changed.
0300         if ( !canRemove( *it, Register::STATUS, behaviour.reg( Register::STATUS ).indep ) )
0301             continue;
0302 
0303         Instr_movlw * movlw = new Instr_movlw( outputState.value );
0304 //      cout << "Replacing \""<<(*it)->code()<<"\" with \""<<movlw->code()<<"\"\n";
0305         it.insertBefore( movlw );
0306         it.removeAndIncrement();
0307         return true;
0308     }
0309     //END Optimization 4: Replace writes to W with MOVLW when value is known
0310 
0311 
0312     //BEGIN Optimization 5: Remove writes to a bit when the value is ignored and overwritten again
0313     // We go through the instructions looking for statements that write to a bit (bcf, bsf).
0314     //  If we find any, then we trace through their output links to see if their value is
0315     // overwritten before it is used - and if so, the instruction can be removed.
0316     for ( Code::iterator it = m_pCode->begin(); it != end; ++it )
0317     {
0318         if ( (*it)->assemblyType() != Instruction::BitOriented )
0319             continue;
0320 
0321         const Register regSet = (*it)->file();
0322 
0323         if ( regSet.affectsExternal() )
0324             continue;
0325 
0326         uchar bitPos = (*it)->bit().bitPos();
0327 
0328         ProcessorState inputState = (*it)->inputState();
0329         ProcessorState outputState = (*it)->outputState();
0330         ProcessorBehaviour behaviour = (*it)->behaviour();
0331 
0332         // Are we rewriting over a bit that already has the same value?
0333         // (Note this check is just for the bit changing instructions, as there is a similar
0334         // check for register changing actions later on when we know which bits care about
0335         // being overwritten).
0336         if ( inputState.reg( regSet ).known & (1 << bitPos) )
0337         {
0338             bool beforeVal = (inputState.reg( regSet ).value & (1 << bitPos));
0339             bool afterVal = (outputState.reg( regSet ).value & (1 << bitPos));
0340             if ( beforeVal == afterVal )
0341             {
0342 //              cout << "Removing: " << (*it)->code() << endl;
0343                 it.removeAndIncrement();
0344                 return true;
0345             }
0346         }
0347 
0348         uchar depends = generateRegisterDepends( *it, regSet );
0349         if ( !(depends & (1 << bitPos)) )
0350         {
0351             // Bit is overwritten before being used - so lets remove this instruction :)
0352 //          cout << "Removing: " << (*it)->code() << endl;
0353             it.removeAndIncrement();
0354             return true;
0355         }
0356     }
0357     m_pCode->setAllUnused();
0358     //END Optimization 5: Remove writes to a bit when the value is ignored and overwritten again
0359 
0360 
0361     //BEGIN Optimization 6: Remove writes to a register when the value is ignored and overwritten again
0362     // We go through the instructions looking for statements that write to a register (such as MOVLW).
0363     // If we find any, then we trace through their output links to see if their value is
0364     // overwritten before it is used - and if so, the instruction can be removed.
0365     for ( Code::iterator it = m_pCode->begin(); it != end; ++it )
0366     {
0367         bool noFile = false;
0368 
0369         switch ( (*it)->assemblyType() )
0370         {
0371             case Instruction::WorkingOriented:
0372                 noFile = true;
0373                 // (no break)
0374 
0375             case Instruction::FileOriented:
0376                 break;
0377 
0378             case Instruction::BitOriented:
0379             case Instruction::Other:
0380             case Instruction::None:
0381                 continue;
0382         }
0383 
0384         const Register regSet = noFile ? Register( Register::WORKING ) : (*it)->outputReg();
0385 
0386         if ( regSet.affectsExternal() )
0387             continue;
0388 
0389         ProcessorState inputState = (*it)->inputState();
0390         ProcessorState outputState = (*it)->outputState();
0391         ProcessorBehaviour behaviour = (*it)->behaviour();
0392 
0393         // All ins_file instructions will affect at most two registers; the
0394         // register it is writing to (regSet) and the status register.
0395         // In i==0, test regSet
0396         // In i==1, test STATUS
0397         bool ok = true;
0398         for ( unsigned i = 0; i < 2; ++ i)
0399         {
0400             // If we are testing STATUS, then we assume that the bits changed
0401             // are only those that are marked as independent.
0402             uchar bitmask = ( i == 1 ) ? behaviour.reg( Register::STATUS ).indep : 0xff;
0403             if ( !canRemove( *it, (i == 0) ? regSet : Register::STATUS, bitmask ) )
0404             {
0405                 ok = false;
0406                 break;
0407             }
0408         }
0409 
0410         if ( !ok )
0411             continue;
0412 
0413         // Looks like we're free to remove the instruction :);
0414 //      cout << "Removing: " << (*it)->code() << endl;
0415         it.removeAndIncrement();
0416         return true;
0417     }
0418     m_pCode->setAllUnused();
0419     //END Optimization 6: Remove writes to a register when the value is ignored and overwritten again
0420 
0421     return false;
0422 }
0423 
0424 
0425 bool Optimizer::redirectGotos( Instruction * current, const QString & label )
0426 {
0427     if ( current->isUsed() )
0428         return false;
0429 
0430     current->setUsed( true );
0431 
0432     bool changed = false;
0433 
0434     const InstructionList list = current->inputLinks();
0435     InstructionList::const_iterator end = list.end();
0436     for ( InstructionList::const_iterator it = list.begin(); it != end; ++it )
0437     {
0438         Instr_goto * gotoIns = dynamic_cast<Instr_goto*>(*it);
0439         if ( !gotoIns || (gotoIns->label() == label) )
0440             continue;
0441 
0442 //      cout << "Redirecting goto to label \"" << label << "\" : " << gotoIns->code() << endl;
0443         gotoIns->setLabel( label );
0444         changed = true;
0445     }
0446 
0447     return changed;
0448 }
0449 
0450 
0451 uchar Optimizer::generateRegisterDepends( Instruction * current, const Register & reg )
0452 {
0453     m_pCode->setAllUnused();
0454 
0455     const InstructionList list = current->outputLinks();
0456     InstructionList::const_iterator listEnd = list.end();
0457 
0458     uchar depends = 0x0;
0459 
0460     for ( InstructionList::const_iterator listIt = list.begin(); listIt != listEnd; ++listIt )
0461         depends |= registerDepends( *listIt, reg );
0462 
0463     return depends;
0464 }
0465 
0466 
0467 uchar Optimizer::registerDepends( Instruction * current, const Register & reg )
0468 {
0469     if ( current->isUsed() )
0470         return current->registerDepends( reg );
0471 
0472     current->setUsed( true );
0473 
0474     uchar depends = 0x0;
0475 
0476     const InstructionList list = current->outputLinks();
0477     InstructionList::const_iterator end = list.end();
0478     for ( InstructionList::const_iterator it = list.begin(); it != end; ++it )
0479         depends |= registerDepends( *it, reg );
0480 
0481     RegisterBehaviour behaviour = current->behaviour().reg( reg );
0482     depends &= ~(behaviour.indep); // Get rid of depend bits that are set in this instruction
0483     depends |= behaviour.depends; // And add the ones that are dependent in this instruction
0484 
0485     current->setRegisterDepends( depends, reg );
0486     return depends;
0487 }
0488 
0489 
0490 bool Optimizer::canRemove( Instruction * ins, const Register & reg, uchar bitMask )
0491 {
0492     // The bits that are depended upon in the future for this register
0493     uchar depends = generateRegisterDepends( ins, reg );
0494 
0495     // Only interested in those bits allowed by the bit mask
0496     depends &= bitMask;
0497 
0498     RegisterState inputState = ins->inputState().reg( reg );
0499     RegisterState outputState = ins->outputState().reg( reg );
0500 
0501     if ( inputState.unknown() & depends )
0502     {
0503         // There's at least one bit whose value is depended on, but is not known before this
0504         // instruction is executed. Therefore, it is not safe to remove this instruction.
0505         return false;
0506     }
0507 
0508     if ( outputState.unknown() & depends )
0509     {
0510         // There's at least one bit whose value is depended on, but is not known after this
0511         // instruction is executed. Therefore, it is not safe to remove this instruction.
0512         return false;
0513     }
0514 
0515     uchar dependsInput = inputState.value & depends;
0516     uchar dependsOutput = outputState.value & depends;
0517     if ( dependsInput != dependsOutput )
0518     {
0519         // At least one bit whose value is depended upon was changed.
0520         return false;
0521     }
0522 
0523     return true;
0524 }
0525