unittests/DeLICM/DeLICMTest.cpp

   1 //===- DeLICMTest.cpp ----------------------------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include "polly/DeLICM.h"
  11 #include "gtest/gtest.h"
  12 #include <isl/map.h>
  13 #include <isl/set.h>
  14 #include <isl/stream.h>
  15 #include <isl/union_map.h>
  16 #include <isl/union_set.h>
  17 #include <memory>
  18
  19 using namespace llvm;
  20 using namespace polly;
  21
  22 namespace {
  23
  24 /// Get the universes of all spaces in @p USet.
  25 isl::union_set unionSpace(const isl::union_set &USet) {
  26   auto Result = give(isl_union_set_empty(isl_union_set_get_space(USet.keep())));
  27   USet.foreach_set([=, &Result](isl::set Set) -> isl::stat {
  28     auto Space = give(isl_set_get_space(Set.keep()));
  29     auto Universe = give(isl_set_universe(Space.take()));
  30     Result = give(isl_union_set_add_set(Result.take(), Universe.take()));
  31     return isl::stat::ok;
  32   });
  33   return Result;
  34 }
  35
  36 void completeLifetime(isl::union_set Universe, isl::union_map OccupiedAndKnown,
  37                       isl::union_set &Occupied, isl::union_map &Known,
  38                       isl::union_set &Undef) {
  39   auto ParamSpace = give(isl_union_set_get_space(Universe.keep()));
  40
  41   if (Undef && !Occupied) {
  42     assert(!Occupied);
  43     Occupied = give(isl_union_set_subtract(Universe.copy(), Undef.copy()));
  44   }
  45
  46   if (OccupiedAndKnown) {
  47     assert(!Known);
  48
  49     Known = isl::union_map::empty(ParamSpace);
  50
  51     if (!Occupied)
  52       Occupied = OccupiedAndKnown.domain();
  53
  54     OccupiedAndKnown.foreach_map([&Known](isl::map Map) -> isl::stat {
  55       if (isl_map_has_tuple_name(Map.keep(), isl_dim_out) != isl_bool_true)
  56         return isl::stat::ok;
  57       Known = give(isl_union_map_add_map(Known.take(), Map.take()));
  58       return isl::stat::ok;
  59     });
  60   }
  61
  62   if (!Undef) {
  63     assert(Occupied);
  64     Undef = give(isl_union_set_subtract(Universe.copy(), Occupied.copy()));
  65   }
  66
  67   if (!Known) { // By default, nothing is known.
  68     Known = isl::union_map::empty(ParamSpace);
  69   }
  70
  71   // Conditions that must hold when returning.
  72   assert(Occupied);
  73   assert(Undef);
  74   assert(Known);
  75 }
  76
  77 typedef struct {
  78   const char *OccupiedStr;
  79   const char *UndefStr;
  80   const char *WrittenStr;
  81 } KnowledgeStr;
  82
  83 isl::union_set parseSetOrNull(isl_ctx *Ctx, const char *Str) {
  84   if (!Str)
  85     return nullptr;
  86   return isl::union_set(Ctx, Str);
  87 }
  88
  89 isl::union_map parseMapOrNull(isl_ctx *Ctx, const char *Str) {
  90   if (!Str)
  91     return nullptr;
  92   return isl::union_map(Ctx, Str);
  93 }
  94
  95 bool checkIsConflictingNonsymmetricCommon(
  96     isl_ctx *Ctx, isl::union_map ExistingOccupiedAndKnown,
  97     isl::union_set ExistingUnused, isl::union_map ExistingWritten,
  98     isl::union_map ProposedOccupiedAndKnown, isl::union_set ProposedUnused,
  99     isl::union_map ProposedWritten) {
 100   // Determine universe (set of all possible domains).
 101   auto Universe = give(isl_union_set_empty(isl_space_params_alloc(Ctx, 0)));
 102   if (ExistingOccupiedAndKnown)
 103     Universe = give(isl_union_set_union(
 104         Universe.take(), ExistingOccupiedAndKnown.domain().take()));
 105   if (ExistingUnused)
 106     Universe =
 107         give(isl_union_set_union(Universe.take(), ExistingUnused.copy()));
 108   if (ExistingWritten)
 109     Universe = give(
 110         isl_union_set_union(Universe.take(), ExistingWritten.domain().take()));
 111   if (ProposedOccupiedAndKnown)
 112     Universe = give(isl_union_set_union(
 113         Universe.take(), ProposedOccupiedAndKnown.domain().take()));
 114   if (ProposedUnused)
 115     Universe =
 116         give(isl_union_set_union(Universe.take(), ProposedUnused.copy()));
 117   if (ProposedWritten)
 118     Universe = give(
 119         isl_union_set_union(Universe.take(), ProposedWritten.domain().take()));
 120
 121   Universe = unionSpace(Universe);
 122
 123   // Add a space the universe that does not occur anywhere else to ensure
 124   // robustness. Use &NewId to ensure that this Id is unique.
 125   isl::id NewId = give(isl_id_alloc(Ctx, "Unrelated", &NewId));
 126   // The space must contains at least one dimension to allow order
 127   // modifications.
 128   auto NewSpace = give(isl_space_set_alloc(Ctx, 0, 1));
 129   NewSpace =
 130       give(isl_space_set_tuple_id(NewSpace.take(), isl_dim_set, NewId.copy()));
 131   auto NewSet = give(isl_set_universe(NewSpace.take()));
 132   Universe = give(isl_union_set_add_set(Universe.take(), NewSet.take()));
 133
 134   // Using the universe, fill missing data.
 135   isl::union_set ExistingOccupied;
 136   isl::union_map ExistingKnown;
 137   completeLifetime(Universe, ExistingOccupiedAndKnown, ExistingOccupied,
 138                    ExistingKnown, ExistingUnused);
 139
 140   isl::union_set ProposedOccupied;
 141   isl::union_map ProposedKnown;
 142   completeLifetime(Universe, ProposedOccupiedAndKnown, ProposedOccupied,
 143                    ProposedKnown, ProposedUnused);
 144
 145   auto Result = isConflicting(ExistingOccupied, ExistingUnused, ExistingKnown,
 146                               ExistingWritten, ProposedOccupied, ProposedUnused,
 147                               ProposedKnown, ProposedWritten);
 148
 149   // isConflicting does not require ExistingOccupied nor ProposedUnused and are
 150   // implicitly assumed to be the remainder elements. Test the implicitness as
 151   // well.
 152   EXPECT_EQ(Result,
 153             isConflicting(ExistingOccupied, ExistingUnused, ExistingKnown,
 154                           ExistingWritten, ProposedOccupied, {}, ProposedKnown,
 155                           ProposedWritten));
 156   EXPECT_EQ(Result,
 157             isConflicting({}, ExistingUnused, ExistingKnown, ExistingWritten,
 158                           ProposedOccupied, ProposedUnused, ProposedKnown,
 159                           ProposedWritten));
 160   EXPECT_EQ(Result, isConflicting({}, ExistingUnused, ExistingKnown,
 161                                   ExistingWritten, ProposedOccupied, {},
 162                                   ProposedKnown, ProposedWritten));
 163
 164   return Result;
 165 }
 166
 167 bool checkIsConflictingNonsymmetricKnown(KnowledgeStr Existing,
 168                                          KnowledgeStr Proposed) {
 169   std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
 170                                                         &isl_ctx_free);
 171
 172   // Parse knowledge.
 173   auto ExistingOccupiedAndKnown =
 174       parseMapOrNull(Ctx.get(), Existing.OccupiedStr);
 175   auto ExistingUnused = parseSetOrNull(Ctx.get(), Existing.UndefStr);
 176   auto ExistingWritten = parseMapOrNull(Ctx.get(), Existing.WrittenStr);
 177
 178   auto ProposedOccupiedAndKnown =
 179       parseMapOrNull(Ctx.get(), Proposed.OccupiedStr);
 180   auto ProposedUnused = parseSetOrNull(Ctx.get(), Proposed.UndefStr);
 181   auto ProposedWritten = parseMapOrNull(Ctx.get(), Proposed.WrittenStr);
 182
 183   return checkIsConflictingNonsymmetricCommon(
 184       Ctx.get(), ExistingOccupiedAndKnown, ExistingUnused, ExistingWritten,
 185       ProposedOccupiedAndKnown, ProposedUnused, ProposedWritten);
 186 }
 187
 188 bool checkIsConflictingNonsymmetric(KnowledgeStr Existing,
 189                                     KnowledgeStr Proposed) {
 190   std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
 191                                                         &isl_ctx_free);
 192
 193   // Parse knowledge.
 194   auto ExistingOccupied = parseSetOrNull(Ctx.get(), Existing.OccupiedStr);
 195   auto ExistingUnused = parseSetOrNull(Ctx.get(), Existing.UndefStr);
 196   auto ExistingWritten = parseSetOrNull(Ctx.get(), Existing.WrittenStr);
 197
 198   auto ProposedOccupied = parseSetOrNull(Ctx.get(), Proposed.OccupiedStr);
 199   auto ProposedUnused = parseSetOrNull(Ctx.get(), Proposed.UndefStr);
 200   auto ProposedWritten = parseSetOrNull(Ctx.get(), Proposed.WrittenStr);
 201
 202   return checkIsConflictingNonsymmetricCommon(
 203       Ctx.get(),
 204       isl::manage(isl_union_map_from_domain(ExistingOccupied.take())),
 205       ExistingUnused,
 206       isl::manage(isl_union_map_from_domain(ExistingWritten.take())),
 207       isl::manage(isl_union_map_from_domain(ProposedOccupied.take())),
 208       ProposedUnused,
 209       isl::manage(isl_union_map_from_domain(ProposedWritten.take())));
 210 }
 211
 212 bool checkIsConflicting(KnowledgeStr Existing, KnowledgeStr Proposed) {
 213   auto Forward = checkIsConflictingNonsymmetric(Existing, Proposed);
 214   auto Backward = checkIsConflictingNonsymmetric(Proposed, Existing);
 215
 216   // isConflicting should be symmetric.
 217   EXPECT_EQ(Forward, Backward);
 218
 219   return Forward || Backward;
 220 }
 221
 222 bool checkIsConflictingKnown(KnowledgeStr Existing, KnowledgeStr Proposed) {
 223   auto Forward = checkIsConflictingNonsymmetricKnown(Existing, Proposed);
 224   auto Backward = checkIsConflictingNonsymmetricKnown(Proposed, Existing);
 225
 226   // checkIsConflictingKnown should be symmetric.
 227   EXPECT_EQ(Forward, Backward);
 228
 229   return Forward || Backward;
 230 }
 231
 232 TEST(DeLICM, isConflicting) {
 233
 234   // Check occupied vs. occupied.
 235   EXPECT_TRUE(
 236       checkIsConflicting({"{ Dom[i] }", nullptr, "{}"}, {nullptr, "{}", "{}"}));
 237   EXPECT_TRUE(checkIsConflicting({"{ Dom[i] }", nullptr, "{}"},
 238                                  {"{ Dom[i] }", nullptr, "{}"}));
 239   EXPECT_FALSE(checkIsConflicting({"{ Dom[0] }", nullptr, "{}"},
 240                                   {nullptr, "{ Dom[0] }", "{}"}));
 241   EXPECT_FALSE(checkIsConflicting({"{ Dom[i] : i != 0 }", nullptr, "{}"},
 242                                   {"{ Dom[0] }", nullptr, "{}"}));
 243
 244   // Check occupied vs. occupied with known values.
 245   EXPECT_FALSE(checkIsConflictingKnown({"{ Dom[i] -> Val[] }", nullptr, "{}"},
 246                                        {"{ Dom[i] -> Val[] }", nullptr, "{}"}));
 247   EXPECT_TRUE(checkIsConflictingKnown({"{ Dom[i] -> ValA[] }", nullptr, "{}"},
 248                                       {"{ Dom[i] -> ValB[] }", nullptr, "{}"}));
 249   EXPECT_TRUE(checkIsConflictingKnown({"{ Dom[i] -> Val[] }", nullptr, "{}"},
 250                                       {"{ Dom[i] -> [] }", nullptr, "{}"}));
 251   EXPECT_FALSE(checkIsConflictingKnown({"{ Dom[0] -> Val[] }", nullptr, "{}"},
 252                                        {nullptr, "{ Dom[0] }", "{}"}));
 253   EXPECT_FALSE(checkIsConflictingKnown(
 254       {"{ Dom[i] -> Val[]; Dom[i] -> Phi[] }", nullptr, "{}"},
 255       {"{ Dom[i] -> Val[] }", nullptr, "{}"}));
 256
 257   // An implementation using subtract would have exponential runtime on patterns
 258   // such as this one.
 259   EXPECT_TRUE(checkIsConflictingKnown(
 260       {"{ Dom[i0,i1,i2,i3,i4,i5,i6,i7,i8,i9,i10,i11,i12,i13,i14,i15]"
 261        "-> Val[] }",
 262        nullptr, "{}"},
 263       {"[p0,p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,p11,p12,p13,p14,p15,q0,"
 264        "q1,q2,q3,q4,q5,q6,q7,q8,q9,q10,q11,q12,q13,q14,q15] -> {"
 265        "Dom[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] -> Val[];"
 266        "Dom[p0,p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,p11,p12,p13,p14,p15] -> Val[];"
 267        "Dom[q0,q1,q2,q3,q4,q5,q6,q7,q8,q9,q10,q11,q12,q13,q14,q15] -> Val[] }",
 268        "{}", "{}"}));
 269
 270   // Check occupied vs. written.
 271   EXPECT_TRUE(
 272       checkIsConflicting({nullptr, "{}", "{}"}, {"{}", nullptr, "{ Dom[0] }"}));
 273   EXPECT_FALSE(
 274       checkIsConflicting({"{}", nullptr, "{}"}, {"{}", nullptr, "{ Dom[0] }"}));
 275
 276   EXPECT_TRUE(checkIsConflicting({"{ Dom[i] }", nullptr, "{}"},
 277                                  {"{}", nullptr, "{ Dom[0] }"}));
 278   EXPECT_FALSE(checkIsConflicting({"{ DomA[i] }", nullptr, "{}"},
 279                                   {"{}", nullptr, "{ DomB[0] }"}));
 280
 281   // Dom[1] represents the time between 0 and 1. Now Proposed writes at timestep
 282   // 0 such that will have a different value between 0 and 1. Hence it is
 283   // conflicting with Existing.
 284   EXPECT_TRUE(checkIsConflicting({"{ Dom[1] }", nullptr, "{}"},
 285                                  {"{}", nullptr, "{ Dom[0] }"}));
 286   EXPECT_FALSE(checkIsConflicting({"{ Dom[i] : i != 1 }", nullptr, "{}"},
 287                                   {"{}", nullptr, "{ Dom[0] }"}));
 288
 289   // Check occupied vs. written with known values.
 290   EXPECT_FALSE(checkIsConflictingKnown({"{ Dom[i] -> Val[] }", nullptr, "{}"},
 291                                        {"{}", nullptr, "{ Dom[0] -> Val[] }"}));
 292   EXPECT_TRUE(checkIsConflictingKnown({"{ Dom[i] -> ValA[] }", nullptr, "{}"},
 293                                       {"{}", nullptr, "{ Dom[0] -> ValB[] }"}));
 294   EXPECT_TRUE(checkIsConflictingKnown({"{ Dom[i] -> Val[] }", nullptr, "{}"},
 295                                       {"{}", nullptr, "{ Dom[0] -> [] }"}));
 296   EXPECT_TRUE(checkIsConflictingKnown({"{ Dom[i] -> [] }", nullptr, "{}"},
 297                                       {"{}", nullptr, "{ Dom[0] -> Val[] }"}));
 298
 299   // The same value can be known under multiple names, for instance a PHINode
 300   // has the same value as one of the incoming values. One matching pair
 301   // suffices.
 302   EXPECT_FALSE(checkIsConflictingKnown(
 303       {"{ Dom[i] -> Val[]; Dom[i] -> Phi[] }", nullptr, "{}"},
 304       {"{}", nullptr, "{ Dom[0] -> Val[] }"}));
 305   EXPECT_FALSE(checkIsConflictingKnown(
 306       {"{ Dom[i] -> Val[] }", nullptr, "{}"},
 307       {"{}", nullptr, "{ Dom[0] -> Val[]; Dom[0] -> Phi[] }"}));
 308
 309   // Check written vs. written.
 310   EXPECT_TRUE(checkIsConflicting({"{}", nullptr, "{ Dom[0] }"},
 311                                  {"{}", nullptr, "{ Dom[0] }"}));
 312   EXPECT_FALSE(checkIsConflicting({"{}", nullptr, "{ Dom[-1] }"},
 313                                   {"{}", nullptr, "{ Dom[0] }"}));
 314   EXPECT_FALSE(checkIsConflicting({"{}", nullptr, "{ Dom[1] }"},
 315                                   {"{}", nullptr, "{ Dom[0] }"}));
 316
 317   // Check written vs. written with known values.
 318   EXPECT_FALSE(checkIsConflictingKnown({"{}", nullptr, "{ Dom[0] -> Val[] }"},
 319                                        {"{}", nullptr, "{ Dom[0] -> Val[] }"}));
 320   EXPECT_TRUE(checkIsConflictingKnown({"{}", nullptr, "{ Dom[0] -> ValA[] }"},
 321                                       {"{}", nullptr, "{ Dom[0] -> ValB[] }"}));
 322   EXPECT_TRUE(checkIsConflictingKnown({"{}", nullptr, "{ Dom[0] -> Val[] }"},
 323                                       {"{}", nullptr, "{ Dom[0] -> [] }"}));
 324   EXPECT_FALSE(checkIsConflictingKnown(
 325       {"{}", nullptr, "{ Dom[0] -> Val[]}"},
 326       {"{}", nullptr, "{ Dom[0] -> Val[]; Dom[0] -> Phi[] }"}));
 327 }
 328 } // anonymous namespace