[Bug middle-end/107661] New: [13 Regression] lambdas get merged incorrectly in tempaltes, cause llvm-12 miscompilation

[Bug middle-end/107661] New: [13 Regression] lambdas get merged incorrectly in tempaltes, cause llvm-12 miscompilation

[slyfox at gcc dot gnu.org]

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

            Bug ID: 107661
           Summary: [13 Regression] lambdas get merged incorrectly in
                    tempaltes, cause llvm-12 miscompilation
           Product: gcc
           Version: 13.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: middle-end
          Assignee: unassigned at gcc dot gnu.org
          Reporter: slyfox at gcc dot gnu.org
  Target Milestone: ---

Created attachment 53888
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=53888&action=edit
a.cc

Initially observed the problem on llvm-12's test suite where 4 AMDGCN test
fail:

    Failed Tests (4):
      LLVM :: CodeGen/AMDGPU/GlobalISel/llvm.amdgcn.div.fmas.ll
      LLVM :: CodeGen/AMDGPU/atomic_optimizations_pixelshader.ll
      LLVM :: CodeGen/AMDGPU/smem-war-hazard.mir
      LLVM :: CodeGen/AMDGPU/vgpr-descriptor-waterfall-loop-idom-update.ll

Digging deeper it looks liek llvm's class

    template<typename Ret, typename ...Params> class
function_ref<Ret(Params...)> ...

gets miscompiled in a very unusual way. I extracted smaller a.cc reproducer.

It looks like as if gcc picked wrong (unused) lambda to inline into actually
used code.

Reproducing:

$ ./gcc-13-HEAD/bin/gcc -Wall -O0 a.cc -o a
$ ./gcc-13-HEAD/bin/gcc -Wall -O3 a.cc -o a
./bug_HEAD.bash: line 6: 1309437 Illegal instruction     (core dumped) ./a
$ ./gcc-13-HEAD/bin/gcc -Wall -O0 -DDISABLE_HACK a.cc -o a
$ ./gcc-13-HEAD/bin/gcc -Wall -O3 -DDISABLE_HACK a.cc -o a

$ ./gcc-13-HEAD/bin/gcc -v |& unnix
Using built-in specs.
COLLECT_GCC=/<<NIX>>/gcc-13.0.0/bin/gcc
COLLECT_LTO_WRAPPER=/<<NIX>>/gcc-13.0.0/libexec/gcc/x86_64-unknown-linux-gnu/13.0.0/lto-wrapper
Target: x86_64-unknown-linux-gnu
Configured with:
Thread model: posix
Supported LTO compression algorithms: zlib
gcc version 13.0.0 20221112 (experimental) (GCC)

Full a.cc example (somewhat long, also attached):

/// 'function_ref' is taken from llvm-12 as is without any modifications.
/// The rest if severely maimed AMDGCN hasard verifier code.

// How to break:
// $ ./gcc-13-snap/bin/gcc -O3                a.cc -o a && ./a
// Illegal instruction (core dumped)
// $ ./gcc-13-snap/bin/gcc -O3 -DDISABLE_HACK a.cc -o a && ./a
// <ok>

#pragma GCC optimize "-O1"
#pragma GCC optimize "-fipa-cp"
#pragma GCC optimize "-fipa-cp-clone"

// #define DISABLE_HACK 1

#include <cstdint>
#include <limits>
#include <type_traits>
#include <utility>

/// An efficient, type-erasing, non-owning reference to a callable. This is
/// intended for use as the type of a function parameter that is not used
/// after the function in question returns.
///
/// This class does not own the callable, so it is not in general safe to store
/// a function_ref.
template<typename Fn> class function_ref;

template<typename Ret, typename ...Params>
class function_ref<Ret(Params...)> {
  Ret (*callback)(intptr_t callable, Params ...params) = nullptr;
  intptr_t callable;

  template<typename Callable>
  //__attribute__((noinline, noipa))
  static Ret callback_fn(intptr_t callable, Params ...params) {
    return (*reinterpret_cast<Callable*>(callable))(
        std::forward<Params>(params)...);
  }

public:
  __attribute__((noinline, noipa))
  function_ref() = default;
  __attribute__((noinline, noipa))
  function_ref(std::nullptr_t) {}

  template <typename Callable>
  //__attribute__((noinline, noipa))
  function_ref(
      Callable &&callable,
      // This is not the copy-constructor.
      std::enable_if_t<
          !std::is_same<std::remove_cv_t<std::remove_reference_t<Callable>>,
                        function_ref>::value> * = nullptr,
      // Functor must be callable and return a suitable type.
      std::enable_if_t<std::is_void<Ret>::value ||
                       std::is_convertible<decltype(std::declval<Callable>()(
                                               std::declval<Params>()...)),
                                           Ret>::value> * = nullptr)
      : callback(callback_fn<typename std::remove_reference<Callable>::type>),
        callable(reinterpret_cast<intptr_t>(&callable)) {}

