MatchNode::build_instr_pred

[Andrew Haley]

I'm sorry this mail is rather long.  Bottom line: there's a baffling
bug in adlc, and I'm seeking help understanding how it's supposed to
work.

I've come across a very odd problem when building the AArch64 back
end.  I defined a certain pattern, and the compiler segfaulted when
run.

The pattern was this

(Set dst (XorL src1 (OrL (URShiftL src2 shift1) (LShiftL src2 shift2))))

I think the bug which caused the segfault is in
MatchNode::build_instr_pred().  This is a very simple routine which is
passed a name; it walks a binary tree and returns the path to the Nth
occurrence of that name.  This is used for generating a matching
predicate for an operand used twice in a pattern.  I wouldn't expect
anything to go wrong, but it generates the wrong code for the above
pattern.

The sub-pattern I was trying to match was this:

  (XorI  (OrI  (URShiftI  src2 shift1) (LShiftI  src2 shift2)) src1)

For the two occurrences of "src2" in this pattern, build_instr_pred()
returns

 "_kids[0]->_kids[0]->_kids[0]->_leaf"

   and

 "_kids[1]->_kids[0]->_leaf"

but it should return

 "_kids[0]->_kids[0]->_kids[0]->_leaf"

   and

 "_kids[0]->_kids[1]->_kids[0]->_leaf"

which is why it segfaults.

Here is the source of build_instr_pred() :

//------------------------------build_instr_pred-------------------------------
// Build a path to 'name' in buf.  Actually only build if cnt is zero, so we
// can skip some leading instances of 'name'.
int MatchNode::build_instr_pred( char *buf, const char *name, int cnt ) {
  if( _lChild ) {
    if( !cnt )strcpy( buf, "_kids[0]->" );
    cnt = _lChild->build_instr_pred( buf+strlen(buf), name, cnt );
    if( cnt < 0 ) return cnt;   // Found it, all done
  }
  if( _rChild ) {
    if( !cnt ) strcpy( buf, "_kids[1]->" );
    cnt = _rChild->build_instr_pred( buf+strlen(buf), name, cnt );
    if( cnt < 0 ) return cnt;   // Found it, all done
  }
  if( !_lChild && !_rChild ) {  // Found a leaf
    // Wrong name?  Give up...
    if( strcmp(name,_name) ) return cnt;
    if( !cnt ) strcpy(buf,"_leaf");
    return cnt-1;
  }
  return cnt;
}

It seems to me that the use of "if( !cnt )" is simply wrong: for
simple patterns it has no effect, and where it does have an effect it
serves only to break things.  The comment "Actually only build if cnt
is zero, so we can skip some leading instances of 'name'" doesn't
really help me to understand what it was supposed to do.

I have tried the following patch, and it fixes my bug, and it doesn't
break x86.  However, I think this bug has been in C2 since the year
dot, so I'm rather surprised no-one has ever been affected, and I am
totally mystified: what is that "if( !cnt )" for?  It doesn't seem to
do anything useful, and I suspect it never has.

Finally, how should I report this as a bug?  It doesn't affect any
existing OpenJDK targets, as far as I know.

Thanks,
Andrew.


 // ============================================================================
 // Floating Point Arithmetic Instructions
diff -r 50f6ffa33a7c src/share/vm/adlc/formssel.cpp
--- a/src/share/vm/adlc/formssel.cpp    Fri Dec 12 06:32:18 2014 -0500
+++ b/src/share/vm/adlc/formssel.cpp    Mon Dec 15 10:30:49 2014 -0500
@@ -3407,12 +3407,12 @@
 // can skip some leading instances of 'name'.
 int MatchNode::build_instr_pred( char *buf, const char *name, int cnt ) {
   if( _lChild ) {
-    if( !cnt ) strcpy( buf, "_kids[0]->" );
+    strcpy( buf, "_kids[0]->" );
     cnt = _lChild->build_instr_pred( buf+strlen(buf), name, cnt );
     if( cnt < 0 ) return cnt;   // Found it, all done
   }
   if( _rChild ) {
-    if( !cnt ) strcpy( buf, "_kids[1]->" );
+    strcpy( buf, "_kids[1]->" );
     cnt = _rChild->build_instr_pred( buf+strlen(buf), name, cnt );
     if( cnt < 0 ) return cnt;   // Found it, all done
   }