[Polly] [BlockGenerator] Unify ScalarMap and PhiOpsMap

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.

llvm-svn: 293374

3 files changed, 50 insertions, 62 deletions

diff --git a/polly/lib/CodeGen/BlockGenerators.cpp b/polly/lib/CodeGen/BlockGenerators.cpp
index 25622378ca7..1bd8df43f1a 100644
--- a/polly/lib/CodeGen/BlockGenerators.cpp
+++ b/polly/lib/CodeGen/BlockGenerators.cpp
@@ -50,12 +50,11 @@ static cl::opt<bool> DebugPrinting(
 
 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,
@@ -214,13 +213,7 @@ BlockGenerator::getImplicitAddress(MemoryAccess &Access, Loop *L,
                                     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 {
@@ -366,53 +359,56 @@ void BlockGenerator::copyBB(ScopStmt &Stmt, BasicBlock *BB, BasicBlock *CopyBB,
     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");
-}
+  Addr = new AllocaInst(Ty, ScalarBase->getName() + NameExt);
+  EntryBB = &Builder.GetInsertBlock()->getParent()->getEntryBlock();
+  Addr->insertBefore(&*EntryBB->getFirstInsertionPt());
 
-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.
@@ -438,7 +434,7 @@ void BlockGenerator::handleOutsideUsers(const Scop &S, Instruction *Inst) {
     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));
@@ -548,7 +544,7 @@ void BlockGenerator::createScalarInitialization(Scop &S) {
 
       Value *ScalarValue = PHI->getIncomingValue(Idx);
 
-      Builder.CreateStore(ScalarValue, getOrCreatePHIAlloca(PHI));
+      Builder.CreateStore(ScalarValue, getOrCreateAlloca(Array));
       continue;
     }
 
@@ -565,8 +561,7 @@ void BlockGenerator::createScalarInitialization(Scop &S) {
       if (!S.hasSingleExitEdge() && PHI->getBasicBlockIndex(ExitBB) >= 0)
         continue;
 
-    Builder.CreateStore(Array->getBasePtr(),
-                        getOrCreateScalarAlloca(Array->getBasePtr()));
+    Builder.CreateStore(Array->getBasePtr(), getOrCreateAlloca(Array));
   }
 }
 
@@ -636,7 +631,7 @@ void BlockGenerator::findOutsideUsers(Scop &S) {
     if (!S.contains(Inst))
       continue;
 
-    handleOutsideUsers(S, Inst);
+    handleOutsideUsers(S, Array);
   }
 }
 
@@ -671,7 +666,7 @@ void BlockGenerator::createExitPHINodeMerges(Scop &S) {
       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);
diff --git a/polly/lib/CodeGen/IslNodeBuilder.cpp b/polly/lib/CodeGen/IslNodeBuilder.cpp
index f970f544dc2..dedf5574e2c 100644
--- a/polly/lib/CodeGen/IslNodeBuilder.cpp
+++ b/polly/lib/CodeGen/IslNodeBuilder.cpp
@@ -1220,12 +1220,8 @@ bool IslNodeBuilder::preloadInvariantEquivClass(
       }
 
       // 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;
     }
   }
 
diff --git a/polly/lib/CodeGen/PPCGCodeGeneration.cpp b/polly/lib/CodeGen/PPCGCodeGeneration.cpp
index 456382c2be6..462b825dfb3 100644
--- a/polly/lib/CodeGen/PPCGCodeGeneration.cpp
+++ b/polly/lib/CodeGen/PPCGCodeGeneration.cpp
@@ -1206,10 +1206,8 @@ void GPUNodeBuilder::createKernel(__isl_take isl_ast_node *KernelStmt) {
   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;
 
@@ -1240,7 +1238,6 @@ void GPUNodeBuilder::createKernel(__isl_take isl_ast_node *KernelStmt) {
 
   ValueMap = std::move(HostValueMap);
   ScalarMap = std::move(HostScalarMap);
-  PHIOpMap = std::move(HostPHIOpMap);
   EscapeMap.clear();
   IDToSAI.clear();
   Annotator.resetAlternativeAliasBases();