317 lines · cpp
1//===- DeLICMTest.cpp ----------------------------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#include "polly/DeLICM.h"10#include "polly/Support/ISLTools.h"11#include "gtest/gtest.h"12#include <isl/map.h>13#include <isl/set.h>14#include <isl/stream.h>15#include <isl/union_map.h>16#include <isl/union_set.h>17#include <memory>18 19using namespace llvm;20using namespace polly;21 22namespace {23 24/// Get the universes of all spaces in @p USet.25isl::union_set unionSpace(const isl::union_set &USet) {26 auto Result = isl::union_set::empty(USet.ctx());27 for (isl::set Set : USet.get_set_list()) {28 isl::space Space = Set.get_space();29 isl::set Universe = isl::set::universe(Space);30 Result = Result.unite(Universe);31 }32 return Result;33}34 35void completeLifetime(isl::union_set Universe, isl::union_map OccupiedAndKnown,36 isl::union_set &Occupied, isl::union_map &Known,37 isl::union_set &Undef) {38 auto ParamSpace = Universe.get_space();39 40 if (!Undef.is_null() && Occupied.is_null()) {41 assert(Occupied.is_null());42 Occupied = Universe.subtract(Undef);43 }44 45 if (!OccupiedAndKnown.is_null()) {46 assert(Known.is_null());47 48 Known = isl::union_map::empty(ParamSpace.ctx());49 50 if (Occupied.is_null())51 Occupied = OccupiedAndKnown.domain();52 53 for (isl::map Map : OccupiedAndKnown.get_map_list()) {54 if (!Map.has_tuple_name(isl::dim::out))55 continue;56 Known = Known.unite(Map);57 }58 }59 60 if (Undef.is_null()) {61 assert(!Occupied.is_null());62 Undef = Universe.subtract(Occupied);63 }64 65 if (Known.is_null()) { // By default, nothing is known.66 Known = isl::union_map::empty(ParamSpace.ctx());67 }68 69 // Conditions that must hold when returning.70 assert(!Occupied.is_null());71 assert(!Undef.is_null());72 assert(!Known.is_null());73}74 75typedef struct {76 const char *OccupiedStr;77 const char *UndefStr;78 const char *WrittenStr;79} KnowledgeStr;80 81isl::union_set parseSetOrNull(isl_ctx *Ctx, const char *Str) {82 if (!Str)83 return {};84 return isl::union_set(Ctx, Str);85}86 87isl::union_map parseMapOrNull(isl_ctx *Ctx, const char *Str) {88 if (!Str)89 return {};90 return isl::union_map(Ctx, Str);91}92 93bool checkIsConflictingNonsymmetricCommon(94 isl_ctx *Ctx, isl::union_map ExistingOccupiedAndKnown,95 isl::union_set ExistingUnused, isl::union_map ExistingWritten,96 isl::union_map ProposedOccupiedAndKnown, isl::union_set ProposedUnused,97 isl::union_map ProposedWritten) {98 // Determine universe (set of all possible domains).99 auto Universe = isl::union_set::empty(Ctx);100 if (!ExistingOccupiedAndKnown.is_null())101 Universe = Universe.unite(ExistingOccupiedAndKnown.domain());102 if (!ExistingUnused.is_null())103 Universe = Universe.unite(ExistingUnused);104 if (!ExistingWritten.is_null())105 Universe = Universe.unite(ExistingWritten.domain());106 if (!ProposedOccupiedAndKnown.is_null())107 Universe = Universe.unite(ProposedOccupiedAndKnown.domain());108 if (!ProposedUnused.is_null())109 Universe = Universe.unite(ProposedUnused);110 if (!ProposedWritten.is_null())111 Universe = Universe.unite(ProposedWritten.domain());112 113 Universe = unionSpace(Universe);114 115 // Add a space the universe that does not occur anywhere else to ensure116 // robustness. Use &NewId to ensure that this Id is unique.117 isl::id NewId = isl::id::alloc(Ctx, "Unrelated", &NewId);118 // The space must contains at least one dimension to allow order119 // modifications.120 auto NewSpace = isl::space(Ctx, 0, 1);121 NewSpace = NewSpace.set_tuple_id(isl::dim::set, NewId);122 auto NewSet = isl::set::universe(NewSpace);123 Universe = Universe.unite(NewSet);124 125 // Using the universe, fill missing data.126 isl::union_set ExistingOccupied;127 isl::union_map ExistingKnown;128 completeLifetime(Universe, ExistingOccupiedAndKnown, ExistingOccupied,129 ExistingKnown, ExistingUnused);130 131 isl::union_set ProposedOccupied;132 isl::union_map ProposedKnown;133 completeLifetime(Universe, ProposedOccupiedAndKnown, ProposedOccupied,134 ProposedKnown, ProposedUnused);135 136 auto Result = isConflicting(ExistingOccupied, ExistingUnused, ExistingKnown,137 ExistingWritten, ProposedOccupied, ProposedUnused,138 ProposedKnown, ProposedWritten);139 140 // isConflicting does not require ExistingOccupied nor ProposedUnused and are141 // implicitly assumed to be the remainder elements. Test the implicitness as142 // well.143 EXPECT_EQ(Result,144 isConflicting(ExistingOccupied, ExistingUnused, ExistingKnown,145 ExistingWritten, ProposedOccupied, {}, ProposedKnown,146 ProposedWritten));147 EXPECT_EQ(Result,148 isConflicting({}, ExistingUnused, ExistingKnown, ExistingWritten,149 ProposedOccupied, ProposedUnused, ProposedKnown,150 ProposedWritten));151 EXPECT_EQ(Result, isConflicting({}, ExistingUnused, ExistingKnown,152 ExistingWritten, ProposedOccupied, {},153 ProposedKnown, ProposedWritten));154 155 return Result;156}157 158bool checkIsConflictingNonsymmetricKnown(KnowledgeStr Existing,159 KnowledgeStr Proposed) {160 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),161 &isl_ctx_free);162 163 // Parse knowledge.164 auto ExistingOccupiedAndKnown =165 parseMapOrNull(Ctx.get(), Existing.OccupiedStr);166 auto ExistingUnused = parseSetOrNull(Ctx.get(), Existing.UndefStr);167 auto ExistingWritten = parseMapOrNull(Ctx.get(), Existing.WrittenStr);168 169 auto ProposedOccupiedAndKnown =170 parseMapOrNull(Ctx.get(), Proposed.OccupiedStr);171 auto ProposedUnused = parseSetOrNull(Ctx.get(), Proposed.UndefStr);172 auto ProposedWritten = parseMapOrNull(Ctx.get(), Proposed.WrittenStr);173 174 return checkIsConflictingNonsymmetricCommon(175 Ctx.get(), ExistingOccupiedAndKnown, ExistingUnused, ExistingWritten,176 ProposedOccupiedAndKnown, ProposedUnused, ProposedWritten);177}178 179bool checkIsConflictingNonsymmetric(KnowledgeStr Existing,180 KnowledgeStr Proposed) {181 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),182 &isl_ctx_free);183 184 // Parse knowledge.185 auto ExistingOccupied = parseSetOrNull(Ctx.get(), Existing.OccupiedStr);186 auto ExistingUnused = parseSetOrNull(Ctx.get(), Existing.UndefStr);187 auto ExistingWritten = parseSetOrNull(Ctx.get(), Existing.WrittenStr);188 189 auto ProposedOccupied = parseSetOrNull(Ctx.get(), Proposed.OccupiedStr);190 auto ProposedUnused = parseSetOrNull(Ctx.get(), Proposed.UndefStr);191 auto ProposedWritten = parseSetOrNull(Ctx.get(), Proposed.WrittenStr);192 193 return checkIsConflictingNonsymmetricCommon(194 Ctx.get(), isl::union_map::from_domain(ExistingOccupied), ExistingUnused,195 isl::union_map::from_domain(ExistingWritten),196 isl::union_map::from_domain(ProposedOccupied), ProposedUnused,197 isl::union_map::from_domain(ProposedWritten));198}199 200bool checkIsConflicting(KnowledgeStr Existing, KnowledgeStr Proposed) {201 auto Forward = checkIsConflictingNonsymmetric(Existing, Proposed);202 auto Backward = checkIsConflictingNonsymmetric(Proposed, Existing);203 204 // isConflicting should be symmetric.205 EXPECT_EQ(Forward, Backward);206 207 return Forward || Backward;208}209 210bool checkIsConflictingKnown(KnowledgeStr Existing, KnowledgeStr Proposed) {211 auto Forward = checkIsConflictingNonsymmetricKnown(Existing, Proposed);212 auto Backward = checkIsConflictingNonsymmetricKnown(Proposed, Existing);213 214 // checkIsConflictingKnown should be symmetric.215 EXPECT_EQ(Forward, Backward);216 217 return Forward || Backward;218}219 220TEST(DeLICM, isConflicting) {221 222 // Check occupied vs. occupied.223 EXPECT_TRUE(224 checkIsConflicting({"{ Dom[i] }", nullptr, "{}"}, {nullptr, "{}", "{}"}));225 EXPECT_TRUE(checkIsConflicting({"{ Dom[i] }", nullptr, "{}"},226 {"{ Dom[i] }", nullptr, "{}"}));227 EXPECT_FALSE(checkIsConflicting({"{ Dom[0] }", nullptr, "{}"},228 {nullptr, "{ Dom[0] }", "{}"}));229 EXPECT_FALSE(checkIsConflicting({"{ Dom[i] : i != 0 }", nullptr, "{}"},230 {"{ Dom[0] }", nullptr, "{}"}));231 232 // Check occupied vs. occupied with known values.233 EXPECT_FALSE(checkIsConflictingKnown({"{ Dom[i] -> Val[] }", nullptr, "{}"},234 {"{ Dom[i] -> Val[] }", nullptr, "{}"}));235 EXPECT_TRUE(checkIsConflictingKnown({"{ Dom[i] -> ValA[] }", nullptr, "{}"},236 {"{ Dom[i] -> ValB[] }", nullptr, "{}"}));237 EXPECT_TRUE(checkIsConflictingKnown({"{ Dom[i] -> Val[] }", nullptr, "{}"},238 {"{ Dom[i] -> [] }", nullptr, "{}"}));239 EXPECT_FALSE(checkIsConflictingKnown({"{ Dom[0] -> Val[] }", nullptr, "{}"},240 {nullptr, "{ Dom[0] }", "{}"}));241 EXPECT_FALSE(checkIsConflictingKnown(242 {"{ Dom[i] -> Val[]; Dom[i] -> Phi[] }", nullptr, "{}"},243 {"{ Dom[i] -> Val[] }", nullptr, "{}"}));244 245 // An implementation using subtract would have exponential runtime on patterns246 // such as this one.247 EXPECT_TRUE(checkIsConflictingKnown(248 {"{ Dom[i0,i1,i2,i3,i4,i5,i6,i7,i8,i9,i10,i11,i12,i13,i14,i15]"249 "-> Val[] }",250 nullptr, "{}"},251 {"[p0,p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,p11,p12,p13,p14,p15,q0,"252 "q1,q2,q3,q4,q5,q6,q7,q8,q9,q10,q11,q12,q13,q14,q15] -> {"253 "Dom[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0] -> Val[];"254 "Dom[p0,p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,p11,p12,p13,p14,p15] -> Val[];"255 "Dom[q0,q1,q2,q3,q4,q5,q6,q7,q8,q9,q10,q11,q12,q13,q14,q15] -> Val[] }",256 "{}", "{}"}));257 258 // Check occupied vs. written.259 EXPECT_TRUE(260 checkIsConflicting({nullptr, "{}", "{}"}, {"{}", nullptr, "{ Dom[0] }"}));261 EXPECT_FALSE(262 checkIsConflicting({"{}", nullptr, "{}"}, {"{}", nullptr, "{ Dom[0] }"}));263 264 EXPECT_TRUE(checkIsConflicting({"{ Dom[i] }", nullptr, "{}"},265 {"{}", nullptr, "{ Dom[0] }"}));266 EXPECT_FALSE(checkIsConflicting({"{ DomA[i] }", nullptr, "{}"},267 {"{}", nullptr, "{ DomB[0] }"}));268 269 // Dom[1] represents the time between 0 and 1. Now Proposed writes at timestep270 // 0 such that will have a different value between 0 and 1. Hence it is271 // conflicting with Existing.272 EXPECT_TRUE(checkIsConflicting({"{ Dom[1] }", nullptr, "{}"},273 {"{}", nullptr, "{ Dom[0] }"}));274 EXPECT_FALSE(checkIsConflicting({"{ Dom[i] : i != 1 }", nullptr, "{}"},275 {"{}", nullptr, "{ Dom[0] }"}));276 277 // Check occupied vs. written with known values.278 EXPECT_FALSE(checkIsConflictingKnown({"{ Dom[i] -> Val[] }", nullptr, "{}"},279 {"{}", nullptr, "{ Dom[0] -> Val[] }"}));280 EXPECT_TRUE(checkIsConflictingKnown({"{ Dom[i] -> ValA[] }", nullptr, "{}"},281 {"{}", nullptr, "{ Dom[0] -> ValB[] }"}));282 EXPECT_TRUE(checkIsConflictingKnown({"{ Dom[i] -> Val[] }", nullptr, "{}"},283 {"{}", nullptr, "{ Dom[0] -> [] }"}));284 EXPECT_TRUE(checkIsConflictingKnown({"{ Dom[i] -> [] }", nullptr, "{}"},285 {"{}", nullptr, "{ Dom[0] -> Val[] }"}));286 287 // The same value can be known under multiple names, for instance a PHINode288 // has the same value as one of the incoming values. One matching pair289 // suffices.290 EXPECT_FALSE(checkIsConflictingKnown(291 {"{ Dom[i] -> Val[]; Dom[i] -> Phi[] }", nullptr, "{}"},292 {"{}", nullptr, "{ Dom[0] -> Val[] }"}));293 EXPECT_FALSE(checkIsConflictingKnown(294 {"{ Dom[i] -> Val[] }", nullptr, "{}"},295 {"{}", nullptr, "{ Dom[0] -> Val[]; Dom[0] -> Phi[] }"}));296 297 // Check written vs. written.298 EXPECT_TRUE(checkIsConflicting({"{}", nullptr, "{ Dom[0] }"},299 {"{}", nullptr, "{ Dom[0] }"}));300 EXPECT_FALSE(checkIsConflicting({"{}", nullptr, "{ Dom[-1] }"},301 {"{}", nullptr, "{ Dom[0] }"}));302 EXPECT_FALSE(checkIsConflicting({"{}", nullptr, "{ Dom[1] }"},303 {"{}", nullptr, "{ Dom[0] }"}));304 305 // Check written vs. written with known values.306 EXPECT_FALSE(checkIsConflictingKnown({"{}", nullptr, "{ Dom[0] -> Val[] }"},307 {"{}", nullptr, "{ Dom[0] -> Val[] }"}));308 EXPECT_TRUE(checkIsConflictingKnown({"{}", nullptr, "{ Dom[0] -> ValA[] }"},309 {"{}", nullptr, "{ Dom[0] -> ValB[] }"}));310 EXPECT_TRUE(checkIsConflictingKnown({"{}", nullptr, "{ Dom[0] -> Val[] }"},311 {"{}", nullptr, "{ Dom[0] -> [] }"}));312 EXPECT_FALSE(checkIsConflictingKnown(313 {"{}", nullptr, "{ Dom[0] -> Val[]}"},314 {"{}", nullptr, "{ Dom[0] -> Val[]; Dom[0] -> Phi[] }"}));315}316} // anonymous namespace317