SECTION "CGI"

GET "b.CGheader"

STATIC {
 /* Version of 11 Sep 87 13:41:44
 */
   dummy = VersionMark;
   version = 1*256+7 };

STATIC {
   deferredShift = 0;
   secondOp = 0;
   secondMultiplier = 0;
   thirdMultiplier = 0;
   registerForMultiply = 0 }

LET LowBit(n) = n & (-n)

AND DivByPowerOf2Minus1(n) = VALOF
{  LET t = TABLE	 #x7fffff, #x3fffff, #x1fffff,
		#xfffff,  #x7ffff,  #x3ffff,  #x1ffff,
		 #xffff,   #x7fff,   #x3fff,   #x1fff,
		  #xfff,    #x7ff,    #x3ff,	#x1ff,
		   #xff,     #x7f,     #x3f,	 #x1f,
		    #xf,      #x7,	#x3,	    0;
   LET i = 0;
   LET x = ?;
   {  x := t!i;
      IF x=0 THEN RESULTIS Null;
      IF (n REM x)=0 THEN RESULTIS x
      i := i+1
   } REPEAT
}

AND DivByPowerOf2Plus1(n) = VALOF
{  LET t = TABLE	 #x400001, #x200001, #x100001,
		#x80001,  #x40001,  #x20001,  #x10001,
		 #x8001,   #x4001,   #x2001,   #x1001,
		  #x801,    #x401,    #x201,	#x101,
		   #x81,     #x41,     #x21,	 #x11,
		    #x9,      #x5,	  0;
   LET i = 0;
   LET x = ?
   {  x := t!i;
      IF x=0 THEN RESULTIS Null;
      IF (n REM x)=0 THEN RESULTIS x
      i := i+1
   } REPEAT
}

AND IsPowerOf2(n) = n>0 & LowBit(n)=n

AND IsSimpleMultiply(k) = IsPowerOf2(k) |
			  IsPowerOf2(k+1) |
			  IsPowerOf2(k-1)

AND FindSourceAndDestinationRegisters(lvs, x, mustBeDistinct) = VALOF
{  LET s = IsInARegister(x);
   LET nextop = PeekN();
   LET r = nextop=s.res | nextop=s.fnrn -> 1,
		   1<=argumentNumber<=4 -> ArgumentRegister(argumentNumber),
					  -1;
   argumentNumber := Null;
   TEST s=Null | (h1!x=k.loc & h3!x>=ssp-2) | h1!x=k.reg THEN {
      IF r>0 & mustBeDistinct THEN Lock(r, k.reg);
      s := MoveToAnyR(x); Lock(s, k.reg);
      IF r<0 THEN
	 TEST mustBeDistinct THEN
	    r := NextR()
	 ELSE
	    r := s }
   ELSE {
      TEST r=s & mustBeDistinct THEN {
	 Lock(r, k.reg); s := MoveToAnyR(x) }
      ELSE
	 MoveToR(s, x);
      IF r<0 THEN r := NextR() };
   FlushPendingUsesOfReg(r);
   !lvs := s;
   RESULTIS r
}

AND DoTwoSimpleMultiplies(x, m, n) BE
{  LET s = ?;
   LET r = FindSourceAndDestinationRegisters(@s, x, FALSE);
   registerForMultiply := r;
   SimpleMultiply(r, n, s, FALSE);
   SimpleMultiply(r, m, r, TRUE)
}

AND FRandShiftedR(f, r, s, t, k) BE
   F1Inst(f, r, s, t, 0, sh.asl, LogBase2(k), m.always)

AND MultiplyBySumOrDifferenceOfPowers(f, x, n, k) BE
{  LET s = ?;
   LET r = FindSourceAndDestinationRegisters(@s, x, TRUE);
   registerForMultiply := r;
   SimpleMultiply(r, n, s, FALSE);
   FRandShiftedR(f, r, r, s, k);
   Unlock(s, k.reg)
}


