[Polly] Allow switch instructions in SCoPs

[jdoerfert]

Summary

This patch allows switch instructions with affine conditions in the
SCoP. Also switch instructions in non-affine subregions are allowed.
Both did not require much changes to the code, though there was some
refactoring needed to integrate them without code duplication.

In the llvm-test suite the number of profitable SCoPs increased from
135 to 139 but more importantly we can handle more benchmarks and user
inputs without preprocessing.

[grosser]

LGTM.

polly/trunk/include/polly/ScopDetection.h

private:
   /// @brief Check if an instruction can be part of a Scop.
   ///
   /// @param Inst The instruction to check.
   /// @param Context The context of scop detection.
   ///
   /// @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.
   /// @param Context The context of scop detection.
   ///
   /// @return True if the BB contains only valid control flow.
   bool isValidCFG(BasicBlock &BB, DetectionContext &Context) const;
 

polly/trunk/include/polly/ScopDetectionDiagnostic.h

 /// @param F The function we emit remarks for
 /// @param R The region that marks a valid Scop
 void emitValidRemarks(const llvm::Function &F, const Region *R);
 
 // Discriminator for LLVM-style RTTI (dyn_cast<> et al.)
 enum RejectReasonKind {
   // CFG Category
   rrkCFG,
-  rrkNonBranchTerminator,
+  rrkInvalidTerminator,
   rrkCondition,
   rrkLastCFG,
 
   // Non-Affinity
   rrkAffFunc,
   rrkUndefCond,
   rrkInvalidCond,
   rrkUnsignedCond,
public:
 
   /// @name LLVM-RTTI interface
   //@{
   static bool classof(const RejectReason *RR);
   //@}
 };
 
 //===----------------------------------------------------------------------===//
-/// @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
   //@{
   static bool classof(const RejectReason *RR);
   //@}
 
   /// @name RejectReason interface
   //@{

polly/trunk/include/polly/Support/ScopHelper.h

 class PHINode;
 class Region;
 class Pass;
 class BasicBlock;
 class StringRef;
 class DataLayout;
 class DominatorTree;
 class RegionInfo;
+class TerminatorInst;
 class ScalarEvolution;
 }
 
 namespace polly {
 class Scop;
 /// Temporary Hack for extended regiontree.
 ///
 /// @brief Cast the region to loop.

 ///  - It is terminated by an unreachable instruction
 ///  - It contains a call to a function named:
 ///     + __ubsan_handle_out_of_bounds
 ///
 /// @param BB The block to check.
 ///
 /// @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

polly/trunk/lib/Analysis/ScopDetection.cpp

for (BasicBlock *BB : AR->blocks()) {
     Loop *L = LI->getLoopFor(BB);
     if (AR->contains(L))
       Context.BoxedLoopsSet.insert(L);
   }
 
   return (AllowNonAffineSubLoops || Context.BoxedLoopsSet.empty());
 }
 
-bool ScopDetection::isValidCFG(BasicBlock &BB,
+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<ReturnInst>(TI) && !CurRegion.getExit() && TI->getNumOperands() == 0)
-    return true;
-
-  BranchInst *Br = dyn_cast<BranchInst>(TI);
+  Loop *L = LI->getLoopFor(&BB);
+  const SCEV *ConditionSCEV = SE->getSCEVAtScope(Condition, L);
 
-  if (!Br)
-    return invalid<ReportNonBranchTerminator>(Context, /*Assert=*/true, &BB);
+  if (!isAffineExpr(&CurRegion, ConditionSCEV, *SE))
+    if (!AllowNonAffineSubRegions ||
+        !addOverApproximatedRegion(RI->getRegionFor(&BB), Context))
+      return invalid<ReportNonAffBranch>(Context, /*Assert=*/true, &BB,
+                                         ConditionSCEV, ConditionSCEV, SI);
 
-  if (Br->isUnconditional())
-    return true;
+}
 
-  Value *Condition = Br->getCondition();
-
-  // UndefValue is not allowed as condition.
-  if (isa<UndefValue>(Condition))
-    return invalid<ReportUndefCond>(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<Constant>(Condition) || isa<ICmpInst>(Condition))) {
+  // Non constant conditions of branches need to be ICmpInst.
+  if (!isa<ICmpInst>(Condition)) {
     if (!AllowNonAffineSubRegions ||
         !addOverApproximatedRegion(RI->getRegionFor(&BB), Context))
-      return invalid<ReportInvalidCond>(Context, /*Assert=*/true, Br, &BB);
+      return invalid<ReportInvalidCond>(Context, /*Assert=*/true, BI, &BB);
   }
 
-  // Allow perfectly nested conditions.
-  assert(Br->getNumSuccessors() == 2 && "Unexpected number of successors");
-
   if (ICmpInst *ICmp = dyn_cast<ICmpInst>(Condition)) {
     // Unsigned comparisons are not allowed. They trigger overflow problems
     // in the code generation.
     //
     // TODO: This is not sufficient and just hides bugs. However it does pretty
     // well.
     if (ICmp->isUnsigned() && !AllowUnsigned)
-      return invalid<ReportUnsignedCond>(Context, /*Assert=*/true, Br, &BB);
+      return invalid<ReportUnsignedCond>(Context, /*Assert=*/true, BI, &BB);
 
     // Are both operands of the ICmp affine?
     if (isa<UndefValue>(ICmp->getOperand(0)) ||
         isa<UndefValue>(ICmp->getOperand(1)))
       return invalid<ReportUndefOperand>(Context, /*Assert=*/true, &BB, ICmp);
 
     // TODO: FIXME: IslExprBuilder is not capable of producing valid code
     //              for arbitrary pointer expressions at the moment. Until
if (!isAffineExpr(&CurRegion, LHS, *SE) ||
         return invalid<ReportNonAffBranch>(Context, /*Assert=*/true, &BB, LHS,
                                            RHS, ICmp);
     }
   }
 
   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<ReturnInst>(TI) && !CurRegion.getExit() && TI->getNumOperands() == 0)
