source/fuzz/transformation_replace_boolean_constant_with_constant_binary.cpp

   1 // Copyright (c) 2019 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 #include "source/fuzz/transformation_replace_boolean_constant_with_constant_binary.h"
  16
  17 #include <cmath>
  18
  19 #include "source/fuzz/fuzzer_util.h"
  20 #include "source/fuzz/id_use_descriptor.h"
  21
  22 namespace spvtools {
  23 namespace fuzz {
  24
  25 namespace {
  26
  27 // Given floating-point values |lhs| and |rhs|, and a floating-point binary
  28 // operator |binop|, returns true if it is certain that 'lhs binop rhs'
  29 // evaluates to |required_value|.
  30 template <typename T>
  31 bool float_binop_evaluates_to(T lhs, T rhs, spv::Op binop,
  32                               bool required_value) {
  33   // Infinity and NaN values are conservatively treated as out of scope.
  34   if (!std::isfinite(lhs) || !std::isfinite(rhs)) {
  35     return false;
  36   }
  37   bool binop_result;
  38   // The following captures the binary operators that spirv-fuzz can actually
  39   // generate when turning a boolean constant into a binary expression.
  40   switch (binop) {
  41     case spv::Op::OpFOrdGreaterThanEqual:
  42     case spv::Op::OpFUnordGreaterThanEqual:
  43       binop_result = (lhs >= rhs);
  44       break;
  45     case spv::Op::OpFOrdGreaterThan:
  46     case spv::Op::OpFUnordGreaterThan:
  47       binop_result = (lhs > rhs);
  48       break;
  49     case spv::Op::OpFOrdLessThanEqual:
  50     case spv::Op::OpFUnordLessThanEqual:
  51       binop_result = (lhs <= rhs);
  52       break;
  53     case spv::Op::OpFOrdLessThan:
  54     case spv::Op::OpFUnordLessThan:
  55       binop_result = (lhs < rhs);
  56       break;
  57     default:
  58       return false;
  59   }
  60   return binop_result == required_value;
  61 }
  62
  63 // Analogous to 'float_binop_evaluates_to', but for signed int values.
  64 template <typename T>
  65 bool signed_int_binop_evaluates_to(T lhs, T rhs, spv::Op binop,
  66                                    bool required_value) {
  67   bool binop_result;
  68   switch (binop) {
  69     case spv::Op::OpSGreaterThanEqual:
  70       binop_result = (lhs >= rhs);
  71       break;
  72     case spv::Op::OpSGreaterThan:
  73       binop_result = (lhs > rhs);
  74       break;
  75     case spv::Op::OpSLessThanEqual:
  76       binop_result = (lhs <= rhs);
  77       break;
  78     case spv::Op::OpSLessThan:
  79       binop_result = (lhs < rhs);
  80       break;
  81     default:
  82       return false;
  83   }
  84   return binop_result == required_value;
  85 }
  86
  87 // Analogous to 'float_binop_evaluates_to', but for unsigned int values.
  88 template <typename T>
  89 bool unsigned_int_binop_evaluates_to(T lhs, T rhs, spv::Op binop,
  90                                      bool required_value) {
  91   bool binop_result;
  92   switch (binop) {
  93     case spv::Op::OpUGreaterThanEqual:
  94       binop_result = (lhs >= rhs);
  95       break;
  96     case spv::Op::OpUGreaterThan:
  97       binop_result = (lhs > rhs);
  98       break;
  99     case spv::Op::OpULessThanEqual:
 100       binop_result = (lhs <= rhs);
 101       break;
 102     case spv::Op::OpULessThan:
 103       binop_result = (lhs < rhs);
 104       break;
 105     default:
 106       return false;
 107   }
 108   return binop_result == required_value;
 109 }
 110
 111 }  // namespace
 112
 113 TransformationReplaceBooleanConstantWithConstantBinary::
 114     TransformationReplaceBooleanConstantWithConstantBinary(
 115         protobufs::TransformationReplaceBooleanConstantWithConstantBinary
 116             message)
 117     : message_(std::move(message)) {}
 118
 119 TransformationReplaceBooleanConstantWithConstantBinary::
 120     TransformationReplaceBooleanConstantWithConstantBinary(
 121         const protobufs::IdUseDescriptor& id_use_descriptor, uint32_t lhs_id,
 122         uint32_t rhs_id, spv::Op comparison_opcode,
 123         uint32_t fresh_id_for_binary_operation) {
 124   *message_.mutable_id_use_descriptor() = id_use_descriptor;
 125   message_.set_lhs_id(lhs_id);
 126   message_.set_rhs_id(rhs_id);
 127   message_.set_opcode(uint32_t(comparison_opcode));
 128   message_.set_fresh_id_for_binary_operation(fresh_id_for_binary_operation);
 129 }
 130
 131 bool TransformationReplaceBooleanConstantWithConstantBinary::IsApplicable(
 132     opt::IRContext* ir_context, const TransformationContext& /*unused*/) const {
 133   // The id for the binary result must be fresh
 134   if (!fuzzerutil::IsFreshId(ir_context,
 135                              message_.fresh_id_for_binary_operation())) {
 136     return false;
 137   }
 138
 139   // The used id must be for a boolean constant
 140   auto boolean_constant = ir_context->get_def_use_mgr()->GetDef(
 141       message_.id_use_descriptor().id_of_interest());
 142   if (!boolean_constant) {
 143     return false;
 144   }
 145   if (!(boolean_constant->opcode() == spv::Op::OpConstantFalse ||
 146         boolean_constant->opcode() == spv::Op::OpConstantTrue)) {
 147     return false;
 148   }
 149
 150   // The left-hand-side id must correspond to a constant instruction.
 151   auto lhs_constant_inst =
 152       ir_context->get_def_use_mgr()->GetDef(message_.lhs_id());
 153   if (!lhs_constant_inst) {
 154     return false;
 155   }
 156   if (lhs_constant_inst->opcode() != spv::Op::OpConstant) {
 157     return false;
 158   }
 159
 160   // The right-hand-side id must correspond to a constant instruction.
 161   auto rhs_constant_inst =
 162       ir_context->get_def_use_mgr()->GetDef(message_.rhs_id());
 163   if (!rhs_constant_inst) {
 164     return false;
 165   }
 166   if (rhs_constant_inst->opcode() != spv::Op::OpConstant) {
 167     return false;
 168   }
 169
 170   // The left- and right-hand side instructions must have the same type.
 171   if (lhs_constant_inst->type_id() != rhs_constant_inst->type_id()) {
 172     return false;
 173   }
 174
 175   // The expression 'LHS opcode RHS' must evaluate to the boolean constant.
 176   auto lhs_constant =
 177       ir_context->get_constant_mgr()->FindDeclaredConstant(message_.lhs_id());
 178   auto rhs_constant =
 179       ir_context->get_constant_mgr()->FindDeclaredConstant(message_.rhs_id());
 180   bool expected_result =
 181       (boolean_constant->opcode() == spv::Op::OpConstantTrue);
 182
 183   const auto binary_opcode = static_cast<spv::Op>(message_.opcode());
 184
 185   // We consider the floating point, signed and unsigned integer cases
 186   // separately.  In each case the logic is very similar.
 187   if (lhs_constant->AsFloatConstant()) {
 188     assert(rhs_constant->AsFloatConstant() &&
 189            "Both constants should be of the same type.");
 190     if (lhs_constant->type()->AsFloat()->width() == 32) {
 191       if (!float_binop_evaluates_to(lhs_constant->GetFloat(),
 192                                     rhs_constant->GetFloat(), binary_opcode,
 193                                     expected_result)) {
 194         return false;
 195       }
 196     } else {
 197       assert(lhs_constant->type()->AsFloat()->width() == 64);
 198       if (!float_binop_evaluates_to(lhs_constant->GetDouble(),
 199                                     rhs_constant->GetDouble(), binary_opcode,
 200                                     expected_result)) {
 201         return false;
 202       }
 203     }
 204   } else {
 205     assert(lhs_constant->AsIntConstant() && "Constants should be in or float.");
 206     assert(rhs_constant->AsIntConstant() &&
 207            "Both constants should be of the same type.");
 208     if (lhs_constant->type()->AsInteger()->IsSigned()) {
 209       if (lhs_constant->type()->AsInteger()->width() == 32) {
 210         if (!signed_int_binop_evaluates_to(lhs_constant->GetS32(),
 211                                            rhs_constant->GetS32(),
 212                                            binary_opcode, expected_result)) {
 213           return false;
 214         }
 215       } else {
 216         assert(lhs_constant->type()->AsInteger()->width() == 64);
 217         if (!signed_int_binop_evaluates_to(lhs_constant->GetS64(),
 218                                            rhs_constant->GetS64(),
 219                                            binary_opcode, expected_result)) {
 220           return false;
 221         }
 222       }
 223     } else {
 224       if (lhs_constant->type()->AsInteger()->width() == 32) {
 225         if (!unsigned_int_binop_evaluates_to(lhs_constant->GetU32(),
 226                                              rhs_constant->GetU32(),
 227                                              binary_opcode, expected_result)) {
 228           return false;
 229         }
 230       } else {
 231         assert(lhs_constant->type()->AsInteger()->width() == 64);
 232         if (!unsigned_int_binop_evaluates_to(lhs_constant->GetU64(),
 233                                              rhs_constant->GetU64(),
 234                                              binary_opcode, expected_result)) {
 235           return false;
 236         }
 237       }
 238     }
 239   }
 240
 241   // The id use descriptor must identify some instruction
 242   auto instruction =
 243       FindInstructionContainingUse(message_.id_use_descriptor(), ir_context);
 244   if (instruction == nullptr) {
 245     return false;
 246   }
 247
 248   // The instruction must not be an OpVariable, because (a) we cannot insert
 249   // a binary operator before an OpVariable, but in any case (b) the
 250   // constant we would be replacing is the initializer constant of the
 251   // OpVariable, and this cannot be the result of a binary operation.
 252   if (instruction->opcode() == spv::Op::OpVariable) {
 253     return false;
 254   }
 255
 256   return true;
 257 }
 258
 259 void TransformationReplaceBooleanConstantWithConstantBinary::Apply(
 260     opt::IRContext* ir_context,
 261     TransformationContext* transformation_context) const {
 262   ApplyWithResult(ir_context, transformation_context);
 263 }
 264
 265 opt::Instruction*
 266 TransformationReplaceBooleanConstantWithConstantBinary::ApplyWithResult(
 267     opt::IRContext* ir_context, TransformationContext* /*unused*/) const {
 268   opt::analysis::Bool bool_type;
 269   opt::Instruction::OperandList operands = {
 270       {SPV_OPERAND_TYPE_ID, {message_.lhs_id()}},
 271       {SPV_OPERAND_TYPE_ID, {message_.rhs_id()}}};
 272   auto binary_instruction = MakeUnique<opt::Instruction>(
 273       ir_context, static_cast<spv::Op>(message_.opcode()),
 274       ir_context->get_type_mgr()->GetId(&bool_type),
 275       message_.fresh_id_for_binary_operation(), operands);
 276   opt::Instruction* result = binary_instruction.get();
 277   auto instruction_containing_constant_use =
 278       FindInstructionContainingUse(message_.id_use_descriptor(), ir_context);
 279   auto instruction_before_which_to_insert = instruction_containing_constant_use;
 280
 281   // If |instruction_before_which_to_insert| is an OpPhi instruction,
 282   // then |binary_instruction| will be inserted into the parent block associated
 283   // with the OpPhi variable operand.
 284   if (instruction_containing_constant_use->opcode() == spv::Op::OpPhi) {
 285     instruction_before_which_to_insert =
 286         ir_context->cfg()
 287             ->block(instruction_containing_constant_use->GetSingleWordInOperand(
 288                 message_.id_use_descriptor().in_operand_index() + 1))
 289             ->terminator();
 290   }
 291
 292   // We want to insert the new instruction before the instruction that contains
 293   // the use of the boolean, but we need to go backwards one more instruction if
 294   // the using instruction is preceded by a merge instruction.
 295   {
 296     opt::Instruction* previous_node =
 297         instruction_before_which_to_insert->PreviousNode();
 298     if (previous_node &&
 299         (previous_node->opcode() == spv::Op::OpLoopMerge ||
 300          previous_node->opcode() == spv::Op::OpSelectionMerge)) {
 301       instruction_before_which_to_insert = previous_node;
 302     }
 303   }
 304
 305   instruction_before_which_to_insert->InsertBefore(
 306       std::move(binary_instruction));
 307   instruction_containing_constant_use->SetInOperand(
 308       message_.id_use_descriptor().in_operand_index(),
 309       {message_.fresh_id_for_binary_operation()});
 310   fuzzerutil::UpdateModuleIdBound(ir_context,
 311                                   message_.fresh_id_for_binary_operation());
 312   ir_context->InvalidateAnalysesExceptFor(
 313       opt::IRContext::Analysis::kAnalysisNone);
 314   return result;
 315 }
 316
 317 protobufs::Transformation
 318 TransformationReplaceBooleanConstantWithConstantBinary::ToMessage() const {
 319   protobufs::Transformation result;
 320   *result.mutable_replace_boolean_constant_with_constant_binary() = message_;
 321   return result;
 322 }
 323
 324 std::unordered_set<uint32_t>
 325 TransformationReplaceBooleanConstantWithConstantBinary::GetFreshIds() const {
 326   return {message_.fresh_id_for_binary_operation()};
 327 }
 328
 329 }  // namespace fuzz
 330 }  // namespace spvtools