1012 _worklist.print_set();
1013 }
1014 }
1015 }
1016 #endif /* ASSERT */
1017
1018 void PhaseIterGVN::optimize() {
1019 DEBUG_ONLY(uint num_processed = 0;)
1020 NOT_PRODUCT(init_verifyPhaseIterGVN();)
1021 NOT_PRODUCT(C->reset_igv_phase_iter(PHASE_AFTER_ITER_GVN_STEP);)
1022 C->print_method(PHASE_BEFORE_ITER_GVN, 3);
1023 if (StressIGVN) {
1024 shuffle_worklist();
1025 }
1026
1027 // The node count check in the loop below (check_node_count) assumes that we
1028 // increase the live node count with at most
1029 // max_live_nodes_increase_per_iteration in between checks. If this
1030 // assumption does not hold, there is a risk that we exceed the max node
1031 // limit in between checks and trigger an assert during node creation.
1032 const int max_live_nodes_increase_per_iteration = NodeLimitFudgeFactor * 3;
1033
1034 uint loop_count = 0;
1035 // Pull from worklist and transform the node. If the node has changed,
1036 // update edge info and put uses on worklist.
1037 while (_worklist.size() > 0) {
1038 if (C->check_node_count(max_live_nodes_increase_per_iteration, "Out of nodes")) {
1039 C->print_method(PHASE_AFTER_ITER_GVN, 3);
1040 return;
1041 }
1042 Node* n = _worklist.pop();
1043 if (loop_count >= K * C->live_nodes()) {
1044 DEBUG_ONLY(dump_infinite_loop_info(n, "PhaseIterGVN::optimize");)
1045 C->record_method_not_compilable("infinite loop in PhaseIterGVN::optimize");
1046 C->print_method(PHASE_AFTER_ITER_GVN, 3);
1047 return;
1048 }
1049 DEBUG_ONLY(trace_PhaseIterGVN_verbose(n, num_processed++);)
1050 if (n->outcnt() != 0) {
1051 NOT_PRODUCT(const Type* oldtype = type_or_null(n));
1052 // Do the transformation
1166 // SubNode::Value
1167 // CmpPNode::sub
1168 // MemNode::detect_ptr_independence
1169 // MemNode::all_controls_dominate
1170 // We find all controls of a pointer load, and see if they dominate the control of
1171 // an allocation. If they all dominate, we know the allocation is after (independent)
1172 // of the pointer load, and we can say the pointers are different. For this we call
1173 // n->dominates(sub, nlist) to check if controls n of the pointer load dominate the
1174 // control sub of the allocation. The problems is that sometimes dominates answers
1175 // false conservatively, and later it can determine that it is indeed true. Loops with
1176 // Region heads can lead to giving up, whereas LoopNodes can be skipped easier, and
1177 // so the traversal becomes more powerful. This is difficult to remidy, we would have
1178 // to notify the CmpP of CFG updates. Luckily, we recompute CmpP::Value during CCP
1179 // after loop-opts, so that should take care of many of these cases.
1180 return false;
1181 }
1182
1183 stringStream ss; // Print as a block without tty lock.
1184 ss.cr();
1185 ss.print_cr("Missed Value optimization:");
1186 n->dump_bfs(1, nullptr, "", &ss);
1187 ss.print_cr("Current type:");
1188 told->dump_on(&ss);
1189 ss.cr();
1190 ss.print_cr("Optimized type:");
1191 tnew->dump_on(&ss);
1192 ss.cr();
1193 tty->print_cr("%s", ss.as_string());
1194 return true;
1195 }
1196
1197 // Check that all Ideal optimizations that could be done were done.
1198 // Returns true if it found missed optimization opportunities and
1199 // false otherwise (no missed optimization, or skipped verification).
1200 bool PhaseIterGVN::verify_Ideal_for(Node* n, bool can_reshape) {
1201 // First, we check a list of exceptions, where we skip verification,
1202 // because there are known cases where Ideal can optimize after IGVN.
1203 // Some may be expected and cannot be fixed, and others should be fixed.
1204 switch (n->Opcode()) {
1205 // RangeCheckNode::Ideal looks up the chain for about 999 nodes
1206 // (see "Range-Check scan limit"). So, it is possible that something
2074 }
2075 }
2076 return false;
2077 }
2078 #endif
2079
2080 /**
2081 * Register a new node with the optimizer. Update the types array, the def-use
2082 * info. Put on worklist.
2083 */
2084 Node* PhaseIterGVN::register_new_node_with_optimizer(Node* n, Node* orig) {
2085 set_type_bottom(n);
2086 _worklist.push(n);
2087 if (orig != nullptr) C->copy_node_notes_to(n, orig);
2088 return n;
2089 }
2090
2091 //------------------------------transform--------------------------------------
2092 // Non-recursive: idealize Node 'n' with respect to its inputs and its value
2093 Node *PhaseIterGVN::transform( Node *n ) {
2094 if (_delay_transform) {
2095 // Register the node but don't optimize for now
2096 register_new_node_with_optimizer(n);
2097 return n;
2098 }
2099
2100 // If brand new node, make space in type array, and give it a type.
2101 ensure_type_or_null(n);
2102 if (type_or_null(n) == nullptr) {
2103 set_type_bottom(n);
2104 }
2105
2106 return transform_old(n);
2107 }
2108
2109 Node *PhaseIterGVN::transform_old(Node* n) {
2110 NOT_PRODUCT(set_transforms());
2111 // Remove 'n' from hash table in case it gets modified
2112 _table.hash_delete(n);
2113 #ifdef ASSERT
2114 if (is_verify_def_use()) {
2115 assert(!_table.find_index(n->_idx), "found duplicate entry in table");
2116 }
2117 #endif
2118
2119 // Allow Bool -> Cmp idealisation in late inlining intrinsics that return a bool
2120 if (n->is_Cmp()) {
2121 add_users_to_worklist(n);
2122 }
2123
2124 // Apply the Ideal call in a loop until it no longer applies
2125 Node* k = n;
2358
2359 // Smash all inputs to 'old', isolating him completely
2360 Node *temp = new Node(1);
2361 temp->init_req(0,nn); // Add a use to nn to prevent him from dying
2362 remove_dead_node( old );
2363 temp->del_req(0); // Yank bogus edge
2364 if (nn != nullptr && nn->outcnt() == 0) {
2365 _worklist.push(nn);
2366 }
2367 #ifndef PRODUCT
2368 if (is_verify_def_use()) {
2369 for ( int i = 0; i < _verify_window_size; i++ ) {
2370 if ( _verify_window[i] == old )
2371 _verify_window[i] = nn;
2372 }
2373 }
2374 #endif
2375 temp->destruct(this); // reuse the _idx of this little guy
2376 }
2377
2378 //------------------------------add_users_to_worklist--------------------------
2379 void PhaseIterGVN::add_users_to_worklist0(Node* n, Unique_Node_List& worklist) {
2380 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
2381 worklist.push(n->fast_out(i)); // Push on worklist
2382 }
2383 }
2384
2385 // Return counted loop Phi if as a counted loop exit condition, cmp
2386 // compares the induction variable with n
2387 static PhiNode* countedloop_phi_from_cmp(CmpNode* cmp, Node* n) {
2388 for (DUIterator_Fast imax, i = cmp->fast_outs(imax); i < imax; i++) {
2389 Node* bol = cmp->fast_out(i);
2390 for (DUIterator_Fast i2max, i2 = bol->fast_outs(i2max); i2 < i2max; i2++) {
2391 Node* iff = bol->fast_out(i2);
2392 if (iff->is_BaseCountedLoopEnd()) {
2393 BaseCountedLoopEndNode* cle = iff->as_BaseCountedLoopEnd();
2394 if (cle->limit() == n) {
2395 PhiNode* phi = cle->phi();
2396 if (phi != nullptr) {
2397 return phi;
2413 add_users_of_use_to_worklist(n, use, worklist);
2414 }
2415 }
2416
2417 void PhaseIterGVN::add_users_of_use_to_worklist(Node* n, Node* use, Unique_Node_List& worklist) {
2418 if(use->is_Multi() || // Multi-definer? Push projs on worklist
2419 use->is_Store() ) // Enable store/load same address
2420 add_users_to_worklist0(use, worklist);
2421
2422 // If we changed the receiver type to a call, we need to revisit
2423 // the Catch following the call. It's looking for a non-null
2424 // receiver to know when to enable the regular fall-through path
2425 // in addition to the NullPtrException path.
2426 if (use->is_CallDynamicJava() && n == use->in(TypeFunc::Parms)) {
2427 Node* p = use->as_CallDynamicJava()->proj_out_or_null(TypeFunc::Control);
2428 if (p != nullptr) {
2429 add_users_to_worklist0(p, worklist);
2430 }
2431 }
2432
2433 uint use_op = use->Opcode();
2434 if(use->is_Cmp()) { // Enable CMP/BOOL optimization
2435 add_users_to_worklist0(use, worklist); // Put Bool on worklist
2436 if (use->outcnt() > 0) {
2437 Node* bol = use->raw_out(0);
2438 if (bol->outcnt() > 0) {
2439 Node* iff = bol->raw_out(0);
2440 if (iff->outcnt() == 2) {
2441 // Look for the 'is_x2logic' pattern: "x ? : 0 : 1" and put the
2442 // phi merging either 0 or 1 onto the worklist
2443 Node* ifproj0 = iff->raw_out(0);
2444 Node* ifproj1 = iff->raw_out(1);
2445 if (ifproj0->outcnt() > 0 && ifproj1->outcnt() > 0) {
2446 Node* region0 = ifproj0->raw_out(0);
2447 Node* region1 = ifproj1->raw_out(0);
2448 if( region0 == region1 )
2449 add_users_to_worklist0(region0, worklist);
2450 }
2451 }
2452 }
2510 assert(n == in2, "only in2 modified");
2511 // Find all CastII with input in1.
2512 for (DUIterator_Fast jmax, j = in1->fast_outs(jmax); j < jmax; j++) {
2513 Node* castii = in1->fast_out(j);
2514 if (castii->is_CastII() && castii->as_CastII()->carry_dependency()) {
2515 // Find If.
2516 if (castii->in(0) != nullptr && castii->in(0)->in(0) != nullptr && castii->in(0)->in(0)->is_If()) {
2517 Node* ifnode = castii->in(0)->in(0);
2518 // Check that if connects to the cmp
2519 if (ifnode->in(1) != nullptr && ifnode->in(1)->is_Bool() && ifnode->in(1)->in(1) == cmp) {
2520 worklist.push(castii);
2521 }
2522 }
2523 }
2524 }
2525 }
2526 }
2527 }
2528 }
2529
2530 // If changed Cast input, notify down for Phi, Sub, and Xor - all do "uncast"
2531 // Patterns:
2532 // ConstraintCast+ -> Sub
2533 // ConstraintCast+ -> Phi
2534 // ConstraintCast+ -> Xor
2535 if (use->is_ConstraintCast()) {
2536 auto push_the_uses_to_worklist = [&](Node* n){
2537 if (n->is_Phi() || n->is_Sub() || n->Opcode() == Op_XorI || n->Opcode() == Op_XorL) {
2538 worklist.push(n);
2539 }
2540 };
2541 auto is_boundary = [](Node* n){ return !n->is_ConstraintCast(); };
2542 use->visit_uses(push_the_uses_to_worklist, is_boundary);
2543 }
2544 // If changed LShift inputs, check RShift users for useless sign-ext
2545 if (use_op == Op_LShiftI || use_op == Op_LShiftL) {
2546 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2547 Node* u = use->fast_out(i2);
2548 if (u->Opcode() == Op_RShiftI || u->Opcode() == Op_RShiftL)
2549 worklist.push(u);
2636 // If the ValidLengthTest input changes then the fallthrough path out of the AllocateArray may have become dead.
2637 // CatchNode::Value() is responsible for killing that path. The CatchNode has to be explicitly enqueued for igvn
2638 // to guarantee the change is not missed.
2639 if (use_op == Op_AllocateArray && n == use->in(AllocateNode::ValidLengthTest)) {
2640 Node* p = use->as_AllocateArray()->proj_out_or_null(TypeFunc::Control);
2641 if (p != nullptr) {
2642 add_users_to_worklist0(p, worklist);
2643 }
2644 }
2645
2646 if (use_op == Op_Initialize) {
2647 InitializeNode* init = use->as_Initialize();
2648 init->for_each_proj(enqueue_init_mem_projs, TypeFunc::Memory);
2649 }
2650 // Loading the java mirror from a Klass requires two loads and the type
2651 // of the mirror load depends on the type of 'n'. See LoadNode::Value().
2652 // LoadBarrier?(LoadP(LoadP(AddP(foo:Klass, #java_mirror))))
2653 BarrierSetC2* bs = BarrierSet::barrier_set()->barrier_set_c2();
2654 bool has_load_barrier_nodes = bs->has_load_barrier_nodes();
2655
2656 if (use_op == Op_LoadP && use->bottom_type()->isa_rawptr()) {
2657 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2658 Node* u = use->fast_out(i2);
2659 const Type* ut = u->bottom_type();
2660 if (u->Opcode() == Op_LoadP && ut->isa_instptr()) {
2661 if (has_load_barrier_nodes) {
2662 // Search for load barriers behind the load
2663 for (DUIterator_Fast i3max, i3 = u->fast_outs(i3max); i3 < i3max; i3++) {
2664 Node* b = u->fast_out(i3);
2665 if (bs->is_gc_barrier_node(b)) {
2666 worklist.push(b);
2667 }
2668 }
2669 }
2670 worklist.push(u);
2671 }
2672 }
2673 }
2674 if (use->Opcode() == Op_OpaqueZeroTripGuard) {
2675 assert(use->outcnt() <= 1, "OpaqueZeroTripGuard can't be shared");
2676 if (use->outcnt() == 1) {
2677 Node* cmp = use->unique_out();
2678 worklist.push(cmp);
2679 }
2680 }
2681
2682 // From CastX2PNode::Ideal
2683 // CastX2P(AddX(x, y))
2684 // CastX2P(SubX(x, y))
2685 if (use->Opcode() == Op_AddX || use->Opcode() == Op_SubX) {
2686 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2687 Node* u = use->fast_out(i2);
2688 if (u->Opcode() == Op_CastX2P) {
2689 worklist.push(u);
2690 }
2691 }
2692 }
2693
2773 //------------------------------PhaseCCP---------------------------------------
2774 // Conditional Constant Propagation, ala Wegman & Zadeck
2775 PhaseCCP::PhaseCCP( PhaseIterGVN *igvn ) : PhaseIterGVN(igvn) {
2776 NOT_PRODUCT( clear_constants(); )
2777 assert( _worklist.size() == 0, "" );
2778 analyze();
2779 }
2780
2781 #ifndef PRODUCT
2782 //------------------------------~PhaseCCP--------------------------------------
2783 PhaseCCP::~PhaseCCP() {
2784 inc_invokes();
2785 _total_constants += count_constants();
2786 }
2787 #endif
2788
2789
2790 #ifdef ASSERT
2791 void PhaseCCP::verify_type(Node* n, const Type* tnew, const Type* told) {
2792 if (tnew->meet(told) != tnew->remove_speculative()) {
2793 n->dump(1);
2794 tty->print("told = "); told->dump(); tty->cr();
2795 tty->print("tnew = "); tnew->dump(); tty->cr();
2796 fatal("Not monotonic");
2797 }
2798 assert(!told->isa_int() || !tnew->isa_int() || told->is_int()->_widen <= tnew->is_int()->_widen, "widen increases");
2799 assert(!told->isa_long() || !tnew->isa_long() || told->is_long()->_widen <= tnew->is_long()->_widen, "widen increases");
2800 }
2801 #endif //ASSERT
2802
2803 // In this analysis, all types are initially set to TOP. We iteratively call Value() on all nodes of the graph until
2804 // we reach a fixed-point (i.e. no types change anymore). We start with a list that only contains the root node. Each time
2805 // a new type is set, we push all uses of that node back to the worklist (in some cases, we also push grandchildren
2806 // or nodes even further down back to the worklist because their type could change as a result of the current type
2807 // change).
2808 void PhaseCCP::analyze() {
2809 // Initialize all types to TOP, optimistic analysis
2810 for (uint i = 0; i < C->unique(); i++) {
2811 _types.map(i, Type::TOP);
2812 }
2813
2937 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
2938 Node* use = n->fast_out(i);
2939 push_if_not_bottom_type(worklist, use);
2940 push_more_uses(worklist, n, use);
2941 }
2942 }
2943
2944 void PhaseCCP::push_if_not_bottom_type(Unique_Node_List& worklist, Node* n) const {
2945 if (n->bottom_type() != type(n)) {
2946 worklist.push(n);
2947 }
2948 }
2949
2950 // For some nodes, we need to propagate the type change to grandchildren or even further down.
2951 // Add them back to the worklist.
2952 void PhaseCCP::push_more_uses(Unique_Node_List& worklist, Node* parent, const Node* use) const {
2953 push_phis(worklist, use);
2954 push_catch(worklist, use);
2955 push_cmpu(worklist, use);
2956 push_counted_loop_phi(worklist, parent, use);
2957 push_loadp(worklist, use);
2958 push_and(worklist, parent, use);
2959 push_cast_ii(worklist, parent, use);
2960 push_opaque_zero_trip_guard(worklist, use);
2961 push_bool_with_cmpu_and_mask(worklist, use);
2962 }
2963
2964
2965 // We must recheck Phis too if use is a Region.
2966 void PhaseCCP::push_phis(Unique_Node_List& worklist, const Node* use) const {
2967 if (use->is_Region()) {
2968 for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
2969 push_if_not_bottom_type(worklist, use->fast_out(i));
2970 }
2971 }
2972 }
2973
2974 // If we changed the receiver type to a call, we need to revisit the Catch node following the call. It's looking for a
2975 // non-null receiver to know when to enable the regular fall-through path in addition to the NullPtrException path.
2976 // Same is true if the type of a ValidLengthTest input to an AllocateArrayNode changes.
3048 continue;
3049 }
3050
3051 Node* m = addI->in(1);
3052 if (m == andI->in(1) || m == andI->in(2)) {
3053 // Is "m" shared? Matched (1b) and thus we revisit Bool.
3054 push_if_not_bottom_type(worklist, bol);
3055 }
3056 }
3057 }
3058
3059 // 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'.
3060 // Seem PhiNode::Value().
3061 void PhaseCCP::push_counted_loop_phi(Unique_Node_List& worklist, Node* parent, const Node* use) {
3062 uint use_op = use->Opcode();
3063 if (use_op == Op_CmpI || use_op == Op_CmpL) {
3064 PhiNode* phi = countedloop_phi_from_cmp(use->as_Cmp(), parent);
3065 if (phi != nullptr) {
3066 worklist.push(phi);
3067 }
3068 }
3069 }
3070
3071 // Loading the java mirror from a Klass requires two loads and the type of the mirror load depends on the type of 'n'.
3072 // See LoadNode::Value().
3073 void PhaseCCP::push_loadp(Unique_Node_List& worklist, const Node* use) const {
3074 BarrierSetC2* barrier_set = BarrierSet::barrier_set()->barrier_set_c2();
3075 bool has_load_barrier_nodes = barrier_set->has_load_barrier_nodes();
3076
3077 if (use->Opcode() == Op_LoadP && use->bottom_type()->isa_rawptr()) {
3078 for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
3079 Node* loadp = use->fast_out(i);
3080 const Type* ut = loadp->bottom_type();
3081 if (loadp->Opcode() == Op_LoadP && ut->isa_instptr() && ut != type(loadp)) {
3082 if (has_load_barrier_nodes) {
3083 // Search for load barriers behind the load
3084 push_load_barrier(worklist, barrier_set, loadp);
3085 }
3086 worklist.push(loadp);
3087 }
|
1012 _worklist.print_set();
1013 }
1014 }
1015 }
1016 #endif /* ASSERT */
1017
1018 void PhaseIterGVN::optimize() {
1019 DEBUG_ONLY(uint num_processed = 0;)
1020 NOT_PRODUCT(init_verifyPhaseIterGVN();)
1021 NOT_PRODUCT(C->reset_igv_phase_iter(PHASE_AFTER_ITER_GVN_STEP);)
1022 C->print_method(PHASE_BEFORE_ITER_GVN, 3);
1023 if (StressIGVN) {
1024 shuffle_worklist();
1025 }
1026
1027 // The node count check in the loop below (check_node_count) assumes that we
1028 // increase the live node count with at most
1029 // max_live_nodes_increase_per_iteration in between checks. If this
1030 // assumption does not hold, there is a risk that we exceed the max node
1031 // limit in between checks and trigger an assert during node creation.
1032 const int max_live_nodes_increase_per_iteration = NodeLimitFudgeFactor * 5;
1033
1034 uint loop_count = 0;
1035 // Pull from worklist and transform the node. If the node has changed,
1036 // update edge info and put uses on worklist.
1037 while (_worklist.size() > 0) {
1038 if (C->check_node_count(max_live_nodes_increase_per_iteration, "Out of nodes")) {
1039 C->print_method(PHASE_AFTER_ITER_GVN, 3);
1040 return;
1041 }
1042 Node* n = _worklist.pop();
1043 if (loop_count >= K * C->live_nodes()) {
1044 DEBUG_ONLY(dump_infinite_loop_info(n, "PhaseIterGVN::optimize");)
1045 C->record_method_not_compilable("infinite loop in PhaseIterGVN::optimize");
1046 C->print_method(PHASE_AFTER_ITER_GVN, 3);
1047 return;
1048 }
1049 DEBUG_ONLY(trace_PhaseIterGVN_verbose(n, num_processed++);)
1050 if (n->outcnt() != 0) {
1051 NOT_PRODUCT(const Type* oldtype = type_or_null(n));
1052 // Do the transformation
1166 // SubNode::Value
1167 // CmpPNode::sub
1168 // MemNode::detect_ptr_independence
1169 // MemNode::all_controls_dominate
1170 // We find all controls of a pointer load, and see if they dominate the control of
1171 // an allocation. If they all dominate, we know the allocation is after (independent)
1172 // of the pointer load, and we can say the pointers are different. For this we call
1173 // n->dominates(sub, nlist) to check if controls n of the pointer load dominate the
1174 // control sub of the allocation. The problems is that sometimes dominates answers
1175 // false conservatively, and later it can determine that it is indeed true. Loops with
1176 // Region heads can lead to giving up, whereas LoopNodes can be skipped easier, and
1177 // so the traversal becomes more powerful. This is difficult to remidy, we would have
1178 // to notify the CmpP of CFG updates. Luckily, we recompute CmpP::Value during CCP
1179 // after loop-opts, so that should take care of many of these cases.
1180 return false;
1181 }
1182
1183 stringStream ss; // Print as a block without tty lock.
1184 ss.cr();
1185 ss.print_cr("Missed Value optimization:");
1186 n->dump_bfs(3, nullptr, "", &ss);
1187 ss.print_cr("Current type:");
1188 told->dump_on(&ss);
1189 ss.cr();
1190 ss.print_cr("Optimized type:");
1191 tnew->dump_on(&ss);
1192 ss.cr();
1193 tty->print_cr("%s", ss.as_string());
1194 return true;
1195 }
1196
1197 // Check that all Ideal optimizations that could be done were done.
1198 // Returns true if it found missed optimization opportunities and
1199 // false otherwise (no missed optimization, or skipped verification).
1200 bool PhaseIterGVN::verify_Ideal_for(Node* n, bool can_reshape) {
1201 // First, we check a list of exceptions, where we skip verification,
1202 // because there are known cases where Ideal can optimize after IGVN.
1203 // Some may be expected and cannot be fixed, and others should be fixed.
1204 switch (n->Opcode()) {
1205 // RangeCheckNode::Ideal looks up the chain for about 999 nodes
1206 // (see "Range-Check scan limit"). So, it is possible that something
2074 }
2075 }
2076 return false;
2077 }
2078 #endif
2079
2080 /**
2081 * Register a new node with the optimizer. Update the types array, the def-use
2082 * info. Put on worklist.
2083 */
2084 Node* PhaseIterGVN::register_new_node_with_optimizer(Node* n, Node* orig) {
2085 set_type_bottom(n);
2086 _worklist.push(n);
2087 if (orig != nullptr) C->copy_node_notes_to(n, orig);
2088 return n;
2089 }
2090
2091 //------------------------------transform--------------------------------------
2092 // Non-recursive: idealize Node 'n' with respect to its inputs and its value
2093 Node *PhaseIterGVN::transform( Node *n ) {
2094 // If brand new node, make space in type array, and give it a type.
2095 ensure_type_or_null(n);
2096 if (type_or_null(n) == nullptr) {
2097 set_type_bottom(n);
2098 }
2099
2100 if (_delay_transform) {
2101 // Add the node to the worklist but don't optimize for now
2102 _worklist.push(n);
2103 return n;
2104 }
2105
2106 return transform_old(n);
2107 }
2108
2109 Node *PhaseIterGVN::transform_old(Node* n) {
2110 NOT_PRODUCT(set_transforms());
2111 // Remove 'n' from hash table in case it gets modified
2112 _table.hash_delete(n);
2113 #ifdef ASSERT
2114 if (is_verify_def_use()) {
2115 assert(!_table.find_index(n->_idx), "found duplicate entry in table");
2116 }
2117 #endif
2118
2119 // Allow Bool -> Cmp idealisation in late inlining intrinsics that return a bool
2120 if (n->is_Cmp()) {
2121 add_users_to_worklist(n);
2122 }
2123
2124 // Apply the Ideal call in a loop until it no longer applies
2125 Node* k = n;
2358
2359 // Smash all inputs to 'old', isolating him completely
2360 Node *temp = new Node(1);
2361 temp->init_req(0,nn); // Add a use to nn to prevent him from dying
2362 remove_dead_node( old );
2363 temp->del_req(0); // Yank bogus edge
2364 if (nn != nullptr && nn->outcnt() == 0) {
2365 _worklist.push(nn);
2366 }
2367 #ifndef PRODUCT
2368 if (is_verify_def_use()) {
2369 for ( int i = 0; i < _verify_window_size; i++ ) {
2370 if ( _verify_window[i] == old )
2371 _verify_window[i] = nn;
2372 }
2373 }
2374 #endif
2375 temp->destruct(this); // reuse the _idx of this little guy
2376 }
2377
2378 void PhaseIterGVN::replace_in_uses(Node* n, Node* m) {
2379 assert(n != nullptr, "sanity");
2380 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
2381 Node* u = n->fast_out(i);
2382 if (u != n) {
2383 rehash_node_delayed(u);
2384 int nb = u->replace_edge(n, m);
2385 --i, imax -= nb;
2386 }
2387 }
2388 assert(n->outcnt() == 0, "all uses must be deleted");
2389 }
2390
2391 //------------------------------add_users_to_worklist--------------------------
2392 void PhaseIterGVN::add_users_to_worklist0(Node* n, Unique_Node_List& worklist) {
2393 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
2394 worklist.push(n->fast_out(i)); // Push on worklist
2395 }
2396 }
2397
2398 // Return counted loop Phi if as a counted loop exit condition, cmp
2399 // compares the induction variable with n
2400 static PhiNode* countedloop_phi_from_cmp(CmpNode* cmp, Node* n) {
2401 for (DUIterator_Fast imax, i = cmp->fast_outs(imax); i < imax; i++) {
2402 Node* bol = cmp->fast_out(i);
2403 for (DUIterator_Fast i2max, i2 = bol->fast_outs(i2max); i2 < i2max; i2++) {
2404 Node* iff = bol->fast_out(i2);
2405 if (iff->is_BaseCountedLoopEnd()) {
2406 BaseCountedLoopEndNode* cle = iff->as_BaseCountedLoopEnd();
2407 if (cle->limit() == n) {
2408 PhiNode* phi = cle->phi();
2409 if (phi != nullptr) {
2410 return phi;
2426 add_users_of_use_to_worklist(n, use, worklist);
2427 }
2428 }
2429
2430 void PhaseIterGVN::add_users_of_use_to_worklist(Node* n, Node* use, Unique_Node_List& worklist) {
2431 if(use->is_Multi() || // Multi-definer? Push projs on worklist
2432 use->is_Store() ) // Enable store/load same address
2433 add_users_to_worklist0(use, worklist);
2434
2435 // If we changed the receiver type to a call, we need to revisit
2436 // the Catch following the call. It's looking for a non-null
2437 // receiver to know when to enable the regular fall-through path
2438 // in addition to the NullPtrException path.
2439 if (use->is_CallDynamicJava() && n == use->in(TypeFunc::Parms)) {
2440 Node* p = use->as_CallDynamicJava()->proj_out_or_null(TypeFunc::Control);
2441 if (p != nullptr) {
2442 add_users_to_worklist0(p, worklist);
2443 }
2444 }
2445
2446 // AndLNode::Ideal folds GraphKit::mark_word_test patterns. Give it a chance to run.
2447 if (n->is_Load() && use->is_Phi()) {
2448 for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
2449 Node* u = use->fast_out(i);
2450 if (u->Opcode() == Op_AndL) {
2451 worklist.push(u);
2452 }
2453 }
2454 }
2455
2456 uint use_op = use->Opcode();
2457 if(use->is_Cmp()) { // Enable CMP/BOOL optimization
2458 add_users_to_worklist0(use, worklist); // Put Bool on worklist
2459 if (use->outcnt() > 0) {
2460 Node* bol = use->raw_out(0);
2461 if (bol->outcnt() > 0) {
2462 Node* iff = bol->raw_out(0);
2463 if (iff->outcnt() == 2) {
2464 // Look for the 'is_x2logic' pattern: "x ? : 0 : 1" and put the
2465 // phi merging either 0 or 1 onto the worklist
2466 Node* ifproj0 = iff->raw_out(0);
2467 Node* ifproj1 = iff->raw_out(1);
2468 if (ifproj0->outcnt() > 0 && ifproj1->outcnt() > 0) {
2469 Node* region0 = ifproj0->raw_out(0);
2470 Node* region1 = ifproj1->raw_out(0);
2471 if( region0 == region1 )
2472 add_users_to_worklist0(region0, worklist);
2473 }
2474 }
2475 }
2533 assert(n == in2, "only in2 modified");
2534 // Find all CastII with input in1.
2535 for (DUIterator_Fast jmax, j = in1->fast_outs(jmax); j < jmax; j++) {
2536 Node* castii = in1->fast_out(j);
2537 if (castii->is_CastII() && castii->as_CastII()->carry_dependency()) {
2538 // Find If.
2539 if (castii->in(0) != nullptr && castii->in(0)->in(0) != nullptr && castii->in(0)->in(0)->is_If()) {
2540 Node* ifnode = castii->in(0)->in(0);
2541 // Check that if connects to the cmp
2542 if (ifnode->in(1) != nullptr && ifnode->in(1)->is_Bool() && ifnode->in(1)->in(1) == cmp) {
2543 worklist.push(castii);
2544 }
2545 }
2546 }
2547 }
2548 }
2549 }
2550 }
2551 }
2552
2553 // Inline type nodes can have other inline types as users. If an input gets
2554 // updated, make sure that inline type users get a chance for optimization.
2555 if (use->is_InlineType()) {
2556 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2557 Node* u = use->fast_out(i2);
2558 if (u->is_InlineType())
2559 worklist.push(u);
2560 }
2561 }
2562 // If changed Cast input, notify down for Phi, Sub, and Xor - all do "uncast"
2563 // Patterns:
2564 // ConstraintCast+ -> Sub
2565 // ConstraintCast+ -> Phi
2566 // ConstraintCast+ -> Xor
2567 if (use->is_ConstraintCast()) {
2568 auto push_the_uses_to_worklist = [&](Node* n){
2569 if (n->is_Phi() || n->is_Sub() || n->Opcode() == Op_XorI || n->Opcode() == Op_XorL) {
2570 worklist.push(n);
2571 }
2572 };
2573 auto is_boundary = [](Node* n){ return !n->is_ConstraintCast(); };
2574 use->visit_uses(push_the_uses_to_worklist, is_boundary);
2575 }
2576 // If changed LShift inputs, check RShift users for useless sign-ext
2577 if (use_op == Op_LShiftI || use_op == Op_LShiftL) {
2578 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2579 Node* u = use->fast_out(i2);
2580 if (u->Opcode() == Op_RShiftI || u->Opcode() == Op_RShiftL)
2581 worklist.push(u);
2668 // If the ValidLengthTest input changes then the fallthrough path out of the AllocateArray may have become dead.
2669 // CatchNode::Value() is responsible for killing that path. The CatchNode has to be explicitly enqueued for igvn
2670 // to guarantee the change is not missed.
2671 if (use_op == Op_AllocateArray && n == use->in(AllocateNode::ValidLengthTest)) {
2672 Node* p = use->as_AllocateArray()->proj_out_or_null(TypeFunc::Control);
2673 if (p != nullptr) {
2674 add_users_to_worklist0(p, worklist);
2675 }
2676 }
2677
2678 if (use_op == Op_Initialize) {
2679 InitializeNode* init = use->as_Initialize();
2680 init->for_each_proj(enqueue_init_mem_projs, TypeFunc::Memory);
2681 }
2682 // Loading the java mirror from a Klass requires two loads and the type
2683 // of the mirror load depends on the type of 'n'. See LoadNode::Value().
2684 // LoadBarrier?(LoadP(LoadP(AddP(foo:Klass, #java_mirror))))
2685 BarrierSetC2* bs = BarrierSet::barrier_set()->barrier_set_c2();
2686 bool has_load_barrier_nodes = bs->has_load_barrier_nodes();
2687
2688 if (use_op == Op_CastP2X) {
2689 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2690 Node* u = use->fast_out(i2);
2691 // TODO 8350865 Still needed? Yes, I think this is from PhaseMacroExpand::expand_mh_intrinsic_return
2692 if (u->Opcode() == Op_AndX) {
2693 worklist.push(u);
2694 }
2695 // Search for CmpL(OrL(CastP2X(..), CastP2X(..)), 0L)
2696 if (u->Opcode() == Op_OrL) {
2697 for (DUIterator_Fast i3max, i3 = u->fast_outs(i3max); i3 < i3max; i3++) {
2698 Node* cmp = u->fast_out(i3);
2699 if (cmp->Opcode() == Op_CmpL) {
2700 worklist.push(cmp);
2701 }
2702 }
2703 }
2704 }
2705 }
2706 if (use_op == Op_LoadP && use->bottom_type()->isa_rawptr()) {
2707 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2708 Node* u = use->fast_out(i2);
2709 const Type* ut = u->bottom_type();
2710 if (u->Opcode() == Op_LoadP && ut->isa_instptr()) {
2711 if (has_load_barrier_nodes) {
2712 // Search for load barriers behind the load
2713 for (DUIterator_Fast i3max, i3 = u->fast_outs(i3max); i3 < i3max; i3++) {
2714 Node* b = u->fast_out(i3);
2715 if (bs->is_gc_barrier_node(b)) {
2716 worklist.push(b);
2717 }
2718 }
2719 }
2720 worklist.push(u);
2721 }
2722 }
2723 }
2724 // Give CallStaticJavaNode::remove_useless_allocation a chance to run
2725 if (use->is_Region()) {
2726 Node* c = use;
2727 do {
2728 c = c->unique_ctrl_out_or_null();
2729 } while (c != nullptr && c->is_Region());
2730 if (c != nullptr && c->is_CallStaticJava() && c->as_CallStaticJava()->uncommon_trap_request() != 0) {
2731 worklist.push(c);
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
2833 //------------------------------PhaseCCP---------------------------------------
2834 // Conditional Constant Propagation, ala Wegman & Zadeck
2835 PhaseCCP::PhaseCCP( PhaseIterGVN *igvn ) : PhaseIterGVN(igvn) {
2836 NOT_PRODUCT( clear_constants(); )
2837 assert( _worklist.size() == 0, "" );
2838 analyze();
2839 }
2840
2841 #ifndef PRODUCT
2842 //------------------------------~PhaseCCP--------------------------------------
2843 PhaseCCP::~PhaseCCP() {
2844 inc_invokes();
2845 _total_constants += count_constants();
2846 }
2847 #endif
2848
2849
2850 #ifdef ASSERT
2851 void PhaseCCP::verify_type(Node* n, const Type* tnew, const Type* told) {
2852 if (tnew->meet(told) != tnew->remove_speculative()) {
2853 n->dump(3);
2854 tty->print("told = "); told->dump(); tty->cr();
2855 tty->print("tnew = "); tnew->dump(); tty->cr();
2856 fatal("Not monotonic");
2857 }
2858 assert(!told->isa_int() || !tnew->isa_int() || told->is_int()->_widen <= tnew->is_int()->_widen, "widen increases");
2859 assert(!told->isa_long() || !tnew->isa_long() || told->is_long()->_widen <= tnew->is_long()->_widen, "widen increases");
2860 }
2861 #endif //ASSERT
2862
2863 // In this analysis, all types are initially set to TOP. We iteratively call Value() on all nodes of the graph until
2864 // we reach a fixed-point (i.e. no types change anymore). We start with a list that only contains the root node. Each time
2865 // a new type is set, we push all uses of that node back to the worklist (in some cases, we also push grandchildren
2866 // or nodes even further down back to the worklist because their type could change as a result of the current type
2867 // change).
2868 void PhaseCCP::analyze() {
2869 // Initialize all types to TOP, optimistic analysis
2870 for (uint i = 0; i < C->unique(); i++) {
2871 _types.map(i, Type::TOP);
2872 }
2873
2997 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
2998 Node* use = n->fast_out(i);
2999 push_if_not_bottom_type(worklist, use);
3000 push_more_uses(worklist, n, use);
3001 }
3002 }
3003
3004 void PhaseCCP::push_if_not_bottom_type(Unique_Node_List& worklist, Node* n) const {
3005 if (n->bottom_type() != type(n)) {
3006 worklist.push(n);
3007 }
3008 }
3009
3010 // For some nodes, we need to propagate the type change to grandchildren or even further down.
3011 // Add them back to the worklist.
3012 void PhaseCCP::push_more_uses(Unique_Node_List& worklist, Node* parent, const Node* use) const {
3013 push_phis(worklist, use);
3014 push_catch(worklist, use);
3015 push_cmpu(worklist, use);
3016 push_counted_loop_phi(worklist, parent, use);
3017 push_cast(worklist, use);
3018 push_loadp(worklist, use);
3019 push_and(worklist, parent, use);
3020 push_cast_ii(worklist, parent, use);
3021 push_opaque_zero_trip_guard(worklist, use);
3022 push_bool_with_cmpu_and_mask(worklist, use);
3023 }
3024
3025
3026 // We must recheck Phis too if use is a Region.
3027 void PhaseCCP::push_phis(Unique_Node_List& worklist, const Node* use) const {
3028 if (use->is_Region()) {
3029 for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
3030 push_if_not_bottom_type(worklist, use->fast_out(i));
3031 }
3032 }
3033 }
3034
3035 // If we changed the receiver type to a call, we need to revisit the Catch node following the call. It's looking for a
3036 // non-null receiver to know when to enable the regular fall-through path in addition to the NullPtrException path.
3037 // Same is true if the type of a ValidLengthTest input to an AllocateArrayNode changes.
3109 continue;
3110 }
3111
3112 Node* m = addI->in(1);
3113 if (m == andI->in(1) || m == andI->in(2)) {
3114 // Is "m" shared? Matched (1b) and thus we revisit Bool.
3115 push_if_not_bottom_type(worklist, bol);
3116 }
3117 }
3118 }
3119
3120 // 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'.
3121 // Seem PhiNode::Value().
3122 void PhaseCCP::push_counted_loop_phi(Unique_Node_List& worklist, Node* parent, const Node* use) {
3123 uint use_op = use->Opcode();
3124 if (use_op == Op_CmpI || use_op == Op_CmpL) {
3125 PhiNode* phi = countedloop_phi_from_cmp(use->as_Cmp(), parent);
3126 if (phi != nullptr) {
3127 worklist.push(phi);
3128 }
3129 }
3130 }
3131
3132 // TODO 8350865 Still needed? Yes, I think this is from PhaseMacroExpand::expand_mh_intrinsic_return
3133 void PhaseCCP::push_cast(Unique_Node_List& worklist, const Node* use) {
3134 uint use_op = use->Opcode();
3135 if (use_op == Op_CastP2X) {
3136 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
3137 Node* u = use->fast_out(i2);
3138 if (u->Opcode() == Op_AndX) {
3139 worklist.push(u);
3140 }
3141 }
3142 }
3143 }
3144
3145 // Loading the java mirror from a Klass requires two loads and the type of the mirror load depends on the type of 'n'.
3146 // See LoadNode::Value().
3147 void PhaseCCP::push_loadp(Unique_Node_List& worklist, const Node* use) const {
3148 BarrierSetC2* barrier_set = BarrierSet::barrier_set()->barrier_set_c2();
3149 bool has_load_barrier_nodes = barrier_set->has_load_barrier_nodes();
3150
3151 if (use->Opcode() == Op_LoadP && use->bottom_type()->isa_rawptr()) {
3152 for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
3153 Node* loadp = use->fast_out(i);
3154 const Type* ut = loadp->bottom_type();
3155 if (loadp->Opcode() == Op_LoadP && ut->isa_instptr() && ut != type(loadp)) {
3156 if (has_load_barrier_nodes) {
3157 // Search for load barriers behind the load
3158 push_load_barrier(worklist, barrier_set, loadp);
3159 }
3160 worklist.push(loadp);
3161 }
|