[IR] Extend cmpxchg to allow pointer type operands

[reames]

Summary

Today, we do not allow cmpxchg operations with pointer arguments. We require the frontend to insert ptrtoint casts and do the cmpxchg in integers. While correct, this is problematic from a couple of perspectives:

1. It makes the IR harder to analyse (for instance, it make capture tracking overly conservative)
2. It pushes work onto the frontend authors for no real gain

This patch implements the simplest form of IR support. As we did with floating point loads and stores, we teach AtomicExpand to convert back to the old representation. This prevents us needing to change all backends in a single lock step change. Over time, we can migrate each backend to natively selecting the pointer type. In the meantime, we get the advantages of a cleaner IR representation without waiting for the backend changes.

[jfb]

lib/AsmParser/LLParser.cpp

5912 ↗

(On Diff #48400)

I think this is too permissive, store does:

if (!Val->getType()->isFirstClassType())
  return Error(Loc, "store operand must be a first class value");

The change is also allowing pointer types. Should this be a separate change? At the minimum it has to be tested.

lib/CodeGen/AtomicExpandPass.cpp

173 ↗

(On Diff #48400)

FP can fall into the same helper? Though the helper will need to support FP as well.

464 ↗

(On Diff #48400)

"equivalent"

test/Transforms/AtomicExpand/X86/expand-atomic-non-integer.ll

124 ↗

(On Diff #48400)

Add a test with volatile and addrspace, make sure they're kept.

[reames]

lib/AsmParser/LLParser.cpp

5912 ↗

(On Diff #48400)

I was a bit confused why this code was here at all. Shouldn't this just be caught by the Verifier? It seems to have the checks duplicated twice.

lib/CodeGen/AtomicExpandPass.cpp

173 ↗

(On Diff #48400)

That's the intent. I just wanted to do that as a separate change.

test/Transforms/AtomicExpand/X86/expand-atomic-non-integer.ll

124 ↗

(On Diff #48400)

will do

[jfb]

lib/AsmParser/LLParser.cpp

5912 ↗

(On Diff #48400)

I'm not sure which checks are expected to go in which part of LLVM :-)

The verifier seems like more of a sanity check for internals (an assert) whereas this part seems to be the syntax check on .ll files themselves (equivalent to the errors clang gives)?

It's redundant, but there seems to be a purpose to the redundancy.

lib/CodeGen/AtomicExpandPass.cpp

173 ↗

(On Diff #48400)

Ah OK, and it'll fail in the verifier so it's fine. Maybe just assert early here? It'll fail miserably in convertCmpXchgToIntegerType otherwise.

[reames]

Address JF's review comments.

[jfb]

lgtm

[theraven]

llvm/trunk/docs/LangRef.rst

7091

Is there a reason to disallow floating point types? C11 expects compare and exchange to work on floating point types, and requiring casts to integer types doesn't play particularly nicely with TBAA.

Given the recent mailing list discussion, is this part of the work to allow the front end to provide any type here and lower to a library call closer to the back end?

llvm/trunk/lib/CodeGen/AtomicExpandPass.cpp

179

This TODO is quite important for us. We're currently unable to use or pointer LL/SC instructions from C because our target does not have a valid integer type as big as our pointer type.

llvm/trunk/docs/LangRef.rst

 equal, it tries to store a new value into the memory.
 
 Arguments:
 """"""""""
 
 There are three arguments to the '``cmpxchg``' instruction: an address
 to operate on, a value to compare to the value currently be at that
 address, and a new value to place at that address if the compared values
-are equal. The type of '<cmp>' must be an integer type whose bit width
-is a power of two greater than or equal to eight and less than or equal
-to a target-specific size limit. '<cmp>' and '<new>' must have the same
-type, and the type of '<pointer>' must be a pointer to that type. If the
-``cmpxchg`` is marked as ``volatile``, then the optimizer is not allowed
-to modify the number or order of execution of this ``cmpxchg`` with
-other :ref:`volatile operations <volatile>`.
+are equal. The type of '<cmp>' must be an integer or pointer type whose
+bit width is a power of two greater than or equal to eight and less 
+than or equal to a target-specific size limit. '<cmp>' and '<new>' must
+have the same type, and the type of '<pointer>' must be a pointer to 
+that type. If the ``cmpxchg`` is marked as ``volatile``, then the 
+optimizer is not allowed to modify the number or order of execution of
+this ``cmpxchg`` with other :ref:`volatile operations <volatile>`.
 
 The success and failure :ref:`ordering <ordering>` arguments specify how this
 ``cmpxchg`` synchronizes with other atomic operations. Both ordering parameters
 must be at least ``monotonic``, the ordering constraint on failure must be no
 stronger than that on success, and the failure ordering cannot be either
 ``release`` or ``acq_rel``.
 
 The optional "``singlethread``" argument declares that the ``cmpxchg``

llvm/trunk/lib/AsmParser/LLParser.cpp

 #include "llvm/IR/DebugInfoMetadata.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/InlineAsm.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/IR/ValueSymbolTable.h"
+#include "llvm/Support/Debug.h"
 #include "llvm/Support/Dwarf.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/SaveAndRestore.h"
 #include "llvm/Support/raw_ostream.h"
 using namespace llvm;
 
 static std::string getTypeString(Type *T) {
   std::string Result;
int LLParser::ParseCmpXchg(Instruction *&Inst, PerFunctionState &PFS) {
   if (FailureOrdering == Release || FailureOrdering == AcquireRelease)
     return TokError("cmpxchg failure ordering cannot include release semantics");
   if (!Ptr->getType()->isPointerTy())
     return Error(PtrLoc, "cmpxchg operand must be a pointer");
   if (cast<PointerType>(Ptr->getType())->getElementType() != Cmp->getType())
     return Error(CmpLoc, "compare value and pointer type do not match");
   if (cast<PointerType>(Ptr->getType())->getElementType() != New->getType())
     return Error(NewLoc, "new value and pointer type do not match");
-  if (!New->getType()->isIntegerTy())
-    return Error(NewLoc, "cmpxchg operand must be an integer");
-  unsigned Size = New->getType()->getPrimitiveSizeInBits();
-  if (Size < 8 || (Size & (Size - 1)))
-    return Error(NewLoc, "cmpxchg operand must be power-of-two byte-sized"
-                         " integer");
-
+  if (!New->getType()->isFirstClassType())
+    return Error(NewLoc, "cmpxchg operand must be a first class value");
   AtomicCmpXchgInst *CXI = new AtomicCmpXchgInst(
       Ptr, Cmp, New, SuccessOrdering, FailureOrdering, Scope);
   CXI->setVolatile(isVolatile);
   CXI->setWeak(isWeak);
   Inst = CXI;
   return AteExtraComma ? InstExtraComma : InstNormal;
 }
 

llvm/trunk/lib/CodeGen/AtomicExpandPass.cpp

private:
     bool expandAtomicLoadToLL(LoadInst *LI);
     bool expandAtomicLoadToCmpXchg(LoadInst *LI);
     StoreInst *convertAtomicStoreToIntegerType(StoreInst *SI);
     bool expandAtomicStore(StoreInst *SI);
     bool tryExpandAtomicRMW(AtomicRMWInst *AI);
     bool expandAtomicOpToLLSC(
         Instruction *I, Value *Addr, AtomicOrdering MemOpOrder,
         std::function<Value *(IRBuilder<> &, Value *)> PerformOp);
+    AtomicCmpXchgInst *convertCmpXchgToIntegerType(AtomicCmpXchgInst *CI);
     bool expandAtomicCmpXchg(AtomicCmpXchgInst *CI);
     bool isIdempotentRMW(AtomicRMWInst *AI);
     bool simplifyIdempotentRMW(AtomicRMWInst *AI);
   };
 }
 
 char AtomicExpand::ID = 0;
 char &llvm::AtomicExpandID = AtomicExpand::ID;
if (LI) {
       // - into a Cmpxchg/LL-SC loop otherwise
       // we try them in that order.
 
       if (isIdempotentRMW(RMWI) && simplifyIdempotentRMW(RMWI)) {
         MadeChange = true;
       } else {
         MadeChange |= tryExpandAtomicRMW(RMWI);
       }
-    } else if (CASI && TLI->shouldExpandAtomicCmpXchgInIR(CASI)) {
+    } else if (CASI) {
+      // TODO: when we're ready to make the change at the IR level, we can
+      // extend convertCmpXchgToInteger for floating point too.
+      assert(!CASI->getCompareOperand()->getType()->isFloatingPointTy() &&
+             "unimplemented - floating point not legal at IR level");
+      if (CASI->getCompareOperand()->getType()->isPointerTy() ) {
+        // TODO: add a TLI hook to control this so that each target can
+        // convert to lowering the original type one at a time.
+        CASI = convertCmpXchgToIntegerType(CASI);
+        assert(CASI->getCompareOperand()->getType()->isIntegerTy() &&
+               "invariant broken");
+        MadeChange = true;
+      }
+      
+      if (TLI->shouldExpandAtomicCmpXchgInIR(CASI))
         MadeChange |= expandAtomicCmpXchg(CASI);
     }
   }
   return MadeChange;
 }
 
 bool AtomicExpand::bracketInstWithFences(Instruction *I, AtomicOrdering Order,
                                          bool IsStore, bool IsLoad) {
   IRBuilder<> Builder(I);
IntegerType *AtomicExpand::getCorrespondingIntegerType(Type *T,
                                                        const DataLayout &DL) {
   EVT VT = TLI->getValueType(DL, T);
   unsigned BitWidth = VT.getStoreSizeInBits();
   assert(BitWidth == VT.getSizeInBits() && "must be a power of two");
   return IntegerType::get(T->getContext(), BitWidth);
 }
 
 /// Convert an atomic load of a non-integral type to an integer load of the
-/// equivelent bitwidth.  See the function comment on
+/// equivalent bitwidth.  See the function comment on
 /// convertAtomicStoreToIntegerType for background.  
 LoadInst *AtomicExpand::convertAtomicLoadToIntegerType(LoadInst *LI) {
   auto *M = LI->getModule();
   Type *NewTy = getCorrespondingIntegerType(LI->getType(),
                                             M->getDataLayout());
 
   IRBuilder<> Builder(LI);
   
bool AtomicExpand::expandAtomicLoadToCmpXchg(LoadInst *LI) {
 
   LI->replaceAllUsesWith(Loaded);
   LI->eraseFromParent();
 
   return true;
 }
 
 /// Convert an atomic store of a non-integral type to an integer store of the
-/// equivelent bitwidth.  We used to not support floating point or vector
+/// equivalent bitwidth.  We used to not support floating point or vector
 /// atomics in the IR at all.  The backends learned to deal with the bitcast
 /// idiom because that was the only way of expressing the notion of a atomic
 /// float or vector store.  The long term plan is to teach each backend to
 /// instruction select from the original atomic store, but as a migration
 /// mechanism, we convert back to the old format which the backends understand.
 /// Each backend will need individual work to recognize the new format.
 StoreInst *AtomicExpand::convertAtomicStoreToIntegerType(StoreInst *SI) {
   IRBuilder<> Builder(SI);
bool AtomicExpand::expandAtomicOpToLLSC(
   Builder.SetInsertPoint(ExitBB, ExitBB->begin());
 
   I->replaceAllUsesWith(Loaded);
   I->eraseFromParent();
 
   return true;
 }
 
+/// Convert an atomic cmpxchg of a non-integral type to an integer cmpxchg of
+/// the equivalent bitwidth.  We used to not support pointer cmpxchg in the
+/// IR.  As a migration step, we convert back to what use to be the standard
+/// way to represent a pointer cmpxchg so that we can update backends one by
+/// one. 
+AtomicCmpXchgInst *AtomicExpand::convertCmpXchgToIntegerType(AtomicCmpXchgInst *CI) {
+  auto *M = CI->getModule();
+  Type *NewTy = getCorrespondingIntegerType(CI->getCompareOperand()->getType(),
+                                            M->getDataLayout());
+
+  IRBuilder<> Builder(CI);
+  
+  Value *Addr = CI->getPointerOperand();
+  Type *PT = PointerType::get(NewTy,
+                              Addr->getType()->getPointerAddressSpace());
+  Value *NewAddr = Builder.CreateBitCast(Addr, PT);
+
+  Value *NewCmp = Builder.CreatePtrToInt(CI->getCompareOperand(), NewTy);
+  Value *NewNewVal = Builder.CreatePtrToInt(CI->getNewValOperand(), NewTy);
+  
+  
+  auto *NewCI = Builder.CreateAtomicCmpXchg(NewAddr, NewCmp, NewNewVal,
+                                            CI->getSuccessOrdering(),
+                                            CI->getFailureOrdering(),
+                                            CI->getSynchScope());
+  NewCI->setVolatile(CI->isVolatile());
+  NewCI->setWeak(CI->isWeak());
+  DEBUG(dbgs() << "Replaced " << *CI << " with " << *NewCI << "\n");
+
+  Value *OldVal = Builder.CreateExtractValue(NewCI, 0);
+  Value *Succ = Builder.CreateExtractValue(NewCI, 1);
+
+  OldVal = Builder.CreateIntToPtr(OldVal, CI->getCompareOperand()->getType());
+
+  Value *Res = UndefValue::get(CI->getType());
+  Res = Builder.CreateInsertValue(Res, OldVal, 0);
+  Res = Builder.CreateInsertValue(Res, Succ, 1);
+
+  CI->replaceAllUsesWith(Res);
+  CI->eraseFromParent();
+  return NewCI;
+}
+
+
 bool AtomicExpand::expandAtomicCmpXchg(AtomicCmpXchgInst *CI) {
   AtomicOrdering SuccessOrder = CI->getSuccessOrdering();
   AtomicOrdering FailureOrder = CI->getFailureOrdering();
   Value *Addr = CI->getPointerOperand();
   BasicBlock *BB = CI->getParent();
   Function *F = BB->getParent();
   LLVMContext &Ctx = F->getContext();
   // If getInsertFencesForAtomic() returns true, then the target does not want

llvm/trunk/lib/IR/Verifier.cpp

Assert(CXI.getSuccessOrdering() >= CXI.getFailureOrdering(),
          &CXI);
   Assert(CXI.getFailureOrdering() != Release &&
              CXI.getFailureOrdering() != AcquireRelease,
          "cmpxchg failure ordering cannot include release semantics", &CXI);
 
   PointerType *PTy = dyn_cast<PointerType>(CXI.getOperand(0)->getType());
   Assert(PTy, "First cmpxchg operand must be a pointer.", &CXI);
   Type *ElTy = PTy->getElementType();
-  Assert(ElTy->isIntegerTy(), "cmpxchg operand must have integer type!", &CXI,
-         ElTy);
+  Assert(ElTy->isIntegerTy() || ElTy->isPointerTy(),
+        "cmpxchg operand must have integer or pointer type",
+         ElTy, &CXI);
   checkAtomicMemAccessSize(M, ElTy, &CXI);
   Assert(ElTy == CXI.getOperand(1)->getType(),
          "Expected value type does not match pointer operand type!", &CXI,
          ElTy);
   Assert(ElTy == CXI.getOperand(2)->getType(),
          "Stored value type does not match pointer operand type!", &CXI, ElTy);
   visitInstruction(CXI);
 }

llvm/trunk/test/Transforms/AtomicExpand/X86/expand-atomic-non-integer.ll

 ; CHECK-LABEL: @float_store_expand_addr1
 ; CHECK: %1 = bitcast float %v to i32
 ; CHECK: %2 = bitcast float addrspace(1)* %ptr to i32 addrspace(1)*
 ; CHECK: store atomic i32 %1, i32 addrspace(1)* %2 unordered, align 4
   store atomic float %v, float addrspace(1)* %ptr unordered, align 4
   ret void
 }
 
+define void @pointer_cmpxchg_expand(i8** %ptr, i8* %v) {
+; CHECK-LABEL: @pointer_cmpxchg_expand
+; CHECK: %1 = bitcast i8** %ptr to i64*
+; CHECK: %2 = ptrtoint i8* %v to i64
+; CHECK: %3 = cmpxchg i64* %1, i64 0, i64 %2 seq_cst monotonic
+; CHECK: %4 = extractvalue { i64, i1 } %3, 0
+; CHECK: %5 = extractvalue { i64, i1 } %3, 1
+; CHECK: %6 = inttoptr i64 %4 to i8*
+; CHECK: %7 = insertvalue { i8*, i1 } undef, i8* %6, 0
+; CHECK: %8 = insertvalue { i8*, i1 } %7, i1 %5, 1
+  cmpxchg i8** %ptr, i8* null, i8* %v seq_cst monotonic
+  ret void
+}
+
+define void @pointer_cmpxchg_expand2(i8** %ptr, i8* %v) {
+; CHECK-LABEL: @pointer_cmpxchg_expand2
+; CHECK: %1 = bitcast i8** %ptr to i64*
+; CHECK: %2 = ptrtoint i8* %v to i64
+; CHECK: %3 = cmpxchg i64* %1, i64 0, i64 %2 release monotonic
+; CHECK: %4 = extractvalue { i64, i1 } %3, 0
+; CHECK: %5 = extractvalue { i64, i1 } %3, 1
+; CHECK: %6 = inttoptr i64 %4 to i8*
+; CHECK: %7 = insertvalue { i8*, i1 } undef, i8* %6, 0
+; CHECK: %8 = insertvalue { i8*, i1 } %7, i1 %5, 1
+  cmpxchg i8** %ptr, i8* null, i8* %v release monotonic
+  ret void
+}
+
+define void @pointer_cmpxchg_expand3(i8** %ptr, i8* %v) {
+; CHECK-LABEL: @pointer_cmpxchg_expand3
+; CHECK: %1 = bitcast i8** %ptr to i64*
+; CHECK: %2 = ptrtoint i8* %v to i64
+; CHECK: %3 = cmpxchg i64* %1, i64 0, i64 %2 seq_cst seq_cst
+; CHECK: %4 = extractvalue { i64, i1 } %3, 0
+; CHECK: %5 = extractvalue { i64, i1 } %3, 1
+; CHECK: %6 = inttoptr i64 %4 to i8*
+; CHECK: %7 = insertvalue { i8*, i1 } undef, i8* %6, 0
+; CHECK: %8 = insertvalue { i8*, i1 } %7, i1 %5, 1
+  cmpxchg i8** %ptr, i8* null, i8* %v seq_cst seq_cst
+  ret void
+}
+
+define void @pointer_cmpxchg_expand4(i8** %ptr, i8* %v) {
+; CHECK-LABEL: @pointer_cmpxchg_expand4
+; CHECK: %1 = bitcast i8** %ptr to i64*
+; CHECK: %2 = ptrtoint i8* %v to i64
+; CHECK: %3 = cmpxchg weak i64* %1, i64 0, i64 %2 seq_cst seq_cst
+; CHECK: %4 = extractvalue { i64, i1 } %3, 0
+; CHECK: %5 = extractvalue { i64, i1 } %3, 1
+; CHECK: %6 = inttoptr i64 %4 to i8*
+; CHECK: %7 = insertvalue { i8*, i1 } undef, i8* %6, 0
+; CHECK: %8 = insertvalue { i8*, i1 } %7, i1 %5, 1
+  cmpxchg weak i8** %ptr, i8* null, i8* %v seq_cst seq_cst
+  ret void
+}
+
+define void @pointer_cmpxchg_expand5(i8** %ptr, i8* %v) {
+; CHECK-LABEL: @pointer_cmpxchg_expand5
+; CHECK: %1 = bitcast i8** %ptr to i64*
+; CHECK: %2 = ptrtoint i8* %v to i64
+; CHECK: %3 = cmpxchg volatile i64* %1, i64 0, i64 %2 seq_cst seq_cst
+; CHECK: %4 = extractvalue { i64, i1 } %3, 0
+; CHECK: %5 = extractvalue { i64, i1 } %3, 1
+; CHECK: %6 = inttoptr i64 %4 to i8*
+; CHECK: %7 = insertvalue { i8*, i1 } undef, i8* %6, 0
+; CHECK: %8 = insertvalue { i8*, i1 } %7, i1 %5, 1
+  cmpxchg volatile i8** %ptr, i8* null, i8* %v seq_cst seq_cst
+  ret void
+}
+
+define void @pointer_cmpxchg_expand6(i8 addrspace(2)* addrspace(1)* %ptr, 
+                                     i8 addrspace(2)* %v) {
+; CHECK-LABEL: @pointer_cmpxchg_expand6
+; CHECK: %1 = bitcast i8 addrspace(2)* addrspace(1)* %ptr to i64 addrspace(1)*
+; CHECK: %2 = ptrtoint i8 addrspace(2)* %v to i64
+; CHECK: %3 = cmpxchg i64 addrspace(1)* %1, i64 0, i64 %2 seq_cst seq_cst
+; CHECK: %4 = extractvalue { i64, i1 } %3, 0
+; CHECK: %5 = extractvalue { i64, i1 } %3, 1
+; CHECK: %6 = inttoptr i64 %4 to i8 addrspace(2)*
+; CHECK: %7 = insertvalue { i8 addrspace(2)*, i1 } undef, i8 addrspace(2)* %6, 0
+; CHECK: %8 = insertvalue { i8 addrspace(2)*, i1 } %7, i1 %5, 1
+  cmpxchg i8 addrspace(2)* addrspace(1)* %ptr, i8 addrspace(2)* null, i8 addrspace(2)* %v seq_cst seq_cst
+  ret void
+}
+