From a8e885d87ca643a2f6030cfda5e2dfb2343e04d1 Mon Sep 17 00:00:00 2001 From: Michael Kruse Date: Thu, 13 Apr 2017 16:32:46 +0000 Subject: [PATCH] [DeLICM] Introduce unittesting infrastructure for Known and Written. NFC. llvm-svn: 300212 --- polly/unittests/DeLICM/DeLICMTest.cpp | 179 ++++++++++++++++++-------- 1 file changed, 126 insertions(+), 53 deletions(-) diff --git a/polly/unittests/DeLICM/DeLICMTest.cpp b/polly/unittests/DeLICM/DeLICMTest.cpp index 8803b07ff648..a1154fc403c8 100644 --- a/polly/unittests/DeLICM/DeLICMTest.cpp +++ b/polly/unittests/DeLICM/DeLICMTest.cpp @@ -32,16 +32,36 @@ isl::union_set unionSpace(const isl::union_set &USet) { return Result; } -void completeLifetime(isl::union_set Universe, isl::union_set &Unknown, +void completeLifetime(isl::union_set Universe, isl::union_map OccupiedAndKnown, + isl::union_set &Occupied, isl::union_map &Known, isl::union_set &Undef) { - if (!Unknown) { + auto ParamSpace = give(isl_union_set_get_space(Universe.keep())); + + if (OccupiedAndKnown) { + assert(!Occupied); + assert(!Known); + + Known = isl::union_map::empty(ParamSpace); + Occupied = OccupiedAndKnown.domain(); + foreachElt(OccupiedAndKnown, [&Known](isl::map Map) { + if (isl_map_has_tuple_name(Map.keep(), isl_dim_out) != isl_bool_true) + return; + Known = give(isl_union_map_add_map(Known.take(), Map.take())); + }); + } + + if (!Occupied) { assert(Undef); - Unknown = give(isl_union_set_subtract(Universe.copy(), Undef.copy())); + Occupied = give(isl_union_set_subtract(Universe.copy(), Undef.copy())); } if (!Undef) { - assert(Unknown); - Undef = give(isl_union_set_subtract(Universe.copy(), Unknown.copy())); + assert(Occupied); + Undef = give(isl_union_set_subtract(Universe.copy(), Occupied.copy())); + } + + if (!Known) { // By default, nothing is known. + Known = isl::union_map::empty(ParamSpace); } } @@ -57,86 +77,129 @@ isl::union_set parseSetOrNull(isl_ctx *Ctx, const char *Str) { return isl::union_set(Ctx, Str); } -bool checkIsConflictingNonsymmetric(KnowledgeStr Existing, - KnowledgeStr Proposed) { - std::unique_ptr Ctx(isl_ctx_alloc(), - &isl_ctx_free); - - // Parse knowledge. - auto ExistingOccupied = parseSetOrNull(Ctx.get(), Existing.OccupiedStr); - auto ExistingUnused = parseSetOrNull(Ctx.get(), Existing.UndefStr); - auto ExistingWritten = parseSetOrNull(Ctx.get(), Existing.WrittenStr); - - auto ProposedOccupied = parseSetOrNull(Ctx.get(), Proposed.OccupiedStr); - auto ProposedUnused = parseSetOrNull(Ctx.get(), Proposed.UndefStr); - auto ProposedWritten = parseSetOrNull(Ctx.get(), Proposed.WrittenStr); +isl::union_map parseMapOrNull(isl_ctx *Ctx, const char *Str) { + if (!Str) + return nullptr; + return isl::union_map(Ctx, Str); +} +bool checkIsConflictingNonsymmetricCommon( + isl_ctx *Ctx, isl::union_map ExistingOccupiedAndKnown, + isl::union_set ExistingUnused, isl::union_map ExistingWritten, + isl::union_map ProposedOccupiedAndKnown, isl::union_set ProposedUnused, + isl::union_map ProposedWritten) { // Determine universe (set of all possible domains). - auto Universe = - give(isl_union_set_empty(isl_space_params_alloc(Ctx.get(), 0))); - if (ExistingOccupied) - Universe = - give(isl_union_set_union(Universe.take(), ExistingOccupied.copy())); + auto Universe = give(isl_union_set_empty(isl_space_params_alloc(Ctx, 0))); + if (ExistingOccupiedAndKnown) + Universe = give(isl_union_set_union( + Universe.take(), ExistingOccupiedAndKnown.domain().take())); if (ExistingUnused) Universe = give(isl_union_set_union(Universe.take(), ExistingUnused.copy())); if (ExistingWritten) - Universe = - give(isl_union_set_union(Universe.take(), ExistingWritten.copy())); - if (ProposedOccupied) - Universe = - give(isl_union_set_union(Universe.take(), ProposedOccupied.copy())); + Universe = give( + isl_union_set_union(Universe.take(), ExistingWritten.domain().take())); + if (ProposedOccupiedAndKnown) + Universe = give(isl_union_set_union( + Universe.take(), ProposedOccupiedAndKnown.domain().take())); if (ProposedUnused) Universe = give(isl_union_set_union(Universe.take(), ProposedUnused.copy())); if (ProposedWritten) - Universe = - give(isl_union_set_union(Universe.take(), ProposedWritten.copy())); + Universe = give( + isl_union_set_union(Universe.take(), ProposedWritten.domain().take())); + Universe = unionSpace(Universe); // Add a space the universe that does not occur anywhere else to ensure // robustness. Use &NewId to ensure that this Id is unique. - isl::id NewId = give(isl_id_alloc(Ctx.get(), "Unrelated", &NewId)); + isl::id NewId = give(isl_id_alloc(Ctx, "Unrelated", &NewId)); // The space must contains at least one dimension to allow order // modifications. - auto NewSpace = give(isl_space_set_alloc(Ctx.get(), 0, 1)); + auto NewSpace = give(isl_space_set_alloc(Ctx, 0, 1)); NewSpace = give(isl_space_set_tuple_id(NewSpace.take(), isl_dim_set, NewId.copy())); auto NewSet = give(isl_set_universe(NewSpace.take())); Universe = give(isl_union_set_add_set(Universe.take(), NewSet.take())); // Using the universe, fill missing data. - completeLifetime(Universe, ExistingOccupied, ExistingUnused); - completeLifetime(Universe, ProposedOccupied, ProposedUnused); - - auto ParamSpace = isl::manage(isl_union_set_get_space(Universe.keep())); - auto EmptyUnionMap = isl::union_map::empty(ParamSpace); - auto ExistingWrittenMap = - isl::manage(isl_union_map_from_domain(ExistingWritten.copy())); - auto ProposedWrittenMap = - isl::manage(isl_union_map_from_domain(ProposedWritten.copy())); - auto Result = isConflicting( - ExistingOccupied, ExistingUnused, EmptyUnionMap, ExistingWrittenMap, - ProposedOccupied, ProposedUnused, EmptyUnionMap, ProposedWrittenMap); + isl::union_set ExistingOccupied; + isl::union_map ExistingKnown; + completeLifetime(Universe, ExistingOccupiedAndKnown, ExistingOccupied, + ExistingKnown, ExistingUnused); + + isl::union_set ProposedOccupied; + isl::union_map ProposedKnown; + completeLifetime(Universe, ProposedOccupiedAndKnown, ProposedOccupied, + ProposedKnown, ProposedUnused); + + auto Result = isConflicting(ExistingOccupied, ExistingUnused, ExistingKnown, + ExistingWritten, ProposedOccupied, ProposedUnused, + ProposedKnown, ProposedWritten); // isConflicting does not require ExistingOccupied nor ProposedUnused and are // implicitly assumed to be the remainder elements. Test the implicitness as // well. EXPECT_EQ(Result, - isConflicting(ExistingOccupied, ExistingUnused, EmptyUnionMap, - ExistingWrittenMap, ProposedOccupied, {}, - EmptyUnionMap, ProposedWrittenMap)); + isConflicting(ExistingOccupied, ExistingUnused, ExistingKnown, + ExistingWritten, ProposedOccupied, {}, ProposedKnown, + ProposedWritten)); EXPECT_EQ(Result, - isConflicting({}, ExistingUnused, EmptyUnionMap, ExistingWrittenMap, - ProposedOccupied, ProposedUnused, EmptyUnionMap, - ProposedWrittenMap)); - EXPECT_EQ(Result, isConflicting({}, ExistingUnused, EmptyUnionMap, - ExistingWrittenMap, ProposedOccupied, {}, - EmptyUnionMap, ProposedWrittenMap)); + isConflicting({}, ExistingUnused, ExistingKnown, ExistingWritten, + ProposedOccupied, ProposedUnused, ProposedKnown, + ProposedWritten)); + EXPECT_EQ(Result, isConflicting({}, ExistingUnused, ExistingKnown, + ExistingWritten, ProposedOccupied, {}, + ProposedKnown, ProposedWritten)); return Result; } +bool checkIsConflictingNonsymmetricKnown(KnowledgeStr Existing, + KnowledgeStr Proposed) { + std::unique_ptr Ctx(isl_ctx_alloc(), + &isl_ctx_free); + + // Parse knowledge. + auto ExistingOccupiedAndKnown = + parseMapOrNull(Ctx.get(), Existing.OccupiedStr); + auto ExistingUnused = parseSetOrNull(Ctx.get(), Existing.UndefStr); + auto ExistingWritten = parseMapOrNull(Ctx.get(), Existing.WrittenStr); + + auto ProposedOccupiedAndKnown = + parseMapOrNull(Ctx.get(), Proposed.OccupiedStr); + auto ProposedUnused = parseSetOrNull(Ctx.get(), Proposed.UndefStr); + auto ProposedWritten = parseMapOrNull(Ctx.get(), Proposed.WrittenStr); + + return checkIsConflictingNonsymmetricCommon( + Ctx.get(), ExistingOccupiedAndKnown, ExistingUnused, ExistingWritten, + ProposedOccupiedAndKnown, ProposedUnused, ProposedWritten); +} + +bool checkIsConflictingNonsymmetric(KnowledgeStr Existing, + KnowledgeStr Proposed) { + std::unique_ptr Ctx(isl_ctx_alloc(), + &isl_ctx_free); + + // Parse knowledge. + auto ExistingOccupied = parseSetOrNull(Ctx.get(), Existing.OccupiedStr); + auto ExistingUnused = parseSetOrNull(Ctx.get(), Existing.UndefStr); + auto ExistingWritten = parseSetOrNull(Ctx.get(), Existing.WrittenStr); + + auto ProposedOccupied = parseSetOrNull(Ctx.get(), Proposed.OccupiedStr); + auto ProposedUnused = parseSetOrNull(Ctx.get(), Proposed.UndefStr); + auto ProposedWritten = parseSetOrNull(Ctx.get(), Proposed.WrittenStr); + + return checkIsConflictingNonsymmetricCommon( + Ctx.get(), + isl::manage(isl_union_map_from_domain(ExistingOccupied.take())), + ExistingUnused, + isl::manage(isl_union_map_from_domain(ExistingWritten.take())), + isl::manage(isl_union_map_from_domain(ProposedOccupied.take())), + ProposedUnused, + isl::manage(isl_union_map_from_domain(ProposedWritten.take()))); +} + bool checkIsConflicting(KnowledgeStr Existing, KnowledgeStr Proposed) { auto Forward = checkIsConflictingNonsymmetric(Existing, Proposed); auto Backward = checkIsConflictingNonsymmetric(Proposed, Existing); @@ -147,6 +210,16 @@ bool checkIsConflicting(KnowledgeStr Existing, KnowledgeStr Proposed) { return Forward || Backward; } +bool checkIsConflictingKnown(KnowledgeStr Existing, KnowledgeStr Proposed) { + auto Forward = checkIsConflictingNonsymmetricKnown(Existing, Proposed); + auto Backward = checkIsConflictingNonsymmetricKnown(Proposed, Existing); + + // checkIsConflictingKnown should be symmetric. + EXPECT_EQ(Forward, Backward); + + return Forward || Backward; +} + TEST(DeLICM, isConflicting) { // Check occupied vs. occupied. -- 2.34.1