diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGAddressAnalysis.cpp b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGAddressAnalysis.cpp --- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGAddressAnalysis.cpp +++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGAddressAnalysis.cpp @@ -7,6 +7,7 @@ //===----------------------------------------------------------------------===// #include "llvm/CodeGen/SelectionDAGAddressAnalysis.h" +#include "llvm/Analysis/MemoryLocation.h" #include "llvm/CodeGen/ISDOpcodes.h" #include "llvm/CodeGen/MachineFrameInfo.h" #include "llvm/CodeGen/MachineFunction.h" @@ -96,18 +97,28 @@ int64_t PtrDiff; if (NumBytes0.hasValue() && NumBytes1.hasValue() && BasePtr0.equalBaseIndex(BasePtr1, DAG, PtrDiff)) { + // If the size of memory access is unknown, do not use it to analysis. + // One example of unknown size memory access is to load/store scalable + // vector objects on the stack. // BasePtr1 is PtrDiff away from BasePtr0. They alias if none of the // following situations arise: - IsAlias = !( - // [----BasePtr0----] - // [---BasePtr1--] - // ========PtrDiff========> - (*NumBytes0 <= PtrDiff) || - // [----BasePtr0----] - // [---BasePtr1--] - // =====(-PtrDiff)====> - (PtrDiff + *NumBytes1 <= 0)); // i.e. *NumBytes1 < -PtrDiff. - return true; + if (PtrDiff >= 0 && + *NumBytes0 != static_cast(MemoryLocation::UnknownSize)) { + // [----BasePtr0----] + // [---BasePtr1--] + // ========PtrDiff========> + IsAlias = !(*NumBytes0 <= PtrDiff); + return true; + } + if (PtrDiff < 0 && + *NumBytes1 != static_cast(MemoryLocation::UnknownSize)) { + // [----BasePtr0----] + // [---BasePtr1--] + // =====(-PtrDiff)====> + IsAlias = !((PtrDiff + *NumBytes1) <= 0); + return true; + } + return false; } // If both BasePtr0 and BasePtr1 are FrameIndexes, we will not be // able to calculate their relative offset if at least one arises diff --git a/llvm/unittests/CodeGen/CMakeLists.txt b/llvm/unittests/CodeGen/CMakeLists.txt --- a/llvm/unittests/CodeGen/CMakeLists.txt +++ b/llvm/unittests/CodeGen/CMakeLists.txt @@ -26,6 +26,7 @@ MachineOperandTest.cpp PassManagerTest.cpp ScalableVectorMVTsTest.cpp + SelectionDAGAddressAnalysisTest.cpp TypeTraitsTest.cpp TargetOptionsTest.cpp TestAsmPrinter.cpp diff --git a/llvm/unittests/CodeGen/SelectionDAGAddressAnalysisTest.cpp b/llvm/unittests/CodeGen/SelectionDAGAddressAnalysisTest.cpp new file mode 100644 --- /dev/null +++ b/llvm/unittests/CodeGen/SelectionDAGAddressAnalysisTest.cpp @@ -0,0 +1,337 @@ +//===- llvm/unittest/CodeGen/SelectionDAGAddressAnalysisTest.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 "llvm/CodeGen/SelectionDAGAddressAnalysis.h" +#include "llvm/Analysis/MemoryLocation.h" +#include "llvm/Analysis/OptimizationRemarkEmitter.h" +#include "llvm/AsmParser/Parser.h" +#include "llvm/CodeGen/MachineModuleInfo.h" +#include "llvm/CodeGen/SelectionDAG.h" +#include "llvm/CodeGen/TargetLowering.h" +#include "llvm/Support/SourceMgr.h" +#include "llvm/Support/TargetRegistry.h" +#include "llvm/Support/TargetSelect.h" +#include "llvm/Target/TargetMachine.h" +#include "gtest/gtest.h" + +namespace llvm { + +class SelectionDAGAddressAnalysisTest : public testing::Test { +protected: + static void SetUpTestCase() { + InitializeAllTargets(); + InitializeAllTargetMCs(); + } + + void SetUp() override { + StringRef Assembly = "@g = global i32 0\n" + "define i32 @f() {\n" + " %1 = load i32, i32* @g\n" + " ret i32 %1\n" + "}"; + + Triple TargetTriple("aarch64--"); + std::string Error; + const Target *T = TargetRegistry::lookupTarget("", TargetTriple, Error); + // FIXME: These tests do not depend on AArch64 specifically, but we have to + // initialize a target. A skeleton Target for unittests would allow us to + // always run these tests. + if (!T) + return; + + TargetOptions Options; + TM = std::unique_ptr(static_cast( + T->createTargetMachine("AArch64", "", "+sve", Options, None, None, + CodeGenOpt::Aggressive))); + if (!TM) + return; + + SMDiagnostic SMError; + M = parseAssemblyString(Assembly, SMError, Context); + if (!M) + report_fatal_error(SMError.getMessage()); + M->setDataLayout(TM->createDataLayout()); + + F = M->getFunction("f"); + if (!F) + report_fatal_error("F?"); + G = M->getGlobalVariable("g"); + if (!G) + report_fatal_error("G?"); + + MachineModuleInfo MMI(TM.get()); + + MF = std::make_unique(*F, *TM, *TM->getSubtargetImpl(*F), + 0, MMI); + + DAG = std::make_unique(*TM, CodeGenOpt::None); + if (!DAG) + report_fatal_error("DAG?"); + OptimizationRemarkEmitter ORE(F); + DAG->init(*MF, ORE, nullptr, nullptr, nullptr, nullptr, nullptr); + } + + TargetLoweringBase::LegalizeTypeAction getTypeAction(EVT VT) { + return DAG->getTargetLoweringInfo().getTypeAction(Context, VT); + } + + EVT getTypeToTransformTo(EVT VT) { + return DAG->getTargetLoweringInfo().getTypeToTransformTo(Context, VT); + } + + LLVMContext Context; + std::unique_ptr TM; + std::unique_ptr M; + Function *F; + GlobalVariable *G; + std::unique_ptr MF; + std::unique_ptr DAG; +}; + +TEST_F(SelectionDAGAddressAnalysisTest, sameFrameObject) { + if (!TM) + return; + SDLoc Loc; + auto Int8VT = EVT::getIntegerVT(Context, 8); + auto VecVT = EVT::getVectorVT(Context, Int8VT, 4); + SDValue FIPtr = DAG->CreateStackTemporary(VecVT); + int FI = cast(FIPtr.getNode())->getIndex(); + MachinePointerInfo PtrInfo = MachinePointerInfo::getFixedStack(*MF, FI); + TypeSize Offset = TypeSize::Fixed(0); + SDValue Value = DAG->getConstant(0, Loc, VecVT); + SDValue Index = DAG->getMemBasePlusOffset(FIPtr, Offset, Loc); + SDValue Store = DAG->getStore(DAG->getEntryNode(), Loc, Value, Index, + PtrInfo.getWithOffset(Offset)); + Optional NumBytes = MemoryLocation::getSizeOrUnknown( + cast(Store)->getMemoryVT().getStoreSize()); + + bool IsAlias; + bool IsValid = BaseIndexOffset::computeAliasing( + Store.getNode(), NumBytes, Store.getNode(), NumBytes, *DAG, IsAlias); + + EXPECT_TRUE(IsValid); + EXPECT_TRUE(IsAlias); +} + +TEST_F(SelectionDAGAddressAnalysisTest, noAliasingFrameObjects) { + if (!TM) + return; + SDLoc Loc; + auto Int8VT = EVT::getIntegerVT(Context, 8); + // <4 x i8> + auto VecVT = EVT::getVectorVT(Context, Int8VT, 4); + // <2 x i8> + auto SubVecVT = EVT::getVectorVT(Context, Int8VT, 2); + SDValue FIPtr = DAG->CreateStackTemporary(VecVT); + int FI = cast(FIPtr.getNode())->getIndex(); + MachinePointerInfo PtrInfo = MachinePointerInfo::getFixedStack(*MF, FI); + SDValue Value = DAG->getConstant(0, Loc, SubVecVT); + TypeSize Offset0 = TypeSize::Fixed(0); + TypeSize Offset1 = SubVecVT.getStoreSize(); + SDValue Index0 = DAG->getMemBasePlusOffset(FIPtr, Offset0, Loc); + SDValue Index1 = DAG->getMemBasePlusOffset(FIPtr, Offset1, Loc); + SDValue Store0 = DAG->getStore(DAG->getEntryNode(), Loc, Value, Index0, + PtrInfo.getWithOffset(Offset0)); + SDValue Store1 = DAG->getStore(DAG->getEntryNode(), Loc, Value, Index1, + PtrInfo.getWithOffset(Offset1)); + Optional NumBytes0 = MemoryLocation::getSizeOrUnknown( + cast(Store0)->getMemoryVT().getStoreSize()); + Optional NumBytes1 = MemoryLocation::getSizeOrUnknown( + cast(Store1)->getMemoryVT().getStoreSize()); + + bool IsAlias; + bool IsValid = BaseIndexOffset::computeAliasing( + Store0.getNode(), NumBytes0, Store1.getNode(), NumBytes1, *DAG, IsAlias); + + EXPECT_TRUE(IsValid); + EXPECT_FALSE(IsAlias); +} + +TEST_F(SelectionDAGAddressAnalysisTest, unknownSizeFrameObjects) { + if (!TM) + return; + SDLoc Loc; + auto Int8VT = EVT::getIntegerVT(Context, 8); + // + auto VecVT = EVT::getVectorVT(Context, Int8VT, 4, true); + // + auto SubVecVT = EVT::getVectorVT(Context, Int8VT, 2, true); + SDValue FIPtr = DAG->CreateStackTemporary(VecVT); + int FI = cast(FIPtr.getNode())->getIndex(); + MachinePointerInfo PtrInfo = MachinePointerInfo::getFixedStack(*MF, FI); + SDValue Value = DAG->getConstant(0, Loc, SubVecVT); + TypeSize Offset0 = TypeSize::Fixed(0); + TypeSize Offset1 = SubVecVT.getStoreSize(); + SDValue Index0 = DAG->getMemBasePlusOffset(FIPtr, Offset0, Loc); + SDValue Index1 = DAG->getMemBasePlusOffset(FIPtr, Offset1, Loc); + SDValue Store0 = DAG->getStore(DAG->getEntryNode(), Loc, Value, Index0, + PtrInfo.getWithOffset(Offset0)); + SDValue Store1 = DAG->getStore(DAG->getEntryNode(), Loc, Value, Index1, + PtrInfo.getWithOffset(Offset1)); + Optional NumBytes0 = MemoryLocation::getSizeOrUnknown( + cast(Store0)->getMemoryVT().getStoreSize()); + Optional NumBytes1 = MemoryLocation::getSizeOrUnknown( + cast(Store1)->getMemoryVT().getStoreSize()); + + bool IsAlias; + bool IsValid = BaseIndexOffset::computeAliasing( + Store0.getNode(), NumBytes0, Store1.getNode(), NumBytes1, *DAG, IsAlias); + + EXPECT_FALSE(IsValid); +} + +TEST_F(SelectionDAGAddressAnalysisTest, globalWithFrameObject) { + if (!TM) + return; + SDLoc Loc; + auto Int8VT = EVT::getIntegerVT(Context, 8); + // + auto VecVT = EVT::getVectorVT(Context, Int8VT, 4, true); + SDValue FIPtr = DAG->CreateStackTemporary(VecVT); + int FI = cast(FIPtr.getNode())->getIndex(); + MachinePointerInfo PtrInfo = MachinePointerInfo::getFixedStack(*MF, FI); + SDValue Value = DAG->getConstant(0, Loc, VecVT); + TypeSize Offset = TypeSize::Fixed(0); + SDValue Index = DAG->getMemBasePlusOffset(FIPtr, Offset, Loc); + SDValue Store = DAG->getStore(DAG->getEntryNode(), Loc, Value, Index, + PtrInfo.getWithOffset(Offset)); + Optional NumBytes = MemoryLocation::getSizeOrUnknown( + cast(Store)->getMemoryVT().getStoreSize()); + EVT GTy = DAG->getTargetLoweringInfo().getValueType(DAG->getDataLayout(), + G->getType()); + SDValue GValue = DAG->getConstant(0, Loc, GTy); + SDValue GAddr = DAG->getGlobalAddress(G, Loc, GTy); + SDValue GStore = DAG->getStore(DAG->getEntryNode(), Loc, GValue, GAddr, + MachinePointerInfo(G, 0)); + Optional GNumBytes = MemoryLocation::getSizeOrUnknown( + cast(GStore)->getMemoryVT().getStoreSize()); + + bool IsAlias; + bool IsValid = BaseIndexOffset::computeAliasing( + Store.getNode(), NumBytes, GStore.getNode(), GNumBytes, *DAG, IsAlias); + + EXPECT_TRUE(IsValid); + EXPECT_FALSE(IsAlias); +} + +TEST_F(SelectionDAGAddressAnalysisTest, fixedSizeFrameObjectsWithinDiff) { + if (!TM) + return; + SDLoc Loc; + auto Int8VT = EVT::getIntegerVT(Context, 8); + // + auto VecVT = EVT::getVectorVT(Context, Int8VT, 4, true); + // + auto SubVecVT = EVT::getVectorVT(Context, Int8VT, 2, true); + // <2 x i8> + auto SubFixedVecVT2xi8 = EVT::getVectorVT(Context, Int8VT, 2); + SDValue FIPtr = DAG->CreateStackTemporary(VecVT); + int FI = cast(FIPtr.getNode())->getIndex(); + MachinePointerInfo PtrInfo = MachinePointerInfo::getFixedStack(*MF, FI); + SDValue Value0 = DAG->getConstant(0, Loc, SubFixedVecVT2xi8); + SDValue Value1 = DAG->getConstant(0, Loc, SubVecVT); + TypeSize Offset0 = TypeSize::Fixed(0); + TypeSize Offset1 = SubFixedVecVT2xi8.getStoreSize(); + SDValue Index0 = DAG->getMemBasePlusOffset(FIPtr, Offset0, Loc); + SDValue Index1 = DAG->getMemBasePlusOffset(FIPtr, Offset1, Loc); + SDValue Store0 = DAG->getStore(DAG->getEntryNode(), Loc, Value0, Index0, + PtrInfo.getWithOffset(Offset0)); + SDValue Store1 = DAG->getStore(DAG->getEntryNode(), Loc, Value1, Index1, + PtrInfo.getWithOffset(Offset1)); + Optional NumBytes0 = MemoryLocation::getSizeOrUnknown( + cast(Store0)->getMemoryVT().getStoreSize()); + Optional NumBytes1 = MemoryLocation::getSizeOrUnknown( + cast(Store1)->getMemoryVT().getStoreSize()); + + bool IsAlias; + bool IsValid = BaseIndexOffset::computeAliasing( + Store0.getNode(), NumBytes0, Store1.getNode(), NumBytes1, *DAG, IsAlias); + EXPECT_TRUE(IsValid); + EXPECT_FALSE(IsAlias); + + IsValid = BaseIndexOffset::computeAliasing( + Store1.getNode(), NumBytes1, Store0.getNode(), NumBytes0, *DAG, IsAlias); + EXPECT_TRUE(IsValid); + EXPECT_FALSE(IsAlias); +} + +TEST_F(SelectionDAGAddressAnalysisTest, fixedSizeFrameObjectsOutOfDiff) { + if (!TM) + return; + SDLoc Loc; + auto Int8VT = EVT::getIntegerVT(Context, 8); + // + auto VecVT = EVT::getVectorVT(Context, Int8VT, 4, true); + // + auto SubVecVT = EVT::getVectorVT(Context, Int8VT, 2, true); + // <2 x i8> + auto SubFixedVecVT2xi8 = EVT::getVectorVT(Context, Int8VT, 2); + // <4 x i8> + auto SubFixedVecVT4xi8 = EVT::getVectorVT(Context, Int8VT, 4); + SDValue FIPtr = DAG->CreateStackTemporary(VecVT); + int FI = cast(FIPtr.getNode())->getIndex(); + MachinePointerInfo PtrInfo = MachinePointerInfo::getFixedStack(*MF, FI); + SDValue Value0 = DAG->getConstant(0, Loc, SubFixedVecVT4xi8); + SDValue Value1 = DAG->getConstant(0, Loc, SubVecVT); + TypeSize Offset0 = TypeSize::Fixed(0); + TypeSize Offset1 = SubFixedVecVT2xi8.getStoreSize(); + SDValue Index0 = DAG->getMemBasePlusOffset(FIPtr, Offset0, Loc); + SDValue Index1 = DAG->getMemBasePlusOffset(FIPtr, Offset1, Loc); + SDValue Store0 = DAG->getStore(DAG->getEntryNode(), Loc, Value0, Index0, + PtrInfo.getWithOffset(Offset0)); + SDValue Store1 = DAG->getStore(DAG->getEntryNode(), Loc, Value1, Index1, + PtrInfo.getWithOffset(Offset1)); + Optional NumBytes0 = MemoryLocation::getSizeOrUnknown( + cast(Store0)->getMemoryVT().getStoreSize()); + Optional NumBytes1 = MemoryLocation::getSizeOrUnknown( + cast(Store1)->getMemoryVT().getStoreSize()); + + bool IsAlias; + bool IsValid = BaseIndexOffset::computeAliasing( + Store0.getNode(), NumBytes0, Store1.getNode(), NumBytes1, *DAG, IsAlias); + EXPECT_TRUE(IsValid); + EXPECT_TRUE(IsAlias); +} + +TEST_F(SelectionDAGAddressAnalysisTest, twoFixedStackObjects) { + if (!TM) + return; + SDLoc Loc; + auto Int8VT = EVT::getIntegerVT(Context, 8); + // + auto VecVT = EVT::getVectorVT(Context, Int8VT, 2, true); + // <2 x i8> + auto FixedVecVT = EVT::getVectorVT(Context, Int8VT, 2); + SDValue FIPtr0 = DAG->CreateStackTemporary(FixedVecVT); + SDValue FIPtr1 = DAG->CreateStackTemporary(VecVT); + int FI0 = cast(FIPtr0.getNode())->getIndex(); + int FI1 = cast(FIPtr1.getNode())->getIndex(); + MachinePointerInfo PtrInfo0 = MachinePointerInfo::getFixedStack(*MF, FI0); + MachinePointerInfo PtrInfo1 = MachinePointerInfo::getFixedStack(*MF, FI1); + SDValue Value0 = DAG->getConstant(0, Loc, FixedVecVT); + SDValue Value1 = DAG->getConstant(0, Loc, VecVT); + TypeSize Offset0 = TypeSize::Fixed(0); + SDValue Index0 = DAG->getMemBasePlusOffset(FIPtr0, Offset0, Loc); + SDValue Index1 = DAG->getMemBasePlusOffset(FIPtr1, Offset0, Loc); + SDValue Store0 = DAG->getStore(DAG->getEntryNode(), Loc, Value0, Index0, + PtrInfo0.getWithOffset(Offset0)); + SDValue Store1 = DAG->getStore(DAG->getEntryNode(), Loc, Value1, Index1, + PtrInfo1.getWithOffset(Offset0)); + Optional NumBytes0 = MemoryLocation::getSizeOrUnknown( + cast(Store0)->getMemoryVT().getStoreSize()); + Optional NumBytes1 = MemoryLocation::getSizeOrUnknown( + cast(Store1)->getMemoryVT().getStoreSize()); + + bool IsAlias; + bool IsValid = BaseIndexOffset::computeAliasing( + Store0.getNode(), NumBytes0, Store1.getNode(), NumBytes1, *DAG, IsAlias); + EXPECT_TRUE(IsValid); + EXPECT_FALSE(IsAlias); +} + +} // end namespace llvm