[Polly] Loop versioning after code generation (WIP)

[Meinersbur]

Summary

Loop versioning modifies the scop, especially the PHI nodes in the entry and exit block. Code generation must take this into account and test for multiple cases where the PHIs could have landed which can also depend on the code surrounding the scop. Not considering all cases has been a source of many bugs.

With this patch we generate code before modifying the scop region into a region disconnected from the original code. Only after the code has been created, it is connected as an alternative of the original scop region.

Going further with this idea, we could generate all SCoPs in a function before connecting them in order to not require to verify whether other detected SCoPs are still valid.

[Meinersbur]

Currently failing 71 unit tests (none adapted to possibly required changes). Working on the SCEVs of IslNodeBuilder::OutsideLoopIterations which expand into the original scop region, but are used in the generated one.

[Meinersbur]

This may cause problems with ScalarEvolution which is not propared to generate code in (temporarily) disconnected blocks. Since we are not in control of SE to reliably correct this, we abandon this approach.

[llvm-commits]

To bad, I thought this was a nice solution.

One of the students I advice currently tackles a similar problem when SE
is used to synthesise code in a parallel subfunction... I'll let you
know once we figured that out.

• signature.asc219 BDownload
• msg-27075-277.txt162 BDownload

[Meinersbur]

In D14715#309767, @llvm-commits wrote:

To bad, I thought this was a nice solution.

One of the students I advice currently tackles a similar problem when SE
is used to synthesise code in a parallel subfunction... I'll let you
know once we figured that out.

One of my other suggestions was to generate the code in a separate function which is to be inlined by LLVM afterwards. Unfortunatelt it is forbidden for function passes to touch (or create) functions they were not invoked on.

[llvm-commits]

Polly has to become a SCC pass anyway in order to make parallelization
valid (and allow inter-procedural analysis), thus this should not be a
concern. However, it seems odd and expensive to create a function only
to inline it again, so we might not want to do that.

• signature.asc219 BDownload
• msg-2245-328.txt162 BDownload

include/polly/CodeGen/BlockGenerators.h

public:
 
   /// @brief Finalize the code generation for the SCoP @p S.
   ///
   /// This will initialize and finalize the scalar variables we demoted during
   /// the code generation.
   ///
   /// @see createScalarInitialization(Scop &)
   /// @see createScalarFinalization(Region &)
-  void finalizeSCoP(Scop &S);
+  void finalizeSCoP(Scop &S, Region &GenR);
+
+  /// @brief Promote the values of demoted scalars after the SCoP.
+  ///
+  /// If a scalar value was used outside the SCoP we need to promote the value
+  /// stored in the memory cell allocated for that scalar and combine it with
+  /// the original value in the non-optimized SCoP.
+  void createScalarFinalization(Region &R, Region &GenR,
+                                BasicBlock *EnteringBlock,
+                                BasicBlock *SplitBlock, BasicBlock *MergeBlock);
 
   /// @brief An empty destructor
   virtual ~BlockGenerator(){};
 
   BlockGenerator(const BlockGenerator &) = default;
 
 protected:
   PollyIRBuilder &Builder;
protected:
   /// check failed).
   ///
   /// @param S The scop for which to find the outside users.
   void findOutsideUsers(Scop &S);
 
   /// @brief Initialize the memory of demoted scalars.
   ///
   /// @param S The scop for which to generate the scalar initializers.
-  void createScalarInitialization(Scop &S);
+  // void createScalarInitialization(Scop &S, Region &GenR);
 
   /// @brief Create exit PHI node merges for PHI nodes with more than two edges
   ///        from inside the scop.
   ///
   /// For scops which have a PHI node in the exit block that has more than two
   /// incoming edges from inside the scop region, we require some special
   /// handling to understand which of the possible values will be passed to the
   /// PHI node from inside the optimized version of the scop. To do so ScopInfo
   /// models the possible incoming values as write accesses of the ScopStmts.
   ///
   /// This function creates corresponding code to reload the computed outgoing
   /// value from the stack slot it has been stored into and to pass it on to the
   /// PHI node in the original exit block.
   ///
   /// @param S The scop for which to generate the exiting PHI nodes.
-  void createExitPHINodeMerges(Scop &S);
-
-  /// @brief Promote the values of demoted scalars after the SCoP.
-  ///
-  /// If a scalar value was used outside the SCoP we need to promote the value
-  /// stored in the memory cell allocated for that scalar and combine it with
-  /// the original value in the non-optimized SCoP.
-  void createScalarFinalization(Region &R);
+  // void createExitPHINodeMerges(Scop &S);
 
   /// @brief Try to synthesize a new value
   ///
   /// Given an old value, we try to synthesize it in a new context from its
   /// original SCEV expression. We start from the original SCEV expression,
   /// then replace outdated parameter and loop references, and finally
   /// expand it to code that computes this updated expression.
   ///

include/polly/CodeGen/IRBuilder.h

 
 // TODO: We should not name instructions in NDEBUG builds.
 //
 // We currently always name instructions, as the polly test suite currently
 // matches for certain names.
 typedef PollyBuilderInserter<true> IRInserter;
 typedef llvm::IRBuilder<true, llvm::ConstantFolder, IRInserter> PollyIRBuilder;
 
