[OpenMP][IRBuilder] Support allocas in nested parallel regions

[jdoerfert]

Summary

We need to keep track of the alloca insertion point (which we already
communicate via the callback to the user) as we place allocas as well.

[fghanim]

Thanks for the Patch. I have few questions to help me understand what's going on.

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

283

What's the benefit of this over just maintaining an alloca insertion point?

With this we will have 3 IRBuilders to maintain and keep track of: the clang (or flang) IRBuilder, the OMP IRBuilder and the allocaBuilder

292

I see two benefits of passing entry and exit blocks, as opposed to what we used to do:

1. less memory, but in return we collect blocks twice (i.e. O(N) mem & O(N+E) work vs O(1) mem and 2 * O(N+E) work ). Do you expect that the vector is likely to become large enough where it is a problem? if not, what's the benefit of the change?

2. If some blocks are added later, then this becomes a correctness issue. Which is unlikely since it happens after the body codegen is complete. However, if I am mistaken, shouldn't we also delay searching for inputs/outputs?

297

What is the benefit of passing blockSet when it is exclusively used inside of collectBlocks?
I don't think I saw a usage of it in calling functions. am I missing something?

[jdoerfert]

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

283

No functional difference. Basically the same reason why clang has an AllocIRBuilder (I think), we can use it independently of the other one. The alternative is to save the builder IP, set it to the alloca IP, do alloca stuff, reset the builder IP, when you use the AllocaIRBuilder below. Again, no functional difference, just less setting/resetting of IPs.

292

It is 2. Here, finalization steps will outline the inner region and introduce split blocks in the process. Those were not in the outer regions blocks vector which caused problems. The inputs/outputs are not allowed to change though, that invariant seems to hold fine.
(Once we do OpenMP loop transformations on this level other new blocks would be introduced during finalize.)

297

It's used in line 684 outside of collectBlocks.

[fghanim]

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

283

I understand where you are coming from, and I understand that functionally there is mostly no change - for now. But I prefer we do a small struct with some RAII, over adding an entire builder. I think it's a bit overkill and will be a source to lots of trouble.

Clang maintains an instruction AllocaInsertPt, not a specific builder. Speaking of which, This is completely from memory (i.e. check to make sure); I think we already save the previous AllocaInsertionPt in clang as part of the bodyGenCB. In which case, this is not needed; a nested parallel will always be generated by clang as part of the bodyGenCB, which in turn is going to save the Alloca insertion point for us.
To enable the creation of the allocas for TID and ZeroAddr in the outer function, Why not pass current AllocaInsertionPt as an arg. to createParallel

292

Oh right. Thanks for explaining that. :)
Nit: if possible, add a simple assert to check that inputs/outputs didn't change

297

Oh, Thanks. I missed that. :)
In this case; I think both the Blockset, and BlockVector have the same contents, correct? can't we use the vector instead on line 684, and keep the set local?

[jdoerfert]

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

283

I understand where you are coming from, and I understand that functionally there is mostly no change - for now. But I prefer we do a small struct with some RAII, over adding an entire builder. I think it's a bit overkill and will be a source to lots of trouble.

Could you explain what kind of overkill you see here? And maybe also the lots of trouble you expect from a builder versus a insertion point? It is the same information, just packed in a different struct, right?

Clang maintains an instruction AllocaInsertPt, not a specific builder.

Right.

Speaking of which, This is completely from memory (i.e. check to make sure); I think we already save the previous AllocaInsertionPt in clang as part of the bodyGenCB.

I think so.

In which case, this is not needed;

Not strictly, no.

a nested parallel will always be generated by clang as part of the bodyGenCB,

Yes.

which in turn is going to save the Alloca insertion point for us.

Yes.

To enable the creation of the allocas for TID and ZeroAddr in the outer function, Why not pass current AllocaInsertionPt as an arg. to createParallel

So far, because this will not be the only one that needs to create allocas. If you want to add the allocaIP to all runtime calls that create allocas, I'm fine with that too.

292

We can only if we remember them. I'll do it in debug builds I guess.

297

We could but we don't want to:
(1) that will make the currently logarithmic query in 684 linear, and
(2) we already compute the set during the vector construction because the we would get the same linear instead of logarithmic behavior there.

