Convert atomicrmws to xchg or store where legal

[reames]

Summary

Implement two more transforms of atomicrmw in InstCombine.

1. We can convert an atomicrmw which produces a known value in memory into an xchg instead.
2. We can convert an atomicrmw xchg w/o users into a store for some orderings.

[jfb]

A few nits, LGTM otherwise.

lib/Transforms/InstCombine/InstCombineAtomicRMW.cpp

52

"its value's"

59

You can move RMWI.getOperation() in here.

73

FAdd / FSub with any NaN are also saturating.

Technically xchg is also saturating, pre your description above...

99

Do you want to factor this out and run it after isSaturating succeeds above? That way instcombine doesn't have to do two passes to do this transform.

133

I guess here you could have done return eraseInstFromFunction(RMWI); as well?

[reames]

lib/Transforms/InstCombine/InstCombineAtomicRMW.cpp

59

Will do this and the other site of the same in a follow up nfc

99

Saving a cycle through the iteration didn't seem worth code complexity.

133

InstCombine does that automatically for non-void instructions.

lib/Transforms/InstCombine/InstCombineAtomicRMW.cpp

switch(Op) {
     case AtomicRMWInst::UMin:
       return C->isMaxValue(false);
     case AtomicRMWInst::UMax:
       return C->isMinValue(false);
     default:
       return false;
   }
 }
-}
 
+/// Return true if the given instruction always produces a value in memory
+/// equivelent to it's value operand.
+bool isSaturating(AtomicRMWInst& RMWI) {
+  auto C = dyn_cast<ConstantInt>(RMWI.getValOperand());
+  if(!C)
+    return false;
+
+  AtomicRMWInst::BinOp Op = RMWI.getOperation();
+  switch(Op) {
+  default:
+    return false;
+  case AtomicRMWInst::Or:
+    return C->isAllOnesValue();
+  case AtomicRMWInst::And:
+    return C->isZero();
+  case AtomicRMWInst::Min:
+    return C->isMinValue(true);
+  case AtomicRMWInst::Max:
+    return C->isMaxValue(true);
+  case AtomicRMWInst::UMin:
+    return C->isMinValue(false);
+  case AtomicRMWInst::UMax:
+    return C->isMaxValue(false);
+  };
+}
+}
 
 Instruction *InstCombiner::visitAtomicRMWInst(AtomicRMWInst &RMWI) {
-  // TODO: Any atomicrmw op which produces a known result in memory can be
-  // replaced w/an atomicrmw xchg. (see getBinOpAbsorber)
-  
-  // TODO: Any atomicrmw xchg with no uses can be converted to a atomic store
-  // if the ordering is compatible.
-  
-  if (!isIdempotentRMW(RMWI))
+  // Volatile RMWs perform a load and a store, we cannot replace this by just a
+  // load or just a store. We chose not to canonicalize out of general paranoia
+  // about user expectations around volatile. 
+  if (RMWI.isVolatile())
+    return nullptr;
+  // Any atomicrmw op which produces a known result in memory can be
+  // replaced w/an atomicrmw xchg.
+  if (isSaturating(RMWI)) {
+    RMWI.setOperation(AtomicRMWInst::Xchg);
+    return &RMWI;
+  }
+
+  AtomicOrdering Ordering = RMWI.getOrdering();
+  assert(Ordering != AtomicOrdering::NotAtomic &&
+         Ordering != AtomicOrdering::Unordered &&
+         "AtomicRMWs don't make sense with Unordered or NotAtomic");
+
+  // Any atomicrmw xchg with no uses can be converted to a atomic store if the
+  // ordering is compatible. 
+  if (RMWI.getOperation() == AtomicRMWInst::Xchg &&
+      RMWI.use_empty()) {
+    if (Ordering != AtomicOrdering::Release &&
+        Ordering != AtomicOrdering::Monotonic)
       return nullptr;
+    auto *SI = new StoreInst(RMWI.getValOperand(),
+                             RMWI.getPointerOperand(), &RMWI);
+    SI->setAtomic(Ordering, RMWI.getSyncScopeID());
+    SI->setAlignment(DL.getABITypeAlignment(RMWI.getType()));
+    return eraseInstFromFunction(RMWI);
+  }
   
-  // Volatile RMWs perform a load and a store, we cannot replace this by just a
-  // load. We chose not to canonicalize out of general paranoia about user
-  // expectations around volatile. 
-  if (RMWI.isVolatile())
+  if (!isIdempotentRMW(RMWI))
     return nullptr;
 
   // We chose to canonicalize all idempotent operations to an single
   // operation code and constant.  This makes it easier for the rest of the
   // optimizer to match easily.  The choice of or w/zero is arbitrary.
   if (RMWI.getType()->isIntegerTy() &&
       RMWI.getOperation() != AtomicRMWInst::Or) {
     RMWI.setOperation(AtomicRMWInst::Or);
     RMWI.setOperand(1, ConstantInt::get(RMWI.getType(), 0));
     return &RMWI;
   }
 
   // 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)
     return nullptr;
   
   LoadInst *Load = new LoadInst(RMWI.getType(), RMWI.getPointerOperand());
   Load->setAtomic(Ordering, RMWI.getSyncScopeID());
   Load->setAlignment(DL.getABITypeAlignment(RMWI.getType()));
   return Load;
 }

