Jlm
LoopStrengthReductionTests.cpp
Go to the documentation of this file.
1 /*
2  * Copyright 2026 Andreas Lilleby Hjulstad <andreas.lilleby.hjulstad@gmail.com>
3  * See COPYING for terms of redistribution.
4  */
5 
6 #include <jlm/llvm/ir/operators/call.hpp>
7 #include <jlm/llvm/ir/operators/delta.hpp>
8 #include <jlm/llvm/ir/operators/GetElementPtr.hpp>
9 #include <jlm/llvm/ir/operators/IntegerOperations.hpp>
10 #include <jlm/llvm/ir/operators/lambda.hpp>
11 #include <jlm/llvm/ir/operators/Load.hpp>
12 #include <jlm/llvm/ir/operators/operators.hpp>
13 #include <jlm/llvm/ir/operators/sext.hpp>
14 #include <jlm/llvm/ir/operators/Store.hpp>
15 #include <jlm/llvm/ir/RvsdgModule.hpp>
16 #include <jlm/llvm/opt/LoopStrengthReduction.hpp>
17 #include <jlm/rvsdg/gamma.hpp>
18 #include <jlm/rvsdg/TestOperations.hpp>
19 #include <jlm/rvsdg/view.hpp>
20 
21 #include <gtest/gtest.h>
22 
23 void
24 RunLoopStrengthReduction(jlm::rvsdg::RvsdgModule & rvsdgModule)
25 {
26  jlm::llvm::LoopStrengthReduction loopStrengthReduction;
27  jlm::util::StatisticsCollector statisticsCollector;
28  loopStrengthReduction.Run(rvsdgModule, statisticsCollector);
29 }
30 
31 TEST(LoopStrengthReductionTests, SimpleArithmeticCandidateOperation)
32 {
33  // Tests strength reduction of a simple candidate operation j = 3 * i
34  // i has the recurrence {0,+,2}. Applying strength reduction should result in us creating a new
35  // induction variable for j with the recurrence {0,+,6}
36  using namespace jlm::llvm;
37 
38  // Arrange
39  const auto intType = jlm::rvsdg::BitType::Create(32);
40  const auto memoryStateType = MemoryStateType::Create();
41 
42  LlvmRvsdgModule rvsdgModule(jlm::util::FilePath(""), "", "");
43  auto & graph = rvsdgModule.Rvsdg();
44 
45  auto mem = &jlm::rvsdg::GraphImport::Create(graph, memoryStateType, "");
46 
47  const auto & c0 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 0);
48  const auto & theta = jlm::rvsdg::ThetaNode::create(&graph.GetRootRegion());
49 
50  const auto memoryState = theta->AddLoopVar(mem);
51  const auto lv1 = theta->AddLoopVar(c0.output(0)); // i
52 
53  const auto & c2 = IntegerConstantOperation::Create(*theta->subregion(), 32, 2);
54  auto & addNode = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv1.pre, c2.output(0) }, 32);
55 
56  const auto & c3 = IntegerConstantOperation::Create(*theta->subregion(), 32, 3);
57  auto & mulNode = jlm::rvsdg::CreateOpNode<IntegerMulOperation>({ lv1.pre, c3.output(0) }, 32);
58 
59  auto testOperation = jlm::rvsdg::TestOperation::createNode(
60  theta->subregion(),
61  { mulNode.output(0), memoryState.pre },
62  { memoryStateType });
63 
64  const auto & c5 = IntegerConstantOperation::Create(*theta->subregion(), 32, 5);
65 
66  auto & sltNode =
67  jlm::rvsdg::CreateOpNode<IntegerSltOperation>({ addNode.output(0), c5.output(0) }, 32);
68  const auto matchResult =
69  jlm::rvsdg::MatchOperation::Create(*sltNode.output(0), { { 1, 1 } }, 0, 2);
70 
71  theta->set_predicate(matchResult);
72  lv1.post->divert_to(addNode.output(0));
73  memoryState.post->divert_to(testOperation->output(0));
74 
75  jlm::rvsdg::GraphExport::Create(*memoryState.output, "");
76 
77  // std::cout << "Before: \n";
78  // jlm::rvsdg::view(graph, stdout);
79 
80  const auto numLoopVarsBefore = theta->GetLoopVars().size();
81 
82  // Act
83  RunLoopStrengthReduction(rvsdgModule);
84 
85  // std::cout << "After: \n";
86  // jlm::rvsdg::view(graph, stdout);
87 
88  const auto numLoopVarsAfter = theta->GetLoopVars().size();
89 
90  // Assert
91 
92  // Check that a new loop variable was added
93  EXPECT_EQ(numLoopVarsAfter, numLoopVarsBefore + 1);
94 
95  auto newIV = theta->GetLoopVars()[numLoopVarsAfter - 1];
96 
97  // Check the start value
98  const auto & IVInputNode =
99  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::SimpleNode>(*newIV.input->origin());
100  EXPECT_TRUE(jlm::rvsdg::is<IntegerConstantOperation>(IVInputNode->GetOperation()));
101  const auto & constantOperation =
102  dynamic_cast<const IntegerConstantOperation *>(&IVInputNode->GetOperation());
103  EXPECT_NE(constantOperation, nullptr);
104  EXPECT_EQ(constantOperation->Representation().to_uint(), 0u);
105 
106  // Check that the post value of the new IV comes from a new ADD node
107  const auto & IVPostOrigin =
108  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::SimpleNode>(*newIV.post->origin());
109  EXPECT_TRUE(jlm::rvsdg::is<IntegerAddOperation>(IVPostOrigin->GetOperation()));
110 
111  // Check that LHS of the ADD is the pre value of the new IV
112  EXPECT_EQ(IVPostOrigin->input(0)->origin(), newIV.pre);
113 
114  // Check that RHS of the ADD is an integer constant with the step value (6)
115  const auto & addRhsInputNode =
116  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::SimpleNode>(*IVPostOrigin->input(1)->origin());
117  EXPECT_TRUE(jlm::rvsdg::is<IntegerConstantOperation>(addRhsInputNode));
118  const auto & rhsConstantOperation =
119  dynamic_cast<const IntegerConstantOperation *>(&addRhsInputNode->GetOperation());
120  EXPECT_NE(rhsConstantOperation, nullptr);
121  EXPECT_EQ(rhsConstantOperation->Representation().to_uint(), 6u);
122 
123  // Check that the test operation now uses the new induction variable
124  EXPECT_EQ(testOperation->input(0)->origin(), newIV.pre);
125 }
126 
127 TEST(LoopStrengthReductionTests, CandidateOperationDependentOnInvalidInductionVariable)
128 {
129  // Tests that applying strength reduction on a loop with candidate operation j = 3 * i, where i is
130  // an invalid (geometric) induction variable i, results in no change
131  using namespace jlm::llvm;
132 
133  // Arrange
134  const auto intType = jlm::rvsdg::BitType::Create(32);
135  const auto memoryStateType = MemoryStateType::Create();
136 
137  LlvmRvsdgModule rvsdgModule(jlm::util::FilePath(""), "", "");
138  auto & graph = rvsdgModule.Rvsdg();
139 
140  auto mem = &jlm::rvsdg::GraphImport::Create(graph, memoryStateType, "");
141 
142  const auto & c0 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 0);
143  const auto & theta = jlm::rvsdg::ThetaNode::create(&graph.GetRootRegion());
144 
145  const auto memoryState = theta->AddLoopVar(mem);
146  const auto lv1 = theta->AddLoopVar(c0.output(0)); // i
147 
148  const auto & c2 = IntegerConstantOperation::Create(*theta->subregion(), 32, 2);
149  auto & mulNode1 = jlm::rvsdg::CreateOpNode<IntegerMulOperation>({ lv1.pre, c2.output(0) }, 32);
150 
151  const auto & c3 = IntegerConstantOperation::Create(*theta->subregion(), 32, 3);
152  auto & mulNode2 = jlm::rvsdg::CreateOpNode<IntegerMulOperation>({ lv1.pre, c3.output(0) }, 32);
153 
154  auto testOperation = jlm::rvsdg::TestOperation::createNode(
155  theta->subregion(),
156  { mulNode2.output(0), memoryState.pre },
157  { memoryStateType });
158 
159  const auto & c5 = IntegerConstantOperation::Create(*theta->subregion(), 32, 5);
160 
161  auto & sltNode =
162  jlm::rvsdg::CreateOpNode<IntegerSltOperation>({ mulNode1.output(0), c5.output(0) }, 32);
163  const auto matchResult =
164  jlm::rvsdg::MatchOperation::Create(*sltNode.output(0), { { 1, 1 } }, 0, 2);
165 
166  theta->set_predicate(matchResult);
167  lv1.post->divert_to(mulNode1.output(0));
168  memoryState.post->divert_to(testOperation->output(0));
169 
170  jlm::rvsdg::GraphExport::Create(*memoryState.output, "");
171 
172  // std::cout << "Before: \n";
173  // jlm::rvsdg::view(graph, stdout);
174 
175  const auto numLoopVarsBefore = theta->GetLoopVars().size();
176 
177  // Act
178  RunLoopStrengthReduction(rvsdgModule);
179 
180  // std::cout << "After: \n";
181  // jlm::rvsdg::view(graph, stdout);
182 
183  const auto numLoopVarsAfter = theta->GetLoopVars().size();
184 
185  // Assert
186 
187  // Check that no loop variables were added
188  EXPECT_EQ(numLoopVarsAfter, numLoopVarsBefore);
189 
190  // Check that the test operation still uses the MUL node (no change)
191  EXPECT_EQ(testOperation->input(0)->origin(), mulNode2.output(0));
192 }
193 
194 TEST(LoopStrengthReductionTests, NestedArithmeticCandidateOperation)
195 {
196  // Tests that we don't create unnecessary induction variables for nested operations.
197  // It applies strength reduction on a loop with candidate operations j = 3 * i and k = j + 1.
198  // i has the recurrence {0,+,2}. Even though k is defined with an addition, it's definition (scev
199  // tree) includes the multiplication from j, and it is therefore a candidate to be reduced.
200  // Since j has no other users than k, applying strength reduction should result in us only
201  // creating a new induction variable for k with the recurrence {1,+,6}
202  using namespace jlm::llvm;
203 
204  // Arrange
205  const auto intType = jlm::rvsdg::BitType::Create(32);
206  const auto memoryStateType = MemoryStateType::Create();
207 
208  LlvmRvsdgModule rvsdgModule(jlm::util::FilePath(""), "", "");
209  auto & graph = rvsdgModule.Rvsdg();
210 
211  auto mem = &jlm::rvsdg::GraphImport::Create(graph, memoryStateType, "");
212 
213  const auto & c0 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 0);
214  const auto & theta = jlm::rvsdg::ThetaNode::create(&graph.GetRootRegion());
215 
216  const auto memoryState = theta->AddLoopVar(mem);
217  const auto lv1 = theta->AddLoopVar(c0.output(0)); // i
218 
219  const auto & c2 = IntegerConstantOperation::Create(*theta->subregion(), 32, 2);
220  auto & addNode1 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv1.pre, c2.output(0) }, 32);
221 
222  const auto & c3 = IntegerConstantOperation::Create(*theta->subregion(), 32, 3);
223  auto & mulNode = jlm::rvsdg::CreateOpNode<IntegerMulOperation>({ lv1.pre, c3.output(0) }, 32);
224 
225  const auto & c1 = IntegerConstantOperation::Create(*theta->subregion(), 32, 1);
226  auto & addNode2 =
227  jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ mulNode.output(0), c1.output(0) }, 32);
228 
229  auto testOperation = jlm::rvsdg::TestOperation::createNode(
230  theta->subregion(),
231  { addNode2.output(0), memoryState.pre },
232  { memoryStateType });
233 
234  const auto & c5 = IntegerConstantOperation::Create(*theta->subregion(), 32, 5);
235 
236  auto & sltNode =
237  jlm::rvsdg::CreateOpNode<IntegerSltOperation>({ addNode1.output(0), c5.output(0) }, 32);
238  const auto matchResult =
239  jlm::rvsdg::MatchOperation::Create(*sltNode.output(0), { { 1, 1 } }, 0, 2);
240 
241  theta->set_predicate(matchResult);
242  lv1.post->divert_to(addNode1.output(0));
243  memoryState.post->divert_to(testOperation->output(0));
244 
245  jlm::rvsdg::GraphExport::Create(*memoryState.output, "");
246 
247  // std::cout << "Before: \n";
248  // jlm::rvsdg::view(graph, stdout);
249 
250  const auto numLoopVarsBefore = theta->GetLoopVars().size();
251 
252  // Act
253  RunLoopStrengthReduction(rvsdgModule);
254 
255  // std::cout << "After: \n";
256  // jlm::rvsdg::view(graph, stdout);
257 
258  const auto numLoopVarsAfter = theta->GetLoopVars().size();
259 
260  // Assert
261 
262  // Check that only one loop variable was added
263  EXPECT_EQ(numLoopVarsAfter, numLoopVarsBefore + 1);
264 
265  auto newIV = theta->GetLoopVars()[numLoopVarsAfter - 1];
266 
267  // Check the start value
268  const auto & IVInputNode =
269  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::SimpleNode>(*newIV.input->origin());
270  EXPECT_TRUE(jlm::rvsdg::is<IntegerConstantOperation>(IVInputNode->GetOperation()));
271  const auto & constantOperation =
272  dynamic_cast<const IntegerConstantOperation *>(&IVInputNode->GetOperation());
273  EXPECT_NE(constantOperation, nullptr);
274  EXPECT_EQ(constantOperation->Representation().to_uint(), 1u);
275 
276  // Check that the post value of the new IV comes from a new ADD node
277  const auto & IVPostOrigin =
278  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::SimpleNode>(*newIV.post->origin());
279  EXPECT_TRUE(jlm::rvsdg::is<IntegerAddOperation>(IVPostOrigin->GetOperation()));
280  // Check that LHS of the ADD is the pre value of the new IV
281  EXPECT_EQ(IVPostOrigin->input(0)->origin(), newIV.pre);
282  // Check that RHS of the ADD is an integer constant with the step value (6)
283  const auto & addRhsInputNode =
284  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::SimpleNode>(*IVPostOrigin->input(1)->origin());
285  EXPECT_TRUE(jlm::rvsdg::is<IntegerConstantOperation>(addRhsInputNode));
286  const auto & rhsConstantOperation =
287  dynamic_cast<const IntegerConstantOperation *>(&addRhsInputNode->GetOperation());
288  EXPECT_NE(rhsConstantOperation, nullptr);
289  EXPECT_EQ(rhsConstantOperation->Representation().to_uint(), 6u);
290 
291  // Check that the test operation now uses the new induction variable
292  EXPECT_EQ(testOperation->input(0)->origin(), newIV.pre);
293 }
294 
295 TEST(LoopStrengthReductionTests, NestedArithmeticCandidateOperationWithUsersForBoth)
296 {
297  // Tests strength reduction of the two candidate operations j = 3 * i and k = j + 1 where both j
298  // and k have users. i has the recurrence {0,+,2}. Since both j and k are being used, applying
299  // strength reduction should result in us creating two new induction variables, one for j with the
300  // recurrence {0,+,6} and one for k with the recurrence {1,+,6}
301  using namespace jlm::llvm;
302 
303  // Arrange
304  const auto intType = jlm::rvsdg::BitType::Create(32);
305  const auto memoryStateType = MemoryStateType::Create();
306 
307  LlvmRvsdgModule rvsdgModule(jlm::util::FilePath(""), "", "");
308  auto & graph = rvsdgModule.Rvsdg();
309 
310  auto mem = &jlm::rvsdg::GraphImport::Create(graph, memoryStateType, "");
311 
312  const auto & c0 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 0);
313  const auto & theta = jlm::rvsdg::ThetaNode::create(&graph.GetRootRegion());
314 
315  const auto memoryState = theta->AddLoopVar(mem);
316  const auto lv1 = theta->AddLoopVar(c0.output(0)); // i
317 
318  const auto & c2 = IntegerConstantOperation::Create(*theta->subregion(), 32, 2);
319  auto & addNode1 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv1.pre, c2.output(0) }, 32);
320 
321  const auto & c3 = IntegerConstantOperation::Create(*theta->subregion(), 32, 3);
322  auto & mulNode = jlm::rvsdg::CreateOpNode<IntegerMulOperation>({ lv1.pre, c3.output(0) }, 32);
323 
324  const auto & c1 = IntegerConstantOperation::Create(*theta->subregion(), 32, 1);
325  auto & addNode2 =
326  jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ mulNode.output(0), c1.output(0) }, 32);
327 
328  auto testOperation1 = jlm::rvsdg::TestOperation::createNode(
329  theta->subregion(),
330  { mulNode.output(0), memoryState.pre },
331  { memoryStateType });
332 
333  auto testOperation2 = jlm::rvsdg::TestOperation::createNode(
334  theta->subregion(),
335  { addNode2.output(0), testOperation1->output(0) },
336  { memoryStateType });
337 
338  const auto & c5 = IntegerConstantOperation::Create(*theta->subregion(), 32, 5);
339 
340  auto & sltNode =
341  jlm::rvsdg::CreateOpNode<IntegerSltOperation>({ addNode1.output(0), c5.output(0) }, 32);
342  const auto matchResult =
343  jlm::rvsdg::MatchOperation::Create(*sltNode.output(0), { { 1, 1 } }, 0, 2);
344 
345  theta->set_predicate(matchResult);
346  lv1.post->divert_to(addNode1.output(0));
347  memoryState.post->divert_to(testOperation2->output(0));
348 
349  jlm::rvsdg::GraphExport::Create(*memoryState.output, "");
350 
351  // std::cout << "Before: \n";
352  // jlm::rvsdg::view(graph, stdout);
353 
354  const auto numLoopVarsBefore = theta->GetLoopVars().size();
355 
356  // Act
357  RunLoopStrengthReduction(rvsdgModule);
358 
359  // std::cout << "After: \n";
360  // jlm::rvsdg::view(graph, stdout);
361 
362  const auto numLoopVarsAfter = theta->GetLoopVars().size();
363 
364  // Assert
365 
366  // Check that two new loop variables were added
367  EXPECT_EQ(numLoopVarsAfter, numLoopVarsBefore + 2);
368 
369  auto newIV1 = theta->GetLoopVars()[numLoopVarsAfter - 1];
370  auto newIV2 = theta->GetLoopVars()[numLoopVarsAfter - 2];
371 
372  // Check their start values
373  const auto & IV1InputNode =
374  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::SimpleNode>(*newIV1.input->origin());
375  EXPECT_TRUE(jlm::rvsdg::is<IntegerConstantOperation>(IV1InputNode->GetOperation()));
376  auto constantOperation1 =
377  dynamic_cast<const IntegerConstantOperation *>(&IV1InputNode->GetOperation());
378  EXPECT_NE(constantOperation1, nullptr);
379  EXPECT_EQ(constantOperation1->Representation().to_uint(), 1u);
380 
381  const auto & IV2InputNode =
382  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::SimpleNode>(*newIV2.input->origin());
383  EXPECT_TRUE(jlm::rvsdg::is<IntegerConstantOperation>(IV2InputNode->GetOperation()));
384  auto constantOperation2 =
385  dynamic_cast<const IntegerConstantOperation *>(&IV2InputNode->GetOperation());
386  EXPECT_NE(constantOperation2, nullptr);
387  EXPECT_EQ(constantOperation2->Representation().to_uint(), 0u);
388 
389  // Check that the post value of the new IV comes from a new ADD node
390  const auto & IV1PostOrigin =
391  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::SimpleNode>(*newIV1.post->origin());
392  EXPECT_TRUE(jlm::rvsdg::is<IntegerAddOperation>(IV1PostOrigin->GetOperation()));
393  // Check that LHS of the ADD is the pre value of the new IV1
394  EXPECT_EQ(IV1PostOrigin->input(0)->origin(), newIV1.pre);
395  // Check that RHS of the ADD is an integer constant with the step value (6)
396  const auto & addRhsInputNode1 =
397  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::SimpleNode>(*IV1PostOrigin->input(1)->origin());
398  EXPECT_TRUE(jlm::rvsdg::is<IntegerConstantOperation>(addRhsInputNode1));
399  const auto & rhsConstantOperation1 =
400  dynamic_cast<const IntegerConstantOperation *>(&addRhsInputNode1->GetOperation());
401  EXPECT_NE(rhsConstantOperation1, nullptr);
402  EXPECT_EQ(rhsConstantOperation1->Representation().to_uint(), 6u);
403 
404  const auto & IV2PostOrigin =
405  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::SimpleNode>(*newIV2.post->origin());
406  EXPECT_TRUE(jlm::rvsdg::is<IntegerAddOperation>(IV2PostOrigin->GetOperation()));
407  // Check that LHS of the ADD is the pre value of the new IV2
408  EXPECT_EQ(IV2PostOrigin->input(0)->origin(), newIV2.pre);
409  // Check that RHS of the ADD is an integer constant with the step value (6)
410  const auto & addRhsInputNode2 =
411  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::SimpleNode>(*IV2PostOrigin->input(1)->origin());
412  EXPECT_TRUE(jlm::rvsdg::is<IntegerConstantOperation>(addRhsInputNode2));
413  const auto & rhsConstantOperation2 =
414  dynamic_cast<const IntegerConstantOperation *>(&addRhsInputNode2->GetOperation());
415  EXPECT_NE(rhsConstantOperation2, nullptr);
416  EXPECT_EQ(rhsConstantOperation2->Representation().to_uint(), 6u);
417 
418  // Check that the test operations now use their respective new induction variables
419  EXPECT_EQ(testOperation1->input(0)->origin(), newIV2.pre);
420  EXPECT_EQ(testOperation2->input(0)->origin(), newIV1.pre);
421 }
422 
423 TEST(LoopStrengthReductionTests, SimpleGEPCandidateOperation)
424 {
425  // Tests strength reduction of a GEP operation which takes j = 3 * i as index. i has the
426  // recurrence {0,+,2} and j has recurrence {0,+,6}. Since the GEP has int type, the recurrence for
427  // the GEP is {Init(a1),+,24}. We expect to strength reduce the original GEP to a new loop
428  // variable which is incremented by the value of a new GEP with byte type and offset 24
429  using namespace jlm::llvm;
430 
431  // Arrange
432  const auto intType = jlm::rvsdg::BitType::Create(32);
433  const auto intArrayType = ArrayType::Create(intType, 5);
434  const auto pointerType = PointerType::Create();
435  const auto memoryStateType = MemoryStateType::Create();
436 
437  LlvmRvsdgModule rvsdgModule(jlm::util::FilePath(""), "", "");
438  auto & graph = rvsdgModule.Rvsdg();
439 
440  auto arrPtr = &jlm::rvsdg::GraphImport::Create(graph, pointerType, "arrPtr");
441  auto mem = &jlm::rvsdg::GraphImport::Create(graph, memoryStateType, "");
442 
443  const auto & c0_1 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 0);
444  const auto & theta = jlm::rvsdg::ThetaNode::create(&graph.GetRootRegion());
445 
446  const auto memoryState = theta->AddLoopVar(mem);
447  const auto lv1 = theta->AddLoopVar(c0_1.output(0)); // i
448  const auto lv2 = theta->AddLoopVar(arrPtr); // arr ptr
449 
450  const auto & c2 = IntegerConstantOperation::Create(*theta->subregion(), 32, 2);
451  auto & addNode1 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv1.pre, c2.output(0) }, 32);
452 
453  const auto & c3 = IntegerConstantOperation::Create(*theta->subregion(), 32, 3);
454  auto & mulNode = jlm::rvsdg::CreateOpNode<IntegerMulOperation>({ lv1.pre, c3.output(0) }, 32);
455 
456  const auto & sExtNode = SExtOperation::create(64, mulNode.output(0));
457 
458  const auto & c0_2 = IntegerConstantOperation::Create(*theta->subregion(), 64, 0);
459  const auto gep =
460  GetElementPtrOperation::create(lv2.pre, { c0_2.output(0), sExtNode }, intArrayType);
461 
462  auto loadOutputs = LoadNonVolatileOperation::Create(gep, { memoryState.pre }, intType, 32);
463  auto & subNode =
464  jlm::rvsdg::CreateOpNode<IntegerSubOperation>({ loadOutputs[0], c2.output(0) }, 32);
465 
466  auto storeOutputs =
467  StoreNonVolatileOperation::Create(gep, subNode.output(0), { loadOutputs[1] }, 4);
468  const auto & c5 = IntegerConstantOperation::Create(*theta->subregion(), 32, 5);
469 
470  auto & sltNode =
471  jlm::rvsdg::CreateOpNode<IntegerSltOperation>({ addNode1.output(0), c5.output(0) }, 32);
472  const auto matchResult =
473  jlm::rvsdg::MatchOperation::Create(*sltNode.output(0), { { 1, 1 } }, 0, 2);
474 
475  lv1.post->divert_to(addNode1.output(0));
476  memoryState.post->divert_to(storeOutputs[0]);
477  theta->set_predicate(matchResult);
478 
479  jlm::rvsdg::GraphExport::Create(*memoryState.output, "");
480 
481  // std::cout << "Before: \n";
482  // jlm::rvsdg::view(graph, stdout);
483 
484  const auto numLoopVarsBefore = theta->GetLoopVars().size();
485 
486  std::vector<jlm::rvsdg::Input *> oldGepNodeUsers;
487 
488  // Act
489  RunLoopStrengthReduction(rvsdgModule);
490 
491  // std::cout << "After: \n";
492  // jlm::rvsdg::view(graph, stdout);
493 
494  const auto numLoopVarsAfter = theta->GetLoopVars().size();
495 
496  // Assert
497 
498  // Check that a new loop variable was added
499  EXPECT_EQ(numLoopVarsAfter, numLoopVarsBefore + 1);
500  auto newIV = theta->GetLoopVars()[numLoopVarsAfter - 1];
501 
502  // Check that the post value of the new IV comes from a new GEP node
503  const auto & IVPostOrigin =
504  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::SimpleNode>(*newIV.post->origin());
505  EXPECT_TRUE(jlm::rvsdg::is<GetElementPtrOperation>(IVPostOrigin->GetOperation()));
506  const auto & gepOperation =
507  dynamic_cast<const GetElementPtrOperation *>(&IVPostOrigin->GetOperation());
508  EXPECT_NE(gepOperation, nullptr);
509  // Check that it has the right type
510  EXPECT_EQ(gepOperation->getPointeeType(), *jlm::rvsdg::BitType::Create(8));
511  // Check that base address of the GEP is the pre value of the new IV
512  EXPECT_EQ(IVPostOrigin->input(0)->origin(), newIV.pre);
513  // Check that index of the GEP is an integer constant with the step value
514  const auto & gepIndexInputNode =
515  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::SimpleNode>(*IVPostOrigin->input(1)->origin());
516  EXPECT_TRUE(jlm::rvsdg::is<IntegerConstantOperation>(gepIndexInputNode));
517  const auto & constantOperation =
518  dynamic_cast<const IntegerConstantOperation *>(&gepIndexInputNode->GetOperation());
519  EXPECT_NE(constantOperation, nullptr);
520  EXPECT_EQ(constantOperation->Representation().nbits(), 64u);
521  EXPECT_EQ(constantOperation->Representation().to_uint(), 24u);
522 
523  // Check that the both the load and store nodes use the new induction variable as address
524  auto loadNode = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::SimpleNode>(*loadOutputs[0]);
525  EXPECT_NE(loadNode, nullptr);
526  EXPECT_TRUE(jlm::rvsdg::is<LoadNonVolatileOperation>(loadNode->GetOperation()));
527  EXPECT_EQ(LoadOperation::AddressInput(*loadNode).origin(), newIV.pre);
528 
529  auto storeNode = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::SimpleNode>(*storeOutputs[0]);
530  EXPECT_NE(storeNode, nullptr);
531  EXPECT_TRUE(jlm::rvsdg::is<StoreNonVolatileOperation>(storeNode->GetOperation()));
532  EXPECT_EQ(StoreOperation::AddressInput(*storeNode).origin(), newIV.pre);
533 }
534 
535 TEST(LoopStrengthReductionTests, GEPCandidateOperationWithNAryStart)
536 {
537  // Tests strength reduction of a GEP operation which takes j = (3 * i) + 4 as index. i has the
538  // recurrence {0,+,2} and j has recurrence {4,+,6}. Since the GEP has int type, the recurrence for
539  // the GEP is {(Init(a1) + 16),+,24}. We expect to strength reduce the original GEP to a new loop
540  // variable which has as input value a GEP operation with the ptr Init(a1) and 16 as offset,
541  // and is incremented by the value of a new GEP with byte type and offset 24
542  using namespace jlm::llvm;
543 
544  // Arrange
545  const auto intType = jlm::rvsdg::BitType::Create(32);
546  const auto intArrayType = ArrayType::Create(intType, 5);
547  const auto pointerType = PointerType::Create();
548  const auto memoryStateType = MemoryStateType::Create();
549 
550  LlvmRvsdgModule rvsdgModule(jlm::util::FilePath(""), "", "");
551  auto & graph = rvsdgModule.Rvsdg();
552 
553  auto arrPtr = &jlm::rvsdg::GraphImport::Create(graph, pointerType, "arrPtr");
554  auto mem = &jlm::rvsdg::GraphImport::Create(graph, memoryStateType, "");
555 
556  const auto & c0_1 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 0);
557  const auto & theta = jlm::rvsdg::ThetaNode::create(&graph.GetRootRegion());
558 
559  const auto memoryState = theta->AddLoopVar(mem);
560  const auto lv1 = theta->AddLoopVar(c0_1.output(0)); // i
561  const auto lv2 = theta->AddLoopVar(arrPtr); // arr ptr
562 
563  const auto & c2 = IntegerConstantOperation::Create(*theta->subregion(), 32, 2);
564  auto & addNode1 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv1.pre, c2.output(0) }, 32);
565 
566  const auto & c3 = IntegerConstantOperation::Create(*theta->subregion(), 32, 3);
567  auto & mulNode = jlm::rvsdg::CreateOpNode<IntegerMulOperation>({ lv1.pre, c3.output(0) }, 32);
568  const auto & c4 = IntegerConstantOperation::Create(*theta->subregion(), 32, 4);
569  auto & addNode2 =
570  jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ mulNode.output(0), c4.output(0) }, 32);
571 
572  const auto & sExtNode = SExtOperation::create(64, addNode2.output(0));
573 
574  const auto & c0_2 = IntegerConstantOperation::Create(*theta->subregion(), 64, 0);
575  const auto gep =
576  GetElementPtrOperation::create(lv2.pre, { c0_2.output(0), sExtNode }, intArrayType);
577 
578  const auto & c10 = IntegerConstantOperation::Create(*theta->subregion(), 32, 10);
579 
580  auto storeOutputs = StoreNonVolatileOperation::Create(gep, c10.output(0), { memoryState.pre }, 4);
581  const auto & c5 = IntegerConstantOperation::Create(*theta->subregion(), 32, 5);
582 
583  auto & sltNode =
584  jlm::rvsdg::CreateOpNode<IntegerSltOperation>({ addNode1.output(0), c5.output(0) }, 32);
585  const auto matchResult =
586  jlm::rvsdg::MatchOperation::Create(*sltNode.output(0), { { 1, 1 } }, 0, 2);
587 
588  lv1.post->divert_to(addNode1.output(0));
589  memoryState.post->divert_to(storeOutputs[0]);
590  theta->set_predicate(matchResult);
591 
592  jlm::rvsdg::GraphExport::Create(*memoryState.output, "");
593 
594  // std::cout << "Before: \n";
595  // jlm::rvsdg::view(graph, stdout);
596 
597  const auto numLoopVarsBefore = theta->GetLoopVars().size();
598 
599  std::vector<jlm::rvsdg::Input *> oldGepNodeUsers;
600 
601  // Act
602  RunLoopStrengthReduction(rvsdgModule);
603 
604  // std::cout << "After: \n";
605  // jlm::rvsdg::view(graph, stdout);
606 
607  const auto numLoopVarsAfter = theta->GetLoopVars().size();
608 
609  // Assert
610 
611  // Check that a new loop variable was added
612  EXPECT_EQ(numLoopVarsAfter, numLoopVarsBefore + 1);
613  auto newIV = theta->GetLoopVars()[numLoopVarsAfter - 1];
614 
615  // Check that the base address of the new induction variable is a GEP operation with the original
616  // array ptr as lhs and the right offset as rhs
617  const auto & newIVInputNode =
618  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::SimpleNode>(*newIV.input->origin());
619  EXPECT_TRUE(jlm::rvsdg::is<GetElementPtrOperation>(newIVInputNode->GetOperation()));
620  auto lhs = newIVInputNode->input(0)->origin();
621  auto rhs = newIVInputNode->input(1)->origin();
622  EXPECT_EQ(lhs, arrPtr);
623  const auto rhsNode = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::SimpleNode>(*rhs);
624  EXPECT_TRUE(jlm::rvsdg::is<IntegerConstantOperation>(rhsNode->GetOperation()));
625  const auto & constantOperation =
626  dynamic_cast<const IntegerConstantOperation *>(&rhsNode->GetOperation());
627  EXPECT_NE(constantOperation, nullptr);
628  EXPECT_EQ(constantOperation->Representation().to_uint(), 16u);
629 
630  // Check that the post value of the new IV comes from a new GEP node
631  const auto & IVPostOrigin =
632  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::SimpleNode>(*newIV.post->origin());
633  EXPECT_TRUE(jlm::rvsdg::is<GetElementPtrOperation>(IVPostOrigin->GetOperation()));
634  const auto & stepGepOperation =
635  dynamic_cast<const GetElementPtrOperation *>(&IVPostOrigin->GetOperation());
636  EXPECT_NE(stepGepOperation, nullptr);
637  // Check that it has the right type
638  EXPECT_EQ(stepGepOperation->getPointeeType(), *jlm::rvsdg::BitType::Create(8));
639 
640  // Check that index of the GEP is an integer constant with the step value
641  const auto & gepIndexInputNode =
642  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::SimpleNode>(*IVPostOrigin->input(1)->origin());
643  EXPECT_TRUE(jlm::rvsdg::is<IntegerConstantOperation>(gepIndexInputNode));
644  const auto & indexConstantOperation =
645  dynamic_cast<const IntegerConstantOperation *>(&gepIndexInputNode->GetOperation());
646  EXPECT_NE(indexConstantOperation, nullptr);
647  EXPECT_EQ(indexConstantOperation->Representation().nbits(), 64u);
648  EXPECT_EQ(indexConstantOperation->Representation().to_uint(), 24u);
649 
650  // Check that the both the load and store nodes use the new induction variable as address
651  auto storeNode = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::SimpleNode>(*storeOutputs[0]);
652  EXPECT_NE(storeNode, nullptr);
653  EXPECT_TRUE(jlm::rvsdg::is<StoreNonVolatileOperation>(storeNode->GetOperation()));
654  EXPECT_EQ(StoreOperation::AddressInput(*storeNode).origin(), newIV.pre);
655 }
656 
657 TEST(LoopStrengthReductionTests, CandidateOperationInNestedLoopTest)
658 {
659  // Tests strength reduction of a variable with the recurrence {{0,+,3}<1>}<2>. Since {0,+,3}<1> is
660  // invariant in the loop with ID 2, this is treated as a constant, and is hoisted into the loop
661  // "preheader", and used as the input value of a new loop variable.
662  using namespace jlm::llvm;
663 
664  // Arrange
665  const auto intType = jlm::rvsdg::BitType::Create(32);
666  const auto memoryStateType = MemoryStateType::Create();
667 
668  LlvmRvsdgModule rvsdgModule(jlm::util::FilePath(""), "", "");
669  auto & graph = rvsdgModule.Rvsdg();
670 
671  auto mem = &jlm::rvsdg::GraphImport::Create(graph, memoryStateType, "");
672 
673  const auto & c0 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 0);
674  const auto & theta1 = jlm::rvsdg::ThetaNode::create(&graph.GetRootRegion());
675 
676  const auto memoryState1 = theta1->AddLoopVar(mem);
677  const auto lv1_1 = theta1->AddLoopVar(c0.output(0)); // i
678 
679  const auto & c1 = IntegerConstantOperation::Create(*theta1->subregion(), 32, 1);
680  auto & addNode1 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv1_1.pre, c1.output(0) }, 32);
681 
682  const auto & c5 = IntegerConstantOperation::Create(*theta1->subregion(), 32, 5);
683  auto & sltNode1 =
684  jlm::rvsdg::CreateOpNode<IntegerSltOperation>({ addNode1.output(0), c5.output(0) }, 32);
685  const auto matchResult1 =
686  jlm::rvsdg::MatchOperation::Create(*sltNode1.output(0), { { 1, 1 } }, 0, 2);
687 
688  theta1->set_predicate(matchResult1);
689  lv1_1.post->divert_to(addNode1.output(0));
690 
691  const auto & theta2 = jlm::rvsdg::ThetaNode::create(theta1->subregion());
692 
693  const auto lv1_2 = theta2->AddLoopVar(lv1_1.pre); // i (but in inner loop)
694  const auto lv2 = theta2->AddLoopVar(c1.output(0)); // x
695  const auto memoryState2 = theta2->AddLoopVar(memoryState1.pre);
696 
697  const auto & c2 = IntegerConstantOperation::Create(*theta2->subregion(), 32, 2);
698  auto & addNode2 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv2.pre, c2.output(0) }, 32);
699 
700  const auto & c3 = IntegerConstantOperation::Create(*theta2->subregion(), 32, 3);
701  auto & mulNode = jlm::rvsdg::CreateOpNode<IntegerMulOperation>({ lv1_2.pre, c3.output(0) }, 32);
702 
703  const auto & c10 = IntegerConstantOperation::Create(*theta2->subregion(), 32, 10);
704  auto & sltNode2 =
705  jlm::rvsdg::CreateOpNode<IntegerSltOperation>({ addNode2.output(0), c10.output(0) }, 32);
706  const auto matchResult2 =
707  jlm::rvsdg::MatchOperation::Create(*sltNode2.output(0), { { 1, 1 } }, 0, 2);
708 
709  auto testOperation = jlm::rvsdg::TestOperation::createNode(
710  theta2->subregion(),
711  { mulNode.output(0), memoryState2.pre },
712  { memoryStateType });
713 
714  theta2->set_predicate(matchResult2);
715  lv2.post->divert_to(addNode2.output(0));
716  memoryState2.post->divert_to(testOperation->output(0));
717 
718  memoryState1.post->divert_to(memoryState2.output);
719  jlm::rvsdg::GraphExport::Create(*memoryState1.output, "");
720 
721  // std::cout << "Before: \n";
722  // jlm::rvsdg::view(graph, stdout);
723 
724  const auto outerNumLoopVarsBefore = theta1->GetLoopVars().size();
725  const auto innerNumLoopVarsBefore = theta2->GetLoopVars().size();
726 
727  // Act
728  RunLoopStrengthReduction(rvsdgModule);
729 
730  // std::cout << "After: \n";
731  // jlm::rvsdg::view(graph, stdout);
732 
733  const auto outerNumLoopVarsAfter = theta1->GetLoopVars().size();
734  const auto innerNumLoopVarsAfter = theta2->GetLoopVars().size();
735 
736  // Assert
737 
738  // Check that a new loop variable was added in both the inner and outer loop
739  EXPECT_EQ(outerNumLoopVarsAfter, outerNumLoopVarsBefore + 1);
740  EXPECT_EQ(innerNumLoopVarsAfter, innerNumLoopVarsBefore + 1);
741 
742  auto outerNewIV = theta1->GetLoopVars()[outerNumLoopVarsAfter - 1];
743  auto innerNewIV = theta2->GetLoopVars()[innerNumLoopVarsAfter - 1];
744 
745  // Check the start value
746  const auto & outerIVInputNode =
747  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::SimpleNode>(*outerNewIV.input->origin());
748  EXPECT_TRUE(jlm::rvsdg::is<IntegerConstantOperation>(outerIVInputNode->GetOperation()));
749  const auto & constantOperation =
750  dynamic_cast<const IntegerConstantOperation *>(&outerIVInputNode->GetOperation());
751  EXPECT_NE(constantOperation, nullptr);
752  EXPECT_EQ(constantOperation->Representation().to_uint(), 0u);
753 
754  // Check that the post value of the new IV comes from a new ADD node
755  const auto & outerIVPostOrigin =
756  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::SimpleNode>(*outerNewIV.post->origin());
757  EXPECT_TRUE(jlm::rvsdg::is<IntegerAddOperation>(outerIVPostOrigin->GetOperation()));
758  // Check that LHS of the ADD is the pre value of the new IV
759  EXPECT_EQ(outerIVPostOrigin->input(0)->origin(), outerNewIV.pre);
760  // Check that RHS of the ADD is an integer constant with the step value (3)
761  const auto & addRhsInputNode =
762  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::SimpleNode>(*outerIVPostOrigin->input(1)->origin());
763  EXPECT_TRUE(jlm::rvsdg::is<IntegerConstantOperation>(addRhsInputNode));
764  const auto & rhsConstantOperation =
765  dynamic_cast<const IntegerConstantOperation *>(&addRhsInputNode->GetOperation());
766  EXPECT_NE(rhsConstantOperation, nullptr);
767  EXPECT_EQ(rhsConstantOperation->Representation().to_uint(), 3u);
768 
769  // Check that the new inner induction variable uses the pre value of the outer IV as start value
770  EXPECT_EQ(innerNewIV.input->origin(), outerNewIV.pre);
771  // And that it is not modified in the inner loop
772  EXPECT_EQ(innerNewIV.post->origin(), innerNewIV.pre);
773 
774  // Check that the test operation now uses the new inner induction variable
775  EXPECT_EQ(testOperation->input(0)->origin(), innerNewIV.pre);
776 }
777 
778 TEST(LoopStrengthReductionTests, CandidateOperationInNestedLoopWithGammaTest)
779 {
780  // Does essentially the same as CandidateOperationInNestedLoopTest, but simulating the structure
781  // of a head-controlled loop. Meaning we have interchanging theta and gamma nodes. This means that
782  // the hoisted value must be routed down through from the outer loop to the inner loop.
783  using namespace jlm::llvm;
784 
785  // Arrange
786  const auto intType = jlm::rvsdg::BitType::Create(32);
787  const auto memoryStateType = MemoryStateType::Create();
788  const auto controlType = jlm::rvsdg::ControlType::Create(2);
789 
790  LlvmRvsdgModule rvsdgModule(jlm::util::FilePath(""), "", "");
791  auto & graph = rvsdgModule.Rvsdg();
792 
793  auto c = &jlm::rvsdg::GraphImport::Create(graph, controlType, "");
794  auto m = &jlm::rvsdg::GraphImport::Create(graph, memoryStateType, "");
795 
796  const auto gamma1 = jlm::rvsdg::GammaNode::create(c, 2);
797  const auto & c0 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 0);
798  auto ev1 = gamma1->AddEntryVar(c0.output(0));
799  auto mem1 = gamma1->AddEntryVar(m);
800 
801  const auto & theta1 = jlm::rvsdg::ThetaNode::create(gamma1->subregion(1));
802 
803  const auto memoryState1 = theta1->AddLoopVar(mem1.branchArgument[1]);
804  const auto lv1_1 = theta1->AddLoopVar(ev1.branchArgument[1]); // i
805 
806  const auto & c1 = IntegerConstantOperation::Create(*theta1->subregion(), 32, 1);
807  auto & addNode1 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv1_1.pre, c1.output(0) }, 32);
808 
809  const auto & c5 = IntegerConstantOperation::Create(*theta1->subregion(), 32, 5);
810  auto & sltNode1 =
811  jlm::rvsdg::CreateOpNode<IntegerSltOperation>({ addNode1.output(0), c5.output(0) }, 32);
812  const auto matchResult1 =
813  jlm::rvsdg::MatchOperation::Create(*sltNode1.output(0), { { 1, 1 } }, 0, 2);
814 
815  theta1->set_predicate(matchResult1);
816  lv1_1.post->divert_to(addNode1.output(0));
817 
818  const auto & c10 = IntegerConstantOperation::Create(*theta1->subregion(), 32, 10);
819  auto & sltNode2 =
820  jlm::rvsdg::CreateOpNode<IntegerSltOperation>({ c1.output(0), c10.output(0) }, 32);
821  const auto matchResult2 =
822  jlm::rvsdg::MatchOperation::Create(*sltNode2.output(0), { { 1, 1 } }, 0, 2);
823 
824  const auto & gamma2 = jlm::rvsdg::GammaNode::create(matchResult2, 2);
825  auto ev2 = gamma2->AddEntryVar(c1.output(0));
826  auto mem2 = gamma2->AddEntryVar(memoryState1.pre);
827  auto ev3 = gamma2->AddEntryVar(lv1_1.pre);
828 
829  const auto & theta2 = jlm::rvsdg::ThetaNode::create(gamma2->subregion(1));
830 
831  const auto lv2 = theta2->AddLoopVar(ev2.branchArgument[1]); // x
832  const auto lv1_2 = theta2->AddLoopVar(ev3.branchArgument[1]); // i (but in inner loop)
833  const auto memoryState2 = theta2->AddLoopVar(mem2.branchArgument[1]);
834 
835  const auto & c2 = IntegerConstantOperation::Create(*theta2->subregion(), 32, 2);
836  auto & addNode2 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv2.pre, c2.output(0) }, 32);
837 
838  const auto & c3 = IntegerConstantOperation::Create(*theta2->subregion(), 32, 3);
839  auto & mulNode = jlm::rvsdg::CreateOpNode<IntegerMulOperation>({ lv1_2.pre, c3.output(0) }, 32);
840 
841  const auto & c10_2 = IntegerConstantOperation::Create(*theta2->subregion(), 32, 10);
842  auto & sltNode3 =
843  jlm::rvsdg::CreateOpNode<IntegerSltOperation>({ addNode2.output(0), c10_2.output(0) }, 32);
844  const auto matchResult3 =
845  jlm::rvsdg::MatchOperation::Create(*sltNode3.output(0), { { 1, 1 } }, 0, 2);
846 
847  auto testOperation = jlm::rvsdg::TestOperation::createNode(
848  theta2->subregion(),
849  { mulNode.output(0), memoryState2.pre },
850  { memoryStateType });
851 
852  theta2->set_predicate(matchResult3);
853  lv2.post->divert_to(addNode2.output(0));
854  memoryState2.post->divert_to(testOperation->output(0));
855 
856  auto exitVar1 = gamma2->AddExitVar({ mem2.branchArgument[0], memoryState2.output });
857  memoryState1.post->divert_to(exitVar1.output);
858  auto exitVar2 = gamma1->AddExitVar({ mem1.branchArgument[0], memoryState1.output });
859 
860  jlm::rvsdg::GraphExport::Create(*exitVar2.output, "");
861 
862  // std::cout << "Before: \n";
863  // jlm::rvsdg::view(graph, stdout);
864 
865  const auto outerNumLoopVarsBefore = theta1->GetLoopVars().size();
866  const auto innerNumLoopVarsBefore = theta2->GetLoopVars().size();
867 
868  const auto outerNumEntryVarsBefore = gamma1->GetEntryVars().size();
869  const auto innerNumEntryVarsBefore = gamma2->GetEntryVars().size();
870 
871  // Act
872  RunLoopStrengthReduction(rvsdgModule);
873 
874  // std::cout << "After: \n";
875  // jlm::rvsdg::view(graph, stdout);
876 
877  const auto outerNumLoopVarsAfter = theta1->GetLoopVars().size();
878  const auto innerNumLoopVarsAfter = theta2->GetLoopVars().size();
879 
880  const auto outerNumEntryVarsAfter = gamma1->GetEntryVars().size();
881  const auto innerNumEntryVarsAfter = gamma2->GetEntryVars().size();
882 
883  // Assert
884 
885  // Check that a new loop variable was added in both the inner and outer loop
886  EXPECT_EQ(outerNumLoopVarsAfter, outerNumLoopVarsBefore + 1);
887  EXPECT_EQ(innerNumLoopVarsAfter, innerNumLoopVarsBefore + 1);
888 
889  // Check that a new entry variable was added in the inner gamma, but not in the outer gamma
890  EXPECT_EQ(innerNumEntryVarsAfter, innerNumEntryVarsBefore + 1);
891  EXPECT_EQ(outerNumEntryVarsAfter, outerNumEntryVarsBefore);
892 
893  auto outerNewIV = theta1->GetLoopVars()[outerNumLoopVarsAfter - 1];
894  auto innerNewIV = theta2->GetLoopVars()[innerNumLoopVarsAfter - 1];
895 
896  // Check the start value
897  const auto & outerIVInputNode =
898  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::SimpleNode>(*outerNewIV.input->origin());
899  EXPECT_TRUE(jlm::rvsdg::is<IntegerConstantOperation>(outerIVInputNode->GetOperation()));
900  const auto & constantOperation =
901  dynamic_cast<const IntegerConstantOperation *>(&outerIVInputNode->GetOperation());
902  EXPECT_NE(constantOperation, nullptr);
903  EXPECT_EQ(constantOperation->Representation().to_uint(), 0u);
904 
905  // Check that the post value of the new IV comes from a new ADD node
906  const auto & outerIVPostOrigin =
907  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::SimpleNode>(*outerNewIV.post->origin());
908  EXPECT_TRUE(jlm::rvsdg::is<IntegerAddOperation>(outerIVPostOrigin->GetOperation()));
909  // Check that LHS of the ADD is the pre value of the new IV
910  EXPECT_EQ(outerIVPostOrigin->input(0)->origin(), outerNewIV.pre);
911  // Check that RHS of the ADD is an integer constant with the step value (3)
912  const auto & addRhsInputNode =
913  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::SimpleNode>(*outerIVPostOrigin->input(1)->origin());
914  EXPECT_TRUE(jlm::rvsdg::is<IntegerConstantOperation>(addRhsInputNode));
915  const auto & rhsConstantOperation =
916  dynamic_cast<const IntegerConstantOperation *>(&addRhsInputNode->GetOperation());
917  EXPECT_NE(rhsConstantOperation, nullptr);
918  EXPECT_EQ(rhsConstantOperation->Representation().to_uint(), 3u);
919 
920  // Check that the new outer IV has been routed correctly through the gamma nodes
921  auto innerNewEV = gamma2->GetEntryVars()[innerNumEntryVarsAfter - 1];
922  // Check that the new entry variable has the pre value of the new IV as input
923  EXPECT_EQ(innerNewEV.input->origin(), outerNewIV.pre);
924 
925  // Check that the new inner IV has the branch argument of the new inner entry variable as input
926  EXPECT_EQ(innerNewIV.input->origin(), innerNewEV.branchArgument[1]);
927 
928  // Check that the new inner IV is not modified in the inner loop
929  EXPECT_EQ(innerNewIV.post->origin(), innerNewIV.pre);
930 
931  // Check that the test operation now uses the new inner induction variable
932  EXPECT_EQ(testOperation->input(0)->origin(), innerNewIV.pre);
933 }
934 
935 TEST(LoopStrengthReductionTests, CandidateOperationInThreeLevelNestedLoopTest)
936 {
937  // Similar to the previous two tests, but with one layer deeper of nesting. This test exists to
938  // ensure that the routing of hoisted variables functions correctly.
939  using namespace jlm::llvm;
940 
941  // Arrange
942  const auto intType = jlm::rvsdg::BitType::Create(32);
943  const auto memoryStateType = MemoryStateType::Create();
944 
945  LlvmRvsdgModule rvsdgModule(jlm::util::FilePath(""), "", "");
946  auto & graph = rvsdgModule.Rvsdg();
947 
948  auto mem = &jlm::rvsdg::GraphImport::Create(graph, memoryStateType, "");
949 
950  const auto & c0 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 0);
951  const auto & theta1 = jlm::rvsdg::ThetaNode::create(&graph.GetRootRegion());
952 
953  const auto memoryState1 = theta1->AddLoopVar(mem);
954  const auto lv1_1 = theta1->AddLoopVar(c0.output(0)); // i
955 
956  const auto & c1 = IntegerConstantOperation::Create(*theta1->subregion(), 32, 1);
957  auto & addNode1 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv1_1.pre, c1.output(0) }, 32);
958 
959  const auto & c5 = IntegerConstantOperation::Create(*theta1->subregion(), 32, 5);
960  auto & sltNode1 =
961  jlm::rvsdg::CreateOpNode<IntegerSltOperation>({ addNode1.output(0), c5.output(0) }, 32);
962  const auto matchResult1 =
963  jlm::rvsdg::MatchOperation::Create(*sltNode1.output(0), { { 1, 1 } }, 0, 2);
964 
965  theta1->set_predicate(matchResult1);
966  lv1_1.post->divert_to(addNode1.output(0));
967 
968  const auto & theta2 = jlm::rvsdg::ThetaNode::create(theta1->subregion());
969 
970  const auto lv1_2 = theta2->AddLoopVar(lv1_1.pre); // i (but in middle loop)
971  const auto lv2 = theta2->AddLoopVar(c1.output(0)); // x
972  const auto memoryState2 = theta2->AddLoopVar(memoryState1.pre);
973 
974  const auto & c2 = IntegerConstantOperation::Create(*theta2->subregion(), 32, 2);
975  auto & addNode2 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv2.pre, c2.output(0) }, 32);
976 
977  const auto & c10 = IntegerConstantOperation::Create(*theta2->subregion(), 32, 10);
978  auto & sltNode2 =
979  jlm::rvsdg::CreateOpNode<IntegerSltOperation>({ addNode2.output(0), c10.output(0) }, 32);
980  const auto matchResult2 =
981  jlm::rvsdg::MatchOperation::Create(*sltNode2.output(0), { { 1, 1 } }, 0, 2);
982 
983  theta2->set_predicate(matchResult2);
984  lv2.post->divert_to(addNode2.output(0));
985 
986  const auto & theta3 = jlm::rvsdg::ThetaNode::create(theta2->subregion());
987 
988  const auto lv1_3 = theta3->AddLoopVar(lv1_2.pre); // i (but in inner loop)
989  const auto lv3 = theta3->AddLoopVar(c2.output(0)); // y
990  const auto memoryState3 = theta3->AddLoopVar(memoryState2.pre);
991 
992  const auto & c4 = IntegerConstantOperation::Create(*theta3->subregion(), 32, 4);
993  auto & addNode3 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv3.pre, c4.output(0) }, 32);
994 
995  const auto & c3 = IntegerConstantOperation::Create(*theta3->subregion(), 32, 3);
996  auto & mulNode = jlm::rvsdg::CreateOpNode<IntegerMulOperation>({ lv1_3.pre, c3.output(0) }, 32);
997 
998  const auto & c20 = IntegerConstantOperation::Create(*theta3->subregion(), 32, 20);
999  auto & sltNode3 =
1000  jlm::rvsdg::CreateOpNode<IntegerSltOperation>({ addNode3.output(0), c20.output(0) }, 32);
1001  const auto matchResult3 =
1002  jlm::rvsdg::MatchOperation::Create(*sltNode3.output(0), { { 1, 1 } }, 0, 2);
1003 
1004  auto testOperation = jlm::rvsdg::TestOperation::createNode(
1005  theta3->subregion(),
1006  { mulNode.output(0), memoryState3.pre },
1007  { memoryStateType });
1008 
1009  theta3->set_predicate(matchResult3);
1010  lv3.post->divert_to(addNode3.output(0));
1011  memoryState3.post->divert_to(testOperation->output(0));
1012 
1013  lv1_2.post->divert_to(lv1_3.output);
1014  memoryState2.post->divert_to(memoryState3.output);
1015 
1016  memoryState1.post->divert_to(memoryState2.output);
1017  jlm::rvsdg::GraphExport::Create(*memoryState1.output, "");
1018 
1019  // std::cout << "Before: \n";
1020  // jlm::rvsdg::view(graph, stdout);
1021 
1022  const auto outerNumLoopVarsBefore = theta1->GetLoopVars().size();
1023  const auto middleNumLoopVarsBefore = theta2->GetLoopVars().size();
1024  const auto innerNumLoopVarsBefore = theta3->GetLoopVars().size();
1025 
1026  // Act
1027  RunLoopStrengthReduction(rvsdgModule);
1028 
1029  // std::cout << "After: \n";
1030  // jlm::rvsdg::view(graph, stdout);
1031 
1032  const auto outerNumLoopVarsAfter = theta1->GetLoopVars().size();
1033  const auto middleNumLoopVarsAfter = theta2->GetLoopVars().size();
1034  const auto innerNumLoopVarsAfter = theta3->GetLoopVars().size();
1035 
1036  // Assert
1037 
1038  // Check that a new loop variable was added in all three loops
1039  EXPECT_EQ(outerNumLoopVarsAfter, outerNumLoopVarsBefore + 1);
1040  EXPECT_EQ(middleNumLoopVarsAfter, middleNumLoopVarsBefore + 1);
1041  EXPECT_EQ(innerNumLoopVarsAfter, innerNumLoopVarsBefore + 1);
1042 
1043  auto outerNewIV = theta1->GetLoopVars()[outerNumLoopVarsAfter - 1];
1044  auto middleNewIV = theta2->GetLoopVars()[middleNumLoopVarsAfter - 1];
1045  auto innerNewIV = theta3->GetLoopVars()[innerNumLoopVarsAfter - 1];
1046 
1047  // Check the start value
1048  const auto & outerIVInputNode =
1049  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::SimpleNode>(*outerNewIV.input->origin());
1050  EXPECT_TRUE(jlm::rvsdg::is<IntegerConstantOperation>(outerIVInputNode->GetOperation()));
1051  const auto & constantOperation =
1052  dynamic_cast<const IntegerConstantOperation *>(&outerIVInputNode->GetOperation());
1053  EXPECT_NE(constantOperation, nullptr);
1054  EXPECT_EQ(constantOperation->Representation().to_uint(), 0u);
1055 
1056  // Check that the post value of the new IV comes from a new ADD node
1057  const auto & outerIVPostOrigin =
1058  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::SimpleNode>(*outerNewIV.post->origin());
1059  EXPECT_TRUE(jlm::rvsdg::is<IntegerAddOperation>(outerIVPostOrigin->GetOperation()));
1060  // Check that LHS of the ADD is the pre value of the new IV
1061  EXPECT_EQ(outerIVPostOrigin->input(0)->origin(), outerNewIV.pre);
1062  // Check that RHS of the ADD is an integer constant with the step value (3)
1063  const auto & addRhsInputNode =
1064  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::SimpleNode>(*outerIVPostOrigin->input(1)->origin());
1065  EXPECT_TRUE(jlm::rvsdg::is<IntegerConstantOperation>(addRhsInputNode));
1066  const auto & rhsConstantOperation =
1067  dynamic_cast<const IntegerConstantOperation *>(&addRhsInputNode->GetOperation());
1068  EXPECT_NE(rhsConstantOperation, nullptr);
1069  EXPECT_EQ(rhsConstantOperation->Representation().to_uint(), 3u);
1070 
1071  // Check that the new middle induction variable uses the pre value of the outer IV as start value
1072  EXPECT_EQ(middleNewIV.input->origin(), outerNewIV.pre);
1073  // And that it is not modified in the middle loop
1074  EXPECT_EQ(middleNewIV.post->origin(), middleNewIV.pre);
1075 
1076  // Check that the new inner induction variable uses the pre value of the middle IV as start value
1077  EXPECT_EQ(innerNewIV.input->origin(), middleNewIV.pre);
1078  // And that it is not modified in the inner loop
1079  EXPECT_EQ(innerNewIV.post->origin(), innerNewIV.pre);
1080 
1081  // Check that the test operation now uses the new inner induction variable
1082  EXPECT_EQ(testOperation->input(0)->origin(), innerNewIV.pre);
1083 }
1084 
1085 TEST(LoopStrengthReductionTests, CandidateOperationWithInitTest)
1086 {
1087  // Tests strength reduction of an operation with the following chrec:
1088  // {(Init(a1) * 3),+,(Init(a2) * 3)}<2>. In this example, we need to create new loop variables for
1089  // both the start value and the chrec, and add them together in the loop's subregion. This test
1090  // verifies that the hoisting of SCEV expressions functions correctly.
1091  using namespace jlm::llvm;
1092 
1093  // Arrange
1094  const auto intType = jlm::rvsdg::BitType::Create(32);
1095  const auto memoryStateType = MemoryStateType::Create();
1096 
1097  LlvmRvsdgModule rvsdgModule(jlm::util::FilePath(""), "", "");
1098  auto & graph = rvsdgModule.Rvsdg();
1099 
1100  auto mem = &jlm::rvsdg::GraphImport::Create(graph, memoryStateType, "");
1101  auto i = &jlm::rvsdg::GraphImport::Create(graph, intType, "i");
1102  auto k = &jlm::rvsdg::GraphImport::Create(graph, intType, "k");
1103 
1104  auto lambda = jlm::rvsdg::LambdaNode::Create(
1105  graph.GetRootRegion(),
1106  LlvmLambdaOperation::Create(
1107  jlm::rvsdg::FunctionType::Create({ intType, intType }, { memoryStateType }),
1108  "f",
1109  Linkage::externalLinkage));
1110  auto cv1 = lambda->AddContextVar(*mem).inner;
1111  auto cv2 = lambda->AddContextVar(*i).inner;
1112  auto cv3 = lambda->AddContextVar(*k).inner;
1113 
1114  const auto & theta = jlm::rvsdg::ThetaNode::create(lambda->subregion());
1115 
1116  const auto memoryState = theta->AddLoopVar(cv1); // memory state
1117  const auto lv1 = theta->AddLoopVar(cv2); // i
1118  const auto lv2 = theta->AddLoopVar(cv3); // k
1119 
1120  auto & addNode = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv1.pre, lv2.pre }, 32);
1121 
1122  const auto & c3 = IntegerConstantOperation::Create(*theta->subregion(), 32, 3);
1123  auto & mulNode = jlm::rvsdg::CreateOpNode<IntegerMulOperation>({ lv1.pre, c3.output(0) }, 32);
1124 
1125  auto testOperation = jlm::rvsdg::TestOperation::createNode(
1126  theta->subregion(),
1127  { mulNode.output(0), memoryState.pre },
1128  { memoryStateType });
1129 
1130  const auto & c5 = IntegerConstantOperation::Create(*theta->subregion(), 32, 5);
1131 
1132  auto & sltNode =
1133  jlm::rvsdg::CreateOpNode<IntegerSltOperation>({ addNode.output(0), c5.output(0) }, 32);
1134  const auto matchResult =
1135  jlm::rvsdg::MatchOperation::Create(*sltNode.output(0), { { 1, 1 } }, 0, 2);
1136 
1137  theta->set_predicate(matchResult);
1138  lv1.post->divert_to(addNode.output(0));
1139  memoryState.post->divert_to(testOperation->output(0));
1140 
1141  auto res = lambda->finalize({ memoryState.output });
1142 
1143  jlm::rvsdg::GraphExport::Create(*res, "");
1144 
1145  // std::cout << "Before: \n";
1146  // jlm::rvsdg::view(graph, stdout);
1147 
1148  const auto numLoopVarsBefore = theta->GetLoopVars().size();
1149 
1150  // Act
1151  RunLoopStrengthReduction(rvsdgModule);
1152 
1153  // std::cout << "After: \n";
1154  // jlm::rvsdg::view(graph, stdout);
1155 
1156  const auto numLoopVarsAfter = theta->GetLoopVars().size();
1157 
1158  // Assert
1159  // Check that two new loop variables were added
1160  EXPECT_EQ(numLoopVarsAfter, numLoopVarsBefore + 2);
1161 
1162  auto newIV1 = theta->GetLoopVars()[numLoopVarsAfter - 1];
1163  auto newIV2 = theta->GetLoopVars()[numLoopVarsAfter - 2];
1164 
1165  // We are checking that the input value of the first IV is the value of i times 3.
1166  // This corresponds with the start value of the chrec being (Init(a1) * 3)
1167  const auto & IV1InputNode =
1168  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::SimpleNode>(*newIV1.input->origin());
1169  EXPECT_TRUE(jlm::rvsdg::is<IntegerMulOperation>(IV1InputNode->GetOperation()));
1170  auto lhs1 = IV1InputNode->input(0)->origin();
1171  auto rhs1 = IV1InputNode->input(1)->origin();
1172  EXPECT_EQ(lhs1, cv2);
1173  const auto rhsNode = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::SimpleNode>(*rhs1);
1174  EXPECT_TRUE(jlm::rvsdg::is<IntegerConstantOperation>(rhsNode->GetOperation()));
1175  const auto & constantOperation =
1176  dynamic_cast<const IntegerConstantOperation *>(&rhsNode->GetOperation());
1177  EXPECT_NE(constantOperation, nullptr);
1178  EXPECT_EQ(constantOperation->Representation().to_uint(), 3u);
1179 
1180  // We are checking that the input value of the second IV is the value of k times 3.
1181  // This corresponds with the start value of the chrec being (Init(a2) * 3)
1182  const auto & IV2InputNode =
1183  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::SimpleNode>(*newIV2.input->origin());
1184  EXPECT_TRUE(jlm::rvsdg::is<IntegerMulOperation>(IV2InputNode->GetOperation()));
1185  auto lhs2 = IV2InputNode->input(0)->origin();
1186  auto rhs2 = IV2InputNode->input(1)->origin();
1187  EXPECT_EQ(lhs2, cv3);
1188  const auto rhsNode2 = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::SimpleNode>(*rhs2);
1189  EXPECT_TRUE(jlm::rvsdg::is<IntegerConstantOperation>(rhsNode2->GetOperation()));
1190  const auto & constantOperation2 =
1191  dynamic_cast<const IntegerConstantOperation *>(&rhsNode2->GetOperation());
1192  EXPECT_NE(constantOperation2, nullptr);
1193  EXPECT_EQ(constantOperation2->Representation().to_uint(), 3u);
1194 
1195  // Check that the post value of the new IV2 comes from a new ADD node
1196  const auto & IV1PostOrigin =
1197  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::SimpleNode>(*newIV1.post->origin());
1198  EXPECT_TRUE(jlm::rvsdg::is<IntegerAddOperation>(IV1PostOrigin->GetOperation()));
1199  // Check that LHS of the ADD is the pre value of the new IV1
1200  EXPECT_EQ(IV1PostOrigin->input(0)->origin(), newIV1.pre);
1201  // Check that RHS of the ADD is the pre value of the new IV2
1202  EXPECT_EQ(IV1PostOrigin->input(1)->origin(), newIV2.pre);
1203 
1204  // Check that the test operation now uses the new induction variable
1205  EXPECT_EQ(testOperation->input(0)->origin(), newIV1.pre);
1206 }
1207 
1208 TEST(LoopStrengthReductionTests, CandidateOperationWithInitAndTracingTest)
1209 {
1210  // In some cases, a recurrence from a higher level loop can be add-/mul-folded with a SCEV in
1211  // a loop that is at a lower level. In those cases, when hoisting the value, we need to trace the
1212  // output of the SCEV up to the corresponding output in the outermost loop's region.
1213 
1214  // Tests strength reduction of an operation with the following chrec:
1215  // {{(Init(a1) * 3),+,-1}<2>}<3>, where Init(a1) is in the loop with ID 3, which is at a lower
1216  // level than the recurrence it is in (loop with ID 2). In this example, we need to hoist the
1217  // recurrence {(Init(a1) * 3),+,-1}<2> which is invariant in the loop with ID 3. This is done by
1218  // creating a new induction variable in the outermost loop with (Init(a1) * 3) as the start value,
1219  // and which is decremented by 1 each iteration.
1220  using namespace jlm::llvm;
1221 
1222  // Arrange
1223  const auto intType = jlm::rvsdg::BitType::Create(32);
1224  const auto memoryStateType = MemoryStateType::Create();
1225 
1226  LlvmRvsdgModule rvsdgModule(jlm::util::FilePath(""), "", "");
1227  auto & graph = rvsdgModule.Rvsdg();
1228 
1229  auto mem = &jlm::rvsdg::GraphImport::Create(graph, memoryStateType, "");
1230  auto a = &jlm::rvsdg::GraphImport::Create(graph, intType, "a");
1231  auto lambda = jlm::rvsdg::LambdaNode::Create(
1232  graph.GetRootRegion(),
1233  LlvmLambdaOperation::Create(
1234  jlm::rvsdg::FunctionType::Create({ intType }, { memoryStateType }),
1235  "f",
1236  Linkage::externalLinkage));
1237  auto cv1 = lambda->AddContextVar(*mem).inner;
1238  auto cv2 = lambda->AddContextVar(*a).inner;
1239 
1240  const auto & c0 = IntegerConstantOperation::Create(*lambda->subregion(), 32, 0);
1241  const auto & theta1 = jlm::rvsdg::ThetaNode::create(lambda->subregion());
1242 
1243  const auto memoryState1 = theta1->AddLoopVar(cv1);
1244  const auto lv1_1 = theta1->AddLoopVar(c0.output(0)); // i
1245  const auto lv2_1 = theta1->AddLoopVar(cv2); // a
1246 
1247  const auto & c1 = IntegerConstantOperation::Create(*theta1->subregion(), 32, 1);
1248  auto & addNode1 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv1_1.pre, c1.output(0) }, 32);
1249 
1250  const auto & c5 = IntegerConstantOperation::Create(*theta1->subregion(), 32, 5);
1251  auto & sltNode1 =
1252  jlm::rvsdg::CreateOpNode<IntegerSltOperation>({ addNode1.output(0), c5.output(0) }, 32);
1253  const auto matchResult1 =
1254  jlm::rvsdg::MatchOperation::Create(*sltNode1.output(0), { { 1, 1 } }, 0, 2);
1255 
1256  theta1->set_predicate(matchResult1);
1257  lv1_1.post->divert_to(addNode1.output(0));
1258 
1259  const auto & theta2 = jlm::rvsdg::ThetaNode::create(theta1->subregion());
1260 
1261  const auto lv1_2 = theta2->AddLoopVar(lv1_1.pre); // i (but in inner loop)
1262  const auto lv2_2 = theta2->AddLoopVar(lv2_1.pre); // a (but in inner loop)
1263  const auto lv3 = theta2->AddLoopVar(c1.output(0)); // k
1264  const auto memoryState2 = theta2->AddLoopVar(memoryState1.pre);
1265 
1266  const auto & c2 = IntegerConstantOperation::Create(*theta2->subregion(), 32, 2);
1267  auto & addNode2 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv3.pre, c2.output(0) }, 32);
1268 
1269  const auto & c3 = IntegerConstantOperation::Create(*theta2->subregion(), 32, 3);
1270  auto & mulNode = jlm::rvsdg::CreateOpNode<IntegerMulOperation>({ lv2_2.pre, c3.output(0) }, 32);
1271 
1272  auto & subNode =
1273  jlm::rvsdg::CreateOpNode<IntegerSubOperation>({ mulNode.output(0), lv1_2.pre }, 32);
1274 
1275  const auto & c10 = IntegerConstantOperation::Create(*theta2->subregion(), 32, 10);
1276  auto & sltNode2 =
1277  jlm::rvsdg::CreateOpNode<IntegerSltOperation>({ addNode2.output(0), c10.output(0) }, 32);
1278  const auto matchResult2 =
1279  jlm::rvsdg::MatchOperation::Create(*sltNode2.output(0), { { 1, 1 } }, 0, 2);
1280 
1281  auto testOperation = jlm::rvsdg::TestOperation::createNode(
1282  theta2->subregion(),
1283  { subNode.output(0), memoryState2.pre },
1284  { memoryStateType });
1285 
1286  theta2->set_predicate(matchResult2);
1287  lv3.post->divert_to(addNode2.output(0));
1288  memoryState2.post->divert_to(testOperation->output(0));
1289 
1290  memoryState1.post->divert_to(memoryState2.output);
1291  auto res = lambda->finalize({ memoryState1.output });
1292  jlm::rvsdg::GraphExport::Create(*res, "");
1293 
1294  // std::cout << "Before: \n";
1295  // jlm::rvsdg::view(graph, stdout);
1296 
1297  const auto outerNumLoopVarsBefore = theta1->GetLoopVars().size();
1298  const auto innerNumLoopVarsBefore = theta2->GetLoopVars().size();
1299 
1300  // Act
1301  RunLoopStrengthReduction(rvsdgModule);
1302 
1303  // std::cout << "After: \n";
1304  // jlm::rvsdg::view(graph, stdout);
1305 
1306  const auto outerNumLoopVarsAfter = theta1->GetLoopVars().size();
1307  const auto innerNumLoopVarsAfter = theta2->GetLoopVars().size();
1308 
1309  // Assert
1310 
1311  // Check that a new loop variable was added in both the inner and outer loop
1312  EXPECT_EQ(outerNumLoopVarsAfter, outerNumLoopVarsBefore + 1);
1313  EXPECT_EQ(innerNumLoopVarsAfter, innerNumLoopVarsBefore + 1);
1314 
1315  auto outerNewIV = theta1->GetLoopVars()[outerNumLoopVarsAfter - 1];
1316  auto innerNewIV = theta2->GetLoopVars()[innerNumLoopVarsAfter - 1];
1317 
1318  // We are checking that the input value of the outer new IV is the value of a times 3.
1319  // This corresponds with the start value of the chrec being (Init(a1) * 3)
1320  const auto & outerIVInputNode =
1321  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::SimpleNode>(*outerNewIV.input->origin());
1322  EXPECT_TRUE(jlm::rvsdg::is<IntegerMulOperation>(outerIVInputNode->GetOperation()));
1323  auto lhs = outerIVInputNode->input(0)->origin();
1324  auto rhs = outerIVInputNode->input(1)->origin();
1325  EXPECT_EQ(lhs, cv2);
1326  const auto rhsNode = jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::SimpleNode>(*rhs);
1327  EXPECT_TRUE(jlm::rvsdg::is<IntegerConstantOperation>(rhsNode->GetOperation()));
1328  const auto & constantOperation =
1329  dynamic_cast<const IntegerConstantOperation *>(&rhsNode->GetOperation());
1330  EXPECT_EQ(constantOperation->Representation().to_uint(), 3u);
1331 
1332  // Check that the post value of the new IV comes from a new ADD node
1333  const auto & outerIVPostOrigin =
1334  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::SimpleNode>(*outerNewIV.post->origin());
1335  EXPECT_TRUE(jlm::rvsdg::is<IntegerAddOperation>(outerIVPostOrigin->GetOperation()));
1336  // Check that LHS of the ADD is the pre value of the new IV
1337  EXPECT_EQ(outerIVPostOrigin->input(0)->origin(), outerNewIV.pre);
1338  // Check that RHS of the ADD is an integer constant with the step value (-1)
1339  const auto & addRhsInputNode =
1340  jlm::rvsdg::TryGetOwnerNode<jlm::rvsdg::SimpleNode>(*outerIVPostOrigin->input(1)->origin());
1341  EXPECT_TRUE(jlm::rvsdg::is<IntegerConstantOperation>(addRhsInputNode));
1342  const auto & rhsConstantOperation =
1343  dynamic_cast<const IntegerConstantOperation *>(&addRhsInputNode->GetOperation());
1344  EXPECT_EQ(rhsConstantOperation->Representation().to_int(), -1);
1345 
1346  // Check that the new inner induction variable uses the pre value of the outer IV as start value
1347  EXPECT_EQ(innerNewIV.input->origin(), outerNewIV.pre);
1348  // And that it is not modified in the inner loop
1349  EXPECT_EQ(innerNewIV.post->origin(), innerNewIV.pre);
1350 
1351  // Check that the test operation now uses the new inner induction variable
1352  EXPECT_EQ(testOperation->input(0)->origin(), innerNewIV.pre);
1353 }
statisticsCollector
static jlm::util::StatisticsCollector statisticsCollector
Definition: CommonNodeEliminationTests.cpp:21
TEST
TEST(LoopStrengthReductionTests, SimpleArithmeticCandidateOperation)
Definition: LoopStrengthReductionTests.cpp:31
RunLoopStrengthReduction
void RunLoopStrengthReduction(jlm::rvsdg::RvsdgModule &rvsdgModule)
Definition: LoopStrengthReductionTests.cpp:24
jlm::llvm::ArrayType::Create
static std::shared_ptr< const ArrayType > Create(std::shared_ptr< const Type > type, size_t nelements)
Definition: types.hpp:98
jlm::llvm::GetElementPtrOperation::create
static rvsdg::Output * create(rvsdg::Output *baseAddress, const std::vector< rvsdg::Output * > &indices, std::shared_ptr< const rvsdg::Type > pointeeType)
Definition: GetElementPtr.hpp:195
jlm::llvm::IntegerConstantOperation::Create
static rvsdg::Node & Create(rvsdg::Region &region, IntegerValueRepresentation representation)
Definition: IntegerOperations.hpp:50
jlm::llvm::LlvmLambdaOperation::Create
static std::unique_ptr< LlvmLambdaOperation > Create(std::shared_ptr< const jlm::rvsdg::FunctionType > type, std::string name, const jlm::llvm::Linkage &linkage, jlm::llvm::CallingConvention callingConvention, jlm::llvm::AttributeSet attributes)
Definition: lambda.hpp:84
jlm::llvm::LoadNonVolatileOperation::Create
static std::unique_ptr< llvm::ThreeAddressCode > Create(const Variable *address, const Variable *state, std::shared_ptr< const rvsdg::Type > loadedType, size_t alignment)
Definition: Load.hpp:444
jlm::llvm::LoopStrengthReduction::Run
void Run(rvsdg::RvsdgModule &rvsdgModule, util::StatisticsCollector &statisticsCollector) override
Perform RVSDG transformation.
Definition: LoopStrengthReduction.cpp:129
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::llvm::SExtOperation::create
static std::unique_ptr< llvm::ThreeAddressCode > create(const Variable *operand, const std::shared_ptr< const rvsdg::Type > &type)
Definition: sext.hpp:75
jlm::llvm::StoreNonVolatileOperation::Create
static std::unique_ptr< llvm::ThreeAddressCode > Create(const Variable *address, const Variable *value, const Variable *state, size_t alignment)
Definition: Store.hpp:304
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::FunctionType::Create
static std::shared_ptr< const FunctionType > Create(std::vector< std::shared_ptr< const jlm::rvsdg::Type >> argumentTypes, std::vector< std::shared_ptr< const jlm::rvsdg::Type >> resultTypes)
Definition: FunctionType.cpp:115
jlm::rvsdg::GammaNode::create
static GammaNode * create(jlm::rvsdg::Output *predicate, size_t nalternatives)
Definition: gamma.hpp:161
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::LambdaNode::Create
static LambdaNode * Create(rvsdg::Region &parent, std::unique_ptr< LambdaOperation > operation)
Definition: lambda.cpp:140
jlm::rvsdg::MatchOperation::Create
static Output * Create(Output &predicate, const std::unordered_map< uint64_t, uint64_t > &mapping, const uint64_t defaultAlternative, const size_t numAlternatives)
Definition: control.hpp:242
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::ThetaNode::create
static ThetaNode * create(rvsdg::Region *parent)
Definition: theta.hpp:73
jlm::rvsdg::ThetaNode::AddLoopVar
LoopVar AddLoopVar(rvsdg::Output *origin)
Creates a new loop-carried variable.
Definition: theta.cpp:49
jlm::llvm
Global memory state passed between functions.
Definition: IpGraphToLlvmConverter.cpp:36
Generated by doxygen 1.9.1