IfConversionTests.cpp

Go to the documentation of this file.

/*
 * Copyright 2025 Nico Reißmann <nico.reissmann@gmail.com>
 * See COPYING for terms of redistribution.
 */
 
#include <gtest/gtest.h>
 
#include <jlm/llvm/ir/operators/IntegerOperations.hpp>
#include <jlm/llvm/ir/operators/lambda.hpp>
#include <jlm/llvm/ir/operators/operators.hpp>
#include <jlm/llvm/ir/RvsdgModule.hpp>
#include <jlm/llvm/opt/IfConversion.hpp>
#include <jlm/rvsdg/FunctionType.hpp>
#include <jlm/rvsdg/gamma.hpp>
#include <jlm/rvsdg/lambda.hpp>
#include <jlm/rvsdg/TestOperations.hpp>
#include <jlm/rvsdg/TestType.hpp>
#include <jlm/rvsdg/view.hpp>
#include <jlm/util/Statistics.hpp>
 
TEST(IfConversionTests, GammaWithoutMatch)
{
  using namespace jlm::llvm;
  using namespace jlm::util;
 
  // Arrange
  auto valueType = jlm::rvsdg::TestType::createValueType();
  auto functionType = jlm::rvsdg::FunctionType::Create(
      { jlm::rvsdg::ControlType::Create(2), valueType, valueType },
      { valueType });
 
  LlvmRvsdgModule rvsdgModule(FilePath(""), "", "");
 
  auto lambdaNode = jlm::rvsdg::LambdaNode::Create(
      rvsdgModule.Rvsdg().GetRootRegion(),
      LlvmLambdaOperation::Create(functionType, "lambdaOutput", Linkage::externalLinkage));
  const auto conditionValue = lambdaNode->GetFunctionArguments()[0];
  const auto trueValue = lambdaNode->GetFunctionArguments()[1];
  const auto falseValue = lambdaNode->GetFunctionArguments()[2];
 
  auto gammaNode = jlm::rvsdg::GammaNode::create(conditionValue, 2);
  auto gammaInput1 = gammaNode->AddEntryVar(trueValue);
  auto gammaInput2 = gammaNode->AddEntryVar(falseValue);
  auto gammaOutput =
      gammaNode->AddExitVar({ gammaInput1.branchArgument[0], gammaInput2.branchArgument[1] });
 
  auto lambdaOutput = lambdaNode->finalize({ gammaOutput.output });
  jlm::rvsdg::GraphExport::Create(*lambdaOutput, "");
 
  jlm::rvsdg::view(rvsdgModule.Rvsdg(), stdout);
 
  // Act
  StatisticsCollector statisticsCollector;
  IfConversion ifConversion;
  ifConversion.Run(rvsdgModule, statisticsCollector);
 
  view(rvsdgModule.Rvsdg(), stdout);
 
  // Assert
 
  EXPECT_TRUE(gammaNode->IsDead());
  const auto selectNode =
      jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*lambdaNode->subregion()->result(0)->origin());
  EXPECT_TRUE(selectNode && is<SelectOperation>(selectNode));
  EXPECT_EQ(selectNode->input(1)->origin(), falseValue);
  EXPECT_EQ(selectNode->input(2)->origin(), trueValue);
 
  const auto controlToBitsNode =
      jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*selectNode->input(0)->origin());
  EXPECT_TRUE(controlToBitsNode && is<ControlToIntOperation>(controlToBitsNode));
  EXPECT_EQ(controlToBitsNode->input(0)->origin(), conditionValue);
}
 
