klee
KModule.cpp
Go to the documentation of this file.
1//===-- KModule.cpp -------------------------------------------------------===//
2//
3// The KLEE Symbolic Virtual Machine
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9
10#define DEBUG_TYPE "KModule"
11
12#include "Passes.h"
13
14#include "klee/Config/Version.h"
17#include "klee/Module/Cell.h"
20#include "klee/Module/KModule.h"
21#include "klee/Support/Debug.h"
24
25#include "llvm/Bitcode/BitcodeWriter.h"
26#if LLVM_VERSION_CODE < LLVM_VERSION(8, 0)
27#include "llvm/IR/CallSite.h"
28#endif
29#include "llvm/IR/DataLayout.h"
30#include "llvm/IR/IRBuilder.h"
31#include "llvm/IR/Instructions.h"
32#include "llvm/IR/LegacyPassManager.h"
33#include "llvm/IR/LLVMContext.h"
34#include "llvm/IR/Module.h"
35#include "llvm/IR/ValueSymbolTable.h"
36#include "llvm/IR/Verifier.h"
37#include "llvm/Linker/Linker.h"
38#include "llvm/Support/CommandLine.h"
39#include "llvm/Support/Path.h"
40#include "llvm/Support/raw_ostream.h"
41#include "llvm/Support/raw_os_ostream.h"
42#include "llvm/Transforms/Scalar.h"
43#if LLVM_VERSION_CODE >= LLVM_VERSION(8, 0)
44#include "llvm/Transforms/Scalar/Scalarizer.h"
45#endif
46#include "llvm/Transforms/Utils/Cloning.h"
47#if LLVM_VERSION_CODE >= LLVM_VERSION(7, 0)
48#include "llvm/Transforms/Utils.h"
49#endif
50
51#include <sstream>
52
53using namespace llvm;
54using namespace klee;
55
56namespace klee {
57cl::OptionCategory
58 ModuleCat("Module-related options",
59 "These options affect the compile-time processing of the code.");
60}
61
62namespace {
63 enum SwitchImplType {
64 eSwitchTypeSimple,
65 eSwitchTypeLLVM,
66 eSwitchTypeInternal
67 };
68
69 cl::opt<bool>
70 OutputSource("output-source",
71 cl::desc("Write the assembly for the final transformed source (default=true)"),
72 cl::init(true),
73 cl::cat(ModuleCat));
74
75 cl::opt<bool>
76 OutputModule("output-module",
77 cl::desc("Write the bitcode for the final transformed module"),
78 cl::init(false),
79 cl::cat(ModuleCat));
80
81 cl::opt<SwitchImplType>
82 SwitchType("switch-type", cl::desc("Select the implementation of switch (default=internal)"),
83 cl::values(clEnumValN(eSwitchTypeSimple, "simple",
84 "lower to ordered branches"),
85 clEnumValN(eSwitchTypeLLVM, "llvm",
86 "lower using LLVM"),
87 clEnumValN(eSwitchTypeInternal, "internal",
88 "execute switch internally")),
89 cl::init(eSwitchTypeInternal),
90 cl::cat(ModuleCat));
91
92 cl::opt<bool>
93 DebugPrintEscapingFunctions("debug-print-escaping-functions",
94 cl::desc("Print functions whose address is taken (default=false)"),
95 cl::cat(ModuleCat));
96
97 // Don't run VerifierPass when checking module
98 cl::opt<bool>
99 DontVerify("disable-verify",
100 cl::desc("Do not verify the module integrity (default=false)"),
101 cl::init(false), cl::cat(klee::ModuleCat));
102
103 cl::opt<bool>
104 OptimiseKLEECall("klee-call-optimisation",
105 cl::desc("Allow optimization of functions that "
106 "contain KLEE calls (default=true)"),
107 cl::init(true), cl::cat(ModuleCat));
108}
109
110/***/
111
112namespace llvm {
113extern void Optimize(Module *, llvm::ArrayRef<const char *> preservedFunctions);
114}
115
116// what a hack
117static Function *getStubFunctionForCtorList(Module *m,
118 GlobalVariable *gv,
119 std::string name) {
120 assert(!gv->isDeclaration() && !gv->hasInternalLinkage() &&
121 "do not support old LLVM style constructor/destructor lists");
122
123 std::vector<Type *> nullary;
124
125 Function *fn = Function::Create(FunctionType::get(Type::getVoidTy(m->getContext()),
126 nullary, false),
127 GlobalVariable::InternalLinkage,
128 name,
129 m);
130 BasicBlock *bb = BasicBlock::Create(m->getContext(), "entry", fn);
131 llvm::IRBuilder<> Builder(bb);
132
133 // From lli:
134 // Should be an array of '{ int, void ()* }' structs. The first value is
135 // the init priority, which we ignore.
136 auto arr = dyn_cast<ConstantArray>(gv->getInitializer());
137 if (arr) {
138 for (unsigned i=0; i<arr->getNumOperands(); i++) {
139 auto cs = cast<ConstantStruct>(arr->getOperand(i));
140 // There is a third element in global_ctor elements (``i8 @data``).
141#if LLVM_VERSION_CODE >= LLVM_VERSION(9, 0)
142 assert(cs->getNumOperands() == 3 &&
143 "unexpected element in ctor initializer list");
144#else
145 // before LLVM 9.0, the third operand was optional
146 assert((cs->getNumOperands() == 2 || cs->getNumOperands() == 3) &&
147 "unexpected element in ctor initializer list");
148#endif
149 auto fp = cs->getOperand(1);
150 if (!fp->isNullValue()) {
151 if (auto ce = dyn_cast<llvm::ConstantExpr>(fp))
152 fp = ce->getOperand(0);
153
154 if (auto f = dyn_cast<Function>(fp)) {
155 Builder.CreateCall(f);
156 } else {
157 assert(0 && "unable to get function pointer from ctor initializer list");
158 }
159 }
160 }
161 }
162
163 Builder.CreateRetVoid();
164
165 return fn;
166}
167
168static void
170 llvm::StringRef entryFunction) {
171 GlobalVariable *ctors = m->getNamedGlobal("llvm.global_ctors");
172 GlobalVariable *dtors = m->getNamedGlobal("llvm.global_dtors");
173
174 if (!ctors && !dtors)
175 return;
176
177 Function *mainFn = m->getFunction(entryFunction);
178 if (!mainFn)
179 klee_error("Entry function '%s' not found in module.",
180 entryFunction.str().c_str());
181
182 if (ctors) {
183 llvm::IRBuilder<> Builder(&*mainFn->begin()->begin());
184 Builder.CreateCall(getStubFunctionForCtorList(m, ctors, "klee.ctor_stub"));
185 }
186
187 if (dtors) {
188 Function *dtorStub = getStubFunctionForCtorList(m, dtors, "klee.dtor_stub");
189 for (Function::iterator it = mainFn->begin(), ie = mainFn->end(); it != ie;
190 ++it) {
191 if (isa<ReturnInst>(it->getTerminator())) {
192 llvm::IRBuilder<> Builder(it->getTerminator());
193 Builder.CreateCall(dtorStub);
194 }
195 }
196 }
197}
198
199void KModule::addInternalFunction(const char* functionName){
200 Function* internalFunction = module->getFunction(functionName);
201 if (!internalFunction) {
202 KLEE_DEBUG(klee_warning(
203 "Failed to add internal function %s. Not found.", functionName));
204 return ;
205 }
206 KLEE_DEBUG(klee_message("Added function %s.",functionName));
207 internalFunctions.insert(internalFunction);
208}
209
210bool KModule::link(std::vector<std::unique_ptr<llvm::Module>> &modules,
211 const std::string &entryPoint) {
212 auto numRemainingModules = modules.size();
213 // Add the currently active module to the list of linkables
214 modules.push_back(std::move(module));
215 std::string error;
216 module = std::unique_ptr<llvm::Module>(
217 klee::linkModules(modules, entryPoint, error));
218 if (!module)
219 klee_error("Could not link KLEE files %s", error.c_str());
220
221 targetData = std::unique_ptr<llvm::DataLayout>(new DataLayout(module.get()));
222
223 // Check if we linked anything
224 return modules.size() != numRemainingModules;
225}
226
228 // Inject checks prior to optimization... we also perform the
229 // invariant transformations that we will end up doing later so that
230 // optimize is seeing what is as close as possible to the final
231 // module.
232 legacy::PassManager pm;
233 pm.add(new RaiseAsmPass());
234
235 // This pass will scalarize as much code as possible so that the Executor
236 // does not need to handle operands of vector type for most instructions
237 // other than InsertElementInst and ExtractElementInst.
238 //
239 // NOTE: Must come before division/overshift checks because those passes
240 // don't know how to handle vector instructions.
241 pm.add(createScalarizerPass());
242
243 // This pass will replace atomic instructions with non-atomic operations
244 pm.add(createLowerAtomicPass());
245 if (opts.CheckDivZero) pm.add(new DivCheckPass());
246 if (opts.CheckOvershift) pm.add(new OvershiftCheckPass());
247
248 pm.add(new IntrinsicCleanerPass(*targetData));
249 pm.run(*module);
250}
251
253 const Interpreter::ModuleOptions &opts,
254 llvm::ArrayRef<const char *> preservedFunctions) {
255 // Preserve all functions containing klee-related function calls from being
256 // optimised around
257 if (!OptimiseKLEECall) {
258 legacy::PassManager pm;
259 pm.add(new OptNonePass());
260 pm.run(*module);
261 }
262
263 if (opts.Optimize)
264 Optimize(module.get(), preservedFunctions);
265
266 // Add internal functions which are not used to check if instructions
267 // have been already visited
268 if (opts.CheckDivZero)
269 addInternalFunction("klee_div_zero_check");
270 if (opts.CheckOvershift)
271 addInternalFunction("klee_overshift_check");
272
273 // Needs to happen after linking (since ctors/dtors can be modified)
274 // and optimization (since global optimization can rewrite lists).
276
277 // Finally, run the passes that maintain invariants we expect during
278 // interpretation. We run the intrinsic cleaner just in case we
279 // linked in something with intrinsics but any external calls are
280 // going to be unresolved. We really need to handle the intrinsics
281 // directly I think?
282 legacy::PassManager pm3;
283 pm3.add(createCFGSimplificationPass());
284 switch(SwitchType) {
285 case eSwitchTypeInternal: break;
286 case eSwitchTypeSimple: pm3.add(new LowerSwitchPass()); break;
287 case eSwitchTypeLLVM: pm3.add(createLowerSwitchPass()); break;
288 default: klee_error("invalid --switch-type");
289 }
290 pm3.add(new IntrinsicCleanerPass(*targetData));
291 pm3.add(createScalarizerPass());
292 pm3.add(new PhiCleanerPass());
293 pm3.add(new FunctionAliasPass());
294 pm3.run(*module);
295}
296
297void KModule::manifest(InterpreterHandler *ih, bool forceSourceOutput) {
298 if (OutputSource || forceSourceOutput) {
299 std::unique_ptr<llvm::raw_fd_ostream> os(ih->openOutputFile("assembly.ll"));
300 assert(os && !os->has_error() && "unable to open source output");
301 *os << *module;
302 }
303
304 if (OutputModule) {
305 std::unique_ptr<llvm::raw_fd_ostream> f(ih->openOutputFile("final.bc"));
306#if LLVM_VERSION_CODE >= LLVM_VERSION(7, 0)
307 WriteBitcodeToFile(*module, *f);
308#else
309 WriteBitcodeToFile(module.get(), *f);
310#endif
311 }
312
313 /* Build shadow structures */
314
315 infos = std::unique_ptr<InstructionInfoTable>(
316 new InstructionInfoTable(*module.get()));
317
318 std::vector<Function *> declarations;
319
320 for (auto &Function : *module) {
321 if (Function.isDeclaration()) {
322 declarations.push_back(&Function);
323 continue;
324 }
325
326 auto kf = std::unique_ptr<KFunction>(new KFunction(&Function, this));
327
328 for (unsigned i=0; i<kf->numInstructions; ++i) {
329 KInstruction *ki = kf->instructions[i];
330 ki->info = &infos->getInfo(*ki->inst);
331 }
332
333 functionMap.insert(std::make_pair(&Function, kf.get()));
334 functions.push_back(std::move(kf));
335 }
336
337 /* Compute various interesting properties */
338
339 for (auto &kf : functions) {
340 if (functionEscapes(kf->function))
341 escapingFunctions.insert(kf->function);
342 }
343
344 for (auto &declaration : declarations) {
345 if (functionEscapes(declaration))
346 escapingFunctions.insert(declaration);
347 }
348
349 if (DebugPrintEscapingFunctions && !escapingFunctions.empty()) {
350 llvm::errs() << "KLEE: escaping functions: [";
351 std::string delimiter = "";
352 for (auto &Function : escapingFunctions) {
353 llvm::errs() << delimiter << Function->getName();
354 delimiter = ", ";
355 }
356 llvm::errs() << "]\n";
357 }
358}
359
361 InstructionOperandTypeCheckPass *operandTypeCheckPass =
363
364 legacy::PassManager pm;
365 if (!DontVerify)
366 pm.add(createVerifierPass());
367 pm.add(operandTypeCheckPass);
368 pm.run(*module);
369
370 // Enforce the operand type invariants that the Executor expects. This
371 // implicitly depends on the "Scalarizer" pass to be run in order to succeed
372 // in the presence of vector instructions.
373 if (!operandTypeCheckPass->checkPassed()) {
374 klee_error("Unexpected instruction operand types detected");
375 }
376}
377
378KConstant* KModule::getKConstant(const Constant *c) {
379 auto it = constantMap.find(c);
380 if (it != constantMap.end())
381 return it->second.get();
382 return NULL;
383}
384
385unsigned KModule::getConstantID(Constant *c, KInstruction* ki) {
386 if (KConstant *kc = getKConstant(c))
387 return kc->id;
388
389 unsigned id = constants.size();
390 auto kc = std::unique_ptr<KConstant>(new KConstant(c, id, ki));
391 constantMap.insert(std::make_pair(c, std::move(kc)));
392 constants.push_back(c);
393 return id;
394}
395
396/***/
397
398KConstant::KConstant(llvm::Constant* _ct, unsigned _id, KInstruction* _ki) {
399 ct = _ct;
400 id = _id;
401 ki = _ki;
402}
403
404/***/
405
406static int getOperandNum(Value *v,
407 std::map<Instruction*, unsigned> &registerMap,
408 KModule *km,
409 KInstruction *ki) {
410 if (Instruction *inst = dyn_cast<Instruction>(v)) {
411 return registerMap[inst];
412 } else if (Argument *a = dyn_cast<Argument>(v)) {
413 return a->getArgNo();
414 } else if (isa<BasicBlock>(v) || isa<InlineAsm>(v) ||
415 isa<MetadataAsValue>(v)) {
416 return -1;
417 } else {
418 assert(isa<Constant>(v));
419 Constant *c = cast<Constant>(v);
420 return -(km->getConstantID(c, ki) + 2);
421 }
422}
423
424KFunction::KFunction(llvm::Function *_function,
425 KModule *km)
426 : function(_function),
427 numArgs(function->arg_size()),
428 numInstructions(0),
429 trackCoverage(true) {
430 // Assign unique instruction IDs to each basic block
431 for (auto &BasicBlock : *function) {
432 basicBlockEntry[&BasicBlock] = numInstructions;
433 numInstructions += BasicBlock.size();
434 }
435
437
438 std::map<Instruction*, unsigned> registerMap;
439
440 // The first arg_size() registers are reserved for formals.
441 unsigned rnum = numArgs;
442 for (llvm::Function::iterator bbit = function->begin(),
443 bbie = function->end(); bbit != bbie; ++bbit) {
444 for (llvm::BasicBlock::iterator it = bbit->begin(), ie = bbit->end();
445 it != ie; ++it)
446 registerMap[&*it] = rnum++;
447 }
448 numRegisters = rnum;
449
450 unsigned i = 0;
451 for (llvm::Function::iterator bbit = function->begin(),
452 bbie = function->end(); bbit != bbie; ++bbit) {
453 for (llvm::BasicBlock::iterator it = bbit->begin(), ie = bbit->end();
454 it != ie; ++it) {
455 KInstruction *ki;
456
457 switch(it->getOpcode()) {
458 case Instruction::GetElementPtr:
459 case Instruction::InsertValue:
460 case Instruction::ExtractValue:
461 ki = new KGEPInstruction(); break;
462 default:
463 ki = new KInstruction(); break;
464 }
465
466 Instruction *inst = &*it;
467 ki->inst = inst;
468 ki->dest = registerMap[inst];
469
470 if (isa<CallInst>(it) || isa<InvokeInst>(it)) {
471#if LLVM_VERSION_CODE >= LLVM_VERSION(8, 0)
472 const CallBase &cs = cast<CallBase>(*inst);
473 Value *val = cs.getCalledOperand();
474#else
475 const CallSite cs(inst);
476 Value *val = cs.getCalledValue();
477#endif
478 unsigned numArgs = cs.arg_size();
479 ki->operands = new int[numArgs+1];
480 ki->operands[0] = getOperandNum(val, registerMap, km, ki);
481 for (unsigned j=0; j<numArgs; j++) {
482 Value *v = cs.getArgOperand(j);
483 ki->operands[j+1] = getOperandNum(v, registerMap, km, ki);
484 }
485 } else {
486 unsigned numOperands = it->getNumOperands();
487 ki->operands = new int[numOperands];
488 for (unsigned j=0; j<numOperands; j++) {
489 Value *v = it->getOperand(j);
490 ki->operands[j] = getOperandNum(v, registerMap, km, ki);
491 }
492 }
493
494 instructions[i++] = ki;
495 }
496 }
497}
498
500 for (unsigned i=0; i<numInstructions; ++i)
501 delete instructions[i];
502 delete[] instructions;
503}
static int getOperandNum(Value *v, std::map< Instruction *, unsigned > &registerMap, KModule *km, KInstruction *ki)
Definition: KModule.cpp:406
static Function * getStubFunctionForCtorList(Module *m, GlobalVariable *gv, std::string name)
Definition: KModule.cpp:117
static void injectStaticConstructorsAndDestructors(Module *m, llvm::StringRef entryFunction)
Definition: KModule.cpp:169
virtual std::unique_ptr< llvm::raw_fd_ostream > openOutputFile(const std::string &filename)=0
KInstruction * ki
Definition: KModule.h:77
KConstant(llvm::Constant *, unsigned, KInstruction *)
Definition: KModule.cpp:398
llvm::Constant * ct
Actual LLVM constant this represents.
Definition: KModule.h:70
void checkModule()
Definition: KModule.cpp:360
unsigned getConstantID(llvm::Constant *c, KInstruction *ki)
Return an id for the given constant, creating a new one if necessary.
Definition: KModule.cpp:385
void optimiseAndPrepare(const Interpreter::ModuleOptions &opts, llvm::ArrayRef< const char * >)
Optimise and prepare module such that KLEE can execute it.
Definition: KModule.cpp:252
void addInternalFunction(const char *functionName)
Definition: KModule.cpp:199
KConstant * getKConstant(const llvm::Constant *c)
Definition: KModule.cpp:378
std::map< const llvm::Constant *, std::unique_ptr< KConstant > > constantMap
Definition: KModule.h:99
void instrument(const Interpreter::ModuleOptions &opts)
Definition: KModule.cpp:227
void manifest(InterpreterHandler *ih, bool forceSourceOutput)
Definition: KModule.cpp:297
bool link(std::vector< std::unique_ptr< llvm::Module > > &modules, const std::string &entryPoint)
Definition: KModule.cpp:210
std::set< const llvm::Function * > internalFunctions
Definition: KModule.h:105
std::unique_ptr< llvm::DataLayout > targetData
Definition: KModule.h:86
std::unique_ptr< InstructionInfoTable > infos
Definition: KModule.h:96
std::set< llvm::Function * > escapingFunctions
Definition: KModule.h:94
std::vector< std::unique_ptr< KFunction > > functions
Definition: KModule.h:89
std::vector< llvm::Constant * > constants
Definition: KModule.h:98
std::unique_ptr< llvm::Module > module
Definition: KModule.h:85
std::map< llvm::Function *, KFunction * > functionMap
Definition: KModule.h:90
Instruments every function that contains a KLEE function call as nonopt.
Definition: Passes.h:201
Definition: main.cpp:291
void klee_message(const char *msg,...) __attribute__((format(printf
std::unique_ptr< llvm::Module > linkModules(std::vector< std::unique_ptr< llvm::Module > > &modules, llvm::StringRef entryFunction, std::string &errorMsg)
Definition: ModuleUtil.cpp:146
bool functionEscapes(const llvm::Function *f)
cl::OptionCategory ModuleCat("Module-related options", "These options affect the compile-time processing of the code.")
void klee_error(const char *msg,...) __attribute__((format(printf
llvm::cl::OptionCategory ModuleCat
void void void klee_warning(const char *msg,...) __attribute__((format(printf
void Optimize(Module *, llvm::ArrayRef< const char * > preservedFunctions)
Definition: Optimize.cpp:161
std::map< llvm::BasicBlock *, unsigned > basicBlockEntry
Definition: KModule.h:50
llvm::Function * function
Definition: KModule.h:43
unsigned numArgs
Definition: KModule.h:45
unsigned numRegisters
Definition: KModule.h:45
KInstruction ** instructions
Definition: KModule.h:48
unsigned numInstructions
Definition: KModule.h:47
KFunction(llvm::Function *, KModule *)
Definition: KModule.cpp:424
const InstructionInfo * info
Definition: KInstruction.h:35
unsigned dest
Destination register index.
Definition: KInstruction.h:43
llvm::Instruction * inst
Definition: KInstruction.h:34