mlir/unittests/Analysis/Presburger/PresburgerSpaceTest.cpp

   1 //===- PresburgerSpaceTest.cpp - Tests for PresburgerSpace ----------------===//
   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-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "mlir/Analysis/Presburger/PresburgerSpace.h"
  10 #include <gmock/gmock.h>
  11 #include <gtest/gtest.h>
  12
  13 using namespace mlir;
  14 using namespace presburger;
  15
  16 TEST(PresburgerSpaceTest, insertId) {
  17   PresburgerSpace space = PresburgerSpace::getRelationSpace(2, 2, 1);
  18
  19   // Try inserting 2 domain ids.
  20   space.insertVar(VarKind::Domain, 0, 2);
  21   EXPECT_EQ(space.getNumDomainVars(), 4u);
  22
  23   // Try inserting 1 range ids.
  24   space.insertVar(VarKind::Range, 0, 1);
  25   EXPECT_EQ(space.getNumRangeVars(), 3u);
  26 }
  27
  28 TEST(PresburgerSpaceTest, insertIdSet) {
  29   PresburgerSpace space = PresburgerSpace::getSetSpace(2, 1);
  30
  31   // Try inserting 2 dimension ids. The space should have 4 range ids since
  32   // spaces which do not distinguish between domain, range are implemented like
  33   // this.
  34   space.insertVar(VarKind::SetDim, 0, 2);
  35   EXPECT_EQ(space.getNumRangeVars(), 4u);
  36 }
  37
  38 TEST(PresburgerSpaceTest, removeIdRange) {
  39   PresburgerSpace space = PresburgerSpace::getRelationSpace(2, 1, 3);
  40
  41   // Remove 1 domain identifier.
  42   space.removeVarRange(VarKind::Domain, 0, 1);
  43   EXPECT_EQ(space.getNumDomainVars(), 1u);
  44
  45   // Remove 1 symbol and 1 range identifier.
  46   space.removeVarRange(VarKind::Symbol, 0, 1);
  47   space.removeVarRange(VarKind::Range, 0, 1);
  48   EXPECT_EQ(space.getNumDomainVars(), 1u);
  49   EXPECT_EQ(space.getNumRangeVars(), 0u);
  50   EXPECT_EQ(space.getNumSymbolVars(), 2u);
  51 }
  52
  53 TEST(PresburgerSpaceTest, insertVarIdentifier) {
  54   PresburgerSpace space = PresburgerSpace::getRelationSpace(2, 2, 1, 0);
  55
  56   int identifiers[2] = {0, 1};
  57
  58   // Attach identifiers to domain ids.
  59   space.setId(VarKind::Domain, 0, Identifier(&identifiers[0]));
  60   space.setId(VarKind::Domain, 1, Identifier(&identifiers[1]));
  61
  62   // Try inserting 2 domain ids.
  63   space.insertVar(VarKind::Domain, 0, 2);
  64   EXPECT_EQ(space.getNumDomainVars(), 4u);
  65
  66   // Try inserting 1 range ids.
  67   space.insertVar(VarKind::Range, 0, 1);
  68   EXPECT_EQ(space.getNumRangeVars(), 3u);
  69
  70   // Check if the identifiers for the old ids are still attached properly.
  71   EXPECT_EQ(space.getId(VarKind::Domain, 2), Identifier(&identifiers[0]));
  72   EXPECT_EQ(space.getId(VarKind::Domain, 3), Identifier(&identifiers[1]));
  73 }
  74
  75 TEST(PresburgerSpaceTest, removeVarRangeIdentifier) {
  76   PresburgerSpace space = PresburgerSpace::getRelationSpace(2, 1, 3, 0);
  77
  78   int identifiers[6] = {0, 1, 2, 3, 4, 5};
  79
  80   // Attach identifiers to domain identifiers.
  81   space.setId(VarKind::Domain, 0, Identifier(&identifiers[0]));
  82   space.setId(VarKind::Domain, 1, Identifier(&identifiers[1]));
  83
  84   // Attach identifiers to range identifiers.
  85   space.setId(VarKind::Range, 0, Identifier(&identifiers[2]));
  86
  87   // Attach identifiers to symbol identifiers.
  88   space.setId(VarKind::Symbol, 0, Identifier(&identifiers[3]));
  89   space.setId(VarKind::Symbol, 1, Identifier(&identifiers[4]));
  90   space.setId(VarKind::Symbol, 2, Identifier(&identifiers[5]));
  91
  92   // Remove 1 domain identifier.
  93   space.removeVarRange(VarKind::Domain, 0, 1);
  94   EXPECT_EQ(space.getNumDomainVars(), 1u);
  95
  96   // Remove 1 symbol and 1 range identifier.
  97   space.removeVarRange(VarKind::Symbol, 0, 1);
  98   space.removeVarRange(VarKind::Range, 0, 1);
  99   EXPECT_EQ(space.getNumDomainVars(), 1u);
 100   EXPECT_EQ(space.getNumRangeVars(), 0u);
 101   EXPECT_EQ(space.getNumSymbolVars(), 2u);
 102
 103   // Check if domain identifiers are attached properly.
 104   EXPECT_EQ(space.getId(VarKind::Domain, 0), Identifier(&identifiers[1]));
 105
 106   // Check if symbol identifiers are attached properly.
 107   EXPECT_EQ(space.getId(VarKind::Range, 0), Identifier(&identifiers[4]));
 108   EXPECT_EQ(space.getId(VarKind::Range, 1), Identifier(&identifiers[5]));
 109 }
 110
 111 TEST(PresburgerSpaceTest, IdentifierIsEqual) {
 112   PresburgerSpace space = PresburgerSpace::getRelationSpace(1, 2, 0, 0);
 113
 114   int identifiers[2] = {0, 1};
 115   space.setId(VarKind::Domain, 0, Identifier(&identifiers[0]));
 116   space.setId(VarKind::Range, 0, Identifier(&identifiers[0]));
 117   space.setId(VarKind::Range, 1, Identifier(&identifiers[1]));
 118
 119   EXPECT_EQ(space.getId(VarKind::Domain, 0), space.getId(VarKind::Range, 0));
 120   EXPECT_FALSE(
 121       space.getId(VarKind::Range, 0).isEqual(space.getId(VarKind::Range, 1)));
 122 }
 123
 124 TEST(PresburgerSpaceTest, convertVarKind) {
 125   PresburgerSpace space = PresburgerSpace::getRelationSpace(2, 2, 0, 0);
 126
 127   // Attach identifiers.
 128   int identifiers[4] = {0, 1, 2, 3};
 129   space.setId(VarKind::Domain, 0, Identifier(&identifiers[0]));
 130   space.setId(VarKind::Domain, 1, Identifier(&identifiers[1]));
 131   space.setId(VarKind::Range, 0, Identifier(&identifiers[2]));
 132   space.setId(VarKind::Range, 1, Identifier(&identifiers[3]));
 133
 134   // Convert Range variables to symbols.
 135   space.convertVarKind(VarKind::Range, 0, 2, VarKind::Symbol, 0);
 136
 137   // Check if the identifiers are moved to symbols.
 138   EXPECT_EQ(space.getId(VarKind::Symbol, 0), Identifier(&identifiers[2]));
 139   EXPECT_EQ(space.getId(VarKind::Symbol, 1), Identifier(&identifiers[3]));
 140
 141   // Convert 1 symbol to range identifier.
 142   space.convertVarKind(VarKind::Symbol, 1, 1, VarKind::Range, 0);
 143
 144   // Check if the identifier is moved to range.
 145   EXPECT_EQ(space.getId(VarKind::Range, 0), Identifier(&identifiers[3]));
 146 }
 147
 148 TEST(PresburgerSpaceTest, convertVarKindLocals) {
 149   PresburgerSpace space = PresburgerSpace::getRelationSpace(2, 2, 0, 0);
 150
 151   // Attach identifiers to range variables.
 152   int identifiers[4] = {0, 1};
 153   space.setId(VarKind::Range, 0, Identifier(&identifiers[0]));
 154   space.setId(VarKind::Range, 1, Identifier(&identifiers[1]));
 155
 156   // Convert Range variables to locals i.e. project them out.
 157   space.convertVarKind(VarKind::Range, 0, 2, VarKind::Local, 0);
 158
 159   // Check if the variables were moved.
 160   EXPECT_EQ(space.getNumVarKind(VarKind::Range), 0u);
 161   EXPECT_EQ(space.getNumVarKind(VarKind::Local), 2u);
 162
 163   // Convert the Local variables back to Range variables.
 164   space.convertVarKind(VarKind::Local, 0, 2, VarKind::Range, 0);
 165
 166   // The identifier information should be lost.
 167   EXPECT_FALSE(space.getId(VarKind::Range, 0).hasValue());
 168   EXPECT_FALSE(space.getId(VarKind::Range, 1).hasValue());
 169 }
 170
 171 TEST(PresburgerSpaceTest, convertVarKind2) {
 172   PresburgerSpace space = PresburgerSpace::getRelationSpace(0, 2, 2, 0);
 173
 174   // Attach identifiers.
 175   int identifiers[4] = {0, 1, 2, 3};
 176   space.setId(VarKind::Range, 0, Identifier(&identifiers[0]));
 177   space.setId(VarKind::Range, 1, Identifier(&identifiers[1]));
 178   space.setId(VarKind::Symbol, 0, Identifier(&identifiers[2]));
 179   space.setId(VarKind::Symbol, 1, Identifier(&identifiers[3]));
 180
 181   // Convert Range variables to symbols.
 182   space.convertVarKind(VarKind::Range, 0, 2, VarKind::Symbol, 1);
 183
 184   // Check if the identifiers are moved to symbols.
 185   EXPECT_EQ(space.getId(VarKind::Symbol, 0), Identifier(&identifiers[2]));
 186   EXPECT_EQ(space.getId(VarKind::Symbol, 1), Identifier(&identifiers[0]));
 187   EXPECT_EQ(space.getId(VarKind::Symbol, 2), Identifier(&identifiers[1]));
 188   EXPECT_EQ(space.getId(VarKind::Symbol, 3), Identifier(&identifiers[3]));
 189 }
 190
 191 TEST(PresburgerSpaceTest, mergeAndAlignSymbols) {
 192   PresburgerSpace space = PresburgerSpace::getRelationSpace(3, 3, 2, 0);
 193
 194   PresburgerSpace otherSpace = PresburgerSpace::getRelationSpace(3, 2, 3, 0);
 195
 196   // Attach identifiers.
 197   int identifiers[7] = {0, 1, 2, 3, 4, 5, 6};
 198   int otherIdentifiers[8] = {10, 11, 12, 13, 14, 15, 16, 17};
 199
 200   space.setId(VarKind::Domain, 0, Identifier(&identifiers[0]));
 201   space.setId(VarKind::Domain, 1, Identifier(&identifiers[1]));
 202   // Note the common identifier.
 203   space.setId(VarKind::Domain, 2, Identifier(&otherIdentifiers[2]));
 204   space.setId(VarKind::Range, 0, Identifier(&identifiers[2]));
 205   space.setId(VarKind::Range, 1, Identifier(&identifiers[3]));
 206   space.setId(VarKind::Range, 2, Identifier(&identifiers[4]));
 207   space.setId(VarKind::Symbol, 0, Identifier(&identifiers[5]));
 208   space.setId(VarKind::Symbol, 1, Identifier(&identifiers[6]));
 209
 210   otherSpace.setId(VarKind::Domain, 0, Identifier(&otherIdentifiers[0]));
 211   otherSpace.setId(VarKind::Domain, 1, Identifier(&otherIdentifiers[1]));
 212   otherSpace.setId(VarKind::Domain, 2, Identifier(&otherIdentifiers[2]));
 213   otherSpace.setId(VarKind::Range, 0, Identifier(&otherIdentifiers[3]));
 214   otherSpace.setId(VarKind::Range, 1, Identifier(&otherIdentifiers[4]));
 215   // Note the common identifier.
 216   otherSpace.setId(VarKind::Symbol, 0, Identifier(&identifiers[6]));
 217   otherSpace.setId(VarKind::Symbol, 1, Identifier(&otherIdentifiers[5]));
 218   otherSpace.setId(VarKind::Symbol, 2, Identifier(&otherIdentifiers[7]));
 219
 220   space.mergeAndAlignSymbols(otherSpace);
 221
 222   // Check if merge & align is successful.
 223   // Check symbol var identifiers.
 224   EXPECT_EQ(4u, space.getNumSymbolVars());
 225   EXPECT_EQ(4u, otherSpace.getNumSymbolVars());
 226   EXPECT_EQ(space.getId(VarKind::Symbol, 0), Identifier(&identifiers[5]));
 227   EXPECT_EQ(space.getId(VarKind::Symbol, 1), Identifier(&identifiers[6]));
 228   EXPECT_EQ(space.getId(VarKind::Symbol, 2), Identifier(&otherIdentifiers[5]));
 229   EXPECT_EQ(space.getId(VarKind::Symbol, 3), Identifier(&otherIdentifiers[7]));
 230   EXPECT_EQ(otherSpace.getId(VarKind::Symbol, 0), Identifier(&identifiers[5]));
 231   EXPECT_EQ(otherSpace.getId(VarKind::Symbol, 1), Identifier(&identifiers[6]));
 232   EXPECT_EQ(otherSpace.getId(VarKind::Symbol, 2),
 233             Identifier(&otherIdentifiers[5]));
 234   EXPECT_EQ(otherSpace.getId(VarKind::Symbol, 3),
 235             Identifier(&otherIdentifiers[7]));
 236   // Check that domain and range var identifiers are not affected.
 237   EXPECT_EQ(3u, space.getNumDomainVars());
 238   EXPECT_EQ(3u, space.getNumRangeVars());
 239   EXPECT_EQ(space.getId(VarKind::Domain, 0), Identifier(&identifiers[0]));
 240   EXPECT_EQ(space.getId(VarKind::Domain, 1), Identifier(&identifiers[1]));
 241   EXPECT_EQ(space.getId(VarKind::Domain, 2), Identifier(&otherIdentifiers[2]));
 242   EXPECT_EQ(space.getId(VarKind::Range, 0), Identifier(&identifiers[2]));
 243   EXPECT_EQ(space.getId(VarKind::Range, 1), Identifier(&identifiers[3]));
 244   EXPECT_EQ(space.getId(VarKind::Range, 2), Identifier(&identifiers[4]));
 245   EXPECT_EQ(3u, otherSpace.getNumDomainVars());
 246   EXPECT_EQ(2u, otherSpace.getNumRangeVars());
 247   EXPECT_EQ(otherSpace.getId(VarKind::Domain, 0),
 248             Identifier(&otherIdentifiers[0]));
 249   EXPECT_EQ(otherSpace.getId(VarKind::Domain, 1),
 250             Identifier(&otherIdentifiers[1]));
 251   EXPECT_EQ(otherSpace.getId(VarKind::Domain, 2),
 252             Identifier(&otherIdentifiers[2]));
 253   EXPECT_EQ(otherSpace.getId(VarKind::Range, 0),
 254             Identifier(&otherIdentifiers[3]));
 255   EXPECT_EQ(otherSpace.getId(VarKind::Range, 1),
 256             Identifier(&otherIdentifiers[4]));
 257 }