1 /*
   2  * Copyright (c) 1997, 2015, 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 #ifndef SHARE_VM_OPTO_SUBNODE_HPP
  26 #define SHARE_VM_OPTO_SUBNODE_HPP
  27 
  28 #include "opto/node.hpp"
  29 #include "opto/opcodes.hpp"
  30 #include "opto/type.hpp"
  31 
  32 // Portions of code courtesy of Clifford Click
  33 
  34 //------------------------------SUBNode----------------------------------------
  35 // Class SUBTRACTION functionality.  This covers all the usual 'subtract'
  36 // behaviors.  Subtract-integer, -float, -double, binary xor, compare-integer,
  37 // -float, and -double are all inherited from this class.  The compare
  38 // functions behave like subtract functions, except that all negative answers
  39 // are compressed into -1, and all positive answers compressed to 1.
  40 class SubNode : public Node {
  41 public:
  42   SubNode( Node *in1, Node *in2 ) : Node(0,in1,in2) {
  43     init_class_id(Class_Sub);
  44   }
  45 
  46   // Handle algebraic identities here.  If we have an identity, return the Node
  47   // we are equivalent to.  We look for "add of zero" as an identity.
  48   virtual Node* Identity(PhaseGVN* phase);
  49 
  50   // Compute a new Type for this node.  Basically we just do the pre-check,
  51   // then call the virtual add() to set the type.
  52   virtual const Type* Value(PhaseGVN* phase) const;
  53   const Type* Value_common( PhaseTransform *phase ) const;
  54 
  55   // Supplied function returns the subtractend of the inputs.
  56   // This also type-checks the inputs for sanity.  Guaranteed never to
  57   // be passed a TOP or BOTTOM type, these are filtered out by a pre-check.
  58   virtual const Type *sub( const Type *, const Type * ) const = 0;
  59 
  60   // Supplied function to return the additive identity type.
  61   // This is returned whenever the subtracts inputs are the same.
  62   virtual const Type *add_id() const = 0;
  63 };
  64 
  65 
  66 // NOTE: SubINode should be taken away and replaced by add and negate
  67 //------------------------------SubINode---------------------------------------
  68 // Subtract 2 integers
  69 class SubINode : public SubNode {
  70 public:
  71   SubINode( Node *in1, Node *in2 ) : SubNode(in1,in2) {}
  72   virtual int Opcode() const;
  73   virtual Node *Ideal(PhaseGVN *phase, bool can_reshape);
  74   virtual const Type *sub( const Type *, const Type * ) const;
  75   const Type *add_id() const { return TypeInt::ZERO; }
  76   const Type *bottom_type() const { return TypeInt::INT; }
  77   virtual uint ideal_reg() const { return Op_RegI; }
  78 };
  79 
  80 //------------------------------SubLNode---------------------------------------
  81 // Subtract 2 integers
  82 class SubLNode : public SubNode {
  83 public:
  84   SubLNode( Node *in1, Node *in2 ) : SubNode(in1,in2) {}
  85   virtual int Opcode() const;
  86   virtual Node *Ideal(PhaseGVN *phase, bool can_reshape);
  87   virtual const Type *sub( const Type *, const Type * ) const;
  88   const Type *add_id() const { return TypeLong::ZERO; }
  89   const Type *bottom_type() const { return TypeLong::LONG; }
  90   virtual uint ideal_reg() const { return Op_RegL; }
  91 };
  92 
  93 // NOTE: SubFPNode should be taken away and replaced by add and negate
  94 //------------------------------SubFPNode--------------------------------------
  95 // Subtract 2 floats or doubles
  96 class SubFPNode : public SubNode {
  97 protected:
  98   SubFPNode( Node *in1, Node *in2 ) : SubNode(in1,in2) {}
  99 public:
 100   const Type* Value(PhaseGVN* phase) const;
 101 };
 102 
 103 // NOTE: SubFNode should be taken away and replaced by add and negate
 104 //------------------------------SubFNode---------------------------------------
 105 // Subtract 2 doubles
 106 class SubFNode : public SubFPNode {
 107 public:
 108   SubFNode( Node *in1, Node *in2 ) : SubFPNode(in1,in2) {}
 109   virtual int Opcode() const;
 110   virtual Node *Ideal(PhaseGVN *phase, bool can_reshape);
 111   virtual const Type *sub( const Type *, const Type * ) const;
 112   const Type   *add_id() const { return TypeF::ZERO; }
 113   const Type   *bottom_type() const { return Type::FLOAT; }
 114   virtual uint  ideal_reg() const { return Op_RegF; }
 115 };
 116 
 117 // NOTE: SubDNode should be taken away and replaced by add and negate
 118 //------------------------------SubDNode---------------------------------------
 119 // Subtract 2 doubles
 120 class SubDNode : public SubFPNode {
 121 public:
 122   SubDNode( Node *in1, Node *in2 ) : SubFPNode(in1,in2) {}
 123   virtual int Opcode() const;
 124   virtual Node *Ideal(PhaseGVN *phase, bool can_reshape);
 125   virtual const Type *sub( const Type *, const Type * ) const;
 126   const Type   *add_id() const { return TypeD::ZERO; }
 127   const Type   *bottom_type() const { return Type::DOUBLE; }
 128   virtual uint  ideal_reg() const { return Op_RegD; }
 129 };
 130 
 131 //------------------------------CmpNode---------------------------------------
 132 // Compare 2 values, returning condition codes (-1, 0 or 1).
 133 class CmpNode : public SubNode {
 134 public:
 135   CmpNode( Node *in1, Node *in2 ) : SubNode(in1,in2) {
 136     init_class_id(Class_Cmp);
 137   }
 138   virtual Node* Identity(PhaseGVN* phase);
 139   const Type *add_id() const { return TypeInt::ZERO; }
 140   const Type *bottom_type() const { return TypeInt::CC; }
 141   virtual uint ideal_reg() const { return Op_RegFlags; }
 142 
 143 #ifndef PRODUCT
 144   // CmpNode and subclasses include all data inputs (until hitting a control
 145   // boundary) in their related node set, as well as all outputs until and
 146   // including eventual control nodes and their projections.
 147   virtual void related(GrowableArray<Node*> *in_rel, GrowableArray<Node*> *out_rel, bool compact) const;
 148 #endif
 149 };
 150 
 151 //------------------------------CmpINode---------------------------------------
 152 // Compare 2 signed values, returning condition codes (-1, 0 or 1).
 153 class CmpINode : public CmpNode {
 154 public:
 155   CmpINode( Node *in1, Node *in2 ) : CmpNode(in1,in2) {}
 156   virtual int Opcode() const;
 157   virtual Node *Ideal(PhaseGVN *phase, bool can_reshape);
 158   virtual const Type *sub( const Type *, const Type * ) const;
 159 };
 160 
 161 //------------------------------CmpUNode---------------------------------------
 162 // Compare 2 unsigned values (integer or pointer), returning condition codes (-1, 0 or 1).
 163 class CmpUNode : public CmpNode {
 164 public:
 165   CmpUNode( Node *in1, Node *in2 ) : CmpNode(in1,in2) {}
 166   virtual int Opcode() const;
 167   virtual const Type *sub( const Type *, const Type * ) const;
 168   const Type* Value(PhaseGVN* phase) const;
 169   bool is_index_range_check() const;
 170 };
 171 
 172 //------------------------------CmpPNode---------------------------------------
 173 // Compare 2 pointer values, returning condition codes (-1, 0 or 1).
 174 class CmpPNode : public CmpNode {
 175 public:
 176   CmpPNode( Node *in1, Node *in2 ) : CmpNode(in1,in2) {}
 177   virtual int Opcode() const;
 178   virtual Node *Ideal(PhaseGVN *phase, bool can_reshape);
 179   virtual const Type *sub( const Type *, const Type * ) const;
 180   Node* has_perturbed_operand() const;
 181 };
 182 
 183 //------------------------------CmpNNode--------------------------------------
 184 // Compare 2 narrow oop values, returning condition codes (-1, 0 or 1).
 185 class CmpNNode : public CmpNode {
 186 public:
 187   CmpNNode( Node *in1, Node *in2 ) : CmpNode(in1,in2) {}
 188   virtual int Opcode() const;
 189   virtual Node *Ideal(PhaseGVN *phase, bool can_reshape);
 190   virtual const Type *sub( const Type *, const Type * ) const;
 191 };
 192 
 193 //------------------------------CmpLNode---------------------------------------
 194 // Compare 2 long values, returning condition codes (-1, 0 or 1).
 195 class CmpLNode : public CmpNode {
 196 public:
 197   CmpLNode( Node *in1, Node *in2 ) : CmpNode(in1,in2) {}
 198   virtual int    Opcode() const;
 199   virtual Node* Ideal(PhaseGVN* phase, bool can_reshape);
 200   virtual const Type *sub( const Type *, const Type * ) const;
 201 };
 202 
 203 //------------------------------CmpULNode---------------------------------------
 204 // Compare 2 unsigned long values, returning condition codes (-1, 0 or 1).
 205 class CmpULNode : public CmpNode {
 206 public:
 207   CmpULNode(Node* in1, Node* in2) : CmpNode(in1, in2) { }
 208   virtual int Opcode() const;
 209   virtual const Type* sub(const Type*, const Type*) const;
 210 };
 211 
 212 //------------------------------CmpL3Node--------------------------------------
 213 // Compare 2 long values, returning integer value (-1, 0 or 1).
 214 class CmpL3Node : public CmpLNode {
 215 public:
 216   CmpL3Node( Node *in1, Node *in2 ) : CmpLNode(in1,in2) {
 217     // Since it is not consumed by Bools, it is not really a Cmp.
 218     init_class_id(Class_Sub);
 219   }
 220   virtual int    Opcode() const;
 221   virtual uint ideal_reg() const { return Op_RegI; }
 222 };
 223 
 224 //------------------------------CmpFNode---------------------------------------
 225 // Compare 2 float values, returning condition codes (-1, 0 or 1).
 226 // This implements the Java bytecode fcmpl, so unordered returns -1.
 227 // Operands may not commute.
 228 class CmpFNode : public CmpNode {
 229 public:
 230   CmpFNode( Node *in1, Node *in2 ) : CmpNode(in1,in2) {}
 231   virtual int Opcode() const;
 232   virtual const Type *sub( const Type *, const Type * ) const { ShouldNotReachHere(); return NULL; }
 233   const Type* Value(PhaseGVN* phase) const;
 234 };
 235 
 236 //------------------------------CmpF3Node--------------------------------------
 237 // Compare 2 float values, returning integer value (-1, 0 or 1).
 238 // This implements the Java bytecode fcmpl, so unordered returns -1.
 239 // Operands may not commute.
 240 class CmpF3Node : public CmpFNode {
 241 public:
 242   CmpF3Node( Node *in1, Node *in2 ) : CmpFNode(in1,in2) {
 243     // Since it is not consumed by Bools, it is not really a Cmp.
 244     init_class_id(Class_Sub);
 245   }
 246   virtual int Opcode() const;
 247   // Since it is not consumed by Bools, it is not really a Cmp.
 248   virtual uint ideal_reg() const { return Op_RegI; }
 249 };
 250 
 251 
 252 //------------------------------CmpDNode---------------------------------------
 253 // Compare 2 double values, returning condition codes (-1, 0 or 1).
 254 // This implements the Java bytecode dcmpl, so unordered returns -1.
 255 // Operands may not commute.
 256 class CmpDNode : public CmpNode {
 257 public:
 258   CmpDNode( Node *in1, Node *in2 ) : CmpNode(in1,in2) {}
 259   virtual int Opcode() const;
 260   virtual const Type *sub( const Type *, const Type * ) const { ShouldNotReachHere(); return NULL; }
 261   const Type* Value(PhaseGVN* phase) const;
 262   virtual Node  *Ideal(PhaseGVN *phase, bool can_reshape);
 263 };
 264 
 265 //------------------------------CmpD3Node--------------------------------------
 266 // Compare 2 double values, returning integer value (-1, 0 or 1).
 267 // This implements the Java bytecode dcmpl, so unordered returns -1.
 268 // Operands may not commute.
 269 class CmpD3Node : public CmpDNode {
 270 public:
 271   CmpD3Node( Node *in1, Node *in2 ) : CmpDNode(in1,in2) {
 272     // Since it is not consumed by Bools, it is not really a Cmp.
 273     init_class_id(Class_Sub);
 274   }
 275   virtual int Opcode() const;
 276   virtual uint ideal_reg() const { return Op_RegI; }
 277 };
 278 
 279 
 280 //------------------------------BoolTest---------------------------------------
 281 // Convert condition codes to a boolean test value (0 or -1).
 282 // We pick the values as 3 bits; the low order 2 bits we compare against the
 283 // condition codes, the high bit flips the sense of the result.
 284 struct BoolTest VALUE_OBJ_CLASS_SPEC {
 285   enum mask { eq = 0, ne = 4, le = 5, ge = 7, lt = 3, gt = 1, overflow = 2, no_overflow = 6, illegal = 8 };
 286   mask _test;
 287   BoolTest( mask btm ) : _test(btm) {}
 288   const Type *cc2logical( const Type *CC ) const;
 289   // Commute the test.  I use a small table lookup.  The table is created as
 290   // a simple char array where each element is the ASCII version of a 'mask'
 291   // enum from above.
 292   mask commute( ) const { return mask("032147658"[_test]-'0'); }
 293   mask negate( ) const { return mask(_test^4); }
 294   bool is_canonical( ) const { return (_test == BoolTest::ne || _test == BoolTest::lt || _test == BoolTest::le || _test == BoolTest::overflow); }
 295   bool is_less( )  const { return _test == BoolTest::lt || _test == BoolTest::le; }
 296   bool is_greater( ) const { return _test == BoolTest::gt || _test == BoolTest::ge; }
 297   void dump_on(outputStream *st) const;
 298 };
 299 
 300 //------------------------------BoolNode---------------------------------------
 301 // A Node to convert a Condition Codes to a Logical result.
 302 class BoolNode : public Node {
 303   virtual uint hash() const;
 304   virtual uint cmp( const Node &n ) const;
 305   virtual uint size_of() const;
 306 
 307   // Try to optimize signed integer comparison
 308   Node* fold_cmpI(PhaseGVN* phase, SubNode* cmp, Node* cmp1, int cmp_op,
 309                   int cmp1_op, const TypeInt* cmp2_type);
 310 public:
 311   const BoolTest _test;
 312   BoolNode( Node *cc, BoolTest::mask t): _test(t), Node(0,cc) {
 313     init_class_id(Class_Bool);
 314   }
 315   // Convert an arbitrary int value to a Bool or other suitable predicate.
 316   static Node* make_predicate(Node* test_value, PhaseGVN* phase);
 317   // Convert self back to an integer value.
 318   Node* as_int_value(PhaseGVN* phase);
 319   // Invert sense of self, returning new Bool.
 320   BoolNode* negate(PhaseGVN* phase);
 321   virtual int Opcode() const;
 322   virtual Node *Ideal(PhaseGVN *phase, bool can_reshape);
 323   virtual const Type* Value(PhaseGVN* phase) const;
 324   virtual const Type *bottom_type() const { return TypeInt::BOOL; }
 325   uint match_edge(uint idx) const { return 0; }
 326   virtual uint ideal_reg() const { return Op_RegI; }
 327 
 328   bool is_counted_loop_exit_test();
 329 #ifndef PRODUCT
 330   virtual void dump_spec(outputStream *st) const;
 331   virtual void related(GrowableArray<Node*> *in_rel, GrowableArray<Node*> *out_rel, bool compact) const;
 332 #endif
 333 };
 334 
 335 //------------------------------AbsNode----------------------------------------
 336 // Abstract class for absolute value.  Mostly used to get a handy wrapper
 337 // for finding this pattern in the graph.
 338 class AbsNode : public Node {
 339 public:
 340   AbsNode( Node *value ) : Node(0,value) {}
 341 };
 342 
 343 //------------------------------AbsINode---------------------------------------
 344 // Absolute value an integer.  Since a naive graph involves control flow, we
 345 // "match" it in the ideal world (so the control flow can be removed).
 346 class AbsINode : public AbsNode {
 347 public:
 348   AbsINode( Node *in1 ) : AbsNode(in1) {}
 349   virtual int Opcode() const;
 350   const Type *bottom_type() const { return TypeInt::INT; }
 351   virtual uint ideal_reg() const { return Op_RegI; }
 352 };
 353 
 354 //------------------------------AbsFNode---------------------------------------
 355 // Absolute value a float, a common float-point idiom with a cheap hardware
 356 // implemention on most chips.  Since a naive graph involves control flow, we
 357 // "match" it in the ideal world (so the control flow can be removed).
 358 class AbsFNode : public AbsNode {
 359 public:
 360   AbsFNode( Node *in1 ) : AbsNode(in1) {}
 361   virtual int Opcode() const;
 362   const Type *bottom_type() const { return Type::FLOAT; }
 363   virtual uint ideal_reg() const { return Op_RegF; }
 364 };
 365 
 366 //------------------------------AbsDNode---------------------------------------
 367 // Absolute value a double, a common float-point idiom with a cheap hardware
 368 // implemention on most chips.  Since a naive graph involves control flow, we
 369 // "match" it in the ideal world (so the control flow can be removed).
 370 class AbsDNode : public AbsNode {
 371 public:
 372   AbsDNode( Node *in1 ) : AbsNode(in1) {}
 373   virtual int Opcode() const;
 374   const Type *bottom_type() const { return Type::DOUBLE; }
 375   virtual uint ideal_reg() const { return Op_RegD; }
 376 };
 377 
 378 
 379 //------------------------------CmpLTMaskNode----------------------------------
 380 // If p < q, return -1 else return 0.  Nice for flow-free idioms.
 381 class CmpLTMaskNode : public Node {
 382 public:
 383   CmpLTMaskNode( Node *p, Node *q ) : Node(0, p, q) {}
 384   virtual int Opcode() const;
 385   const Type *bottom_type() const { return TypeInt::INT; }
 386   virtual uint ideal_reg() const { return Op_RegI; }
 387 };
 388 
 389 
 390 //------------------------------NegNode----------------------------------------
 391 class NegNode : public Node {
 392 public:
 393   NegNode( Node *in1 ) : Node(0,in1) {}
 394 };
 395 
 396 //------------------------------NegFNode---------------------------------------
 397 // Negate value a float.  Negating 0.0 returns -0.0, but subtracting from
 398 // zero returns +0.0 (per JVM spec on 'fneg' bytecode).  As subtraction
 399 // cannot be used to replace negation we have to implement negation as ideal
 400 // node; note that negation and addition can replace subtraction.
 401 class NegFNode : public NegNode {
 402 public:
 403   NegFNode( Node *in1 ) : NegNode(in1) {}
 404   virtual int Opcode() const;
 405   const Type *bottom_type() const { return Type::FLOAT; }
 406   virtual uint ideal_reg() const { return Op_RegF; }
 407 };
 408 
 409 //------------------------------NegDNode---------------------------------------
 410 // Negate value a double.  Negating 0.0 returns -0.0, but subtracting from
 411 // zero returns +0.0 (per JVM spec on 'dneg' bytecode).  As subtraction
 412 // cannot be used to replace negation we have to implement negation as ideal
 413 // node; note that negation and addition can replace subtraction.
 414 class NegDNode : public NegNode {
 415 public:
 416   NegDNode( Node *in1 ) : NegNode(in1) {}
 417   virtual int Opcode() const;
 418   const Type *bottom_type() const { return Type::DOUBLE; }
 419   virtual uint ideal_reg() const { return Op_RegD; }
 420 };
 421 
 422 //------------------------------AtanDNode--------------------------------------
 423 // arcus tangens of a double
 424 class AtanDNode : public Node {
 425 public:
 426   AtanDNode(Node *c, Node *in1, Node *in2  ) : Node(c, in1, in2) {}
 427   virtual int Opcode() const;
 428   const Type *bottom_type() const { return Type::DOUBLE; }
 429   virtual uint ideal_reg() const { return Op_RegD; }
 430 };
 431 
 432 
 433 //------------------------------SqrtDNode--------------------------------------
 434 // square root a double
 435 class SqrtDNode : public Node {
 436 public:
 437   SqrtDNode(Compile* C, Node *c, Node *in1) : Node(c, in1) {
 438     init_flags(Flag_is_expensive);
 439     C->add_expensive_node(this);
 440   }
 441   virtual int Opcode() const;
 442   const Type *bottom_type() const { return Type::DOUBLE; }
 443   virtual uint ideal_reg() const { return Op_RegD; }
 444   virtual const Type* Value(PhaseGVN* phase) const;
 445 };
 446 
 447 //------------------------------SqrtFNode--------------------------------------
 448 // square root a float
 449 class SqrtFNode : public Node {
 450 public:
 451   SqrtFNode(Compile* C, Node *c, Node *in1) : Node(c, in1) {
 452     init_flags(Flag_is_expensive);
 453     C->add_expensive_node(this);
 454   }
 455   virtual int Opcode() const;
 456   const Type *bottom_type() const { return Type::FLOAT; }
 457   virtual uint ideal_reg() const { return Op_RegF; }
 458   virtual const Type* Value(PhaseGVN* phase) const;
 459 };
 460 
 461 //-------------------------------ReverseBytesINode--------------------------------
 462 // reverse bytes of an integer
 463 class ReverseBytesINode : public Node {
 464 public:
 465   ReverseBytesINode(Node *c, Node *in1) : Node(c, in1) {}
 466   virtual int Opcode() const;
 467   const Type *bottom_type() const { return TypeInt::INT; }
 468   virtual uint ideal_reg() const { return Op_RegI; }
 469 };
 470 
 471 //-------------------------------ReverseBytesLNode--------------------------------
 472 // reverse bytes of a long
 473 class ReverseBytesLNode : public Node {
 474 public:
 475   ReverseBytesLNode(Node *c, Node *in1) : Node(c, in1) {}
 476   virtual int Opcode() const;
 477   const Type *bottom_type() const { return TypeLong::LONG; }
 478   virtual uint ideal_reg() const { return Op_RegL; }
 479 };
 480 
 481 //-------------------------------ReverseBytesUSNode--------------------------------
 482 // reverse bytes of an unsigned short / char
 483 class ReverseBytesUSNode : public Node {
 484 public:
 485   ReverseBytesUSNode(Node *c, Node *in1) : Node(c, in1) {}
 486   virtual int Opcode() const;
 487   const Type *bottom_type() const { return TypeInt::CHAR; }
 488   virtual uint ideal_reg() const { return Op_RegI; }
 489 };
 490 
 491 //-------------------------------ReverseBytesSNode--------------------------------
 492 // reverse bytes of a short
 493 class ReverseBytesSNode : public Node {
 494 public:
 495   ReverseBytesSNode(Node *c, Node *in1) : Node(c, in1) {}
 496   virtual int Opcode() const;
 497   const Type *bottom_type() const { return TypeInt::SHORT; }
 498   virtual uint ideal_reg() const { return Op_RegI; }
 499 };
 500 
 501 #endif // SHARE_VM_OPTO_SUBNODE_HPP