42 // Optimization - Graph Style
43
44 #include "math.h"
45
46 //=============================================================================
47 //------------------------------Identity---------------------------------------
48 // If right input is a constant 0, return the left input.
49 Node* SubNode::Identity(PhaseGVN* phase) {
50 assert(in(1) != this, "Must already have called Value");
51 assert(in(2) != this, "Must already have called Value");
52
53 // Remove double negation
54 const Type *zero = add_id();
55 if( phase->type( in(1) )->higher_equal( zero ) &&
56 in(2)->Opcode() == Opcode() &&
57 phase->type( in(2)->in(1) )->higher_equal( zero ) ) {
58 return in(2)->in(2);
59 }
60
61 // Convert "(X+Y) - Y" into X and "(X+Y) - X" into Y
62 if( in(1)->Opcode() == Op_AddI ) {
63 if( phase->eqv(in(1)->in(2),in(2)) )
64 return in(1)->in(1);
65 if (phase->eqv(in(1)->in(1),in(2)))
66 return in(1)->in(2);
67
68 // Also catch: "(X + Opaque2(Y)) - Y". In this case, 'Y' is a loop-varying
69 // trip counter and X is likely to be loop-invariant (that's how O2 Nodes
70 // are originally used, although the optimizer sometimes jiggers things).
71 // This folding through an O2 removes a loop-exit use of a loop-varying
72 // value and generally lowers register pressure in and around the loop.
73 if( in(1)->in(2)->Opcode() == Op_Opaque2 &&
74 phase->eqv(in(1)->in(2)->in(1),in(2)) )
75 return in(1)->in(1);
76 }
77
78 return ( phase->type( in(2) )->higher_equal( zero ) ) ? in(1) : this;
79 }
80
81 //------------------------------Value------------------------------------------
82 // A subtract node differences it's two inputs.
83 const Type* SubNode::Value_common(PhaseTransform *phase) const {
84 const Node* in1 = in(1);
85 const Node* in2 = in(2);
86 // Either input is TOP ==> the result is TOP
87 const Type* t1 = (in1 == this) ? Type::TOP : phase->type(in1);
88 if( t1 == Type::TOP ) return Type::TOP;
89 const Type* t2 = (in2 == this) ? Type::TOP : phase->type(in2);
90 if( t2 == Type::TOP ) return Type::TOP;
91
92 // Not correct for SubFnode and AddFNode (must check for infinity)
93 // Equal? Subtract is zero
124 const PhiNode *phi;
125 if( ( !inc->in(1)->is_Phi() ||
126 !(phi=inc->in(1)->as_Phi()) ||
127 phi->is_copy() ||
128 !phi->region()->is_CountedLoop() ||
129 inc != phi->region()->as_CountedLoop()->incr() )
130 &&
131 // Do not collapse (x+c0)-iv if "iv" is a loop induction variable,
132 // because "x" maybe invariant.
133 ( !iv->is_loop_iv() )
134 ) {
135 return true;
136 } else {
137 return false;
138 }
139 }
140 //------------------------------Ideal------------------------------------------
141 Node *SubINode::Ideal(PhaseGVN *phase, bool can_reshape){
142 Node *in1 = in(1);
143 Node *in2 = in(2);
144 uint op1 = in1->Opcode();
145 uint op2 = in2->Opcode();
146
147 #ifdef ASSERT
148 // Check for dead loop
149 if( phase->eqv( in1, this ) || phase->eqv( in2, this ) ||
150 ( op1 == Op_AddI || op1 == Op_SubI ) &&
151 ( phase->eqv( in1->in(1), this ) || phase->eqv( in1->in(2), this ) ||
152 phase->eqv( in1->in(1), in1 ) || phase->eqv( in1->in(2), in1 ) ) )
153 assert(false, "dead loop in SubINode::Ideal");
154 #endif
155
156 const Type *t2 = phase->type( in2 );
157 if( t2 == Type::TOP ) return NULL;
158 // Convert "x-c0" into "x+ -c0".
159 if( t2->base() == Type::Int ){ // Might be bottom or top...
160 const TypeInt *i = t2->is_int();
161 if( i->is_con() )
162 return new AddINode(in1, phase->intcon(-i->get_con()));
163 }
164
165 // Convert "(x+c0) - y" into (x-y) + c0"
166 // Do not collapse (x+c0)-y if "+" is a loop increment or
167 // if "y" is a loop induction variable.
168 if( op1 == Op_AddI && ok_to_convert(in1, in2) ) {
169 const Type *tadd = phase->type( in1->in(2) );
170 if( tadd->singleton() && tadd != Type::TOP ) {
171 Node *sub2 = phase->transform( new SubINode( in1->in(1), in2 ));
172 return new AddINode( sub2, in1->in(2) );
173 }
174 }
175
176
177 // Convert "x - (y+c0)" into "(x-y) - c0"
178 // Need the same check as in above optimization but reversed.
179 if (op2 == Op_AddI && ok_to_convert(in2, in1)) {
180 Node* in21 = in2->in(1);
181 Node* in22 = in2->in(2);
182 const TypeInt* tcon = phase->type(in22)->isa_int();
183 if (tcon != NULL && tcon->is_con()) {
184 Node* sub2 = phase->transform( new SubINode(in1, in21) );
185 Node* neg_c0 = phase->intcon(- tcon->get_con());
186 return new AddINode(sub2, neg_c0);
187 }
188 }
189
190 const Type *t1 = phase->type( in1 );
191 if( t1 == Type::TOP ) return NULL;
192
193 #ifdef ASSERT
194 // Check for dead loop
195 if( ( op2 == Op_AddI || op2 == Op_SubI ) &&
196 ( phase->eqv( in2->in(1), this ) || phase->eqv( in2->in(2), this ) ||
197 phase->eqv( in2->in(1), in2 ) || phase->eqv( in2->in(2), in2 ) ) )
198 assert(false, "dead loop in SubINode::Ideal");
199 #endif
200
201 // Convert "x - (x+y)" into "-y"
202 if( op2 == Op_AddI &&
203 phase->eqv( in1, in2->in(1) ) )
204 return new SubINode( phase->intcon(0),in2->in(2));
205 // Convert "(x-y) - x" into "-y"
206 if( op1 == Op_SubI &&
207 phase->eqv( in1->in(1), in2 ) )
208 return new SubINode( phase->intcon(0),in1->in(2));
209 // Convert "x - (y+x)" into "-y"
210 if( op2 == Op_AddI &&
211 phase->eqv( in1, in2->in(2) ) )
212 return new SubINode( phase->intcon(0),in2->in(1));
213
214 // Convert "0 - (x-y)" into "y-x"
215 if( t1 == TypeInt::ZERO && op2 == Op_SubI )
216 return new SubINode( in2->in(2), in2->in(1) );
217
218 // Convert "0 - (x+con)" into "-con-x"
219 jint con;
220 if( t1 == TypeInt::ZERO && op2 == Op_AddI &&
221 (con = in2->in(2)->find_int_con(0)) != 0 )
222 return new SubINode( phase->intcon(-con), in2->in(1) );
223
224 // Convert "(X+A) - (X+B)" into "A - B"
225 if( op1 == Op_AddI && op2 == Op_AddI && in1->in(1) == in2->in(1) )
226 return new SubINode( in1->in(2), in2->in(2) );
227
228 // Convert "(A+X) - (B+X)" into "A - B"
229 if( op1 == Op_AddI && op2 == Op_AddI && in1->in(2) == in2->in(2) )
230 return new SubINode( in1->in(1), in2->in(1) );
231
232 // Convert "(A+X) - (X+B)" into "A - B"
233 if( op1 == Op_AddI && op2 == Op_AddI && in1->in(2) == in2->in(1) )
234 return new SubINode( in1->in(1), in2->in(2) );
235
236 // Convert "(X+A) - (B+X)" into "A - B"
237 if( op1 == Op_AddI && op2 == Op_AddI && in1->in(1) == in2->in(2) )
238 return new SubINode( in1->in(2), in2->in(1) );
239
240 // Convert "A-(B-C)" into (A+C)-B", since add is commutative and generally
241 // nicer to optimize than subtract.
242 if( op2 == Op_SubI && in2->outcnt() == 1) {
243 Node *add1 = phase->transform( new AddINode( in1, in2->in(2) ) );
244 return new SubINode( add1, in2->in(1) );
245 }
246
247 return NULL;
248 }
249
250 //------------------------------sub--------------------------------------------
251 // A subtract node differences it's two inputs.
252 const Type *SubINode::sub( const Type *t1, const Type *t2 ) const {
253 const TypeInt *r0 = t1->is_int(); // Handy access
254 const TypeInt *r1 = t2->is_int();
255 int32_t lo = java_subtract(r0->_lo, r1->_hi);
256 int32_t hi = java_subtract(r0->_hi, r1->_lo);
257
258 // We next check for 32-bit overflow.
259 // If that happens, we just assume all integers are possible.
260 if( (((r0->_lo ^ r1->_hi) >= 0) || // lo ends have same signs OR
261 ((r0->_lo ^ lo) >= 0)) && // lo results have same signs AND
262 (((r0->_hi ^ r1->_lo) >= 0) || // hi ends have same signs OR
263 ((r0->_hi ^ hi) >= 0)) ) // hi results have same signs
264 return TypeInt::make(lo,hi,MAX2(r0->_widen,r1->_widen));
265 else // Overflow; assume all integers
266 return TypeInt::INT;
267 }
268
269 //=============================================================================
270 //------------------------------Ideal------------------------------------------
271 Node *SubLNode::Ideal(PhaseGVN *phase, bool can_reshape) {
272 Node *in1 = in(1);
273 Node *in2 = in(2);
274 uint op1 = in1->Opcode();
275 uint op2 = in2->Opcode();
276
277 #ifdef ASSERT
278 // Check for dead loop
279 if( phase->eqv( in1, this ) || phase->eqv( in2, this ) ||
280 ( op1 == Op_AddL || op1 == Op_SubL ) &&
281 ( phase->eqv( in1->in(1), this ) || phase->eqv( in1->in(2), this ) ||
282 phase->eqv( in1->in(1), in1 ) || phase->eqv( in1->in(2), in1 ) ) )
283 assert(false, "dead loop in SubLNode::Ideal");
284 #endif
285
286 if( phase->type( in2 ) == Type::TOP ) return NULL;
287 const TypeLong *i = phase->type( in2 )->isa_long();
288 // Convert "x-c0" into "x+ -c0".
289 if( i && // Might be bottom or top...
290 i->is_con() )
291 return new AddLNode(in1, phase->longcon(-i->get_con()));
292
293 // Convert "(x+c0) - y" into (x-y) + c0"
294 // Do not collapse (x+c0)-y if "+" is a loop increment or
295 // if "y" is a loop induction variable.
296 if( op1 == Op_AddL && ok_to_convert(in1, in2) ) {
297 Node *in11 = in1->in(1);
298 const Type *tadd = phase->type( in1->in(2) );
299 if( tadd->singleton() && tadd != Type::TOP ) {
300 Node *sub2 = phase->transform( new SubLNode( in11, in2 ));
301 return new AddLNode( sub2, in1->in(2) );
302 }
303 }
304
305 // Convert "x - (y+c0)" into "(x-y) - c0"
306 // Need the same check as in above optimization but reversed.
307 if (op2 == Op_AddL && ok_to_convert(in2, in1)) {
308 Node* in21 = in2->in(1);
309 Node* in22 = in2->in(2);
310 const TypeLong* tcon = phase->type(in22)->isa_long();
311 if (tcon != NULL && tcon->is_con()) {
312 Node* sub2 = phase->transform( new SubLNode(in1, in21) );
313 Node* neg_c0 = phase->longcon(- tcon->get_con());
314 return new AddLNode(sub2, neg_c0);
315 }
316 }
317
318 const Type *t1 = phase->type( in1 );
319 if( t1 == Type::TOP ) return NULL;
320
321 #ifdef ASSERT
322 // Check for dead loop
323 if( ( op2 == Op_AddL || op2 == Op_SubL ) &&
324 ( phase->eqv( in2->in(1), this ) || phase->eqv( in2->in(2), this ) ||
325 phase->eqv( in2->in(1), in2 ) || phase->eqv( in2->in(2), in2 ) ) )
326 assert(false, "dead loop in SubLNode::Ideal");
327 #endif
328
329 // Convert "x - (x+y)" into "-y"
330 if( op2 == Op_AddL &&
331 phase->eqv( in1, in2->in(1) ) )
332 return new SubLNode( phase->makecon(TypeLong::ZERO), in2->in(2));
333 // Convert "x - (y+x)" into "-y"
334 if( op2 == Op_AddL &&
335 phase->eqv( in1, in2->in(2) ) )
336 return new SubLNode( phase->makecon(TypeLong::ZERO),in2->in(1));
337
338 // Convert "0 - (x-y)" into "y-x"
339 if( phase->type( in1 ) == TypeLong::ZERO && op2 == Op_SubL )
340 return new SubLNode( in2->in(2), in2->in(1) );
341
342 // Convert "(X+A) - (X+B)" into "A - B"
343 if( op1 == Op_AddL && op2 == Op_AddL && in1->in(1) == in2->in(1) )
344 return new SubLNode( in1->in(2), in2->in(2) );
345
346 // Convert "(A+X) - (B+X)" into "A - B"
347 if( op1 == Op_AddL && op2 == Op_AddL && in1->in(2) == in2->in(2) )
348 return new SubLNode( in1->in(1), in2->in(1) );
349
350 // Convert "A-(B-C)" into (A+C)-B"
351 if( op2 == Op_SubL && in2->outcnt() == 1) {
352 Node *add1 = phase->transform( new AddLNode( in1, in2->in(2) ) );
353 return new SubLNode( add1, in2->in(1) );
354 }
355
356 return NULL;
357 }
358
359 //------------------------------sub--------------------------------------------
360 // A subtract node differences it's two inputs.
361 const Type *SubLNode::sub( const Type *t1, const Type *t2 ) const {
362 const TypeLong *r0 = t1->is_long(); // Handy access
363 const TypeLong *r1 = t2->is_long();
364 jlong lo = java_subtract(r0->_lo, r1->_hi);
365 jlong hi = java_subtract(r0->_hi, r1->_lo);
366
367 // We next check for 32-bit overflow.
368 // If that happens, we just assume all integers are possible.
369 if( (((r0->_lo ^ r1->_hi) >= 0) || // lo ends have same signs OR
370 ((r0->_lo ^ lo) >= 0)) && // lo results have same signs AND
371 (((r0->_hi ^ r1->_lo) >= 0) || // hi ends have same signs OR
611 // (This is a gross hack, since the sub method never
612 // looks at the structure of the node in any other case.)
613 if ((jint)lo0 >= 0 && (jint)lo1 >= 0 && is_index_range_check())
614 return TypeInt::CC_LT;
615 return TypeInt::CC; // else use worst case results
616 }
617
618 const Type* CmpUNode::Value(PhaseGVN* phase) const {
619 const Type* t = SubNode::Value_common(phase);
620 if (t != NULL) {
621 return t;
622 }
623 const Node* in1 = in(1);
624 const Node* in2 = in(2);
625 const Type* t1 = phase->type(in1);
626 const Type* t2 = phase->type(in2);
627 assert(t1->isa_int(), "CmpU has only Int type inputs");
628 if (t2 == TypeInt::INT) { // Compare to bottom?
629 return bottom_type();
630 }
631 uint in1_op = in1->Opcode();
632 if (in1_op == Op_AddI || in1_op == Op_SubI) {
633 // The problem rise when result of AddI(SubI) may overflow
634 // signed integer value. Let say the input type is
635 // [256, maxint] then +128 will create 2 ranges due to
636 // overflow: [minint, minint+127] and [384, maxint].
637 // But C2 type system keep only 1 type range and as result
638 // it use general [minint, maxint] for this case which we
639 // can't optimize.
640 //
641 // Make 2 separate type ranges based on types of AddI(SubI) inputs
642 // and compare results of their compare. If results are the same
643 // CmpU node can be optimized.
644 const Node* in11 = in1->in(1);
645 const Node* in12 = in1->in(2);
646 const Type* t11 = (in11 == in1) ? Type::TOP : phase->type(in11);
647 const Type* t12 = (in12 == in1) ? Type::TOP : phase->type(in12);
648 // Skip cases when input types are top or bottom.
649 if ((t11 != Type::TOP) && (t11 != TypeInt::INT) &&
650 (t12 != Type::TOP) && (t12 != TypeInt::INT)) {
651 const TypeInt *r0 = t11->is_int();
652 const TypeInt *r1 = t12->is_int();
653 jlong lo_r0 = r0->_lo;
654 jlong hi_r0 = r0->_hi;
655 jlong lo_r1 = r1->_lo;
656 jlong hi_r1 = r1->_hi;
657 if (in1_op == Op_SubI) {
658 jlong tmp = hi_r1;
659 hi_r1 = -lo_r1;
660 lo_r1 = -tmp;
661 // Note, for substructing [minint,x] type range
662 // long arithmetic provides correct overflow answer.
663 // The confusion come from the fact that in 32-bit
664 // -minint == minint but in 64-bit -minint == maxint+1.
665 }
666 jlong lo_long = lo_r0 + lo_r1;
667 jlong hi_long = hi_r0 + hi_r1;
668 int lo_tr1 = min_jint;
669 int hi_tr1 = (int)hi_long;
670 int lo_tr2 = (int)lo_long;
671 int hi_tr2 = max_jint;
672 bool underflow = lo_long != (jlong)lo_tr2;
673 bool overflow = hi_long != (jlong)hi_tr1;
674 // Use sub(t1, t2) when there is no overflow (one type range)
675 // or when both overflow and underflow (too complex).
676 if ((underflow != overflow) && (hi_tr1 < lo_tr2)) {
677 // Overflow only on one boundary, compare 2 separate type ranges.
678 int w = MAX2(r0->_widen, r1->_widen); // _widen does not matter here
679 const TypeInt* tr1 = TypeInt::make(lo_tr1, hi_tr1, w);
680 const TypeInt* tr2 = TypeInt::make(lo_tr2, hi_tr2, w);
681 const Type* cmp1 = sub(tr1, t2);
682 const Type* cmp2 = sub(tr2, t2);
683 if (cmp1 == cmp2) {
684 return cmp1; // Hit!
685 }
686 }
687 }
688 }
689
690 return sub(t1, t2); // Local flavor of type subtraction
691 }
692
693 bool CmpUNode::is_index_range_check() const {
694 // Check for the "(X ModI Y) CmpU Y" shape
695 return (in(1)->Opcode() == Op_ModI &&
696 in(1)->in(2)->eqv_uncast(in(2)));
697 }
698
699 //------------------------------Idealize---------------------------------------
700 Node *CmpINode::Ideal( PhaseGVN *phase, bool can_reshape ) {
701 if (phase->type(in(2))->higher_equal(TypeInt::ZERO)) {
702 switch (in(1)->Opcode()) {
703 case Op_CmpL3: // Collapse a CmpL3/CmpI into a CmpL
704 return new CmpLNode(in(1)->in(1),in(1)->in(2));
705 case Op_CmpF3: // Collapse a CmpF3/CmpI into a CmpF
706 return new CmpFNode(in(1)->in(1),in(1)->in(2));
707 case Op_CmpD3: // Collapse a CmpD3/CmpI into a CmpD
708 return new CmpDNode(in(1)->in(1),in(1)->in(2));
709 //case Op_SubI:
710 // If (x - y) cannot overflow, then ((x - y) <?> 0)
711 // can be turned into (x <?> y).
712 // This is handled (with more general cases) by Ideal_sub_algebra.
713 }
714 }
715 return NULL; // No change
716 }
717
718
719 //=============================================================================
720 // Simplify a CmpL (compare 2 longs ) node, based on local information.
721 // If both inputs are constants, compare them.
722 const Type *CmpLNode::sub( const Type *t1, const Type *t2 ) const {
723 const TypeLong *r0 = t1->is_long(); // Handy access
724 const TypeLong *r1 = t2->is_long();
725
726 if( r0->_hi < r1->_lo ) // Range is always low?
727 return TypeInt::CC_LT;
809
810 // Known constants can be compared exactly
811 // Null can be distinguished from any NotNull pointers
812 // Unknown inputs makes an unknown result
813 if( r0->singleton() ) {
814 intptr_t bits0 = r0->get_con();
815 if( r1->singleton() )
816 return bits0 == r1->get_con() ? TypeInt::CC_EQ : TypeInt::CC_GT;
817 return ( r1->_ptr == TypePtr::NotNull && bits0==0 ) ? TypeInt::CC_GT : TypeInt::CC;
818 } else if( r1->singleton() ) {
819 intptr_t bits1 = r1->get_con();
820 return ( r0->_ptr == TypePtr::NotNull && bits1==0 ) ? TypeInt::CC_GT : TypeInt::CC;
821 } else
822 return TypeInt::CC;
823 }
824
825 static inline Node* isa_java_mirror_load(PhaseGVN* phase, Node* n) {
826 // Return the klass node for
827 // LoadP(AddP(foo:Klass, #java_mirror))
828 // or NULL if not matching.
829 if (n->Opcode() != Op_LoadP) return NULL;
830
831 const TypeInstPtr* tp = phase->type(n)->isa_instptr();
832 if (!tp || tp->klass() != phase->C->env()->Class_klass()) return NULL;
833
834 Node* adr = n->in(MemNode::Address);
835 intptr_t off = 0;
836 Node* k = AddPNode::Ideal_base_and_offset(adr, phase, off);
837 if (k == NULL) return NULL;
838 const TypeKlassPtr* tkp = phase->type(k)->isa_klassptr();
839 if (!tkp || off != in_bytes(Klass::java_mirror_offset())) return NULL;
840
841 // We've found the klass node of a Java mirror load.
842 return k;
843 }
844
845 static inline Node* isa_const_java_mirror(PhaseGVN* phase, Node* n) {
846 // for ConP(Foo.class) return ConP(Foo.klass)
847 // otherwise return NULL
848 if (!n->is_Con()) return NULL;
849
894 if (k1 && (k2 || conk2)) {
895 Node* lhs = k1;
896 Node* rhs = (k2 != NULL) ? k2 : conk2;
897 this->set_req(1, lhs);
898 this->set_req(2, rhs);
899 return this;
900 }
901 }
902
903 // Constant pointer on right?
904 const TypeKlassPtr* t2 = phase->type(in(2))->isa_klassptr();
905 if (t2 == NULL || !t2->klass_is_exact())
906 return NULL;
907 // Get the constant klass we are comparing to.
908 ciKlass* superklass = t2->klass();
909
910 // Now check for LoadKlass on left.
911 Node* ldk1 = in(1);
912 if (ldk1->is_DecodeNKlass()) {
913 ldk1 = ldk1->in(1);
914 if (ldk1->Opcode() != Op_LoadNKlass )
915 return NULL;
916 } else if (ldk1->Opcode() != Op_LoadKlass )
917 return NULL;
918 // Take apart the address of the LoadKlass:
919 Node* adr1 = ldk1->in(MemNode::Address);
920 intptr_t con2 = 0;
921 Node* ldk2 = AddPNode::Ideal_base_and_offset(adr1, phase, con2);
922 if (ldk2 == NULL)
923 return NULL;
924 if (con2 == oopDesc::klass_offset_in_bytes()) {
925 // We are inspecting an object's concrete class.
926 // Short-circuit the check if the query is abstract.
927 if (superklass->is_interface() ||
928 superklass->is_abstract()) {
929 // Make it come out always false:
930 this->set_req(2, phase->makecon(TypePtr::NULL_PTR));
931 return this;
932 }
933 }
934
935 // Check for a LoadKlass from primary supertype array.
936 // Any nested loadklass from loadklass+con must be from the p.s. array.
937 if (ldk2->is_DecodeNKlass()) {
938 // Keep ldk2 as DecodeN since it could be used in CmpP below.
939 if (ldk2->in(1)->Opcode() != Op_LoadNKlass )
940 return NULL;
941 } else if (ldk2->Opcode() != Op_LoadKlass)
942 return NULL;
943
944 // Verify that we understand the situation
945 if (con2 != (intptr_t) superklass->super_check_offset())
946 return NULL; // Might be element-klass loading from array klass
947
948 // If 'superklass' has no subklasses and is not an interface, then we are
949 // assured that the only input which will pass the type check is
950 // 'superklass' itself.
951 //
952 // We could be more liberal here, and allow the optimization on interfaces
953 // which have a single implementor. This would require us to increase the
954 // expressiveness of the add_dependency() mechanism.
955 // %%% Do this after we fix TypeOopPtr: Deps are expressive enough now.
956
957 // Object arrays must have their base element have no subtypes
958 while (superklass->is_obj_array_klass()) {
959 ciType* elem = superklass->as_obj_array_klass()->element_type();
960 superklass = elem->as_klass();
961 }
1106 if( td1->is_nan() || td2->is_nan() )
1107 return TypeInt::CC_LT;
1108
1109 if( td1->_d < td2->_d ) return TypeInt::CC_LT;
1110 if( td1->_d > td2->_d ) return TypeInt::CC_GT;
1111 assert( td1->_d == td2->_d, "do not understand FP behavior" );
1112 return TypeInt::CC_EQ;
1113 }
1114
1115 //------------------------------Ideal------------------------------------------
1116 Node *CmpDNode::Ideal(PhaseGVN *phase, bool can_reshape){
1117 // Check if we can change this to a CmpF and remove a ConvD2F operation.
1118 // Change (CMPD (F2D (float)) (ConD value))
1119 // To (CMPF (float) (ConF value))
1120 // Valid when 'value' does not lose precision as a float.
1121 // Benefits: eliminates conversion, does not require 24-bit mode
1122
1123 // NaNs prevent commuting operands. This transform works regardless of the
1124 // order of ConD and ConvF2D inputs by preserving the original order.
1125 int idx_f2d = 1; // ConvF2D on left side?
1126 if( in(idx_f2d)->Opcode() != Op_ConvF2D )
1127 idx_f2d = 2; // No, swap to check for reversed args
1128 int idx_con = 3-idx_f2d; // Check for the constant on other input
1129
1130 if( ConvertCmpD2CmpF &&
1131 in(idx_f2d)->Opcode() == Op_ConvF2D &&
1132 in(idx_con)->Opcode() == Op_ConD ) {
1133 const TypeD *t2 = in(idx_con)->bottom_type()->is_double_constant();
1134 double t2_value_as_double = t2->_d;
1135 float t2_value_as_float = (float)t2_value_as_double;
1136 if( t2_value_as_double == (double)t2_value_as_float ) {
1137 // Test value can be represented as a float
1138 // Eliminate the conversion to double and create new comparison
1139 Node *new_in1 = in(idx_f2d)->in(1);
1140 Node *new_in2 = phase->makecon( TypeF::make(t2_value_as_float) );
1141 if( idx_f2d != 1 ) { // Must flip args to match original order
1142 Node *tmp = new_in1;
1143 new_in1 = new_in2;
1144 new_in2 = tmp;
1145 }
1146 CmpFNode *new_cmp = (Opcode() == Op_CmpD3)
1147 ? new CmpF3Node( new_in1, new_in2 )
1148 : new CmpFNode ( new_in1, new_in2 ) ;
1149 return new_cmp; // Changed to CmpFNode
1150 }
1151 // Testing value required the precision of a double
1152 }
1153 return NULL; // No change
1154 }
1155
1156
1157 //=============================================================================
1158 //------------------------------cc2logical-------------------------------------
1159 // Convert a condition code type to a logical type
1160 const Type *BoolTest::cc2logical( const Type *CC ) const {
1161 if( CC == Type::TOP ) return Type::TOP;
1162 if( CC->base() != Type::Int ) return TypeInt::BOOL; // Bottom or worse
1163 const TypeInt *ti = CC->is_int();
1164 if( ti->is_con() ) { // Only 1 kind of condition codes set?
1165 // Match low order 2 bits
1166 int tmp = ((ti->get_con()&3) == (_test&3)) ? 1 : 0;
1220 return phase->transform(bol);
1221 }
1222
1223 //--------------------------------as_int_value---------------------------------
1224 Node* BoolNode::as_int_value(PhaseGVN* phase) {
1225 // Inverse to make_predicate. The CMove probably boils down to a Conv2B.
1226 Node* cmov = CMoveNode::make(NULL, this,
1227 phase->intcon(0), phase->intcon(1),
1228 TypeInt::BOOL);
1229 return phase->transform(cmov);
1230 }
1231
1232 //----------------------------------negate-------------------------------------
1233 BoolNode* BoolNode::negate(PhaseGVN* phase) {
1234 return new BoolNode(in(1), _test.negate());
1235 }
1236
1237 // Change "bool eq/ne (cmp (add/sub A B) C)" into false/true if add/sub
1238 // overflows and we can prove that C is not in the two resulting ranges.
1239 // This optimization is similar to the one performed by CmpUNode::Value().
1240 Node* BoolNode::fold_cmpI(PhaseGVN* phase, SubNode* cmp, Node* cmp1, int cmp_op,
1241 int cmp1_op, const TypeInt* cmp2_type) {
1242 // Only optimize eq/ne integer comparison of add/sub
1243 if((_test._test == BoolTest::eq || _test._test == BoolTest::ne) &&
1244 (cmp_op == Op_CmpI) && (cmp1_op == Op_AddI || cmp1_op == Op_SubI)) {
1245 // Skip cases were inputs of add/sub are not integers or of bottom type
1246 const TypeInt* r0 = phase->type(cmp1->in(1))->isa_int();
1247 const TypeInt* r1 = phase->type(cmp1->in(2))->isa_int();
1248 if ((r0 != NULL) && (r0 != TypeInt::INT) &&
1249 (r1 != NULL) && (r1 != TypeInt::INT) &&
1250 (cmp2_type != TypeInt::INT)) {
1251 // Compute exact (long) type range of add/sub result
1252 jlong lo_long = r0->_lo;
1253 jlong hi_long = r0->_hi;
1254 if (cmp1_op == Op_AddI) {
1255 lo_long += r1->_lo;
1256 hi_long += r1->_hi;
1257 } else {
1258 lo_long -= r1->_hi;
1259 hi_long -= r1->_lo;
1260 }
1261 // Check for over-/underflow by casting to integer
1262 int lo_int = (int)lo_long;
1263 int hi_int = (int)hi_long;
1264 bool underflow = lo_long != (jlong)lo_int;
1265 bool overflow = hi_long != (jlong)hi_int;
1266 if ((underflow != overflow) && (hi_int < lo_int)) {
1267 // Overflow on one boundary, compute resulting type ranges:
1268 // tr1 [MIN_INT, hi_int] and tr2 [lo_int, MAX_INT]
1269 int w = MAX2(r0->_widen, r1->_widen); // _widen does not matter here
1270 const TypeInt* tr1 = TypeInt::make(min_jint, hi_int, w);
1271 const TypeInt* tr2 = TypeInt::make(lo_int, max_jint, w);
1272 // Compare second input of cmp to both type ranges
1273 const Type* sub_tr1 = cmp->sub(tr1, cmp2_type);
1274 const Type* sub_tr2 = cmp->sub(tr2, cmp2_type);
1275 if (sub_tr1 == TypeInt::CC_LT && sub_tr2 == TypeInt::CC_GT) {
1276 // The result of the add/sub will never equal cmp2. Replace BoolNode
1277 // by false (0) if it tests for equality and by true (1) otherwise.
1278 return ConINode::make((_test._test == BoolTest::eq) ? 0 : 1);
1279 }
1280 }
1281 }
1282 }
1283 return NULL;
1284 }
1285
1286 //------------------------------Ideal------------------------------------------
1287 Node *BoolNode::Ideal(PhaseGVN *phase, bool can_reshape) {
1288 // Change "bool tst (cmp con x)" into "bool ~tst (cmp x con)".
1289 // This moves the constant to the right. Helps value-numbering.
1290 Node *cmp = in(1);
1291 if( !cmp->is_Sub() ) return NULL;
1292 int cop = cmp->Opcode();
1293 if( cop == Op_FastLock || cop == Op_FastUnlock) return NULL;
1294 Node *cmp1 = cmp->in(1);
1295 Node *cmp2 = cmp->in(2);
1296 if( !cmp1 ) return NULL;
1297
1298 if (_test._test == BoolTest::overflow || _test._test == BoolTest::no_overflow) {
1299 return NULL;
1300 }
1301
1302 // Constant on left?
1303 Node *con = cmp1;
1304 uint op2 = cmp2->Opcode();
1305 // Move constants to the right of compare's to canonicalize.
1306 // Do not muck with Opaque1 nodes, as this indicates a loop
1307 // guard that cannot change shape.
1308 if( con->is_Con() && !cmp2->is_Con() && op2 != Op_Opaque1 &&
1309 // Because of NaN's, CmpD and CmpF are not commutative
1310 cop != Op_CmpD && cop != Op_CmpF &&
1311 // Protect against swapping inputs to a compare when it is used by a
1312 // counted loop exit, which requires maintaining the loop-limit as in(2)
1313 !is_counted_loop_exit_test() ) {
1314 // Ok, commute the constant to the right of the cmp node.
1315 // Clone the Node, getting a new Node of the same class
1316 cmp = cmp->clone();
1317 // Swap inputs to the clone
1318 cmp->swap_edges(1, 2);
1319 cmp = phase->transform( cmp );
1320 return new BoolNode( cmp, _test.commute() );
1321 }
1322
1323 // Change "bool eq/ne (cmp (xor X 1) 0)" into "bool ne/eq (cmp X 0)".
1324 // The XOR-1 is an idiom used to flip the sense of a bool. We flip the
1325 // test instead.
1326 int cmp1_op = cmp1->Opcode();
1327 const TypeInt* cmp2_type = phase->type(cmp2)->isa_int();
1328 if (cmp2_type == NULL) return NULL;
1329 Node* j_xor = cmp1;
1330 if( cmp2_type == TypeInt::ZERO &&
1331 cmp1_op == Op_XorI &&
1332 j_xor->in(1) != j_xor && // An xor of itself is dead
1333 phase->type( j_xor->in(1) ) == TypeInt::BOOL &&
1334 phase->type( j_xor->in(2) ) == TypeInt::ONE &&
1335 (_test._test == BoolTest::eq ||
1336 _test._test == BoolTest::ne) ) {
1337 Node *ncmp = phase->transform(new CmpINode(j_xor->in(1),cmp2));
1338 return new BoolNode( ncmp, _test.negate() );
1339 }
1340
1341 // Change ((x & m) u<= m) or ((m & x) u<= m) to always true
1342 // Same with ((x & m) u< m+1) and ((m & x) u< m+1)
1343 if (cop == Op_CmpU &&
1344 cmp1->Opcode() == Op_AndI) {
1345 Node* bound = NULL;
1346 if (_test._test == BoolTest::le) {
1347 bound = cmp2;
1348 } else if (_test._test == BoolTest::lt &&
1349 cmp2->Opcode() == Op_AddI &&
1350 cmp2->in(2)->find_int_con(0) == 1) {
1351 bound = cmp2->in(1);
1352 }
1353 if (cmp1->in(2) == bound || cmp1->in(1) == bound) {
1354 return ConINode::make(1);
1355 }
1356 }
1357
1358 // Change ((x & (m - 1)) u< m) into (m > 0)
1359 // This is the off-by-one variant of the above
1360 if (cop == Op_CmpU &&
1361 _test._test == BoolTest::lt &&
1362 cmp1->Opcode() == Op_AndI) {
1363 Node* l = cmp1->in(1);
1364 Node* r = cmp1->in(2);
1365 for (int repeat = 0; repeat < 2; repeat++) {
1366 bool match = r->Opcode() == Op_AddI && r->in(2)->find_int_con(0) == -1 &&
1367 r->in(1) == cmp2;
1368 if (match) {
1369 // arraylength known to be non-negative, so a (arraylength != 0) is sufficient,
1370 // but to be compatible with the array range check pattern, use (arraylength u> 0)
1371 Node* ncmp = cmp2->Opcode() == Op_LoadRange
1372 ? phase->transform(new CmpUNode(cmp2, phase->intcon(0)))
1373 : phase->transform(new CmpINode(cmp2, phase->intcon(0)));
1374 return new BoolNode(ncmp, BoolTest::gt);
1375 } else {
1376 // commute and try again
1377 l = cmp1->in(2);
1378 r = cmp1->in(1);
1379 }
1380 }
1381 }
1382
1383 // Change (arraylength <= 0) or (arraylength == 0)
1384 // into (arraylength u<= 0)
1385 // Also change (arraylength != 0) into (arraylength u> 0)
1386 // The latter version matches the code pattern generated for
1387 // array range checks, which will more likely be optimized later.
1388 if (cop == Op_CmpI &&
1389 cmp1->Opcode() == Op_LoadRange &&
1390 cmp2->find_int_con(-1) == 0) {
1391 if (_test._test == BoolTest::le || _test._test == BoolTest::eq) {
1392 Node* ncmp = phase->transform(new CmpUNode(cmp1, cmp2));
1393 return new BoolNode(ncmp, BoolTest::le);
1394 } else if (_test._test == BoolTest::ne) {
1395 Node* ncmp = phase->transform(new CmpUNode(cmp1, cmp2));
1396 return new BoolNode(ncmp, BoolTest::gt);
1397 }
1398 }
1399
1400 // Change "bool eq/ne (cmp (Conv2B X) 0)" into "bool eq/ne (cmp X 0)".
1401 // This is a standard idiom for branching on a boolean value.
1402 Node *c2b = cmp1;
1403 if( cmp2_type == TypeInt::ZERO &&
1404 cmp1_op == Op_Conv2B &&
1405 (_test._test == BoolTest::eq ||
1406 _test._test == BoolTest::ne) ) {
1407 Node *ncmp = phase->transform(phase->type(c2b->in(1))->isa_int()
1408 ? (Node*)new CmpINode(c2b->in(1),cmp2)
1409 : (Node*)new CmpPNode(c2b->in(1),phase->makecon(TypePtr::NULL_PTR))
1410 );
1411 return new BoolNode( ncmp, _test._test );
1412 }
1413
1414 // Comparing a SubI against a zero is equal to comparing the SubI
1415 // arguments directly. This only works for eq and ne comparisons
1416 // due to possible integer overflow.
1417 if ((_test._test == BoolTest::eq || _test._test == BoolTest::ne) &&
1418 (cop == Op_CmpI) &&
1419 (cmp1->Opcode() == Op_SubI) &&
1420 ( cmp2_type == TypeInt::ZERO ) ) {
1421 Node *ncmp = phase->transform( new CmpINode(cmp1->in(1),cmp1->in(2)));
1422 return new BoolNode( ncmp, _test._test );
1423 }
1424
1425 // Change (-A vs 0) into (A vs 0) by commuting the test. Disallow in the
1426 // most general case because negating 0x80000000 does nothing. Needed for
1427 // the CmpF3/SubI/CmpI idiom.
1428 if( cop == Op_CmpI &&
1429 cmp1->Opcode() == Op_SubI &&
1430 cmp2_type == TypeInt::ZERO &&
1431 phase->type( cmp1->in(1) ) == TypeInt::ZERO &&
1432 phase->type( cmp1->in(2) )->higher_equal(TypeInt::SYMINT) ) {
1433 Node *ncmp = phase->transform( new CmpINode(cmp1->in(2),cmp2));
1434 return new BoolNode( ncmp, _test.commute() );
1435 }
1436
1437 // Try to optimize signed integer comparison
1438 return fold_cmpI(phase, cmp->as_Sub(), cmp1, cop, cmp1_op, cmp2_type);
1439
1440 // The transformation below is not valid for either signed or unsigned
1441 // comparisons due to wraparound concerns at MAX_VALUE and MIN_VALUE.
1442 // This transformation can be resurrected when we are able to
1443 // make inferences about the range of values being subtracted from
1444 // (or added to) relative to the wraparound point.
1445 //
1446 // // Remove +/-1's if possible.
1447 // // "X <= Y-1" becomes "X < Y"
1448 // // "X+1 <= Y" becomes "X < Y"
1449 // // "X < Y+1" becomes "X <= Y"
|
42 // Optimization - Graph Style
43
44 #include "math.h"
45
46 //=============================================================================
47 //------------------------------Identity---------------------------------------
48 // If right input is a constant 0, return the left input.
49 Node* SubNode::Identity(PhaseGVN* phase) {
50 assert(in(1) != this, "Must already have called Value");
51 assert(in(2) != this, "Must already have called Value");
52
53 // Remove double negation
54 const Type *zero = add_id();
55 if( phase->type( in(1) )->higher_equal( zero ) &&
56 in(2)->Opcode() == Opcode() &&
57 phase->type( in(2)->in(1) )->higher_equal( zero ) ) {
58 return in(2)->in(2);
59 }
60
61 // Convert "(X+Y) - Y" into X and "(X+Y) - X" into Y
62 if( in(1)->Opcode() == Opcodes::Op_AddI ) {
63 if( phase->eqv(in(1)->in(2),in(2)) )
64 return in(1)->in(1);
65 if (phase->eqv(in(1)->in(1),in(2)))
66 return in(1)->in(2);
67
68 // Also catch: "(X + Opaque2(Y)) - Y". In this case, 'Y' is a loop-varying
69 // trip counter and X is likely to be loop-invariant (that's how O2 Nodes
70 // are originally used, although the optimizer sometimes jiggers things).
71 // This folding through an O2 removes a loop-exit use of a loop-varying
72 // value and generally lowers register pressure in and around the loop.
73 if( in(1)->in(2)->Opcode() == Opcodes::Op_Opaque2 &&
74 phase->eqv(in(1)->in(2)->in(1),in(2)) )
75 return in(1)->in(1);
76 }
77
78 return ( phase->type( in(2) )->higher_equal( zero ) ) ? in(1) : this;
79 }
80
81 //------------------------------Value------------------------------------------
82 // A subtract node differences it's two inputs.
83 const Type* SubNode::Value_common(PhaseTransform *phase) const {
84 const Node* in1 = in(1);
85 const Node* in2 = in(2);
86 // Either input is TOP ==> the result is TOP
87 const Type* t1 = (in1 == this) ? Type::TOP : phase->type(in1);
88 if( t1 == Type::TOP ) return Type::TOP;
89 const Type* t2 = (in2 == this) ? Type::TOP : phase->type(in2);
90 if( t2 == Type::TOP ) return Type::TOP;
91
92 // Not correct for SubFnode and AddFNode (must check for infinity)
93 // Equal? Subtract is zero
124 const PhiNode *phi;
125 if( ( !inc->in(1)->is_Phi() ||
126 !(phi=inc->in(1)->as_Phi()) ||
127 phi->is_copy() ||
128 !phi->region()->is_CountedLoop() ||
129 inc != phi->region()->as_CountedLoop()->incr() )
130 &&
131 // Do not collapse (x+c0)-iv if "iv" is a loop induction variable,
132 // because "x" maybe invariant.
133 ( !iv->is_loop_iv() )
134 ) {
135 return true;
136 } else {
137 return false;
138 }
139 }
140 //------------------------------Ideal------------------------------------------
141 Node *SubINode::Ideal(PhaseGVN *phase, bool can_reshape){
142 Node *in1 = in(1);
143 Node *in2 = in(2);
144 Opcodes op1 = in1->Opcode();
145 Opcodes op2 = in2->Opcode();
146
147 #ifdef ASSERT
148 // Check for dead loop
149 if( phase->eqv( in1, this ) || phase->eqv( in2, this ) ||
150 ( op1 == Opcodes::Op_AddI || op1 == Opcodes::Op_SubI ) &&
151 ( phase->eqv( in1->in(1), this ) || phase->eqv( in1->in(2), this ) ||
152 phase->eqv( in1->in(1), in1 ) || phase->eqv( in1->in(2), in1 ) ) )
153 assert(false, "dead loop in SubINode::Ideal");
154 #endif
155
156 const Type *t2 = phase->type( in2 );
157 if( t2 == Type::TOP ) return NULL;
158 // Convert "x-c0" into "x+ -c0".
159 if( t2->base() == Type::Int ){ // Might be bottom or top...
160 const TypeInt *i = t2->is_int();
161 if( i->is_con() )
162 return new AddINode(in1, phase->intcon(-i->get_con()));
163 }
164
165 // Convert "(x+c0) - y" into (x-y) + c0"
166 // Do not collapse (x+c0)-y if "+" is a loop increment or
167 // if "y" is a loop induction variable.
168 if( op1 == Opcodes::Op_AddI && ok_to_convert(in1, in2) ) {
169 const Type *tadd = phase->type( in1->in(2) );
170 if( tadd->singleton() && tadd != Type::TOP ) {
171 Node *sub2 = phase->transform( new SubINode( in1->in(1), in2 ));
172 return new AddINode( sub2, in1->in(2) );
173 }
174 }
175
176
177 // Convert "x - (y+c0)" into "(x-y) - c0"
178 // Need the same check as in above optimization but reversed.
179 if (op2 == Opcodes::Op_AddI && ok_to_convert(in2, in1)) {
180 Node* in21 = in2->in(1);
181 Node* in22 = in2->in(2);
182 const TypeInt* tcon = phase->type(in22)->isa_int();
183 if (tcon != NULL && tcon->is_con()) {
184 Node* sub2 = phase->transform( new SubINode(in1, in21) );
185 Node* neg_c0 = phase->intcon(- tcon->get_con());
186 return new AddINode(sub2, neg_c0);
187 }
188 }
189
190 const Type *t1 = phase->type( in1 );
191 if( t1 == Type::TOP ) return NULL;
192
193 #ifdef ASSERT
194 // Check for dead loop
195 if( ( op2 == Opcodes::Op_AddI || op2 == Opcodes::Op_SubI ) &&
196 ( phase->eqv( in2->in(1), this ) || phase->eqv( in2->in(2), this ) ||
197 phase->eqv( in2->in(1), in2 ) || phase->eqv( in2->in(2), in2 ) ) )
198 assert(false, "dead loop in SubINode::Ideal");
199 #endif
200
201 // Convert "x - (x+y)" into "-y"
202 if( op2 == Opcodes::Op_AddI &&
203 phase->eqv( in1, in2->in(1) ) )
204 return new SubINode( phase->intcon(0),in2->in(2));
205 // Convert "(x-y) - x" into "-y"
206 if( op1 == Opcodes::Op_SubI &&
207 phase->eqv( in1->in(1), in2 ) )
208 return new SubINode( phase->intcon(0),in1->in(2));
209 // Convert "x - (y+x)" into "-y"
210 if( op2 == Opcodes::Op_AddI &&
211 phase->eqv( in1, in2->in(2) ) )
212 return new SubINode( phase->intcon(0),in2->in(1));
213
214 // Convert "0 - (x-y)" into "y-x"
215 if( t1 == TypeInt::ZERO && op2 == Opcodes::Op_SubI )
216 return new SubINode( in2->in(2), in2->in(1) );
217
218 // Convert "0 - (x+con)" into "-con-x"
219 jint con;
220 if( t1 == TypeInt::ZERO && op2 == Opcodes::Op_AddI &&
221 (con = in2->in(2)->find_int_con(0)) != 0 )
222 return new SubINode( phase->intcon(-con), in2->in(1) );
223
224 // Convert "(X+A) - (X+B)" into "A - B"
225 if( op1 == Opcodes::Op_AddI && op2 == Opcodes::Op_AddI && in1->in(1) == in2->in(1) )
226 return new SubINode( in1->in(2), in2->in(2) );
227
228 // Convert "(A+X) - (B+X)" into "A - B"
229 if( op1 == Opcodes::Op_AddI && op2 == Opcodes::Op_AddI && in1->in(2) == in2->in(2) )
230 return new SubINode( in1->in(1), in2->in(1) );
231
232 // Convert "(A+X) - (X+B)" into "A - B"
233 if( op1 == Opcodes::Op_AddI && op2 == Opcodes::Op_AddI && in1->in(2) == in2->in(1) )
234 return new SubINode( in1->in(1), in2->in(2) );
235
236 // Convert "(X+A) - (B+X)" into "A - B"
237 if( op1 == Opcodes::Op_AddI && op2 == Opcodes::Op_AddI && in1->in(1) == in2->in(2) )
238 return new SubINode( in1->in(2), in2->in(1) );
239
240 // Convert "A-(B-C)" into (A+C)-B", since add is commutative and generally
241 // nicer to optimize than subtract.
242 if( op2 == Opcodes::Op_SubI && in2->outcnt() == 1) {
243 Node *add1 = phase->transform( new AddINode( in1, in2->in(2) ) );
244 return new SubINode( add1, in2->in(1) );
245 }
246
247 return NULL;
248 }
249
250 //------------------------------sub--------------------------------------------
251 // A subtract node differences it's two inputs.
252 const Type *SubINode::sub( const Type *t1, const Type *t2 ) const {
253 const TypeInt *r0 = t1->is_int(); // Handy access
254 const TypeInt *r1 = t2->is_int();
255 int32_t lo = java_subtract(r0->_lo, r1->_hi);
256 int32_t hi = java_subtract(r0->_hi, r1->_lo);
257
258 // We next check for 32-bit overflow.
259 // If that happens, we just assume all integers are possible.
260 if( (((r0->_lo ^ r1->_hi) >= 0) || // lo ends have same signs OR
261 ((r0->_lo ^ lo) >= 0)) && // lo results have same signs AND
262 (((r0->_hi ^ r1->_lo) >= 0) || // hi ends have same signs OR
263 ((r0->_hi ^ hi) >= 0)) ) // hi results have same signs
264 return TypeInt::make(lo,hi,MAX2(r0->_widen,r1->_widen));
265 else // Overflow; assume all integers
266 return TypeInt::INT;
267 }
268
269 //=============================================================================
270 //------------------------------Ideal------------------------------------------
271 Node *SubLNode::Ideal(PhaseGVN *phase, bool can_reshape) {
272 Node *in1 = in(1);
273 Node *in2 = in(2);
274 Opcodes op1 = in1->Opcode();
275 Opcodes op2 = in2->Opcode();
276
277 #ifdef ASSERT
278 // Check for dead loop
279 if( phase->eqv( in1, this ) || phase->eqv( in2, this ) ||
280 ( op1 == Opcodes::Op_AddL || op1 == Opcodes::Op_SubL ) &&
281 ( phase->eqv( in1->in(1), this ) || phase->eqv( in1->in(2), this ) ||
282 phase->eqv( in1->in(1), in1 ) || phase->eqv( in1->in(2), in1 ) ) )
283 assert(false, "dead loop in SubLNode::Ideal");
284 #endif
285
286 if( phase->type( in2 ) == Type::TOP ) return NULL;
287 const TypeLong *i = phase->type( in2 )->isa_long();
288 // Convert "x-c0" into "x+ -c0".
289 if( i && // Might be bottom or top...
290 i->is_con() )
291 return new AddLNode(in1, phase->longcon(-i->get_con()));
292
293 // Convert "(x+c0) - y" into (x-y) + c0"
294 // Do not collapse (x+c0)-y if "+" is a loop increment or
295 // if "y" is a loop induction variable.
296 if( op1 == Opcodes::Op_AddL && ok_to_convert(in1, in2) ) {
297 Node *in11 = in1->in(1);
298 const Type *tadd = phase->type( in1->in(2) );
299 if( tadd->singleton() && tadd != Type::TOP ) {
300 Node *sub2 = phase->transform( new SubLNode( in11, in2 ));
301 return new AddLNode( sub2, in1->in(2) );
302 }
303 }
304
305 // Convert "x - (y+c0)" into "(x-y) - c0"
306 // Need the same check as in above optimization but reversed.
307 if (op2 == Opcodes::Op_AddL && ok_to_convert(in2, in1)) {
308 Node* in21 = in2->in(1);
309 Node* in22 = in2->in(2);
310 const TypeLong* tcon = phase->type(in22)->isa_long();
311 if (tcon != NULL && tcon->is_con()) {
312 Node* sub2 = phase->transform( new SubLNode(in1, in21) );
313 Node* neg_c0 = phase->longcon(- tcon->get_con());
314 return new AddLNode(sub2, neg_c0);
315 }
316 }
317
318 const Type *t1 = phase->type( in1 );
319 if( t1 == Type::TOP ) return NULL;
320
321 #ifdef ASSERT
322 // Check for dead loop
323 if( ( op2 == Opcodes::Op_AddL || op2 == Opcodes::Op_SubL ) &&
324 ( phase->eqv( in2->in(1), this ) || phase->eqv( in2->in(2), this ) ||
325 phase->eqv( in2->in(1), in2 ) || phase->eqv( in2->in(2), in2 ) ) )
326 assert(false, "dead loop in SubLNode::Ideal");
327 #endif
328
329 // Convert "x - (x+y)" into "-y"
330 if( op2 == Opcodes::Op_AddL &&
331 phase->eqv( in1, in2->in(1) ) )
332 return new SubLNode( phase->makecon(TypeLong::ZERO), in2->in(2));
333 // Convert "x - (y+x)" into "-y"
334 if( op2 == Opcodes::Op_AddL &&
335 phase->eqv( in1, in2->in(2) ) )
336 return new SubLNode( phase->makecon(TypeLong::ZERO),in2->in(1));
337
338 // Convert "0 - (x-y)" into "y-x"
339 if( phase->type( in1 ) == TypeLong::ZERO && op2 == Opcodes::Op_SubL )
340 return new SubLNode( in2->in(2), in2->in(1) );
341
342 // Convert "(X+A) - (X+B)" into "A - B"
343 if( op1 == Opcodes::Op_AddL && op2 == Opcodes::Op_AddL && in1->in(1) == in2->in(1) )
344 return new SubLNode( in1->in(2), in2->in(2) );
345
346 // Convert "(A+X) - (B+X)" into "A - B"
347 if( op1 == Opcodes::Op_AddL && op2 == Opcodes::Op_AddL && in1->in(2) == in2->in(2) )
348 return new SubLNode( in1->in(1), in2->in(1) );
349
350 // Convert "A-(B-C)" into (A+C)-B"
351 if( op2 == Opcodes::Op_SubL && in2->outcnt() == 1) {
352 Node *add1 = phase->transform( new AddLNode( in1, in2->in(2) ) );
353 return new SubLNode( add1, in2->in(1) );
354 }
355
356 return NULL;
357 }
358
359 //------------------------------sub--------------------------------------------
360 // A subtract node differences it's two inputs.
361 const Type *SubLNode::sub( const Type *t1, const Type *t2 ) const {
362 const TypeLong *r0 = t1->is_long(); // Handy access
363 const TypeLong *r1 = t2->is_long();
364 jlong lo = java_subtract(r0->_lo, r1->_hi);
365 jlong hi = java_subtract(r0->_hi, r1->_lo);
366
367 // We next check for 32-bit overflow.
368 // If that happens, we just assume all integers are possible.
369 if( (((r0->_lo ^ r1->_hi) >= 0) || // lo ends have same signs OR
370 ((r0->_lo ^ lo) >= 0)) && // lo results have same signs AND
371 (((r0->_hi ^ r1->_lo) >= 0) || // hi ends have same signs OR
611 // (This is a gross hack, since the sub method never
612 // looks at the structure of the node in any other case.)
613 if ((jint)lo0 >= 0 && (jint)lo1 >= 0 && is_index_range_check())
614 return TypeInt::CC_LT;
615 return TypeInt::CC; // else use worst case results
616 }
617
618 const Type* CmpUNode::Value(PhaseGVN* phase) const {
619 const Type* t = SubNode::Value_common(phase);
620 if (t != NULL) {
621 return t;
622 }
623 const Node* in1 = in(1);
624 const Node* in2 = in(2);
625 const Type* t1 = phase->type(in1);
626 const Type* t2 = phase->type(in2);
627 assert(t1->isa_int(), "CmpU has only Int type inputs");
628 if (t2 == TypeInt::INT) { // Compare to bottom?
629 return bottom_type();
630 }
631 Opcodes in1_op = in1->Opcode();
632 if (in1_op == Opcodes::Op_AddI || in1_op == Opcodes::Op_SubI) {
633 // The problem rise when result of AddI(SubI) may overflow
634 // signed integer value. Let say the input type is
635 // [256, maxint] then +128 will create 2 ranges due to
636 // overflow: [minint, minint+127] and [384, maxint].
637 // But C2 type system keep only 1 type range and as result
638 // it use general [minint, maxint] for this case which we
639 // can't optimize.
640 //
641 // Make 2 separate type ranges based on types of AddI(SubI) inputs
642 // and compare results of their compare. If results are the same
643 // CmpU node can be optimized.
644 const Node* in11 = in1->in(1);
645 const Node* in12 = in1->in(2);
646 const Type* t11 = (in11 == in1) ? Type::TOP : phase->type(in11);
647 const Type* t12 = (in12 == in1) ? Type::TOP : phase->type(in12);
648 // Skip cases when input types are top or bottom.
649 if ((t11 != Type::TOP) && (t11 != TypeInt::INT) &&
650 (t12 != Type::TOP) && (t12 != TypeInt::INT)) {
651 const TypeInt *r0 = t11->is_int();
652 const TypeInt *r1 = t12->is_int();
653 jlong lo_r0 = r0->_lo;
654 jlong hi_r0 = r0->_hi;
655 jlong lo_r1 = r1->_lo;
656 jlong hi_r1 = r1->_hi;
657 if (in1_op == Opcodes::Op_SubI) {
658 jlong tmp = hi_r1;
659 hi_r1 = -lo_r1;
660 lo_r1 = -tmp;
661 // Note, for substructing [minint,x] type range
662 // long arithmetic provides correct overflow answer.
663 // The confusion come from the fact that in 32-bit
664 // -minint == minint but in 64-bit -minint == maxint+1.
665 }
666 jlong lo_long = lo_r0 + lo_r1;
667 jlong hi_long = hi_r0 + hi_r1;
668 int lo_tr1 = min_jint;
669 int hi_tr1 = (int)hi_long;
670 int lo_tr2 = (int)lo_long;
671 int hi_tr2 = max_jint;
672 bool underflow = lo_long != (jlong)lo_tr2;
673 bool overflow = hi_long != (jlong)hi_tr1;
674 // Use sub(t1, t2) when there is no overflow (one type range)
675 // or when both overflow and underflow (too complex).
676 if ((underflow != overflow) && (hi_tr1 < lo_tr2)) {
677 // Overflow only on one boundary, compare 2 separate type ranges.
678 int w = MAX2(r0->_widen, r1->_widen); // _widen does not matter here
679 const TypeInt* tr1 = TypeInt::make(lo_tr1, hi_tr1, w);
680 const TypeInt* tr2 = TypeInt::make(lo_tr2, hi_tr2, w);
681 const Type* cmp1 = sub(tr1, t2);
682 const Type* cmp2 = sub(tr2, t2);
683 if (cmp1 == cmp2) {
684 return cmp1; // Hit!
685 }
686 }
687 }
688 }
689
690 return sub(t1, t2); // Local flavor of type subtraction
691 }
692
693 bool CmpUNode::is_index_range_check() const {
694 // Check for the "(X ModI Y) CmpU Y" shape
695 return (in(1)->Opcode() == Opcodes::Op_ModI &&
696 in(1)->in(2)->eqv_uncast(in(2)));
697 }
698
699 //------------------------------Idealize---------------------------------------
700 Node *CmpINode::Ideal( PhaseGVN *phase, bool can_reshape ) {
701 if (phase->type(in(2))->higher_equal(TypeInt::ZERO)) {
702 switch (in(1)->Opcode()) {
703 case Opcodes::Op_CmpL3: // Collapse a CmpL3/CmpI into a CmpL
704 return new CmpLNode(in(1)->in(1),in(1)->in(2));
705 case Opcodes::Op_CmpF3: // Collapse a CmpF3/CmpI into a CmpF
706 return new CmpFNode(in(1)->in(1),in(1)->in(2));
707 case Opcodes::Op_CmpD3: // Collapse a CmpD3/CmpI into a CmpD
708 return new CmpDNode(in(1)->in(1),in(1)->in(2));
709 //case Op_SubI:
710 // If (x - y) cannot overflow, then ((x - y) <?> 0)
711 // can be turned into (x <?> y).
712 // This is handled (with more general cases) by Ideal_sub_algebra.
713 }
714 }
715 return NULL; // No change
716 }
717
718
719 //=============================================================================
720 // Simplify a CmpL (compare 2 longs ) node, based on local information.
721 // If both inputs are constants, compare them.
722 const Type *CmpLNode::sub( const Type *t1, const Type *t2 ) const {
723 const TypeLong *r0 = t1->is_long(); // Handy access
724 const TypeLong *r1 = t2->is_long();
725
726 if( r0->_hi < r1->_lo ) // Range is always low?
727 return TypeInt::CC_LT;
809
810 // Known constants can be compared exactly
811 // Null can be distinguished from any NotNull pointers
812 // Unknown inputs makes an unknown result
813 if( r0->singleton() ) {
814 intptr_t bits0 = r0->get_con();
815 if( r1->singleton() )
816 return bits0 == r1->get_con() ? TypeInt::CC_EQ : TypeInt::CC_GT;
817 return ( r1->_ptr == TypePtr::NotNull && bits0==0 ) ? TypeInt::CC_GT : TypeInt::CC;
818 } else if( r1->singleton() ) {
819 intptr_t bits1 = r1->get_con();
820 return ( r0->_ptr == TypePtr::NotNull && bits1==0 ) ? TypeInt::CC_GT : TypeInt::CC;
821 } else
822 return TypeInt::CC;
823 }
824
825 static inline Node* isa_java_mirror_load(PhaseGVN* phase, Node* n) {
826 // Return the klass node for
827 // LoadP(AddP(foo:Klass, #java_mirror))
828 // or NULL if not matching.
829 if (n->Opcode() != Opcodes::Op_LoadP) return NULL;
830
831 const TypeInstPtr* tp = phase->type(n)->isa_instptr();
832 if (!tp || tp->klass() != phase->C->env()->Class_klass()) return NULL;
833
834 Node* adr = n->in(MemNode::Address);
835 intptr_t off = 0;
836 Node* k = AddPNode::Ideal_base_and_offset(adr, phase, off);
837 if (k == NULL) return NULL;
838 const TypeKlassPtr* tkp = phase->type(k)->isa_klassptr();
839 if (!tkp || off != in_bytes(Klass::java_mirror_offset())) return NULL;
840
841 // We've found the klass node of a Java mirror load.
842 return k;
843 }
844
845 static inline Node* isa_const_java_mirror(PhaseGVN* phase, Node* n) {
846 // for ConP(Foo.class) return ConP(Foo.klass)
847 // otherwise return NULL
848 if (!n->is_Con()) return NULL;
849
894 if (k1 && (k2 || conk2)) {
895 Node* lhs = k1;
896 Node* rhs = (k2 != NULL) ? k2 : conk2;
897 this->set_req(1, lhs);
898 this->set_req(2, rhs);
899 return this;
900 }
901 }
902
903 // Constant pointer on right?
904 const TypeKlassPtr* t2 = phase->type(in(2))->isa_klassptr();
905 if (t2 == NULL || !t2->klass_is_exact())
906 return NULL;
907 // Get the constant klass we are comparing to.
908 ciKlass* superklass = t2->klass();
909
910 // Now check for LoadKlass on left.
911 Node* ldk1 = in(1);
912 if (ldk1->is_DecodeNKlass()) {
913 ldk1 = ldk1->in(1);
914 if (ldk1->Opcode() != Opcodes::Op_LoadNKlass )
915 return NULL;
916 } else if (ldk1->Opcode() != Opcodes::Op_LoadKlass )
917 return NULL;
918 // Take apart the address of the LoadKlass:
919 Node* adr1 = ldk1->in(MemNode::Address);
920 intptr_t con2 = 0;
921 Node* ldk2 = AddPNode::Ideal_base_and_offset(adr1, phase, con2);
922 if (ldk2 == NULL)
923 return NULL;
924 if (con2 == oopDesc::klass_offset_in_bytes()) {
925 // We are inspecting an object's concrete class.
926 // Short-circuit the check if the query is abstract.
927 if (superklass->is_interface() ||
928 superklass->is_abstract()) {
929 // Make it come out always false:
930 this->set_req(2, phase->makecon(TypePtr::NULL_PTR));
931 return this;
932 }
933 }
934
935 // Check for a LoadKlass from primary supertype array.
936 // Any nested loadklass from loadklass+con must be from the p.s. array.
937 if (ldk2->is_DecodeNKlass()) {
938 // Keep ldk2 as DecodeN since it could be used in CmpP below.
939 if (ldk2->in(1)->Opcode() != Opcodes::Op_LoadNKlass )
940 return NULL;
941 } else if (ldk2->Opcode() != Opcodes::Op_LoadKlass)
942 return NULL;
943
944 // Verify that we understand the situation
945 if (con2 != (intptr_t) superklass->super_check_offset())
946 return NULL; // Might be element-klass loading from array klass
947
948 // If 'superklass' has no subklasses and is not an interface, then we are
949 // assured that the only input which will pass the type check is
950 // 'superklass' itself.
951 //
952 // We could be more liberal here, and allow the optimization on interfaces
953 // which have a single implementor. This would require us to increase the
954 // expressiveness of the add_dependency() mechanism.
955 // %%% Do this after we fix TypeOopPtr: Deps are expressive enough now.
956
957 // Object arrays must have their base element have no subtypes
958 while (superklass->is_obj_array_klass()) {
959 ciType* elem = superklass->as_obj_array_klass()->element_type();
960 superklass = elem->as_klass();
961 }
1106 if( td1->is_nan() || td2->is_nan() )
1107 return TypeInt::CC_LT;
1108
1109 if( td1->_d < td2->_d ) return TypeInt::CC_LT;
1110 if( td1->_d > td2->_d ) return TypeInt::CC_GT;
1111 assert( td1->_d == td2->_d, "do not understand FP behavior" );
1112 return TypeInt::CC_EQ;
1113 }
1114
1115 //------------------------------Ideal------------------------------------------
1116 Node *CmpDNode::Ideal(PhaseGVN *phase, bool can_reshape){
1117 // Check if we can change this to a CmpF and remove a ConvD2F operation.
1118 // Change (CMPD (F2D (float)) (ConD value))
1119 // To (CMPF (float) (ConF value))
1120 // Valid when 'value' does not lose precision as a float.
1121 // Benefits: eliminates conversion, does not require 24-bit mode
1122
1123 // NaNs prevent commuting operands. This transform works regardless of the
1124 // order of ConD and ConvF2D inputs by preserving the original order.
1125 int idx_f2d = 1; // ConvF2D on left side?
1126 if( in(idx_f2d)->Opcode() != Opcodes::Op_ConvF2D )
1127 idx_f2d = 2; // No, swap to check for reversed args
1128 int idx_con = 3-idx_f2d; // Check for the constant on other input
1129
1130 if( ConvertCmpD2CmpF &&
1131 in(idx_f2d)->Opcode() == Opcodes::Op_ConvF2D &&
1132 in(idx_con)->Opcode() == Opcodes::Op_ConD ) {
1133 const TypeD *t2 = in(idx_con)->bottom_type()->is_double_constant();
1134 double t2_value_as_double = t2->_d;
1135 float t2_value_as_float = (float)t2_value_as_double;
1136 if( t2_value_as_double == (double)t2_value_as_float ) {
1137 // Test value can be represented as a float
1138 // Eliminate the conversion to double and create new comparison
1139 Node *new_in1 = in(idx_f2d)->in(1);
1140 Node *new_in2 = phase->makecon( TypeF::make(t2_value_as_float) );
1141 if( idx_f2d != 1 ) { // Must flip args to match original order
1142 Node *tmp = new_in1;
1143 new_in1 = new_in2;
1144 new_in2 = tmp;
1145 }
1146 CmpFNode *new_cmp = (Opcode() == Opcodes::Op_CmpD3)
1147 ? new CmpF3Node( new_in1, new_in2 )
1148 : new CmpFNode ( new_in1, new_in2 ) ;
1149 return new_cmp; // Changed to CmpFNode
1150 }
1151 // Testing value required the precision of a double
1152 }
1153 return NULL; // No change
1154 }
1155
1156
1157 //=============================================================================
1158 //------------------------------cc2logical-------------------------------------
1159 // Convert a condition code type to a logical type
1160 const Type *BoolTest::cc2logical( const Type *CC ) const {
1161 if( CC == Type::TOP ) return Type::TOP;
1162 if( CC->base() != Type::Int ) return TypeInt::BOOL; // Bottom or worse
1163 const TypeInt *ti = CC->is_int();
1164 if( ti->is_con() ) { // Only 1 kind of condition codes set?
1165 // Match low order 2 bits
1166 int tmp = ((ti->get_con()&3) == (_test&3)) ? 1 : 0;
1220 return phase->transform(bol);
1221 }
1222
1223 //--------------------------------as_int_value---------------------------------
1224 Node* BoolNode::as_int_value(PhaseGVN* phase) {
1225 // Inverse to make_predicate. The CMove probably boils down to a Conv2B.
1226 Node* cmov = CMoveNode::make(NULL, this,
1227 phase->intcon(0), phase->intcon(1),
1228 TypeInt::BOOL);
1229 return phase->transform(cmov);
1230 }
1231
1232 //----------------------------------negate-------------------------------------
1233 BoolNode* BoolNode::negate(PhaseGVN* phase) {
1234 return new BoolNode(in(1), _test.negate());
1235 }
1236
1237 // Change "bool eq/ne (cmp (add/sub A B) C)" into false/true if add/sub
1238 // overflows and we can prove that C is not in the two resulting ranges.
1239 // This optimization is similar to the one performed by CmpUNode::Value().
1240 Node* BoolNode::fold_cmpI(PhaseGVN* phase, SubNode* cmp, Node* cmp1, Opcodes cmp_op,
1241 Opcodes cmp1_op, const TypeInt* cmp2_type) {
1242 // Only optimize eq/ne integer comparison of add/sub
1243 if((_test._test == BoolTest::eq || _test._test == BoolTest::ne) &&
1244 (cmp_op == Opcodes::Op_CmpI) && (cmp1_op == Opcodes::Op_AddI || cmp1_op == Opcodes::Op_SubI)) {
1245 // Skip cases were inputs of add/sub are not integers or of bottom type
1246 const TypeInt* r0 = phase->type(cmp1->in(1))->isa_int();
1247 const TypeInt* r1 = phase->type(cmp1->in(2))->isa_int();
1248 if ((r0 != NULL) && (r0 != TypeInt::INT) &&
1249 (r1 != NULL) && (r1 != TypeInt::INT) &&
1250 (cmp2_type != TypeInt::INT)) {
1251 // Compute exact (long) type range of add/sub result
1252 jlong lo_long = r0->_lo;
1253 jlong hi_long = r0->_hi;
1254 if (cmp1_op == Opcodes::Op_AddI) {
1255 lo_long += r1->_lo;
1256 hi_long += r1->_hi;
1257 } else {
1258 lo_long -= r1->_hi;
1259 hi_long -= r1->_lo;
1260 }
1261 // Check for over-/underflow by casting to integer
1262 int lo_int = (int)lo_long;
1263 int hi_int = (int)hi_long;
1264 bool underflow = lo_long != (jlong)lo_int;
1265 bool overflow = hi_long != (jlong)hi_int;
1266 if ((underflow != overflow) && (hi_int < lo_int)) {
1267 // Overflow on one boundary, compute resulting type ranges:
1268 // tr1 [MIN_INT, hi_int] and tr2 [lo_int, MAX_INT]
1269 int w = MAX2(r0->_widen, r1->_widen); // _widen does not matter here
1270 const TypeInt* tr1 = TypeInt::make(min_jint, hi_int, w);
1271 const TypeInt* tr2 = TypeInt::make(lo_int, max_jint, w);
1272 // Compare second input of cmp to both type ranges
1273 const Type* sub_tr1 = cmp->sub(tr1, cmp2_type);
1274 const Type* sub_tr2 = cmp->sub(tr2, cmp2_type);
1275 if (sub_tr1 == TypeInt::CC_LT && sub_tr2 == TypeInt::CC_GT) {
1276 // The result of the add/sub will never equal cmp2. Replace BoolNode
1277 // by false (0) if it tests for equality and by true (1) otherwise.
1278 return ConINode::make((_test._test == BoolTest::eq) ? 0 : 1);
1279 }
1280 }
1281 }
1282 }
1283 return NULL;
1284 }
1285
1286 //------------------------------Ideal------------------------------------------
1287 Node *BoolNode::Ideal(PhaseGVN *phase, bool can_reshape) {
1288 // Change "bool tst (cmp con x)" into "bool ~tst (cmp x con)".
1289 // This moves the constant to the right. Helps value-numbering.
1290 Node *cmp = in(1);
1291 if( !cmp->is_Sub() ) return NULL;
1292 Opcodes cop = cmp->Opcode();
1293 if( cop == Opcodes::Op_FastLock || cop == Opcodes::Op_FastUnlock) return NULL;
1294 Node *cmp1 = cmp->in(1);
1295 Node *cmp2 = cmp->in(2);
1296 if( !cmp1 ) return NULL;
1297
1298 if (_test._test == BoolTest::overflow || _test._test == BoolTest::no_overflow) {
1299 return NULL;
1300 }
1301
1302 // Constant on left?
1303 Node *con = cmp1;
1304 Opcodes op2 = cmp2->Opcode();
1305 // Move constants to the right of compare's to canonicalize.
1306 // Do not muck with Opaque1 nodes, as this indicates a loop
1307 // guard that cannot change shape.
1308 if( con->is_Con() && !cmp2->is_Con() && op2 != Opcodes::Op_Opaque1 &&
1309 // Because of NaN's, CmpD and CmpF are not commutative
1310 cop != Opcodes::Op_CmpD && cop != Opcodes::Op_CmpF &&
1311 // Protect against swapping inputs to a compare when it is used by a
1312 // counted loop exit, which requires maintaining the loop-limit as in(2)
1313 !is_counted_loop_exit_test() ) {
1314 // Ok, commute the constant to the right of the cmp node.
1315 // Clone the Node, getting a new Node of the same class
1316 cmp = cmp->clone();
1317 // Swap inputs to the clone
1318 cmp->swap_edges(1, 2);
1319 cmp = phase->transform( cmp );
1320 return new BoolNode( cmp, _test.commute() );
1321 }
1322
1323 // Change "bool eq/ne (cmp (xor X 1) 0)" into "bool ne/eq (cmp X 0)".
1324 // The XOR-1 is an idiom used to flip the sense of a bool. We flip the
1325 // test instead.
1326 Opcodes cmp1_op = cmp1->Opcode();
1327 const TypeInt* cmp2_type = phase->type(cmp2)->isa_int();
1328 if (cmp2_type == NULL) return NULL;
1329 Node* j_xor = cmp1;
1330 if( cmp2_type == TypeInt::ZERO &&
1331 cmp1_op == Opcodes::Op_XorI &&
1332 j_xor->in(1) != j_xor && // An xor of itself is dead
1333 phase->type( j_xor->in(1) ) == TypeInt::BOOL &&
1334 phase->type( j_xor->in(2) ) == TypeInt::ONE &&
1335 (_test._test == BoolTest::eq ||
1336 _test._test == BoolTest::ne) ) {
1337 Node *ncmp = phase->transform(new CmpINode(j_xor->in(1),cmp2));
1338 return new BoolNode( ncmp, _test.negate() );
1339 }
1340
1341 // Change ((x & m) u<= m) or ((m & x) u<= m) to always true
1342 // Same with ((x & m) u< m+1) and ((m & x) u< m+1)
1343 if (cop == Opcodes::Op_CmpU &&
1344 cmp1->Opcode() == Opcodes::Op_AndI) {
1345 Node* bound = NULL;
1346 if (_test._test == BoolTest::le) {
1347 bound = cmp2;
1348 } else if (_test._test == BoolTest::lt &&
1349 cmp2->Opcode() == Opcodes::Op_AddI &&
1350 cmp2->in(2)->find_int_con(0) == 1) {
1351 bound = cmp2->in(1);
1352 }
1353 if (cmp1->in(2) == bound || cmp1->in(1) == bound) {
1354 return ConINode::make(1);
1355 }
1356 }
1357
1358 // Change ((x & (m - 1)) u< m) into (m > 0)
1359 // This is the off-by-one variant of the above
1360 if (cop == Opcodes::Op_CmpU &&
1361 _test._test == BoolTest::lt &&
1362 cmp1->Opcode() == Opcodes::Op_AndI) {
1363 Node* l = cmp1->in(1);
1364 Node* r = cmp1->in(2);
1365 for (int repeat = 0; repeat < 2; repeat++) {
1366 bool match = r->Opcode() == Opcodes::Op_AddI && r->in(2)->find_int_con(0) == -1 &&
1367 r->in(1) == cmp2;
1368 if (match) {
1369 // arraylength known to be non-negative, so a (arraylength != 0) is sufficient,
1370 // but to be compatible with the array range check pattern, use (arraylength u> 0)
1371 Node* ncmp = cmp2->Opcode() == Opcodes::Op_LoadRange
1372 ? phase->transform(new CmpUNode(cmp2, phase->intcon(0)))
1373 : phase->transform(new CmpINode(cmp2, phase->intcon(0)));
1374 return new BoolNode(ncmp, BoolTest::gt);
1375 } else {
1376 // commute and try again
1377 l = cmp1->in(2);
1378 r = cmp1->in(1);
1379 }
1380 }
1381 }
1382
1383 // Change (arraylength <= 0) or (arraylength == 0)
1384 // into (arraylength u<= 0)
1385 // Also change (arraylength != 0) into (arraylength u> 0)
1386 // The latter version matches the code pattern generated for
1387 // array range checks, which will more likely be optimized later.
1388 if (cop == Opcodes::Op_CmpI &&
1389 cmp1->Opcode() == Opcodes::Op_LoadRange &&
1390 cmp2->find_int_con(-1) == 0) {
1391 if (_test._test == BoolTest::le || _test._test == BoolTest::eq) {
1392 Node* ncmp = phase->transform(new CmpUNode(cmp1, cmp2));
1393 return new BoolNode(ncmp, BoolTest::le);
1394 } else if (_test._test == BoolTest::ne) {
1395 Node* ncmp = phase->transform(new CmpUNode(cmp1, cmp2));
1396 return new BoolNode(ncmp, BoolTest::gt);
1397 }
1398 }
1399
1400 // Change "bool eq/ne (cmp (Conv2B X) 0)" into "bool eq/ne (cmp X 0)".
1401 // This is a standard idiom for branching on a boolean value.
1402 Node *c2b = cmp1;
1403 if( cmp2_type == TypeInt::ZERO &&
1404 cmp1_op == Opcodes::Op_Conv2B &&
1405 (_test._test == BoolTest::eq ||
1406 _test._test == BoolTest::ne) ) {
1407 Node *ncmp = phase->transform(phase->type(c2b->in(1))->isa_int()
1408 ? (Node*)new CmpINode(c2b->in(1),cmp2)
1409 : (Node*)new CmpPNode(c2b->in(1),phase->makecon(TypePtr::NULL_PTR))
1410 );
1411 return new BoolNode( ncmp, _test._test );
1412 }
1413
1414 // Comparing a SubI against a zero is equal to comparing the SubI
1415 // arguments directly. This only works for eq and ne comparisons
1416 // due to possible integer overflow.
1417 if ((_test._test == BoolTest::eq || _test._test == BoolTest::ne) &&
1418 (cop == Opcodes::Op_CmpI) &&
1419 (cmp1->Opcode() == Opcodes::Op_SubI) &&
1420 ( cmp2_type == TypeInt::ZERO ) ) {
1421 Node *ncmp = phase->transform( new CmpINode(cmp1->in(1),cmp1->in(2)));
1422 return new BoolNode( ncmp, _test._test );
1423 }
1424
1425 // Change (-A vs 0) into (A vs 0) by commuting the test. Disallow in the
1426 // most general case because negating 0x80000000 does nothing. Needed for
1427 // the CmpF3/SubI/CmpI idiom.
1428 if( cop == Opcodes::Op_CmpI &&
1429 cmp1->Opcode() == Opcodes::Op_SubI &&
1430 cmp2_type == TypeInt::ZERO &&
1431 phase->type( cmp1->in(1) ) == TypeInt::ZERO &&
1432 phase->type( cmp1->in(2) )->higher_equal(TypeInt::SYMINT) ) {
1433 Node *ncmp = phase->transform( new CmpINode(cmp1->in(2),cmp2));
1434 return new BoolNode( ncmp, _test.commute() );
1435 }
1436
1437 // Try to optimize signed integer comparison
1438 return fold_cmpI(phase, cmp->as_Sub(), cmp1, cop, cmp1_op, cmp2_type);
1439
1440 // The transformation below is not valid for either signed or unsigned
1441 // comparisons due to wraparound concerns at MAX_VALUE and MIN_VALUE.
1442 // This transformation can be resurrected when we are able to
1443 // make inferences about the range of values being subtracted from
1444 // (or added to) relative to the wraparound point.
1445 //
1446 // // Remove +/-1's if possible.
1447 // // "X <= Y-1" becomes "X < Y"
1448 // // "X+1 <= Y" becomes "X < Y"
1449 // // "X < Y+1" becomes "X <= Y"
|