Index: include/polly/CodeGen/BlockGenerators.h =================================================================== --- include/polly/CodeGen/BlockGenerators.h +++ include/polly/CodeGen/BlockGenerators.h @@ -338,7 +338,9 @@ /// @param R The current SCoP region. /// @param Inst The current instruction we check. /// @param InstCopy The copy of the instruction @p Inst in the optimized SCoP. - void handleOutsideUsers(const Region &R, Instruction *Inst, Value *InstCopy); + /// @param Address If given it is used as the escape address for @p Inst. + void handleOutsideUsers(const Region &R, Instruction *Inst, Value *InstCopy, + AllocaInst *Address = nullptr); /// @brief Initialize the memory of demoted scalars. /// Index: include/polly/ScopDetection.h =================================================================== --- include/polly/ScopDetection.h +++ include/polly/ScopDetection.h @@ -223,13 +223,6 @@ /// @return True if all blocks in R are valid, false otherwise. bool allBlocksValid(DetectionContext &Context) const; - /// @brief Check the exit block of a region is valid. - /// - /// @param Context The context of scop detection. - /// - /// @return True if the exit of R is valid, false otherwise. - bool isValidExit(DetectionContext &Context) const; - /// @brief Check if a region is a Scop. /// /// @param Context The context of scop detection. Index: include/polly/ScopInfo.h =================================================================== --- include/polly/ScopInfo.h +++ include/polly/ScopInfo.h @@ -777,6 +777,9 @@ /// Flag to indicate that the scheduler actually optimized the SCoP. bool IsOptimized; + /// @brief True if the underlying region has a single exiting block. + bool HasSingleExitEdge; + /// Max loop depth. unsigned MaxLoopDepth; @@ -1124,6 +1127,9 @@ /// @brief Align the parameters in the statement to the scop context void realignParams(); + /// @brief Return true if the underlying region has a single exiting block. + bool hasSingleExitEdge() const { return HasSingleExitEdge; } + /// @brief Print the static control part. /// /// @param OS The output stream the static control part is printed to. Index: include/polly/TempScopInfo.h =================================================================== --- include/polly/TempScopInfo.h +++ include/polly/TempScopInfo.h @@ -293,8 +293,9 @@ /// @param R The SCoP region /// @param Functions The access functions of the current BB /// @param NonAffineSubRegion The non affine sub-region @p PHI is in. + /// @param IsExitBlock Flag to indicate that @p PHI is in the exit BB. void buildPHIAccesses(PHINode *PHI, Region &R, AccFuncSetType &Functions, - Region *NonAffineSubRegion); + Region *NonAffineSubRegion, bool IsExitBlock = false); /// @brief Build the access functions for the subregion @p SR. /// @@ -307,8 +308,10 @@ /// @param R The SCoP region. /// @param BB A basic block in @p R. /// @param NonAffineSubRegion The non affine sub-region @p BB is in. + /// @param IsExitBlock Flag to indicate that @p BB is in the exit BB. void buildAccessFunctions(Region &R, BasicBlock &BB, - Region *NonAffineSubRegion = nullptr); + Region *NonAffineSubRegion = nullptr, + bool IsExitBlock = false); public: static char ID; Index: lib/Analysis/ScopDetection.cpp =================================================================== --- lib/Analysis/ScopDetection.cpp +++ lib/Analysis/ScopDetection.cpp @@ -760,8 +760,7 @@ DEBUG(dbgs() << "\t\tTrying " << ExpandedRegion->getNameStr() << "\n"); // Only expand when we did not collect errors. - // Check the exit first (cheap) - if (isValidExit(Context) && !Context.Log.hasErrors()) { + if (!Context.Log.hasErrors()) { // If the exit is valid check all blocks // - if true, a valid region was found => store it + keep expanding // - if false, .tbd. => stop (should this really end the loop?) @@ -903,18 +902,6 @@ return true; } -bool ScopDetection::isValidExit(DetectionContext &Context) const { - - // PHI nodes are not allowed in the exit basic block. - if (BasicBlock *Exit = Context.CurRegion.getExit()) { - BasicBlock::iterator I = Exit->begin(); - if (I != Exit->end() && isa(*I)) - return invalid(Context, /*Assert=*/true, I); - } - - return true; -} - bool ScopDetection::isValidRegion(DetectionContext &Context) const { Region &CurRegion = Context.CurRegion; @@ -957,9 +944,6 @@ &(CurRegion.getEntry()->getParent()->getEntryBlock())) return invalid(Context, /*Assert=*/true, CurRegion.getEntry()); - if (!isValidExit(Context)) - return false; - if (!allBlocksValid(Context)) return false; Index: lib/Analysis/ScopInfo.cpp =================================================================== --- lib/Analysis/ScopInfo.cpp +++ lib/Analysis/ScopInfo.cpp @@ -1495,7 +1495,8 @@ Scop::Scop(Region &R, ScalarEvolution &ScalarEvolution, isl_ctx *Context, unsigned MaxLoopDepth) : SE(&ScalarEvolution), R(R), IsOptimized(false), - MaxLoopDepth(MaxLoopDepth), IslCtx(Context), Affinator(this) {} + HasSingleExitEdge(R.getExitingBlock()), MaxLoopDepth(MaxLoopDepth), + IslCtx(Context), Affinator(this) {} void Scop::initFromTempScop(TempScop &TempScop, LoopInfo &LI, ScopDetection &SD) { Index: lib/Analysis/TempScopInfo.cpp =================================================================== --- lib/Analysis/TempScopInfo.cpp +++ lib/Analysis/TempScopInfo.cpp @@ -107,8 +107,18 @@ void TempScopInfo::buildPHIAccesses(PHINode *PHI, Region &R, AccFuncSetType &Functions, - Region *NonAffineSubRegion) { - if (canSynthesize(PHI, LI, SE, &R)) + Region *NonAffineSubRegion, + bool IsExitBlock) { + + // PHI nodes that are in the ExitBlock of the region, hence if IsExitBlock is + // true, are not modelt as ordinary PHI nodes as they are not part of the + // region. However, we model the operands in the predecessor blocks that are + // part of the region as regular scalar accesses. + + // If we can synthesize a PHI we can skip it, however only if it is in + // the region. If it is not it can only be in the exit block of the region. + // In this case we model the operands but not the PHI itself. + if (PHI->getParent() != R.getExit() && canSynthesize(PHI, LI, SE, &R)) return; // PHI nodes are modeled as if they had been demoted prior to the SCoP @@ -149,13 +159,13 @@ OpI = OpBB->getTerminator(); IRAccess ScalarAccess(IRAccess::MUST_WRITE, PHI, ZeroOffset, 1, true, Op, - /* IsPHI */ true); + /* IsPHI */ !IsExitBlock); AccFuncMap[OpBB].push_back(std::make_pair(ScalarAccess, OpI)); } if (!OnlyNonAffineSubRegionOperands) { IRAccess ScalarAccess(IRAccess::READ, PHI, ZeroOffset, 1, true, PHI, - /* IsPHI */ true); + /* IsPHI */ !IsExitBlock); Functions.push_back(std::make_pair(ScalarAccess, PHI)); } } @@ -310,7 +320,8 @@ } void TempScopInfo::buildAccessFunctions(Region &R, BasicBlock &BB, - Region *NonAffineSubRegion) { + Region *NonAffineSubRegion, + bool IsExitBlock) { AccFuncSetType Functions; Loop *L = LI->getLoopFor(&BB); @@ -319,13 +330,19 @@ for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I) { Instruction *Inst = I; + + PHINode *PHI = dyn_cast(Inst); + if (PHI) + buildPHIAccesses(PHI, R, Functions, NonAffineSubRegion, IsExitBlock); + + // For the exit block we stop modeling after the last PHI node. + if (!PHI && IsExitBlock) + break; + if (isa(Inst) || isa(Inst)) Functions.push_back( std::make_pair(buildIRAccess(Inst, L, &R, BoxedLoops), Inst)); - if (PHINode *PHI = dyn_cast(Inst)) - buildPHIAccesses(PHI, R, Functions, NonAffineSubRegion); - if (!isa(Inst) && buildScalarDependences(Inst, &R, NonAffineSubRegion)) { // If the Instruction is used outside the statement, we need to build the @@ -459,6 +476,15 @@ buildAccessFunctions(R, R); + // In case the region does not have an exiting block we will later (during + // code generation) split the exit block. This will move potential PHI nodes + // in the exit block into the region that are at this point not part of it. + // To handle these PHI nodes later on we will model their operands as scalar + // accesses. Note that we do not model anything in the exit block if we have + // a exiting block in the region, hence there will not be any splitting later. + if (!R.getExitingBlock()) + buildAccessFunctions(R, *R.getExit(), nullptr, /* IsExitBlock */ true); + for (const auto &BB : R.blocks()) buildCondition(BB, R); Index: lib/CodeGen/BlockGenerators.cpp =================================================================== --- lib/CodeGen/BlockGenerators.cpp +++ lib/CodeGen/BlockGenerators.cpp @@ -373,7 +373,7 @@ } void BlockGenerator::handleOutsideUsers(const Region &R, Instruction *Inst, - Value *InstCopy) { + Value *InstCopy, AllocaInst *Address) { EscapeUserVectorTy EscapeUsers; for (User *U : Inst->users()) { @@ -402,18 +402,18 @@ return; // Get or create an escape alloca for this instruction. - bool IsNew; - AllocaInst *ScalarAddr = - getOrCreateAlloca(Inst, ScalarMap, ".escape", &IsNew); + bool IsNew = false; + if (!Address) + Address = getOrCreateAlloca(Inst, ScalarMap, ".escape", &IsNew); // Remember that this instruction has escape uses and the escape alloca. - EscapeMap[Inst] = std::make_pair(ScalarAddr, std::move(EscapeUsers)); + EscapeMap[Inst] = std::make_pair(Address, std::move(EscapeUsers)); // If the escape alloca was just created store the instruction in there, // otherwise that happened already. if (IsNew) { assert(InstCopy && "Except PHIs every instruction should have a copy!"); - Builder.CreateStore(InstCopy, ScalarAddr); + Builder.CreateStore(InstCopy, Address); } } @@ -587,6 +587,23 @@ } void BlockGenerator::finalizeSCoP(Scop &S, ValueMapT &GlobalMap) { + + // Handle PHI nodes that were in the original exit and are now + // moved into the region exiting block. + if (!S.hasSingleExitEdge()) { + for (Instruction &I : *S.getRegion().getExitingBlock()) { + PHINode *PHI = dyn_cast(&I); + if (!PHI) + break; + + assert(PHI->getNumUses() == 1); + assert(ScalarMap.count(PHI->user_back())); + + AllocaInst *Address = ScalarMap[PHI->user_back()]; + handleOutsideUsers(S.getRegion(), PHI, nullptr, Address); + } + } + createScalarInitialization(S.getRegion(), GlobalMap); createScalarFinalization(S.getRegion()); }