[Polly] Extract number of elements/iterations for a isl_set/isl_ast_node

[jdoerfert]

Move the functions and actually use the new getNumberOfIterations interface

[jdoerfert]

Restricted the diff to the actual commit (not some pending predecessor commits)

[jdoerfert]

Some comments about the patch

include/polly/CodeGen/CodeGeneration.h

42 ↗

(On Diff #14599)

This is a full fledged function marked static and put into a header file which is other than that pretty much useless.

I really want to get rid of it.

include/polly/CodeGen/IslAst.h

144 ↗

(On Diff #14599)

We might consider to move to this interface and do some actual computation on the parametric loop trip counts instead of limiting ourselfs to integer loop trip counts... often the LLVM vectorizer does not vectorize loops even if they are annotated parallel and have a few simple load-binop-store chains (e.g., bicg when it's parallelized in the outer most dimension and therefore doesn't have a reduction in the innermost loop any more [due to privatization to be exact]).

include/polly/Support/GICHelper.h

77

We might want to put stuff like this [also createAff, createPwAff, etc] into isl to ease handling.

93

This function will also be used to determine the number of privatization locations needed.

lib/Support/GICHelper.cpp

198

This will probably be easier from within isl.

[jdoerfert]

Promoted the trip count to a member of the isl_ast_node payload and used the
new functionality to emit less loop guards than with ScalarEvolution

[jdoerfert]

Lnt shows that sometimes it is very costly to compute the loop bounds. So I figure we cannot compute it for every loop but only on demand.

However, we need a fast way to compute hasAtLeastOneIteration(isl_ast_node *For). Any thoughts?

[simbuerg]

Just a minor comment, I'm not fully awake yet. Btw, get some sleep! ;-)

include/polly/CodeGen/CodeGeneration.h

42 ↗

(On Diff #14652)

Deprecated*

[jdoerfert]

This was flawed and is not needed at the moment.

include/polly/Support/GICHelper.h

 struct isl_set;
 struct isl_union_set;
 struct isl_schedule;
 struct isl_multi_aff;
 struct isl_pw_multi_aff;
 struct isl_aff;
 struct isl_pw_aff;
 struct isl_val;
+struct isl_ast_node;
 
 namespace llvm {
 class Value;
 }
 
 namespace polly {
 __isl_give isl_val *isl_valFromAPInt(isl_ctx *Ctx, const llvm::APInt Int,
                                      bool IsSigned);
inline llvm::raw_ostream &operator<<(llvm::raw_ostream &OS,
   OS << polly::stringFromIslObj(Map);
   return OS;
 }
 
 /// @brief Return @p Prefix + @p Val->getName() + @p Suffix but Isl compatible.
 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 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.
+///
+/// @note The returned value is always "off by one" (to low) in each dimension.
+__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.
+///
+/// @see getNumberOfIterations(isl_ast_node *For).
+__isl_give isl_pw_aff *
+getNumberOfIterationsForSchedule(__isl_take isl_union_map *Schedule);
+
+/// @brief Return the number of iterations for @p For.
+///
+/// @note This function used getNumElementsUB which guarantees only an
+///       overestimation on the number of elements of the given set.
+///       However, due to the nature of the set we are using the number of
+///       elements will always be exact. (The set here is the loop domain!)
+__isl_give isl_pw_aff *getNumberOfIterations(__isl_keep isl_ast_node *For);
+
 } // end namespace polly
 
 #endif

lib/Support/GICHelper.cpp

 //===- GmpConv.cpp - Recreate LLVM IR from the Scop.  ---------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // Functions for converting between gmp objects and apint.
 //
 //===----------------------------------------------------------------------===//
 #include "polly/Support/GICHelper.h"
+#include "polly/CodeGen/IslAst.h"
+
 #include "llvm/IR/Value.h"
+
 #include "isl/aff.h"
 #include "isl/map.h"
 #include "isl/schedule.h"
 #include "isl/set.h"
 #include "isl/union_map.h"
 #include "isl/union_set.h"
 #include "isl/val.h"
+#include "isl/ast.h"
 
 using namespace llvm;
 
 __isl_give isl_val *polly::isl_valFromAPInt(isl_ctx *Ctx, const APInt Int,
                                             bool IsSigned) {
   APInt Abs;
   isl_val *v;
 
std::string polly::getIslCompatibleName(std::string Prefix, const Value *Val,
   Val->printAsOperand(OS, false);
   ValStr = OS.str();
   // Remove the leading %
   ValStr.erase(0, 1);
   ValStr = Prefix + ValStr + Suffix;
   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);
+  return isl_pw_multi_aff_coalesce(Elements);
+}
+
+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);
+  NumIterations = incrementPwAff(NumIterations, 1);
+  NumIterations = isl_pw_aff_coalesce(NumIterations);
+  return NumIterations;
+}
+
+isl_pw_aff *polly::getNumberOfIterations(isl_ast_node *For) {
+  isl_union_map *Schedule = IslAstInfo::getSchedule(For);
+  return getNumberOfIterationsForSchedule(Schedule);
+}