unittests/DeLICM/DeLICMTest.cpp - llvm-project/polly - Git at Google

 //===- DeLICMTest.cpp ----------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//

 #include "polly/DeLICM.h"
 #include "polly/Support/ISLTools.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 = isl::union_set::empty(USet.ctx());
   for (isl::set Set : USet.get_set_list()) {
     isl::space Space = Set.get_space();
     isl::set Universe = isl::set::universe(Space);
     Result = Result.unite(Universe);
   }
   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 = Universe.get_space();

   if (!Undef.is_null() && Occupied.is_null()) {
     assert(Occupied.is_null());
     Occupied = Universe.subtract(Undef);
   }

   if (!OccupiedAndKnown.is_null()) {
     assert(Known.is_null());

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

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

     for (isl::map Map : OccupiedAndKnown.get_map_list()) {
       if (!Map.has_tuple_name(isl::dim::out))
         continue;
       Known = Known.unite(Map);
     }
   }

   if (Undef.is_null()) {
     assert(!Occupied.is_null());
     Undef = Universe.subtract(Occupied);
   }

   if (Known.is_null()) { // By default, nothing is known.
     Known = isl::union_map::empty(ParamSpace.ctx());
   }

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

 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 {};
   return isl::union_set(Ctx, Str);
 }

 isl::union_map parseMapOrNull(isl_ctx *Ctx, const char *Str) {
   if (!Str)
     return {};
   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 = isl::union_set::empty(Ctx);
   if (!ExistingOccupiedAndKnown.is_null())
     Universe = Universe.unite(ExistingOccupiedAndKnown.domain());
   if (!ExistingUnused.is_null())
     Universe = Universe.unite(ExistingUnused);
   if (!ExistingWritten.is_null())
     Universe = Universe.unite(ExistingWritten.domain());
   if (!ProposedOccupiedAndKnown.is_null())
     Universe = Universe.unite(ProposedOccupiedAndKnown.domain());
   if (!ProposedUnused.is_null())
     Universe = Universe.unite(ProposedUnused);
   if (!ProposedWritten.is_null())
     Universe = Universe.unite(ProposedWritten.domain());

   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 = isl::id::alloc(Ctx, "Unrelated", &NewId);
   // The space must contains at least one dimension to allow order
   // modifications.
   auto NewSpace = isl::space(Ctx, 0, 1);
   NewSpace = NewSpace.set_tuple_id(isl::dim::set, NewId);
   auto NewSet = isl::set::universe(NewSpace);
   Universe = Universe.unite(NewSet);

   // 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::union_map::from_domain(ExistingOccupied), ExistingUnused,
       isl::union_map::from_domain(ExistingWritten),
       isl::union_map::from_domain(ProposedOccupied), ProposedUnused,
       isl::union_map::from_domain(ProposedWritten));
 }

 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 ----------------------------------------------------===//
	//
	// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
	// See https://llvm.org/LICENSE.txt for license information.
	// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
	//
	//===----------------------------------------------------------------------===//

	#include "polly/DeLICM.h"
	#include "polly/Support/ISLTools.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 = isl::union_set::empty(USet.ctx());
	for (isl::set Set : USet.get_set_list()) {
	isl::space Space = Set.get_space();
	isl::set Universe = isl::set::universe(Space);
	Result = Result.unite(Universe);
	}
	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 = Universe.get_space();

	if (!Undef.is_null() && Occupied.is_null()) {
	assert(Occupied.is_null());
	Occupied = Universe.subtract(Undef);
	}

	if (!OccupiedAndKnown.is_null()) {
	assert(Known.is_null());

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

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

	for (isl::map Map : OccupiedAndKnown.get_map_list()) {
	if (!Map.has_tuple_name(isl::dim::out))
	continue;
	Known = Known.unite(Map);
	}
	}

	if (Undef.is_null()) {
	assert(!Occupied.is_null());
	Undef = Universe.subtract(Occupied);
	}

	if (Known.is_null()) { // By default, nothing is known.
	Known = isl::union_map::empty(ParamSpace.ctx());
	}

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

	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 {};
	return isl::union_set(Ctx, Str);
	}

	isl::union_map parseMapOrNull(isl_ctx Ctx, const char Str) {
	if (!Str)
	return {};
	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 = isl::union_set::empty(Ctx);
	if (!ExistingOccupiedAndKnown.is_null())
	Universe = Universe.unite(ExistingOccupiedAndKnown.domain());
	if (!ExistingUnused.is_null())
	Universe = Universe.unite(ExistingUnused);
	if (!ExistingWritten.is_null())
	Universe = Universe.unite(ExistingWritten.domain());
	if (!ProposedOccupiedAndKnown.is_null())
	Universe = Universe.unite(ProposedOccupiedAndKnown.domain());
	if (!ProposedUnused.is_null())
	Universe = Universe.unite(ProposedUnused);
	if (!ProposedWritten.is_null())
	Universe = Universe.unite(ProposedWritten.domain());

	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 = isl::id::alloc(Ctx, "Unrelated", &NewId);
	// The space must contains at least one dimension to allow order
	// modifications.
	auto NewSpace = isl::space(Ctx, 0, 1);
	NewSpace = NewSpace.set_tuple_id(isl::dim::set, NewId);
	auto NewSet = isl::set::universe(NewSpace);
	Universe = Universe.unite(NewSet);

	// 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::union_map::from_domain(ExistingOccupied), ExistingUnused,
	isl::union_map::from_domain(ExistingWritten),
	isl::union_map::from_domain(ProposedOccupied), ProposedUnused,
	isl::union_map::from_domain(ProposedWritten));
	}

	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