[2/2] IPA ICF: make algorithm stable to survive -fcompare-debug

Message ID 719d17b0-baf0-4fe8-dd7c-43365e9c689c@suse.cz
State New
Headers show

Commit Message

Martin Liška Jan. 9, 2017, 3:05 p.m.
Second part of the patch does sorting of final congruence classes, it's groups
and items included in the groups according DECL_UID.

Both patches can bootstrap together on ppc64le-redhat-linux and survive regression tests.

Ready to be installed?
Martin

Comments

Richard Biener Jan. 10, 2017, 1:56 p.m. | #1
On Mon, Jan 9, 2017 at 4:05 PM, Martin Liška <mliska@suse.cz> wrote:
> Second part of the patch does sorting of final congruence classes, it's groups

> and items included in the groups according DECL_UID.

>

> Both patches can bootstrap together on ppc64le-redhat-linux and survive regression tests.

>

> Ready to be installed?


Minor nit:

+  auto_vec <congruence_class_group *> classes;
+  for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
+       it != m_classes.end (); ++it)
+    classes.safe_push (*it);

use quick_push and reserve_exact m_classes.elements () elements for
the classes vector before.

+
+  classes.qsort (sort_congruence_class_groups_by_decl_uid);

Ok with that change.

Richard.


> Martin
Martin Liška Jan. 10, 2017, 2:40 p.m. | #2
On 01/10/2017 02:56 PM, Richard Biener wrote:
> On Mon, Jan 9, 2017 at 4:05 PM, Martin Liška <mliska@suse.cz> wrote:

>> Second part of the patch does sorting of final congruence classes, it's groups

>> and items included in the groups according DECL_UID.

>>

>> Both patches can bootstrap together on ppc64le-redhat-linux and survive regression tests.

>>

>> Ready to be installed?

>

> Minor nit:

>

> +  auto_vec <congruence_class_group *> classes;

> +  for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();

> +       it != m_classes.end (); ++it)

> +    classes.safe_push (*it);

>

> use quick_push and reserve_exact m_classes.elements () elements for

> the classes vector before.


Thanks for hint.

>

> +

> +  classes.qsort (sort_congruence_class_groups_by_decl_uid);

>

> Ok with that change.


Installed as r244273.

Martin

>

> Richard.

>

>

>> Martin
Christophe Lyon Jan. 11, 2017, 10:21 a.m. | #3
Hi Martin,

On 10 January 2017 at 15:40, Martin Liška <mliska@suse.cz> wrote:
> On 01/10/2017 02:56 PM, Richard Biener wrote:

>>

>> On Mon, Jan 9, 2017 at 4:05 PM, Martin Liška <mliska@suse.cz> wrote:

>>>

>>> Second part of the patch does sorting of final congruence classes, it's

>>> groups

>>> and items included in the groups according DECL_UID.

>>>

>>> Both patches can bootstrap together on ppc64le-redhat-linux and survive

>>> regression tests.

>>>

>>> Ready to be installed?

>>

>>

>> Minor nit:

>>

>> +  auto_vec <congruence_class_group *> classes;

>> +  for (hash_table<congruence_class_hash>::iterator it = m_classes.begin

>> ();

>> +       it != m_classes.end (); ++it)

>> +    classes.safe_push (*it);

>>

>> use quick_push and reserve_exact m_classes.elements () elements for

>> the classes vector before.

>

>

> Thanks for hint.

>

>>

>> +

>> +  classes.qsort (sort_congruence_class_groups_by_decl_uid);

>>

>> Ok with that change.

>

>

> Installed as r244273.

>

Since then, I've noticed that
  gcc.dg/tree-ssa/flatten-3.c scan-assembler cycle[123][: \t\n]
now fails on aarch64 and arm targets.

Christophe



> Martin

>

>>

>> Richard.

>>

>>

>>> Martin

>

>
Jakub Jelinek Jan. 11, 2017, 10:28 a.m. | #4
On Wed, Jan 11, 2017 at 11:21:08AM +0100, Christophe Lyon wrote:
> Since then, I've noticed that

>   gcc.dg/tree-ssa/flatten-3.c scan-assembler cycle[123][: \t\n]

> now fails on aarch64 and arm targets.


It fails on x86_64-linux and i686-linux too.

	Jakub
Martin Liška Jan. 11, 2017, 10:30 a.m. | #5
On 01/11/2017 11:28 AM, Jakub Jelinek wrote:
> On Wed, Jan 11, 2017 at 11:21:08AM +0100, Christophe Lyon wrote:

>> Since then, I've noticed that

>>   gcc.dg/tree-ssa/flatten-3.c scan-assembler cycle[123][: \t\n]

>> now fails on aarch64 and arm targets.

> 

> It fails on x86_64-linux and i686-linux too.

> 

> 	Jakub

> 


Sorry for the breakage, I'm going to fix that.

Martin
Dominik Vogt Jan. 18, 2017, 12:35 a.m. | #6
On Tue, Jan 10, 2017 at 03:40:00PM +0100, Martin Liška wrote:
> On 01/10/2017 02:56 PM, Richard Biener wrote:

> >On Mon, Jan 9, 2017 at 4:05 PM, Martin Liška <mliska@suse.cz> wrote:

> >>Second part of the patch does sorting of final congruence classes, it's groups

> >>and items included in the groups according DECL_UID.

> >>

> >>Both patches can bootstrap together on ppc64le-redhat-linux and survive regression tests.

> >>

> >>Ready to be installed?

> >

> >Minor nit:

> >

> >+  auto_vec <congruence_class_group *> classes;

> >+  for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();

> >+       it != m_classes.end (); ++it)

> >+    classes.safe_push (*it);

> >

> >use quick_push and reserve_exact m_classes.elements () elements for

> >the classes vector before.

> 

> Thanks for hint.

> 

> >

> >+

> >+  classes.qsort (sort_congruence_class_groups_by_decl_uid);

> >

> >Ok with that change.

> 

