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 <ostream>
18#include <set>
19#include <string>
20#include <unordered_set>
21#include <utility>
22#include <vector>
23
24#include "source/opt/basic_block.h"
25#include "source/opt/instruction.h"
26#include "source/opt/scalar_analysis.h"
27#include "source/opt/scalar_analysis_nodes.h"
28
29namespace spvtools {
30namespace opt {
31
32bool LoopDependenceAnalysis::IsZIV(
33 const std::pair<SENode*, SENode*>& subscript_pair) {
34 return CountInductionVariables(subscript_pair.first, subscript_pair.second) ==
35 0;
36}
37
38bool LoopDependenceAnalysis::IsSIV(
39 const std::pair<SENode*, SENode*>& subscript_pair) {
40 return CountInductionVariables(subscript_pair.first, subscript_pair.second) ==
41 1;
42}
43
44bool LoopDependenceAnalysis::IsMIV(
45 const std::pair<SENode*, SENode*>& subscript_pair) {
46 return CountInductionVariables(subscript_pair.first, subscript_pair.second) >
47 1;
48}
49
50SENode* LoopDependenceAnalysis::GetLowerBound(const Loop* loop) {
51 Instruction* cond_inst = loop->GetConditionInst();
52 if (!cond_inst) {
53 return nullptr;
54 }
55 Instruction* lower_inst = GetOperandDefinition(cond_inst, 0);
56 switch (cond_inst->opcode()) {
57 case SpvOpULessThan:
58 case SpvOpSLessThan:
59 case SpvOpULessThanEqual:
60 case SpvOpSLessThanEqual:
61 case SpvOpUGreaterThan:
62 case SpvOpSGreaterThan:
63 case SpvOpUGreaterThanEqual:
64 case SpvOpSGreaterThanEqual: {
65 // If we have a phi we are looking at the induction variable. We look
66 // through the phi to the initial value of the phi upon entering the loop.
67 if (lower_inst->opcode() == SpvOpPhi) {
68 lower_inst = GetOperandDefinition(lower_inst, 0);
69 // We don't handle looking through multiple phis.
70 if (lower_inst->opcode() == SpvOpPhi) {
71 return nullptr;
72 }
73 }
74 return scalar_evolution_.SimplifyExpression(
75 scalar_evolution_.AnalyzeInstruction(lower_inst));
76 }
77 default:
78 return nullptr;
79 }
80}
81
82SENode* LoopDependenceAnalysis::GetUpperBound(const Loop* loop) {
83 Instruction* cond_inst = loop->GetConditionInst();
84 if (!cond_inst) {
85 return nullptr;
86 }
87 Instruction* upper_inst = GetOperandDefinition(cond_inst, 1);
88 switch (cond_inst->opcode()) {
89 case SpvOpULessThan:
90 case SpvOpSLessThan: {
91 // When we have a < condition we must subtract 1 from the analyzed upper
92 // instruction.
93 SENode* upper_bound = scalar_evolution_.SimplifyExpression(
94 scalar_evolution_.CreateSubtraction(
95 scalar_evolution_.AnalyzeInstruction(upper_inst),
96 scalar_evolution_.CreateConstant(1)));
97 return upper_bound;
98 }
99 case SpvOpUGreaterThan:
100 case SpvOpSGreaterThan: {
101 // When we have a > condition we must add 1 to the analyzed upper
102 // instruction.
103 SENode* upper_bound =
104 scalar_evolution_.SimplifyExpression(scalar_evolution_.CreateAddNode(
105 scalar_evolution_.AnalyzeInstruction(upper_inst),
106 scalar_evolution_.CreateConstant(1)));
107 return upper_bound;
108 }
109 case SpvOpULessThanEqual:
110 case SpvOpSLessThanEqual:
111 case SpvOpUGreaterThanEqual:
112 case SpvOpSGreaterThanEqual: {
113 // We don't need to modify the results of analyzing when we have <= or >=.
114 SENode* upper_bound = scalar_evolution_.SimplifyExpression(
115 scalar_evolution_.AnalyzeInstruction(upper_inst));
116 return upper_bound;
117 }
118 default:
119 return nullptr;
120 }
121}
122
123bool LoopDependenceAnalysis::IsWithinBounds(int64_t value, int64_t bound_one,
124 int64_t bound_two) {
125 if (bound_one < bound_two) {
126 // If |bound_one| is the lower bound.
127 return (value >= bound_one && value <= bound_two);
128 } else if (bound_one > bound_two) {
129 // If |bound_two| is the lower bound.
130 return (value >= bound_two && value <= bound_one);
131 } else {
132 // Both bounds have the same value.
133 return value == bound_one;
134 }
135}
136
137bool LoopDependenceAnalysis::IsProvablyOutsideOfLoopBounds(
138 const Loop* loop, SENode* distance, SENode* coefficient) {
139 // We test to see if we can reduce the coefficient to an integral constant.
140 SEConstantNode* coefficient_constant = coefficient->AsSEConstantNode();
141 if (!coefficient_constant) {
142 PrintDebug(
143 "IsProvablyOutsideOfLoopBounds could not reduce coefficient to a "
144 "SEConstantNode so must exit.");
145 return false;
146 }
147
148 SENode* lower_bound = GetLowerBound(loop);
149 SENode* upper_bound = GetUpperBound(loop);
150 if (!lower_bound || !upper_bound) {
151 PrintDebug(
152 "IsProvablyOutsideOfLoopBounds could not get both the lower and upper "
153 "bounds so must exit.");
154 return false;
155 }
156 // If the coefficient is positive we calculate bounds as upper - lower
157 // If the coefficient is negative we calculate bounds as lower - upper
158 SENode* bounds = nullptr;
159 if (coefficient_constant->FoldToSingleValue() >= 0) {
160 PrintDebug(
161 "IsProvablyOutsideOfLoopBounds found coefficient >= 0.\n"
162 "Using bounds as upper - lower.");
163 bounds = scalar_evolution_.SimplifyExpression(
164 scalar_evolution_.CreateSubtraction(upper_bound, lower_bound));
165 } else {
166 PrintDebug(
167 "IsProvablyOutsideOfLoopBounds found coefficient < 0.\n"
168 "Using bounds as lower - upper.");
169 bounds = scalar_evolution_.SimplifyExpression(
170 scalar_evolution_.CreateSubtraction(lower_bound, upper_bound));
171 }
172
173 // We can attempt to deal with symbolic cases by subtracting |distance| and
174 // the bound nodes. If we can subtract, simplify and produce a SEConstantNode
175 // we can produce some information.
176 SEConstantNode* distance_minus_bounds =
177 scalar_evolution_
178 .SimplifyExpression(
179 scalar_evolution_.CreateSubtraction(distance, bounds))
180 ->AsSEConstantNode();
181 if (distance_minus_bounds) {
182 PrintDebug(
183 "IsProvablyOutsideOfLoopBounds found distance - bounds as a "
184 "SEConstantNode with value " +
185 ToString(distance_minus_bounds->FoldToSingleValue()));
186 // If distance - bounds > 0 we prove the distance is outwith the loop
187 // bounds.
188 if (distance_minus_bounds->FoldToSingleValue() > 0) {
189 PrintDebug(
190 "IsProvablyOutsideOfLoopBounds found distance escaped the loop "
191 "bounds.");
192 return true;
193 }
194 }
195
196 return false;
197}
198
199const Loop* LoopDependenceAnalysis::GetLoopForSubscriptPair(
200 const std::pair<SENode*, SENode*>& subscript_pair) {
201 // Collect all the SERecurrentNodes.
202 std::vector<SERecurrentNode*> source_nodes =
203 std::get<0>(subscript_pair)->CollectRecurrentNodes();
204 std::vector<SERecurrentNode*> destination_nodes =
205 std::get<1>(subscript_pair)->CollectRecurrentNodes();
206
207 // Collect all the loops stored by the SERecurrentNodes.
208 std::unordered_set<const Loop*> loops{};
209 for (auto source_nodes_it = source_nodes.begin();
210 source_nodes_it != source_nodes.end(); ++source_nodes_it) {
211 loops.insert((*source_nodes_it)->GetLoop());
212 }
213 for (auto destination_nodes_it = destination_nodes.begin();
214 destination_nodes_it != destination_nodes.end();
215 ++destination_nodes_it) {
216 loops.insert((*destination_nodes_it)->GetLoop());
217 }
218
219 // If we didn't find 1 loop |subscript_pair| is a subscript over multiple or 0
220 // loops. We don't handle this so return nullptr.
221 if (loops.size() != 1) {
222 PrintDebug("GetLoopForSubscriptPair found loops.size() != 1.");
223 return nullptr;
224 }
225 return *loops.begin();
226}
227
228DistanceEntry* LoopDependenceAnalysis::GetDistanceEntryForLoop(
229 const Loop* loop, DistanceVector* distance_vector) {
230 if (!loop) {
231 return nullptr;
232 }
233
234 DistanceEntry* distance_entry = nullptr;
235 for (size_t loop_index = 0; loop_index < loops_.size(); ++loop_index) {
236 if (loop == loops_[loop_index]) {
237 distance_entry = &(distance_vector->GetEntries()[loop_index]);
238 break;
239 }
240 }
241
242 return distance_entry;
243}
244
245DistanceEntry* LoopDependenceAnalysis::GetDistanceEntryForSubscriptPair(
246 const std::pair<SENode*, SENode*>& subscript_pair,
247 DistanceVector* distance_vector) {
248 const Loop* loop = GetLoopForSubscriptPair(subscript_pair);
249
250 return GetDistanceEntryForLoop(loop, distance_vector);
251}
252
253SENode* LoopDependenceAnalysis::GetTripCount(const Loop* loop) {
254 BasicBlock* condition_block = loop->FindConditionBlock();
255 if (!condition_block) {
256 return nullptr;
257 }
258 Instruction* induction_instr = loop->FindConditionVariable(condition_block);
259 if (!induction_instr) {
260 return nullptr;
261 }
262 Instruction* cond_instr = loop->GetConditionInst();
263 if (!cond_instr) {
264 return nullptr;
265 }
266
267 size_t iteration_count = 0;
268
269 // We have to check the instruction type here. If the condition instruction
270 // isn't a supported type we can't calculate the trip count.
271 if (loop->IsSupportedCondition(cond_instr->opcode())) {
272 if (loop->FindNumberOfIterations(induction_instr, &*condition_block->tail(),
273 &iteration_count)) {
274 return scalar_evolution_.CreateConstant(
275 static_cast<int64_t>(iteration_count));
276 }
277 }
278
279 return nullptr;
280}
281
282SENode* LoopDependenceAnalysis::GetFirstTripInductionNode(const Loop* loop) {
283 BasicBlock* condition_block = loop->FindConditionBlock();
284 if (!condition_block) {
285 return nullptr;
286 }
287 Instruction* induction_instr = loop->FindConditionVariable(condition_block);
288 if (!induction_instr) {
289 return nullptr;
290 }
291 int64_t induction_initial_value = 0;
292 if (!loop->GetInductionInitValue(induction_instr, &induction_initial_value)) {
293 return nullptr;
294 }
295
296 SENode* induction_init_SENode = scalar_evolution_.SimplifyExpression(
297 scalar_evolution_.CreateConstant(induction_initial_value));
298 return induction_init_SENode;
299}
300
301SENode* LoopDependenceAnalysis::GetFinalTripInductionNode(
302 const Loop* loop, SENode* induction_coefficient) {
303 SENode* first_trip_induction_node = GetFirstTripInductionNode(loop);
304 if (!first_trip_induction_node) {
305 return nullptr;
306 }
307 // Get trip_count as GetTripCount - 1
308 // This is because the induction variable is not stepped on the first
309 // iteration of the loop
310 SENode* trip_count =
311 scalar_evolution_.SimplifyExpression(scalar_evolution_.CreateSubtraction(
312 GetTripCount(loop), scalar_evolution_.CreateConstant(1)));
313 // Return first_trip_induction_node + trip_count * induction_coefficient
314 return scalar_evolution_.SimplifyExpression(scalar_evolution_.CreateAddNode(
315 first_trip_induction_node,
316 scalar_evolution_.CreateMultiplyNode(trip_count, induction_coefficient)));
317}
318
319std::set<const Loop*> LoopDependenceAnalysis::CollectLoops(
320 const std::vector<SERecurrentNode*>& recurrent_nodes) {
321 // We don't handle loops with more than one induction variable. Therefore we
322 // can identify the number of induction variables by collecting all of the
323 // loops the collected recurrent nodes belong to.
324 std::set<const Loop*> loops{};
325 for (auto recurrent_nodes_it = recurrent_nodes.begin();
326 recurrent_nodes_it != recurrent_nodes.end(); ++recurrent_nodes_it) {
327 loops.insert((*recurrent_nodes_it)->GetLoop());
328 }
329
330 return loops;
331}
332
333int64_t LoopDependenceAnalysis::CountInductionVariables(SENode* node) {
334 if (!node) {
335 return -1;
336 }
337
338 std::vector<SERecurrentNode*> recurrent_nodes = node->CollectRecurrentNodes();
339
340 // We don't handle loops with more than one induction variable. Therefore we
341 // can identify the number of induction variables by collecting all of the
342 // loops the collected recurrent nodes belong to.
343 std::set<const Loop*> loops = CollectLoops(recurrent_nodes);
344
345 return static_cast<int64_t>(loops.size());
346}
347
348std::set<const Loop*> LoopDependenceAnalysis::CollectLoops(
349 SENode* source, SENode* destination) {
350 if (!source || !destination) {
351 return std::set<const Loop*>{};
352 }
353
354 std::vector<SERecurrentNode*> source_nodes = source->CollectRecurrentNodes();
355 std::vector<SERecurrentNode*> destination_nodes =
356 destination->CollectRecurrentNodes();
357
358 std::set<const Loop*> loops = CollectLoops(source_nodes);
359 std::set<const Loop*> destination_loops = CollectLoops(destination_nodes);
360
361 loops.insert(std::begin(destination_loops), std::end(destination_loops));
362
363 return loops;
364}
365
366int64_t LoopDependenceAnalysis::CountInductionVariables(SENode* source,
367 SENode* destination) {
368 if (!source || !destination) {
369 return -1;
370 }
371
372 std::set<const Loop*> loops = CollectLoops(source, destination);
373
374 return static_cast<int64_t>(loops.size());
375}
376
377Instruction* LoopDependenceAnalysis::GetOperandDefinition(
378 const Instruction* instruction, int id) {
379 return context_->get_def_use_mgr()->GetDef(
380 instruction->GetSingleWordInOperand(id));
381}
382
383std::vector<Instruction*> LoopDependenceAnalysis::GetSubscripts(
384 const Instruction* instruction) {
385 Instruction* access_chain = GetOperandDefinition(instruction, 0);
386
387 std::vector<Instruction*> subscripts;
388
389 for (auto i = 1u; i < access_chain->NumInOperandWords(); ++i) {
390 subscripts.push_back(GetOperandDefinition(access_chain, i));
391 }
392
393 return subscripts;
394}
395
396SENode* LoopDependenceAnalysis::GetConstantTerm(const Loop* loop,
397 SERecurrentNode* induction) {
398 SENode* offset = induction->GetOffset();
399 SENode* lower_bound = GetLowerBound(loop);
400 if (!offset || !lower_bound) {
401 return nullptr;
402 }
403 SENode* constant_term = scalar_evolution_.SimplifyExpression(
404 scalar_evolution_.CreateSubtraction(offset, lower_bound));
405 return constant_term;
406}
407
408bool LoopDependenceAnalysis::CheckSupportedLoops(
409 std::vector<const Loop*> loops) {
410 for (auto loop : loops) {
411 if (!IsSupportedLoop(loop)) {
412 return false;
413 }
414 }
415 return true;
416}
417
418void LoopDependenceAnalysis::MarkUnsusedDistanceEntriesAsIrrelevant(
419 const Instruction* source, const Instruction* destination,
420 DistanceVector* distance_vector) {
421 std::vector<Instruction*> source_subscripts = GetSubscripts(source);
422 std::vector<Instruction*> destination_subscripts = GetSubscripts(destination);
423
424 std::set<const Loop*> used_loops{};
425
426 for (Instruction* source_inst : source_subscripts) {
427 SENode* source_node = scalar_evolution_.SimplifyExpression(
428 scalar_evolution_.AnalyzeInstruction(source_inst));
429 std::vector<SERecurrentNode*> recurrent_nodes =
430 source_node->CollectRecurrentNodes();
431 for (SERecurrentNode* recurrent_node : recurrent_nodes) {
432 used_loops.insert(recurrent_node->GetLoop());
433 }
434 }
435
436 for (Instruction* destination_inst : destination_subscripts) {
437 SENode* destination_node = scalar_evolution_.SimplifyExpression(
438 scalar_evolution_.AnalyzeInstruction(destination_inst));
439 std::vector<SERecurrentNode*> recurrent_nodes =
440 destination_node->CollectRecurrentNodes();
441 for (SERecurrentNode* recurrent_node : recurrent_nodes) {
442 used_loops.insert(recurrent_node->GetLoop());
443 }
444 }
445
446 for (size_t i = 0; i < loops_.size(); ++i) {
447 if (used_loops.find(loops_[i]) == used_loops.end()) {
448 distance_vector->GetEntries()[i].dependence_information =
449 DistanceEntry::DependenceInformation::IRRELEVANT;
450 }
451 }
452}
453
454bool LoopDependenceAnalysis::IsSupportedLoop(const Loop* loop) {
455 std::vector<Instruction*> inductions{};
456 loop->GetInductionVariables(inductions);
457 if (inductions.size() != 1) {
458 return false;
459 }
460 Instruction* induction = inductions[0];
461 SENode* induction_node = scalar_evolution_.SimplifyExpression(
462 scalar_evolution_.AnalyzeInstruction(induction));
463 if (!induction_node->AsSERecurrentNode()) {
464 return false;
465 }
466 SENode* induction_step =
467 induction_node->AsSERecurrentNode()->GetCoefficient();
468 if (!induction_step->AsSEConstantNode()) {
469 return false;
470 }
471 if (!(induction_step->AsSEConstantNode()->FoldToSingleValue() == 1 ||
472 induction_step->AsSEConstantNode()->FoldToSingleValue() == -1)) {
473 return false;
474 }
475 return true;
476}
477
478void LoopDependenceAnalysis::PrintDebug(std::string debug_msg) {
479 if (debug_stream_) {
480 (*debug_stream_) << debug_msg << "\n";
481 }
482}
483
484bool Constraint::operator==(const Constraint& other) const {
485 // A distance of |d| is equivalent to a line |x - y = -d|
486 if ((GetType() == ConstraintType::Distance &&
487 other.GetType() == ConstraintType::Line) ||
488 (GetType() == ConstraintType::Line &&
489 other.GetType() == ConstraintType::Distance)) {
490 auto is_distance = AsDependenceLine() != nullptr;
491
492 auto as_distance =
493 is_distance ? AsDependenceDistance() : other.AsDependenceDistance();
494 auto distance = as_distance->GetDistance();
495
496 auto line = other.AsDependenceLine();
497
498 auto scalar_evolution = distance->GetParentAnalysis();
499
500 auto neg_distance = scalar_evolution->SimplifyExpression(
501 scalar_evolution->CreateNegation(distance));
502
503 return *scalar_evolution->CreateConstant(1) == *line->GetA() &&
504 *scalar_evolution->CreateConstant(-1) == *line->GetB() &&
505 *neg_distance == *line->GetC();
506 }
507
508 if (GetType() != other.GetType()) {
509 return false;
510 }
511
512 if (AsDependenceDistance()) {
513 return *AsDependenceDistance()->GetDistance() ==
514 *other.AsDependenceDistance()->GetDistance();
515 }
516
517 if (AsDependenceLine()) {
518 auto this_line = AsDependenceLine();
519 auto other_line = other.AsDependenceLine();
520 return *this_line->GetA() == *other_line->GetA() &&
521 *this_line->GetB() == *other_line->GetB() &&
522 *this_line->GetC() == *other_line->GetC();
523 }
524
525 if (AsDependencePoint()) {
526 auto this_point = AsDependencePoint();
527 auto other_point = other.AsDependencePoint();
528
529 return *this_point->GetSource() == *other_point->GetSource() &&
530 *this_point->GetDestination() == *other_point->GetDestination();
531 }
532
533 return true;
534}
535
536bool Constraint::operator!=(const Constraint& other) const {
537 return !(*this == other);
538}
539
540} // namespace opt
541} // namespace spvtools
542