[FuzzMutate] New InsertPHINode strategy.

[Peter]

Summary

PHI Node can't be modeled like other instructions since its operand
number depends on predecessors. So we have a stand alone strategy for it.

Signed-off-by: Peter Rong <[e-mail]>

[Peter]

code style change

[arsenm]

llvm/unittests/FuzzMutate/StrategiesTest.cpp

350

Probably should be assert_false. Otherwise you're proceeding to mutate an invalid module

[Peter]

use ASSERT to abort failed test immediately.

[arsenm]

llvm/lib/FuzzMutate/IRMutator.cpp

310

s/Prev/Pred

314–315

If a predecessor block branches to the same block multiple times (e.g. it's the target of multiple switch cases), the same incoming value needs to appear for each instance. Can you add such a case to the test?

[Peter]

bug fix. Should have same value for incoming edges from the same block.
Using DenseMap to keep track of the value used for each incoming edge instead of SmallVector
Add a unit test to reflect this change.

llvm/include/llvm/FuzzMutate/IRMutator.h

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;
 };
 
+/// Strategy to insert PHI Nodes at the head of each basic block.
+class InsertPHIStrategy : public IRMutationStrategy {
+public:
+  uint64_t getWeight(size_t CurrentSize, size_t MaxSize,
+                     uint64_t CurrentWeight) override {
+    return 2;
+  }
+
+  void mutate(BasicBlock &BB, RandomIRBuilder &IB) override;
+};
+
 /// Strategy to select a random instruction and add a new sink (user) to it to
 /// increate data dependency.
 class SinkInstructionStrategy : public IRMutationStrategy {
 public:
   uint64_t getWeight(size_t CurrentSize, size_t MaxSize,
                      uint64_t CurrentWeight) override {
     return 2;
   }

llvm/include/llvm/FuzzMutate/RandomIRBuilder.h

struct RandomIRBuilder {
   /// \c BB. This may also create some new instruction in \c BB and use that.
   void connectToSink(BasicBlock &BB, ArrayRef<Instruction *> Insts, Value *V);
   /// Create a user for \c V in \c BB.
   void newSink(BasicBlock &BB, ArrayRef<Instruction *> Insts, Value *V);
   Value *findPointer(BasicBlock &BB, ArrayRef<Instruction *> Insts,
                      ArrayRef<Value *> Srcs, fuzzerop::SourcePred Pred);
   Type *chooseType(LLVMContext &Context, ArrayRef<Value *> Srcs,
                    fuzzerop::SourcePred Pred);
+  /// Return a uniformly choosen type from \c AllowedTypes
+  Type *randomType();
 };
 
 } // namespace llvm
 
 #endif // LLVM_FUZZMUTATE_RANDOMIRBUILDER_H

llvm/lib/FuzzMutate/IRMutator.cpp

if (ShuffleItems != NoneItem) {
     });
   }
 
   auto RS = makeSampler(IB.Rand, Modifications);
   if (RS)
     RS.getSelection()();
 }
 
+void InsertPHIStrategy::mutate(BasicBlock &BB, RandomIRBuilder &IB) {
+  // Can't insert PHI node to entry node.
+  if (&BB == &BB.getParent()->getEntryBlock())
+    return;
+  Type *Ty = IB.randomType();
+  PHINode *PHI = PHINode::Create(Ty, llvm::pred_size(&BB), "", &BB.front());
+
+  // Use a map to make sure the same incoming basic block has the same value.
+  DenseMap<BasicBlock *, Value *> IncomingValues;
+  for (BasicBlock *Pred : predecessors(&BB)) {
+    Value *Src = IncomingValues[Pred];
+    // If `Pred` is not in the map yet, we'll get a nullptr.
+    if (!Src) {
+      SmallVector<Instruction *, 32> Insts;
+      for (auto I = Pred->begin(); I != Pred->end(); ++I)
+        Insts.push_back(&*I);
+      // There is no need to inform IB what previously used values are if we are
+      // using `onlyType`
+      Src = IB.findOrCreateSource(*Pred, Insts, {}, fuzzerop::onlyType(Ty));
+      IncomingValues[Pred] = Src;
+    }
+    PHI->addIncoming(Src, Pred);
+  }
+  SmallVector<Instruction *, 32> InstsAfter;
+  for (auto I = BB.getFirstInsertionPt(), E = BB.end(); I != E; ++I)
+    InstsAfter.push_back(&*I);
+  IB.connectToSink(BB, InstsAfter, PHI);
+}
+
 void SinkInstructionStrategy::mutate(Function &F, RandomIRBuilder &IB) {
   for (BasicBlock &BB : F) {
     this->mutate(BB, IB);
   }
 }
 void SinkInstructionStrategy::mutate(BasicBlock &BB, RandomIRBuilder &IB) {
   SmallVector<Instruction *, 32> Insts;
   for (auto I = BB.getFirstInsertionPt(), E = BB.end(); I != E; ++I)

llvm/lib/FuzzMutate/RandomIRBuilder.cpp

if (auto *PtrTy = dyn_cast<PointerType>(Inst->getType())) {
       return Pred.matches(Srcs, UndefValue::get(ElemTy));
     }
     return false;
   };
   if (auto RS = makeSampler(Rand, make_filter_range(Insts, IsMatchingPtr)))
     return RS.getSelection();
   return nullptr;
 }
