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