-/// @brief Return an IR builder pointed before the @p BB terminator.
+/// @brief Return an IR builder.
 static inline PollyIRBuilder createPollyIRBuilder(llvm::BasicBlock *BB,
                                                   ScopAnnotator &LA) {
   PollyIRBuilder Builder(BB->getContext(), llvm::ConstantFolder(),
                          polly::IRInserter(LA));
   Builder.SetInsertPoint(BB->getTerminator());
   return Builder;
 }
 }
 #endif

include/polly/CodeGen/IslNodeBuilder.h

 struct isl_ast_node;
 struct isl_ast_build;
 struct isl_union_map;
 
 class IslNodeBuilder {
 public:
   IslNodeBuilder(PollyIRBuilder &Builder, ScopAnnotator &Annotator, Pass *P,
                  const DataLayout &DL, LoopInfo &LI, ScalarEvolution &SE,
-                 DominatorTree &DT, Scop &S)
+                 DominatorTree &DT, Scop &S, Region &GenR)
       : S(S), Builder(Builder), Annotator(Annotator),
         ExprBuilder(S, Builder, IDToValue, ValueMap, DL, SE, DT, LI),
         BlockGen(Builder, LI, SE, DT, ScalarMap, PHIOpMap, EscapeMap, ValueMap,
                  &ExprBuilder),
-        RegionGen(BlockGen), P(P), DL(DL), LI(LI), SE(SE), DT(DT) {}
+        RegionGen(BlockGen), P(P), DL(DL), LI(LI), SE(SE), DT(DT), GenR(GenR) {}
 
   virtual ~IslNodeBuilder() {}
 
   void addParameters(__isl_take isl_set *Context);
   void create(__isl_take isl_ast_node *Node);
 
   /// @brief Preload all memory loads that are invariant.
   bool preloadInvariantLoads();
 
   /// @brief Finalize code generation for the SCoP @p S.
   ///
   /// @see BlockGenerator::finalizeSCoP(Scop &S)
-  void finalizeSCoP(Scop &S) { BlockGen.finalizeSCoP(S); }
+  void finalizeSCoP(Region &GenR) { BlockGen.finalizeSCoP(S, GenR); }
+
+  void mergeSCoP(BasicBlock *EnteringBlock, BasicBlock *SplitBlock,
+                 BasicBlock *MergeBlock) {
+    BlockGen.createScalarFinalization(S.getRegion(), GenR, EnteringBlock,
+                                      SplitBlock, MergeBlock);
+  }
 
   IslExprBuilder &getExprBuilder() { return ExprBuilder; }
 
   /// @brief Get the associated block generator.
   ///
   /// @return A referecne to the associated block generator.
   BlockGenerator &getBlockGenerator() { return BlockGen; }
 
 protected:
   Scop &S;
   PollyIRBuilder &Builder;
   ScopAnnotator &Annotator;
 
   IslExprBuilder ExprBuilder;
 
+  Region &GenR;
+
   /// @brief Maps used by the block and region generator to demote scalars.
   ///
   ///@{
 
   /// @brief See BlockGenerator::ScalarMap.
   BlockGenerator::ScalarAllocaMapTy ScalarMap;
 
   /// @brief See BlockGenerator::PhiOpMap.

include/polly/ScopInfo.h

public:
   /// @brief The type of a memory access.
   enum ARRAYKIND {
     // Scalar references to SSA values.
     KIND_SCALAR,
 
     // Scalar references used to model PHI nodes
     KIND_PHI,
 
+    // Like KIND_PHI, but for PHIs in the exit node. Depending on context, these
+    // are handled like KIND_SCALAR.
+    KIND_EXIT_PHI,
+
     // References to (multi-dimensional) arrays
     KIND_ARRAY,
   };
 
   /// @brief Construct a ScopArrayInfo object.
   ///
   /// @param BasePtr        The array base pointer.
   /// @param ElementType    The type of the elements stored in the array.
public:
   /// ------------------------------------  ------------------------------------
   ///
   /// #AccessInst is either the llvm::Value for WRITEs or the value's user for
   /// READS. The #BaseAddr is represented by the value's definition (i.e. the
   /// llvm::Value itself) as no such alloca yet exists before CodeGeneration.
   /// #AccessValue is also the llvm::Value itself.
   ///
   ///
-  /// * Accesses to emulate PHI nodes
+  /// * Accesses to emulate PHI nodes within the SCoP
   ///
   /// PHIInst instructions such as
   ///
   /// %PHI = phi float [ %Val1, %IncomingBlock1 ], [ %Val2, %IncomingBlock2 ]
   ///
   /// are modeled as if the accesses occured this way:
   ///
   ///                    _______________________________
public:
   /// #AccessInst of a load is the PHIInst and a incoming block's terminator for
   /// stores. The #BaseAddr is represented through the PHINode because there
   /// also such alloca in the analyzed code. The #AccessValue is represented by
   /// the PHIInst itself.
   ///
   /// Note that there can also be a scalar write access for %PHI if used in a
   /// different BasicBlock, i.e. there can be a %PHI.phiops as well as a
   /// %PHI.s2a.