[anchu-rajendran]

The change looks good to me. Thanks!

[SouraVX]

Overall this seems great Thanks! I have one minor concern:
This patch seems to do 2 things: Support for nested parallel regions(which was crashing earlier) and some infrastructure change(introducing AllocBuilder..).
I'm not sure of this, but is it possible to separate these as 2( or more) patches ? 1 for Nested parallel region support and other patch as a infrastructure change ?

Main benefit of this approach would be that this would be easier to track/maintain changes in future.
Thanks!

[jdoerfert]

In D82470#2116581, @SouraVX wrote:

Overall this seems great Thanks! I have one minor concern:
This patch seems to do 2 things: Support for nested parallel regions(which was crashing earlier) and some infrastructure change(introducing AllocBuilder..).
I'm not sure of this, but is it possible to separate these as 2( or more) patches ? 1 for Nested parallel region support and other patch as a infrastructure change ?

I'll try.

[jdoerfert]

restrict this to the alloca support

[SouraVX]

In D82470#2118814, @jdoerfert wrote:

In D82470#2116581, @SouraVX wrote:

Overall this seems great Thanks! I have one minor concern:
This patch seems to do 2 things: Support for nested parallel regions(which was crashing earlier) and some infrastructure change(introducing AllocBuilder..).
I'm not sure of this, but is it possible to separate these as 2( or more) patches ? 1 for Nested parallel region support and other patch as a infrastructure change ?

I'll try.

Thanks a lot for separating this :) both LGTM!

[fghanim]

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

283

Could you explain what kind of overkill you see here?

Using an IRBuilder when an insertion point suffices

And maybe also the lots of trouble you expect from a builder versus a insertion point?

Currently, when using the OMPBuilder you need to juggle two IRBuilders, let's not make them 3 :)

It is the same information, just packed in a different struct, right?

no it is not. InsetrionPoint vs struct that contains Insertionpoint + other things. But that's beside the point

I mean, is the AllocaBuilder providing a new functionality other than a convenient way to keep track of the Alloca InsertionPoint?
Personally, I prefer some suitable structure to your needs and a stack (i.e. the way clang does it) . This should also resolve the todo below. Alternatively, pass an allocation point as an argument as suggested earlier. I am open to any third way if you have any.

[jdoerfert]

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

283

Personally, I prefer some suitable structure to your needs and a stack (i.e. the way clang does it).

The stack is already here, implicitly, and actually on the stack. With
IRBuilder<>::InsertPointGuard AIPG(AllocaBuilder);
we have all the stack we need without leaking the state.
The updates to the insertion point are done for use and the AllocaBuilder is always ready to be used. No need to create a builder or update an insertion point (other than the places that create the new alloca insertion points). Note that the suitable structure is the builder, as it is the only interaction with the insertion point, e.g. we do not pass the insertion point to other functions.

InsetrionPoint vs struct that contains Insertionpoint + other things. But that's beside the point

I disagree. The "other things" is the only interaction we have with the insertion point. So storing or accepting an insertion point is fine for the only purpose of creating a Builder and interacting with the builder. The difference is that we need to add more churn to update and reset the insertion point (what happens behind the scenes with the one line I quoted above).

Alternatively, pass an allocation point as an argument as suggested earlier.

I did not go this route because I think it complicates the API with little gain. I was also unsure what the flang situation looks like here. Do we have an alloca insertion point there too?
At the end of the day, this makes it easier for the user.

[fghanim]

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

283

But we haven't solved a problem, we just kicked it down the road with the TODO you added, with the only trade-off being convenience now. The AllocaBuilder is not usable by the frontend - the frontend doesn't & shouldn't know or care about any builders other than its own. However, an insertion point can be passed to the frontend (i.e. bodyCB). So keeping track of an Alloca insertion point across nests -similar to how clang does it- is what we need. I still prefer having a stack to push to - maybe even piggy back on the finalization stack by creating a struct that contains all relevant info per nest level. But you don't like it, fine.

Then just pass an argument for allocaIP and be done with it. Flang (or clang or whichever other frontend) are required to emit allocas into function entry block by all LLVM passes that follow. As such, we can safely assume the outermost call is always going to have the AllocaIP in the entry block of the enclosing function. Which means the first time we call CreateParallel they can pass that as arg.. or pass an empty insertion point, in which case we already detect it.