+    return true;
+
+  Value *Condition = getConditionFromTerminator(TI);
+
+  if (!Condition)
+    return invalid<ReportInvalidTerminator>(Context, /*Assert=*/true, &BB);
+
+  // UndefValue is not allowed as condition.
+  if (isa<UndefValue>(Condition))
+    return invalid<ReportUndefCond>(Context, /*Assert=*/true, TI, &BB);
+
+  // Constant conditions are always affine.
+  if (isa<Constant>(Condition))
+    return true;
+
+  if (BranchInst *BI = dyn_cast<BranchInst>(TI))
+    return isValidBranch(BB, BI, Condition, Context);
+
+  SwitchInst *SI = dyn_cast<SwitchInst>(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;
 
   if (CI.doesNotAccessMemory())
     return true;
 
   Function *CalledFunction = CI.getCalledFunction();

polly/trunk/lib/Analysis/ScopDetectionDiagnostic.cpp

ReportCFG::ReportCFG(const RejectReasonKind K) : RejectReason(K) {
   ++BadCFGForScop;
 }
 
 bool ReportCFG::classof(const RejectReason *RR) {
   return RR->getKind() >= rrkCFG && RR->getKind() <= rrkLastCFG;
 }
 
 //===----------------------------------------------------------------------===//
-// 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;
 }
 
 //===----------------------------------------------------------------------===//
 // ReportAffFunc.
 
 ReportAffFunc::ReportAffFunc(const RejectReasonKind K, const Instruction *Inst)
     : RejectReason(K), Inst(Inst) {
   ++BadAffFuncForScop;

polly/trunk/lib/Analysis/ScopInfo.cpp

partitionSetParts(__isl_take isl_set *S, unsigned Dim) {
 
   // Remove the artificial upper bound parameters again.
   BoundedParts = isl_set_remove_dims(BoundedParts, isl_dim_param, 0, Dim);
 
   isl_set *UnboundedParts = isl_set_subtract(S, isl_set_copy(BoundedParts));
   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);
   case ICmpInst::ICMP_NE:
     return isl_pw_aff_ne_set(L, R);
   case ICmpInst::ICMP_SLT:
     return isl_pw_aff_lt_set(L, R);
   case ICmpInst::ICMP_SLE:
case ICmpInst::ICMP_ULE:
     return isl_pw_aff_le_set(L, R);
   case ICmpInst::ICMP_UGE:
     return isl_pw_aff_ge_set(L, R);
   default:
     llvm_unreachable("Non integer predicate not supported");
   }
 }
 
