Index: include/polly/CodeGen/Utils.h =================================================================== --- include/polly/CodeGen/Utils.h +++ include/polly/CodeGen/Utils.h @@ -70,5 +70,9 @@ executeScopConditionally(Scop &S, llvm::Value *RTC, llvm::DominatorTree &DT, llvm::RegionInfo &RI, llvm::LoopInfo &LI); +std::pair +executeTopLevelScopConditionally(Scop &S, llvm::Value *RTC, + llvm::DominatorTree &DT, llvm::RegionInfo &RI, + llvm::LoopInfo &LI); } // namespace polly #endif Index: lib/CodeGen/BlockGenerators.cpp =================================================================== --- lib/CodeGen/BlockGenerators.cpp +++ lib/CodeGen/BlockGenerators.cpp @@ -886,8 +886,12 @@ void BlockGenerator::finalizeSCoP(Scop &S) { findOutsideUsers(S); createScalarInitialization(S); - createExitPHINodeMerges(S); - createScalarFinalization(S); + + if (!S.getRegion().isTopLevelRegion()) { + createExitPHINodeMerges(S); + createScalarFinalization(S); + } + invalidateScalarEvolution(S); } Index: lib/CodeGen/CodeGeneration.cpp =================================================================== --- lib/CodeGen/CodeGeneration.cpp +++ lib/CodeGen/CodeGeneration.cpp @@ -159,32 +159,41 @@ isl_ast_node *AstRoot = AI.getAst(); if (!AstRoot) return false; - - auto &DL = S.getFunction().getParent()->getDataLayout(); Region *R = &S.getRegion(); - assert(!R->isTopLevelRegion() && "Top level regions are not supported"); - + Function *F = R->getEntry()->getParent(); + BasicBlock *StartBlock = nullptr, *ExitBlock = nullptr; + BBPair StartExitBlocks; ScopAnnotator Annotator; + PollyIRBuilder Builder = createPollyIRBuilder(R->getEntry(), Annotator); + auto &DL = S.getFunction().getParent()->getDataLayout(); - simplifyRegion(R, &DT, &LI, &RI); - assert(R->isSimple()); - BasicBlock *EnteringBB = S.getEnteringBlock(); - assert(EnteringBB); - PollyIRBuilder Builder = createPollyIRBuilder(EnteringBB, Annotator); - - // 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. - BBPair StartExitBlocks = - std::get<0>(executeScopConditionally(S, Builder.getTrue(), DT, RI, LI)); - BasicBlock *StartBlock = std::get<0>(StartExitBlocks); - BasicBlock *ExitBlock = std::get<1>(StartExitBlocks); - + if (R->isTopLevelRegion()) { + StartExitBlocks = std::get<0>( + executeTopLevelScopConditionally(S, Builder.getTrue(), DT, RI, LI)); + StartBlock = std::get<0>(StartExitBlocks); + ExitBlock = std::get<1>(StartExitBlocks); + } else { + simplifyRegion(R, &DT, &LI, &RI); + assert(R->isSimple()); + BasicBlock *EnteringBB = S.getEnteringBlock(); + assert(EnteringBB); + + // 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. + StartExitBlocks = + std::get<0>(executeScopConditionally(S, Builder.getTrue(), DT, RI, LI)); + StartBlock = std::get<0>(StartExitBlocks); + ExitBlock = std::get<1>(StartExitBlocks); + } removeLifetimeMarkers(R); auto *SplitBlock = StartBlock->getSinglePredecessor(); + if (R->isTopLevelRegion()) { + SplitBlock = SplitBlock->getSinglePredecessor(); + } IslNodeBuilder NodeBuilder(Builder, Annotator, DL, LI, SE, DT, S, StartBlock); @@ -194,7 +203,7 @@ Annotator.buildAliasScopes(S); if (PerfMonitoring) { - PerfMonitor P(S, EnteringBB->getParent()->getParent()); + PerfMonitor P(S, F->getParent()); P.initialize(); P.insertRegionStart(SplitBlock->getTerminator()); @@ -246,10 +255,8 @@ NodeBuilder.create(AstRoot); NodeBuilder.finalize(); - fixRegionInfo(*EnteringBB->getParent(), *R->getParent(), RI); + fixRegionInfo(*F, *R->getParent(), RI); } - - Function *F = EnteringBB->getParent(); verifyGeneratedFunction(S, *F, AI); for (auto *SubF : NodeBuilder.getParallelSubfunctions()) verifyGeneratedFunction(S, *SubF, AI); Index: lib/CodeGen/Utils.cpp =================================================================== --- lib/CodeGen/Utils.cpp +++ lib/CodeGen/Utils.cpp @@ -219,3 +219,108 @@ return std::make_pair(std::make_pair(StartBlock, ExitingBlock), CondBr); } + +// Transforms F to have a single exit node by introducing a new basic block +// and unconditional jumps from the existing nodes with return instructions. +// The return value is obtained with a corresponding phi instruction. +static BasicBlock *unifyFunctionExitNodes(Function &F) { + // Loop over all of the blocks in a function, tracking all of the blocks that + // return. + // + SmallVector ReturningBlocks; + BasicBlock *ReturnBlock = nullptr; + for (BasicBlock &I : F) + if (isa(I.getTerminator())) + ReturningBlocks.push_back(&I); + + // Now handle return blocks. + if (ReturningBlocks.empty()) { + llvm_unreachable("Full function Scop does not return"); + } else if (ReturningBlocks.size() == 1) { + ReturnBlock = ReturningBlocks.front(); // Already has a single return block + return ReturnBlock; + } + + // Otherwise, we need to insert a new basic block into the function, add a PHI + // nodes (if the function returns values), and convert all of the return + // instructions into unconditional branches. + // + BasicBlock *NewRetBlock = BasicBlock::Create(F.getContext(), "polly.ret", &F); + + PHINode *PN = nullptr; + if (F.getReturnType()->isVoidTy()) { + ReturnInst::Create(F.getContext(), nullptr, NewRetBlock); + } else { + // If the function doesn't return void... add a PHI node to the block... + PN = PHINode::Create(F.getReturnType(), ReturningBlocks.size(), + "UnifiedRetVal"); + + NewRetBlock->getInstList().push_back(PN); + ReturnInst::Create(F.getContext(), PN, NewRetBlock); + } + + // Loop over all of the blocks, replacing the return instruction with an + // unconditional branch. + for (BasicBlock *BB : ReturningBlocks) { + // Add an incoming element to the PHI node for every return instruction that + // is merging into this new block... + if (PN) + PN->addIncoming(BB->getTerminator()->getOperand(0), BB); + + BB->getTerminator()->eraseFromParent(); + BranchInst::Create(NewRetBlock, BB); + } + return NewRetBlock; +} + +std::pair +polly::executeTopLevelScopConditionally(Scop &S, Value *RTC, DominatorTree &DT, + RegionInfo &RI, LoopInfo &LI) { + Region *R = &S.getRegion(); + Function *F = R->getEntry()->getParent(); + + splitEntryBlockForAlloca(R->getEntry(), &DT, &LI, &RI); + + BasicBlock *SingleExitBlock = unifyFunctionExitNodes(*F); + + BasicBlock *ExitPred = SingleExitBlock->getSinglePredecessor(); + assert(ExitPred && "Multiple predessors not yet supported."); + + ScopAnnotator Annotator; + PollyIRBuilder Builder = createPollyIRBuilder(R->getEntry(), Annotator); + + BasicBlock *SplitBlock = + BasicBlock::Create(F->getContext(), "polly.split", F); + + BasicBlock *JoinBlock = + splitEdge(ExitPred, SingleExitBlock, "polly.merge", &DT, &LI, &RI); + + BasicBlock *StartBlock = + BasicBlock::Create(F->getContext(), "polly.start", F); + + BasicBlock *ExitingBlock = + BasicBlock::Create(F->getContext(), "polly.exiting", F); + + Builder.SetInsertPoint(SplitBlock); + Builder.CreateBr(StartBlock); + + Builder.SetInsertPoint(StartBlock); + Builder.CreateBr(ExitingBlock); + + Builder.SetInsertPoint(ExitingBlock); + Builder.CreateBr(JoinBlock); + + BasicBlock *EntrySucc = R->getEntry()->getSingleSuccessor(); + assert(EntrySucc); + R->getEntry()->getTerminator()->eraseFromParent(); + Builder.SetInsertPoint(R->getEntry()); + BranchInst *CondBr = Builder.CreateCondBr(RTC, EntrySucc, SplitBlock); + + DT.recalculate(*F); + // TODO : Update DT incrementally + if (Loop *L = LI.getLoopFor(SplitBlock)) { + L->addBasicBlockToLoop(StartBlock, LI); + L->addBasicBlockToLoop(ExitingBlock, LI); + } + return std::make_pair(std::make_pair(StartBlock, ExitingBlock), CondBr); +} Index: lib/Support/ScopHelper.cpp =================================================================== --- lib/Support/ScopHelper.cpp +++ lib/Support/ScopHelper.cpp @@ -291,7 +291,9 @@ else if (Inst && RTCBB->getParent() == Inst->getFunction()) IP = RTCBB->getTerminator(); else - IP = RTCBB->getParent()->getEntryBlock().getTerminator(); + IP = R.isTopLevelRegion() + ? R.getEntry()->getTerminator() + : RTCBB->getParent()->getEntryBlock().getTerminator(); if (!Inst || (Inst->getOpcode() != Instruction::SRem && Inst->getOpcode() != Instruction::SDiv)) Index: test/Isl/CodeGen/full-function.ll =================================================================== --- /dev/null +++ test/Isl/CodeGen/full-function.ll @@ -0,0 +1,29 @@ +; RUN: opt %loadPolly -polly-codegen -polly-detect-full-functions -S \ +; RUN: < %s | FileCheck %s +; CHECK: polly.split: +; CHECK: polly.start: +; CHECK: polly.stmt.bb2: + +@A = common global [1024 x i32] zeroinitializer, align 16 ; <[1024 x i32]*> [#uses=3] + +define void @bar(i64 %n) nounwind { +bb: + br label %bb1 + +bb1: ; preds = %bb3, %bb + %i.0 = phi i64 [ 0, %bb ], [ %tmp, %bb3 ] ; [#uses=3] + %scevgep = getelementptr [1024 x i32], [1024 x i32]* @A, i64 0, i64 %i.0 ; [#uses=1] + %exitcond = icmp ne i64 %i.0, %n ; [#uses=1] + br i1 %exitcond, label %bb2, label %bb4 + +bb2: ; preds = %bb1 + store i32 1, i32* %scevgep + br label %bb3 + +bb3: ; preds = %bb2 + %tmp = add nsw i64 %i.0, 1 ; [#uses=1] + br label %bb1 + +bb4: ; preds = %bb1 + ret void +}