1057 t2 != nullptr && t2->isa_oopptr();
1058 }
1059 // IfNode::Ideal() -> search_identical() walks up the CFG dominator tree.
1060 // RangeCheckNode::Ideal() scans up to ~999 nodes up the chain.
1061 // CountedLoopEndNode/LongCountedLoopEndNode::Ideal() via simple_subsuming
1062 // looks for dominating test that subsumes the current test.
1063 switch (n->Opcode()) {
1064 case Op_If:
1065 case Op_RangeCheck:
1066 case Op_CountedLoopEnd:
1067 case Op_LongCountedLoopEnd:
1068 return true;
1069 default:
1070 break;
1071 }
1072 return false;
1073 }
1074
1075 bool PhaseIterGVN::drain_worklist() {
1076 uint loop_count = 1;
1077 const int max_live_nodes_increase_per_iteration = NodeLimitFudgeFactor * 3;
1078 while (_worklist.size() != 0) {
1079 if (C->check_node_count(max_live_nodes_increase_per_iteration, "Out of nodes")) {
1080 C->print_method(PHASE_AFTER_ITER_GVN, 3);
1081 return true;
1082 }
1083 Node* n = _worklist.pop();
1084 if (loop_count >= K * C->live_nodes()) {
1085 DEBUG_ONLY(dump_infinite_loop_info(n, "PhaseIterGVN::drain_worklist");)
1086 C->record_method_not_compilable("infinite loop in PhaseIterGVN::drain_worklist");
1087 C->print_method(PHASE_AFTER_ITER_GVN, 3);
1088 return true;
1089 }
1090 DEBUG_ONLY(trace_PhaseIterGVN_verbose(n, _num_processed++);)
1091 if (n->outcnt() != 0) {
1092 NOT_PRODUCT(const Type* oldtype = type_or_null(n));
1093 // Do the transformation
1094 DEBUG_ONLY(int live_nodes_before = C->live_nodes();)
1095 Node* nn = transform_old(n);
1096 DEBUG_ONLY(int live_nodes_after = C->live_nodes();)
1097 // Ensure we did not increase the live node count with more than
1313 // SubNode::Value
1314 // CmpPNode::sub
1315 // MemNode::detect_ptr_independence
1316 // MemNode::all_controls_dominate
1317 // We find all controls of a pointer load, and see if they dominate the control of
1318 // an allocation. If they all dominate, we know the allocation is after (independent)
1319 // of the pointer load, and we can say the pointers are different. For this we call
1320 // n->dominates(sub, nlist) to check if controls n of the pointer load dominate the
1321 // control sub of the allocation. The problems is that sometimes dominates answers
1322 // false conservatively, and later it can determine that it is indeed true. Loops with
1323 // Region heads can lead to giving up, whereas LoopNodes can be skipped easier, and
1324 // so the traversal becomes more powerful. This is difficult to remedy, we would have
1325 // to notify the CmpP of CFG updates. Luckily, we recompute CmpP::Value during CCP
1326 // after loop-opts, so that should take care of many of these cases.
1327 return;
1328 }
1329
1330 stringStream ss; // Print as a block without tty lock.
1331 ss.cr();
1332 ss.print_cr("Missed Value optimization:");
1333 n->dump_bfs(1, nullptr, "", &ss);
1334 ss.print_cr("Current type:");
1335 told->dump_on(&ss);
1336 ss.cr();
1337 ss.print_cr("Optimized type:");
1338 tnew->dump_on(&ss);
1339 ss.cr();
1340 tty->print_cr("%s", ss.as_string());
1341
1342 switch (_phase) {
1343 case PhaseValuesType::iter_gvn:
1344 assert(false, "Missed Value optimization opportunity in PhaseIterGVN for %s",n->Name());
1345 break;
1346 case PhaseValuesType::ccp:
1347 assert(false, "PhaseCCP not at fixpoint: analysis result may be unsound for %s", n->Name());
1348 break;
1349 default:
1350 assert(false, "Unexpected phase");
1351 break;
1352 }
1353 }
1944 if (progress != 0) {
1945 stringStream ss; // Print as a block without tty lock.
1946 ss.cr();
1947 ss.print_cr("Ideal optimization did not make progress but had side effects.");
1948 ss.print_cr(" %u transforms made progress", progress);
1949 n->dump_bfs(1, nullptr, "", &ss);
1950 tty->print_cr("%s", ss.as_string());
1951 assert(false, "Unexpected side effects from applying Ideal optimization on %s", n->Name());
1952 }
1953
1954 if (old_hash != n->hash()) {
1955 stringStream ss; // Print as a block without tty lock.
1956 ss.cr();
1957 ss.print_cr("Ideal optimization did not make progress but node hash changed.");
1958 ss.print_cr(" old_hash = %d, hash = %d", old_hash, n->hash());
1959 n->dump_bfs(1, nullptr, "", &ss);
1960 tty->print_cr("%s", ss.as_string());
1961 assert(false, "Unexpected hash change from applying Ideal optimization on %s", n->Name());
1962 }
1963
1964 verify_empty_worklist(n);
1965
1966 // Everything is good.
1967 hash_find_insert(n);
1968 return;
1969 }
1970
1971 // We just saw a new Idealization which was not done during IGVN.
1972 stringStream ss; // Print as a block without tty lock.
1973 ss.cr();
1974 ss.print_cr("Missed Ideal optimization (can_reshape=%s):", can_reshape ? "true": "false");
1975 if (i == n) {
1976 ss.print_cr("The node was reshaped by Ideal.");
1977 } else {
1978 ss.print_cr("The node was replaced by Ideal.");
1979 ss.print_cr("Old node:");
1980 n->dump_bfs(1, nullptr, "", &ss);
1981 }
1982 ss.print_cr("The result after Ideal:");
1983 i->dump_bfs(1, nullptr, "", &ss);
2158 assert(false, "Broken node invariant for %s", n->Name());
2159 }
2160 }
2161 }
2162 #endif
2163
2164 /**
2165 * Register a new node with the optimizer. Update the types array, the def-use
2166 * info. Put on worklist.
2167 */
2168 Node* PhaseIterGVN::register_new_node_with_optimizer(Node* n, Node* orig) {
2169 set_type_bottom(n);
2170 _worklist.push(n);
2171 if (orig != nullptr) C->copy_node_notes_to(n, orig);
2172 return n;
2173 }
2174
2175 //------------------------------transform--------------------------------------
2176 // Non-recursive: idealize Node 'n' with respect to its inputs and its value
2177 Node *PhaseIterGVN::transform( Node *n ) {
2178 if (_delay_transform) {
2179 // Register the node but don't optimize for now
2180 register_new_node_with_optimizer(n);
2181 return n;
2182 }
2183
2184 // If brand new node, make space in type array, and give it a type.
2185 ensure_type_or_null(n);
2186 if (type_or_null(n) == nullptr) {
2187 set_type_bottom(n);
2188 }
2189
2190 return transform_old(n);
2191 }
2192
2193 Node *PhaseIterGVN::transform_old(Node* n) {
2194 NOT_PRODUCT(set_transforms());
2195 // Remove 'n' from hash table in case it gets modified
2196 _table.hash_delete(n);
2197 #ifdef ASSERT
2198 if (is_verify_def_use()) {
2199 assert(!_table.find_index(n->_idx), "found duplicate entry in table");
2200 }
2201 #endif
2202
2203 // Allow Bool -> Cmp idealisation in late inlining intrinsics that return a bool
2204 if (n->is_Cmp()) {
2205 add_users_to_worklist(n);
2206 }
2207
2208 // Apply the Ideal call in a loop until it no longer applies
2209 Node* k = n;
2452
2453 // Smash all inputs to 'old', isolating him completely
2454 Node *temp = new Node(1);
2455 temp->init_req(0,nn); // Add a use to nn to prevent him from dying
2456 remove_dead_node(old, NodeOrigin::Graph);
2457 temp->del_req(0); // Yank bogus edge
2458 if (nn != nullptr && nn->outcnt() == 0) {
2459 _worklist.push(nn);
2460 }
2461 #ifndef PRODUCT
2462 if (is_verify_def_use()) {
2463 for ( int i = 0; i < _verify_window_size; i++ ) {
2464 if ( _verify_window[i] == old )
2465 _verify_window[i] = nn;
2466 }
2467 }
2468 #endif
2469 temp->destruct(this); // reuse the _idx of this little guy
2470 }
2471
2472 //------------------------------add_users_to_worklist--------------------------
2473 void PhaseIterGVN::add_users_to_worklist0(Node* n, Unique_Node_List& worklist) {
2474 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
2475 worklist.push(n->fast_out(i)); // Push on worklist
2476 }
2477 }
2478
2479 // Return counted loop Phi if as a counted loop exit condition, cmp
2480 // compares the induction variable with n
2481 static PhiNode* countedloop_phi_from_cmp(CmpNode* cmp, Node* n) {
2482 for (DUIterator_Fast imax, i = cmp->fast_outs(imax); i < imax; i++) {
2483 Node* bol = cmp->fast_out(i);
2484 for (DUIterator_Fast i2max, i2 = bol->fast_outs(i2max); i2 < i2max; i2++) {
2485 Node* iff = bol->fast_out(i2);
2486 if (iff->is_BaseCountedLoopEnd()) {
2487 BaseCountedLoopEndNode* cle = iff->as_BaseCountedLoopEnd();
2488 if (cle->limit() == n) {
2489 PhiNode* phi = cle->phi();
2490 if (phi != nullptr) {
2491 return phi;
2507 add_users_of_use_to_worklist(n, use, worklist);
2508 }
2509 }
2510
2511 void PhaseIterGVN::add_users_of_use_to_worklist(Node* n, Node* use, Unique_Node_List& worklist) {
2512 if(use->is_Multi() || // Multi-definer? Push projs on worklist
2513 use->is_Store() ) // Enable store/load same address
2514 add_users_to_worklist0(use, worklist);
2515
2516 // If we changed the receiver type to a call, we need to revisit
2517 // the Catch following the call. It's looking for a non-null
2518 // receiver to know when to enable the regular fall-through path
2519 // in addition to the NullPtrException path.
2520 if (use->is_CallDynamicJava() && n == use->in(TypeFunc::Parms)) {
2521 Node* p = use->as_CallDynamicJava()->proj_out_or_null(TypeFunc::Control);
2522 if (p != nullptr) {
2523 add_users_to_worklist0(p, worklist);
2524 }
2525 }
2526
2527 uint use_op = use->Opcode();
2528 if(use->is_Cmp()) { // Enable CMP/BOOL optimization
2529 add_users_to_worklist0(use, worklist); // Put Bool on worklist
2530 if (use->outcnt() > 0) {
2531 Node* bol = use->raw_out(0);
2532 if (bol->outcnt() > 0) {
2533 Node* iff = bol->raw_out(0);
2534 if (iff->outcnt() == 2) {
2535 // Look for the 'is_x2logic' pattern: "x ? : 0 : 1" and put the
2536 // phi merging either 0 or 1 onto the worklist
2537 Node* ifproj0 = iff->raw_out(0);
2538 Node* ifproj1 = iff->raw_out(1);
2539 if (ifproj0->outcnt() > 0 && ifproj1->outcnt() > 0) {
2540 Node* region0 = ifproj0->raw_out(0);
2541 Node* region1 = ifproj1->raw_out(0);
2542 if( region0 == region1 )
2543 add_users_to_worklist0(region0, worklist);
2544 }
2545 }
2546 }
2604 assert(n == in2, "only in2 modified");
2605 // Find all CastII with input in1.
2606 for (DUIterator_Fast jmax, j = in1->fast_outs(jmax); j < jmax; j++) {
2607 Node* castii = in1->fast_out(j);
2608 if (castii->is_CastII() && castii->as_CastII()->carry_dependency()) {
2609 // Find If.
2610 if (castii->in(0) != nullptr && castii->in(0)->in(0) != nullptr && castii->in(0)->in(0)->is_If()) {
2611 Node* ifnode = castii->in(0)->in(0);
2612 // Check that if connects to the cmp
2613 if (ifnode->in(1) != nullptr && ifnode->in(1)->is_Bool() && ifnode->in(1)->in(1) == cmp) {
2614 worklist.push(castii);
2615 }
2616 }
2617 }
2618 }
2619 }
2620 }
2621 }
2622 }
2623
2624 // If changed Cast input, notify down for Phi, Sub, and Xor - all do "uncast"
2625 // Patterns:
2626 // ConstraintCast+ -> Sub
2627 // ConstraintCast+ -> Phi
2628 // ConstraintCast+ -> Xor
2629 if (use->is_ConstraintCast()) {
2630 auto push_the_uses_to_worklist = [&](Node* n){
2631 if (n->is_Phi() || n->is_Sub() || n->Opcode() == Op_XorI || n->Opcode() == Op_XorL) {
2632 worklist.push(n);
2633 }
2634 };
2635 auto is_boundary = [](Node* n){ return !n->is_ConstraintCast(); };
2636 use->visit_uses(push_the_uses_to_worklist, is_boundary);
2637 }
2638 // If changed LShift inputs, check RShift/URShift users for
2639 // "(X << C) >> C" sign-ext and "(X << C) >>> C" zero-ext optimizations.
2640 if (use_op == Op_LShiftI || use_op == Op_LShiftL) {
2641 add_users_to_worklist_if(worklist, use, [](Node* u) {
2642 return u->Opcode() == Op_RShiftI || u->Opcode() == Op_RShiftL ||
2643 u->Opcode() == Op_URShiftI || u->Opcode() == Op_URShiftL;
2745 // If the ValidLengthTest input changes then the fallthrough path out of the AllocateArray may have become dead.
2746 // CatchNode::Value() is responsible for killing that path. The CatchNode has to be explicitly enqueued for igvn
2747 // to guarantee the change is not missed.
2748 if (use_op == Op_AllocateArray && n == use->in(AllocateNode::ValidLengthTest)) {
2749 Node* p = use->as_AllocateArray()->proj_out_or_null(TypeFunc::Control);
2750 if (p != nullptr) {
2751 add_users_to_worklist0(p, worklist);
2752 }
2753 }
2754
2755 if (use_op == Op_Initialize) {
2756 InitializeNode* init = use->as_Initialize();
2757 init->for_each_proj(enqueue_init_mem_projs, TypeFunc::Memory);
2758 }
2759 // Loading the java mirror from a Klass requires two loads and the type
2760 // of the mirror load depends on the type of 'n'. See LoadNode::Value().
2761 // LoadBarrier?(LoadP(LoadP(AddP(foo:Klass, #java_mirror))))
2762 BarrierSetC2* bs = BarrierSet::barrier_set()->barrier_set_c2();
2763 bool has_load_barrier_nodes = bs->has_load_barrier_nodes();
2764
2765 if (use_op == Op_LoadP && use->bottom_type()->isa_rawptr()) {
2766 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2767 Node* u = use->fast_out(i2);
2768 const Type* ut = u->bottom_type();
2769 if (u->Opcode() == Op_LoadP && ut->isa_instptr()) {
2770 if (has_load_barrier_nodes) {
2771 // Search for load barriers behind the load
2772 add_users_to_worklist_if(worklist, u, [&](Node* b) {
2773 return bs->is_gc_barrier_node(b);
2774 });
2775 }
2776 worklist.push(u);
2777 }
2778 }
2779 }
2780 if (use->Opcode() == Op_OpaqueZeroTripGuard) {
2781 assert(use->outcnt() <= 1, "OpaqueZeroTripGuard can't be shared");
2782 if (use->outcnt() == 1) {
2783 Node* cmp = use->unique_out();
2784 worklist.push(cmp);
2785 }
2786 }
2787 // VectorMaskToLongNode::Ideal_MaskAll looks through VectorStoreMask
2788 // to fold constant masks.
2789 if (use_op == Op_VectorStoreMask) {
2790 add_users_to_worklist_if(worklist, use, [](Node* u) { return u->Opcode() == Op_VectorMaskToLong; });
2791 }
2792
2793 // From CastX2PNode::Ideal
2794 // CastX2P(AddX(x, y))
2795 // CastX2P(SubX(x, y))
2796 if (use->Opcode() == Op_AddX || use->Opcode() == Op_SubX) {
2797 add_users_to_worklist_if(worklist, use, [](Node* u) { return u->Opcode() == Op_CastX2P; });
2798 }
2799
2856 // Conditional Constant Propagation, ala Wegman & Zadeck
2857 PhaseCCP::PhaseCCP( PhaseIterGVN *igvn ) : PhaseIterGVN(igvn) {
2858 NOT_PRODUCT( clear_constants(); )
2859 assert( _worklist.size() == 0, "" );
2860 _phase = PhaseValuesType::ccp;
2861 analyze();
2862 }
2863
2864 #ifndef PRODUCT
2865 //------------------------------~PhaseCCP--------------------------------------
2866 PhaseCCP::~PhaseCCP() {
2867 inc_invokes();
2868 _total_constants += count_constants();
2869 }
2870 #endif
2871
2872
2873 #ifdef ASSERT
2874 void PhaseCCP::verify_type(Node* n, const Type* tnew, const Type* told) {
2875 if (tnew->meet(told) != tnew->remove_speculative()) {
2876 n->dump(1);
2877 tty->print("told = "); told->dump(); tty->cr();
2878 tty->print("tnew = "); tnew->dump(); tty->cr();
2879 fatal("Not monotonic");
2880 }
2881 assert(!told->isa_int() || !tnew->isa_int() || told->is_int()->_widen <= tnew->is_int()->_widen, "widen increases");
2882 assert(!told->isa_long() || !tnew->isa_long() || told->is_long()->_widen <= tnew->is_long()->_widen, "widen increases");
2883 }
2884 #endif //ASSERT
2885
2886 // In this analysis, all types are initially set to TOP. We iteratively call Value() on all nodes of the graph until
2887 // we reach a fixed-point (i.e. no types change anymore). We start with a list that only contains the root node. Each time
2888 // a new type is set, we push all uses of that node back to the worklist (in some cases, we also push grandchildren
2889 // or nodes even further down back to the worklist because their type could change as a result of the current type
2890 // change).
2891 void PhaseCCP::analyze() {
2892 // Initialize all types to TOP, optimistic analysis
2893 for (uint i = 0; i < C->unique(); i++) {
2894 _types.map(i, Type::TOP);
2895 }
2896
3025 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
3026 Node* use = n->fast_out(i);
3027 push_if_not_bottom_type(worklist, use);
3028 push_more_uses(worklist, n, use);
3029 }
3030 }
3031
3032 void PhaseCCP::push_if_not_bottom_type(Unique_Node_List& worklist, Node* n) const {
3033 if (not_bottom_type(n)) {
3034 worklist.push(n);
3035 }
3036 }
3037
3038 // For some nodes, we need to propagate the type change to grandchildren or even further down.
3039 // Add them back to the worklist.
3040 void PhaseCCP::push_more_uses(Unique_Node_List& worklist, Node* parent, const Node* use) const {
3041 push_phis(worklist, use);
3042 push_catch(worklist, use);
3043 push_cmpu(worklist, use);
3044 push_counted_loop_phi(worklist, parent, use);
3045 push_loadp(worklist, use);
3046 push_and(worklist, parent, use);
3047 push_cast_ii(worklist, parent, use);
3048 push_opaque_zero_trip_guard(worklist, use);
3049 push_bool_with_cmpu_and_mask(worklist, use);
3050 }
3051
3052
3053 // We must recheck Phis too if use is a Region.
3054 void PhaseCCP::push_phis(Unique_Node_List& worklist, const Node* use) const {
3055 if (use->is_Region()) {
3056 add_users_to_worklist_if(worklist, use, [&](Node* u) {
3057 return not_bottom_type(u);
3058 });
3059 }
3060 }
3061
3062 // If we changed the receiver type to a call, we need to revisit the Catch node following the call. It's looking for a
3063 // non-null receiver to know when to enable the regular fall-through path in addition to the NullPtrException path.
3064 // Same is true if the type of a ValidLengthTest input to an AllocateArrayNode changes.
3136 Node* m = addI->in(1);
3137 if (m == andI->in(1) || m == andI->in(2)) {
3138 // Is "m" shared? Matched (1b) and thus we revisit Bool.
3139 push_if_not_bottom_type(worklist, bol);
3140 }
3141 }
3142 }
3143
3144 // If n is used in a counted loop exit condition, then the type of the counted loop's Phi depends on the type of 'n'.
3145 // Seem PhiNode::Value().
3146 void PhaseCCP::push_counted_loop_phi(Unique_Node_List& worklist, Node* parent, const Node* use) {
3147 uint use_op = use->Opcode();
3148 if (use_op == Op_CmpI || use_op == Op_CmpL) {
3149 PhiNode* phi = countedloop_phi_from_cmp(use->as_Cmp(), parent);
3150 if (phi != nullptr) {
3151 worklist.push(phi);
3152 }
3153 }
3154 }
3155
3156 // Loading the java mirror from a Klass requires two loads and the type of the mirror load depends on the type of 'n'.
3157 // See LoadNode::Value().
3158 void PhaseCCP::push_loadp(Unique_Node_List& worklist, const Node* use) const {
3159 BarrierSetC2* barrier_set = BarrierSet::barrier_set()->barrier_set_c2();
3160 bool has_load_barrier_nodes = barrier_set->has_load_barrier_nodes();
3161
3162 if (use->Opcode() == Op_LoadP && use->bottom_type()->isa_rawptr()) {
3163 for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
3164 Node* loadp = use->fast_out(i);
3165 const Type* ut = loadp->bottom_type();
3166 if (loadp->Opcode() == Op_LoadP && ut->isa_instptr() && ut != type(loadp)) {
3167 if (has_load_barrier_nodes) {
3168 // Search for load barriers behind the load
3169 push_load_barrier(worklist, barrier_set, loadp);
3170 }
3171 worklist.push(loadp);
3172 }
3173 }
3174 }
3175 }
|
1057 t2 != nullptr && t2->isa_oopptr();
1058 }
1059 // IfNode::Ideal() -> search_identical() walks up the CFG dominator tree.
1060 // RangeCheckNode::Ideal() scans up to ~999 nodes up the chain.
1061 // CountedLoopEndNode/LongCountedLoopEndNode::Ideal() via simple_subsuming
1062 // looks for dominating test that subsumes the current test.
1063 switch (n->Opcode()) {
1064 case Op_If:
1065 case Op_RangeCheck:
1066 case Op_CountedLoopEnd:
1067 case Op_LongCountedLoopEnd:
1068 return true;
1069 default:
1070 break;
1071 }
1072 return false;
1073 }
1074
1075 bool PhaseIterGVN::drain_worklist() {
1076 uint loop_count = 1;
1077 const int max_live_nodes_increase_per_iteration = NodeLimitFudgeFactor * 5;
1078 while (_worklist.size() != 0) {
1079 if (C->check_node_count(max_live_nodes_increase_per_iteration, "Out of nodes")) {
1080 C->print_method(PHASE_AFTER_ITER_GVN, 3);
1081 return true;
1082 }
1083 Node* n = _worklist.pop();
1084 if (loop_count >= K * C->live_nodes()) {
1085 DEBUG_ONLY(dump_infinite_loop_info(n, "PhaseIterGVN::drain_worklist");)
1086 C->record_method_not_compilable("infinite loop in PhaseIterGVN::drain_worklist");
1087 C->print_method(PHASE_AFTER_ITER_GVN, 3);
1088 return true;
1089 }
1090 DEBUG_ONLY(trace_PhaseIterGVN_verbose(n, _num_processed++);)
1091 if (n->outcnt() != 0) {
1092 NOT_PRODUCT(const Type* oldtype = type_or_null(n));
1093 // Do the transformation
1094 DEBUG_ONLY(int live_nodes_before = C->live_nodes();)
1095 Node* nn = transform_old(n);
1096 DEBUG_ONLY(int live_nodes_after = C->live_nodes();)
1097 // Ensure we did not increase the live node count with more than
1313 // SubNode::Value
1314 // CmpPNode::sub
1315 // MemNode::detect_ptr_independence
1316 // MemNode::all_controls_dominate
1317 // We find all controls of a pointer load, and see if they dominate the control of
1318 // an allocation. If they all dominate, we know the allocation is after (independent)
1319 // of the pointer load, and we can say the pointers are different. For this we call
1320 // n->dominates(sub, nlist) to check if controls n of the pointer load dominate the
1321 // control sub of the allocation. The problems is that sometimes dominates answers
1322 // false conservatively, and later it can determine that it is indeed true. Loops with
1323 // Region heads can lead to giving up, whereas LoopNodes can be skipped easier, and
1324 // so the traversal becomes more powerful. This is difficult to remedy, we would have
1325 // to notify the CmpP of CFG updates. Luckily, we recompute CmpP::Value during CCP
1326 // after loop-opts, so that should take care of many of these cases.
1327 return;
1328 }
1329
1330 stringStream ss; // Print as a block without tty lock.
1331 ss.cr();
1332 ss.print_cr("Missed Value optimization:");
1333 n->dump_bfs(3, nullptr, "", &ss);
1334 ss.print_cr("Current type:");
1335 told->dump_on(&ss);
1336 ss.cr();
1337 ss.print_cr("Optimized type:");
1338 tnew->dump_on(&ss);
1339 ss.cr();
1340 tty->print_cr("%s", ss.as_string());
1341
1342 switch (_phase) {
1343 case PhaseValuesType::iter_gvn:
1344 assert(false, "Missed Value optimization opportunity in PhaseIterGVN for %s",n->Name());
1345 break;
1346 case PhaseValuesType::ccp:
1347 assert(false, "PhaseCCP not at fixpoint: analysis result may be unsound for %s", n->Name());
1348 break;
1349 default:
1350 assert(false, "Unexpected phase");
1351 break;
1352 }
1353 }
1944 if (progress != 0) {
1945 stringStream ss; // Print as a block without tty lock.
1946 ss.cr();
1947 ss.print_cr("Ideal optimization did not make progress but had side effects.");
1948 ss.print_cr(" %u transforms made progress", progress);
1949 n->dump_bfs(1, nullptr, "", &ss);
1950 tty->print_cr("%s", ss.as_string());
1951 assert(false, "Unexpected side effects from applying Ideal optimization on %s", n->Name());
1952 }
1953
1954 if (old_hash != n->hash()) {
1955 stringStream ss; // Print as a block without tty lock.
1956 ss.cr();
1957 ss.print_cr("Ideal optimization did not make progress but node hash changed.");
1958 ss.print_cr(" old_hash = %d, hash = %d", old_hash, n->hash());
1959 n->dump_bfs(1, nullptr, "", &ss);
1960 tty->print_cr("%s", ss.as_string());
1961 assert(false, "Unexpected hash change from applying Ideal optimization on %s", n->Name());
1962 }
1963
1964 // Some nodes try to push itself back to the worklist if can_reshape is
1965 // false
1966 if (!can_reshape && _worklist.size() > 0 && _worklist.pop() != n) {
1967 stringStream ss;
1968 ss.cr();
1969 ss.print_cr("Previously optimized:");
1970 n->dump_bfs(1, nullptr, "", &ss);
1971 tty->print_cr("%s", ss.as_string());
1972 assert(false, "should only push itself on worklist");
1973 }
1974 verify_empty_worklist(n);
1975
1976 // Everything is good.
1977 hash_find_insert(n);
1978 return;
1979 }
1980
1981 // We just saw a new Idealization which was not done during IGVN.
1982 stringStream ss; // Print as a block without tty lock.
1983 ss.cr();
1984 ss.print_cr("Missed Ideal optimization (can_reshape=%s):", can_reshape ? "true": "false");
1985 if (i == n) {
1986 ss.print_cr("The node was reshaped by Ideal.");
1987 } else {
1988 ss.print_cr("The node was replaced by Ideal.");
1989 ss.print_cr("Old node:");
1990 n->dump_bfs(1, nullptr, "", &ss);
1991 }
1992 ss.print_cr("The result after Ideal:");
1993 i->dump_bfs(1, nullptr, "", &ss);
2168 assert(false, "Broken node invariant for %s", n->Name());
2169 }
2170 }
2171 }
2172 #endif
2173
2174 /**
2175 * Register a new node with the optimizer. Update the types array, the def-use
2176 * info. Put on worklist.
2177 */
2178 Node* PhaseIterGVN::register_new_node_with_optimizer(Node* n, Node* orig) {
2179 set_type_bottom(n);
2180 _worklist.push(n);
2181 if (orig != nullptr) C->copy_node_notes_to(n, orig);
2182 return n;
2183 }
2184
2185 //------------------------------transform--------------------------------------
2186 // Non-recursive: idealize Node 'n' with respect to its inputs and its value
2187 Node *PhaseIterGVN::transform( Node *n ) {
2188 // If brand new node, make space in type array, and give it a type.
2189 ensure_type_or_null(n);
2190 if (type_or_null(n) == nullptr) {
2191 set_type_bottom(n);
2192 }
2193
2194 if (_delay_transform) {
2195 // Add the node to the worklist but don't optimize for now
2196 _worklist.push(n);
2197 return n;
2198 }
2199
2200 return transform_old(n);
2201 }
2202
2203 Node *PhaseIterGVN::transform_old(Node* n) {
2204 NOT_PRODUCT(set_transforms());
2205 // Remove 'n' from hash table in case it gets modified
2206 _table.hash_delete(n);
2207 #ifdef ASSERT
2208 if (is_verify_def_use()) {
2209 assert(!_table.find_index(n->_idx), "found duplicate entry in table");
2210 }
2211 #endif
2212
2213 // Allow Bool -> Cmp idealisation in late inlining intrinsics that return a bool
2214 if (n->is_Cmp()) {
2215 add_users_to_worklist(n);
2216 }
2217
2218 // Apply the Ideal call in a loop until it no longer applies
2219 Node* k = n;
2462
2463 // Smash all inputs to 'old', isolating him completely
2464 Node *temp = new Node(1);
2465 temp->init_req(0,nn); // Add a use to nn to prevent him from dying
2466 remove_dead_node(old, NodeOrigin::Graph);
2467 temp->del_req(0); // Yank bogus edge
2468 if (nn != nullptr && nn->outcnt() == 0) {
2469 _worklist.push(nn);
2470 }
2471 #ifndef PRODUCT
2472 if (is_verify_def_use()) {
2473 for ( int i = 0; i < _verify_window_size; i++ ) {
2474 if ( _verify_window[i] == old )
2475 _verify_window[i] = nn;
2476 }
2477 }
2478 #endif
2479 temp->destruct(this); // reuse the _idx of this little guy
2480 }
2481
2482 void PhaseIterGVN::replace_in_uses(Node* n, Node* m) {
2483 assert(n != nullptr, "sanity");
2484 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
2485 Node* u = n->fast_out(i);
2486 if (u != n) {
2487 rehash_node_delayed(u);
2488 int nb = u->replace_edge(n, m);
2489 --i, imax -= nb;
2490 }
2491 }
2492 assert(n->outcnt() == 0, "all uses must be deleted");
2493 }
2494
2495 //------------------------------add_users_to_worklist--------------------------
2496 void PhaseIterGVN::add_users_to_worklist0(Node* n, Unique_Node_List& worklist) {
2497 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
2498 worklist.push(n->fast_out(i)); // Push on worklist
2499 }
2500 }
2501
2502 // Return counted loop Phi if as a counted loop exit condition, cmp
2503 // compares the induction variable with n
2504 static PhiNode* countedloop_phi_from_cmp(CmpNode* cmp, Node* n) {
2505 for (DUIterator_Fast imax, i = cmp->fast_outs(imax); i < imax; i++) {
2506 Node* bol = cmp->fast_out(i);
2507 for (DUIterator_Fast i2max, i2 = bol->fast_outs(i2max); i2 < i2max; i2++) {
2508 Node* iff = bol->fast_out(i2);
2509 if (iff->is_BaseCountedLoopEnd()) {
2510 BaseCountedLoopEndNode* cle = iff->as_BaseCountedLoopEnd();
2511 if (cle->limit() == n) {
2512 PhiNode* phi = cle->phi();
2513 if (phi != nullptr) {
2514 return phi;
2530 add_users_of_use_to_worklist(n, use, worklist);
2531 }
2532 }
2533
2534 void PhaseIterGVN::add_users_of_use_to_worklist(Node* n, Node* use, Unique_Node_List& worklist) {
2535 if(use->is_Multi() || // Multi-definer? Push projs on worklist
2536 use->is_Store() ) // Enable store/load same address
2537 add_users_to_worklist0(use, worklist);
2538
2539 // If we changed the receiver type to a call, we need to revisit
2540 // the Catch following the call. It's looking for a non-null
2541 // receiver to know when to enable the regular fall-through path
2542 // in addition to the NullPtrException path.
2543 if (use->is_CallDynamicJava() && n == use->in(TypeFunc::Parms)) {
2544 Node* p = use->as_CallDynamicJava()->proj_out_or_null(TypeFunc::Control);
2545 if (p != nullptr) {
2546 add_users_to_worklist0(p, worklist);
2547 }
2548 }
2549
2550 // AndLNode::Ideal folds GraphKit::mark_word_test patterns. Give it a chance to run.
2551 if (n->is_Load() && use->is_Phi()) {
2552 for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
2553 Node* u = use->fast_out(i);
2554 if (u->Opcode() == Op_AndL) {
2555 worklist.push(u);
2556 }
2557 }
2558 }
2559
2560 uint use_op = use->Opcode();
2561 if(use->is_Cmp()) { // Enable CMP/BOOL optimization
2562 add_users_to_worklist0(use, worklist); // Put Bool on worklist
2563 if (use->outcnt() > 0) {
2564 Node* bol = use->raw_out(0);
2565 if (bol->outcnt() > 0) {
2566 Node* iff = bol->raw_out(0);
2567 if (iff->outcnt() == 2) {
2568 // Look for the 'is_x2logic' pattern: "x ? : 0 : 1" and put the
2569 // phi merging either 0 or 1 onto the worklist
2570 Node* ifproj0 = iff->raw_out(0);
2571 Node* ifproj1 = iff->raw_out(1);
2572 if (ifproj0->outcnt() > 0 && ifproj1->outcnt() > 0) {
2573 Node* region0 = ifproj0->raw_out(0);
2574 Node* region1 = ifproj1->raw_out(0);
2575 if( region0 == region1 )
2576 add_users_to_worklist0(region0, worklist);
2577 }
2578 }
2579 }
2637 assert(n == in2, "only in2 modified");
2638 // Find all CastII with input in1.
2639 for (DUIterator_Fast jmax, j = in1->fast_outs(jmax); j < jmax; j++) {
2640 Node* castii = in1->fast_out(j);
2641 if (castii->is_CastII() && castii->as_CastII()->carry_dependency()) {
2642 // Find If.
2643 if (castii->in(0) != nullptr && castii->in(0)->in(0) != nullptr && castii->in(0)->in(0)->is_If()) {
2644 Node* ifnode = castii->in(0)->in(0);
2645 // Check that if connects to the cmp
2646 if (ifnode->in(1) != nullptr && ifnode->in(1)->is_Bool() && ifnode->in(1)->in(1) == cmp) {
2647 worklist.push(castii);
2648 }
2649 }
2650 }
2651 }
2652 }
2653 }
2654 }
2655 }
2656
2657 // Inline type nodes can have other inline types as users. If an input gets
2658 // updated, make sure that inline type users get a chance for optimization.
2659 if (use->is_InlineType() || use->is_DecodeN()) {
2660 auto push_the_uses_to_worklist = [&](Node* n){
2661 if (n->is_InlineType()) {
2662 worklist.push(n);
2663 }
2664 };
2665 auto is_boundary = [](Node* n){ return !n->is_InlineType(); };
2666 use->visit_uses(push_the_uses_to_worklist, is_boundary, true);
2667 }
2668 // If changed Cast input, notify down for Phi, Sub, and Xor - all do "uncast"
2669 // Patterns:
2670 // ConstraintCast+ -> Sub
2671 // ConstraintCast+ -> Phi
2672 // ConstraintCast+ -> Xor
2673 if (use->is_ConstraintCast()) {
2674 auto push_the_uses_to_worklist = [&](Node* n){
2675 if (n->is_Phi() || n->is_Sub() || n->Opcode() == Op_XorI || n->Opcode() == Op_XorL) {
2676 worklist.push(n);
2677 }
2678 };
2679 auto is_boundary = [](Node* n){ return !n->is_ConstraintCast(); };
2680 use->visit_uses(push_the_uses_to_worklist, is_boundary);
2681 }
2682 // If changed LShift inputs, check RShift/URShift users for
2683 // "(X << C) >> C" sign-ext and "(X << C) >>> C" zero-ext optimizations.
2684 if (use_op == Op_LShiftI || use_op == Op_LShiftL) {
2685 add_users_to_worklist_if(worklist, use, [](Node* u) {
2686 return u->Opcode() == Op_RShiftI || u->Opcode() == Op_RShiftL ||
2687 u->Opcode() == Op_URShiftI || u->Opcode() == Op_URShiftL;
2789 // If the ValidLengthTest input changes then the fallthrough path out of the AllocateArray may have become dead.
2790 // CatchNode::Value() is responsible for killing that path. The CatchNode has to be explicitly enqueued for igvn
2791 // to guarantee the change is not missed.
2792 if (use_op == Op_AllocateArray && n == use->in(AllocateNode::ValidLengthTest)) {
2793 Node* p = use->as_AllocateArray()->proj_out_or_null(TypeFunc::Control);
2794 if (p != nullptr) {
2795 add_users_to_worklist0(p, worklist);
2796 }
2797 }
2798
2799 if (use_op == Op_Initialize) {
2800 InitializeNode* init = use->as_Initialize();
2801 init->for_each_proj(enqueue_init_mem_projs, TypeFunc::Memory);
2802 }
2803 // Loading the java mirror from a Klass requires two loads and the type
2804 // of the mirror load depends on the type of 'n'. See LoadNode::Value().
2805 // LoadBarrier?(LoadP(LoadP(AddP(foo:Klass, #java_mirror))))
2806 BarrierSetC2* bs = BarrierSet::barrier_set()->barrier_set_c2();
2807 bool has_load_barrier_nodes = bs->has_load_barrier_nodes();
2808
2809 if (use_op == Op_CastP2X) {
2810 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2811 Node* u = use->fast_out(i2);
2812 // TODO 8350865 Still needed? Yes, I think this is from PhaseMacroExpand::expand_mh_intrinsic_return
2813 if (u->Opcode() == Op_AndX) {
2814 worklist.push(u);
2815 }
2816 // Search for CmpL(OrL(CastP2X(..), CastP2X(..)), 0L)
2817 if (u->Opcode() == Op_OrL) {
2818 for (DUIterator_Fast i3max, i3 = u->fast_outs(i3max); i3 < i3max; i3++) {
2819 Node* cmp = u->fast_out(i3);
2820 if (cmp->Opcode() == Op_CmpL) {
2821 worklist.push(cmp);
2822 }
2823 }
2824 }
2825 }
2826 }
2827 if (use_op == Op_LoadP && use->bottom_type()->isa_rawptr()) {
2828 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2829 Node* u = use->fast_out(i2);
2830 const Type* ut = u->bottom_type();
2831 if (u->Opcode() == Op_LoadP && ut->isa_instptr()) {
2832 if (has_load_barrier_nodes) {
2833 // Search for load barriers behind the load
2834 add_users_to_worklist_if(worklist, u, [&](Node* b) {
2835 return bs->is_gc_barrier_node(b);
2836 });
2837 }
2838 worklist.push(u);
2839 }
2840 }
2841 }
2842 // Give CallStaticJavaNode::remove_useless_allocation a chance to run
2843 if (use->is_Region()) {
2844 Node* c = use;
2845 do {
2846 c = c->unique_ctrl_out_or_null();
2847 } while (c != nullptr && c->is_Region());
2848 if (c != nullptr && c->is_CallStaticJava() && c->as_CallStaticJava()->uncommon_trap_request() != 0) {
2849 worklist.push(c);
2850 }
2851 }
2852 if (use->Opcode() == Op_OpaqueZeroTripGuard) {
2853 assert(use->outcnt() <= 1, "OpaqueZeroTripGuard can't be shared");
2854 if (use->outcnt() == 1) {
2855 Node* cmp = use->unique_out();
2856 worklist.push(cmp);
2857 }
2858 }
2859 // VectorMaskToLongNode::Ideal_MaskAll looks through VectorStoreMask
2860 // to fold constant masks.
2861 if (use_op == Op_VectorStoreMask) {
2862 add_users_to_worklist_if(worklist, use, [](Node* u) { return u->Opcode() == Op_VectorMaskToLong; });
2863 }
2864
2865 // From CastX2PNode::Ideal
2866 // CastX2P(AddX(x, y))
2867 // CastX2P(SubX(x, y))
2868 if (use->Opcode() == Op_AddX || use->Opcode() == Op_SubX) {
2869 add_users_to_worklist_if(worklist, use, [](Node* u) { return u->Opcode() == Op_CastX2P; });
2870 }
2871
2928 // Conditional Constant Propagation, ala Wegman & Zadeck
2929 PhaseCCP::PhaseCCP( PhaseIterGVN *igvn ) : PhaseIterGVN(igvn) {
2930 NOT_PRODUCT( clear_constants(); )
2931 assert( _worklist.size() == 0, "" );
2932 _phase = PhaseValuesType::ccp;
2933 analyze();
2934 }
2935
2936 #ifndef PRODUCT
2937 //------------------------------~PhaseCCP--------------------------------------
2938 PhaseCCP::~PhaseCCP() {
2939 inc_invokes();
2940 _total_constants += count_constants();
2941 }
2942 #endif
2943
2944
2945 #ifdef ASSERT
2946 void PhaseCCP::verify_type(Node* n, const Type* tnew, const Type* told) {
2947 if (tnew->meet(told) != tnew->remove_speculative()) {
2948 n->dump(3);
2949 tty->print("told = "); told->dump(); tty->cr();
2950 tty->print("tnew = "); tnew->dump(); tty->cr();
2951 fatal("Not monotonic");
2952 }
2953 assert(!told->isa_int() || !tnew->isa_int() || told->is_int()->_widen <= tnew->is_int()->_widen, "widen increases");
2954 assert(!told->isa_long() || !tnew->isa_long() || told->is_long()->_widen <= tnew->is_long()->_widen, "widen increases");
2955 }
2956 #endif //ASSERT
2957
2958 // In this analysis, all types are initially set to TOP. We iteratively call Value() on all nodes of the graph until
2959 // we reach a fixed-point (i.e. no types change anymore). We start with a list that only contains the root node. Each time
2960 // a new type is set, we push all uses of that node back to the worklist (in some cases, we also push grandchildren
2961 // or nodes even further down back to the worklist because their type could change as a result of the current type
2962 // change).
2963 void PhaseCCP::analyze() {
2964 // Initialize all types to TOP, optimistic analysis
2965 for (uint i = 0; i < C->unique(); i++) {
2966 _types.map(i, Type::TOP);
2967 }
2968
3097 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
3098 Node* use = n->fast_out(i);
3099 push_if_not_bottom_type(worklist, use);
3100 push_more_uses(worklist, n, use);
3101 }
3102 }
3103
3104 void PhaseCCP::push_if_not_bottom_type(Unique_Node_List& worklist, Node* n) const {
3105 if (not_bottom_type(n)) {
3106 worklist.push(n);
3107 }
3108 }
3109
3110 // For some nodes, we need to propagate the type change to grandchildren or even further down.
3111 // Add them back to the worklist.
3112 void PhaseCCP::push_more_uses(Unique_Node_List& worklist, Node* parent, const Node* use) const {
3113 push_phis(worklist, use);
3114 push_catch(worklist, use);
3115 push_cmpu(worklist, use);
3116 push_counted_loop_phi(worklist, parent, use);
3117 push_cast(worklist, use);
3118 push_loadp(worklist, use);
3119 push_and(worklist, parent, use);
3120 push_cast_ii(worklist, parent, use);
3121 push_opaque_zero_trip_guard(worklist, use);
3122 push_bool_with_cmpu_and_mask(worklist, use);
3123 }
3124
3125
3126 // We must recheck Phis too if use is a Region.
3127 void PhaseCCP::push_phis(Unique_Node_List& worklist, const Node* use) const {
3128 if (use->is_Region()) {
3129 add_users_to_worklist_if(worklist, use, [&](Node* u) {
3130 return not_bottom_type(u);
3131 });
3132 }
3133 }
3134
3135 // If we changed the receiver type to a call, we need to revisit the Catch node following the call. It's looking for a
3136 // non-null receiver to know when to enable the regular fall-through path in addition to the NullPtrException path.
3137 // Same is true if the type of a ValidLengthTest input to an AllocateArrayNode changes.
3209 Node* m = addI->in(1);
3210 if (m == andI->in(1) || m == andI->in(2)) {
3211 // Is "m" shared? Matched (1b) and thus we revisit Bool.
3212 push_if_not_bottom_type(worklist, bol);
3213 }
3214 }
3215 }
3216
3217 // If n is used in a counted loop exit condition, then the type of the counted loop's Phi depends on the type of 'n'.
3218 // Seem PhiNode::Value().
3219 void PhaseCCP::push_counted_loop_phi(Unique_Node_List& worklist, Node* parent, const Node* use) {
3220 uint use_op = use->Opcode();
3221 if (use_op == Op_CmpI || use_op == Op_CmpL) {
3222 PhiNode* phi = countedloop_phi_from_cmp(use->as_Cmp(), parent);
3223 if (phi != nullptr) {
3224 worklist.push(phi);
3225 }
3226 }
3227 }
3228
3229 // TODO 8350865 Still needed? Yes, I think this is from PhaseMacroExpand::expand_mh_intrinsic_return
3230 void PhaseCCP::push_cast(Unique_Node_List& worklist, const Node* use) {
3231 uint use_op = use->Opcode();
3232 if (use_op == Op_CastP2X) {
3233 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
3234 Node* u = use->fast_out(i2);
3235 if (u->Opcode() == Op_AndX) {
3236 worklist.push(u);
3237 }
3238 }
3239 }
3240 }
3241
3242 // Loading the java mirror from a Klass requires two loads and the type of the mirror load depends on the type of 'n'.
3243 // See LoadNode::Value().
3244 void PhaseCCP::push_loadp(Unique_Node_List& worklist, const Node* use) const {
3245 BarrierSetC2* barrier_set = BarrierSet::barrier_set()->barrier_set_c2();
3246 bool has_load_barrier_nodes = barrier_set->has_load_barrier_nodes();
3247
3248 if (use->Opcode() == Op_LoadP && use->bottom_type()->isa_rawptr()) {
3249 for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
3250 Node* loadp = use->fast_out(i);
3251 const Type* ut = loadp->bottom_type();
3252 if (loadp->Opcode() == Op_LoadP && ut->isa_instptr() && ut != type(loadp)) {
3253 if (has_load_barrier_nodes) {
3254 // Search for load barriers behind the load
3255 push_load_barrier(worklist, barrier_set, loadp);
3256 }
3257 worklist.push(loadp);
3258 }
3259 }
3260 }
3261 }
|