  //__attribute__((noinline, noipa))
  Ret operator()(Params ...params) const {
    return callback(callable, std::forward<Params>(params)...);
  }

  __attribute__((noinline, noipa))
  explicit operator bool() const { return callback; }
};

typedef int OI;
typedef int OBB;

typedef function_ref<bool(OI, int WaitStates)> IsExpiredFnT;
typedef function_ref<bool(OI)> IsHazardFnT;

__attribute__((noinline, noipa)) OI get_e(
    OBB MBB,
    OI I) {
    static int n = 0;
    switch (n++) {
      case 0: return I;
      case 1: return ++I;
      default: return I;
    }
}

__attribute__((noinline, noipa))
static OBB get_mbb_b(OBB MBB) {
    return MBB;
}

__attribute__((noinline, noipa))
static OBB get_mbb_e(OBB MBB) {
    static int n = 0;
    switch (n++) {
      case 0: return MBB + 1;
      default: return MBB;
    }
}

__attribute__((noinline))
static int getWaitStatesSince6(IsHazardFnT IsHazard, OBB MBB, OI I, int
WaitStates, IsExpiredFnT IsExpired) {

  auto E = get_e(MBB, I);
  if (I != E) {
    WaitStates += 2;

    if (IsExpired(I, WaitStates))
      return std::numeric_limits<int>::max();
  }

  auto pri = get_mbb_b(MBB);
  auto pre = get_mbb_e(MBB);
  if (pri != pre) {
    OBB Pred = pri;
    getWaitStatesSince6(IsHazard, Pred, I,
                        WaitStates, IsExpired);
  }

  return std::numeric_limits<int>::max();
}

__attribute__((noinline)) // not a noclone
static int getWaitStatesSince3(IsHazardFnT IsHazard, OI MI, IsExpiredFnT
IsExpired) {
  return getWaitStatesSince6(IsHazard, 0, MI, 0, IsExpired);
}

__attribute__((noinline, noipa))
bool bug(OI MI) {
  auto IsHazardFn = [](OI I) __attribute__((noinline, noipa)) { return false;
};

  auto IsExpiredFn = [](OI MI, int) __attribute__((noinline, noipa)) { return
true; };

  ::getWaitStatesSince3(IsHazardFn, MI, IsExpiredFn);

  return true;
}

__attribute__((noinline, noipa))
int main() { bug(0); }

#if defined(DISABLE_HACK)
#else
__attribute__((noinline, noipa))
int seemingly_unused_foo(IsHazardFnT IsHazard, int Limit, OI MI) {
  auto IsExpiredFn = [Limit] (OI, int WaitStates)
  {
    __builtin_trap();
    return WaitStates >= Limit;
  };
  return ::getWaitStatesSince3(IsHazard, MI, IsExpiredFn);
}
#endif

[Bug middle-end/107661] [13 Regression] lambdas get merged incorrectly in tempaltes, cause llvm-12 miscompilation

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |13.0
           Severity|normal                      |blocker

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
IPA-CP didn't change in 13 as far as I know but lambda mangling did.

[Bug middle-end/107661] [13 Regression] lambdas get merged incorrectly in tempaltes, cause llvm-12 miscompilation

[slyfox at gcc dot gnu.org]

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

