BricxCC/NBC test release 2011-07-19

[HaWe]

Matrix test, jch version:

Code: Select all

            // Matrix algebra / arithmetics
// vers. 0.92t (HaWe+jch+splrc version)


#define MatrixMulS(_Out, _A, _s) asm { mul _Out, _A, _s }
#define MatrixDivS(_Out, _A, _s) asm { div _Out, _A, _s }

#define MatrixAdd(_Out, _A, _B) asm { add _Out, _A, _B }
#define MatrixSub(_Out, _A, _B) asm { sub _Out, _A, _B }

#define ArrayIndex(_out, _A, _i)   asm { index _out, _A, _i }
#define ArrayReplace(_A, _i, _new) asm { replace _A, _A, _i, _new }

#define BranchTest(_cmp, _lbl, _v1) asm{ brtst _cmp, _lbl, _v1 }
#define BranchComp(_cmp, _lbl, _v1, _v2) asm{ brcmp _cmp, _lbl, _v1, _v2 }


#define ArrayInit2D(array, tmp, init_val, dimx, dimy) { \
  ArrayInit(tmp, init_val, dimy);  \
  ArrayInit(array, tmp, dimx);     \
  ArrayInit(tmp,0,0);              \
}


void MatrixTransp(float A[][], float &C[][], int R, int S) {
   float tmp[], arr_temp[], val_temp;
   int s, r;
   ArrayInit(tmp, 0, R);
   ArrayInit(C, tmp, S);
   s = S;
   lbl_Trans_start_s:
   {
      s--;
      r = R;
      lbl_Trans_start_r:
      {
         r--;
         ArrayIndex(arr_temp, A, r);
         ArrayIndex(val_temp, arr_temp, s);
         ArrayReplace(tmp, r, val_temp);
      }
      BranchTest(GT, lbl_Trans_start_r, r);
      ArrayReplace(C, s, tmp);
   }
   BranchTest(GT, lbl_Trans_start_s, s);
}

                                               // N x M Matrix  *  M x K Matrix, OLD version
void MatrixMatrixMult_OLD(float A[][], float B[][], float &C[][], int N, int M, int K){
  int i, j, s;

  for (i=0; i<N; ++i) {
    for (j=0; j<K; ++j) {
       C[i][j]=0;
       for (s=0; s<M; ++s) {
         C[i][j]=C[i][j] + A[i][s]*B[s][j];
      }
    }
  }
}

                                               // N x M Matrix  *  M x K Matrix, NEW version
void MatrixMatrixMult(float A[][], float B[][], float &C[][], int N, int M, int K){
   float arr_temp[];
   //Set size of C
   ArrayInit( arr_temp, 0, K );
   ArrayInit( C, arr_temp, N );

lbl_Mult_start_i:   N--;   //Loop start
      //Speed up arrays
      float A_i[];
      float C_i[];
      ArrayIndex(A_i, A, N);
      ArrayIndex(C_i, C, N);

      int j = K;
lbl_Mult_start_j: j--;   //Second loop start
         float sum = 0;

         int s = M;
lbl_Mult_start_s: s--;   //Third loop start

            //sum += A_i[s]*B[s][j];
            float temp, sum_temp;
            ArrayIndex(sum_temp, A_i, s);
            ArrayIndex(arr_temp, B, s);
            ArrayIndex(temp, arr_temp, j);
            sum_temp *= temp;
            sum += sum_temp;
         asm { brtst GT, lbl_Mult_start_s, s }
         ArrayReplace(C_i, j, sum);
      asm { brtst GT, lbl_Mult_start_j, j }
      ArrayReplace(C, N, C_i);
     asm { brtst GT, lbl_Mult_start_i, N }
}



void MatrixRotate2DMath(float A[][], float &C[][], float angleDeg) {
   float tmp[], x, B[][];

   ArrayInit2D(C, tmp, 0, 2, 2);

   x=cosd(angleDeg);
   ArrayInit2D(B, tmp, x, 2, 2);
   x=sind(angleDeg);
   B[0][1]=-x;
   B[1][0]= x;

   MatrixMatrixMult(B, A, C, 2, 2, 2);
}


#define MatrixRotate2DGeo(A,C, d) MatrixRotate2DMath(A,C,-d)



