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_
112