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