> Installed as r244273.


This patch has somehow broken the error line information in some
s390x test case:

.../build/gcc/xgcc -B.../gcc/ .../gcc/testsuite/gcc.target/s390/target-attribute/tattr-2.c -O3 -march=zEC12 -mno-htm -S -m64 -o tattr-2.s

...
.../gcc/testsuite/gcc.target/s390/target-attribute/tattr-2.c:
In function ‘a0’:
            ^^^^
.../gcc/testsuite/gcc.target/s390/target-attribute/tattr-2.c:23:3:
                                                            ^^^^
error: Builtin ‘__builtin_tend’ is not supported without -mhtm
(default with -march=zEC12 and higher).

But function a0 is actually in lines 37 to 43.  It looks like the
message has used the same line number as the previous message.

Ciao

Dominik ^_^  ^_^

-- 

Dominik Vogt
IBM Germany
Martin Liška Jan. 18, 2017, 9:53 a.m. | #7
On 01/18/2017 01:35 AM, Dominik Vogt wrote:
> On Tue, Jan 10, 2017 at 03:40:00PM +0100, Martin Liška wrote:

>> On 01/10/2017 02:56 PM, Richard Biener wrote:

>>> On Mon, Jan 9, 2017 at 4:05 PM, Martin Liška <mliska@suse.cz> wrote:

>>>> Second part of the patch does sorting of final congruence classes, it's groups

>>>> and items included in the groups according DECL_UID.

>>>>

>>>> Both patches can bootstrap together on ppc64le-redhat-linux and survive regression tests.

>>>>

>>>> Ready to be installed?

>>>

>>> Minor nit:

>>>

>>> +  auto_vec <congruence_class_group *> classes;

>>> +  for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();

>>> +       it != m_classes.end (); ++it)

>>> +    classes.safe_push (*it);

>>>

>>> use quick_push and reserve_exact m_classes.elements () elements for

>>> the classes vector before.

>>

>> Thanks for hint.

>>

>>>

>>> +

>>> +  classes.qsort (sort_congruence_class_groups_by_decl_uid);

>>>

>>> Ok with that change.

>>

>> Installed as r244273.

> 

> This patch has somehow broken the error line information in some

> s390x test case:

> 

> .../build/gcc/xgcc -B.../gcc/ .../gcc/testsuite/gcc.target/s390/target-attribute/tattr-2.c -O3 -march=zEC12 -mno-htm -S -m64 -o tattr-2.s

> 

> ...

> .../gcc/testsuite/gcc.target/s390/target-attribute/tattr-2.c:

> In function ‘a0’:

>             ^^^^

> .../gcc/testsuite/gcc.target/s390/target-attribute/tattr-2.c:23:3:

>                                                             ^^^^

> error: Builtin ‘__builtin_tend’ is not supported without -mhtm

> (default with -march=zEC12 and higher).


Hello.

As I've been reading when the warning is emitted (rtl expansion), I guess a pair of function was merged
by IPA ICF and thus the location points to a different function.

I can't reproduce the test-case due to missing __HTM__. Can you please provide pre-processed source file?

Thanks,
Martin

> 

> But function a0 is actually in lines 37 to 43.  It looks like the

> message has used the same line number as the previous message.

> 

> Ciao

> 

> Dominik ^_^  ^_^

>
Martin Liška Jan. 18, 2017, 10:29 a.m. | #8
On 01/18/2017 11:21 AM, Jakub Jelinek wrote:
> So my preference is to add -fno-ipa-icf to dg-options and

> add the missing dg-error line on line 42.

> 

> Like below, ok for trunk?


I like the idea of adding -fno-ipa-icf to the test-case.

Martin
Andreas Krebbel Jan. 18, 2017, 11:21 a.m. | #9
On 01/18/2017 11:21 AM, Jakub Jelinek wrote:
> 2017-01-18  Jakub Jelinek  <jakub@redhat.com>

> 

> 	* gcc.target/s390/target-attribute/tattr-2.c: Add -fno-ipa-icf

> 	to dg-options.

> 	(p0): Add missing dg-error.


Ok. Thanks!

-Andreas-
Dominik Vogt Jan. 18, 2017, 11:49 a.m. | #10
On Wed, Jan 18, 2017 at 11:21:50AM +0100, Jakub Jelinek wrote:
> On Wed, Jan 18, 2017 at 10:53:59AM +0100, Martin Liška wrote:

> > As I've been reading when the warning is emitted (rtl expansion), I guess a pair of function was merged

> > by IPA ICF and thus the location points to a different function.

> > 

> > I can't reproduce the test-case due to missing __HTM__. Can you please provide pre-processed source file?

> 

> The testcase doesn't include any headers, just compile it with a cross to

> s390x-linux.  That said, IMHO the test should either use -fno-ipa-icf,

> or use something to avoid ICFing of functions it doesn't want to fold

> (say use int return type instead of void and return a different constant in

> each case).

> 

> I think the testcase as written just assumes ICF happens but in a certain

> way and what broke is that the same functions are ICFed in a different order

> now, because with -fno-ipa-icf it reports:

> tattr-2.c: In function ‘p0’:

> tattr-2.c:23:3: error: Builtin ‘__builtin_tend’ is not supported without -mhtm (default with -march=zEC12 and higher).

>    __builtin_tend ();

>    ^~~~~~~~~~~~~~~~~

> tattr-2.c: In function ‘a0’:

> tattr-2.c:42:3: error: Builtin ‘__builtin_tend’ is not supported without -mhtm (default with -march=zEC12 and higher).

>    __builtin_tend (); /* { dg-error "is not supported without -mhtm" } */

>    ^~~~~~~~~~~~~~~~~

> tattr-2.c: In function ‘htmd’:

> tattr-2.c:50:3: error: Builtin ‘__builtin_tend’ is not supported without -mhtm (default with -march=zEC12 and higher).

>    __builtin_tend (); /* { dg-error "is not supported without -mhtm" } */