Adding a builder for every insertion point that we need to pass across nests or regions is not something we want to do for the reasons I mentioned earlier. Whether we like it or not, it is a builder we have to juggle along the other two, no matter how much we try to specialize its use, or keep it "hidden".

[jdoerfert]

Rebase

[jdoerfert]

Used an extra argument now. Please let me know if this is OK.

[fghanim]

Thanks for the update. Just a couple of Nits, and a quick note

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

288

Nit: isn't this supposed to be part of one of the other patches you split of this?

llvm/lib/Frontend/OpenMP/OMPIRBuilder.cpp

433

Here and elsewhere: You seem to have forgotten to undo the changes introduced by using a separate AllocaBuilder?

Also, Nit: before using AllocaIP, either add an assert that it is not empty, or alternatively, add logic to just set it to entry block of outerfn if it is

490

NIT: I think it would be better to give each a different name, to avoid unnecessary confusion. maybe OuterAllocaIP and innerAllocaIP? Also, we don't overwrite the outerAllocaIP in case it's needed later?

[jdoerfert]

I'll address the nits. Unsure if that is all. I also don't get the one comment.

llvm/lib/Frontend/OpenMP/OMPIRBuilder.cpp

433

Here and elsewhere: You seem to have forgotten to undo the changes introduced by using a separate AllocaBuilder?

I don't get this. These changes are on purpose.

[fghanim]

I'll address the nits.

Thanks :)

Unsure if that is all.

depends on the comment about AllocaBuilder

llvm/lib/Frontend/OpenMP/OMPIRBuilder.cpp

433

Oh, my bad. I assumed that since we now pass allocaip to communicate where is the insertion point, using builder the way we used to is sufficient, and this was leftover code. So now what purpose does AllocaBuilder serve?

[jdoerfert]

llvm/lib/Frontend/OpenMP/OMPIRBuilder.cpp

433

1. No switching the IP back and forth in one builder all the time.
2. Showing by the name of the builder directly where the instructions will be created.

[fghanim]

llvm/lib/Frontend/OpenMP/OMPIRBuilder.cpp

433

No switching the IP back and forth in one builder all the time.

• Is this about something you expect in the future? because unless I am missing something, and looking at it side by side, I don't see any less setting /reseting of IPs going on, except in the new version we to set the debug info IP in allocabuilder in addition to in builder.
• we don't use either AllocaIP after returning from bodyCB
• Even if we did, both bodyCB, and FiniCB have IPGuards inside them.
• Also, since IRBuilders do insertbefore an IP, both AllocaIP should be up-to-date except if the iterator for an IP gets invalidated, the risk of which is sort of proportional to increase in number of IRbuilders.

Showing by the name of the builder directly where the instructions will be created.

Wouldn't a comment be better?
Personally, I find it confusing when something called AllocaBuilder, is being used to emit loads and stores.

[jdoerfert]

Reuse builder

[fghanim]

Great. Thank you!
LGTM

clang/lib/CodeGen/CGStmtOpenMP.cpp

auto BodyGenCB = [ParallelRegionBodyStmt,
       OMPBuilderCBHelpers::OutlinedRegionBodyRAII ORB(*this, AllocaIP,
                                                       ContinuationBB);
       OMPBuilderCBHelpers::EmitOMPRegionBody(*this, ParallelRegionBodyStmt,
                                              CodeGenIP, ContinuationBB);
     };
 
     CGCapturedStmtInfo CGSI(*CS, CR_OpenMP);
     CodeGenFunction::CGCapturedStmtRAII CapInfoRAII(*this, &CGSI);
