diff options
Diffstat (limited to 'lib/Analysis/DataStructure/FunctionRepBuilder.cpp')
| -rw-r--r-- | lib/Analysis/DataStructure/FunctionRepBuilder.cpp | 365 |
1 files changed, 0 insertions, 365 deletions
diff --git a/lib/Analysis/DataStructure/FunctionRepBuilder.cpp b/lib/Analysis/DataStructure/FunctionRepBuilder.cpp deleted file mode 100644 index be49eec177..0000000000 --- a/lib/Analysis/DataStructure/FunctionRepBuilder.cpp +++ /dev/null @@ -1,365 +0,0 @@ -//===- FunctionRepBuilder.cpp - Build the local datastructure graph -------===// -// -// Build the local datastructure graph for a single method. -// -//===----------------------------------------------------------------------===// - -#include "FunctionRepBuilder.h" -#include "llvm/Function.h" -#include "llvm/BasicBlock.h" -#include "llvm/iMemory.h" -#include "llvm/iPHINode.h" -#include "llvm/iOther.h" -#include "llvm/iTerminators.h" -#include "llvm/DerivedTypes.h" -#include "llvm/Constants.h" -#include "Support/STLExtras.h" -#include <algorithm> - -// synthesizeNode - Create a new shadow node that is to be linked into this -// chain.. -// FIXME: This should not take a FunctionRepBuilder as an argument! -// -ShadowDSNode *DSNode::synthesizeNode(const Type *Ty, - FunctionRepBuilder *Rep) { - // If we are a derived shadow node, defer to our parent to synthesize the node - if (ShadowDSNode *Th = dyn_cast<ShadowDSNode>(this)) - if (Th->getShadowParent()) - return Th->getShadowParent()->synthesizeNode(Ty, Rep); - - // See if we have already synthesized a node of this type... - for (unsigned i = 0, e = SynthNodes.size(); i != e; ++i) - if (SynthNodes[i].first == Ty) return SynthNodes[i].second; - - // No we haven't. Do so now and add it to our list of saved nodes... - - ShadowDSNode *SN = Rep->makeSynthesizedShadow(Ty, this); - SynthNodes.push_back(std::make_pair(Ty, SN)); - - return SN; -} - -ShadowDSNode *FunctionRepBuilder::makeSynthesizedShadow(const Type *Ty, - DSNode *Parent) { - ShadowDSNode *Result = new ShadowDSNode(Ty, F->getFunction()->getParent(), - Parent); - ShadowNodes.push_back(Result); - return Result; -} - - - -// visitOperand - If the specified instruction operand is a global value, add -// a node for it... -// -void InitVisitor::visitOperand(Value *V) { - if (!Rep->ValueMap.count(V)) // Only process it once... - if (GlobalValue *GV = dyn_cast<GlobalValue>(V)) { - GlobalDSNode *N = new GlobalDSNode(GV); - Rep->GlobalNodes.push_back(N); - Rep->ValueMap[V].add(N); - Rep->addAllUsesToWorkList(GV); - - // FIXME: If the global variable has fields, we should add critical - // shadow nodes to represent them! - } -} - - -// visitCallInst - Create a call node for the callinst, and create as shadow -// node if the call returns a pointer value. Check to see if the call node -// uses any global variables... -// -void InitVisitor::visitCallInst(CallInst &CI) { - CallDSNode *C = new CallDSNode(&CI); - Rep->CallNodes.push_back(C); - Rep->CallMap[&CI] = C; - - if (const PointerType *PT = dyn_cast<PointerType>(CI.getType())) { - // Create a critical shadow node to represent the memory object that the - // return value points to... - ShadowDSNode *Shad = new ShadowDSNode(PT->getElementType(), - Func->getParent()); - Rep->ShadowNodes.push_back(Shad); - - // The return value of the function is a pointer to the shadow value - // just created... - // - C->getLink(0).add(Shad); - - // The call instruction returns a pointer to the shadow block... - Rep->ValueMap[&CI].add(Shad, &CI); - - // If the call returns a value with pointer type, add all of the users - // of the call instruction to the work list... - Rep->addAllUsesToWorkList(&CI); - } - - // Loop over all of the operands of the call instruction (except the first - // one), to look for global variable references... - // - for_each(CI.op_begin(), CI.op_end(), - bind_obj(this, &InitVisitor::visitOperand)); -} - - -// visitAllocationInst - Create an allocation node for the allocation. Since -// allocation instructions do not take pointer arguments, they cannot refer to -// global vars... -// -void InitVisitor::visitAllocationInst(AllocationInst &AI) { - AllocDSNode *N = new AllocDSNode(&AI); - Rep->AllocNodes.push_back(N); - - Rep->ValueMap[&AI].add(N, &AI); - - // Add all of the users of the malloc instruction to the work list... - Rep->addAllUsesToWorkList(&AI); -} - - -// Visit all other instruction types. Here we just scan, looking for uses of -// global variables... -// -void InitVisitor::visitInstruction(Instruction &I) { - for_each(I.op_begin(), I.op_end(), - bind_obj(this, &InitVisitor::visitOperand)); -} - - -// addAllUsesToWorkList - Add all of the instructions users of the specified -// value to the work list for further processing... -// -void FunctionRepBuilder::addAllUsesToWorkList(Value *V) { - //cerr << "Adding all uses of " << V << "\n"; - for (Value::use_iterator I = V->use_begin(), E = V->use_end(); I != E; ++I) { - Instruction *Inst = cast<Instruction>(*I); - // When processing global values, it's possible that the instructions on - // the use list are not all in this method. Only add the instructions - // that _are_ in this method. - // - if (Inst->getParent()->getParent() == F->getFunction()) - // Only let an instruction occur on the work list once... - if (std::find(WorkList.begin(), WorkList.end(), Inst) == WorkList.end()) - WorkList.push_back(Inst); - } -} - - - - -void FunctionRepBuilder::initializeWorkList(Function *Func) { - // Add all of the arguments to the method to the graph and add all users to - // the worklists... - // - for (Function::aiterator I = Func->abegin(), E = Func->aend(); I != E; ++I) { - // Only process arguments that are of pointer type... - if (const PointerType *PT = dyn_cast<PointerType>(I->getType())) { - // Add a shadow value for it to represent what it is pointing to and add - // this to the value map... - ShadowDSNode *Shad = new ShadowDSNode(PT->getElementType(), - Func->getParent()); - ShadowNodes.push_back(Shad); - ValueMap[I].add(PointerVal(Shad), I); - - // Make sure that all users of the argument are processed... - addAllUsesToWorkList(I); - } - } - - // Iterate over the instructions in the method. Create nodes for malloc and - // call instructions. Add all uses of these to the worklist of instructions - // to process. - // - InitVisitor IV(this, Func); - IV.visit(Func); -} - - - - -PointerVal FunctionRepBuilder::getIndexedPointerDest(const PointerVal &InP, - const MemAccessInst &MAI) { - unsigned Index = InP.Index; - const Type *SrcTy = MAI.getPointerOperand()->getType(); - - for (MemAccessInst::const_op_iterator I = MAI.idx_begin(), - E = MAI.idx_end(); I != E; ++I) - if ((*I)->getType() == Type::UByteTy) { // Look for struct indices... - const StructType *STy = cast<StructType>(SrcTy); - unsigned StructIdx = cast<ConstantUInt>(I->get())->getValue(); - for (unsigned i = 0; i != StructIdx; ++i) - Index += countPointerFields(STy->getContainedType(i)); - - // Advance SrcTy to be the new element type... - SrcTy = STy->getContainedType(StructIdx); - } else { - // Otherwise, stepping into array or initial pointer, just increment type - SrcTy = cast<SequentialType>(SrcTy)->getElementType(); - } - - return PointerVal(InP.Node, Index); -} - -static PointerValSet &getField(const PointerVal &DestPtr) { - assert(DestPtr.Node != 0); - return DestPtr.Node->getLink(DestPtr.Index); -} - - -// Reprocessing a GEP instruction is the result of the pointer operand -// changing. This means that the set of possible values for the GEP -// needs to be expanded. -// -void FunctionRepBuilder::visitGetElementPtrInst(GetElementPtrInst &GEP) { - PointerValSet &GEPPVS = ValueMap[&GEP]; // PointerValSet to expand - - // Get the input pointer val set... - const PointerValSet &SrcPVS = ValueMap[GEP.getOperand(0)]; - - bool Changed = false; // Process each input value... propogating it. - for (unsigned i = 0, e = SrcPVS.size(); i != e; ++i) { - // Calculate where the resulting pointer would point based on an - // input of 'Val' as the pointer type... and add it to our outgoing - // value set. Keep track of whether or not we actually changed - // anything. - // - Changed |= GEPPVS.add(getIndexedPointerDest(SrcPVS[i], GEP)); - } - - // If our current value set changed, notify all of the users of our - // value. - // - if (Changed) addAllUsesToWorkList(&GEP); -} - -void FunctionRepBuilder::visitReturnInst(ReturnInst &RI) { - RetNode.add(ValueMap[RI.getOperand(0)]); -} - -void FunctionRepBuilder::visitLoadInst(LoadInst &LI) { - // Only loads that return pointers are interesting... - const PointerType *DestTy = dyn_cast<PointerType>(LI.getType()); - if (DestTy == 0) return; - - const PointerValSet &SrcPVS = ValueMap[LI.getOperand(0)]; - PointerValSet &LIPVS = ValueMap[&LI]; - - bool Changed = false; - for (unsigned si = 0, se = SrcPVS.size(); si != se; ++si) { - PointerVal Ptr = getIndexedPointerDest(SrcPVS[si], LI); - PointerValSet &Field = getField(Ptr); - - if (Field.size()) { // Field loaded wasn't null? - Changed |= LIPVS.add(Field); - } else { - // If we are loading a null field out of a shadow node, we need to - // synthesize a new shadow node and link it in... - // - ShadowDSNode *SynthNode = - Ptr.Node->synthesizeNode(DestTy->getElementType(), this); - Field.add(SynthNode); - - Changed |= LIPVS.add(Field); - } - } - - if (Changed) addAllUsesToWorkList(&LI); -} - -void FunctionRepBuilder::visitStoreInst(StoreInst &SI) { - // The only stores that are interesting are stores the store pointers - // into data structures... - // - if (!isa<PointerType>(SI.getOperand(0)->getType())) return; - if (!ValueMap.count(SI.getOperand(0))) return; // Src scalar has no values! - - const PointerValSet &SrcPVS = ValueMap[SI.getOperand(0)]; - const PointerValSet &PtrPVS = ValueMap[SI.getOperand(1)]; - - for (unsigned si = 0, se = SrcPVS.size(); si != se; ++si) { - const PointerVal &SrcPtr = SrcPVS[si]; - for (unsigned pi = 0, pe = PtrPVS.size(); pi != pe; ++pi) { - PointerVal Dest = getIndexedPointerDest(PtrPVS[pi], SI); - -#if 0 - std::cerr << "Setting Dest:\n"; - Dest.print(std::cerr); - std::cerr << "to point to Src:\n"; - SrcPtr.print(std::cerr); -#endif - - // Add SrcPtr into the Dest field... - if (getField(Dest).add(SrcPtr)) { - // If we modified the dest field, then invalidate everyone that points - // to Dest. - const std::vector<Value*> &Ptrs = Dest.Node->getPointers(); - for (unsigned i = 0, e = Ptrs.size(); i != e; ++i) - addAllUsesToWorkList(Ptrs[i]); - } - } - } -} - -void FunctionRepBuilder::visitCallInst(CallInst &CI) { - CallDSNode *DSN = CallMap[&CI]; - unsigned PtrNum = 0; - for (unsigned i = 0, e = CI.getNumOperands(); i != e; ++i) - if (isa<PointerType>(CI.getOperand(i)->getType())) - DSN->addArgValue(PtrNum++, ValueMap[CI.getOperand(i)]); -} - -void FunctionRepBuilder::visitPHINode(PHINode &PN) { - assert(isa<PointerType>(PN.getType()) && "Should only update ptr phis"); - - PointerValSet &PN_PVS = ValueMap[&PN]; - bool Changed = false; - for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) - Changed |= PN_PVS.add(ValueMap[PN.getIncomingValue(i)], - PN.getIncomingValue(i)); - - if (Changed) addAllUsesToWorkList(&PN); -} - - - - -// FunctionDSGraph constructor - Perform the global analysis to determine -// what the data structure usage behavior or a method looks like. -// -FunctionDSGraph::FunctionDSGraph(Function *F) : Func(F) { - FunctionRepBuilder Builder(this); - AllocNodes = Builder.getAllocNodes(); - ShadowNodes = Builder.getShadowNodes(); - GlobalNodes = Builder.getGlobalNodes(); - CallNodes = Builder.getCallNodes(); - RetNode = Builder.getRetNode(); - ValueMap = Builder.getValueMap(); - - // Remove all entries in the value map that consist of global values pointing - // at things. They can only point to their node, so there is no use keeping - // them. - // - for (std::map<Value*, PointerValSet>::iterator I = ValueMap.begin(), - E = ValueMap.end(); I != E;) - if (isa<GlobalValue>(I->first)) { -#if MAP_DOESNT_HAVE_BROKEN_ERASE_MEMBER - I = ValueMap.erase(I); -#else - ValueMap.erase(I); // This is really lame. - I = ValueMap.begin(); // GCC's stdc++ lib doesn't return an it! -#endif - } else - ++I; - - bool Changed = true; - while (Changed) { - // Eliminate shadow nodes that are not distinguishable from some other - // node in the graph... - // - Changed = UnlinkUndistinguishableNodes(); - - // Eliminate shadow nodes that are now extraneous due to linking... - Changed |= RemoveUnreachableNodes(); - } -} |