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 = isl::union_set::empty(USet.get_space());
  27   USet.foreach_set([=, &Result](isl::set Set) -> isl::stat {
  28     auto Space = Set.get_space();
  29     auto Universe = isl::set::universe(Space);
  30     Result = Result.add_set(Universe);
  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 = Universe.get_space();
  40
  41   if (Undef && !Occupied) {
  42     assert(!Occupied);
  43     Occupied = Universe.subtract(Undef);
  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 = Known.add_map(Map);
  58       return isl::stat::ok;
  59     });
  60   }
  61
  62   if (!Undef) {
  63     assert(Occupied);
  64     Undef = Universe.subtract(Occupied);
  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 = isl::union_set::empty(isl::space::params_alloc(Ctx, 0));
 102   if (ExistingOccupiedAndKnown)
 103     Universe = Universe.unite(ExistingOccupiedAndKnown.domain());
 104   if (ExistingUnused)
 105     Universe = Universe.unite(ExistingUnused);
 106   if (ExistingWritten)
 107     Universe = Universe.unite(ExistingWritten.domain());
 108   if (ProposedOccupiedAndKnown)
 109     Universe = Universe.unite(ProposedOccupiedAndKnown.domain());
 110   if (ProposedUnused)
 111     Universe = Universe.unite(ProposedUnused);
 112   if (ProposedWritten)
 113     Universe = Universe.unite(ProposedWritten.domain());
 114
 115   Universe = unionSpace(Universe);
 116
 117   // Add a space the universe that does not occur anywhere else to ensure
 118   // robustness. Use &NewId to ensure that this Id is unique.
 119   isl::id NewId = isl::id::alloc(Ctx, "Unrelated", &NewId);
 120   // The space must contains at least one dimension to allow order
 121   // modifications.
 122   auto NewSpace = isl::space(Ctx, 0, 1);
 123   NewSpace = NewSpace.set_tuple_id(isl::dim::set, NewId);
 124   auto NewSet = isl::set::universe(NewSpace);
 125   Universe = Universe.add_set(NewSet);
 126
 127   // Using the universe, fill missing data.
 128   isl::union_set ExistingOccupied;
 129   isl::union_map ExistingKnown;
 130   completeLifetime(Universe, ExistingOccupiedAndKnown, ExistingOccupied,
 131                    ExistingKnown, ExistingUnused);
 132
 133   isl::union_set ProposedOccupied;
 134   isl::union_map ProposedKnown;
 135   completeLifetime(Universe, ProposedOccupiedAndKnown, ProposedOccupied,
 136                    ProposedKnown, ProposedUnused);
 137
 138   auto Result = isConflicting(ExistingOccupied, ExistingUnused, ExistingKnown,
 139                               ExistingWritten, ProposedOccupied, ProposedUnused,
 140                               ProposedKnown, ProposedWritten);
 141
 142   // isConflicting does not require ExistingOccupied nor ProposedUnused and are
 143   // implicitly assumed to be the remainder elements. Test the implicitness as
 144   // well.
 145   EXPECT_EQ(Result,
 146             isConflicting(ExistingOccupied, ExistingUnused, ExistingKnown,
 147                           ExistingWritten, ProposedOccupied, {}, ProposedKnown,
 148                           ProposedWritten));
 149   EXPECT_EQ(Result,
 150             isConflicting({}, ExistingUnused, ExistingKnown, ExistingWritten,
 151                           ProposedOccupied, ProposedUnused, ProposedKnown,
 152                           ProposedWritten));
 153   EXPECT_EQ(Result, isConflicting({}, ExistingUnused, ExistingKnown,
 154                                   ExistingWritten, ProposedOccupied, {},
 155                                   ProposedKnown, ProposedWritten));
 156
 157   return Result;
 158 }
 159
 160 bool checkIsConflictingNonsymmetricKnown(KnowledgeStr Existing,
 161                                          KnowledgeStr Proposed) {
 162   std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
 163                                                         &isl_ctx_free);
 164
 165   // Parse knowledge.
 166   auto ExistingOccupiedAndKnown =
 167       parseMapOrNull(Ctx.get(), Existing.OccupiedStr);
 168   auto ExistingUnused = parseSetOrNull(Ctx.get(), Existing.UndefStr);
 169   auto ExistingWritten = parseMapOrNull(Ctx.get(), Existing.WrittenStr);
 170
 171   auto ProposedOccupiedAndKnown =
 172       parseMapOrNull(Ctx.get(), Proposed.OccupiedStr);
 173   auto ProposedUnused = parseSetOrNull(Ctx.get(), Proposed.UndefStr);
 174   auto ProposedWritten = parseMapOrNull(Ctx.get(), Proposed.WrittenStr);
 175
 176   return checkIsConflictingNonsymmetricCommon(
 177       Ctx.get(), ExistingOccupiedAndKnown, ExistingUnused, ExistingWritten,
 178       ProposedOccupiedAndKnown, ProposedUnused, ProposedWritten);
 179 }
 180
 181 bool checkIsConflictingNonsymmetric(KnowledgeStr Existing,
 182                                     KnowledgeStr Proposed) {
 183   std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
 184                                                         &isl_ctx_free);
 185
 186   // Parse knowledge.
 187   auto ExistingOccupied = parseSetOrNull(Ctx.get(), Existing.OccupiedStr);
 188   auto ExistingUnused = parseSetOrNull(Ctx.get(), Existing.UndefStr);
 189   auto ExistingWritten = parseSetOrNull(Ctx.get(), Existing.WrittenStr);
 190
 191   auto ProposedOccupied = parseSetOrNull(Ctx.get(), Proposed.OccupiedStr);
 192   auto ProposedUnused = parseSetOrNull(Ctx.get(), Proposed.UndefStr);
 193   auto ProposedWritten = parseSetOrNull(Ctx.get(), Proposed.WrittenStr);
 194
 195   return checkIsConflictingNonsymmetricCommon(
 196       Ctx.get(), isl::union_map::from_domain(ExistingOccupied), ExistingUnused,
 197       isl::union_map::from_domain(ExistingWritten),
 198       isl::union_map::from_domain(ProposedOccupied), ProposedUnused,
 199       isl::union_map::from_domain(ProposedWritten));
 200 }
 201
 202 bool checkIsConflicting(KnowledgeStr Existing, KnowledgeStr Proposed) {
 203   auto Forward = checkIsConflictingNonsymmetric(Existing, Proposed);
 204   auto Backward = checkIsConflictingNonsymmetric(Proposed, Existing);
 205
 206   // isConflicting should be symmetric.
 207   EXPECT_EQ(Forward, Backward);
 208
 209   return Forward || Backward;
 210 }
 211
 212 bool checkIsConflictingKnown(KnowledgeStr Existing, KnowledgeStr Proposed) {
 213   auto Forward = checkIsConflictingNonsymmetricKnown(Existing, Proposed);
 214   auto Backward = checkIsConflictingNonsymmetricKnown(Proposed, Existing);
 215
 216   // checkIsConflictingKnown should be symmetric.
 217   EXPECT_EQ(Forward, Backward);
 218
 219   return Forward || Backward;
 220 }
 221
 222 TEST(DeLICM, isConflicting) {
 223
 224   // Check occupied vs. occupied.
 225   EXPECT_TRUE(
 226       checkIsConflicting({"{ Dom[i] }", nullptr, "{}"}, {nullptr, "{}", "{}"}));
 227   EXPECT_TRUE(checkIsConflicting({"{ Dom[i] }", nullptr, "{}"},
 228                                  {"{ Dom[i] }", nullptr, "{}"}));
 229   EXPECT_FALSE(checkIsConflicting({"{ Dom[0] }", nullptr, "{}"},
 230                                   {nullptr, "{ Dom[0] }", "{}"}));
 231   EXPECT_FALSE(checkIsConflicting({"{ Dom[i] : i != 0 }", nullptr, "{}"},
 232                                   {"{ Dom[0] }", nullptr, "{}"}));
 233
 234   // Check occupied vs. occupied with known values.
 235   EXPECT_FALSE(checkIsConflictingKnown({"{ Dom[i] -> Val[] }", nullptr, "{}"},
 236                                        {"{ Dom[i] -> Val[] }", nullptr, "{}"}));
 237   EXPECT_TRUE(checkIsConflictingKnown({"{ Dom[i] -> ValA[] }", nullptr, "{}"},
 238                                       {"{ Dom[i] -> ValB[] }", nullptr, "{}"}));
 239   EXPECT_TRUE(checkIsConflictingKnown({"{ Dom[i] -> Val[] }", nullptr, "{}"},
 240                                       {"{ Dom[i] -> [] }", nullptr, "{}"}));
 241   EXPECT_FALSE(checkIsConflictingKnown({"{ Dom[0] -> Val[] }", nullptr, "{}"},
 242                                        {nullptr, "{ Dom[0] }", "{}"}));
 243   EXPECT_FALSE(checkIsConflictingKnown(
 244       {"{ Dom[i] -> Val[]; Dom[i] -> Phi[] }", nullptr, "{}"},
 245       {"{ Dom[i] -> Val[] }", nullptr, "{}"}));
 246
 247   // An implementation using subtract would have exponential runtime on patterns
 248   // such as this one.
 249   EXPECT_TRUE(checkIsConflictingKnown(
 250       {"{ Dom[i0,i1,i2,i3,i4,i5,i6,i7,i8,i9,i10,i11,i12,i13,i14,i15]"
 251        "-> Val[] }",
 252        nullptr, "{}"},
 253       {"[p0,p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,p11,p12,p13,p14,p15,q0,"
 254        "q1,q2,q3,q4,q5,q6,q7,q8,q9,q10,q11,q12,q13,q14,q15] -> {"
 255        "Dom[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] -> Val[];"
 256        "Dom[p0,p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,p11,p12,p13,p14,p15] -> Val[];"
 257        "Dom[q0,q1,q2,q3,q4,q5,q6,q7,q8,q9,q10,q11,q12,q13,q14,q15] -> Val[] }",
 258        "{}", "{}"}));
 259
 260   // Check occupied vs. written.
 261   EXPECT_TRUE(
 262       checkIsConflicting({nullptr, "{}", "{}"}, {"{}", nullptr, "{ Dom[0] }"}));
 263   EXPECT_FALSE(
 264       checkIsConflicting({"{}", nullptr, "{}"}, {"{}", nullptr, "{ Dom[0] }"}));
 265
 266   EXPECT_TRUE(checkIsConflicting({"{ Dom[i] }", nullptr, "{}"},
 267                                  {"{}", nullptr, "{ Dom[0] }"}));
 268   EXPECT_FALSE(checkIsConflicting({"{ DomA[i] }", nullptr, "{}"},
 269                                   {"{}", nullptr, "{ DomB[0] }"}));
 270
 271   // Dom[1] represents the time between 0 and 1. Now Proposed writes at timestep
 272   // 0 such that will have a different value between 0 and 1. Hence it is
 273   // conflicting with Existing.
 274   EXPECT_TRUE(checkIsConflicting({"{ Dom[1] }", nullptr, "{}"},
 275                                  {"{}", nullptr, "{ Dom[0] }"}));
 276   EXPECT_FALSE(checkIsConflicting({"{ Dom[i] : i != 1 }", nullptr, "{}"},
 277                                   {"{}", nullptr, "{ Dom[0] }"}));
 278
 279   // Check occupied vs. written with known values.
 280   EXPECT_FALSE(checkIsConflictingKnown({"{ Dom[i] -> Val[] }", nullptr, "{}"},
 281                                        {"{}", nullptr, "{ Dom[0] -> Val[] }"}));
 282   EXPECT_TRUE(checkIsConflictingKnown({"{ Dom[i] -> ValA[] }", nullptr, "{}"},
 283                                       {"{}", nullptr, "{ Dom[0] -> ValB[] }"}));
 284   EXPECT_TRUE(checkIsConflictingKnown({"{ Dom[i] -> Val[] }", nullptr, "{}"},
 285                                       {"{}", nullptr, "{ Dom[0] -> [] }"}));
 286   EXPECT_TRUE(checkIsConflictingKnown({"{ Dom[i] -> [] }", nullptr, "{}"},
 287                                       {"{}", nullptr, "{ Dom[0] -> Val[] }"}));
 288
 289   // The same value can be known under multiple names, for instance a PHINode
 290   // has the same value as one of the incoming values. One matching pair
 291   // suffices.
 292   EXPECT_FALSE(checkIsConflictingKnown(
 293       {"{ Dom[i] -> Val[]; Dom[i] -> Phi[] }", nullptr, "{}"},
 294       {"{}", nullptr, "{ Dom[0] -> Val[] }"}));
 295   EXPECT_FALSE(checkIsConflictingKnown(
 296       {"{ Dom[i] -> Val[] }", nullptr, "{}"},
 297       {"{}", nullptr, "{ Dom[0] -> Val[]; Dom[0] -> Phi[] }"}));
 298
 299   // Check written vs. written.
 300   EXPECT_TRUE(checkIsConflicting({"{}", nullptr, "{ Dom[0] }"},
 301                                  {"{}", nullptr, "{ Dom[0] }"}));
 302   EXPECT_FALSE(checkIsConflicting({"{}", nullptr, "{ Dom[-1] }"},
 303                                   {"{}", nullptr, "{ Dom[0] }"}));
 304   EXPECT_FALSE(checkIsConflicting({"{}", nullptr, "{ Dom[1] }"},
 305                                   {"{}", nullptr, "{ Dom[0] }"}));
 306
 307   // Check written vs. written with known values.
 308   EXPECT_FALSE(checkIsConflictingKnown({"{}", nullptr, "{ Dom[0] -> Val[] }"},
 309                                        {"{}", nullptr, "{ Dom[0] -> Val[] }"}));
 310   EXPECT_TRUE(checkIsConflictingKnown({"{}", nullptr, "{ Dom[0] -> ValA[] }"},
 311                                       {"{}", nullptr, "{ Dom[0] -> ValB[] }"}));
 312   EXPECT_TRUE(checkIsConflictingKnown({"{}", nullptr, "{ Dom[0] -> Val[] }"},
 313                                       {"{}", nullptr, "{ Dom[0] -> [] }"}));
 314   EXPECT_FALSE(checkIsConflictingKnown(
 315       {"{}", nullptr, "{ Dom[0] -> Val[]}"},
 316       {"{}", nullptr, "{ Dom[0] -> Val[]; Dom[0] -> Phi[] }"}));
 317 }
 318 } // anonymous namespace