TEST(IfConversionTests, EmptyGammaWithTwoSubregionsAndMatch)
{
  using namespace jlm::llvm;
  using namespace jlm::util;
 
  // Arrange
  auto valueType = jlm::rvsdg::TestType::createValueType();
  const auto functionType = jlm::rvsdg::FunctionType::Create(
      { jlm::rvsdg::BitType::Create(32), valueType, valueType },
      { valueType });
 
  LlvmRvsdgModule rvsdgModule(FilePath(""), "", "");
 
  const auto lambdaNode = jlm::rvsdg::LambdaNode::Create(
      rvsdgModule.Rvsdg().GetRootRegion(),
      LlvmLambdaOperation::Create(functionType, "lambdaOutput", Linkage::externalLinkage));
  const auto conditionValue = lambdaNode->GetFunctionArguments()[0];
  const auto trueValue = lambdaNode->GetFunctionArguments()[1];
  const auto falseValue = lambdaNode->GetFunctionArguments()[2];
 
  auto caseValue = 24;
  auto & matchNode =
      jlm::rvsdg::MatchOperation::CreateNode(*conditionValue, { { caseValue, 0 } }, 1, 2);
 
  const auto gammaNode = jlm::rvsdg::GammaNode::create(matchNode.output(0), 2);
  auto [inputTrue, branchArgumentTrue] = gammaNode->AddEntryVar(trueValue);
  auto [inputFalse, branchArgumentFalse] = gammaNode->AddEntryVar(falseValue);
  auto [_, gammaOutput] = gammaNode->AddExitVar({ branchArgumentTrue[0], branchArgumentFalse[1] });
 
  const auto lambdaOutput = lambdaNode->finalize({ gammaOutput });
  jlm::rvsdg::GraphExport::Create(*lambdaOutput, "");
 
  view(rvsdgModule.Rvsdg(), stdout);
 
  // Act
  StatisticsCollector statisticsCollector;
  IfConversion ifConversion;
  ifConversion.Run(rvsdgModule, statisticsCollector);
 
  view(rvsdgModule.Rvsdg(), stdout);
 
  // Assert
 
  EXPECT_TRUE(gammaNode->IsDead());
  const auto selectNode =
      jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*lambdaNode->subregion()->result(0)->origin());
  EXPECT_TRUE(selectNode && is<SelectOperation>(selectNode));
  EXPECT_EQ(selectNode->input(1)->origin(), trueValue);
  EXPECT_EQ(selectNode->input(2)->origin(), falseValue);
 
  const auto eqNode =
      jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::SimpleNode>(*selectNode->input(0)->origin());
  EXPECT_TRUE(eqNode && is<IntegerEqOperation>(eqNode));
 
  auto constantNode =
      jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::SimpleNode>(*eqNode->input(0)->origin());
  if (constantNode)
  {
    EXPECT_EQ(eqNode->input(1)->origin(), conditionValue);
    auto constantOperation =
        dynamic_cast<const IntegerConstantOperation *>(&constantNode->GetOperation());
    EXPECT_NE(constantOperation, nullptr);
    EXPECT_EQ(constantOperation->Representation(), 24);
  }
  else
  {
    EXPECT_EQ(eqNode->input(0)->origin(), conditionValue);
    constantNode = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::SimpleNode>(*eqNode->input(1)->origin());
    auto constantOperation =
        dynamic_cast<const IntegerConstantOperation *>(&constantNode->GetOperation());
    EXPECT_NE(constantOperation, nullptr);
    EXPECT_EQ(constantOperation->Representation(), 24);
  }
}
 
