[Polly][DeLICM] Use Known information when comparing Occupied and Written.

[Meinersbur]

Summary

Do not conflict if a write writes the same value as already known.

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.

[grosser]

Hi Michael,

I really enjoy reviewing these small size patches. Thanks a lot. In general the content of the patch looks great, but I feel the operations you use could possibly simplified (see below). I would be interested in your opinion.

lib/Transform/DeLICM.cpp

684 ↗

(On Diff #95147)

This comment does not seem to be in line with what actually happens. Where do we:

• "remove the writes that write into Proposed.Unused"
• "see wheather the written value is already in Proposed.Known"

It seems what we do is:

• Intersect the Existing Writes with the Currently Occupied values to find the set of possibly conflicting writes.

• See if the set of possibly conflicting writes only contains known values by checking if it is a subset of ProposedFixedKnown.

707 ↗

(On Diff #95147)

This seems more complex as needed. For me the following code also works:

auto ProposedFixedDefs =                                                     
    convertZoneToTimepoints(Proposed.Occupied, true, false);                 
auto ProposedFixedKnown =                                                    
    convertZoneToTimepoints(Proposed.Known, isl::dim::in, true, false);      
auto ExistingConflictingWrites =                                             
    Existing.Written.intersect_domain(ProposedFixedDefs);                    
                                                                             
if (!ExistingConflictingWrites.is_subset(ProposedFixedKnown)) {

Some of the later code can -- if needed at all -- be sunk into the "if (OS)".

Or did I miss something?

738 ↗

(On Diff #95147)

AFAIU this is equivalent to the following code:

auto ProposedWrittenDomain = Proposed.Written.domain();                      
auto ExistingAvailableDefs =                                                 
    convertZoneToTimepoints(Existing.Unused, true, false);                   
auto KnownIdentical = Existing.Known.intersect(Proposed.Written);            
if (!ProposedWrittenDomain.is_subset(                                        
        ExistingAvailableDefs.unite(KnownIdentical.domain()))) {

which is _very_ similar to the earlier code, a lot more concise, and does not even need an expensive subtract. I just now realized that we can avoid the subtract by computing the union of the KnownIdenticalSet with the ExistingAvailableDefs, rather than subtracting it beforehand. The same appraoch likely also applies to D32025.

[Meinersbur]

lib/Transform/DeLICM.cpp

684 ↗

(On Diff #95147)

In my understanding this is exactly what the code below does:

"remove the writes that write into Proposed.Unused"

auto ExistingConflictingWrites = Existing.Written.intersect_domain(ProposedFixedDefs);

ProposedFixedDefs = Proposed.Occupied, i.e. the intersect removes Proposed.Unused.

"see wheather the written value is already in Proposed.Known"

auto SomeWrittenVal = ProposedFixedKnown.intersect(ExistingConflictingWrites);

SomeWrittenVal will contain matched pairs where the value written is the same as the value already known. The final condition is whether all writes overlapping with Proposed.Occupied has a match.

707 ↗

(On Diff #95147)

Added a test case where the difference between your implementation and mine matters.

We could simplify to your version if we assume that Existing.Written contains at most one value (assert(isl_union_map_is_single_valued(Existing.Written))). I want to leave the possibility open to properly handle PHINodes.

738 ↗

(On Diff #95147)

Both implementations do the same. Mine has the union the intersection and adds the unknown value to both arguments such that it survives the intersection. This can indeed be made simpler by doing the union afterwards. I opted to your version (There was a`convertZoneToTimepoints` call missing and I introduced an intermediate result variable IdenticalOrUnused).

[Meinersbur]

• Rebase to r301301
• Adressed Tobias' comments.

[grosser]

Nice, this LGTM.

polly/trunk/lib/Transform/DeLICM.cpp

if (!Proposed.Occupied.is_subset(Matches)) {
               << "Existing Known:       " << ExistingConflictingKnown << "\n";
         if (!ProposedConflictingKnown.is_empty())
           OS->indent(Indent)
               << "Proposed Known:       " << ProposedConflictingKnown << "\n";
       }
       return true;
     }
 
-    // Do the writes in Existing only overwrite unused values in Proposed?
+    // Do the writes in Existing conflict with occupied values in Proposed?
+    //
+    // In order to not conflict, it must either write to unused lifetime or
+    // write the same value. To check, we remove the writes that write into
+    // Proposed.Unused (they never conflict) and then see whether the written
+    // value is already in Proposed.Known. If there are multiple known values
+    // and a written value is known under different names, it is enough when one
+    // of the written values (assuming that they are the same value under
+    // different names, e.g. a PHINode and one of the incoming values) matches
+    // one of the known names.
+    //
     // We convert here the set of lifetimes to actual timepoints. A lifetime is
     // in conflict with a set of write timepoints, if either a live timepoint is
     // clearly within the lifetime or if a write happens at the beginning of the
     // lifetime (where it would conflict with the value that actually writes the
     // value alive). There is no conflict at the end of a lifetime, as the alive
     // value will always be read, before it is overwritten again. The last
     // property holds in Polly for all scalar values and we expect all users of
     // Knowledge to check this property also for accesses to MemoryKind::Array.
     auto ProposedFixedDefs =
         convertZoneToTimepoints(Proposed.Occupied, true, false);
-    auto ExistingWrittenDomain =
-        isl::manage(isl_union_map_domain(Existing.Written.copy()));
-    if (isl_union_set_is_disjoint(ExistingWrittenDomain.keep(),
-                                  ProposedFixedDefs.keep()) != isl_bool_true) {
+    auto ProposedFixedKnown =
+        convertZoneToTimepoints(Proposed.Known, isl::dim::in, true, false);
+
+    auto ExistingConflictingWrites =
+        Existing.Written.intersect_domain(ProposedFixedDefs);
+    auto ExistingConflictingWritesDomain = ExistingConflictingWrites.domain();
+
+    auto CommonWrittenVal =
+        ProposedFixedKnown.intersect(ExistingConflictingWrites);
+    auto CommonWrittenValDomain = CommonWrittenVal.domain();
+
+    if (!ExistingConflictingWritesDomain.is_subset(CommonWrittenValDomain)) {
       if (OS) {
-        auto ConflictingWrites = give(isl_union_set_intersect(
-            ExistingWrittenDomain.copy(), ProposedFixedDefs.copy()));
-        OS->indent(Indent) << "Proposed writes into range used by existing\n";
-        OS->indent(Indent) << "Conflicting writes: " << ConflictingWrites
-                           << "\n";
+        auto ExistingConflictingWritten =
+            ExistingConflictingWrites.subtract_domain(CommonWrittenValDomain);
+        auto ProposedConflictingKnown = ProposedFixedKnown.subtract_domain(
+            ExistingConflictingWritten.domain());
+
+        OS->indent(Indent)
+            << "Proposed a lifetime where there is an Existing write into it\n";
+        OS->indent(Indent) << "Existing conflicting writes: "
+                           << ExistingConflictingWritten << "\n";
+        if (!ProposedConflictingKnown.is_empty())
+          OS->indent(Indent)
+              << "Proposed conflicting known:  " << ProposedConflictingKnown
       }
       return true;
     }
 
-    // Do the new writes in Proposed only overwrite unused values in Existing?
+    // Do the writes in Proposed conflict with occupied values in Existing?
     auto ExistingAvailableDefs =
         convertZoneToTimepoints(Existing.Unused, true, false);
-    auto ProposedWrittenDomain =
-        isl::manage(isl_union_map_domain(Proposed.Written.copy()));
-    if (isl_union_set_is_subset(ProposedWrittenDomain.keep(),
-                                ExistingAvailableDefs.keep()) !=
-        isl_bool_true) {
+    auto ExistingKnownDefs =
+        convertZoneToTimepoints(Existing.Known, isl::dim::in, true, false);
+
+    auto ProposedWrittenDomain = Proposed.Written.domain();
+    auto KnownIdentical = ExistingKnownDefs.intersect(Proposed.Written);
+    auto IdenticalOrUnused =
+        ExistingAvailableDefs.unite(KnownIdentical.domain());
+    if (!ProposedWrittenDomain.is_subset(IdenticalOrUnused)) {
       if (OS) {
-        auto ConflictingWrites = give(isl_union_set_subtract(
-            ProposedWrittenDomain.copy(), ExistingAvailableDefs.copy()));
+        auto Conflicting = ProposedWrittenDomain.subtract(IdenticalOrUnused);
+        auto ExistingConflictingKnown =
+            ExistingKnownDefs.intersect_domain(Conflicting);
+        auto ProposedConflictingWritten =
+            Proposed.Written.intersect_domain(Conflicting);
+
+        OS->indent(Indent) << "Proposed writes into range used by Existing\n";
+        OS->indent(Indent) << "Proposed conflicting writes: "
+                           << ProposedConflictingWritten << "\n";
+        if (!ExistingConflictingKnown.is_empty())
           OS->indent(Indent)
-            << "Proposed a lifetime where there is an Existing write into it\n";
-        OS->indent(Indent) << "Conflicting writes: " << ConflictingWrites
-                           << "\n";
+              << "Existing conflicting known: " << ExistingConflictingKnown
       }
       return true;
     }
 
     // Does Proposed write at the same time as Existing already does (order of
     // writes is undefined)? Writing the same value is permitted.
+    auto ExistingWrittenDomain =
+        isl::manage(isl_union_map_domain(Existing.Written.copy()));
     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)) {

polly/trunk/unittests/DeLICM/DeLICMTest.cpp

TEST(DeLICM, isConflicting) {
   // Dom[1] represents the time between 0 and 1. Now Proposed writes at timestep
   // 0 such that will have a different value between 0 and 1. Hence it is
   // conflicting with Existing.
   EXPECT_TRUE(checkIsConflicting({"{ Dom[1] }", nullptr, "{}"},
                                  {"{}", nullptr, "{ Dom[0] }"}));
   EXPECT_FALSE(checkIsConflicting({"{ Dom[i] : i != 1 }", nullptr, "{}"},
                                   {"{}", nullptr, "{ Dom[0] }"}));
 
+  // Check occupied vs. written with known values.
+  EXPECT_FALSE(checkIsConflictingKnown({"{ Dom[i] -> Val[] }", nullptr, "{}"},
+                                       {"{}", nullptr, "{ Dom[0] -> Val[] }"}));
+  EXPECT_TRUE(checkIsConflictingKnown({"{ Dom[i] -> ValA[] }", nullptr, "{}"},
+                                      {"{}", nullptr, "{ Dom[0] -> ValB[] }"}));
+  EXPECT_TRUE(checkIsConflictingKnown({"{ Dom[i] -> Val[] }", nullptr, "{}"},
+                                      {"{}", nullptr, "{ Dom[0] -> [] }"}));
+  EXPECT_TRUE(checkIsConflictingKnown({"{ Dom[i] -> [] }", nullptr, "{}"},
+                                      {"{}", nullptr, "{ Dom[0] -> Val[] }"}));
+
+  // The same value can be known under multiple names, for instance a PHINode
+  // has the same value as one of the incoming values. One matching pair
+  // suffices.
+  EXPECT_FALSE(checkIsConflictingKnown(
+      {"{ Dom[i] -> Val[]; Dom[i] -> Phi[] }", nullptr, "{}"},
+      {"{}", nullptr, "{ Dom[0] -> Val[] }"}));
+  EXPECT_FALSE(checkIsConflictingKnown(
+      {"{ Dom[i] -> Val[] }", nullptr, "{}"},
+      {"{}", nullptr, "{ Dom[0] -> Val[]; Dom[0] -> Phi[] }"}));
+
   // 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] }"}));