Jlm
RedundantBufferEliminationTests.cpp
Go to the documentation of this file.
1 /*
2  * Copyright 2025 Nico Reißmann <nico.reissmann@gmail.com>
3  * See COPYING for terms of redistribution.
4  */
5 
6 #include <gtest/gtest.h>
7 
8 #include <jlm/hls/backend/rvsdg2rhls/remove-redundant-buf.hpp>
9 #include <jlm/hls/ir/hls.hpp>
10 #include <jlm/llvm/ir/RvsdgModule.hpp>
11 #include <jlm/rvsdg/TestOperations.hpp>
12 #include <jlm/rvsdg/TestType.hpp>
13 #include <jlm/rvsdg/view.hpp>
14 
15 TEST(RedundantBufferEliminationTests, BufferWithLocalLoad)
16 {
17  using namespace jlm::hls;
18  using namespace jlm::llvm;
19  using namespace jlm::rvsdg;
20  using namespace jlm::util;
21 
22  // Arrange
23  auto valueType = jlm::rvsdg::TestType::createValueType();
24  auto i64Type = jlm::rvsdg::BitType::Create(64);
25  auto memoryStateType = MemoryStateType::Create();
26 
27  jlm::llvm::LlvmRvsdgModule rvsdgModule(FilePath(""), "", "");
28  auto & rvsdg = rvsdgModule.Rvsdg();
29 
30  auto & importI64 = jlm::rvsdg::GraphImport::Create(rvsdg, i64Type, "i64");
31  auto & importMemState = jlm::rvsdg::GraphImport::Create(rvsdg, memoryStateType, "memstate");
32  auto & importValue = jlm::rvsdg::GraphImport::Create(rvsdg, valueType, "value");
33 
34  auto loadResults = LocalLoadOperation::create(importI64, { &importMemState }, importValue);
35  auto bufferResults = BufferOperation::create(*loadResults[1], 4, false);
36 
37  auto & x = jlm::rvsdg::GraphExport::Create(*bufferResults[0], "x");
38 
39  view(rvsdg, stdout);
40 
41  // Act
42  StatisticsCollector statisticsCollector;
43  RedundantBufferElimination::CreateAndRun(rvsdgModule, statisticsCollector);
44  view(rvsdg, stdout);
45 
46  // Assert
47  // We expect the BufferOperation node to be replaced by a passthrough BufferOperation node
48  EXPECT_EQ(rvsdg.GetRootRegion().numNodes(), 2);
49  auto [bufferNode, bufferOperation] = TryGetSimpleNodeAndOptionalOp<BufferOperation>(*x.origin());
50  EXPECT_TRUE(bufferNode && bufferOperation);
51  EXPECT_EQ(bufferOperation->Capacity(), 4);
52  EXPECT_TRUE(bufferOperation->IsPassThrough());
53 }
54 
55 TEST(RedundantBufferEliminationTests, BufferWithLocalStore)
56 {
57  using namespace jlm::hls;
58  using namespace jlm::llvm;
59  using namespace jlm::rvsdg;
60  using namespace jlm::util;
61 
62  // Arrange
63  auto valueType = jlm::rvsdg::TestType::createValueType();
64  auto i64Type = jlm::rvsdg::BitType::Create(64);
65  auto memoryStateType = MemoryStateType::Create();
66 
67  jlm::llvm::LlvmRvsdgModule rvsdgModule(FilePath(""), "", "");
68  auto & rvsdg = rvsdgModule.Rvsdg();
69 
70  auto & importI64 = jlm::rvsdg::GraphImport::Create(rvsdg, i64Type, "i64");
71  auto & importMemState = jlm::rvsdg::GraphImport::Create(rvsdg, memoryStateType, "memstate");
72  auto & importValue = jlm::rvsdg::GraphImport::Create(rvsdg, valueType, "value");
73 
74  auto storeResults = LocalStoreOperation::create(importI64, importValue, { &importMemState });
75  auto bufferResults = BufferOperation::create(*storeResults[0], 4, false);
76 
77  auto & x = jlm::rvsdg::GraphExport::Create(*bufferResults[0], "x");
78 
79  view(rvsdg, stdout);
80 
81  // Act
82  StatisticsCollector statisticsCollector;
83  RedundantBufferElimination::CreateAndRun(rvsdgModule, statisticsCollector);
84  view(rvsdg, stdout);
85 
86  // Assert
87  // We expect the BufferOperation node to be replaced by a passthrough BufferOperation node
88  EXPECT_EQ(rvsdg.GetRootRegion().numNodes(), 2);
89  auto [bufferNode, bufferOperation] = TryGetSimpleNodeAndOptionalOp<BufferOperation>(*x.origin());
90  EXPECT_TRUE(bufferNode && bufferOperation);
91  EXPECT_EQ(bufferOperation->Capacity(), 4);
92  EXPECT_TRUE(bufferOperation->IsPassThrough());
93 }
94 
95 TEST(RedundantBufferEliminationTests, BufferWithLoad)
96 {
97  using namespace jlm::hls;
98  using namespace jlm::llvm;
99  using namespace jlm::rvsdg;
100  using namespace jlm::util;
101 
102  // Arrange
103  auto valueType = jlm::rvsdg::TestType::createValueType();
104  auto pointerType = PointerType::Create();
105  auto memoryStateType = MemoryStateType::Create();
106 
107  jlm::llvm::LlvmRvsdgModule rvsdgModule(FilePath(""), "", "");
108  auto & rvsdg = rvsdgModule.Rvsdg();
109 
110  auto & importPtr = jlm::rvsdg::GraphImport::Create(rvsdg, pointerType, "ptr");
111  auto & importMemState = jlm::rvsdg::GraphImport::Create(rvsdg, memoryStateType, "memstate");
112  auto & importValue = jlm::rvsdg::GraphImport::Create(rvsdg, valueType, "value");
113 
114  auto loadResults = LoadOperation::create(importPtr, { &importMemState }, importValue);
115  auto bufferResults = BufferOperation::create(*loadResults[1], 4, false);
116 
117  auto & x = jlm::rvsdg::GraphExport::Create(*bufferResults[0], "x");
118 
119  view(rvsdg, stdout);
120 
121  // Act
122  StatisticsCollector statisticsCollector;
123  RedundantBufferElimination::CreateAndRun(rvsdgModule, statisticsCollector);
124  view(rvsdg, stdout);
125 
126  // Assert
127  // We expect the BufferOperation node to be replaced by a passthrough BufferOperation node
128  EXPECT_EQ(rvsdg.GetRootRegion().numNodes(), 2);
129  auto [bufferNode, bufferOperation] = TryGetSimpleNodeAndOptionalOp<BufferOperation>(*x.origin());
130  EXPECT_TRUE(bufferNode && bufferOperation);
131  EXPECT_EQ(bufferOperation->Capacity(), 4);
132  EXPECT_TRUE(bufferOperation->IsPassThrough());
133 }
134 
135 TEST(RedundantBufferEliminationTests, BufferWithStore)
136 {
137  using namespace jlm::hls;
138  using namespace jlm::llvm;
139  using namespace jlm::rvsdg;
140  using namespace jlm::util;
141 
142  // Arrange
143  auto valueType = jlm::rvsdg::TestType::createValueType();
144  auto pointerType = PointerType::Create();
145  auto memoryStateType = MemoryStateType::Create();
146 
147  jlm::llvm::LlvmRvsdgModule rvsdgModule(FilePath(""), "", "");
148  auto & rvsdg = rvsdgModule.Rvsdg();
149 
150  auto & importPtr = jlm::rvsdg::GraphImport::Create(rvsdg, pointerType, "ptr");
151  auto & importMemState0 = jlm::rvsdg::GraphImport::Create(rvsdg, memoryStateType, "memstate0");
152  auto & importMemState1 = jlm::rvsdg::GraphImport::Create(rvsdg, memoryStateType, "memstate1");
153  auto & importValue = jlm::rvsdg::GraphImport::Create(rvsdg, valueType, "value");
154 
155  auto storeResults = jlm::hls::StoreOperation::create(
156  importPtr,
157  importValue,
158  { &importMemState0 },
159  importMemState1);
160  auto bufferResults = BufferOperation::create(*storeResults[0], 4, false);
161 
162  auto & x = jlm::rvsdg::GraphExport::Create(*bufferResults[0], "x");
163 
164  view(rvsdg, stdout);
165 
166  // Act
167  StatisticsCollector statisticsCollector;
168  RedundantBufferElimination::CreateAndRun(rvsdgModule, statisticsCollector);
169  view(rvsdg, stdout);
170 
171  // Assert
172  // We expect the BufferOperation node to be replaced by a passthrough BufferOperation node
173  EXPECT_EQ(rvsdg.GetRootRegion().numNodes(), 2);
174  auto [bufferNode, bufferOperation] = TryGetSimpleNodeAndOptionalOp<BufferOperation>(*x.origin());
175  EXPECT_TRUE(bufferNode && bufferOperation);
176  EXPECT_EQ(bufferOperation->Capacity(), 4);
177  EXPECT_TRUE(bufferOperation->IsPassThrough());
178 }
179 
180 TEST(RedundantBufferEliminationTests, BufferWithForkAndLocalLoad)
181 {
182  using namespace jlm::hls;
183  using namespace jlm::llvm;
184  using namespace jlm::rvsdg;
185  using namespace jlm::util;
186 
187  // Arrange
188  auto valueType = jlm::rvsdg::TestType::createValueType();
189  auto i64Type = jlm::rvsdg::BitType::Create(64);
190  auto memoryStateType = MemoryStateType::Create();
191 
192  jlm::llvm::LlvmRvsdgModule rvsdgModule(FilePath(""), "", "");
193  auto & rvsdg = rvsdgModule.Rvsdg();
194 
195  auto & importI64 = jlm::rvsdg::GraphImport::Create(rvsdg, i64Type, "i64");
196  auto & importMemState = jlm::rvsdg::GraphImport::Create(rvsdg, memoryStateType, "memstate");
197  auto & importValue = jlm::rvsdg::GraphImport::Create(rvsdg, valueType, "value");
198 
199  auto loadResults = LocalLoadOperation::create(importI64, { &importMemState }, importValue);
200  auto forkResults = ForkOperation::create(2, *loadResults[1]);
201  auto bufferResults = BufferOperation::create(*forkResults[0], 4, false);
202 
203  auto & x = jlm::rvsdg::GraphExport::Create(*bufferResults[0], "x");
204 
205  view(rvsdg, stdout);
206 
207  // Act
208  StatisticsCollector statisticsCollector;
209  RedundantBufferElimination::CreateAndRun(rvsdgModule, statisticsCollector);
210  view(rvsdg, stdout);
211 
212  // Assert
213  // We expect the BufferOperation node to be replaced by a passthrough BufferOperation node
214  EXPECT_EQ(rvsdg.GetRootRegion().numNodes(), 3);
215  auto [bufferNode, bufferOperation] = TryGetSimpleNodeAndOptionalOp<BufferOperation>(*x.origin());
216  EXPECT_TRUE(bufferNode && bufferOperation);
217  EXPECT_EQ(bufferOperation->Capacity(), 4);
218  EXPECT_TRUE(bufferOperation->IsPassThrough());
219 }
220 
221 TEST(RedundantBufferEliminationTests, BufferWithBranchAndLocalLoad)
222 {
223  using namespace jlm::hls;
224  using namespace jlm::llvm;
225  using namespace jlm::rvsdg;
226  using namespace jlm::util;
227 
228  // Arrange
229  auto valueType = jlm::rvsdg::TestType::createValueType();
230  auto i64Type = jlm::rvsdg::BitType::Create(64);
231  auto controlType = ControlType::Create(2);
232  auto memoryStateType = MemoryStateType::Create();
233 
234  jlm::llvm::LlvmRvsdgModule rvsdgModule(FilePath(""), "", "");
235  auto & rvsdg = rvsdgModule.Rvsdg();
236 
237  auto & importI64 = jlm::rvsdg::GraphImport::Create(rvsdg, i64Type, "i64");
238  auto & importControl = jlm::rvsdg::GraphImport::Create(rvsdg, controlType, "control");
239  auto & importMemState = jlm::rvsdg::GraphImport::Create(rvsdg, memoryStateType, "memstate");
240  auto & importValue = jlm::rvsdg::GraphImport::Create(rvsdg, valueType, "value");
241 
242  auto loadResults = LocalLoadOperation::create(importI64, { &importMemState }, importValue);
243  auto branchResults = BranchOperation::create(importControl, *loadResults[1]);
244  auto bufferResults = BufferOperation::create(*branchResults[0], 4, false);
245 
246  auto & x = jlm::rvsdg::GraphExport::Create(*bufferResults[0], "x");
247 
248  view(rvsdg, stdout);
249 
250  // Act
251  StatisticsCollector statisticsCollector;
252  RedundantBufferElimination::CreateAndRun(rvsdgModule, statisticsCollector);
253  view(rvsdg, stdout);
254 
255  // Assert
256  // We expect the BufferOperation node to be replaced by a passthrough BufferOperation node
257  EXPECT_EQ(rvsdg.GetRootRegion().numNodes(), 3);
258  auto [bufferNode, bufferOperation] = TryGetSimpleNodeAndOptionalOp<BufferOperation>(*x.origin());
259  EXPECT_TRUE(bufferNode && bufferOperation);
260  EXPECT_EQ(bufferOperation->Capacity(), 4);
261  EXPECT_TRUE(bufferOperation->IsPassThrough());
262 }
263 
264 TEST(RedundantBufferEliminationTests, BufferWithOtherNode)
265 {
266  using namespace jlm::hls;
267  using namespace jlm::llvm;
268  using namespace jlm::rvsdg;
269  using namespace jlm::util;
270 
271  // Arrange
272  auto valueType = jlm::rvsdg::TestType::createValueType();
273  auto memoryStateType = MemoryStateType::Create();
274 
275  jlm::llvm::LlvmRvsdgModule rvsdgModule(FilePath(""), "", "");
276  auto & rvsdg = rvsdgModule.Rvsdg();
277 
278  auto & importValue = jlm::rvsdg::GraphImport::Create(rvsdg, valueType, "value");
279 
280  auto node =
281  TestOperation::createNode(&rvsdg.GetRootRegion(), { &importValue }, { memoryStateType });
282  auto bufferResults = BufferOperation::create(*node->output(0), 4, false);
283 
284  auto & x = jlm::rvsdg::GraphExport::Create(*bufferResults[0], "x");
285 
286  view(rvsdg, stdout);
287 
288  // Act
289  StatisticsCollector statisticsCollector;
290  RedundantBufferElimination::CreateAndRun(rvsdgModule, statisticsCollector);
291  view(rvsdg, stdout);
292 
293  // Assert
294  // We expect the BufferOperation node to NOT have been replaced as the operand of the
295  // BufferOperation node cannot be traced to a Load-/Store-/LocalLoad-/LocalStoreOperation node
296  EXPECT_EQ(rvsdg.GetRootRegion().numNodes(), 2);
297  EXPECT_EQ(x.origin(), bufferResults[0]);
298  auto [bufferNode, bufferOperation] = TryGetSimpleNodeAndOptionalOp<BufferOperation>(*x.origin());
299  EXPECT_TRUE(bufferNode && bufferOperation);
300  EXPECT_EQ(bufferOperation->Capacity(), 4);
301  EXPECT_FALSE(bufferOperation->IsPassThrough());
302 }
303 
304 TEST(RedundantBufferEliminationTests, BufferWithNonMemoryStateOperand)
305 {
306  using namespace jlm::hls;
307  using namespace jlm::llvm;
308  using namespace jlm::rvsdg;
309  using namespace jlm::util;
310 
311  // Arrange
312  auto valueType = jlm::rvsdg::TestType::createValueType();
313  auto i64Type = jlm::rvsdg::BitType::Create(64);
314  auto memoryStateType = MemoryStateType::Create();
315 
316  jlm::llvm::LlvmRvsdgModule rvsdgModule(FilePath(""), "", "");
317  auto & rvsdg = rvsdgModule.Rvsdg();
318 
319  auto & importI64 = jlm::rvsdg::GraphImport::Create(rvsdg, i64Type, "i64");
320  auto & importMemState = jlm::rvsdg::GraphImport::Create(rvsdg, memoryStateType, "memstate");
321  auto & importValue = jlm::rvsdg::GraphImport::Create(rvsdg, valueType, "value");
322 
323  auto loadResults = LocalLoadOperation::create(importI64, { &importMemState }, importValue);
324  auto bufferResults = BufferOperation::create(*loadResults[0], 4, false);
325 
326  auto & x = jlm::rvsdg::GraphExport::Create(*bufferResults[0], "x");
327 
328  view(rvsdg, stdout);
329 
330  // Act
331  StatisticsCollector statisticsCollector;
332  RedundantBufferElimination::CreateAndRun(rvsdgModule, statisticsCollector);
333  view(rvsdg, stdout);
334 
335  // Assert
336  // We expect the BufferOperation node to NOT have been replaced as the operand of the
337  // BufferOperation node is not of type llvm::MemoryStateType
338  EXPECT_EQ(rvsdg.GetRootRegion().numNodes(), 2);
339  EXPECT_EQ(x.origin(), bufferResults[0]);
340  auto [bufferNode, bufferOperation] = TryGetSimpleNodeAndOptionalOp<BufferOperation>(*x.origin());
341  EXPECT_TRUE(bufferNode && bufferOperation);
342  EXPECT_EQ(bufferOperation->Capacity(), 4);
343  EXPECT_FALSE(bufferOperation->IsPassThrough());
344 }
345 
346 TEST(RedundantBufferEliminationTests, PassthroughBuffer)
347 {
348  using namespace jlm::hls;
349  using namespace jlm::llvm;
350  using namespace jlm::rvsdg;
351  using namespace jlm::util;
352 
353  // Arrange
354  auto valueType = jlm::rvsdg::TestType::createValueType();
355  auto i64Type = jlm::rvsdg::BitType::Create(64);
356  auto memoryStateType = MemoryStateType::Create();
357 
358  jlm::llvm::LlvmRvsdgModule rvsdgModule(FilePath(""), "", "");
359  auto & rvsdg = rvsdgModule.Rvsdg();
360 
361  auto & importI64 = jlm::rvsdg::GraphImport::Create(rvsdg, i64Type, "i64");
362  auto & importMemState = jlm::rvsdg::GraphImport::Create(rvsdg, memoryStateType, "memstate");
363  auto & importValue = jlm::rvsdg::GraphImport::Create(rvsdg, valueType, "value");
364 
365  auto loadResults = LocalLoadOperation::create(importI64, { &importMemState }, importValue);
366  auto bufferResults = BufferOperation::create(*loadResults[1], 4, true);
367 
368  auto & x = jlm::rvsdg::GraphExport::Create(*bufferResults[0], "x");
369 
370  view(rvsdg, stdout);
371 
372  // Act
373  StatisticsCollector statisticsCollector;
374  RedundantBufferElimination::CreateAndRun(rvsdgModule, statisticsCollector);
375  view(rvsdg, stdout);
376 
377  // Assert
378  // We expect the BufferOperation node to NOT have been replaced as the BufferOperation is already
379  // marked as passthrough.
380  EXPECT_EQ(rvsdg.GetRootRegion().numNodes(), 2);
381  EXPECT_EQ(x.origin(), bufferResults[0]);
382  auto [bufferNode, bufferOperation] = TryGetSimpleNodeAndOptionalOp<BufferOperation>(*x.origin());
383  EXPECT_TRUE(bufferNode && bufferOperation);
384  EXPECT_EQ(bufferOperation->Capacity(), 4);
385  EXPECT_TRUE(bufferOperation->IsPassThrough());
386 }
statisticsCollector
static jlm::util::StatisticsCollector statisticsCollector
Definition: CommonNodeEliminationTests.cpp:21
TEST
TEST(RedundantBufferEliminationTests, BufferWithLocalLoad)
Definition: RedundantBufferEliminationTests.cpp:15
jlm::hls::BranchOperation::create
static std::vector< jlm::rvsdg::Output * > create(jlm::rvsdg::Output &predicate, jlm::rvsdg::Output &value, bool loop=false)
Definition: hls.hpp:68
jlm::hls::BufferOperation::create
static std::vector< jlm::rvsdg::Output * > create(jlm::rvsdg::Output &value, size_t capacity, bool pass_through=false)
Definition: hls.hpp:438
jlm::hls::ForkOperation::create
static std::vector< jlm::rvsdg::Output * > create(size_t nalternatives, jlm::rvsdg::Output &value, bool isConstant=false)
Definition: hls.hpp:161
jlm::hls::LoadOperation::create
static std::vector< jlm::rvsdg::Output * > create(jlm::rvsdg::Output &addr, const std::vector< jlm::rvsdg::Output * > &states, jlm::rvsdg::Output &load_result)
Definition: hls.hpp:957
jlm::hls::LocalLoadOperation::create
static std::vector< jlm::rvsdg::Output * > create(jlm::rvsdg::Output &index, const std::vector< jlm::rvsdg::Output * > &states, jlm::rvsdg::Output &load_result)
Definition: hls.hpp:1596
jlm::hls::LocalStoreOperation::create
static std::vector< jlm::rvsdg::Output * > create(jlm::rvsdg::Output &index, jlm::rvsdg::Output &value, const std::vector< jlm::rvsdg::Output * > &states)
Definition: hls.hpp:1669
jlm::hls::RedundantBufferElimination::CreateAndRun
static void CreateAndRun(rvsdg::RvsdgModule &module, util::StatisticsCollector &statisticsCollector)
Definition: remove-redundant-buf.cpp:22
jlm::hls::StoreOperation::create
static std::vector< jlm::rvsdg::Output * > create(jlm::rvsdg::Output &addr, jlm::rvsdg::Output &value, const std::vector< jlm::rvsdg::Output * > &states, jlm::rvsdg::Output &resp)
Definition: hls.hpp:1428
jlm::llvm::MemoryStateType::Create
static std::shared_ptr< const MemoryStateType > Create()
Definition: types.cpp:379
jlm::llvm::PointerType::Create
static std::shared_ptr< const PointerType > Create()
Definition: types.cpp:45
jlm::rvsdg::BitType::Create
static std::shared_ptr< const BitType > Create(std::size_t nbits)
Creates bit type of specified width.
Definition: type.cpp:45
jlm::rvsdg::ControlType::Create
static std::shared_ptr< const ControlType > Create(std::size_t nalternatives)
Instantiates control type.
Definition: control.cpp:50
jlm::rvsdg::GraphExport::Create
static GraphExport & Create(Output &origin, std::string name)
Definition: graph.cpp:62
jlm::rvsdg::GraphImport::Create
static GraphImport & Create(Graph &graph, std::shared_ptr< const rvsdg::Type > type, std::string name)
Definition: graph.cpp:36
jlm::rvsdg::RvsdgModule::Rvsdg
Graph & Rvsdg() noexcept
Definition: RvsdgModule.hpp:57
jlm::rvsdg::TestOperation::createNode
static SimpleNode * createNode(Region *region, const std::vector< Output * > &operands, std::vector< std::shared_ptr< const Type >> resultTypes)
Definition: TestOperations.hpp:191
jlm::rvsdg::TestType::createValueType
static std::shared_ptr< const TestType > createValueType()
Definition: TestType.cpp:67
jlm::llvm
Global memory state passed between functions.
Definition: IpGraphToLlvmConverter.cpp:36
jlm::rvsdg::view
std::string view(const rvsdg::Region *region)
Definition: view.cpp:142
Generated by doxygen 1.9.1