OpenMPIRBuilderTest.cpp

//===- llvm/unittest/IR/OpenMPIRBuilderTest.cpp - OpenMPIRBuilder tests ---===//
//
// 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
//
//===----------------------------------------------------------------------===//

#include"llvm/Frontend/OpenMP/OMPConstants.h"
#include"llvm/Frontend/OpenMP/OMPIRBuilder.h"
#include"llvm/IR/BasicBlock.h"
#include"llvm/IR/DIBuilder.h"
#include"llvm/IR/Function.h"
#include"llvm/IR/InstIterator.h"
#include"llvm/IR/LLVMContext.h"
#include"llvm/IR/Module.h"
#include"llvm/IR/Verifier.h"
#include"llvm/Passes/PassBuilder.h"
#include"llvm/Transforms/Utils/BasicBlockUtils.h"
#include"gtest/gtest.h"

usingnamespacellvm;
usingnamespaceomp;

namespace {

/// Create an instruction that uses the values in \p Values. We use "printf"
/// just because it is often used for this purpose in test code, but it is never
/// executed here.
static CallInst *createPrintfCall(IRBuilder<> &Builder, StringRef FormatStr,
 ArrayRef<Value *> Values) {
 Module *M = Builder.GetInsertBlock()->getParent()->getParent();

 GlobalVariable *GV = Builder.CreateGlobalString(FormatStr, "", 0, M);
 Constant *Zero = ConstantInt::get(Type::getInt32Ty(M->getContext()), 0);
 Constant *Indices[] = {Zero, Zero};
 Constant *FormatStrConst =
ConstantExpr::getInBoundsGetElementPtr(GV->getValueType(), GV, Indices);

 Function *PrintfDecl = M->getFunction("printf");
if (!PrintfDecl) {
 GlobalValue::LinkageTypes Linkage = Function::ExternalLinkage;
 FunctionType *Ty = FunctionType::get(Builder.getInt32Ty(), true);
 PrintfDecl = Function::Create(Ty, Linkage, "printf", M);
 }

 SmallVector<Value *, 4> Args;
 Args.push_back(FormatStrConst);
 Args.append(Values.begin(), Values.end());
return Builder.CreateCall(PrintfDecl, Args);
}

/// Verify that blocks in \p RefOrder are corresponds to the depth-first visit
/// order the control flow of \p F.
///
/// This is an easy way to verify the branching structure of the CFG without
/// checking every branch instruction individually. For the CFG of a
/// CanonicalLoopInfo, the Cond BB's terminating branch's first edge is entering
/// the body, i.e. the DFS order corresponds to the execution order with one
/// loop iteration.
static testing::AssertionResult
verifyDFSOrder(Function *F, ArrayRef<BasicBlock *> RefOrder) {
 ArrayRef<BasicBlock *>::iterator It = RefOrder.begin();
 ArrayRef<BasicBlock *>::iterator E = RefOrder.end();

 df_iterator_default_set<BasicBlock *, 16> Visited;
auto DFS = llvm::depth_first_ext(&F->getEntryBlock(), Visited);

 BasicBlock *Prev = nullptr;
for (BasicBlock *BB : DFS) {
if (It != E && BB == *It) {
 Prev = *It;
 ++It;
 }
 }

if (It == E)
returntesting::AssertionSuccess();
if (!Prev)
returntesting::AssertionFailure()
 << "Did not find " << (*It)->getName() << " in control flow";
returntesting::AssertionFailure()
 << "Expected " << Prev->getName() << " before " << (*It)->getName()
 << " in control flow";
}

/// Verify that blocks in \p RefOrder are in the same relative order in the
/// linked lists of blocks in \p F. The linked list may contain additional
/// blocks in-between.
///
/// While the order in the linked list is not relevant for semantics, keeping
/// the order roughly in execution order makes its printout easier to read.
static testing::AssertionResult
verifyListOrder(Function *F, ArrayRef<BasicBlock *> RefOrder) {
 ArrayRef<BasicBlock *>::iterator It = RefOrder.begin();
 ArrayRef<BasicBlock *>::iterator E = RefOrder.end();

 BasicBlock *Prev = nullptr;
for (BasicBlock &BB : *F) {
if (It != E && &BB == *It) {
 Prev = *It;
 ++It;
 }
 }

if (It == E)
returntesting::AssertionSuccess();
if (!Prev)
returntesting::AssertionFailure() << "Did not find " << (*It)->getName()
 << " in function " << F->getName();
returntesting::AssertionFailure()
 << "Expected " << Prev->getName() << " before " << (*It)->getName()
 << " in function " << F->getName();
}

classOpenMPIRBuilderTest : publictesting::Test {
protected:
voidSetUp() override {
 M.reset(newModule("MyModule", Ctx));
 FunctionType *FTy =
FunctionType::get(Type::getVoidTy(Ctx), {Type::getInt32Ty(Ctx)},
/*isVarArg=*/false);
 F = Function::Create(FTy, Function::ExternalLinkage, "", M.get());
 BB = BasicBlock::Create(Ctx, "", F);

 DIBuilder DIB(*M);
auto File = DIB.createFile("test.dbg", "/src", llvm::None,
 Optional<StringRef>("/src/test.dbg"));
auto CU =
 DIB.createCompileUnit(dwarf::DW_LANG_C, File, "llvm-C", true, "", 0);
auto Type = DIB.createSubroutineType(DIB.getOrCreateTypeArray(None));
auto SP = DIB.createFunction(
 CU, "foo", "", File, 1, Type, 1, DINode::FlagZero,
 DISubprogram::SPFlagDefinition | DISubprogram::SPFlagOptimized);
 F->setSubprogram(SP);
auto Scope = DIB.createLexicalBlockFile(SP, File, 0);
 DIB.finalize();
 DL = DILocation::get(Ctx, 3, 7, Scope);
 }

voidTearDown() override {
 BB = nullptr;
 M.reset();
 }

/// Create a function with a simple loop that calls printf using the logical
/// loop counter for use with tests that need a CanonicalLoopInfo object.
 CanonicalLoopInfo *buildSingleLoopFunction(DebugLoc DL,
 OpenMPIRBuilder &OMPBuilder,
 Instruction **Call = nullptr,
 BasicBlock **BodyCode = nullptr) {
 OMPBuilder.initialize();
 F->setName("func");

 IRBuilder<> Builder(BB);
 OpenMPIRBuilder::LocationDescription Loc({Builder.saveIP(), DL});
 Value *TripCount = F->getArg(0);

auto LoopBodyGenCB = [&](OpenMPIRBuilder::InsertPointTy CodeGenIP,
 llvm::Value *LC) {
 Builder.restoreIP(CodeGenIP);
if (BodyCode)
 *BodyCode = Builder.GetInsertBlock();

// Add something that consumes the induction variable to the body.
 CallInst *CallInst = createPrintfCall(Builder, "%d\\n", {LC});
if (Call)
 *Call = CallInst;
 };
 CanonicalLoopInfo *Loop =
 OMPBuilder.createCanonicalLoop(Loc, LoopBodyGenCB, TripCount);

// Finalize the function.
 Builder.restoreIP(Loop->getAfterIP());
 Builder.CreateRetVoid();

return Loop;
 }

 LLVMContext Ctx;
 std::unique_ptr<Module> M;
 Function *F;
 BasicBlock *BB;
 DebugLoc DL;
};

classOpenMPIRBuilderTestWithParams
 : public OpenMPIRBuilderTest,
 public ::testing::WithParamInterface<omp::OMPScheduleType> {};

// Returns the value stored in the given allocation. Returns null if the given
// value is not a result of an InstTy instruction, if no value is stored or if
// there is more than one store.
template <typename InstTy> static Value *findStoredValue(Value *AllocaValue) {
 Instruction *Inst = dyn_cast<InstTy>(AllocaValue);
if (!Inst)
returnnullptr;
 StoreInst *Store = nullptr;
for (Use &U : Inst->uses()) {
if (auto *CandidateStore = dyn_cast<StoreInst>(U.getUser())) {
EXPECT_EQ(Store, nullptr);
 Store = CandidateStore;
 }
 }
if (!Store)
returnnullptr;
return Store->getValueOperand();
}

TEST_F(OpenMPIRBuilderTest, CreateBarrier) {
 OpenMPIRBuilder OMPBuilder(*M);
 OMPBuilder.initialize();

 IRBuilder<> Builder(BB);

 OMPBuilder.createBarrier({IRBuilder<>::InsertPoint()}, OMPD_for);
EXPECT_TRUE(M->global_empty());
EXPECT_EQ(M->size(), 1U);
EXPECT_EQ(F->size(), 1U);
EXPECT_EQ(BB->size(), 0U);

 OpenMPIRBuilder::LocationDescription Loc({Builder.saveIP()});
 OMPBuilder.createBarrier(Loc, OMPD_for);
EXPECT_FALSE(M->global_empty());
EXPECT_EQ(M->size(), 3U);
EXPECT_EQ(F->size(), 1U);
EXPECT_EQ(BB->size(), 2U);

 CallInst *GTID = dyn_cast<CallInst>(&BB->front());
EXPECT_NE(GTID, nullptr);
EXPECT_EQ(GTID->arg_size(), 1U);
EXPECT_EQ(GTID->getCalledFunction()->getName(), "__kmpc_global_thread_num");
EXPECT_FALSE(GTID->getCalledFunction()->doesNotAccessMemory());
EXPECT_FALSE(GTID->getCalledFunction()->doesNotFreeMemory());

 CallInst *Barrier = dyn_cast<CallInst>(GTID->getNextNode());
EXPECT_NE(Barrier, nullptr);
EXPECT_EQ(Barrier->arg_size(), 2U);
EXPECT_EQ(Barrier->getCalledFunction()->getName(), "__kmpc_barrier");
EXPECT_FALSE(Barrier->getCalledFunction()->doesNotAccessMemory());
EXPECT_FALSE(Barrier->getCalledFunction()->doesNotFreeMemory());

EXPECT_EQ(cast<CallInst>(Barrier)->getArgOperand(1), GTID);

 Builder.CreateUnreachable();
EXPECT_FALSE(verifyModule(*M, &errs()));
}

TEST_F(OpenMPIRBuilderTest, CreateCancel) {
using InsertPointTy = OpenMPIRBuilder::InsertPointTy;
 OpenMPIRBuilder OMPBuilder(*M);
 OMPBuilder.initialize();

 BasicBlock *CBB = BasicBlock::Create(Ctx, "", F);
newUnreachableInst(Ctx, CBB);
auto FiniCB = [&](InsertPointTy IP) {
ASSERT_NE(IP.getBlock(), nullptr);
ASSERT_EQ(IP.getBlock()->end(), IP.getPoint());
BranchInst::Create(CBB, IP.getBlock());
 };
 OMPBuilder.pushFinalizationCB({FiniCB, OMPD_parallel, true});

 IRBuilder<> Builder(BB);

 OpenMPIRBuilder::LocationDescription Loc({Builder.saveIP()});
auto NewIP = OMPBuilder.createCancel(Loc, nullptr, OMPD_parallel);
 Builder.restoreIP(NewIP);
EXPECT_FALSE(M->global_empty());
EXPECT_EQ(M->size(), 4U);
EXPECT_EQ(F->size(), 4U);
EXPECT_EQ(BB->size(), 4U);

 CallInst *GTID = dyn_cast<CallInst>(&BB->front());
EXPECT_NE(GTID, nullptr);
EXPECT_EQ(GTID->arg_size(), 1U);
EXPECT_EQ(GTID->getCalledFunction()->getName(), "__kmpc_global_thread_num");
EXPECT_FALSE(GTID->getCalledFunction()->doesNotAccessMemory());
EXPECT_FALSE(GTID->getCalledFunction()->doesNotFreeMemory());

 CallInst *Cancel = dyn_cast<CallInst>(GTID->getNextNode());
EXPECT_NE(Cancel, nullptr);
EXPECT_EQ(Cancel->arg_size(), 3U);
EXPECT_EQ(Cancel->getCalledFunction()->getName(), "__kmpc_cancel");
EXPECT_FALSE(Cancel->getCalledFunction()->doesNotAccessMemory());
EXPECT_FALSE(Cancel->getCalledFunction()->doesNotFreeMemory());
EXPECT_EQ(Cancel->getNumUses(), 1U);
 Instruction *CancelBBTI = Cancel->getParent()->getTerminator();
EXPECT_EQ(CancelBBTI->getNumSuccessors(), 2U);
EXPECT_EQ(CancelBBTI->getSuccessor(0), NewIP.getBlock());
EXPECT_EQ(CancelBBTI->getSuccessor(1)->size(), 3U);
 CallInst *GTID1 = dyn_cast<CallInst>(&CancelBBTI->getSuccessor(1)->front());
EXPECT_NE(GTID1, nullptr);
EXPECT_EQ(GTID1->arg_size(), 1U);
EXPECT_EQ(GTID1->getCalledFunction()->getName(), "__kmpc_global_thread_num");
EXPECT_FALSE(GTID1->getCalledFunction()->doesNotAccessMemory());
EXPECT_FALSE(GTID1->getCalledFunction()->doesNotFreeMemory());
 CallInst *Barrier = dyn_cast<CallInst>(GTID1->getNextNode());
EXPECT_NE(Barrier, nullptr);
EXPECT_EQ(Barrier->arg_size(), 2U);
EXPECT_EQ(Barrier->getCalledFunction()->getName(), "__kmpc_cancel_barrier");
EXPECT_FALSE(Barrier->getCalledFunction()->doesNotAccessMemory());
EXPECT_FALSE(Barrier->getCalledFunction()->doesNotFreeMemory());
EXPECT_EQ(Barrier->getNumUses(), 0U);
EXPECT_EQ(CancelBBTI->getSuccessor(1)->getTerminator()->getNumSuccessors(),
1U);
EXPECT_EQ(CancelBBTI->getSuccessor(1)->getTerminator()->getSuccessor(0),
 CBB);

EXPECT_EQ(cast<CallInst>(Cancel)->getArgOperand(1), GTID);

 OMPBuilder.popFinalizationCB();

 Builder.CreateUnreachable();
EXPECT_FALSE(verifyModule(*M, &errs()));
}

TEST_F(OpenMPIRBuilderTest, CreateCancelIfCond) {
using InsertPointTy = OpenMPIRBuilder::InsertPointTy;
 OpenMPIRBuilder OMPBuilder(*M);
 OMPBuilder.initialize();

 BasicBlock *CBB = BasicBlock::Create(Ctx, "", F);
newUnreachableInst(Ctx, CBB);
auto FiniCB = [&](InsertPointTy IP) {
ASSERT_NE(IP.getBlock(), nullptr);
ASSERT_EQ(IP.getBlock()->end(), IP.getPoint());
BranchInst::Create(CBB, IP.getBlock());
 };
 OMPBuilder.pushFinalizationCB({FiniCB, OMPD_parallel, true});

 IRBuilder<> Builder(BB);

 OpenMPIRBuilder::LocationDescription Loc({Builder.saveIP()});
auto NewIP = OMPBuilder.createCancel(Loc, Builder.getTrue(), OMPD_parallel);
 Builder.restoreIP(NewIP);
EXPECT_FALSE(M->global_empty());
EXPECT_EQ(M->size(), 4U);
EXPECT_EQ(F->size(), 7U);
EXPECT_EQ(BB->size(), 1U);
ASSERT_TRUE(isa<BranchInst>(BB->getTerminator()));
ASSERT_EQ(BB->getTerminator()->getNumSuccessors(), 2U);
 BB = BB->getTerminator()->getSuccessor(0);
EXPECT_EQ(BB->size(), 4U);


 CallInst *GTID = dyn_cast<CallInst>(&BB->front());
EXPECT_NE(GTID, nullptr);
EXPECT_EQ(GTID->arg_size(), 1U);
EXPECT_EQ(GTID->getCalledFunction()->getName(), "__kmpc_global_thread_num");
EXPECT_FALSE(GTID->getCalledFunction()->doesNotAccessMemory());
EXPECT_FALSE(GTID->getCalledFunction()->doesNotFreeMemory());

 CallInst *Cancel = dyn_cast<CallInst>(GTID->getNextNode());
EXPECT_NE(Cancel, nullptr);
EXPECT_EQ(Cancel->arg_size(), 3U);
EXPECT_EQ(Cancel->getCalledFunction()->getName(), "__kmpc_cancel");
EXPECT_FALSE(Cancel->getCalledFunction()->doesNotAccessMemory());
EXPECT_FALSE(Cancel->getCalledFunction()->doesNotFreeMemory());
EXPECT_EQ(Cancel->getNumUses(), 1U);
 Instruction *CancelBBTI = Cancel->getParent()->getTerminator();
EXPECT_EQ(CancelBBTI->getNumSuccessors(), 2U);
EXPECT_EQ(CancelBBTI->getSuccessor(0)->size(), 1U);
EXPECT_EQ(CancelBBTI->getSuccessor(0)->getUniqueSuccessor(), NewIP.getBlock());
EXPECT_EQ(CancelBBTI->getSuccessor(1)->size(), 3U);
 CallInst *GTID1 = dyn_cast<CallInst>(&CancelBBTI->getSuccessor(1)->front());
EXPECT_NE(GTID1, nullptr);
EXPECT_EQ(GTID1->arg_size(), 1U);
EXPECT_EQ(GTID1->getCalledFunction()->getName(), "__kmpc_global_thread_num");
EXPECT_FALSE(GTID1->getCalledFunction()->doesNotAccessMemory());
EXPECT_FALSE(GTID1->getCalledFunction()->doesNotFreeMemory());
 CallInst *Barrier = dyn_cast<CallInst>(GTID1->getNextNode());
EXPECT_NE(Barrier, nullptr);
EXPECT_EQ(Barrier->arg_size(), 2U);
EXPECT_EQ(Barrier->getCalledFunction()->getName(), "__kmpc_cancel_barrier");
EXPECT_FALSE(Barrier->getCalledFunction()->doesNotAccessMemory());
EXPECT_FALSE(Barrier->getCalledFunction()->doesNotFreeMemory());
EXPECT_EQ(Barrier->getNumUses(), 0U);
EXPECT_EQ(CancelBBTI->getSuccessor(1)->getTerminator()->getNumSuccessors(),
1U);
EXPECT_EQ(CancelBBTI->getSuccessor(1)->getTerminator()->getSuccessor(0),
 CBB);

EXPECT_EQ(cast<CallInst>(Cancel)->getArgOperand(1), GTID);

 OMPBuilder.popFinalizationCB();

 Builder.CreateUnreachable();
EXPECT_FALSE(verifyModule(*M, &errs()));
}

TEST_F(OpenMPIRBuilderTest, CreateCancelBarrier) {
using InsertPointTy = OpenMPIRBuilder::InsertPointTy;
 OpenMPIRBuilder OMPBuilder(*M);
 OMPBuilder.initialize();

 BasicBlock *CBB = BasicBlock::Create(Ctx, "", F);
newUnreachableInst(Ctx, CBB);
auto FiniCB = [&](InsertPointTy IP) {
ASSERT_NE(IP.getBlock(), nullptr);
ASSERT_EQ(IP.getBlock()->end(), IP.getPoint());
BranchInst::Create(CBB, IP.getBlock());
 };
 OMPBuilder.pushFinalizationCB({FiniCB, OMPD_parallel, true});

 IRBuilder<> Builder(BB);

 OpenMPIRBuilder::LocationDescription Loc({Builder.saveIP()});
auto NewIP = OMPBuilder.createBarrier(Loc, OMPD_for);
 Builder.restoreIP(NewIP);
EXPECT_FALSE(M->global_empty());
EXPECT_EQ(M->size(), 3U);
EXPECT_EQ(F->size(), 4U);
EXPECT_EQ(BB->size(), 4U);

 CallInst *GTID = dyn_cast<CallInst>(&BB->front());
EXPECT_NE(GTID, nullptr);
EXPECT_EQ(GTID->arg_size(), 1U);
EXPECT_EQ(GTID->getCalledFunction()->getName(), "__kmpc_global_thread_num");
EXPECT_FALSE(GTID->getCalledFunction()->doesNotAccessMemory());
EXPECT_FALSE(GTID->getCalledFunction()->doesNotFreeMemory());

 CallInst *Barrier = dyn_cast<CallInst>(GTID->getNextNode());
EXPECT_NE(Barrier, nullptr);
EXPECT_EQ(Barrier->arg_size(), 2U);
EXPECT_EQ(Barrier->getCalledFunction()->getName(), "__kmpc_cancel_barrier");
EXPECT_FALSE(Barrier->getCalledFunction()->doesNotAccessMemory());
EXPECT_FALSE(Barrier->getCalledFunction()->doesNotFreeMemory());
EXPECT_EQ(Barrier->getNumUses(), 1U);
 Instruction *BarrierBBTI = Barrier->getParent()->getTerminator();
EXPECT_EQ(BarrierBBTI->getNumSuccessors(), 2U);
EXPECT_EQ(BarrierBBTI->getSuccessor(0), NewIP.getBlock());
EXPECT_EQ(BarrierBBTI->getSuccessor(1)->size(), 1U);
EXPECT_EQ(BarrierBBTI->getSuccessor(1)->getTerminator()->getNumSuccessors(),
1U);
EXPECT_EQ(BarrierBBTI->getSuccessor(1)->getTerminator()->getSuccessor(0),
 CBB);

EXPECT_EQ(cast<CallInst>(Barrier)->getArgOperand(1), GTID);

 OMPBuilder.popFinalizationCB();

 Builder.CreateUnreachable();
EXPECT_FALSE(verifyModule(*M, &errs()));
}

TEST_F(OpenMPIRBuilderTest, DbgLoc) {
 OpenMPIRBuilder OMPBuilder(*M);
 OMPBuilder.initialize();
 F->setName("func");

 IRBuilder<> Builder(BB);

 OpenMPIRBuilder::LocationDescription Loc({Builder.saveIP(), DL});
 OMPBuilder.createBarrier(Loc, OMPD_for);
 CallInst *GTID = dyn_cast<CallInst>(&BB->front());
 CallInst *Barrier = dyn_cast<CallInst>(GTID->getNextNode());
EXPECT_EQ(GTID->getDebugLoc(), DL);
EXPECT_EQ(Barrier->getDebugLoc(), DL);
EXPECT_TRUE(isa<GlobalVariable>(Barrier->getOperand(0)));
if (!isa<GlobalVariable>(Barrier->getOperand(0)))
return;
 GlobalVariable *Ident = cast<GlobalVariable>(Barrier->getOperand(0));
EXPECT_TRUE(Ident->hasInitializer());
if (!Ident->hasInitializer())
return;
 Constant *Initializer = Ident->getInitializer();
EXPECT_TRUE(
 isa<GlobalVariable>(Initializer->getOperand(4)->stripPointerCasts()));
 GlobalVariable *SrcStrGlob =
 cast<GlobalVariable>(Initializer->getOperand(4)->stripPointerCasts());
if (!SrcStrGlob)
return;
EXPECT_TRUE(isa<ConstantDataArray>(SrcStrGlob->getInitializer()));
 ConstantDataArray *SrcSrc =
 dyn_cast<ConstantDataArray>(SrcStrGlob->getInitializer());
if (!SrcSrc)
return;
EXPECT_EQ(SrcSrc->getAsCString(), ";/src/test.dbg;foo;3;7;;");
}

TEST_F(OpenMPIRBuilderTest, ParallelSimple) {
using InsertPointTy = OpenMPIRBuilder::InsertPointTy;
 OpenMPIRBuilder OMPBuilder(*M);
 OMPBuilder.initialize();
 F->setName("func");
 IRBuilder<> Builder(BB);

 OpenMPIRBuilder::LocationDescription Loc({Builder.saveIP(), DL});

 AllocaInst *PrivAI = nullptr;

unsigned NumBodiesGenerated = 0;
unsigned NumPrivatizedVars = 0;
unsigned NumFinalizationPoints = 0;

auto BodyGenCB = [&](InsertPointTy AllocaIP, InsertPointTy CodeGenIP,
 BasicBlock &ContinuationIP) {
 ++NumBodiesGenerated;

 Builder.restoreIP(AllocaIP);
 PrivAI = Builder.CreateAlloca(F->arg_begin()->getType());
 Builder.CreateStore(F->arg_begin(), PrivAI);

 Builder.restoreIP(CodeGenIP);
 Value *PrivLoad = Builder.CreateLoad(PrivAI->getAllocatedType(), PrivAI,
"local.use");
 Value *Cmp = Builder.CreateICmpNE(F->arg_begin(), PrivLoad);
 Instruction *ThenTerm, *ElseTerm;
SplitBlockAndInsertIfThenElse(Cmp, CodeGenIP.getBlock()->getTerminator(),
 &ThenTerm, &ElseTerm);

 Builder.SetInsertPoint(ThenTerm);
 Builder.CreateBr(&ContinuationIP);
 ThenTerm->eraseFromParent();
 };

auto PrivCB = [&](InsertPointTy AllocaIP, InsertPointTy CodeGenIP,
 Value &Orig, Value &Inner,
 Value *&ReplacementValue) -> InsertPointTy {
 ++NumPrivatizedVars;

if (!isa<AllocaInst>(Orig)) {
EXPECT_EQ(&Orig, F->arg_begin());
 ReplacementValue = &Inner;
return CodeGenIP;
 }

// Since the original value is an allocation, it has a pointer type and
// therefore no additional wrapping should happen.
EXPECT_EQ(&Orig, &Inner);

// Trivial copy (=firstprivate).
 Builder.restoreIP(AllocaIP);
 Type *VTy = Inner.getType()->getPointerElementType();
 Value *V = Builder.CreateLoad(VTy, &Inner, Orig.getName() + ".reload");
 ReplacementValue = Builder.CreateAlloca(VTy, 0, Orig.getName() + ".copy");
 Builder.restoreIP(CodeGenIP);
 Builder.CreateStore(V, ReplacementValue);
return CodeGenIP;
 };

auto FiniCB = [&](InsertPointTy CodeGenIP) { ++NumFinalizationPoints; };

 IRBuilder<>::InsertPoint AllocaIP(&F->getEntryBlock(),
 F->getEntryBlock().getFirstInsertionPt());
 IRBuilder<>::InsertPoint AfterIP =
 OMPBuilder.createParallel(Loc, AllocaIP, BodyGenCB, PrivCB, FiniCB,
nullptr, nullptr, OMP_PROC_BIND_default, false);
EXPECT_EQ(NumBodiesGenerated, 1U);
EXPECT_EQ(NumPrivatizedVars, 1U);
EXPECT_EQ(NumFinalizationPoints, 1U);

 Builder.restoreIP(AfterIP);
 Builder.CreateRetVoid();

 OMPBuilder.finalize();

EXPECT_NE(PrivAI, nullptr);
 Function *OutlinedFn = PrivAI->getFunction();
EXPECT_NE(F, OutlinedFn);
EXPECT_FALSE(verifyModule(*M, &errs()));
EXPECT_TRUE(OutlinedFn->hasFnAttribute(Attribute::NoUnwind));
EXPECT_TRUE(OutlinedFn->hasFnAttribute(Attribute::NoRecurse));
EXPECT_TRUE(OutlinedFn->hasParamAttribute(0, Attribute::NoAlias));
EXPECT_TRUE(OutlinedFn->hasParamAttribute(1, Attribute::NoAlias));

EXPECT_TRUE(OutlinedFn->hasInternalLinkage());
EXPECT_EQ(OutlinedFn->arg_size(), 3U);

EXPECT_EQ(&OutlinedFn->getEntryBlock(), PrivAI->getParent());
EXPECT_EQ(OutlinedFn->getNumUses(), 1U);
 User *Usr = OutlinedFn->user_back();
ASSERT_TRUE(isa<ConstantExpr>(Usr));
 CallInst *ForkCI = dyn_cast<CallInst>(Usr->user_back());
ASSERT_NE(ForkCI, nullptr);

EXPECT_EQ(ForkCI->getCalledFunction()->getName(), "__kmpc_fork_call");
EXPECT_EQ(ForkCI->arg_size(), 4U);
EXPECT_TRUE(isa<GlobalVariable>(ForkCI->getArgOperand(0)));
EXPECT_EQ(ForkCI->getArgOperand(1),
ConstantInt::get(Type::getInt32Ty(Ctx), 1U));
EXPECT_EQ(ForkCI->getArgOperand(2), Usr);
EXPECT_EQ(findStoredValue<AllocaInst>(ForkCI->getArgOperand(3)),
 F->arg_begin());
}

TEST_F(OpenMPIRBuilderTest, ParallelNested) {
using InsertPointTy = OpenMPIRBuilder::InsertPointTy;
 OpenMPIRBuilder OMPBuilder(*M);
 OMPBuilder.initialize();
 F->setName("func");
 IRBuilder<> Builder(BB);

 OpenMPIRBuilder::LocationDescription Loc({Builder.saveIP(), DL});

unsigned NumInnerBodiesGenerated = 0;
unsigned NumOuterBodiesGenerated = 0;
unsigned NumFinalizationPoints = 0;

auto InnerBodyGenCB = [&](InsertPointTy AllocaIP, InsertPointTy CodeGenIP,
 BasicBlock &ContinuationIP) {
 ++NumInnerBodiesGenerated;
 };

auto PrivCB = [&](InsertPointTy AllocaIP, InsertPointTy CodeGenIP,
 Value &Orig, Value &Inner,
 Value *&ReplacementValue) -> InsertPointTy {
// Trivial copy (=firstprivate).
 Builder.restoreIP(AllocaIP);
 Type *VTy = Inner.getType()->getPointerElementType();
 Value *V = Builder.CreateLoad(VTy, &Inner, Orig.getName() + ".reload");
 ReplacementValue = Builder.CreateAlloca(VTy, 0, Orig.getName() + ".copy");
 Builder.restoreIP(CodeGenIP);
 Builder.CreateStore(V, ReplacementValue);
return CodeGenIP;
 };

auto FiniCB = [&](InsertPointTy CodeGenIP) { ++NumFinalizationPoints; };

auto OuterBodyGenCB = [&](InsertPointTy AllocaIP, InsertPointTy CodeGenIP,
 BasicBlock &ContinuationIP) {
 ++NumOuterBodiesGenerated;
 Builder.restoreIP(CodeGenIP);
 BasicBlock *CGBB = CodeGenIP.getBlock();
 BasicBlock *NewBB = SplitBlock(CGBB, &*CodeGenIP.getPoint());
 CGBB->getTerminator()->eraseFromParent();
 ;

 IRBuilder<>::InsertPoint AfterIP = OMPBuilder.createParallel(
InsertPointTy(CGBB, CGBB->end()), AllocaIP, InnerBodyGenCB, PrivCB,
 FiniCB, nullptr, nullptr, OMP_PROC_BIND_default, false);

 Builder.restoreIP(AfterIP);
 Builder.CreateBr(NewBB);
 };

 IRBuilder<>::InsertPoint AllocaIP(&F->getEntryBlock(),
 F->getEntryBlock().getFirstInsertionPt());
 IRBuilder<>::InsertPoint AfterIP =
 OMPBuilder.createParallel(Loc, AllocaIP, OuterBodyGenCB, PrivCB, FiniCB,
nullptr, nullptr, OMP_PROC_BIND_default, false);

EXPECT_EQ(NumInnerBodiesGenerated, 1U);
EXPECT_EQ(NumOuterBodiesGenerated, 1U);
EXPECT_EQ(NumFinalizationPoints, 2U);

 Builder.restoreIP(AfterIP);
 Builder.CreateRetVoid();

 OMPBuilder.finalize();

EXPECT_EQ(M->size(), 5U);
for (Function &OutlinedFn : *M) {
if (F == &OutlinedFn || OutlinedFn.isDeclaration())
continue;
EXPECT_FALSE(verifyModule(*M, &errs()));
EXPECT_TRUE(OutlinedFn.hasFnAttribute(Attribute::NoUnwind));
EXPECT_TRUE(OutlinedFn.hasFnAttribute(Attribute::NoRecurse));
EXPECT_TRUE(OutlinedFn.hasParamAttribute(0, Attribute::NoAlias));
EXPECT_TRUE(OutlinedFn.hasParamAttribute(1, Attribute::NoAlias));

EXPECT_TRUE(OutlinedFn.hasInternalLinkage());
EXPECT_EQ(OutlinedFn.arg_size(), 2U);

EXPECT_EQ(OutlinedFn.getNumUses(), 1U);
 User *Usr = OutlinedFn.user_back();
ASSERT_TRUE(isa<ConstantExpr>(Usr));
 CallInst *ForkCI = dyn_cast<CallInst>(Usr->user_back());
ASSERT_NE(ForkCI, nullptr);

EXPECT_EQ(ForkCI->getCalledFunction()->getName(), "__kmpc_fork_call");
EXPECT_EQ(ForkCI->arg_size(), 3U);
EXPECT_TRUE(isa<GlobalVariable>(ForkCI->getArgOperand(0)));
EXPECT_EQ(ForkCI->getArgOperand(1),
ConstantInt::get(Type::getInt32Ty(Ctx), 0U));
EXPECT_EQ(ForkCI->getArgOperand(2), Usr);
 }
}

TEST_F(OpenMPIRBuilderTest, ParallelNested2Inner) {
using InsertPointTy = OpenMPIRBuilder::InsertPointTy;
 OpenMPIRBuilder OMPBuilder(*M);
 OMPBuilder.initialize();
 F->setName("func");
 IRBuilder<> Builder(BB);

 OpenMPIRBuilder::LocationDescription Loc({Builder.saveIP(), DL});

unsigned NumInnerBodiesGenerated = 0;
unsigned NumOuterBodiesGenerated = 0;
unsigned NumFinalizationPoints = 0;

auto InnerBodyGenCB = [&](InsertPointTy AllocaIP, InsertPointTy CodeGenIP,
 BasicBlock &ContinuationIP) {
 ++NumInnerBodiesGenerated;
 };

auto PrivCB = [&](InsertPointTy AllocaIP, InsertPointTy CodeGenIP,
 Value &Orig, Value &Inner,
 Value *&ReplacementValue) -> InsertPointTy {
// Trivial copy (=firstprivate).
 Builder.restoreIP(AllocaIP);
 Type *VTy = Inner.getType()->getPointerElementType();
 Value *V = Builder.CreateLoad(VTy, &Inner, Orig.getName() + ".reload");
 ReplacementValue = Builder.CreateAlloca(VTy, 0, Orig.getName() + ".copy");
 Builder.restoreIP(CodeGenIP);
 Builder.CreateStore(V, ReplacementValue);
return CodeGenIP;
 };

auto FiniCB = [&](InsertPointTy CodeGenIP) { ++NumFinalizationPoints; };

auto OuterBodyGenCB = [&](InsertPointTy AllocaIP, InsertPointTy CodeGenIP,
 BasicBlock &ContinuationIP) {
 ++NumOuterBodiesGenerated;
 Builder.restoreIP(CodeGenIP);
 BasicBlock *CGBB = CodeGenIP.getBlock();
 BasicBlock *NewBB1 = SplitBlock(CGBB, &*CodeGenIP.getPoint());
 BasicBlock *NewBB2 = SplitBlock(NewBB1, &*NewBB1->getFirstInsertionPt());
 CGBB->getTerminator()->eraseFromParent();
 ;
 NewBB1->getTerminator()->eraseFromParent();
 ;

 IRBuilder<>::InsertPoint AfterIP1 = OMPBuilder.createParallel(
InsertPointTy(CGBB, CGBB->end()), AllocaIP, InnerBodyGenCB, PrivCB,
 FiniCB, nullptr, nullptr, OMP_PROC_BIND_default, false);

 Builder.restoreIP(AfterIP1);
 Builder.CreateBr(NewBB1);

 IRBuilder<>::InsertPoint AfterIP2 = OMPBuilder.createParallel(
InsertPointTy(NewBB1, NewBB1->end()), AllocaIP, InnerBodyGenCB, PrivCB,
 FiniCB, nullptr, nullptr, OMP_PROC_BIND_default, false);

 Builder.restoreIP(AfterIP2);
 Builder.CreateBr(NewBB2);
 };

 IRBuilder<>::InsertPoint AllocaIP(&F->getEntryBlock(),
 F->getEntryBlock().getFirstInsertionPt());
 IRBuilder<>::InsertPoint AfterIP =
 OMPBuilder.createParallel(Loc, AllocaIP, OuterBodyGenCB, PrivCB, FiniCB,
nullptr, nullptr, OMP_PROC_BIND_default, false);

EXPECT_EQ(NumInnerBodiesGenerated, 2U);
EXPECT_EQ(NumOuterBodiesGenerated, 1U);
EXPECT_EQ(NumFinalizationPoints, 3U);

 Builder.restoreIP(AfterIP);
 Builder.CreateRetVoid();

 OMPBuilder.finalize();

EXPECT_EQ(M->size(), 6U);
for (Function &OutlinedFn : *M) {
if (F == &OutlinedFn || OutlinedFn.isDeclaration())
continue;
EXPECT_FALSE(verifyModule(*M, &errs()));
EXPECT_TRUE(OutlinedFn.hasFnAttribute(Attribute::NoUnwind));
EXPECT_TRUE(OutlinedFn.hasFnAttribute(Attribute::NoRecurse));
EXPECT_TRUE(OutlinedFn.hasParamAttribute(0, Attribute::NoAlias));
EXPECT_TRUE(OutlinedFn.hasParamAttribute(1, Attribute::NoAlias));

EXPECT_TRUE(OutlinedFn.hasInternalLinkage());
EXPECT_EQ(OutlinedFn.arg_size(), 2U);

unsigned NumAllocas = 0;
for (Instruction &I : instructions(OutlinedFn))
 NumAllocas += isa<AllocaInst>(I);
EXPECT_EQ(NumAllocas, 1U);

EXPECT_EQ(OutlinedFn.getNumUses(), 1U);
 User *Usr = OutlinedFn.user_back();
ASSERT_TRUE(isa<ConstantExpr>(Usr));
 CallInst *ForkCI = dyn_cast<CallInst>(Usr->user_back());
ASSERT_NE(ForkCI, nullptr);

EXPECT_EQ(ForkCI->getCalledFunction()->getName(), "__kmpc_fork_call");
EXPECT_EQ(ForkCI->arg_size(), 3U);
EXPECT_TRUE(isa<GlobalVariable>(ForkCI->getArgOperand(0)));
EXPECT_EQ(ForkCI->getArgOperand(1),
ConstantInt::get(Type::getInt32Ty(Ctx), 0U));
EXPECT_EQ(ForkCI->getArgOperand(2), Usr);
 }
}

TEST_F(OpenMPIRBuilderTest, ParallelIfCond) {
using InsertPointTy = OpenMPIRBuilder::InsertPointTy;
 OpenMPIRBuilder OMPBuilder(*M);
 OMPBuilder.initialize();
 F->setName("func");
 IRBuilder<> Builder(BB);

 OpenMPIRBuilder::LocationDescription Loc({Builder.saveIP(), DL});

 AllocaInst *PrivAI = nullptr;

unsigned NumBodiesGenerated = 0;
unsigned NumPrivatizedVars = 0;
unsigned NumFinalizationPoints = 0;

auto BodyGenCB = [&](InsertPointTy AllocaIP, InsertPointTy CodeGenIP,
 BasicBlock &ContinuationIP) {
 ++NumBodiesGenerated;

 Builder.restoreIP(AllocaIP);
 PrivAI = Builder.CreateAlloca(F->arg_begin()->getType());
 Builder.CreateStore(F->arg_begin(), PrivAI);

 Builder.restoreIP(CodeGenIP);
 Value *PrivLoad = Builder.CreateLoad(PrivAI->getAllocatedType(), PrivAI,
"local.use");
 Value *Cmp = Builder.CreateICmpNE(F->arg_begin(), PrivLoad);
 Instruction *ThenTerm, *ElseTerm;
SplitBlockAndInsertIfThenElse(Cmp, CodeGenIP.getBlock()->getTerminator(),
 &ThenTerm, &ElseTerm);

 Builder.SetInsertPoint(ThenTerm);
 Builder.CreateBr(&ContinuationIP);
 ThenTerm->eraseFromParent();
 };

auto PrivCB = [&](InsertPointTy AllocaIP, InsertPointTy CodeGenIP,
 Value &Orig, Value &Inner,
 Value *&ReplacementValue) -> InsertPointTy {
 ++NumPrivatizedVars;

if (!isa<AllocaInst>(Orig)) {
EXPECT_EQ(&Orig, F->arg_begin());
 ReplacementValue = &Inner;
return CodeGenIP;
 }

// Since the original value is an allocation, it has a pointer type and
// therefore no additional wrapping should happen.
EXPECT_EQ(&Orig, &Inner);

// Trivial copy (=firstprivate).
 Builder.restoreIP(AllocaIP);
 Type *VTy = Inner.getType()->getPointerElementType();
 Value *V = Builder.CreateLoad(VTy, &Inner, Orig.getName() + ".reload");
 ReplacementValue = Builder.CreateAlloca(VTy, 0, Orig.getName() + ".copy");
 Builder.restoreIP(CodeGenIP);
 Builder.CreateStore(V, ReplacementValue);
return CodeGenIP;
 };

auto FiniCB = [&](InsertPointTy CodeGenIP) {
 ++NumFinalizationPoints;
// No destructors.
 };

 IRBuilder<>::InsertPoint AllocaIP(&F->getEntryBlock(),
 F->getEntryBlock().getFirstInsertionPt());
 IRBuilder<>::InsertPoint AfterIP =
 OMPBuilder.createParallel(Loc, AllocaIP, BodyGenCB, PrivCB, FiniCB,
 Builder.CreateIsNotNull(F->arg_begin()),
nullptr, OMP_PROC_BIND_default, false);

EXPECT_EQ(NumBodiesGenerated, 1U);
EXPECT_EQ(NumPrivatizedVars, 1U);
EXPECT_EQ(NumFinalizationPoints, 1U);

 Builder.restoreIP(AfterIP);
 Builder.CreateRetVoid();
 OMPBuilder.finalize();

EXPECT_NE(PrivAI, nullptr);
 Function *OutlinedFn = PrivAI->getFunction();
EXPECT_NE(F, OutlinedFn);
EXPECT_FALSE(verifyModule(*M, &errs()));

EXPECT_TRUE(OutlinedFn->hasInternalLinkage());
EXPECT_EQ(OutlinedFn->arg_size(), 3U);

EXPECT_EQ(&OutlinedFn->getEntryBlock(), PrivAI->getParent());
ASSERT_EQ(OutlinedFn->getNumUses(), 2U);

 CallInst *DirectCI = nullptr;
 CallInst *ForkCI = nullptr;
for (User *Usr : OutlinedFn->users()) {
if (isa<CallInst>(Usr)) {
ASSERT_EQ(DirectCI, nullptr);
 DirectCI = cast<CallInst>(Usr);
 } else {
ASSERT_TRUE(isa<ConstantExpr>(Usr));
ASSERT_EQ(Usr->getNumUses(), 1U);
ASSERT_TRUE(isa<CallInst>(Usr->user_back()));
 ForkCI = cast<CallInst>(Usr->user_back());
 }
 }

EXPECT_EQ(ForkCI->getCalledFunction()->getName(), "__kmpc_fork_call");
EXPECT_EQ(ForkCI->arg_size(), 4U);
EXPECT_TRUE(isa<GlobalVariable>(ForkCI->getArgOperand(0)));
EXPECT_EQ(ForkCI->getArgOperand(1),
ConstantInt::get(Type::getInt32Ty(Ctx), 1));
 Value *StoredForkArg = findStoredValue<AllocaInst>(ForkCI->getArgOperand(3));
EXPECT_EQ(StoredForkArg, F->arg_begin());

EXPECT_EQ(DirectCI->getCalledFunction(), OutlinedFn);
EXPECT_EQ(DirectCI->arg_size(), 3U);
EXPECT_TRUE(isa<AllocaInst>(DirectCI->getArgOperand(0)));
EXPECT_TRUE(isa<AllocaInst>(DirectCI->getArgOperand(1)));
 Value *StoredDirectArg =
 findStoredValue<AllocaInst>(DirectCI->getArgOperand(2));
EXPECT_EQ(StoredDirectArg, F->arg_begin());
}

TEST_F(OpenMPIRBuilderTest, ParallelCancelBarrier) {
using InsertPointTy = OpenMPIRBuilder::InsertPointTy;
 OpenMPIRBuilder OMPBuilder(*M);
 OMPBuilder.initialize();
 F->setName("func");
 IRBuilder<> Builder(BB);

 OpenMPIRBuilder::LocationDescription Loc({Builder.saveIP(), DL});

unsigned NumBodiesGenerated = 0;
unsigned NumPrivatizedVars = 0;
unsigned NumFinalizationPoints = 0;

 CallInst *CheckedBarrier = nullptr;
auto BodyGenCB = [&](InsertPointTy AllocaIP, InsertPointTy CodeGenIP,
 BasicBlock &ContinuationIP) {
 ++NumBodiesGenerated;

 Builder.restoreIP(CodeGenIP);

// Create three barriers, two cancel barriers but only one checked.
 Function *CBFn, *BFn;

 Builder.restoreIP(
 OMPBuilder.createBarrier(Builder.saveIP(), OMPD_parallel));

 CBFn = M->getFunction("__kmpc_cancel_barrier");
 BFn = M->getFunction("__kmpc_barrier");
ASSERT_NE(CBFn, nullptr);
ASSERT_EQ(BFn, nullptr);
ASSERT_EQ(CBFn->getNumUses(), 1U);
ASSERT_TRUE(isa<CallInst>(CBFn->user_back()));
ASSERT_EQ(CBFn->user_back()->getNumUses(), 1U);
 CheckedBarrier = cast<CallInst>(CBFn->user_back());

 Builder.restoreIP(
 OMPBuilder.createBarrier(Builder.saveIP(), OMPD_parallel, true));
 CBFn = M->getFunction("__kmpc_cancel_barrier");
 BFn = M->getFunction("__kmpc_barrier");
ASSERT_NE(CBFn, nullptr);
ASSERT_NE(BFn, nullptr);
ASSERT_EQ(CBFn->getNumUses(), 1U);
ASSERT_EQ(BFn->getNumUses(), 1U);
ASSERT_TRUE(isa<CallInst>(BFn->user_back()));
ASSERT_EQ(BFn->user_back()->getNumUses(), 0U);

 Builder.restoreIP(OMPBuilder.createBarrier(Builder.saveIP(), OMPD_parallel,
false, false));
ASSERT_EQ(CBFn->getNumUses(), 2U);
ASSERT_EQ(BFn->getNumUses(), 1U);
ASSERT_TRUE(CBFn->user_back() != CheckedBarrier);
ASSERT_TRUE(isa<CallInst>(CBFn->user_back()));
ASSERT_EQ(CBFn->user_back()->getNumUses(), 0U);
 };

auto PrivCB = [&](InsertPointTy, InsertPointTy, Value &V, Value &,
 Value *&) -> InsertPointTy {
 ++NumPrivatizedVars;
llvm_unreachable("No privatization callback call expected!");
 };

 FunctionType *FakeDestructorTy =
FunctionType::get(Type::getVoidTy(Ctx), {Type::getInt32Ty(Ctx)},
/*isVarArg=*/false);
auto *FakeDestructor = Function::Create(
 FakeDestructorTy, Function::ExternalLinkage, "fakeDestructor", M.get());

auto FiniCB = [&](InsertPointTy IP) {
 ++NumFinalizationPoints;
 Builder.restoreIP(IP);
 Builder.CreateCall(FakeDestructor,
 {Builder.getInt32(NumFinalizationPoints)});
 };

 IRBuilder<>::InsertPoint AllocaIP(&F->getEntryBlock(),
 F->getEntryBlock().getFirstInsertionPt());
 IRBuilder<>::InsertPoint AfterIP =
 OMPBuilder.createParallel(Loc, AllocaIP, BodyGenCB, PrivCB, FiniCB,
 Builder.CreateIsNotNull(F->arg_begin()),
nullptr, OMP_PROC_BIND_default, true);

EXPECT_EQ(NumBodiesGenerated, 1U);
EXPECT_EQ(NumPrivatizedVars, 0U);
EXPECT_EQ(NumFinalizationPoints, 2U);
EXPECT_EQ(FakeDestructor->getNumUses(), 2U);

 Builder.restoreIP(AfterIP);
 Builder.CreateRetVoid();
 OMPBuilder.finalize();