float MatrixDet2x2(float A[][]) {               // Determinante 1x1, 2x2, 3x3
   float r0[], r1[], r2[], v00, v01, v02, v10, v11, v12, v20, v21, v22;

      r0 = A[0];
      r1 = A[1];
      return ( r0[0]*r1[1]- r0[1]*r1[0] );
}


float MatrixDet3x3(float A[][]) {               // Determinante  3x3
   float r0[], r1[], r2[], v00, v01, v02, v10, v11, v12, v20, v21, v22;

      r0 = A[0];
      r1 = A[1];
      r2 = A[2];
      v00 = r0[0]; v01 = r0[1]; v02 = r0[2];
      v10 = r1[0]; v11 = r1[1]; v12 = r1[2];
      v20 = r2[0]; v21 = r2[1]; v22 = r2[2];
      return (v00*v11*v22
             +v01*v12*v20
             +v02*v10*v21
             -v02*v11*v20
             -v01*v10*v22
             -v00*v12*v21);

}


void MatrixAdj2x2 (float A[][], float &C[][]) {  // Adjugate=Adjunkte 1x1, 2x2, 3x3
  float r0[], r1[], r2[], c0[], c1[], c2[], t0, t1, t2;

    ArrayIndex(r0, A, 0);
    ArrayIndex(r1, A, 1);
    ArrayIndex(t0, r1, 1);
    ArrayIndex(t1, r0, 1);
    asm { mul t1, t1, -1 }
    ArrayBuild(c0, t0, t1);
    ArrayIndex(t0, r1, 0);
    asm { mul t0, t0, -1 }
    ArrayIndex(t1, r0, 0);
    ArrayBuild(c1, t0, t1);
    ArrayBuild(C, c0, c1);

}


void MatrixAdj3x3 (float A[][], float &C[][]) {  // Adjugate=Adjunkte 1x1, 2x2, 3x3
  float r0[], r1[], r2[], c0[], c1[], c2[], t0, t1, t2;


    float v00, v01, v02, v10, v11, v12, v20, v21, v22;
    r0 = A[0]; r1 = A[1]; r2 = A[2];
    v00 = r0[0]; v01 = r0[1]; v02 = r0[2];
    v10 = r1[0]; v11 = r1[1]; v12 = r1[2];
    v20 = r2[0]; v21 = r2[1]; v22 = r2[2];

    t0 = v11*v22-v12*v21;
    t1 = v02*v21-v01*v22;
    t2 = v01*v12-v02*v11;
    ArrayBuild(c0, t0, t1, t2);

    t0 = v12*v20-v10*v22;
    t1 = v00*v22-v02*v20;
    t2 = v02*v10-v00*v12;
    ArrayBuild(c1, t0, t1, t2);

    t0 = v10*v21-v11*v20;
    t1 = v01*v20-v00*v21;
    t2 = v00*v11-v01*v10;
    ArrayBuild(c2, t0, t1, t2);

    ArrayBuild(C, c0, c1, c2);

}


bool MatrixInverse2x2(float A[][], float &C[][]) {
   float det;

   det=MatrixDet2x2(A);
   if (det==0) return 0;
   else {
     MatrixAdj2x2(A, C);
     C/=det;
     return 1;
   }
}


bool MatrixInverse3x3(float A[][], float &C[][]) {
   float det;

   det=MatrixDet3x3(A);
   if (det==0) return 0;
   else {
     MatrixAdj3x3(A, C);
     C/=det;
     return 1;
   }
}



void MatrixLinear(float A[][], float &C[], int R, int S) {
  int i=0, s, r;
  int dim=R*S;
  ArrayInit(C, 0, dim);
  for (s=0; s<S; ++s) {
    for (r=0; r<R; ++r) {
      C[i++]=A[r][s];
    }
  }
}


void SubMatrix(float A[][], float &C[][], int RS, int r, int s) {
  int i=0, j=0, x=0, y=0, dim_1;
  float tmp[];

  dim_1=RS-1;
  ArrayInit2D(C, tmp, 0, dim_1, dim_1);

  for (y=0; y<RS; ++y) {
    for (x=0; x<RS; ++x) {
      if ((x!=r)&&(y!=s))   {
         C[i][j]=A[x][y];
         ++i;
         if (i>=dim_1){
           i=0; ++j;
         }
      }
    }
  }
}


