LocalAliasAnalysisTests.cpp

Go to the documentation of this file.

/*
 * Copyright 2025 Håvard Krogstie <krogstie.havard@gmail.com>
 * See COPYING for terms of redistribution.
 */
 
#include <gtest/gtest.h>
 
#include <jlm/llvm/ir/CallingConvention.hpp>
#include <jlm/llvm/ir/Linkage.hpp>
#include <jlm/llvm/ir/operators/alloca.hpp>
#include <jlm/llvm/ir/operators/call.hpp>
#include <jlm/llvm/ir/operators/GetElementPtr.hpp>
#include <jlm/llvm/ir/operators/IntegerOperations.hpp>
#include <jlm/llvm/ir/operators/lambda.hpp>
#include <jlm/llvm/ir/operators/Load.hpp>
#include <jlm/llvm/ir/operators/MemoryStateOperations.hpp>
#include <jlm/llvm/ir/operators/operators.hpp>
#include <jlm/llvm/ir/operators/Store.hpp>
#include <jlm/llvm/ir/RvsdgModule.hpp>
#include <jlm/llvm/ir/types.hpp>
#include <jlm/llvm/opt/alias-analyses/LocalAliasAnalysis.hpp>
#include <jlm/llvm/TestRvsdgs.hpp>
#include <jlm/rvsdg/bitstring/constant.hpp>
#include <jlm/rvsdg/bitstring/type.hpp>
#include <jlm/rvsdg/control.hpp>
#include <jlm/rvsdg/gamma.hpp>
#include <jlm/rvsdg/graph.hpp>
#include <jlm/rvsdg/theta.hpp>
#include <jlm/rvsdg/view.hpp>
 
static void
Expect(
    jlm::llvm::aa::AliasAnalysis & aa,
    const jlm::rvsdg::Output & p1,
    size_t s1,
    const jlm::rvsdg::Output & p2,
    size_t s2,
    jlm::llvm::aa::AliasAnalysis::AliasQueryResponse expected)
{
  const auto actual = aa.Query(p1, s1, p2, s2);
  EXPECT_EQ(actual, expected);
 
  // An alias analysis query should always be symmetrical, so check the opposite as well
  const auto mirror = aa.Query(p2, s2, p1, s1);
  EXPECT_EQ(mirror, expected);
}
 
