diff --git a/llvm/include/llvm/Frontend/OpenMP/OMPConstants.h b/llvm/include/llvm/Frontend/OpenMP/OMPConstants.h --- a/llvm/include/llvm/Frontend/OpenMP/OMPConstants.h +++ b/llvm/include/llvm/Frontend/OpenMP/OMPConstants.h @@ -80,6 +80,11 @@ #define OMP_IDENT_FLAG(Enum, ...) constexpr auto Enum = omp::IdentFlag::Enum; #include "llvm/Frontend/OpenMP/OMPKinds.def" +enum class SchedType { +#define OMP_SCHED_TYPE(Enum, Str, Value) Enum = Value, +#include "llvm/Frontend/OpenMP/OMPKinds.def" +}; + /// Helper to describe assume clauses. struct AssumptionClauseMappingInfo { /// The identifier describing the (beginning of the) clause. diff --git a/llvm/include/llvm/Frontend/OpenMP/OMPIRBuilder.h b/llvm/include/llvm/Frontend/OpenMP/OMPIRBuilder.h --- a/llvm/include/llvm/Frontend/OpenMP/OMPIRBuilder.h +++ b/llvm/include/llvm/Frontend/OpenMP/OMPIRBuilder.h @@ -97,6 +97,11 @@ using BodyGenCallbackTy = function_ref; + // This is created primarily for sections construct as llvm::function_ref + // are not storable + using StorableBodyGenCallbackTy = + std::function; /// Callback type for loop body code generation. /// @@ -500,6 +505,27 @@ FinalizeCallbackTy FiniCB, StringRef CriticalName, Value *HintInst); + /// Generator for '#omp sections' + /// + /// \param Loc The insert and source location description. + /// \param AllocaIP The insertion points to be used for alloca instructions. + /// \param SectionCBs Callbacks that will generate body of each section. + /// \param SectionFiniCBs Callbacks that finalize each of the sections (count + /// must be equal to the number of sections). + /// \param PrivCB Callback to copy a given variable (think copy constructor). + /// \param FiniCB Callback to finalize variable copies. + /// \param IsCancellable Flag to indicate a cancellable parallel region. + /// \param IsNowait If true, barrier - to ensure all sections are executed + /// before moving forward will not be generated. + /// \returns The insertion position *after* the sections. + InsertPointTy createSections(const LocationDescription &Loc, + InsertPointTy AllocaIP, + ArrayRef SectionCBs, + ArrayRef SectionFiniCBs, + PrivatizeCallbackTy PrivCB, + FinalizeCallbackTy FiniCB, bool IsCancellable, + bool IsNowait); + /// Generate conditional branch and relevant BasicBlocks through which private /// threads copy the 'copyin' variables from Master copy to threadprivate /// copies. diff --git a/llvm/include/llvm/Frontend/OpenMP/OMPKinds.def b/llvm/include/llvm/Frontend/OpenMP/OMPKinds.def --- a/llvm/include/llvm/Frontend/OpenMP/OMPKinds.def +++ b/llvm/include/llvm/Frontend/OpenMP/OMPKinds.def @@ -1014,6 +1014,52 @@ ///} +/// OMP Scheduler Type Kinds +/// +/// See: +/// openmp/runtime/src/kmp.h - enum sched_type +///{ + +#ifndef OMP_SCHED_TYPE +#define OMP_SCHED_TYPE(Enum, Str, Value) +#endif + +#define __OMP_SCHED_TYPE(Name, Value) \ + OMP_SCHED_TYPE(OMP_SCHED_TYPE_##Name, #Name, Value) + +/// Lower bound for default (unordered) versions. +__OMP_SCHED_TYPE(SCH_LOWER, 32) +__OMP_SCHED_TYPE(SCH_STATIC_CHUNKED, 33) +__OMP_SCHED_TYPE(SCH_STATIC, 34) +__OMP_SCHED_TYPE(SCH_DYNAMIC_CHUNKED, 35) +__OMP_SCHED_TYPE(SCH_GUIDED_CHUNKED, 36) +__OMP_SCHED_TYPE(SCH_RUNTIME, 37) +__OMP_SCHED_TYPE(SCH_AUTO, 38) +/// static with chunk adjustment (e.g., simd) +__OMP_SCHED_TYPE(SCH_STATIC_BALANCED_CHUNKED, 45) +/// Lower bound for 'ordered' versions. +__OMP_SCHED_TYPE(ORD_LOWER, 64) +__OMP_SCHED_TYPE(ORD_STATIC_CHUNKED, 65) +__OMP_SCHED_TYPE(ORD_STATIC, 66) +__OMP_SCHED_TYPE(ORD_DYNAMIC_CHUNKED, 67) +__OMP_SCHED_TYPE(ORD_GUIDED_CHUNKED, 68) +__OMP_SCHED_TYPE(ORD_RUNTIME, 69) +__OMP_SCHED_TYPE(ORD_AUTO, 70) +__OMP_SCHED_TYPE(SCH_DEFAULT, 34) // = SCH_STATIC +/// dist_schedule types +__OMP_SCHED_TYPE(DIST_SCH_STATIC_CHUNKED, 91) +__OMP_SCHED_TYPE(DIST_SCH_STATIC, 92) +/// Support for OpenMP 4.5 monotonic and nonmonotonic schedule modifiers. +/// Set if the monotonic schedule modifier was present. +__OMP_SCHED_TYPE(SCH_MODIFIER_MONOTONIC, 1 << 29) +/// Set if the nonmonotonic schedule modifier was present. +__OMP_SCHED_TYPE(SCH_MODIFIER_NONMONOTONIC, 1 << 30) + +#undef __OMP_SCHED_TYPE +#undef OMP_SCHED_TYPE + +///} + /// KMP cancel kind /// ///{ diff --git a/llvm/lib/Frontend/OpenMP/OMPIRBuilder.cpp b/llvm/lib/Frontend/OpenMP/OMPIRBuilder.cpp --- a/llvm/lib/Frontend/OpenMP/OMPIRBuilder.cpp +++ b/llvm/lib/Frontend/OpenMP/OMPIRBuilder.cpp @@ -834,6 +834,152 @@ emitTaskyieldImpl(Loc); } +// TODO: Handle privatisation callbacks +OpenMPIRBuilder::InsertPointTy OpenMPIRBuilder::createSections( + const LocationDescription &Loc, InsertPointTy AllocaIP, + ArrayRef SectionCBs, + ArrayRef SectionFiniCBs, PrivatizeCallbackTy PrivCB, + FinalizeCallbackTy FiniCB, bool IsCancellable, bool IsNowait) { + if (!updateToLocation(Loc)) + return Loc.IP; + assert(SectionCBs.size() == SectionFiniCBs.size() && + "Each Section should have its own finalization callback"); + Constant *SrcLocStr = getOrCreateSrcLocStr(Loc); + Value *Ident = getOrCreateIdent(SrcLocStr); + Value *ThreadID = getOrCreateThreadID(Ident); + + InsertPointTy CurIP = Builder.saveIP(); + Builder.restoreIP(AllocaIP); + // Allocate helper vars for for loop + Value *LB = Builder.CreateAlloca(Int32, nullptr, "omp.sections.lb"); + Value *UB = Builder.CreateAlloca(Int32, nullptr, "omp.sections.ub"); + Value *ST = Builder.CreateAlloca(Int32, nullptr, "omp.sections.st"); + Value *IL = Builder.CreateAlloca(Int32, nullptr, "omp.sections.il"); + Value *IV = Builder.CreateAlloca(Int32, nullptr, "omp.sections.iv"); + + Builder.restoreIP(CurIP); + // Initialize helper vars for for loop + ConstantInt *GlobalUBVal = Builder.getInt32(SectionCBs.size() - 1); + Builder.CreateStore(Builder.getInt32(0), LB); + Builder.CreateStore(GlobalUBVal, UB); + Builder.CreateStore(Builder.getInt32(1), ST); + Builder.CreateStore(Builder.getInt32(0), IL); + + // Emit loop construct + // The Control Flow Graph is described as follows: + // loop condition (omp.sections.inner.for.cond) <-------------------- + // | (false) | + // |--------> loop exit ---> (end) | + // (true)| | + // v | + // loop body | + // | | + // switch-case construct, one case for each section (see below) | + // | | + // loop increment | + // | | + // ----------------------------------------------------------- + // TODO: Change the following to call the IR Builder function to emit kmpc_for + // after for loop is lowered. + Value *ForEntryArgs[] = { + Ident, + ThreadID, + Builder.getInt32(static_cast( + SchedType::OMP_SCHED_TYPE_SCH_STATIC)), // Schedule type + IL, // &isLastIter + LB, // &LB + UB, // &UB + ST, // &Stride + Builder.getInt32(1), // Incr + Builder.getInt32(1) // Chunk + }; + Function *EntryRTLFn = + getOrCreateRuntimeFunctionPtr(OMPRTL___kmpc_for_static_init_4); + Instruction *EntryCall = Builder.CreateCall(EntryRTLFn, ForEntryArgs); + Value *ForExitArgs[] = {Ident, ThreadID}; + Function *ExitRTLFn = + getOrCreateRuntimeFunctionPtr(OMPRTL___kmpc_for_static_fini); + Instruction *ExitCall = Builder.CreateCall(ExitRTLFn, ForExitArgs); + + auto BodyGenCB = [&](InsertPointTy AllocaIP, InsertPointTy CodeGenIP, + llvm::BasicBlock &FiniBB) { + auto *InsertBB = CodeGenIP.getBlock(); + auto *CurFn = InsertBB->getParent(); + Builder.SetInsertPoint(InsertBB->getTerminator()); + Instruction *LBRef = Builder.CreateLoad(LB); + Builder.CreateStore(LBRef, IV); + + auto *ForCondBB = InsertBB->splitBasicBlock(InsertBB->getTerminator(), + "omp.sections.inner.for.cond"); + auto *ForBodyBB = ForCondBB->splitBasicBlock(ForCondBB->getTerminator(), + "omp.sections.inner.for.body"); + auto *ForIncBB = ForBodyBB->splitBasicBlock(ForBodyBB->getTerminator(), + "omp.sections.inner.for.inc"); + auto *ForExitBB = ForIncBB->splitBasicBlock(ForIncBB->getTerminator(), + "omp.sections.inner.for.exit"); + // Terminators for these BB's are manually created later + ForCondBB->getTerminator()->eraseFromParent(); + ForBodyBB->getTerminator()->eraseFromParent(); + ForIncBB->getTerminator()->eraseFromParent(); + + // Setup the loop condition block + Builder.SetInsertPoint(ForCondBB); + Instruction *IVRef = Builder.CreateLoad(IV); + Instruction *UBRef = Builder.CreateLoad(UB); + Value *cmpRef = + Builder.CreateICmpSLE(IVRef, UBRef, "omp.sections.inner.for.cond.cmp"); + Builder.CreateCondBr(cmpRef, ForBodyBB, ForExitBB); + + // Setup the loop increment block + Builder.SetInsertPoint(ForIncBB); + Instruction *IVRef2 = Builder.CreateLoad(IV); + Value *Inc = Builder.CreateNSWAdd(IVRef2, Builder.getInt32(1), + "omp.sections.inner.for.inc.tmp_val"); + Builder.CreateStore(Inc, IV); + Builder.CreateBr(ForCondBB); + + // Setup loop body block + Builder.SetInsertPoint(ForBodyBB); + SwitchInst *SwitchStmt = + Builder.CreateSwitch(Builder.CreateLoad(IV), ForIncBB); + // each section in emitted as a switch case + // Iterate through all sections and emit a switch construct: + // switch (IV) { + // case 0: + // ; + // ; + // break; + // ... + // case - 1: + // - 1]>; + // - 1]>; + // break; + // } + // omp.sections.inner.for.inc: + // ; + unsigned CaseNumber = 0; + for (auto SectionCB : SectionCBs) { + auto *CaseBB = BasicBlock::Create( + M.getContext(), "omp.sections.inner.for.body.switch.case", CurFn); + SwitchStmt->addCase(Builder.getInt32(CaseNumber), CaseBB); + Builder.SetInsertPoint(CaseBB); + SectionCB(InsertPointTy(), Builder.saveIP(), *ForIncBB); + Builder.SetInsertPoint(CaseBB->getTerminator()); + SectionFiniCBs[CaseNumber](Builder.saveIP()); + CaseNumber++; + } + // Loop body ends here + + Builder.SetInsertPoint(ForExitBB->getTerminator()); + if (!IsNowait) + createBarrier(Builder, OMPD_sections, false, IsCancellable); + }; + + return EmitOMPInlinedRegion(Directive::OMPD_sections, EntryCall, ExitCall, + BodyGenCB, FiniCB, + /*Conditional*/ false, /*hasFinalize*/ true); +} + OpenMPIRBuilder::InsertPointTy OpenMPIRBuilder::createMaster(const LocationDescription &Loc, BodyGenCallbackTy BodyGenCB, diff --git a/llvm/unittests/Frontend/OpenMPIRBuilderTest.cpp b/llvm/unittests/Frontend/OpenMPIRBuilderTest.cpp --- a/llvm/unittests/Frontend/OpenMPIRBuilderTest.cpp +++ b/llvm/unittests/Frontend/OpenMPIRBuilderTest.cpp @@ -1437,4 +1437,149 @@ EXPECT_EQ(SingleEndCI->getArgOperand(1), SingleEntryCI->getArgOperand(1)); } +TEST_F(OpenMPIRBuilderTest, CreateSections) { + using InsertPointTy = OpenMPIRBuilder::InsertPointTy; + using BodyGenCallbackTy = llvm::OpenMPIRBuilder::StorableBodyGenCallbackTy; + using FinalizationCallbackTy = llvm::OpenMPIRBuilder::FinalizeCallbackTy; + OpenMPIRBuilder OMPBuilder(*M); + OMPBuilder.initialize(); + F->setName("func"); + IRBuilder<> Builder(BB); + + OpenMPIRBuilder::LocationDescription Loc({Builder.saveIP(), DL}); + llvm::SmallVector SectionCBVector; + llvm::SmallVector SectionFiniCBVector; + llvm::SmallVector CaseBBs; + + BasicBlock *SwitchBBPtr = nullptr; + BasicBlock *FiniBBPtr = + nullptr; // is actually loop's increment BB from code's point of view + AllocaInst *PrivAI = nullptr; + SwitchInst *Switch = nullptr; + + unsigned NumBodiesGenerated = 0; + unsigned NumFiniCBCalls = 0; + unsigned NumSectionFiniCBCalls = 0; + PrivAI = Builder.CreateAlloca(F->arg_begin()->getType()); + + auto FiniCB = [&](InsertPointTy IP) { + ++NumFiniCBCalls; + BasicBlock *IPBB = IP.getBlock(); + EXPECT_NE(IPBB->end(), IP.getPoint()); + }; + + auto SectionFiniCB = [&](InsertPointTy IP) { ++NumSectionFiniCBCalls; }; + + auto SectionCB = [&](InsertPointTy AllocaIP, InsertPointTy CodeGenIP, + BasicBlock &FiniBB) { + ++NumBodiesGenerated; + CaseBBs.push_back(CodeGenIP.getBlock()); + SwitchBBPtr = CodeGenIP.getBlock()->getSinglePredecessor(); + Builder.restoreIP(CodeGenIP); + Builder.CreateStore(F->arg_begin(), PrivAI); + Value *PrivLoad = Builder.CreateLoad(PrivAI, "local.alloca"); + Builder.CreateICmpNE(F->arg_begin(), PrivLoad); + Builder.CreateBr(&FiniBB); + FiniBBPtr = &FiniBB; + }; + auto PrivCB = [](InsertPointTy AllocaIP, InsertPointTy CodeGenIP, + llvm::Value &, llvm::Value &Val, llvm::Value *&ReplVal) { + // TODO: Privatization not implemented yet + return CodeGenIP; + }; + + SectionCBVector.push_back(SectionCB); + SectionCBVector.push_back(SectionCB); + SectionFiniCBVector.push_back(SectionFiniCB); + SectionFiniCBVector.push_back(SectionFiniCB); + + IRBuilder<>::InsertPoint AllocaIP(&F->getEntryBlock(), + F->getEntryBlock().getFirstInsertionPt()); + Builder.restoreIP(OMPBuilder.createSections(Loc, AllocaIP, SectionCBVector, + SectionFiniCBVector, PrivCB, + FiniCB, false, false)); + Builder.CreateRetVoid(); // Required at the end of the function + + EXPECT_NE(PrivAI, nullptr); + Function *OutlinedFn = PrivAI->getFunction(); + EXPECT_EQ(F, OutlinedFn); + EXPECT_FALSE(verifyModule(*M, &errs())); + EXPECT_EQ(OutlinedFn->arg_size(), 1U); + EXPECT_EQ(OutlinedFn->getBasicBlockList().size(), 7U); + + BasicBlock *EntryBB = &OutlinedFn->getBasicBlockList().front(); + // loop variables are 5 - lower bound, upper bound, stride, islastiter, and + // iterator/counter + size_t loop_var_count = 0; + bool found_for_init = false; + for (Instruction &Inst : *EntryBB) { + if (isa(Inst)) { + StoreInst *SI = cast(&Inst); + if (SI->getPointerOperand()->getName() == "omp.sections.lb") { + EXPECT_EQ(cast(SI->getValueOperand())->getValue(), 0U); + } else if (SI->getPointerOperand()->getName() == "omp.sections.ub") { + EXPECT_EQ(cast(SI->getValueOperand())->getValue(), 1U); + } else if (SI->getPointerOperand()->getName() == "omp.sections.st") { + EXPECT_EQ(cast(SI->getValueOperand())->getValue(), 1U); + } else if (SI->getPointerOperand()->getName() == "omp.sections.il") { + EXPECT_EQ(cast(SI->getValueOperand())->getValue(), 0U); + } else if (SI->getPointerOperand()->getName() == "omp.sections.iv") { + EXPECT_EQ(isa(SI->getValueOperand()), true); + LoadInst *Load = cast(SI->getValueOperand()); + EXPECT_EQ(Load->getPointerOperand()->getName(), "omp.sections.lb"); + } else { + continue; + } + ++loop_var_count; + } else if (isa(Inst)) { + if (cast(&Inst)->getCalledFunction()->getName() == + "__kmpc_for_static_init_4") { + found_for_init = true; + } + } + } + EXPECT_EQ(found_for_init, true); + EXPECT_EQ(loop_var_count, 5U); + + // Switch BB's predecessor is loop condition BB, whose successor at index 1 is + // loop's exit BB + BasicBlock *ForExitBB = + SwitchBBPtr->getSinglePredecessor()->getTerminator()->getSuccessor(1); + bool found_for_exit = false; + bool found_barrier = false; + for (Instruction &Inst : *ForExitBB) { + if (isa(Inst)) { + if (cast(&Inst)->getCalledFunction()->getName() == + "__kmpc_for_static_fini") { + found_for_exit = true; + } + if (cast(&Inst)->getCalledFunction()->getName() == + "__kmpc_barrier") { + found_barrier = true; + } + if (found_for_exit && found_barrier) + break; + } + } + EXPECT_EQ(found_for_exit, true); + EXPECT_EQ(found_barrier, true); + + EXPECT_NE(SwitchBBPtr, nullptr); + EXPECT_NE(SwitchBBPtr->getTerminator(), nullptr); + EXPECT_EQ(isa(SwitchBBPtr->getTerminator()), true); + Switch = cast(SwitchBBPtr->getTerminator()); + EXPECT_EQ(Switch->getNumCases(), 2U); + EXPECT_EQ(Switch->getSuccessor(0), FiniBBPtr); + + EXPECT_EQ(CaseBBs.size(), 2U); + for (auto *&CaseBB : CaseBBs) { + EXPECT_EQ(CaseBB->getParent(), OutlinedFn); + EXPECT_EQ(CaseBB->getSingleSuccessor(), FiniBBPtr); + } + + ASSERT_EQ(NumBodiesGenerated, 2U); + ASSERT_EQ(NumSectionFiniCBCalls, 2U); + ASSERT_EQ(NumFiniCBCalls, 1U); +} + } // namespace