Index: include/polly/CodeGen/CodeGeneration.h
===================================================================
--- include/polly/CodeGen/CodeGeneration.h
+++ include/polly/CodeGen/CodeGeneration.h
@@ -39,6 +39,7 @@
 /// @brief Flag to turn on/off annotation of alias scopes.
 extern bool PollyAnnotateAliasScopes;
 
+/// FIXME: Depraced and needs to be removed with the cloog backend.
 static inline int getNumberOfIterations(__isl_take isl_set *Domain) {
   int Dim = isl_set_dim(Domain, isl_dim_set);
 
Index: include/polly/CodeGen/IslAst.h
===================================================================
--- include/polly/CodeGen/IslAst.h
+++ include/polly/CodeGen/IslAst.h
@@ -139,6 +139,12 @@
   /// @brief Get the nodes build context or a nullptr if not available.
   static __isl_give isl_ast_build *getBuild(__isl_keep isl_ast_node *Node);
 
+  /// @brief Get the number of iterations or a nullptr if not available.
+  static __isl_give isl_pw_aff *
+  getNumberOfIterations(__isl_keep isl_ast_node *For);
+
+  /// @brief Get the number of iterations as int or -1 if not available.
+  static int getNumberOfIterationsAsInt(__isl_keep isl_ast_node *For);
   ///}
 
   virtual void getAnalysisUsage(AnalysisUsage &AU) const;
Index: include/polly/Support/GICHelper.h
===================================================================
--- include/polly/Support/GICHelper.h
+++ include/polly/Support/GICHelper.h
@@ -75,6 +75,32 @@
 std::string getIslCompatibleName(std::string Prefix, const llvm::Value *Val,
                                  std::string Suffix);
 
+/// @brief Return @p Aff incremented by @p i
+__isl_give isl_pw_aff *incrementPwAff(__isl_take isl_pw_aff *Aff, int i);
+
+/// @brief Return the only affine piece of @p PA.
+__isl_give isl_aff *isl_aff_from_pw_aff(__isl_take isl_pw_aff *PA);
+
+/// @brief Return an overestimation of the number of elements in @p S.
+///
+/// @param S         The set of which we want to now a bound on the elements.
+/// @param Dim       The number of input dimensions we want to keep.
+/// @param LexMinPtr If not null the lexmin will be returned in here.
+/// @param LexMaxPtr If not null the lexmax will be returned in here.
+///
+/// @returns A piecewise affine function over approximating the number of
+///          elements in @p S as a function of the first @p Dim dimensions
+///          of @p S. Furthermore the lexicographic minimum/maximum of @p S
+///          in @p LexMinPtr and @p LexMaxPtr if they are given.
+__isl_give isl_pw_multi_aff *
+getNumElementsUB(__isl_take isl_set *S, int Dim,
+                 __isl_give isl_map **LexMinPtr = nullptr,
+                 __isl_give isl_map **LexMaxPtr = nullptr);
+
+/// @brief Return the number of iterations for the outermost dim of @p Schedule.
+__isl_give isl_pw_aff *
+getNumberOfIterationsForSchedule(__isl_take isl_union_map *Schedule);
+
 } // end namespace polly
 
 #endif
Index: lib/CodeGen/IslAst.cpp
===================================================================
--- lib/CodeGen/IslAst.cpp
+++ lib/CodeGen/IslAst.cpp
@@ -25,6 +25,7 @@
 #include "polly/LinkAllPasses.h"
 #include "polly/Options.h"
 #include "polly/ScopInfo.h"
+#include "polly/Support/GICHelper.h"
 #include "llvm/Support/Debug.h"
 
 #include "isl/union_map.h"
@@ -466,6 +467,31 @@
   return Payload ? Payload->Build : nullptr;
 }
 
+isl_pw_aff *IslAstInfo::getNumberOfIterations(isl_ast_node *For) {
+  isl_union_map *Schedule = IslAstInfo::getSchedule(For);
+  return Schedule ? getNumberOfIterationsForSchedule(Schedule) : nullptr;
+}
+
+int IslAstInfo::getNumberOfIterationsAsInt(isl_ast_node *For) {
+  isl_pw_aff *NumItPAff = getNumberOfIterations(For);
+  if (!NumItPAff || !isl_pw_aff_is_cst(NumItPAff) ||
+      isl_pw_aff_n_piece(NumItPAff) != 1) {
+    isl_pw_aff_free(NumItPAff);
+    return -1;
+  }
+
+  isl_aff *NumItAff = isl_aff_from_pw_aff(NumItPAff);
+  assert(isl_aff_is_cst(NumItAff) && "Assumed affine function to be constant");
+
+  isl_val *NumItVal = isl_aff_get_constant_val(NumItAff);
+  isl_aff_free(NumItAff);
+
+  int NumItInt = isl_val_get_num_si(NumItVal);
+  isl_val_free(NumItVal);
+
+  return NumItInt;
+}
+
 void IslAstInfo::printScop(raw_ostream &OS) const {
   isl_ast_print_options *Options;
   isl_ast_node *RootNode = getAst();
Index: lib/CodeGen/IslCodeGeneration.cpp
===================================================================
--- lib/CodeGen/IslCodeGeneration.cpp
+++ lib/CodeGen/IslCodeGeneration.cpp
@@ -110,8 +110,6 @@
   __isl_give isl_ast_expr *getUpperBound(__isl_keep isl_ast_node *For,
                                          CmpInst::Predicate &Predicate);
 
-  unsigned getNumberOfIterations(__isl_keep isl_ast_node *For);
-
   void createFor(__isl_take isl_ast_node *For);
   void createForVector(__isl_take isl_ast_node *For, int VectorWidth);
   void createForSequential(__isl_take isl_ast_node *For);
@@ -222,15 +220,6 @@
   return UB;
 }
 