class LocalAliasAnalysisTest1 final : public jlm::llvm::RvsdgTest
{
  struct Outputs
  {
    jlm::rvsdg::Output * GetPtr = {};
    jlm::rvsdg::Output * Global = {};
    jlm::rvsdg::Output * GlobalShort = {};
    jlm::rvsdg::Output * Array = {};
    jlm::rvsdg::Output * Func = {};
    jlm::rvsdg::Output * P = {};
    jlm::rvsdg::Output * Alloca1 = {};
    jlm::rvsdg::Output * Alloca2 = {};
    jlm::rvsdg::Output * Q = {};
    jlm::rvsdg::Output * QPlus2 = {};
    jlm::rvsdg::Output * QAgain = {};
    jlm::rvsdg::Output * Arr1 = {};
    jlm::rvsdg::Output * Arr2 = {};
    jlm::rvsdg::Output * Arr3 = {};
    jlm::rvsdg::Output * ArrUnknown = {};
    jlm::rvsdg::Output * BytePtr = {};
    jlm::rvsdg::Output * BytePtrPlus2 = {};
  };
 
public:
  const Outputs &
  GetOutputs() const noexcept
  {
    return Outputs_;
  }
 
private:
  std::unique_ptr<jlm::llvm::LlvmRvsdgModule>
  SetupRvsdg() override
  {
    using namespace jlm;
    using namespace jlm::llvm;
 
    auto rvsdgModule = LlvmRvsdgModule::Create(jlm::util::FilePath(""), "", "");
    auto & rvsdg = rvsdgModule->Rvsdg();
 
    const auto pointerType = PointerType::Create();
    const auto intType = rvsdg::BitType::Create(32);
    const auto shortType = rvsdg::BitType::Create(16);
    const auto byteType = rvsdg::BitType::Create(8);
    const auto intArrayType = ArrayType::Create(intType, 10);
    const auto ioStateType = IOStateType::Create();
    const auto memoryStateType = MemoryStateType::Create();
 
    const auto funcType = rvsdg::FunctionType::Create(
        { pointerType, ioStateType, memoryStateType },
        { ioStateType, memoryStateType });
 
    const auto getPtrFuncType = rvsdg::FunctionType::Create(
        { ioStateType, memoryStateType },
        { pointerType, ioStateType, memoryStateType });
 
    Outputs_.GetPtr = &LlvmGraphImport::createFunctionImport(
        rvsdg,
        getPtrFuncType,
        "getPtr",
        Linkage::externalLinkage,
        CallingConvention::Default);
 
    Outputs_.Global = &LlvmGraphImport::createGlobalImport(
        rvsdg,
        intType,
        pointerType,
        "global",
        Linkage::externalLinkage,
        false,
        4);
    Outputs_.GlobalShort = &LlvmGraphImport::createGlobalImport(
        rvsdg,
        shortType,
        pointerType,
        "globalShort",
        Linkage::externalLinkage,
        false,
        4);
    Outputs_.Array = &LlvmGraphImport::createGlobalImport(
        rvsdg,
        intArrayType,
        pointerType,
        "array",
        Linkage::externalLinkage,
        false,
        4);
 
    // Setup the function "func"
    {
      auto & lambdaNode = *rvsdg::LambdaNode::Create(
          rvsdg.GetRootRegion(),
          LlvmLambdaOperation::Create(funcType, "func", Linkage::internalLinkage));
 
      Outputs_.P = lambdaNode.GetFunctionArguments()[0];
      auto ioState = lambdaNode.GetFunctionArguments()[1];
      auto memoryState = lambdaNode.GetFunctionArguments()[2];
 
      const auto getPtrCtxVar = lambdaNode.AddContextVar(*Outputs_.GetPtr).inner;
      const auto arrayCtxVar = lambdaNode.AddContextVar(*Outputs_.Array).inner;
      const auto globalCtxVar = lambdaNode.AddContextVar(*Outputs_.Global).inner;
 
      const auto constantOne =
          &rvsdg::BitConstantOperation::create(*lambdaNode.subregion(), { 32, 1 });
      const auto constantTwo =
          &rvsdg::BitConstantOperation::create(*lambdaNode.subregion(), { 32, 2 });
      const auto constantThree =
          &rvsdg::BitConstantOperation::create(*lambdaNode.subregion(), { 32, 3 });
      const auto constantFour =
          &rvsdg::BitConstantOperation::create(*lambdaNode.subregion(), { 32, 4 });
      const auto constantMinusTwo =
          &rvsdg::BitConstantOperation::create(*lambdaNode.subregion(), { 32, -2 });
 
      const auto alloca1Outputs = AllocaOperation::create(intType, constantOne, 4);
      const auto alloca2Outputs = AllocaOperation::create(intType, constantOne, 4);
 
      Outputs_.Alloca1 = alloca1Outputs[0];
      Outputs_.Alloca2 = alloca2Outputs[0];
 
      memoryState =
          MemoryStateMergeOperation::Create({ memoryState, alloca1Outputs[1], alloca2Outputs[1] });
 
      // Load from the pointer p
      const auto loadP =
          LoadNonVolatileOperation::Create(Outputs_.P, { memoryState }, pointerType, 8);
      memoryState = loadP[1];
 
      Outputs_.Q = GetElementPtrOperation::create(loadP[0], { constantTwo }, intType);
      Outputs_.QPlus2 = GetElementPtrOperation::create(loadP[0], { constantFour }, intType);
      Outputs_.QAgain =
          GetElementPtrOperation::create(Outputs_.QPlus2, { constantMinusTwo }, intType);
 
      // Create offsets into array
      Outputs_.Arr1 = GetElementPtrOperation::create(arrayCtxVar, { constantOne }, intType);
      Outputs_.Arr2 = GetElementPtrOperation::create(arrayCtxVar, { constantTwo }, intType);
      Outputs_.Arr3 = GetElementPtrOperation::create(arrayCtxVar, { constantThree }, intType);
 
      // Create a load of the global integer variable "global"
      const auto loadGlobal =
          LoadNonVolatileOperation::Create(globalCtxVar, { memoryState }, intType, 4);
      memoryState = loadGlobal[1];
      Outputs_.ArrUnknown =
          GetElementPtrOperation::create(arrayCtxVar, { loadGlobal[0] }, byteType);
 
      // Make alloca2 escape
      const auto storeOutputs =
          StoreNonVolatileOperation::Create(Outputs_.P, Outputs_.Alloca2, { memoryState }, 4);
      memoryState = storeOutputs[0];
 
      // Get bytePtr by calling getPtr()
      const auto callOutputs =
          CallOperation::Create(getPtrCtxVar, getPtrFuncType, { ioState, memoryState });
      Outputs_.BytePtr = callOutputs[0];
      ioState = callOutputs[1];
      memoryState = callOutputs[2];
 
      Outputs_.BytePtrPlus2 =
          GetElementPtrOperation::create(Outputs_.BytePtr, { constantTwo }, byteType);
 
      lambdaNode.finalize({ ioState, memoryState });
      Outputs_.Func = lambdaNode.output();
    }
 
    return rvsdgModule;
  }
 
  Outputs Outputs_ = {};
};
 
