src/share/vm/opto/loopnode.cpp

rev 10221 : 8149745: C2 should optimize long accumulations in a counted loop
summary: Look for parallel iv for long adds
Reviewed-by:

*** 1741,1792 ****
  //---------------------------replace_parallel_iv-------------------------------
  // Replace parallel induction variable (parallel to trip counter)
  void PhaseIdealLoop::replace_parallel_iv(IdealLoopTree *loop) {
    assert(loop->_head->is_CountedLoop(), "");
    CountedLoopNode *cl = loop->_head->as_CountedLoop();
!   if (!cl->is_valid_counted_loop())
      return;         // skip malformed counted loop
    Node *incr = cl->incr();
!   if (incr == NULL)
      return;         // Dead loop?
    Node *init = cl->init_trip();
    Node *phi  = cl->phi();
    int stride_con = cl->stride_con();
  
    // Visit all children, looking for Phis
    for (DUIterator i = cl->outs(); cl->has_out(i); i++) {
      Node *out = cl->out(i);
      // Look for other phis (secondary IVs). Skip dead ones
!     if (!out->is_Phi() || out == phi || !has_node(out))
        continue;
      PhiNode* phi2 = out->as_Phi();
!     Node *incr2 = phi2->in( LoopNode::LoopBackControl );
      // Look for induction variables of the form:  X += constant
      if (phi2->region() != loop->_head ||
          incr2->req() != 3 ||
          incr2->in(1) != phi2 ||
          incr2 == incr ||
!         incr2->Opcode() != Op_AddI ||
!         !incr2->in(2)->is_Con())
        continue;
  
      // Check for parallel induction variable (parallel to trip counter)
      // via an affine function.  In particular, count-down loops with
      // count-up array indices are common. We only RCE references off
      // the trip-counter, so we need to convert all these to trip-counter
      // expressions.
!     Node *init2 = phi2->in( LoopNode::EntryControl );
!     int stride_con2 = incr2->in(2)->get_int();
  
      // The general case here gets a little tricky.  We want to find the
      // GCD of all possible parallel IV's and make a new IV using this
      // GCD for the loop.  Then all possible IVs are simple multiples of
      // the GCD.  In practice, this will cover very few extra loops.
      // Instead we require 'stride_con2' to be a multiple of 'stride_con',
      // where +/-1 is the common case, but other integer multiples are
      // also easy to handle.
!     int ratio_con = stride_con2/stride_con;
  
      if ((ratio_con * stride_con) == stride_con2) { // Check for exact
  #ifndef PRODUCT
        if (TraceLoopOpts) {
          tty->print("Parallel IV: %d ", phi2->_idx);
--- 1741,1798 ----
  //---------------------------replace_parallel_iv-------------------------------
  // Replace parallel induction variable (parallel to trip counter)
  void PhaseIdealLoop::replace_parallel_iv(IdealLoopTree *loop) {
    assert(loop->_head->is_CountedLoop(), "");
    CountedLoopNode *cl = loop->_head->as_CountedLoop();
!   if (!cl->is_valid_counted_loop()) {
      return;         // skip malformed counted loop
+   }
    Node *incr = cl->incr();
!   if (incr == NULL) {
      return;         // Dead loop?
+   }
    Node *init = cl->init_trip();
    Node *phi  = cl->phi();
    int stride_con = cl->stride_con();
  
    // Visit all children, looking for Phis
    for (DUIterator i = cl->outs(); cl->has_out(i); i++) {
      Node *out = cl->out(i);
      // Look for other phis (secondary IVs). Skip dead ones
!     if (!out->is_Phi() || out == phi || !has_node(out)) {
        continue;
+     }
      PhiNode* phi2 = out->as_Phi();
!     Node *incr2 = phi2->in(LoopNode::LoopBackControl);
      // Look for induction variables of the form:  X += constant
      if (phi2->region() != loop->_head ||
          incr2->req() != 3 ||
          incr2->in(1) != phi2 ||
          incr2 == incr ||
!         (incr2->Opcode() != Op_AddI && incr2->Opcode() != Op_AddL) ||
!         !incr2->in(2)->is_Con()) {
        continue;
+     }
+     BasicType bt = incr2->Opcode() == Op_AddI ? T_INT : T_LONG;
  
      // Check for parallel induction variable (parallel to trip counter)
      // via an affine function.  In particular, count-down loops with
      // count-up array indices are common. We only RCE references off
      // the trip-counter, so we need to convert all these to trip-counter
      // expressions.
!     Node *init2 = phi2->in(LoopNode::EntryControl);
!     Node* stride2 = incr2->in(2);
!     jlong stride_con2 = (bt == T_INT) ? stride2->get_int() : stride2->get_long();
  
      // The general case here gets a little tricky.  We want to find the
      // GCD of all possible parallel IV's and make a new IV using this
      // GCD for the loop.  Then all possible IVs are simple multiples of
      // the GCD.  In practice, this will cover very few extra loops.
      // Instead we require 'stride_con2' to be a multiple of 'stride_con',
      // where +/-1 is the common case, but other integer multiples are
      // also easy to handle.
!     jlong ratio_con = stride_con2/stride_con;
  
      if ((ratio_con * stride_con) == stride_con2) { // Check for exact
  #ifndef PRODUCT
        if (TraceLoopOpts) {
          tty->print("Parallel IV: %d ", phi2->_idx);
*** 1795,1819 ****
  #endif
        // Convert to using the trip counter.  The parallel induction
        // variable differs from the trip counter by a loop-invariant
        // amount, the difference between their respective initial values.
        // It is scaled by the 'ratio_con'.
!       Node* ratio = _igvn.intcon(ratio_con);
        set_ctrl(ratio, C->root());
!       Node* ratio_init = new MulINode(init, ratio);
!       _igvn.register_new_node_with_optimizer(ratio_init, init);
        set_early_ctrl(ratio_init);
!       Node* diff = new SubINode(init2, ratio_init);
        _igvn.register_new_node_with_optimizer(diff, init2);
        set_early_ctrl(diff);
!       Node* ratio_idx = new MulINode(phi, ratio);
!       _igvn.register_new_node_with_optimizer(ratio_idx, phi);
        set_ctrl(ratio_idx, cl);
!       Node* add = new AddINode(ratio_idx, diff);
        _igvn.register_new_node_with_optimizer(add);
        set_ctrl(add, cl);
!       _igvn.replace_node( phi2, add );
        // Sometimes an induction variable is unused
        if (add->outcnt() == 0) {
          _igvn.remove_dead_node(add);
        }
        --i; // deleted this phi; rescan starting with next position
--- 1801,1837 ----
  #endif
        // Convert to using the trip counter.  The parallel induction
        // variable differs from the trip counter by a loop-invariant
        // amount, the difference between their respective initial values.
        // It is scaled by the 'ratio_con'.
!       Node* ratio = (bt == T_INT) ? (Node*)_igvn.intcon((int)ratio_con) : (Node*)_igvn.longcon(ratio_con);
        set_ctrl(ratio, C->root());
!       Node* conv_init = init;
!       if (bt == T_LONG) {
!         conv_init = new ConvI2LNode(init);
!         _igvn.register_new_node_with_optimizer(conv_init, init);
!         set_early_ctrl(conv_init);
!       }
!       Node* ratio_init = MulNode::make(bt, conv_init, ratio);
!       _igvn.register_new_node_with_optimizer(ratio_init, conv_init);
        set_early_ctrl(ratio_init);
!       Node* diff = SubNode::make(bt, init2, ratio_init);
        _igvn.register_new_node_with_optimizer(diff, init2);
        set_early_ctrl(diff);
!       Node* conv_phi = phi;
!       if (bt == T_LONG) {
!         conv_phi = new ConvI2LNode(phi);
!         _igvn.register_new_node_with_optimizer(conv_phi, phi);
!         set_ctrl(conv_phi, cl);
!       }      
!       Node* ratio_idx = MulINode::make(bt, conv_phi, ratio);
!       _igvn.register_new_node_with_optimizer(ratio_idx, conv_phi);
        set_ctrl(ratio_idx, cl);
!       Node* add = AddNode::make(bt, ratio_idx, diff);
        _igvn.register_new_node_with_optimizer(add);
        set_ctrl(add, cl);
!       _igvn.replace_node(phi2, add);
        // Sometimes an induction variable is unused
        if (add->outcnt() == 0) {
          _igvn.remove_dead_node(add);
        }
        --i; // deleted this phi; rescan starting with next position