[LLVMdev] Tablegen: RegisterInfoEmitter.cpp

[Jakob Stoklund Olesen]

On Oct 1, 2011, at 2:42 AM, Jonas Paulsson wrote:

> 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.

Almost. It is trying to compare embedded sequences of digits as numbers. It does this by first comparing the length of the digit sequence, and then a lexicographical comparison of equal length digit sequences.

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

No, a1b < a12 < a22. "a1b" is smaller than "a12" because it has fewer digits. "a12" has the same number of digits as "a22", but it is lexicographically smaller.

> 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:

> /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.

Your fix is correct, but there is one problem: The algorithm is now quadratic in the length of embedded digit sequences.

This is easy to fix, see r140859.

Thanks!

/jakob

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