Add fuzzer pass to copy objects (#2853)
A new fuzzer pass that randomly introduces OpCopyObject instructions
that make copies of ids, and uses the fact manager to record the fact
that an id %id is synonymous with an id generated by an OpCopyObject
applied to %id. (A future pass will exploit such synonym facts.)
diff --git a/source/fuzz/CMakeLists.txt b/source/fuzz/CMakeLists.txt
index 7b5deb8..c0592b3 100644
--- a/source/fuzz/CMakeLists.txt
+++ b/source/fuzz/CMakeLists.txt
@@ -34,6 +34,7 @@
fuzzer_pass_add_dead_breaks.h
fuzzer_pass_add_dead_continues.h
fuzzer_pass_add_useful_constructs.h
+ fuzzer_pass_copy_objects.h
fuzzer_pass_obfuscate_constants.h
fuzzer_pass_permute_blocks.h
fuzzer_pass_split_blocks.h
@@ -69,6 +70,7 @@
fuzzer_pass_add_dead_breaks.cpp
fuzzer_pass_add_dead_continues.cpp
fuzzer_pass_add_useful_constructs.cpp
+ fuzzer_pass_copy_objects.cpp
fuzzer_pass_obfuscate_constants.cpp
fuzzer_pass_permute_blocks.cpp
fuzzer_pass_split_blocks.cpp
diff --git a/source/fuzz/fuzzer.cpp b/source/fuzz/fuzzer.cpp
index 89250a0..9d2a7c7 100644
--- a/source/fuzz/fuzzer.cpp
+++ b/source/fuzz/fuzzer.cpp
@@ -22,6 +22,7 @@
#include "source/fuzz/fuzzer_pass_add_dead_breaks.h"
#include "source/fuzz/fuzzer_pass_add_dead_continues.h"
#include "source/fuzz/fuzzer_pass_add_useful_constructs.h"
+#include "source/fuzz/fuzzer_pass_copy_objects.h"
#include "source/fuzz/fuzzer_pass_obfuscate_constants.h"
#include "source/fuzz/fuzzer_pass_permute_blocks.h"
#include "source/fuzz/fuzzer_pass_split_blocks.h"
@@ -107,6 +108,9 @@
.Apply();
// Apply some semantics-preserving passes.
+ FuzzerPassCopyObjects(ir_context.get(), &fact_manager, &fuzzer_context,
+ transformation_sequence_out)
+ .Apply();
FuzzerPassSplitBlocks(ir_context.get(), &fact_manager, &fuzzer_context,
transformation_sequence_out)
.Apply();
diff --git a/source/fuzz/fuzzer_context.cpp b/source/fuzz/fuzzer_context.cpp
index 59f8f32..e9398d5 100644
--- a/source/fuzz/fuzzer_context.cpp
+++ b/source/fuzz/fuzzer_context.cpp
@@ -26,6 +26,7 @@
const uint32_t kDefaultChanceOfAddingDeadBreak = 20;
const uint32_t kDefaultChanceOfAddingDeadContinue = 20;
+const uint32_t kDefaultChanceOfCopyingObject = 20;
const uint32_t kDefaultChanceOfMovingBlockDown = 25;
const uint32_t kDefaultChanceOfObfuscatingConstant = 20;
const uint32_t kDefaultChanceOfSplittingBlock = 20;
@@ -48,6 +49,7 @@
next_fresh_id_(min_fresh_id),
chance_of_adding_dead_break_(kDefaultChanceOfAddingDeadBreak),
chance_of_adding_dead_continue_(kDefaultChanceOfAddingDeadContinue),
+ chance_of_copying_object_(kDefaultChanceOfCopyingObject),
chance_of_moving_block_down_(kDefaultChanceOfMovingBlockDown),
chance_of_obfuscating_constant_(kDefaultChanceOfObfuscatingConstant),
chance_of_splitting_block_(kDefaultChanceOfSplittingBlock),
diff --git a/source/fuzz/fuzzer_context.h b/source/fuzz/fuzzer_context.h
index 588a460..ed6a355 100644
--- a/source/fuzz/fuzzer_context.h
+++ b/source/fuzz/fuzzer_context.h
@@ -61,6 +61,7 @@
uint32_t GetChanceOfAddingDeadContinue() {
return chance_of_adding_dead_continue_;
}
+ uint32_t GetChanceOfCopyingObject() { return chance_of_copying_object_; }
uint32_t GetChanceOfMovingBlockDown() { return chance_of_moving_block_down_; }
uint32_t GetChanceOfObfuscatingConstant() {
return chance_of_obfuscating_constant_;
@@ -83,6 +84,7 @@
// Keep them in alphabetical order.
uint32_t chance_of_adding_dead_break_;
uint32_t chance_of_adding_dead_continue_;
+ uint32_t chance_of_copying_object_;
uint32_t chance_of_moving_block_down_;
uint32_t chance_of_obfuscating_constant_;
uint32_t chance_of_splitting_block_;
diff --git a/source/fuzz/fuzzer_pass_copy_objects.cpp b/source/fuzz/fuzzer_pass_copy_objects.cpp
new file mode 100644
index 0000000..a1b118a
--- /dev/null
+++ b/source/fuzz/fuzzer_pass_copy_objects.cpp
@@ -0,0 +1,148 @@
+// Copyright (c) 2019 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/fuzzer_pass_copy_objects.h"
+
+#include "source/fuzz/transformation_copy_object.h"
+
+namespace spvtools {
+namespace fuzz {
+
+FuzzerPassCopyObjects::FuzzerPassCopyObjects(
+ opt::IRContext* ir_context, FactManager* fact_manager,
+ FuzzerContext* fuzzer_context,
+ protobufs::TransformationSequence* transformations)
+ : FuzzerPass(ir_context, fact_manager, fuzzer_context, transformations) {}
+
+FuzzerPassCopyObjects::~FuzzerPassCopyObjects() = default;
+
+void FuzzerPassCopyObjects::Apply() {
+ // Consider every block in every function.
+ for (auto& function : *GetIRContext()->module()) {
+ for (auto& block : function) {
+ // We now consider every instruction in the block, randomly deciding
+ // whether to add an object copy before the instruction.
+
+ // In order to insert an object copy instruction, we need to be able to
+ // identify the instruction a copy should be inserted before. We do this
+ // by tracking a base instruction, which must generate a result id, and an
+ // offset (to allow us to identify instructions that do not generate
+ // result ids).
+
+ // The initial base instruction is the block label.
+ uint32_t base = block.id();
+ uint32_t offset = 0;
+ // Consider every instruction in the block.
+ for (auto inst_it = block.begin(); inst_it != block.end(); ++inst_it) {
+ if (inst_it->HasResultId()) {
+ // In the case that the instruction has a result id, we use the
+ // instruction as its own base, with zero offset.
+ base = inst_it->result_id();
+ offset = 0;
+ } else {
+ // The instruction does not have a result id, so we need to identify
+ // it via the latest instruction that did have a result id (base), and
+ // an incremented offset.
+ offset++;
+ }
+
+ // Check whether it is legitimate to insert a copy before this
+ // instruction.
+ if (!TransformationCopyObject::CanInsertCopyBefore(inst_it)) {
+ continue;
+ }
+
+ // Randomly decide whether to try inserting an object copy here.
+ if (!GetFuzzerContext()->ChoosePercentage(
+ GetFuzzerContext()->GetChanceOfCopyingObject())) {
+ continue;
+ }
+
+ // Populate list of potential instructions that can be copied.
+ // TODO(afd) The following is (relatively) simple, but may end up being
+ // prohibitively inefficient, as it walks the whole dominator tree for
+ // every copy that is added.
+ std::vector<opt::Instruction*> copyable_instructions;
+
+ // Consider all global declarations
+ for (auto& global : GetIRContext()->module()->types_values()) {
+ if (TransformationCopyObject::IsCopyable(GetIRContext(), &global)) {
+ copyable_instructions.push_back(&global);
+ }
+ }
+
+ // Consider all previous instructions in this block
+ for (auto prev_inst_it = block.begin(); prev_inst_it != inst_it;
+ ++prev_inst_it) {
+ if (TransformationCopyObject::IsCopyable(GetIRContext(),
+ &*prev_inst_it)) {
+ copyable_instructions.push_back(&*prev_inst_it);
+ }
+ }
+
+ // Walk the dominator tree to consider all instructions from dominating
+ // blocks
+ auto dominator_analysis =
+ GetIRContext()->GetDominatorAnalysis(&function);
+ for (auto next_dominator =
+ dominator_analysis->ImmediateDominator(&block);
+ next_dominator != nullptr;
+ next_dominator =
+ dominator_analysis->ImmediateDominator(next_dominator)) {
+ for (auto& dominating_inst : *next_dominator) {
+ if (TransformationCopyObject::IsCopyable(GetIRContext(),
+ &dominating_inst)) {
+ copyable_instructions.push_back(&dominating_inst);
+ }
+ }
+ }
+
+ // At this point, |copyable_instructions| contains all the instructions
+ // we might think of copying.
+
+ if (!copyable_instructions.empty()) {
+ // Choose a copyable instruction at random, and create and apply an
+ // object copying transformation based on it.
+ uint32_t index =
+ GetFuzzerContext()->RandomIndex(copyable_instructions);
+ TransformationCopyObject transformation(
+ copyable_instructions[index]->result_id(), base, offset,
+ GetFuzzerContext()->GetFreshId());
+ assert(
+ transformation.IsApplicable(GetIRContext(), *GetFactManager()) &&
+ "This transformation should be applicable by construction.");
+ transformation.Apply(GetIRContext(), GetFactManager());
+ *GetTransformations()->add_transformation() =
+ transformation.ToMessage();
+
+ if (!inst_it->HasResultId()) {
+ // We have inserted a new instruction before the current
+ // instruction, and we are tracking the current id-less instruction
+ // via an offset (offset) from a previous instruction (base) that
+ // has an id. We increment |offset| to reflect the newly-inserted
+ // instruction.
+ //
+ // This is slightly preferable to the alternative of setting |base|
+ // to be the result id of the new instruction, since on replay we
+ // might end up eliminating this copy but keeping a subsequent copy.
+ offset++;
+ }
+ }
+ }
+ }
+ }
+}
+
+} // namespace fuzz
+} // namespace spvtools
diff --git a/source/fuzz/fuzzer_pass_copy_objects.h b/source/fuzz/fuzzer_pass_copy_objects.h
new file mode 100644
index 0000000..5419459
--- /dev/null
+++ b/source/fuzz/fuzzer_pass_copy_objects.h
@@ -0,0 +1,38 @@
+// Copyright (c) 2019 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.
+
+#ifndef SOURCE_FUZZ_FUZZER_PASS_COPY_OBJECTS_H_
+#define SOURCE_FUZZ_FUZZER_PASS_COPY_OBJECTS_H_
+
+#include "source/fuzz/fuzzer_pass.h"
+
+namespace spvtools {
+namespace fuzz {
+
+// A fuzzer pass for adding adding copies of objects to the module.
+class FuzzerPassCopyObjects : public FuzzerPass {
+ public:
+ FuzzerPassCopyObjects(opt::IRContext* ir_context, FactManager* fact_manager,
+ FuzzerContext* fuzzer_context,
+ protobufs::TransformationSequence* transformations);
+
+ ~FuzzerPassCopyObjects();
+
+ void Apply() override;
+};
+
+} // namespace fuzz
+} // namespace spvtools
+
+#endif // SOURCE_FUZZ_FUZZER_PASS_COPY_OBJECTS_H_
diff --git a/source/fuzz/transformation.cpp b/source/fuzz/transformation.cpp
index a252734..bf2cdcd 100644
--- a/source/fuzz/transformation.cpp
+++ b/source/fuzz/transformation.cpp
@@ -25,6 +25,7 @@
#include "transformation_add_type_float.h"
#include "transformation_add_type_int.h"
#include "transformation_add_type_pointer.h"
+#include "transformation_copy_object.h"
#include "transformation_move_block_down.h"
#include "transformation_replace_boolean_constant_with_constant_binary.h"
#include "transformation_replace_constant_with_uniform.h"
@@ -59,6 +60,8 @@
case protobufs::Transformation::TransformationCase::kAddTypePointer:
return MakeUnique<TransformationAddTypePointer>(
message.add_type_pointer());
+ case protobufs::Transformation::TransformationCase::kCopyObject:
+ return MakeUnique<TransformationCopyObject>(message.copy_object());
case protobufs::Transformation::TransformationCase::kMoveBlockDown:
return MakeUnique<TransformationMoveBlockDown>(message.move_block_down());
case protobufs::Transformation::TransformationCase::
@@ -71,13 +74,12 @@
message.replace_constant_with_uniform());
case protobufs::Transformation::TransformationCase::kSplitBlock:
return MakeUnique<TransformationSplitBlock>(message.split_block());
- default:
- assert(message.transformation_case() ==
- protobufs::Transformation::TRANSFORMATION_NOT_SET &&
- "Unhandled transformation type.");
+ case protobufs::Transformation::TRANSFORMATION_NOT_SET:
assert(false && "An unset transformation was encountered.");
return nullptr;
}
+ assert(false && "Should be unreachable as all cases must be handled above.");
+ return nullptr;
}
} // namespace fuzz
diff --git a/source/fuzz/transformation_copy_object.cpp b/source/fuzz/transformation_copy_object.cpp
index f9ead43..cfd97ae 100644
--- a/source/fuzz/transformation_copy_object.cpp
+++ b/source/fuzz/transformation_copy_object.cpp
@@ -46,18 +46,7 @@
if (!object_inst) {
return false;
}
- if (!object_inst->type_id()) {
- // We can only apply OpCopyObject to instructions that have types.
- return false;
- }
- if (!context->get_decoration_mgr()
- ->GetDecorationsFor(message_.object(), true)
- .empty()) {
- // We do not copy objects that have decorations: if the copy is not
- // decorated analogously, using the original object vs. its copy may not be
- // equivalent.
- // TODO(afd): it would be possible to make the copy but not add an id
- // synonym.
+ if (!IsCopyable(context, object_inst)) {
return false;
}
@@ -81,22 +70,11 @@
// The offset was inappropriate.
return false;
}
- if (insert_before->PreviousNode() &&
- (insert_before->PreviousNode()->opcode() == SpvOpLoopMerge ||
- insert_before->PreviousNode()->opcode() == SpvOpSelectionMerge)) {
- // We cannot insert a copy directly after a merge instruction.
+
+ if (!CanInsertCopyBefore(insert_before)) {
return false;
}
- if (insert_before->opcode() == SpvOpVariable) {
- // We cannot insert a copy directly before a variable; variables in a
- // function must be contiguous in the entry block.
- return false;
- }
- // We cannot insert a copy directly before OpPhi, because OpPhi instructions
- // need to be contiguous at the start of a block.
- if (insert_before->opcode() == SpvOpPhi) {
- return false;
- }
+
// |message_object| must be available at the point where we want to add the
// copy. It is available if it is at global scope (in which case it has no
// block), or if it dominates the point of insertion but is different from the
@@ -154,5 +132,43 @@
return result;
}
+bool TransformationCopyObject::IsCopyable(opt::IRContext* ir_context,
+ opt::Instruction* inst) {
+ if (!inst->HasResultId()) {
+ // We can only apply OpCopyObject to instructions that generate ids.
+ return false;
+ }
+ if (!inst->type_id()) {
+ // We can only apply OpCopyObject to instructions that have types.
+ return false;
+ }
+ // We do not copy objects that have decorations: if the copy is not
+ // decorated analogously, using the original object vs. its copy may not be
+ // equivalent.
+ // TODO(afd): it would be possible to make the copy but not add an id
+ // synonym.
+ return ir_context->get_decoration_mgr()
+ ->GetDecorationsFor(inst->result_id(), true)
+ .empty();
+}
+
+bool TransformationCopyObject::CanInsertCopyBefore(
+ const opt::BasicBlock::iterator& instruction_in_block) {
+ if (instruction_in_block->PreviousNode() &&
+ (instruction_in_block->PreviousNode()->opcode() == SpvOpLoopMerge ||
+ instruction_in_block->PreviousNode()->opcode() == SpvOpSelectionMerge)) {
+ // We cannot insert a copy directly after a merge instruction.
+ return false;
+ }
+ if (instruction_in_block->opcode() == SpvOpVariable) {
+ // We cannot insert a copy directly before a variable; variables in a
+ // function must be contiguous in the entry block.
+ return false;
+ }
+ // We cannot insert a copy directly before OpPhi, because OpPhi instructions
+ // need to be contiguous at the start of a block.
+ return instruction_in_block->opcode() != SpvOpPhi;
+}
+
} // namespace fuzz
} // namespace spvtools
diff --git a/source/fuzz/transformation_copy_object.h b/source/fuzz/transformation_copy_object.h
index 6ce72df..20e5874 100644
--- a/source/fuzz/transformation_copy_object.h
+++ b/source/fuzz/transformation_copy_object.h
@@ -28,8 +28,8 @@
explicit TransformationCopyObject(
const protobufs::TransformationCopyObject& message);
- TransformationCopyObject(uint32_t fresh_id, uint32_t object,
- uint32_t insert_after_id, uint32_t offset);
+ TransformationCopyObject(uint32_t object, uint32_t base_instruction_id,
+ uint32_t offset, uint32_t fresh_id);
// - |message_.fresh_id| must not be used by the module.
// - |message_.object| must be a result id that is a legitimate operand for
@@ -58,6 +58,14 @@
protobufs::Transformation ToMessage() const override;
+ // Determines whether it is OK to make a copy of |inst|.
+ static bool IsCopyable(opt::IRContext* ir_context, opt::Instruction* inst);
+
+ // Determines whether it is OK to insert a copy instruction before the given
+ // instruction.
+ static bool CanInsertCopyBefore(
+ const opt::BasicBlock::iterator& instruction_in_block);
+
private:
protobufs::TransformationCopyObject message_;
};
