[Polly] [BlockGenerator] Unify ScalarMap and PhiOpsMap

[grosser]

Summary

Instead of keeping two separate maps from Value to Allocas, one for
MemoryType::Value and the other for MemoryType::PHI, we introduce a single map
from ScopArrayInfo to the corresponding Alloca. This change is intended, both as
a general simplification and cleanup, but also to reduce our use of
MemoryAccess::getBaseAddr(). Moving away from using getBaseAddr() makes sure
we have only a single place where the array (and its base pointer) for which we
generate code for is specified, which means we can more easily introduce new
access functions that use a different ScopArrayInfo as base. We already today
experiment with modifiable access functions, so this change does not address
a specific bug, but it just reduces the scope one needs to reason about.

Another motivation for this patch is https://reviews.llvm.org/D28518, where
memory accesses with different base pointers could possibly be mapped to a
single ScopArrayInfo object. Such a mapping is currently not possible, as we
currently generate alloca instructions according to the base addresses of the
memory accesses, not according to the ScopArrayInfo object they belong to. By
making allocas ScopArrayInfo specific, a mapping to a single ScopArrayInfo
object will automatically mean that the same stack slot is used for these
arrays. For D28518 this is not a problem, as only MemoryType::Array objects are
mapping, but resolving this inconsistency will hopefully avoid confusion.

[Meinersbur]

I find it confusing that it is a ScalarMap, but its type is ArrayToAllocaMapTy. Our previous terminology was that a SAI (although it has Array in its name) is either a scalar or an array, according to MemoryKind. Proposal: SAIToAllocaMapTy (SaiAllocaMapTy?) or just AllocaMapTy.

I like the simplification of what was previously handled by different code paths.

include/polly/CodeGen/BlockGenerators.h

71–72

The name is ScalarMap, but it maps Arrays?

169–170

Suggestion:
For any llvm::Value, up to two different ScopArrayInfo objects are associated with it

Although this applies only to llvm::PHINode subtypes

179

And MemoryType::ExitPHI

lib/CodeGen/BlockGenerators.cpp

400

Proposal (to reduce indention avoid double lookup):

auto &Addr = ScalarMap[Array];
if (Addr)
  return Addr;

...

404–408

Remove braces?

Depends on out coding style, I am personally OK with braces here. We can also use the ternary operator or a table lookup here:

auto NameExt  = Table[Array->isPHIKind()];

407–408

I see this is what the old getOrCreateAlloca did as well. When I disable it, OpenMP\single_loop_with_param.ll fails. Presumbly this is used to use a thread parameter instead of a local scope variable.

Ideally, if we are not using the alloca anyway, we should not have created one. Possibly resolution by putting the ScopArrayInfo of this address to be replaced into ScalarMap instead into ScalarMap. GlobalMap should only contain "original llvm::Value -> generated llvm::Value", never "generated llvm::Value -> newer generated llvm::Value" which could cause transitivity issues (having to look up GlobalMap until no more replacement found)

410–413

You can use S.getScopArrayInfo to get the SAI; this imposed fewer requirements on the caller of this function.

[grosser]

Address Michael's comments

[grosser]

Hi Michael,

all comments except the one that suggested a restructuring of how we handle OpenMP code. While your comments are well taken, I think these should be addressed in a separate cleanup patch, when time permits.

lib/CodeGen/BlockGenerators.cpp

400

I took this code snippet.

404–408

I dropped braces.

407–408

We may indeed use the outer alloca for a while, but will temporarily switch to an internal alloca while being in the OpenMP body. The OpenMP code should take care of copying values appropriately. Also, we do not have more than two levels of nesting, only normal + OpenMP. So, I do not think this is a bug here.

This could potentially be improved, but I believe such an improvement should be discussed separately. It will also require a more complete code review which I won't manage to do within the next week. I suggest to leave it as is for now.

410–413

Instead of dropping Array, I dropped Inst. This seems more clear in the calling context.

[Meinersbur]

lib/CodeGen/BlockGenerators.cpp

216

Is this dead code now?

374–375

This still looks strange; maybe add a comment what the lookup does? Could we do the GlobalMap lookup when Addr is inserted into ScalarMap (do lookup once instead of each time getOrCreateAlloca is called)?

402–405

Instead of introducing NewAddr you could write directly write to Addr since it's a reference to the already created entry.

411

Ok, I didn't think of doing it this way around.

[Meinersbur]

Just noted that you added comments while I was reviewing the updated diff.

[grosser]

Address Michael's comments. Most importantly, add a large comment documenting
the somehow surprising use of GlobalMap.

