1 /*
   2  * Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  *
  23  */
  24 
  25 #include "precompiled.hpp"
  26 #include "memory/allocation.inline.hpp"
  27 #include "opto/addnode.hpp"
  28 #include "opto/cfgnode.hpp"
  29 #include "opto/machnode.hpp"
  30 #include "opto/matcher.hpp"
  31 #include "opto/mathexactnode.hpp"
  32 #include "opto/subnode.hpp"
  33 
  34 MathExactNode::MathExactNode(Node* ctrl, Node* in1) : MultiNode(2) {
  35   init_class_id(Class_MathExact);
  36   init_req(0, ctrl);
  37   init_req(1, in1);
  38 }
  39 
  40 MathExactNode::MathExactNode(Node* ctrl, Node* in1, Node* in2) : MultiNode(3) {
  41   init_class_id(Class_MathExact);
  42   init_req(0, ctrl);
  43   init_req(1, in1);
  44   init_req(2, in2);
  45 }
  46 
  47 BoolNode* MathExactNode::bool_node() const {
  48   Node* flags = flags_node();
  49   BoolNode* boolnode = flags->unique_out()->as_Bool();
  50   assert(boolnode != NULL, "must have BoolNode");
  51   return boolnode;
  52 }
  53 
  54 IfNode* MathExactNode::if_node() const {
  55   BoolNode* boolnode = bool_node();
  56   IfNode* ifnode = boolnode->unique_out()->as_If();
  57   assert(ifnode != NULL, "must have IfNode");
  58   return ifnode;
  59 }
  60 
  61 Node* MathExactNode::control_node() const {
  62   IfNode* ifnode = if_node();
  63   return ifnode->in(0);
  64 }
  65 
  66 Node* MathExactNode::non_throwing_branch() const {
  67   IfNode* ifnode = if_node();
  68   if (bool_node()->_test._test == BoolTest::overflow) {
  69     return ifnode->proj_out(0);
  70   }
  71   return ifnode->proj_out(1);
  72 }
  73 
  74 // If the MathExactNode won't overflow we have to replace the
  75 // FlagsProjNode and ProjNode that is generated by the MathExactNode
  76 Node* MathExactNode::no_overflow(PhaseGVN* phase, Node* new_result) {
  77   PhaseIterGVN* igvn = phase->is_IterGVN();
  78   if (igvn) {
  79     ProjNode* result = result_node();
  80     ProjNode* flags = flags_node();
  81 
  82     if (result != NULL) {
  83       igvn->replace_node(result, new_result);
  84     }
  85 
  86     if (flags != NULL) {
  87       BoolNode* boolnode = bool_node();
  88       switch (boolnode->_test._test) {
  89         case BoolTest::overflow:
  90           // if the check is for overflow - never taken
  91           igvn->replace_node(boolnode, phase->intcon(0));
  92           break;
  93         case BoolTest::no_overflow:
  94           // if the check is for no overflow - always taken
  95           igvn->replace_node(boolnode, phase->intcon(1));
  96           break;
  97         default:
  98           fatal("Unexpected value of BoolTest");
  99           break;
 100       }
 101       flags->del_req(0);
 102     }
 103   }
 104   return new_result;
 105 }
 106 
 107 Node* MathExactINode::match(const ProjNode* proj, const Matcher* m) {
 108   uint ideal_reg = proj->ideal_reg();
 109   RegMask rm;
 110   if (proj->_con == result_proj_node) {
 111     rm = m->mathExactI_result_proj_mask();
 112   } else {
 113     assert(proj->_con == flags_proj_node, "must be result or flags");
 114     assert(ideal_reg == Op_RegFlags, "sanity");
 115     rm = m->mathExactI_flags_proj_mask();
 116   }
 117   return new (m->C) MachProjNode(this, proj->_con, rm, ideal_reg);
 118 }
 119 
 120 Node* MathExactLNode::match(const ProjNode* proj, const Matcher* m) {
 121   uint ideal_reg = proj->ideal_reg();
 122   RegMask rm;
 123   if (proj->_con == result_proj_node) {
 124     rm = m->mathExactL_result_proj_mask();
 125   } else {
 126     assert(proj->_con == flags_proj_node, "must be result or flags");
 127     assert(ideal_reg == Op_RegFlags, "sanity");
 128     rm = m->mathExactI_flags_proj_mask();
 129   }
 130   return new (m->C) MachProjNode(this, proj->_con, rm, ideal_reg);
 131 }
 132 
 133 Node* AddExactINode::Ideal(PhaseGVN* phase, bool can_reshape) {
 134   Node* arg1 = in(1);
 135   Node* arg2 = in(2);
 136 
 137   const Type* type1 = phase->type(arg1);
 138   const Type* type2 = phase->type(arg2);
 139 
 140   if (type1 != Type::TOP && type1->singleton() &&
 141       type2 != Type::TOP && type2->singleton()) {
 142     jint val1 = arg1->get_int();
 143     jint val2 = arg2->get_int();
 144     jint result = val1 + val2;
 145     // Hacker's Delight 2-12 Overflow if both arguments have the opposite sign of the result
 146     if ( (((val1 ^ result) & (val2 ^ result)) >= 0)) {
 147       Node* con_result = ConINode::make(phase->C, result);
 148       return no_overflow(phase, con_result);
 149     }
 150     return NULL;
 151   }
 152 
 153   if (type1 == TypeInt::ZERO || type2 == TypeInt::ZERO) { // (Add 0 x) == x
 154     Node* add_result = new (phase->C) AddINode(arg1, arg2);
 155     return no_overflow(phase, add_result);
 156   }
 157 
 158   if (type2->singleton()) {
 159     return NULL; // no change - keep constant on the right
 160   }
 161 
 162   if (type1->singleton()) {
 163     // Make it x + Constant - move constant to the right
 164     swap_edges(1, 2);
 165     return this;
 166   }
 167 
 168   if (arg2->is_Load()) {
 169     return NULL; // no change - keep load on the right
 170   }
 171 
 172   if (arg1->is_Load()) {
 173     // Make it x + Load - move load to the right
 174     swap_edges(1, 2);
 175     return this;
 176   }
 177 
 178   if (arg1->_idx > arg2->_idx) {
 179     // Sort the edges
 180     swap_edges(1, 2);
 181     return this;
 182   }
 183 
 184   return NULL;
 185 }
 186 
 187 Node* AddExactLNode::Ideal(PhaseGVN* phase, bool can_reshape) {
 188   Node* arg1 = in(1);
 189   Node* arg2 = in(2);
 190 
 191   const Type* type1 = phase->type(arg1);
 192   const Type* type2 = phase->type(arg2);
 193 
 194   if (type1 != Type::TOP && type1->singleton() &&
 195       type2 != Type::TOP && type2->singleton()) {
 196     jlong val1 = arg1->get_long();
 197     jlong val2 = arg2->get_long();
 198     jlong result = val1 + val2;
 199     // Hacker's Delight 2-12 Overflow if both arguments have the opposite sign of the result
 200     if ( (((val1 ^ result) & (val2 ^ result)) >= 0)) {
 201       Node* con_result = ConLNode::make(phase->C, result);
 202       return no_overflow(phase, con_result);
 203     }
 204     return NULL;
 205   }
 206 
 207   if (type1 == TypeLong::ZERO || type2 == TypeLong::ZERO) { // (Add 0 x) == x
 208     Node* add_result = new (phase->C) AddLNode(arg1, arg2);
 209     return no_overflow(phase, add_result);
 210   }
 211 
 212   if (type2->singleton()) {
 213     return NULL; // no change - keep constant on the right
 214   }
 215 
 216   if (type1->singleton()) {
 217     // Make it x + Constant - move constant to the right
 218     swap_edges(1, 2);
 219     return this;
 220   }
 221 
 222   if (arg2->is_Load()) {
 223     return NULL; // no change - keep load on the right
 224   }
 225 
 226   if (arg1->is_Load()) {
 227     // Make it x + Load - move load to the right
 228     swap_edges(1, 2);
 229     return this;
 230   }
 231 
 232   if (arg1->_idx > arg2->_idx) {
 233     // Sort the edges
 234     swap_edges(1, 2);
 235     return this;
 236   }
 237 
 238   return NULL;
 239 }
 240 
 241 Node* SubExactINode::Ideal(PhaseGVN* phase, bool can_reshape) {
 242   Node* arg1 = in(1);
 243   Node* arg2 = in(2);
 244 
 245   const Type* type1 = phase->type(arg1);
 246   const Type* type2 = phase->type(arg2);
 247 
 248   if (type1 != Type::TOP && type1->singleton() &&
 249       type2 != Type::TOP && type2->singleton()) {
 250     jint val1 = arg1->get_int();
 251     jint val2 = arg2->get_int();
 252     jint result = val1 - val2;
 253 
 254     // Hacker's Delight 2-12 Overflow iff the arguments have different signs and
 255     // the sign of the result is different than the sign of arg1
 256     if (((val1 ^ val2) & (val1 ^ result)) >= 0) {
 257       Node* con_result = ConINode::make(phase->C, result);
 258       return no_overflow(phase, con_result);
 259     }
 260     return NULL;
 261   }
 262 
 263   if (type1 == TypeInt::ZERO || type2 == TypeInt::ZERO) {
 264     // Sub with zero is the same as add with zero
 265     Node* add_result = new (phase->C) AddINode(arg1, arg2);
 266     return no_overflow(phase, add_result);
 267   }
 268 
 269   return NULL;
 270 }
 271 
 272 Node* SubExactLNode::Ideal(PhaseGVN* phase, bool can_reshape) {
 273   Node* arg1 = in(1);
 274   Node* arg2 = in(2);
 275 
 276   const Type* type1 = phase->type(arg1);
 277   const Type* type2 = phase->type(arg2);
 278 
 279   if (type1 != Type::TOP && type1->singleton() &&
 280       type2 != Type::TOP && type2->singleton()) {
 281     jlong val1 = arg1->get_long();
 282     jlong val2 = arg2->get_long();
 283     jlong result = val1 - val2;
 284 
 285     // Hacker's Delight 2-12 Overflow iff the arguments have different signs and
 286     // the sign of the result is different than the sign of arg1
 287     if (((val1 ^ val2) & (val1 ^ result)) >= 0) {
 288       Node* con_result = ConLNode::make(phase->C, result);
 289       return no_overflow(phase, con_result);
 290     }
 291     return NULL;
 292   }
 293 
 294   if (type1 == TypeLong::ZERO || type2 == TypeLong::ZERO) {
 295     // Sub with zero is the same as add with zero
 296     Node* add_result = new (phase->C) AddLNode(arg1, arg2);
 297     return no_overflow(phase, add_result);
 298   }
 299 
 300   return NULL;
 301 }
 302 
 303 Node* NegExactINode::Ideal(PhaseGVN* phase, bool can_reshape) {
 304   Node *arg = in(1);
 305 
 306   const Type* type = phase->type(arg);
 307   if (type != Type::TOP && type->singleton()) {
 308     jint value = arg->get_int();
 309     if (value != min_jint) {
 310       Node* neg_result = ConINode::make(phase->C, -value);
 311       return no_overflow(phase, neg_result);
 312     }
 313   }
 314   return NULL;
 315 }
 316 
 317 Node* NegExactLNode::Ideal(PhaseGVN* phase, bool can_reshape) {
 318   Node *arg = in(1);
 319 
 320   const Type* type = phase->type(arg);
 321   if (type != Type::TOP && type->singleton()) {
 322     jlong value = arg->get_long();
 323     if (value != min_jlong) {
 324       Node* neg_result = ConLNode::make(phase->C, -value);
 325       return no_overflow(phase, neg_result);
 326     }
 327   }
 328   return NULL;
 329 }
 330 
 331 Node* MulExactINode::Ideal(PhaseGVN* phase, bool can_reshape) {
 332   Node* arg1 = in(1);
 333   Node* arg2 = in(2);
 334 
 335   const Type* type1 = phase->type(arg1);
 336   const Type* type2 = phase->type(arg2);
 337 
 338   if (type1 != Type::TOP && type1->singleton() &&
 339       type2 != Type::TOP && type2->singleton()) {
 340     jint val1 = arg1->get_int();
 341     jint val2 = arg2->get_int();
 342     jlong result = (jlong) val1 * (jlong) val2;
 343     if ((jint) result == result) {
 344       // no overflow
 345       Node* mul_result = ConINode::make(phase->C, result);
 346       return no_overflow(phase, mul_result);
 347     }
 348   }
 349 
 350   if (type1 == TypeInt::ZERO || type2 == TypeInt::ZERO) {
 351     return no_overflow(phase, ConINode::make(phase->C, 0));
 352   }
 353 
 354   if (type1 == TypeInt::ONE) {
 355     Node* mul_result = new (phase->C) AddINode(arg2, phase->intcon(0));
 356     return no_overflow(phase, mul_result);
 357   }
 358   if (type2 == TypeInt::ONE) {
 359     Node* mul_result = new (phase->C) AddINode(arg1, phase->intcon(0));
 360     return no_overflow(phase, mul_result);
 361   }
 362 
 363   if (type1 == TypeInt::MINUS_1) {
 364     return new (phase->C) NegExactINode(NULL, arg2);
 365   }
 366 
 367   if (type2 == TypeInt::MINUS_1) {
 368     return new (phase->C) NegExactINode(NULL, arg1);
 369   }
 370 
 371   return NULL;
 372 }
 373 
 374 Node* MulExactLNode::Ideal(PhaseGVN* phase, bool can_reshape) {
 375   Node* arg1 = in(1);
 376   Node* arg2 = in(2);
 377 
 378   const Type* type1 = phase->type(arg1);
 379   const Type* type2 = phase->type(arg2);
 380 
 381   if (type1 != Type::TOP && type1->singleton() &&
 382       type2 != Type::TOP && type2->singleton()) {
 383     jlong val1 = arg1->get_long();
 384     jlong val2 = arg2->get_long();
 385 
 386     jlong result = val1 * val2;
 387     jlong ax = (val1 < 0 ? -val1 : val1);
 388     jlong ay = (val2 < 0 ? -val2 : val2);
 389 
 390     bool overflow = false;
 391     if ((ax | ay) & CONST64(0xFFFFFFFF00000000)) {
 392       // potential overflow if any bit in upper 32 bits are set
 393       if ((val1 == min_jlong && val2 == -1) || (val2 == min_jlong && val1 == -1)) {
 394         // -1 * Long.MIN_VALUE will overflow
 395         overflow = true;
 396       } else if (val2 != 0 && (result / val2 != val1)) {
 397         overflow = true;
 398       }
 399     }
 400 
 401     if (!overflow) {
 402       Node* mul_result = ConLNode::make(phase->C, result);
 403       return no_overflow(phase, mul_result);
 404     }
 405   }
 406 
 407   if (type1 == TypeLong::ZERO || type2 == TypeLong::ZERO) {
 408     return no_overflow(phase, ConLNode::make(phase->C, 0));
 409   }
 410 
 411   if (type1 == TypeLong::ONE) {
 412     Node* mul_result = new (phase->C) AddLNode(arg2, phase->longcon(0));
 413     return no_overflow(phase, mul_result);
 414   }
 415   if (type2 == TypeLong::ONE) {
 416     Node* mul_result = new (phase->C) AddLNode(arg1, phase->longcon(0));
 417     return no_overflow(phase, mul_result);
 418   }
 419 
 420   if (type1 == TypeLong::MINUS_1) {
 421     return new (phase->C) NegExactLNode(NULL, arg2);
 422   }
 423 
 424   if (type2 == TypeLong::MINUS_1) {
 425     return new (phase->C) NegExactLNode(NULL, arg1);
 426   }
 427 
 428   return NULL;
 429 }
 430