-unsigned IslNodeBuilder::getNumberOfIterations(__isl_keep isl_ast_node *For) {
-  isl_union_map *Schedule = IslAstInfo::getSchedule(For);
-  isl_set *LoopDomain = isl_set_from_union_set(isl_union_map_range(Schedule));
-  int NumberOfIterations = polly::getNumberOfIterations(LoopDomain);
-  if (NumberOfIterations == -1)
-    return -1;
-  return NumberOfIterations + 1;
-}
-
 void IslNodeBuilder::createUserVector(__isl_take isl_ast_node *User,
                                       std::vector<Value *> &IVS,
                                       __isl_take isl_id *IteratorID,
@@ -386,7 +375,7 @@
 
   if (Vector && IslAstInfo::isInnermostParallel(For) &&
       !IslAstInfo::isReductionParallel(For)) {
-    int VectorWidth = getNumberOfIterations(For);
+    int VectorWidth = IslAstInfo::getNumberOfIterationsAsInt(For);
     if (1 < VectorWidth && VectorWidth <= 16) {
       createForVector(For, VectorWidth);
       return;
Index: lib/Support/GICHelper.cpp
===================================================================
--- lib/Support/GICHelper.cpp
+++ lib/Support/GICHelper.cpp
@@ -11,7 +11,9 @@
 //
 //===----------------------------------------------------------------------===//
 #include "polly/Support/GICHelper.h"
+
 #include "llvm/IR/Value.h"
+
 #include "isl/aff.h"
 #include "isl/map.h"
 #include "isl/schedule.h"
@@ -152,3 +154,70 @@
   makeIslCompatible(ValStr);
   return ValStr;
 }
+
+isl_pw_aff *polly::incrementPwAff(isl_pw_aff *Aff, int i) {
+  isl_aff *Zero = isl_aff_zero_on_domain(
+      isl_local_space_from_space(isl_pw_aff_get_domain_space(Aff)));
+  isl_aff *Inc = isl_aff_add_constant_si(Zero, i);
+  return isl_pw_aff_add(Aff, isl_pw_aff_from_aff(Inc));
+}
+
+isl_pw_multi_aff *polly::getNumElementsUB(isl_set *S, int Dim,
+                                          isl_map **LexMinPtr,
+                                          isl_map **LexMaxPtr) {
+  S = isl_set_reset_tuple_id(S);
+
+  isl_map *Map = isl_map_from_domain_and_range(isl_set_copy(S), S);
+  for (int i = 0; i < Dim; i++)
+    Map = isl_map_equate(Map, isl_dim_in, i, isl_dim_out, i);
+
+  isl_map *LexMax = isl_map_lexmax(isl_map_copy(Map));
+  if (LexMaxPtr)
+    *LexMaxPtr = isl_map_copy(LexMax);
+
+  isl_map *LexMin = isl_map_lexmin(Map);
+  if (LexMinPtr)
+    *LexMinPtr = isl_map_copy(LexMin);
+
+  isl_map *Sub = isl_map_sum(LexMax, isl_map_neg(LexMin));
+  isl_pw_multi_aff *Elements = isl_pw_multi_aff_from_map(Sub);
+
+  // Elements is now off-by-one (to low) in each dimension.
+  for (unsigned u = 0, e = isl_pw_multi_aff_dim(Elements, isl_dim_out); u < e;
+       u++) {
+    isl_pw_aff *ElementsDim = isl_pw_multi_aff_get_pw_aff(Elements, u);
+    ElementsDim = incrementPwAff(ElementsDim, 1);
+    Elements = isl_pw_multi_aff_set_pw_aff(Elements, u, ElementsDim);
+  }
+
+  return isl_pw_multi_aff_coalesce(Elements);
+}
+
+static int extractAffineFromPiecewiseAffine(__isl_keep isl_set *Dom,
+                                            __isl_keep isl_aff *Aff,
+                                            void *User) {
+  isl_set_free(Dom);
+  *(isl_aff **)User = Aff;
+  return 0;
+}
+
+isl_aff *polly::isl_aff_from_pw_aff(isl_pw_aff *PA) {
+  assert(PA && isl_pw_aff_n_piece(PA) == 1 &&
+         "PA is null or has not exactly one piece");
+  isl_aff *A = nullptr;
+  isl_pw_aff_foreach_piece(PA, extractAffineFromPiecewiseAffine, &A);
+  isl_pw_aff_free(PA);
+  assert(A && "Could not extract affine piece");
+  return A;
+}
+
+isl_pw_aff *polly::getNumberOfIterationsForSchedule(isl_union_map *Schedule) {
+  isl_union_set *Range = isl_union_map_range(Schedule);
+  isl_set *LoopDomain = isl_set_from_union_set(Range);
+  int InDim = isl_set_n_dim(LoopDomain) - 1;
+  isl_pw_multi_aff *NumElements = getNumElementsUB(LoopDomain, InDim);
+  unsigned Dim = isl_pw_multi_aff_dim(NumElements, isl_dim_set) - 1;
+  isl_pw_aff *NumIterations = isl_pw_multi_aff_get_pw_aff(NumElements, Dim);
+  isl_pw_multi_aff_free(NumElements);
+  return NumIterations;
+}