TableGen: ClassInfos are not well ordered

[dwblaikie]

Bugzilla Link	22796
Version	trunk
OS	Linux
CC	@dexonsmith

Extended Description

There appear to be contradictions in the ordering of matchables.

I found this when attempting to change the data structures for the matchables (see the review thread for r222935)

By walking the 'sorted' list after the stable_sort of Matchables, I was able to find places where the sorting was incomplete:

std::stable_sort(Info.Matchables.begin(), Info.Matchables.end(), [](const std::unique_ptr &a, const std::unique_ptr &b){ return a < b;});

for (auto I = Info.Matchables.begin(), E = Info.Matchables.end(); I != E; ++I) { for (auto J = I; J != E; ++J) { bool greater = J < I; assert(!greater); } }

I added further checks (which I've lost, but could help someone reconstruct if they're interested) to try to find specific contradictions, especially in short cycles. Here's one short cycle I found:

X: Mnemonic: vshl AsmOperands.size(): 4 AsmOperands[0].Class: MCK_CondCode AsmOperands[1].Class: MCK__DOT_u64

X + 1: Mnemonic: vshl AsmOperands.size(): 4 AsmOperands[0].Class: MCK_CondCode AsmOperands[1].Class: MCK__DOT_i64

X + 2: Mnemonic: vshl AsmOperands.size(): 4 AsmOperands[0].Class.MCK_CondCode AsmOperands[1].Class.MCK_s8

(MCKDOT_u64 < MCKDOT_i64) (MCK_s8 < MCKDOT_u64) (MCKDOT_i64 < MCK__DOT_s8)

This is because:

u64 < i64: u64 is a subset of i64 i64 < s8: i64 and s8 are not subsets of each other, so order by ValueName ('.i64' < '.s8') s8 < u64: s8 and u64 are not subsets of each other, so order by ValueName ('.u64' !< '.s8')

[3f18db19-85d0-42b5-b58f-dbfbd8cbce51]

I had some ideas for how to push forward on the mailing list:

http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20150209/258339.html

[dwblaikie]

Added a FIXME for this in r231282