< prev index next >

src/hotspot/share/opto/loopUnswitch.cpp

Print this page
*** 22,10 ***
--- 22,12 ---
   *
   */
  
  #include "precompiled.hpp"
  #include "memory/allocation.inline.hpp"
+ #include "opto/mulnode.hpp"
+ #include "opto/addnode.hpp"
  #include "opto/connode.hpp"
  #include "opto/convertnode.hpp"
  #include "opto/loopnode.hpp"
  #include "opto/opaquenode.hpp"
  #include "opto/rootnode.hpp"

*** 49,10 ***
--- 51,11 ---
  //                                 endloop
  //                               endif
  //
  // Note: the "else" clause may be empty
  
+ 
  //------------------------------policy_unswitching-----------------------------
  // Return TRUE or FALSE if the loop should be unswitched
  // (ie. clone loop with an invariant test that does not exit the loop)
  bool IdealLoopTree::policy_unswitching( PhaseIdealLoop *phase ) const {
    if (!LoopUnswitching) {

*** 72,21 ***
  
    LoopNode* head = _head->as_Loop();
    if (head->unswitch_count() + 1 > head->unswitch_max()) {
      return false;
    }
!   if (phase->find_unswitching_candidate(this) == NULL) {
      return false;
    }
  
    // Too speculative if running low on nodes.
    return phase->may_require_nodes(est_loop_clone_sz(2));
  }
  
  //------------------------------find_unswitching_candidate-----------------------------
  // Find candidate "if" for unswitching
! IfNode* PhaseIdealLoop::find_unswitching_candidate(const IdealLoopTree *loop) const {
  
    // Find first invariant test that doesn't exit the loop
    LoopNode *head = loop->_head->as_Loop();
    IfNode* unswitch_iff = NULL;
    Node* n = head->in(LoopNode::LoopBackControl);
--- 75,27 ---
  
    LoopNode* head = _head->as_Loop();
    if (head->unswitch_count() + 1 > head->unswitch_max()) {
      return false;
    }
! 
+   if (head->is_flattened_arrays()) {
+     return false;
+   }
+ 
+   Node_List unswitch_iffs;
+   if (phase->find_unswitching_candidate(this, unswitch_iffs) == NULL) {
      return false;
    }
  
    // Too speculative if running low on nodes.
    return phase->may_require_nodes(est_loop_clone_sz(2));
  }
  
  //------------------------------find_unswitching_candidate-----------------------------
  // Find candidate "if" for unswitching
! IfNode* PhaseIdealLoop::find_unswitching_candidate(const IdealLoopTree *loop, Node_List& unswitch_iffs) const {
  
    // Find first invariant test that doesn't exit the loop
    LoopNode *head = loop->_head->as_Loop();
    IfNode* unswitch_iff = NULL;
    Node* n = head->in(LoopNode::LoopBackControl);

*** 107,10 ***
--- 116,28 ---
          }
        }
      }
      n = n_dom;
    }
+   if (unswitch_iff != NULL) {
+     unswitch_iffs.push(unswitch_iff);
+   }
+ 
+   // Collect all non-flattened array checks for unswitching to create a fast loop
+   // without checks (only non-flattened array accesses) and a slow loop with checks.
+   if (unswitch_iff == NULL || unswitch_iff->is_flat_array_check(&_igvn)) {
+     for (uint i = 0; i < loop->_body.size(); i++) {
+       IfNode* n = loop->_body.at(i)->isa_If();
+       if (n != NULL && n != unswitch_iff && n->is_flat_array_check(&_igvn) &&
+           loop->is_invariant(n->in(1)) && !loop->is_loop_exit(n)) {
+         unswitch_iffs.push(n);
+         if (unswitch_iff == NULL) {
+           unswitch_iff = n;
+         }
+       }
+     }
+   }
    return unswitch_iff;
  }
  
  //------------------------------do_unswitching-----------------------------
  // Clone loop with an invariant test (that does not exit) and

*** 130,26 ***
        // to wrong execution. Remove this bailout, once this is fixed.
        return;
      }
    }
    // Find first invariant test that doesn't exit the loop
!   IfNode* unswitch_iff = find_unswitching_candidate((const IdealLoopTree *)loop);
!   assert(unswitch_iff != NULL, "should be at least one");
  
  #ifndef PRODUCT
    if (TraceLoopOpts) {
      tty->print("Unswitch   %d ", head->unswitch_count()+1);
      loop->dump_head();
    }
  #endif
  
    // Need to revert back to normal loop
    if (head->is_CountedLoop() && !head->as_CountedLoop()->is_normal_loop()) {
      head->as_CountedLoop()->set_normal_loop();
    }
  
