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/Support/ScopHelper.h =================================================================== --- include/polly/Support/ScopHelper.h +++ include/polly/Support/ScopHelper.h @@ -14,6 +14,8 @@ #ifndef POLLY_SUPPORT_IRHELPER_H #define POLLY_SUPPORT_IRHELPER_H +#include "llvm/ADT/ArrayRef.h" + namespace llvm { class Type; class Instruction; @@ -77,5 +79,52 @@ /// @param P The pass that currently running. /// void splitEntryBlockForAlloca(llvm::BasicBlock *EntryBlock, llvm::Pass *P); + +/// @brief Move a set of incoming edges to a new successor. +/// +/// Similar to llvm::SplitPredecessors, but instead of creating a new +/// predecessor, this creates a new successor. +/// Preserves LCSSA because all PHIs will exist in both BasicBlocks. A PHI node +/// is created in the successor for every PHI in the original block, even if +/// there is only one incoming edge. PHI nodes in the orginal block are never +/// removed, even if they have fewer than two incoming edges left. +/// We generally cannot update RegionInfo since it could invalidate regions, +/// depending on the list of edges. +/// +/// Before: After: +/// +/// NonPred[0] NonPred[0] +/// \ / \ / +/// /---->Entry /-->Entry / +/// | | | \ / +/// \--BlockInRegion | Entry.split +/// | | +/// \-------BlockInRegion +/// +/// If Entry is split. neither "Entry" nor "Entry.split" can be made the +/// region's entry node. "Entry" cannot because there is en edge from an +/// ouside-of-region block NonPred[0] to another region block, violating the +/// single entry requirement of a region. The new block "Entry.split" cannot be +/// the entry block because there is an exiting edge to "Entry", which would +/// then be an alternative to the region's other exit block. +/// There is a similar situation with the exit block conflicting with other +/// regions. +/// Hence, the caller of this function should make sure such cases do not happen +/// and update RegionInfo accordingly. +/// +/// @param BB Block to split. +/// @param NonPreds Set of incoming edges to move to the new successor. +/// @param Suffix Suffix to append to the name of the new block. +/// @param DT DominatorTree to update. +/// @param LI LoopInfo to update. +/// @param SE ScalarEvolution to update. +/// +/// @return The newly created successor of BB or null if the block could not be +/// split. +llvm::BasicBlock * +splitBlockNonPredecessors(llvm::BasicBlock *BB, + llvm::ArrayRef NonPreds, + llvm::StringRef Suffix, llvm::DominatorTree *DT, + llvm::LoopInfo *LI, llvm::ScalarEvolution *SE); } #endif Index: include/polly/TempScopInfo.h =================================================================== --- include/polly/TempScopInfo.h +++ include/polly/TempScopInfo.h @@ -306,6 +306,14 @@ void buildAccessFunctions(Region &R, BasicBlock &BB, Region *NonAffineSubRegion = nullptr); + /// @brief Determine whether an instruction belongs to the Scop. + /// + /// @param R The region representing the scop. + /// @param Inst The instruction to query. + /// + /// @return True iff the instruction belongs to the scop. + bool scopContains(llvm::Region *R, llvm::Instruction *Inst) const; + public: static char ID; explicit TempScopInfo() : RegionPass(ID), TempScopOfRegion(nullptr) {} Index: lib/Analysis/ScopDetection.cpp =================================================================== --- lib/Analysis/ScopDetection.cpp +++ lib/Analysis/ScopDetection.cpp @@ -761,7 +761,7 @@ // 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 +903,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 +945,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 @@ -859,9 +859,10 @@ } void ScopStmt::deriveAssumptions(BasicBlock *Block) { - for (Instruction &Inst : *Block) + for (Instruction &Inst : *Block) { if (auto *GEP = dyn_cast(&Inst)) deriveAssumptionsFromGEP(GEP); + } } ScopStmt::ScopStmt(Scop &parent, TempScop &tempScop, const Region &CurRegion, @@ -895,8 +896,16 @@ BaseName = getIslCompatibleName("Stmt_", &bb, ""); Domain = buildDomain(tempScop, CurRegion); + assert((parent.getRegion().getExit() != BB || + isl_set_dim(Domain, isl_dim_set) == 0) && + "Exit block does not have a domain"); buildAccesses(tempScop, BB); - deriveAssumptions(BB); + + // In the exit block, we are only interested in PHI nodes which have no + // assumptions. + if (Parent.getRegion().getExit() != BB) { + deriveAssumptions(BB); + } checkForReductions(); } @@ -1478,6 +1487,12 @@ if (!Schedule) Schedule = isl_schedule_empty(getParamSpace()); + // Build the statement for PHIs in the exit block (never nested in a + // scopped-loop) + isl_schedule *StmtSchedule = + buildBBScopStmt(getRegion().getExit(), TempScop, getRegion(), NestLoops); + Schedule = combineInSequence(Schedule, StmtSchedule); + realignParams(); addParameterBounds(); simplifyAssumedContext(); Index: lib/Analysis/TempScopInfo.cpp =================================================================== --- lib/Analysis/TempScopInfo.cpp +++ lib/Analysis/TempScopInfo.cpp @@ -178,7 +178,11 @@ BasicBlock *UseParent = UI->getParent(); // Ignore the users in the same BB (statement) - if (UseParent == ParentBB) + // There will be a split in the Exit BB after the last PHI instruction which + // we have to consider. PHI nodes in the exit block are in a different block + // than non-PHI instructions. + if ((UseParent == ParentBB) && + !(UseParent == R->getExit() && isa(Inst) != isa(UI))) continue; // Do not build scalar dependences inside a non-affine subregion. @@ -186,7 +190,7 @@ continue; // Check whether or not the use is in the SCoP. - if (!R->contains(UseParent)) { + if (!scopContains(R, UI)) { AnyCrossStmtUse = true; continue; } @@ -221,7 +225,7 @@ continue; if (Instruction *OpInst = dyn_cast(Op)) - if (R->contains(OpInst)) + if (scopContains(R, OpInst)) continue; IRAccess ScalarAccess(IRAccess::READ, Op, ZeroOffset, 1, true); @@ -315,6 +319,13 @@ for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I) { Instruction *Inst = I; + + // The PHI nodes of the exit block are later moved into the region so handle + // them like any other PHI. All following instructions do not belong to the + // region and are skipped. + if (R.getExit() == &BB && !isa(Inst)) + break; + if (isa(Inst) || isa(Inst)) Functions.push_back( std::make_pair(buildIRAccess(Inst, L, &R, BoxedLoops), Inst)); @@ -338,6 +349,18 @@ Accs.insert(Accs.end(), Functions.begin(), Functions.end()); } +bool TempScopInfo::scopContains(Region *R, llvm::Instruction *Inst) const { + if (R->contains(Inst)) + return true; + + // The region will be extended later to also contain the PHI nodes in the exit + // block. + if (Inst->getParent() == R->getExit() && isa(Inst)) + return true; + + return false; +} + Comparison TempScopInfo::buildAffineCondition(Value &V, bool inverted) { if (ConstantInt *C = dyn_cast(&V)) { // If this is always true condition, we will create 0 <= 1, @@ -453,6 +476,7 @@ TempScop *TScop = new TempScop(R, BBConds, AccFuncMap); buildAccessFunctions(R, R); + buildAccessFunctions(R, *R.getExit()); for (const auto &BB : R.blocks()) buildCondition(BB, R); Index: lib/CodeGen/CodeGeneration.cpp =================================================================== --- lib/CodeGen/CodeGeneration.cpp +++ lib/CodeGen/CodeGeneration.cpp @@ -93,6 +93,74 @@ return true; } + // Create a dedicated block for exit node PHIs. + // This special block is made the exiting block so the PHIs become included + // into the region. + // The exit block itself keeps its identity. + BasicBlock *createExitingBlockForExitNodePHIs(Region *R) { + BasicBlock *ExitBB = R->getExit(); + + SmallVector NonPreds; + for (BasicBlock *P : predecessors(ExitBB)) + if (!R->contains(P)) + NonPreds.push_back(P); + + // Preds[0] Preds[1] otherBB // + // \ | ________/ // + // \ | / // + // ExitBB // + BasicBlock *NewExitBlock = + splitBlockNonPredecessors(ExitBB, NonPreds, ".exit", DT, LI, SE); + // Preds[0] Preds[1] otherBB // + // \ / / // + // ExitBB / // + // \ / // + // NewExitBlock // + + // Set the region of the newly created block. + Region *RegionOfExit = RI->getRegionFor(ExitBB); + RI->setRegionFor(NewExitBlock, RegionOfExit); + + // If there was a region with ExitBB as entry block, change it to + // NewExitBlock. + while (RegionOfExit && !RegionOfExit->isTopLevelRegion() && + RegionOfExit->getEntry() == ExitBB) { + RegionOfExit->replaceEntry(NewExitBlock); + RegionOfExit = RegionOfExit->getParent(); + } + + // Change the exit node of R, but not its subregions because they can keep + // ExitBB as their exit block. + // This ensures that the region of ExitBB is always R itself. + R->replaceExit(NewExitBlock); + RI->setRegionFor(ExitBB, R); + + // Make NewExitBlock the new exit block of all other regions that previously + // had ExitBB as exit block. + for (BasicBlock *PotentialExiting : predecessors(NewExitBlock)) { + if (PotentialExiting == NewExitBlock) + continue; + + Region *OtherR = RI->getRegionFor(PotentialExiting); + while (OtherR && !OtherR->isTopLevelRegion() && + OtherR->getExit() == ExitBB) { + OtherR->replaceExit(NewExitBlock); + OtherR = OtherR->getParent(); + } + } + + assert(R->contains(ExitBB)); + assert(!R->contains(NewExitBlock)); + assert(R->getExit() == NewExitBlock); + assert(R->getExitingBlock() == ExitBB); + +#ifndef NDEBUG + RI->verifyAnalysis(); +#endif + + return ExitBB; // The block containing the PHIs + } + // 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. @@ -123,8 +191,10 @@ Annotator.buildAliasScopes(S); + createExitingBlockForExitNodePHIs(R); simplifyRegion(R, DT, LI, RI); assert(R->isSimple()); + BasicBlock *EnteringBB = S.getRegion().getEnteringBlock(); assert(EnteringBB); PollyIRBuilder Builder = createPollyIRBuilder(EnteringBB, Annotator); Index: lib/Support/SCEVValidator.cpp =================================================================== --- lib/Support/SCEVValidator.cpp +++ lib/Support/SCEVValidator.cpp @@ -482,9 +482,15 @@ bool visitUnknown(const SCEVUnknown *Expr) { Instruction *Inst = dyn_cast(Expr->getValue()); + if (!Inst) + return false; // Return true when Inst is defined inside the region R. - if (Inst && R->contains(Inst)) + if (R->contains(Inst)) + return true; + + // PHI nodes of the exit node will be moved later into the scop + if (R->getExit() == Inst->getParent() && isa(Inst)) return true; return false; Index: lib/Support/ScopHelper.cpp =================================================================== --- lib/Support/ScopHelper.cpp +++ lib/Support/ScopHelper.cpp @@ -252,3 +252,137 @@ // splitBlock updates DT, LI and RI. splitBlock(EntryBlock, I, DT, LI, RI); } + +BasicBlock *polly::splitBlockNonPredecessors(BasicBlock *BB, + ArrayRef NonPreds, + llvm::StringRef Suffix, + DominatorTree *DT, LoopInfo *LI, + ScalarEvolution *SE) { + assert(BB); + + // Do not attempt to split blocks that cannot be split. + if (!BB->canSplitPredecessors()) + return nullptr; + + // Currently we cannot handle landing pads. + if (BB->isLandingPad()) + return nullptr; + + // Before: + // + // NonPreds[0] // + // \ / // + // BB // + // / \ // + + // Create new basic block, insert right after the original block. + auto OldName = BB->getName(); + BasicBlock *NewBB = + splitBlock(BB, BB->getFirstInsertionPt(), DT, LI, nullptr); + NewBB->setName(OldName + Suffix); + + // Create new PHIs into the new block. + for (auto I = BB->begin(); isa(I); ++I) { + PHINode *OldPHI = cast(&*I); + PHINode *NewPHI = PHINode::Create(OldPHI->getType(), NonPreds.size() + 1, + OldPHI->getName() + ".np", + NewBB->getFirstInsertionPt()); + + // Replaces uses of the original PHI by the new ones. + OldPHI->replaceAllUsesWith(NewPHI); + + // Add an edge from the original block (this adds a use) + NewPHI->addIncoming(OldPHI, BB); + + // Move the incoming block's values. + for (BasicBlock *Edge : NonPreds) { + BasicBlock *RedirectedEdge = Edge == BB ? NewBB : Edge; + auto i = OldPHI->getBasicBlockIndex(RedirectedEdge); + assert(i >= 0); + Value *Val = OldPHI->getIncomingValue(i); + NewPHI->addIncoming(Val, RedirectedEdge); + OldPHI->removeIncomingValue(i, false); + + if (SE) + SE->forgetValue(OldPHI); + } + } + + // If there were no edges to move, there is nothing more to do. + if (NonPreds.empty()) + return NewBB; + + // Move all non-pred edges to the new BB. + for (BasicBlock *Edge : NonPreds) { + BasicBlock *RedirectedEdge = Edge == BB ? NewBB : Edge; + assert(!isa(RedirectedEdge->getTerminator()) && + "Cannot split an edge from an IndirectBrInst"); + RedirectedEdge->getTerminator()->replaceUsesOfWith(BB, NewBB); + } + + if (DT) { + // DominatorTree::splitBlock assumes that it is the predecessor which is + // new. In order to reuse that function, we recreate the situation as if it + // was. + auto BBNode = DT->getNode(BB); + auto NewBBNode = DT->getNode(NewBB); + DT->changeImmediateDominator(NewBBNode, BBNode->getIDom()); + DT->eraseNode(BB); + + DT->splitBlock(BB); + } + + if (LI) { + BasicBlock *OldBB = BB; + Loop *L = LI->getLoopFor(OldBB); + while (L) { + assert(L->contains(OldBB)); + + bool OldBBReachableFromInside = false; + for (BasicBlock *Pred : predecessors(OldBB)) { + if (Pred == NewBB || L->contains(Pred)) { + OldBBReachableFromInside = true; + break; + } + } + + bool NewBBReachableFromOutside = false; + for (auto Pred : make_range(pred_begin(NewBB), pred_end(NewBB))) { + if (Pred == OldBB) + continue; + + if (Pred != NewBB && !L->contains(Pred)) { + NewBBReachableFromOutside = true; + break; + } + } + + if (NewBBReachableFromOutside || !OldBBReachableFromInside) { + // Remove BB from the loop and make the NewBB the next loop header. + // Since NewBB dominates OldBB, it can be the new header. + if (L->getHeader() == OldBB) + L->moveToHeader(NewBB); + } + + if (!OldBBReachableFromInside) { + // OldBB cannot be reached from the loop header anymore, i.e. it has + // been excluded from the loop. + L->removeBlockFromLoop(BB); + LI->changeLoopFor(BB, L->getParentLoop()); + } + + L = L->getParentLoop(); + } + } + + // After: + // + // NonPreds[0] // + // \ / // + // BB / // + // \ / // + // NewBB // + // / \ // + + return NewBB; +} \ No newline at end of file Index: test/Isl/CodeGen/loop_with_conditional_entry_edge_split_hard_case.ll =================================================================== --- test/Isl/CodeGen/loop_with_conditional_entry_edge_split_hard_case.ll +++ test/Isl/CodeGen/loop_with_conditional_entry_edge_split_hard_case.ll @@ -19,10 +19,10 @@ entry: br label %while.begin -; CHECK-LABEL: while.begin.region_exiting: -; CHECK: br label %polly.merge_new_and_old - ; CHECK-LABEL: while.begin: +; CHECK: br label %polly.merge_new_and_old + +; CHECK-LABEL: while.begin.exit: while.begin: ; CHECK: %call = call i32 @f() %call = call i32 @f() Index: test/Isl/CodeGen/phi_loop_carried_float.ll =================================================================== --- test/Isl/CodeGen/phi_loop_carried_float.ll +++ test/Isl/CodeGen/phi_loop_carried_float.ll @@ -13,7 +13,10 @@ ; CHECK-DAG: %tmp.0.phiops = alloca float ; CHECK-NOT: %tmp7{{[.*]}} = alloca float -; CHECK-LABEL: exit: +; CHECK-LABEL: polly.merge_new_and_old: +; CHECK-NEXT: br label %exit.exit + +; CHECK-LABEL: exit.exit: ; CHECK-NEXT: ret ; CHECK-LABEL: polly.start: Index: test/Isl/CodeGen/phi_loop_carried_float_escape.ll =================================================================== --- test/Isl/CodeGen/phi_loop_carried_float_escape.ll +++ test/Isl/CodeGen/phi_loop_carried_float_escape.ll @@ -8,8 +8,11 @@ ; } ; CHECK-LABEL: polly.merge_new_and_old: -; CHECK-NEXT: %tmp.0.merge = phi float [ %tmp.0.final_reload, %polly.merge ], [ %tmp.0, %bb8 ] -; CHECK-NEXT: br label %exit +; CHECK-NEXT: %tmp.0.merge = phi float [ %tmp.0.final_reload, %polly.merge ], [ %tmp.0, %exit ] +; CHECK-NEXT: br label %exit.exit + +; CHECK-LABEL: exit.exit: +; CHECK-NEXT: ret float %tmp.0.merge ; CHECK-LABEL: polly.start: ; CHECK-NEXT: store float 0.000000e+00, float* %tmp.0.phiops Index: test/Isl/CodeGen/phi_scalar_simple_1.ll =================================================================== --- test/Isl/CodeGen/phi_scalar_simple_1.ll +++ test/Isl/CodeGen/phi_scalar_simple_1.ll @@ -22,7 +22,7 @@ br label %for.cond ; CHECK-LABEL: polly.merge_new_and_old: -; CHECK: %x.addr.0.merge = phi i32 [ %x.addr.0.final_reload, %polly.merge ], [ %x.addr.0, %for.cond ] +; CHECK: %x.addr.0.merge = phi i32 [ %x.addr.0.final_reload, %polly.merge ], [ %x.addr.0, %for.end6 ] ; CHECK: ret i32 %x.addr.0.merge ; CHECK-LABEL: polly.start: Index: test/Isl/CodeGen/phi_scalar_simple_2.ll =================================================================== --- test/Isl/CodeGen/phi_scalar_simple_2.ll +++ test/Isl/CodeGen/phi_scalar_simple_2.ll @@ -24,7 +24,7 @@ br label %for.cond ; CHECK-LABEL: polly.merge_new_and_old: -; CHECK: %x.addr.0.merge = phi i32 [ %x.addr.0.final_reload, %polly.merge ], [ %x.addr.0, %for.cond ] +; CHECK: %x.addr.0.merge = phi i32 [ %x.addr.0.final_reload, %polly.merge ], [ %x.addr.0, %for.end7 ] ; CHECK: ret i32 %x.addr.0.merge ; CHECK-LABEL: polly.start: Index: test/ScopDetect/keep_going_expansion.ll =================================================================== --- test/ScopDetect/keep_going_expansion.ll +++ test/ScopDetect/keep_going_expansion.ll @@ -42,4 +42,4 @@ ret i32 %add } -; CHECK: Valid Region for Scop: for.body => for.cond2.preheader +; CHECK: Valid Region for Scop: for.body => for.body4 Index: test/ScopDetect/multidim_indirect_access.ll =================================================================== --- test/ScopDetect/multidim_indirect_access.ll +++ test/ScopDetect/multidim_indirect_access.ll @@ -10,9 +10,6 @@ ; treated as a multidimensional access with dimension size x. This test will ; check that we correctly invalidate the region and do not detect a outer SCoP. ; -; FIXME: -; We should detect the inner region but the PHI node in the exit blocks that. -; ; void f(int *A, long N) { ; int j = 0; ; while (N > j) { @@ -25,8 +22,8 @@ ; } ; } ; -; INDEPENDENT-NOT: Valid -; NON_INDEPENDENT-NOT: Valid +; INDEPENDENT-NOT: Valid Region for Scop: bb0 => bb1 +; NON_INDEPENDENT-NOT: Valid Region for Scop: bb0 => bb1 ; target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" Index: test/ScopDetect/non-affine-loop-condition-dependent-access_2.ll =================================================================== --- test/ScopDetect/non-affine-loop-condition-dependent-access_2.ll +++ test/ScopDetect/non-affine-loop-condition-dependent-access_2.ll @@ -7,9 +7,9 @@ ; innermost loop as a SCoP of depth 1, we have to reject the loop nest if not ; both, non-affine loops as well as non-affine accesses are allowed. ; -; REJECTNONAFFINELOOPS: Valid Region for Scop: bb15 => bb26 +; REJECTNONAFFINELOOPS: Valid Region for Scop: bb15 => bb13 ; REJECTNONAFFINELOOPS-NOT: Valid -; ALLOWNONAFFINELOOPS: Valid Region for Scop: bb15 => bb26 +; ALLOWNONAFFINELOOPS: Valid Region for Scop: bb15 => bb13 ; ALLOWNONAFFINELOOPS-NOT: Valid ; ALLOWNONAFFINELOOPSANDACCESSES: Valid Region for Scop: bb11 => bb29 ; Index: test/ScopDetect/non-affine-loop-condition-dependent-access_3.ll =================================================================== --- test/ScopDetect/non-affine-loop-condition-dependent-access_3.ll +++ test/ScopDetect/non-affine-loop-condition-dependent-access_3.ll @@ -7,9 +7,9 @@ ; innermost loop as a SCoP of depth 1, we have to reject the loop nest if not ; both, non-affine loops as well as non-affine accesses are allowed. ; -; REJECTNONAFFINELOOPS: Valid Region for Scop: bb15 => bb26 +; REJECTNONAFFINELOOPS: Valid Region for Scop: bb15 => bb13 ; REJECTNONAFFINELOOPS-NOT: Valid -; ALLOWNONAFFINELOOPS: Valid Region for Scop: bb15 => bb26 +; ALLOWNONAFFINELOOPS: Valid Region for Scop: bb15 => bb13 ; ALLOWNONAFFINELOOPS-NOT: Valid ; ALLOWNONAFFINELOOPSANDACCESSES: Valid Region for Scop: bb11 => bb29 ; Index: test/ScopDetect/phi_with_multi_exiting_edges.ll =================================================================== --- test/ScopDetect/phi_with_multi_exiting_edges.ll +++ test/ScopDetect/phi_with_multi_exiting_edges.ll @@ -1,7 +1,5 @@ ; RUN: opt %loadPolly -polly-detect-unprofitable -polly-detect -analyze -S < %s | FileCheck %s ; -; XFAIL: * -; ; Region with an exit node that has a PHI node multiple incoming edges from ; inside the region. Motivation for supporting such cases in Polly. ; Index: test/ScopDetect/phi_with_multi_exiting_edges_2.ll =================================================================== --- /dev/null +++ test/ScopDetect/phi_with_multi_exiting_edges_2.ll @@ -0,0 +1,35 @@ +; RUN: opt %loadPolly -polly-detect-unprofitable -polly-detect -analyze -S < %s | FileCheck %s + +define float @foo(float* %A, i64 %param) { +entry: + br label %entry.split + +entry.split: + %branchcond = icmp slt i64 %param, 64 + br i1 %branchcond, label %loopA, label %loopB + +loopA: + %indvarA = phi i64 [0, %entry.split], [%indvar.nextA, %loopA] + %indvar.nextA = add i64 %indvarA, 1 + %valA = load float, float* %A + %sumA = fadd float %valA, %valA + store float %valA, float* %A + %cndA = icmp eq i64 %indvar.nextA, 100 + br i1 %cndA, label %next, label %loopA + +loopB: + %indvarB = phi i64 [0, %entry.split], [%indvar.nextB, %loopB] + %indvar.nextB = add i64 %indvarB, 1 + %valB = load float, float* %A + %sumB = fadd float %valB, %valB + store float %valB, float* %A + %cndB = icmp eq i64 %indvar.nextB, 100 + br i1 %cndB, label %next, label %loopB + +next: + %result = phi float [%sumA, %loopA], [%sumB, %loopB] + ret float %result + +} + +; CHECK: Valid Region for Scop: entry.split => next Index: test/ScopDetect/simple_non_single_entry.ll =================================================================== --- test/ScopDetect/simple_non_single_entry.ll +++ test/ScopDetect/simple_non_single_entry.ll @@ -65,4 +65,4 @@ ret void } -; CHECK: Valid Region for Scop: next => for.i.head1 +; CHECK: Valid Region for Scop: next => for.i Index: test/ScopInfo/20111108-Parameter-not-detected.ll =================================================================== --- test/ScopInfo/20111108-Parameter-not-detected.ll +++ test/ScopInfo/20111108-Parameter-not-detected.ll @@ -54,5 +54,5 @@ ; CHECK: p0: {0,+,1}<%for.cond> ; CHECK: Domain := -; CHECK: [p_0] -> { Stmt_if_then[i0] : i0 >= 0 and i0 <= 1022 and i0 >= 999 - p_0 }; +; CHECK: [p_0] -> { Stmt_if_then[i0] : i0 <= 1022 and i0 >= 0 and i0 >= 999 - p_0 }; Index: test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_2.ll =================================================================== --- test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_2.ll +++ test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_2.ll @@ -9,7 +9,7 @@ ; access. ; ; INNERMOST: Function: f -; INNERMOST: Region: %bb15---%bb26 +; INNERMOST: Region: %bb15---%bb13 ; INNERMOST: Max Loop Depth: 1 ; INNERMOST: p0: {0,+,{0,+,-1}<%bb11>}<%bb13> ; INNERMOST: p1: {0,+,{0,+,1}<%bb11>}<%bb13> @@ -19,11 +19,11 @@ ; INNERMOST: Alias Groups (0): ; INNERMOST: n/a ; INNERMOST: Statements { -; INNERMOST: Stmt_bb16 +; INNERMOST: Stmt_bb16 ; INNERMOST: Domain := -; INNERMOST: [p_0, p_1, p_2, p_3, p_4] -> { Stmt_bb16[i0] : (i0 <= 1023 - p_1 and i0 >= 0 and i0 <= 1024 + p_0) or (i0 >= 0 and i0 >= 1025 - p_1 and i0 <= 1024 + p_0) }; +; INNERMOST: [p_0, p_1, p_2, p_3, p_4] -> { Stmt_bb16[i0] : (i0 >= 0 and i0 >= 1025 - p_1 and i0 <= 1024 + p_0) or (i0 <= 1023 - p_1 and i0 >= 0 and i0 <= 1024 + p_0) }; ; INNERMOST: Schedule := -; INNERMOST: [p_0, p_1, p_2, p_3, p_4] -> { Stmt_bb16[i0] -> [i0] : i0 >= 1025 - p_1 or i0 <= 1023 - p_1 }; +; INNERMOST: [p_0, p_1, p_2, p_3, p_4] -> { Stmt_bb16[i0] -> [0, i0] : i0 >= 1025 - p_1 or i0 <= 1023 - p_1 }; ; INNERMOST: ReadAccess := [Reduction Type: NONE] [Scalar: 0] ; INNERMOST: [p_0, p_1, p_2, p_3, p_4] -> { Stmt_bb16[i0] -> MemRef_A[o0] : 4o0 = p_2 }; ; INNERMOST: ReadAccess := [Reduction Type: NONE] [Scalar: 0] @@ -32,6 +32,13 @@ ; INNERMOST: [p_0, p_1, p_2, p_3, p_4] -> { Stmt_bb16[i0] -> MemRef_A[o0] : 4o0 = p_4 + 4i0 }; ; INNERMOST: MustWriteAccess := [Reduction Type: +] [Scalar: 0] ; INNERMOST: [p_0, p_1, p_2, p_3, p_4] -> { Stmt_bb16[i0] -> MemRef_A[o0] : 4o0 = p_4 + 4i0 }; +; INNERMOST: Stmt_bb13 +; INNERMOST: Domain := +; INNERMOST: [p_0, p_1, p_2, p_3, p_4] -> { Stmt_bb13[] }; +; INNERMOST: Schedule := +; INNERMOST: [p_0, p_1, p_2, p_3, p_4] -> { Stmt_bb13[] -> [1, 0] }; +; INNERMOST: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; INNERMOST: [p_0, p_1, p_2, p_3, p_4] -> { Stmt_bb13[] -> MemRef_indvars_iv5[] }; ; INNERMOST: } ; ; ALL: Function: f Index: test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_3.ll =================================================================== --- test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_3.ll +++ test/ScopInfo/NonAffine/non-affine-loop-condition-dependent-access_3.ll @@ -9,7 +9,7 @@ ; access. ; ; INNERMOST: Function: f -; INNERMOST: Region: %bb15---%bb26 +; INNERMOST: Region: %bb15---%bb13 ; INNERMOST: Max Loop Depth: 1 ; INNERMOST: Context: ; INNERMOST: [p_0, p_1, p_2] -> { : p_0 >= 0 and p_0 <= 2147483647 and p_1 >= 0 and p_1 <= 4096 and p_2 >= 0 and p_2 <= 4096 } @@ -25,7 +25,7 @@ ; INNERMOST: Domain := ; INNERMOST: [p_0, p_1, p_2] -> { Stmt_bb16[i0] : i0 >= 0 and i0 <= -1 + p_0 }; ; INNERMOST: Schedule := -; INNERMOST: [p_0, p_1, p_2] -> { Stmt_bb16[i0] -> [i0] }; +; INNERMOST: [p_0, p_1, p_2] -> { Stmt_bb16[i0] -> [0, i0] }; ; INNERMOST: ReadAccess := [Reduction Type: NONE] [Scalar: 0] ; INNERMOST: [p_0, p_1, p_2] -> { Stmt_bb16[i0] -> MemRef_A[o0] : 4o0 = p_1 }; ; INNERMOST: ReadAccess := [Reduction Type: NONE] [Scalar: 0]