[LLVMbugs] [Bug 17419] New: AsmMatcherEmitter's ClassInfo comparator not transitive

[bugzilla-daemon at llvm.org]

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

            Bug ID: 17419
           Summary: AsmMatcherEmitter's ClassInfo comparator not
                    transitive
           Product: new-bugs
           Version: trunk
          Hardware: PC
                OS: Linux
            Status: NEW
          Severity: normal
          Priority: P
         Component: new bugs
          Assignee: unassignedbugs at nondot.org
          Reporter: willdtz at gmail.com
                CC: llvmbugs at cs.uiuc.edu
    Classification: Unclassified

Similar to the recent fix posted for the sorting predicate used in
DAGISelEmitter[1], the sorting predicate used in AsmMatcherEmitter for
ClassInfo objects is also non-transitive.

This results in unspecified sorting behavior and in particular
breaks tests relying on a particular match ordering
(possibly producing inferior assembly or other problems).

The comparison operator is in AsmMatcherEmitter.cpp:265.

Examples of lack of transitivity are:

class A subclass B, B.Kind < A.Kind.
when a class 'C' has a kind between B and A, this breaks:

A < B (A subclass B)
B < C (unrelated classes, B.Kind < C.Kind)
C < A (unrelated classes, C.Kind < A.Kind)

And a similar failure with ValueName causing the failure
instead of the Kind comparison.

I've seen both of these failures happen when emitting the AsmMatcher for X86,
I haven't tested other platforms.  These were detected while debugging building
LLVM w/an alternative C++ implementation, with the following sanity check added
to std::sort():

--------------
for (_RandomAccessIterator cur = first; cur != last; ++cur)
  for (_RandomAccessIterator before = first; before != cur; ++before)
    assert((comp(*before, *cur) || !comp(*cur, *before)) && 
           "Bad sort predicate");
--------------

Perhaps a preprocessing pass over the ClassInfo's that builds a numbering would
work?  A postorder traversal of the class heirarchy should provide a reasonable
such numbering, I believe, and can use Kind/ValueName as we presently do to
break ties amongst children for output that's as deterministic as what we have
today.

Regardless if someone could take a look that'd be great.  Thanks! :)

[1]
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20130930/189318.html

-- 
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/20130930/cab2ee4d/attachment.html>