Michael, can you have a final look if this comment is understandable?

[grosser]

This was (accidentally) already committed in r293374. I am still a little sleepy this morning and pushed ENTER at the wrong command line. As it was already complete from my side, I won't revert it, but please feel free to point out anything that I might have forgotten.

[Meinersbur]

include/polly/CodeGen/BlockGenerators.h

351

ScopArrayInfo

lib/CodeGen/BlockGenerators.cpp

387–388

Grammar: "at call to getOrCreateAlloca"?

The sentence is rather long, I had difficulty parsing it.

Thanks for the explanation.

402–405

What I meant was

Addr = new AllocaInst(Ty, ScalarBase->getName() + NameExt);
EntryBB = &Builder.GetInsertBlock()->getParent()->getEntryBlock();
Addr->insertBefore(&*EntryBB->getFirstInsertionPt());

[grosser]

Thank you. I added these changes in r293378.

include/polly/CodeGen/BlockGenerators.h

 /// Generate a new basic block for a polyhedral statement.
 class BlockGenerator {
 public:
   typedef llvm::SmallVector<ValueMapT, 8> VectorValueMapT;
 
   /// Map types to resolve scalar dependences.
   ///
   ///@{
-
-  /// @see The ScalarMap and PHIOpMap member.
-  using ScalarAllocaMapTy = DenseMap<AssertingVH<Value>, AssertingVH<Value>>;
+  using AllocaMapTy = DenseMap<const ScopArrayInfo *, AssertingVH<Value>>;
 
   /// Simple vector of instructions to store escape users.
   using EscapeUserVectorTy = SmallVector<Instruction *, 4>;
 
   /// Map type to resolve escaping users for scalar instructions.
   ///
   /// @see The EscapeMap member.
   using EscapeUsersAllocaMapTy =
       MapVector<Instruction *,
                 std::pair<AssertingVH<Value>, EscapeUserVectorTy>>;
 
   ///@}
 
   /// Create a generator for basic blocks.
   ///
   /// @param Builder     The LLVM-IR Builder used to generate the statement. The
   ///                    code is generated at the location, the Builder points
   ///                    to.
   /// @param LI          The loop info for the current function
   /// @param SE          The scalar evolution info for the current function
   /// @param DT          The dominator tree of this function.
   /// @param ScalarMap   Map from scalars to their demoted location.
-  /// @param PHIOpMap    Map from PHIs to their demoted operand location.
   /// @param EscapeMap   Map from scalars to their escape users and locations.
   /// @param GlobalMap   A mapping from llvm::Values used in the original scop
   ///                    region to a new set of llvm::Values. Each reference to
   ///                    an original value appearing in this mapping is replaced
   ///                    with the new value it is mapped to.
   /// @param ExprBuilder An expression builder to generate new access functions.
   /// @param StartBlock  The first basic block after the RTC.
   BlockGenerator(PollyIRBuilder &Builder, LoopInfo &LI, ScalarEvolution &SE,
-                 DominatorTree &DT, ScalarAllocaMapTy &ScalarMap,
-                 ScalarAllocaMapTy &PHIOpMap, EscapeUsersAllocaMapTy &EscapeMap,
-                 ValueMapT &GlobalMap, IslExprBuilder *ExprBuilder,
-                 BasicBlock *StartBlock);
+                 DominatorTree &DT, AllocaMapTy &ScalarMap,
+                 EscapeUsersAllocaMapTy &EscapeMap, ValueMapT &GlobalMap,
+                 IslExprBuilder *ExprBuilder, BasicBlock *StartBlock);
 
   /// Copy the basic block.
   ///
   /// This copies the entire basic block and updates references to old values
   /// with references to new values, as defined by GlobalMap.
   ///
   /// @param Stmt        The block statement to code generate.
   /// @param LTS         A map from old loops to new induction variables as
   ///                    SCEVs.
   /// @param NewAccesses A map from memory access ids to new ast expressions,
   ///                    which may contain new access expressions for certain
   ///                    memory accesses.
   void copyStmt(ScopStmt &Stmt, LoopToScevMapT &LTS,
                 isl_id_to_ast_expr *NewAccesses);
 