TEST(LocalAliasAnalysisTests, TestLocalAliasAnalysis)
{
  using namespace jlm::llvm::aa;
 
  // Arrange
  LocalAliasAnalysisTest1 rvsdg;
  rvsdg.InitializeTest();
  const auto & outputs = rvsdg.GetOutputs();
 
  jlm::rvsdg::view(&rvsdg.graph().GetRootRegion(), stdout);
 
  LocalAliasAnalysis aa;
 
  // Assert
 
  // Distinct global variables do not alias
  Expect(aa, *outputs.Global, 4, *outputs.GlobalShort, 2, AliasAnalysis::NoAlias);
  Expect(aa, *outputs.Global, 4, *outputs.Arr1, 4, AliasAnalysis::NoAlias);
 
  // An alloca never aliases any other memory allocating operation
  Expect(aa, *outputs.Alloca2, 4, *outputs.Alloca1, 4, AliasAnalysis::NoAlias);
  Expect(aa, *outputs.Alloca2, 4, *outputs.Global, 4, AliasAnalysis::NoAlias);
  Expect(aa, *outputs.Alloca2, 4, *outputs.Array, 4, AliasAnalysis::NoAlias);
  Expect(aa, *outputs.Alloca2, 4, *outputs.Arr1, 4, AliasAnalysis::NoAlias);
 
  // An alloca that has not "escaped" can not alias external pointers
  Expect(aa, *outputs.Alloca1, 4, *outputs.BytePtr, 4, AliasAnalysis::NoAlias);
 
  // An alloca that has "escaped" may alias external pointers
  Expect(aa, *outputs.Alloca2, 4, *outputs.BytePtr, 4, AliasAnalysis::MayAlias);
 
  // Distinct offsets can not alias, unless the access regions overlap
  Expect(aa, *outputs.Q, 8, *outputs.QPlus2, 8, AliasAnalysis::NoAlias);
  Expect(aa, *outputs.Q, 9, *outputs.QPlus2, 8, AliasAnalysis::MayAlias);
  Expect(aa, *outputs.Q, 8, *outputs.QPlus2, 16, AliasAnalysis::NoAlias);
 
  // Identical offsets are MustAlias
  Expect(aa, *outputs.Q, 4, *outputs.QAgain, 4, AliasAnalysis::MustAlias);
 
  // q is at least 8 bytes into the storage instance of *p
  // so it can not alias with the first 8 bytes of array
  Expect(aa, *outputs.Array, 8, *outputs.Q, 4, AliasAnalysis::NoAlias);
  Expect(aa, *outputs.Array, 9, *outputs.Q, 4, AliasAnalysis::MayAlias);
  // We know that arr1, arr2 and arr3 are 4, 8 and 12 bytes into array
  Expect(aa, *outputs.Arr1, 4, *outputs.Q, 4, AliasAnalysis::NoAlias);
  Expect(aa, *outputs.Arr1, 5, *outputs.Q, 4, AliasAnalysis::MayAlias);
  Expect(aa, *outputs.Arr2, 4, *outputs.Q, 4, AliasAnalysis::MayAlias);
  Expect(aa, *outputs.Arr3, 4, *outputs.Q, 4, AliasAnalysis::MayAlias);
 
  // An unknown offset into array can only alias with array, at all offsets
  Expect(aa, *outputs.ArrUnknown, 4, *outputs.Array, 4, AliasAnalysis::MayAlias);
  Expect(aa, *outputs.ArrUnknown, 4, *outputs.Arr1, 4, AliasAnalysis::MayAlias);
  Expect(aa, *outputs.ArrUnknown, 4, *outputs.Arr2, 4, AliasAnalysis::MayAlias);
  Expect(aa, *outputs.ArrUnknown, 4, *outputs.Arr3, 4, AliasAnalysis::MayAlias);
  Expect(aa, *outputs.ArrUnknown, 4, *outputs.Global, 4, AliasAnalysis::NoAlias);
  // Q may be a pointer into array, so it is also "MayAlias"
  Expect(aa, *outputs.ArrUnknown, 4, *outputs.Q, 4, AliasAnalysis::MayAlias);
 
  // We know that q is at least 16 bytes into its storage instance,
  // so it may not alias with storage instances that are 16 bytes or less
  Expect(aa, *outputs.Q, 4, *outputs.Global, 4, AliasAnalysis::NoAlias);
 
  // A five byte operation can never target the 4 byte global variable
  Expect(aa, *outputs.BytePtr, 5, *outputs.Global, 4, AliasAnalysis::NoAlias);
  // A four byte operation can, however
  Expect(aa, *outputs.BytePtr, 4, *outputs.Global, 4, AliasAnalysis::MayAlias);
  // Even a 40 byte operation can target the 40 byte global array
  Expect(aa, *outputs.BytePtr, 40, *outputs.Array, 4, AliasAnalysis::MayAlias);
  // The 40 byte operation may overlap with 4 bytes at any offset within the Array
  Expect(aa, *outputs.BytePtr, 40, *outputs.Arr3, 4, AliasAnalysis::MayAlias);
 
  // BytePtrPlus2 has an offset of at least 2, so can not alias with the first 2 bytes of anything
  Expect(aa, *outputs.BytePtrPlus2, 2, *outputs.Alloca2, 2, AliasAnalysis::NoAlias);
  Expect(aa, *outputs.BytePtrPlus2, 2, *outputs.Alloca2, 3, AliasAnalysis::MayAlias);
  Expect(aa, *outputs.BytePtrPlus2, 2, *outputs.Array, 2, AliasAnalysis::NoAlias);
  Expect(aa, *outputs.BytePtrPlus2, 2, *outputs.Array, 3, AliasAnalysis::MayAlias);
  // Arr1 is already 4 bytes into array, so BytePtrPlus2 can alias with it
  Expect(aa, *outputs.BytePtrPlus2, 2, *outputs.Arr1, 2, AliasAnalysis::MayAlias);
}
 
