1 // Copyright (c) 2021 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/dataflow.h"
16
17 #include <algorithm>
18 #include <cstdint>
19
20 namespace spvtools {
21 namespace opt {
22
Enqueue(Instruction * inst)23 bool DataFlowAnalysis::Enqueue(Instruction* inst) {
24 bool& is_enqueued = on_worklist_[inst];
25 if (is_enqueued) return false;
26 is_enqueued = true;
27 worklist_.push(inst);
28 return true;
29 }
30
RunOnce(Function * function,bool is_first_iteration)31 DataFlowAnalysis::VisitResult DataFlowAnalysis::RunOnce(
32 Function* function, bool is_first_iteration) {
33 InitializeWorklist(function, is_first_iteration);
34 VisitResult ret = VisitResult::kResultFixed;
35 while (!worklist_.empty()) {
36 Instruction* top = worklist_.front();
37 worklist_.pop();
38 on_worklist_[top] = false;
39 VisitResult result = Visit(top);
40 if (result == VisitResult::kResultChanged) {
41 EnqueueSuccessors(top);
42 ret = VisitResult::kResultChanged;
43 }
44 }
45 return ret;
46 }
47
Run(Function * function)48 void DataFlowAnalysis::Run(Function* function) {
49 VisitResult result = RunOnce(function, true);
50 while (result == VisitResult::kResultChanged) {
51 result = RunOnce(function, false);
52 }
53 }
54
InitializeWorklist(Function * function,bool)55 void ForwardDataFlowAnalysis::InitializeWorklist(Function* function,
56 bool /*is_first_iteration*/) {
57 context().cfg()->ForEachBlockInReversePostOrder(
58 function->entry().get(), [this](BasicBlock* bb) {
59 if (label_position_ == LabelPosition::kLabelsOnly) {
60 Enqueue(bb->GetLabelInst());
61 return;
62 }
63 if (label_position_ == LabelPosition::kLabelsAtBeginning) {
64 Enqueue(bb->GetLabelInst());
65 }
66 for (Instruction& inst : *bb) {
67 Enqueue(&inst);
68 }
69 if (label_position_ == LabelPosition::kLabelsAtEnd) {
70 Enqueue(bb->GetLabelInst());
71 }
72 });
73 }
74
EnqueueUsers(Instruction * inst)75 void ForwardDataFlowAnalysis::EnqueueUsers(Instruction* inst) {
76 context().get_def_use_mgr()->ForEachUser(
77 inst, [this](Instruction* user) { Enqueue(user); });
78 }
79
EnqueueBlockSuccessors(Instruction * inst)80 void ForwardDataFlowAnalysis::EnqueueBlockSuccessors(Instruction* inst) {
81 if (inst->opcode() != SpvOpLabel) return;
82 context()
83 .cfg()
84 ->block(inst->result_id())
85 ->ForEachSuccessorLabel([this](uint32_t* label) {
86 Enqueue(context().cfg()->block(*label)->GetLabelInst());
87 });
88 }
89
90 } // namespace opt
91 } // namespace spvtools
92