!   IfNode* invar_iff = create_slow_version_of_loop(loop, old_new, unswitch_iff, CloneIncludesStripMined);
    ProjNode* proj_true = invar_iff->proj_out(1);
    ProjNode* proj_false = invar_iff->proj_out(0);
  
  #ifdef ASSERT
    assert(proj_true->is_IfTrue(), "must be true projection");
--- 157,32 ---
        // to wrong execution. Remove this bailout, once this is fixed.
        return;
      }
    }
    // Find first invariant test that doesn't exit the loop
!   Node_List unswitch_iffs;
!   IfNode* unswitch_iff = find_unswitching_candidate((const IdealLoopTree *)loop, unswitch_iffs);
+   assert(unswitch_iff != NULL && unswitch_iff == unswitch_iffs.at(0), "should be at least one");
+   bool flat_array_checks = unswitch_iffs.size() > 1;
  
  #ifndef PRODUCT
    if (TraceLoopOpts) {
      tty->print("Unswitch   %d ", head->unswitch_count()+1);
      loop->dump_head();
+     for (uint i = 0; i < unswitch_iffs.size(); i++) {
+       unswitch_iffs.at(i)->dump(3);
+       tty->cr();
+     }
    }
  #endif
  
    // Need to revert back to normal loop
    if (head->is_CountedLoop() && !head->as_CountedLoop()->is_normal_loop()) {
      head->as_CountedLoop()->set_normal_loop();
    }
  
!   IfNode* invar_iff = create_slow_version_of_loop(loop, old_new, unswitch_iffs, CloneIncludesStripMined);
    ProjNode* proj_true = invar_iff->proj_out(1);
    ProjNode* proj_false = invar_iff->proj_out(0);
  
  #ifdef ASSERT
    assert(proj_true->is_IfTrue(), "must be true projection");

*** 183,43 ***
    LoopNode* head_clone = old_new[head->_idx]->as_Loop();
    int nct = head->unswitch_count() + 1;
    head->set_unswitch_count(nct);
    head_clone->set_unswitch_count(nct);
  
!   // Hoist invariant casts out of each loop to the appropriate
-   // control projection.
- 
    Node_List worklist;
!   for (DUIterator_Fast imax, i = unswitch_iff->fast_outs(imax); i < imax; i++) {
!     ProjNode* proj= unswitch_iff->fast_out(i)->as_Proj();
!     // Copy to a worklist for easier manipulation
!     for (DUIterator_Fast jmax, j = proj->fast_outs(jmax); j < jmax; j++) {
!       Node* use = proj->fast_out(j);
!       if (use->Opcode() == Op_CheckCastPP && loop->is_invariant(use->in(1))) {
!         worklist.push(use);
        }
-     }
-     ProjNode* invar_proj = invar_iff->proj_out(proj->_con)->as_Proj();
-     while (worklist.size() > 0) {
-       Node* use = worklist.pop();
-       Node* nuse = use->clone();
-       nuse->set_req(0, invar_proj);
-       _igvn.replace_input_of(use, 1, nuse);
-       register_new_node(nuse, invar_proj);
-       // Same for the clone
-       Node* use_clone = old_new[use->_idx];
-       _igvn.replace_input_of(use_clone, 1, nuse);
      }
    }
  
    // Hardwire the control paths in the loops into if(true) and if(false)
!   _igvn.rehash_node_delayed(unswitch_iff);
!   dominated_by(proj_true, unswitch_iff, false, false);
! 
    IfNode* unswitch_iff_clone = old_new[unswitch_iff->_idx]->as_If();
