Changeset 86 for trunk/UBFTarget.pas


Ignore:
Timestamp:
Aug 29, 2017, 5:12:18 PM (7 years ago)
Author:
chronos
Message:
  • Added: New optimization using relative indexes to eliminate lots of pointer inc/dec operations.
  • Added: New command "multiply" extended command to replace while loops used for cell multiplication. Also added related optimization.
File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/UBFTarget.pas

    r80 r86  
    1111
    1212  TMachineCommand = (cmNoOperation, cmInc, cmDec, cmPointerInc, cmPointerDec,
    13     cmOutput, cmInput, cmLoopStart, cmLoopEnd, cmDebug, cmSet);
     13    cmOutput, cmInput, cmLoopStart, cmLoopEnd, cmDebug, cmSet, cmMultipy);
    1414
    1515  TMachineOperation = record
    1616    Command: TMachineCommand;
    1717    Parameter: Integer;
     18    RelIndex: Integer;
    1819  end;
    1920
    … …  
    2829    procedure OptimizeMerge;
    2930    procedure OptimizeZeroInitMemory;
     31    procedure OptimizeRelativeIndexes;
     32    procedure OptimizeCopyMultiply;
    3033  protected
    3134    FProgram: array of TMachineOperation;
    … …  
    261264end;
    262265
     266procedure TBFTarget.OptimizeRelativeIndexes;
     267var
     268  NewProgram: array of TMachineOperation;
     269  NewProgramIndex: Integer;
     270  RelIndex: Integer;
     271begin
     272  NewProgramIndex := 0;
     273  SetLength(NewProgram, Length(FProgram));
     274
     275  RelIndex := 0;
     276  FProgramIndex := 0;
     277  while (FProgramIndex < Length(FProgram)) do begin
     278    case FProgram[FProgramIndex].Command of
     279      cmPointerInc: begin
     280        RelIndex := RelIndex + FProgram[FProgramIndex].Parameter;
     281        Dec(NewProgramIndex);
     282      end;
     283      cmPointerDec: begin
     284        RelIndex := RelIndex - FProgram[FProgramIndex].Parameter;
     285        Dec(NewProgramIndex);
     286      end;
     287      cmInc, cmDec, cmInput, cmOutput, cmSet: begin
     288        NewProgram[NewProgramIndex].Command := FProgram[FProgramIndex].Command;
     289        NewProgram[NewProgramIndex].Parameter := FProgram[FProgramIndex].Parameter;
     290        NewProgram[NewProgramIndex].RelIndex := RelIndex;
     291      end;
     292      cmLoopStart, cmLoopEnd: begin
     293        if RelIndex > 0 then begin
     294          NewProgram[NewProgramIndex].Command := cmPointerInc;
     295          NewProgram[NewProgramIndex].Parameter := RelIndex;
     296          NewProgram[NewProgramIndex].RelIndex := 0;
     297          Inc(NewProgramIndex);
     298          RelIndex := 0;
     299        end else
     300        if RelIndex < 0 then begin
     301          NewProgram[NewProgramIndex].Command := cmPointerDec;
     302          NewProgram[NewProgramIndex].Parameter := Abs(RelIndex);
     303          NewProgram[NewProgramIndex].RelIndex := 0;
     304          Inc(NewProgramIndex);
     305          RelIndex := 0;
     306        end;
     307        NewProgram[NewProgramIndex].Command := FProgram[FProgramIndex].Command;
     308        NewProgram[NewProgramIndex].Parameter := FProgram[FProgramIndex].Parameter;
     309        NewProgram[NewProgramIndex].RelIndex := 0;
     310      end;
     311    end;
     312    DebugSteps.UpdateTargetPos(FProgramIndex, NewProgramIndex);
     313    Inc(FProgramIndex);
     314    Inc(NewProgramIndex);
     315  end;
     316  SetLength(NewProgram, NewProgramIndex);
     317
     318  // Replace old program by new program
     319  SetLength(FProgram, Length(NewProgram));
     320  Move(Pointer(NewProgram)^, Pointer(FProgram)^, SizeOf(TMachineOperation) *
     321    Length(NewProgram));
     322end;
     323
     324procedure TBFTarget.OptimizeCopyMultiply;
     325var
     326  NewProgram: array of TMachineOperation;
     327  NewProgramIndex: Integer;
     328  ProcessLoop: Boolean;
     329  PointerChange: Integer;
     330  NumberOfBaseDecrement: Integer;
     331  LoopStartIndex: Integer;
     332  LoopStartIndexNew: Integer;
     333begin
     334  NewProgramIndex := 0;
     335  SetLength(NewProgram, Length(FProgram));
     336
     337  NumberOfBaseDecrement := 0;
     338  ProcessLoop := False;
     339  FProgramIndex := 0;
     340  PointerChange := 0;
     341  while (FProgramIndex < Length(FProgram)) do begin
     342    case FProgram[FProgramIndex].Command of
     343      cmPointerInc: begin
     344        PointerChange := PointerChange + FProgram[FProgramIndex].Parameter;
     345        NewProgram[NewProgramIndex].Command := FProgram[FProgramIndex].Command;
     346        NewProgram[NewProgramIndex].Parameter := FProgram[FProgramIndex].Parameter;
     347        NewProgram[NewProgramIndex].RelIndex := FProgram[FProgramIndex].RelIndex;
     348      end;
     349      cmPointerDec: begin
     350        PointerChange := PointerChange - FProgram[FProgramIndex].Parameter;
     351        NewProgram[NewProgramIndex].Command := FProgram[FProgramIndex].Command;
     352        NewProgram[NewProgramIndex].Parameter := FProgram[FProgramIndex].Parameter;
     353        NewProgram[NewProgramIndex].RelIndex := FProgram[FProgramIndex].RelIndex;
     354      end;
     355      cmInc: begin
     356        if not ProcessLoop then begin
     357          NewProgram[NewProgramIndex].Command := FProgram[FProgramIndex].Command;
     358          NewProgram[NewProgramIndex].Parameter := FProgram[FProgramIndex].Parameter;
     359          NewProgram[NewProgramIndex].RelIndex := FProgram[FProgramIndex].RelIndex;
     360        end else begin
     361          if ((FProgram[FProgramIndex].RelIndex + PointerChange) <> 0) then begin
     362            NewProgram[NewProgramIndex].Command := cmMultipy;
     363            NewProgram[NewProgramIndex].Parameter := FProgram[FProgramIndex].Parameter;
     364            NewProgram[NewProgramIndex].RelIndex := FProgram[FProgramIndex].RelIndex;
     365          end else Dec(NewProgramIndex);
     366        end;
     367      end;
     368      cmDec: begin
     369        if not ProcessLoop then begin
     370          if (PointerChange = 0) and (FProgram[FProgramIndex].RelIndex = 0) and
     371            (FProgram[FProgramIndex].Parameter = 1) then
     372            Inc(NumberOfBaseDecrement);
     373          NewProgram[NewProgramIndex].Command := FProgram[FProgramIndex].Command;
     374          NewProgram[NewProgramIndex].Parameter := FProgram[FProgramIndex].Parameter;
     375          NewProgram[NewProgramIndex].RelIndex := FProgram[FProgramIndex].RelIndex;
     376        end else begin
     377          if ((FProgram[FProgramIndex].RelIndex + PointerChange) <> 0) then begin
     378            NewProgram[NewProgramIndex].Command := cmMultipy;
     379            NewProgram[NewProgramIndex].Parameter := -FProgram[FProgramIndex].Parameter;
     380            NewProgram[NewProgramIndex].RelIndex := FProgram[FProgramIndex].RelIndex;
     381          end else Dec(NewProgramIndex);
     382        end;
     383      end;
     384      cmInput, cmOutput: begin
     385        NewProgram[NewProgramIndex].Command := FProgram[FProgramIndex].Command;
     386        NewProgram[NewProgramIndex].Parameter := FProgram[FProgramIndex].Parameter;
     387        NewProgram[NewProgramIndex].RelIndex := FProgram[FProgramIndex].RelIndex;
     388        Inc(NumberOfBaseDecrement, 2);
     389      end;
     390      cmSet: begin
     391        NewProgram[NewProgramIndex].Command := FProgram[FProgramIndex].Command;
     392        NewProgram[NewProgramIndex].Parameter := FProgram[FProgramIndex].Parameter;
     393        NewProgram[NewProgramIndex].RelIndex := FProgram[FProgramIndex].RelIndex;
     394        Inc(NumberOfBaseDecrement, 2);
     395      end;
     396      cmLoopStart: begin
     397        if not ProcessLoop then begin
     398          NumberOfBaseDecrement := 0;
     399          PointerChange := 0;
     400          LoopStartIndex := FProgramIndex;
     401          LoopStartIndexNew := NewProgramIndex;
     402          NewProgram[NewProgramIndex].Command := FProgram[FProgramIndex].Command;
     403          NewProgram[NewProgramIndex].Parameter := FProgram[FProgramIndex].Parameter;
     404          NewProgram[NewProgramIndex].RelIndex := FProgram[FProgramIndex].RelIndex;
     405        end else begin
     406          Dec(NewProgramIndex);
     407        end;
     408      end;
     409      cmLoopEnd: begin
     410        if not ProcessLoop then begin
     411          if (NumberOfBaseDecrement = 1) and (PointerChange = 0) then begin
     412            FProgramIndex := LoopstartIndex - 1;
     413            NewProgramIndex := LoopStartIndexNew - 1;
     414            ProcessLoop := True;
     415          end else begin
     416            NewProgram[NewProgramIndex].Command := FProgram[FProgramIndex].Command;
     417            NewProgram[NewProgramIndex].Parameter := FProgram[FProgramIndex].Parameter;
     418            NewProgram[NewProgramIndex].RelIndex := FProgram[FProgramIndex].RelIndex;
     419          end;
     420        end else begin
     421          NewProgram[NewProgramIndex].Command := cmSet;
     422          NewProgram[NewProgramIndex].Parameter := 0;
     423          NewProgram[NewProgramIndex].RelIndex := 0;
     424          ProcessLoop := False;
     425        end;
     426      end;
     427    end;
     428    DebugSteps.UpdateTargetPos(FProgramIndex, NewProgramIndex);
     429    Inc(FProgramIndex);
     430    Inc(NewProgramIndex);
     431  end;
     432  SetLength(NewProgram, NewProgramIndex);
     433
     434  // Replace old program by new program
     435  SetLength(FProgram, Length(NewProgram));
     436  Move(Pointer(NewProgram)^, Pointer(FProgram)^, SizeOf(TMachineOperation) *
     437    Length(NewProgram));
     438end;
     439
    263440procedure TBFTarget.LoadProgram;
    264441var
    … …  
    274451        FProgram[FProgramIndex].Command := cmInc;
    275452        FProgram[FProgramIndex].Parameter := 1;
     453        FProgram[FProgramIndex].RelIndex := 0;
    276454        DebugSteps.AddStep(I - 1, FProgramIndex, soNormal);
    277455      end;
    … …  
    279457        FProgram[FProgramIndex].Command := cmDec;
    280458        FProgram[FProgramIndex].Parameter := 1;
     459        FProgram[FProgramIndex].RelIndex := 0;
    281460        DebugSteps.AddStep(I - 1, FProgramIndex, soNormal);
    282461      end;
    … …  
    284463        FProgram[FProgramIndex].Command := cmPointerInc;
    285464        FProgram[FProgramIndex].Parameter := 1;
     465        FProgram[FProgramIndex].RelIndex := 0;
    286466        DebugSteps.AddStep(I - 1, FProgramIndex, soNormal);
    287467      end;
    … …  
    289469        FProgram[FProgramIndex].Command := cmPointerDec;
    290470        FProgram[FProgramIndex].Parameter := 1;
     471        FProgram[FProgramIndex].RelIndex := 0;
    291472        DebugSteps.AddStep(I - 1, FProgramIndex, soNormal);
    292473      end;
    … …  
    294475        FProgram[FProgramIndex].Command := cmInput;
    295476        FProgram[FProgramIndex].Parameter := 0;
     477        FProgram[FProgramIndex].RelIndex := 0;
    296478        DebugSteps.AddStep(I - 1, FProgramIndex, soNormal);
    297479      end;
    … …  
    299481        FProgram[FProgramIndex].Command := cmOutput;
    300482        FProgram[FProgramIndex].Parameter := 0;
     483        FProgram[FProgramIndex].RelIndex := 0;
    301484        DebugSteps.AddStep(I - 1, FProgramIndex, soNormal);
    302485      end;
    … …  
    304487        FProgram[FProgramIndex].Command := cmLoopStart;
    305488        FProgram[FProgramIndex].Parameter := 0;
     489        FProgram[FProgramIndex].RelIndex := 0;
    306490        DebugSteps.AddStep(I - 1, FProgramIndex, soStepIn);
    307491      end;
    … …  
    309493        FProgram[FProgramIndex].Command := cmLoopEnd;
    310494        FProgram[FProgramIndex].Parameter := 0;
     495        FProgram[FProgramIndex].RelIndex := 0;
    311496        DebugSteps.AddStep(I - 1, FProgramIndex, soStepOut);
    312497      end
    … …  
    336521  until Length(FProgram) = OldLength;
    337522  OptimizeZeroInitMemory;
     523  OptimizeRelativeIndexes;
     524  OptimizeCopyMultiply;
    338525end;
    339526
Note: See TracChangeset for help on using the changeset viewer.