Add isl operator overloads for isl::pw_aff (Try II)

[grosser]

Summary

Piecewise affine expressions have directly corresponding mathematical
operators. Introduce these operators as overloads as this makes writing
code with isl::pw_aff expressions more directly readable.

We can now write:

A = B + C    instead of    A = B.add(C)

[Meinersbur]

Did you consider an NFC tag for the title?

We could also overload !=, ==, +=, -=. *=, /=. Would these be added in a follow-up patch?

include/polly/Support/ISLOperators.h

2

File name has capitalized ISL

14

[serious] Header guard still missing

19

Consider using @{ so doxygen knowns to which functions the comment applies

42

[serious] Use 'long' instead of 'int'. That's what isl::val's ctor takes.

unittests/Isl/IslTest.cpp

350

[serious] The other tests use

std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(), &isl_ctx_free);

to not require manual releasing the isl_ctx. The dtors of the pw_aff objects will also be only called at the end of the scop, i.e. /after/ their parent isl_ctx is free'd.

[philip.pfaffe]

Since you expect users to include the header, the operators should also be declared static.

[Meinersbur]

include/polly/Support/ISLOperators.h

111–167

[comment] Using tdiv as basis for division and remainder corresponds to C/C++'s definition of these operators, i.e. the most consistent choice.
However, in practice this rarely what a user really wants, most often it is modulo (cdiv) or they assume that the divisor is positive or divides the dividend in an integer (divexact). Would not defining a default division/remainder operator an option?

[grosser]

Changes since last patch:

• Capitalize ISL in header comment

• Add header guards

• Use "@{" to indicate multi-function doxygen comments

• Use unique_ptr when allocating isl_ctx

• Use "static inline"

[Meinersbur]

In D45534#1064800, @philip.pfaffe wrote:

Since you expect users to include the header, the operators should also be declared static.

This is not required. If the inline-function has external linkage, the compiler/linker may (and even must) reuse the same symbol for all cases where the function is not inlined (which is possible at the compiler's judgment). With static, the same function symbol can appear multiple times in the final executable, resulting in larger executables. This is how I understand http://en.cppreference.com/w/cpp/language/inline

[grosser]

Hi Michael, hi Philip.,

thanks for the very helpful comments. I believe I addressed all but the one I comment below explicitly:

include/polly/Support/ISLOperators.h

111–167

Very good analysis. We should either add a comment why these operators are choosen or drop them.

I am open to not having any division / remainder operators defined -- either forever or just as a start. If this is what you want and others agree I can drop this. Is this what you would prefer? Or should I rather add a comment why these have been choosen?r

[grosser]

@Meinersbur , your analysis regarding static seems correct. If @philip.pfaffe agrees, I drop the 'static' keyword again.

[Meinersbur]

In D45534#1064820, @grosser wrote:

@Meinersbur , your analysis regarding static seems correct. If @philip.pfaffe agrees, I drop the 'static' keyword again.

I don't really care. Compilation might faster with static because the compiler does not have to emit those symbols (I'd expect a compiler to not emit the symbols if the function is not used, even with external linkage; because the language mandates that an inline function has a definition in every translation unit, i.e. there is no translation unit that requires the symbol without defining it; it is true for clang, msvc and gcc; I checked. However, only for C++ but not C).

LGTM

include/polly/Support/ISLOperators.h

111–167

I'm fine with keeping them. Probably the most typical use cases are with constant-positive divisors: aff / 2 and aff % 2. We probably want to support this use case and it does not matter what the behavior with negative divisors is.

[grosser]

Add comments to operator/ and operator% describing that we round towards zero.

[grosser]

Remove unneeded include form incluse/Support/SCEVAffinator

include/polly/Support/ISLOperators.h

