StoreValueForwardingTests.cpp File Reference

#include <gtest/gtest.h>
#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/operators.hpp>
#include <jlm/llvm/ir/operators/Store.hpp>
#include <jlm/llvm/ir/RvsdgModule.hpp>
#include <jlm/llvm/ir/Trace.hpp>
#include <jlm/llvm/opt/StoreValueForwarding.hpp>
#include <jlm/rvsdg/control.hpp>
#include <jlm/rvsdg/delta.hpp>
#include <jlm/rvsdg/gamma.hpp>
#include <jlm/rvsdg/node.hpp>
#include <jlm/rvsdg/region.hpp>
#include <jlm/rvsdg/simple-node.hpp>
#include <jlm/rvsdg/TestType.hpp>
#include <jlm/rvsdg/theta.hpp>
#include <jlm/rvsdg/UnitType.hpp>
#include <jlm/rvsdg/view.hpp>
#include <jlm/util/Statistics.hpp>
#include <llvm/ADT/APFloat.h>
#include <llvm/IR/Constants.h>

Include dependency graph for StoreValueForwardingTests.cpp:

Go to the source code of this file.

Functions
static void	RunStoreValueForwarding (jlm::llvm::LlvmRvsdgModule &rvsdgModule)
	TEST (StoreValueForwardingTests, NestedAllocas)
	TEST (StoreValueForwardingTests, GetElementPointerOffsets)
	TEST (StoreValueForwardingTests, RoutingIn)
	TEST (StoreValueForwardingTests, RouteOut)
	TEST (StoreValueForwardingTests, RouteAroundLoadLoop)
	TEST (StoreValueForwardingTests, RouteUninitialized)
	TEST (StoreValueForwardingTests, GepInLoop)
	TEST (StoreValueForwardingTests, LoadForwarding)
	TEST (StoreValueForwardingTests, LoadForwardingIntoTheta)
	TEST (StoreValueForwardingTests, LoadForwardingFromDeltaWithIntegerConstant)
	TEST (StoreValueForwardingTests, LoadForwardingFromDeltaWithAggregateZeroConstant)
	TEST (StoreValueForwardingTests, LoadForwardingFromDeltaCtxVar)
	TEST (StoreValueForwardingTests, LoadForwardingFromDeltaWithConstantFP)
	TEST (StoreValueForwardingTests, LoadForwardingFromDeltaWithConstantPointerNull)
	TEST (StoreValueForwardingTests, LoadForwardingFromDeltaWithConstantDataArray)
	TEST (StoreValueForwardingTests, RegionPredicatedValueForwarding)
	TEST (StoreValueForwardingTests, LoadForwardingFromLoopExiting)
	TEST (StoreValueForwardingTests, LoadForwardingFromDeltaWithConstantStruct)
	TEST (StoreValueForwardingTests, LoadForwardingFromDeltaWithConstantArray)
	TEST (StoreValueForwardingTests, LoadForwardingFromDeltaWithIntToPtr)
	TEST (StoreValueForwardingTests, LoadForwardingFromDeltaWithConstantGep)

Function Documentation

RunStoreValueForwarding()

static void RunStoreValueForwarding ( jlm::llvm::LlvmRvsdgModule &  rvsdgModule )

static

Definition at line 34 of file StoreValueForwardingTests.cpp.

TEST() [1/21]

TEST	(	StoreValueForwardingTests	,
		GepInLoop
	)

Checks that StoreValueForwarding handles GetElementPointer operations, and is able to distinguish between different offsets into the same memory region.

Creates a function that looks like int func() { int a[4]; // Alloca of type int[4]

int* a2 = &a[2]; int* a3 = &a[3]; *a2 = 20; *a3 = 30;

do { int loaded = a2; int a1 = &a[1]; int* a22 = &a1[1]; *a22 = loaded + 1; *a1 = 10; } while(0);

return *a2 + *a3; }

After StoreValueForwarding, all loads should be removed, and the load of a3 should not go via the theta node at all.

