Logo Search packages:      
Sourcecode: ktechlab version File versions  Download package

bool Optimizer::optimizeInstructions (  )  [protected]

Perform optimizations (code cropping, modification, assembly, etc) based on instruction linkage and processor states.

Returns:
whether anything was changed

Definition at line 180 of file optimizer.cpp.

References Register::affectsExternal(), Code::begin(), Instruction::BitOriented, canRemove(), RegisterState::definiteOnes(), Code::end(), Instruction::FileOriented, generateRegisterDepends(), RegisterBehaviour::indep, RegisterState::known, Instruction::None, Instruction::Other, Instruction::outputLinks(), redirectGotos(), ProcessorState::reg(), ProcessorBehaviour::reg(), Code::setAllUnused(), ProcessorState::status, RegisterState::value, ProcessorState::working, and Instruction::WorkingOriented.

{
      //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;
}


Generated by  Doxygen 1.6.0   Back to index