+//===------ ISLOperators.h --------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Operator overloads for isl C++ objects.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef POLLY_ISLOPERATORS_H
+#define POLLY_ISLOPERATORS_H
+
+#include "isl/isl-noexceptions.h"
+
+namespace polly {
+
+/// Addition
+/// @{
+inline isl::pw_aff operator+(isl::pw_aff Left, isl::pw_aff Right) {
+  return Left.add(Right);
+}
+
+inline isl::pw_aff operator+(isl::val ValLeft, isl::pw_aff Right) {
+  isl::pw_aff Left(Right.domain(), ValLeft);
+  return Left.add(Right);
+}
+
+inline isl::pw_aff operator+(isl::pw_aff Left, isl::val ValRight) {
+  isl::pw_aff Right(Left.domain(), ValRight);
+  return Left.add(Right);
+}
+
+inline isl::pw_aff operator+(long IntLeft, isl::pw_aff Right) {
+  isl::ctx Ctx = Right.get_ctx();
+  isl::val ValLeft(Ctx, IntLeft);
+  isl::pw_aff Left(Right.domain(), ValLeft);
+  return Left.add(Right);
+}
+
+inline isl::pw_aff operator+(isl::pw_aff Left, long IntRight) {
+  isl::ctx Ctx = Left.get_ctx();
+  isl::val ValRight(Ctx, IntRight);
+  isl::pw_aff Right(Left.domain(), ValRight);
+  return Left.add(Right);
+}
+/// @}
+
+/// Multiplication
+/// @{
+inline isl::pw_aff operator*(isl::pw_aff Left, isl::pw_aff Right) {
+  return Left.mul(Right);
+}
+
+inline isl::pw_aff operator*(isl::val ValLeft, isl::pw_aff Right) {
+  isl::pw_aff Left(Right.domain(), ValLeft);
+  return Left.mul(Right);
+}
+
+inline isl::pw_aff operator*(isl::pw_aff Left, isl::val ValRight) {
+  isl::pw_aff Right(Left.domain(), ValRight);
+  return Left.mul(Right);
+}
+
+inline isl::pw_aff operator*(long IntLeft, isl::pw_aff Right) {
+  isl::ctx Ctx = Right.get_ctx();
+  isl::val ValLeft(Ctx, IntLeft);
+  isl::pw_aff Left(Right.domain(), ValLeft);
+  return Left.mul(Right);
+}
+
+inline isl::pw_aff operator*(isl::pw_aff Left, long IntRight) {
+  isl::ctx Ctx = Left.get_ctx();
+  isl::val ValRight(Ctx, IntRight);
+  isl::pw_aff Right(Left.domain(), ValRight);
+  return Left.mul(Right);
+}
+/// @}
+
+/// Subtraction
+/// @{
+inline isl::pw_aff operator-(isl::pw_aff Left, isl::pw_aff Right) {
+  return Left.sub(Right);
+}
+
+inline isl::pw_aff operator-(isl::val ValLeft, isl::pw_aff Right) {
+  isl::pw_aff Left(Right.domain(), ValLeft);
+  return Left.sub(Right);
+}
+
+inline isl::pw_aff operator-(isl::pw_aff Left, isl::val ValRight) {
+  isl::pw_aff Right(Left.domain(), ValRight);
+  return Left.sub(Right);
+}
+
+inline isl::pw_aff operator-(long IntLeft, isl::pw_aff Right) {
+  isl::ctx Ctx = Right.get_ctx();
+  isl::val ValLeft(Ctx, IntLeft);
+  isl::pw_aff Left(Right.domain(), ValLeft);
+  return Left.sub(Right);
+}
+
+inline isl::pw_aff operator-(isl::pw_aff Left, long IntRight) {
+  isl::ctx Ctx = Left.get_ctx();
+  isl::val ValRight(Ctx, IntRight);
+  isl::pw_aff Right(Left.domain(), ValRight);
+  return Left.sub(Right);
+}
+/// @}
+
+/// Division
+///
+/// This division rounds towards zero. This follows the semantics of C/C++.
+///
+/// @{
+inline isl::pw_aff operator/(isl::pw_aff Left, isl::pw_aff Right) {
+  return Left.tdiv_q(Right);
+}
+
+inline isl::pw_aff operator/(isl::val ValLeft, isl::pw_aff Right) {
+  isl::pw_aff Left(Right.domain(), ValLeft);
+  return Left.tdiv_q(Right);
+}
+
+inline isl::pw_aff operator/(isl::pw_aff Left, isl::val ValRight) {
+  isl::pw_aff Right(Left.domain(), ValRight);
+  return Left.tdiv_q(Right);
+}
+
+inline isl::pw_aff operator/(long IntLeft, isl::pw_aff Right) {
+  isl::ctx Ctx = Right.get_ctx();
+  isl::val ValLeft(Ctx, IntLeft);
+  isl::pw_aff Left(Right.domain(), ValLeft);
+  return Left.tdiv_q(Right);
+}
+
+inline isl::pw_aff operator/(isl::pw_aff Left, long IntRight) {
+  isl::ctx Ctx = Left.get_ctx();
+  isl::val ValRight(Ctx, IntRight);
+  isl::pw_aff Right(Left.domain(), ValRight);
+  return Left.tdiv_q(Right);
+}
+/// @}
+
+/// Remainder
+///
+/// This is the remainder of a division which rounds towards zero. This follows
+/// the semantics of C/C++.
+///
+/// @{
+inline isl::pw_aff operator%(isl::pw_aff Left, isl::pw_aff Right) {
+  return Left.tdiv_r(Right);
+}
+
+inline isl::pw_aff operator%(isl::val ValLeft, isl::pw_aff Right) {
+  isl::pw_aff Left(Right.domain(), ValLeft);
+  return Left.tdiv_r(Right);
+}
+
+inline isl::pw_aff operator%(isl::pw_aff Left, isl::val ValRight) {
+  isl::pw_aff Right(Left.domain(), ValRight);
+  return Left.tdiv_r(Right);
+}
+
+inline isl::pw_aff operator%(long IntLeft, isl::pw_aff Right) {
+  isl::ctx Ctx = Right.get_ctx();
+  isl::val ValLeft(Ctx, IntLeft);
+  isl::pw_aff Left(Right.domain(), ValLeft);
+  return Left.tdiv_r(Right);
+}
+
+inline isl::pw_aff operator%(isl::pw_aff Left, long IntRight) {
+  isl::ctx Ctx = Left.get_ctx();
+  isl::val ValRight(Ctx, IntRight);
+  isl::pw_aff Right(Left.domain(), ValRight);
+  return Left.tdiv_r(Right);
+}
+/// @}
+
+} // namespace polly
+
+#endif // POLLY_ISLOPERATORS_H

