Jlm
ScalarEvolutionTests.cpp
Go to the documentation of this file.
1 /*
2  * Copyright 2025 Andreas Lilleby Hjulstad <andreas.lilleby.hjulstad@gmail.com>
3  * See COPYING for terms of redistribution.
4  */
5 
6 #include <jlm/llvm/ir/operators/delta.hpp>
7 #include <jlm/llvm/ir/operators/GetElementPtr.hpp>
8 #include <jlm/llvm/ir/operators/IntegerOperations.hpp>
9 #include <jlm/llvm/ir/operators/lambda.hpp>
10 #include <jlm/llvm/ir/operators/Load.hpp>
11 #include <jlm/llvm/ir/operators/operators.hpp>
12 #include <jlm/llvm/ir/operators/sext.hpp>
13 #include <jlm/llvm/ir/RvsdgModule.hpp>
14 #include <jlm/llvm/opt/ScalarEvolution.hpp>
15 #include <jlm/rvsdg/view.hpp>
16 
17 #include <gtest/gtest.h>
18 
19 static std::pair<
20  std::unordered_map<const jlm::rvsdg::Output *, std::unique_ptr<jlm::llvm::SCEVChainRecurrence>>,
21  std::unordered_map<const jlm::rvsdg::ThetaNode *, size_t>>
22 RunScalarEvolution(jlm::rvsdg::RvsdgModule & rvsdgModule)
23 {
24  jlm::llvm::ScalarEvolution scalarEvolution;
25  jlm::util::StatisticsCollector statisticsCollector;
26  scalarEvolution.Run(rvsdgModule, statisticsCollector);
27  return { scalarEvolution.GetChrecMap(), scalarEvolution.GetTripCountMap() };
28 }
29 
30 TEST(ScalarEvolutionTests, NonEvolvingVariable)
31 {
32  using namespace jlm::llvm;
33 
34  // Arrange
35  const auto intType = jlm::rvsdg::BitType::Create(32);
36 
37  LlvmRvsdgModule rvsdgModule(jlm::util::FilePath(""), "", "");
38  const auto & graph = rvsdgModule.Rvsdg();
39 
40  const auto & c0 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 0);
41 
42  const auto theta = jlm::rvsdg::ThetaNode::create(&graph.GetRootRegion());
43  const auto lv1 = theta->AddLoopVar(c0.output(0));
44 
45  const auto & c1 = IntegerConstantOperation::Create(*theta->subregion(), 32, 1);
46 
47  lv1.post->divert_to(c1.output(0));
48 
49  const auto & c5 = IntegerConstantOperation::Create(*theta->subregion(), 32, 5);
50  auto & sltNode = jlm::rvsdg::CreateOpNode<IntegerSltOperation>({ lv1.pre, c5.output(0) }, 32);
51  const auto matchResult =
52  jlm::rvsdg::MatchOperation::Create(*sltNode.output(0), { { 1, 1 } }, 0, 2);
53 
54  theta->set_predicate(matchResult);
55 
56  jlm::rvsdg::view(graph, stdout);
57 
58  // Act
59  const auto & chrecMap = RunScalarEvolution(rvsdgModule).first;
60 
61  // Assert
62 
63  // Since lv1 is a variable which does not depend on the previous value (no evolution). There
64  // should be no computed chrec for it
65  EXPECT_EQ(chrecMap.find(lv1.pre), chrecMap.end());
66 }
67 
68 TEST(ScalarEvolutionTests, InductionVariable)
69 {
70  using namespace jlm::llvm;
71 
72  // Arrange
73  const auto intType = jlm::rvsdg::BitType::Create(32);
74 
75  LlvmRvsdgModule rvsdgModule(jlm::util::FilePath(""), "", "");
76  const auto & graph = rvsdgModule.Rvsdg();
77 
78  const auto & c0 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 0);
79  const auto & c2 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 2);
80 
81  const auto theta = jlm::rvsdg::ThetaNode::create(&graph.GetRootRegion());
82  const auto lv1 = theta->AddLoopVar(c0.output(0));
83  const auto lv2 = theta->AddLoopVar(c2.output(0));
84 
85  const auto & c1 = IntegerConstantOperation::Create(*theta->subregion(), 32, 1);
86  auto & addNode = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv1.pre, c1.output(0) }, 32);
87  const auto result = addNode.output(0);
88 
89  const auto & c5 = IntegerConstantOperation::Create(*theta->subregion(), 32, 5);
90  auto & sltNode = jlm::rvsdg::CreateOpNode<IntegerSltOperation>({ result, c5.output(0) }, 32);
91  const auto matchResult =
92  jlm::rvsdg::MatchOperation::Create(*sltNode.output(0), { { 1, 1 } }, 0, 2);
93 
94  theta->set_predicate(matchResult);
95  lv1.post->divert_to(result);
96 
97  jlm::rvsdg::view(graph, stdout);
98 
99  // Act
100  const auto & chrecMap = RunScalarEvolution(rvsdgModule).first;
101 
102  // Assert
103  EXPECT_NE(chrecMap.find(lv1.pre), chrecMap.end());
104  EXPECT_NE(chrecMap.find(lv2.pre), chrecMap.end());
105 
106  // lv1 is a simple induction variable with the recurrence {0,+,1}
107  auto lv1TestChrec = SCEVChainRecurrence(*theta, *lv1.pre);
108  lv1TestChrec.AddOperand(SCEVConstant::Create(0));
109  lv1TestChrec.AddOperand(SCEVConstant::Create(1));
110  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv1TestChrec, *chrecMap.at(lv1.pre)));
111 
112  // lv2 is a constant with the recurrence {2}
113  auto lv2TestChrec = SCEVChainRecurrence(*theta, *lv2.pre);
114  lv2TestChrec.AddOperand(SCEVConstant::Create(2));
115  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv2TestChrec, *chrecMap.at(lv2.pre)));
116 }
117 
118 TEST(ScalarEvolutionTests, RecursiveInductionVariable)
119 {
120  using namespace jlm::llvm;
121 
122  // Arrange
123  const auto intType = jlm::rvsdg::BitType::Create(32);
124 
125  LlvmRvsdgModule rvsdgModule(jlm::util::FilePath(""), "", "");
126  const auto & graph = rvsdgModule.Rvsdg();
127 
128  const auto & c0 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 0);
129  const auto & c4 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 4);
130 
131  const auto theta = jlm::rvsdg::ThetaNode::create(&graph.GetRootRegion());
132  const auto lv1 = theta->AddLoopVar(c0.output(0));
133  const auto lv2 = theta->AddLoopVar(c4.output(0));
134 
135  const auto & c1 = IntegerConstantOperation::Create(*theta->subregion(), 32, 1);
136  auto & addNode = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv1.pre, c1.output(0) }, 32);
137  const auto res1 = addNode.output(0);
138 
139  const auto & c5 = IntegerConstantOperation::Create(*theta->subregion(), 32, 5);
140  auto & sltNode = jlm::rvsdg::CreateOpNode<IntegerSltOperation>({ res1, c5.output(0) }, 32);
141  const auto matchResult =
142  jlm::rvsdg::MatchOperation::Create(*sltNode.output(0), { { 1, 1 } }, 0, 2);
143 
144  const auto & c2 = IntegerConstantOperation::Create(*theta->subregion(), 32, 2);
145  auto & addNode2 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv2.pre, c2.output(0) }, 32);
146  const auto res2 = addNode2.output(0);
147 
148  const auto & c3 = IntegerConstantOperation::Create(*theta->subregion(), 32, 3);
149  auto & addNode3 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ res2, c3.output(0) }, 32);
150  const auto res3 = addNode3.output(0);
151 
152  theta->set_predicate(matchResult);
153  lv1.post->divert_to(res1);
154  lv2.post->divert_to(res3);
155 
156  jlm::rvsdg::view(graph, stdout);
157 
158  // Act
159  const auto & chrecMap = RunScalarEvolution(rvsdgModule).first;
160 
161  // Assert
162  EXPECT_NE(chrecMap.find(lv1.pre), chrecMap.end());
163  EXPECT_NE(chrecMap.find(lv2.pre), chrecMap.end());
164 
165  // lv1 is a simple induction variable with the recurrence {0,+,1}
166  auto lv1TestChrec = SCEVChainRecurrence(*theta, *lv1.pre);
167  lv1TestChrec.AddOperand(SCEVConstant::Create(0));
168  lv1TestChrec.AddOperand(SCEVConstant::Create(1));
169  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv1TestChrec, *chrecMap.at(lv1.pre)));
170 
171  // lv2 is a recursive induction variable, which should be folded to {4,+,5}
172  auto lv2TestChrec = SCEVChainRecurrence(*theta, *lv2.pre);
173  lv2TestChrec.AddOperand(SCEVConstant::Create(4));
174  lv2TestChrec.AddOperand(SCEVConstant::Create(5));
175  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv2TestChrec, *chrecMap.at(lv2.pre)));
176 }
177 
178 TEST(ScalarEvolutionTests, PolynomialInductionVariable)
179 {
180  using namespace jlm::llvm;
181 
182  // Arrange
183  const auto intType = jlm::rvsdg::BitType::Create(32);
184 
185  LlvmRvsdgModule rvsdgModule(jlm::util::FilePath(""), "", "");
186  const auto & graph = rvsdgModule.Rvsdg();
187 
188  const auto & c0 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 0);
189  const auto & c2 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 2);
190 
191  const auto theta = jlm::rvsdg::ThetaNode::create(&graph.GetRootRegion());
192  const auto lv1 = theta->AddLoopVar(c0.output(0));
193  const auto lv2 = theta->AddLoopVar(c2.output(0));
194 
195  const auto & c1 = IntegerConstantOperation::Create(*theta->subregion(), 32, 1);
196  auto & addNode = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv1.pre, c1.output(0) }, 32);
197  const auto res1 = addNode.output(0);
198 
199  const auto & c5 = IntegerConstantOperation::Create(*theta->subregion(), 32, 5);
200  auto & sltNode = jlm::rvsdg::CreateOpNode<IntegerSltOperation>({ res1, c5.output(0) }, 32);
201  const auto matchResult =
202  jlm::rvsdg::MatchOperation::Create(*sltNode.output(0), { { 1, 1 } }, 0, 2);
203 
204  auto & addNode2 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv2.pre, res1 }, 32);
205  const auto res2 = addNode2.output(0);
206 
207  theta->set_predicate(matchResult);
208  lv1.post->divert_to(res1);
209  lv2.post->divert_to(res2);
210 
211  jlm::rvsdg::view(graph, stdout);
212 
213  // Act
214  const auto & chrecMap = RunScalarEvolution(rvsdgModule).first;
215 
216  // Assert
217  EXPECT_NE(chrecMap.find(lv1.pre), chrecMap.end());
218  EXPECT_NE(chrecMap.find(lv2.pre), chrecMap.end());
219 
220  // lv1 is a simple induction variable with the recurrence {0,+,1}
221  auto lv1TestChrec = SCEVChainRecurrence(*theta, *lv1.pre);
222  lv1TestChrec.AddOperand(SCEVConstant::Create(0));
223  lv1TestChrec.AddOperand(SCEVConstant::Create(1));
224  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv1TestChrec, *chrecMap.at(lv1.pre)));
225 
226  // lv2 is a (second degree) polynomial induction variable with three operands,
227  // Recurrence: {2,+,1,+,1}
228  auto lv2TestChrec = SCEVChainRecurrence(*theta, *lv2.pre);
229  lv2TestChrec.AddOperand(SCEVConstant::Create(2));
230  lv2TestChrec.AddOperand(SCEVConstant::Create(1));
231  lv2TestChrec.AddOperand(SCEVConstant::Create(1));
232  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv2TestChrec, *chrecMap.at(lv2.pre)));
233 }
234 
235 TEST(ScalarEvolutionTests, ThirdDegreePolynomialInductionVariable)
236 {
237  using namespace jlm::llvm;
238 
239  // Arrange
240  const auto intType = jlm::rvsdg::BitType::Create(32);
241 
242  LlvmRvsdgModule rvsdgModule(jlm::util::FilePath(""), "", "");
243  const auto & graph = rvsdgModule.Rvsdg();
244 
245  const auto & c2 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 2);
246  const auto & c3 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 3);
247  const auto & c4 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 4);
248 
249  const auto theta = jlm::rvsdg::ThetaNode::create(&graph.GetRootRegion());
250  const auto lv1 = theta->AddLoopVar(c2.output(0));
251  const auto lv2 = theta->AddLoopVar(c3.output(0));
252  const auto lv3 = theta->AddLoopVar(c4.output(0));
253 
254  const auto & c1 = IntegerConstantOperation::Create(*theta->subregion(), 32, 1);
255 
256  auto & addNode_1 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv1.pre, c1.output(0) }, 32);
257  const auto result_1 = addNode_1.output(0);
258 
259  auto & addNode_2 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv1.pre, lv2.pre }, 32);
260  const auto result_2 = addNode_2.output(0);
261 
262  auto & addNode_3 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv3.pre, lv2.pre }, 32);
263  const auto result_3 = addNode_3.output(0);
264 
265  const auto & c5 = IntegerConstantOperation::Create(*theta->subregion(), 32, 5);
266  auto & sltNode = jlm::rvsdg::CreateOpNode<IntegerSltOperation>({ result_1, c5.output(0) }, 32);
267  const auto matchResult =
268  jlm::rvsdg::MatchOperation::Create(*sltNode.output(0), { { 1, 1 } }, 0, 2);
269 
270  theta->set_predicate(matchResult);
271  lv1.post->divert_to(result_1);
272  lv2.post->divert_to(result_2);
273  lv3.post->divert_to(result_3);
274 
275  jlm::rvsdg::view(graph, stdout);
276 
277  // Act
278  const auto & chrecMap = RunScalarEvolution(rvsdgModule).first;
279 
280  // Assert
281  EXPECT_NE(chrecMap.find(lv1.pre), chrecMap.end());
282  EXPECT_NE(chrecMap.find(lv2.pre), chrecMap.end());
283  EXPECT_NE(chrecMap.find(lv3.pre), chrecMap.end());
284 
285  // lv1 is a simple induction variable with the recurrence {2,+,1}
286  auto lv1TestChrec = SCEVChainRecurrence(*theta, *lv1.pre);
287  lv1TestChrec.AddOperand(SCEVConstant::Create(2));
288  lv1TestChrec.AddOperand(SCEVConstant::Create(1));
289  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv1TestChrec, *chrecMap.at(lv1.pre)));
290 
291  // lv2 is a second degree polynomial induction variable with three operands, {3,+,2,+,1}
292  auto lv2TestChrec = SCEVChainRecurrence(*theta, *lv2.pre);
293  lv2TestChrec.AddOperand(SCEVConstant::Create(3));
294  lv2TestChrec.AddOperand(SCEVConstant::Create(2));
295  lv2TestChrec.AddOperand(SCEVConstant::Create(1));
296  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv2TestChrec, *chrecMap.at(lv2.pre)));
297 
298  // lv2 is a third degree polynomial induction variable with three operands,
299  // Recurrence: {4,+,3,+,2,+,1}
300  auto lv3TestChrec = SCEVChainRecurrence(*theta, *lv3.pre);
301  lv3TestChrec.AddOperand(SCEVConstant::Create(4));
302  lv3TestChrec.AddOperand(SCEVConstant::Create(3));
303  lv3TestChrec.AddOperand(SCEVConstant::Create(2));
304  lv3TestChrec.AddOperand(SCEVConstant::Create(1));
305  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv3TestChrec, *chrecMap.at(lv3.pre)));
306 }
307 
308 TEST(ScalarEvolutionTests, InductionVariableWithMultiplication)
309 {
310  using namespace jlm::llvm;
311 
312  // Arrange
313  const auto intType = jlm::rvsdg::BitType::Create(32);
314 
315  LlvmRvsdgModule rvsdgModule(jlm::util::FilePath(""), "", "");
316  const auto & graph = rvsdgModule.Rvsdg();
317 
318  const auto & c0 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 0);
319  const auto & c2 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 2);
320 
321  const auto theta = jlm::rvsdg::ThetaNode::create(&graph.GetRootRegion());
322  const auto lv1 = theta->AddLoopVar(c0.output(0));
323  const auto lv2 = theta->AddLoopVar(c2.output(0));
324 
325  const auto & c1 = IntegerConstantOperation::Create(*theta->subregion(), 32, 1);
326  auto & addNode1 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv1.pre, c1.output(0) }, 32);
327  auto res1 = addNode1.output(0);
328 
329  const auto & c3 = IntegerConstantOperation::Create(*theta->subregion(), 32, 3);
330  auto & mulNode = jlm::rvsdg::CreateOpNode<IntegerMulOperation>({ res1, c3.output(0) }, 32);
331 
332  auto & addNode2 =
333  jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv2.pre, mulNode.output(0) }, 32);
334  auto res2 = addNode2.output(0);
335 
336  const auto & c5 = IntegerConstantOperation::Create(*theta->subregion(), 32, 5);
337  auto & sltNode = jlm::rvsdg::CreateOpNode<IntegerSltOperation>({ res1, c5.output(0) }, 32);
338  const auto matchResult =
339  jlm::rvsdg::MatchOperation::Create(*sltNode.output(0), { { 1, 1 } }, 0, 2);
340 
341  theta->set_predicate(matchResult);
342  lv1.post->divert_to(res1);
343  lv2.post->divert_to(res2);
344 
345  jlm::rvsdg::view(graph, stdout);
346 
347  // Act
348  const auto & chrecMap = RunScalarEvolution(rvsdgModule).first;
349 
350  // Assert
351  EXPECT_NE(chrecMap.find(lv1.pre), chrecMap.end());
352  EXPECT_NE(chrecMap.find(lv2.pre), chrecMap.end());
353 
354  // lv1 is a simple induction variable with the recurrence {0,+,1}
355  auto lv1TestChrec = SCEVChainRecurrence(*theta, *lv1.pre);
356  lv1TestChrec.AddOperand(SCEVConstant::Create(0));
357  lv1TestChrec.AddOperand(SCEVConstant::Create(1));
358  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv1TestChrec, *chrecMap.at(lv1.pre)));
359 
360  // lv2 is incremented with 3 * {1,+,1} (lv1 + 1) each iteration. With the starting value of 2,
361  // this should give us the recurrence {2,+,3,+,3}
362  auto lv2TestChrec = SCEVChainRecurrence(*theta, *lv2.pre);
363  lv2TestChrec.AddOperand(SCEVConstant::Create(2));
364  lv2TestChrec.AddOperand(SCEVConstant::Create(3));
365  lv2TestChrec.AddOperand(SCEVConstant::Create(3));
366  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv2TestChrec, *chrecMap.at(lv2.pre)));
367 }
368 
369 TEST(ScalarEvolutionTests, InvalidInductionVariableWithMultiplication)
370 {
371  using namespace jlm::llvm;
372 
373  // Arrange
374  const auto intType = jlm::rvsdg::BitType::Create(32);
375 
376  LlvmRvsdgModule rvsdgModule(jlm::util::FilePath(""), "", "");
377  const auto & graph = rvsdgModule.Rvsdg();
378 
379  const auto & c1 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 1);
380 
381  const auto theta = jlm::rvsdg::ThetaNode::create(&graph.GetRootRegion());
382  const auto lv1 = theta->AddLoopVar(c1.output(0));
383 
384  const auto & c2 = IntegerConstantOperation::Create(*theta->subregion(), 32, 2);
385  auto & mulNode = jlm::rvsdg::CreateOpNode<IntegerMulOperation>({ lv1.pre, c2.output(0) }, 32);
386  const auto res1 = mulNode.output(0);
387 
388  const auto & c5 = IntegerConstantOperation::Create(*theta->subregion(), 32, 5);
389  auto & sltNode = jlm::rvsdg::CreateOpNode<IntegerSltOperation>({ res1, c5.output(0) }, 32);
390  const auto matchResult =
391  jlm::rvsdg::MatchOperation::Create(*sltNode.output(0), { { 1, 1 } }, 0, 2);
392 
393  theta->set_predicate(matchResult);
394  lv1.post->divert_to(res1);
395 
396  jlm::rvsdg::view(graph, stdout);
397 
398  // Act
399  const auto & chrecMap = RunScalarEvolution(rvsdgModule).first;
400 
401  // Assert
402  EXPECT_NE(chrecMap.find(lv1.pre), chrecMap.end());
403 
404  // lv1 is not an induction variable because of illegal mult operation
405  // (results in quadratic recurrence). It should therefore be modeled as {Unknown}
406  auto lv1TestChrec = SCEVChainRecurrence(*theta, *lv1.pre);
407  lv1TestChrec.AddOperand(SCEVUnknown::Create());
408  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv1TestChrec, *chrecMap.at(lv1.pre)));
409 }
410 
411 TEST(ScalarEvolutionTests, MultiplicationOfTwoAffineChrecs)
412 {
413  using namespace jlm::llvm;
414 
415  // Arrange
416  const auto intType = jlm::rvsdg::BitType::Create(32);
417 
418  LlvmRvsdgModule rvsdgModule(jlm::util::FilePath(""), "", "");
419  const auto & graph = rvsdgModule.Rvsdg();
420 
421  const auto & c0 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 0);
422  const auto & c3 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 3);
423 
424  const auto theta = jlm::rvsdg::ThetaNode::create(&graph.GetRootRegion());
425  const auto lv1 = theta->AddLoopVar(c0.output(0));
426  const auto lv2 = theta->AddLoopVar(c3.output(0));
427 
428  const auto & c1 = IntegerConstantOperation::Create(*theta->subregion(), 32, 1);
429  auto & addNode1 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv1.pre, c1.output(0) }, 32);
430  auto res1 = addNode1.output(0);
431 
432  auto & mulNode = jlm::rvsdg::CreateOpNode<IntegerMulOperation>({ lv1.pre, lv1.pre }, 32);
433 
434  auto & addNode2 =
435  jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv2.pre, mulNode.output(0) }, 32);
436  auto res2 = addNode2.output(0);
437 
438  const auto & c5 = IntegerConstantOperation::Create(*theta->subregion(), 32, 5);
439  auto & sltNode = jlm::rvsdg::CreateOpNode<IntegerSltOperation>({ res1, c5.output(0) }, 32);
440  const auto matchResult =
441  jlm::rvsdg::MatchOperation::Create(*sltNode.output(0), { { 1, 1 } }, 0, 2);
442 
443  theta->set_predicate(matchResult);
444  lv1.post->divert_to(res1);
445  lv2.post->divert_to(res2);
446 
447  jlm::rvsdg::view(graph, stdout);
448 
449  // Act
450  const auto & chrecMap = RunScalarEvolution(rvsdgModule).first;
451 
452  // Assert
453  EXPECT_NE(chrecMap.find(lv1.pre), chrecMap.end());
454  EXPECT_NE(chrecMap.find(lv2.pre), chrecMap.end());
455 
456  // lv1 is a simple induction variable with the recurrence {0,+,1}
457  auto lv1TestChrec = SCEVChainRecurrence(*theta, *lv1.pre);
458  lv1TestChrec.AddOperand(SCEVConstant::Create(0));
459  lv1TestChrec.AddOperand(SCEVConstant::Create(1));
460  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv1TestChrec, *chrecMap.at(lv1.pre)));
461 
462  // {0,+,1} * {0,+,1} folded together should be {0,+,1,+,2}, so adding this to lv2, should give us
463  // {3,+,0,+,1,+,2} as the recurrence for lv2
464  auto lv2TestChrec = SCEVChainRecurrence(*theta, *lv2.pre);
465  lv2TestChrec.AddOperand(SCEVConstant::Create(3));
466  lv2TestChrec.AddOperand(SCEVConstant::Create(0));
467  lv2TestChrec.AddOperand(SCEVConstant::Create(1));
468  lv2TestChrec.AddOperand(SCEVConstant::Create(2));
469  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv2TestChrec, *chrecMap.at(lv2.pre)));
470 }
471 
472 TEST(ScalarEvolutionTests, MultiplicationOfTwoQuadraticChrecs)
473 {
474  using namespace jlm::llvm;
475 
476  // Arrange
477  const auto intType = jlm::rvsdg::BitType::Create(32);
478 
479  LlvmRvsdgModule rvsdgModule(jlm::util::FilePath(""), "", "");
480  const auto & graph = rvsdgModule.Rvsdg();
481 
482  const auto & c0 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 0);
483  const auto & c1_1 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 1);
484  const auto & c2 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 2);
485 
486  const auto theta = jlm::rvsdg::ThetaNode::create(&graph.GetRootRegion());
487  const auto lv1 = theta->AddLoopVar(c0.output(0));
488  const auto lv2 = theta->AddLoopVar(c1_1.output(0));
489  const auto lv3 = theta->AddLoopVar(c2.output(0));
490 
491  const auto & c1_2 = IntegerConstantOperation::Create(*theta->subregion(), 32, 1);
492  auto & addNode1 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv1.pre, c1_2.output(0) }, 32);
493  auto res1 = addNode1.output(0);
494 
495  auto & addNode2 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv2.pre, lv1.pre }, 32);
496  auto res2 = addNode2.output(0);
497 
498  auto & mulNode = jlm::rvsdg::CreateOpNode<IntegerMulOperation>({ lv2.pre, lv2.pre }, 32);
499  auto & addNode3 =
500  jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv3.pre, mulNode.output(0) }, 32);
501  auto res3 = addNode3.output(0);
502 
503  const auto & c5 = IntegerConstantOperation::Create(*theta->subregion(), 32, 5);
504  auto & sltNode = jlm::rvsdg::CreateOpNode<IntegerSltOperation>({ res1, c5.output(0) }, 32);
505  const auto matchResult =
506  jlm::rvsdg::MatchOperation::Create(*sltNode.output(0), { { 1, 1 } }, 0, 2);
507 
508  theta->set_predicate(matchResult);
509  lv1.post->divert_to(res1);
510  lv2.post->divert_to(res2);
511  lv3.post->divert_to(res3);
512 
513  jlm::rvsdg::view(graph, stdout);
514 
515  // Act
516  const auto & chrecMap = RunScalarEvolution(rvsdgModule).first;
517 
518  // Assert
519  EXPECT_NE(chrecMap.find(lv1.pre), chrecMap.end());
520  EXPECT_NE(chrecMap.find(lv2.pre), chrecMap.end());
521  EXPECT_NE(chrecMap.find(lv3.pre), chrecMap.end());
522 
523  // lv1 is a simple induction variable with the affine recurrence {0,+,1}
524  auto lv1TestChrec = SCEVChainRecurrence(*theta, *lv1.pre);
525  lv1TestChrec.AddOperand(SCEVConstant::Create(0));
526  lv1TestChrec.AddOperand(SCEVConstant::Create(1));
527  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv1TestChrec, *chrecMap.at(lv1.pre)));
528 
529  // lv2 is a polynomial induction variable with the quadratic recurrence {1,+,0,+,1}
530  auto lv2TestChrec = SCEVChainRecurrence(*theta, *lv2.pre);
531  lv2TestChrec.AddOperand(SCEVConstant::Create(1));
532  lv2TestChrec.AddOperand(SCEVConstant::Create(0));
533  lv2TestChrec.AddOperand(SCEVConstant::Create(1));
534  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv2TestChrec, *chrecMap.at(lv2.pre)));
535 
536  // {1,+,0,+,1} * {1,+,0,+,1} foled together is {1,+,0,+,3,+,6,+,6}, adding that to lv3, we get the
537  // recurrence {2,+,1,+,0,+,3,+,6,+,6}
538  auto lv3TestChrec = SCEVChainRecurrence(*theta, *lv3.pre);
539  lv3TestChrec.AddOperand(SCEVConstant::Create(2));
540  lv3TestChrec.AddOperand(SCEVConstant::Create(1));
541  lv3TestChrec.AddOperand(SCEVConstant::Create(0));
542  lv3TestChrec.AddOperand(SCEVConstant::Create(3));
543  lv3TestChrec.AddOperand(SCEVConstant::Create(6));
544  lv3TestChrec.AddOperand(SCEVConstant::Create(6));
545  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv3TestChrec, *chrecMap.at(lv3.pre)));
546 }
547 
548 TEST(ScalarEvolutionTests, InvalidPolynomialInductionVariableWithMultiplication)
549 {
550  using namespace jlm::llvm;
551 
552  // Arrange
553  const auto intType = jlm::rvsdg::BitType::Create(32);
554 
555  LlvmRvsdgModule rvsdgModule(jlm::util::FilePath(""), "", "");
556  const auto & graph = rvsdgModule.Rvsdg();
557 
558  const auto & c0 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 0);
559  const auto & c3 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 3);
560 
561  const auto theta = jlm::rvsdg::ThetaNode::create(&graph.GetRootRegion());
562  const auto lv1 = theta->AddLoopVar(c0.output(0));
563  const auto lv2 = theta->AddLoopVar(c3.output(0));
564 
565  const auto & c1 = IntegerConstantOperation::Create(*theta->subregion(), 32, 1);
566  auto & addNode1 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv1.pre, c1.output(0) }, 32);
567  auto res1 = addNode1.output(0);
568 
569  const auto & c2 = IntegerConstantOperation::Create(*theta->subregion(), 32, 1);
570  auto & addNode2 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv1.pre, c2.output(0) }, 32);
571  auto & mulNode =
572  jlm::rvsdg::CreateOpNode<IntegerMulOperation>({ lv2.pre, addNode2.output(0) }, 32);
573  const auto res2 = mulNode.output(0);
574 
575  const auto & c5 = IntegerConstantOperation::Create(*theta->subregion(), 32, 5);
576  auto & sltNode = jlm::rvsdg::CreateOpNode<IntegerSltOperation>({ res1, c5.output(0) }, 32);
577  const auto matchResult =
578  jlm::rvsdg::MatchOperation::Create(*sltNode.output(0), { { 1, 1 } }, 0, 2);
579 
580  theta->set_predicate(matchResult);
581  lv1.post->divert_to(res1);
582  lv2.post->divert_to(res2);
583 
584  jlm::rvsdg::view(graph, stdout);
585 
586  // Act
587  const auto & chrecMap = RunScalarEvolution(rvsdgModule).first;
588 
589  // Assert
590  EXPECT_NE(chrecMap.find(lv1.pre), chrecMap.end());
591  EXPECT_NE(chrecMap.find(lv2.pre), chrecMap.end());
592 
593  // lv1 is a simple induction variable with the recurrence {0,+,1}
594  auto lv1TestChrec = SCEVChainRecurrence(*theta, *lv1.pre);
595  lv1TestChrec.AddOperand(SCEVConstant::Create(0));
596  lv1TestChrec.AddOperand(SCEVConstant::Create(1));
597  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv1TestChrec, *chrecMap.at(lv1.pre)));
598 
599  // lv2 is not an induction variable because of illegal mult operation
600  // (results in quadratic recurrence). It should therefore be modeled as {Unknown}
601  auto lv2TestChrec = SCEVChainRecurrence(*theta, *lv2.pre);
602  lv2TestChrec.AddOperand(SCEVUnknown::Create());
603  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv2TestChrec, *chrecMap.at(lv2.pre)));
604 }
605 
606 TEST(ScalarEvolutionTests, InductionVariableWithSubtraction)
607 {
608  using namespace jlm::llvm;
609 
610  // Arrange
611  const auto intType = jlm::rvsdg::BitType::Create(32);
612 
613  LlvmRvsdgModule rvsdgModule(jlm::util::FilePath(""), "", "");
614  const auto & graph = rvsdgModule.Rvsdg();
615 
616  const auto & c10 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 10);
617 
618  const auto theta = jlm::rvsdg::ThetaNode::create(&graph.GetRootRegion());
619  const auto lv1 = theta->AddLoopVar(c10.output(0));
620 
621  const auto & c1 = IntegerConstantOperation::Create(*theta->subregion(), 32, 1);
622 
623  auto & subNode = jlm::rvsdg::CreateOpNode<IntegerSubOperation>({ lv1.pre, c1.output(0) }, 32);
624  const auto & res1 = subNode.output(0);
625 
626  const auto & c5 = IntegerConstantOperation::Create(*theta->subregion(), 32, 5);
627  auto & sltNode = jlm::rvsdg::CreateOpNode<IntegerSgtOperation>({ res1, c5.output(0) }, 32);
628  const auto matchResult =
629  jlm::rvsdg::MatchOperation::Create(*sltNode.output(0), { { 1, 1 } }, 0, 2);
630 
631  theta->set_predicate(matchResult);
632  lv1.post->divert_to(res1);
633 
634  jlm::rvsdg::view(graph, stdout);
635 
636  // Act
637  const auto & chrecMap = RunScalarEvolution(rvsdgModule).first;
638 
639  // Assert
640  EXPECT_NE(chrecMap.find(lv1.pre), chrecMap.end());
641 
642  // lv1 is a simple negative induction variable with the recurrence {10,+,-1}
643  auto lv1TestChrec = SCEVChainRecurrence(*theta, *lv1.pre);
644  lv1TestChrec.AddOperand(SCEVConstant::Create(10));
645  lv1TestChrec.AddOperand(SCEVConstant::Create(-1));
646  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv1TestChrec, *chrecMap.at(lv1.pre)));
647 }
648 
649 TEST(ScalarEvolutionTests, PolynomialInductionVariableWithSubtraction)
650 {
651  using namespace jlm::llvm;
652 
653  // Arrange
654  const auto intType = jlm::rvsdg::BitType::Create(32);
655 
656  LlvmRvsdgModule rvsdgModule(jlm::util::FilePath(""), "", "");
657  const auto & graph = rvsdgModule.Rvsdg();
658 
659  const auto & c0 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 0);
660  const auto & c3 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 3);
661 
662  const auto theta = jlm::rvsdg::ThetaNode::create(&graph.GetRootRegion());
663  const auto lv1 = theta->AddLoopVar(c0.output(0));
664  const auto lv2 = theta->AddLoopVar(c3.output(0));
665 
666  const auto & c1 = IntegerConstantOperation::Create(*theta->subregion(), 32, 1);
667  auto & addNode = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv1.pre, c1.output(0) }, 32);
668  const auto res1 = addNode.output(0);
669 
670  auto & subNode = jlm::rvsdg::CreateOpNode<IntegerSubOperation>({ lv2.pre, res1 }, 32);
671  const auto res2 = subNode.output(0);
672 
673  const auto & c5 = IntegerConstantOperation::Create(*theta->subregion(), 32, 5);
674  auto & sltNode = jlm::rvsdg::CreateOpNode<IntegerSltOperation>({ res1, c5.output(0) }, 32);
675  const auto matchResult =
676  jlm::rvsdg::MatchOperation::Create(*sltNode.output(0), { { 1, 1 } }, 0, 2);
677 
678  theta->set_predicate(matchResult);
679  lv1.post->divert_to(res1);
680  lv2.post->divert_to(res2);
681 
682  jlm::rvsdg::view(graph, stdout);
683 
684  // Act
685  const auto & chrecMap = RunScalarEvolution(rvsdgModule).first;
686 
687  // Assert
688  EXPECT_NE(chrecMap.find(lv1.pre), chrecMap.end());
689  EXPECT_NE(chrecMap.find(lv2.pre), chrecMap.end());
690 
691  // lv1 is a simple induction variable with the recurrence {0,+,1}
692  auto lv1TestChrec = SCEVChainRecurrence(*theta, *lv1.pre);
693  lv1TestChrec.AddOperand(SCEVConstant::Create(0));
694  lv1TestChrec.AddOperand(SCEVConstant::Create(1));
695  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv1TestChrec, *chrecMap.at(lv1.pre)));
696 
697  // lv2 is decremented with {1,+,1} every iteration (lv1 + 1), and has a start value of 3, this
698  // results in the recurrence {3,+,-1,+,-1}
699  auto lv2TestChrec = SCEVChainRecurrence(*theta, *lv2.pre);
700  lv2TestChrec.AddOperand(SCEVConstant::Create(3));
701  lv2TestChrec.AddOperand(SCEVConstant::Create(-1));
702  lv2TestChrec.AddOperand(SCEVConstant::Create(-1));
703  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv2TestChrec, *chrecMap.at(lv2.pre)));
704 }
705 
706 TEST(ScalarEvolutionTests, InductionVariablesWithNonConstantInitialValues)
707 {
708  // This test checks the functionality of the folding rules for variables that have start values
709  // that are not constants. These will get a SCEVInit node instead, which cannot be folded like a
710  // constant.
711  using namespace jlm::llvm;
712 
713  // Arrange
714  const auto intType = jlm::rvsdg::BitType::Create(32);
715 
716  LlvmRvsdgModule rvsdgModule(jlm::util::FilePath(""), "", "");
717  jlm::rvsdg::Graph & graph = rvsdgModule.Rvsdg();
718 
719  auto x = &jlm::rvsdg::GraphImport::Create(graph, intType, "x");
720  auto y = &jlm::rvsdg::GraphImport::Create(graph, intType, "y");
721  auto z = &jlm::rvsdg::GraphImport::Create(graph, intType, "z");
722  auto w = &jlm::rvsdg::GraphImport::Create(graph, intType, "w");
723  auto lambda = jlm::rvsdg::LambdaNode::Create(
724  graph.GetRootRegion(),
725  LlvmLambdaOperation::Create(
726  jlm::rvsdg::FunctionType::Create({ intType }, { intType }),
727  "f",
728  Linkage::externalLinkage));
729 
730  // We wrap the theta in a lambda node to get init nodes in the SCEV tree
731 
732  auto cv1 = lambda->AddContextVar(*x).inner;
733  auto cv2 = lambda->AddContextVar(*y).inner;
734  auto cv3 = lambda->AddContextVar(*z).inner;
735  auto cv4 = lambda->AddContextVar(*w).inner;
736 
737  const auto theta = jlm::rvsdg::ThetaNode::create(lambda->subregion());
738  auto lv1 = theta->AddLoopVar(cv1);
739  auto lv2 = theta->AddLoopVar(cv2);
740  auto lv3 = theta->AddLoopVar(cv3);
741  auto lv4 = theta->AddLoopVar(cv4);
742 
743  auto & addNode1 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv2.pre, lv1.pre }, 32);
744  const auto res1 = addNode1.output(0);
745 
746  auto & addNode2 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv3.pre, res1 }, 32);
747  const auto res2 = addNode2.output(0);
748 
749  auto & addNode3 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ res2, res1 }, 32);
750  const auto res3 = addNode3.output(0);
751 
752  auto & addNode4 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv4.pre, res3 }, 32);
753  const auto res4 = addNode4.output(0);
754 
755  const auto & c5 = IntegerConstantOperation::Create(*theta->subregion(), 32, 5);
756  auto & sltNode = jlm::rvsdg::CreateOpNode<IntegerSltOperation>({ res1, c5.output(0) }, 32);
757  const auto matchResult =
758  jlm::rvsdg::MatchOperation::Create(*sltNode.output(0), { { 1, 1 } }, 0, 2);
759 
760  theta->set_predicate(matchResult);
761  lv2.post->divert_to(res1);
762  lv3.post->divert_to(res2);
763  lv4.post->divert_to(res4);
764 
765  jlm::rvsdg::view(graph, stdout);
766 
767  // Act
768  const auto & chrecMap = RunScalarEvolution(rvsdgModule).first;
769 
770  // Assert
771  EXPECT_NE(chrecMap.find(lv1.pre), chrecMap.end());
772  EXPECT_NE(chrecMap.find(lv2.pre), chrecMap.end());
773  EXPECT_NE(chrecMap.find(lv3.pre), chrecMap.end());
774  EXPECT_NE(chrecMap.find(lv4.pre), chrecMap.end());
775 
776  // lv1 is a trivial (constant) induction variable.
777  // Recurrence: {Init(a0)}
778  auto lv1TestChrec = SCEVChainRecurrence(*theta, *lv1.pre);
779  lv1TestChrec.AddOperand(SCEVInit::Create(*lv1.pre));
780  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv1TestChrec, *chrecMap.at(lv1.pre)));
781 
782  // lv2 is a general induction variable which is incremented by the value of lv1 for each
783  // iteration.
784  // Recurrence: {Init(a1),+,Init(a0)}
785  auto lv2TestChrec = SCEVChainRecurrence(*theta, *lv2.pre);
786  lv2TestChrec.AddOperand(SCEVInit::Create(*lv2.pre));
787  lv2TestChrec.AddOperand(SCEVInit::Create(*lv1.pre));
788  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv2TestChrec, *chrecMap.at(lv2.pre)));
789 
790  // Tests that two init nodes folded together creates an NAryAdd expression
791  // Recurrence: {Init(a2),+,(Init(a1) + Init(a0)),+,Init(a0)}
792  auto lv3TestChrec = SCEVChainRecurrence(*theta, *lv3.pre);
793  lv3TestChrec.AddOperand(SCEVInit::Create(*lv3.pre));
794  lv3TestChrec.AddOperand(
795  SCEVNAryAddExpr::Create(SCEVInit::Create(*lv2.pre), SCEVInit::Create(*lv1.pre)));
796  lv3TestChrec.AddOperand(SCEVInit::Create(*lv1.pre));
797  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv3TestChrec, *chrecMap.at(lv3.pre)));
798 
799  // Tests that when two NAryAdd expressions are folded together, the operands of the RHS add is
800  // added to the LHS add
801  // Recurrence: {Init(a3),+,(Init(a1) + Init(a0) + Init(a2) + Init(a1) + Init(a0)),+,(Init(a1) +
802  // Init(a0) + Init(a0) + Init(a0)),+,Init(a0)}
803  auto lv4TestChrec = SCEVChainRecurrence(*theta, *lv4.pre);
804  lv4TestChrec.AddOperand(SCEVInit::Create(*lv4.pre));
805  lv4TestChrec.AddOperand(SCEVNAryAddExpr::Create(
806  SCEVInit::Create(*lv2.pre),
807  SCEVInit::Create(*lv1.pre),
808  SCEVInit::Create(*lv3.pre),
809  SCEVInit::Create(*lv2.pre),
810  SCEVInit::Create(*lv1.pre)));
811  lv4TestChrec.AddOperand(SCEVNAryAddExpr::Create(
812  SCEVInit::Create(*lv2.pre),
813  SCEVInit::Create(*lv1.pre),
814  SCEVInit::Create(*lv1.pre),
815  SCEVInit::Create(*lv1.pre)));
816  lv4TestChrec.AddOperand(SCEVInit::Create(*lv1.pre));
817  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv4TestChrec, *chrecMap.at(lv4.pre)));
818 }
819 
820 TEST(ScalarEvolutionTests, InductionVariablesWithNonConstantInitialValuesAndMultiplication)
821 {
822  using namespace jlm::llvm;
823 
824  // Arrange
825  const auto intType = jlm::rvsdg::BitType::Create(32);
826 
827  LlvmRvsdgModule rvsdgModule(jlm::util::FilePath(""), "", "");
828  jlm::rvsdg::Graph & graph = rvsdgModule.Rvsdg();
829 
830  auto x = &jlm::rvsdg::GraphImport::Create(graph, intType, "x");
831  auto y = &jlm::rvsdg::GraphImport::Create(graph, intType, "y");
832  auto z = &jlm::rvsdg::GraphImport::Create(graph, intType, "z");
833  auto w = &jlm::rvsdg::GraphImport::Create(graph, intType, "w");
834  auto lambda = jlm::rvsdg::LambdaNode::Create(
835  graph.GetRootRegion(),
836  LlvmLambdaOperation::Create(
837  jlm::rvsdg::FunctionType::Create({ intType }, { intType }),
838  "f",
839  Linkage::externalLinkage));
840 
841  auto cv1 = lambda->AddContextVar(*x).inner;
842  auto cv2 = lambda->AddContextVar(*y).inner;
843  auto cv3 = lambda->AddContextVar(*z).inner;
844  auto cv4 = lambda->AddContextVar(*w).inner;
845 
846  const auto theta = jlm::rvsdg::ThetaNode::create(lambda->subregion());
847  auto lv1 = theta->AddLoopVar(cv1);
848  auto lv2 = theta->AddLoopVar(cv2);
849  auto lv3 = theta->AddLoopVar(cv3);
850  auto lv4 = theta->AddLoopVar(cv4);
851 
852  const auto & c1 = IntegerConstantOperation::Create(*theta->subregion(), 32, 1);
853  auto & addNode1 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv2.pre, c1.output(0) }, 32);
854  const auto res1 = addNode1.output(0);
855 
856  auto & mulNode1 = jlm::rvsdg::CreateOpNode<IntegerMulOperation>({ lv1.pre, lv2.pre }, 32);
857  const auto res2 = mulNode1.output(0);
858 
859  auto & addNode2 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv3.pre, res2 }, 32);
860  const auto res3 = addNode2.output(0);
861 
862  auto & mulNode2 = jlm::rvsdg::CreateOpNode<IntegerMulOperation>({ res2, res2 }, 32);
863 
864  auto & addNode3 =
865  jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv4.pre, mulNode2.output(0) }, 32);
866  const auto res4 = addNode3.output(0);
867 
868  const auto & c5 = IntegerConstantOperation::Create(*theta->subregion(), 32, 5);
869  auto & sltNode = jlm::rvsdg::CreateOpNode<IntegerSltOperation>({ res1, c5.output(0) }, 32);
870  const auto matchResult =
871  jlm::rvsdg::MatchOperation::Create(*sltNode.output(0), { { 1, 1 } }, 0, 2);
872 
873  theta->set_predicate(matchResult);
874  lv2.post->divert_to(res1);
875  lv3.post->divert_to(res3);
876  lv4.post->divert_to(res4);
877 
878  jlm::rvsdg::view(graph, stdout);
879 
880  // Act
881  const auto & chrecMap = RunScalarEvolution(rvsdgModule).first;
882 
883  // Assert
884  EXPECT_NE(chrecMap.find(lv1.pre), chrecMap.end());
885  EXPECT_NE(chrecMap.find(lv2.pre), chrecMap.end());
886  EXPECT_NE(chrecMap.find(lv3.pre), chrecMap.end());
887  EXPECT_NE(chrecMap.find(lv4.pre), chrecMap.end());
888 
889  // lv1 is a trivial (constant) induction variable.
890  // Recurrence: {Init(a0)}
891  auto lv1TestChrec = SCEVChainRecurrence(*theta, *lv1.pre);
892  lv1TestChrec.AddOperand(SCEVInit::Create(*lv1.pre));
893  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv1TestChrec, *chrecMap.at(lv1.pre)));
894 
895  // lv2 is a general induction variable which is incremented by 1 each iteration.
896  // Recurrence: {Init(a1),+,1}
897  auto lv2TestChrec = SCEVChainRecurrence(*theta, *lv2.pre);
898  lv2TestChrec.AddOperand(SCEVInit::Create(*lv2.pre));
899  lv2TestChrec.AddOperand(SCEVConstant::Create(1));
900  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv2TestChrec, *chrecMap.at(lv2.pre)));
901 
902  // Tests multiplying two init nodes together creates an n-ary mult expression.
903  // Recurrence: {Init(a2),+,(Init(a0) * Init(a1)),+,Init(a0)}
904  auto lv3TestChrec = SCEVChainRecurrence(*theta, *lv3.pre);
905  lv3TestChrec.AddOperand(SCEVInit::Create(*lv3.pre));
906  lv3TestChrec.AddOperand(
907  SCEVNAryMulExpr::Create(SCEVInit::Create(*lv1.pre), SCEVInit::Create(*lv2.pre)));
908  lv3TestChrec.AddOperand(SCEVInit::Create(*lv1.pre));
909 
910  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv3TestChrec, *chrecMap.at(lv3.pre)));
911 
912  // Tests that when two n-ary mult expressions are folded together, the operands of the RHS mult is
913  // added to the LHS mult
914  // Recurrence:
915  // {Init(a3),+,(Init(a0) * Init(a1) * Init(a0) * Init(a1)),+,((Init(a0) * Init(a1) * Init(a0)) +
916  // (Init(a0) * Init(a0)) + (Init(a0) * Init(a1) * Init(a0))),+,((Init(a0) * Init(a0)) + (Init(a0)
917  // * Init(a0)))}
918  auto lv4TestChrec = SCEVChainRecurrence(*theta, *lv4.pre);
919  lv4TestChrec.AddOperand(SCEVInit::Create(*lv4.pre));
920  lv4TestChrec.AddOperand(SCEVNAryMulExpr::Create(
921  SCEVInit::Create(*lv1.pre),
922  SCEVInit::Create(*lv2.pre),
923  SCEVInit::Create(*lv1.pre),
924  SCEVInit::Create(*lv2.pre)));
925  lv4TestChrec.AddOperand(SCEVNAryAddExpr::Create(
926  SCEVNAryMulExpr::Create(
927  SCEVInit::Create(*lv1.pre),
928  SCEVInit::Create(*lv2.pre),
929  SCEVInit::Create(*lv1.pre)),
930  SCEVNAryMulExpr::Create(SCEVInit::Create(*lv1.pre), SCEVInit::Create(*lv1.pre)),
931  SCEVNAryMulExpr::Create(
932  SCEVInit::Create(*lv1.pre),
933  SCEVInit::Create(*lv2.pre),
934  SCEVInit::Create(*lv1.pre))));
935  lv4TestChrec.AddOperand(SCEVNAryAddExpr::Create(
936  SCEVNAryMulExpr::Create(SCEVInit::Create(*lv1.pre), SCEVInit::Create(*lv1.pre)),
937  SCEVNAryMulExpr::Create(SCEVInit::Create(*lv1.pre), SCEVInit::Create(*lv1.pre))));
938 
939  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv4TestChrec, *chrecMap.at(lv4.pre)));
940 }
941 
942 TEST(ScalarEvolutionTests, SelfRecursiveInductionVariable)
943 {
944  using namespace jlm::llvm;
945 
946  // Arrange
947  const auto intType = jlm::rvsdg::BitType::Create(32);
948 
949  LlvmRvsdgModule rvsdgModule(jlm::util::FilePath(""), "", "");
950  const auto & graph = rvsdgModule.Rvsdg();
951 
952  const auto & c0 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 0);
953 
954  const auto theta = jlm::rvsdg::ThetaNode::create(&graph.GetRootRegion());
955  const auto lv1 = theta->AddLoopVar(c0.output(0));
956 
957  auto & addNode = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv1.pre, lv1.pre }, 32);
958  const auto result = addNode.output(0);
959 
960  const auto & c5 = IntegerConstantOperation::Create(*theta->subregion(), 32, 5);
961  auto & sltNode = jlm::rvsdg::CreateOpNode<IntegerSltOperation>({ result, c5.output(0) }, 32);
962  const auto matchResult =
963  jlm::rvsdg::MatchOperation::Create(*sltNode.output(0), { { 1, 1 } }, 0, 2);
964 
965  theta->set_predicate(matchResult);
966  lv1.post->divert_to(result);
967 
968  jlm::rvsdg::view(graph, stdout);
969 
970  // Act
971  const auto & chrecMap = RunScalarEvolution(rvsdgModule).first;
972 
973  // Assert
974  EXPECT_NE(chrecMap.find(lv1.pre), chrecMap.end());
975 
976  // lv1 is not an induction variable because of self dependency. Should be {Unknown}
977  auto lv1TestChrec = SCEVChainRecurrence(*theta, *lv1.pre);
978  lv1TestChrec.AddOperand(SCEVUnknown::Create());
979  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv1TestChrec, *chrecMap.at(lv1.pre)));
980 }
981 
982 TEST(ScalarEvolutionTests, DependentOnInvalidInductionVariable)
983 {
984  using namespace jlm::llvm;
985 
986  // Arrange
987  const auto intType = jlm::rvsdg::BitType::Create(32);
988 
989  LlvmRvsdgModule rvsdgModule(jlm::util::FilePath(""), "", "");
990  const auto & graph = rvsdgModule.Rvsdg();
991 
992  const auto & c0 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 0);
993  const auto & c1 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 0);
994 
995  const auto theta = jlm::rvsdg::ThetaNode::create(&graph.GetRootRegion());
996  const auto lv1 = theta->AddLoopVar(c0.output(0));
997  const auto lv2 = theta->AddLoopVar(c1.output(0));
998 
999  auto & addNode_1 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv1.pre, lv1.pre }, 32);
1000  const auto result_1 = addNode_1.output(0);
1001 
1002  auto & addNode_2 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv2.pre, lv1.pre }, 32);
1003  const auto result_2 = addNode_2.output(0);
1004 
1005  const auto & c5 = IntegerConstantOperation::Create(*theta->subregion(), 32, 5);
1006  auto & sltNode = jlm::rvsdg::CreateOpNode<IntegerSltOperation>({ result_1, c5.output(0) }, 32);
1007  const auto matchResult =
1008  jlm::rvsdg::MatchOperation::Create(*sltNode.output(0), { { 1, 1 } }, 0, 2);
1009 
1010  theta->set_predicate(matchResult);
1011  lv1.post->divert_to(result_1);
1012  lv2.post->divert_to(result_2);
1013 
1014  jlm::rvsdg::view(graph, stdout);
1015 
1016  // Act
1017  const auto & chrecMap = RunScalarEvolution(rvsdgModule).first;
1018 
1019  // Assert
1020  EXPECT_NE(chrecMap.find(lv1.pre), chrecMap.end());
1021  EXPECT_NE(chrecMap.find(lv2.pre), chrecMap.end());
1022 
1023  // lv1 is not an induction variable because of self dependency. Should be {Unknown}
1024  auto lv1TestChrec = SCEVChainRecurrence(*theta, *lv1.pre);
1025  lv1TestChrec.AddOperand(SCEVUnknown::Create());
1026  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv1TestChrec, *chrecMap.at(lv1.pre)));
1027 
1028  // lv2 has the recurrence {0,+,Unknown} due to the dependency of lv1
1029  auto lv2TestChrec = SCEVChainRecurrence(*theta, *lv2.pre);
1030  lv2TestChrec.AddOperand(SCEVConstant::Create(0));
1031  lv2TestChrec.AddOperand(SCEVUnknown::Create());
1032  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv2TestChrec, *chrecMap.at(lv2.pre)));
1033 }
1034 
1035 TEST(ScalarEvolutionTests, MutuallyDependentInductionVariables)
1036 {
1037  // Testing mutually dependent variables (A->B->A)
1038  using namespace jlm::llvm;
1039 
1040  // Arrange
1041  const auto intType = jlm::rvsdg::BitType::Create(32);
1042 
1043  LlvmRvsdgModule rvsdgModule(jlm::util::FilePath(""), "", "");
1044  const auto & graph = rvsdgModule.Rvsdg();
1045 
1046  const auto & c0 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 0);
1047  const auto & c1 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 1);
1048 
1049  const auto theta = jlm::rvsdg::ThetaNode::create(&graph.GetRootRegion());
1050  const auto lv1 = theta->AddLoopVar(c0.output(0)); // A
1051  const auto lv2 = theta->AddLoopVar(c1.output(0)); // B
1052 
1053  auto & addNode_1 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv1.pre, lv2.pre }, 32);
1054  const auto result_1 = addNode_1.output(0);
1055 
1056  auto & addNode_2 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv1.pre, lv2.pre }, 32);
1057  const auto result_2 = addNode_2.output(0);
1058 
1059  const auto & c5 = IntegerConstantOperation::Create(*theta->subregion(), 32, 5);
1060  auto & sltNode = jlm::rvsdg::CreateOpNode<IntegerSltOperation>({ result_1, c5.output(0) }, 32);
1061  const auto matchResult =
1062  jlm::rvsdg::MatchOperation::Create(*sltNode.output(0), { { 1, 1 } }, 0, 2);
1063 
1064  theta->set_predicate(matchResult);
1065  lv1.post->divert_to(result_1);
1066  lv2.post->divert_to(result_2);
1067 
1068  jlm::rvsdg::view(graph, stdout);
1069 
1070  // Act
1071  const auto & chrecMap = RunScalarEvolution(rvsdgModule).first;
1072 
1073  // Assert
1074  EXPECT_NE(chrecMap.find(lv1.pre), chrecMap.end());
1075  EXPECT_NE(chrecMap.find(lv2.pre), chrecMap.end());
1076 
1077  // Both lv1 and lv2 should be {Unknown} due to mutual dependency (A->B->A)
1078  auto lv1TestChrec = SCEVChainRecurrence(*theta, *lv1.pre);
1079  lv1TestChrec.AddOperand(SCEVUnknown::Create());
1080  auto lv2TestChrec = SCEVChainRecurrence(*theta, *lv2.pre);
1081  lv2TestChrec.AddOperand(SCEVUnknown::Create());
1082  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv1TestChrec, *chrecMap.at(lv1.pre)));
1083  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv2TestChrec, *chrecMap.at(lv2.pre)));
1084 }
1085 
1086 TEST(ScalarEvolutionTests, MultiLayeredMutuallyDependentInductionVariables)
1087 {
1088  // Testing chains of mutually dependent IVs (A->B->C->D->A)
1089  using namespace jlm::llvm;
1090 
1091  // Arrange
1092  const auto intType = jlm::rvsdg::BitType::Create(32);
1093 
1094  LlvmRvsdgModule rvsdgModule(jlm::util::FilePath(""), "", "");
1095  const auto & graph = rvsdgModule.Rvsdg();
1096 
1097  const auto & c0 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 0);
1098  const auto & c1 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 1);
1099  const auto & c2 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 2);
1100  const auto & c3 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 3);
1101 
1102  const auto theta = jlm::rvsdg::ThetaNode::create(&graph.GetRootRegion());
1103  const auto lv1 = theta->AddLoopVar(c0.output(0)); // A
1104  const auto lv2 = theta->AddLoopVar(c1.output(0)); // B
1105  const auto lv3 = theta->AddLoopVar(c2.output(0)); // C
1106  const auto lv4 = theta->AddLoopVar(c3.output(0)); // D
1107 
1108  auto & addNode_1 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv1.pre, lv2.pre }, 32);
1109  const auto result_1 = addNode_1.output(0);
1110  auto & addNode_2 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv2.pre, lv3.pre }, 32);
1111  const auto result_2 = addNode_2.output(0);
1112  auto & addNode_3 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv3.pre, lv4.pre }, 32);
1113  const auto result_3 = addNode_3.output(0);
1114  auto & addNode_4 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv4.pre, lv1.pre }, 32);
1115  const auto result_4 = addNode_4.output(0);
1116 
1117  const auto & c5 = IntegerConstantOperation::Create(*theta->subregion(), 32, 5);
1118  auto & sltNode = jlm::rvsdg::CreateOpNode<IntegerSltOperation>({ result_1, c5.output(0) }, 32);
1119  const auto matchResult =
1120  jlm::rvsdg::MatchOperation::Create(*sltNode.output(0), { { 1, 1 } }, 0, 2);
1121 
1122  theta->set_predicate(matchResult);
1123  lv1.post->divert_to(result_1);
1124  lv2.post->divert_to(result_2);
1125  lv3.post->divert_to(result_3);
1126  lv4.post->divert_to(result_4);
1127 
1128  jlm::rvsdg::view(graph, stdout);
1129 
1130  // Act
1131  const auto & chrecMap = RunScalarEvolution(rvsdgModule).first;
1132 
1133  // Assert
1134  EXPECT_NE(chrecMap.find(lv1.pre), chrecMap.end());
1135  EXPECT_NE(chrecMap.find(lv2.pre), chrecMap.end());
1136  EXPECT_NE(chrecMap.find(lv3.pre), chrecMap.end());
1137  EXPECT_NE(chrecMap.find(lv4.pre), chrecMap.end());
1138 
1139  // All variables should be {Unknown} due to mutual dependency chain (A->B->C->D->A)
1140  auto lv1TestChrec = SCEVChainRecurrence(*theta, *lv1.pre);
1141  lv1TestChrec.AddOperand(SCEVUnknown::Create());
1142  auto lv2TestChrec = SCEVChainRecurrence(*theta, *lv2.pre);
1143  lv2TestChrec.AddOperand(SCEVUnknown::Create());
1144  auto lv3TestChrec = SCEVChainRecurrence(*theta, *lv3.pre);
1145  lv3TestChrec.AddOperand(SCEVUnknown::Create());
1146  auto lv4TestChrec = SCEVChainRecurrence(*theta, *lv4.pre);
1147  lv4TestChrec.AddOperand(SCEVUnknown::Create());
1148 
1149  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv1TestChrec, *chrecMap.at(lv1.pre)));
1150  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv2TestChrec, *chrecMap.at(lv2.pre)));
1151  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv3TestChrec, *chrecMap.at(lv3.pre)));
1152  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv4TestChrec, *chrecMap.at(lv4.pre)));
1153 }
1154 
1155 TEST(ScalarEvolutionTests, InductionVariablesInNestedLoops)
1156 {
1157  // Tests "stitching" of induction variables in outer loops
1158  using namespace jlm::llvm;
1159 
1160  // Arrange
1161  const auto intType = jlm::rvsdg::BitType::Create(32);
1162 
1163  LlvmRvsdgModule rvsdgModule(jlm::util::FilePath(""), "", "");
1164  const auto & graph = rvsdgModule.Rvsdg();
1165 
1166  const auto & c0 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 0);
1167  const auto theta1 = jlm::rvsdg::ThetaNode::create(&graph.GetRootRegion());
1168  const auto lv1 = theta1->AddLoopVar(c0.output(0));
1169 
1170  const auto & c1 = IntegerConstantOperation::Create(*theta1->subregion(), 32, 1);
1171  auto & addNode1 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv1.pre, c1.output(0) }, 32);
1172  const auto res1 = addNode1.output(0);
1173 
1174  const auto & c5 = IntegerConstantOperation::Create(*theta1->subregion(), 32, 5);
1175  auto & sltNode1 = jlm::rvsdg::CreateOpNode<IntegerSltOperation>({ res1, c5.output(0) }, 32);
1176  const auto matchResult1 =
1177  jlm::rvsdg::MatchOperation::Create(*sltNode1.output(0), { { 1, 1 } }, 0, 2);
1178 
1179  const auto theta2 = jlm::rvsdg::ThetaNode::create(theta1->subregion());
1180  const auto lv2 = theta2->AddLoopVar(c1.output(0));
1181  const auto lv3 = theta2->AddLoopVar(lv1.pre);
1182 
1183  auto & addNode2 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv2.pre, lv3.pre }, 32);
1184  const auto & res2 = addNode2.output(0);
1185 
1186  const auto & c10 = IntegerConstantOperation::Create(*theta2->subregion(), 32, 10);
1187  auto & sltNode2 = jlm::rvsdg::CreateOpNode<IntegerSltOperation>({ res2, c10.output(0) }, 32);
1188 
1189  const auto matchResult2 =
1190  jlm::rvsdg::MatchOperation::Create(*sltNode2.output(0), { { 1, 1 } }, 0, 2);
1191 
1192  theta1->set_predicate(matchResult1);
1193  lv1.post->divert_to(res1);
1194 
1195  theta2->set_predicate(matchResult2);
1196  lv2.post->divert_to(res2);
1197 
1198  jlm::rvsdg::view(graph, stdout);
1199 
1200  // Act
1201  const auto & chrecMap = RunScalarEvolution(rvsdgModule).first;
1202 
1203  // Assert
1204  EXPECT_NE(chrecMap.find(lv1.pre), chrecMap.end());
1205 
1206  EXPECT_NE(chrecMap.find(lv2.pre), chrecMap.end());
1207  EXPECT_NE(chrecMap.find(lv3.pre), chrecMap.end());
1208 
1209  // lv1 is a simple induction variable with the recurrence {0,+,1}<1>
1210  auto lv1TestChrec = SCEVChainRecurrence(*theta1, *lv1.pre);
1211  lv1TestChrec.AddOperand(SCEVConstant::Create(0));
1212  lv1TestChrec.AddOperand(SCEVConstant::Create(1));
1213  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv1TestChrec, *chrecMap.at(lv1.pre)));
1214 
1215  // lv2 is a nested induction variable, which is incremented by the value of lv1 for each
1216  // iteration
1217  auto lv2TestChrec = SCEVChainRecurrence(*theta2, *lv2.pre);
1218  lv2TestChrec.AddOperand(SCEVConstant::Create(1));
1219  lv2TestChrec.AddOperand(lv1TestChrec.Clone());
1220  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv2TestChrec, *chrecMap.at(lv2.pre)));
1221 
1222  // lv3 has the same value as lv1, but for the inner loop
1223  auto lv3TestChrec = SCEVChainRecurrence(*theta2, *lv3.pre);
1224  lv3TestChrec.AddOperand(lv1TestChrec.Clone());
1225  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv3TestChrec, *chrecMap.at(lv3.pre)));
1226 }
1227 
1228 TEST(ScalarEvolutionTests, InductionVariablesInNestedLoopsWithFolding)
1229 {
1230  using namespace jlm::llvm;
1231 
1232  // Arrange
1233  const auto intType = jlm::rvsdg::BitType::Create(32);
1234 
1235  LlvmRvsdgModule rvsdgModule(jlm::util::FilePath(""), "", "");
1236  const auto & graph = rvsdgModule.Rvsdg();
1237 
1238  const auto & c0_1 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 0);
1239  const auto & c2_1 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 2);
1240  const auto & c3_1 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 3);
1241 
1242  const auto theta1 = jlm::rvsdg::ThetaNode::create(&graph.GetRootRegion());
1243  const auto lv1_1 = theta1->AddLoopVar(c0_1.output(0));
1244  const auto lv2_1 = theta1->AddLoopVar(c2_1.output(0));
1245  const auto lv3_1 = theta1->AddLoopVar(c3_1.output(0));
1246 
1247  const auto & c1_2 = IntegerConstantOperation::Create(*theta1->subregion(), 32, 1);
1248  const auto & c2_2 = IntegerConstantOperation::Create(*theta1->subregion(), 32, 2);
1249  const auto & c3_2 = IntegerConstantOperation::Create(*theta1->subregion(), 32, 3);
1250 
1251  auto & addNode1 =
1252  jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv1_1.pre, c1_2.output(0) }, 32);
1253  auto & addNode2 =
1254  jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv2_1.pre, c2_2.output(0) }, 32);
1255  auto & addNode3 =
1256  jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv3_1.pre, c3_2.output(0) }, 32);
1257  const auto res1 = addNode1.output(0);
1258  const auto res2 = addNode2.output(0);
1259  const auto res3 = addNode3.output(0);
1260 
1261  const auto & c5 = IntegerConstantOperation::Create(*theta1->subregion(), 32, 5);
1262  auto & sltNode1 = jlm::rvsdg::CreateOpNode<IntegerSltOperation>({ res1, c5.output(0) }, 32);
1263  const auto matchResult1 =
1264  jlm::rvsdg::MatchOperation::Create(*sltNode1.output(0), { { 1, 1 } }, 0, 2);
1265 
1266  const auto theta2 = jlm::rvsdg::ThetaNode::create(theta1->subregion());
1267  const auto lv1_2 = theta2->AddLoopVar(res1);
1268  const auto lv2_2 = theta2->AddLoopVar(res2);
1269  const auto lv3_2 = theta2->AddLoopVar(res3);
1270  const auto lv4 = theta2->AddLoopVar(c1_2.output(0));
1271  const auto lv5 = theta2->AddLoopVar(c1_2.output(0));
1272 
1273  auto & addNode4 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv1_2.pre, lv2_2.pre }, 32);
1274  auto & addNode5 =
1275  jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ addNode4.output(0), lv3_2.pre }, 32);
1276  auto & addNode6 =
1277  jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv4.pre, addNode5.output(0) }, 32);
1278  const auto & res4 = addNode6.output(0);
1279 
1280  auto & mulNode1 = jlm::rvsdg::CreateOpNode<IntegerMulOperation>({ lv1_2.pre, lv2_2.pre }, 32);
1281  auto & addNode7 =
1282  jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv5.pre, mulNode1.output(0) }, 32);
1283  const auto & res5 = addNode7.output(0);
1284 
1285  const auto & c10 = IntegerConstantOperation::Create(*theta2->subregion(), 32, 10);
1286  auto & sltNode2 = jlm::rvsdg::CreateOpNode<IntegerSltOperation>({ res4, c10.output(0) }, 32);
1287 
1288  const auto matchResult2 =
1289  jlm::rvsdg::MatchOperation::Create(*sltNode2.output(0), { { 1, 1 } }, 0, 2);
1290 
1291  // Outer loop
1292  theta1->set_predicate(matchResult1);
1293  lv1_1.post->divert_to(res1);
1294  lv2_1.post->divert_to(res2);
1295  lv3_1.post->divert_to(res3);
1296 
1297  // Inner loop
1298  theta2->set_predicate(matchResult2);
1299  lv4.post->divert_to(res4);
1300  lv5.post->divert_to(res5);
1301 
1302  jlm::rvsdg::view(graph, stdout);
1303 
1304  // Act
1305  const auto & chrecMap = RunScalarEvolution(rvsdgModule).first;
1306 
1307  // Assert
1308  EXPECT_NE(chrecMap.find(lv1_1.pre), chrecMap.end());
1309  EXPECT_NE(chrecMap.find(lv2_1.pre), chrecMap.end());
1310  EXPECT_NE(chrecMap.find(lv3_1.pre), chrecMap.end());
1311 
1312  EXPECT_NE(chrecMap.find(lv1_2.pre), chrecMap.end());
1313  EXPECT_NE(chrecMap.find(lv2_2.pre), chrecMap.end());
1314  EXPECT_NE(chrecMap.find(lv3_2.pre), chrecMap.end());
1315  EXPECT_NE(chrecMap.find(lv4.pre), chrecMap.end());
1316  EXPECT_NE(chrecMap.find(lv5.pre), chrecMap.end());
1317 
1318  // lv1 is a simple induction variable with the recurrence {0,+,1}<1>
1319  auto lv1TestChrec = SCEVChainRecurrence(*theta1, *lv1_1.pre);
1320  lv1TestChrec.AddOperand(SCEVConstant::Create(0));
1321  lv1TestChrec.AddOperand(SCEVConstant::Create(1));
1322  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv1TestChrec, *chrecMap.at(lv1_1.pre)));
1323 
1324  // lv2 is a simple induction variable with the recurrence {2,+,2}<1>
1325  auto lv2TestChrec = SCEVChainRecurrence(*theta1, *lv2_1.pre);
1326  lv2TestChrec.AddOperand(SCEVConstant::Create(2));
1327  lv2TestChrec.AddOperand(SCEVConstant::Create(2));
1328  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv2TestChrec, *chrecMap.at(lv2_1.pre)));
1329 
1330  // lv3 is a simple induction variable with the recurrence {3,+,3}<1>
1331  auto lv3TestChrec = SCEVChainRecurrence(*theta1, *lv3_1.pre);
1332  lv3TestChrec.AddOperand(SCEVConstant::Create(3));
1333  lv3TestChrec.AddOperand(SCEVConstant::Create(3));
1334  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv3TestChrec, *chrecMap.at(lv3_1.pre)));
1335 
1336  // lv1_2 is lv1_1 incremented by 1 but in the inner loop
1337  auto lv1_2TestChrec = SCEVChainRecurrence(*theta2, *lv1_2.pre);
1338  const auto lv1_2InnerChrec = SCEVChainRecurrence::Create(*theta1, *lv1_1.post->origin());
1339  lv1_2InnerChrec->AddOperand(SCEVConstant::Create(1));
1340  lv1_2InnerChrec->AddOperand(SCEVConstant::Create(1));
1341  lv1_2TestChrec.AddOperand(lv1_2InnerChrec->Clone());
1342  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv1_2TestChrec, *chrecMap.at(lv1_2.pre)));
1343 
1344  // lv2_2 is lv2_1 incremented by 2 but in the inner loop
1345  auto lv2_2TestChrec = SCEVChainRecurrence(*theta2, *lv2_2.pre);
1346  const auto lv2_2InnerChrec = SCEVChainRecurrence::Create(*theta1, *lv2_1.post->origin());
1347  lv2_2InnerChrec->AddOperand(SCEVConstant::Create(4));
1348  lv2_2InnerChrec->AddOperand(SCEVConstant::Create(2));
1349  lv2_2TestChrec.AddOperand(lv2_2InnerChrec->Clone());
1350  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv2_2TestChrec, *chrecMap.at(lv2_2.pre)));
1351 
1352  // lv3_2 is lv3_1 incremented by 3 but in the inner loop
1353  auto lv3_2TestChrec = SCEVChainRecurrence(*theta2, *lv3_2.pre);
1354  const auto lv3_2InnerChrec = SCEVChainRecurrence::Create(*theta1, *lv3_1.post->origin());
1355  lv3_2InnerChrec->AddOperand(SCEVConstant::Create(6));
1356  lv3_2InnerChrec->AddOperand(SCEVConstant::Create(3));
1357  lv3_2TestChrec.AddOperand(lv3_2InnerChrec->Clone());
1358  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv3_2TestChrec, *chrecMap.at(lv3_2.pre)));
1359 
1360  // lv4 is in the inner loop and has a start value of 1 which is incremented by the result of
1361  // folding ({1,+,1}<1> + {4,+,2}<1> + {6,+,3}<1>) = {11,+,6}<1>. Recurrence:
1362  // { 1, +, { 11, +, 6 } < 1 > } < 2 >
1363  auto lv4TestChrec = SCEVChainRecurrence(*theta2, *lv4.pre);
1364  lv4TestChrec.AddOperand(SCEVConstant::Create(1));
1365  const auto lv4InnerChrec = SCEVChainRecurrence::Create(*theta1, *lv4.pre);
1366  lv4InnerChrec->AddOperand(SCEVConstant::Create(11));
1367  lv4InnerChrec->AddOperand(SCEVConstant::Create(6));
1368  lv4TestChrec.AddOperand(lv4InnerChrec->Clone());
1369  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv4TestChrec, *chrecMap.at(lv4.pre)));
1370 
1371  // lv5 is in the inner loop and has a start value of 1 which is incremented by the result of
1372  // folding ({1,+,1}<1> * {4,+,2}<1>) = {4,+,8,+,4}<1>. Recurrence: {1,+,{4,+,8,+,4}<1>}<2>
1373  auto lv5TestChrec = SCEVChainRecurrence(*theta2, *lv5.pre);
1374  lv5TestChrec.AddOperand(SCEVConstant::Create(1));
1375  const auto lv5InnerChrec = SCEVChainRecurrence::Create(*theta1, *lv5.pre);
1376  lv5InnerChrec->AddOperand(SCEVConstant::Create(4));
1377  lv5InnerChrec->AddOperand(SCEVConstant::Create(8));
1378  lv5InnerChrec->AddOperand(SCEVConstant::Create(4));
1379  lv5TestChrec.AddOperand(lv5InnerChrec->Clone());
1380  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv5TestChrec, *chrecMap.at(lv5.pre)));
1381 }
1382 
1383 TEST(ScalarEvolutionTests, InductionVariablesInSisterLoops)
1384 {
1385  // Tests "stitching" of induction variables in other loops that are on the same level, AKA
1386  // "sister loops"
1387  using namespace jlm::llvm;
1388 
1389  // Arrange
1390  const auto intType = jlm::rvsdg::BitType::Create(32);
1391 
1392  LlvmRvsdgModule rvsdgModule(jlm::util::FilePath(""), "", "");
1393  const auto & graph = rvsdgModule.Rvsdg();
1394 
1395  const auto & c0 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 0);
1396  const auto theta1 = jlm::rvsdg::ThetaNode::create(&graph.GetRootRegion());
1397  const auto lv1 = theta1->AddLoopVar(c0.output(0));
1398 
1399  const auto & c1 = IntegerConstantOperation::Create(*theta1->subregion(), 32, 1);
1400  auto & addNode1 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv1.pre, c1.output(0) }, 32);
1401  const auto res1 = addNode1.output(0);
1402 
1403  const auto & c5 = IntegerConstantOperation::Create(*theta1->subregion(), 32, 5);
1404  auto & sltNode1 = jlm::rvsdg::CreateOpNode<IntegerSltOperation>({ res1, c5.output(0) }, 32);
1405  const auto matchResult1 =
1406  jlm::rvsdg::MatchOperation::Create(*sltNode1.output(0), { { 1, 1 } }, 0, 2);
1407 
1408  const auto & c2 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 2);
1409  const auto theta2 = jlm::rvsdg::ThetaNode::create(&graph.GetRootRegion());
1410  const auto lv2 = theta2->AddLoopVar(c2.output(0));
1411  const auto lv3 = theta2->AddLoopVar(theta1->output(0));
1412 
1413  auto & addNode2 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv2.pre, lv3.pre }, 32);
1414  const auto & res2 = addNode2.output(0);
1415 
1416  const auto & c10 = IntegerConstantOperation::Create(*theta2->subregion(), 32, 10);
1417  auto & sltNode2 = jlm::rvsdg::CreateOpNode<IntegerSltOperation>({ res2, c10.output(0) }, 32);
1418 
1419  const auto matchResult2 =
1420  jlm::rvsdg::MatchOperation::Create(*sltNode2.output(0), { { 1, 1 } }, 0, 2);
1421 
1422  theta1->set_predicate(matchResult1);
1423  lv1.post->divert_to(res1);
1424 
1425  theta2->set_predicate(matchResult2);
1426  lv2.post->divert_to(res2);
1427 
1428  jlm::rvsdg::view(graph, stdout);
1429 
1430  // Act
1431  const auto & chrecMap = RunScalarEvolution(rvsdgModule).first;
1432 
1433  // Assert
1434  EXPECT_NE(chrecMap.find(lv1.pre), chrecMap.end());
1435 
1436  EXPECT_NE(chrecMap.find(lv2.pre), chrecMap.end());
1437  EXPECT_NE(chrecMap.find(lv3.pre), chrecMap.end());
1438 
1439  // lv1 is a simple induction variable with the recurrence {0,+,1}<1>
1440  auto lv1TestChrec = SCEVChainRecurrence(*theta1, *lv1.pre);
1441  lv1TestChrec.AddOperand(SCEVConstant::Create(0));
1442  lv1TestChrec.AddOperand(SCEVConstant::Create(1));
1443  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv1TestChrec, *chrecMap.at(lv1.pre)));
1444 
1445  // lv2 is a nested induction variable, which is incremented by the post iteration value of lv1
1446  // ({1,+,1}<1>) for each iteration
1447  auto lv2TestChrec = SCEVChainRecurrence(*theta2, *lv2.pre);
1448  lv2TestChrec.AddOperand(SCEVConstant::Create(2));
1449  auto lv2InnerChrec = SCEVChainRecurrence(*theta1, *lv1.output);
1450  lv2InnerChrec.AddOperand(SCEVConstant::Create(1));
1451  lv2InnerChrec.AddOperand(SCEVConstant::Create(1));
1452  lv2TestChrec.AddOperand(lv2InnerChrec.Clone());
1453  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv2TestChrec, *chrecMap.at(lv2.pre)));
1454 
1455  // lv3 has the same value as the post iteration value of lv1, but wrapped in the inner loop
1456  auto lv3TestChrec = SCEVChainRecurrence(*theta2, *lv3.pre);
1457  lv3TestChrec.AddOperand(lv2InnerChrec.Clone());
1458  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv3TestChrec, *chrecMap.at(lv3.pre)));
1459 }
1460 
1461 TEST(ScalarEvolutionTests, ComputeRecurrenceForArrayGEP)
1462 {
1463  using namespace jlm::llvm;
1464 
1465  // Arrange
1466  const auto intType = jlm::rvsdg::BitType::Create(32);
1467  const auto intArrayType = ArrayType::Create(intType, 5);
1468  const auto pointerType = PointerType::Create();
1469  const auto memoryStateType = MemoryStateType::Create();
1470 
1471  LlvmRvsdgModule rvsdgModule(jlm::util::FilePath(""), "", "");
1472  const auto & graph = rvsdgModule.Rvsdg();
1473 
1474  auto lambda = jlm::rvsdg::LambdaNode::Create(
1475  graph.GetRootRegion(),
1476  LlvmLambdaOperation::Create(
1477  jlm::rvsdg::FunctionType::Create(
1478  { pointerType, memoryStateType },
1479  { intType, memoryStateType }),
1480  "f",
1481  Linkage::externalLinkage));
1482 
1483  const auto & delta = jlm::rvsdg::DeltaNode::Create(
1484  &graph.GetRootRegion(),
1485  DeltaOperation::Create(intArrayType, "", Linkage::externalLinkage, "", false, 4));
1486 
1487  const auto & arrayC1 = IntegerConstantOperation::Create(*delta->subregion(), 32, 1);
1488  const auto & arrayC2 = IntegerConstantOperation::Create(*delta->subregion(), 32, 2);
1489  const auto & arrayC3 = IntegerConstantOperation::Create(*delta->subregion(), 32, 3);
1490  const auto & arrayC4 = IntegerConstantOperation::Create(*delta->subregion(), 32, 4);
1491  const auto & arrayC5 = IntegerConstantOperation::Create(*delta->subregion(), 32, 5);
1492 
1493  const auto & constantArray = ConstantDataArray::Create({ arrayC1.output(0),
1494  arrayC2.output(0),
1495  arrayC3.output(0),
1496  arrayC4.output(0),
1497  arrayC5.output(0) });
1498  delta->finalize(constantArray);
1499 
1500  const auto cv1 = lambda->AddContextVar(delta->output());
1501 
1502  const auto & c0_1 = IntegerConstantOperation::Create(*lambda->subregion(), 32, 0);
1503  const auto & c1_1 = IntegerConstantOperation::Create(*lambda->subregion(), 32, 1);
1504  const auto & theta = jlm::rvsdg::ThetaNode::create(lambda->subregion());
1505 
1506  const auto memoryState = theta->AddLoopVar(lambda->GetFunctionArguments()[1]);
1507  const auto lv1 = theta->AddLoopVar(c0_1.output(0)); // i
1508  const auto lv2 = theta->AddLoopVar(c1_1.output(0)); // sum
1509  const auto lv3 = theta->AddLoopVar(cv1.inner); // arr ptr
1510 
1511  const auto & c1_2 = IntegerConstantOperation::Create(*theta->subregion(), 32, 1);
1512 
1513  auto & addNode1 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv1.pre, c1_2.output(0) }, 32);
1514  const auto res1 = addNode1.output(0);
1515 
1516  const auto & c0_2 = IntegerConstantOperation::Create(*theta->subregion(), 64, 0);
1517  const auto & lv1SExt = SExtOperation::create(64, lv1.pre);
1518 
1519  const auto gep =
1520  GetElementPtrOperation::create(lv3.pre, { c0_2.output(0), lv1SExt }, intArrayType);
1521 
1522  auto loadedValue = LoadNonVolatileOperation::Create(gep, { memoryState.pre }, intType, 32)[0];
1523 
1524  auto & addNode2 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv2.pre, loadedValue }, 32);
1525  const auto res2 = addNode2.output(0);
1526 
1527  const auto & c4 = IntegerConstantOperation::Create(*theta->subregion(), 32, 4);
1528  auto & sltNode = jlm::rvsdg::CreateOpNode<IntegerSltOperation>({ res1, c4.output(0) }, 32);
1529  const auto matchResult =
1530  jlm::rvsdg::MatchOperation::Create(*sltNode.output(0), { { 1, 1 } }, 0, 2);
1531 
1532  theta->set_predicate(matchResult);
1533 
1534  lv1.post->divert_to(res1);
1535  lv2.post->divert_to(res2);
1536 
1537  jlm::rvsdg::view(graph, stdout);
1538 
1539  // Act
1540  const auto & chrecMap = RunScalarEvolution(rvsdgModule).first;
1541 
1542  // Assert
1543  EXPECT_NE(chrecMap.find(lv1.pre), chrecMap.end());
1544  EXPECT_NE(chrecMap.find(lv2.pre), chrecMap.end());
1545  EXPECT_NE(chrecMap.find(lv3.pre), chrecMap.end());
1546  EXPECT_NE(chrecMap.find(gep), chrecMap.end());
1547 
1548  // lv1 is a simple induction variable with the recurrence {0,+,1}
1549  auto lv1TestChrec = SCEVChainRecurrence(*theta, *lv1.pre);
1550  lv1TestChrec.AddOperand(SCEVConstant::Create(0));
1551  lv1TestChrec.AddOperand(SCEVConstant::Create(1));
1552  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv1TestChrec, *chrecMap.at(lv1.pre)));
1553 
1554  // lv2 is reliant on the result from a LOAD operation, and should therefore be {1,+,Unknown}
1555  auto lv2TestChrec = SCEVChainRecurrence(*theta, *lv2.pre);
1556  lv2TestChrec.AddOperand(SCEVConstant::Create(1));
1557  lv2TestChrec.AddOperand(SCEVUnknown::Create());
1558  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv2TestChrec, *chrecMap.at(lv2.pre)));
1559 
1560  // lv3 (base pointer in GEP) is unchanged, it's recurrence should be {Init(a3)}
1561  auto lv3TestChrec = SCEVChainRecurrence(*theta, *lv3.pre);
1562  lv3TestChrec.AddOperand(SCEVInit::Create(*lv3.pre));
1563  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv3TestChrec, *chrecMap.at(lv3.pre)));
1564 
1565  // The GEP should have the following SCEV: (PH(a3) + ((0 * 20) + (PH(a1) * 4)))
1566  // Replacing the placeholders gives us ({Init(a3)} + (0 * 20) + ({0,+,1} * 4)})
1567  // Folding constants together gives us ({Init(a3)} + {0,+,4}) = {Init(a3),+,4} which is the
1568  // resulting recurrence
1569  auto gepTestChrec = SCEVChainRecurrence(*theta, *gep);
1570  gepTestChrec.AddOperand(SCEVInit::Create(*lv3.pre));
1571  gepTestChrec.AddOperand(SCEVConstant::Create(4));
1572  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(gepTestChrec, *chrecMap.at(gep)));
1573 }
1574 
1575 TEST(ScalarEvolutionTests, ComputeRecurrenceForStructGEP)
1576 {
1577  using namespace jlm::llvm;
1578 
1579  // Arrange
1580  const auto intType = jlm::rvsdg::BitType::Create(32);
1581  const auto intStructType =
1582  StructType::CreateLiteral({ intType, intType, intType, intType, intType }, false);
1583  const auto pointerType = PointerType::Create();
1584  const auto memoryStateType = MemoryStateType::Create();
1585 
1586  LlvmRvsdgModule rvsdgModule(jlm::util::FilePath(""), "", "");
1587  const auto & graph = rvsdgModule.Rvsdg();
1588 
1589  auto lambda = jlm::rvsdg::LambdaNode::Create(
1590  graph.GetRootRegion(),
1591  LlvmLambdaOperation::Create(
1592  jlm::rvsdg::FunctionType::Create(
1593  { pointerType, memoryStateType },
1594  { intType, memoryStateType }),
1595  "f",
1596  Linkage::externalLinkage));
1597 
1598  const auto & delta = jlm::rvsdg::DeltaNode::Create(
1599  &graph.GetRootRegion(),
1600  DeltaOperation::Create(intStructType, "", Linkage::externalLinkage, "", false, 4));
1601 
1602  const auto & structC1 = IntegerConstantOperation::Create(*delta->subregion(), 32, 1);
1603  const auto & structC2 = IntegerConstantOperation::Create(*delta->subregion(), 32, 2);
1604  const auto & structC3 = IntegerConstantOperation::Create(*delta->subregion(), 32, 3);
1605  const auto & structC4 = IntegerConstantOperation::Create(*delta->subregion(), 32, 4);
1606  const auto & structC5 = IntegerConstantOperation::Create(*delta->subregion(), 32, 5);
1607 
1608  auto & constantStruct = ConstantStruct::Create(
1609  *delta->subregion(),
1610  { structC1.output(0),
1611  structC2.output(0),
1612  structC3.output(0),
1613  structC4.output(0),
1614  structC5.output(0) },
1615  intStructType);
1616  delta->finalize(&constantStruct);
1617 
1618  const auto cv1 = lambda->AddContextVar(delta->output());
1619 
1620  const auto & c0_1 = IntegerConstantOperation::Create(*lambda->subregion(), 32, 0);
1621  const auto & c1_1 = IntegerConstantOperation::Create(*lambda->subregion(), 32, 1);
1622  const auto & theta = jlm::rvsdg::ThetaNode::create(lambda->subregion());
1623 
1624  const auto memoryState = theta->AddLoopVar(lambda->GetFunctionArguments()[1]);
1625  const auto lv1 = theta->AddLoopVar(c0_1.output(0)); // i
1626  const auto lv2 = theta->AddLoopVar(c1_1.output(0)); // sum
1627  const auto lv3 = theta->AddLoopVar(cv1.inner); // struct ptr
1628 
1629  const auto & c1_2 = IntegerConstantOperation::Create(*theta->subregion(), 32, 1);
1630 
1631  auto & addNode1 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv1.pre, c1_2.output(0) }, 32);
1632  const auto res1 = addNode1.output(0);
1633 
1634  const auto & lv1SExt = SExtOperation::create(64, lv1.pre);
1635  const auto gep = GetElementPtrOperation::create(lv3.pre, { lv1SExt }, intType);
1636 
1637  auto loadedValue = LoadNonVolatileOperation::Create(gep, { memoryState.pre }, intType, 32)[0];
1638 
1639  auto & addNode2 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv2.pre, loadedValue }, 32);
1640  const auto res2 = addNode2.output(0);
1641 
1642  const auto & c4 = IntegerConstantOperation::Create(*theta->subregion(), 32, 4);
1643  auto & sltNode = jlm::rvsdg::CreateOpNode<IntegerSltOperation>({ res1, c4.output(0) }, 32);
1644  const auto matchResult =
1645  jlm::rvsdg::MatchOperation::Create(*sltNode.output(0), { { 1, 1 } }, 0, 2);
1646 
1647  theta->set_predicate(matchResult);
1648 
1649  lv1.post->divert_to(res1);
1650  lv2.post->divert_to(res2);
1651 
1652  jlm::rvsdg::view(graph, stdout);
1653 
1654  // Act
1655  const auto & chrecMap = RunScalarEvolution(rvsdgModule).first;
1656 
1657  // Assert
1658  EXPECT_NE(chrecMap.find(lv1.pre), chrecMap.end());
1659  EXPECT_NE(chrecMap.find(lv2.pre), chrecMap.end());
1660  EXPECT_NE(chrecMap.find(lv3.pre), chrecMap.end());
1661  EXPECT_NE(chrecMap.find(gep), chrecMap.end());
1662 
1663  // lv1 is a simple induction variable with the recurrence {0,+,1}
1664  auto lv1TestChrec = SCEVChainRecurrence(*theta, *lv1.pre);
1665  lv1TestChrec.AddOperand(SCEVConstant::Create(0));
1666  lv1TestChrec.AddOperand(SCEVConstant::Create(1));
1667  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv1TestChrec, *chrecMap.at(lv1.pre)));
1668 
1669  // lv2 is reliant on the result from a LOAD operation, and should therefore be {1,+,Unknown}
1670  auto lv2TestChrec = SCEVChainRecurrence(*theta, *lv2.pre);
1671  lv2TestChrec.AddOperand(SCEVConstant::Create(1));
1672  lv2TestChrec.AddOperand(SCEVUnknown::Create());
1673  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv2TestChrec, *chrecMap.at(lv2.pre)));
1674 
1675  // lv3 (base pointer in GEP) is unchanged, it's recurrence should be {Init(a3)}
1676  auto lv3TestChrec = SCEVChainRecurrence(*theta, *lv3.pre);
1677  lv3TestChrec.AddOperand(SCEVInit::Create(*lv3.pre));
1678  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(lv3TestChrec, *chrecMap.at(lv3.pre)));
1679 
1680  // The GEP should have the following SCEV: (PH(a3) + (PH(a1) * 4))
1681  // Replacing the placeholders gives us ({Init(a3)} + ({0,+,1} * 4))
1682  // Folding constants together gives us ({Init(a3)} + {0,+,4}) = {Init(a3),+,4} which is the
1683  // resulting recurrence
1684  auto gepTestChrec = SCEVChainRecurrence(*theta, *gep);
1685  gepTestChrec.AddOperand(SCEVInit::Create(*lv3.pre));
1686  gepTestChrec.AddOperand(SCEVConstant::Create(4));
1687  EXPECT_TRUE(ScalarEvolution::StructurallyEqual(gepTestChrec, *chrecMap.at(gep)));
1688 }
1689 
1690 TEST(ScalarEvolutionTests, ComputeTripCountForSLTComparisonWithAffineRecurrence)
1691 {
1692  using namespace jlm::llvm;
1693 
1694  // Arrange
1695  const auto intType = jlm::rvsdg::BitType::Create(32);
1696 
1697  LlvmRvsdgModule rvsdgModule(jlm::util::FilePath(""), "", "");
1698  const auto & graph = rvsdgModule.Rvsdg();
1699 
1700  const auto & c0 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 0);
1701 
1702  const auto theta = jlm::rvsdg::ThetaNode::create(&graph.GetRootRegion());
1703  const auto lv1 = theta->AddLoopVar(c0.output(0));
1704 
1705  const auto & c1 = IntegerConstantOperation::Create(*theta->subregion(), 32, 1);
1706  auto & addNode = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv1.pre, c1.output(0) }, 32);
1707  const auto result = addNode.output(0);
1708 
1709  const auto & c5 = IntegerConstantOperation::Create(*theta->subregion(), 32, 5);
1710  auto & sltNode = jlm::rvsdg::CreateOpNode<IntegerSltOperation>({ result, c5.output(0) }, 32);
1711  const auto matchResult =
1712  jlm::rvsdg::MatchOperation::Create(*sltNode.output(0), { { 1, 1 } }, 0, 2);
1713 
1714  theta->set_predicate(matchResult);
1715  lv1.post->divert_to(result);
1716 
1717  jlm::rvsdg::view(graph, stdout);
1718 
1719  // Act
1720  const auto & tripCountMap = RunScalarEvolution(rvsdgModule).second;
1721 
1722  // Assert
1723  EXPECT_NE(tripCountMap.find(theta), tripCountMap.end());
1724  const auto tripCount = tripCountMap.at(theta);
1725  EXPECT_TRUE(tripCount == 5);
1726 }
1727 
1728 TEST(ScalarEvolutionTests, ComputeTripCountForSLEComparisonWithAffineRecurrence)
1729 {
1730  using namespace jlm::llvm;
1731 
1732  // Arrange
1733  const auto intType = jlm::rvsdg::BitType::Create(32);
1734 
1735  LlvmRvsdgModule rvsdgModule(jlm::util::FilePath(""), "", "");
1736  const auto & graph = rvsdgModule.Rvsdg();
1737 
1738  const auto & c0 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 0);
1739 
1740  const auto theta = jlm::rvsdg::ThetaNode::create(&graph.GetRootRegion());
1741  const auto lv1 = theta->AddLoopVar(c0.output(0));
1742 
1743  const auto & c1 = IntegerConstantOperation::Create(*theta->subregion(), 32, 1);
1744  auto & addNode = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv1.pre, c1.output(0) }, 32);
1745  const auto result = addNode.output(0);
1746 
1747  const auto & c5 = IntegerConstantOperation::Create(*theta->subregion(), 32, 5);
1748  auto & sleNode = jlm::rvsdg::CreateOpNode<IntegerSleOperation>({ result, c5.output(0) }, 32);
1749  const auto matchResult =
1750  jlm::rvsdg::MatchOperation::Create(*sleNode.output(0), { { 1, 1 } }, 0, 2);
1751 
1752  theta->set_predicate(matchResult);
1753  lv1.post->divert_to(result);
1754 
1755  jlm::rvsdg::view(graph, stdout);
1756 
1757  // Act
1758  const auto & tripCountMap = RunScalarEvolution(rvsdgModule).second;
1759 
1760  // Assert
1761  EXPECT_NE(tripCountMap.find(theta), tripCountMap.end());
1762  // For equals, we expect an extra iteration compared to strict lesser than
1763  const auto tripCount = tripCountMap.at(theta);
1764 
1765  EXPECT_TRUE(tripCount == 6);
1766 }
1767 
1768 TEST(ScalarEvolutionTests, ComputeTripCountForSGTComparisonWithAffineRecurrence)
1769 {
1770  using namespace jlm::llvm;
1771 
1772  // Arrange
1773  const auto intType = jlm::rvsdg::BitType::Create(32);
1774 
1775  LlvmRvsdgModule rvsdgModule(jlm::util::FilePath(""), "", "");
1776  const auto & graph = rvsdgModule.Rvsdg();
1777 
1778  const auto & c5 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 5);
1779 
1780  const auto theta = jlm::rvsdg::ThetaNode::create(&graph.GetRootRegion());
1781  const auto lv1 = theta->AddLoopVar(c5.output(0));
1782 
1783  const auto & c1 = IntegerConstantOperation::Create(*theta->subregion(), 32, 1);
1784  auto & subNode = jlm::rvsdg::CreateOpNode<IntegerSubOperation>({ lv1.pre, c1.output(0) }, 32);
1785  const auto result = subNode.output(0);
1786 
1787  const auto & c0 = IntegerConstantOperation::Create(*theta->subregion(), 32, 0);
1788  auto & sgtNode = jlm::rvsdg::CreateOpNode<IntegerSgtOperation>({ result, c0.output(0) }, 32);
1789  const auto matchResult =
1790  jlm::rvsdg::MatchOperation::Create(*sgtNode.output(0), { { 1, 1 } }, 0, 2);
1791 
1792  theta->set_predicate(matchResult);
1793  lv1.post->divert_to(result);
1794 
1795  jlm::rvsdg::view(graph, stdout);
1796 
1797  // Act
1798  const auto & tripCountMap = RunScalarEvolution(rvsdgModule).second;
1799 
1800  // Assert
1801  EXPECT_NE(tripCountMap.find(theta), tripCountMap.end());
1802  const auto tripCount = tripCountMap.at(theta);
1803  EXPECT_TRUE(tripCount == 5);
1804 }
1805 
1806 TEST(ScalarEvolutionTests, ComputeTripCountForSGEComparisonWithAffineRecurrence)
1807 {
1808  using namespace jlm::llvm;
1809 
1810  // Arrange
1811  const auto intType = jlm::rvsdg::BitType::Create(32);
1812 
1813  LlvmRvsdgModule rvsdgModule(jlm::util::FilePath(""), "", "");
1814  const auto & graph = rvsdgModule.Rvsdg();
1815 
1816  const auto & c5 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 5);
1817 
1818  const auto theta = jlm::rvsdg::ThetaNode::create(&graph.GetRootRegion());
1819  const auto lv1 = theta->AddLoopVar(c5.output(0));
1820 
1821  const auto & c1 = IntegerConstantOperation::Create(*theta->subregion(), 32, 1);
1822  auto & subNode = jlm::rvsdg::CreateOpNode<IntegerSubOperation>({ lv1.pre, c1.output(0) }, 32);
1823  const auto result = subNode.output(0);
1824 
1825  const auto & c0 = IntegerConstantOperation::Create(*theta->subregion(), 32, 0);
1826  auto & sgeNode = jlm::rvsdg::CreateOpNode<IntegerSgeOperation>({ result, c0.output(0) }, 32);
1827  const auto matchResult =
1828  jlm::rvsdg::MatchOperation::Create(*sgeNode.output(0), { { 1, 1 } }, 0, 2);
1829 
1830  theta->set_predicate(matchResult);
1831  lv1.post->divert_to(result);
1832 
1833  jlm::rvsdg::view(graph, stdout);
1834 
1835  // Act
1836  const auto & tripCountMap = RunScalarEvolution(rvsdgModule).second;
1837 
1838  // Assert
1839  EXPECT_NE(tripCountMap.find(theta), tripCountMap.end());
1840  // For equals, we expect an extra iteration compared to strict greater than
1841  const auto tripCount = tripCountMap.at(theta);
1842  EXPECT_TRUE(tripCount == 6);
1843 }
1844 
1845 TEST(ScalarEvolutionTests, ComputeTripCountForNEComparisonWithAffineRecurrence)
1846 {
1847  using namespace jlm::llvm;
1848 
1849  // Arrange
1850  const auto intType = jlm::rvsdg::BitType::Create(32);
1851 
1852  LlvmRvsdgModule rvsdgModule(jlm::util::FilePath(""), "", "");
1853  const auto & graph = rvsdgModule.Rvsdg();
1854 
1855  const auto & c0 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 0);
1856 
1857  const auto theta = jlm::rvsdg::ThetaNode::create(&graph.GetRootRegion());
1858  const auto lv1 = theta->AddLoopVar(c0.output(0));
1859 
1860  const auto & c1 = IntegerConstantOperation::Create(*theta->subregion(), 32, 1);
1861  auto & addNode = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv1.pre, c1.output(0) }, 32);
1862  const auto result = addNode.output(0);
1863 
1864  const auto & c5 = IntegerConstantOperation::Create(*theta->subregion(), 32, 5);
1865  auto & neNode = jlm::rvsdg::CreateOpNode<IntegerNeOperation>({ result, c5.output(0) }, 32);
1866  const auto matchResult =
1867  jlm::rvsdg::MatchOperation::Create(*neNode.output(0), { { 1, 1 } }, 0, 2);
1868 
1869  theta->set_predicate(matchResult);
1870  lv1.post->divert_to(result);
1871 
1872  jlm::rvsdg::view(graph, stdout);
1873 
1874  // Act
1875  const auto & tripCountMap = RunScalarEvolution(rvsdgModule).second;
1876 
1877  // Assert
1878  EXPECT_NE(tripCountMap.find(theta), tripCountMap.end());
1879  const auto tripCount = tripCountMap.at(theta);
1880  EXPECT_TRUE(tripCount == 5);
1881 }
1882 
1883 TEST(ScalarEvolutionTests, ComputeTripCountForEQComparisonWithAffineRecurrence)
1884 {
1885  using namespace jlm::llvm;
1886 
1887  // Arrange
1888  const auto intType = jlm::rvsdg::BitType::Create(32);
1889 
1890  LlvmRvsdgModule rvsdgModule(jlm::util::FilePath(""), "", "");
1891  const auto & graph = rvsdgModule.Rvsdg();
1892 
1893  const auto & c0 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 0);
1894 
1895  const auto theta = jlm::rvsdg::ThetaNode::create(&graph.GetRootRegion());
1896  const auto lv1 = theta->AddLoopVar(c0.output(0));
1897 
1898  const auto & c1_1 = IntegerConstantOperation::Create(*theta->subregion(), 32, 1);
1899  auto & addNode = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv1.pre, c1_1.output(0) }, 32);
1900  const auto result = addNode.output(0);
1901 
1902  const auto & c1_2 = IntegerConstantOperation::Create(*theta->subregion(), 32, 1);
1903  auto & eqNode = jlm::rvsdg::CreateOpNode<IntegerEqOperation>({ result, c1_2.output(0) }, 32);
1904  const auto matchResult =
1905  jlm::rvsdg::MatchOperation::Create(*eqNode.output(0), { { 1, 1 } }, 0, 2);
1906 
1907  theta->set_predicate(matchResult);
1908  lv1.post->divert_to(result);
1909 
1910  jlm::rvsdg::view(graph, stdout);
1911 
1912  // Act
1913  const auto & tripCountMap = RunScalarEvolution(rvsdgModule).second;
1914 
1915  // Assert
1916  EXPECT_NE(tripCountMap.find(theta), tripCountMap.end());
1917  const auto tripCount = tripCountMap.at(theta);
1918  EXPECT_TRUE(tripCount == 2);
1919 }
1920 
1921 TEST(ScalarEvolutionTests, ComputeTripCountForInfiniteSLTComparisonWithAffineRecurrence)
1922 {
1923  using namespace jlm::llvm;
1924 
1925  // Arrange
1926  const auto intType = jlm::rvsdg::BitType::Create(32);
1927 
1928  LlvmRvsdgModule rvsdgModule(jlm::util::FilePath(""), "", "");
1929  const auto & graph = rvsdgModule.Rvsdg();
1930 
1931  const auto & c0 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 0);
1932 
1933  const auto theta = jlm::rvsdg::ThetaNode::create(&graph.GetRootRegion());
1934  const auto lv1 = theta->AddLoopVar(c0.output(0));
1935 
1936  const auto & c1 = IntegerConstantOperation::Create(*theta->subregion(), 32, 1);
1937  auto & subNode = jlm::rvsdg::CreateOpNode<IntegerSubOperation>({ lv1.pre, c1.output(0) }, 32);
1938  const auto result = subNode.output(0);
1939 
1940  const auto & c5 = IntegerConstantOperation::Create(*theta->subregion(), 32, 5);
1941  auto & sltNode = jlm::rvsdg::CreateOpNode<IntegerSltOperation>({ result, c5.output(0) }, 32);
1942  const auto matchResult =
1943  jlm::rvsdg::MatchOperation::Create(*sltNode.output(0), { { 1, 1 } }, 0, 2);
1944 
1945  theta->set_predicate(matchResult);
1946  lv1.post->divert_to(result);
1947 
1948  jlm::rvsdg::view(graph, stdout);
1949 
1950  // Act
1951  const auto & tripCountMap = RunScalarEvolution(rvsdgModule).second;
1952 
1953  // Assert
1954  // Negative increment. Since the start value of lv1 (0) is already less than the comparison value
1955  // (5), we get an infinite loop.
1956  EXPECT_EQ(tripCountMap.find(theta), tripCountMap.end());
1957 }
1958 
1959 TEST(ScalarEvolutionTests, ComputeTripCountForInfiniteSGTComparisonWithAffineRecurrence)
1960 {
1961  using namespace jlm::llvm;
1962 
1963  // Arrange
1964  const auto intType = jlm::rvsdg::BitType::Create(32);
1965 
1966  LlvmRvsdgModule rvsdgModule(jlm::util::FilePath(""), "", "");
1967  const auto & graph = rvsdgModule.Rvsdg();
1968 
1969  const auto & c5 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 5);
1970 
1971  const auto theta = jlm::rvsdg::ThetaNode::create(&graph.GetRootRegion());
1972  const auto lv1 = theta->AddLoopVar(c5.output(0));
1973 
1974  const auto & c1 = IntegerConstantOperation::Create(*theta->subregion(), 32, 1);
1975  auto & addNode = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv1.pre, c1.output(0) }, 32);
1976  const auto result = addNode.output(0);
1977 
1978  const auto & c0 = IntegerConstantOperation::Create(*theta->subregion(), 32, 0);
1979  auto & sgeNode = jlm::rvsdg::CreateOpNode<IntegerSgeOperation>({ result, c0.output(0) }, 32);
1980  const auto matchResult =
1981  jlm::rvsdg::MatchOperation::Create(*sgeNode.output(0), { { 1, 1 } }, 0, 2);
1982 
1983  theta->set_predicate(matchResult);
1984  lv1.post->divert_to(result);
1985 
1986  jlm::rvsdg::view(graph, stdout);
1987 
1988  // Act
1989  const auto & tripCountMap = RunScalarEvolution(rvsdgModule).second;
1990 
1991  // Assert
1992  // Positive increment. Since the start value of lv1 (5) is already greater than the comparison
1993  // value (0), we get an infinite loop.
1994  EXPECT_EQ(tripCountMap.find(theta), tripCountMap.end());
1995 }
1996 
1997 TEST(ScalarEvolutionTests, ComputeTripCountForInfiniteNEComparisonWithAffineRecurrence)
1998 {
1999  using namespace jlm::llvm;
2000 
2001  // Arrange
2002  const auto intType = jlm::rvsdg::BitType::Create(32);
2003 
2004  LlvmRvsdgModule rvsdgModule(jlm::util::FilePath(""), "", "");
2005  const auto & graph = rvsdgModule.Rvsdg();
2006 
2007  const auto & c0 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 0);
2008 
2009  const auto theta = jlm::rvsdg::ThetaNode::create(&graph.GetRootRegion());
2010  const auto lv1 = theta->AddLoopVar(c0.output(0));
2011 
2012  const auto & c2 = IntegerConstantOperation::Create(*theta->subregion(), 32, 2);
2013  auto & addNode = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv1.pre, c2.output(0) }, 32);
2014  const auto result = addNode.output(0);
2015 
2016  const auto & c5 = IntegerConstantOperation::Create(*theta->subregion(), 32, 5);
2017  auto & neNode = jlm::rvsdg::CreateOpNode<IntegerNeOperation>({ result, c5.output(0) }, 32);
2018  const auto matchResult =
2019  jlm::rvsdg::MatchOperation::Create(*neNode.output(0), { { 1, 1 } }, 0, 2);
2020 
2021  theta->set_predicate(matchResult);
2022  lv1.post->divert_to(result);
2023 
2024  jlm::rvsdg::view(graph, stdout);
2025 
2026  // Act
2027  const auto & tripCountMap = RunScalarEvolution(rvsdgModule).second;
2028 
2029  // Assert
2030  // Start value of 0, increment by 2. This means that lv1 will never have the value of 5, which
2031  // is the value in the "not equals" comparison. Therefore, we get an infinite loop.
2032  EXPECT_EQ(tripCountMap.find(theta), tripCountMap.end());
2033 }
2034 
2035 TEST(ScalarEvolutionTests, ComputeTripCountForSimpleQuadraticRecurrence)
2036 {
2037  using namespace jlm::llvm;
2038 
2039  // Arrange
2040  const auto intType = jlm::rvsdg::BitType::Create(32);
2041 
2042  LlvmRvsdgModule rvsdgModule(jlm::util::FilePath(""), "", "");
2043  const auto & graph = rvsdgModule.Rvsdg();
2044 
2045  const auto & c0 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 0);
2046  const auto & c1_1 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 1);
2047 
2048  const auto theta = jlm::rvsdg::ThetaNode::create(&graph.GetRootRegion());
2049  const auto lv1 = theta->AddLoopVar(c0.output(0));
2050  const auto lv2 = theta->AddLoopVar(c1_1.output(0));
2051 
2052  const auto & c1_2 = IntegerConstantOperation::Create(*theta->subregion(), 32, 1);
2053  auto & addNode = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv1.pre, c1_2.output(0) }, 32);
2054  const auto res1 = addNode.output(0);
2055 
2056  auto & addNode2 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv2.pre, res1 }, 32);
2057  const auto res2 = addNode2.output(0);
2058 
2059  const auto & c10 = IntegerConstantOperation::Create(*theta->subregion(), 32, 10);
2060  auto & sltNode = jlm::rvsdg::CreateOpNode<IntegerSltOperation>({ res2, c10.output(0) }, 32);
2061  const auto matchResult =
2062  jlm::rvsdg::MatchOperation::Create(*sltNode.output(0), { { 1, 1 } }, 0, 2);
2063 
2064  theta->set_predicate(matchResult);
2065  lv1.post->divert_to(res1);
2066  lv2.post->divert_to(res2);
2067 
2068  jlm::rvsdg::view(graph, stdout);
2069 
2070  // Act
2071  const auto & tripCountMap = RunScalarEvolution(rvsdgModule).second;
2072 
2073  // Assert
2074  EXPECT_NE(tripCountMap.find(theta), tripCountMap.end());
2075  const auto tripCount = tripCountMap.at(theta);
2076  EXPECT_TRUE(tripCount == 4);
2077 }
2078 
2079 TEST(ScalarEvolutionTests, TestTripCountCouldNotCompute)
2080 {
2081  using namespace jlm::llvm;
2082 
2083  // Arrange
2084  const auto intType = jlm::rvsdg::BitType::Create(32);
2085 
2086  LlvmRvsdgModule rvsdgModule(jlm::util::FilePath(""), "", "");
2087  const auto & graph = rvsdgModule.Rvsdg();
2088 
2089  const auto & c2 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 2);
2090  const auto & c3 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 3);
2091  const auto & c4 = IntegerConstantOperation::Create(graph.GetRootRegion(), 32, 4);
2092 
2093  const auto theta = jlm::rvsdg::ThetaNode::create(&graph.GetRootRegion());
2094  const auto lv1 = theta->AddLoopVar(c2.output(0));
2095  const auto lv2 = theta->AddLoopVar(c3.output(0));
2096  const auto lv3 = theta->AddLoopVar(c4.output(0));
2097 
2098  const auto & c1 = IntegerConstantOperation::Create(*theta->subregion(), 32, 1);
2099  auto & addNode1 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv1.pre, c1.output(0) }, 32);
2100  const auto res1 = addNode1.output(0);
2101 
2102  auto & addNode2 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv2.pre, res1 }, 32);
2103  const auto res2 = addNode2.output(0);
2104 
2105  auto & addNode3 = jlm::rvsdg::CreateOpNode<IntegerAddOperation>({ lv3.pre, res2 }, 32);
2106  const auto res3 = addNode3.output(0);
2107 
2108  const auto & c50 = IntegerConstantOperation::Create(*theta->subregion(), 32, 50);
2109  auto & sltNode = jlm::rvsdg::CreateOpNode<IntegerSltOperation>({ res3, c50.output(0) }, 32);
2110  const auto matchResult =
2111  jlm::rvsdg::MatchOperation::Create(*sltNode.output(0), { { 1, 1 } }, 0, 2);
2112 
2113  theta->set_predicate(matchResult);
2114  lv1.post->divert_to(res1);
2115  lv2.post->divert_to(res2);
2116  lv3.post->divert_to(res3);
2117 
2118  jlm::rvsdg::view(graph, stdout);
2119 
2120  // Act
2121  const auto & tripCountMap = RunScalarEvolution(rvsdgModule).second;
2122 
2123  // Assert
2124  // The recurrence is a third degree polynomial ({a,+,b,+,c,+,d}). For these cases, we return could
2125  // not compute, as there is no implementation for solving recurrences with an order greater
2126  // than 2.
2127  EXPECT_EQ(tripCountMap.find(theta), tripCountMap.end());
2128 }
statisticsCollector
static jlm::util::StatisticsCollector statisticsCollector
Definition: CommonNodeEliminationTests.cpp:21
TEST
TEST(ScalarEvolutionTests, NonEvolvingVariable)
Definition: ScalarEvolutionTests.cpp:30
RunScalarEvolution
static std::pair< std::unordered_map< const jlm::rvsdg::Output *, std::unique_ptr< jlm::llvm::SCEVChainRecurrence > >, std::unordered_map< const jlm::rvsdg::ThetaNode *, size_t > > RunScalarEvolution(jlm::rvsdg::RvsdgModule &rvsdgModule)
Definition: ScalarEvolutionTests.cpp:22
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::ConstantDataArray::Create
static jlm::rvsdg::Output * Create(const std::vector< jlm::rvsdg::Output * > &elements)
Definition: operators.hpp:670
jlm::llvm::ConstantStruct::Create
static rvsdg::Output & Create(rvsdg::Region &, const std::vector< rvsdg::Output * > &operands, std::shared_ptr< const rvsdg::Type > resultType)
Definition: operators.hpp:1653
jlm::llvm::DeltaOperation::Create
static std::unique_ptr< DeltaOperation > Create(std::shared_ptr< const rvsdg::Type > type, const std::string &name, const Linkage &linkage, std::string section, bool constant, const size_t alignment)
Definition: delta.hpp:84
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::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::ScalarEvolution::GetChrecMap
std::unordered_map< const rvsdg::Output *, std::unique_ptr< SCEVChainRecurrence > > GetChrecMap() const
Definition: ScalarEvolution.cpp:243
jlm::llvm::ScalarEvolution::Run
void Run(rvsdg::RvsdgModule &rvsdgModule, util::StatisticsCollector &statisticsCollector) override
Perform RVSDG transformation.
Definition: ScalarEvolution.cpp:271
jlm::llvm::ScalarEvolution::GetTripCountMap
std::unordered_map< const rvsdg::ThetaNode *, size_t > GetTripCountMap() const noexcept
Definition: ScalarEvolution.cpp:265
jlm::llvm::StructType::CreateLiteral
static std::shared_ptr< const StructType > CreateLiteral(std::vector< std::shared_ptr< const Type >> types, bool isPacked)
Definition: types.hpp:334
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::DeltaNode::Create
static DeltaNode * Create(rvsdg::Region *parent, std::unique_ptr< DeltaOperation > op)
Definition: delta.hpp:313
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::GraphImport::Create
static GraphImport & Create(Graph &graph, std::shared_ptr< const rvsdg::Type > type, std::string name)
Definition: graph.cpp:36
jlm::rvsdg::Graph::GetRootRegion
Region & GetRootRegion() const noexcept
Definition: graph.hpp:99
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::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
jlm::rvsdg::view
std::string view(const rvsdg::Region *region)
Definition: view.cpp:142
jlm::rvsdg::ThetaNode::LoopVar::output
rvsdg::Output * output
Variable at loop exit (output of theta).
Definition: theta.hpp:66
Generated by doxygen 1.9.1