-    Builder.restoreIP(OMPBuilder.CreateParallel(Builder, BodyGenCB, PrivCB,
-                                                FiniCB, IfCond, NumThreads,
-                                                ProcBind, S.hasCancel()));
+    llvm::OpenMPIRBuilder::InsertPointTy AllocaIP(
+        AllocaInsertPt->getParent(), AllocaInsertPt->getIterator());
+    Builder.restoreIP(
+        OMPBuilder.CreateParallel(Builder, AllocaIP, BodyGenCB, PrivCB, FiniCB,
+                                  IfCond, NumThreads, ProcBind, S.hasCancel()));
     return;
   }
 
   // Emit parallel region as a standalone region.
   auto &&CodeGen = [&S](CodeGenFunction &CGF, PrePostActionTy &Action) {
     Action.Enter(CGF);
     OMPPrivateScope PrivateScope(CGF);
     bool Copyins = CGF.EmitOMPCopyinClause(S);

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

public:
   ///
   /// \returns The insertion point after the barrier.
   InsertPointTy CreateCancel(const LocationDescription &Loc, Value *IfCondition,
                              omp::Directive CanceledDirective);
 
   /// Generator for '#omp parallel'
   ///
   /// \param Loc The insert and source location description.
+  /// \param AllocaIP The insertion points to be used for alloca instructions.
   /// \param BodyGenCB Callback that will generate the region code.
   /// \param PrivCB Callback to copy a given variable (think copy constructor).
   /// \param FiniCB Callback to finalize variable copies.
   /// \param IfCondition The evaluated 'if' clause expression, if any.
   /// \param NumThreads The evaluated 'num_threads' clause expression, if any.
   /// \param ProcBind The value of the 'proc_bind' clause (see ProcBindKind).
   /// \param IsCancellable Flag to indicate a cancellable parallel region.
   ///
   /// \returns The insertion position *after* the parallel.
   IRBuilder<>::InsertPoint
-  CreateParallel(const LocationDescription &Loc, BodyGenCallbackTy BodyGenCB,
-                 PrivatizeCallbackTy PrivCB, FinalizeCallbackTy FiniCB,
-                 Value *IfCondition, Value *NumThreads,
-                 omp::ProcBindKind ProcBind, bool IsCancellable);
+  CreateParallel(const LocationDescription &Loc, InsertPointTy AllocaIP,
+                 BodyGenCallbackTy BodyGenCB, PrivatizeCallbackTy PrivCB,
+                 FinalizeCallbackTy FiniCB, Value *IfCondition,
+                 Value *NumThreads, omp::ProcBindKind ProcBind,
+                 bool IsCancellable);
 
   /// Generator for '#omp flush'
   ///
   /// \param Loc The location where the flush directive was encountered
   void CreateFlush(const LocationDescription &Loc);
 
   /// Generator for '#omp taskwait'
   ///
public:
   /// The underlying LLVM-IR module
   Module &M;
 
   /// The LLVM-IR Builder used to create IR.
   IRBuilder<> Builder;
 
   /// Map to remember source location strings
   StringMap<Constant *> SrcLocStrMap;
 
   /// Map to remember existing ident_t*.
   DenseMap<std::pair<Constant *, uint64_t>, GlobalVariable *> IdentMap;
 
   /// Helper that contains information about regions we need to outline
   /// during finalization.
   struct OutlineInfo {
-    SmallVector<BasicBlock *, 32> Blocks;
     using PostOutlineCBTy = std::function<void(Function &)>;
     PostOutlineCBTy PostOutlineCB;
     BasicBlock *EntryBB, *ExitBB;
 
     /// Collect all blocks in between EntryBB and ExitBB in both the given
     /// vector and set.
     void collectBlocks(SmallPtrSetImpl<BasicBlock *> &BlockSet,
                        SmallVectorImpl<BasicBlock *> &BlockVector);
   };
 
   /// Collection of regions that need to be outlined during finalization.
   SmallVector<OutlineInfo, 16> OutlineInfos;
 
   /// Add a new region that will be outlined later.
   void addOutlineInfo(OutlineInfo &&OI) { OutlineInfos.emplace_back(OI); }
 

llvm/lib/Frontend/OpenMP/OMPIRBuilder.cpp

void OpenMPIRBuilder::emitCancelationCheckImpl(
   auto &FI = FinalizationStack.back();
   FI.FiniCB(Builder.saveIP());
 
   // The continuation block is where code generation continues.
   Builder.SetInsertPoint(NonCancellationBlock, NonCancellationBlock->begin());
 }
 
 IRBuilder<>::InsertPoint OpenMPIRBuilder::CreateParallel(
-    const LocationDescription &Loc, BodyGenCallbackTy BodyGenCB,
-    PrivatizeCallbackTy PrivCB, FinalizeCallbackTy FiniCB, Value *IfCondition,
-    Value *NumThreads, omp::ProcBindKind ProcBind, bool IsCancellable) {
+    const LocationDescription &Loc, InsertPointTy AllocaIP,
+    BodyGenCallbackTy BodyGenCB, PrivatizeCallbackTy PrivCB,
+    FinalizeCallbackTy FiniCB, Value *IfCondition, Value *NumThreads,
+    omp::ProcBindKind ProcBind, bool IsCancellable) {
   if (!updateToLocation(Loc))
     return Loc.IP;
 
   Constant *SrcLocStr = getOrCreateSrcLocStr(Loc);
   Value *Ident = getOrCreateIdent(SrcLocStr);
   Value *ThreadID = getOrCreateThreadID(Ident);
 
   if (NumThreads) {
IRBuilder<>::InsertPoint OpenMPIRBuilder::CreateParallel(
 
   BasicBlock *InsertBB = Builder.GetInsertBlock();
   Function *OuterFn = InsertBB->getParent();
 
   // Vector to remember instructions we used only during the modeling but which
   // we want to delete at the end.
   SmallVector<Instruction *, 4> ToBeDeleted;
 
-  Builder.SetInsertPoint(OuterFn->getEntryBlock().getFirstNonPHI());
-  AllocaInst *TIDAddr = Builder.CreateAlloca(Int32, nullptr, "tid.addr");
-  AllocaInst *ZeroAddr = Builder.CreateAlloca(Int32, nullptr, "zero.addr");
+  IRBuilder<> AllocaBuilder(AllocaIP.getBlock(), AllocaIP.getPoint());
+
+  // Use the debug location of the pragma for alloca related code as well.
+  AllocaBuilder.SetCurrentDebugLocation(Loc.DL);
+
+  AllocaInst *TIDAddr = AllocaBuilder.CreateAlloca(Int32, nullptr, "tid.addr");
+  AllocaInst *ZeroAddr =
+      AllocaBuilder.CreateAlloca(Int32, nullptr, "zero.addr");
 
   // If there is an if condition we actually use the TIDAddr and ZeroAddr in the
   // program, otherwise we only need them for modeling purposes to get the
   // associated arguments in the outlined function. In the former case,
   // initialize the allocas properly, in the latter case, delete them later.
   if (IfCondition) {
-    Builder.CreateStore(Constant::getNullValue(Int32), TIDAddr);
-    Builder.CreateStore(Constant::getNullValue(Int32), ZeroAddr);
+    AllocaBuilder.CreateStore(Constant::getNullValue(Int32), TIDAddr);
+    AllocaBuilder.CreateStore(Constant::getNullValue(Int32), ZeroAddr);
   } else {
     ToBeDeleted.push_back(TIDAddr);
     ToBeDeleted.push_back(ZeroAddr);
   }
 
   // Create an artificial insertion point that will also ensure the blocks we
   // are about to split are not degenerated.
   auto *UI = new UnreachableInst(Builder.getContext(), InsertBB);
assert(IP.getBlock()->getTerminator()->getNumSuccessors() == 1 &&
            "Unexpected insertion point for finalization call!");
     return FiniCB(IP);
   };
 
   FinalizationStack.push_back({FiniCBWrapper, OMPD_parallel, IsCancellable});
 
   // Generate the privatization allocas in the block that will become the entry
   // of the outlined function.
-  InsertPointTy AllocaIP(PRegEntryBB,
-                         PRegEntryBB->getTerminator()->getIterator());
-  Builder.restoreIP(AllocaIP);
+  AllocaIP =
+      InsertPointTy(PRegEntryBB, PRegEntryBB->getTerminator()->getIterator());
+  AllocaBuilder.restoreIP(AllocaIP);
   AllocaInst *PrivTIDAddr =
-      Builder.CreateAlloca(Int32, nullptr, "tid.addr.local");
-  Instruction *PrivTID = Builder.CreateLoad(PrivTIDAddr, "tid");
+      AllocaBuilder.CreateAlloca(Int32, nullptr, "tid.addr.local");
+  Instruction *PrivTID = AllocaBuilder.CreateLoad(PrivTIDAddr, "tid");
 
   // Add some fake uses for OpenMP provided arguments.
-  ToBeDeleted.push_back(Builder.CreateLoad(TIDAddr, "tid.addr.use"));
-  ToBeDeleted.push_back(Builder.CreateLoad(ZeroAddr, "zero.addr.use"));
+  ToBeDeleted.push_back(AllocaBuilder.CreateLoad(TIDAddr, "tid.addr.use"));
+  ToBeDeleted.push_back(AllocaBuilder.CreateLoad(ZeroAddr, "zero.addr.use"));
 
   // ThenBB
   //   |
   //   V
   // PRegionEntryBB         <- Privatization allocas are placed here.
   //   |
   //   V
   // PRegionBodyBB          <- BodeGen is invoked here.
auto PrivHelper = [&](Value &V) {
     for (Use *UPtr : Uses)
       UPtr->set(ReplacementValue);
   };
 
   for (Value *Input : Inputs) {
     LLVM_DEBUG(dbgs() << "Captured input: " << *Input << "\n");
     PrivHelper(*Input);
   }
+  LLVM_DEBUG({
+    for (Value *Output : Outputs)
+      LLVM_DEBUG(dbgs() << "Captured output: " << *Output << "\n");
+  });
   assert(Outputs.empty() &&
          "OpenMP outlining should not produce live-out values!");
 
   LLVM_DEBUG(dbgs() << "After  privatization: " << *OuterFn << "\n");
   LLVM_DEBUG({
     for (auto *BB : Blocks)
       dbgs() << " PBR: " << BB->getName() << "\n";
   });

llvm/unittests/Frontend/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/Frontend/OpenMP/OMPConstants.h"
 #include "llvm/IR/Verifier.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "gtest/gtest.h"
 
 using namespace llvm;
 using namespace omp;
 
 namespace {
auto PrivCB = [&](InsertPointTy AllocaIP, InsertPointTy CodeGenIP,
     ReplacementValue = Builder.CreateAlloca(VTy, 0, VPtr.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, BodyGenCB, PrivCB, FiniCB, nullptr,
-                                nullptr, OMP_PROC_BIND_default, false);
+      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();
TEST_F(OpenMPIRBuilderTest, ParallelSimple) {
   EXPECT_EQ(ForkCI->getNumArgOperands(), 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(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 &VPtr, Value *&ReplacementValue) -> InsertPointTy {
+    // Trivial copy (=firstprivate).
+    Builder.restoreIP(AllocaIP);
+    Type *VTy = VPtr.getType()->getPointerElementType();
+    Value *V = Builder.CreateLoad(VTy, &VPtr, VPtr.getName() + ".reload");
+    ReplacementValue = Builder.CreateAlloca(VTy, 0, VPtr.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->getNumArgOperands(), 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 &VPtr, Value *&ReplacementValue) -> InsertPointTy {
+    // Trivial copy (=firstprivate).
+    Builder.restoreIP(AllocaIP);
+    Type *VTy = VPtr.getType()->getPointerElementType();
+    Value *V = Builder.CreateLoad(VTy, &VPtr, VPtr.getName() + ".reload");
+    ReplacementValue = Builder.CreateAlloca(VTy, 0, VPtr.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->getNumArgOperands(), 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});
auto PrivCB = [&](InsertPointTy AllocaIP, InsertPointTy CodeGenIP,
     return CodeGenIP;
   };
 
   auto FiniCB = [&](InsertPointTy CodeGenIP) {
     ++NumFinalizationPoints;
     // No destructors.
   };
 
-  IRBuilder<>::InsertPoint AfterIP = OMPBuilder.CreateParallel(
-      Loc, BodyGenCB, PrivCB, FiniCB, Builder.CreateIsNotNull(F->arg_begin()),
+  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();
TEST_F(OpenMPIRBuilderTest, ParallelCancelBarrier) {
 
   auto FiniCB = [&](InsertPointTy IP) {
     ++NumFinalizationPoints;
     Builder.restoreIP(IP);
     Builder.CreateCall(FakeDestructor,
                        {Builder.getInt32(NumFinalizationPoints)});
   };
 
-  IRBuilder<>::InsertPoint AfterIP = OMPBuilder.CreateParallel(
-      Loc, BodyGenCB, PrivCB, FiniCB, Builder.CreateIsNotNull(F->arg_begin()),
+  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();