[PATCH] ipa-icf: compare the nonnull contract of two functions [PR123227]

Two functions with identical bodies can still make different promises
about their arguments, and ICF was not looking at those promises.
get_nonnull_args derives them from two places: the nonnull attribute on
the function type, and a METHOD_TYPE, whose this pointer is nonnull
whether or not anything says so.  sem_function::equals_wpa compared the
type attributes with comp_type_attributes, which by design only reports
attributes whose affects_type_identity is set, and nonnull is not one of
those, and it never compared FUNCTION_TYPE against METHOD_TYPE outside a
devirtualization specific check.  Either way the two functions were
declared equal and unified.  The surviving body keeps its own promise, a
later pass drops the null test that promise makes redundant, and a call
through the other symbol dereferences the null pointer that symbol was
required to accept.

Type identity is the wrong question for ICF.  The comment above the
variable case already says that for functions we do not know which
attributes affect code generation, which is why the decl attributes are
compared as whole lists.  Compare the type attributes the same way, and
reject a METHOD_TYPE paired with a FUNCTION_TYPE, which carries the same
promise with nothing on the attribute list to compare.

	PR ipa/123227

gcc/ChangeLog:

	* ipa-icf.cc (sem_function::equals_wpa): Compare TYPE_ATTRIBUTES
	as a list rather than through comp_type_attributes.  Reject a
	METHOD_TYPE compared against a FUNCTION_TYPE.

gcc/testsuite/ChangeLog:

	* gcc.dg/ipa/pr123227.c: New test.
	* g++.dg/ipa/pr123227.C: New test.
	* gcc.dg/lto/pr123227_0.c: New test.
	* gcc.dg/lto/pr123227_1.c: New test.
	* g++.dg/lto/pr123227_0.C: New test.
	* g++.dg/lto/pr123227_1.C: New test.

Signed-off-by: Rohith Kapelli <[email protected]>
---

Both spellings are in the PR: a C case with an explicit nonnull attribute,
and the reporter's original C++ case where a non-static member function is
unified with a free function.

The patch compares the type attributes as whole lists rather than through
comp_type_attributes, and rejects a METHOD_TYPE paired with a
FUNCTION_TYPE. Type identity is the wrong question for ICF.  The comment
already in the file says so: "For functions we compare attributes in
equals_wpa, because we do not know what attributes may cause codegen
differences".  That is why the DECL_ATTRIBUTES comparison immediately below
already compares whole lists with attribute_list_equal.  This change makes
the type attributes agree with the policy the file already states.

Comment 7 and comment 8 of the PR enumerate fifteen attributes that set
affects_type_identity false and can still affect generated code: nonnull,
nonnull_if_nonzero, warn_unused_result, sentinel, "fn spec",
returns_nonnull, alloc_align, assume_aligned, access, fd_arg, fd_arg_read,
fd_arg_write, null_terminated_string_arg, reproducible and unsequenced.
All fifteen are false in the 7th field of their entries in
gcc/c-family/c-attribs.cc, so comp_type_attributes skips every one of them.
Comparing the type attributes as a list covers the set.

Of the fourteen that can be written in source, one is exploitable today.
Three never reach ICF, because the attribute is consumed before it runs and
the bodies already differ.  Ten merge and stay correct, because they
constrain what a caller may assume rather than what the body may assume:
after a merge each symbol keeps its own declaration, which the dump shows
directly, returns_nonnull still on one decl and absent from the other.

That count is a fact about pass ordering, not about what ICF may ignore.
nonnull and nonnull_if_nonzero both constrain what the body may assume
about its parameters, which is the thing a merge shares, and the second is
safe only because another pass consumes it first.  An equality predicate
whose correctness depends on which attributes happen to be consumed before
it runs is the wrong shape for this pass.