class LocalAliasAnalysisTest2 final : public jlm::llvm::RvsdgTest
{
  struct Outputs
  {
    jlm::rvsdg::Output * Func = {};
    jlm::rvsdg::Output * X = {};
    jlm::rvsdg::Output * Ptr = {};
    jlm::rvsdg::Output * Alloca1 = {};
    jlm::rvsdg::Output * Alloca2 = {};
    jlm::rvsdg::Output * Alloca3 = {};
    jlm::rvsdg::Output * AllocaUnknown = {};
    jlm::rvsdg::Output * AllocaUnknownPlus1 = {};
    jlm::rvsdg::Output * Alloca3Plus1 = {};
    jlm::rvsdg::Output * Alloca3UnknownOffset = {};
    jlm::rvsdg::Output * Alloca3KnownOffset = {};
  };
 
public:
  const Outputs &
  GetOutputs() const noexcept
  {
    return Outputs_;
  }
 
private:
  std::unique_ptr<jlm::llvm::LlvmRvsdgModule>
  SetupRvsdg() override
  {
    using namespace jlm;
    using namespace jlm::llvm;
 
    auto rvsdgModule = LlvmRvsdgModule::Create(jlm::util::FilePath(""), "", "");
    auto & rvsdg = rvsdgModule->Rvsdg();
 
    const auto pointerType = PointerType::Create();
    const auto int1Type = rvsdg::BitType::Create(1);
    const auto int32Type = rvsdg::BitType::Create(32);
    const auto int64Type = rvsdg::BitType::Create(64);
    const auto intArrayType = ArrayType::Create(int32Type, 2);
    const auto ioStateType = IOStateType::Create();
    const auto memoryStateType = MemoryStateType::Create();
 
    const auto funcType = rvsdg::FunctionType::Create(
        { int1Type, pointerType, ioStateType, memoryStateType },
        { ioStateType, memoryStateType });
 
    // Setup the function "func"
    {
      auto & lambdaNode = *rvsdg::LambdaNode::Create(
          rvsdg.GetRootRegion(),
          LlvmLambdaOperation::Create(funcType, "func", Linkage::internalLinkage));
 
      Outputs_.X = lambdaNode.GetFunctionArguments()[0];
      Outputs_.Ptr = lambdaNode.GetFunctionArguments()[1];
      auto ioState = lambdaNode.GetFunctionArguments()[2];
      auto memoryState = lambdaNode.GetFunctionArguments()[3];
 
      const auto constantZero =
          &rvsdg::BitConstantOperation::create(*lambdaNode.subregion(), { 32, 0 });
      const auto constantOne =
          &rvsdg::BitConstantOperation::create(*lambdaNode.subregion(), { 32, 1 });
 
      const auto alloca1Outputs = AllocaOperation::create(int32Type, constantOne, 4);
      const auto alloca2Outputs = AllocaOperation::create(int64Type, constantOne, 4);
      const auto alloca3Outputs = AllocaOperation::create(intArrayType, constantOne, 4);
 
      Outputs_.Alloca1 = alloca1Outputs[0];
      Outputs_.Alloca2 = alloca2Outputs[0];
      Outputs_.Alloca3 = alloca3Outputs[0];
 
      memoryState = MemoryStateMergeOperation::Create(
          { memoryState, alloca1Outputs[1], alloca2Outputs[1], alloca3Outputs[1] });
 
      const auto matchResult = rvsdg::MatchOperation::Create(*Outputs_.X, { { 1, 1 } }, 0, 2);
      const auto gamma = rvsdg::GammaNode::create(matchResult, 2);
      const auto entryVarA1 = gamma->AddEntryVar(Outputs_.Alloca1);
      const auto entryVarA2 = gamma->AddEntryVar(Outputs_.Alloca2);
      const auto exitVar =
          gamma->AddExitVar({ entryVarA1.branchArgument[0], entryVarA2.branchArgument[1] });
      Outputs_.AllocaUnknown = exitVar.output;
 
      Outputs_.AllocaUnknownPlus1 =
          GetElementPtrOperation::create(Outputs_.AllocaUnknown, { constantOne }, int32Type);
 
      Outputs_.Alloca3Plus1 = GetElementPtrOperation::create(
          Outputs_.Alloca3,
          { constantZero, constantOne },
          intArrayType);
 
      Outputs_.Alloca3UnknownOffset = rvsdg::CreateOpNode<SelectOperation>(
                                          { Outputs_.X, Outputs_.Alloca3, Outputs_.Alloca3Plus1 },
                                          pointerType)
                                          .output(0);
 
      Outputs_.Alloca3KnownOffset =
          rvsdg::CreateOpNode<SelectOperation>(
              { Outputs_.X, Outputs_.Alloca3Plus1, Outputs_.Alloca3Plus1 },
              pointerType)
              .output(0);
 
      lambdaNode.finalize({ ioState, memoryState });
      Outputs_.Func = lambdaNode.output();
    }
 
    return rvsdgModule;
  }
 