-/// @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 BI to its successors. Hence, @p ConditionSets will
-/// have as many elements as @p BI has successors.
+/// 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, BranchInst *BI, Loop *L, __isl_keep isl_set *Domain,
+buildConditionSets(Scop &S, SwitchInst *SI, Loop *L, __isl_keep isl_set *Domain,
                    SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
 
-  if (BI->isUnconditional()) {
+  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 TI to its successors. Hence, @p ConditionSets will
+/// have as many elements as @p TI has successors.
+static void
+buildConditionSets(Scop &S, TerminatorInst *TI, Loop *L,
+                   __isl_keep isl_set *Domain,
+                   SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
+
+  if (SwitchInst *SI = dyn_cast<SwitchInst>(TI))
+    return buildConditionSets(S, SI, L, Domain, ConditionSets);
+
+  assert(isa<BranchInst>(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<ConstantInt>(Condition)) {
     if (CCond->isZero())
       ConsequenceCondSet = isl_set_empty(isl_set_get_space(Domain));
     else
       ConsequenceCondSet = isl_set_universe(isl_set_get_space(Domain));
   } else {
     auto *ICond = dyn_cast<ICmpInst>(Condition);
     assert(ICond &&
            "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);
-    }
+        buildConditionSet(ICond->getPredicate(), LHS, RHS, Domain);
   }
 
   assert(ConsequenceCondSet);
   isl_set *AlternativeCondSet =
       isl_set_complement(isl_set_copy(ConsequenceCondSet));
 
   ConditionSets.push_back(isl_set_coalesce(
       isl_set_intersect(ConsequenceCondSet, isl_set_copy(Domain))));

 
 /// @brief Return the block that is the representing block for @p RN.
 static inline BasicBlock *getRegionNodeBasicBlock(RegionNode *RN) {
   return RN->isSubRegion() ? RN->getNodeAs<Region>()->getEntry()
                            : RN->getNodeAs<BasicBlock>();
 }
 
 /// @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<Region>()->getExit();
   }
-  return BI->getSuccessor(idx);
+  return TI->getSuccessor(idx);
 }
 
 /// @brief Return the smallest loop surrounding @p RN.
 static inline Loop *getRegionNodeLoop(RegionNode *RN, LoopInfo &LI) {
   if (!RN->isSubRegion())
     return LI.getLoopFor(RN->getNodeAs<BasicBlock>());
 
   Region *NonAffineSubRegion = RN->getNodeAs<Region>();
for (auto *RN : RTraversal) {
 
     Loop *BBLoop = getRegionNodeLoop(RN, LI);
     int BBLoopDepth = getRelativeLoopDepth(BBLoop);
 
     // Build the condition sets for the successor nodes of the current region
     // 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<isl_set *, 2> ConditionSets;
-    BranchInst *BI = cast<BranchInst>(TI);
+    SmallVector<isl_set *, 8> 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)) {
         isl_set_free(CondSet);
         continue;
       }
 
       // Do not adjust the number of dimensions if we enter a boxed loop or are
void Scop::addLoopBoundsToHeaderDomain(Loop *L, LoopInfo &LI) {
   SmallVector<llvm::BasicBlock *, 4> LatchBlocks;
   L->getLoopLatches(LatchBlocks);
 
   for (BasicBlock *LatchBB : LatchBlocks) {
     assert(DomainMap.count(LatchBB));
     isl_set *LatchBBDom = DomainMap[LatchBB];
     isl_set *BackedgeCondition = nullptr;
 
-    BranchInst *BI = cast<BranchInst>(LatchBB->getTerminator());
-    if (BI->isUnconditional())
+    TerminatorInst *TI = LatchBB->getTerminator();
+    BranchInst *BI = dyn_cast<BranchInst>(TI);
+    if (BI && BI->isUnconditional())
       BackedgeCondition = isl_set_copy(LatchBBDom);
     else {
-      SmallVector<isl_set *, 2> ConditionSets;
+      SmallVector<isl_set *, 8> 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]);
 
       BackedgeCondition = ConditionSets[idx];
     }
 
     int LatchLoopDepth = getRelativeLoopDepth(LI.getLoopFor(LatchBB));

polly/trunk/lib/CodeGen/BlockGenerators.cpp

for (BasicBlock *BB : SeenBlocks) {
     TerminatorInst *TI = BB->getTerminator();
     if (isa<UnreachableInst>(TI)) {
       while (!BBCopy->empty())
         BBCopy->begin()->eraseFromParent();
       new UnreachableInst(BBCopy->getContext(), BBCopy);
       continue;
     }
 
-    BranchInst *BI = cast<BranchInst>(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();
   }
 
   // Add counting PHI nodes to all loops in the region that can be used as
   // replacement for SCEVs refering to the old loop.
   for (BasicBlock *BB : SeenBlocks) {
     Loop *L = LI.getLoopFor(BB);
     if (L == nullptr || L->getHeader() != BB)

polly/trunk/lib/Support/ScopHelper.cpp

if (CallInst *CI = dyn_cast<CallInst>(&Inst))
         if (F->getName().equals("__ubsan_handle_out_of_bounds"))
           return true;
 
   if (isa<UnreachableInst>(BB.getTerminator()))
     return true;
 
   return false;
 }
+
+Value *polly::getConditionFromTerminator(TerminatorInst *TI) {
+  if (BranchInst *BR = dyn_cast<BranchInst>(TI)) {
+    if (BR->isUnconditional())
+      return ConstantInt::getTrue(Type::getInt1Ty(TI->getContext()));
+
+    return BR->getCondition();
+  }
+
+  if (SwitchInst *SI = dyn_cast<SwitchInst>(TI))
+    return SI->getCondition();
+
+  return nullptr;
+}

polly/trunk/test/Isl/CodeGen/non-affine-switch.ll

+; 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
+}

polly/trunk/test/Isl/CodeGen/switch-in-non-affine-region.ll

+; 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
+}

polly/trunk/test/ScopInfo/switch-1.ll

+; 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
+}

polly/trunk/test/ScopInfo/switch-2.ll

+; 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
+}

polly/trunk/test/ScopInfo/switch-3.ll

+; 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
+}

polly/trunk/test/ScopInfo/switch-4.ll

+; 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
+}

polly/trunk/test/ScopInfo/switch-5.ll

+; 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
+}

polly/trunk/test/ScopInfo/switch-6.ll

+; 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
+}

polly/trunk/test/ScopInfo/switch-7.ll

+; 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
+}