Definition at line 716 of file StoreValueForwardingTests.cpp.

TEST() [2/21]

TEST	(	StoreValueForwardingTests	,
		GetElementPointerOffsets
	)

Create a function that looks like int func(io0, mem0) { a, memA0 = ALLOCA[bits32], 2 memA1 = STORE[bits32] a, 40, memA0 b = GetElementPointer a, bits32[1] memA2 = STORE[bits32] b, 20, memA1 l1, memA3 = LOAD[bits64] a , memA2 l2, memA4 = LOAD[bits32] a , memA3 c = GetElementPointer[byte] a, 4 l3, memA5 = LOAD[bits32] c, memA4 return l1, l2, l3, io0, mem0 }

After StoreValueForwarding, the LOAD of l2 and l3 should be gone, and be replaced by constant values 40 and 20, respectively

Definition at line 151 of file StoreValueForwardingTests.cpp.

TEST() [3/21]

TEST	(	StoreValueForwardingTests	,
		LoadForwarding
	)

Creates an RVSDG that looks like

lambda [p:ptr, io, mem0] { l1, mem1 = load[uint32] p, mem0 l2, mem2 = load[uint32] p, mem1 add0 = add l1, l2 } [add0, io, mem2]

and validates that only one load remains after running StoreValueForwarding.

Definition at line 872 of file StoreValueForwardingTests.cpp.

TEST() [4/21]

TEST	(	StoreValueForwardingTests	,
		LoadForwardingFromDeltaCtxVar
	)

Definition at line 1235 of file StoreValueForwardingTests.cpp.

TEST() [5/21]

TEST	(	StoreValueForwardingTests	,
		LoadForwardingFromDeltaWithAggregateZeroConstant
	)

Definition at line 1110 of file StoreValueForwardingTests.cpp.

TEST() [6/21]

TEST	(	StoreValueForwardingTests	,
		LoadForwardingFromDeltaWithConstantArray
	)

Definition at line 2006 of file StoreValueForwardingTests.cpp.

TEST() [7/21]

TEST	(	StoreValueForwardingTests	,
		LoadForwardingFromDeltaWithConstantDataArray
	)

Definition at line 1362 of file StoreValueForwardingTests.cpp.

TEST() [8/21]

TEST	(	StoreValueForwardingTests	,
		LoadForwardingFromDeltaWithConstantFP
	)

Definition at line 1282 of file StoreValueForwardingTests.cpp.

TEST() [9/21]

TEST	(	StoreValueForwardingTests	,
		LoadForwardingFromDeltaWithConstantGep
	)

Definition at line 2171 of file StoreValueForwardingTests.cpp.

TEST() [10/21]

TEST	(	StoreValueForwardingTests	,
		LoadForwardingFromDeltaWithConstantPointerNull
	)

Definition at line 1323 of file StoreValueForwardingTests.cpp.

TEST() [11/21]

TEST	(	StoreValueForwardingTests	,
		LoadForwardingFromDeltaWithConstantStruct
	)

Definition at line 1879 of file StoreValueForwardingTests.cpp.

TEST() [12/21]

TEST	(	StoreValueForwardingTests	,
		LoadForwardingFromDeltaWithIntegerConstant
	)

Definition at line 1049 of file StoreValueForwardingTests.cpp.

TEST() [13/21]

TEST	(	StoreValueForwardingTests	,
		LoadForwardingFromDeltaWithIntToPtr
	)

Definition at line 2127 of file StoreValueForwardingTests.cpp.

TEST() [14/21]

TEST	(	StoreValueForwardingTests	,
		LoadForwardingFromLoopExiting
	)

Creates an RVSDG corresponding to the C code

void opaque();
int func(int* p, int* q) {
     while(1) {
         opaque();
         if(*p) {
             return *p;
         }
         else {
             if(*q)
                 return *q;
             else
                 ; //continue
         }
     }
}

