//===- 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 #include // 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(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(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(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(*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(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(SrcTy); unsigned StructIdx = cast(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(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(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(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 &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(CI.getOperand(i)->getType())) DSN->addArgValue(PtrNum++, ValueMap[CI.getOperand(i)]); } void FunctionRepBuilder::visitPHINode(PHINode &PN) { assert(isa(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::iterator I = ValueMap.begin(), E = ValueMap.end(); I != E;) if (isa(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(); } }