-  /// Return the scalar alloca for @p ScalarBase.
-  ///
-  /// If no alloca was mapped to @p ScalarBase a new one is created.
-  ///
-  /// @param ScalarBase The demoted scalar value.
-  /// @param GlobalMap  A mapping from Allocas to other memory locations that
-  ///                   can be used to replace the original alloca locations
-  ///                   with new memory locations, e.g. when passing values to
-  ///                   subfunctions while offloading parallel sections.
-  ///
-  /// @returns The alloca for @p ScalarBase or a replacement value taken from
-  ///          GlobalMap.
-  Value *getOrCreateScalarAlloca(Value *ScalarBase);
-
-  /// Remove a Value's allocation from the ScalarMap.
+  /// Remove a ScopArrayInfo's allocation from the ScalarMap.
   ///
   /// This function allows to remove values from the ScalarMap. This is useful
   /// if the corresponding alloca instruction will be deleted (or moved into
   /// another module), as without removing these values the underlying
   /// AssertingVH will trigger due to us still keeping reference to this
   /// scalar.
   ///
-  /// @param ScalarBase The value to remove.
-  void freeScalarAlloc(Value *ScalarBase) { ScalarMap.erase(ScalarBase); }
-
-  /// Return the PHi-node alloca for @p ScalarBase.
-  ///
-  /// If no alloca was mapped to @p ScalarBase a new one is created.
-  ///
-  /// @param ScalarBase The demoted scalar value.
-  ///
-  /// @returns The alloca for @p ScalarBase or a replacement value taken from
-  ///          GlobalMap.
-  Value *getOrCreatePHIAlloca(Value *ScalarBase);
+  /// @param Array The array for which the alloca was generated.
+  void freeScalarAlloc(ScopArrayInfo *Array) { ScalarMap.erase(Array); }
 
   /// Return the alloca for @p Access.
   ///
   /// If no alloca was mapped for @p Access a new one is created.
   ///
   /// @param Access    The memory access for which to generate the alloca.
   ///
   /// @returns The alloca for @p Access or a replacement value taken from
protected:
   IslExprBuilder *ExprBuilder;
 
   /// The dominator tree of this function.
   DominatorTree &DT;
 
   /// The entry block of the current function.
   BasicBlock *EntryBB;
 
-  /// Maps to resolve scalar dependences for PHI operands and scalars.
+  /// Map to resolve scalar dependences for PHI operands and scalars.
   ///
   /// When translating code that contains scalar dependences as they result from
-  /// inter-block scalar dependences (including the use of data carrying
-  /// PHI nodes), we do not directly regenerate in-register SSA code, but
-  /// instead allocate some stack memory through which these scalar values are
-  /// passed. Only a later pass of -mem2reg will then (re)introduce in-register
+  /// inter-block scalar dependences (including the use of data carrying PHI
+  /// nodes), we do not directly regenerate in-register SSA code, but instead
+  /// allocate some stack memory through which these scalar values are passed.
+  /// Only a later pass of -mem2reg will then (re)introduce in-register
   /// computations.
   ///
   /// To keep track of the memory location(s) used to store the data computed by
-  /// a given SSA instruction, we use the maps 'ScalarMap' and 'PHIOpMap'. Each
-  /// maps a given scalar value to a junk of stack allocated memory.
-  ///
-  /// 'ScalarMap' is used for normal scalar dependences that go from a scalar
-  /// definition to its use. Such dependences are lowered by directly writing
-  /// the value an instruction computes into the corresponding chunk of memory
-  /// and reading it back from this chunk of memory right before every use of
-  /// this original scalar value. The memory locations in 'ScalarMap' end with
-  /// '.s2a'.
-  ///
-  /// 'PHIOpMap' is used to model PHI nodes. For each PHI nodes we introduce,
-  /// besides the memory in 'ScalarMap', a second chunk of memory into which we
-  /// write at the end of each basic block preceeding the PHI instruction the
-  /// value passed through this basic block. At the place where the PHI node is
-  /// executed, we replace the PHI node with a load from the corresponding
-  /// memory location in the 'PHIOpMap' table. The memory locations in
-  /// 'PHIOpMap' end with '.phiops'.
-  ///
-  /// The ScopArrayInfo objects of accesses that belong to a PHI node may have
-  /// identical base pointers, even though they refer to two different memory
-  /// locations, the normal '.s2a' locations and the special '.phiops'
-  /// locations. For historic reasons we keep such accesses in two maps
-  /// 'ScalarMap' and 'PHIOpMap', index by the BasePointer. An alternative
-  /// implemenation, could use a single map that uses the ScopArrayInfo object
-  /// as index.
+  /// a given SSA instruction, we use the map 'ScalarMap'. ScalarMap maps a
+  /// given ScopArrayInfo to the junk of stack allocated memory, that is
+  /// used for code generation.
+  ///
+  /// Up to two different ScopArrayInfo objects are associated with each
+  /// llvm::Value:
+  ///
+  /// MemoryType::Value objects are used for normal scalar dependences that go
+  /// from a scalar definition to its use. Such dependences are lowered by
+  /// directly writing the value an instruction computes into the corresponding
+  /// chunk of memory and reading it back from this chunk of memory right before
+  /// every use of this original scalar value. The memory allocations for
+  /// MemoryType::Value objects end with '.s2a'.
+  ///
+  /// MemoryType::PHI (and MemoryType::ExitPHI) objects are used to model PHI
+  /// nodes. For each PHI nodes we introduce, besides the Array of type
+  /// MemoryType::Value, a second chunk of memory into which we write at the end
+  /// of each basic block preceeding the PHI instruction the value passed
+  /// through this basic block. At the place where the PHI node is executed, we
+  /// replace the PHI node with a load from the corresponding MemoryType::PHI
+  /// memory location. The memory allocations for MemoryType::PHI end with
+  /// '.phiops'.
   ///
   /// Example:
   ///
   ///                              Input C Code
   ///                              ============
   ///
   ///                 S1:      x1 = ...
   ///                          for (i=0...N) {
