diff options
| -rw-r--r-- | lib/Module/CMakeLists.txt | 14 | ||||
| -rw-r--r-- | lib/Module/Instrument.cpp | 19 | ||||
| -rw-r--r-- | lib/Module/InstrumentLegacy.cpp | 125 | ||||
| -rw-r--r-- | lib/Module/KModule.cpp | 139 | ||||
| -rw-r--r-- | lib/Module/ModuleHelper.h | 37 | ||||
| -rw-r--r-- | lib/Module/Optimize.cpp | 249 | ||||
| -rw-r--r-- | lib/Module/OptimizeLegacy.cpp | 249 |
7 files changed, 475 insertions, 357 deletions
diff --git a/lib/Module/CMakeLists.txt b/lib/Module/CMakeLists.txt index e1f548e8..71e1d40c 100644 --- a/lib/Module/CMakeLists.txt +++ b/lib/Module/CMakeLists.txt @@ -16,12 +16,24 @@ set(KLEE_MODULE_COMPONENT_SRCS KModule.cpp LowerSwitch.cpp ModuleUtil.cpp - Optimize.cpp OptNone.cpp PhiCleaner.cpp RaiseAsm.cpp ) +if ("${LLVM_VERSION_MAJOR}" LESS 17) + LIST(APPEND KLEE_MODULE_COMPONENT_SRCS + InstrumentLegacy.cpp + OptimizeLegacy.cpp + ) +else () + LIST(APPEND KLEE_MODULE_COMPONENT_SRCS + Instrument.cpp + Optimize.cpp + ) +endif () + + add_library(kleeModule ${KLEE_MODULE_COMPONENT_SRCS} ) diff --git a/lib/Module/Instrument.cpp b/lib/Module/Instrument.cpp new file mode 100644 index 00000000..bbb5df7c --- /dev/null +++ b/lib/Module/Instrument.cpp @@ -0,0 +1,19 @@ +//===-- Instrument.cpp ------------------------------------------*- C++ -*-===// +// +// The KLEE Symbolic Virtual Machine +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#include "ModuleHelper.h" + +using namespace klee; + +void klee::checkModule(bool DontVerfify, llvm::Module *module) { assert(0); } + +void klee::instrument(bool CheckDivZero, bool CheckOvershift, + llvm::Module *module) { + assert(0); +} \ No newline at end of file diff --git a/lib/Module/InstrumentLegacy.cpp b/lib/Module/InstrumentLegacy.cpp new file mode 100644 index 00000000..daae8043 --- /dev/null +++ b/lib/Module/InstrumentLegacy.cpp @@ -0,0 +1,125 @@ +//===-- InstrumentLegacy.cpp ------------------------------------*- C++ -*-===// +// +// The KLEE Symbolic Virtual Machine +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +#include "ModuleHelper.h" + +#include "Passes.h" +#include "klee/Support/CompilerWarning.h" +#include "klee/Support/ErrorHandling.h" + +DISABLE_WARNING_PUSH +DISABLE_WARNING_DEPRECATED_DECLARATIONS +#include "llvm/Bitcode/BitcodeWriter.h" +#include "llvm/IR/DataLayout.h" +#include "llvm/IR/IRBuilder.h" +#include "llvm/IR/LLVMContext.h" +#include "llvm/IR/LegacyPassManager.h" +#include "llvm/IR/Module.h" +#include "llvm/IR/ValueSymbolTable.h" +#include "llvm/IR/Verifier.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Transforms/Scalar.h" +#include "llvm/Transforms/Scalar/Scalarizer.h" +#include "llvm/Transforms/Utils.h" +#include "llvm/Transforms/Utils/Cloning.h" +DISABLE_WARNING_POP + +using namespace llvm; +using namespace klee; + +void klee::instrument(bool CheckDivZero, bool CheckOvershift, + llvm::Module *module) { + // Inject checks prior to optimization... we also perform the + // invariant transformations that we will end up doing later so that + // optimize is seeing what is as close as possible to the final + // module. + legacy::PassManager pm; + pm.add(new RaiseAsmPass()); + + // This pass will scalarize as much code as possible so that the Executor + // does not need to handle operands of vector type for most instructions + // other than InsertElementInst and ExtractElementInst. + // + // NOTE: Must come before division/overshift checks because those passes + // don't know how to handle vector instructions. + pm.add(createScalarizerPass()); + + // This pass will replace atomic instructions with non-atomic operations + pm.add(createLowerAtomicPass()); + if (CheckDivZero) + pm.add(new DivCheckPass()); + if (CheckOvershift) + pm.add(new OvershiftCheckPass()); + + llvm::DataLayout targetData(module); + pm.add(new IntrinsicCleanerPass(targetData)); + pm.run(*module); +} + +void klee::checkModule(bool DontVerify, llvm::Module *module) { + InstructionOperandTypeCheckPass *operandTypeCheckPass = + new InstructionOperandTypeCheckPass(); + + legacy::PassManager pm; + if (!DontVerify) + pm.add(createVerifierPass()); + pm.add(operandTypeCheckPass); + pm.run(*module); + + // Enforce the operand type invariants that the Executor expects. This + // implicitly depends on the "Scalarizer" pass to be run in order to succeed + // in the presence of vector instructions. + if (!operandTypeCheckPass->checkPassed()) { + klee_error("Unexpected instruction operand types detected"); + } +} + +void klee::optimiseAndPrepare(bool OptimiseKLEECall, bool Optimize, + SwitchImplType SwitchType, std::string EntryPoint, + llvm::ArrayRef<const char *> preservedFunctions, + llvm::Module *module) { + // Preserve all functions containing klee-related function calls from being + // optimised around + if (!OptimiseKLEECall) { + legacy::PassManager pm; + pm.add(new OptNonePass()); + pm.run(*module); + } + + if (Optimize) + optimizeModule(module, preservedFunctions); + + // Needs to happen after linking (since ctors/dtors can be modified) + // and optimization (since global optimization can rewrite lists). + injectStaticConstructorsAndDestructors(module, EntryPoint); + + // Finally, run the passes that maintain invariants we expect during + // interpretation. We run the intrinsic cleaner just in case we + // linked in something with intrinsics but any external calls are + // going to be unresolved. We really need to handle the intrinsics + // directly I think? + legacy::PassManager pm3; + pm3.add(createCFGSimplificationPass()); + switch (SwitchType) { + case SwitchImplType::eSwitchTypeInternal: + break; + case SwitchImplType::eSwitchTypeSimple: + pm3.add(new LowerSwitchPass()); + break; + case SwitchImplType::eSwitchTypeLLVM: + pm3.add(createLowerSwitchPass()); + break; + } + + llvm::DataLayout targetData(module); + pm3.add(new IntrinsicCleanerPass(targetData)); + pm3.add(createScalarizerPass()); + pm3.add(new PhiCleanerPass()); + pm3.add(new FunctionAliasPass()); + pm3.run(*module); +} \ No newline at end of file diff --git a/lib/Module/KModule.cpp b/lib/Module/KModule.cpp index eed922f8..cb8b4539 100644 --- a/lib/Module/KModule.cpp +++ b/lib/Module/KModule.cpp @@ -9,40 +9,27 @@ #define DEBUG_TYPE "KModule" +#include "klee/Module/KModule.h" + +#include "ModuleHelper.h" #include "Passes.h" #include "klee/Config/Version.h" #include "klee/Core/Interpreter.h" -#include "klee/Support/OptionCategories.h" #include "klee/Module/Cell.h" #include "klee/Module/InstructionInfoTable.h" #include "klee/Module/KInstruction.h" -#include "klee/Module/KModule.h" #include "klee/Support/Debug.h" #include "klee/Support/ErrorHandling.h" #include "klee/Support/ModuleUtil.h" +#include "klee/Support/OptionCategories.h" #include "klee/Support/CompilerWarning.h" + DISABLE_WARNING_PUSH DISABLE_WARNING_DEPRECATED_DECLARATIONS #include "llvm/Bitcode/BitcodeWriter.h" -#include "llvm/IR/DataLayout.h" #include "llvm/IR/IRBuilder.h" -#include "llvm/IR/Instructions.h" -#include "llvm/IR/LegacyPassManager.h" -#include "llvm/IR/LLVMContext.h" -#include "llvm/IR/Module.h" -#include "llvm/IR/ValueSymbolTable.h" -#include "llvm/IR/Verifier.h" -#include "llvm/Linker/Linker.h" -#include "llvm/Support/CommandLine.h" -#include "llvm/Support/Path.h" -#include "llvm/Support/raw_ostream.h" -#include "llvm/Support/raw_os_ostream.h" -#include "llvm/Transforms/Scalar.h" -#include "llvm/Transforms/Scalar/Scalarizer.h" -#include "llvm/Transforms/Utils/Cloning.h" -#include "llvm/Transforms/Utils.h" DISABLE_WARNING_POP #include <sstream> @@ -57,12 +44,6 @@ cl::OptionCategory } namespace { - enum SwitchImplType { - eSwitchTypeSimple, - eSwitchTypeLLVM, - eSwitchTypeInternal - }; - cl::opt<bool> OutputSource("output-source", cl::desc("Write the assembly for the final transformed source (default=true)"), @@ -75,16 +56,6 @@ namespace { cl::init(false), cl::cat(ModuleCat)); - cl::opt<SwitchImplType> - SwitchType("switch-type", cl::desc("Select the implementation of switch (default=internal)"), - cl::values(clEnumValN(eSwitchTypeSimple, "simple", - "lower to ordered branches"), - clEnumValN(eSwitchTypeLLVM, "llvm", - "lower using LLVM"), - clEnumValN(eSwitchTypeInternal, "internal", - "execute switch internally")), - cl::init(eSwitchTypeInternal), - cl::cat(ModuleCat)); cl::opt<bool> DebugPrintEscapingFunctions("debug-print-escaping-functions", @@ -102,14 +73,21 @@ namespace { cl::desc("Allow optimization of functions that " "contain KLEE calls (default=true)"), cl::init(true), cl::cat(ModuleCat)); -} +cl::opt<SwitchImplType> SwitchType( + "switch-type", + cl::desc("Select the implementation of switch (default=internal)"), + cl::values(clEnumValN(SwitchImplType::eSwitchTypeSimple, "simple", + "lower to ordered branches"), + clEnumValN(SwitchImplType::eSwitchTypeLLVM, "llvm", + "lower using LLVM"), + clEnumValN(SwitchImplType::eSwitchTypeInternal, "internal", + "execute switch internally")), + cl::init(SwitchImplType::eSwitchTypeInternal), cl::cat(ModuleCat)); + +} // namespace /***/ -namespace llvm { -extern void Optimize(Module *, llvm::ArrayRef<const char *> preservedFunctions); -} - // what a hack static Function *getStubFunctionForCtorList(Module *m, GlobalVariable *gv, @@ -156,9 +134,8 @@ static Function *getStubFunctionForCtorList(Module *m, return fn; } -static void -injectStaticConstructorsAndDestructors(Module *m, - llvm::StringRef entryFunction) { +void klee::injectStaticConstructorsAndDestructors( + Module *m, llvm::StringRef entryFunction) { GlobalVariable *ctors = m->getNamedGlobal("llvm.global_ctors"); GlobalVariable *dtors = m->getNamedGlobal("llvm.global_dtors"); @@ -216,44 +193,12 @@ bool KModule::link(std::vector<std::unique_ptr<llvm::Module>> &modules, } void KModule::instrument(const Interpreter::ModuleOptions &opts) { - // Inject checks prior to optimization... we also perform the - // invariant transformations that we will end up doing later so that - // optimize is seeing what is as close as possible to the final - // module. - legacy::PassManager pm; - pm.add(new RaiseAsmPass()); - - // This pass will scalarize as much code as possible so that the Executor - // does not need to handle operands of vector type for most instructions - // other than InsertElementInst and ExtractElementInst. - // - // NOTE: Must come before division/overshift checks because those passes - // don't know how to handle vector instructions. - pm.add(createScalarizerPass()); - - // This pass will replace atomic instructions with non-atomic operations - pm.add(createLowerAtomicPass()); - if (opts.CheckDivZero) pm.add(new DivCheckPass()); - if (opts.CheckOvershift) pm.add(new OvershiftCheckPass()); - - pm.add(new IntrinsicCleanerPass(*targetData)); - pm.run(*module); + klee::instrument(opts.CheckDivZero, opts.CheckOvershift, module.get()); } void KModule::optimiseAndPrepare( const Interpreter::ModuleOptions &opts, llvm::ArrayRef<const char *> preservedFunctions) { - // Preserve all functions containing klee-related function calls from being - // optimised around - if (!OptimiseKLEECall) { - legacy::PassManager pm; - pm.add(new OptNonePass()); - pm.run(*module); - } - - if (opts.Optimize) - Optimize(module.get(), preservedFunctions); - // Add internal functions which are not used to check if instructions // have been already visited if (opts.CheckDivZero) @@ -261,28 +206,8 @@ void KModule::optimiseAndPrepare( if (opts.CheckOvershift) addInternalFunction("klee_overshift_check"); - // Needs to happen after linking (since ctors/dtors can be modified) - // and optimization (since global optimization can rewrite lists). - injectStaticConstructorsAndDestructors(module.get(), opts.EntryPoint); - - // Finally, run the passes that maintain invariants we expect during - // interpretation. We run the intrinsic cleaner just in case we - // linked in something with intrinsics but any external calls are - // going to be unresolved. We really need to handle the intrinsics - // directly I think? - legacy::PassManager pm3; - pm3.add(createCFGSimplificationPass()); - switch(SwitchType) { - case eSwitchTypeInternal: break; - case eSwitchTypeSimple: pm3.add(new LowerSwitchPass()); break; - case eSwitchTypeLLVM: pm3.add(createLowerSwitchPass()); break; - default: klee_error("invalid --switch-type"); - } - pm3.add(new IntrinsicCleanerPass(*targetData)); - pm3.add(createScalarizerPass()); - pm3.add(new PhiCleanerPass()); - pm3.add(new FunctionAliasPass()); - pm3.run(*module); + klee::optimiseAndPrepare(OptimiseKLEECall, opts.Optimize, SwitchType, + opts.EntryPoint, preservedFunctions, module.get()); } void KModule::manifest(InterpreterHandler *ih, bool forceSourceOutput) { @@ -294,7 +219,7 @@ void KModule::manifest(InterpreterHandler *ih, bool forceSourceOutput) { if (OutputModule) { std::unique_ptr<llvm::raw_fd_ostream> f(ih->openOutputFile("final.bc")); - WriteBitcodeToFile(*module, *f); + llvm::WriteBitcodeToFile(*module, *f); } /* Build shadow structures */ @@ -343,23 +268,7 @@ void KModule::manifest(InterpreterHandler *ih, bool forceSourceOutput) { } } -void KModule::checkModule() { - InstructionOperandTypeCheckPass *operandTypeCheckPass = - new InstructionOperandTypeCheckPass(); - - legacy::PassManager pm; - if (!DontVerify) - pm.add(createVerifierPass()); - pm.add(operandTypeCheckPass); - pm.run(*module); - - // Enforce the operand type invariants that the Executor expects. This - // implicitly depends on the "Scalarizer" pass to be run in order to succeed - // in the presence of vector instructions. - if (!operandTypeCheckPass->checkPassed()) { - klee_error("Unexpected instruction operand types detected"); - } -} +void KModule::checkModule() { klee::checkModule(DontVerify, module.get()); } KConstant* KModule::getKConstant(const Constant *c) { auto it = constantMap.find(c); diff --git a/lib/Module/ModuleHelper.h b/lib/Module/ModuleHelper.h new file mode 100644 index 00000000..1b279edd --- /dev/null +++ b/lib/Module/ModuleHelper.h @@ -0,0 +1,37 @@ +//===-- ModuleHelper.h ------------------------------------------*- C++ -*-===// +// +// The KLEE Symbolic Virtual Machine +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef KLEE_MODULEHELPER_H +#define KLEE_MODULEHELPER_H + +#include "llvm/ADT/ArrayRef.h" +#include "llvm/IR/Module.h" + +namespace klee { +enum class SwitchImplType { + eSwitchTypeSimple, + eSwitchTypeLLVM, + eSwitchTypeInternal +}; + +void optimiseAndPrepare(bool OptimiseKLEECall, bool Optimize, + SwitchImplType SwitchType, std::string EntryPoint, + llvm::ArrayRef<const char *> preservedFunctions, + llvm::Module *module); +void checkModule(bool DontVerfify, llvm::Module *module); +void instrument(bool CheckDivZero, bool CheckOvershift, llvm::Module *module); + +void injectStaticConstructorsAndDestructors(llvm::Module *m, + llvm::StringRef entryFunction); + +void optimizeModule(llvm::Module *M, + llvm::ArrayRef<const char *> preservedFunctions); +} // namespace klee + +#endif // KLEE_MODULEHELPER_H diff --git a/lib/Module/Optimize.cpp b/lib/Module/Optimize.cpp index 35b9805a..9475512b 100644 --- a/lib/Module/Optimize.cpp +++ b/lib/Module/Optimize.cpp @@ -15,247 +15,14 @@ // //===----------------------------------------------------------------------===// -#include "klee/Config/Version.h" -#include "klee/Support/OptionCategories.h" +#include "ModuleHelper.h" -#include "klee/Support/CompilerWarning.h" -DISABLE_WARNING_PUSH -DISABLE_WARNING_DEPRECATED_DECLARATIONS -#include "llvm/Analysis/GlobalsModRef.h" -#include "llvm/Analysis/Passes.h" -#include "llvm/Analysis/LoopPass.h" #include "llvm/IR/Module.h" -#include "llvm/IR/DataLayout.h" -#include "llvm/IR/LegacyPassManager.h" -#include "llvm/IR/Verifier.h" -#include "llvm/Support/CommandLine.h" -#include "llvm/Support/DynamicLibrary.h" -#include "llvm/Support/PluginLoader.h" -#include "llvm/Target/TargetMachine.h" -#include "llvm/Transforms/InstCombine/InstCombine.h" -#include "llvm/Transforms/IPO.h" -#include "llvm/Transforms/IPO/FunctionAttrs.h" -#include "llvm/Transforms/Scalar.h" -#include "llvm/Transforms/Scalar/GVN.h" -#include "llvm/Transforms/Utils.h" -DISABLE_WARNING_POP -using namespace llvm; - -static cl::opt<bool> - DisableInline("disable-inlining", - cl::desc("Do not run the inliner pass (default=false)"), - cl::init(false), cl::cat(klee::ModuleCat)); - -static cl::opt<bool> DisableInternalize( - "disable-internalize", - cl::desc("Do not mark all symbols as internal (default=false)"), - cl::init(false), cl::cat(klee::ModuleCat)); - -static cl::opt<bool> VerifyEach( - "verify-each", - cl::desc("Verify intermediate results of all optimization passes (default=false)"), - cl::init(false), - cl::cat(klee::ModuleCat)); - -static cl::alias ExportDynamic("export-dynamic", - cl::aliasopt(DisableInternalize), - cl::desc("Alias for -disable-internalize")); - -static cl::opt<bool> - Strip("strip-all", cl::desc("Strip all symbol information from executable"), - cl::init(false), cl::cat(klee::ModuleCat)); - -static cl::alias A0("s", cl::desc("Alias for --strip-all"), - cl::aliasopt(Strip)); - -static cl::opt<bool> - StripDebug("strip-debug", - cl::desc("Strip debugger symbol info from executable"), - cl::init(false), cl::cat(klee::ModuleCat)); - -static cl::alias A1("S", cl::desc("Alias for --strip-debug"), - cl::aliasopt(StripDebug)); - -// A utility function that adds a pass to the pass manager but will also add -// a verifier pass after if we're supposed to verify. -static inline void addPass(legacy::PassManager &PM, Pass *P) { - // Add the pass to the pass manager... - PM.add(P); - - // If we are verifying all of the intermediate steps, add the verifier... - if (VerifyEach) - PM.add(createVerifierPass()); -} - -namespace llvm { - - -static void AddStandardCompilePasses(legacy::PassManager &PM) { - PM.add(createVerifierPass()); // Verify that input is correct - - // If the -strip-debug command line option was specified, do it. - if (StripDebug) - addPass(PM, createStripSymbolsPass(true)); - - addPass(PM, createCFGSimplificationPass()); // Clean up disgusting code - addPass(PM, createPromoteMemoryToRegisterPass());// Kill useless allocas - addPass(PM, createGlobalOptimizerPass()); // Optimize out global vars - addPass(PM, createGlobalDCEPass()); // Remove unused fns and globs -#if LLVM_VERSION_CODE >= LLVM_VERSION(11, 0) - addPass(PM, createSCCPPass()); // Constant prop with SCCP -#else - addPass(PM, createIPConstantPropagationPass());// IP Constant Propagation -#endif - addPass(PM, createDeadArgEliminationPass()); // Dead argument elimination - addPass(PM, createInstructionCombiningPass()); // Clean up after IPCP & DAE - addPass(PM, createCFGSimplificationPass()); // Clean up after IPCP & DAE - - addPass(PM, createPruneEHPass()); // Remove dead EH info - addPass(PM, createPostOrderFunctionAttrsLegacyPass()); - addPass(PM, createReversePostOrderFunctionAttrsPass()); // Deduce function attrs - - if (!DisableInline) - addPass(PM, createFunctionInliningPass()); // Inline small functions - addPass(PM, createArgumentPromotionPass()); // Scalarize uninlined fn args - - addPass(PM, createInstructionCombiningPass()); // Cleanup for scalarrepl. - addPass(PM, createJumpThreadingPass()); // Thread jumps. - addPass(PM, createCFGSimplificationPass()); // Merge & remove BBs - addPass(PM, createSROAPass()); // Break up aggregate allocas - addPass(PM, createInstructionCombiningPass()); // Combine silly seq's - - addPass(PM, createTailCallEliminationPass()); // Eliminate tail calls - addPass(PM, createCFGSimplificationPass()); // Merge & remove BBs - addPass(PM, createReassociatePass()); // Reassociate expressions - addPass(PM, createLoopRotatePass()); - addPass(PM, createLICMPass()); // Hoist loop invariants - addPass(PM, createLoopUnswitchPass()); // Unswitch loops. - // FIXME : Removing instcombine causes nestedloop regression. - addPass(PM, createInstructionCombiningPass()); - addPass(PM, createIndVarSimplifyPass()); // Canonicalize indvars - addPass(PM, createLoopDeletionPass()); // Delete dead loops - addPass(PM, createLoopUnrollPass()); // Unroll small loops - addPass(PM, createInstructionCombiningPass()); // Clean up after the unroller - addPass(PM, createGVNPass()); // Remove redundancies - addPass(PM, createMemCpyOptPass()); // Remove memcpy / form memset - addPass(PM, createSCCPPass()); // Constant prop with SCCP - - // Run instcombine after redundancy elimination to exploit opportunities - // opened up by them. - addPass(PM, createInstructionCombiningPass()); - - addPass(PM, createDeadStoreEliminationPass()); // Delete dead stores - addPass(PM, createAggressiveDCEPass()); // Delete dead instructions - addPass(PM, createCFGSimplificationPass()); // Merge & remove BBs - addPass(PM, createStripDeadPrototypesPass()); // Get rid of dead prototypes - addPass(PM, createConstantMergePass()); // Merge dup global constants -} - -/// Optimize - Perform link time optimizations. This will run the scalar -/// optimizations, any loaded plugin-optimization modules, and then the -/// inter-procedural optimizations if applicable. -void Optimize(Module *M, llvm::ArrayRef<const char *> preservedFunctions) { - - // Instantiate the pass manager to organize the passes. - legacy::PassManager Passes; - - // If we're verifying, start off with a verification pass. - if (VerifyEach) - Passes.add(createVerifierPass()); - - // DWD - Run the opt standard pass list as well. - AddStandardCompilePasses(Passes); - - // Now that composite has been compiled, scan through the module, looking - // for a main function. If main is defined, mark all other functions - // internal. - if (!DisableInternalize) { - auto PreserveFunctions = [=](const GlobalValue &GV) { - StringRef GVName = GV.getName(); - - for (const char *fun : preservedFunctions) - if (GVName.equals(fun)) - return true; - - return false; - }; - ModulePass *pass = createInternalizePass(PreserveFunctions); - addPass(Passes, pass); - } - - // Propagate constants at call sites into the functions they call. This - // opens opportunities for globalopt (and inlining) by substituting function - // pointers passed as arguments to direct uses of functions. - addPass(Passes, createIPSCCPPass()); - - // Now that we internalized some globals, see if we can hack on them! - addPass(Passes, createGlobalOptimizerPass()); - - // Linking modules together can lead to duplicated global constants, only - // keep one copy of each constant... - addPass(Passes, createConstantMergePass()); - - // Remove unused arguments from functions... - addPass(Passes, createDeadArgEliminationPass()); - - // Reduce the code after globalopt and ipsccp. Both can open up significant - // simplification opportunities, and both can propagate functions through - // function pointers. When this happens, we often have to resolve varargs - // calls, etc, so let instcombine do this. - addPass(Passes, createInstructionCombiningPass()); - - if (!DisableInline) - addPass(Passes, createFunctionInliningPass()); // Inline small functions - - addPass(Passes, createPruneEHPass()); // Remove dead EH info - addPass(Passes, createGlobalOptimizerPass()); // Optimize globals again. - addPass(Passes, createGlobalDCEPass()); // Remove dead functions - - // If we didn't decide to inline a function, check to see if we can - // transform it to pass arguments by value instead of by reference. - addPass(Passes, createArgumentPromotionPass()); - - // The IPO passes may leave cruft around. Clean up after them. - addPass(Passes, createInstructionCombiningPass()); - addPass(Passes, createJumpThreadingPass()); // Thread jumps. - addPass(Passes, createSROAPass()); // Break up allocas - - // Run a few AA driven optimizations here and now, to cleanup the code. - addPass(Passes, createPostOrderFunctionAttrsLegacyPass()); - addPass(Passes, createReversePostOrderFunctionAttrsPass()); // Add nocapture - addPass(Passes, createGlobalsAAWrapperPass()); // IP alias analysis - - addPass(Passes, createLICMPass()); // Hoist loop invariants - addPass(Passes, createGVNPass()); // Remove redundancies - addPass(Passes, createMemCpyOptPass()); // Remove dead memcpy's - addPass(Passes, createDeadStoreEliminationPass()); // Nuke dead stores - - // Cleanup and simplify the code after the scalar optimizations. - addPass(Passes, createInstructionCombiningPass()); - - addPass(Passes, createJumpThreadingPass()); // Thread jumps. - addPass(Passes, createPromoteMemoryToRegisterPass()); // Cleanup jumpthread. - - // Delete basic blocks, which optimization passes may have killed... - addPass(Passes, createCFGSimplificationPass()); - - // Now that we have optimized the program, discard unreachable functions... - addPass(Passes, createGlobalDCEPass()); - - // If the -s or -S command line options were specified, strip the symbols out - // of the resulting program to make it smaller. -s and -S are GNU ld options - // that we are supporting; they alias -strip-all and -strip-debug. - if (Strip || StripDebug) - addPass(Passes, createStripSymbolsPass(StripDebug && !Strip)); - - // The user's passes may leave cruft around; clean up after them. - addPass(Passes, createInstructionCombiningPass()); - addPass(Passes, createCFGSimplificationPass()); - addPass(Passes, createAggressiveDCEPass()); - addPass(Passes, createGlobalDCEPass()); - - // Run our queue of passes all at once now, efficiently. - Passes.run(*M); -} -} +using namespace klee; +void klee::optimiseAndPrepare(bool OptimiseKLEECall, bool Optimize, + SwitchImplType SwitchType, std::string EntryPoint, + llvm::ArrayRef<const char *> preservedFunctions, + llvm::Module *module) { + assert(0); +} \ No newline at end of file diff --git a/lib/Module/OptimizeLegacy.cpp b/lib/Module/OptimizeLegacy.cpp new file mode 100644 index 00000000..53488924 --- /dev/null +++ b/lib/Module/OptimizeLegacy.cpp @@ -0,0 +1,249 @@ +// FIXME: This file is a bastard child of opt.cpp and llvm-ld's +// Optimize.cpp. This stuff should live in common code. + +//===- Optimize.cpp - Optimize a complete program -------------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file implements all optimization of the linked module for llvm-ld. +// +//===----------------------------------------------------------------------===// + +#include "klee/Config/Version.h" +#include "klee/Support/OptionCategories.h" + +#include "klee/Support/CompilerWarning.h" + +#include "ModuleHelper.h" + +DISABLE_WARNING_PUSH +DISABLE_WARNING_DEPRECATED_DECLARATIONS +#include "llvm/Analysis/GlobalsModRef.h" +#include "llvm/Analysis/LoopPass.h" +#include "llvm/IR/LegacyPassManager.h" +#include "llvm/IR/Module.h" +#include "llvm/IR/Verifier.h" +#include "llvm/Support/CommandLine.h" +#include "llvm/Target/TargetMachine.h" +#include "llvm/Transforms/IPO.h" +#include "llvm/Transforms/IPO/FunctionAttrs.h" +#include "llvm/Transforms/InstCombine/InstCombine.h" +#include "llvm/Transforms/Scalar.h" +#include "llvm/Transforms/Scalar/GVN.h" +#include "llvm/Transforms/Utils.h" +DISABLE_WARNING_POP + +using namespace llvm; +using namespace klee; + +namespace { +static cl::opt<bool> + DisableInline("disable-inlining", + cl::desc("Do not run the inliner pass (default=false)"), + cl::init(false), cl::cat(klee::ModuleCat)); + +static cl::opt<bool> DisableInternalize( + "disable-internalize", + cl::desc("Do not mark all symbols as internal (default=false)"), + cl::init(false), cl::cat(klee::ModuleCat)); + +static cl::opt<bool> VerifyEach("verify-each", + cl::desc("Verify intermediate results of all " + "optimization passes (default=false)"), + cl::init(false), cl::cat(klee::ModuleCat)); + +static cl::opt<bool> + Strip("strip-all", cl::desc("Strip all symbol information from executable"), + cl::init(false), cl::cat(klee::ModuleCat)); + +static cl::opt<bool> + StripDebug("strip-debug", + cl::desc("Strip debugger symbol info from executable"), + cl::init(false), cl::cat(klee::ModuleCat)); + +// A utility function that adds a pass to the pass manager but will also add +// a verifier pass after if we're supposed to verify. +static inline void addPass(legacy::PassManager &PM, Pass *P) { + // Add the pass to the pass manager... + PM.add(P); + + // If we are verifying all of the intermediate steps, add the verifier... + if (VerifyEach) + PM.add(createVerifierPass()); +} +} // namespace + +static void AddStandardCompilePasses(legacy::PassManager &PM) { + PM.add(createVerifierPass()); // Verify that input is correct + + // If the -strip-debug command line option was specified, do it. + if (StripDebug) + addPass(PM, createStripSymbolsPass(true)); + + addPass(PM, createCFGSimplificationPass()); // Clean up disgusting code + addPass(PM, createPromoteMemoryToRegisterPass()); // Kill useless allocas + addPass(PM, createGlobalOptimizerPass()); // Optimize out global vars + addPass(PM, createGlobalDCEPass()); // Remove unused fns and globs +#if LLVM_VERSION_CODE >= LLVM_VERSION(11, 0) + addPass(PM, createSCCPPass()); // Constant prop with SCCP +#else + addPass(PM, createIPConstantPropagationPass()); // IP Constant Propagation +#endif + addPass(PM, createDeadArgEliminationPass()); // Dead argument elimination + addPass(PM, createInstructionCombiningPass()); // Clean up after IPCP & DAE + addPass(PM, createCFGSimplificationPass()); // Clean up after IPCP & DAE + + addPass(PM, createPruneEHPass()); // Remove dead EH info + addPass(PM, createPostOrderFunctionAttrsLegacyPass()); + addPass(PM, + createReversePostOrderFunctionAttrsPass()); // Deduce function attrs + + if (!DisableInline) + addPass(PM, createFunctionInliningPass()); // Inline small functions + addPass(PM, createArgumentPromotionPass()); // Scalarize uninlined fn args + + addPass(PM, createInstructionCombiningPass()); // Cleanup for scalarrepl. + addPass(PM, createJumpThreadingPass()); // Thread jumps. + addPass(PM, createCFGSimplificationPass()); // Merge & remove BBs + addPass(PM, createSROAPass()); // Break up aggregate allocas + addPass(PM, createInstructionCombiningPass()); // Combine silly seq's + + addPass(PM, createTailCallEliminationPass()); // Eliminate tail calls + addPass(PM, createCFGSimplificationPass()); // Merge & remove BBs + addPass(PM, createReassociatePass()); // Reassociate expressions + addPass(PM, createLoopRotatePass()); + addPass(PM, createLICMPass()); // Hoist loop invariants + addPass(PM, createLoopUnswitchPass()); // Unswitch loops. + // FIXME : Removing instcombine causes nestedloop regression. + addPass(PM, createInstructionCombiningPass()); + addPass(PM, createIndVarSimplifyPass()); // Canonicalize indvars + addPass(PM, createLoopDeletionPass()); // Delete dead loops + addPass(PM, createLoopUnrollPass()); // Unroll small loops + addPass(PM, createInstructionCombiningPass()); // Clean up after the unroller + addPass(PM, createGVNPass()); // Remove redundancies + addPass(PM, createMemCpyOptPass()); // Remove memcpy / form memset + addPass(PM, createSCCPPass()); // Constant prop with SCCP + + // Run instcombine after redundancy elimination to exploit opportunities + // opened up by them. + addPass(PM, createInstructionCombiningPass()); + + addPass(PM, createDeadStoreEliminationPass()); // Delete dead stores + addPass(PM, createAggressiveDCEPass()); // Delete dead instructions + addPass(PM, createCFGSimplificationPass()); // Merge & remove BBs + addPass(PM, createStripDeadPrototypesPass()); // Get rid of dead prototypes + addPass(PM, createConstantMergePass()); // Merge dup global constants +} + +/// Optimize - Perform link time optimizations. This will run the scalar +/// optimizations, any loaded plugin-optimization modules, and then the +/// inter-procedural optimizations if applicable. +void klee::optimizeModule(llvm::Module *M, + llvm::ArrayRef<const char *> preservedFunctions) { + + // Instantiate the pass manager to organize the passes. + legacy::PassManager Passes; + + // If we're verifying, start off with a verification pass. + if (VerifyEach) + Passes.add(createVerifierPass()); + + // DWD - Run the opt standard pass list as well. + AddStandardCompilePasses(Passes); + + // Now that composite has been compiled, scan through the module, looking + // for a main function. If main is defined, mark all other functions + // internal. + if (!DisableInternalize) { + auto PreserveFunctions = [=](const llvm::GlobalValue &GV) { + StringRef GVName = GV.getName(); + + for (const char *fun : preservedFunctions) + if (GVName.equals(fun)) + return true; + + return false; + }; + ModulePass *pass = createInternalizePass(PreserveFunctions); + addPass(Passes, pass); + } + + // Propagate constants at call sites into the functions they call. This + // opens opportunities for globalopt (and inlining) by substituting function + // pointers passed as arguments to direct uses of functions. + addPass(Passes, createIPSCCPPass()); + + // Now that we internalized some globals, see if we can hack on them! + addPass(Passes, createGlobalOptimizerPass()); + + // Linking modules together can lead to duplicated global constants, only + // keep one copy of each constant... + addPass(Passes, createConstantMergePass()); + + // Remove unused arguments from functions... + addPass(Passes, createDeadArgEliminationPass()); + + // Reduce the code after globalopt and ipsccp. Both can open up significant + // simplification opportunities, and both can propagate functions through + // function pointers. When this happens, we often have to resolve varargs + // calls, etc, so let instcombine do this. + addPass(Passes, createInstructionCombiningPass()); + + if (!DisableInline) + addPass(Passes, createFunctionInliningPass()); // Inline small functions + + addPass(Passes, createPruneEHPass()); // Remove dead EH info + addPass(Passes, createGlobalOptimizerPass()); // Optimize globals again. + addPass(Passes, createGlobalDCEPass()); // Remove dead functions + + // If we didn't decide to inline a function, check to see if we can + // transform it to pass arguments by value instead of by reference. + addPass(Passes, createArgumentPromotionPass()); + + // The IPO passes may leave cruft around. Clean up after them. + addPass(Passes, createInstructionCombiningPass()); + addPass(Passes, createJumpThreadingPass()); // Thread jumps. + addPass(Passes, createSROAPass()); // Break up allocas + + // Run a few AA driven optimizations here and now, to cleanup the code. + addPass(Passes, createPostOrderFunctionAttrsLegacyPass()); + addPass(Passes, createReversePostOrderFunctionAttrsPass()); // Add nocapture + addPass(Passes, createGlobalsAAWrapperPass()); // IP alias analysis + + addPass(Passes, createLICMPass()); // Hoist loop invariants + addPass(Passes, createGVNPass()); // Remove redundancies + addPass(Passes, createMemCpyOptPass()); // Remove dead memcpy's + addPass(Passes, createDeadStoreEliminationPass()); // Nuke dead stores + + // Cleanup and simplify the code after the scalar optimizations. + addPass(Passes, createInstructionCombiningPass()); + + addPass(Passes, createJumpThreadingPass()); // Thread jumps. + addPass(Passes, createPromoteMemoryToRegisterPass()); // Cleanup jumpthread. + + // Delete basic blocks, which optimization passes may have killed... + addPass(Passes, createCFGSimplificationPass()); + + // Now that we have optimized the program, discard unreachable functions... + addPass(Passes, createGlobalDCEPass()); + + // If the -s or -S command line options were specified, strip the symbols out + // of the resulting program to make it smaller. -s and -S are GNU ld options + // that we are supporting; they alias -strip-all and -strip-debug. + if (Strip || StripDebug) + addPass(Passes, createStripSymbolsPass(StripDebug && !Strip)); + + // The user's passes may leave cruft around; clean up after them. + addPass(Passes, createInstructionCombiningPass()); + addPass(Passes, createCFGSimplificationPass()); + addPass(Passes, createAggressiveDCEPass()); + addPass(Passes, createGlobalDCEPass()); + + // Run our queue of passes all at once now, efficiently. + Passes.run(*M); +} |