1 //===-- llvm-stress.cpp - Generate random LL files to stress-test LLVM -----===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This program is a utility that generates random .ll files to stress-test
11 // different components in LLVM.
13 //===----------------------------------------------------------------------===//
14 #include "llvm/LLVMContext.h"
15 #include "llvm/Module.h"
16 #include "llvm/PassManager.h"
17 #include "llvm/Constants.h"
18 #include "llvm/Instruction.h"
19 #include "llvm/CallGraphSCCPass.h"
20 #include "llvm/Assembly/PrintModulePass.h"
21 #include "llvm/Analysis/Verifier.h"
22 #include "llvm/Support/PassNameParser.h"
23 #include "llvm/Support/Debug.h"
24 #include "llvm/Support/ManagedStatic.h"
25 #include "llvm/Support/PluginLoader.h"
26 #include "llvm/Support/PrettyStackTrace.h"
27 #include "llvm/Support/ToolOutputFile.h"
35 static cl::opt<unsigned> SeedCL("seed",
36 cl::desc("Seed used for randomness"), cl::init(0));
37 static cl::opt<unsigned> SizeCL("size",
38 cl::desc("The estimated size of the generated function (# of instrs)"),
40 static cl::opt<std::string>
41 OutputFilename("o", cl::desc("Override output filename"),
42 cl::value_desc("filename"));
44 /// A utility class to provide a pseudo-random number generator which is
45 /// the same across all platforms. This is somewhat close to the libc
46 /// implementation. Note: This is not a cryptographically secure pseudorandom
51 Random(unsigned _seed):Seed(_seed) {}
52 /// Return the next random value.
54 unsigned Val = Seed + 0x000b07a1;
55 Seed = (Val * 0x3c7c0ac1);
56 // Only lowest 19 bits are random-ish.
57 return Seed & 0x7ffff;
64 /// Generate an empty function with a default argument list.
65 Function *GenEmptyFunction(Module *M) {
67 std::vector<Type*> ArgsTy;
68 // Define a few arguments
69 LLVMContext &Context = M->getContext();
70 ArgsTy.push_back(PointerType::get(IntegerType::getInt8Ty(Context), 0));
71 ArgsTy.push_back(PointerType::get(IntegerType::getInt32Ty(Context), 0));
72 ArgsTy.push_back(PointerType::get(IntegerType::getInt64Ty(Context), 0));
73 ArgsTy.push_back(IntegerType::getInt32Ty(Context));
74 ArgsTy.push_back(IntegerType::getInt64Ty(Context));
75 ArgsTy.push_back(IntegerType::getInt8Ty(Context));
77 FunctionType *FuncTy = FunctionType::get(Type::getVoidTy(Context), ArgsTy, 0);
78 // Pick a unique name to describe the input parameters
80 ss<<"autogen_SD"<<SeedCL;
81 Function *Func = Function::Create(FuncTy, GlobalValue::ExternalLinkage,
84 Func->setCallingConv(CallingConv::C);
88 /// A base class, implementing utilities needed for
89 /// modifying and adding new random instructions.
91 /// Used to store the randomly generated values.
92 typedef std::vector<Value*> PieceTable;
96 Modifier(BasicBlock *Block, PieceTable *PT, Random *R):
97 BB(Block),PT(PT),Ran(R),Context(BB->getContext()) {};
98 /// Add a new instruction.
99 virtual void Act() = 0;
100 /// Add N new instructions,
101 virtual void ActN(unsigned n) {
102 for (unsigned i=0; i<n; ++i)
107 /// Return a random value from the list of known values.
108 Value *getRandomVal() {
110 return PT->at(Ran->Rand() % PT->size());
113 Constant *getRandomConstant(Type *Tp) {
114 if (Tp->isIntegerTy()) {
116 return ConstantInt::getAllOnesValue(Tp);
117 return ConstantInt::getNullValue(Tp);
118 } else if (Tp->isFloatingPointTy()) {
120 return ConstantFP::getAllOnesValue(Tp);
121 return ConstantFP::getNullValue(Tp);
123 return UndefValue::get(Tp);
126 /// Return a random value with a known type.
127 Value *getRandomValue(Type *Tp) {
128 unsigned index = Ran->Rand();
129 for (unsigned i=0; i<PT->size(); ++i) {
130 Value *V = PT->at((index + i) % PT->size());
131 if (V->getType() == Tp)
135 // If the requested type was not found, generate a constant value.
136 if (Tp->isIntegerTy()) {
138 return ConstantInt::getAllOnesValue(Tp);
139 return ConstantInt::getNullValue(Tp);
140 } else if (Tp->isFloatingPointTy()) {
142 return ConstantFP::getAllOnesValue(Tp);
143 return ConstantFP::getNullValue(Tp);
144 } else if (Tp->isVectorTy()) {
145 VectorType *VTp = cast<VectorType>(Tp);
147 std::vector<Constant*> TempValues;
148 TempValues.reserve(VTp->getNumElements());
149 for (unsigned i = 0; i < VTp->getNumElements(); ++i)
150 TempValues.push_back(getRandomConstant(VTp->getScalarType()));
152 ArrayRef<Constant*> VectorValue(TempValues);
153 return ConstantVector::get(VectorValue);
156 return UndefValue::get(Tp);
159 /// Return a random value of any pointer type.
160 Value *getRandomPointerValue() {
161 unsigned index = Ran->Rand();
162 for (unsigned i=0; i<PT->size(); ++i) {
163 Value *V = PT->at((index + i) % PT->size());
164 if (V->getType()->isPointerTy())
167 return UndefValue::get(pickPointerType());
170 /// Return a random value of any vector type.
171 Value *getRandomVectorValue() {
172 unsigned index = Ran->Rand();
173 for (unsigned i=0; i<PT->size(); ++i) {
174 Value *V = PT->at((index + i) % PT->size());
175 if (V->getType()->isVectorTy())
178 return UndefValue::get(pickVectorType());
181 /// Pick a random type.
183 return (Ran->Rand() & 1 ? pickVectorType() : pickScalarType());
186 /// Pick a random pointer type.
187 Type *pickPointerType() {
188 Type *Ty = pickType();
189 return PointerType::get(Ty, 0);
192 /// Pick a random vector type.
193 Type *pickVectorType(unsigned len = (unsigned)-1) {
194 Type *Ty = pickScalarType();
195 // Pick a random vector width in the range 2**0 to 2**4.
196 // by adding two randoms we are generating a normal-like distribution
198 unsigned width = 1<<((Ran->Rand() % 3) + (Ran->Rand() % 3));
199 if (len != (unsigned)-1)
201 return VectorType::get(Ty, width);
204 /// Pick a random scalar type.
205 Type *pickScalarType() {
206 switch (Ran->Rand() % 15) {
207 case 0: return Type::getInt1Ty(Context);
208 case 1: return Type::getInt8Ty(Context);
209 case 2: return Type::getInt16Ty(Context);
211 case 5: return Type::getFloatTy(Context);
213 case 8: return Type::getDoubleTy(Context);
215 case 11: return Type::getInt32Ty(Context);
217 case 14: return Type::getInt64Ty(Context);
219 llvm_unreachable("Invalid scalar value");
222 /// Basic block to populate
226 /// Random number generator
229 LLVMContext &Context;
232 struct LoadModifier: public Modifier {
233 LoadModifier(BasicBlock *BB, PieceTable *PT, Random *R):Modifier(BB, PT, R) {};
235 // Try to use predefined pointers. If non exist, use undef pointer value;
236 Value *Ptr = getRandomPointerValue();
237 Value *V = new LoadInst(Ptr, "L", BB->getTerminator());
242 struct StoreModifier: public Modifier {
243 StoreModifier(BasicBlock *BB, PieceTable *PT, Random *R):Modifier(BB, PT, R) {}
245 // Try to use predefined pointers. If non exist, use undef pointer value;
246 Value *Ptr = getRandomPointerValue();
247 Type *Tp = Ptr->getType();
248 Value *Val = getRandomValue(Tp->getContainedType(0));
249 Type *ValTy = Val->getType();
251 // Do not store vectors of i1s because they are unsupported
253 if (ValTy->isVectorTy() && ValTy->getScalarSizeInBits() == 1)
256 new StoreInst(Val, Ptr, BB->getTerminator());
260 struct BinModifier: public Modifier {
261 BinModifier(BasicBlock *BB, PieceTable *PT, Random *R):Modifier(BB, PT, R) {}
264 Value *Val0 = getRandomVal();
265 Value *Val1 = getRandomValue(Val0->getType());
267 // Don't handle pointer types.
268 if (Val0->getType()->isPointerTy() ||
269 Val1->getType()->isPointerTy())
272 // Don't handle i1 types.
273 if (Val0->getType()->getScalarSizeInBits() == 1)
277 bool isFloat = Val0->getType()->getScalarType()->isFloatingPointTy();
278 Instruction* Term = BB->getTerminator();
279 unsigned R = Ran->Rand() % (isFloat ? 7 : 13);
280 Instruction::BinaryOps Op;
283 default: llvm_unreachable("Invalid BinOp");
284 case 0:{Op = (isFloat?Instruction::FAdd : Instruction::Add); break; }
285 case 1:{Op = (isFloat?Instruction::FSub : Instruction::Sub); break; }
286 case 2:{Op = (isFloat?Instruction::FMul : Instruction::Mul); break; }
287 case 3:{Op = (isFloat?Instruction::FDiv : Instruction::SDiv); break; }
288 case 4:{Op = (isFloat?Instruction::FDiv : Instruction::UDiv); break; }
289 case 5:{Op = (isFloat?Instruction::FRem : Instruction::SRem); break; }
290 case 6:{Op = (isFloat?Instruction::FRem : Instruction::URem); break; }
291 case 7: {Op = Instruction::Shl; break; }
292 case 8: {Op = Instruction::LShr; break; }
293 case 9: {Op = Instruction::AShr; break; }
294 case 10:{Op = Instruction::And; break; }
295 case 11:{Op = Instruction::Or; break; }
296 case 12:{Op = Instruction::Xor; break; }
299 PT->push_back(BinaryOperator::Create(Op, Val0, Val1, "B", Term));
303 /// Generate constant values.
304 struct ConstModifier: public Modifier {
305 ConstModifier(BasicBlock *BB, PieceTable *PT, Random *R):Modifier(BB, PT, R) {}
307 Type *Ty = pickType();
309 if (Ty->isVectorTy()) {
310 switch (Ran->Rand() % 2) {
311 case 0: if (Ty->getScalarType()->isIntegerTy())
312 return PT->push_back(ConstantVector::getAllOnesValue(Ty));
313 case 1: if (Ty->getScalarType()->isIntegerTy())
314 return PT->push_back(ConstantVector::getNullValue(Ty));
318 if (Ty->isFloatingPointTy()) {
320 return PT->push_back(ConstantFP::getNullValue(Ty));
321 return PT->push_back(ConstantFP::get(Ty,
322 static_cast<double>(1)/Ran->Rand()));
325 if (Ty->isIntegerTy()) {
326 switch (Ran->Rand() % 7) {
327 case 0: if (Ty->isIntegerTy())
328 return PT->push_back(ConstantInt::get(Ty,
329 APInt::getAllOnesValue(Ty->getPrimitiveSizeInBits())));
330 case 1: if (Ty->isIntegerTy())
331 return PT->push_back(ConstantInt::get(Ty,
332 APInt::getNullValue(Ty->getPrimitiveSizeInBits())));
333 case 2: case 3: case 4: case 5:
334 case 6: if (Ty->isIntegerTy())
335 PT->push_back(ConstantInt::get(Ty, Ran->Rand()));
342 struct AllocaModifier: public Modifier {
343 AllocaModifier(BasicBlock *BB, PieceTable *PT, Random *R):Modifier(BB, PT, R){}
346 Type *Tp = pickType();
347 PT->push_back(new AllocaInst(Tp, "A", BB->getFirstNonPHI()));
351 struct ExtractElementModifier: public Modifier {
352 ExtractElementModifier(BasicBlock *BB, PieceTable *PT, Random *R):
353 Modifier(BB, PT, R) {}
356 Value *Val0 = getRandomVectorValue();
357 Value *V = ExtractElementInst::Create(Val0,
358 ConstantInt::get(Type::getInt32Ty(BB->getContext()),
359 Ran->Rand() % cast<VectorType>(Val0->getType())->getNumElements()),
360 "E", BB->getTerminator());
361 return PT->push_back(V);
365 struct ShuffModifier: public Modifier {
366 ShuffModifier(BasicBlock *BB, PieceTable *PT, Random *R):Modifier(BB, PT, R) {}
369 Value *Val0 = getRandomVectorValue();
370 Value *Val1 = getRandomValue(Val0->getType());
372 unsigned Width = cast<VectorType>(Val0->getType())->getNumElements();
373 std::vector<Constant*> Idxs;
375 Type *I32 = Type::getInt32Ty(BB->getContext());
376 for (unsigned i=0; i<Width; ++i) {
377 Constant *CI = ConstantInt::get(I32, Ran->Rand() % (Width*2));
378 // Pick some undef values.
379 if (!(Ran->Rand() % 5))
380 CI = UndefValue::get(I32);
384 Constant *Mask = ConstantVector::get(Idxs);
386 Value *V = new ShuffleVectorInst(Val0, Val1, Mask, "Shuff",
387 BB->getTerminator());
392 struct InsertElementModifier: public Modifier {
393 InsertElementModifier(BasicBlock *BB, PieceTable *PT, Random *R):
394 Modifier(BB, PT, R) {}
397 Value *Val0 = getRandomVectorValue();
398 Value *Val1 = getRandomValue(Val0->getType()->getScalarType());
400 Value *V = InsertElementInst::Create(Val0, Val1,
401 ConstantInt::get(Type::getInt32Ty(BB->getContext()),
402 Ran->Rand() % cast<VectorType>(Val0->getType())->getNumElements()),
403 "I", BB->getTerminator());
404 return PT->push_back(V);
409 struct CastModifier: public Modifier {
410 CastModifier(BasicBlock *BB, PieceTable *PT, Random *R):Modifier(BB, PT, R) {}
413 Value *V = getRandomVal();
414 Type *VTy = V->getType();
415 Type *DestTy = pickScalarType();
417 // Handle vector casts vectors.
418 if (VTy->isVectorTy()) {
419 VectorType *VecTy = cast<VectorType>(VTy);
420 DestTy = pickVectorType(VecTy->getNumElements());
424 if (VTy == DestTy) return;
427 if (VTy->isPointerTy()) {
428 if (!DestTy->isPointerTy())
429 DestTy = PointerType::get(DestTy, 0);
430 return PT->push_back(
431 new BitCastInst(V, DestTy, "PC", BB->getTerminator()));
434 // Generate lots of bitcasts.
435 if ((Ran->Rand() & 1) &&
436 VTy->getPrimitiveSizeInBits() == DestTy->getPrimitiveSizeInBits()) {
437 return PT->push_back(
438 new BitCastInst(V, DestTy, "BC", BB->getTerminator()));
441 // Both types are integers:
442 if (VTy->getScalarType()->isIntegerTy() &&
443 DestTy->getScalarType()->isIntegerTy()) {
444 if (VTy->getScalarType()->getPrimitiveSizeInBits() >
445 DestTy->getScalarType()->getPrimitiveSizeInBits()) {
446 return PT->push_back(
447 new TruncInst(V, DestTy, "Tr", BB->getTerminator()));
450 return PT->push_back(
451 new ZExtInst(V, DestTy, "ZE", BB->getTerminator()));
452 return PT->push_back(new SExtInst(V, DestTy, "Se", BB->getTerminator()));
457 if (VTy->getScalarType()->isFloatingPointTy() &&
458 DestTy->getScalarType()->isIntegerTy()) {
460 return PT->push_back(
461 new FPToSIInst(V, DestTy, "FC", BB->getTerminator()));
462 return PT->push_back(new FPToUIInst(V, DestTy, "FC", BB->getTerminator()));
466 if (VTy->getScalarType()->isIntegerTy() &&
467 DestTy->getScalarType()->isFloatingPointTy()) {
469 return PT->push_back(
470 new SIToFPInst(V, DestTy, "FC", BB->getTerminator()));
471 return PT->push_back(new UIToFPInst(V, DestTy, "FC", BB->getTerminator()));
476 if (VTy->getScalarType()->isFloatingPointTy() &&
477 DestTy->getScalarType()->isFloatingPointTy()) {
478 if (VTy->getScalarType()->getPrimitiveSizeInBits() >
479 DestTy->getScalarType()->getPrimitiveSizeInBits()) {
480 return PT->push_back(
481 new FPTruncInst(V, DestTy, "Tr", BB->getTerminator()));
483 return PT->push_back(
484 new FPExtInst(V, DestTy, "ZE", BB->getTerminator()));
491 struct SelectModifier: public Modifier {
492 SelectModifier(BasicBlock *BB, PieceTable *PT, Random *R):
493 Modifier(BB, PT, R) {}
496 // Try a bunch of different select configuration until a valid one is found.
497 Value *Val0 = getRandomVal();
498 Value *Val1 = getRandomValue(Val0->getType());
500 Type *CondTy = Type::getInt1Ty(Context);
502 // If the value type is a vector, and we allow vector select, then in 50%
503 // of the cases generate a vector select.
504 if (Val0->getType()->isVectorTy() && (Ran->Rand() % 1)) {
505 unsigned NumElem = cast<VectorType>(Val0->getType())->getNumElements();
506 CondTy = VectorType::get(CondTy, NumElem);
509 Value *Cond = getRandomValue(CondTy);
510 Value *V = SelectInst::Create(Cond, Val0, Val1, "Sl", BB->getTerminator());
511 return PT->push_back(V);
516 struct CmpModifier: public Modifier {
517 CmpModifier(BasicBlock *BB, PieceTable *PT, Random *R):Modifier(BB, PT, R) {}
520 Value *Val0 = getRandomVal();
521 Value *Val1 = getRandomValue(Val0->getType());
523 if (Val0->getType()->isPointerTy()) return;
524 bool fp = Val0->getType()->getScalarType()->isFloatingPointTy();
529 (CmpInst::LAST_FCMP_PREDICATE - CmpInst::FIRST_FCMP_PREDICATE) +
530 CmpInst::FIRST_FCMP_PREDICATE;
533 (CmpInst::LAST_ICMP_PREDICATE - CmpInst::FIRST_ICMP_PREDICATE) +
534 CmpInst::FIRST_ICMP_PREDICATE;
537 Value *V = CmpInst::Create(fp ? Instruction::FCmp : Instruction::ICmp,
538 op, Val0, Val1, "Cmp", BB->getTerminator());
539 return PT->push_back(V);
543 void FillFunction(Function *F) {
544 // Create a legal entry block.
545 BasicBlock *BB = BasicBlock::Create(F->getContext(), "BB", F);
546 ReturnInst::Create(F->getContext(), BB);
548 // Create the value table.
549 Modifier::PieceTable PT;
550 // Pick an initial seed value
553 // Consider arguments as legal values.
554 for (Function::arg_iterator it = F->arg_begin(), e = F->arg_end();
558 // List of modifiers which add new random instructions.
559 std::vector<Modifier*> Modifiers;
560 std::auto_ptr<Modifier> LM(new LoadModifier(BB, &PT, &R));
561 std::auto_ptr<Modifier> SM(new StoreModifier(BB, &PT, &R));
562 std::auto_ptr<Modifier> EE(new ExtractElementModifier(BB, &PT, &R));
563 std::auto_ptr<Modifier> SHM(new ShuffModifier(BB, &PT, &R));
564 std::auto_ptr<Modifier> IE(new InsertElementModifier(BB, &PT, &R));
565 std::auto_ptr<Modifier> BM(new BinModifier(BB, &PT, &R));
566 std::auto_ptr<Modifier> CM(new CastModifier(BB, &PT, &R));
567 std::auto_ptr<Modifier> SLM(new SelectModifier(BB, &PT, &R));
568 std::auto_ptr<Modifier> PM(new CmpModifier(BB, &PT, &R));
569 Modifiers.push_back(LM.get());
570 Modifiers.push_back(SM.get());
571 Modifiers.push_back(EE.get());
572 Modifiers.push_back(SHM.get());
573 Modifiers.push_back(IE.get());
574 Modifiers.push_back(BM.get());
575 Modifiers.push_back(CM.get());
576 Modifiers.push_back(SLM.get());
577 Modifiers.push_back(PM.get());
579 // Generate the random instructions
580 AllocaModifier AM(BB, &PT, &R); AM.ActN(5); // Throw in a few allocas
581 ConstModifier COM(BB, &PT, &R); COM.ActN(40); // Throw in a few constants
583 for (unsigned i=0; i< SizeCL / Modifiers.size(); ++i)
584 for (std::vector<Modifier*>::iterator it = Modifiers.begin(),
585 e = Modifiers.end(); it != e; ++it) {
589 SM->ActN(5); // Throw in a few stores.
592 void IntroduceControlFlow(Function *F) {
593 std::set<Instruction*> BoolInst;
594 for (BasicBlock::iterator it = F->begin()->begin(),
595 e = F->begin()->end(); it != e; ++it) {
596 if (it->getType() == IntegerType::getInt1Ty(F->getContext()))
600 for (std::set<Instruction*>::iterator it = BoolInst.begin(),
601 e = BoolInst.end(); it != e; ++it) {
602 Instruction *Instr = *it;
603 BasicBlock *Curr = Instr->getParent();
604 BasicBlock::iterator Loc= Instr;
605 BasicBlock *Next = Curr->splitBasicBlock(Loc, "CF");
606 Instr->moveBefore(Curr->getTerminator());
607 if (Curr != &F->getEntryBlock()) {
608 BranchInst::Create(Curr, Next, Instr, Curr->getTerminator());
609 Curr->getTerminator()->eraseFromParent();
614 int main(int argc, char **argv) {
615 // Init LLVM, call llvm_shutdown() on exit, parse args, etc.
616 llvm::PrettyStackTraceProgram X(argc, argv);
617 cl::ParseCommandLineOptions(argc, argv, "llvm codegen stress-tester\n");
620 std::auto_ptr<Module> M(new Module("/tmp/autogen.bc", getGlobalContext()));
621 Function *F = GenEmptyFunction(M.get());
623 IntroduceControlFlow(F);
625 // Figure out what stream we are supposed to write to...
626 OwningPtr<tool_output_file> Out;
627 // Default to standard output.
628 if (OutputFilename.empty())
629 OutputFilename = "-";
631 std::string ErrorInfo;
632 Out.reset(new tool_output_file(OutputFilename.c_str(), ErrorInfo,
633 raw_fd_ostream::F_Binary));
634 if (!ErrorInfo.empty()) {
635 errs() << ErrorInfo << '\n';
640 Passes.add(createVerifierPass());
641 Passes.add(createPrintModulePass(&Out->os()));
642 Passes.run(*M.get());