Index: include/polly/CodeGen/BlockGenerators.h =================================================================== --- include/polly/CodeGen/BlockGenerators.h +++ include/polly/CodeGen/BlockGenerators.h @@ -148,7 +148,16 @@ /// /// @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(){}; @@ -394,7 +403,7 @@ /// @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. @@ -410,14 +419,7 @@ /// 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 /// Index: include/polly/CodeGen/IRBuilder.h =================================================================== --- include/polly/CodeGen/IRBuilder.h +++ include/polly/CodeGen/IRBuilder.h @@ -136,7 +136,7 @@ typedef PollyBuilderInserter IRInserter; typedef llvm::IRBuilder 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(), Index: include/polly/CodeGen/IslNodeBuilder.h =================================================================== --- include/polly/CodeGen/IslNodeBuilder.h +++ include/polly/CodeGen/IslNodeBuilder.h @@ -31,12 +31,12 @@ 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() {} @@ -49,7 +49,13 @@ /// @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; } @@ -65,6 +71,8 @@ IslExprBuilder ExprBuilder; + Region &GenR; + /// @brief Maps used by the block and region generator to demote scalars. /// ///@{ Index: include/polly/ScopInfo.h =================================================================== --- include/polly/ScopInfo.h +++ include/polly/ScopInfo.h @@ -105,6 +105,10 @@ // 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, }; @@ -324,7 +328,7 @@ /// #AccessValue is also the llvm::Value itself. /// /// - /// * Accesses to emulate PHI nodes + /// * Accesses to emulate PHI nodes within the SCoP /// /// PHIInst instructions such as /// @@ -359,7 +363,14 @@ /// 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 /// @@ -671,6 +682,10 @@ /// @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; } Index: include/polly/Support/ScopHelper.h =================================================================== --- include/polly/Support/ScopHelper.h +++ include/polly/Support/ScopHelper.h @@ -164,5 +164,14 @@ /// 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 Index: lib/Analysis/ScopInfo.cpp =================================================================== --- lib/Analysis/ScopInfo.cpp +++ lib/Analysis/ScopInfo.cpp @@ -876,6 +876,8 @@ 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 @@ -3494,43 +3496,22 @@ bool AnyCrossStmtUse = false; BasicBlock *ParentBB = Inst->getParent(); - for (User *U : Inst->users()) { - Instruction *UI = dyn_cast(U); + for (Use &U : Inst->uses()) { + Instruction *UI = dyn_cast(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(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(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; @@ -3544,8 +3525,7 @@ // 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(UI) && UI->getParent() == R->getExit() && - !R->getExitingBlock()) + if (isa(UI) && UI->getParent() == R->getExit()) continue; // Check whether or not the use is in the SCoP. @@ -3855,7 +3835,7 @@ addMemoryAccess(IncomingBlock, IncomingBlock->getTerminator(), MemoryAccess::MUST_WRITE, PHI, 1, true, IncomingValue, ArrayRef(), ArrayRef(), - 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, Index: lib/CodeGen/BlockGenerators.cpp =================================================================== --- lib/CodeGen/BlockGenerators.cpp +++ lib/CodeGen/BlockGenerators.cpp @@ -362,14 +362,14 @@ return; EscapeUserVectorTy EscapeUsers; - for (User *U : Inst->users()) { + for (Use &U : Inst->uses()) { // Non-instruction user will never escape. - Instruction *UI = dyn_cast(U); + Instruction *UI = dyn_cast(U.getUser()); if (!UI) continue; - if (R.contains(UI)) + if (R.contains(getUseBlock(U))) continue; EscapeUsers.push_back(UI); @@ -464,76 +464,23 @@ } } -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(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(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(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(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) { @@ -567,6 +514,11 @@ // 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); } } @@ -596,51 +548,10 @@ } } -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(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, @@ -1012,7 +923,7 @@ 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(); @@ -1033,7 +944,7 @@ 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) @@ -1048,8 +959,8 @@ // 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 Blocks; @@ -1106,13 +1017,13 @@ // 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()) + repairDominance(ExitBB, ExitBBCopy); + // 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. @@ -1201,7 +1112,7 @@ ValueMapT *LocalBBMap = &BBMap; // Implicit writes induced by PHIs must be written in the incoming blocks. - if (isa(ScalarInst)) { + if (MA->isPHI() || MA->isExitPHI()) { BasicBlock *ExitingBB = ScalarInst->getParent(); BasicBlock *ExitingBBCopy = BlockMap[ExitingBB]; Builder.SetInsertPoint(ExitingBBCopy->getTerminator()); @@ -1217,7 +1128,7 @@ Builder.CreateStore(Val, Address); // Restore the insertion point if necessary. - if (isa(ScalarInst)) + if (MA->isPHI() || MA->isExitPHI()) Builder.SetInsertPoint(SavedInsertBB, SavedInsertionPoint); } } Index: lib/CodeGen/CodeGeneration.cpp =================================================================== --- lib/CodeGen/CodeGeneration.cpp +++ lib/CodeGen/CodeGeneration.cpp @@ -34,6 +34,7 @@ #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; @@ -67,7 +68,6 @@ /// /// @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); @@ -98,10 +98,8 @@ // nested structure to keep the RegionInfo verifier happy. void fixRegionInfo(Function *F, Region *ParentRegion) { for (BasicBlock &BB : *F) { - if (RI->getRegionFor(&BB)) - continue; - - RI->setRegionFor(&BB, ParentRegion); + if (!RI->getRegionFor(&BB)) + RI->setRegionFor(&BB, ParentRegion); } } @@ -120,41 +118,50 @@ DL = &S.getRegion().getEntry()->getParent()->getParent()->getDataLayout(); RI = &getAnalysis().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); + 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 - IslNodeBuilder NodeBuilder(Builder, Annotator, this, *DL, *LI, *SE, *DT, S); + BasicBlock *EndBB = llvm::SplitBlock(StartBB, TermInst, DT, LI); + EndBB->setName("polly.gen_exit"); - // 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(); + 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(); @@ -163,18 +170,64 @@ } 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(StartBlock->getTerminator())->setSuccessor(0, StartBB); + DT->changeImmediateDominator(StartBB, StartBlock); + + assert(isa(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; } Index: lib/Support/ScopHelper.cpp =================================================================== --- lib/Support/ScopHelper.cpp +++ lib/Support/ScopHelper.cpp @@ -453,3 +453,14 @@ return false; } + +llvm::BasicBlock *polly::getUseBlock(llvm::Use &U) { + Instruction *UI = dyn_cast(U.getUser()); + if (!UI) + return nullptr; + + if (PHINode *PHI = dyn_cast(UI)) + return PHI->getIncomingBlock(U); + + return UI->getParent(); +}