Index: polly/trunk/include/polly/ScopDetection.h =================================================================== --- polly/trunk/include/polly/ScopDetection.h +++ polly/trunk/include/polly/ScopDetection.h @@ -271,6 +271,28 @@ /// @return True if the instruction is valid, false otherwise. bool isValidInstruction(Instruction &Inst, DetectionContext &Context) const; + /// @brief Check if the switch @p SI with condition @p Condition is valid. + /// + /// @param BB The block to check. + /// @param SI The switch to check. + /// @param Condition The switch condition. + /// @param Context The context of scop detection. + /// + /// @return True if the branch @p BI is valid. + bool isValidSwitch(BasicBlock &BB, SwitchInst *SI, Value *Condition, + DetectionContext &Context) const; + + /// @brief Check if the branch @p BI with condition @p Condition is valid. + /// + /// @param BB The block to check. + /// @param BI The branch to check. + /// @param Condition The branch condition. + /// @param Context The context of scop detection. + /// + /// @return True if the branch @p BI is valid. + bool isValidBranch(BasicBlock &BB, BranchInst *BI, Value *Condition, + DetectionContext &Context) const; + /// @brief Check if the control flow in a basic block is valid. /// /// @param BB The BB to check the control flow. Index: polly/trunk/include/polly/ScopDetectionDiagnostic.h =================================================================== --- polly/trunk/include/polly/ScopDetectionDiagnostic.h +++ polly/trunk/include/polly/ScopDetectionDiagnostic.h @@ -62,7 +62,7 @@ enum RejectReasonKind { // CFG Category rrkCFG, - rrkNonBranchTerminator, + rrkInvalidTerminator, rrkCondition, rrkLastCFG, @@ -230,13 +230,13 @@ }; //===----------------------------------------------------------------------===// -/// @brief Captures a non-branch terminator within a Scop candidate. -class ReportNonBranchTerminator : public ReportCFG { +/// @brief Captures bad terminator within a Scop candidate. +class ReportInvalidTerminator : public ReportCFG { BasicBlock *BB; public: - ReportNonBranchTerminator(BasicBlock *BB) - : ReportCFG(rrkNonBranchTerminator), BB(BB) {} + ReportInvalidTerminator(BasicBlock *BB) + : ReportCFG(rrkInvalidTerminator), BB(BB) {} /// @name LLVM-RTTI interface //@{ Index: polly/trunk/include/polly/Support/ScopHelper.h =================================================================== --- polly/trunk/include/polly/Support/ScopHelper.h +++ polly/trunk/include/polly/Support/ScopHelper.h @@ -30,6 +30,7 @@ class DataLayout; class DominatorTree; class RegionInfo; +class TerminatorInst; class ScalarEvolution; } @@ -113,5 +114,14 @@ /// /// @return True if the block is a error block, false otherwise. bool isErrorBlock(llvm::BasicBlock &BB); + +/// @brief Return the condition for the terminator @p TI. +/// +/// For unconditional branches the "i1 true" condition will be returned. +/// +/// @param TI The terminator to get the condition from. +/// +/// @return The condition of @p TI and nullptr if none could be extracted. +llvm::Value *getConditionFromTerminator(llvm::TerminatorInst *TI); } #endif Index: polly/trunk/lib/Analysis/ScopDetection.cpp =================================================================== --- polly/trunk/lib/Analysis/ScopDetection.cpp +++ polly/trunk/lib/Analysis/ScopDetection.cpp @@ -299,40 +299,35 @@ return (AllowNonAffineSubLoops || Context.BoxedLoopsSet.empty()); } -bool ScopDetection::isValidCFG(BasicBlock &BB, - DetectionContext &Context) const { +bool ScopDetection::isValidSwitch(BasicBlock &BB, SwitchInst *SI, + Value *Condition, + DetectionContext &Context) const { Region &CurRegion = Context.CurRegion; - TerminatorInst *TI = BB.getTerminator(); - - // Return instructions are only valid if the region is the top level region. - if (isa(TI) && !CurRegion.getExit() && TI->getNumOperands() == 0) - return true; - - BranchInst *Br = dyn_cast(TI); + Loop *L = LI->getLoopFor(&BB); + const SCEV *ConditionSCEV = SE->getSCEVAtScope(Condition, L); - if (!Br) - return invalid(Context, /*Assert=*/true, &BB); - - if (Br->isUnconditional()) - return true; + if (!isAffineExpr(&CurRegion, ConditionSCEV, *SE)) + if (!AllowNonAffineSubRegions || + !addOverApproximatedRegion(RI->getRegionFor(&BB), Context)) + return invalid(Context, /*Assert=*/true, &BB, + ConditionSCEV, ConditionSCEV, SI); - Value *Condition = Br->getCondition(); + return true; +} - // UndefValue is not allowed as condition. - if (isa(Condition)) - return invalid(Context, /*Assert=*/true, Br, &BB); +bool ScopDetection::isValidBranch(BasicBlock &BB, BranchInst *BI, + Value *Condition, + DetectionContext &Context) const { + Region &CurRegion = Context.CurRegion; - // Only Constant and ICmpInst are allowed as condition. - if (!(isa(Condition) || isa(Condition))) { + // Non constant conditions of branches need to be ICmpInst. + if (!isa(Condition)) { if (!AllowNonAffineSubRegions || !addOverApproximatedRegion(RI->getRegionFor(&BB), Context)) - return invalid(Context, /*Assert=*/true, Br, &BB); + return invalid(Context, /*Assert=*/true, BI, &BB); } - // Allow perfectly nested conditions. - assert(Br->getNumSuccessors() == 2 && "Unexpected number of successors"); - if (ICmpInst *ICmp = dyn_cast(Condition)) { // Unsigned comparisons are not allowed. They trigger overflow problems // in the code generation. @@ -340,7 +335,7 @@ // TODO: This is not sufficient and just hides bugs. However it does pretty // well. if (ICmp->isUnsigned() && !AllowUnsigned) - return invalid(Context, /*Assert=*/true, Br, &BB); + return invalid(Context, /*Assert=*/true, BI, &BB); // Are both operands of the ICmp affine? if (isa(ICmp->getOperand(0)) || @@ -369,6 +364,38 @@ return true; } +bool ScopDetection::isValidCFG(BasicBlock &BB, + DetectionContext &Context) const { + Region &CurRegion = Context.CurRegion; + + TerminatorInst *TI = BB.getTerminator(); + + // Return instructions are only valid if the region is the top level region. + if (isa(TI) && !CurRegion.getExit() && TI->getNumOperands() == 0) + return true; + + Value *Condition = getConditionFromTerminator(TI); + + if (!Condition) + return invalid(Context, /*Assert=*/true, &BB); + + // UndefValue is not allowed as condition. + if (isa(Condition)) + return invalid(Context, /*Assert=*/true, TI, &BB); + + // Constant conditions are always affine. + if (isa(Condition)) + return true; + + if (BranchInst *BI = dyn_cast(TI)) + return isValidBranch(BB, BI, Condition, Context); + + SwitchInst *SI = dyn_cast(TI); + assert(SI && "Terminator was neither branch nor switch"); + + return isValidSwitch(BB, SI, Condition, Context); +} + bool ScopDetection::isValidCallInst(CallInst &CI) { if (CI.doesNotReturn()) return false; Index: polly/trunk/lib/Analysis/ScopDetectionDiagnostic.cpp =================================================================== --- polly/trunk/lib/Analysis/ScopDetectionDiagnostic.cpp +++ polly/trunk/lib/Analysis/ScopDetectionDiagnostic.cpp @@ -141,18 +141,18 @@ } //===----------------------------------------------------------------------===// -// ReportNonBranchTerminator. +// ReportInvalidTerminator. -std::string ReportNonBranchTerminator::getMessage() const { - return ("Non branch instruction terminates BB: " + BB->getName()).str(); +std::string ReportInvalidTerminator::getMessage() const { + return ("Invalid instruction terminates BB: " + BB->getName()).str(); } -const DebugLoc &ReportNonBranchTerminator::getDebugLoc() const { +const DebugLoc &ReportInvalidTerminator::getDebugLoc() const { return BB->getTerminator()->getDebugLoc(); } -bool ReportNonBranchTerminator::classof(const RejectReason *RR) { - return RR->getKind() == rrkNonBranchTerminator; +bool ReportInvalidTerminator::classof(const RejectReason *RR) { + return RR->getKind() == rrkInvalidTerminator; } //===----------------------------------------------------------------------===// Index: polly/trunk/lib/Analysis/ScopInfo.cpp =================================================================== --- polly/trunk/lib/Analysis/ScopInfo.cpp +++ polly/trunk/lib/Analysis/ScopInfo.cpp @@ -914,8 +914,20 @@ return std::make_pair(UnboundedParts, BoundedParts); } +/// @brief Set the dimension Ids from @p From in @p To. +static __isl_give isl_set *setDimensionIds(__isl_keep isl_set *From, + __isl_take isl_set *To) { + for (unsigned u = 0, e = isl_set_n_dim(From); u < e; u++) { + isl_id *DimId = isl_set_get_dim_id(From, isl_dim_set, u); + To = isl_set_set_dim_id(To, isl_dim_set, u, DimId); + } + return To; +} + +/// @brief Create the conditions under which @p L @p Pred @p R is true. static __isl_give isl_set *buildConditionSet(ICmpInst::Predicate Pred, - isl_pw_aff *L, isl_pw_aff *R) { + __isl_take isl_pw_aff *L, + __isl_take isl_pw_aff *R) { switch (Pred) { case ICmpInst::ICMP_EQ: return isl_pw_aff_eq_set(L, R); @@ -942,21 +954,82 @@ } } -/// @brief Build the conditions sets for the branch @p BI in the @p Domain. +/// @brief Create the conditions under which @p L @p Pred @p R is true. +/// +/// Helper function that will make sure the dimensions of the result have the +/// same isl_id's as the @p Domain. +static __isl_give isl_set *buildConditionSet(ICmpInst::Predicate Pred, + __isl_take isl_pw_aff *L, + __isl_take isl_pw_aff *R, + __isl_keep isl_set *Domain) { + isl_set *ConsequenceCondSet = buildConditionSet(Pred, L, R); + return setDimensionIds(Domain, ConsequenceCondSet); +} + +/// @brief Build the conditions sets for the switch @p SI in the @p Domain. +/// +/// This will fill @p ConditionSets with the conditions under which control +/// will be moved from @p SI to its successors. Hence, @p ConditionSets will +/// have as many elements as @p SI has successors. +static void +buildConditionSets(Scop &S, SwitchInst *SI, Loop *L, __isl_keep isl_set *Domain, + SmallVectorImpl<__isl_give isl_set *> &ConditionSets) { + + Value *Condition = getConditionFromTerminator(SI); + assert(Condition && "No condition for switch"); + + ScalarEvolution &SE = *S.getSE(); + BasicBlock *BB = SI->getParent(); + isl_pw_aff *LHS, *RHS; + LHS = S.getPwAff(SE.getSCEVAtScope(Condition, L), BB); + + unsigned NumSuccessors = SI->getNumSuccessors(); + ConditionSets.resize(NumSuccessors); + for (auto &Case : SI->cases()) { + unsigned Idx = Case.getSuccessorIndex(); + ConstantInt *CaseValue = Case.getCaseValue(); + + RHS = S.getPwAff(SE.getSCEV(CaseValue), BB); + isl_set *CaseConditionSet = + buildConditionSet(ICmpInst::ICMP_EQ, isl_pw_aff_copy(LHS), RHS, Domain); + ConditionSets[Idx] = isl_set_coalesce( + isl_set_intersect(CaseConditionSet, isl_set_copy(Domain))); + } + + assert(ConditionSets[0] == nullptr && "Default condition set was set"); + isl_set *ConditionSetUnion = isl_set_copy(ConditionSets[1]); + for (unsigned u = 2; u < NumSuccessors; u++) + ConditionSetUnion = + isl_set_union(ConditionSetUnion, isl_set_copy(ConditionSets[u])); + ConditionSets[0] = setDimensionIds( + Domain, isl_set_subtract(isl_set_copy(Domain), ConditionSetUnion)); + + S.markAsOptimized(); + isl_pw_aff_free(LHS); +} + +/// @brief Build the conditions sets for the terminator @p TI in the @p Domain. /// /// This will fill @p ConditionSets with the conditions under which control -/// will be moved from @p BI to its successors. Hence, @p ConditionSets will -/// have as many elements as @p BI has successors. +/// will be moved from @p TI to its successors. Hence, @p ConditionSets will +/// have as many elements as @p TI has successors. static void -buildConditionSets(Scop &S, BranchInst *BI, Loop *L, __isl_keep isl_set *Domain, +buildConditionSets(Scop &S, TerminatorInst *TI, Loop *L, + __isl_keep isl_set *Domain, SmallVectorImpl<__isl_give isl_set *> &ConditionSets) { - if (BI->isUnconditional()) { + if (SwitchInst *SI = dyn_cast(TI)) + return buildConditionSets(S, SI, L, Domain, ConditionSets); + + assert(isa(TI) && "Terminator was neither branch nor switch."); + + if (TI->getNumSuccessors() == 1) { ConditionSets.push_back(isl_set_copy(Domain)); return; } - Value *Condition = BI->getCondition(); + Value *Condition = getConditionFromTerminator(TI); + assert(Condition && "No condition for Terminator"); isl_set *ConsequenceCondSet = nullptr; if (auto *CCond = dyn_cast(Condition)) { @@ -970,17 +1043,12 @@ "Condition of exiting branch was neither constant nor ICmp!"); ScalarEvolution &SE = *S.getSE(); - BasicBlock *BB = BI->getParent(); + BasicBlock *BB = TI->getParent(); isl_pw_aff *LHS, *RHS; LHS = S.getPwAff(SE.getSCEVAtScope(ICond->getOperand(0), L), BB); RHS = S.getPwAff(SE.getSCEVAtScope(ICond->getOperand(1), L), BB); - ConsequenceCondSet = buildConditionSet(ICond->getPredicate(), LHS, RHS); - - for (unsigned u = 0, e = isl_set_n_dim(Domain); u < e; u++) { - isl_id *DimId = isl_set_get_dim_id(Domain, isl_dim_set, u); - ConsequenceCondSet = - isl_set_set_dim_id(ConsequenceCondSet, isl_dim_set, u, DimId); - } + ConsequenceCondSet = + buildConditionSet(ICond->getPredicate(), LHS, RHS, Domain); } assert(ConsequenceCondSet); @@ -1551,13 +1619,13 @@ } /// @brief Return the @p idx'th block that is executed after @p RN. -static inline BasicBlock *getRegionNodeSuccessor(RegionNode *RN, BranchInst *BI, - unsigned idx) { +static inline BasicBlock * +getRegionNodeSuccessor(RegionNode *RN, TerminatorInst *TI, unsigned idx) { if (RN->isSubRegion()) { assert(idx == 0); return RN->getNodeAs()->getExit(); } - return BI->getSuccessor(idx); + return TI->getSuccessor(idx); } /// @brief Return the smallest loop surrounding @p RN. @@ -1681,20 +1749,20 @@ // node. If it is a non-affine subregion we will always execute the single // exit node, hence the single entry node domain is the condition set. For // basic blocks we use the helper function buildConditionSets. - SmallVector ConditionSets; - BranchInst *BI = cast(TI); + SmallVector ConditionSets; if (RN->isSubRegion()) ConditionSets.push_back(isl_set_copy(Domain)); else - buildConditionSets(*this, BI, BBLoop, Domain, ConditionSets); + buildConditionSets(*this, TI, BBLoop, Domain, ConditionSets); // Now iterate over the successors and set their initial domain based on // their condition set. We skip back edges here and have to be careful when // we leave a loop not to keep constraints over a dimension that doesn't // exist anymore. + assert(RN->isSubRegion() || TI->getNumSuccessors() == ConditionSets.size()); for (unsigned u = 0, e = ConditionSets.size(); u < e; u++) { - BasicBlock *SuccBB = getRegionNodeSuccessor(RN, BI, u); isl_set *CondSet = ConditionSets[u]; + BasicBlock *SuccBB = getRegionNodeSuccessor(RN, TI, u); // Skip back edges. if (DT.dominates(SuccBB, BB)) { @@ -1915,13 +1983,14 @@ isl_set *LatchBBDom = DomainMap[LatchBB]; isl_set *BackedgeCondition = nullptr; - BranchInst *BI = cast(LatchBB->getTerminator()); - if (BI->isUnconditional()) + TerminatorInst *TI = LatchBB->getTerminator(); + BranchInst *BI = dyn_cast(TI); + if (BI && BI->isUnconditional()) BackedgeCondition = isl_set_copy(LatchBBDom); else { - SmallVector ConditionSets; + SmallVector ConditionSets; int idx = BI->getSuccessor(0) != HeaderBB; - buildConditionSets(*this, BI, L, LatchBBDom, ConditionSets); + buildConditionSets(*this, TI, L, LatchBBDom, ConditionSets); // Free the non back edge condition set as we do not need it. isl_set_free(ConditionSets[1 - idx]); Index: polly/trunk/lib/CodeGen/BlockGenerators.cpp =================================================================== --- polly/trunk/lib/CodeGen/BlockGenerators.cpp +++ polly/trunk/lib/CodeGen/BlockGenerators.cpp @@ -1074,15 +1074,13 @@ continue; } - BranchInst *BI = cast(TI); - Instruction *BICopy = BBCopy->getTerminator(); ValueMapT &RegionMap = RegionMaps[BBCopy]; RegionMap.insert(BlockMap.begin(), BlockMap.end()); Builder.SetInsertPoint(BICopy); - copyInstScalar(Stmt, BI, RegionMap, LTS); + copyInstScalar(Stmt, TI, RegionMap, LTS); BICopy->eraseFromParent(); } Index: polly/trunk/lib/Support/ScopHelper.cpp =================================================================== --- polly/trunk/lib/Support/ScopHelper.cpp +++ polly/trunk/lib/Support/ScopHelper.cpp @@ -345,3 +345,17 @@ return false; } + +Value *polly::getConditionFromTerminator(TerminatorInst *TI) { + if (BranchInst *BR = dyn_cast(TI)) { + if (BR->isUnconditional()) + return ConstantInt::getTrue(Type::getInt1Ty(TI->getContext())); + + return BR->getCondition(); + } + + if (SwitchInst *SI = dyn_cast(TI)) + return SI->getCondition(); + + return nullptr; +} Index: polly/trunk/test/Isl/CodeGen/non-affine-switch.ll =================================================================== --- polly/trunk/test/Isl/CodeGen/non-affine-switch.ll +++ polly/trunk/test/Isl/CodeGen/non-affine-switch.ll @@ -0,0 +1,67 @@ +; RUN: opt %loadPolly -polly-detect-unprofitable -polly-no-early-exit \ +; RUN: -S -polly-codegen < %s | FileCheck %s +; +; void f(int *A, int N) { +; for (int i = 0; i < N; i++) +; switch (A[i]) { +; case 0: +; A[i] += 1; +; break; +; case 1: +; A[i] += 2; +; break; +; } +; } +; +; CHECK: polly.stmt.for.body: +; CHECK: %scevgep = getelementptr i32, i32* %A, i64 %polly.indvar +; CHECK: %tmp1_p_scalar_ = load i32, i32* %scevgep, align 4 +; CHECK: switch i32 %tmp1_p_scalar_, label %polly.stmt.sw.epilog.exit [ +; CHECK: i32 0, label %polly.stmt.sw.bb +; CHECK: i32 1, label %polly.stmt.sw.bb.3 +; CHECK: ] +; +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define void @f(i32* %A, i32 %N) { +entry: + %tmp = sext i32 %N to i64 + br label %for.cond + +for.cond: ; preds = %for.inc, %entry + %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ] + %cmp = icmp slt i64 %indvars.iv, %tmp + br i1 %cmp, label %for.body, label %for.end + +for.body: ; preds = %for.cond + %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv + %tmp1 = load i32, i32* %arrayidx, align 4 + switch i32 %tmp1, label %sw.epilog [ + i32 0, label %sw.bb + i32 1, label %sw.bb.3 + ] + +sw.bb: ; preds = %for.body + %arrayidx2 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv + %tmp2 = load i32, i32* %arrayidx2, align 4 + %add = add nsw i32 %tmp2, 1 + store i32 %add, i32* %arrayidx2, align 4 + br label %sw.epilog + +sw.bb.3: ; preds = %for.body + %arrayidx5 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv + %tmp3 = load i32, i32* %arrayidx5, align 4 + %add6 = add nsw i32 %tmp3, 2 + store i32 %add6, i32* %arrayidx5, align 4 + br label %sw.epilog + +sw.epilog: ; preds = %sw.bb.3, %sw.bb, %for.body + br label %for.inc + +for.inc: ; preds = %sw.epilog + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + br label %for.cond + +for.end: ; preds = %for.cond + ret void +} Index: polly/trunk/test/Isl/CodeGen/switch-in-non-affine-region.ll =================================================================== --- polly/trunk/test/Isl/CodeGen/switch-in-non-affine-region.ll +++ polly/trunk/test/Isl/CodeGen/switch-in-non-affine-region.ll @@ -0,0 +1,77 @@ +; RUN: opt %loadPolly -polly-detect-unprofitable -polly-no-early-exit \ +; RUN: -S -polly-codegen < %s | FileCheck %s +; +; void f(int *A, int N) { +; for (int i = 0; i < N; i++) +; if (A[i]) +; switch (i % 4) { +; case 0: +; A[i] += 1; +; break; +; case 1: +; A[i] += 2; +; break; +; } +; } +; +; CHECK: polly.stmt.if.then: +; CHECK: %1 = trunc i64 %polly.indvar to i32 +; CHECK: %p_rem = srem i32 %1, 4 +; CHECK: switch i32 %p_rem, label %polly.stmt.sw.epilog [ +; CHECK: i32 0, label %polly.stmt.sw.bb +; CHECK: i32 1, label %polly.stmt.sw.bb.3 +; CHECK: ] +; +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define void @f(i32* %A, i32 %N) { +entry: + %tmp = sext i32 %N to i64 + br label %for.cond + +for.cond: ; preds = %for.inc, %entry + %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ] + %cmp = icmp slt i64 %indvars.iv, %tmp + br i1 %cmp, label %for.body, label %for.end + +for.body: ; preds = %for.cond + %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv + %tmp1 = load i32, i32* %arrayidx, align 4 + %tobool = icmp eq i32 %tmp1, 0 + br i1 %tobool, label %if.end, label %if.then + +if.then: ; preds = %for.body + %tmp2 = trunc i64 %indvars.iv to i32 + %rem = srem i32 %tmp2, 4 + switch i32 %rem, label %sw.epilog [ + i32 0, label %sw.bb + i32 1, label %sw.bb.3 + ] + +sw.bb: ; preds = %if.then + %arrayidx2 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv + %tmp3 = load i32, i32* %arrayidx2, align 4 + %add = add nsw i32 %tmp3, 1 + store i32 %add, i32* %arrayidx2, align 4 + br label %sw.epilog + +sw.bb.3: ; preds = %if.then + %arrayidx5 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv + %tmp4 = load i32, i32* %arrayidx5, align 4 + %add6 = add nsw i32 %tmp4, 2 + store i32 %add6, i32* %arrayidx5, align 4 + br label %sw.epilog + +sw.epilog: ; preds = %sw.bb.3, %sw.bb, %if.then + br label %if.end + +if.end: ; preds = %for.body, %sw.epilog + br label %for.inc + +for.inc: ; preds = %if.end + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + br label %for.cond + +for.end: ; preds = %for.cond + ret void +} Index: polly/trunk/test/ScopInfo/switch-1.ll =================================================================== --- polly/trunk/test/ScopInfo/switch-1.ll +++ polly/trunk/test/ScopInfo/switch-1.ll @@ -0,0 +1,111 @@ +; RUN: opt %loadPolly -polly-detect-unprofitable -polly-scops -analyze < %s | FileCheck %s +; RUN: opt %loadPolly -polly-detect-unprofitable -polly-ast -analyze < %s | FileCheck %s --check-prefix=AST +; +; void f(int *A, int N) { +; for (int i = 0; i < N; i++) +; switch (i % 4) { +; case 0: +; break; +; case 1: +; A[i] += 1; +; break; +; case 2: +; A[i] += 2; +; break; +; case 3: +; A[i] += 3; +; break; +; } +; } +; +; CHECK: Statements { +; CHECK: Stmt_sw_bb_6 +; CHECK: Domain := +; CHECK: [N] -> { Stmt_sw_bb_6[i0] : exists (e0 = floor((-3 + i0)/4): 4e0 = -3 + i0 and i0 >= 0 and i0 <= -1 + N) }; +; CHECK: Schedule := +; CHECK: [N] -> { Stmt_sw_bb_6[i0] -> [i0, 0] }; +; CHECK: Stmt_sw_bb_2 +; CHECK: Domain := +; CHECK: [N] -> { Stmt_sw_bb_2[i0] : exists (e0 = floor((-2 + i0)/4): 4e0 = -2 + i0 and i0 >= 2 and i0 <= -1 + N) }; +; CHECK: Schedule := +; CHECK: [N] -> { Stmt_sw_bb_2[i0] -> [i0, 1] }; +; CHECK: Stmt_sw_bb_1 +; CHECK: Domain := +; CHECK: [N] -> { Stmt_sw_bb_1[i0] : exists (e0 = floor((-1 + i0)/4): 4e0 = -1 + i0 and i0 >= 1 and i0 <= -1 + N) }; +; CHECK: Schedule := +; CHECK: [N] -> { Stmt_sw_bb_1[i0] -> [i0, 2] }; +; CHECK: } +; +; +; AST: if (1) +; +; AST: { +; AST: for (int c0 = 1; c0 < N - 2; c0 += 4) { +; AST: Stmt_sw_bb_1(c0); +; AST: Stmt_sw_bb_2(c0 + 1); +; AST: Stmt_sw_bb_6(c0 + 2); +; AST: } +; AST: if (N >= 2) +; AST: if (N % 4 >= 2) { +; AST: Stmt_sw_bb_1(-(N % 4) + N + 1); +; AST: if ((N - 3) % 4 == 0) +; AST: Stmt_sw_bb_2(N - 1); +; AST: } +; AST: } +; +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define void @f(i32* %A, i32 %N) { +entry: + %tmp = sext i32 %N to i64 + br label %for.cond + +for.cond: ; preds = %for.inc, %entry + %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ] + %cmp = icmp slt i64 %indvars.iv, %tmp + br i1 %cmp, label %for.body, label %for.end + +for.body: ; preds = %for.cond + %tmp1 = trunc i64 %indvars.iv to i32 + %rem = srem i32 %tmp1, 4 + switch i32 %rem, label %sw.epilog [ + i32 0, label %sw.bb + i32 1, label %sw.bb.1 + i32 2, label %sw.bb.2 + i32 3, label %sw.bb.6 + ] + +sw.bb: ; preds = %for.body + br label %sw.epilog + +sw.bb.1: ; preds = %for.body + %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv + %tmp2 = load i32, i32* %arrayidx, align 4 + %add = add nsw i32 %tmp2, 1 + store i32 %add, i32* %arrayidx, align 4 + br label %sw.epilog + +sw.bb.2: ; preds = %for.body + %arrayidx4 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv + %tmp3 = load i32, i32* %arrayidx4, align 4 + %add5 = add nsw i32 %tmp3, 2 + store i32 %add5, i32* %arrayidx4, align 4 + br label %sw.epilog + +sw.bb.6: ; preds = %for.body + %arrayidx8 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv + %tmp4 = load i32, i32* %arrayidx8, align 4 + %add9 = add nsw i32 %tmp4, 3 + store i32 %add9, i32* %arrayidx8, align 4 + br label %sw.epilog + +sw.epilog: ; preds = %sw.bb.6, %sw.bb.2, %sw.bb.1, %sw.bb, %for.body + br label %for.inc + +for.inc: ; preds = %sw.epilog + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + br label %for.cond + +for.end: ; preds = %for.cond + ret void +} Index: polly/trunk/test/ScopInfo/switch-2.ll =================================================================== --- polly/trunk/test/ScopInfo/switch-2.ll +++ polly/trunk/test/ScopInfo/switch-2.ll @@ -0,0 +1,98 @@ +; RUN: opt %loadPolly -polly-detect-unprofitable -polly-scops -analyze < %s | FileCheck %s +; RUN: opt %loadPolly -polly-detect-unprofitable -polly-ast -analyze < %s | FileCheck %s --check-prefix=AST +; +; void f(int *A, int N) { +; for (int i = 0; i < N; i++) +; switch (i % 4) { +; case 0: +; A[i] += 1; +; break; +; case 1: +; break; +; case 2: +; A[i] += 2; +; break; +; case 3: +; break; +; } +; } +; +; CHECK: Statements { +; CHECK-NOT: Stmt_sw_bb1 +; CHECK: Stmt_sw_bb_2 +; CHECK: Domain := +; CHECK: [N] -> { Stmt_sw_bb_2[i0] : exists (e0 = floor((-2 + i0)/4): 4e0 = -2 + i0 and i0 >= 2 and i0 <= -1 + N) }; +; CHECK: Schedule := +; CHECK: [N] -> { Stmt_sw_bb_2[i0] -> [i0, 0] }; +; CHECK-NOT: Stmt_sw_bb1 +; CHECK: Stmt_sw_bb +; CHECK: Domain := +; CHECK: [N] -> { Stmt_sw_bb[i0] : exists (e0 = floor((i0)/4): 4e0 = i0 and i0 >= 0 and i0 <= -1 + N) }; +; CHECK: Schedule := +; CHECK: [N] -> { Stmt_sw_bb[i0] -> [i0, 1] }; +; CHECK-NOT: Stmt_sw_bb1 +; CHECK: } +; +; AST: if (1) +; +; AST: for (int c0 = 0; c0 < N; c0 += 4) { +; AST: Stmt_sw_bb(c0); +; AST: if (N >= c0 + 3) +; AST: Stmt_sw_bb_2(c0 + 2); +; AST: } +; +; AST: else +; AST: { /* original code */ } +; +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define void @f(i32* %A, i32 %N) { +entry: + %tmp = sext i32 %N to i64 + br label %for.cond + +for.cond: ; preds = %for.inc, %entry + %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ] + %cmp = icmp slt i64 %indvars.iv, %tmp + br i1 %cmp, label %for.body, label %for.end + +for.body: ; preds = %for.cond + %tmp1 = trunc i64 %indvars.iv to i32 + %rem = srem i32 %tmp1, 4 + switch i32 %rem, label %sw.epilog [ + i32 0, label %sw.bb + i32 1, label %sw.bb.1 + i32 2, label %sw.bb.2 + i32 3, label %sw.bb.6 + ] + +sw.bb: ; preds = %for.body + %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv + %tmp2 = load i32, i32* %arrayidx, align 4 + %add = add nsw i32 %tmp2, 1 + store i32 %add, i32* %arrayidx, align 4 + br label %sw.epilog + +sw.bb.1: ; preds = %for.body + br label %sw.epilog + +sw.bb.2: ; preds = %for.body + %arrayidx4 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv + %tmp3 = load i32, i32* %arrayidx4, align 4 + %add5 = add nsw i32 %tmp3, 2 + store i32 %add5, i32* %arrayidx4, align 4 + br label %sw.epilog + +sw.bb.6: ; preds = %for.body + br label %sw.epilog + +sw.epilog: ; preds = %sw.bb.6, %sw.bb.2, %sw.bb.1, %sw.bb, %for.body + br label %for.inc + +for.inc: ; preds = %sw.epilog + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + br label %for.cond + +for.end: ; preds = %for.cond + ret void +} Index: polly/trunk/test/ScopInfo/switch-3.ll =================================================================== --- polly/trunk/test/ScopInfo/switch-3.ll +++ polly/trunk/test/ScopInfo/switch-3.ll @@ -0,0 +1,119 @@ +; RUN: opt %loadPolly -polly-detect-unprofitable -polly-scops -analyze < %s | FileCheck %s +; RUN: opt %loadPolly -polly-detect-unprofitable -polly-ast -analyze < %s | FileCheck %s --check-prefix=AST +; +; void f(int *A, int N) { +; for (int i = 0; i < N; i++) +; switch (i % 4) { +; case 0: +; A[i] += 1; +; case 1: +; A[i] += 2; +; break; +; case 2: +; A[i] += 3; +; case 3: +; A[i] += 4; +; break; +; } +; } +; +; CHECK: Statements { +; CHECK: Stmt_sw_bb_5 +; CHECK: Domain := +; CHECK: [N] -> { Stmt_sw_bb_5[i0] : exists (e0 = floor((-2 + i0)/4): 4e0 = -2 + i0 and i0 >= 2 and i0 <= -1 + N) }; +; CHECK: Schedule := +; CHECK: [N] -> { Stmt_sw_bb_5[i0] -> [i0, 0] }; +; CHECK: Stmt_sw_bb_9 +; CHECK: Domain := +; CHECK: [N] -> { Stmt_sw_bb_9[i0] : exists (e0 = floor((i0)/4): i0 >= 0 and i0 <= -1 + N and 4e0 >= -3 + i0 and 4e0 <= -2 + i0) }; +; CHECK: Schedule := +; CHECK: [N] -> { Stmt_sw_bb_9[i0] -> [i0, 1] }; +; CHECK: Stmt_sw_bb +; CHECK: Domain := +; CHECK: [N] -> { Stmt_sw_bb[i0] : exists (e0 = floor((i0)/4): 4e0 = i0 and i0 >= 0 and i0 <= -1 + N) }; +; CHECK: Schedule := +; CHECK: [N] -> { Stmt_sw_bb[i0] -> [i0, 2] }; +; CHECK: Stmt_sw_bb_1 +; CHECK: Domain := +; CHECK: [N] -> { Stmt_sw_bb_1[i0] : exists (e0 = floor((2 + i0)/4): i0 >= 0 and i0 <= -1 + N and 4e0 >= -1 + i0 and 4e0 <= i0) }; +; CHECK: Schedule := +; CHECK: [N] -> { Stmt_sw_bb_1[i0] -> [i0, 3] }; +; CHECK: } +; +; AST: if (1) +; +; AST: for (int c0 = 0; c0 < N; c0 += 1) { +; AST: if ((c0 - 2) % 4 == 0) +; AST: Stmt_sw_bb_5(c0); +; AST: if (c0 % 4 >= 2) { +; AST: Stmt_sw_bb_9(c0); +; AST: } else { +; AST: if (c0 % 4 == 0) +; AST: Stmt_sw_bb(c0); +; AST: Stmt_sw_bb_1(c0); +; AST: } +; AST: } +; +; AST: else +; AST: { /* original code */ } +; +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define void @f(i32* %A, i32 %N) { +entry: + %tmp = sext i32 %N to i64 + br label %for.cond + +for.cond: ; preds = %for.inc, %entry + %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ] + %cmp = icmp slt i64 %indvars.iv, %tmp + br i1 %cmp, label %for.body, label %for.end + +for.body: ; preds = %for.cond + %tmp1 = trunc i64 %indvars.iv to i32 + %rem = srem i32 %tmp1, 4 + switch i32 %rem, label %sw.epilog [ + i32 0, label %sw.bb + i32 1, label %sw.bb.1 + i32 2, label %sw.bb.5 + i32 3, label %sw.bb.9 + ] + +sw.bb: ; preds = %for.body + %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv + %tmp2 = load i32, i32* %arrayidx, align 4 + %add = add nsw i32 %tmp2, 1 + store i32 %add, i32* %arrayidx, align 4 + br label %sw.bb.1 + +sw.bb.1: ; preds = %sw.bb, %for.body + %arrayidx3 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv + %tmp3 = load i32, i32* %arrayidx3, align 4 + %add4 = add nsw i32 %tmp3, 2 + store i32 %add4, i32* %arrayidx3, align 4 + br label %sw.epilog + +sw.bb.5: ; preds = %for.body + %arrayidx7 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv + %tmp4 = load i32, i32* %arrayidx7, align 4 + %add8 = add nsw i32 %tmp4, 3 + store i32 %add8, i32* %arrayidx7, align 4 + br label %sw.bb.9 + +sw.bb.9: ; preds = %sw.bb.5, %for.body + %arrayidx11 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv + %tmp5 = load i32, i32* %arrayidx11, align 4 + %add12 = add nsw i32 %tmp5, 4 + store i32 %add12, i32* %arrayidx11, align 4 + br label %sw.epilog + +sw.epilog: ; preds = %sw.bb.9, %sw.bb.1, %for.body + br label %for.inc + +for.inc: ; preds = %sw.epilog + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + br label %for.cond + +for.end: ; preds = %for.cond + ret void +} Index: polly/trunk/test/ScopInfo/switch-4.ll =================================================================== --- polly/trunk/test/ScopInfo/switch-4.ll +++ polly/trunk/test/ScopInfo/switch-4.ll @@ -0,0 +1,143 @@ +; RUN: opt %loadPolly -polly-detect-unprofitable -polly-scops -analyze < %s | FileCheck %s +; RUN: opt %loadPolly -polly-detect-unprofitable -polly-ast -analyze < %s | FileCheck %s --check-prefix=AST +; +; void f(int *A, int N) { +; for (int i = 0; i < N; i++) +; switch (i % 4) { +; case 0: +; A[i] += 1; +; break; +; case 1: +; A[i] += 2; +; break; +; case 2: +; A[i] += 3; +; break; +; case 3: +; A[i] += 4; +; break; +; default: +; A[i - 1] += A[i + 1]; +; } +; } +; +; CHECK: Statements { +; CHECK: Stmt_sw_bb_9 +; CHECK: Domain := +; CHECK: [N] -> { Stmt_sw_bb_9[i0] : exists (e0 = floor((-3 + i0)/4): 4e0 = -3 + i0 and i0 >= 0 and i0 <= -1 + N) }; +; CHECK: Schedule := +; CHECK: [N] -> { Stmt_sw_bb_9[i0] -> [i0, 0] }; +; CHECK: Stmt_sw_bb_5 +; CHECK: Domain := +; CHECK: [N] -> { Stmt_sw_bb_5[i0] : exists (e0 = floor((-2 + i0)/4): 4e0 = -2 + i0 and i0 >= 2 and i0 <= -1 + N) }; +; CHECK: Schedule := +; CHECK: [N] -> { Stmt_sw_bb_5[i0] -> [i0, 1] }; +; CHECK: Stmt_sw_bb_1 +; CHECK: Domain := +; CHECK: [N] -> { Stmt_sw_bb_1[i0] : exists (e0 = floor((-1 + i0)/4): 4e0 = -1 + i0 and i0 >= 1 and i0 <= -1 + N) }; +; CHECK: Schedule := +; CHECK: [N] -> { Stmt_sw_bb_1[i0] -> [i0, 2] }; +; CHECK: Stmt_sw_bb +; CHECK: Domain := +; CHECK: [N] -> { Stmt_sw_bb[i0] : exists (e0 = floor((i0)/4): 4e0 = i0 and i0 >= 0 and i0 <= -1 + N) }; +; CHECK: Schedule := +; CHECK: [N] -> { Stmt_sw_bb[i0] -> [i0, 3] }; +; CHECK: Stmt_sw_default +; CHECK: Domain := +; CHECK: [N] -> { Stmt_sw_default[i0] : 1 = 0 }; +; CHECK: } +; +; AST: if (1) +; +; AST: { +; AST: for (int c0 = 0; c0 < N - 3; c0 += 4) { +; AST: Stmt_sw_bb(c0); +; AST: Stmt_sw_bb_1(c0 + 1); +; AST: Stmt_sw_bb_5(c0 + 2); +; AST: Stmt_sw_bb_9(c0 + 3); +; AST: } +; AST: if (N >= 1) +; AST: if (N % 4 >= 1) { +; AST: Stmt_sw_bb(-((N - 1) % 4) + N - 1); +; AST: if (N % 4 >= 2) { +; AST: Stmt_sw_bb_1(-((N - 1) % 4) + N); +; AST: if ((N - 3) % 4 == 0) +; AST: Stmt_sw_bb_5(N - 1); +; AST: } +; AST: } +; AST: } +; +; AST: else +; AST: { /* original code */ } +; +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define void @f(i32* %A, i32 %N) { +entry: + %tmp = sext i32 %N to i64 + br label %for.cond + +for.cond: ; preds = %for.inc, %entry + %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ] + %cmp = icmp slt i64 %indvars.iv, %tmp + br i1 %cmp, label %for.body, label %for.end + +for.body: ; preds = %for.cond + %tmp3 = trunc i64 %indvars.iv to i32 + %rem = srem i32 %tmp3, 4 + switch i32 %rem, label %sw.default [ + i32 0, label %sw.bb + i32 1, label %sw.bb.1 + i32 2, label %sw.bb.5 + i32 3, label %sw.bb.9 + ] + +sw.bb: ; preds = %for.body + %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv + %tmp4 = load i32, i32* %arrayidx, align 4 + %add = add nsw i32 %tmp4, 1 + store i32 %add, i32* %arrayidx, align 4 + br label %sw.epilog + +sw.bb.1: ; preds = %for.body + %arrayidx3 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv + %tmp5 = load i32, i32* %arrayidx3, align 4 + %add4 = add nsw i32 %tmp5, 2 + store i32 %add4, i32* %arrayidx3, align 4 + br label %sw.epilog + +sw.bb.5: ; preds = %for.body + %arrayidx7 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv + %tmp6 = load i32, i32* %arrayidx7, align 4 + %add8 = add nsw i32 %tmp6, 3 + store i32 %add8, i32* %arrayidx7, align 4 + br label %sw.epilog + +sw.bb.9: ; preds = %for.body + %arrayidx11 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv + %tmp7 = load i32, i32* %arrayidx11, align 4 + %add12 = add nsw i32 %tmp7, 4 + store i32 %add12, i32* %arrayidx11, align 4 + br label %sw.epilog + +sw.default: ; preds = %for.body + %tmp8 = add nuw nsw i64 %indvars.iv, 1 + %arrayidx15 = getelementptr inbounds i32, i32* %A, i64 %tmp8 + %tmp9 = load i32, i32* %arrayidx15, align 4 + %tmp10 = add nsw i64 %indvars.iv, -1 + %arrayidx17 = getelementptr inbounds i32, i32* %A, i64 %tmp10 + %tmp11 = load i32, i32* %arrayidx17, align 4 + %add18 = add nsw i32 %tmp11, %tmp9 + store i32 %add18, i32* %arrayidx17, align 4 + br label %sw.epilog + +sw.epilog: ; preds = %sw.default, %sw.bb.9, %sw.bb.5, %sw.bb.1, %sw.bb + br label %for.inc + +for.inc: ; preds = %sw.epilog + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + br label %for.cond + +for.end: ; preds = %for.cond + ret void +} Index: polly/trunk/test/ScopInfo/switch-5.ll =================================================================== --- polly/trunk/test/ScopInfo/switch-5.ll +++ polly/trunk/test/ScopInfo/switch-5.ll @@ -0,0 +1,74 @@ +; RUN: opt %loadPolly -polly-detect-unprofitable -polly-scops -analyze < %s | FileCheck %s +; RUN: opt %loadPolly -polly-detect-unprofitable -polly-ast -analyze < %s | FileCheck %s --check-prefix=AST +; +; void f(int *A, int *B, int N) { +; for (int i = 0; i < N; i++) { +; A[i]++; +; switch (N) { +; case 0: +; B[i]++; +; break; +; default: +; return; +; } +; } +; } +; +; CHECK: Statements { +; CHECK: Stmt_for_body +; CHECK: Domain := +; CHECK: [N] -> { Stmt_for_body[0] : N >= 1 }; +; CHECK: Schedule := +; CHECK: [N] -> { Stmt_for_body[i0] -> [0, 0] }; +; CHECK: Stmt_sw_bb +; CHECK: Domain := +; CHECK: [N] -> { Stmt_sw_bb[i0] : 1 = 0 }; +; CHECK: } +; +; AST: if (N >= 1) +; AST: Stmt_for_body(0); +; +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define void @f(i32* %A, i32* %B, i32 %N) { +entry: + %tmp = sext i32 %N to i64 + br label %for.cond + +for.cond: ; preds = %for.inc, %entry + %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ] + %cmp = icmp slt i64 %indvars.iv, %tmp + br i1 %cmp, label %for.body, label %for.end.loopexit + +for.body: ; preds = %for.cond + %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv + %tmp1 = load i32, i32* %arrayidx, align 4 + %inc = add nsw i32 %tmp1, 1 + store i32 %inc, i32* %arrayidx, align 4 + switch i32 %N, label %sw.default [ + i32 0, label %sw.bb + ] + +sw.bb: ; preds = %for.body + %arrayidx2 = getelementptr inbounds i32, i32* %B, i64 %indvars.iv + %tmp2 = load i32, i32* %arrayidx2, align 4 + %inc3 = add nsw i32 %tmp2, 1 + store i32 %inc3, i32* %arrayidx2, align 4 + br label %sw.epilog + +sw.default: ; preds = %for.body + br label %for.end + +sw.epilog: ; preds = %sw.bb + br label %for.inc + +for.inc: ; preds = %sw.epilog + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + br label %for.cond + +for.end.loopexit: ; preds = %for.cond + br label %for.end + +for.end: ; preds = %for.end.loopexit, %sw.default + ret void +} Index: polly/trunk/test/ScopInfo/switch-6.ll =================================================================== --- polly/trunk/test/ScopInfo/switch-6.ll +++ polly/trunk/test/ScopInfo/switch-6.ll @@ -0,0 +1,118 @@ +; RUN: opt %loadPolly -polly-detect-unprofitable -polly-scops -analyze < %s | FileCheck %s +; RUN: opt %loadPolly -polly-detect-unprofitable -polly-ast -analyze < %s | FileCheck %s --check-prefix=AST +; +; void f(int *A, int N) { +; for (int i = 0; i < N; i++) { +; switch (i) { +; case 0: +; A[i] += 1; +; break; +; case 1: +; A[i] += 2; +; break; +; case 2: +; A[i] += 3; +; break; +; case 3: +; A[i] += 4; +; break; +; default:; +; } +; } +; } +; +; CHECK: Statements { +; CHECK: Stmt_sw_bb_9 +; CHECK: Domain := +; CHECK: [N] -> { Stmt_sw_bb_9[3] : N >= 4 }; +; CHECK: Stmt_sw_bb_5 +; CHECK: Domain := +; CHECK: [N] -> { Stmt_sw_bb_5[2] : N >= 3 }; +; CHECK: Stmt_sw_bb_1 +; CHECK: Domain := +; CHECK: [N] -> { Stmt_sw_bb_1[1] : N >= 2 }; +; CHECK: Stmt_sw_bb +; CHECK: Domain := +; CHECK: [N] -> { Stmt_sw_bb[0] : N >= 1 }; +; CHECK: } +; +; AST: if (1) +; +; AST: if (N >= 1) { +; AST: Stmt_sw_bb(0); +; AST: if (N >= 2) { +; AST: Stmt_sw_bb_1(1); +; AST: if (N >= 3) { +; AST: Stmt_sw_bb_5(2); +; AST: if (N >= 4) +; AST: Stmt_sw_bb_9(3); +; AST: } +; AST: } +; AST: } +; +; AST: else +; AST: { /* original code */ } +; +; +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define void @f(i32* %A, i32 %N) { +entry: + %tmp = sext i32 %N to i64 + br label %for.cond + +for.cond: ; preds = %for.inc, %entry + %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ] + %cmp = icmp slt i64 %indvars.iv, %tmp + br i1 %cmp, label %for.body, label %for.end + +for.body: ; preds = %for.cond + %tmp1 = trunc i64 %indvars.iv to i32 + switch i32 %tmp1, label %sw.default [ + i32 0, label %sw.bb + i32 1, label %sw.bb.1 + i32 2, label %sw.bb.5 + i32 3, label %sw.bb.9 + ] + +sw.bb: ; preds = %for.body + %arrayidx = getelementptr inbounds i32, i32* %A, i64 %indvars.iv + %tmp2 = load i32, i32* %arrayidx, align 4 + %add = add nsw i32 %tmp2, 1 + store i32 %add, i32* %arrayidx, align 4 + br label %sw.epilog + +sw.bb.1: ; preds = %for.body + %arrayidx3 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv + %tmp3 = load i32, i32* %arrayidx3, align 4 + %add4 = add nsw i32 %tmp3, 2 + store i32 %add4, i32* %arrayidx3, align 4 + br label %sw.epilog + +sw.bb.5: ; preds = %for.body + %arrayidx7 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv + %tmp4 = load i32, i32* %arrayidx7, align 4 + %add8 = add nsw i32 %tmp4, 3 + store i32 %add8, i32* %arrayidx7, align 4 + br label %sw.epilog + +sw.bb.9: ; preds = %for.body + %arrayidx11 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv + %tmp5 = load i32, i32* %arrayidx11, align 4 + %add12 = add nsw i32 %tmp5, 4 + store i32 %add12, i32* %arrayidx11, align 4 + br label %sw.epilog + +sw.default: ; preds = %for.body + br label %sw.epilog + +sw.epilog: ; preds = %sw.default, %sw.bb.9, %sw.bb.5, %sw.bb.1, %sw.bb + br label %for.inc + +for.inc: ; preds = %sw.epilog + %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1 + br label %for.cond + +for.end: ; preds = %for.cond + ret void +} Index: polly/trunk/test/ScopInfo/switch-7.ll =================================================================== --- polly/trunk/test/ScopInfo/switch-7.ll +++ polly/trunk/test/ScopInfo/switch-7.ll @@ -0,0 +1,114 @@ +; RUN: opt %loadPolly -polly-scops -analyze < %s | FileCheck %s +; RUN: opt %loadPolly -polly-ast -analyze < %s | FileCheck %s --check-prefix=AST +; +; void f(int *A, int c, int N) { +; switch (c) { +; case -1: { +; for (int j = N; j > 0; j--) +; A[j] += A[j - 1]; +; break; +; } +; case 1: { +; for (int j = 1; j <= N; j++) +; A[j] += A[j - 1]; +; break; +; } +; } +; } +; +; CHECK: Statements { +; CHECK: Stmt_for_body_7 +; CHECK: Domain := +; CHECK: [c, N] -> { Stmt_for_body_7[i0] : c = 1 and i0 >= 0 and i0 <= -1 + N }; +; CHECK: Schedule := +; CHECK: [c, N] -> { Stmt_for_body_7[i0] -> [0, i0] }; +; CHECK: Stmt_for_body +; CHECK: Domain := +; CHECK: [c, N] -> { Stmt_for_body[i0] : c = -1 and i0 >= 0 and i0 <= -1 + N }; +; CHECK: Schedule := +; CHECK: [c, N] -> { Stmt_for_body[i0] -> [1, i0] }; +; CHECK: } +; +; AST: if (1) +; +; AST: if (c == 1) { +; AST: for (int c0 = 0; c0 < N; c0 += 1) +; AST: Stmt_for_body_7(c0); +; AST: } else if (c == -1) +; AST: for (int c0 = 0; c0 < N; c0 += 1) +; AST: Stmt_for_body(c0); +; +; AST: else +; AST: { /* original code */ } +; +; +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +define void @f(i32* %A, i32 %c, i32 %N) { +entry: + br label %entry.split + +entry.split: + switch i32 %c, label %sw.epilog [ + i32 -1, label %sw.bb + i32 1, label %sw.bb.3 + ] + +sw.bb: ; preds = %entry + %tmp = sext i32 %N to i64 + br label %for.cond + +for.cond: ; preds = %for.inc, %sw.bb + %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ %tmp, %sw.bb ] + %j.0 = phi i32 [ %N, %sw.bb ], [ %dec, %for.inc ] + %cmp = icmp sgt i64 %indvars.iv, 0 + br i1 %cmp, label %for.body, label %for.end + +for.body: ; preds = %for.cond + %sub = add nsw i32 %j.0, -1 + %idxprom = sext i32 %sub to i64 + %arrayidx = getelementptr inbounds i32, i32* %A, i64 %idxprom + %tmp6 = load i32, i32* %arrayidx, align 4 + %arrayidx2 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv + %tmp7 = load i32, i32* %arrayidx2, align 4 + %add = add nsw i32 %tmp7, %tmp6 + store i32 %add, i32* %arrayidx2, align 4 + br label %for.inc + +for.inc: ; preds = %for.body + %dec = add nsw i32 %j.0, -1 + %indvars.iv.next = add nsw i64 %indvars.iv, -1 + br label %for.cond + +for.end: ; preds = %for.cond + br label %sw.epilog + +sw.bb.3: ; preds = %entry + %tmp8 = sext i32 %N to i64 + br label %for.cond.5 + +for.cond.5: ; preds = %for.inc.14, %sw.bb.3 + %indvars.iv3 = phi i64 [ %indvars.iv.next4, %for.inc.14 ], [ 1, %sw.bb.3 ] + %cmp6 = icmp sgt i64 %indvars.iv3, %tmp8 + br i1 %cmp6, label %for.end.15, label %for.body.7 + +for.body.7: ; preds = %for.cond.5 + %tmp9 = add nsw i64 %indvars.iv3, -1 + %arrayidx10 = getelementptr inbounds i32, i32* %A, i64 %tmp9 + %tmp10 = load i32, i32* %arrayidx10, align 4 + %arrayidx12 = getelementptr inbounds i32, i32* %A, i64 %indvars.iv3 + %tmp11 = load i32, i32* %arrayidx12, align 4 + %add13 = add nsw i32 %tmp11, %tmp10 + store i32 %add13, i32* %arrayidx12, align 4 + br label %for.inc.14 + +for.inc.14: ; preds = %for.body.7 + %indvars.iv.next4 = add nuw nsw i64 %indvars.iv3, 1 + br label %for.cond.5 + +for.end.15: ; preds = %for.cond.5 + br label %sw.epilog + +sw.epilog: ; preds = %for.end.15, %for.end, %entry + ret void +}