1037 _worklist.print_set();
1038 }
1039 }
1040 }
1041 #endif /* ASSERT */
1042
1043 void PhaseIterGVN::optimize() {
1044 DEBUG_ONLY(uint num_processed = 0;)
1045 NOT_PRODUCT(init_verifyPhaseIterGVN();)
1046 NOT_PRODUCT(C->reset_igv_phase_iter(PHASE_AFTER_ITER_GVN_STEP);)
1047 C->print_method(PHASE_BEFORE_ITER_GVN, 3);
1048 if (StressIGVN) {
1049 shuffle_worklist();
1050 }
1051
1052 // The node count check in the loop below (check_node_count) assumes that we
1053 // increase the live node count with at most
1054 // max_live_nodes_increase_per_iteration in between checks. If this
1055 // assumption does not hold, there is a risk that we exceed the max node
1056 // limit in between checks and trigger an assert during node creation.
1057 const int max_live_nodes_increase_per_iteration = NodeLimitFudgeFactor * 3;
1058
1059 uint loop_count = 0;
1060 // Pull from worklist and transform the node. If the node has changed,
1061 // update edge info and put uses on worklist.
1062 while (_worklist.size() > 0) {
1063 if (C->check_node_count(max_live_nodes_increase_per_iteration, "Out of nodes")) {
1064 C->print_method(PHASE_AFTER_ITER_GVN, 3);
1065 return;
1066 }
1067 Node* n = _worklist.pop();
1068 if (loop_count >= K * C->live_nodes()) {
1069 DEBUG_ONLY(dump_infinite_loop_info(n, "PhaseIterGVN::optimize");)
1070 C->record_method_not_compilable("infinite loop in PhaseIterGVN::optimize");
1071 C->print_method(PHASE_AFTER_ITER_GVN, 3);
1072 return;
1073 }
1074 DEBUG_ONLY(trace_PhaseIterGVN_verbose(n, num_processed++);)
1075 if (n->outcnt() != 0) {
1076 NOT_PRODUCT(const Type* oldtype = type_or_null(n));
1077 // Do the transformation
1198 // SubNode::Value
1199 // CmpPNode::sub
1200 // MemNode::detect_ptr_independence
1201 // MemNode::all_controls_dominate
1202 // We find all controls of a pointer load, and see if they dominate the control of
1203 // an allocation. If they all dominate, we know the allocation is after (independent)
1204 // of the pointer load, and we can say the pointers are different. For this we call
1205 // n->dominates(sub, nlist) to check if controls n of the pointer load dominate the
1206 // control sub of the allocation. The problems is that sometimes dominates answers
1207 // false conservatively, and later it can determine that it is indeed true. Loops with
1208 // Region heads can lead to giving up, whereas LoopNodes can be skipped easier, and
1209 // so the traversal becomes more powerful. This is difficult to remedy, we would have
1210 // to notify the CmpP of CFG updates. Luckily, we recompute CmpP::Value during CCP
1211 // after loop-opts, so that should take care of many of these cases.
1212 return;
1213 }
1214
1215 stringStream ss; // Print as a block without tty lock.
1216 ss.cr();
1217 ss.print_cr("Missed Value optimization:");
1218 n->dump_bfs(1, nullptr, "", &ss);
1219 ss.print_cr("Current type:");
1220 told->dump_on(&ss);
1221 ss.cr();
1222 ss.print_cr("Optimized type:");
1223 tnew->dump_on(&ss);
1224 ss.cr();
1225 tty->print_cr("%s", ss.as_string());
1226
1227 switch (_phase) {
1228 case PhaseValuesType::iter_gvn:
1229 assert(false, "Missed Value optimization opportunity in PhaseIterGVN for %s",n->Name());
1230 break;
1231 case PhaseValuesType::ccp:
1232 assert(false, "PhaseCCP not at fixpoint: analysis result may be unsound for %s", n->Name());
1233 break;
1234 default:
1235 assert(false, "Unexpected phase");
1236 break;
1237 }
1238 }
2087 assert(false, "Broken node invariant for %s", n->Name());
2088 }
2089 }
2090 }
2091 #endif
2092
2093 /**
2094 * Register a new node with the optimizer. Update the types array, the def-use
2095 * info. Put on worklist.
2096 */
2097 Node* PhaseIterGVN::register_new_node_with_optimizer(Node* n, Node* orig) {
2098 set_type_bottom(n);
2099 _worklist.push(n);
2100 if (orig != nullptr) C->copy_node_notes_to(n, orig);
2101 return n;
2102 }
2103
2104 //------------------------------transform--------------------------------------
2105 // Non-recursive: idealize Node 'n' with respect to its inputs and its value
2106 Node *PhaseIterGVN::transform( Node *n ) {
2107 if (_delay_transform) {
2108 // Register the node but don't optimize for now
2109 register_new_node_with_optimizer(n);
2110 return n;
2111 }
2112
2113 // If brand new node, make space in type array, and give it a type.
2114 ensure_type_or_null(n);
2115 if (type_or_null(n) == nullptr) {
2116 set_type_bottom(n);
2117 }
2118
2119 return transform_old(n);
2120 }
2121
2122 Node *PhaseIterGVN::transform_old(Node* n) {
2123 NOT_PRODUCT(set_transforms());
2124 // Remove 'n' from hash table in case it gets modified
2125 _table.hash_delete(n);
2126 #ifdef ASSERT
2127 if (is_verify_def_use()) {
2128 assert(!_table.find_index(n->_idx), "found duplicate entry in table");
2129 }
2130 #endif
2131
2132 // Allow Bool -> Cmp idealisation in late inlining intrinsics that return a bool
2133 if (n->is_Cmp()) {
2134 add_users_to_worklist(n);
2135 }
2136
2137 // Apply the Ideal call in a loop until it no longer applies
2138 Node* k = n;
2378
2379 // Smash all inputs to 'old', isolating him completely
2380 Node *temp = new Node(1);
2381 temp->init_req(0,nn); // Add a use to nn to prevent him from dying
2382 remove_dead_node( old );
2383 temp->del_req(0); // Yank bogus edge
2384 if (nn != nullptr && nn->outcnt() == 0) {
2385 _worklist.push(nn);
2386 }
2387 #ifndef PRODUCT
2388 if (is_verify_def_use()) {
2389 for ( int i = 0; i < _verify_window_size; i++ ) {
2390 if ( _verify_window[i] == old )
2391 _verify_window[i] = nn;
2392 }
2393 }
2394 #endif
2395 temp->destruct(this); // reuse the _idx of this little guy
2396 }
2397
2398 //------------------------------add_users_to_worklist--------------------------
2399 void PhaseIterGVN::add_users_to_worklist0(Node* n, Unique_Node_List& worklist) {
2400 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
2401 worklist.push(n->fast_out(i)); // Push on worklist
2402 }
2403 }
2404
2405 // Return counted loop Phi if as a counted loop exit condition, cmp
2406 // compares the induction variable with n
2407 static PhiNode* countedloop_phi_from_cmp(CmpNode* cmp, Node* n) {
2408 for (DUIterator_Fast imax, i = cmp->fast_outs(imax); i < imax; i++) {
2409 Node* bol = cmp->fast_out(i);
2410 for (DUIterator_Fast i2max, i2 = bol->fast_outs(i2max); i2 < i2max; i2++) {
2411 Node* iff = bol->fast_out(i2);
2412 if (iff->is_BaseCountedLoopEnd()) {
2413 BaseCountedLoopEndNode* cle = iff->as_BaseCountedLoopEnd();
2414 if (cle->limit() == n) {
2415 PhiNode* phi = cle->phi();
2416 if (phi != nullptr) {
2417 return phi;
2433 add_users_of_use_to_worklist(n, use, worklist);
2434 }
2435 }
2436
2437 void PhaseIterGVN::add_users_of_use_to_worklist(Node* n, Node* use, Unique_Node_List& worklist) {
2438 if(use->is_Multi() || // Multi-definer? Push projs on worklist
2439 use->is_Store() ) // Enable store/load same address
2440 add_users_to_worklist0(use, worklist);
2441
2442 // If we changed the receiver type to a call, we need to revisit
2443 // the Catch following the call. It's looking for a non-null
2444 // receiver to know when to enable the regular fall-through path
2445 // in addition to the NullPtrException path.
2446 if (use->is_CallDynamicJava() && n == use->in(TypeFunc::Parms)) {
2447 Node* p = use->as_CallDynamicJava()->proj_out_or_null(TypeFunc::Control);
2448 if (p != nullptr) {
2449 add_users_to_worklist0(p, worklist);
2450 }
2451 }
2452
2453 uint use_op = use->Opcode();
2454 if(use->is_Cmp()) { // Enable CMP/BOOL optimization
2455 add_users_to_worklist0(use, worklist); // Put Bool on worklist
2456 if (use->outcnt() > 0) {
2457 Node* bol = use->raw_out(0);
2458 if (bol->outcnt() > 0) {
2459 Node* iff = bol->raw_out(0);
2460 if (iff->outcnt() == 2) {
2461 // Look for the 'is_x2logic' pattern: "x ? : 0 : 1" and put the
2462 // phi merging either 0 or 1 onto the worklist
2463 Node* ifproj0 = iff->raw_out(0);
2464 Node* ifproj1 = iff->raw_out(1);
2465 if (ifproj0->outcnt() > 0 && ifproj1->outcnt() > 0) {
2466 Node* region0 = ifproj0->raw_out(0);
2467 Node* region1 = ifproj1->raw_out(0);
2468 if( region0 == region1 )
2469 add_users_to_worklist0(region0, worklist);
2470 }
2471 }
2472 }
2530 assert(n == in2, "only in2 modified");
2531 // Find all CastII with input in1.
2532 for (DUIterator_Fast jmax, j = in1->fast_outs(jmax); j < jmax; j++) {
2533 Node* castii = in1->fast_out(j);
2534 if (castii->is_CastII() && castii->as_CastII()->carry_dependency()) {
2535 // Find If.
2536 if (castii->in(0) != nullptr && castii->in(0)->in(0) != nullptr && castii->in(0)->in(0)->is_If()) {
2537 Node* ifnode = castii->in(0)->in(0);
2538 // Check that if connects to the cmp
2539 if (ifnode->in(1) != nullptr && ifnode->in(1)->is_Bool() && ifnode->in(1)->in(1) == cmp) {
2540 worklist.push(castii);
2541 }
2542 }
2543 }
2544 }
2545 }
2546 }
2547 }
2548 }
2549
2550 // If changed Cast input, notify down for Phi, Sub, and Xor - all do "uncast"
2551 // Patterns:
2552 // ConstraintCast+ -> Sub
2553 // ConstraintCast+ -> Phi
2554 // ConstraintCast+ -> Xor
2555 if (use->is_ConstraintCast()) {
2556 auto push_the_uses_to_worklist = [&](Node* n){
2557 if (n->is_Phi() || n->is_Sub() || n->Opcode() == Op_XorI || n->Opcode() == Op_XorL) {
2558 worklist.push(n);
2559 }
2560 };
2561 auto is_boundary = [](Node* n){ return !n->is_ConstraintCast(); };
2562 use->visit_uses(push_the_uses_to_worklist, is_boundary);
2563 }
2564 // If changed LShift inputs, check RShift/URShift users for
2565 // "(X << C) >> C" sign-ext and "(X << C) >>> C" zero-ext optimizations.
2566 if (use_op == Op_LShiftI || use_op == Op_LShiftL) {
2567 add_users_to_worklist_if(worklist, use, [](Node* u) {
2568 return u->Opcode() == Op_RShiftI || u->Opcode() == Op_RShiftL ||
2569 u->Opcode() == Op_URShiftI || u->Opcode() == Op_URShiftL;
2651 // If the ValidLengthTest input changes then the fallthrough path out of the AllocateArray may have become dead.
2652 // CatchNode::Value() is responsible for killing that path. The CatchNode has to be explicitly enqueued for igvn
2653 // to guarantee the change is not missed.
2654 if (use_op == Op_AllocateArray && n == use->in(AllocateNode::ValidLengthTest)) {
2655 Node* p = use->as_AllocateArray()->proj_out_or_null(TypeFunc::Control);
2656 if (p != nullptr) {
2657 add_users_to_worklist0(p, worklist);
2658 }
2659 }
2660
2661 if (use_op == Op_Initialize) {
2662 InitializeNode* init = use->as_Initialize();
2663 init->for_each_proj(enqueue_init_mem_projs, TypeFunc::Memory);
2664 }
2665 // Loading the java mirror from a Klass requires two loads and the type
2666 // of the mirror load depends on the type of 'n'. See LoadNode::Value().
2667 // LoadBarrier?(LoadP(LoadP(AddP(foo:Klass, #java_mirror))))
2668 BarrierSetC2* bs = BarrierSet::barrier_set()->barrier_set_c2();
2669 bool has_load_barrier_nodes = bs->has_load_barrier_nodes();
2670
2671 if (use_op == Op_LoadP && use->bottom_type()->isa_rawptr()) {
2672 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2673 Node* u = use->fast_out(i2);
2674 const Type* ut = u->bottom_type();
2675 if (u->Opcode() == Op_LoadP && ut->isa_instptr()) {
2676 if (has_load_barrier_nodes) {
2677 // Search for load barriers behind the load
2678 add_users_to_worklist_if(worklist, u, [&](Node* b) {
2679 return bs->is_gc_barrier_node(b);
2680 });
2681 }
2682 worklist.push(u);
2683 }
2684 }
2685 }
2686 if (use->Opcode() == Op_OpaqueZeroTripGuard) {
2687 assert(use->outcnt() <= 1, "OpaqueZeroTripGuard can't be shared");
2688 if (use->outcnt() == 1) {
2689 Node* cmp = use->unique_out();
2690 worklist.push(cmp);
2691 }
2692 }
2693 // VectorMaskToLongNode::Ideal_MaskAll looks through VectorStoreMask
2694 // to fold constant masks.
2695 if (use_op == Op_VectorStoreMask) {
2696 add_users_to_worklist_if(worklist, use, [](Node* u) { return u->Opcode() == Op_VectorMaskToLong; });
2697 }
2698
2699 // From CastX2PNode::Ideal
2700 // CastX2P(AddX(x, y))
2701 // CastX2P(SubX(x, y))
2702 if (use->Opcode() == Op_AddX || use->Opcode() == Op_SubX) {
2703 add_users_to_worklist_if(worklist, use, [](Node* u) { return u->Opcode() == Op_CastX2P; });
2704 }
2705
2762 // Conditional Constant Propagation, ala Wegman & Zadeck
2763 PhaseCCP::PhaseCCP( PhaseIterGVN *igvn ) : PhaseIterGVN(igvn) {
2764 NOT_PRODUCT( clear_constants(); )
2765 assert( _worklist.size() == 0, "" );
2766 _phase = PhaseValuesType::ccp;
2767 analyze();
2768 }
2769
2770 #ifndef PRODUCT
2771 //------------------------------~PhaseCCP--------------------------------------
2772 PhaseCCP::~PhaseCCP() {
2773 inc_invokes();
2774 _total_constants += count_constants();
2775 }
2776 #endif
2777
2778
2779 #ifdef ASSERT
2780 void PhaseCCP::verify_type(Node* n, const Type* tnew, const Type* told) {
2781 if (tnew->meet(told) != tnew->remove_speculative()) {
2782 n->dump(1);
2783 tty->print("told = "); told->dump(); tty->cr();
2784 tty->print("tnew = "); tnew->dump(); tty->cr();
2785 fatal("Not monotonic");
2786 }
2787 assert(!told->isa_int() || !tnew->isa_int() || told->is_int()->_widen <= tnew->is_int()->_widen, "widen increases");
2788 assert(!told->isa_long() || !tnew->isa_long() || told->is_long()->_widen <= tnew->is_long()->_widen, "widen increases");
2789 }
2790 #endif //ASSERT
2791
2792 // In this analysis, all types are initially set to TOP. We iteratively call Value() on all nodes of the graph until
2793 // we reach a fixed-point (i.e. no types change anymore). We start with a list that only contains the root node. Each time
2794 // a new type is set, we push all uses of that node back to the worklist (in some cases, we also push grandchildren
2795 // or nodes even further down back to the worklist because their type could change as a result of the current type
2796 // change).
2797 void PhaseCCP::analyze() {
2798 // Initialize all types to TOP, optimistic analysis
2799 for (uint i = 0; i < C->unique(); i++) {
2800 _types.map(i, Type::TOP);
2801 }
2802
2931 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
2932 Node* use = n->fast_out(i);
2933 push_if_not_bottom_type(worklist, use);
2934 push_more_uses(worklist, n, use);
2935 }
2936 }
2937
2938 void PhaseCCP::push_if_not_bottom_type(Unique_Node_List& worklist, Node* n) const {
2939 if (not_bottom_type(n)) {
2940 worklist.push(n);
2941 }
2942 }
2943
2944 // For some nodes, we need to propagate the type change to grandchildren or even further down.
2945 // Add them back to the worklist.
2946 void PhaseCCP::push_more_uses(Unique_Node_List& worklist, Node* parent, const Node* use) const {
2947 push_phis(worklist, use);
2948 push_catch(worklist, use);
2949 push_cmpu(worklist, use);
2950 push_counted_loop_phi(worklist, parent, use);
2951 push_loadp(worklist, use);
2952 push_and(worklist, parent, use);
2953 push_cast_ii(worklist, parent, use);
2954 push_opaque_zero_trip_guard(worklist, use);
2955 push_bool_with_cmpu_and_mask(worklist, use);
2956 }
2957
2958
2959 // We must recheck Phis too if use is a Region.
2960 void PhaseCCP::push_phis(Unique_Node_List& worklist, const Node* use) const {
2961 if (use->is_Region()) {
2962 add_users_to_worklist_if(worklist, use, [&](Node* u) {
2963 return not_bottom_type(u);
2964 });
2965 }
2966 }
2967
2968 // If we changed the receiver type to a call, we need to revisit the Catch node following the call. It's looking for a
2969 // non-null receiver to know when to enable the regular fall-through path in addition to the NullPtrException path.
2970 // Same is true if the type of a ValidLengthTest input to an AllocateArrayNode changes.
3042 Node* m = addI->in(1);
3043 if (m == andI->in(1) || m == andI->in(2)) {
3044 // Is "m" shared? Matched (1b) and thus we revisit Bool.
3045 push_if_not_bottom_type(worklist, bol);
3046 }
3047 }
3048 }
3049
3050 // 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'.
3051 // Seem PhiNode::Value().
3052 void PhaseCCP::push_counted_loop_phi(Unique_Node_List& worklist, Node* parent, const Node* use) {
3053 uint use_op = use->Opcode();
3054 if (use_op == Op_CmpI || use_op == Op_CmpL) {
3055 PhiNode* phi = countedloop_phi_from_cmp(use->as_Cmp(), parent);
3056 if (phi != nullptr) {
3057 worklist.push(phi);
3058 }
3059 }
3060 }
3061
3062 // Loading the java mirror from a Klass requires two loads and the type of the mirror load depends on the type of 'n'.
3063 // See LoadNode::Value().
3064 void PhaseCCP::push_loadp(Unique_Node_List& worklist, const Node* use) const {
3065 BarrierSetC2* barrier_set = BarrierSet::barrier_set()->barrier_set_c2();
3066 bool has_load_barrier_nodes = barrier_set->has_load_barrier_nodes();
3067
3068 if (use->Opcode() == Op_LoadP && use->bottom_type()->isa_rawptr()) {
3069 for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
3070 Node* loadp = use->fast_out(i);
3071 const Type* ut = loadp->bottom_type();
3072 if (loadp->Opcode() == Op_LoadP && ut->isa_instptr() && ut != type(loadp)) {
3073 if (has_load_barrier_nodes) {
3074 // Search for load barriers behind the load
3075 push_load_barrier(worklist, barrier_set, loadp);
3076 }
3077 worklist.push(loadp);
3078 }
3079 }
3080 }
3081 }
|
1037 _worklist.print_set();
1038 }
1039 }
1040 }
1041 #endif /* ASSERT */
1042
1043 void PhaseIterGVN::optimize() {
1044 DEBUG_ONLY(uint num_processed = 0;)
1045 NOT_PRODUCT(init_verifyPhaseIterGVN();)
1046 NOT_PRODUCT(C->reset_igv_phase_iter(PHASE_AFTER_ITER_GVN_STEP);)
1047 C->print_method(PHASE_BEFORE_ITER_GVN, 3);
1048 if (StressIGVN) {
1049 shuffle_worklist();
1050 }
1051
1052 // The node count check in the loop below (check_node_count) assumes that we
1053 // increase the live node count with at most
1054 // max_live_nodes_increase_per_iteration in between checks. If this
1055 // assumption does not hold, there is a risk that we exceed the max node
1056 // limit in between checks and trigger an assert during node creation.
1057 const int max_live_nodes_increase_per_iteration = NodeLimitFudgeFactor * 5;
1058
1059 uint loop_count = 0;
1060 // Pull from worklist and transform the node. If the node has changed,
1061 // update edge info and put uses on worklist.
1062 while (_worklist.size() > 0) {
1063 if (C->check_node_count(max_live_nodes_increase_per_iteration, "Out of nodes")) {
1064 C->print_method(PHASE_AFTER_ITER_GVN, 3);
1065 return;
1066 }
1067 Node* n = _worklist.pop();
1068 if (loop_count >= K * C->live_nodes()) {
1069 DEBUG_ONLY(dump_infinite_loop_info(n, "PhaseIterGVN::optimize");)
1070 C->record_method_not_compilable("infinite loop in PhaseIterGVN::optimize");
1071 C->print_method(PHASE_AFTER_ITER_GVN, 3);
1072 return;
1073 }
1074 DEBUG_ONLY(trace_PhaseIterGVN_verbose(n, num_processed++);)
1075 if (n->outcnt() != 0) {
1076 NOT_PRODUCT(const Type* oldtype = type_or_null(n));
1077 // Do the transformation
1198 // SubNode::Value
1199 // CmpPNode::sub
1200 // MemNode::detect_ptr_independence
1201 // MemNode::all_controls_dominate
1202 // We find all controls of a pointer load, and see if they dominate the control of
1203 // an allocation. If they all dominate, we know the allocation is after (independent)
1204 // of the pointer load, and we can say the pointers are different. For this we call
1205 // n->dominates(sub, nlist) to check if controls n of the pointer load dominate the
1206 // control sub of the allocation. The problems is that sometimes dominates answers
1207 // false conservatively, and later it can determine that it is indeed true. Loops with
1208 // Region heads can lead to giving up, whereas LoopNodes can be skipped easier, and
1209 // so the traversal becomes more powerful. This is difficult to remedy, we would have
1210 // to notify the CmpP of CFG updates. Luckily, we recompute CmpP::Value during CCP
1211 // after loop-opts, so that should take care of many of these cases.
1212 return;
1213 }
1214
1215 stringStream ss; // Print as a block without tty lock.
1216 ss.cr();
1217 ss.print_cr("Missed Value optimization:");
1218 n->dump_bfs(3, nullptr, "", &ss);
1219 ss.print_cr("Current type:");
1220 told->dump_on(&ss);
1221 ss.cr();
1222 ss.print_cr("Optimized type:");
1223 tnew->dump_on(&ss);
1224 ss.cr();
1225 tty->print_cr("%s", ss.as_string());
1226
1227 switch (_phase) {
1228 case PhaseValuesType::iter_gvn:
1229 assert(false, "Missed Value optimization opportunity in PhaseIterGVN for %s",n->Name());
1230 break;
1231 case PhaseValuesType::ccp:
1232 assert(false, "PhaseCCP not at fixpoint: analysis result may be unsound for %s", n->Name());
1233 break;
1234 default:
1235 assert(false, "Unexpected phase");
1236 break;
1237 }
1238 }
2087 assert(false, "Broken node invariant for %s", n->Name());
2088 }
2089 }
2090 }
2091 #endif
2092
2093 /**
2094 * Register a new node with the optimizer. Update the types array, the def-use
2095 * info. Put on worklist.
2096 */
2097 Node* PhaseIterGVN::register_new_node_with_optimizer(Node* n, Node* orig) {
2098 set_type_bottom(n);
2099 _worklist.push(n);
2100 if (orig != nullptr) C->copy_node_notes_to(n, orig);
2101 return n;
2102 }
2103
2104 //------------------------------transform--------------------------------------
2105 // Non-recursive: idealize Node 'n' with respect to its inputs and its value
2106 Node *PhaseIterGVN::transform( Node *n ) {
2107 // If brand new node, make space in type array, and give it a type.
2108 ensure_type_or_null(n);
2109 if (type_or_null(n) == nullptr) {
2110 set_type_bottom(n);
2111 }
2112
2113 if (_delay_transform) {
2114 // Add the node to the worklist but don't optimize for now
2115 _worklist.push(n);
2116 return n;
2117 }
2118
2119 return transform_old(n);
2120 }
2121
2122 Node *PhaseIterGVN::transform_old(Node* n) {
2123 NOT_PRODUCT(set_transforms());
2124 // Remove 'n' from hash table in case it gets modified
2125 _table.hash_delete(n);
2126 #ifdef ASSERT
2127 if (is_verify_def_use()) {
2128 assert(!_table.find_index(n->_idx), "found duplicate entry in table");
2129 }
2130 #endif
2131
2132 // Allow Bool -> Cmp idealisation in late inlining intrinsics that return a bool
2133 if (n->is_Cmp()) {
2134 add_users_to_worklist(n);
2135 }
2136
2137 // Apply the Ideal call in a loop until it no longer applies
2138 Node* k = n;
2378
2379 // Smash all inputs to 'old', isolating him completely
2380 Node *temp = new Node(1);
2381 temp->init_req(0,nn); // Add a use to nn to prevent him from dying
2382 remove_dead_node( old );
2383 temp->del_req(0); // Yank bogus edge
2384 if (nn != nullptr && nn->outcnt() == 0) {
2385 _worklist.push(nn);
2386 }
2387 #ifndef PRODUCT
2388 if (is_verify_def_use()) {
2389 for ( int i = 0; i < _verify_window_size; i++ ) {
2390 if ( _verify_window[i] == old )
2391 _verify_window[i] = nn;
2392 }
2393 }
2394 #endif
2395 temp->destruct(this); // reuse the _idx of this little guy
2396 }
2397
2398 void PhaseIterGVN::replace_in_uses(Node* n, Node* m) {
2399 assert(n != nullptr, "sanity");
2400 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
2401 Node* u = n->fast_out(i);
2402 if (u != n) {
2403 rehash_node_delayed(u);
2404 int nb = u->replace_edge(n, m);
2405 --i, imax -= nb;
2406 }
2407 }
2408 assert(n->outcnt() == 0, "all uses must be deleted");
2409 }
2410
2411 //------------------------------add_users_to_worklist--------------------------
2412 void PhaseIterGVN::add_users_to_worklist0(Node* n, Unique_Node_List& worklist) {
2413 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
2414 worklist.push(n->fast_out(i)); // Push on worklist
2415 }
2416 }
2417
2418 // Return counted loop Phi if as a counted loop exit condition, cmp
2419 // compares the induction variable with n
2420 static PhiNode* countedloop_phi_from_cmp(CmpNode* cmp, Node* n) {
2421 for (DUIterator_Fast imax, i = cmp->fast_outs(imax); i < imax; i++) {
2422 Node* bol = cmp->fast_out(i);
2423 for (DUIterator_Fast i2max, i2 = bol->fast_outs(i2max); i2 < i2max; i2++) {
2424 Node* iff = bol->fast_out(i2);
2425 if (iff->is_BaseCountedLoopEnd()) {
2426 BaseCountedLoopEndNode* cle = iff->as_BaseCountedLoopEnd();
2427 if (cle->limit() == n) {
2428 PhiNode* phi = cle->phi();
2429 if (phi != nullptr) {
2430 return phi;
2446 add_users_of_use_to_worklist(n, use, worklist);
2447 }
2448 }
2449
2450 void PhaseIterGVN::add_users_of_use_to_worklist(Node* n, Node* use, Unique_Node_List& worklist) {
2451 if(use->is_Multi() || // Multi-definer? Push projs on worklist
2452 use->is_Store() ) // Enable store/load same address
2453 add_users_to_worklist0(use, worklist);
2454
2455 // If we changed the receiver type to a call, we need to revisit
2456 // the Catch following the call. It's looking for a non-null
2457 // receiver to know when to enable the regular fall-through path
2458 // in addition to the NullPtrException path.
2459 if (use->is_CallDynamicJava() && n == use->in(TypeFunc::Parms)) {
2460 Node* p = use->as_CallDynamicJava()->proj_out_or_null(TypeFunc::Control);
2461 if (p != nullptr) {
2462 add_users_to_worklist0(p, worklist);
2463 }
2464 }
2465
2466 // AndLNode::Ideal folds GraphKit::mark_word_test patterns. Give it a chance to run.
2467 if (n->is_Load() && use->is_Phi()) {
2468 for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
2469 Node* u = use->fast_out(i);
2470 if (u->Opcode() == Op_AndL) {
2471 worklist.push(u);
2472 }
2473 }
2474 }
2475
2476 uint use_op = use->Opcode();
2477 if(use->is_Cmp()) { // Enable CMP/BOOL optimization
2478 add_users_to_worklist0(use, worklist); // Put Bool on worklist
2479 if (use->outcnt() > 0) {
2480 Node* bol = use->raw_out(0);
2481 if (bol->outcnt() > 0) {
2482 Node* iff = bol->raw_out(0);
2483 if (iff->outcnt() == 2) {
2484 // Look for the 'is_x2logic' pattern: "x ? : 0 : 1" and put the
2485 // phi merging either 0 or 1 onto the worklist
2486 Node* ifproj0 = iff->raw_out(0);
2487 Node* ifproj1 = iff->raw_out(1);
2488 if (ifproj0->outcnt() > 0 && ifproj1->outcnt() > 0) {
2489 Node* region0 = ifproj0->raw_out(0);
2490 Node* region1 = ifproj1->raw_out(0);
2491 if( region0 == region1 )
2492 add_users_to_worklist0(region0, worklist);
2493 }
2494 }
2495 }
2553 assert(n == in2, "only in2 modified");
2554 // Find all CastII with input in1.
2555 for (DUIterator_Fast jmax, j = in1->fast_outs(jmax); j < jmax; j++) {
2556 Node* castii = in1->fast_out(j);
2557 if (castii->is_CastII() && castii->as_CastII()->carry_dependency()) {
2558 // Find If.
2559 if (castii->in(0) != nullptr && castii->in(0)->in(0) != nullptr && castii->in(0)->in(0)->is_If()) {
2560 Node* ifnode = castii->in(0)->in(0);
2561 // Check that if connects to the cmp
2562 if (ifnode->in(1) != nullptr && ifnode->in(1)->is_Bool() && ifnode->in(1)->in(1) == cmp) {
2563 worklist.push(castii);
2564 }
2565 }
2566 }
2567 }
2568 }
2569 }
2570 }
2571 }
2572
2573 // Inline type nodes can have other inline types as users. If an input gets
2574 // updated, make sure that inline type users get a chance for optimization.
2575 if (use->is_InlineType() || use->is_DecodeN()) {
2576 auto push_the_uses_to_worklist = [&](Node* n){
2577 if (n->is_InlineType()) {
2578 worklist.push(n);
2579 }
2580 };
2581 auto is_boundary = [](Node* n){ return !n->is_InlineType(); };
2582 use->visit_uses(push_the_uses_to_worklist, is_boundary, true);
2583 }
2584 // If changed Cast input, notify down for Phi, Sub, and Xor - all do "uncast"
2585 // Patterns:
2586 // ConstraintCast+ -> Sub
2587 // ConstraintCast+ -> Phi
2588 // ConstraintCast+ -> Xor
2589 if (use->is_ConstraintCast()) {
2590 auto push_the_uses_to_worklist = [&](Node* n){
2591 if (n->is_Phi() || n->is_Sub() || n->Opcode() == Op_XorI || n->Opcode() == Op_XorL) {
2592 worklist.push(n);
2593 }
2594 };
2595 auto is_boundary = [](Node* n){ return !n->is_ConstraintCast(); };
2596 use->visit_uses(push_the_uses_to_worklist, is_boundary);
2597 }
2598 // If changed LShift inputs, check RShift/URShift users for
2599 // "(X << C) >> C" sign-ext and "(X << C) >>> C" zero-ext optimizations.
2600 if (use_op == Op_LShiftI || use_op == Op_LShiftL) {
2601 add_users_to_worklist_if(worklist, use, [](Node* u) {
2602 return u->Opcode() == Op_RShiftI || u->Opcode() == Op_RShiftL ||
2603 u->Opcode() == Op_URShiftI || u->Opcode() == Op_URShiftL;
2685 // If the ValidLengthTest input changes then the fallthrough path out of the AllocateArray may have become dead.
2686 // CatchNode::Value() is responsible for killing that path. The CatchNode has to be explicitly enqueued for igvn
2687 // to guarantee the change is not missed.
2688 if (use_op == Op_AllocateArray && n == use->in(AllocateNode::ValidLengthTest)) {
2689 Node* p = use->as_AllocateArray()->proj_out_or_null(TypeFunc::Control);
2690 if (p != nullptr) {
2691 add_users_to_worklist0(p, worklist);
2692 }
2693 }
2694
2695 if (use_op == Op_Initialize) {
2696 InitializeNode* init = use->as_Initialize();
2697 init->for_each_proj(enqueue_init_mem_projs, TypeFunc::Memory);
2698 }
2699 // Loading the java mirror from a Klass requires two loads and the type
2700 // of the mirror load depends on the type of 'n'. See LoadNode::Value().
2701 // LoadBarrier?(LoadP(LoadP(AddP(foo:Klass, #java_mirror))))
2702 BarrierSetC2* bs = BarrierSet::barrier_set()->barrier_set_c2();
2703 bool has_load_barrier_nodes = bs->has_load_barrier_nodes();
2704
2705 if (use_op == Op_CastP2X) {
2706 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2707 Node* u = use->fast_out(i2);
2708 // TODO 8350865 Still needed? Yes, I think this is from PhaseMacroExpand::expand_mh_intrinsic_return
2709 if (u->Opcode() == Op_AndX) {
2710 worklist.push(u);
2711 }
2712 // Search for CmpL(OrL(CastP2X(..), CastP2X(..)), 0L)
2713 if (u->Opcode() == Op_OrL) {
2714 for (DUIterator_Fast i3max, i3 = u->fast_outs(i3max); i3 < i3max; i3++) {
2715 Node* cmp = u->fast_out(i3);
2716 if (cmp->Opcode() == Op_CmpL) {
2717 worklist.push(cmp);
2718 }
2719 }
2720 }
2721 }
2722 }
2723 if (use_op == Op_LoadP && use->bottom_type()->isa_rawptr()) {
2724 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2725 Node* u = use->fast_out(i2);
2726 const Type* ut = u->bottom_type();
2727 if (u->Opcode() == Op_LoadP && ut->isa_instptr()) {
2728 if (has_load_barrier_nodes) {
2729 // Search for load barriers behind the load
2730 add_users_to_worklist_if(worklist, u, [&](Node* b) {
2731 return bs->is_gc_barrier_node(b);
2732 });
2733 }
2734 worklist.push(u);
2735 }
2736 }
2737 }
2738 // Give CallStaticJavaNode::remove_useless_allocation a chance to run
2739 if (use->is_Region()) {
2740 Node* c = use;
2741 do {
2742 c = c->unique_ctrl_out_or_null();
2743 } while (c != nullptr && c->is_Region());
2744 if (c != nullptr && c->is_CallStaticJava() && c->as_CallStaticJava()->uncommon_trap_request() != 0) {
2745 worklist.push(c);
2746 }
2747 }
2748 if (use->Opcode() == Op_OpaqueZeroTripGuard) {
2749 assert(use->outcnt() <= 1, "OpaqueZeroTripGuard can't be shared");
2750 if (use->outcnt() == 1) {
2751 Node* cmp = use->unique_out();
2752 worklist.push(cmp);
2753 }
2754 }
2755 // VectorMaskToLongNode::Ideal_MaskAll looks through VectorStoreMask
2756 // to fold constant masks.
2757 if (use_op == Op_VectorStoreMask) {
2758 add_users_to_worklist_if(worklist, use, [](Node* u) { return u->Opcode() == Op_VectorMaskToLong; });
2759 }
2760
2761 // From CastX2PNode::Ideal
2762 // CastX2P(AddX(x, y))
2763 // CastX2P(SubX(x, y))
2764 if (use->Opcode() == Op_AddX || use->Opcode() == Op_SubX) {
2765 add_users_to_worklist_if(worklist, use, [](Node* u) { return u->Opcode() == Op_CastX2P; });
2766 }
2767
2824 // Conditional Constant Propagation, ala Wegman & Zadeck
2825 PhaseCCP::PhaseCCP( PhaseIterGVN *igvn ) : PhaseIterGVN(igvn) {
2826 NOT_PRODUCT( clear_constants(); )
2827 assert( _worklist.size() == 0, "" );
2828 _phase = PhaseValuesType::ccp;
2829 analyze();
2830 }
2831
2832 #ifndef PRODUCT
2833 //------------------------------~PhaseCCP--------------------------------------
2834 PhaseCCP::~PhaseCCP() {
2835 inc_invokes();
2836 _total_constants += count_constants();
2837 }
2838 #endif
2839
2840
2841 #ifdef ASSERT
2842 void PhaseCCP::verify_type(Node* n, const Type* tnew, const Type* told) {
2843 if (tnew->meet(told) != tnew->remove_speculative()) {
2844 n->dump(3);
2845 tty->print("told = "); told->dump(); tty->cr();
2846 tty->print("tnew = "); tnew->dump(); tty->cr();
2847 fatal("Not monotonic");
2848 }
2849 assert(!told->isa_int() || !tnew->isa_int() || told->is_int()->_widen <= tnew->is_int()->_widen, "widen increases");
2850 assert(!told->isa_long() || !tnew->isa_long() || told->is_long()->_widen <= tnew->is_long()->_widen, "widen increases");
2851 }
2852 #endif //ASSERT
2853
2854 // In this analysis, all types are initially set to TOP. We iteratively call Value() on all nodes of the graph until
2855 // we reach a fixed-point (i.e. no types change anymore). We start with a list that only contains the root node. Each time
2856 // a new type is set, we push all uses of that node back to the worklist (in some cases, we also push grandchildren
2857 // or nodes even further down back to the worklist because their type could change as a result of the current type
2858 // change).
2859 void PhaseCCP::analyze() {
2860 // Initialize all types to TOP, optimistic analysis
2861 for (uint i = 0; i < C->unique(); i++) {
2862 _types.map(i, Type::TOP);
2863 }
2864
2993 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
2994 Node* use = n->fast_out(i);
2995 push_if_not_bottom_type(worklist, use);
2996 push_more_uses(worklist, n, use);
2997 }
2998 }
2999
3000 void PhaseCCP::push_if_not_bottom_type(Unique_Node_List& worklist, Node* n) const {
3001 if (not_bottom_type(n)) {
3002 worklist.push(n);
3003 }
3004 }
3005
3006 // For some nodes, we need to propagate the type change to grandchildren or even further down.
3007 // Add them back to the worklist.
3008 void PhaseCCP::push_more_uses(Unique_Node_List& worklist, Node* parent, const Node* use) const {
3009 push_phis(worklist, use);
3010 push_catch(worklist, use);
3011 push_cmpu(worklist, use);
3012 push_counted_loop_phi(worklist, parent, use);
3013 push_cast(worklist, use);
3014 push_loadp(worklist, use);
3015 push_and(worklist, parent, use);
3016 push_cast_ii(worklist, parent, use);
3017 push_opaque_zero_trip_guard(worklist, use);
3018 push_bool_with_cmpu_and_mask(worklist, use);
3019 }
3020
3021
3022 // We must recheck Phis too if use is a Region.
3023 void PhaseCCP::push_phis(Unique_Node_List& worklist, const Node* use) const {
3024 if (use->is_Region()) {
3025 add_users_to_worklist_if(worklist, use, [&](Node* u) {
3026 return not_bottom_type(u);
3027 });
3028 }
3029 }
3030
3031 // If we changed the receiver type to a call, we need to revisit the Catch node following the call. It's looking for a
3032 // non-null receiver to know when to enable the regular fall-through path in addition to the NullPtrException path.
3033 // Same is true if the type of a ValidLengthTest input to an AllocateArrayNode changes.
3105 Node* m = addI->in(1);
3106 if (m == andI->in(1) || m == andI->in(2)) {
3107 // Is "m" shared? Matched (1b) and thus we revisit Bool.
3108 push_if_not_bottom_type(worklist, bol);
3109 }
3110 }
3111 }
3112
3113 // 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'.
3114 // Seem PhiNode::Value().
3115 void PhaseCCP::push_counted_loop_phi(Unique_Node_List& worklist, Node* parent, const Node* use) {
3116 uint use_op = use->Opcode();
3117 if (use_op == Op_CmpI || use_op == Op_CmpL) {
3118 PhiNode* phi = countedloop_phi_from_cmp(use->as_Cmp(), parent);
3119 if (phi != nullptr) {
3120 worklist.push(phi);
3121 }
3122 }
3123 }
3124
3125 // TODO 8350865 Still needed? Yes, I think this is from PhaseMacroExpand::expand_mh_intrinsic_return
3126 void PhaseCCP::push_cast(Unique_Node_List& worklist, const Node* use) {
3127 uint use_op = use->Opcode();
3128 if (use_op == Op_CastP2X) {
3129 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
3130 Node* u = use->fast_out(i2);
3131 if (u->Opcode() == Op_AndX) {
3132 worklist.push(u);
3133 }
3134 }
3135 }
3136 }
3137
3138 // Loading the java mirror from a Klass requires two loads and the type of the mirror load depends on the type of 'n'.
3139 // See LoadNode::Value().
3140 void PhaseCCP::push_loadp(Unique_Node_List& worklist, const Node* use) const {
3141 BarrierSetC2* barrier_set = BarrierSet::barrier_set()->barrier_set_c2();
3142 bool has_load_barrier_nodes = barrier_set->has_load_barrier_nodes();
3143
3144 if (use->Opcode() == Op_LoadP && use->bottom_type()->isa_rawptr()) {
3145 for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
3146 Node* loadp = use->fast_out(i);
3147 const Type* ut = loadp->bottom_type();
3148 if (loadp->Opcode() == Op_LoadP && ut->isa_instptr() && ut != type(loadp)) {
3149 if (has_load_barrier_nodes) {
3150 // Search for load barriers behind the load
3151 push_load_barrier(worklist, barrier_set, loadp);
3152 }
3153 worklist.push(loadp);
3154 }
3155 }
3156 }
3157 }
|