diff options
| -rw-r--r-- | Android.mk | 1 | ||||
| -rw-r--r-- | source/opcode.cpp | 26 | ||||
| -rw-r--r-- | source/opcode.h | 9 | ||||
| -rw-r--r-- | source/opt/CMakeLists.txt | 36 | ||||
| -rw-r--r-- | source/opt/aggressive_dead_code_elim_pass.cpp | 2 | ||||
| -rw-r--r-- | source/opt/aggressive_dead_code_elim_pass.h | 5 | ||||
| -rw-r--r-- | source/opt/basic_block.h | 4 | ||||
| -rw-r--r-- | source/opt/cfg.h | 8 | ||||
| -rw-r--r-- | source/opt/instruction.h | 16 | ||||
| -rw-r--r-- | source/opt/propagator.cpp | 232 | ||||
| -rw-r--r-- | source/opt/propagator.h | 296 | ||||
| -rw-r--r-- | test/opt/CMakeLists.txt | 5 | ||||
| -rw-r--r-- | test/opt/aggressive_dead_code_elim_test.cpp | 111 | ||||
| -rw-r--r-- | test/opt/propagator_test.cpp | 217 |
14 files changed, 939 insertions, 29 deletions
@@ -87,6 +87,7 @@ SPVTOOLS_OPT_SRC_FILES := \ source/opt/optimizer.cpp \ source/opt/pass.cpp \ source/opt/pass_manager.cpp \ + source/opt/propagator.cpp \ source/opt/remove_duplicates_pass.cpp \ source/opt/set_spec_constant_default_value_pass.cpp \ source/opt/strength_reduction_pass.cpp \ diff --git a/source/opcode.cpp b/source/opcode.cpp index 50f5e52c..a9ab1e60 100644 --- a/source/opcode.cpp +++ b/source/opcode.cpp @@ -360,6 +360,17 @@ bool spvOpcodeIsLoad(const SpvOp opcode) { } } +bool spvOpcodeIsBranch(SpvOp opcode) { + switch (opcode) { + case SpvOpBranch: + case SpvOpBranchConditional: + case SpvOpSwitch: + return true; + default: + return false; + } +} + bool spvOpcodeIsAtomicOp(const SpvOp opcode) { switch (opcode) { case SpvOpAtomicLoad: @@ -385,3 +396,18 @@ bool spvOpcodeIsAtomicOp(const SpvOp opcode) { return false; } } + +bool spvOpcodeIsReturn(SpvOp opcode) { + switch (opcode) { + case SpvOpReturn: + case SpvOpReturnValue: + return true; + default: + return false; + } +} + +bool spvOpcodeIsBlockTerminator(SpvOp opcode) { + return spvOpcodeIsBranch(opcode) || spvOpcodeIsReturn(opcode) || + opcode == SpvOpKill || opcode == SpvOpUnreachable; +} diff --git a/source/opcode.h b/source/opcode.h index ba693f05..3ba99df6 100644 --- a/source/opcode.h +++ b/source/opcode.h @@ -97,4 +97,13 @@ bool spvOpcodeIsLoad(const SpvOp opcode); // Returns true if the opcode is an atomic operation. bool spvOpcodeIsAtomicOp(const SpvOp opcode); +// Returns true if the given opcode is a branch instruction. +bool spvOpcodeIsBranch(SpvOp opcode); + +// Returns true if the given opcode is a return instruction. +bool spvOpcodeIsReturn(SpvOp opcode); + +// Returns true if the given opcode is a basic block terminator. +bool spvOpcodeIsBlockTerminator(SpvOp opcode); + #endif // LIBSPIRV_OPCODE_H_ diff --git a/source/opt/CMakeLists.txt b/source/opt/CMakeLists.txt index 2964ebdb..2294e81f 100644 --- a/source/opt/CMakeLists.txt +++ b/source/opt/CMakeLists.txt @@ -26,39 +26,40 @@ add_library(SPIRV-Tools-opt decoration_manager.h def_use_manager.h eliminate_dead_constant_pass.h + eliminate_dead_functions_pass.h flatten_decoration_pass.h - function.h fold.h fold_spec_constant_op_and_composite_pass.h freeze_spec_constant_value_pass.h - inline_pass.h + function.h inline_exhaustive_pass.h inline_opaque_pass.h + inline_pass.h insert_extract_elim.h instruction.h - ir_loader.h ir_context.h + ir_loader.h local_access_chain_convert_pass.h local_redundancy_elimination.h local_single_block_elim_pass.h local_single_store_elim_pass.h local_ssa_elim_pass.h log.h + mem_pass.h merge_return_pass.h module.h null_pass.h - reflect.h - mem_pass.h - pass.h passes.h + pass.h pass_manager.h - eliminate_dead_functions_pass.h + propagator.h + reflect.h remove_duplicates_pass.h set_spec_constant_default_value_pass.h strength_reduction_pass.h strip_debug_info_pass.h - types.h type_manager.h + types.h unify_const_pass.h value_number_table.h @@ -70,42 +71,43 @@ add_library(SPIRV-Tools-opt cfg.cpp common_uniform_elim_pass.cpp compact_ids_pass.cpp - decoration_manager.cpp - def_use_manager.cpp dead_branch_elim_pass.cpp dead_variable_elimination.cpp + decoration_manager.cpp + def_use_manager.cpp eliminate_dead_constant_pass.cpp + eliminate_dead_functions_pass.cpp flatten_decoration_pass.cpp fold.cpp fold_spec_constant_op_and_composite_pass.cpp freeze_spec_constant_value_pass.cpp function.cpp - inline_pass.cpp inline_exhaustive_pass.cpp inline_opaque_pass.cpp + inline_pass.cpp insert_extract_elim.cpp instruction.cpp instruction_list.cpp - ir_loader.cpp ir_context.cpp + ir_loader.cpp local_access_chain_convert_pass.cpp local_redundancy_elimination.cpp local_single_block_elim_pass.cpp local_single_store_elim_pass.cpp local_ssa_elim_pass.cpp + mem_pass.cpp merge_return_pass.cpp module.cpp - eliminate_dead_functions_pass.cpp - remove_duplicates_pass.cpp - set_spec_constant_default_value_pass.cpp optimizer.cpp - mem_pass.cpp pass.cpp pass_manager.cpp + propagator.cpp + remove_duplicates_pass.cpp + set_spec_constant_default_value_pass.cpp strength_reduction_pass.cpp strip_debug_info_pass.cpp - types.cpp type_manager.cpp + types.cpp unify_const_pass.cpp value_number_table.cpp ) diff --git a/source/opt/aggressive_dead_code_elim_pass.cpp b/source/opt/aggressive_dead_code_elim_pass.cpp index b9147024..d8c51645 100644 --- a/source/opt/aggressive_dead_code_elim_pass.cpp +++ b/source/opt/aggressive_dead_code_elim_pass.cpp @@ -300,7 +300,7 @@ bool AggressiveDCEPass::AggressiveDCE(ir::Function* func) { for (auto bi = structuredOrder.begin(); bi != structuredOrder.end(); ++bi) { for (auto ii = (*bi)->begin(); ii != (*bi)->end(); ++ii) { if (IsLive(&*ii)) continue; - if (IsBranch(ii->opcode()) && + if (ii->IsBranch() && !IsStructuredIfHeader(*bi, nullptr, nullptr, nullptr)) continue; dead_insts_.insert(&*ii); diff --git a/source/opt/aggressive_dead_code_elim_pass.h b/source/opt/aggressive_dead_code_elim_pass.h index 54d05d23..6540f3ed 100644 --- a/source/opt/aggressive_dead_code_elim_pass.h +++ b/source/opt/aggressive_dead_code_elim_pass.h @@ -57,11 +57,6 @@ class AggressiveDCEPass : public MemPass { // privates_like_local_) bool IsLocalVar(uint32_t varId); - // Return true if |op| is branch instruction - bool IsBranch(SpvOp op) { - return op == SpvOpBranch || op == SpvOpBranchConditional; - } - // Return true if |inst| is marked live bool IsLive(ir::Instruction* inst) { return live_insts_.find(inst) != live_insts_.end(); diff --git a/source/opt/basic_block.h b/source/opt/basic_block.h index f4405f2a..c84206cd 100644 --- a/source/opt/basic_block.h +++ b/source/opt/basic_block.h @@ -138,6 +138,10 @@ class BasicBlock { // this block, if any. If none, returns zero. uint32_t ContinueBlockIdIfAny() const; + // Returns true if this basic block exits this function and returns to its + // caller. + bool IsReturn() const { return ctail()->IsReturn(); } + private: // The enclosing function. Function* function_; diff --git a/source/opt/cfg.h b/source/opt/cfg.h index f8f3c6c0..0a2054b7 100644 --- a/source/opt/cfg.h +++ b/source/opt/cfg.h @@ -63,10 +63,10 @@ class CFG { return block_ptr == &pseudo_exit_block_; } - // Compute structured block order into |structuredOrder| for |func| starting - // at |root|. This order has the property that dominators come before all - // blocks they dominate and merge blocks come after all blocks that are in - // the control constructs of their header. + // Compute structured block order into |order| for |func| starting at |root|. + // This order has the property that dominators come before all blocks they + // dominate and merge blocks come after all blocks that are in the control + // constructs of their header. void ComputeStructuredOrder(ir::Function* func, ir::BasicBlock* root, std::list<ir::BasicBlock*>* order); diff --git a/source/opt/instruction.h b/source/opt/instruction.h index a046e8dc..08c5b77e 100644 --- a/source/opt/instruction.h +++ b/source/opt/instruction.h @@ -295,6 +295,19 @@ class Instruction : public utils::IntrusiveNodeBase<Instruction> { // Returns true if the instruction is an atom operation. inline bool IsAtomicOp() const; + // Returns true if this instruction is a branch or switch instruction (either + // conditional or not). + bool IsBranch() const { return spvOpcodeIsBranch(opcode()); } + + // Returns true if this instruction causes the function to finish execution + // and return to its caller + bool IsReturn() const { return spvOpcodeIsReturn(opcode()); } + + // Returns true if this instruction is a basic block terminator. + bool IsBlockTerminator() const { + return spvOpcodeIsBlockTerminator(opcode()); + } + inline bool operator==(const Instruction&) const; inline bool operator!=(const Instruction&) const; inline bool operator<(const Instruction&) const; @@ -344,8 +357,7 @@ inline const Operand& Instruction::GetOperand(uint32_t index) const { }; inline void Instruction::AddOperand(Operand&& operand) { - operands_.push_back(operand); - return; + operands_.push_back(std::move(operand)); } inline void Instruction::SetInOperand(uint32_t index, diff --git a/source/opt/propagator.cpp b/source/opt/propagator.cpp new file mode 100644 index 00000000..907f41f5 --- /dev/null +++ b/source/opt/propagator.cpp @@ -0,0 +1,232 @@ +// Copyright (c) 2017 Google Inc. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#include "propagator.h" + +namespace spvtools { +namespace opt { + +void SSAPropagator::AddControlEdge(const Edge& edge) { + ir::BasicBlock* dest_bb = edge.dest; + + // Refuse to add the exit block to the work list. + if (dest_bb == cfg_->pseudo_exit_block()) { + return; + } + + // Try to mark the edge executable. If it was already in the set of + // executable edges, do nothing. + if (!MarkEdgeExecutable(edge)) { + return; + } + + // If the edge had not already been marked executable, add the destination + // basic block to the work list. + blocks_.push(dest_bb); +} + +void SSAPropagator::AddSSAEdges(uint32_t id) { + get_def_use_mgr()->ForEachUser(id, [this](ir::Instruction *instr) { + // If the basic block for |instr| has not been simulated yet, do nothing. + if (!BlockHasBeenSimulated(ctx_->get_instr_block(instr))) { + return; + } + + if (ShouldSimulateAgain(instr)) { + ssa_edge_uses_.push(instr); + } + }); +} + +bool SSAPropagator::Simulate(ir::Instruction* instr) { + bool changed = false; + + // Don't bother visiting instructions that should not be simulated again. + if (!ShouldSimulateAgain(instr)) { + return changed; + } + + ir::BasicBlock* dest_bb = nullptr; + PropStatus status = visit_fn_(instr, &dest_bb); + + if (status == kVarying) { + // The statement produces a varying result, add it to the list of statements + // not to simulate anymore and add its SSA def-use edges for simulation. + DontSimulateAgain(instr); + if (instr->result_id() > 0) { + AddSSAEdges(instr->result_id()); + } + + // If |instr| is a block terminator, add all the control edges out of its + // block. + if (instr->IsBlockTerminator()) { + ir::BasicBlock* block = ctx_->get_instr_block(instr); + for (const auto& e : bb_succs_.at(block)) { + AddControlEdge(e); + } + } + return false; + } else if (status == kInteresting) { + // If the instruction produced a new interesting value, add the SSA edge + // for its result ID. + if (instr->result_id() > 0) { + AddSSAEdges(instr->result_id()); + } + + // If there are multiple outgoing control flow edges and we know which one + // will be taken, add the destination block to the CFG work list. + if (dest_bb) { + blocks_.push(dest_bb); + } + changed = true; + } + + // At this point, we are dealing with instructions that are in status + // kInteresting or kNotInteresting. To decide whether this instruction should + // be simulated again, we examine its operands. If at least one operand O is + // defined at an instruction D that should be simulated again, then the output + // of D might affect |instr|, so we should simulate |instr| again. + bool has_operands_to_simulate = false; + ir::BasicBlock* instr_bb = ctx_->get_instr_block(instr); + if (instr->opcode() == SpvOpPhi) { + // For Phi instructions, an operand causes the Phi to be simulated again if + // the operand comes from an edge that has not yet been traversed or if its + // definition should be simulated again. + for (uint32_t i = 2; i < instr->NumOperands(); i += 2) { + // Phi arguments come in pairs. Index 'i' contains the + // variable id, index 'i + 1' is the originating block id. + assert(i % 2 == 0 && i < instr->NumOperands() - 1 && + "malformed Phi arguments"); + + uint32_t arg_id = instr->GetSingleWordOperand(i); + ir::Instruction* arg_def_instr = get_def_use_mgr()->GetDef(arg_id); + uint32_t in_label_id = instr->GetSingleWordOperand(i + 1); + ir::Instruction* in_label_instr = get_def_use_mgr()->GetDef(in_label_id); + ir::BasicBlock* in_bb = ctx_->get_instr_block(in_label_instr); + Edge edge(in_bb, instr_bb); + + if (!IsEdgeExecutable(edge) || ShouldSimulateAgain(arg_def_instr)) { + has_operands_to_simulate = true; + break; + } + } + } else { + // For regular instructions, check if the defining instruction of each + // operand needs to be simulated again. If so, then this instruction should + // also be simulated again. + instr->ForEachInId([&has_operands_to_simulate, this](const uint32_t* use) { + ir::Instruction* def_instr = get_def_use_mgr()->GetDef(*use); + if (ShouldSimulateAgain(def_instr)) { + has_operands_to_simulate = true; + return; + } + }); + } + + if (!has_operands_to_simulate) { + DontSimulateAgain(instr); + } + + return changed; +} + +bool SSAPropagator::Simulate(ir::BasicBlock* block) { + if (block == cfg_->pseudo_exit_block()) { + return false; + } + + // Always simulate Phi instructions, even if we have simulated this block + // before. We do this because Phi instructions receive their inputs from + // incoming edges. When those edges are marked executable, the corresponding + // operand can be simulated. + bool changed = false; + block->ForEachPhiInst( + [&changed, this](ir::Instruction* instr) { changed |= Simulate(instr); }); + + // If this is the first time this block is being simulated, simulate every + // statement in it. + if (!BlockHasBeenSimulated(block)) { + block->ForEachInst([this, &changed](ir::Instruction* instr) { + if (instr->opcode() != SpvOpPhi) { + changed |= Simulate(instr); + } + }); + + MarkBlockSimulated(block); + + // If this block has exactly one successor, mark the edge to its successor + // as executable. + if (bb_succs_.at(block).size() == 1) { + AddControlEdge(bb_succs_.at(block).at(0)); + } + } + + return changed; +} + +void SSAPropagator::Initialize(ir::Function* fn) { + // Compute predecessor and successor blocks for every block in |fn|'s CFG. + // TODO(dnovillo): Move this to ir::CFG and always build them. Alternately, + // move it to IRContext and build CFG preds/succs on-demand. + bb_succs_[cfg_->pseudo_entry_block()].push_back( + Edge(cfg_->pseudo_entry_block(), fn->entry().get())); + + for (auto& block : *fn) { + block.ForEachSuccessorLabel([this, &block](uint32_t label_id) { + ir::BasicBlock* succ_bb = + ctx_->get_instr_block(get_def_use_mgr()->GetDef(label_id)); + bb_succs_[&block].push_back(Edge(&block, succ_bb)); + bb_preds_[succ_bb].push_back(Edge(succ_bb, &block)); + }); + if (block.IsReturn()) { + bb_succs_[&block].push_back(Edge(&block, cfg_->pseudo_exit_block())); + bb_preds_[cfg_->pseudo_exit_block()].push_back( + Edge(cfg_->pseudo_exit_block(), &block)); + } + } + + // Add the edges out of the entry block to seed the propagator. + const auto& entry_succs = bb_succs_[cfg_->pseudo_entry_block()]; + for (const auto& e : entry_succs) { + AddControlEdge(e); + } +} + +bool SSAPropagator::Run(ir::Function* fn) { + Initialize(fn); + + bool changed = false; + while (!blocks_.empty() || !ssa_edge_uses_.empty()) { + // Simulate all blocks first. Simulating blocks will add SSA edges to + // follow after all the blocks have been simulated. + if (!blocks_.empty()) { + auto block = blocks_.front(); + changed |= Simulate(block); + blocks_.pop(); + continue; + } + + // Simulate edges from the SSA queue. + if (!ssa_edge_uses_.empty()) { + ir::Instruction* instr = ssa_edge_uses_.front(); + changed |= Simulate(instr); + ssa_edge_uses_.pop(); + } + } + + return changed; +} + +} // namespace opt +} // namespace spvtools diff --git a/source/opt/propagator.h b/source/opt/propagator.h new file mode 100644 index 00000000..454bcdfc --- /dev/null +++ b/source/opt/propagator.h @@ -0,0 +1,296 @@ +// Copyright (c) 2017 Google Inc. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#ifndef LIBSPIRV_OPT_PROPAGATOR_H_ +#define LIBSPIRV_OPT_PROPAGATOR_H_ + +#include <functional> +#include <queue> +#include <set> +#include <unordered_map> +#include <unordered_set> +#include <vector> + +#include "cfg.h" +#include "ir_context.h" +#include "module.h" + +namespace spvtools { +namespace opt { + +// Represents a CFG control edge. +struct Edge { + explicit Edge(ir::BasicBlock* b1, ir::BasicBlock* b2) + : source(b1), dest(b2) {} + ir::BasicBlock* source; + ir::BasicBlock* dest; + bool operator<(const Edge& o) const { + return source < o.source || dest < o.dest; + } +}; + +// This class implements a generic value propagation algorithm based on the +// conditional constant propagation algorithm proposed in +// +// Constant propagation with conditional branches, +// Wegman and Zadeck, ACM TOPLAS 13(2):181-210. +// +// A Propagation Engine for GCC +// Diego Novillo, GCC Summit 2005 +// http://ols.fedoraproject.org/GCC/Reprints-2005/novillo-Reprint.pdf +// +// The purpose of this implementation is to act as a common framework for any +// transformation that needs to propagate values from statements producing new +// values to statements using those values. Simulation proceeds as follows: +// +// 1- Initially, all edges of the CFG are marked not executable and the CFG +// worklist is seeded with all the statements in the entry basic block. +// +// 2- Every instruction I is simulated by calling a pass-provided function +// |visit_fn|. This function is responsible for three things: +// +// (a) Keep a value table of interesting values. This table maps SSA IDs to +// their values. For instance, when implementing constant propagation, +// given a store operation 'OpStore %f %int_3', |visit_fn| should assign +// the value 3 to the table slot for %f. +// +// In general, |visit_fn| will need to use the value table to replace its +// operands, fold the result and decide whether a new value needs to be +// stored in the table. |visit_fn| should only create a new mapping in +// the value table if all the operands in the instruction are known and +// present in the value table. +// +// (b) Return a status indicator to direct the propagator logic. Once the +// instruction is simulated, the propagator needs to know whether this +// instruction produced something interesting. This is indicated via +// |visit_fn|'s return value: +// +// SSAPropagator::kNotInteresting: Instruction I produces nothing of +// interest and does not affect any of the work lists. The +// propagator will visit the statement again if any of its operands +// produce an interesting value in the future. +// +// |visit_fn| should always return this value when it is not sure +// whether the instruction will produce an interesting value in the +// future or not. For instance, for constant propagation, an OpIAdd +// instruction may produce a constant if its two operands are +// constant, but the first time we visit the instruction, we still +// may not have its operands in the value table. +// +// SSAPropagator::kVarying: The value produced by I cannot be determined +// at compile time. Further simulation of I is not required. The +// propagator will not visit this instruction again. Additionally, +// the propagator will add all the instructions at the end of SSA +// def-use edges to be simulated again. +// +// If I is a basic block terminator, it will mark all outgoing edges +// as executable so they are traversed one more time. Eventually +// the kVarying attribute will be spread out to all the data and +// control dependents for I. +// +// It is important for propagation to use kVarying as a bottom value +// for the propagation lattice. It should never be possible for an +// instruction to return kVarying once and kInteresting on a second +// visit. Otherwise, propagation would not stabilize. +// +// SSAPropagator::kInteresting: Instruction I produces a value that can +// be computed at compile time. In this case, |visit_fn| should +// create a new mapping between I's result ID and the produced +// value. Much like the kNotInteresting case, the propagator will +// visit this instruction again if any of its operands changes. +// This is useful when the statement changes from one interesting +// state to another. +// +// (c) For conditional branches, |visit_fn| may decide which edge to take out +// of I's basic block. For example, if the operand for an OpSwitch is +// known to take a specific constant value, |visit_fn| should figure out +// the destination basic block and pass it back by setting the second +// argument to |visit_fn|. +// +// At the end of propagation, values in the value table are guaranteed to be +// stable and can be replaced in the IR. +// +// 3- The propagator keeps two work queues. Instructions are only added to +// these queues if they produce an interesting or varying value. None of this +// should be handled by |visit_fn|. The propagator keeps track of this +// automatically (see SSAPropagator::Simulate for implementation). +// +// CFG blocks: contains the queue of blocks to be simulated. +// Blocks are added to this queue if their incoming edges are +// executable. +// +// SSA Edges: An SSA edge is a def-use edge between a value-producing +// instruction and its use instruction. The SSA edges list +// contains the statements at the end of a def-use edge that need +// to be re-visited when an instruction produces a kVarying or +// kInteresting result. +// +// 4- Simulation terminates when all work queues are drained. +// +// +// EXAMPLE: Basic constant store propagator. +// +// Suppose we want to propagate all constant assignments of the form "OpStore +// %id %cst" where "%id" is some variable and "%cst" an OpConstant. The +// following code builds a table |values| where every id that was assigned a +// constant value is mapped to the constant value it was assigned. +// +// auto ctx = spvtools::BuildModule(...); +// std::map<uint32_t, uint32_t> values; +// const auto visit_fn = [&ctx, &values](ir::Instruction* instr, +// ir::BasicBlock** dest_bb) { +// if (instr->opcode() == SpvOpStore) { +// uint32_t rhs_id = instr->GetSingleWordOperand(1); +// ir::Instruction* rhs_def = ctx->get_def_use_mgr()->GetDef(rhs_id); +// if (rhs_def->opcode() == SpvOpConstant) { +// uint32_t val = rhs_def->GetSingleWordOperand(2); +// values[rhs_id] = val; +// return opt::SSAPropagator::kInteresting; +// } +// } +// return opt::SSAPropagator::kVarying; +// }; +// opt::SSAPropagator propagator(ctx.get(), &cfg, visit_fn); +// propagator.Run(&fn); +// +// Given the code: +// +// %int_4 = OpConstant %int 4 +// %int_3 = OpConstant %int 3 +// %int_1 = OpConstant %int 1 +// OpStore %x %int_4 +// OpStore %y %int_3 +// OpStore %z %int_1 +// +// After SSAPropagator::Run returns, the |values| map will contain the entries: +// values[%x] = 4, values[%y] = 3, and, values[%z] = 1. +class SSAPropagator { + public: + // Lattice values used for propagation. See class documentation for + // a description. + enum PropStatus { kNotInteresting, kInteresting, kVarying }; + + using VisitFunction = + std::function<PropStatus(ir::Instruction*, ir::BasicBlock**)>; + + SSAPropagator(ir::IRContext* context, ir::CFG* cfg, + const VisitFunction& visit_fn) + : ctx_(context), cfg_(cfg), visit_fn_(visit_fn) {} + + // Run the propagator on function |fn|. Returns true if changes were made to + // the function. Otherwise, it returns false. + bool Run(ir::Function* fn); + + private: + // Initialize processing. + void Initialize(ir::Function* fn); + + // Simulate the execution |block| by calling |visit_fn_| on every instruction + // in it. + bool Simulate(ir::BasicBlock* block); + + // Simulate the execution of |instr| by replacing all the known values in + // every operand and determining whether the result is interesting for + // propagation. This invokes the callback function |visit_fn_| to determine + // the value computed by |instr|. + bool Simulate(ir::Instruction* instr); + + // Returns true if |instr| should be simulated again. + bool ShouldSimulateAgain(ir::Instruction* instr) const { + return do_not_simulate_.find(instr) == do_not_simulate_.end(); + } + + // Add |instr| to the set of instructions not to simulate again. + void DontSimulateAgain(ir::Instruction* instr) { + do_not_simulate_.insert(instr); + } + + // Returns true if |block| has been simulated already. + bool BlockHasBeenSimulated(ir::BasicBlock* block) { + return simulated_blocks_.find(block) != simulated_blocks_.end(); + } + + // Marks block |block| as simulated. + void MarkBlockSimulated(ir::BasicBlock* block) { + simulated_blocks_.insert(block); + } + + // Marks |edge| as executable. Returns false if the edge was already marked + // as executable. + bool MarkEdgeExecutable(const Edge& edge) { + return executable_edges_.insert(edge).second; + } + + // Returns true if |edge| has been marked as executable. + bool IsEdgeExecutable(const Edge& edge) { + return executable_edges_.find(edge) != executable_edges_.end(); + } + + // Returns a pointer to the def-use manager for |ctx_|. + analysis::DefUseManager* get_def_use_mgr() const { + return ctx_->get_def_use_mgr(); + } + + // If the CFG edge |e| has not been executed, add its destination block to the + // work list. + void AddControlEdge(const Edge& e); + + // Add all the instructions that use |id| to the SSA edges work list. + void AddSSAEdges(uint32_t id); + + // IR context to use. + ir::IRContext* ctx_; + + // CFG to propagate values on. TODO(dnovillo): The CFG should be part of + // IRContext. + ir::CFG* cfg_; + + // Function that visits instructions during simulation. The output of this + // function is used to determine if the simulated instruction produced a value + // interesting for propagation. The function is responsible for keeping + // track of interesting values by storing them in some user-provided map. + VisitFunction visit_fn_; + + // SSA def-use edges to traverse. Each entry is a destination statement for an + // SSA def-use edge as returned by |def_use_manager_|. + std::queue<ir::Instruction*> ssa_edge_uses_; + + // Blocks to simulate. + std::queue<ir::BasicBlock*> blocks_; + + // Blocks simulated during propagation. + std::unordered_set<ir::BasicBlock*> simulated_blocks_; + + // Set of instructions that should not be simulated again because they have + // been found to be in the kVarying state. + std::unordered_set<ir::Instruction*> do_not_simulate_; + + // Map between a basic block and its predecessor edges. + // TODO(dnovillo): Move this to ir::CFG and always build them. Alternately, + // move it to IRContext and build CFG preds/succs on-demand. + std::unordered_map<ir::BasicBlock*, std::vector<Edge>> bb_preds_; + + // Map between a basic block and its successor edges. + // TODO(dnovillo): Move this to ir::CFG and always build them. Alternately, + // move it to IRContext and build CFG preds/succs on-demand. + std::unordered_map<ir::BasicBlock*, std::vector<Edge>> bb_succs_; + + // Set of executable CFG edges. + std::set<Edge> executable_edges_; +}; + +} // namespace opt +} // namespace spvtools + +#endif // LIBSPIRV_OPT_PROPAGATOR_H_ diff --git a/test/opt/CMakeLists.txt b/test/opt/CMakeLists.txt index 891eba34..b6e75fcb 100644 --- a/test/opt/CMakeLists.txt +++ b/test/opt/CMakeLists.txt @@ -218,3 +218,8 @@ add_spvtools_unittest(TARGET local_redundancy_elimination SRCS local_redundancy_elimination_test.cpp pass_utils.cpp LIBS SPIRV-Tools-opt ) + +add_spvtools_unittest(TARGET propagator + SRCS propagator_test.cpp + LIBS SPIRV-Tools-opt +) diff --git a/test/opt/aggressive_dead_code_elim_test.cpp b/test/opt/aggressive_dead_code_elim_test.cpp index 6982e517..0fc7b20f 100644 --- a/test/opt/aggressive_dead_code_elim_test.cpp +++ b/test/opt/aggressive_dead_code_elim_test.cpp @@ -1608,6 +1608,117 @@ OpFunctionEnd predefs_before + func_before, predefs_after + func_after, true, true); } +// This test fails. OpSwitch is not handled by ADCE. +// (https://github.com/KhronosGroup/SPIRV-Tools/issues/1021). +TEST_F(AggressiveDCETest, DISABLED_EliminateDeadSwitch) { + // #version 450 + // + // layout(location = 0) in vec4 BaseColor; + // layout(location = 1) in flat int x; + // layout(location = 0) out vec4 OutColor; + // + // void main() + // { + // float d; + // switch (x) { + // case 0: + // d = BaseColor.y; + // } + // OutColor = vec4(1.0,1.0,1.0,1.0); + // } + const std::string before = + R"(OpCapability Shader + %1 = OpExtInstImport "GLSL.std.450" + OpMemoryModel Logical GLSL450 + OpEntryPoint Fragment %main "main" %x %BaseColor %OutColor + OpExecutionMode %main OriginUpperLeft + OpSource GLSL 450 + OpName %main "main" + OpName %x "x" + OpName %d "d" + OpName %BaseColor "BaseColor" + OpName %OutColor "OutColor" + OpDecorate %x Flat + OpDecorate %x Location 1 + OpDecorate %BaseColor Location 0 + OpDecorate %OutColor Location 0 + %void = OpTypeVoid + %3 = OpTypeFunction %void + %int = OpTypeInt 32 1 +%_ptr_Input_int = OpTypePointer Input %int + %x = OpVariable %_ptr_Input_int Input + %float = OpTypeFloat 32 +%_ptr_Function_float = OpTypePointer Function %float + %v4float = OpTypeVector %float 4 +%_ptr_Input_v4float = OpTypePointer Input %v4float + %BaseColor = OpVariable %_ptr_Input_v4float Input + %uint = OpTypeInt 32 0 + %uint_1 = OpConstant %uint 1 +%_ptr_Input_float = OpTypePointer Input %float +%_ptr_Output_v4float = OpTypePointer Output %v4float + %OutColor = OpVariable %_ptr_Output_v4float Output + %float_1 = OpConstant %float 1 + %27 = OpConstantComposite %v4float %float_1 %float_1 %float_1 %float_1 + %main = OpFunction %void None %3 + %5 = OpLabel + %d = OpVariable %_ptr_Function_float Function + %9 = OpLoad %int %x + OpSelectionMerge %11 None + OpSwitch %9 %11 0 %10 + %10 = OpLabel + %21 = OpAccessChain %_ptr_Input_float %BaseColor %uint_1 + %22 = OpLoad %float %21 + OpStore %d %22 + OpBranch %11 + %11 = OpLabel + OpStore %OutColor %27 + OpReturn + OpFunctionEnd)"; + + const std::string after = + R"(OpCapability Shader +%1 = OpExtInstImport "GLSL.std.450" +OpMemoryModel Logical GLSL450 +OpEntryPoint Fragment %main "main" %x %BaseColor %OutColor +OpExecutionMode %main OriginUpperLeft +OpSource GLSL 450 +OpName %main "main" +OpName %x "x" +OpName %BaseColor "BaseColor" +OpName %OutColor "OutColor" +OpDecorate %x Flat +OpDecorate %x Location 1 +OpDecorate %BaseColor Location 0 +OpDecorate %OutColor Location 0 +%void = OpTypeVoid +%8 = OpTypeFunction %void +%int = OpTypeInt 32 1 +%_ptr_Input_int = OpTypePointer Input %int +%x = OpVariable %_ptr_Input_int Input +%float = OpTypeFloat 32 +%_ptr_Function_float = OpTypePointer Function %float +%v4float = OpTypeVector %float 4 +%_ptr_Input_v4float = OpTypePointer Input %v4float +%BaseColor = OpVariable %_ptr_Input_v4float Input +%uint = OpTypeInt 32 0 +%uint_1 = OpConstant %uint 1 +%_ptr_Input_float = OpTypePointer Input %float +%_ptr_Output_v4float = OpTypePointer Output %v4float +%OutColor = OpVariable %_ptr_Output_v4float Output +%float_1 = OpConstant %float 1 +%20 = OpConstantComposite %v4float %float_1 %float_1 %float_1 %float_1 +%main = OpFunction %void None %8 +%21 = OpLabel +OpBranch %11 +%11 = OpLabel +OpStore %OutColor %27 +OpReturn +OpFunctionEnd +)"; + + SinglePassRunAndCheck<opt::AggressiveDCEPass>(before, after, true, true); +} + TEST_F(AggressiveDCETest, EliminateDeadIfThenElseNested) { // #version 450 // diff --git a/test/opt/propagator_test.cpp b/test/opt/propagator_test.cpp new file mode 100644 index 00000000..cd3f0d41 --- /dev/null +++ b/test/opt/propagator_test.cpp @@ -0,0 +1,217 @@ +// Copyright (c) 2017 Google Inc. +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. + +#include <gmock/gmock.h> +#include <gtest/gtest.h> + +#include "opt/build_module.h" +#include "opt/cfg.h" +#include "opt/ir_context.h" +#include "opt/pass.h" +#include "opt/propagator.h" + +namespace { + +using namespace spvtools; + +using ::testing::UnorderedElementsAre; + +class PropagatorTest : public testing::Test { + protected: + virtual void TearDown() { + ctx_.reset(nullptr); + cfg_.reset(nullptr); + values_.clear(); + values_vec_.clear(); + } + + void Assemble(const std::string& input) { + ctx_ = BuildModule(SPV_ENV_UNIVERSAL_1_1, nullptr, input); + ASSERT_NE(nullptr, ctx_) << "Assembling failed for shader:\n" + << input << "\n"; + cfg_.reset(new ir::CFG(ctx_->module())); + } + + bool Propagate(const opt::SSAPropagator::VisitFunction& visit_fn) { + opt::SSAPropagator propagator(ctx_.get(), cfg_.get(), visit_fn); + bool retval = false; + for (auto& fn : *ctx_->module()) { + retval |= propagator.Run(&fn); + } + return retval; + } + + const std::vector<uint32_t>& GetValues() { + values_vec_.clear(); + for (const auto& it : values_) { + values_vec_.push_back(it.second); + } + return values_vec_; + } + + std::unique_ptr<ir::IRContext> ctx_; + std::unique_ptr<ir::CFG> cfg_; + std::map<uint32_t, uint32_t> values_; + std::vector<uint32_t> values_vec_; +}; + +TEST_F(PropagatorTest, LocalPropagate) { + const std::string spv_asm = R"( + OpCapability Shader + %1 = OpExtInstImport "GLSL.std.450" + OpMemoryModel Logical GLSL450 + OpEntryPoint Fragment %main "main" %outparm + OpExecutionMode %main OriginUpperLeft + OpSource GLSL 450 + OpName %main "main" + OpName %x "x" + OpName %y "y" + OpName %z "z" + OpName %outparm "outparm" + OpDecorate %outparm Location 0 + %void = OpTypeVoid + %3 = OpTypeFunction %void + %int = OpTypeInt 32 1 +%_ptr_Function_int = OpTypePointer Function %int + %int_4 = OpConstant %int 4 + %int_3 = OpConstant %int 3 + %int_1 = OpConstant %int 1 +%_ptr_Output_int = OpTypePointer Output %int + %outparm = OpVariable %_ptr_Output_int Output + %main = OpFunction %void None %3 + %5 = OpLabel + %x = OpVariable %_ptr_Function_int Function + %y = OpVariable %_ptr_Function_int Function + %z = OpVariable %_ptr_Function_int Function + OpStore %x %int_4 + OpStore %y %int_3 + OpStore %z %int_1 + %20 = OpLoad %int %z + OpStore %outparm %20 + OpReturn + OpFunctionEnd + )"; + Assemble(spv_asm); + + const auto visit_fn = [this](ir::Instruction* instr, + ir::BasicBlock** dest_bb) { + *dest_bb = nullptr; + if (instr->opcode() == SpvOpStore) { + uint32_t lhs_id = instr->GetSingleWordOperand(0); + uint32_t rhs_id = instr->GetSingleWordOperand(1); + ir::Instruction* rhs_def = ctx_->get_def_use_mgr()->GetDef(rhs_id); + if (rhs_def->opcode() == SpvOpConstant) { + uint32_t val = rhs_def->GetSingleWordOperand(2); + values_[lhs_id] = val; + return opt::SSAPropagator::kInteresting; + } + } + return opt::SSAPropagator::kVarying; + }; + + EXPECT_TRUE(Propagate(visit_fn)); + EXPECT_THAT(GetValues(), UnorderedElementsAre(4, 3, 1)); +} + +TEST_F(PropagatorTest, PropagateThroughPhis) { + const std::string spv_asm = R"( + OpCapability Shader + %1 = OpExtInstImport "GLSL.std.450" + OpMemoryModel Logical GLSL450 + OpEntryPoint Fragment %main "main" %x %outparm + OpExecutionMode %main OriginUpperLeft + OpSource GLSL 450 + OpName %main "main" + OpName %x "x" + OpName %outparm "outparm" + OpDecorate %x Flat + OpDecorate %x Location 0 + OpDecorate %outparm Location 0 + %void = OpTypeVoid + %3 = OpTypeFunction %void + %int = OpTypeInt 32 1 + %bool = OpTypeBool +%_ptr_Function_int = OpTypePointer Function %int + %int_4 = OpConstant %int 4 + %int_3 = OpConstant %int 3 + %int_1 = OpConstant %int 1 +%_ptr_Input_int = OpTypePointer Input %int + %x = OpVariable %_ptr_Input_int Input +%_ptr_Output_int = OpTypePointer Output %int + %outparm = OpVariable %_ptr_Output_int Output + %main = OpFunction %void None %3 + %4 = OpLabel + %5 = OpLoad %int %x + %6 = OpSGreaterThan %bool %5 %int_3 + OpSelectionMerge %25 None + OpBranchConditional %6 %22 %23 + %22 = OpLabel + %7 = OpLoad %int %int_4 + OpBranch %25 + %23 = OpLabel + %8 = OpLoad %int %int_4 + OpBranch %25 + %25 = OpLabel + %35 = OpPhi %int %7 %22 %8 %23 + OpStore %outparm %35 + OpReturn + OpFunctionEnd + )"; + + Assemble(spv_asm); + + ir::Instruction *phi_instr = nullptr; + const auto visit_fn = [this, &phi_instr](ir::Instruction* instr, + ir::BasicBlock** dest_bb) { + *dest_bb = nullptr; + if (instr->opcode() == SpvOpLoad) { + uint32_t rhs_id = instr->GetSingleWordOperand(2); + ir::Instruction* rhs_def = ctx_->get_def_use_mgr()->GetDef(rhs_id); + if (rhs_def->opcode() == SpvOpConstant) { + uint32_t val = rhs_def->GetSingleWordOperand(2); + values_[instr->result_id()] = val; + return opt::SSAPropagator::kInteresting; + } + } else if (instr->opcode() == SpvOpPhi) { + phi_instr = instr; + opt::SSAPropagator::PropStatus retval; + for (uint32_t i = 2; i < instr->NumOperands(); i += 2) { + uint32_t phi_arg_id = instr->GetSingleWordOperand(i); + auto it = values_.find(phi_arg_id); + if (it != values_.end()) { + EXPECT_EQ(it->second, 4); + retval = opt::SSAPropagator::kInteresting; + values_[instr->result_id()] = it->second; + } else { + retval = opt::SSAPropagator::kNotInteresting; + break; + } + } + return retval; + } + + return opt::SSAPropagator::kVarying; + }; + + EXPECT_TRUE(Propagate(visit_fn)); + + // The propagator should've concluded that the Phi instruction has a constant + // value of 4. + EXPECT_NE(phi_instr, nullptr); + EXPECT_EQ(values_[phi_instr->result_id()], 4); + + EXPECT_THAT(GetValues(), UnorderedElementsAre(4, 4, 4)); +} + +} // namespace |