1
2 /*
3 * Copyright (c) 1997, 2015, Oracle and/or its affiliates. All rights reserved.
4 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
5 *
6 * This code is free software; you can redistribute it and/or modify it
7 * under the terms of the GNU General Public License version 2 only, as
8 * published by the Free Software Foundation.
9 *
10 * This code is distributed in the hope that it will be useful, but WITHOUT
11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13 * version 2 for more details (a copy is included in the LICENSE file that
14 * accompanied this code).
15 *
16 * You should have received a copy of the GNU General Public License version
17 * 2 along with this work; if not, write to the Free Software Foundation,
18 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
19 *
20 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
21 * or visit www.oracle.com if you need additional information or have any
22 * questions.
23 *
24 */
25
26 #ifndef SHARE_VM_OPTO_SUBNODE_HPP
27 #define SHARE_VM_OPTO_SUBNODE_HPP
28
29 #include "opto/node.hpp"
30 #include "opto/opcodes.hpp"
31 #include "opto/type.hpp"
32
33 // Portions of code courtesy of Clifford Click
34
35 //------------------------------SUBNode----------------------------------------
36 // Class SUBTRACTION functionality. This covers all the usual 'subtract'
37 // behaviors. Subtract-integer, -float, -double, binary xor, compare-integer,
38 // -float, and -double are all inherited from this class. The compare
39 // functions behave like subtract functions, except that all negative answers
40 // are compressed into -1, and all positive answers compressed to 1.
41 class SubNode : public Node {
42 public:
43 SubNode( Node *in1, Node *in2 ) : Node(0,in1,in2) {
44 init_class_id(Class_Sub);
45 }
46
47 // Handle algebraic identities here. If we have an identity, return the Node
48 // we are equivalent to. We look for "add of zero" as an identity.
49 virtual Node* Identity(PhaseGVN* phase);
50
51 // Compute a new Type for this node. Basically we just do the pre-check,
52 // then call the virtual add() to set the type.
53 virtual const Type* Value(PhaseGVN* phase) const;
54 const Type* Value_common( PhaseTransform *phase ) const;
55
56 // Supplied function returns the subtractend of the inputs.
57 // This also type-checks the inputs for sanity. Guaranteed never to
58 // be passed a TOP or BOTTOM type, these are filtered out by a pre-check.
59 virtual const Type *sub( const Type *, const Type * ) const = 0;
60
61 // Supplied function to return the additive identity type.
62 // This is returned whenever the subtracts inputs are the same.
63 virtual const Type *add_id() const = 0;
64 };
65
66
67 // NOTE: SubINode should be taken away and replaced by add and negate
68 //------------------------------SubINode---------------------------------------
69 // Subtract 2 integers
70 class SubINode : public SubNode {
71 public:
72 SubINode( Node *in1, Node *in2 ) : SubNode(in1,in2) {}
73 virtual int Opcode() const;
74 virtual Node *Ideal(PhaseGVN *phase, bool can_reshape);
75 virtual const Type *sub( const Type *, const Type * ) const;
76 const Type *add_id() const { return TypeInt::ZERO; }
77 const Type *bottom_type() const { return TypeInt::INT; }
78 virtual uint ideal_reg() const { return Op_RegI; }
79 };
80
81 //------------------------------SubLNode---------------------------------------
82 // Subtract 2 integers
83 class SubLNode : public SubNode {
84 public:
85 SubLNode( Node *in1, Node *in2 ) : SubNode(in1,in2) {}
86 virtual int Opcode() const;
87 virtual Node *Ideal(PhaseGVN *phase, bool can_reshape);
88 virtual const Type *sub( const Type *, const Type * ) const;
89 const Type *add_id() const { return TypeLong::ZERO; }
90 const Type *bottom_type() const { return TypeLong::LONG; }
91 virtual uint ideal_reg() const { return Op_RegL; }
92 };
93
94 // NOTE: SubFPNode should be taken away and replaced by add and negate
95 //------------------------------SubFPNode--------------------------------------
96 // Subtract 2 floats or doubles
97 class SubFPNode : public SubNode {
98 protected:
99 SubFPNode( Node *in1, Node *in2 ) : SubNode(in1,in2) {}
100 public:
101 const Type* Value(PhaseGVN* phase) const;
102 };
103
104 // NOTE: SubFNode should be taken away and replaced by add and negate
105 //------------------------------SubFNode---------------------------------------
106 // Subtract 2 doubles
107 class SubFNode : public SubFPNode {
108 public:
109 SubFNode( Node *in1, Node *in2 ) : SubFPNode(in1,in2) {}
110 virtual int Opcode() const;
111 virtual Node *Ideal(PhaseGVN *phase, bool can_reshape);
112 virtual const Type *sub( const Type *, const Type * ) const;
113 const Type *add_id() const { return TypeF::ZERO; }
114 const Type *bottom_type() const { return Type::FLOAT; }
115 virtual uint ideal_reg() const { return Op_RegF; }
116 };
117
118 // NOTE: SubDNode should be taken away and replaced by add and negate
119 //------------------------------SubDNode---------------------------------------
120 // Subtract 2 doubles
121 class SubDNode : public SubFPNode {
122 public:
123 SubDNode( Node *in1, Node *in2 ) : SubFPNode(in1,in2) {}
124 virtual int Opcode() const;
125 virtual Node *Ideal(PhaseGVN *phase, bool can_reshape);
126 virtual const Type *sub( const Type *, const Type * ) const;
127 const Type *add_id() const { return TypeD::ZERO; }
128 const Type *bottom_type() const { return Type::DOUBLE; }
129 virtual uint ideal_reg() const { return Op_RegD; }
130 };
131
132 //------------------------------CmpNode---------------------------------------
133 // Compare 2 values, returning condition codes (-1, 0 or 1).
134 class CmpNode : public SubNode {
135 public:
136 CmpNode( Node *in1, Node *in2 ) : SubNode(in1,in2) {
137 init_class_id(Class_Cmp);
138 }
139 virtual Node* Identity(PhaseGVN* phase);
140 const Type *add_id() const { return TypeInt::ZERO; }
141 const Type *bottom_type() const { return TypeInt::CC; }
142 virtual uint ideal_reg() const { return Op_RegFlags; }
143
144 #ifndef PRODUCT
145 // CmpNode and subclasses include all data inputs (until hitting a control
146 // boundary) in their related node set, as well as all outputs until and
147 // including eventual control nodes and their projections.
148 virtual void related(GrowableArray<Node*> *in_rel, GrowableArray<Node*> *out_rel, bool compact) const;
149 #endif
150 };
151
152 //------------------------------CmpINode---------------------------------------
153 // Compare 2 signed values, returning condition codes (-1, 0 or 1).
154 class CmpINode : public CmpNode {
155 public:
156 CmpINode( Node *in1, Node *in2 ) : CmpNode(in1,in2) {}
157 virtual int Opcode() const;
158 virtual Node *Ideal(PhaseGVN *phase, bool can_reshape);
159 virtual const Type *sub( const Type *, const Type * ) const;
160 };
161
162 //------------------------------CmpUNode---------------------------------------
163 // Compare 2 unsigned values (integer or pointer), returning condition codes (-1, 0 or 1).
164 class CmpUNode : public CmpNode {
165 public:
166 CmpUNode( Node *in1, Node *in2 ) : CmpNode(in1,in2) {}
167 virtual int Opcode() const;
168 virtual const Type *sub( const Type *, const Type * ) const;
169 const Type* Value(PhaseGVN* phase) const;
170 bool is_index_range_check() const;
171 };
172
173 //------------------------------CmpPNode---------------------------------------
174 // Compare 2 pointer values, returning condition codes (-1, 0 or 1).
175 class CmpPNode : public CmpNode {
176 public:
177 CmpPNode( Node *in1, Node *in2 ) : CmpNode(in1,in2) {}
178 virtual int Opcode() const;
179 virtual Node *Ideal(PhaseGVN *phase, bool can_reshape);
180 virtual const Type *sub( const Type *, const Type * ) const;
181 };
182
183 //------------------------------CmpNNode--------------------------------------
184 // Compare 2 narrow oop values, returning condition codes (-1, 0 or 1).
185 class CmpNNode : public CmpNode {
186 public:
187 CmpNNode( Node *in1, Node *in2 ) : CmpNode(in1,in2) {}
188 virtual int Opcode() const;
189 virtual Node *Ideal(PhaseGVN *phase, bool can_reshape);
190 virtual const Type *sub( const Type *, const Type * ) const;
191 };
192
193 //------------------------------CmpLNode---------------------------------------
194 // Compare 2 long values, returning condition codes (-1, 0 or 1).
195 class CmpLNode : public CmpNode {
196 public:
197 CmpLNode( Node *in1, Node *in2 ) : CmpNode(in1,in2) {}
198 virtual int Opcode() const;
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 VALUE_OBJ_CLASS_SPEC {
284 enum mask { eq = 0, ne = 4, le = 5, ge = 7, lt = 3, gt = 1, overflow = 2, no_overflow = 6, illegal = 8 };
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 };
298
299 //------------------------------BoolNode---------------------------------------
300 // A Node to convert a Condition Codes to a Logical result.
301 class BoolNode : public Node {
302 virtual uint hash() const;
303 virtual uint cmp( const Node &n ) const;
304 virtual uint size_of() const;
305
306 // Try to optimize signed integer comparison
307 Node* fold_cmpI(PhaseGVN* phase, SubNode* cmp, Node* cmp1, int cmp_op,
308 int cmp1_op, const TypeInt* cmp2_type);
309 public:
310 const BoolTest _test;
311 BoolNode( Node *cc, BoolTest::mask t): _test(t), Node(0,cc) {
312 init_class_id(Class_Bool);
313 }
314 // Convert an arbitrary int value to a Bool or other suitable predicate.
315 static Node* make_predicate(Node* test_value, PhaseGVN* phase);
316 // Convert self back to an integer value.
317 Node* as_int_value(PhaseGVN* phase);
318 // Invert sense of self, returning new Bool.
319 BoolNode* negate(PhaseGVN* phase);
320 virtual int Opcode() const;
321 virtual Node *Ideal(PhaseGVN *phase, bool can_reshape);
322 virtual const Type* Value(PhaseGVN* phase) const;
323 virtual const Type *bottom_type() const { return TypeInt::BOOL; }
324 uint match_edge(uint idx) const { return 0; }
325 virtual uint ideal_reg() const { return Op_RegI; }
326
327 bool is_counted_loop_exit_test();
328 #ifndef PRODUCT
329 virtual void dump_spec(outputStream *st) const;
330 virtual void related(GrowableArray<Node*> *in_rel, GrowableArray<Node*> *out_rel, bool compact) const;
331 #endif
332 };
333
334 //------------------------------AbsNode----------------------------------------
335 // Abstract class for absolute value. Mostly used to get a handy wrapper
336 // for finding this pattern in the graph.
337 class AbsNode : public Node {
338 public:
339 AbsNode( Node *value ) : Node(0,value) {}
340 };
341
342 //------------------------------AbsINode---------------------------------------
343 // Absolute value an integer. Since a naive graph involves control flow, we
344 // "match" it in the ideal world (so the control flow can be removed).
345 class AbsINode : public AbsNode {
346 public:
347 AbsINode( Node *in1 ) : AbsNode(in1) {}
348 virtual int Opcode() const;
349 const Type *bottom_type() const { return TypeInt::INT; }
350 virtual uint ideal_reg() const { return Op_RegI; }
351 };
352
353 //------------------------------AbsFNode---------------------------------------
354 // Absolute value a float, a common float-point idiom with a cheap hardware
355 // implemention on most chips. Since a naive graph involves control flow, we
356 // "match" it in the ideal world (so the control flow can be removed).
357 class AbsFNode : public AbsNode {
358 public:
359 AbsFNode( Node *in1 ) : AbsNode(in1) {}
360 virtual int Opcode() const;
361 const Type *bottom_type() const { return Type::FLOAT; }
362 virtual uint ideal_reg() const { return Op_RegF; }
363 };
364
365 //------------------------------AbsDNode---------------------------------------
366 // Absolute value a double, 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 AbsDNode : public AbsNode {
370 public:
371 AbsDNode( Node *in1 ) : AbsNode(in1) {}
372 virtual int Opcode() const;
373 const Type *bottom_type() const { return Type::DOUBLE; }
374 virtual uint ideal_reg() const { return Op_RegD; }
375 };
376
377
378 //------------------------------CmpLTMaskNode----------------------------------
379 // If p < q, return -1 else return 0. Nice for flow-free idioms.
380 class CmpLTMaskNode : public Node {
381 public:
382 CmpLTMaskNode( Node *p, Node *q ) : Node(0, p, q) {}
383 virtual int Opcode() const;
384 const Type *bottom_type() const { return TypeInt::INT; }
385 virtual uint ideal_reg() const { return Op_RegI; }
386 };
387
388
389 //------------------------------NegNode----------------------------------------
390 class NegNode : public Node {
391 public:
392 NegNode( Node *in1 ) : Node(0,in1) {}
393 };
394
395 //------------------------------NegFNode---------------------------------------
396 // Negate value a float. Negating 0.0 returns -0.0, but subtracting from
397 // zero returns +0.0 (per JVM spec on 'fneg' bytecode). As subtraction
398 // cannot be used to replace negation we have to implement negation as ideal
399 // node; note that negation and addition can replace subtraction.
400 class NegFNode : public NegNode {
401 public:
402 NegFNode( Node *in1 ) : NegNode(in1) {}
403 virtual int Opcode() const;
404 const Type *bottom_type() const { return Type::FLOAT; }
405 virtual uint ideal_reg() const { return Op_RegF; }
406 };
407
408 //------------------------------NegDNode---------------------------------------
409 // Negate value a double. Negating 0.0 returns -0.0, but subtracting from
410 // zero returns +0.0 (per JVM spec on 'dneg' bytecode). As subtraction
411 // cannot be used to replace negation we have to implement negation as ideal
412 // node; note that negation and addition can replace subtraction.
413 class NegDNode : public NegNode {
414 public:
415 NegDNode( Node *in1 ) : NegNode(in1) {}
416 virtual int Opcode() const;
417 const Type *bottom_type() const { return Type::DOUBLE; }
418 virtual uint ideal_reg() const { return Op_RegD; }
419 };
420
421 //------------------------------AtanDNode--------------------------------------
422 // arcus tangens of a double
423 class AtanDNode : public Node {
424 public:
425 AtanDNode(Node *c, Node *in1, Node *in2 ) : Node(c, in1, in2) {}
426 virtual int Opcode() const;
427 const Type *bottom_type() const { return Type::DOUBLE; }
428 virtual uint ideal_reg() const { return Op_RegD; }
429 };
430
431
432 //------------------------------SqrtDNode--------------------------------------
433 // square root a double
434 class SqrtDNode : public Node {
435 public:
436 SqrtDNode(Compile* C, Node *c, Node *in1) : Node(c, in1) {
437 init_flags(Flag_is_expensive);
438 C->add_expensive_node(this);
439 }
440 virtual int Opcode() const;
441 const Type *bottom_type() const { return Type::DOUBLE; }
442 virtual uint ideal_reg() const { return Op_RegD; }
443 virtual const Type* Value(PhaseGVN* phase) const;
444 };
445
446 //-------------------------------ReverseBytesINode--------------------------------
447 // reverse bytes of an integer
448 class ReverseBytesINode : public Node {
449 public:
450 ReverseBytesINode(Node *c, Node *in1) : Node(c, in1) {}
451 virtual int Opcode() const;
452 const Type *bottom_type() const { return TypeInt::INT; }
453 virtual uint ideal_reg() const { return Op_RegI; }
454 };
455
456 //-------------------------------ReverseBytesLNode--------------------------------
457 // reverse bytes of a long
458 class ReverseBytesLNode : public Node {
459 public:
460 ReverseBytesLNode(Node *c, Node *in1) : Node(c, in1) {}
461 virtual int Opcode() const;
462 const Type *bottom_type() const { return TypeLong::LONG; }
463 virtual uint ideal_reg() const { return Op_RegL; }
464 };
465
466 //-------------------------------ReverseBytesUSNode--------------------------------
467 // reverse bytes of an unsigned short / char
468 class ReverseBytesUSNode : public Node {
469 public:
470 ReverseBytesUSNode(Node *c, Node *in1) : Node(c, in1) {}
471 virtual int Opcode() const;
472 const Type *bottom_type() const { return TypeInt::CHAR; }
473 virtual uint ideal_reg() const { return Op_RegI; }
474 };
475
476 //-------------------------------ReverseBytesSNode--------------------------------
477 // reverse bytes of a short
478 class ReverseBytesSNode : public Node {
479 public:
480 ReverseBytesSNode(Node *c, Node *in1) : Node(c, in1) {}
481 virtual int Opcode() const;
482 const Type *bottom_type() const { return TypeInt::SHORT; }
483 virtual uint ideal_reg() const { return Op_RegI; }
484 };
485
486 #endif // SHARE_VM_OPTO_SUBNODE_HPP