Index: polly/trunk/include/polly/CodeGen/IRBuilder.h =================================================================== --- polly/trunk/include/polly/CodeGen/IRBuilder.h +++ polly/trunk/include/polly/CodeGen/IRBuilder.h @@ -95,11 +95,16 @@ // // We currently always name instructions, as the polly test suite currently // matches for certain names. -// -// typedef PollyBuilderInserter IRInserter; -// typedef llvm::IRBuilder -// PollyIRBuilder; typedef PollyBuilderInserter IRInserter; typedef llvm::IRBuilder PollyIRBuilder; + +/// @brief Return an IR builder pointed before the @p BB terminator. +static inline PollyIRBuilder createPollyIRBuilder(llvm::BasicBlock *BB, + LoopAnnotator &LA) { + PollyIRBuilder Builder(BB->getContext(), llvm::ConstantFolder(), + polly::IRInserter(LA)); + Builder.SetInsertPoint(BB->getTerminator()); + return Builder; +} } #endif Index: polly/trunk/include/polly/CodeGen/Utils.h =================================================================== --- polly/trunk/include/polly/CodeGen/Utils.h +++ polly/trunk/include/polly/CodeGen/Utils.h @@ -15,6 +15,7 @@ namespace llvm { class Pass; +class Value; class BasicBlock; } @@ -22,16 +23,12 @@ class Scop; -/// @brief Execute a Scop conditionally. +/// @brief Execute a Scop conditionally wrt @p RTC. /// /// In the CFG the optimized code of the Scop is generated next to the /// original code. Both the new and the original version of the code remain -/// in the CFG. A branch statement decides which version is executed. -/// For now, we always execute the new version (the old one is dead code -/// eliminated by the cleanup passes). In the future we may decide to execute -/// the new version only if certain run time checks succeed. This will be -/// useful to support constructs for which we cannot prove all assumptions at -/// compile time. +/// in the CFG. A branch statement decides which version is executed based on +/// the runtime value of @p RTC. /// /// Before transformation: /// @@ -53,9 +50,12 @@ /// \ / /// bb1 (joinBlock) /// -/// @param S The Scop to execute conditionally. -/// @param PassInfo A reference to the pass calling this function. -/// @return BasicBlock The 'StartBlock' to which new code can be added. -llvm::BasicBlock *executeScopConditionally(Scop &S, llvm::Pass *PassInfo); +/// @param S The Scop to execute conditionally. +/// @param P A reference to the pass calling this function. +/// @param RTC The runtime condition checked before executing the new SCoP. +/// +/// @return The 'StartBlock' to which new code can be added. +llvm::BasicBlock *executeScopConditionally(Scop &S, llvm::Pass *P, + llvm::Value *RTC); } #endif Index: polly/trunk/include/polly/Support/ScopHelper.h =================================================================== --- polly/trunk/include/polly/Support/ScopHelper.h +++ polly/trunk/include/polly/Support/ScopHelper.h @@ -52,13 +52,14 @@ llvm::Value *getPointerOperand(llvm::Instruction &Inst); llvm::BasicBlock *createSingleExitEdge(llvm::Region *R, llvm::Pass *P); -/// @brief Simplify the region in a scop to have a single entry edge -/// and a single exit edge. +/// @brief Simplify the region in a SCoP to have a single unconditional entry +/// edge and a single exit edge. /// -/// @param S The scop that is simplified. +/// @param S The SCoP that is simplified. /// @param P The pass that is currently running. /// -void simplifyRegion(polly::Scop *S, llvm::Pass *P); +/// @return The unique entering block for the region. +llvm::BasicBlock *simplifyRegion(polly::Scop *S, llvm::Pass *P); /// @brief Split the entry block of a function to store the newly inserted /// allocations outside of all Scops. Index: polly/trunk/lib/CodeGen/CodeGeneration.cpp =================================================================== --- polly/trunk/lib/CodeGen/CodeGeneration.cpp +++ polly/trunk/lib/CodeGen/CodeGeneration.cpp @@ -1045,7 +1045,8 @@ simplifyRegion(&S, this); - BasicBlock *StartBlock = executeScopConditionally(S, this); + Value *RTC = ConstantInt::getTrue(S.getSE()->getContext()); + BasicBlock *StartBlock = executeScopConditionally(S, this, RTC); PollyIRBuilder Builder(StartBlock->begin()); Index: polly/trunk/lib/CodeGen/IslCodeGeneration.cpp =================================================================== --- polly/trunk/lib/CodeGen/IslCodeGeneration.cpp +++ polly/trunk/lib/CodeGen/IslCodeGeneration.cpp @@ -566,41 +566,51 @@ IslCodeGeneration() : ScopPass(ID) {} + /// @name The analysis passes we need to generate code. + /// + ///{ + LoopInfo *LI; + IslAstInfo *AI; + DominatorTree *DT; + ScalarEvolution *SE; + ///} + + /// @brief The loop annotator to generate llvm.loop metadata. + LoopAnnotator Annotator; + + /// @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()); + return Builder.CreateIsNotNull(RTC); + } + bool runOnScop(Scop &S) { - LoopInfo &LI = getAnalysis(); - IslAstInfo &AstInfo = getAnalysis(); - ScalarEvolution &SE = getAnalysis(); - DominatorTree &DT = getAnalysis().getDomTree(); + LI = &getAnalysis(); + AI = &getAnalysis(); + DT = &getAnalysis().getDomTree(); + SE = &getAnalysis(); assert(!S.getRegion().isTopLevelRegion() && "Top level regions are not supported"); - simplifyRegion(&S, this); - - BasicBlock *StartBlock = executeScopConditionally(S, this); - isl_ast_node *Ast = AstInfo.getAst(); - LoopAnnotator Annotator; - PollyIRBuilder Builder(StartBlock->getContext(), llvm::ConstantFolder(), - polly::IRInserter(Annotator)); - Builder.SetInsertPoint(StartBlock->begin()); + BasicBlock *EnteringBB = simplifyRegion(&S, this); + PollyIRBuilder Builder = createPollyIRBuilder(EnteringBB, Annotator); - IslNodeBuilder NodeBuilder(Builder, Annotator, this, LI, SE, DT); - - Builder.SetInsertPoint(StartBlock->getSinglePredecessor()->begin()); + IslNodeBuilder NodeBuilder(Builder, Annotator, this, *LI, *SE, *DT); NodeBuilder.addMemoryAccesses(S); NodeBuilder.addParameters(S.getContext()); - // Build condition that evaluates at run-time if all assumptions taken - // for the scop hold. If we detect some assumptions do not hold, the - // original code is executed. - Value *V = NodeBuilder.getExprBuilder().create(AstInfo.getRunCondition()); - Value *Zero = ConstantInt::get(V->getType(), 0); - V = Builder.CreateICmp(CmpInst::ICMP_NE, Zero, V); - BasicBlock *PrevBB = StartBlock->getUniquePredecessor(); - BranchInst *Branch = dyn_cast(PrevBB->getTerminator()); - Branch->setCondition(V); + + Value *RTC = buildRTC(Builder, NodeBuilder.getExprBuilder()); + BasicBlock *StartBlock = executeScopConditionally(S, this, RTC); Builder.SetInsertPoint(StartBlock->begin()); - NodeBuilder.create(Ast); + NodeBuilder.create(AI->getAst()); return true; } Index: polly/trunk/lib/CodeGen/Utils.cpp =================================================================== --- polly/trunk/lib/CodeGen/Utils.cpp +++ polly/trunk/lib/CodeGen/Utils.cpp @@ -20,18 +20,17 @@ using namespace llvm; -BasicBlock *polly::executeScopConditionally(Scop &S, Pass *PassInfo) { +BasicBlock *polly::executeScopConditionally(Scop &S, Pass *P, Value *RTC) { BasicBlock *StartBlock, *SplitBlock, *NewBlock; Region &R = S.getRegion(); PollyIRBuilder Builder(R.getEntry()); - DominatorTree &DT = - PassInfo->getAnalysis().getDomTree(); - RegionInfo &RI = PassInfo->getAnalysis().getRegionInfo(); - LoopInfo &LI = PassInfo->getAnalysis(); + DominatorTree &DT = P->getAnalysis().getDomTree(); + RegionInfo &RI = P->getAnalysis().getRegionInfo(); + LoopInfo &LI = P->getAnalysis(); // Split the entry edge of the region and generate a new basic block on this // edge. This function also updates ScopInfo and RegionInfo. - NewBlock = SplitEdge(R.getEnteringBlock(), R.getEntry(), PassInfo); + NewBlock = SplitEdge(R.getEnteringBlock(), R.getEntry(), P); if (DT.dominates(R.getEntry(), NewBlock)) { BasicBlock *OldBlock = R.getEntry(); std::string OldName = OldBlock->getName(); @@ -59,7 +58,7 @@ StartBlock = BasicBlock::Create(F->getContext(), "polly.start", F); SplitBlock->getTerminator()->eraseFromParent(); Builder.SetInsertPoint(SplitBlock); - Builder.CreateCondBr(Builder.getTrue(), StartBlock, R.getEntry()); + Builder.CreateCondBr(RTC, StartBlock, R.getEntry()); if (Loop *L = LI.getLoopFor(SplitBlock)) L->addBasicBlockToLoop(StartBlock, LI.getBase()); DT.addNewBlock(StartBlock, SplitBlock); @@ -72,7 +71,7 @@ // PHI nodes that would complicate life. MergeBlock = R.getExit(); else { - MergeBlock = SplitEdge(R.getExitingBlock(), R.getExit(), PassInfo); + MergeBlock = SplitEdge(R.getExitingBlock(), R.getExit(), P); // SplitEdge will never split R.getExit(), as R.getExit() has more than // one predecessor. Hence, mergeBlock is always a newly generated block. R.replaceExitRecursive(MergeBlock); Index: polly/trunk/lib/Support/ScopHelper.cpp =================================================================== --- polly/trunk/lib/Support/ScopHelper.cpp +++ polly/trunk/lib/Support/ScopHelper.cpp @@ -86,11 +86,14 @@ return SplitBlockPredecessors(BB, Preds, ".region", P); } -void polly::simplifyRegion(Scop *S, Pass *P) { +BasicBlock *polly::simplifyRegion(Scop *S, Pass *P) { Region *R = &S->getRegion(); + // The entering block for the region. + BasicBlock *EnteringBB = R->getEnteringBlock(); + // Create single entry edge if the region has multiple entry edges. - if (!R->getEnteringBlock()) { + if (!EnteringBB) { BasicBlock *OldEntry = R->getEntry(); BasicBlock *NewEntry = SplitBlock(OldEntry, OldEntry->begin(), P); @@ -101,6 +104,13 @@ } R->replaceEntryRecursive(NewEntry); + EnteringBB = OldEntry; + } + + // Create an unconditional entry edge. + if (EnteringBB->getTerminator()->getNumSuccessors() != 1) { + EnteringBB = SplitEdge(EnteringBB, R->getEntry(), P); + EnteringBB->setName("polly.entering.block"); } // Create single exit edge if the region has multiple exit edges. @@ -110,6 +120,8 @@ for (auto &&SubRegion : *R) SubRegion->replaceExitRecursive(NewExit); } + + return EnteringBB; } void polly::splitEntryBlockForAlloca(BasicBlock *EntryBlock, Pass *P) { Index: polly/trunk/test/Isl/CodeGen/blas_sscal_simplified.ll =================================================================== --- polly/trunk/test/Isl/CodeGen/blas_sscal_simplified.ll +++ polly/trunk/test/Isl/CodeGen/blas_sscal_simplified.ll @@ -0,0 +1,44 @@ +; RUN: opt %loadPolly -polly-codegen-isl < %s +; +; Regression test for a bug in the runtime check generation. + +; This was extracted from the blas testcase. It crashed in one +; part of the runtime check generation at some point. To be +; precise, we couldn't find a suitable block to put the RTC code in. +; +; int sscal(int n, float sa, float *sx) { +; for(int i=0; i