InliningTests.cpp

Go to the documentation of this file.

/*
 * Copyright 2017 Nico Reißmann <nico.reissmann@gmail.com>
 * Copyright 2025 Håvard Krogstie <krogstie.havard@gmail.com>
 * See COPYING for terms of redistribution.
 */
 
#include <gtest/gtest.h>
 
#include <jlm/llvm/ir/operators/alloca.hpp>
#include <jlm/llvm/ir/operators/call.hpp>
#include <jlm/llvm/ir/operators/ConversionOperations.hpp>
#include <jlm/llvm/ir/operators/delta.hpp>
#include <jlm/llvm/ir/operators/IntegerOperations.hpp>
#include <jlm/llvm/ir/operators/IOBarrier.hpp>
#include <jlm/llvm/ir/operators/lambda.hpp>
#include <jlm/llvm/ir/operators/Load.hpp>
#include <jlm/llvm/ir/operators/Store.hpp>
#include <jlm/llvm/ir/RvsdgModule.hpp>
#include <jlm/llvm/opt/inlining.hpp>
#include <jlm/rvsdg/control.hpp>
#include <jlm/rvsdg/delta.hpp>
#include <jlm/rvsdg/gamma.hpp>
#include <jlm/rvsdg/TestOperations.hpp>
#include <jlm/rvsdg/TestType.hpp>
#include <jlm/rvsdg/theta.hpp>
#include <jlm/rvsdg/view.hpp>
#include <jlm/util/Statistics.hpp>
 
static std::unique_ptr<jlm::util::Statistics>
runInlining(jlm::llvm::LlvmRvsdgModule & rm)
{
  jlm::llvm::FunctionInlining fctinline;
  jlm::util::StatisticsCollectorSettings settings({ jlm::util::Statistics::Id::FunctionInlining });
  jlm::util::StatisticsCollector collector(settings);
  fctinline.Run(rm, collector);
 
  EXPECT_EQ(collector.NumCollectedStatistics(), 1u);
  return collector.releaseStatistic(jlm::util::Statistics::Id::FunctionInlining);
}
 