  Outputs Outputs_ = {};
};
 
TEST(LocalAliasAnalysisTests, TestLocalAliasAnalysisMultipleOrigins)
{
  using namespace jlm::llvm::aa;
 
  // Arrange
  LocalAliasAnalysisTest2 rvsdg;
  rvsdg.InitializeTest();
  const auto & outputs = rvsdg.GetOutputs();
 
  jlm::rvsdg::view(&rvsdg.graph().GetRootRegion(), stdout);
 
  LocalAliasAnalysis aa;
 
  // Assert
 
  // First check that none of the allocas have been mixed up with unknown pointers
  Expect(aa, *outputs.Alloca1, 4, *outputs.Ptr, 4, AliasAnalysis::NoAlias);
  Expect(aa, *outputs.Alloca2, 4, *outputs.Ptr, 4, AliasAnalysis::NoAlias);
  Expect(aa, *outputs.Alloca3, 4, *outputs.Ptr, 4, AliasAnalysis::NoAlias);
  Expect(aa, *outputs.Alloca3Plus1, 4, *outputs.Ptr, 4, AliasAnalysis::NoAlias);
 
  // Check that allocaUnknown may alias only alloca1 or alloca2
  Expect(aa, *outputs.AllocaUnknown, 4, *outputs.Alloca1, 4, AliasAnalysis::MayAlias);
  Expect(aa, *outputs.AllocaUnknown, 4, *outputs.Alloca2, 4, AliasAnalysis::MayAlias);
  Expect(aa, *outputs.AllocaUnknown, 4, *outputs.Alloca3, 4, AliasAnalysis::NoAlias);
  Expect(aa, *outputs.AllocaUnknown, 4, *outputs.Alloca3Plus1, 4, AliasAnalysis::NoAlias);
  Expect(aa, *outputs.AllocaUnknown, 4, *outputs.Ptr, 4, AliasAnalysis::NoAlias);
 
  // If performing an 8 byte operation, it may only alias alloca2, becoming a must alias
  Expect(aa, *outputs.AllocaUnknown, 8, *outputs.Alloca1, 4, AliasAnalysis::NoAlias);
  Expect(aa, *outputs.AllocaUnknown, 8, *outputs.Alloca2, 4, AliasAnalysis::MustAlias);
  // Performing a 9 byte operation is neither legal for alloca1 nor alloca2
  Expect(aa, *outputs.AllocaUnknown, 9, *outputs.Alloca2, 4, AliasAnalysis::NoAlias);
 
  // Adding a 4 byte offset forces all operations to be on alloca2
  Expect(aa, *outputs.AllocaUnknownPlus1, 1, *outputs.Alloca1, 1, AliasAnalysis::NoAlias);
  // We also know that we are 4 bytes into alloca2
  Expect(aa, *outputs.AllocaUnknownPlus1, 4, *outputs.Alloca2, 4, AliasAnalysis::NoAlias);
  Expect(aa, *outputs.AllocaUnknownPlus1, 4, *outputs.Alloca2, 5, AliasAnalysis::MayAlias);
  // Performing a 5 byte operation is neither legal for alloca1 nor alloca2
  Expect(aa, *outputs.AllocaUnknownPlus1, 5, *outputs.Alloca2, 8, AliasAnalysis::NoAlias);
 
  // Check that the offset of allocaUnknown is correctly calculated (4 bytes)
  Expect(aa, *outputs.AllocaUnknown, 4, *outputs.AllocaUnknownPlus1, 4, AliasAnalysis::NoAlias);
  Expect(aa, *outputs.AllocaUnknown, 5, *outputs.AllocaUnknownPlus1, 4, AliasAnalysis::MayAlias);
 
  // Check that the pointer with an unknown offset into alloca3 does not alias anything else
  Expect(aa, *outputs.Alloca3UnknownOffset, 4, *outputs.Alloca1, 4, AliasAnalysis::NoAlias);
  Expect(aa, *outputs.Alloca3UnknownOffset, 4, *outputs.Alloca2, 4, AliasAnalysis::NoAlias);
  Expect(aa, *outputs.Alloca3UnknownOffset, 4, *outputs.AllocaUnknown, 4, AliasAnalysis::NoAlias);
  Expect(aa, *outputs.Alloca3UnknownOffset, 4, *outputs.Ptr, 4, AliasAnalysis::NoAlias);
 
  // It may alias alloca3 and alloca3 + 1
  Expect(aa, *outputs.Alloca3UnknownOffset, 4, *outputs.Alloca3, 4, AliasAnalysis::MayAlias);
  Expect(aa, *outputs.Alloca3UnknownOffset, 4, *outputs.Alloca3Plus1, 4, AliasAnalysis::MayAlias);
 
  // If performing an 8 byte operation, we know that we are at the start of alloca3
  Expect(aa, *outputs.Alloca3UnknownOffset, 8, *outputs.Alloca3, 4, AliasAnalysis::MustAlias);
  // We still overlap with the second half of alloca3
  Expect(aa, *outputs.Alloca3UnknownOffset, 8, *outputs.Alloca3Plus1, 4, AliasAnalysis::MayAlias);
 
  // The select with duplicate operands should be a single origin: alloca3
  Expect(aa, *outputs.Alloca3KnownOffset, 4, *outputs.Alloca3, 4, AliasAnalysis::NoAlias);
  Expect(aa, *outputs.Alloca3KnownOffset, 4, *outputs.Alloca3Plus1, 4, AliasAnalysis::MustAlias);
}
 
