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 "gc/shared/barrierSet.hpp"
26 #include "gc/shared/c2/barrierSetC2.hpp"
27 #include "memory/allocation.inline.hpp"
28 #include "memory/resourceArea.hpp"
29 #include "oops/objArrayKlass.hpp"
30 #include "opto/addnode.hpp"
31 #include "opto/castnode.hpp"
32 #include "opto/cfgnode.hpp"
33 #include "opto/connode.hpp"
34 #include "opto/convertnode.hpp"
35 #include "opto/loopnode.hpp"
36 #include "opto/machnode.hpp"
37 #include "opto/movenode.hpp"
38 #include "opto/mulnode.hpp"
39 #include "opto/narrowptrnode.hpp"
40 #include "opto/phaseX.hpp"
41 #include "opto/regalloc.hpp"
42 #include "opto/regmask.hpp"
43 #include "opto/runtime.hpp"
44 #include "opto/subnode.hpp"
45 #include "opto/vectornode.hpp"
46 #include "utilities/vmError.hpp"
47
48 // Portions of code courtesy of Clifford Click
49
50 // Optimization - Graph Style
51
52 //=============================================================================
53 //------------------------------Value------------------------------------------
54 // Compute the type of the RegionNode.
503 if (left_path == nullptr || right_path == nullptr) {
504 return false;
505 }
506 Node* diamond_if = left_path->in(0);
507 if (diamond_if == nullptr || !diamond_if->is_If() || diamond_if != right_path->in(0)) {
508 // Not an IfNode merging a diamond or TOP.
509 return false;
510 }
511
512 // Check for a proper bool/cmp
513 const Node* bol = diamond_if->in(1);
514 if (!bol->is_Bool()) {
515 return false;
516 }
517 const Node* cmp = bol->in(1);
518 if (!cmp->is_Cmp()) {
519 return false;
520 }
521 return true;
522 }
523 //------------------------------Ideal------------------------------------------
524 // Return a node which is more "ideal" than the current node. Must preserve
525 // the CFG, but we can still strip out dead paths.
526 Node *RegionNode::Ideal(PhaseGVN *phase, bool can_reshape) {
527 if( !can_reshape && !in(0) ) return nullptr; // Already degraded to a Copy
528 assert(!in(0) || !in(0)->is_Root(), "not a specially hidden merge");
529
530 // Check for RegionNode with no Phi users and both inputs come from either
531 // arm of the same IF. If found, then the control-flow split is useless.
532 bool has_phis = false;
533 if (can_reshape) { // Need DU info to check for Phi users
534 try_clean_mem_phis(phase->is_IterGVN());
535 has_phis = (has_phi() != nullptr); // Cache result
536
537 if (!has_phis) { // No Phi users? Nothing merging?
538 for (uint i = 1; i < req()-1; i++) {
539 Node *if1 = in(i);
540 if( !if1 ) continue;
541 Node *iff = if1->in(0);
542 if( !iff || !iff->is_If() ) continue;
949 if (iff1 == iff2) {
950 igvn->add_users_to_worklist(iff1); // Make sure dead if is eliminated
951 igvn->replace_input_of(region, idx1, iff1->in(0));
952 igvn->replace_input_of(region, idx2, igvn->C->top());
953 return (region == this); // Remove useless if (both projections map to the same control/value)
954 }
955 BoolNode* bol1 = iff1->in(1)->isa_Bool();
956 BoolNode* bol2 = iff2->in(1)->isa_Bool();
957 if (bol1 == nullptr || bol2 == nullptr) {
958 return false; // No bool inputs found
959 }
960 Node* cmp1 = bol1->in(1);
961 Node* cmp2 = bol2->in(1);
962 bool commute = false;
963 if (!cmp1->is_Cmp() || !cmp2->is_Cmp()) {
964 return false; // No comparison
965 } else if (cmp1->Opcode() == Op_CmpF || cmp1->Opcode() == Op_CmpD ||
966 cmp2->Opcode() == Op_CmpF || cmp2->Opcode() == Op_CmpD ||
967 cmp1->Opcode() == Op_CmpP || cmp1->Opcode() == Op_CmpN ||
968 cmp2->Opcode() == Op_CmpP || cmp2->Opcode() == Op_CmpN ||
969 cmp1->is_SubTypeCheck() || cmp2->is_SubTypeCheck()) {
970 // Floats and pointers don't exactly obey trichotomy. To be on the safe side, don't transform their tests.
971 // SubTypeCheck is not commutative
972 return false;
973 } else if (cmp1 != cmp2) {
974 if (cmp1->in(1) == cmp2->in(2) &&
975 cmp1->in(2) == cmp2->in(1)) {
976 commute = true; // Same but swapped inputs, commute the test
977 } else {
978 return false; // Ifs are not comparing the same values
979 }
980 }
981 proj1 = proj1->other_if_proj();
982 proj2 = proj2->other_if_proj();
983 if (!((proj1->unique_ctrl_out_or_null() == iff2 &&
984 proj2->unique_ctrl_out_or_null() == this) ||
985 (proj2->unique_ctrl_out_or_null() == iff1 &&
986 proj1->unique_ctrl_out_or_null() == this))) {
987 return false; // Ifs are not connected through other projs
988 }
989 // Found 'iff -> proj -> iff -> proj -> this' shape where all other projs are merged
1028 st->print("#reducible ");
1029 break;
1030 case RegionNode::LoopStatus::NeverIrreducibleEntry:
1031 break; // nothing
1032 }
1033 }
1034 #endif
1035
1036 // Find the one non-null required input. RegionNode only
1037 Node *Node::nonnull_req() const {
1038 assert( is_Region(), "" );
1039 for( uint i = 1; i < _cnt; i++ )
1040 if( in(i) )
1041 return in(i);
1042 ShouldNotReachHere();
1043 return nullptr;
1044 }
1045
1046
1047 //=============================================================================
1048 // note that these functions assume that the _adr_type field is flattened
1049 uint PhiNode::hash() const {
1050 const Type* at = _adr_type;
1051 return TypeNode::hash() + (at ? at->hash() : 0);
1052 }
1053 bool PhiNode::cmp( const Node &n ) const {
1054 return TypeNode::cmp(n) && _adr_type == ((PhiNode&)n)._adr_type;
1055 }
1056 static inline
1057 const TypePtr* flatten_phi_adr_type(const TypePtr* at) {
1058 if (at == nullptr || at == TypePtr::BOTTOM) return at;
1059 return Compile::current()->alias_type(at)->adr_type();
1060 }
1061
1062 //----------------------------make---------------------------------------------
1063 // create a new phi with edges matching r and set (initially) to x
1064 PhiNode* PhiNode::make(Node* r, Node* x, const Type *t, const TypePtr* at) {
1065 uint preds = r->req(); // Number of predecessor paths
1066 assert(t != Type::MEMORY || at == flatten_phi_adr_type(at), "flatten at");
1067 PhiNode* p = new PhiNode(r, t, at);
1068 for (uint j = 1; j < preds; j++) {
1069 // Fill in all inputs, except those which the region does not yet have
1070 if (r->in(j) != nullptr)
1071 p->init_req(j, x);
1072 }
1073 return p;
1074 }
1075 PhiNode* PhiNode::make(Node* r, Node* x) {
1076 const Type* t = x->bottom_type();
1077 const TypePtr* at = nullptr;
1078 if (t == Type::MEMORY) at = flatten_phi_adr_type(x->adr_type());
1079 return make(r, x, t, at);
1080 }
1081 PhiNode* PhiNode::make_blank(Node* r, Node* x) {
1082 const Type* t = x->bottom_type();
1083 const TypePtr* at = nullptr;
1084 if (t == Type::MEMORY) at = flatten_phi_adr_type(x->adr_type());
1085 return new PhiNode(r, t, at);
1086 }
1175 np->as_Phi()->verify_adr_type(visited, at);
1176 } else if (n->bottom_type() == Type::TOP
1177 || (n->is_Mem() && n->in(MemNode::Address)->bottom_type() == Type::TOP)) {
1178 // ignore top inputs
1179 } else {
1180 const TypePtr* nat = flatten_phi_adr_type(n->adr_type());
1181 // recheck phi/non-phi consistency at leaves:
1182 assert((nat != nullptr) == (at != nullptr), "");
1183 assert(nat == at || nat == TypePtr::BOTTOM,
1184 "adr_type must be consistent at leaves of phi nest");
1185 }
1186 }
1187 }
1188
1189 // Verify a whole nest of phis rooted at this one.
1190 void PhiNode::verify_adr_type(bool recursive) const {
1191 if (VMError::is_error_reported()) return; // muzzle asserts when debugging an error
1192 if (Node::in_dump()) return; // muzzle asserts when printing
1193
1194 assert((_type == Type::MEMORY) == (_adr_type != nullptr), "adr_type for memory phis only");
1195
1196 if (!VerifyAliases) return; // verify thoroughly only if requested
1197
1198 assert(_adr_type == flatten_phi_adr_type(_adr_type),
1199 "Phi::adr_type must be pre-normalized");
1200
1201 if (recursive) {
1202 VectorSet visited;
1203 verify_adr_type(visited, _adr_type);
1204 }
1205 }
1206 #endif
1207
1208
1209 //------------------------------Value------------------------------------------
1210 // Compute the type of the PhiNode
1211 const Type* PhiNode::Value(PhaseGVN* phase) const {
1212 Node *r = in(0); // RegionNode
1213 if( !r ) // Copy or dead
1214 return in(1) ? phase->type(in(1)) : Type::TOP;
1393 assert(is_diamond_phi() > 0, "sanity");
1394 assert(req() == 3, "same as region");
1395 const Node* region = in(0);
1396 for (uint i = 1; i < 3; i++) {
1397 Node* phi_input = in(i);
1398 if (phi_input != nullptr && phi_input->is_MergeMem() && region->in(i)->outcnt() == 1) {
1399 // Nothing is control-dependent on path #i except the region itself.
1400 MergeMemNode* merge_mem = phi_input->as_MergeMem();
1401 uint j = 3 - i;
1402 Node* other_phi_input = in(j);
1403 if (other_phi_input != nullptr && other_phi_input == merge_mem->base_memory()) {
1404 // merge_mem is a successor memory to other_phi_input, and is not pinned inside the diamond, so push it out.
1405 // This will allow the diamond to collapse completely if there are no other phis left.
1406 igvn->replace_node(this, merge_mem);
1407 return true;
1408 }
1409 }
1410 }
1411 return false;
1412 }
1413 //----------------------------check_cmove_id-----------------------------------
1414 // Check for CMove'ing a constant after comparing against the constant.
1415 // Happens all the time now, since if we compare equality vs a constant in
1416 // the parser, we "know" the variable is constant on one path and we force
1417 // it. Thus code like "if( x==0 ) {/*EMPTY*/}" ends up inserting a
1418 // conditional move: "x = (x==0)?0:x;". Yucko. This fix is slightly more
1419 // general in that we don't need constants. Since CMove's are only inserted
1420 // in very special circumstances, we do it here on generic Phi's.
1421 Node* PhiNode::is_cmove_id(PhaseTransform* phase, int true_path) {
1422 assert(true_path !=0, "only diamond shape graph expected");
1423
1424 // is_diamond_phi() has guaranteed the correctness of the nodes sequence:
1425 // phi->region->if_proj->ifnode->bool->cmp
1426 Node* region = in(0);
1427 Node* iff = region->in(1)->in(0);
1428 BoolNode* b = iff->in(1)->as_Bool();
1429 Node* cmp = b->in(1);
1430 Node* tval = in(true_path);
1431 Node* fval = in(3-true_path);
1432 Node* id = CMoveNode::is_cmove_id(phase, cmp, tval, fval, b);
1447 }
1448
1449 return id;
1450 }
1451
1452 //------------------------------Identity---------------------------------------
1453 // Check for Region being Identity.
1454 Node* PhiNode::Identity(PhaseGVN* phase) {
1455 if (must_wait_for_region_in_irreducible_loop(phase)) {
1456 return this;
1457 }
1458 // Check for no merging going on
1459 // (There used to be special-case code here when this->region->is_Loop.
1460 // It would check for a tributary phi on the backedge that the main phi
1461 // trivially, perhaps with a single cast. The unique_input method
1462 // does all this and more, by reducing such tributaries to 'this'.)
1463 Node* uin = unique_input(phase, false);
1464 if (uin != nullptr) {
1465 return uin;
1466 }
1467
1468 int true_path = is_diamond_phi();
1469 // Delay CMove'ing identity if Ideal has not had the chance to handle unsafe cases, yet.
1470 if (true_path != 0 && !(phase->is_IterGVN() && wait_for_region_igvn(phase))) {
1471 Node* id = is_cmove_id(phase, true_path);
1472 if (id != nullptr) {
1473 return id;
1474 }
1475 }
1476
1477 // Looking for phis with identical inputs. If we find one that has
1478 // type TypePtr::BOTTOM, replace the current phi with the bottom phi.
1479 if (phase->is_IterGVN() && type() == Type::MEMORY && adr_type() !=
1480 TypePtr::BOTTOM && !adr_type()->is_known_instance()) {
1481 uint phi_len = req();
1482 Node* phi_reg = region();
1483 for (DUIterator_Fast imax, i = phi_reg->fast_outs(imax); i < imax; i++) {
1484 Node* u = phi_reg->fast_out(i);
1485 if (u->is_Phi() && u->as_Phi()->type() == Type::MEMORY &&
1486 u->adr_type() == TypePtr::BOTTOM && u->in(0) == phi_reg &&
1546 }
1547 // Check for a unique input (maybe uncasted)
1548 if (input == nullptr) {
1549 input = un;
1550 } else if (input != un) {
1551 input = NodeSentinel; // no unique input
1552 }
1553 }
1554 if (input == nullptr) {
1555 return phase->C->top(); // no inputs
1556 }
1557
1558 if (input != NodeSentinel) {
1559 return input; // one unique direct input
1560 }
1561
1562 // Nothing.
1563 return nullptr;
1564 }
1565
1566 //------------------------------is_x2logic-------------------------------------
1567 // Check for simple convert-to-boolean pattern
1568 // If:(C Bool) Region:(IfF IfT) Phi:(Region 0 1)
1569 // Convert Phi to an ConvIB.
1570 static Node *is_x2logic( PhaseGVN *phase, PhiNode *phi, int true_path ) {
1571 assert(true_path !=0, "only diamond shape graph expected");
1572
1573 // If we're late in the optimization process, we may have already expanded Conv2B nodes
1574 if (phase->C->post_loop_opts_phase() && !Matcher::match_rule_supported(Op_Conv2B)) {
1575 return nullptr;
1576 }
1577
1578 // Convert the true/false index into an expected 0/1 return.
1579 // Map 2->0 and 1->1.
1580 int flipped = 2-true_path;
1581
1582 // is_diamond_phi() has guaranteed the correctness of the nodes sequence:
1583 // phi->region->if_proj->ifnode->bool->cmp
1584 Node *region = phi->in(0);
1585 Node *iff = region->in(1)->in(0);
2013
2014 if (rc->in(0)->in(1) == nullptr || !rc->in(0)->in(1)->is_Bool()) { continue; }
2015 if (worklist.member(rc->in(0)->in(1))) {
2016 delay = true;
2017 break;
2018 }
2019
2020 if (rc->in(0)->in(1)->in(1) == nullptr || !rc->in(0)->in(1)->in(1)->is_Cmp()) { continue; }
2021 if (worklist.member(rc->in(0)->in(1)->in(1))) {
2022 delay = true;
2023 break;
2024 }
2025 }
2026
2027 if (delay) {
2028 worklist.push(this);
2029 }
2030 return delay;
2031 }
2032
2033 // If the Phi's Region is in an irreducible loop, and the Region
2034 // has had an input removed, but not yet transformed, it could be
2035 // that the Region (and this Phi) are not reachable from Root.
2036 // If we allow the Phi to collapse before the Region, this may lead
2037 // to dead-loop data. Wait for the Region to check for reachability,
2038 // and potentially remove the dead code.
2039 bool PhiNode::must_wait_for_region_in_irreducible_loop(PhaseGVN* phase) const {
2040 RegionNode* region = in(0)->as_Region();
2041 if (region->loop_status() == RegionNode::LoopStatus::MaybeIrreducibleEntry) {
2042 Node* top = phase->C->top();
2043 for (uint j = 1; j < req(); j++) {
2044 Node* rc = region->in(j); // for each control input
2045 if (rc == nullptr || phase->type(rc) == Type::TOP) {
2046 // Region is missing a control input
2047 Node* n = in(j);
2048 if (n != nullptr && n != top) {
2049 // Phi still has its input, so region just lost its input
2050 return true;
2051 }
2052 }
2413 // Phi (this) |
2414 // | |
2415 // +-----------+
2416 //
2417 // Generally, there are issues with non-termination with such circularity
2418 // (see comment further below). However, if there is a direct loop to self,
2419 // splitting the Phi through the MergeMem will result in the below.
2420 //
2421 // +---+
2422 // | |
2423 // v |
2424 // Phi |
2425 // |\ |
2426 // | +-+
2427 // (base_memory) v
2428 // MergeMem
2429 //
2430 // This split breaks the circularity and consequently does not lead to
2431 // non-termination.
2432 uint merge_width = 0;
2433 bool split_always_terminates = false; // Is splitting guaranteed to terminate?
2434 for( uint i=1; i<req(); ++i ) {// For all paths in
2435 Node *ii = in(i);
2436 // TOP inputs should not be counted as safe inputs because if the
2437 // Phi references itself through all other inputs then splitting the
2438 // Phi through memory merges would create dead loop at later stage.
2439 if (ii == top) {
2440 return nullptr; // Delay optimization until graph is cleaned.
2441 }
2442 if (ii->is_MergeMem()) {
2443 MergeMemNode* n = ii->as_MergeMem();
2444 merge_width = MAX2(merge_width, n->req());
2445 if (n->base_memory() == this) {
2446 split_always_terminates = true;
2447 }
2448 }
2449 }
2450
2451 // There are cases with circular dependencies between bottom Phis
2452 // and MergeMems. Below is a minimal example.
2453 //
2454 // +------------+
2455 // | |
2456 // (base_memory) v |
2457 // MergeMem |
2458 // | |
2459 // v |
2460 // Phi (this) |
2461 // | |
2462 // v |
2463 // Phi |
2464 // | |
2465 // +----------+
2466 //
2467 // Here, we cannot break the circularity through a self-loop as there
2468 // are two Phis involved. Repeatedly splitting the Phis through the
2469 // MergeMem leads to non-termination. We check for non-termination below.
2470 // Only check for non-termination if necessary.
2471 if (!split_always_terminates && adr_type() == TypePtr::BOTTOM &&
2472 merge_width > Compile::AliasIdxRaw) {
2473 split_always_terminates = is_split_through_mergemem_terminating();
2474 }
2475
2476 if (merge_width > Compile::AliasIdxRaw) {
2477 // found at least one non-empty MergeMem
2478 const TypePtr* at = adr_type();
2479 if (at != TypePtr::BOTTOM) {
2480 // Patch the existing phi to select an input from the merge:
2481 // Phi:AT1(...MergeMem(m0, m1, m2)...) into
2482 // Phi:AT1(...m1...)
2483 int alias_idx = phase->C->get_alias_index(at);
2484 for (uint i=1; i<req(); ++i) {
2485 Node *ii = in(i);
2486 if (ii->is_MergeMem()) {
2487 MergeMemNode* n = ii->as_MergeMem();
2488 // compress paths and change unreachable cycles to TOP
2489 // If not, we can update the input infinitely along a MergeMem cycle
2490 // Equivalent code is in MemNode::Ideal_common
2491 Node *m = phase->transform(n);
2492 if (outcnt() == 0) { // Above transform() may kill us!
2493 return top;
2494 }
2495 // If transformed to a MergeMem, get the desired slice
2496 // Otherwise the returned node represents memory for every slice
2497 Node *new_mem = (m->is_MergeMem()) ?
2498 m->as_MergeMem()->memory_at(alias_idx) : m;
2499 // Update input if it is progress over what we have now
2500 if (new_mem != ii) {
2501 set_req_X(i, new_mem, phase->is_IterGVN());
2502 progress = this;
2503 }
2504 }
2505 }
2506 } else if (split_always_terminates) {
2507 // If all inputs reference this phi (directly or through data nodes) -
2508 // it is a dead loop.
2509 bool saw_safe_input = false;
2510 for (uint j = 1; j < req(); ++j) {
2511 Node* n = in(j);
2512 if (n->is_MergeMem()) {
2513 MergeMemNode* mm = n->as_MergeMem();
2514 if (mm->base_memory() == this || mm->base_memory() == mm->empty_memory()) {
2515 // Skip this input if it references back to this phi or if the memory path is dead
2516 continue;
2517 }
2518 }
2519 if (!is_unsafe_data_reference(n)) {
2520 saw_safe_input = true; // found safe input
2521 break;
2522 }
2523 }
2524 if (!saw_safe_input) {
2525 // There is a dead loop: All inputs are either dead or reference back to this phi
2526 return top;
2527 }
2528
2529 // Phi(...MergeMem(m0, m1:AT1, m2:AT2)...) into
2530 // MergeMem(Phi(...m0...), Phi:AT1(...m1...), Phi:AT2(...m2...))
2531 PhaseIterGVN* igvn = phase->is_IterGVN();
2532 assert(igvn != nullptr, "sanity check");
2533 PhiNode* new_base = (PhiNode*) clone();
2534 // Must eagerly register phis, since they participate in loops.
2535 igvn->register_new_node_with_optimizer(new_base);
2536
2537 MergeMemNode* result = MergeMemNode::make(new_base);
2538 for (uint i = 1; i < req(); ++i) {
2539 Node *ii = in(i);
2540 if (ii->is_MergeMem()) {
2541 MergeMemNode* n = ii->as_MergeMem();
2542 for (MergeMemStream mms(result, n); mms.next_non_empty2(); ) {
2543 // If we have not seen this slice yet, make a phi for it.
2544 bool made_new_phi = false;
2545 if (mms.is_empty()) {
2546 Node* new_phi = new_base->slice_memory(mms.adr_type(phase->C));
2547 made_new_phi = true;
2548 igvn->register_new_node_with_optimizer(new_phi);
2549 mms.set_memory(new_phi);
2550 }
2551 Node* phi = mms.memory();
2552 assert(made_new_phi || phi->in(i) == n, "replace the i-th merge by a slice");
2553 phi->set_req(i, mms.memory2());
2554 }
2555 }
2556 }
2557 // Distribute all self-loops.
2558 { // (Extra braces to hide mms.)
2559 for (MergeMemStream mms(result); mms.next_non_empty(); ) {
2560 Node* phi = mms.memory();
2561 for (uint i = 1; i < req(); ++i) {
2632 if (is_decodeN) {
2633 new_ii = new EncodePNode(ii, narrow_t);
2634 } else {
2635 new_ii = new EncodePKlassNode(ii, narrow_t);
2636 }
2637 igvn->register_new_node_with_optimizer(new_ii);
2638 }
2639 }
2640 new_phi->set_req(i, new_ii);
2641 }
2642 igvn->register_new_node_with_optimizer(new_phi, this);
2643 if (is_decodeN) {
2644 progress = new DecodeNNode(new_phi, bottom_type());
2645 } else {
2646 progress = new DecodeNKlassNode(new_phi, bottom_type());
2647 }
2648 }
2649 }
2650 #endif
2651
2652 // Try to convert a Phi with two duplicated convert nodes into a phi of the pre-conversion type and the convert node
2653 // proceeding the phi, to de-duplicate the convert node and compact the IR.
2654 if (can_reshape && progress == nullptr) {
2655 ConvertNode* convert = in(1)->isa_Convert();
2656 if (convert != nullptr) {
2657 int conv_op = convert->Opcode();
2658 bool ok = true;
2659
2660 // Check the rest of the inputs
2661 for (uint i = 2; i < req(); i++) {
2662 // Make sure that all inputs are of the same type of convert node
2663 if (in(i)->Opcode() != conv_op) {
2664 ok = false;
2665 break;
2666 }
2667 }
2668
2669 if (ok) {
2670 // Find the local bottom type to set as the type of the phi
2671 const Type* source_type = Type::get_const_basic_type(convert->in_type()->basic_type());
2675 // Set inputs to the new phi be the inputs of the convert
2676 for (uint i = 1; i < req(); i++) {
2677 newphi->init_req(i, in(i)->in(1));
2678 }
2679
2680 phase->is_IterGVN()->register_new_node_with_optimizer(newphi, this);
2681
2682 return ConvertNode::create_convert(get_convert_type(convert, source_type), get_convert_type(convert, dest_type), newphi);
2683 }
2684 }
2685 }
2686
2687 // Phi (VB ... VB) => VB (Phi ...) (Phi ...)
2688 if (EnableVectorReboxing && can_reshape && progress == nullptr && type()->isa_oopptr()) {
2689 progress = merge_through_phi(this, phase->is_IterGVN());
2690 }
2691
2692 return progress; // Return any progress
2693 }
2694
2695 static int compare_types(const Type* const& e1, const Type* const& e2) {
2696 return (intptr_t)e1 - (intptr_t)e2;
2697 }
2698
2699 // Collect types at casts that are going to be eliminated at that Phi and store them in a TypeTuple.
2700 // Sort the types using an arbitrary order so a list of some types always hashes to the same TypeTuple (and TypeTuple
2701 // pointer comparison is enough to tell if 2 list of types are the same or not)
2702 const TypeTuple* PhiNode::collect_types(PhaseGVN* phase) const {
2703 const Node* region = in(0);
2704 const Type* phi_type = bottom_type();
2705 ResourceMark rm;
2706 GrowableArray<const Type*> types;
2707 for (uint i = 1; i < req(); i++) {
2708 if (region->in(i) == nullptr || phase->type(region->in(i)) == Type::TOP) {
2709 continue;
2710 }
2711 Node* in = Node::in(i);
2712 const Type* t = phase->type(in);
2713 if (in == nullptr || in == this || t == Type::TOP) {
2714 continue;
3057 #ifndef PRODUCT
3058 void CatchProjNode::dump_spec(outputStream *st) const {
3059 ProjNode::dump_spec(st);
3060 st->print("@bci %d ",_handler_bci);
3061 }
3062 #endif
3063
3064 //=============================================================================
3065 //------------------------------Identity---------------------------------------
3066 // Check for CreateEx being Identity.
3067 Node* CreateExNode::Identity(PhaseGVN* phase) {
3068 if( phase->type(in(1)) == Type::TOP ) return in(1);
3069 if( phase->type(in(0)) == Type::TOP ) return in(0);
3070 if (phase->type(in(0)->in(0)) == Type::TOP) {
3071 assert(in(0)->is_CatchProj(), "control is CatchProj");
3072 return phase->C->top(); // dead code
3073 }
3074 // We only come from CatchProj, unless the CatchProj goes away.
3075 // If the CatchProj is optimized away, then we just carry the
3076 // exception oop through.
3077 CallNode *call = in(1)->in(0)->as_Call();
3078
3079 return (in(0)->is_CatchProj() && in(0)->in(0)->is_Catch() &&
3080 in(0)->in(0)->in(1) == in(1)) ? this : call->in(TypeFunc::Parms);
3081 }
3082
3083 //=============================================================================
3084 //------------------------------Value------------------------------------------
3085 // Check for being unreachable.
3086 const Type* NeverBranchNode::Value(PhaseGVN* phase) const {
3087 if (!in(0) || in(0)->is_top()) return Type::TOP;
3088 return bottom_type();
3089 }
3090
3091 //------------------------------Ideal------------------------------------------
3092 // Check for no longer being part of a loop
3093 Node *NeverBranchNode::Ideal(PhaseGVN *phase, bool can_reshape) {
3094 if (can_reshape && !in(0)->is_Region()) {
3095 // Dead code elimination can sometimes delete this projection so
3096 // if it's not there, there's nothing to do.
|
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 "gc/shared/barrierSet.hpp"
26 #include "gc/shared/c2/barrierSetC2.hpp"
27 #include "memory/allocation.inline.hpp"
28 #include "memory/resourceArea.hpp"
29 #include "oops/objArrayKlass.hpp"
30 #include "opto/addnode.hpp"
31 #include "opto/castnode.hpp"
32 #include "opto/cfgnode.hpp"
33 #include "opto/connode.hpp"
34 #include "opto/convertnode.hpp"
35 #include "opto/inlinetypenode.hpp"
36 #include "opto/loopnode.hpp"
37 #include "opto/machnode.hpp"
38 #include "opto/movenode.hpp"
39 #include "opto/mulnode.hpp"
40 #include "opto/narrowptrnode.hpp"
41 #include "opto/phaseX.hpp"
42 #include "opto/regalloc.hpp"
43 #include "opto/regmask.hpp"
44 #include "opto/runtime.hpp"
45 #include "opto/subnode.hpp"
46 #include "opto/vectornode.hpp"
47 #include "utilities/vmError.hpp"
48
49 // Portions of code courtesy of Clifford Click
50
51 // Optimization - Graph Style
52
53 //=============================================================================
54 //------------------------------Value------------------------------------------
55 // Compute the type of the RegionNode.
504 if (left_path == nullptr || right_path == nullptr) {
505 return false;
506 }
507 Node* diamond_if = left_path->in(0);
508 if (diamond_if == nullptr || !diamond_if->is_If() || diamond_if != right_path->in(0)) {
509 // Not an IfNode merging a diamond or TOP.
510 return false;
511 }
512
513 // Check for a proper bool/cmp
514 const Node* bol = diamond_if->in(1);
515 if (!bol->is_Bool()) {
516 return false;
517 }
518 const Node* cmp = bol->in(1);
519 if (!cmp->is_Cmp()) {
520 return false;
521 }
522 return true;
523 }
524
525 //------------------------------Ideal------------------------------------------
526 // Return a node which is more "ideal" than the current node. Must preserve
527 // the CFG, but we can still strip out dead paths.
528 Node *RegionNode::Ideal(PhaseGVN *phase, bool can_reshape) {
529 if( !can_reshape && !in(0) ) return nullptr; // Already degraded to a Copy
530 assert(!in(0) || !in(0)->is_Root(), "not a specially hidden merge");
531
532 // Check for RegionNode with no Phi users and both inputs come from either
533 // arm of the same IF. If found, then the control-flow split is useless.
534 bool has_phis = false;
535 if (can_reshape) { // Need DU info to check for Phi users
536 try_clean_mem_phis(phase->is_IterGVN());
537 has_phis = (has_phi() != nullptr); // Cache result
538
539 if (!has_phis) { // No Phi users? Nothing merging?
540 for (uint i = 1; i < req()-1; i++) {
541 Node *if1 = in(i);
542 if( !if1 ) continue;
543 Node *iff = if1->in(0);
544 if( !iff || !iff->is_If() ) continue;
951 if (iff1 == iff2) {
952 igvn->add_users_to_worklist(iff1); // Make sure dead if is eliminated
953 igvn->replace_input_of(region, idx1, iff1->in(0));
954 igvn->replace_input_of(region, idx2, igvn->C->top());
955 return (region == this); // Remove useless if (both projections map to the same control/value)
956 }
957 BoolNode* bol1 = iff1->in(1)->isa_Bool();
958 BoolNode* bol2 = iff2->in(1)->isa_Bool();
959 if (bol1 == nullptr || bol2 == nullptr) {
960 return false; // No bool inputs found
961 }
962 Node* cmp1 = bol1->in(1);
963 Node* cmp2 = bol2->in(1);
964 bool commute = false;
965 if (!cmp1->is_Cmp() || !cmp2->is_Cmp()) {
966 return false; // No comparison
967 } else if (cmp1->Opcode() == Op_CmpF || cmp1->Opcode() == Op_CmpD ||
968 cmp2->Opcode() == Op_CmpF || cmp2->Opcode() == Op_CmpD ||
969 cmp1->Opcode() == Op_CmpP || cmp1->Opcode() == Op_CmpN ||
970 cmp2->Opcode() == Op_CmpP || cmp2->Opcode() == Op_CmpN ||
971 cmp1->is_SubTypeCheck() || cmp2->is_SubTypeCheck() ||
972 cmp1->is_FlatArrayCheck() || cmp2->is_FlatArrayCheck()) {
973 // Floats and pointers don't exactly obey trichotomy. To be on the safe side, don't transform their tests.
974 // SubTypeCheck is not commutative
975 return false;
976 } else if (cmp1 != cmp2) {
977 if (cmp1->in(1) == cmp2->in(2) &&
978 cmp1->in(2) == cmp2->in(1)) {
979 commute = true; // Same but swapped inputs, commute the test
980 } else {
981 return false; // Ifs are not comparing the same values
982 }
983 }
984 proj1 = proj1->other_if_proj();
985 proj2 = proj2->other_if_proj();
986 if (!((proj1->unique_ctrl_out_or_null() == iff2 &&
987 proj2->unique_ctrl_out_or_null() == this) ||
988 (proj2->unique_ctrl_out_or_null() == iff1 &&
989 proj1->unique_ctrl_out_or_null() == this))) {
990 return false; // Ifs are not connected through other projs
991 }
992 // Found 'iff -> proj -> iff -> proj -> this' shape where all other projs are merged
1031 st->print("#reducible ");
1032 break;
1033 case RegionNode::LoopStatus::NeverIrreducibleEntry:
1034 break; // nothing
1035 }
1036 }
1037 #endif
1038
1039 // Find the one non-null required input. RegionNode only
1040 Node *Node::nonnull_req() const {
1041 assert( is_Region(), "" );
1042 for( uint i = 1; i < _cnt; i++ )
1043 if( in(i) )
1044 return in(i);
1045 ShouldNotReachHere();
1046 return nullptr;
1047 }
1048
1049
1050 //=============================================================================
1051 // note that these functions assume that the _adr_type field is flat
1052 uint PhiNode::hash() const {
1053 const Type* at = _adr_type;
1054 return TypeNode::hash() + (at ? at->hash() : 0);
1055 }
1056 bool PhiNode::cmp( const Node &n ) const {
1057 return TypeNode::cmp(n) && _adr_type == ((PhiNode&)n)._adr_type;
1058 }
1059 static inline
1060 const TypePtr* flatten_phi_adr_type(const TypePtr* at) {
1061 if (at == nullptr || at == TypePtr::BOTTOM) return at;
1062 return Compile::current()->alias_type(at)->adr_type();
1063 }
1064
1065 //----------------------------make---------------------------------------------
1066 // create a new phi with edges matching r and set (initially) to x
1067 PhiNode* PhiNode::make(Node* r, Node* x, const Type *t, const TypePtr* at) {
1068 uint preds = r->req(); // Number of predecessor paths
1069 assert(t != Type::MEMORY || at == flatten_phi_adr_type(at) || (flatten_phi_adr_type(at) == TypeAryPtr::INLINES && Compile::current()->flat_accesses_share_alias()), "flatten at");
1070 PhiNode* p = new PhiNode(r, t, at);
1071 for (uint j = 1; j < preds; j++) {
1072 // Fill in all inputs, except those which the region does not yet have
1073 if (r->in(j) != nullptr)
1074 p->init_req(j, x);
1075 }
1076 return p;
1077 }
1078 PhiNode* PhiNode::make(Node* r, Node* x) {
1079 const Type* t = x->bottom_type();
1080 const TypePtr* at = nullptr;
1081 if (t == Type::MEMORY) at = flatten_phi_adr_type(x->adr_type());
1082 return make(r, x, t, at);
1083 }
1084 PhiNode* PhiNode::make_blank(Node* r, Node* x) {
1085 const Type* t = x->bottom_type();
1086 const TypePtr* at = nullptr;
1087 if (t == Type::MEMORY) at = flatten_phi_adr_type(x->adr_type());
1088 return new PhiNode(r, t, at);
1089 }
1178 np->as_Phi()->verify_adr_type(visited, at);
1179 } else if (n->bottom_type() == Type::TOP
1180 || (n->is_Mem() && n->in(MemNode::Address)->bottom_type() == Type::TOP)) {
1181 // ignore top inputs
1182 } else {
1183 const TypePtr* nat = flatten_phi_adr_type(n->adr_type());
1184 // recheck phi/non-phi consistency at leaves:
1185 assert((nat != nullptr) == (at != nullptr), "");
1186 assert(nat == at || nat == TypePtr::BOTTOM,
1187 "adr_type must be consistent at leaves of phi nest");
1188 }
1189 }
1190 }
1191
1192 // Verify a whole nest of phis rooted at this one.
1193 void PhiNode::verify_adr_type(bool recursive) const {
1194 if (VMError::is_error_reported()) return; // muzzle asserts when debugging an error
1195 if (Node::in_dump()) return; // muzzle asserts when printing
1196
1197 assert((_type == Type::MEMORY) == (_adr_type != nullptr), "adr_type for memory phis only");
1198 // Flat array element shouldn't get their own memory slice until flat_accesses_share_alias is cleared.
1199 // It could be the graph has no loads/stores and flat_accesses_share_alias is never cleared. EA could still
1200 // creates per element Phis but that wouldn't be a problem as there are no memory accesses for that array.
1201 assert(_adr_type == nullptr || _adr_type->isa_aryptr() == nullptr ||
1202 _adr_type->is_aryptr()->is_known_instance() ||
1203 !_adr_type->is_aryptr()->is_flat() ||
1204 !Compile::current()->flat_accesses_share_alias() ||
1205 _adr_type == TypeAryPtr::INLINES, "flat array element shouldn't get its own slice yet");
1206
1207 if (!VerifyAliases) return; // verify thoroughly only if requested
1208
1209 assert(_adr_type == flatten_phi_adr_type(_adr_type),
1210 "Phi::adr_type must be pre-normalized");
1211
1212 if (recursive) {
1213 VectorSet visited;
1214 verify_adr_type(visited, _adr_type);
1215 }
1216 }
1217 #endif
1218
1219
1220 //------------------------------Value------------------------------------------
1221 // Compute the type of the PhiNode
1222 const Type* PhiNode::Value(PhaseGVN* phase) const {
1223 Node *r = in(0); // RegionNode
1224 if( !r ) // Copy or dead
1225 return in(1) ? phase->type(in(1)) : Type::TOP;
1404 assert(is_diamond_phi() > 0, "sanity");
1405 assert(req() == 3, "same as region");
1406 const Node* region = in(0);
1407 for (uint i = 1; i < 3; i++) {
1408 Node* phi_input = in(i);
1409 if (phi_input != nullptr && phi_input->is_MergeMem() && region->in(i)->outcnt() == 1) {
1410 // Nothing is control-dependent on path #i except the region itself.
1411 MergeMemNode* merge_mem = phi_input->as_MergeMem();
1412 uint j = 3 - i;
1413 Node* other_phi_input = in(j);
1414 if (other_phi_input != nullptr && other_phi_input == merge_mem->base_memory()) {
1415 // merge_mem is a successor memory to other_phi_input, and is not pinned inside the diamond, so push it out.
1416 // This will allow the diamond to collapse completely if there are no other phis left.
1417 igvn->replace_node(this, merge_mem);
1418 return true;
1419 }
1420 }
1421 }
1422 return false;
1423 }
1424
1425 //----------------------------check_cmove_id-----------------------------------
1426 // Check for CMove'ing a constant after comparing against the constant.
1427 // Happens all the time now, since if we compare equality vs a constant in
1428 // the parser, we "know" the variable is constant on one path and we force
1429 // it. Thus code like "if( x==0 ) {/*EMPTY*/}" ends up inserting a
1430 // conditional move: "x = (x==0)?0:x;". Yucko. This fix is slightly more
1431 // general in that we don't need constants. Since CMove's are only inserted
1432 // in very special circumstances, we do it here on generic Phi's.
1433 Node* PhiNode::is_cmove_id(PhaseTransform* phase, int true_path) {
1434 assert(true_path !=0, "only diamond shape graph expected");
1435
1436 // is_diamond_phi() has guaranteed the correctness of the nodes sequence:
1437 // phi->region->if_proj->ifnode->bool->cmp
1438 Node* region = in(0);
1439 Node* iff = region->in(1)->in(0);
1440 BoolNode* b = iff->in(1)->as_Bool();
1441 Node* cmp = b->in(1);
1442 Node* tval = in(true_path);
1443 Node* fval = in(3-true_path);
1444 Node* id = CMoveNode::is_cmove_id(phase, cmp, tval, fval, b);
1459 }
1460
1461 return id;
1462 }
1463
1464 //------------------------------Identity---------------------------------------
1465 // Check for Region being Identity.
1466 Node* PhiNode::Identity(PhaseGVN* phase) {
1467 if (must_wait_for_region_in_irreducible_loop(phase)) {
1468 return this;
1469 }
1470 // Check for no merging going on
1471 // (There used to be special-case code here when this->region->is_Loop.
1472 // It would check for a tributary phi on the backedge that the main phi
1473 // trivially, perhaps with a single cast. The unique_input method
1474 // does all this and more, by reducing such tributaries to 'this'.)
1475 Node* uin = unique_input(phase, false);
1476 if (uin != nullptr) {
1477 return uin;
1478 }
1479 uin = unique_constant_input_recursive(phase);
1480 if (uin != nullptr) {
1481 return uin;
1482 }
1483
1484 int true_path = is_diamond_phi();
1485 // Delay CMove'ing identity if Ideal has not had the chance to handle unsafe cases, yet.
1486 if (true_path != 0 && !(phase->is_IterGVN() && wait_for_region_igvn(phase))) {
1487 Node* id = is_cmove_id(phase, true_path);
1488 if (id != nullptr) {
1489 return id;
1490 }
1491 }
1492
1493 // Looking for phis with identical inputs. If we find one that has
1494 // type TypePtr::BOTTOM, replace the current phi with the bottom phi.
1495 if (phase->is_IterGVN() && type() == Type::MEMORY && adr_type() !=
1496 TypePtr::BOTTOM && !adr_type()->is_known_instance()) {
1497 uint phi_len = req();
1498 Node* phi_reg = region();
1499 for (DUIterator_Fast imax, i = phi_reg->fast_outs(imax); i < imax; i++) {
1500 Node* u = phi_reg->fast_out(i);
1501 if (u->is_Phi() && u->as_Phi()->type() == Type::MEMORY &&
1502 u->adr_type() == TypePtr::BOTTOM && u->in(0) == phi_reg &&
1562 }
1563 // Check for a unique input (maybe uncasted)
1564 if (input == nullptr) {
1565 input = un;
1566 } else if (input != un) {
1567 input = NodeSentinel; // no unique input
1568 }
1569 }
1570 if (input == nullptr) {
1571 return phase->C->top(); // no inputs
1572 }
1573
1574 if (input != NodeSentinel) {
1575 return input; // one unique direct input
1576 }
1577
1578 // Nothing.
1579 return nullptr;
1580 }
1581
1582 // Find the unique input, try to look recursively through input Phis
1583 Node* PhiNode::unique_constant_input_recursive(PhaseGVN* phase) {
1584 if (!phase->is_IterGVN()) {
1585 return nullptr;
1586 }
1587
1588 ResourceMark rm;
1589 Node* unique = nullptr;
1590 Unique_Node_List visited;
1591 visited.push(this);
1592
1593 for (uint visited_idx = 0; visited_idx < visited.size(); visited_idx++) {
1594 Node* current = visited.at(visited_idx);
1595 for (uint i = 1; i < current->req(); i++) {
1596 Node* phi_in = current->in(i);
1597 if (phi_in == nullptr) {
1598 continue;
1599 }
1600
1601 if (phi_in->is_Phi()) {
1602 visited.push(phi_in);
1603 } else {
1604 if (unique == nullptr) {
1605 if (!phi_in->is_Con()) {
1606 return nullptr;
1607 }
1608 unique = phi_in;
1609 } else if (unique != phi_in) {
1610 return nullptr;
1611 }
1612 }
1613 }
1614 }
1615 return unique;
1616 }
1617
1618 //------------------------------is_x2logic-------------------------------------
1619 // Check for simple convert-to-boolean pattern
1620 // If:(C Bool) Region:(IfF IfT) Phi:(Region 0 1)
1621 // Convert Phi to an ConvIB.
1622 static Node *is_x2logic( PhaseGVN *phase, PhiNode *phi, int true_path ) {
1623 assert(true_path !=0, "only diamond shape graph expected");
1624
1625 // If we're late in the optimization process, we may have already expanded Conv2B nodes
1626 if (phase->C->post_loop_opts_phase() && !Matcher::match_rule_supported(Op_Conv2B)) {
1627 return nullptr;
1628 }
1629
1630 // Convert the true/false index into an expected 0/1 return.
1631 // Map 2->0 and 1->1.
1632 int flipped = 2-true_path;
1633
1634 // is_diamond_phi() has guaranteed the correctness of the nodes sequence:
1635 // phi->region->if_proj->ifnode->bool->cmp
1636 Node *region = phi->in(0);
1637 Node *iff = region->in(1)->in(0);
2065
2066 if (rc->in(0)->in(1) == nullptr || !rc->in(0)->in(1)->is_Bool()) { continue; }
2067 if (worklist.member(rc->in(0)->in(1))) {
2068 delay = true;
2069 break;
2070 }
2071
2072 if (rc->in(0)->in(1)->in(1) == nullptr || !rc->in(0)->in(1)->in(1)->is_Cmp()) { continue; }
2073 if (worklist.member(rc->in(0)->in(1)->in(1))) {
2074 delay = true;
2075 break;
2076 }
2077 }
2078
2079 if (delay) {
2080 worklist.push(this);
2081 }
2082 return delay;
2083 }
2084
2085 // Push inline type input nodes (and null) down through the phi recursively (can handle data loops).
2086 InlineTypeNode* PhiNode::push_inline_types_down(PhaseGVN* phase, bool can_reshape, ciInlineKlass* inline_klass) {
2087 assert(inline_klass != nullptr, "must be");
2088 InlineTypeNode* vt = InlineTypeNode::make_null(*phase, inline_klass, /* transform = */ false)->clone_with_phis(phase, in(0), nullptr, !_type->maybe_null(), true);
2089 if (can_reshape) {
2090 // Replace phi right away to be able to use the inline
2091 // type node when reaching the phi again through data loops.
2092 PhaseIterGVN* igvn = phase->is_IterGVN();
2093 for (DUIterator_Fast imax, i = fast_outs(imax); i < imax; i++) {
2094 Node* u = fast_out(i);
2095 igvn->rehash_node_delayed(u);
2096 imax -= u->replace_edge(this, vt);
2097 --i;
2098 }
2099 igvn->rehash_node_delayed(this);
2100 assert(outcnt() == 0, "should be dead now");
2101 }
2102 ResourceMark rm;
2103 Node_List casts;
2104 for (uint i = 1; i < req(); ++i) {
2105 Node* n = in(i);
2106 while (n->is_ConstraintCast()) {
2107 casts.push(n);
2108 n = n->in(1);
2109 }
2110 if (phase->type(n)->is_zero_type()) {
2111 n = InlineTypeNode::make_null(*phase, inline_klass);
2112 } else if (n->is_Phi()) {
2113 assert(can_reshape, "can only handle phis during IGVN");
2114 n = phase->transform(n->as_Phi()->push_inline_types_down(phase, can_reshape, inline_klass));
2115 }
2116 while (casts.size() != 0) {
2117 // Push the cast(s) through the InlineTypeNode
2118 // TODO 8302217 Can we avoid cloning? See InlineTypeNode::clone_if_required
2119 Node* cast = casts.pop()->clone();
2120 cast->set_req_X(1, n->as_InlineType()->get_oop(), phase);
2121 n = n->clone();
2122 n->as_InlineType()->set_oop(*phase, phase->transform(cast));
2123 n = phase->transform(n);
2124 if (n->is_top()) {
2125 break;
2126 }
2127 }
2128 bool transform = !can_reshape && (i == (req()-1)); // Transform phis on last merge
2129 assert(n->is_top() || n->is_InlineType(), "Only InlineType or top at this point.");
2130 if (n->is_InlineType()) {
2131 vt->merge_with(phase, n->as_InlineType(), i, transform);
2132 } // else nothing to do: phis above vt created by clone_with_phis are initialized to top already.
2133 }
2134 return vt;
2135 }
2136
2137 // If the Phi's Region is in an irreducible loop, and the Region
2138 // has had an input removed, but not yet transformed, it could be
2139 // that the Region (and this Phi) are not reachable from Root.
2140 // If we allow the Phi to collapse before the Region, this may lead
2141 // to dead-loop data. Wait for the Region to check for reachability,
2142 // and potentially remove the dead code.
2143 bool PhiNode::must_wait_for_region_in_irreducible_loop(PhaseGVN* phase) const {
2144 RegionNode* region = in(0)->as_Region();
2145 if (region->loop_status() == RegionNode::LoopStatus::MaybeIrreducibleEntry) {
2146 Node* top = phase->C->top();
2147 for (uint j = 1; j < req(); j++) {
2148 Node* rc = region->in(j); // for each control input
2149 if (rc == nullptr || phase->type(rc) == Type::TOP) {
2150 // Region is missing a control input
2151 Node* n = in(j);
2152 if (n != nullptr && n != top) {
2153 // Phi still has its input, so region just lost its input
2154 return true;
2155 }
2156 }
2517 // Phi (this) |
2518 // | |
2519 // +-----------+
2520 //
2521 // Generally, there are issues with non-termination with such circularity
2522 // (see comment further below). However, if there is a direct loop to self,
2523 // splitting the Phi through the MergeMem will result in the below.
2524 //
2525 // +---+
2526 // | |
2527 // v |
2528 // Phi |
2529 // |\ |
2530 // | +-+
2531 // (base_memory) v
2532 // MergeMem
2533 //
2534 // This split breaks the circularity and consequently does not lead to
2535 // non-termination.
2536 uint merge_width = 0;
2537 // TODO revisit this with JDK-8247216
2538 bool mergemem_only = true;
2539 bool split_always_terminates = false; // Is splitting guaranteed to terminate?
2540 for( uint i=1; i<req(); ++i ) {// For all paths in
2541 Node *ii = in(i);
2542 // TOP inputs should not be counted as safe inputs because if the
2543 // Phi references itself through all other inputs then splitting the
2544 // Phi through memory merges would create dead loop at later stage.
2545 if (ii == top) {
2546 return nullptr; // Delay optimization until graph is cleaned.
2547 }
2548 if (ii->is_MergeMem()) {
2549 MergeMemNode* n = ii->as_MergeMem();
2550 merge_width = MAX2(merge_width, n->req());
2551 if (n->base_memory() == this) {
2552 split_always_terminates = true;
2553 }
2554 } else {
2555 mergemem_only = false;
2556 }
2557 }
2558
2559 // There are cases with circular dependencies between bottom Phis
2560 // and MergeMems. Below is a minimal example.
2561 //
2562 // +------------+
2563 // | |
2564 // (base_memory) v |
2565 // MergeMem |
2566 // | |
2567 // v |
2568 // Phi (this) |
2569 // | |
2570 // v |
2571 // Phi |
2572 // | |
2573 // +----------+
2574 //
2575 // Here, we cannot break the circularity through a self-loop as there
2576 // are two Phis involved. Repeatedly splitting the Phis through the
2577 // MergeMem leads to non-termination. We check for non-termination below.
2578 // Only check for non-termination if necessary.
2579 if (!mergemem_only && !split_always_terminates && adr_type() == TypePtr::BOTTOM &&
2580 merge_width > Compile::AliasIdxRaw) {
2581 split_always_terminates = is_split_through_mergemem_terminating();
2582 }
2583
2584 if (merge_width > Compile::AliasIdxRaw) {
2585 // found at least one non-empty MergeMem
2586 const TypePtr* at = adr_type();
2587 if (at != TypePtr::BOTTOM) {
2588 // Patch the existing phi to select an input from the merge:
2589 // Phi:AT1(...MergeMem(m0, m1, m2)...) into
2590 // Phi:AT1(...m1...)
2591 int alias_idx = phase->C->get_alias_index(at);
2592 for (uint i=1; i<req(); ++i) {
2593 Node *ii = in(i);
2594 if (ii->is_MergeMem()) {
2595 MergeMemNode* n = ii->as_MergeMem();
2596 // compress paths and change unreachable cycles to TOP
2597 // If not, we can update the input infinitely along a MergeMem cycle
2598 // Equivalent code is in MemNode::Ideal_common
2599 Node *m = phase->transform(n);
2600 if (outcnt() == 0) { // Above transform() may kill us!
2601 return top;
2602 }
2603 // If transformed to a MergeMem, get the desired slice
2604 // Otherwise the returned node represents memory for every slice
2605 Node *new_mem = (m->is_MergeMem()) ?
2606 m->as_MergeMem()->memory_at(alias_idx) : m;
2607 // Update input if it is progress over what we have now
2608 if (new_mem != ii) {
2609 set_req_X(i, new_mem, phase->is_IterGVN());
2610 progress = this;
2611 }
2612 }
2613 }
2614 } else if (mergemem_only || split_always_terminates) {
2615 // If all inputs reference this phi (directly or through data nodes) -
2616 // it is a dead loop.
2617 bool saw_safe_input = false;
2618 for (uint j = 1; j < req(); ++j) {
2619 Node* n = in(j);
2620 if (n->is_MergeMem()) {
2621 MergeMemNode* mm = n->as_MergeMem();
2622 if (mm->base_memory() == this || mm->base_memory() == mm->empty_memory()) {
2623 // Skip this input if it references back to this phi or if the memory path is dead
2624 continue;
2625 }
2626 }
2627 if (!is_unsafe_data_reference(n)) {
2628 saw_safe_input = true; // found safe input
2629 break;
2630 }
2631 }
2632 if (!saw_safe_input) {
2633 // There is a dead loop: All inputs are either dead or reference back to this phi
2634 return top;
2635 }
2636
2637 // Phi(...MergeMem(m0, m1:AT1, m2:AT2)...) into
2638 // MergeMem(Phi(...m0...), Phi:AT1(...m1...), Phi:AT2(...m2...))
2639 PhaseIterGVN* igvn = phase->is_IterGVN();
2640 assert(igvn != nullptr, "sanity check");
2641 PhiNode* new_base = (PhiNode*) clone();
2642 // Must eagerly register phis, since they participate in loops.
2643 igvn->register_new_node_with_optimizer(new_base);
2644
2645 MergeMemNode* result = MergeMemNode::make(new_base);
2646 for (uint i = 1; i < req(); ++i) {
2647 Node *ii = in(i);
2648 if (ii->is_MergeMem()) {
2649 MergeMemNode* n = ii->as_MergeMem();
2650 if (igvn) {
2651 // TODO revisit this with JDK-8247216
2652 // Put 'n' on the worklist because it might be modified by MergeMemStream::iteration_setup
2653 igvn->_worklist.push(n);
2654 }
2655 for (MergeMemStream mms(result, n); mms.next_non_empty2(); ) {
2656 // If we have not seen this slice yet, make a phi for it.
2657 bool made_new_phi = false;
2658 if (mms.is_empty()) {
2659 Node* new_phi = new_base->slice_memory(mms.adr_type(phase->C));
2660 made_new_phi = true;
2661 igvn->register_new_node_with_optimizer(new_phi);
2662 mms.set_memory(new_phi);
2663 }
2664 Node* phi = mms.memory();
2665 assert(made_new_phi || phi->in(i) == n, "replace the i-th merge by a slice");
2666 phi->set_req(i, mms.memory2());
2667 }
2668 }
2669 }
2670 // Distribute all self-loops.
2671 { // (Extra braces to hide mms.)
2672 for (MergeMemStream mms(result); mms.next_non_empty(); ) {
2673 Node* phi = mms.memory();
2674 for (uint i = 1; i < req(); ++i) {
2745 if (is_decodeN) {
2746 new_ii = new EncodePNode(ii, narrow_t);
2747 } else {
2748 new_ii = new EncodePKlassNode(ii, narrow_t);
2749 }
2750 igvn->register_new_node_with_optimizer(new_ii);
2751 }
2752 }
2753 new_phi->set_req(i, new_ii);
2754 }
2755 igvn->register_new_node_with_optimizer(new_phi, this);
2756 if (is_decodeN) {
2757 progress = new DecodeNNode(new_phi, bottom_type());
2758 } else {
2759 progress = new DecodeNKlassNode(new_phi, bottom_type());
2760 }
2761 }
2762 }
2763 #endif
2764
2765 Node* inline_type = try_push_inline_types_down(phase, can_reshape);
2766 if (inline_type != this) {
2767 return inline_type;
2768 }
2769
2770 // Try to convert a Phi with two duplicated convert nodes into a phi of the pre-conversion type and the convert node
2771 // proceeding the phi, to de-duplicate the convert node and compact the IR.
2772 if (can_reshape && progress == nullptr) {
2773 ConvertNode* convert = in(1)->isa_Convert();
2774 if (convert != nullptr) {
2775 int conv_op = convert->Opcode();
2776 bool ok = true;
2777
2778 // Check the rest of the inputs
2779 for (uint i = 2; i < req(); i++) {
2780 // Make sure that all inputs are of the same type of convert node
2781 if (in(i)->Opcode() != conv_op) {
2782 ok = false;
2783 break;
2784 }
2785 }
2786
2787 if (ok) {
2788 // Find the local bottom type to set as the type of the phi
2789 const Type* source_type = Type::get_const_basic_type(convert->in_type()->basic_type());
2793 // Set inputs to the new phi be the inputs of the convert
2794 for (uint i = 1; i < req(); i++) {
2795 newphi->init_req(i, in(i)->in(1));
2796 }
2797
2798 phase->is_IterGVN()->register_new_node_with_optimizer(newphi, this);
2799
2800 return ConvertNode::create_convert(get_convert_type(convert, source_type), get_convert_type(convert, dest_type), newphi);
2801 }
2802 }
2803 }
2804
2805 // Phi (VB ... VB) => VB (Phi ...) (Phi ...)
2806 if (EnableVectorReboxing && can_reshape && progress == nullptr && type()->isa_oopptr()) {
2807 progress = merge_through_phi(this, phase->is_IterGVN());
2808 }
2809
2810 return progress; // Return any progress
2811 }
2812
2813 // Check recursively if inputs are either an inline type, constant null
2814 // or another Phi (including self references through data loops). If so,
2815 // push the inline types down through the phis to enable folding of loads.
2816 Node* PhiNode::try_push_inline_types_down(PhaseGVN* phase, const bool can_reshape) {
2817 if (!can_be_inline_type()) {
2818 return this;
2819 }
2820
2821 ciInlineKlass* inline_klass;
2822 if (can_push_inline_types_down(phase, can_reshape, inline_klass)) {
2823 assert(inline_klass != nullptr, "must be");
2824 return push_inline_types_down(phase, can_reshape, inline_klass);
2825 }
2826 return this;
2827 }
2828
2829 bool PhiNode::can_push_inline_types_down(PhaseGVN* phase, const bool can_reshape, ciInlineKlass*& inline_klass) {
2830 if (req() <= 2) {
2831 // Dead phi.
2832 return false;
2833 }
2834 inline_klass = nullptr;
2835
2836 // TODO 8302217 We need to prevent endless pushing through
2837 bool only_phi = (outcnt() != 0);
2838 for (DUIterator_Fast imax, i = fast_outs(imax); i < imax; i++) {
2839 Node* n = fast_out(i);
2840 if (n->is_InlineType() && n->in(1) == this) {
2841 return false;
2842 }
2843 if (!n->is_Phi()) {
2844 only_phi = false;
2845 }
2846 }
2847 if (only_phi) {
2848 return false;
2849 }
2850
2851 ResourceMark rm;
2852 Unique_Node_List worklist;
2853 worklist.push(this);
2854 Node_List casts;
2855
2856 for (uint next = 0; next < worklist.size(); next++) {
2857 Node* phi = worklist.at(next);
2858 for (uint i = 1; i < phi->req(); i++) {
2859 Node* n = phi->in(i);
2860 if (n == nullptr) {
2861 return false;
2862 }
2863 while (n->is_ConstraintCast()) {
2864 if (n->in(0) != nullptr && n->in(0)->is_top()) {
2865 // Will die, don't optimize
2866 return false;
2867 }
2868 casts.push(n);
2869 n = n->in(1);
2870 }
2871 const Type* type = phase->type(n);
2872 if (n->is_InlineType() && (inline_klass == nullptr || inline_klass == type->inline_klass())) {
2873 inline_klass = type->inline_klass();
2874 } else if (n->is_Phi() && can_reshape && n->bottom_type()->isa_ptr()) {
2875 worklist.push(n);
2876 } else if (!type->is_zero_type()) {
2877 return false;
2878 }
2879 }
2880 }
2881 if (inline_klass == nullptr) {
2882 return false;
2883 }
2884
2885 // Check if cast nodes can be pushed through
2886 const Type* t = Type::get_const_type(inline_klass);
2887 while (casts.size() != 0 && t != nullptr) {
2888 Node* cast = casts.pop();
2889 if (t->filter(cast->bottom_type()) == Type::TOP) {
2890 return false;
2891 }
2892 }
2893
2894 return true;
2895 }
2896
2897 #ifdef ASSERT
2898 bool PhiNode::can_push_inline_types_down(PhaseGVN* phase) {
2899 if (!can_be_inline_type()) {
2900 return false;
2901 }
2902
2903 ciInlineKlass* inline_klass;
2904 return can_push_inline_types_down(phase, true, inline_klass);
2905 }
2906 #endif // ASSERT
2907
2908 static int compare_types(const Type* const& e1, const Type* const& e2) {
2909 return (intptr_t)e1 - (intptr_t)e2;
2910 }
2911
2912 // Collect types at casts that are going to be eliminated at that Phi and store them in a TypeTuple.
2913 // Sort the types using an arbitrary order so a list of some types always hashes to the same TypeTuple (and TypeTuple
2914 // pointer comparison is enough to tell if 2 list of types are the same or not)
2915 const TypeTuple* PhiNode::collect_types(PhaseGVN* phase) const {
2916 const Node* region = in(0);
2917 const Type* phi_type = bottom_type();
2918 ResourceMark rm;
2919 GrowableArray<const Type*> types;
2920 for (uint i = 1; i < req(); i++) {
2921 if (region->in(i) == nullptr || phase->type(region->in(i)) == Type::TOP) {
2922 continue;
2923 }
2924 Node* in = Node::in(i);
2925 const Type* t = phase->type(in);
2926 if (in == nullptr || in == this || t == Type::TOP) {
2927 continue;
3270 #ifndef PRODUCT
3271 void CatchProjNode::dump_spec(outputStream *st) const {
3272 ProjNode::dump_spec(st);
3273 st->print("@bci %d ",_handler_bci);
3274 }
3275 #endif
3276
3277 //=============================================================================
3278 //------------------------------Identity---------------------------------------
3279 // Check for CreateEx being Identity.
3280 Node* CreateExNode::Identity(PhaseGVN* phase) {
3281 if( phase->type(in(1)) == Type::TOP ) return in(1);
3282 if( phase->type(in(0)) == Type::TOP ) return in(0);
3283 if (phase->type(in(0)->in(0)) == Type::TOP) {
3284 assert(in(0)->is_CatchProj(), "control is CatchProj");
3285 return phase->C->top(); // dead code
3286 }
3287 // We only come from CatchProj, unless the CatchProj goes away.
3288 // If the CatchProj is optimized away, then we just carry the
3289 // exception oop through.
3290
3291 // CheckCastPPNode::Ideal() for inline types reuses the exception
3292 // paths of a call to perform an allocation: we can see a Phi here.
3293 if (in(1)->is_Phi()) {
3294 return this;
3295 }
3296 CallNode *call = in(1)->in(0)->as_Call();
3297
3298 return (in(0)->is_CatchProj() && in(0)->in(0)->is_Catch() &&
3299 in(0)->in(0)->in(1) == in(1)) ? this : call->in(TypeFunc::Parms);
3300 }
3301
3302 //=============================================================================
3303 //------------------------------Value------------------------------------------
3304 // Check for being unreachable.
3305 const Type* NeverBranchNode::Value(PhaseGVN* phase) const {
3306 if (!in(0) || in(0)->is_top()) return Type::TOP;
3307 return bottom_type();
3308 }
3309
3310 //------------------------------Ideal------------------------------------------
3311 // Check for no longer being part of a loop
3312 Node *NeverBranchNode::Ideal(PhaseGVN *phase, bool can_reshape) {
3313 if (can_reshape && !in(0)->is_Region()) {
3314 // Dead code elimination can sometimes delete this projection so
3315 // if it's not there, there's nothing to do.
|