1164 // SubNode::Value
1165 // CmpPNode::sub
1166 // MemNode::detect_ptr_independence
1167 // MemNode::all_controls_dominate
1168 // We find all controls of a pointer load, and see if they dominate the control of
1169 // an allocation. If they all dominate, we know the allocation is after (independent)
1170 // of the pointer load, and we can say the pointers are different. For this we call
1171 // n->dominates(sub, nlist) to check if controls n of the pointer load dominate the
1172 // control sub of the allocation. The problems is that sometimes dominates answers
1173 // false conservatively, and later it can determine that it is indeed true. Loops with
1174 // Region heads can lead to giving up, whereas LoopNodes can be skipped easier, and
1175 // so the traversal becomes more powerful. This is difficult to remidy, we would have
1176 // to notify the CmpP of CFG updates. Luckily, we recompute CmpP::Value during CCP
1177 // after loop-opts, so that should take care of many of these cases.
1178 return false;
1179 }
1180
1181 stringStream ss; // Print as a block without tty lock.
1182 ss.cr();
1183 ss.print_cr("Missed Value optimization:");
1184 n->dump_bfs(1, nullptr, "", &ss);
1185 ss.print_cr("Current type:");
1186 told->dump_on(&ss);
1187 ss.cr();
1188 ss.print_cr("Optimized type:");
1189 tnew->dump_on(&ss);
1190 ss.cr();
1191 tty->print_cr("%s", ss.as_string());
1192 return true;
1193 }
1194
1195 // Check that all Ideal optimizations that could be done were done.
1196 // Returns true if it found missed optimization opportunities and
1197 // false otherwise (no missed optimization, or skipped verification).
1198 bool PhaseIterGVN::verify_Ideal_for(Node* n, bool can_reshape) {
1199 // First, we check a list of exceptions, where we skip verification,
1200 // because there are known cases where Ideal can optimize after IGVN.
1201 // Some may be expected and cannot be fixed, and others should be fixed.
1202 switch (n->Opcode()) {
1203 // RangeCheckNode::Ideal looks up the chain for about 999 nodes
1204 // (see "Range-Check scan limit"). So, it is possible that something
2056 i->dump_bfs(1, nullptr, "", &ss);
2057 tty->print_cr("%s", ss.as_string());
2058 return true;
2059 }
2060 #endif
2061
2062 /**
2063 * Register a new node with the optimizer. Update the types array, the def-use
2064 * info. Put on worklist.
2065 */
2066 Node* PhaseIterGVN::register_new_node_with_optimizer(Node* n, Node* orig) {
2067 set_type_bottom(n);
2068 _worklist.push(n);
2069 if (orig != nullptr) C->copy_node_notes_to(n, orig);
2070 return n;
2071 }
2072
2073 //------------------------------transform--------------------------------------
2074 // Non-recursive: idealize Node 'n' with respect to its inputs and its value
2075 Node *PhaseIterGVN::transform( Node *n ) {
2076 if (_delay_transform) {
2077 // Register the node but don't optimize for now
2078 register_new_node_with_optimizer(n);
2079 return n;
2080 }
2081
2082 // If brand new node, make space in type array, and give it a type.
2083 ensure_type_or_null(n);
2084 if (type_or_null(n) == nullptr) {
2085 set_type_bottom(n);
2086 }
2087
2088 return transform_old(n);
2089 }
2090
2091 Node *PhaseIterGVN::transform_old(Node* n) {
2092 NOT_PRODUCT(set_transforms());
2093 // Remove 'n' from hash table in case it gets modified
2094 _table.hash_delete(n);
2095 #ifdef ASSERT
2096 if (is_verify_def_use()) {
2097 assert(!_table.find_index(n->_idx), "found duplicate entry in table");
2098 }
2099 #endif
2100
2101 // Allow Bool -> Cmp idealisation in late inlining intrinsics that return a bool
2102 if (n->is_Cmp()) {
2103 add_users_to_worklist(n);
2104 }
2105
2106 // Apply the Ideal call in a loop until it no longer applies
2107 Node* k = n;
2340
2341 // Smash all inputs to 'old', isolating him completely
2342 Node *temp = new Node(1);
2343 temp->init_req(0,nn); // Add a use to nn to prevent him from dying
2344 remove_dead_node( old );
2345 temp->del_req(0); // Yank bogus edge
2346 if (nn != nullptr && nn->outcnt() == 0) {
2347 _worklist.push(nn);
2348 }
2349 #ifndef PRODUCT
2350 if (is_verify_def_use()) {
2351 for ( int i = 0; i < _verify_window_size; i++ ) {
2352 if ( _verify_window[i] == old )
2353 _verify_window[i] = nn;
2354 }
2355 }
2356 #endif
2357 temp->destruct(this); // reuse the _idx of this little guy
2358 }
2359
2360 //------------------------------add_users_to_worklist--------------------------
2361 void PhaseIterGVN::add_users_to_worklist0(Node* n, Unique_Node_List& worklist) {
2362 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
2363 worklist.push(n->fast_out(i)); // Push on worklist
2364 }
2365 }
2366
2367 // Return counted loop Phi if as a counted loop exit condition, cmp
2368 // compares the induction variable with n
2369 static PhiNode* countedloop_phi_from_cmp(CmpNode* cmp, Node* n) {
2370 for (DUIterator_Fast imax, i = cmp->fast_outs(imax); i < imax; i++) {
2371 Node* bol = cmp->fast_out(i);
2372 for (DUIterator_Fast i2max, i2 = bol->fast_outs(i2max); i2 < i2max; i2++) {
2373 Node* iff = bol->fast_out(i2);
2374 if (iff->is_BaseCountedLoopEnd()) {
2375 BaseCountedLoopEndNode* cle = iff->as_BaseCountedLoopEnd();
2376 if (cle->limit() == n) {
2377 PhiNode* phi = cle->phi();
2378 if (phi != nullptr) {
2379 return phi;
2395 add_users_of_use_to_worklist(n, use, worklist);
2396 }
2397 }
2398
2399 void PhaseIterGVN::add_users_of_use_to_worklist(Node* n, Node* use, Unique_Node_List& worklist) {
2400 if(use->is_Multi() || // Multi-definer? Push projs on worklist
2401 use->is_Store() ) // Enable store/load same address
2402 add_users_to_worklist0(use, worklist);
2403
2404 // If we changed the receiver type to a call, we need to revisit
2405 // the Catch following the call. It's looking for a non-null
2406 // receiver to know when to enable the regular fall-through path
2407 // in addition to the NullPtrException path.
2408 if (use->is_CallDynamicJava() && n == use->in(TypeFunc::Parms)) {
2409 Node* p = use->as_CallDynamicJava()->proj_out_or_null(TypeFunc::Control);
2410 if (p != nullptr) {
2411 add_users_to_worklist0(p, worklist);
2412 }
2413 }
2414
2415 uint use_op = use->Opcode();
2416 if(use->is_Cmp()) { // Enable CMP/BOOL optimization
2417 add_users_to_worklist0(use, worklist); // Put Bool on worklist
2418 if (use->outcnt() > 0) {
2419 Node* bol = use->raw_out(0);
2420 if (bol->outcnt() > 0) {
2421 Node* iff = bol->raw_out(0);
2422 if (iff->outcnt() == 2) {
2423 // Look for the 'is_x2logic' pattern: "x ? : 0 : 1" and put the
2424 // phi merging either 0 or 1 onto the worklist
2425 Node* ifproj0 = iff->raw_out(0);
2426 Node* ifproj1 = iff->raw_out(1);
2427 if (ifproj0->outcnt() > 0 && ifproj1->outcnt() > 0) {
2428 Node* region0 = ifproj0->raw_out(0);
2429 Node* region1 = ifproj1->raw_out(0);
2430 if( region0 == region1 )
2431 add_users_to_worklist0(region0, worklist);
2432 }
2433 }
2434 }
2492 assert(n == in2, "only in2 modified");
2493 // Find all CastII with input in1.
2494 for (DUIterator_Fast jmax, j = in1->fast_outs(jmax); j < jmax; j++) {
2495 Node* castii = in1->fast_out(j);
2496 if (castii->is_CastII() && castii->as_CastII()->carry_dependency()) {
2497 // Find If.
2498 if (castii->in(0) != nullptr && castii->in(0)->in(0) != nullptr && castii->in(0)->in(0)->is_If()) {
2499 Node* ifnode = castii->in(0)->in(0);
2500 // Check that if connects to the cmp
2501 if (ifnode->in(1) != nullptr && ifnode->in(1)->is_Bool() && ifnode->in(1)->in(1) == cmp) {
2502 worklist.push(castii);
2503 }
2504 }
2505 }
2506 }
2507 }
2508 }
2509 }
2510 }
2511
2512 // If changed Cast input, notify down for Phi, Sub, and Xor - all do "uncast"
2513 // Patterns:
2514 // ConstraintCast+ -> Sub
2515 // ConstraintCast+ -> Phi
2516 // ConstraintCast+ -> Xor
2517 if (use->is_ConstraintCast()) {
2518 auto push_the_uses_to_worklist = [&](Node* n){
2519 if (n->is_Phi() || n->is_Sub() || n->Opcode() == Op_XorI || n->Opcode() == Op_XorL) {
2520 worklist.push(n);
2521 }
2522 };
2523 auto is_boundary = [](Node* n){ return !n->is_ConstraintCast(); };
2524 use->visit_uses(push_the_uses_to_worklist, is_boundary);
2525 }
2526 // If changed LShift inputs, check RShift users for useless sign-ext
2527 if (use_op == Op_LShiftI || use_op == Op_LShiftL) {
2528 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2529 Node* u = use->fast_out(i2);
2530 if (u->Opcode() == Op_RShiftI || u->Opcode() == Op_RShiftL)
2531 worklist.push(u);
2602 // If the ValidLengthTest input changes then the fallthrough path out of the AllocateArray may have become dead.
2603 // CatchNode::Value() is responsible for killing that path. The CatchNode has to be explicitly enqueued for igvn
2604 // to guarantee the change is not missed.
2605 if (use_op == Op_AllocateArray && n == use->in(AllocateNode::ValidLengthTest)) {
2606 Node* p = use->as_AllocateArray()->proj_out_or_null(TypeFunc::Control);
2607 if (p != nullptr) {
2608 add_users_to_worklist0(p, worklist);
2609 }
2610 }
2611
2612 if (use_op == Op_Initialize) {
2613 Node* imem = use->as_Initialize()->proj_out_or_null(TypeFunc::Memory);
2614 if (imem != nullptr) add_users_to_worklist0(imem, worklist);
2615 }
2616 // Loading the java mirror from a Klass requires two loads and the type
2617 // of the mirror load depends on the type of 'n'. See LoadNode::Value().
2618 // LoadBarrier?(LoadP(LoadP(AddP(foo:Klass, #java_mirror))))
2619 BarrierSetC2* bs = BarrierSet::barrier_set()->barrier_set_c2();
2620 bool has_load_barrier_nodes = bs->has_load_barrier_nodes();
2621
2622 if (use_op == Op_LoadP && use->bottom_type()->isa_rawptr()) {
2623 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2624 Node* u = use->fast_out(i2);
2625 const Type* ut = u->bottom_type();
2626 if (u->Opcode() == Op_LoadP && ut->isa_instptr()) {
2627 if (has_load_barrier_nodes) {
2628 // Search for load barriers behind the load
2629 for (DUIterator_Fast i3max, i3 = u->fast_outs(i3max); i3 < i3max; i3++) {
2630 Node* b = u->fast_out(i3);
2631 if (bs->is_gc_barrier_node(b)) {
2632 worklist.push(b);
2633 }
2634 }
2635 }
2636 worklist.push(u);
2637 }
2638 }
2639 }
2640 if (use->Opcode() == Op_OpaqueZeroTripGuard) {
2641 assert(use->outcnt() <= 1, "OpaqueZeroTripGuard can't be shared");
2642 if (use->outcnt() == 1) {
2643 Node* cmp = use->unique_out();
2644 worklist.push(cmp);
2645 }
2646 }
2647 if (use->Opcode() == Op_AddX) {
2648 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2649 Node* u = use->fast_out(i2);
2650 if (u->Opcode() == Op_CastX2P) {
2651 worklist.push(u);
2652 }
2653 }
2654 }
2655
2656 /* AndNode has a special handling when one of the operands is a LShiftNode:
2657 * (LHS << s) & RHS
2658 * if RHS fits in less than s bits, the value of this expression is 0.
2659 * The difficulty is that there might be a conversion node (ConvI2L) between
2735 //------------------------------PhaseCCP---------------------------------------
2736 // Conditional Constant Propagation, ala Wegman & Zadeck
2737 PhaseCCP::PhaseCCP( PhaseIterGVN *igvn ) : PhaseIterGVN(igvn) {
2738 NOT_PRODUCT( clear_constants(); )
2739 assert( _worklist.size() == 0, "" );
2740 analyze();
2741 }
2742
2743 #ifndef PRODUCT
2744 //------------------------------~PhaseCCP--------------------------------------
2745 PhaseCCP::~PhaseCCP() {
2746 inc_invokes();
2747 _total_constants += count_constants();
2748 }
2749 #endif
2750
2751
2752 #ifdef ASSERT
2753 void PhaseCCP::verify_type(Node* n, const Type* tnew, const Type* told) {
2754 if (tnew->meet(told) != tnew->remove_speculative()) {
2755 n->dump(1);
2756 tty->print("told = "); told->dump(); tty->cr();
2757 tty->print("tnew = "); tnew->dump(); tty->cr();
2758 fatal("Not monotonic");
2759 }
2760 assert(!told->isa_int() || !tnew->isa_int() || told->is_int()->_widen <= tnew->is_int()->_widen, "widen increases");
2761 assert(!told->isa_long() || !tnew->isa_long() || told->is_long()->_widen <= tnew->is_long()->_widen, "widen increases");
2762 }
2763 #endif //ASSERT
2764
2765 // In this analysis, all types are initially set to TOP. We iteratively call Value() on all nodes of the graph until
2766 // we reach a fixed-point (i.e. no types change anymore). We start with a list that only contains the root node. Each time
2767 // a new type is set, we push all uses of that node back to the worklist (in some cases, we also push grandchildren
2768 // or nodes even further down back to the worklist because their type could change as a result of the current type
2769 // change).
2770 void PhaseCCP::analyze() {
2771 // Initialize all types to TOP, optimistic analysis
2772 for (uint i = 0; i < C->unique(); i++) {
2773 _types.map(i, Type::TOP);
2774 }
2775
2857 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
2858 Node* use = n->fast_out(i);
2859 push_if_not_bottom_type(worklist, use);
2860 push_more_uses(worklist, n, use);
2861 }
2862 }
2863
2864 void PhaseCCP::push_if_not_bottom_type(Unique_Node_List& worklist, Node* n) const {
2865 if (n->bottom_type() != type(n)) {
2866 worklist.push(n);
2867 }
2868 }
2869
2870 // For some nodes, we need to propagate the type change to grandchildren or even further down.
2871 // Add them back to the worklist.
2872 void PhaseCCP::push_more_uses(Unique_Node_List& worklist, Node* parent, const Node* use) const {
2873 push_phis(worklist, use);
2874 push_catch(worklist, use);
2875 push_cmpu(worklist, use);
2876 push_counted_loop_phi(worklist, parent, use);
2877 push_loadp(worklist, use);
2878 push_and(worklist, parent, use);
2879 push_cast_ii(worklist, parent, use);
2880 push_opaque_zero_trip_guard(worklist, use);
2881 push_bool_with_cmpu_and_mask(worklist, use);
2882 }
2883
2884
2885 // We must recheck Phis too if use is a Region.
2886 void PhaseCCP::push_phis(Unique_Node_List& worklist, const Node* use) const {
2887 if (use->is_Region()) {
2888 for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
2889 push_if_not_bottom_type(worklist, use->fast_out(i));
2890 }
2891 }
2892 }
2893
2894 // If we changed the receiver type to a call, we need to revisit the Catch node following the call. It's looking for a
2895 // non-null receiver to know when to enable the regular fall-through path in addition to the NullPtrException path.
2896 // Same is true if the type of a ValidLengthTest input to an AllocateArrayNode changes.
2968 continue;
2969 }
2970
2971 Node* m = addI->in(1);
2972 if (m == andI->in(1) || m == andI->in(2)) {
2973 // Is "m" shared? Matched (1b) and thus we revisit Bool.
2974 push_if_not_bottom_type(worklist, bol);
2975 }
2976 }
2977 }
2978
2979 // 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'.
2980 // Seem PhiNode::Value().
2981 void PhaseCCP::push_counted_loop_phi(Unique_Node_List& worklist, Node* parent, const Node* use) {
2982 uint use_op = use->Opcode();
2983 if (use_op == Op_CmpI || use_op == Op_CmpL) {
2984 PhiNode* phi = countedloop_phi_from_cmp(use->as_Cmp(), parent);
2985 if (phi != nullptr) {
2986 worklist.push(phi);
2987 }
2988 }
2989 }
2990
2991 // Loading the java mirror from a Klass requires two loads and the type of the mirror load depends on the type of 'n'.
2992 // See LoadNode::Value().
2993 void PhaseCCP::push_loadp(Unique_Node_List& worklist, const Node* use) const {
2994 BarrierSetC2* barrier_set = BarrierSet::barrier_set()->barrier_set_c2();
2995 bool has_load_barrier_nodes = barrier_set->has_load_barrier_nodes();
2996
2997 if (use->Opcode() == Op_LoadP && use->bottom_type()->isa_rawptr()) {
2998 for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
2999 Node* loadp = use->fast_out(i);
3000 const Type* ut = loadp->bottom_type();
3001 if (loadp->Opcode() == Op_LoadP && ut->isa_instptr() && ut != type(loadp)) {
3002 if (has_load_barrier_nodes) {
3003 // Search for load barriers behind the load
3004 push_load_barrier(worklist, barrier_set, loadp);
3005 }
3006 worklist.push(loadp);
3007 }
|
1164 // SubNode::Value
1165 // CmpPNode::sub
1166 // MemNode::detect_ptr_independence
1167 // MemNode::all_controls_dominate
1168 // We find all controls of a pointer load, and see if they dominate the control of
1169 // an allocation. If they all dominate, we know the allocation is after (independent)
1170 // of the pointer load, and we can say the pointers are different. For this we call
1171 // n->dominates(sub, nlist) to check if controls n of the pointer load dominate the
1172 // control sub of the allocation. The problems is that sometimes dominates answers
1173 // false conservatively, and later it can determine that it is indeed true. Loops with
1174 // Region heads can lead to giving up, whereas LoopNodes can be skipped easier, and
1175 // so the traversal becomes more powerful. This is difficult to remidy, we would have
1176 // to notify the CmpP of CFG updates. Luckily, we recompute CmpP::Value during CCP
1177 // after loop-opts, so that should take care of many of these cases.
1178 return false;
1179 }
1180
1181 stringStream ss; // Print as a block without tty lock.
1182 ss.cr();
1183 ss.print_cr("Missed Value optimization:");
1184 n->dump_bfs(3, nullptr, "", &ss);
1185 ss.print_cr("Current type:");
1186 told->dump_on(&ss);
1187 ss.cr();
1188 ss.print_cr("Optimized type:");
1189 tnew->dump_on(&ss);
1190 ss.cr();
1191 tty->print_cr("%s", ss.as_string());
1192 return true;
1193 }
1194
1195 // Check that all Ideal optimizations that could be done were done.
1196 // Returns true if it found missed optimization opportunities and
1197 // false otherwise (no missed optimization, or skipped verification).
1198 bool PhaseIterGVN::verify_Ideal_for(Node* n, bool can_reshape) {
1199 // First, we check a list of exceptions, where we skip verification,
1200 // because there are known cases where Ideal can optimize after IGVN.
1201 // Some may be expected and cannot be fixed, and others should be fixed.
1202 switch (n->Opcode()) {
1203 // RangeCheckNode::Ideal looks up the chain for about 999 nodes
1204 // (see "Range-Check scan limit"). So, it is possible that something
2056 i->dump_bfs(1, nullptr, "", &ss);
2057 tty->print_cr("%s", ss.as_string());
2058 return true;
2059 }
2060 #endif
2061
2062 /**
2063 * Register a new node with the optimizer. Update the types array, the def-use
2064 * info. Put on worklist.
2065 */
2066 Node* PhaseIterGVN::register_new_node_with_optimizer(Node* n, Node* orig) {
2067 set_type_bottom(n);
2068 _worklist.push(n);
2069 if (orig != nullptr) C->copy_node_notes_to(n, orig);
2070 return n;
2071 }
2072
2073 //------------------------------transform--------------------------------------
2074 // Non-recursive: idealize Node 'n' with respect to its inputs and its value
2075 Node *PhaseIterGVN::transform( Node *n ) {
2076 // If brand new node, make space in type array, and give it a type.
2077 ensure_type_or_null(n);
2078 if (type_or_null(n) == nullptr) {
2079 set_type_bottom(n);
2080 }
2081
2082 if (_delay_transform) {
2083 // Add the node to the worklist but don't optimize for now
2084 _worklist.push(n);
2085 return n;
2086 }
2087
2088 return transform_old(n);
2089 }
2090
2091 Node *PhaseIterGVN::transform_old(Node* n) {
2092 NOT_PRODUCT(set_transforms());
2093 // Remove 'n' from hash table in case it gets modified
2094 _table.hash_delete(n);
2095 #ifdef ASSERT
2096 if (is_verify_def_use()) {
2097 assert(!_table.find_index(n->_idx), "found duplicate entry in table");
2098 }
2099 #endif
2100
2101 // Allow Bool -> Cmp idealisation in late inlining intrinsics that return a bool
2102 if (n->is_Cmp()) {
2103 add_users_to_worklist(n);
2104 }
2105
2106 // Apply the Ideal call in a loop until it no longer applies
2107 Node* k = n;
2340
2341 // Smash all inputs to 'old', isolating him completely
2342 Node *temp = new Node(1);
2343 temp->init_req(0,nn); // Add a use to nn to prevent him from dying
2344 remove_dead_node( old );
2345 temp->del_req(0); // Yank bogus edge
2346 if (nn != nullptr && nn->outcnt() == 0) {
2347 _worklist.push(nn);
2348 }
2349 #ifndef PRODUCT
2350 if (is_verify_def_use()) {
2351 for ( int i = 0; i < _verify_window_size; i++ ) {
2352 if ( _verify_window[i] == old )
2353 _verify_window[i] = nn;
2354 }
2355 }
2356 #endif
2357 temp->destruct(this); // reuse the _idx of this little guy
2358 }
2359
2360 void PhaseIterGVN::replace_in_uses(Node* n, Node* m) {
2361 assert(n != nullptr, "sanity");
2362 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
2363 Node* u = n->fast_out(i);
2364 if (u != n) {
2365 rehash_node_delayed(u);
2366 int nb = u->replace_edge(n, m);
2367 --i, imax -= nb;
2368 }
2369 }
2370 assert(n->outcnt() == 0, "all uses must be deleted");
2371 }
2372
2373 //------------------------------add_users_to_worklist--------------------------
2374 void PhaseIterGVN::add_users_to_worklist0(Node* n, Unique_Node_List& worklist) {
2375 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
2376 worklist.push(n->fast_out(i)); // Push on worklist
2377 }
2378 }
2379
2380 // Return counted loop Phi if as a counted loop exit condition, cmp
2381 // compares the induction variable with n
2382 static PhiNode* countedloop_phi_from_cmp(CmpNode* cmp, Node* n) {
2383 for (DUIterator_Fast imax, i = cmp->fast_outs(imax); i < imax; i++) {
2384 Node* bol = cmp->fast_out(i);
2385 for (DUIterator_Fast i2max, i2 = bol->fast_outs(i2max); i2 < i2max; i2++) {
2386 Node* iff = bol->fast_out(i2);
2387 if (iff->is_BaseCountedLoopEnd()) {
2388 BaseCountedLoopEndNode* cle = iff->as_BaseCountedLoopEnd();
2389 if (cle->limit() == n) {
2390 PhiNode* phi = cle->phi();
2391 if (phi != nullptr) {
2392 return phi;
2408 add_users_of_use_to_worklist(n, use, worklist);
2409 }
2410 }
2411
2412 void PhaseIterGVN::add_users_of_use_to_worklist(Node* n, Node* use, Unique_Node_List& worklist) {
2413 if(use->is_Multi() || // Multi-definer? Push projs on worklist
2414 use->is_Store() ) // Enable store/load same address
2415 add_users_to_worklist0(use, worklist);
2416
2417 // If we changed the receiver type to a call, we need to revisit
2418 // the Catch following the call. It's looking for a non-null
2419 // receiver to know when to enable the regular fall-through path
2420 // in addition to the NullPtrException path.
2421 if (use->is_CallDynamicJava() && n == use->in(TypeFunc::Parms)) {
2422 Node* p = use->as_CallDynamicJava()->proj_out_or_null(TypeFunc::Control);
2423 if (p != nullptr) {
2424 add_users_to_worklist0(p, worklist);
2425 }
2426 }
2427
2428 // AndLNode::Ideal folds GraphKit::mark_word_test patterns. Give it a chance to run.
2429 if (n->is_Load() && use->is_Phi()) {
2430 for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
2431 Node* u = use->fast_out(i);
2432 if (u->Opcode() == Op_AndL) {
2433 worklist.push(u);
2434 }
2435 }
2436 }
2437
2438 uint use_op = use->Opcode();
2439 if(use->is_Cmp()) { // Enable CMP/BOOL optimization
2440 add_users_to_worklist0(use, worklist); // Put Bool on worklist
2441 if (use->outcnt() > 0) {
2442 Node* bol = use->raw_out(0);
2443 if (bol->outcnt() > 0) {
2444 Node* iff = bol->raw_out(0);
2445 if (iff->outcnt() == 2) {
2446 // Look for the 'is_x2logic' pattern: "x ? : 0 : 1" and put the
2447 // phi merging either 0 or 1 onto the worklist
2448 Node* ifproj0 = iff->raw_out(0);
2449 Node* ifproj1 = iff->raw_out(1);
2450 if (ifproj0->outcnt() > 0 && ifproj1->outcnt() > 0) {
2451 Node* region0 = ifproj0->raw_out(0);
2452 Node* region1 = ifproj1->raw_out(0);
2453 if( region0 == region1 )
2454 add_users_to_worklist0(region0, worklist);
2455 }
2456 }
2457 }
2515 assert(n == in2, "only in2 modified");
2516 // Find all CastII with input in1.
2517 for (DUIterator_Fast jmax, j = in1->fast_outs(jmax); j < jmax; j++) {
2518 Node* castii = in1->fast_out(j);
2519 if (castii->is_CastII() && castii->as_CastII()->carry_dependency()) {
2520 // Find If.
2521 if (castii->in(0) != nullptr && castii->in(0)->in(0) != nullptr && castii->in(0)->in(0)->is_If()) {
2522 Node* ifnode = castii->in(0)->in(0);
2523 // Check that if connects to the cmp
2524 if (ifnode->in(1) != nullptr && ifnode->in(1)->is_Bool() && ifnode->in(1)->in(1) == cmp) {
2525 worklist.push(castii);
2526 }
2527 }
2528 }
2529 }
2530 }
2531 }
2532 }
2533 }
2534
2535 // Inline type nodes can have other inline types as users. If an input gets
2536 // updated, make sure that inline type users get a chance for optimization.
2537 if (use->is_InlineType()) {
2538 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2539 Node* u = use->fast_out(i2);
2540 if (u->is_InlineType())
2541 worklist.push(u);
2542 }
2543 }
2544 // If changed Cast input, notify down for Phi, Sub, and Xor - all do "uncast"
2545 // Patterns:
2546 // ConstraintCast+ -> Sub
2547 // ConstraintCast+ -> Phi
2548 // ConstraintCast+ -> Xor
2549 if (use->is_ConstraintCast()) {
2550 auto push_the_uses_to_worklist = [&](Node* n){
2551 if (n->is_Phi() || n->is_Sub() || n->Opcode() == Op_XorI || n->Opcode() == Op_XorL) {
2552 worklist.push(n);
2553 }
2554 };
2555 auto is_boundary = [](Node* n){ return !n->is_ConstraintCast(); };
2556 use->visit_uses(push_the_uses_to_worklist, is_boundary);
2557 }
2558 // If changed LShift inputs, check RShift users for useless sign-ext
2559 if (use_op == Op_LShiftI || use_op == Op_LShiftL) {
2560 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2561 Node* u = use->fast_out(i2);
2562 if (u->Opcode() == Op_RShiftI || u->Opcode() == Op_RShiftL)
2563 worklist.push(u);
2634 // If the ValidLengthTest input changes then the fallthrough path out of the AllocateArray may have become dead.
2635 // CatchNode::Value() is responsible for killing that path. The CatchNode has to be explicitly enqueued for igvn
2636 // to guarantee the change is not missed.
2637 if (use_op == Op_AllocateArray && n == use->in(AllocateNode::ValidLengthTest)) {
2638 Node* p = use->as_AllocateArray()->proj_out_or_null(TypeFunc::Control);
2639 if (p != nullptr) {
2640 add_users_to_worklist0(p, worklist);
2641 }
2642 }
2643
2644 if (use_op == Op_Initialize) {
2645 Node* imem = use->as_Initialize()->proj_out_or_null(TypeFunc::Memory);
2646 if (imem != nullptr) add_users_to_worklist0(imem, worklist);
2647 }
2648 // Loading the java mirror from a Klass requires two loads and the type
2649 // of the mirror load depends on the type of 'n'. See LoadNode::Value().
2650 // LoadBarrier?(LoadP(LoadP(AddP(foo:Klass, #java_mirror))))
2651 BarrierSetC2* bs = BarrierSet::barrier_set()->barrier_set_c2();
2652 bool has_load_barrier_nodes = bs->has_load_barrier_nodes();
2653
2654 if (use_op == Op_CastP2X) {
2655 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2656 Node* u = use->fast_out(i2);
2657 if (u->Opcode() == Op_AndX) {
2658 worklist.push(u);
2659 }
2660 }
2661 }
2662 if (use_op == Op_LoadP && use->bottom_type()->isa_rawptr()) {
2663 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2664 Node* u = use->fast_out(i2);
2665 const Type* ut = u->bottom_type();
2666 if (u->Opcode() == Op_LoadP && ut->isa_instptr()) {
2667 if (has_load_barrier_nodes) {
2668 // Search for load barriers behind the load
2669 for (DUIterator_Fast i3max, i3 = u->fast_outs(i3max); i3 < i3max; i3++) {
2670 Node* b = u->fast_out(i3);
2671 if (bs->is_gc_barrier_node(b)) {
2672 worklist.push(b);
2673 }
2674 }
2675 }
2676 worklist.push(u);
2677 }
2678 }
2679 }
2680 // Give CallStaticJavaNode::remove_useless_allocation a chance to run
2681 if (use->is_Region()) {
2682 Node* c = use;
2683 do {
2684 c = c->unique_ctrl_out_or_null();
2685 } while (c != nullptr && c->is_Region());
2686 if (c != nullptr && c->is_CallStaticJava() && c->as_CallStaticJava()->uncommon_trap_request() != 0) {
2687 worklist.push(c);
2688 }
2689 }
2690 if (use->Opcode() == Op_OpaqueZeroTripGuard) {
2691 assert(use->outcnt() <= 1, "OpaqueZeroTripGuard can't be shared");
2692 if (use->outcnt() == 1) {
2693 Node* cmp = use->unique_out();
2694 worklist.push(cmp);
2695 }
2696 }
2697 if (use->Opcode() == Op_AddX) {
2698 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2699 Node* u = use->fast_out(i2);
2700 if (u->Opcode() == Op_CastX2P) {
2701 worklist.push(u);
2702 }
2703 }
2704 }
2705
2706 /* AndNode has a special handling when one of the operands is a LShiftNode:
2707 * (LHS << s) & RHS
2708 * if RHS fits in less than s bits, the value of this expression is 0.
2709 * The difficulty is that there might be a conversion node (ConvI2L) between
2785 //------------------------------PhaseCCP---------------------------------------
2786 // Conditional Constant Propagation, ala Wegman & Zadeck
2787 PhaseCCP::PhaseCCP( PhaseIterGVN *igvn ) : PhaseIterGVN(igvn) {
2788 NOT_PRODUCT( clear_constants(); )
2789 assert( _worklist.size() == 0, "" );
2790 analyze();
2791 }
2792
2793 #ifndef PRODUCT
2794 //------------------------------~PhaseCCP--------------------------------------
2795 PhaseCCP::~PhaseCCP() {
2796 inc_invokes();
2797 _total_constants += count_constants();
2798 }
2799 #endif
2800
2801
2802 #ifdef ASSERT
2803 void PhaseCCP::verify_type(Node* n, const Type* tnew, const Type* told) {
2804 if (tnew->meet(told) != tnew->remove_speculative()) {
2805 n->dump(3);
2806 tty->print("told = "); told->dump(); tty->cr();
2807 tty->print("tnew = "); tnew->dump(); tty->cr();
2808 fatal("Not monotonic");
2809 }
2810 assert(!told->isa_int() || !tnew->isa_int() || told->is_int()->_widen <= tnew->is_int()->_widen, "widen increases");
2811 assert(!told->isa_long() || !tnew->isa_long() || told->is_long()->_widen <= tnew->is_long()->_widen, "widen increases");
2812 }
2813 #endif //ASSERT
2814
2815 // In this analysis, all types are initially set to TOP. We iteratively call Value() on all nodes of the graph until
2816 // we reach a fixed-point (i.e. no types change anymore). We start with a list that only contains the root node. Each time
2817 // a new type is set, we push all uses of that node back to the worklist (in some cases, we also push grandchildren
2818 // or nodes even further down back to the worklist because their type could change as a result of the current type
2819 // change).
2820 void PhaseCCP::analyze() {
2821 // Initialize all types to TOP, optimistic analysis
2822 for (uint i = 0; i < C->unique(); i++) {
2823 _types.map(i, Type::TOP);
2824 }
2825
2907 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
2908 Node* use = n->fast_out(i);
2909 push_if_not_bottom_type(worklist, use);
2910 push_more_uses(worklist, n, use);
2911 }
2912 }
2913
2914 void PhaseCCP::push_if_not_bottom_type(Unique_Node_List& worklist, Node* n) const {
2915 if (n->bottom_type() != type(n)) {
2916 worklist.push(n);
2917 }
2918 }
2919
2920 // For some nodes, we need to propagate the type change to grandchildren or even further down.
2921 // Add them back to the worklist.
2922 void PhaseCCP::push_more_uses(Unique_Node_List& worklist, Node* parent, const Node* use) const {
2923 push_phis(worklist, use);
2924 push_catch(worklist, use);
2925 push_cmpu(worklist, use);
2926 push_counted_loop_phi(worklist, parent, use);
2927 push_cast(worklist, use);
2928 push_loadp(worklist, use);
2929 push_and(worklist, parent, use);
2930 push_cast_ii(worklist, parent, use);
2931 push_opaque_zero_trip_guard(worklist, use);
2932 push_bool_with_cmpu_and_mask(worklist, use);
2933 }
2934
2935
2936 // We must recheck Phis too if use is a Region.
2937 void PhaseCCP::push_phis(Unique_Node_List& worklist, const Node* use) const {
2938 if (use->is_Region()) {
2939 for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
2940 push_if_not_bottom_type(worklist, use->fast_out(i));
2941 }
2942 }
2943 }
2944
2945 // If we changed the receiver type to a call, we need to revisit the Catch node following the call. It's looking for a
2946 // non-null receiver to know when to enable the regular fall-through path in addition to the NullPtrException path.
2947 // Same is true if the type of a ValidLengthTest input to an AllocateArrayNode changes.
3019 continue;
3020 }
3021
3022 Node* m = addI->in(1);
3023 if (m == andI->in(1) || m == andI->in(2)) {
3024 // Is "m" shared? Matched (1b) and thus we revisit Bool.
3025 push_if_not_bottom_type(worklist, bol);
3026 }
3027 }
3028 }
3029
3030 // 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'.
3031 // Seem PhiNode::Value().
3032 void PhaseCCP::push_counted_loop_phi(Unique_Node_List& worklist, Node* parent, const Node* use) {
3033 uint use_op = use->Opcode();
3034 if (use_op == Op_CmpI || use_op == Op_CmpL) {
3035 PhiNode* phi = countedloop_phi_from_cmp(use->as_Cmp(), parent);
3036 if (phi != nullptr) {
3037 worklist.push(phi);
3038 }
3039 }
3040 }
3041
3042 void PhaseCCP::push_cast(Unique_Node_List& worklist, const Node* use) {
3043 uint use_op = use->Opcode();
3044 if (use_op == Op_CastP2X) {
3045 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
3046 Node* u = use->fast_out(i2);
3047 if (u->Opcode() == Op_AndX) {
3048 worklist.push(u);
3049 }
3050 }
3051 }
3052 }
3053
3054 // Loading the java mirror from a Klass requires two loads and the type of the mirror load depends on the type of 'n'.
3055 // See LoadNode::Value().
3056 void PhaseCCP::push_loadp(Unique_Node_List& worklist, const Node* use) const {
3057 BarrierSetC2* barrier_set = BarrierSet::barrier_set()->barrier_set_c2();
3058 bool has_load_barrier_nodes = barrier_set->has_load_barrier_nodes();
3059
3060 if (use->Opcode() == Op_LoadP && use->bottom_type()->isa_rawptr()) {
3061 for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
3062 Node* loadp = use->fast_out(i);
3063 const Type* ut = loadp->bottom_type();
3064 if (loadp->Opcode() == Op_LoadP && ut->isa_instptr() && ut != type(loadp)) {
3065 if (has_load_barrier_nodes) {
3066 // Search for load barriers behind the load
3067 push_load_barrier(worklist, barrier_set, loadp);
3068 }
3069 worklist.push(loadp);
3070 }
|