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