test/Transforms/InstCombine/atomicrmw.ll

 ; CHECK-NEXT: ret i16 %res
 define i16 @atomic_acq_rel(i16* %addr) {
   %res = atomicrmw xor i16* %addr, i16 0 acq_rel
   ret i16 %res
 }
 
 
 ; CHECK-LABEL: sat_or_allones
-; CHECK-NEXT: %res = atomicrmw add i32* %addr, i32 -1 monotonic
+; CHECK-NEXT: %res = atomicrmw xchg i32* %addr, i32 -1 monotonic
 ; CHECK-NEXT: ret i32 %res
 define i32 @sat_or_allones(i32* %addr) {
-  %res = atomicrmw add i32* %addr, i32 -1 monotonic
+  %res = atomicrmw or i32* %addr, i32 -1 monotonic
   ret i32 %res
 }
 
 ; CHECK-LABEL: sat_and_zero
-; CHECK-NEXT: %res = atomicrmw and i32* %addr, i32 0 monotonic
+; CHECK-NEXT: %res = atomicrmw xchg i32* %addr, i32 0 monotonic
 ; CHECK-NEXT: ret i32 %res
 define i32 @sat_and_zero(i32* %addr) {
   %res = atomicrmw and i32* %addr, i32 0 monotonic
   ret i32 %res
 }
 ; CHECK-LABEL: sat_umin_uint_min
-; CHECK-NEXT: %res = atomicrmw umin i32* %addr, i32 0 monotonic
+; CHECK-NEXT: %res = atomicrmw xchg i32* %addr, i32 0 monotonic
 ; CHECK-NEXT: ret i32 %res
 define i32 @sat_umin_uint_min(i32* %addr) {
   %res = atomicrmw umin i32* %addr, i32 0 monotonic
   ret i32 %res
 }
 
 ; CHECK-LABEL: sat_umax_uint_max
-; CHECK-NEXT: %res = atomicrmw umax i32* %addr, i32 -1 monotonic
+; CHECK-NEXT: %res = atomicrmw xchg i32* %addr, i32 -1 monotonic
 ; CHECK-NEXT: ret i32 %res
 define i32 @sat_umax_uint_max(i32* %addr) {
   %res = atomicrmw umax i32* %addr, i32 -1 monotonic
   ret i32 %res
 }
 
 ; CHECK-LABEL: sat_min_smin_char
-; CHECK-NEXT: %res = atomicrmw min i8* %addr, i8 -128 monotonic
+; CHECK-NEXT: %res = atomicrmw xchg i8* %addr, i8 -128 monotonic
 ; CHECK-NEXT: ret i8 %res
 define i8 @sat_min_smin_char(i8* %addr) {
   %res = atomicrmw min i8* %addr, i8 -128 monotonic
   ret i8 %res
 }
 
 ; CHECK-LABEL: sat_max_smax_char
-; CHECK-NEXT: %res = atomicrmw max i8* %addr, i8 127 monotonic
+; CHECK-NEXT: %res = atomicrmw xchg i8* %addr, i8 127 monotonic
 ; CHECK-NEXT: ret i8 %res
 define i8 @sat_max_smax_char(i8* %addr) {
   %res = atomicrmw max i8* %addr, i8 127 monotonic
   ret i8 %res
 }
 
 ; CHECK-LABEL: xchg_unused_monotonic
-; CHECK-NEXT: atomicrmw xchg i32* %addr, i32 0 monotonic
+; CHECK-NEXT: store atomic i32 0, i32* %addr monotonic, align 4
 ; CHECK-NEXT: ret void
 define void @xchg_unused_monotonic(i32* %addr) {
   atomicrmw xchg i32* %addr, i32 0 monotonic
   ret void
 }
 
 ; CHECK-LABEL: xchg_unused_release
-; CHECK-NEXT: atomicrmw xchg i32* %addr, i32 -1 release
+; CHECK-NEXT: store atomic i32 -1, i32* %addr release, align 4
 ; CHECK-NEXT: ret void
 define void @xchg_unused_release(i32* %addr) {
   atomicrmw xchg i32* %addr, i32 -1 release
   ret void
 }
 
 ; CHECK-LABEL: xchg_unused_seq_cst
 ; CHECK-NEXT: atomicrmw xchg i32* %addr, i32 0 seq_cst
 ; CHECK-NEXT: ret void
 define void @xchg_unused_seq_cst(i32* %addr) {
   atomicrmw xchg i32* %addr, i32 0 seq_cst
   ret void
 }
 
 ; CHECK-LABEL: xchg_unused_volatile
 ; CHECK-NEXT: atomicrmw volatile xchg i32* %addr, i32 0 monotonic
 ; CHECK-NEXT: ret void
 define void @xchg_unused_volatile(i32* %addr) {
   atomicrmw volatile xchg i32* %addr, i32 0 monotonic
   ret void
 }
 
+; CHECK-LABEL: sat_or_allones_unused
+; CHECK-NEXT: store atomic i32 -1, i32* %addr monotonic, align 4
+; CHECK-NEXT: ret void
+define void @sat_or_allones_unused(i32* %addr) {
+  atomicrmw or i32* %addr, i32 -1 monotonic
+  ret void
+}