>    ^~~~~~~~~~~~~~~~~

> So my preference is to add -fno-ipa-icf to dg-options and

> add the missing dg-error line on line 42.


You mean line 23.  Does -fno-ipa-icf also enable the error there?

> Like below, ok for trunk?


Looks good.

> 

> 2017-01-18  Jakub Jelinek  <jakub@redhat.com>

> 

> 	* gcc.target/s390/target-attribute/tattr-2.c: Add -fno-ipa-icf

> 	to dg-options.

> 	(p0): Add missing dg-error.

> 

> --- gcc/testsuite/gcc.target/s390/target-attribute/tattr-2.c.jj	2015-12-04 17:19:09.000000000 +0100

> +++ gcc/testsuite/gcc.target/s390/target-attribute/tattr-2.c	2017-01-18 11:18:15.674196392 +0100

> @@ -2,7 +2,7 @@

> 

>  /* { dg-do compile */

>  /* { dg-require-effective-target target_attribute } */

> -/* { dg-options "-O3 -march=zEC12 -mno-htm" } */

> +/* { dg-options "-O3 -march=zEC12 -mno-htm -fno-ipa-icf" } */

> 

>  #pragma GCC target("htm")

>  void p1(void)

> @@ -20,7 +20,7 @@ void p0(void)

>  #ifdef __HTM__

>  #error __HTM__ is defined

>  #endif

> -  __builtin_tend ();

> +  __builtin_tend (); /* { dg-error "is not supported without -mhtm" } */

>  }

>  #pragma GCC reset_options


Ciao

Dominik ^_^  ^_^

-- 

Dominik Vogt
IBM Germany
Jakub Jelinek Jan. 18, 2017, 12:05 p.m. | #11
Hi!
On Wed, Jan 18, 2017 at 12:49:19PM +0100, Dominik Vogt wrote:
> > I think the testcase as written just assumes ICF happens but in a certain

> > way and what broke is that the same functions are ICFed in a different order

> > now, because with -fno-ipa-icf it reports:

> > tattr-2.c: In function ‘p0’:

> > tattr-2.c:23:3: error: Builtin ‘__builtin_tend’ is not supported without -mhtm (default with -march=zEC12 and higher).

> >    __builtin_tend ();

> >    ^~~~~~~~~~~~~~~~~

> > tattr-2.c: In function ‘a0’:

> > tattr-2.c:42:3: error: Builtin ‘__builtin_tend’ is not supported without -mhtm (default with -march=zEC12 and higher).

> >    __builtin_tend (); /* { dg-error "is not supported without -mhtm" } */

> >    ^~~~~~~~~~~~~~~~~

> > tattr-2.c: In function ‘htmd’:

> > tattr-2.c:50:3: error: Builtin ‘__builtin_tend’ is not supported without -mhtm (default with -march=zEC12 and higher).

> >    __builtin_tend (); /* { dg-error "is not supported without -mhtm" } */

> >    ^~~~~~~~~~~~~~~~~

> > So my preference is to add -fno-ipa-icf to dg-options and

> > add the missing dg-error line on line 42.

> 

> You mean line 23.  Does -fno-ipa-icf also enable the error there?

> 

> > Like below, ok for trunk?

> 

> Looks good.


Committed to trunk.
Two more things:
1)
823		  error ("Builtin %qF is not supported without -mhtm "
824			 "(default with -march=zEC12 and higher).", fndecl);
   is a bug, diagnostics (I think Fortran FE is a big exception here) should
   not start with capital letters, so it should be "builtin instead of
   "Builtin .  Please look at other diagnostics in config/s390
2) what happens on the testcase is actually quite nasty, which is why
   you get 3 errors instead of just 2 I was expecting with the default
   -fipa-icf - first ICF optimizes a0 + p0 and a1 + p1 calls, with
   current trunk a0 and a1 are thunks that call p0 or p1.  And then
   comes inlining and inlines p0 into a0 and p1 into a1, which basically
   undoes the ICF optimization, but not even that, it is worse than before
   because the debug info as well as locations are as if p0 has been an
   inline function inlined into a0.  Dunno if ICF shouldn't check if
   the functions aren't small enough not to be worth ICFing them together,
   or if inlining shouldn't recognize ICF created thunks and not inline
   into them

	Jakub
Andreas Krebbel Jan. 18, 2017, 1:54 p.m. | #12
On 01/18/2017 01:05 PM, Jakub Jelinek wrote:
...
> Two more things:

> 1)

> 823		  error ("Builtin %qF is not supported without -mhtm "

> 824			 "(default with -march=zEC12 and higher).", fndecl);

>    is a bug, diagnostics (I think Fortran FE is a big exception here) should

>    not start with capital letters, so it should be "builtin instead of

>    "Builtin .  Please look at other diagnostics in config/s390


These have been added by me.  I'll commit a patch.

-Andreas-

Patch hide | download patch | download mbox

From c3baaad9da1fdaa95ff5b8a69fc7925ede13d8c9 Mon Sep 17 00:00:00 2001
From: marxin <mliska@suse.cz>
Date: Fri, 6 Jan 2017 13:30:08 +0100
Subject: [PATCH 2/2] IPA ICF: make algorithm stable to survive -fcompare-debug

gcc/testsuite/ChangeLog:

