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