I also implemented the narrower form, which keeps comp_type_attributes and
adds a comparison of the two get_nonnull_args bitmaps.  It is bootstrapped
with the same checking options and fully regression tested, and I can post
it on request.  It fixes nonnull and leaves the other fourteen attributes
as they are.  The two forms are indistinguishable in cost.  Merge counts
and code size, unpatched trunk against this patch against the narrow form:

  libstdc++ sources built into one shared library with LTO, merge counts read
  from the WPA stage dump, size is .text of the stripped library:
    -O2   182 unified, 255 equal symbols, 1707315 bytes, all three identical
    -Os   190 unified, 270 equal symbols, 1364990 bytes, all three identical
  2331 file testsuite corpus at -O2, gcc.c-torture/execute plus g++.dg/opt and
  g++.dg/ipa, summing per file counts:
    393 equal symbols, 3112301 text bytes, all three identical
  the existing ICF test set, comparing merge decisions rather than pass counts:
    177 decision lines, byte identical across all three
  400 mutually mergeable functions each carrying nine of those attributes, which
  is the adversarial case for the quadratic comparison:
    Equal symbols: 399 in every configuration, so every pair reaches the
    attribute comparison

WPA link time on the same libstdc++ workload, timing only the link step,
measured round robin across the three compilers over twelve rounds on an
idle machine:

    trunk   min 23.726  median 24.056  mean 24.030  max 24.214  stdev 0.151
    patch   min 23.659  median 24.056  mean 24.021  max 24.180  stdev 0.154
    narrow  min 23.789  median 24.053  mean 24.026  max 24.167  stdev 0.128

Median difference is -0.001 s for this patch and -0.003 s for the narrow
form, against 0.465 s of drift in the machine itself over the twelve
rounds.

The adversarial case for the quadratic comparison is 400 functions with
byte identical bodies each carrying N of those attributes, address taken so
none is removed, which puts all 400 in one congruence class so every pair
reaches the attribute comparison.  N scaled 0, 1, 3, 9, nine being the
largest set of those attributes simultaneously legal on one signature, so
an 81 to 1 ratio in the quadratic term.  Seven rounds per scale, medians in
seconds:

    attrs   trunk      patch      narrow   patch-trunk
        0   0.585      0.601      0.604        +0.016
        1   0.612      0.609      0.615        -0.003
        3   0.537      0.539      0.534        +0.002
        9   0.537      0.532      0.535        -0.005

The delta does not grow with the attribute count, and the spread across the
28 trunk samples alone is 0.101 s, six times the largest delta.

The patch does not block merging that should happen.  Two static member
functions, which have FUNCTION_TYPE, still merge; two member functions of
the same class and two virtual functions, both METHOD_TYPE, still merge;
and two functions carrying the same attributes in the opposite order still
merge, since attribute_list_equal is order insensitive by construction.
Each of those is a testcase, not an assertion.

Testing, on aarch64-unknown-linux-gnu at trunk 8df013222df: patched and
unpatched from the same tree in the same environment, with only ipa-icf.cc
differing, three stage bootstrap configured --enable-languages=c,c++,lto
--enable-checking=yes,rtl,extra --disable-multilib --disable-nls
--disable-libsanitizer, make compare reported comparison successful.  Shard
sums merged with contrib/dg-extract-results.sh and compared with
contrib/compare_tests:

    gcc         399733 pass, 19 fail  ->  399737 pass, 15 fail
    g++         466938 pass,  8 fail  ->  467042 pass,  0 fail
    gcc.dg/lto    1867 pass,  2 fail  ->    1869 pass,  0 fail
    g++.dg/lto    1747 pass,  2 fail  ->    1749 pass,  0 fail
    libstdc++    18889 pass, 14 fail  ->   18889 pass, 14 fail
    libgomp       6315 pass,  0 fail  ->    6315 pass,  0 fail
    libitm          44 pass,  0 fail  ->      44 pass,  0 fail
    libatomic       54 pass,  0 fail  ->      54 pass,  0 fail

Unresolved, error and xpass are 0 everywhere before and after, and
compare_tests reports no "Tests that now fail, but worked before" section
for any comparison. Across the four runtime libraries every result line is
identical, 26919 of them, same md5 sorted; the 14 libstdc++ failures are
pre-existing mdspan dg-error line mismatches present in both runs.  The 12
tests that change from fail to pass are this patch's own; the 15 that
remain are pre-existing, mostly aarch64 SVE scan-assembler and vectoriser
dump scans.  The g++ comparison also reports 96 new and 96 disappeared
tests, all g++.dg/modules, whose dejagnu names embed a generated gcm.cache
path; that suite run twice against one unchanged compiler differs by 27 new
and 42 disappeared, so the churn carries no information.  The testsuite
rerun with the bootstrapped compiler itself gives the same 15 failures.