lib/Support/SCEVAffinator.cpp

 // Create a polyhedral description for a SCEV value.
 //
 //===----------------------------------------------------------------------===//
 
 #include "polly/Support/SCEVAffinator.h"
 #include "polly/Options.h"
 #include "polly/ScopInfo.h"
 #include "polly/Support/GICHelper.h"
+#include "polly/Support/ISLOperators.h"
 #include "polly/Support/SCEVValidator.h"
 #include "polly/Support/ScopHelper.h"
 #include "isl/aff.h"
 #include "isl/local_space.h"
 #include "isl/set.h"
 #include "isl/val.h"
 
 using namespace llvm;

unittests/Isl/IslTest.cpp

 //===- IslTest.cpp ----------------------------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "polly/Support/GICHelper.h"
+#include "polly/Support/ISLOperators.h"
 #include "polly/Support/ISLTools.h"
 #include "gtest/gtest.h"
 #include "isl/stream.h"
 #include "isl/val.h"
 
 using namespace llvm;
 using namespace polly;
 

 static bool operator==(const isl::union_map &LHS, const isl::union_map &RHS) {
   return bool(LHS.is_equal(RHS));
 }
 
 static bool operator==(const isl::val &LHS, const isl::val &RHS) {
   return bool(LHS.eq(RHS));
 }
 
+static bool operator==(const isl::pw_aff &LHS, const isl::pw_aff &RHS) {
+  return bool(LHS.is_equal(RHS));
+}
 } // namespace noexceptions
 } // namespace isl
 
 namespace {
 
 TEST(Isl, APIntToIslVal) {
   isl_ctx *IslCtx = isl_ctx_alloc();
 
isl_ctx *IslCtx = isl_ctx_alloc();
     EXPECT_EQ(513u, APLargeNPow2.getBitWidth());
     EXPECT_EQ(513u, APLargeNPow2.getMinSignedBits());
     EXPECT_EQ(512, (-APLargeNPow2).exactLogBase2());
   }
 
   isl_ctx_free(IslCtx);
 }
 