float MatrixMinor(float A[][], int RS, int r, int s) {
   float C[][];

   SubMatrix(A, C, RS, r, s);

   if(RS==3) {
     return MatrixDet2x2(C);
   }
   else
   if(RS==4) {
     return MatrixDet3x3(C);
   }
}


float MatrixCofactor(float A[][], int RS, int r, int s) {
   float x;

   return pow(-1, r+s)* MatrixMinor(A, RS, r, s);;
}


float MatrixDet4x4(float A[][])  {
   float det=0, x=0;
   int i, j=0, n0, max0=0, imax0, jmax0=0;

   for (j=0; j<4; ++j) {    // find column with most 0's: jmax0
     n0=0;
     for (i=0; i<4; ++i) {
       if (A[i][j]==0) ++n0;
     }
     if (max0<n0) {max0=n0; jmax0=j;}
   }

   for (i=0; i<4; ++i) {    // find row with most 0's: imax0
     n0=0;
     for (j=0; j<4; ++j) {
       if (A[i][j]==0) ++n0;
     }
     if (max0<n0) {max0=n0; imax0=i;}
   }


   if (jmax0>imax0) {
     for (i=0; i<4; ++i) {         // develop from jmax0
       if ( A[i][jmax0]!=0) {      // 0*?=0
          x=A[i][jmax0]*MatrixCofactor(A, 4, i, jmax0);
          det+=x;
       }
     }
     //TextOut(72,56,"j"); NumOut(80,56,jmax0); //debug
     return det;
   }
   else  {
     for (j=0; j<4; ++j) {         // develop from imax0
       if ( A[imax0][j]!=0) {      // 0*?=0
          x=A[imax0][j]*MatrixCofactor(A, 4, imax0, j);
          det+=x;
       }
     }
     //TextOut(72,56,"i"); NumOut(80,56,imax0); //debug
     return det;
   }
}


// speed test
long time0, runtime;

task main() {

  float A[][], B[][], C[][], x;
  float O[][], T[][], L[][], tmp[];;
  int loop;
  time0=CurrentTick();

 for (loop=0; loop<100; ++loop)
 {
  ArrayInit2D(A, tmp, 0, 2,2);
  ArrayInit2D(B, tmp, 0, 2,2);
  ArrayInit2D(C, tmp, 0, 2,2);

  ArrayInit2D(O, tmp, 0, 4,4);

  NumOut(0,56,loop);

  O[0][0]=0;   O[0][1]=0;   O[0][2]=8;   O[0][3]=22;
  O[1][0]=1;   O[1][1]=5;   O[1][2]=9;   O[1][3]=13;
  O[2][0]=2;   O[2][1]=6;   O[2][2]=10;  O[2][3]=14;
  O[3][0]=3;   O[3][1]=7;   O[3][2]=22;  O[3][3]=15;

  x=MatrixDet4x4(O);

  SubMatrix(O,T,4, 2,1);  // expanded to A[i][j]


  x=MatrixDet3x3(T);


  SubMatrix(T,C,3, 0,1);

  x=MatrixDet2x2(C);


  x=MatrixMinor(T, 3, 0,1);

  x=MatrixCofactor(T, 3, 0,1);


  A[0][0]=1;   A[0][1]=3;
  A[1][0]=2;   A[1][1]=4;

  x=10;
  B=A; B*=x;

  C=A; C+=B;

  MatrixAdj2x2(A,C);

  MatrixInverse2x2(A,C);

  MatrixInverse2x2(A,B);

  MatrixMatrixMult(A,B,C,2,2,2);


  A[0][0]=1;   A[0][1]=1;
  A[1][0]=1;   A[1][1]=0;


  MatrixRotate2DGeo(A,B,30);

  MatrixRotate2DGeo(A,C,90);

 }
 runtime=CurrentTick()-time0;
 TextOut(0,40,"run time");
 NumOut (0,32, runtime);   TextOut(72,32,"msec");


 while(1);
}

// old release 2010702:
// level 0: 9784
// level 1: 8462
// level 2: 7385
// level 3: 7385
// level 4: 7383

// new release 20110720:
// level 0: 9715
// level 1: 8470
// level 2: file error -1
// level 3: file error -1
// level 4: file error -1

the same for new fw, removed code

Code: Select all

#define ArrayIndex(_out, _A, _i)   asm { index _out, _A, _i }
#define ArrayReplace(_A, _i, _new) asm { replace _A, _A, _i, _new }