2017-01-06  Martin Liska  <mliska@suse.cz>

	* gcc.dg/ipa/ipa-icf-1.c: Change scanned pattern.
	* gcc.dg/ipa/ipa-icf-10.c: Likewise.
	* gcc.dg/ipa/ipa-icf-11.c: Likewise.
	* gcc.dg/ipa/ipa-icf-12.c: Likewise.
	* gcc.dg/ipa/ipa-icf-13.c: Likewise.
	* gcc.dg/ipa/ipa-icf-16.c: Likewise.
	* gcc.dg/ipa/ipa-icf-18.c: Likewise.
	* gcc.dg/ipa/ipa-icf-2.c: Likewise.
	* gcc.dg/ipa/ipa-icf-20.c: Likewise.
	* gcc.dg/ipa/ipa-icf-21.c: Likewise.
	* gcc.dg/ipa/ipa-icf-23.c: Likewise.
	* gcc.dg/ipa/ipa-icf-25.c: Likewise.
	* gcc.dg/ipa/ipa-icf-26.c: Likewise.
	* gcc.dg/ipa/ipa-icf-27.c: Likewise.
	* gcc.dg/ipa/ipa-icf-3.c: Likewise.
	* gcc.dg/ipa/ipa-icf-35.c: Likewise.
	* gcc.dg/ipa/ipa-icf-36.c: Likewise.
	* gcc.dg/ipa/ipa-icf-37.c: Likewise.
	* gcc.dg/ipa/ipa-icf-5.c: Likewise.
	* gcc.dg/ipa/ipa-icf-7.c: Likewise.
	* gcc.dg/ipa/ipa-icf-8.c: Likewise.
	* gcc.dg/ipa/pr64307.c: Likewise.
	* gcc.dg/ipa/pr77653.c: Likewise.

gcc/ChangeLog:

2017-01-06  Martin Liska  <mliska@suse.cz>

	* ipa-icf.c (sort_sem_items_by_decl_uid): New function.
	(sort_congruence_classes_by_decl_uid): Likewise.
	(sort_congruence_class_groups_by_decl_uid): Likewise.
	(sem_item_optimizer::merge_classes): Sort class, groups in these
	classes and members in the groups by DECL_UID of declarations.
	This would make merge operations stable.
---
 gcc/ipa-icf.c                         | 92 +++++++++++++++++++++++++++++++++--
 gcc/testsuite/gcc.dg/ipa/ipa-icf-1.c  |  2 +-
 gcc/testsuite/gcc.dg/ipa/ipa-icf-10.c |  2 +-
 gcc/testsuite/gcc.dg/ipa/ipa-icf-11.c |  2 +-
 gcc/testsuite/gcc.dg/ipa/ipa-icf-12.c |  2 +-
 gcc/testsuite/gcc.dg/ipa/ipa-icf-13.c |  6 +--
 gcc/testsuite/gcc.dg/ipa/ipa-icf-16.c |  2 +-
 gcc/testsuite/gcc.dg/ipa/ipa-icf-18.c |  2 +-
 gcc/testsuite/gcc.dg/ipa/ipa-icf-2.c  |  2 +-
 gcc/testsuite/gcc.dg/ipa/ipa-icf-20.c |  2 +-
 gcc/testsuite/gcc.dg/ipa/ipa-icf-21.c |  2 +-
 gcc/testsuite/gcc.dg/ipa/ipa-icf-23.c |  2 +-
 gcc/testsuite/gcc.dg/ipa/ipa-icf-25.c |  4 +-
 gcc/testsuite/gcc.dg/ipa/ipa-icf-26.c |  2 +-
 gcc/testsuite/gcc.dg/ipa/ipa-icf-27.c |  2 +-
 gcc/testsuite/gcc.dg/ipa/ipa-icf-3.c  |  2 +-
 gcc/testsuite/gcc.dg/ipa/ipa-icf-35.c |  6 +--
 gcc/testsuite/gcc.dg/ipa/ipa-icf-36.c | 10 ++--
 gcc/testsuite/gcc.dg/ipa/ipa-icf-37.c | 10 ++--
 gcc/testsuite/gcc.dg/ipa/ipa-icf-5.c  |  2 +-
 gcc/testsuite/gcc.dg/ipa/ipa-icf-7.c  |  2 +-
 gcc/testsuite/gcc.dg/ipa/ipa-icf-8.c  |  2 +-
 gcc/testsuite/gcc.dg/ipa/pr64307.c    |  2 +-
 gcc/testsuite/gcc.dg/ipa/pr77653.c    |  2 +-
 24 files changed, 124 insertions(+), 40 deletions(-)

diff --git a/gcc/ipa-icf.c b/gcc/ipa-icf.c
index 28de251c421..4c835c39e3d 100644
--- a/gcc/ipa-icf.c
+++ b/gcc/ipa-icf.c
@@ -3380,6 +3380,66 @@  sem_item_optimizer::dump_cong_classes (void)
   free (histogram);
 }
 
+/* Sort pair of sem_items A and B by DECL_UID.  */
+
+static int
+sort_sem_items_by_decl_uid (const void *a, const void *b)
+{
+  const sem_item *i1 = *(const sem_item * const *)a;
+  const sem_item *i2 = *(const sem_item * const *)b;
+
+  int uid1 = DECL_UID (i1->decl);
+  int uid2 = DECL_UID (i2->decl);
+
+  if (uid1 < uid2)
+    return -1;
+  else if (uid1 > uid2)
+    return 1;
+  else
+    return 0;
+}
+
+/* Sort pair of congruence_classes A and B by DECL_UID of the first member.  */
+
+static int
+sort_congruence_classes_by_decl_uid (const void *a, const void *b)
+{
+  const congruence_class *c1 = *(const congruence_class * const *)a;
+  const congruence_class *c2 = *(const congruence_class * const *)b;
+
+  int uid1 = DECL_UID (c1->members[0]->decl);
+  int uid2 = DECL_UID (c2->members[0]->decl);
+
+  if (uid1 < uid2)
+    return -1;
+  else if (uid1 > uid2)
+    return 1;
+  else
+    return 0;
+}
+
+/* Sort pair of congruence_class_groups A and B by
+   DECL_UID of the first member of a first group.  */
+
+static int
+sort_congruence_class_groups_by_decl_uid (const void *a, const void *b)
+{
+  const congruence_class_group *g1
+    = *(const congruence_class_group * const *)a;
+  const congruence_class_group *g2
+    = *(const congruence_class_group * const *)b;
+
+  int uid1 = DECL_UID (g1->classes[0]->members[0]->decl);
+  int uid2 = DECL_UID (g2->classes[0]->members[0]->decl);
+
+  if (uid1 < uid2)
+    return -1;
+  else if (uid1 > uid2)
+    return 1;
+  else
+    return 0;
+}
+
 /* After reduction is done, we can declare all items in a group
    to be equal. PREV_CLASS_COUNT is start number of classes
    before reduction. True is returned if there's a merge operation
@@ -3397,6 +3457,22 @@  sem_item_optimizer::merge_classes (unsigned int prev_class_count)
 
   bool merged_p = false;
 
+  /* PR lto/78211
+     Sort functions in congruence classes by DECL_UID and do the same
+     for the classes to not to break -fcompare-debug.  */
+
+  for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
+       it != m_classes.end (); ++it)
+    {
+      for (unsigned int i = 0; i < (*it)->classes.length (); i++)
+	{
+	  congruence_class *c = (*it)->classes[i];
+	  c->members.qsort (sort_sem_items_by_decl_uid);
+	}
+
+      (*it)->classes.qsort (sort_congruence_classes_by_decl_uid);
+    }
+
   for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
        it != m_classes.end (); ++it)
     for (unsigned int i = 0; i < (*it)->classes.length (); i++)
