1// Copyright (c) 2017 Google Inc.
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/propagator.h"
16
17namespace spvtools {
18namespace opt {
19
20void SSAPropagator::AddControlEdge(const Edge& edge) {
21 BasicBlock* dest_bb = edge.dest;
22
23 // Refuse to add the exit block to the work list.
24 if (dest_bb == ctx_->cfg()->pseudo_exit_block()) {
25 return;
26 }
27
28 // Try to mark the edge executable. If it was already in the set of
29 // executable edges, do nothing.
30 if (!MarkEdgeExecutable(edge)) {
31 return;
32 }
33
34 // If the edge had not already been marked executable, add the destination
35 // basic block to the work list.
36 blocks_.push(dest_bb);
37}
38
39void SSAPropagator::AddSSAEdges(Instruction* instr) {
40 // Ignore instructions that produce no result.
41 if (instr->result_id() == 0) {
42 return;
43 }
44
45 get_def_use_mgr()->ForEachUser(
46 instr->result_id(), [this](Instruction* use_instr) {
47 // If the basic block for |use_instr| has not been simulated yet, do
48 // nothing. The instruction |use_instr| will be simulated next time the
49 // block is scheduled.
50 if (!BlockHasBeenSimulated(ctx_->get_instr_block(use_instr))) {
51 return;
52 }
53
54 if (ShouldSimulateAgain(use_instr)) {
55 ssa_edge_uses_.push(use_instr);
56 }
57 });
58}
59
60bool SSAPropagator::IsPhiArgExecutable(Instruction* phi, uint32_t i) const {
61 BasicBlock* phi_bb = ctx_->get_instr_block(phi);
62
63 uint32_t in_label_id = phi->GetSingleWordOperand(i + 1);
64 Instruction* in_label_instr = get_def_use_mgr()->GetDef(in_label_id);
65 BasicBlock* in_bb = ctx_->get_instr_block(in_label_instr);
66
67 return IsEdgeExecutable(Edge(in_bb, phi_bb));
68}
69
70bool SSAPropagator::SetStatus(Instruction* inst, PropStatus status) {
71 bool has_old_status = false;
72 PropStatus old_status = kVarying;
73 if (HasStatus(inst)) {
74 has_old_status = true;
75 old_status = Status(inst);
76 }
77
78 assert((!has_old_status || old_status <= status) &&
79 "Invalid lattice transition");
80
81 bool status_changed = !has_old_status || (old_status != status);
82 if (status_changed) statuses_[inst] = status;
83
84 return status_changed;
85}
86
87bool SSAPropagator::Simulate(Instruction* instr) {
88 bool changed = false;
89
90 // Don't bother visiting instructions that should not be simulated again.
91 if (!ShouldSimulateAgain(instr)) {
92 return changed;
93 }
94
95 BasicBlock* dest_bb = nullptr;
96 PropStatus status = visit_fn_(instr, &dest_bb);
97 bool status_changed = SetStatus(instr, status);
98
99 if (status == kVarying) {
100 // The statement produces a varying result, add it to the list of statements
101 // not to simulate anymore and add its SSA def-use edges for simulation.
102 DontSimulateAgain(instr);
103 if (status_changed) {
104 AddSSAEdges(instr);
105 }
106
107 // If |instr| is a block terminator, add all the control edges out of its
108 // block.
109 if (instr->IsBlockTerminator()) {
110 BasicBlock* block = ctx_->get_instr_block(instr);
111 for (const auto& e : bb_succs_.at(block)) {
112 AddControlEdge(e);
113 }
114 }
115 return false;
116 } else if (status == kInteresting) {
117 // Add the SSA edges coming out of this instruction if the propagation
118 // status has changed.
119 if (status_changed) {
120 AddSSAEdges(instr);
121 }
122
123 // If there are multiple outgoing control flow edges and we know which one
124 // will be taken, add the destination block to the CFG work list.
125 if (dest_bb) {
126 AddControlEdge(Edge(ctx_->get_instr_block(instr), dest_bb));
127 }
128 changed = true;
129 }
130
131 // At this point, we are dealing with instructions that are in status
132 // kInteresting or kNotInteresting. To decide whether this instruction should
133 // be simulated again, we examine its operands. If at least one operand O is
134 // defined at an instruction D that should be simulated again, then the output
135 // of D might affect |instr|, so we should simulate |instr| again.
136 bool has_operands_to_simulate = false;
137 if (instr->opcode() == SpvOpPhi) {
138 // For Phi instructions, an operand causes the Phi to be simulated again if
139 // the operand comes from an edge that has not yet been traversed or if its
140 // definition should be simulated again.
141 for (uint32_t i = 2; i < instr->NumOperands(); i += 2) {
142 // Phi arguments come in pairs. Index 'i' contains the
143 // variable id, index 'i + 1' is the originating block id.
144 assert(i % 2 == 0 && i < instr->NumOperands() - 1 &&
145 "malformed Phi arguments");
146
147 uint32_t arg_id = instr->GetSingleWordOperand(i);
148 Instruction* arg_def_instr = get_def_use_mgr()->GetDef(arg_id);
149 if (!IsPhiArgExecutable(instr, i) || ShouldSimulateAgain(arg_def_instr)) {
150 has_operands_to_simulate = true;
151 break;
152 }
153 }
154 } else {
155 // For regular instructions, check if the defining instruction of each
156 // operand needs to be simulated again. If so, then this instruction should
157 // also be simulated again.
158 has_operands_to_simulate =
159 !instr->WhileEachInId([this](const uint32_t* use) {
160 Instruction* def_instr = get_def_use_mgr()->GetDef(*use);
161 if (ShouldSimulateAgain(def_instr)) {
162 return false;
163 }
164 return true;
165 });
166 }
167
168 if (!has_operands_to_simulate) {
169 DontSimulateAgain(instr);
170 }
171
172 return changed;
173}
174
175bool SSAPropagator::Simulate(BasicBlock* block) {
176 if (block == ctx_->cfg()->pseudo_exit_block()) {
177 return false;
178 }
179
180 // Always simulate Phi instructions, even if we have simulated this block
181 // before. We do this because Phi instructions receive their inputs from
182 // incoming edges. When those edges are marked executable, the corresponding
183 // operand can be simulated.
184 bool changed = false;
185 block->ForEachPhiInst(
186 [&changed, this](Instruction* instr) { changed |= Simulate(instr); });
187
188 // If this is the first time this block is being simulated, simulate every
189 // statement in it.
190 if (!BlockHasBeenSimulated(block)) {
191 block->ForEachInst([this, &changed](Instruction* instr) {
192 if (instr->opcode() != SpvOpPhi) {
193 changed |= Simulate(instr);
194 }
195 });
196
197 MarkBlockSimulated(block);
198
199 // If this block has exactly one successor, mark the edge to its successor
200 // as executable.
201 if (bb_succs_.at(block).size() == 1) {
202 AddControlEdge(bb_succs_.at(block).at(0));
203 }
204 }
205
206 return changed;
207}
208
209void SSAPropagator::Initialize(Function* fn) {
210 // Compute predecessor and successor blocks for every block in |fn|'s CFG.
211 // TODO(dnovillo): Move this to CFG and always build them. Alternately,
212 // move it to IRContext and build CFG preds/succs on-demand.
213 bb_succs_[ctx_->cfg()->pseudo_entry_block()].push_back(
214 Edge(ctx_->cfg()->pseudo_entry_block(), fn->entry().get()));
215
216 for (auto& block : *fn) {
217 const auto& const_block = block;
218 const_block.ForEachSuccessorLabel([this, &block](const uint32_t label_id) {
219 BasicBlock* succ_bb =
220 ctx_->get_instr_block(get_def_use_mgr()->GetDef(label_id));
221 bb_succs_[&block].push_back(Edge(&block, succ_bb));
222 bb_preds_[succ_bb].push_back(Edge(succ_bb, &block));
223 });
224 if (block.IsReturnOrAbort()) {
225 bb_succs_[&block].push_back(
226 Edge(&block, ctx_->cfg()->pseudo_exit_block()));
227 bb_preds_[ctx_->cfg()->pseudo_exit_block()].push_back(
228 Edge(ctx_->cfg()->pseudo_exit_block(), &block));
229 }
230 }
231
232 // Add the edges out of the entry block to seed the propagator.
233 const auto& entry_succs = bb_succs_[ctx_->cfg()->pseudo_entry_block()];
234 for (const auto& e : entry_succs) {
235 AddControlEdge(e);
236 }
237}
238
239bool SSAPropagator::Run(Function* fn) {
240 Initialize(fn);
241
242 bool changed = false;
243 while (!blocks_.empty() || !ssa_edge_uses_.empty()) {
244 // Simulate all blocks first. Simulating blocks will add SSA edges to
245 // follow after all the blocks have been simulated.
246 if (!blocks_.empty()) {
247 auto block = blocks_.front();
248 changed |= Simulate(block);
249 blocks_.pop();
250 continue;
251 }
252
253 // Simulate edges from the SSA queue.
254 if (!ssa_edge_uses_.empty()) {
255 Instruction* instr = ssa_edge_uses_.front();
256 changed |= Simulate(instr);
257 ssa_edge_uses_.pop();
258 }
259 }
260
261#ifndef NDEBUG
262 // Verify all visited values have settled. No value that has been simulated
263 // should end on not interesting.
264 fn->ForEachInst([this](Instruction* inst) {
265 assert(
266 (!HasStatus(inst) || Status(inst) != SSAPropagator::kNotInteresting) &&
267 "Unsettled value");
268 });
269#endif
270
271 return changed;
272}
273
274std::ostream& operator<<(std::ostream& str,
275 const SSAPropagator::PropStatus& status) {
276 switch (status) {
277 case SSAPropagator::kVarying:
278 str << "Varying";
279 break;
280 case SSAPropagator::kInteresting:
281 str << "Interesting";
282 break;
283 default:
284 str << "Not interesting";
285 break;
286 }
287 return str;
288}
289
290} // namespace opt
291} // namespace spvtools
292