#define BranchTest(_cmp, _lbl, _v1) asm{ brtst _cmp, _lbl, _v1 }
#define BranchComp(_cmp, _lbl, _v1, _v2) asm{ brcmp _cmp, _lbl, _v1, _v2 }

[HaWe]

As I obeserved, the restauration of the old version 2011-07-07 on my computer was corrupted (different mixed file versions).
The installation of the new version and the related reports were correct.

I reinstalled the 2011-07-02 version completely new to compare with, and it shows that the differences between old and new version are much bigger than assumed before.
In the old BCC version the tamtam and matrix programs run fine on all levels without abort (except once for level 0),
while most of the reported problems are really new and affect specifically the 2011-07-20 release.

The reports are updated in my previous posts.

[afanofosc]

Please could I get someone other than Doc to try out the new test release with your programs? Pretty please?

As I have noted below all of the problems that Doc has mentioned below can be worked around with tweaks to the source code (adding a simple TextOut to the end of the main task or modifying the showtime function slightly to remove a structure from the dataspace). This strongly suggests that the compiler you have right now has the same defect that is causing these problems in the 2011-07-20 test release and it is only good fortune that has kept you from running into it already. I am trying to figure out what it might be but I need more data from other users of NBC/NXC.

John Hansen

[timpattinson]

ok Tomorrow night I'll dig out some of my old programs, to see if they still work , and if not, why

[spillerrec]

I have tested three of my old programs now, sorry for the delay.

Slides:
-Z2: 2.04KB - works
-Z3: 1.92 KB - works

NXTexplorer:
-Z2: 12.8KB - works
-Z3: 12.1KB - one bug

NXT RPG:
-Z2: 30.7KB - works
-Z3: 27.7KB - 2 bugs which prevents me from testing all parts of the program

I will try to debug them to find the issues later. They seem to be related to control structures though, but it is just a guess. Any info about what kind of optimizations it does at level 3 would be greatly appreciated though.
btw, the optimizer is indeed much faster than before : D

[afanofosc]

If you did not get the build from 2011-07-20 then definitely do get that one. The level 3 optimizations in the 07-19 build were definitely doing unsafe things - especially where boolean expressions in if statements were being used. One change in level 2 optimizations is that the code considers array helpers in addition to register and stack variables. Earlier versions did nothing to optimize out array helpers.

The level 3 code looks like this:

