1 // Copyright (c) 2020 Google LLC 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_OVERFLOW_ID_SOURCE_H_ 16 #define SOURCE_FUZZ_OVERFLOW_ID_SOURCE_H_ 17 18 #include <cstdint> 19 #include <unordered_set> 20 21 namespace spvtools { 22 namespace fuzz { 23 24 // An implementation of this interface can be used to provide fresh ids on 25 // demand when applying a transformation. 26 // 27 // During fuzzing this should never be required: a fuzzer pass should determine 28 // all the fresh ids it requires to apply a transformation. 29 // 30 // However, during shrinking we can have the situation where, after removing 31 // an early transformation, a later transformation needs more ids. 32 // 33 // As an example, suppose a SPIR-V function originally has this form: 34 // 35 // main() { 36 // stmt1; 37 // stmt2; 38 // stmt3; 39 // stmt4; 40 // } 41 // 42 // Now suppose two *outlining* transformations are applied. The first 43 // transformation, T1, outlines "stmt1; stmt2;" into a function foo, giving us: 44 // 45 // foo() { 46 // stmt1; 47 // stmt2; 48 // } 49 // 50 // main() { 51 // foo(); 52 // stmt3; 53 // stmt4; 54 // } 55 // 56 // The second transformation, T2, outlines "foo(); stmt3;" from main into a 57 // function bar, giving us: 58 // 59 // foo() { 60 // stmt1; 61 // stmt2; 62 // } 63 // 64 // bar() { 65 // foo(); 66 // stmt3; 67 // } 68 // 69 // main() { 70 // bar(); 71 // stmt4; 72 // } 73 // 74 // Suppose that T2 used a set of fresh ids, FRESH, in order to perform its 75 // outlining. 76 // 77 // Now suppose that during shrinking we remove T1, but still want to apply T2. 78 // The fresh ids used by T2 - FRESH - are sufficient to outline "foo(); stmt3;". 79 // However, because we did not apply T1, "foo();" does not exist and instead the 80 // task of T2 is to outline "stmt1; stmt2; stmt3;". The set FRESH contains 81 // *some* of the fresh ids required to do this (those for "stmt3;"), but not all 82 // of them (those for "stmt1; stmt2;" are missing). 83 // 84 // A source of overflow ids can be used to allow the shrinker to proceed 85 // nevertheless. 86 // 87 // It is desirable to use overflow ids only when needed. In our worked example, 88 // T2 should still use the ids from FRESH when handling "stmt3;", because later 89 // transformations might refer to those ids and will become inapplicable if 90 // overflow ids are used instead. 91 class OverflowIdSource { 92 public: 93 virtual ~OverflowIdSource(); 94 95 // Returns true if and only if this source is capable of providing overflow 96 // ids. 97 virtual bool HasOverflowIds() const = 0; 98 99 // Precondition: HasOverflowIds() must hold. Returns the next available 100 // overflow id. 101 virtual uint32_t GetNextOverflowId() = 0; 102 103 // Returns the set of overflow ids from this source that have been previously 104 // issued via calls to GetNextOverflowId(). 105 virtual const std::unordered_set<uint32_t>& GetIssuedOverflowIds() const = 0; 106 }; 107 108 } // namespace fuzz 109 } // namespace spvtools 110 111 #endif // SOURCE_FUZZ_OVERFLOW_ID_SOURCE_H_ 112