blob: 8c0472cd29dd05224c39a252e14ef6b8ac3facfc [file] [log] [blame]
// Copyright (c) 2016 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
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// See the License for the specific language governing permissions and
// limitations under the License.
#include <algorithm>
#include <functional>
#include <memory>
#include <string>
#include <unordered_set>
#include <utility>
#include <vector>
#include "source/opt/basic_block.h"
#include "source/opt/instruction.h"
#include "source/opt/iterator.h"
namespace spvtools {
namespace opt {
class CFG;
class IRContext;
class Module;
// A SPIR-V function.
class Function {
using iterator = UptrVectorIterator<BasicBlock>;
using const_iterator = UptrVectorIterator<BasicBlock, true>;
// Creates a function instance declared by the given OpFunction instruction
// |def_inst|.
inline explicit Function(std::unique_ptr<Instruction> def_inst);
explicit Function(const Function& f) = delete;
// Creates a clone of the instruction in the given |context|
// The parent module will default to null and needs to be explicitly set by
// the user.
Function* Clone(IRContext*) const;
// The OpFunction instruction that begins the definition of this function.
Instruction& DefInst() { return *def_inst_; }
const Instruction& DefInst() const { return *def_inst_; }
// Appends a parameter to this function.
inline void AddParameter(std::unique_ptr<Instruction> p);
// Appends a debug instruction in function header to this function.
inline void AddDebugInstructionInHeader(std::unique_ptr<Instruction> p);
// Appends a basic block to this function.
inline void AddBasicBlock(std::unique_ptr<BasicBlock> b);
// Appends a basic block to this function at the position |ip|.
inline void AddBasicBlock(std::unique_ptr<BasicBlock> b, iterator ip);
template <typename T>
inline void AddBasicBlocks(T begin, T end, iterator ip);
// Move basic block with |id| to the position after |ip|. Both have to be
// contained in this function.
inline void MoveBasicBlockToAfter(uint32_t id, BasicBlock* ip);
// Delete all basic blocks that contain no instructions.
inline void RemoveEmptyBlocks();
// Removes a parameter from the function with result id equal to |id|.
// Does nothing if the function doesn't have such a parameter.
inline void RemoveParameter(uint32_t id);
// Saves the given function end instruction.
inline void SetFunctionEnd(std::unique_ptr<Instruction> end_inst);
// Add a non-semantic instruction that succeeds this function in the module.
// These instructions are maintained in the order they are added.
inline void AddNonSemanticInstruction(
std::unique_ptr<Instruction> non_semantic);
// Returns the given function end instruction.
inline Instruction* EndInst() { return end_inst_.get(); }
inline const Instruction* EndInst() const { return end_inst_.get(); }
// Returns function's id
inline uint32_t result_id() const { return def_inst_->result_id(); }
// Returns function's return type id
inline uint32_t type_id() const { return def_inst_->type_id(); }
// Returns the function's control mask
inline uint32_t control_mask() const { return def_inst_->GetSingleWordInOperand(0); }
// Returns the entry basic block for this function.
const std::unique_ptr<BasicBlock>& entry() const { return blocks_.front(); }
// Returns the last basic block in this function.
BasicBlock* tail() { return blocks_.back().get(); }
const BasicBlock* tail() const { return blocks_.back().get(); }
iterator begin() { return iterator(&blocks_, blocks_.begin()); }
iterator end() { return iterator(&blocks_, blocks_.end()); }
const_iterator begin() const { return cbegin(); }
const_iterator end() const { return cend(); }
const_iterator cbegin() const {
return const_iterator(&blocks_, blocks_.cbegin());
const_iterator cend() const {
return const_iterator(&blocks_, blocks_.cend());
// Returns an iterator to the basic block |id|.
iterator FindBlock(uint32_t bb_id) {
return std::find_if(begin(), end(), [bb_id](const BasicBlock& it_bb) {
return bb_id ==;
// Runs the given function |f| on instructions in this function, in order,
// and optionally on debug line instructions that might precede them and
// non-semantic instructions that succceed the function.
void ForEachInst(const std::function<void(Instruction*)>& f,
bool run_on_debug_line_insts = false,
bool run_on_non_semantic_insts = false);
void ForEachInst(const std::function<void(const Instruction*)>& f,
bool run_on_debug_line_insts = false,
bool run_on_non_semantic_insts = false) const;
// Runs the given function |f| on instructions in this function, in order,
// and optionally on debug line instructions that might precede them and
// non-semantic instructions that succeed the function. If |f| returns
// false, iteration is terminated and this function returns false.
bool WhileEachInst(const std::function<bool(Instruction*)>& f,
bool run_on_debug_line_insts = false,
bool run_on_non_semantic_insts = false);
bool WhileEachInst(const std::function<bool(const Instruction*)>& f,
bool run_on_debug_line_insts = false,
bool run_on_non_semantic_insts = false) const;
// Runs the given function |f| on each parameter instruction in this function,
// in order, and optionally on debug line instructions that might precede
// them.
void ForEachParam(const std::function<void(const Instruction*)>& f,
bool run_on_debug_line_insts = false) const;
void ForEachParam(const std::function<void(Instruction*)>& f,
bool run_on_debug_line_insts = false);
// Runs the given function |f| on each debug instruction in this function's
// header in order.
void ForEachDebugInstructionsInHeader(
const std::function<void(Instruction*)>& f);
BasicBlock* InsertBasicBlockAfter(std::unique_ptr<BasicBlock>&& new_block,
BasicBlock* position);
BasicBlock* InsertBasicBlockBefore(std::unique_ptr<BasicBlock>&& new_block,
BasicBlock* position);
// Returns true if the function has a return block other than the exit block.
bool HasEarlyReturn() const;
// Returns true if the function calls itself either directly or indirectly.
bool IsRecursive() const;
// Pretty-prints all the basic blocks in this function into a std::string.
// |options| are the disassembly options. SPV_BINARY_TO_TEXT_OPTION_NO_HEADER
// is always added to |options|.
std::string PrettyPrint(uint32_t options = 0u) const;
// Dump this function on stderr. Useful when running interactive
// debuggers.
void Dump() const;
// Returns true is a function declaration and not a function definition.
bool IsDeclaration() { return begin() == end(); }
// Reorders the basic blocks in the function to match the structured order.
void ReorderBasicBlocksInStructuredOrder();
// Reorders the basic blocks in the function to match the order given by the
// range |{begin,end}|. The range must contain every basic block in the
// function, and no extras.
template <class It>
void ReorderBasicBlocks(It begin, It end);
template <class It>
bool ContainsAllBlocksInTheFunction(It begin, It end);
// The OpFunction instruction that begins the definition of this function.
std::unique_ptr<Instruction> def_inst_;
// All parameters to this function.
std::vector<std::unique_ptr<Instruction>> params_;
// All debug instructions in this function's header.
InstructionList debug_insts_in_header_;
// All basic blocks inside this function in specification order
std::vector<std::unique_ptr<BasicBlock>> blocks_;
// The OpFunctionEnd instruction.
std::unique_ptr<Instruction> end_inst_;
// Non-semantic instructions succeeded by this function.
std::vector<std::unique_ptr<Instruction>> non_semantic_;
// Pretty-prints |func| to |str|. Returns |str|.
std::ostream& operator<<(std::ostream& str, const Function& func);
inline Function::Function(std::unique_ptr<Instruction> def_inst)
: def_inst_(std::move(def_inst)), end_inst_() {}
inline void Function::AddParameter(std::unique_ptr<Instruction> p) {
inline void Function::AddDebugInstructionInHeader(
std::unique_ptr<Instruction> p) {
inline void Function::AddBasicBlock(std::unique_ptr<BasicBlock> b) {
AddBasicBlock(std::move(b), end());
inline void Function::AddBasicBlock(std::unique_ptr<BasicBlock> b,
iterator ip) {
template <typename T>
inline void Function::AddBasicBlocks(T src_begin, T src_end, iterator ip) {
blocks_.insert(ip.Get(), std::make_move_iterator(src_begin),
inline void Function::MoveBasicBlockToAfter(uint32_t id, BasicBlock* ip) {
std::unique_ptr<BasicBlock> block_to_move = std::move(*FindBlock(id).Get());
blocks_.erase(std::find(std::begin(blocks_), std::end(blocks_), nullptr));
assert(block_to_move->GetParent() == ip->GetParent() &&
"Both blocks have to be in the same function.");
InsertBasicBlockAfter(std::move(block_to_move), ip);
inline void Function::RemoveEmptyBlocks() {
auto first_empty =
std::remove_if(std::begin(blocks_), std::end(blocks_),
[](const std::unique_ptr<BasicBlock>& bb) -> bool {
return bb->GetLabelInst()->opcode() == spv::Op::OpNop;
blocks_.erase(first_empty, std::end(blocks_));
inline void Function::RemoveParameter(uint32_t id) {
params_.erase(std::remove_if(params_.begin(), params_.end(),
[id](const std::unique_ptr<Instruction>& param) {
return param->result_id() == id;
inline void Function::SetFunctionEnd(std::unique_ptr<Instruction> end_inst) {
end_inst_ = std::move(end_inst);
inline void Function::AddNonSemanticInstruction(
std::unique_ptr<Instruction> non_semantic) {
template <class It>
void Function::ReorderBasicBlocks(It begin, It end) {
// Asserts to make sure every node in the function is in new_order.
assert(ContainsAllBlocksInTheFunction(begin, end));
// We have a pointer to all the elements in order, so we can release all
// pointers in |block_|, and then create the new unique pointers from |{begin,
// end}|.
std::for_each(blocks_.begin(), blocks_.end(),
[](std::unique_ptr<BasicBlock>& bb) { bb.release(); });
std::transform(begin, end, blocks_.begin(), [](BasicBlock* bb) {
return std::unique_ptr<BasicBlock>(bb);
template <class It>
bool Function::ContainsAllBlocksInTheFunction(It begin, It end) {
std::unordered_multiset<BasicBlock*> range(begin, end);
if (range.size() != blocks_.size()) {
return false;
for (auto& bb : blocks_) {
if (range.count(bb.get()) == 0) return false;
return true;
} // namespace opt
} // namespace spvtools