< prev index next >

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

Print this page

    7702   // Next infrequent code is moved outside loops.
    7703   bind(L_last_x);
    7704   if (UseBMI2Instructions) {
    7705     movl(rdx, Address(x,  0));
    7706   } else {
    7707     movl(x_xstart, Address(x,  0));
    7708   }
    7709   jmp(L_third_loop_prologue);
    7710
    7711   bind(L_done);
    7712
    7713   pop(zlen);
    7714   pop(xlen);
    7715
    7716   pop(tmp5);
    7717   pop(tmp4);
    7718   pop(tmp3);
    7719   pop(tmp2);
    7720   pop(tmp1);
    7721 }

    7722 #endif
    7723
    7724 /**
    7725  * Emits code to update CRC-32 with a byte value according to constants in table
    7726  *
    7727  * @param [in,out]crc   Register containing the crc.
    7728  * @param [in]val       Register containing the byte to fold into the CRC.
    7729  * @param [in]table     Register containing the table of crc constants.
    7730  *
    7731  * uint32_t crc;
    7732  * val = crc_table[(val ^ crc) & 0xFF];
    7733  * crc = val ^ (crc >> 8);
    7734  *
    7735  */
    7736 void MacroAssembler::update_byte_crc32(Register crc, Register val, Register table) {
    7737   xorl(val, crc);
    7738   andl(val, 0xFF);
    7739   shrl(crc, 8); // unsigned shift
    7740   xorl(crc, Address(table, val, Address::times_4, 0));
    7741 }
    7702   // Next infrequent code is moved outside loops.
    7703   bind(L_last_x);
    7704   if (UseBMI2Instructions) {
    7705     movl(rdx, Address(x,  0));
    7706   } else {
    7707     movl(x_xstart, Address(x,  0));
    7708   }
    7709   jmp(L_third_loop_prologue);
    7710
    7711   bind(L_done);
    7712
    7713   pop(zlen);
    7714   pop(xlen);
    7715
    7716   pop(tmp5);
    7717   pop(tmp4);
    7718   pop(tmp3);
    7719   pop(tmp2);
    7720   pop(tmp1);
    7721 }
    7722
    7723 //Helper functions for square_to_len()
    7724
    7725 /**
    7726  * Store the squares of x[], right shifted one bit (divided by 2) into z[]
    7727  * Preserves x and z and modifies rest of the registers.
    7728  */
    7729
    7730 void MacroAssembler::square_rshift(Register x, Register xlen, Register z, Register tmp1, Register tmp3, Register tmp4, Register tmp5, Register rdxReg, Register raxReg) {
    7731   // Perform square and right shift by 1
    7732   // Handle odd xlen case first, then for even xlen do the following
    7733   // jlong carry = 0;
    7734   // for (int j=0, i=0; j < xlen; j+=2, i+=4) {
    7735   //     huge_128 product = x[j:j+1] * x[j:j+1];
    7736   //     z[i:i+1] = (carry << 63) | (jlong)(product >>> 65);
    7737   //     z[i+2:i+3] = (jlong)(product >>> 1);
    7738   //     carry = (jlong)product;
    7739   // }
    7740
    7741   xorq(tmp5, tmp5);     // carry
    7742   xorq(rdxReg, rdxReg);
    7743   xorl(tmp1, tmp1);     // index for x
    7744   xorl(tmp4, tmp4);     // index for z
    7745
    7746   Label L_first_loop, L_first_loop_exit;
    7747
    7748   testl(xlen, 1);
    7749   jcc(Assembler::zero, L_first_loop); //jump if xlen is even
    7750
    7751   // Square and right shift by 1 the odd element using 32 bit multiply
    7752   movl(raxReg, Address(x, tmp1, Address::times_4, 0));
    7753   imulq(raxReg, raxReg);
    7754   shrq(raxReg, 1);
    7755   adcq(tmp5, 0);
    7756   movq(Address(z, tmp4, Address::times_4, 0), raxReg);
    7757   incrementl(tmp1);
    7758   addl(tmp4, 2);
    7759
    7760   // Square and  right shift by 1 the rest using 64 bit multiply
    7761   bind(L_first_loop);
    7762   cmpptr(tmp1, xlen);
    7763   jcc(Assembler::equal, L_first_loop_exit);
    7764
    7765   // Square
    7766   movq(raxReg, Address(x, tmp1, Address::times_4,  0));
    7767   rorq(raxReg, 32);    // convert big-endian to little-endian
    7768   mulq(raxReg);        // 64-bit multiply rax * rax -> rdx:rax
    7769
    7770   // Right shift by 1 and save carry
    7771   shrq(tmp5, 1);       // rdx:rax:tmp5 = (tmp5:rdx:rax) >>> 1
    7772   rcrq(rdxReg, 1);
    7773   rcrq(raxReg, 1);
    7774   adcq(tmp5, 0);
    7775
    7776   // Store result in z
    7777   movq(Address(z, tmp4, Address::times_4, 0), rdxReg);
    7778   movq(Address(z, tmp4, Address::times_4, 8), raxReg);
    7779
    7780   // Update indices for x and z
    7781   addl(tmp1, 2);
    7782   addl(tmp4, 4);
    7783   jmp(L_first_loop);
    7784
    7785   bind(L_first_loop_exit);
    7786 }
    7787
    7788
    7789 /**
    7790  * Perform the following multiply add operation using BMI2 instructions
    7791  * carry:sum = sum + op1*op2 + carry
    7792  * op2 should be in rdx
    7793  * op2 is preserved, all other registers are modified
    7794  */
    7795 void MacroAssembler::multiply_add_64_bmi2(Register sum, Register op1, Register op2, Register carry, Register tmp2) {
    7796   // assert op2 is rdx
    7797   mulxq(tmp2, op1, op1);  //  op1 * op2 -> tmp2:op1
    7798   addq(sum, carry);
    7799   adcq(tmp2, 0);
    7800   addq(sum, op1);
    7801   adcq(tmp2, 0);
    7802   movq(carry, tmp2);
    7803 }
    7804
    7805 /**
    7806  * Perform the following multiply add operation:
    7807  * carry:sum = sum + op1*op2 + carry
    7808  * Preserves op1, op2 and modifies rest of registers
    7809  */
    7810 void MacroAssembler::multiply_add_64(Register sum, Register op1, Register op2, Register carry, Register rdxReg, Register raxReg) {
    7811   // rdx:rax = op1 * op2
    7812   movq(raxReg, op2);
    7813   mulq(op1);
    7814
    7815   //  rdx:rax = sum + carry + rdx:rax
    7816   addq(sum, carry);
    7817   adcq(rdxReg, 0);
    7818   addq(sum, raxReg);
    7819   adcq(rdxReg, 0);
    7820
    7821   // carry:sum = rdx:sum
    7822   movq(carry, rdxReg);
    7823 }
    7824
    7825 /**
    7826  * Add 64 bit long carry into z[] with carry propogation.
    7827  * Preserves z and carry register values and modifies rest of registers.
    7828  *
    7829  */
    7830 void MacroAssembler::add_one_64(Register z, Register zlen, Register carry, Register tmp1) {
    7831   Label L_fourth_loop, L_fourth_loop_exit;
    7832
    7833   movl(tmp1, 1);
    7834   subl(zlen, 2);
    7835   addq(Address(z, zlen, Address::times_4, 0), carry);
    7836
    7837   bind(L_fourth_loop);
    7838   jcc(Assembler::carryClear, L_fourth_loop_exit);
    7839   subl(zlen, 2);
    7840   jcc(Assembler::negative, L_fourth_loop_exit);
    7841   addq(Address(z, zlen, Address::times_4, 0), tmp1);
    7842   jmp(L_fourth_loop);
    7843   bind(L_fourth_loop_exit);
    7844 }
    7845
    7846 /**
    7847  * Shift z[] left by 1 bit.
    7848  * Preserves x, len, z and zlen registers and modifies rest of the registers.
    7849  *
    7850  */
    7851 void MacroAssembler::lshift_by_1(Register x, Register len, Register z, Register zlen, Register tmp1, Register tmp2, Register tmp3, Register tmp4) {
    7852
    7853   Label L_fifth_loop, L_fifth_loop_exit;
    7854
    7855   // Fifth loop
    7856   // Perform primitiveLeftShift(z, zlen, 1)
    7857
    7858   const Register prev_carry = tmp1;
    7859   const Register new_carry = tmp4;
    7860   const Register value = tmp2;
    7861   const Register zidx = tmp3;
    7862
    7863   // int zidx, carry;
    7864   // long value;
    7865   // carry = 0;
    7866   // for (zidx = zlen-2; zidx >=0; zidx -= 2) {
    7867   //    (carry:value)  = (z[i] << 1) | carry ;
    7868   //    z[i] = value;
    7869   // }
    7870
    7871   movl(zidx, zlen);
    7872   xorl(prev_carry, prev_carry); // clear carry flag and prev_carry register
    7873
    7874   bind(L_fifth_loop);
    7875   decl(zidx);  // Use decl to preserve carry flag
    7876   decl(zidx);
    7877   jcc(Assembler::negative, L_fifth_loop_exit);
    7878
    7879   if (UseBMI2Instructions) {
    7880      movq(value, Address(z, zidx, Address::times_4, 0));
    7881      rclq(value, 1);
    7882      rorxq(value, value, 32);
    7883      movq(Address(z, zidx, Address::times_4,  0), value);  // Store back in big endian form
    7884   }
    7885   else {
    7886     // clear new_carry
    7887     xorl(new_carry, new_carry);
    7888
    7889     // Shift z[i] by 1, or in previous carry and save new carry
    7890     movq(value, Address(z, zidx, Address::times_4, 0));
    7891     shlq(value, 1);
    7892     adcl(new_carry, 0);
    7893
    7894     orq(value, prev_carry);
    7895     rorq(value, 0x20);
    7896     movq(Address(z, zidx, Address::times_4,  0), value);  // Store back in big endian form
    7897
    7898     // Set previous carry = new carry
    7899     movl(prev_carry, new_carry);
    7900   }
    7901   jmp(L_fifth_loop);
    7902
    7903   bind(L_fifth_loop_exit);
    7904 }
    7905
    7906
    7907 /**
    7908  * Code for BigInteger::squareToLen() intrinsic
    7909  *
    7910  * rdi: x
    7911  * rsi: len
    7912  * r8:  z
    7913  * rcx: zlen
    7914  * r12: tmp1
    7915  * r13: tmp2
    7916  * r14: tmp3
    7917  * r15: tmp4
    7918  * rbx: tmp5
    7919  *
    7920  */
    7921 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) {
    7922
    7923   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;
    7924   push(tmp1);
    7925   push(tmp2);
    7926   push(tmp3);
    7927   push(tmp4);
    7928   push(tmp5);
    7929
    7930   // First loop
    7931   // Store the squares, right shifted one bit (i.e., divided by 2).
    7932   square_rshift(x, len, z, tmp1, tmp3, tmp4, tmp5, rdxReg, raxReg);
    7933
    7934   // Add in off-diagonal sums.
    7935   //
    7936   // Second, third (nested) and fourth loops.
    7937   // zlen +=2;
    7938   // for (int xidx=len-2,zidx=zlen-4; xidx > 0; xidx-=2,zidx-=4) {
    7939   //    carry = 0;
    7940   //    long op2 = x[xidx:xidx+1];
    7941   //    for (int j=xidx-2,k=zidx; j >= 0; j-=2) {
    7942   //       k -= 2;
    7943   //       long op1 = x[j:j+1];
    7944   //       long sum = z[k:k+1];
    7945   //       carry:sum = multiply_add_64(sum, op1, op2, carry, tmp_regs);
    7946   //       z[k:k+1] = sum;
    7947   //    }
    7948   //    add_one_64(z, k, carry, tmp_regs);
    7949   // }
    7950
    7951
    7952   const Register carry = tmp5;
    7953   const Register sum = tmp3;
    7954   const Register op1 = tmp4;
    7955   Register op2 = tmp2;
    7956
    7957   push(zlen);
    7958   push(len);
    7959   addl(zlen,2);
    7960   bind(L_second_loop);
    7961   xorq(carry, carry);
    7962   subl(zlen, 4);
    7963   subl(len, 2);
    7964   push(zlen);
    7965   push(len);
    7966   cmpl(len, 0);
    7967   jcc(Assembler::lessEqual, L_second_loop_exit);
    7968
    7969   // Multiply an array by one 64 bit long.
    7970   if (UseBMI2Instructions) {
    7971     op2 = rdxReg;
    7972     movq(op2, Address(x, len, Address::times_4,  0));
    7973     rorxq(op2, op2, 32);
    7974   }
    7975   else {
    7976     movq(op2, Address(x, len, Address::times_4,  0));
    7977     rorq(op2, 32);
    7978   }
    7979
    7980   bind(L_third_loop);
    7981   decrementl(len);
    7982   jcc(Assembler::negative, L_third_loop_exit);
    7983   decrementl(len);
    7984   jcc(Assembler::negative, L_last_x);
    7985
    7986   movq(op1, Address(x, len, Address::times_4,  0));
    7987   rorq(op1, 32);
    7988
    7989   bind(L_multiply);
    7990   subl(zlen, 2);
    7991   movq(sum, Address(z, zlen, Address::times_4,  0));
    7992
    7993   // Multiply 64 bit by 64 bit and add 64 bits lower half and upper 64 bits as carry.
    7994   if (UseBMI2Instructions) {
    7995     multiply_add_64_bmi2(sum, op1, op2, carry, tmp2);
    7996   }
    7997   else {
    7998     multiply_add_64(sum, op1, op2, carry, rdxReg, raxReg);
    7999   }
    8000
    8001   movq(Address(z, zlen, Address::times_4, 0), sum);
    8002
    8003   jmp(L_third_loop);
    8004   bind(L_third_loop_exit);
    8005
    8006   // Fourth loop
    8007   // Add 64 bit long carry into z with carry propogation.
    8008   // Uses offsetted zlen.
    8009   add_one_64(z, zlen, carry, tmp1);
    8010
    8011   pop(len);
    8012   pop(zlen);
    8013   jmp(L_second_loop);
    8014
    8015   // Next infrequent code is moved outside loops.
    8016   bind(L_last_x);
    8017   movl(op1, Address(x, 0));
    8018   jmp(L_multiply);
    8019
    8020   bind(L_second_loop_exit);
    8021   pop(len);
    8022   pop(zlen);
    8023   pop(len);
    8024   pop(zlen);
    8025
    8026   // Fifth loop
    8027   // Shift z left 1 bit.
    8028   lshift_by_1(x, len, z, zlen, tmp1, tmp2, tmp3, tmp4);
    8029
    8030   // z[zlen-1] |= x[len-1] & 1;
    8031   movl(tmp3, Address(x, len, Address::times_4, -4));
    8032   andl(tmp3, 1);
    8033   orl(Address(z, zlen, Address::times_4,  -4), tmp3);
    8034
    8035   pop(tmp5);
    8036   pop(tmp4);
    8037   pop(tmp3);
    8038   pop(tmp2);
    8039   pop(tmp1);
    8040 }
    8041
    8042 /**
    8043  * Helper function for mul_add()
    8044  * Multiply the in[] by int k and add to out[] starting at offset offs using
    8045  * 128 bit by 32 bit multiply and return the carry in tmp5.
    8046  * Only quad int aligned length of in[] is operated on in this function.
    8047  * k is in rdxReg for BMI2Instructions, for others it is in tmp2.
    8048  * This function preserves out, in and k registers.
    8049  * len and offset point to the appropriate index in "in" & "out" correspondingly
    8050  * tmp5 has the carry.
    8051  * other registers are temporary and are modified.
    8052  *
    8053  */
    8054 void MacroAssembler::mul_add_128_x_32_loop(Register out, Register in,
    8055   Register offset, Register len, Register tmp1, Register tmp2, Register tmp3,
    8056   Register tmp4, Register tmp5, Register rdxReg, Register raxReg) {
    8057
    8058   Label L_first_loop, L_first_loop_exit;
    8059
    8060   movl(tmp1, len);
    8061   shrl(tmp1, 2);
    8062
    8063   bind(L_first_loop);
    8064   subl(tmp1, 1);
    8065   jcc(Assembler::negative, L_first_loop_exit);
    8066
    8067   subl(len, 4);
    8068   subl(offset, 4);
    8069
    8070   Register op2 = tmp2;
    8071   const Register sum = tmp3;
    8072   const Register op1 = tmp4;
    8073   const Register carry = tmp5;
    8074
    8075   if (UseBMI2Instructions) {
    8076     op2 = rdxReg;
    8077   }
    8078
    8079   movq(op1, Address(in, len, Address::times_4,  8));
    8080   rorq(op1, 32);
    8081   movq(sum, Address(out, offset, Address::times_4,  8));
    8082   rorq(sum, 32);
    8083   if (UseBMI2Instructions) {
    8084     multiply_add_64_bmi2(sum, op1, op2, carry, raxReg);
    8085   }
    8086   else {
    8087     multiply_add_64(sum, op1, op2, carry, rdxReg, raxReg);
    8088   }
    8089   // Store back in big endian from little endian
    8090   rorq(sum, 0x20);
    8091   movq(Address(out, offset, Address::times_4,  8), sum);
    8092
    8093   movq(op1, Address(in, len, Address::times_4,  0));
    8094   rorq(op1, 32);
    8095   movq(sum, Address(out, offset, Address::times_4,  0));
    8096   rorq(sum, 32);
    8097   if (UseBMI2Instructions) {
    8098     multiply_add_64_bmi2(sum, op1, op2, carry, raxReg);
    8099   }
    8100   else {
    8101     multiply_add_64(sum, op1, op2, carry, rdxReg, raxReg);
    8102   }
    8103   // Store back in big endian from little endian
    8104   rorq(sum, 0x20);
    8105   movq(Address(out, offset, Address::times_4,  0), sum);
    8106
    8107   jmp(L_first_loop);
    8108   bind(L_first_loop_exit);
    8109 }
    8110
    8111 /**
    8112  * Code for BigInteger::mulAdd() intrinsic
    8113  *
    8114  * rdi: out
    8115  * rsi: in
    8116  * r11: offs (out.length - offset)
    8117  * rcx: len
    8118  * r8:  k
    8119  * r12: tmp1
    8120  * r13: tmp2
    8121  * r14: tmp3
    8122  * r15: tmp4
    8123  * rbx: tmp5
    8124  * Multiply the in[] by word k and add to out[], return the carry in rax
    8125  */
    8126 void MacroAssembler::mul_add(Register out, Register in, Register offs,
    8127    Register len, Register k, Register tmp1, Register tmp2, Register tmp3,
    8128    Register tmp4, Register tmp5, Register rdxReg, Register raxReg) {
    8129
    8130   Label L_carry, L_last_in, L_done;
    8131
    8132 // carry = 0;
    8133 // for (int j=len-1; j >= 0; j--) {
    8134 //    long product = (in[j] & LONG_MASK) * kLong +
    8135 //                   (out[offs] & LONG_MASK) + carry;
    8136 //    out[offs--] = (int)product;
    8137 //    carry = product >>> 32;
    8138 // }
    8139 //
    8140   push(tmp1);
    8141   push(tmp2);
    8142   push(tmp3);
    8143   push(tmp4);
    8144   push(tmp5);
    8145
    8146   Register op2 = tmp2;
    8147   const Register sum = tmp3;
    8148   const Register op1 = tmp4;
    8149   const Register carry =  tmp5;
    8150
    8151   if (UseBMI2Instructions) {
    8152     op2 = rdxReg;
    8153     movl(op2, k);
    8154   }
    8155   else {
    8156     movl(op2, k);
    8157   }
    8158
    8159   xorq(carry, carry);
    8160
    8161   //First loop
    8162
    8163   //Multiply in[] by k in a 4 way unrolled loop using 128 bit by 32 bit multiply
    8164   //The carry is in tmp5
    8165   mul_add_128_x_32_loop(out, in, offs, len, tmp1, tmp2, tmp3, tmp4, tmp5, rdxReg, raxReg);
    8166
    8167   //Multiply the trailing in[] entry using 64 bit by 32 bit, if any
    8168   decrementl(len);
    8169   jcc(Assembler::negative, L_carry);
    8170   decrementl(len);
    8171   jcc(Assembler::negative, L_last_in);
    8172
    8173   movq(op1, Address(in, len, Address::times_4,  0));
    8174   rorq(op1, 32);
    8175
    8176   subl(offs, 2);
    8177   movq(sum, Address(out, offs, Address::times_4,  0));
    8178   rorq(sum, 32);
    8179
    8180   if (UseBMI2Instructions) {
    8181     multiply_add_64_bmi2(sum, op1, op2, carry, raxReg);
    8182   }
    8183   else {
    8184     multiply_add_64(sum, op1, op2, carry, rdxReg, raxReg);
    8185   }
    8186
    8187   // Store back in big endian from little endian
    8188   rorq(sum, 0x20);
    8189   movq(Address(out, offs, Address::times_4,  0), sum);
    8190
    8191   testl(len, len);
    8192   jccb(Assembler::zero, L_carry);
    8193
    8194   //Multiply the last in[] entry, if any
    8195   bind(L_last_in);
    8196   movl(op1, Address(in, 0));
    8197   movl(sum, Address(out, offs, Address::times_4,  -4));
    8198
    8199   movl(raxReg, k);
    8200   mull(op1); //tmp4 * eax -> edx:eax
    8201   addl(sum, carry);
    8202   adcl(rdxReg, 0);
    8203   addl(sum, raxReg);
    8204   adcl(rdxReg, 0);
    8205   movl(carry, rdxReg);
    8206
    8207   movl(Address(out, offs, Address::times_4,  -4), sum);
    8208
    8209   bind(L_carry);
    8210   //return tmp5/carry as carry in rax
    8211   movl(rax, carry);
    8212
    8213   bind(L_done);
    8214   pop(tmp5);
    8215   pop(tmp4);
    8216   pop(tmp3);
    8217   pop(tmp2);
    8218   pop(tmp1);
    8219 }
    8220 #endif
    8221
    8222 /**
    8223  * Emits code to update CRC-32 with a byte value according to constants in table
    8224  *
    8225  * @param [in,out]crc   Register containing the crc.
    8226  * @param [in]val       Register containing the byte to fold into the CRC.
    8227  * @param [in]table     Register containing the table of crc constants.
    8228  *
    8229  * uint32_t crc;
    8230  * val = crc_table[(val ^ crc) & 0xFF];
    8231  * crc = val ^ (crc >> 8);
    8232  *
    8233  */
    8234 void MacroAssembler::update_byte_crc32(Register crc, Register val, Register table) {
    8235   xorl(val, crc);
    8236   andl(val, 0xFF);
    8237   shrl(crc, 8); // unsigned shift
    8238   xorl(crc, Address(table, val, Address::times_4, 0));
    8239 }

< prev index next >