[Polly][DeLICM] Use Known information when comparing Existing.Written and Proposed.Written. NFC.

[grosser]

Hi Michael,

this looks good to me. Could you possibly still add one test case where both Expected and Proposed map to '{}'. I also have two small ideas how the code could been written a little bit simpler. Nothing serious. Feel free to apply them or not. Otherwise, this looks all fine.

(I also would not call this NFC)

lib/Transform/DeLICM.cpp

425 ↗

(On Diff #95148)

This could possibly be written simpler as

UMap = UMap.subtract_range(makeUnknown());

assuming we introduce a makeUnknown() function.

788 ↗

(On Diff #95148)

If you intersect before filtering, you just need to apply the filter once.

[Meinersbur]

In D32027#727734, @grosser wrote:

Hi Michael,

this looks good to me. Could you possibly still add one test case where both Expected and Proposed map to '{}'.

It is already tested by e.g.

EXPECT_TRUE(
    checkIsConflicting({"{ Dom[i] }", nullptr, "{}"}, {nullptr, "{}", "{}"}));

(I also would not call this NFC)

Interesting. How do you define "NFC"?

My idea of adding NFC was that this does not (at least it is not intended) change the output of any Polly pass and therefore won't break any compilation. I don't count additional unit-tests and internal interface changes as functional change.

lib/Transform/DeLICM.cpp

425 ↗

(On Diff #95148)

This would turn a linear-time function into an exponential-worst-time function due to its use of the intLP solver. Also, isl_map_subtract unconditionally calls normalization functions such as isl_basic_map_simplify and isl_map_compute_divs.

788 ↗

(On Diff #95148)

The idea of calling filterKnownValInst early is that the unknown spaces do not need to be computed just to throw them away afterwards.

[grosser]

The definition of NFC is a little blurry in general, I assume.

In the most strict sense, it is really just comment, formatting changes, and renamings. But yes, we use it sometimes also for functional changes, where the output is not expected to change. However, as this is a rather large change and even unit tests are effected, maybe it helps to clarify to add a small sentence:

"This change only affects unit tests, but no functional changes are expected on LLVM-IR, as no Known information is yet extracted and consequently this functionality is only triggered through unit tests."

It is already tested by e.g.

EXPECT_TRUE(

checkIsConflicting({"{ Dom[i] }", nullptr, "{}"}, {nullptr, "{}", "{}"}));

OK, I missed this one.

In general, this patch is clearly correct. I added some comments to give you some options, but please go ahead and choose what seems best for you. Most of my remarks are personal style comments only.

lib/Transform/DeLICM.cpp

425 ↗

(On Diff #95148)

We have so many exponential worst-case functions, one more likely does not matter. The question is if we expect problems in practice. I commonly avoid 'subtract' as it indeed can become expensive, but I would assume subtracting universe sets should be fast. If it is not, we should probably fix isl.

I would prefer to keep the code simpler, and then add optimizations where needed. Again, the code is not super complex either. So I don't feel strong regarding what you choose.

788 ↗

(On Diff #95148)

I generally prefer simplicity over performance optimizations, as long as we don't do anything clearly inefficient.
Now, the difference is not very large. I will trust here your choice.

polly/trunk/lib/Transform/DeLICM.cpp

for (auto *MA : *Stmt) {
 
     assert(MA->getAccessValue() == MA->getBaseAddr());
     if (MA->getAccessValue() == InputVal)
       return MA;
   }
   return nullptr;
 }
 
+/// Return whether @p Map maps to an unknown value.
+///
+/// @param { [] -> ValInst[] }
+bool isMapToUnknown(const isl::map &Map) {
+  auto Space = give(isl_space_range(isl_map_get_space(Map.keep())));
+  return !isl_map_has_tuple_id(Map.keep(), isl_dim_set) &&
+         !isl_space_is_wrapping(Space.keep()) &&
+         isl_map_dim(Map.keep(), isl_dim_out) == 0;
+}
+
+/// Return only the mappings that map to known values.
+///
+/// @param UMap { [] -> ValInst[] }
+///
+/// @return { [] -> ValInst[] }
+isl::union_map filterKnownValInst(const isl::union_map &UMap) {
+  auto Result = give(isl_union_map_empty(isl_union_map_get_space(UMap.keep())));
+  UMap.foreach_map([=, &Result](isl::map Map) -> isl::stat {
+    if (!isMapToUnknown(Map))
+      Result = give(isl_union_map_add_map(Result.take(), Map.take()));
+    return isl::stat::ok;
+  });
+  return Result;
+}
+
 /// Try to find a 'natural' extension of a mapped to elements outside its
 /// domain.
 ///
 /// @param Relevant The map with mapping that may not be modified.
 /// @param Universe The domain to which @p Relevant needs to be extended.
 ///
 /// @return A map with that associates the domain elements of @p Relevant to the
 ///         same elements and in addition the elements of @p Universe to some
if (isl_union_set_is_subset(ProposedWrittenDomain.keep(),
             << "Proposed a lifetime where there is an Existing write into it\n";
         OS->indent(Indent) << "Conflicting writes: " << ConflictingWrites
                            << "\n";
       }
       return true;
     }
 
     // Does Proposed write at the same time as Existing already does (order of
-    // writes is undefined)?
-    if (isl_union_set_is_disjoint(ExistingWrittenDomain.keep(),
-                                  ProposedWrittenDomain.keep()) !=
-        isl_bool_true) {
+    // writes is undefined)? Writing the same value is permitted.
+    auto BothWritten =
+        Existing.Written.domain().intersect(Proposed.Written.domain());
+    auto ExistingKnownWritten = filterKnownValInst(Existing.Written);
+    auto ProposedKnownWritten = filterKnownValInst(Proposed.Written);
+    auto CommonWritten =
+        ExistingKnownWritten.intersect(ProposedKnownWritten).domain();
+
+    if (!BothWritten.is_subset(CommonWritten)) {
       if (OS) {
-        auto ConflictingWrites = give(isl_union_set_intersect(
-            ExistingWrittenDomain.copy(), ProposedWrittenDomain.copy()));
+        auto Conflicting = BothWritten.subtract(CommonWritten);
+        auto ExistingConflictingWritten =
+            Existing.Written.intersect_domain(Conflicting);
+        auto ProposedConflictingWritten =
+            Proposed.Written.intersect_domain(Conflicting);
+
         OS->indent(Indent) << "Proposed writes at the same time as an already "
                               "Existing write\n";
-        OS->indent(Indent) << "Conflicting writes: " << ConflictingWrites
-                           << "\n";
+        OS->indent(Indent) << "Conflicting writes: " << Conflicting << "\n";
+        if (!ExistingConflictingWritten.is_empty())
+          OS->indent(Indent)
+              << "Exiting write:      " << ExistingConflictingWritten << "\n";
+        if (!ProposedConflictingWritten.is_empty())
+          OS->indent(Indent)
+              << "Proposed write:     " << ProposedConflictingWritten << "\n";
       }
       return true;
     }
 
     return false;
   }
 };
 

polly/trunk/unittests/DeLICM/DeLICMTest.cpp

TEST(DeLICM, isConflicting) {
 
   // Check written vs. written.
   EXPECT_TRUE(checkIsConflicting({"{}", nullptr, "{ Dom[0] }"},
                                  {"{}", nullptr, "{ Dom[0] }"}));
   EXPECT_FALSE(checkIsConflicting({"{}", nullptr, "{ Dom[-1] }"},
                                   {"{}", nullptr, "{ Dom[0] }"}));
   EXPECT_FALSE(checkIsConflicting({"{}", nullptr, "{ Dom[1] }"},
                                   {"{}", nullptr, "{ Dom[0] }"}));
+
+  // Check written vs. written with known values.
+  EXPECT_FALSE(checkIsConflictingKnown({"{}", nullptr, "{ Dom[0] -> Val[] }"},
+                                       {"{}", nullptr, "{ Dom[0] -> Val[] }"}));
+  EXPECT_TRUE(checkIsConflictingKnown({"{}", nullptr, "{ Dom[0] -> ValA[] }"},
+                                      {"{}", nullptr, "{ Dom[0] -> ValB[] }"}));
+  EXPECT_TRUE(checkIsConflictingKnown({"{}", nullptr, "{ Dom[0] -> Val[] }"},
+                                      {"{}", nullptr, "{ Dom[0] -> [] }"}));
 }
 } // anonymous namespace