[LLVMdev] Tablegen: RegisterInfoEmitter.cpp

[Jonas Paulsson]

Hi,

I understand the idea behind compare_numeric() is to compare strings containing digits in a special way: Do a normal string-compare up to the point where both string elemnts are numerical. Find then an outcome based on the number of consecutive digits in the strings while disregarding the value of the digits, eg a12b < a123.

I guess then this order should hold: a12 == a22 < a1b, for these strings.

Looking at StringRef::compare_numeric(StringRef RHS), the problem is, for a12 and a1b, Data[1]==RHS.Data[1], and the continue is reached.  Data[2] is then less than RHS.Data[2], so a12 < a1b. But in the case for a22 and a1b, we get the opposite, since '2'!='1', and 22 is more digits than 1. So we get a12 < a1b < a22, which is incorrect, because a12==a22.

My problem was with these registers: a23g, a2g and a3g. When I renamed a23g to aa23g, it worked. Since '2'=='2', the problem was that a23g<a2g.

I think the fix is to first check for two digits, and move the equality comparison to after this. Then a2g < a3g < a23g:

/// compare_numeric - Compare strings, handle embedded numbers.
int StringRef::compare_numeric(StringRef RHS) const {
  for (size_t I = 0, E = min(Length, RHS.Length); I != E; ++I) {
    if (ascii_isdigit(Data[I]) && ascii_isdigit(RHS.Data[I])) {
      // The longer sequence of numbers is larger. This doesn't really handle
      // prefixed zeros well.
      for (size_t J = I+1; J != E+1; ++J) {
        bool ld = J < Length && ascii_isdigit(Data[J]);
        bool rd = J < RHS.Length && ascii_isdigit(RHS.Data[J]);
        if (ld != rd)
          return rd ? -1 : 1;
        if (!rd)
          break;
      }
    }
    if (Data[I] == RHS.Data[I])
      continue;
    return (unsigned char)Data[I] < (unsigned char)RHS.Data[I] ? -1 : 1;
  }
  if (Length == RHS.Length)
    return 0;
  return Length < RHS.Length ? -1 : 1;
}

patch (2.9):
/lib/Support/StringRef.cpp:
48a49,50
>     if (Data[I] == RHS.Data[I])
>       continue;
61,62d62
<     if (Data[I] == RHS.Data[I])
<       continue;

I ran this, and now I have no problems, and the other targets built as well, at least, without problems. I have not run the testsuite.

Jonas


Subject: Re: [LLVMdev] Tablegen: RegisterInfoEmitter.cpp
From: stoklund at 2pi.dk
Date: Fri, 30 Sep 2011 08:39:51 -0700
CC: llvmdev at cs.uiuc.edu
To: jnspaulsson at hotmail.com




On Sep 30, 2011, at 8:29 AM, Jonas Paulsson wrote:The conclusion is that the StringRef::compare_numeric() is not deterministic
Thanks for tracking this down.
I believe we have a bug in compare_numeric() causing it to be non-transitive sometimes. It is supposed to provide a total ordering of strings. Can you find the bug?
/jakob

 		 	   		  
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20111001/ec0407b0/attachment.html>