llvm/lib/FuzzMutate/RandomIRBuilder.cpp

   1 //===-- RandomIRBuilder.cpp -----------------------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "llvm/FuzzMutate/RandomIRBuilder.h"
  10 #include "llvm/ADT/STLExtras.h"
  11 #include "llvm/FuzzMutate/OpDescriptor.h"
  12 #include "llvm/FuzzMutate/Random.h"
  13 #include "llvm/IR/BasicBlock.h"
  14 #include "llvm/IR/Constants.h"
  15 #include "llvm/IR/DataLayout.h"
  16 #include "llvm/IR/Dominators.h"
  17 #include "llvm/IR/Function.h"
  18 #include "llvm/IR/Instructions.h"
  19 #include "llvm/IR/IntrinsicInst.h"
  20 #include "llvm/IR/Module.h"
  21
  22 using namespace llvm;
  23 using namespace fuzzerop;
  24
  25 /// Return a vector of Blocks that dominates this block, excluding current
  26 /// block.
  27 static std::vector<BasicBlock *> getDominators(BasicBlock *BB) {
  28   std::vector<BasicBlock *> ret;
  29   DominatorTree DT(*BB->getParent());
  30   DomTreeNode *Node = DT[BB]->getIDom();
  31   while (Node && Node->getBlock()) {
  32     ret.push_back(Node->getBlock());
  33     // Get parent block.
  34     Node = Node->getIDom();
  35   }
  36   return ret;
  37 }
  38
  39 /// Return a vector of Blocks that is dominated by this block, excluding current
  40 /// block
  41 static std::vector<BasicBlock *> getDominatees(BasicBlock *BB) {
  42   DominatorTree DT(*BB->getParent());
  43   std::vector<BasicBlock *> ret;
  44   for (DomTreeNode *Child : DT[BB]->children())
  45     ret.push_back(Child->getBlock());
  46   uint64_t Idx = 0;
  47   while (Idx < ret.size()) {
  48     DomTreeNode *Node = DT[ret[Idx]];
  49     Idx++;
  50     for (DomTreeNode *Child : Node->children())
  51       ret.push_back(Child->getBlock());
  52   }
  53   return ret;
  54 }
  55
  56 AllocaInst *RandomIRBuilder::createStackMemory(Function *F, Type *Ty,
  57                                                Value *Init) {
  58   /// TODO: For all Allocas, maybe allocate an array.
  59   BasicBlock *EntryBB = &F->getEntryBlock();
  60   DataLayout DL(F->getParent());
  61   AllocaInst *Alloca = new AllocaInst(Ty, DL.getAllocaAddrSpace(), "A",
  62                                       &*EntryBB->getFirstInsertionPt());
  63   if (Init)
  64     new StoreInst(Init, Alloca, Alloca->getNextNode());
  65   return Alloca;
  66 }
  67
  68 std::pair<GlobalVariable *, bool>
  69 RandomIRBuilder::findOrCreateGlobalVariable(Module *M, ArrayRef<Value *> Srcs,
  70                                             fuzzerop::SourcePred Pred) {
  71   auto MatchesPred = [&Srcs, &Pred](GlobalVariable *GV) {
  72     // Can't directly compare GV's type, as it would be a pointer to the actual
  73     // type.
  74     return Pred.matches(Srcs, UndefValue::get(GV->getValueType()));
  75   };
  76   bool DidCreate = false;
  77   SmallVector<GlobalVariable *, 4> GlobalVars;
  78   for (GlobalVariable &GV : M->globals()) {
  79     GlobalVars.push_back(&GV);
  80   }
  81   auto RS = makeSampler(Rand, make_filter_range(GlobalVars, MatchesPred));
  82   RS.sample(nullptr, 1);
  83   GlobalVariable *GV = RS.getSelection();
  84   if (!GV) {
  85     DidCreate = true;
  86     using LinkageTypes = GlobalVariable::LinkageTypes;
  87     auto TRS = makeSampler<Constant *>(Rand);
  88     TRS.sample(Pred.generate(Srcs, KnownTypes));
  89     Constant *Init = TRS.getSelection();
  90     Type *Ty = Init->getType();
  91     GV = new GlobalVariable(*M, Ty, false, LinkageTypes::ExternalLinkage, Init,
  92                             "G", nullptr,
  93                             GlobalValue::ThreadLocalMode::NotThreadLocal,
  94                             M->getDataLayout().getDefaultGlobalsAddressSpace());
  95   }
  96   return {GV, DidCreate};
  97 }
  98
  99 Value *RandomIRBuilder::findOrCreateSource(BasicBlock &BB,
 100                                            ArrayRef<Instruction *> Insts) {
 101   return findOrCreateSource(BB, Insts, {}, anyType());
 102 }
 103
 104 Value *RandomIRBuilder::findOrCreateSource(BasicBlock &BB,
 105                                            ArrayRef<Instruction *> Insts,
 106                                            ArrayRef<Value *> Srcs,
 107                                            SourcePred Pred,
 108                                            bool allowConstant) {
 109   auto MatchesPred = [&Srcs, &Pred](Value *V) { return Pred.matches(Srcs, V); };
 110   SmallVector<uint64_t, 8> SrcTys;
 111   for (uint64_t i = 0; i < EndOfValueSource; i++)
 112     SrcTys.push_back(i);
 113   std::shuffle(SrcTys.begin(), SrcTys.end(), Rand);
 114   for (uint64_t SrcTy : SrcTys) {
 115     switch (SrcTy) {
 116     case SrcFromInstInCurBlock: {
 117       auto RS = makeSampler(Rand, make_filter_range(Insts, MatchesPred));
 118       if (!RS.isEmpty()) {
 119         return RS.getSelection();
 120       }
 121       break;
 122     }
 123     case FunctionArgument: {
 124       Function *F = BB.getParent();
 125       SmallVector<Argument *, 8> Args;
 126       for (uint64_t i = 0; i < F->arg_size(); i++) {
 127         Args.push_back(F->getArg(i));
 128       }
 129       auto RS = makeSampler(Rand, make_filter_range(Args, MatchesPred));
 130       if (!RS.isEmpty()) {
 131         return RS.getSelection();
 132       }
 133       break;
 134     }
 135     case InstInDominator: {
 136       auto Dominators = getDominators(&BB);
 137       std::shuffle(Dominators.begin(), Dominators.end(), Rand);
 138       for (BasicBlock *Dom : Dominators) {
 139         SmallVector<Instruction *, 16> Instructions;
 140         for (Instruction &I : *Dom) {
 141           Instructions.push_back(&I);
 142         }
 143         auto RS =
 144             makeSampler(Rand, make_filter_range(Instructions, MatchesPred));
 145         // Also consider choosing no source, meaning we want a new one.
 146         if (!RS.isEmpty()) {
 147           return RS.getSelection();
 148         }
 149       }
 150       break;
 151     }
 152     case SrcFromGlobalVariable: {
 153       Module *M = BB.getParent()->getParent();
 154       auto [GV, DidCreate] = findOrCreateGlobalVariable(M, Srcs, Pred);
 155       Type *Ty = GV->getValueType();
 156       LoadInst *LoadGV = nullptr;
 157       if (BB.getTerminator()) {
 158         LoadGV = new LoadInst(Ty, GV, "LGV", &*BB.getFirstInsertionPt());
 159       } else {
 160         LoadGV = new LoadInst(Ty, GV, "LGV", &BB);
 161       }
 162       // Because we might be generating new values, we have to check if it
 163       // matches again.
 164       if (DidCreate) {
 165         if (Pred.matches(Srcs, LoadGV)) {
 166           return LoadGV;
 167         }
 168         LoadGV->eraseFromParent();
 169         // If no one is using this GlobalVariable, delete it too.
 170         if (GV->use_empty()) {
 171           GV->eraseFromParent();
 172         }
 173       }
 174       break;
 175     }
 176     case NewConstOrStack: {
 177       return newSource(BB, Insts, Srcs, Pred, allowConstant);
 178     }
 179     default:
 180     case EndOfValueSource: {
 181       llvm_unreachable("EndOfValueSource executed");
 182     }
 183     }
 184   }
 185   llvm_unreachable("Can't find a source");
 186 }
 187
 188 Value *RandomIRBuilder::newSource(BasicBlock &BB, ArrayRef<Instruction *> Insts,
 189                                   ArrayRef<Value *> Srcs, SourcePred Pred,
 190                                   bool allowConstant) {
 191   // Generate some constants to choose from.
 192   auto RS = makeSampler<Value *>(Rand);
 193   RS.sample(Pred.generate(Srcs, KnownTypes));
 194
 195   // If we can find a pointer to load from, use it half the time.
 196   Value *Ptr = findPointer(BB, Insts, Srcs, Pred);
 197   if (Ptr) {
 198     // Create load from the chosen pointer
 199     auto IP = BB.getFirstInsertionPt();
 200     if (auto *I = dyn_cast<Instruction>(Ptr)) {
 201       IP = ++I->getIterator();
 202       assert(IP != BB.end() && "guaranteed by the findPointer");
 203     }
 204     // For opaque pointers, pick the type independently.
 205     Type *AccessTy = Ptr->getType()->isOpaquePointerTy()
 206                          ? RS.getSelection()->getType()
 207                          : Ptr->getType()->getNonOpaquePointerElementType();
 208     auto *NewLoad = new LoadInst(AccessTy, Ptr, "L", &*IP);
 209
 210     // Only sample this load if it really matches the descriptor
 211     if (Pred.matches(Srcs, NewLoad))
 212       RS.sample(NewLoad, RS.totalWeight());
 213     else
 214       NewLoad->eraseFromParent();
 215   }
 216
 217   Value *newSrc = RS.getSelection();
 218   // Generate a stack alloca and store the constant to it if constant is not
 219   // allowed, our hope is that later mutations can generate some values and
 220   // store to this placeholder.
 221   if (!allowConstant && isa<Constant>(newSrc)) {
 222     Type *Ty = newSrc->getType();
 223     Function *F = BB.getParent();
 224     AllocaInst *Alloca = createStackMemory(F, Ty, newSrc);
 225     if (BB.getTerminator()) {
 226       newSrc = new LoadInst(Ty, Alloca, /*ArrLen,*/ "L", BB.getTerminator());
 227     } else {
 228       newSrc = new LoadInst(Ty, Alloca, /*ArrLen,*/ "L", &BB);
 229     }
 230   }
 231   return newSrc;
 232 }
 233
 234 static bool isCompatibleReplacement(const Instruction *I, const Use &Operand,
 235                                     const Value *Replacement) {
 236   unsigned int OperandNo = Operand.getOperandNo();
 237   if (Operand->getType() != Replacement->getType())
 238     return false;
 239   switch (I->getOpcode()) {
 240   case Instruction::GetElementPtr:
 241   case Instruction::ExtractElement:
 242   case Instruction::ExtractValue:
 243     // TODO: We could potentially validate these, but for now just leave indices
 244     // alone.
 245     if (OperandNo >= 1)
 246       return false;
 247     break;
 248   case Instruction::InsertValue:
 249   case Instruction::InsertElement:
 250   case Instruction::ShuffleVector:
 251     if (OperandNo >= 2)
 252       return false;
 253     break;
 254   // For Br/Switch, we only try to modify the 1st Operand (condition).
 255   // Modify other operands, like switch case may accidently change case from
 256   // ConstantInt to a register, which is illegal.
 257   case Instruction::Switch:
 258   case Instruction::Br:
 259     if (OperandNo >= 1)
 260       return false;
 261     break;
 262   case Instruction::Call:
 263   case Instruction::Invoke:
 264   case Instruction::CallBr: {
 265     const Function *Callee = cast<CallBase>(I)->getCalledFunction();
 266     // If it's an indirect call, give up.
 267     if (!Callee)
 268       return false;
 269     // If callee is not an intrinsic, operand 0 is the function to be called.
 270     // Since we cannot assume that the replacement is a function pointer,
 271     // we give up.
 272     if (!Callee->getIntrinsicID() && OperandNo == 0)
 273       return false;
 274     return !Callee->hasParamAttribute(OperandNo, Attribute::ImmArg);
 275   }
 276   default:
 277     break;
 278   }
 279   return true;
 280 }
 281
 282 Instruction *RandomIRBuilder::connectToSink(BasicBlock &BB,
 283                                             ArrayRef<Instruction *> Insts,
 284                                             Value *V) {
 285   SmallVector<uint64_t, 8> SinkTys;
 286   for (uint64_t i = 0; i < EndOfValueSink; i++)
 287     SinkTys.push_back(i);
 288   std::shuffle(SinkTys.begin(), SinkTys.end(), Rand);
 289   auto findSinkAndConnect =
 290       [this, V](ArrayRef<Instruction *> Instructions) -> Instruction * {
 291     auto RS = makeSampler<Use *>(Rand);
 292     for (auto &I : Instructions) {
 293       for (Use &U : I->operands())
 294         if (isCompatibleReplacement(I, U, V))
 295           RS.sample(&U, 1);
 296     }
 297     if (!RS.isEmpty()) {
 298       Use *Sink = RS.getSelection();
 299       User *U = Sink->getUser();
 300       unsigned OpNo = Sink->getOperandNo();
 301       U->setOperand(OpNo, V);
 302       return cast<Instruction>(U);
 303     }
 304     return nullptr;
 305   };
 306   Instruction *Sink = nullptr;
 307   for (uint64_t SinkTy : SinkTys) {
 308     switch (SinkTy) {
 309     case SinkToInstInCurBlock:
 310       Sink = findSinkAndConnect(Insts);
 311       if (Sink)
 312         return Sink;
 313       break;
 314     case PointersInDominator: {
 315       auto Dominators = getDominators(&BB);
 316       std::shuffle(Dominators.begin(), Dominators.end(), Rand);
 317       for (BasicBlock *Dom : Dominators) {
 318         for (Instruction &I : *Dom) {
 319           if (isa<PointerType>(I.getType()))
 320             return new StoreInst(V, &I, Insts.back());
 321         }
 322       }
 323       break;
 324     }
 325     case InstInDominatee: {
 326       auto Dominatees = getDominatees(&BB);
 327       std::shuffle(Dominatees.begin(), Dominatees.end(), Rand);
 328       for (BasicBlock *Dominee : Dominatees) {
 329         std::vector<Instruction *> Instructions;
 330         for (Instruction &I : *Dominee)
 331           Instructions.push_back(&I);
 332         Sink = findSinkAndConnect(Instructions);
 333         if (Sink) {
 334           return Sink;
 335         }
 336       }
 337       break;
 338     }
 339     case NewStore:
 340       /// TODO: allocate a new stack memory.
 341       return newSink(BB, Insts, V);
 342     case SinkToGlobalVariable: {
 343       Module *M = BB.getParent()->getParent();
 344       auto [GV, DidCreate] =
 345           findOrCreateGlobalVariable(M, {}, fuzzerop::onlyType(V->getType()));
 346       return new StoreInst(V, GV, Insts.back());
 347     }
 348     case EndOfValueSink:
 349     default:
 350       llvm_unreachable("EndOfValueSink executed");
 351     }
 352   }
 353   llvm_unreachable("Can't find a sink");
 354 }
 355
 356 Instruction *RandomIRBuilder::newSink(BasicBlock &BB,
 357                                       ArrayRef<Instruction *> Insts, Value *V) {
 358   Value *Ptr = findPointer(BB, Insts, {V}, matchFirstType());
 359   if (!Ptr) {
 360     if (uniform(Rand, 0, 1)) {
 361       Type *Ty = V->getType();
 362       Ptr = createStackMemory(BB.getParent(), Ty, UndefValue::get(Ty));
 363     } else {
 364       Ptr = UndefValue::get(PointerType::get(V->getType(), 0));
 365     }
 366   }
 367
 368   return new StoreInst(V, Ptr, Insts.back());
 369 }
 370
 371 Value *RandomIRBuilder::findPointer(BasicBlock &BB,
 372                                     ArrayRef<Instruction *> Insts,
 373                                     ArrayRef<Value *> Srcs, SourcePred Pred) {
 374   auto IsMatchingPtr = [&Srcs, &Pred](Instruction *Inst) {
 375     // Invoke instructions sometimes produce valid pointers but currently
 376     // we can't insert loads or stores from them
 377     if (Inst->isTerminator())
 378       return false;
 379
 380     if (auto *PtrTy = dyn_cast<PointerType>(Inst->getType())) {
 381       if (PtrTy->isOpaque())
 382         return true;
 383
 384       // We can never generate loads from non first class or non sized types
 385       Type *ElemTy = PtrTy->getNonOpaquePointerElementType();
 386       if (!ElemTy->isSized() || !ElemTy->isFirstClassType())
 387         return false;
 388
 389       // TODO: Check if this is horribly expensive.
 390       return Pred.matches(Srcs, UndefValue::get(ElemTy));
 391     }
 392     return false;
 393   };
 394   if (auto RS = makeSampler(Rand, make_filter_range(Insts, IsMatchingPtr)))
 395     return RS.getSelection();
 396   return nullptr;
 397 }
 398
 399 Type *RandomIRBuilder::randomType() {
 400   uint64_t TyIdx = uniform<uint64_t>(Rand, 0, KnownTypes.size() - 1);
 401   return KnownTypes[TyIdx];
 402 }
 403
 404 Function *RandomIRBuilder::createFunctionDeclaration(Module &M,
 405                                                      uint64_t ArgNum) {
 406   Type *RetType = randomType();
 407
 408   SmallVector<Type *, 2> Args;
 409   for (uint64_t i = 0; i < ArgNum; i++) {
 410     Args.push_back(randomType());
 411   }
 412
 413   Function *F = Function::Create(FunctionType::get(RetType, Args,
 414                                                    /*isVarArg=*/false),
 415                                  GlobalValue::ExternalLinkage, "f", &M);
 416   return F;
 417 }
 418 Function *RandomIRBuilder::createFunctionDeclaration(Module &M) {
 419   return createFunctionDeclaration(
 420       M, uniform<uint64_t>(Rand, MinArgNum, MaxArgNum));
 421 }
 422
 423 Function *RandomIRBuilder::createFunctionDefinition(Module &M,
 424                                                     uint64_t ArgNum) {
 425   Function *F = this->createFunctionDeclaration(M, ArgNum);
 426
 427   // TODO: Some arguments and a return value would probably be more
 428   // interesting.
 429   LLVMContext &Context = M.getContext();
 430   DataLayout DL(&M);
 431   BasicBlock *BB = BasicBlock::Create(Context, "BB", F);
 432   Type *RetTy = F->getReturnType();
 433   if (RetTy != Type::getVoidTy(Context)) {
 434     Instruction *RetAlloca =
 435         new AllocaInst(RetTy, DL.getAllocaAddrSpace(), "RP", BB);
 436     Instruction *RetLoad = new LoadInst(RetTy, RetAlloca, "", BB);
 437     ReturnInst::Create(Context, RetLoad, BB);
 438   } else {
 439     ReturnInst::Create(Context, BB);
 440   }
 441
 442   return F;
 443 }
 444 Function *RandomIRBuilder::createFunctionDefinition(Module &M) {
 445   return createFunctionDefinition(
 446       M, uniform<uint64_t>(Rand, MinArgNum, MaxArgNum));
 447 }