@@ -3409,6 +3485,13 @@  sem_item_optimizer::merge_classes (unsigned int prev_class_count)
 	  }
       }
 
+  auto_vec <congruence_class_group *> classes;
+  for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
+       it != m_classes.end (); ++it)
+    classes.safe_push (*it);
+
+  classes.qsort (sort_congruence_class_groups_by_decl_uid);
+
   if (dump_file)
     {
       fprintf (dump_file, "\nItem count: %u\n", item_count);
@@ -3426,11 +3509,12 @@  sem_item_optimizer::merge_classes (unsigned int prev_class_count)
 	       item_count ? 100.0f * equal_items / item_count : 0.0f);
     }
 
-  for (hash_table<congruence_class_hash>::iterator it = m_classes.begin ();
-       it != m_classes.end (); ++it)
-    for (unsigned int i = 0; i < (*it)->classes.length (); i++)
+  unsigned int l;
+  congruence_class_group *it;
+  FOR_EACH_VEC_ELT (classes, l, it)
+    for (unsigned int i = 0; i < it->classes.length (); i++)
       {
-	congruence_class *c = (*it)->classes[i];
+	congruence_class *c = it->classes[i];
 
 	if (c->members.length () == 1)
 	  continue;
diff --git a/gcc/testsuite/gcc.dg/ipa/ipa-icf-1.c b/gcc/testsuite/gcc.dg/ipa/ipa-icf-1.c
index af86b9b8d50..a3d88585a9e 100644
--- a/gcc/testsuite/gcc.dg/ipa/ipa-icf-1.c
+++ b/gcc/testsuite/gcc.dg/ipa/ipa-icf-1.c
@@ -56,5 +56,5 @@  int main(int argc, char **argv)
   return 0;
 }
 
-/* { dg-final { scan-ipa-dump "Semantic equality hit:x2->x1" "icf"  } } */
+/* { dg-final { scan-ipa-dump "Semantic equality hit:x1->x2" "icf"  } } */
 /* { dg-final { scan-ipa-dump "Equal symbols: 1" "icf"  } } */
diff --git a/gcc/testsuite/gcc.dg/ipa/ipa-icf-10.c b/gcc/testsuite/gcc.dg/ipa/ipa-icf-10.c
index 6a2dd008849..5f76c1d87e7 100644
--- a/gcc/testsuite/gcc.dg/ipa/ipa-icf-10.c
+++ b/gcc/testsuite/gcc.dg/ipa/ipa-icf-10.c
@@ -29,5 +29,5 @@  int main(int argc, char **argv)
   return 0;
 }
 
-/* { dg-final { scan-ipa-dump "Semantic equality hit:funkce->ferda" "icf"  } } */
+/* { dg-final { scan-ipa-dump "Semantic equality hit:ferda->funkce" "icf"  } } */
 /* { dg-final { scan-ipa-dump "Equal symbols: 1" "icf"  } } */
diff --git a/gcc/testsuite/gcc.dg/ipa/ipa-icf-11.c b/gcc/testsuite/gcc.dg/ipa/ipa-icf-11.c
index 33b62ca6eb7..2610af9e55c 100644
--- a/gcc/testsuite/gcc.dg/ipa/ipa-icf-11.c
+++ b/gcc/testsuite/gcc.dg/ipa/ipa-icf-11.c
@@ -24,5 +24,5 @@  int main(int argc, char **argv)
   return f0(argc) * f1(argc);
 }
 
-/* { dg-final { scan-ipa-dump "Semantic equality hit:f1->f0" "icf"  } } */
+/* { dg-final { scan-ipa-dump "Semantic equality hit:f0->f1" "icf"  } } */
 /* { dg-final { scan-ipa-dump "Equal symbols: 1" "icf"  } } */
diff --git a/gcc/testsuite/gcc.dg/ipa/ipa-icf-12.c b/gcc/testsuite/gcc.dg/ipa/ipa-icf-12.c
index 8c03a47431b..8e4aa56b032 100644
--- a/gcc/testsuite/gcc.dg/ipa/ipa-icf-12.c
+++ b/gcc/testsuite/gcc.dg/ipa/ipa-icf-12.c
@@ -73,5 +73,5 @@  int main(int argc, char **argv)
   return 0;
 }
 
-/* { dg-final { scan-ipa-dump "Semantic equality hit:nsd->gcd" "icf"  } } */
+/* { dg-final { scan-ipa-dump "Semantic equality hit:gcd->nsd" "icf"  } } */
 /* { dg-final { scan-ipa-dump "Equal symbols: 1" "icf"  } } */
