Refactor bigint _sqrTo in preparation of intrinsification.

runtime/vm/intrinsifier_ia32.cc

 // Copyright (c) 2013, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 //
 // The intrinsic code below is executed before a method has built its frame.
 // The return address is on the stack and the arguments below it.
 // Registers EDX (arguments descriptor) and ECX (function) must be preserved.
 // Each intrinsification method returns true if the corresponding
 // Dart method was intrinsified.
 
@@ skipping 909 matching lines @@
   //                     Uint32List m_digits, int i,
   //                     Uint32List a_digits, int j, int n) {
   //   uint32_t x = args[MA_MULTIPLIER];
   //   if (x == 0) {
   //     args[MA_CARRY_OUT] = 0;
   //     return;
   //   }
   //   uint32_t* mip = &m_digits[i >> 1];  // i is Smi.
   //   uint32_t* ajp = &a_digits[j >> 1];  // j is Smi.
   //   uint32_t c = 0;
-  //   while ((n -= 2) >= 0) {  // n is Smi.
+  //   SmiUntag(n);
+  //   while (--n >= 0) {
   //     uint32_t mi = *mip++;
   //     uint32_t aj = *ajp;
   //     uint64_t t = x*mi + aj + c;  // 32-bit * 32-bit -> 64-bit.
   //     *ajp++ = low32(t);
   //     c = high32(t);
   //   }
   //   args[MA_CARRY_OUT] = c;
   // }
 
-  // TODO(regis): Confirm that it is not required to check arguments (and also
-  // convince invocation_fuzz_test).
-
   // EBX = x
   Label x_not_zero;
   __ movl(ECX, Address(ESP, 6 * kWordSize));  // args
   __ movl(EBX, FieldAddress(ECX, TypedData::data_offset()));  // x
   __ cmpl(EBX, Immediate(0));
   __ j(NOT_EQUAL, &x_not_zero, Assembler::kNearJump);
   // Set args[MA_CARRY_OUT] to 0 and return.
   __ movl(FieldAddress(ECX, TypedData::data_offset() + kWordSize), EBX);
   // TODO(regis): Confirm that returning Object::null() is not required.
   __ ret();
   __ Bind(&x_not_zero);
 
   // Preserve CTX to free ESI.
   __ pushl(CTX);
   ASSERT(CTX == ESI);
 
   // EDI = mip = &m_digits[i >> 1]
   __ movl(EDI, Address(ESP, 6 * kWordSize));  // m_digits
   __ movl(EAX, Address(ESP, 5 * kWordSize));  // i is Smi
   __ leal(EDI, FieldAddress(EDI, EAX, TIMES_2, TypedData::data_offset()));
 
   // ESI = ajp = &a_digits[j >> 1]
   __ movl(ESI, Address(ESP, 4 * kWordSize));  // a_digits
   __ movl(EAX, Address(ESP, 3 * kWordSize));  // j is Smi
   __ leal(ESI, FieldAddress(ESI, EAX, TIMES_2, TypedData::data_offset()));
 
   // ECX = c = 0
   __ xorl(ECX, ECX);
 

[srdjan, 2014/09/24 00:19:28]

You could define:
Address n_addr = Address(ESP, 2 * kWordSize)

and use it on various places below

[regis, 2014/09/24 01:50:49]

Done.
And it may not be such a good idea to untag n above the stack pointer (not
sure). I pushed an untagged copy as a local.

+  // SmiUntag(n), 'sar mem32, 1' not implemented
+  __ movl(EAX, Address(ESP, 2 * kWordSize));
+  __ SmiUntag(EAX);
+  __ movl(Address(ESP, 2 * kWordSize), EAX);
+
   Label loop, done;
   __ Bind(&loop);
   // x:   EBX
   // mip: EDI
   // ajp: ESI
   // c:   ECX
   // t:   EDX:EAX (not live at loop entry)
+  // n:   ESP[2]
 
