diff --git a/llvm/include/llvm/FuzzMutate/IRMutator.h b/llvm/include/llvm/FuzzMutate/IRMutator.h
--- a/llvm/include/llvm/FuzzMutate/IRMutator.h
+++ b/llvm/include/llvm/FuzzMutate/IRMutator.h
@@ -102,6 +102,17 @@
   void mutate(Instruction &Inst, RandomIRBuilder &IB) override;
 };
 
+class InstModificationIRStrategy : public IRMutationStrategy {
+public:
+  uint64_t getWeight(size_t CurrentSize, size_t MaxSize,
+                     uint64_t CurrentWeight) override {
+    return 4;
+  }
+
+  using IRMutationStrategy::mutate;
+  void mutate(Instruction &Inst, RandomIRBuilder &IB) override;
+};
+
 } // end llvm namespace
 
 #endif // LLVM_FUZZMUTATE_IRMUTATOR_H
diff --git a/llvm/lib/FuzzMutate/IRMutator.cpp b/llvm/lib/FuzzMutate/IRMutator.cpp
--- a/llvm/lib/FuzzMutate/IRMutator.cpp
+++ b/llvm/lib/FuzzMutate/IRMutator.cpp
@@ -197,3 +197,46 @@
   Inst.replaceAllUsesWith(RS.getSelection());
   Inst.eraseFromParent();
 }
+
+void InstModificationIRStrategy::mutate(Instruction &Inst,
+                                        RandomIRBuilder &IB) {
+  SmallVector<std::function<void()>, 8> Modifications;
+  CmpInst *CI = nullptr;
+  GetElementPtrInst *GEP = nullptr;
+  switch (Inst.getOpcode()) {
+  default:
+    break;
+  case Instruction::Add:
+  case Instruction::Mul:
+  case Instruction::Sub:
+  case Instruction::Shl:
+    Modifications.push_back([&Inst]() { Inst.setHasNoSignedWrap(true); }),
+        Modifications.push_back([&Inst]() { Inst.setHasNoSignedWrap(false); });
+    Modifications.push_back([&Inst]() { Inst.setHasNoUnsignedWrap(true); });
+    Modifications.push_back([&Inst]() { Inst.setHasNoUnsignedWrap(false); });
+
+    break;
+  case Instruction::ICmp:
+    CI = cast<ICmpInst>(&Inst);
+    Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_EQ); });
+    Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_NE); });
+    Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_UGT); });
+    Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_UGE); });
+    Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_ULT); });
+    Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_ULE); });
+    Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_SGT); });
+    Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_SGE); });
+    Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_SLT); });
+    Modifications.push_back([CI]() { CI->setPredicate(CmpInst::ICMP_SLE); });
+    break;
+  case Instruction::GetElementPtr:
+    GEP = cast<GetElementPtrInst>(&Inst);
+    Modifications.push_back([GEP]() { GEP->setIsInBounds(true); });
+    Modifications.push_back([GEP]() { GEP->setIsInBounds(false); });
+    break;
+  }
+
+  auto RS = makeSampler(IB.Rand, Modifications);
+  if (RS)
+    RS.getSelection()();
+}
diff --git a/llvm/tools/llvm-opt-fuzzer/llvm-opt-fuzzer.cpp b/llvm/tools/llvm-opt-fuzzer/llvm-opt-fuzzer.cpp
--- a/llvm/tools/llvm-opt-fuzzer/llvm-opt-fuzzer.cpp
+++ b/llvm/tools/llvm-opt-fuzzer/llvm-opt-fuzzer.cpp
@@ -51,6 +51,7 @@
           InjectorIRStrategy::getDefaultOps()));
   Strategies.push_back(
       std::make_unique<InstDeleterIRStrategy>());
+  Strategies.push_back(std::make_unique<InstModificationIRStrategy>());
 
   return std::make_unique<IRMutator>(std::move(Types), std::move(Strategies));
 }
diff --git a/llvm/unittests/FuzzMutate/StrategiesTest.cpp b/llvm/unittests/FuzzMutate/StrategiesTest.cpp
--- a/llvm/unittests/FuzzMutate/StrategiesTest.cpp
+++ b/llvm/unittests/FuzzMutate/StrategiesTest.cpp
@@ -49,6 +49,17 @@
   return std::make_unique<IRMutator>(std::move(Types), std::move(Strategies));
 }
 