TEST(FunctionInliningTests, testSimpleInlining)
{
  using namespace jlm::llvm;
  using namespace jlm::rvsdg;
 
  // Arrange
  jlm::llvm::LlvmRvsdgModule rm(jlm::util::FilePath(""), "", "");
  auto & graph = rm.Rvsdg();
  auto vt = TestType::createValueType();
  auto iOStateType = IOStateType::Create();
  auto memoryStateType = MemoryStateType::Create();
  auto i = &jlm::rvsdg::GraphImport::Create(graph, vt, "i");
 
  Region * gammaRegion0 = nullptr;
 
  auto SetupF1 = [&]()
  {
    auto functionType = jlm::rvsdg::FunctionType::Create(
        { vt, IOStateType::Create(), MemoryStateType::Create() },
        { vt, IOStateType::Create(), MemoryStateType::Create() });
 
    auto lambda = jlm::rvsdg::LambdaNode::Create(
        graph.GetRootRegion(),
        LlvmLambdaOperation::Create(functionType, "f1", Linkage::externalLinkage));
    lambda->AddContextVar(*i);
 
    auto t = TestOperation::createNode(
        lambda->subregion(),
        { lambda->GetFunctionArguments()[0] },
        { vt });
 
    return lambda->finalize(
        { t->output(0), lambda->GetFunctionArguments()[1], lambda->GetFunctionArguments()[2] });
  };
 
  auto SetupF2 = [&](jlm::rvsdg::Output * f1)
  {
    auto ct = jlm::rvsdg::ControlType::Create(2);
    auto functionType = jlm::rvsdg::FunctionType::Create(
        { jlm::rvsdg::ControlType::Create(2),
          vt,
          IOStateType::Create(),
          MemoryStateType::Create() },
        { vt, IOStateType::Create(), MemoryStateType::Create() });
 
    auto lambda = jlm::rvsdg::LambdaNode::Create(
        graph.GetRootRegion(),
        LlvmLambdaOperation::Create(functionType, "f2", Linkage::externalLinkage));
    auto d = lambda->AddContextVar(*f1).inner;
    auto controlArgument = lambda->GetFunctionArguments()[0];
    auto valueArgument = lambda->GetFunctionArguments()[1];
    auto iOStateArgument = lambda->GetFunctionArguments()[2];
    auto memoryStateArgument = lambda->GetFunctionArguments()[3];
 
    auto gamma = jlm::rvsdg::GammaNode::create(controlArgument, 2);
    gammaRegion0 = gamma->subregion(0);
    auto gammaInputF1 = gamma->AddEntryVar(d);
    auto gammaInputValue = gamma->AddEntryVar(valueArgument);
    auto gammaInputIoState = gamma->AddEntryVar(iOStateArgument);
    auto gammaInputMemoryState = gamma->AddEntryVar(memoryStateArgument);
 
    auto callResults = CallOperation::Create(
        gammaInputF1.branchArgument[0],
        jlm::rvsdg::AssertGetOwnerNode<jlm::rvsdg::LambdaNode>(*f1).GetOperation().Type(),
        { gammaInputValue.branchArgument[0],
          gammaInputIoState.branchArgument[0],
          gammaInputMemoryState.branchArgument[0] });
 
    auto gammaOutputValue =
        gamma->AddExitVar({ callResults[0], gammaInputValue.branchArgument[1] });
    auto gammaOutputIoState =
        gamma->AddExitVar({ callResults[1], gammaInputIoState.branchArgument[1] });
    auto gammaOutputMemoryState =
        gamma->AddExitVar({ callResults[2], gammaInputMemoryState.branchArgument[1] });
 
    return lambda->finalize(
        { gammaOutputValue.output, gammaOutputIoState.output, gammaOutputMemoryState.output });
  };
 
  auto f1 = SetupF1();
  auto f2 = SetupF2(f1);
 
  GraphExport::Create(*f2, "f2");
 
  //    jlm::rvsdg::view(graph.GetRootRegion(), stdout);
 
  // Act
  auto statistics = runInlining(rm);
 
  //    jlm::rvsdg::view(graph.GetRootRegion(), stdout);
 
  // Assert
  // Check that the call has been replaced by the test operation inside f1
  EXPECT_FALSE(Region::containsOperation<CallOperation>(graph.GetRootRegion(), true));
  EXPECT_TRUE(Region::containsOperation<TestOperation>(*gammaRegion0, true));
 
  // Check that the statistics match what we expect. f2 is technically inlineable
  EXPECT_EQ(statistics->GetMeasurementValue<uint64_t>("#Functions"), 2u);
  EXPECT_EQ(statistics->GetMeasurementValue<uint64_t>("#InlineableFunctions"), 2u);
  EXPECT_EQ(statistics->GetMeasurementValue<uint64_t>("#FunctionCalls"), 1u);
  EXPECT_EQ(statistics->GetMeasurementValue<uint64_t>("#InlinableCalls"), 1u);
  EXPECT_EQ(statistics->GetMeasurementValue<uint64_t>("#CallsInlined"), 1u);
}
 