The tests.  gcc.dg/ipa/pr123227.c and g++.dg/ipa/pr123227.C cover the
non-LTO path; gcc.dg/lto/pr123227_{0,1}.c and g++.dg/lto/pr123227_{0,1}.C
are dg-lto-do run tests that exercise the WPA path this patch guards.  Each
asserts both that no merge was materialised, scan-ipa-dump-not "Unified",
and that ICF found no equal pair, scan-ipa-dump "Equal symbols: 0", using
the scan-wpa-ipa-dump forms in the LTO tests; neither assertion depends on
which form of the fix is applied. In the LTO tests the two functions live
in different translation units and both are called, so both survive to WPA.
On unpatched trunk the WPA dump reports Equal symbols: 1 and "Unified;
Function alias has been created." and the program segfaults; with the patch
it reports 0, prints no Unified line, and exits 0. All four tests fail
before the patch and pass after, 18 FAIL to 0 FAIL, on trunk and on each of
the four release branches.

Branch applicability.  This is a wrong-code regression affecting 13, 14,
15, 16 and 17.  The patch applies cleanly to trunk and to the gcc-16,
gcc-15, gcc-14 and gcc-13 branches.  I built each of the four branches
unpatched, ran the four testcases, applied only the gcc/ipa-icf.cc hunk,
rebuilt in place and reran them:

    releases/gcc-16  38b61f4fee1e   12 fail 10 pass  ->  0 fail 22 pass
    releases/gcc-15  ca85bd3e8a1f   12 fail 10 pass  ->  0 fail 22 pass
    releases/gcc-14  b0a1bcacd1c1   14 fail 11 pass  ->  0 fail 25 pass
    releases/gcc-13  0a4ef247dd72   14 fail 11 pass  ->  0 fail 25 pass

The differing line counts are the number of -std variants each branch's g++
harness runs.  I have left the backport decision to the maintainers.

OK for trunk?

 gcc/ipa-icf.cc                        | 16 +++++++--
 gcc/testsuite/g++.dg/ipa/pr123227.C   | 50 ++++++++++++++++++++++++++
 gcc/testsuite/g++.dg/lto/pr123227_0.C | 52 +++++++++++++++++++++++++++
 gcc/testsuite/g++.dg/lto/pr123227_1.C | 24 +++++++++++++
 gcc/testsuite/gcc.dg/ipa/pr123227.c   | 45 +++++++++++++++++++++++
 gcc/testsuite/gcc.dg/lto/pr123227_0.c | 47 ++++++++++++++++++++++++
 gcc/testsuite/gcc.dg/lto/pr123227_1.c | 17 +++++++++
 7 files changed, 248 insertions(+), 3 deletions(-)
 create mode 100644 gcc/testsuite/g++.dg/ipa/pr123227.C
 create mode 100644 gcc/testsuite/g++.dg/lto/pr123227_0.C
 create mode 100644 gcc/testsuite/g++.dg/lto/pr123227_1.C
 create mode 100644 gcc/testsuite/gcc.dg/ipa/pr123227.c
 create mode 100644 gcc/testsuite/gcc.dg/lto/pr123227_0.c
 create mode 100644 gcc/testsuite/gcc.dg/lto/pr123227_1.c