diff --git a/gcc/testsuite/gcc.dg/ipa/ipa-icf-13.c b/gcc/testsuite/gcc.dg/ipa/ipa-icf-13.c
index dd3f262146f..09d817c4030 100644
--- a/gcc/testsuite/gcc.dg/ipa/ipa-icf-13.c
+++ b/gcc/testsuite/gcc.dg/ipa/ipa-icf-13.c
@@ -187,7 +187,7 @@  int main(int argc, char **argv)
   printf("Test2: %d, %d, gdc: %d\n", a, b, nsd(a, b));
 }
 
-/* { dg-final { scan-ipa-dump "Semantic equality hit:s2->s1" "icf"  } } */
-/* { dg-final { scan-ipa-dump "Semantic equality hit:nsd_different_result2->nsd_different_result" "icf"  } } */
-/* { dg-final { scan-ipa-dump "Semantic equality hit:nsd->gcd" "icf"  } } */
+/* { dg-final { scan-ipa-dump "Semantic equality hit:s1->s2" "icf"  } } */
+/* { dg-final { scan-ipa-dump "Semantic equality hit:nsd_different_result->nsd_different_result2" "icf"  } } */
+/* { dg-final { scan-ipa-dump "Semantic equality hit:gcd->nsd" "icf"  } } */
 /* { dg-final { scan-ipa-dump "Equal symbols: 3" "icf"  } } */
diff --git a/gcc/testsuite/gcc.dg/ipa/ipa-icf-16.c b/gcc/testsuite/gcc.dg/ipa/ipa-icf-16.c
index 6f038f13cf9..a2613af5dd5 100644
--- a/gcc/testsuite/gcc.dg/ipa/ipa-icf-16.c
+++ b/gcc/testsuite/gcc.dg/ipa/ipa-icf-16.c
@@ -22,5 +22,5 @@  int main()
   return foo() + bar();
 }
 
-/* { dg-final { scan-ipa-dump "Semantic equality hit:bar->foo" "icf"  } } */
+/* { dg-final { scan-ipa-dump "Semantic equality hit:foo->bar" "icf"  } } */
 /* { dg-final { scan-ipa-dump "Equal symbols: 1" "icf"  } } */
diff --git a/gcc/testsuite/gcc.dg/ipa/ipa-icf-18.c b/gcc/testsuite/gcc.dg/ipa/ipa-icf-18.c
index a8e28c1ff3a..e246c2b3404 100644
--- a/gcc/testsuite/gcc.dg/ipa/ipa-icf-18.c
+++ b/gcc/testsuite/gcc.dg/ipa/ipa-icf-18.c
@@ -32,5 +32,5 @@  int main()
   return 0;
 }
 
-/* { dg-final { scan-ipa-dump "Semantic equality hit:bar->foo" "icf"  } } */
+/* { dg-final { scan-ipa-dump "Semantic equality hit:foo->bar" "icf"  } } */
 /* { dg-final { scan-ipa-dump "Equal symbols: 1" "icf"  } } */
diff --git a/gcc/testsuite/gcc.dg/ipa/ipa-icf-2.c b/gcc/testsuite/gcc.dg/ipa/ipa-icf-2.c
index 4d3cbafff4a..983e3d818d0 100644
--- a/gcc/testsuite/gcc.dg/ipa/ipa-icf-2.c
+++ b/gcc/testsuite/gcc.dg/ipa/ipa-icf-2.c
@@ -64,5 +64,5 @@  int main(int argc, char **argv)
   return 0;
 }
 
-/* { dg-final { scan-ipa-dump "Semantic equality hit:f2->f1" "icf"  } } */
+/* { dg-final { scan-ipa-dump "Semantic equality hit:f1->f2" "icf"  } } */
 /* { dg-final { scan-ipa-dump "Equal symbols: 1" "icf"  } } */
diff --git a/gcc/testsuite/gcc.dg/ipa/ipa-icf-20.c b/gcc/testsuite/gcc.dg/ipa/ipa-icf-20.c
index 470e466ba23..46dc70492f0 100644
--- a/gcc/testsuite/gcc.dg/ipa/ipa-icf-20.c
+++ b/gcc/testsuite/gcc.dg/ipa/ipa-icf-20.c
@@ -23,5 +23,5 @@  int main()
   return 0;
 }
 
-/* { dg-final { scan-ipa-dump "Semantic equality hit:bar->foo" "icf"  } } */
+/* { dg-final { scan-ipa-dump "Semantic equality hit:foo->bar" "icf"  } } */
 /* { dg-final { scan-ipa-dump "Equal symbols: 1" "icf"  } } */
diff --git a/gcc/testsuite/gcc.dg/ipa/ipa-icf-21.c b/gcc/testsuite/gcc.dg/ipa/ipa-icf-21.c
index 447fd7bad51..a20b4a43ffe 100644
--- a/gcc/testsuite/gcc.dg/ipa/ipa-icf-21.c
+++ b/gcc/testsuite/gcc.dg/ipa/ipa-icf-21.c
@@ -22,5 +22,5 @@  int main()
   return 2;
 }
 
-/* { dg-final { scan-ipa-dump "Semantic equality hit:bar->foo" "icf"  } } */
+/* { dg-final { scan-ipa-dump "Semantic equality hit:foo->bar" "icf"  } } */
 /* { dg-final { scan-ipa-dump "Equal symbols: 1" "icf"  } } */
diff --git a/gcc/testsuite/gcc.dg/ipa/ipa-icf-23.c b/gcc/testsuite/gcc.dg/ipa/ipa-icf-23.c
index 7787f06938e..02bb138c28d 100644
--- a/gcc/testsuite/gcc.dg/ipa/ipa-icf-23.c
+++ b/gcc/testsuite/gcc.dg/ipa/ipa-icf-23.c
@@ -24,5 +24,5 @@  int main()
   return foo(0) + bar(0);
 }
 
-/* { dg-final { scan-ipa-dump "Semantic equality hit:bar->foo" "icf"  } } */
+/* { dg-final { scan-ipa-dump "Semantic equality hit:foo->bar" "icf"  } } */
 /* { dg-final { scan-ipa-dump "Equal symbols: 1" "icf"  } } */
