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