[LLVMbugs] [Bug 22796] New: TableGen: Matchables are not well ordered

[bugzilla-daemon at llvm.org]

http://llvm.org/bugs/show_bug.cgi?id=22796

            Bug ID: 22796
           Summary: TableGen: Matchables are not well ordered
           Product: libraries
           Version: trunk
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: normal
          Priority: P
         Component: Common Code Generator Code
          Assignee: unassignedbugs at nondot.org
          Reporter: dblaikie at gmail.com
                CC: dexonsmith at apple.com, llvmbugs at cs.uiuc.edu
    Classification: Unclassified

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<MatchableInfo> &a,
                      const std::unique_ptr<MatchableInfo> &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

(MCK__DOT_u64 < MCK__DOT_i64)
(MCK_s8 < MCK__DOT_u64)
(MCK__DOT_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')

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20150304/3a95793d/attachment.html>