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

[Meinersbur]

Summary

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,

thank you for reducing the size of the proposed patches. This is now a lot easier to review in-depth! Thanks a lot.

First, I don't think this is a 'NFC'. We clearly change the semantics of the code (as shown by the unit tests), but the tests are just expected to not yet influence the IR we generate. Instead of calling it 'NFC', I would state that this currently only affects the unit tests.

Technically the patch looks correct. However, it seems more complicated than necessary. Is this some kind of performance tuning?

Also, I had some problems understanding the comments. I added some of the thoughts I had while reading the comments. Maybe they can help to make the comments a little more clear.

lib/Transform/DeLICM.cpp

381 ↗

(On Diff #95146)

Nice. Can you possibly add a comment that repeats the information that "Written values that cannot be identified are represented by an unknown ValInst[] (an unnamed tuple of 0 dimension). It conflicts with itself. " and add a comment that more details can be found in the documentation for known?

633 ↗

(On Diff #95146)

conflicting -> conflict

635 ↗

(On Diff #95146)

I was confused why you wrote "element / lifetime interval", as I did not understand if these were identical terms for the same thing or different things. Maybe you can clarify in half a sentence what element and lifetime mean here. Maybe something like:

"In order to not conflict, one of the following conditions must apply for each element or each lifetime. (We reason about single elements in case ... and about lifetimes in case ...)"

641 ↗

(On Diff #95146)

I am surprised you formulate this as symmetric condition. The code below does not seem to be symmetric, as it does not even look at Proposed.Unused. Meaning, it would not return true if a value is in Existing.Occupied and not in Proposed.Unused. For me, it would probably have been easier to understand if the comment would be formulated closer to the asymmetric check the code performs.

E.g., something like the following:

In order to not conflict, one of the following conditions must apply:

1. If occupied in Proposed, it is unused in Existing

2. If occupied in Proposed and occupied in Existing, the Known value in proposed must match the known value in Existing.

If the behavior is indeed symmetric, it might make sense to mention this afterwards and explain why the asymmetric code indeed results in symmetric behavior.

645 ↗

(On Diff #95146)

conditions -> condition
will also apply -> also applies

I did not understand what you mean by "Instead of partitioning the lifetimes into a part occupied by both". I would probably have calculated this as:

+    auto KnownIdentical = Proposed.Known.intersect(Existing.Known).domain();
+    auto ProposedOccupied = Proposed.Occupied.subtract(KnownIdentical);
+    if (!ProposedOccupied.is_subset(Existing.Unused)) {

This has the benefit that we do not affect compile time for cases where no Known information is available. Also, this 'unknown' stuff does not need to be explained. Was there a reason you did not take this approach?

If you found cases where such a subtract would become too expensive, it would be good to have a such a test case committed and describe both the simple and the more complex solution as well as the reason why the more complex solution was taken.

646 ↗

(On Diff #95146)

Not sure what you mean by "the value occupying Proposed"?

650 ↗

(On Diff #95146)

Has this later check already been committed? Are you indeed referring to a later commit, or just to the line where SomeVal is computed?

657 ↗

(On Diff #95146)

What does SomeVal mean?

660 ↗

(On Diff #95146)

I initially thought you could just compare ProposedValues and ExistingValues directly, but a problem arises in situations where values are known in Proposed and unused in Existing. In this case the ProposedValues are not a subset of the ExistingValues, even though the Proposed Knowledge is indeed not conflicting with the Existing Knowledge. It would be nice to explain this situation.

unittests/DeLICM/DeLICMTest.cpp

244 ↗

(On Diff #95146)

Can you add test cases:

EXPECT_TRUE(checkIsConflictingKnown(
   {"{ Dom[i] -> [] }", nullptr, "{}"},
   {"{ Dom[i] -> [] }", nullptr, "{}"}
));

[grosser]

Hi Michael,

it also seems as if as part of this commit and the next two commits you exploit more of the new isl C++ bindings in isConflicting. It might make sense to just have a first [NFC] which switches the complete function over and commit this change ahead of time. In general, after the C++ bindings are now mostly through, it seems we can be more free in moving parts of Polly over. At least from my perspective, patches that just move parts of Polly step by step to the new bindings are in such obvious cases as here probably OK to commit even without pre-commit review.

[Meinersbur]

lib/Transform/DeLICM.cpp

381 ↗

(On Diff #95146)

Note that a more detailed explanation of what "ValInst" means is part of the makeValInst documentation in D31247.

I expanded the comment here anyway.

635 ↗

(On Diff #95146)

The domain has the form `[Element[] -> Zone[]]` which I tried to express as "element / lifetime interval". I.e. the cross product, not the union as I would understand from your suggestion.

I'll try to reformulate.

641 ↗

(On Diff #95146)

The conceptional behavior of isConflicting is indeed symmetric, as tested by DeLICMTests.

Asymmetry comes in because "Existing" defines occupied, but "Proposed" defines unused, which was done to avoid a complement operation.

The comment first describes what the code intends to do (which is as mentioned symmetric) and then how this behavior was implemented.

I'd be very confused if it was the other way around. How can I understand an implementation without knowing what it was supposed to do? That could be called reverse engineering.

645 ↗

(On Diff #95146)

Your code does exactly what I described in "instead of ..." part. I added a test case where the subtract would blow up.

If Known is empty, the unites just return the Unused/Occupied set. No additional cost.

650 ↗

(On Diff #95146)

removed

657 ↗

(On Diff #95146)

Renamed to MatchingVals

unittests/DeLICM/DeLICMTest.cpp

244 ↗

(On Diff #95146)

This is identical to

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

at line 118.

[Meinersbur]

Addressed Tobias' comments.

[grosser]

lgtm

lib/Transform/DeLICM.cpp

379–380 ↗

(On Diff #96491)

BE represented

684 ↗

(On Diff #96491)

these TO check

polly/trunk/lib/Transform/DeLICM.cpp

auto UMap = computeScalarReachingDefinition(
       Schedule, give(isl_union_set_from_set(Writes.take())), InclDef,
       InclRedef);
 
   auto ResultSpace = give(isl_space_map_from_domain_and_range(
       ScatterSpace.take(), DomainSpace.take()));
   return singleton(UMap, ResultSpace);
 }
 
+/// Create a domain-to-unknown value mapping.
+///
+/// Value instances that do not represent a specific value are represented by an
+/// unnamed tuple of 0 dimensions. Its meaning depends on the context. It can
+/// either mean a specific but unknown value which cannot be represented by
+/// other means. It conflicts with itself because those two unknown ValInsts may
+/// have different concrete values at runtime.
+///
+/// The other meaning is an arbitrary or wildcard value that can be chosen
+/// freely, like LLVM's undef. If matched with an unknown ValInst, there is no
+/// conflict.
+///
+/// @param Domain { Domain[] }
+///
+/// @return { Domain[] -> ValInst[] }
+isl::union_map makeUnknownForDomain(isl::union_set Domain) {
+  return give(isl_union_map_from_domain(Domain.take()));
+}
+
 /// If InputVal is not defined in the stmt itself, return the MemoryAccess that
 /// reads the scalar. Return nullptr otherwise (if the value is defined in the
 /// scop, or is synthesizable).
 MemoryAccess *getInputAccessOf(Value *InputVal, ScopStmt *Stmt) {
   for (auto *MA : *Stmt) {
     if (!MA->isRead())
       continue;
     if (!MA->isLatestScalarKind())
if (Existing.Occupied && Proposed.Unused) {
       auto ProposedUniverse = give(isl_union_set_union(Proposed.Occupied.copy(),
                                                        Proposed.Unused.copy()));
       assert(isl_union_set_is_equal(ExistingUniverse.keep(),
                                     ProposedUniverse.keep()) == isl_bool_true &&
              "Both inputs' Knowledges must be over the same universe");
     }
 #endif
 
-    // Are the new lifetimes required for Proposed unused in Existing?
-    if (isl_union_set_is_subset(Proposed.Occupied.keep(),
-                                Existing.Unused.keep()) != isl_bool_true) {
+    // Do the Existing and Proposed lifetimes conflict?
+    //
+    // Lifetimes are described as the cross-product of array elements and zone
+    // intervals in which they are alive (the space { [Element[] -> Zone[]] }).
+    // In the following we call this "element/lifetime interval".
+    //
+    // In order to not conflict, one of the following conditions must apply for
+    // each element/lifetime interval:
+    //
+    // 1. If occupied in one of the knowledges, it is unused in the other.
+    //
+    //   - or -
+    //
+    // 2. Both contain the same value.
+    //
+    // Instead of partitioning the element/lifetime intervals into a part that
+    // both Knowledges occupy (which requires an expensive subtraction) and for
+    // these to check whether they are known to be the same value, we check only
+    // the second condition and ensure that it also applies when then first
+    // condition is true. This is done by adding a wildcard value to
+    // Proposed.Known and Existing.Unused such that they match as a common known
+    // value. We use the "unknown ValInst" for this purpose. Every
+    // Existing.Unused may match with an unknown Proposed.Occupied because these
+    // never are in conflict with each other.
+    auto ProposedOccupiedAnyVal = makeUnknownForDomain(Proposed.Occupied);
+    auto ProposedValues = Proposed.Known.unite(ProposedOccupiedAnyVal);
+
+    auto ExistingUnusedAnyVal = makeUnknownForDomain(Existing.Unused);
+    auto ExistingValues = Existing.Known.unite(ExistingUnusedAnyVal);
+
+    auto MatchingVals = ExistingValues.intersect(ProposedValues);
+    auto Matches = MatchingVals.domain();
+
+    // Any Proposed.Occupied must either have a match between the known values
+    // of Existing and Occupied, or be in Existing.Unused. In the latter case,
+    // the previously added "AnyVal" will match each other.
+    if (!Proposed.Occupied.is_subset(Matches)) {
       if (OS) {
-        auto ConflictingLifetimes = give(isl_union_set_subtract(
-            Proposed.Occupied.copy(), Existing.Unused.copy()));
-        OS->indent(Indent) << "Proposed lifetimes are not unused in existing\n";
-        OS->indent(Indent) << "Conflicting lifetimes: " << ConflictingLifetimes
-                           << "\n";
+        auto Conflicting = Proposed.Occupied.subtract(Matches);
+        auto ExistingConflictingKnown =
+            Existing.Known.intersect_domain(Conflicting);
+        auto ProposedConflictingKnown =
+            Proposed.Known.intersect_domain(Conflicting);
+
+        OS->indent(Indent) << "Proposed lifetime conflicting with Existing's\n";
+        OS->indent(Indent) << "Conflicting occupied: " << Conflicting << "\n";
+        if (!ExistingConflictingKnown.is_empty())
+          OS->indent(Indent)
+              << "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?
     // 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

polly/trunk/unittests/DeLICM/DeLICMTest.cpp

EXPECT_TRUE(
       checkIsConflicting({"{ Dom[i] }", nullptr, "{}"}, {nullptr, "{}", "{}"}));
   EXPECT_TRUE(checkIsConflicting({"{ Dom[i] }", nullptr, "{}"},
                                  {"{ Dom[i] }", nullptr, "{}"}));
   EXPECT_FALSE(checkIsConflicting({"{ Dom[0] }", nullptr, "{}"},
                                   {nullptr, "{ Dom[0] }", "{}"}));
   EXPECT_FALSE(checkIsConflicting({"{ Dom[i] : i != 0 }", nullptr, "{}"},
                                   {"{ Dom[0] }", nullptr, "{}"}));
 
+  // Check occupied vs. occupied with known values.
+  EXPECT_FALSE(checkIsConflictingKnown({"{ Dom[i] -> Val[] }", nullptr, "{}"},
+                                       {"{ Dom[i] -> Val[] }", nullptr, "{}"}));
+  EXPECT_TRUE(checkIsConflictingKnown({"{ Dom[i] -> ValA[] }", nullptr, "{}"},
+                                      {"{ Dom[i] -> ValB[] }", nullptr, "{}"}));
+  EXPECT_TRUE(checkIsConflictingKnown({"{ Dom[i] -> Val[] }", nullptr, "{}"},
+                                      {"{ Dom[i] -> [] }", nullptr, "{}"}));
+  EXPECT_FALSE(checkIsConflictingKnown({"{ Dom[0] -> Val[] }", nullptr, "{}"},
+                                       {nullptr, "{ Dom[0] }", "{}"}));
+
+  // An implementation using subtract would have exponential runtime on patterns
+  // such as this one.
+  EXPECT_TRUE(checkIsConflictingKnown(
+      {"{ Dom[i0,i1,i2,i3,i4,i5,i6,i7,i8,i9,i10,i11,i12,i13,i14,i15]"
+       "-> Val[] }",
+       nullptr, "{}"},
+      {"[p0,p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,p11,p12,p13,p14,p15,q0,"
+       "q1,q2,q3,q4,q5,q6,q7,q8,q9,q10,q11,q12,q13,q14,q15] -> {"
+       "Dom[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] -> Val[];"
+       "Dom[p0,p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,p11,p12,p13,p14,p15] -> Val[];"
+       "Dom[q0,q1,q2,q3,q4,q5,q6,q7,q8,q9,q10,q11,q12,q13,q14,q15] -> Val[] }",
+       "{}", "{}"}));
+
   // Check occupied vs. written.
   EXPECT_TRUE(
       checkIsConflicting({nullptr, "{}", "{}"}, {"{}", nullptr, "{ Dom[0] }"}));
   EXPECT_FALSE(
       checkIsConflicting({"{}", nullptr, "{}"}, {"{}", nullptr, "{ Dom[0] }"}));
 
   EXPECT_TRUE(checkIsConflicting({"{ Dom[i] }", nullptr, "{}"},
                                  {"{}", nullptr, "{ Dom[0] }"}));