United StatesChange Country, Oracle Worldwide Web Sites Communities I am a... I want to...
Bug ID: JDK-6321689 Ideal_DU_postCCP not conservative enough
JDK-6321689 : Ideal_DU_postCCP not conservative enough

Details
Type:
Bug
Submit Date:
2005-09-08
Status:
Resolved
Updated Date:
2010-05-10
Project Name:
JDK
Resolved Date:
2005-10-13
Component:
hotspot
OS:
solaris_9,generic,windows_2000
Sub-Component:
compiler
CPU:
x86,sparc
Priority:
P3
Resolution:
Fixed
Affected Versions:
1.4.2_15,5.0u8,6
Fixed Versions:

Related Reports
Backport:
Backport:
Backport:
Backport:
Duplicate:
Duplicate:

Sub Tasks

Description
Cliff Click of Azul Systems reports:

Hi!  Long time no bug report - so I thought you might need one.  :-)
This one happens with "java_g -server -Xmx512m -Xms512m -Xbatch 
-XX:+PrintCompilation -XX:CompileOnly=foo.insert foo" and the included 
foo.java, on 1.4.2_03 SparcV9 for sure (and +PrintOptoAssembly shows a 
load scheduled before the null-check).  I get funny OOM errors with the 
product versions of later X86 & Sparc things; not sure if it's the same 
crash.


Cliff

------------------------------------------------------------------------
 From my putback msg:

The Ideal_DU_postCCP function removes CastPP's and replaces them with 
control edges on memory ops.  In order to give some scheduling freedom, 
it tries to find a least restrictive control input that is also 
sufficient to prevent hoisting above any needed null-check.  In the case 
of CountedLoops, it is willing to use a pre-loop control input.  This is 
not always correct: if the base value is known not-null but is a merge 
at the loop head - at is null-checked on entry AND at the loop bottom - 
then the old code would allow the control edge to move up to the 
null-check on entry.  The memory op could not float up out of the loop 
because the base value merges at the loop head.

If we later unrolled the loop, the cloned memory op would then take 
control from before the loop (like the original now does) and its base 
input from the unrolled prior loop body - which has no merging phi and 
whose CastPP was removed before unrolling.  Hence the cloned memory op 
could float above a needed null test. 

Fix is to not lift the control above a CountedLoop, unless the base 
value does not merge at the loop head (and is available already 
null-checked before loop).

Test case:

class foo  {
  public static void main(String argv[]) {
    System.out.println("Warmup");
    foo F = new foo();
    char [] C = new char[100];
    for( int i=0; i<100000; i++ ) {
      String s = Integer.toString(i);
      s.getChars(0,s.length(),C,0);
      F.insert(C);
    }
    System.out.println("Done ");
  }

  private final Node ROOT = new Node();
  private static class Node {
    final Node _next[] = new Node[128];
  }

  public Node insert(char [] C) {
    int len = C.length;
    Node node = ROOT;
    int j = 0;

    for(; j < len; j++) {
      Node node1 = node._next[C[j]];
      if( node1 == null ) break;
      node = node1;  
    }

    for(; j < len; j++) {
      Node node2 = new Node();
      node._next[C[j]] = node2;
      node = node2;
    }

    return node;
  }
}

                                    

Comments
SUGGESTED FIX

Cliff Click suggests:

 //---------------------------cast_is_loop_invariant----------------------------
 // A helper function for Ideal_DU_postCCP to check if a CastPP in a 
