jdk
1/*
2* Copyright (c) 2014, 2024, 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#include "precompiled.hpp"26#include "opto/addnode.hpp"27#include "opto/connode.hpp"28#include "opto/convertnode.hpp"29#include "opto/matcher.hpp"30#include "opto/movenode.hpp"31#include "opto/phaseX.hpp"32#include "opto/subnode.hpp"33
34//=============================================================================
35/*
36The major change is for CMoveP and StrComp. They have related but slightly
37different problems. They both take in TWO oops which are both null-checked
38independently before the using Node. After CCP removes the CastPP's they need
39to pick up the guarding test edge - in this case TWO control edges. I tried
40various solutions, all have problems:
41
42(1) Do nothing. This leads to a bug where we hoist a Load from a CMoveP or a
43StrComp above a guarding null check. I've seen both cases in normal -Xcomp
44testing.
45
46(2) Plug the control edge from 1 of the 2 oops in. Apparent problem here is
47to figure out which test post-dominates. The real problem is that it doesn't
48matter which one you pick. After you pick up, the dominating-test elider in
49IGVN can remove the test and allow you to hoist up to the dominating test on
50the chosen oop bypassing the test on the not-chosen oop. Seen in testing.
51Oops.
52
53(3) Leave the CastPP's in. This makes the graph more accurate in some sense;
54we get to keep around the knowledge that an oop is not-null after some test.
55Alas, the CastPP's interfere with GVN (some values are the regular oop, some
56are the CastPP of the oop, all merge at Phi's which cannot collapse, etc).
57This cost us 10% on SpecJVM, even when I removed some of the more trivial
58cases in the optimizer. Removing more useless Phi's started allowing Loads to
59illegally float above null checks. I gave up on this approach.
60
61(4) Add BOTH control edges to both tests. Alas, too much code knows that
62control edges are in slot-zero ONLY. Many quick asserts fail; no way to do
63this one. Note that I really want to allow the CMoveP to float and add both
64control edges to the dependent Load op - meaning I can select early but I
65cannot Load until I pass both tests.
66
67(5) Do not hoist CMoveP and StrComp. To this end I added the v-call
68depends_only_on_test(). No obvious performance loss on Spec, but we are
69clearly conservative on CMoveP (also so on StrComp but that's unlikely to
70matter ever).
71
72*/
73
74
75//------------------------------Ideal------------------------------------------
76// Return a node which is more "ideal" than the current node.
77// Move constants to the right.
78Node *CMoveNode::Ideal(PhaseGVN *phase, bool can_reshape) {79if (in(0) != nullptr && remove_dead_region(phase, can_reshape)) {80return this;81}82// Don't bother trying to transform a dead node83if (in(0) != nullptr && in(0)->is_top()) {84return nullptr;85}86assert(in(Condition) != this &&87in(IfFalse) != this &&88in(IfTrue) != this, "dead loop in CMoveNode::Ideal");89if (phase->type(in(Condition)) == Type::TOP ||90phase->type(in(IfFalse)) == Type::TOP ||91phase->type(in(IfTrue)) == Type::TOP) {92return nullptr;93}94// Canonicalize the node by moving constants to the right input.95if (in(Condition)->is_Bool() && phase->type(in(IfFalse))->singleton() && !phase->type(in(IfTrue))->singleton()) {96BoolNode* b = in(Condition)->as_Bool()->negate(phase);97return make(in(Control), phase->transform(b), in(IfTrue), in(IfFalse), _type);98}99
100Node* minmax = Ideal_minmax(phase, this);101if (minmax != nullptr) {102return minmax;103}104
105return nullptr;106}
107
108//------------------------------is_cmove_id------------------------------------
109// Helper function to check for CMOVE identity. Shared with PhiNode::Identity
110Node *CMoveNode::is_cmove_id( PhaseTransform *phase, Node *cmp, Node *t, Node *f, BoolNode *b ) {111// Check for Cmp'ing and CMove'ing same values112if ((cmp->in(1) == f && cmp->in(2) == t) ||113// Swapped Cmp is OK114(cmp->in(2) == f && cmp->in(1) == t)) {115// Give up this identity check for floating points because it may choose incorrect116// value around 0.0 and -0.0117if ( cmp->Opcode()==Op_CmpF || cmp->Opcode()==Op_CmpD )118return nullptr;119// Check for "(t==f)?t:f;" and replace with "f"120if( b->_test._test == BoolTest::eq )121return f;122// Allow the inverted case as well123// Check for "(t!=f)?t:f;" and replace with "t"124if( b->_test._test == BoolTest::ne )125return t;126}127return nullptr;128}
129
130//------------------------------Identity---------------------------------------
131// Conditional-move is an identity if both inputs are the same, or the test
132// true or false.
133Node* CMoveNode::Identity(PhaseGVN* phase) {134// C-moving identical inputs?135if (in(IfFalse) == in(IfTrue)) {136return in(IfFalse); // Then it doesn't matter137}138if (phase->type(in(Condition)) == TypeInt::ZERO) {139return in(IfFalse); // Always pick left(false) input140}141if (phase->type(in(Condition)) == TypeInt::ONE) {142return in(IfTrue); // Always pick right(true) input143}144
145// Check for CMove'ing a constant after comparing against the constant.146// Happens all the time now, since if we compare equality vs a constant in147// the parser, we "know" the variable is constant on one path and we force148// it. Thus code like "if( x==0 ) {/*EMPTY*/}" ends up inserting a149// conditional move: "x = (x==0)?0:x;". Yucko. This fix is slightly more150// general in that we don't need constants.151if( in(Condition)->is_Bool() ) {152BoolNode *b = in(Condition)->as_Bool();153Node *cmp = b->in(1);154if( cmp->is_Cmp() ) {155Node *id = is_cmove_id( phase, cmp, in(IfTrue), in(IfFalse), b );156if( id ) return id;157}158}159
160return this;161}
162
163//------------------------------Value------------------------------------------
164// Result is the meet of inputs
165const Type* CMoveNode::Value(PhaseGVN* phase) const {166if (phase->type(in(Condition)) == Type::TOP) {167return Type::TOP;168}169if (phase->type(in(IfTrue)) == Type::TOP || phase->type(in(IfFalse)) == Type::TOP) {170return Type::TOP;171}172if (phase->type(in(Condition)) == TypeInt::ZERO) {173return phase->type(in(IfFalse))->filter(_type); // Always pick left (false) input174}175if (phase->type(in(Condition)) == TypeInt::ONE) {176return phase->type(in(IfTrue))->filter(_type); // Always pick right (true) input177}178
179const Type* t = phase->type(in(IfFalse))->meet_speculative(phase->type(in(IfTrue)));180return t->filter(_type);181}
182
183//------------------------------make-------------------------------------------
184// Make a correctly-flavored CMove. Since _type is directly determined
185// from the inputs we do not need to specify it here.
186CMoveNode *CMoveNode::make(Node *c, Node *bol, Node *left, Node *right, const Type *t) {187switch( t->basic_type() ) {188case T_INT: return new CMoveINode( bol, left, right, t->is_int() );189case T_FLOAT: return new CMoveFNode( bol, left, right, t );190case T_DOUBLE: return new CMoveDNode( bol, left, right, t );191case T_LONG: return new CMoveLNode( bol, left, right, t->is_long() );192case T_OBJECT: return new CMovePNode( c, bol, left, right, t->is_oopptr() );193case T_ADDRESS: return new CMovePNode( c, bol, left, right, t->is_ptr() );194case T_NARROWOOP: return new CMoveNNode( c, bol, left, right, t );195default:196ShouldNotReachHere();197return nullptr;198}199}
200
201// Try to identify min/max patterns in CMoves
202Node* CMoveNode::Ideal_minmax(PhaseGVN* phase, CMoveNode* cmove) {203// Only create MinL/MaxL if we are allowed to create macro nodes.204if (!phase->C->allow_macro_nodes()) {205return nullptr;206}207
208// The BoolNode may have been idealized into a constant. If that's the case, then Identity should take care of it instead.209BoolNode* bol = cmove->in(CMoveNode::Condition)->isa_Bool();210if (bol == nullptr) {211return nullptr;212}213
214Node* cmp = bol->in(1);215int cmove_op = cmove->Opcode();216int cmp_op = cmp->Opcode();217
218// Ensure comparison is an integral type, and that the cmove is of the same type.219if (!((cmp_op == Op_CmpI && cmove_op == Op_CMoveI) || (cmp_op == Op_CmpL && cmove_op == Op_CMoveL))) {220return nullptr;221}222
223// Only accept canonicalized le and lt comparisons224int test = bol->_test._test;225if (test != BoolTest::le && test != BoolTest::lt) {226return nullptr;227}228
229// The values being compared230Node* cmp_l = cmp->in(1);231Node* cmp_r = cmp->in(2);232
233// The values being selected234Node* cmove_l = cmove->in(CMoveNode::IfTrue);235Node* cmove_r = cmove->in(CMoveNode::IfFalse);236
237// For this transformation to be valid, the values being compared must be the same as the values being selected.238// We accept two different forms, "a < b ? a : b" and "a < b ? b : a". For the first form, the lhs and rhs of the239// comparison and cmove are the same, resulting in a minimum. For the second form, the lhs and rhs of both are flipped,240// resulting in a maximum. If neither form is found, bail out.241
242bool is_max;243if (cmp_l == cmove_l && cmp_r == cmove_r) {244is_max = false;245} else if (cmp_l == cmove_r && cmp_r == cmove_l) {246is_max = true;247} else {248return nullptr;249}250
251// Create the Min/Max node based on the type and kind252if (cmp_op == Op_CmpL) {253return MaxNode::build_min_max_long(phase, cmp_l, cmp_r, is_max);254} else {255return MaxNode::build_min_max_int(cmp_l, cmp_r, is_max);256}257}
258
259//=============================================================================
260//------------------------------Ideal------------------------------------------
261// Return a node which is more "ideal" than the current node.
262// Check for conversions to boolean
263Node *CMoveINode::Ideal(PhaseGVN *phase, bool can_reshape) {264// Try generic ideal's first265Node *x = CMoveNode::Ideal(phase, can_reshape);266if( x ) return x;267
268// If zero is on the left (false-case, no-move-case) it must mean another269// constant is on the right (otherwise the shared CMove::Ideal code would270// have moved the constant to the right). This situation is bad for x86 because271// the zero has to be manifested in a register with a XOR which kills flags,272// which are live on input to the CMoveI, leading to a situation which causes273// excessive spilling. See bug 4677505.274if( phase->type(in(IfFalse)) == TypeInt::ZERO && !(phase->type(in(IfTrue)) == TypeInt::ZERO) ) {275if( in(Condition)->is_Bool() ) {276BoolNode* b = in(Condition)->as_Bool();277BoolNode* b2 = b->negate(phase);278return make(in(Control), phase->transform(b2), in(IfTrue), in(IfFalse), _type);279}280}281
282// If we're late in the optimization process, we may have already expanded Conv2B nodes283if (phase->C->post_loop_opts_phase() && !Matcher::match_rule_supported(Op_Conv2B)) {284return nullptr;285}286
287// Now check for booleans288int flip = 0;289
290// Check for picking from zero/one291if( phase->type(in(IfFalse)) == TypeInt::ZERO && phase->type(in(IfTrue)) == TypeInt::ONE ) {292flip = 1 - flip;293} else if( phase->type(in(IfFalse)) == TypeInt::ONE && phase->type(in(IfTrue)) == TypeInt::ZERO ) {294} else return nullptr;295
296// Check for eq/ne test297if( !in(1)->is_Bool() ) return nullptr;298BoolNode *bol = in(1)->as_Bool();299if( bol->_test._test == BoolTest::eq ) {300} else if( bol->_test._test == BoolTest::ne ) {301flip = 1-flip;302} else return nullptr;303
304// Check for vs 0 or 1305if( !bol->in(1)->is_Cmp() ) return nullptr;306const CmpNode *cmp = bol->in(1)->as_Cmp();307if( phase->type(cmp->in(2)) == TypeInt::ZERO ) {308} else if( phase->type(cmp->in(2)) == TypeInt::ONE ) {309// Allow cmp-vs-1 if the other input is bounded by 0-1310if( phase->type(cmp->in(1)) != TypeInt::BOOL )311return nullptr;312flip = 1 - flip;313} else return nullptr;314
315// Convert to a bool (flipped)316// Build int->bool conversion317if (PrintOpto) { tty->print_cr("CMOV to I2B"); }318Node* n = new Conv2BNode(cmp->in(1));319if (flip) {320n = new XorINode(phase->transform(n), phase->intcon(1));321}322
323return n;324}
325
326//=============================================================================
327//------------------------------Ideal------------------------------------------
328// Return a node which is more "ideal" than the current node.
329// Check for absolute value
330Node *CMoveFNode::Ideal(PhaseGVN *phase, bool can_reshape) {331// Try generic ideal's first332Node *x = CMoveNode::Ideal(phase, can_reshape);333if( x ) return x;334
335int cmp_zero_idx = 0; // Index of compare input where to look for zero336int phi_x_idx = 0; // Index of phi input where to find naked x337
338// Find the Bool339if( !in(1)->is_Bool() ) return nullptr;340BoolNode *bol = in(1)->as_Bool();341// Check bool sense342switch( bol->_test._test ) {343case BoolTest::lt: cmp_zero_idx = 1; phi_x_idx = IfTrue; break;344case BoolTest::le: cmp_zero_idx = 2; phi_x_idx = IfFalse; break;345case BoolTest::gt: cmp_zero_idx = 2; phi_x_idx = IfTrue; break;346case BoolTest::ge: cmp_zero_idx = 1; phi_x_idx = IfFalse; break;347default: return nullptr; break;348}349
350// Find zero input of CmpF; the other input is being abs'd351Node *cmpf = bol->in(1);352if( cmpf->Opcode() != Op_CmpF ) return nullptr;353Node *X = nullptr;354bool flip = false;355if( phase->type(cmpf->in(cmp_zero_idx)) == TypeF::ZERO ) {356X = cmpf->in(3 - cmp_zero_idx);357} else if (phase->type(cmpf->in(3 - cmp_zero_idx)) == TypeF::ZERO) {358// The test is inverted, we should invert the result...359X = cmpf->in(cmp_zero_idx);360flip = true;361} else {362return nullptr;363}364
365// If X is found on the appropriate phi input, find the subtract on the other366if( X != in(phi_x_idx) ) return nullptr;367int phi_sub_idx = phi_x_idx == IfTrue ? IfFalse : IfTrue;368Node *sub = in(phi_sub_idx);369
370// Allow only SubF(0,X) and fail out for all others; NegF is not OK371if( sub->Opcode() != Op_SubF ||372sub->in(2) != X ||373phase->type(sub->in(1)) != TypeF::ZERO ) return nullptr;374
375Node *abs = new AbsFNode( X );376if( flip )377abs = new SubFNode(sub->in(1), phase->transform(abs));378
379return abs;380}
381
382//=============================================================================
383//------------------------------Ideal------------------------------------------
384// Return a node which is more "ideal" than the current node.
385// Check for absolute value
386Node *CMoveDNode::Ideal(PhaseGVN *phase, bool can_reshape) {387// Try generic ideal's first388Node *x = CMoveNode::Ideal(phase, can_reshape);389if( x ) return x;390
391int cmp_zero_idx = 0; // Index of compare input where to look for zero392int phi_x_idx = 0; // Index of phi input where to find naked x393
394// Find the Bool395if( !in(1)->is_Bool() ) return nullptr;396BoolNode *bol = in(1)->as_Bool();397// Check bool sense398switch( bol->_test._test ) {399case BoolTest::lt: cmp_zero_idx = 1; phi_x_idx = IfTrue; break;400case BoolTest::le: cmp_zero_idx = 2; phi_x_idx = IfFalse; break;401case BoolTest::gt: cmp_zero_idx = 2; phi_x_idx = IfTrue; break;402case BoolTest::ge: cmp_zero_idx = 1; phi_x_idx = IfFalse; break;403default: return nullptr; break;404}405
406// Find zero input of CmpD; the other input is being abs'd407Node *cmpd = bol->in(1);408if( cmpd->Opcode() != Op_CmpD ) return nullptr;409Node *X = nullptr;410bool flip = false;411if( phase->type(cmpd->in(cmp_zero_idx)) == TypeD::ZERO ) {412X = cmpd->in(3 - cmp_zero_idx);413} else if (phase->type(cmpd->in(3 - cmp_zero_idx)) == TypeD::ZERO) {414// The test is inverted, we should invert the result...415X = cmpd->in(cmp_zero_idx);416flip = true;417} else {418return nullptr;419}420
421// If X is found on the appropriate phi input, find the subtract on the other422if( X != in(phi_x_idx) ) return nullptr;423int phi_sub_idx = phi_x_idx == IfTrue ? IfFalse : IfTrue;424Node *sub = in(phi_sub_idx);425
426// Allow only SubD(0,X) and fail out for all others; NegD is not OK427if( sub->Opcode() != Op_SubD ||428sub->in(2) != X ||429phase->type(sub->in(1)) != TypeD::ZERO ) return nullptr;430
431Node *abs = new AbsDNode( X );432if( flip )433abs = new SubDNode(sub->in(1), phase->transform(abs));434
435return abs;436}
437
438//------------------------------MoveNode------------------------------------------
439
440Node* MoveNode::Ideal(PhaseGVN* phase, bool can_reshape) {441if (can_reshape) {442// Fold reinterpret cast into memory operation:443// MoveX2Y (LoadX mem) => LoadY mem444LoadNode* ld = in(1)->isa_Load();445if (ld != nullptr && (ld->outcnt() == 1)) { // replace only446const Type* rt = bottom_type();447if (ld->has_reinterpret_variant(rt)) {448if (phase->C->post_loop_opts_phase()) {449return ld->convert_to_reinterpret_load(*phase, rt);450} else {451phase->C->record_for_post_loop_opts_igvn(this); // attempt the transformation once loop opts are over452}453}454}455}456return nullptr;457}
458
459Node* MoveNode::Identity(PhaseGVN* phase) {460if (in(1)->is_Move()) {461// Back-to-back moves: MoveX2Y (MoveY2X v) => v462assert(bottom_type() == in(1)->in(1)->bottom_type(), "sanity");463return in(1)->in(1);464}465return this;466}
467
468//------------------------------Value------------------------------------------
469const Type* MoveL2DNode::Value(PhaseGVN* phase) const {470const Type *t = phase->type( in(1) );471if( t == Type::TOP ) return Type::TOP;472const TypeLong *tl = t->is_long();473if( !tl->is_con() ) return bottom_type();474JavaValue v;475v.set_jlong(tl->get_con());476return TypeD::make( v.get_jdouble() );477}
478
479//------------------------------Identity----------------------------------------
480Node* MoveL2DNode::Identity(PhaseGVN* phase) {481if (in(1)->Opcode() == Op_MoveD2L) {482return in(1)->in(1);483}484return this;485}
486
487//------------------------------Value------------------------------------------
488const Type* MoveI2FNode::Value(PhaseGVN* phase) const {489const Type *t = phase->type( in(1) );490if( t == Type::TOP ) return Type::TOP;491const TypeInt *ti = t->is_int();492if( !ti->is_con() ) return bottom_type();493JavaValue v;494v.set_jint(ti->get_con());495return TypeF::make( v.get_jfloat() );496}
497
498//------------------------------Identity----------------------------------------
499Node* MoveI2FNode::Identity(PhaseGVN* phase) {500if (in(1)->Opcode() == Op_MoveF2I) {501return in(1)->in(1);502}503return this;504}
505
506//------------------------------Value------------------------------------------
507const Type* MoveF2INode::Value(PhaseGVN* phase) const {508const Type *t = phase->type( in(1) );509if( t == Type::TOP ) return Type::TOP;510if( t == Type::FLOAT ) return TypeInt::INT;511const TypeF *tf = t->is_float_constant();512JavaValue v;513v.set_jfloat(tf->getf());514return TypeInt::make( v.get_jint() );515}
516
517//------------------------------Identity----------------------------------------
518Node* MoveF2INode::Identity(PhaseGVN* phase) {519if (in(1)->Opcode() == Op_MoveI2F) {520return in(1)->in(1);521}522return this;523}
524
525//------------------------------Value------------------------------------------
526const Type* MoveD2LNode::Value(PhaseGVN* phase) const {527const Type *t = phase->type( in(1) );528if( t == Type::TOP ) return Type::TOP;529if( t == Type::DOUBLE ) return TypeLong::LONG;530const TypeD *td = t->is_double_constant();531JavaValue v;532v.set_jdouble(td->getd());533return TypeLong::make( v.get_jlong() );534}
535
536//------------------------------Identity----------------------------------------
537Node* MoveD2LNode::Identity(PhaseGVN* phase) {538if (in(1)->Opcode() == Op_MoveL2D) {539return in(1)->in(1);540}541return this;542}
543