AND TwoInstructionMultiply(k, x) = VALOF
{  LET bottombit = LowBit(k);
   LET n = ?;

   IF bottombit~=1 THEN {
      n := k/bottombit;
      IF IsSimpleMultiply(n) THEN {  // multiplier is 2^n * (2^m+-1)
	 DoTwoSimpleMultiplies(x, bottombit, n);
	 RESULTIS TRUE } };

   n := DivByPowerOf2Minus1(k);
   IF n~=Null THEN
   {  LET m = k/n;
      IF IsSimpleMultiply(m) THEN {  // multiplier is (2^n-1)(2^m+-1)
	 DoTwoSimpleMultiplies(x, n, m);
	 RESULTIS TRUE } };

   n := DivByPowerOf2Plus1(k);
   IF n~=Null THEN {
      LET m = k/n;
      IF IsSimpleMultiply(m) THEN {  // multiplier is (2^n+1)(2^m+1)
	 DoTwoSimpleMultiplies(x, n, m)
	 RESULTIS TRUE } };

   n := IsSumOfPowers(k, 2);
   IF n~=Null THEN {  // multiplier is 2^n+2^m+-1
      // 2^n+2^m is of course detected earlier
      MultiplyBySumOrDifferenceOfPowers(f.add, x, n, k-n);
      RESULTIS TRUE };

   n := IsDifferenceOfPowers(k, 2);
   IF n~=Null THEN {  // multiplier is 2^n-2^m+-1
      MultiplyBySumOrDifferenceOfPowers(f.rsb, x, n, k+n);
      RESULTIS TRUE };

   RESULTIS FALSE
}


AND IsSumOrDifferenceOfPowersOf2(k) = VALOF
{  LET bottombit = LowBit(k);
   LET n = k-bottombit;

   IF IsPowerOf2(n) THEN {
      secondOp := f.add;
      secondMultiplier := bottombit;
      thirdMultiplier := n;
      RESULTIS TRUE };

   n := k+bottombit;
   IF IsPowerOf2(n) THEN {
      secondOp := f.rsb;
      secondMultiplier := bottombit;
      thirdMultiplier := n;
      RESULTIS TRUE };

   RESULTIS FALSE
}

AND IsSumOfPowers(k, p) = VALOF
{  LET n = LowBit(k-1)+1;
   LET m = LowBit(k+1)-1;

   RESULTIS	  IsPowerOf2(k-n) -> n,
		  IsPowerOf2(k-m) -> m,
			      p=2 -> Null,
IsSumOrDifferenceOfPowersOf2(k-n) -> n,
IsSumOrDifferenceOfPowersOf2(k-m) -> m,
				     Null
}

AND IsDifferenceOfPowers(k, p) = VALOF
{  LET n = LowBit(k+1)+1;
   LET m = LowBit(k-1)-1;

   RESULTIS	  IsPowerOf2(k+n) -> n,
		  IsPowerOf2(k+m) -> m,
			      p=2 -> Null,
IsSumOrDifferenceOfPowersOf2(k+n) -> n,
IsSumOrDifferenceOfPowersOf2(k+m) -> m,
				     Null
}

AND SimpleMultiply(res, k, r, deferShift) BE
   TEST IsPowerOf2(k) THEN
      TEST res=r & deferShift THEN
	 deferredShift := sh.asl*32+LogBase2(k)
      ELSE
	 ShiftRegisterDS(res, r, sh.asl, LogBase2(k))
   ELSE TEST IsPowerOf2(k+1)
      THEN FRandShiftedR(f.rsb, res, r, r, k+1)
   ELSE TEST IsPowerOf2(k-1)
      THEN FRandShiftedR(f.add, res, r, r, k-1)
      ELSE CGError(FALSE, "SimpleMultiply wrongly called (k=%n)", k)


