On Mon, Jul 17, 2017 at 11:10:01AM +0300, Alexander Monakov wrote:
> On Sun, 16 Jul 2017, Segher Boessenkool wrote:
> > > How? There's no stable sort in libc and switching over to std::stable_sort
> > > would be problematic.
> > Why?
> - you'd need to decide if the build time cost of extra 8000+ lines
> lines brought in by <algorithm> (per each TU) is acceptable;
> - you'd need to decide if the code size cost of multiple instantiations
> of template stable_sort is acceptable (or take measures to unify them);
OTOH it should be faster than calling callbacks all the time.
> - you'd need to adapt comparators, as STL uses a different interface
> that C qsort;
> - you'd need to ensure it doesn't lead to a noticeable slowdown.
Okay, so the slowness of compiling STL stuff is a very real issue.
> > Sure. Some of our sorts in fact require stable sort though
> At moment only bb-reorder appears to use std::stable_sort, is that what
> you meant, or are there more places?
For example all_saved_regs (in caller-save.c) ensures a stable sort
(I don't know if it actually needs it, or this is just to ensure
only identical objects compare equal). I know the one in bb-reorder
very much does need it (I added it myself). Sure, you can avoid it
by essentially doing it manually (with a last-resort comparison).