diff --git a/gcc/ipa-icf.cc b/gcc/ipa-icf.cc
index 44501ec760e..64cc722bd7a 100644
--- a/gcc/ipa-icf.cc
+++ b/gcc/ipa-icf.cc
@@ -659,10 +659,20 @@ sem_function::equals_wpa (sem_item *item,
     return return_false_with_msg ("different number of references");
 
   /* Checking function attributes.
-     This is quadratic in number of attributes  */
-  if (comp_type_attributes (TREE_TYPE (decl),
-			    TREE_TYPE (item->decl)) != 1)
+     This is quadratic in number of attributes.
+     comp_type_attributes only considers attributes that affect type
+     identity, but an attribute that leaves the type alone can still let
+     the body assume something, nonnull being one, so compare the lists
+     the same way the decl attributes are compared below.  */
+  if (!attribute_list_equal (TYPE_ATTRIBUTES (TREE_TYPE (decl)),
+			     TYPE_ATTRIBUTES (TREE_TYPE (item->decl))))
     return return_false_with_msg ("different type attributes");
+  /* A METHOD_TYPE promises a nonnull this pointer without carrying an
+     attribute that says so, so it is not interchangeable with a
+     FUNCTION_TYPE that makes no such promise.  */
+  if ((TREE_CODE (TREE_TYPE (decl)) == METHOD_TYPE)
+      != (TREE_CODE (TREE_TYPE (item->decl)) == METHOD_TYPE))
+    return return_false_with_msg ("METHOD_TYPE and FUNCTION_TYPE mismatch");
   if (!attribute_list_equal (DECL_ATTRIBUTES (decl),
 			     DECL_ATTRIBUTES (item->decl)))
     return return_false_with_msg ("different decl attributes");
diff --git a/gcc/testsuite/g++.dg/ipa/pr123227.C b/gcc/testsuite/g++.dg/ipa/pr123227.C
new file mode 100644
index 00000000000..180792ba247
--- /dev/null
+++ b/gcc/testsuite/g++.dg/ipa/pr123227.C
@@ -0,0 +1,50 @@
+// PR ipa/123227
+// { dg-do run }
+// { dg-options "-Os -fipa-icf -fdump-ipa-icf-details" }
+
+// Link::get_vals and get_vals have identical bodies, but the member
+// function may assume a non-null this while the free function must accept
+// a null argument, so ICF must not unify them.
+
+enum Val { zero = 0 };
+
+inline Val&
+operator|=(Val& a, Val b)
+{
+    return a = static_cast<Val>(static_cast<int>(a) | static_cast<int>(b));
+}
+
+struct Link {
+    Val get_vals();
+    Val val;
+    Link* next;
+};
+
+Val
+Link::get_vals()
+{
+    Val v = zero;
+    for (Link* l = this; l; l = l->next)
+        v |= l->val;
+    return v;
+}
+
+Val
+get_vals(Link* l)
+{
+    Val v = zero;
+    for (; l; l = l->next)
+        v |= l->val;
+    return v;
+}
+
+int
+main(int, char**)
+{
+    if (get_vals(0) != zero)
+        __builtin_abort();
+    return 0;
+}
+
+// { dg-final { scan-ipa-dump-not "Unified" "icf" } }
+// { dg-final { scan-ipa-dump "Equal symbols: 0" "icf" } }
diff --git a/gcc/testsuite/g++.dg/lto/pr123227_0.C b/gcc/testsuite/g++.dg/lto/pr123227_0.C
new file mode 100644
index 00000000000..2072c598102
--- /dev/null
+++ b/gcc/testsuite/g++.dg/lto/pr123227_0.C
@@ -0,0 +1,52 @@
+// PR ipa/123227
+// { dg-lto-do run }
+// { dg-lto-options {{-Os -flto -fipa-icf -fdump-ipa-icf-details}} }
+
+// Link::get_vals and get_vals have identical bodies, but the member
+// function may assume a non-null this while the free function must accept
+// a null argument, so ICF must not unify them at WPA.  Both are called so
+// that neither is removed before ICF runs, and both are noinline so that
+// the calls survive as calls.
+
+enum Val { zero = 0 };
+
+inline Val&
+operator|=(Val& a, Val b)
+{
+    return a = static_cast<Val>(static_cast<int>(a) | static_cast<int>(b));
+}
+
+struct Link {
+    Val get_vals();
+    Val val;
+    Link* next;
+};
+
+Val __attribute__((noinline))
+Link::get_vals()
+{
+    Val v = zero;
+    for (Link* l = this; l; l = l->next)
+        v |= l->val;
+    return v;
+}
+
+extern Val get_vals(Link* l);
+
+static Link one = { Val(5), 0 };
+
+// Volatile so that the null argument is not propagated into get_vals.
+Link *volatile nullp = 0;
+
+int
+main()
+{
+    if (one.get_vals() != Val(5))
+        __builtin_abort();
+    if (get_vals(nullp) != zero)
+        __builtin_abort();
+    return 0;
+}
+
+// { dg-final { scan-wpa-ipa-dump-not "Unified" "icf" } }
+// { dg-final { scan-wpa-ipa-dump "Equal symbols: 0" "icf" } }
diff --git a/gcc/testsuite/g++.dg/lto/pr123227_1.C b/gcc/testsuite/g++.dg/lto/pr123227_1.C
new file mode 100644
index 00000000000..bc2a7aa168d
--- /dev/null
+++ b/gcc/testsuite/g++.dg/lto/pr123227_1.C
@@ -0,0 +1,24 @@
+// PR ipa/123227
+
+enum Val { zero = 0 };
+
+inline Val&
+operator|=(Val& a, Val b)
+{
+    return a = static_cast<Val>(static_cast<int>(a) | static_cast<int>(b));
+}
+
+struct Link {
+    Val get_vals();
+    Val val;
+    Link* next;
+};
+
+Val __attribute__((noinline))
+get_vals(Link* l)
+{
+    Val v = zero;
+    for (; l; l = l->next)
+        v |= l->val;
+    return v;
+}
diff --git a/gcc/testsuite/gcc.dg/ipa/pr123227.c b/gcc/testsuite/gcc.dg/ipa/pr123227.c
new file mode 100644
index 00000000000..e1942350819
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/ipa/pr123227.c
@@ -0,0 +1,45 @@
+/* PR ipa/123227 */
+/* { dg-do run } */
+/* { dg-options "-Os -fipa-icf -fdump-ipa-icf-details" } */
+
+/* The two functions have identical bodies but only one promises a non-null
+   argument, so ICF must not unify them: the surviving body is allowed to
+   drop the null test that the other one needs.  */
+
+typedef struct Link Link;
+struct Link
+{
+  int val;
+  Link *next;
+};
+
+int get_vals_nonnull (Link *) __attribute__((nonnull (1)));
+
+int
+get_vals_nonnull (Link *l)
+{
+  int v = 0;
+  for (; l; l = l->next)
+    v |= l->val;
+  return v;
+}
+
+int
+get_vals (Link *l)
+{
+  int v = 0;
+  for (; l; l = l->next)
+    v |= l->val;
+  return v;
+}
+
+int
+main (void)
+{
+  if (get_vals ((Link *) 0) != 0)
+    __builtin_abort ();
+  return 0;
+}
+
+/* { dg-final { scan-ipa-dump-not "Unified" "icf" } } */
+/* { dg-final { scan-ipa-dump "Equal symbols: 0" "icf" } } */
diff --git a/gcc/testsuite/gcc.dg/lto/pr123227_0.c b/gcc/testsuite/gcc.dg/lto/pr123227_0.c
new file mode 100644
index 00000000000..60f2d730305
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/lto/pr123227_0.c
@@ -0,0 +1,47 @@
+/* PR ipa/123227 */
+/* { dg-lto-do run } */
+/* { dg-lto-options {{-Os -flto -fipa-icf -fdump-ipa-icf-details}} } */
+
+/* get_vals_nonnull and get_vals have identical bodies but only one
+   promises a non-null argument, so ICF must not unify them at WPA: the
+   surviving body is allowed to drop the null test the other one needs.
+   Both are called so that neither is removed before ICF runs, and both
+   are noinline so that the calls survive as calls.  */
+
+typedef struct Link Link;
+struct Link
+{
+  int val;
+  Link *next;
+};
+
+int get_vals_nonnull (Link *) __attribute__((nonnull (1)));
+
+int __attribute__((noinline))
+get_vals_nonnull (Link *l)
+{
+  int v = 0;
+  for (; l; l = l->next)
+    v |= l->val;
+  return v;
+}
+
+extern int get_vals (Link *);
+
+static Link one = { 5, 0 };
+
+/* Volatile so that the null argument is not propagated into get_vals.  */
+Link *volatile nullp = 0;
+
+int
+main (void)
+{
+  if (get_vals_nonnull (&one) != 5)
+    __builtin_abort ();
+  if (get_vals (nullp) != 0)
+    __builtin_abort ();
+  return 0;
+}
+
+/* { dg-final { scan-wpa-ipa-dump-not "Unified" "icf" } } */
+/* { dg-final { scan-wpa-ipa-dump "Equal symbols: 0" "icf" } } */
diff --git a/gcc/testsuite/gcc.dg/lto/pr123227_1.c b/gcc/testsuite/gcc.dg/lto/pr123227_1.c
new file mode 100644
index 00000000000..677f59a918c
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/lto/pr123227_1.c
@@ -0,0 +1,17 @@
+/* PR ipa/123227 */
+
+typedef struct Link Link;
+struct Link
+{
+  int val;
+  Link *next;
+};
+
+int __attribute__((noinline))
+get_vals (Link *l)
+{
+  int v = 0;
+  for (; l; l = l->next)
+    v |= l->val;
+  return v;
+}
-- 
2.53.0