AND CGMult() BE
{  LET a, b = arg1, arg2;
   IF Class(arg1, TRUE) < Class(arg2, TRUE) THEN
      a, b := arg2, arg1;
   deferredShift := Null;
   IF IsConst(a) THEN {
      LET k = h3!a;
      LET r = Null;
      TEST k=0 | IsConst(b) THEN {
	 LET k2 = h3!b;
	 Stack(ssp-2);
	 Load(k.number, k*k2);
	 RETURN }

      ELSE TEST k=1 THEN
      {  LET t, ind, n, k = h1!b, h2!b, h3!b, h4!b;
	 Stack(ssp-1);
	 h1!arg1, h2!arg1, h3!arg1, h4!arg1 := t, ind, n, k;
	 RETURN }

      ELSE TEST IsSimpleMultiply(k) THEN {  // multipler is 2^n[+-1]
	 LET s = ?;
	 r := FindSourceAndDestinationRegisters(@s, b, FALSE);
	 SimpleMultiply(r, k, s, TRUE);
	 UnLock(s, k.reg) }

      ELSE TEST TwoInstructionMultiply(k, b) THEN
	 r := registerForMultiply

      ELSE TEST (k&1)=0 & TwoInstructionMultiply(k/LowBit(k), b) THEN {
	 r := registerForMultiply;
	 SimpleMultiply(r, LowBit(k), r, TRUE) }

      ELSE {
	 LET n = DivByPowerOf2minus1(k);
	 IF n~=Null & TwoInstructionMultiply(k/n, b) THEN {
	    r := registerForMultiply;
	    SimpleMultiply(r, n, r, FALSE);
	    GOTO done };

	 n := DivByPowerOf2plus1(k);
	 IF n~=Null & TwoInstructionMultiply(k/n, b) THEN {
	    r := registerForMultiply;
	    SimpleMultiply(r, n, r, FALSE);
	    GOTO done };

	 n := IsSumOfPowers(k, 3);
	 IF n~=Null THEN {
	    LET s = ?;
	    LET r = FindSourceAndDestinationRegisters(@s, b, TRUE);
	    SimpleMultiply(r, n, s, FALSE);
	    FRandShiftedR(secondOp, r, r, s, secondMultiplier)
	    FRandShiftedR(secondOp, r, r, s, thirdMultiplier)
	    Unlock(r, k.reg); Unlock(s, k.reg);
	    GOTO done };

	 n := IsDifferenceOfPowers(k, 3);
	 IF n~=Null THEN {
	    LET s = ?;
	    LET r = FindSourceAndDestinationRegisters(@s, b, TRUE);
	    SimpleMultiply(r, n, s, FALSE);
	    FRandShiftedR((secondOp=f.rsb -> f.add, f.rsb),
			  r, r, s, secondMultiplier)
	    FRandShiftedR(secondOp, r, r, s, thirdMultiplier)
	    Unlock(r, k.reg); Unlock(s, k.reg) } };

done:
      IF r~=Null THEN
      {  LoseR(r, deferredShift);
	 RETURN } };

   {  LET s = ?;
      LET r = FindSourceAndDestinationRegisters(@s, b, FALSE);
      LET r2 = ?;
      FlushPendingUsesOfReg(r);
      Lock(s, k.reg);
      r2 := MoveToAnyCR(a);
      IF r = r2 = s THEN {
	 r2 := NextR();
	 MoveToR(r2, a) };
      IF r=s THEN { LET temp = s; s := r2; r2 := temp };
      MultiplyInst(f.mul, r, s, r2, 0);
      Lose(r, k.reg);
      UnLock(s, k.reg) }
}

AND CallArithmeticRoutine(offset, a1, a2, res) BE
{  MoveToR(ArgumentRegister(1), a1);
   MoveToR(ArgumentRegister(2), a2);
   FlushPendingUsesOfReg(ArgumentRegister(1));
   FlushPendingUsesOfReg(ArgumentRegister(2));
   FlushPendingUsesOfReg(r.14);
   TEST CompactCode THEN
      F5InstL(m.always, (offset=sr.multiply -> MultLab, QuotLab), f.bl)
   ELSE
      CallSub(offset);
   DiscardReg(ArgumentRegister(1), k.reg);
   DiscardReg(ArgumentRegister(2), k.reg);
   DiscardReg(r.14, k.reg);
   Lose(ArgumentRegister(res), k.reg)
}

AND CGMinus() BE
   TEST IsConst(arg1) THEN {
      h3!arg1 := -h3!arg1;
      CGPlus() }
   ELSE {
      LET f, x, y = f.sub, arg1, arg2;
      LET r, s = ?, ?;
      IF Class(x, TRUE) < Class(y, TRUE) THEN
	 f, x, y := f.rsb, arg2, arg1;
      r := FindSourceAndDestinationRegisters(@s, y, FALSE);
      GenFDS(f, r, s, x);
      Lose(r, k.reg);
      UnLock(s, k.reg) }