+TEST(Isl, Operators) {
+  std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> IslCtx(isl_ctx_alloc(),
+                                                           &isl_ctx_free);
+
+  isl::val ValOne = isl::val(IslCtx.get(), 1);
+  isl::val ValTwo = isl::val(IslCtx.get(), 2);
+  isl::val ValThree = isl::val(IslCtx.get(), 3);
+  isl::val ValFour = isl::val(IslCtx.get(), 4);
+  isl::val ValNegOne = isl::val(IslCtx.get(), -1);
+  isl::val ValNegTwo = isl::val(IslCtx.get(), -2);
+  isl::val ValNegThree = isl::val(IslCtx.get(), -3);
+  isl::val ValNegFour = isl::val(IslCtx.get(), -4);
+
+  isl::space Space = isl::space(IslCtx.get(), 0, 0);
+  isl::local_space LS = isl::local_space(Space);
+
+  isl::pw_aff AffOne = isl::aff(LS, ValOne);
+  isl::pw_aff AffTwo = isl::aff(LS, ValTwo);
+  isl::pw_aff AffThree = isl::aff(LS, ValThree);
+  isl::pw_aff AffFour = isl::aff(LS, ValFour);
+  isl::pw_aff AffNegOne = isl::aff(LS, ValNegOne);
+  isl::pw_aff AffNegTwo = isl::aff(LS, ValNegTwo);
+  isl::pw_aff AffNegThree = isl::aff(LS, ValNegThree);
+  isl::pw_aff AffNegFour = isl::aff(LS, ValNegFour);
+
+  // Addition
+  {
+    EXPECT_EQ(AffOne + AffOne, AffTwo);
+    EXPECT_EQ(AffOne + 1, AffTwo);
+    EXPECT_EQ(1 + AffOne, AffTwo);
+    EXPECT_EQ(AffOne + ValOne, AffTwo);
+    EXPECT_EQ(ValOne + AffOne, AffTwo);
+  }
+
+  // Multiplication
+  {
+    EXPECT_EQ(AffTwo * AffTwo, AffFour);
+    EXPECT_EQ(AffTwo * 2, AffFour);
+    EXPECT_EQ(2 * AffTwo, AffFour);
+    EXPECT_EQ(AffTwo * ValTwo, AffFour);
+    EXPECT_EQ(ValTwo * AffTwo, AffFour);
+  }
+
+  // Subtraction
+  {
+    EXPECT_EQ(AffTwo - AffOne, AffOne);
+    EXPECT_EQ(AffTwo - 1, AffOne);
+    EXPECT_EQ(2 - AffOne, AffOne);
+    EXPECT_EQ(AffTwo - ValOne, AffOne);
+    EXPECT_EQ(ValTwo - AffOne, AffOne);
+  }
+
+  // Division
+  {
+    EXPECT_EQ(AffFour / AffTwo, AffTwo);
+    EXPECT_EQ(AffFour / 2, AffTwo);
+    EXPECT_EQ(4 / AffTwo, AffTwo);
+    EXPECT_EQ(AffFour / ValTwo, AffTwo);
+    EXPECT_EQ(AffFour / 2, AffTwo);
+
+    // Dividend is negative (should be rounded towards zero)
+    EXPECT_EQ(AffNegFour / AffThree, AffNegOne);
+    EXPECT_EQ(AffNegFour / 3, AffNegOne);
+    EXPECT_EQ((-4) / AffThree, AffNegOne);
+    EXPECT_EQ(AffNegFour / ValThree, AffNegOne);
+    EXPECT_EQ(AffNegFour / 3, AffNegOne);
+
+    // Divisor is negative (should be rounded towards zero)
+    EXPECT_EQ(AffFour / AffNegThree, AffNegOne);
+    EXPECT_EQ(AffFour / -3, AffNegOne);
+    EXPECT_EQ(4 / AffNegThree, AffNegOne);
+    EXPECT_EQ(AffFour / ValNegThree, AffNegOne);
+    EXPECT_EQ(AffFour / -3, AffNegOne);
+  }
+
+  // Remainder
+  {
+    EXPECT_EQ(AffThree % AffTwo, AffOne);
+    EXPECT_EQ(AffThree % 2, AffOne);
+    EXPECT_EQ(3 % AffTwo, AffOne);
+    EXPECT_EQ(AffThree % ValTwo, AffOne);
+    EXPECT_EQ(ValThree % AffTwo, AffOne);
+
+    // Dividend is negative (should be rounded towards zero)
+    EXPECT_EQ(AffNegFour % AffThree, AffNegOne);
+    EXPECT_EQ(AffNegFour % 3, AffNegOne);
+    EXPECT_EQ((-4) % AffThree, AffNegOne);
+    EXPECT_EQ(AffNegFour % ValThree, AffNegOne);
+    EXPECT_EQ(AffNegFour % 3, AffNegOne);
+
+    // Divisor is negative (should be rounded towards zero)
+    EXPECT_EQ(AffFour % AffNegThree, AffOne);
+    EXPECT_EQ(AffFour % -3, AffOne);
+    EXPECT_EQ(4 % AffNegThree, AffOne);
+    EXPECT_EQ(AffFour % ValNegThree, AffOne);
+    EXPECT_EQ(AffFour % -3, AffOne);
+  }
+}
+
 TEST(Isl, Foreach) {
   std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
                                                         &isl_ctx_free);
 
   auto MapSpace = isl::space(Ctx.get(), 0, 1, 1);
   auto TestBMap = isl::basic_map::universe(MapSpace);
   TestBMap = TestBMap.fix_si(isl::dim::out, 0, 0);
   TestBMap = TestBMap.fix_si(isl::dim::out, 0, 0);