The return statements are placed in a gamma node outside the loop. The RVSDG looks like:

opaque0 = import[void opaque()]

lambda(int func(int* p, int* q)) opaque0 [p, q, io0, mem0, opaque1]{ exitPred, _, _, mem8, io3, _ = theta undef, p, q, io0, mem0, opaque1 [_, p1, q1, io1, mem1, opaque2] { mem2, io2 = CALL opaque2 io1, mem1 pLoad, mem3 = LOAD p1, mem2 zero = IntegerConstant32(0) gamma1Cond = NEq pLoad, zero gamma1Pred = MATCH[1->1, 0] gamma1Cond loopPred, exitPred1, mem7 = gamma gamma1Pred, q1, mem3 [_, mem4]{ ctrlZero = ControlConstant(0) }[ctrlZero, ctrlZero, mem4] [q2, mem5]{ qLoad, mem6 = LOAD q2, mem5 zero = IntegerConstant32(0) gamma2Cond = NEq qLoad, zero gamma2Pred = MATCH[1->1, 0] gamma2Cond loopPred1, exitPred1 = gamma gamma2Pred []{ ctrlZero1 = ControlConstant(0) ctrlOne1 = ControlConstant(1) }[ctrlZero1, ctrlOne1] []{ ctrlOne2 = ControlConstant(1) }[ctrlOne2, ctrlOne2] }[ctrlZero, ctrlZero, mem6] }[loopPred, exitPred1, p1, q1, mem7, io2, opaque2]

ret, mem13 = gamma exitPred, p, q, mem8 [p2, _, mem9]{ pLoad2, mem10 = LOAD p2, mem9 }[pLoad2, mem10] [_, q2, mem11]{ qLoad2, mem12 = LOAD q2, mem11 }[qLoad2, mem12] }[ret, io3, mem13]

Definition at line 1610 of file StoreValueForwardingTests.cpp.

TEST() [15/21]

TEST	(	StoreValueForwardingTests	,
		LoadForwardingIntoTheta
	)

Creates an RVSDG that looks like

lambda [p:ptr, io, mem0] { l1, mem1 = load[uint32] p, mem0

_, sum, mem4 = theta p, l1, mem1 [pInner, sumInner, mem2] { l2, mem3 = load[uint32] pInner, mem2 sum2 = add sumInner, l2 constant100 = IntegerConstantValue[100: uint32] compare = SignedLessThan sum2, constant100 predicate = MATCH[1->1, 0] compare }[predicate, pInner, sum2, mem3]

} [sum, io, mem4]

and validates that the load inside the theta gets removed by forwarding.

Definition at line 944 of file StoreValueForwardingTests.cpp.

TEST() [16/21]

TEST	(	StoreValueForwardingTests	,
		NestedAllocas
	)

Create a function that looks like int func(io0, mem0) { p, memP0 = ALLOCA[ptr] a, memA0 = ALLOCA[int] memP1, memA1 = STORE p, a, memP0, memA0 memP2, memA2 = STORE a, 20, memP1, memA1 a0, memP3, memA3 = LOAD p, memP2, memA2 v1, memP4, memA4 = LOAD a0, memP3, memA3 return v1, io0, mem0 }

After StoreValueForwarding, both ALLOCAs should be gone, and the return value should be 20

Definition at line 41 of file StoreValueForwardingTests.cpp.

TEST() [17/21]

TEST	(	StoreValueForwardingTests	,
		RegionPredicatedValueForwarding
	)

Creates the following RVSDG:

+-int func(int* p)---—x-—x-----------—+ | / \ | | | /----------------—/ | | | | | CTRL(0) | | | | | v v v | | | +-gamma1—x---—x-—+—x--—x–+ | | | | | 40 | | | | | | | | v v v | | | | | | | CTRL(0) STORE(int32) | CTRL(1) | | | | | | v v | v v | | | | +-—x---------—x-—+---—x–x–+ | | | | | | | ------—|---—\ | | | v v v | | +-gamma2-x-—x–+-—x-—x--—+ | | | v v | v v | | | | LOAD(int32) | LOAD(int32) | | | | v v | v v | | | +-----—x-—x–+-—x-—x--—+ | | | | | | v v | +---------------—x–x------------------—+

