polly/unittests/DeLICM/DeLICMTest.cpp - toolchain/llvm-project - Gitiles

 //===- DeLICMTest.cpp ----------------------------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//

 #include "polly/DeLICM.h"
 #include "gtest/gtest.h"
 #include <isl/map.h>
 #include <isl/set.h>
 #include <isl/stream.h>
 #include <isl/union_map.h>
 #include <isl/union_set.h>
 #include <memory>

 using namespace llvm;
 using namespace polly;

 namespace {

 /// Get the universes of all spaces in @p USet.
 isl::union_set unionSpace(const isl::union_set &USet) {
   auto Result = give(isl_union_set_empty(isl_union_set_get_space(USet.keep())));
   USet.foreach_set([=, &Result](isl::set Set) -> isl::stat {
     auto Space = give(isl_set_get_space(Set.keep()));
     auto Universe = give(isl_set_universe(Space.take()));
     Result = give(isl_union_set_add_set(Result.take(), Universe.take()));
     return isl::stat::ok;
   });
   return Result;
 }

 void completeLifetime(isl::union_set Universe, isl::union_map OccupiedAndKnown,
                       isl::union_set &Occupied, isl::union_map &Known,
                       isl::union_set &Undef) {
   auto ParamSpace = give(isl_union_set_get_space(Universe.keep()));

   if (Undef && !Occupied) {
     assert(!Occupied);
     Occupied = give(isl_union_set_subtract(Universe.copy(), Undef.copy()));
   }

   if (OccupiedAndKnown) {
     assert(!Known);

     Known = isl::union_map::empty(ParamSpace);

     if (!Occupied)
       Occupied = OccupiedAndKnown.domain();

     OccupiedAndKnown.foreach_map([&Known](isl::map Map) -> isl::stat {
       if (isl_map_has_tuple_name(Map.keep(), isl_dim_out) != isl_bool_true)
         return isl::stat::ok;
       Known = give(isl_union_map_add_map(Known.take(), Map.take()));
       return isl::stat::ok;
     });
   }

   if (!Undef) {
     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);
   }

   // Conditions that must hold when returning.
   assert(Occupied);
   assert(Undef);
   assert(Known);
 }

 typedef struct {
   const char *OccupiedStr;
   const char *UndefStr;
   const char *WrittenStr;
 } KnowledgeStr;

 isl::union_set parseSetOrNull(isl_ctx *Ctx, const char *Str) {
   if (!Str)
     return nullptr;
   return isl::union_set(Ctx, Str);
 }

 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, 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.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.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, "Unrelated", &NewId));
   // The space must contains at least one dimension to allow order
   // modifications.
   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.
   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, ExistingKnown,
                           ExistingWritten, ProposedOccupied, {}, ProposedKnown,
                           ProposedWritten));
   EXPECT_EQ(Result,
             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<isl_ctx, decltype(&isl_ctx_free)> 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<isl_ctx, decltype(&isl_ctx_free)> 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);

   // isConflicting should be symmetric.
   EXPECT_EQ(Forward, Backward);

   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.
   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] }", "{}"}));
   EXPECT_FALSE(checkIsConflictingKnown(
       {"{ Dom[i] -> Val[]; Dom[i] -> Phi[] }", nullptr, "{}"},
       {"{ Dom[i] -> Val[] }", nullptr, "{}"}));

   // 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] }"}));
   EXPECT_FALSE(checkIsConflicting({"{ DomA[i] }", nullptr, "{}"},
                                   {"{}", nullptr, "{ DomB[0] }"}));

   // 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] }"}));

   // 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] -> [] }"}));
   EXPECT_FALSE(checkIsConflictingKnown(
       {"{}", nullptr, "{ Dom[0] -> Val[]}"},
       {"{}", nullptr, "{ Dom[0] -> Val[]; Dom[0] -> Phi[] }"}));
 }
 } // anonymous namespace
	//===- DeLICMTest.cpp ----------------------------------------------------===//
	//
	// The LLVM Compiler Infrastructure
	//
	// This file is distributed under the University of Illinois Open Source
	// License. See LICENSE.TXT for details.
	//
	//===----------------------------------------------------------------------===//

	#include "polly/DeLICM.h"
	#include "gtest/gtest.h"
	#include <isl/map.h>
	#include <isl/set.h>
	#include <isl/stream.h>
	#include <isl/union_map.h>
	#include <isl/union_set.h>
	#include <memory>

	using namespace llvm;
	using namespace polly;

	namespace {

	/// Get the universes of all spaces in @p USet.
	isl::union_set unionSpace(const isl::union_set &USet) {
	auto Result = give(isl_union_set_empty(isl_union_set_get_space(USet.keep())));
	USet.foreach_set([=, &Result](isl::set Set) -> isl::stat {
	auto Space = give(isl_set_get_space(Set.keep()));
	auto Universe = give(isl_set_universe(Space.take()));
	Result = give(isl_union_set_add_set(Result.take(), Universe.take()));
	return isl::stat::ok;
	});
	return Result;
	}

	void completeLifetime(isl::union_set Universe, isl::union_map OccupiedAndKnown,
	isl::union_set &Occupied, isl::union_map &Known,
	isl::union_set &Undef) {
	auto ParamSpace = give(isl_union_set_get_space(Universe.keep()));

	if (Undef && !Occupied) {
	assert(!Occupied);
	Occupied = give(isl_union_set_subtract(Universe.copy(), Undef.copy()));
	}

	if (OccupiedAndKnown) {
	assert(!Known);

	Known = isl::union_map::empty(ParamSpace);

	if (!Occupied)
	Occupied = OccupiedAndKnown.domain();

	OccupiedAndKnown.foreach_map([&Known](isl::map Map) -> isl::stat {
	if (isl_map_has_tuple_name(Map.keep(), isl_dim_out) != isl_bool_true)
	return isl::stat::ok;
	Known = give(isl_union_map_add_map(Known.take(), Map.take()));
	return isl::stat::ok;
	});
	}

	if (!Undef) {
	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);
	}

	// Conditions that must hold when returning.
	assert(Occupied);
	assert(Undef);
	assert(Known);
	}

	typedef struct {
	const char *OccupiedStr;
	const char *UndefStr;
	const char *WrittenStr;
	} KnowledgeStr;

	isl::union_set parseSetOrNull(isl_ctx Ctx, const char Str) {
	if (!Str)
	return nullptr;
	return isl::union_set(Ctx, Str);
	}

	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, 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.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.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, "Unrelated", &NewId));
	// The space must contains at least one dimension to allow order
	// modifications.
	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.
	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, ExistingKnown,
	ExistingWritten, ProposedOccupied, {}, ProposedKnown,
	ProposedWritten));
	EXPECT_EQ(Result,
	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<isl_ctx, decltype(&isl_ctx_free)> 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<isl_ctx, decltype(&isl_ctx_free)> 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);

	// isConflicting should be symmetric.
	EXPECT_EQ(Forward, Backward);

	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.
	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] }", "{}"}));
	EXPECT_FALSE(checkIsConflictingKnown(
	{"{ Dom[i] -> Val[]; Dom[i] -> Phi[] }", nullptr, "{}"},
	{"{ Dom[i] -> Val[] }", nullptr, "{}"}));

	// 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] }"}));
	EXPECT_FALSE(checkIsConflicting({"{ DomA[i] }", nullptr, "{}"},
	{"{}", nullptr, "{ DomB[0] }"}));

	// 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] }"}));

	// 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] -> [] }"}));
	EXPECT_FALSE(checkIsConflictingKnown(
	{"{}", nullptr, "{ Dom[0] -> Val[]}"},
	{"{}", nullptr, "{ Dom[0] -> Val[]; Dom[0] -> Phi[] }"}));
	}
	} // anonymous namespace