-  enum AccessOrigin { EXPLICIT, SCALAR, PHI };
+  ///
+  /// * Accesses to emulate PHI node that are in the SCoP's exit block
+  ///
+  /// Like the previous, but the PHI itself is not located in the SCoP itself.
+  /// There will be no READ type MemoryAccess for such values. The PHINode's
+  /// llvm::Value is treated as a value escaping the SCoP. The WRITE access
+  /// write directly to the escaping value's ".s2a" alloca.
+  enum AccessOrigin { EXPLICIT, SCALAR, PHI, EXIT_PHI };
 
   /// @brief The access type of a memory access
   ///
   /// There are three kind of access types:
   ///
   /// * A read access
   ///
   /// A certain set of memory locations are read and may be used for internal
public:
 
   /// @brief Whether this access represents a register access or models PHI
   /// nodes.
   bool isImplicit() const { return !isExplicit(); }
 
   /// @brief Is this MemoryAccess modeling special PHI node accesses?
   bool isPHI() const { return Origin == PHI; }
 
+  /// @brief Is this MemoryAccess modeling the accesses of a PHI node in the
+  /// SCoP's exit block?
+  bool isExitPHI() const { return Origin == EXIT_PHI; }
+
   /// @brief Get the statement that contains this memory access.
   ScopStmt *getStatement() const { return Statement; }
 
   /// @brief Get the reduction type of this access
   ReductionType getReductionType() const { return RedType; }
 
   /// @brief Set the updated access relation read from JSCOP file.
   void setNewAccessRelation(__isl_take isl_map *NewAccessRelation);

include/polly/Support/ScopHelper.h

 /// @param LI The LoopInfo analysis.
 /// @param SE The scalar evolution database.
 /// @param R The region out of which SSA names are parameters.
 /// @return If the instruction I can be regenerated from its
 ///         scalar evolution representation, return true,
 ///         otherwise return false.
 bool canSynthesize(const llvm::Value *V, const llvm::LoopInfo *LI,
                    llvm::ScalarEvolution *SE, const llvm::Region *R);
+
+/// @brief Return the block in which a value is used.
+///
+/// For normal instructions, this is the instruction's parent block. For PHI
+/// nodes, this is the incoming block of that use, because this is where the
+/// operand must be defined (i.e. its definition dominates this block).
+/// Non-instructions do not use operands at a specific point such that in this
+/// case this function returns nullptr.
+llvm::BasicBlock *getUseBlock(llvm::Use &U);
 }
 #endif

