Teach instcombine about remaining idemptotent atomicrmw types

[reames]

Summary

Expand on Quentin's r353471 patch which converts some atomicrmws into loads. Handle remaining operation types, and fix a slight bug. Atomic loads are required to have alignment. Since this was within the InstCombine fixed point, somewhere else in InstCombine was adding alignment before the verifier saw it, but still, we should fix.

Terminology wise, I'm using the "idempotent" naming that is used for the same operations in AtomicExpand and X86ISelLoweringInfo. Once this lands, I'll add similar tests for AtomicExpand, and move the pattern match function to a common location. Any suggestions as to where?

The last thing we should probably do - not in this patch - is to canonicalize the operation for any idempotent atomicrmw which we can't convert to a load. I was thinking to have "atomicrmw or, ptr, 0" be the canonical choice. Thoughts?

[qcolombet]

LGTM, one nitpick below.

Nice catch for the alignment stuff!

lib/Transforms/InstCombine/InstCombineAtomicRMW.cpp

53 ↗

(On Diff #186858)

IIRC to be pedantic idempotent is when something doesn't change when multiplied by itself, hence this name could be misleading (though I could remember wrong :P).

[spatel]

lib/Transforms/InstCombine/InstCombineAtomicRMW.cpp

53 ↗

(On Diff #186858)

Idempotent is (copied from Instruction.h):

///   Idempotent operators satisfy:  x op x === x
///
/// In LLVM, the And and Or operators are idempotent.

We have similar logic/switch for binop instructions. See:
ConstantExpr::getBinOpIdentity()
(not sure if there's a way to share code between this and that)

[qcolombet]

lib/Transforms/InstCombine/InstCombineAtomicRMW.cpp

53 ↗

(On Diff #186858)

Thanks for the reference Sanjay.
Technically, this does not match what we are doing here: x op cst === x where cst may be different than x, but I guess this is a wildly spread language abuse that people just get it.

[jfb]

lgtm

For the idempotent RMW, atomicrmw or, ptr, 0 sgtm. I assume that you'd do the same for floating-point (with a cast)? I wonder if in the long run we'd actually just want a separate instruction for this...

[reames]

lib/Transforms/InstCombine/InstCombineAtomicRMW.cpp

53 ↗

(On Diff #186858)

Seems like there's consensus the name is confusing. Given we use the same naming in AtomicExpand, I'm going to land as is, and then change everything in one go. Any suggestions on better names?

[qcolombet]

lib/Transforms/InstCombine/InstCombineAtomicRMW.cpp

53 ↗

(On Diff #186858)

To be honest, we can leave it this way. I could be wrong be I guess most people are not confused by this.

If I were to come up with a different name, I would try to convey the notion that this does not change the input value. IsNoOp could be a candidate, but it kind of implies that we can just remove the instruction which is not true...

Long story short, I don't have a good suggestion!

[reames]

lib/Transforms/InstCombine/InstCombineAtomicRMW.cpp

53 ↗

(On Diff #186858)

Here are some ideas:
AtomicRMWInst::isIdempotent()
AtomicRMWInst::isMemoryIdempotent()
Instruction::isMemoryIdempotent()
Instruction::isMemoryNop()
Instruction::mayChangeMemory()

ValueTracking.h
mayChangeMemory(Instruction&)

I'm leaning towards mayChangeMemory on Instruction myself.

p.s. I need a common location, regardless of what name we choose. So I'd like the name to be non-confusing. :)

llvm/trunk/lib/Transforms/InstCombine/InstCombineAtomicRMW.cpp

 //===- InstCombineAtomicRMW.cpp -------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the visit functions for atomic rmw instructions.
 //
 //===----------------------------------------------------------------------===//
 #include "InstCombineInternal.h"
 #include "llvm/IR/Instructions.h"
 
 using namespace llvm;
 
-Instruction *InstCombiner::visitAtomicRMWInst(AtomicRMWInst &RMWI) {
-  switch (RMWI.getOperation()) {
-  default:
-    break;
+namespace {
+/// Return true if and only if the given instruction does not modify the memory
+/// location referenced.  Note that an idemptent atomicrmw may still have
+/// ordering effects on nearby instructions, or be volatile.
+/// TODO: Common w/ the version in AtomicExpandPass, and change the term used.
+/// Idemptotent is confusing in this context.
+bool isIdempotentRMW(AtomicRMWInst& RMWI) {
+  auto C = dyn_cast<ConstantInt>(RMWI.getValOperand());
+  if(!C)
+    // TODO: Handle fadd, fsub?
+    return false;
+
+  AtomicRMWInst::BinOp Op = RMWI.getOperation();
+  switch(Op) {
     case AtomicRMWInst::Add:
     case AtomicRMWInst::Sub:
     case AtomicRMWInst::Or:
-    // Replace atomicrmw <op> addr, 0 => load atomic addr.
+    case AtomicRMWInst::Xor:
+      return C->isZero();
+    case AtomicRMWInst::And:
+      return C->isMinusOne();
+    case AtomicRMWInst::Min:
+      return C->isMaxValue(true);
+    case AtomicRMWInst::Max:
+      return C->isMinValue(true);
+    case AtomicRMWInst::UMin:
+      return C->isMaxValue(false);
+    case AtomicRMWInst::UMax:
+      return C->isMinValue(false);
+    default:
+      return false;
+  }
+}
+}
+
+
+Instruction *InstCombiner::visitAtomicRMWInst(AtomicRMWInst &RMWI) {
+  if (!isIdempotentRMW(RMWI))
+    return nullptr;
+
+  // TODO: Canonicalize the operation for an idempotent operation we can't
+  // convert into a simple load.
 
-    // Volatile RMWs perform a load and a store, we cannot replace
-    // this by just a load.
-    if (RMWI.isVolatile())
-      break;
+    return nullptr;
 
-    auto *CI = dyn_cast<ConstantInt>(RMWI.getValOperand());
-    if (!CI || !CI->isZero())
-      break;
-    // Check if the required ordering is compatible with an
-    // atomic load.
-    AtomicOrdering Ordering = RMWI.getOrdering();
-    assert(Ordering != AtomicOrdering::NotAtomic &&
-           Ordering != AtomicOrdering::Unordered &&
-           "AtomicRMWs don't make sense with Unordered or NotAtomic");
-    if (Ordering != AtomicOrdering::Acquire &&
-        Ordering != AtomicOrdering::Monotonic)
-      break;
-    LoadInst *Load = new LoadInst(RMWI.getType(), RMWI.getPointerOperand());
-    Load->setAtomic(Ordering, RMWI.getSyncScopeID());
-    return Load;
-  }
-  return nullptr;
-}
+  // Check if the required ordering is compatible with an atomic load.
+    return nullptr;
+  
+  Load->setAlignment(DL.getABITypeAlignment(RMWI.getType()));

llvm/trunk/test/Transforms/InstCombine/atomicrmw.ll

 ; CHECK-NEXT: %res = load atomic i32, i32* %addr monotonic, align 4
 ; CHECK-NEXT: ret i32 %res
 define i32 @atomic_sub_zero(i32* %addr) {
   %res = atomicrmw sub i32* %addr, i32 0 monotonic
   ret i32 %res
 }
 
 ; CHECK-LABEL: atomic_and_allones
-; CHECK-NEXT: %res = atomicrmw and i32* %addr, i32 -1 monotonic
+; CHECK-NEXT: %res = load atomic i32, i32* %addr monotonic, align 4
 ; CHECK-NEXT: ret i32 %res
 define i32 @atomic_and_allones(i32* %addr) {
   %res = atomicrmw and i32* %addr, i32 -1 monotonic
   ret i32 %res
 }
 ; CHECK-LABEL: atomic_umin_uint_max
-; CHECK-NEXT: %res = atomicrmw umin i32* %addr, i32 -1 monotonic
+; CHECK-NEXT: %res = load atomic i32, i32* %addr monotonic, align 4
 ; CHECK-NEXT: ret i32 %res
 define i32 @atomic_umin_uint_max(i32* %addr) {
   %res = atomicrmw umin i32* %addr, i32 -1 monotonic
   ret i32 %res
 }
 
 ; CHECK-LABEL: atomic_umax_zero
-; CHECK-NEXT: %res = atomicrmw umax i32* %addr, i32 0 monotonic
+; CHECK-NEXT: %res = load atomic i32, i32* %addr monotonic, align 4
 ; CHECK-NEXT: ret i32 %res
 define i32 @atomic_umax_zero(i32* %addr) {
   %res = atomicrmw umax i32* %addr, i32 0 monotonic
   ret i32 %res
 }
 
 ; CHECK-LABEL: atomic_min_smax_char
-; CHECK-NEXT: %res = atomicrmw min i8* %addr, i8 -128 monotonic
+; CHECK-NEXT: %res = load atomic i8, i8* %addr monotonic, align 1
 ; CHECK-NEXT: ret i8 %res
 define i8 @atomic_min_smax_char(i8* %addr) {
-  %res = atomicrmw min i8* %addr, i8 -128 monotonic
+  %res = atomicrmw min i8* %addr, i8 127 monotonic
   ret i8 %res
 }
 
 ; CHECK-LABEL: atomic_max_smin_char
-; CHECK-NEXT: %res = atomicrmw max i8* %addr, i8 127 monotonic
+; CHECK-NEXT: %res = load atomic i8, i8* %addr monotonic, align 1
 ; CHECK-NEXT: ret i8 %res
 define i8 @atomic_max_smin_char(i8* %addr) {
-  %res = atomicrmw max i8* %addr, i8 127 monotonic
+  %res = atomicrmw max i8* %addr, i8 -128 monotonic
   ret i8 %res
 }
 
 
-; Don't transform volatile atomicrmw. This would eliminate a volatile store
-; otherwise.
+; Can't replace a volatile w/a load; this would eliminate a volatile store.
 ; CHECK-LABEL: atomic_sub_zero_volatile
 ; CHECK-NEXT: %res = atomicrmw volatile sub i64* %addr, i64 0 acquire
 ; CHECK-NEXT: ret i64 %res
 define i64 @atomic_sub_zero_volatile(i64* %addr) {
   %res = atomicrmw volatile sub i64* %addr, i64 0 acquire
   ret i64 %res
 }
 

 ; CHECK-LABEL: atomic_add_non_zero
 ; CHECK-NEXT: %res = atomicrmw add i16* %addr, i16 2 monotonic
 ; CHECK-NEXT: ret i16 %res
 define i16 @atomic_add_non_zero(i16* %addr) {
   %res = atomicrmw add i16* %addr, i16 2 monotonic
   ret i16 %res
 }
 
-; Check that the transformation does not apply when the value is changed by
-; the atomic operation (xor operation with zero).
 ; CHECK-LABEL: atomic_xor_zero
-; CHECK-NEXT: %res = atomicrmw xor i16* %addr, i16 0 monotonic
+; CHECK-NEXT: %res = load atomic i16, i16* %addr monotonic, align 2
 ; CHECK-NEXT: ret i16 %res
 define i16 @atomic_xor_zero(i16* %addr) {
   %res = atomicrmw xor i16* %addr, i16 0 monotonic
   ret i16 %res
 }
 
 ; Check that the transformation does not apply when the ordering is
 ; incompatible with a load (release).