!   _igvn.rehash_node_delayed(unswitch_iff_clone);
!   dominated_by(proj_false, unswitch_iff_clone, false, false);
  
    // Reoptimize loops
    loop->record_for_igvn();
    for(int i = loop->_body.size() - 1; i >= 0 ; i--) {
      Node *n = loop->_body[i];
--- 216,55 ---
    LoopNode* head_clone = old_new[head->_idx]->as_Loop();
    int nct = head->unswitch_count() + 1;
    head->set_unswitch_count(nct);
    head_clone->set_unswitch_count(nct);
  
!   // Hoist invariant casts out of each loop to the appropriate control projection.
    Node_List worklist;
!   for (uint i = 0; i < unswitch_iffs.size(); i++) {
!     IfNode* iff = unswitch_iffs.at(i)->as_If();
!     for (DUIterator_Fast imax, i = iff->fast_outs(imax); i < imax; i++) {
!       ProjNode* proj = iff->fast_out(i)->as_Proj();
!       // Copy to a worklist for easier manipulation
!       for (DUIterator_Fast jmax, j = proj->fast_outs(jmax); j < jmax; j++) {
!         Node* use = proj->fast_out(j);
+         if (use->Opcode() == Op_CheckCastPP && loop->is_invariant(use->in(1))) {
+           worklist.push(use);
+         }
+       }
+       ProjNode* invar_proj = invar_iff->proj_out(proj->_con)->as_Proj();
+       while (worklist.size() > 0) {
+         Node* use = worklist.pop();
+         Node* nuse = use->clone();
+         nuse->set_req(0, invar_proj);
+         _igvn.replace_input_of(use, 1, nuse);
+         register_new_node(nuse, invar_proj);
+         // Same for the clone if we are removing checks from the slow loop
+         if (!flat_array_checks) {
+           Node* use_clone = old_new[use->_idx];
+           _igvn.replace_input_of(use_clone, 1, nuse);
+         }
        }
      }
    }
  
    // Hardwire the control paths in the loops into if(true) and if(false)
!   for (uint i = 0; i < unswitch_iffs.size(); i++) {
!     IfNode* iff = unswitch_iffs.at(i)->as_If();
!     _igvn.rehash_node_delayed(iff);
+     dominated_by(proj_true, iff);
+   }
    IfNode* unswitch_iff_clone = old_new[unswitch_iff->_idx]->as_If();
!   if (!flat_array_checks) {
!     ProjNode* proj_false = invar_iff->proj_out(0)->as_Proj();
+     _igvn.rehash_node_delayed(unswitch_iff_clone);
+     dominated_by(proj_false, unswitch_iff_clone);
+   } else {
+     // Leave the flattened array checks in the slow loop and
+     // prevent it from being unswitched again based on these checks.
+     head_clone->mark_flattened_arrays();
+   }
  
    // Reoptimize loops
    loop->record_for_igvn();
    for(int i = loop->_body.size() - 1; i >= 0 ; i--) {
      Node *n = loop->_body[i];

*** 227,13 ***
      _igvn._worklist.push(n_clone);
    }
  
  #ifndef PRODUCT
    if (TraceLoopUnswitching) {
!     tty->print_cr("Loop unswitching orig: %d @ %d  new: %d @ %d",
!                   head->_idx,                unswitch_iff->_idx,
!                   old_new[head->_idx]->_idx, unswitch_iff_clone->_idx);
    }
  #endif
  
    C->set_major_progress();
  }
--- 272,15 ---
      _igvn._worklist.push(n_clone);
    }
  
  #ifndef PRODUCT
    if (TraceLoopUnswitching) {
!     for (uint i = 0; i < unswitch_iffs.size(); i++) {
!       tty->print_cr("Loop unswitching orig: %d @ %d  new: %d @ %d",
!                     head->_idx,                unswitch_iffs.at(i)->_idx,
+                     old_new[head->_idx]->_idx, old_new[unswitch_iffs.at(i)->_idx]->_idx);
+     }
    }
  #endif
  
    C->set_major_progress();
  }