+
+Type *RandomIRBuilder::randomType() {
+  uint64_t TyIdx = uniform<uint64_t>(Rand, 0, KnownTypes.size() - 1);
+  return KnownTypes[TyIdx];
+}

llvm/unittests/FuzzMutate/StrategiesTest.cpp

 //===- InjectorIRStrategyTest.cpp - Tests for injector strategy -----------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/AsmParser/Parser.h"
 #include "llvm/AsmParser/SlotMapping.h"
 #include "llvm/FuzzMutate/IRMutator.h"
 #include "llvm/FuzzMutate/Operations.h"
+#include "llvm/FuzzMutate/RandomIRBuilder.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/Verifier.h"
 #include "llvm/Support/SourceMgr.h"
 #include <random>
 
 #include "gtest/gtest.h"
TEST(InstModificationIRStrategyTest, DidntShuffleFRem) {
   StringRef Source = "\n\
       define <2 x double> @test(<2 x double> %0) {\n\
         %div = frem <2 x double> <double 0.0, double 0.0>, %0\n\
         ret <2 x double> %div\n\
       }";
   VerfyDivDidntShuffle(Source);
 }
 
+TEST(InsertPHIStrategy, PHI) {
+  LLVMContext Ctx;
+  StringRef Source = "\n\
+        define void @test(i1 %C1, i1 %C2, i32 %I, double %FP) { \n\
+        Entry:  \n\
+          %C = and i1 %C1, %C2 \n\
+          br i1 %C, label %LoopHead, label %Exit \n\
+        LoopHead: ; pred Entry, LoopBody \n\
+          switch i32 %I, label %Default [ \n\
+              i32 1, label %OnOne  \n\
+              i32 2, label %OnTwo \n\
+              i32 3, label %OnThree \n\
+          ] \n\
+        Default:  \n\
+          br label %LoopBody \n\
+        OnOne: ; pred LoopHead \n\
+          %DFP = fmul double %FP, 2.0 \n\
+          %OnOneCond = fcmp ogt double %DFP, %FP \n\
+          br i1 %OnOneCond, label %LoopBody, label %Exit \n\
+        OnTwo: ; pred Entry \n\
+          br i1 %C1, label %OnThree, label %LoopBody \n\
+        OnThree: ; pred Entry, OnTwo, OnThree \n\
+          br i1 %C2, label %OnThree, label %LoopBody \n\
+        LoopBody: ; pred Default, OnOne, OnTwo, OnThree \n\
+          br label %LoopHead \n\
+        Exit: ; pred Entry, OnOne \n\
+          ret void \n\
+        }";
+  auto Mutator = createMutator<InsertPHIStrategy>();
+  ASSERT_TRUE(Mutator);
+
+  auto M = parseAssembly(Source.data(), Ctx);
+  std::mt19937 mt(Seed);
+  std::uniform_int_distribution<int> RandInt(INT_MIN, INT_MAX);
+  for (int i = 0; i < 100; i++) {
+    Mutator->mutateModule(*M, RandInt(mt), Source.size(), Source.size() + 1024);
+    ASSERT_FALSE(verifyModule(*M, &errs()));
+  }
+}
+
+TEST(InsertPHIStrategy, PHIWithSameIncomingBlock) {
+  LLVMContext Ctx;
+  StringRef Source = "\n\
+        define void @test(i32 %I) { \n\
+        Entry:  \n\
+          switch i32 %I, label %Exit [ \n\
+              i32 1, label %IdentCase  \n\
+              i32 2, label %IdentCase \n\
+              i32 3, label %IdentCase \n\
+              i32 4, label %IdentCase \n\
+          ] \n\
+        IdentCase: \n\
+          br label %Exit \n\
+        Exit: \n\
+          ret void \n\
+        }";
+  auto IPS = std::make_unique<InsertPHIStrategy>();
+  RandomIRBuilder IB(Seed, {IntegerType::getInt32Ty(Ctx)});
+  auto M = parseAssembly(Source.data(), Ctx);
+  Function &F = *M->begin();
+  for (auto &BB : F) {
+    IPS->mutate(BB, IB);
+    ASSERT_FALSE(verifyModule(*M, &errs()));
+  }
+}
+
 TEST(SinkInstructionStrategy, Operand) {
   LLVMContext Ctx;
   StringRef Source = "\n\
       define i32 @test(i1 %C1, i1 %C2, i1 %C3, i32 %I, i32 %J) { \n\
         Entry:  \n\
           %I100 = add i32 %I, 100  \n\
           switch i32 %I100, label %BB0 [ \n\
             i32 42, label %BB1  \n\