class LocalAliasAnalysisLoopVariantPointersTest final : public jlm::llvm::RvsdgTest
{
  struct Outputs
  {
    jlm::rvsdg::Output * Func = {};
    jlm::rvsdg::Output * Unknown = {};
    jlm::rvsdg::Output * GlobalArray = {};
    jlm::rvsdg::Output * Array = {};
    jlm::rvsdg::Output * PInLoop = {};
    jlm::rvsdg::Output * QInLoop = {};
    jlm::rvsdg::Output * PAfterLoop = {};
    jlm::rvsdg::Output * QAfterLoop = {};
  };
 
public:
  const Outputs &
  GetOutputs() const noexcept
  {
    return Outputs_;
  }
 
private:
  std::unique_ptr<jlm::llvm::LlvmRvsdgModule>
  SetupRvsdg() override
  {
    using namespace jlm;
    using namespace jlm::llvm;
 
    auto rvsdgModule = LlvmRvsdgModule::Create(jlm::util::FilePath(""), "", "");
    auto & rvsdg = rvsdgModule->Rvsdg();
 
    const auto pointerType = PointerType::Create();
    const auto intType = rvsdg::BitType::Create(32);
    const auto intArrayType = ArrayType::Create(intType, 101);
    const auto memoryStateType = MemoryStateType::Create();
 
    const auto funcType =
        rvsdg::FunctionType::Create({ pointerType, memoryStateType }, { intType, memoryStateType });
 
    Outputs_.GlobalArray = &LlvmGraphImport::createGlobalImport(
        rvsdg,
        intArrayType,
        pointerType,
        "globalArray",
        Linkage::externalLinkage,
        false,
        4);
 
    {
      auto & lambdaNode = *rvsdg::LambdaNode::Create(
          rvsdg.GetRootRegion(),
          LlvmLambdaOperation::Create(funcType, "func", Linkage::internalLinkage));
 
      Outputs_.Unknown = lambdaNode.GetFunctionArguments()[0];
      auto memoryState = lambdaNode.GetFunctionArguments()[1];
      const auto globalArrayCtxVar = lambdaNode.AddContextVar(*Outputs_.GlobalArray).inner;
 
      const auto constantZero =
          &rvsdg::BitConstantOperation::create(*lambdaNode.subregion(), { 32, 0 });
      const auto constantOne =
          &rvsdg::BitConstantOperation::create(*lambdaNode.subregion(), { 32, 1 });
 
      const auto allocaArrayOutputs = AllocaOperation::create(intArrayType, constantOne, 4);
      Outputs_.Array = allocaArrayOutputs[0];
      memoryState = MemoryStateMergeOperation::Create(
          std::vector<jlm::rvsdg::Output *>{ memoryState, allocaArrayOutputs[1] });
 
      const auto initialP = GetElementPtrOperation::create(
          Outputs_.Array,
          { constantZero, constantZero },
          intArrayType);
      const auto initialQ = GetElementPtrOperation::create(
          globalArrayCtxVar,
          { constantZero, constantZero },
          intArrayType);
 
      auto thetaNode = rvsdg::ThetaNode::create(lambdaNode.subregion());
      auto i = thetaNode->AddLoopVar(constantZero);
      auto p = thetaNode->AddLoopVar(initialP);
      auto q = thetaNode->AddLoopVar(initialQ);
      auto m = thetaNode->AddLoopVar(memoryState);
 
      const auto constantOneTheta =
          &rvsdg::BitConstantOperation::create(*thetaNode->subregion(), { 32, 1 });
      const auto constantHundredTheta =
          &rvsdg::BitConstantOperation::create(*thetaNode->subregion(), { 32, 100 });
 
      Outputs_.PInLoop = p.pre;
      Outputs_.QInLoop = q.pre;
 
      const auto storeP = StoreNonVolatileOperation::Create(Outputs_.PInLoop, i.pre, { m.pre }, 4);
      const auto storeQ =
          StoreNonVolatileOperation::Create(Outputs_.QInLoop, i.pre, { storeP[0] }, 4);
      const auto nextP = GetElementPtrOperation::create(p.pre, { constantOneTheta }, intType);
      const auto nextQ = GetElementPtrOperation::create(q.pre, { constantOneTheta }, intType);
      const auto increment = jlm::rvsdg::bitadd_op::create(32, i.pre, constantOneTheta);
      const auto continueLoop = jlm::rvsdg::bitult_op::create(32, increment, constantHundredTheta);
      auto & predicateNode = rvsdg::MatchOperation::CreateNode(*continueLoop, { { 1, 1 } }, 0, 2);
 
      i.post->divert_to(increment);
      p.post->divert_to(nextP);
      q.post->divert_to(nextQ);
      m.post->divert_to(storeQ[0]);
      thetaNode->set_predicate(predicateNode.output(0));
 
      Outputs_.PAfterLoop = p.output;
      Outputs_.QAfterLoop = q.output;
 
      const auto loadP =
          LoadNonVolatileOperation::Create(Outputs_.PAfterLoop, { m.output }, intType, 4);
      const auto loadQ =
          LoadNonVolatileOperation::Create(Outputs_.QAfterLoop, { loadP[1] }, intType, 4);
      const auto sum = jlm::rvsdg::bitadd_op::create(32, loadP[0], loadQ[0]);
 
      lambdaNode.finalize({ sum, loadQ[1] });
      Outputs_.Func = lambdaNode.output();
    }
 
    return rvsdgModule;
  }
 
