1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/share/vm/opto/divnode.cpp Wed Apr 27 01:25:04 2016 +0800
1.3 @@ -0,0 +1,1325 @@
1.4 +/*
1.5 + * Copyright (c) 1997, 2012, Oracle and/or its affiliates. All rights reserved.
1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.7 + *
1.8 + * This code is free software; you can redistribute it and/or modify it
1.9 + * under the terms of the GNU General Public License version 2 only, as
1.10 + * published by the Free Software Foundation.
1.11 + *
1.12 + * This code is distributed in the hope that it will be useful, but WITHOUT
1.13 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.14 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.15 + * version 2 for more details (a copy is included in the LICENSE file that
1.16 + * accompanied this code).
1.17 + *
1.18 + * You should have received a copy of the GNU General Public License version
1.19 + * 2 along with this work; if not, write to the Free Software Foundation,
1.20 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.21 + *
1.22 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
1.23 + * or visit www.oracle.com if you need additional information or have any
1.24 + * questions.
1.25 + *
1.26 + */
1.27 +
1.28 +#include "precompiled.hpp"
1.29 +#include "memory/allocation.inline.hpp"
1.30 +#include "opto/addnode.hpp"
1.31 +#include "opto/connode.hpp"
1.32 +#include "opto/divnode.hpp"
1.33 +#include "opto/machnode.hpp"
1.34 +#include "opto/matcher.hpp"
1.35 +#include "opto/mulnode.hpp"
1.36 +#include "opto/phaseX.hpp"
1.37 +#include "opto/subnode.hpp"
1.38 +
1.39 +// Portions of code courtesy of Clifford Click
1.40 +
1.41 +// Optimization - Graph Style
1.42 +
1.43 +#include <math.h>
1.44 +
1.45 +//----------------------magic_int_divide_constants-----------------------------
1.46 +// Compute magic multiplier and shift constant for converting a 32 bit divide
1.47 +// by constant into a multiply/shift/add series. Return false if calculations
1.48 +// fail.
1.49 +//
1.50 +// Borrowed almost verbatim from Hacker's Delight by Henry S. Warren, Jr. with
1.51 +// minor type name and parameter changes.
1.52 +static bool magic_int_divide_constants(jint d, jint &M, jint &s) {
1.53 + int32_t p;
1.54 + uint32_t ad, anc, delta, q1, r1, q2, r2, t;
1.55 + const uint32_t two31 = 0x80000000L; // 2**31.
1.56 +
1.57 + ad = ABS(d);
1.58 + if (d == 0 || d == 1) return false;
1.59 + t = two31 + ((uint32_t)d >> 31);
1.60 + anc = t - 1 - t%ad; // Absolute value of nc.
1.61 + p = 31; // Init. p.
1.62 + q1 = two31/anc; // Init. q1 = 2**p/|nc|.
1.63 + r1 = two31 - q1*anc; // Init. r1 = rem(2**p, |nc|).
1.64 + q2 = two31/ad; // Init. q2 = 2**p/|d|.
1.65 + r2 = two31 - q2*ad; // Init. r2 = rem(2**p, |d|).
1.66 + do {
1.67 + p = p + 1;
1.68 + q1 = 2*q1; // Update q1 = 2**p/|nc|.
1.69 + r1 = 2*r1; // Update r1 = rem(2**p, |nc|).
1.70 + if (r1 >= anc) { // (Must be an unsigned
1.71 + q1 = q1 + 1; // comparison here).
1.72 + r1 = r1 - anc;
1.73 + }
1.74 + q2 = 2*q2; // Update q2 = 2**p/|d|.
1.75 + r2 = 2*r2; // Update r2 = rem(2**p, |d|).
1.76 + if (r2 >= ad) { // (Must be an unsigned
1.77 + q2 = q2 + 1; // comparison here).
1.78 + r2 = r2 - ad;
1.79 + }
1.80 + delta = ad - r2;
1.81 + } while (q1 < delta || (q1 == delta && r1 == 0));
1.82 +
1.83 + M = q2 + 1;
1.84 + if (d < 0) M = -M; // Magic number and
1.85 + s = p - 32; // shift amount to return.
1.86 +
1.87 + return true;
1.88 +}
1.89 +
1.90 +//--------------------------transform_int_divide-------------------------------
1.91 +// Convert a division by constant divisor into an alternate Ideal graph.
1.92 +// Return NULL if no transformation occurs.
1.93 +static Node *transform_int_divide( PhaseGVN *phase, Node *dividend, jint divisor ) {
1.94 +
1.95 + // Check for invalid divisors
1.96 + assert( divisor != 0 && divisor != min_jint,
1.97 + "bad divisor for transforming to long multiply" );
1.98 +
1.99 + bool d_pos = divisor >= 0;
1.100 + jint d = d_pos ? divisor : -divisor;
1.101 + const int N = 32;
1.102 +
1.103 + // Result
1.104 + Node *q = NULL;
1.105 +
1.106 + if (d == 1) {
1.107 + // division by +/- 1
1.108 + if (!d_pos) {
1.109 + // Just negate the value
1.110 + q = new (phase->C) SubINode(phase->intcon(0), dividend);
1.111 + }
1.112 + } else if ( is_power_of_2(d) ) {
1.113 + // division by +/- a power of 2
1.114 +
1.115 + // See if we can simply do a shift without rounding
1.116 + bool needs_rounding = true;
1.117 + const Type *dt = phase->type(dividend);
1.118 + const TypeInt *dti = dt->isa_int();
1.119 + if (dti && dti->_lo >= 0) {
1.120 + // we don't need to round a positive dividend
1.121 + needs_rounding = false;
1.122 + } else if( dividend->Opcode() == Op_AndI ) {
1.123 + // An AND mask of sufficient size clears the low bits and
1.124 + // I can avoid rounding.
1.125 + const TypeInt *andconi_t = phase->type( dividend->in(2) )->isa_int();
1.126 + if( andconi_t && andconi_t->is_con() ) {
1.127 + jint andconi = andconi_t->get_con();
1.128 + if( andconi < 0 && is_power_of_2(-andconi) && (-andconi) >= d ) {
1.129 + if( (-andconi) == d ) // Remove AND if it clears bits which will be shifted
1.130 + dividend = dividend->in(1);
1.131 + needs_rounding = false;
1.132 + }
1.133 + }
1.134 + }
1.135 +
1.136 + // Add rounding to the shift to handle the sign bit
1.137 + int l = log2_intptr(d-1)+1;
1.138 + if (needs_rounding) {
1.139 + // Divide-by-power-of-2 can be made into a shift, but you have to do
1.140 + // more math for the rounding. You need to add 0 for positive
1.141 + // numbers, and "i-1" for negative numbers. Example: i=4, so the
1.142 + // shift is by 2. You need to add 3 to negative dividends and 0 to
1.143 + // positive ones. So (-7+3)>>2 becomes -1, (-4+3)>>2 becomes -1,
1.144 + // (-2+3)>>2 becomes 0, etc.
1.145 +
1.146 + // Compute 0 or -1, based on sign bit
1.147 + Node *sign = phase->transform(new (phase->C) RShiftINode(dividend, phase->intcon(N - 1)));
1.148 + // Mask sign bit to the low sign bits
1.149 + Node *round = phase->transform(new (phase->C) URShiftINode(sign, phase->intcon(N - l)));
1.150 + // Round up before shifting
1.151 + dividend = phase->transform(new (phase->C) AddINode(dividend, round));
1.152 + }
1.153 +
1.154 + // Shift for division
1.155 + q = new (phase->C) RShiftINode(dividend, phase->intcon(l));
1.156 +
1.157 + if (!d_pos) {
1.158 + q = new (phase->C) SubINode(phase->intcon(0), phase->transform(q));
1.159 + }
1.160 + } else {
1.161 + // Attempt the jint constant divide -> multiply transform found in
1.162 + // "Division by Invariant Integers using Multiplication"
1.163 + // by Granlund and Montgomery
1.164 + // See also "Hacker's Delight", chapter 10 by Warren.
1.165 +
1.166 + jint magic_const;
1.167 + jint shift_const;
1.168 + if (magic_int_divide_constants(d, magic_const, shift_const)) {
1.169 + Node *magic = phase->longcon(magic_const);
1.170 + Node *dividend_long = phase->transform(new (phase->C) ConvI2LNode(dividend));
1.171 +
1.172 + // Compute the high half of the dividend x magic multiplication
1.173 + Node *mul_hi = phase->transform(new (phase->C) MulLNode(dividend_long, magic));
1.174 +
1.175 + if (magic_const < 0) {
1.176 + mul_hi = phase->transform(new (phase->C) RShiftLNode(mul_hi, phase->intcon(N)));
1.177 + mul_hi = phase->transform(new (phase->C) ConvL2INode(mul_hi));
1.178 +
1.179 + // The magic multiplier is too large for a 32 bit constant. We've adjusted
1.180 + // it down by 2^32, but have to add 1 dividend back in after the multiplication.
1.181 + // This handles the "overflow" case described by Granlund and Montgomery.
1.182 + mul_hi = phase->transform(new (phase->C) AddINode(dividend, mul_hi));
1.183 +
1.184 + // Shift over the (adjusted) mulhi
1.185 + if (shift_const != 0) {
1.186 + mul_hi = phase->transform(new (phase->C) RShiftINode(mul_hi, phase->intcon(shift_const)));
1.187 + }
1.188 + } else {
1.189 + // No add is required, we can merge the shifts together.
1.190 + mul_hi = phase->transform(new (phase->C) RShiftLNode(mul_hi, phase->intcon(N + shift_const)));
1.191 + mul_hi = phase->transform(new (phase->C) ConvL2INode(mul_hi));
1.192 + }
1.193 +
1.194 + // Get a 0 or -1 from the sign of the dividend.
1.195 + Node *addend0 = mul_hi;
1.196 + Node *addend1 = phase->transform(new (phase->C) RShiftINode(dividend, phase->intcon(N-1)));
1.197 +
1.198 + // If the divisor is negative, swap the order of the input addends;
1.199 + // this has the effect of negating the quotient.
1.200 + if (!d_pos) {
1.201 + Node *temp = addend0; addend0 = addend1; addend1 = temp;
1.202 + }
1.203 +
1.204 + // Adjust the final quotient by subtracting -1 (adding 1)
1.205 + // from the mul_hi.
1.206 + q = new (phase->C) SubINode(addend0, addend1);
1.207 + }
1.208 + }
1.209 +
1.210 + return q;
1.211 +}
1.212 +
1.213 +//---------------------magic_long_divide_constants-----------------------------
1.214 +// Compute magic multiplier and shift constant for converting a 64 bit divide
1.215 +// by constant into a multiply/shift/add series. Return false if calculations
1.216 +// fail.
1.217 +//
1.218 +// Borrowed almost verbatim from Hacker's Delight by Henry S. Warren, Jr. with
1.219 +// minor type name and parameter changes. Adjusted to 64 bit word width.
1.220 +static bool magic_long_divide_constants(jlong d, jlong &M, jint &s) {
1.221 + int64_t p;
1.222 + uint64_t ad, anc, delta, q1, r1, q2, r2, t;
1.223 + const uint64_t two63 = 0x8000000000000000LL; // 2**63.
1.224 +
1.225 + ad = ABS(d);
1.226 + if (d == 0 || d == 1) return false;
1.227 + t = two63 + ((uint64_t)d >> 63);
1.228 + anc = t - 1 - t%ad; // Absolute value of nc.
1.229 + p = 63; // Init. p.
1.230 + q1 = two63/anc; // Init. q1 = 2**p/|nc|.
1.231 + r1 = two63 - q1*anc; // Init. r1 = rem(2**p, |nc|).
1.232 + q2 = two63/ad; // Init. q2 = 2**p/|d|.
1.233 + r2 = two63 - q2*ad; // Init. r2 = rem(2**p, |d|).
1.234 + do {
1.235 + p = p + 1;
1.236 + q1 = 2*q1; // Update q1 = 2**p/|nc|.
1.237 + r1 = 2*r1; // Update r1 = rem(2**p, |nc|).
1.238 + if (r1 >= anc) { // (Must be an unsigned
1.239 + q1 = q1 + 1; // comparison here).
1.240 + r1 = r1 - anc;
1.241 + }
1.242 + q2 = 2*q2; // Update q2 = 2**p/|d|.
1.243 + r2 = 2*r2; // Update r2 = rem(2**p, |d|).
1.244 + if (r2 >= ad) { // (Must be an unsigned
1.245 + q2 = q2 + 1; // comparison here).
1.246 + r2 = r2 - ad;
1.247 + }
1.248 + delta = ad - r2;
1.249 + } while (q1 < delta || (q1 == delta && r1 == 0));
1.250 +
1.251 + M = q2 + 1;
1.252 + if (d < 0) M = -M; // Magic number and
1.253 + s = p - 64; // shift amount to return.
1.254 +
1.255 + return true;
1.256 +}
1.257 +
1.258 +//---------------------long_by_long_mulhi--------------------------------------
1.259 +// Generate ideal node graph for upper half of a 64 bit x 64 bit multiplication
1.260 +static Node* long_by_long_mulhi(PhaseGVN* phase, Node* dividend, jlong magic_const) {
1.261 + // If the architecture supports a 64x64 mulhi, there is
1.262 + // no need to synthesize it in ideal nodes.
1.263 + if (Matcher::has_match_rule(Op_MulHiL)) {
1.264 + Node* v = phase->longcon(magic_const);
1.265 + return new (phase->C) MulHiLNode(dividend, v);
1.266 + }
1.267 +
1.268 + // Taken from Hacker's Delight, Fig. 8-2. Multiply high signed.
1.269 + // (http://www.hackersdelight.org/HDcode/mulhs.c)
1.270 + //
1.271 + // int mulhs(int u, int v) {
1.272 + // unsigned u0, v0, w0;
1.273 + // int u1, v1, w1, w2, t;
1.274 + //
1.275 + // u0 = u & 0xFFFF; u1 = u >> 16;
1.276 + // v0 = v & 0xFFFF; v1 = v >> 16;
1.277 + // w0 = u0*v0;
1.278 + // t = u1*v0 + (w0 >> 16);
1.279 + // w1 = t & 0xFFFF;
1.280 + // w2 = t >> 16;
1.281 + // w1 = u0*v1 + w1;
1.282 + // return u1*v1 + w2 + (w1 >> 16);
1.283 + // }
1.284 + //
1.285 + // Note: The version above is for 32x32 multiplications, while the
1.286 + // following inline comments are adapted to 64x64.
1.287 +
1.288 + const int N = 64;
1.289 +
1.290 + // Dummy node to keep intermediate nodes alive during construction
1.291 + Node* hook = new (phase->C) Node(4);
1.292 +
1.293 + // u0 = u & 0xFFFFFFFF; u1 = u >> 32;
1.294 + Node* u0 = phase->transform(new (phase->C) AndLNode(dividend, phase->longcon(0xFFFFFFFF)));
1.295 + Node* u1 = phase->transform(new (phase->C) RShiftLNode(dividend, phase->intcon(N / 2)));
1.296 + hook->init_req(0, u0);
1.297 + hook->init_req(1, u1);
1.298 +
1.299 + // v0 = v & 0xFFFFFFFF; v1 = v >> 32;
1.300 + Node* v0 = phase->longcon(magic_const & 0xFFFFFFFF);
1.301 + Node* v1 = phase->longcon(magic_const >> (N / 2));
1.302 +
1.303 + // w0 = u0*v0;
1.304 + Node* w0 = phase->transform(new (phase->C) MulLNode(u0, v0));
1.305 +
1.306 + // t = u1*v0 + (w0 >> 32);
1.307 + Node* u1v0 = phase->transform(new (phase->C) MulLNode(u1, v0));
1.308 + Node* temp = phase->transform(new (phase->C) URShiftLNode(w0, phase->intcon(N / 2)));
1.309 + Node* t = phase->transform(new (phase->C) AddLNode(u1v0, temp));
1.310 + hook->init_req(2, t);
1.311 +
1.312 + // w1 = t & 0xFFFFFFFF;
1.313 + Node* w1 = phase->transform(new (phase->C) AndLNode(t, phase->longcon(0xFFFFFFFF)));
1.314 + hook->init_req(3, w1);
1.315 +
1.316 + // w2 = t >> 32;
1.317 + Node* w2 = phase->transform(new (phase->C) RShiftLNode(t, phase->intcon(N / 2)));
1.318 +
1.319 + // w1 = u0*v1 + w1;
1.320 + Node* u0v1 = phase->transform(new (phase->C) MulLNode(u0, v1));
1.321 + w1 = phase->transform(new (phase->C) AddLNode(u0v1, w1));
1.322 +
1.323 + // return u1*v1 + w2 + (w1 >> 32);
1.324 + Node* u1v1 = phase->transform(new (phase->C) MulLNode(u1, v1));
1.325 + Node* temp1 = phase->transform(new (phase->C) AddLNode(u1v1, w2));
1.326 + Node* temp2 = phase->transform(new (phase->C) RShiftLNode(w1, phase->intcon(N / 2)));
1.327 +
1.328 + // Remove the bogus extra edges used to keep things alive
1.329 + PhaseIterGVN* igvn = phase->is_IterGVN();
1.330 + if (igvn != NULL) {
1.331 + igvn->remove_dead_node(hook);
1.332 + } else {
1.333 + for (int i = 0; i < 4; i++) {
1.334 + hook->set_req(i, NULL);
1.335 + }
1.336 + }
1.337 +
1.338 + return new (phase->C) AddLNode(temp1, temp2);
1.339 +}
1.340 +
1.341 +
1.342 +//--------------------------transform_long_divide------------------------------
1.343 +// Convert a division by constant divisor into an alternate Ideal graph.
1.344 +// Return NULL if no transformation occurs.
1.345 +static Node *transform_long_divide( PhaseGVN *phase, Node *dividend, jlong divisor ) {
1.346 + // Check for invalid divisors
1.347 + assert( divisor != 0L && divisor != min_jlong,
1.348 + "bad divisor for transforming to long multiply" );
1.349 +
1.350 + bool d_pos = divisor >= 0;
1.351 + jlong d = d_pos ? divisor : -divisor;
1.352 + const int N = 64;
1.353 +
1.354 + // Result
1.355 + Node *q = NULL;
1.356 +
1.357 + if (d == 1) {
1.358 + // division by +/- 1
1.359 + if (!d_pos) {
1.360 + // Just negate the value
1.361 + q = new (phase->C) SubLNode(phase->longcon(0), dividend);
1.362 + }
1.363 + } else if ( is_power_of_2_long(d) ) {
1.364 +
1.365 + // division by +/- a power of 2
1.366 +
1.367 + // See if we can simply do a shift without rounding
1.368 + bool needs_rounding = true;
1.369 + const Type *dt = phase->type(dividend);
1.370 + const TypeLong *dtl = dt->isa_long();
1.371 +
1.372 + if (dtl && dtl->_lo > 0) {
1.373 + // we don't need to round a positive dividend
1.374 + needs_rounding = false;
1.375 + } else if( dividend->Opcode() == Op_AndL ) {
1.376 + // An AND mask of sufficient size clears the low bits and
1.377 + // I can avoid rounding.
1.378 + const TypeLong *andconl_t = phase->type( dividend->in(2) )->isa_long();
1.379 + if( andconl_t && andconl_t->is_con() ) {
1.380 + jlong andconl = andconl_t->get_con();
1.381 + if( andconl < 0 && is_power_of_2_long(-andconl) && (-andconl) >= d ) {
1.382 + if( (-andconl) == d ) // Remove AND if it clears bits which will be shifted
1.383 + dividend = dividend->in(1);
1.384 + needs_rounding = false;
1.385 + }
1.386 + }
1.387 + }
1.388 +
1.389 + // Add rounding to the shift to handle the sign bit
1.390 + int l = log2_long(d-1)+1;
1.391 + if (needs_rounding) {
1.392 + // Divide-by-power-of-2 can be made into a shift, but you have to do
1.393 + // more math for the rounding. You need to add 0 for positive
1.394 + // numbers, and "i-1" for negative numbers. Example: i=4, so the
1.395 + // shift is by 2. You need to add 3 to negative dividends and 0 to
1.396 + // positive ones. So (-7+3)>>2 becomes -1, (-4+3)>>2 becomes -1,
1.397 + // (-2+3)>>2 becomes 0, etc.
1.398 +
1.399 + // Compute 0 or -1, based on sign bit
1.400 + Node *sign = phase->transform(new (phase->C) RShiftLNode(dividend, phase->intcon(N - 1)));
1.401 + // Mask sign bit to the low sign bits
1.402 + Node *round = phase->transform(new (phase->C) URShiftLNode(sign, phase->intcon(N - l)));
1.403 + // Round up before shifting
1.404 + dividend = phase->transform(new (phase->C) AddLNode(dividend, round));
1.405 + }
1.406 +
1.407 + // Shift for division
1.408 + q = new (phase->C) RShiftLNode(dividend, phase->intcon(l));
1.409 +
1.410 + if (!d_pos) {
1.411 + q = new (phase->C) SubLNode(phase->longcon(0), phase->transform(q));
1.412 + }
1.413 + } else if ( !Matcher::use_asm_for_ldiv_by_con(d) ) { // Use hardware DIV instruction when
1.414 + // it is faster than code generated below.
1.415 + // Attempt the jlong constant divide -> multiply transform found in
1.416 + // "Division by Invariant Integers using Multiplication"
1.417 + // by Granlund and Montgomery
1.418 + // See also "Hacker's Delight", chapter 10 by Warren.
1.419 +
1.420 + jlong magic_const;
1.421 + jint shift_const;
1.422 + if (magic_long_divide_constants(d, magic_const, shift_const)) {
1.423 + // Compute the high half of the dividend x magic multiplication
1.424 + Node *mul_hi = phase->transform(long_by_long_mulhi(phase, dividend, magic_const));
1.425 +
1.426 + // The high half of the 128-bit multiply is computed.
1.427 + if (magic_const < 0) {
1.428 + // The magic multiplier is too large for a 64 bit constant. We've adjusted
1.429 + // it down by 2^64, but have to add 1 dividend back in after the multiplication.
1.430 + // This handles the "overflow" case described by Granlund and Montgomery.
1.431 + mul_hi = phase->transform(new (phase->C) AddLNode(dividend, mul_hi));
1.432 + }
1.433 +
1.434 + // Shift over the (adjusted) mulhi
1.435 + if (shift_const != 0) {
1.436 + mul_hi = phase->transform(new (phase->C) RShiftLNode(mul_hi, phase->intcon(shift_const)));
1.437 + }
1.438 +
1.439 + // Get a 0 or -1 from the sign of the dividend.
1.440 + Node *addend0 = mul_hi;
1.441 + Node *addend1 = phase->transform(new (phase->C) RShiftLNode(dividend, phase->intcon(N-1)));
1.442 +
1.443 + // If the divisor is negative, swap the order of the input addends;
1.444 + // this has the effect of negating the quotient.
1.445 + if (!d_pos) {
1.446 + Node *temp = addend0; addend0 = addend1; addend1 = temp;
1.447 + }
1.448 +
1.449 + // Adjust the final quotient by subtracting -1 (adding 1)
1.450 + // from the mul_hi.
1.451 + q = new (phase->C) SubLNode(addend0, addend1);
1.452 + }
1.453 + }
1.454 +
1.455 + return q;
1.456 +}
1.457 +
1.458 +//=============================================================================
1.459 +//------------------------------Identity---------------------------------------
1.460 +// If the divisor is 1, we are an identity on the dividend.
1.461 +Node *DivINode::Identity( PhaseTransform *phase ) {
1.462 + return (phase->type( in(2) )->higher_equal(TypeInt::ONE)) ? in(1) : this;
1.463 +}
1.464 +
1.465 +//------------------------------Idealize---------------------------------------
1.466 +// Divides can be changed to multiplies and/or shifts
1.467 +Node *DivINode::Ideal(PhaseGVN *phase, bool can_reshape) {
1.468 + if (in(0) && remove_dead_region(phase, can_reshape)) return this;
1.469 + // Don't bother trying to transform a dead node
1.470 + if( in(0) && in(0)->is_top() ) return NULL;
1.471 +
1.472 + const Type *t = phase->type( in(2) );
1.473 + if( t == TypeInt::ONE ) // Identity?
1.474 + return NULL; // Skip it
1.475 +
1.476 + const TypeInt *ti = t->isa_int();
1.477 + if( !ti ) return NULL;
1.478 + if( !ti->is_con() ) return NULL;
1.479 + jint i = ti->get_con(); // Get divisor
1.480 +
1.481 + if (i == 0) return NULL; // Dividing by zero constant does not idealize
1.482 +
1.483 + set_req(0,NULL); // Dividing by a not-zero constant; no faulting
1.484 +
1.485 + // Dividing by MININT does not optimize as a power-of-2 shift.
1.486 + if( i == min_jint ) return NULL;
1.487 +
1.488 + return transform_int_divide( phase, in(1), i );
1.489 +}
1.490 +
1.491 +//------------------------------Value------------------------------------------
1.492 +// A DivINode divides its inputs. The third input is a Control input, used to
1.493 +// prevent hoisting the divide above an unsafe test.
1.494 +const Type *DivINode::Value( PhaseTransform *phase ) const {
1.495 + // Either input is TOP ==> the result is TOP
1.496 + const Type *t1 = phase->type( in(1) );
1.497 + const Type *t2 = phase->type( in(2) );
1.498 + if( t1 == Type::TOP ) return Type::TOP;
1.499 + if( t2 == Type::TOP ) return Type::TOP;
1.500 +
1.501 + // x/x == 1 since we always generate the dynamic divisor check for 0.
1.502 + if( phase->eqv( in(1), in(2) ) )
1.503 + return TypeInt::ONE;
1.504 +
1.505 + // Either input is BOTTOM ==> the result is the local BOTTOM
1.506 + const Type *bot = bottom_type();
1.507 + if( (t1 == bot) || (t2 == bot) ||
1.508 + (t1 == Type::BOTTOM) || (t2 == Type::BOTTOM) )
1.509 + return bot;
1.510 +
1.511 + // Divide the two numbers. We approximate.
1.512 + // If divisor is a constant and not zero
1.513 + const TypeInt *i1 = t1->is_int();
1.514 + const TypeInt *i2 = t2->is_int();
1.515 + int widen = MAX2(i1->_widen, i2->_widen);
1.516 +
1.517 + if( i2->is_con() && i2->get_con() != 0 ) {
1.518 + int32 d = i2->get_con(); // Divisor
1.519 + jint lo, hi;
1.520 + if( d >= 0 ) {
1.521 + lo = i1->_lo/d;
1.522 + hi = i1->_hi/d;
1.523 + } else {
1.524 + if( d == -1 && i1->_lo == min_jint ) {
1.525 + // 'min_jint/-1' throws arithmetic exception during compilation
1.526 + lo = min_jint;
1.527 + // do not support holes, 'hi' must go to either min_jint or max_jint:
1.528 + // [min_jint, -10]/[-1,-1] ==> [min_jint] UNION [10,max_jint]
1.529 + hi = i1->_hi == min_jint ? min_jint : max_jint;
1.530 + } else {
1.531 + lo = i1->_hi/d;
1.532 + hi = i1->_lo/d;
1.533 + }
1.534 + }
1.535 + return TypeInt::make(lo, hi, widen);
1.536 + }
1.537 +
1.538 + // If the dividend is a constant
1.539 + if( i1->is_con() ) {
1.540 + int32 d = i1->get_con();
1.541 + if( d < 0 ) {
1.542 + if( d == min_jint ) {
1.543 + // (-min_jint) == min_jint == (min_jint / -1)
1.544 + return TypeInt::make(min_jint, max_jint/2 + 1, widen);
1.545 + } else {
1.546 + return TypeInt::make(d, -d, widen);
1.547 + }
1.548 + }
1.549 + return TypeInt::make(-d, d, widen);
1.550 + }
1.551 +
1.552 + // Otherwise we give up all hope
1.553 + return TypeInt::INT;
1.554 +}
1.555 +
1.556 +
1.557 +//=============================================================================
1.558 +//------------------------------Identity---------------------------------------
1.559 +// If the divisor is 1, we are an identity on the dividend.
1.560 +Node *DivLNode::Identity( PhaseTransform *phase ) {
1.561 + return (phase->type( in(2) )->higher_equal(TypeLong::ONE)) ? in(1) : this;
1.562 +}
1.563 +
1.564 +//------------------------------Idealize---------------------------------------
1.565 +// Dividing by a power of 2 is a shift.
1.566 +Node *DivLNode::Ideal( PhaseGVN *phase, bool can_reshape) {
1.567 + if (in(0) && remove_dead_region(phase, can_reshape)) return this;
1.568 + // Don't bother trying to transform a dead node
1.569 + if( in(0) && in(0)->is_top() ) return NULL;
1.570 +
1.571 + const Type *t = phase->type( in(2) );
1.572 + if( t == TypeLong::ONE ) // Identity?
1.573 + return NULL; // Skip it
1.574 +
1.575 + const TypeLong *tl = t->isa_long();
1.576 + if( !tl ) return NULL;
1.577 + if( !tl->is_con() ) return NULL;
1.578 + jlong l = tl->get_con(); // Get divisor
1.579 +
1.580 + if (l == 0) return NULL; // Dividing by zero constant does not idealize
1.581 +
1.582 + set_req(0,NULL); // Dividing by a not-zero constant; no faulting
1.583 +
1.584 + // Dividing by MINLONG does not optimize as a power-of-2 shift.
1.585 + if( l == min_jlong ) return NULL;
1.586 +
1.587 + return transform_long_divide( phase, in(1), l );
1.588 +}
1.589 +
1.590 +//------------------------------Value------------------------------------------
1.591 +// A DivLNode divides its inputs. The third input is a Control input, used to
1.592 +// prevent hoisting the divide above an unsafe test.
1.593 +const Type *DivLNode::Value( PhaseTransform *phase ) const {
1.594 + // Either input is TOP ==> the result is TOP
1.595 + const Type *t1 = phase->type( in(1) );
1.596 + const Type *t2 = phase->type( in(2) );
1.597 + if( t1 == Type::TOP ) return Type::TOP;
1.598 + if( t2 == Type::TOP ) return Type::TOP;
1.599 +
1.600 + // x/x == 1 since we always generate the dynamic divisor check for 0.
1.601 + if( phase->eqv( in(1), in(2) ) )
1.602 + return TypeLong::ONE;
1.603 +
1.604 + // Either input is BOTTOM ==> the result is the local BOTTOM
1.605 + const Type *bot = bottom_type();
1.606 + if( (t1 == bot) || (t2 == bot) ||
1.607 + (t1 == Type::BOTTOM) || (t2 == Type::BOTTOM) )
1.608 + return bot;
1.609 +
1.610 + // Divide the two numbers. We approximate.
1.611 + // If divisor is a constant and not zero
1.612 + const TypeLong *i1 = t1->is_long();
1.613 + const TypeLong *i2 = t2->is_long();
1.614 + int widen = MAX2(i1->_widen, i2->_widen);
1.615 +
1.616 + if( i2->is_con() && i2->get_con() != 0 ) {
1.617 + jlong d = i2->get_con(); // Divisor
1.618 + jlong lo, hi;
1.619 + if( d >= 0 ) {
1.620 + lo = i1->_lo/d;
1.621 + hi = i1->_hi/d;
1.622 + } else {
1.623 + if( d == CONST64(-1) && i1->_lo == min_jlong ) {
1.624 + // 'min_jlong/-1' throws arithmetic exception during compilation
1.625 + lo = min_jlong;
1.626 + // do not support holes, 'hi' must go to either min_jlong or max_jlong:
1.627 + // [min_jlong, -10]/[-1,-1] ==> [min_jlong] UNION [10,max_jlong]
1.628 + hi = i1->_hi == min_jlong ? min_jlong : max_jlong;
1.629 + } else {
1.630 + lo = i1->_hi/d;
1.631 + hi = i1->_lo/d;
1.632 + }
1.633 + }
1.634 + return TypeLong::make(lo, hi, widen);
1.635 + }
1.636 +
1.637 + // If the dividend is a constant
1.638 + if( i1->is_con() ) {
1.639 + jlong d = i1->get_con();
1.640 + if( d < 0 ) {
1.641 + if( d == min_jlong ) {
1.642 + // (-min_jlong) == min_jlong == (min_jlong / -1)
1.643 + return TypeLong::make(min_jlong, max_jlong/2 + 1, widen);
1.644 + } else {
1.645 + return TypeLong::make(d, -d, widen);
1.646 + }
1.647 + }
1.648 + return TypeLong::make(-d, d, widen);
1.649 + }
1.650 +
1.651 + // Otherwise we give up all hope
1.652 + return TypeLong::LONG;
1.653 +}
1.654 +
1.655 +
1.656 +//=============================================================================
1.657 +//------------------------------Value------------------------------------------
1.658 +// An DivFNode divides its inputs. The third input is a Control input, used to
1.659 +// prevent hoisting the divide above an unsafe test.
1.660 +const Type *DivFNode::Value( PhaseTransform *phase ) const {
1.661 + // Either input is TOP ==> the result is TOP
1.662 + const Type *t1 = phase->type( in(1) );
1.663 + const Type *t2 = phase->type( in(2) );
1.664 + if( t1 == Type::TOP ) return Type::TOP;
1.665 + if( t2 == Type::TOP ) return Type::TOP;
1.666 +
1.667 + // Either input is BOTTOM ==> the result is the local BOTTOM
1.668 + const Type *bot = bottom_type();
1.669 + if( (t1 == bot) || (t2 == bot) ||
1.670 + (t1 == Type::BOTTOM) || (t2 == Type::BOTTOM) )
1.671 + return bot;
1.672 +
1.673 + // x/x == 1, we ignore 0/0.
1.674 + // Note: if t1 and t2 are zero then result is NaN (JVMS page 213)
1.675 + // Does not work for variables because of NaN's
1.676 + if( phase->eqv( in(1), in(2) ) && t1->base() == Type::FloatCon)
1.677 + if (!g_isnan(t1->getf()) && g_isfinite(t1->getf()) && t1->getf() != 0.0) // could be negative ZERO or NaN
1.678 + return TypeF::ONE;
1.679 +
1.680 + if( t2 == TypeF::ONE )
1.681 + return t1;
1.682 +
1.683 + // If divisor is a constant and not zero, divide them numbers
1.684 + if( t1->base() == Type::FloatCon &&
1.685 + t2->base() == Type::FloatCon &&
1.686 + t2->getf() != 0.0 ) // could be negative zero
1.687 + return TypeF::make( t1->getf()/t2->getf() );
1.688 +
1.689 + // If the dividend is a constant zero
1.690 + // Note: if t1 and t2 are zero then result is NaN (JVMS page 213)
1.691 + // Test TypeF::ZERO is not sufficient as it could be negative zero
1.692 +
1.693 + if( t1 == TypeF::ZERO && !g_isnan(t2->getf()) && t2->getf() != 0.0 )
1.694 + return TypeF::ZERO;
1.695 +
1.696 + // Otherwise we give up all hope
1.697 + return Type::FLOAT;
1.698 +}
1.699 +
1.700 +//------------------------------isA_Copy---------------------------------------
1.701 +// Dividing by self is 1.
1.702 +// If the divisor is 1, we are an identity on the dividend.
1.703 +Node *DivFNode::Identity( PhaseTransform *phase ) {
1.704 + return (phase->type( in(2) ) == TypeF::ONE) ? in(1) : this;
1.705 +}
1.706 +
1.707 +
1.708 +//------------------------------Idealize---------------------------------------
1.709 +Node *DivFNode::Ideal(PhaseGVN *phase, bool can_reshape) {
1.710 + if (in(0) && remove_dead_region(phase, can_reshape)) return this;
1.711 + // Don't bother trying to transform a dead node
1.712 + if( in(0) && in(0)->is_top() ) return NULL;
1.713 +
1.714 + const Type *t2 = phase->type( in(2) );
1.715 + if( t2 == TypeF::ONE ) // Identity?
1.716 + return NULL; // Skip it
1.717 +
1.718 + const TypeF *tf = t2->isa_float_constant();
1.719 + if( !tf ) return NULL;
1.720 + if( tf->base() != Type::FloatCon ) return NULL;
1.721 +
1.722 + // Check for out of range values
1.723 + if( tf->is_nan() || !tf->is_finite() ) return NULL;
1.724 +
1.725 + // Get the value
1.726 + float f = tf->getf();
1.727 + int exp;
1.728 +
1.729 + // Only for special case of dividing by a power of 2
1.730 + if( frexp((double)f, &exp) != 0.5 ) return NULL;
1.731 +
1.732 + // Limit the range of acceptable exponents
1.733 + if( exp < -126 || exp > 126 ) return NULL;
1.734 +
1.735 + // Compute the reciprocal
1.736 + float reciprocal = ((float)1.0) / f;
1.737 +
1.738 + assert( frexp((double)reciprocal, &exp) == 0.5, "reciprocal should be power of 2" );
1.739 +
1.740 + // return multiplication by the reciprocal
1.741 + return (new (phase->C) MulFNode(in(1), phase->makecon(TypeF::make(reciprocal))));
1.742 +}
1.743 +
1.744 +//=============================================================================
1.745 +//------------------------------Value------------------------------------------
1.746 +// An DivDNode divides its inputs. The third input is a Control input, used to
1.747 +// prevent hoisting the divide above an unsafe test.
1.748 +const Type *DivDNode::Value( PhaseTransform *phase ) const {
1.749 + // Either input is TOP ==> the result is TOP
1.750 + const Type *t1 = phase->type( in(1) );
1.751 + const Type *t2 = phase->type( in(2) );
1.752 + if( t1 == Type::TOP ) return Type::TOP;
1.753 + if( t2 == Type::TOP ) return Type::TOP;
1.754 +
1.755 + // Either input is BOTTOM ==> the result is the local BOTTOM
1.756 + const Type *bot = bottom_type();
1.757 + if( (t1 == bot) || (t2 == bot) ||
1.758 + (t1 == Type::BOTTOM) || (t2 == Type::BOTTOM) )
1.759 + return bot;
1.760 +
1.761 + // x/x == 1, we ignore 0/0.
1.762 + // Note: if t1 and t2 are zero then result is NaN (JVMS page 213)
1.763 + // Does not work for variables because of NaN's
1.764 + if( phase->eqv( in(1), in(2) ) && t1->base() == Type::DoubleCon)
1.765 + if (!g_isnan(t1->getd()) && g_isfinite(t1->getd()) && t1->getd() != 0.0) // could be negative ZERO or NaN
1.766 + return TypeD::ONE;
1.767 +
1.768 + if( t2 == TypeD::ONE )
1.769 + return t1;
1.770 +
1.771 +#if defined(IA32)
1.772 + if (!phase->C->method()->is_strict())
1.773 + // Can't trust native compilers to properly fold strict double
1.774 + // division with round-to-zero on this platform.
1.775 +#endif
1.776 + {
1.777 + // If divisor is a constant and not zero, divide them numbers
1.778 + if( t1->base() == Type::DoubleCon &&
1.779 + t2->base() == Type::DoubleCon &&
1.780 + t2->getd() != 0.0 ) // could be negative zero
1.781 + return TypeD::make( t1->getd()/t2->getd() );
1.782 + }
1.783 +
1.784 + // If the dividend is a constant zero
1.785 + // Note: if t1 and t2 are zero then result is NaN (JVMS page 213)
1.786 + // Test TypeF::ZERO is not sufficient as it could be negative zero
1.787 + if( t1 == TypeD::ZERO && !g_isnan(t2->getd()) && t2->getd() != 0.0 )
1.788 + return TypeD::ZERO;
1.789 +
1.790 + // Otherwise we give up all hope
1.791 + return Type::DOUBLE;
1.792 +}
1.793 +
1.794 +
1.795 +//------------------------------isA_Copy---------------------------------------
1.796 +// Dividing by self is 1.
1.797 +// If the divisor is 1, we are an identity on the dividend.
1.798 +Node *DivDNode::Identity( PhaseTransform *phase ) {
1.799 + return (phase->type( in(2) ) == TypeD::ONE) ? in(1) : this;
1.800 +}
1.801 +
1.802 +//------------------------------Idealize---------------------------------------
1.803 +Node *DivDNode::Ideal(PhaseGVN *phase, bool can_reshape) {
1.804 + if (in(0) && remove_dead_region(phase, can_reshape)) return this;
1.805 + // Don't bother trying to transform a dead node
1.806 + if( in(0) && in(0)->is_top() ) return NULL;
1.807 +
1.808 + const Type *t2 = phase->type( in(2) );
1.809 + if( t2 == TypeD::ONE ) // Identity?
1.810 + return NULL; // Skip it
1.811 +
1.812 + const TypeD *td = t2->isa_double_constant();
1.813 + if( !td ) return NULL;
1.814 + if( td->base() != Type::DoubleCon ) return NULL;
1.815 +
1.816 + // Check for out of range values
1.817 + if( td->is_nan() || !td->is_finite() ) return NULL;
1.818 +
1.819 + // Get the value
1.820 + double d = td->getd();
1.821 + int exp;
1.822 +
1.823 + // Only for special case of dividing by a power of 2
1.824 + if( frexp(d, &exp) != 0.5 ) return NULL;
1.825 +
1.826 + // Limit the range of acceptable exponents
1.827 + if( exp < -1021 || exp > 1022 ) return NULL;
1.828 +
1.829 + // Compute the reciprocal
1.830 + double reciprocal = 1.0 / d;
1.831 +
1.832 + assert( frexp(reciprocal, &exp) == 0.5, "reciprocal should be power of 2" );
1.833 +
1.834 + // return multiplication by the reciprocal
1.835 + return (new (phase->C) MulDNode(in(1), phase->makecon(TypeD::make(reciprocal))));
1.836 +}
1.837 +
1.838 +//=============================================================================
1.839 +//------------------------------Idealize---------------------------------------
1.840 +Node *ModINode::Ideal(PhaseGVN *phase, bool can_reshape) {
1.841 + // Check for dead control input
1.842 + if( in(0) && remove_dead_region(phase, can_reshape) ) return this;
1.843 + // Don't bother trying to transform a dead node
1.844 + if( in(0) && in(0)->is_top() ) return NULL;
1.845 +
1.846 + // Get the modulus
1.847 + const Type *t = phase->type( in(2) );
1.848 + if( t == Type::TOP ) return NULL;
1.849 + const TypeInt *ti = t->is_int();
1.850 +
1.851 + // Check for useless control input
1.852 + // Check for excluding mod-zero case
1.853 + if( in(0) && (ti->_hi < 0 || ti->_lo > 0) ) {
1.854 + set_req(0, NULL); // Yank control input
1.855 + return this;
1.856 + }
1.857 +
1.858 + // See if we are MOD'ing by 2^k or 2^k-1.
1.859 + if( !ti->is_con() ) return NULL;
1.860 + jint con = ti->get_con();
1.861 +
1.862 + Node *hook = new (phase->C) Node(1);
1.863 +
1.864 + // First, special check for modulo 2^k-1
1.865 + if( con >= 0 && con < max_jint && is_power_of_2(con+1) ) {
1.866 + uint k = exact_log2(con+1); // Extract k
1.867 +
1.868 + // Basic algorithm by David Detlefs. See fastmod_int.java for gory details.
1.869 + static int unroll_factor[] = { 999, 999, 29, 14, 9, 7, 5, 4, 4, 3, 3, 2, 2, 2, 2, 2, 1 /*past here we assume 1 forever*/};
1.870 + int trip_count = 1;
1.871 + if( k < ARRAY_SIZE(unroll_factor)) trip_count = unroll_factor[k];
1.872 +
1.873 + // If the unroll factor is not too large, and if conditional moves are
1.874 + // ok, then use this case
1.875 + if( trip_count <= 5 && ConditionalMoveLimit != 0 ) {
1.876 + Node *x = in(1); // Value being mod'd
1.877 + Node *divisor = in(2); // Also is mask
1.878 +
1.879 + hook->init_req(0, x); // Add a use to x to prevent him from dying
1.880 + // Generate code to reduce X rapidly to nearly 2^k-1.
1.881 + for( int i = 0; i < trip_count; i++ ) {
1.882 + Node *xl = phase->transform( new (phase->C) AndINode(x,divisor) );
1.883 + Node *xh = phase->transform( new (phase->C) RShiftINode(x,phase->intcon(k)) ); // Must be signed
1.884 + x = phase->transform( new (phase->C) AddINode(xh,xl) );
1.885 + hook->set_req(0, x);
1.886 + }
1.887 +
1.888 + // Generate sign-fixup code. Was original value positive?
1.889 + // int hack_res = (i >= 0) ? divisor : 1;
1.890 + Node *cmp1 = phase->transform( new (phase->C) CmpINode( in(1), phase->intcon(0) ) );
1.891 + Node *bol1 = phase->transform( new (phase->C) BoolNode( cmp1, BoolTest::ge ) );
1.892 + Node *cmov1= phase->transform( new (phase->C) CMoveINode(bol1, phase->intcon(1), divisor, TypeInt::POS) );
1.893 + // if( x >= hack_res ) x -= divisor;
1.894 + Node *sub = phase->transform( new (phase->C) SubINode( x, divisor ) );
1.895 + Node *cmp2 = phase->transform( new (phase->C) CmpINode( x, cmov1 ) );
1.896 + Node *bol2 = phase->transform( new (phase->C) BoolNode( cmp2, BoolTest::ge ) );
1.897 + // Convention is to not transform the return value of an Ideal
1.898 + // since Ideal is expected to return a modified 'this' or a new node.
1.899 + Node *cmov2= new (phase->C) CMoveINode(bol2, x, sub, TypeInt::INT);
1.900 + // cmov2 is now the mod
1.901 +
1.902 + // Now remove the bogus extra edges used to keep things alive
1.903 + if (can_reshape) {
1.904 + phase->is_IterGVN()->remove_dead_node(hook);
1.905 + } else {
1.906 + hook->set_req(0, NULL); // Just yank bogus edge during Parse phase
1.907 + }
1.908 + return cmov2;
1.909 + }
1.910 + }
1.911 +
1.912 + // Fell thru, the unroll case is not appropriate. Transform the modulo
1.913 + // into a long multiply/int multiply/subtract case
1.914 +
1.915 + // Cannot handle mod 0, and min_jint isn't handled by the transform
1.916 + if( con == 0 || con == min_jint ) return NULL;
1.917 +
1.918 + // Get the absolute value of the constant; at this point, we can use this
1.919 + jint pos_con = (con >= 0) ? con : -con;
1.920 +
1.921 + // integer Mod 1 is always 0
1.922 + if( pos_con == 1 ) return new (phase->C) ConINode(TypeInt::ZERO);
1.923 +
1.924 + int log2_con = -1;
1.925 +
1.926 + // If this is a power of two, they maybe we can mask it
1.927 + if( is_power_of_2(pos_con) ) {
1.928 + log2_con = log2_intptr((intptr_t)pos_con);
1.929 +
1.930 + const Type *dt = phase->type(in(1));
1.931 + const TypeInt *dti = dt->isa_int();
1.932 +
1.933 + // See if this can be masked, if the dividend is non-negative
1.934 + if( dti && dti->_lo >= 0 )
1.935 + return ( new (phase->C) AndINode( in(1), phase->intcon( pos_con-1 ) ) );
1.936 + }
1.937 +
1.938 + // Save in(1) so that it cannot be changed or deleted
1.939 + hook->init_req(0, in(1));
1.940 +
1.941 + // Divide using the transform from DivI to MulL
1.942 + Node *result = transform_int_divide( phase, in(1), pos_con );
1.943 + if (result != NULL) {
1.944 + Node *divide = phase->transform(result);
1.945 +
1.946 + // Re-multiply, using a shift if this is a power of two
1.947 + Node *mult = NULL;
1.948 +
1.949 + if( log2_con >= 0 )
1.950 + mult = phase->transform( new (phase->C) LShiftINode( divide, phase->intcon( log2_con ) ) );
1.951 + else
1.952 + mult = phase->transform( new (phase->C) MulINode( divide, phase->intcon( pos_con ) ) );
1.953 +
1.954 + // Finally, subtract the multiplied divided value from the original
1.955 + result = new (phase->C) SubINode( in(1), mult );
1.956 + }
1.957 +
1.958 + // Now remove the bogus extra edges used to keep things alive
1.959 + if (can_reshape) {
1.960 + phase->is_IterGVN()->remove_dead_node(hook);
1.961 + } else {
1.962 + hook->set_req(0, NULL); // Just yank bogus edge during Parse phase
1.963 + }
1.964 +
1.965 + // return the value
1.966 + return result;
1.967 +}
1.968 +
1.969 +//------------------------------Value------------------------------------------
1.970 +const Type *ModINode::Value( PhaseTransform *phase ) const {
1.971 + // Either input is TOP ==> the result is TOP
1.972 + const Type *t1 = phase->type( in(1) );
1.973 + const Type *t2 = phase->type( in(2) );
1.974 + if( t1 == Type::TOP ) return Type::TOP;
1.975 + if( t2 == Type::TOP ) return Type::TOP;
1.976 +
1.977 + // We always generate the dynamic check for 0.
1.978 + // 0 MOD X is 0
1.979 + if( t1 == TypeInt::ZERO ) return TypeInt::ZERO;
1.980 + // X MOD X is 0
1.981 + if( phase->eqv( in(1), in(2) ) ) return TypeInt::ZERO;
1.982 +
1.983 + // Either input is BOTTOM ==> the result is the local BOTTOM
1.984 + const Type *bot = bottom_type();
1.985 + if( (t1 == bot) || (t2 == bot) ||
1.986 + (t1 == Type::BOTTOM) || (t2 == Type::BOTTOM) )
1.987 + return bot;
1.988 +
1.989 + const TypeInt *i1 = t1->is_int();
1.990 + const TypeInt *i2 = t2->is_int();
1.991 + if( !i1->is_con() || !i2->is_con() ) {
1.992 + if( i1->_lo >= 0 && i2->_lo >= 0 )
1.993 + return TypeInt::POS;
1.994 + // If both numbers are not constants, we know little.
1.995 + return TypeInt::INT;
1.996 + }
1.997 + // Mod by zero? Throw exception at runtime!
1.998 + if( !i2->get_con() ) return TypeInt::POS;
1.999 +
1.1000 + // We must be modulo'ing 2 float constants.
1.1001 + // Check for min_jint % '-1', result is defined to be '0'.
1.1002 + if( i1->get_con() == min_jint && i2->get_con() == -1 )
1.1003 + return TypeInt::ZERO;
1.1004 +
1.1005 + return TypeInt::make( i1->get_con() % i2->get_con() );
1.1006 +}
1.1007 +
1.1008 +
1.1009 +//=============================================================================
1.1010 +//------------------------------Idealize---------------------------------------
1.1011 +Node *ModLNode::Ideal(PhaseGVN *phase, bool can_reshape) {
1.1012 + // Check for dead control input
1.1013 + if( in(0) && remove_dead_region(phase, can_reshape) ) return this;
1.1014 + // Don't bother trying to transform a dead node
1.1015 + if( in(0) && in(0)->is_top() ) return NULL;
1.1016 +
1.1017 + // Get the modulus
1.1018 + const Type *t = phase->type( in(2) );
1.1019 + if( t == Type::TOP ) return NULL;
1.1020 + const TypeLong *tl = t->is_long();
1.1021 +
1.1022 + // Check for useless control input
1.1023 + // Check for excluding mod-zero case
1.1024 + if( in(0) && (tl->_hi < 0 || tl->_lo > 0) ) {
1.1025 + set_req(0, NULL); // Yank control input
1.1026 + return this;
1.1027 + }
1.1028 +
1.1029 + // See if we are MOD'ing by 2^k or 2^k-1.
1.1030 + if( !tl->is_con() ) return NULL;
1.1031 + jlong con = tl->get_con();
1.1032 +
1.1033 + Node *hook = new (phase->C) Node(1);
1.1034 +
1.1035 + // Expand mod
1.1036 + if( con >= 0 && con < max_jlong && is_power_of_2_long(con+1) ) {
1.1037 + uint k = exact_log2_long(con+1); // Extract k
1.1038 +
1.1039 + // Basic algorithm by David Detlefs. See fastmod_long.java for gory details.
1.1040 + // Used to help a popular random number generator which does a long-mod
1.1041 + // of 2^31-1 and shows up in SpecJBB and SciMark.
1.1042 + static int unroll_factor[] = { 999, 999, 61, 30, 20, 15, 12, 10, 8, 7, 6, 6, 5, 5, 4, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1 /*past here we assume 1 forever*/};
1.1043 + int trip_count = 1;
1.1044 + if( k < ARRAY_SIZE(unroll_factor)) trip_count = unroll_factor[k];
1.1045 +
1.1046 + // If the unroll factor is not too large, and if conditional moves are
1.1047 + // ok, then use this case
1.1048 + if( trip_count <= 5 && ConditionalMoveLimit != 0 ) {
1.1049 + Node *x = in(1); // Value being mod'd
1.1050 + Node *divisor = in(2); // Also is mask
1.1051 +
1.1052 + hook->init_req(0, x); // Add a use to x to prevent him from dying
1.1053 + // Generate code to reduce X rapidly to nearly 2^k-1.
1.1054 + for( int i = 0; i < trip_count; i++ ) {
1.1055 + Node *xl = phase->transform( new (phase->C) AndLNode(x,divisor) );
1.1056 + Node *xh = phase->transform( new (phase->C) RShiftLNode(x,phase->intcon(k)) ); // Must be signed
1.1057 + x = phase->transform( new (phase->C) AddLNode(xh,xl) );
1.1058 + hook->set_req(0, x); // Add a use to x to prevent him from dying
1.1059 + }
1.1060 +
1.1061 + // Generate sign-fixup code. Was original value positive?
1.1062 + // long hack_res = (i >= 0) ? divisor : CONST64(1);
1.1063 + Node *cmp1 = phase->transform( new (phase->C) CmpLNode( in(1), phase->longcon(0) ) );
1.1064 + Node *bol1 = phase->transform( new (phase->C) BoolNode( cmp1, BoolTest::ge ) );
1.1065 + Node *cmov1= phase->transform( new (phase->C) CMoveLNode(bol1, phase->longcon(1), divisor, TypeLong::LONG) );
1.1066 + // if( x >= hack_res ) x -= divisor;
1.1067 + Node *sub = phase->transform( new (phase->C) SubLNode( x, divisor ) );
1.1068 + Node *cmp2 = phase->transform( new (phase->C) CmpLNode( x, cmov1 ) );
1.1069 + Node *bol2 = phase->transform( new (phase->C) BoolNode( cmp2, BoolTest::ge ) );
1.1070 + // Convention is to not transform the return value of an Ideal
1.1071 + // since Ideal is expected to return a modified 'this' or a new node.
1.1072 + Node *cmov2= new (phase->C) CMoveLNode(bol2, x, sub, TypeLong::LONG);
1.1073 + // cmov2 is now the mod
1.1074 +
1.1075 + // Now remove the bogus extra edges used to keep things alive
1.1076 + if (can_reshape) {
1.1077 + phase->is_IterGVN()->remove_dead_node(hook);
1.1078 + } else {
1.1079 + hook->set_req(0, NULL); // Just yank bogus edge during Parse phase
1.1080 + }
1.1081 + return cmov2;
1.1082 + }
1.1083 + }
1.1084 +
1.1085 + // Fell thru, the unroll case is not appropriate. Transform the modulo
1.1086 + // into a long multiply/int multiply/subtract case
1.1087 +
1.1088 + // Cannot handle mod 0, and min_jlong isn't handled by the transform
1.1089 + if( con == 0 || con == min_jlong ) return NULL;
1.1090 +
1.1091 + // Get the absolute value of the constant; at this point, we can use this
1.1092 + jlong pos_con = (con >= 0) ? con : -con;
1.1093 +
1.1094 + // integer Mod 1 is always 0
1.1095 + if( pos_con == 1 ) return new (phase->C) ConLNode(TypeLong::ZERO);
1.1096 +
1.1097 + int log2_con = -1;
1.1098 +
1.1099 + // If this is a power of two, then maybe we can mask it
1.1100 + if( is_power_of_2_long(pos_con) ) {
1.1101 + log2_con = exact_log2_long(pos_con);
1.1102 +
1.1103 + const Type *dt = phase->type(in(1));
1.1104 + const TypeLong *dtl = dt->isa_long();
1.1105 +
1.1106 + // See if this can be masked, if the dividend is non-negative
1.1107 + if( dtl && dtl->_lo >= 0 )
1.1108 + return ( new (phase->C) AndLNode( in(1), phase->longcon( pos_con-1 ) ) );
1.1109 + }
1.1110 +
1.1111 + // Save in(1) so that it cannot be changed or deleted
1.1112 + hook->init_req(0, in(1));
1.1113 +
1.1114 + // Divide using the transform from DivL to MulL
1.1115 + Node *result = transform_long_divide( phase, in(1), pos_con );
1.1116 + if (result != NULL) {
1.1117 + Node *divide = phase->transform(result);
1.1118 +
1.1119 + // Re-multiply, using a shift if this is a power of two
1.1120 + Node *mult = NULL;
1.1121 +
1.1122 + if( log2_con >= 0 )
1.1123 + mult = phase->transform( new (phase->C) LShiftLNode( divide, phase->intcon( log2_con ) ) );
1.1124 + else
1.1125 + mult = phase->transform( new (phase->C) MulLNode( divide, phase->longcon( pos_con ) ) );
1.1126 +
1.1127 + // Finally, subtract the multiplied divided value from the original
1.1128 + result = new (phase->C) SubLNode( in(1), mult );
1.1129 + }
1.1130 +
1.1131 + // Now remove the bogus extra edges used to keep things alive
1.1132 + if (can_reshape) {
1.1133 + phase->is_IterGVN()->remove_dead_node(hook);
1.1134 + } else {
1.1135 + hook->set_req(0, NULL); // Just yank bogus edge during Parse phase
1.1136 + }
1.1137 +
1.1138 + // return the value
1.1139 + return result;
1.1140 +}
1.1141 +
1.1142 +//------------------------------Value------------------------------------------
1.1143 +const Type *ModLNode::Value( PhaseTransform *phase ) const {
1.1144 + // Either input is TOP ==> the result is TOP
1.1145 + const Type *t1 = phase->type( in(1) );
1.1146 + const Type *t2 = phase->type( in(2) );
1.1147 + if( t1 == Type::TOP ) return Type::TOP;
1.1148 + if( t2 == Type::TOP ) return Type::TOP;
1.1149 +
1.1150 + // We always generate the dynamic check for 0.
1.1151 + // 0 MOD X is 0
1.1152 + if( t1 == TypeLong::ZERO ) return TypeLong::ZERO;
1.1153 + // X MOD X is 0
1.1154 + if( phase->eqv( in(1), in(2) ) ) return TypeLong::ZERO;
1.1155 +
1.1156 + // Either input is BOTTOM ==> the result is the local BOTTOM
1.1157 + const Type *bot = bottom_type();
1.1158 + if( (t1 == bot) || (t2 == bot) ||
1.1159 + (t1 == Type::BOTTOM) || (t2 == Type::BOTTOM) )
1.1160 + return bot;
1.1161 +
1.1162 + const TypeLong *i1 = t1->is_long();
1.1163 + const TypeLong *i2 = t2->is_long();
1.1164 + if( !i1->is_con() || !i2->is_con() ) {
1.1165 + if( i1->_lo >= CONST64(0) && i2->_lo >= CONST64(0) )
1.1166 + return TypeLong::POS;
1.1167 + // If both numbers are not constants, we know little.
1.1168 + return TypeLong::LONG;
1.1169 + }
1.1170 + // Mod by zero? Throw exception at runtime!
1.1171 + if( !i2->get_con() ) return TypeLong::POS;
1.1172 +
1.1173 + // We must be modulo'ing 2 float constants.
1.1174 + // Check for min_jint % '-1', result is defined to be '0'.
1.1175 + if( i1->get_con() == min_jlong && i2->get_con() == -1 )
1.1176 + return TypeLong::ZERO;
1.1177 +
1.1178 + return TypeLong::make( i1->get_con() % i2->get_con() );
1.1179 +}
1.1180 +
1.1181 +
1.1182 +//=============================================================================
1.1183 +//------------------------------Value------------------------------------------
1.1184 +const Type *ModFNode::Value( PhaseTransform *phase ) const {
1.1185 + // Either input is TOP ==> the result is TOP
1.1186 + const Type *t1 = phase->type( in(1) );
1.1187 + const Type *t2 = phase->type( in(2) );
1.1188 + if( t1 == Type::TOP ) return Type::TOP;
1.1189 + if( t2 == Type::TOP ) return Type::TOP;
1.1190 +
1.1191 + // Either input is BOTTOM ==> the result is the local BOTTOM
1.1192 + const Type *bot = bottom_type();
1.1193 + if( (t1 == bot) || (t2 == bot) ||
1.1194 + (t1 == Type::BOTTOM) || (t2 == Type::BOTTOM) )
1.1195 + return bot;
1.1196 +
1.1197 + // If either number is not a constant, we know nothing.
1.1198 + if ((t1->base() != Type::FloatCon) || (t2->base() != Type::FloatCon)) {
1.1199 + return Type::FLOAT; // note: x%x can be either NaN or 0
1.1200 + }
1.1201 +
1.1202 + float f1 = t1->getf();
1.1203 + float f2 = t2->getf();
1.1204 + jint x1 = jint_cast(f1); // note: *(int*)&f1, not just (int)f1
1.1205 + jint x2 = jint_cast(f2);
1.1206 +
1.1207 + // If either is a NaN, return an input NaN
1.1208 + if (g_isnan(f1)) return t1;
1.1209 + if (g_isnan(f2)) return t2;
1.1210 +
1.1211 + // If an operand is infinity or the divisor is +/- zero, punt.
1.1212 + if (!g_isfinite(f1) || !g_isfinite(f2) || x2 == 0 || x2 == min_jint)
1.1213 + return Type::FLOAT;
1.1214 +
1.1215 + // We must be modulo'ing 2 float constants.
1.1216 + // Make sure that the sign of the fmod is equal to the sign of the dividend
1.1217 + jint xr = jint_cast(fmod(f1, f2));
1.1218 + if ((x1 ^ xr) < 0) {
1.1219 + xr ^= min_jint;
1.1220 + }
1.1221 +
1.1222 + return TypeF::make(jfloat_cast(xr));
1.1223 +}
1.1224 +
1.1225 +
1.1226 +//=============================================================================
1.1227 +//------------------------------Value------------------------------------------
1.1228 +const Type *ModDNode::Value( PhaseTransform *phase ) const {
1.1229 + // Either input is TOP ==> the result is TOP
1.1230 + const Type *t1 = phase->type( in(1) );
1.1231 + const Type *t2 = phase->type( in(2) );
1.1232 + if( t1 == Type::TOP ) return Type::TOP;
1.1233 + if( t2 == Type::TOP ) return Type::TOP;
1.1234 +
1.1235 + // Either input is BOTTOM ==> the result is the local BOTTOM
1.1236 + const Type *bot = bottom_type();
1.1237 + if( (t1 == bot) || (t2 == bot) ||
1.1238 + (t1 == Type::BOTTOM) || (t2 == Type::BOTTOM) )
1.1239 + return bot;
1.1240 +
1.1241 + // If either number is not a constant, we know nothing.
1.1242 + if ((t1->base() != Type::DoubleCon) || (t2->base() != Type::DoubleCon)) {
1.1243 + return Type::DOUBLE; // note: x%x can be either NaN or 0
1.1244 + }
1.1245 +
1.1246 + double f1 = t1->getd();
1.1247 + double f2 = t2->getd();
1.1248 + jlong x1 = jlong_cast(f1); // note: *(long*)&f1, not just (long)f1
1.1249 + jlong x2 = jlong_cast(f2);
1.1250 +
1.1251 + // If either is a NaN, return an input NaN
1.1252 + if (g_isnan(f1)) return t1;
1.1253 + if (g_isnan(f2)) return t2;
1.1254 +
1.1255 + // If an operand is infinity or the divisor is +/- zero, punt.
1.1256 + if (!g_isfinite(f1) || !g_isfinite(f2) || x2 == 0 || x2 == min_jlong)
1.1257 + return Type::DOUBLE;
1.1258 +
1.1259 + // We must be modulo'ing 2 double constants.
1.1260 + // Make sure that the sign of the fmod is equal to the sign of the dividend
1.1261 + jlong xr = jlong_cast(fmod(f1, f2));
1.1262 + if ((x1 ^ xr) < 0) {
1.1263 + xr ^= min_jlong;
1.1264 + }
1.1265 +
1.1266 + return TypeD::make(jdouble_cast(xr));
1.1267 +}
1.1268 +
1.1269 +//=============================================================================
1.1270 +
1.1271 +DivModNode::DivModNode( Node *c, Node *dividend, Node *divisor ) : MultiNode(3) {
1.1272 + init_req(0, c);
1.1273 + init_req(1, dividend);
1.1274 + init_req(2, divisor);
1.1275 +}
1.1276 +
1.1277 +//------------------------------make------------------------------------------
1.1278 +DivModINode* DivModINode::make(Compile* C, Node* div_or_mod) {
1.1279 + Node* n = div_or_mod;
1.1280 + assert(n->Opcode() == Op_DivI || n->Opcode() == Op_ModI,
1.1281 + "only div or mod input pattern accepted");
1.1282 +
1.1283 + DivModINode* divmod = new (C) DivModINode(n->in(0), n->in(1), n->in(2));
1.1284 + Node* dproj = new (C) ProjNode(divmod, DivModNode::div_proj_num);
1.1285 + Node* mproj = new (C) ProjNode(divmod, DivModNode::mod_proj_num);
1.1286 + return divmod;
1.1287 +}
1.1288 +
1.1289 +//------------------------------make------------------------------------------
1.1290 +DivModLNode* DivModLNode::make(Compile* C, Node* div_or_mod) {
1.1291 + Node* n = div_or_mod;
1.1292 + assert(n->Opcode() == Op_DivL || n->Opcode() == Op_ModL,
1.1293 + "only div or mod input pattern accepted");
1.1294 +
1.1295 + DivModLNode* divmod = new (C) DivModLNode(n->in(0), n->in(1), n->in(2));
1.1296 + Node* dproj = new (C) ProjNode(divmod, DivModNode::div_proj_num);
1.1297 + Node* mproj = new (C) ProjNode(divmod, DivModNode::mod_proj_num);
1.1298 + return divmod;
1.1299 +}
1.1300 +
1.1301 +//------------------------------match------------------------------------------
1.1302 +// return result(s) along with their RegMask info
1.1303 +Node *DivModINode::match( const ProjNode *proj, const Matcher *match ) {
1.1304 + uint ideal_reg = proj->ideal_reg();
1.1305 + RegMask rm;
1.1306 + if (proj->_con == div_proj_num) {
1.1307 + rm = match->divI_proj_mask();
1.1308 + } else {
1.1309 + assert(proj->_con == mod_proj_num, "must be div or mod projection");
1.1310 + rm = match->modI_proj_mask();
1.1311 + }
1.1312 + return new (match->C)MachProjNode(this, proj->_con, rm, ideal_reg);
1.1313 +}
1.1314 +
1.1315 +
1.1316 +//------------------------------match------------------------------------------
1.1317 +// return result(s) along with their RegMask info
1.1318 +Node *DivModLNode::match( const ProjNode *proj, const Matcher *match ) {
1.1319 + uint ideal_reg = proj->ideal_reg();
1.1320 + RegMask rm;
1.1321 + if (proj->_con == div_proj_num) {
1.1322 + rm = match->divL_proj_mask();
1.1323 + } else {
1.1324 + assert(proj->_con == mod_proj_num, "must be div or mod projection");
1.1325 + rm = match->modL_proj_mask();
1.1326 + }
1.1327 + return new (match->C)MachProjNode(this, proj->_con, rm, ideal_reg);
1.1328 +}
