1 /*
2 * Copyright (c) 1997, 2010, 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 // Portions of code courtesy of Clifford Click
26
27 //------------------------------SUBNode----------------------------------------
28 // Class SUBTRACTION functionality. This covers all the usual 'subtract'
29 // behaviors. Subtract-integer, -float, -double, binary xor, compare-integer,
30 // -float, and -double are all inherited from this class. The compare
31 // functions behave like subtract functions, except that all negative answers
32 // are compressed into -1, and all positive answers compressed to 1.
33 class SubNode : public Node {
34 public:
35 SubNode( Node *in1, Node *in2 ) : Node(0,in1,in2) {
36 init_class_id(Class_Sub);
37 }
38
39 // Handle algebraic identities here. If we have an identity, return the Node
40 // we are equivalent to. We look for "add of zero" as an identity.
41 virtual Node *Identity( PhaseTransform *phase );
42
43 // Compute a new Type for this node. Basically we just do the pre-check,
44 // then call the virtual add() to set the type.
45 virtual const Type *Value( PhaseTransform *phase ) const;
46
47 // Supplied function returns the subtractend of the inputs.
48 // This also type-checks the inputs for sanity. Guaranteed never to
49 // be passed a TOP or BOTTOM type, these are filtered out by a pre-check.
50 virtual const Type *sub( const Type *, const Type * ) const = 0;
51
52 // Supplied function to return the additive identity type.
53 // This is returned whenever the subtracts inputs are the same.
54 virtual const Type *add_id() const = 0;
55
56 };
57
58
59 // NOTE: SubINode should be taken away and replaced by add and negate
60 //------------------------------SubINode---------------------------------------
61 // Subtract 2 integers
62 class SubINode : public SubNode {
63 public:
64 SubINode( Node *in1, Node *in2 ) : SubNode(in1,in2) {}
65 virtual int Opcode() const;
66 virtual Node *Ideal(PhaseGVN *phase, bool can_reshape);
67 virtual const Type *sub( const Type *, const Type * ) const;
68 const Type *add_id() const { return TypeInt::ZERO; }
69 const Type *bottom_type() const { return TypeInt::INT; }
70 virtual uint ideal_reg() const { return Op_RegI; }
71 };
72
73 //------------------------------SubLNode---------------------------------------
74 // Subtract 2 integers
75 class SubLNode : public SubNode {
76 public:
77 SubLNode( Node *in1, Node *in2 ) : SubNode(in1,in2) {}
78 virtual int Opcode() const;
79 virtual Node *Ideal(PhaseGVN *phase, bool can_reshape);
80 virtual const Type *sub( const Type *, const Type * ) const;
81 const Type *add_id() const { return TypeLong::ZERO; }
82 const Type *bottom_type() const { return TypeLong::LONG; }
83 virtual uint ideal_reg() const { return Op_RegL; }
84 };
85
86 // NOTE: SubFPNode should be taken away and replaced by add and negate
87 //------------------------------SubFPNode--------------------------------------
88 // Subtract 2 floats or doubles
89 class SubFPNode : public SubNode {
90 protected:
91 SubFPNode( Node *in1, Node *in2 ) : SubNode(in1,in2) {}
92 public:
93 const Type *Value( PhaseTransform *phase ) const;
94 };
95
96 // NOTE: SubFNode should be taken away and replaced by add and negate
97 //------------------------------SubFNode---------------------------------------
98 // Subtract 2 doubles
99 class SubFNode : public SubFPNode {
100 public:
101 SubFNode( Node *in1, Node *in2 ) : SubFPNode(in1,in2) {}
102 virtual int Opcode() const;
103 virtual Node *Ideal(PhaseGVN *phase, bool can_reshape);
104 virtual const Type *sub( const Type *, const Type * ) const;
105 const Type *add_id() const { return TypeF::ZERO; }
106 const Type *bottom_type() const { return Type::FLOAT; }
107 virtual uint ideal_reg() const { return Op_RegF; }
108 };
109
110 // NOTE: SubDNode should be taken away and replaced by add and negate
111 //------------------------------SubDNode---------------------------------------
112 // Subtract 2 doubles
113 class SubDNode : public SubFPNode {
114 public:
115 SubDNode( Node *in1, Node *in2 ) : SubFPNode(in1,in2) {}
116 virtual int Opcode() const;
117 virtual Node *Ideal(PhaseGVN *phase, bool can_reshape);
118 virtual const Type *sub( const Type *, const Type * ) const;
119 const Type *add_id() const { return TypeD::ZERO; }
120 const Type *bottom_type() const { return Type::DOUBLE; }
121 virtual uint ideal_reg() const { return Op_RegD; }
122 };
123
124 //------------------------------CmpNode---------------------------------------
125 // Compare 2 values, returning condition codes (-1, 0 or 1).
126 class CmpNode : public SubNode {
127 public:
128 CmpNode( Node *in1, Node *in2 ) : SubNode(in1,in2) {
129 init_class_id(Class_Cmp);
130 }
131 virtual Node *Identity( PhaseTransform *phase );
132 const Type *add_id() const { return TypeInt::ZERO; }
133 const Type *bottom_type() const { return TypeInt::CC; }
134 virtual uint ideal_reg() const { return Op_RegFlags; }
135 };
136
137 //------------------------------CmpINode---------------------------------------
138 // Compare 2 signed values, returning condition codes (-1, 0 or 1).
139 class CmpINode : public CmpNode {
140 public:
141 CmpINode( Node *in1, Node *in2 ) : CmpNode(in1,in2) {}
142 virtual int Opcode() const;
143 virtual Node *Ideal(PhaseGVN *phase, bool can_reshape);
144 virtual const Type *sub( const Type *, const Type * ) const;
145 };
146
147 //------------------------------CmpUNode---------------------------------------
148 // Compare 2 unsigned values (integer or pointer), returning condition codes (-1, 0 or 1).
149 class CmpUNode : public CmpNode {
150 public:
151 CmpUNode( Node *in1, Node *in2 ) : CmpNode(in1,in2) {}
152 virtual int Opcode() const;
153 virtual const Type *sub( const Type *, const Type * ) const;
154 };
155
156 //------------------------------CmpPNode---------------------------------------
157 // Compare 2 pointer values, returning condition codes (-1, 0 or 1).
158 class CmpPNode : public CmpNode {
159 public:
160 CmpPNode( Node *in1, Node *in2 ) : CmpNode(in1,in2) {}
161 virtual int Opcode() const;
162 virtual Node *Ideal(PhaseGVN *phase, bool can_reshape);
163 virtual const Type *sub( const Type *, const Type * ) const;
164 };
165
166 //------------------------------CmpNNode--------------------------------------
167 // Compare 2 narrow oop values, returning condition codes (-1, 0 or 1).
168 class CmpNNode : public CmpNode {
169 public:
170 CmpNNode( Node *in1, Node *in2 ) : CmpNode(in1,in2) {}
171 virtual int Opcode() const;
172 virtual Node *Ideal(PhaseGVN *phase, bool can_reshape);
173 virtual const Type *sub( const Type *, const Type * ) const;
174 };
175
176 //------------------------------CmpLNode---------------------------------------
177 // Compare 2 long values, returning condition codes (-1, 0 or 1).
178 class CmpLNode : public CmpNode {
179 public:
180 CmpLNode( Node *in1, Node *in2 ) : CmpNode(in1,in2) {}
181 virtual int Opcode() const;
182 virtual const Type *sub( const Type *, const Type * ) const;
183 };
184
185 //------------------------------CmpL3Node--------------------------------------
186 // Compare 2 long values, returning integer value (-1, 0 or 1).
187 class CmpL3Node : public CmpLNode {
188 public:
189 CmpL3Node( Node *in1, Node *in2 ) : CmpLNode(in1,in2) {
190 // Since it is not consumed by Bools, it is not really a Cmp.
191 init_class_id(Class_Sub);
192 }
193 virtual int Opcode() const;
194 virtual uint ideal_reg() const { return Op_RegI; }
195 };
196
197 //------------------------------CmpFNode---------------------------------------
198 // Compare 2 float values, returning condition codes (-1, 0 or 1).
199 // This implements the Java bytecode fcmpl, so unordered returns -1.
200 // Operands may not commute.
201 class CmpFNode : public CmpNode {
202 public:
203 CmpFNode( Node *in1, Node *in2 ) : CmpNode(in1,in2) {}
204 virtual int Opcode() const;
205 virtual const Type *sub( const Type *, const Type * ) const { ShouldNotReachHere(); return NULL; }
206 const Type *Value( PhaseTransform *phase ) const;
207 };
208
209 //------------------------------CmpF3Node--------------------------------------
210 // Compare 2 float values, returning integer value (-1, 0 or 1).
211 // This implements the Java bytecode fcmpl, so unordered returns -1.
212 // Operands may not commute.
213 class CmpF3Node : public CmpFNode {
214 public:
215 CmpF3Node( Node *in1, Node *in2 ) : CmpFNode(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 // Since it is not consumed by Bools, it is not really a Cmp.
221 virtual uint ideal_reg() const { return Op_RegI; }
222 };
223
224
225 //------------------------------CmpDNode---------------------------------------
226 // Compare 2 double values, returning condition codes (-1, 0 or 1).
227 // This implements the Java bytecode dcmpl, so unordered returns -1.
228 // Operands may not commute.
229 class CmpDNode : public CmpNode {
230 public:
231 CmpDNode( 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( PhaseTransform *phase ) const;
235 virtual Node *Ideal(PhaseGVN *phase, bool can_reshape);
236 };
237
238 //------------------------------CmpD3Node--------------------------------------
239 // Compare 2 double values, returning integer value (-1, 0 or 1).
240 // This implements the Java bytecode dcmpl, so unordered returns -1.
241 // Operands may not commute.
242 class CmpD3Node : public CmpDNode {
243 public:
244 CmpD3Node( Node *in1, Node *in2 ) : CmpDNode(in1,in2) {
245 // Since it is not consumed by Bools, it is not really a Cmp.
246 init_class_id(Class_Sub);
247 }
248 virtual int Opcode() const;
249 virtual uint ideal_reg() const { return Op_RegI; }
250 };
251
252
253 //------------------------------BoolTest---------------------------------------
254 // Convert condition codes to a boolean test value (0 or -1).
255 // We pick the values as 3 bits; the low order 2 bits we compare against the
256 // condition codes, the high bit flips the sense of the result.
257 struct BoolTest VALUE_OBJ_CLASS_SPEC {
258 enum mask { eq = 0, ne = 4, le = 5, ge = 7, lt = 3, gt = 1, illegal = 8 };
259 mask _test;
260 BoolTest( mask btm ) : _test(btm) {}
261 const Type *cc2logical( const Type *CC ) const;
262 // Commute the test. I use a small table lookup. The table is created as
263 // a simple char array where each element is the ASCII version of a 'mask'
264 // enum from above.
265 mask commute( ) const { return mask("038147858"[_test]-'0'); }
266 mask negate( ) const { return mask(_test^4); }
267 bool is_canonical( ) const { return (_test == BoolTest::ne || _test == BoolTest::lt || _test == BoolTest::le); }
268 #ifndef PRODUCT
269 void dump_on(outputStream *st) const;
270 #endif
271 };
272
273 //------------------------------BoolNode---------------------------------------
274 // A Node to convert a Condition Codes to a Logical result.
275 class BoolNode : public Node {
276 virtual uint hash() const;
277 virtual uint cmp( const Node &n ) const;
278 virtual uint size_of() const;
279 public:
280 const BoolTest _test;
281 BoolNode( Node *cc, BoolTest::mask t): _test(t), Node(0,cc) {
282 init_class_id(Class_Bool);
283 }
284 // Convert an arbitrary int value to a Bool or other suitable predicate.
285 static Node* make_predicate(Node* test_value, PhaseGVN* phase);
286 // Convert self back to an integer value.
287 Node* as_int_value(PhaseGVN* phase);
288 // Invert sense of self, returning new Bool.
289 BoolNode* negate(PhaseGVN* phase);
290 virtual int Opcode() const;
291 virtual Node *Ideal(PhaseGVN *phase, bool can_reshape);
292 virtual const Type *Value( PhaseTransform *phase ) const;
293 virtual const Type *bottom_type() const { return TypeInt::BOOL; }
294 uint match_edge(uint idx) const { return 0; }
295 virtual uint ideal_reg() const { return Op_RegI; }
296
297 bool is_counted_loop_exit_test();
298 #ifndef PRODUCT
299 virtual void dump_spec(outputStream *st) const;
300 #endif
301 };
302
303 //------------------------------AbsNode----------------------------------------
304 // Abstract class for absolute value. Mostly used to get a handy wrapper
305 // for finding this pattern in the graph.
306 class AbsNode : public Node {
307 public:
308 AbsNode( Node *value ) : Node(0,value) {}
309 };
310
311 //------------------------------AbsINode---------------------------------------
312 // Absolute value an integer. Since a naive graph involves control flow, we
313 // "match" it in the ideal world (so the control flow can be removed).
314 class AbsINode : public AbsNode {
315 public:
316 AbsINode( Node *in1 ) : AbsNode(in1) {}
317 virtual int Opcode() const;
318 const Type *bottom_type() const { return TypeInt::INT; }
319 virtual uint ideal_reg() const { return Op_RegI; }
320 };
321
322 //------------------------------AbsFNode---------------------------------------
323 // Absolute value a float, a common float-point idiom with a cheap hardware
324 // implemention on most chips. Since a naive graph involves control flow, we
325 // "match" it in the ideal world (so the control flow can be removed).
326 class AbsFNode : public AbsNode {
327 public:
328 AbsFNode( Node *in1 ) : AbsNode(in1) {}
329 virtual int Opcode() const;
330 const Type *bottom_type() const { return Type::FLOAT; }
331 virtual uint ideal_reg() const { return Op_RegF; }
332 };
333
334 //------------------------------AbsDNode---------------------------------------
335 // Absolute value a double, a common float-point idiom with a cheap hardware
336 // implemention on most chips. Since a naive graph involves control flow, we
337 // "match" it in the ideal world (so the control flow can be removed).
338 class AbsDNode : public AbsNode {
339 public:
340 AbsDNode( Node *in1 ) : AbsNode(in1) {}
341 virtual int Opcode() const;
342 const Type *bottom_type() const { return Type::DOUBLE; }
343 virtual uint ideal_reg() const { return Op_RegD; }
344 };
345
346
347 //------------------------------CmpLTMaskNode----------------------------------
348 // If p < q, return -1 else return 0. Nice for flow-free idioms.
349 class CmpLTMaskNode : public Node {
350 public:
351 CmpLTMaskNode( Node *p, Node *q ) : Node(0, p, q) {}
352 virtual int Opcode() const;
353 const Type *bottom_type() const { return TypeInt::INT; }
354 virtual uint ideal_reg() const { return Op_RegI; }
355 };
356
357
358 //------------------------------NegNode----------------------------------------
359 class NegNode : public Node {
360 public:
361 NegNode( Node *in1 ) : Node(0,in1) {}
362 };
363
364 //------------------------------NegFNode---------------------------------------
365 // Negate value a float. Negating 0.0 returns -0.0, but subtracting from
366 // zero returns +0.0 (per JVM spec on 'fneg' bytecode). As subtraction
367 // cannot be used to replace negation we have to implement negation as ideal
368 // node; note that negation and addition can replace subtraction.
369 class NegFNode : public NegNode {
370 public:
371 NegFNode( Node *in1 ) : NegNode(in1) {}
372 virtual int Opcode() const;
373 virtual Node *Ideal(PhaseGVN *phase, bool can_reshape);
374 const Type *bottom_type() const { return Type::FLOAT; }
375 virtual uint ideal_reg() const { return Op_RegF; }
376 };
377
378 //------------------------------NegDNode---------------------------------------
379 // Negate value a double. Negating 0.0 returns -0.0, but subtracting from
380 // zero returns +0.0 (per JVM spec on 'dneg' bytecode). As subtraction
381 // cannot be used to replace negation we have to implement negation as ideal
382 // node; note that negation and addition can replace subtraction.
383 class NegDNode : public NegNode {
384 public:
385 NegDNode( Node *in1 ) : NegNode(in1) {}
386 virtual int Opcode() const;
387 virtual Node *Ideal(PhaseGVN *phase, bool can_reshape);
388 const Type *bottom_type() const { return Type::DOUBLE; }
389 virtual uint ideal_reg() const { return Op_RegD; }
390 };
391
392 //------------------------------CosDNode---------------------------------------
393 // Cosinus of a double
394 class CosDNode : public Node {
395 public:
396 CosDNode( Node *in1 ) : Node(0, in1) {}
397 virtual int Opcode() const;
398 const Type *bottom_type() const { return Type::DOUBLE; }
399 virtual uint ideal_reg() const { return Op_RegD; }
400 virtual const Type *Value( PhaseTransform *phase ) const;
401 };
402
403 //------------------------------CosDNode---------------------------------------
404 // Sinus of a double
405 class SinDNode : public Node {
406 public:
407 SinDNode( Node *in1 ) : Node(0, 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 virtual const Type *Value( PhaseTransform *phase ) const;
412 };
413
414
415 //------------------------------TanDNode---------------------------------------
416 // tangens of a double
417 class TanDNode : public Node {
418 public:
419 TanDNode(Node *in1 ) : Node(0, in1) {}
420 virtual int Opcode() const;
421 const Type *bottom_type() const { return Type::DOUBLE; }
422 virtual uint ideal_reg() const { return Op_RegD; }
423 virtual const Type *Value( PhaseTransform *phase ) const;
424 };
425
426
427 //------------------------------AtanDNode--------------------------------------
428 // arcus tangens of a double
429 class AtanDNode : public Node {
430 public:
431 AtanDNode(Node *c, Node *in1, Node *in2 ) : Node(c, in1, in2) {}
432 virtual int Opcode() const;
433 const Type *bottom_type() const { return Type::DOUBLE; }
434 virtual uint ideal_reg() const { return Op_RegD; }
435 };
436
437
438 //------------------------------SqrtDNode--------------------------------------
439 // square root a double
440 class SqrtDNode : public Node {
441 public:
442 SqrtDNode(Node *c, Node *in1 ) : Node(c, in1) {}
443 virtual int Opcode() const;
444 const Type *bottom_type() const { return Type::DOUBLE; }
445 virtual uint ideal_reg() const { return Op_RegD; }
446 virtual const Type *Value( PhaseTransform *phase ) const;
447 };
448
449 //------------------------------ExpDNode---------------------------------------
450 // Exponentiate a double
451 class ExpDNode : public Node {
452 public:
453 ExpDNode( Node *c, Node *in1 ) : Node(c, in1) {}
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( PhaseTransform *phase ) const;
458 };
459
460 //------------------------------LogDNode---------------------------------------
461 // Log_e of a double
462 class LogDNode : public Node {
463 public:
464 LogDNode( Node *in1 ) : Node(0, in1) {}
465 virtual int Opcode() const;
466 const Type *bottom_type() const { return Type::DOUBLE; }
467 virtual uint ideal_reg() const { return Op_RegD; }
468 virtual const Type *Value( PhaseTransform *phase ) const;
469 };
470
471 //------------------------------Log10DNode---------------------------------------
472 // Log_10 of a double
473 class Log10DNode : public Node {
474 public:
475 Log10DNode( Node *in1 ) : Node(0, in1) {}
476 virtual int Opcode() const;
477 const Type *bottom_type() const { return Type::DOUBLE; }
478 virtual uint ideal_reg() const { return Op_RegD; }
479 virtual const Type *Value( PhaseTransform *phase ) const;
480 };
481
482 //------------------------------PowDNode---------------------------------------
483 // Raise a double to a double power
484 class PowDNode : public Node {
485 public:
486 PowDNode(Node *c, Node *in1, Node *in2 ) : Node(c, in1, in2) {}
487 virtual int Opcode() const;
488 const Type *bottom_type() const { return Type::DOUBLE; }
489 virtual uint ideal_reg() const { return Op_RegD; }
490 virtual const Type *Value( PhaseTransform *phase ) const;
491 };
492
493 //-------------------------------ReverseBytesINode--------------------------------
494 // reverse bytes of an integer
495 class ReverseBytesINode : public Node {
496 public:
497 ReverseBytesINode(Node *c, Node *in1) : Node(c, in1) {}
498 virtual int Opcode() const;
499 const Type *bottom_type() const { return TypeInt::INT; }
500 virtual uint ideal_reg() const { return Op_RegI; }
501 };
502
503 //-------------------------------ReverseBytesLNode--------------------------------
504 // reverse bytes of a long
505 class ReverseBytesLNode : public Node {
506 public:
507 ReverseBytesLNode(Node *c, Node *in1) : Node(c, in1) {}
508 virtual int Opcode() const;
509 const Type *bottom_type() const { return TypeLong::LONG; }
510 virtual uint ideal_reg() const { return Op_RegL; }
511 };
512
513 //-------------------------------ReverseBytesUSNode--------------------------------
514 // reverse bytes of an unsigned short / char
515 class ReverseBytesUSNode : public Node {
516 public:
517 ReverseBytesUSNode(Node *c, Node *in1) : Node(c, in1) {}
518 virtual int Opcode() const;
519 const Type *bottom_type() const { return TypeInt::CHAR; }
520 virtual uint ideal_reg() const { return Op_RegI; }
521 };
522
523 //-------------------------------ReverseBytesSNode--------------------------------
524 // reverse bytes of a short
525 class ReverseBytesSNode : public Node {
526 public:
527 ReverseBytesSNode(Node *c, Node *in1) : Node(c, in1) {}
528 virtual int Opcode() const;
529 const Type *bottom_type() const { return TypeInt::SHORT; }
530 virtual uint ideal_reg() const { return Op_RegI; }
531 };