-  // while ((n -= 2) >= 0), n is on stack, above ret addr and saved CTX.
-  __ movl(EAX, Immediate(2));  // 'sub mem32, imm32' not implemented.
-  __ subl(Address(ESP, 2 * kWordSize), EAX);  // --n, n is Smi.
+  // while (--n >= 0)
+  __ decl(Address(ESP, 2 * kWordSize));  // --n
   __ j(NEGATIVE, &done);
 
   // uint32_t mi = *mip++
   __ movl(EAX, Address(EDI, 0));
   __ addl(EDI, Immediate(kWordSize));
 
   // uint64_t t = x*mi
   __ mull(EBX);  // t = EDX:EAX = EAX * EBX
   __ addl(EAX, ECX);  // t += c
   __ adcl(EDX, Immediate(0));
@@ skipping 13 matching lines @@
   __ Bind(&done);
   // Restore CTX, set args[MA_CARRY_OUT] to c and return.
   __ popl(CTX);
   __ movl(EAX, Address(ESP, 6 * kWordSize));  // args
   __ movl(FieldAddress(EAX, TypedData::data_offset() + kWordSize), ECX);
   // TODO(regis): Confirm that returning Object::null() is not required.
   __ ret();
 }
 
 
+// TODO(regis): Once this intrinsic is implemented on all architectures, the
+// corresponding Dart method will be untested. Add a test with --no-intrinsify.
+void Intrinsifier::Bigint_sqrAdd(Assembler* assembler) {
+  // Pseudo code:
+  // static void _sqrAdd(Uint32List x_digits, int i,
+  //                     Uint32List a_digits, int used) {
+  //   uint32_t* xip = &x_digits[i >> 1];  // i is Smi.
+  //   uint32_t x = *xip++;
+  //   if (x == 0) return;
+  //   uint32_t* ajp = &a_digits[i];  // j == 2*i, i is Smi.
+  //   uint32_t aj = *ajp;
+  //   uint64_t t = x*x + aj;
+  //   *ajp++ = low32(t);
+  //   uint64_t c = high32(t);
+  //   int n = ((used - i) >> 1) - 1;  // used and i are Smi.
+  //   while (--n >= 0) {
+  //     uint32_t xi = *xip++;
+  //     uint32_t aj = *ajp;
+  //     uint96_t t = 2*x*xi + aj + c;  // 2-bit * 32-bit * 32-bit -> 65-bit.
+  //     *ajp++ = low32(t);
+  //     c = high64(t);  // 33-bit.
+  //   }
+  //   uint32_t aj = *ajp;
+  //   uint64_t t = aj + c;  // 32-bit + 33-bit -> 34-bit.
+  //   *ajp++ = low32(t);
+  //   *ajp = high32(t);
+
+  // EDI = xip = &x_digits[i >> 1]
+  __ movl(EDI, Address(ESP, 4 * kWordSize));  // m_digits
+  __ movl(EAX, Address(ESP, 3 * kWordSize));  // i is Smi
+  __ leal(EDI, FieldAddress(EDI, EAX, TIMES_2, TypedData::data_offset()));
+
+  // EBX = x = *xip++, return if x == 0
+  Label x_not_zero;
+  __ movl(EBX, Address(EDI, 0));
+  __ cmpl(EBX, Immediate(0));
+  __ j(NOT_EQUAL, &x_not_zero, Assembler::kNearJump);

[srdjan, 2014/09/24 00:19:28]

You could jump if equal 0 to a label just before the last ret in the code.

[regis, 2014/09/24 01:50:49]

Done.

+  // TODO(regis): Confirm that returning Object::null() is not required.
+  __ ret();
+  __ Bind(&x_not_zero);
+  __ addl(EDI, Immediate(kWordSize));
+
+  // Preserve CTX to free ESI.
+  __ pushl(CTX);
+  ASSERT(CTX == ESI);
+
+  // ESI = ajp = &a_digits[i]
+  __ movl(ESI, Address(ESP, 3 * kWordSize));  // a_digits
+  __ leal(ESI, FieldAddress(ESI, EAX, TIMES_4, TypedData::data_offset()));
+
+  // EAX:EDX = t = x*x + *ajp
+  __ movl(EAX, EBX);
+  __ mull(EBX);
+  __ addl(EAX, Address(ESI, 0));
+  __ adcl(EDX, Immediate(0));
+
+  // *ajp++ = low32(t)
+  __ movl(Address(ESI, 0), EAX);
+  __ addl(ESI, Immediate(kWordSize));
+
+  // int n = used - i - 1;  // All Smi.
+  __ movl(EAX, Address(ESP, 2 * kWordSize));  // used is Smi
+  __ subl(EAX, Address(ESP, 4 * kWordSize));  // i is Smi
+  __ SmiUntag(EAX);
+  __ decl(EAX);
+  __ pushl(EAX);  // Save n on stack.
+
+  // uint64_t c = high32(t)
+  __ pushl(Immediate(0));  // push high32(c) == 0
+  __ pushl(EDX);  // push low32(c) == high32(t)
+
+  Label loop, done;
+  __ Bind(&loop);
+  // x:   EBX
+  // xip: EDI
+  // ajp: ESI
+  // c:   ESP[1]:ESP[0]
+  // t:   ECX:EDX:EAX (not live at loop entry)
+  // n:   ESP[2]
+
+  // while (--n >= 0)
+  __ decl(Address(ESP, 2 * kWordSize));  // --n
+  __ j(NEGATIVE, &done);
+
+  // uint32_t xi = *xip++
+  __ movl(EAX, Address(EDI, 0));
+  __ addl(EDI, Immediate(kWordSize));
+
+  // uint96_t t = ECX:EDX:EAX = 2*x*xi + aj + c
+  __ mull(EBX);  // EDX:EAX = EAX * EBX
+  __ xorl(ECX, ECX);  // ECX = 0
+  __ shld(ECX, EDX, Immediate(1));
+  __ shld(EDX, EAX, Immediate(1));
+  __ shll(EAX, Immediate(1));  // ECX:EDX:EAX <<= 1
+  __ addl(EAX, Address(ESI, 0));  // t += aj
+  __ adcl(EDX, Immediate(0));
+  __ adcl(ECX, Immediate(0));
+  __ addl(EAX, Address(ESP, 0 * kWordSize));  // t += low32(c)
+  __ adcl(EDX, Address(ESP, 1 * kWordSize));  // t += high32(c) << 32
+  __ adcl(ECX, Immediate(0));
+
+  // *ajp++ = low32(t)
+  __ movl(Address(ESI, 0), EAX);
+  __ addl(ESI, Immediate(kWordSize));
+
+  // c = high64(t)
+  __ movl(Address(ESP, 0 * kWordSize), EDX);
+  __ movl(Address(ESP, 1 * kWordSize), ECX);
+
+  __ jmp(&loop, Assembler::kNearJump);
+
+  __ Bind(&done);
+  // uint32_t aj = *ajp;
+  __ movl(EAX, Address(ESI, 0));
+
+  // uint64_t t = aj + c;  // 32-bit + 33-bit -> 34-bit.
+  __ movl(EAX, Address(ESP, 0 * kWordSize));  // t = c
+  __ movl(EDX, Address(ESP, 1 * kWordSize));
+  __ addl(EAX, Address(ESI, 0));  // t += aj
+  __ adcl(EDX, Immediate(0));
+
+  // *ajp++ = low32(t);
+  __ movl(Address(ESI, 0), EAX);
+  __ addl(ESI, Immediate(kWordSize));
+
+  // *ajp = high32(t);
+  __ movl(Address(ESI, 0), EDX);
+
+  // Restore CTX and return.
+  __ Drop(3);
+  __ popl(CTX);
+  // TODO(regis): Confirm that returning Object::null() is not required.
+  __ ret();
+}
+
+
 // Check if the last argument is a double, jump to label 'is_smi' if smi
 // (easy to convert to double), otherwise jump to label 'not_double_smi',
 // Returns the last argument in EAX.
 static void TestLastArgumentIsDouble(Assembler* assembler,
                                      Label* is_smi,
                                      Label* not_double_smi) {
   __ movl(EAX, Address(ESP, + 1 * kWordSize));
   __ testl(EAX, Immediate(kSmiTagMask));
   __ j(ZERO, is_smi, Assembler::kNearJump);  // Jump if Smi.
   __ CompareClassId(EAX, kDoubleCid, EBX);
@@ skipping 715 matching lines @@
                         Isolate::current_tag_offset());
   // Set return value to Isolate::current_tag_.
   __ movl(EAX, current_tag_addr);
   __ ret();
 }
 
 #undef __
 }  // namespace dart
 
 #endif  // defined TARGET_ARCH_IA32