llvm/unittests/CodeGen/SelectionDAGAddressAnalysisTest.cpp

   1 //===- llvm/unittest/CodeGen/SelectionDAGAddressAnalysisTest.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-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "llvm/CodeGen/SelectionDAGAddressAnalysis.h"
  10 #include "llvm/Analysis/MemoryLocation.h"
  11 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
  12 #include "llvm/AsmParser/Parser.h"
  13 #include "llvm/CodeGen/MachineModuleInfo.h"
  14 #include "llvm/CodeGen/SelectionDAG.h"
  15 #include "llvm/CodeGen/TargetLowering.h"
  16 #include "llvm/MC/TargetRegistry.h"
  17 #include "llvm/Support/SourceMgr.h"
  18 #include "llvm/Support/TargetSelect.h"
  19 #include "llvm/Target/TargetMachine.h"
  20 #include "gtest/gtest.h"
  21
  22 namespace llvm {
  23
  24 class SelectionDAGAddressAnalysisTest : public testing::Test {
  25 protected:
  26   static void SetUpTestCase() {
  27     InitializeAllTargets();
  28     InitializeAllTargetMCs();
  29   }
  30
  31   void SetUp() override {
  32     StringRef Assembly = "@g = global i32 0\n"
  33                          "@g_alias = alias i32, i32* @g\n"
  34                          "define i32 @f() {\n"
  35                          "  %1 = load i32, i32* @g\n"
  36                          "  ret i32 %1\n"
  37                          "}";
  38
  39     Triple TargetTriple("aarch64--");
  40     std::string Error;
  41     const Target *T = TargetRegistry::lookupTarget("", TargetTriple, Error);
  42     // FIXME: These tests do not depend on AArch64 specifically, but we have to
  43     // initialize a target. A skeleton Target for unittests would allow us to
  44     // always run these tests.
  45     if (!T)
  46       GTEST_SKIP();
  47
  48     TargetOptions Options;
  49     TM = std::unique_ptr<LLVMTargetMachine>(static_cast<LLVMTargetMachine *>(
  50         T->createTargetMachine("AArch64", "", "+sve", Options, std::nullopt,
  51                                std::nullopt, CodeGenOptLevel::Aggressive)));
  52     if (!TM)
  53       GTEST_SKIP();
  54
  55     SMDiagnostic SMError;
  56     M = parseAssemblyString(Assembly, SMError, Context);
  57     if (!M)
  58       report_fatal_error(SMError.getMessage());
  59     M->setDataLayout(TM->createDataLayout());
  60
  61     F = M->getFunction("f");
  62     if (!F)
  63       report_fatal_error("F?");
  64     G = M->getGlobalVariable("g");
  65     if (!G)
  66       report_fatal_error("G?");
  67     AliasedG = M->getNamedAlias("g_alias");
  68     if (!AliasedG)
  69       report_fatal_error("AliasedG?");
  70
  71     MachineModuleInfo MMI(TM.get());
  72
  73     MF = std::make_unique<MachineFunction>(*F, *TM, *TM->getSubtargetImpl(*F),
  74                                            0, MMI);
  75
  76     DAG = std::make_unique<SelectionDAG>(*TM, CodeGenOptLevel::None);
  77     if (!DAG)
  78       report_fatal_error("DAG?");
  79     OptimizationRemarkEmitter ORE(F);
  80     DAG->init(*MF, ORE, nullptr, nullptr, nullptr, nullptr, nullptr, nullptr);
  81   }
  82
  83   TargetLoweringBase::LegalizeTypeAction getTypeAction(EVT VT) {
  84     return DAG->getTargetLoweringInfo().getTypeAction(Context, VT);
  85   }
  86
  87   EVT getTypeToTransformTo(EVT VT) {
  88     return DAG->getTargetLoweringInfo().getTypeToTransformTo(Context, VT);
  89   }
  90
  91   LLVMContext Context;
  92   std::unique_ptr<LLVMTargetMachine> TM;
  93   std::unique_ptr<Module> M;
  94   Function *F;
  95   GlobalVariable *G;
  96   GlobalAlias *AliasedG;
  97   std::unique_ptr<MachineFunction> MF;
  98   std::unique_ptr<SelectionDAG> DAG;
  99 };
 100
 101 TEST_F(SelectionDAGAddressAnalysisTest, sameFrameObject) {
 102   SDLoc Loc;
 103   auto Int8VT = EVT::getIntegerVT(Context, 8);
 104   auto VecVT = EVT::getVectorVT(Context, Int8VT, 4);
 105   SDValue FIPtr = DAG->CreateStackTemporary(VecVT);
 106   int FI = cast<FrameIndexSDNode>(FIPtr.getNode())->getIndex();
 107   MachinePointerInfo PtrInfo = MachinePointerInfo::getFixedStack(*MF, FI);
 108   TypeSize Offset = TypeSize::Fixed(0);
 109   SDValue Value = DAG->getConstant(0, Loc, VecVT);
 110   SDValue Index = DAG->getMemBasePlusOffset(FIPtr, Offset, Loc);
 111   SDValue Store = DAG->getStore(DAG->getEntryNode(), Loc, Value, Index,
 112                                 PtrInfo.getWithOffset(Offset));
 113   std::optional<int64_t> NumBytes = MemoryLocation::getSizeOrUnknown(
 114       cast<StoreSDNode>(Store)->getMemoryVT().getStoreSize());
 115
 116   bool IsAlias;
 117   bool IsValid = BaseIndexOffset::computeAliasing(
 118       Store.getNode(), NumBytes, Store.getNode(), NumBytes, *DAG, IsAlias);
 119
 120   EXPECT_TRUE(IsValid);
 121   EXPECT_TRUE(IsAlias);
 122 }
 123
 124 TEST_F(SelectionDAGAddressAnalysisTest, sameFrameObjectUnknownSize) {
 125   SDLoc Loc;
 126   auto Int8VT = EVT::getIntegerVT(Context, 8);
 127   auto VecVT = EVT::getVectorVT(Context, Int8VT, 4);
 128   SDValue FIPtr = DAG->CreateStackTemporary(VecVT);
 129   int FI = cast<FrameIndexSDNode>(FIPtr.getNode())->getIndex();
 130   MachinePointerInfo PtrInfo = MachinePointerInfo::getFixedStack(*MF, FI);
 131   TypeSize Offset = TypeSize::Fixed(0);
 132   SDValue Value = DAG->getConstant(0, Loc, VecVT);
 133   SDValue Index = DAG->getMemBasePlusOffset(FIPtr, Offset, Loc);
 134   SDValue Store = DAG->getStore(DAG->getEntryNode(), Loc, Value, Index,
 135                                 PtrInfo.getWithOffset(Offset));
 136
 137   // Maybe unlikely that BaseIndexOffset::computeAliasing is used with the
 138   // optional NumBytes being unset like in this test, but it would be confusing
 139   // if that function determined IsAlias=false here.
 140   std::optional<int64_t> NumBytes;
 141
 142   bool IsAlias;
 143   bool IsValid = BaseIndexOffset::computeAliasing(
 144       Store.getNode(), NumBytes, Store.getNode(), NumBytes, *DAG, IsAlias);
 145
 146   EXPECT_FALSE(IsValid);
 147 }
 148
 149 TEST_F(SelectionDAGAddressAnalysisTest, noAliasingFrameObjects) {
 150   SDLoc Loc;
 151   auto Int8VT = EVT::getIntegerVT(Context, 8);
 152   // <4 x i8>
 153   auto VecVT = EVT::getVectorVT(Context, Int8VT, 4);
 154   // <2 x i8>
 155   auto SubVecVT = EVT::getVectorVT(Context, Int8VT, 2);
 156   SDValue FIPtr = DAG->CreateStackTemporary(VecVT);
 157   int FI = cast<FrameIndexSDNode>(FIPtr.getNode())->getIndex();
 158   MachinePointerInfo PtrInfo = MachinePointerInfo::getFixedStack(*MF, FI);
 159   SDValue Value = DAG->getConstant(0, Loc, SubVecVT);
 160   TypeSize Offset0 = TypeSize::Fixed(0);
 161   TypeSize Offset1 = SubVecVT.getStoreSize();
 162   SDValue Index0 = DAG->getMemBasePlusOffset(FIPtr, Offset0, Loc);
 163   SDValue Index1 = DAG->getMemBasePlusOffset(FIPtr, Offset1, Loc);
 164   SDValue Store0 = DAG->getStore(DAG->getEntryNode(), Loc, Value, Index0,
 165                                  PtrInfo.getWithOffset(Offset0));
 166   SDValue Store1 = DAG->getStore(DAG->getEntryNode(), Loc, Value, Index1,
 167                                  PtrInfo.getWithOffset(Offset1));
 168   std::optional<int64_t> NumBytes0 = MemoryLocation::getSizeOrUnknown(
 169       cast<StoreSDNode>(Store0)->getMemoryVT().getStoreSize());
 170   std::optional<int64_t> NumBytes1 = MemoryLocation::getSizeOrUnknown(
 171       cast<StoreSDNode>(Store1)->getMemoryVT().getStoreSize());
 172
 173   bool IsAlias;
 174   bool IsValid = BaseIndexOffset::computeAliasing(
 175       Store0.getNode(), NumBytes0, Store1.getNode(), NumBytes1, *DAG, IsAlias);
 176
 177   EXPECT_TRUE(IsValid);
 178   EXPECT_FALSE(IsAlias);
 179 }
 180
 181 TEST_F(SelectionDAGAddressAnalysisTest, unknownSizeFrameObjects) {
 182   SDLoc Loc;
 183   auto Int8VT = EVT::getIntegerVT(Context, 8);
 184   // <vscale x 4 x i8>
 185   auto VecVT = EVT::getVectorVT(Context, Int8VT, 4, true);
 186   // <vscale x 2 x i8>
 187   auto SubVecVT = EVT::getVectorVT(Context, Int8VT, 2, true);
 188   SDValue FIPtr = DAG->CreateStackTemporary(VecVT);
 189   int FI = cast<FrameIndexSDNode>(FIPtr.getNode())->getIndex();
 190   MachinePointerInfo PtrInfo = MachinePointerInfo::getFixedStack(*MF, FI);
 191   SDValue Value = DAG->getConstant(0, Loc, SubVecVT);
 192   TypeSize Offset1 = SubVecVT.getStoreSize();
 193   SDValue Index1 = DAG->getMemBasePlusOffset(FIPtr, Offset1, Loc);
 194   SDValue Store0 =
 195       DAG->getStore(DAG->getEntryNode(), Loc, Value, FIPtr, PtrInfo);
 196   SDValue Store1 = DAG->getStore(DAG->getEntryNode(), Loc, Value, Index1,
 197                                  MachinePointerInfo(PtrInfo.getAddrSpace()));
 198   std::optional<int64_t> NumBytes0 = MemoryLocation::getSizeOrUnknown(
 199       cast<StoreSDNode>(Store0)->getMemoryVT().getStoreSize());
 200   std::optional<int64_t> NumBytes1 = MemoryLocation::getSizeOrUnknown(
 201       cast<StoreSDNode>(Store1)->getMemoryVT().getStoreSize());
 202
 203   bool IsAlias;
 204   bool IsValid = BaseIndexOffset::computeAliasing(
 205       Store0.getNode(), NumBytes0, Store1.getNode(), NumBytes1, *DAG, IsAlias);
 206
 207   EXPECT_FALSE(IsValid);
 208 }
 209
 210 TEST_F(SelectionDAGAddressAnalysisTest, globalWithFrameObject) {
 211   SDLoc Loc;
 212   auto Int8VT = EVT::getIntegerVT(Context, 8);
 213   // <vscale x 4 x i8>
 214   auto VecVT = EVT::getVectorVT(Context, Int8VT, 4, true);
 215   SDValue FIPtr = DAG->CreateStackTemporary(VecVT);
 216   int FI = cast<FrameIndexSDNode>(FIPtr.getNode())->getIndex();
 217   MachinePointerInfo PtrInfo = MachinePointerInfo::getFixedStack(*MF, FI);
 218   SDValue Value = DAG->getConstant(0, Loc, VecVT);
 219   TypeSize Offset = TypeSize::Fixed(0);
 220   SDValue Index = DAG->getMemBasePlusOffset(FIPtr, Offset, Loc);
 221   SDValue Store = DAG->getStore(DAG->getEntryNode(), Loc, Value, Index,
 222                                 PtrInfo.getWithOffset(Offset));
 223   std::optional<int64_t> NumBytes = MemoryLocation::getSizeOrUnknown(
 224       cast<StoreSDNode>(Store)->getMemoryVT().getStoreSize());
 225   EVT GTy = DAG->getTargetLoweringInfo().getValueType(DAG->getDataLayout(),
 226                                                       G->getType());
 227   SDValue GValue = DAG->getConstant(0, Loc, GTy);
 228   SDValue GAddr = DAG->getGlobalAddress(G, Loc, GTy);
 229   SDValue GStore = DAG->getStore(DAG->getEntryNode(), Loc, GValue, GAddr,
 230                                  MachinePointerInfo(G, 0));
 231   std::optional<int64_t> GNumBytes = MemoryLocation::getSizeOrUnknown(
 232       cast<StoreSDNode>(GStore)->getMemoryVT().getStoreSize());
 233
 234   bool IsAlias;
 235   bool IsValid = BaseIndexOffset::computeAliasing(
 236       Store.getNode(), NumBytes, GStore.getNode(), GNumBytes, *DAG, IsAlias);
 237
 238   EXPECT_TRUE(IsValid);
 239   EXPECT_FALSE(IsAlias);
 240 }
 241
 242 TEST_F(SelectionDAGAddressAnalysisTest, globalWithAliasedGlobal) {
 243   SDLoc Loc;
 244
 245   EVT GTy = DAG->getTargetLoweringInfo().getValueType(DAG->getDataLayout(),
 246                                                       G->getType());
 247   SDValue GValue = DAG->getConstant(0, Loc, GTy);
 248   SDValue GAddr = DAG->getGlobalAddress(G, Loc, GTy);
 249   SDValue GStore = DAG->getStore(DAG->getEntryNode(), Loc, GValue, GAddr,
 250                                  MachinePointerInfo(G, 0));
 251   std::optional<int64_t> GNumBytes = MemoryLocation::getSizeOrUnknown(
 252       cast<StoreSDNode>(GStore)->getMemoryVT().getStoreSize());
 253
 254   SDValue AliasedGValue = DAG->getConstant(1, Loc, GTy);
 255   SDValue AliasedGAddr = DAG->getGlobalAddress(AliasedG, Loc, GTy);
 256   SDValue AliasedGStore =
 257       DAG->getStore(DAG->getEntryNode(), Loc, AliasedGValue, AliasedGAddr,
 258                     MachinePointerInfo(AliasedG, 0));
 259
 260   bool IsAlias;
 261   bool IsValid = BaseIndexOffset::computeAliasing(GStore.getNode(), GNumBytes,
 262                                                   AliasedGStore.getNode(),
 263                                                   GNumBytes, *DAG, IsAlias);
 264
 265   // With some deeper analysis we could detect if G and AliasedG is aliasing or
 266   // not. But computeAliasing is currently defensive and assumes that a
 267   // GlobalAlias might alias with any global variable.
 268   EXPECT_FALSE(IsValid);
 269 }
 270
 271 TEST_F(SelectionDAGAddressAnalysisTest, fixedSizeFrameObjectsWithinDiff) {
 272   SDLoc Loc;
 273   auto Int8VT = EVT::getIntegerVT(Context, 8);
 274   // <vscale x 4 x i8>
 275   auto VecVT = EVT::getVectorVT(Context, Int8VT, 4, true);
 276   // <vscale x 2 x i8>
 277   auto SubVecVT = EVT::getVectorVT(Context, Int8VT, 2, true);
 278   // <2 x i8>
 279   auto SubFixedVecVT2xi8 = EVT::getVectorVT(Context, Int8VT, 2);
 280   SDValue FIPtr = DAG->CreateStackTemporary(VecVT);
 281   int FI = cast<FrameIndexSDNode>(FIPtr.getNode())->getIndex();
 282   MachinePointerInfo PtrInfo = MachinePointerInfo::getFixedStack(*MF, FI);
 283   SDValue Value0 = DAG->getConstant(0, Loc, SubFixedVecVT2xi8);
 284   SDValue Value1 = DAG->getConstant(0, Loc, SubVecVT);
 285   TypeSize Offset0 = TypeSize::Fixed(0);
 286   TypeSize Offset1 = SubFixedVecVT2xi8.getStoreSize();
 287   SDValue Index0 = DAG->getMemBasePlusOffset(FIPtr, Offset0, Loc);
 288   SDValue Index1 = DAG->getMemBasePlusOffset(FIPtr, Offset1, Loc);
 289   SDValue Store0 = DAG->getStore(DAG->getEntryNode(), Loc, Value0, Index0,
 290                                  PtrInfo.getWithOffset(Offset0));
 291   SDValue Store1 = DAG->getStore(DAG->getEntryNode(), Loc, Value1, Index1,
 292                                  PtrInfo.getWithOffset(Offset1));
 293   std::optional<int64_t> NumBytes0 = MemoryLocation::getSizeOrUnknown(
 294       cast<StoreSDNode>(Store0)->getMemoryVT().getStoreSize());
 295   std::optional<int64_t> NumBytes1 = MemoryLocation::getSizeOrUnknown(
 296       cast<StoreSDNode>(Store1)->getMemoryVT().getStoreSize());
 297
 298   bool IsAlias;
 299   bool IsValid = BaseIndexOffset::computeAliasing(
 300       Store0.getNode(), NumBytes0, Store1.getNode(), NumBytes1, *DAG, IsAlias);
 301   EXPECT_TRUE(IsValid);
 302   EXPECT_FALSE(IsAlias);
 303
 304   IsValid = BaseIndexOffset::computeAliasing(
 305       Store1.getNode(), NumBytes1, Store0.getNode(), NumBytes0, *DAG, IsAlias);
 306   EXPECT_TRUE(IsValid);
 307   EXPECT_FALSE(IsAlias);
 308 }
 309
 310 TEST_F(SelectionDAGAddressAnalysisTest, fixedSizeFrameObjectsOutOfDiff) {
 311   SDLoc Loc;
 312   auto Int8VT = EVT::getIntegerVT(Context, 8);
 313   // <vscale x 4 x i8>
 314   auto VecVT = EVT::getVectorVT(Context, Int8VT, 4, true);
 315   // <vscale x 2 x i8>
 316   auto SubVecVT = EVT::getVectorVT(Context, Int8VT, 2, true);
 317   // <2 x i8>
 318   auto SubFixedVecVT2xi8 = EVT::getVectorVT(Context, Int8VT, 2);
 319   // <4 x i8>
 320   auto SubFixedVecVT4xi8 = EVT::getVectorVT(Context, Int8VT, 4);
 321   SDValue FIPtr = DAG->CreateStackTemporary(VecVT);
 322   int FI = cast<FrameIndexSDNode>(FIPtr.getNode())->getIndex();
 323   MachinePointerInfo PtrInfo = MachinePointerInfo::getFixedStack(*MF, FI);
 324   SDValue Value0 = DAG->getConstant(0, Loc, SubFixedVecVT4xi8);
 325   SDValue Value1 = DAG->getConstant(0, Loc, SubVecVT);
 326   TypeSize Offset0 = TypeSize::Fixed(0);
 327   TypeSize Offset1 = SubFixedVecVT2xi8.getStoreSize();
 328   SDValue Index0 = DAG->getMemBasePlusOffset(FIPtr, Offset0, Loc);
 329   SDValue Index1 = DAG->getMemBasePlusOffset(FIPtr, Offset1, Loc);
 330   SDValue Store0 = DAG->getStore(DAG->getEntryNode(), Loc, Value0, Index0,
 331                                  PtrInfo.getWithOffset(Offset0));
 332   SDValue Store1 = DAG->getStore(DAG->getEntryNode(), Loc, Value1, Index1,
 333                                  PtrInfo.getWithOffset(Offset1));
 334   std::optional<int64_t> NumBytes0 = MemoryLocation::getSizeOrUnknown(
 335       cast<StoreSDNode>(Store0)->getMemoryVT().getStoreSize());
 336   std::optional<int64_t> NumBytes1 = MemoryLocation::getSizeOrUnknown(
 337       cast<StoreSDNode>(Store1)->getMemoryVT().getStoreSize());
 338
 339   bool IsAlias;
 340   bool IsValid = BaseIndexOffset::computeAliasing(
 341       Store0.getNode(), NumBytes0, Store1.getNode(), NumBytes1, *DAG, IsAlias);
 342   EXPECT_TRUE(IsValid);
 343   EXPECT_TRUE(IsAlias);
 344 }
 345
 346 TEST_F(SelectionDAGAddressAnalysisTest, twoFixedStackObjects) {
 347   SDLoc Loc;
 348   auto Int8VT = EVT::getIntegerVT(Context, 8);
 349   // <vscale x 2 x i8>
 350   auto VecVT = EVT::getVectorVT(Context, Int8VT, 2, true);
 351   // <2 x i8>
 352   auto FixedVecVT = EVT::getVectorVT(Context, Int8VT, 2);
 353   SDValue FIPtr0 = DAG->CreateStackTemporary(FixedVecVT);
 354   SDValue FIPtr1 = DAG->CreateStackTemporary(VecVT);
 355   int FI0 = cast<FrameIndexSDNode>(FIPtr0.getNode())->getIndex();
 356   int FI1 = cast<FrameIndexSDNode>(FIPtr1.getNode())->getIndex();
 357   MachinePointerInfo PtrInfo0 = MachinePointerInfo::getFixedStack(*MF, FI0);
 358   MachinePointerInfo PtrInfo1 = MachinePointerInfo::getFixedStack(*MF, FI1);
 359   SDValue Value0 = DAG->getConstant(0, Loc, FixedVecVT);
 360   SDValue Value1 = DAG->getConstant(0, Loc, VecVT);
 361   TypeSize Offset0 = TypeSize::Fixed(0);
 362   SDValue Index0 = DAG->getMemBasePlusOffset(FIPtr0, Offset0, Loc);
 363   SDValue Index1 = DAG->getMemBasePlusOffset(FIPtr1, Offset0, Loc);
 364   SDValue Store0 = DAG->getStore(DAG->getEntryNode(), Loc, Value0, Index0,
 365                                  PtrInfo0.getWithOffset(Offset0));
 366   SDValue Store1 = DAG->getStore(DAG->getEntryNode(), Loc, Value1, Index1,
 367                                  PtrInfo1.getWithOffset(Offset0));
 368   std::optional<int64_t> NumBytes0 = MemoryLocation::getSizeOrUnknown(
 369       cast<StoreSDNode>(Store0)->getMemoryVT().getStoreSize());
 370   std::optional<int64_t> NumBytes1 = MemoryLocation::getSizeOrUnknown(
 371       cast<StoreSDNode>(Store1)->getMemoryVT().getStoreSize());
 372
 373   bool IsAlias;
 374   bool IsValid = BaseIndexOffset::computeAliasing(
 375       Store0.getNode(), NumBytes0, Store1.getNode(), NumBytes1, *DAG, IsAlias);
 376   EXPECT_TRUE(IsValid);
 377   EXPECT_FALSE(IsAlias);
 378 }
 379
 380 } // end namespace llvm