source/fuzz/available_instructions.h

   1 // Copyright (c) 2021 Alastair F. Donaldson
   2 //
   3 // Licensed under the Apache License, Version 2.0 (the "License");
   4 // you may not use this file except in compliance with the License.
   5 // You may obtain a copy of the License at
   6 //
   7 //     http://www.apache.org/licenses/LICENSE-2.0
   8 //
   9 // Unless required by applicable law or agreed to in writing, software
  10 // distributed under the License is distributed on an "AS IS" BASIS,
  11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12 // See the License for the specific language governing permissions and
  13 // limitations under the License.
  14
  15 #ifndef SOURCE_FUZZ_AVAILABLE_INSTRUCTIONS_H_
  16 #define SOURCE_FUZZ_AVAILABLE_INSTRUCTIONS_H_
  17
  18 #include <unordered_map>
  19 #include <vector>
  20
  21 #include "source/opt/instruction.h"
  22 #include "source/opt/ir_context.h"
  23
  24 namespace spvtools {
  25 namespace fuzz {
  26
  27 // A class for allowing efficient querying of the instruction that satisfy a
  28 // particular predicate that are available before a given instruction.
  29 // Availability information is only computed for instructions in *reachable*
  30 // basic blocks.
  31 class AvailableInstructions {
  32  public:
  33   // The outer class captures availability information for a whole module, and
  34   // each instance of this inner class captures availability for a particular
  35   // instruction.
  36   class AvailableBeforeInstruction {
  37    public:
  38     AvailableBeforeInstruction(
  39         const AvailableInstructions& available_instructions,
  40         opt::Instruction* inst);
  41
  42     // Returns the number of instructions that are available before the
  43     // instruction associated with this class.
  44     uint32_t size() const;
  45
  46     // Returns true if and only if |size()| is 0.
  47     bool empty() const;
  48
  49     // Requires |index| < |size()|. Returns the ith available instruction.
  50     opt::Instruction* operator[](uint32_t index) const;
  51
  52    private:
  53     // A references to an instance of the outer class.
  54     const AvailableInstructions& available_instructions_;
  55
  56     // The instruction for which availability information is captured.
  57     opt::Instruction* inst_;
  58
  59     // A cache to improve the efficiency of the [] operator. The [] operator
  60     // requires walking the instruction's dominator tree to find an instruction
  61     // at a particular index, which is a linear time operation. By inserting all
  62     // instructions that are traversed during this search into a cache, future
  63     // lookups will take constant time unless they require traversing the
  64     // dominator tree more deeply.
  65     mutable std::unordered_map<uint32_t, opt::Instruction*> index_cache;
  66   };
  67
  68   // Constructs availability instructions for |ir_context|, where instructions
  69   // are only available if they satisfy |predicate|.
  70   AvailableInstructions(
  71       opt::IRContext* ir_context,
  72       const std::function<bool(opt::IRContext*, opt::Instruction*)>& predicate);
  73
  74   // Yields instruction availability for |inst|.
  75   AvailableBeforeInstruction GetAvailableBeforeInstruction(
  76       opt::Instruction* inst) const;
  77
  78  private:
  79   // The module in which all instructions are contained.
  80   opt::IRContext* ir_context_;
  81
  82   // The global instructions that satisfy the predicate.
  83   std::vector<opt::Instruction*> available_globals_;
  84
  85   // Per function, the parameters that satisfy the predicate.
  86   std::unordered_map<opt::Function*, std::vector<opt::Instruction*>>
  87       available_params_;
  88
  89   // The number of instructions that satisfy the predicate and that are
  90   // available at the entry to a block. For the entry block of a function this
  91   // is the number of available globals + the number of available function
  92   // parameters. For any other block it is the number of available instructions
  93   // for the blocks immediate dominator + the number of instructions generated
  94   // by the immediate dominator.
  95   std::unordered_map<opt::BasicBlock*, uint32_t> num_available_at_block_entry_;
  96
  97   // For each block this records those instructions in the block that satisfy
  98   // the predicate.
  99   std::unordered_map<opt::BasicBlock*, std::vector<opt::Instruction*>>
 100       generated_by_block_;
 101
 102   // For each instruction this records how many instructions satisfying the
 103   // predicate are available before the instruction.
 104   std::unordered_map<opt::Instruction*, uint32_t>
 105       num_available_before_instruction_;
 106 };
 107
 108 }  // namespace fuzz
 109 }  // namespace spvtools
 110
 111 #endif  // SOURCE_FUZZ_AVAILABLE_INSTRUCTIONS_H_