[Bug rtl-optimization/68988] New: reload_pseudo_compare_func violates qsort requirements

[y.gribov at samsung dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=68988

            Bug ID: 68988
           Summary: reload_pseudo_compare_func violates qsort requirements
           Product: gcc
           Version: 6.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: rtl-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: y.gribov at samsung dot com
                CC: vmakarov at redhat dot com
  Target Milestone: ---

One of the comparisons in reload_pseudo_compare_func violates the transitivity
axiom (i.e. x < y && y < z => x < z) which is a requirement for proper
comparison function. The offending piece is

  if ((diff
       = (ira_reg_class_max_nregs[cl2][lra_reg_info[r2].biggest_mode]
          - ira_reg_class_max_nregs[cl1][lra_reg_info[r1].biggest_mode])) != 0
      /* The code below executes rarely as nregs == 1 in most cases.
         So we should not worry about using faster data structures to
         check reload pseudos.  */
      && ! bitmap_bit_p (&non_reload_pseudos, r1)
      && ! bitmap_bit_p (&non_reload_pseudos, r2))

This one is activated only when non_reload_pseudos is off for both r1 and r2.

Now imagine that we compare non-reload pseudos A, B but for reload pseudo C.
Then A/B pair will be compared absolutely differently from A/C and B/C pairs.
In practice this may lead to violation of transitivity axiom which may puzzle
qsort and lead to all sorts of bugs (e.g. unsorted array of pseudos).

For additional details check
https://gcc.gnu.org/ml/gcc-patches/2015-12/msg01817.html