CommonNodeEliminationTests.cpp File Reference

#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/CommonNodeElimination.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/Phi.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>

Include dependency graph for CommonNodeEliminationTests.cpp:

Go to the source code of this file.

Functions
	TEST (CommonNodeEliminationTests, test_simple)
	TEST (CommonNodeEliminationTests, test_gamma)
	TEST (CommonNodeEliminationTests, test_gamma_congruent_exit_vars)
	TEST (CommonNodeEliminationTests, test_theta)
	TEST (CommonNodeEliminationTests, test_theta2)
	TEST (CommonNodeEliminationTests, test_theta3)
	TEST (CommonNodeEliminationTests, test_theta4)
	TEST (CommonNodeEliminationTests, test_theta5)
	TEST (CommonNodeEliminationTests, MultipleThetas)
	TEST (CommonNodeEliminationTests, MultipleThetasPassthrough)
	TEST (CommonNodeEliminationTests, test_lambda)
	TEST (CommonNodeEliminationTests, test_phi)
	TEST (CommonNodeEliminationTests, EmptyTheta)
	TEST (CommonNodeEliminationTests, GammaInTheta)
	TEST (CommonNodeEliminationTests, InvariantThetaInTheta)
	TEST (CommonNodeEliminationTests, InvariantLoopOutputs)

Variables
static jlm::util::StatisticsCollector	statisticsCollector

Function Documentation

TEST() [1/16]

TEST	(	CommonNodeEliminationTests	,
		EmptyTheta
	)

Definition at line 641 of file CommonNodeEliminationTests.cpp.

TEST() [2/16]

TEST	(	CommonNodeEliminationTests	,
		GammaInTheta
	)

Creates a graph with a gamma node inside a theta node, that looks like:

         10
         /\
        V  V

+-----------------—+ | CTRL(0) | | | | V V V | | +----—+----—+ | | | \ | / | | | | V | V | | | +----—+----—+ | | V |

USER1
CTRL(0) 6 7
V V V

+-----------------—+

After performing CNE, the USER1 should still take its value from the gamma node, and not be re-routed to one of the loop variables, despite the loop variables appearing congruent in the first iteration.

Definition at line 682 of file CommonNodeEliminationTests.cpp.

TEST() [3/16]

TEST	(	CommonNodeEliminationTests	,
		InvariantLoopOutputs
	)

Creates RVSDG that looks like

   undef   0   undef
      |    |    |
      v    v    v

+-theta------------------—+ | v v v | | CTR(0) |-----—\ | | v v | | | +-gamma—+-----—+ | | | | v | v | | | | | | | | | | | | | v | v | | | | +------—+-----—+ | | | v | | | /| /-—/ | | /-/ | | | | CTR(0) / | | | | v v v v | +------------------------—+ v v v export(x) | export(z) v export(y)

After running CNE, the exports "x", "y" and "z" should all take their value directly from the constant 0.

Definition at line 855 of file CommonNodeEliminationTests.cpp.

TEST() [4/16]

TEST	(	CommonNodeEliminationTests	,
		InvariantThetaInTheta
	)

Creates an RVSDG graph corresponding to the C code:

int f() {
  int x = 0;
  int y = 0;
  do {
    int z = 5;
    do {
      // z and y are routed through this inner loop
    } while(0);
 
    x += 1;
    y += 2;
  } while(y < 10);
 
  return y;
}

The RVSDG looks like this:

zero := IntegerConstant(0) xOut0, yOut0 = theta zero, zero [xPre0, yPre0] { five = IntegerConstant(5); zOut1, yOut1 = theta five, yPre0 [zPre1, yPre1] { predicate1 = CTRL(0) } [predicate1, zPre1, yPre1]

one = IntegerConstant(1) xPlus1 = IntegerAdd xPre0, one

two = IntegerConstant(2) yPlus2 = IntegerAdd yOut1, two

ten = IntegerConstant(10) slt = signedLessThan xPlus1, ten predicate0 = MATCH[1->1, 0] slt }[predicate0, xPlus1, yPlus2]

The test performs common node elimination on the code, which should route value of y around the inner theta, without mixing up x and y in the outer theta.

Definition at line 747 of file CommonNodeEliminationTests.cpp.

TEST() [5/16]

TEST	(	CommonNodeEliminationTests	,
		MultipleThetas
	)

Definition at line 457 of file CommonNodeEliminationTests.cpp.

TEST() [6/16]

TEST	(	CommonNodeEliminationTests	,
		MultipleThetasPassthrough
	)

Definition at line 508 of file CommonNodeEliminationTests.cpp.

TEST() [7/16]

TEST	(	CommonNodeEliminationTests	,
		test_gamma
	)

Definition at line 68 of file CommonNodeEliminationTests.cpp.

TEST() [8/16]

TEST	(	CommonNodeEliminationTests	,
		test_gamma_congruent_exit_vars
	)

Creates an RVSDG graph that looks like c := GraphImport("c") // ControlType(2) a := GraphImport("a") // ValueType b := GraphImport("b") // ValueType a2, b2, x, y, z := gamma c, a, b [_, a0 <- a, b0 <- b] { } [a0 -> a2, b0 -> b2, a0 -> x, a0 -> y, b0 -> z] [_, a1 <- a, b1 <- b] { } [a1 -> a2, b1 -> b2, b1 -> x, b1 -> y, a1 -> z] GraphExport(a2) GraphExport(b2) GraphExport(x) GraphExport(y) GraphExport(z)

and checks the result of running CommonNodeElimination.

The exports of a2 and b2 should be redirected directly to the respective imports, while x and y should be merged into a single output. The z graph export should be left alone, as it is unique and non-invariant.

Definition at line 132 of file CommonNodeEliminationTests.cpp.

TEST() [9/16]

TEST	(	CommonNodeEliminationTests	,
		test_lambda
	)

Definition at line 554 of file CommonNodeEliminationTests.cpp.

TEST() [10/16]

TEST	(	CommonNodeEliminationTests	,
		test_phi
	)

Definition at line 589 of file CommonNodeEliminationTests.cpp.

TEST() [11/16]

TEST	(	CommonNodeEliminationTests	,
		test_simple
	)

Definition at line 26 of file CommonNodeEliminationTests.cpp.

TEST() [12/16]

TEST	(	CommonNodeEliminationTests	,
		test_theta
	)

Definition at line 210 of file CommonNodeEliminationTests.cpp.

TEST() [13/16]

TEST	(	CommonNodeEliminationTests	,
		test_theta2
	)

Definition at line 261 of file CommonNodeEliminationTests.cpp.

TEST() [14/16]

TEST	(	CommonNodeEliminationTests	,
		test_theta3
	)

Definition at line 304 of file CommonNodeEliminationTests.cpp.

TEST() [15/16]

TEST	(	CommonNodeEliminationTests	,
		test_theta4
	)

Definition at line 361 of file CommonNodeEliminationTests.cpp.

TEST() [16/16]

TEST	(	CommonNodeEliminationTests	,
		test_theta5
	)

Definition at line 413 of file CommonNodeEliminationTests.cpp.

Variable Documentation

statisticsCollector

jlm::util::StatisticsCollector statisticsCollector

static

Definition at line 24 of file CommonNodeEliminationTests.cpp.