//===- Andersens.cpp - Andersen's Interprocedural Alias Analysis ----------===//
-//
+//
// 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.
-//
+//
//===----------------------------------------------------------------------===//
//
// This file defines a very simple implementation of Andersen's interprocedural
//
// Future Improvements:
// This implementation of Andersen's algorithm is extremely slow. To make it
-// scale reasonably well, the inclusion constraints could be sorted (easy),
-// offline variable substitution would be a huge win (straight-forward), and
+// scale reasonably well, the inclusion constraints could be sorted (easy),
+// offline variable substitution would be a huge win (straight-forward), and
// online cycle elimination (trickier) might help as well.
//
//===----------------------------------------------------------------------===//
std::map<Value*, unsigned> ValueNodes;
/// ObjectNodes - This map contains entries for each memory object in the
- /// program: globals, alloca's and mallocs.
+ /// program: globals, alloca's and mallocs.
std::map<Value*, unsigned> ObjectNodes;
/// ReturnNodes - This map contains an entry for each function in the
Constraint(ConstraintType Ty, Node *D, Node *S)
: Type(Ty), Dest(D), Src(S) {}
};
-
+
/// Constraints - This vector contains a list of all of the constraints
/// identified by the program.
std::vector<Constraint> Constraints;
NullPtr = 1,
NullObject = 2,
};
-
+
public:
bool runOnModule(Module &M) {
InitializeAliasAnalysis(this);
ReturnNodes.clear();
VarargNodes.clear();
EscapingInternalFunctions.clear();
- std::vector<Constraint>().swap(Constraints);
+ std::vector<Constraint>().swap(Constraints);
return false;
}
//------------------------------------------------
// Implement the AliasAnalysis API
- //
+ //
AliasResult alias(const Value *V1, unsigned V1Size,
const Value *V2, unsigned V2Size);
ModRefResult getModRefInfo(CallSite CS, Value *P, unsigned Size);
}
return &GraphNodes[I->second];
}
-
+
/// getObject - Return the node corresponding to the memory object for the
/// specified global or allocation instruction.
Node *getObject(Value *V) {
void visitCastInst(CastInst &CI);
void visitSetCondInst(SetCondInst &SCI) {} // NOOP!
void visitSelectInst(SelectInst &SI);
- void visitVANext(VANextInst &I);
void visitVAArg(VAArgInst &I);
void visitInstruction(Instruction &I);
};
Node *N1 = getNode(P);
bool PointsToUniversalSet = false;
- for (Node::iterator NI = N1->begin(), E = N1->end(); NI != E; ++NI) {
- Node *PN = *NI;
- if (PN->begin() == PN->end())
- continue; // P doesn't point to anything.
- // Get the first pointee.
- Node *FirstPointee = *PN->begin();
- if (FirstPointee == &GraphNodes[UniversalSet]) {
- PointsToUniversalSet = true;
- break;
- }
- }
+ if (N1->begin() == N1->end())
+ return NoModRef; // P doesn't point to anything.
- if (!PointsToUniversalSet)
+ // Get the first pointee.
+ Node *FirstPointee = *N1->begin();
+ if (FirstPointee != &GraphNodes[UniversalSet])
return NoModRef; // P doesn't point to the universal set.
}
}
}
}
-
+
AliasAnalysis::getMustAliases(P, RetVals);
}
if (C->getType()->isFirstClassType()) {
if (isa<PointerType>(C->getType()))
N->copyFrom(getNodeForConstantPointer(C));
-
+
} else if (C->isNullValue()) {
N->addPointerTo(&GraphNodes[NullObject]);
return;
assert(F->isExternal() && "Not an external function!");
// These functions don't induce any points-to constraints.
- if (F->getName() == "printf" || F->getName() == "fprintf" ||
- F->getName() == "sprintf" ||
- F->getName() == "fgets" || F->getName() == "__assert_fail" ||
- F->getName() == "open" || F->getName() == "fopen" ||
- F->getName() == "fclose" || F->getName() == "fflush" ||
- F->getName() == "rewind" ||
- F->getName() == "atoi" || F->getName() == "atol" ||
- F->getName() == "unlink" ||
- F->getName() == "sscanf" || F->getName() == "fscanf" ||
- F->getName() == "llvm.memset" || F->getName() == "memcmp" ||
- F->getName() == "read" || F->getName() == "write")
+ if (F->getName() == "atoi" || F->getName() == "atof" ||
+ F->getName() == "atol" || F->getName() == "atoll" ||
+ F->getName() == "remove" || F->getName() == "unlink" ||
+ F->getName() == "rename" || F->getName() == "memcmp" ||
+ F->getName() == "llvm.memset" ||
+ F->getName() == "strcmp" || F->getName() == "strncmp" ||
+ F->getName() == "execl" || F->getName() == "execlp" ||
+ F->getName() == "execle" || F->getName() == "execv" ||
+ F->getName() == "execvp" || F->getName() == "chmod" ||
+ F->getName() == "puts" || F->getName() == "write" ||
+ F->getName() == "open" || F->getName() == "create" ||
+ F->getName() == "truncate" || F->getName() == "chdir" ||
+ F->getName() == "mkdir" || F->getName() == "rmdir" ||
+ F->getName() == "read" || F->getName() == "pipe" ||
+ F->getName() == "wait" || F->getName() == "time" ||
+ F->getName() == "stat" || F->getName() == "fstat" ||
+ F->getName() == "lstat" || F->getName() == "strtod" ||
+ F->getName() == "strtof" || F->getName() == "strtold" ||
+ F->getName() == "fopen" || F->getName() == "fdopen" ||
+ F->getName() == "freopen" ||
+ F->getName() == "fflush" || F->getName() == "feof" ||
+ F->getName() == "fileno" || F->getName() == "clearerr" ||
+ F->getName() == "rewind" || F->getName() == "ftell" ||
+ F->getName() == "ferror" || F->getName() == "fgetc" ||
+ F->getName() == "fgetc" || F->getName() == "_IO_getc" ||
+ F->getName() == "fwrite" || F->getName() == "fread" ||
+ F->getName() == "fgets" || F->getName() == "ungetc" ||
+ F->getName() == "fputc" ||
+ F->getName() == "fputs" || F->getName() == "putc" ||
+ F->getName() == "ftell" || F->getName() == "rewind" ||
+ F->getName() == "_IO_putc" || F->getName() == "fseek" ||
+ F->getName() == "fgetpos" || F->getName() == "fsetpos" ||
+ F->getName() == "printf" || F->getName() == "fprintf" ||
+ F->getName() == "sprintf" || F->getName() == "vprintf" ||
+ F->getName() == "vfprintf" || F->getName() == "vsprintf" ||
+ F->getName() == "scanf" || F->getName() == "fscanf" ||
+ F->getName() == "sscanf" || F->getName() == "__assert_fail" ||
+ F->getName() == "modf")
return true;
+
// These functions do induce points-to edges.
if (F->getName() == "llvm.memcpy" || F->getName() == "llvm.memmove" ||
F->getName() == "memmove") {
&GraphNodes[UniversalSet]));
}
}
-
+
for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F) {
// Make the function address point to the function object.
getNodeValue(*F)->addPointerTo(getObject(F)->setValue(F));
getNode(CI.getOperand(0))));
} else {
// P1 = cast int --> <Copy/P1/Univ>
+#if 0
Constraints.push_back(Constraint(Constraint::Copy, getNodeValue(CI),
&GraphNodes[UniversalSet]));
+#else
+ getNodeValue(CI);
+#endif
}
} else if (isa<PointerType>(Op->getType())) {
// int = cast P1 --> <Copy/Univ/P1>
+#if 0
Constraints.push_back(Constraint(Constraint::Copy,
&GraphNodes[UniversalSet],
getNode(CI.getOperand(0))));
+#else
+ getNode(CI.getOperand(0));
+#endif
}
}
}
}
-void Andersens::visitVANext(VANextInst &I) {
- // FIXME: Implement
- assert(0 && "vanext not handled yet!");
-}
void Andersens::visitVAArg(VAArgInst &I) {
assert(0 && "vaarg not handled yet!");
}
&GraphNodes[UniversalSet],
getReturnNode(F)));
}
-
+
Function::arg_iterator AI = F->arg_begin(), AE = F->arg_end();
CallSite::arg_iterator ArgI = CS.arg_begin(), ArgE = CS.arg_end();
for (; AI != AE && ArgI != ArgE; ++AI, ++ArgI)
&GraphNodes[UniversalSet],
getNode(*ArgI)));
}
-
+
// Copy all pointers passed through the varargs section to the varargs node.
if (F->getFunctionType()->isVarArg())
for (; ArgI != ArgE; ++ArgI)