protected:
   ///
   ///                                    S4:    x1 = x1.s2a
   /// S4:  ... = x1                             ... = x1
   ///                                           x2 = x2.s2a
   ///      ... = x2                             ... = x2
   ///                                           add = add.s2a
   ///      ... = add                            ... = add
   ///
-  ///      ScalarMap = { x1 -> x1.s2a, x2 -> x2.s2a, add -> add.s2a }
-  ///      PHIOpMap =  { x2 -> x2.phiops }
-  ///
+  ///      ScalarMap = { x1:Value -> x1.s2a, x2:Value -> x2.s2a,
+  ///                    add:Value -> add.s2a, x2:PHI -> x2.phiops }
   ///
   ///  ??? Why does a PHI-node require two memory chunks ???
   ///
   ///  One may wonder why a PHI node requires two memory chunks and not just
   ///  all data is stored in a single location. The following example tries
   ///  to store all data in .s2a and drops the .phiops location:
   ///
   ///      S1:    x1 = ...
protected:
   ///             add = add.s2a
   ///             ... = add
   ///
   ///  As visible in the example, the SSA value of the PHI node may still be
   ///  needed _after_ the basic block, which could conceptually branch to the
   ///  PHI node, has been run and has overwritten the PHI's old value. Hence, a
   ///  single memory location is not enough to code-generate a PHI node.
   ///
-  ///{
-  ///
   /// Memory locations used for the special PHI node modeling.
-  ScalarAllocaMapTy &PHIOpMap;
-
-  /// Memory locations used to model scalar dependences.
-  ScalarAllocaMapTy &ScalarMap;
-  ///}
+  AllocaMapTy &ScalarMap;
 
   /// Map from instructions to their escape users as well as the alloca.
   EscapeUsersAllocaMapTy &EscapeMap;
 
   /// A map from llvm::Values referenced in the old code to a new set of
   ///        llvm::Values, which is used to replace these old values during
   ///        code generation.
   ValueMapT &GlobalMap;
protected:
   ///                    SCEVs.
   /// @param NewAccesses A map from memory access ids to new ast expressions,
   ///                    which may contain new access expressions for certain
   ///                    memory accesses.
   void copyBB(ScopStmt &Stmt, BasicBlock *BB, BasicBlock *BBCopy,
               ValueMapT &BBMap, LoopToScevMapT &LTS,
               isl_id_to_ast_expr *NewAccesses);
 
