From: Soumya AR <[email protected]>
This patch adds a new pass that recognises compare-and-swap loops implementing
an atomic fetch min or max, and replaces each one with a single
IFN_ATOMIC_FETCH_MINMAX call. This allows us to emit a target optab for fetch
min/max, if available.
For example, the following CAS loop implementing fetch_max [P0493R5 5.2]:
template <typename T>
T atomic_fetch_max_explicit (std::atomic<T> *pv,
typename std::atomic<T>::value_type v,
std::memory_order m) noexcept {
auto t = pv->load (std::memory_order_relaxed);
while (!pv->compare_exchange_weak (t, std::max (v, t), m,
std::memory_order_relaxed))
;
return t;
}
Can be generalized to the following shape:
expected = atomic_load (ptr);
loop:
desired = MIN/MAX (expected, value);
success = compare_exchange (ptr, &expected, desired, mem_order);
if (success) exit loop;
goto loop;
return expected;
and rewritten to an IFN call:
result = IFN_ATOMIC_FETCH_MINMAX (ptr, value, mem_order,
op_code, /* MIN_EXPR or MAX_EXPR */
0_datatype)
return result;
The pass runs at -O2 and above, just after phiopt.
----
The first step in this pattern-matching is finding a CAS loop. The pass looks
for a generic fetch-op CAS loop by asking the following:
(1) Is there a CAS call in the loop body?
CAS can show up in two forms in gimple:
- The IFN form IFN_ATOMIC_COMPARE_EXCHANGE takes 'expected' by value and
returns a complex (expected, success-flag).
- The builtin form __atomic_compare_exchange_N takes &expected so it can write
the observed value back to memory on failure, and returns just the bool.
The pass recognises both. If the call has no LHS, the user is throwing away
the result entirely, and this can't be a CAS retry loop.
(2) Does the CAS success flag control the loop's exit?
For the IFN form we extract the IMAGPART; for the builtin form we use the bool
directly. We then walk uses of that flag, allowing one optional BIT_NOT_EXPR
(to tackle "while (!cas(...))"), and look for a gcond that sits inside the loop
and is the source of the loop's single exit edge.
(3) Is the loop self-contained?
Every statement in the loop other than the CAS itself must be side-effect free,
and every SSA name defined in the loop must have all its uses inside the loop.
Although, one exception is permitted: for an IFN CAS, the REALPART of the CAS
result (the value memory held when CAS finally succeeded) is allowed to escape.
That value is what a fetch-op call returns, so a post-loop use of it is
semantically equivalent to a use of the new IFN's LHS.
(4) Are the arguments well formed in the builtin?
For the IFN form, 'expected' is just CAS call's arg 1 in SSA form.
For the builtin form arg 1 is normally an ADDR_EXPR wrapping a VAR_DECL.
We unwrap it to get m_expected so that emit_replacement can later assign
the IFN's result into that decl.
If arg 1 isn't an ADDR_EXPR, we bail. This can happen for when the user invokes
the builtin with expected as a pointer, for example:
int helper_fetch_min (int *ptr, int desired, int *expected, int val) {
do {
desired = *expected < val ? *expected : val;
} while (!__atomic_compare_exchange_n (ptr, expected, desired, 0,
__ATOMIC_SEQ_CST,
__ATOMIC_RELAXED));
return *expected;
}
This is valid, but to handle it we'd probably need to do some kind of pointer
analysis, which is out of scope here.
(5) Is there a pre-loop __atomic_load_N that set 'expected'?
If one is reachable from 'expected' through copies and casts and is fed only
into the CAS, we can mark it for removal.
If no such load exists: eg. if 'expected' was set to a constant, or a function
argument, or anything else: we leave whatever sits in the preheader alone.
If a non atomic load of 'expected' is given to CAS, it should be UB, but for
our intents, pattern-matching to fetch min/max should be allowed.
Either way, we can pattern-match to fetch min/max.
----
The second step is matching the desired op, in this case, min/max. We look
at the SSA name passed as 'desired' and ask whether it was computed as a
MIN/MAX of 'expected' and some other value. Three shapes show up in practice:
(1) A MIN_EXPR or MAX_EXPR feeding desired directly:
bb_header:
expected = PHI <expected_init (preheader), expected_after_cas (latch)>
desired = MIN_EXPR <val, expected>
success = CAS (ptr, expected, desired, ...)
if (success) exit
goto bb_header
One operand of the MIN must be 'expected'; the other becomes the value being
compared against.
(2) A PHI selecting between two SSA names out of a compare:
bb_dom: if (a < b) goto bb_true else bb_false
/ \
bb_true bb_false
\ /
bb_join: desired = PHI <a (from bb_true), b (from bb_false)>
... desired feeds CAS ...
We find the gcond at the PHI's immediate dominator, decide MIN vs MAX from the
combination of compare code and which PHI argument sits on which edge, and
verify that one of the compared values is 'expected'.
The PHI could also select between two values via a MEM_REF. In that case we
unwrap the ADDR_EXPRs once before comparing.
(3) A PHI joining two MIN/MAX gassigns. This is what libstdc++'s
atomic_fetch_min/max compiles to: it uses a while-loop, so 'desired' is computed
once before the loop and again inside it, and the two computations meet at a PHI
feeding CAS:
bb_preheader: bb_failed_cas_recompute:
expected_init = atomic_load expected_post = REALPART of last CAS
desired_init = MIN <val, desired_post = MIN <val,
expected_init> expected_post>
\ /
v v
bb_cas:
desired = PHI <desired_init (preheader), desired_post (recompute)>
expected = PHI <expected_init (preheader), expected_post (recompute)>
CAS (ptr, expected, desired, ...)
We add a check that walks the two PHIs arguments': for each predecessor edge,
the minmax PHI's argument on that edge must be a MIN/MAX gassign whose non-val
operand equals the expected PHI's argument on the same edge.
If every edge agrees on the same MIN-vs-MAX code and the same val, we can
collapse the join to a single MIN/MAX <val, expected> and create a case for (1).
----
The pass is laid out as a small class hierarchy to allow future atomic ops to
re-use the CAS pattern-matching infra.
cas_to_atomic_op is the base class that owns all of the CAS-loop work described
above and exposes two pure-virtual hooks:
- match_op_shape, which checks if the expression feeding 'desired' matches the
shape for this op.
- emit_replacement, which builds the IFN call and splices it in.
cas_to_minmax derives from it and fills in those hooks for the min/max
case.
----
The source CAS has separate success/failure memory orders, but the
ATOMIC_FETCH_MINMAX IFN encodes a single order. We replicate what the
CAS expanders' promotion rules do:
- non-constant orders are treated as SEQ_CST
- if failure > success or failure = release/acq_rel, promote the effective
success order to SEQ_CST.
We then use the resultant success ordering for the IFN.
----
For deleting the CAS loop, the pass takes a deliberately small approach.
We do not remove any basic blocks. Instead we splice the new IFN before the
CAS, and:
- Set the success flag reads as 1
- For IFN CAS, set the REALPART to IFN's LHS
- Patch the exit gcond to a trivially true compare.
CFG cleanup at the end of the pass then folds the dead branches and removes
the redundant loop body for us. Trying to delete the BB kept tripping on
side-effects, so this felt a lot simpler.
----
Bootstrapped and regression tested on aarch64-linux-gnu and x86_64-linux-gnu,
no regression. Cross-compiled and regression tested under qemu for
arm-linux-gnueabihf-armv7-a and aarch64-linux-gnu without LSE.
OK for mainline?
Signed-off-by: Soumya AR <[email protected]>
gcc/ChangeLog:
* Makefile.in: Add tree-cas-to-atomic-op.o.
* passes.def: Add pass_transform_cas_loops_to_atomic_op after phiopt.
* tree-pass.h (make_pass_transform_cas_loops_to_atomic_op): Declare.
* tree-cas-to-atomic-op.cc: New file.
gcc/testsuite/ChangeLog:
* g++.dg/tree-ssa/cas-to-minmax-1.C: New test.
* g++.dg/tree-ssa/cas-to-minmax-2.C: New test.
* g++.dg/tree-ssa/cas-to-minmax-3.C: New test.
* g++.dg/tree-ssa/cas-to-minmax-4.C: New test.
* gcc.dg/tree-ssa/cas-to-minmax-1.c: New test.
* gcc.dg/tree-ssa/cas-to-minmax-2.c: New test.
* gcc.dg/tree-ssa/cas-to-minmax-3.c: New test.
* gcc.dg/tree-ssa/cas-to-minmax-4.c: New test.
* gcc.dg/tree-ssa/cas-to-minmax-5.c: New test.
* gcc.dg/tree-ssa/cas-to-minmax-6.c: New test.
* gcc.dg/tree-ssa/cas-to-minmax-7.c: New test.
* gcc.dg/tree-ssa/cas-to-minmax-run-1.c: New test.
* gcc.dg/tree-ssa/cas-to-minmax-run-2.c: New test.
* gcc.dg/tree-ssa/cas-to-minmax-run-3.c: New test.
---
gcc/Makefile.in | 1 +
gcc/passes.def | 1 +
.../g++.dg/tree-ssa/cas-to-minmax-1.C | 36 +
.../g++.dg/tree-ssa/cas-to-minmax-2.C | 35 +
.../g++.dg/tree-ssa/cas-to-minmax-3.C | 36 +
.../g++.dg/tree-ssa/cas-to-minmax-4.C | 36 +
.../gcc.dg/tree-ssa/cas-to-minmax-1.c | 29 +
.../gcc.dg/tree-ssa/cas-to-minmax-2.c | 28 +
.../gcc.dg/tree-ssa/cas-to-minmax-3.c | 25 +
.../gcc.dg/tree-ssa/cas-to-minmax-4.c | 33 +
.../gcc.dg/tree-ssa/cas-to-minmax-5.c | 29 +
.../gcc.dg/tree-ssa/cas-to-minmax-6.c | 28 +
.../gcc.dg/tree-ssa/cas-to-minmax-7.c | 34 +
.../gcc.dg/tree-ssa/cas-to-minmax-run-1.c | 75 +
.../gcc.dg/tree-ssa/cas-to-minmax-run-2.c | 55 +
.../gcc.dg/tree-ssa/cas-to-minmax-run-3.c | 59 +
gcc/tree-cas-to-atomic-op.cc | 1428 +++++++++++++++++
gcc/tree-pass.h | 1 +
18 files changed, 1969 insertions(+)
create mode 100644 gcc/testsuite/g++.dg/tree-ssa/cas-to-minmax-1.C
create mode 100644 gcc/testsuite/g++.dg/tree-ssa/cas-to-minmax-2.C
create mode 100644 gcc/testsuite/g++.dg/tree-ssa/cas-to-minmax-3.C
create mode 100644 gcc/testsuite/g++.dg/tree-ssa/cas-to-minmax-4.C
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/cas-to-minmax-1.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/cas-to-minmax-2.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/cas-to-minmax-3.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/cas-to-minmax-4.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/cas-to-minmax-5.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/cas-to-minmax-6.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/cas-to-minmax-7.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/cas-to-minmax-run-1.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/cas-to-minmax-run-2.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/cas-to-minmax-run-3.c
create mode 100644 gcc/tree-cas-to-atomic-op.cc
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index bcd5059d00c..301a8ffdcf1 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1793,6 +1793,7 @@ OBJS = \
tree-ssa-dom.o \
tree-ssa-dse.o \
tree-ssa-forwprop.o \
+ tree-cas-to-atomic-op.o \
tree-ssa-ifcombine.o \
tree-ssa-live.o \
tree-ssa-loop-ch.o \
diff --git a/gcc/passes.def b/gcc/passes.def
index 54f2eeb159d..38b44495805 100644
--- a/gcc/passes.def
+++ b/gcc/passes.def
@@ -99,6 +99,7 @@ along with GCC; see the file COPYING3. If not see
NEXT_PASS (pass_dse);
NEXT_PASS (pass_cd_dce, false /* update_address_taken_p */, true /*
remove_unused_locals */);
NEXT_PASS (pass_phiopt, true /* early_p */);
+ NEXT_PASS (pass_transform_cas_loops_to_atomic_op);
/* Cleanup eh is done before tail recusision to remove empty (only
clobbers)
finally blocks which would block tail recursion. */
NEXT_PASS (pass_cleanup_eh);
diff --git a/gcc/testsuite/g++.dg/tree-ssa/cas-to-minmax-1.C
b/gcc/testsuite/g++.dg/tree-ssa/cas-to-minmax-1.C
new file mode 100644
index 00000000000..5da7f2d2135
--- /dev/null
+++ b/gcc/testsuite/g++.dg/tree-ssa/cas-to-minmax-1.C
@@ -0,0 +1,36 @@
+// { dg-do compile { target c++11 } }
+// { dg-options "-O2 -fdump-tree-cas-to-atomic-op" }
+
+#include <atomic>
+#include <algorithm>
+
+template <typename T>
+T atomic_fetch_min_explicit(std::atomic<T>* pv,
+ typename std::atomic<T>::value_type v,
+ std::memory_order m) noexcept {
+ auto t = pv->load(std::memory_order_relaxed);
+ while (!pv->compare_exchange_weak(t, std::min(v, t), m,
+ std::memory_order_relaxed))
+ ;
+ return t;
+}
+
+template <typename T>
+T atomic_fetch_max_explicit(std::atomic<T>* pv,
+ typename std::atomic<T>::value_type v,
+ std::memory_order m) noexcept {
+ auto t = pv->load(std::memory_order_relaxed);
+ while (!pv->compare_exchange_weak(t, std::max(v, t), m,
+ std::memory_order_relaxed))
+ ;
+ return t;
+}
+
+template int atomic_fetch_min_explicit<int>(std::atomic<int>*, int,
+ std::memory_order) noexcept;
+template int atomic_fetch_max_explicit<int>(std::atomic<int>*, int,
+ std::memory_order) noexcept;
+
+// { dg-final { scan-tree-dump "atomic_fetch_min_explicit\\<int\\>: rewrote
loop \[0-9\]+ to atomic MIN" "cas-to-atomic-op" } }
+// { dg-final { scan-tree-dump "atomic_fetch_max_explicit\\<int\\>: rewrote
loop \[0-9\]+ to atomic MAX" "cas-to-atomic-op" } }
+// { dg-final { scan-tree-dump-not "ATOMIC_COMPARE_EXCHANGE"
"cas-to-atomic-op" } }
diff --git a/gcc/testsuite/g++.dg/tree-ssa/cas-to-minmax-2.C
b/gcc/testsuite/g++.dg/tree-ssa/cas-to-minmax-2.C
new file mode 100644
index 00000000000..e0486883c89
--- /dev/null
+++ b/gcc/testsuite/g++.dg/tree-ssa/cas-to-minmax-2.C
@@ -0,0 +1,35 @@
+// { dg-do compile { target c++11 } }
+// { dg-options "-O2 -fdump-tree-cas-to-atomic-op" }
+
+#include <atomic>
+
+template <typename T>
+T atomic_fetch_min_inline(std::atomic<T>* pv,
+ typename std::atomic<T>::value_type v,
+ std::memory_order m) noexcept {
+ auto t = pv->load(std::memory_order_relaxed);
+ while (!pv->compare_exchange_weak(t, (t < v) ? t : v, m,
+ std::memory_order_relaxed))
+ ;
+ return t;
+}
+
+template <typename T>
+T atomic_fetch_max_inline(std::atomic<T>* pv,
+ typename std::atomic<T>::value_type v,
+ std::memory_order m) noexcept {
+ auto t = pv->load(std::memory_order_relaxed);
+ while (!pv->compare_exchange_weak(t, (t > v) ? t : v, m,
+ std::memory_order_relaxed))
+ ;
+ return t;
+}
+
+template int atomic_fetch_min_inline<int>(std::atomic<int>*, int,
+ std::memory_order) noexcept;
+template int atomic_fetch_max_inline<int>(std::atomic<int>*, int,
+ std::memory_order) noexcept;
+
+// { dg-final { scan-tree-dump "atomic_fetch_min_inline\\<int\\>: rewrote loop
\[0-9\]+ to atomic MIN" "cas-to-atomic-op" } }
+// { dg-final { scan-tree-dump "atomic_fetch_max_inline\\<int\\>: rewrote loop
\[0-9\]+ to atomic MAX" "cas-to-atomic-op" } }
+// { dg-final { scan-tree-dump-not "ATOMIC_COMPARE_EXCHANGE"
"cas-to-atomic-op" } }
diff --git a/gcc/testsuite/g++.dg/tree-ssa/cas-to-minmax-3.C
b/gcc/testsuite/g++.dg/tree-ssa/cas-to-minmax-3.C
new file mode 100644
index 00000000000..f6d5c918641
--- /dev/null
+++ b/gcc/testsuite/g++.dg/tree-ssa/cas-to-minmax-3.C
@@ -0,0 +1,36 @@
+// { dg-do compile { target c++11 } }
+// { dg-options "-O2 -fdump-tree-cas-to-atomic-op" }
+
+#include <atomic>
+#include <algorithm>
+
+template <typename T>
+T atomic_fetch_min_unsigned(std::atomic<T>* pv,
+ typename std::atomic<T>::value_type v,
+ std::memory_order m) noexcept {
+ auto t = pv->load(std::memory_order_relaxed);
+ while (!pv->compare_exchange_weak(t, std::min(v, t), m,
+ std::memory_order_relaxed))
+ ;
+ return t;
+}
+
+template <typename T>
+T atomic_fetch_max_unsigned(std::atomic<T>* pv,
+ typename std::atomic<T>::value_type v,
+ std::memory_order m) noexcept {
+ auto t = pv->load(std::memory_order_relaxed);
+ while (!pv->compare_exchange_weak(t, std::max(v, t), m,
+ std::memory_order_relaxed))
+ ;
+ return t;
+}
+
+template unsigned int atomic_fetch_min_unsigned<unsigned int>(
+ std::atomic<unsigned int>*, unsigned int, std::memory_order) noexcept;
+template unsigned int atomic_fetch_max_unsigned<unsigned int>(
+ std::atomic<unsigned int>*, unsigned int, std::memory_order) noexcept;
+
+// { dg-final { scan-tree-dump "atomic_fetch_min_unsigned\\<unsigned int\\>:
rewrote loop \[0-9\]+ to atomic MIN" "cas-to-atomic-op" } }
+// { dg-final { scan-tree-dump "atomic_fetch_max_unsigned\\<unsigned int\\>:
rewrote loop \[0-9\]+ to atomic MAX" "cas-to-atomic-op" } }
+// { dg-final { scan-tree-dump-not "ATOMIC_COMPARE_EXCHANGE"
"cas-to-atomic-op" } }
diff --git a/gcc/testsuite/g++.dg/tree-ssa/cas-to-minmax-4.C
b/gcc/testsuite/g++.dg/tree-ssa/cas-to-minmax-4.C
new file mode 100644
index 00000000000..80429b95d22
--- /dev/null
+++ b/gcc/testsuite/g++.dg/tree-ssa/cas-to-minmax-4.C
@@ -0,0 +1,36 @@
+// { dg-do compile { target c++11 } }
+// { dg-options "-O2 -fdump-tree-cas-to-atomic-op" }
+
+#include <atomic>
+#include <algorithm>
+
+template <typename T>
+T atomic_fetch_min_no_load(std::atomic<T>* pv,
+ typename std::atomic<T>::value_type v,
+ std::memory_order m) noexcept {
+ T t = 0;
+ while (!pv->compare_exchange_weak(t, std::min(v, t), m,
+ std::memory_order_relaxed))
+ ;
+ return t;
+}
+
+template <typename T>
+T atomic_fetch_max_no_load(std::atomic<T>* pv,
+ typename std::atomic<T>::value_type v,
+ std::memory_order m) noexcept {
+ T t = 0;
+ while (!pv->compare_exchange_weak(t, std::max(v, t), m,
+ std::memory_order_relaxed))
+ ;
+ return t;
+}
+
+template int atomic_fetch_min_no_load<int>(std::atomic<int>*, int,
+ std::memory_order) noexcept;
+template int atomic_fetch_max_no_load<int>(std::atomic<int>*, int,
+ std::memory_order) noexcept;
+
+// { dg-final { scan-tree-dump "atomic_fetch_min_no_load\\<int\\>: rewrote
loop \[0-9\]+ to atomic MIN" "cas-to-atomic-op" } }
+// { dg-final { scan-tree-dump "atomic_fetch_max_no_load\\<int\\>: rewrote
loop \[0-9\]+ to atomic MAX" "cas-to-atomic-op" } }
+// { dg-final { scan-tree-dump-not "ATOMIC_COMPARE_EXCHANGE"
"cas-to-atomic-op" } }
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/cas-to-minmax-1.c
b/gcc/testsuite/gcc.dg/tree-ssa/cas-to-minmax-1.c
new file mode 100644
index 00000000000..4d946a34188
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/cas-to-minmax-1.c
@@ -0,0 +1,29 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-cas-to-atomic-op" } */
+
+int
+atomic_fetch_min (int *ptr, int val)
+{
+ int expected = __atomic_load_n (ptr, __ATOMIC_RELAXED);
+ while (!__atomic_compare_exchange_n (ptr, &expected,
+ expected < val ? expected : val, 0,
+ __ATOMIC_SEQ_CST, __ATOMIC_RELAXED))
+ ;
+ return expected;
+}
+
+int
+atomic_fetch_max (int *ptr, int val)
+{
+ int expected = __atomic_load_n (ptr, __ATOMIC_RELAXED);
+ while (!__atomic_compare_exchange_n (ptr, &expected,
+ expected > val ? expected : val, 0,
+ __ATOMIC_SEQ_CST, __ATOMIC_RELAXED))
+ ;
+ return expected;
+}
+
+/* { dg-final { scan-tree-dump "atomic_fetch_min: rewrote loop \[0-9\]+ to
atomic MIN" "cas-to-atomic-op" } } */
+/* { dg-final { scan-tree-dump "atomic_fetch_max: rewrote loop \[0-9\]+ to
atomic MAX" "cas-to-atomic-op" } } */
+/* { dg-final { scan-tree-dump-not "ATOMIC_COMPARE_EXCHANGE"
"cas-to-atomic-op" } } */
+/* { dg-final { scan-tree-dump-not "__atomic_load" "cas-to-atomic-op" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/cas-to-minmax-2.c
b/gcc/testsuite/gcc.dg/tree-ssa/cas-to-minmax-2.c
new file mode 100644
index 00000000000..375cf2542ca
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/cas-to-minmax-2.c
@@ -0,0 +1,28 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-cas-to-atomic-op" } */
+
+unsigned int
+atomic_fetch_min_unsigned (unsigned int *ptr, unsigned int val)
+{
+ unsigned int expected = __atomic_load_n (ptr, __ATOMIC_RELAXED);
+ while (!__atomic_compare_exchange_n (ptr, &expected,
+ expected < val ? expected : val, 0,
+ __ATOMIC_SEQ_CST, __ATOMIC_RELAXED))
+ ;
+ return expected;
+}
+
+unsigned int
+atomic_fetch_max_unsigned (unsigned int *ptr, unsigned int val)
+{
+ unsigned int expected = __atomic_load_n (ptr, __ATOMIC_RELAXED);
+ while (!__atomic_compare_exchange_n (ptr, &expected,
+ expected > val ? expected : val, 0,
+ __ATOMIC_SEQ_CST, __ATOMIC_RELAXED))
+ ;
+ return expected;
+}
+
+/* { dg-final { scan-tree-dump "atomic_fetch_min_unsigned: rewrote loop
\[0-9\]+ to atomic MIN" "cas-to-atomic-op" } } */
+/* { dg-final { scan-tree-dump "atomic_fetch_max_unsigned: rewrote loop
\[0-9\]+ to atomic MAX" "cas-to-atomic-op" } } */
+/* { dg-final { scan-tree-dump-not "ATOMIC_COMPARE_EXCHANGE"
"cas-to-atomic-op" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/cas-to-minmax-3.c
b/gcc/testsuite/gcc.dg/tree-ssa/cas-to-minmax-3.c
new file mode 100644
index 00000000000..090b242b3ec
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/cas-to-minmax-3.c
@@ -0,0 +1,25 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-cas-to-atomic-op" } */
+
+void
+atomic_min_no_return (int *ptr, int val)
+{
+ int expected = __atomic_load_n (ptr, __ATOMIC_RELAXED);
+ while (!__atomic_compare_exchange_n (ptr, &expected,
+ expected < val ? expected : val, 0,
+ __ATOMIC_SEQ_CST, __ATOMIC_RELAXED))
+ ;
+}
+
+void
+atomic_max_no_return (int *ptr, int val)
+{
+ int expected = __atomic_load_n (ptr, __ATOMIC_RELAXED);
+ while (!__atomic_compare_exchange_n (ptr, &expected,
+ expected > val ? expected : val, 0,
+ __ATOMIC_SEQ_CST, __ATOMIC_RELAXED))
+ ;
+}
+
+/* { dg-final { scan-tree-dump "atomic_min_no_return: rewrote loop \[0-9\]+ to
atomic MIN" "cas-to-atomic-op" } } */
+/* { dg-final { scan-tree-dump "atomic_max_no_return: rewrote loop \[0-9\]+ to
atomic MAX" "cas-to-atomic-op" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/cas-to-minmax-4.c
b/gcc/testsuite/gcc.dg/tree-ssa/cas-to-minmax-4.c
new file mode 100644
index 00000000000..4aebebdb464
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/cas-to-minmax-4.c
@@ -0,0 +1,33 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-cas-to-atomic-op" } */
+
+extern void log_attempt (int);
+
+int
+atomic_min_side_effect (int *ptr, int val)
+{
+ int expected = __atomic_load_n (ptr, __ATOMIC_RELAXED);
+ while (!__atomic_compare_exchange_n (ptr, &expected,
+ expected < val ? expected : val, 0,
+ __ATOMIC_SEQ_CST, __ATOMIC_RELAXED))
+ {
+ log_attempt (expected); /* Side effect, do not transform. */
+ }
+ return expected;
+}
+
+int
+atomic_max_side_effect (int *ptr, int val)
+{
+ int expected = __atomic_load_n (ptr, __ATOMIC_RELAXED);
+ while (!__atomic_compare_exchange_n (ptr, &expected,
+ expected > val ? expected : val, 0,
+ __ATOMIC_SEQ_CST, __ATOMIC_RELAXED))
+ {
+ log_attempt (expected); /* Side effect, do not transform. */
+ }
+ return expected;
+}
+
+/* { dg-final { scan-tree-dump-not "rewrote loop" "cas-to-atomic-op" } } */
+/* { dg-final { scan-tree-dump-not "ATOMIC_FETCH_MINMAX" "cas-to-atomic-op" }
} */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/cas-to-minmax-5.c
b/gcc/testsuite/gcc.dg/tree-ssa/cas-to-minmax-5.c
new file mode 100644
index 00000000000..03d660b284f
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/cas-to-minmax-5.c
@@ -0,0 +1,29 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-cas-to-atomic-op" } */
+
+int
+atomic_fetch_min_mem_order (int *ptr, int val)
+{
+ int expected = __atomic_load_n (ptr, __ATOMIC_ACQUIRE);
+ while (!__atomic_compare_exchange_n (ptr, &expected,
+ expected < val ? expected : val, 0,
+ __ATOMIC_ACQ_REL, __ATOMIC_ACQUIRE))
+ ;
+ return expected;
+}
+
+int
+atomic_fetch_max_mem_order (int *ptr, int val)
+{
+ int expected = __atomic_load_n (ptr, __ATOMIC_ACQUIRE);
+ while (!__atomic_compare_exchange_n (ptr, &expected,
+ expected > val ? expected : val, 0,
+ __ATOMIC_ACQ_REL, __ATOMIC_ACQUIRE))
+ ;
+ return expected;
+}
+
+/* { dg-final { scan-tree-dump "atomic_fetch_min_mem_order: rewrote loop
\[0-9\]+ to atomic MIN" "cas-to-atomic-op" } } */
+/* { dg-final { scan-tree-dump "atomic_fetch_max_mem_order: rewrote loop
\[0-9\]+ to atomic MAX" "cas-to-atomic-op" } } */
+/* { dg-final { scan-tree-dump "ATOMIC_FETCH_MINMAX \\(ptr_\[0-9\]+\\(D\\),
val_\[0-9\]+\\(D\\), 4," "cas-to-atomic-op" } } */
+/* { dg-final { scan-tree-dump-not "ATOMIC_COMPARE_EXCHANGE"
"cas-to-atomic-op" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/cas-to-minmax-6.c
b/gcc/testsuite/gcc.dg/tree-ssa/cas-to-minmax-6.c
new file mode 100644
index 00000000000..bc81b4020b3
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/cas-to-minmax-6.c
@@ -0,0 +1,28 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-cas-to-atomic-op" } */
+
+int
+atomic_fetch_min_no_load (int *ptr, int val)
+{
+ int expected = 0;
+ while (!__atomic_compare_exchange_n (ptr, &expected,
+ expected < val ? expected : val, 0,
+ __ATOMIC_SEQ_CST, __ATOMIC_RELAXED))
+ ;
+ return expected;
+}
+
+int
+atomic_fetch_max_no_load (int *ptr, int val)
+{
+ int expected = 0;
+ while (!__atomic_compare_exchange_n (ptr, &expected,
+ expected > val ? expected : val, 0,
+ __ATOMIC_SEQ_CST, __ATOMIC_RELAXED))
+ ;
+ return expected;
+}
+
+/* { dg-final { scan-tree-dump "atomic_fetch_min_no_load: rewrote loop
\[0-9\]+ to atomic MIN" "cas-to-atomic-op" } } */
+/* { dg-final { scan-tree-dump "atomic_fetch_max_no_load: rewrote loop
\[0-9\]+ to atomic MAX" "cas-to-atomic-op" } } */
+/* { dg-final { scan-tree-dump-not "ATOMIC_COMPARE_EXCHANGE"
"cas-to-atomic-op" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/cas-to-minmax-7.c
b/gcc/testsuite/gcc.dg/tree-ssa/cas-to-minmax-7.c
new file mode 100644
index 00000000000..6b09c52b551
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/cas-to-minmax-7.c
@@ -0,0 +1,34 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-cas-to-atomic-op" } */
+
+int
+atomic_fetch_min_separated (int *ptr, int val)
+{
+ int expected = __atomic_load_n (ptr, __ATOMIC_RELAXED);
+ int desired;
+ do
+ {
+ desired = expected < val ? expected : val;
+ }
+ while (!__atomic_compare_exchange_n (ptr, &expected, desired, 0,
+ __ATOMIC_SEQ_CST, __ATOMIC_RELAXED));
+ return expected;
+}
+
+int
+atomic_fetch_max_separated (int *ptr, int val)
+{
+ int expected = __atomic_load_n (ptr, __ATOMIC_RELAXED);
+ int desired;
+ do
+ {
+ desired = expected > val ? expected : val;
+ }
+ while (!__atomic_compare_exchange_n (ptr, &expected, desired, 0,
+ __ATOMIC_SEQ_CST, __ATOMIC_RELAXED));
+ return expected;
+}
+
+/* { dg-final { scan-tree-dump "atomic_fetch_min_separated: rewrote loop
\[0-9\]+ to atomic MIN" "cas-to-atomic-op" } } */
+/* { dg-final { scan-tree-dump "atomic_fetch_max_separated: rewrote loop
\[0-9\]+ to atomic MAX" "cas-to-atomic-op" } } */
+/* { dg-final { scan-tree-dump-not "ATOMIC_COMPARE_EXCHANGE"
"cas-to-atomic-op" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/cas-to-minmax-run-1.c
b/gcc/testsuite/gcc.dg/tree-ssa/cas-to-minmax-run-1.c
new file mode 100644
index 00000000000..6c7b2f85090
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/cas-to-minmax-run-1.c
@@ -0,0 +1,75 @@
+/* { dg-do run } */
+/* { dg-options "-O2" } */
+
+extern void abort (void);
+
+int
+atomic_fetch_min (int *ptr, int val)
+{
+ int expected = __atomic_load_n (ptr, __ATOMIC_RELAXED);
+ while (!__atomic_compare_exchange_n (ptr, &expected,
+ expected < val ? expected : val, 0,
+ __ATOMIC_SEQ_CST, __ATOMIC_RELAXED))
+ ;
+ return expected;
+}
+
+int
+atomic_fetch_max (int *ptr, int val)
+{
+ int expected = __atomic_load_n (ptr, __ATOMIC_RELAXED);
+ while (!__atomic_compare_exchange_n (ptr, &expected,
+ expected > val ? expected : val, 0,
+ __ATOMIC_SEQ_CST, __ATOMIC_RELAXED))
+ ;
+ return expected;
+}
+
+int
+main ()
+{
+ int x;
+ int old;
+
+ x = 10;
+ old = atomic_fetch_min (&x, 5);
+ if (old != 10 || x != 5)
+ abort ();
+
+ x = 10;
+ old = atomic_fetch_min (&x, 15);
+ if (old != 10 || x != 10)
+ abort ();
+
+ x = 10;
+ old = atomic_fetch_max (&x, 20);
+ if (old != 10 || x != 20)
+ abort ();
+
+ x = 10;
+ old = atomic_fetch_max (&x, 5);
+ if (old != 10 || x != 10)
+ abort ();
+
+ x = -5;
+ old = atomic_fetch_min (&x, -10);
+ if (old != -5 || x != -10)
+ abort ();
+
+ x = -10;
+ old = atomic_fetch_max (&x, -5);
+ if (old != -10 || x != -5)
+ abort ();
+
+ x = 42;
+ old = atomic_fetch_min (&x, 42);
+ if (old != 42 || x != 42)
+ abort ();
+
+ x = 42;
+ old = atomic_fetch_max (&x, 42);
+ if (old != 42 || x != 42)
+ abort ();
+
+ return 0;
+}
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/cas-to-minmax-run-2.c
b/gcc/testsuite/gcc.dg/tree-ssa/cas-to-minmax-run-2.c
new file mode 100644
index 00000000000..130944580db
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/cas-to-minmax-run-2.c
@@ -0,0 +1,55 @@
+/* { dg-do run } */
+/* { dg-options "-O2" } */
+
+extern void abort (void);
+
+unsigned int
+atomic_fetch_max_unsigned (unsigned int *ptr, unsigned int val)
+{
+ unsigned int expected = __atomic_load_n (ptr, __ATOMIC_RELAXED);
+ while (!__atomic_compare_exchange_n (ptr, &expected,
+ expected > val ? expected : val, 0,
+ __ATOMIC_SEQ_CST, __ATOMIC_RELAXED))
+ ;
+ return expected;
+}
+
+unsigned int
+atomic_fetch_min_unsigned (unsigned int *ptr, unsigned int val)
+{
+ unsigned int expected = __atomic_load_n (ptr, __ATOMIC_RELAXED);
+ while (!__atomic_compare_exchange_n (ptr, &expected,
+ expected < val ? expected : val, 0,
+ __ATOMIC_SEQ_CST, __ATOMIC_RELAXED))
+ ;
+ return expected;
+}
+
+int
+main ()
+{
+ unsigned int x;
+ unsigned int old;
+
+ x = 100u;
+ old = atomic_fetch_max_unsigned (&x, 200u);
+ if (old != 100u || x != 200u)
+ abort ();
+
+ x = 100u;
+ old = atomic_fetch_min_unsigned (&x, 50u);
+ if (old != 100u || x != 50u)
+ abort ();
+
+ x = 0xFFFFFFFFu;
+ old = atomic_fetch_min_unsigned (&x, 0u);
+ if (old != 0xFFFFFFFFu || x != 0u)
+ abort ();
+
+ x = 0u;
+ old = atomic_fetch_max_unsigned (&x, 0xFFFFFFFFu);
+ if (old != 0u || x != 0xFFFFFFFFu)
+ abort ();
+
+ return 0;
+}
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/cas-to-minmax-run-3.c
b/gcc/testsuite/gcc.dg/tree-ssa/cas-to-minmax-run-3.c
new file mode 100644
index 00000000000..1a79949ab80
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/cas-to-minmax-run-3.c
@@ -0,0 +1,59 @@
+/* { dg-do run } */
+/* { dg-options "-O2 -fdump-tree-cas-to-atomic-op" } */
+
+extern void abort (void);
+
+unsigned val_min;
+unsigned val_max;
+
+int __attribute__((noinline))
+do_signed_min_via_cast (int x)
+{
+ int expected = __atomic_load_n ((int *)&val_min, __ATOMIC_RELAXED);
+ while (!__atomic_compare_exchange_n ((int *)&val_min, &expected,
+ expected < x ? expected : x, 0,
+ __ATOMIC_SEQ_CST, __ATOMIC_RELAXED))
+ ;
+ return expected;
+}
+
+int __attribute__((noinline))
+do_signed_max_via_cast (int x)
+{
+ int expected = __atomic_load_n ((int *)&val_max, __ATOMIC_RELAXED);
+ while (!__atomic_compare_exchange_n ((int *)&val_max, &expected,
+ expected > x ? expected : x, 0,
+ __ATOMIC_SEQ_CST, __ATOMIC_RELAXED))
+ ;
+ return expected;
+}
+
+int
+main ()
+{
+ int old;
+
+ val_min = (unsigned)-1;
+ old = do_signed_min_via_cast (5);
+ if (old != -1 || (int)val_min != -1)
+ abort ();
+
+ val_max = (unsigned)-1;
+ old = do_signed_max_via_cast (5);
+ if (old != -1 || (int)val_max != 5)
+ abort ();
+
+ val_min = (unsigned)-3;
+ old = do_signed_min_via_cast (-10);
+ if (old != -3 || (int)val_min != -10)
+ abort ();
+
+ val_max = (unsigned)-10;
+ old = do_signed_max_via_cast (-3);
+ if (old != -10 || (int)val_max != -3)
+ abort ();
+
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump "ATOMIC_FETCH_MINMAX" "cas-to-atomic-op" } } */
diff --git a/gcc/tree-cas-to-atomic-op.cc b/gcc/tree-cas-to-atomic-op.cc
new file mode 100644
index 00000000000..653049be033
--- /dev/null
+++ b/gcc/tree-cas-to-atomic-op.cc
@@ -0,0 +1,1428 @@
+/* Transform CAS loops implementing atomic fetch ops to dedicated IFNs.
+ Copyright The GNU Toolchain Authors.
+
+ This file is part of GCC.
+
+ GCC is free software; you can redistribute it and/or modify it
+ under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 3, or (at your option)
+ any later version.
+
+ GCC is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with GCC; see the file COPYING3. If not see
+ <http://www.gnu.org/licenses/>.
+
+This pass recognises CAS loops implementing an atomic fetch-op and rewrites
+each one to a single IFN call. The backend can then either expand the IFN
+to a dedicated instruction (where one exists) or fall back to a CAS loop again.
+
+Pattern detected:
+ expected = atomic_load (ptr)
+ loop:
+ desired = op (expected, value)
+ success = compare_exchange (ptr, &expected, desired, mem_order)
+ if (success) exit loop
+ goto loop
+ return expected
+
+The CAS can either be an IFN or a builtin, both forms are recognised.
+
+The source CAS has separate success/failure memory orders but the
+ATOMIC_FETCH_MINMAX IFN we emit encodes a single order. To handle this, we
+mirror what the CAS expanders do: if failure > success, promote the effective
+success order to SEQ_CST. The result is used on the IFN, so the rewrite
+preserves the original CAS's effective ordering.
+
+The cas_to_atomic_op base class in this pass drives the shared CAS-loop work,
+and one derived class per fetch-op fills in the op-specific bits. After a
+successful rewrite the loop's body collapses to the IFN call. The redundant
+loop header and exit block are left for CFG cleanup that runs at the end of
+the pass. */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "backend.h"
+#include "tree-core.h"
+#include "tree.h"
+#include "gimple.h"
+#include "tree-pass.h"
+#include "ssa.h"
+#include "gimple-iterator.h"
+#include "tree-cfg.h"
+#include "tree-ssa.h"
+#include "cfgloop.h"
+#include "fold-const.h"
+#include "cfganal.h"
+#include "internal-fn.h"
+#include "memmodel.h"
+
+namespace {
+#define DUMP_DETAILS(...)
\
+ do
\
+ {
\
+ if (dump_file && (dump_flags & TDF_DETAILS))
\
+ fprintf (dump_file, __VA_ARGS__); \
+ }
\
+ while (0)
+
+/* Return underlying values for an SSA name by removing trivial wrappers
+ like copies and casts.
+
+ - a cast is followed through its source.
+ - a copy from another SSA name is followed.
+ - a load from a VAR_DECL / PARM_DECL ends the walk: the decl is
+ returned, and the load's VUSE is written to *VUSE_OUT.
+ - anything else stops the walk and is returned as-is. */
+static tree
+get_ssa_base_value (tree name, tree *vuse_out = NULL)
+{
+ if (vuse_out)
+ *vuse_out = NULL_TREE;
+
+ if (TREE_CODE (name) != SSA_NAME)
+ return name;
+
+ gimple *def_stmt = SSA_NAME_DEF_STMT (name);
+
+ /* Follow casts. eg. _5 = (int) _4 */
+ if (gimple_assign_cast_p (def_stmt))
+ return get_ssa_base_value (gimple_assign_rhs1 (def_stmt), vuse_out);
+
+ /* Follow simple copies. eg. _4 = _3 */
+ if (gimple_assign_single_p (def_stmt))
+ {
+ tree rhs = gimple_assign_rhs1 (def_stmt);
+ if (TREE_CODE (rhs) == SSA_NAME)
+ return get_ssa_base_value (rhs, vuse_out);
+
+ /* The walk ends at a load from a VAR_DECL or PARM_DECL. eg. _3 = x
+ Return the decl as the base, and record the load's VUSE so the caller
+ can tell two loads of the same decl apart. VAR_DECL and PARM_DECL
+ are handled together: both produce the same _X = decl shape here,
+ and thus the matcher treats them identically. */
+ if (TREE_CODE (rhs) == VAR_DECL || TREE_CODE (rhs) == PARM_DECL)
+ {
+ if (vuse_out)
+ *vuse_out = gimple_vuse (def_stmt);
+ return rhs;
+ }
+ }
+
+ return name;
+}
+
+/* Compare two values for equality, following SSA copies and casts.
+
+ When both sides end at a load from memory, demand they read the
+ same memory version (same VUSE); otherwise two loads of the same
+ location could hold different values. */
+static bool
+values_equal_p (tree a, tree b)
+{
+ if (operand_equal_p (a, b, 0))
+ return true;
+
+ tree vuse_a, vuse_b;
+ tree base_a = get_ssa_base_value (a, &vuse_a);
+ tree base_b = get_ssa_base_value (b, &vuse_b);
+
+ if (!operand_equal_p (base_a, base_b, 0))
+ return false;
+
+ /* Different VUSEs means memory was rewritten between the loads,
+ so the two SSA names need not hold the same value. */
+ if (vuse_a && vuse_b)
+ return vuse_a == vuse_b;
+
+ /* At least one side didn't terminate at a load (get_ssa_base_value leaves
+ *vuse_out NULL in that case). The typical reason is the builtin-CAS
+ form: the matcher compares an SSA load of 'expected' against the bare
+ decl extracted from '&expected', which isn't a load and so has no VUSE.
+
+ Since base_a == base_b is already established, the remaining question
+ is whether memory could have changed between any load involved and the
+ CAS. That's not something we can check locally so the guarantee comes
+ from loop_is_self_contained, which rejects any loop body containing a
+ non-CAS VDEF. In a matched loop, no such intervening write exists, so
+ we should be able to confirm that the loaded value really is what the
+ CAS reads. */
+ return true;
+}
+
+/* Returns true if CALL is an atomic compare and swap call, either in the
+ form of an internal function or builtin. */
+static bool
+is_atomic_cas_call_p (gcall *call)
+{
+ if (gimple_call_internal_p (call, IFN_ATOMIC_COMPARE_EXCHANGE))
+ return true;
+
+ tree fndecl = gimple_call_fndecl (call);
+ if (fndecl && fndecl_built_in_p (fndecl, BUILT_IN_NORMAL))
+ {
+ enum built_in_function fncode = DECL_FUNCTION_CODE (fndecl);
+ return (fncode >= BUILT_IN_ATOMIC_COMPARE_EXCHANGE_N
+ && fncode <= BUILT_IN_ATOMIC_COMPARE_EXCHANGE_16);
+ }
+ return false;
+}
+
+/* Check if VALUE defined inside LOOP is used outside LOOP. */
+static bool
+value_escapes_loop_p (tree value, class loop *loop)
+{
+ if (TREE_CODE (value) != SSA_NAME)
+ return false;
+
+ /* Find instances of defs inside the loop. */
+ gimple *def_stmt = SSA_NAME_DEF_STMT (value);
+ basic_block def_bb = gimple_bb (def_stmt);
+
+ if (!def_bb || !flow_bb_inside_loop_p (loop, def_bb))
+ return false;
+
+ /* Find uses of those defs outside the loop. */
+ for (gimple *use_stmt : gather_imm_use_stmts (value))
+ {
+ basic_block use_bb = gimple_bb (use_stmt);
+ if (use_bb && !flow_bb_inside_loop_p (loop, use_bb))
+ return true;
+ }
+ return false;
+}
+
+/* For IFN CAS, the result is a complex (expected, success-flag) where the
+ REALPART is the post-CAS observed expected (i.e. what a fetch-op call
+ would return). CAS_RESULT is that complex SSA name. Walks its uses
+ for a REALPART_EXPR that escapes LOOP, and returns the escaping SSA name.
+ Returns NULL_TREE if no use escapes (in which case the IFN replacement
+ doesn't need an LHS). */
+static tree
+find_expected_out_ssa (tree cas_result, class loop *loop)
+{
+ for (gimple *use_stmt : gather_imm_use_stmts (cas_result))
+ {
+ if (!is_gimple_assign (use_stmt)
+ || gimple_assign_rhs_code (use_stmt) != REALPART_EXPR)
+ continue;
+
+ tree realpart = gimple_assign_lhs (use_stmt);
+
+ if (value_escapes_loop_p (realpart, loop))
+ return realpart;
+
+ /* Check for cast after REALPART_EXPR. */
+ for (gimple *cast_use : gather_imm_use_stmts (realpart))
+ if (gimple_assign_cast_p (cast_use))
+ {
+ tree cast_result = gimple_assign_lhs (cast_use);
+ if (value_escapes_loop_p (cast_result, loop))
+ return cast_result;
+ }
+ }
+ return NULL_TREE;
+}
+
+/* We target the following pattern:
+
+ m_atomic_load: expected = atomic_load (m_ptr) // optional;
+
+ loop header:
+ m_desired = op (expected, ...)
+ m_cas_result = compare_exchange (m_ptr,
+ &m_expected,
+ m_desired,
+ m_success_model)
+ if (cas-success-flag (m_cas_result)) exit
+ goto loop header */
+class cas_to_atomic_op
+{
+public:
+ cas_to_atomic_op (class loop *loop) : m_loop (loop) {}
+
+ bool try_transform ();
+
+protected:
+ /* Decide whether m_desired's RHS matches the op's expected shape. */
+ virtual bool match_op_shape () = 0;
+ /* Builds and splice in the op IFN that replaces the CAS. */
+ virtual void emit_replacement () = 0;
+
+ /* Find the CAS call in m_loop and record it in m_cas_call, along with its
+ captured result in m_cas_result. Returns true on success. The CAS can
+ be either an IFN or a builtin. If the result isn't captured the loop
+ cannot be a CAS loop, so we treat that as failure here. */
+ bool match_cas ();
+
+ /* Validate that the CAS success flag controls the loop's single exit.
+
+ For an IFN CAS the bool is the IMAGPART of the complex result; for a
+ builtin it's the call result directly. An optional BIT_NOT_EXPR may
+ sit between the bool and the gcond (eg. "while (!cas(...))"). The
+ gcond itself must live inside the loop and be the source of its single
+ exit edge. Returns true if all of that holds. */
+ bool match_exit_cond ();
+
+ /* Check that no statement in the loop (other than CAS) has side effects,
+ and that every SSA defined in the loop has all its uses inside the loop.
+
+ One exception is permitted: for an IFN CAS, the REALPART of the CAS
+ result (the value memory held when CAS finally succeeded) is allowed
+ to escape. That value is what a fetch-op call returns to its caller
+ so a post-loop use of it is semantically equivalent to a use of the
+ fetch-op IFN's LHS. This is how emit_replacement will wire it up.
+
+ Returns true if the loop is acceptable. */
+ bool loop_is_self_contained ();
+
+ /* Parse the CAS call's arguments into m_ptr / m_expected / m_desired /
+ m_success_model, and reject any shape we won't handle. */
+ bool parse_cas_arguments ();
+
+ /* Identify the pre-loop __atomic_load that initialised m_expected, so it
+ can be retired once the CAS loop is gone. Sets m_atomic_load if a
+ target is found; leaves it null otherwise. */
+ void find_atomic_load ();
+
+ /* Replace uses of m_cas_result to make the loop always exit.
+ For IFN CAS replace IMAGPART (the success flag) with 1 and REALPART
+ (the observed expected) with m_ifn_result (the new IFN's lhs, or NULL
+ if the REALPART chain didn't escape and no LHS is needed).
+
+ For builtin CAS the result itself is the bool; replace it with 1 directly,
+ and patch any gcond that uses it to an unconditional-exit (true == true)
+ compare. */
+ void replace_cas_uses_for_exit ();
+
+ /* The loop being analysed. Set at construction. */
+ class loop *m_loop;
+
+ /* The CAS call in the loop, and its LHS. For an IFN CAS, m_cas_result
+ is a complex (expected, success-flag); for a builtin CAS it is the
+ bool success flag itself. Set by match_cas. */
+ gcall *m_cas_call = nullptr;
+ tree m_cas_result = NULL_TREE;
+
+ /* For an IFN CAS only: the SSA name extracted from m_cas_result via
+ REALPART_EXPR, if it has uses outside the loop. NULL_TREE if it
+ doesn't escape. Set by loop_is_self_contained via find_expected_out_ssa,
+ and consumed by emit_replacement. */
+ tree m_expected_out = NULL_TREE;
+
+ /* The four CAS operands we care about. Set by parse_cas_arguments.
+ For an IFN CAS, m_expected is an SSA name; for a builtin CAS, m_expected
+ is an addressable VAR_DECL. */
+ tree m_ptr = NULL_TREE;
+ tree m_expected = NULL_TREE;
+ tree m_success_model = NULL_TREE;
+ tree m_desired = NULL_TREE;
+
+ /* The pre-loop atomic_load that initializes 'expected', if one is reachable
+ and has a single use feeding the CAS; NULL if not found.
+ Set by find_atomic_load. */
+ gcall *m_atomic_load = nullptr;
+
+ /* SSA name holding the result of the IFN that replaces the CAS. Set
+ by the derived class's emit_replacement and read in
+ replace_cas_uses_for_exit to rewire post-loop uses of the CAS's expected
+ value. NULL_TREE if the IFN has no LHS (i.e. the expected value doesn't
+ escape the loop). */
+ tree m_ifn_result = NULL_TREE;
+};
+
+/* Specialisation for atomic fetch min/max. */
+
+class cas_to_minmax : public cas_to_atomic_op
+{
+public:
+ using cas_to_atomic_op::cas_to_atomic_op;
+
+private:
+ /* MIN/MAX pattern information. */
+ struct minmax_pattern
+ {
+ enum pattern_type
+ {
+ NONE, /* No MIN/MAX pattern found. */
+ PHI, /* MIN/MAX pattern found in a PHI node from conditional branch. */
+ EXPR /* MIN/MAX pattern found in a MIN_EXPR/MAX_EXPR node. */
+ } type;
+ union
+ {
+ gphi *phi; /* PHI node from a conditional branch. */
+ gassign *assign; /* MIN_EXPR/MAX_EXPR node. */
+ } stmt;
+ /* For PHI patterns, true if the PHI was reached via a MEM_REF dereference
+ in match_minmax_shape. In that case the PHI selects between addresses
+ rather than scalar values, and its ADDR_EXPR arguments must be unwrapped
+ before decode_minmax_phi can run its value comparisons. */
+ bool via_mem_ref;
+ };
+
+ /* Locate the MIN/MAX pattern that sets m_desired and decode it into m_value
+ and m_is_min. */
+ bool match_op_shape () final override;
+ /* Do the transformtion:
+ - build IFN_ATOMIC_FETCH_MINMAX
+ - splice it in before the CAS
+ - rewire CAS uses so the loop's exit condition becomes unconditionally true
+ - drop the CAS itself
+ - if found, retire the pre-loop atomic load. */
+ void emit_replacement () final override;
+
+ /* Trace m_desired to find a MIN/MAX shape (PHI from compare branch, or
+ MIN_EXPR/MAX_EXPR). On success, stores the matched node and which
+ kind it is in m_pattern, and returns true. Returns false if the
+ shape doesn't match. */
+ bool match_minmax_shape ();
+
+ /* Make a call to the correct minmax decoder depending on m_pattern. */
+ bool decode_minmax ();
+
+ /* Decode a MIN_EXPR/MAX_EXPR that sets m_desired. We expect one operand
+ to be m_expected (the value the loop is reading via CAS) and the
+ other to be the value being compared with in. Records the latter in
+ m_value, and sets m_is_min based on which of MIN_EXPR / MAX_EXPR we
+ saw. Returns false if neither operand matches m_expected. */
+ bool decode_minmax_expr (gassign *assign);
+
+ /* Analyze PHI node implementing MIN/MAX selection. m_expected is the value
+ passed to CAS, which is compared against m_value. Use these with the PHI
+ args to determine the operation (MIN or MAX) being performed.
+
+ VIA_MEM_REF is true if match_minmax_shape reached this PHI by following a
+ MEM_REF dereference, i.e. the PHI selects between addresses. In that case
+ the arguments must be ADDR_EXPRs and we unwrap them to recover the
+ underlying values. */
+ bool decode_minmax_phi (gphi *phi);
+
+ /* Try to collapse a PHI of MIN/MAX EXPRs feeding m_desired into a single
+ MIN/MAX <val, expected>. This shape occurs when a CAS loop is implemented
+ using a while-loop + a pre-computed min/max. Sets m_value and m_is_min
+ on success. */
+ bool try_phi_of_minmax (gphi *minmax_phi);
+
+ minmax_pattern m_pattern{minmax_pattern::NONE, {nullptr}, false};
+ tree m_value = NULL_TREE;
+ bool m_is_min = true;
+};
+
+/* Find the CAS call in m_loop and record it in m_cas_call, along with its
+ captured result in m_cas_result. Returns true on success. The CAS can
+ be either an IFN or a builtin. If the result isn't captured the loop
+ cannot be a CAS loop, so we treat that as failure here. */
+bool
+cas_to_atomic_op::match_cas ()
+{
+ basic_block *bbs = get_loop_body (m_loop);
+
+ for (unsigned i = 0; i < m_loop->num_nodes && !m_cas_call; i++)
+ for (gimple_stmt_iterator gsi = gsi_start_bb (bbs[i]); !gsi_end_p (gsi);
+ gsi_next (&gsi))
+ {
+ gimple *stmt = gsi_stmt (gsi);
+ if (gcall *call = dyn_cast<gcall *> (stmt))
+ if (is_atomic_cas_call_p (call))
+ {
+ m_cas_call = call;
+ break;
+ }
+ }
+
+ free (bbs);
+
+ if (!m_cas_call)
+ {
+ DUMP_DETAILS ("reject: no CAS call in loop body\n");
+ return false;
+ }
+
+ /* If there is no LHS, the result was not captured, and this cannot be
+ a CAS loop. */
+ m_cas_result = gimple_call_lhs (m_cas_call);
+ if (!m_cas_result)
+ {
+ DUMP_DETAILS ("reject: CAS result is not captured\n");
+ return false;
+ }
+ return true;
+}
+
+/* Validate that the CAS success flag controls the loop's single exit.
+
+ For an IFN CAS the bool is the IMAGPART of the complex result; for a
+ builtin it's the call result directly. An optional BIT_NOT_EXPR may
+ sit between the bool and the gcond (for "while (!cas(...))"). The
+ gcond itself must live inside the loop and be the source of its single
+ exit edge. Returns true if all of that holds. */
+bool
+cas_to_atomic_op::match_exit_cond ()
+{
+ tree bool_result = NULL_TREE;
+
+ /* Handle IFN. */
+ if (gimple_call_internal_p (m_cas_call, IFN_ATOMIC_COMPARE_EXCHANGE))
+ {
+ /* IFN returns a complex (expected, success_flag); the success flag is
+ extracted via IMAGPART_EXPR. */
+ for (gimple *use_stmt : gather_imm_use_stmts (m_cas_result))
+ if (is_gimple_assign (use_stmt)
+ && gimple_assign_rhs_code (use_stmt) == IMAGPART_EXPR)
+ {
+ bool_result = gimple_assign_lhs (use_stmt);
+ break;
+ }
+ }
+ /* Handle builtin. */
+ else
+ bool_result = m_cas_result;
+
+ if (!bool_result)
+ {
+ DUMP_DETAILS ("reject: no success flag extracted from CAS\n");
+ return false;
+ }
+
+ /* Find THE conditional that uses the bool result. We require exactly
+ one: replace_cas_uses_for_exit will patch this gcond to true==true
+ (forcing the loop to exit) and then remove the CAS itself. With two
+ gconds reading the same bool, reject. */
+ gcond *cond = nullptr;
+ unsigned cond_count = 0;
+ for (gimple *use_stmt : gather_imm_use_stmts (bool_result))
+ {
+ if (gcond *c = dyn_cast<gcond *> (use_stmt))
+ {
+ cond = c;
+ cond_count++;
+ continue;
+ }
+
+ /* Bool might be negated before use. */
+ if (is_gimple_assign (use_stmt)
+ && gimple_assign_rhs_code (use_stmt) == BIT_NOT_EXPR)
+ {
+ tree negated = gimple_assign_lhs (use_stmt);
+ for (gimple *neg_use : gather_imm_use_stmts (negated))
+ if (gcond *c = dyn_cast<gcond *> (neg_use))
+ {
+ cond = c;
+ cond_count++;
+ }
+ }
+ }
+
+ if (cond_count > 1)
+ {
+ DUMP_DETAILS ("reject: CAS success flag is used by multiple gconds\n");
+ return false;
+ }
+
+ if (!cond)
+ {
+ DUMP_DETAILS ("reject: CAS success flag has no controlling"
+ " gcond\n");
+ return false;
+ }
+
+ /* Verify the conditional is in the loop and controls single exit. */
+ basic_block cond_bb = gimple_bb (cond);
+ if (!flow_bb_inside_loop_p (m_loop, cond_bb))
+ {
+ DUMP_DETAILS ("reject: controlling gcond is not in loop\n");
+ return false;
+ }
+
+ edge exit_edge = single_exit (m_loop);
+ if (!exit_edge || exit_edge->src != cond_bb)
+ {
+ DUMP_DETAILS ("reject: gcond does not control the loop's single"
+ " exit\n");
+ return false;
+ }
+
+ return true;
+}
+
+/* Check that no statement in the loop (other than CAS) has side effects,
+ and that every SSA defined in the loop has all its uses inside the loop.
+
+ One exception is permitted: for an IFN CAS, the REALPART of the CAS
+ result (the value memory held when CAS finally succeeded) is allowed
+ to escape. That value is what a fetch-op call returns to its caller
+ so a post-loop use of it is semantically equivalent to a use of the
+ fetch-op IFN's LHS. This is how emit_replacement will wire it up.
+
+ Returns true if the loop is acceptable. */
+
+bool
+cas_to_atomic_op::loop_is_self_contained ()
+{
+ basic_block *bbs = get_loop_body (m_loop);
+ bool reject = false;
+ tree cas_expected = NULL_TREE;
+
+ /* For IFN, check if 'expected' (extracted via REALPART) escapes. */
+ if (gimple_call_internal_p (m_cas_call, IFN_ATOMIC_COMPARE_EXCHANGE))
+ cas_expected = find_expected_out_ssa (m_cas_result, m_loop);
+
+ for (unsigned i = 0; i < m_loop->num_nodes && !reject; i++)
+ {
+ for (gimple_stmt_iterator gsi = gsi_start_bb (bbs[i]); !gsi_end_p (gsi);
+ gsi_next (&gsi))
+ {
+ gimple *stmt = gsi_stmt (gsi);
+
+ /* Skip the CAS call itself. */
+ if (stmt == m_cas_call)
+ continue;
+
+ if (gimple_has_side_effects (stmt))
+ {
+ reject = true;
+ break;
+ }
+
+ /* The only memory write in the loop body must be the CAS. Any
+ other VDEF means the user's loop does work that collapsing to
+ a single atomic op would discard. */
+ if (gimple_vdef (stmt))
+ {
+ reject = true;
+ break;
+ }
+
+ tree lhs = gimple_get_lhs (stmt);
+ if (!lhs)
+ continue;
+
+ /* Allow the tolerated 'expected' escape. */
+ if (cas_expected && lhs == cas_expected)
+ continue;
+
+ if (value_escapes_loop_p (lhs, m_loop))
+ {
+ reject = true;
+ break;
+ }
+ }
+
+ for (gphi_iterator psi = gsi_start_phis (bbs[i]); !gsi_end_p (psi);
+ gsi_next (&psi))
+ {
+ gphi *phi = psi.phi ();
+ tree result = gimple_phi_result (phi);
+
+ if (value_escapes_loop_p (result, m_loop))
+ {
+ reject = true;
+ break;
+ }
+ }
+ }
+
+ free (bbs);
+
+ if (reject)
+ {
+ DUMP_DETAILS ("reject: loop has side effects or an escaping"
+ " value other than CAS's expected\n");
+ return false;
+ }
+
+ m_expected_out = cas_expected;
+ return true;
+}
+
+/* Parse the CAS call's arguments into m_ptr / m_expected / m_desired /
+ m_success_model, and reject any shape we won't handle. */
+bool
+cas_to_atomic_op::parse_cas_arguments ()
+{
+ m_ptr = gimple_call_arg (m_cas_call, 0);
+ m_desired = gimple_call_arg (m_cas_call, 2);
+ m_success_model = gimple_call_arg (m_cas_call, 4);
+ tree failure_model = gimple_call_arg (m_cas_call, 5);
+
+ if (!POINTER_TYPE_P (TREE_TYPE (m_ptr))
+ || !INTEGRAL_TYPE_P (TREE_TYPE (TREE_TYPE (m_ptr))))
+ {
+ DUMP_DETAILS ("reject: CAS ptr does not point to an integer type\n");
+ return false;
+ }
+
+ if (gimple_call_internal_p (m_cas_call, IFN_ATOMIC_COMPARE_EXCHANGE))
+ m_expected = gimple_call_arg (m_cas_call, 1);
+ else
+ {
+ tree expected_ref = gimple_call_arg (m_cas_call, 1);
+
+ /* For builtin form, arg 1 must be a reference to an `expected` variable.
+ A pointer parameter passed straight to the CAS would require
+ more analysis, which is out of scope here. */
+ if (TREE_CODE (expected_ref) != ADDR_EXPR)
+ {
+ DUMP_DETAILS ("reject: builtin CAS expected arg is not"
+ "an ADDR_EXPR\n");
+ return false;
+ }
+ m_expected = TREE_OPERAND (expected_ref, 0);
+ }
+
+ /* The gimplifier may have wrapped this arg in a cast to the operation's
+ unsigned-int form. Peel that to recover the user's actual type before
+ the integer check.
+ I saw at least one instance of incorrect pattern-matching without this
+ in libstdc++. */
+ tree expected_base = get_ssa_base_value (m_expected);
+ if (!INTEGRAL_TYPE_P (TREE_TYPE (expected_base)))
+ {
+ DUMP_DETAILS ("reject: CAS expected is not integer-typed\n");
+ return false;
+ }
+
+ /* The CAS source has separate success/failure memory orders, but the
+ ATOMIC_FETCH_MINMAX IFN encodes a single order. To preserve the
+ CAS's effective ordering we mirror what the CAS expander's rules do:
+ - non-constant order => treat as SEQ_CST
+ - failure > success => success := SEQ_CST
+ - failure is release/acq_rel => success := SEQ_CST
+ and use the resulting success order on the IFN. */
+ bool s_const = TREE_CODE (m_success_model) == INTEGER_CST;
+ bool f_const = TREE_CODE (failure_model) == INTEGER_CST;
+ enum memmodel s = s_const
+ ? memmodel_from_int (tree_to_uhwi (m_success_model))
+ : MEMMODEL_SEQ_CST;
+ enum memmodel f = f_const
+ ? memmodel_from_int (tree_to_uhwi (failure_model))
+ : MEMMODEL_SEQ_CST;
+ if (f > s || is_mm_release (f) || is_mm_acq_rel (f))
+ s = MEMMODEL_SEQ_CST;
+
+ m_success_model = build_int_cst (integer_type_node, s);
+
+ return true;
+}
+
+/* Try to collapse a PHI of MIN/MAX EXPRs feeding m_desired into a single
+ MIN/MAX <val, expected>. This shape occurs when a CAS loop is implemented
+ using a while-loop + a pre-computed min/max. Sets m_value and m_is_min
+ on success. */
+bool
+cas_to_minmax::try_phi_of_minmax (gphi *minmax_phi)
+{
+ /* The shape we're matching is a while-loop with a pre-loop MIN/MAX and
+ an in-loop MIN/MAX recompute, which compiles to two MIN/MAX_EXPRs
+ joined by a PHI. Taking the example of a MIN:
+
+ bb 2 (preheader): bb 3 (failed-CAS recompute):
+ _9 = atomic_load _11 = REALPART of last CAS
+ _10 = MIN_EXPR <val, _9> _12 = MIN_EXPR <val, _11>
+ | |
+ | edge 0 | edge 1
+ v v
+ bb 4 (CAS block):
+ desired = PHI <_10 (edge 0), _12 (edge 1)> <- desired PHI
+ expected = PHI <_9 (edge 0), _11 (edge 1)> <- expected PHI
+ CAS (ptr, expected, desired, ...)
+
+ Here, we cannot take the trivial approach of decode_minmax_expr (which
+ just checks which operand of the MIN_EXPR is m_expected and treats the
+ other one as m_value), because each MIN_EXPR sees a different SSA name
+ for 'expected'.
+
+ Instead, for each PHI edge i, check that the i-th MIN_EXPR's non-val
+ operand equals the i-th argument of the 'expected' PHI. For the example
+ above:
+
+ edge 0: 'desired' PHI's arg is _10, defined by MIN_EXPR <val, _9>.
+ 'expected' PHI's arg on the same edge is _9.
+ _9 appears as an operand of the MIN_EXPR, so the other operand
+ (val) is our m_value candidate for this edge.
+
+ edge 1: 'desired' PHI's arg is _12, defined by MIN_EXPR <val, _11>.
+ 'expected' PHI's arg on the same edge is _11.
+ _11 appears as an operand of the MIN_EXPR, so the other operand
+ (val) is our m_value candidate for this edge.
+
+ Both edges agree on val and on MIN_EXPR, so we can set set m_value = val,
+ m_is_min = true. */
+
+ /* Find the 'expected' PHI. */
+ if (TREE_CODE (m_expected) != SSA_NAME)
+ return false;
+ tree base = get_ssa_base_value (m_expected);
+ if (TREE_CODE (base) != SSA_NAME)
+ return false;
+ gphi *expected_phi = dyn_cast<gphi *> (SSA_NAME_DEF_STMT (base));
+ if (!expected_phi)
+ return false;
+
+ /* Both PHIs must be in the same BB so we can match up their argument
+ edges. */
+ if (gimple_bb (expected_phi) != gimple_bb (minmax_phi))
+ return false;
+
+ unsigned n = gimple_phi_num_args (minmax_phi);
+ if (n < 2 || gimple_phi_num_args (expected_phi) != n)
+ return false;
+
+ /* Across all edges we confirm two facts:
+ - the MIN or MAX op being performed is the same.
+ - the non-'expected' operand is the same on every edge; that operand
+ becomes m_value. */
+ tree_code expected_minmax_code = ERROR_MARK;
+ tree shared_val = NULL_TREE;
+
+ for (unsigned i = 0; i < n; i++)
+ {
+ /* The minmax PHI's argument on this edge must be an SSA name
+ defined by a MIN/MAX gassign. */
+ tree minmax_arg = gimple_phi_arg_def (minmax_phi, i);
+ if (TREE_CODE (minmax_arg) != SSA_NAME)
+ return false;
+ gassign *minmax_def
+ = dyn_cast<gassign *> (SSA_NAME_DEF_STMT (minmax_arg));
+ if (!minmax_def)
+ return false;
+ tree_code code = gimple_assign_rhs_code (minmax_def);
+ if (code != MIN_EXPR && code != MAX_EXPR)
+ return false;
+
+ /* All minmax PHI arguments must use the same code: a PHI joining
+ MIN with MAX is not a fetch_min/max. */
+ if (expected_minmax_code == ERROR_MARK)
+ expected_minmax_code = code;
+ else if (code != expected_minmax_code)
+ return false;
+
+ /* Look up the 'expected' PHI's argument on the same edge. */
+ tree expected_on_edge = gimple_phi_arg_def (expected_phi, i);
+
+ /* One operand of the MIN/MAX must equal that per-edge expected;
+ the other is the candidate for 'val'. */
+ tree op1 = gimple_assign_rhs1 (minmax_def);
+ tree op2 = gimple_assign_rhs2 (minmax_def);
+ tree val_candidate;
+ if (values_equal_p (op1, expected_on_edge))
+ val_candidate = op2;
+ else if (values_equal_p (op2, expected_on_edge))
+ val_candidate = op1;
+ else
+ return false;
+
+ /* The candidate must agree on val across edges. */
+ if (!shared_val)
+ shared_val = val_candidate;
+ else if (!values_equal_p (val_candidate, shared_val))
+ return false;
+ }
+
+ m_value = shared_val;
+ m_is_min = (expected_minmax_code == MIN_EXPR);
+ return true;
+}
+
+/* Locate the MIN/MAX pattern that sets m_desired and decode it into m_value
+ and m_is_min. */
+
+bool
+cas_to_minmax::match_op_shape ()
+{
+ /* CAS loops implemented via a while-loop and a pre-computed MIN/MAX
+ produce a PHI of MIN/MAX_EXPRs feeding m_desired. Handle that
+ shape first; otherwise fall through to the direct MIN/MAX or
+ PHI-from-compare cases. */
+ if (TREE_CODE (m_desired) == SSA_NAME)
+ {
+ tree stripped = get_ssa_base_value (m_desired);
+ if (TREE_CODE (stripped) == SSA_NAME)
+ if (gphi *phi = dyn_cast<gphi *> (SSA_NAME_DEF_STMT (stripped)))
+ if (try_phi_of_minmax (phi))
+ return true;
+ }
+
+ return match_minmax_shape () && decode_minmax ();
+}
+
+/* Trace m_desired to find a MIN/MAX shape (PHI from compare branch, or
+ MIN_EXPR/MAX_EXPR). On success, stores the matched node and which
+ kind it is in m_pattern, and returns true. Returns false if the
+ shape doesn't match. */
+bool
+cas_to_minmax::match_minmax_shape ()
+{
+ m_pattern = {minmax_pattern::NONE, {nullptr}, false};
+
+ if (TREE_CODE (m_desired) != SSA_NAME)
+ {
+ DUMP_DETAILS ("reject: CAS desired is not an SSA name\n");
+ return false;
+ }
+
+ gimple *def_stmt = SSA_NAME_DEF_STMT (m_desired);
+
+ /* Skip casts. */
+ tree stripped = get_ssa_base_value (m_desired);
+ if (TREE_CODE (stripped) == SSA_NAME && stripped != m_desired)
+ def_stmt = SSA_NAME_DEF_STMT (stripped);
+
+ bool followed_mem_ref = false;
+
+ if (is_gimple_assign (def_stmt))
+ {
+ tree_code code = gimple_assign_rhs_code (def_stmt);
+
+ if (code == MIN_EXPR || code == MAX_EXPR)
+ {
+ m_pattern.type = minmax_pattern::EXPR;
+ m_pattern.stmt.assign = as_a<gassign *> (def_stmt);
+ return true;
+ }
+
+ /* Follow MEM_REF to find address PHI. */
+ if (gimple_assign_single_p (def_stmt) && code == MEM_REF)
+ {
+ tree rhs = gimple_assign_rhs1 (def_stmt);
+ tree addr = TREE_OPERAND (rhs, 0);
+ if (TREE_CODE (addr) == SSA_NAME)
+ {
+ def_stmt = SSA_NAME_DEF_STMT (addr);
+ followed_mem_ref = true;
+ }
+ else
+ return false;
+ }
+ }
+
+ if (gimple_code (def_stmt) == GIMPLE_PHI)
+ {
+ m_pattern.type = minmax_pattern::PHI;
+ m_pattern.stmt.phi = as_a<gphi *> (def_stmt);
+ m_pattern.via_mem_ref = followed_mem_ref;
+ return true;
+ }
+
+ DUMP_DETAILS ("reject: CAS desired is not a MIN/MAX expression"
+ " or a PHI from a compare branch\n");
+ return false;
+}
+
+/* Make a call to the correct minmax decoder depending on m_pattern. */
+bool
+cas_to_minmax::decode_minmax ()
+{
+ switch (m_pattern.type)
+ {
+ case minmax_pattern::EXPR:
+ return decode_minmax_expr (m_pattern.stmt.assign);
+ case minmax_pattern::PHI:
+ return decode_minmax_phi (m_pattern.stmt.phi);
+ default:
+ return false;
+ }
+}
+
+/* Decode a MIN_EXPR/MAX_EXPR that sets m_desired. We expect one operand
+ to be m_expected (the value the loop is reading via CAS) and the
+ other to be the value being compared with in. Records the latter in
+ m_value, and sets m_is_min based on which of MIN_EXPR / MAX_EXPR we
+ saw. Returns false if neither operand matches m_expected. */
+
+bool
+cas_to_minmax::decode_minmax_expr (gassign *assign)
+{
+ tree_code code = gimple_assign_rhs_code (assign);
+ if (code != MIN_EXPR && code != MAX_EXPR)
+ return false;
+
+ tree op1 = gimple_assign_rhs1 (assign);
+ tree op2 = gimple_assign_rhs2 (assign);
+
+ if (values_equal_p (op1, m_expected))
+ m_value = op2;
+ else if (values_equal_p (op2, m_expected))
+ m_value = op1;
+ else
+ {
+ DUMP_DETAILS ("reject: MIN/MAX operands don't include CAS's"
+ " expected value\n");
+ return false;
+ }
+
+ m_is_min = (code == MIN_EXPR);
+ return true;
+}
+
+/* Analyze PHI node implementing MIN/MAX selection. m_expected is the value
+ passed to CAS, which is compared against m_value. Use these with the PHI
+ args to determine the operation (MIN or MAX) being performed.
+
+ via_mem_ref is true if match_minmax_shape reached this PHI by following a
+ MEM_REF dereference, i.e. the PHI selects between addresses. In that case
+ the arguments must be ADDR_EXPRs and we unwrap them to recover the
+ underlying values. */
+
+bool
+cas_to_minmax::decode_minmax_phi (gphi *phi)
+{
+ if (gimple_phi_num_args (phi) != 2)
+ {
+ DUMP_DETAILS ("reject: MIN/MAX PHI has != 2 arguments\n");
+ return false;
+ }
+
+ tree arg0 = gimple_phi_arg_def (phi, 0);
+ tree arg1 = gimple_phi_arg_def (phi, 1);
+ edge edge0 = gimple_phi_arg_edge (phi, 0);
+ edge edge1 = gimple_phi_arg_edge (phi, 1);
+
+ /* Unwrap ADDR_EXPRs only when we reached the PHI through a MEM_REF.
+ Doing so unconditionally would theoretically be unsafe: a CAS loop that
+ does something strange (like swapping a pointer) could legitimately have
+ ADDR_EXPR arguments in its PHI without a MEM_REF dereference, and
+ stripping them would not be correct then. */
+ if (m_pattern.via_mem_ref)
+ {
+ if (TREE_CODE (arg0) != ADDR_EXPR || TREE_CODE (arg1) != ADDR_EXPR)
+ {
+ DUMP_DETAILS ("reject: PHI reached through MEM_REF but its"
+ " args are not ADDR_EXPRs\n");
+ return false;
+ }
+ arg0 = TREE_OPERAND (arg0, 0);
+ arg1 = TREE_OPERAND (arg1, 0);
+ }
+
+ basic_block phi_bb = gimple_bb (phi);
+ basic_block dom = get_immediate_dominator (CDI_DOMINATORS, phi_bb);
+ if (!dom)
+ return false;
+
+ gimple_stmt_iterator gsi = gsi_last_nondebug_bb (dom);
+ if (gsi_end_p (gsi))
+ return false;
+
+ gcond *cond = dyn_cast<gcond *> (gsi_stmt (gsi));
+ if (!cond)
+ {
+ DUMP_DETAILS ("reject: PHI's immediate dominator does not end with"
+ " a gcond (the MIN/MAX-from-PHI shape requires the PHI"
+ " to be a select on a compare)\n");
+ return false;
+ }
+
+ tree cond_lhs = gimple_cond_lhs (cond);
+ tree cond_rhs = gimple_cond_rhs (cond);
+ enum tree_code cond_code = gimple_cond_code (cond);
+
+ edge true_edge, false_edge;
+ extract_true_false_edges_from_block (dom, &true_edge, &false_edge);
+
+ /* Skip intermediate empty forwarder blocks. */
+ if (true_edge->dest != phi_bb && single_succ_p (true_edge->dest))
+ true_edge = single_succ_edge (true_edge->dest);
+ if (false_edge->dest != phi_bb && single_succ_p (false_edge->dest))
+ false_edge = single_succ_edge (false_edge->dest);
+
+ /* Map PHI arguments to TRUE/FALSE paths. */
+ tree true_arg, false_arg;
+ if (true_edge == edge0)
+ {
+ true_arg = arg0;
+ false_arg = arg1;
+ }
+ else if (true_edge == edge1)
+ {
+ true_arg = arg1;
+ false_arg = arg0;
+ }
+ else
+ {
+ DUMP_DETAILS ("reject: PHI's incoming edges don't match the"
+ " dominator's true/false edges\n");
+ return false;
+ }
+
+ /* Determine MIN vs MAX based on condition and which value is selected.
+ For "LHS op RHS":
+ - TRUE selects LHS: LT/LE -> MIN, GT/GE -> MAX.
+ - TRUE selects RHS: LT/LE -> MAX, GT/GE -> MIN. */
+ bool is_min;
+ if (values_equal_p (true_arg, cond_lhs)
+ && values_equal_p (false_arg, cond_rhs))
+ is_min = (cond_code == LT_EXPR || cond_code == LE_EXPR);
+ else if (values_equal_p (true_arg, cond_rhs)
+ && values_equal_p (false_arg, cond_lhs))
+ is_min = (cond_code == GT_EXPR || cond_code == GE_EXPR);
+ else
+ {
+ DUMP_DETAILS ("reject: PHI args don't line up with the"
+ " condition's compared values\n");
+ return false;
+ }
+
+ /* The condition is some "lhs cmp rhs" where one side is m_expected and
+ the other is the value being merged in. We don't know which side
+ the user wrote on, so check both orderings. If neither side is
+ m_expected, this isn't the MIN/MAX we're looking for. */
+ tree value;
+ if (values_equal_p (cond_lhs, m_expected))
+ value = cond_rhs;
+ else if (values_equal_p (cond_rhs, m_expected))
+ value = cond_lhs;
+ else
+ {
+ DUMP_DETAILS ("reject: condition doesn't compare against"
+ " CAS's expected value\n");
+ return false;
+ }
+
+ m_value = value;
+ m_is_min = is_min;
+ return true;
+}
+/* Identify the pre-loop __atomic_load that initialised m_expected, so it
+ can be retired once the CAS loop is gone. Sets m_atomic_load if a
+ target is found; leaves it null otherwise. */
+
+void
+cas_to_atomic_op::find_atomic_load ()
+{
+ /* The strategy here is to first trace back m_expected to the 'expected'
+ value that entered the loop from the preheader edge.
+
+ Once we have this value, we can walk the preheader bb in reverse to find
+ where the entering value was defined, the RHS for this statement should
+ give us the load. The method for finding the entering value depends on
+ the type of CAS call:
+ - IFN: M_EXPECTED is an SSA name defined by a PHI at the loop header.
+ The arg on the preheader edge is the entering value.
+ - Builtin form: M_EXPECTED is a memory decl, so there is no PHI. Find
+ the preheader bb, then scan it backwards for the last store to
+ M_EXPECTED, that store's RHS is the entering value.
+
+ It should be OK to pattern-match even if there is no atomic load, CAS might
+ fail but will eventually succeed and model fetch min/max anyway. */
+
+ /* The SSA name flowing into the loop as the initial 'expected' value from
+ the atomic load. */
+ tree entering = NULL_TREE;
+ edge latch = loop_latch_edge (m_loop);
+
+ if (TREE_CODE (m_expected) == SSA_NAME)
+ {
+ /* The IFN's expected argument may be a cast of the loop PHI; unwind
+ to find the PHI itself. */
+ tree phi_lhs = get_ssa_base_value (m_expected);
+ if (TREE_CODE (phi_lhs) != SSA_NAME)
+ return;
+ gphi *phi = dyn_cast<gphi *> (SSA_NAME_DEF_STMT (phi_lhs));
+ if (!phi || gimple_phi_num_args (phi) != 2)
+ return;
+
+ entering
+ = (gimple_phi_arg_edge (phi, 0) == latch ? gimple_phi_arg_def (phi, 1)
+ : gimple_phi_arg_def (phi, 0));
+ }
+ else if (DECL_P (m_expected))
+ {
+ /* loop_preheader_edge asserts flags that need to be set by the pass,
+ looks like it's better to do this? */
+ if (EDGE_COUNT (m_loop->header->preds) != 2)
+ return;
+ edge e0 = EDGE_PRED (m_loop->header, 0);
+ edge e1 = EDGE_PRED (m_loop->header, 1);
+ basic_block preheader = (e0 == latch ? e1->src : e0->src);
+
+ /* The builtin form has no PHI for M_EXPECTED (it's a VAR_DECL, not in
+ SSA), so the entering value is whatever the last preheader store to
+ it wrote. Walk the BB backwards to find that store. */
+ for (gimple_stmt_iterator gsi = gsi_last_bb (preheader); !gsi_end_p
(gsi);
+ gsi_prev (&gsi))
+ {
+ gimple *stmt = gsi_stmt (gsi);
+ if (gimple_assign_single_p (stmt)
+ && operand_equal_p (gimple_assign_lhs (stmt), m_expected, 0))
+ {
+ entering = gimple_assign_rhs1 (stmt);
+ break;
+ }
+ }
+ }
+
+ /* If the entering value isn't an SSA name, there's no atomic_load to
+ trace back to. */
+ if (!entering || TREE_CODE (entering) != SSA_NAME)
+ return;
+
+ tree base = get_ssa_base_value (entering);
+ if (TREE_CODE (base) != SSA_NAME)
+ return;
+
+ gcall *load_call = dyn_cast<gcall *> (SSA_NAME_DEF_STMT (base));
+ if (!load_call || gimple_call_lhs (load_call) != base)
+ return;
+
+ /* Call can be IFN or builtin, but should be atomic load. */
+ tree fndecl = gimple_call_fndecl (load_call);
+ if (!fndecl || !fndecl_built_in_p (fndecl, BUILT_IN_NORMAL))
+ return;
+ enum built_in_function fncode = DECL_FUNCTION_CODE (fndecl);
+ if (fncode < BUILT_IN_ATOMIC_LOAD_N || fncode > BUILT_IN_ATOMIC_LOAD_16)
+ return;
+
+ /* Confirm we have the right load for the atomic pointer we are working
+ with in the CAS call. */
+ if (!operand_equal_p (gimple_call_arg (load_call, 0),
+ gimple_call_arg (m_cas_call, 0), 0))
+ return;
+
+ /* Single use should feed into CAS, anything else means we can't delete
+ the call. */
+ if (!has_single_use (base))
+ return;
+
+ m_atomic_load = load_call;
+}
+
+/* Replace uses of m_cas_result to make the loop's exit condition
+ unconditionally true, so CFG cleanup can fold the exit branch.
+
+ For IFN CAS replace IMAGPART (the success flag) with 1 and REALPART
+ (the observed expected) with m_ifn_result (the new IFN's lhs, or NULL
+ if the REALPART chain didn't escape and no LHS is needed).
+
+ For builtin CAS the result itself is the bool; replace it with 1 directly,
+ and patch any gcond that uses it to an unconditional-exit (true == true)
+ compare. */
+
+void
+cas_to_atomic_op::replace_cas_uses_for_exit ()
+{
+ if (gimple_call_internal_p (m_cas_call, IFN_ATOMIC_COMPARE_EXCHANGE))
+ {
+ /* IFN CAS: m_cas_result is a complex (expected, success-flag) */
+ for (gimple *use_stmt : gather_imm_use_stmts (m_cas_result))
+ {
+ if (!is_gimple_assign (use_stmt))
+ continue;
+
+ tree_code code = gimple_assign_rhs_code (use_stmt);
+ if (code != IMAGPART_EXPR && code != REALPART_EXPR)
+ continue;
+
+ tree lhs = gimple_assign_lhs (use_stmt);
+ tree val;
+
+ if (code == IMAGPART_EXPR)
+ /* success flag: replace with 1 for DCE. */
+ val = build_one_cst (TREE_TYPE (lhs));
+ else if (m_ifn_result)
+ /* expected: set to the IFN's lhs. */
+ val = m_ifn_result;
+ else
+ /* expected: replace with 0 for DCE. */
+ val = build_zero_cst (TREE_TYPE (lhs));
+
+ /* The CAS IFN result's complex element is unsigned; the FETCH_MINMAX
+ IFN's LHS has the operation's datatype (which can be signed).
+ Cast when they differ. */
+ gimple *new_stmt;
+ if (TREE_CODE (val) == SSA_NAME
+ && !useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (val)))
+ new_stmt = gimple_build_assign (lhs, NOP_EXPR, val);
+ else
+ new_stmt = gimple_build_assign (lhs, val);
+ gimple_stmt_iterator use_gsi = gsi_for_stmt (use_stmt);
+ gsi_replace (&use_gsi, new_stmt, true);
+ }
+ return;
+ }
+
+ /* Builtin: replace bool result with 1 (success). */
+ for (gimple *use_stmt : gather_imm_use_stmts (m_cas_result))
+ {
+ gimple_stmt_iterator use_gsi = gsi_for_stmt (use_stmt);
+
+ if (is_gimple_assign (use_stmt))
+ {
+ tree lhs = gimple_assign_lhs (use_stmt);
+ gimple *new_stmt
+ = gimple_build_assign (lhs, build_one_cst (TREE_TYPE (lhs)));
+ gsi_replace (&use_gsi, new_stmt, true);
+ }
+ /* For the controlling gcond, replace with a dummy true==true to
+ force always-exit. */
+ else if (gcond *cond_stmt = dyn_cast<gcond *> (use_stmt))
+ {
+ gimple_cond_set_lhs (cond_stmt, boolean_true_node);
+ gimple_cond_set_rhs (cond_stmt, boolean_true_node);
+ gimple_cond_set_code (cond_stmt, EQ_EXPR);
+ update_stmt (cond_stmt);
+ }
+ }
+}
+
+/* At this point, we can commit to the rewrite:
+ - build IFN_ATOMIC_FETCH_MINMAX
+ - splice it in before the CAS
+ - rewire CAS uses so the loop's exit condition becomes unconditionally true
+ - drop the CAS itself
+ - if found, retire the pre-loop atomic load. */
+
+void
+cas_to_minmax::emit_replacement ()
+{
+ /* Build IFN_ATOMIC_FETCH_MINMAX call. */
+ tree data_type = TREE_TYPE (m_value);
+
+ tree op_code_tree
+ = build_int_cst (integer_type_node, m_is_min ? MIN_EXPR : MAX_EXPR);
+ tree type_arg = build_zero_cst (data_type);
+
+ gcall *ifn_call
+ = gimple_build_call_internal (IFN_ATOMIC_FETCH_MINMAX, 5, m_ptr, m_value,
+ m_success_model, op_code_tree, type_arg);
+ gimple_call_set_nothrow (ifn_call, gimple_call_nothrow_p (m_cas_call));
+
+ cfun->calls_atomic_ifn = 1;
+
+ gimple_stmt_iterator cas_gsi = gsi_for_stmt (m_cas_call);
+ bool is_ifn
+ = gimple_call_internal_p (m_cas_call, IFN_ATOMIC_COMPARE_EXCHANGE);
+
+ /* For IFN CAS: capture return if 'expected' (REALPART) escapes.
+ For builtin CAS: always capture return and store into expected variable,
+ since post-loop reads of expected should get the final value. */
+ if (is_ifn)
+ {
+ if (m_expected_out)
+ {
+ m_ifn_result = make_ssa_name (data_type);
+ gimple_call_set_lhs (ifn_call, m_ifn_result);
+ }
+ }
+ else
+ {
+ m_ifn_result = make_ssa_name (data_type);
+ gimple_call_set_lhs (ifn_call, m_ifn_result);
+ }
+
+ /* Insert FETCH_MINMAX before CAS. */
+ gsi_insert_before (&cas_gsi, ifn_call, GSI_SAME_STMT);
+
+ if (!is_ifn && m_ifn_result)
+ {
+ gimple *store_stmt = gimple_build_assign (m_expected, m_ifn_result);
+ gsi_insert_before (&cas_gsi, store_stmt, GSI_SAME_STMT);
+ }
+
+ /* Fixup CAS uses to make loop exit. */
+ replace_cas_uses_for_exit ();
+
+ /* Remove CAS. */
+ gsi_remove (&cas_gsi, true);
+
+ /* Replace the pre-loop atomic_load with an assignment to zero. */
+ if (m_atomic_load)
+ {
+ gimple_stmt_iterator load_gsi = gsi_for_stmt (m_atomic_load);
+ tree load_lhs = gimple_call_lhs (m_atomic_load);
+ gimple *zero_assign
+ = gimple_build_assign (load_lhs, build_zero_cst (TREE_TYPE (load_lhs)));
+ gsi_replace (&load_gsi, zero_assign, true);
+ }
+
+ if (dump_file)
+ fprintf (dump_file, "%s: rewrote loop %d to atomic %s\n",
+ function_name (cfun), m_loop->num, m_is_min ? "MIN" : "MAX");
+}
+
+bool
+cas_to_atomic_op::try_transform ()
+{
+ DUMP_DETAILS ("%s: trying loop %d\n", function_name (cfun), m_loop->num);
+ if (!match_cas ()
+ || !match_exit_cond ()
+ || !loop_is_self_contained ()
+ || !parse_cas_arguments ()
+ || !match_op_shape ())
+ {
+ DUMP_DETAILS ("%s: loop %d not a fetch-op CAS loop\n",
+ function_name (cfun), m_loop->num);
+ return false;
+ }
+
+ find_atomic_load ();
+ DUMP_DETAILS ("%s: loop %d matched, atomic_load %s\n", function_name (cfun),
+ m_loop->num, m_atomic_load ? "found" : "not found");
+
+ emit_replacement ();
+ return true;
+}
+
+static unsigned int
+transform_cas_loops_to_atomic_op (void)
+{
+ bool changed = false;
+ calculate_dominance_info (CDI_DOMINATORS);
+
+ if (!loops_state_satisfies_p (LOOPS_HAVE_RECORDED_EXITS))
+ record_loop_exits ();
+
+ for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
+ changed |= cas_to_minmax (loop).try_transform ();
+
+ if (changed)
+ return TODO_cleanup_cfg | TODO_update_ssa;
+
+ return 0;
+}
+
+static bool
+gate_transform_cas_loops (void)
+{
+ return optimize >= 2;
+}
+
+const pass_data pass_data_transform_cas_loops_to_atomic_op = {
+ GIMPLE_PASS, /* type */
+ "cas-to-atomic-op", /* name */
+ OPTGROUP_LOOP, /* optinfo_flags */
+ TV_NONE, /* tv_id */
+ (PROP_cfg | PROP_ssa), /* properties_required */
+ 0, /* properties_provided */
+ 0, /* properties_destroyed */
+ 0, /* todo_flags_start */
+ 0 /* todo_flags_finish */
+};
+
+class pass_transform_cas_loops_to_atomic_op : public gimple_opt_pass
+{
+public:
+ pass_transform_cas_loops_to_atomic_op (gcc::context *ctxt)
+ : gimple_opt_pass (pass_data_transform_cas_loops_to_atomic_op, ctxt)
+ {}
+
+ bool gate (function *) final override { return gate_transform_cas_loops (); }
+
+ unsigned int execute (function *) final override
+ {
+ return transform_cas_loops_to_atomic_op ();
+ }
+}; // class pass_transform_cas_loops_to_atomic_op
+
+} // anonymous namespace
+
+gimple_opt_pass *
+make_pass_transform_cas_loops_to_atomic_op (gcc::context *ctxt)
+{
+ return new pass_transform_cas_loops_to_atomic_op (ctxt);
+}
diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
index be51227e6d3..0fcf4fefc25 100644
--- a/gcc/tree-pass.h
+++ b/gcc/tree-pass.h
@@ -423,6 +423,7 @@ extern unsigned int tail_merge_optimize (bool);
extern gimple_opt_pass *make_pass_profile (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_strip_predict_hints (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_lower_atomic_ifn (gcc::context *ctxt);
+extern gimple_opt_pass *make_pass_transform_cas_loops_to_atomic_op
(gcc::context *ctxt);
extern gimple_opt_pass *make_pass_rebuild_frequencies (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_lower_complex_O0 (gcc::context *ctxt);
extern gimple_opt_pass *make_pass_lower_complex (gcc::context *ctxt);
--
2.43.0