After StoreValueForwarding, the LOAD in the left subregion of gamma2 should be gone, replaced by an entry variable that takes 40 from the left subregion of gamma1, and undef from the right subregion. The other LOAD should remain untouched.

Definition at line 1473 of file StoreValueForwardingTests.cpp.

TEST() [18/21]

TEST	(	StoreValueForwardingTests	,
		RouteAroundLoadLoop
	)

Checks that StoreValueForwarding avoids routing values through loops with no stores. The inner LOAD needs to have a loop variable created to provide the value, but the outer LOAD should be directly replaced by the constant 40.

Create a function that looks like int func(q[ptr], io0, mem0) { mem1 = STORE[bits32] q, 40, mem0 u1 = undef[bits32] _, mem4, l2 = theta q, mem1, u1 [q1, mem2, _] { pred = CTRL(0) l1, mem3 = LOAD[bits32], q1, mem2 }[pred, q1, mem3, l1] l3, mem5 = LOAD[bits32] q, mem4 add1 = ADD l2, l3 return add1, io0, mem5 }

Definition at line 519 of file StoreValueForwardingTests.cpp.

TEST() [19/21]

TEST	(	StoreValueForwardingTests	,
		RouteOut
	)

Create a function that looks like int func(q[ptr], io0, mem0) { mem1 = STORE[bits32] q, 40, mem0 _, mem7 = theta q, mem1 [q1, mem2] { pred = CTRL(0) mem6 = gamma pred, q1, mem2 [_, q2, mem3]{ mem4 = STORE[bits32] q2, 20, mem3 }[mem4] [_, _, mem5]{ // empty region }[mem5] }[pred, q1, mem6] l1, mem8 = LOAD[bits32] q, mem7 return l1, io0, mem8 }

After StoreValueForwarding, the LOAD should be gone. The function return value should be a loop output, which leads to a gamma output, which is a constant 20 in the 0th region, and invariant in the 1st region.

Definition at line 392 of file StoreValueForwardingTests.cpp.

TEST() [20/21]

TEST	(	StoreValueForwardingTests	,
		RouteUninitialized
	)

Checks that StoreValueForwarding creates Undef nodes when forwarding from memory that has not been stored to since it was allocated.

Create a function that looks like int func(io0, mem0) { a, mem1 = ALLOCA[bits32], 1 pred = CTRL(0) mem5 = gamma prec, a, mem1 [_, a1, mem2] { mem3 = STORE a1, 20, mem2 }[mem3] [_, a2, mem4] { // Nothing happens in this gamma branch }[mem4] ld, mem6 = LOAD[bits32] a, mem5 return ld, io0, mem0 }

After StoreValueForwarding, the returned value should originate from a gamma output, which provides a constant integer 20 in the left region, and an undef node in the right branch.

Definition at line 621 of file StoreValueForwardingTests.cpp.

TEST() [21/21]

TEST	(	StoreValueForwardingTests	,
		RoutingIn
	)

Create a function that looks like int func(q[ptr], io0, mem0) { mem1 = STORE[bits32] q, 40, mem0 _, mem7, l3 = theta q, mem1, undef [q1, mem2, _] { pred = CTRL(0) l2, mem6 = gamma pred, q1, mem2 [q2, mem3]{ l1, mem4 = LOAD[bits32] q2, mem3 }[l1, mem4] [q3, mem5]{ l2 = IntegerConstantOperation(70) }[l2, mem5] }[pred, q1, mem6, l2] return l3, io0, mem7 }

After StoreValueForwarding, the LOAD should be gone, and the 40 be routed in to the gamma

Definition at line 278 of file StoreValueForwardingTests.cpp.