1022 _worklist.print_set();
1023 }
1024 }
1025 }
1026 #endif /* ASSERT */
1027
1028 void PhaseIterGVN::optimize() {
1029 DEBUG_ONLY(uint num_processed = 0;)
1030 NOT_PRODUCT(init_verifyPhaseIterGVN();)
1031 NOT_PRODUCT(C->reset_igv_phase_iter(PHASE_AFTER_ITER_GVN_STEP);)
1032 C->print_method(PHASE_BEFORE_ITER_GVN, 3);
1033 if (StressIGVN) {
1034 shuffle_worklist();
1035 }
1036
1037 // The node count check in the loop below (check_node_count) assumes that we
1038 // increase the live node count with at most
1039 // max_live_nodes_increase_per_iteration in between checks. If this
1040 // assumption does not hold, there is a risk that we exceed the max node
1041 // limit in between checks and trigger an assert during node creation.
1042 const int max_live_nodes_increase_per_iteration = NodeLimitFudgeFactor * 3;
1043
1044 uint loop_count = 0;
1045 // Pull from worklist and transform the node. If the node has changed,
1046 // update edge info and put uses on worklist.
1047 while (_worklist.size() > 0) {
1048 if (C->check_node_count(max_live_nodes_increase_per_iteration, "Out of nodes")) {
1049 C->print_method(PHASE_AFTER_ITER_GVN, 3);
1050 return;
1051 }
1052 Node* n = _worklist.pop();
1053 if (loop_count >= K * C->live_nodes()) {
1054 DEBUG_ONLY(dump_infinite_loop_info(n, "PhaseIterGVN::optimize");)
1055 C->record_method_not_compilable("infinite loop in PhaseIterGVN::optimize");
1056 C->print_method(PHASE_AFTER_ITER_GVN, 3);
1057 return;
1058 }
1059 DEBUG_ONLY(trace_PhaseIterGVN_verbose(n, num_processed++);)
1060 if (n->outcnt() != 0) {
1061 NOT_PRODUCT(const Type* oldtype = type_or_null(n));
1062 // Do the transformation
1176 // SubNode::Value
1177 // CmpPNode::sub
1178 // MemNode::detect_ptr_independence
1179 // MemNode::all_controls_dominate
1180 // We find all controls of a pointer load, and see if they dominate the control of
1181 // an allocation. If they all dominate, we know the allocation is after (independent)
1182 // of the pointer load, and we can say the pointers are different. For this we call
1183 // n->dominates(sub, nlist) to check if controls n of the pointer load dominate the
1184 // control sub of the allocation. The problems is that sometimes dominates answers
1185 // false conservatively, and later it can determine that it is indeed true. Loops with
1186 // Region heads can lead to giving up, whereas LoopNodes can be skipped easier, and
1187 // so the traversal becomes more powerful. This is difficult to remidy, we would have
1188 // to notify the CmpP of CFG updates. Luckily, we recompute CmpP::Value during CCP
1189 // after loop-opts, so that should take care of many of these cases.
1190 return false;
1191 }
1192
1193 stringStream ss; // Print as a block without tty lock.
1194 ss.cr();
1195 ss.print_cr("Missed Value optimization:");
1196 n->dump_bfs(1, nullptr, "", &ss);
1197 ss.print_cr("Current type:");
1198 told->dump_on(&ss);
1199 ss.cr();
1200 ss.print_cr("Optimized type:");
1201 tnew->dump_on(&ss);
1202 ss.cr();
1203 tty->print_cr("%s", ss.as_string());
1204 return true;
1205 }
1206
1207 // Check that all Ideal optimizations that could be done were done.
1208 // Returns true if it found missed optimization opportunities and
1209 // false otherwise (no missed optimization, or skipped verification).
1210 bool PhaseIterGVN::verify_Ideal_for(Node* n, bool can_reshape) {
1211 // First, we check a list of exceptions, where we skip verification,
1212 // because there are known cases where Ideal can optimize after IGVN.
1213 // Some may be expected and cannot be fixed, and others should be fixed.
1214 switch (n->Opcode()) {
1215 // RangeCheckNode::Ideal looks up the chain for about 999 nodes
1216 // (see "Range-Check scan limit"). So, it is possible that something
2084 }
2085 }
2086 return false;
2087 }
2088 #endif
2089
2090 /**
2091 * Register a new node with the optimizer. Update the types array, the def-use
2092 * info. Put on worklist.
2093 */
2094 Node* PhaseIterGVN::register_new_node_with_optimizer(Node* n, Node* orig) {
2095 set_type_bottom(n);
2096 _worklist.push(n);
2097 if (orig != nullptr) C->copy_node_notes_to(n, orig);
2098 return n;
2099 }
2100
2101 //------------------------------transform--------------------------------------
2102 // Non-recursive: idealize Node 'n' with respect to its inputs and its value
2103 Node *PhaseIterGVN::transform( Node *n ) {
2104 if (_delay_transform) {
2105 // Register the node but don't optimize for now
2106 register_new_node_with_optimizer(n);
2107 return n;
2108 }
2109
2110 // If brand new node, make space in type array, and give it a type.
2111 ensure_type_or_null(n);
2112 if (type_or_null(n) == nullptr) {
2113 set_type_bottom(n);
2114 }
2115
2116 return transform_old(n);
2117 }
2118
2119 Node *PhaseIterGVN::transform_old(Node* n) {
2120 NOT_PRODUCT(set_transforms());
2121 // Remove 'n' from hash table in case it gets modified
2122 _table.hash_delete(n);
2123 #ifdef ASSERT
2124 if (is_verify_def_use()) {
2125 assert(!_table.find_index(n->_idx), "found duplicate entry in table");
2126 }
2127 #endif
2128
2129 // Allow Bool -> Cmp idealisation in late inlining intrinsics that return a bool
2130 if (n->is_Cmp()) {
2131 add_users_to_worklist(n);
2132 }
2133
2134 // Apply the Ideal call in a loop until it no longer applies
2135 Node* k = n;
2368
2369 // Smash all inputs to 'old', isolating him completely
2370 Node *temp = new Node(1);
2371 temp->init_req(0,nn); // Add a use to nn to prevent him from dying
2372 remove_dead_node( old );
2373 temp->del_req(0); // Yank bogus edge
2374 if (nn != nullptr && nn->outcnt() == 0) {
2375 _worklist.push(nn);
2376 }
2377 #ifndef PRODUCT
2378 if (is_verify_def_use()) {
2379 for ( int i = 0; i < _verify_window_size; i++ ) {
2380 if ( _verify_window[i] == old )
2381 _verify_window[i] = nn;
2382 }
2383 }
2384 #endif
2385 temp->destruct(this); // reuse the _idx of this little guy
2386 }
2387
2388 //------------------------------add_users_to_worklist--------------------------
2389 void PhaseIterGVN::add_users_to_worklist0(Node* n, Unique_Node_List& worklist) {
2390 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
2391 worklist.push(n->fast_out(i)); // Push on worklist
2392 }
2393 }
2394
2395 // Return counted loop Phi if as a counted loop exit condition, cmp
2396 // compares the induction variable with n
2397 static PhiNode* countedloop_phi_from_cmp(CmpNode* cmp, Node* n) {
2398 for (DUIterator_Fast imax, i = cmp->fast_outs(imax); i < imax; i++) {
2399 Node* bol = cmp->fast_out(i);
2400 for (DUIterator_Fast i2max, i2 = bol->fast_outs(i2max); i2 < i2max; i2++) {
2401 Node* iff = bol->fast_out(i2);
2402 if (iff->is_BaseCountedLoopEnd()) {
2403 BaseCountedLoopEndNode* cle = iff->as_BaseCountedLoopEnd();
2404 if (cle->limit() == n) {
2405 PhiNode* phi = cle->phi();
2406 if (phi != nullptr) {
2407 return phi;
2423 add_users_of_use_to_worklist(n, use, worklist);
2424 }
2425 }
2426
2427 void PhaseIterGVN::add_users_of_use_to_worklist(Node* n, Node* use, Unique_Node_List& worklist) {
2428 if(use->is_Multi() || // Multi-definer? Push projs on worklist
2429 use->is_Store() ) // Enable store/load same address
2430 add_users_to_worklist0(use, worklist);
2431
2432 // If we changed the receiver type to a call, we need to revisit
2433 // the Catch following the call. It's looking for a non-null
2434 // receiver to know when to enable the regular fall-through path
2435 // in addition to the NullPtrException path.
2436 if (use->is_CallDynamicJava() && n == use->in(TypeFunc::Parms)) {
2437 Node* p = use->as_CallDynamicJava()->proj_out_or_null(TypeFunc::Control);
2438 if (p != nullptr) {
2439 add_users_to_worklist0(p, worklist);
2440 }
2441 }
2442
2443 uint use_op = use->Opcode();
2444 if(use->is_Cmp()) { // Enable CMP/BOOL optimization
2445 add_users_to_worklist0(use, worklist); // Put Bool on worklist
2446 if (use->outcnt() > 0) {
2447 Node* bol = use->raw_out(0);
2448 if (bol->outcnt() > 0) {
2449 Node* iff = bol->raw_out(0);
2450 if (iff->outcnt() == 2) {
2451 // Look for the 'is_x2logic' pattern: "x ? : 0 : 1" and put the
2452 // phi merging either 0 or 1 onto the worklist
2453 Node* ifproj0 = iff->raw_out(0);
2454 Node* ifproj1 = iff->raw_out(1);
2455 if (ifproj0->outcnt() > 0 && ifproj1->outcnt() > 0) {
2456 Node* region0 = ifproj0->raw_out(0);
2457 Node* region1 = ifproj1->raw_out(0);
2458 if( region0 == region1 )
2459 add_users_to_worklist0(region0, worklist);
2460 }
2461 }
2462 }
2520 assert(n == in2, "only in2 modified");
2521 // Find all CastII with input in1.
2522 for (DUIterator_Fast jmax, j = in1->fast_outs(jmax); j < jmax; j++) {
2523 Node* castii = in1->fast_out(j);
2524 if (castii->is_CastII() && castii->as_CastII()->carry_dependency()) {
2525 // Find If.
2526 if (castii->in(0) != nullptr && castii->in(0)->in(0) != nullptr && castii->in(0)->in(0)->is_If()) {
2527 Node* ifnode = castii->in(0)->in(0);
2528 // Check that if connects to the cmp
2529 if (ifnode->in(1) != nullptr && ifnode->in(1)->is_Bool() && ifnode->in(1)->in(1) == cmp) {
2530 worklist.push(castii);
2531 }
2532 }
2533 }
2534 }
2535 }
2536 }
2537 }
2538 }
2539
2540 // If changed Cast input, notify down for Phi, Sub, and Xor - all do "uncast"
2541 // Patterns:
2542 // ConstraintCast+ -> Sub
2543 // ConstraintCast+ -> Phi
2544 // ConstraintCast+ -> Xor
2545 if (use->is_ConstraintCast()) {
2546 auto push_the_uses_to_worklist = [&](Node* n){
2547 if (n->is_Phi() || n->is_Sub() || n->Opcode() == Op_XorI || n->Opcode() == Op_XorL) {
2548 worklist.push(n);
2549 }
2550 };
2551 auto is_boundary = [](Node* n){ return !n->is_ConstraintCast(); };
2552 use->visit_uses(push_the_uses_to_worklist, is_boundary);
2553 }
2554 // If changed LShift inputs, check RShift users for useless sign-ext
2555 if (use_op == Op_LShiftI || use_op == Op_LShiftL) {
2556 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2557 Node* u = use->fast_out(i2);
2558 if (u->Opcode() == Op_RShiftI || u->Opcode() == Op_RShiftL)
2559 worklist.push(u);
2655 // If the ValidLengthTest input changes then the fallthrough path out of the AllocateArray may have become dead.
2656 // CatchNode::Value() is responsible for killing that path. The CatchNode has to be explicitly enqueued for igvn
2657 // to guarantee the change is not missed.
2658 if (use_op == Op_AllocateArray && n == use->in(AllocateNode::ValidLengthTest)) {
2659 Node* p = use->as_AllocateArray()->proj_out_or_null(TypeFunc::Control);
2660 if (p != nullptr) {
2661 add_users_to_worklist0(p, worklist);
2662 }
2663 }
2664
2665 if (use_op == Op_Initialize) {
2666 InitializeNode* init = use->as_Initialize();
2667 init->for_each_proj(enqueue_init_mem_projs, TypeFunc::Memory);
2668 }
2669 // Loading the java mirror from a Klass requires two loads and the type
2670 // of the mirror load depends on the type of 'n'. See LoadNode::Value().
2671 // LoadBarrier?(LoadP(LoadP(AddP(foo:Klass, #java_mirror))))
2672 BarrierSetC2* bs = BarrierSet::barrier_set()->barrier_set_c2();
2673 bool has_load_barrier_nodes = bs->has_load_barrier_nodes();
2674
2675 if (use_op == Op_LoadP && use->bottom_type()->isa_rawptr()) {
2676 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2677 Node* u = use->fast_out(i2);
2678 const Type* ut = u->bottom_type();
2679 if (u->Opcode() == Op_LoadP && ut->isa_instptr()) {
2680 if (has_load_barrier_nodes) {
2681 // Search for load barriers behind the load
2682 for (DUIterator_Fast i3max, i3 = u->fast_outs(i3max); i3 < i3max; i3++) {
2683 Node* b = u->fast_out(i3);
2684 if (bs->is_gc_barrier_node(b)) {
2685 worklist.push(b);
2686 }
2687 }
2688 }
2689 worklist.push(u);
2690 }
2691 }
2692 }
2693 if (use->Opcode() == Op_OpaqueZeroTripGuard) {
2694 assert(use->outcnt() <= 1, "OpaqueZeroTripGuard can't be shared");
2695 if (use->outcnt() == 1) {
2696 Node* cmp = use->unique_out();
2697 worklist.push(cmp);
2698 }
2699 }
2700
2701 // From CastX2PNode::Ideal
2702 // CastX2P(AddX(x, y))
2703 // CastX2P(SubX(x, y))
2704 if (use->Opcode() == Op_AddX || use->Opcode() == Op_SubX) {
2705 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2706 Node* u = use->fast_out(i2);
2707 if (u->Opcode() == Op_CastX2P) {
2708 worklist.push(u);
2709 }
2710 }
2711 }
2712
2792 //------------------------------PhaseCCP---------------------------------------
2793 // Conditional Constant Propagation, ala Wegman & Zadeck
2794 PhaseCCP::PhaseCCP( PhaseIterGVN *igvn ) : PhaseIterGVN(igvn) {
2795 NOT_PRODUCT( clear_constants(); )
2796 assert( _worklist.size() == 0, "" );
2797 analyze();
2798 }
2799
2800 #ifndef PRODUCT
2801 //------------------------------~PhaseCCP--------------------------------------
2802 PhaseCCP::~PhaseCCP() {
2803 inc_invokes();
2804 _total_constants += count_constants();
2805 }
2806 #endif
2807
2808
2809 #ifdef ASSERT
2810 void PhaseCCP::verify_type(Node* n, const Type* tnew, const Type* told) {
2811 if (tnew->meet(told) != tnew->remove_speculative()) {
2812 n->dump(1);
2813 tty->print("told = "); told->dump(); tty->cr();
2814 tty->print("tnew = "); tnew->dump(); tty->cr();
2815 fatal("Not monotonic");
2816 }
2817 assert(!told->isa_int() || !tnew->isa_int() || told->is_int()->_widen <= tnew->is_int()->_widen, "widen increases");
2818 assert(!told->isa_long() || !tnew->isa_long() || told->is_long()->_widen <= tnew->is_long()->_widen, "widen increases");
2819 }
2820 #endif //ASSERT
2821
2822 // In this analysis, all types are initially set to TOP. We iteratively call Value() on all nodes of the graph until
2823 // we reach a fixed-point (i.e. no types change anymore). We start with a list that only contains the root node. Each time
2824 // a new type is set, we push all uses of that node back to the worklist (in some cases, we also push grandchildren
2825 // or nodes even further down back to the worklist because their type could change as a result of the current type
2826 // change).
2827 void PhaseCCP::analyze() {
2828 // Initialize all types to TOP, optimistic analysis
2829 for (uint i = 0; i < C->unique(); i++) {
2830 _types.map(i, Type::TOP);
2831 }
2832
2956 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
2957 Node* use = n->fast_out(i);
2958 push_if_not_bottom_type(worklist, use);
2959 push_more_uses(worklist, n, use);
2960 }
2961 }
2962
2963 void PhaseCCP::push_if_not_bottom_type(Unique_Node_List& worklist, Node* n) const {
2964 if (n->bottom_type() != type(n)) {
2965 worklist.push(n);
2966 }
2967 }
2968
2969 // For some nodes, we need to propagate the type change to grandchildren or even further down.
2970 // Add them back to the worklist.
2971 void PhaseCCP::push_more_uses(Unique_Node_List& worklist, Node* parent, const Node* use) const {
2972 push_phis(worklist, use);
2973 push_catch(worklist, use);
2974 push_cmpu(worklist, use);
2975 push_counted_loop_phi(worklist, parent, use);
2976 push_loadp(worklist, use);
2977 push_and(worklist, parent, use);
2978 push_cast_ii(worklist, parent, use);
2979 push_opaque_zero_trip_guard(worklist, use);
2980 push_bool_with_cmpu_and_mask(worklist, use);
2981 }
2982
2983
2984 // We must recheck Phis too if use is a Region.
2985 void PhaseCCP::push_phis(Unique_Node_List& worklist, const Node* use) const {
2986 if (use->is_Region()) {
2987 for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
2988 push_if_not_bottom_type(worklist, use->fast_out(i));
2989 }
2990 }
2991 }
2992
2993 // If we changed the receiver type to a call, we need to revisit the Catch node following the call. It's looking for a
2994 // non-null receiver to know when to enable the regular fall-through path in addition to the NullPtrException path.
2995 // Same is true if the type of a ValidLengthTest input to an AllocateArrayNode changes.
3067 continue;
3068 }
3069
3070 Node* m = addI->in(1);
3071 if (m == andI->in(1) || m == andI->in(2)) {
3072 // Is "m" shared? Matched (1b) and thus we revisit Bool.
3073 push_if_not_bottom_type(worklist, bol);
3074 }
3075 }
3076 }
3077
3078 // 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'.
3079 // Seem PhiNode::Value().
3080 void PhaseCCP::push_counted_loop_phi(Unique_Node_List& worklist, Node* parent, const Node* use) {
3081 uint use_op = use->Opcode();
3082 if (use_op == Op_CmpI || use_op == Op_CmpL) {
3083 PhiNode* phi = countedloop_phi_from_cmp(use->as_Cmp(), parent);
3084 if (phi != nullptr) {
3085 worklist.push(phi);
3086 }
3087 }
3088 }
3089
3090 // Loading the java mirror from a Klass requires two loads and the type of the mirror load depends on the type of 'n'.
3091 // See LoadNode::Value().
3092 void PhaseCCP::push_loadp(Unique_Node_List& worklist, const Node* use) const {
3093 BarrierSetC2* barrier_set = BarrierSet::barrier_set()->barrier_set_c2();
3094 bool has_load_barrier_nodes = barrier_set->has_load_barrier_nodes();
3095
3096 if (use->Opcode() == Op_LoadP && use->bottom_type()->isa_rawptr()) {
3097 for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
3098 Node* loadp = use->fast_out(i);
3099 const Type* ut = loadp->bottom_type();
3100 if (loadp->Opcode() == Op_LoadP && ut->isa_instptr() && ut != type(loadp)) {
3101 if (has_load_barrier_nodes) {
3102 // Search for load barriers behind the load
3103 push_load_barrier(worklist, barrier_set, loadp);
3104 }
3105 worklist.push(loadp);
3106 }
|
1022 _worklist.print_set();
1023 }
1024 }
1025 }
1026 #endif /* ASSERT */
1027
1028 void PhaseIterGVN::optimize() {
1029 DEBUG_ONLY(uint num_processed = 0;)
1030 NOT_PRODUCT(init_verifyPhaseIterGVN();)
1031 NOT_PRODUCT(C->reset_igv_phase_iter(PHASE_AFTER_ITER_GVN_STEP);)
1032 C->print_method(PHASE_BEFORE_ITER_GVN, 3);
1033 if (StressIGVN) {
1034 shuffle_worklist();
1035 }
1036
1037 // The node count check in the loop below (check_node_count) assumes that we
1038 // increase the live node count with at most
1039 // max_live_nodes_increase_per_iteration in between checks. If this
1040 // assumption does not hold, there is a risk that we exceed the max node
1041 // limit in between checks and trigger an assert during node creation.
1042 const int max_live_nodes_increase_per_iteration = NodeLimitFudgeFactor * 5;
1043
1044 uint loop_count = 0;
1045 // Pull from worklist and transform the node. If the node has changed,
1046 // update edge info and put uses on worklist.
1047 while (_worklist.size() > 0) {
1048 if (C->check_node_count(max_live_nodes_increase_per_iteration, "Out of nodes")) {
1049 C->print_method(PHASE_AFTER_ITER_GVN, 3);
1050 return;
1051 }
1052 Node* n = _worklist.pop();
1053 if (loop_count >= K * C->live_nodes()) {
1054 DEBUG_ONLY(dump_infinite_loop_info(n, "PhaseIterGVN::optimize");)
1055 C->record_method_not_compilable("infinite loop in PhaseIterGVN::optimize");
1056 C->print_method(PHASE_AFTER_ITER_GVN, 3);
1057 return;
1058 }
1059 DEBUG_ONLY(trace_PhaseIterGVN_verbose(n, num_processed++);)
1060 if (n->outcnt() != 0) {
1061 NOT_PRODUCT(const Type* oldtype = type_or_null(n));
1062 // Do the transformation
1176 // SubNode::Value
1177 // CmpPNode::sub
1178 // MemNode::detect_ptr_independence
1179 // MemNode::all_controls_dominate
1180 // We find all controls of a pointer load, and see if they dominate the control of
1181 // an allocation. If they all dominate, we know the allocation is after (independent)
1182 // of the pointer load, and we can say the pointers are different. For this we call
1183 // n->dominates(sub, nlist) to check if controls n of the pointer load dominate the
1184 // control sub of the allocation. The problems is that sometimes dominates answers
1185 // false conservatively, and later it can determine that it is indeed true. Loops with
1186 // Region heads can lead to giving up, whereas LoopNodes can be skipped easier, and
1187 // so the traversal becomes more powerful. This is difficult to remidy, we would have
1188 // to notify the CmpP of CFG updates. Luckily, we recompute CmpP::Value during CCP
1189 // after loop-opts, so that should take care of many of these cases.
1190 return false;
1191 }
1192
1193 stringStream ss; // Print as a block without tty lock.
1194 ss.cr();
1195 ss.print_cr("Missed Value optimization:");
1196 n->dump_bfs(3, nullptr, "", &ss);
1197 ss.print_cr("Current type:");
1198 told->dump_on(&ss);
1199 ss.cr();
1200 ss.print_cr("Optimized type:");
1201 tnew->dump_on(&ss);
1202 ss.cr();
1203 tty->print_cr("%s", ss.as_string());
1204 return true;
1205 }
1206
1207 // Check that all Ideal optimizations that could be done were done.
1208 // Returns true if it found missed optimization opportunities and
1209 // false otherwise (no missed optimization, or skipped verification).
1210 bool PhaseIterGVN::verify_Ideal_for(Node* n, bool can_reshape) {
1211 // First, we check a list of exceptions, where we skip verification,
1212 // because there are known cases where Ideal can optimize after IGVN.
1213 // Some may be expected and cannot be fixed, and others should be fixed.
1214 switch (n->Opcode()) {
1215 // RangeCheckNode::Ideal looks up the chain for about 999 nodes
1216 // (see "Range-Check scan limit"). So, it is possible that something
2084 }
2085 }
2086 return false;
2087 }
2088 #endif
2089
2090 /**
2091 * Register a new node with the optimizer. Update the types array, the def-use
2092 * info. Put on worklist.
2093 */
2094 Node* PhaseIterGVN::register_new_node_with_optimizer(Node* n, Node* orig) {
2095 set_type_bottom(n);
2096 _worklist.push(n);
2097 if (orig != nullptr) C->copy_node_notes_to(n, orig);
2098 return n;
2099 }
2100
2101 //------------------------------transform--------------------------------------
2102 // Non-recursive: idealize Node 'n' with respect to its inputs and its value
2103 Node *PhaseIterGVN::transform( Node *n ) {
2104 // If brand new node, make space in type array, and give it a type.
2105 ensure_type_or_null(n);
2106 if (type_or_null(n) == nullptr) {
2107 set_type_bottom(n);
2108 }
2109
2110 if (_delay_transform) {
2111 // Add the node to the worklist but don't optimize for now
2112 _worklist.push(n);
2113 return n;
2114 }
2115
2116 return transform_old(n);
2117 }
2118
2119 Node *PhaseIterGVN::transform_old(Node* n) {
2120 NOT_PRODUCT(set_transforms());
2121 // Remove 'n' from hash table in case it gets modified
2122 _table.hash_delete(n);
2123 #ifdef ASSERT
2124 if (is_verify_def_use()) {
2125 assert(!_table.find_index(n->_idx), "found duplicate entry in table");
2126 }
2127 #endif
2128
2129 // Allow Bool -> Cmp idealisation in late inlining intrinsics that return a bool
2130 if (n->is_Cmp()) {
2131 add_users_to_worklist(n);
2132 }
2133
2134 // Apply the Ideal call in a loop until it no longer applies
2135 Node* k = n;
2368
2369 // Smash all inputs to 'old', isolating him completely
2370 Node *temp = new Node(1);
2371 temp->init_req(0,nn); // Add a use to nn to prevent him from dying
2372 remove_dead_node( old );
2373 temp->del_req(0); // Yank bogus edge
2374 if (nn != nullptr && nn->outcnt() == 0) {
2375 _worklist.push(nn);
2376 }
2377 #ifndef PRODUCT
2378 if (is_verify_def_use()) {
2379 for ( int i = 0; i < _verify_window_size; i++ ) {
2380 if ( _verify_window[i] == old )
2381 _verify_window[i] = nn;
2382 }
2383 }
2384 #endif
2385 temp->destruct(this); // reuse the _idx of this little guy
2386 }
2387
2388 void PhaseIterGVN::replace_in_uses(Node* n, Node* m) {
2389 assert(n != nullptr, "sanity");
2390 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
2391 Node* u = n->fast_out(i);
2392 if (u != n) {
2393 rehash_node_delayed(u);
2394 int nb = u->replace_edge(n, m);
2395 --i, imax -= nb;
2396 }
2397 }
2398 assert(n->outcnt() == 0, "all uses must be deleted");
2399 }
2400
2401 //------------------------------add_users_to_worklist--------------------------
2402 void PhaseIterGVN::add_users_to_worklist0(Node* n, Unique_Node_List& worklist) {
2403 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
2404 worklist.push(n->fast_out(i)); // Push on worklist
2405 }
2406 }
2407
2408 // Return counted loop Phi if as a counted loop exit condition, cmp
2409 // compares the induction variable with n
2410 static PhiNode* countedloop_phi_from_cmp(CmpNode* cmp, Node* n) {
2411 for (DUIterator_Fast imax, i = cmp->fast_outs(imax); i < imax; i++) {
2412 Node* bol = cmp->fast_out(i);
2413 for (DUIterator_Fast i2max, i2 = bol->fast_outs(i2max); i2 < i2max; i2++) {
2414 Node* iff = bol->fast_out(i2);
2415 if (iff->is_BaseCountedLoopEnd()) {
2416 BaseCountedLoopEndNode* cle = iff->as_BaseCountedLoopEnd();
2417 if (cle->limit() == n) {
2418 PhiNode* phi = cle->phi();
2419 if (phi != nullptr) {
2420 return phi;
2436 add_users_of_use_to_worklist(n, use, worklist);
2437 }
2438 }
2439
2440 void PhaseIterGVN::add_users_of_use_to_worklist(Node* n, Node* use, Unique_Node_List& worklist) {
2441 if(use->is_Multi() || // Multi-definer? Push projs on worklist
2442 use->is_Store() ) // Enable store/load same address
2443 add_users_to_worklist0(use, worklist);
2444
2445 // If we changed the receiver type to a call, we need to revisit
2446 // the Catch following the call. It's looking for a non-null
2447 // receiver to know when to enable the regular fall-through path
2448 // in addition to the NullPtrException path.
2449 if (use->is_CallDynamicJava() && n == use->in(TypeFunc::Parms)) {
2450 Node* p = use->as_CallDynamicJava()->proj_out_or_null(TypeFunc::Control);
2451 if (p != nullptr) {
2452 add_users_to_worklist0(p, worklist);
2453 }
2454 }
2455
2456 // AndLNode::Ideal folds GraphKit::mark_word_test patterns. Give it a chance to run.
2457 if (n->is_Load() && use->is_Phi()) {
2458 for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
2459 Node* u = use->fast_out(i);
2460 if (u->Opcode() == Op_AndL) {
2461 worklist.push(u);
2462 }
2463 }
2464 }
2465
2466 uint use_op = use->Opcode();
2467 if(use->is_Cmp()) { // Enable CMP/BOOL optimization
2468 add_users_to_worklist0(use, worklist); // Put Bool on worklist
2469 if (use->outcnt() > 0) {
2470 Node* bol = use->raw_out(0);
2471 if (bol->outcnt() > 0) {
2472 Node* iff = bol->raw_out(0);
2473 if (iff->outcnt() == 2) {
2474 // Look for the 'is_x2logic' pattern: "x ? : 0 : 1" and put the
2475 // phi merging either 0 or 1 onto the worklist
2476 Node* ifproj0 = iff->raw_out(0);
2477 Node* ifproj1 = iff->raw_out(1);
2478 if (ifproj0->outcnt() > 0 && ifproj1->outcnt() > 0) {
2479 Node* region0 = ifproj0->raw_out(0);
2480 Node* region1 = ifproj1->raw_out(0);
2481 if( region0 == region1 )
2482 add_users_to_worklist0(region0, worklist);
2483 }
2484 }
2485 }
2543 assert(n == in2, "only in2 modified");
2544 // Find all CastII with input in1.
2545 for (DUIterator_Fast jmax, j = in1->fast_outs(jmax); j < jmax; j++) {
2546 Node* castii = in1->fast_out(j);
2547 if (castii->is_CastII() && castii->as_CastII()->carry_dependency()) {
2548 // Find If.
2549 if (castii->in(0) != nullptr && castii->in(0)->in(0) != nullptr && castii->in(0)->in(0)->is_If()) {
2550 Node* ifnode = castii->in(0)->in(0);
2551 // Check that if connects to the cmp
2552 if (ifnode->in(1) != nullptr && ifnode->in(1)->is_Bool() && ifnode->in(1)->in(1) == cmp) {
2553 worklist.push(castii);
2554 }
2555 }
2556 }
2557 }
2558 }
2559 }
2560 }
2561 }
2562
2563 // Inline type nodes can have other inline types as users. If an input gets
2564 // updated, make sure that inline type users get a chance for optimization.
2565 if (use->is_InlineType()) {
2566 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2567 Node* u = use->fast_out(i2);
2568 if (u->is_InlineType())
2569 worklist.push(u);
2570 }
2571 }
2572 // If changed Cast input, notify down for Phi, Sub, and Xor - all do "uncast"
2573 // Patterns:
2574 // ConstraintCast+ -> Sub
2575 // ConstraintCast+ -> Phi
2576 // ConstraintCast+ -> Xor
2577 if (use->is_ConstraintCast()) {
2578 auto push_the_uses_to_worklist = [&](Node* n){
2579 if (n->is_Phi() || n->is_Sub() || n->Opcode() == Op_XorI || n->Opcode() == Op_XorL) {
2580 worklist.push(n);
2581 }
2582 };
2583 auto is_boundary = [](Node* n){ return !n->is_ConstraintCast(); };
2584 use->visit_uses(push_the_uses_to_worklist, is_boundary);
2585 }
2586 // If changed LShift inputs, check RShift users for useless sign-ext
2587 if (use_op == Op_LShiftI || use_op == Op_LShiftL) {
2588 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2589 Node* u = use->fast_out(i2);
2590 if (u->Opcode() == Op_RShiftI || u->Opcode() == Op_RShiftL)
2591 worklist.push(u);
2687 // If the ValidLengthTest input changes then the fallthrough path out of the AllocateArray may have become dead.
2688 // CatchNode::Value() is responsible for killing that path. The CatchNode has to be explicitly enqueued for igvn
2689 // to guarantee the change is not missed.
2690 if (use_op == Op_AllocateArray && n == use->in(AllocateNode::ValidLengthTest)) {
2691 Node* p = use->as_AllocateArray()->proj_out_or_null(TypeFunc::Control);
2692 if (p != nullptr) {
2693 add_users_to_worklist0(p, worklist);
2694 }
2695 }
2696
2697 if (use_op == Op_Initialize) {
2698 InitializeNode* init = use->as_Initialize();
2699 init->for_each_proj(enqueue_init_mem_projs, TypeFunc::Memory);
2700 }
2701 // Loading the java mirror from a Klass requires two loads and the type
2702 // of the mirror load depends on the type of 'n'. See LoadNode::Value().
2703 // LoadBarrier?(LoadP(LoadP(AddP(foo:Klass, #java_mirror))))
2704 BarrierSetC2* bs = BarrierSet::barrier_set()->barrier_set_c2();
2705 bool has_load_barrier_nodes = bs->has_load_barrier_nodes();
2706
2707 if (use_op == Op_CastP2X) {
2708 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2709 Node* u = use->fast_out(i2);
2710 // TODO 8350865 Still needed? Yes, I think this is from PhaseMacroExpand::expand_mh_intrinsic_return
2711 if (u->Opcode() == Op_AndX) {
2712 worklist.push(u);
2713 }
2714 // Search for CmpL(OrL(CastP2X(..), CastP2X(..)), 0L)
2715 if (u->Opcode() == Op_OrL) {
2716 for (DUIterator_Fast i3max, i3 = u->fast_outs(i3max); i3 < i3max; i3++) {
2717 Node* cmp = u->fast_out(i3);
2718 if (cmp->Opcode() == Op_CmpL) {
2719 worklist.push(cmp);
2720 }
2721 }
2722 }
2723 }
2724 }
2725 if (use_op == Op_LoadP && use->bottom_type()->isa_rawptr()) {
2726 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2727 Node* u = use->fast_out(i2);
2728 const Type* ut = u->bottom_type();
2729 if (u->Opcode() == Op_LoadP && ut->isa_instptr()) {
2730 if (has_load_barrier_nodes) {
2731 // Search for load barriers behind the load
2732 for (DUIterator_Fast i3max, i3 = u->fast_outs(i3max); i3 < i3max; i3++) {
2733 Node* b = u->fast_out(i3);
2734 if (bs->is_gc_barrier_node(b)) {
2735 worklist.push(b);
2736 }
2737 }
2738 }
2739 worklist.push(u);
2740 }
2741 }
2742 }
2743 // Give CallStaticJavaNode::remove_useless_allocation a chance to run
2744 if (use->is_Region()) {
2745 Node* c = use;
2746 do {
2747 c = c->unique_ctrl_out_or_null();
2748 } while (c != nullptr && c->is_Region());
2749 if (c != nullptr && c->is_CallStaticJava() && c->as_CallStaticJava()->uncommon_trap_request() != 0) {
2750 worklist.push(c);
2751 }
2752 }
2753 if (use->Opcode() == Op_OpaqueZeroTripGuard) {
2754 assert(use->outcnt() <= 1, "OpaqueZeroTripGuard can't be shared");
2755 if (use->outcnt() == 1) {
2756 Node* cmp = use->unique_out();
2757 worklist.push(cmp);
2758 }
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 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2766 Node* u = use->fast_out(i2);
2767 if (u->Opcode() == Op_CastX2P) {
2768 worklist.push(u);
2769 }
2770 }
2771 }
2772
2852 //------------------------------PhaseCCP---------------------------------------
2853 // Conditional Constant Propagation, ala Wegman & Zadeck
2854 PhaseCCP::PhaseCCP( PhaseIterGVN *igvn ) : PhaseIterGVN(igvn) {
2855 NOT_PRODUCT( clear_constants(); )
2856 assert( _worklist.size() == 0, "" );
2857 analyze();
2858 }
2859
2860 #ifndef PRODUCT
2861 //------------------------------~PhaseCCP--------------------------------------
2862 PhaseCCP::~PhaseCCP() {
2863 inc_invokes();
2864 _total_constants += count_constants();
2865 }
2866 #endif
2867
2868
2869 #ifdef ASSERT
2870 void PhaseCCP::verify_type(Node* n, const Type* tnew, const Type* told) {
2871 if (tnew->meet(told) != tnew->remove_speculative()) {
2872 n->dump(3);
2873 tty->print("told = "); told->dump(); tty->cr();
2874 tty->print("tnew = "); tnew->dump(); tty->cr();
2875 fatal("Not monotonic");
2876 }
2877 assert(!told->isa_int() || !tnew->isa_int() || told->is_int()->_widen <= tnew->is_int()->_widen, "widen increases");
2878 assert(!told->isa_long() || !tnew->isa_long() || told->is_long()->_widen <= tnew->is_long()->_widen, "widen increases");
2879 }
2880 #endif //ASSERT
2881
2882 // In this analysis, all types are initially set to TOP. We iteratively call Value() on all nodes of the graph until
2883 // we reach a fixed-point (i.e. no types change anymore). We start with a list that only contains the root node. Each time
2884 // a new type is set, we push all uses of that node back to the worklist (in some cases, we also push grandchildren
2885 // or nodes even further down back to the worklist because their type could change as a result of the current type
2886 // change).
2887 void PhaseCCP::analyze() {
2888 // Initialize all types to TOP, optimistic analysis
2889 for (uint i = 0; i < C->unique(); i++) {
2890 _types.map(i, Type::TOP);
2891 }
2892
3016 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
3017 Node* use = n->fast_out(i);
3018 push_if_not_bottom_type(worklist, use);
3019 push_more_uses(worklist, n, use);
3020 }
3021 }
3022
3023 void PhaseCCP::push_if_not_bottom_type(Unique_Node_List& worklist, Node* n) const {
3024 if (n->bottom_type() != type(n)) {
3025 worklist.push(n);
3026 }
3027 }
3028
3029 // For some nodes, we need to propagate the type change to grandchildren or even further down.
3030 // Add them back to the worklist.
3031 void PhaseCCP::push_more_uses(Unique_Node_List& worklist, Node* parent, const Node* use) const {
3032 push_phis(worklist, use);
3033 push_catch(worklist, use);
3034 push_cmpu(worklist, use);
3035 push_counted_loop_phi(worklist, parent, use);
3036 push_cast(worklist, use);
3037 push_loadp(worklist, use);
3038 push_and(worklist, parent, use);
3039 push_cast_ii(worklist, parent, use);
3040 push_opaque_zero_trip_guard(worklist, use);
3041 push_bool_with_cmpu_and_mask(worklist, use);
3042 }
3043
3044
3045 // We must recheck Phis too if use is a Region.
3046 void PhaseCCP::push_phis(Unique_Node_List& worklist, const Node* use) const {
3047 if (use->is_Region()) {
3048 for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
3049 push_if_not_bottom_type(worklist, use->fast_out(i));
3050 }
3051 }
3052 }
3053
3054 // If we changed the receiver type to a call, we need to revisit the Catch node following the call. It's looking for a
3055 // non-null receiver to know when to enable the regular fall-through path in addition to the NullPtrException path.
3056 // Same is true if the type of a ValidLengthTest input to an AllocateArrayNode changes.
3128 continue;
3129 }
3130
3131 Node* m = addI->in(1);
3132 if (m == andI->in(1) || m == andI->in(2)) {
3133 // Is "m" shared? Matched (1b) and thus we revisit Bool.
3134 push_if_not_bottom_type(worklist, bol);
3135 }
3136 }
3137 }
3138
3139 // 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'.
3140 // Seem PhiNode::Value().
3141 void PhaseCCP::push_counted_loop_phi(Unique_Node_List& worklist, Node* parent, const Node* use) {
3142 uint use_op = use->Opcode();
3143 if (use_op == Op_CmpI || use_op == Op_CmpL) {
3144 PhiNode* phi = countedloop_phi_from_cmp(use->as_Cmp(), parent);
3145 if (phi != nullptr) {
3146 worklist.push(phi);
3147 }
3148 }
3149 }
3150
3151 // TODO 8350865 Still needed? Yes, I think this is from PhaseMacroExpand::expand_mh_intrinsic_return
3152 void PhaseCCP::push_cast(Unique_Node_List& worklist, const Node* use) {
3153 uint use_op = use->Opcode();
3154 if (use_op == Op_CastP2X) {
3155 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
3156 Node* u = use->fast_out(i2);
3157 if (u->Opcode() == Op_AndX) {
3158 worklist.push(u);
3159 }
3160 }
3161 }
3162 }
3163
3164 // Loading the java mirror from a Klass requires two loads and the type of the mirror load depends on the type of 'n'.
3165 // See LoadNode::Value().
3166 void PhaseCCP::push_loadp(Unique_Node_List& worklist, const Node* use) const {
3167 BarrierSetC2* barrier_set = BarrierSet::barrier_set()->barrier_set_c2();
3168 bool has_load_barrier_nodes = barrier_set->has_load_barrier_nodes();
3169
3170 if (use->Opcode() == Op_LoadP && use->bottom_type()->isa_rawptr()) {
3171 for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
3172 Node* loadp = use->fast_out(i);
3173 const Type* ut = loadp->bottom_type();
3174 if (loadp->Opcode() == Op_LoadP && ut->isa_instptr() && ut != type(loadp)) {
3175 if (has_load_barrier_nodes) {
3176 // Search for load barriers behind the load
3177 push_load_barrier(worklist, barrier_set, loadp);
3178 }
3179 worklist.push(loadp);
3180 }
|