TEST(FunctionInliningTests, testInliningWithAlloca)
{
  using namespace jlm::llvm;
  using namespace jlm::rvsdg;
 
  // Arrange
  jlm::llvm::LlvmRvsdgModule rm(jlm::util::FilePath(""), "", "");
  auto & graph = rm.Rvsdg();
  auto vt = TestType::createValueType();
  auto iOStateType = IOStateType::Create();
  auto memoryStateType = MemoryStateType::Create();
  auto i = &jlm::rvsdg::GraphImport::Create(graph, vt, "i");
 
  Region * gammaRegion0 = nullptr;
  Region * f2Region = nullptr;
 
  auto SetupF1 = [&]()
  {
    auto functionType = jlm::rvsdg::FunctionType::Create(
        { vt, IOStateType::Create(), MemoryStateType::Create() },
        { IOStateType::Create(), MemoryStateType::Create() });
 
    auto lambda = jlm::rvsdg::LambdaNode::Create(
        graph.GetRootRegion(),
        LlvmLambdaOperation::Create(functionType, "f1", Linkage::externalLinkage));
    lambda->AddContextVar(*i);
    auto lambdaArgs = lambda->GetFunctionArguments();
 
    const auto & one = IntegerConstantOperation::Create(*lambda->subregion(), 32, 1);
    auto alloca = AllocaOperation::create(vt, one.output(0), 4);
    auto store = StoreNonVolatileOperation::Create(alloca[0], lambdaArgs[0], { lambdaArgs[2] }, 4);
 
    return lambda->finalize({ lambdaArgs[1], store[0] });
  };
 
  auto SetupF2 = [&](jlm::rvsdg::Output * f1)
  {
    auto ct = jlm::rvsdg::ControlType::Create(2);
    auto functionType = jlm::rvsdg::FunctionType::Create(
        { jlm::rvsdg::ControlType::Create(2),
          vt,
          IOStateType::Create(),
          MemoryStateType::Create() },
        { IOStateType::Create(), MemoryStateType::Create() });
 
    auto lambda = jlm::rvsdg::LambdaNode::Create(
        graph.GetRootRegion(),
        LlvmLambdaOperation::Create(functionType, "f2", Linkage::externalLinkage));
    auto d = lambda->AddContextVar(*f1).inner;
    auto controlArgument = lambda->GetFunctionArguments()[0];
    auto valueArgument = lambda->GetFunctionArguments()[1];
    auto iOStateArgument = lambda->GetFunctionArguments()[2];
    auto memoryStateArgument = lambda->GetFunctionArguments()[3];
    f2Region = lambda->subregion();
 
    auto gamma = jlm::rvsdg::GammaNode::create(controlArgument, 2);
    gammaRegion0 = gamma->subregion(0);
    auto gammaInputF1 = gamma->AddEntryVar(d);
    auto gammaInputValue = gamma->AddEntryVar(valueArgument);
    auto gammaInputIoState = gamma->AddEntryVar(iOStateArgument);
    auto gammaInputMemoryState = gamma->AddEntryVar(memoryStateArgument);
 
    auto callResults = CallOperation::Create(
        gammaInputF1.branchArgument[0],
        jlm::rvsdg::AssertGetOwnerNode<jlm::rvsdg::LambdaNode>(*f1).GetOperation().Type(),
        { gammaInputValue.branchArgument[0],
          gammaInputIoState.branchArgument[0],
          gammaInputMemoryState.branchArgument[0] });
 
    auto gammaOutputIoState =
        gamma->AddExitVar({ callResults[0], gammaInputIoState.branchArgument[1] });
    auto gammaOutputMemoryState =
        gamma->AddExitVar({ callResults[1], gammaInputMemoryState.branchArgument[1] });
 
    return lambda->finalize({ gammaOutputIoState.output, gammaOutputMemoryState.output });
  };
 
  auto f1 = SetupF1();
  auto f2 = SetupF2(f1);
 
  GraphExport::Create(*f2, "f2");
 
  // jlm::rvsdg::view(graph.GetRootRegion(), stdout);
 
  // Act
  runInlining(rm);
 
  // jlm::rvsdg::view(&graph.GetRootRegion(), stdout);
 
  // Assert
  // Check that the call is gone
  EXPECT_FALSE(Region::containsOperation<CallOperation>(graph.GetRootRegion(), true));
  // A store should have taken its place in the gamma subregion
  EXPECT_TRUE(Region::containsOperation<StoreNonVolatileOperation>(*gammaRegion0, true));
  // Check that the alloca operation is not inside the gamma subregion
  EXPECT_FALSE(Region::containsOperation<AllocaOperation>(*gammaRegion0, true));
  // The alloca should have been moved to the top level of f2
  EXPECT_TRUE(Region::containsOperation<AllocaOperation>(*f2Region, false));
}
 
