| // Copyright (c) 2020 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/fuzz/pass_management/repeated_pass_recommender_standard.h" |
| |
| #include <numeric> |
| |
| namespace spvtools { |
| namespace fuzz { |
| |
| RepeatedPassRecommenderStandard::RepeatedPassRecommenderStandard( |
| RepeatedPassInstances* pass_instances, FuzzerContext* fuzzer_context) |
| : pass_instances_(pass_instances), fuzzer_context_(fuzzer_context) {} |
| |
| RepeatedPassRecommenderStandard::~RepeatedPassRecommenderStandard() = default; |
| |
| std::vector<FuzzerPass*> |
| RepeatedPassRecommenderStandard::GetFuturePassRecommendations( |
| const FuzzerPass& pass) { |
| if (&pass == pass_instances_->GetAddAccessChains()) { |
| // - Adding access chains means there is more scope for loading and storing |
| // - It could be worth making more access chains from the recently-added |
| // access chains |
| return RandomOrderAndNonNull({pass_instances_->GetAddLoads(), |
| pass_instances_->GetAddStores(), |
| pass_instances_->GetAddAccessChains()}); |
| } |
| if (&pass == pass_instances_->GetAddBitInstructionSynonyms()) { |
| // - Adding bit instruction synonyms creates opportunities to apply synonyms |
| return RandomOrderAndNonNull({pass_instances_->GetApplyIdSynonyms()}); |
| } |
| if (&pass == pass_instances_->GetAddCompositeExtract()) { |
| // - This transformation can introduce synonyms to the fact manager. |
| return RandomOrderAndNonNull({pass_instances_->GetApplyIdSynonyms()}); |
| } |
| if (&pass == pass_instances_->GetAddCompositeInserts()) { |
| // - Having added inserts we will have more vectors, so there is scope for |
| // vector shuffling |
| // - Adding inserts creates synonyms, which we should try to use |
| // - Vector inserts can be made dynamic |
| return RandomOrderAndNonNull( |
| {pass_instances_->GetAddVectorShuffleInstructions(), |
| pass_instances_->GetApplyIdSynonyms(), |
| pass_instances_->GetMakeVectorOperationsDynamic()}); |
| } |
| if (&pass == pass_instances_->GetAddCompositeTypes()) { |
| // - More composite types gives more scope for constructing composites |
| return RandomOrderAndNonNull({pass_instances_->GetConstructComposites()}); |
| } |
| if (&pass == pass_instances_->GetAddCopyMemory()) { |
| // - Recently-added copy memories could be replace with load-store pairs |
| return RandomOrderAndNonNull( |
| {pass_instances_->GetReplaceCopyMemoriesWithLoadsStores()}); |
| } |
| if (&pass == pass_instances_->GetAddDeadBlocks()) { |
| // - Dead blocks are great for adding function calls |
| // - Dead blocks are also great for adding loads and stores |
| // - The guard associated with a dead block can be obfuscated |
| // - Branches from dead blocks may be replaced with exits |
| return RandomOrderAndNonNull( |
| {pass_instances_->GetAddFunctionCalls(), pass_instances_->GetAddLoads(), |
| pass_instances_->GetAddStores(), |
| pass_instances_->GetObfuscateConstants(), |
| pass_instances_->GetReplaceBranchesFromDeadBlocksWithExits()}); |
| } |
| if (&pass == pass_instances_->GetAddDeadBreaks()) { |
| // - The guard of the dead break is a good candidate for obfuscation |
| return RandomOrderAndNonNull({pass_instances_->GetObfuscateConstants()}); |
| } |
| if (&pass == pass_instances_->GetAddDeadContinues()) { |
| // - The guard of the dead continue is a good candidate for obfuscation |
| return RandomOrderAndNonNull({pass_instances_->GetObfuscateConstants()}); |
| } |
| if (&pass == pass_instances_->GetAddEquationInstructions()) { |
| // - Equation instructions can create synonyms, which we can apply |
| // - Equation instructions collaborate with one another to make synonyms, so |
| // having added some it is worth adding more |
| return RandomOrderAndNonNull( |
| {pass_instances_->GetApplyIdSynonyms(), |
| pass_instances_->GetAddEquationInstructions()}); |
| } |
| if (&pass == pass_instances_->GetAddFunctionCalls()) { |
| // - Called functions can be inlined |
| // - Irrelevant ids are created, so they can be replaced |
| return RandomOrderAndNonNull({pass_instances_->GetInlineFunctions(), |
| pass_instances_->GetReplaceIrrelevantIds()}); |
| } |
| if (&pass == pass_instances_->GetAddGlobalVariables()) { |
| // - New globals provide new possibilities for making access chains |
| // - We can load from and store to new globals |
| return RandomOrderAndNonNull({pass_instances_->GetAddAccessChains(), |
| pass_instances_->GetAddLoads(), |
| pass_instances_->GetAddStores()}); |
| } |
| if (&pass == pass_instances_->GetAddImageSampleUnusedComponents()) { |
| // - This introduces an unused component whose id is irrelevant and can be |
| // replaced |
| return RandomOrderAndNonNull({pass_instances_->GetReplaceIrrelevantIds()}); |
| } |
| if (&pass == pass_instances_->GetAddLoads()) { |
| // - Loads might end up with corresponding stores, so that pairs can be |
| // replaced with memory copies |
| return RandomOrderAndNonNull( |
| {pass_instances_->GetReplaceLoadsStoresWithCopyMemories()}); |
| } |
| if (&pass == pass_instances_->GetAddLocalVariables()) { |
| // - New locals provide new possibilities for making access chains |
| // - We can load from and store to new locals |
| return RandomOrderAndNonNull({pass_instances_->GetAddAccessChains(), |
| pass_instances_->GetAddLoads(), |
| pass_instances_->GetAddStores()}); |
| } |
| if (&pass == pass_instances_->GetAddLoopPreheaders()) { |
| // - The loop preheader provides more scope for duplicating regions and |
| // outlining functions. |
| return RandomOrderAndNonNull( |
| {pass_instances_->GetDuplicateRegionsWithSelections(), |
| pass_instances_->GetOutlineFunctions(), |
| pass_instances_->GetWrapRegionsInSelections()}); |
| } |
| if (&pass == pass_instances_->GetAddLoopsToCreateIntConstantSynonyms()) { |
| // - New synonyms can be applied |
| return RandomOrderAndNonNull({pass_instances_->GetApplyIdSynonyms()}); |
| } |
| if (&pass == pass_instances_->GetAddOpPhiSynonyms()) { |
| // - New synonyms can be applied |
| // - If OpPhi synonyms are introduced for blocks with dead predecessors, the |
| // values consumed from dead predecessors can be replaced |
| return RandomOrderAndNonNull( |
| {pass_instances_->GetApplyIdSynonyms(), |
| pass_instances_->GetReplaceOpPhiIdsFromDeadPredecessors()}); |
| } |
| if (&pass == pass_instances_->GetAddParameters()) { |
| // - We might be able to create interesting synonyms of new parameters. |
| // - This introduces irrelevant ids, which can be replaced |
| return RandomOrderAndNonNull({pass_instances_->GetAddSynonyms(), |
| pass_instances_->GetReplaceIrrelevantIds()}); |
| } |
| if (&pass == pass_instances_->GetAddRelaxedDecorations()) { |
| // - No obvious follow-on passes |
| return {}; |
| } |
| if (&pass == pass_instances_->GetAddStores()) { |
| // - Stores might end up with corresponding loads, so that pairs can be |
| // replaced with memory copies |
| return RandomOrderAndNonNull( |
| {pass_instances_->GetReplaceLoadsStoresWithCopyMemories()}); |
| } |
| if (&pass == pass_instances_->GetAddSynonyms()) { |
| // - New synonyms can be applied |
| // - Synonym instructions use constants, which can be obfuscated |
| // - Synonym instructions use irrelevant ids, which can be replaced |
| // - Synonym instructions introduce addition/subtraction, which can be |
| // replaced with carrying/extended versions |
| return RandomOrderAndNonNull( |
| {pass_instances_->GetApplyIdSynonyms(), |
| pass_instances_->GetObfuscateConstants(), |
| pass_instances_->GetReplaceAddsSubsMulsWithCarryingExtended(), |
| pass_instances_->GetReplaceIrrelevantIds()}); |
| } |
| if (&pass == pass_instances_->GetAddVectorShuffleInstructions()) { |
| // - Vector shuffles create synonyms that can be applied |
| // - TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/3806) Extract |
| // from composites. |
| return RandomOrderAndNonNull({pass_instances_->GetApplyIdSynonyms()}); |
| } |
| if (&pass == pass_instances_->GetApplyIdSynonyms()) { |
| // - No obvious follow-on passes |
| return {}; |
| } |
| if (&pass == pass_instances_->GetConstructComposites()) { |
| // - TODO(https://github.com/KhronosGroup/SPIRV-Tools/issues/3806): Extract |
| // from composites. |
| return RandomOrderAndNonNull({}); |
| } |
| if (&pass == pass_instances_->GetCopyObjects()) { |
| // - Object copies create synonyms that can be applied |
| // - OpCopyObject can be replaced with a store/load pair |
| return RandomOrderAndNonNull( |
| {pass_instances_->GetApplyIdSynonyms(), |
| pass_instances_->GetReplaceCopyObjectsWithStoresLoads()}); |
| } |
| if (&pass == pass_instances_->GetDonateModules()) { |
| // - New functions in the module can be called |
| // - Donated dead functions produce irrelevant ids, which can be replaced |
| // - Donated functions are good candidates for having their returns merged |
| // - Donated dead functions may allow branches to be replaced with exits |
| return RandomOrderAndNonNull( |
| {pass_instances_->GetAddFunctionCalls(), |
| pass_instances_->GetReplaceIrrelevantIds(), |
| pass_instances_->GetMergeFunctionReturns(), |
| pass_instances_->GetReplaceBranchesFromDeadBlocksWithExits()}); |
| } |
| if (&pass == pass_instances_->GetDuplicateRegionsWithSelections()) { |
| // - Parts of duplicated regions can be outlined |
| return RandomOrderAndNonNull({pass_instances_->GetOutlineFunctions()}); |
| } |
| if (&pass == pass_instances_->GetExpandVectorReductions()) { |
| // - Adding OpAny and OpAll synonyms creates opportunities to apply synonyms |
| return RandomOrderAndNonNull({pass_instances_->GetApplyIdSynonyms()}); |
| } |
| if (&pass == pass_instances_->GetFlattenConditionalBranches()) { |
| // - Parts of flattened selections can be outlined |
| // - The flattening transformation introduces constants and irrelevant ids |
| // for enclosing hard-to-flatten operations; these can be obfuscated or |
| // replaced |
| return RandomOrderAndNonNull({pass_instances_->GetObfuscateConstants(), |
| pass_instances_->GetOutlineFunctions(), |
| pass_instances_->GetReplaceIrrelevantIds()}); |
| } |
| if (&pass == pass_instances_->GetInlineFunctions()) { |
| // - Parts of inlined functions can be outlined again |
| return RandomOrderAndNonNull({pass_instances_->GetOutlineFunctions()}); |
| } |
| if (&pass == pass_instances_->GetInvertComparisonOperators()) { |
| // - No obvious follow-on passes |
| return {}; |
| } |
| if (&pass == pass_instances_->GetMakeVectorOperationsDynamic()) { |
| // - No obvious follow-on passes |
| return {}; |
| } |
| if (&pass == pass_instances_->GetMergeBlocks()) { |
| // - Having merged some blocks it may be interesting to split them in a |
| // different way |
| return RandomOrderAndNonNull({pass_instances_->GetSplitBlocks()}); |
| } |
| if (&pass == pass_instances_->GetMergeFunctionReturns()) { |
| // - Functions without early returns are more likely to be able to be |
| // inlined. |
| return RandomOrderAndNonNull({pass_instances_->GetInlineFunctions()}); |
| } |
| if (&pass == pass_instances_->GetMutatePointers()) { |
| // - This creates irrelevant ids, which can be replaced |
| return RandomOrderAndNonNull({pass_instances_->GetReplaceIrrelevantIds()}); |
| } |
| if (&pass == pass_instances_->GetObfuscateConstants()) { |
| // - No obvious follow-on passes |
| return {}; |
| } |
| if (&pass == pass_instances_->GetOutlineFunctions()) { |
| // - This creates more functions, which can be called |
| // - Inlining the function for the region that was outlined might also be |
| // fruitful; it will be inlined in a different form |
| return RandomOrderAndNonNull({pass_instances_->GetAddFunctionCalls(), |
| pass_instances_->GetInlineFunctions()}); |
| } |
| if (&pass == pass_instances_->GetPermuteBlocks()) { |
| // No obvious follow-on passes |
| return {}; |
| } |
| if (&pass == pass_instances_->GetPermuteFunctionParameters()) { |
| // No obvious follow-on passes |
| return {}; |
| } |
| if (&pass == pass_instances_->GetPermuteInstructions()) { |
| // No obvious follow-on passes |
| return {}; |
| } |
| if (&pass == pass_instances_->GetPropagateInstructionsDown()) { |
| // - This fuzzer pass might create new synonyms that can later be applied. |
| // - This fuzzer pass might create irrelevant ids that can later be |
| // replaced. |
| return RandomOrderAndNonNull({pass_instances_->GetApplyIdSynonyms(), |
| pass_instances_->GetReplaceIrrelevantIds()}); |
| } |
| if (&pass == pass_instances_->GetPropagateInstructionsUp()) { |
| // No obvious follow-on passes |
| return {}; |
| } |
| if (&pass == pass_instances_->GetPushIdsThroughVariables()) { |
| // - This pass creates synonyms, so it is worth applying them |
| return RandomOrderAndNonNull({pass_instances_->GetApplyIdSynonyms()}); |
| } |
| if (&pass == pass_instances_->GetReplaceAddsSubsMulsWithCarryingExtended()) { |
| // No obvious follow-on passes |
| return {}; |
| } |
| if (&pass == pass_instances_->GetReplaceBranchesFromDeadBlocksWithExits()) { |
| // - Changing a branch to OpReturnValue introduces an irrelevant id, which |
| // can be replaced |
| return RandomOrderAndNonNull({pass_instances_->GetReplaceIrrelevantIds()}); |
| } |
| if (&pass == pass_instances_->GetReplaceCopyMemoriesWithLoadsStores()) { |
| // No obvious follow-on passes |
| return {}; |
| } |
| if (&pass == pass_instances_->GetReplaceCopyObjectsWithStoresLoads()) { |
| // - We may end up with load/store pairs that could be used to create memory |
| // copies |
| return RandomOrderAndNonNull( |
| {pass_instances_->GetReplaceLoadsStoresWithCopyMemories()}); |
| } |
| if (&pass == pass_instances_->GetReplaceIrrelevantIds()) { |
| // No obvious follow-on passes |
| return {}; |
| } |
| if (&pass == pass_instances_->GetReplaceLinearAlgebraInstructions()) { |
| // No obvious follow-on passes |
| return {}; |
| } |
| if (&pass == pass_instances_->GetReplaceLoadsStoresWithCopyMemories()) { |
| // No obvious follow-on passes |
| return {}; |
| } |
| if (&pass == pass_instances_->GetReplaceOpPhiIdsFromDeadPredecessors()) { |
| // No obvious follow-on passes |
| return {}; |
| } |
| if (&pass == pass_instances_->GetReplaceOpSelectsWithConditionalBranches()) { |
| // No obvious follow-on passes |
| return {}; |
| } |
| if (&pass == pass_instances_->GetReplaceParameterWithGlobal()) { |
| // No obvious follow-on passes |
| return {}; |
| } |
| if (&pass == pass_instances_->GetReplaceParamsWithStruct()) { |
| // No obvious follow-on passes |
| return {}; |
| } |
| if (&pass == pass_instances_->GetSplitBlocks()) { |
| // - More blocks means more chances for adding dead breaks/continues, and |
| // for adding dead blocks |
| return RandomOrderAndNonNull({pass_instances_->GetAddDeadBreaks(), |
| pass_instances_->GetAddDeadContinues(), |
| pass_instances_->GetAddDeadBlocks()}); |
| } |
| if (&pass == pass_instances_->GetSwapBranchConditionalOperands()) { |
| // No obvious follow-on passes |
| return {}; |
| } |
| if (&pass == pass_instances_->GetWrapRegionsInSelections()) { |
| // - This pass uses an irrelevant boolean constant - we can replace it with |
| // something more interesting. |
| // - We can obfuscate that very constant as well. |
| // - We can flatten created selection construct. |
| return RandomOrderAndNonNull( |
| {pass_instances_->GetObfuscateConstants(), |
| pass_instances_->GetReplaceIrrelevantIds(), |
| pass_instances_->GetFlattenConditionalBranches()}); |
| } |
| if (&pass == pass_instances_->GetWrapVectorSynonym()) { |
| // This transformation introduces synonym facts and irrelevant ids. |
| return RandomOrderAndNonNull({pass_instances_->GetApplyIdSynonyms(), |
| pass_instances_->GetReplaceIrrelevantIds()}); |
| } |
| |
| assert(false && "Unreachable: every fuzzer pass should be dealt with."); |
| return {}; |
| } |
| |
| std::vector<FuzzerPass*> RepeatedPassRecommenderStandard::RandomOrderAndNonNull( |
| const std::vector<FuzzerPass*>& passes) { |
| std::vector<uint32_t> indices(passes.size()); |
| std::iota(indices.begin(), indices.end(), 0); |
| std::vector<FuzzerPass*> result; |
| while (!indices.empty()) { |
| FuzzerPass* maybe_pass = |
| passes[fuzzer_context_->RemoveAtRandomIndex(&indices)]; |
| if (maybe_pass != nullptr && |
| fuzzer_context_->ChoosePercentage( |
| fuzzer_context_ |
| ->GetChanceOfAcceptingRepeatedPassRecommendation())) { |
| result.push_back(maybe_pass); |
| } |
| } |
| return result; |
| } |
| |
| } // namespace fuzz |
| } // namespace spvtools |
