[OMPIRBuilder] Add the support for compare capture

[tianshilei1992]

Summary

This patch adds the support for compare capture in OMPIRBuilder.

[tianshilei1992]

add test

[tianshilei1992]

rebase

[jdoerfert]

LG

[tianshilei1992]

rebase

[tianshilei1992]

rebase

[tianshilei1992]

rebase

clang/lib/CodeGen/CGStmtOpenMP.cpp

static void emitOMPAtomicCompareExpr(CodeGenFunction &CGF,
   Address XAddr = XLVal.getAddress(CGF);
   llvm::Value *EVal = CGF.EmitScalarExpr(E);
   llvm::Value *DVal = D ? CGF.EmitScalarExpr(D) : nullptr;
 
   llvm::OpenMPIRBuilder::AtomicOpValue XOpVal{
       XAddr.getPointer(), XAddr.getElementType(),
       X->getType()->hasSignedIntegerRepresentation(),
       X->getType().isVolatileQualified()};
+  llvm::OpenMPIRBuilder::AtomicOpValue VOpVal, ROpVal;
 
   CGF.Builder.restoreIP(OMPBuilder.createAtomicCompare(
-      CGF.Builder, XOpVal, EVal, DVal, AO, Op, IsXBinopExpr));
+      CGF.Builder, XOpVal, VOpVal, ROpVal, EVal, DVal, AO, Op, IsXBinopExpr,
+      /* IsPostfixUpdate */ false, /* IsFailOnly */ false));
 }
 
 static void emitOMPAtomicExpr(CodeGenFunction &CGF, OpenMPClauseKind Kind,
                               llvm::AtomicOrdering AO, bool IsPostfixUpdate,
                               const Expr *X, const Expr *V, const Expr *E,
                               const Expr *UE, const Expr *D, const Expr *CE,
                               bool IsXLHSInRHSPart, bool IsCompareCapture,
                               SourceLocation Loc) {

llvm/include/llvm/Frontend/OpenMP/OMPIRBuilder.h

public:
   InsertPointTy
   createAtomicCapture(const LocationDescription &Loc, InsertPointTy AllocaIP,
                       AtomicOpValue &X, AtomicOpValue &V, Value *Expr,
                       AtomicOrdering AO, AtomicRMWInst::BinOp RMWOp,
                       AtomicUpdateCallbackTy &UpdateOp, bool UpdateExpr,
                       bool IsPostfixUpdate, bool IsXBinopExpr);
 
   /// Emit atomic compare for constructs: --- Only scalar data types
-  /// cond-update-atomic:
+  /// cond-expr-stmt:
   /// x = x ordop expr ? expr : x;
   /// x = expr ordop x ? expr : x;
   /// x = x == e ? d : x;
   /// x = e == x ? d : x; (this one is not in the spec)
   /// cond-update-stmt:
   /// if (x ordop expr) { x = expr; }
   /// if (expr ordop x) { x = expr; }
   /// if (x == e) { x = d; }
   /// if (e == x) { x = d; } (this one is not in the spec)
+  /// conditional-update-capture-atomic:
+  /// v = x; cond-update-stmt; (IsPostfixUpdate=true, IsFailOnly=false)
+  /// cond-update-stmt; v = x; (IsPostfixUpdate=false, IsFailOnly=false)
+  /// if (x == e) { x = d; } else { v = x; } (IsPostfixUpdate=false,
+  ///                                         IsFailOnly=true)
+  /// r = x == e; if (r) { x = d; } (IsPostfixUpdate=false, IsFailOnly=false)
+  /// r = x == e; if (r) { x = d; } else { v = x; } (IsPostfixUpdate=false,
+  ///                                                IsFailOnly=true)
   ///
   /// \param Loc          The insert and source location description.
   /// \param X            The target atomic pointer to be updated.
+  /// \param V            Memory address where to store captured value (for
+  ///                     compare capture only).
+  /// \param R            Memory address where to store comparison result
+  ///                     (for compare capture with '==' only).
   /// \param E            The expected value ('e') for forms that use an
   ///                     equality comparison or an expression ('expr') for
   ///                     forms that use 'ordop' (logically an atomic maximum or
   ///                     minimum).
   /// \param D            The desired value for forms that use an equality
   ///                     comparison. If forms that use 'ordop', it should be
   ///                     \p nullptr.
   /// \param AO           Atomic ordering of the generated atomic instructions.
   /// \param Op           Atomic compare operation. It can only be ==, <, or >.
   /// \param IsXBinopExpr True if the conditional statement is in the form where
   ///                     x is on LHS. It only matters for < or >.
+  /// \param IsPostfixUpdate  True if original value of 'x' must be stored in
+  ///                         'v', not an updated one (for compare capture
+  ///                         only).
+  /// \param IsFailOnly   True if the original value of 'x' is stored to 'v'
+  ///                     only when the comparison fails. This is only valid for
+  ///                     the case the comparison is '=='.
   ///
   /// \return Insertion point after generated atomic capture IR.
-  InsertPointTy createAtomicCompare(const LocationDescription &Loc,
-                                    AtomicOpValue &X, Value *E, Value *D,
-                                    AtomicOrdering AO,
-                                    omp::OMPAtomicCompareOp Op,
-                                    bool IsXBinopExpr);
+  InsertPointTy
+  createAtomicCompare(const LocationDescription &Loc, AtomicOpValue &X,
+                      AtomicOpValue &V, AtomicOpValue &R, Value *E, Value *D,
+                      AtomicOrdering AO, omp::OMPAtomicCompareOp Op,
+                      bool IsXBinopExpr, bool IsPostfixUpdate, bool IsFailOnly);
 
   /// Create the control flow structure of a canonical OpenMP loop.
   ///
   /// The emitted loop will be disconnected, i.e. no edge to the loop's
   /// preheader and no terminator in the AfterBB. The OpenMPIRBuilder's
   /// IRBuilder location is not preserved.
   ///
   /// \param DL        DebugLoc used for the instructions in the skeleton.

llvm/lib/Frontend/OpenMP/OMPIRBuilder.cpp

OpenMPIRBuilder::InsertPointTy OpenMPIRBuilder::createAtomicCapture(
   Value *CapturedVal = (IsPostfixUpdate ? Result.first : Result.second);
   Builder.CreateStore(CapturedVal, V.Var, V.IsVolatile);
 
   checkAndEmitFlushAfterAtomic(Loc, AO, AtomicKind::Capture);
   return Builder.saveIP();
 }
 
 OpenMPIRBuilder::InsertPointTy OpenMPIRBuilder::createAtomicCompare(
-    const LocationDescription &Loc, AtomicOpValue &X, Value *E, Value *D,
-    AtomicOrdering AO, OMPAtomicCompareOp Op, bool IsXBinopExpr) {
+    const LocationDescription &Loc, AtomicOpValue &X, AtomicOpValue &V,
+    AtomicOpValue &R, Value *E, Value *D, AtomicOrdering AO,
+    omp::OMPAtomicCompareOp Op, bool IsXBinopExpr, bool IsPostfixUpdate,
+    bool IsFailOnly) {
+
   if (!updateToLocation(Loc))
     return Loc.IP;
 
   assert(X.Var->getType()->isPointerTy() &&
          "OMP atomic expects a pointer to target memory");
   assert((X.ElemTy->isIntegerTy() || X.ElemTy->isPointerTy()) &&
          "OMP atomic compare expected a integer scalar type");
+  // compare capture
+  if (V.Var) {
+    assert(V.Var->getType()->isPointerTy() && "v.var must be of pointer type");
+    assert(V.ElemTy == X.ElemTy && "x and v must be of same type");
+  }
 
   if (Op == OMPAtomicCompareOp::EQ) {
     AtomicOrdering Failure = AtomicCmpXchgInst::getStrongestFailureOrdering(AO);
-    // We don't need the result for now.
-    (void)Builder.CreateAtomicCmpXchg(X.Var, E, D, MaybeAlign(), AO, Failure);
+    AtomicCmpXchgInst *Result =
+        Builder.CreateAtomicCmpXchg(X.Var, E, D, MaybeAlign(), AO, Failure);
+    if (V.Var) {
+      Value *OldValue = Builder.CreateExtractValue(Result, /*Idxs=*/0);
+      assert(OldValue->getType() == V.ElemTy &&
+             "OldValue and V must be of same type");
+      if (IsPostfixUpdate) {
+        Builder.CreateStore(OldValue, V.Var, V.IsVolatile);
+      } else {
+        Value *SuccessOrFail = Builder.CreateExtractValue(Result, /*Idxs=*/1);
+        if (IsFailOnly) {
+          // CurBB----
+          //   |     |
+          //   v     |
+          // ContBB  |
+          //   |     |
+          //   v     |
+          // ExitBB <-
+          //
+          // where ContBB only contains the store of old value to 'v'.
+          BasicBlock *CurBB = Builder.GetInsertBlock();
+          Instruction *CurBBTI = CurBB->getTerminator();
+          CurBBTI = CurBBTI ? CurBBTI : Builder.CreateUnreachable();
+          BasicBlock *ExitBB = CurBB->splitBasicBlock(
+              CurBBTI, X.Var->getName() + ".atomic.exit");
+          BasicBlock *ContBB = CurBB->splitBasicBlock(
+              CurBB->getTerminator(), X.Var->getName() + ".atomic.cont");
+          ContBB->getTerminator()->eraseFromParent();
+          CurBB->getTerminator()->eraseFromParent();
+
+          Builder.CreateCondBr(SuccessOrFail, ExitBB, ContBB);
+
+          Builder.SetInsertPoint(ContBB);
+          Builder.CreateStore(OldValue, V.Var);
+          Builder.CreateBr(ExitBB);
+
+          if (UnreachableInst *ExitTI =
+                  dyn_cast<UnreachableInst>(ExitBB->getTerminator())) {
+            CurBBTI->eraseFromParent();
+            Builder.SetInsertPoint(ExitBB);
+          } else {
+            Builder.SetInsertPoint(ExitTI);
+          }
+        } else {
+          Value *CapturedValue =
+              Builder.CreateSelect(SuccessOrFail, E, OldValue);
+          Builder.CreateStore(CapturedValue, V.Var, V.IsVolatile);
+        }
+      }
+    }
+    // The comparison result has to be stored.
+    if (R.Var) {
+      assert(R.Var->getType()->isPointerTy() &&
+             "r.var must be of pointer type");
+      assert(R.ElemTy->isIntegerTy() && "r must be of integral type");
+
+      Value *SuccessFailureVal = Builder.CreateExtractValue(Result, /*Idxs=*/1);
+      Value *ResultCast = R.IsSigned
+                              ? Builder.CreateSExt(SuccessFailureVal, R.ElemTy)
+                              : Builder.CreateZExt(SuccessFailureVal, R.ElemTy);
+      Builder.CreateStore(ResultCast, R.Var, R.IsVolatile);
+    }
   } else {
     assert((Op == OMPAtomicCompareOp::MAX || Op == OMPAtomicCompareOp::MIN) &&
            "Op should be either max or min at this point");
+    assert(!IsFailOnly && "IsFailOnly is only valid when the comparison is ==");
 
     // Reverse the ordop as the OpenMP forms are different from LLVM forms.
     // Let's take max as example.
     // OpenMP form:
     // x = x > expr ? expr : x;
     // LLVM form:
     // *ptr = *ptr > val ? *ptr : val;
     // We need to transform to LLVM form.
if (Op == OMPAtomicCompareOp::EQ) {
     } else {
       if (X.IsSigned)
         NewOp = Op == OMPAtomicCompareOp::MAX ? AtomicRMWInst::Max
                                               : AtomicRMWInst::Min;
       else
         NewOp = Op == OMPAtomicCompareOp::MAX ? AtomicRMWInst::UMax
                                               : AtomicRMWInst::UMin;
     }
-    // We dont' need the result for now.
-    (void)Builder.CreateAtomicRMW(NewOp, X.Var, E, MaybeAlign(), AO);
+
+    AtomicRMWInst *OldValue =
+        Builder.CreateAtomicRMW(NewOp, X.Var, E, MaybeAlign(), AO);
+    if (V.Var) {
+      Value *CapturedValue = nullptr;
+      if (IsPostfixUpdate) {
+        CapturedValue = OldValue;
+      } else {
+        CmpInst::Predicate Pred;
+        switch (NewOp) {
+        case AtomicRMWInst::Max:
+          Pred = CmpInst::ICMP_SGT;
+          break;
+        case AtomicRMWInst::UMax:
+          Pred = CmpInst::ICMP_UGT;
+          break;
+        case AtomicRMWInst::Min:
+          Pred = CmpInst::ICMP_SLT;
+          break;
+        case AtomicRMWInst::UMin:
+          Pred = CmpInst::ICMP_ULT;
+          break;
+        default:
+          llvm_unreachable("unexpected comparison op");
+        }
+        Value *NonAtomicCmp = Builder.CreateCmp(Pred, OldValue, E);
+        CapturedValue = Builder.CreateSelect(NonAtomicCmp, E, OldValue);
+      }
+      Builder.CreateStore(CapturedValue, V.Var, V.IsVolatile);
+    }
   }
 
   checkAndEmitFlushAfterAtomic(Loc, AO, AtomicKind::Compare);
 
   return Builder.saveIP();
 }
 
 GlobalVariable *

llvm/unittests/Frontend/OpenMPIRBuilderTest.cpp

TEST_F(OpenMPIRBuilderTest, OMPAtomicCompare) {
   IntegerType *Int32 = Type::getInt32Ty(Ctx);
   AllocaInst *XVal = Builder.CreateAlloca(Int32);
   XVal->setName("x");
   StoreInst *Init =
       Builder.CreateStore(ConstantInt::get(Type::getInt32Ty(Ctx), 0U), XVal);
 
   OpenMPIRBuilder::AtomicOpValue XSigned = {XVal, Int32, true, false};
   OpenMPIRBuilder::AtomicOpValue XUnsigned = {XVal, Int32, false, false};
+  // V and R are not used in atomic compare
+  OpenMPIRBuilder::AtomicOpValue V = {nullptr, nullptr, false, false};
+  OpenMPIRBuilder::AtomicOpValue R = {nullptr, nullptr, false, false};
   AtomicOrdering AO = AtomicOrdering::Monotonic;
   ConstantInt *Expr = ConstantInt::get(Type::getInt32Ty(Ctx), 1U);
   ConstantInt *D = ConstantInt::get(Type::getInt32Ty(Ctx), 1U);
   OMPAtomicCompareOp OpMax = OMPAtomicCompareOp::MAX;
   OMPAtomicCompareOp OpEQ = OMPAtomicCompareOp::EQ;
 
-  Builder.restoreIP(OMPBuilder.createAtomicCompare(Builder, XSigned, Expr,
-                                                   nullptr, AO, OpMax, true));
-  Builder.restoreIP(OMPBuilder.createAtomicCompare(Builder, XUnsigned, Expr,
-                                                   nullptr, AO, OpMax, false));
-  Builder.restoreIP(OMPBuilder.createAtomicCompare(Builder, XSigned, Expr, D,
-                                                   AO, OpEQ, true));
+  Builder.restoreIP(OMPBuilder.createAtomicCompare(
+      Builder, XSigned, V, R, Expr, nullptr, AO, OpMax, true, false, false));
+  Builder.restoreIP(OMPBuilder.createAtomicCompare(
+      Builder, XUnsigned, V, R, Expr, nullptr, AO, OpMax, false, false, false));
+  Builder.restoreIP(OMPBuilder.createAtomicCompare(
+      Builder, XSigned, V, R, Expr, D, AO, OpEQ, true, false, false));
 
   BasicBlock *EntryBB = BB;
   EXPECT_EQ(EntryBB->getParent()->size(), 1U);
   EXPECT_EQ(EntryBB->size(), 5U);
 
   AtomicRMWInst *ARWM1 = dyn_cast<AtomicRMWInst>(Init->getNextNode());
   EXPECT_NE(ARWM1, nullptr);
   EXPECT_EQ(ARWM1->getPointerOperand(), XVal);
TEST_F(OpenMPIRBuilderTest, OMPAtomicCompare) {
   EXPECT_EQ(AXCHG->getCompareOperand(), Expr);
   EXPECT_EQ(AXCHG->getNewValOperand(), D);
 
   Builder.CreateRetVoid();
   OMPBuilder.finalize();
   EXPECT_FALSE(verifyModule(*M, &errs()));
 }
 
+TEST_F(OpenMPIRBuilderTest, OMPAtomicCompareCapture) {
+  OpenMPIRBuilder OMPBuilder(*M);
+  OMPBuilder.initialize();
+  F->setName("func");
+  IRBuilder<> Builder(BB);
+
+  OpenMPIRBuilder::LocationDescription Loc({Builder.saveIP(), DL});
+
+  LLVMContext &Ctx = M->getContext();
+  IntegerType *Int32 = Type::getInt32Ty(Ctx);
+  AllocaInst *XVal = Builder.CreateAlloca(Int32);
+  XVal->setName("x");
+  AllocaInst *VVal = Builder.CreateAlloca(Int32);
+  VVal->setName("v");
+  AllocaInst *RVal = Builder.CreateAlloca(Int32);
+  RVal->setName("r");
+
+  StoreInst *Init =
+      Builder.CreateStore(ConstantInt::get(Type::getInt32Ty(Ctx), 0U), XVal);
+
+  OpenMPIRBuilder::AtomicOpValue X = {XVal, Int32, true, false};
+  OpenMPIRBuilder::AtomicOpValue V = {VVal, Int32, false, false};
+  OpenMPIRBuilder::AtomicOpValue NoV = {nullptr, nullptr, false, false};
+  OpenMPIRBuilder::AtomicOpValue R = {RVal, Int32, false, false};
+  OpenMPIRBuilder::AtomicOpValue NoR = {nullptr, nullptr, false, false};
+
+  AtomicOrdering AO = AtomicOrdering::Monotonic;
+  ConstantInt *Expr = ConstantInt::get(Type::getInt32Ty(Ctx), 1U);
+  ConstantInt *D = ConstantInt::get(Type::getInt32Ty(Ctx), 1U);
+  OMPAtomicCompareOp OpMax = OMPAtomicCompareOp::MAX;
+  OMPAtomicCompareOp OpEQ = OMPAtomicCompareOp::EQ;
+
+  // { cond-update-stmt v = x; }
+  Builder.restoreIP(OMPBuilder.createAtomicCompare(
+      Builder, X, V, NoR, Expr, D, AO, OpEQ, /* IsXBinopExpr */ true,
+      /* IsPostfixUpdate */ false,
+      /* IsFailOnly */ false));
+  // { v = x; cond-update-stmt }
+  Builder.restoreIP(OMPBuilder.createAtomicCompare(
+      Builder, X, V, NoR, Expr, D, AO, OpEQ, /* IsXBinopExpr */ true,
+      /* IsPostfixUpdate */ true,
+      /* IsFailOnly */ false));
+  // if(x == e) { x = d; } else { v = x; }
+  Builder.restoreIP(OMPBuilder.createAtomicCompare(
+      Builder, X, V, NoR, Expr, D, AO, OpEQ, /* IsXBinopExpr */ true,
+      /* IsPostfixUpdate */ false,
+      /* IsFailOnly */ true));
+  // { r = x == e; if(r) { x = d; } }
+  Builder.restoreIP(OMPBuilder.createAtomicCompare(
+      Builder, X, NoV, R, Expr, D, AO, OpEQ, /* IsXBinopExpr */ true,
+      /* IsPostfixUpdate */ false,
+      /* IsFailOnly */ false));
+  // { r = x == e; if(r) { x = d; } else { v = x; } }
+  Builder.restoreIP(OMPBuilder.createAtomicCompare(
+      Builder, X, V, R, Expr, D, AO, OpEQ, /* IsXBinopExpr */ true,
+      /* IsPostfixUpdate */ false,
+      /* IsFailOnly */ true));
+
+  // { v = x; cond-update-stmt }
+  Builder.restoreIP(OMPBuilder.createAtomicCompare(
+      Builder, X, V, NoR, Expr, nullptr, AO, OpMax, /* IsXBinopExpr */ true,
+      /* IsPostfixUpdate */ true,
+      /* IsFailOnly */ false));
+  // { cond-update-stmt v = x; }
+  Builder.restoreIP(OMPBuilder.createAtomicCompare(
+      Builder, X, V, NoR, Expr, nullptr, AO, OpMax, /* IsXBinopExpr */ false,
+      /* IsPostfixUpdate */ false,
+      /* IsFailOnly */ false));
+
+  BasicBlock *EntryBB = BB;
+  EXPECT_EQ(EntryBB->getParent()->size(), 5U);
+  BasicBlock *Cont1 = dyn_cast<BasicBlock>(EntryBB->getNextNode());
+  EXPECT_NE(Cont1, nullptr);
+  BasicBlock *Exit1 = dyn_cast<BasicBlock>(Cont1->getNextNode());
+  EXPECT_NE(Exit1, nullptr);
+  BasicBlock *Cont2 = dyn_cast<BasicBlock>(Exit1->getNextNode());
+  EXPECT_NE(Cont2, nullptr);
+  BasicBlock *Exit2 = dyn_cast<BasicBlock>(Cont2->getNextNode());
+  EXPECT_NE(Exit2, nullptr);
+
+  AtomicCmpXchgInst *CmpXchg1 =
+      dyn_cast<AtomicCmpXchgInst>(Init->getNextNode());
+  EXPECT_NE(CmpXchg1, nullptr);
+  EXPECT_EQ(CmpXchg1->getPointerOperand(), XVal);
+  EXPECT_EQ(CmpXchg1->getCompareOperand(), Expr);
+  EXPECT_EQ(CmpXchg1->getNewValOperand(), D);
+  ExtractValueInst *ExtVal1 =
+      dyn_cast<ExtractValueInst>(CmpXchg1->getNextNode());
+  EXPECT_NE(ExtVal1, nullptr);
+  EXPECT_EQ(ExtVal1->getAggregateOperand(), CmpXchg1);
+  EXPECT_EQ(ExtVal1->getIndices(), ArrayRef<unsigned int>(0U));
+  ExtractValueInst *ExtVal2 =
+      dyn_cast<ExtractValueInst>(ExtVal1->getNextNode());
+  EXPECT_NE(ExtVal2, nullptr);
+  EXPECT_EQ(ExtVal2->getAggregateOperand(), CmpXchg1);
+  EXPECT_EQ(ExtVal2->getIndices(), ArrayRef<unsigned int>(1U));
+  SelectInst *Sel1 = dyn_cast<SelectInst>(ExtVal2->getNextNode());
+  EXPECT_NE(Sel1, nullptr);
+  EXPECT_EQ(Sel1->getCondition(), ExtVal2);
+  EXPECT_EQ(Sel1->getTrueValue(), Expr);
+  EXPECT_EQ(Sel1->getFalseValue(), ExtVal1);
+  StoreInst *Store1 = dyn_cast<StoreInst>(Sel1->getNextNode());
+  EXPECT_NE(Store1, nullptr);
+  EXPECT_EQ(Store1->getPointerOperand(), VVal);
+  EXPECT_EQ(Store1->getValueOperand(), Sel1);
+
+  AtomicCmpXchgInst *CmpXchg2 =
+      dyn_cast<AtomicCmpXchgInst>(Store1->getNextNode());
+  EXPECT_NE(CmpXchg2, nullptr);
+  EXPECT_EQ(CmpXchg2->getPointerOperand(), XVal);
+  EXPECT_EQ(CmpXchg2->getCompareOperand(), Expr);
+  EXPECT_EQ(CmpXchg2->getNewValOperand(), D);
+  ExtractValueInst *ExtVal3 =
+      dyn_cast<ExtractValueInst>(CmpXchg2->getNextNode());
+  EXPECT_NE(ExtVal3, nullptr);
+  EXPECT_EQ(ExtVal3->getAggregateOperand(), CmpXchg2);
+  EXPECT_EQ(ExtVal3->getIndices(), ArrayRef<unsigned int>(0U));
+  StoreInst *Store2 = dyn_cast<StoreInst>(ExtVal3->getNextNode());
+  EXPECT_NE(Store2, nullptr);
+  EXPECT_EQ(Store2->getPointerOperand(), VVal);
+  EXPECT_EQ(Store2->getValueOperand(), ExtVal3);
+
+  AtomicCmpXchgInst *CmpXchg3 =
+      dyn_cast<AtomicCmpXchgInst>(Store2->getNextNode());
+  EXPECT_NE(CmpXchg3, nullptr);
+  EXPECT_EQ(CmpXchg3->getPointerOperand(), XVal);
+  EXPECT_EQ(CmpXchg3->getCompareOperand(), Expr);
+  EXPECT_EQ(CmpXchg3->getNewValOperand(), D);
+  ExtractValueInst *ExtVal4 =
+      dyn_cast<ExtractValueInst>(CmpXchg3->getNextNode());
+  EXPECT_NE(ExtVal4, nullptr);
+  EXPECT_EQ(ExtVal4->getAggregateOperand(), CmpXchg3);
+  EXPECT_EQ(ExtVal4->getIndices(), ArrayRef<unsigned int>(0U));
+  ExtractValueInst *ExtVal5 =
+      dyn_cast<ExtractValueInst>(ExtVal4->getNextNode());
+  EXPECT_NE(ExtVal5, nullptr);
+  EXPECT_EQ(ExtVal5->getAggregateOperand(), CmpXchg3);
+  EXPECT_EQ(ExtVal5->getIndices(), ArrayRef<unsigned int>(1U));
+  BranchInst *Br1 = dyn_cast<BranchInst>(ExtVal5->getNextNode());
+  EXPECT_NE(Br1, nullptr);
+  EXPECT_EQ(Br1->isConditional(), true);
+  EXPECT_EQ(Br1->getCondition(), ExtVal5);
+  EXPECT_EQ(Br1->getSuccessor(0), Exit1);
+  EXPECT_EQ(Br1->getSuccessor(1), Cont1);
+
+  StoreInst *Store3 = dyn_cast<StoreInst>(&Cont1->front());
+  EXPECT_NE(Store3, nullptr);
+  EXPECT_EQ(Store3->getPointerOperand(), VVal);
+  EXPECT_EQ(Store3->getValueOperand(), ExtVal4);
+  BranchInst *Br2 = dyn_cast<BranchInst>(Store3->getNextNode());
+  EXPECT_NE(Br2, nullptr);
+  EXPECT_EQ(Br2->isUnconditional(), true);
+  EXPECT_EQ(Br2->getSuccessor(0), Exit1);
+
+  AtomicCmpXchgInst *CmpXchg4 = dyn_cast<AtomicCmpXchgInst>(&Exit1->front());
+  EXPECT_NE(CmpXchg4, nullptr);
+  EXPECT_EQ(CmpXchg4->getPointerOperand(), XVal);
+  EXPECT_EQ(CmpXchg4->getCompareOperand(), Expr);
+  EXPECT_EQ(CmpXchg4->getNewValOperand(), D);
+  ExtractValueInst *ExtVal6 =
+      dyn_cast<ExtractValueInst>(CmpXchg4->getNextNode());
+  EXPECT_NE(ExtVal6, nullptr);
+  EXPECT_EQ(ExtVal6->getAggregateOperand(), CmpXchg4);
+  EXPECT_EQ(ExtVal6->getIndices(), ArrayRef<unsigned int>(1U));
+  ZExtInst *ZExt1 = dyn_cast<ZExtInst>(ExtVal6->getNextNode());
+  EXPECT_NE(ZExt1, nullptr);
+  EXPECT_EQ(ZExt1->getDestTy(), Int32);
+  StoreInst *Store4 = dyn_cast<StoreInst>(ZExt1->getNextNode());
+  EXPECT_NE(Store4, nullptr);
+  EXPECT_EQ(Store4->getPointerOperand(), RVal);
+  EXPECT_EQ(Store4->getValueOperand(), ZExt1);
+
+  AtomicCmpXchgInst *CmpXchg5 =
+      dyn_cast<AtomicCmpXchgInst>(Store4->getNextNode());
+  EXPECT_NE(CmpXchg5, nullptr);
+  EXPECT_EQ(CmpXchg5->getPointerOperand(), XVal);
+  EXPECT_EQ(CmpXchg5->getCompareOperand(), Expr);
+  EXPECT_EQ(CmpXchg5->getNewValOperand(), D);
+  ExtractValueInst *ExtVal7 =
+      dyn_cast<ExtractValueInst>(CmpXchg5->getNextNode());
+  EXPECT_NE(ExtVal7, nullptr);
+  EXPECT_EQ(ExtVal7->getAggregateOperand(), CmpXchg5);
+  EXPECT_EQ(ExtVal7->getIndices(), ArrayRef<unsigned int>(0U));
+  ExtractValueInst *ExtVal8 =
+      dyn_cast<ExtractValueInst>(ExtVal7->getNextNode());
+  EXPECT_NE(ExtVal8, nullptr);
+  EXPECT_EQ(ExtVal8->getAggregateOperand(), CmpXchg5);
+  EXPECT_EQ(ExtVal8->getIndices(), ArrayRef<unsigned int>(1U));
+  BranchInst *Br3 = dyn_cast<BranchInst>(ExtVal8->getNextNode());
+  EXPECT_NE(Br3, nullptr);
+  EXPECT_EQ(Br3->isConditional(), true);
+  EXPECT_EQ(Br3->getCondition(), ExtVal8);
+  EXPECT_EQ(Br3->getSuccessor(0), Exit2);
+  EXPECT_EQ(Br3->getSuccessor(1), Cont2);
+
+  StoreInst *Store5 = dyn_cast<StoreInst>(&Cont2->front());
+  EXPECT_NE(Store5, nullptr);
+  EXPECT_EQ(Store5->getPointerOperand(), VVal);
+  EXPECT_EQ(Store5->getValueOperand(), ExtVal7);
+  BranchInst *Br4 = dyn_cast<BranchInst>(Store5->getNextNode());
+  EXPECT_NE(Br4, nullptr);
+  EXPECT_EQ(Br4->isUnconditional(), true);
+  EXPECT_EQ(Br4->getSuccessor(0), Exit2);
+
+  ExtractValueInst *ExtVal9 = dyn_cast<ExtractValueInst>(&Exit2->front());
+  EXPECT_NE(ExtVal9, nullptr);
+  EXPECT_EQ(ExtVal9->getAggregateOperand(), CmpXchg5);
+  EXPECT_EQ(ExtVal9->getIndices(), ArrayRef<unsigned int>(1U));
+  ZExtInst *ZExt2 = dyn_cast<ZExtInst>(ExtVal9->getNextNode());
+  EXPECT_NE(ZExt2, nullptr);
+  EXPECT_EQ(ZExt2->getDestTy(), Int32);
+  StoreInst *Store6 = dyn_cast<StoreInst>(ZExt2->getNextNode());
+  EXPECT_NE(Store6, nullptr);
+  EXPECT_EQ(Store6->getPointerOperand(), RVal);
+  EXPECT_EQ(Store6->getValueOperand(), ZExt2);
+
+  AtomicRMWInst *ARWM1 = dyn_cast<AtomicRMWInst>(Store6->getNextNode());
+  EXPECT_NE(ARWM1, nullptr);
+  EXPECT_EQ(ARWM1->getPointerOperand(), XVal);
+  EXPECT_EQ(ARWM1->getValOperand(), Expr);
+  EXPECT_EQ(ARWM1->getOperation(), AtomicRMWInst::Min);
+  StoreInst *Store7 = dyn_cast<StoreInst>(ARWM1->getNextNode());
+  EXPECT_NE(Store7, nullptr);
+  EXPECT_EQ(Store7->getPointerOperand(), VVal);
+  EXPECT_EQ(Store7->getValueOperand(), ARWM1);
+
+  AtomicRMWInst *ARWM2 = dyn_cast<AtomicRMWInst>(Store7->getNextNode());
+  EXPECT_NE(ARWM2, nullptr);
+  EXPECT_EQ(ARWM2->getPointerOperand(), XVal);
+  EXPECT_EQ(ARWM2->getValOperand(), Expr);
+  EXPECT_EQ(ARWM2->getOperation(), AtomicRMWInst::Max);
+  CmpInst *Cmp1 = dyn_cast<CmpInst>(ARWM2->getNextNode());
+  EXPECT_NE(Cmp1, nullptr);
+  EXPECT_EQ(Cmp1->getPredicate(), CmpInst::ICMP_SGT);
+  EXPECT_EQ(Cmp1->getOperand(0), ARWM2);
+  EXPECT_EQ(Cmp1->getOperand(1), Expr);
+  SelectInst *Sel2 = dyn_cast<SelectInst>(Cmp1->getNextNode());
+  EXPECT_NE(Sel2, nullptr);
+  EXPECT_EQ(Sel2->getCondition(), Cmp1);
+  EXPECT_EQ(Sel2->getTrueValue(), Expr);
+  EXPECT_EQ(Sel2->getFalseValue(), ARWM2);
+  StoreInst *Store8 = dyn_cast<StoreInst>(Sel2->getNextNode());
+  EXPECT_NE(Store8, nullptr);
+  EXPECT_EQ(Store8->getPointerOperand(), VVal);
+  EXPECT_EQ(Store8->getValueOperand(), Sel2);
+
+  Builder.CreateRetVoid();
+  OMPBuilder.finalize();
+  EXPECT_FALSE(verifyModule(*M, &errs()));
+}
+
 /// Returns the single instruction of InstTy type in BB that uses the value V.
 /// If there is more than one such instruction, returns null.
 template <typename InstTy>
 static InstTy *findSingleUserInBlock(Value *V, BasicBlock *BB) {
   InstTy *Result = nullptr;
   for (User *U : V->users()) {
     auto *Inst = dyn_cast<InstTy>(U);
     if (!Inst || Inst->getParent() != BB)