1026 _worklist.print_set();
1027 }
1028 }
1029 }
1030 #endif /* ASSERT */
1031
1032 void PhaseIterGVN::optimize() {
1033 DEBUG_ONLY(uint num_processed = 0;)
1034 NOT_PRODUCT(init_verifyPhaseIterGVN();)
1035 NOT_PRODUCT(C->reset_igv_phase_iter(PHASE_AFTER_ITER_GVN_STEP);)
1036 C->print_method(PHASE_BEFORE_ITER_GVN, 3);
1037 if (StressIGVN) {
1038 shuffle_worklist();
1039 }
1040
1041 // The node count check in the loop below (check_node_count) assumes that we
1042 // increase the live node count with at most
1043 // max_live_nodes_increase_per_iteration in between checks. If this
1044 // assumption does not hold, there is a risk that we exceed the max node
1045 // limit in between checks and trigger an assert during node creation.
1046 const int max_live_nodes_increase_per_iteration = NodeLimitFudgeFactor * 3;
1047
1048 uint loop_count = 0;
1049 // Pull from worklist and transform the node. If the node has changed,
1050 // update edge info and put uses on worklist.
1051 while (_worklist.size() > 0) {
1052 if (C->check_node_count(max_live_nodes_increase_per_iteration, "Out of nodes")) {
1053 C->print_method(PHASE_AFTER_ITER_GVN, 3);
1054 return;
1055 }
1056 Node* n = _worklist.pop();
1057 if (loop_count >= K * C->live_nodes()) {
1058 DEBUG_ONLY(dump_infinite_loop_info(n, "PhaseIterGVN::optimize");)
1059 C->record_method_not_compilable("infinite loop in PhaseIterGVN::optimize");
1060 C->print_method(PHASE_AFTER_ITER_GVN, 3);
1061 return;
1062 }
1063 DEBUG_ONLY(trace_PhaseIterGVN_verbose(n, num_processed++);)
1064 if (n->outcnt() != 0) {
1065 NOT_PRODUCT(const Type* oldtype = type_or_null(n));
1066 // Do the transformation
1187 // SubNode::Value
1188 // CmpPNode::sub
1189 // MemNode::detect_ptr_independence
1190 // MemNode::all_controls_dominate
1191 // We find all controls of a pointer load, and see if they dominate the control of
1192 // an allocation. If they all dominate, we know the allocation is after (independent)
1193 // of the pointer load, and we can say the pointers are different. For this we call
1194 // n->dominates(sub, nlist) to check if controls n of the pointer load dominate the
1195 // control sub of the allocation. The problems is that sometimes dominates answers
1196 // false conservatively, and later it can determine that it is indeed true. Loops with
1197 // Region heads can lead to giving up, whereas LoopNodes can be skipped easier, and
1198 // so the traversal becomes more powerful. This is difficult to remedy, we would have
1199 // to notify the CmpP of CFG updates. Luckily, we recompute CmpP::Value during CCP
1200 // after loop-opts, so that should take care of many of these cases.
1201 return;
1202 }
1203
1204 stringStream ss; // Print as a block without tty lock.
1205 ss.cr();
1206 ss.print_cr("Missed Value optimization:");
1207 n->dump_bfs(1, nullptr, "", &ss);
1208 ss.print_cr("Current type:");
1209 told->dump_on(&ss);
1210 ss.cr();
1211 ss.print_cr("Optimized type:");
1212 tnew->dump_on(&ss);
1213 ss.cr();
1214 tty->print_cr("%s", ss.as_string());
1215
1216 switch (_phase) {
1217 case PhaseValuesType::iter_gvn:
1218 assert(false, "Missed Value optimization opportunity in PhaseIterGVN for %s",n->Name());
1219 break;
1220 case PhaseValuesType::ccp:
1221 assert(false, "PhaseCCP not at fixpoint: analysis result may be unsound for %s", n->Name());
1222 break;
1223 default:
1224 assert(false, "Unexpected phase");
1225 break;
1226 }
1227 }
2110 assert(false, "Broken node invariant for %s", n->Name());
2111 }
2112 }
2113 }
2114 #endif
2115
2116 /**
2117 * Register a new node with the optimizer. Update the types array, the def-use
2118 * info. Put on worklist.
2119 */
2120 Node* PhaseIterGVN::register_new_node_with_optimizer(Node* n, Node* orig) {
2121 set_type_bottom(n);
2122 _worklist.push(n);
2123 if (orig != nullptr) C->copy_node_notes_to(n, orig);
2124 return n;
2125 }
2126
2127 //------------------------------transform--------------------------------------
2128 // Non-recursive: idealize Node 'n' with respect to its inputs and its value
2129 Node *PhaseIterGVN::transform( Node *n ) {
2130 if (_delay_transform) {
2131 // Register the node but don't optimize for now
2132 register_new_node_with_optimizer(n);
2133 return n;
2134 }
2135
2136 // If brand new node, make space in type array, and give it a type.
2137 ensure_type_or_null(n);
2138 if (type_or_null(n) == nullptr) {
2139 set_type_bottom(n);
2140 }
2141
2142 return transform_old(n);
2143 }
2144
2145 Node *PhaseIterGVN::transform_old(Node* n) {
2146 NOT_PRODUCT(set_transforms());
2147 // Remove 'n' from hash table in case it gets modified
2148 _table.hash_delete(n);
2149 #ifdef ASSERT
2150 if (is_verify_def_use()) {
2151 assert(!_table.find_index(n->_idx), "found duplicate entry in table");
2152 }
2153 #endif
2154
2155 // Allow Bool -> Cmp idealisation in late inlining intrinsics that return a bool
2156 if (n->is_Cmp()) {
2157 add_users_to_worklist(n);
2158 }
2159
2160 // Apply the Ideal call in a loop until it no longer applies
2161 Node* k = n;
2406
2407 // Smash all inputs to 'old', isolating him completely
2408 Node *temp = new Node(1);
2409 temp->init_req(0,nn); // Add a use to nn to prevent him from dying
2410 remove_dead_node( old );
2411 temp->del_req(0); // Yank bogus edge
2412 if (nn != nullptr && nn->outcnt() == 0) {
2413 _worklist.push(nn);
2414 }
2415 #ifndef PRODUCT
2416 if (is_verify_def_use()) {
2417 for ( int i = 0; i < _verify_window_size; i++ ) {
2418 if ( _verify_window[i] == old )
2419 _verify_window[i] = nn;
2420 }
2421 }
2422 #endif
2423 temp->destruct(this); // reuse the _idx of this little guy
2424 }
2425
2426 //------------------------------add_users_to_worklist--------------------------
2427 void PhaseIterGVN::add_users_to_worklist0(Node* n, Unique_Node_List& worklist) {
2428 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
2429 worklist.push(n->fast_out(i)); // Push on worklist
2430 }
2431 }
2432
2433 // Return counted loop Phi if as a counted loop exit condition, cmp
2434 // compares the induction variable with n
2435 static PhiNode* countedloop_phi_from_cmp(CmpNode* cmp, Node* n) {
2436 for (DUIterator_Fast imax, i = cmp->fast_outs(imax); i < imax; i++) {
2437 Node* bol = cmp->fast_out(i);
2438 for (DUIterator_Fast i2max, i2 = bol->fast_outs(i2max); i2 < i2max; i2++) {
2439 Node* iff = bol->fast_out(i2);
2440 if (iff->is_BaseCountedLoopEnd()) {
2441 BaseCountedLoopEndNode* cle = iff->as_BaseCountedLoopEnd();
2442 if (cle->limit() == n) {
2443 PhiNode* phi = cle->phi();
2444 if (phi != nullptr) {
2445 return phi;
2461 add_users_of_use_to_worklist(n, use, worklist);
2462 }
2463 }
2464
2465 void PhaseIterGVN::add_users_of_use_to_worklist(Node* n, Node* use, Unique_Node_List& worklist) {
2466 if(use->is_Multi() || // Multi-definer? Push projs on worklist
2467 use->is_Store() ) // Enable store/load same address
2468 add_users_to_worklist0(use, worklist);
2469
2470 // If we changed the receiver type to a call, we need to revisit
2471 // the Catch following the call. It's looking for a non-null
2472 // receiver to know when to enable the regular fall-through path
2473 // in addition to the NullPtrException path.
2474 if (use->is_CallDynamicJava() && n == use->in(TypeFunc::Parms)) {
2475 Node* p = use->as_CallDynamicJava()->proj_out_or_null(TypeFunc::Control);
2476 if (p != nullptr) {
2477 add_users_to_worklist0(p, worklist);
2478 }
2479 }
2480
2481 uint use_op = use->Opcode();
2482 if(use->is_Cmp()) { // Enable CMP/BOOL optimization
2483 add_users_to_worklist0(use, worklist); // Put Bool on worklist
2484 if (use->outcnt() > 0) {
2485 Node* bol = use->raw_out(0);
2486 if (bol->outcnt() > 0) {
2487 Node* iff = bol->raw_out(0);
2488 if (iff->outcnt() == 2) {
2489 // Look for the 'is_x2logic' pattern: "x ? : 0 : 1" and put the
2490 // phi merging either 0 or 1 onto the worklist
2491 Node* ifproj0 = iff->raw_out(0);
2492 Node* ifproj1 = iff->raw_out(1);
2493 if (ifproj0->outcnt() > 0 && ifproj1->outcnt() > 0) {
2494 Node* region0 = ifproj0->raw_out(0);
2495 Node* region1 = ifproj1->raw_out(0);
2496 if( region0 == region1 )
2497 add_users_to_worklist0(region0, worklist);
2498 }
2499 }
2500 }
2558 assert(n == in2, "only in2 modified");
2559 // Find all CastII with input in1.
2560 for (DUIterator_Fast jmax, j = in1->fast_outs(jmax); j < jmax; j++) {
2561 Node* castii = in1->fast_out(j);
2562 if (castii->is_CastII() && castii->as_CastII()->carry_dependency()) {
2563 // Find If.
2564 if (castii->in(0) != nullptr && castii->in(0)->in(0) != nullptr && castii->in(0)->in(0)->is_If()) {
2565 Node* ifnode = castii->in(0)->in(0);
2566 // Check that if connects to the cmp
2567 if (ifnode->in(1) != nullptr && ifnode->in(1)->is_Bool() && ifnode->in(1)->in(1) == cmp) {
2568 worklist.push(castii);
2569 }
2570 }
2571 }
2572 }
2573 }
2574 }
2575 }
2576 }
2577
2578 // If changed Cast input, notify down for Phi, Sub, and Xor - all do "uncast"
2579 // Patterns:
2580 // ConstraintCast+ -> Sub
2581 // ConstraintCast+ -> Phi
2582 // ConstraintCast+ -> Xor
2583 if (use->is_ConstraintCast()) {
2584 auto push_the_uses_to_worklist = [&](Node* n){
2585 if (n->is_Phi() || n->is_Sub() || n->Opcode() == Op_XorI || n->Opcode() == Op_XorL) {
2586 worklist.push(n);
2587 }
2588 };
2589 auto is_boundary = [](Node* n){ return !n->is_ConstraintCast(); };
2590 use->visit_uses(push_the_uses_to_worklist, is_boundary);
2591 }
2592 // If changed LShift inputs, check RShift/URShift users for
2593 // "(X << C) >> C" sign-ext and "(X << C) >>> C" zero-ext optimizations.
2594 if (use_op == Op_LShiftI || use_op == Op_LShiftL) {
2595 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2596 Node* u = use->fast_out(i2);
2597 if (u->Opcode() == Op_RShiftI || u->Opcode() == Op_RShiftL ||
2696 // If the ValidLengthTest input changes then the fallthrough path out of the AllocateArray may have become dead.
2697 // CatchNode::Value() is responsible for killing that path. The CatchNode has to be explicitly enqueued for igvn
2698 // to guarantee the change is not missed.
2699 if (use_op == Op_AllocateArray && n == use->in(AllocateNode::ValidLengthTest)) {
2700 Node* p = use->as_AllocateArray()->proj_out_or_null(TypeFunc::Control);
2701 if (p != nullptr) {
2702 add_users_to_worklist0(p, worklist);
2703 }
2704 }
2705
2706 if (use_op == Op_Initialize) {
2707 InitializeNode* init = use->as_Initialize();
2708 init->for_each_proj(enqueue_init_mem_projs, TypeFunc::Memory);
2709 }
2710 // Loading the java mirror from a Klass requires two loads and the type
2711 // of the mirror load depends on the type of 'n'. See LoadNode::Value().
2712 // LoadBarrier?(LoadP(LoadP(AddP(foo:Klass, #java_mirror))))
2713 BarrierSetC2* bs = BarrierSet::barrier_set()->barrier_set_c2();
2714 bool has_load_barrier_nodes = bs->has_load_barrier_nodes();
2715
2716 if (use_op == Op_LoadP && use->bottom_type()->isa_rawptr()) {
2717 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2718 Node* u = use->fast_out(i2);
2719 const Type* ut = u->bottom_type();
2720 if (u->Opcode() == Op_LoadP && ut->isa_instptr()) {
2721 if (has_load_barrier_nodes) {
2722 // Search for load barriers behind the load
2723 for (DUIterator_Fast i3max, i3 = u->fast_outs(i3max); i3 < i3max; i3++) {
2724 Node* b = u->fast_out(i3);
2725 if (bs->is_gc_barrier_node(b)) {
2726 worklist.push(b);
2727 }
2728 }
2729 }
2730 worklist.push(u);
2731 }
2732 }
2733 }
2734 if (use->Opcode() == Op_OpaqueZeroTripGuard) {
2735 assert(use->outcnt() <= 1, "OpaqueZeroTripGuard can't be shared");
2736 if (use->outcnt() == 1) {
2737 Node* cmp = use->unique_out();
2738 worklist.push(cmp);
2739 }
2740 }
2741
2742 // From CastX2PNode::Ideal
2743 // CastX2P(AddX(x, y))
2744 // CastX2P(SubX(x, y))
2745 if (use->Opcode() == Op_AddX || use->Opcode() == Op_SubX) {
2746 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2747 Node* u = use->fast_out(i2);
2748 if (u->Opcode() == Op_CastX2P) {
2749 worklist.push(u);
2750 }
2751 }
2752 }
2753
2803 // Conditional Constant Propagation, ala Wegman & Zadeck
2804 PhaseCCP::PhaseCCP( PhaseIterGVN *igvn ) : PhaseIterGVN(igvn) {
2805 NOT_PRODUCT( clear_constants(); )
2806 assert( _worklist.size() == 0, "" );
2807 _phase = PhaseValuesType::ccp;
2808 analyze();
2809 }
2810
2811 #ifndef PRODUCT
2812 //------------------------------~PhaseCCP--------------------------------------
2813 PhaseCCP::~PhaseCCP() {
2814 inc_invokes();
2815 _total_constants += count_constants();
2816 }
2817 #endif
2818
2819
2820 #ifdef ASSERT
2821 void PhaseCCP::verify_type(Node* n, const Type* tnew, const Type* told) {
2822 if (tnew->meet(told) != tnew->remove_speculative()) {
2823 n->dump(1);
2824 tty->print("told = "); told->dump(); tty->cr();
2825 tty->print("tnew = "); tnew->dump(); tty->cr();
2826 fatal("Not monotonic");
2827 }
2828 assert(!told->isa_int() || !tnew->isa_int() || told->is_int()->_widen <= tnew->is_int()->_widen, "widen increases");
2829 assert(!told->isa_long() || !tnew->isa_long() || told->is_long()->_widen <= tnew->is_long()->_widen, "widen increases");
2830 }
2831 #endif //ASSERT
2832
2833 // In this analysis, all types are initially set to TOP. We iteratively call Value() on all nodes of the graph until
2834 // we reach a fixed-point (i.e. no types change anymore). We start with a list that only contains the root node. Each time
2835 // a new type is set, we push all uses of that node back to the worklist (in some cases, we also push grandchildren
2836 // or nodes even further down back to the worklist because their type could change as a result of the current type
2837 // change).
2838 void PhaseCCP::analyze() {
2839 // Initialize all types to TOP, optimistic analysis
2840 for (uint i = 0; i < C->unique(); i++) {
2841 _types.map(i, Type::TOP);
2842 }
2843
2968 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
2969 Node* use = n->fast_out(i);
2970 push_if_not_bottom_type(worklist, use);
2971 push_more_uses(worklist, n, use);
2972 }
2973 }
2974
2975 void PhaseCCP::push_if_not_bottom_type(Unique_Node_List& worklist, Node* n) const {
2976 if (n->bottom_type() != type(n)) {
2977 worklist.push(n);
2978 }
2979 }
2980
2981 // For some nodes, we need to propagate the type change to grandchildren or even further down.
2982 // Add them back to the worklist.
2983 void PhaseCCP::push_more_uses(Unique_Node_List& worklist, Node* parent, const Node* use) const {
2984 push_phis(worklist, use);
2985 push_catch(worklist, use);
2986 push_cmpu(worklist, use);
2987 push_counted_loop_phi(worklist, parent, use);
2988 push_loadp(worklist, use);
2989 push_and(worklist, parent, use);
2990 push_cast_ii(worklist, parent, use);
2991 push_opaque_zero_trip_guard(worklist, use);
2992 push_bool_with_cmpu_and_mask(worklist, use);
2993 }
2994
2995
2996 // We must recheck Phis too if use is a Region.
2997 void PhaseCCP::push_phis(Unique_Node_List& worklist, const Node* use) const {
2998 if (use->is_Region()) {
2999 for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
3000 push_if_not_bottom_type(worklist, use->fast_out(i));
3001 }
3002 }
3003 }
3004
3005 // If we changed the receiver type to a call, we need to revisit the Catch node following the call. It's looking for a
3006 // non-null receiver to know when to enable the regular fall-through path in addition to the NullPtrException path.
3007 // Same is true if the type of a ValidLengthTest input to an AllocateArrayNode changes.
3079 continue;
3080 }
3081
3082 Node* m = addI->in(1);
3083 if (m == andI->in(1) || m == andI->in(2)) {
3084 // Is "m" shared? Matched (1b) and thus we revisit Bool.
3085 push_if_not_bottom_type(worklist, bol);
3086 }
3087 }
3088 }
3089
3090 // 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'.
3091 // Seem PhiNode::Value().
3092 void PhaseCCP::push_counted_loop_phi(Unique_Node_List& worklist, Node* parent, const Node* use) {
3093 uint use_op = use->Opcode();
3094 if (use_op == Op_CmpI || use_op == Op_CmpL) {
3095 PhiNode* phi = countedloop_phi_from_cmp(use->as_Cmp(), parent);
3096 if (phi != nullptr) {
3097 worklist.push(phi);
3098 }
3099 }
3100 }
3101
3102 // Loading the java mirror from a Klass requires two loads and the type of the mirror load depends on the type of 'n'.
3103 // See LoadNode::Value().
3104 void PhaseCCP::push_loadp(Unique_Node_List& worklist, const Node* use) const {
3105 BarrierSetC2* barrier_set = BarrierSet::barrier_set()->barrier_set_c2();
3106 bool has_load_barrier_nodes = barrier_set->has_load_barrier_nodes();
3107
3108 if (use->Opcode() == Op_LoadP && use->bottom_type()->isa_rawptr()) {
3109 for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
3110 Node* loadp = use->fast_out(i);
3111 const Type* ut = loadp->bottom_type();
3112 if (loadp->Opcode() == Op_LoadP && ut->isa_instptr() && ut != type(loadp)) {
3113 if (has_load_barrier_nodes) {
3114 // Search for load barriers behind the load
3115 push_load_barrier(worklist, barrier_set, loadp);
3116 }
3117 worklist.push(loadp);
3118 }
|
1026 _worklist.print_set();
1027 }
1028 }
1029 }
1030 #endif /* ASSERT */
1031
1032 void PhaseIterGVN::optimize() {
1033 DEBUG_ONLY(uint num_processed = 0;)
1034 NOT_PRODUCT(init_verifyPhaseIterGVN();)
1035 NOT_PRODUCT(C->reset_igv_phase_iter(PHASE_AFTER_ITER_GVN_STEP);)
1036 C->print_method(PHASE_BEFORE_ITER_GVN, 3);
1037 if (StressIGVN) {
1038 shuffle_worklist();
1039 }
1040
1041 // The node count check in the loop below (check_node_count) assumes that we
1042 // increase the live node count with at most
1043 // max_live_nodes_increase_per_iteration in between checks. If this
1044 // assumption does not hold, there is a risk that we exceed the max node
1045 // limit in between checks and trigger an assert during node creation.
1046 const int max_live_nodes_increase_per_iteration = NodeLimitFudgeFactor * 5;
1047
1048 uint loop_count = 0;
1049 // Pull from worklist and transform the node. If the node has changed,
1050 // update edge info and put uses on worklist.
1051 while (_worklist.size() > 0) {
1052 if (C->check_node_count(max_live_nodes_increase_per_iteration, "Out of nodes")) {
1053 C->print_method(PHASE_AFTER_ITER_GVN, 3);
1054 return;
1055 }
1056 Node* n = _worklist.pop();
1057 if (loop_count >= K * C->live_nodes()) {
1058 DEBUG_ONLY(dump_infinite_loop_info(n, "PhaseIterGVN::optimize");)
1059 C->record_method_not_compilable("infinite loop in PhaseIterGVN::optimize");
1060 C->print_method(PHASE_AFTER_ITER_GVN, 3);
1061 return;
1062 }
1063 DEBUG_ONLY(trace_PhaseIterGVN_verbose(n, num_processed++);)
1064 if (n->outcnt() != 0) {
1065 NOT_PRODUCT(const Type* oldtype = type_or_null(n));
1066 // Do the transformation
1187 // SubNode::Value
1188 // CmpPNode::sub
1189 // MemNode::detect_ptr_independence
1190 // MemNode::all_controls_dominate
1191 // We find all controls of a pointer load, and see if they dominate the control of
1192 // an allocation. If they all dominate, we know the allocation is after (independent)
1193 // of the pointer load, and we can say the pointers are different. For this we call
1194 // n->dominates(sub, nlist) to check if controls n of the pointer load dominate the
1195 // control sub of the allocation. The problems is that sometimes dominates answers
1196 // false conservatively, and later it can determine that it is indeed true. Loops with
1197 // Region heads can lead to giving up, whereas LoopNodes can be skipped easier, and
1198 // so the traversal becomes more powerful. This is difficult to remedy, we would have
1199 // to notify the CmpP of CFG updates. Luckily, we recompute CmpP::Value during CCP
1200 // after loop-opts, so that should take care of many of these cases.
1201 return;
1202 }
1203
1204 stringStream ss; // Print as a block without tty lock.
1205 ss.cr();
1206 ss.print_cr("Missed Value optimization:");
1207 n->dump_bfs(3, nullptr, "", &ss);
1208 ss.print_cr("Current type:");
1209 told->dump_on(&ss);
1210 ss.cr();
1211 ss.print_cr("Optimized type:");
1212 tnew->dump_on(&ss);
1213 ss.cr();
1214 tty->print_cr("%s", ss.as_string());
1215
1216 switch (_phase) {
1217 case PhaseValuesType::iter_gvn:
1218 assert(false, "Missed Value optimization opportunity in PhaseIterGVN for %s",n->Name());
1219 break;
1220 case PhaseValuesType::ccp:
1221 assert(false, "PhaseCCP not at fixpoint: analysis result may be unsound for %s", n->Name());
1222 break;
1223 default:
1224 assert(false, "Unexpected phase");
1225 break;
1226 }
1227 }
2110 assert(false, "Broken node invariant for %s", n->Name());
2111 }
2112 }
2113 }
2114 #endif
2115
2116 /**
2117 * Register a new node with the optimizer. Update the types array, the def-use
2118 * info. Put on worklist.
2119 */
2120 Node* PhaseIterGVN::register_new_node_with_optimizer(Node* n, Node* orig) {
2121 set_type_bottom(n);
2122 _worklist.push(n);
2123 if (orig != nullptr) C->copy_node_notes_to(n, orig);
2124 return n;
2125 }
2126
2127 //------------------------------transform--------------------------------------
2128 // Non-recursive: idealize Node 'n' with respect to its inputs and its value
2129 Node *PhaseIterGVN::transform( Node *n ) {
2130 // If brand new node, make space in type array, and give it a type.
2131 ensure_type_or_null(n);
2132 if (type_or_null(n) == nullptr) {
2133 set_type_bottom(n);
2134 }
2135
2136 if (_delay_transform) {
2137 // Add the node to the worklist but don't optimize for now
2138 _worklist.push(n);
2139 return n;
2140 }
2141
2142 return transform_old(n);
2143 }
2144
2145 Node *PhaseIterGVN::transform_old(Node* n) {
2146 NOT_PRODUCT(set_transforms());
2147 // Remove 'n' from hash table in case it gets modified
2148 _table.hash_delete(n);
2149 #ifdef ASSERT
2150 if (is_verify_def_use()) {
2151 assert(!_table.find_index(n->_idx), "found duplicate entry in table");
2152 }
2153 #endif
2154
2155 // Allow Bool -> Cmp idealisation in late inlining intrinsics that return a bool
2156 if (n->is_Cmp()) {
2157 add_users_to_worklist(n);
2158 }
2159
2160 // Apply the Ideal call in a loop until it no longer applies
2161 Node* k = n;
2406
2407 // Smash all inputs to 'old', isolating him completely
2408 Node *temp = new Node(1);
2409 temp->init_req(0,nn); // Add a use to nn to prevent him from dying
2410 remove_dead_node( old );
2411 temp->del_req(0); // Yank bogus edge
2412 if (nn != nullptr && nn->outcnt() == 0) {
2413 _worklist.push(nn);
2414 }
2415 #ifndef PRODUCT
2416 if (is_verify_def_use()) {
2417 for ( int i = 0; i < _verify_window_size; i++ ) {
2418 if ( _verify_window[i] == old )
2419 _verify_window[i] = nn;
2420 }
2421 }
2422 #endif
2423 temp->destruct(this); // reuse the _idx of this little guy
2424 }
2425
2426 void PhaseIterGVN::replace_in_uses(Node* n, Node* m) {
2427 assert(n != nullptr, "sanity");
2428 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
2429 Node* u = n->fast_out(i);
2430 if (u != n) {
2431 rehash_node_delayed(u);
2432 int nb = u->replace_edge(n, m);
2433 --i, imax -= nb;
2434 }
2435 }
2436 assert(n->outcnt() == 0, "all uses must be deleted");
2437 }
2438
2439 //------------------------------add_users_to_worklist--------------------------
2440 void PhaseIterGVN::add_users_to_worklist0(Node* n, Unique_Node_List& worklist) {
2441 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
2442 worklist.push(n->fast_out(i)); // Push on worklist
2443 }
2444 }
2445
2446 // Return counted loop Phi if as a counted loop exit condition, cmp
2447 // compares the induction variable with n
2448 static PhiNode* countedloop_phi_from_cmp(CmpNode* cmp, Node* n) {
2449 for (DUIterator_Fast imax, i = cmp->fast_outs(imax); i < imax; i++) {
2450 Node* bol = cmp->fast_out(i);
2451 for (DUIterator_Fast i2max, i2 = bol->fast_outs(i2max); i2 < i2max; i2++) {
2452 Node* iff = bol->fast_out(i2);
2453 if (iff->is_BaseCountedLoopEnd()) {
2454 BaseCountedLoopEndNode* cle = iff->as_BaseCountedLoopEnd();
2455 if (cle->limit() == n) {
2456 PhiNode* phi = cle->phi();
2457 if (phi != nullptr) {
2458 return phi;
2474 add_users_of_use_to_worklist(n, use, worklist);
2475 }
2476 }
2477
2478 void PhaseIterGVN::add_users_of_use_to_worklist(Node* n, Node* use, Unique_Node_List& worklist) {
2479 if(use->is_Multi() || // Multi-definer? Push projs on worklist
2480 use->is_Store() ) // Enable store/load same address
2481 add_users_to_worklist0(use, worklist);
2482
2483 // If we changed the receiver type to a call, we need to revisit
2484 // the Catch following the call. It's looking for a non-null
2485 // receiver to know when to enable the regular fall-through path
2486 // in addition to the NullPtrException path.
2487 if (use->is_CallDynamicJava() && n == use->in(TypeFunc::Parms)) {
2488 Node* p = use->as_CallDynamicJava()->proj_out_or_null(TypeFunc::Control);
2489 if (p != nullptr) {
2490 add_users_to_worklist0(p, worklist);
2491 }
2492 }
2493
2494 // AndLNode::Ideal folds GraphKit::mark_word_test patterns. Give it a chance to run.
2495 if (n->is_Load() && use->is_Phi()) {
2496 for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
2497 Node* u = use->fast_out(i);
2498 if (u->Opcode() == Op_AndL) {
2499 worklist.push(u);
2500 }
2501 }
2502 }
2503
2504 uint use_op = use->Opcode();
2505 if(use->is_Cmp()) { // Enable CMP/BOOL optimization
2506 add_users_to_worklist0(use, worklist); // Put Bool on worklist
2507 if (use->outcnt() > 0) {
2508 Node* bol = use->raw_out(0);
2509 if (bol->outcnt() > 0) {
2510 Node* iff = bol->raw_out(0);
2511 if (iff->outcnt() == 2) {
2512 // Look for the 'is_x2logic' pattern: "x ? : 0 : 1" and put the
2513 // phi merging either 0 or 1 onto the worklist
2514 Node* ifproj0 = iff->raw_out(0);
2515 Node* ifproj1 = iff->raw_out(1);
2516 if (ifproj0->outcnt() > 0 && ifproj1->outcnt() > 0) {
2517 Node* region0 = ifproj0->raw_out(0);
2518 Node* region1 = ifproj1->raw_out(0);
2519 if( region0 == region1 )
2520 add_users_to_worklist0(region0, worklist);
2521 }
2522 }
2523 }
2581 assert(n == in2, "only in2 modified");
2582 // Find all CastII with input in1.
2583 for (DUIterator_Fast jmax, j = in1->fast_outs(jmax); j < jmax; j++) {
2584 Node* castii = in1->fast_out(j);
2585 if (castii->is_CastII() && castii->as_CastII()->carry_dependency()) {
2586 // Find If.
2587 if (castii->in(0) != nullptr && castii->in(0)->in(0) != nullptr && castii->in(0)->in(0)->is_If()) {
2588 Node* ifnode = castii->in(0)->in(0);
2589 // Check that if connects to the cmp
2590 if (ifnode->in(1) != nullptr && ifnode->in(1)->is_Bool() && ifnode->in(1)->in(1) == cmp) {
2591 worklist.push(castii);
2592 }
2593 }
2594 }
2595 }
2596 }
2597 }
2598 }
2599 }
2600
2601 // Inline type nodes can have other inline types as users. If an input gets
2602 // updated, make sure that inline type users get a chance for optimization.
2603 if (use->is_InlineType() || use->is_DecodeN()) {
2604 auto push_the_uses_to_worklist = [&](Node* n){
2605 if (n->is_InlineType()) {
2606 worklist.push(n);
2607 }
2608 };
2609 auto is_boundary = [](Node* n){ return !n->is_InlineType(); };
2610 use->visit_uses(push_the_uses_to_worklist, is_boundary, true);
2611 }
2612 // If changed Cast input, notify down for Phi, Sub, and Xor - all do "uncast"
2613 // Patterns:
2614 // ConstraintCast+ -> Sub
2615 // ConstraintCast+ -> Phi
2616 // ConstraintCast+ -> Xor
2617 if (use->is_ConstraintCast()) {
2618 auto push_the_uses_to_worklist = [&](Node* n){
2619 if (n->is_Phi() || n->is_Sub() || n->Opcode() == Op_XorI || n->Opcode() == Op_XorL) {
2620 worklist.push(n);
2621 }
2622 };
2623 auto is_boundary = [](Node* n){ return !n->is_ConstraintCast(); };
2624 use->visit_uses(push_the_uses_to_worklist, is_boundary);
2625 }
2626 // If changed LShift inputs, check RShift/URShift users for
2627 // "(X << C) >> C" sign-ext and "(X << C) >>> C" zero-ext optimizations.
2628 if (use_op == Op_LShiftI || use_op == Op_LShiftL) {
2629 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2630 Node* u = use->fast_out(i2);
2631 if (u->Opcode() == Op_RShiftI || u->Opcode() == Op_RShiftL ||
2730 // If the ValidLengthTest input changes then the fallthrough path out of the AllocateArray may have become dead.
2731 // CatchNode::Value() is responsible for killing that path. The CatchNode has to be explicitly enqueued for igvn
2732 // to guarantee the change is not missed.
2733 if (use_op == Op_AllocateArray && n == use->in(AllocateNode::ValidLengthTest)) {
2734 Node* p = use->as_AllocateArray()->proj_out_or_null(TypeFunc::Control);
2735 if (p != nullptr) {
2736 add_users_to_worklist0(p, worklist);
2737 }
2738 }
2739
2740 if (use_op == Op_Initialize) {
2741 InitializeNode* init = use->as_Initialize();
2742 init->for_each_proj(enqueue_init_mem_projs, TypeFunc::Memory);
2743 }
2744 // Loading the java mirror from a Klass requires two loads and the type
2745 // of the mirror load depends on the type of 'n'. See LoadNode::Value().
2746 // LoadBarrier?(LoadP(LoadP(AddP(foo:Klass, #java_mirror))))
2747 BarrierSetC2* bs = BarrierSet::barrier_set()->barrier_set_c2();
2748 bool has_load_barrier_nodes = bs->has_load_barrier_nodes();
2749
2750 if (use_op == Op_CastP2X) {
2751 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2752 Node* u = use->fast_out(i2);
2753 // TODO 8350865 Still needed? Yes, I think this is from PhaseMacroExpand::expand_mh_intrinsic_return
2754 if (u->Opcode() == Op_AndX) {
2755 worklist.push(u);
2756 }
2757 // Search for CmpL(OrL(CastP2X(..), CastP2X(..)), 0L)
2758 if (u->Opcode() == Op_OrL) {
2759 for (DUIterator_Fast i3max, i3 = u->fast_outs(i3max); i3 < i3max; i3++) {
2760 Node* cmp = u->fast_out(i3);
2761 if (cmp->Opcode() == Op_CmpL) {
2762 worklist.push(cmp);
2763 }
2764 }
2765 }
2766 }
2767 }
2768 if (use_op == Op_LoadP && use->bottom_type()->isa_rawptr()) {
2769 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2770 Node* u = use->fast_out(i2);
2771 const Type* ut = u->bottom_type();
2772 if (u->Opcode() == Op_LoadP && ut->isa_instptr()) {
2773 if (has_load_barrier_nodes) {
2774 // Search for load barriers behind the load
2775 for (DUIterator_Fast i3max, i3 = u->fast_outs(i3max); i3 < i3max; i3++) {
2776 Node* b = u->fast_out(i3);
2777 if (bs->is_gc_barrier_node(b)) {
2778 worklist.push(b);
2779 }
2780 }
2781 }
2782 worklist.push(u);
2783 }
2784 }
2785 }
2786 // Give CallStaticJavaNode::remove_useless_allocation a chance to run
2787 if (use->is_Region()) {
2788 Node* c = use;
2789 do {
2790 c = c->unique_ctrl_out_or_null();
2791 } while (c != nullptr && c->is_Region());
2792 if (c != nullptr && c->is_CallStaticJava() && c->as_CallStaticJava()->uncommon_trap_request() != 0) {
2793 worklist.push(c);
2794 }
2795 }
2796 if (use->Opcode() == Op_OpaqueZeroTripGuard) {
2797 assert(use->outcnt() <= 1, "OpaqueZeroTripGuard can't be shared");
2798 if (use->outcnt() == 1) {
2799 Node* cmp = use->unique_out();
2800 worklist.push(cmp);
2801 }
2802 }
2803
2804 // From CastX2PNode::Ideal
2805 // CastX2P(AddX(x, y))
2806 // CastX2P(SubX(x, y))
2807 if (use->Opcode() == Op_AddX || use->Opcode() == Op_SubX) {
2808 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2809 Node* u = use->fast_out(i2);
2810 if (u->Opcode() == Op_CastX2P) {
2811 worklist.push(u);
2812 }
2813 }
2814 }
2815
2865 // Conditional Constant Propagation, ala Wegman & Zadeck
2866 PhaseCCP::PhaseCCP( PhaseIterGVN *igvn ) : PhaseIterGVN(igvn) {
2867 NOT_PRODUCT( clear_constants(); )
2868 assert( _worklist.size() == 0, "" );
2869 _phase = PhaseValuesType::ccp;
2870 analyze();
2871 }
2872
2873 #ifndef PRODUCT
2874 //------------------------------~PhaseCCP--------------------------------------
2875 PhaseCCP::~PhaseCCP() {
2876 inc_invokes();
2877 _total_constants += count_constants();
2878 }
2879 #endif
2880
2881
2882 #ifdef ASSERT
2883 void PhaseCCP::verify_type(Node* n, const Type* tnew, const Type* told) {
2884 if (tnew->meet(told) != tnew->remove_speculative()) {
2885 n->dump(3);
2886 tty->print("told = "); told->dump(); tty->cr();
2887 tty->print("tnew = "); tnew->dump(); tty->cr();
2888 fatal("Not monotonic");
2889 }
2890 assert(!told->isa_int() || !tnew->isa_int() || told->is_int()->_widen <= tnew->is_int()->_widen, "widen increases");
2891 assert(!told->isa_long() || !tnew->isa_long() || told->is_long()->_widen <= tnew->is_long()->_widen, "widen increases");
2892 }
2893 #endif //ASSERT
2894
2895 // In this analysis, all types are initially set to TOP. We iteratively call Value() on all nodes of the graph until
2896 // we reach a fixed-point (i.e. no types change anymore). We start with a list that only contains the root node. Each time
2897 // a new type is set, we push all uses of that node back to the worklist (in some cases, we also push grandchildren
2898 // or nodes even further down back to the worklist because their type could change as a result of the current type
2899 // change).
2900 void PhaseCCP::analyze() {
2901 // Initialize all types to TOP, optimistic analysis
2902 for (uint i = 0; i < C->unique(); i++) {
2903 _types.map(i, Type::TOP);
2904 }
2905
3030 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
3031 Node* use = n->fast_out(i);
3032 push_if_not_bottom_type(worklist, use);
3033 push_more_uses(worklist, n, use);
3034 }
3035 }
3036
3037 void PhaseCCP::push_if_not_bottom_type(Unique_Node_List& worklist, Node* n) const {
3038 if (n->bottom_type() != type(n)) {
3039 worklist.push(n);
3040 }
3041 }
3042
3043 // For some nodes, we need to propagate the type change to grandchildren or even further down.
3044 // Add them back to the worklist.
3045 void PhaseCCP::push_more_uses(Unique_Node_List& worklist, Node* parent, const Node* use) const {
3046 push_phis(worklist, use);
3047 push_catch(worklist, use);
3048 push_cmpu(worklist, use);
3049 push_counted_loop_phi(worklist, parent, use);
3050 push_cast(worklist, use);
3051 push_loadp(worklist, use);
3052 push_and(worklist, parent, use);
3053 push_cast_ii(worklist, parent, use);
3054 push_opaque_zero_trip_guard(worklist, use);
3055 push_bool_with_cmpu_and_mask(worklist, use);
3056 }
3057
3058
3059 // We must recheck Phis too if use is a Region.
3060 void PhaseCCP::push_phis(Unique_Node_List& worklist, const Node* use) const {
3061 if (use->is_Region()) {
3062 for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
3063 push_if_not_bottom_type(worklist, use->fast_out(i));
3064 }
3065 }
3066 }
3067
3068 // If we changed the receiver type to a call, we need to revisit the Catch node following the call. It's looking for a
3069 // non-null receiver to know when to enable the regular fall-through path in addition to the NullPtrException path.
3070 // Same is true if the type of a ValidLengthTest input to an AllocateArrayNode changes.
3142 continue;
3143 }
3144
3145 Node* m = addI->in(1);
3146 if (m == andI->in(1) || m == andI->in(2)) {
3147 // Is "m" shared? Matched (1b) and thus we revisit Bool.
3148 push_if_not_bottom_type(worklist, bol);
3149 }
3150 }
3151 }
3152
3153 // 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'.
3154 // Seem PhiNode::Value().
3155 void PhaseCCP::push_counted_loop_phi(Unique_Node_List& worklist, Node* parent, const Node* use) {
3156 uint use_op = use->Opcode();
3157 if (use_op == Op_CmpI || use_op == Op_CmpL) {
3158 PhiNode* phi = countedloop_phi_from_cmp(use->as_Cmp(), parent);
3159 if (phi != nullptr) {
3160 worklist.push(phi);
3161 }
3162 }
3163 }
3164
3165 // TODO 8350865 Still needed? Yes, I think this is from PhaseMacroExpand::expand_mh_intrinsic_return
3166 void PhaseCCP::push_cast(Unique_Node_List& worklist, const Node* use) {
3167 uint use_op = use->Opcode();
3168 if (use_op == Op_CastP2X) {
3169 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
3170 Node* u = use->fast_out(i2);
3171 if (u->Opcode() == Op_AndX) {
3172 worklist.push(u);
3173 }
3174 }
3175 }
3176 }
3177
3178 // Loading the java mirror from a Klass requires two loads and the type of the mirror load depends on the type of 'n'.
3179 // See LoadNode::Value().
3180 void PhaseCCP::push_loadp(Unique_Node_List& worklist, const Node* use) const {
3181 BarrierSetC2* barrier_set = BarrierSet::barrier_set()->barrier_set_c2();
3182 bool has_load_barrier_nodes = barrier_set->has_load_barrier_nodes();
3183
3184 if (use->Opcode() == Op_LoadP && use->bottom_type()->isa_rawptr()) {
3185 for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
3186 Node* loadp = use->fast_out(i);
3187 const Type* ut = loadp->bottom_type();
3188 if (loadp->Opcode() == Op_LoadP && ut->isa_instptr() && ut != type(loadp)) {
3189 if (has_load_barrier_nodes) {
3190 // Search for load barriers behind the load
3191 push_load_barrier(worklist, barrier_set, loadp);
3192 }
3193 worklist.push(loadp);
3194 }
|