diff --git a/gcc/testsuite/gcc.dg/ipa/ipa-icf-25.c b/gcc/testsuite/gcc.dg/ipa/ipa-icf-25.c
index 7e42052fe20..4b364eb7c72 100644
--- a/gcc/testsuite/gcc.dg/ipa/ipa-icf-25.c
+++ b/gcc/testsuite/gcc.dg/ipa/ipa-icf-25.c
@@ -46,6 +46,6 @@  int main()
   return foo() + bar();
 }
 
-/* { dg-final { scan-ipa-dump "Semantic equality hit:bar->foo" "icf"  } } */
-/* { dg-final { scan-ipa-dump "Semantic equality hit:zap->zip" "icf"  } } */
+/* { dg-final { scan-ipa-dump "Semantic equality hit:foo->bar" "icf"  } } */
+/* { dg-final { scan-ipa-dump "Semantic equality hit:zip->zap" "icf"  } } */
 /* { dg-final { scan-ipa-dump "Equal symbols: 2" "icf"  } } */
diff --git a/gcc/testsuite/gcc.dg/ipa/ipa-icf-26.c b/gcc/testsuite/gcc.dg/ipa/ipa-icf-26.c
index f3bb675d82a..325ece1befa 100644
--- a/gcc/testsuite/gcc.dg/ipa/ipa-icf-26.c
+++ b/gcc/testsuite/gcc.dg/ipa/ipa-icf-26.c
@@ -38,5 +38,5 @@  int main()
   return 0;
 }
 
-/* { dg-final { scan-ipa-dump "Semantic equality hit:remove->destroy" "icf"  } } */
+/* { dg-final { scan-ipa-dump "Semantic equality hit:destroy->remove" "icf"  } } */
 /* { dg-final { scan-ipa-dump "Equal symbols: 1" "icf"  } } */
diff --git a/gcc/testsuite/gcc.dg/ipa/ipa-icf-27.c b/gcc/testsuite/gcc.dg/ipa/ipa-icf-27.c
index 7265ee4035e..bc49e58cb95 100644
--- a/gcc/testsuite/gcc.dg/ipa/ipa-icf-27.c
+++ b/gcc/testsuite/gcc.dg/ipa/ipa-icf-27.c
@@ -25,5 +25,5 @@  int main()
   return 0;
 }
 
-/* { dg-final { scan-ipa-dump "Semantic equality hit:remove->destroy" "icf"  } } */
+/* { dg-final { scan-ipa-dump "Semantic equality hit:destroy->remove" "icf"  } } */
 /* { dg-final { scan-ipa-dump "Equal symbols: 1" "icf"  } } */
diff --git a/gcc/testsuite/gcc.dg/ipa/ipa-icf-3.c b/gcc/testsuite/gcc.dg/ipa/ipa-icf-3.c
index 6418acea19c..2ecab2335c2 100644
--- a/gcc/testsuite/gcc.dg/ipa/ipa-icf-3.c
+++ b/gcc/testsuite/gcc.dg/ipa/ipa-icf-3.c
@@ -31,5 +31,5 @@  int main()
   return 0;
 }
 
-/* { dg-final { scan-ipa-dump "Semantic equality hit:bar->foo" "icf"  } } */
+/* { dg-final { scan-ipa-dump "Semantic equality hit:foo->bar" "icf"  } } */
 /* { dg-final { scan-ipa-dump "Equal symbols: 1" "icf"  } } */
diff --git a/gcc/testsuite/gcc.dg/ipa/ipa-icf-35.c b/gcc/testsuite/gcc.dg/ipa/ipa-icf-35.c
index ace6ae2b353..d194f918fd0 100644
--- a/gcc/testsuite/gcc.dg/ipa/ipa-icf-35.c
+++ b/gcc/testsuite/gcc.dg/ipa/ipa-icf-35.c
@@ -25,6 +25,6 @@  int main()
 }
 
 /* { dg-final { scan-ipa-dump "Equal symbols: 3" "icf"  } } */
-/* { dg-final { scan-ipa-dump "Semantic equality hit:f2->f1" "icf"  } } */
-/* { dg-final { scan-ipa-dump "Semantic equality hit:d->c" "icf"  } } */
-/* { dg-final { scan-ipa-dump "Semantic equality hit:b->a" "icf"  } } */
+/* { dg-final { scan-ipa-dump "Semantic equality hit:f1->f2" "icf"  } } */
+/* { dg-final { scan-ipa-dump "Semantic equality hit:c->d" "icf"  } } */
+/* { dg-final { scan-ipa-dump "Semantic equality hit:a->b" "icf"  } } */
diff --git a/gcc/testsuite/gcc.dg/ipa/ipa-icf-36.c b/gcc/testsuite/gcc.dg/ipa/ipa-icf-36.c
index d8cd5c8567e..5d125d0e1b7 100644
--- a/gcc/testsuite/gcc.dg/ipa/ipa-icf-36.c
+++ b/gcc/testsuite/gcc.dg/ipa/ipa-icf-36.c
@@ -29,8 +29,8 @@  int t(int tt)
   }
 }
 /* { dg-final { scan-ipa-dump "Equal symbols: 6" "icf"  } } */
