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; @@ -26,6 +28,10 @@ class Region; class Pass; class BasicBlock; +class StringRef; +class DominatorTree; +class RegionInfo; +class ScalarEvolution; } namespace polly { @@ -51,16 +57,13 @@ bool hasInvokeEdge(const llvm::PHINode *PN); 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 unconditional entry -/// edge and a single exit edge. +/// @brief Simplify the region to have a single unconditional entry edge and a +/// single exit edge. /// -/// @param S The SCoP that is simplified. +/// @param R The region to be simplified /// @param P The pass that is currently running. -/// -/// @return The unique entering block for the region. -llvm::BasicBlock *simplifyRegion(polly::Scop *S, llvm::Pass *P); +void simplifyRegion(llvm::Region *R, llvm::Pass *P); /// @brief Split the entry block of a function to store the newly inserted /// allocations outside of all Scops. @@ -69,5 +72,24 @@ /// @param P The pass that currently running. /// void splitEntryBlockForAlloca(llvm::BasicBlock *EntryBlock, llvm::Pass *P); + +/// @brief Split the block into two successive blocks. +/// +/// Like llvm::SplitBlock, but also preserves RegionInfo and allows a suffix +/// other than ".split" +/// +/// @param Old Block to split; will be predecessor of the new BasicBlock. +/// @param SplitPt All instructions after and including this instruction are +/// moved to the new block. +/// @param Suffix The new block's name is the old block's name with this suffix +/// appended. +/// @param DT DominatorTree to update. +/// @param LI LoopInfo to update. +/// @param RI RegionInfo to update. +/// +/// @return The new block, unconditional successor of the old one. +llvm::BasicBlock *splitBlock(llvm::BasicBlock *Old, llvm::Instruction *SplitPt, + llvm::StringRef Suffix, llvm::DominatorTree *DT, + llvm::LoopInfo *LI, llvm::RegionInfo *RI); } #endif Index: lib/CodeGen/CodeGeneration.cpp =================================================================== --- lib/CodeGen/CodeGeneration.cpp +++ lib/CodeGen/CodeGeneration.cpp @@ -53,6 +53,7 @@ IslAstInfo *AI; DominatorTree *DT; ScalarEvolution *SE; + RegionInfo *RI; ///} /// @brief The loop annotator to generate llvm.loop metadata. @@ -91,6 +92,18 @@ return true; } + // 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. + void fixRegionInfo(Function *F, Region *ParentRegion) { + for (auto &BB : *F) { + if (RI->getRegionFor(&BB)) + continue; + + RI->setRegionFor(&BB, ParentRegion); + } + } + bool runOnScop(Scop &S) override { AI = &getAnalysis(); @@ -103,13 +116,20 @@ DT = &getAnalysis().getDomTree(); SE = &getAnalysis(); DL = &S.getRegion().getEntry()->getParent()->getParent()->getDataLayout(); + RI = &getAnalysis().getRegionInfo(); assert(!S.getRegion().isTopLevelRegion() && "Top level regions are not supported"); Annotator.buildAliasScopes(S); - BasicBlock *EnteringBB = simplifyRegion(&S, this); + Region *R = &S.getRegion(); + assert(!R->isTopLevelRegion()); + simplifyRegion(R, this); + + assert(R->isSimple()); + BasicBlock *EnteringBB = S.getRegion().getEnteringBlock(); + assert(EnteringBB); PollyIRBuilder Builder = createPollyIRBuilder(EnteringBB, Annotator); IslNodeBuilder NodeBuilder(Builder, Annotator, this, *DL, *LI, *SE, *DT, S); @@ -132,6 +152,7 @@ NodeBuilder.create(AstRoot); NodeBuilder.finalizeSCoP(S); + fixRegionInfo(EnteringBB->getParent(), R->getParent()); assert(!verifyGeneratedFunction(S, *EnteringBB->getParent()) && "Verification of generated function failed"); Index: lib/CodeGen/Utils.cpp =================================================================== --- lib/CodeGen/Utils.cpp +++ lib/CodeGen/Utils.cpp @@ -18,71 +18,157 @@ #include "llvm/Analysis/RegionInfo.h" #include "llvm/Support/Debug.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" +#include "polly/Support/ScopHelper.h" using namespace llvm; +// Alternative to llvm::SplitCriticalEdge. +// llvm::SplitCriticalEdge does nothing if the edge is not critical. +// llvm::SplitEdge is unpredictable in which block it creates. +// +// Creates a new block which branches to Succ. The edge to split is redirected +// to the new block. +static BasicBlock *splitEdge(BasicBlock *Prev, BasicBlock *Succ, + const char *Suffix, DominatorTree *DT, + LoopInfo *LI, RegionInfo *RI) { + assert(Prev && Succ); + + // Before: + /* \ / / */ + /* Prev / */ + /* | \___/ */ + /* | ___ */ + /* | / \ */ + /* Succ \ */ + /* / \ \ */ + + // It might be more efficient to either change llvm::SplitCriticalEdge than to + // llvm::SplitBlockPredecessors optionally forcing it to do something or to + // copy&paste it here without the check whether it is a critical edges + BasicBlock *MiddleBlock = SplitBlockPredecessors( + Succ, ArrayRef(Prev), Suffix, DT, LI); + + if (RI) { + Region *PrevRegion = RI->getRegionFor(Prev); + Region *SuccRegion = RI->getRegionFor(Succ); + if (PrevRegion->contains(MiddleBlock)) { + RI->setRegionFor(MiddleBlock, PrevRegion); + } else { + RI->setRegionFor(MiddleBlock, SuccRegion); + } + } + + // After: + /* \ / / */ + /* Prev / */ + /* | \___/ */ + /* | */ + /* MiddleBlock */ + /* | ___ */ + /* | / \ */ + /* Succ \ */ + /* / \ \ */ + + return MiddleBlock; +} + BasicBlock *polly::executeScopConditionally(Scop &S, Pass *P, Value *RTC) { - BasicBlock *StartBlock, *SplitBlock, *NewBlock; Region &R = S.getRegion(); PollyIRBuilder Builder(R.getEntry()); DominatorTree &DT = P->getAnalysis().getDomTree(); RegionInfo &RI = P->getAnalysis().getRegionInfo(); LoopInfo &LI = P->getAnalysis().getLoopInfo(); - // 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(), &DT, &LI); - if (DT.dominates(R.getEntry(), NewBlock)) { - BasicBlock *OldBlock = R.getEntry(); - std::string OldName = OldBlock->getName(); - - // Update ScopInfo. - for (ScopStmt &Stmt : S) - if (Stmt.getBasicBlock() == OldBlock) { - Stmt.setBasicBlock(NewBlock); - break; - } - - // Update RegionInfo. - SplitBlock = OldBlock; - OldBlock->setName("polly.split"); - NewBlock->setName(OldName); - R.replaceEntryRecursive(NewBlock); - RI.setRegionFor(NewBlock, &R); - } else { - RI.setRegionFor(NewBlock, R.getParent()); - SplitBlock = NewBlock; - } + // Before: + /* \ / */ + /* EnteringBB */ + /* _____|_____ */ + /* / EntryBB \ */ + /* | (region) | */ + /* \_ExitingBB_/ */ + /* | */ + /* ExitBB */ + /* / \ */ - SplitBlock->setName("polly.split_new_and_old"); - Function *F = SplitBlock->getParent(); - StartBlock = BasicBlock::Create(F->getContext(), "polly.start", F); - SplitBlock->getTerminator()->eraseFromParent(); - Builder.SetInsertPoint(SplitBlock); + // Create a fork block + BasicBlock *EnteringBB = R.getEnteringBlock(); + BasicBlock *EntryBB = R.getEntry(); + assert(EnteringBB && "Must be a simple region"); + BasicBlock *JunctionBlock = + splitEdge(EnteringBB, EntryBB, ".split_new_and_old", &DT, &LI, &RI); + JunctionBlock->setName("polly.split_new_and_old"); + + // Create a join block + BasicBlock *ExitingBB = R.getExitingBlock(); + BasicBlock *ExitBB = R.getExit(); + assert(ExitingBB && "Must be a simple region"); + BasicBlock *MergeBlock = + splitEdge(ExitingBB, ExitBB, ".merge_new_and_old", &DT, &LI, &RI); + MergeBlock->setName("polly.merge_new_and_old"); + + // exclude the join block from the region + R.replaceExitRecursive(MergeBlock); + RI.setRegionFor(MergeBlock, R.getParent()); + + /* \ / */ + /* EnteringBB */ + /* | */ + /* fork */ + /* _____|_____ */ + /* / EntryBB \ */ + /* | (region) | */ + /* \_ExitingBB_/ */ + /* | */ + /* join */ + /* | */ + /* ExitBB */ + /* / \ */ + + // Create the start block + Function *F = JunctionBlock->getParent(); + BasicBlock *StartBlock = + BasicBlock::Create(F->getContext(), "polly.start", F); + JunctionBlock->getTerminator()->eraseFromParent(); + Builder.SetInsertPoint(JunctionBlock); Builder.CreateCondBr(RTC, StartBlock, R.getEntry()); - if (Loop *L = LI.getLoopFor(SplitBlock)) + if (Loop *L = LI.getLoopFor(JunctionBlock)) L->addBasicBlockToLoop(StartBlock, LI); - DT.addNewBlock(StartBlock, SplitBlock); - Builder.SetInsertPoint(StartBlock); + DT.addNewBlock(StartBlock, JunctionBlock); + RI.setRegionFor(StartBlock, RI.getRegionFor(JunctionBlock)); - BasicBlock *MergeBlock; - - if (R.getExit()->getSinglePredecessor()) - // No splitEdge required. A block with a single predecessor cannot have - // PHI nodes that would complicate life. - MergeBlock = R.getExit(); - else { - MergeBlock = SplitEdge(R.getExitingBlock(), R.getExit(), &DT, &LI); - // 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); - RI.setRegionFor(MergeBlock, &R); - } + /* \ / */ + /* EnteringBB */ + /* | */ + /* fork-------------\ */ + /* _____|_____ | */ + /* / EntryBB \ polly.start */ + /* | (region) | */ + /* \_ExitingBB_/ */ + /* | */ + /* join */ + /* | */ + /* ExitBB */ + /* / \ */ + // Connect start block to the join block + Builder.SetInsertPoint(StartBlock); Builder.CreateBr(MergeBlock); - MergeBlock->setName("polly.merge_new_and_old"); + DT.changeImmediateDominator(MergeBlock, JunctionBlock); + + // After: + /* \ / */ + /* EnteringBB */ + /* | */ + /* fork-------------\ */ + /* _____|_____ | */ + /* / EntryBB \ polly.start */ + /* | (region) | | */ + /* \_ExitingBB_/ | */ + /* | | */ + /* join------------/ */ + /* | */ + /* ExitBB */ + /* / \ */ - if (DT.dominates(SplitBlock, MergeBlock)) - DT.changeImmediateDominator(MergeBlock, SplitBlock); return StartBlock; } Index: lib/Support/ScopHelper.cpp =================================================================== --- lib/Support/ScopHelper.cpp +++ lib/Support/ScopHelper.cpp @@ -23,6 +23,7 @@ #include "llvm/Transforms/Utils/BasicBlockUtils.h" using namespace llvm; +using namespace polly; #define DEBUG_TYPE "polly-scop-helper" @@ -76,97 +77,139 @@ return false; } -BasicBlock *polly::createSingleExitEdge(Region *R, Pass *P) { - BasicBlock *BB = R->getExit(); +// Ensures that there is just one predecessor to the entry node from outside the +// region. +// The identity of the region entry node is preserved. +static void simplifyRegionEntry(Region *R, Pass *P) { + assert(R); + if (R->isTopLevelRegion()) + return; - SmallVector Preds; - for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) - if (R->contains(*PI)) - Preds.push_back(*PI); - - auto *DTWP = P->getAnalysisIfAvailable(); + auto *DTWP = + P ? P->getAnalysisIfAvailable() : nullptr; auto *DT = DTWP ? &DTWP->getDomTree() : nullptr; - auto *LIWP = P->getAnalysisIfAvailable(); + auto *LIWP = P ? P->getAnalysisIfAvailable() : nullptr; auto *LI = LIWP ? &LIWP->getLoopInfo() : nullptr; + auto RI = R->getRegionInfo(); - return SplitBlockPredecessors(BB, Preds, ".region", DT, LI); -} - -static void replaceScopAndRegionEntry(polly::Scop *S, BasicBlock *OldEntry, - BasicBlock *NewEntry) { - if (polly::ScopStmt *Stmt = S->getStmtForBasicBlock(OldEntry)) - Stmt->setBasicBlock(NewEntry); - - S->getRegion().replaceEntryRecursive(NewEntry); -} - -BasicBlock *polly::simplifyRegion(Scop *S, Pass *P) { - Region *R = &S->getRegion(); - - // The entering block for the region. BasicBlock *EnteringBB = R->getEnteringBlock(); - BasicBlock *OldEntry = R->getEntry(); - BasicBlock *NewEntry = nullptr; + BasicBlock *Entry = R->getEntry(); - auto *DTWP = P->getAnalysisIfAvailable(); - auto *DT = DTWP ? &DTWP->getDomTree() : nullptr; - auto *LIWP = P->getAnalysisIfAvailable(); - auto *LI = LIWP ? &LIWP->getLoopInfo() : nullptr; + // Before (one of): + /* \ / */ + /* EnteringBB */ + /* | \------> */ + /* \ / | */ + /* Entry <--\ Entry <--\ */ + /* / \ / / \ / */ + /* .... .... */ // Create single entry edge if the region has multiple entry edges. if (!EnteringBB) { - NewEntry = SplitBlock(OldEntry, OldEntry->begin(), DT, LI); - EnteringBB = OldEntry; - } + SmallVector Preds; + for (BasicBlock *P : predecessors(Entry)) + if (!R->contains(P)) + Preds.push_back(P); + + BasicBlock *NewEntering = + SplitBlockPredecessors(Entry, Preds, ".region_entering", DT, LI); + + // The entry exit block of predeccessing regions must be changed to + // NewEntering + for (BasicBlock *ExitPred : predecessors(NewEntering)) { + Region *RegionOfPred = RI->getRegionFor(ExitPred); + if (RegionOfPred->getExit() != Entry) + continue; + + while (!RegionOfPred->isTopLevelRegion() && + RegionOfPred->getExit() == Entry) { + RegionOfPred->replaceExit(NewEntering); + RegionOfPred = RegionOfPred->getParent(); + } + } - // Create an unconditional entry edge. - if (EnteringBB->getTerminator()->getNumSuccessors() != 1) { - BasicBlock *EntryBB = NewEntry ? NewEntry : OldEntry; - BasicBlock *SplitEdgeBB = SplitEdge(EnteringBB, EntryBB, DT, LI); - - // Once the edge between EnteringBB and EntryBB is split, two cases arise. - // The first is simple. The new block is inserted between EnteringBB and - // EntryBB. In this case no further action is needed. However it might - // happen (if the splitted edge is not critical) that the new block is - // inserted __after__ EntryBB causing the following situation: - // - // EnteringBB - // _|_ - // | | - // | \-> some_other_BB_not_in_R - // V - // EntryBB - // | - // V - // SplitEdgeBB - // - // In this case we need to swap the role of EntryBB and SplitEdgeBB. - - // Check which case SplitEdge produced: - if (SplitEdgeBB->getTerminator()->getSuccessor(0) == EntryBB) { - // First (simple) case. - EnteringBB = SplitEdgeBB; - } else { - // Second (complicated) case. - NewEntry = SplitEdgeBB; - EnteringBB = EntryBB; + // Make all ancestors use EnteringBB as entry; there might be edges to it + Region *AncestorR = R->getParent(); + RI->setRegionFor(NewEntering, AncestorR); + while (!AncestorR->isTopLevelRegion() && AncestorR->getEntry() == Entry) { + AncestorR->replaceEntry(NewEntering); + AncestorR = AncestorR->getParent(); } - EnteringBB->setName("polly.entering.block"); + EnteringBB = NewEntering; } + assert(R->getEnteringBlock() == EnteringBB); + + // After: + /* \ / */ + /* EnteringBB */ + /* | */ + /* | */ + /* Entry <--\ */ + /* / \ / */ + /* .... */ +} - if (NewEntry) - replaceScopAndRegionEntry(S, OldEntry, NewEntry); +// Ensure that the region has a single block that branches to the exit node. +static void simplifyRegionExit(Region *R, Pass *P) { + assert(R); + if (R->isTopLevelRegion()) + return; - // Create single exit edge if the region has multiple exit edges. - if (!R->getExitingBlock()) { - BasicBlock *NewExiting = createSingleExitEdge(R, P); - (void)NewExiting; - assert(NewExiting == R->getExitingBlock() && - "Did not create a single exiting block"); + auto *DTWP = + P ? P->getAnalysisIfAvailable() : nullptr; + auto *DT = DTWP ? &DTWP->getDomTree() : nullptr; + auto *LIWP = P ? P->getAnalysisIfAvailable() : nullptr; + auto *LI = LIWP ? &LIWP->getLoopInfo() : nullptr; + auto RI = R->getRegionInfo(); + + BasicBlock *ExitBB = R->getExit(); + BasicBlock *ExitingBB = R->getExitingBlock(); + + // Before: + /* (Region) ______/ */ + /* \ | / */ + /* ExitBB */ + /* / \ */ + + if (!ExitingBB) { + SmallVector Preds; + for (BasicBlock *P : predecessors(ExitBB)) + if (R->contains(P)) + Preds.push_back(P); + + /* Preds[0] Preds[1] otherBB */ + /* \ | ________/ */ + /* \ | / */ + /* BB */ + ExitingBB = + SplitBlockPredecessors(ExitBB, Preds, ".region_exiting", DT, LI); + /* Preds[0] Preds[1] otherBB */ + /* \ / / */ + /* BB.exiting / */ + /* \ / */ + /* BB */ + + RI->setRegionFor(ExitingBB, R); + + // Change the exit of nested regions, but not the region itself + R->replaceExitRecursive(ExitingBB); + R->replaceExit(ExitBB); } + assert(ExitingBB == R->getExitingBlock()); + + // After: + /* \ / */ + /* ExitingBB _____/ */ + /* \ / */ + /* ExitBB */ + /* / \ */ +} - return EnteringBB; +void polly::simplifyRegion(Region *R, Pass *P) { + simplifyRegionEntry(R, P); + simplifyRegionExit(R, P); + assert(R->isSimple()); } void polly::splitEntryBlockForAlloca(BasicBlock *EntryBlock, Pass *P) { @@ -176,13 +219,43 @@ while (isa(I)) ++I; - auto *DTWP = P->getAnalysisIfAvailable(); + auto *DTWP = + P ? P->getAnalysisIfAvailable() : nullptr; auto *DT = DTWP ? &DTWP->getDomTree() : nullptr; - auto *LIWP = P->getAnalysisIfAvailable(); + auto *LIWP = P ? P->getAnalysisIfAvailable() : nullptr; auto *LI = LIWP ? &LIWP->getLoopInfo() : nullptr; + auto RIP = P ? P->getAnalysisIfAvailable() : nullptr; + auto RI = RIP ? &RIP->getRegionInfo() : nullptr; + + // SplitBlock updates DT, DF, LI and RI. + splitBlock(EntryBlock, I, ".split", DT, LI, RI); +} + +llvm::BasicBlock *polly::splitBlock(llvm::BasicBlock *Old, + llvm::Instruction *SplitPt, + llvm::StringRef Suffix, + llvm::DominatorTree *DT, llvm::LoopInfo *LI, + llvm::RegionInfo *RI) { + assert(Old && SplitPt); + + // Before: + /* \ / */ + /* Old */ + /* / \ */ + auto OldName = Old->getName(); + BasicBlock *NewBlock = llvm::SplitBlock(Old, SplitPt, DT, LI); + NewBlock->setName(OldName + Suffix); + // After: + /* \ / */ + /* Old */ + /* | */ + /* NewBlock */ + /* / \ */ + + if (RI) { + Region *R = RI->getRegionFor(Old); + RI->setRegionFor(NewBlock, R); + } - // SplitBlock updates DT, DF and LI. - BasicBlock *NewEntry = SplitBlock(EntryBlock, I, DT, LI); - if (RegionInfoPass *RIP = P->getAnalysisIfAvailable()) - RIP->getRegionInfo().splitBlock(NewEntry, EntryBlock); + return NewBlock; } Index: test/Isl/CodeGen/loop_with_conditional_entry_edge_splited_hard_case.ll =================================================================== --- test/Isl/CodeGen/loop_with_conditional_entry_edge_splited_hard_case.ll +++ /dev/null @@ -1,63 +0,0 @@ -; RUN: opt %loadPolly -polly-detect-unprofitable -polly-no-early-exit -polly-codegen -S < %s | FileCheck %s -; -; Test case to trigger the hard way of creating a unique entering -; edge for the SCoP. It is triggered because the entering edge -; here: %while.begin --> %if is __not__ critical. -; -; int f(void); -; void jd(int b, int *A) { -; while (f()) { -; if (b) -; for (int i = 0; i < 1024; i++) -; A[i] = i; -; } -; } -; -target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" - -define void @jd(i32 %b, i32* %A) { -entry: - br label %while.begin - -; CHECK: while.begin: -while.begin: -; CHECK: %call = call i32 @f() - %call = call i32 @f() -; CHECK: %tobool = icmp eq i32 %call, 0 - %tobool = icmp eq i32 %call, 0 -; CHECK: br i1 %tobool, label %while.end, label %polly.entering.block - br i1 %tobool, label %while.end, label %if - -; CHECK: polly.entering.block: -; CHECK: br label %polly.split_new_and_old - -; CHECK: polly.split_new_and_old: -; CHECK: br i1 true, label %polly.start, label %if.split - -; CHECK: if.split: -if: ; preds = %while.begin -; CHECK: %tobool2 = icmp eq i32 %b, 0 - %tobool2 = icmp eq i32 %b, 0 -; CHECK: br i1 %tobool2, label %while.begin{{[a-zA-Z._]*}}, label %for.cond - br i1 %tobool2, label %while.begin, label %for.cond - -for.cond: ; preds = %for.inc, %if - %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %if ] - %exitcond = icmp ne i64 %indvars.iv, 1024 - br i1 %exitcond, label %for.body, label %while.begin - -for.body: ; preds = %for.cond - %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv - %tmp = trunc i64 %indvars.iv to i32 - store i32 %tmp, i32* %arrayidx, align 4 - br label %for.inc - -for.inc: ; preds = %for.body - %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 - br label %for.cond - -while.end: ; preds = %entry, %for.cond - ret void -} - -declare i32 @f() Index: test/Isl/CodeGen/loop_with_conditional_entry_edge_splitted_hard_case.ll =================================================================== --- /dev/null +++ test/Isl/CodeGen/loop_with_conditional_entry_edge_splitted_hard_case.ll @@ -0,0 +1,63 @@ +; RUN: opt %loadPolly -polly-detect-unprofitable -polly-no-early-exit -polly-codegen -S < %s | FileCheck %s +; +; Test case to trigger the hard way of creating a unique entering +; edge for the SCoP. It is triggered because the entering edge +; here: %while.begin --> %if is __not__ critical. +; +; int f(void); +; void jd(int b, int *A) { +; while (f()) { +; if (b) +; for (int i = 0; i < 1024; i++) +; A[i] = i; +; } +; } +; +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define void @jd(i32 %b, i32* %A) { +entry: + br label %while.begin + +; CHECK-LABEL: while.begin.region_exiting: +; CHECK: br label %polly.merge_new_and_old + +; CHECK-LABEL: while.begin: +while.begin: +; CHECK: %call = call i32 @f() + %call = call i32 @f() +; CHECK: %tobool = icmp eq i32 %call, 0 + %tobool = icmp eq i32 %call, 0 +; CHECK: br i1 %tobool, label %while.end, label %polly.split_new_and_old + br i1 %tobool, label %while.end, label %if + +; CHECK-LABEL: polly.split_new_and_old: +; CHECK: br i1 true, label %polly.start, label %if + +; CHECK-LABEL: if: +if: ; preds = %while.begin +; CHECK: %tobool2 = icmp eq i32 %b, 0 + %tobool2 = icmp eq i32 %b, 0 +; CHECK: br i1 %tobool2, label %while.begin{{[a-zA-Z._]*}}, label %for.cond + br i1 %tobool2, label %while.begin, label %for.cond + +for.cond: ; preds = %for.inc, %if + %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %if ] + %exitcond = icmp ne i64 %indvars.iv, 1024 + br i1 %exitcond, label %for.body, label %while.begin + +for.body: ; preds = %for.cond + %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv + %tmp = trunc i64 %indvars.iv to i32 + store i32 %tmp, i32* %arrayidx, align 4 + br label %for.inc + +for.inc: ; preds = %for.body + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + br label %for.cond + +while.end: ; preds = %entry, %for.cond + ret void +} + +declare 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 @@ -12,29 +12,29 @@ ; CHECK-NOT: %tmp7{{[.*]}} = alloca float ; CHECK-DAG: %tmp.0.phiops = alloca float ; CHECK-NOT: %tmp7{{[.*]}} = alloca float -; -; CHECK: polly.merge_new_and_old: -; CHECK-NEXT: ret -; -; CHECK: polly.start: -; CHECK-NEXT: store float 0.000000e+00, float* %tmp.0.phiops -; CHECK: polly.merge: -; CHECK-NEXT: br label %polly.merge_new_and_old +; CHECK-LABEL: exit: +; CHECK-NEXT: ret + +; CHECK-LABEL: polly.start: +; CHECK-NEXT: store float 0.000000e+00, float* %tmp.0.phiops + +; CHECK-LABEL: polly.merge: +; CHECK-NEXT: br label %polly.merge_new_and_old -; CHECK: polly.stmt.bb1{{[0-9]*}}: -; CHECK-NEXT: %tmp.0.phiops.reload[[R1:[0-9]*]] = load float, float* %tmp.0.phiops -; CHECK: store float %tmp.0.phiops.reload[[R1]], float* %tmp.0.s2a +; CHECK-LABEL: polly.stmt.bb1{{[0-9]*}}: +; CHECK-NEXT: %tmp.0.phiops.reload[[R1:[0-9]*]] = load float, float* %tmp.0.phiops +; CHECK: store float %tmp.0.phiops.reload[[R1]], float* %tmp.0.s2a -; CHECK: polly.stmt.bb1{{[0-9]*}}: -; CHECK-NEXT: %tmp.0.phiops.reload[[R2:[0-9]*]] = load float, float* %tmp.0.phiops -; CHECK: store float %tmp.0.phiops.reload[[R2]], float* %tmp.0.s2a +; CHECK-LABEL: polly.stmt.bb1{{[0-9]*}}: +; CHECK-NEXT: %tmp.0.phiops.reload[[R2:[0-9]*]] = load float, float* %tmp.0.phiops +; CHECK: store float %tmp.0.phiops.reload[[R2]], float* %tmp.0.s2a -; CHECK: polly.stmt.bb4: ; preds = %polly.then3 -; CHECK: %tmp[[R5:[0-9]*]]_p_scalar_ = load float, float* %scevgep, align 4, !alias.scope !0, !noalias !2 -; CHECK: %tmp.0.s2a.reload[[R3:[0-9]*]] = load float, float* %tmp.0.s2a -; CHECK: %p_tmp[[R4:[0-9]*]] = fadd float %tmp.0.s2a.reload[[R3]], %tmp[[R5]]_p_scalar_ -; CHECK: store float %p_tmp[[R4]], float* %tmp.0.phiops +; CHECK-LABEL: polly.stmt.bb4: ; preds = %polly.then3 +; CHECK: %tmp[[R5:[0-9]*]]_p_scalar_ = load float, float* %scevgep, align 4, !alias.scope !0, !noalias !2 +; CHECK: %tmp.0.s2a.reload[[R3:[0-9]*]] = load float, float* %tmp.0.s2a +; CHECK: %p_tmp[[R4:[0-9]*]] = fadd float %tmp.0.s2a.reload[[R3]], %tmp[[R5]]_p_scalar_ +; CHECK: store float %p_tmp[[R4]], float* %tmp.0.phiops target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" 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 @@ -6,31 +6,31 @@ ; tmp += A[i]; ; return tmp; ; } -; -; CHECK: polly.merge_new_and_old: -; CHECK-NEXT: %tmp.0.merge = phi float [ %tmp.0.final_reload, %polly.merge ], [ %tmp.0, %bb8 ] -; CHECK-NEXT: ret float %tmp.0.merge -; -; CHECK: polly.start: -; CHECK-NEXT: store float 0.000000e+00, float* %tmp.0.phiops - -; CHECK: polly.merge: -; CHECK-NEXT: %tmp.0.final_reload = load float, float* %tmp.0.s2a -; CHECK-NEXT: br label %polly.merge_new_and_old - -; CHECK: polly.stmt.bb1{{[0-9]*}}: -; CHECK-NEXT: %tmp.0.phiops.reload[[R1:[0-9]*]] = load float, float* %tmp.0.phiops -; CHECK-: store float %tmp.0.phiops.reload[[R1]], float* %tmp.0.s2a - -; CHECK: polly.stmt.bb1{{[0-9]*}}: -; CHECK-NEXT: %tmp.0.phiops.reload[[R2:[0-9]*]] = load float, float* %tmp.0.phiops -; CHECK: store float %tmp.0.phiops.reload[[R2]], float* %tmp.0.s2a - -; CHECK: polly.stmt.bb4: ; preds = %polly.then3 -; CHECK: %tmp[[R5:[0-9]*]]_p_scalar_ = load float, float* %scevgep, align 4, !alias.scope !0, !noalias !2 -; CHECK: %tmp.0.s2a.reload[[R3:[0-9]*]] = load float, float* %tmp.0.s2a -; CHECK: %p_tmp[[R4:[0-9]*]] = fadd float %tmp.0.s2a.reload[[R3]], %tmp[[R5]]_p_scalar_ -; CHECK: store float %p_tmp[[R4]], float* %tmp.0.phiops + +; 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-LABEL: polly.start: +; CHECK-NEXT: store float 0.000000e+00, float* %tmp.0.phiops + +; CHECK-LABEL: polly.merge: +; CHECK-NEXT: %tmp.0.final_reload = load float, float* %tmp.0.s2a +; CHECK-NEXT: br label %polly.merge_new_and_old + +; CHECK-LABEL: polly.stmt.bb1{{[0-9]*}}: +; CHECK-NEXT: %tmp.0.phiops.reload[[R1:[0-9]*]] = load float, float* %tmp.0.phiops +; CHECK-: store float %tmp.0.phiops.reload[[R1]], float* %tmp.0.s2a + +; CHECK-LABEL: polly.stmt.bb1{{[0-9]*}}: +; CHECK-NEXT: %tmp.0.phiops.reload[[R2:[0-9]*]] = load float, float* %tmp.0.phiops +; CHECK: store float %tmp.0.phiops.reload[[R2]], float* %tmp.0.s2a + +; CHECK-LABEL: polly.stmt.bb4: ; preds = %polly.then3 +; CHECK: %tmp[[R5:[0-9]*]]_p_scalar_ = load float, float* %scevgep, align 4, !alias.scope !0, !noalias !2 +; CHECK: %tmp.0.s2a.reload[[R3:[0-9]*]] = load float, float* %tmp.0.s2a +; CHECK: %p_tmp[[R4:[0-9]*]] = fadd float %tmp.0.s2a.reload[[R3]], %tmp[[R5]]_p_scalar_ +; CHECK: store float %p_tmp[[R4]], float* %tmp.0.phiops target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" Index: test/Isl/CodeGen/simple_non_single_entry.ll =================================================================== --- test/Isl/CodeGen/simple_non_single_entry.ll +++ test/Isl/CodeGen/simple_non_single_entry.ll @@ -65,6 +65,6 @@ ret void } -; CHECK: Create LLVM-IR from SCoPs' for region: 'next.split => polly.merge_new_and_old' +; CHECK: Create LLVM-IR from SCoPs' for region: 'next => polly.merge_new_and_old' ; CHECK-CODE: polly.split_new_and_old ; CHECK-CODE: polly.merge_new_and_old