Author: alenhar2 Date: Mon Aug 6 09:54:33 2007 New Revision: 40860 URL: http://llvm.org/viewvc/llvm-project?rev=40860&view=rev Log: different cloners
Added: poolalloc/branches/SVA/lib/DSA/KPools.cpp Modified: poolalloc/branches/SVA/lib/DSA/LeafRepl.cpp poolalloc/branches/SVA/lib/DSA/Local.cpp Added: poolalloc/branches/SVA/lib/DSA/KPools.cpp URL: http://llvm.org/viewvc/llvm-project/poolalloc/branches/SVA/lib/DSA/KPools.cpp?rev=40860&view=auto ============================================================================== --- poolalloc/branches/SVA/lib/DSA/KPools.cpp (added) +++ poolalloc/branches/SVA/lib/DSA/KPools.cpp Mon Aug 6 09:54:33 2007 @@ -0,0 +1,48 @@ +#include "llvm/Constants.h" +#include "llvm/DerivedTypes.h" +#include "llvm/GlobalValue.h" +#include "llvm/Pass.h" +#include "llvm/Module.h" +#include "llvm/Instructions.h" +#include "llvm/Constants.h" +#include "llvm/Value.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/Support/Debug.h" +#include <iostream> +#include "dsa/DataStructure.h" +#include "dsa/DSGraph.h" +#include "llvm/Support/CallSite.h" + +using namespace llvm; + +namespace { + class KPCount : public ModulePass { + public: + void getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesAll(); + AU.addRequired<TDDataStructures>(); + } + bool runOnModule(Module& M) { + TDDataStructures* T = &getAnalysis<TDDataStructures>(); + Function* f = M.getNamedFunction("kmem_cache_alloc"); + for (Value::use_iterator ii = f->use_begin(), ee = f->use_end(); + ii != ee; ++ii) { + if (CallInst* CI = dyn_cast<CallInst>(*ii)) { + if (LoadInst* LI = dyn_cast<LoadInst>(CI->getOperand(1))) { + CallSite cs = CallSite::get(CI); + DSNode* N = T->getDSGraph(*cs.getCaller()) + .getNodeForValue(CI).getNode(); + if (N->isNodeCompletelyFolded()) + std::cerr << "F "; + else + std::cerr << "S "; + std::cerr << LI->getOperand(0)->getName() << "\n"; + } + } + } + return false; + } + }; + + RegisterPass<KPCount> X("kpcount", "Count Kernel Pool Thingies"); +} Modified: poolalloc/branches/SVA/lib/DSA/LeafRepl.cpp URL: http://llvm.org/viewvc/llvm-project/poolalloc/branches/SVA/lib/DSA/LeafRepl.cpp?rev=40860&r1=40859&r2=40860&view=diff ============================================================================== --- poolalloc/branches/SVA/lib/DSA/LeafRepl.cpp (original) +++ poolalloc/branches/SVA/lib/DSA/LeafRepl.cpp Mon Aug 6 09:54:33 2007 @@ -5,123 +5,128 @@ #include "llvm/DerivedTypes.h" #include "llvm/Transforms/Utils/Cloning.h" #include "llvm/ADT/Statistic.h" +#include "llvm/Support/CommandLine.h" #include <set> +#include <map> #include <vector> #include <algorithm> using namespace llvm; namespace { - Statistic<> FuncAdded("CSCloner", "Number of functions added"); - Statistic<> IndDirSplit("CSCloner", "Number of direct and indirect splits"); + Statistic<> FuncAdded("Cloner", "Number of functions added"); + Statistic<> IndDirSplit("IndCloner", "Number of direct and indirect splits"); Statistic<> LeafClone("CSCloner", "Number of leaves cloned"); Statistic<> ShallowClone("CSCloner", "Number of shallow functions cloned"); Statistic<> ConstantClone("CSCloner", "Number of functions with constant pointers cloned"); + Statistic<> DepthClone("DepthCloner", "Number of functions cloned by depth"); - class CSCloner : public ModulePass { - - bool isLeaf(Function* F) { - for (Function::iterator FI = F->begin(), FE = F->end(); - FI != FE; ++FI) - for (BasicBlock::iterator BI = FI->begin(), BE = FI->end(); - BI != BE; ++BI) - if(isa<CallInst>(BI) || isa<InvokeInst>(BI)) - return false; - return true; - } - - bool isLevelOne(Function* F) { - for (Function::iterator FI = F->begin(), FE = F->end(); - FI != FE; ++FI) - for (BasicBlock::iterator BI = FI->begin(), BE = FI->end(); - BI != BE; ++BI) { - if(LoadInst* LI = dyn_cast<LoadInst>(BI)) - if (isa<PointerType>(LI->getType())) - return false; - if(StoreInst* SI = dyn_cast<StoreInst>(BI)) - if (isa<PointerType>(SI->getOperand(0)->getType())) - return false; - } - return true; - } - - bool isLevelTwo(Function* F) { - for (Function::iterator FI = F->begin(), FE = F->end(); - FI != FE; ++FI) - for (BasicBlock::iterator BI = FI->begin(), BE = FI->end(); - BI != BE; ++BI) { - if(LoadInst* LI = dyn_cast<LoadInst>(BI)) - if (isa<PointerType>(LI->getType())) - for (Value::use_iterator ii = LI->use_begin(), ee = LI->use_end(); - ii != ee; ++ii) - if (isa<LoadInst>(ii)) - return false; - } + static cl::opt<int> + CloneDepth("clone-depth", cl::Hidden, cl::init(4), + cl::desc("depth to clone in the call graph")); + + static Function* clone(Function* F) { + Function* FNew = CloneFunction(F); + FNew->setLinkage(Function::InternalLinkage); + ++FuncAdded; + F->getParent()->getFunctionList().push_back(FNew); + return FNew; + } + + static bool hasPointer(Function* F) { + const FunctionType* FT = F->getFunctionType(); + if (FT->isVarArg() || isa<PointerType>(FT->getReturnType())) return true; - } - - Function* clone(Function* F) { - Function* FNew = CloneFunction(F); - FNew->setLinkage(Function::InternalLinkage); - ++FuncAdded; - F->getParent()->getFunctionList().push_back(FNew); - return FNew; - } - - bool isDirect(Function* F) { - for (Value::use_iterator ii = F->use_begin(), ee = F->use_end(); - ii != ee; ++ii) { - CallInst* CI = dyn_cast<CallInst>(*ii); - if (CI && CI->getCalledFunction() == F) + else + for (FunctionType::param_iterator pi = FT->param_begin(), pe = FT->param_end(); + pi != pe; ++pi) + if (isa<PointerType>(pi->get())) return true; - } - return false; + return false; + } + + static bool isDirect(Function* F) { + for (Value::use_iterator ii = F->use_begin(), ee = F->use_end(); + ii != ee; ++ii) { + CallInst* CI = dyn_cast<CallInst>(*ii); + if (CI && CI->getCalledFunction() == F) + return true; } - - bool isUnknown(Function* F) { - for (Value::use_iterator ii = F->use_begin(), ee = F->use_end(); - ii != ee; ++ii) { - CallInst* CI = dyn_cast<CallInst>(*ii); - if (!CI || CI->getCalledFunction() != F) - return true; - } - return false; + return false; + } + + static bool isUnknown(Function* F) { + for (Value::use_iterator ii = F->use_begin(), ee = F->use_end(); + ii != ee; ++ii) { + CallInst* CI = dyn_cast<CallInst>(*ii); + if (!CI || CI->getCalledFunction() != F) + return true; } - - bool hasPointer(Function* F) { - const FunctionType* FT = F->getFunctionType(); - if (FT->isVarArg() || isa<PointerType>(FT->getReturnType())) + return false; + } + + static bool hasConstArgs(CallInst* CI) { + for (unsigned x = 1; x < CI->getNumOperands(); ++x) + if (isa<Constant>(CI->getOperand(x)) && isa<PointerType>(CI->getOperand(x)->getType())) return true; - else - for (FunctionType::param_iterator pi = FT->param_begin(), pe = FT->param_end(); - pi != pe; ++pi) - if (isa<PointerType>(pi->get())) - return true; - return false; - } - - bool hasConstArgs(CallInst* CI) { - for (unsigned x = 1; x < CI->getNumOperands(); ++x) - if (isa<Constant>(CI->getOperand(x)) && isa<PointerType>(CI->getOperand(x)->getType())) + return false; + } + + static bool hasConstArgs(Function* F) { + for (Value::use_iterator ii = F->use_begin(), ee = F->use_end(); + ii != ee; ++ii) { + CallInst* CI = dyn_cast<CallInst>(*ii); + if (CI && CI->getCalledFunction() == F) + if (hasConstArgs(CI)) return true; - return false; } + return false; + } - bool hasConstArgs(Function* F) { - for (Value::use_iterator ii = F->use_begin(), ee = F->use_end(); - ii != ee; ++ii) { - CallInst* CI = dyn_cast<CallInst>(*ii); - if (CI && CI->getCalledFunction() == F) - if (hasConstArgs(CI)) - return true; + bool isLeaf(Function* F) { + for (Function::iterator FI = F->begin(), FE = F->end(); + FI != FE; ++FI) + for (BasicBlock::iterator BI = FI->begin(), BE = FI->end(); + BI != BE; ++BI) + if(isa<CallInst>(BI) || isa<InvokeInst>(BI)) + return false; + return true; + } + + bool isLevelOne(Function* F) { + for (Function::iterator FI = F->begin(), FE = F->end(); + FI != FE; ++FI) + for (BasicBlock::iterator BI = FI->begin(), BE = FI->end(); + BI != BE; ++BI) { + if(LoadInst* LI = dyn_cast<LoadInst>(BI)) + if (isa<PointerType>(LI->getType())) + return false; + if(StoreInst* SI = dyn_cast<StoreInst>(BI)) + if (isa<PointerType>(SI->getOperand(0)->getType())) + return false; } - return false; - } - + return true; + } + bool isLevelTwo(Function* F) { + for (Function::iterator FI = F->begin(), FE = F->end(); + FI != FE; ++FI) + for (BasicBlock::iterator BI = FI->begin(), BE = FI->end(); + BI != BE; ++BI) { + if(LoadInst* LI = dyn_cast<LoadInst>(BI)) + if (isa<PointerType>(LI->getType())) + for (Value::use_iterator ii = LI->use_begin(), ee = LI->use_end(); + ii != ee; ++ii) + if (isa<LoadInst>(ii)) + return false; + } + return true; + } + + class IndCloner : public ModulePass { public: - bool runOnModuleI(Module& M) { + bool runOnModule(Module& M) { bool changed = false; @@ -129,9 +134,6 @@ std::set<Function*> DirectCalls; std::set<Function*> Unknowns; std::set<Function*> TakesPointers; - std::set<Function*> Leaf; - std::set<Function*> Shallow; - std::set<Function*> ConstantArgs; std::vector<std::string> IgnoreList; IgnoreList.push_back("kmalloc"); IgnoreList.push_back("__vmalloc"); @@ -146,18 +148,12 @@ MI != ME; ++MI) if (!MI->isExternal() && std::find(IgnoreList.begin(), IgnoreList.end(), MI->getName()) == IgnoreList.end()) { - if (isLeaf(MI)) - Leaf.insert(MI); - if (isLevelOne(MI) || isLevelTwo(MI)) - Shallow.insert(MI); if (isDirect(MI)) DirectCalls.insert(MI); if (isUnknown(MI)) Unknowns.insert(MI); if (hasPointer(MI)) TakesPointers.insert(MI); - if (hasConstArgs(MI)) - ConstantArgs.insert(MI); } //now think about replicating some functions @@ -180,7 +176,58 @@ } } } - + } + } + return changed; + } + }; + + class CSCloner : public ModulePass { + public: + bool runOnModule(Module& M) { + + bool changed = false; + + //first figure out how functions are used + std::set<Function*> DirectCalls; + std::set<Function*> Unknowns; + std::set<Function*> TakesPointers; + std::set<Function*> Leaf; + std::set<Function*> Shallow; + std::set<Function*> ConstantArgs; + std::vector<std::string> IgnoreList; + IgnoreList.push_back("kmalloc"); + IgnoreList.push_back("__vmalloc"); + IgnoreList.push_back("kmem_cache_alloc"); + IgnoreList.push_back("__alloc_bootmem"); + IgnoreList.push_back(" __get_free_pages"); + IgnoreList.push_back("kfree"); + IgnoreList.push_back("vfree"); + IgnoreList.push_back("free_pages"); + + for (Module::iterator MI = M.begin(), ME = M.end(); + MI != ME; ++MI) + if (!MI->isExternal() && + std::find(IgnoreList.begin(), IgnoreList.end(), MI->getName()) == IgnoreList.end()) { + if (isLeaf(MI)) + Leaf.insert(MI); + if (isLevelOne(MI) || isLevelTwo(MI)) + Shallow.insert(MI); + if (isDirect(MI)) + DirectCalls.insert(MI); + if (isUnknown(MI)) + Unknowns.insert(MI); + if (hasPointer(MI)) + TakesPointers.insert(MI); + if (hasConstArgs(MI)) + ConstantArgs.insert(MI); + } + + //now think about replicating some functions + for (Module::iterator MI = M.begin(), ME = M.end(); + MI != ME; ++MI) { + if(TakesPointers.find(MI) != TakesPointers.end()) { + //if it takes constants in pointer parameters if (ConstantArgs.find(MI) != ConstantArgs.end() && !MI->hasOneUse() && !MI->use_empty()) { for (Value::use_iterator ii = MI->use_begin(), ee = MI->use_end(); @@ -226,15 +273,92 @@ } return changed; } + }; + class DepthCloner : public ModulePass { + public: + bool runOnModule(Module& M) { + + bool changed = false; + + //first figure out how functions are used + std::set<Function*> DirectCalls; + std::set<Function*> Unknowns; + std::set<Function*> TakesPointers; + std::vector<std::string> IgnoreList; + IgnoreList.push_back("kmalloc"); + IgnoreList.push_back("__vmalloc"); + IgnoreList.push_back("kmem_cache_alloc"); + IgnoreList.push_back("__alloc_bootmem"); + IgnoreList.push_back(" __get_free_pages"); + IgnoreList.push_back("kfree"); + IgnoreList.push_back("vfree"); + IgnoreList.push_back("free_pages"); - virtual bool runOnModule(Module& M) { - // int x = 4; - // while (runOnModuleI(M) && --x) {} - // return true; - return runOnModuleI(M); + std::map<Function*, std::set<Function*> > Callers; + typedef std::map<Function*, std::set<Function*> >::iterator citer; + std::map<Function*, int> Level; + + for (Module::iterator MI = M.begin(), ME = M.end(); + MI != ME; ++MI) + if (!MI->isExternal() && + std::find(IgnoreList.begin(), IgnoreList.end(), MI->getName()) == IgnoreList.end()) { + if (isDirect(MI)) + DirectCalls.insert(MI); + if (isUnknown(MI)) + Unknowns.insert(MI); + if (hasPointer(MI)) + TakesPointers.insert(MI); + for (Function::iterator FI = MI->begin(), FE = MI->end(); + FI != FE; ++FI) + for (BasicBlock::iterator BI = FI->begin(), BE = FI->end(); + BI != BE; ++BI) { + if (isa<CallInst>(BI) && isa<Function>(BI->getOperand(0)) && + BI->getOperand(0) != MI) + Callers[MI].insert(cast<Function>(BI->getOperand(0))); + } + } + + //this doesn't handle mutual recursion + bool c; + do { + c = false; + for (citer ii = Callers.begin(), ee = Callers.end(); ii != ee; ++ii) + for (std::set<Function*>::iterator i = ii->second.begin(), e = ii->second.end(); + i != e; ++i) { + if (Level[ii->first] <= Level[*i] && Level[ii->first] <= CloneDepth) { + ii->second.insert(Callers[*i].begin(), Callers[*i].end()); + c = true; + Level[ii->first] = Level[*i] + 1; + } + } + } while (c); + + //now think about replicating some functions + for (Module::iterator MI = M.begin(), ME = M.end(); + MI != ME; ++MI) { + if(TakesPointers.find(MI) != TakesPointers.end()) { + + //if it is a fixed depth, clone it + if (Level[MI] <= CloneDepth && !MI->hasOneUse() && !MI->use_empty()) { + for (Value::use_iterator ii = MI->use_begin(), ee = MI->use_end(); + ii != ee; ++ii) { + CallInst* CI = dyn_cast<CallInst>(*ii); + if (CI && CI->getCalledFunction() == MI) { + Function* FNew = clone(MI); + ++DepthClone; + changed = true; + CI->setOperand(0, FNew); + } + } + } + } + } + return changed; } }; - RegisterPass<CSCloner> X("csclone", "Cloning for Context Sensitivity"); + RegisterPass<CSCloner> X("csclone", "Cloning for Context Sensitivity"); + RegisterPass<IndCloner> Y("indclone", "Cloning for Context Sensitivity"); + RegisterPass<DepthCloner> Z("depthclone", "Cloning for Context Sensitivity"); } Modified: poolalloc/branches/SVA/lib/DSA/Local.cpp URL: http://llvm.org/viewvc/llvm-project/poolalloc/branches/SVA/lib/DSA/Local.cpp?rev=40860&r1=40859&r2=40860&view=diff ============================================================================== --- poolalloc/branches/SVA/lib/DSA/Local.cpp (original) +++ poolalloc/branches/SVA/lib/DSA/Local.cpp Mon Aug 6 09:54:33 2007 @@ -28,6 +28,7 @@ #include "llvm/Support/Timer.h" #include "poolalloc/Config/config.h" #include <iostream> +#include <queue> // FIXME: This should eventually be a FunctionPass that is automatically // aggregated into a Pass. @@ -43,6 +44,9 @@ std::map<unsigned int, Function*> syscalls; #endif +static Statistic<> CastTraceT ("dsa", "Number of int casts traced successfully"); +static Statistic<> CastTraceF ("dsa", "Number of int casts not traced"); + Statistic<> stat_unknown ("dsa", "Number of markunknowns"); static cl::opt<bool> Crash("dsa-crash", cl::Hidden, @@ -277,6 +281,46 @@ // Helper method implementations... // +static bool getSourcePointerValues(Value* V, std::set<Value*>& sources) { + std::queue<Value*> tocheck; + std::set<Value*> visited; + tocheck.push(V); + while (!tocheck.empty()) { + V = tocheck.front(); + tocheck.pop(); + if (visited.find(V) == visited.end()) { + visited.insert(V); + if (isa<PointerType>(V->getType())) { + sources.insert(V); + } else if (ConstantInt* N = dyn_cast<ConstantInt>(V)) { + if (!(-N->getSExtValue() <= 124 && -N->getSExtValue() >= 0)) { + goto fail; + } + } else if (PHINode* N = dyn_cast<PHINode>(V)) { + for (unsigned x = 0; x < N->getNumIncomingValues(); ++x) + tocheck.push(N->getIncomingValue(x)); + } else if (CastInst* N = dyn_cast<CastInst>(V)) { + tocheck.push(N->getOperand(0)); + } else if (ConstantExpr* N = dyn_cast<ConstantExpr>(V)) { + if (N->getOpcode() == Instruction::Cast) { + tocheck.push(N->getOperand(0)); + } else { + goto fail; + } + } else { + goto fail; + } + } + } + ++CastTraceT; + return true; + fail: + ++CastTraceF; + std::cerr << "Int2Ptr: fail "; + V->dump(); + return false; +} + /// getValueDest - Return the DSNode that the actual value points to. /// DSNodeHandle GraphBuilder::getValueDest(Value &Val) { @@ -298,20 +342,12 @@ N->addGlobal(GV); } else if (Constant *C = dyn_cast<Constant>(V)) { if (ConstantExpr *CE = dyn_cast<ConstantExpr>(C)) { - if (CE->getOpcode() == Instruction::Cast) { - if (isa<PointerType>(CE->getOperand(0)->getType())) - NH = getValueDest(*CE->getOperand(0)); - else - if (CE->getOpcode() == Instruction::Cast && - isa<ConstantInt>(CE->getOperand(0)) && - ( - cast<ConstantInt>(CE->getOperand(0))->equalsInt(1) || - (-cast<ConstantInt>(CE->getOperand(0))->getSExtValue() <= 124 && - -cast<ConstantInt>(CE->getOperand(0))->getSExtValue() >= 0) - )) - NH = createNode(); - else - NH = createNode()->setUnknownNodeMarker(); + std::set<Value*> sources; + if (getSourcePointerValues(CE, sources)) { + NH = createNode(); + for (std::set<Value*>::iterator ii = sources.begin(), ee = sources.end(); + ii != ee; ++ii) + NH.mergeWith(getValueDest(**ii)); } else if (CE->getOpcode() == Instruction::GetElementPtr) { visitGetElementPtrInst(*CE); DSScalarMap::iterator I = ScalarMap.find(CE); @@ -1428,9 +1464,9 @@ } else if (F->getName() == "llva_get_icontext_stackp") { // Create a new DSNode for the memory returned by llva_save_stackp() DSNodeHandle RetNH = getValueDest(*CS.getInstruction()); - RetNH.getNode()->setAllocaNodeMarker(); - RetNH.getNode()->setUnknownNodeMarker(); - RetNH.getNode()->foldNodeCompletely(); + // RetNH.getNode()->setAllocaNodeMarker(); + // RetNH.getNode()->setUnknownNodeMarker(); + // RetNH.getNode()->foldNodeCompletely(); if (DSNode *N = getValueDest(**CS.arg_begin()).getNode()) N->setReadMarker(); return true; @@ -1468,7 +1504,11 @@ // Determine if the called function is one of the specified heap // allocation functions if (AllocList.end() != std::find(AllocList.begin(), AllocList.end(), F->getName())) { - DSNodeHandle RetNH = getValueDest(*CS.getInstruction()); + DSNodeHandle RetNH; + if (F->getName() == "pseudo_alloc") + RetNH = getValueDest(**CS.arg_begin()); + else + RetNH = getValueDest(*CS.getInstruction()); RetNH.getNode()->setHeapNodeMarker()->setModifiedMarker(); RetNH.getNode()->getMP()->addCallSite(CS); return; @@ -1572,15 +1612,20 @@ // don't know about. Make an "Unknown" node. // - if (ConstantInt* I = dyn_cast<ConstantInt>(CI.getOperand(0))) - if (-I->getSExtValue() <= 124 && -I->getSExtValue() >= 0) - setDestTo(CI, createNode()); - - if (DebugUnknown) { - std::cerr << "In " << CI.getParent()->getParent()->getName() << " "; - CI.dump(); - } - setDestTo(CI, createNode()->setUnknownNodeMarker()); + //Try to track all values of ints back to constants or valid pointers + std::set<Value*> sources; + if (getSourcePointerValues(&CI, sources)) { + setDestTo(CI, createNode()); + for (std::set<Value*>::iterator ii = sources.begin(), ee = sources.end(); + ii != ee; ++ii) + getValueDest(CI).mergeWith(getValueDest(**ii)); + } else { + if (DebugUnknown) { + std::cerr << "In " << CI.getParent()->getParent()->getName() << " "; + CI.dump(); + } + setDestTo(CI, createNode()->setUnknownNodeMarker()); + } } } @@ -1754,6 +1799,7 @@ AllocList.push_back("kmem_cache_alloc"); AllocList.push_back("__alloc_bootmem"); AllocList.push_back(" __get_free_pages"); + AllocList.push_back("pseudo_alloc"); #if 0 FreeList.push_back("kfree"); @@ -1761,6 +1807,7 @@ FreeList.push_back("vfree"); FreeList.push_back("free_pages"); FreeList.push_back("kmem_cache_free"); + FreeList.push_back("pseudo_free"); //figure out all system call numbers Function* lrs = M.getNamedFunction("llva_register_syscall"); _______________________________________________ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits