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 @@ -114,10 +114,16 @@ return *RS; } +static inline iterator_range +getInsertionRange(BasicBlock &BB) { + auto End = BB.getTerminatingMustTailCall() ? std::prev(BB.end()) : BB.end(); + return make_range(BB.getFirstInsertionPt(), End); +} + void InjectorIRStrategy::mutate(BasicBlock &BB, RandomIRBuilder &IB) { SmallVector Insts; - for (auto I = BB.getFirstInsertionPt(), E = BB.end(); I != E; ++I) - Insts.push_back(&*I); + for (Instruction &I : getInsertionRange(BB)) + Insts.push_back(&I); if (Insts.size() < 1) return; @@ -360,6 +366,10 @@ auto RS = makeSampler(IB.Rand, Functions); Function *F = RS.getSelection(); + // Some functions accept metadata type or token type as arguments. + // We don't call those functions for now. + // For example, `@llvm.dbg.declare(metadata, metadata, metadata)` + // https://llvm.org/docs/SourceLevelDebugging.html#llvm-dbg-declare auto IsUnsupportedTy = [](Type *T) { return T->isMetadataTy() || T->isTokenTy(); }; @@ -385,7 +395,7 @@ }; SmallVector Insts; - for (Instruction &I : make_range(BB.getFirstInsertionPt(), BB.end())) + for (Instruction &I : getInsertionRange(BB)) Insts.push_back(&I); if (Insts.size() < 1) return; @@ -411,7 +421,7 @@ void InsertCFGStrategy::mutate(BasicBlock &BB, RandomIRBuilder &IB) { SmallVector Insts; - for (Instruction &I : make_range(BB.getFirstInsertionPt(), BB.end())) + for (Instruction &I : getInsertionRange(BB)) Insts.push_back(&I); if (Insts.size() < 1) return; @@ -551,7 +561,7 @@ PHI->addIncoming(Src, Pred); } SmallVector InstsAfter; - for (Instruction &I : make_range(BB.getFirstInsertionPt(), BB.end())) + for (Instruction &I : getInsertionRange(BB)) InstsAfter.push_back(&I); IB.connectToSink(BB, InstsAfter, PHI); } @@ -563,7 +573,7 @@ } void SinkInstructionStrategy::mutate(BasicBlock &BB, RandomIRBuilder &IB) { SmallVector Insts; - for (Instruction &I : make_range(BB.getFirstInsertionPt(), BB.end())) + for (Instruction &I : getInsertionRange(BB)) Insts.push_back(&I); if (Insts.size() < 1) return; @@ -572,9 +582,9 @@ Instruction *Inst = Insts[Idx]; // `Idx + 1` so we don't sink to ourselves. auto InstsAfter = ArrayRef(Insts).slice(Idx + 1); - LLVMContext &C = BB.getParent()->getParent()->getContext(); - // Don't sink terminators, void function calls, etc. - if (Inst->getType() != Type::getVoidTy(C)) + Type *Ty = Inst->getType(); + // Don't sink terminators, void function calls, token, etc. + if (!Ty->isVoidTy() && !Ty->isTokenTy()) // Find a new sink and wire up the results of the operation. IB.connectToSink(BB, InstsAfter, Inst); } diff --git a/llvm/lib/FuzzMutate/RandomIRBuilder.cpp b/llvm/lib/FuzzMutate/RandomIRBuilder.cpp --- a/llvm/lib/FuzzMutate/RandomIRBuilder.cpp +++ b/llvm/lib/FuzzMutate/RandomIRBuilder.cpp @@ -27,7 +27,12 @@ static std::vector getDominators(BasicBlock *BB) { std::vector ret; DominatorTree DT(*BB->getParent()); - DomTreeNode *Node = DT[BB]->getIDom(); + DomTreeNode *Node = DT.getNode(BB); + // It's possible that an orphan block is not in the dom tree. In that case we + // just return nothing. + if (!Node) + return ret; + Node = Node->getIDom(); while (Node && Node->getBlock()) { ret.push_back(Node->getBlock()); // Get parent block. @@ -41,7 +46,12 @@ static std::vector getDominatees(BasicBlock *BB) { DominatorTree DT(*BB->getParent()); std::vector ret; - for (DomTreeNode *Child : DT[BB]->children()) + DomTreeNode *Parent = DT.getNode(BB); + // It's possible that an orphan block is not in the dom tree. In that case we + // just return nothing. + if (!Parent) + return ret; + for (DomTreeNode *Child : Parent->children()) ret.push_back(Child->getBlock()); uint64_t Idx = 0; while (Idx < ret.size()) { diff --git a/llvm/unittests/FuzzMutate/RandomIRBuilderTest.cpp b/llvm/unittests/FuzzMutate/RandomIRBuilderTest.cpp --- a/llvm/unittests/FuzzMutate/RandomIRBuilderTest.cpp +++ b/llvm/unittests/FuzzMutate/RandomIRBuilderTest.cpp @@ -563,4 +563,53 @@ } ASSERT_FALSE(Modified); } + +TEST(RandomIRBuilderTest, SrcAndSinkWOrphanBlock) { + const char *Source = "\n\ + define i1 @test(i1 %Bool, i32 %Int, i64 %Long) { \n\ + Entry: \n\ + %Eq0 = icmp eq i64 %Long, 0 \n\ + br i1 %Eq0, label %True, label %False \n\ + True: \n\ + %Or = or i1 %Bool, %Eq0 \n\ + ret i1 %Or \n\ + False: \n\ + %And = and i1 %Bool, %Eq0 \n\ + ret i1 %And \n\ + Orphan_1: \n\ + %NotBool = sub i1 1, %Bool \n\ + ret i1 %NotBool \n\ + Orphan_2: \n\ + %Le42 = icmp sle i32 %Int, 42 \n\ + ret i1 %Le42 \n\ + }"; + LLVMContext Ctx; + std::mt19937 mt(Seed); + std::uniform_int_distribution RandInt(INT_MIN, INT_MAX); + std::array IntTys( + {Type::getInt64Ty(Ctx), Type::getInt32Ty(Ctx), Type::getInt1Ty(Ctx)}); + std::vector Constants; + for (Type *IntTy : IntTys) { + for (size_t v : {1, 42}) { + Constants.push_back(ConstantInt::get(IntTy, v)); + } + } + for (int i = 0; i < 10; i++) { + RandomIRBuilder IB(RandInt(mt), IntTys); + std::unique_ptr M = parseAssembly(Source, Ctx); + Function &F = *M->getFunction("test"); + for (BasicBlock &BB : F) { + SmallVector Insts; + for (Instruction &I : BB) { + Insts.push_back(&I); + } + for (int j = 0; j < 10; j++) { + IB.findOrCreateSource(BB, Insts); + } + for (Value *V : Constants) { + IB.connectToSink(BB, Insts, V); + } + } + } +} } // namespace 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 @@ -129,6 +129,30 @@ mutateAndVerifyModule(Source, Mutator, 100); } +TEST(InjectorIRStrategyTest, InsertWMustTailCall) { + StringRef Source = "\n\ + define i1 @recursive() { \n\ + Entry: \n\ + %Ret = musttail call i1 @recursive() \n\ + ret i1 %Ret \n\ + }"; + auto Mutator = createInjectorMutator(); + ASSERT_TRUE(Mutator); + mutateAndVerifyModule(Source, Mutator, 100); +} + +TEST(InjectorIRStrategyTest, InsertWTailCall) { + StringRef Source = "\n\ + define i1 @recursive() { \n\ + Entry: \n\ + %Ret = tail call i1 @recursive() \n\ + ret i1 %Ret \n\ + }"; + auto Mutator = createInjectorMutator(); + ASSERT_TRUE(Mutator); + mutateAndVerifyModule(Source, Mutator, 100); +} + TEST(InstDeleterIRStrategyTest, EmptyFunction) { // Test that we don't crash even if we can't remove from one of the functions. @@ -576,6 +600,19 @@ mutateAndVerifyModule(Source); } +TEST(SinkInstructionStrategy, DoNotSinkTokenType) { + StringRef Source = "\n\ + declare ptr @fake_personality_function() \n\ + declare token @llvm.experimental.gc.statepoint.p0(i64 immarg %0, i32 immarg %1, ptr %2, i32 immarg %3, i32 immarg %4, ...) \n\ + define void @test() gc \"statepoint-example\" personality ptr @fake_personality_function { \n\ + Entry: \n\ + %token1 = call token (i64, i32, ptr, i32, i32, ...) \ + @llvm.experimental.gc.statepoint.p0(i64 0, i32 0, ptr elementtype(ptr addrspace(1) ()) undef, i32 0, i32 0, i32 0, i32 0) \n\ + ret void \n\ + }"; + mutateAndVerifyModule(Source); +} + static void VerifyBlockShuffle(StringRef Source) { LLVMContext Ctx; auto Mutator = createMutator();