*** old/src/share/vm/opto/loopopts.cpp	Wed Jun 10 16:45:38 2015
--- new/src/share/vm/opto/loopopts.cpp	Wed Jun 10 16:45:37 2015

*** 651,660 ****
--- 651,861 ----
    _igvn._worklist.push(region);
  
    return iff->in(1);
  }
  
+ #ifdef ASSERT
+ static void enqueue_cfg_uses(Node* m, Unique_Node_List& wq) {
+   for (DUIterator_Fast imax, i = m->fast_outs(imax); i < imax; i++) {
+     Node* u = m->fast_out(i);
+     if (u->is_CFG()) {
+       if (u->Opcode() == Op_NeverBranch) {
+         u = ((NeverBranchNode*)u)->proj_out(0);
+         enqueue_cfg_uses(u, wq);
+       } else {
+         wq.push(u);
+       }
+     }
+   }
+ }
+ #endif
+ 
+ // Try moving a store out of a loop, right before the loop
+ Node* PhaseIdealLoop::try_move_store_before_loop(Node* n, Node *n_ctrl) {
+   // Store has to be first in the loop body
+   IdealLoopTree *n_loop = get_loop(n_ctrl);
+   if (n->is_Store() && n_loop != _ltree_root && !n_loop->_irreducible) {
+     Node* address = n->in(MemNode::Address);
+     Node* value = n->in(MemNode::ValueIn);
+     Node* mem = n->in(MemNode::Memory);
+     IdealLoopTree* address_loop = get_loop(get_ctrl(address));
+     IdealLoopTree* value_loop = get_loop(get_ctrl(value));
+ 
+     // - address and value must be loop invariant
+     // - memory must be a memory Phi for the loop
+     // - Store must be the only store on this memory slice in the
+     // loop: if there's another store following this one then value
+     // written at iteration i by the second store could be overwritten
+     // at iteration i+n by the first store: it's not safe to move the
+     // first store out of the loop
+     // - nothing must observe the Phi memory: it guarantees no read
+     // before the store and no early exit out of the loop
+     // With those conditions, we are also guaranteed the store post
+     // dominates the loop head. Otherwise there would be extra Phi
+     // involved between the loop's Phi and the store.
+ 
+     if (!n_loop->is_member(address_loop) &&
+         !n_loop->is_member(value_loop) &&
+         mem->is_Phi() && mem->in(0) == n_loop->_head &&
+         mem->outcnt() == 1 &&
+         mem->in(LoopNode::LoopBackControl) == n) {
+ 
+ #ifdef ASSERT
+       // Check that store's control does post dominate loop entry
+       bool ctrl_ok = false;
+       {
+         // Follow control from loop head until n or we exit the loop
+         ResourceMark rm;
+         Unique_Node_List wq;
+         wq.push(n_loop->_head);
+         for (uint next = 0; next < wq.size(); ++next) {
+           Node *m = wq.at(next);
+           if (m == n->in(0)) {
+             ctrl_ok = true;
+             continue;
+           }
+           assert(!has_ctrl(m), "should be CFG");
+           if (!n_loop->is_member(get_loop(m))) {
+             ctrl_ok = false;
+             break;
+           }
+           enqueue_cfg_uses(m, wq);
+         }
+       }
+       assert(ctrl_ok, "bad control");
+ #endif
+           
+       // move the Store
+       _igvn.replace_input_of(mem, LoopNode::LoopBackControl, mem);
+       _igvn.replace_input_of(n, 0, n_loop->_head->in(LoopNode::EntryControl));
+       _igvn.replace_input_of(n, MemNode::Memory, mem->in(LoopNode::EntryControl));
+       // Disconnect the phi now. An empty phi can confuse other
+       // optimizations in this pass of loop opts.
+       _igvn.replace_node(mem, mem->in(LoopNode::EntryControl));
+       n_loop->_body.yank(mem);
+       
+       IdealLoopTree* new_loop = get_loop(n->in(0));
+       set_ctrl_and_loop(n, n->in(0));
+         
+       return n;
+     }
+   }
+   return NULL;
+ }
+ 
+ // Try moving a store out of a loop, right after the loop
+ void PhaseIdealLoop::try_move_store_after_loop(Node* n) {
+   if (n->is_Store()) {
+     assert(n->in(0), "store should have control set");
+     Node *n_ctrl = get_ctrl(n);
+     IdealLoopTree *n_loop = get_loop(n_ctrl);
+     // Store must be in a loop
+     if (n_loop != _ltree_root && !n_loop->_irreducible) {
+       Node* address = n->in(MemNode::Address);
+       Node* value = n->in(MemNode::ValueIn);
+       IdealLoopTree* address_loop = get_loop(get_ctrl(address));
+       // address must be loop invariant
+       if (!n_loop->is_member(address_loop)) {
+         assert(n_loop != address_loop, "address is loop varying");
+         // Store must be last on this memory slice in the loop and
+         // nothing in the loop must observe it
+         Node* phi = NULL;
+         for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
+           Node* u = n->fast_out(i);
+           if (has_ctrl(u)) { // control use?
+             IdealLoopTree *u_loop = get_loop(get_ctrl(u));
+             if (!n_loop->is_member(u_loop)) {
+               continue;
+             }
+             if (u->is_Phi() && u->in(0) == n_loop->_head) {
+               assert(_igvn.type(u) == Type::MEMORY, "bad phi");
+               assert(phi == NULL, "already found");
+               phi = u;
+               continue;
+             }
+           }
+           phi = NULL;
+           break;
+         }
+         if (phi != NULL) {
+           // Nothing in the loop before the store (next iteration)
+           // must observe the stored value
+           bool mem_ok = true;
+           {
+             ResourceMark rm;
+             Unique_Node_List wq;
+             wq.push(phi);
+             for (uint next = 0; next < wq.size() && mem_ok; ++next) {
+               Node *m = wq.at(next);
+               for (DUIterator_Fast imax, i = m->fast_outs(imax); i < imax && mem_ok; i++) {
+                 Node* u = m->fast_out(i);
+                 if (u->is_Store() || u->is_Phi()) {
+                   if (u != n) {
+                     wq.push(u);
+                     mem_ok = (wq.size() <= 10);
+                   }
+                 } else {
+                   mem_ok = false;
+                   break;
+                 }
+               }
+             }
+           }
+           if (mem_ok) {
+             // Move the Store out of the loop creating clones along
+             // all paths out of the loop that observe the stored value
+             _igvn.rehash_node_delayed(phi);
+             int count = phi->replace_edge(n, n->in(MemNode::Memory));
+             assert(count > 0, "inconsistent phi");
+             for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) {
+               Node* u = n->fast_out(i);
+               Node* c = get_ctrl(u);
+ 
+               if (u->is_Phi()) {
+                 c = u->in(0)->in(u->find_edge(n));
+               }
+               IdealLoopTree *u_loop = get_loop(c);
+               assert (!n_loop->is_member(u_loop), "only the phi should have been a use in the loop");
+               while(true) {
+                 Node* next_c = find_non_split_ctrl(idom(c));
+                 if (n_loop->is_member(get_loop(next_c))) {
+                   break;
+                 }
+                 c = next_c;
+               }
+ 
+               Node* st = n->clone();
+               st->set_req(0, c);
+               _igvn.register_new_node_with_optimizer(st);
+               
+               set_ctrl(st, c);
+               IdealLoopTree* new_loop = get_loop(c);
+               assert(new_loop->_child != NULL, "");
+               assert(new_loop != n_loop, "should be moved out of loop");
+               if (new_loop->_child == NULL) new_loop->_body.push(st);
+ 
+               _igvn.replace_input_of(u, u->find_edge(n), st);
+               --imax;
+               --i;
+             }
+ 
+ 
+             assert(n->outcnt() == 0, "all uses should be gone");
+             _igvn.replace_input_of(n, MemNode::Memory, C->top());
+             // Disconnect the phi now. An empty phi can confuse other
+             // optimizations in this pass of loop opts..
+             if (phi->in(LoopNode::LoopBackControl) == phi) {
+               _igvn.replace_node(phi, phi->in(LoopNode::EntryControl));
+               n_loop->_body.yank(phi);
+             }
+           }
+         }
+       }
+     }
+   }
+ }
+ 
  //------------------------------split_if_with_blocks_pre-----------------------
  // Do the real work in a non-recursive function.  Data nodes want to be
  // cloned in the pre-order so they can feed each other nicely.
  Node *PhaseIdealLoop::split_if_with_blocks_pre( Node *n ) {
    // Cloning these guys is unlikely to win

*** 681,709 ****
--- 882,917 ----
    if( n->is_Con() ) return n;   // No cloning for Con nodes
  
    Node *n_ctrl = get_ctrl(n);
    if( !n_ctrl ) return n;       // Dead node
  
+   Node* res = try_move_store_before_loop(n, n_ctrl);
+   if (res != NULL) {
+     return n;
+   }
+ 
    // Attempt to remix address expressions for loop invariants
    Node *m = remix_address_expressions( n );
    if( m ) return m;
  
    // Determine if the Node has inputs from some local Phi.
    // Returns the block to clone thru.
    Node *n_blk = has_local_phi_input( n );
    if( !n_blk ) return n;
+ 
    // Do not clone the trip counter through on a CountedLoop
    // (messes up the canonical shape).
    if( n_blk->is_CountedLoop() && n->Opcode() == Op_AddI ) return n;
  
    // Check for having no control input; not pinned.  Allow
    // dominating control.
!   if( n->in(0) ) {
!   if (n->in(0)) {
      Node *dom = idom(n_blk);
!     if( dom_lca( n->in(0), dom ) != n->in(0) )
!     if (dom_lca(n->in(0), dom) != n->in(0)) {
        return n;
      }
+   }
    // Policy: when is it profitable.  You must get more wins than
    // policy before it is considered profitable.  Policy is usually 0,
    // so 1 win is considered profitable.  Big merges will require big
    // cloning, so get a larger policy.
    int policy = n_blk->req() >> 2;

*** 1027,1036 ****
--- 1235,1246 ----
          }
        }
      }
    }
  
+   try_move_store_after_loop(n);
+ 
    // Check for Opaque2's who's loop has disappeared - who's input is in the
    // same loop nest as their output.  Remove 'em, they are no longer useful.
    if( n_op == Op_Opaque2 &&
        n->in(1) != NULL &&
        get_loop(get_ctrl(n)) == get_loop(get_ctrl(n->in(1))) ) {