  Outputs Outputs_ = {};
};
 
TEST(LocalAliasAnalysisTests, testLoopVariantPointers)
{
  using namespace jlm;
  using namespace jlm::llvm;
  using namespace jlm::llvm::aa;
 
  // Arrange
  LocalAliasAnalysisLoopVariantPointersTest rvsdg;
  rvsdg.InitializeTest();
  const auto & outputs = rvsdg.GetOutputs();
 
  jlm::rvsdg::view(&rvsdg.graph().GetRootRegion(), stdout);
 
  LocalAliasAnalysis aa;
 
  // Assert for loop-internal pointers
  Expect(aa, *outputs.PInLoop, 4, *outputs.QInLoop, 4, AliasAnalysis::NoAlias);
  Expect(aa, *outputs.PInLoop, 4, *outputs.GlobalArray, 4, AliasAnalysis::NoAlias);
  Expect(aa, *outputs.QInLoop, 4, *outputs.Array, 4, AliasAnalysis::NoAlias);
  Expect(aa, *outputs.PInLoop, 4, *outputs.Array, 4, AliasAnalysis::MayAlias);
  Expect(aa, *outputs.QInLoop, 4, *outputs.GlobalArray, 4, AliasAnalysis::MayAlias);
  // Against the unknown pointer
  Expect(aa, *outputs.PInLoop, 4, *outputs.Unknown, 4, AliasAnalysis::NoAlias);
  Expect(aa, *outputs.QInLoop, 4, *outputs.Unknown, 4, AliasAnalysis::MayAlias);
 
  // Assert for loop-external pointers traced through the theta node
  Expect(aa, *outputs.PAfterLoop, 4, *outputs.QAfterLoop, 4, AliasAnalysis::NoAlias);
  Expect(aa, *outputs.PAfterLoop, 4, *outputs.GlobalArray, 4, AliasAnalysis::NoAlias);
  Expect(aa, *outputs.QAfterLoop, 4, *outputs.Array, 4, AliasAnalysis::NoAlias);
  Expect(aa, *outputs.PAfterLoop, 4, *outputs.Array, 4, AliasAnalysis::MayAlias);
  Expect(aa, *outputs.QAfterLoop, 4, *outputs.GlobalArray, 4, AliasAnalysis::MayAlias);
  // Against the unknown pointer
  Expect(aa, *outputs.PAfterLoop, 4, *outputs.Unknown, 4, AliasAnalysis::NoAlias);
  Expect(aa, *outputs.QAfterLoop, 4, *outputs.Unknown, 4, AliasAnalysis::MayAlias);
}
 