+std::unique_ptr<IRMutator> createInstModifierMutator() {
+  std::vector<TypeGetter> Types{
+      Type::getInt1Ty,  Type::getInt8Ty,  Type::getInt16Ty, Type::getInt32Ty,
+      Type::getInt64Ty, Type::getFloatTy, Type::getDoubleTy};
+
+  std::vector<std::unique_ptr<IRMutationStrategy>> Strategies;
+  Strategies.push_back(std::make_unique<InstModificationIRStrategy>());
+
+  return std::make_unique<IRMutator>(std::move(Types), std::move(Strategies));
+}
+
 std::unique_ptr<Module> parseAssembly(
     const char *Assembly, LLVMContext &Context) {
 
@@ -135,4 +146,98 @@
   IterateOnSource(Source, *Mutator);
 }
 
+static void checkModifyNoUnsignedAndNoSignedWrap(StringRef Opc) {
+  LLVMContext Ctx;
+  std::string Source = std::string("\n\
+      define i32 @test(i32 %x) {\n\
+        %a = ") + Opc.str() +
+                       std::string(" i32 %x, 10\n\
+        ret i32 %a\n\
+      }");
+
+  auto Mutator = createInstModifierMutator();
+  ASSERT_TRUE(Mutator);
+
+  auto M = parseAssembly(Source.data(), Ctx);
+  auto &F = *M->begin();
+  auto *AddI = &*F.begin()->begin();
+  ASSERT_TRUE(M && !verifyModule(*M, &errs()));
+  bool FoundNUW = false;
+  bool FoundNSW = false;
+  for (int i = 0; i < 100; ++i) {
+    Mutator->mutateModule(*M, Seed + i, Source.size(), Source.size() + 100);
+    EXPECT_TRUE(!verifyModule(*M, &errs()));
+    FoundNUW |= AddI->hasNoUnsignedWrap();
+    FoundNSW |= AddI->hasNoSignedWrap();
+  }
+
+  // The mutator should have added nuw and nsw during some mutations.
+  EXPECT_TRUE(FoundNUW);
+  EXPECT_TRUE(FoundNSW);
+}
+TEST(InstModificationIRStrategyTest, Add) {
+  checkModifyNoUnsignedAndNoSignedWrap("add");
+}
+
+TEST(InstModificationIRStrategyTest, Sub) {
+  checkModifyNoUnsignedAndNoSignedWrap("sub");
+}
+
+TEST(InstModificationIRStrategyTest, Mul) {
+  checkModifyNoUnsignedAndNoSignedWrap("mul");
+}
+
+TEST(InstModificationIRStrategyTest, Shl) {
+  checkModifyNoUnsignedAndNoSignedWrap("shl");
+}
+
+TEST(InstModificationIRStrategyTest, ICmp) {
+  LLVMContext Ctx;
+  StringRef Source = "\n\
+      define i1 @test(i32 %x) {\n\
+        %a = icmp eq i32 %x, 10\n\
+        ret i1 %a\n\
+      }";
+
+  auto Mutator = createInstModifierMutator();
+  ASSERT_TRUE(Mutator);
+
+  auto M = parseAssembly(Source.data(), Ctx);
+  auto &F = *M->begin();
+  CmpInst *CI = cast<CmpInst>(&*F.begin()->begin());
+  ASSERT_TRUE(M && !verifyModule(*M, &errs()));
+  bool FoundNE = false;
+  for (int i = 0; i < 100; ++i) {
+    Mutator->mutateModule(*M, Seed + i, Source.size(), Source.size() + 100);
+    EXPECT_TRUE(!verifyModule(*M, &errs()));
+    FoundNE |= CI->getPredicate() == CmpInst::ICMP_NE;
+  }
+
+  EXPECT_TRUE(FoundNE);
+}
+
+TEST(InstModificationIRStrategyTest, GEP) {
+  LLVMContext Ctx;
+  StringRef Source = "\n\
+      define i32* @test(i32* %ptr) {\n\
+        %gep = getelementptr i32, i32* %ptr, i32 10\n\
+        ret i32* %gep\n\
+      }";
+
+  auto Mutator = createInstModifierMutator();
+  ASSERT_TRUE(Mutator);
+
+  auto M = parseAssembly(Source.data(), Ctx);
+  auto &F = *M->begin();
+  GetElementPtrInst *GEP = cast<GetElementPtrInst>(&*F.begin()->begin());
+  ASSERT_TRUE(M && !verifyModule(*M, &errs()));
+  bool FoundInbounds = false;
+  for (int i = 0; i < 100; ++i) {
+    Mutator->mutateModule(*M, Seed + i, Source.size(), Source.size() + 100);
+    EXPECT_TRUE(!verifyModule(*M, &errs()));
+    FoundInbounds |= GEP->isInBounds();
+  }
+
+  EXPECT_TRUE(FoundInbounds);
+}
 }