AND CGPlus() BE
{  IF Isconst(arg2) THEN
      SwapSS(arg1, arg2);

   IF IsConst(arg1) & h1!arg2~=k.shreg THEN
   {  LET k = h3!arg1;
      IF k~=0 THEN
      {  IF h2!arg2>=0 THEN MoveToAnyR(arg2);
	 h4!arg2 := h4!arg2+k };
      IsConst(arg2);
      Stack(ssp-1);
      RETURN };

   {  LET NextOp = PeekN();
      TEST NextOp=s.rv THEN {
	 CGVecap(); RETURN }
      ELSE IF NextOp=s.stind THEN {
	 CGVecSt(); RETURN } };

   {  LET x, y = arg1, arg2;
      LET r, s = ?, ?;
      LET k = 0;
      IF h2!arg1<0 & h1!arg1~=k.shreg THEN {  k := h4!arg1; h4!arg1 := 0 };
      IF h2!arg2<0 & h1!arg2~=k.shreg THEN {  k := k+h4!arg2; h4!arg2 := 0 };
      IF Class(x, TRUE)<Class(y, TRUE)
	 THEN x, y := arg2, arg1;
      r := FindSourceAndDestinationRegisters(@s, y, FALSE);
      GenFDS(f.add, r, s, x);
      Lose(r, k.reg);
      h4!arg1 := k;
      UnLock(s, k.reg) }
}

AND CGDiv() BE
{  IF IsConst(arg1) THEN
   {  LET n = h3!arg1;
      IF n=1 THEN {
	 Stack(ssp-1);
	 RETURN };

      IF n=0 THEN {
	 CGError(FALSE, "Compiling division by zero");
	 Stack(ssp-2);
	 Load(k.number, 0);
	 RETURN };

      IF IsConst(arg2) THEN
      {  LET k = h3!arg2;
	 Stack(ssp-2);
	 Load(k.number, k/n);
	 RETURN };

      IF [n&(-n)]=n THEN
      {  LET s = ?;
	 LET r = FindSourceAndDestinationRegisters(@s, arg2, FALSE);
	 GenRR(f.movs, r, 0, s);
	 TEST n=2 THEN {
	    F1Inst(f.sub, r, s, s, 0, sh.asr, 1, m.mi)
	    F1Inst(f.mov, r, 0, s, 0, sh.asr, 1, m.pl) }
	 ELSE {
	    F1Inst(f.rsb, r, r, Null, 0, Null, 0, m.mi);
	    ShiftRegisterDS(r, r, sh.asr, LogBase2(n));
	    F1Inst(f.rsb, r, r, Null, 0, Null, 0, m.mi) };
	 LoseR(r, Null);
	 UnLock(s, k.reg);
	 RETURN } };

   CallArithmeticRoutine(sr.quotrem, arg2, arg1, 1)
}

AND CGRem() BE
{  IF IsConst(arg1) THEN
   {  LET n = h3!arg1;
      LET lowbit = n & (-n);

      IF n=1 | IsConst(arg2) THEN {
	 LET k = h3!arg2;
	 Stack(ssp-2);
	 Load(k.number, k REM n);
	 RETURN };

      IF n=0 THEN {
	 CGError(FALSE, "Compiling division by zero");
	 Stack(ssp-2);
	 Load(k.number, 0);
	 RETURN };

      IF lowbit=n THEN
      {  LET s = ?;
	 LET r = FindSourceAndDestinationRegisters(@s, arg2, FALSE);
	 h3!arg1 := n-1;
	 CompareAgainstK(s, 0, m.lt);
	 GenFDS(f.and, r, s, arg1);
	 F1Inst(f.sub, r, r, Null, n, Null, 0, m.lt);
	 Lose(r, k.reg);
	 UnLock(s, k.reg);
	 RETURN } };

   CallArithmeticRoutine(sr.quotrem, arg2, arg1, 2)
}