Code: Select all

          // at higher optimization levels we'll do more here
          if level >= 3 then
          begin
            // the 0th output argument of this opcode is a temporary variable
            // (aka stack/reg/array helper)
            // so maybe we can do an optimization
            // find the next line (which may not be i+1) that refers to the
            // same temporary variable with no labeled statements
            // or branches in between
            offset := 1;
            tmpIdx := -1;
            while (i < ClumpCode.Count - offset) do begin
              tmpAL := ClumpCode.Items[i+offset];
              tmpIdx := -1;
              tmp := '';
              if tmpAL.LineLabel <> '' then
                Break;
              if (tmpAL.Command in [OP_BRCMP, OP_BRTST, OP_JMP]) then
                Break;
              // does this line refer to the same temporary variable?
              // prefer to find input parameters over finding output parameters
              // so we start at the last arg and work toward the first
              for j := tmpAL.Args.Count - 1 downto 0 do
              begin
                tmp := tmpAL.Args[j].Value;
                if arg1 = RootOf(tmp) then
                begin
                  tmpIdx := j;
                  Break;
                end;
              end;
              if tmpIdx <> -1 then
                Break;
              inc(offset);
            end;
            if (tmpIdx <> -1) and (i < (ClumpCode.Count - offset)) and (arg1 = tmp) then
            begin
              ALNext := ClumpCode.Items[i+offset];
              // now check other cases
              // bricxcc-Bugs-1669679 - make sure the next line
              // cannot be jumped to from elsewhere.  If it does then the
              // "previous" line may actually be skipped so we cannot
              // do any optimization
              if ALNext.LineLabel = '' then
              begin
                // is the next reference to this temporary variable an output
                // or is it an input?
                argDir := ArgDirection(firmVer, ALNext.Command, tmpIdx);
                if argDir = aadOutput then
                begin
                  // if the next line with no labels or branches in between uses this
                  // same temporary as an output variable then the first line
                  // can be replaced with a no-op
                  //
                  // op reg/stack/ah, rest
                  // op reg/stack/ah, rest
                  // nop
                  // op reg/stack/ah, rest
                  AL.RemoveVariableReferences;
                  RemoveOrNOPLine(AL, nil, i);
                  bDone := False;
                  Break;
                end
                else if argDir = aadInput then
                begin
                  if ALNext.Command = OP_MOV then
                  begin
                    // if the next line with no labels or branches in between uses this same
                    // temporary as an input variable and it is a mov then
                    // we may be able to optimize out the mov.
                    //
                    // op reg/stack/ah, rest
                    // mov anything, reg/stack/ah
                    // op anything, rest
                    // nop
                    if IsMovOptimizationSafe(bEnhanced, AL.Command, ALNext.Args[0].Value) then
                    begin
                      AL.RemoveVariableReference(arg1, 0);
                      tmp := ALNext.Args[0].Value;
                      AL.Args[0].Value := tmp; // switch output arg (no ref count changes)
                      ALNext.RemoveVariableReference(arg1, 1);
                      ALNext.Command := OPS_INVALID; // no-op next line
                      ALNext.Args.Clear;
                      // if the variable we moved from ALNext to AL was a stack or array helper
                      // then we have a little extra work to do
                      if IsStack(tmp) or IsArrayHelper(tmp) then
                        FixupPragmas(AL, ALNext, tmp);
                      bDone := False;
                      Break;
                    end;
                  end
                  else if (AL.Command = OP_SET) and ALNext.Optimizable then
                  begin
                    // set reg/stack/ah, constant
                    // op anything, reg/stack/ah
                    // set reg/stack/ah, constant - we might be able to remove/nop this line
                    // op anything, constantvar
                    tmp := CreateConstantVar(CodeSpace.Dataspace, StrToIntDef(AL.Args[1].Value, 0), True);
                    // if the output of set is input of any opcode then it is safe
                    // to set the ALNext's input to AL's input
                    ALNext.RemoveVariableReference(arg1, tmpIdx);
                    ALNext.Args[tmpIdx].Value := tmp; // switch input arg (no ref count changes)
                    // We can't remove the set in case the temporary
                    // is reused as an input in subsequent lines.
                    // This restriction can be removed if we can tell that this
                    // particular temporary is never used as an input from the
                    // time it is acquired to the time it is released.
                    if IsStack(arg1) or IsArrayHelper(arg1) then
                      RemoveLineIfPossible(AL, arg1);
                    bDone := False;
                    Break;
                  end;
                end;
              end;
            end;

          end;

I am not 100% sure these are entirely safe optimizations and I have a slightly modified version that I have not yet checked in which cuts back on this a little. I am going to look at optimizing other types of code patterns, such as the way code is generated for while(true) loops and things like that.

John Hansen

[spillerrec]

I did get that build ; )

EDIT: sorry, nope I didn't. Since my build was newer than the next newest, I assumed I had the correct one... -__-
I didn't notice any bugs in the two programs with the 2011-07-20 release.

EDIT2: I tried another two of my programs (and a few more minor ones), 2 by Muntoo and microMario.nbc. No issues so far...

[afanofosc]

I am glad to hear that not everyone is experiencing weird problems like Doc is. Yeah! I will try to wrap up a new official release over the weekend.

I would like to hear from other NXC users whether they have any problems with level 2 or level 3 optimizations in the 2011-07-20 test release.

John Hansen

[HaWe]

could you erase the compiler bugs always generating "file error -1" just at level 0 (while all other levels are fine, both at old and new versions)?
what was about this issue with new version on level 1 saying "file error -5" although there was no lack of RAM (level 2 was fine) - what was the reason?

[afanofosc]

could you erase the compiler bugs always generating "file error -1" just at level 0 (while all other levels are fine, both at old and new versions)?
what was about this issue with new version on level 1 saying "file error -5" although there was no lack of RAM (level 2 was fine) - what was the reason?

I have no idea at all what's going with your programs. I would encourage you to dig in deep and try to figure out what is going on. My guess is it has something to do with multi-dimensional arrays. I could be totally wrong. If it were a simple bug to find and fix I would have found it and fixed it a long time ago.

The reason for the -5 error was somehow somewhere in your program it ran out of memory. No idea why.

John Hansen