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