1// Copyright (c) 2018 Google LLC.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15#include "source/opt/loop_dependence.h"
16
17#include <functional>
18#include <memory>
19#include <numeric>
20#include <string>
21#include <utility>
22#include <vector>
23
24#include "source/opt/instruction.h"
25#include "source/opt/scalar_analysis.h"
26#include "source/opt/scalar_analysis_nodes.h"
27
28namespace spvtools {
29namespace opt {
30
31using SubscriptPair = std::pair<SENode*, SENode*>;
32
33namespace {
34
35// Calculate the greatest common divisor of a & b using Stein's algorithm.
36// https://en.wikipedia.org/wiki/Binary_GCD_algorithm
37int64_t GreatestCommonDivisor(int64_t a, int64_t b) {
38 // Simple cases
39 if (a == b) {
40 return a;
41 } else if (a == 0) {
42 return b;
43 } else if (b == 0) {
44 return a;
45 }
46
47 // Both even
48 if (a % 2 == 0 && b % 2 == 0) {
49 return 2 * GreatestCommonDivisor(a / 2, b / 2);
50 }
51
52 // Even a, odd b
53 if (a % 2 == 0 && b % 2 == 1) {
54 return GreatestCommonDivisor(a / 2, b);
55 }
56
57 // Odd a, even b
58 if (a % 2 == 1 && b % 2 == 0) {
59 return GreatestCommonDivisor(a, b / 2);
60 }
61
62 // Both odd, reduce the larger argument
63 if (a > b) {
64 return GreatestCommonDivisor((a - b) / 2, b);
65 } else {
66 return GreatestCommonDivisor((b - a) / 2, a);
67 }
68}
69
70// Check if node is affine, ie in the form: a0*i0 + a1*i1 + ... an*in + c
71// and contains only the following types of nodes: SERecurrentNode, SEAddNode
72// and SEConstantNode
73bool IsInCorrectFormForGCDTest(SENode* node) {
74 bool children_ok = true;
75
76 if (auto add_node = node->AsSEAddNode()) {
77 for (auto child : add_node->GetChildren()) {
78 children_ok &= IsInCorrectFormForGCDTest(child);
79 }
80 }
81
82 bool this_ok = node->AsSERecurrentNode() || node->AsSEAddNode() ||
83 node->AsSEConstantNode();
84
85 return children_ok && this_ok;
86}
87
88// If |node| is an SERecurrentNode then returns |node| or if |node| is an
89// SEAddNode returns a vector of SERecurrentNode that are its children.
90std::vector<SERecurrentNode*> GetAllTopLevelRecurrences(SENode* node) {
91 auto nodes = std::vector<SERecurrentNode*>{};
92 if (auto recurrent_node = node->AsSERecurrentNode()) {
93 nodes.push_back(recurrent_node);
94 }
95
96 if (auto add_node = node->AsSEAddNode()) {
97 for (auto child : add_node->GetChildren()) {
98 auto child_nodes = GetAllTopLevelRecurrences(child);
99 nodes.insert(nodes.end(), child_nodes.begin(), child_nodes.end());
100 }
101 }
102
103 return nodes;
104}
105
106// If |node| is an SEConstantNode then returns |node| or if |node| is an
107// SEAddNode returns a vector of SEConstantNode that are its children.
108std::vector<SEConstantNode*> GetAllTopLevelConstants(SENode* node) {
109 auto nodes = std::vector<SEConstantNode*>{};
110 if (auto recurrent_node = node->AsSEConstantNode()) {
111 nodes.push_back(recurrent_node);
112 }
113
114 if (auto add_node = node->AsSEAddNode()) {
115 for (auto child : add_node->GetChildren()) {
116 auto child_nodes = GetAllTopLevelConstants(child);
117 nodes.insert(nodes.end(), child_nodes.begin(), child_nodes.end());
118 }
119 }
120
121 return nodes;
122}
123
124bool AreOffsetsAndCoefficientsConstant(
125 const std::vector<SERecurrentNode*>& nodes) {
126 for (auto node : nodes) {
127 if (!node->GetOffset()->AsSEConstantNode() ||
128 !node->GetOffset()->AsSEConstantNode()) {
129 return false;
130 }
131 }
132 return true;
133}
134
135// Fold all SEConstantNode that appear in |recurrences| and |constants| into a
136// single integer value.
137int64_t CalculateConstantTerm(const std::vector<SERecurrentNode*>& recurrences,
138 const std::vector<SEConstantNode*>& constants) {
139 int64_t constant_term = 0;
140 for (auto recurrence : recurrences) {
141 constant_term +=
142 recurrence->GetOffset()->AsSEConstantNode()->FoldToSingleValue();
143 }
144
145 for (auto constant : constants) {
146 constant_term += constant->FoldToSingleValue();
147 }
148
149 return constant_term;
150}
151
152int64_t CalculateGCDFromCoefficients(
153 const std::vector<SERecurrentNode*>& recurrences, int64_t running_gcd) {
154 for (SERecurrentNode* recurrence : recurrences) {
155 auto coefficient = recurrence->GetCoefficient()->AsSEConstantNode();
156
157 running_gcd = GreatestCommonDivisor(
158 running_gcd, std::abs(coefficient->FoldToSingleValue()));
159 }
160
161 return running_gcd;
162}
163
164// Compare 2 fractions while first normalizing them, e.g. 2/4 and 4/8 will both
165// be simplified to 1/2 and then determined to be equal.
166bool NormalizeAndCompareFractions(int64_t numerator_0, int64_t denominator_0,
167 int64_t numerator_1, int64_t denominator_1) {
168 auto gcd_0 =
169 GreatestCommonDivisor(std::abs(numerator_0), std::abs(denominator_0));
170 auto gcd_1 =
171 GreatestCommonDivisor(std::abs(numerator_1), std::abs(denominator_1));
172
173 auto normalized_numerator_0 = numerator_0 / gcd_0;
174 auto normalized_denominator_0 = denominator_0 / gcd_0;
175 auto normalized_numerator_1 = numerator_1 / gcd_1;
176 auto normalized_denominator_1 = denominator_1 / gcd_1;
177
178 return normalized_numerator_0 == normalized_numerator_1 &&
179 normalized_denominator_0 == normalized_denominator_1;
180}
181
182} // namespace
183
184bool LoopDependenceAnalysis::GetDependence(const Instruction* source,
185 const Instruction* destination,
186 DistanceVector* distance_vector) {
187 // Start off by finding and marking all the loops in |loops_| that are
188 // irrelevant to the dependence analysis.
189 MarkUnsusedDistanceEntriesAsIrrelevant(source, destination, distance_vector);
190
191 Instruction* source_access_chain = GetOperandDefinition(source, 0);
192 Instruction* destination_access_chain = GetOperandDefinition(destination, 0);
193
194 auto num_access_chains =
195 (source_access_chain->opcode() == SpvOpAccessChain) +
196 (destination_access_chain->opcode() == SpvOpAccessChain);
197
198 // If neither is an access chain, then they are load/store to a variable.
199 if (num_access_chains == 0) {
200 if (source_access_chain != destination_access_chain) {
201 // Not the same location, report independence
202 return true;
203 } else {
204 // Accessing the same variable
205 for (auto& entry : distance_vector->GetEntries()) {
206 entry = DistanceEntry();
207 }
208 return false;
209 }
210 }
211
212 // If only one is an access chain, it could be accessing a part of a struct
213 if (num_access_chains == 1) {
214 auto source_is_chain = source_access_chain->opcode() == SpvOpAccessChain;
215 auto access_chain =
216 source_is_chain ? source_access_chain : destination_access_chain;
217 auto variable =
218 source_is_chain ? destination_access_chain : source_access_chain;
219
220 auto location_in_chain = GetOperandDefinition(access_chain, 0);
221
222 if (variable != location_in_chain) {
223 // Not the same location, report independence
224 return true;
225 } else {
226 // Accessing the same variable
227 for (auto& entry : distance_vector->GetEntries()) {
228 entry = DistanceEntry();
229 }
230 return false;
231 }
232 }
233
234 // If the access chains aren't collecting from the same structure there is no
235 // dependence.
236 Instruction* source_array = GetOperandDefinition(source_access_chain, 0);
237 Instruction* destination_array =
238 GetOperandDefinition(destination_access_chain, 0);
239
240 // Nested access chains are not supported yet, bail out.
241 if (source_array->opcode() == SpvOpAccessChain ||
242 destination_array->opcode() == SpvOpAccessChain) {
243 for (auto& entry : distance_vector->GetEntries()) {
244 entry = DistanceEntry();
245 }
246 return false;
247 }
248
249 if (source_array != destination_array) {
250 PrintDebug("Proved independence through different arrays.");
251 return true;
252 }
253
254 // To handle multiple subscripts we must get every operand in the access
255 // chains past the first.
256 std::vector<Instruction*> source_subscripts = GetSubscripts(source);
257 std::vector<Instruction*> destination_subscripts = GetSubscripts(destination);
258
259 auto sets_of_subscripts =
260 PartitionSubscripts(source_subscripts, destination_subscripts);
261
262 auto first_coupled = std::partition(
263 std::begin(sets_of_subscripts), std::end(sets_of_subscripts),
264 [](const std::set<std::pair<Instruction*, Instruction*>>& set) {
265 return set.size() == 1;
266 });
267
268 // Go through each subscript testing for independence.
269 // If any subscript results in independence, we prove independence between the
270 // load and store.
271 // If we can't prove independence we store what information we can gather in
272 // a DistanceVector.
273 for (auto it = std::begin(sets_of_subscripts); it < first_coupled; ++it) {
274 auto source_subscript = std::get<0>(*(*it).begin());
275 auto destination_subscript = std::get<1>(*(*it).begin());
276
277 SENode* source_node = scalar_evolution_.SimplifyExpression(
278 scalar_evolution_.AnalyzeInstruction(source_subscript));
279 SENode* destination_node = scalar_evolution_.SimplifyExpression(
280 scalar_evolution_.AnalyzeInstruction(destination_subscript));
281
282 // Check the loops are in a form we support.
283 auto subscript_pair = std::make_pair(source_node, destination_node);
284
285 const Loop* loop = GetLoopForSubscriptPair(subscript_pair);
286 if (loop) {
287 if (!IsSupportedLoop(loop)) {
288 PrintDebug(
289 "GetDependence found an unsupported loop form. Assuming <=> for "
290 "loop.");
291 DistanceEntry* distance_entry =
292 GetDistanceEntryForSubscriptPair(subscript_pair, distance_vector);
293 if (distance_entry) {
294 distance_entry->direction = DistanceEntry::Directions::ALL;
295 }
296 continue;
297 }
298 }
299
300 // If either node is simplified to a CanNotCompute we can't perform any
301 // analysis so must assume <=> dependence and return.
302 if (source_node->GetType() == SENode::CanNotCompute ||
303 destination_node->GetType() == SENode::CanNotCompute) {
304 // Record the <=> dependence if we can get a DistanceEntry
305 PrintDebug(
306 "GetDependence found source_node || destination_node as "
307 "CanNotCompute. Abandoning evaluation for this subscript.");
308 DistanceEntry* distance_entry =
309 GetDistanceEntryForSubscriptPair(subscript_pair, distance_vector);
310 if (distance_entry) {
311 distance_entry->direction = DistanceEntry::Directions::ALL;
312 }
313 continue;
314 }
315
316 // We have no induction variables so can apply a ZIV test.
317 if (IsZIV(subscript_pair)) {
318 PrintDebug("Found a ZIV subscript pair");
319 if (ZIVTest(subscript_pair)) {
320 PrintDebug("Proved independence with ZIVTest.");
321 return true;
322 }
323 }
324
325 // We have only one induction variable so should attempt an SIV test.
326 if (IsSIV(subscript_pair)) {
327 PrintDebug("Found a SIV subscript pair.");
328 if (SIVTest(subscript_pair, distance_vector)) {
329 PrintDebug("Proved independence with SIVTest.");
330 return true;
331 }
332 }
333
334 // We have multiple induction variables so should attempt an MIV test.
335 if (IsMIV(subscript_pair)) {
336 PrintDebug("Found a MIV subscript pair.");
337 if (GCDMIVTest(subscript_pair)) {
338 PrintDebug("Proved independence with the GCD test.");
339 auto current_loops = CollectLoops(source_node, destination_node);
340
341 for (auto current_loop : current_loops) {
342 auto distance_entry =
343 GetDistanceEntryForLoop(current_loop, distance_vector);
344 distance_entry->direction = DistanceEntry::Directions::NONE;
345 }
346 return true;
347 }
348 }
349 }
350
351 for (auto it = first_coupled; it < std::end(sets_of_subscripts); ++it) {
352 auto coupled_instructions = *it;
353 std::vector<SubscriptPair> coupled_subscripts{};
354
355 for (const auto& elem : coupled_instructions) {
356 auto source_subscript = std::get<0>(elem);
357 auto destination_subscript = std::get<1>(elem);
358
359 SENode* source_node = scalar_evolution_.SimplifyExpression(
360 scalar_evolution_.AnalyzeInstruction(source_subscript));
361 SENode* destination_node = scalar_evolution_.SimplifyExpression(
362 scalar_evolution_.AnalyzeInstruction(destination_subscript));
363
364 coupled_subscripts.push_back({source_node, destination_node});
365 }
366
367 auto supported = true;
368
369 for (const auto& subscript : coupled_subscripts) {
370 auto loops = CollectLoops(std::get<0>(subscript), std::get<1>(subscript));
371
372 auto is_subscript_supported =
373 std::all_of(std::begin(loops), std::end(loops),
374 [this](const Loop* l) { return IsSupportedLoop(l); });
375
376 supported = supported && is_subscript_supported;
377 }
378
379 if (DeltaTest(coupled_subscripts, distance_vector)) {
380 return true;
381 }
382 }
383
384 // We were unable to prove independence so must gather all of the direction
385 // information we found.
386 PrintDebug(
387 "Couldn't prove independence.\n"
388 "All possible direction information has been collected in the input "
389 "DistanceVector.");
390
391 return false;
392}
393
394bool LoopDependenceAnalysis::ZIVTest(
395 const std::pair<SENode*, SENode*>& subscript_pair) {
396 auto source = std::get<0>(subscript_pair);
397 auto destination = std::get<1>(subscript_pair);
398
399 PrintDebug("Performing ZIVTest");
400 // If source == destination, dependence with direction = and distance 0.
401 if (source == destination) {
402 PrintDebug("ZIVTest found EQ dependence.");
403 return false;
404 } else {
405 PrintDebug("ZIVTest found independence.");
406 // Otherwise we prove independence.
407 return true;
408 }
409}
410
411bool LoopDependenceAnalysis::SIVTest(
412 const std::pair<SENode*, SENode*>& subscript_pair,
413 DistanceVector* distance_vector) {
414 DistanceEntry* distance_entry =
415 GetDistanceEntryForSubscriptPair(subscript_pair, distance_vector);
416 if (!distance_entry) {
417 PrintDebug(
418 "SIVTest could not find a DistanceEntry for subscript_pair. Exiting");
419 }
420
421 SENode* source_node = std::get<0>(subscript_pair);
422 SENode* destination_node = std::get<1>(subscript_pair);
423
424 int64_t source_induction_count = CountInductionVariables(source_node);
425 int64_t destination_induction_count =
426 CountInductionVariables(destination_node);
427
428 // If the source node has no induction variables we can apply a
429 // WeakZeroSrcTest.
430 if (source_induction_count == 0) {
431 PrintDebug("Found source has no induction variable.");
432 if (WeakZeroSourceSIVTest(
433 source_node, destination_node->AsSERecurrentNode(),
434 destination_node->AsSERecurrentNode()->GetCoefficient(),
435 distance_entry)) {
436 PrintDebug("Proved independence with WeakZeroSourceSIVTest.");
437 distance_entry->dependence_information =
438 DistanceEntry::DependenceInformation::DIRECTION;
439 distance_entry->direction = DistanceEntry::Directions::NONE;
440 return true;
441 }
442 }
443
444 // If the destination has no induction variables we can apply a
445 // WeakZeroDestTest.
446 if (destination_induction_count == 0) {
447 PrintDebug("Found destination has no induction variable.");
448 if (WeakZeroDestinationSIVTest(
449 source_node->AsSERecurrentNode(), destination_node,
450 source_node->AsSERecurrentNode()->GetCoefficient(),
451 distance_entry)) {
452 PrintDebug("Proved independence with WeakZeroDestinationSIVTest.");
453 distance_entry->dependence_information =
454 DistanceEntry::DependenceInformation::DIRECTION;
455 distance_entry->direction = DistanceEntry::Directions::NONE;
456 return true;
457 }
458 }
459
460 // We now need to collect the SERecurrentExpr nodes from source and
461 // destination. We do not handle cases where source or destination have
462 // multiple SERecurrentExpr nodes.
463 std::vector<SERecurrentNode*> source_recurrent_nodes =
464 source_node->CollectRecurrentNodes();
465 std::vector<SERecurrentNode*> destination_recurrent_nodes =
466 destination_node->CollectRecurrentNodes();
467
468 if (source_recurrent_nodes.size() == 1 &&
469 destination_recurrent_nodes.size() == 1) {
470 PrintDebug("Found source and destination have 1 induction variable.");
471 SERecurrentNode* source_recurrent_expr = *source_recurrent_nodes.begin();
472 SERecurrentNode* destination_recurrent_expr =
473 *destination_recurrent_nodes.begin();
474
475 // If the coefficients are identical we can apply a StrongSIVTest.
476 if (source_recurrent_expr->GetCoefficient() ==
477 destination_recurrent_expr->GetCoefficient()) {
478 PrintDebug("Found source and destination share coefficient.");
479 if (StrongSIVTest(source_node, destination_node,
480 source_recurrent_expr->GetCoefficient(),
481 distance_entry)) {
482 PrintDebug("Proved independence with StrongSIVTest");
483 distance_entry->dependence_information =
484 DistanceEntry::DependenceInformation::DIRECTION;
485 distance_entry->direction = DistanceEntry::Directions::NONE;
486 return true;
487 }
488 }
489
490 // If the coefficients are of equal magnitude and opposite sign we can
491 // apply a WeakCrossingSIVTest.
492 if (source_recurrent_expr->GetCoefficient() ==
493 scalar_evolution_.CreateNegation(
494 destination_recurrent_expr->GetCoefficient())) {
495 PrintDebug("Found source coefficient = -destination coefficient.");
496 if (WeakCrossingSIVTest(source_node, destination_node,
497 source_recurrent_expr->GetCoefficient(),
498 distance_entry)) {
499 PrintDebug("Proved independence with WeakCrossingSIVTest");
500 distance_entry->dependence_information =
501 DistanceEntry::DependenceInformation::DIRECTION;
502 distance_entry->direction = DistanceEntry::Directions::NONE;
503 return true;
504 }
505 }
506 }
507
508 return false;
509}
510
511bool LoopDependenceAnalysis::StrongSIVTest(SENode* source, SENode* destination,
512 SENode* coefficient,
513 DistanceEntry* distance_entry) {
514 PrintDebug("Performing StrongSIVTest.");
515 // If both source and destination are SERecurrentNodes we can perform tests
516 // based on distance.
517 // If either source or destination contain value unknown nodes or if one or
518 // both are not SERecurrentNodes we must attempt a symbolic test.
519 std::vector<SEValueUnknown*> source_value_unknown_nodes =
520 source->CollectValueUnknownNodes();
521 std::vector<SEValueUnknown*> destination_value_unknown_nodes =
522 destination->CollectValueUnknownNodes();
523 if (source_value_unknown_nodes.size() > 0 ||
524 destination_value_unknown_nodes.size() > 0) {
525 PrintDebug(
526 "StrongSIVTest found symbolics. Will attempt SymbolicStrongSIVTest.");
527 return SymbolicStrongSIVTest(source, destination, coefficient,
528 distance_entry);
529 }
530
531 if (!source->AsSERecurrentNode() || !destination->AsSERecurrentNode()) {
532 PrintDebug(
533 "StrongSIVTest could not simplify source and destination to "
534 "SERecurrentNodes so will exit.");
535 distance_entry->direction = DistanceEntry::Directions::ALL;
536 return false;
537 }
538
539 // Build an SENode for distance.
540 std::pair<SENode*, SENode*> subscript_pair =
541 std::make_pair(source, destination);
542 const Loop* subscript_loop = GetLoopForSubscriptPair(subscript_pair);
543 SENode* source_constant_term =
544 GetConstantTerm(subscript_loop, source->AsSERecurrentNode());
545 SENode* destination_constant_term =
546 GetConstantTerm(subscript_loop, destination->AsSERecurrentNode());
547 if (!source_constant_term || !destination_constant_term) {
548 PrintDebug(
549 "StrongSIVTest could not collect the constant terms of either source "
550 "or destination so will exit.");
551 return false;
552 }
553 SENode* constant_term_delta =
554 scalar_evolution_.SimplifyExpression(scalar_evolution_.CreateSubtraction(
555 destination_constant_term, source_constant_term));
556
557 // Scalar evolution doesn't perform division, so we must fold to constants and
558 // do it manually.
559 // We must check the offset delta and coefficient are constants.
560 int64_t distance = 0;
561 SEConstantNode* delta_constant = constant_term_delta->AsSEConstantNode();
562 SEConstantNode* coefficient_constant = coefficient->AsSEConstantNode();
563 if (delta_constant && coefficient_constant) {
564 int64_t delta_value = delta_constant->FoldToSingleValue();
565 int64_t coefficient_value = coefficient_constant->FoldToSingleValue();
566 PrintDebug(
567 "StrongSIVTest found delta value and coefficient value as constants "
568 "with values:\n"
569 "\tdelta value: " +
570 ToString(delta_value) +
571 "\n\tcoefficient value: " + ToString(coefficient_value) + "\n");
572 // Check if the distance is not integral to try to prove independence.
573 if (delta_value % coefficient_value != 0) {
574 PrintDebug(
575 "StrongSIVTest proved independence through distance not being an "
576 "integer.");
577 distance_entry->dependence_information =
578 DistanceEntry::DependenceInformation::DIRECTION;
579 distance_entry->direction = DistanceEntry::Directions::NONE;
580 return true;
581 } else {
582 distance = delta_value / coefficient_value;
583 PrintDebug("StrongSIV test found distance as " + ToString(distance));
584 }
585 } else {
586 // If we can't fold delta and coefficient to single values we can't produce
587 // distance.
588 // As a result we can't perform the rest of the pass and must assume
589 // dependence in all directions.
590 PrintDebug("StrongSIVTest could not produce a distance. Must exit.");
591 distance_entry->distance = DistanceEntry::Directions::ALL;
592 return false;
593 }
594
595 // Next we gather the upper and lower bounds as constants if possible. If
596 // distance > upper_bound - lower_bound we prove independence.
597 SENode* lower_bound = GetLowerBound(subscript_loop);
598 SENode* upper_bound = GetUpperBound(subscript_loop);
599 if (lower_bound && upper_bound) {
600 PrintDebug("StrongSIVTest found bounds.");
601 SENode* bounds = scalar_evolution_.SimplifyExpression(
602 scalar_evolution_.CreateSubtraction(upper_bound, lower_bound));
603
604 if (bounds->GetType() == SENode::SENodeType::Constant) {
605 int64_t bounds_value = bounds->AsSEConstantNode()->FoldToSingleValue();
606 PrintDebug(
607 "StrongSIVTest found upper_bound - lower_bound as a constant with "
608 "value " +
609 ToString(bounds_value));
610
611 // If the absolute value of the distance is > upper bound - lower bound
612 // then we prove independence.
613 if (llabs(distance) > llabs(bounds_value)) {
614 PrintDebug(
615 "StrongSIVTest proved independence through distance escaping the "
616 "loop bounds.");
617 distance_entry->dependence_information =
618 DistanceEntry::DependenceInformation::DISTANCE;
619 distance_entry->direction = DistanceEntry::Directions::NONE;
620 distance_entry->distance = distance;
621 return true;
622 }
623 }
624 } else {
625 PrintDebug("StrongSIVTest was unable to gather lower and upper bounds.");
626 }
627
628 // Otherwise we can get a direction as follows
629 // { < if distance > 0
630 // direction = { = if distance == 0
631 // { > if distance < 0
632 PrintDebug(
633 "StrongSIVTest could not prove independence. Gathering direction "
634 "information.");
635 if (distance > 0) {
636 distance_entry->dependence_information =
637 DistanceEntry::DependenceInformation::DISTANCE;
638 distance_entry->direction = DistanceEntry::Directions::LT;
639 distance_entry->distance = distance;
640 return false;
641 }
642 if (distance == 0) {
643 distance_entry->dependence_information =
644 DistanceEntry::DependenceInformation::DISTANCE;
645 distance_entry->direction = DistanceEntry::Directions::EQ;
646 distance_entry->distance = 0;
647 return false;
648 }
649 if (distance < 0) {
650 distance_entry->dependence_information =
651 DistanceEntry::DependenceInformation::DISTANCE;
652 distance_entry->direction = DistanceEntry::Directions::GT;
653 distance_entry->distance = distance;
654 return false;
655 }
656
657 // We were unable to prove independence or discern any additional information
658 // Must assume <=> direction.
659 PrintDebug(
660 "StrongSIVTest was unable to determine any dependence information.");
661 distance_entry->direction = DistanceEntry::Directions::ALL;
662 return false;
663}
664
665bool LoopDependenceAnalysis::SymbolicStrongSIVTest(
666 SENode* source, SENode* destination, SENode* coefficient,
667 DistanceEntry* distance_entry) {
668 PrintDebug("Performing SymbolicStrongSIVTest.");
669 SENode* source_destination_delta = scalar_evolution_.SimplifyExpression(
670 scalar_evolution_.CreateSubtraction(source, destination));
671 // By cancelling out the induction variables by subtracting the source and
672 // destination we can produce an expression of symbolics and constants. This
673 // expression can be compared to the loop bounds to find if the offset is
674 // outwith the bounds.
675 std::pair<SENode*, SENode*> subscript_pair =
676 std::make_pair(source, destination);
677 const Loop* subscript_loop = GetLoopForSubscriptPair(subscript_pair);
678 if (IsProvablyOutsideOfLoopBounds(subscript_loop, source_destination_delta,
679 coefficient)) {
680 PrintDebug(
681 "SymbolicStrongSIVTest proved independence through loop bounds.");
682 distance_entry->dependence_information =
683 DistanceEntry::DependenceInformation::DIRECTION;
684 distance_entry->direction = DistanceEntry::Directions::NONE;
685 return true;
686 }
687 // We were unable to prove independence or discern any additional information.
688 // Must assume <=> direction.
689 PrintDebug(
690 "SymbolicStrongSIVTest was unable to determine any dependence "
691 "information.");
692 distance_entry->direction = DistanceEntry::Directions::ALL;
693 return false;
694}
695
696bool LoopDependenceAnalysis::WeakZeroSourceSIVTest(
697 SENode* source, SERecurrentNode* destination, SENode* coefficient,
698 DistanceEntry* distance_entry) {
699 PrintDebug("Performing WeakZeroSourceSIVTest.");
700 std::pair<SENode*, SENode*> subscript_pair =
701 std::make_pair(source, destination);
702 const Loop* subscript_loop = GetLoopForSubscriptPair(subscript_pair);
703 // Build an SENode for distance.
704 SENode* destination_constant_term =
705 GetConstantTerm(subscript_loop, destination);
706 SENode* delta = scalar_evolution_.SimplifyExpression(
707 scalar_evolution_.CreateSubtraction(source, destination_constant_term));
708
709 // Scalar evolution doesn't perform division, so we must fold to constants and
710 // do it manually.
711 int64_t distance = 0;
712 SEConstantNode* delta_constant = delta->AsSEConstantNode();
713 SEConstantNode* coefficient_constant = coefficient->AsSEConstantNode();
714 if (delta_constant && coefficient_constant) {
715 PrintDebug(
716 "WeakZeroSourceSIVTest folding delta and coefficient to constants.");
717 int64_t delta_value = delta_constant->FoldToSingleValue();
718 int64_t coefficient_value = coefficient_constant->FoldToSingleValue();
719 // Check if the distance is not integral.
720 if (delta_value % coefficient_value != 0) {
721 PrintDebug(
722 "WeakZeroSourceSIVTest proved independence through distance not "
723 "being an integer.");
724 distance_entry->dependence_information =
725 DistanceEntry::DependenceInformation::DIRECTION;
726 distance_entry->direction = DistanceEntry::Directions::NONE;
727 return true;
728 } else {
729 distance = delta_value / coefficient_value;
730 PrintDebug(
731 "WeakZeroSourceSIVTest calculated distance with the following "
732 "values\n"
733 "\tdelta value: " +
734 ToString(delta_value) +
735 "\n\tcoefficient value: " + ToString(coefficient_value) +
736 "\n\tdistance: " + ToString(distance) + "\n");
737 }
738 } else {
739 PrintDebug(
740 "WeakZeroSourceSIVTest was unable to fold delta and coefficient to "
741 "constants.");
742 }
743
744 // If we can prove the distance is outside the bounds we prove independence.
745 SEConstantNode* lower_bound =
746 GetLowerBound(subscript_loop)->AsSEConstantNode();
747 SEConstantNode* upper_bound =
748 GetUpperBound(subscript_loop)->AsSEConstantNode();
749 if (lower_bound && upper_bound) {
750 PrintDebug("WeakZeroSourceSIVTest found bounds as SEConstantNodes.");
751 int64_t lower_bound_value = lower_bound->FoldToSingleValue();
752 int64_t upper_bound_value = upper_bound->FoldToSingleValue();
753 if (!IsWithinBounds(llabs(distance), lower_bound_value,
754 upper_bound_value)) {
755 PrintDebug(
756 "WeakZeroSourceSIVTest proved independence through distance escaping "
757 "the loop bounds.");
758 PrintDebug(
759 "Bound values were as follow\n"
760 "\tlower bound value: " +
761 ToString(lower_bound_value) +
762 "\n\tupper bound value: " + ToString(upper_bound_value) +
763 "\n\tdistance value: " + ToString(distance) + "\n");
764 distance_entry->dependence_information =
765 DistanceEntry::DependenceInformation::DISTANCE;
766 distance_entry->direction = DistanceEntry::Directions::NONE;
767 distance_entry->distance = distance;
768 return true;
769 }
770 } else {
771 PrintDebug(
772 "WeakZeroSourceSIVTest was unable to find lower and upper bound as "
773 "SEConstantNodes.");
774 }
775
776 // Now we want to see if we can detect to peel the first or last iterations.
777
778 // We get the FirstTripValue as GetFirstTripInductionNode() +
779 // GetConstantTerm(destination)
780 SENode* first_trip_SENode =
781 scalar_evolution_.SimplifyExpression(scalar_evolution_.CreateAddNode(
782 GetFirstTripInductionNode(subscript_loop),
783 GetConstantTerm(subscript_loop, destination)));
784
785 // If source == FirstTripValue, peel_first.
786 if (first_trip_SENode) {
787 PrintDebug("WeakZeroSourceSIVTest built first_trip_SENode.");
788 if (first_trip_SENode->AsSEConstantNode()) {
789 PrintDebug(
790 "WeakZeroSourceSIVTest has found first_trip_SENode as an "
791 "SEConstantNode with value: " +
792 ToString(first_trip_SENode->AsSEConstantNode()->FoldToSingleValue()) +
793 "\n");
794 }
795 if (source == first_trip_SENode) {
796 // We have found that peeling the first iteration will break dependency.
797 PrintDebug(
798 "WeakZeroSourceSIVTest has found peeling first iteration will break "
799 "dependency");
800 distance_entry->dependence_information =
801 DistanceEntry::DependenceInformation::PEEL;
802 distance_entry->peel_first = true;
803 return false;
804 }
805 } else {
806 PrintDebug("WeakZeroSourceSIVTest was unable to build first_trip_SENode");
807 }
808
809 // We get the LastTripValue as GetFinalTripInductionNode(coefficient) +
810 // GetConstantTerm(destination)
811 SENode* final_trip_SENode =
812 scalar_evolution_.SimplifyExpression(scalar_evolution_.CreateAddNode(
813 GetFinalTripInductionNode(subscript_loop, coefficient),
814 GetConstantTerm(subscript_loop, destination)));
815
816 // If source == LastTripValue, peel_last.
817 if (final_trip_SENode) {
818 PrintDebug("WeakZeroSourceSIVTest built final_trip_SENode.");
819 if (first_trip_SENode->AsSEConstantNode()) {
820 PrintDebug(
821 "WeakZeroSourceSIVTest has found final_trip_SENode as an "
822 "SEConstantNode with value: " +
823 ToString(final_trip_SENode->AsSEConstantNode()->FoldToSingleValue()) +
824 "\n");
825 }
826 if (source == final_trip_SENode) {
827 // We have found that peeling the last iteration will break dependency.
828 PrintDebug(
829 "WeakZeroSourceSIVTest has found peeling final iteration will break "
830 "dependency");
831 distance_entry->dependence_information =
832 DistanceEntry::DependenceInformation::PEEL;
833 distance_entry->peel_last = true;
834 return false;
835 }
836 } else {
837 PrintDebug("WeakZeroSourceSIVTest was unable to build final_trip_SENode");
838 }
839
840 // We were unable to prove independence or discern any additional information.
841 // Must assume <=> direction.
842 PrintDebug(
843 "WeakZeroSourceSIVTest was unable to determine any dependence "
844 "information.");
845 distance_entry->direction = DistanceEntry::Directions::ALL;
846 return false;
847}
848
849bool LoopDependenceAnalysis::WeakZeroDestinationSIVTest(
850 SERecurrentNode* source, SENode* destination, SENode* coefficient,
851 DistanceEntry* distance_entry) {
852 PrintDebug("Performing WeakZeroDestinationSIVTest.");
853 // Build an SENode for distance.
854 std::pair<SENode*, SENode*> subscript_pair =
855 std::make_pair(source, destination);
856 const Loop* subscript_loop = GetLoopForSubscriptPair(subscript_pair);
857 SENode* source_constant_term = GetConstantTerm(subscript_loop, source);
858 SENode* delta = scalar_evolution_.SimplifyExpression(
859 scalar_evolution_.CreateSubtraction(destination, source_constant_term));
860
861 // Scalar evolution doesn't perform division, so we must fold to constants and
862 // do it manually.
863 int64_t distance = 0;
864 SEConstantNode* delta_constant = delta->AsSEConstantNode();
865 SEConstantNode* coefficient_constant = coefficient->AsSEConstantNode();
866 if (delta_constant && coefficient_constant) {
867 PrintDebug(
868 "WeakZeroDestinationSIVTest folding delta and coefficient to "
869 "constants.");
870 int64_t delta_value = delta_constant->FoldToSingleValue();
871 int64_t coefficient_value = coefficient_constant->FoldToSingleValue();
872 // Check if the distance is not integral.
873 if (delta_value % coefficient_value != 0) {
874 PrintDebug(
875 "WeakZeroDestinationSIVTest proved independence through distance not "
876 "being an integer.");
877 distance_entry->dependence_information =
878 DistanceEntry::DependenceInformation::DIRECTION;
879 distance_entry->direction = DistanceEntry::Directions::NONE;
880 return true;
881 } else {
882 distance = delta_value / coefficient_value;
883 PrintDebug(
884 "WeakZeroDestinationSIVTest calculated distance with the following "
885 "values\n"
886 "\tdelta value: " +
887 ToString(delta_value) +
888 "\n\tcoefficient value: " + ToString(coefficient_value) +
889 "\n\tdistance: " + ToString(distance) + "\n");
890 }
891 } else {
892 PrintDebug(
893 "WeakZeroDestinationSIVTest was unable to fold delta and coefficient "
894 "to constants.");
895 }
896
897 // If we can prove the distance is outside the bounds we prove independence.
898 SEConstantNode* lower_bound =
899 GetLowerBound(subscript_loop)->AsSEConstantNode();
900 SEConstantNode* upper_bound =
901 GetUpperBound(subscript_loop)->AsSEConstantNode();
902 if (lower_bound && upper_bound) {
903 PrintDebug("WeakZeroDestinationSIVTest found bounds as SEConstantNodes.");
904 int64_t lower_bound_value = lower_bound->FoldToSingleValue();
905 int64_t upper_bound_value = upper_bound->FoldToSingleValue();
906 if (!IsWithinBounds(llabs(distance), lower_bound_value,
907 upper_bound_value)) {
908 PrintDebug(
909 "WeakZeroDestinationSIVTest proved independence through distance "
910 "escaping the loop bounds.");
911 PrintDebug(
912 "Bound values were as follows\n"
913 "\tlower bound value: " +
914 ToString(lower_bound_value) +
915 "\n\tupper bound value: " + ToString(upper_bound_value) +
916 "\n\tdistance value: " + ToString(distance));
917 distance_entry->dependence_information =
918 DistanceEntry::DependenceInformation::DISTANCE;
919 distance_entry->direction = DistanceEntry::Directions::NONE;
920 distance_entry->distance = distance;
921 return true;
922 }
923 } else {
924 PrintDebug(
925 "WeakZeroDestinationSIVTest was unable to find lower and upper bound "
926 "as SEConstantNodes.");
927 }
928
929 // Now we want to see if we can detect to peel the first or last iterations.
930
931 // We get the FirstTripValue as GetFirstTripInductionNode() +
932 // GetConstantTerm(source)
933 SENode* first_trip_SENode = scalar_evolution_.SimplifyExpression(
934 scalar_evolution_.CreateAddNode(GetFirstTripInductionNode(subscript_loop),
935 GetConstantTerm(subscript_loop, source)));
936
937 // If destination == FirstTripValue, peel_first.
938 if (first_trip_SENode) {
939 PrintDebug("WeakZeroDestinationSIVTest built first_trip_SENode.");
940 if (first_trip_SENode->AsSEConstantNode()) {
941 PrintDebug(
942 "WeakZeroDestinationSIVTest has found first_trip_SENode as an "
943 "SEConstantNode with value: " +
944 ToString(first_trip_SENode->AsSEConstantNode()->FoldToSingleValue()) +
945 "\n");
946 }
947 if (destination == first_trip_SENode) {
948 // We have found that peeling the first iteration will break dependency.
949 PrintDebug(
950 "WeakZeroDestinationSIVTest has found peeling first iteration will "
951 "break dependency");
952 distance_entry->dependence_information =
953 DistanceEntry::DependenceInformation::PEEL;
954 distance_entry->peel_first = true;
955 return false;
956 }
957 } else {
958 PrintDebug(
959 "WeakZeroDestinationSIVTest was unable to build first_trip_SENode");
960 }
961
962 // We get the LastTripValue as GetFinalTripInductionNode(coefficient) +
963 // GetConstantTerm(source)
964 SENode* final_trip_SENode =
965 scalar_evolution_.SimplifyExpression(scalar_evolution_.CreateAddNode(
966 GetFinalTripInductionNode(subscript_loop, coefficient),
967 GetConstantTerm(subscript_loop, source)));
968
969 // If destination == LastTripValue, peel_last.
970 if (final_trip_SENode) {
971 PrintDebug("WeakZeroDestinationSIVTest built final_trip_SENode.");
972 if (final_trip_SENode->AsSEConstantNode()) {
973 PrintDebug(
974 "WeakZeroDestinationSIVTest has found final_trip_SENode as an "
975 "SEConstantNode with value: " +
976 ToString(final_trip_SENode->AsSEConstantNode()->FoldToSingleValue()) +
977 "\n");
978 }
979 if (destination == final_trip_SENode) {
980 // We have found that peeling the last iteration will break dependency.
981 PrintDebug(
982 "WeakZeroDestinationSIVTest has found peeling final iteration will "
983 "break dependency");
984 distance_entry->dependence_information =
985 DistanceEntry::DependenceInformation::PEEL;
986 distance_entry->peel_last = true;
987 return false;
988 }
989 } else {
990 PrintDebug(
991 "WeakZeroDestinationSIVTest was unable to build final_trip_SENode");
992 }
993
994 // We were unable to prove independence or discern any additional information.
995 // Must assume <=> direction.
996 PrintDebug(
997 "WeakZeroDestinationSIVTest was unable to determine any dependence "
998 "information.");
999 distance_entry->direction = DistanceEntry::Directions::ALL;
1000 return false;
1001}
1002
1003bool LoopDependenceAnalysis::WeakCrossingSIVTest(
1004 SENode* source, SENode* destination, SENode* coefficient,
1005 DistanceEntry* distance_entry) {
1006 PrintDebug("Performing WeakCrossingSIVTest.");
1007 // We currently can't handle symbolic WeakCrossingSIVTests. If either source
1008 // or destination are not SERecurrentNodes we must exit.
1009 if (!source->AsSERecurrentNode() || !destination->AsSERecurrentNode()) {
1010 PrintDebug(
1011 "WeakCrossingSIVTest found source or destination != SERecurrentNode. "
1012 "Exiting");
1013 distance_entry->direction = DistanceEntry::Directions::ALL;
1014 return false;
1015 }
1016
1017 // Build an SENode for distance.
1018 SENode* offset_delta =
1019 scalar_evolution_.SimplifyExpression(scalar_evolution_.CreateSubtraction(
1020 destination->AsSERecurrentNode()->GetOffset(),
1021 source->AsSERecurrentNode()->GetOffset()));
1022
1023 // Scalar evolution doesn't perform division, so we must fold to constants and
1024 // do it manually.
1025 int64_t distance = 0;
1026 SEConstantNode* delta_constant = offset_delta->AsSEConstantNode();
1027 SEConstantNode* coefficient_constant = coefficient->AsSEConstantNode();
1028 if (delta_constant && coefficient_constant) {
1029 PrintDebug(
1030 "WeakCrossingSIVTest folding offset_delta and coefficient to "
1031 "constants.");
1032 int64_t delta_value = delta_constant->FoldToSingleValue();
1033 int64_t coefficient_value = coefficient_constant->FoldToSingleValue();
1034 // Check if the distance is not integral or if it has a non-integral part
1035 // equal to 1/2.
1036 if (delta_value % (2 * coefficient_value) != 0 &&
1037 static_cast<float>(delta_value % (2 * coefficient_value)) /
1038 static_cast<float>(2 * coefficient_value) !=
1039 0.5) {
1040 PrintDebug(
1041 "WeakCrossingSIVTest proved independence through distance escaping "
1042 "the loop bounds.");
1043 distance_entry->dependence_information =
1044 DistanceEntry::DependenceInformation::DIRECTION;
1045 distance_entry->direction = DistanceEntry::Directions::NONE;
1046 return true;
1047 } else {
1048 distance = delta_value / (2 * coefficient_value);
1049 }
1050
1051 if (distance == 0) {
1052 PrintDebug("WeakCrossingSIVTest found EQ dependence.");
1053 distance_entry->dependence_information =
1054 DistanceEntry::DependenceInformation::DISTANCE;
1055 distance_entry->direction = DistanceEntry::Directions::EQ;
1056 distance_entry->distance = 0;
1057 return false;
1058 }
1059 } else {
1060 PrintDebug(
1061 "WeakCrossingSIVTest was unable to fold offset_delta and coefficient "
1062 "to constants.");
1063 }
1064
1065 // We were unable to prove independence or discern any additional information.
1066 // Must assume <=> direction.
1067 PrintDebug(
1068 "WeakCrossingSIVTest was unable to determine any dependence "
1069 "information.");
1070 distance_entry->direction = DistanceEntry::Directions::ALL;
1071 return false;
1072}
1073
1074// Perform the GCD test if both, the source and the destination nodes, are in
1075// the form a0*i0 + a1*i1 + ... an*in + c.
1076bool LoopDependenceAnalysis::GCDMIVTest(
1077 const std::pair<SENode*, SENode*>& subscript_pair) {
1078 auto source = std::get<0>(subscript_pair);
1079 auto destination = std::get<1>(subscript_pair);
1080
1081 // Bail out if source/destination is in an unexpected form.
1082 if (!IsInCorrectFormForGCDTest(source) ||
1083 !IsInCorrectFormForGCDTest(destination)) {
1084 return false;
1085 }
1086
1087 auto source_recurrences = GetAllTopLevelRecurrences(source);
1088 auto dest_recurrences = GetAllTopLevelRecurrences(destination);
1089
1090 // Bail out if all offsets and coefficients aren't constant.
1091 if (!AreOffsetsAndCoefficientsConstant(source_recurrences) ||
1092 !AreOffsetsAndCoefficientsConstant(dest_recurrences)) {
1093 return false;
1094 }
1095
1096 // Calculate the GCD of all coefficients.
1097 auto source_constants = GetAllTopLevelConstants(source);
1098 int64_t source_constant =
1099 CalculateConstantTerm(source_recurrences, source_constants);
1100
1101 auto dest_constants = GetAllTopLevelConstants(destination);
1102 int64_t destination_constant =
1103 CalculateConstantTerm(dest_recurrences, dest_constants);
1104
1105 int64_t delta = std::abs(source_constant - destination_constant);
1106
1107 int64_t running_gcd = 0;
1108
1109 running_gcd = CalculateGCDFromCoefficients(source_recurrences, running_gcd);
1110 running_gcd = CalculateGCDFromCoefficients(dest_recurrences, running_gcd);
1111
1112 return delta % running_gcd != 0;
1113}
1114
1115using PartitionedSubscripts =
1116 std::vector<std::set<std::pair<Instruction*, Instruction*>>>;
1117PartitionedSubscripts LoopDependenceAnalysis::PartitionSubscripts(
1118 const std::vector<Instruction*>& source_subscripts,
1119 const std::vector<Instruction*>& destination_subscripts) {
1120 PartitionedSubscripts partitions{};
1121
1122 auto num_subscripts = source_subscripts.size();
1123
1124 // Create initial partitions with one subscript pair per partition.
1125 for (size_t i = 0; i < num_subscripts; ++i) {
1126 partitions.push_back({{source_subscripts[i], destination_subscripts[i]}});
1127 }
1128
1129 // Iterate over the loops to create all partitions
1130 for (auto loop : loops_) {
1131 int64_t k = -1;
1132
1133 for (size_t j = 0; j < partitions.size(); ++j) {
1134 auto& current_partition = partitions[j];
1135
1136 // Does |loop| appear in |current_partition|
1137 auto it = std::find_if(
1138 current_partition.begin(), current_partition.end(),
1139 [loop,
1140 this](const std::pair<Instruction*, Instruction*>& elem) -> bool {
1141 auto source_recurrences =
1142 scalar_evolution_.AnalyzeInstruction(std::get<0>(elem))
1143 ->CollectRecurrentNodes();
1144 auto destination_recurrences =
1145 scalar_evolution_.AnalyzeInstruction(std::get<1>(elem))
1146 ->CollectRecurrentNodes();
1147
1148 source_recurrences.insert(source_recurrences.end(),
1149 destination_recurrences.begin(),
1150 destination_recurrences.end());
1151
1152 auto loops_in_pair = CollectLoops(source_recurrences);
1153 auto end_it = loops_in_pair.end();
1154
1155 return std::find(loops_in_pair.begin(), end_it, loop) != end_it;
1156 });
1157
1158 auto has_loop = it != current_partition.end();
1159
1160 if (has_loop) {
1161 if (k == -1) {
1162 k = j;
1163 } else {
1164 // Add |partitions[j]| to |partitions[k]| and discard |partitions[j]|
1165 partitions[static_cast<size_t>(k)].insert(current_partition.begin(),
1166 current_partition.end());
1167 current_partition.clear();
1168 }
1169 }
1170 }
1171 }
1172
1173 // Remove empty (discarded) partitions
1174 partitions.erase(
1175 std::remove_if(
1176 partitions.begin(), partitions.end(),
1177 [](const std::set<std::pair<Instruction*, Instruction*>>& partition) {
1178 return partition.empty();
1179 }),
1180 partitions.end());
1181
1182 return partitions;
1183}
1184
1185Constraint* LoopDependenceAnalysis::IntersectConstraints(
1186 Constraint* constraint_0, Constraint* constraint_1,
1187 const SENode* lower_bound, const SENode* upper_bound) {
1188 if (constraint_0->AsDependenceNone()) {
1189 return constraint_1;
1190 } else if (constraint_1->AsDependenceNone()) {
1191 return constraint_0;
1192 }
1193
1194 // Both constraints are distances. Either the same distance or independent.
1195 if (constraint_0->AsDependenceDistance() &&
1196 constraint_1->AsDependenceDistance()) {
1197 auto dist_0 = constraint_0->AsDependenceDistance();
1198 auto dist_1 = constraint_1->AsDependenceDistance();
1199
1200 if (*dist_0->GetDistance() == *dist_1->GetDistance()) {
1201 return constraint_0;
1202 } else {
1203 return make_constraint<DependenceEmpty>();
1204 }
1205 }
1206
1207 // Both constraints are points. Either the same point or independent.
1208 if (constraint_0->AsDependencePoint() && constraint_1->AsDependencePoint()) {
1209 auto point_0 = constraint_0->AsDependencePoint();
1210 auto point_1 = constraint_1->AsDependencePoint();
1211
1212 if (*point_0->GetSource() == *point_1->GetSource() &&
1213 *point_0->GetDestination() == *point_1->GetDestination()) {
1214 return constraint_0;
1215 } else {
1216 return make_constraint<DependenceEmpty>();
1217 }
1218 }
1219
1220 // Both constraints are lines/distances.
1221 if ((constraint_0->AsDependenceDistance() ||
1222 constraint_0->AsDependenceLine()) &&
1223 (constraint_1->AsDependenceDistance() ||
1224 constraint_1->AsDependenceLine())) {
1225 auto is_distance_0 = constraint_0->AsDependenceDistance() != nullptr;
1226 auto is_distance_1 = constraint_1->AsDependenceDistance() != nullptr;
1227
1228 auto a0 = is_distance_0 ? scalar_evolution_.CreateConstant(1)
1229 : constraint_0->AsDependenceLine()->GetA();
1230 auto b0 = is_distance_0 ? scalar_evolution_.CreateConstant(-1)
1231 : constraint_0->AsDependenceLine()->GetB();
1232 auto c0 =
1233 is_distance_0
1234 ? scalar_evolution_.SimplifyExpression(
1235 scalar_evolution_.CreateNegation(
1236 constraint_0->AsDependenceDistance()->GetDistance()))
1237 : constraint_0->AsDependenceLine()->GetC();
1238
1239 auto a1 = is_distance_1 ? scalar_evolution_.CreateConstant(1)
1240 : constraint_1->AsDependenceLine()->GetA();
1241 auto b1 = is_distance_1 ? scalar_evolution_.CreateConstant(-1)
1242 : constraint_1->AsDependenceLine()->GetB();
1243 auto c1 =
1244 is_distance_1
1245 ? scalar_evolution_.SimplifyExpression(
1246 scalar_evolution_.CreateNegation(
1247 constraint_1->AsDependenceDistance()->GetDistance()))
1248 : constraint_1->AsDependenceLine()->GetC();
1249
1250 if (a0->AsSEConstantNode() && b0->AsSEConstantNode() &&
1251 c0->AsSEConstantNode() && a1->AsSEConstantNode() &&
1252 b1->AsSEConstantNode() && c1->AsSEConstantNode()) {
1253 auto constant_a0 = a0->AsSEConstantNode()->FoldToSingleValue();
1254 auto constant_b0 = b0->AsSEConstantNode()->FoldToSingleValue();
1255 auto constant_c0 = c0->AsSEConstantNode()->FoldToSingleValue();
1256
1257 auto constant_a1 = a1->AsSEConstantNode()->FoldToSingleValue();
1258 auto constant_b1 = b1->AsSEConstantNode()->FoldToSingleValue();
1259 auto constant_c1 = c1->AsSEConstantNode()->FoldToSingleValue();
1260
1261 // a & b can't both be zero, otherwise it wouldn't be line.
1262 if (NormalizeAndCompareFractions(constant_a0, constant_b0, constant_a1,
1263 constant_b1)) {
1264 // Slopes are equal, either parallel lines or the same line.
1265
1266 if (constant_b0 == 0 && constant_b1 == 0) {
1267 if (NormalizeAndCompareFractions(constant_c0, constant_a0,
1268 constant_c1, constant_a1)) {
1269 return constraint_0;
1270 }
1271
1272 return make_constraint<DependenceEmpty>();
1273 } else if (NormalizeAndCompareFractions(constant_c0, constant_b0,
1274 constant_c1, constant_b1)) {
1275 // Same line.
1276 return constraint_0;
1277 } else {
1278 // Parallel lines can't intersect, report independence.
1279 return make_constraint<DependenceEmpty>();
1280 }
1281
1282 } else {
1283 // Lines are not parallel, therefore, they must intersect.
1284
1285 // Calculate intersection.
1286 if (upper_bound->AsSEConstantNode() &&
1287 lower_bound->AsSEConstantNode()) {
1288 auto constant_lower_bound =
1289 lower_bound->AsSEConstantNode()->FoldToSingleValue();
1290 auto constant_upper_bound =
1291 upper_bound->AsSEConstantNode()->FoldToSingleValue();
1292
1293 auto up = constant_b1 * constant_c0 - constant_b0 * constant_c1;
1294 // Both b or both a can't be 0, so down is never 0
1295 // otherwise would have entered the parallel line section.
1296 auto down = constant_b1 * constant_a0 - constant_b0 * constant_a1;
1297
1298 auto x_coord = up / down;
1299
1300 int64_t y_coord = 0;
1301 int64_t arg1 = 0;
1302 int64_t const_b_to_use = 0;
1303
1304 if (constant_b1 != 0) {
1305 arg1 = constant_c1 - constant_a1 * x_coord;
1306 y_coord = arg1 / constant_b1;
1307 const_b_to_use = constant_b1;
1308 } else if (constant_b0 != 0) {
1309 arg1 = constant_c0 - constant_a0 * x_coord;
1310 y_coord = arg1 / constant_b0;
1311 const_b_to_use = constant_b0;
1312 }
1313
1314 if (up % down == 0 &&
1315 arg1 % const_b_to_use == 0 && // Coordinates are integers.
1316 constant_lower_bound <=
1317 x_coord && // x_coord is within loop bounds.
1318 x_coord <= constant_upper_bound &&
1319 constant_lower_bound <=
1320 y_coord && // y_coord is within loop bounds.
1321 y_coord <= constant_upper_bound) {
1322 // Lines intersect at integer coordinates.
1323 return make_constraint<DependencePoint>(
1324 scalar_evolution_.CreateConstant(x_coord),
1325 scalar_evolution_.CreateConstant(y_coord),
1326 constraint_0->GetLoop());
1327
1328 } else {
1329 return make_constraint<DependenceEmpty>();
1330 }
1331
1332 } else {
1333 // Not constants, bail out.
1334 return make_constraint<DependenceNone>();
1335 }
1336 }
1337
1338 } else {
1339 // Not constants, bail out.
1340 return make_constraint<DependenceNone>();
1341 }
1342 }
1343
1344 // One constraint is a line/distance and the other is a point.
1345 if ((constraint_0->AsDependencePoint() &&
1346 (constraint_1->AsDependenceLine() ||
1347 constraint_1->AsDependenceDistance())) ||
1348 (constraint_1->AsDependencePoint() &&
1349 (constraint_0->AsDependenceLine() ||
1350 constraint_0->AsDependenceDistance()))) {
1351 auto point_0 = constraint_0->AsDependencePoint() != nullptr;
1352
1353 auto point = point_0 ? constraint_0->AsDependencePoint()
1354 : constraint_1->AsDependencePoint();
1355
1356 auto line_or_distance = point_0 ? constraint_1 : constraint_0;
1357
1358 auto is_distance = line_or_distance->AsDependenceDistance() != nullptr;
1359
1360 auto a = is_distance ? scalar_evolution_.CreateConstant(1)
1361 : line_or_distance->AsDependenceLine()->GetA();
1362 auto b = is_distance ? scalar_evolution_.CreateConstant(-1)
1363 : line_or_distance->AsDependenceLine()->GetB();
1364 auto c =
1365 is_distance
1366 ? scalar_evolution_.SimplifyExpression(
1367 scalar_evolution_.CreateNegation(
1368 line_or_distance->AsDependenceDistance()->GetDistance()))
1369 : line_or_distance->AsDependenceLine()->GetC();
1370
1371 auto x = point->GetSource();
1372 auto y = point->GetDestination();
1373
1374 if (a->AsSEConstantNode() && b->AsSEConstantNode() &&
1375 c->AsSEConstantNode() && x->AsSEConstantNode() &&
1376 y->AsSEConstantNode()) {
1377 auto constant_a = a->AsSEConstantNode()->FoldToSingleValue();
1378 auto constant_b = b->AsSEConstantNode()->FoldToSingleValue();
1379 auto constant_c = c->AsSEConstantNode()->FoldToSingleValue();
1380
1381 auto constant_x = x->AsSEConstantNode()->FoldToSingleValue();
1382 auto constant_y = y->AsSEConstantNode()->FoldToSingleValue();
1383
1384 auto left_hand_side = constant_a * constant_x + constant_b * constant_y;
1385
1386 if (left_hand_side == constant_c) {
1387 // Point is on line, return point
1388 return point_0 ? constraint_0 : constraint_1;
1389 } else {
1390 // Point not on line, report independence (empty constraint).
1391 return make_constraint<DependenceEmpty>();
1392 }
1393
1394 } else {
1395 // Not constants, bail out.
1396 return make_constraint<DependenceNone>();
1397 }
1398 }
1399
1400 return nullptr;
1401}
1402
1403// Propagate constraints function as described in section 5 of Practical
1404// Dependence Testing, Goff, Kennedy, Tseng, 1991.
1405SubscriptPair LoopDependenceAnalysis::PropagateConstraints(
1406 const SubscriptPair& subscript_pair,
1407 const std::vector<Constraint*>& constraints) {
1408 SENode* new_first = subscript_pair.first;
1409 SENode* new_second = subscript_pair.second;
1410
1411 for (auto& constraint : constraints) {
1412 // In the paper this is a[k]. We're extracting the coefficient ('a') of a
1413 // recurrent expression with respect to the loop 'k'.
1414 SENode* coefficient_of_recurrent =
1415 scalar_evolution_.GetCoefficientFromRecurrentTerm(
1416 new_first, constraint->GetLoop());
1417
1418 // In the paper this is a'[k].
1419 SENode* coefficient_of_recurrent_prime =
1420 scalar_evolution_.GetCoefficientFromRecurrentTerm(
1421 new_second, constraint->GetLoop());
1422
1423 if (constraint->GetType() == Constraint::Distance) {
1424 DependenceDistance* as_distance = constraint->AsDependenceDistance();
1425
1426 // In the paper this is a[k]*d
1427 SENode* rhs = scalar_evolution_.CreateMultiplyNode(
1428 coefficient_of_recurrent, as_distance->GetDistance());
1429
1430 // In the paper this is a[k] <- 0
1431 SENode* zeroed_coefficient =
1432 scalar_evolution_.BuildGraphWithoutRecurrentTerm(
1433 new_first, constraint->GetLoop());
1434
1435 // In the paper this is e <- e - a[k]*d.
1436 new_first = scalar_evolution_.CreateSubtraction(zeroed_coefficient, rhs);
1437 new_first = scalar_evolution_.SimplifyExpression(new_first);
1438
1439 // In the paper this is a'[k] - a[k].
1440 SENode* new_child = scalar_evolution_.SimplifyExpression(
1441 scalar_evolution_.CreateSubtraction(coefficient_of_recurrent_prime,
1442 coefficient_of_recurrent));
1443
1444 // In the paper this is a'[k]'i[k].
1445 SERecurrentNode* prime_recurrent =
1446 scalar_evolution_.GetRecurrentTerm(new_second, constraint->GetLoop());
1447
1448 if (!prime_recurrent) continue;
1449
1450 // As we hash the nodes we need to create a new node when we update a
1451 // child.
1452 SENode* new_recurrent = scalar_evolution_.CreateRecurrentExpression(
1453 constraint->GetLoop(), prime_recurrent->GetOffset(), new_child);
1454 // In the paper this is a'[k] <- a'[k] - a[k].
1455 new_second = scalar_evolution_.UpdateChildNode(
1456 new_second, prime_recurrent, new_recurrent);
1457 }
1458 }
1459
1460 new_second = scalar_evolution_.SimplifyExpression(new_second);
1461 return std::make_pair(new_first, new_second);
1462}
1463
1464bool LoopDependenceAnalysis::DeltaTest(
1465 const std::vector<SubscriptPair>& coupled_subscripts,
1466 DistanceVector* dv_entry) {
1467 std::vector<Constraint*> constraints(loops_.size());
1468
1469 std::vector<bool> loop_appeared(loops_.size());
1470
1471 std::generate(std::begin(constraints), std::end(constraints),
1472 [this]() { return make_constraint<DependenceNone>(); });
1473
1474 // Separate SIV and MIV subscripts
1475 std::vector<SubscriptPair> siv_subscripts{};
1476 std::vector<SubscriptPair> miv_subscripts{};
1477
1478 for (const auto& subscript_pair : coupled_subscripts) {
1479 if (IsSIV(subscript_pair)) {
1480 siv_subscripts.push_back(subscript_pair);
1481 } else {
1482 miv_subscripts.push_back(subscript_pair);
1483 }
1484 }
1485
1486 // Delta Test
1487 while (!siv_subscripts.empty()) {
1488 std::vector<bool> results(siv_subscripts.size());
1489
1490 std::vector<DistanceVector> current_distances(
1491 siv_subscripts.size(), DistanceVector(loops_.size()));
1492
1493 // Apply SIV test to all SIV subscripts, report independence if any of them
1494 // is independent
1495 std::transform(
1496 std::begin(siv_subscripts), std::end(siv_subscripts),
1497 std::begin(current_distances), std::begin(results),
1498 [this](SubscriptPair& p, DistanceVector& d) { return SIVTest(p, &d); });
1499
1500 if (std::accumulate(std::begin(results), std::end(results), false,
1501 std::logical_or<bool>{})) {
1502 return true;
1503 }
1504
1505 // Derive new constraint vector.
1506 std::vector<std::pair<Constraint*, size_t>> all_new_constrants{};
1507
1508 for (size_t i = 0; i < siv_subscripts.size(); ++i) {
1509 auto loop = GetLoopForSubscriptPair(siv_subscripts[i]);
1510
1511 auto loop_id =
1512 std::distance(std::begin(loops_),
1513 std::find(std::begin(loops_), std::end(loops_), loop));
1514
1515 loop_appeared[loop_id] = true;
1516 auto distance_entry = current_distances[i].GetEntries()[loop_id];
1517
1518 if (distance_entry.dependence_information ==
1519 DistanceEntry::DependenceInformation::DISTANCE) {
1520 // Construct a DependenceDistance.
1521 auto node = scalar_evolution_.CreateConstant(distance_entry.distance);
1522
1523 all_new_constrants.push_back(
1524 {make_constraint<DependenceDistance>(node, loop), loop_id});
1525 } else {
1526 // Construct a DependenceLine.
1527 const auto& subscript_pair = siv_subscripts[i];
1528 SENode* source_node = std::get<0>(subscript_pair);
1529 SENode* destination_node = std::get<1>(subscript_pair);
1530
1531 int64_t source_induction_count = CountInductionVariables(source_node);
1532 int64_t destination_induction_count =
1533 CountInductionVariables(destination_node);
1534
1535 SENode* a = nullptr;
1536 SENode* b = nullptr;
1537 SENode* c = nullptr;
1538
1539 if (destination_induction_count != 0) {
1540 a = destination_node->AsSERecurrentNode()->GetCoefficient();
1541 c = scalar_evolution_.CreateNegation(
1542 destination_node->AsSERecurrentNode()->GetOffset());
1543 } else {
1544 a = scalar_evolution_.CreateConstant(0);
1545 c = scalar_evolution_.CreateNegation(destination_node);
1546 }
1547
1548 if (source_induction_count != 0) {
1549 b = scalar_evolution_.CreateNegation(
1550 source_node->AsSERecurrentNode()->GetCoefficient());
1551 c = scalar_evolution_.CreateAddNode(
1552 c, source_node->AsSERecurrentNode()->GetOffset());
1553 } else {
1554 b = scalar_evolution_.CreateConstant(0);
1555 c = scalar_evolution_.CreateAddNode(c, source_node);
1556 }
1557
1558 a = scalar_evolution_.SimplifyExpression(a);
1559 b = scalar_evolution_.SimplifyExpression(b);
1560 c = scalar_evolution_.SimplifyExpression(c);
1561
1562 all_new_constrants.push_back(
1563 {make_constraint<DependenceLine>(a, b, c, loop), loop_id});
1564 }
1565 }
1566
1567 // Calculate the intersection between the new and existing constraints.
1568 std::vector<Constraint*> intersection = constraints;
1569 for (const auto& constraint_to_intersect : all_new_constrants) {
1570 auto loop_id = std::get<1>(constraint_to_intersect);
1571 auto loop = loops_[loop_id];
1572 intersection[loop_id] = IntersectConstraints(
1573 intersection[loop_id], std::get<0>(constraint_to_intersect),
1574 GetLowerBound(loop), GetUpperBound(loop));
1575 }
1576
1577 // Report independence if an empty constraint (DependenceEmpty) is found.
1578 auto first_empty =
1579 std::find_if(std::begin(intersection), std::end(intersection),
1580 [](Constraint* constraint) {
1581 return constraint->AsDependenceEmpty() != nullptr;
1582 });
1583 if (first_empty != std::end(intersection)) {
1584 return true;
1585 }
1586 std::vector<SubscriptPair> new_siv_subscripts{};
1587 std::vector<SubscriptPair> new_miv_subscripts{};
1588
1589 auto equal =
1590 std::equal(std::begin(constraints), std::end(constraints),
1591 std::begin(intersection),
1592 [](Constraint* a, Constraint* b) { return *a == *b; });
1593
1594 // If any constraints have changed, propagate them into the rest of the
1595 // subscripts possibly creating new ZIV/SIV subscripts.
1596 if (!equal) {
1597 std::vector<SubscriptPair> new_subscripts(miv_subscripts.size());
1598
1599 // Propagate constraints into MIV subscripts
1600 std::transform(std::begin(miv_subscripts), std::end(miv_subscripts),
1601 std::begin(new_subscripts),
1602 [this, &intersection](SubscriptPair& subscript_pair) {
1603 return PropagateConstraints(subscript_pair,
1604 intersection);
1605 });
1606
1607 // If a ZIV subscript is returned, apply test, otherwise, update untested
1608 // subscripts.
1609 for (auto& subscript : new_subscripts) {
1610 if (IsZIV(subscript) && ZIVTest(subscript)) {
1611 return true;
1612 } else if (IsSIV(subscript)) {
1613 new_siv_subscripts.push_back(subscript);
1614 } else {
1615 new_miv_subscripts.push_back(subscript);
1616 }
1617 }
1618 }
1619
1620 // Set new constraints and subscripts to test.
1621 std::swap(siv_subscripts, new_siv_subscripts);
1622 std::swap(miv_subscripts, new_miv_subscripts);
1623 std::swap(constraints, intersection);
1624 }
1625
1626 // Create the dependence vector from the constraints.
1627 for (size_t i = 0; i < loops_.size(); ++i) {
1628 // Don't touch entries for loops that weren't tested.
1629 if (loop_appeared[i]) {
1630 auto current_constraint = constraints[i];
1631 auto& current_distance_entry = (*dv_entry).GetEntries()[i];
1632
1633 if (auto dependence_distance =
1634 current_constraint->AsDependenceDistance()) {
1635 if (auto constant_node =
1636 dependence_distance->GetDistance()->AsSEConstantNode()) {
1637 current_distance_entry.dependence_information =
1638 DistanceEntry::DependenceInformation::DISTANCE;
1639
1640 current_distance_entry.distance = constant_node->FoldToSingleValue();
1641 if (current_distance_entry.distance == 0) {
1642 current_distance_entry.direction = DistanceEntry::Directions::EQ;
1643 } else if (current_distance_entry.distance < 0) {
1644 current_distance_entry.direction = DistanceEntry::Directions::GT;
1645 } else {
1646 current_distance_entry.direction = DistanceEntry::Directions::LT;
1647 }
1648 }
1649 } else if (auto dependence_point =
1650 current_constraint->AsDependencePoint()) {
1651 auto source = dependence_point->GetSource();
1652 auto destination = dependence_point->GetDestination();
1653
1654 if (source->AsSEConstantNode() && destination->AsSEConstantNode()) {
1655 current_distance_entry = DistanceEntry(
1656 source->AsSEConstantNode()->FoldToSingleValue(),
1657 destination->AsSEConstantNode()->FoldToSingleValue());
1658 }
1659 }
1660 }
1661 }
1662
1663 // Test any remaining MIV subscripts and report independence if found.
1664 std::vector<bool> results(miv_subscripts.size());
1665
1666 std::transform(std::begin(miv_subscripts), std::end(miv_subscripts),
1667 std::begin(results),
1668 [this](const SubscriptPair& p) { return GCDMIVTest(p); });
1669
1670 return std::accumulate(std::begin(results), std::end(results), false,
1671 std::logical_or<bool>{});
1672}
1673
1674} // namespace opt
1675} // namespace spvtools
1676