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 };
 181 
 182 //------------------------------CmpNNode--------------------------------------
 183 // Compare 2 narrow oop values, returning condition codes (-1, 0 or 1).
 184 class CmpNNode : public CmpNode {
 185 public:
 186   CmpNNode( Node *in1, Node *in2 ) : CmpNode(in1,in2) {}
 187   virtual int Opcode() const;
 188   virtual Node *Ideal(PhaseGVN *phase, bool can_reshape);
 189   virtual const Type *sub( const Type *, const Type * ) const;
 190 };
 191 
 192 //------------------------------CmpLNode---------------------------------------
 193 // Compare 2 long values, returning condition codes (-1, 0 or 1).
 194 class CmpLNode : public CmpNode {
 195 public:
 196   CmpLNode( Node *in1, Node *in2 ) : CmpNode(in1,in2) {}
 197   virtual int    Opcode() const;
 198   virtual const Type *sub( const Type *, const Type * ) const;
 199 };
 200 
 201 //------------------------------CmpULNode---------------------------------------
 202 // Compare 2 unsigned long values, returning condition codes (-1, 0 or 1).
 203 class CmpULNode : public CmpNode {
 204 public:
 205   CmpULNode(Node* in1, Node* in2) : CmpNode(in1, in2) { }
 206   virtual int Opcode() const;
 207   virtual const Type* sub(const Type*, const Type*) const;
 208 };
 209 
 210 //------------------------------CmpL3Node--------------------------------------
 211 // Compare 2 long values, returning integer value (-1, 0 or 1).
 212 class CmpL3Node : public CmpLNode {
 213 public:
 214   CmpL3Node( Node *in1, Node *in2 ) : CmpLNode(in1,in2) {
 215     // Since it is not consumed by Bools, it is not really a Cmp.
 216     init_class_id(Class_Sub);
 217   }
 218   virtual int    Opcode() const;
 219   virtual uint ideal_reg() const { return Op_RegI; }
 220 };
 221 
 222 //------------------------------CmpFNode---------------------------------------
 223 // Compare 2 float values, returning condition codes (-1, 0 or 1).
 224 // This implements the Java bytecode fcmpl, so unordered returns -1.
 225 // Operands may not commute.
 226 class CmpFNode : public CmpNode {
 227 public:
 228   CmpFNode( Node *in1, Node *in2 ) : CmpNode(in1,in2) {}
 229   virtual int Opcode() const;
 230   virtual const Type *sub( const Type *, const Type * ) const { ShouldNotReachHere(); return NULL; }
 231   const Type* Value(PhaseGVN* phase) const;
 232 };
 233 
 234 //------------------------------CmpF3Node--------------------------------------
 235 // Compare 2 float values, returning integer value (-1, 0 or 1).
 236 // This implements the Java bytecode fcmpl, so unordered returns -1.
 237 // Operands may not commute.
 238 class CmpF3Node : public CmpFNode {
 239 public:
 240   CmpF3Node( Node *in1, Node *in2 ) : CmpFNode(in1,in2) {
 241     // Since it is not consumed by Bools, it is not really a Cmp.
 242     init_class_id(Class_Sub);
 243   }
 244   virtual int Opcode() const;
 245   // Since it is not consumed by Bools, it is not really a Cmp.
 246   virtual uint ideal_reg() const { return Op_RegI; }
 247 };
 248 
 249 
 250 //------------------------------CmpDNode---------------------------------------
 251 // Compare 2 double values, returning condition codes (-1, 0 or 1).
 252 // This implements the Java bytecode dcmpl, so unordered returns -1.
 253 // Operands may not commute.
 254 class CmpDNode : public CmpNode {
 255 public:
 256   CmpDNode( Node *in1, Node *in2 ) : CmpNode(in1,in2) {}
 257   virtual int Opcode() const;
 258   virtual const Type *sub( const Type *, const Type * ) const { ShouldNotReachHere(); return NULL; }
 259   const Type* Value(PhaseGVN* phase) const;
 260   virtual Node  *Ideal(PhaseGVN *phase, bool can_reshape);
 261 };
 262 
 263 //------------------------------CmpD3Node--------------------------------------
 264 // Compare 2 double values, returning integer value (-1, 0 or 1).
 265 // This implements the Java bytecode dcmpl, so unordered returns -1.
 266 // Operands may not commute.
 267 class CmpD3Node : public CmpDNode {
 268 public:
 269   CmpD3Node( Node *in1, Node *in2 ) : CmpDNode(in1,in2) {
 270     // Since it is not consumed by Bools, it is not really a Cmp.
 271     init_class_id(Class_Sub);
 272   }
 273   virtual int Opcode() const;
 274   virtual uint ideal_reg() const { return Op_RegI; }
 275 };
 276 
 277 
 278 //------------------------------BoolTest---------------------------------------
 279 // Convert condition codes to a boolean test value (0 or -1).
 280 // We pick the values as 3 bits; the low order 2 bits we compare against the
 281 // condition codes, the high bit flips the sense of the result.
 282 struct BoolTest {
 283   enum mask { eq = 0, ne = 4, le = 5, ge = 7, lt = 3, gt = 1, overflow = 2, no_overflow = 6, illegal = 8 };
 284   mask _test;
 285   BoolTest( mask btm ) : _test(btm) {}
 286   const Type *cc2logical( const Type *CC ) const;
 287   // Commute the test.  I use a small table lookup.  The table is created as
 288   // a simple char array where each element is the ASCII version of a 'mask'
 289   // enum from above.
 290   mask commute( ) const { return mask("032147658"[_test]-'0'); }
 291   mask negate( ) const { return mask(_test^4); }
 292   bool is_canonical( ) const { return (_test == BoolTest::ne || _test == BoolTest::lt || _test == BoolTest::le || _test == BoolTest::overflow); }
 293   bool is_less( )  const { return _test == BoolTest::lt || _test == BoolTest::le; }
 294   bool is_greater( ) const { return _test == BoolTest::gt || _test == BoolTest::ge; }
 295   void dump_on(outputStream *st) const;
 296 };
 297 
 298 //------------------------------BoolNode---------------------------------------
 299 // A Node to convert a Condition Codes to a Logical result.
 300 class BoolNode : public Node {
 301   virtual uint hash() const;
 302   virtual uint cmp( const Node &n ) const;
 303   virtual uint size_of() const;
 304 
 305   // Try to optimize signed integer comparison
 306   Node* fold_cmpI(PhaseGVN* phase, SubNode* cmp, Node* cmp1, int cmp_op,
 307                   int cmp1_op, const TypeInt* cmp2_type);
 308 public:
 309   const BoolTest _test;
 310   BoolNode( Node *cc, BoolTest::mask t): _test(t), Node(0,cc) {
 311     init_class_id(Class_Bool);
 312   }
 313   // Convert an arbitrary int value to a Bool or other suitable predicate.
 314   static Node* make_predicate(Node* test_value, PhaseGVN* phase);
 315   // Convert self back to an integer value.
 316   Node* as_int_value(PhaseGVN* phase);
 317   // Invert sense of self, returning new Bool.
 318   BoolNode* negate(PhaseGVN* phase);
 319   virtual int Opcode() const;
 320   virtual Node *Ideal(PhaseGVN *phase, bool can_reshape);
 321   virtual const Type* Value(PhaseGVN* phase) const;
 322   virtual const Type *bottom_type() const { return TypeInt::BOOL; }
 323   uint match_edge(uint idx) const { return 0; }
 324   virtual uint ideal_reg() const { return Op_RegI; }
 325 
 326   bool is_counted_loop_exit_test();
 327 #ifndef PRODUCT
 328   virtual void dump_spec(outputStream *st) const;
 329   virtual void related(GrowableArray<Node*> *in_rel, GrowableArray<Node*> *out_rel, bool compact) const;
 330 #endif
 331 };
 332 
 333 //------------------------------AbsNode----------------------------------------
 334 // Abstract class for absolute value.  Mostly used to get a handy wrapper
 335 // for finding this pattern in the graph.
 336 class AbsNode : public Node {
 337 public:
 338   AbsNode( Node *value ) : Node(0,value) {}
 339 };
 340 
 341 //------------------------------AbsINode---------------------------------------
 342 // Absolute value an integer.  Since a naive graph involves control flow, we
 343 // "match" it in the ideal world (so the control flow can be removed).
 344 class AbsINode : public AbsNode {
 345 public:
 346   AbsINode( Node *in1 ) : AbsNode(in1) {}
 347   virtual int Opcode() const;
 348   const Type *bottom_type() const { return TypeInt::INT; }
 349   virtual uint ideal_reg() const { return Op_RegI; }
 350 };
 351 
 352 //------------------------------AbsFNode---------------------------------------
 353 // Absolute value a float, a common float-point idiom with a cheap hardware
 354 // implemention on most chips.  Since a naive graph involves control flow, we
 355 // "match" it in the ideal world (so the control flow can be removed).
 356 class AbsFNode : public AbsNode {
 357 public:
 358   AbsFNode( Node *in1 ) : AbsNode(in1) {}
 359   virtual int Opcode() const;
 360   const Type *bottom_type() const { return Type::FLOAT; }
 361   virtual uint ideal_reg() const { return Op_RegF; }
 362 };
 363 
 364 //------------------------------AbsDNode---------------------------------------
 365 // Absolute value a double, a common float-point idiom with a cheap hardware
 366 // implemention on most chips.  Since a naive graph involves control flow, we
 367 // "match" it in the ideal world (so the control flow can be removed).
 368 class AbsDNode : public AbsNode {
 369 public:
 370   AbsDNode( Node *in1 ) : AbsNode(in1) {}
 371   virtual int Opcode() const;
 372   const Type *bottom_type() const { return Type::DOUBLE; }
 373   virtual uint ideal_reg() const { return Op_RegD; }
 374 };
 375 
 376 
 377 //------------------------------CmpLTMaskNode----------------------------------
 378 // If p < q, return -1 else return 0.  Nice for flow-free idioms.
 379 class CmpLTMaskNode : public Node {
 380 public:
 381   CmpLTMaskNode( Node *p, Node *q ) : Node(0, p, q) {}
 382   virtual int Opcode() const;
 383   const Type *bottom_type() const { return TypeInt::INT; }
 384   virtual uint ideal_reg() const { return Op_RegI; }
 385 };
 386 
 387 
 388 //------------------------------NegNode----------------------------------------
 389 class NegNode : public Node {
 390 public:
 391   NegNode( Node *in1 ) : Node(0,in1) {}
 392 };
 393 
 394 //------------------------------NegFNode---------------------------------------
 395 // Negate value a float.  Negating 0.0 returns -0.0, but subtracting from
 396 // zero returns +0.0 (per JVM spec on 'fneg' bytecode).  As subtraction
 397 // cannot be used to replace negation we have to implement negation as ideal
 398 // node; note that negation and addition can replace subtraction.
 399 class NegFNode : public NegNode {
 400 public:
 401   NegFNode( Node *in1 ) : NegNode(in1) {}
 402   virtual int Opcode() const;
 403   const Type *bottom_type() const { return Type::FLOAT; }
 404   virtual uint ideal_reg() const { return Op_RegF; }
 405 };
 406 
 407 //------------------------------NegDNode---------------------------------------
 408 // Negate value a double.  Negating 0.0 returns -0.0, but subtracting from
 409 // zero returns +0.0 (per JVM spec on 'dneg' bytecode).  As subtraction
 410 // cannot be used to replace negation we have to implement negation as ideal
 411 // node; note that negation and addition can replace subtraction.
 412 class NegDNode : public NegNode {
 413 public:
 414   NegDNode( Node *in1 ) : NegNode(in1) {}
 415   virtual int Opcode() const;
 416   const Type *bottom_type() const { return Type::DOUBLE; }
 417   virtual uint ideal_reg() const { return Op_RegD; }
 418 };
 419 
 420 //------------------------------AtanDNode--------------------------------------
 421 // arcus tangens of a double
 422 class AtanDNode : public Node {
 423 public:
 424   AtanDNode(Node *c, Node *in1, Node *in2  ) : Node(c, in1, in2) {}
 425   virtual int Opcode() const;
 426   const Type *bottom_type() const { return Type::DOUBLE; }
 427   virtual uint ideal_reg() const { return Op_RegD; }
 428 };
 429 
 430 
 431 //------------------------------SqrtDNode--------------------------------------
 432 // square root a double
 433 class SqrtDNode : public Node {
 434 public:
 435   SqrtDNode(Compile* C, Node *c, Node *in1) : Node(c, in1) {
 436     init_flags(Flag_is_expensive);
 437     C->add_expensive_node(this);
 438   }
 439   virtual int Opcode() const;
 440   const Type *bottom_type() const { return Type::DOUBLE; }
 441   virtual uint ideal_reg() const { return Op_RegD; }
 442   virtual const Type* Value(PhaseGVN* phase) const;
 443 };
 444 
 445 //------------------------------SqrtFNode--------------------------------------
 446 // square root a float
 447 class SqrtFNode : public Node {
 448 public:
 449   SqrtFNode(Compile* C, Node *c, Node *in1) : Node(c, in1) {
 450     init_flags(Flag_is_expensive);
 451     C->add_expensive_node(this);
 452   }
 453   virtual int Opcode() const;
 454   const Type *bottom_type() const { return Type::FLOAT; }
 455   virtual uint ideal_reg() const { return Op_RegF; }
 456   virtual const Type* Value(PhaseGVN* phase) const;
 457 };
 458 
 459 //-------------------------------ReverseBytesINode--------------------------------
 460 // reverse bytes of an integer
 461 class ReverseBytesINode : public Node {
 462 public:
 463   ReverseBytesINode(Node *c, Node *in1) : Node(c, in1) {}
 464   virtual int Opcode() const;
 465   const Type *bottom_type() const { return TypeInt::INT; }
 466   virtual uint ideal_reg() const { return Op_RegI; }
 467 };
 468 
 469 //-------------------------------ReverseBytesLNode--------------------------------
 470 // reverse bytes of a long
 471 class ReverseBytesLNode : public Node {
 472 public:
 473   ReverseBytesLNode(Node *c, Node *in1) : Node(c, in1) {}
 474   virtual int Opcode() const;
 475   const Type *bottom_type() const { return TypeLong::LONG; }
 476   virtual uint ideal_reg() const { return Op_RegL; }
 477 };
 478 
 479 //-------------------------------ReverseBytesUSNode--------------------------------
 480 // reverse bytes of an unsigned short / char
 481 class ReverseBytesUSNode : public Node {
 482 public:
 483   ReverseBytesUSNode(Node *c, Node *in1) : Node(c, in1) {}
 484   virtual int Opcode() const;
 485   const Type *bottom_type() const { return TypeInt::CHAR; }
 486   virtual uint ideal_reg() const { return Op_RegI; }
 487 };
 488 
 489 //-------------------------------ReverseBytesSNode--------------------------------
 490 // reverse bytes of a short
 491 class ReverseBytesSNode : public Node {
 492 public:
 493   ReverseBytesSNode(Node *c, Node *in1) : Node(c, in1) {}
 494   virtual int Opcode() const;
 495   const Type *bottom_type() const { return TypeInt::SHORT; }
 496   virtual uint ideal_reg() const { return Op_RegI; }
 497 };
 498 
 499 #endif // SHARE_VM_OPTO_SUBNODE_HPP