summaryrefslogtreecommitdiffstats
path: root/llvm/lib
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib')
-rw-r--r--llvm/lib/CMakeLists.txt1
-rw-r--r--llvm/lib/FuzzMutate/CMakeLists.txt12
-rw-r--r--llvm/lib/FuzzMutate/IRMutator.cpp183
-rw-r--r--llvm/lib/FuzzMutate/LLVMBuild.txt22
-rw-r--r--llvm/lib/FuzzMutate/OpDescriptor.cpp38
-rw-r--r--llvm/lib/FuzzMutate/Operations.cpp312
-rw-r--r--llvm/lib/FuzzMutate/RandomIRBuilder.cpp140
7 files changed, 708 insertions, 0 deletions
diff --git a/llvm/lib/CMakeLists.txt b/llvm/lib/CMakeLists.txt
index 71b0a0aa0d3..5e20d503482 100644
--- a/llvm/lib/CMakeLists.txt
+++ b/llvm/lib/CMakeLists.txt
@@ -2,6 +2,7 @@
# CMakeLists.txt
add_subdirectory(IR)
+add_subdirectory(FuzzMutate)
add_subdirectory(IRReader)
add_subdirectory(CodeGen)
add_subdirectory(BinaryFormat)
diff --git a/llvm/lib/FuzzMutate/CMakeLists.txt b/llvm/lib/FuzzMutate/CMakeLists.txt
new file mode 100644
index 00000000000..4aec682b01f
--- /dev/null
+++ b/llvm/lib/FuzzMutate/CMakeLists.txt
@@ -0,0 +1,12 @@
+add_llvm_library(LLVMFuzzMutate
+ IRMutator.cpp
+ OpDescriptor.cpp
+ Operations.cpp
+ RandomIRBuilder.cpp
+
+ ADDITIONAL_HEADER_DIRS
+ ${LLVM_MAIN_INCLUDE_DIR}/llvm/FuzzMutate
+
+ DEPENDS
+ intrinsics_gen
+ )
diff --git a/llvm/lib/FuzzMutate/IRMutator.cpp b/llvm/lib/FuzzMutate/IRMutator.cpp
new file mode 100644
index 00000000000..6545446a984
--- /dev/null
+++ b/llvm/lib/FuzzMutate/IRMutator.cpp
@@ -0,0 +1,183 @@
+//===-- IRMutator.cpp -----------------------------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/FuzzMutate/IRMutator.h"
+#include "llvm/Analysis/TargetLibraryInfo.h"
+#include "llvm/FuzzMutate/Operations.h"
+#include "llvm/FuzzMutate/Random.h"
+#include "llvm/FuzzMutate/RandomIRBuilder.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/InstIterator.h"
+#include "llvm/IR/Module.h"
+#include "llvm/Transforms/Scalar/DCE.h"
+
+using namespace llvm;
+
+static void createEmptyFunction(Module &M) {
+ // TODO: Some arguments and a return value would probably be more interesting.
+ LLVMContext &Context = M.getContext();
+ Function *F = Function::Create(FunctionType::get(Type::getVoidTy(Context), {},
+ /*isVarArg=*/false),
+ GlobalValue::ExternalLinkage, "f", &M);
+ BasicBlock *BB = BasicBlock::Create(Context, "BB", F);
+ ReturnInst::Create(Context, BB);
+}
+
+void IRMutationStrategy::mutate(Module &M, RandomIRBuilder &IB) {
+ if (M.empty())
+ createEmptyFunction(M);
+
+ auto RS = makeSampler<Function *>(IB.Rand);
+ for (Function &F : M)
+ if (!F.isDeclaration())
+ RS.sample(&F, /*Weight=*/1);
+ mutate(*RS.getSelection(), IB);
+}
+
+void IRMutationStrategy::mutate(Function &F, RandomIRBuilder &IB) {
+ mutate(*makeSampler(IB.Rand, make_pointer_range(F)).getSelection(), IB);
+}
+
+void IRMutationStrategy::mutate(BasicBlock &BB, RandomIRBuilder &IB) {
+ mutate(*makeSampler(IB.Rand, make_pointer_range(BB)).getSelection(), IB);
+}
+
+void IRMutator::mutateModule(Module &M, int Seed, size_t CurSize,
+ size_t MaxSize) {
+ std::vector<Type *> Types;
+ for (const auto &Getter : AllowedTypes)
+ Types.push_back(Getter(M.getContext()));
+ RandomIRBuilder IB(Seed, Types);
+
+ auto RS = makeSampler<IRMutationStrategy *>(IB.Rand);
+ for (const auto &Strategy : Strategies)
+ RS.sample(Strategy.get(),
+ Strategy->getWeight(CurSize, MaxSize, RS.totalWeight()));
+ auto Strategy = RS.getSelection();
+
+ Strategy->mutate(M, IB);
+}
+
+static void eliminateDeadCode(Function &F) {
+ FunctionPassManager FPM;
+ FPM.addPass(DCEPass());
+ FunctionAnalysisManager FAM;
+ FAM.registerPass([&] { return TargetLibraryAnalysis(); });
+ FPM.run(F, FAM);
+}
+
+void InjectorIRStrategy::mutate(Function &F, RandomIRBuilder &IB) {
+ IRMutationStrategy::mutate(F, IB);
+ eliminateDeadCode(F);
+}
+
+std::vector<fuzzerop::OpDescriptor> InjectorIRStrategy::getDefaultOps() {
+ std::vector<fuzzerop::OpDescriptor> Ops;
+ describeFuzzerIntOps(Ops);
+ describeFuzzerFloatOps(Ops);
+ describeFuzzerControlFlowOps(Ops);
+ describeFuzzerPointerOps(Ops);
+ describeFuzzerAggregateOps(Ops);
+ describeFuzzerVectorOps(Ops);
+ return Ops;
+}
+
+fuzzerop::OpDescriptor
+InjectorIRStrategy::chooseOperation(Value *Src, RandomIRBuilder &IB) {
+ auto OpMatchesPred = [&Src](fuzzerop::OpDescriptor &Op) {
+ return Op.SourcePreds[0].matches({}, Src);
+ };
+ auto RS = makeSampler(IB.Rand, make_filter_range(Operations, OpMatchesPred));
+ if (RS.isEmpty())
+ report_fatal_error("No available operations for src type");
+ return *RS;
+}
+
+void InjectorIRStrategy::mutate(BasicBlock &BB, RandomIRBuilder &IB) {
+ SmallVector<Instruction *, 32> Insts;
+ for (auto I = BB.getFirstInsertionPt(), E = BB.end(); I != E; ++I)
+ Insts.push_back(&*I);
+
+ // Choose an insertion point for our new instruction.
+ size_t IP = uniform<size_t>(IB.Rand, 0, Insts.size() - 1);
+
+ auto InstsBefore = makeArrayRef(Insts).slice(0, IP);
+ auto InstsAfter = makeArrayRef(Insts).slice(IP);
+
+ // Choose a source, which will be used to constrain the operation selection.
+ SmallVector<Value *, 2> Srcs;
+ Srcs.push_back(IB.findOrCreateSource(BB, InstsBefore));
+
+ // Choose an operation that's constrained to be valid for the type of the
+ // source, collect any other sources it needs, and then build it.
+ fuzzerop::OpDescriptor OpDesc = chooseOperation(Srcs[0], IB);
+ for (const auto &Pred : makeArrayRef(OpDesc.SourcePreds).slice(1))
+ Srcs.push_back(IB.findOrCreateSource(BB, InstsBefore, Srcs, Pred));
+ if (Value *Op = OpDesc.BuilderFunc(Srcs, Insts[IP])) {
+ // Find a sink and wire up the results of the operation.
+ IB.connectToSink(BB, InstsAfter, Op);
+ }
+}
+
+uint64_t InstDeleterIRStrategy::getWeight(size_t CurrentSize, size_t MaxSize,
+ uint64_t CurrentWeight) {
+ // If we have less than 200 bytes, panic and try to always delete.
+ if (CurrentSize > MaxSize - 200)
+ return CurrentWeight ? CurrentWeight * 100 : 1;
+ // Draw a line starting from when we only have 1k left and increasing linearly
+ // to double the current weight.
+ int Line = (-2 * CurrentWeight) * (MaxSize - CurrentSize + 1000);
+ // Clamp negative weights to zero.
+ if (Line < 0)
+ return 0;
+ return Line;
+}
+
+void InstDeleterIRStrategy::mutate(Function &F, RandomIRBuilder &IB) {
+ auto RS = makeSampler<Instruction *>(IB.Rand);
+ // Avoid terminators so we don't have to worry about keeping the CFG coherent.
+ for (Instruction &Inst : instructions(F))
+ if (!Inst.isTerminator())
+ RS.sample(&Inst, /*Weight=*/1);
+ assert(!RS.isEmpty() && "No instructions to delete");
+ // Delete the instruction.
+ mutate(*RS.getSelection(), IB);
+ // Clean up any dead code that's left over after removing the instruction.
+ eliminateDeadCode(F);
+}
+
+void InstDeleterIRStrategy::mutate(Instruction &Inst, RandomIRBuilder &IB) {
+ assert(!Inst.isTerminator() && "Deleting terminators invalidates CFG");
+
+ if (Inst.getType()->isVoidTy()) {
+ // Instructions with void type (ie, store) have no uses to worry about. Just
+ // erase it and move on.
+ Inst.eraseFromParent();
+ return;
+ }
+
+ // Otherwise we need to find some other value with the right type to keep the
+ // users happy.
+ auto Pred = fuzzerop::onlyType(Inst.getType());
+ auto RS = makeSampler<Value *>(IB.Rand);
+ SmallVector<Instruction *, 32> InstsBefore;
+ BasicBlock *BB = Inst.getParent();
+ for (auto I = BB->getFirstInsertionPt(), E = Inst.getIterator(); I != E;
+ ++I) {
+ if (Pred.matches({}, &*I))
+ RS.sample(&*I, /*Weight=*/1);
+ InstsBefore.push_back(&*I);
+ }
+ if (!RS)
+ RS.sample(IB.newSource(*BB, InstsBefore, {}, Pred), /*Weight=*/1);
+
+ Inst.replaceAllUsesWith(RS.getSelection());
+}
diff --git a/llvm/lib/FuzzMutate/LLVMBuild.txt b/llvm/lib/FuzzMutate/LLVMBuild.txt
new file mode 100644
index 00000000000..732c371a54f
--- /dev/null
+++ b/llvm/lib/FuzzMutate/LLVMBuild.txt
@@ -0,0 +1,22 @@
+;===- ./lib/FuzzMutate/LLVMBuild.txt ---------------------------*- Conf -*--===;
+;
+; The LLVM Compiler Infrastructure
+;
+; This file is distributed under the University of Illinois Open Source
+; License. See LICENSE.TXT for details.
+;
+;===------------------------------------------------------------------------===;
+;
+; This is an LLVMBuild description file for the components in this subdirectory.
+;
+; For more information on the LLVMBuild system, please see:
+;
+; http://llvm.org/docs/LLVMBuild.html
+;
+;===------------------------------------------------------------------------===;
+
+[component_0]
+type = Library
+name = FuzzMutate
+parent = Libraries
+required_libraries = Analysis Core IR Support Transforms
diff --git a/llvm/lib/FuzzMutate/OpDescriptor.cpp b/llvm/lib/FuzzMutate/OpDescriptor.cpp
new file mode 100644
index 00000000000..1c5d8f606ae
--- /dev/null
+++ b/llvm/lib/FuzzMutate/OpDescriptor.cpp
@@ -0,0 +1,38 @@
+//===-- OpDescriptor.cpp --------------------------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/FuzzMutate/OpDescriptor.h"
+#include "llvm/IR/Constants.h"
+
+using namespace llvm;
+using namespace fuzzerop;
+
+void fuzzerop::makeConstantsWithType(Type *T, std::vector<Constant *> &Cs) {
+ if (auto *IntTy = dyn_cast<IntegerType>(T)) {
+ uint64_t W = IntTy->getBitWidth();
+ Cs.push_back(ConstantInt::get(IntTy, APInt::getMaxValue(W)));
+ Cs.push_back(ConstantInt::get(IntTy, APInt::getMinValue(W)));
+ Cs.push_back(ConstantInt::get(IntTy, APInt::getSignedMaxValue(W)));
+ Cs.push_back(ConstantInt::get(IntTy, APInt::getSignedMinValue(W)));
+ Cs.push_back(ConstantInt::get(IntTy, APInt::getOneBitSet(W, W / 2)));
+ } else if (T->isFloatingPointTy()) {
+ auto &Ctx = T->getContext();
+ auto &Sem = T->getFltSemantics();
+ Cs.push_back(ConstantFP::get(Ctx, APFloat::getZero(Sem)));
+ Cs.push_back(ConstantFP::get(Ctx, APFloat::getLargest(Sem)));
+ Cs.push_back(ConstantFP::get(Ctx, APFloat::getSmallest(Sem)));
+ } else
+ Cs.push_back(UndefValue::get(T));
+}
+
+std::vector<Constant *> fuzzerop::makeConstantsWithType(Type *T) {
+ std::vector<Constant *> Result;
+ makeConstantsWithType(T, Result);
+ return Result;
+}
diff --git a/llvm/lib/FuzzMutate/Operations.cpp b/llvm/lib/FuzzMutate/Operations.cpp
new file mode 100644
index 00000000000..083d9aa039e
--- /dev/null
+++ b/llvm/lib/FuzzMutate/Operations.cpp
@@ -0,0 +1,312 @@
+//===-- Operations.cpp ----------------------------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/FuzzMutate/Operations.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Instructions.h"
+
+using namespace llvm;
+using namespace fuzzerop;
+
+void llvm::describeFuzzerIntOps(std::vector<fuzzerop::OpDescriptor> &Ops) {
+ Ops.push_back(binOpDescriptor(1, Instruction::Add));
+ Ops.push_back(binOpDescriptor(1, Instruction::Sub));
+ Ops.push_back(binOpDescriptor(1, Instruction::Mul));
+ Ops.push_back(binOpDescriptor(1, Instruction::SDiv));
+ Ops.push_back(binOpDescriptor(1, Instruction::UDiv));
+ Ops.push_back(binOpDescriptor(1, Instruction::SRem));
+ Ops.push_back(binOpDescriptor(1, Instruction::URem));
+ Ops.push_back(binOpDescriptor(1, Instruction::Shl));
+ Ops.push_back(binOpDescriptor(1, Instruction::LShr));
+ Ops.push_back(binOpDescriptor(1, Instruction::AShr));
+ Ops.push_back(binOpDescriptor(1, Instruction::And));
+ Ops.push_back(binOpDescriptor(1, Instruction::Or));
+ Ops.push_back(binOpDescriptor(1, Instruction::Xor));
+
+ Ops.push_back(cmpOpDescriptor(1, Instruction::ICmp, CmpInst::ICMP_EQ));
+ Ops.push_back(cmpOpDescriptor(1, Instruction::ICmp, CmpInst::ICMP_NE));
+ Ops.push_back(cmpOpDescriptor(1, Instruction::ICmp, CmpInst::ICMP_UGT));
+ Ops.push_back(cmpOpDescriptor(1, Instruction::ICmp, CmpInst::ICMP_UGE));
+ Ops.push_back(cmpOpDescriptor(1, Instruction::ICmp, CmpInst::ICMP_ULT));
+ Ops.push_back(cmpOpDescriptor(1, Instruction::ICmp, CmpInst::ICMP_ULE));
+ Ops.push_back(cmpOpDescriptor(1, Instruction::ICmp, CmpInst::ICMP_SGT));
+ Ops.push_back(cmpOpDescriptor(1, Instruction::ICmp, CmpInst::ICMP_SGE));
+ Ops.push_back(cmpOpDescriptor(1, Instruction::ICmp, CmpInst::ICMP_SLT));
+ Ops.push_back(cmpOpDescriptor(1, Instruction::ICmp, CmpInst::ICMP_SLE));
+}
+
+void llvm::describeFuzzerFloatOps(std::vector<fuzzerop::OpDescriptor> &Ops) {
+ Ops.push_back(binOpDescriptor(1, Instruction::FAdd));
+ Ops.push_back(binOpDescriptor(1, Instruction::FSub));
+ Ops.push_back(binOpDescriptor(1, Instruction::FMul));
+ Ops.push_back(binOpDescriptor(1, Instruction::FDiv));
+ Ops.push_back(binOpDescriptor(1, Instruction::FRem));
+
+ Ops.push_back(cmpOpDescriptor(1, Instruction::FCmp, CmpInst::FCMP_FALSE));
+ Ops.push_back(cmpOpDescriptor(1, Instruction::FCmp, CmpInst::FCMP_OEQ));
+ Ops.push_back(cmpOpDescriptor(1, Instruction::FCmp, CmpInst::FCMP_OGT));
+ Ops.push_back(cmpOpDescriptor(1, Instruction::FCmp, CmpInst::FCMP_OGE));
+ Ops.push_back(cmpOpDescriptor(1, Instruction::FCmp, CmpInst::FCMP_OLT));
+ Ops.push_back(cmpOpDescriptor(1, Instruction::FCmp, CmpInst::FCMP_OLE));
+ Ops.push_back(cmpOpDescriptor(1, Instruction::FCmp, CmpInst::FCMP_ONE));
+ Ops.push_back(cmpOpDescriptor(1, Instruction::FCmp, CmpInst::FCMP_ORD));
+ Ops.push_back(cmpOpDescriptor(1, Instruction::FCmp, CmpInst::FCMP_UNO));
+ Ops.push_back(cmpOpDescriptor(1, Instruction::FCmp, CmpInst::FCMP_UEQ));
+ Ops.push_back(cmpOpDescriptor(1, Instruction::FCmp, CmpInst::FCMP_UGT));
+ Ops.push_back(cmpOpDescriptor(1, Instruction::FCmp, CmpInst::FCMP_UGE));
+ Ops.push_back(cmpOpDescriptor(1, Instruction::FCmp, CmpInst::FCMP_ULT));
+ Ops.push_back(cmpOpDescriptor(1, Instruction::FCmp, CmpInst::FCMP_ULE));
+ Ops.push_back(cmpOpDescriptor(1, Instruction::FCmp, CmpInst::FCMP_UNE));
+ Ops.push_back(cmpOpDescriptor(1, Instruction::FCmp, CmpInst::FCMP_TRUE));
+}
+
+void llvm::describeFuzzerControlFlowOps(
+ std::vector<fuzzerop::OpDescriptor> &Ops) {
+ Ops.push_back(splitBlockDescriptor(1));
+}
+
+void llvm::describeFuzzerPointerOps(std::vector<fuzzerop::OpDescriptor> &Ops) {
+ Ops.push_back(gepDescriptor(1));
+}
+
+void llvm::describeFuzzerAggregateOps(
+ std::vector<fuzzerop::OpDescriptor> &Ops) {
+ Ops.push_back(extractValueDescriptor(1));
+ Ops.push_back(insertValueDescriptor(1));
+}
+
+void llvm::describeFuzzerVectorOps(std::vector<fuzzerop::OpDescriptor> &Ops) {
+ Ops.push_back(extractElementDescriptor(1));
+ Ops.push_back(insertElementDescriptor(1));
+ Ops.push_back(shuffleVectorDescriptor(1));
+}
+
+OpDescriptor llvm::fuzzerop::binOpDescriptor(unsigned Weight,
+ Instruction::BinaryOps Op) {
+ auto buildOp = [Op](ArrayRef<Value *> Srcs, Instruction *Inst) {
+ return BinaryOperator::Create(Op, Srcs[0], Srcs[1], "B", Inst);
+ };
+ switch (Op) {
+ case Instruction::Add:
+ case Instruction::Sub:
+ case Instruction::Mul:
+ case Instruction::SDiv:
+ case Instruction::UDiv:
+ case Instruction::SRem:
+ case Instruction::URem:
+ case Instruction::Shl:
+ case Instruction::LShr:
+ case Instruction::AShr:
+ case Instruction::And:
+ case Instruction::Or:
+ case Instruction::Xor:
+ return {Weight, {anyIntType(), matchFirstType()}, buildOp};
+ case Instruction::FAdd:
+ case Instruction::FSub:
+ case Instruction::FMul:
+ case Instruction::FDiv:
+ case Instruction::FRem:
+ return {Weight, {anyFloatType(), matchFirstType()}, buildOp};
+ case Instruction::BinaryOpsEnd:
+ llvm_unreachable("Value out of range of enum");
+ }
+ llvm_unreachable("Covered switch");
+}
+
+OpDescriptor llvm::fuzzerop::cmpOpDescriptor(unsigned Weight,
+ Instruction::OtherOps CmpOp,
+ CmpInst::Predicate Pred) {
+ auto buildOp = [CmpOp, Pred](ArrayRef<Value *> Srcs, Instruction *Inst) {
+ return CmpInst::Create(CmpOp, Pred, Srcs[0], Srcs[1], "C", Inst);
+ };
+
+ switch (CmpOp) {
+ case Instruction::ICmp:
+ return {Weight, {anyIntType(), matchFirstType()}, buildOp};
+ case Instruction::FCmp:
+ return {Weight, {anyFloatType(), matchFirstType()}, buildOp};
+ default:
+ llvm_unreachable("CmpOp must be ICmp or FCmp");
+ }
+}
+
+OpDescriptor llvm::fuzzerop::splitBlockDescriptor(unsigned Weight) {
+ auto buildSplitBlock = [](ArrayRef<Value *> Srcs, Instruction *Inst) {
+ BasicBlock *Block = Inst->getParent();
+ BasicBlock *Next = Block->splitBasicBlock(Inst, "BB");
+ if (Block != &Block->getParent()->getEntryBlock()) {
+ // Loop back on this block by replacing the unconditional forward branch
+ // with a conditional with a backedge.
+ BranchInst::Create(Block, Next, Srcs[0], Block->getTerminator());
+ Block->getTerminator()->eraseFromParent();
+
+ // We need values for each phi in the block. Since there isn't a good way
+ // to do a variable number of input values currently, we just fill them
+ // with undef.
+ for (PHINode &PHI : Block->phis())
+ PHI.addIncoming(UndefValue::get(PHI.getType()), Block);
+ }
+ return nullptr;
+ };
+ SourcePred isInt1Ty{[](ArrayRef<Value *>, const Value *V) {
+ return V->getType()->isIntegerTy(1);
+ },
+ None};
+ return {Weight, {isInt1Ty}, buildSplitBlock};
+}
+
+OpDescriptor llvm::fuzzerop::gepDescriptor(unsigned Weight) {
+ auto buildGEP = [](ArrayRef<Value *> Srcs, Instruction *Inst) {
+ Type *Ty = cast<PointerType>(Srcs[0]->getType())->getElementType();
+ auto Indices = makeArrayRef(Srcs).drop_front(1);
+ return GetElementPtrInst::Create(Ty, Srcs[0], Indices, "G", Inst);
+ };
+ // TODO: Handle aggregates and vectors
+ // TODO: Support multiple indices.
+ // TODO: Try to avoid meaningless accesses.
+ return {Weight, {anyPtrType(), anyIntType()}, buildGEP};
+}
+
+static uint64_t getAggregateNumElements(Type *T) {
+ assert(T->isAggregateType() && "Not a struct or array");
+ if (isa<StructType>(T))
+ return T->getStructNumElements();
+ return T->getArrayNumElements();
+}
+
+static SourcePred validExtractValueIndex() {
+ auto Pred = [](ArrayRef<Value *> Cur, const Value *V) {
+ if (auto *CI = dyn_cast<ConstantInt>(V))
+ if (!CI->uge(getAggregateNumElements(Cur[0]->getType())))
+ return true;
+ return false;
+ };
+ auto Make = [](ArrayRef<Value *> Cur, ArrayRef<Type *> Ts) {
+ std::vector<Constant *> Result;
+ auto *Int32Ty = Type::getInt32Ty(Cur[0]->getContext());
+ uint64_t N = getAggregateNumElements(Cur[0]->getType());
+ // Create indices at the start, end, and middle, but avoid dups.
+ Result.push_back(ConstantInt::get(Int32Ty, 0));
+ if (N > 1)
+ Result.push_back(ConstantInt::get(Int32Ty, N - 1));
+ if (N > 2)
+ Result.push_back(ConstantInt::get(Int32Ty, N / 2));
+ return Result;
+ };
+ return {Pred, Make};
+}
+
+OpDescriptor llvm::fuzzerop::extractValueDescriptor(unsigned Weight) {
+ auto buildExtract = [](ArrayRef<Value *> Srcs, Instruction *Inst) {
+ // TODO: It's pretty inefficient to shuffle this all through constants.
+ unsigned Idx = cast<ConstantInt>(Srcs[1])->getZExtValue();
+ return ExtractValueInst::Create(Srcs[0], {Idx}, "E", Inst);
+ };
+ // TODO: Should we handle multiple indices?
+ return {Weight, {anyAggregateType(), validExtractValueIndex()}, buildExtract};
+}
+
+static SourcePred matchScalarInAggregate() {
+ auto Pred = [](ArrayRef<Value *> Cur, const Value *V) {
+ if (isa<ArrayType>(Cur[0]->getType()))
+ return V->getType() == Cur[0]->getType();
+ auto *STy = cast<StructType>(Cur[0]->getType());
+ for (int I = 0, E = STy->getNumElements(); I < E; ++I)
+ if (STy->getTypeAtIndex(I) == V->getType())
+ return true;
+ return false;
+ };
+ auto Make = [](ArrayRef<Value *> Cur, ArrayRef<Type *>) {
+ if (isa<ArrayType>(Cur[0]->getType()))
+ return makeConstantsWithType(Cur[0]->getType());
+ std::vector<Constant *> Result;
+ auto *STy = cast<StructType>(Cur[0]->getType());
+ for (int I = 0, E = STy->getNumElements(); I < E; ++I)
+ makeConstantsWithType(STy->getTypeAtIndex(I), Result);
+ return Result;
+ };
+ return {Pred, Make};
+}
+
+static SourcePred validInsertValueIndex() {
+ auto Pred = [](ArrayRef<Value *> Cur, const Value *V) {
+ auto *CTy = cast<CompositeType>(Cur[0]->getType());
+ if (auto *CI = dyn_cast<ConstantInt>(V))
+ if (CI->getBitWidth() == 32)
+ if (CTy->getTypeAtIndex(CI->getZExtValue()) == V->getType())
+ return true;
+ return false;
+ };
+ auto Make = [](ArrayRef<Value *> Cur, ArrayRef<Type *> Ts) {
+ std::vector<Constant *> Result;
+ auto *Int32Ty = Type::getInt32Ty(Cur[0]->getContext());
+ auto *CTy = cast<CompositeType>(Cur[0]->getType());
+ for (int I = 0, E = getAggregateNumElements(CTy); I < E; ++I)
+ if (CTy->getTypeAtIndex(I) == Cur[1]->getType())
+ Result.push_back(ConstantInt::get(Int32Ty, I));
+ return Result;
+ };
+ return {Pred, Make};
+}
+
+OpDescriptor llvm::fuzzerop::insertValueDescriptor(unsigned Weight) {
+ auto buildInsert = [](ArrayRef<Value *> Srcs, Instruction *Inst) {
+ // TODO: It's pretty inefficient to shuffle this all through constants.
+ unsigned Idx = cast<ConstantInt>(Srcs[2])->getZExtValue();
+ return InsertValueInst::Create(Srcs[0], Srcs[1], {Idx}, "I", Inst);
+ };
+ return {
+ Weight,
+ {anyAggregateType(), matchScalarInAggregate(), validInsertValueIndex()},
+ buildInsert};
+}
+
+OpDescriptor llvm::fuzzerop::extractElementDescriptor(unsigned Weight) {
+ auto buildExtract = [](ArrayRef<Value *> Srcs, Instruction *Inst) {
+ return ExtractElementInst::Create(Srcs[0], Srcs[1], "E", Inst);
+ };
+ // TODO: Try to avoid undefined accesses.
+ return {Weight, {anyVectorType(), anyIntType()}, buildExtract};
+}
+
+OpDescriptor llvm::fuzzerop::insertElementDescriptor(unsigned Weight) {
+ auto buildInsert = [](ArrayRef<Value *> Srcs, Instruction *Inst) {
+ return InsertElementInst::Create(Srcs[0], Srcs[1], Srcs[2], "I", Inst);
+ };
+ // TODO: Try to avoid undefined accesses.
+ return {Weight,
+ {anyVectorType(), matchScalarOfFirstType(), anyIntType()},
+ buildInsert};
+}
+
+static SourcePred validShuffleVectorIndex() {
+ auto Pred = [](ArrayRef<Value *> Cur, const Value *V) {
+ return ShuffleVectorInst::isValidOperands(Cur[0], Cur[1], V);
+ };
+ auto Make = [](ArrayRef<Value *> Cur, ArrayRef<Type *> Ts) {
+ auto *FirstTy = cast<VectorType>(Cur[0]->getType());
+ auto *Int32Ty = Type::getInt32Ty(Cur[0]->getContext());
+ // TODO: It's straighforward to make up reasonable values, but listing them
+ // exhaustively would be insane. Come up with a couple of sensible ones.
+ return std::vector<Constant *>{
+ UndefValue::get(VectorType::get(Int32Ty, FirstTy->getNumElements()))};
+ };
+ return {Pred, Make};
+}
+
+OpDescriptor llvm::fuzzerop::shuffleVectorDescriptor(unsigned Weight) {
+ auto buildShuffle = [](ArrayRef<Value *> Srcs, Instruction *Inst) {
+ return new ShuffleVectorInst(Srcs[0], Srcs[1], Srcs[2], "S", Inst);
+ };
+ return {Weight,
+ {anyVectorType(), matchFirstType(), validShuffleVectorIndex()},
+ buildShuffle};
+}
diff --git a/llvm/lib/FuzzMutate/RandomIRBuilder.cpp b/llvm/lib/FuzzMutate/RandomIRBuilder.cpp
new file mode 100644
index 00000000000..fd93c4005d3
--- /dev/null
+++ b/llvm/lib/FuzzMutate/RandomIRBuilder.cpp
@@ -0,0 +1,140 @@
+//===-- RandomIRBuilder.cpp -----------------------------------------------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/FuzzMutate/RandomIRBuilder.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/FuzzMutate/Random.h"
+#include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/IR/IntrinsicInst.h"
+#include "llvm/IR/Module.h"
+
+using namespace llvm;
+using namespace fuzzerop;
+
+Value *RandomIRBuilder::findOrCreateSource(BasicBlock &BB,
+ ArrayRef<Instruction *> Insts) {
+ return findOrCreateSource(BB, Insts, {}, anyType());
+}
+
+Value *RandomIRBuilder::findOrCreateSource(BasicBlock &BB,
+ ArrayRef<Instruction *> Insts,
+ ArrayRef<Value *> Srcs,
+ SourcePred Pred) {
+ auto MatchesPred = [&Srcs, &Pred](Instruction *Inst) {
+ return Pred.matches(Srcs, Inst);
+ };
+ auto RS = makeSampler(Rand, make_filter_range(Insts, MatchesPred));
+ // Also consider choosing no source, meaning we want a new one.
+ RS.sample(nullptr, /*Weight=*/1);
+ if (Instruction *Src = RS.getSelection())
+ return Src;
+ return newSource(BB, Insts, Srcs, Pred);
+}
+
+Value *RandomIRBuilder::newSource(BasicBlock &BB, ArrayRef<Instruction *> Insts,
+ ArrayRef<Value *> Srcs, SourcePred Pred) {
+ // Generate some constants to choose from.
+ auto RS = makeSampler<Value *>(Rand);
+ RS.sample(Pred.generate(Srcs, KnownTypes));
+ assert(!RS.isEmpty() && "Failed to generate sources");
+
+ // If we can find a pointer to load from, use it half the time.
+ Value *Ptr = findPointer(BB, Insts, Srcs, Pred);
+ if (Ptr)
+ RS.sample(Ptr, RS.totalWeight());
+
+ Value *Result = RS.getSelection();
+ if (Result != Ptr)
+ return Result;
+
+ // If we choose the pointer, we need to create a load.
+ auto IP = BB.getFirstInsertionPt();
+ if (auto *I = dyn_cast<Instruction>(Ptr))
+ IP = ++I->getIterator();
+ return new LoadInst(Ptr, "L", &*IP);
+}
+
+static bool isCompatibleReplacement(const Instruction *I, const Use &Operand,
+ const Value *Replacement) {
+ if (Operand->getType() != Replacement->getType())
+ return false;
+ switch (I->getOpcode()) {
+ case Instruction::GetElementPtr:
+ case Instruction::ExtractElement:
+ case Instruction::ExtractValue:
+ // TODO: We could potentially validate these, but for now just leave indices
+ // alone.
+ if (Operand.getOperandNo() > 1)
+ return false;
+ break;
+ case Instruction::InsertValue:
+ case Instruction::InsertElement:
+ if (Operand.getOperandNo() > 2)
+ return false;
+ break;
+ default:
+ break;
+ }
+ return true;
+}
+
+void RandomIRBuilder::connectToSink(BasicBlock &BB,
+ ArrayRef<Instruction *> Insts, Value *V) {
+ auto RS = makeSampler<Use *>(Rand);
+ for (auto &I : Insts) {
+ if (isa<IntrinsicInst>(I))
+ // TODO: Replacing operands of intrinsics would be interesting, but
+ // there's no easy way to verify that a given replacement is valid given
+ // that intrinsics can impose arbitrary constraints.
+ continue;
+ for (Use &U : I->operands())
+ if (isCompatibleReplacement(I, U, V))
+ RS.sample(&U, 1);
+ }
+ // Also consider choosing no sink, meaning we want a new one.
+ RS.sample(nullptr, /*Weight=*/1);
+
+ if (Use *Sink = RS.getSelection()) {
+ User *U = Sink->getUser();
+ unsigned OpNo = Sink->getOperandNo();
+ U->setOperand(OpNo, V);
+ return;
+ }
+ newSink(BB, Insts, V);
+}
+
+void RandomIRBuilder::newSink(BasicBlock &BB, ArrayRef<Instruction *> Insts,
+ Value *V) {
+ Value *Ptr = findPointer(BB, Insts, {V}, matchFirstType());
+ if (!Ptr) {
+ if (uniform<bool>(Rand))
+ Ptr = new AllocaInst(V->getType(), 0, "A", &*BB.getFirstInsertionPt());
+ else
+ Ptr = UndefValue::get(PointerType::get(V->getType(), 0));
+ }
+
+ new StoreInst(V, Ptr, Insts.back());
+}
+
+Value *RandomIRBuilder::findPointer(BasicBlock &BB,
+ ArrayRef<Instruction *> Insts,
+ ArrayRef<Value *> Srcs, SourcePred Pred) {
+ auto IsMatchingPtr = [&Srcs, &Pred](Instruction *Inst) {
+ if (auto PtrTy = dyn_cast<PointerType>(Inst->getType()))
+ // TODO: Check if this is horribly expensive.
+ return Pred.matches(Srcs, UndefValue::get(PtrTy->getElementType()));
+ return false;
+ };
+ if (auto RS = makeSampler(Rand, make_filter_range(Insts, IsMatchingPtr)))
+ return RS.getSelection();
+ return nullptr;
+}
OpenPOWER on IntegriCloud