TEST(IfConversionTests, EmptyGammaWithTwoSubregions)
{
  using namespace jlm::llvm;
  using namespace jlm::util;
 
  // Arrange
  auto valueType = jlm::rvsdg::TestType::createValueType();
  auto functionType = jlm::rvsdg::FunctionType::Create(
      { jlm::rvsdg::BitType::Create(32), valueType, valueType },
      { valueType });
 
  LlvmRvsdgModule rvsdgModule(FilePath(""), "", "");
 
  const auto lambdaNode = jlm::rvsdg::LambdaNode::Create(
      rvsdgModule.Rvsdg().GetRootRegion(),
      LlvmLambdaOperation::Create(functionType, "lambdaOutput", Linkage::externalLinkage));
  const auto trueValue = lambdaNode->GetFunctionArguments()[1];
  const auto falseValue = lambdaNode->GetFunctionArguments()[2];
 
  auto & matchNode = jlm::rvsdg::MatchOperation::CreateNode(
      *lambdaNode->GetFunctionArguments()[0],
      { { 0, 0 } },
      1,
      2);
 
  const auto gammaNode0 = jlm::rvsdg::GammaNode::create(matchNode.output(0), 2);
  const auto & c0 = jlm::rvsdg::CreateOpNode<jlm::rvsdg::ControlConstantOperation>(
      *gammaNode0->subregion(0),
      jlm::rvsdg::ControlValueRepresentation(0, 2));
  const auto & c1 = jlm::rvsdg::CreateOpNode<jlm::rvsdg::ControlConstantOperation>(
      *gammaNode0->subregion(1),
      jlm::rvsdg::ControlValueRepresentation(1, 2));
  auto c = gammaNode0->AddExitVar({ c0.output(0), c1.output(0) });
 
  const auto gammaNode1 = jlm::rvsdg::GammaNode::create(c.output, 2);
  auto [inputTrue, branchArgumentTrue] = gammaNode1->AddEntryVar(trueValue);
  auto [inputFalse, branchArgumentFalse] = gammaNode1->AddEntryVar(falseValue);
  auto [_, gammaOutput] = gammaNode1->AddExitVar({ branchArgumentFalse[0], branchArgumentTrue[1] });
 
  const auto lambdaOutput = lambdaNode->finalize({ gammaOutput });
  jlm::rvsdg::GraphExport::Create(*lambdaOutput, "");
 
  view(rvsdgModule.Rvsdg(), stdout);
 
  // Act
  StatisticsCollector statisticsCollector;
  IfConversion ifConversion;
  ifConversion.Run(rvsdgModule, statisticsCollector);
 
  view(rvsdgModule.Rvsdg(), stdout);
 
  // Assert
  EXPECT_TRUE(gammaNode1->IsDead());
  const auto selectNode =
      jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::Node>(*lambdaNode->subregion()->result(0)->origin());
  EXPECT_TRUE(selectNode && is<SelectOperation>(selectNode));
  EXPECT_EQ(selectNode->input(1)->origin(), trueValue);
  EXPECT_EQ(selectNode->input(2)->origin(), falseValue);
}
 
TEST(IfConversionTests, EmptyGammaWithThreeSubregions)
{
  using namespace jlm::llvm;
  using namespace jlm::util;
 
  // Arrange
  auto valueType = jlm::rvsdg::TestType::createValueType();
  auto functionType = jlm::rvsdg::FunctionType::Create(
      { jlm::rvsdg::BitType::Create(32), valueType, valueType },
      { valueType });
 
  LlvmRvsdgModule rvsdgModule(FilePath(""), "", "");
 
  auto lambdaNode = jlm::rvsdg::LambdaNode::Create(
      rvsdgModule.Rvsdg().GetRootRegion(),
      LlvmLambdaOperation::Create(functionType, "lambdaOutput", Linkage::externalLinkage));
 
  auto & matchNode = jlm::rvsdg::MatchOperation::CreateNode(
      *lambdaNode->GetFunctionArguments()[0],
      { { 0, 0 }, { 1, 1 } },
      2,
      3);
 
  auto gammaNode = jlm::rvsdg::GammaNode::create(matchNode.output(0), 3);
  auto gammaInput1 = gammaNode->AddEntryVar(lambdaNode->GetFunctionArguments()[1]);
  auto gammaInput2 = gammaNode->AddEntryVar(lambdaNode->GetFunctionArguments()[2]);
  auto gammaOutput = gammaNode->AddExitVar({ gammaInput1.branchArgument[0],
                                             gammaInput1.branchArgument[1],
                                             gammaInput2.branchArgument[2] });
 
  auto lambdaOutput = lambdaNode->finalize({ gammaOutput.output });
  jlm::rvsdg::GraphExport::Create(*lambdaOutput, "");
 
  view(rvsdgModule.Rvsdg(), stdout);
 
  // Act
  StatisticsCollector statisticsCollector;
  IfConversion ifConversion;
  ifConversion.Run(rvsdgModule, statisticsCollector);
 
  view(rvsdgModule.Rvsdg(), stdout);
 
  // Assert
 
  // Only the gamma and match nodes should be in the lambda region. No select operation
  // should have been created.
  EXPECT_EQ(lambdaNode->subregion()->numNodes(), 2u);
  EXPECT_FALSE(gammaNode->IsDead());
}
 
