[FuzzMutate] RandomIRBuilder has more source and sink type now.

[Peter]

Summary

Source and Sink are required when generating a new instruction.
(Term defined by previous author, in LLVM terms it's probably Use and User.)
Previously, only instructions in the same block is considered when taking source and sink.

In this patch, more source and sink types are considered.
For source, we have SrcFromInstInCurBlock, FunctionArgument, InstInDominator, SrcFromGlobalVariable, and NewConstOrStack.
For sink, we have SinkToInstInCurBlock, PointersInDominator, InstInDominatee, NewStore, and SinkToGlobalVariable.

A unit test to make sure source always dominates an instruction, and the instruction always dominates the sink is included.

[Peter]

add comment for new functions

[arsenm]

llvm/include/llvm/FuzzMutate/RandomIRBuilder.h

47–49

return std::pair instead of using bool out argument?

llvm/lib/FuzzMutate/RandomIRBuilder.cpp

63

Alloca address space, not program

96

Should use datalayout's default global address space

131

With the range do you really need to make the args vector? If so you can just initialize with Args(F->arg_begin(), F->arg_end())

173

No else after return

[Peter]

Use pair for return type

llvm/lib/FuzzMutate/RandomIRBuilder.cpp

131

What's annoying about built in ranges is that they are ranges of references, which a) can be used to initialize a pointer vector and b) causes a ton of type conversion and use of copy constructor issues.

173

Do you mean we don't need to remove the newly created Global Variable, even if we didn't use it? I am worried the random module will be filled with them pretty soon...

[Peter]

no else after return

[Peter]

llvm/lib/FuzzMutate/RandomIRBuilder.cpp

173

nvm, thanks for pointing out.

[arsenm]

llvm/lib/FuzzMutate/RandomIRBuilder.cpp

42

You shouldn't need this template stuff, you're operating directly on IR with the IR version of the tree?

127

SmallVector

174

use_empty

318

Shouldn't bother handling typed pointers?

343

Dead break

354

Extra ;

llvm/unittests/FuzzMutate/RandomIRBuilderTest.cpp

238

I think there is an ASSERT_NE

[Peter]

llvm/lib/FuzzMutate/RandomIRBuilder.cpp

42

Ah yes. The template is there just in case I need PostDominatorTree. I can add it back when I need it in the future.

318

I'm sorry I don't fully understand. What do you mean we shouldn't handle typed pointers? Since we have no knowledge what we are mutating on, I think we should consider the possibility that the pointer is typed.

[Peter]

Update

[arsenm]

llvm/include/llvm/FuzzMutate/RandomIRBuilder.h

22–31

clang-format should sort these alphabetically for you

llvm/lib/FuzzMutate/RandomIRBuilder.cpp

127

Use default size, or something larger

128

Args(F.args()) or Args(F.arg_begin, F.arg_end()) should work to do this in the constructor

348

dead break

llvm/unittests/FuzzMutate/RandomIRBuilderTest.cpp

238

Don't see why this needs to be ASSERT, and not EXPECT

319

Try adding some vector, pointer, FP, and aggregate types?

[Peter]

update unit tests.
mod code style.

[Peter]

llvm/lib/FuzzMutate/RandomIRBuilder.cpp

128

As we have discussed before, both methods you mentioned gives a reference range. While makeSampler down below doesn't work well with references as it declared std::remove_reference_t, implicitly calling a copy constructor when sampling.

[Peter]

@arsenm Hey Matt does these changes look to you?

[Peter]

Fix a bug when we call Initializer of a GV, it may not have one.

We use it's type to construct a UndefValue now.

[Peter]

@arsenm Hi Matt, Would you mind spend some time and review this patch?

[arsenm]

llvm/lib/FuzzMutate/RandomIRBuilder.cpp

125–126

Drop comment

141–142

Drop comment

287–289

Not really, you just need to avoid touching immarg parameters

318

You can just drop the isOpaqueOrPointeeTypeMatches check, pointers are always opaque now

llvm/unittests/FuzzMutate/RandomIRBuilderTest.cpp

326

Can just use a regular array or std::array, you never resize these

[Peter]

Update tests and comments.

[Peter]

llvm/lib/FuzzMutate/RandomIRBuilder.cpp

287–289

I am not sure how to determine if an operand of an intrinsic should be immarg or not, would you please elabrate?

[arsenm]

llvm/lib/FuzzMutate/RandomIRBuilder.cpp

287–289

Something like F.hasParamAttr(i, Attribute::ImmArg) should work

[Peter]

Allow sink into Intrinsic now

llvm/lib/FuzzMutate/RandomIRBuilder.cpp

287–289

This rule is now added to isCompatibleReplacement

[arsenm]

llvm/lib/FuzzMutate/RandomIRBuilder.cpp

310

Braces

311

Braecs

[arsenm]

llvm/lib/FuzzMutate/RandomIRBuilder.cpp

268

Allowing replacement of immarg with any Constant is too broad, it only allows ConstantInt. Additionally, replacing the value may be a bit risky. Might as well just skip all immarg arguments

[Peter]

Forbits replacement of immarg

[Peter]

Updated

[Peter]

rebase to upstream/main

[thakis]

This breaks tests on Mac (m1): http://45.33.8.238/macm1/58752/step_11.txt

Please take a look and revert for now if it takes a while to fix.

[Peter]

Thanks for mentioning. It has been reverted in the upstream.

The problems seem to be unit testing, not the code. When we have explicit pointer types, we check that we cannot load to a function pointer. Now that we default to opaque pointers, that check may fail.

[Peter]

Remove unit tests that checks for pointer type match, they are all opaque pointers now.

[Peter]

remove tests

[Peter]

• Remove pointer tests since they are all opaque now

[Peter]

Remove pointer tests as they are opaque now

llvm/include/llvm/FuzzMutate/RandomIRBuilder.h

 #ifndef LLVM_FUZZMUTATE_RANDOMIRBUILDER_H
 #define LLVM_FUZZMUTATE_RANDOMIRBUILDER_H
 
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/SmallVector.h"
 #include <random>
 
 namespace llvm {
+class AllocaInst;
 class BasicBlock;
+class Function;
+class GlobalVariable;
 class Instruction;
 class LLVMContext;
 class Type;
 class Value;
+class Module;
+
 namespace fuzzerop {
 class SourcePred;
 }
 
 using RandomEngine = std::mt19937;
 
 struct RandomIRBuilder {
   RandomEngine Rand;
   SmallVector<Type *, 16> KnownTypes;
 
   RandomIRBuilder(int Seed, ArrayRef<Type *> AllowedTypes)
       : Rand(Seed), KnownTypes(AllowedTypes.begin(), AllowedTypes.end()) {}
 
   // TODO: Try to make this a bit less of a random mishmash of functions.
 
+  /// Create a stack memory at the head of the function, store \c Init to the
+  /// memory if provided.
+  AllocaInst *createStackMemory(Function *F, Type *Ty, Value *Init = nullptr);
+  /// Find or create a global variable. It will be initialized by random
+  /// constants that satisfies \c Pred. It will also report whether this global
+  /// variable found or created.
+  std::pair<GlobalVariable *, bool>
+  findOrCreateGlobalVariable(Module *M, ArrayRef<Value *> Srcs,
+                             fuzzerop::SourcePred Pred);
+  enum SourceType {
+    SrcFromInstInCurBlock,
+    FunctionArgument,
+    InstInDominator,
+    SrcFromGlobalVariable,
+    NewConstOrStack,
+    EndOfValueSource,
+  };
   /// Find a "source" for some operation, which will be used in one of the
   /// operation's operands. This either selects an instruction in \c Insts or
   /// returns some new arbitrary Value.
   Value *findOrCreateSource(BasicBlock &BB, ArrayRef<Instruction *> Insts);
   /// Find a "source" for some operation, which will be used in one of the
   /// operation's operands. This either selects an instruction in \c Insts that
   /// matches \c Pred, or returns some new Value that matches \c Pred. The
   /// values in \c Srcs should be source operands that have already been
   /// selected.
   Value *findOrCreateSource(BasicBlock &BB, ArrayRef<Instruction *> Insts,
                             ArrayRef<Value *> Srcs, fuzzerop::SourcePred Pred,
                             bool allowConstant = true);
   /// Create some Value suitable as a source for some operation.
   Value *newSource(BasicBlock &BB, ArrayRef<Instruction *> Insts,
                    ArrayRef<Value *> Srcs, fuzzerop::SourcePred Pred,
                    bool allowConstant = true);
+
+  enum SinkType {
+    /// TODO: Also consider pointers in function argument.
+    SinkToInstInCurBlock,
+    PointersInDominator,
+    InstInDominatee,
+    NewStore,
+    SinkToGlobalVariable,
+    EndOfValueSink,
+  };
   /// Find a viable user for \c V in \c Insts, which should all be contained in
   /// \c BB. This may also create some new instruction in \c BB and use that.
-  void connectToSink(BasicBlock &BB, ArrayRef<Instruction *> Insts, Value *V);
+  Instruction *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);
+  Instruction *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/RandomIRBuilder.cpp

 //===-- RandomIRBuilder.cpp -----------------------------------------------===//
 //
 // 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/FuzzMutate/RandomIRBuilder.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/FuzzMutate/OpDescriptor.h"
 #include "llvm/FuzzMutate/Random.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
+#include "llvm/IR/Dominators.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;
 
+/// Return a vector of Blocks that dominates this block, excluding current
+/// block.
+static std::vector<BasicBlock *> getDominators(BasicBlock *BB) {
+  std::vector<BasicBlock *> ret;
+  DominatorTree DT(*BB->getParent());
+  DomTreeNode *Node = DT[BB]->getIDom();
+  while (Node && Node->getBlock()) {
+    ret.push_back(Node->getBlock());
+    // Get parent block.
+    Node = Node->getIDom();
+  }
+  return ret;
+}
+
+/// Return a vector of Blocks that is dominated by this block, excluding current
+/// block
+static std::vector<BasicBlock *> getDominatees(BasicBlock *BB) {
+  DominatorTree DT(*BB->getParent());
+  std::vector<BasicBlock *> ret;
+  for (DomTreeNode *Child : DT[BB]->children())
+    ret.push_back(Child->getBlock());
+  uint64_t Idx = 0;
+  while (Idx < ret.size()) {
+    DomTreeNode *Node = DT[ret[Idx]];
+    Idx++;
+    for (DomTreeNode *Child : Node->children())
+      ret.push_back(Child->getBlock());
+  }
+  return ret;
+}
+
+AllocaInst *RandomIRBuilder::createStackMemory(Function *F, Type *Ty,
+                                               Value *Init) {
+  /// TODO: For all Allocas, maybe allocate an array.
+  BasicBlock *EntryBB = &F->getEntryBlock();
+  DataLayout DL(F->getParent());
+  AllocaInst *Alloca = new AllocaInst(Ty, DL.getAllocaAddrSpace(), "A",
+                                      &*EntryBB->getFirstInsertionPt());
+  if (Init)
+    new StoreInst(Init, Alloca, Alloca->getNextNode());
+  return Alloca;
+}
+
+std::pair<GlobalVariable *, bool>
+RandomIRBuilder::findOrCreateGlobalVariable(Module *M, ArrayRef<Value *> Srcs,
+                                            fuzzerop::SourcePred Pred) {
+  auto MatchesPred = [&Srcs, &Pred](GlobalVariable *GV) {
+    // Can't directly compare GV's type, as it would be a pointer to the actual
+    // type.
+    return Pred.matches(Srcs, UndefValue::get(GV->getValueType()));
+  };
+  bool DidCreate = false;
+  SmallVector<GlobalVariable *, 4> GlobalVars;
+  for (GlobalVariable &GV : M->globals()) {
+    GlobalVars.push_back(&GV);
+  }
+  auto RS = makeSampler(Rand, make_filter_range(GlobalVars, MatchesPred));
+  RS.sample(nullptr, 1);
+  GlobalVariable *GV = RS.getSelection();
+  if (!GV) {
+    DidCreate = true;
+    using LinkageTypes = GlobalVariable::LinkageTypes;
+    auto TRS = makeSampler<Constant *>(Rand);
+    TRS.sample(Pred.generate(Srcs, KnownTypes));
+    Constant *Init = TRS.getSelection();
+    Type *Ty = Init->getType();
+    GV = new GlobalVariable(*M, Ty, false, LinkageTypes::ExternalLinkage, Init,
+                            "G", nullptr,
+                            GlobalValue::ThreadLocalMode::NotThreadLocal,
+                            M->getDataLayout().getDefaultGlobalsAddressSpace());
+  }
+  return {GV, DidCreate};
+}
+
 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,
                                            bool allowConstant) {
-  auto MatchesPred = [&Srcs, &Pred](Instruction *Inst) {
-    return Pred.matches(Srcs, Inst);
-  };
+  auto MatchesPred = [&Srcs, &Pred](Value *V) { return Pred.matches(Srcs, V); };
+  SmallVector<uint64_t, 8> SrcTys;
+  for (uint64_t i = 0; i < EndOfValueSource; i++)
+    SrcTys.push_back(i);
+  std::shuffle(SrcTys.begin(), SrcTys.end(), Rand);
+  for (uint64_t SrcTy : SrcTys) {
+    switch (SrcTy) {
+    case SrcFromInstInCurBlock: {
       auto RS = makeSampler(Rand, make_filter_range(Insts, MatchesPred));
+      if (!RS.isEmpty()) {
+        return RS.getSelection();
+      }
+      break;
+    }
+    case FunctionArgument: {
+      Function *F = BB.getParent();
+      SmallVector<Argument *, 8> Args;
+      for (uint64_t i = 0; i < F->arg_size(); i++) {
+        Args.push_back(F->getArg(i));
+      }
+      auto RS = makeSampler(Rand, make_filter_range(Args, MatchesPred));
+      if (!RS.isEmpty()) {
+        return RS.getSelection();
+      }
+      break;
+    }
+    case InstInDominator: {
+      auto Dominators = getDominators(&BB);
+      std::shuffle(Dominators.begin(), Dominators.end(), Rand);
+      for (BasicBlock *Dom : Dominators) {
+        SmallVector<Instruction *, 16> Instructions;
+        for (Instruction &I : *Dom) {
+          Instructions.push_back(&I);
+        }
+        auto RS =
+            makeSampler(Rand, make_filter_range(Instructions, MatchesPred));
         // Also consider choosing no source, meaning we want a new one.
-  RS.sample(nullptr, /*Weight=*/1);
-  if (Instruction *Src = RS.getSelection())
-    return Src;
+        if (!RS.isEmpty()) {
+          return RS.getSelection();
+        }
+      }
+      break;
+    }
+    case SrcFromGlobalVariable: {
+      Module *M = BB.getParent()->getParent();
+      auto [GV, DidCreate] = findOrCreateGlobalVariable(M, Srcs, Pred);
+      Type *Ty = GV->getValueType();
+      LoadInst *LoadGV = nullptr;
+      if (BB.getTerminator()) {
+        LoadGV = new LoadInst(Ty, GV, "LGV", &*BB.getFirstInsertionPt());
+      } else {
+        LoadGV = new LoadInst(Ty, GV, "LGV", &BB);
+      }
+      // Because we might be generating new values, we have to check if it
+      // matches again.
+      if (DidCreate) {
+        if (Pred.matches(Srcs, LoadGV)) {
+          return LoadGV;
+        }
+        LoadGV->eraseFromParent();
+        // If no one is using this GlobalVariable, delete it too.
+        if (GV->use_empty()) {
+          GV->eraseFromParent();
+        }
+      }
+      break;
+    }
+    case NewConstOrStack: {
       return newSource(BB, Insts, Srcs, Pred, allowConstant);
     }
+    default:
+    case EndOfValueSource: {
+      llvm_unreachable("EndOfValueSource executed");
+    }
+    }
+  }
+  llvm_unreachable("Can't find a source");
+}
 
 Value *RandomIRBuilder::newSource(BasicBlock &BB, ArrayRef<Instruction *> Insts,
                                   ArrayRef<Value *> Srcs, SourcePred Pred,
                                   bool allowConstant) {
   // Generate some constants to choose from.
   auto RS = makeSampler<Value *>(Rand);
   RS.sample(Pred.generate(Srcs, KnownTypes));
 
Value *RandomIRBuilder::newSource(BasicBlock &BB, ArrayRef<Instruction *> Insts,
 
   Value *newSrc = RS.getSelection();
   // Generate a stack alloca and store the constant to it if constant is not
   // allowed, our hope is that later mutations can generate some values and
   // store to this placeholder.
   if (!allowConstant && isa<Constant>(newSrc)) {
     Type *Ty = newSrc->getType();
     Function *F = BB.getParent();
-    BasicBlock *EntryBB = &F->getEntryBlock();
-    /// TODO: For all Allocas, maybe allocate an array.
-    DataLayout DL(BB.getParent()->getParent());
-    AllocaInst *Alloca = new AllocaInst(Ty, DL.getProgramAddressSpace(), "A",
-                                        EntryBB->getTerminator());
-    new StoreInst(newSrc, Alloca, EntryBB->getTerminator());
+    AllocaInst *Alloca = createStackMemory(F, Ty, newSrc);
     if (BB.getTerminator()) {
       newSrc = new LoadInst(Ty, Alloca, /*ArrLen,*/ "L", BB.getTerminator());
     } else {
       newSrc = new LoadInst(Ty, Alloca, /*ArrLen,*/ "L", &BB);
     }
   }
   return newSrc;
 }
static bool isCompatibleReplacement(const Instruction *I, const Use &Operand,
   // For Br/Switch, we only try to modify the 1st Operand (condition).
   // Modify other operands, like switch case may accidently change case from
   // ConstantInt to a register, which is illegal.
   case Instruction::Switch:
   case Instruction::Br:
     if (OperandNo >= 1)
       return false;
     break;
+  case Instruction::Call:
+  case Instruction::Invoke:
+  case Instruction::CallBr: {
+    const CallBase *II = cast<CallBase>(I);
+    const Function *Callee = II->getCalledFunction();
+    return !Callee->hasParamAttribute(OperandNo, Attribute::ImmArg);
+  }
   default:
     break;
   }
   return true;
 }
 
-void RandomIRBuilder::connectToSink(BasicBlock &BB,
-                                    ArrayRef<Instruction *> Insts, Value *V) {
+Instruction *RandomIRBuilder::connectToSink(BasicBlock &BB,
+                                            ArrayRef<Instruction *> Insts,
+                                            Value *V) {
+  SmallVector<uint64_t, 8> SinkTys;
+  for (uint64_t i = 0; i < EndOfValueSink; i++)
+    SinkTys.push_back(i);
+  std::shuffle(SinkTys.begin(), SinkTys.end(), Rand);
+  auto findSinkAndConnect =
+      [this, V](ArrayRef<Instruction *> Instructions) -> Instruction * {
     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 (auto &I : Instructions) {
       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()) {
+    if (!RS.isEmpty()) {
+      Use *Sink = RS.getSelection();
       User *U = Sink->getUser();
       unsigned OpNo = Sink->getOperandNo();
       U->setOperand(OpNo, V);
-    return;
+      return cast<Instruction>(U);
+    }
+    return nullptr;
+  };
+  Instruction *Sink = nullptr;
+  for (uint64_t SinkTy : SinkTys) {
+    switch (SinkTy) {
+    case SinkToInstInCurBlock:
+      Sink = findSinkAndConnect(Insts);
+      if (Sink)
+        return Sink;
+      break;
+    case PointersInDominator: {
+      auto Dominators = getDominators(&BB);
+      std::shuffle(Dominators.begin(), Dominators.end(), Rand);
+      for (BasicBlock *Dom : Dominators) {
+        for (Instruction &I : *Dom) {
+          if (PointerType *PtrTy = dyn_cast<PointerType>(I.getType()))
+            return new StoreInst(V, &I, Insts.back());
         }
-  newSink(BB, Insts, V);
+      }
+      break;
+    }
+    case InstInDominatee: {
+      auto Dominatees = getDominatees(&BB);
+      std::shuffle(Dominatees.begin(), Dominatees.end(), Rand);
+      for (BasicBlock *Dominee : Dominatees) {
+        std::vector<Instruction *> Instructions;
+        for (Instruction &I : *Dominee)
+          Instructions.push_back(&I);
+        Sink = findSinkAndConnect(Instructions);
+        if (Sink) {
+          return Sink;
+        }
+      }
+      break;
+    }
+    case NewStore:
+      /// TODO: allocate a new stack memory.
+      return newSink(BB, Insts, V);
+    case SinkToGlobalVariable: {
+      Module *M = BB.getParent()->getParent();
+      auto [GV, DidCreate] =
+          findOrCreateGlobalVariable(M, {}, fuzzerop::onlyType(V->getType()));
+      return new StoreInst(V, GV, Insts.back());
+    }
+    case EndOfValueSink:
+    default:
+      llvm_unreachable("EndOfValueSink executed");
+    }
+  }
+  llvm_unreachable("Can't find a sink");
 }
 
-void RandomIRBuilder::newSink(BasicBlock &BB, ArrayRef<Instruction *> Insts,
-                              Value *V) {
+Instruction *RandomIRBuilder::newSink(BasicBlock &BB,
+                                      ArrayRef<Instruction *> Insts, Value *V) {
   Value *Ptr = findPointer(BB, Insts, {V}, matchFirstType());
   if (!Ptr) {
-    if (uniform(Rand, 0, 1))
-      Ptr = new AllocaInst(V->getType(), 0, "A", &*BB.getFirstInsertionPt());
-    else
+    if (uniform(Rand, 0, 1)) {
+      Type *Ty = V->getType();
+      Ptr = createStackMemory(BB.getParent(), Ty, UndefValue::get(Ty));
+    } else {
       Ptr = UndefValue::get(PointerType::get(V->getType(), 0));
     }
+  }
 
-  new StoreInst(V, Ptr, Insts.back());
+  return 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) {
     // Invoke instructions sometimes produce valid pointers but currently
     // we can't insert loads or stores from them

llvm/unittests/FuzzMutate/RandomIRBuilderTest.cpp

 #include "llvm/ADT/StringRef.h"
 #include "llvm/AsmParser/Parser.h"
 #include "llvm/AsmParser/SlotMapping.h"
 #include "llvm/FuzzMutate/IRMutator.h"
 #include "llvm/FuzzMutate/OpDescriptor.h"
 #include "llvm/FuzzMutate/Operations.h"
 #include "llvm/FuzzMutate/Random.h"
 #include "llvm/IR/Constants.h"
+#include "llvm/IR/Dominators.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 "gtest/gtest.h"
 
const char *Source = "%T = type {i8, i32, i64}\n"
                        "  %A = alloca %T\n"
                        "  %L = load %T, ptr %A"
                        "  ret void\n"
                        "}";
   auto M = parseAssembly(Source, Ctx);
 
   fuzzerop::OpDescriptor IVDescr = fuzzerop::insertValueDescriptor(1);
 
-  std::vector<Type *> Types = {Type::getInt8Ty(Ctx), Type::getInt32Ty(Ctx),
+  std::array<Type *, 3> Types = {Type::getInt8Ty(Ctx), Type::getInt32Ty(Ctx),
                                  Type::getInt64Ty(Ctx)};
   RandomIRBuilder IB(Seed, Types);
 
   // Get first basic block of the first function
   Function &F = *M->begin();
   BasicBlock &BB = *F.begin();
 
   // Pick first source
   Instruction *Src = &*std::next(BB.begin());
const char *SourceCode = "define void @test() {\n"
                            "  %A = alloca [8 x i32]\n"
                            "  %L = load [8 x i32], ptr %A"
                            "  ret void\n"
                            "}";
   auto M = parseAssembly(SourceCode, Ctx);
 
   fuzzerop::OpDescriptor Descr = fuzzerop::insertValueDescriptor(1);
 
-  std::vector<Type *> Types = {Type::getInt8Ty(Ctx), Type::getInt32Ty(Ctx),
+  std::array<Type *, 3> Types = {Type::getInt8Ty(Ctx), Type::getInt32Ty(Ctx),
                                  Type::getInt64Ty(Ctx)};
   RandomIRBuilder IB(Seed, Types);
 
   // Get first basic block of the first function
   Function &F = *M->begin();
   BasicBlock &BB = *F.begin();
 
   // Pick first source
   Instruction *Source = &*std::next(BB.begin());
const char *SourceCode =
       "normal:\n"
       "  ret ptr %val\n"
       "exceptional:\n"
       "  %landing_pad4 = landingpad token cleanup\n"
       "  ret ptr undef\n"
       "}";
   auto M = parseAssembly(SourceCode, Ctx);
 
-  std::vector<Type *> Types = {Type::getInt8Ty(Ctx)};
+  std::array<Type *, 1> Types = {Type::getInt8Ty(Ctx)};
   RandomIRBuilder IB(Seed, Types);
 
   // Get first basic block of the test function
   Function &F = *M->getFunction("test");
   BasicBlock &BB = *F.begin();
 
   Instruction *Invoke = &*BB.begin();
 
   // Find source but never insert new load after invoke
   for (int i = 0; i < 10; ++i) {
     (void)IB.findOrCreateSource(BB, {Invoke}, {}, fuzzerop::anyIntType());
     ASSERT_TRUE(!verifyModule(*M, &errs()));
   }
 }
 
 TEST(RandomIRBuilderTest, SwiftError) {
   // Check that we never pick swifterror value as a source for operation
   // other than load, store and call.
 
   LLVMContext Ctx;
   const char *SourceCode = "declare void @use(ptr swifterror %err)"
                            "define void @test() {\n"
                            "entry:\n"
                            "  %err = alloca swifterror ptr, align 8\n"
                            "  call void @use(ptr swifterror %err)\n"
                            "  ret void\n"
                            "}";
   auto M = parseAssembly(SourceCode, Ctx);
 
-  std::vector<Type *> Types = {Type::getInt8Ty(Ctx)};
+  std::array<Type *, 1> Types = {Type::getInt8Ty(Ctx)};
   RandomIRBuilder IB(Seed, Types);
 
   // Get first basic block of the test function
   Function &F = *M->getFunction("test");
   BasicBlock &BB = *F.begin();
   Instruction *Alloca = &*BB.begin();
 
   fuzzerop::OpDescriptor Descr = fuzzerop::gepDescriptor(1);
Default:  \n\
       %CAnd = and i1 %C1, %C2 \n\
       br i1 %CIEqJ, label %Default, label %Exit \n\
     OnOne:  \n\
       br i1 %C1, label %OnOne, label %Exit \n\
     Exit:  \n\
       ret void \n\
     }";
 
-  std::vector<Type *> Types = {Type::getInt32Ty(Ctx), Type::getInt1Ty(Ctx)};
+  std::array<Type *, 2> Types = {Type::getInt32Ty(Ctx), Type::getInt1Ty(Ctx)};
   RandomIRBuilder IB(Seed, Types);
   for (int i = 0; i < 20; i++) {
     std::unique_ptr<Module> M = parseAssembly(SourceCode, Ctx);
     Function &F = *M->getFunction("test");
     auto RS = makeSampler(IB.Rand, make_pointer_range(F));
     BasicBlock *BB = RS.getSelection();
     SmallVector<Instruction *, 32> Insts;
     for (auto I = BB->getFirstInsertionPt(), E = BB->end(); I != E; ++I)
       Insts.push_back(&*I);
     if (Insts.size() < 2)
       continue;
     // Choose an instruction and connect to later operations.
     size_t IP = uniform<size_t>(IB.Rand, 1, Insts.size() - 1);
     Instruction *Inst = Insts[IP - 1];
     auto ConnectAfter = ArrayRef(Insts).slice(IP);
     IB.connectToSink(*BB, ConnectAfter, Inst);
     ASSERT_FALSE(verifyModule(*M, &errs()));
   }
 }
 
+TEST(RandomIRBuilderTest, createStackMemory) {
+  LLVMContext Ctx;
+  const char *SourceCode = "\n\
+    define void @test(i1 %C1, i1 %C2, i32 %I, i32 %J) { \n\
+    Entry:  \n\
+      ret void \n\
+    }";
+  Type *Int32Ty = Type::getInt32Ty(Ctx);
+  Constant *Int32_1 = ConstantInt::get(Int32Ty, APInt(32, 1));
+  Type *Int64Ty = Type::getInt64Ty(Ctx);
+  Constant *Int64_42 = ConstantInt::get(Int64Ty, APInt(64, 42));
+  Type *DoubleTy = Type::getDoubleTy(Ctx);
+  Constant *Double_0 =
+      ConstantFP::get(Ctx, APFloat::getZero(DoubleTy->getFltSemantics()));
+  std::array<Type *, 8> Types = {
+      Int32Ty,
+      Int64Ty,
+      DoubleTy,
+      PointerType::get(Ctx, 0),
+      PointerType::get(Int32Ty, 0),
+      VectorType::get(Int32Ty, 4, false),
+      StructType::create({Int32Ty, DoubleTy, Int64Ty}),
+      ArrayType::get(Int64Ty, 4),
+  };
+  std::array<Value *, 8> Inits = {
+      Int32_1,
+      Int64_42,
+      Double_0,
+      UndefValue::get(Types[3]),
+      UndefValue::get(Types[4]),
+      ConstantVector::get({Int32_1, Int32_1, Int32_1, Int32_1}),
+      ConstantStruct::get(cast<StructType>(Types[6]),
+                          {Int32_1, Double_0, Int64_42}),
+      ConstantArray::get(cast<ArrayType>(Types[7]),
+                         {Int64_42, Int64_42, Int64_42, Int64_42}),
+  };
+  ASSERT_EQ(Types.size(), Inits.size());
+  unsigned NumTests = Types.size();
+  RandomIRBuilder IB(Seed, Types);
+  auto CreateStackMemoryAndVerify = [&Ctx, &SourceCode, &IB](Type *Ty,
+                                                             Value *Init) {
+    std::unique_ptr<Module> M = parseAssembly(SourceCode, Ctx);
+    Function &F = *M->getFunction("test");
+    // Create stack memory without initializer.
+    IB.createStackMemory(&F, Ty, nullptr);
+    // Create stack memory with initializer.
+    IB.createStackMemory(&F, Ty, Init);
+    EXPECT_FALSE(verifyModule(*M, &errs()));
+  };
+  for (unsigned i = 0; i < NumTests; i++) {
+    CreateStackMemoryAndVerify(Types[i], Inits[i]);
+  }
+}
+
+TEST(RandomIRBuilderTest, findOrCreateGlobalVariable) {
+  LLVMContext Ctx;
+  const char *SourceCode = "\n\
+    @G0 = external global i16 \n\
+    @G1 = global i32 1 \n\
+  ";
+  std::array<Type *, 3> Types = {Type::getInt16Ty(Ctx), Type::getInt32Ty(Ctx),
+                                 Type::getInt64Ty(Ctx)};
+  RandomIRBuilder IB(Seed, Types);
+
+  // Find external global
+  std::unique_ptr<Module> M0 = parseAssembly(SourceCode, Ctx);
+  Type *ExternalTy = M0->globals().begin()->getValueType();
+  ASSERT_TRUE(ExternalTy->isIntegerTy(16));
+  IB.findOrCreateGlobalVariable(&*M0, {}, fuzzerop::onlyType(Types[0]));
+  ASSERT_FALSE(verifyModule(*M0, &errs()));
+  unsigned NumGV0 = M0->getNumNamedValues();
+  auto [GV0, DidCreate0] =
+      IB.findOrCreateGlobalVariable(&*M0, {}, fuzzerop::onlyType(Types[0]));
+  ASSERT_FALSE(verifyModule(*M0, &errs()));
+  ASSERT_EQ(M0->getNumNamedValues(), NumGV0 + DidCreate0);
+
+  // Find existing global
+  std::unique_ptr<Module> M1 = parseAssembly(SourceCode, Ctx);
+  IB.findOrCreateGlobalVariable(&*M1, {}, fuzzerop::onlyType(Types[1]));
+  ASSERT_FALSE(verifyModule(*M1, &errs()));
+  unsigned NumGV1 = M1->getNumNamedValues();
+  auto [GV1, DidCreate1] =
+      IB.findOrCreateGlobalVariable(&*M1, {}, fuzzerop::onlyType(Types[1]));
+  ASSERT_FALSE(verifyModule(*M1, &errs()));
+  ASSERT_EQ(M1->getNumNamedValues(), NumGV1 + DidCreate1);
+
+  // Create new global
+  std::unique_ptr<Module> M2 = parseAssembly(SourceCode, Ctx);
+  auto [GV2, DidCreate2] =
+      IB.findOrCreateGlobalVariable(&*M2, {}, fuzzerop::onlyType(Types[2]));
+  ASSERT_FALSE(verifyModule(*M2, &errs()));
+  ASSERT_TRUE(DidCreate2);
+}
+
+/// Checks if the source and sink we find for an instruction has correct
+/// domination relation.
+TEST(RandomIRBuilderTest, findSourceAndSink) {
+  const char *Source = "\n\
+        define i64 @test(i1 %0, i1 %1, i1 %2, i32 %3, i32 %4) { \n\
+        Entry:  \n\
+          %A = alloca i32, i32 8, align 4 \n\
+          %E.1 = and i32 %3, %4 \n\
+          %E.2 = add i32 %4 , 1 \n\
+          %A.GEP.1 = getelementptr i32, ptr %A, i32 0 \n\
+          %A.GEP.2 = getelementptr i32, ptr %A.GEP.1, i32 1 \n\
+          %L.2 = load i32, ptr %A.GEP.2 \n\
+          %L.1 = load i32, ptr %A.GEP.1 \n\
+          %E.3 = sub i32 %E.2, %L.1 \n\
+          %Cond.1 = icmp eq i32 %E.3, %E.2 \n\
+          %Cond.2 = and i1 %0, %1 \n\
+          %Cond = or i1 %Cond.1, %Cond.2 \n\
+          br i1 %Cond, label %BB0, label %BB1  \n\
+        BB0:  \n\
+          %Add = add i32 %L.1, %L.2 \n\
+          %Sub = sub i32 %L.1, %L.2 \n\
+          %Sub.1 = sub i32 %Sub, 12 \n\
+          %Cast.1 = bitcast i32 %4 to float \n\
+          %Add.2 = add i32 %3, 1 \n\
+          %Cast.2 = bitcast i32 %Add.2 to float \n\
+          %FAdd = fadd float %Cast.1, %Cast.2 \n\
+          %Add.3 = add i32 %L.2, %L.1 \n\
+          %Cast.3 = bitcast float %FAdd to i32 \n\
+          %Sub.2 = sub i32 %Cast.3, %Sub.1 \n\
+          %SExt = sext i32 %Cast.3 to i64 \n\
+          %A.GEP.3 = getelementptr i64, ptr %A, i32 1 \n\
+          store i64 %SExt, ptr %A.GEP.3 \n\
+          br label %Exit  \n\
+        BB1:  \n\
+          %PHI.1 = phi i32 [0, %Entry] \n\
+          %SExt.1 = sext i1 %Cond.2 to i32 \n\
+          %SExt.2 = sext i1 %Cond.1 to i32 \n\
+          %E.164 = zext i32 %E.1 to i64 \n\
+          %E.264 = zext i32 %E.2 to i64 \n\
+          %E.1264 = mul i64 %E.164, %E.264 \n\
+          %E.12 = trunc i64 %E.1264 to i32 \n\
+          %A.GEP.4 = getelementptr i32, ptr %A, i32 2 \n\
+          %A.GEP.5 = getelementptr i32, ptr %A.GEP.4, i32 2 \n\
+          store i32 %E.12, ptr %A.GEP.5 \n\
+          br label %Exit  \n\
+        Exit:  \n\
+          %PHI.2 = phi i32 [%Add, %BB0], [%E.3, %BB1] \n\
+          %PHI.3 = phi i64 [%SExt, %BB0], [%E.1264, %BB1] \n\
+          %ZExt = zext i32 %PHI.2 to i64 \n\
+          %Add.5 = add i64 %PHI.3, 3 \n\
+          ret i64 %Add.5  \n\
+      }";
+  LLVMContext Ctx;
+  std::array<Type *, 3> Types = {Type::getInt1Ty(Ctx), Type::getInt32Ty(Ctx),
+                                 Type::getInt64Ty(Ctx)};
+  std::mt19937 mt(Seed);
+  std::uniform_int_distribution<int> RandInt(INT_MIN, INT_MAX);
+
+  // Get a random instruction, try to find source and sink, make sure it is
+  // dominated.
+  for (int i = 0; i < 100; i++) {
+    RandomIRBuilder IB(RandInt(mt), Types);
+    std::unique_ptr<Module> M = parseAssembly(Source, Ctx);
+    Function &F = *M->getFunction("test");
+    DominatorTree DT(F);
+    BasicBlock *BB = makeSampler(IB.Rand, make_pointer_range(F)).getSelection();
+    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, 1, Insts.size() - 2);
+
+    auto InstsBefore = ArrayRef(Insts).slice(0, IP);
+    auto InstsAfter = ArrayRef(Insts).slice(IP);
+    Value *Src = IB.findOrCreateSource(
+        *BB, InstsBefore, {}, fuzzerop::onlyType(Types[i % Types.size()]));
+    ASSERT_TRUE(DT.dominates(Src, Insts[IP + 1]));
+    Instruction *Sink = IB.connectToSink(*BB, InstsAfter, Insts[IP - 1]);
+    if (!DT.dominates(Insts[IP - 1], Sink)) {
+      errs() << *Insts[IP - 1] << "\n" << *Sink << "\n ";
+    }
+    ASSERT_TRUE(DT.dominates(Insts[IP - 1], Sink));
+  }
+}
+TEST(RandomIRBuilderTest, sinkToInstrinsic) {
+  const char *Source = "\n\
+        declare double @llvm.sqrt.f64(double %Val)  \n\
+        declare void   @llvm.ubsantrap(i8 immarg) cold noreturn nounwind  \n\
+        \n\
+        define double @test(double %0, double %1, i64 %2, i64 %3, i64 %4, i8 %5) {  \n\
+        Entry:   \n\
+            %sqrt = call double @llvm.sqrt.f64(double %0)  \n\
+            call void @llvm.ubsantrap(i8 1)  \n\
+            ret double %sqrt \n\
+        }";
+  LLVMContext Ctx;
+  std::array<Type *, 3> Types = {Type::getInt8Ty(Ctx), Type::getInt64Ty(Ctx),
+                                 Type::getDoubleTy(Ctx)};
+  std::mt19937 mt(Seed);
+  std::uniform_int_distribution<int> RandInt(INT_MIN, INT_MAX);
+
+  RandomIRBuilder IB(RandInt(mt), Types);
+  std::unique_ptr<Module> M = parseAssembly(Source, Ctx);
+  Function &F = *M->getFunction("test");
+  BasicBlock &BB = F.getEntryBlock();
+  bool Modified = false;
+
+  Instruction *I = &*BB.begin();
+  for (int i = 0; i < 20; i++) {
+    Value *OldOperand = I->getOperand(0);
+    Value *Src = F.getArg(1);
+    IB.connectToSink(BB, {I}, Src);
+    Value *NewOperand = I->getOperand(0);
+    Modified |= (OldOperand != NewOperand);
+    ASSERT_FALSE(verifyModule(*M, &errs()));
+  }
+  ASSERT_TRUE(Modified);
+
+  Modified = false;
+  I = I->getNextNonDebugInstruction();
+  for (int i = 0; i < 20; i++) {
+    Value *OldOperand = I->getOperand(0);
+    Value *Src = F.getArg(5);
+    IB.connectToSink(BB, {I}, Src);
+    Value *NewOperand = I->getOperand(0);
+    Modified |= (OldOperand != NewOperand);
+    ASSERT_FALSE(verifyModule(*M, &errs()));
+  }
+  ASSERT_FALSE(Modified);
+}
 } // namespace