-/* { dg-final { scan-ipa-dump "Semantic equality hit:b->a" "icf"  } } */
-/* { dg-final { scan-ipa-dump "Semantic equality hit:d->c" "icf"  } } */
-/* { dg-final { scan-ipa-dump "Semantic equality hit:f->e" "icf"  } } */
-/* { dg-final { scan-ipa-dump "Semantic equality hit:h->g" "icf"  } } */
-/* { dg-final { scan-ipa-dump "Semantic equality hit:k->i" "icf"  } } */
+/* { dg-final { scan-ipa-dump "Semantic equality hit:a->b" "icf"  } } */
+/* { dg-final { scan-ipa-dump "Semantic equality hit:c->d" "icf"  } } */
+/* { dg-final { scan-ipa-dump "Semantic equality hit:e->f" "icf"  } } */
+/* { dg-final { scan-ipa-dump "Semantic equality hit:g->h" "icf"  } } */
+/* { dg-final { scan-ipa-dump "Semantic equality hit:i->k" "icf"  } } */
diff --git a/gcc/testsuite/gcc.dg/ipa/ipa-icf-37.c b/gcc/testsuite/gcc.dg/ipa/ipa-icf-37.c
index 7314697e887..5c02e8ec336 100644
--- a/gcc/testsuite/gcc.dg/ipa/ipa-icf-37.c
+++ b/gcc/testsuite/gcc.dg/ipa/ipa-icf-37.c
@@ -29,8 +29,8 @@  int t(int tt)
   }
 }
 /* { dg-final { scan-ipa-dump "Equal symbols: 5" "icf"  } } */
-/* { dg-final { scan-ipa-dump "Semantic equality hit:b->a" "icf"  } } */
-/* { dg-final { scan-ipa-dump "Semantic equality hit:d->c" "icf"  } } */
-/* { dg-final { scan-ipa-dump "Semantic equality hit:f->e" "icf"  } } */
-/* { dg-final { scan-ipa-dump "Semantic equality hit:h->g" "icf"  } } */
-/* { dg-final { scan-ipa-dump "Semantic equality hit:j->i" "icf"  } } */
+/* { dg-final { scan-ipa-dump "Semantic equality hit:a->b" "icf"  } } */
+/* { dg-final { scan-ipa-dump "Semantic equality hit:c->d" "icf"  } } */
+/* { dg-final { scan-ipa-dump "Semantic equality hit:e->f" "icf"  } } */
+/* { dg-final { scan-ipa-dump "Semantic equality hit:g->h" "icf"  } } */
+/* { dg-final { scan-ipa-dump "Semantic equality hit:i->j" "icf"  } } */
diff --git a/gcc/testsuite/gcc.dg/ipa/ipa-icf-5.c b/gcc/testsuite/gcc.dg/ipa/ipa-icf-5.c
index bef80f27f65..b2d48f9d79d 100644
--- a/gcc/testsuite/gcc.dg/ipa/ipa-icf-5.c
+++ b/gcc/testsuite/gcc.dg/ipa/ipa-icf-5.c
@@ -51,5 +51,5 @@  int main()
   return 1;
 }
 
-/* { dg-final { scan-ipa-dump "Semantic equality hit:f2->f1" "icf"  } } */
+/* { dg-final { scan-ipa-dump "Semantic equality hit:f1->f2" "icf"  } } */
 /* { dg-final { scan-ipa-dump "Equal symbols: 1" "icf"  } } */
diff --git a/gcc/testsuite/gcc.dg/ipa/ipa-icf-7.c b/gcc/testsuite/gcc.dg/ipa/ipa-icf-7.c
index 862dd70d50c..488e133d93f 100644
--- a/gcc/testsuite/gcc.dg/ipa/ipa-icf-7.c
+++ b/gcc/testsuite/gcc.dg/ipa/ipa-icf-7.c
@@ -68,5 +68,5 @@  int main()
   return 1;
 }
 
-/* { dg-final { scan-ipa-dump "Semantic equality hit:foo2->foo" "icf"  } } */
+/* { dg-final { scan-ipa-dump "Semantic equality hit:foo->foo2" "icf"  } } */
 /* { dg-final { scan-ipa-dump "Equal symbols: 1" "icf"  } } */
diff --git a/gcc/testsuite/gcc.dg/ipa/ipa-icf-8.c b/gcc/testsuite/gcc.dg/ipa/ipa-icf-8.c
index 32eed406d53..8ee46d034e7 100644
--- a/gcc/testsuite/gcc.dg/ipa/ipa-icf-8.c
+++ b/gcc/testsuite/gcc.dg/ipa/ipa-icf-8.c
@@ -40,5 +40,5 @@  int main(int argc, char **argv)
   printf("fce2: %d\n", fce2(argc, 2 * argc));
 }
 
-/* { dg-final { scan-ipa-dump "Semantic equality hit:fce2->fce1" "icf"  } } */
+/* { dg-final { scan-ipa-dump "Semantic equality hit:fce1->fce2" "icf"  } } */
 /* { dg-final { scan-ipa-dump "Equal symbols: 1" "icf"  } } */
diff --git a/gcc/testsuite/gcc.dg/ipa/pr64307.c b/gcc/testsuite/gcc.dg/ipa/pr64307.c
index 87537c6113f..79d93af6eb7 100644
--- a/gcc/testsuite/gcc.dg/ipa/pr64307.c
+++ b/gcc/testsuite/gcc.dg/ipa/pr64307.c
@@ -27,5 +27,5 @@  int main()
   return r1 - r2;
 }
 
-/* { dg-final { scan-ipa-dump "Semantic equality hit:real_part_2->real_part" "icf"  } } */
+/* { dg-final { scan-ipa-dump "Semantic equality hit:real_part->real_part_2" "icf"  } } */
 /* { dg-final { scan-ipa-dump "Equal symbols: 1" "icf"  } } */
diff --git a/gcc/testsuite/gcc.dg/ipa/pr77653.c b/gcc/testsuite/gcc.dg/ipa/pr77653.c
index 16ae510bbb0..f508815a3fb 100644
--- a/gcc/testsuite/gcc.dg/ipa/pr77653.c
+++ b/gcc/testsuite/gcc.dg/ipa/pr77653.c
@@ -21,4 +21,4 @@  int main ()
 }
 
 /* { dg-final { scan-ipa-dump "Equal symbols: 1" "icf"  } } */
-/* { dg-final { scan-ipa-dump "Not unifying; address of original may be compared." "icf"  } } */
+/* { dg-final { scan-ipa-dump "Not unifying; alias cannot be created; target is discardable" "icf"  } } */
-- 
2.11.0