| // Copyright (c) 2021 Alastair F. Donaldson |
| // |
| // 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/fuzz/available_instructions.h" |
| #include "source/fuzz/fuzzer_util.h" |
| |
| namespace spvtools { |
| namespace fuzz { |
| |
| AvailableInstructions::AvailableInstructions( |
| opt::IRContext* ir_context, |
| const std::function<bool(opt::IRContext*, opt::Instruction*)>& predicate) |
| : ir_context_(ir_context) { |
| // Consider all global declarations |
| for (auto& global : ir_context->module()->types_values()) { |
| if (predicate(ir_context, &global)) { |
| available_globals_.push_back(&global); |
| } |
| } |
| |
| // Consider every function |
| for (auto& function : *ir_context->module()) { |
| // Identify those function parameters that satisfy the predicate. |
| std::vector<opt::Instruction*> available_params_for_function; |
| function.ForEachParam( |
| [&predicate, ir_context, |
| &available_params_for_function](opt::Instruction* param) { |
| if (predicate(ir_context, param)) { |
| available_params_for_function.push_back(param); |
| } |
| }); |
| |
| // Consider every reachable block in the function. |
| auto dominator_analysis = ir_context->GetDominatorAnalysis(&function); |
| for (auto& block : function) { |
| if (!fuzzerutil::BlockIsReachableInItsFunction(ir_context, &block)) { |
| // The block is not reachable. |
| continue; |
| } |
| if (&block == &*function.begin()) { |
| // The function entry block is special: only the relevant globals and |
| // function parameters are available at its entry point. |
| num_available_at_block_entry_.insert( |
| {&block, |
| static_cast<uint32_t>(available_params_for_function.size() + |
| available_globals_.size())}); |
| } else { |
| // |block| is not the entry block and is reachable, so it must have an |
| // immediate dominator. The number of instructions available on entry to |
| // |block| is thus the number of instructions available on entry to the |
| // immediate dominator + the number of instructions generated_by_block |
| // by the immediate dominator. |
| auto immediate_dominator = |
| dominator_analysis->ImmediateDominator(&block); |
| assert(immediate_dominator != nullptr && |
| "The block is reachable so should have an immediate dominator."); |
| assert(generated_by_block_.count(immediate_dominator) != 0 && |
| "Immediate dominator should have already been processed."); |
| assert(num_available_at_block_entry_.count(immediate_dominator) != 0 && |
| "Immediate dominator should have already been processed."); |
| num_available_at_block_entry_.insert( |
| {&block, |
| static_cast<uint32_t>( |
| generated_by_block_.at(immediate_dominator).size()) + |
| num_available_at_block_entry_.at(immediate_dominator)}); |
| } |
| // Now consider each instruction in the block. |
| std::vector<opt::Instruction*> generated_by_block; |
| for (auto& inst : block) { |
| assert(num_available_at_block_entry_.count(&block) != 0 && |
| "Block should have already been processed."); |
| // The number of available instructions before |inst| is the number |
| // available at the start of the block + the number of relevant |
| // instructions generated by the block so far. |
| num_available_before_instruction_.insert( |
| {&inst, num_available_at_block_entry_.at(&block) + |
| static_cast<uint32_t>(generated_by_block.size())}); |
| if (predicate(ir_context, &inst)) { |
| // This instruction satisfies the predicate, so note that it is |
| // generated by |block|. |
| generated_by_block.push_back(&inst); |
| } |
| } |
| generated_by_block_.emplace(&block, std::move(generated_by_block)); |
| } |
| available_params_.emplace(&function, |
| std::move(available_params_for_function)); |
| } |
| } |
| |
| AvailableInstructions::AvailableBeforeInstruction |
| AvailableInstructions::GetAvailableBeforeInstruction( |
| opt::Instruction* inst) const { |
| assert(num_available_before_instruction_.count(inst) != 0 && |
| "Availability can only be queried for reachable instructions."); |
| return {*this, inst}; |
| } |
| |
| AvailableInstructions::AvailableBeforeInstruction::AvailableBeforeInstruction( |
| const AvailableInstructions& available_instructions, opt::Instruction* inst) |
| : available_instructions_(available_instructions), inst_(inst) {} |
| |
| uint32_t AvailableInstructions::AvailableBeforeInstruction::size() const { |
| return available_instructions_.num_available_before_instruction_.at(inst_); |
| } |
| |
| bool AvailableInstructions::AvailableBeforeInstruction::empty() const { |
| return size() == 0; |
| } |
| |
| opt::Instruction* AvailableInstructions::AvailableBeforeInstruction::operator[]( |
| uint32_t index) const { |
| assert(index < size() && "Index out of bounds."); |
| |
| // First, check the cache to see whether we can return the available |
| // instruction in constant time. |
| auto cached_result = index_cache.find(index); |
| if (cached_result != index_cache.end()) { |
| return cached_result->second; |
| } |
| |
| // Next check whether the index falls into the global region. |
| if (index < available_instructions_.available_globals_.size()) { |
| auto result = available_instructions_.available_globals_[index]; |
| index_cache.insert({index, result}); |
| return result; |
| } |
| |
| auto block = available_instructions_.ir_context_->get_instr_block(inst_); |
| auto function = block->GetParent(); |
| |
| // Next check whether the index falls into the available instructions that |
| // correspond to function parameters. |
| if (index < |
| available_instructions_.available_globals_.size() + |
| available_instructions_.available_params_.at(function).size()) { |
| auto result = available_instructions_.available_params_.at( |
| function)[index - available_instructions_.available_globals_.size()]; |
| index_cache.insert({index, result}); |
| return result; |
| } |
| |
| auto dominator_analysis = |
| available_instructions_.ir_context_->GetDominatorAnalysis(function); |
| |
| // Now the expensive part (which is why we have the cache): walk the dominator |
| // tree backwards starting from the block containing |inst_| until we get to |
| // the block in which the instruction corresponding to |index| exists. |
| for (auto* ancestor = block; true; |
| ancestor = dominator_analysis->ImmediateDominator(ancestor)) { |
| uint32_t num_available_at_ancestor_entry = |
| available_instructions_.num_available_at_block_entry_.at(ancestor); |
| if (index_cache.count(num_available_at_ancestor_entry) == 0) { |
| // This is the first time we have traversed this block, so we populate the |
| // cache with the index of each instruction, so that if a future index |
| // query relates to indices associated with this block we can return the |
| // result in constant time. |
| auto& generated_by_ancestor = |
| available_instructions_.generated_by_block_.at(ancestor); |
| for (uint32_t local_index = 0; local_index < generated_by_ancestor.size(); |
| local_index++) { |
| index_cache.insert({num_available_at_ancestor_entry + local_index, |
| generated_by_ancestor[local_index]}); |
| } |
| } |
| if (index >= num_available_at_ancestor_entry) { |
| // This block contains the instruction we want, so by now it will be in |
| // the cache. |
| return index_cache.at(index); |
| } |
| assert(ancestor != &*function->begin() && |
| "By construction we should find a block associated with the index."); |
| } |
| |
| assert(false && "Unreachable."); |
| return nullptr; |
| } |
| |
| } // namespace fuzz |
| } // namespace spvtools |