--- Comment #2 from Sergei Trofimovich <slyfox at gcc dot gnu.org> ---
(In reply to Sergei Trofimovich from comment #0)
> Reproducing:
> 
> $ ./gcc-13-HEAD/bin/gcc -Wall -O0 a.cc -o a
> $ ./gcc-13-HEAD/bin/gcc -Wall -O3 a.cc -o a
> ./bug_HEAD.bash: line 6: 1309437 Illegal instruction     (core dumped) ./a
> $ ./gcc-13-HEAD/bin/gcc -Wall -O0 -DDISABLE_HACK a.cc -o a
> $ ./gcc-13-HEAD/bin/gcc -Wall -O3 -DDISABLE_HACK a.cc -o a

Whoops. Lines miss `&& ./a` execution. The correct reproducer (it's a runtime
crash):

$ ./gcc-13-HEAD/bin/gcc -Wall -O3 a.cc -o a && ./a
Illegal instruction (core dumped)

For comparison the other modes are fine:

# remove seemingly unused code with __builtin_trap from visibility:
$ ./gcc-13-HEAD/bin/gcc -Wall -O3 a.cc -o a -DDISABLE_HACK && ./a
<ok>

[Bug middle-end/107661] [13 Regression] lambdas get merged incorrectly in tempaltes, cause llvm-12 miscompilation

[slyfox at gcc dot gnu.org]

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

--- Comment #3 from Sergei Trofimovich <slyfox at gcc dot gnu.org> ---
Created attachment 53889
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=53889&action=edit
a_simpler.cc

a_simpler.cc is a bit more trimmed down version of a.cc: does not need pragmas
or argument forwarding. Uses only -O1 -fipa-cp -fipa-cp-clone:

$ ./gcc-13-HEAD/bin/gcc -Wall -O1 -fipa-cp -fipa-cp-clone -DDISABLE_HACK
a_simpler.cc -o a && ./a
$ ./gcc-13-HEAD/bin/gcc -Wall -O1 -fipa-cp -fipa-cp-clone a_simpler.cc -o a &&
./a
Illegal instruction (core dumped)

/// 'function_ref' is taken from llvm-12 as is without any modifications.
/// The rest if severely maimed AMDGCN hazard verifier code.

// How to break:
// $ ./gcc-13-snap/bin/gcc -O1 -fipa-cp -fipa-cp-clone               
a_simpler.cc -o a && ./a
// Illegal instruction (core dumped)
// $ ./gcc-13-snap/bin/gcc -O1 -fipa-cp -fipa-cp-clone -DDISABLE_HACK
a_simpler.cc -o a && ./a
// <ok>

// #define DISABLE_HACK 1

#include <utility>

class function_ref {
  void (*callback)(void * callable) = nullptr;
  void * callable;

  template<typename Callable>
  static void callback_fn(void * callable) {
    (*reinterpret_cast<Callable*>(callable))();
  }

public:
  function_ref() = delete;

  template <typename Callable>
  function_ref(
      Callable &&callable,
      // This is not the copy-constructor.
      std::enable_if_t<
          !std::is_same<std::remove_cv_t<std::remove_reference_t<Callable>>,
                        function_ref>::value> * = nullptr)
      : callback(callback_fn<typename std::remove_reference<Callable>::type>),
        callable(reinterpret_cast<void*>(&callable)) {}

  void operator()(void) const {
    callback(callable);
  }
};

static int get_mbb_b(int MBB) { return MBB; }
static int get_mbb_e(int MBB) {
    static int n = 0;
    switch (n++) {
      case 0: return MBB + 1;
      default: return MBB;
    }
}

static void getWaitStatesSince6(int MBB, int I, int WaitStates, function_ref
Expired) {
  Expired();

  if (I) {
    WaitStates += 1;
  }

  auto pri = get_mbb_b(MBB);
  auto pre = get_mbb_e(MBB);
  if (pri != pre) {
    getWaitStatesSince6(pri, I, WaitStates, Expired);
  }
}

static void getWaitStatesSince3(int MI, function_ref Expired) {
  getWaitStatesSince6(0, MI, 42, Expired);
}

static void always_void(void) { }

int main() {
  getWaitStatesSince3(0, always_void);
}

#if defined(DISABLE_HACK)
#else
void seemingly_unused_foo(int MI) {
  struct L {
    void operator()(void) const {
      __builtin_trap();
    }
  };
  L IsExpiredFn;

  getWaitStatesSince3(MI, IsExpiredFn);
}
#endif

[Bug middle-end/107661] [13 Regression] lambdas get merged incorrectly in tempaltes, cause llvm-12 miscompilation

[slyfox at gcc dot gnu.org]

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

--- Comment #4 from Sergei Trofimovich <slyfox at gcc dot gnu.org> ---
If I read a.cc.254t.optimized correctly I think there are two unrelated places
that are expected to generate `getWaitStatesSince6.constprop`:
- one is through main()
- another is through seemingly_unused_foo()

They have slightly different parameters, but gcc uses seemingly_unused_foo()'s
one in main()'s path and as a result calls code from normally unreachable
lambda.

[Bug middle-end/107661] [13 Regression] lambdas get merged incorrectly in tempaltes, cause llvm-12 miscompilation since r13-3358-ge0403e95689af7

[slyfox at gcc dot gnu.org]

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

Sergei Trofimovich <slyfox at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[13 Regression] lambdas get |[13 Regression] lambdas get
                   |merged incorrectly in       |merged incorrectly in
                   |tempaltes, cause llvm-12    |tempaltes, cause llvm-12
                   |miscompilation              |miscompilation since
                   |                            |r13-3358-ge0403e95689af7

--- Comment #5 from Sergei Trofimovich <slyfox at gcc dot gnu.org> ---
Bisected down to r13-3358-ge0403e95689af7 (looks very relevant):

commit e0403e95689af7d562c7d04f706e9e25115747ff
Author: Martin Jambor <mjambor@suse.cz>
Date:   Tue Oct 18 14:14:26 2022 +0200

    ipa-cp: Better representation of aggregate values we clone for

    This patch replaces linked lists of ipa_agg_replacement_value with
    vectors of similar structures called ipa_argagg_value and simplifies
    how we compute them in the first place.  Having a vector should also
    result in less overhead when allocating and because we keep it sorted,
    it leads to logarithmic searches.

    The slightly obnoxious "argagg" bit in the name can be changed into
    "agg" after the next patch removes our current ipa_agg_value type.

    The patch also introduces type ipa_argagg_value_list which serves as a
    common view into a vector of ipa_argagg_value structures regardless
    whether they are stored in GC memory (required for IPA-CP
    transformation summary because we store trees) or in an auto_vec which
    is hopefully usually only allocated on stack.

    The calculation of aggreagete costant values for a given subsert of
    callers is then rewritten to compute known constants for each
    edge (some pruning to skip obviously not needed is still employed and
    should not be really worse than what I am replacing) and these vectors
    are there intersected, which can be done linearly since they are
    sorted.  The patch also removes a lot of heap allocations of small
    lists of aggregate values and replaces them with stack based
    auto_vecs.

    As Richard Sandiford suggested, I use std::lower_bound from
    <algorithm> rather than re-implementing bsearch for array_slice.  The
    patch depends on the patch which adds the ability to construct
    array_slices from gc-allocated vectors.

[Bug middle-end/107661] [13 Regression] lambdas get merged incorrectly in tempaltes, cause llvm-12 miscompilation since r13-3358-ge0403e95689af7

[jamborm at gcc dot gnu.org]

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

Martin Jambor <jamborm at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |ASSIGNED
     Ever confirmed|0                           |1
           Assignee|unassigned at gcc dot gnu.org      |jamborm at gcc dot gnu.org
   Last reconfirmed|                            |2022-11-13

--- Comment #6 from Martin Jambor <jamborm at gcc dot gnu.org> ---
Interesting, I'll have a look.

[Bug middle-end/107661] [13 Regression] lambdas get merged incorrectly in tempaltes, cause llvm-12 miscompilation since r13-3358-ge0403e95689af7

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P1

[Bug middle-end/107661] [13 Regression] lambdas get merged incorrectly in tempaltes, cause llvm-12 miscompilation since r13-3358-ge0403e95689af7

[slyfox at gcc dot gnu.org]

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

--- Comment #7 from Sergei Trofimovich <slyfox at gcc dot gnu.org> ---
Looking -fdump-ipa-cp-all I see the following clone

```
IPA decision stage:


Evaluating opportunities for static void function_ref::callback_fn(void*) [with
Callable = seemingly_unused_foo(int)::L]/30.

Evaluating opportunities for static void function_ref::callback_fn(void*) [with
Callable = void()]/29.

Evaluating opportunities for void getWaitStatesSince3(int, function_ref)/18.
 - considering value callback_fn for param #1 Expired, offset: 0 (caller_count:
1)
     good_cloning_opportunity_p (time: 33, size: 37, freq_sum: 1) ->
evaluation: 891.89, threshold: 500
  Creating a specialized node of void getWaitStatesSince3(int,
function_ref)/18.
                Accounting size:5.00, time:14.00 on predicate exec:(true)
     the new node is void getWaitStatesSince3.constprop(int, function_ref)/33.
     Aggregate replacements: 1[0]=callback_fn
     overall size reached 88

Evaluating opportunities for void getWaitStatesSince6(int, int, int,
function_ref)/17.
 - considering value 0 for param #0 MBB (caller_count: 2)
     good_cloning_opportunity_p (time: 1, size: 21, freq_sum: 2, self_scc,
single_call) -> evaluation: 80.95, threshold: 500
     good_cloning_opportunity_p (time: 1, size: 21, freq_sum: 2, self_scc,
single_call) -> evaluation: 80.95, threshold: 500
 - considering value 42 for param #2 WaitStates (caller_count: 2)
     good_cloning_opportunity_p (time: 1.5, size: 20, freq_sum: 2, self_scc,
single_call) -> evaluation: 127.50, threshold: 500
     good_cloning_opportunity_p (time: 1.5, size: 20, freq_sum: 2, self_scc,
single_call) -> evaluation: 127.50, threshold: 500
 - considering value callback_fn for param #3 Expired, offset: 0 (caller_count:
2)
     good_cloning_opportunity_p (time: 33, size: 29, freq_sum: 1.4888,
self_scc, single_call) -> evaluation: 1440.03, threshold: 500
  Creating a specialized node of void getWaitStatesSince6(int, int, int,
function_ref)/17.
                Accounting size:2.00, time:11.00 on predicate exec:(true)
                Accounting size:3.00, time:12.00 on predicate exec:(true)
                Accounting size:3.00, time:12.00 on predicate exec:(true)
                Accounting size:5.00, time:6.84 on predicate exec:(true)
     the new node is void getWaitStatesSince6.constprop(int, int, int,
function_ref)/34.
     Aggregate replacements: 3[0]=callback_fn
     overall size reached 109

Evaluating opportunities for void getWaitStatesSince6(int, int, int,
function_ref)/17.
 - considering value 0 for param #0 MBB (caller_count: 1)
     good_cloning_opportunity_p (time: 1, size: 21, freq_sum: 1, self_scc,
single_call) -> evaluation: 40.48, threshold: 500
     good_cloning_opportunity_p (time: 1, size: 21, freq_sum: 1, self_scc,
single_call) -> evaluation: 40.48, threshold: 500
 - considering value 42 for param #2 WaitStates (caller_count: 1)
     good_cloning_opportunity_p (time: 1.5, size: 20, freq_sum: 1, self_scc,
single_call) -> evaluation: 63.75, threshold: 500
     good_cloning_opportunity_p (time: 1.5, size: 20, freq_sum: 1, self_scc,
single_call) -> evaluation: 63.75, threshold: 500
 - adding an extra caller void getWaitStatesSince6(int, int, int,
function_ref)/17 of void getWaitStatesSince6.constprop(int, int, int,
function_ref)/34

Evaluating opportunities for void Exec(function_ref)/13.
 - considering value callback_fn for param #0 fr, offset: 0 (caller_count: 1)
     good_cloning_opportunity_p (time: 33, size: 8, freq_sum: 1) -> evaluation:
4125.00, threshold: 500
  Creating a specialized node of void Exec(function_ref)/13.
                Accounting size:4.00, time:16.00 on predicate exec:(true)
     the new node is void Exec.constprop(function_ref)/35.
     Aggregate replacements: 0[0]=callback_fn
ipa-prop: Discovered an indirect call to a known target (void
Exec.constprop(function_ref)/35 -> static void function_ref::callback_fn(void*)
[with Callable = seemingly_unused_foo(int)::L]/30), for stmt _1 (_2);
../a.cc:37:14: optimized: converting indirect call in void
Exec.constprop(function_ref)/35 to direct call to static void
function_ref::callback_fn(void*) [with Callable =
seemingly_unused_foo(int)::L]/30
                Accounting size:2.00, time:11.00 on predicate exec:(true)
     overall size reached 117

Evaluating opportunities for void Exec(function_ref)/13.
Not considering void Exec.constprop(function_ref)/35 for ipa bitwise
propagation ; -fipa-bit-cp: disabled.
...

IPA constant propagation end
```

When debug reports unqualified `Aggregate replacements: 1[0]=callback_fn` does
it mean ipa-cp does not distinguish between:
  * static void function_ref::callback_fn(void*) [with Callable =
seemingly_unused_foo(int)::L]/30.
  * static void function_ref::callback_fn(void*) [with Callable = void()]/29.
?

I suspect it does not and that results in a wrong callback_fn inline.

[Bug middle-end/107661] [13 Regression] lambdas get merged incorrectly in tempaltes, cause llvm-12 miscompilation since r13-3358-ge0403e95689af7

[slyfox at gcc dot gnu.org]

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

--- Comment #8 from Sergei Trofimovich <slyfox at gcc dot gnu.org> ---
(In reply to Sergei Trofimovich from comment #7)
> When debug reports unqualified `Aggregate replacements: 1[0]=callback_fn`
> does it mean ipa-cp does not distinguish between:
>   * static void function_ref::callback_fn(void*) [with Callable =
> seemingly_unused_foo(int)::L]/30.
>   * static void function_ref::callback_fn(void*) [with Callable = void()]/29.
> ?
> 
> I suspect it does not and that results in a wrong callback_fn inline.

That was not it. Identical names is a printing artifact.

I shrunk example a bit more to avoid any overloads and crashes. Now example
just prints different things.

// How to break:
// $ ./gcc-13-snap/bin/gcc -O1 -fipa-cp -fipa-cp-clone                 a.cc -o
a && ./a
// GOOD
// BAD
// $ ./gcc-13-snap/bin/gcc -O1 -fipa-cp -fipa-cp-clone -DDISABLE_HACK a.cc -o a
&& ./a
// GOOD
// GOOD

// #define DISABLE_HACK 1

#include <stdio.h>

struct R {} RGood;
struct L {} LBad;

static void L_run(void) { fprintf(stderr, "BAD\n"); }
static void callback_fn_L(void) { L_run(); }
static void callback_fn_R(void) { fprintf(stderr, "GOOD\n"); }

struct function_ref {
  void (*callback)(void) = nullptr;

  function_ref(L * pl) { callback = callback_fn_L; }
  function_ref(R * pr) { callback = callback_fn_R; }
};

// allow one level of recursion to call callback twice
static int is_recur(void) {
    static int n = 0;
    switch (n++) {
      case 0: return 1;
      default: return 0;
    }
}

static void do3(volatile int * punused, function_ref Expired) {
  Expired.callback();

  if (is_recur())
      do3(punused, Expired);
}

static void do1(function_ref Expired) {
  volatile int unused = 42;

  do3(&unused, Expired);
}

int main(void) { do1(&RGood); }

#if defined(DISABLE_HACK)
#else
void seemingly_unused_foo(void) { do1(&LBad); }
#endif

[Bug middle-end/107661] [13 Regression] lambdas get merged incorrectly in tempaltes, cause llvm-12 miscompilation since r13-3358-ge0403e95689af7

[slyfox at gcc dot gnu.org]

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

Sergei Trofimovich <slyfox at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #53888|0                           |1
        is obsolete|                            |
  Attachment #53889|0                           |1
        is obsolete|                            |

--- Comment #9 from Sergei Trofimovich <slyfox at gcc dot gnu.org> ---
Created attachment 53922
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=53922&action=edit
a_simplest.cc

[Bug middle-end/107661] [13 Regression] lambdas get merged incorrectly in tempaltes, cause llvm-12 miscompilation since r13-3358-ge0403e95689af7

[slyfox at gcc dot gnu.org]

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

--- Comment #10 from Sergei Trofimovich <slyfox at gcc dot gnu.org> ---
I think ipa-cp adds the call edge info in wrong direction. a.cc.081i.cp snippet
around do3() param1 (our callback):

  IPA lattices after all propagation:

  Lattices:
    ...
    Node: void do3(volatile int*, function_ref)/25:
      ...
      param [1]: VARIABLE
           ctxs: VARIABLE
           Bits unusable (BOTTOM)
           [irange] int VARYING
          offset 0: callback_fn_L [scc: 3, from: 25(0.330000) 26(1.000000)]
[loc_time: 17, loc_size: 13, prop_time: 17, prop_size: 13]
                    callback_fn_R [scc: 4, from: 25(0.330000) 26(1.000000)]
[loc_time: 9, loc_size: 13, prop_time: 9, prop_size: 13]

  ...
  Evaluating opportunities for void do3(volatile int*, function_ref)/25.
   - considering value callback_fn_L for param #1 Expired, offset: 0
(caller_count: 2)
       good_cloning_opportunity_p (time: 17, size: 13, freq_sum: 1.33,
self_scc) -> evaluation: 1739.23, threshold: 500
    Creating a specialized node of void do3(volatile int*, function_ref)/25.
       the new node is void do3.constprop(volatile int*, function_ref)/33.
       Aggregate replacements: 1[0]=callback_fn_L
  ipa-prop: Discovered an indirect call to a known target (void
do3.constprop(volatile int*, function_ref)/33 -> void callback_fn_L()/15), for
stmt _1 ();
    ../a.cc:37:19: optimized: converting indirect call in void
do3.constprop(volatile int*, function_ref)/33 to direct call to void
callback_fn_L()/15

    Evaluating opportunities for void do3(volatile int*, function_ref)/25.
     - adding an extra caller void do3(volatile int*, function_ref)/25 of void
do3.constprop(volatile int*, function_ref)/33

Note: the uncloned do3() is a self-recursive function. I would expect cloned
do3.constprop() to refer to uncloned do3().
If I read "adding an extra caller" correctly it adds an edge in wrong
direction: do3() now calls do3.constptop().

[Bug middle-end/107661] [13 Regression] lambdas get merged incorrectly in tempaltes, cause llvm-12 miscompilation since r13-3358-ge0403e95689af7

[slyfox at gcc dot gnu.org]

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

--- Comment #11 from Sergei Trofimovich <slyfox at gcc dot gnu.org> ---
I think I found the bug: r13-3358-ge0403e95689af7
cgraph_edge_brings_all_agg_vals_for_node() accidentally changed behaviour of
the predicate:

- before the change: ipa-cp triggers when constrop contains all possible edges
aggregates (ok).
- after the change: ipa-cp triggers when constrop contains a subset(!) of
possible edges aggregates (bad, redirects invalid values sometimes).

Thus substitution of do3()->do3.constprop() redirects to the wrong target.

Sounds plausible?

[Bug middle-end/107661] [13 Regression] lambdas get merged incorrectly in tempaltes, cause llvm-12 miscompilation since r13-3358-ge0403e95689af7

[slyfox at gcc dot gnu.org]

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

--- Comment #12 from Sergei Trofimovich <slyfox at gcc dot gnu.org> ---
Testing the following:

--- a/gcc/ipa-cp.cc
+++ b/gcc/ipa-cp.cc
@@ -5869,37 +5869,37 @@ cgraph_edge_brings_all_scalars_for_node (struct
cgraph_edge *cs,
 /* Determine whether CS also brings all aggregate values that NODE is
    specialized for.  */

 static bool
 cgraph_edge_brings_all_agg_vals_for_node (struct cgraph_edge *cs,
                                          struct cgraph_node *node)
 {
   ipcp_transformation *ts = ipcp_get_transformation_summary (node);
   if (!ts || vec_safe_is_empty (ts->m_agg_values))
     return true;

   const ipa_argagg_value_list existing (ts->m_agg_values);
   auto_vec<ipa_argagg_value, 32> edge_values;
   ipa_node_params *dest_info = ipa_node_params_sum->get (node);
   gcc_checking_assert (dest_info->ipcp_orig_node);
   dest_info = ipa_node_params_sum->get (dest_info->ipcp_orig_node);
   push_agg_values_from_edge (cs, dest_info, &edge_values, &existing);
   const ipa_argagg_value_list avl (&edge_values);
-  return avl.superset_of_p (existing);
+  return existing.superset_of_p (avl);
 }

[Bug middle-end/107661] [13 Regression] lambdas get merged incorrectly in tempaltes, cause llvm-12 miscompilation since r13-3358-ge0403e95689af7

[slyfox at gcc dot gnu.org]

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

--- Comment #13 from Sergei Trofimovich <slyfox at gcc dot gnu.org> ---
(In reply to Sergei Trofimovich from comment #12)
> Testing the following:
> 
> --- a/gcc/ipa-cp.cc
> +++ b/gcc/ipa-cp.cc
> @@ -5869,37 +5869,37 @@ cgraph_edge_brings_all_scalars_for_node (struct
> cgraph_edge *cs,
>  /* Determine whether CS also brings all aggregate values that NODE is
>     specialized for.  */
> 
>  static bool
>  cgraph_edge_brings_all_agg_vals_for_node (struct cgraph_edge *cs,
>                                           struct cgraph_node *node)
>  {
>    ipcp_transformation *ts = ipcp_get_transformation_summary (node);
>    if (!ts || vec_safe_is_empty (ts->m_agg_values))
>      return true;
> 
>    const ipa_argagg_value_list existing (ts->m_agg_values);
>    auto_vec<ipa_argagg_value, 32> edge_values;
>    ipa_node_params *dest_info = ipa_node_params_sum->get (node);
>    gcc_checking_assert (dest_info->ipcp_orig_node);
>    dest_info = ipa_node_params_sum->get (dest_info->ipcp_orig_node);
>    push_agg_values_from_edge (cs, dest_info, &edge_values, &existing);
>    const ipa_argagg_value_list avl (&edge_values);
> -  return avl.superset_of_p (existing);
> +  return existing.superset_of_p (avl);
>  }

It was not enough.

What I expected:
- avl contains: callback_fn_L and callback_fn_R
- existing contains: callback_fn_L

What I get:
- avl contains: callback_fn_L
- existing contains: callback_fn_L

It seems to have something to do with
push_agg_values_from_edge()/push_agg_values_for_index_from_edge() behaviour of
filtering self-recursive lattice values:

      if (interim && self_recursive_pass_through_p (cs, jfunc, index))
        {
          interim->push_adjusted_values (src_idx, index, unit_delta,
                                         res);
          return;
        }

Here we seem to ignore lattice values discovered on the edges and only copy
already encountered values. But we only populate 'interim' with values we
specialised the self-recursive call against:

  push_agg_values_from_edge (cs, dest_info, &edge_values, &existing);

('existing' variable is populated by values caller uses in one location).


The following hack seems to fix the test case for me but I suspect it just
breaks any self-recursive propagation:

--- a/gcc/ipa-cp.cc
+++ b/gcc/ipa-cp.cc
@@ -5868,35 +5868,35 @@ cgraph_edge_brings_all_scalars_for_node (struct
cgraph_edge *cs,

 /* Determine whether CS also brings all aggregate values that NODE is
    specialized for.  */

 static bool
 cgraph_edge_brings_all_agg_vals_for_node (struct cgraph_edge *cs,
                                          struct cgraph_node *node)
 {
   ipcp_transformation *ts = ipcp_get_transformation_summary (node);
   if (!ts || vec_safe_is_empty (ts->m_agg_values))
     return true;

   const ipa_argagg_value_list existing (ts->m_agg_values);
   auto_vec<ipa_argagg_value, 32> edge_values;
   ipa_node_params *dest_info = ipa_node_params_sum->get (node);
   gcc_checking_assert (dest_info->ipcp_orig_node);
   dest_info = ipa_node_params_sum->get (dest_info->ipcp_orig_node);
-  push_agg_values_from_edge (cs, dest_info, &edge_values, &existing);
+  push_agg_values_from_edge (cs, dest_info, &edge_values, NULL);
   const ipa_argagg_value_list avl (&edge_values);
   return avl.superset_of_p (existing);
 }

[Bug middle-end/107661] [13 Regression] lambdas get merged incorrectly in tempaltes, cause llvm-12 miscompilation since r13-3358-ge0403e95689af7

[jamborm at gcc dot gnu.org]

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

--- Comment #14 from Martin Jambor <jamborm at gcc dot gnu.org> ---
(In reply to Sergei Trofimovich from comment #13)
> It seems to have something to do with
> push_agg_values_from_edge()/push_agg_values_for_index_from_edge() behaviour
> of filtering self-recursive lattice values:
> 
>       if (interim && self_recursive_pass_through_p (cs, jfunc, index))
>         {
>           interim->push_adjusted_values (src_idx, index, unit_delta,
>                                          res);
>           return;
>         }

Spot on.

> 
> Here we seem to ignore lattice values discovered on the edges and only copy
> already encountered values. But we only populate 'interim' with values we
> specialised the self-recursive call against:
> 
>   push_agg_values_from_edge (cs, dest_info, &edge_values, &existing);
> 
> ('existing' variable is populated by values caller uses in one location).
> 
> 
> The following hack seems to fix the test case for me but I suspect it just
> breaks any self-recursive propagation:

No, it does not.  The self-recursive hack, I mean feature, is meant to
be used when push_agg_values_from_edge is called from
find_aggregate_values_for_callers_subset.  At that point we can assume
we would change both the caller and the callee.  But when it is called
from cgraph_edge_brings_all_agg_vals_for_node it is not the right
thing to do because it potentially leads only to redirection to a
different callee.

Correctness-wise your patch is a valid fix.  But it would disable to
computation avoidance code in push_agg_values_from_edge and so I'll
propose a patch adding a parameter to push_agg_values_from_edge and
its helper signaling whether they can be optimistic about
self-recursive edges.

Thank you for reporting and a very nice test-case.

[Bug ipa/107661] [13 Regression] lambdas get merged incorrectly in tempaltes, cause llvm-12 miscompilation since r13-3358-ge0403e95689af7

[jamborm at gcc dot gnu.org]

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

--- Comment #15 from Martin Jambor <jamborm at gcc dot gnu.org> ---
I have proposed a patch on the mailing list: 
https://gcc.gnu.org/pipermail/gcc-patches/2022-November/607017.html

[Bug ipa/107661] [13 Regression] lambdas get merged incorrectly in tempaltes, cause llvm-12 miscompilation since r13-3358-ge0403e95689af7

[cvs-commit at gcc dot gnu.org]

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

--- Comment #16 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Martin Jambor <jamborm@gcc.gnu.org>:

https://gcc.gnu.org/g:c4a92a9117a034e7cf291ae51d8b9b844fb5a88b

commit r13-4238-gc4a92a9117a034e7cf291ae51d8b9b844fb5a88b
Author: Martin Jambor <mjambor@suse.cz>
Date:   Tue Nov 22 18:22:03 2022 +0100

    ipa-cp: Do not be too optimistic about self-recursive edges (PR 107661)

    PR 107661 shows that function push_agg_values_for_index_from_edge
    should not attempt to optimize self-recursive call graph edges when
    called from cgraph_edge_brings_all_agg_vals_for_node.  Unlike when
    being called from find_aggregate_values_for_callers_subset, we cannot
    expect that any cloning for constants would lead to the edge leading
    from a new clone to the same new clone, in this case it would only be
    redirected to a new callee.

    Fixed by adding a parameter to push_agg_values_from_edge whether being
    optimistic about self-recursive edges is possible.

    gcc/ChangeLog:

    2022-11-22  Martin Jambor  <mjambor@suse.cz>

            PR ipa/107661
            * ipa-cp.cc (push_agg_values_from_edge): New parameter
            optimize_self_recursion, use it to decide whether to pass interim
to
            the helper function.
            (find_aggregate_values_for_callers_subset): Pass true in the new
            parameter of push_agg_values_from_edge.
            (cgraph_edge_brings_all_agg_vals_for_node): Pass false in the new
            parameter of push_agg_values_from_edge.

    gcc/testsuite/ChangeLog:

    2022-11-22  Martin Jambor  <mjambor@suse.cz>

            PR ipa/107661
            * g++.dg/ipa/pr107661.C: New test.

[Bug ipa/107661] [13 Regression] lambdas get merged incorrectly in tempaltes, cause llvm-12 miscompilation since r13-3358-ge0403e95689af7

[jamborm at gcc dot gnu.org]

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

Martin Jambor <jamborm at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |FIXED
             Status|ASSIGNED                    |RESOLVED

--- Comment #17 from Martin Jambor <jamborm at gcc dot gnu.org> ---
Fixed.

[Bug ipa/107661] [13 Regression] lambdas get merged incorrectly in tempaltes, cause llvm-12 miscompilation since r13-3358-ge0403e95689af7

[slyfox at gcc dot gnu.org]

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

--- Comment #18 from Sergei Trofimovich <slyfox at gcc dot gnu.org> ---
The fix also fixed all initial llvm-12's test suite failures for me. Thank you!