diff options
| -rw-r--r-- | include/llvm/Analysis/DSGraph.h | 82 | ||||
| -rw-r--r-- | include/llvm/Analysis/DataStructure/DSGraph.h | 82 | ||||
| -rw-r--r-- | lib/Analysis/DataStructure/DataStructure.cpp | 216 | ||||
| -rw-r--r-- | lib/Analysis/DataStructure/Local.cpp | 111 |
4 files changed, 364 insertions, 127 deletions
diff --git a/include/llvm/Analysis/DSGraph.h b/include/llvm/Analysis/DSGraph.h index 906e9df002..931836a301 100644 --- a/include/llvm/Analysis/DSGraph.h +++ b/include/llvm/Analysis/DSGraph.h @@ -83,6 +83,30 @@ public: //===----------------------------------------------------------------------===// +/// DSTypeRec - This structure is used to represent a single type that is held +/// in a DSNode. +/// +struct DSTypeRec { + const Type *Ty; // The type itself... + unsigned Offset; // The offset in the node + bool isArray; // Have we accessed an array of elements? + + DSTypeRec() : Ty(0), Offset(0), isArray(false) {} + DSTypeRec(const Type *T, unsigned O) : Ty(T), Offset(O), isArray(false) {} + + bool operator<(const DSTypeRec &TR) const { + // Sort first by offset! + return Offset < TR.Offset || (Offset == TR.Offset && Ty < TR.Ty); + } + bool operator==(const DSTypeRec &TR) const { + return Ty == TR.Ty && Offset == TR.Offset; + } + bool operator!=(const DSTypeRec &TR) const { return !operator==(TR); } +}; + + + +//===----------------------------------------------------------------------===// /// DSNode - Data structure node class /// /// This class represents an untyped memory object of Size bytes. It keeps @@ -121,31 +145,11 @@ class DSNode { /// std::vector<DSNodeHandle*> Referrers; - /// TypeRec - This structure is used to represent a single type that is held - /// in a DSNode. - struct TypeRec { - const Type *Ty; // The type itself... - unsigned Offset; // The offset in the node - bool isArray; // Have we accessed an array of elements? - - TypeRec() : Ty(0), Offset(0), isArray(false) {} - TypeRec(const Type *T, unsigned O) : Ty(T), Offset(O), isArray(false) {} - - bool operator<(const TypeRec &TR) const { - // Sort first by offset! - return Offset < TR.Offset || (Offset == TR.Offset && Ty < TR.Ty); - } - bool operator==(const TypeRec &TR) const { - return Ty == TR.Ty && Offset == TR.Offset; - } - bool operator!=(const TypeRec &TR) const { return !operator==(TR); } - }; - /// TypeEntries - As part of the merging process of this algorithm, nodes of /// different types can be represented by this single DSNode. This vector is /// kept sorted. /// - std::vector<TypeRec> TypeEntries; + std::vector<DSTypeRec> TypeEntries; /// Globals - The list of global values that are merged into this node. /// @@ -195,7 +199,7 @@ public: unsigned getSize() const { return MergeMap.size(); } // getTypeEntries - Return the possible types and their offsets in this object - const std::vector<TypeRec> &getTypeEntries() const { return TypeEntries; } + const std::vector<DSTypeRec> &getTypeEntries() const { return TypeEntries; } /// getReferrers - Return a list of the pointers to this node... /// @@ -229,11 +233,35 @@ public: return 0; } + /// getMergeMapLabel - Return the merge map entry specified, to allow printing + /// out of DSNodes nicely for DOT graphs. + /// int getMergeMapLabel(unsigned i) const { assert(i < MergeMap.size() && "MergeMap index out of range!"); return MergeMap[i]; } + /// getTypeRec - This method returns the specified type record if it exists. + /// If it does not yet exist, the method checks to see whether or not the + /// request would result in an untrackable state. If adding it would cause + /// untrackable state, we foldNodeCompletely the node and return the void + /// record, otherwise we add an new TypeEntry and return it. + /// + DSTypeRec &getTypeRec(const Type *Ty, unsigned Offset); + + /// foldNodeCompletely - If we determine that this node has some funny + /// behavior happening to it that we cannot represent, we fold it down to a + /// single, completely pessimistic, node. This node is represented as a + /// single byte with a single TypeEntry of "void". + /// + void foldNodeCompletely(); + + /// isNodeCompletelyFolded - Return true if this node has been completely + /// folded down to something that can never be expanded, effectively losing + /// all of the field sensitivity that may be present in the node. + /// + bool isNodeCompletelyFolded() const; + /// setLink - Set the link at the specified offset to the specified /// NodeHandle, replacing what was there. It is uncommon to use this method, /// instead one of the higher level methods should be used, below. @@ -305,6 +333,16 @@ private: /// rewriting the map entries. /// void mergeMappedValues(signed char V1, signed char V2); + + /// growNode - Attempt to grow the node to the specified size. This may do + /// one of three things: + /// 1. Grow the node, return false + /// 2. Refuse to grow the node, but maintain a trackable situation, return + /// false. + /// 3. Be unable to track if node was that size, so collapse the node and + /// return true. + /// + bool growNode(unsigned RequestedSize); }; diff --git a/include/llvm/Analysis/DataStructure/DSGraph.h b/include/llvm/Analysis/DataStructure/DSGraph.h index 906e9df002..931836a301 100644 --- a/include/llvm/Analysis/DataStructure/DSGraph.h +++ b/include/llvm/Analysis/DataStructure/DSGraph.h @@ -83,6 +83,30 @@ public: //===----------------------------------------------------------------------===// +/// DSTypeRec - This structure is used to represent a single type that is held +/// in a DSNode. +/// +struct DSTypeRec { + const Type *Ty; // The type itself... + unsigned Offset; // The offset in the node + bool isArray; // Have we accessed an array of elements? + + DSTypeRec() : Ty(0), Offset(0), isArray(false) {} + DSTypeRec(const Type *T, unsigned O) : Ty(T), Offset(O), isArray(false) {} + + bool operator<(const DSTypeRec &TR) const { + // Sort first by offset! + return Offset < TR.Offset || (Offset == TR.Offset && Ty < TR.Ty); + } + bool operator==(const DSTypeRec &TR) const { + return Ty == TR.Ty && Offset == TR.Offset; + } + bool operator!=(const DSTypeRec &TR) const { return !operator==(TR); } +}; + + + +//===----------------------------------------------------------------------===// /// DSNode - Data structure node class /// /// This class represents an untyped memory object of Size bytes. It keeps @@ -121,31 +145,11 @@ class DSNode { /// std::vector<DSNodeHandle*> Referrers; - /// TypeRec - This structure is used to represent a single type that is held - /// in a DSNode. - struct TypeRec { - const Type *Ty; // The type itself... - unsigned Offset; // The offset in the node - bool isArray; // Have we accessed an array of elements? - - TypeRec() : Ty(0), Offset(0), isArray(false) {} - TypeRec(const Type *T, unsigned O) : Ty(T), Offset(O), isArray(false) {} - - bool operator<(const TypeRec &TR) const { - // Sort first by offset! - return Offset < TR.Offset || (Offset == TR.Offset && Ty < TR.Ty); - } - bool operator==(const TypeRec &TR) const { - return Ty == TR.Ty && Offset == TR.Offset; - } - bool operator!=(const TypeRec &TR) const { return !operator==(TR); } - }; - /// TypeEntries - As part of the merging process of this algorithm, nodes of /// different types can be represented by this single DSNode. This vector is /// kept sorted. /// - std::vector<TypeRec> TypeEntries; + std::vector<DSTypeRec> TypeEntries; /// Globals - The list of global values that are merged into this node. /// @@ -195,7 +199,7 @@ public: unsigned getSize() const { return MergeMap.size(); } // getTypeEntries - Return the possible types and their offsets in this object - const std::vector<TypeRec> &getTypeEntries() const { return TypeEntries; } + const std::vector<DSTypeRec> &getTypeEntries() const { return TypeEntries; } /// getReferrers - Return a list of the pointers to this node... /// @@ -229,11 +233,35 @@ public: return 0; } + /// getMergeMapLabel - Return the merge map entry specified, to allow printing + /// out of DSNodes nicely for DOT graphs. + /// int getMergeMapLabel(unsigned i) const { assert(i < MergeMap.size() && "MergeMap index out of range!"); return MergeMap[i]; } + /// getTypeRec - This method returns the specified type record if it exists. + /// If it does not yet exist, the method checks to see whether or not the + /// request would result in an untrackable state. If adding it would cause + /// untrackable state, we foldNodeCompletely the node and return the void + /// record, otherwise we add an new TypeEntry and return it. + /// + DSTypeRec &getTypeRec(const Type *Ty, unsigned Offset); + + /// foldNodeCompletely - If we determine that this node has some funny + /// behavior happening to it that we cannot represent, we fold it down to a + /// single, completely pessimistic, node. This node is represented as a + /// single byte with a single TypeEntry of "void". + /// + void foldNodeCompletely(); + + /// isNodeCompletelyFolded - Return true if this node has been completely + /// folded down to something that can never be expanded, effectively losing + /// all of the field sensitivity that may be present in the node. + /// + bool isNodeCompletelyFolded() const; + /// setLink - Set the link at the specified offset to the specified /// NodeHandle, replacing what was there. It is uncommon to use this method, /// instead one of the higher level methods should be used, below. @@ -305,6 +333,16 @@ private: /// rewriting the map entries. /// void mergeMappedValues(signed char V1, signed char V2); + + /// growNode - Attempt to grow the node to the specified size. This may do + /// one of three things: + /// 1. Grow the node, return false + /// 2. Refuse to grow the node, but maintain a trackable situation, return + /// false. + /// 3. Be unable to track if node was that size, so collapse the node and + /// return true. + /// + bool growNode(unsigned RequestedSize); }; diff --git a/lib/Analysis/DataStructure/DataStructure.cpp b/lib/Analysis/DataStructure/DataStructure.cpp index 91c9a7cbd2..cd2c898319 100644 --- a/lib/Analysis/DataStructure/DataStructure.cpp +++ b/lib/Analysis/DataStructure/DataStructure.cpp @@ -31,38 +31,8 @@ using namespace DataStructureAnalysis; //===----------------------------------------------------------------------===// DSNode::DSNode(enum NodeTy NT, const Type *T) : NodeType(NT) { - // If this node is big enough to have pointer fields, add space for them now. - if (T != Type::VoidTy && !isa<FunctionType>(T)) { // Avoid TargetData assert's - MergeMap.resize(TD.getTypeSize(T)); - - // Assign unique values to all of the elements of MergeMap - if (MergeMap.size() < 128) { - // Handle the common case of reasonable size structures... - for (unsigned i = 0, e = MergeMap.size(); i != e; ++i) - MergeMap[i] = -1-i; // Assign -1, -2, -3, ... - } else { - // It's possible that we have something really big here. In this case, - // divide the object into chunks until it will fit into 128 elements. - unsigned Multiple = MergeMap.size()/128; - - // It's probably an array, and probably some power of two in size. - // Because of this, find the biggest power of two that is bigger than - // multiple to use as our real Multiple. - unsigned RealMultiple = 2; - while (RealMultiple <= Multiple) RealMultiple <<= 1; - - unsigned RealBound = MergeMap.size()/RealMultiple; - assert(RealBound <= 128 && "Math didn't work out right"); - - // Now go through and assign indexes that are between -1 and -128 - // inclusive - // - for (unsigned i = 0, e = MergeMap.size(); i != e; ++i) - MergeMap[i] = -1-(i % RealBound); // Assign -1, -2, -3... - } - } - - TypeEntries.push_back(TypeRec(T, 0)); + // Add the type entry if it is specified... + if (T) getTypeRec(T, 0); } // DSNode copy constructor... do not copy over the referrers list! @@ -95,6 +65,44 @@ void DSNode::addGlobal(GlobalValue *GV) { } } +/// foldNodeCompletely - If we determine that this node has some funny +/// behavior happening to it that we cannot represent, we fold it down to a +/// single, completely pessimistic, node. This node is represented as a +/// single byte with a single TypeEntry of "void". +/// +void DSNode::foldNodeCompletely() { + // We are no longer typed at all... + TypeEntries.clear(); + TypeEntries.push_back(DSTypeRec(Type::VoidTy, 0)); + + // Loop over all of our referrers, making them point to our one byte of space. + for (vector<DSNodeHandle*>::iterator I = Referrers.begin(), E=Referrers.end(); + I != E; ++I) + (*I)->setOffset(0); + + // Fold the MergeMap down to a single byte of space... + MergeMap.resize(1); + MergeMap[0] = -1; + + // If we have links, merge all of our outgoing links together... + if (!Links.empty()) { + MergeMap[0] = 0; // We now contain an outgoing edge... + for (unsigned i = 1, e = Links.size(); i != e; ++i) + Links[0].mergeWith(Links[i]); + Links.resize(1); + } +} + +/// isNodeCompletelyFolded - Return true if this node has been completely +/// folded down to something that can never be expanded, effectively losing +/// all of the field sensitivity that may be present in the node. +/// +bool DSNode::isNodeCompletelyFolded() const { + return getSize() == 1 && TypeEntries.size() == 1 && + TypeEntries[0].Ty == Type::VoidTy; +} + + /// setLink - Set the link at the specified offset to the specified /// NodeHandle, replacing what was there. It is uncommon to use this method, @@ -144,6 +152,108 @@ void DSNode::addEdgeTo(unsigned Offset, const DSNodeHandle &NH) { } } +/// getTypeRec - This method returns the specified type record if it exists. +/// If it does not yet exist, the method checks to see whether or not the +/// request would result in an untrackable state. If adding it would cause +/// untrackable state, we foldNodeCompletely the node and return the void +/// record, otherwise we add an new TypeEntry and return it. +/// +DSTypeRec &DSNode::getTypeRec(const Type *Ty, unsigned Offset) { + // If the node is already collapsed, we can't do anything... bail out early + if (isNodeCompletelyFolded()) { + assert(TypeEntries.size() == 1 && "Node folded and Entries.size() != 1?"); + return TypeEntries[0]; + } + + // First search to see if we already have a record for this... + DSTypeRec SearchFor(Ty, Offset); + + std::vector<DSTypeRec>::iterator I; + if (TypeEntries.size() < 5) { // Linear search if we have few entries. + I = TypeEntries.begin(); + while (I != TypeEntries.end() && *I < SearchFor) + ++I; + } else { + I = std::lower_bound(TypeEntries.begin(), TypeEntries.end(), SearchFor); + } + + // At this point, I either points to the right entry or it points to the entry + // we are to insert the new entry in front of... + // + if (I != TypeEntries.end() && *I == SearchFor) + return *I; + + // ASSUME that it's okay to add this type entry. + // FIXME: This should check to make sure it's ok. + + // If the data size is different then our current size, try to resize the node + unsigned ReqSize = Ty->isSized() ? TD.getTypeSize(Ty) : 0; + if (getSize() < ReqSize) { + // If we are trying to make it bigger, and we can grow the node, do so. + if (growNode(ReqSize)) { + assert(isNodeCompletelyFolded() && "Node isn't folded?"); + return TypeEntries[0]; + } + + } else if (getSize() > ReqSize) { + // If we are trying to make the node smaller, we don't have to do anything. + + } + + return *TypeEntries.insert(I, SearchFor); +} + +/// growNode - Attempt to grow the node to the specified size. This may do one +/// of three things: +/// 1. Grow the node, return false +/// 2. Refuse to grow the node, but maintain a trackable situation, return +/// false. +/// 3. Be unable to track if node was that size, so collapse the node and +/// return true. +/// +bool DSNode::growNode(unsigned ReqSize) { + unsigned OldSize = getSize(); + + if (0) { + // FIXME: DSNode::growNode() doesn't perform correct safety checks yet! + + foldNodeCompletely(); + return true; + } + + assert(ReqSize > OldSize && "Not growing node!"); + + // Resize the merge map to have enough space... + MergeMap.resize(ReqSize); + + // Assign unique values to all of the elements of MergeMap + if (ReqSize < 128) { + // Handle the common case of reasonable size structures... + for (unsigned i = OldSize; i != ReqSize; ++i) + MergeMap[i] = -1-i; // Assign -1, -2, -3, ... + } else { + // It's possible that we have something really big here. In this case, + // divide the object into chunks until it will fit into 128 elements. + unsigned Multiple = ReqSize/128; + + // It's probably an array, and probably some power of two in size. + // Because of this, find the biggest power of two that is bigger than + // multiple to use as our real Multiple. + unsigned RealMultiple = 2; + while (RealMultiple <= Multiple) RealMultiple <<= 1; + + unsigned RealBound = ReqSize/RealMultiple; + assert(RealBound <= 128 && "Math didn't work out right"); + + // Now go through and assign indexes that are between -1 and -128 + // inclusive + // + for (unsigned i = OldSize; i != ReqSize; ++i) + MergeMap[i] = -1-(i % RealBound); // Assign -1, -2, -3... + } + return false; +} + /// mergeMappedValues - This is the higher level form of rewriteMergeMap. It is /// fully capable of merging links together if neccesary as well as simply /// rewriting the map entries. @@ -236,11 +346,21 @@ void MergeSortedVectors(vector<T> &Dest, const vector<T> &Src) { void DSNode::mergeWith(const DSNodeHandle &NH, unsigned Offset) { DSNode *N = NH.getNode(); if (N == 0 || (N == this && NH.getOffset() == Offset)) - return; // Noop + return; // Noop assert(NH.getNode() != this && "Cannot merge two portions of the same node yet!"); + // If we are merging a node with a completely folded node, then both nodes are + // now completely folded. + // + if (isNodeCompletelyFolded()) { + NH.getNode()->foldNodeCompletely(); + } else if (NH.getNode()->isNodeCompletelyFolded()) { + foldNodeCompletely(); + Offset = 0; + } + // If both nodes are not at offset 0, make sure that we are merging the node // at an later offset into the node with the zero offset. // @@ -322,27 +442,18 @@ void DSNode::mergeWith(const DSNodeHandle &NH, unsigned Offset) { NodeType |= N->NodeType; N->NodeType = 0; // N is now a dead node. - // If this merging into node has more than just void nodes in it, merge! - assert(!N->TypeEntries.empty() && "TypeEntries is empty for a node?"); - if (N->TypeEntries.size() != 1 || N->TypeEntries[0].Ty != Type::VoidTy) { - // If the current node just has a Void entry in it, remove it. - if (TypeEntries.size() == 1 && TypeEntries[0].Ty == Type::VoidTy) - TypeEntries.clear(); - - // Adjust all of the type entries we are merging in by the offset... and add - // them to the TypeEntries list. - // - if (NOffset != 0) { // This case is common enough to optimize for - // Offset all of the TypeEntries in N with their new offset - for (unsigned i = 0, e = N->TypeEntries.size(); i != e; ++i) - N->TypeEntries[i].Offset += NOffset; - } - - MergeSortedVectors(TypeEntries, N->TypeEntries); - - N->TypeEntries.clear(); + // Adjust all of the type entries we are merging in by the offset... + // + if (NOffset != 0) { // This case is common enough to optimize for + // Offset all of the TypeEntries in N with their new offset + for (unsigned i = 0, e = N->TypeEntries.size(); i != e; ++i) + N->TypeEntries[i].Offset += NOffset; } + // ... now add them to the TypeEntries list. + MergeSortedVectors(TypeEntries, N->TypeEntries); + N->TypeEntries.clear(); // N is dead, no type-entries need exist + // Merge the globals list... if (!N->Globals.empty()) { MergeSortedVectors(Globals, N->Globals); @@ -408,6 +519,7 @@ static void CopyFunctionCallsList(const vector<DSCallSite>& fromCalls, /// remapLinks - Change all of the Links in the current node according to the /// specified mapping. +/// void DSNode::remapLinks(std::map<const DSNode*, DSNode*> &OldNodeMap) { for (unsigned i = 0, e = Links.size(); i != e; ++i) Links[i].setNode(OldNodeMap[Links[i].getNode()]); diff --git a/lib/Analysis/DataStructure/Local.cpp b/lib/Analysis/DataStructure/Local.cpp index 210bbec023..0cdb0e16a9 100644 --- a/lib/Analysis/DataStructure/Local.cpp +++ b/lib/Analysis/DataStructure/Local.cpp @@ -61,6 +61,7 @@ namespace { vector<DSNode*> &Nodes; DSNodeHandle &RetNode; // Node that gets returned... map<Value*, DSNodeHandle> &ValueMap; + map<GlobalValue*, DSNodeHandle> GlobalScalarValueMap; vector<DSCallSite> &FunctionCalls; public: @@ -112,7 +113,7 @@ namespace { /// value. This either returns the already existing node, or creates a new /// one and adds it to the graph, if none exists. /// - DSNodeHandle getValueNode(Value &V); + DSNodeHandle &getValueNode(Value &V); /// getValueDest - Return the DSNode that the actual value points to. This /// is basically the same thing as: getLink(getValueNode(V), 0) @@ -184,25 +185,37 @@ DSNodeHandle &GraphBuilder::getGlobalNode(GlobalValue &V) { // This either returns the already existing node, or creates a new one and adds // it to the graph, if none exists. // -DSNodeHandle GraphBuilder::getValueNode(Value &V) { +DSNodeHandle &GraphBuilder::getValueNode(Value &V) { assert(isPointerType(V.getType()) && "Should only use pointer scalars!"); - DSNodeHandle &NH = ValueMap[&V]; - if (NH.getNode()) return NH; // Already have a node? Just return it... - - // Otherwise we need to create a new scalar node... - DSNode *N = createNode(DSNode::ScalarNode, V.getType()); - - // If this is a global value, create the global pointed to. if (GlobalValue *GV = dyn_cast<GlobalValue>(&V)) { + // The GlobalScalarValueMap keeps track of the scalar nodes that point to + // global values... The ValueMap contains pointers to the global memory + // object itself, not the scalar constant that points to the memory. + // + DSNodeHandle &NH = GlobalScalarValueMap[GV]; + if (NH.getNode()) return NH; + + // If this is a global value, create the global pointed to. + DSNode *N = createNode(DSNode::ScalarNode, V.getType()); + NH.setOffset(0); + NH.setNode(N); + N->addEdgeTo(0, getGlobalNode(*GV)); - return DSNodeHandle(N, 0); + return NH; + } else { + DSNodeHandle &NH = ValueMap[&V]; + if (NH.getNode()) + return NH; // Already have a node? Just return it... + + // Otherwise we need to create a new scalar node... + DSNode *N = createNode(DSNode::ScalarNode, V.getType()); + NH.setOffset(0); NH.setNode(N); + return NH; } - - return NH; } /// getValueDest - Return the DSNode that the actual value points to. This @@ -220,27 +233,25 @@ DSNodeHandle &GraphBuilder::getValueDest(Value &V) { /// type should be linked to if we need to create a new node. /// DSNodeHandle &GraphBuilder::getLink(const DSNodeHandle &node, - unsigned LinkNo, const Type *FieldTy) { + unsigned LinkNo, + const Type *FieldTy // FIXME: eliminate + ) { DSNodeHandle &Node = const_cast<DSNodeHandle&>(node); - DSNodeHandle *Link = Node.getLink(LinkNo); if (Link) return *Link; - - // If the link hasn't been created yet, make and return a new shadow node of - // the appropriate type for FieldTy... - // +#if 0 // FIXME: delete // If we are indexing with a typed pointer, then the thing we are pointing // to is of the pointed type. If we are pointing to it with an integer // (because of cast to an integer), we represent it with a void type. // - const Type *ReqTy; + const Type *ReqTy = 0; if (const PointerType *Ptr = dyn_cast<PointerType>(FieldTy)) ReqTy = Ptr->getElementType(); - else - ReqTy = Type::VoidTy; +#endif - DSNode *N = createNode(DSNode::ShadowNode, ReqTy); + // If the link hasn't been created yet, make and return a new shadow node + DSNode *N = createNode(DSNode::ShadowNode, 0); Node.setLink(LinkNo, N); return *Node.getLink(LinkNo); } @@ -254,8 +265,7 @@ DSNodeHandle &GraphBuilder::getLink(const DSNodeHandle &node, /// object, pointing the scalar to it. /// void GraphBuilder::handleAlloc(AllocationInst &AI, DSNode::NodeTy NodeType) { - //DSNode *New = createNode(NodeType, Type::VoidTy); - DSNode *New = createNode(NodeType, AI.getAllocatedType()); + DSNode *New = createNode(NodeType, 0); // Make the scalar point to the new node... getValueNode(AI).addEdgeTo(New); @@ -277,18 +287,50 @@ void GraphBuilder::visitGetElementPtrInst(GetElementPtrInst &GEP) { DSNodeHandle Value = getValueDest(*GEP.getOperand(0)); unsigned Offset = 0; - const Type *CurTy = GEP.getOperand(0)->getType(); + const PointerType *PTy = cast<PointerType>(GEP.getOperand(0)->getType()); + const Type *CurTy = PTy->getElementType(); + DSTypeRec &TopTypeRec = + Value.getNode()->getTypeRec(PTy->getElementType(), Value.getOffset()); + + // If the node had to be folded... exit quickly + if (TopTypeRec.Ty == Type::VoidTy) { + getValueNode(GEP).addEdgeTo(Value); // GEP result points to folded node + return; + } + + // Handle the pointer index specially... + if (GEP.getNumOperands() > 1 && + GEP.getOperand(1) != ConstantSInt::getNullValue(Type::LongTy)) { + + // If we already know this is an array being accessed, don't do anything... + if (!TopTypeRec.isArray) { + TopTypeRec.isArray = true; + + // If we are treating some inner field pointer as an array, fold the node + // up because we cannot handle it right. This can come because of + // something like this: &((&Pt->X)[1]) == &Pt->Y + // + if (Value.getOffset()) { + // Value is now the pointer we want to GEP to be... + Value.getNode()->foldNodeCompletely(); + getValueNode(GEP).addEdgeTo(Value); // GEP result points to folded node + return; + } else { + // This is a pointer to the first byte of the node. Make sure that we + // are pointing to the outter most type in the node. + // FIXME: We need to check one more case here... + } + } + } - for (unsigned i = 1, e = GEP.getNumOperands(); i != e; ++i) + // All of these subscripts are indexing INTO the elements we have... + for (unsigned i = 2, e = GEP.getNumOperands(); i < e; ++i) if (GEP.getOperand(i)->getType() == Type::LongTy) { // Get the type indexing into... const SequentialType *STy = cast<SequentialType>(CurTy); CurTy = STy->getElementType(); if (ConstantSInt *CS = dyn_cast<ConstantSInt>(GEP.getOperand(i))) { - if (isa<PointerType>(STy)) - std::cerr << "Pointer indexing not handled yet!\n"; - else - Offset += CS->getValue()*TD.getTypeSize(CurTy); + Offset += CS->getValue()*TD.getTypeSize(CurTy); } else { // Variable index into a node. We must merge all of the elements of the // sequential type here. @@ -326,6 +368,9 @@ void GraphBuilder::visitGetElementPtrInst(GetElementPtrInst &GEP) { void GraphBuilder::visitLoadInst(LoadInst &LI) { DSNodeHandle &Ptr = getValueDest(*LI.getOperand(0)); Ptr.getNode()->NodeType |= DSNode::Read; + + // Ensure a typerecord exists... + Ptr.getNode()->getTypeRec(LI.getType(), Ptr.getOffset()); if (isPointerType(LI.getType())) getValueNode(LI).addEdgeTo(getLink(Ptr, 0, LI.getType())); @@ -334,9 +379,13 @@ void GraphBuilder::visitLoadInst(LoadInst &LI) { void GraphBuilder::visitStoreInst(StoreInst &SI) { DSNodeHandle &Dest = getValueDest(*SI.getOperand(1)); Dest.getNode()->NodeType |= DSNode::Modified; + const Type *StoredTy = SI.getOperand(0)->getType(); + + // Ensure a typerecord exists... + Dest.getNode()->getTypeRec(StoredTy, Dest.getOffset()); // Avoid adding edges from null, or processing non-"pointer" stores - if (isPointerType(SI.getOperand(0)->getType()) && + if (isPointerType(StoredTy) && !isa<ConstantPointerNull>(SI.getOperand(0))) { Dest.addEdgeTo(getValueDest(*SI.getOperand(0))); } |