This commit was manufactured by cvs2svn to create tag 'start'.
llvm-svn: 87109
diff --git a/safecode/Makefile b/safecode/Makefile
new file mode 100755
index 0000000..6698a54
--- /dev/null
+++ b/safecode/Makefile
@@ -0,0 +1,7 @@
+LEVEL = .
+DIRS = lib tools
+
+include $(LEVEL)/Makefile.common
+
+test :: all
+ cd test; $(MAKE)
diff --git a/safecode/Makefile.common b/safecode/Makefile.common
new file mode 100755
index 0000000..052feab
--- /dev/null
+++ b/safecode/Makefile.common
@@ -0,0 +1,16 @@
+# should be llvm source
+LLVM_SRC_DIR = /home/vadve/dhurjati/llvmnew/llvm
+
+# project directory
+PROJ_DIR = /home/vadve/$(USER)/parse
+
+#llvm lib
+LLVM_LIB_DIR = /localhome/$(USER)/llvmnew/llvm/
+
+#proj compile
+PROJ_COMPILE := 1
+
+TOPLEVEL := $(LEVEL)
+LEVEL = $(LLVM_SRC_DIR)
+include $(LEVEL)/Makefile.common
+
diff --git a/safecode/README b/safecode/README
new file mode 100755
index 0000000..2b2fa73
--- /dev/null
+++ b/safecode/README
@@ -0,0 +1 @@
+Need to change a few definitions in Makefile to use the Makefile
diff --git a/safecode/include/ArrayBoundsCheck.h b/safecode/include/ArrayBoundsCheck.h
new file mode 100755
index 0000000..619810c
--- /dev/null
+++ b/safecode/include/ArrayBoundsCheck.h
@@ -0,0 +1,2 @@
+Pass *createABCPreProcessPass();
+Pass *createArrayBoundsCheckPass();
diff --git a/safecode/include/SafeDynMemAlloc.h b/safecode/include/SafeDynMemAlloc.h
new file mode 100755
index 0000000..0d6a357
--- /dev/null
+++ b/safecode/include/SafeDynMemAlloc.h
@@ -0,0 +1,15 @@
+//===- llvm/Transforms/IPO/EmbeC/EmbeC.h - CZero passes -*- C++ -*---------=//
+//
+// This file defines a set of utilities for EmbeC checks on pointers and
+// dynamic memory
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_EMBEC_H
+#define LLVM_EMBEC_H
+
+#include "llvm/Pass.h"
+
+Pass* createEmbeCFreeRemovalPass();
+
+#endif
diff --git a/safecode/include/StackSafety.h b/safecode/include/StackSafety.h
new file mode 100755
index 0000000..585f113
--- /dev/null
+++ b/safecode/include/StackSafety.h
@@ -0,0 +1,14 @@
+//===- StackSafety.h -*- C++ -*---------=//
+//
+// This file defines checks for stack safety
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_STACKSAFETY_H
+#define LLVM_STACKSAFETY_H
+
+#include "llvm/Pass.h"
+
+Pass* createStackSafetyPass();
+
+#endif
diff --git a/safecode/include/UninitPointer.h b/safecode/include/UninitPointer.h
new file mode 100755
index 0000000..7403143
--- /dev/null
+++ b/safecode/include/UninitPointer.h
@@ -0,0 +1,17 @@
+//===- llvm/Transforms/IPO/CZero/CZero.h - CZero passes -*- C++ -*---------=//
+//
+// This file defines a set of utilities for CZero checks on pointers and
+// dynamic memory
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CZERO_H
+#define LLVM_CZERO_H
+
+#include "llvm/Pass.h"
+
+
+FunctionPass* createCZeroUninitPtrPass();
+// FunctionPass* createCZeroLivePtrs();
+
+#endif
diff --git a/safecode/lib/ArrayBoundChecks/ABCPreProcess.cpp b/safecode/lib/ArrayBoundChecks/ABCPreProcess.cpp
new file mode 100755
index 0000000..f4edbb5
--- /dev/null
+++ b/safecode/lib/ArrayBoundChecks/ABCPreProcess.cpp
@@ -0,0 +1,81 @@
+//===- ArrayBoundCheck.cpp - ArrayBounds Checking (Omega)----------------===//
+//
+// requires piNodeinsertion pass before
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Pass.h"
+#include "llvm/Module.h"
+#include "llvm/Function.h"
+#include "llvm/BasicBlock.h"
+#include "AffineExpressions.h"
+#include "llvm/Support/InstIterator.h"
+#include "llvm/Instruction.h"
+#include "llvm/Constants.h"
+#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h"
+
+namespace ABC {
+
+ IndVarMap indMap;
+ ExitNodeMap enMap;
+ PostDominanceFrontier * pdf;
+ DominatorSet *ds;
+ PostDominatorSet *pds;
+
+ //This pass is written because the induction var pass doesnt run properly
+ //after the phi nodes are inserted.
+ struct ABCPreProcess : public FunctionPass {
+ private:
+ void print(ostream &out);
+
+ public :
+ const char *getPassName() const { return "Collect Induction Variables"; }
+ virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.addRequired<UnifyFunctionExitNodes>();
+ AU.addRequired<LoopInfo>();
+ AU.addRequired<DominatorSet>();
+ AU.addRequired<PostDominatorSet>();
+ AU.addRequired<PostDominanceFrontier>();
+ }
+ virtual bool runOnFunction(Function &F);
+ };
+
+
+
+
+void ABCPreProcess::print(ostream &out) {
+ out << " Printing phi nodes which are induction variables ... \n";
+ IndVarMap::iterator ivCurrent = indMap.begin(), ivEnd = indMap.end();
+ for (; ivCurrent != ivEnd; ++ivCurrent) {
+ out << ivCurrent->first;
+ }
+ out << " Printing induction variables done ... \n";
+
+}
+
+bool ABCPreProcess::runOnFunction(Function &F) {
+ BasicBlock *bb = getAnalysis<UnifyFunctionExitNodes>().getExitNode();
+ enMap[&F] = bb;
+ LoopInfo &LI1 = getAnalysis<LoopInfo>();
+ LoopInfo *LI = & LI1;
+
+ pdf = &getAnalysis<PostDominanceFrontier>();
+ ds = &getAnalysis<DominatorSet>();
+ pds = &getAnalysis<PostDominatorSet>();
+ // std::cerr << "calculated pdf for " << F.getName() << "\n";
+ for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {
+ if (PHINode *phi = dyn_cast<PHINode>(*I)) {
+ InductionVariable* iv = new InductionVariable(phi,LI);
+ indMap[phi] = iv;
+ }
+ }
+ // print(std::cerr);
+ return false;
+}
+
+ RegisterOpt<ABCPreProcess> Y("abcpre",
+ "Array Bounds Checking preprocess pass");
+
+}
+
+Pass *createABCPreProcessPass() { return new ABC::ABCPreProcess(); }
diff --git a/safecode/lib/ArrayBoundChecks/AffineExpressions.cpp b/safecode/lib/ArrayBoundChecks/AffineExpressions.cpp
new file mode 100755
index 0000000..83bb594
--- /dev/null
+++ b/safecode/lib/ArrayBoundChecks/AffineExpressions.cpp
@@ -0,0 +1,171 @@
+//===- Expressions.cpp - Expression Analysis Utilities ----------------------=//
+//
+// This file defines a package of expression analysis utilties:
+//
+//
+//===----------------------------------------------------------------------===//
+
+#include "AffineExpressions.h"
+#include "llvm/SlotCalculator.h"
+#include "llvm/DerivedTypes.h"
+#include "Support/StringExtras.h"
+#include "llvm/ConstantHandling.h"
+#include "llvm/Function.h"
+#include "llvm/BasicBlock.h"
+#include "llvm/InstrTypes.h"
+#include "llvm/iTerminators.h"
+#include "llvm/iMemory.h"
+#include "llvm/iOther.h"
+#include "llvm/iPHINode.h"
+#include "llvm/BasicBlock.h"
+#include <iostream>
+#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/InductionVariable.h"
+
+
+
+LinearExpr::LinearExpr(const Value *Val, SlotCalculator &Tab) {
+ if (Val) {
+ vList = new VarList();
+ cMap = new CoefficientMap();
+ vsMap = new ValStringMap();
+ if (const ConstantSInt *CPI = dyn_cast<ConstantSInt>(Val)) {
+ offSet = CPI->getValue();
+ exprTy = Linear;
+ return;
+ } else if (const ConstantUInt *CPI = dyn_cast<ConstantUInt>(Val)) {
+ offSet = CPI->getValue();
+ exprTy = Linear;
+ return;
+ }
+ offSet = 0;
+ vList->push_back(Val);
+ string tempstr;
+ if (Val->hasName()) {
+ tempstr = makeNameProper(Val->getName());
+ } else {
+ int Slot = Tab.getValSlot(Val); // slot number
+ if (Slot >= 0) {
+ tempstr = "l_" + itostr(Slot) + "_" + utostr(Val->getType()->getUniqueID());
+ } else {
+ exprTy = Unknown;
+ tempstr = "unknown";
+ return;
+ }
+ }
+ (*vsMap)[Val] = tempstr;
+ (*cMap)[Val] = 1;
+ }
+ else exprTy = Unknown;
+}
+
+
+void
+LinearExpr::negate() {
+ mulByConstant(-1);
+}
+
+
+void
+LinearExpr::print(ostream &out) {
+
+ if (exprTy != Unknown) {
+ VarListIt vlj = vList->begin();
+ out << offSet;
+ for (; vlj != vList->end(); ++vlj)
+ out << " + " << (*cMap)[*vlj] << " * " << (*vsMap)[*vlj];
+ } else out << "Unknown ";
+}
+
+void
+LinearExpr::addLinearExpr(LinearExpr *E) {
+ if (E->getExprType() == Unknown) {
+ exprTy = Unknown;
+ return;
+ }
+ offSet = E->getOffSet() + offSet;
+ VarList* vl = E->getVarList();
+ CoefficientMap* cm = E->getCMap();
+ ValStringMap* vsm = E->getVSMap();
+
+ VarListIt vli = vl->begin();
+ bool matched;
+ for (; vli != vl->end(); ++vli) {
+ matched = false;
+ VarListIt vlj = vList->begin();
+ for (; vlj != vList->end(); ++vlj) {
+ if (*vli == *vlj) {
+ //matched the vars .. now add the coefficients.
+ (*cMap)[*vli] = (*cMap)[*vli] + (*cm)[*vlj];
+ matched = true;
+ break;
+ }
+ }
+ if (!matched) {
+ //didnt match any var....
+ vList->push_back(*vli);
+ (*cMap)[*vli] = (*cm)[*vli];
+ (*vsMap)[*vli] = (*vsm)[*vli];
+ }
+ }
+}
+
+LinearExpr *
+LinearExpr::mulLinearExpr(LinearExpr *E) {
+ if ((exprTy == Unknown) || (E->getExprType() == Unknown)) {
+ exprTy = Unknown;
+ return this;
+ }
+ VarList* vl = E->getVarList();
+ if ((vl->size() != 0) && (vList->size() != 0)) {
+ exprTy = Unknown;
+ return this;
+ }
+ if (vl->size() == 0) {
+ //The one coming in is a constant
+ mulByConstant(E->getOffSet());
+ return this;
+ } else {
+ E->mulByConstant(offSet);
+ return E;
+ }
+}
+
+void
+LinearExpr::mulByConstant(int E) {
+ offSet = offSet * E;
+ VarListIt vlj = vList->begin();
+ for (; vlj != vList->end(); ++vlj) {
+ (*cMap)[*vlj] = (*cMap)[*vlj] * E;
+ }
+}
+
+void
+Constraint::print(ostream &out) {
+ out << var;
+ out << rel;
+ le->print(out);
+}
+
+
+void
+ABCExprTree::print(ostream &out) {
+ if (constraint != 0) {
+ // out << "printing the constraint \n";
+ constraint->print(out);
+ }
+ else {
+ if (logOp == "||")
+ out << "((";
+ left->print(out);
+ if (logOp == "||")
+ out << ") ";
+ out << "\n" << logOp;
+ if (logOp == "||")
+ out << "(";
+ right->print(out);
+ if (logOp == "||")
+ out << "))";
+ }
+}
+
diff --git a/safecode/lib/ArrayBoundChecks/AffineExpressions.h b/safecode/lib/ArrayBoundChecks/AffineExpressions.h
new file mode 100755
index 0000000..6f4846c
--- /dev/null
+++ b/safecode/lib/ArrayBoundChecks/AffineExpressions.h
@@ -0,0 +1,228 @@
+//===- llvm/ArrayBoundChecks/AffineExpressions.h - Expression Analysis Utils ---*- C++ -*--=//
+//
+// This file defines a package of expression analysis utilties:
+//
+
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_C_EXPRESSIONS_H
+#define LLVM_C_EXPRESSIONS_H
+
+#include <assert.h>
+#include <map>
+#include <list>
+#include <string>
+#include "llvm/Instruction.h"
+#include "llvm/iMemory.h"
+#include "llvm/InstrTypes.h"
+#include "llvm/iTerminators.h"
+#include "llvm/iOther.h"
+#include "llvm/iPHINode.h"
+#include "llvm/iOperators.h"
+#include "llvm/Constants.h"
+#include "llvm/Analysis/PostDominators.h"
+#include "Support/StringExtras.h"
+#include "llvm/SlotCalculator.h"
+#include "llvm/DerivedTypes.h"
+#include "llvm/Analysis/InductionVariable.h"
+
+using namespace std;
+
+class Value;
+class BasicBlock;
+class Function;
+
+namespace cfg { class LoopInfo; }
+
+typedef std::map<const PHINode *,InductionVariable*> IndVarMap;
+typedef std::map<const Function *,BasicBlock *> ExitNodeMap;
+typedef std::map<const Function *, PostDominanceFrontier *> PostDominanceFrontierMap;
+
+typedef std::map<const Value*,int> CoefficientMap;
+typedef std::map<const Value*,string> ValStringMap;
+typedef std::list<const Value*> VarList;
+typedef std::list<const Value*>::const_iterator VarListIt;
+typedef std::list<const CallInst*> CallInstList;
+typedef std::list<const CallInst*>::const_iterator CallInstListIt;
+typedef std::list<const Instruction*> MemAccessInstListType;
+typedef std::list<const Instruction*>::const_iterator MemAccessInstListIt;
+
+// LinearExpr - Represent an expression of the form CONST*VAR1+CONST*VAR2+ .....
+// or simpler.
+
+
+class LinearExpr {
+
+ int offSet;
+ VarList* vList;
+ CoefficientMap* cMap;
+ ValStringMap* vsMap;
+public:
+enum ExpressionType {
+ Linear, // Expr is linear
+ Unknown
+ } exprTy;
+ inline int getOffSet() { return offSet; };
+ inline void setOffSet(int offset) { offSet = offset; };
+ inline ExpressionType getExprType() { return exprTy; };
+ inline VarList* getVarList() { return vList; };
+ inline CoefficientMap* getCMap() { return cMap; };
+ inline ValStringMap* getVSMap() { return vsMap; };
+
+ LinearExpr(const Value *Val,SlotCalculator &Tab); // Create a linear expression
+ void negate();
+ void addLinearExpr(LinearExpr *);
+ LinearExpr * mulLinearExpr(LinearExpr *);
+ void mulByConstant(int);
+ void print(ostream &out);
+};
+
+class Constraint {
+ string var;
+ LinearExpr *le;
+ string rel; // can be < , >, <=, >= for now
+public :
+ Constraint(string v, LinearExpr *l, string r) {
+ assert(l != 0 && "the rhs for this constraint is null");
+ var = v;
+ le = l;
+ rel = r;
+ }
+ void print(ostream &out);
+};
+
+
+
+//This holds a set of ABCExprs
+class ABCExprTree {
+ Constraint *constraint;
+ ABCExprTree *right;
+ ABCExprTree *left;
+ string logOp; // can be && or || or
+ public:
+ ABCExprTree(Constraint *c) {
+ constraint = c;
+ left = 0;
+ right = 0;
+ logOp = "&&";
+ };
+ ABCExprTree(ABCExprTree *l, ABCExprTree *r, string op) {
+ constraint = 0;
+ left = l;
+ right = r;
+ logOp = op;
+ }
+ void print(ostream &out);
+};
+
+typedef std::map<const Value *, ABCExprTree *> InstConstraintMapType;
+
+
+
+//This holds the local information of a function
+class FuncLocalInfo {
+ //Local cache for constraints
+ InstConstraintMapType FuncLocalConstraints;
+
+ //Storing all constraints which need proving
+ InstConstraintMapType FuncSafetyConstraints;
+
+ //All array accesses in a function
+ MemAccessInstListType maiList;
+ //This stores the Or of the arguments at
+ //various call sites, so that can be computed only once for
+ //different array accesses.
+ ABCExprTree *argConstraints;
+
+ bool dependsOnArg;
+public :
+ FuncLocalInfo() {
+ dependsOnArg = false;
+ argConstraints = 0;
+ }
+
+ inline void setdependsOnArg() {
+ dependsOnArg = true;
+ }
+
+ inline bool isDependentOnArg() {
+ return dependsOnArg;
+ }
+
+ inline void addMemAccessInst(Instruction *MAI) {
+ maiList.push_back(MAI);
+ }
+
+ inline void addLocalConstraint(const Value *v, ABCExprTree *aet) {
+ FuncLocalConstraints[v] = aet;
+ }
+ inline bool inLocalConstraints(const Value *v) {
+ return (FuncLocalConstraints.count(v) > 0);
+ }
+ inline ABCExprTree * getLocalConstraint(const Value *v) {
+ if (FuncLocalConstraints.count(v)) return FuncLocalConstraints[v];
+ else return 0;
+ }
+ inline void addSafetyConstraint(const Value *v, ABCExprTree *aet) {
+ FuncSafetyConstraints[v] = aet;
+ }
+ inline ABCExprTree* getSafetyConstraint(const Value *v) {
+ return (FuncSafetyConstraints[v]);
+ }
+ inline MemAccessInstListType getMemAccessInstList() {
+ return maiList;
+ }
+
+ inline void addArgumentConstraints(ABCExprTree *aet) {
+ argConstraints = aet;
+ }
+ inline ABCExprTree * getArgumentConstraints() {
+ return argConstraints;
+ }
+};
+
+// We dont want identifier names with ., space, - in them.
+// So we replace them with _
+static string makeNameProper(string x) {
+ string tmp;
+ int len = 0;
+ for (string::iterator sI = x.begin(), sEnd = x.end(); sI != sEnd; sI++) {
+ if (len > 18) return tmp; //have to do something more meaningful
+ len++;
+ switch (*sI) {
+ case '.': tmp += "d_"; len++;break;
+ case ' ': tmp += "s_"; len++;break;
+ case '-': tmp += "D_"; len++;break;
+ case '_': tmp += "l_"; len++;break;
+ default: tmp += *sI;
+ }
+ }
+ if (tmp == "in") return "in__1";
+ return tmp;
+ };
+
+
+static string getValueNames( Value *V, SlotCalculator *Table) {
+ if ( Constant *CPI = dyn_cast<Constant>(V)) {
+ if ( ConstantSInt *CPI = dyn_cast<ConstantSInt>(V)) {
+ return itostr(CPI->getValue());
+ } else if ( ConstantUInt *CPI = dyn_cast<ConstantUInt>(V)) {
+ return utostr(CPI->getValue());
+ }
+ }
+ if (V->hasName()) {
+ return makeNameProper(V->getName());
+ }
+ else {
+ int Slot = Table->getValSlot(V);
+ // assert(Slot >= 0 && "Invalid value!");
+ if (Slot >= 0) {
+ return "l_" + itostr(Slot) + "_" + utostr(V->getType()->getUniqueID());
+ } else return "Unknown";
+ }
+};
+
+
+
+#endif
diff --git a/safecode/lib/ArrayBoundChecks/ArrayBoundCheck.cpp b/safecode/lib/ArrayBoundChecks/ArrayBoundCheck.cpp
new file mode 100755
index 0000000..435c693
--- /dev/null
+++ b/safecode/lib/ArrayBoundChecks/ArrayBoundCheck.cpp
@@ -0,0 +1,1030 @@
+//===- ArrayBoundCheck.cpp - ArrayBounds Checking (Omega)----------------===//
+//
+// requires piNodeinsertion pass before
+// Now we use the control dependence
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Pass.h"
+#include "llvm/Module.h"
+#include "llvm/Function.h"
+#include "llvm/BasicBlock.h"
+#include "AffineExpressions.h"
+#include "llvm/Support/InstIterator.h"
+#include "llvm/Instruction.h"
+#include "llvm/Constants.h"
+#include "llvm/Analysis/InductionVariable.h"
+#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h"
+#include <fstream>
+
+#define REGION_INIT "RInit"
+#define REGION_MALLOC "RMalloc"
+#define REGION_FREE "RFree"
+
+namespace ABC{
+ static std::ofstream out("omega.ip");
+
+ //these are filled from preprocess pass, since they require fn passes
+ //FIXME replace these by annotations later.
+ extern IndVarMap indMap;
+ extern ExitNodeMap enMap;
+ extern PostDominanceFrontier* pdf;
+ extern DominatorSet* ds;
+ extern PostDominatorSet* pds;
+
+ static unsigned count = 0;
+ //Interprocedural ArrayBoundsCheck pass
+ struct ArrayBoundsCheck : public Pass {
+ public :
+ const char *getPassName() const { return "Array Bounds Check"; }
+ virtual bool run(Module &M);
+ private :
+ typedef std::map<const Function *,FuncLocalInfo*> InfoMap;
+ typedef std::map<Function*, int> FuncIntMap;
+
+ //This is required for getting the names/unique identifiers for variables.
+ SlotCalculator *Table;
+
+ //for storing local information about a function
+ InfoMap fMap;
+
+ //Known Func Database
+ std::set<string> KnownFuncDB;
+
+ //for storing info about the functions which are already proven safe
+ FuncIntMap provenSafe;
+
+ //for storing what control dependent blocks are already dealt with for the current
+ //array access
+ std::set<BasicBlock *> DoneList;
+
+ //Initializes the KnownFuncDB
+ void initialize();
+
+ void outputDeclsForOmega(Module &M);
+
+ //Interface for collecting constraints for different array access
+ // in a function
+ void collectSafetyConstraints(Function &F);
+
+ //This function collects from the branch which controls the current block
+ //the Successor tells the path
+ void addBranchConstraints(BranchInst *BI, BasicBlock *Successor, ABCExprTree **rootp);
+ //This method adds constraints for known trusted functions
+ void addConstraintsForKnownFunctions(CallInst *CI, ABCExprTree **rootp);
+
+
+ //Interface for getting constraints for a particular value
+ void getConstraintsInternal( Value *v, ABCExprTree **rootp);
+ void getConstraints( Value *v, ABCExprTree **rootp);
+
+ //adds all the conditions on which the currentblock is control dependent on.
+ void addControlDependentConditions(BasicBlock *currentBlock, ABCExprTree **rootp);
+
+ //Gives the return value constraints interms of its arguments
+ void getReturnValueConstraints( const CallInst *CI,ABCExprTree **rootp);
+
+ //Checks if the function is safe (produces output for omega consumption)
+ void checkSafety(Function &F, ostream &out);
+
+ //Get the constraints on the arguments
+ //This goes and looks at all call sites and ors the corresponding
+ //constraints
+ ABCExprTree* getArgumentConstraints(Function &F);
+
+ //for simplifying the constraints
+ LinearExpr* SimplifyExpression( Value *Expr, ABCExprTree **rootp);
+
+ string getValueName( Value *V);
+ void generateArrayTypeConstraintsGlobal(string var, const ArrayType *T, ABCExprTree **rootp, unsigned int numElem);
+ void generateArrayTypeConstraints(string var, const ArrayType *T, ABCExprTree **rootp);
+ void printarraytype(string var,const ArrayType *T);
+ void printStandardArguments(const Module *M, ostream & out);
+ };
+
+ void ArrayBoundsCheck::initialize() {
+ KnownFuncDB.insert("puts");
+ KnownFuncDB.insert("memcpy"); //need to add the extra checks
+ // KnownFuncDB.insert("fscanf");
+ KnownFuncDB.insert("strcpy"); //need to add the extra checks
+ KnownFuncDB.insert("strlen");
+ KnownFuncDB.insert("strcmp");
+ KnownFuncDB.insert("strtol");
+ KnownFuncDB.insert("fopen");
+ KnownFuncDB.insert("fwrite");
+ KnownFuncDB.insert("fgetc");
+ KnownFuncDB.insert("getc");
+ KnownFuncDB.insert("read");
+ KnownFuncDB.insert("fread");
+ KnownFuncDB.insert("feof");
+ KnownFuncDB.insert("fputc");
+ KnownFuncDB.insert("qsort"); //need to add the extra checks
+ }
+
+ void ArrayBoundsCheck::outputDeclsForOmega(Module& M) {
+ for (Module::iterator FI = M.begin(), FE = M.end(); FI != FE; ++FI) {
+ Function *F = FI;
+ out << "symbolic Unknown;\n";
+ out << "symbolic argc;\n";
+ out << "symbolic argv;\n";
+ if (!(F->isExternal())) {
+ out << "symbolic " << getValueName(F) <<"; \n";
+ for (Function::ArgumentListType::iterator aI = F->getArgumentList().begin(),
+ aE = F->getArgumentList().end(); aI != aE; ++aI) {
+ out << "symbolic ";
+ out << getValueName((aI));
+ out << ";\n";
+ }
+ }
+ for (Module::giterator gI = M.gbegin(), gE = M.gend(); gI != gE; ++gI) {
+ out << "symbolic ";
+ out << getValueName((gI));
+ out << ";\n";
+ if (const ArrayType *AT = dyn_cast<ArrayType>(gI->getType()->getElementType())) {
+ printarraytype(getValueName(gI), AT);
+ }
+ }
+
+ for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
+ if ((*I)->getType() != Type::VoidTy) {
+ out << "symbolic ";
+ out << getValueName(*I);
+ out << ";\n";
+ if (AllocationInst *AI = dyn_cast<AllocationInst>(*I)) {
+ //FIXME this should be really alloca (for local variables)
+ //This can not be malloc, if array bounds check is run just after
+ //bytecode is generated. But if other passes introduce mallocInsts
+ //we should take care of them just like the allocas
+
+
+ //We have to see the dimension of the array that this alloca is
+ //pointing to
+ //If the allocation is done by constant, then its a constant array
+ // else its a normal alloca which we already have taken care of
+ if (const ArrayType *AT = dyn_cast<ArrayType>(AI->getType()->getElementType())) {
+ printarraytype(getValueName(*I), AT);
+ }
+ } //Note that RMalloc unlike alloca cannot take an array type constant
+ //Array type constant is only taken by alloca for the local variables
+ }
+ }
+ }
+
+
+
+ string ArrayBoundsCheck::getValueName( Value *V) {
+ return getValueNames(V, Table);
+ }
+
+ void ArrayBoundsCheck::printarraytype(string var,const ArrayType *T) {
+ string var1 = var + "_i";
+ out << "symbolic " << var1 << ";\n";
+ if (const ArrayType *AT = dyn_cast<ArrayType>(T->getElementType())) {
+ printarraytype(var1,AT);
+ }
+ }
+
+ //This is an auxillary function used by getConstraints
+ //gets the constraints on the return value interms of its arguments
+ // and ands it with the existing rootp!
+ void ArrayBoundsCheck::getReturnValueConstraints(const CallInst *CI,ABCExprTree **rootp) {
+ // out << "in return value constraints \n";
+ //and the return
+ if (const Function* pf = dyn_cast<Function>(CI->getOperand(0))) {
+ //we have to get the exit node for pf
+ if (KnownFuncDB.find(CI->getOperand(0)->getName()) != KnownFuncDB.end()) {
+ if (!(pf->isExternal())) {
+ BasicBlock *bb = enMap[pf];
+ getConstraints(bb->getTerminator(),rootp);
+ /*
+ if (bb->getTerminator()->getType()->getPrimitiveID() != Type::VoidTyID) {
+ out << "in return value constraints for" << bb->getTerminator() << "\n";
+ }
+ */
+ }
+ }
+ }
+ }
+
+ void ArrayBoundsCheck::addControlDependentConditions(BasicBlock *currentBlock, ABCExprTree **rootp) {
+ PostDominanceFrontier::const_iterator it = pdf->find(currentBlock);
+ if (it != pdf->end()) {
+ const PostDominanceFrontier::DomSetType &S = it->second;
+ if (S.size() > 0) {
+ PostDominanceFrontier::DomSetType::iterator pCurrent = S.begin(), pEnd = S.end();
+ //check if it is control dependent on only one node.
+ //If it is control dependent on only one node.
+ //If it not, then there must be only one that dominates this node and
+ //the rest should be dominated by this node.
+ //or this must dominate every other node (incase of do while)
+ bool dominated = false;
+ bool rdominated = true; //to check if this dominates every other node
+ for (; pCurrent != pEnd; ++pCurrent) {
+ BasicBlock *debugBlock = *pCurrent;
+ if (*pCurrent == currentBlock) {
+ rdominated = rdominated & true;
+ continue;
+ }
+ if (!dominated) {
+ if (ds->dominates(*pCurrent, currentBlock)) {
+ dominated = true;
+ rdominated = false;
+ continue;
+ }
+ }
+ if (ds->dominates(currentBlock, *pCurrent)) {
+ rdominated = rdominated & true;
+ continue;
+ } else {
+ // out << "In function " << currentBlock->getParent()->getName();
+ // out << "for basic block " << currentBlock->getName();
+ // out << "Something wrong .. non affine or unstructured control flow ??\n";
+ dominated = false;
+ break;
+ }
+ }
+ if ((dominated) || (rdominated)) {
+ //Now we are sure that the control dominance is proper
+ //i.e. it doesn't have unstructured control flow
+
+ PostDominanceFrontier::DomSetType::iterator pdCurrent = S.begin(), pdEnd = S.end();
+ for (; pdCurrent != pdEnd; ++pdCurrent) {
+ BasicBlock *CBB = *pdCurrent;
+ if (DoneList.find(CBB) == DoneList.end()) {
+ TerminatorInst *TI = CBB->getTerminator();
+ if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
+ for (unsigned index = 0; index < BI->getNumSuccessors(); ++index) {
+ BasicBlock * succBlock = BI->getSuccessor(index);
+ if (pds->dominates(currentBlock, succBlock)) {
+ // if (BI->getSuccessor(index) == currentBlock) {
+ //FIXME It need not be Successor, we need to check for post dominance
+
+ DoneList.insert(CBB);
+ addControlDependentConditions(CBB,rootp);
+ addBranchConstraints(BI, BI->getSuccessor(index), rootp);
+ break;
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+
+ //adds constraints for known functions
+ void ArrayBoundsCheck::addConstraintsForKnownFunctions(CallInst *CI, ABCExprTree **rootp) {
+ string funcName = CI->getOperand(0)->getName();
+ if (funcName == "memcpy") {
+ string var = getValueName(CI->getOperand(1));
+ LinearExpr *l1 = new LinearExpr(CI->getOperand(2),*Table);
+ Constraint *c1 = new Constraint(var,l1,">=");
+ *rootp = new ABCExprTree(*rootp,new ABCExprTree(c1),"||");
+ getConstraints(CI->getOperand(1), rootp);
+ getConstraints(CI->getOperand(2), rootp);
+ } else if (funcName == "strlen") {
+ string var = getValueName(CI);
+ const Type* csiType = Type::getPrimitiveType(Type::UIntTyID);
+ const ConstantSInt * signedzero = ConstantSInt::get(csiType,0);
+
+ Constraint *c = new Constraint(var, new LinearExpr(signedzero, *Table),">=");
+ *rootp = new ABCExprTree(*rootp,new ABCExprTree(c),"&&");
+
+
+ string var1 = var +" + 1";
+
+ LinearExpr *l1 = new LinearExpr(CI->getOperand(1),*Table);
+ Constraint *c1 = new Constraint(var1,l1,"=");
+ *rootp = new ABCExprTree(*rootp,new ABCExprTree(c1),"&&");
+ getConstraints(CI->getOperand(1), rootp);
+ } else if (funcName == "read") {
+ //FIXME we also need to check that the buf size is less than
+ //the bytes reading
+ string var = getValueName(CI);
+ LinearExpr *l1 = new LinearExpr(CI->getOperand(3),*Table);
+ Constraint *c1 = new Constraint(var,l1,"<=");
+ *rootp = new ABCExprTree(*rootp,new ABCExprTree(c1),"&&");
+ getConstraints(CI->getOperand(3), rootp);
+
+ } else if (funcName == "fread") {
+ //FIXME we also need to check that the buf size is less than
+ //the bytes reading
+ string var = getValueName(CI);
+ LinearExpr *l1 = new LinearExpr(CI->getOperand(2),*Table);
+ LinearExpr *l2 = new LinearExpr(CI->getOperand(3),*Table);
+ l2->mulLinearExpr(l1);
+ Constraint *c1 = new Constraint(var,l2,"<=");
+ *rootp = new ABCExprTree(*rootp,new ABCExprTree(c1),"&&");
+ getConstraints(CI->getOperand(3), rootp);
+ getConstraints(CI->getOperand(2), rootp);
+
+ } else {
+ // out << funcName << " is not supported yet \n";
+ }
+ }
+
+
+ void ArrayBoundsCheck::getConstraints(Value *v, ABCExprTree **rootp) {
+ string tempName1 = getValueName(v);
+ LinearExpr *letemp1 = new LinearExpr(v,*Table);
+ Constraint* ctemp1 = new Constraint(tempName1,letemp1,"=");
+ ABCExprTree* abctemp1 = new ABCExprTree(ctemp1);
+ getConstraintsInternal(v,&abctemp1);
+ *rootp = new ABCExprTree(*rootp, abctemp1, "&&");
+ }
+
+ //Get Constraints on a value v, this assumes that the Table is correctly set
+ //for the function that is cal ling this
+ void ArrayBoundsCheck::getConstraintsInternal(Value *v, ABCExprTree **rootp) {
+ string var;
+ LinearExpr *et;
+ if ( Instruction *I = dyn_cast<Instruction>(v)) {
+
+ Function* func = I->getParent()->getParent();
+ BasicBlock * currentBlock = I->getParent();
+
+ // out << "fn & bb " << func->getName() << I->getParent()->getName() << "\n";
+ // out << " getting constraints for the Instruction " << *I;
+
+
+ //Here we need to add the post dominator stuff if necessary
+ addControlDependentConditions(currentBlock, rootp);
+
+ if (!isa<ReturnInst>(I)) {
+ var = getValueName(I);
+ } else {
+ var = getValueName(func);
+ }
+ if (fMap[func]->inLocalConstraints(I)) { //checking the cache
+ if (fMap[func]->getLocalConstraint(I) != 0) {
+ *rootp = new ABCExprTree(*rootp, fMap[func]->getLocalConstraint(I),"&&");
+ }
+ return;
+ }
+ fMap[func]->addLocalConstraint(I,0);
+ if (isa<SwitchInst>(I)) {
+ //TODO later
+ } else if (ReturnInst * ri = dyn_cast<ReturnInst>(I)) {
+ //For getting the constraints on return values
+ LinearExpr *l1 = new LinearExpr(ri->getOperand(0),*Table);
+ Constraint *c1 = new Constraint(var,l1,"=");
+ *rootp = new ABCExprTree(*rootp,new ABCExprTree(c1),"&&");
+ if (ri->getNumOperands() > 0) {
+ getConstraints(ri->getOperand(0), rootp);
+ }
+
+ } else if (PHINode *p = dyn_cast<PHINode>(I)) {
+ //its a normal PhiNode
+ if (indMap.count(p) > 0) {
+ InductionVariable* iv = indMap[p];
+ if (iv->InductionType != InductionVariable::Unknown) {
+ //depending on the sign ,
+ // FIXME : for the following assumptions
+ // sign is assumed positive
+ ABCExprTree *abcetemp;
+ Value *v0 = p->getIncomingValue(0);
+ Value *v1 = p->getIncomingValue(1);
+ if (iv->Start != v0) {
+ std::swap(v0, v1);
+ }
+ LinearExpr *l1 = new LinearExpr(v0,*Table);
+ Constraint *c1 = new Constraint(var,l1,">=");
+ Instruction *prevDef;
+ if ((prevDef = dyn_cast<Instruction>(v0))) {
+ getConstraints(prevDef,rootp);
+ };
+ abcetemp = new ABCExprTree(c1);
+
+ //V1 is coming in from the loop
+ l1 = new LinearExpr(v1,*Table);
+ c1 = new Constraint(var,l1,"<=");
+ if ((prevDef = dyn_cast<Instruction>(v1))) {
+ getConstraints(prevDef,rootp);
+ };
+ abcetemp = new ABCExprTree(abcetemp,new ABCExprTree(c1),"&&"); //
+ *rootp = new ABCExprTree(*rootp,abcetemp,"&&");
+ } else {
+ //Its OKay to conservatively ignore this phi node
+ // out << " In function " << I->getParent()->getParent()->getName() << "\n";
+ // out << " for the instruction " << I << "\n";
+ // out << " \n\n Induction Variable not Found \n\n ";
+ // out << "Array Bounds Check failed ";
+ }
+ } else {
+ // out << " \n\n Induction Variable not Found \n\n ";
+ // out << "Array Bounds Check failed ";
+ }
+ } else if (isa<CallInst>(I)) {
+ CallInst * CI = dyn_cast<CallInst>(I);
+ //First we have to check if it is an RMalloc
+ if (CI->getOperand(0)->getName() == REGION_MALLOC) {
+ //It is an RMalloc, we knoe it has only one argument
+ Constraint *c = new Constraint(var, SimplifyExpression(I->getOperand(1),rootp),"=");
+ *rootp = new ABCExprTree(*rootp,new ABCExprTree(c),"&&");
+ } else {
+ if (KnownFuncDB.find(CI->getOperand(0)->getName()) != KnownFuncDB.end()) {
+ //Its a known and trusted function
+ // we need to add the constraints carefully
+ addConstraintsForKnownFunctions(CI, rootp);
+ } else {
+ //we have to get constraints for arguments.
+ if (fMap.count(func) == 0) {
+ fMap[func] = new FuncLocalInfo();
+ }
+ getReturnValueConstraints(CI, rootp);
+ //getting the constraints on the arguments.
+ if (Function *Fn = dyn_cast<Function>(CI->getOperand(0))) {
+ Function::aiterator formalArgCurrent = Fn->abegin(), formalArgEnd = Fn->aend();
+ for (unsigned i = 1; formalArgCurrent != formalArgEnd; ++formalArgCurrent, ++i) {
+ string varName = getValueName(formalArgCurrent);
+ Value *OperandVal = CI->getOperand(i);
+ LinearExpr *le = new LinearExpr(OperandVal,*Table);
+ Constraint* c1 = new Constraint(varName,le,"=");
+ ABCExprTree *temp = new ABCExprTree(c1);
+ // if (!isa<Constant>(OperandVal)) {
+ getConstraints(OperandVal,&temp);
+ // }
+ *rootp = new ABCExprTree(*rootp, temp, "&&");
+ }
+ }
+ LinearExpr *le1 = new LinearExpr(v,*Table);
+ Constraint *c1 = new Constraint(getValueName(I->getOperand(0)),le1,"=");
+ *rootp = new ABCExprTree(*rootp,new ABCExprTree(c1),"&&");
+ }
+ }
+ } else if (isa<AllocationInst>(I)) {
+ //Note that this is for the local variables which are converted in to
+ //allocas , we take care of the RMallocs in the CallInst case
+
+ AllocationInst *AI = cast<AllocationInst>(I);
+ if (const ArrayType *AT = dyn_cast<ArrayType>(AI->getType()->getElementType())) {
+ //sometime allocas have some array as their allocating constant !!
+ //We then have to generate constraints for all the dimensions
+ const Type* csiType = Type::getPrimitiveType(Type::UIntTyID);
+ const ConstantSInt * signedOne = ConstantSInt::get(csiType,1);
+
+ Constraint *c = new Constraint(var, new LinearExpr(signedOne, *Table),"=");
+ *rootp = new ABCExprTree(*rootp,new ABCExprTree(c),"&&");
+ generateArrayTypeConstraints(var, AT, rootp);
+ } else {
+ //This is the general case, where the allocas are allocated by some
+ //variable
+ Constraint *c = new Constraint(var, SimplifyExpression(I->getOperand(0),rootp),"=");
+ *rootp = new ABCExprTree(*rootp,new ABCExprTree(c),"&&");
+ }
+ } else if (isa<GetElementPtrInst>(I)) {
+
+
+ GetElementPtrInst *GEP = cast<GetElementPtrInst>(I);
+ Value *PointerOperand = I->getOperand(0);
+ if (const PointerType *pType = dyn_cast<PointerType>(PointerOperand->getType()) ){
+ //this is for arrays inside structs
+ if (const StructType *stype = dyn_cast<StructType>(pType->getElementType())) {
+ //getelementptr *key, long 0, ubyte 0, long 18
+ if (GEP->getNumOperands() == 4) {
+ if (const ArrayType *aType = dyn_cast<ArrayType>(stype->getContainedType(0))) {
+ int elSize = aType->getNumElements();
+ if (const ConstantSInt *CSI = dyn_cast<ConstantSInt>(I->getOperand(3))) {
+ elSize = elSize - CSI->getValue();
+ if (elSize == 0) {
+ //Dirty HACK, this doesnt work for more than 2 arrays in a struct!!
+ if (const ArrayType *aType2 = dyn_cast<ArrayType>(stype->getContainedType(1))) {
+ elSize = aType2->getNumElements();
+ }
+ }
+ const Type* csiType = Type::getPrimitiveType(Type::IntTyID);
+ const ConstantSInt * signedOne = ConstantSInt::get(csiType,elSize);
+ Constraint *c = new Constraint(var, new LinearExpr(signedOne, *Table),"=");
+ *rootp = new ABCExprTree(*rootp,new ABCExprTree(c),"&&");
+ }
+ }
+ }
+ }
+ }
+ //dunno if this is a special case or need to be generalized
+ //FIXME for now it is a special case.
+ if (I->getNumOperands() == 2) {
+ getConstraints(PointerOperand,rootp);
+ getConstraints(GEP->getOperand(1),rootp);
+ LinearExpr *L1 = new LinearExpr(GEP->getOperand(1), *Table);
+ LinearExpr *L2 = new LinearExpr(PointerOperand, *Table);
+ L1->negate();
+ L1->addLinearExpr(L2);
+ Constraint *c = new Constraint(var, L1,"=");
+ *rootp = new ABCExprTree(*rootp,new ABCExprTree(c),"&&");
+ }
+ //This is added for the special case found in the embedded bench marks
+ //Normally GetElementPtrInst is taken care by the getSafetyConstraints
+ //But sometimes you get a pointer to an array x = &x[0]
+ //z = getelementptr x 0 0
+ //getlelementptr z is equivalent to getelementptr x !
+ if (I->getNumOperands() == 3) {
+ if (const PointerType *PT = dyn_cast<PointerType>(PointerOperand->getType())) {
+ if (const ArrayType *AT = dyn_cast<ArrayType>(PT->getElementType())) {
+ if (const ConstantSInt *CSI = dyn_cast<ConstantSInt>(I->getOperand(1))) {
+ if (CSI->getValue() == 0) {
+ if (const ConstantSInt *CSI2 = dyn_cast<ConstantSInt>(I->getOperand(2))) {
+ if (CSI2->getValue() == 0) {
+ //Now add the constraint
+
+ const Type* csiType = Type::getPrimitiveType(Type::IntTyID);
+ const ConstantSInt * signedOne = ConstantSInt::get(csiType,AT->getNumElements());
+ Constraint *c = new Constraint(var, new LinearExpr(signedOne, *Table),"=");
+ *rootp = new ABCExprTree(*rootp,new ABCExprTree(c),"&&");
+
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+ } else {
+ Constraint *c = new Constraint(var, SimplifyExpression(I,rootp),"=");
+ *rootp = new ABCExprTree(*rootp,new ABCExprTree(c),"&&");
+ }
+ fMap[func]->addLocalConstraint(I,*rootp); //storing in the cache
+ } else if (GlobalVariable *GV = dyn_cast<GlobalVariable>(v)) {
+ //Its a global variable...
+ //It could be an array
+ var = getValueName(GV);
+ if (const ArrayType *AT = dyn_cast<ArrayType>(GV->getType()->getElementType())) {
+ const Type* csiType = Type::getPrimitiveType(Type::UIntTyID);
+ const ConstantSInt * signedOne = ConstantSInt::get(csiType,1);
+
+ Constraint *c = new Constraint(var, new LinearExpr(signedOne, *Table),"=");
+ *rootp = new ABCExprTree(*rootp,new ABCExprTree(c),"&&");
+ generateArrayTypeConstraintsGlobal(var, AT, rootp, 1);
+ }
+ }
+ }
+
+ void ArrayBoundsCheck::generateArrayTypeConstraintsGlobal(string var, const ArrayType *T, ABCExprTree **rootp, unsigned int numElem) {
+ string var1 = var + "_i";
+ const Type* csiType = Type::getPrimitiveType(Type::IntTyID);
+ if (const ArrayType *AT = dyn_cast<ArrayType>(T->getElementType())) {
+ const ConstantSInt * signedOne = ConstantSInt::get(csiType,1);
+ Constraint *c = new Constraint(var1, new LinearExpr(signedOne, *Table),"=");
+ *rootp = new ABCExprTree(*rootp,new ABCExprTree(c),"&&");
+ generateArrayTypeConstraintsGlobal(var1,AT, rootp, T->getNumElements() * numElem);
+ } else {
+ const ConstantSInt * signedOne = ConstantSInt::get(csiType,numElem * T->getNumElements());
+ Constraint *c = new Constraint(var1, new LinearExpr(signedOne, *Table),"=");
+ *rootp = new ABCExprTree(*rootp,new ABCExprTree(c),"&&");
+ }
+ }
+
+
+ void ArrayBoundsCheck::generateArrayTypeConstraints(string var, const ArrayType *T, ABCExprTree **rootp) {
+ string var1 = var + "_i";
+ const Type* csiType = Type::getPrimitiveType(Type::IntTyID);
+ const ConstantSInt * signedOne = ConstantSInt::get(csiType,T->getNumElements());
+ Constraint *c = new Constraint(var1, new LinearExpr(signedOne, *Table),"=");
+ *rootp = new ABCExprTree(*rootp,new ABCExprTree(c),"&&");
+ if (const ArrayType *AT = dyn_cast<ArrayType>(T->getElementType())) {
+ generateArrayTypeConstraints(var1,AT, rootp);
+ }
+ }
+
+ ABCExprTree *ArrayBoundsCheck::getArgumentConstraints(Function & F) {
+ //First check if it is in cache
+ ABCExprTree *root = fMap[&F]->getArgumentConstraints();
+ if (root) {
+ return root;
+ } else {
+ root = 0;
+ ABCExprTree *rootCallInst;
+ //Its not there in cache, so we compute it
+ DoneList.clear();
+ for (Value::use_iterator I = F.use_begin(), E = F.use_end(); I != E; ++I) {
+ User *U = *I;
+ rootCallInst = 0;
+ if (CallInst *CI = dyn_cast<CallInst>(U)) {
+ //we need to AND the constraints on the arguments
+ Function::aiterator formalArgCurrent = F.abegin(), formalArgEnd = F.aend();
+ for (unsigned i = 1; formalArgCurrent != formalArgEnd; ++formalArgCurrent, ++i) {
+ string varName = getValueName(formalArgCurrent);
+ Value *OperandVal = CI->getOperand(i);
+ LinearExpr *le = new LinearExpr(OperandVal,*Table);
+ Constraint* c1 = new Constraint(varName,le,"=");
+ ABCExprTree *temp = new ABCExprTree(c1);
+ if (!isa<Constant>(OperandVal)) {
+ getConstraints(OperandVal,&temp);
+ }
+ if (!rootCallInst) {
+ rootCallInst = temp;
+ } else {
+ rootCallInst = new ABCExprTree(rootCallInst, temp, "&&");
+ }
+ }
+ if (!root) {
+ root = rootCallInst;
+ } else {
+ root = new ABCExprTree(root, rootCallInst, "||");
+ }
+ }
+ }
+ }
+ fMap[&F]->addArgumentConstraints(root); //store it in cache
+ return root;
+ }
+
+
+ void ArrayBoundsCheck::printStandardArguments(const Module *M, ostream & out) {
+ for (Module::const_iterator fI = M->begin(), fE = M->end(); fI != fE; ++fI) {
+ if (fI->getName() == "main") {
+ Function::const_aiterator formalArgCurrent = fI->abegin(), formalArgEnd = fI->aend();
+ if (formalArgCurrent != formalArgEnd) {
+ //relyingon front end's ability to get two arguments
+ string argcname = formalArgCurrent->getName();
+ ++formalArgCurrent;
+ string argvname = formalArgCurrent->getName();
+ out << " && " << argcname << " = " << argvname ;
+ break;
+ }
+ }
+ }
+ }
+
+
+ //FIXME doesn't handle any kind of recursion
+ void ArrayBoundsCheck::checkSafety(Function &F, ostream &out) {
+ // out << "fn name " << F.getName() << "\n";
+ provenSafe[&F] = 1;
+ //first check if all its parents are safe, i.e. all calling functions are safe
+ for (Value::use_iterator I = F.use_begin(), E = F.use_end(); I != E; ++I) {
+ User *U = *I;
+ if (CallInst *CI = dyn_cast<CallInst>(U)) {
+ Function *parentfunc = CI->getParent()->getParent();
+ // out << " Inside Check Safety Uses paren func " << getValueName(parentfunc) << " func " << getValueName(&F) << endl;
+ if (!(provenSafe.count(parentfunc))) { //may be wa have to change it to indicate the end
+ checkSafety(*parentfunc, out);
+ }
+ }
+ }
+ // we know that all its parents are safe.
+ // out << " Inside Check Safety " << getValueName(&F) << endl;
+ if (fMap[&F] != 0) {
+ MemAccessInstListType MemAccessInstList = fMap[&F]->getMemAccessInstList();
+ MemAccessInstListIt maI = MemAccessInstList.begin(), maE = MemAccessInstList.end();
+ for (; maI != maE; ++maI) {
+ ABCExprTree *root = fMap[&F]->getSafetyConstraint(*maI);
+ // out << " Inside Check Safety getting root for " << getValueName(&F) << endl;
+ ABCExprTree * argConstraints = getArgumentConstraints(F);
+ if (argConstraints) {
+ root = new ABCExprTree(root,argConstraints,"&&");
+ }
+ //omega stuff should go in here.
+ out << " P" <<count << " := {[i] : \n";
+ if (root != 0)root->print(out);
+ const Module *M = (*maI)->getParent()->getParent()->getParent();
+
+ printStandardArguments(M, out);
+
+ out << " && (argv = argc) ";
+ out << "};\n P"<<count++ << ";\n";
+ //gist something to prove safety
+ // out << " Inside Check Safety getting retval constr " << getValueName(&F) << endl;
+ }
+ }
+ }
+
+ bool ArrayBoundsCheck::run(Module &M) {
+ Table = new SlotCalculator(&M, true);
+ initialize();
+ /* printing preliminaries */
+ outputDeclsForOmega(M);
+ // out << "outputting decls for Omega done" <<endl;
+
+
+ // out << " First Collect Safety Constraints ";
+ for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) {
+ Function &F = *I;
+ if (!(F.hasName()) || (KnownFuncDB.find(F.getName()) == KnownFuncDB.end()))
+ collectSafetyConstraints(F);
+ }
+
+ // out << "Output of collect safety constraints \n";
+ for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) {
+ // out << " Function Name "<< getValueName(I) << "\n";
+ if (fMap[I] != 0) {
+ // we dont have info for external functions
+ MemAccessInstListType MemAccessInstList = fMap[I]->getMemAccessInstList();
+ MemAccessInstListIt maI = MemAccessInstList.begin(), maE = MemAccessInstList.end();
+ for (; maI != maE; ++maI) {
+ ABCExprTree *root = fMap[I]->getSafetyConstraint(*maI);
+ // root->print(out);
+ }
+ }
+ out << "\n";
+ }
+
+ // out << " Now checking the constraints \n ";
+ for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I) {
+ if (!(provenSafe.count(I) != 0)) checkSafety(*I, out);
+ }
+ out << " NumAccessses" <<count << " := {[i] : i = " <<count<< " };\n";
+ // out << "done \n" ;
+ return false;
+ }
+
+
+ void ArrayBoundsCheck::collectSafetyConstraints(Function &F) {
+ if (fMap.count(&F) == 0) {
+ fMap[&F] = new FuncLocalInfo();
+ }
+
+ for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) {
+ Instruction *iLocal = *I;
+ if (isa<CastInst>(iLocal)) {
+ //This is an ugly hack for kill code to work
+ if (isa<GetElementPtrInst>(iLocal->getOperand(0))) {
+ iLocal = cast<Instruction>(iLocal->getOperand(0));
+ }
+ }
+ if (isa<GetElementPtrInst>(iLocal)) {
+ GetElementPtrInst *MAI = cast<GetElementPtrInst>(iLocal);
+ if (const PointerType *PT = dyn_cast<PointerType>(MAI->getPointerOperand()->getType())) {
+ if (!isa<StructType>(PT->getElementType())) {
+ User::op_iterator mI = MAI->op_begin(), mE = MAI->op_end();
+ if (mI == mE) {
+ continue;
+ }
+ mI++;
+ ABCExprTree *root;
+ string varName = getValueName(MAI->getPointerOperand());
+ if ((*mI)->getType() == Type::LongTy) {
+ LinearExpr *le = new LinearExpr(*mI,*Table);
+ Constraint* c1 = new Constraint(varName,le,"<="); // length < index
+ ABCExprTree* abctemp1 = new ABCExprTree(c1);
+ Constraint* c2 = new Constraint("0",le,">"); // 0 > index
+ ABCExprTree* abctemp2 = new ABCExprTree(c2);
+ root = new ABCExprTree(abctemp1, abctemp2, "||");
+ }
+ mI++;
+ for (; mI != mE; ++mI) {
+ if ((*mI)->getType() == Type::LongTy) {
+ LinearExpr *le = new LinearExpr(*mI,*Table);
+ varName = varName+"_i" ;
+ Constraint* c1 = new Constraint(varName,le,"<="); // length < index
+ ABCExprTree* abctemp1 = new ABCExprTree(c1);
+ Constraint* c2 = new Constraint("0",le,">"); // 0 > index
+ ABCExprTree* abctemp2 = new ABCExprTree(c2);
+ ABCExprTree*abctempor = new ABCExprTree(abctemp1,abctemp2,"||"); // abctemp1 || abctemp2
+ root = new ABCExprTree(root, abctempor, "||");
+ }
+ }
+ //reinitialize mI , now getting the constraints on the indices
+ //We need to clear DoneList since we are getting constraints for a new access.
+ DoneList.clear();
+ addControlDependentConditions(MAI->getParent(), &root);
+ mI = MAI->idx_begin();
+ for (; mI != mE; ++mI) {
+ if ((*mI)->getType() == Type::LongTy) {
+ getConstraints(*mI,&root);
+ }
+ }
+ getConstraints(MAI->getPointerOperand(),&root);
+ fMap[&F]->addSafetyConstraint(MAI,root);
+ fMap[&F]->addMemAccessInst(MAI);
+ }
+ }
+ }
+ }
+ }
+
+
+ void ArrayBoundsCheck::addBranchConstraints(BranchInst *BI,BasicBlock *Successor, ABCExprTree **rootp) {
+ //this has to be a conditional branch, otherwise we wouldnt have been here
+ assert((BI->isConditional()) && "abcd wrong pi node");
+ if (SetCondInst *SCI = dyn_cast<SetCondInst>(BI->getCondition())) {
+
+ //SCI now has the conditional statement
+ Value *operand0 = SCI->getOperand(0);
+ Value *operand1 = SCI->getOperand(1);
+
+ getConstraints(operand0,rootp);
+ getConstraints(operand1,rootp);
+
+
+ LinearExpr *l1 = new LinearExpr(operand1,*Table);
+
+ string var0 = getValueName(operand0);
+ Constraint *ct;
+
+ switch(SCI->getOpcode()) {
+ case Instruction::SetLE :
+ //there are 2 cases for each opcode!
+ //its the true branch or the false branch
+ if (BI->getSuccessor(0) == Successor) {
+ //true branch
+ ct = new Constraint(var0,l1,"<=");
+ } else {
+ ct = new Constraint(var0,l1,">");
+ }
+ break;
+ case Instruction::SetNE :
+ if (BI->getSuccessor(0) == Successor) {
+ //true branch
+ ct = new Constraint(var0,l1,"!=");
+ } else {
+ ct = new Constraint(var0,l1,"=");
+ }
+ break;
+ case Instruction::SetEQ :
+ if (BI->getSuccessor(0) == Successor) {
+ //true branch
+ ct = new Constraint(var0,l1,"=");
+ } else {
+ //false branch
+ ct = new Constraint(var0,l1,"!=");
+ }
+ break;
+ case Instruction::SetGE :
+ if (BI->getSuccessor(0) == Successor) {
+ //true branch
+ ct = new Constraint(var0,l1,">=");
+ } else {
+ //false branch
+ ct = new Constraint(var0,l1,"<");
+ }
+ break;
+ case Instruction::SetLT :
+ if (BI->getSuccessor(0) == Successor) {
+ //true branch
+ ct = new Constraint(var0,l1,"<");
+ } else {
+ //false branch
+ ct = new Constraint(var0,l1,">=");
+ }
+ break;
+ case Instruction::SetGT :
+ if (BI->getSuccessor(0) == Successor) {
+ //true branch
+ ct = new Constraint(var0,l1,">");
+ } else {
+ //false branch
+ ct = new Constraint(var0,l1,"<=");
+ }
+ break;
+ default :
+ break;
+ }
+ *rootp = new ABCExprTree(*rootp,new ABCExprTree(ct),"&&"); //
+ }
+ }
+
+
+
+ // SimplifyExpression: Analyze an expression inorder to simplify it
+
+
+ LinearExpr* ArrayBoundsCheck::SimplifyExpression( Value *Expr, ABCExprTree **rootp) {
+ assert(Expr != 0 && "Can't classify a null expression!");
+ if (Expr->getType() == Type::FloatTy || Expr->getType() == Type::DoubleTy)
+ return new LinearExpr(Expr, *Table) ; // nothing known return variable itself
+
+ switch (Expr->getValueType()) {
+ case Value::InstructionVal: break; // Instruction... hmmm... investigate.
+ case Value::TypeVal: case Value::BasicBlockVal:
+ case Value::FunctionVal:
+ out << "test\n ";
+ assert(1 && "Unexpected expression type to classify!");
+ // out << "Bizarre thing to expr classify: " << Expr << "\n";
+ out << "testing \n ";
+ return 0;
+ case Value::GlobalVariableVal: // Global Variable & Method argument:
+ case Value::ArgumentVal: // nothing known, return variable itself
+ return new LinearExpr(Expr, *Table);
+ case Value::ConstantVal: // Constant value, just return constant
+ Constant *CPV = cast<Constant>(Expr);
+ if (CPV->getType()->isIntegral()) { // It's an integral constant!
+ if (ConstantArray *CA = dyn_cast<ConstantArray>(CPV)) {
+ const std::vector<Use> &Values = CA->getValues();
+ ConstantInt *CPI = cast<ConstantInt>(Values[1]);
+ return new LinearExpr(CPI, *Table);
+ } else {
+ ConstantInt *CPI = cast<ConstantInt>(Expr);
+ return new LinearExpr(CPI, *Table);
+ }
+ }
+ return new LinearExpr(Expr, *Table); //nothing known, just return itself
+ }
+
+ Instruction *I = cast<Instruction>(Expr);
+ const Type *Ty = I->getType();
+
+ switch (I->getOpcode()) { // Handle each instruction type seperately
+ case Instruction::Add: {
+ LinearExpr* Left = (SimplifyExpression(I->getOperand(0), rootp));
+ if (Left == 0) {
+ Left = new LinearExpr(I->getOperand(0), *Table);
+ }
+ LinearExpr* Right = (SimplifyExpression(I->getOperand(1), rootp));
+ if (Right == 0) {
+ Right = new LinearExpr(I->getOperand(1), *Table);
+ }
+ Left->addLinearExpr(Right);
+ return Left;
+ }
+ case Instruction::Sub: {
+ LinearExpr* Left = (SimplifyExpression(I->getOperand(0), rootp));
+ if (Left == 0) {
+ Left = new LinearExpr(I->getOperand(0), *Table);
+ }
+ LinearExpr* Right = (SimplifyExpression(I->getOperand(1), rootp));
+ if (Right == 0) {
+ Right = new LinearExpr(I->getOperand(1), *Table);
+ }
+ Right->negate();
+ Left->addLinearExpr(Right);
+ return Left;
+ }
+ case Instruction::SetLE :
+ case Instruction::SetNE :
+ case Instruction::SetEQ :
+ case Instruction::SetGE :
+ case Instruction::SetLT :
+ case Instruction::SetGT : {
+ LinearExpr* L = new LinearExpr(I->getOperand(1),*Table);
+ return L;
+ };
+ case Instruction::Mul :
+
+ LinearExpr* Left = (SimplifyExpression(I->getOperand(0),rootp));
+ if (Left == 0) {
+ Left = new LinearExpr(I->getOperand(0), *Table);
+ }
+ LinearExpr* Right = (SimplifyExpression(I->getOperand(1),rootp));
+ if (Right == 0) {
+ Right = new LinearExpr(I->getOperand(1), *Table);
+ }
+ return Left->mulLinearExpr(Right);
+ } // end switch
+ if (isa<CastInst>(I)) {
+ // out << "dealing with cast instruction ";
+ //FIXME .. this should be for all types not just sbyte
+ const Type *opType = I->getOperand(0)->getType();
+ if ((opType->isPrimitiveType()) && ((opType->getPrimitiveID() == Type::SByteTyID) || (opType->getPrimitiveID() == Type::UByteTyID))) {
+ string number = "255";
+ string number2 = "0";
+ string var = getValueName(I);
+ LinearExpr *l1 = new LinearExpr(I,*Table);
+ Constraint *c1 = new Constraint(number,l1,">=");
+ Constraint *c2 = new Constraint(number2,l1,"<=");
+ *rootp = new ABCExprTree(*rootp,new ABCExprTree(c1),"&&");
+ *rootp = new ABCExprTree(*rootp,new ABCExprTree(c2),"&&");
+ Constraint *c = new Constraint(var, SimplifyExpression(I->getOperand(0),rootp),"=");
+ *rootp = new ABCExprTree(*rootp,new ABCExprTree(c),"&&");
+ return l1;
+ } else {
+ //special case for casts to beginning of structs
+ // the case is (sbyte*) (Struct with the first element arrauy)
+ //If it is a cast from struct to something else * ...
+ if (const PointerType *pType = dyn_cast<PointerType>(I->getType())){
+ const Type *eltype = pType->getElementType();
+ if (eltype->isPrimitiveType() && (eltype->getPrimitiveID() == Type::SByteTyID)) {
+ if (const PointerType *opPType = dyn_cast<PointerType>(opType)){
+ const Type *opEltype = opPType->getElementType();
+ if (const StructType *stype = dyn_cast<StructType>(opEltype)) {
+ if (const ArrayType *aType = dyn_cast<ArrayType>(stype->getContainedType(0))) {
+ if (aType->getElementType()->isPrimitiveType()) {
+ int elSize = aType->getNumElements();
+ switch (aType->getElementType()->getPrimitiveID()) {
+ case Type::ShortTyID :
+ case Type::UShortTyID : elSize *= 2; break;
+ case Type::IntTyID :
+ case Type::UIntTyID : elSize *= 4; break;
+ case Type::LongTyID :
+ case Type::ULongTyID : elSize *= 8; break;
+ default : break;
+ }
+ string varName = getValueName(I);
+ const Type* csiType = Type::getPrimitiveType(Type::IntTyID);
+ const ConstantSInt * signedOne = ConstantSInt::get(csiType,elSize);
+ LinearExpr *l1 = new LinearExpr(signedOne, *Table);
+ return l1;
+ // Constraint *c = new Constraint(varName, new LinearExpr(signedOne, *Table),"=");
+ // *rootp = new ABCExprTree(*rootp,new ABCExprTree(c),"&&");
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+ return SimplifyExpression(I->getOperand(0),rootp);
+ } else {
+ getConstraints(I,rootp);
+ LinearExpr* ret = new LinearExpr(I,*Table);
+ return ret;
+ }
+ // Otherwise, I don't know anything about this value!
+ return 0;
+ }
+ RegisterOpt<ArrayBoundsCheck> X("abc",
+ "Array Bounds Checking pass");
+}
+
+Pass *createArrayBoundsCheckPass() { return new ABC::ArrayBoundsCheck(); }
diff --git a/safecode/lib/ArrayBoundChecks/Makefile b/safecode/lib/ArrayBoundChecks/Makefile
new file mode 100755
index 0000000..6096358
--- /dev/null
+++ b/safecode/lib/ArrayBoundChecks/Makefile
@@ -0,0 +1,9 @@
+
+LEVEL = ../../
+
+LIBRARYNAME = arrayboundcheck
+
+SHARED_LIBRARY = 1
+
+include $(LEVEL)/Makefile.common
+
diff --git a/safecode/lib/Makefile b/safecode/lib/Makefile
new file mode 100755
index 0000000..f9dcaef
--- /dev/null
+++ b/safecode/lib/Makefile
@@ -0,0 +1,6 @@
+LEVEL = ..
+
+PARALLEL_DIRS = ArrayBoundChecks PointerChecks
+
+include $(LEVEL)/Makefile.common
+
diff --git a/safecode/lib/PointerChecks/CZero.cpp b/safecode/lib/PointerChecks/CZero.cpp
new file mode 100755
index 0000000..13735d5
--- /dev/null
+++ b/safecode/lib/PointerChecks/CZero.cpp
@@ -0,0 +1,465 @@
+//===-- CZero.cpp - CZero security checks ----------------===//
+//
+// This transformation ensures that the code emitted (if there are no warnings)
+// poses no security threat to the target system.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/IPO.h"
+#include "CZeroInfo.h"
+#include "llvm/Module.h"
+#include "llvm/Argument.h"
+#include "llvm/Constants.h"
+#include "llvm/iTerminators.h"
+#include "llvm/DerivedTypes.h"
+#include "Support/DepthFirstIterator.h"
+#include "llvm/Function.h"
+#include "llvm/Support/CFG.h"
+
+
+
+//===----------------------------------------------------------------------===//
+// CZeroInfo Implementation
+//===----------------------------------------------------------------------===//
+
+string CZeroInfo::WarningString(enum WarningType WT) {
+ switch (WT) {
+ case NoWarning: return "";
+ case IllegalMemoryLoc: return "Accessing an illegal memory location\n";
+ case UninitPointer: return "Potential use of location pointed to by uninitialized pointer variable\n";
+ default: return "";
+ }
+}
+
+string& CZeroInfo::getWarnings() {
+
+ // Lazy evaluation.
+ // TODO: Introduce an analyzed bool flag so that we
+ // don't end up redo-ing the evaluation when there are no security warnings
+ if (WarningsList != "")
+ return WarningsList;
+
+ // Uninitialized pointers
+ depthFirstGatherer();
+
+ findSpuriousInsts();
+
+ return WarningsList;
+
+}
+
+void CZeroInfo::depthFirstGatherer() {
+ // Adding the pointer values among the arguments to the alias graph
+ // We treat them as pointers to global targets.
+ const FunctionType *FT = cast<FunctionType>(TheFunction.getFunctionType());
+
+ for (Function::const_aiterator I = TheFunction.abegin(),
+ E = TheFunction.aend(); I != E; ++I) {
+ if (I->getType()->getPrimitiveID() == Type::PointerTyID)
+ PointerAliasGraph.addEdge(I, PointsToTarget::GlobalTarget);
+ }
+
+ df_iterator<const Function*> It = df_begin(&TheFunction), End = df_end(&TheFunction);
+ for ( ; It != End; It++) {
+ const BasicBlock *BB = *It;
+
+ // Look for store instructions sequentially in the basic block
+ // updating pointer alias graphs for the other instructions
+ BasicBlock::const_iterator iterBB;
+ for (iterBB = BB->begin(); iterBB != BB->end(); ++iterBB) {
+ const Instruction& I = *iterBB;
+
+ // NOTE!!! Removed the if (I) clause here
+ //
+ if (I.hasName() &&
+ I.getType()->getPrimitiveID() == Type::PointerTyID) {
+ // Each of these cases needs to modify the alias graph appropriately
+ if (isa<AllocaInst>(I)) {
+ PointerAliasGraph.addEdge(&I, &I);
+ }
+ else if (isa<MallocInst>(I)) {
+ // TODO: We'll be making this illegal and only allowing
+ // calls to rmalloc and rfree.
+ PointerAliasGraph.addEdge(&I, &I);
+ }
+ else if (isa<LoadInst>(I)) {
+ PointerAliasGraph.addEdge(&I, PointsToTarget::DummyTarget);
+ }
+ else if (isa<GetElementPtrInst>(I)) {
+ // Check if the operand is a global value, in which case we
+ // generate an alias to a generic global value.
+ if (!isa<ConstantPointerNull>(I.getOperand(0)))
+ if (isa<GlobalValue>(I.getOperand(0)) ||
+ isa<Constant>(I.getOperand(0)))
+ PointerAliasGraph.addEdge(&I, PointsToTarget::GlobalTarget);
+ else
+ PointerAliasGraph.addAlias(&I, I.getOperand(0));
+ else
+ PointerAliasGraph.addEdge(&I, PointsToTarget::DummyTarget);
+ }
+ else if (isa<PHINode>(I)) {
+ PointerAliasGraph.addEdge(&I, &I);
+ }
+ else if (isa<CallInst>(I)) {
+ PointerAliasGraph.addEdge(&I, PointsToTarget::GlobalTarget);
+ }
+ else if (isa<CastInst>(I)) {
+ PointerAliasGraph.addEdge(&I, PointsToTarget::DummyTarget);
+ }
+ }
+ else if (!I.hasName()) {
+ if (isa<StoreInst>(I)) {
+ // We only consider stores of scalar pointers.
+ if (I.getNumOperands() <= 2 ||
+ (I.getNumOperands() == 3 &&
+ I.getOperand(2) != ConstantUInt::get(Type::UIntTy, 0))) {
+ if (!isa<ConstantPointerNull>(I.getOperand(1))) {
+ BBPointerLiveInfo[BB][I.getOperand(1)] = true;
+ df_iterator<const Function*> localIt = df_begin(&TheFunction),
+ localEnd = df_end(&TheFunction);
+ for ( ; localIt != localEnd; ++localIt) {
+ if (DomSet->dominates((BasicBlock *) BB,
+ (BasicBlock *) *localIt))
+ BBPointerLiveInfo[*localIt][I.getOperand(1)] = true;
+ }
+ } else {
+ WarningsList += "Stores to null pointers disallowed in CZero\n";
+ }
+ }
+ }
+ }
+ }
+ }
+}
+
+bool CZeroInfo::checkPredecessors(const BasicBlock *BB, const Value *V,
+ set<const BasicBlock *>& visitedBlocks) {
+ set<const Value *> aliases = PointerAliasGraph.getAliases(V);
+ set<const Value *>::iterator Siter;
+
+ // Check the block BB itself. Necessary when checkPredecessors is called
+ // for a PHINode pointer
+ for (Siter = aliases.begin(); Siter != aliases.end(); ++Siter)
+ if (BBPointerLiveInfo[BB][*Siter])
+ return true;
+
+ pred_const_iterator PI = pred_begin(BB), PEnd = pred_end(BB);
+
+ if (PI != PEnd) {
+ for (; PI != PEnd; ++PI) {
+ if (visitedBlocks.find(*PI) == visitedBlocks.end()) {
+ bool alivehere = false;
+ visitedBlocks.insert(*PI);
+ for (Siter = aliases.begin(); Siter != aliases.end(); ++Siter)
+ if (BBPointerLiveInfo[*PI][*Siter])
+ alivehere = true;
+ if (!alivehere) {
+ if (!checkPredecessors(*PI, V, visitedBlocks))
+ return false;
+ else {
+ // Caching the value for future use.
+ for (Siter = aliases.begin(); Siter != aliases.end(); Siter++)
+ BBPointerLiveInfo[*PI][*Siter] = true;
+ }
+ }
+ }
+ }
+ }
+ else
+ return false;
+ return true;
+}
+
+// if BigSet contains even one of the elements in the smallset, return true
+// else return false
+static bool setContains (set<const Value *> BigSet, set<const Value *> SmallSet) {
+ set<const Value *>::iterator Siter;
+ bool found = false;
+ if (!SmallSet.empty())
+ for (Siter = SmallSet.begin(); Siter != SmallSet.end() && !found; Siter++)
+ if (BigSet.find(*Siter) != BigSet.end())
+ found = true;
+ return found;
+}
+
+// Called on PointerVar only if PointerVar is a scalar, non-heap variable.
+// However the case that PointerVar points to a phi node needs to be handled.
+enum WarningType CZeroInfo::checkIfStored(const BasicBlock *BB,
+ const Value *PointerVar,
+ std::set<const Value *>&
+ LocalStoresSoFar) {
+ if (!isa<ConstantPointerNull>(PointerVar))
+ return NoWarning;
+ // TODO: Optimization if a pointer is defined in the same basic block.
+ set<const Value *> aliases = PointerAliasGraph.getAliases(PointerVar);
+ set<const BasicBlock *> visitedBlocks;
+ visitedBlocks.insert(BB);
+ if (PointerAliasGraph.getPointsToInfo(PointerVar).isPHINode()) {
+ // We have a phi node pointer
+ // Solve separate problems for each of the predecessors
+ if (!setContains(LocalStoresSoFar, aliases)) {
+ // Each of the predecessor branches.
+ bool stored = true;
+ const PHINode *pI = dyn_cast<const PHINode>(PointerAliasGraph.getPointsToInfo(PointerVar).val());
+ // There has to be at least one predecessor
+ for (unsigned int i = 0; i < pI->getNumIncomingValues(); i++) {
+ if (!checkPredecessors(pI->getIncomingBlock(i),
+ pI->getIncomingValue(i),
+ visitedBlocks))
+ stored = false;
+ }
+ if (!stored)
+ return UninitPointer;
+ else {
+ // Cache the value
+ set<const Value *>::iterator Siter;
+ for (Siter = aliases.begin(); Siter != aliases.end(); Siter++)
+ BBPointerLiveInfo[BB][*Siter] = true;
+ }
+ }
+ }
+ else {
+ if (!setContains(LocalStoresSoFar, aliases))
+ if (!checkPredecessors(BB, PointerVar, visitedBlocks))
+ return UninitPointer;
+ else {
+ // Cache the information that PointerVar and its aliases are live here
+ set<const Value *>::iterator Siter;
+ for (Siter = aliases.begin(); Siter != aliases.end(); Siter++)
+ BBPointerLiveInfo[BB][*Siter] = true;
+ }
+ }
+ return NoWarning;
+}
+
+// Called for load and getelementptr instructions
+enum WarningType CZeroInfo::checkInstruction(const BasicBlock *BB,
+ const Instruction *I,
+ std::set<const Value *>&
+ LocalStoresSoFar) {
+ const Value *PointerVar = I->getOperand(0);
+ if (isa<ConstantPointerNull>(I->getOperand(0)))
+ return IllegalMemoryLoc;
+
+ // Check for pointer arithmetic
+ if (!PointerAliasGraph.getPointsToInfo(PointerVar).isArray()) {
+ if (I->getNumOperands() > 1) {
+ // Check that every operand is 0 except for struct accesses.
+ const Type *elemType = I->getType();
+ for(unsigned int i = 1; i < I->getNumOperands(); i++) {
+ if (elemType->getPrimitiveID() == Type::PointerTyID) {
+ if (I->getOperand(i) != ConstantUInt::get(Type::UIntTy, 0))
+ return IllegalMemoryLoc;
+ elemType = cast<const PointerType>(elemType)->getElementType();
+ }
+ else if (elemType->getPrimitiveID() == Type::ArrayTyID) {
+ elemType = cast<const ArrayType>(elemType)->getElementType();
+ }
+ else if (elemType->getPrimitiveID() == Type::StructTyID) {
+ elemType = cast<const StructType>(elemType)->getTypeAtIndex(I->getOperand(i));
+ }
+ }
+ }
+ if (!isa<GlobalValue>(PointerVar) &&
+ !(PointerAliasGraph.getPointsToInfo(PointerVar).isGlobal()) &&
+ !(PointerAliasGraph.getPointsToInfo(PointerVar).isHeap()) &&
+ !(PointerAliasGraph.getPointsToInfo(PointerVar).isStruct()) &&
+ !(PointerAliasGraph.getPointsToInfo(PointerVar).isDummy())) {
+ return checkIfStored(BB, PointerVar, LocalStoresSoFar);
+ }
+ }
+
+ return NoWarning;
+}
+
+bool CZeroInfo::findSpuriousInsts() {
+ bool WarningFlag = false;
+ df_iterator<const Function*> It = df_begin(&TheFunction), End = df_end(&TheFunction);
+ for ( ; It != End; It++) {
+ const BasicBlock *BB = *It;
+ std::set<const Value *> LocalStoresSoFar;
+
+ // Sequentially scan instructions in the block
+ BasicBlock::const_iterator iterBB;
+ for (iterBB = BB->begin(); iterBB != BB->end(); iterBB++) {
+ const Instruction *I = iterBB;
+ enum WarningType WT;
+ if (!I)
+ continue;
+
+ if (isa<CastInst>(I)) {
+ // Disallow cast instructions involving pointers
+ if (I->getType()->getPrimitiveID() == Type::PointerTyID) {
+ WarningsList += I->getName() + ": Casts to pointers disallowed" +
+ "in CZero\n";
+ WarningFlag = true;
+ }
+ else if (I->getOperand(0)->getType()->getPrimitiveID()
+ == Type::PointerTyID) {
+ WarningsList += I->getName() + ":Casts from a pointer disallowed " +
+ "in CZero\n";
+ WarningFlag = true;
+ }
+ }
+ // If this is a store instruction update LocalStoresSoFar
+ else if (isa<StoreInst>(I)) {
+ LocalStoresSoFar.insert(I->getOperand(1));
+
+ // Check that there is no pointer arithmetic here
+ if (!PointerAliasGraph.getPointsToInfo(I->getOperand(1)).isArray()) {
+ const Type *elemType = I->getOperand(1)->getType();
+ for(unsigned int i = 2; i < I->getNumOperands(); i++) {
+ if (elemType->getPrimitiveID() == Type::PointerTyID) {
+ if (I->getOperand(i) != ConstantUInt::get(Type::UIntTy, 0)) {
+ WarningsList += "Stores to pointer variables should not have pointer arithmetic\n";
+ WarningFlag = true;
+ }
+ elemType = cast<const PointerType>(elemType)->getElementType();
+ }
+ else if (elemType->getPrimitiveID() == Type::ArrayTyID) {
+ elemType = cast<const ArrayType>(elemType)->getElementType();
+ }
+ else if (elemType->getPrimitiveID() == Type::StructTyID) {
+ elemType = cast<const StructType>(elemType)->getTypeAtIndex(I->getOperand(i));
+ }
+ }
+ }
+
+ // If a pointer is stored to another pointer, then we check that
+ // the pointer being stored has been stored to. (boy thats twisted!)
+ if (I->getOperand(0)->getType()->getPrimitiveID() ==
+ Type::PointerTyID) {
+ if (!isa<GlobalValue>(I->getOperand(0)) &&
+ !(PointerAliasGraph.getPointsToInfo
+ (I->getOperand(0)).isGlobal()) &&
+ !(PointerAliasGraph.getPointsToInfo
+ (I->getOperand(0)).isHeap()) &&
+ !(PointerAliasGraph.getPointsToInfo
+ (I->getOperand(0)).isStruct()) &&
+ !(PointerAliasGraph.getPointsToInfo
+ (I->getOperand(0)).isDummy()) &&
+ !(PointerAliasGraph.getPointsToInfo
+ (I->getOperand(0)).isArray())) {
+ // TODO: Array
+ WT = checkIfStored(BB, I->getOperand(0), LocalStoresSoFar);
+ if (WT == UninitPointer)
+ WarningsList += "Pointer value being stored potentially uninitialized\n";
+ else
+ WarningsList += WarningString(WT);
+ if (WT != NoWarning)
+ WarningFlag = true;
+ }
+ }
+
+ }
+ else if (isa<LoadInst>(I)) {
+ // Check for globals, heaps and structs... all of which we ignore.
+ WT = checkInstruction(BB, I, LocalStoresSoFar);
+ if (WT == IllegalMemoryLoc) {
+ WarningsList += "Load from illegal memory location\n";
+ WarningFlag = true;
+ }
+ else {
+ WarningsList += WarningString(WT);
+ if (WT != NoWarning)
+ WarningFlag = true;
+ }
+ }
+ else if (isa<GetElementPtrInst>(I)) {
+ WT = checkInstruction(BB, I, LocalStoresSoFar);
+ // don't check for pointer arithmetic any more
+ if (WT == IllegalMemoryLoc) {
+ // WarningsList += "Pointer Arithmetic disallowed\n";
+ // WarningFlag = true;
+ }
+ else {
+ WarningsList += WarningString(WT);
+ if (WT != NoWarning)
+ WarningFlag = true;
+ }
+ }
+ else if (isa<CallInst>(I)) {
+ if (I->getNumOperands() > 1)
+ for (unsigned int i = 1; i < I->getNumOperands(); i++) {
+ if (I->getOperand(i)->getType()->getPrimitiveID() ==
+ Type::PointerTyID) {
+ if (!isa<GlobalValue>(I->getOperand(i)) &&
+ !(PointerAliasGraph.getPointsToInfo
+ (I->getOperand(i)).isGlobal()) &&
+ !(PointerAliasGraph.getPointsToInfo
+ (I->getOperand(i)).isHeap()) &&
+ !(PointerAliasGraph.getPointsToInfo
+ (I->getOperand(i)).isStruct()) &&
+ !(PointerAliasGraph.getPointsToInfo
+ (I->getOperand(i)).isDummy()) &&
+ !(PointerAliasGraph.getPointsToInfo
+ (I->getOperand(i)).isArray())) {
+ WT = checkIfStored(BB, I->getOperand(i), LocalStoresSoFar);
+ if (WT == UninitPointer)
+ WarningsList += "Pointer value argument to function call potentially uninitialized \n";
+ else
+ WarningsList += WarningString(WT);
+ if (WT != NoWarning)
+ WarningFlag = true;
+ }
+ }
+ }
+ }
+ else if (isa<ReturnInst>(I)) {
+ if (I->getNumOperands() > 0)
+ if (I->getOperand(0)->getType()->getPrimitiveID() ==
+ Type::PointerTyID) {
+ if (!isa<GlobalValue>(I->getOperand(0)) &&
+ !(PointerAliasGraph.getPointsToInfo
+ (I->getOperand(0)).isGlobal())) {
+ WarningsList += "Pointer value being returned by function does not point to a global value (only intra-procedural region analysis done)\n";
+ WarningFlag = true;
+ }
+ }
+ }
+ }
+ }
+ return WarningFlag;
+}
+
+namespace {
+
+ // The Pass class we implement
+ struct CZeroPtrChecks : public FunctionPass {
+
+ const char *getPassName() const { return "CZero security pass"; }
+
+ virtual bool runOnFunction (Function &F) {
+ bool Error = false;
+ DominatorSet *DomSet = &getAnalysis<DominatorSet>();
+ CZeroInfo *CZI = new CZeroInfo(F, DomSet);
+ std::cerr << "\nIn function " << F.getName() << "\n";
+ if (CZI->getWarnings() != "") {
+ std::cerr << "Security Warning/s: \n";
+ std::cerr << CZI->getWarnings();
+ Error = true;
+ }
+
+ free(CZI);
+
+ return false;
+
+ }
+
+ virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ // TODO: Check when we generate code.
+ AU.setPreservesAll();
+ AU.addRequired<DominatorSet>();
+ }
+
+ };
+
+ RegisterOpt<CZeroPtrChecks> X("czeroptrchecks", "CZero Pointer Checks");
+
+}
+
+//Externally visible
+
+Pass *createCZeroUninitPtrPass() {
+ return new CZeroPtrChecks();
+}
diff --git a/safecode/lib/PointerChecks/CZeroInfo.h b/safecode/lib/PointerChecks/CZeroInfo.h
new file mode 100755
index 0000000..948b2f8
--- /dev/null
+++ b/safecode/lib/PointerChecks/CZeroInfo.h
@@ -0,0 +1,264 @@
+//===- llvm/Analysis/CZeroInfo.h - CZero info --------*- C++ -*--=//
+//
+// This file checks the LLVM code for any potential security holes. We allow
+// a restricted number of usages in order to preserve memory safety etc.
+//
+//===----------------------------------------------------------------------===//
+
+
+#ifndef LLVM_ANALYSIS_CZEROINFO_H
+#define LLVM_ANALYSIS_CZEROINFO_H
+
+#include "llvm/Type.h"
+#include "llvm/Value.h"
+#include "llvm/iMemory.h"
+#include "llvm/iPHINode.h"
+#include "llvm/iOther.h"
+#include "llvm/BasicBlock.h"
+#include "llvm/Analysis/Dominators.h"
+#include "llvm/SlotCalculator.h"
+#include "llvm/Pass.h"
+#include "llvm/Support/CFG.h"
+#include <algorithm>
+using std::string;
+using std::map;
+using std::vector;
+using std::set;
+
+
+// A dummy node is used when the value pointed to is unknown as yet.
+struct PointsToTarget {
+private:
+ const Value *Val;
+ bool Dummy;
+ bool Global;
+
+ // If the node is a dummy, the following fields don't matter
+ bool Array;
+ bool Struct;
+ bool Heap;
+ int TargetID;
+
+ static int NextTargetID;
+
+public:
+
+ static const int DummyTarget = 1;
+ static const int GlobalTarget = 2;
+
+ bool operator<(const PointsToTarget PTT) const {
+ return (TargetID < PTT.TargetID);
+ }
+
+ PointsToTarget(const Value *V) : Val(V) {
+ TargetID = NextTargetID++;
+ Dummy = false;
+ Global = false;
+ Heap = false;
+ Array = false;
+ Struct = false;
+ if (isa<AllocaInst>(V)) {
+ const AllocaInst *AIV = dyn_cast<AllocaInst>(V);
+ Array = AIV->isArrayAllocation();
+ if (!AIV->isArrayAllocation()) {
+ if (AIV->getAllocatedType()->getPrimitiveID() == Type::StructTyID)
+ Struct = true;
+ }
+ }
+ else if (isa<MallocInst>(V)) {
+ const MallocInst *MIV = dyn_cast<MallocInst>(V);
+ Array = MIV->isArrayAllocation();
+ if (!MIV->isArrayAllocation()) {
+ if (MIV->getAllocatedType()->getPrimitiveID() == Type::StructTyID)
+ Struct = true;
+ }
+ Heap = true;
+ }
+ }
+
+ // Default constructor creates a dummy node.
+ PointsToTarget(int TargetType) {
+ TargetID = NextTargetID++;
+ Val = 0;
+ Dummy = false;
+ Global = false;
+ if (TargetType == DummyTarget) {
+ Dummy = true;
+ }
+ else if (TargetType == GlobalTarget) {
+ Global = true;
+ }
+ Struct = false;
+ Array = false;
+ Heap = false;
+ }
+
+ PointsToTarget() {
+ Val = 0;
+ Dummy = false;
+ Global = false;
+ Struct = false;
+ Array = false;
+ Heap = false;
+ }
+
+ bool isDummy() { return Dummy; }
+
+ bool isGlobal() { return Global; }
+
+ bool isArray() { return Array; }
+
+ bool isStruct() { return Struct; }
+
+ bool isHeap() { return Heap; }
+
+ bool isPHINode() {
+ if (Val)
+ return isa<PHINode>(Val);
+ else
+ return false;
+ }
+
+ const Value* val() { return Val; }
+
+};
+
+int PointsToTarget::NextTargetID = 0;
+
+// The graph is to be recreated for each function. This is done by each
+// CZeroInfo object being associated with a CZeroAliasGraph
+class CZeroAliasGraph {
+ // We ensure that memory locations on stack alone are initialized before
+ // use. A memory location on the stack is identified by the alloca
+ // instruction that created it.
+
+protected:
+ // There are edges from a SSA pointer variable to memory locations
+ // and from SSA pointer variables to phi nodes.
+ // Phi nodes are treated specially in the alias graph.
+ std::map<const Value *, PointsToTarget> pointsTo;
+
+ // Given a memory location, all the SSA pointer vars that point to it.
+ std::map<PointsToTarget, set<const Value *> > pointedBy;
+
+ // NOTE: every update to the graph should update both of these maps
+
+public:
+
+ // Add and edge from V1 to V2.
+ // Situations in which this happens is
+ // V1: SSA pointer variable, V2: alloca
+ // V1: SSA pointer variable, V2: phi node.
+ // Called only once for each SSA pointer value.
+ void addEdge (const Value *V1, const Value *V2) {
+ assert (pointsTo.count(V1) == 0 && "Value should not be inserted in graph yet");
+ PointsToTarget PT(V2);
+ pointsTo[V1] = PT;
+ pointedBy[PT].insert(V1);
+ }
+
+ // Add an edge from an SSA pointer variable to a dummy if we don't really
+ // know what it points to.
+ // Eg. If we load an int* from an int** since we currently don't do any
+ // flow-sensitive pointer tracking.
+ // This or addEdge(V1, V2) called only once for an SSA pointer value
+ void addEdge (const Value *V, int TargetType) {
+ assert (pointsTo.count(V) == 0 && "Value should not be inserted in graph yet");
+ PointsToTarget PT(TargetType);
+ pointsTo[V] = PT;
+ pointedBy[PT].insert(V);
+ }
+
+ PointsToTarget getPointsToInfo(const Value *V) {
+ return pointsTo[V];
+ }
+
+ set<const Value *> getPointedByInfo(PointsToTarget PT) {
+ return pointedBy[PT];
+ }
+
+ // make alias an alias of orig.
+ // If orig does not exist, then both of them need to point to a dummy node.
+ // NOTE: Call only when alias is the lvalue of an instruction.
+ // Call only once for a particular alias
+ void addAlias (const Value *alias, const Value *orig) {
+ assert (pointsTo.count(alias) == 0 && "Value alias not already in graph");
+ assert (pointsTo.count(orig) != 0 && "Value orig not inserted in graph yet");
+ if (pointsTo[orig].val())
+ addEdge(alias, pointsTo[orig].val());
+ else if (pointsTo[orig].isGlobal())
+ addEdge(alias, PointsToTarget::GlobalTarget);
+ else if (pointsTo[orig].isDummy())
+ addEdge(alias, PointsToTarget::DummyTarget);
+ }
+
+ // Returns aliases of the value.
+ // Return value also contains V
+ set<const Value *> getAliases(const Value *V) {
+ return pointedBy[pointsTo[V]];
+ }
+
+};
+
+
+enum WarningType {
+ NoWarning,
+ IllegalMemoryLoc,
+ UninitPointer
+};
+
+typedef std::map<const Value *, bool> LivePointerMap;
+
+// This class contains the information that CZero checks require.
+// This is re-instantiated and initialized for each function.
+class CZeroInfo {
+ // The two phases of our algorithm
+ // Phase 1: Examine all the stores by looking at basic blocks in a depth
+ // first manner and update the PointerLiveInfo map.
+ void depthFirstGatherer();
+ // Phase 2: Iterate through basic blocks depth first and see if the loads
+ // are safe i.e. there is a store of the pointer at every path to the load
+ // in question.
+ bool findSpuriousInsts();
+ bool checkPredecessors(const BasicBlock *BB, const Value *V,
+ set<const BasicBlock *>& vistedBlocks);
+ enum WarningType checkIfStored(const BasicBlock *BB,
+ const Value *V,
+ std::set<const Value *>& LocalStoresSoFar);
+
+ enum WarningType checkInstruction(const BasicBlock *BB,
+ const Instruction *I,
+ std::set<const Value *>& LocalStoresSoFar);
+
+ string WarningString(enum WarningType WT);
+
+protected:
+ const Function& TheFunction;
+
+ // This is the map (BasicBlock1 * Pointer variable) -> BasicBlock2
+ // where BasicBlock2 dominates BasicBlock1 and has a store to the pointer
+ std::map<const BasicBlock *, LivePointerMap> BBPointerLiveInfo;
+
+ // Alias graph to be used in the findSpuriousLoads phase
+ // Created in phase 1.
+ CZeroAliasGraph PointerAliasGraph;
+
+ // Dominator set information
+ DominatorSet *DomSet;
+
+ string WarningsList;
+
+
+public:
+
+ CZeroInfo (Function& F, DominatorSet* DSet) : TheFunction(F), DomSet(DSet) {
+
+ }
+
+ // Public access method to get all the warnings associated with
+ // the particular function.
+ string& getWarnings ();
+};
+
+#endif
+
diff --git a/safecode/lib/PointerChecks/CheckStackPointer.cpp b/safecode/lib/PointerChecks/CheckStackPointer.cpp
new file mode 100755
index 0000000..367df37
--- /dev/null
+++ b/safecode/lib/PointerChecks/CheckStackPointer.cpp
@@ -0,0 +1,92 @@
+//===-- StackSafety.cpp - Analysis for ensuring stack safety ------------//
+// Implementation of StackSafety.h
+//
+
+
+#include "llvm/Module.h"
+#include "llvm/Function.h"
+#include "llvm/Instruction.h"
+#include "llvm/iTerminators.h"
+#include "llvm/BasicBlock.h"
+#include "llvm/Type.h"
+#include "llvm/Pass.h"
+#include "llvm/Analysis/DataStructure.h"
+#include "llvm/Analysis/DSGraph.h"
+#include "llvm/Analysis/DSNode.h"
+#include "llvm/Support/InstIterator.h"
+
+namespace {
+ struct checkStackSafety : public Pass {
+ public :
+ const char *getPassName() const { return "Stack Safety Check";}
+ virtual bool run(Module &M);
+ virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.addRequired<TDDataStructures>();
+ }
+ private :
+ bool checkIfReachesAlloca(DSNode *DSN);
+ };
+ RegisterOpt<checkStackSafety> css("css1",
+ "check stack safety");
+}
+
+
+bool checkStackSafety::checkIfReachesAlloca(DSNode *DSN) {
+ if (DSN->NodeType & DSNode::AllocaNode) {
+ return true;
+ }
+ for (unsigned i = 0, e = DSN->getSize(); i < e; i += DS::PointerSize)
+ if (DSNode *DSNchild = DSN->getLink(i).getNode()) {
+ if (checkIfReachesAlloca(DSNchild)) {
+ return true;
+ }
+ }
+ return false;
+}
+
+bool checkStackSafety::run(Module &M) {
+
+ TDDataStructures *TDDS;
+ TDDS = &getAnalysis<TDDataStructures>();
+
+ for (Module::iterator MI = M.begin(), ME = M.end(); MI != ME; ++MI) {
+ Function &F = *MI;
+
+ if (!F.isExternal()) {
+ DSGraph &TDG = TDDS->getDSGraph(F);
+
+ // check if return value is a pointers
+ if (isa<PointerType>(F.getReturnType())) {
+ //return value type is a pointer
+ for(inst_iterator ii = inst_begin(F), ie = inst_end(&F); ii != ie; ++ii) {
+ if (ReturnInst *RI = dyn_cast<ReturnInst>(*ii)) {
+ DSNode *DSN = TDG.getNodeForValue(RI).getNode();
+ if (checkIfReachesAlloca(DSN)) {
+ std::cerr << "Instruction : \n" << RI << "points to a stack location\n";
+ std::cerr << "In Function " << F.getName() << "\n";
+ return false;
+ }
+ }
+ }
+ }
+ Function::aiterator AI = F.abegin(), AE = F.aend();
+ for (; AI != AE; ++AI) {
+ if (isa<PointerType>(AI->getType())) {
+ DSNode *DSN = TDG.getNodeForValue(AI).getNode();
+ if (checkIfReachesAlloca(DSN)) {
+ std::cerr << "Instruction : \n" << AI << "points to a stack location\n";
+ std::cerr << "In Function " << F.getName() << "\n";
+ return false;
+ }
+ }
+ }
+ }
+ }
+ return true;
+}
+
+
+Pass *createStackSafetyPass() { return new checkStackSafety(); }
+
+
+
diff --git a/safecode/lib/PointerChecks/FreeRemoval.cpp b/safecode/lib/PointerChecks/FreeRemoval.cpp
new file mode 100755
index 0000000..02d8c7c
--- /dev/null
+++ b/safecode/lib/PointerChecks/FreeRemoval.cpp
@@ -0,0 +1,379 @@
+//===-- FreeRemoval.cpp - EmbeC transformation that removes frees ------------//
+// Implementation of FreeRemoval.h : an EmbeC pass
+//
+// Some assumptions:
+// * Correctness of pool allocation
+// * Destroys at end of functions.
+// Pool pointer aliasing assumptions
+// -pool pointer copies via gep's are removed
+// -no phinode takes two pool pointers because then they would be the same pool
+// Result: If we look at pool pointer defs and look for their uses... we check
+// that their only uses are calls to pool_allocs, pool_frees and pool_destroys.
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Module.h"
+#include "llvm/Pass.h"
+#include "llvm/Transforms/IPO.h"
+#include "Support/PostOrderIterator.h"
+#include "llvm/DerivedTypes.h"
+#include "llvm/iOther.h"
+#include "llvm/Support/CFG.h"
+#include "llvm/Analysis/CallGraph.h"
+#include "llvm/Transforms/PoolAllocate.h"
+#include "Support/VectorExtras.h"
+#include <set>
+#include <map>
+#include <string>
+using std::set;
+using std::map;
+
+
+namespace {
+
+ struct EmbeCFreeRemoval : public Pass {
+
+ // The function representing 'poolmakeunfreeable'
+ Function *PoolMakeUnfreeable;
+
+ bool run(Module &M);
+
+ static const std::string PoolI;
+ static const std::string PoolA;
+ static const std::string PoolArr;
+ static const std::string PoolF;
+ static const std::string PoolD;
+
+ void checkPoolSSAVarUses(Function *F, Value *V,
+ map<Value *, set<Instruction *> > &FuncAllocs,
+ map<Value *, set<Instruction *> > &FuncFrees,
+ map<Value *, set<Instruction *> > &FuncDestroy);
+
+ virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ // TODO: Check!
+ AU.setPreservesAll();
+ AU.addRequired<PoolAllocate>();
+ AU.addRequired<CallGraph>();
+ }
+
+ private:
+
+ Module *CurModule;
+
+ bool moduleChanged;
+ bool hasError;
+
+ // The following maps are only for pool pointers that escape a function.
+ // Associates function with set of pools that are freed or alloc'ed using
+ // pool_free or pool_alloc but not destroyed within the function.
+ // These have to be pool pointer arguments to the function
+ map<Function *, set<Value *> > FuncFreedPools;
+ map<Function *, set<Value *> > FuncAllocedPools;
+ map<Function *, set<Value *> > FuncDestroyedPools;
+
+ };
+
+ const std::string EmbeCFreeRemoval::PoolI = "poolinit";
+ const std::string EmbeCFreeRemoval::PoolA = "poolalloc";
+ const std::string EmbeCFreeRemoval::PoolArr = "poolallocarray";
+ const std::string EmbeCFreeRemoval::PoolF = "poolfree";
+ const std::string EmbeCFreeRemoval::PoolD = "pooldestroy";
+
+ RegisterOpt<EmbeCFreeRemoval> Y("EmbeC", "EmbeC pass that removes all frees and issues warnings if behaviour has changed");
+
+}
+
+
+// Check if SSA pool pointer variable V has uses other than alloc, free and
+// destroy
+void EmbeCFreeRemoval::checkPoolSSAVarUses(Function *F, Value *V,
+ map<Value *, set<Instruction *> > &FuncPoolAllocs,
+ map<Value *, set<Instruction *> > &FuncPoolFrees,
+ map<Value *, set<Instruction *> > &FuncPoolDestroys) {
+ if (V->use_begin() != V->use_end()) {
+ for (Value::use_iterator UI = V->use_begin(), UE = V->use_end();
+ UI != UE; ++UI) {
+ // Check that the use is nothing except a call to pool_alloc, pool_free
+ // or pool_destroy
+ if (CallInst *CI = dyn_cast<CallInst>(*UI)) {
+ if (Function *calledF = dyn_cast<Function>(CI->getOperand(0))) {
+ if (!calledF->isExternal()) {
+ // the pool pointer is passed to the called function
+
+ // Find the formal parameter corresponding to the parameter V
+ int operandNo;
+ for (unsigned int i = 1; i < CI->getNumOperands(); i++)
+ if (CI->getOperand(i) == V)
+ operandNo = i;
+
+ Value *formalParam;
+ int opi = 0;
+ for (Function::aiterator I = calledF->abegin(),
+ E = calledF->aend();
+ I != E && opi <= operandNo; ++I, ++opi)
+ if (opi == operandNo)
+ formalParam = I;
+
+ // if the called function has undestroyed frees in pool formalParam
+ if (FuncFreedPools[calledF].find(formalParam) !=
+ FuncFreedPools[calledF].end() &&
+ FuncDestroyedPools[calledF].find(formalParam) ==
+ FuncDestroyedPools[calledF].end()) {
+ FuncPoolFrees[V].insert(cast<Instruction>(*UI));
+ }
+ // if the called function has undestroyed allocs in formalParam
+ if (FuncAllocedPools[calledF].find(formalParam) !=
+ FuncAllocedPools[calledF].end()) {
+ FuncPoolAllocs[V].insert(cast<Instruction>(*UI));
+ }
+
+ // if the called function has a destroy in formalParam
+ if (FuncDestroyedPools[calledF].find(formalParam) !=
+ FuncDestroyedPools[calledF].end()) {
+ FuncPoolDestroys[V].insert(cast<Instruction>(*UI));
+ }
+ } else {
+ // external function
+ if (calledF->getName() == EmbeCFreeRemoval::PoolI) {
+ // Insert call to poolmakeunfreeable after every poolinit since
+ // we do not free memory to the system for safety in all cases.
+ // Also, insert prototype in the module
+
+ // NB: This has to be in sync with the types in PoolAllocate.cpp
+ const Type *VoidPtrTy = PointerType::get(Type::SByteTy);
+ // The type to allocate for a pool descriptor: { sbyte*, uint }
+ const Type *PoolDescType =
+ StructType::get(make_vector<const Type*>(VoidPtrTy,
+ Type::UIntTy, 0));
+ const PointerType *PoolDescPtr = PointerType::get(PoolDescType);
+ std::vector<const Type*> PMUArgs(1, PoolDescPtr);
+ FunctionType *PoolMakeUnfreeableTy =
+ FunctionType::get(Type::VoidTy, PMUArgs, false);
+ PoolMakeUnfreeable = CurModule->getOrInsertFunction("poolmakeunfreeable", PoolMakeUnfreeableTy);
+ new CallInst(PoolMakeUnfreeable, make_vector(V), "",
+ CI->getNext());
+ std::cerr << "here\n";
+ assert(0);
+ moduleChanged = true;
+ } else if (calledF->getName() == EmbeCFreeRemoval::PoolA ||
+ calledF->getName() == EmbeCFreeRemoval::PoolArr) {
+ FuncPoolAllocs[V].insert(cast<Instruction>(*UI));
+ } else if (calledF->getName() == EmbeCFreeRemoval::PoolF) {
+ FuncPoolFrees[V].insert(cast<Instruction>(*UI));
+ } else if (calledF->getName() == EmbeCFreeRemoval::PoolD) {
+ FuncPoolDestroys[V].insert(cast<Instruction>(*UI));
+ } else {
+ hasError = true;
+ std::cerr << "EmbeC: " << F->getName() << ": Unrecognized pool variable use \n";
+ }
+ }
+ } else {
+ // indirect function call
+ hasError = true;
+ std::cerr << "EmbeC: " << F->getName() << ": Unrecognized pool variable use \n";
+ }
+ } else {
+ hasError = true;
+ std::cerr << "EmbeC: " << F->getName() << ": Unrecognized pool variable use \n";
+ }
+ }
+ }
+}
+
+// Returns true if BB1 follows BB2 in some path in F
+static bool followsBlock(BasicBlock *BB1, BasicBlock *BB2, Function *F,
+ set<BasicBlock *> visitedBlocks) {
+ if (succ_begin(BB2) != succ_end(BB2)) {
+ for (BasicBlock::succ_iterator BBSI = succ_begin(BB2), BBSE =
+ succ_end(BB2); BBSI != BBSE; ++BBSI) {
+ if (visitedBlocks.find(*BBSI) == visitedBlocks.end())
+ if (*BBSI == BB1)
+ return true;
+ else {
+ visitedBlocks.insert(*BBSI);
+ if (followsBlock(BB1, *BBSI, F, visitedBlocks))
+ return true;
+ }
+ }
+ }
+ return false;
+}
+
+// Checks if Inst1 follows Inst2 in any path in the function F.
+static bool followsInst(Instruction *Inst1, Instruction *Inst2, Function *F) {
+ if (Inst1->getParent() == Inst2->getParent()) {
+ for (BasicBlock::iterator BBI = Inst2, BBE = Inst2->getParent()->end();
+ BBI != BBE; ++BBI)
+ if (Inst1 == &(*BBI))
+ return true;
+ }
+ set<BasicBlock *> visitedBlocks;
+ return followsBlock(Inst1->getParent(), Inst2->getParent(), F,
+ visitedBlocks);
+}
+
+
+bool EmbeCFreeRemoval::run(Module &M) {
+ CurModule = &M;
+ moduleChanged = false;
+ hasError = false;
+
+ Function *mainF = M.getMainFunction();
+
+ if (!mainF) {
+ hasError = true;
+ std::cerr << "EmbeC: Function main required\n";
+ return false;
+ }
+
+ // Bottom up on the call graph
+ // TODO: Take care of recursion/mutual recursion
+ CallGraph &CG = getAnalysis<CallGraph>();
+ PoolAllocate &PoolInfo = getAnalysis<PoolAllocate>();
+
+
+ for (po_iterator<CallGraph*> CGI = po_begin(&CG),
+ CGE = po_end(&CG); CGI != CGE; ++CGI) {
+
+ Function *F = (*CGI)->getFunction();
+
+ // Ignore nodes representing external functions in the call graph
+ if (!F)
+ continue;
+
+ // All its pool SSA variables including its arguments
+ set<Value *> FuncPoolPtrs;
+
+ // Pool SSA variables that are used in allocs, destroy and free or calls
+ // to functions that escaped allocs, destroys and frees respectively.
+ map<Value *, set<Instruction *> > FuncPoolAllocs, FuncPoolFrees,
+ FuncPoolDestroys;
+
+ // Traverse the function finding poolfrees and calls to functions that
+ // have poolfrees without pooldestroys on all paths in that function.
+
+ if (!F->isExternal()) {
+ // For each pool pointer def check its uses and ensure that there are
+ // no uses other than the pool_alloc, pool_free or pool_destroy calls
+
+
+ PA::FuncInfo* PAFI = 0;
+
+ // Calculating the FuncInfo for F
+ for (Module::iterator ModI = CurModule->begin(), ModE = CurModule->end();
+ ModI != ModE;
+ ++ModI) {
+ PA::FuncInfo* PFI = PoolInfo.getFuncInfo(*ModI);
+ if (PFI) {
+ if (&*ModI == F || (PFI->Clone && PFI->Clone == F)) {
+ PAFI = PFI;
+ break;
+ }
+ }
+ }
+
+
+ // If the function has no pool pointers (args or SSA), ignore the
+ // function.
+ if (!PAFI)
+ continue;
+
+ if (!PAFI->PoolDescriptors.empty()) {
+ for (map<DSNode*, Value*>::iterator PAFII =
+ PAFI->PoolDescriptors.begin(),
+ PAFIE = PAFI->PoolDescriptors.end(); PAFII != PAFIE; ++PAFII) {
+ checkPoolSSAVarUses(F, (*PAFII).second, FuncPoolAllocs,
+ FuncPoolFrees, FuncPoolDestroys);
+ FuncPoolPtrs.insert((*PAFII).second);
+ }
+ }
+ else
+ continue;
+
+ // Do a local analysis on these and update the pool variables that escape
+ // the function (poolfrees without pooldestroys, poolallocs)
+ // For each instruction in the list of free/calls to free, do
+ // the following: go down to the bottom of the function looking for
+ // allocs till you see destroy. If you don't see destroy on some path,
+ // update escape list.
+ // Update escape list with allocs without destroys too for arguments
+ // As well as arguments that are destroyed.
+ // TODO: Modify implementation so you are not checking that there is no
+ // alloc to other pools follows a free in the function, but to see that
+ // there is a destroy on pool between a free and an alloc to another pool
+ // Current Assumption: destroys are at the end of a function.
+ if (!FuncPoolFrees.empty()) {
+ for (map<Value *, set<Instruction *> >::iterator ValueI =
+ FuncPoolFrees.begin(), ValueE = FuncPoolFrees.end();
+ ValueI != ValueE; ++ValueI) {
+ if (!(*ValueI).second.empty()) {
+ for (set<Instruction *>::iterator FreeInstI =
+ (*ValueI).second.begin(),
+ FreeInstE = (*ValueI).second.end();
+ FreeInstI != FreeInstE; ++FreeInstI) {
+ // For each free instruction or call to a function which escapes
+ // a free in pool (*ValueI).first
+ for (set<Value *>::iterator PoolPtrsI = FuncPoolPtrs.begin(),
+ PoolPtrsE = FuncPoolPtrs.end(); PoolPtrsI != PoolPtrsE;
+ ++PoolPtrsI) {
+ // For each pool pointer other than the one in the free
+ // instruction under consideration, check that allocs to it
+ // don't follow the free on any path.
+ if (*PoolPtrsI != (*ValueI).first) {
+ map<Value *, set<Instruction *> >::iterator AllocSet=
+ FuncPoolAllocs.find(*PoolPtrsI);
+ if (AllocSet != FuncPoolAllocs.end())
+ for (set<Instruction *>::iterator AllocInstI =
+ (*AllocSet).second.begin(),
+ AllocInstE = (*AllocSet).second.end();
+ AllocInstI != AllocInstE; ++AllocInstI)
+ if (followsInst(*AllocInstI, *FreeInstI, F)) {
+ hasError = true;
+ std::cerr << "EmbeC: Free instruction could not be "
+ << "removed. Allocs from other pools "
+ << "following free instruction\n";
+ }
+ }
+ }
+ }
+ }
+ }
+
+ }
+
+ // Assumption: if we have pool_destroy on a pool in a function, then it
+ // is on all exit paths of the function
+ // TODO: correct later.
+ // Therefore, all pool ptr arguments that have frees but no destroys
+ // escape the function. Similarly all pool ptr arguments that have
+ // allocs but no destroys escape the function
+
+ for (set<Value *>::iterator PoolPtrsI = FuncPoolPtrs.begin(),
+ PoolPtrsE = FuncPoolPtrs.end(); PoolPtrsI != PoolPtrsE;
+ ++PoolPtrsI) {
+ if (isa<Argument>(*PoolPtrsI)) {
+ // Only for pool pointers that are arguments
+ if (FuncPoolFrees.find(*PoolPtrsI) != FuncPoolFrees.end())
+ FuncFreedPools[F].insert(*PoolPtrsI);
+ if (FuncPoolAllocs.find(*PoolPtrsI) != FuncPoolAllocs.end())
+ FuncAllocedPools[F].insert(*PoolPtrsI);
+ if (FuncPoolDestroys.find(*PoolPtrsI) != FuncPoolDestroys.end()) {
+ FuncDestroyedPools[F].insert(*PoolPtrsI);
+ }
+ }
+ }
+
+ // TODO
+ // For each function, check that the frees in the function are safe i.e.
+ // there are no mallocs between the free and its corresponding
+ // pool_destroy and then remove the pool free call.
+ }
+ }
+
+ return moduleChanged;
+
+}
+
+Pass *createEmbeCFreeRemovalPass() { return new EmbeCFreeRemoval(); }
+
+
+
diff --git a/safecode/lib/PointerChecks/Makefile b/safecode/lib/PointerChecks/Makefile
new file mode 100755
index 0000000..ee41085
--- /dev/null
+++ b/safecode/lib/PointerChecks/Makefile
@@ -0,0 +1,7 @@
+LEVEL = ../../
+LIBRARYNAME = pointerchecks
+
+BUILD_ARCHIVE = 1
+
+include $(LEVEL)/Makefile.common
+
diff --git a/safecode/tools/EmbeC/Makefile b/safecode/tools/EmbeC/Makefile
new file mode 100755
index 0000000..1b905e8
--- /dev/null
+++ b/safecode/tools/EmbeC/Makefile
@@ -0,0 +1,9 @@
+LEVEL = ../..
+TOOLNAME = embec
+LLVMLIBS = bcreader bcwriter instrument \
+ profpaths scalaropts \
+ ipo ipa.a datastructure.a transforms target.a analysis \
+ transformutils vmcore support cwriter
+USEDLIBS = pointerchecks arrayboundcheck
+TOOLLINKOPTS = -ldl
+include $(LEVEL)/Makefile.common
diff --git a/safecode/tools/EmbeC/embec.cpp b/safecode/tools/EmbeC/embec.cpp
new file mode 100755
index 0000000..cca459f
--- /dev/null
+++ b/safecode/tools/EmbeC/embec.cpp
@@ -0,0 +1,80 @@
+//===----------------------------------------------------------------------===//
+// LLVM 'embec' UTILITY : Checks codes for safety as per the EmbeC language
+// rules. Targetted at embedded systems.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Module.h"
+#include "llvm/PassManager.h"
+#include "llvm/Bytecode/Reader.h"
+#include "llvm/Assembly/CWriter.h"
+#include "UninitPointer.h"
+#include "SafeDynMemAlloc.h"
+#include "ArrayBoundsCheck.h"
+#include "StackSafety.h"
+#include "llvm/Transforms/Scalar.h"
+#include "Support/CommandLine.h"
+#include "Support/Signals.h"
+#include <fstream>
+#include <memory>
+using namespace std;
+
+static cl::opt<string>
+InputFilename(cl::Positional, cl::desc("<input bytecode>"), cl::init("-"));
+
+static cl::opt<string>
+OutputFilename("o", cl::desc("Override output filename"),
+ cl::value_desc("filename"));
+
+static cl::opt<bool>
+Force("f", cl::desc("Overwrite output files"));
+
+int main(int argc, char **argv) {
+
+ cl::ParseCommandLineOptions(argc, argv,
+ " llvm .bc -> .bc modular optimizer\n");
+
+ // Load the input module...
+ std::auto_ptr<Module> M(ParseBytecodeFile(InputFilename));
+
+
+ if (M.get() == 0) {
+ cerr << "bytecode didn't read correctly.\n";
+ return 1;
+ }
+
+ // Figure out what stream we are supposed to write to...
+
+ std::ostream *Out = &std::cout; // Default to printing to stdout...
+
+
+ if (OutputFilename != "") {
+ Out = new std::ofstream(OutputFilename.c_str());
+
+
+ if (!Out->good()) {
+ cerr << "Error opening " << OutputFilename << "!\n";
+ return 1;
+ }
+
+ }
+
+
+ //
+ PassManager Passes;
+
+ //Add passes
+ Passes.add(createCZeroUninitPtrPass());
+ Passes.add(createABCPreProcessPass());
+ Passes.add(createArrayBoundsCheckPass());
+ Passes.add(createStackSafetyPass());
+ Passes.add(createEmbeCFreeRemovalPass());
+
+ // Now that we have all of the passes ready, run them.
+ if (Passes.run(*M.get()))
+ cerr << "Program modified.\n";
+ (*Out) << M.get();
+ // WriteToC(M.get(), *Out, false);
+
+ return 0;
+}
diff --git a/safecode/tools/Makefile b/safecode/tools/Makefile
new file mode 100755
index 0000000..4c799f9
--- /dev/null
+++ b/safecode/tools/Makefile
@@ -0,0 +1,5 @@
+LEVEL = ..
+PARALLEL_DIRS = Parse EmbeC
+
+include $(LEVEL)/Makefile.common
+
diff --git a/safecode/tools/Parse/Makefile b/safecode/tools/Parse/Makefile
new file mode 100755
index 0000000..aa12097
--- /dev/null
+++ b/safecode/tools/Parse/Makefile
@@ -0,0 +1,9 @@
+LEVEL = ../..
+TOOLNAME = parse
+LLVMLIBS = bcreader bcwriter instrument profpaths scalaropts \
+ ipo ipa.a datastructure.a transforms target.a analysis \
+ transformutils vmcore support cwriter
+USEDLIBS = arrayboundcheck
+TOOLLINKOPTS = -ldl
+include $(LEVEL)/Makefile.common
+
diff --git a/safecode/tools/Parse/parse.cpp b/safecode/tools/Parse/parse.cpp
new file mode 100755
index 0000000..99708dc
--- /dev/null
+++ b/safecode/tools/Parse/parse.cpp
@@ -0,0 +1,73 @@
+//===----------------------------------------------------------------------===//
+// LLVM 'czero' UTILITY
+//
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Module.h"
+#include "llvm/PassManager.h"
+#include "llvm/Bytecode/Reader.h"
+#include "llvm/Assembly/CWriter.h"
+#include "ArrayBoundsCheck.h"
+#include "llvm/Transforms/Scalar.h"
+#include "Support/CommandLine.h"
+#include "Support/Signals.h"
+#include <fstream>
+#include <memory>
+using namespace std;
+
+static cl::opt<string>
+InputFilename(cl::Positional, cl::desc("<input bytecode>"), cl::init("-"));
+
+static cl::opt<string>
+OutputFilename("o", cl::desc("Override output filename"),
+ cl::value_desc("filename"));
+
+static cl::opt<bool>
+Force("f", cl::desc("Overwrite output files"));
+
+int main(int argc, char **argv) {
+
+ cl::ParseCommandLineOptions(argc, argv,
+ " llvm .bc -> .bc modular optimizer\n");
+
+// Load the input module...
+ std::auto_ptr<Module> M(ParseBytecodeFile(InputFilename));
+
+
+ if (M.get() == 0) {
+ cerr << "bytecode didn't read correctly.\n";
+ return 1;
+ }
+
+ // Figure out what stream we are supposed to write to...
+
+ std::ostream *Out = &std::cout; // Default to printing to stdout...
+
+
+ if (OutputFilename != "") {
+ Out = new std::ofstream(OutputFilename.c_str());
+
+ if (!Out->good()) {
+ cerr << "Error opening " << OutputFilename << "!\n";
+ return 1;
+ }
+
+ }
+
+
+ //
+ PassManager Passes;
+
+ //Add passes
+ Passes.add(createABCPreProcessPass());
+ // Passes.add(createPiNodeInsertionPass());
+ Passes.add(createArrayBoundsCheckPass());
+
+ // Now that we have all of the passes ready, run them.
+ Passes.run(*M.get());
+ (*Out) << M.get();
+ // WriteToC(M.get(), *Out, false);
+
+ return 0;
+}