TEST(IfConversionTests, PartialEmptyGamma)
{
  using namespace jlm::llvm;
  using namespace jlm::rvsdg;
  using namespace jlm::util;
 
  // Arrange
  auto valueType = jlm::rvsdg::TestType::createValueType();
  auto functionType = jlm::rvsdg::FunctionType::Create(
      { jlm::rvsdg::BitType::Create(1), valueType },
      { valueType });
 
  jlm::llvm::LlvmRvsdgModule rvsdgModule(FilePath(""), "", "");
 
  auto lambdaNode = jlm::rvsdg::LambdaNode::Create(
      rvsdgModule.Rvsdg().GetRootRegion(),
      LlvmLambdaOperation::Create(functionType, "lambdaOutput", Linkage::externalLinkage));
 
  auto & matchNode =
      MatchOperation::CreateNode(*lambdaNode->GetFunctionArguments()[0], { { 0, 0 } }, 1, 2);
  auto gammaNode = GammaNode::create(matchNode.output(0), 2);
  auto gammaInput = gammaNode->AddEntryVar(lambdaNode->GetFunctionArguments()[1]);
  auto output = TestOperation::createNode(
                    gammaNode->subregion(1),
                    { gammaInput.branchArgument[1] },
                    { valueType })
                    ->output(0);
  auto gammaOutput = gammaNode->AddExitVar({ gammaInput.branchArgument[0], output });
 
  auto lambdaOutput = lambdaNode->finalize({ gammaOutput.output });
 
  jlm::rvsdg::GraphExport::Create(*lambdaOutput, "");
 
  view(rvsdgModule.Rvsdg(), stdout);
 
  // Act
  StatisticsCollector statisticsCollector;
  IfConversion ifConversion;
  ifConversion.Run(rvsdgModule, statisticsCollector);
 
  view(rvsdgModule.Rvsdg(), stdout);
 
  // Assert
 
  // Only the gamma and match nodes should be in the lambda region. No select operation
  // should have been created.
  EXPECT_EQ(lambdaNode->subregion()->numNodes(), 2u);
  EXPECT_FALSE(gammaNode->IsDead());
}
 
TEST(IfConversionTests, GammaWithMatchAlternativeMismatch)
{
  using namespace jlm::llvm;
  using namespace jlm::util;
 
  // Arrange
  auto valueType = jlm::rvsdg::TestType::createValueType();
  const auto functionType = jlm::rvsdg::FunctionType::Create(
      { jlm::rvsdg::BitType::Create(32), valueType, valueType },
      { valueType });
 
  LlvmRvsdgModule rvsdgModule(FilePath(""), "", "");
 
  const auto lambdaNode = jlm::rvsdg::LambdaNode::Create(
      rvsdgModule.Rvsdg().GetRootRegion(),
      LlvmLambdaOperation::Create(functionType, "lambdaOutput", Linkage::externalLinkage));
  const auto conditionValue = lambdaNode->GetFunctionArguments()[0];
  const auto trueValue = lambdaNode->GetFunctionArguments()[1];
  const auto falseValue = lambdaNode->GetFunctionArguments()[2];
 
  auto & matchNode = jlm::rvsdg::MatchOperation::CreateNode(
      *conditionValue,
      { { 24, 0 }, { 3, 0 }, { 45, 0 } },
      1,
      2);
 
  const auto gammaNode = jlm::rvsdg::GammaNode::create(matchNode.output(0), 2);
  auto [inputTrue, branchArgumentTrue] = gammaNode->AddEntryVar(trueValue);
  auto [inputFalse, branchArgumentFalse] = gammaNode->AddEntryVar(falseValue);
  auto [_, gammaOutput] = gammaNode->AddExitVar({ branchArgumentTrue[0], branchArgumentFalse[1] });
 
  const auto lambdaOutput = lambdaNode->finalize({ gammaOutput });
  jlm::rvsdg::GraphExport::Create(*lambdaOutput, "");
 
  view(rvsdgModule.Rvsdg(), stdout);
 
  // Act
  StatisticsCollector statisticsCollector;
  IfConversion ifConversion;
  ifConversion.Run(rvsdgModule, statisticsCollector);
 
  view(rvsdgModule.Rvsdg(), stdout);
 
  // Assert
 
  // Only the gamma and match nodes should be in the lambda region. No select operation
  // should have been created.
  EXPECT_EQ(lambdaNode->subregion()->numNodes(), 2u);
  EXPECT_FALSE(gammaNode->IsDead());
}