//===- Local.cpp - Compute a local data structure graph for a function ----===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file was developed by the LLVM research group and is distributed under
+// the University of Illinois Open Source License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
//
// Compute the local version of the data structure graph for a function. The
// external interface to this file is the DSGraph constructor.
#include "llvm/Analysis/DSGraph.h"
#include "llvm/Constants.h"
#include "llvm/DerivedTypes.h"
-#include "llvm/Function.h"
-#include "llvm/GlobalVariable.h"
#include "llvm/Instructions.h"
+#include "llvm/Support/GetElementPtrTypeIterator.h"
#include "llvm/Support/InstVisitor.h"
#include "llvm/Target/TargetData.h"
#include "Support/CommandLine.h"
//
#include "llvm/Module.h"
+using namespace llvm;
+
static RegisterAnalysis<LocalDataStructures>
X("datastructure", "Local Data Structure Analysis");
-namespace DS {
- // FIXME: Do something smarter with target data!
- TargetData TD("temp-td");
+static cl::opt<bool>
+TrackIntegersAsPointers("dsa-track-integers",
+ cl::desc("If this is set, track integers as potential pointers"));
+
+namespace llvm {
+namespace DS {
// isPointerType - Return true if this type is big enough to hold a pointer.
bool isPointerType(const Type *Ty) {
if (isa<PointerType>(Ty))
return true;
- else if (Ty->isPrimitiveType() && Ty->isInteger())
+ else if (TrackIntegersAsPointers && Ty->isPrimitiveType() &&Ty->isInteger())
return Ty->getPrimitiveSize() >= PointerSize;
return false;
}
-}
-using namespace DS;
+}}
+using namespace DS;
namespace {
cl::opt<bool>
};
}
+using namespace DS;
+
//===----------------------------------------------------------------------===//
// DSGraph constructor - Simply use the GraphBuilder to construct the local
// graph.
-DSGraph::DSGraph(Function &F, DSGraph *GG) : GlobalsGraph(GG) {
+DSGraph::DSGraph(const TargetData &td, Function &F, DSGraph *GG)
+ : GlobalsGraph(GG), TD(td) {
PrintAuxCalls = false;
DEBUG(std::cerr << " [Loc] Calculating graph for: " << F.getName() << "\n");
DSNodeHandle Value = getValueDest(*GEP.getOperand(0));
if (Value.getNode() == 0) return;
+ // As a special case, if all of the index operands of GEP are constant zeros,
+ // handle this just like we handle casts (ie, don't do much).
+ bool AllZeros = true;
+ for (unsigned i = 1, e = GEP.getNumOperands(); i != e; ++i)
+ if (GEP.getOperand(i) !=
+ Constant::getNullValue(GEP.getOperand(i)->getType())) {
+ AllZeros = false;
+ break;
+ }
+
+ // If all of the indices are zero, the result points to the operand without
+ // applying the type.
+ if (AllZeros) {
+ setDestTo(GEP, Value);
+ return;
+ }
+
+
const PointerType *PTy = cast<PointerType>(GEP.getOperand(0)->getType());
const Type *CurTy = PTy->getElementType();
return;
}
+ const TargetData &TD = Value.getNode()->getTargetData();
+
#if 0
// Handle the pointer index specially...
if (GEP.getNumOperands() > 1 &&
// All of these subscripts are indexing INTO the elements we have...
unsigned Offset = 0;
- 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();
+ for (gep_type_iterator I = gep_type_begin(GEP), E = gep_type_end(GEP);
+ I != E; ++I)
+ if (const StructType *STy = dyn_cast<StructType>(*I)) {
+ unsigned FieldNo = cast<ConstantUInt>(I.getOperand())->getValue();
+ Offset += TD.getStructLayout(STy)->MemberOffsets[FieldNo];
+ }
+
+
#if 0
+ if (const SequentialType *STy = cast<SequentialType>(*I)) {
+ CurTy = STy->getElementType();
if (ConstantSInt *CS = dyn_cast<ConstantSInt>(GEP.getOperand(i))) {
Offset += CS->getValue()*TD.getTypeSize(CurTy);
} else {
N->mergeIndexes(RawOffset+j, RawOffset+i*ElSize+j);
}
}
-#endif
- } else if (GEP.getOperand(i)->getType() == Type::UByteTy) {
- unsigned FieldNo = cast<ConstantUInt>(GEP.getOperand(i))->getValue();
- const StructType *STy = cast<StructType>(CurTy);
- Offset += TD.getStructLayout(STy)->MemberOffsets[FieldNo];
- CurTy = STy->getContainedType(FieldNo);
}
+#endif
// Add in the offset calculated...
Value.setOffset(Value.getOffset()+Offset);
} else if (F->getName() == "realloc") {
DSNodeHandle RetNH = getValueDest(*CS.getInstruction());
RetNH.mergeWith(getValueDest(**CS.arg_begin()));
- DSNode *N = RetNH.getNode();
- if (N) N->setHeapNodeMarker()->setModifiedMarker()->setReadMarker();
+ if (DSNode *N = RetNH.getNode())
+ N->setHeapNodeMarker()->setModifiedMarker()->setReadMarker();
+ return;
+ } else if (F->getName() == "memset") {
+ // Merge the first argument with the return value, and mark the memory
+ // modified.
+ DSNodeHandle RetNH = getValueDest(*CS.getInstruction());
+ RetNH.mergeWith(getValueDest(**CS.arg_begin()));
+ if (DSNode *N = RetNH.getNode())
+ N->setModifiedMarker();
+ return;
+ } else if (F->getName() == "memmove") {
+ // Merge the first & second arguments with the result, and mark the
+ // memory read and modified.
+ DSNodeHandle RetNH = getValueDest(*CS.getInstruction());
+ RetNH.mergeWith(getValueDest(**CS.arg_begin()));
+ RetNH.mergeWith(getValueDest(**(CS.arg_begin()+1)));
+ if (DSNode *N = RetNH.getNode())
+ N->setModifiedMarker()->setReadMarker();
+ return;
+ } else if (F->getName() == "bzero") {
+ // Mark the memory modified.
+ DSNodeHandle H = getValueDest(**CS.arg_begin());
+ if (DSNode *N = H.getNode())
+ N->setModifiedMarker();
return;
}
NH.addEdgeTo(getValueDest(*C));
return;
}
-
+
+ const TargetData &TD = NH.getNode()->getTargetData();
+
if (ConstantArray *CA = dyn_cast<ConstantArray>(C)) {
for (unsigned i = 0, e = CA->getNumOperands(); i != e; ++i)
// We don't currently do any indexing for arrays...
bool LocalDataStructures::run(Module &M) {
- GlobalsGraph = new DSGraph();
+ GlobalsGraph = new DSGraph(getAnalysis<TargetData>());
+
+ const TargetData &TD = getAnalysis<TargetData>();
// Calculate all of the graphs...
for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
if (!I->isExternal())
- DSInfo.insert(std::make_pair(I, new DSGraph(*I, GlobalsGraph)));
+ DSInfo.insert(std::make_pair(I, new DSGraph(TD, *I, GlobalsGraph)));
GraphBuilder GGB(*GlobalsGraph);
delete GlobalsGraph;
GlobalsGraph = 0;
}
+