TEST(FunctionInliningTests, testIndirectCall)
{
  using namespace jlm::llvm;
  using namespace jlm::rvsdg;
 
  // Arrange
  auto vt = TestType::createValueType();
  auto iOStateType = IOStateType::Create();
  auto memoryStateType = MemoryStateType::Create();
 
  auto functionType1 = jlm::rvsdg::FunctionType::Create(
      { vt, IOStateType::Create(), MemoryStateType::Create() },
      { IOStateType::Create(), MemoryStateType::Create() });
  auto pt = PointerType::Create();
 
  auto functionType2 = jlm::rvsdg::FunctionType::Create(
      { PointerType::Create(), IOStateType::Create(), MemoryStateType::Create() },
      { IOStateType::Create(), MemoryStateType::Create() });
 
  jlm::llvm::LlvmRvsdgModule rm(jlm::util::FilePath(""), "", "");
  auto & graph = rm.Rvsdg();
  auto i = &jlm::rvsdg::GraphImport::Create(graph, functionType2, "i");
 
  auto SetupF1 = [&](const std::shared_ptr<const jlm::rvsdg::FunctionType> & functionType)
  {
    auto lambda = jlm::rvsdg::LambdaNode::Create(
        graph.GetRootRegion(),
        LlvmLambdaOperation::Create(functionType, "f1", Linkage::externalLinkage));
    return lambda->finalize(
        { lambda->GetFunctionArguments()[1], lambda->GetFunctionArguments()[2] });
  };
 
  auto SetupF2 = [&](jlm::rvsdg::Output * f1)
  {
    auto functionType = jlm::rvsdg::FunctionType::Create(
        { IOStateType::Create(), MemoryStateType::Create() },
        { IOStateType::Create(), MemoryStateType::Create() });
 
    auto lambda = jlm::rvsdg::LambdaNode::Create(
        graph.GetRootRegion(),
        LlvmLambdaOperation::Create(functionType, "f2", Linkage::externalLinkage));
    auto cvi = lambda->AddContextVar(*i).inner;
    auto cvf1 = lambda->AddContextVar(*f1).inner;
    auto iOStateArgument = lambda->GetFunctionArguments()[0];
    auto memoryStateArgument = lambda->GetFunctionArguments()[1];
 
    auto callResults =
        CallOperation::Create(cvi, functionType2, { cvf1, iOStateArgument, memoryStateArgument });
 
    return lambda->finalize(callResults);
  };
 
  auto f1 = SetupF1(functionType1);
  auto f2 = SetupF2(
      jlm::rvsdg::CreateOpNode<FunctionToPointerOperation>({ f1 }, functionType1).output(0));
 
  GraphExport::Create(*f2, "f2");
 
  // jlm::rvsdg::view(&graph.GetRootRegion(), stdout);
 
  // Act
  auto statistics = runInlining(rm);
 
  // jlm::rvsdg::view(&graph.GetRootRegion(), stdout);
 
  // Assert
  // No inlining happens in this test, but both f1 and f2 are technically possible to inline
  EXPECT_EQ(statistics->GetMeasurementValue<uint64_t>("#Functions"), 2u);
  EXPECT_EQ(statistics->GetMeasurementValue<uint64_t>("#InlineableFunctions"), 2u);
  EXPECT_EQ(statistics->GetMeasurementValue<uint64_t>("#FunctionCalls"), 1u);
  EXPECT_EQ(statistics->GetMeasurementValue<uint64_t>("#InlinableCalls"), 0u);
  EXPECT_EQ(statistics->GetMeasurementValue<uint64_t>("#CallsInlined"), 0u);
}
 
TEST(FunctionInliningTests, testFunctionWithDisqualifyingAlloca)
{
  using namespace jlm::llvm;
  using namespace jlm::rvsdg;
 
  // Arrange
  auto vt = TestType::createValueType();
  auto iOStateType = IOStateType::Create();
  auto memoryStateType = MemoryStateType::Create();
 
  jlm::llvm::LlvmRvsdgModule rm(jlm::util::FilePath(""), "", "");
  auto & graph = rm.Rvsdg();
 
  auto SetupF1 = [&]()
  {
    auto functionType = FunctionType::Create(
        { IOStateType::Create(), MemoryStateType::Create() },
        { IOStateType::Create(), MemoryStateType::Create() });
 
    auto lambda = jlm::rvsdg::LambdaNode::Create(
        graph.GetRootRegion(),
        LlvmLambdaOperation::Create(functionType, "f1", Linkage::externalLinkage));
    auto theta = ThetaNode::create(lambda->subregion());
 
    const auto & one = IntegerConstantOperation::Create(*theta->subregion(), 32, 1);
    AllocaOperation::create(vt, one.output(0), 4);
 
    return lambda->finalize(
        { lambda->GetFunctionArguments()[0], lambda->GetFunctionArguments()[1] });
  };
  SetupF1();
 
  // Act
  auto statistics = runInlining(rm);
 
  // Assert
  EXPECT_EQ(statistics->GetMeasurementValue<uint64_t>("#Functions"), 1u);
  // f1 should not be considered inlinable, due to the alloca
  EXPECT_EQ(statistics->GetMeasurementValue<uint64_t>("#InlineableFunctions"), 0u);
}
 
