blob: 7ed41de58f8869ef66ad3e35b19486b36e274d5b [file] [log] [blame]
// Copyright (c) 2022 Google LLC.
//
// 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 "source/diff/diff.h"
#include "source/diff/lcs.h"
#include "source/disassemble.h"
#include "source/ext_inst.h"
#include "source/latest_version_spirv_header.h"
#include "source/print.h"
#include "spirv-tools/libspirv.hpp"
namespace spvtools {
namespace diff {
namespace {
// A map from an id to the instruction that defines it.
using IdToInstructionMap = std::vector<const opt::Instruction*>;
// A map from an id to the instructions that decorate it, or name it, etc.
using IdToInfoMap = std::vector<std::vector<const opt::Instruction*>>;
// A map from an instruction to another, used for instructions without id.
using InstructionToInstructionMap =
std::unordered_map<const opt::Instruction*, const opt::Instruction*>;
// A flat list of instructions in a function for easier iteration.
using InstructionList = std::vector<const opt::Instruction*>;
// A map from a function to its list of instructions.
using FunctionInstMap = std::map<uint32_t, InstructionList>;
// A list of ids with some similar property, for example functions with the same
// name.
using IdGroup = std::vector<uint32_t>;
// A map of names to ids with the same name. This is an ordered map so
// different implementations produce identical results.
using IdGroupMapByName = std::map<std::string, IdGroup>;
using IdGroupMapByTypeId = std::map<uint32_t, IdGroup>;
using IdGroupMapByOp = std::map<SpvOp, IdGroup>;
using IdGroupMapByStorageClass = std::map<SpvStorageClass, IdGroup>;
// A set of potential id mappings that haven't been resolved yet. Any id in src
// may map in any id in dst. Note that ids are added in the same order as they
// appear in src and dst to facilitate matching dependent instructions. For
// example, this guarantees that when matching OpTypeVector, the basic type of
// the vector is already (potentially) matched.
struct PotentialIdMap {
std::vector<uint32_t> src_ids;
std::vector<uint32_t> dst_ids;
};
void CompactIds(std::vector<uint32_t>& ids) {
size_t write_index = 0;
for (size_t i = 0; i < ids.size(); ++i) {
if (ids[i] != 0) {
ids[write_index++] = ids[i];
}
}
ids.resize(write_index);
}
// A mapping between src and dst ids.
class IdMap {
public:
IdMap(size_t id_bound) { id_map_.resize(id_bound, 0); }
void MapIds(uint32_t from, uint32_t to) {
assert(from != 0);
assert(to != 0);
assert(from < id_map_.size());
assert(id_map_[from] == 0);
id_map_[from] = to;
}
uint32_t MappedId(uint32_t from) const {
assert(from != 0);
return from < id_map_.size() ? id_map_[from] : 0;
}
const opt::Instruction* MappedInst(const opt::Instruction* from_inst) const {
assert(from_inst != nullptr);
assert(!from_inst->HasResultId());
auto mapped = inst_map_.find(from_inst);
if (mapped == inst_map_.end()) {
return nullptr;
}
return mapped->second;
}
bool IsMapped(uint32_t from) const {
assert(from != 0);
return from < id_map_.size() && id_map_[from] != 0;
}
// Map any ids in src and dst that have not been mapped to new ids in dst and
// src respectively.
void MapUnmatchedIds(IdMap& other_way);
// Some instructions don't have result ids. Those are mapped by pointer.
void MapInsts(const opt::Instruction* from_inst,
const opt::Instruction* to_inst) {
assert(from_inst != nullptr);
assert(to_inst != nullptr);
assert(inst_map_.find(from_inst) == inst_map_.end());
inst_map_[from_inst] = to_inst;
}
uint32_t IdBound() const { return static_cast<uint32_t>(id_map_.size()); }
private:
// Given an id, returns the corresponding id in the other module, or 0 if not
// matched yet.
std::vector<uint32_t> id_map_;
// Same for instructions that don't have an id.
InstructionToInstructionMap inst_map_;
};
// Two way mapping of ids.
class SrcDstIdMap {
public:
SrcDstIdMap(size_t src_id_bound, size_t dst_id_bound)
: src_to_dst_(src_id_bound), dst_to_src_(dst_id_bound) {}
void MapIds(uint32_t src, uint32_t dst) {
src_to_dst_.MapIds(src, dst);
dst_to_src_.MapIds(dst, src);
}
uint32_t MappedDstId(uint32_t src) {
uint32_t dst = src_to_dst_.MappedId(src);
assert(dst == 0 || dst_to_src_.MappedId(dst) == src);
return dst;
}
uint32_t MappedSrcId(uint32_t dst) {
uint32_t src = dst_to_src_.MappedId(dst);
assert(src == 0 || src_to_dst_.MappedId(src) == dst);
return src;
}
bool IsSrcMapped(uint32_t src) { return src_to_dst_.IsMapped(src); }
bool IsDstMapped(uint32_t dst) { return dst_to_src_.IsMapped(dst); }
// Map any ids in src and dst that have not been mapped to new ids in dst and
// src respectively.
void MapUnmatchedIds();
// Some instructions don't have result ids. Those are mapped by pointer.
void MapInsts(const opt::Instruction* src_inst,
const opt::Instruction* dst_inst) {
assert(src_inst->HasResultId() == dst_inst->HasResultId());
if (src_inst->HasResultId()) {
MapIds(src_inst->result_id(), dst_inst->result_id());
} else {
src_to_dst_.MapInsts(src_inst, dst_inst);
dst_to_src_.MapInsts(dst_inst, src_inst);
}
}
const IdMap& SrcToDstMap() const { return src_to_dst_; }
const IdMap& DstToSrcMap() const { return dst_to_src_; }
private:
IdMap src_to_dst_;
IdMap dst_to_src_;
};
struct IdInstructions {
IdInstructions(const opt::Module* module)
: inst_map_(module->IdBound(), nullptr),
name_map_(module->IdBound()),
decoration_map_(module->IdBound()),
forward_pointer_map_(module->IdBound()) {
// Map ids from all sections to instructions that define them.
MapIdsToInstruction(module->ext_inst_imports());
MapIdsToInstruction(module->types_values());
for (const opt::Function& function : *module) {
function.ForEachInst(
[this](const opt::Instruction* inst) {
if (inst->HasResultId()) {
MapIdToInstruction(inst->result_id(), inst);
}
},
true, true);
}
// Gather decorations applied to ids that could be useful in matching them
// between src and dst modules.
MapIdsToInfos(module->debugs2());
MapIdsToInfos(module->annotations());
MapIdsToInfos(module->types_values());
}
void MapIdToInstruction(uint32_t id, const opt::Instruction* inst);
void MapIdsToInstruction(
opt::IteratorRange<opt::Module::const_inst_iterator> section);
void MapIdsToInfos(
opt::IteratorRange<opt::Module::const_inst_iterator> section);
IdToInstructionMap inst_map_;
IdToInfoMap name_map_;
IdToInfoMap decoration_map_;
IdToInstructionMap forward_pointer_map_;
};
class Differ {
public:
Differ(opt::IRContext* src, opt::IRContext* dst, std::ostream& out,
Options options)
: src_context_(src),
dst_context_(dst),
src_(src->module()),
dst_(dst->module()),
options_(options),
out_(out),
src_id_to_(src_),
dst_id_to_(dst_),
id_map_(src_->IdBound(), dst_->IdBound()) {
// Cache function bodies in canonicalization order.
GetFunctionBodies(src_context_, &src_funcs_, &src_func_insts_);
GetFunctionBodies(dst_context_, &dst_funcs_, &dst_func_insts_);
}
// Match ids or instructions of different sections.
void MatchCapabilities();
void MatchExtensions();
void MatchExtInstImportIds();
void MatchMemoryModel();
void MatchEntryPointIds();
void MatchExecutionModes();
void MatchTypeForwardPointers();
void MatchTypeIds();
void MatchConstants();
void MatchVariableIds();
void MatchFunctions();
// Debug info and annotations are matched only after ids are matched.
void MatchDebugs1();
void MatchDebugs2();
void MatchDebugs3();
void MatchExtInstDebugInfo();
void MatchAnnotations();
// Output the diff.
spv_result_t Output();
void DumpIdMap() {
if (!options_.dump_id_map) {
return;
}
out_ << " Src -> Dst\n";
for (uint32_t src_id = 1; src_id < src_->IdBound(); ++src_id) {
uint32_t dst_id = id_map_.MappedDstId(src_id);
if (src_id_to_.inst_map_[src_id] != nullptr && dst_id != 0)
out_ << std::setw(4) << src_id << " -> " << std::setw(4) << dst_id
<< " [" << spvOpcodeString(src_id_to_.inst_map_[src_id]->opcode())
<< "]\n";
}
}
private:
// Helper functions that match ids between src and dst
void PoolPotentialIds(
opt::IteratorRange<opt::Module::const_inst_iterator> section,
std::vector<uint32_t>& ids, bool is_src,
std::function<bool(const opt::Instruction&)> filter,
std::function<uint32_t(const opt::Instruction&)> get_id);
void MatchIds(
PotentialIdMap& potential,
std::function<bool(const opt::Instruction*, const opt::Instruction*)>
match);
// Helper functions that match id-less instructions between src and dst.
void MatchPreambleInstructions(
opt::IteratorRange<opt::Module::const_inst_iterator> src_insts,
opt::IteratorRange<opt::Module::const_inst_iterator> dst_insts);
InstructionList SortPreambleInstructions(
const opt::Module* module,
opt::IteratorRange<opt::Module::const_inst_iterator> insts);
int ComparePreambleInstructions(const opt::Instruction* a,
const opt::Instruction* b,
const opt::Module* src_inst_module,
const opt::Module* dst_inst_module);
// Helper functions that match debug and annotation instructions of already
// matched ids.
void MatchDebugAndAnnotationInstructions(
opt::IteratorRange<opt::Module::const_inst_iterator> src_insts,
opt::IteratorRange<opt::Module::const_inst_iterator> dst_insts);
// Get various properties from an id. These Helper functions are passed to
// `GroupIds` and `GroupIdsAndMatch` below (as the `get_group` argument).
uint32_t GroupIdsHelperGetTypeId(const IdInstructions& id_to, uint32_t id);
SpvStorageClass GroupIdsHelperGetTypePointerStorageClass(
const IdInstructions& id_to, uint32_t id);
SpvOp GroupIdsHelperGetTypePointerTypeOp(const IdInstructions& id_to,
uint32_t id);
// Given a list of ids, groups them based on some value. The `get_group`
// function extracts a piece of information corresponding to each id, and the
// ids are bucketed based on that (and output in `groups`). This is useful to
// attempt to match ids between src and dst only when said property is
// identical.
template <typename T>
void GroupIds(const IdGroup& ids, bool is_src, std::map<T, IdGroup>* groups,
T (Differ::*get_group)(const IdInstructions&, uint32_t));
// Calls GroupIds to bucket ids in src and dst based on a property returned by
// `get_group`. This function then calls `match_group` for each bucket (i.e.
// "group") with identical values for said property.
//
// For example, say src and dst ids have the following properties
// correspondingly:
//
// - src ids' properties: {id0: A, id1: A, id2: B, id3: C, id4: B}
// - dst ids' properties: {id0': B, id1': C, id2': B, id3': D, id4': B}
//
// Then `match_group` is called 2 times:
//
// - Once with: ([id2, id4], [id0', id2', id4']) corresponding to B
// - Once with: ([id3], [id2']) corresponding to C
//
// Ids corresponding to A and D cannot match based on this property.
template <typename T>
void GroupIdsAndMatch(
const IdGroup& src_ids, const IdGroup& dst_ids, T invalid_group_key,
T (Differ::*get_group)(const IdInstructions&, uint32_t),
std::function<void(const IdGroup& src_group, const IdGroup& dst_group)>
match_group);
// Helper functions that determine if two instructions match
bool DoIdsMatch(uint32_t src_id, uint32_t dst_id);
bool DoesOperandMatch(const opt::Operand& src_operand,
const opt::Operand& dst_operand);
bool DoOperandsMatch(const opt::Instruction* src_inst,
const opt::Instruction* dst_inst,
uint32_t in_operand_index_start,
uint32_t in_operand_count);
bool DoInstructionsMatch(const opt::Instruction* src_inst,
const opt::Instruction* dst_inst);
bool DoIdsMatchFuzzy(uint32_t src_id, uint32_t dst_id);
bool DoesOperandMatchFuzzy(const opt::Operand& src_operand,
const opt::Operand& dst_operand);
bool DoInstructionsMatchFuzzy(const opt::Instruction* src_inst,
const opt::Instruction* dst_inst);
bool AreIdenticalUintConstants(uint32_t src_id, uint32_t dst_id);
bool DoDebugAndAnnotationInstructionsMatch(const opt::Instruction* src_inst,
const opt::Instruction* dst_inst);
bool AreVariablesMatchable(uint32_t src_id, uint32_t dst_id,
uint32_t flexibility);
bool MatchOpTypeStruct(const opt::Instruction* src_inst,
const opt::Instruction* dst_inst,
uint32_t flexibility);
bool MatchOpConstant(const opt::Instruction* src_inst,
const opt::Instruction* dst_inst, uint32_t flexibility);
bool MatchOpSpecConstant(const opt::Instruction* src_inst,
const opt::Instruction* dst_inst);
bool MatchOpVariable(const opt::Instruction* src_inst,
const opt::Instruction* dst_inst, uint32_t flexibility);
bool MatchPerVertexType(uint32_t src_type_id, uint32_t dst_type_id);
bool MatchPerVertexVariable(const opt::Instruction* src_inst,
const opt::Instruction* dst_inst);
// Helper functions for matching OpTypeForwardPointer
void MatchTypeForwardPointersByName(const IdGroup& src, const IdGroup& dst);
void MatchTypeForwardPointersByTypeOp(const IdGroup& src, const IdGroup& dst);
// Helper functions for function matching.
using FunctionMap = std::map<uint32_t, const opt::Function*>;
InstructionList GetFunctionBody(opt::IRContext* context,
opt::Function& function);
InstructionList GetFunctionHeader(const opt::Function& function);
void GetFunctionBodies(opt::IRContext* context, FunctionMap* functions,
FunctionInstMap* function_insts);
void GetFunctionHeaderInstructions(const opt::Module* module,
FunctionInstMap* function_insts);
void BestEffortMatchFunctions(const IdGroup& src_func_ids,
const IdGroup& dst_func_ids,
const FunctionInstMap& src_func_insts,
const FunctionInstMap& dst_func_insts);
// Calculates the diff of two function bodies. Note that the matched
// instructions themselves may not be identical; output of exact matches
// should produce the exact instruction while inexact matches should produce a
// diff as well.
//
// Returns the similarity of the two bodies = 2*N_match / (N_src + N_dst)
void MatchFunctionParamIds(const opt::Function* src_func,
const opt::Function* dst_func);
float MatchFunctionBodies(const InstructionList& src_body,
const InstructionList& dst_body,
DiffMatch* src_match_result,
DiffMatch* dst_match_result);
void MatchIdsInFunctionBodies(const InstructionList& src_body,
const InstructionList& dst_body,
const DiffMatch& src_match_result,
const DiffMatch& dst_match_result,
uint32_t flexibility);
void MatchVariablesUsedByMatchedInstructions(const opt::Instruction* src_inst,
const opt::Instruction* dst_inst,
uint32_t flexibility);
// Helper functions to retrieve information pertaining to an id
const opt::Instruction* GetInst(const IdInstructions& id_to, uint32_t id);
uint32_t GetConstantUint(const IdInstructions& id_to, uint32_t constant_id);
SpvExecutionModel GetExecutionModel(const opt::Module* module,
uint32_t entry_point_id);
bool HasName(const IdInstructions& id_to, uint32_t id);
// Get the OpName associated with an id
std::string GetName(const IdInstructions& id_to, uint32_t id, bool* has_name);
// Get the OpName associated with an id, with argument types stripped for
// functions. Some tools don't encode function argument types in the OpName
// string, and this improves diff between SPIR-V from those tools and others.
std::string GetSanitizedName(const IdInstructions& id_to, uint32_t id);
uint32_t GetVarTypeId(const IdInstructions& id_to, uint32_t var_id,
SpvStorageClass* storage_class);
bool GetDecorationValue(const IdInstructions& id_to, uint32_t id,
SpvDecoration decoration, uint32_t* decoration_value);
const opt::Instruction* GetForwardPointerInst(const IdInstructions& id_to,
uint32_t id);
bool IsIntType(const IdInstructions& id_to, uint32_t type_id);
bool IsFloatType(const IdInstructions& id_to, uint32_t type_id);
bool IsConstantUint(const IdInstructions& id_to, uint32_t id);
bool IsVariable(const IdInstructions& id_to, uint32_t pointer_id);
bool IsOp(const IdInstructions& id_to, uint32_t id, SpvOp opcode);
bool IsPerVertexType(const IdInstructions& id_to, uint32_t type_id);
bool IsPerVertexVariable(const IdInstructions& id_to, uint32_t type_id);
SpvStorageClass GetPerVertexStorageClass(const opt::Module* module,
uint32_t type_id);
spv_ext_inst_type_t GetExtInstType(const IdInstructions& id_to,
uint32_t set_id);
spv_number_kind_t GetNumberKind(const IdInstructions& id_to,
const opt::Instruction& inst,
uint32_t operand_index,
uint32_t* number_bit_width);
spv_number_kind_t GetTypeNumberKind(const IdInstructions& id_to, uint32_t id,
uint32_t* number_bit_width);
// Helper functions to output a diff line
const opt::Instruction* MappedDstInst(const opt::Instruction* src_inst);
const opt::Instruction* MappedSrcInst(const opt::Instruction* dst_inst);
const opt::Instruction* MappedInstImpl(const opt::Instruction* inst,
const IdMap& to_other,
const IdInstructions& other_id_to);
void OutputLine(std::function<bool()> are_lines_identical,
std::function<void()> output_src_line,
std::function<void()> output_dst_line);
template <typename InstList>
void OutputSection(
const InstList& src_insts, const InstList& dst_insts,
std::function<void(const opt::Instruction&, const IdInstructions&,
const opt::Instruction&)>
write_inst);
void ToParsedInstruction(const opt::Instruction& inst,
const IdInstructions& id_to,
const opt::Instruction& original_inst,
spv_parsed_instruction_t* parsed_inst,
std::vector<spv_parsed_operand_t>& parsed_operands,
std::vector<uint32_t>& inst_binary);
opt::Instruction ToMappedSrcIds(const opt::Instruction& dst_inst);
void OutputRed() {
if (options_.color_output) out_ << spvtools::clr::red{true};
}
void OutputGreen() {
if (options_.color_output) out_ << spvtools::clr::green{true};
}
void OutputResetColor() {
if (options_.color_output) out_ << spvtools::clr::reset{true};
}
opt::IRContext* src_context_;
opt::IRContext* dst_context_;
const opt::Module* src_;
const opt::Module* dst_;
Options options_;
std::ostream& out_;
// Helpers to look up instructions based on id.
IdInstructions src_id_to_;
IdInstructions dst_id_to_;
// The ids that have been matched between src and dst so far.
SrcDstIdMap id_map_;
// List of instructions in function bodies after canonicalization. Cached
// here to avoid duplicate work. More importantly, some maps use
// opt::Instruction pointers so they need to be unique.
FunctionInstMap src_func_insts_;
FunctionInstMap dst_func_insts_;
FunctionMap src_funcs_;
FunctionMap dst_funcs_;
};
void IdMap::MapUnmatchedIds(IdMap& other_way) {
const uint32_t src_id_bound = static_cast<uint32_t>(id_map_.size());
const uint32_t dst_id_bound = static_cast<uint32_t>(other_way.id_map_.size());
uint32_t next_src_id = src_id_bound;
uint32_t next_dst_id = dst_id_bound;
for (uint32_t src_id = 1; src_id < src_id_bound; ++src_id) {
if (!IsMapped(src_id)) {
MapIds(src_id, next_dst_id);
other_way.id_map_.push_back(0);
other_way.MapIds(next_dst_id++, src_id);
}
}
for (uint32_t dst_id = 1; dst_id < dst_id_bound; ++dst_id) {
if (!other_way.IsMapped(dst_id)) {
id_map_.push_back(0);
MapIds(next_src_id, dst_id);
other_way.MapIds(dst_id, next_src_id++);
}
}
}
void SrcDstIdMap::MapUnmatchedIds() {
src_to_dst_.MapUnmatchedIds(dst_to_src_);
}
void IdInstructions::MapIdToInstruction(uint32_t id,
const opt::Instruction* inst) {
assert(id != 0);
assert(id < inst_map_.size());
assert(inst_map_[id] == nullptr);
inst_map_[id] = inst;
}
void IdInstructions::MapIdsToInstruction(
opt::IteratorRange<opt::Module::const_inst_iterator> section) {
for (const opt::Instruction& inst : section) {
uint32_t result_id = inst.result_id();
if (result_id == 0) {
continue;
}
MapIdToInstruction(result_id, &inst);
}
}
void IdInstructions::MapIdsToInfos(
opt::IteratorRange<opt::Module::const_inst_iterator> section) {
for (const opt::Instruction& inst : section) {
IdToInfoMap* info_map = nullptr;
uint32_t id_operand = 0;
switch (inst.opcode()) {
case SpvOpName:
info_map = &name_map_;
break;
case SpvOpMemberName:
info_map = &name_map_;
break;
case SpvOpDecorate:
info_map = &decoration_map_;
break;
case SpvOpMemberDecorate:
info_map = &decoration_map_;
break;
case SpvOpTypeForwardPointer: {
uint32_t id = inst.GetSingleWordOperand(0);
assert(id != 0);
assert(id < forward_pointer_map_.size());
forward_pointer_map_[id] = &inst;
continue;
}
default:
// Currently unsupported instruction, don't attempt to use it for
// matching.
break;
}
if (info_map == nullptr) {
continue;
}
uint32_t id = inst.GetOperand(id_operand).AsId();
assert(id != 0);
assert(id < info_map->size());
assert(std::find((*info_map)[id].begin(), (*info_map)[id].end(), &inst) ==
(*info_map)[id].end());
(*info_map)[id].push_back(&inst);
}
}
void Differ::PoolPotentialIds(
opt::IteratorRange<opt::Module::const_inst_iterator> section,
std::vector<uint32_t>& ids, bool is_src,
std::function<bool(const opt::Instruction&)> filter,
std::function<uint32_t(const opt::Instruction&)> get_id) {
for (const opt::Instruction& inst : section) {
if (!filter(inst)) {
continue;
}
uint32_t result_id = get_id(inst);
assert(result_id != 0);
assert(std::find(ids.begin(), ids.end(), result_id) == ids.end());
// Don't include ids that are already matched, for example through
// OpTypeForwardPointer.
const bool is_matched = is_src ? id_map_.IsSrcMapped(result_id)
: id_map_.IsDstMapped(result_id);
if (is_matched) {
continue;
}
ids.push_back(result_id);
}
}
void Differ::MatchIds(
PotentialIdMap& potential,
std::function<bool(const opt::Instruction*, const opt::Instruction*)>
match) {
for (size_t src_index = 0; src_index < potential.src_ids.size();
++src_index) {
for (size_t dst_index = 0; dst_index < potential.dst_ids.size();
++dst_index) {
const uint32_t src_id = potential.src_ids[src_index];
const uint32_t dst_id = potential.dst_ids[dst_index];
if (dst_id == 0) {
// Already matched.
continue;
}
const opt::Instruction* src_inst = src_id_to_.inst_map_[src_id];
const opt::Instruction* dst_inst = dst_id_to_.inst_map_[dst_id];
if (match(src_inst, dst_inst)) {
id_map_.MapIds(src_id, dst_id);
// Remove the ids from the potential list.
potential.src_ids[src_index] = 0;
potential.dst_ids[dst_index] = 0;
// Find a match for the next src id.
break;
}
}
}
// Remove matched ids to make the next iteration faster.
CompactIds(potential.src_ids);
CompactIds(potential.dst_ids);
}
void Differ::MatchPreambleInstructions(
opt::IteratorRange<opt::Module::const_inst_iterator> src_insts,
opt::IteratorRange<opt::Module::const_inst_iterator> dst_insts) {
// First, pool all instructions from each section and sort them.
InstructionList sorted_src_insts = SortPreambleInstructions(src_, src_insts);
InstructionList sorted_dst_insts = SortPreambleInstructions(dst_, dst_insts);
// Then walk and match them.
size_t src_cur = 0;
size_t dst_cur = 0;
while (src_cur < sorted_src_insts.size() &&
dst_cur < sorted_dst_insts.size()) {
const opt::Instruction* src_inst = sorted_src_insts[src_cur];
const opt::Instruction* dst_inst = sorted_dst_insts[dst_cur];
int compare = ComparePreambleInstructions(src_inst, dst_inst, src_, dst_);
if (compare == 0) {
id_map_.MapInsts(src_inst, dst_inst);
}
if (compare <= 0) {
++src_cur;
}
if (compare >= 0) {
++dst_cur;
}
}
}
InstructionList Differ::SortPreambleInstructions(
const opt::Module* module,
opt::IteratorRange<opt::Module::const_inst_iterator> insts) {
InstructionList sorted;
for (const opt::Instruction& inst : insts) {
sorted.push_back(&inst);
}
std::sort(
sorted.begin(), sorted.end(),
[this, module](const opt::Instruction* a, const opt::Instruction* b) {
return ComparePreambleInstructions(a, b, module, module) < 0;
});
return sorted;
}
int Differ::ComparePreambleInstructions(const opt::Instruction* a,
const opt::Instruction* b,
const opt::Module* src_inst_module,
const opt::Module* dst_inst_module) {
assert(a->opcode() == b->opcode());
assert(!a->HasResultId());
assert(!a->HasResultType());
const uint32_t a_operand_count = a->NumOperands();
const uint32_t b_operand_count = b->NumOperands();
if (a_operand_count < b_operand_count) {
return -1;
}
if (a_operand_count > b_operand_count) {
return 1;
}
// Instead of comparing OpExecutionMode entry point ids as ids, compare them
// through their corresponding execution model. This simplifies traversing
// the sorted list of instructions between src and dst modules.
if (a->opcode() == SpvOpExecutionMode) {
const SpvExecutionModel src_model =
GetExecutionModel(src_inst_module, a->GetSingleWordOperand(0));
const SpvExecutionModel dst_model =
GetExecutionModel(dst_inst_module, b->GetSingleWordOperand(0));
if (src_model < dst_model) {
return -1;
}
if (src_model > dst_model) {
return 1;
}
}
// Match every operand of the instruction.
for (uint32_t operand_index = 0; operand_index < a_operand_count;
++operand_index) {
const opt::Operand& a_operand = a->GetOperand(operand_index);
const opt::Operand& b_operand = b->GetOperand(operand_index);
if (a_operand.type < b_operand.type) {
return -1;
}
if (a_operand.type > b_operand.type) {
return 1;
}
switch (a_operand.type) {
case SPV_OPERAND_TYPE_ID:
// Don't compare ids, there can't be multiple instances of the
// OpExecutionMode with different ids of the same execution model.
break;
case SPV_OPERAND_TYPE_TYPE_ID:
case SPV_OPERAND_TYPE_MEMORY_SEMANTICS_ID:
case SPV_OPERAND_TYPE_SCOPE_ID:
assert(false && "Unreachable");
break;
case SPV_OPERAND_TYPE_LITERAL_STRING: {
int str_compare =
strcmp(a_operand.AsString().c_str(), b_operand.AsString().c_str());
if (str_compare != 0) {
return str_compare;
}
break;
}
default:
// Expect literal values to match.
assert(a_operand.words.size() == 1);
assert(b_operand.words.size() == 1);
if (a_operand.words[0] < b_operand.words[0]) {
return -1;
}
if (a_operand.words[0] > b_operand.words[0]) {
return 1;
}
break;
}
}
return 0;
}
void Differ::MatchDebugAndAnnotationInstructions(
opt::IteratorRange<opt::Module::const_inst_iterator> src_insts,
opt::IteratorRange<opt::Module::const_inst_iterator> dst_insts) {
for (const opt::Instruction& src_inst : src_insts) {
for (const opt::Instruction& dst_inst : dst_insts) {
if (MappedSrcInst(&dst_inst) != nullptr) {
continue;
}
// Map instructions as soon as they match. Debug and annotation
// instructions are matched such that there can't be multiple matches.
if (DoDebugAndAnnotationInstructionsMatch(&src_inst, &dst_inst)) {
id_map_.MapInsts(&src_inst, &dst_inst);
break;
}
}
}
}
uint32_t Differ::GroupIdsHelperGetTypeId(const IdInstructions& id_to,
uint32_t id) {
return GetInst(id_to, id)->type_id();
}
SpvStorageClass Differ::GroupIdsHelperGetTypePointerStorageClass(
const IdInstructions& id_to, uint32_t id) {
const opt::Instruction* inst = GetInst(id_to, id);
assert(inst && inst->opcode() == SpvOpTypePointer);
return SpvStorageClass(inst->GetSingleWordInOperand(0));
}
SpvOp Differ::GroupIdsHelperGetTypePointerTypeOp(const IdInstructions& id_to,
uint32_t id) {
const opt::Instruction* inst = GetInst(id_to, id);
assert(inst && inst->opcode() == SpvOpTypePointer);
const uint32_t type_id = inst->GetSingleWordInOperand(1);
const opt::Instruction* type_inst = GetInst(id_to, type_id);
assert(type_inst);
return type_inst->opcode();
}
template <typename T>
void Differ::GroupIds(const IdGroup& ids, bool is_src,
std::map<T, IdGroup>* groups,
T (Differ::*get_group)(const IdInstructions&, uint32_t)) {
assert(groups->empty());
const IdInstructions& id_to = is_src ? src_id_to_ : dst_id_to_;
for (const uint32_t id : ids) {
// Don't include ids that are already matched, for example through
// OpEntryPoint.
const bool is_matched =
is_src ? id_map_.IsSrcMapped(id) : id_map_.IsDstMapped(id);
if (is_matched) {
continue;
}
T group = (this->*get_group)(id_to, id);
(*groups)[group].push_back(id);
}
}
template <typename T>
void Differ::GroupIdsAndMatch(
const IdGroup& src_ids, const IdGroup& dst_ids, T invalid_group_key,
T (Differ::*get_group)(const IdInstructions&, uint32_t),
std::function<void(const IdGroup& src_group, const IdGroup& dst_group)>
match_group) {
// Group the ids based on a key (get_group)
std::map<T, IdGroup> src_groups;
std::map<T, IdGroup> dst_groups;
GroupIds<T>(src_ids, true, &src_groups, get_group);
GroupIds<T>(dst_ids, false, &dst_groups, get_group);
// Iterate over the groups, and match those with identical keys
for (const auto& iter : src_groups) {
const T& key = iter.first;
const IdGroup& src_group = iter.second;
if (key == invalid_group_key) {
continue;
}
const IdGroup& dst_group = dst_groups[key];
// Let the caller match the groups as appropriate.
match_group(src_group, dst_group);
}
}
bool Differ::DoIdsMatch(uint32_t src_id, uint32_t dst_id) {
assert(dst_id != 0);
return id_map_.MappedDstId(src_id) == dst_id;
}
bool Differ::DoesOperandMatch(const opt::Operand& src_operand,
const opt::Operand& dst_operand) {
assert(src_operand.type == dst_operand.type);
switch (src_operand.type) {
case SPV_OPERAND_TYPE_ID:
case SPV_OPERAND_TYPE_TYPE_ID:
case SPV_OPERAND_TYPE_RESULT_ID:
case SPV_OPERAND_TYPE_MEMORY_SEMANTICS_ID:
case SPV_OPERAND_TYPE_SCOPE_ID:
// Match ids only if they are already matched in the id map.
return DoIdsMatch(src_operand.AsId(), dst_operand.AsId());
case SPV_OPERAND_TYPE_LITERAL_STRING:
return src_operand.AsString() == dst_operand.AsString();
default:
// Otherwise expect them to match exactly.
assert(src_operand.type != SPV_OPERAND_TYPE_LITERAL_STRING);
if (src_operand.words.size() != dst_operand.words.size()) {
return false;
}
for (size_t i = 0; i < src_operand.words.size(); ++i) {
if (src_operand.words[i] != dst_operand.words[i]) {
return false;
}
}
return true;
}
}
bool Differ::DoOperandsMatch(const opt::Instruction* src_inst,
const opt::Instruction* dst_inst,
uint32_t in_operand_index_start,
uint32_t in_operand_count) {
// Caller should have returned early for instructions with different opcode.
assert(src_inst->opcode() == dst_inst->opcode());
bool match = true;
for (uint32_t i = 0; i < in_operand_count; ++i) {
const uint32_t in_operand_index = in_operand_index_start + i;
const opt::Operand& src_operand = src_inst->GetInOperand(in_operand_index);
const opt::Operand& dst_operand = dst_inst->GetInOperand(in_operand_index);
match = match && DoesOperandMatch(src_operand, dst_operand);
}
return match;
}
bool Differ::DoInstructionsMatch(const opt::Instruction* src_inst,
const opt::Instruction* dst_inst) {
// Check whether the two instructions are identical, that is the instructions
// themselves are matched, every id is matched, and every other value is
// identical.
if (MappedDstInst(src_inst) != dst_inst) {
return false;
}
assert(src_inst->opcode() == dst_inst->opcode());
if (src_inst->NumOperands() != dst_inst->NumOperands()) {
return false;
}
for (uint32_t operand_index = 0; operand_index < src_inst->NumOperands();
++operand_index) {
const opt::Operand& src_operand = src_inst->GetOperand(operand_index);
const opt::Operand& dst_operand = dst_inst->GetOperand(operand_index);
if (!DoesOperandMatch(src_operand, dst_operand)) {
return false;
}
}
return true;
}
bool Differ::DoIdsMatchFuzzy(uint32_t src_id, uint32_t dst_id) {
assert(dst_id != 0);
const uint32_t mapped_dst_id = id_map_.MappedDstId(src_id);
// Consider unmatched ids as a match. In function bodies, no result id is
// matched yet and thus they are excluded from instruction matching when used
// as parameters in subsequent instructions.
if (mapped_dst_id == 0 || mapped_dst_id == dst_id) {
return true;
}
// Int and Uint constants are interchangeable, match them in that case.
if (AreIdenticalUintConstants(src_id, dst_id)) {
return true;
}
return false;
}
bool Differ::DoesOperandMatchFuzzy(const opt::Operand& src_operand,
const opt::Operand& dst_operand) {
if (src_operand.type != dst_operand.type) {
return false;
}
assert(src_operand.type != SPV_OPERAND_TYPE_RESULT_ID);
assert(dst_operand.type != SPV_OPERAND_TYPE_RESULT_ID);
switch (src_operand.type) {
case SPV_OPERAND_TYPE_ID:
case SPV_OPERAND_TYPE_TYPE_ID:
case SPV_OPERAND_TYPE_MEMORY_SEMANTICS_ID:
case SPV_OPERAND_TYPE_SCOPE_ID:
// Match id operands only if they are already matched in the id map.
return DoIdsMatchFuzzy(src_operand.AsId(), dst_operand.AsId());
default:
// Otherwise allow everything to match.
return true;
}
}
bool Differ::DoInstructionsMatchFuzzy(const opt::Instruction* src_inst,
const opt::Instruction* dst_inst) {
// Similar to DoOperandsMatch, but only checks that ids that have already been
// matched are identical. Ids that are unknown are allowed to match, as well
// as any non-id operand.
if (src_inst->opcode() != dst_inst->opcode()) {
return false;
}
// For external instructions, make sure the set and opcode of the external
// instruction matches too.
if (src_inst->opcode() == SpvOpExtInst) {
if (!DoOperandsMatch(src_inst, dst_inst, 0, 2)) {
return false;
}
}
assert(src_inst->HasResultType() == dst_inst->HasResultType());
if (src_inst->HasResultType() &&
!DoIdsMatchFuzzy(src_inst->type_id(), dst_inst->type_id())) {
return false;
}
// TODO: allow some instructions to match with different instruction lengths,
// for example OpImage* with additional operands.
if (src_inst->NumInOperandWords() != dst_inst->NumInOperandWords()) {
return false;
}
bool match = true;
for (uint32_t in_operand_index = 0;
in_operand_index < src_inst->NumInOperandWords(); ++in_operand_index) {
const opt::Operand& src_operand = src_inst->GetInOperand(in_operand_index);
const opt::Operand& dst_operand = dst_inst->GetInOperand(in_operand_index);
match = match && DoesOperandMatchFuzzy(src_operand, dst_operand);
}
return match;
}
bool Differ::AreIdenticalUintConstants(uint32_t src_id, uint32_t dst_id) {
return IsConstantUint(src_id_to_, src_id) &&
IsConstantUint(dst_id_to_, dst_id) &&
GetConstantUint(src_id_to_, src_id) ==
GetConstantUint(dst_id_to_, dst_id);
}
bool Differ::DoDebugAndAnnotationInstructionsMatch(
const opt::Instruction* src_inst, const opt::Instruction* dst_inst) {
if (src_inst->opcode() != dst_inst->opcode()) {
return false;
}
switch (src_inst->opcode()) {
case SpvOpString:
case SpvOpSourceExtension:
case SpvOpModuleProcessed:
return DoesOperandMatch(src_inst->GetOperand(0), dst_inst->GetOperand(0));
case SpvOpSource:
return DoOperandsMatch(src_inst, dst_inst, 0, 2);
case SpvOpSourceContinued:
return true;
case SpvOpName:
return DoOperandsMatch(src_inst, dst_inst, 0, 1);
case SpvOpMemberName:
return DoOperandsMatch(src_inst, dst_inst, 0, 2);
case SpvOpDecorate:
return DoOperandsMatch(src_inst, dst_inst, 0, 2);
case SpvOpMemberDecorate:
return DoOperandsMatch(src_inst, dst_inst, 0, 3);
case SpvOpExtInst:
case SpvOpDecorationGroup:
case SpvOpGroupDecorate:
case SpvOpGroupMemberDecorate:
return false;
default:
return false;
}
}
bool Differ::AreVariablesMatchable(uint32_t src_id, uint32_t dst_id,
uint32_t flexibility) {
// Variables must match by their built-in decorations.
uint32_t src_built_in_decoration = 0, dst_built_in_decoration = 0;
const bool src_is_built_in = GetDecorationValue(
src_id_to_, src_id, SpvDecorationBuiltIn, &src_built_in_decoration);
const bool dst_is_built_in = GetDecorationValue(
dst_id_to_, dst_id, SpvDecorationBuiltIn, &dst_built_in_decoration);
if (src_is_built_in != dst_is_built_in) {
return false;
}
if (src_is_built_in && src_built_in_decoration != dst_built_in_decoration) {
return false;
}
// Check their types and storage classes.
SpvStorageClass src_storage_class, dst_storage_class;
const uint32_t src_type_id =
GetVarTypeId(src_id_to_, src_id, &src_storage_class);
const uint32_t dst_type_id =
GetVarTypeId(dst_id_to_, dst_id, &dst_storage_class);
if (!DoIdsMatch(src_type_id, dst_type_id)) {
return false;
}
switch (flexibility) {
case 0:
if (src_storage_class != dst_storage_class) {
return false;
}
break;
case 1:
if (src_storage_class != dst_storage_class) {
// Allow one of the two to be Private while the other is Input or
// Output, this allows matching in/out variables that have been turned
// global as part of linking two stages (as done in ANGLE).
const bool src_is_io = src_storage_class == SpvStorageClassInput ||
src_storage_class == SpvStorageClassOutput;
const bool dst_is_io = dst_storage_class == SpvStorageClassInput ||
dst_storage_class == SpvStorageClassOutput;
const bool src_is_private = src_storage_class == SpvStorageClassPrivate;
const bool dst_is_private = dst_storage_class == SpvStorageClassPrivate;
if (!((src_is_io && dst_is_private) || (src_is_private && dst_is_io))) {
return false;
}
}
break;
default:
assert(false && "Unreachable");
return false;
}
// TODO: Is there any other way to check compatiblity of the variables? It's
// easy to tell when the variables definitely don't match, but there's little
// information that can be used for a definite match.
return true;
}
bool Differ::MatchOpTypeStruct(const opt::Instruction* src_inst,
const opt::Instruction* dst_inst,
uint32_t flexibility) {
const uint32_t src_type_id = src_inst->result_id();
const uint32_t dst_type_id = dst_inst->result_id();
bool src_has_name = false, dst_has_name = false;
std::string src_name = GetName(src_id_to_, src_type_id, &src_has_name);
std::string dst_name = GetName(dst_id_to_, dst_type_id, &dst_has_name);
// If debug info is present, always match the structs by name.
if (src_has_name && dst_has_name) {
if (src_name != dst_name) {
return false;
}
// For gl_PerVertex, find the type pointer of this type (array) and make
// sure the storage classes of src and dst match; geometry and tessellation
// shaders have two instances of gl_PerVertex.
if (src_name == "gl_PerVertex") {
return MatchPerVertexType(src_type_id, dst_type_id);
}
return true;
}
// If debug info is not present, match the structs by their type.
// For gl_PerVertex, find the type pointer of this type (array) and match by
// storage class. The gl_PerVertex struct is itself found by the BuiltIn
// decorations applied to its members.
const bool src_is_per_vertex = IsPerVertexType(src_id_to_, src_type_id);
const bool dst_is_per_vertex = IsPerVertexType(dst_id_to_, dst_type_id);
if (src_is_per_vertex != dst_is_per_vertex) {
return false;
}
if (src_is_per_vertex) {
return MatchPerVertexType(src_type_id, dst_type_id);
}
switch (flexibility) {
case 0:
if (src_inst->NumInOperandWords() != dst_inst->NumInOperandWords()) {
return false;
}
return DoOperandsMatch(src_inst, dst_inst, 0,
src_inst->NumInOperandWords());
case 1:
// TODO: match by taking a diff of the fields, and see if there's a >75%
// match. Need to then make sure OpMemberName, OpMemberDecorate,
// OpAccessChain etc are aware of the struct field matching.
return false;
default:
assert(false && "Unreachable");
return false;
}
}
bool Differ::MatchOpConstant(const opt::Instruction* src_inst,
const opt::Instruction* dst_inst,
uint32_t flexibility) {
// The constants' type must match. In flexibility == 1, match constants of
// int and uint, as they are generally interchangeable.
switch (flexibility) {
case 0:
if (!DoesOperandMatch(src_inst->GetOperand(0), dst_inst->GetOperand(0))) {
return false;
}
break;
case 1:
if (!IsIntType(src_id_to_, src_inst->type_id()) ||
!IsIntType(dst_id_to_, dst_inst->type_id())) {
return false;
}
break;
default:
assert(false && "Unreachable");
return false;
}
const opt::Operand& src_value_operand = src_inst->GetOperand(2);
const opt::Operand& dst_value_operand = dst_inst->GetOperand(2);
const uint64_t src_value = src_value_operand.AsLiteralUint64();
const uint64_t dst_value = dst_value_operand.AsLiteralUint64();
// If values are identical, it's a match.
if (src_value == dst_value) {
return true;
}
// Otherwise, only allow flexibility for float types.
if (IsFloatType(src_id_to_, src_inst->type_id()) && flexibility == 1) {
// Tolerance is:
//
// - For float: allow 4 bits of mantissa as error
// - For double: allow 6 bits of mantissa as error
//
// TODO: the above values are arbitrary and a placeholder; investigate the
// amount of error resulting from using `printf("%f", f)` and `printf("%lf",
// d)` and having glslang parse them.
const uint64_t tolerance = src_value_operand.words.size() == 1 ? 16 : 64;
return src_value - dst_value < tolerance ||
dst_value - src_value < tolerance;
}
return false;
}
bool Differ::MatchOpSpecConstant(const opt::Instruction* src_inst,
const opt::Instruction* dst_inst) {
const uint32_t src_id = src_inst->result_id();
const uint32_t dst_id = dst_inst->result_id();
bool src_has_name = false, dst_has_name = false;
std::string src_name = GetName(src_id_to_, src_id, &src_has_name);
std::string dst_name = GetName(dst_id_to_, dst_id, &dst_has_name);
// If debug info is present, always match the spec consts by name.
if (src_has_name && dst_has_name) {
return src_name == dst_name;
}
// Otherwise, match them by SpecId.
uint32_t src_spec_id, dst_spec_id;
if (GetDecorationValue(src_id_to_, src_id, SpvDecorationSpecId,
&src_spec_id) &&
GetDecorationValue(dst_id_to_, dst_id, SpvDecorationSpecId,
&dst_spec_id)) {
return src_spec_id == dst_spec_id;
}
// There is no SpecId decoration, while not practical, still valid.
// SpecConstantOp don't have SpecId and can be matched by operands
if (src_inst->opcode() == SpvOpSpecConstantOp) {
if (src_inst->NumInOperandWords() == dst_inst->NumInOperandWords()) {
return DoOperandsMatch(src_inst, dst_inst, 0,
src_inst->NumInOperandWords());
}
}
return false;
}
bool Differ::MatchOpVariable(const opt::Instruction* src_inst,
const opt::Instruction* dst_inst,
uint32_t flexibility) {
const uint32_t src_id = src_inst->result_id();
const uint32_t dst_id = dst_inst->result_id();
const bool src_is_pervertex = IsPerVertexVariable(src_id_to_, src_id);
const bool dst_is_pervertex = IsPerVertexVariable(dst_id_to_, dst_id);
// For gl_PerVertex, make sure the input and output instances are matched
// correctly.
if (src_is_pervertex != dst_is_pervertex) {
return false;
}
if (src_is_pervertex) {
return MatchPerVertexVariable(src_inst, dst_inst);
}
bool src_has_name = false, dst_has_name = false;
std::string src_name = GetName(src_id_to_, src_id, &src_has_name);
std::string dst_name = GetName(dst_id_to_, dst_id, &dst_has_name);
// If debug info is present, always match the variables by name.
if (src_has_name && dst_has_name) {
return src_name == dst_name;
}
// If debug info is not present, see if the variables can be matched by their
// built-in decorations.
uint32_t src_built_in_decoration;
const bool src_is_built_in = GetDecorationValue(
src_id_to_, src_id, SpvDecorationBuiltIn, &src_built_in_decoration);
if (src_is_built_in && AreVariablesMatchable(src_id, dst_id, flexibility)) {
return true;
}
SpvStorageClass src_storage_class, dst_storage_class;
GetVarTypeId(src_id_to_, src_id, &src_storage_class);
GetVarTypeId(dst_id_to_, dst_id, &dst_storage_class);
if (src_storage_class != dst_storage_class) {
return false;
}
// If variables are decorated with set/binding, match by the value of those
// decorations.
if (!options_.ignore_set_binding) {
uint32_t src_set = 0, dst_set = 0;
uint32_t src_binding = 0, dst_binding = 0;
const bool src_has_set = GetDecorationValue(
src_id_to_, src_id, SpvDecorationDescriptorSet, &src_set);
const bool dst_has_set = GetDecorationValue(
dst_id_to_, dst_id, SpvDecorationDescriptorSet, &dst_set);
const bool src_has_binding =
GetDecorationValue(src_id_to_, src_id, SpvDecorationBinding, &src_set);
const bool dst_has_binding =
GetDecorationValue(dst_id_to_, dst_id, SpvDecorationBinding, &dst_set);
if (src_has_set && dst_has_set && src_has_binding && dst_has_binding) {
return src_set == dst_set && src_binding == dst_binding;
}
}
// If variables are decorated with location, match by the value of that
// decoration.
if (!options_.ignore_location) {
uint32_t src_location, dst_location;
const bool src_has_location = GetDecorationValue(
src_id_to_, src_id, SpvDecorationLocation, &src_location);
const bool dst_has_location = GetDecorationValue(
dst_id_to_, dst_id, SpvDecorationLocation, &dst_location);
if (src_has_location && dst_has_location) {
return src_location == dst_location;
}
}
// Currently, there's no other way to match variables.
return false;
}
bool Differ::MatchPerVertexType(uint32_t src_type_id, uint32_t dst_type_id) {
// For gl_PerVertex, find the type pointer of this type (array) and make sure
// the storage classes of src and dst match; geometry and tessellation shaders
// have two instances of gl_PerVertex.
SpvStorageClass src_storage_class =
GetPerVertexStorageClass(src_, src_type_id);
SpvStorageClass dst_storage_class =
GetPerVertexStorageClass(dst_, dst_type_id);
assert(src_storage_class == SpvStorageClassInput ||
src_storage_class == SpvStorageClassOutput);
assert(dst_storage_class == SpvStorageClassInput ||
dst_storage_class == SpvStorageClassOutput);
return src_storage_class == dst_storage_class;
}
bool Differ::MatchPerVertexVariable(const opt::Instruction* src_inst,
const opt::Instruction* dst_inst) {
SpvStorageClass src_storage_class =
SpvStorageClass(src_inst->GetSingleWordInOperand(0));
SpvStorageClass dst_storage_class =
SpvStorageClass(dst_inst->GetSingleWordInOperand(0));
return src_storage_class == dst_storage_class;
}
void Differ::MatchTypeForwardPointersByName(const IdGroup& src,
const IdGroup& dst) {
// Given two sets of compatible groups of OpTypeForwardPointer instructions,
// attempts to match them by name.
// Group them by debug info and loop over them.
GroupIdsAndMatch<std::string>(
src, dst, "", &Differ::GetSanitizedName,
[this](const IdGroup& src_group, const IdGroup& dst_group) {
// Match only if there's a unique forward declaration with this debug
// name.
if (src_group.size() == 1 && dst_group.size() == 1) {
id_map_.MapIds(src_group[0], dst_group[0]);
}
});
}
void Differ::MatchTypeForwardPointersByTypeOp(const IdGroup& src,
const IdGroup& dst) {
// Given two sets of compatible groups of OpTypeForwardPointer instructions,
// attempts to match them by type op. Must be called after
// MatchTypeForwardPointersByName to match as many as possible by debug info.
// Remove ids that are matched with debug info in
// MatchTypeForwardPointersByName.
IdGroup src_unmatched_ids;
IdGroup dst_unmatched_ids;
std::copy_if(src.begin(), src.end(), std::back_inserter(src_unmatched_ids),
[this](uint32_t id) { return !id_map_.IsSrcMapped(id); });
std::copy_if(dst.begin(), dst.end(), std::back_inserter(dst_unmatched_ids),
[this](uint32_t id) { return !id_map_.IsDstMapped(id); });
// Match only if there's a unique forward declaration with this
// storage class and type opcode. If both have debug info, they
// must not have been matchable.
if (src_unmatched_ids.size() == 1 && dst_unmatched_ids.size() == 1) {
uint32_t src_id = src_unmatched_ids[0];
uint32_t dst_id = dst_unmatched_ids[0];
if (!HasName(src_id_to_, src_id) || !HasName(dst_id_to_, dst_id)) {
id_map_.MapIds(src_id, dst_id);
}
}
}
InstructionList Differ::GetFunctionBody(opt::IRContext* context,
opt::Function& function) {
// Canonicalize the blocks of the function to produce better diff, for example
// to not produce any diff if the src and dst have the same switch/case blocks
// but with the cases simply reordered.
std::list<opt::BasicBlock*> order;
context->cfg()->ComputeStructuredOrder(&function, &*function.begin(), &order);
// Go over the instructions of the function and add the instructions to a flat
// list to simplify future iterations.
InstructionList body;
for (opt::BasicBlock* block : order) {
block->ForEachInst(
[&body](const opt::Instruction* inst) { body.push_back(inst); }, true);
}
body.push_back(function.EndInst());
return body;
}
InstructionList Differ::GetFunctionHeader(const opt::Function& function) {
// Go over the instructions of the function and add the header instructions to
// a flat list to simplify diff generation.
InstructionList body;
function.WhileEachInst(
[&body](const opt::Instruction* inst) {
if (inst->opcode() == SpvOpLabel) {
return false;
}
body.push_back(inst);
return true;
},
true, true);
return body;
}
void Differ::GetFunctionBodies(opt::IRContext* context, FunctionMap* functions,
FunctionInstMap* function_insts) {
for (opt::Function& function : *context->module()) {
uint32_t id = function.result_id();
assert(functions->find(id) == functions->end());
assert(function_insts->find(id) == function_insts->end());
(*functions)[id] = &function;
InstructionList body = GetFunctionBody(context, function);
(*function_insts)[id] = std::move(body);
}
}
void Differ::GetFunctionHeaderInstructions(const opt::Module* module,
FunctionInstMap* function_insts) {
for (opt::Function& function : *module) {
InstructionList body = GetFunctionHeader(function);
(*function_insts)[function.result_id()] = std::move(body);
}
}
void Differ::BestEffortMatchFunctions(const IdGroup& src_func_ids,
const IdGroup& dst_func_ids,
const FunctionInstMap& src_func_insts,
const FunctionInstMap& dst_func_insts) {
struct MatchResult {
uint32_t src_id;
uint32_t dst_id;
DiffMatch src_match;
DiffMatch dst_match;
float match_rate;
bool operator<(const MatchResult& other) const {
return match_rate > other.match_rate;
}
};
std::vector<MatchResult> all_match_results;
for (const uint32_t src_func_id : src_func_ids) {
if (id_map_.IsSrcMapped(src_func_id)) {
continue;
}
const std::string src_name = GetSanitizedName(src_id_to_, src_func_id);
for (const uint32_t dst_func_id : dst_func_ids) {
if (id_map_.IsDstMapped(dst_func_id)) {
continue;
}
// Don't match functions that are named, but the names are different.
const std::string dst_name = GetSanitizedName(dst_id_to_, dst_func_id);
if (src_name != "" && dst_name != "" && src_name != dst_name) {
continue;
}
DiffMatch src_match_result, dst_match_result;
float match_rate = MatchFunctionBodies(
src_func_insts.at(src_func_id), dst_func_insts.at(dst_func_id),
&src_match_result, &dst_match_result);
// Only consider the functions a match if there's at least 60% match.
// This is an arbitrary limit that should be tuned.
constexpr float pass_match_rate = 0.6f;
if (match_rate >= pass_match_rate) {
all_match_results.emplace_back(
MatchResult{src_func_id, dst_func_id, std::move(src_match_result),
std::move(dst_match_result), match_rate});
}
}
}
std::sort(all_match_results.begin(), all_match_results.end());
for (const MatchResult& match_result : all_match_results) {
if (id_map_.IsSrcMapped(match_result.src_id) ||
id_map_.IsDstMapped(match_result.dst_id)) {
continue;
}
id_map_.MapIds(match_result.src_id, match_result.dst_id);
MatchIdsInFunctionBodies(src_func_insts.at(match_result.src_id),
dst_func_insts.at(match_result.dst_id),
match_result.src_match, match_result.dst_match, 0);
}
}
void Differ::MatchFunctionParamIds(const opt::Function* src_func,
const opt::Function* dst_func) {
IdGroup src_params;
IdGroup dst_params;
src_func->ForEachParam(
[&src_params](const opt::Instruction* param) {
src_params.push_back(param->result_id());
},
false);
dst_func->ForEachParam(
[&dst_params](const opt::Instruction* param) {
dst_params.push_back(param->result_id());
},
false);
GroupIdsAndMatch<std::string>(
src_params, dst_params, "", &Differ::GetSanitizedName,
[this](const IdGroup& src_group, const IdGroup& dst_group) {
// There shouldn't be two parameters with the same name, so the ids
// should match. There is nothing restricting the SPIR-V however to have
// two parameters with the same name, so be resilient against that.
if (src_group.size() == 1 && dst_group.size() == 1) {
id_map_.MapIds(src_group[0], dst_group[0]);
}
});
// Then match the parameters by their type. If there are multiple of them,
// match them by their order.
GroupIdsAndMatch<uint32_t>(
src_params, dst_params, 0, &Differ::GroupIdsHelperGetTypeId,
[this](const IdGroup& src_group_by_type_id,
const IdGroup& dst_group_by_type_id) {
const size_t shared_param_count =
std::min(src_group_by_type_id.size(), dst_group_by_type_id.size());
for (size_t param_index = 0; param_index < shared_param_count;
++param_index) {
id_map_.MapIds(src_group_by_type_id[0], dst_group_by_type_id[0]);
}
});
}
float Differ::MatchFunctionBodies(const InstructionList& src_body,
const InstructionList& dst_body,
DiffMatch* src_match_result,
DiffMatch* dst_match_result) {
LongestCommonSubsequence<std::vector<const opt::Instruction*>> lcs(src_body,
dst_body);
uint32_t best_match_length = lcs.Get<const opt::Instruction*>(
[this](const opt::Instruction* src_inst,
const opt::Instruction* dst_inst) {
return DoInstructionsMatchFuzzy(src_inst, dst_inst);
},
src_match_result, dst_match_result);
// TODO: take the gaps in between matches and match those again with a relaxed
// instruction-and-type-only comparison. This can produce a better diff for
// example if an array index is changed, causing the OpAccessChain id to not
// match and subsequently every operation that's derived from that id.
// Usually this mismatch cascades until the next OpStore which doesn't produce
// an id.
return static_cast<float>(best_match_length) * 2.0f /
static_cast<float>(src_body.size() + dst_body.size());
}
void Differ::MatchIdsInFunctionBodies(const InstructionList& src_body,
const InstructionList& dst_body,
const DiffMatch& src_match_result,
const DiffMatch& dst_match_result,
uint32_t flexibility) {
size_t src_cur = 0;
size_t dst_cur = 0;
while (src_cur < src_body.size() && dst_cur < dst_body.size()) {
if (src_match_result[src_cur] && dst_match_result[dst_cur]) {
// Match instructions the src and dst instructions.
//
// TODO: count the matchings between variables discovered this way and
// choose the "best match" after all functions have been diffed and all
// instructions analyzed.
const opt::Instruction* src_inst = src_body[src_cur++];
const opt::Instruction* dst_inst = dst_body[dst_cur++];
// Record the matching between the instructions. This is done only once
// (hence flexibility == 0). Calls with non-zero flexibility values will
// only deal with matching other ids based on the operands.
if (flexibility == 0) {
id_map_.MapInsts(src_inst, dst_inst);
}
// Match any unmatched variables referenced by the instructions.
MatchVariablesUsedByMatchedInstructions(src_inst, dst_inst, flexibility);
continue;
}
if (!src_match_result[src_cur]) {
++src_cur;
}
if (!dst_match_result[dst_cur]) {
++dst_cur;
}
}
}
void Differ::MatchVariablesUsedByMatchedInstructions(
const opt::Instruction* src_inst, const opt::Instruction* dst_inst,
uint32_t flexibility) {
// For OpAccessChain, OpLoad and OpStore instructions that reference unmatched
// variables, match them as a best effort.
assert(src_inst->opcode() == dst_inst->opcode());
switch (src_inst->opcode()) {
default:
// TODO: match functions based on OpFunctionCall?
break;
case SpvOpAccessChain:
case SpvOpInBoundsAccessChain:
case SpvOpPtrAccessChain:
case SpvOpInBoundsPtrAccessChain:
case SpvOpLoad:
case SpvOpStore:
const uint32_t src_pointer_id = src_inst->GetSingleWordInOperand(0);
const uint32_t dst_pointer_id = dst_inst->GetSingleWordInOperand(0);
if (IsVariable(src_id_to_, src_pointer_id) &&
IsVariable(dst_id_to_, dst_pointer_id) &&
!id_map_.IsSrcMapped(src_pointer_id) &&
!id_map_.IsDstMapped(dst_pointer_id) &&
AreVariablesMatchable(src_pointer_id, dst_pointer_id, flexibility)) {
id_map_.MapIds(src_pointer_id, dst_pointer_id);
}
break;
}
}
const opt::Instruction* Differ::GetInst(const IdInstructions& id_to,
uint32_t id) {
assert(id != 0);
assert(id < id_to.inst_map_.size());
const opt::Instruction* inst = id_to.inst_map_[id];
assert(inst != nullptr);
return inst;
}
uint32_t Differ::GetConstantUint(const IdInstructions& id_to,
uint32_t constant_id) {
const opt::Instruction* constant_inst = GetInst(id_to, constant_id);
assert(constant_inst->opcode() == SpvOpConstant);
assert(GetInst(id_to, constant_inst->type_id())->opcode() == SpvOpTypeInt);
return constant_inst->GetSingleWordInOperand(0);
}
SpvExecutionModel Differ::GetExecutionModel(const opt::Module* module,
uint32_t entry_point_id) {
for (const opt::Instruction& inst : module->entry_points()) {
assert(inst.opcode() == SpvOpEntryPoint);
if (inst.GetSingleWordOperand(1) == entry_point_id) {
return SpvExecutionModel(inst.GetSingleWordOperand(0));
}
}
assert(false && "Unreachable");
return SpvExecutionModel(0xFFF);
}
bool Differ::HasName(const IdInstructions& id_to, uint32_t id) {
assert(id != 0);
assert(id < id_to.name_map_.size());
for (const opt::Instruction* inst : id_to.name_map_[id]) {
if (inst->opcode() == SpvOpName) {
return true;
}
}
return false;
}
std::string Differ::GetName(const IdInstructions& id_to, uint32_t id,
bool* has_name) {
assert(id != 0);
assert(id < id_to.name_map_.size());
for (const opt::Instruction* inst : id_to.name_map_[id]) {
if (inst->opcode() == SpvOpName) {
*has_name = true;
return inst->GetOperand(1).AsString();
}
}
*has_name = false;
return "";
}
std::string Differ::GetSanitizedName(const IdInstructions& id_to, uint32_t id) {
bool has_name = false;
std::string name = GetName(id_to, id, &has_name);
if (!has_name) {
return "";
}
// Remove args from the name, in case this is a function name
return name.substr(0, name.find('('));
}
uint32_t Differ::GetVarTypeId(const IdInstructions& id_to, uint32_t var_id,
SpvStorageClass* storage_class) {
const opt::Instruction* var_inst = GetInst(id_to, var_id);
assert(var_inst->opcode() == SpvOpVariable);
*storage_class = SpvStorageClass(var_inst->GetSingleWordInOperand(0));
// Get the type pointer from the variable.
const uint32_t type_pointer_id = var_inst->type_id();
const opt::Instruction* type_pointer_inst = GetInst(id_to, type_pointer_id);
// Get the type from the type pointer.
return type_pointer_inst->GetSingleWordInOperand(1);
}
bool Differ::GetDecorationValue(const IdInstructions& id_to, uint32_t id,
SpvDecoration decoration,
uint32_t* decoration_value) {
assert(id != 0);
assert(id < id_to.decoration_map_.size());
for (const opt::Instruction* inst : id_to.decoration_map_[id]) {
if (inst->opcode() == SpvOpDecorate &&
inst->GetSingleWordOperand(0) == id &&
inst->GetSingleWordOperand(1) == decoration) {
*decoration_value = inst->GetSingleWordOperand(2);
return true;
}
}
return false;
}
const opt::Instruction* Differ::GetForwardPointerInst(
const IdInstructions& id_to, uint32_t id) {
assert(id != 0);
assert(id < id_to.forward_pointer_map_.size());
return id_to.forward_pointer_map_[id];
}
bool Differ::IsIntType(const IdInstructions& id_to, uint32_t type_id) {
return IsOp(id_to, type_id, SpvOpTypeInt);
}
bool Differ::IsFloatType(const IdInstructions& id_to, uint32_t type_id) {
return IsOp(id_to, type_id, SpvOpTypeFloat);
}
bool Differ::IsConstantUint(const IdInstructions& id_to, uint32_t id) {
const opt::Instruction* constant_inst = GetInst(id_to, id);
if (constant_inst->opcode() != SpvOpConstant) {
return false;
}
const opt::Instruction* type_inst = GetInst(id_to, constant_inst->type_id());
return type_inst->opcode() == SpvOpTypeInt;
}
bool Differ::IsVariable(const IdInstructions& id_to, uint32_t pointer_id) {
return IsOp(id_to, pointer_id, SpvOpVariable);
}
bool Differ::IsOp(const IdInstructions& id_to, uint32_t id, SpvOp op) {
return GetInst(id_to, id)->opcode() == op;
}
bool Differ::IsPerVertexType(const IdInstructions& id_to, uint32_t type_id) {
assert(type_id != 0);
assert(type_id < id_to.decoration_map_.size());
for (const opt::Instruction* inst : id_to.decoration_map_[type_id]) {
if (inst->opcode() == SpvOpMemberDecorate &&
inst->GetSingleWordOperand(0) == type_id &&
inst->GetSingleWordOperand(2) == SpvDecorationBuiltIn) {
SpvBuiltIn built_in = SpvBuiltIn(inst->GetSingleWordOperand(3));
// Only gl_PerVertex can have, and it can only have, the following
// built-in decorations.
return built_in == SpvBuiltInPosition ||
built_in == SpvBuiltInPointSize ||
built_in == SpvBuiltInClipDistance ||
built_in == SpvBuiltInCullDistance;
}
}
return false;
}
bool Differ::IsPerVertexVariable(const IdInstructions& id_to, uint32_t var_id) {
// Get the type from the type pointer.
SpvStorageClass storage_class;
uint32_t type_id = GetVarTypeId(id_to, var_id, &storage_class);
const opt::Instruction* type_inst = GetInst(id_to, type_id);
// If array, get the element type.
if (type_inst->opcode() == SpvOpTypeArray) {
type_id = type_inst->GetSingleWordInOperand(0);
}
// Now check if the type is gl_PerVertex.
return IsPerVertexType(id_to, type_id);
}
SpvStorageClass Differ::GetPerVertexStorageClass(const opt::Module* module,
uint32_t type_id) {
for (const opt::Instruction& inst : module->types_values()) {
switch (inst.opcode()) {
case SpvOpTypeArray:
// The gl_PerVertex instance could be an array, look for a variable of
// the array type instead.
if (inst.GetSingleWordInOperand(0) == type_id) {
type_id = inst.result_id();
}
break;
case SpvOpTypePointer:
// Find the storage class of the pointer to this type.
if (inst.GetSingleWordInOperand(1) == type_id) {
return SpvStorageClass(inst.GetSingleWordInOperand(0));
}
break;
default:
break;
}
}
// gl_PerVertex is declared, but is unused. Return either of Input or Output
// classes just so it matches one in the other module. This should be highly
// unlikely, perhaps except for ancient GS-used-to-emulate-CS scenarios.
return SpvStorageClassOutput;
}
spv_ext_inst_type_t Differ::GetExtInstType(const IdInstructions& id_to,
uint32_t set_id) {
const opt::Instruction* set_inst = GetInst(id_to, set_id);
return spvExtInstImportTypeGet(set_inst->GetInOperand(0).AsString().c_str());
}
spv_number_kind_t Differ::GetNumberKind(const IdInstructions& id_to,
const opt::Instruction& inst,
uint32_t operand_index,
uint32_t* number_bit_width) {
const opt::Operand& operand = inst.GetOperand(operand_index);
*number_bit_width = 0;
// A very limited version of Parser::parseOperand.
switch (operand.type) {
case SPV_OPERAND_TYPE_LITERAL_INTEGER:
case SPV_OPERAND_TYPE_OPTIONAL_LITERAL_INTEGER:
// Always unsigned integers.
*number_bit_width = 32;
return SPV_NUMBER_UNSIGNED_INT;
case SPV_OPERAND_TYPE_TYPED_LITERAL_NUMBER:
case SPV_OPERAND_TYPE_OPTIONAL_TYPED_LITERAL_INTEGER:
switch (inst.opcode()) {
case SpvOpSwitch:
case SpvOpConstant:
case SpvOpSpecConstant:
// Same kind of number as the selector (OpSwitch) or the type
// (Op*Constant).
return GetTypeNumberKind(id_to, inst.GetSingleWordOperand(0),
number_bit_width);
default:
assert(false && "Unreachable");
break;
}
break;
default:
break;
}
return SPV_NUMBER_NONE;
}
spv_number_kind_t Differ::GetTypeNumberKind(const IdInstructions& id_to,
uint32_t id,
uint32_t* number_bit_width) {
const opt::Instruction* type_inst = GetInst(id_to, id);
if (!spvOpcodeIsScalarType(type_inst->opcode())) {
type_inst = GetInst(id_to, type_inst->type_id());
}
switch (type_inst->opcode()) {
case SpvOpTypeInt:
*number_bit_width = type_inst->GetSingleWordOperand(1);
return type_inst->GetSingleWordOperand(2) == 0 ? SPV_NUMBER_UNSIGNED_INT
: SPV_NUMBER_SIGNED_INT;
break;
case SpvOpTypeFloat:
*number_bit_width = type_inst->GetSingleWordOperand(1);
return SPV_NUMBER_FLOATING;
default:
assert(false && "Unreachable");
return SPV_NUMBER_NONE;
}
}
void Differ::MatchCapabilities() {
MatchPreambleInstructions(src_->capabilities(), dst_->capabilities());
}
void Differ::MatchExtensions() {
MatchPreambleInstructions(src_->extensions(), dst_->extensions());
}
void Differ::MatchExtInstImportIds() {
// Bunch all of this section's ids as potential matches.
PotentialIdMap potential_id_map;
auto get_result_id = [](const opt::Instruction& inst) {
return inst.result_id();
};
auto accept_all = [](const opt::Instruction&) { return true; };
PoolPotentialIds(src_->ext_inst_imports(), potential_id_map.src_ids, true,
accept_all, get_result_id);
PoolPotentialIds(dst_->ext_inst_imports(), potential_id_map.dst_ids, false,
accept_all, get_result_id);
// Then match the ids.
MatchIds(potential_id_map, [](const opt::Instruction* src_inst,
const opt::Instruction* dst_inst) {
// Match OpExtInstImport by exact name, which is operand 1
const opt::Operand& src_name = src_inst->GetOperand(1);
const opt::Operand& dst_name = dst_inst->GetOperand(1);
return src_name.AsString() == dst_name.AsString();
});
}
void Differ::MatchMemoryModel() {
// Always match the memory model instructions, there is always a single one of
// it.
id_map_.MapInsts(src_->GetMemoryModel(), dst_->GetMemoryModel());
}
void Differ::MatchEntryPointIds() {
// Match OpEntryPoint ids (at index 1) by ExecutionModel (at index 0) and
// possibly name (at index 2). OpEntryPoint doesn't produce a result id, so
// this function doesn't use the helpers the other functions use.
// Map from execution model to OpEntryPoint instructions of that model.
using ExecutionModelMap =
std::unordered_map<uint32_t, std::vector<const opt::Instruction*>>;
ExecutionModelMap src_entry_points_map;
ExecutionModelMap dst_entry_points_map;
std::set<uint32_t> all_execution_models;
for (const opt::Instruction& src_inst : src_->entry_points()) {
uint32_t execution_model = src_inst.GetSingleWordOperand(0);
src_entry_points_map[execution_model].push_back(&src_inst);
all_execution_models.insert(execution_model);
}
for (const opt::Instruction& dst_inst : dst_->entry_points()) {
uint32_t execution_model = dst_inst.GetSingleWordOperand(0);
dst_entry_points_map[execution_model].push_back(&dst_inst);
all_execution_models.insert(execution_model);
}
// Go through each model and match the ids.
for (const uint32_t execution_model : all_execution_models) {
auto& src_insts = src_entry_points_map[execution_model];
auto& dst_insts = dst_entry_points_map[execution_model];
// If there is only one entry point in src and dst with that model, match
// them unconditionally.
if (src_insts.size() == 1 && dst_insts.size() == 1) {
uint32_t src_id = src_insts[0]->GetSingleWordOperand(1);
uint32_t dst_id = dst_insts[0]->GetSingleWordOperand(1);
id_map_.MapIds(src_id, dst_id);
id_map_.MapInsts(src_insts[0], dst_insts[0]);
continue;
}
// Otherwise match them by name.
bool matched = false;
for (const opt::Instruction* src_inst : src_insts) {
for (const opt::Instruction* dst_inst : dst_insts) {
const opt::Operand& src_name = src_inst->GetOperand(2);
const opt::Operand& dst_name = dst_inst->GetOperand(2);
if (src_name.AsString() == dst_name.AsString()) {
uint32_t src_id = src_inst->GetSingleWordOperand(1);
uint32_t dst_id = dst_inst->GetSingleWordOperand(1);
id_map_.MapIds(src_id, dst_id);
id_map_.MapInsts(src_inst, dst_inst);
matched = true;
break;
}
}
if (matched) {
break;
}
}
}
}
void Differ::MatchExecutionModes() {
MatchPreambleInstructions(src_->execution_modes(), dst_->execution_modes());
}
void Differ::MatchTypeForwardPointers() {
// Bunch all of type forward pointers as potential matches.
PotentialIdMap potential_id_map;
auto get_pointer_type_id = [](const opt::Instruction& inst) {
return inst.GetSingleWordOperand(0);
};
auto accept_type_forward_pointer_ops = [](const opt::Instruction& inst) {
return inst.opcode() == SpvOpTypeForwardPointer;
};
PoolPotentialIds(src_->types_values(), potential_id_map.src_ids, true,
accept_type_forward_pointer_ops, get_pointer_type_id);
PoolPotentialIds(dst_->types_values(), potential_id_map.dst_ids, false,
accept_type_forward_pointer_ops, get_pointer_type_id);
// Matching types with cyclical references (i.e. in the style of linked lists)
// can get very complex. Currently, the diff tool matches types bottom up, so
// on every instruction it expects to know if its operands are already matched
// or not. With cyclical references, it cannot know that. Type matching may
// need significant modifications to be able to support this use case.
//
// Currently, forwarded types are only matched by storage class and debug
// info, with minimal matching of the type being forwarded:
//
// - Group by class
// - Group by OpType being pointed to
// - Group by debug info
// - If same name and unique, match
// - If leftover is unique, match
// Group forwarded pointers by storage class first and loop over them.
GroupIdsAndMatch<SpvStorageClass>(
potential_id_map.src_ids, potential_id_map.dst_ids, SpvStorageClassMax,
&Differ::GroupIdsHelperGetTypePointerStorageClass,
[this](const IdGroup& src_group_by_storage_class,
const IdGroup& dst_group_by_storage_class) {
// Group them further by the type they are pointing to and loop over
// them.
GroupIdsAndMatch<SpvOp>(
src_group_by_storage_class, dst_group_by_storage_class, SpvOpMax,
&Differ::GroupIdsHelperGetTypePointerTypeOp,
[this](const IdGroup& src_group_by_type_op,
const IdGroup& dst_group_by_type_op) {
// Group them even further by debug info, if possible and match by
// debug name.
MatchTypeForwardPointersByName(src_group_by_type_op,
dst_group_by_type_op);
// Match the leftovers only if they lack debug info and there is
// only one instance of them.
MatchTypeForwardPointersByTypeOp(src_group_by_type_op,
dst_group_by_type_op);
});
});
// Match the instructions that forward declare the same type themselves
for (uint32_t src_id : potential_id_map.src_ids) {
uint32_t dst_id = id_map_.MappedDstId(src_id);
if (dst_id == 0) continue;
const opt::Instruction* src_forward_inst =
GetForwardPointerInst(src_id_to_, src_id);
const opt::Instruction* dst_forward_inst =
GetForwardPointerInst(dst_id_to_, dst_id);
assert(src_forward_inst);
assert(dst_forward_inst);
id_map_.MapInsts(src_forward_inst, dst_forward_inst);
}
}
void Differ::MatchTypeIds() {
// Bunch all of type ids as potential matches.
PotentialIdMap potential_id_map;
auto get_result_id = [](const opt::Instruction& inst) {
return inst.result_id();
};
auto accept_type_ops = [](const opt::Instruction& inst) {
return spvOpcodeGeneratesType(inst.opcode());
};
PoolPotentialIds(src_->types_values(), potential_id_map.src_ids, true,
accept_type_ops, get_result_id);
PoolPotentialIds(dst_->types_values(), potential_id_map.dst_ids, false,
accept_type_ops, get_result_id);
// Then match the ids. Start with exact matches, then match the leftover with
// gradually loosening degrees of strictness. For example, in the absence of
// debug info, two block types will be matched if they differ only in a few of
// the fields.
for (uint32_t flexibility = 0; flexibility < 2; ++flexibility) {
MatchIds(potential_id_map, [this, flexibility](
const opt::Instruction* src_inst,
const opt::Instruction* dst_inst) {
const SpvOp src_op = src_inst->opcode();
const SpvOp dst_op = dst_inst->opcode();
// Don't match if the opcode is not the same.
if (src_op != dst_op) {
return false;
}
switch (src_op) {
case SpvOpTypeVoid:
case SpvOpTypeBool:
case SpvOpTypeSampler:
// void, bool and sampler are unique, match them.
return true;
case SpvOpTypeInt:
case SpvOpTypeFloat:
case SpvOpTypeVector:
case SpvOpTypeMatrix:
case SpvOpTypeSampledImage:
case SpvOpTypeRuntimeArray:
case SpvOpTypePointer:
// Match these instructions when all operands match.
assert(src_inst->NumInOperandWords() ==
dst_inst->NumInOperandWords());
return DoOperandsMatch(src_inst, dst_inst, 0,
src_inst->NumInOperandWords());
case SpvOpTypeFunction:
case SpvOpTypeImage:
// Match function types only if they have the same number of operands,
// and they all match.
// Match image types similarly, expecting the optional final parameter
// to match (if provided in both)
if (src_inst->NumInOperandWords() != dst_inst->NumInOperandWords()) {
return false;
}
return DoOperandsMatch(src_inst, dst_inst, 0,
src_inst->NumInOperandWords());
case SpvOpTypeArray:
// Match arrays only if the element type and length match. The length
// is an id of a constant, so the actual constant it's defining is
// compared instead.
if (!DoOperandsMatch(src_inst, dst_inst, 0, 1)) {
return false;
}
if (AreIdenticalUintConstants(src_inst->GetSingleWordInOperand(1),
dst_inst->GetSingleWordInOperand(1))) {
return true;
}
// If size is not OpConstant, expect the ids to match exactly (for
// example if a spec contant is used).
return DoOperandsMatch(src_inst, dst_inst, 1, 1);
case SpvOpTypeStruct:
return MatchOpTypeStruct(src_inst, dst_inst, flexibility);
default:
return false;
}
});
}
}
void Differ::MatchConstants() {
// Bunch all of constant ids as potential matches.
PotentialIdMap potential_id_map;
auto get_result_id = [](const opt::Instruction& inst) {
return inst.result_id();
};
auto accept_type_ops = [](const opt::Instruction& inst) {
return spvOpcodeIsConstant(inst.opcode());
};
PoolPotentialIds(src_->types_values(), potential_id_map.src_ids, true,
accept_type_ops, get_result_id);
PoolPotentialIds(dst_->types_values(), potential_id_map.dst_ids, false,
accept_type_ops, get_result_id);
// Then match the ids. Constants are matched exactly, except for float types
// that are first matched exactly, then leftovers are matched with a small
// error.
for (uint32_t flexibility = 0; flexibility < 2; ++flexibility) {
MatchIds(potential_id_map, [this, flexibility](
const opt::Instruction* src_inst,
const opt::Instruction* dst_inst) {
const SpvOp src_op = src_inst->opcode();
const SpvOp dst_op = dst_inst->opcode();
// Don't match if the opcode is not the same.
if (src_op != dst_op) {
return false;
}
switch (src_op) {
case SpvOpConstantTrue:
case SpvOpConstantFalse:
// true and false are unique, match them.
return true;
case SpvOpConstant:
return MatchOpConstant(src_inst, dst_inst, flexibility);
case SpvOpConstantComposite:
case SpvOpSpecConstantComposite:
// Composite constants must match in type and value.
//
// TODO: match OpConstantNull with OpConstantComposite with all zeros
// at flexibility == 1
// TODO: match constants from structs that have been flexibly-matched.
if (src_inst->NumInOperandWords() != dst_inst->NumInOperandWords()) {
return false;
}
return DoesOperandMatch(src_inst->GetOperand(0),
dst_inst->GetOperand(0)) &&
DoOperandsMatch(src_inst, dst_inst, 0,
src_inst->NumInOperandWords());
case SpvOpConstantSampler:
// Match sampler constants exactly.
// TODO: Allow flexibility in parameters to better diff shaders where
// the sampler param has changed.
assert(src_inst->NumInOperandWords() ==
dst_inst->NumInOperandWords());
return DoOperandsMatch(src_inst, dst_inst, 0,
src_inst->NumInOperandWords());
case SpvOpConstantNull:
// Match null constants as long as the type matches.
return DoesOperandMatch(src_inst->GetOperand(0),
dst_inst->GetOperand(0));
case SpvOpSpecConstantTrue:
case SpvOpSpecConstantFalse:
case SpvOpSpecConstant:
case SpvOpSpecConstantOp:
// Match spec constants by name if available, then by the SpecId
// decoration.
return MatchOpSpecConstant(src_inst, dst_inst);
default:
return false;
}
});
}
}
void Differ::MatchVariableIds() {
// Bunch all of variable ids as potential matches.
PotentialIdMap potential_id_map;
auto get_result_id = [](const opt::Instruction& inst) {
return inst.result_id();
};
auto accept_type_ops = [](const opt::Instruction& inst) {
return inst.opcode() == SpvOpVariable;
};
PoolPotentialIds(src_->types_values(), potential_id_map.src_ids, true,
accept_type_ops, get_result_id);
PoolPotentialIds(dst_->types_values(), potential_id_map.dst_ids, false,
accept_type_ops, get_result_id);
// Then match the ids. Start with exact matches, then match the leftover with
// gradually loosening degrees of strictness. For example, in the absence of
// debug info, two otherwise identical variables will be matched if one of
// them has a Private storage class and the other doesn't.
for (uint32_t flexibility = 0; flexibility < 2; ++flexibility) {
MatchIds(potential_id_map,
[this, flexibility](const opt::Instruction* src_inst,
const opt::Instruction* dst_inst) {
assert(src_inst->opcode() == SpvOpVariable);
assert(dst_inst->opcode() == SpvOpVariable);
return MatchOpVariable(src_inst, dst_inst, flexibility);
});
}
}
void Differ::MatchFunctions() {
IdGroup src_func_ids;
IdGroup dst_func_ids;
for (const auto& func : src_funcs_) {
src_func_ids.push_back(func.first);
}
for (const auto& func : dst_funcs_) {
dst_func_ids.push_back(func.first);
}
// Base the matching of functions on debug info when available.
GroupIdsAndMatch<std::string>(
src_func_ids, dst_func_ids, "", &Differ::GetSanitizedName,
[this](const IdGroup& src_group, const IdGroup& dst_group) {
// If there is a single function with this name in src and dst, it's a
// definite match.
if (src_group.size() == 1 && dst_group.size() == 1) {
id_map_.MapIds(src_group[0], dst_group[0]);
return;
}
// If there are multiple functions with the same name, group them by
// type, and match only if the types match (and are unique).
GroupIdsAndMatch<uint32_t>(src_group, dst_group, 0,
&Differ::GroupIdsHelperGetTypeId,
[this](const IdGroup& src_group_by_type_id,
const IdGroup& dst_group_by_type_id) {
if (src_group_by_type_id.size() == 1 &&
dst_group_by_type_id.size() == 1) {
id_map_.MapIds(src_group_by_type_id[0],
dst_group_by_type_id[0]);
}
});
});
// Any functions that are left are pooled together and matched as if unnamed,
// with the only exception that two functions with mismatching names are not
// matched.
//
// Before that however, the diff of the functions that are matched are taken
// and processed, so that more of the global variables can be matched before
// attempting to match the rest of the functions. They can contribute to the
// precision of the diff of those functions.
for (const uint32_t src_func_id : src_func_ids) {
const uint32_t dst_func_id = id_map_.MappedDstId(src_func_id);
if (dst_func_id == 0) {
continue;
}
// Since these functions are definite matches, match their parameters for a
// better diff.
MatchFunctionParamIds(src_funcs_[src_func_id], dst_funcs_[dst_func_id]);
// Take the diff of the two functions.
DiffMatch src_match_result, dst_match_result;
MatchFunctionBodies(src_func_insts_[src_func_id],
dst_func_insts_[dst_func_id], &src_match_result,
&dst_match_result);
// Match ids between the two function bodies; which can also result in
// global variables getting matched.
MatchIdsInFunctionBodies(src_func_insts_[src_func_id],
dst_func_insts_[dst_func_id], src_match_result,
dst_match_result, 0);
}
// Best effort match functions with matching type.
GroupIdsAndMatch<uint32_t>(
src_func_ids, dst_func_ids, 0, &Differ::GroupIdsHelperGetTypeId,
[this](const IdGroup& src_group_by_type_id,
const IdGroup& dst_group_by_type_id) {
BestEffortMatchFunctions(src_group_by_type_id, dst_group_by_type_id,
src_func_insts_, dst_func_insts_);
});
// Any function that's left, best effort match them.
BestEffortMatchFunctions(src_func_ids, dst_func_ids, src_func_insts_,
dst_func_insts_);
}
void Differ::MatchDebugs1() {
// This section in cludes: OpString, OpSourceExtension, OpSource,
// OpSourceContinued
MatchDebugAndAnnotationInstructions(src_->debugs1(), dst_->debugs1());
}
void Differ::MatchDebugs2() {
// This section includes: OpName, OpMemberName
MatchDebugAndAnnotationInstructions(src_->debugs2(), dst_->debugs2());
}
void Differ::MatchDebugs3() {
// This section includes: OpModuleProcessed
MatchDebugAndAnnotationInstructions(src_->debugs3(), dst_->debugs3());
}
void Differ::MatchExtInstDebugInfo() {
// This section includes OpExtInst for DebugInfo extension
MatchDebugAndAnnotationInstructions(src_->ext_inst_debuginfo(),
dst_->ext_inst_debuginfo());
}
void Differ::MatchAnnotations() {
// This section includes OpDecorate and family.
MatchDebugAndAnnotationInstructions(src_->annotations(), dst_->annotations());
}
const opt::Instruction* Differ::MappedDstInst(
const opt::Instruction* src_inst) {
return MappedInstImpl(src_inst, id_map_.SrcToDstMap(), dst_id_to_);
}
const opt::Instruction* Differ::MappedSrcInst(
const opt::Instruction* dst_inst) {
return MappedInstImpl(dst_inst, id_map_.DstToSrcMap(), src_id_to_);
}
const opt::Instruction* Differ::MappedInstImpl(
const opt::Instruction* inst, const IdMap& to_other,
const IdInstructions& other_id_to) {
if (inst->HasResultId()) {
if (to_other.IsMapped(inst->result_id())) {
const uint32_t other_result_id = to_other.MappedId(inst->result_id());
assert(other_result_id < other_id_to.inst_map_.size());
return other_id_to.inst_map_[other_result_id];
}
return nullptr;
}
return to_other.MappedInst(inst);
}
void Differ::OutputLine(std::function<bool()> are_lines_identical,
std::function<void()> output_src_line,
std::function<void()> output_dst_line) {
if (are_lines_identical()) {
out_ << " ";
output_src_line();
} else {
OutputRed();
out_ << "-";
output_src_line();
OutputGreen();
out_ << "+";
output_dst_line();
OutputResetColor();
}
}
const opt::Instruction* IterInst(opt::Module::const_inst_iterator& iter) {
return &*iter;
}
const opt::Instruction* IterInst(InstructionList::const_iterator& iter) {
return *iter;
}
template <typename InstList>
void Differ::OutputSection(
const InstList& src_insts, const InstList& dst_insts,
std::function<void(const opt::Instruction&, const IdInstructions&,
const opt::Instruction&)>
write_inst) {
auto src_iter = src_insts.begin();
auto dst_iter = dst_insts.begin();
// - While src_inst doesn't have a match, output it with -
// - While dst_inst doesn't have a match, output it with +
// - Now src_inst and dst_inst both have matches; might not match each other!
// * If section is unordered, just process src_inst and its match (dst_inst
// or not),
// dst_inst will eventually be processed when its match is seen.
// * If section is ordered, also just process src_inst and its match. Its
// match must
// necessarily be dst_inst.
while (src_iter != src_insts.end() || dst_iter != dst_insts.end()) {
OutputRed();
while (src_iter != src_insts.end() &&
MappedDstInst(IterInst(src_iter)) == nullptr) {
out_ << "-";
write_inst(*IterInst(src_iter), src_id_to_, *IterInst(src_iter));
++src_iter;
}
OutputGreen();
while (dst_iter != dst_insts.end() &&
MappedSrcInst(IterInst(dst_iter)) == nullptr) {
out_ << "+";
write_inst(ToMappedSrcIds(*IterInst(dst_iter)), dst_id_to_,
*IterInst(dst_iter));
++dst_iter;
}
OutputResetColor();
if (src_iter != src_insts.end() && dst_iter != dst_insts.end()) {
const opt::Instruction* src_inst = IterInst(src_iter);
const opt::Instruction* matched_dst_inst = MappedDstInst(src_inst);
assert(matched_dst_inst != nullptr);
assert(MappedSrcInst(IterInst(dst_iter)) != nullptr);
OutputLine(
[this, src_inst, matched_dst_inst]() {
return DoInstructionsMatch(src_inst, matched_dst_inst);
},
[this, src_inst, &write_inst]() {
write_inst(*src_inst, src_id_to_, *src_inst);
},
[this, matched_dst_inst, &write_inst]() {
write_inst(ToMappedSrcIds(*matched_dst_inst), dst_id_to_,
*matched_dst_inst);
});
++src_iter;
++dst_iter;
}
}
}
void Differ::ToParsedInstruction(
const opt::Instruction& inst, const IdInstructions& id_to,
const opt::Instruction& original_inst,
spv_parsed_instruction_t* parsed_inst,
std::vector<spv_parsed_operand_t>& parsed_operands,
std::vector<uint32_t>& inst_binary) {
inst.ToBinaryWithoutAttachedDebugInsts(&inst_binary);
parsed_operands.resize(inst.NumOperands());
parsed_inst->words = inst_binary.data();
parsed_inst->num_words = static_cast<uint16_t>(inst_binary.size());
parsed_inst->opcode = static_cast<uint16_t>(inst.opcode());
parsed_inst->ext_inst_type =
inst.opcode() == SpvOpExtInst
? GetExtInstType(id_to, original_inst.GetSingleWordInOperand(0))
: SPV_EXT_INST_TYPE_NONE;
parsed_inst->type_id =
inst.HasResultType() ? inst.GetSingleWordOperand(0) : 0;
parsed_inst->result_id = inst.HasResultId() ? inst.result_id() : 0;
parsed_inst->operands = parsed_operands.data();
parsed_inst->num_operands = static_cast<uint16_t>(parsed_operands.size());
// Word 0 is always op and num_words, so operands start at offset 1.
uint32_t offset = 1;
for (uint16_t operand_index = 0; operand_index < parsed_inst->num_operands;
++operand_index) {
const opt::Operand& operand = inst.GetOperand(operand_index);
spv_parsed_operand_t& parsed_operand = parsed_operands[operand_index];
parsed_operand.offset = static_cast<uint16_t>(offset);
parsed_operand.num_words = static_cast<uint16_t>(operand.words.size());
parsed_operand.type = operand.type;
parsed_operand.number_kind = GetNumberKind(
id_to, original_inst, operand_index, &parsed_operand.number_bit_width);
offset += parsed_operand.num_words;
}
}
opt::Instruction Differ::ToMappedSrcIds(const opt::Instruction& dst_inst) {
// Create an identical instruction to dst_inst, except ids are changed to the
// mapped one.
opt::Instruction mapped_inst = dst_inst;
for (uint32_t operand_index = 0; operand_index < mapped_inst.NumOperands();
++operand_index) {
opt::Operand& operand = mapped_inst.GetOperand(operand_index);
if (spvIsIdType(operand.type)) {
assert(id_map_.IsDstMapped(operand.AsId()));
operand.words[0] = id_map_.MappedSrcId(operand.AsId());
}
}
return mapped_inst;
}
spv_result_t Differ::Output() {
id_map_.MapUnmatchedIds();
src_id_to_.inst_map_.resize(id_map_.SrcToDstMap().IdBound(), nullptr);
dst_id_to_.inst_map_.resize(id_map_.DstToSrcMap().IdBound(), nullptr);
const spv_target_env target_env = SPV_ENV_UNIVERSAL_1_6;
spv_opcode_table opcode_table;
spv_operand_table operand_table;
spv_ext_inst_table ext_inst_table;
spv_result_t result;
result = spvOpcodeTableGet(&opcode_table, target_env);
if (result != SPV_SUCCESS) return result;
result = spvOperandTableGet(&operand_table, target_env);
if (result != SPV_SUCCESS) return result;
result = spvExtInstTableGet(&ext_inst_table, target_env);
if (result != SPV_SUCCESS) return result;
spv_context_t context{
target_env,
opcode_table,
operand_table,
ext_inst_table,
};
const AssemblyGrammar grammar(&context);
if (!grammar.isValid()) return SPV_ERROR_INVALID_TABLE;
uint32_t disassembly_options = SPV_BINARY_TO_TEXT_OPTION_PRINT;
if (options_.indent) {
disassembly_options |= SPV_BINARY_TO_TEXT_OPTION_INDENT;
}
NameMapper name_mapper = GetTrivialNameMapper();
disassemble::InstructionDisassembler dis(grammar, out_, disassembly_options,
name_mapper);
if (!options_.no_header) {
// Output the header
// TODO: when using diff with text, the assembler overrides the version and
// generator, so these aren't reflected correctly in the output. Could
// potentially extract this info from the header comment.
OutputLine([]() { return true; }, [&dis]() { dis.EmitHeaderSpirv(); },
[]() { assert(false && "Unreachable"); });
OutputLine([this]() { return src_->version() == dst_->version(); },
[this, &dis]() { dis.EmitHeaderVersion(src_->version()); },
[this, &dis]() { dis.EmitHeaderVersion(dst_->version()); });
OutputLine([this]() { return src_->generator() == dst_->generator(); },
[this, &dis]() { dis.EmitHeaderGenerator(src_->generator()); },
[this, &dis]() { dis.EmitHeaderGenerator(dst_->generator()); });
OutputLine(
[this]() { return src_->IdBound() == id_map_.SrcToDstMap().IdBound(); },
[this, &dis]() { dis.EmitHeaderIdBound(src_->IdBound()); },
[this, &dis]() {
dis.EmitHeaderIdBound(id_map_.SrcToDstMap().IdBound());
});
OutputLine([this]() { return src_->schema() == dst_->schema(); },
[this, &dis]() { dis.EmitHeaderSchema(src_->schema()); },
[this, &dis]() { dis.EmitHeaderSchema(dst_->schema()); });
}
// For each section, iterate both modules and output the disassembly.
auto write_inst = [this, &dis](const opt::Instruction& inst,
const IdInstructions& id_to,
const opt::Instruction& original_inst) {
spv_parsed_instruction_t parsed_inst;
std::vector<spv_parsed_operand_t> parsed_operands;
std::vector<uint32_t> inst_binary;
ToParsedInstruction(inst, id_to, original_inst, &parsed_inst,
parsed_operands, inst_binary);
dis.EmitInstruction(parsed_inst, 0);
};
OutputSection(src_->capabilities(), dst_->capabilities(), write_inst);
OutputSection(src_->extensions(), dst_->extensions(), write_inst);
OutputSection(src_->ext_inst_imports(), dst_->ext_inst_imports(), write_inst);
// There is only one memory model.
OutputLine(
[this]() {
return DoInstructionsMatch(src_->GetMemoryModel(),
dst_->GetMemoryModel());
},
[this, &write_inst]() {
write_inst(*src_->GetMemoryModel(), src_id_to_,
*src_->GetMemoryModel());
},
[this, &write_inst]() {
write_inst(*dst_->GetMemoryModel(), dst_id_to_,
*dst_->GetMemoryModel());
});
OutputSection(src_->entry_points(), dst_->entry_points(), write_inst);
OutputSection(src_->execution_modes(), dst_->execution_modes(), write_inst);
OutputSection(src_->debugs1(), dst_->debugs1(), write_inst);
OutputSection(src_->debugs2(), dst_->debugs2(), write_inst);
OutputSection(src_->debugs3(), dst_->debugs3(), write_inst);
OutputSection(src_->ext_inst_debuginfo(), dst_->ext_inst_debuginfo(),
write_inst);
OutputSection(src_->annotations(), dst_->annotations(), write_inst);
OutputSection(src_->types_values(), dst_->types_values(), write_inst);
// Get the body of all the functions.
FunctionInstMap src_func_header_insts;
FunctionInstMap dst_func_header_insts;
GetFunctionHeaderInstructions(src_, &src_func_header_insts);
GetFunctionHeaderInstructions(dst_, &dst_func_header_insts);
for (const auto& src_func : src_func_insts_) {
const uint32_t src_func_id = src_func.first;
const InstructionList& src_insts = src_func.second;
const InstructionList& src_header_insts =
src_func_header_insts[src_func_id];
const uint32_t dst_func_id = id_map_.MappedDstId(src_func_id);