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
2045 i->dump_bfs(1, nullptr, "", &ss);
2046 tty->print_cr("%s", ss.as_string());
2047 return true;
2048 }
2049 #endif
2050
2051 /**
2052 * Register a new node with the optimizer. Update the types array, the def-use
2053 * info. Put on worklist.
2054 */
2055 Node* PhaseIterGVN::register_new_node_with_optimizer(Node* n, Node* orig) {
2056 set_type_bottom(n);
2057 _worklist.push(n);
2058 if (orig != nullptr) C->copy_node_notes_to(n, orig);
2059 return n;
2060 }
2061
2062 //------------------------------transform--------------------------------------
2063 // Non-recursive: idealize Node 'n' with respect to its inputs and its value
2064 Node *PhaseIterGVN::transform( Node *n ) {
2065 if (_delay_transform) {
2066 // Register the node but don't optimize for now
2067 register_new_node_with_optimizer(n);
2068 return n;
2069 }
2070
2071 // If brand new node, make space in type array, and give it a type.
2072 ensure_type_or_null(n);
2073 if (type_or_null(n) == nullptr) {
2074 set_type_bottom(n);
2075 }
2076
2077 return transform_old(n);
2078 }
2079
2080 Node *PhaseIterGVN::transform_old(Node* n) {
2081 NOT_PRODUCT(set_transforms());
2082 // Remove 'n' from hash table in case it gets modified
2083 _table.hash_delete(n);
2084 #ifdef ASSERT
2085 if (is_verify_def_use()) {
2086 assert(!_table.find_index(n->_idx), "found duplicate entry in table");
2087 }
2088 #endif
2089
2090 // Allow Bool -> Cmp idealisation in late inlining intrinsics that return a bool
2091 if (n->is_Cmp()) {
2092 add_users_to_worklist(n);
2093 }
2094
2095 // Apply the Ideal call in a loop until it no longer applies
2096 Node* k = n;
2329
2330 // Smash all inputs to 'old', isolating him completely
2331 Node *temp = new Node(1);
2332 temp->init_req(0,nn); // Add a use to nn to prevent him from dying
2333 remove_dead_node( old );
2334 temp->del_req(0); // Yank bogus edge
2335 if (nn != nullptr && nn->outcnt() == 0) {
2336 _worklist.push(nn);
2337 }
2338 #ifndef PRODUCT
2339 if (is_verify_def_use()) {
2340 for ( int i = 0; i < _verify_window_size; i++ ) {
2341 if ( _verify_window[i] == old )
2342 _verify_window[i] = nn;
2343 }
2344 }
2345 #endif
2346 temp->destruct(this); // reuse the _idx of this little guy
2347 }
2348
2349 //------------------------------add_users_to_worklist--------------------------
2350 void PhaseIterGVN::add_users_to_worklist0(Node* n, Unique_Node_List& worklist) {
2351 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
2352 worklist.push(n->fast_out(i)); // Push on worklist
2353 }
2354 }
2355
2356 // Return counted loop Phi if as a counted loop exit condition, cmp
2357 // compares the induction variable with n
2358 static PhiNode* countedloop_phi_from_cmp(CmpNode* cmp, Node* n) {
2359 for (DUIterator_Fast imax, i = cmp->fast_outs(imax); i < imax; i++) {
2360 Node* bol = cmp->fast_out(i);
2361 for (DUIterator_Fast i2max, i2 = bol->fast_outs(i2max); i2 < i2max; i2++) {
2362 Node* iff = bol->fast_out(i2);
2363 if (iff->is_BaseCountedLoopEnd()) {
2364 BaseCountedLoopEndNode* cle = iff->as_BaseCountedLoopEnd();
2365 if (cle->limit() == n) {
2366 PhiNode* phi = cle->phi();
2367 if (phi != nullptr) {
2368 return phi;
2384 add_users_of_use_to_worklist(n, use, worklist);
2385 }
2386 }
2387
2388 void PhaseIterGVN::add_users_of_use_to_worklist(Node* n, Node* use, Unique_Node_List& worklist) {
2389 if(use->is_Multi() || // Multi-definer? Push projs on worklist
2390 use->is_Store() ) // Enable store/load same address
2391 add_users_to_worklist0(use, worklist);
2392
2393 // If we changed the receiver type to a call, we need to revisit
2394 // the Catch following the call. It's looking for a non-null
2395 // receiver to know when to enable the regular fall-through path
2396 // in addition to the NullPtrException path.
2397 if (use->is_CallDynamicJava() && n == use->in(TypeFunc::Parms)) {
2398 Node* p = use->as_CallDynamicJava()->proj_out_or_null(TypeFunc::Control);
2399 if (p != nullptr) {
2400 add_users_to_worklist0(p, worklist);
2401 }
2402 }
2403
2404 uint use_op = use->Opcode();
2405 if(use->is_Cmp()) { // Enable CMP/BOOL optimization
2406 add_users_to_worklist0(use, worklist); // Put Bool on worklist
2407 if (use->outcnt() > 0) {
2408 Node* bol = use->raw_out(0);
2409 if (bol->outcnt() > 0) {
2410 Node* iff = bol->raw_out(0);
2411 if (iff->outcnt() == 2) {
2412 // Look for the 'is_x2logic' pattern: "x ? : 0 : 1" and put the
2413 // phi merging either 0 or 1 onto the worklist
2414 Node* ifproj0 = iff->raw_out(0);
2415 Node* ifproj1 = iff->raw_out(1);
2416 if (ifproj0->outcnt() > 0 && ifproj1->outcnt() > 0) {
2417 Node* region0 = ifproj0->raw_out(0);
2418 Node* region1 = ifproj1->raw_out(0);
2419 if( region0 == region1 )
2420 add_users_to_worklist0(region0, worklist);
2421 }
2422 }
2423 }
2481 assert(n == in2, "only in2 modified");
2482 // Find all CastII with input in1.
2483 for (DUIterator_Fast jmax, j = in1->fast_outs(jmax); j < jmax; j++) {
2484 Node* castii = in1->fast_out(j);
2485 if (castii->is_CastII() && castii->as_CastII()->carry_dependency()) {
2486 // Find If.
2487 if (castii->in(0) != nullptr && castii->in(0)->in(0) != nullptr && castii->in(0)->in(0)->is_If()) {
2488 Node* ifnode = castii->in(0)->in(0);
2489 // Check that if connects to the cmp
2490 if (ifnode->in(1) != nullptr && ifnode->in(1)->is_Bool() && ifnode->in(1)->in(1) == cmp) {
2491 worklist.push(castii);
2492 }
2493 }
2494 }
2495 }
2496 }
2497 }
2498 }
2499 }
2500
2501 // If changed Cast input, notify down for Phi, Sub, and Xor - all do "uncast"
2502 // Patterns:
2503 // ConstraintCast+ -> Sub
2504 // ConstraintCast+ -> Phi
2505 // ConstraintCast+ -> Xor
2506 if (use->is_ConstraintCast()) {
2507 auto push_the_uses_to_worklist = [&](Node* n){
2508 if (n->is_Phi() || n->is_Sub() || n->Opcode() == Op_XorI || n->Opcode() == Op_XorL) {
2509 worklist.push(n);
2510 }
2511 };
2512 auto is_boundary = [](Node* n){ return !n->is_ConstraintCast(); };
2513 use->visit_uses(push_the_uses_to_worklist, is_boundary);
2514 }
2515 // If changed LShift inputs, check RShift users for useless sign-ext
2516 if (use_op == Op_LShiftI || use_op == Op_LShiftL) {
2517 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2518 Node* u = use->fast_out(i2);
2519 if (u->Opcode() == Op_RShiftI || u->Opcode() == Op_RShiftL)
2520 worklist.push(u);
2564 // If the ValidLengthTest input changes then the fallthrough path out of the AllocateArray may have become dead.
2565 // CatchNode::Value() is responsible for killing that path. The CatchNode has to be explicitly enqueued for igvn
2566 // to guarantee the change is not missed.
2567 if (use_op == Op_AllocateArray && n == use->in(AllocateNode::ValidLengthTest)) {
2568 Node* p = use->as_AllocateArray()->proj_out_or_null(TypeFunc::Control);
2569 if (p != nullptr) {
2570 add_users_to_worklist0(p, worklist);
2571 }
2572 }
2573
2574 if (use_op == Op_Initialize) {
2575 Node* imem = use->as_Initialize()->proj_out_or_null(TypeFunc::Memory);
2576 if (imem != nullptr) add_users_to_worklist0(imem, worklist);
2577 }
2578 // Loading the java mirror from a Klass requires two loads and the type
2579 // of the mirror load depends on the type of 'n'. See LoadNode::Value().
2580 // LoadBarrier?(LoadP(LoadP(AddP(foo:Klass, #java_mirror))))
2581 BarrierSetC2* bs = BarrierSet::barrier_set()->barrier_set_c2();
2582 bool has_load_barrier_nodes = bs->has_load_barrier_nodes();
2583
2584 if (use_op == Op_LoadP && use->bottom_type()->isa_rawptr()) {
2585 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2586 Node* u = use->fast_out(i2);
2587 const Type* ut = u->bottom_type();
2588 if (u->Opcode() == Op_LoadP && ut->isa_instptr()) {
2589 if (has_load_barrier_nodes) {
2590 // Search for load barriers behind the load
2591 for (DUIterator_Fast i3max, i3 = u->fast_outs(i3max); i3 < i3max; i3++) {
2592 Node* b = u->fast_out(i3);
2593 if (bs->is_gc_barrier_node(b)) {
2594 worklist.push(b);
2595 }
2596 }
2597 }
2598 worklist.push(u);
2599 }
2600 }
2601 }
2602 if (use->Opcode() == Op_OpaqueZeroTripGuard) {
2603 assert(use->outcnt() <= 1, "OpaqueZeroTripGuard can't be shared");
2604 if (use->outcnt() == 1) {
2605 Node* cmp = use->unique_out();
2606 worklist.push(cmp);
2607 }
2608 }
2609 if (use->Opcode() == Op_AddX) {
2610 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2611 Node* u = use->fast_out(i2);
2612 if (u->Opcode() == Op_CastX2P) {
2613 worklist.push(u);
2614 }
2615 }
2616 }
2617
2618 /* AndNode has a special handling when one of the operands is a LShiftNode:
2619 * (LHS << s) & RHS
2620 * if RHS fits in less than s bits, the value of this expression is 0.
2621 * The difficulty is that there might be a conversion node (ConvI2L) between
2697 //------------------------------PhaseCCP---------------------------------------
2698 // Conditional Constant Propagation, ala Wegman & Zadeck
2699 PhaseCCP::PhaseCCP( PhaseIterGVN *igvn ) : PhaseIterGVN(igvn) {
2700 NOT_PRODUCT( clear_constants(); )
2701 assert( _worklist.size() == 0, "" );
2702 analyze();
2703 }
2704
2705 #ifndef PRODUCT
2706 //------------------------------~PhaseCCP--------------------------------------
2707 PhaseCCP::~PhaseCCP() {
2708 inc_invokes();
2709 _total_constants += count_constants();
2710 }
2711 #endif
2712
2713
2714 #ifdef ASSERT
2715 void PhaseCCP::verify_type(Node* n, const Type* tnew, const Type* told) {
2716 if (tnew->meet(told) != tnew->remove_speculative()) {
2717 n->dump(1);
2718 tty->print("told = "); told->dump(); tty->cr();
2719 tty->print("tnew = "); tnew->dump(); tty->cr();
2720 fatal("Not monotonic");
2721 }
2722 assert(!told->isa_int() || !tnew->isa_int() || told->is_int()->_widen <= tnew->is_int()->_widen, "widen increases");
2723 assert(!told->isa_long() || !tnew->isa_long() || told->is_long()->_widen <= tnew->is_long()->_widen, "widen increases");
2724 }
2725 #endif //ASSERT
2726
2727 // In this analysis, all types are initially set to TOP. We iteratively call Value() on all nodes of the graph until
2728 // we reach a fixed-point (i.e. no types change anymore). We start with a list that only contains the root node. Each time
2729 // a new type is set, we push all uses of that node back to the worklist (in some cases, we also push grandchildren
2730 // or nodes even further down back to the worklist because their type could change as a result of the current type
2731 // change).
2732 void PhaseCCP::analyze() {
2733 // Initialize all types to TOP, optimistic analysis
2734 for (uint i = 0; i < C->unique(); i++) {
2735 _types.map(i, Type::TOP);
2736 }
2737
2819 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
2820 Node* use = n->fast_out(i);
2821 push_if_not_bottom_type(worklist, use);
2822 push_more_uses(worklist, n, use);
2823 }
2824 }
2825
2826 void PhaseCCP::push_if_not_bottom_type(Unique_Node_List& worklist, Node* n) const {
2827 if (n->bottom_type() != type(n)) {
2828 worklist.push(n);
2829 }
2830 }
2831
2832 // For some nodes, we need to propagate the type change to grandchildren or even further down.
2833 // Add them back to the worklist.
2834 void PhaseCCP::push_more_uses(Unique_Node_List& worklist, Node* parent, const Node* use) const {
2835 push_phis(worklist, use);
2836 push_catch(worklist, use);
2837 push_cmpu(worklist, use);
2838 push_counted_loop_phi(worklist, parent, use);
2839 push_loadp(worklist, use);
2840 push_and(worklist, parent, use);
2841 push_cast_ii(worklist, parent, use);
2842 push_opaque_zero_trip_guard(worklist, use);
2843 }
2844
2845
2846 // We must recheck Phis too if use is a Region.
2847 void PhaseCCP::push_phis(Unique_Node_List& worklist, const Node* use) const {
2848 if (use->is_Region()) {
2849 for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
2850 push_if_not_bottom_type(worklist, use->fast_out(i));
2851 }
2852 }
2853 }
2854
2855 // If we changed the receiver type to a call, we need to revisit the Catch node following the call. It's looking for a
2856 // non-null receiver to know when to enable the regular fall-through path in addition to the NullPtrException path.
2857 // Same is true if the type of a ValidLengthTest input to an AllocateArrayNode changes.
2858 void PhaseCCP::push_catch(Unique_Node_List& worklist, const Node* use) {
2878 for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
2879 Node* cmpu = use->fast_out(i);
2880 const uint cmpu_opcode = cmpu->Opcode();
2881 if (cmpu_opcode == Op_CmpU || cmpu_opcode == Op_CmpU3) {
2882 // Got a CmpU or CmpU3 which might need the new type information from node n.
2883 push_if_not_bottom_type(worklist, cmpu);
2884 }
2885 }
2886 }
2887 }
2888
2889 // 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'.
2890 // Seem PhiNode::Value().
2891 void PhaseCCP::push_counted_loop_phi(Unique_Node_List& worklist, Node* parent, const Node* use) {
2892 uint use_op = use->Opcode();
2893 if (use_op == Op_CmpI || use_op == Op_CmpL) {
2894 PhiNode* phi = countedloop_phi_from_cmp(use->as_Cmp(), parent);
2895 if (phi != nullptr) {
2896 worklist.push(phi);
2897 }
2898 }
2899 }
2900
2901 // Loading the java mirror from a Klass requires two loads and the type of the mirror load depends on the type of 'n'.
2902 // See LoadNode::Value().
2903 void PhaseCCP::push_loadp(Unique_Node_List& worklist, const Node* use) const {
2904 BarrierSetC2* barrier_set = BarrierSet::barrier_set()->barrier_set_c2();
2905 bool has_load_barrier_nodes = barrier_set->has_load_barrier_nodes();
2906
2907 if (use->Opcode() == Op_LoadP && use->bottom_type()->isa_rawptr()) {
2908 for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
2909 Node* loadp = use->fast_out(i);
2910 const Type* ut = loadp->bottom_type();
2911 if (loadp->Opcode() == Op_LoadP && ut->isa_instptr() && ut != type(loadp)) {
2912 if (has_load_barrier_nodes) {
2913 // Search for load barriers behind the load
2914 push_load_barrier(worklist, barrier_set, loadp);
2915 }
2916 worklist.push(loadp);
2917 }
|
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
2045 i->dump_bfs(1, nullptr, "", &ss);
2046 tty->print_cr("%s", ss.as_string());
2047 return true;
2048 }
2049 #endif
2050
2051 /**
2052 * Register a new node with the optimizer. Update the types array, the def-use
2053 * info. Put on worklist.
2054 */
2055 Node* PhaseIterGVN::register_new_node_with_optimizer(Node* n, Node* orig) {
2056 set_type_bottom(n);
2057 _worklist.push(n);
2058 if (orig != nullptr) C->copy_node_notes_to(n, orig);
2059 return n;
2060 }
2061
2062 //------------------------------transform--------------------------------------
2063 // Non-recursive: idealize Node 'n' with respect to its inputs and its value
2064 Node *PhaseIterGVN::transform( Node *n ) {
2065 // If brand new node, make space in type array, and give it a type.
2066 ensure_type_or_null(n);
2067 if (type_or_null(n) == nullptr) {
2068 set_type_bottom(n);
2069 }
2070
2071 if (_delay_transform) {
2072 // Add the node to the worklist but don't optimize for now
2073 _worklist.push(n);
2074 return n;
2075 }
2076
2077 return transform_old(n);
2078 }
2079
2080 Node *PhaseIterGVN::transform_old(Node* n) {
2081 NOT_PRODUCT(set_transforms());
2082 // Remove 'n' from hash table in case it gets modified
2083 _table.hash_delete(n);
2084 #ifdef ASSERT
2085 if (is_verify_def_use()) {
2086 assert(!_table.find_index(n->_idx), "found duplicate entry in table");
2087 }
2088 #endif
2089
2090 // Allow Bool -> Cmp idealisation in late inlining intrinsics that return a bool
2091 if (n->is_Cmp()) {
2092 add_users_to_worklist(n);
2093 }
2094
2095 // Apply the Ideal call in a loop until it no longer applies
2096 Node* k = n;
2329
2330 // Smash all inputs to 'old', isolating him completely
2331 Node *temp = new Node(1);
2332 temp->init_req(0,nn); // Add a use to nn to prevent him from dying
2333 remove_dead_node( old );
2334 temp->del_req(0); // Yank bogus edge
2335 if (nn != nullptr && nn->outcnt() == 0) {
2336 _worklist.push(nn);
2337 }
2338 #ifndef PRODUCT
2339 if (is_verify_def_use()) {
2340 for ( int i = 0; i < _verify_window_size; i++ ) {
2341 if ( _verify_window[i] == old )
2342 _verify_window[i] = nn;
2343 }
2344 }
2345 #endif
2346 temp->destruct(this); // reuse the _idx of this little guy
2347 }
2348
2349 void PhaseIterGVN::replace_in_uses(Node* n, Node* m) {
2350 assert(n != nullptr, "sanity");
2351 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
2352 Node* u = n->fast_out(i);
2353 if (u != n) {
2354 rehash_node_delayed(u);
2355 int nb = u->replace_edge(n, m);
2356 --i, imax -= nb;
2357 }
2358 }
2359 assert(n->outcnt() == 0, "all uses must be deleted");
2360 }
2361
2362 //------------------------------add_users_to_worklist--------------------------
2363 void PhaseIterGVN::add_users_to_worklist0(Node* n, Unique_Node_List& worklist) {
2364 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
2365 worklist.push(n->fast_out(i)); // Push on worklist
2366 }
2367 }
2368
2369 // Return counted loop Phi if as a counted loop exit condition, cmp
2370 // compares the induction variable with n
2371 static PhiNode* countedloop_phi_from_cmp(CmpNode* cmp, Node* n) {
2372 for (DUIterator_Fast imax, i = cmp->fast_outs(imax); i < imax; i++) {
2373 Node* bol = cmp->fast_out(i);
2374 for (DUIterator_Fast i2max, i2 = bol->fast_outs(i2max); i2 < i2max; i2++) {
2375 Node* iff = bol->fast_out(i2);
2376 if (iff->is_BaseCountedLoopEnd()) {
2377 BaseCountedLoopEndNode* cle = iff->as_BaseCountedLoopEnd();
2378 if (cle->limit() == n) {
2379 PhiNode* phi = cle->phi();
2380 if (phi != nullptr) {
2381 return phi;
2397 add_users_of_use_to_worklist(n, use, worklist);
2398 }
2399 }
2400
2401 void PhaseIterGVN::add_users_of_use_to_worklist(Node* n, Node* use, Unique_Node_List& worklist) {
2402 if(use->is_Multi() || // Multi-definer? Push projs on worklist
2403 use->is_Store() ) // Enable store/load same address
2404 add_users_to_worklist0(use, worklist);
2405
2406 // If we changed the receiver type to a call, we need to revisit
2407 // the Catch following the call. It's looking for a non-null
2408 // receiver to know when to enable the regular fall-through path
2409 // in addition to the NullPtrException path.
2410 if (use->is_CallDynamicJava() && n == use->in(TypeFunc::Parms)) {
2411 Node* p = use->as_CallDynamicJava()->proj_out_or_null(TypeFunc::Control);
2412 if (p != nullptr) {
2413 add_users_to_worklist0(p, worklist);
2414 }
2415 }
2416
2417 // AndLNode::Ideal folds GraphKit::mark_word_test patterns. Give it a chance to run.
2418 if (n->is_Load() && use->is_Phi()) {
2419 for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
2420 Node* u = use->fast_out(i);
2421 if (u->Opcode() == Op_AndL) {
2422 worklist.push(u);
2423 }
2424 }
2425 }
2426
2427 uint use_op = use->Opcode();
2428 if(use->is_Cmp()) { // Enable CMP/BOOL optimization
2429 add_users_to_worklist0(use, worklist); // Put Bool on worklist
2430 if (use->outcnt() > 0) {
2431 Node* bol = use->raw_out(0);
2432 if (bol->outcnt() > 0) {
2433 Node* iff = bol->raw_out(0);
2434 if (iff->outcnt() == 2) {
2435 // Look for the 'is_x2logic' pattern: "x ? : 0 : 1" and put the
2436 // phi merging either 0 or 1 onto the worklist
2437 Node* ifproj0 = iff->raw_out(0);
2438 Node* ifproj1 = iff->raw_out(1);
2439 if (ifproj0->outcnt() > 0 && ifproj1->outcnt() > 0) {
2440 Node* region0 = ifproj0->raw_out(0);
2441 Node* region1 = ifproj1->raw_out(0);
2442 if( region0 == region1 )
2443 add_users_to_worklist0(region0, worklist);
2444 }
2445 }
2446 }
2504 assert(n == in2, "only in2 modified");
2505 // Find all CastII with input in1.
2506 for (DUIterator_Fast jmax, j = in1->fast_outs(jmax); j < jmax; j++) {
2507 Node* castii = in1->fast_out(j);
2508 if (castii->is_CastII() && castii->as_CastII()->carry_dependency()) {
2509 // Find If.
2510 if (castii->in(0) != nullptr && castii->in(0)->in(0) != nullptr && castii->in(0)->in(0)->is_If()) {
2511 Node* ifnode = castii->in(0)->in(0);
2512 // Check that if connects to the cmp
2513 if (ifnode->in(1) != nullptr && ifnode->in(1)->is_Bool() && ifnode->in(1)->in(1) == cmp) {
2514 worklist.push(castii);
2515 }
2516 }
2517 }
2518 }
2519 }
2520 }
2521 }
2522 }
2523
2524 // Inline type nodes can have other inline types as users. If an input gets
2525 // updated, make sure that inline type users get a chance for optimization.
2526 if (use->is_InlineType()) {
2527 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2528 Node* u = use->fast_out(i2);
2529 if (u->is_InlineType())
2530 worklist.push(u);
2531 }
2532 }
2533 // If changed Cast input, notify down for Phi, Sub, and Xor - all do "uncast"
2534 // Patterns:
2535 // ConstraintCast+ -> Sub
2536 // ConstraintCast+ -> Phi
2537 // ConstraintCast+ -> Xor
2538 if (use->is_ConstraintCast()) {
2539 auto push_the_uses_to_worklist = [&](Node* n){
2540 if (n->is_Phi() || n->is_Sub() || n->Opcode() == Op_XorI || n->Opcode() == Op_XorL) {
2541 worklist.push(n);
2542 }
2543 };
2544 auto is_boundary = [](Node* n){ return !n->is_ConstraintCast(); };
2545 use->visit_uses(push_the_uses_to_worklist, is_boundary);
2546 }
2547 // If changed LShift inputs, check RShift users for useless sign-ext
2548 if (use_op == Op_LShiftI || use_op == Op_LShiftL) {
2549 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2550 Node* u = use->fast_out(i2);
2551 if (u->Opcode() == Op_RShiftI || u->Opcode() == Op_RShiftL)
2552 worklist.push(u);
2596 // If the ValidLengthTest input changes then the fallthrough path out of the AllocateArray may have become dead.
2597 // CatchNode::Value() is responsible for killing that path. The CatchNode has to be explicitly enqueued for igvn
2598 // to guarantee the change is not missed.
2599 if (use_op == Op_AllocateArray && n == use->in(AllocateNode::ValidLengthTest)) {
2600 Node* p = use->as_AllocateArray()->proj_out_or_null(TypeFunc::Control);
2601 if (p != nullptr) {
2602 add_users_to_worklist0(p, worklist);
2603 }
2604 }
2605
2606 if (use_op == Op_Initialize) {
2607 Node* imem = use->as_Initialize()->proj_out_or_null(TypeFunc::Memory);
2608 if (imem != nullptr) add_users_to_worklist0(imem, worklist);
2609 }
2610 // Loading the java mirror from a Klass requires two loads and the type
2611 // of the mirror load depends on the type of 'n'. See LoadNode::Value().
2612 // LoadBarrier?(LoadP(LoadP(AddP(foo:Klass, #java_mirror))))
2613 BarrierSetC2* bs = BarrierSet::barrier_set()->barrier_set_c2();
2614 bool has_load_barrier_nodes = bs->has_load_barrier_nodes();
2615
2616 if (use_op == Op_CastP2X) {
2617 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2618 Node* u = use->fast_out(i2);
2619 if (u->Opcode() == Op_AndX) {
2620 worklist.push(u);
2621 }
2622 }
2623 }
2624 if (use_op == Op_LoadP && use->bottom_type()->isa_rawptr()) {
2625 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2626 Node* u = use->fast_out(i2);
2627 const Type* ut = u->bottom_type();
2628 if (u->Opcode() == Op_LoadP && ut->isa_instptr()) {
2629 if (has_load_barrier_nodes) {
2630 // Search for load barriers behind the load
2631 for (DUIterator_Fast i3max, i3 = u->fast_outs(i3max); i3 < i3max; i3++) {
2632 Node* b = u->fast_out(i3);
2633 if (bs->is_gc_barrier_node(b)) {
2634 worklist.push(b);
2635 }
2636 }
2637 }
2638 worklist.push(u);
2639 }
2640 }
2641 }
2642 // Give CallStaticJavaNode::remove_useless_allocation a chance to run
2643 if (use->is_Region()) {
2644 Node* c = use;
2645 do {
2646 c = c->unique_ctrl_out_or_null();
2647 } while (c != nullptr && c->is_Region());
2648 if (c != nullptr && c->is_CallStaticJava() && c->as_CallStaticJava()->uncommon_trap_request() != 0) {
2649 worklist.push(c);
2650 }
2651 }
2652 if (use->Opcode() == Op_OpaqueZeroTripGuard) {
2653 assert(use->outcnt() <= 1, "OpaqueZeroTripGuard can't be shared");
2654 if (use->outcnt() == 1) {
2655 Node* cmp = use->unique_out();
2656 worklist.push(cmp);
2657 }
2658 }
2659 if (use->Opcode() == Op_AddX) {
2660 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2661 Node* u = use->fast_out(i2);
2662 if (u->Opcode() == Op_CastX2P) {
2663 worklist.push(u);
2664 }
2665 }
2666 }
2667
2668 /* AndNode has a special handling when one of the operands is a LShiftNode:
2669 * (LHS << s) & RHS
2670 * if RHS fits in less than s bits, the value of this expression is 0.
2671 * The difficulty is that there might be a conversion node (ConvI2L) between
2747 //------------------------------PhaseCCP---------------------------------------
2748 // Conditional Constant Propagation, ala Wegman & Zadeck
2749 PhaseCCP::PhaseCCP( PhaseIterGVN *igvn ) : PhaseIterGVN(igvn) {
2750 NOT_PRODUCT( clear_constants(); )
2751 assert( _worklist.size() == 0, "" );
2752 analyze();
2753 }
2754
2755 #ifndef PRODUCT
2756 //------------------------------~PhaseCCP--------------------------------------
2757 PhaseCCP::~PhaseCCP() {
2758 inc_invokes();
2759 _total_constants += count_constants();
2760 }
2761 #endif
2762
2763
2764 #ifdef ASSERT
2765 void PhaseCCP::verify_type(Node* n, const Type* tnew, const Type* told) {
2766 if (tnew->meet(told) != tnew->remove_speculative()) {
2767 n->dump(3);
2768 tty->print("told = "); told->dump(); tty->cr();
2769 tty->print("tnew = "); tnew->dump(); tty->cr();
2770 fatal("Not monotonic");
2771 }
2772 assert(!told->isa_int() || !tnew->isa_int() || told->is_int()->_widen <= tnew->is_int()->_widen, "widen increases");
2773 assert(!told->isa_long() || !tnew->isa_long() || told->is_long()->_widen <= tnew->is_long()->_widen, "widen increases");
2774 }
2775 #endif //ASSERT
2776
2777 // In this analysis, all types are initially set to TOP. We iteratively call Value() on all nodes of the graph until
2778 // we reach a fixed-point (i.e. no types change anymore). We start with a list that only contains the root node. Each time
2779 // a new type is set, we push all uses of that node back to the worklist (in some cases, we also push grandchildren
2780 // or nodes even further down back to the worklist because their type could change as a result of the current type
2781 // change).
2782 void PhaseCCP::analyze() {
2783 // Initialize all types to TOP, optimistic analysis
2784 for (uint i = 0; i < C->unique(); i++) {
2785 _types.map(i, Type::TOP);
2786 }
2787
2869 for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
2870 Node* use = n->fast_out(i);
2871 push_if_not_bottom_type(worklist, use);
2872 push_more_uses(worklist, n, use);
2873 }
2874 }
2875
2876 void PhaseCCP::push_if_not_bottom_type(Unique_Node_List& worklist, Node* n) const {
2877 if (n->bottom_type() != type(n)) {
2878 worklist.push(n);
2879 }
2880 }
2881
2882 // For some nodes, we need to propagate the type change to grandchildren or even further down.
2883 // Add them back to the worklist.
2884 void PhaseCCP::push_more_uses(Unique_Node_List& worklist, Node* parent, const Node* use) const {
2885 push_phis(worklist, use);
2886 push_catch(worklist, use);
2887 push_cmpu(worklist, use);
2888 push_counted_loop_phi(worklist, parent, use);
2889 push_cast(worklist, use);
2890 push_loadp(worklist, use);
2891 push_and(worklist, parent, use);
2892 push_cast_ii(worklist, parent, use);
2893 push_opaque_zero_trip_guard(worklist, use);
2894 }
2895
2896
2897 // We must recheck Phis too if use is a Region.
2898 void PhaseCCP::push_phis(Unique_Node_List& worklist, const Node* use) const {
2899 if (use->is_Region()) {
2900 for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
2901 push_if_not_bottom_type(worklist, use->fast_out(i));
2902 }
2903 }
2904 }
2905
2906 // If we changed the receiver type to a call, we need to revisit the Catch node following the call. It's looking for a
2907 // non-null receiver to know when to enable the regular fall-through path in addition to the NullPtrException path.
2908 // Same is true if the type of a ValidLengthTest input to an AllocateArrayNode changes.
2909 void PhaseCCP::push_catch(Unique_Node_List& worklist, const Node* use) {
2929 for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
2930 Node* cmpu = use->fast_out(i);
2931 const uint cmpu_opcode = cmpu->Opcode();
2932 if (cmpu_opcode == Op_CmpU || cmpu_opcode == Op_CmpU3) {
2933 // Got a CmpU or CmpU3 which might need the new type information from node n.
2934 push_if_not_bottom_type(worklist, cmpu);
2935 }
2936 }
2937 }
2938 }
2939
2940 // 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'.
2941 // Seem PhiNode::Value().
2942 void PhaseCCP::push_counted_loop_phi(Unique_Node_List& worklist, Node* parent, const Node* use) {
2943 uint use_op = use->Opcode();
2944 if (use_op == Op_CmpI || use_op == Op_CmpL) {
2945 PhiNode* phi = countedloop_phi_from_cmp(use->as_Cmp(), parent);
2946 if (phi != nullptr) {
2947 worklist.push(phi);
2948 }
2949 }
2950 }
2951
2952 void PhaseCCP::push_cast(Unique_Node_List& worklist, const Node* use) {
2953 uint use_op = use->Opcode();
2954 if (use_op == Op_CastP2X) {
2955 for (DUIterator_Fast i2max, i2 = use->fast_outs(i2max); i2 < i2max; i2++) {
2956 Node* u = use->fast_out(i2);
2957 if (u->Opcode() == Op_AndX) {
2958 worklist.push(u);
2959 }
2960 }
2961 }
2962 }
2963
2964 // Loading the java mirror from a Klass requires two loads and the type of the mirror load depends on the type of 'n'.
2965 // See LoadNode::Value().
2966 void PhaseCCP::push_loadp(Unique_Node_List& worklist, const Node* use) const {
2967 BarrierSetC2* barrier_set = BarrierSet::barrier_set()->barrier_set_c2();
2968 bool has_load_barrier_nodes = barrier_set->has_load_barrier_nodes();
2969
2970 if (use->Opcode() == Op_LoadP && use->bottom_type()->isa_rawptr()) {
2971 for (DUIterator_Fast imax, i = use->fast_outs(imax); i < imax; i++) {
2972 Node* loadp = use->fast_out(i);
2973 const Type* ut = loadp->bottom_type();
2974 if (loadp->Opcode() == Op_LoadP && ut->isa_instptr() && ut != type(loadp)) {
2975 if (has_load_barrier_nodes) {
2976 // Search for load barriers behind the load
2977 push_load_barrier(worklist, barrier_set, loadp);
2978 }
2979 worklist.push(loadp);
2980 }
|