From: Soumya AR <[email protected]>
This patch adds a new pass that recognizes compare-and-swap loops
implementing an atomic fetch min or max, and replaces each one with a
single IFN_ATOMIC_FETCH_MINMAX call, so a target optab can be used
instead.
For example, the following CAS loop implementing fetch_max:
template <typename T>
T atomic_fetch_max (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;
}
has the general shape:
expected = atomic_load (ptr);
loop:
desired = MIN/MAX (expected, value);
success = compare_exchange (ptr, &expected, desired, mem_order);
if (!success) goto loop;
return expected;
and is rewritten to:
return IFN_ATOMIC_FETCH_MINMAX (ptr, value, MIN_EXPR/MAX_EXPR, mem_order);
----
The pass runs at -O2 and above, post-IPA, right after dom2. Running
after IPA lets us check if the backend supports the atomic min/max
optab, before committing to the pattern-matching.
Running after dom2 is useful because for operands passed by reference
(e.g. std::min), SRA turns the memory temporary into an SSA copy inside
the loop, and dom2 propagates that copy so MIN/MAX uses the invariant
value directly. Before dom2, the matcher's invariance checks would
reject the loop for this copy definition.
----
Recognizing a CAS loop:
The CAS can be the IFN form (IFN_ATOMIC_COMPARE_EXCHANGE, which takes
'expected' by value and returns (observed, success)) or the builtin form
(__atomic_compare_exchange_N, which takes &expected). Both are handled
here.
(1) The loop must have a single exit and a single back edge, and every
retry must go through the loop condition. Starting from the exit gcond,
we trace to the CAS, which must succeed exactly when the exit is taken.
(2) For the builtin form, 'expected' must be the address of a variable.
Since the rewrite stores the fetched value back into it, its address
should not escape. To handle this, __atomic_compare_exchange_N gets a
fnspec so passing &expected to it does not by itself count as an escape.
(3) After a failed CAS, the next iteration must use the value that CAS
observed in memory as its new 'expected'.
(4) 'desired' must be MIN/MAX of 'expected' and a value, either directly
or, as in libstdc++'s while-loop, as a PHI of the MIN/MAX computed
before the loop and after each failed CAS. Both must use the same
operation and value.
Validating the transform:
(5) The target must be able to expand the IFN directly.
(6) Every use of the CAS result must be rewritable.
(7) The CAS pointer must be loop invariant.
(8) The MIN/MAX value must be loop invariant.
(9) Nothing else in the loop may have side effects, and only the
observed value may be used outside it.
Rewriting the loop:
The IFN is inserted before the CAS, uses of the CAS result are
rewritten:
- the success flag becomes 1
- for IFNs, the observed value becomes the IFN's result,
- for builtins, the result is stored back into 'expected'
The exit condition is made constant, the CAS is removed, and CFG cleanup
deletes the retry path.
We do not delete the initial atomic load (if any) for now. This will
be handled as a follow-up.
----
Bootstrapped and regression tested on aarch64-linux-gnu and
x86_64-linux-gnu.
Cross-compiled and regression tested for arm-linux-gnueabihf-armv7-a and
aarch64-linux-gnu without LSE.
OK for mainline?
gcc/ChangeLog:
* Makefile.in: Add tree-cas-to-atomic-op.o.
* builtins.cc (builtin_fnspec): Add fnspec for
__atomic_compare_exchange_N.
* passes.def: Add pass_transform_cas_loops_to_atomic_op after
dom2.
* tree-cas-to-atomic-op.cc: New file.
* tree-pass.h (make_pass_transform_cas_loops_to_atomic_op): Declare.
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.
* 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-run-1.c: New test.
Signed-off-by: Soumya AR <[email protected]>
---
gcc/Makefile.in | 1 +
gcc/builtins.cc | 7 +
gcc/passes.def | 1 +
.../g++.dg/tree-ssa/cas-to-minmax-1.C | 48 +
.../g++.dg/tree-ssa/cas-to-minmax-2.C | 31 +
.../gcc.dg/tree-ssa/cas-to-minmax-1.c | 28 +
.../gcc.dg/tree-ssa/cas-to-minmax-2.c | 76 ++
.../gcc.dg/tree-ssa/cas-to-minmax-3.c | 29 +
.../gcc.dg/tree-ssa/cas-to-minmax-4.c | 189 +++
.../gcc.dg/tree-ssa/cas-to-minmax-run-1.c | 212 +++
gcc/tree-cas-to-atomic-op.cc | 1142 +++++++++++++++++
gcc/tree-pass.h | 1 +
12 files changed, 1765 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/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-run-1.c
create mode 100644 gcc/tree-cas-to-atomic-op.cc
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 29b9a73ed6c0..6ddfb7387651 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1804,6 +1804,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/builtins.cc b/gcc/builtins.cc
index 3c7b48940d02..01cf886d1017 100644
--- a/gcc/builtins.cc
+++ b/gcc/builtins.cc
@@ -12843,6 +12843,13 @@ builtin_fnspec (tree callee)
switch (code)
{
+ case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_1:
+ case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_2:
+ case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_4:
+ case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_8:
+ case BUILT_IN_ATOMIC_COMPARE_EXCHANGE_16:
+ return ". . w ";
+
/* All the following functions read memory pointed to by
their second argument and write memory pointed to by first
argument.
diff --git a/gcc/passes.def b/gcc/passes.def
index 9095c134f49d..2f246b79b331 100644
--- a/gcc/passes.def
+++ b/gcc/passes.def
@@ -257,6 +257,7 @@ along with GCC; see the file COPYING3. If not see
trying to move or duplicate pass_dominator somewhere earlier. */
NEXT_PASS (pass_thread_jumps, /*first=*/true);
NEXT_PASS (pass_dominator, true /* may_peel_loop_headers_p */);
+ NEXT_PASS (pass_transform_cas_loops_to_atomic_op);
/* Threading can leave many const/copy propagations in the IL.
Clean them up. Failure to do so well can lead to false
positives from warnings for erroneous code. */
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 000000000000..0ece57ecb5ac
--- /dev/null
+++ b/gcc/testsuite/g++.dg/tree-ssa/cas-to-minmax-1.C
@@ -0,0 +1,48 @@
+// { dg-do compile { target { c++11 && aarch64*-*-* } } }
+// { dg-options "-O2 -fdump-tree-cas-to-atomic-op-optimized" }
+
+#include <atomic>
+
+template <typename T>
+T
+atomic_fetch_min (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 (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<int> (std::atomic<int> *, int,
+ std::memory_order) noexcept;
+// { dg-final { scan-tree-dump "atomic_fetch_min\\<int\\>: rewrote loop
\[0-9\]+ to atomic MIN" "cas-to-atomic-op" } }
+
+template int atomic_fetch_max<int> (std::atomic<int> *, int,
+ std::memory_order) noexcept;
+// { dg-final { scan-tree-dump "atomic_fetch_max\\<int\\>: rewrote loop
\[0-9\]+ to atomic MAX" "cas-to-atomic-op" } }
+
+template unsigned int atomic_fetch_min<unsigned int> (
+ std::atomic<unsigned int> *, unsigned int, std::memory_order) noexcept;
+// { dg-final { scan-tree-dump "atomic_fetch_min\\<unsigned int\\>: rewrote
loop \[0-9\]+ to atomic MIN" "cas-to-atomic-op" } }
+
+template unsigned int atomic_fetch_max<unsigned int> (
+ std::atomic<unsigned int> *, unsigned int, std::memory_order) noexcept;
+// { dg-final { scan-tree-dump "atomic_fetch_max\\<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-2.C
b/gcc/testsuite/g++.dg/tree-ssa/cas-to-minmax-2.C
new file mode 100644
index 000000000000..4e2e9e7d7dad
--- /dev/null
+++ b/gcc/testsuite/g++.dg/tree-ssa/cas-to-minmax-2.C
@@ -0,0 +1,31 @@
+// { dg-do compile { target aarch64*-*-* } }
+// { dg-options "-O2 -fdump-tree-cas-to-atomic-op-optimized" }
+
+#include <algorithm>
+
+int
+cas_std_min (int *ptr, int value)
+{
+ int expected = __atomic_load_n (ptr, __ATOMIC_RELAXED);
+ while (!__atomic_compare_exchange_n (ptr, &expected,
+ std::min (expected, value), 0,
+ __ATOMIC_RELAXED, __ATOMIC_RELAXED))
+ ;
+ return expected;
+}
+// { dg-final { scan-tree-dump "cas_std_min: rewrote loop \[0-9\]+ to atomic
MIN" "cas-to-atomic-op" } }
+
+int
+cas_std_max (int *ptr, int value)
+{
+ int expected = __atomic_load_n (ptr, __ATOMIC_RELAXED);
+ while (!__atomic_compare_exchange_n (ptr, &expected,
+ std::max (expected, value), 0,
+ __ATOMIC_RELAXED, __ATOMIC_RELAXED))
+ ;
+ return expected;
+}
+// { dg-final { scan-tree-dump "cas_std_max: rewrote loop \[0-9\]+ to atomic
MAX" "cas-to-atomic-op" } }
+
+// { dg-final { scan-tree-dump-times "ATOMIC_FETCH_MINMAX" 2
"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 000000000000..439c7edca7d9
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/cas-to-minmax-1.c
@@ -0,0 +1,28 @@
+/* { dg-do compile { target aarch64*-*-* } } */
+/* { dg-options "-O2 -fdump-tree-cas-to-atomic-op-optimized" } */
+
+int
+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;
+}
+/* { dg-final { scan-tree-dump "fetch_min: rewrote loop \[0-9\]+ to atomic
MIN" "cas-to-atomic-op" } } */
+
+int
+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 "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" } } */
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 000000000000..0f7f4a9e1645
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/cas-to-minmax-2.c
@@ -0,0 +1,76 @@
+/* { dg-do compile { target aarch64*-*-* } } */
+/* { dg-options "-O2 -fdump-tree-dom2 -fdump-tree-cas-to-atomic-op-optimized"
} */
+
+int
+min_phi (int *ptr, int val)
+{
+ int expected = __atomic_load_n (ptr, __ATOMIC_RELAXED);
+ int desired = expected < val ? expected : val;
+ while (!__atomic_compare_exchange_n (ptr, &expected, desired, 0,
+ __ATOMIC_SEQ_CST, __ATOMIC_RELAXED))
+ desired = expected < val ? expected : val;
+ return expected;
+}
+/* { dg-final { scan-tree-dump "min_phi: rewrote loop \[0-9\]+ to atomic MIN"
"cas-to-atomic-op" } } */
+
+int
+min_do_while (int *ptr, int val)
+{
+ int expected = __atomic_load_n (ptr, __ATOMIC_RELAXED);
+ int success;
+ do
+ {
+ int desired = expected < val ? expected : val;
+ success
+ = __atomic_compare_exchange_n (ptr, &expected, desired, 0,
+ __ATOMIC_SEQ_CST, __ATOMIC_RELAXED);
+ }
+ while (success != 1);
+ return expected;
+}
+/* { dg-final { scan-tree-dump "min_do_while: rewrote loop \[0-9\]+ to atomic
MIN" "cas-to-atomic-op" } } */
+
+int
+min_no_initial_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 "min_no_initial_load: rewrote loop \[0-9\]+ to
atomic MIN" "cas-to-atomic-op" } } */
+
+void
+min_result_unused (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 "min_result_unused: rewrote loop \[0-9\]+ to
atomic MIN" "cas-to-atomic-op" } } */
+
+__attribute__ ((noinline)) int
+read_expected (const int *ptr)
+{
+ return *ptr;
+}
+
+/* Exercise the builtin path by keeping 'expected' addressable. */
+int
+min_builtin (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 read_expected (&expected);
+}
+/* { dg-final { scan-tree-dump "__atomic_compare_exchange_4" "dom2" } } */
+/* { dg-final { scan-tree-dump "min_builtin: rewrote loop \[0-9\]+ to atomic
MIN" "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 000000000000..904dc0c58ccf
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/cas-to-minmax-3.c
@@ -0,0 +1,29 @@
+/* { dg-do compile { target aarch64*-*-* } } */
+/* { dg-options "-O2 -Wno-invalid-memory-model
-fdump-tree-cas-to-atomic-op-optimized" } */
+
+#define FETCH_MIN(NAME, SUCC, FAIL)
\
+ int NAME (int *ptr, int val)
\
+ {
\
+ int expected = __atomic_load_n (ptr, __ATOMIC_RELAXED);
\
+ while (!__atomic_compare_exchange_n (ptr, &expected,
\
+ expected < val ? expected : val, 0, \
+ SUCC, FAIL)) \
+ ;
\
+ return expected;
\
+ }
+
+FETCH_MIN (relaxed_relaxed, __ATOMIC_RELAXED, __ATOMIC_RELAXED) /* 0 */
+FETCH_MIN (acquire_relaxed, __ATOMIC_ACQUIRE, __ATOMIC_RELAXED) /* 2 */
+FETCH_MIN (acquire_acquire, __ATOMIC_ACQUIRE, __ATOMIC_ACQUIRE) /* 2 */
+FETCH_MIN (release_relaxed, __ATOMIC_RELEASE, __ATOMIC_RELAXED) /* 3 */
+FETCH_MIN (acq_rel_acquire, __ATOMIC_ACQ_REL, __ATOMIC_ACQUIRE) /* 4 */
+FETCH_MIN (seq_cst_relaxed, __ATOMIC_SEQ_CST, __ATOMIC_RELAXED) /* 5 */
+FETCH_MIN (seq_cst_seq_cst, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST) /* 5 */
+FETCH_MIN (relaxed_acquire, __ATOMIC_RELAXED, __ATOMIC_ACQUIRE) /* 5 */
+
+/* { dg-final { scan-tree-dump-times "rewrote loop" 8 "cas-to-atomic-op" } } */
+/* { dg-final { scan-tree-dump-times {\.ATOMIC_FETCH_MINMAX \([^;]*, 0\);} 1
"cas-to-atomic-op" } } */
+/* { dg-final { scan-tree-dump-times {\.ATOMIC_FETCH_MINMAX \([^;]*, 2\);} 2
"cas-to-atomic-op" } } */
+/* { dg-final { scan-tree-dump-times {\.ATOMIC_FETCH_MINMAX \([^;]*, 3\);} 1
"cas-to-atomic-op" } } */
+/* { dg-final { scan-tree-dump-times {\.ATOMIC_FETCH_MINMAX \([^;]*, 4\);} 1
"cas-to-atomic-op" } } */
+/* { dg-final { scan-tree-dump-times {\.ATOMIC_FETCH_MINMAX \([^;]*, 5\);} 3
"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 000000000000..b591a3838506
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/cas-to-minmax-4.c
@@ -0,0 +1,189 @@
+/* { dg-do compile { target aarch64*-*-* } } */
+/* { dg-options "-O2 -fdump-tree-cas-to-atomic-op-details" } */
+
+/* Negative tests. */
+
+extern void log_attempt (int);
+extern void escape (int *);
+
+void
+side_effects (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);
+}
+/* { dg-final { scan-tree-dump "side_effects: reject: loop has side effects"
"cas-to-atomic-op" } } */
+
+void
+exit_on_failure (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 "exit_on_failure: reject: no viable CAS loop
found" "cas-to-atomic-op" } } */
+
+int
+unrelated_retry (int *ptr, int val, int retry)
+{
+ 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))
+ expected = retry;
+ return expected;
+}
+/* { dg-final { scan-tree-dump "unrelated_retry: reject: retry expected does
not come from failed CAS" "cas-to-atomic-op" } } */
+
+int
+stale_expected (int *ptr, int val)
+{
+ int expected = __atomic_load_n (ptr, __ATOMIC_RELAXED);
+ int stale = expected;
+ while (!__atomic_compare_exchange_n (ptr, &expected,
+ stale < val ? stale : val, 0,
+ __ATOMIC_SEQ_CST, __ATOMIC_RELAXED))
+ ;
+ return expected;
+}
+/* { dg-final { scan-tree-dump "stale_expected: reject: no viable MIN/MAX
operation found" "cas-to-atomic-op" } } */
+
+void
+mismatched_widths (int *int_ptr, short *short_ptr, int val)
+{
+ int int_expected = __atomic_load_n (int_ptr, __ATOMIC_RELAXED);
+ while (!__atomic_compare_exchange_n (int_ptr, &int_expected,
+ (short) int_expected < (short) val
+ ? int_expected
+ : val,
+ 0, __ATOMIC_SEQ_CST, __ATOMIC_RELAXED))
+ ;
+
+ short short_expected = __atomic_load_n (short_ptr, __ATOMIC_RELAXED);
+ while (!__atomic_compare_exchange_n (short_ptr, &short_expected,
+ (int) short_expected < val
+ ? short_expected
+ : (short) val,
+ 0, __ATOMIC_SEQ_CST, __ATOMIC_RELAXED))
+ ;
+}
+/* { dg-final { scan-tree-dump-times "mismatched_widths: reject: no viable
MIN/MAX operation found" 2 "cas-to-atomic-op" } } */
+
+void
+varying_pointer (int *first, int *second, int val)
+{
+ int *ptr = first;
+ 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))
+ ptr = second;
+}
+/* { dg-final { scan-tree-dump "varying_pointer: reject: CAS pointer is not
loop invariant" "cas-to-atomic-op" } } */
+
+int
+varying_value (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))
+ --val;
+ return expected;
+}
+/* { dg-final { scan-tree-dump "varying_value: reject: MIN/MAX value is not
loop invariant" "cas-to-atomic-op" } } */
+
+/* A retry path reaches the latch without testing whether the CAS succeeded.
*/
+int
+retry_skips_test (int *ptr, int val, int skip)
+{
+ int expected = __atomic_load_n (ptr, __ATOMIC_RELAXED);
+ while (1)
+ {
+ if (skip-- > 0)
+ continue;
+ if (__atomic_compare_exchange_n (ptr, &expected,
+ expected < val ? expected : val, 0,
+ __ATOMIC_SEQ_CST, __ATOMIC_RELAXED))
+ break;
+ }
+ return expected;
+}
+/* { dg-final { scan-tree-dump "retry_skips_test: reject: no viable CAS loop
found" "cas-to-atomic-op" } } */
+
+int expected_global;
+
+int
+expected_may_alias (int *ptr, int val)
+{
+ expected_global = __atomic_load_n (ptr, __ATOMIC_RELAXED);
+ while (
+ !__atomic_compare_exchange_n (ptr, &expected_global,
+ expected_global < val ? expected_global : val,
+ 0, __ATOMIC_SEQ_CST, __ATOMIC_RELAXED))
+ ;
+ return expected_global;
+}
+/* { dg-final { scan-tree-dump "expected_may_alias: reject: CAS arguments are
not supported" "cas-to-atomic-op" } } */
+
+__attribute__ ((optimize ("no-inline-atomics"))) int
+no_inline_atomics (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-not "Function no_inline_atomics"
"cas-to-atomic-op" } } */
+
+extern int atomic_object, shared_expected;
+
+int
+expected_shared (int val)
+{
+ while (!__atomic_compare_exchange_n (&atomic_object, &shared_expected,
+ shared_expected < val ? shared_expected
: val,
+ 0, __ATOMIC_RELEASE, __ATOMIC_RELAXED))
+ ;
+ return shared_expected;
+}
+/* { dg-final { scan-tree-dump "expected_shared: reject: CAS arguments are not
supported" "cas-to-atomic-op" } } */
+
+int
+expected_escaped (int *ptr, int val)
+{
+ int expected = __atomic_load_n (ptr, __ATOMIC_RELAXED);
+ escape (&expected);
+ while (!__atomic_compare_exchange_n (ptr, &expected,
+ expected < val ? expected : val, 0,
+ __ATOMIC_RELEASE, __ATOMIC_RELAXED))
+ ;
+ return expected;
+}
+/* { dg-final { scan-tree-dump "expected_escaped: reject: CAS arguments are
not supported" "cas-to-atomic-op" } } */
+
+int
+numeric_conversion (int *ptr, int val, float initial)
+{
+ float expected = initial;
+ int desired;
+ do
+ {
+ float tmp = expected;
+ int converted = (int) tmp;
+ desired = converted < val ? converted : val;
+ }
+ while (!__atomic_compare_exchange_n (ptr, (int *) &expected, desired, 0,
+ __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST));
+ return val;
+}
+/* { dg-final { scan-tree-dump "numeric_conversion: reject: no viable MIN/MAX
operation found" "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-run-1.c
b/gcc/testsuite/gcc.dg/tree-ssa/cas-to-minmax-run-1.c
new file mode 100644
index 000000000000..a77fb3786e13
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/cas-to-minmax-run-1.c
@@ -0,0 +1,212 @@
+/* { dg-do run { target aarch64*-*-* } } */
+/* { dg-options "-O2 -fdump-tree-dom2 -fdump-tree-cas-to-atomic-op-optimized"
} */
+
+extern void abort (void);
+
+int
+atomic_fetch_min_signed (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_signed (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;
+}
+
+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;
+}
+
+unsigned val_min;
+unsigned val_max;
+
+int
+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
+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;
+}
+
+__attribute__ ((noinline)) int
+read_expected (const int *ptr)
+{
+ return *ptr;
+}
+
+/* Exercise the builtin path by keeping 'expected' addressable. */
+__attribute__ ((noinline)) int
+min_builtin (int *ptr, int val, int initial)
+{
+ int expected = initial;
+ while (!__atomic_compare_exchange_n (ptr, &expected,
+ expected < val ? expected : val, 0,
+ __ATOMIC_SEQ_CST, __ATOMIC_RELAXED))
+ ;
+ return read_expected (&expected);
+}
+/* { dg-final { scan-tree-dump-times "__atomic_compare_exchange_4" 1 "dom2" }
} */
+
+int
+main (void)
+{
+ {
+ int object = 10;
+ if (min_builtin (&object, 3, 10) != 10 || object != 3)
+ abort ();
+
+ object = 10;
+ if (min_builtin (&object, 3, 0) != 10 || object != 3)
+ abort ();
+
+ object = 10;
+ if (min_builtin (&object, 15, 10) != 10 || object != 10)
+ abort ();
+ }
+
+ {
+ int x;
+ int old;
+
+ x = 10;
+ old = atomic_fetch_min_signed (&x, 5);
+ if (old != 10 || x != 5)
+ abort ();
+
+ x = 10;
+ old = atomic_fetch_min_signed (&x, 15);
+ if (old != 10 || x != 10)
+ abort ();
+
+ x = 10;
+ old = atomic_fetch_max_signed (&x, 20);
+ if (old != 10 || x != 20)
+ abort ();
+
+ x = 10;
+ old = atomic_fetch_max_signed (&x, 5);
+ if (old != 10 || x != 10)
+ abort ();
+
+ x = -5;
+ old = atomic_fetch_min_signed (&x, -10);
+ if (old != -5 || x != -10)
+ abort ();
+
+ x = -10;
+ old = atomic_fetch_max_signed (&x, -5);
+ if (old != -10 || x != -5)
+ abort ();
+
+ x = 20;
+ old = atomic_fetch_min_signed (&x, 20);
+ if (old != 20 || x != 20)
+ abort ();
+
+ x = 20;
+ old = atomic_fetch_max_signed (&x, 20);
+ if (old != 20 || x != 20)
+ abort ();
+ }
+
+ {
+ unsigned int x;
+ unsigned int old;
+ volatile unsigned int min_value = 0u;
+ volatile unsigned int max_value = 0xFFFFFFFFu;
+
+ 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, min_value);
+ if (old != 0xFFFFFFFFu || x != 0u)
+ abort ();
+
+ x = 0u;
+ old = atomic_fetch_max_unsigned (&x, max_value);
+ if (old != 0u || x != 0xFFFFFFFFu)
+ abort ();
+ }
+
+ {
+ 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-times "rewrote loop" 23 "cas-to-atomic-op" } }
*/
+/* { dg-final { scan-tree-dump-not "ATOMIC_COMPARE_EXCHANGE"
"cas-to-atomic-op" } } */
+/* { dg-final { scan-tree-dump-not "__atomic_compare_exchange"
"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 000000000000..9c97ee43c28c
--- /dev/null
+++ b/gcc/tree-cas-to-atomic-op.cc
@@ -0,0 +1,1142 @@
+/* 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 recognizes CAS loops implementing an atomic fetch-op and rewrites
+each one to a single IFN call.
+
+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 cas_to_atomic_op base class handles the common CAS loop analysis and
+rewrite. Derived classes handle op-specific analysis. */
+
+#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 "dumpfile.h"
+#include "ssa.h"
+#include "gimple-iterator.h"
+#include "tree-cfg.h"
+#include "cfganal.h"
+#include "tree-ssa.h"
+#include "tree-ssa-alias.h"
+#include "cfgloop.h"
+#include "fold-const.h"
+#include "internal-fn.h"
+#include "memmodel.h"
+#include "tree-ssa-loop-ivopts.h"
+#include "atomic-ifn-lowering.h"
+
+namespace {
+
+/* Return the value underlying NAME, looking through operations that do
+ not change it:
+
+ - an integer conversion that keeps the precision (only the
+ signedness changes) is followed to its operand.
+ - a copy from another SSA name is followed.
+ - a load from a VAR_DECL or PARM_DECL ends the walk: the decl is
+ returned and the load's VUSE is stored in *VUSE_OUT, so callers can
+ tell loads from different memory states apart.
+ - anything else ends the walk and NAME is returned unchanged. */
+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 integer conversions that keep the precision, i.e. that only
+ change signedness. Other conversions change the value, so they end
+ the walk. */
+ if (is_gimple_assign (def_stmt)
+ && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt))
+ && INTEGRAL_TYPE_P (TREE_TYPE (name))
+ && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (def_stmt)))
+ && (TYPE_PRECISION (TREE_TYPE (name))
+ == TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (def_stmt)))))
+ return get_ssa_base_value (gimple_assign_rhs1 (def_stmt), vuse_out);
+
+ /* Follow simple copies. For example, _4 = _3. */
+ if (gimple_assign_ssa_name_copy_p (def_stmt))
+ return get_ssa_base_value (gimple_assign_rhs1 (def_stmt), vuse_out);
+
+ /* The walk ends at a load from a VAR_DECL or PARM_DECL, e.g. _3 = x.
+ Return the decl and record the load's VUSE so the caller can tell two
+ loads of the same decl apart. */
+ if (gimple_assign_single_p (def_stmt))
+ {
+ tree rhs = gimple_assign_rhs1 (def_stmt);
+ if (TREE_CODE (rhs) == VAR_DECL || TREE_CODE (rhs) == PARM_DECL)
+ {
+ if (vuse_out)
+ *vuse_out = gimple_vuse (def_stmt);
+ return rhs;
+ }
+ }
+
+ return name;
+}
+
+/* Return true if A and B are integers with the same precision. */
+static bool
+same_integer_precision_p (tree a, tree b)
+{
+ tree type_a = TREE_TYPE (a);
+ tree type_b = TREE_TYPE (b);
+ return (INTEGRAL_TYPE_P (type_a) && INTEGRAL_TYPE_P (type_b)
+ && TYPE_PRECISION (type_a) == TYPE_PRECISION (type_b));
+}
+
+/* Compare two values for equality, following SSA copies and casts.
+
+ If either side ends at a load from memory, require both sides to be loads
+ from the same memory version. */
+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;
+
+ return ((!vuse_a && !vuse_b) || (vuse_a && vuse_b && vuse_a == vuse_b));
+}
+
+/* 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;
+
+ 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;
+
+ 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;
+}
+
+class cas_to_atomic_op
+{
+public:
+ cas_to_atomic_op (class loop *loop) : m_loop (loop) {}
+
+ bool try_transform ();
+
+protected:
+ bool reject (const char *reason) const;
+
+ /* Trace back the loop's gcond to find the CAS instruction. For an IFN,
+ success is extracted via IMAGPART_EXPR, for a builtin it is the direct
+ result. There can be one optional cast to bool. */
+ bool match_cas_loop ();
+
+ /* 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 ();
+
+ /* Match how a failed CAS provides the updated value for the next retry.
+
+ For an IFN CAS, expected is part of the loop-header PHI. Its latch
+ input should come from the REALPART_EXPR of this CAS's result.
+ Additionally, record the PHI in m_expected_phi and the extracted
+ value in m_observed_value.
+
+ A builtin CAS updates expected through memory instead. Therefore, its
+ VDEF must flow through the loop latch to its next VUSE. */
+ bool match_retry_value ();
+
+ /* For an IFN CAS, match the observed value that escapes the loop, if any,
+ and record it in m_loop_result. */
+ bool match_loop_result ();
+
+ /* Decide whether m_desired's RHS matches the op's expected shape. */
+ virtual bool match_op_shape () = 0;
+
+ /* Return true if VALUE is the expected value read by the CAS. */
+ bool expected_value_p (tree value) const;
+
+ /* Return true if every immediate use of m_cas_result can be preserved
+ when the CAS is replaced.
+
+ An IFN result may only be used by REALPART_EXPR and IMAGPART_EXPR
+ extractions. A builtin result may control the matched exit directly or
+ flow through an SSA copy or cast. Reject any other use, since it would
+ remain dependent on the removed CAS result. */
+ bool cas_result_uses_rewritable_p () const;
+
+ /* 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, m_loop_result is allowed
+ to escape. That value is what a fetch-op call returns to its caller,
+ so emit_replacement can replace it with the fetch-op IFN's LHS. */
+ bool loop_self_contained_p () const;
+
+ /* Return true if the CAS pointer has the same value on every iteration. */
+ bool cas_pointer_invariant_p () const;
+
+ /* Return true if the value supplied to the operation is the same on every
+ retry. */
+ virtual bool operation_value_invariant_p () const = 0;
+
+ /* Return true if the IFN replacing the CAS needs a result. A builtin CAS
+ stores the result back into expected, and an IFN CAS needs it when the
+ observed value escapes the loop. */
+ bool replacement_needs_result_p () const;
+
+ /* Return true if the target can expand the replacement IFN directly, so
+ that gimple-isel will not lower it back to a CAS loop. */
+ virtual bool can_expand_directly_p () const = 0;
+
+ /* Rewrite uses of m_cas_result before removing the CAS. */
+ void rewrite_cas_result_uses ();
+
+ /* Build and insert the atomic IFN that replaces the CAS. */
+ virtual void emit_replacement () = 0;
+
+ /* The loop being analyzed. */
+ 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. */
+ gcall *m_cas_call = nullptr;
+ tree m_cas_result = NULL_TREE;
+
+ /* The four CAS operands we care about.
+ 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_desired = NULL_TREE;
+ tree m_success_model = NULL_TREE;
+
+ /* The loop's controlling condition, and whether loop exit is taken when
+ the condition is true. */
+ gcond *m_exit_cond = nullptr;
+ bool m_exit_on_true = false;
+
+ /* For an IFN CAS only: the loop-header PHI that defines m_expected.
+ Builtin CAS forms carry expected through memory and leave this null. */
+ gphi *m_expected_phi = nullptr;
+
+ /* For an IFN CAS only: the value extracted from m_cas_result through the
+ REALPART_EXPR that provides the expected value on retry. */
+ tree m_observed_value = NULL_TREE;
+
+ /* For an IFN CAS only: m_observed_value or an immediate cast of it that
+ escapes the loop. NULL_TREE if the observed value does not escape. */
+ tree m_loop_result = NULL_TREE;
+
+ /* SSA name holding the result of the IFN that replaces the CAS. */
+ tree m_ifn_result = NULL_TREE;
+};
+
+/* Specialization 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:
+ /* 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;
+ /* 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 against. 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);
+
+ /* 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);
+
+ /* Decode the MIN/MAX expression reaching MINMAX_PHI along INCOMING. One
+ operand must be reaching m_expected_phi through INCOMING, the other
+ operand becomes VALUE. */
+ bool match_minmax_on_edge (gphi *minmax_phi, edge incoming, tree_code &code,
+ tree &value);
+
+ /* Return true if m_value is the same on every retry. */
+ bool operation_value_invariant_p () const final override;
+
+ /* Return true if the target can expand the IFN_ATOMIC_FETCH_MINMAX call
+ built by emit_replacement directly. */
+ bool can_expand_directly_p () const final override;
+
+ void emit_replacement () final override;
+
+ tree m_value = NULL_TREE;
+ bool m_is_min = true;
+};
+
+bool
+cas_to_atomic_op::reject (const char *reason) const
+{
+ if (dump_enabled_p ())
+ dump_printf (MSG_NOTE, "%s: reject: %s (loop %d)\n",
+ current_function_name (), reason, m_loop->num);
+ return false;
+}
+
+/* Trace back the loop's gcond to find the CAS instruction. For an IFN,
+ success is extracted via IMAGPART_EXPR, for a builtin it is the direct
+ result. There can be one optional cast to bool. */
+
+bool
+cas_to_atomic_op::match_cas_loop ()
+{
+ /* The CAS's success must be the only way out of the loop, and every
+ retry must pass through that test. Otherwise the loop can finish
+ without writing, or retry without checking whether the CAS
+ succeeded. */
+ edge exit_edge = single_exit (m_loop);
+ if (!exit_edge || !m_loop->latch
+ || !dominated_by_p (CDI_DOMINATORS, m_loop->latch, exit_edge->src))
+ return false;
+
+ /* Verify that the statement controlling the loop's exit is a gcond
+ that compares against zero. */
+ gcond *cond = safe_dyn_cast<gcond *> (*gsi_last_bb (exit_edge->src));
+ if (!cond
+ || (gimple_cond_code (cond) != EQ_EXPR
+ && gimple_cond_code (cond) != NE_EXPR)
+ || !integer_zerop (gimple_cond_rhs (cond)))
+ return false;
+
+ tree bool_result = gimple_cond_lhs (cond);
+ if (TREE_CODE (bool_result) != SSA_NAME)
+ return false;
+
+ tree value = bool_result;
+
+ /* Check for an optional cast to bool. */
+ gimple *stmt = SSA_NAME_DEF_STMT (value);
+ if (is_gimple_assign (stmt)
+ && CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (stmt))
+ && TREE_CODE (TREE_TYPE (value)) == BOOLEAN_TYPE)
+ {
+ value = gimple_assign_rhs1 (stmt);
+ if (TREE_CODE (value) != SSA_NAME || !has_single_use (value))
+ return false;
+ stmt = SSA_NAME_DEF_STMT (value);
+ }
+
+ /* For an IFN CAS, trace the success flag through IMAGPART_EXPR. */
+ bool is_ifn = (is_gimple_assign (stmt)
+ && gimple_assign_rhs_code (stmt) == IMAGPART_EXPR);
+ if (is_ifn)
+ {
+ value = TREE_OPERAND (gimple_assign_rhs1 (stmt), 0);
+ if (TREE_CODE (value) != SSA_NAME)
+ return false;
+ stmt = SSA_NAME_DEF_STMT (value);
+ }
+
+ gcall *call = dyn_cast<gcall *> (stmt);
+ if (!call || !is_atomic_cas_call_p (call)
+ || is_ifn != gimple_call_internal_p (call, IFN_ATOMIC_COMPARE_EXCHANGE)
+ || !gimple_bb (call) || !flow_bb_inside_loop_p (m_loop, gimple_bb
(call)))
+ return false;
+
+ m_cas_call = call;
+ m_cas_result = gimple_call_lhs (m_cas_call);
+
+ /* Determine whether the comparison is true when the CAS succeeds.
+ != 0 is true on success, while == 0 is true on failure. */
+ bool cond_true_on_success = gimple_cond_code (cond) == NE_EXPR;
+
+ edge true_edge, false_edge;
+ extract_true_false_edges_from_block (exit_edge->src, &true_edge,
&false_edge);
+ edge success_edge = cond_true_on_success ? true_edge : false_edge;
+ if (success_edge != exit_edge)
+ return false;
+
+ m_exit_cond = cond;
+ m_exit_on_true = exit_edge == true_edge;
+ 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))))
+ 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 passed straight to the CAS would require more analysis,
+ which is out of scope for now. */
+ if (TREE_CODE (expected_ref) != ADDR_EXPR)
+ return false;
+
+ /* After replacement, we store the fetched value back into 'expected'.
+ If 'expected' overlaps with the atomic location (arg 0), that store
+ would clobber the value just written by the operation. */
+ if (ptr_derefs_may_alias_p (m_ptr, expected_ref))
+ return false;
+
+ /* After replacement, we introduce a new store of the fetched value into
+ 'expected'. Make sure 'expected' is a local variable whose address
+ does not escape, so no other thread can race with that store. */
+ m_expected = TREE_OPERAND (expected_ref, 0);
+ tree base = get_base_address (m_expected);
+ if (!base || !DECL_P (base) || is_global_var (base))
+ return false;
+
+ pt_solution pt = {};
+ pt.escaped = 1;
+ pt.ipa_escaped = flag_ipa_pta != 0;
+ if (pt_solution_includes (&pt, base))
+ 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, mirror the CAS expander's rules:
+ - constant valid orders => retain the success order
+ - non-constant success/failure => use SEQ_CST
+ - failure > success => use SEQ_CST
+ - failure is release/acq_rel => use SEQ_CST */
+ 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;
+}
+
+/* Match how a failed CAS provides the updated value for the next retry.
+
+ For an IFN CAS, expected is part of the loop-header PHI. Its latch
+ input should come from the REALPART_EXPR of this CAS's result.
+ Additionally, record the PHI in m_expected_phi and the extracted
+ value in m_observed_value.
+
+ A builtin CAS updates expected through memory instead. Therefore, its
+ VDEF must flow through the loop latch to its next VUSE. */
+bool
+cas_to_atomic_op::match_retry_value ()
+{
+ edge latch = loop_latch_edge (m_loop);
+
+ if (gimple_call_internal_p (m_cas_call, IFN_ATOMIC_COMPARE_EXCHANGE))
+ {
+ tree phi_result = get_ssa_base_value (m_expected);
+
+ if (TREE_CODE (phi_result) != SSA_NAME)
+ return false;
+
+ gphi *expected_phi = dyn_cast<gphi *> (SSA_NAME_DEF_STMT (phi_result));
+ if (!expected_phi)
+ return false;
+
+ if (gimple_bb (expected_phi) != m_loop->header)
+ return false;
+
+ m_expected_phi = expected_phi;
+
+ /* If the SSA name feeding the PHI from the latch is derived from this
+ CAS result's REALPART_EXPR, we can confirm that the retry and observed
+ values line up. */
+ tree retry = gimple_phi_arg_def_from_edge (m_expected_phi, latch);
+ tree observed = get_ssa_base_value (retry);
+
+ if (TREE_CODE (observed) != SSA_NAME)
+ return false;
+
+ gimple *observed_def = SSA_NAME_DEF_STMT (observed);
+ if (!is_gimple_assign (observed_def)
+ || gimple_assign_rhs_code (observed_def) != REALPART_EXPR)
+ return false;
+
+ tree realpart = gimple_assign_rhs1 (observed_def);
+ if (TREE_OPERAND (realpart, 0) != m_cas_result)
+ return false;
+
+ m_observed_value = observed;
+ return true;
+ }
+
+ /* A builtin CAS writes the observed value through its expected argument.
+ The PHI at the loop header should carry this CAS's VDEF through
+ the backedge. */
+ tree cas_vuse = gimple_vuse (m_cas_call);
+ tree cas_vdef = gimple_vdef (m_cas_call);
+
+ if (!cas_vuse || !cas_vdef)
+ return false;
+
+ if (TREE_CODE (cas_vuse) != SSA_NAME)
+ return false;
+
+ gphi *vphi = dyn_cast<gphi *> (SSA_NAME_DEF_STMT (cas_vuse));
+ if (!vphi || gimple_bb (vphi) != m_loop->header)
+ return false;
+
+ tree retry_vdef = gimple_phi_arg_def_from_edge (vphi, latch);
+ if (retry_vdef != cas_vdef)
+ return false;
+
+ return true;
+}
+
+/* For an IFN CAS, match the observed value that escapes the loop, if any,
+ and record it in m_loop_result. The escaping value can be
+ m_observed_value itself or the result of an immediate cast. A builtin CAS
+ writes its observed value through m_expected and has no result to record
+ here. */
+bool
+cas_to_atomic_op::match_loop_result ()
+{
+ if (!gimple_call_internal_p (m_cas_call, IFN_ATOMIC_COMPARE_EXCHANGE))
+ return true;
+
+ gcc_assert (m_observed_value);
+
+ if (value_escapes_loop_p (m_observed_value, m_loop))
+ m_loop_result = m_observed_value;
+
+ for (gimple *use_stmt : gather_imm_use_stmts (m_observed_value))
+ {
+ if (!gimple_assign_cast_p (use_stmt))
+ continue;
+
+ tree cast_result = gimple_assign_lhs (use_stmt);
+ if (!value_escapes_loop_p (cast_result, m_loop))
+ continue;
+
+ if (m_loop_result && m_loop_result != cast_result)
+ return false;
+ m_loop_result = cast_result;
+ }
+
+ 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 ()
+{
+ if (TREE_CODE (m_desired) != SSA_NAME)
+ return false;
+
+ tree stripped = get_ssa_base_value (m_desired);
+
+ /* 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 case. */
+ if (TREE_CODE (stripped) == SSA_NAME)
+ if (gphi *phi = dyn_cast<gphi *> (SSA_NAME_DEF_STMT (stripped)))
+ if (try_phi_of_minmax (phi))
+ {
+ if (dump_enabled_p ())
+ dump_printf (MSG_NOTE,
+ "matched variant: PHI of MIN/MAX expressions\n");
+ return true;
+ }
+
+ gassign *assign = (TREE_CODE (stripped) == SSA_NAME
+ ? dyn_cast<gassign *> (SSA_NAME_DEF_STMT (stripped))
+ : nullptr);
+ if (!assign)
+ return false;
+
+ if (!decode_minmax_expr (assign))
+ return false;
+
+ if (dump_enabled_p ())
+ dump_printf (MSG_NOTE, "matched variant: expression MIN/MAX\n");
+ return true;
+}
+
+/* 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 against. 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 (!same_integer_precision_p (op1, m_desired)
+ || !same_integer_precision_p (op2, m_desired))
+ return false;
+
+ if (expected_value_p (op1))
+ m_value = op2;
+ else if (expected_value_p (op2))
+ m_value = op1;
+ else
+ return false;
+
+ m_is_min = (code == MIN_EXPR);
+ return true;
+}
+
+/* Try to collapse the two MIN/MAX expressions that feed m_desired on the
+ entry and retry edges into a single MIN/MAX <value, expected>.
+
+ The shape has a pre-loop MIN/MAX for the first attempt and another MIN/MAX
+ after a failed CAS. For example:
+
+ entry block: retry/latch block:
+ _9 = atomic_load _11 = REALPART_EXPR <cas_result>
+ _10 = MIN_EXPR <value, _9> _12 = MIN_EXPR <value, _11>
+ | |
+ | entry edge | retry edge
+ v v
+ header/CAS block:
+ expected = PHI <_9 (entry), _11 (retry)>
+ desired = PHI <_10 (entry), _12 (retry)>
+ cas_result = IFN_ATOMIC_COMPARE_EXCHANGE (..., expected,
+ desired, ...) */
+bool
+cas_to_minmax::try_phi_of_minmax (gphi *minmax_phi)
+{
+ /* Builtin CAS forms do not have an SSA PHI for expected. */
+ if (!m_expected_phi)
+ return false;
+
+ /* The desired and expected PHIs describe the same two incoming states:
+ the first CAS attempt and a retry after a failed CAS. */
+ if (gimple_bb (m_expected_phi) != gimple_bb (minmax_phi)
+ || gimple_phi_num_args (minmax_phi) != 2
+ || gimple_phi_num_args (m_expected_phi) != 2)
+ return false;
+
+ edge retry_edge = loop_latch_edge (m_loop);
+ edge first_edge = gimple_phi_arg_edge (minmax_phi, 0);
+ edge second_edge = gimple_phi_arg_edge (minmax_phi, 1);
+ if (first_edge != retry_edge && second_edge != retry_edge)
+ return false;
+
+ edge entry_edge = first_edge == retry_edge ? second_edge : first_edge;
+ tree_code entry_code;
+ tree_code retry_code;
+ tree entry_value;
+ tree retry_value;
+ if (!match_minmax_on_edge (minmax_phi, entry_edge, entry_code, entry_value)
+ || !match_minmax_on_edge (minmax_phi, retry_edge, retry_code,
+ retry_value))
+ return false;
+
+ /* Both attempts must perform the same operation with the same value. */
+ if (entry_code != retry_code || !values_equal_p (entry_value, retry_value))
+ return false;
+
+ m_value = entry_value;
+ m_is_min = (entry_code == MIN_EXPR);
+ return true;
+}
+
+/* Decode the MIN/MAX expression reaching MINMAX_PHI along INCOMING. One
+ operand must be reaching m_expected_phi through INCOMING, the other
+ operand becomes VALUE. */
+bool
+cas_to_minmax::match_minmax_on_edge (gphi *minmax_phi, edge incoming,
+ tree_code &code, tree &value)
+{
+ tree minmax_arg = gimple_phi_arg_def_from_edge (minmax_phi, incoming);
+ 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;
+
+ code = gimple_assign_rhs_code (minmax_def);
+ if (code != MIN_EXPR && code != MAX_EXPR)
+ return false;
+
+ tree op1 = gimple_assign_rhs1 (minmax_def);
+ tree op2 = gimple_assign_rhs2 (minmax_def);
+ if (!same_integer_precision_p (op1, m_desired)
+ || !same_integer_precision_p (op2, m_desired))
+ return false;
+
+ tree expected = gimple_phi_arg_def_from_edge (m_expected_phi, incoming);
+ if (values_equal_p (op1, expected))
+ value = op2;
+ else if (values_equal_p (op2, expected))
+ value = op1;
+ else
+ return false;
+
+ return true;
+}
+
+/* Return true if VALUE is the expected value read by the CAS. */
+bool
+cas_to_atomic_op::expected_value_p (tree value) const
+{
+ if (gimple_call_internal_p (m_cas_call, IFN_ATOMIC_COMPARE_EXCHANGE))
+ return values_equal_p (value, m_expected);
+
+ tree vuse;
+ tree base = get_ssa_base_value (value, &vuse);
+ return (vuse && operand_equal_p (base, m_expected, 0)
+ && vuse == gimple_vuse (m_cas_call));
+}
+
+/* Return true if every immediate use of m_cas_result can be preserved
+ when the CAS is replaced.
+
+ An IFN result may only be used by REALPART_EXPR and IMAGPART_EXPR
+ extractions. A builtin result may control the matched exit directly or
+ flow through an SSA copy or cast. Reject any other use, since it would
+ remain dependent on the removed CAS result. */
+bool
+cas_to_atomic_op::cas_result_uses_rewritable_p () const
+{
+ tree result = gimple_cond_lhs (m_exit_cond);
+
+ /* Make sure there is only one gcond testing CAS success. */
+ for (gimple *use_stmt : gather_imm_use_stmts (result))
+ if (gcond *c = dyn_cast<gcond *> (use_stmt))
+ if (c != m_exit_cond)
+ return false;
+
+ bool is_ifn
+ = gimple_call_internal_p (m_cas_call, IFN_ATOMIC_COMPARE_EXCHANGE);
+
+ for (gimple *use_stmt : gather_imm_use_stmts (m_cas_result))
+ {
+ if (is_gimple_debug (use_stmt))
+ continue;
+
+ if (is_ifn)
+ {
+ if (is_gimple_assign (use_stmt))
+ {
+ tree_code code = gimple_assign_rhs_code (use_stmt);
+ if (code == REALPART_EXPR || code == IMAGPART_EXPR)
+ continue;
+ }
+ }
+ else if (use_stmt == m_exit_cond
+ || gimple_assign_ssa_name_copy_p (use_stmt)
+ || gimple_assign_cast_p (use_stmt))
+ continue;
+
+ 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, m_loop_result is allowed
+ to escape. That value is what a fetch-op call returns to its caller,
+ so emit_replacement can replace it with the fetch-op IFN's LHS. */
+bool
+cas_to_atomic_op::loop_self_contained_p () const
+{
+ basic_block *bbs = get_loop_body (m_loop);
+ bool invalid = false;
+
+ for (unsigned i = 0; i < m_loop->num_nodes && !invalid; 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))
+ {
+ invalid = 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))
+ {
+ invalid = true;
+ break;
+ }
+
+ tree lhs = gimple_get_lhs (stmt);
+ if (!lhs)
+ continue;
+
+ /* Allow the loop result to escape. */
+ if (m_loop_result && lhs == m_loop_result)
+ continue;
+
+ if (value_escapes_loop_p (lhs, m_loop))
+ {
+ invalid = 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))
+ {
+ invalid = true;
+ break;
+ }
+ }
+ }
+
+ free (bbs);
+
+ return !invalid;
+}
+
+/* Return true if the CAS pointer has the same value on every iteration. */
+bool
+cas_to_atomic_op::cas_pointer_invariant_p () const
+{
+ return expr_invariant_in_loop_p (m_loop, m_ptr);
+}
+
+/* Return true if the MIN/MAX value has the same value on every retry. */
+bool
+cas_to_minmax::operation_value_invariant_p () const
+{
+ return expr_invariant_in_loop_p (m_loop, m_value);
+}
+
+/* Return true if the IFN replacing the CAS needs a result. A builtin CAS
+ stores the result back into expected, and an IFN CAS needs it when the
+ observed value escapes the loop. */
+bool
+cas_to_atomic_op::replacement_needs_result_p () const
+{
+ return (!gimple_call_internal_p (m_cas_call, IFN_ATOMIC_COMPARE_EXCHANGE)
+ || m_loop_result);
+}
+
+/* Return true if the target can expand the IFN_ATOMIC_FETCH_MINMAX call
+ built by emit_replacement directly. */
+bool
+cas_to_minmax::can_expand_directly_p () const
+{
+ return can_expand_atomic_fetch_minmax_p (TREE_TYPE (m_value), m_is_min,
+ !replacement_needs_result_p ());
+}
+
+/* Rewrite uses of m_cas_result before removing the CAS. */
+
+void
+cas_to_atomic_op::rewrite_cas_result_uses ()
+{
+ 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_debug (use_stmt))
+ continue;
+
+ gcc_assert (is_gimple_assign (use_stmt));
+ tree_code code = gimple_assign_rhs_code (use_stmt);
+ gcc_assert (code == IMAGPART_EXPR || code == REALPART_EXPR);
+
+ 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 but 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);
+ }
+ }
+
+ else
+ /* Builtin: replace bool assignment uses with 1. */
+ for (gimple *use_stmt : gather_imm_use_stmts (m_cas_result))
+ {
+ if (is_gimple_debug (use_stmt) || use_stmt == m_exit_cond)
+ continue;
+
+ gcc_assert (gimple_assign_ssa_name_copy_p (use_stmt)
+ || gimple_assign_cast_p (use_stmt));
+ gimple_stmt_iterator use_gsi = gsi_for_stmt (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);
+ }
+}
+
+/* Replace the CAS with an IFN_ATOMIC_FETCH_MINMAX call and make the retry
+ path unreachable. */
+
+void
+cas_to_minmax::emit_replacement ()
+{
+ tree data_type = TREE_TYPE (m_value);
+
+ tree op_code_tree
+ = build_int_cst (integer_type_node, m_is_min ? MIN_EXPR : MAX_EXPR);
+
+ gcall *ifn_call
+ = gimple_build_call_internal (IFN_ATOMIC_FETCH_MINMAX, 4, m_ptr, m_value,
+ op_code_tree, m_success_model);
+ gimple_call_set_nothrow (ifn_call, gimple_call_nothrow_p (m_cas_call));
+
+ 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);
+
+ if (replacement_needs_result_p ())
+ {
+ m_ifn_result = make_ssa_name (data_type);
+ gimple_call_set_lhs (ifn_call, m_ifn_result);
+ }
+
+ gsi_insert_before (&cas_gsi, ifn_call, GSI_SAME_STMT);
+
+ if (!is_ifn)
+ {
+ tree store_value = m_ifn_result;
+ if (!useless_type_conversion_p (TREE_TYPE (m_expected),
+ TREE_TYPE (m_ifn_result)))
+ {
+ store_value = make_ssa_name (TREE_TYPE (m_expected));
+ gimple *convert_stmt
+ = gimple_build_assign (store_value, NOP_EXPR, m_ifn_result);
+ gsi_insert_before (&cas_gsi, convert_stmt, GSI_SAME_STMT);
+ }
+ gimple *store_stmt = gimple_build_assign (m_expected, store_value);
+ gsi_insert_before (&cas_gsi, store_stmt, GSI_SAME_STMT);
+ }
+
+ rewrite_cas_result_uses ();
+
+ /* Make the old retry path unreachable. */
+ if (m_exit_on_true)
+ gimple_cond_make_true (m_exit_cond);
+ else
+ gimple_cond_make_false (m_exit_cond);
+ update_stmt (m_exit_cond);
+
+ if (dump_enabled_p ())
+ dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, m_cas_call,
+ "%s: rewrote loop %d to atomic %s\n",
+ current_function_name (), m_loop->num,
+ m_is_min ? "MIN" : "MAX");
+
+ gsi_remove (&cas_gsi, true);
+}
+
+bool
+cas_to_atomic_op::try_transform ()
+{
+ /* Recognize a CAS loop implementing the operation. */
+ if (!match_cas_loop ())
+ return reject ("no viable CAS loop found");
+ if (!parse_cas_arguments ())
+ return reject ("CAS arguments are not supported");
+ if (!match_retry_value ())
+ return reject ("retry expected does not come from failed CAS");
+ if (!match_loop_result ())
+ return reject ("observed CAS value escapes in multiple forms");
+ if (!match_op_shape ())
+ return reject ("no viable MIN/MAX operation found");
+
+ /* Don't create an IFN that would lower back to a CAS loop. */
+ if (!can_expand_directly_p ())
+ return reject ("target cannot expand atomic MIN/MAX directly");
+
+ /* Prove that replacing the matched loop with one atomic operation is
+ safe. */
+ if (!cas_result_uses_rewritable_p ())
+ return reject ("CAS result is used in an unsupported form");
+ if (!cas_pointer_invariant_p ())
+ return reject ("CAS pointer is not loop invariant");
+ if (!operation_value_invariant_p ())
+ return reject ("MIN/MAX value is not loop invariant");
+ if (!loop_self_contained_p ())
+ return reject ("loop has side effects or an escaping value other than"
+ " CAS's expected");
+
+ emit_replacement ();
+ return true;
+}
+
+static unsigned int
+transform_cas_loops_to_atomic_op (void)
+{
+ bool changed = false;
+
+ calculate_dominance_info (CDI_DOMINATORS);
+ record_loop_exits ();
+
+ for (auto loop : loops_list (cfun, LI_ONLY_INNERMOST))
+ changed |= cas_to_minmax (loop).try_transform ();
+
+ if (changed)
+ return TODO_cleanup_cfg | TODO_update_ssa;
+
+ return 0;
+}
+
+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 *fn) final override
+ {
+ return optimize >= 2 && flag_inline_atomics && number_of_loops (fn) > 1;
+ }
+
+ 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 a3b35e009e08..af457ee631ac 100644
--- a/gcc/tree-pass.h
+++ b/gcc/tree-pass.h
@@ -421,6 +421,7 @@ extern gimple_opt_pass *make_pass_pre (gcc::context *ctxt);
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_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