lib/Analysis/ScopInfo.cpp

 
 void ScopStmt::buildAccessRelations() {
   for (MemoryAccess *Access : MemAccs) {
     Type *ElementType = Access->getAccessValue()->getType();
 
     ScopArrayInfo::ARRAYKIND Ty;
     if (Access->isPHI())
       Ty = ScopArrayInfo::KIND_PHI;
+    else if (Access->isExitPHI())
+      Ty = ScopArrayInfo::KIND_EXIT_PHI;
     else if (Access->isImplicit())
       Ty = ScopArrayInfo::KIND_SCALAR;
     else
       Ty = ScopArrayInfo::KIND_ARRAY;
 
     const ScopArrayInfo *SAI = getParent()->getOrCreateScopArrayInfo(
         Access->getBaseAddr(), ElementType, Access->Sizes, Ty);
 
bool ScopInfo::buildScalarDependences(Instruction *Inst, Region *R,
                                       Region *NonAffineSubRegion) {
   bool canSynthesizeInst = canSynthesize(Inst, LI, SE, R);
   if (isIgnoredIntrinsic(Inst))
     return false;
 
   bool AnyCrossStmtUse = false;
   BasicBlock *ParentBB = Inst->getParent();
 
-  for (User *U : Inst->users()) {
-    Instruction *UI = dyn_cast<Instruction>(U);
+  for (Use &U : Inst->uses()) {
+    Instruction *UI = dyn_cast<Instruction>(U.getUser());
 
     // Ignore the strange user
     if (UI == 0)
       continue;
 
-    BasicBlock *UseParent = UI->getParent();
+    BasicBlock *UseParent = getUseBlock(U);
 
     // Ignore basic block local uses. A value that is defined in a scop, but
     // used in a PHI node in the same basic block does not count as basic block
     // local, as for such cases a control flow edge is passed between definition
     // and use.
-    if (UseParent == ParentBB && !isa<PHINode>(UI))
+    if (UseParent == ParentBB)
       continue;
 
-    // Uses by PHI nodes in the entry node count as external uses in case the
-    // use is through an incoming block that is itself not contained in the
-    // region.
-    if (R->getEntry() == UseParent) {
-      if (auto *PHI = dyn_cast<PHINode>(UI)) {
-        bool ExternalUse = false;
-        for (unsigned i = 0; i < PHI->getNumIncomingValues(); i++) {
-          if (PHI->getIncomingValue(i) == Inst &&
-              !R->contains(PHI->getIncomingBlock(i))) {
-            ExternalUse = true;
-            break;
-          }
-        }
-
-        if (ExternalUse) {
-          AnyCrossStmtUse = true;
-          continue;
-        }
-      }
-    }
-
     // Do not build scalar dependences inside a non-affine subregion.
     if (NonAffineSubRegion && NonAffineSubRegion->contains(UseParent))
       continue;
 
     // Check for PHI nodes in the region exit and skip them, if they will be
     // modeled as PHI nodes.
     //
     // PHI nodes in the region exit that have more than two incoming edges need
     // to be modeled as PHI-Nodes to correctly model the fact that depending on
     // the control flow a different value will be assigned to the PHI node. In
     // case this is the case, there is no need to create an additional normal
     // scalar dependence. Hence, bail out before we register an "out-of-region"
     // use for this definition.
-    if (isa<PHINode>(UI) && UI->getParent() == R->getExit() &&
-        !R->getExitingBlock())
+    if (isa<PHINode>(UI) && UI->getParent() == R->getExit())
       continue;
 
     // Check whether or not the use is in the SCoP.
     if (!R->contains(UseParent)) {
       AnyCrossStmtUse = true;
       continue;
     }
 
addMemoryAccess(UserBB, User, MemoryAccess::READ, Value, 1, true, Value,
                   ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
                   MemoryAccess::SCALAR);
 }
 void ScopInfo::addPHIWriteAccess(PHINode *PHI, BasicBlock *IncomingBlock,
                                  Value *IncomingValue, bool IsExitBlock) {
   addMemoryAccess(IncomingBlock, IncomingBlock->getTerminator(),
                   MemoryAccess::MUST_WRITE, PHI, 1, true, IncomingValue,
                   ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
-                  IsExitBlock ? MemoryAccess::SCALAR : MemoryAccess::PHI);
+                  IsExitBlock ? MemoryAccess::EXIT_PHI : MemoryAccess::PHI);
 }
 void ScopInfo::addPHIReadAccess(PHINode *PHI) {
   addMemoryAccess(PHI->getParent(), PHI, MemoryAccess::READ, PHI, 1, true, PHI,
                   ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
                   MemoryAccess::PHI);
 }
 
 void ScopInfo::buildScop(Region &R, DominatorTree &DT, AssumptionCache &AC) {

lib/CodeGen/BlockGenerators.cpp

void BlockGenerator::handleOutsideUsers(const Region &R, Instruction *Inst,
                                         Value *Address) {
   // 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()) {
+  for (Use &U : Inst->uses()) {
 
     // Non-instruction user will never escape.
-    Instruction *UI = dyn_cast<Instruction>(U);
+    Instruction *UI = dyn_cast<Instruction>(U.getUser());
     if (!UI)
       continue;
 
-    if (R.contains(UI))
+    if (R.contains(getUseBlock(U)))
       continue;
 
     EscapeUsers.push_back(UI);
   }
 
   // Exit if no escape uses were found.
   if (EscapeUsers.empty())
     return;
for (MemoryAccess *MA : Stmt) {
     Value *Val = MA->getAccessValue();
     auto *Address = getOrCreateAlloca(*MA);
 
     Val = getNewScalarValue(Val, R, Stmt, LTS, BBMap);
     Builder.CreateStore(Val, Address);
   }
 }
 
-void BlockGenerator::createScalarInitialization(Scop &S) {
-  Region &R = S.getRegion();
-  BasicBlock *ExitBB = R.getExit();
-
-  // The split block __just before__ the region and optimized region.
-  BasicBlock *SplitBB = R.getEnteringBlock();
-  BranchInst *SplitBBTerm = cast<BranchInst>(SplitBB->getTerminator());
-  assert(SplitBBTerm->getNumSuccessors() == 2 && "Bad region entering block!");
-
-  // Get the start block of the __optimized__ region.
-  BasicBlock *StartBB = SplitBBTerm->getSuccessor(0);
-  if (StartBB == R.getEntry())
-    StartBB = SplitBBTerm->getSuccessor(1);
-
-  Builder.SetInsertPoint(StartBB->getTerminator());
-
-  for (auto &Pair : S.arrays()) {
-    auto &Array = Pair.second;
-    if (Array->getNumberOfDimensions() != 0)
-      continue;
-    if (Array->isPHI()) {
-      // For PHI nodes, the only values we need to store are the ones that
-      // reach the PHI node from outside the region. In general there should
-      // only be one such incoming edge and this edge should enter through
-      // 'SplitBB'.
-      auto PHI = cast<PHINode>(Array->getBasePtr());
-
-      for (auto BI = PHI->block_begin(), BE = PHI->block_end(); BI != BE; BI++)
-        if (!R.contains(*BI) && *BI != SplitBB)
-          llvm_unreachable("Incoming edges from outside the scop should always "
-                           "come from SplitBB");
-
-      int Idx = PHI->getBasicBlockIndex(SplitBB);
-      if (Idx < 0)
-        continue;
-
-      Value *ScalarValue = PHI->getIncomingValue(Idx);
-
-      Builder.CreateStore(ScalarValue, getOrCreatePHIAlloca(PHI));
-      continue;
-    }
-
-    auto *Inst = dyn_cast<Instruction>(Array->getBasePtr());
-
-    if (Inst && R.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()));
-  }
-}
-
-void BlockGenerator::createScalarFinalization(Region &R) {
+void BlockGenerator::createScalarFinalization(Region &R, Region &GenR,
+                                              BasicBlock *EnteringBlock,
+                                              BasicBlock *SplitBB,
+                                              BasicBlock *MergeBB) {
   // The exit block of the __unoptimized__ region.
   BasicBlock *ExitBB = R.getExitingBlock();
   // The merge block __just after__ the region and the optimized region.
-  BasicBlock *MergeBB = R.getExit();
+  // BasicBlock *MergeBB = R.getExit();
 
   // The exit block of the __optimized__ region.
-  BasicBlock *OptExitBB = *(pred_begin(MergeBB));
-  if (OptExitBB == ExitBB)
-    OptExitBB = *(++pred_begin(MergeBB));
+  // BasicBlock *OptExitBB = *(pred_begin(MergeBB));
+  // if (OptExitBB == ExitBB)
+  //  OptExitBB = *(++pred_begin(MergeBB));
+  BasicBlock *OptExitBB = GenR.getExitingBlock();
+
+  assert(R.getExit() == MergeBB);
+  assert(GenR.getExit() == MergeBB);
 
   Builder.SetInsertPoint(OptExitBB->getTerminator());
   for (const auto &EscapeMapping : EscapeMap) {
     // Extract the escaping instruction and the escaping users as well as the
     // alloca the instruction was demoted to.
     Instruction *EscapeInst = EscapeMapping.getFirst();
     const auto &EscapeMappingValue = EscapeMapping.getSecond();
     const EscapeUserVectorTy &EscapeUsers = EscapeMappingValue.second;
for (const auto &EscapeMapping : EscapeMap) {
     // The information of scalar evolution about the escaping instruction needs
     // to be revoked so the new merged instruction will be used.
     if (SE.isSCEVable(EscapeInst->getType()))
       SE.forgetValue(EscapeInst);
 
     // Replace all uses of the demoted instruction with the merge PHI.
     for (Instruction *EUser : EscapeUsers)
       EUser->replaceUsesOfWith(EscapeInst, MergePHI);
+
+    // It is possible that some PHI uses have been moved to the entering block
+    // during simplification.
+    for (Instruction &EUser : *EnteringBlock)
+      EUser.replaceUsesOfWith(EscapeInst, MergePHI);
   }
 }
 
 void BlockGenerator::findOutsideUsers(Scop &S) {
   auto &R = S.getRegion();
   for (auto &Pair : S.arrays()) {
     auto &Array = Pair.second;
 
for (auto &Pair : S.arrays()) {
     // relevant outside users.
     if (!R.contains(Inst))
       continue;
 
     handleOutsideUsers(R, Inst, nullptr);
   }
 }
 
-void BlockGenerator::createExitPHINodeMerges(Scop &S) {
-  if (S.hasSingleExitEdge())
-    return;
-
-  Region &R = S.getRegion();
-
-  auto *ExitBB = R.getExitingBlock();
-  auto *MergeBB = R.getExit();
-  auto *AfterMergeBB = MergeBB->getSingleSuccessor();
-  BasicBlock *OptExitBB = *(pred_begin(MergeBB));
-  if (OptExitBB == ExitBB)
-    OptExitBB = *(++pred_begin(MergeBB));
-
-  Builder.SetInsertPoint(OptExitBB->getTerminator());
-
-  for (auto &Pair : S.arrays()) {
-    auto &SAI = Pair.second;
-    auto *Val = SAI->getBasePtr();
-
-    PHINode *PHI = dyn_cast<PHINode>(Val);
-    if (!PHI)
-      continue;
-
-    if (PHI->getParent() != AfterMergeBB)
-      continue;
-
-    std::string Name = PHI->getName();
-    Value *ScalarAddr = getOrCreateScalarAlloca(PHI);
-    Value *Reload = Builder.CreateLoad(ScalarAddr, Name + ".ph.final_reload");
-    Reload = Builder.CreateBitOrPointerCast(Reload, PHI->getType());
-    Value *OriginalValue = PHI->getIncomingValueForBlock(MergeBB);
-    auto *MergePHI = PHINode::Create(PHI->getType(), 2, Name + ".ph.merge");
-    MergePHI->insertBefore(&*MergeBB->getFirstInsertionPt());
-    MergePHI->addIncoming(Reload, OptExitBB);
-    MergePHI->addIncoming(OriginalValue, ExitBB);
-    int Idx = PHI->getBasicBlockIndex(MergeBB);
-    PHI->setIncomingValue(Idx, MergePHI);
-  }
-}
-
-void BlockGenerator::finalizeSCoP(Scop &S) {
+void BlockGenerator::finalizeSCoP(Scop &S, Region &GenR) {
   findOutsideUsers(S);
-  createScalarInitialization(S);
-  createExitPHINodeMerges(S);
-  createScalarFinalization(S.getRegion());
+  // createScalarInitialization(S, GenR, SplitBlock);
+  // createExitPHINodeMerges(S);
 }
 
 VectorBlockGenerator::VectorBlockGenerator(BlockGenerator &BlockGen,
                                            std::vector<LoopToScevMapT> &VLTS,
                                            isl_map *Schedule)
     : BlockGenerator(BlockGen), VLTS(VLTS), Schedule(Schedule) {
   assert(Schedule && "No statement domain provided");
 }
BasicBlock *RegionGenerator::repairDominance(BasicBlock *BB,
   return BBCopyIDom;
 }
 
 void RegionGenerator::copyStmt(ScopStmt &Stmt, LoopToScevMapT &LTS,
                                isl_id_to_ast_expr *IdToAstExp) {
   assert(Stmt.isRegionStmt() &&
          "Only region statements can be copied by the region generator");
 
-  Scop *S = Stmt.getParent();
+  // Scop *S = Stmt.getParent();
 
   // Forget all old mappings.
   BlockMap.clear();
   RegionMaps.clear();
   IncompletePHINodeMap.clear();
 
   // Collection of all values related to this subregion.
   ValueMapT ValueMap;
 
   // The region represented by the statement.
   Region *R = Stmt.getRegion();
 
   // Create a dedicated entry for the region where we can reload all demoted
   // inputs.
   BasicBlock *EntryBB = R->getEntry();
   BasicBlock *EntryBBCopy = SplitBlock(Builder.GetInsertBlock(),
                                        &*Builder.GetInsertPoint(), &DT, &LI);
   EntryBBCopy->setName("polly.stmt." + EntryBB->getName() + ".entry");
   Builder.SetInsertPoint(&EntryBBCopy->front());
 
-  ValueMapT &EntryBBMap = RegionMaps[EntryBBCopy];
+  ValueMapT EntryBBMap = RegionMaps[EntryBBCopy];
   generateScalarLoads(Stmt, EntryBBMap);
 
   for (auto PI = pred_begin(EntryBB), PE = pred_end(EntryBB); PI != PE; ++PI)
     if (!R->contains(*PI))
       BlockMap[*PI] = EntryBBCopy;
 
   // Determine the original exit block of this subregion. If it the exit block
   // is also the scop's exit, it it has been changed to polly.merge_new_and_old.
   // We move one block back to find the original block. This only happens if the
   // scop required simplification.
   // If the whole scop consists of only this non-affine region, then they share
   // the same Region object, such that we cannot change the exit of one and not
   // the other.
   BasicBlock *ExitBB = R->getExit();
-  if (!S->hasSingleExitEdge() && ExitBB == S->getRegion().getExit())
-    ExitBB = *(++pred_begin(ExitBB));
+  // if (!S->hasSingleExitEdge() && ExitBB == S->getRegion().getExit())
+  //  ExitBB = *(++pred_begin(ExitBB));
 
   // Iterate over all blocks in the region in a breadth-first search.
   std::deque<BasicBlock *> Blocks;
   SmallPtrSet<BasicBlock *, 8> SeenBlocks;
   Blocks.push_back(EntryBB);
   SeenBlocks.insert(EntryBB);
 
   while (!Blocks.empty()) {
while (!Blocks.empty()) {
     // Remember value in case it is visible after this subregion.
     if (DT.dominates(BB, ExitBB))
       ValueMap.insert(RegionMap.begin(), RegionMap.end());
   }
 
   // Now create a new dedicated region exit block and add it to the region map.
   BasicBlock *ExitBBCopy = SplitBlock(Builder.GetInsertBlock(),
                                       &*Builder.GetInsertPoint(), &DT, &LI);
-  ExitBBCopy->setName("polly.stmt." + R->getExit()->getName() + ".exit");
-  BlockMap[R->getExit()] = ExitBBCopy;
+  ExitBBCopy->setName("polly.stmt." + ExitBB->getName() + ".exit");
+  BlockMap[ExitBB] = ExitBBCopy;
 
-  if (ExitBB == R->getExit())
-    repairDominance(ExitBB, ExitBBCopy);
-  else
-    DT.changeImmediateDominator(ExitBBCopy, BlockMap.lookup(ExitBB));
+  // if (ExitBB == R->getExit())
+  // else
+  //  DT.changeImmediateDominator(ExitBBCopy, BlockMap.lookup(ExitBB));
 
   // As the block generator doesn't handle control flow we need to add the
   // region control flow by hand after all blocks have been copied.
   for (BasicBlock *BB : SeenBlocks) {
 
     BasicBlock *BBCopy = BlockMap[BB];
     TerminatorInst *TI = BB->getTerminator();
     if (isa<UnreachableInst>(TI)) {
for (MemoryAccess *MA : Stmt) {
 
     // In case we add the store into an exiting block, we need to restore the
     // position for stores in the exit node.
     BasicBlock *SavedInsertBB = Builder.GetInsertBlock();
     auto SavedInsertionPoint = Builder.GetInsertPoint();
     ValueMapT *LocalBBMap = &BBMap;
 
     // Implicit writes induced by PHIs must be written in the incoming blocks.
-    if (isa<TerminatorInst>(ScalarInst)) {
+    if (MA->isPHI() || MA->isExitPHI()) {
       BasicBlock *ExitingBB = ScalarInst->getParent();
       BasicBlock *ExitingBBCopy = BlockMap[ExitingBB];
       Builder.SetInsertPoint(ExitingBBCopy->getTerminator());
 
       // For the incoming blocks, use the block's BBMap instead of the one for
       // the entire region.
       LocalBBMap = &RegionMaps[ExitingBBCopy];
     }
 
     auto Address = getOrCreateAlloca(*MA);
 
     Val = getNewScalarValue(Val, R, Stmt, LTS, *LocalBBMap);
     Builder.CreateStore(Val, Address);
 
     // Restore the insertion point if necessary.
-    if (isa<TerminatorInst>(ScalarInst))
+    if (MA->isPHI() || MA->isExitPHI())
       Builder.SetInsertPoint(SavedInsertBB, SavedInsertionPoint);
   }
 }
 
 void RegionGenerator::addOperandToPHI(ScopStmt &Stmt, const PHINode *PHI,
                                       PHINode *PHICopy, BasicBlock *IncomingBB,
                                       LoopToScevMapT &LTS) {
   Region *StmtR = Stmt.getRegion();

lib/CodeGen/CodeGeneration.cpp

 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Verifier.h"
 #include "llvm/Support/Debug.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
 
 using namespace polly;
 using namespace llvm;
 
 #define DEBUG_TYPE "polly-codegen"
 
 namespace {
 class CodeGeneration : public ScopPass {
public:
 
   /// @brief Build the runtime condition.
   ///
   /// Build the condition that evaluates at run-time to true iff all
   /// assumptions taken for the SCoP hold, and to false otherwise.
   ///
   /// @return A value evaluating to true/false if execution is save/unsafe.
   Value *buildRTC(PollyIRBuilder &Builder, IslExprBuilder &ExprBuilder) {
-    Builder.SetInsertPoint(Builder.GetInsertBlock()->getTerminator());
     Value *RTC = ExprBuilder.create(AI->getRunCondition());
     if (!RTC->getType()->isIntegerTy(1))
       RTC = Builder.CreateIsNotNull(RTC);
     return RTC;
   }
 
   bool verifyGeneratedFunction(Scop &S, Function &F) {
     if (!verifyFunction(F))
bool verifyGeneratedFunction(Scop &S, Function &F) {
     return true;
   }
 
   // CodeGeneration adds a lot of BBs without updating the RegionInfo
   // We make all created BBs belong to the scop's parent region without any
   // nested structure to keep the RegionInfo verifier happy.
   void fixRegionInfo(Function *F, Region *ParentRegion) {
     for (BasicBlock &BB : *F) {
-      if (RI->getRegionFor(&BB))
-        continue;
-
+      if (!RI->getRegionFor(&BB))
         RI->setRegionFor(&BB, ParentRegion);
     }
   }
 
   /// @brief Generate LLVM-IR for the SCoP @p S.
   bool runOnScop(Scop &S) override {
     AI = &getAnalysis<IslAstInfo>();
 
     // Check if we created an isl_ast root node, otherwise exit.
     isl_ast_node *AstRoot = AI->getAst();
     if (!AstRoot)
       return false;
 
     LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
     DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
     SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
     DL = &S.getRegion().getEntry()->getParent()->getParent()->getDataLayout();
     RI = &getAnalysis<RegionInfoPass>().getRegionInfo();
     Region *R = &S.getRegion();
+    Region *ParentR = R->getParent();
     assert(!R->isTopLevelRegion() && "Top level regions are not supported");
 
     ScopAnnotator Annotator;
     Annotator.buildAliasScopes(S);
 
-    simplifyRegion(R, DT, LI, RI);
-    assert(R->isSimple());
-    BasicBlock *EnteringBB = S.getRegion().getEnteringBlock();
-    assert(EnteringBB);
-    PollyIRBuilder Builder = createPollyIRBuilder(EnteringBB, Annotator);
-
-    IslNodeBuilder NodeBuilder(Builder, Annotator, this, *DL, *LI, *SE, *DT, S);
-
-    // Only build the run-time condition and parameters _after_ having
-    // introduced the conditional branch. This is important as the conditional
-    // branch will guard the original scop from new induction variables that
-    // the SCEVExpander may introduce while code generating the parameters and
-    // which may introduce scalar dependences that prevent us from correctly
-    // code generating this scop.
-    BasicBlock *StartBlock =
-        executeScopConditionally(S, this, Builder.getTrue());
-    auto SplitBlock = StartBlock->getSinglePredecessor();
+    BasicBlock *OrigEntryBB = R->getEntry();
+    BasicBlock *CommonIDom = DT->getNode(OrigEntryBB)->getIDom()->getBlock();
+    assert(CommonIDom && "Scop cannot begin with the function's entry");
+    BasicBlock *OrigExitBB = R->getExit();
+    auto &F = *OrigEntryBB->getParent();
+
+    BasicBlock *StartBB =
+        BasicBlock::Create(OrigEntryBB->getContext(), "polly.gen_enter", &F);
+    auto TermInst = new UnreachableInst(OrigEntryBB->getContext(), StartBB);
+    DT->addNewBlock(StartBB, CommonIDom); // StartBB starts disconnected from
+                                          // the tree, but there addNewBlock
+                                          // does not allow nullptr as immediate
+                                          // dominator; DT->verifyDomTree()
+                                          // thaerefore fails until it is
+                                          // connected
+
+    BasicBlock *EndBB = llvm::SplitBlock(StartBB, TermInst, DT, LI);
+    EndBB->setName("polly.gen_exit");
+
+    Region *GenR = new Region(StartBB, EndBB, RI, DT);
+    ParentR->addSubRegion(GenR);
+
+    PollyIRBuilder Builder = createPollyIRBuilder(StartBB, Annotator);
+    IslNodeBuilder NodeBuilder(Builder, Annotator, this, *DL, *LI, *SE, *DT, S,
+                               *GenR);
 
     // First generate code for the hoisted invariant loads and transitively the
     // parameters they reference. Afterwards, for the remaining parameters that
     // might reference the hoisted loads. Finally, build the runtime check
     // that might reference both hoisted loads as well as parameters.
     // If the hoisting fails we have to bail and execute the original code.
-    Builder.SetInsertPoint(SplitBlock->getTerminator());
+    Builder.SetInsertPoint(StartBB->getTerminator());
     if (!NodeBuilder.preloadInvariantLoads()) {
 
       auto *FalseI1 = Builder.getFalse();
       auto *SplitBBTerm = Builder.GetInsertBlock()->getTerminator();
       SplitBBTerm->setOperand(0, FalseI1);
-      auto *StartBBTerm = StartBlock->getTerminator();
+      auto *StartBBTerm = StartBB->getTerminator();
       Builder.SetInsertPoint(StartBBTerm);
       Builder.CreateUnreachable();
       StartBBTerm->eraseFromParent();
       isl_ast_node_free(AstRoot);
 
     } else {
 
       NodeBuilder.addParameters(S.getContext());
+      NodeBuilder.create(AstRoot);
+      NodeBuilder.finalizeSCoP(*GenR);
+
+      simplifyRegion(R, DT, LI, RI);
+      assert(R->isSimple());
+
+      BasicBlock *EnteringBB = R->getEnteringBlock();
+      assert(EnteringBB);
 
+      Builder.SetInsertPoint(EnteringBB->getTerminator());
       Value *RTC = buildRTC(Builder, NodeBuilder.getExprBuilder());
-      Builder.GetInsertBlock()->getTerminator()->setOperand(0, RTC);
-      Builder.SetInsertPoint(&StartBlock->front());
+      BasicBlock *StartBlock = executeScopConditionally(S, this, RTC);
+      auto SplitBlock = StartBlock->getSinglePredecessor();
+      auto MergeBlock = StartBlock->getSingleSuccessor();
 
-      NodeBuilder.create(AstRoot);
+      cast<BranchInst>(StartBlock->getTerminator())->setSuccessor(0, StartBB);
+      DT->changeImmediateDominator(StartBB, StartBlock);
+
+      assert(isa<UnreachableInst>(EndBB->getTerminator()));
+      EndBB->getTerminator()->removeFromParent();
+      BranchInst::Create(MergeBlock, EndBB);
+
+      GenR->replaceEntry(StartBlock);
+      RI->setRegionFor(StartBlock, GenR);
+      GenR->replaceExit(MergeBlock);
+
+      Loop *OuterL = LI->getLoopFor(StartBlock);
+      fixRegionInfo(&F, GenR);
+
+      // repair LoopInfo
+      if (OuterL) {
+        for (auto I = LI->begin(), E = LI->end(); I != E;) {
+          Loop *L = *I;
+
+          if (!GenR->contains(L->getHeader())) {
+            ++I;
+            continue;
+          }
+
+          LI->removeLoop(I);
+          L->setParentLoop(nullptr);
+          OuterL->addChildLoop(L);
+        }
+
+        for (auto BB : GenR->blocks())
+          if (!LI->getLoopFor(BB))
+            OuterL->addBasicBlockToLoop(BB, *LI);
+      }
 
-      NodeBuilder.finalizeSCoP(S);
-      fixRegionInfo(EnteringBB->getParent(), R->getParent());
+      NodeBuilder.mergeSCoP(EnteringBB, SplitBlock, MergeBlock);
     }
 
-    assert(!verifyGeneratedFunction(S, *EnteringBB->getParent()) &&
+#ifndef NDEBUG
+    DT->verifyDomTree();
+    RI->verifyAnalysis();
+    LI->verify();
+#endif
+    assert(!verifyGeneratedFunction(S, *StartBB->getParent()) &&
            "Verification of generated function failed");
     return true;
   }
 
   /// @brief Register all analyses and transformation required.
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<DominatorTreeWrapperPass>();
     AU.addRequired<IslAstInfo>();

lib/Support/ScopHelper.cpp

bool polly::canSynthesize(const Value *V, const llvm::LoopInfo *LI,
 
   if (const SCEV *Scev = SE->getSCEV(const_cast<Value *>(V)))
     if (!isa<SCEVCouldNotCompute>(Scev))
       if (!hasScalarDepsInsideRegion(Scev, R))
         return true;
 
   return false;
 }
+
+llvm::BasicBlock *polly::getUseBlock(llvm::Use &U) {
+  Instruction *UI = dyn_cast<Instruction>(U.getUser());
+  if (!UI)
+    return nullptr;
+
+  if (PHINode *PHI = dyn_cast<PHINode>(UI))
+    return PHI->getIncomingBlock(U);
+
+  return UI->getParent();
+}