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