File indexing completed on 2024-03-24 05:46:08
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