TEST(FunctionInliningTests, testIOBarrierInsertion)
{
  using namespace jlm::llvm;
  using namespace jlm::rvsdg;
 
  // Arrange
  LlvmRvsdgModule rvsdgModule(jlm::util::FilePath(""), "", "");
  auto & graph = rvsdgModule.Rvsdg();
 
  auto vt = TestType::createValueType();
  auto i32Type = BitType::Create(32);
  auto pointerType = PointerType::Create();
  auto iOStateType = IOStateType::Create();
  auto memoryStateType = MemoryStateType::Create();
 
  auto SetupD1 = [&]()
  {
    auto deltaNode = DeltaNode::Create(
        &graph.GetRootRegion(),
        LlvmDeltaOperation::Create(i32Type, "delta", Linkage::externalLinkage, "", true, 4));
    auto & constant = IntegerConstantOperation::Create(*deltaNode->subregion(), 32, 4);
    deltaNode->finalize(constant.output(0));
    return deltaNode;
  };
 
  auto SetupF1 = [&](Output * d1)
  {
    auto functionType = FunctionType::Create(
        { pointerType, IOStateType::Create(), MemoryStateType::Create() },
        { i32Type, i32Type, IOStateType::Create(), MemoryStateType::Create() });
 
    auto lambda = LambdaNode::Create(
        graph.GetRootRegion(),
        LlvmLambdaOperation::Create(functionType, "f1", Linkage::externalLinkage));
    auto ctxVar = lambda->AddContextVar(*d1);
    auto ptrArgument = lambda->GetFunctionArguments()[0];
    auto ioStateArgument = lambda->GetFunctionArguments()[1];
    auto memoryStateArgument = lambda->GetFunctionArguments()[2];
 
    auto & loadNode1 =
        LoadNonVolatileOperation::CreateNode(*ptrArgument, { memoryStateArgument }, i32Type, 4);
 
    auto & loadNode2 =
        LoadNonVolatileOperation::CreateNode(*ctxVar.inner, { loadNode1.output(1) }, i32Type, 4);
 
    return lambda->finalize(
        { loadNode1.output(0), loadNode2.output(0), ioStateArgument, loadNode2.output(1) });
  };
 
  auto SetupF2 = [&](Output * f1)
  {
    auto ct = ControlType::Create(2);
    auto functionType = FunctionType::Create(
        { pointerType, IOStateType::Create(), MemoryStateType::Create() },
        { i32Type, i32Type, IOStateType::Create(), MemoryStateType::Create() });
 
    auto lambda = LambdaNode::Create(
        graph.GetRootRegion(),
        LlvmLambdaOperation::Create(functionType, "f2", Linkage::externalLinkage));
    auto ctxVar = lambda->AddContextVar(*f1);
    auto ptrArgument = lambda->GetFunctionArguments()[0];
    auto iOStateArgument = lambda->GetFunctionArguments()[1];
    auto memoryStateArgument = lambda->GetFunctionArguments()[2];
 
    auto callResults = CallOperation::Create(
        ctxVar.inner,
        jlm::rvsdg::AssertGetOwnerNode<LambdaNode>(*f1).GetOperation().Type(),
        { ptrArgument, iOStateArgument, memoryStateArgument });
 
    lambda->finalize({ callResults[0], callResults[1], callResults[2], callResults[3] });
    return lambda;
  };
 
  auto d1 = SetupD1();
  auto f1 = SetupF1(&d1->output());
  auto f2 = SetupF2(f1);
 
  GraphExport::Create(*f2->output(), "f2");
 
  // Act
  auto statistics = runInlining(rvsdgModule);
 
  // Assert
  // Check that the call has been replaced by the test operation inside f1
  EXPECT_FALSE(Region::containsOperation<CallOperation>(graph.GetRootRegion(), true));
 
  // We expect a two load and IOBarrier nodes
  EXPECT_EQ(f2->subregion()->numNodes(), 4);
 
  {
    auto [loadNode, loadOp] = TryGetSimpleNodeAndOptionalOp<LoadNonVolatileOperation>(
        *f2->GetFunctionResults()[0]->origin());
    EXPECT_NE(loadOp, nullptr);
 
    auto [ioBarrierNode, ioBarrierOp] = TryGetSimpleNodeAndOptionalOp<IOBarrierOperation>(
        *LoadOperation::AddressInput(*loadNode).origin());
    EXPECT_NE(ioBarrierOp, nullptr);
    EXPECT_EQ(ioBarrierNode->input(1)->origin(), f2->GetFunctionArguments()[1]);
  }
 
  {
    auto [loadNode, loadOp] = TryGetSimpleNodeAndOptionalOp<LoadNonVolatileOperation>(
        *f2->GetFunctionResults()[1]->origin());
    EXPECT_NE(loadOp, nullptr);
 
    auto [ioBarrierNode, ioBarrierOp] = TryGetSimpleNodeAndOptionalOp<IOBarrierOperation>(
        *LoadOperation::AddressInput(*loadNode).origin());
    EXPECT_NE(ioBarrierOp, nullptr);
    EXPECT_EQ(ioBarrierNode->input(1)->origin(), f2->GetFunctionArguments()[1]);
  }
}