*** 241,24 ***
  //-------------------------create_slow_version_of_loop------------------------
  // Create a slow version of the loop by cloning the loop
  // and inserting an if to select fast-slow versions.
  // Return the inserted if.
  IfNode* PhaseIdealLoop::create_slow_version_of_loop(IdealLoopTree *loop,
!                                                       Node_List &old_new,
!                                                       IfNode* unswitch_iff,
!                                                       CloneLoopMode mode) {
    LoopNode* head  = loop->_head->as_Loop();
    Node*     entry = head->skip_strip_mined()->in(LoopNode::EntryControl);
    _igvn.rehash_node_delayed(entry);
    IdealLoopTree* outer_loop = loop->_parent;
  
    head->verify_strip_mined(1);
  
    // Add test to new "if" outside of loop
!   Node *bol   = unswitch_iff->in(1)->as_Bool();
    IfNode* iff = (unswitch_iff->Opcode() == Op_RangeCheck) ? new RangeCheckNode(entry, bol, unswitch_iff->_prob, unswitch_iff->_fcnt) :
!     new IfNode(entry, bol, unswitch_iff->_prob, unswitch_iff->_fcnt);
    register_node(iff, outer_loop, entry, dom_depth(entry));
    ProjNode* iffast = new IfTrueNode(iff);
    register_node(iffast, outer_loop, iff, dom_depth(iff));
    ProjNode* ifslow = new IfFalseNode(iff);
    register_node(ifslow, outer_loop, iff, dom_depth(iff));
--- 288,50 ---
  //-------------------------create_slow_version_of_loop------------------------
  // Create a slow version of the loop by cloning the loop
  // and inserting an if to select fast-slow versions.
  // Return the inserted if.
  IfNode* PhaseIdealLoop::create_slow_version_of_loop(IdealLoopTree *loop,
!                                                     Node_List &old_new,
!                                                     Node_List &unswitch_iffs,
!                                                     CloneLoopMode mode) {
    LoopNode* head  = loop->_head->as_Loop();
+   bool counted_loop = head->is_CountedLoop();
    Node*     entry = head->skip_strip_mined()->in(LoopNode::EntryControl);
    _igvn.rehash_node_delayed(entry);
    IdealLoopTree* outer_loop = loop->_parent;
  
    head->verify_strip_mined(1);
  
    // Add test to new "if" outside of loop
!   IfNode* unswitch_iff = unswitch_iffs.at(0)->as_If();
+   BoolNode* bol = unswitch_iff->in(1)->as_Bool();
+   if (unswitch_iffs.size() > 1) {
+     // Flattened array checks are used on array access to switch between
+     // a legacy object array access and a flattened inline type array
+     // access. We want the performance impact on legacy accesses to be
+     // as small as possible so we make two copies of the loop: a fast
+     // one where all accesses are known to be legacy, a slow one where
+     // some accesses are to flattened arrays. Flattened array checks
+     // can be removed from the fast loop (true proj) but not from the
+     // slow loop (false proj) as it can have a mix of flattened/legacy accesses.
+     assert(bol->_test._test == BoolTest::ne, "IfTrue proj must point to flat array");
+     bol = bol->clone()->as_Bool();
+     register_new_node(bol, entry);
+     FlatArrayCheckNode* cmp = bol->in(1)->clone()->as_FlatArrayCheck();
+     register_new_node(cmp, entry);
+     bol->set_req(1, cmp);
+     // Combine all checks into a single one that fails if one array is flattened
+     assert(cmp->req() == 3, "unexpected number of inputs for FlatArrayCheck");
+     cmp->add_req_batch(C->top(), unswitch_iffs.size() - 1);
+     for (uint i = 0; i < unswitch_iffs.size(); i++) {
+       Node* array = unswitch_iffs.at(i)->in(1)->in(1)->in(FlatArrayCheckNode::Array);
+       cmp->set_req(FlatArrayCheckNode::Array + i, array);
+     }
+   }
+ 
    IfNode* iff = (unswitch_iff->Opcode() == Op_RangeCheck) ? new RangeCheckNode(entry, bol, unswitch_iff->_prob, unswitch_iff->_fcnt) :
!       new IfNode(entry, bol, unswitch_iff->_prob, unswitch_iff->_fcnt);
    register_node(iff, outer_loop, entry, dom_depth(entry));
    ProjNode* iffast = new IfTrueNode(iff);
    register_node(iffast, outer_loop, iff, dom_depth(iff));
    ProjNode* ifslow = new IfFalseNode(iff);
    register_node(ifslow, outer_loop, iff, dom_depth(iff));

*** 287,10 ***
--- 360,11 ---
  }
  
  LoopNode* PhaseIdealLoop::create_reserve_version_of_loop(IdealLoopTree *loop, CountedLoopReserveKit* lk) {
    Node_List old_new;
    LoopNode* head  = loop->_head->as_Loop();
+   bool counted_loop = head->is_CountedLoop();
    Node*     entry = head->skip_strip_mined()->in(LoopNode::EntryControl);
    _igvn.rehash_node_delayed(entry);
    IdealLoopTree* outer_loop = head->is_strip_mined() ? loop->_parent->_parent : loop->_parent;
  
    ConINode* const_1 = _igvn.intcon(1);
< prev index next >