duke@435: /* duke@435: * Copyright 1997-2006 Sun Microsystems, Inc. All Rights Reserved. duke@435: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. duke@435: * duke@435: * This code is free software; you can redistribute it and/or modify it duke@435: * under the terms of the GNU General Public License version 2 only, as duke@435: * published by the Free Software Foundation. duke@435: * duke@435: * This code is distributed in the hope that it will be useful, but WITHOUT duke@435: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or duke@435: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License duke@435: * version 2 for more details (a copy is included in the LICENSE file that duke@435: * accompanied this code). duke@435: * duke@435: * You should have received a copy of the GNU General Public License version duke@435: * 2 along with this work; if not, write to the Free Software Foundation, duke@435: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. duke@435: * duke@435: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, duke@435: * CA 95054 USA or visit www.sun.com if you need additional information or duke@435: * have any questions. duke@435: * duke@435: */ duke@435: duke@435: // Portions of code courtesy of Clifford Click duke@435: duke@435: //------------------------------SUBNode---------------------------------------- duke@435: // Class SUBTRACTION functionality. This covers all the usual 'subtract' duke@435: // behaviors. Subtract-integer, -float, -double, binary xor, compare-integer, duke@435: // -float, and -double are all inherited from this class. The compare duke@435: // functions behave like subtract functions, except that all negative answers duke@435: // are compressed into -1, and all positive answers compressed to 1. duke@435: class SubNode : public Node { duke@435: public: duke@435: SubNode( Node *in1, Node *in2 ) : Node(0,in1,in2) { duke@435: init_class_id(Class_Sub); duke@435: } duke@435: duke@435: // Handle algebraic identities here. If we have an identity, return the Node duke@435: // we are equivalent to. We look for "add of zero" as an identity. duke@435: virtual Node *Identity( PhaseTransform *phase ); duke@435: duke@435: // Compute a new Type for this node. Basically we just do the pre-check, duke@435: // then call the virtual add() to set the type. duke@435: virtual const Type *Value( PhaseTransform *phase ) const; duke@435: duke@435: // Supplied function returns the subtractend of the inputs. duke@435: // This also type-checks the inputs for sanity. Guaranteed never to duke@435: // be passed a TOP or BOTTOM type, these are filtered out by a pre-check. duke@435: virtual const Type *sub( const Type *, const Type * ) const = 0; duke@435: duke@435: // Supplied function to return the additive identity type. duke@435: // This is returned whenever the subtracts inputs are the same. duke@435: virtual const Type *add_id() const = 0; duke@435: duke@435: }; duke@435: duke@435: duke@435: // NOTE: SubINode should be taken away and replaced by add and negate duke@435: //------------------------------SubINode--------------------------------------- duke@435: // Subtract 2 integers duke@435: class SubINode : public SubNode { duke@435: public: duke@435: SubINode( Node *in1, Node *in2 ) : SubNode(in1,in2) {} duke@435: virtual int Opcode() const; duke@435: virtual Node *Ideal(PhaseGVN *phase, bool can_reshape); duke@435: virtual const Type *sub( const Type *, const Type * ) const; duke@435: const Type *add_id() const { return TypeInt::ZERO; } duke@435: const Type *bottom_type() const { return TypeInt::INT; } duke@435: virtual uint ideal_reg() const { return Op_RegI; } duke@435: }; duke@435: duke@435: //------------------------------SubLNode--------------------------------------- duke@435: // Subtract 2 integers duke@435: class SubLNode : public SubNode { duke@435: public: duke@435: SubLNode( Node *in1, Node *in2 ) : SubNode(in1,in2) {} duke@435: virtual int Opcode() const; duke@435: virtual Node *Ideal(PhaseGVN *phase, bool can_reshape); duke@435: virtual const Type *sub( const Type *, const Type * ) const; duke@435: const Type *add_id() const { return TypeLong::ZERO; } duke@435: const Type *bottom_type() const { return TypeLong::LONG; } duke@435: virtual uint ideal_reg() const { return Op_RegL; } duke@435: }; duke@435: duke@435: // NOTE: SubFPNode should be taken away and replaced by add and negate duke@435: //------------------------------SubFPNode-------------------------------------- duke@435: // Subtract 2 floats or doubles duke@435: class SubFPNode : public SubNode { duke@435: protected: duke@435: SubFPNode( Node *in1, Node *in2 ) : SubNode(in1,in2) {} duke@435: public: duke@435: const Type *Value( PhaseTransform *phase ) const; duke@435: }; duke@435: duke@435: // NOTE: SubFNode should be taken away and replaced by add and negate duke@435: //------------------------------SubFNode--------------------------------------- duke@435: // Subtract 2 doubles duke@435: class SubFNode : public SubFPNode { duke@435: public: duke@435: SubFNode( Node *in1, Node *in2 ) : SubFPNode(in1,in2) {} duke@435: virtual int Opcode() const; duke@435: virtual Node *Ideal(PhaseGVN *phase, bool can_reshape); duke@435: virtual const Type *sub( const Type *, const Type * ) const; duke@435: const Type *add_id() const { return TypeF::ZERO; } duke@435: const Type *bottom_type() const { return Type::FLOAT; } duke@435: virtual uint ideal_reg() const { return Op_RegF; } duke@435: }; duke@435: duke@435: // NOTE: SubDNode should be taken away and replaced by add and negate duke@435: //------------------------------SubDNode--------------------------------------- duke@435: // Subtract 2 doubles duke@435: class SubDNode : public SubFPNode { duke@435: public: duke@435: SubDNode( Node *in1, Node *in2 ) : SubFPNode(in1,in2) {} duke@435: virtual int Opcode() const; duke@435: virtual Node *Ideal(PhaseGVN *phase, bool can_reshape); duke@435: virtual const Type *sub( const Type *, const Type * ) const; duke@435: const Type *add_id() const { return TypeD::ZERO; } duke@435: const Type *bottom_type() const { return Type::DOUBLE; } duke@435: virtual uint ideal_reg() const { return Op_RegD; } duke@435: }; duke@435: duke@435: //------------------------------CmpNode--------------------------------------- duke@435: // Compare 2 values, returning condition codes (-1, 0 or 1). duke@435: class CmpNode : public SubNode { duke@435: public: duke@435: CmpNode( Node *in1, Node *in2 ) : SubNode(in1,in2) { duke@435: init_class_id(Class_Cmp); duke@435: } duke@435: virtual Node *Identity( PhaseTransform *phase ); duke@435: const Type *add_id() const { return TypeInt::ZERO; } duke@435: const Type *bottom_type() const { return TypeInt::CC; } duke@435: virtual uint ideal_reg() const { return Op_RegFlags; } duke@435: }; duke@435: duke@435: //------------------------------CmpINode--------------------------------------- duke@435: // Compare 2 signed values, returning condition codes (-1, 0 or 1). duke@435: class CmpINode : public CmpNode { duke@435: public: duke@435: CmpINode( Node *in1, Node *in2 ) : CmpNode(in1,in2) {} duke@435: virtual int Opcode() const; duke@435: virtual Node *Ideal(PhaseGVN *phase, bool can_reshape); duke@435: virtual const Type *sub( const Type *, const Type * ) const; duke@435: }; duke@435: duke@435: //------------------------------CmpUNode--------------------------------------- duke@435: // Compare 2 unsigned values (integer or pointer), returning condition codes (-1, 0 or 1). duke@435: class CmpUNode : public CmpNode { duke@435: public: duke@435: CmpUNode( Node *in1, Node *in2 ) : CmpNode(in1,in2) {} duke@435: virtual int Opcode() const; duke@435: virtual const Type *sub( const Type *, const Type * ) const; duke@435: }; duke@435: duke@435: //------------------------------CmpPNode--------------------------------------- duke@435: // Compare 2 pointer values, returning condition codes (-1, 0 or 1). duke@435: class CmpPNode : public CmpNode { duke@435: public: duke@435: CmpPNode( Node *in1, Node *in2 ) : CmpNode(in1,in2) {} duke@435: virtual int Opcode() const; duke@435: virtual Node *Ideal(PhaseGVN *phase, bool can_reshape); duke@435: virtual const Type *sub( const Type *, const Type * ) const; duke@435: }; duke@435: duke@435: //------------------------------CmpLNode--------------------------------------- duke@435: // Compare 2 long values, returning condition codes (-1, 0 or 1). duke@435: class CmpLNode : public CmpNode { duke@435: public: duke@435: CmpLNode( Node *in1, Node *in2 ) : CmpNode(in1,in2) {} duke@435: virtual int Opcode() const; duke@435: virtual const Type *sub( const Type *, const Type * ) const; duke@435: }; duke@435: duke@435: //------------------------------CmpL3Node-------------------------------------- duke@435: // Compare 2 long values, returning integer value (-1, 0 or 1). duke@435: class CmpL3Node : public CmpLNode { duke@435: public: duke@435: CmpL3Node( Node *in1, Node *in2 ) : CmpLNode(in1,in2) { duke@435: // Since it is not consumed by Bools, it is not really a Cmp. duke@435: init_class_id(Class_Sub); duke@435: } duke@435: virtual int Opcode() const; duke@435: virtual uint ideal_reg() const { return Op_RegI; } duke@435: }; duke@435: duke@435: //------------------------------CmpFNode--------------------------------------- duke@435: // Compare 2 float values, returning condition codes (-1, 0 or 1). duke@435: // This implements the Java bytecode fcmpl, so unordered returns -1. duke@435: // Operands may not commute. duke@435: class CmpFNode : public CmpNode { duke@435: public: duke@435: CmpFNode( Node *in1, Node *in2 ) : CmpNode(in1,in2) {} duke@435: virtual int Opcode() const; duke@435: virtual const Type *sub( const Type *, const Type * ) const { ShouldNotReachHere(); return NULL; } duke@435: const Type *Value( PhaseTransform *phase ) const; duke@435: }; duke@435: duke@435: //------------------------------CmpF3Node-------------------------------------- duke@435: // Compare 2 float values, returning integer value (-1, 0 or 1). duke@435: // This implements the Java bytecode fcmpl, so unordered returns -1. duke@435: // Operands may not commute. duke@435: class CmpF3Node : public CmpFNode { duke@435: public: duke@435: CmpF3Node( Node *in1, Node *in2 ) : CmpFNode(in1,in2) { duke@435: // Since it is not consumed by Bools, it is not really a Cmp. duke@435: init_class_id(Class_Sub); duke@435: } duke@435: virtual int Opcode() const; duke@435: // Since it is not consumed by Bools, it is not really a Cmp. duke@435: virtual uint ideal_reg() const { return Op_RegI; } duke@435: }; duke@435: duke@435: duke@435: //------------------------------CmpDNode--------------------------------------- duke@435: // Compare 2 double values, returning condition codes (-1, 0 or 1). duke@435: // This implements the Java bytecode dcmpl, so unordered returns -1. duke@435: // Operands may not commute. duke@435: class CmpDNode : public CmpNode { duke@435: public: duke@435: CmpDNode( Node *in1, Node *in2 ) : CmpNode(in1,in2) {} duke@435: virtual int Opcode() const; duke@435: virtual const Type *sub( const Type *, const Type * ) const { ShouldNotReachHere(); return NULL; } duke@435: const Type *Value( PhaseTransform *phase ) const; duke@435: virtual Node *Ideal(PhaseGVN *phase, bool can_reshape); duke@435: }; duke@435: duke@435: //------------------------------CmpD3Node-------------------------------------- duke@435: // Compare 2 double values, returning integer value (-1, 0 or 1). duke@435: // This implements the Java bytecode dcmpl, so unordered returns -1. duke@435: // Operands may not commute. duke@435: class CmpD3Node : public CmpDNode { duke@435: public: duke@435: CmpD3Node( Node *in1, Node *in2 ) : CmpDNode(in1,in2) { duke@435: // Since it is not consumed by Bools, it is not really a Cmp. duke@435: init_class_id(Class_Sub); duke@435: } duke@435: virtual int Opcode() const; duke@435: virtual uint ideal_reg() const { return Op_RegI; } duke@435: }; duke@435: duke@435: duke@435: //------------------------------BoolTest--------------------------------------- duke@435: // Convert condition codes to a boolean test value (0 or -1). duke@435: // We pick the values as 3 bits; the low order 2 bits we compare against the duke@435: // condition codes, the high bit flips the sense of the result. duke@435: struct BoolTest VALUE_OBJ_CLASS_SPEC { duke@435: enum mask { eq = 0, ne = 4, le = 5, ge = 7, lt = 3, gt = 1, illegal = 8 }; duke@435: mask _test; duke@435: BoolTest( mask btm ) : _test(btm) {} duke@435: const Type *cc2logical( const Type *CC ) const; duke@435: // Commute the test. I use a small table lookup. The table is created as duke@435: // a simple char array where each element is the ASCII version of a 'mask' duke@435: // enum from above. duke@435: mask commute( ) const { return mask("038147858"[_test]-'0'); } duke@435: mask negate( ) const { return mask(_test^4); } duke@435: bool is_canonical( ) const { return (_test == BoolTest::ne || _test == BoolTest::lt || _test == BoolTest::le); } duke@435: #ifndef PRODUCT duke@435: void dump_on(outputStream *st) const; duke@435: #endif duke@435: }; duke@435: duke@435: //------------------------------BoolNode--------------------------------------- duke@435: // A Node to convert a Condition Codes to a Logical result. duke@435: class BoolNode : public Node { duke@435: virtual uint hash() const; duke@435: virtual uint cmp( const Node &n ) const; duke@435: virtual uint size_of() const; duke@435: public: duke@435: const BoolTest _test; duke@435: BoolNode( Node *cc, BoolTest::mask t): _test(t), Node(0,cc) { duke@435: init_class_id(Class_Bool); duke@435: } duke@435: // Convert an arbitrary int value to a Bool or other suitable predicate. duke@435: static Node* make_predicate(Node* test_value, PhaseGVN* phase); duke@435: // Convert self back to an integer value. duke@435: Node* as_int_value(PhaseGVN* phase); duke@435: // Invert sense of self, returning new Bool. duke@435: BoolNode* negate(PhaseGVN* phase); duke@435: virtual int Opcode() const; duke@435: virtual Node *Ideal(PhaseGVN *phase, bool can_reshape); duke@435: virtual const Type *Value( PhaseTransform *phase ) const; duke@435: virtual const Type *bottom_type() const { return TypeInt::BOOL; } duke@435: uint match_edge(uint idx) const { return 0; } duke@435: virtual uint ideal_reg() const { return Op_RegI; } duke@435: duke@435: bool is_counted_loop_exit_test(); duke@435: #ifndef PRODUCT duke@435: virtual void dump_spec(outputStream *st) const; duke@435: #endif duke@435: }; duke@435: duke@435: //------------------------------AbsNode---------------------------------------- duke@435: // Abstract class for absolute value. Mostly used to get a handy wrapper duke@435: // for finding this pattern in the graph. duke@435: class AbsNode : public Node { duke@435: public: duke@435: AbsNode( Node *value ) : Node(0,value) {} duke@435: }; duke@435: duke@435: //------------------------------AbsINode--------------------------------------- duke@435: // Absolute value an integer. Since a naive graph involves control flow, we duke@435: // "match" it in the ideal world (so the control flow can be removed). duke@435: class AbsINode : public AbsNode { duke@435: public: duke@435: AbsINode( Node *in1 ) : AbsNode(in1) {} duke@435: virtual int Opcode() const; duke@435: const Type *bottom_type() const { return TypeInt::INT; } duke@435: virtual uint ideal_reg() const { return Op_RegI; } duke@435: }; duke@435: duke@435: //------------------------------AbsFNode--------------------------------------- duke@435: // Absolute value a float, a common float-point idiom with a cheap hardware duke@435: // implemention on most chips. Since a naive graph involves control flow, we duke@435: // "match" it in the ideal world (so the control flow can be removed). duke@435: class AbsFNode : public AbsNode { duke@435: public: duke@435: AbsFNode( Node *in1 ) : AbsNode(in1) {} duke@435: virtual int Opcode() const; duke@435: const Type *bottom_type() const { return Type::FLOAT; } duke@435: virtual uint ideal_reg() const { return Op_RegF; } duke@435: }; duke@435: duke@435: //------------------------------AbsDNode--------------------------------------- duke@435: // Absolute value a double, a common float-point idiom with a cheap hardware duke@435: // implemention on most chips. Since a naive graph involves control flow, we duke@435: // "match" it in the ideal world (so the control flow can be removed). duke@435: class AbsDNode : public AbsNode { duke@435: public: duke@435: AbsDNode( Node *in1 ) : AbsNode(in1) {} duke@435: virtual int Opcode() const; duke@435: const Type *bottom_type() const { return Type::DOUBLE; } duke@435: virtual uint ideal_reg() const { return Op_RegD; } duke@435: }; duke@435: duke@435: duke@435: //------------------------------CmpLTMaskNode---------------------------------- duke@435: // If p < q, return -1 else return 0. Nice for flow-free idioms. duke@435: class CmpLTMaskNode : public Node { duke@435: public: duke@435: CmpLTMaskNode( Node *p, Node *q ) : Node(0, p, q) {} duke@435: virtual int Opcode() const; duke@435: const Type *bottom_type() const { return TypeInt::INT; } duke@435: virtual uint ideal_reg() const { return Op_RegI; } duke@435: }; duke@435: duke@435: duke@435: //------------------------------NegNode---------------------------------------- duke@435: class NegNode : public Node { duke@435: public: duke@435: NegNode( Node *in1 ) : Node(0,in1) {} duke@435: }; duke@435: duke@435: //------------------------------NegFNode--------------------------------------- duke@435: // Negate value a float. Negating 0.0 returns -0.0, but subtracting from duke@435: // zero returns +0.0 (per JVM spec on 'fneg' bytecode). As subtraction duke@435: // cannot be used to replace negation we have to implement negation as ideal duke@435: // node; note that negation and addition can replace subtraction. duke@435: class NegFNode : public NegNode { duke@435: public: duke@435: NegFNode( Node *in1 ) : NegNode(in1) {} duke@435: virtual int Opcode() const; duke@435: virtual Node *Ideal(PhaseGVN *phase, bool can_reshape); duke@435: const Type *bottom_type() const { return Type::FLOAT; } duke@435: virtual uint ideal_reg() const { return Op_RegF; } duke@435: }; duke@435: duke@435: //------------------------------NegDNode--------------------------------------- duke@435: // Negate value a double. Negating 0.0 returns -0.0, but subtracting from duke@435: // zero returns +0.0 (per JVM spec on 'dneg' bytecode). As subtraction duke@435: // cannot be used to replace negation we have to implement negation as ideal duke@435: // node; note that negation and addition can replace subtraction. duke@435: class NegDNode : public NegNode { duke@435: public: duke@435: NegDNode( Node *in1 ) : NegNode(in1) {} duke@435: virtual int Opcode() const; duke@435: virtual Node *Ideal(PhaseGVN *phase, bool can_reshape); duke@435: const Type *bottom_type() const { return Type::DOUBLE; } duke@435: virtual uint ideal_reg() const { return Op_RegD; } duke@435: }; duke@435: duke@435: //------------------------------CosDNode--------------------------------------- duke@435: // Cosinus of a double duke@435: class CosDNode : public Node { duke@435: public: duke@435: CosDNode( Node *in1 ) : Node(0, in1) {} duke@435: virtual int Opcode() const; duke@435: const Type *bottom_type() const { return Type::DOUBLE; } duke@435: virtual uint ideal_reg() const { return Op_RegD; } duke@435: virtual const Type *Value( PhaseTransform *phase ) const; duke@435: }; duke@435: duke@435: //------------------------------CosDNode--------------------------------------- duke@435: // Sinus of a double duke@435: class SinDNode : public Node { duke@435: public: duke@435: SinDNode( Node *in1 ) : Node(0, in1) {} duke@435: virtual int Opcode() const; duke@435: const Type *bottom_type() const { return Type::DOUBLE; } duke@435: virtual uint ideal_reg() const { return Op_RegD; } duke@435: virtual const Type *Value( PhaseTransform *phase ) const; duke@435: }; duke@435: duke@435: duke@435: //------------------------------TanDNode--------------------------------------- duke@435: // tangens of a double duke@435: class TanDNode : public Node { duke@435: public: duke@435: TanDNode(Node *in1 ) : Node(0, in1) {} duke@435: virtual int Opcode() const; duke@435: const Type *bottom_type() const { return Type::DOUBLE; } duke@435: virtual uint ideal_reg() const { return Op_RegD; } duke@435: virtual const Type *Value( PhaseTransform *phase ) const; duke@435: }; duke@435: duke@435: duke@435: //------------------------------AtanDNode-------------------------------------- duke@435: // arcus tangens of a double duke@435: class AtanDNode : public Node { duke@435: public: duke@435: AtanDNode(Node *c, Node *in1, Node *in2 ) : Node(c, in1, in2) {} duke@435: virtual int Opcode() const; duke@435: const Type *bottom_type() const { return Type::DOUBLE; } duke@435: virtual uint ideal_reg() const { return Op_RegD; } duke@435: }; duke@435: duke@435: duke@435: //------------------------------SqrtDNode-------------------------------------- duke@435: // square root a double duke@435: class SqrtDNode : public Node { duke@435: public: duke@435: SqrtDNode(Node *c, Node *in1 ) : Node(c, in1) {} duke@435: virtual int Opcode() const; duke@435: const Type *bottom_type() const { return Type::DOUBLE; } duke@435: virtual uint ideal_reg() const { return Op_RegD; } duke@435: virtual const Type *Value( PhaseTransform *phase ) const; duke@435: }; duke@435: duke@435: //------------------------------ExpDNode--------------------------------------- duke@435: // Exponentiate a double duke@435: class ExpDNode : public Node { duke@435: public: duke@435: ExpDNode( Node *c, Node *in1 ) : Node(c, in1) {} duke@435: virtual int Opcode() const; duke@435: const Type *bottom_type() const { return Type::DOUBLE; } duke@435: virtual uint ideal_reg() const { return Op_RegD; } duke@435: virtual const Type *Value( PhaseTransform *phase ) const; duke@435: }; duke@435: duke@435: //------------------------------LogDNode--------------------------------------- duke@435: // Log_e of a double duke@435: class LogDNode : public Node { duke@435: public: duke@435: LogDNode( Node *in1 ) : Node(0, in1) {} duke@435: virtual int Opcode() const; duke@435: const Type *bottom_type() const { return Type::DOUBLE; } duke@435: virtual uint ideal_reg() const { return Op_RegD; } duke@435: virtual const Type *Value( PhaseTransform *phase ) const; duke@435: }; duke@435: duke@435: //------------------------------Log10DNode--------------------------------------- duke@435: // Log_10 of a double duke@435: class Log10DNode : public Node { duke@435: public: duke@435: Log10DNode( Node *in1 ) : Node(0, in1) {} duke@435: virtual int Opcode() const; duke@435: const Type *bottom_type() const { return Type::DOUBLE; } duke@435: virtual uint ideal_reg() const { return Op_RegD; } duke@435: virtual const Type *Value( PhaseTransform *phase ) const; duke@435: }; duke@435: duke@435: //------------------------------PowDNode--------------------------------------- duke@435: // Raise a double to a double power duke@435: class PowDNode : public Node { duke@435: public: duke@435: PowDNode(Node *c, Node *in1, Node *in2 ) : Node(c, in1, in2) {} duke@435: virtual int Opcode() const; duke@435: const Type *bottom_type() const { return Type::DOUBLE; } duke@435: virtual uint ideal_reg() const { return Op_RegD; } duke@435: virtual const Type *Value( PhaseTransform *phase ) const; duke@435: }; duke@435: duke@435: //-------------------------------ReverseBytesINode-------------------------------- duke@435: // reverse bytes of an integer duke@435: class ReverseBytesINode : public Node { duke@435: public: duke@435: ReverseBytesINode(Node *c, Node *in1) : Node(c, in1) {} duke@435: virtual int Opcode() const; duke@435: const Type *bottom_type() const { return TypeInt::INT; } duke@435: virtual uint ideal_reg() const { return Op_RegI; } duke@435: }; duke@435: duke@435: //-------------------------------ReverseBytesLNode-------------------------------- duke@435: // reverse bytes of a long duke@435: class ReverseBytesLNode : public Node { duke@435: public: duke@435: ReverseBytesLNode(Node *c, Node *in1) : Node(c, in1) {} duke@435: virtual int Opcode() const; duke@435: const Type *bottom_type() const { return TypeLong::LONG; } duke@435: virtual uint ideal_reg() const { return Op_RegL; } duke@435: };