-  /// Return the alloca for @p ScalarBase in @p Map.
-  ///
-  /// If no alloca was mapped to @p ScalarBase in @p Map a new one is created
-  /// and named after @p ScalarBase with the suffix @p NameExt.
-  ///
-  /// @param ScalarBase The demoted scalar value.
-  /// @param Map        The map we should look for a mapped alloca value.
-  /// @param NameExt    The suffix we add to the name of a new created alloca.
-  ///
-  /// @returns The alloca for @p ScalarBase.
-  Value *getOrCreateAlloca(Value *ScalarBase, ScalarAllocaMapTy &Map,
-                           const char *NameExt);
-
   /// Generate reload of scalars demoted to memory and needed by @p Stmt.
   ///
   /// @param Stmt  The statement we generate code for.
   /// @param LTS   A mapping from loops virtual canonical induction
   ///              variable to their new values.
   /// @param BBMap A mapping from old values to their new values in this block.
   /// @param NewAccesses A map from memory access ids to new ast expressions.
   void generateScalarLoads(ScopStmt &Stmt, LoopToScevMapT &LTS,
protected:
   ///              (for values recalculated in the new ScoP, but not
   ///               within this basic block)
   /// @param BBMap A mapping from old values to their new values in this block.
   /// @param NewAccesses A map from memory access ids to new ast expressions.
   virtual void generateScalarStores(ScopStmt &Stmt, LoopToScevMapT &LTS,
                                     ValueMapT &BBMap,
                                     __isl_keep isl_id_to_ast_expr *NewAccesses);
 
-  /// Handle users of @p Inst outside the SCoP.
+  /// Handle users of @p Array outside the SCoP.
   ///
   /// @param S         The current SCoP.
-  /// @param Inst      The current instruction we check.
-  void handleOutsideUsers(const Scop &S, Instruction *Inst);
+  /// @param Inst      The ScopArray to handle.
+  void handleOutsideUsers(const Scop &S, ScopArrayInfo *Array);
 
   /// Find scalar statements that have outside users.
   ///
   /// We register these scalar values to later update subsequent scalar uses of
   /// these values to either use the newly computed value from within the scop
   /// (if the scop was executed) or the unchanged original code (if the run-time
   /// check failed).
   ///

include/polly/CodeGen/IslNodeBuilder.h

 class IslNodeBuilder {
 public:
   IslNodeBuilder(PollyIRBuilder &Builder, ScopAnnotator &Annotator, Pass *P,
                  const DataLayout &DL, LoopInfo &LI, ScalarEvolution &SE,
                  DominatorTree &DT, Scop &S, BasicBlock *StartBlock)
       : S(S), Builder(Builder), Annotator(Annotator),
         ExprBuilder(S, Builder, IDToValue, ValueMap, DL, SE, DT, LI,
                     StartBlock),
-        BlockGen(Builder, LI, SE, DT, ScalarMap, PHIOpMap, EscapeMap, ValueMap,
+        BlockGen(Builder, LI, SE, DT, ScalarMap, EscapeMap, ValueMap,
                  &ExprBuilder, StartBlock),
         RegionGen(BlockGen), P(P), DL(DL), LI(LI), SE(SE), DT(DT),
         StartBlock(StartBlock) {}
 
   virtual ~IslNodeBuilder() = default;
 
   void addParameters(__isl_take isl_set *Context);
 
protected:
 
   IslExprBuilder ExprBuilder;
 
   /// Maps used by the block and region generator to demote scalars.
   ///
   ///@{
 
   /// See BlockGenerator::ScalarMap.
-  BlockGenerator::ScalarAllocaMapTy ScalarMap;
-
-  /// See BlockGenerator::PhiOpMap.
-  BlockGenerator::ScalarAllocaMapTy PHIOpMap;
+  BlockGenerator::AllocaMapTy ScalarMap;
 
   /// See BlockGenerator::EscapeMap.
   BlockGenerator::EscapeUsersAllocaMapTy EscapeMap;
 
   ///@}
 
   /// The generator used to copy a basic block.
   BlockGenerator BlockGen;

lib/CodeGen/BlockGenerators.cpp

 
 static cl::opt<bool> DebugPrinting(
     "polly-codegen-add-debug-printing",
     cl::desc("Add printf calls that show the values loaded/stored."),
     cl::Hidden, cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
 
 BlockGenerator::BlockGenerator(
     PollyIRBuilder &B, LoopInfo &LI, ScalarEvolution &SE, DominatorTree &DT,
-    ScalarAllocaMapTy &ScalarMap, ScalarAllocaMapTy &PHIOpMap,
-    EscapeUsersAllocaMapTy &EscapeMap, ValueMapT &GlobalMap,
-    IslExprBuilder *ExprBuilder, BasicBlock *StartBlock)
+    AllocaMapTy &ScalarMap, EscapeUsersAllocaMapTy &EscapeMap,
+    ValueMapT &GlobalMap, IslExprBuilder *ExprBuilder, BasicBlock *StartBlock)
     : Builder(B), LI(LI), SE(SE), ExprBuilder(ExprBuilder), DT(DT),
-      EntryBB(nullptr), PHIOpMap(PHIOpMap), ScalarMap(ScalarMap),
-      EscapeMap(EscapeMap), GlobalMap(GlobalMap), StartBlock(StartBlock) {}
+      EntryBB(nullptr), ScalarMap(ScalarMap), EscapeMap(EscapeMap),
+      GlobalMap(GlobalMap), StartBlock(StartBlock) {}
 
 Value *BlockGenerator::trySynthesizeNewValue(ScopStmt &Stmt, Value *Old,
                                              ValueMapT &BBMap,
                                              LoopToScevMapT &LTS,
                                              Loop *L) const {
   if (!SE.isSCEVable(Old->getType()))
     return nullptr;
 

 BlockGenerator::getImplicitAddress(MemoryAccess &Access, Loop *L,
                                    LoopToScevMapT &LTS, ValueMapT &BBMap,
                                    __isl_keep isl_id_to_ast_expr *NewAccesses) {
   if (Access.isLatestArrayKind())
     return generateLocationAccessed(*Access.getStatement(), L, nullptr, BBMap,
                                     LTS, NewAccesses, Access.getId(),
                                     Access.getAccessValue()->getType());
 
-  if (Access.isLatestValueKind() || Access.isLatestExitPHIKind())
-    return getOrCreateScalarAlloca(Access.getBaseAddr());
-
-  if (Access.isLatestPHIKind())
-    return getOrCreatePHIAlloca(Access.getBaseAddr());
-
-  llvm_unreachable("Unknown access type");
+  return getOrCreateAlloca(Access);
 }
 
 Loop *BlockGenerator::getLoopForStmt(const ScopStmt &Stmt) const {
   auto *StmtBB = Stmt.getEntryBlock();
   return LI.getLoopFor(StmtBB);
 }
 
 Value *BlockGenerator::generateArrayLoad(ScopStmt &Stmt, LoadInst *Load,
void BlockGenerator::copyBB(ScopStmt &Stmt, BasicBlock *BB, BasicBlock *CopyBB,
                             ValueMapT &BBMap, LoopToScevMapT &LTS,
                             isl_id_to_ast_expr *NewAccesses) {
   EntryBB = &CopyBB->getParent()->getEntryBlock();
 
   for (Instruction &Inst : *BB)
     copyInstruction(Stmt, &Inst, BBMap, LTS, NewAccesses);
 }
 
-Value *BlockGenerator::getOrCreateAlloca(Value *ScalarBase,
-                                         ScalarAllocaMapTy &Map,
-                                         const char *NameExt) {
-  // If no alloca was found create one and insert it in the entry block.
-  if (!Map.count(ScalarBase)) {
-    auto *Ty = ScalarBase->getType();
-    auto NewAddr = new AllocaInst(Ty, ScalarBase->getName() + NameExt);
-    EntryBB = &Builder.GetInsertBlock()->getParent()->getEntryBlock();
-    NewAddr->insertBefore(&*EntryBB->getFirstInsertionPt());
-    Map[ScalarBase] = NewAddr;
-  }
-
-  auto Addr = Map[ScalarBase];
-
-  if (auto NewAddr = GlobalMap.lookup(Addr))
-    return NewAddr;
-
-  return Addr;
-}
-
 Value *BlockGenerator::getOrCreateAlloca(const MemoryAccess &Access) {
-  assert(!Access.isArrayKind() && "Trying to get alloca for array kind");
+  assert(!Access.isLatestArrayKind() && "Trying to get alloca for array kind");
 
-  if (Access.isPHIKind())
-    return getOrCreatePHIAlloca(Access.getBaseAddr());
-  else
-    return getOrCreateScalarAlloca(Access.getBaseAddr());
+  return getOrCreateAlloca(Access.getLatestScopArrayInfo());
 }
 
 Value *BlockGenerator::getOrCreateAlloca(const ScopArrayInfo *Array) {
   assert(!Array->isArrayKind() && "Trying to get alloca for array kind");
 
+  auto &Addr = ScalarMap[Array];
+
+  if (Addr) {
+    // Allow allocas to be (temporarily) redirected once by adding a new
+    // old-alloca-addr to new-addr mapping to GlobalMap. This funcitionality
+    // is used for example by the OpenMP code generation where a first use
+    // of a scalar while still in the host code allocates a normal alloca with
+    // getOrCreateAlloca. When the values of this scalar are accessed during
+    // the generation of the parallel subfunction, these values are copied over
+    // to the parallel subfunction and each request for a scalar alloca slot
+    // must be forwared to the temporary in-subfunction slot. This mapping is
+    // removed when the subfunction has been generated and again normal host
+    // code is generated. As GlobalMap may be changed multiple times (for
+    // each parallel loop), is commonly only known after the initial alloca
+    // has been generated, and the original alloca value must be restored at
+    // the end, it is not possible to perform the GlobalMap lookup right after
+    // creating the alloca below, but instead we need to check GlobalMap at
+    // call to getOrCreateAlloca.
+    if (Value *NewAddr = GlobalMap.lookup(Addr))
+      return NewAddr;
+    return Addr;
+  }
+
+  Type *Ty = Array->getElementType();
+  Value *ScalarBase = Array->getBasePtr();
+  std::string NameExt;
   if (Array->isPHIKind())
-    return getOrCreatePHIAlloca(Array->getBasePtr());
+    NameExt = ".phiops";
   else
-    return getOrCreateScalarAlloca(Array->getBasePtr());
-}
+    NameExt = ".s2a";
 
-Value *BlockGenerator::getOrCreateScalarAlloca(Value *ScalarBase) {
-  return getOrCreateAlloca(ScalarBase, ScalarMap, ".s2a");
-}
+  auto *NewAddr = new AllocaInst(Ty, ScalarBase->getName() + NameExt);
+  EntryBB = &Builder.GetInsertBlock()->getParent()->getEntryBlock();
+  NewAddr->insertBefore(&*EntryBB->getFirstInsertionPt());
+  Addr = NewAddr;
 
-Value *BlockGenerator::getOrCreatePHIAlloca(Value *ScalarBase) {
-  return getOrCreateAlloca(ScalarBase, PHIOpMap, ".phiops");
+  return Addr;
 }
 
-void BlockGenerator::handleOutsideUsers(const Scop &S, Instruction *Inst) {
+void BlockGenerator::handleOutsideUsers(const Scop &S, ScopArrayInfo *Array) {
+  Instruction *Inst = cast<Instruction>(Array->getBasePtr());
+
   // If there are escape users we get the alloca for this instruction and put it
   // in the EscapeMap for later finalization. Lastly, if the instruction was
   // copied multiple times we already did this and can exit.
   if (EscapeMap.count(Inst))
     return;
 
   EscapeUserVectorTy EscapeUsers;
   for (User *U : Inst->users()) {
 
     // Non-instruction user will never escape.
     Instruction *UI = dyn_cast<Instruction>(U);
     if (!UI)
       continue;
 
     if (S.contains(UI))
       continue;
 
     EscapeUsers.push_back(UI);
   }
 
   // Exit if no escape uses were found.
   if (EscapeUsers.empty())
     return;
 
   // Get or create an escape alloca for this instruction.
-  auto *ScalarAddr = getOrCreateScalarAlloca(Inst);
+  auto *ScalarAddr = getOrCreateAlloca(Array);
 
   // Remember that this instruction has escape uses and the escape alloca.
   EscapeMap[Inst] = std::make_pair(ScalarAddr, std::move(EscapeUsers));
 }
 
 void BlockGenerator::generateScalarLoads(
     ScopStmt &Stmt, LoopToScevMapT &LTS, ValueMapT &BBMap,
     __isl_keep isl_id_to_ast_expr *NewAccesses) {
if (Array->isPHIKind()) {
                            "come from PreEntryBB");
 
       int Idx = PHI->getBasicBlockIndex(PreEntryBB);
       if (Idx < 0)
         continue;
 
       Value *ScalarValue = PHI->getIncomingValue(Idx);
 
-      Builder.CreateStore(ScalarValue, getOrCreatePHIAlloca(PHI));
+      Builder.CreateStore(ScalarValue, getOrCreateAlloca(Array));
       continue;
     }
 
     auto *Inst = dyn_cast<Instruction>(Array->getBasePtr());
 
     if (Inst && S.contains(Inst))
       continue;
 
     // PHI nodes that are not marked as such in their SAI object are either exit
     // PHI nodes we model as common scalars but without initialization, or
     // incoming phi nodes that need to be initialized. Check if the first is the
     // case for Inst and do not create and initialize memory if so.
     if (auto *PHI = dyn_cast_or_null<PHINode>(Inst))
       if (!S.hasSingleExitEdge() && PHI->getBasicBlockIndex(ExitBB) >= 0)
         continue;
 
-    Builder.CreateStore(Array->getBasePtr(),
-                        getOrCreateScalarAlloca(Array->getBasePtr()));
+    Builder.CreateStore(Array->getBasePtr(), getOrCreateAlloca(Array));
   }
 }
 
 void BlockGenerator::createScalarFinalization(Scop &S) {
   // The exit block of the __unoptimized__ region.
   BasicBlock *ExitBB = S.getExitingBlock();
   // The merge block __just after__ the region and the optimized region.
   BasicBlock *MergeBB = S.getExit();
if (!Inst)
       continue;
 
     // Scop invariant hoisting moves some of the base pointers out of the scop.
     // We can ignore these, as the invariant load hoisting already registers the
     // relevant outside users.
     if (!S.contains(Inst))
       continue;
 
-    handleOutsideUsers(S, Inst);
+    handleOutsideUsers(S, Array);
   }
 }
 
 void BlockGenerator::createExitPHINodeMerges(Scop &S) {
   if (S.hasSingleExitEdge())
     return;
 
   auto *ExitBB = S.getExitingBlock();
for (auto &SAI : S.arrays()) {
     PHINode *PHI = dyn_cast<PHINode>(Val);
     if (!PHI)
       continue;
 
     if (PHI->getParent() != AfterMergeBB)
       continue;
 
     std::string Name = PHI->getName();
-    Value *ScalarAddr = getOrCreateScalarAlloca(PHI);
+    Value *ScalarAddr = getOrCreateAlloca(SAI);
     Value *Reload = Builder.CreateLoad(ScalarAddr, Name + ".ph.final_reload");
     Reload = Builder.CreateBitOrPointerCast(Reload, PHI->getType());
     Value *OriginalValue = PHI->getIncomingValueForBlock(MergeBB);
     assert((!isa<Instruction>(OriginalValue) ||
             cast<Instruction>(OriginalValue)->getParent() != MergeBB) &&
            "Original value must no be one we just generated.");
     auto *MergePHI = PHINode::Create(PHI->getType(), 2, Name + ".ph.merge");
     MergePHI->insertBefore(&*MergeBB->getFirstInsertionPt());

lib/CodeGen/IslNodeBuilder.cpp

for (const MemoryAccess *MA : MAs) {
       // should only change the base pointer of the derived SAI if we actually
       // preloaded it.
       if (BasePtr == MA->getBaseAddr()) {
         assert(BasePtr->getType() == PreloadVal->getType());
         DerivedSAI->setBasePtr(PreloadVal);
       }
 
       // For scalar derived SAIs we remap the alloca used for the derived value.
-      if (BasePtr == MA->getAccessInstruction()) {
-        if (DerivedSAI->isPHIKind())
-          PHIOpMap[BasePtr] = Alloca;
-        else
-          ScalarMap[BasePtr] = Alloca;
-      }
+      if (BasePtr == MA->getAccessInstruction())
+        ScalarMap[DerivedSAI] = Alloca;
     }
   }
 
   for (const MemoryAccess *MA : MAs) {
 
     Instruction *MAAccInst = MA->getAccessInstruction();
     // Use the escape system to get the correct value to users outside the SCoP.
     BlockGenerator::EscapeUserVectorTy EscapeUsers;

lib/CodeGen/PPCGCodeGeneration.cpp

void GPUNodeBuilder::createKernel(__isl_take isl_ast_node *KernelStmt) {
 
   SetVector<Value *> SubtreeValues = getReferencesInKernel(Kernel);
 
   assert(Kernel->tree && "Device AST of kernel node is empty");
 
   Instruction &HostInsertPoint = *Builder.GetInsertPoint();
   IslExprBuilder::IDToValueTy HostIDs = IDToValue;
   ValueMapT HostValueMap = ValueMap;
-  BlockGenerator::ScalarAllocaMapTy HostScalarMap = ScalarMap;
-  BlockGenerator::ScalarAllocaMapTy HostPHIOpMap = PHIOpMap;
+  BlockGenerator::AllocaMapTy HostScalarMap = ScalarMap;
   ScalarMap.clear();
-  PHIOpMap.clear();
 
   SetVector<const Loop *> Loops;
 
   // Create for all loops we depend on values that contain the current loop
   // iteration. These values are necessary to generate code for SCEVs that
   // depend on such loops. As a result we need to pass them to the subfunction.
   for (const Loop *L : Loops) {
     const SCEV *OuterLIV = SE.getAddRecExpr(SE.getUnknown(Builder.getInt64(0)),
void GPUNodeBuilder::createKernel(__isl_take isl_ast_node *KernelStmt) {
   clearDominators(F);
   clearScalarEvolution(F);
   clearLoops(F);
 
   IDToValue = HostIDs;
 
   ValueMap = std::move(HostValueMap);
   ScalarMap = std::move(HostScalarMap);
-  PHIOpMap = std::move(HostPHIOpMap);
   EscapeMap.clear();
   IDToSAI.clear();
   Annotator.resetAlternativeAliasBases();
   for (auto &BasePtr : LocalArrays)
     S.invalidateScopArrayInfo(BasePtr, MemoryKind::Array);
   LocalArrays.clear();
 
   std::string ASMString = finalizeKernelFunction();