counted
-// loop is loop invariant. Make a quick traversal of Phi and CastPP nodes
+// loop is loop invariant.  Make a quick traversal of Phi and CastPP nodes
 // looking to see if they are a closed group within the loop.
 static bool cast_is_loop_invariant(Node* cast, Node* adr) {
-  // The idea is that the phi-nest must boil down to only CastPP nodes
-  // with the same data input as the original cast. This implies that 
any path
-  // into the loop already includes such a CastPP, and so the original 
cast,
-  // whatever its input, must be covered by an equivalent cast, with an 
earlier
-  // control input.
+  // The idea is that the phi-nest must boil down to only CastPP nodes with
+  // the same data.  This implies that any path into the loop already 
includes
+  // such a CastPP and so the original cast, whatever its input, must be
+  // covered by an equivalent cast with an earlier control input.
   ResourceMark rm;
   Unique_Node_List closure;
-  closure.push(cast);
-  closure.push(adr);
- 
   Unique_Node_List worklist;
-  worklist.push(adr->in(LoopNode::LoopBackControl));
+  worklist.push(adr);
+  if( cast ) worklist.push(cast);
 
-  int op = cast->Opcode();
-  Node* input = cast->in(1);
+  Node *unique = NULL;          // Do not know the original data
 
   // Begin recursive walk of phi nodes.
   while( worklist.size() ){
@@ -279,19 +275,18 @@
       // Make a sanity check to ensure we don't waste too much time here.
       if( closure.size() > 10) return false;
       // This node is OK if:
-      //  - it is a cast identical (based on opcode and input) to the 
original one
+      //  - it is a cast of an identical value
       //  - or it is a phi node (then we add its inputs to the worklist)
       // Otherwise, the node is not OK, and we presume the cast is not 
invariant
-      if( n->Opcode() == op ) {
-    if( n->in(1) != input ){
-      return false;
-    }
+      if( n->Opcode() == Op_CastPP ) {
+        worklist.push(n->in(1)); // Check input
       } else if( n->Opcode() == Op_Phi ) {
-    for( uint i = 1; i < n->req(); i++ ) {
-      worklist.push(n->in(i));
-    }
-      } else {
-        return false;
+        for( uint i = 1; i < n->req(); i++ )
+          worklist.push(n->in(i)); // Check all inputs
+      } else if( !unique ) {    // Unique input not discovered yet?
+        unique = n;             // Record unique input
+      } else if( unique != n ) {// Must be equal to unique
+        return false;           // Merge of unequals
       }
     }
   }
@@ -317,7 +312,7 @@
   Node *ctr = in(MemNode::Control);
   Node *mem = in(MemNode::Memory);
   Node *adr = in(MemNode::Address);
-  Node *elided_cast = NULL;
+  Node *skipped_cast = NULL;
   // Need a null check?  Regular static accesses do not because they are
   // from constant addresses.  Array ops are gated by the range check 
(which
   // always includes a NULL check).  Just check field ops.
@@ -326,82 +321,84 @@
       case Op_Phi:
         // Attempt to float above a Phi to some dominating point.
         if( adr->in(0)->is_CountedLoop() ) {
+          // If we've already peeked through a Cast (which could have 
set the
+          // control), we can't float above a Phi, because the skipped Cast
+          // may not be loop invariant.
+          if( cast_is_loop_invariant(skipped_cast, adr)) {
+            adr = adr->in(1);
+            continue;
+          }
+        }
-      // If we've already peeked through a CastPP (which could have set the
-      // control), we can't float above a Phi, because the ignored CastPP
-      // may not be loop invariant.
-      if( elided_cast == NULL ||
-              cast_is_loop_invariant(elided_cast, adr)) {
-        adr = adr->in(1);
-        continue;
-      }
-    }
+        // Intentional fallthrough!
                                     
2005-09-08
EVALUATION

Customer's evaluation is correct.
                                     
2005-09-08
SUGGESTED FIX

Cliff's suggested fix is too restrictive.  It fails to find invariant some cases in which are currently correctly found so.  First, instead of looking for a "unique" node,
we should just push adr->in(LoopNode::EntryControl) onto closure. The remaining logic regarding "unique" goes away. Second, because we are now pushing all of the CastPP nodes onto the closure list, we need to expand the sanity check, probably 2x.
                                     
2005-09-21
SUGGESTED FIX

See PRT webrev for final fix:

http://analemma.sfbay.sun.com/net/prt-archiver.sfbay/data/archived_workspaces/main/c2_baseline/2005/20050929074806.rasbold.c2_baseline/workspace/webrevs/webrev-2005.09.29/index.html
                                     
2005-09-30



Hardware and Software, Engineered to Work Together