< prev index next >

## src/cpu/x86/vm/macroAssembler_x86.cpp

Print this page

    @@ -7717,10 +7717,508 @@
       pop(tmp4);
       pop(tmp3);
       pop(tmp2);
       pop(tmp1);
     }
    +
    +//Helper functions for square_to_len()
    +
    +/**
    + * Store the squares of x[], right shifted one bit (divided by 2) into z[]
    + * Preserves x and z and modifies rest of the registers.
    + */
    +
    +void MacroAssembler::square_rshift(Register x, Register xlen, Register z, Register tmp1, Register tmp3, Register tmp4, Register tmp5, Register rdxReg, Register raxReg) {
    +  // Perform square and right shift by 1
    +  // Handle odd xlen case first, then for even xlen do the following
    +  // jlong carry = 0;
    +  // for (int j=0, i=0; j < xlen; j+=2, i+=4) {
    +  //     huge_128 product = x[j:j+1] * x[j:j+1];
    +  //     z[i:i+1] = (carry << 63) | (jlong)(product >>> 65);
    +  //     z[i+2:i+3] = (jlong)(product >>> 1);
    +  //     carry = (jlong)product;
    +  // }
    +
    +  xorq(tmp5, tmp5);     // carry
    +  xorq(rdxReg, rdxReg);
    +  xorl(tmp1, tmp1);     // index for x
    +  xorl(tmp4, tmp4);     // index for z
    +
    +  Label L_first_loop, L_first_loop_exit;
    +
    +  testl(xlen, 1);
    +  jcc(Assembler::zero, L_first_loop); //jump if xlen is even
    +
    +  // Square and right shift by 1 the odd element using 32 bit multiply
    +  movl(raxReg, Address(x, tmp1, Address::times_4, 0));
    +  imulq(raxReg, raxReg);
    +  shrq(raxReg, 1);
    +  adcq(tmp5, 0);
    +  movq(Address(z, tmp4, Address::times_4, 0), raxReg);
    +  incrementl(tmp1);
    +  addl(tmp4, 2);
    +
    +  // Square and  right shift by 1 the rest using 64 bit multiply
    +  bind(L_first_loop);
    +  cmpptr(tmp1, xlen);
    +  jcc(Assembler::equal, L_first_loop_exit);
    +
    +  // Square
    +  movq(raxReg, Address(x, tmp1, Address::times_4,  0));
    +  rorq(raxReg, 32);    // convert big-endian to little-endian
    +  mulq(raxReg);        // 64-bit multiply rax * rax -> rdx:rax
    +
    +  // Right shift by 1 and save carry
    +  shrq(tmp5, 1);       // rdx:rax:tmp5 = (tmp5:rdx:rax) >>> 1
    +  rcrq(rdxReg, 1);
    +  rcrq(raxReg, 1);
    +  adcq(tmp5, 0);
    +
    +  // Store result in z
    +  movq(Address(z, tmp4, Address::times_4, 0), rdxReg);
    +  movq(Address(z, tmp4, Address::times_4, 8), raxReg);
    +
    +  // Update indices for x and z
    +  addl(tmp1, 2);
    +  addl(tmp4, 4);
    +  jmp(L_first_loop);
    +
    +  bind(L_first_loop_exit);
    +}
    +
    +
    +/**
    + * Perform the following multiply add operation using BMI2 instructions
    + * carry:sum = sum + op1*op2 + carry
    + * op2 should be in rdx
    + * op2 is preserved, all other registers are modified
    + */
    +void MacroAssembler::multiply_add_64_bmi2(Register sum, Register op1, Register op2, Register carry, Register tmp2) {
    +  // assert op2 is rdx
    +  mulxq(tmp2, op1, op1);  //  op1 * op2 -> tmp2:op1
    +  addq(sum, carry);
    +  adcq(tmp2, 0);
    +  addq(sum, op1);
    +  adcq(tmp2, 0);
    +  movq(carry, tmp2);
    +}
    +
    +/**
    + * Perform the following multiply add operation:
    + * carry:sum = sum + op1*op2 + carry
    + * Preserves op1, op2 and modifies rest of registers
    + */
    +void MacroAssembler::multiply_add_64(Register sum, Register op1, Register op2, Register carry, Register rdxReg, Register raxReg) {
    +  // rdx:rax = op1 * op2
    +  movq(raxReg, op2);
    +  mulq(op1);
    +
    +  //  rdx:rax = sum + carry + rdx:rax
    +  addq(sum, carry);
    +  adcq(rdxReg, 0);
    +  addq(sum, raxReg);
    +  adcq(rdxReg, 0);
    +
    +  // carry:sum = rdx:sum
    +  movq(carry, rdxReg);
    +}
    +
    +/**
    + * Add 64 bit long carry into z[] with carry propogation.
    + * Preserves z and carry register values and modifies rest of registers.
    + *
    + */
    +void MacroAssembler::add_one_64(Register z, Register zlen, Register carry, Register tmp1) {
    +  Label L_fourth_loop, L_fourth_loop_exit;
    +
    +  movl(tmp1, 1);
    +  subl(zlen, 2);
    +  addq(Address(z, zlen, Address::times_4, 0), carry);
    +
    +  bind(L_fourth_loop);
    +  jcc(Assembler::carryClear, L_fourth_loop_exit);
    +  subl(zlen, 2);
    +  jcc(Assembler::negative, L_fourth_loop_exit);
    +  addq(Address(z, zlen, Address::times_4, 0), tmp1);
    +  jmp(L_fourth_loop);
    +  bind(L_fourth_loop_exit);
    +}
    +
    +/**
    + * Shift z[] left by 1 bit.
    + * Preserves x, len, z and zlen registers and modifies rest of the registers.
    + *
    + */
    +void MacroAssembler::lshift_by_1(Register x, Register len, Register z, Register zlen, Register tmp1, Register tmp2, Register tmp3, Register tmp4) {
    +
    +  Label L_fifth_loop, L_fifth_loop_exit;
    +
    +  // Fifth loop
    +  // Perform primitiveLeftShift(z, zlen, 1)
    +
    +  const Register prev_carry = tmp1;
    +  const Register new_carry = tmp4;
    +  const Register value = tmp2;
    +  const Register zidx = tmp3;
    +
    +  // int zidx, carry;
    +  // long value;
    +  // carry = 0;
    +  // for (zidx = zlen-2; zidx >=0; zidx -= 2) {
    +  //    (carry:value)  = (z[i] << 1) | carry ;
    +  //    z[i] = value;
    +  // }
    +
    +  movl(zidx, zlen);
    +  xorl(prev_carry, prev_carry); // clear carry flag and prev_carry register
    +
    +  bind(L_fifth_loop);
    +  decl(zidx);  // Use decl to preserve carry flag
    +  decl(zidx);
    +  jcc(Assembler::negative, L_fifth_loop_exit);
    +
    +  if (UseBMI2Instructions) {
    +     movq(value, Address(z, zidx, Address::times_4, 0));
    +     rclq(value, 1);
    +     rorxq(value, value, 32);
    +     movq(Address(z, zidx, Address::times_4,  0), value);  // Store back in big endian form
    +  }
    +  else {
    +    // clear new_carry
    +    xorl(new_carry, new_carry);
    +
    +    // Shift z[i] by 1, or in previous carry and save new carry
    +    movq(value, Address(z, zidx, Address::times_4, 0));
    +    shlq(value, 1);
    +    adcl(new_carry, 0);
    +
    +    orq(value, prev_carry);
    +    rorq(value, 0x20);
    +    movq(Address(z, zidx, Address::times_4,  0), value);  // Store back in big endian form
    +
    +    // Set previous carry = new carry
    +    movl(prev_carry, new_carry);
    +  }
    +  jmp(L_fifth_loop);
    +
    +  bind(L_fifth_loop_exit);
    +}
    +
    +
    +/**
    + * Code for BigInteger::squareToLen() intrinsic
    + *
    + * rdi: x
    + * rsi: len
    + * r8:  z
    + * rcx: zlen
    + * r12: tmp1
    + * r13: tmp2
    + * r14: tmp3
    + * r15: tmp4
    + * rbx: tmp5
    + *
    + */
    +void MacroAssembler::square_to_len(Register x, Register len, Register z, Register zlen, Register tmp1, Register tmp2, Register tmp3, Register tmp4, Register tmp5, Register rdxReg, Register raxReg) {
    +
    +  Label L_second_loop, L_second_loop_exit, L_third_loop, L_third_loop_exit, fifth_loop, fifth_loop_exit, L_last_x, L_multiply;
    +  push(tmp1);
    +  push(tmp2);
    +  push(tmp3);
    +  push(tmp4);
    +  push(tmp5);
    +
    +  // First loop
    +  // Store the squares, right shifted one bit (i.e., divided by 2).
    +  square_rshift(x, len, z, tmp1, tmp3, tmp4, tmp5, rdxReg, raxReg);
    +
    +  // Add in off-diagonal sums.
    +  //
    +  // Second, third (nested) and fourth loops.
    +  // zlen +=2;
    +  // for (int xidx=len-2,zidx=zlen-4; xidx > 0; xidx-=2,zidx-=4) {
    +  //    carry = 0;
    +  //    long op2 = x[xidx:xidx+1];
    +  //    for (int j=xidx-2,k=zidx; j >= 0; j-=2) {
    +  //       k -= 2;
    +  //       long op1 = x[j:j+1];
    +  //       long sum = z[k:k+1];
    +  //       carry:sum = multiply_add_64(sum, op1, op2, carry, tmp_regs);
    +  //       z[k:k+1] = sum;
    +  //    }
    +  //    add_one_64(z, k, carry, tmp_regs);
    +  // }
    +
    +
    +  const Register carry = tmp5;
    +  const Register sum = tmp3;
    +  const Register op1 = tmp4;
    +  Register op2 = tmp2;
    +
    +  push(zlen);
    +  push(len);
    +  addl(zlen,2);
    +  bind(L_second_loop);
    +  xorq(carry, carry);
    +  subl(zlen, 4);
    +  subl(len, 2);
    +  push(zlen);
    +  push(len);
    +  cmpl(len, 0);
    +  jcc(Assembler::lessEqual, L_second_loop_exit);
    +
    +  // Multiply an array by one 64 bit long.
    +  if (UseBMI2Instructions) {
    +    op2 = rdxReg;
    +    movq(op2, Address(x, len, Address::times_4,  0));
    +    rorxq(op2, op2, 32);
    +  }
    +  else {
    +    movq(op2, Address(x, len, Address::times_4,  0));
    +    rorq(op2, 32);
    +  }
    +
    +  bind(L_third_loop);
    +  decrementl(len);
    +  jcc(Assembler::negative, L_third_loop_exit);
    +  decrementl(len);
    +  jcc(Assembler::negative, L_last_x);
    +
    +  movq(op1, Address(x, len, Address::times_4,  0));
    +  rorq(op1, 32);
    +
    +  bind(L_multiply);
    +  subl(zlen, 2);
    +  movq(sum, Address(z, zlen, Address::times_4,  0));
    +
    +  // Multiply 64 bit by 64 bit and add 64 bits lower half and upper 64 bits as carry.
    +  if (UseBMI2Instructions) {
    +    multiply_add_64_bmi2(sum, op1, op2, carry, tmp2);
    +  }
    +  else {
    +    multiply_add_64(sum, op1, op2, carry, rdxReg, raxReg);
    +  }
    +
    +  movq(Address(z, zlen, Address::times_4, 0), sum);
    +
    +  jmp(L_third_loop);
    +  bind(L_third_loop_exit);
    +
    +  // Fourth loop
    +  // Add 64 bit long carry into z with carry propogation.
    +  // Uses offsetted zlen.
    +  add_one_64(z, zlen, carry, tmp1);
    +
    +  pop(len);
    +  pop(zlen);
    +  jmp(L_second_loop);
    +
    +  // Next infrequent code is moved outside loops.
    +  bind(L_last_x);
    +  movl(op1, Address(x, 0));
    +  jmp(L_multiply);
    +
    +  bind(L_second_loop_exit);
    +  pop(len);
    +  pop(zlen);
    +  pop(len);
    +  pop(zlen);
    +
    +  // Fifth loop
    +  // Shift z left 1 bit.
    +  lshift_by_1(x, len, z, zlen, tmp1, tmp2, tmp3, tmp4);
    +
    +  // z[zlen-1] |= x[len-1] & 1;
    +  movl(tmp3, Address(x, len, Address::times_4, -4));
    +  andl(tmp3, 1);
    +  orl(Address(z, zlen, Address::times_4,  -4), tmp3);
    +
    +  pop(tmp5);
    +  pop(tmp4);
    +  pop(tmp3);
    +  pop(tmp2);
    +  pop(tmp1);
    +}
    +
    +/**
    + * Helper function for mul_add()
    + * Multiply the in[] by int k and add to out[] starting at offset offs using
    + * 128 bit by 32 bit multiply and return the carry in tmp5.
    + * Only quad int aligned length of in[] is operated on in this function.
    + * k is in rdxReg for BMI2Instructions, for others it is in tmp2.
    + * This function preserves out, in and k registers.
    + * len and offset point to the appropriate index in "in" & "out" correspondingly
    + * tmp5 has the carry.
    + * other registers are temporary and are modified.
    + *
    + */
    +void MacroAssembler::mul_add_128_x_32_loop(Register out, Register in,
    +  Register offset, Register len, Register tmp1, Register tmp2, Register tmp3,
    +  Register tmp4, Register tmp5, Register rdxReg, Register raxReg) {
    +
    +  Label L_first_loop, L_first_loop_exit;
    +
    +  movl(tmp1, len);
    +  shrl(tmp1, 2);
    +
    +  bind(L_first_loop);
    +  subl(tmp1, 1);
    +  jcc(Assembler::negative, L_first_loop_exit);
    +
    +  subl(len, 4);
    +  subl(offset, 4);
    +
    +  Register op2 = tmp2;
    +  const Register sum = tmp3;
    +  const Register op1 = tmp4;
    +  const Register carry = tmp5;
    +
    +  if (UseBMI2Instructions) {
    +    op2 = rdxReg;
    +  }
    +
    +  movq(op1, Address(in, len, Address::times_4,  8));
    +  rorq(op1, 32);
    +  movq(sum, Address(out, offset, Address::times_4,  8));
    +  rorq(sum, 32);
    +  if (UseBMI2Instructions) {
    +    multiply_add_64_bmi2(sum, op1, op2, carry, raxReg);
    +  }
    +  else {
    +    multiply_add_64(sum, op1, op2, carry, rdxReg, raxReg);
    +  }
    +  // Store back in big endian from little endian
    +  rorq(sum, 0x20);
    +  movq(Address(out, offset, Address::times_4,  8), sum);
    +
    +  movq(op1, Address(in, len, Address::times_4,  0));
    +  rorq(op1, 32);
    +  movq(sum, Address(out, offset, Address::times_4,  0));
    +  rorq(sum, 32);
    +  if (UseBMI2Instructions) {
    +    multiply_add_64_bmi2(sum, op1, op2, carry, raxReg);
    +  }
    +  else {
    +    multiply_add_64(sum, op1, op2, carry, rdxReg, raxReg);
    +  }
    +  // Store back in big endian from little endian
    +  rorq(sum, 0x20);
    +  movq(Address(out, offset, Address::times_4,  0), sum);
    +
    +  jmp(L_first_loop);
    +  bind(L_first_loop_exit);
    +}
    +
    +/**
    + * Code for BigInteger::mulAdd() intrinsic
    + *
    + * rdi: out
    + * rsi: in
    + * r11: offs (out.length - offset)
    + * rcx: len
    + * r8:  k
    + * r12: tmp1
    + * r13: tmp2
    + * r14: tmp3
    + * r15: tmp4
    + * rbx: tmp5
    + * Multiply the in[] by word k and add to out[], return the carry in rax
    + */
    +void MacroAssembler::mul_add(Register out, Register in, Register offs,
    +   Register len, Register k, Register tmp1, Register tmp2, Register tmp3,
    +   Register tmp4, Register tmp5, Register rdxReg, Register raxReg) {
    +
    +  Label L_carry, L_last_in, L_done;
    +
    +// carry = 0;
    +// for (int j=len-1; j >= 0; j--) {
    +//    long product = (in[j] & LONG_MASK) * kLong +
    +//                   (out[offs] & LONG_MASK) + carry;
    +//    out[offs--] = (int)product;
    +//    carry = product >>> 32;
    +// }
    +//
    +  push(tmp1);
    +  push(tmp2);
    +  push(tmp3);
    +  push(tmp4);
    +  push(tmp5);
    +
    +  Register op2 = tmp2;
    +  const Register sum = tmp3;
    +  const Register op1 = tmp4;
    +  const Register carry =  tmp5;
    +
    +  if (UseBMI2Instructions) {
    +    op2 = rdxReg;
    +    movl(op2, k);
    +  }
    +  else {
    +    movl(op2, k);
    +  }
    +
    +  xorq(carry, carry);
    +
    +  //First loop
    +
    +  //Multiply in[] by k in a 4 way unrolled loop using 128 bit by 32 bit multiply
    +  //The carry is in tmp5
    +  mul_add_128_x_32_loop(out, in, offs, len, tmp1, tmp2, tmp3, tmp4, tmp5, rdxReg, raxReg);
    +
    +  //Multiply the trailing in[] entry using 64 bit by 32 bit, if any
    +  decrementl(len);
    +  jcc(Assembler::negative, L_carry);
    +  decrementl(len);
    +  jcc(Assembler::negative, L_last_in);
    +
    +  movq(op1, Address(in, len, Address::times_4,  0));
    +  rorq(op1, 32);
    +
    +  subl(offs, 2);
    +  movq(sum, Address(out, offs, Address::times_4,  0));
    +  rorq(sum, 32);
    +
    +  if (UseBMI2Instructions) {
    +    multiply_add_64_bmi2(sum, op1, op2, carry, raxReg);
    +  }
    +  else {
    +    multiply_add_64(sum, op1, op2, carry, rdxReg, raxReg);
    +  }
    +
    +  // Store back in big endian from little endian
    +  rorq(sum, 0x20);
    +  movq(Address(out, offs, Address::times_4,  0), sum);
    +
    +  testl(len, len);
    +  jccb(Assembler::zero, L_carry);
    +
    +  //Multiply the last in[] entry, if any
    +  bind(L_last_in);
    +  movl(op1, Address(in, 0));
    +  movl(sum, Address(out, offs, Address::times_4,  -4));
    +
    +  movl(raxReg, k);
    +  mull(op1); //tmp4 * eax -> edx:eax
    +  addl(sum, carry);
    +  adcl(rdxReg, 0);
    +  addl(sum, raxReg);
    +  adcl(rdxReg, 0);
    +  movl(carry, rdxReg);
    +
    +  movl(Address(out, offs, Address::times_4,  -4), sum);
    +
    +  bind(L_carry);
    +  //return tmp5/carry as carry in rax
    +  movl(rax, carry);
    +
    +  bind(L_done);
    +  pop(tmp5);
    +  pop(tmp4);
    +  pop(tmp3);
    +  pop(tmp2);
    +  pop(tmp1);
    +}
     #endif

     /**
      * Emits code to update CRC-32 with a byte value according to constants in table
      *

< prev index next >