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 ↗

(On Diff #187031)

"its value's"

59 ↗

(On Diff #187031)

You can move RMWI.getOperation() in here.

73 ↗

(On Diff #187031)

FAdd / FSub with any NaN are also saturating.

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

99 ↗

(On Diff #187031)

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 ↗

(On Diff #187031)

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

[reames]

lib/Transforms/InstCombine/InstCombineAtomicRMW.cpp

59 ↗

(On Diff #187031)

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

99 ↗

(On Diff #187031)

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

133 ↗

(On Diff #187031)

InstCombine does that automatically for non-void instructions.

llvm/trunk/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 its 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:
+    // TODO: fadd, fsub w/Nan
+    // Note: We avoid listing xchg to prevent transform cycles.
+    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;
 }

llvm/trunk/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
+}