polly/unittests/DeLICM/DeLICMTest.cpp

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