class LocalAliasAnalysisArgumentAllocaTest final : public jlm::llvm::RvsdgTest
{
  struct Outputs
  {
    jlm::rvsdg::Output * Func = {};
    jlm::rvsdg::Output * Arg = {};
    jlm::rvsdg::Output * LocalAlloca = {};
  };
 
public:
  const Outputs &
  GetOutputs() const noexcept
  {
    return Outputs_;
  }
 
private:
  std::unique_ptr<jlm::llvm::LlvmRvsdgModule>
  SetupRvsdg() override
  {
    using namespace jlm;
    using namespace jlm::llvm;
 
    auto rvsdgModule = LlvmRvsdgModule::Create(jlm::util::FilePath(""), "", "");
    auto & rvsdg = rvsdgModule->Rvsdg();
 
    const auto pointerType = PointerType::Create();
    const auto intType = rvsdg::BitType::Create(32);
    const auto ioStateType = IOStateType::Create();
    const auto memoryStateType = MemoryStateType::Create();
 
    const auto funcType = rvsdg::FunctionType::Create(
        { pointerType, ioStateType, memoryStateType },
        { intType, ioStateType, memoryStateType });
 
    auto & opaqueImport = LlvmGraphImport::createFunctionImport(
        rvsdg,
        funcType,
        "opaque",
        Linkage::externalLinkage,
        CallingConvention::Default);
 
    {
      auto & lambdaNode = *rvsdg::LambdaNode::Create(
          rvsdg.GetRootRegion(),
          LlvmLambdaOperation::Create(funcType, "func", Linkage::internalLinkage));
 
      Outputs_.Arg = lambdaNode.GetFunctionArguments()[0];
      auto ioState = lambdaNode.GetFunctionArguments()[1];
      auto memoryState = lambdaNode.GetFunctionArguments()[2];
      const auto opaqueCtxVar = lambdaNode.AddContextVar(opaqueImport);
 
      const auto constantOne =
          IntegerConstantOperation::Create(*lambdaNode.subregion(), 32, 1).output(0);
      const auto allocaOutputs = AllocaOperation::create(intType, constantOne, 4);
 
      Outputs_.LocalAlloca = allocaOutputs[0];
      memoryState = MemoryStateMergeOperation::Create(
          std::vector<jlm::rvsdg::Output *>{ memoryState, allocaOutputs[1] });
 
      // call opaque(&local);
      auto & callOpaque = CallOperation::CreateNode(
          opaqueCtxVar.inner,
          funcType,
          { Outputs_.LocalAlloca, ioState, memoryState });
      ioState = &CallOperation::GetIOStateOutput(callOpaque);
      memoryState = &CallOperation::GetMemoryStateOutput(callOpaque);
 
      // local = 20
      const auto constantTwenty =
          IntegerConstantOperation::Create(*lambdaNode.subregion(), 32, 20).output(0);
      const auto storeLocalOutputs = StoreNonVolatileOperation::Create(
          Outputs_.LocalAlloca,
          constantTwenty,
          { memoryState },
          4);
      memoryState = storeLocalOutputs[0];
 
      // return *arg
      const auto loadArgOutputs =
          LoadNonVolatileOperation::Create(Outputs_.Arg, { memoryState }, intType, 4);
      auto & loadArg = *loadArgOutputs[0];
      memoryState = loadArgOutputs[1];
 
      lambdaNode.finalize({ &loadArg, ioState, memoryState });
      Outputs_.Func = lambdaNode.output();
    }
 
    return rvsdgModule;
  }
 
  Outputs Outputs_ = {};
};
 
TEST(LocalAliasAnalysisTests, testAllocasArguments)
{
  using namespace jlm;
  using namespace jlm::llvm;
  using namespace jlm::llvm::aa;
 
  // Arrange
  LocalAliasAnalysisArgumentAllocaTest rvsdg;
  rvsdg.InitializeTest();
  const auto & outputs = rvsdg.GetOutputs();
 
  jlm::rvsdg::view(&rvsdg.graph().GetRootRegion(), stdout);
 
  LocalAliasAnalysis aa;
 
  // Assert
  Expect(aa, *outputs.Arg, 4, *outputs.LocalAlloca, 4, AliasAnalysis::NoAlias);
}