//===- ConstraintGeneration.cpp: Interprocedural Constraint Generation --===// // // Now we use the control dependence, post dominance frontier to generate // constraints for //===--------------------------------------------------------------------===// #include #include "dsa/DSGraph.h" #include "utils/fdstream.h" #include "llvm/Pass.h" #include "llvm/Module.h" #include "llvm/BasicBlock.h" #include "llvm/ADT/STLExtras.h" #include "llvm/Support/InstIterator.h" #include "llvm/ADT/StringExtras.h" #include "llvm/Constants.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/ADT/VectorExtras.h" #include "llvm/Support/Debug.h" #include "llvm/Analysis/CallGraph.h" #include "ConstraintGeneration.h" #include #include #include #include using namespace llvm; using namespace ABC; char ConstraintGeneration::ID = 0; //The following are filled from the preprocess pass, since they require //fn passes extern IndVarMap indMap; #if 0 extern DominatorSet::DomSetMapType dsmt; extern PostDominatorSet::DomSetMapType pdsmt; extern PostDominanceFrontier::DomSetMapType pdfmt; #endif static bool dominates(BasicBlock *bb1, BasicBlock *bb2) { DominatorSet::DomSetMapType::const_iterator dsmtI = dsmt.find(bb1); assert((dsmtI != dsmt.end()) && " basic block not found in dominator set"); return (dsmtI->second.count(bb2) != 0); } static bool postDominates(BasicBlock *bb1, BasicBlock *bb2) { PostDominatorSet::DomSetMapType::const_iterator pdsmtI = pdsmt.find(bb1); assert((pdsmtI != pdsmt.end()) && " basic block not found in post dominator set"); return (pdsmtI->second.count(bb2) != 0); } //This will tell us whether the collection of constraints //depends on the incoming args or not //Do we need this to be global? static bool reqArgs = false; //a hack for llvm's malloc instruction which concerts all ints to uints //This is not really necessary, as it is checked in the pool allocation run-time //library static bool fromMalloc = false; //Interprocedural ConstraintGeneration pass RegisterPass cgen1("cgen","Array Bounds Checking pass"); void ConstraintGeneration::initialize(Module &M) { KnownFuncDB.insert("snprintf"); //added the format string & string check KnownFuncDB.insert("strcpy"); //need to add the extra checks KnownFuncDB.insert("memcpy"); //need to add the extra checks KnownFuncDB.insert("llvm.memcpy"); //need to add the extra checks KnownFuncDB.insert("strlen"); //Gives return value constraints KnownFuncDB.insert("read"); // read requires checks and return value constraints KnownFuncDB.insert("fread"); //need to add the extra checks KnownFuncDB.insert("fprintf"); //need to check if it is not format string KnownFuncDB.insert("printf"); //need to check if it is not format string KnownFuncDB.insert("vfprintf"); //need to check if it is not format string KnownFuncDB.insert("syslog"); //need to check if it is not format string KnownFuncDB.insert("memset"); //need to check if we are not setting outside KnownFuncDB.insert("llvm.memset"); //need to check if we are not setting outside KnownFuncDB.insert("gets"); // need to check if the char array is greater than 80 KnownFuncDB.insert("strchr"); //FIXME check has not been added yet KnownFuncDB.insert("sprintf"); //FIXME to add extra checks KnownFuncDB.insert("fscanf"); //Not sure if it requires a check //Not sure if the following require any checks. KnownFuncDB.insert("llvm.va_start"); KnownFuncDB.insert("llvm.va_end"); //The following doesnt require checks KnownFuncDB.insert("random"); KnownFuncDB.insert("rand"); KnownFuncDB.insert("clock"); KnownFuncDB.insert("exp"); KnownFuncDB.insert("fork"); KnownFuncDB.insert("wait"); KnownFuncDB.insert("fflush"); KnownFuncDB.insert("fclose"); KnownFuncDB.insert("alarm"); KnownFuncDB.insert("signal"); KnownFuncDB.insert("setuid"); KnownFuncDB.insert("__errno_location"); KnownFuncDB.insert("log"); KnownFuncDB.insert("srand48"); KnownFuncDB.insert("drand48"); KnownFuncDB.insert("lrand48"); KnownFuncDB.insert("times"); KnownFuncDB.insert("puts"); KnownFuncDB.insert("putchar"); KnownFuncDB.insert("strcmp"); KnownFuncDB.insert("strtol"); KnownFuncDB.insert("fopen"); KnownFuncDB.insert("fwrite"); KnownFuncDB.insert("fgetc"); KnownFuncDB.insert("getc"); KnownFuncDB.insert("open"); KnownFuncDB.insert("feof"); KnownFuncDB.insert("fputc"); KnownFuncDB.insert("atol"); KnownFuncDB.insert("atoi"); KnownFuncDB.insert("atof"); KnownFuncDB.insert("exit"); KnownFuncDB.insert("perror"); KnownFuncDB.insert("sqrt"); KnownFuncDB.insert("floor"); KnownFuncDB.insert("pow"); KnownFuncDB.insert("abort"); KnownFuncDB.insert("srand"); KnownFuncDB.insert("perror"); KnownFuncDB.insert("__isnan"); KnownFuncDB.insert("__main"); KnownFuncDB.insert("ceil"); } string ConstraintGeneration::getValueName(const Value *V) { return Mang->getValueName(V); } ABCExprTree* ConstraintGeneration::getReturnValueConstraints(Function *f) { bool localSave = reqArgs; const Type* csiType = Type::getPrimitiveType(Type::Int32TyID); const ConstantInt * signedzero = ConstantInt::get(csiType,0); string var = "0"; Constraint *c = new Constraint(var, new LinearExpr(signedzero, Mang),"="); ABCExprTree *root = new ABCExprTree(c); //dummy constraint Function::iterator bI = f->begin(), bE = f->end(); for (;bI != bE; ++bI) { BasicBlock *bb = bI; if (ReturnInst *RI = dyn_cast(bb->getTerminator())) getConstraints(RI,&root); } reqArgs = localSave ; //restore to the original return root; } void ConstraintGeneration::addFormalToActual(Function *Fn, CallInst *CI, ABCExprTree **rootp) { LinearExpr *le1 = new LinearExpr(CI,Mang); Constraint *c1 = new Constraint(getValueName(Fn),le1,"="); *rootp = new ABCExprTree(*rootp,new ABCExprTree(c1),"&&"); Function::arg_iterator formalArgCurrent = Fn->arg_begin(), formalArgEnd = Fn->arg_end(); for (unsigned i = 1; formalArgCurrent != formalArgEnd; ++formalArgCurrent, ++i) { string varName = getValueName(formalArgCurrent); Value *OperandVal = CI->getOperand(i); LinearExpr *le = new LinearExpr(OperandVal,Mang); Constraint* c1 = new Constraint(varName,le,"="); ABCExprTree *temp = new ABCExprTree(c1); *rootp = new ABCExprTree(*rootp, temp, "&&"); //and of all arguments } } //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 ConstraintGeneration::getConstraintsAtCallSite(CallInst *CI,ABCExprTree **rootp) { if (Function *pf = dyn_cast(CI->getOperand(0))) { if (pf->isExternal()) { *rootp = new ABCExprTree(*rootp,addConstraintsForKnownFunctions(pf, CI), "&&"); addFormalToActual(pf, CI, rootp); } else { if (buCG->isInSCC(pf)) { std::cerr << "Ignoring return values on function in recursion\n"; return; } *rootp = new ABCExprTree(*rootp,getReturnValueConstraints(pf), "&&"); addFormalToActual(pf, CI, rootp); } //Now get the constraints on the actual arguemnts for the original call site for (unsigned i =1; i < CI->getNumOperands(); ++i) getConstraints(CI->getOperand(i),rootp); } else { //Indirect Calls ABCExprTree *temproot = 0; // Loop over all of the actually called functions... CompleteBUDataStructures::callee_iterator I = cbudsPass->callee_begin(CI), E = cbudsPass->callee_end(CI); //assert((I != E) && "Indirect Call site doesn't have targets ???? "); //Actually thats fine, we ignore the return value constraints ;) for(; I != E; ++I) { CallSite CS = CallSite::get(I->first); if ((I->second->isExternal()) || (KnownFuncDB.find(I->second->getName()) != KnownFuncDB.end()) ) { ABCExprTree * temp = addConstraintsForKnownFunctions(I->second, CI); addFormalToActual(I->second, CI, &temp); if (temproot) { temproot = new ABCExprTree(temproot, temp, "||"); //we need to or them } else { temproot = temp; } } else { if (buCG->isInSCC(I->second)) { std::cerr << "Ignoring return values on function in recursion\n"; return; } ABCExprTree * temp = getReturnValueConstraints(I->second); addFormalToActual(I->second, CI, &temp); if (temproot) { temproot = new ABCExprTree(temproot, temp, "||"); } else { temproot = temp; } } } if (temproot) { *rootp = new ABCExprTree(*rootp, temproot, "&&"); //Now get the constraints on the actual arguemnts for the original call site for (unsigned i =1; i < CI->getNumOperands(); ++i) { getConstraints(CI->getOperand(i),rootp); } } } } void ConstraintGeneration::addControlDependentConditions(BasicBlock *currentBlock, ABCExprTree **rootp) { PostDominanceFrontier::const_iterator it = pdfmt.find(currentBlock); if (it != pdfmt.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) { if (*pCurrent == currentBlock) { rdominated = rdominated & true; continue; } if (!dominated) { if (dominates(*pCurrent, currentBlock)) { dominated = true; rdominated = false; continue; } } if (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(TI)) { for (unsigned index = 0; index < BI->getNumSuccessors(); ++index) { BasicBlock * succBlock = BI->getSuccessor(index); if (postDominates(currentBlock, succBlock)) { DoneList.insert(CBB); addControlDependentConditions(CBB,rootp); addBranchConstraints(BI, BI->getSuccessor(index), rootp); break; } } } } } } } } } //adds constraints for known functions ABCExprTree* ConstraintGeneration::addConstraintsForKnownFunctions(Function *kf, CallInst *CI) { const Type* csiType = Type::getPrimitiveType(Type::Int32TyID); const ConstantInt * signedzero = ConstantInt::get(csiType,0); string var = "0"; Constraint *c = new Constraint(var, new LinearExpr(signedzero, Mang),"="); ABCExprTree *root = new ABCExprTree(c); //dummy constraint ABCExprTree **rootp = &root; string funcName = kf->getName(); if (funcName == "memcpy") { string var = getValueName(CI->getOperand(1)); LinearExpr *l1 = new LinearExpr(CI->getOperand(2),Mang); 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 == "llvm.memcpy") { string var = getValueName(CI->getOperand(1)); LinearExpr *l1 = new LinearExpr(CI->getOperand(2),Mang); 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::Int32TyID); const ConstantInt * signedzero = ConstantInt::get(csiType,0); Constraint *c = new Constraint(var, new LinearExpr(signedzero, Mang),">="); *rootp = new ABCExprTree(*rootp,new ABCExprTree(c),"&&"); LinearExpr *l1 = new LinearExpr(CI->getOperand(1),Mang); Constraint *c1 = new Constraint(var,l1,"<"); *rootp = new ABCExprTree(*rootp,new ABCExprTree(c1),"&&"); getConstraints(CI->getOperand(1), rootp); } else if (funcName == "read") { string var = getValueName(CI); LinearExpr *l1 = new LinearExpr(CI->getOperand(3),Mang); Constraint *c1 = new Constraint(var,l1,"<="); *rootp = new ABCExprTree(*rootp,new ABCExprTree(c1),"&&"); getConstraints(CI->getOperand(3), rootp); } else if (funcName == "fread") { string var = getValueName(CI); LinearExpr *l1 = new LinearExpr(CI->getOperand(2),Mang); LinearExpr *l2 = new LinearExpr(CI->getOperand(3),Mang); 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"; // Ignoring some functions is okay as long as they are not part of the //one of the multiple indirect calls assert((CI->getOperand(0) == kf) && "Need to handle this properly \n"); } return root; } void ConstraintGeneration::getConstraints(Value *v, ABCExprTree **rootp) { string tempName1 = getValueName(v); LinearExpr *letemp1 = new LinearExpr(v,Mang); 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 ConstraintGeneration::getConstraintsInternal(Value *v, ABCExprTree **rootp) { string var; if ( Instruction *I = dyn_cast(v)) { Function* func = I->getParent()->getParent(); BasicBlock * currentBlock = I->getParent(); //Here we need to add the post dominator stuff if necessary addControlDependentConditions(currentBlock, rootp); if (!isa(I)) { var = getValueName(I); } else { var = getValueName(func); } if (fMap.count(func)) { if (fMap[func]->inLocalConstraints(I)) { //checking the cache if (fMap[func]->getLocalConstraint(I) != 0) { *rootp = new ABCExprTree(*rootp, fMap[func]->getLocalConstraint(I),"&&"); } return; } } else { fMap[func] = new FuncLocalInfo(); } fMap[func]->addLocalConstraint(I,0); if (isa(I)) { //TODO later } else if (ReturnInst * ri = dyn_cast(I)) { if (ri->getNumOperands() > 0) { //For getting the constraints on return values LinearExpr *l1 = new LinearExpr(ri->getOperand(0),Mang); Constraint *c1 = new Constraint(var,l1,"="); *rootp = new ABCExprTree(*rootp,new ABCExprTree(c1),"&&"); getConstraints(ri->getOperand(0), rootp); } } else if (PHINode *p = dyn_cast(I)) { //its a normal PhiNode if (indMap.count(p) > 0) { //We know that this is the canonical induction variable //First get the upper bound Value *UBound = indMap[p]; LinearExpr *l1 = new LinearExpr(UBound, Mang); Constraint *c1 = new Constraint(var, l1, "<"); *rootp = new ABCExprTree(*rootp,new ABCExprTree(c1),"&&"); const Type* csiType = Type::getPrimitiveType(Type::Int32TyID); const ConstantInt * signedzero = ConstantInt::get(csiType,0); LinearExpr *l2 = new LinearExpr(signedzero, Mang); Constraint *c2 = new Constraint(var, l2, ">="); *rootp = new ABCExprTree(*rootp,new ABCExprTree(c2),"&&"); getConstraints(UBound, rootp); } } else if (isa(I)) { CallInst * CI = dyn_cast(I); //First we have to check if it is an RMalloc if (CI->getOperand(0)->getName() == "RMalloc") { //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 (fMap.count(func) == 0) { fMap[func] = new FuncLocalInfo(); } //This also get constraints for arguments of CI getConstraintsAtCallSite(CI, rootp); } } else if (isa(I)) { //Note that this is for the local variables which are converted in to //allocas, mallocs , we take care of the RMallocs (CASES work)in the CallInst case AllocationInst *AI = cast(I); if (const ArrayType *AT = dyn_cast(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::Int32TyID); const ConstantInt * signedOne = ConstantInt::get(csiType,1); Constraint *c = new Constraint(var, new LinearExpr(signedOne, Mang),"="); *rootp = new ABCExprTree(*rootp,new ABCExprTree(c),"&&"); generateArrayTypeConstraints(var, AT, rootp); } else { //This is the general case, where the allocas/mallocs are allocated by some //variable //Ugly hack because of the llvm front end's cast of //argument of malloc to uint fromMalloc = true; Value *sizeVal = I->getOperand(0) ; // if (CastInst *csI = dyn_cast(I->getOperand(0))) { // const Type *toType = csI->getType(); // const Type *fromType = csI->getOperand(0)->getType(); // if ((toType->isPrimitiveType()) && (toType->getPrimitiveID() == Type::Int32TyID)) { // sizeVal = csI->getOperand(0); // } // } Constraint *c = new Constraint(var, SimplifyExpression(sizeVal,rootp),"="); fromMalloc = false; *rootp = new ABCExprTree(*rootp,new ABCExprTree(c),"&&"); } } else if (isa(I)) { GetElementPtrInst *GEP = cast(I); Value *PointerOperand = I->getOperand(0); if (const PointerType *pType = dyn_cast(PointerOperand->getType()) ){ //this is for arrays inside structs if (const StructType *stype = dyn_cast(pType->getElementType())) { //getelementptr *key, long 0, ubyte 0, long 18 if (GEP->getNumOperands() == 4) { if (const ArrayType *aType = dyn_cast(stype->getContainedType(0))) { int elSize = aType->getNumElements(); if (const ConstantInt *CSI = dyn_cast(I->getOperand(3))) { elSize = elSize - CSI->getSExtValue(); if (elSize == 0) { //Dirty HACK, this doesnt work for more than 2 arrays in a struct!! if (const ArrayType *aType2 = dyn_cast(stype->getContainedType(1))) { elSize = aType2->getNumElements(); } } const Type* csiType = Type::getPrimitiveType(Type::Int32TyID); const ConstantInt * signedOne = ConstantInt::get(csiType,elSize); Constraint *c = new Constraint(var, new LinearExpr(signedOne, Mang),"="); *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), Mang); LinearExpr *L2 = new LinearExpr(PointerOperand, Mang); 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(PointerOperand->getType())) { if (const ArrayType *AT = dyn_cast(PT->getElementType())) { if (const ConstantInt *CSI = dyn_cast(I->getOperand(1))) { if (CSI->getSExtValue() == 0) { if (const ConstantInt *CSI2 = dyn_cast(I->getOperand(2))) { if (CSI2->getSExtValue() == 0) { //Now add the constraint const Type* csiType = Type::getPrimitiveType(Type::Int32TyID); const ConstantInt * signedOne = ConstantInt::get(csiType,AT->getNumElements()); Constraint *c = new Constraint(var, new LinearExpr(signedOne, Mang),"="); *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(v)) { //Its a global variable... //It could be an array var = getValueName(GV); if (const ArrayType *AT = dyn_cast(GV->getType()->getElementType())) { const Type* csiType = Type::getPrimitiveType(Type::Int32TyID); const ConstantInt * signedOne = ConstantInt::get(csiType,1); Constraint *c = new Constraint(var, new LinearExpr(signedOne, Mang),"="); *rootp = new ABCExprTree(*rootp,new ABCExprTree(c),"&&"); generateArrayTypeConstraintsGlobal(var, AT, rootp, 1); } } } void ConstraintGeneration::generateArrayTypeConstraintsGlobal(string var, const ArrayType *T, ABCExprTree **rootp, unsigned int numElem) { string var1 = var + "_i"; const Type* csiType = Type::getPrimitiveType(Type::Int32TyID); if (const ArrayType *AT = dyn_cast(T->getElementType())) { const ConstantInt * signedOne = ConstantInt::get(csiType,1); Constraint *c = new Constraint(var1, new LinearExpr(signedOne, Mang),"="); *rootp = new ABCExprTree(*rootp,new ABCExprTree(c),"&&"); generateArrayTypeConstraintsGlobal(var1,AT, rootp, T->getNumElements() * numElem); } else { const ConstantInt * signedOne = ConstantInt::get(csiType,numElem * T->getNumElements()); Constraint *c = new Constraint(var1, new LinearExpr(signedOne, Mang),"="); *rootp = new ABCExprTree(*rootp,new ABCExprTree(c),"&&"); } } void ConstraintGeneration::generateArrayTypeConstraints(string var, const ArrayType *T, ABCExprTree **rootp) { string var1 = var + "_i"; const Type* csiType = Type::getPrimitiveType(Type::Int32TyID); const ConstantInt * signedOne = ConstantInt::get(csiType,T->getNumElements()); Constraint *c = new Constraint(var1, new LinearExpr(signedOne, Mang),"="); *rootp = new ABCExprTree(*rootp,new ABCExprTree(c),"&&"); if (const ArrayType *AT = dyn_cast(T->getElementType())) { generateArrayTypeConstraints(var1,AT, rootp); } else if (const StructType *ST = dyn_cast(T->getElementType())) { //This will only work one level of arrays and structs //If there are arrays inside a struct then this will //not help us prove the safety of the access .... unsigned Size = getAnalysis().getTypeSize(ST); string var2 = var1 + "_i"; const Type* csiType = Type::getPrimitiveType(Type::Int32TyID); const ConstantInt * signedOne = ConstantInt::get(csiType,Size); Constraint *c = new Constraint(var2, new LinearExpr(signedOne, Mang),"="); *rootp = new ABCExprTree(*rootp,new ABCExprTree(c),"&&"); } } ABCExprTree *ConstraintGeneration::getArgumentConstraints(Function & F) { if (buCG->isInSCC(&F)) return 0; //Ignore recursion for now std::set reqArgFList; bool localSave = reqArgs; //First check if it is in cache ABCExprTree *root = fMap[&F]->getArgumentConstraints(); if (root) { return root; } else { //Its not there in cache, so we compute it if (buCG->FuncCallSiteMap.count(&F)) { std::vector &cslist = buCG->FuncCallSiteMap[&F]; for (unsigned idx = 0, sz = cslist.size(); idx != sz; ++idx) { ABCExprTree *rootCallInst = 0; if (CallInst *CI = dyn_cast(cslist[idx].getInstruction())) { //we need to AND the constraints on the arguments reqArgs = false; Function::arg_iterator formalArgCurrent = F.arg_begin(), formalArgEnd = F.arg_end(); for (unsigned i = 1; formalArgCurrent != formalArgEnd; ++formalArgCurrent, ++i) { if (i < CI->getNumOperands()) { string varName = getValueName(formalArgCurrent); Value *OperandVal = CI->getOperand(i); LinearExpr *le = new LinearExpr(OperandVal,Mang); Constraint* c1 = new Constraint(varName,le,"="); ABCExprTree *temp = new ABCExprTree(c1); if (!isa(OperandVal)) { getConstraints(OperandVal,&temp); } if (!rootCallInst) { rootCallInst = temp; } else { rootCallInst = new ABCExprTree(rootCallInst, temp, "&&"); } } } if (reqArgs) { //This Call site requires args better to maintain a set //and get the argument constraints once for all //since there could be multiple call sites from the same function reqArgFList.insert(CI->getParent()->getParent()); } } if (!root) root = rootCallInst; else { root = new ABCExprTree(root, rootCallInst, "||"); } } std::set::iterator sI = reqArgFList.begin(), sE= reqArgFList.end(); for (; sI != sE ; ++sI) { ABCExprTree * argConstraints = getArgumentConstraints(**sI); if (argConstraints) root = new ABCExprTree(root, argConstraints, "&&"); } fMap[&F]->addArgumentConstraints(root); //store it in cache } } reqArgs = localSave; return root; } bool ConstraintGeneration::runOnModule(Module &M) { cbudsPass = &getAnalysis(); buCG = &getAnalysis(); Mang = new Mangler(M); initialize(M); return false; } void ConstraintGeneration::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 branch constraint"); if (CmpInst *SCI = dyn_cast(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,Mang); string var0 = getValueName(operand0); Constraint *ct = 0; switch(SCI->getPredicate()) { case ICmpInst::ICMP_ULE: case ICmpInst::ICMP_SLE: //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 ICmpInst::ICMP_UGE: case ICmpInst::ICMP_SGE: if (BI->getSuccessor(0) == Successor) { //true branch ct = new Constraint(var0,l1,">="); } else { //false branch ct = new Constraint(var0,l1,"<"); } break; case ICmpInst::ICMP_ULT: case ICmpInst::ICMP_SLT: if (BI->getSuccessor(0) == Successor) { //true branch ct = new Constraint(var0,l1,"<"); } else { //false branch ct = new Constraint(var0,l1,">="); } break; case ICmpInst::ICMP_UGT: case ICmpInst::ICMP_SGT: if (BI->getSuccessor(0) == Successor) { //true branch ct = new Constraint(var0,l1,">"); } else { //false branch ct = new Constraint(var0,l1,"<="); } break; default : break; } if (ct != 0) { ct->print(std::cerr); *rootp = new ABCExprTree(*rootp,new ABCExprTree(ct),"&&"); } } } // SimplifyExpression: Simplify a Value and return it as an affine expressions LinearExpr* ConstraintGeneration::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, Mang) ; // nothing known return variable itself if ((isa(Expr)) || (isa(Expr))) assert(1 && "Unexpected expression type to classify!"); if ((isa(Expr)) || (isa(Expr))) { reqArgs = true; //I know using global is ugly, fix this later return new LinearExpr(Expr, Mang); } if (isa(Expr)) { Constant *CPV = cast(Expr); if (CPV->getType()->isIntegral()) { // It's an integral constant! if (dyn_cast(CPV)) { assert(1 && "Constant Array don't know how to get the values "); } else if (ConstantInt *CPI = dyn_cast(Expr)) { return new LinearExpr(CPI, Mang); } } return new LinearExpr(Expr, Mang); //nothing known, just return itself } if (isa(Expr)) { Instruction *I = cast(Expr); 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), Mang); } LinearExpr* Right = (SimplifyExpression(I->getOperand(1), rootp)); if (Right == 0) { Right = new LinearExpr(I->getOperand(1), Mang); } Left->addLinearExpr(Right); return Left; } case Instruction::Sub: { LinearExpr* Left = (SimplifyExpression(I->getOperand(0), rootp)); if (Left == 0) { Left = new LinearExpr(I->getOperand(0), Mang); } LinearExpr* Right = (SimplifyExpression(I->getOperand(1), rootp)); if (Right == 0) { Right = new LinearExpr(I->getOperand(1), Mang); } Right->negate(); Left->addLinearExpr(Right); return Left; } case Instruction::FCmp : case Instruction::ICmp : { LinearExpr* L = new LinearExpr(I->getOperand(1),Mang); return L; }; case Instruction::Mul : LinearExpr* Left = (SimplifyExpression(I->getOperand(0),rootp)); if (Left == 0) { Left = new LinearExpr(I->getOperand(0), Mang); } LinearExpr* Right = (SimplifyExpression(I->getOperand(1),rootp)); if (Right == 0) { Right = new LinearExpr(I->getOperand(1), Mang); } return Left->mulLinearExpr(Right); } // end switch if (isa(I)) { DEBUG(std::cerr << "dealing with cast instruction "); //Here we have to give constraints for //FIXME .. this should be for all types not just sbyte const Type *fromType = I->getOperand(0)->getType(); const Type *toType = I->getType(); string number1; string number2; bool addC = false; if (toType->isPrimitiveType() && fromType->isPrimitiveType()) { switch(toType->getTypeID()) { case Type::Int32TyID : switch (fromType->getTypeID()) { case Type::Int8TyID : number1 = "-128"; number2 = "127"; addC = true; break; case Type::Int8TyID : number1 = "0"; number2 = "255"; addC = true; default: break; } case Type::Int32TyID : switch(fromType->getTypeID()) { case Type::Int32TyID : //in llvm front end the malloc argument is always casted to //uint! so we hack it here //This hack works incorrectly for //some programs so moved it to malloc itself //FIXME FIXME This might give incorrect results in some cases!!!! addC = true; break; case Type::Int8TyID : case Type::Int8TyID : number1 = "0"; number2 = "255"; addC = true; break; default : break; } default: break; } if (addC) { string var = getValueName(I); LinearExpr *l1 = new LinearExpr(I,Mang); if (number1 != "") { Constraint *c1 = new Constraint(number1,l1,">=",true); *rootp = new ABCExprTree(*rootp,new ABCExprTree(c1),"&&"); } if (number2 != "") { Constraint *c2 = new Constraint(number2,l1,"<=",true); *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(I->getType())){ const Type *eltype = pType->getElementType(); if (eltype->isPrimitiveType() && (eltype->getTypeID() == Type::Int8TyID)) { if (const PointerType *opPType = dyn_cast(fromType)){ const Type *opEltype = opPType->getElementType(); if (const StructType *stype = dyn_cast(opEltype)) { if (const ArrayType *aType = dyn_cast(stype->getContainedType(0))) { if (aType->getElementType()->isPrimitiveType()) { int elSize = aType->getNumElements(); switch (aType->getElementType()->getTypeID()) { case Type::Int16Ty : case Type::Int16TyID : elSize *= 2; break; case Type::Int32TyID : case Type::Int32TyID : elSize *= 4; break; case Type::Int64Ty : case Type::Int64TyID : elSize *= 8; break; default : break; } string varName = getValueName(I); const Type* csiType = Type::getPrimitiveType(Type::Int32TyID); const ConstantInt * signedOne = ConstantInt::get(csiType,elSize); LinearExpr *l1 = new LinearExpr(signedOne, Mang); return l1; } } } } } } } return SimplifyExpression(I->getOperand(0),rootp); } else { getConstraints(I,rootp); LinearExpr* ret = new LinearExpr(I,Mang); return ret; } } // Otherwise, I don't know anything about this value! return 0; } Pass *createConstraintGenerationPass() { return new ABC::ConstraintGeneration(); }