/* Alias Analysis: See doc/alias-analysis.txt for a high-level description of the algorithm. We associate with each allocation expression or String literal an abstract value unique within the method. We associate with each local variable a list of POSSIBLE abstract values for that variable. Each abstract value is in turn associated with a record (ValueInfo) of things associated with that value: if it is an Object, the possible values of its fields; if it's an array, the possible values of its elements. For example, in the following: 1. a = new int[]; 2. b = a; 3. a[i] = c; 4. c = m[j]; 5. a = obj.outSideField; After (1), 'a' would be mapped to a list consisting only of an anonymous abstract value with its arrayValues set to the a list containing the null abstract value, meaning a[???] has no possible values but 'null'. After (2), b would be mapped to a copy of the values of a. After (3), the arrayValues field associated with every value's record in the values-list of a (in this case only the anonymous value created by 'new') would have the values-list of c appended to its values-list. After (4), the values-list of c will be a concatenation of the arrayValues of each value in the values-list of m. After (5), a's values-list will be a singleton list consisting of nothing but 'the external abstract value'. Values-lists are represented by Bitsets. The only types of possible known values are: allocations, String literals, null, 'this', and an external value representing arbitrary values from the outside. An AliasInfo gives complete information about what is known about any variables at a particular point in the program. It has a mapping of local variable declarations to lists of possible values (Bitsets), and a mapping of abstract values (ints) to ValueInfos. Only method calls and assignments affect AliasInfos. Some examples: 1. a = b; The Bitset of a becomes a copy of the Bitset of b. 2. a = b[i]; The Bitset of a becomes a concatenation of the arrayValues of every possible value of b. 3. a[i] = b; The arrayValues of EVERY value record in the Bitset of a is unioned with the Bitset of b. 4. a[i] = b[i]; The arrayValues of EVERY value in the Bitset of a is unioned with the arrayValues of every Value in the Bitset of b. 5. a.x = b[i]; The Bitset corresponding to the decl of x in every value in the Bitset of a becomes a copy of the Bitset of b[i]. 7. xxx = some.method(v1, ..., vn); xxx's appropriate Bitset gets unioned/replaced with a list of every possible value of v1, ..., vn, every possible sub-value thereof, AND the EXTERNALVALUE. Every sub-value of v1, ..., vn gets joined with every other sub-value of v1, ..., vn, and the EXTERNALVALUE. Furthermore, we have to go erase everything we know about any object's fields in our own method. (The EXTERNALVALUE is used to denote that the variable may be an external value.) Note that, currently, any list of values is only a POSSIBLE list. Just because a certain variable has a singleton list doesn't mean it definitely has that value. This comes mainly from the field/arrayaccess assignment of multiply-valued local variables. One day we might find something more efficient than Bitsets. */ #include "AST.h" #include "cfg.h" #include "code-aa.h" #include "compiler.h" #include "MethodSet.h" extern bool alias_anal; extern bool aaDebugOn; extern bool aaSuperDebugOn; // Used during setup of each method to use the TraverseBblocks(...) // procedures.. yuck static AliasInfos *incomingAliasInfos; // the current method being analyzed. static MethodStatics *currentMethodStatics; // static Bitset *currentSpecialValues; // don't use this, it's not what you think it is. it's only for debugging static AliasInfos *methodAliases; //////////////////////////////// ANALYSIS UTILS ////////////////////////// bool isInterestingNode(TreeNode *t) { return (isMethodCallNode(t) || isAssignNode(t) || isAllocateNode(t)); } void leak(AliasInfos *ai, int value) { assert(isInMap(value, ai->valueToValueInfoMap)); ai->leaksSet->set(value); currentMethodStatics->leaksValues->set(value); } void leak(AliasInfos *ai, Bitset *values) { ai->leaksSet->un(values); currentMethodStatics->leaksValues->un(values); } /* A big nasty print. */ /* void printAllAliasesBblock(Bblock *b) { cout << "Full results on bblock #" << b->number << endl; ListIterator cfgIt = b->cfgIter(); for (; !cfgIt.isDone(); cfgIt.next()) { CfgNode *cfg = *cfgIt; TreeNode *t = cfg->astNode(); if (isHandled(t)) { t->print(cout); cout << endl; cout << "------------" << endl; ListIterator cfgIt2 = b->cfgIter(); for (; !cfgIt2.isDone(); cfgIt2.next()) { CfgNode *cfg2 = *cfgIt2; TreeNode *t2 = cfg2->astNode(); if (isHandled(t2)) { t2->print(cout); cout << endl; cout << methodAliases->checkAliases(t, t2) << endl; cout << "--" << endl; } } } cout << "============" << endl; } } */ // Sets up the map with the local parameters. The values are numbered as // follows: system values go up to AA_FIRSTVALUE - 1, parameters (if any) // start at AA_FIRSTVALUE, and then local values. AliasInfos *createInitialAliasInfos(TreeNode *t, int size) { AliasInfos *ai = new AliasInfos(size, t); TreeListNode *params = t->params(); for (int i = 0; i < params->arity(); i++) { if (isAliasable(params->child(i)->dtype())) { int slot = AA_FIRSTVALUE + i; // here, to simplify our calculations (so that they fit in the // mechanisms), I'm going to make argument values have themselves as // subvalues, and make their types theNullType instead of // params->child(i)->dtype(). Some day we can make it more precise // by doing more work. ai->setupValueInfo(slot, theNullType); Bitset *b = new Bitset(size); b->set(slot); ai->declToBitsetMap[params->child(i)->simpName()->decl()] = b; ai->valueToValueInfoMap[slot]->arrayValues = copyBitset(b); ai->valueToValueInfoMap[slot]->unknownFieldValue = slot; } } return ai; } /* Merge the given bblock's aliases into the global one. */ void mergeAliasesBblock(Bblock *b) { methodAliases->merge(b->aliasesOut()); } static Bitset *makeComparable(AliasInfos *ai, Bitset *b) { if (!b->disjoint(currentMethodStatics->specialValues)) b->set(AA_EXTERNALVALUE); if (b->test(AA_EXTERNALVALUE)) b->un(ai->leaksSet); return b; } /* Lame way to make sure all nodes that may have a field/array access (e.g. ObjectNodes, ThisNode) have comparable values sets after the analysis. */ static void setupValueForObjects(AliasInfos *ai, TreeNode *t) { if ((isObjectNode(t) || isThisNode(t)) && isAliasable(t->type())) { Bitset *b = copyBitset(t->getValues(ai)); t->setAbstractValues(makeComparable(ai, b)); if (aaDebugOn || aaSuperDebugOn) { cout << "Object "; t->pseudoprint(cout, 0); cout << " has values "; printBitset(t->getAbstractValues(), cout); cout << endl; } } } void clearAliasesIn(Bblock *b) { delete b->aliasesIn(); b->setAliasesIn(NULL); } void printFinalStats(TreeNode *t) { cout << "*********************************" << endl; cout << "Final statistics for method "; cout << *t->simpName()->ident() << " in "; t->decl()->container()->print(cout); cout << endl << endl; cout << "Status = " << currentMethodStatics->status << endl; cout << "Is sideEffectFree? " << currentMethodStatics->isSideEffectFree(); cout << endl; cout << "Modifies the values: "; printBitset(currentMethodStatics->modifiesValues, cout); cout << endl; cout << "Leaks the values: "; printBitset(currentMethodStatics->leaksValues, cout); cout << endl; cout << "Returns the values: "; printBitset(currentMethodStatics->returnsValues, cout); cout << endl; methodAliases = new AliasInfos(t->getBblockRoot()->aliasesOut()->size, currentMethodStatics->method); TraverseBblocks(t->getBblockRoot(), mergeAliasesBblock); cout << "APPROXIMATE ALIASINFOS:" << endl; methodAliases->println(cout); cout << "*********************************" << endl; // methodAliases->printAliases(cout); // cout << endl; // TraverseBblocks(t->getBblockRoot(), printAllAliasesBblock); methodAliases = NULL; } //////////////////////////////// ANALYSIS CODE ////////////////////////// // Analyse one method. Don't call directly. void analyzeMethod(TreeNode *t) { if (aaDebugOn || aaSuperDebugOn) { cout << "Doing analysis on "; t->simpName()->pseudoprint(cout, 0); cout << endl; } assert(t->getBblockRoot() != NULL); assert(t->methodStatics() != NULL); currentMethodStatics = t->methodStatics(); currentMethodStatics->status = 1; incomingAliasInfos = createInitialAliasInfos(t, t->methodStatics()->numValues()); if (t->getBblockRoot()->aliasesIn() != NULL) TraverseBblocks(t->getBblockRoot(), clearAliasesIn); // do the actual alias analysis TraverseBblocksIter(t->getBblockRoot(), setupAliasesBblock); TraverseBblocks(t->getBblockRoot(), finalPassAliasesBblock); if (aaDebugOn || aaSuperDebugOn) printFinalStats(t); } // alias analysis on one bblock bool setupAliasesBblock(Bblock *b) { AliasInfos *nextAliasesIn = new AliasInfos(currentMethodStatics->numValues(), currentMethodStatics->method); // take in the method arguments if it's the root block if (incomingAliasInfos != NULL) { nextAliasesIn->merge(incomingAliasInfos); incomingAliasInfos = NULL; } // merge with the incoming ones.. ListIterator bbIt = b->predIter(); for (; !bbIt.isDone(); bbIt.next()) { Bblock *bb = *bbIt; if (bb->aliasesIn() != NULL) { nextAliasesIn->merge(bb->aliasesOut()); } } // check if it's the same as last time, if so just quit if (b->aliasesIn() != NULL && b->aliasesIn()->equivalent(nextAliasesIn)) return false; // save it for next check b->setAliasesIn(nextAliasesIn); // keep a running total to calculate the out-set AliasInfos *aliasesOut = new AliasInfos(nextAliasesIn->size, currentMethodStatics->method); aliasesOut->merge(b->aliasesIn()); ListIterator cfgIt = b->cfgIter(); for (; !cfgIt.isDone(); cfgIt.next()) { CfgNode *cfg = *cfgIt; TreeNode *t = cfg->astNode(); if (aaSuperDebugOn && isInterestingNode(t)) { cout << "----------------"; t->pseudoprint(cout, 0); cout << endl; } aliasesOut->process(t); if (aaSuperDebugOn && isInterestingNode(t)) { cout << "Current aliases info: " << endl; aliasesOut->println(cout); cout << "Current method statics: " << endl; currentMethodStatics->println(cout); } } b->setAliasesOut(aliasesOut); return true; } // Leave residual info for later stages. duplicates above to get // intro-bblock info. void finalPassAliasesBblock(Bblock *b) { AliasInfos *aliasesOut = new AliasInfos(b->aliasesIn()->size, currentMethodStatics->method); aliasesOut->merge(b->aliasesIn()); ListIterator cfgIt = b->cfgIter(); for (; !cfgIt.isDone(); cfgIt.next()) { CfgNode *cfg = *cfgIt; TreeNode *t = cfg->astNode(); setupValueForObjects(aliasesOut, t); aliasesOut->process(t); } // very subtle: doing it again MAY change something only if we're // pending our OWN result, but it's OK in that case we'll be redoing // this whole method yet again anyway so none of this stuff matters.. // if (currentMethodStatics->status != 3) // assert(b->aliasesOut()->equivalent(aliasesOut)); } // accumulates into bs this value and every sub-value (recursive) that any // sub anything can have. void accumulateValues(int value, Bitset *bs, AliasInfos *ai) { if (bs->test(value)) return; bs->set(value); assert(isInMap(value, ai->valueToValueInfoMap)); ValueInfo *vi = ai->valueToValueInfoMap[value]; bool isArray = vi->valueType->isArrayType() || vi->valueType->isNullType(); bool isObj = !vi->valueType->isArrayType() || vi->valueType->isNullType(); if (isArray) { for (int i = 0; i < vi->arrayValues->size(); i++) { if (vi->arrayValues->test(i) && !bs->test(i)) accumulateValues(i, bs, ai); } } if (isObj) { for (DeclToBitsetMap::const_iterator v = vi->fieldToBitsetMap.begin(); v != vi->fieldToBitsetMap.end(); v++) { Bitset *fieldBitset = (*v).second; for (int i = 0; i < fieldBitset->size(); i++) { if (fieldBitset->test(i) && !bs->test(i)) accumulateValues(i, bs, ai); } } accumulateValues(vi->unknownFieldValue, bs, ai); } } // like the above, but only those values possibly returned/leaked/whatever // as given in rv Bitset *getMatchedFormalSubvalues(TreeNode *t, AliasInfos *ai, Bitset *rv) { TreeListNode *args = t->args(); Bitset *accumulator = new Bitset(ai->size); for (int i = 0; i < args->arity(); i++) { if (rv->test(i + AA_FIRSTVALUE)) { TreeNode *nextParam = args->child(i); Bitset *values = nextParam->getValues(ai); for (int j = 0; j < values->size(); j++) { if (values->test(j)) accumulateValues(j, accumulator, ai); } } } return accumulator; } // get all values and subvalues of the arguments, and of the object too if // objectValues is not NULL Bitset *getMatchedObjectFormalSubvalues(TreeNode *t, AliasInfos *ai, Bitset *rv, Bitset *objectValues) { //TreeListNode *args = t->args(); Bitset *accumulator = new Bitset(ai->size); // if it's a.method(...), and a is an object (and not a type), then we // gotta get all values and subvalues of a. if (objectValues != NULL && rv->test(AA_THISVALUE)) { for (int i = 0; i < objectValues->size(); i++) { if (objectValues->test(i)) accumulateValues(i, accumulator, ai); } } accumulator->un(getMatchedFormalSubvalues(t, ai, rv)); return accumulator; } // clobbers all subvalues of the given value void clobberSubvalues(int value, Bitset *incomingValues, Bitset *casualty, AliasInfos *ai) { if (casualty->test(value)) return; casualty->set(value); ValueInfo *vi = ai->valueToValueInfoMap[value]; for (int i = 0; i < vi->arrayValues->size(); i++) { if (vi->arrayValues->test(i) && !casualty->test(i)) clobberSubvalues(i, incomingValues, casualty, ai); } // no longer know anything about any fields vi->fieldToBitsetMap.clear(); // we do here a more careful union. We only pick out the ones that could // possibly be assigned to my dtype if i'm an array if (vi->valueType->isArrayType()) { TypeNode *eltType = vi->valueType->elementType(); for (int i = 0; i < incomingValues->size(); i++) { if (incomingValues->test(i) && eltType->isCastableFrom(ai->valueToValueInfoMap[i]->valueType)) vi->arrayValues->set(i); } } } // clobber all subvalues with those given. void clobberMatchedFormalSubvalues(TreeNode *t, Bitset *subValues, Bitset *casualty,AliasInfos *ai, Bitset *rv) { for (int i = 0; i < t->args()->arity(); i++) { if (rv->test(i + AA_FIRSTVALUE)) { Bitset *values = t->args()->child(i)->getValues(ai); for (int j = 0; j < values->size(); j++) { if (values->test(j)) clobberSubvalues(j, subValues, casualty, ai); } } } } // clobber formal values and subvalues of procedure call t (if they're in // rv) with the specified subValues, and also for the objectValues if it's // not NULL. returns casualty Bitset *clobberMatchedObjectFormalSubvalues(TreeNode *t, Bitset *subValues, AliasInfos *ai, Bitset *rv, Bitset *objectValues) { Bitset *casualty = new Bitset(ai->size); // if it's a.method(...), and a is an object (and not a type), then we // gotta clobber subvalues of a. if (objectValues != NULL && rv->test(AA_THISVALUE)) { for (int i = 0; i < objectValues->size(); i++) { if (objectValues->test(i)) clobberSubvalues(i, subValues, casualty, ai); } } clobberMatchedFormalSubvalues(t, subValues, casualty, ai, rv); return casualty; } void collectValues(AliasInfos *ai, Bitset *casualty, Bitset *values); void collectValueAndSubvalues(int value, AliasInfos *ai, Bitset *casualty) { casualty->set(value); ValueInfo *vi = ai->valueToValueInfoMap[value]; collectValues(ai, casualty, vi->arrayValues); for (DeclToBitsetMap::const_iterator v = vi->fieldToBitsetMap.begin(); v != vi->fieldToBitsetMap.end(); v++) { Bitset *bs = (*v).second; collectValues(ai, casualty, bs); } } void collectValues(AliasInfos *ai, Bitset *casualty, Bitset *values) { for (int i = 0; i < values->size(); i++) { if (!casualty->test(i) && values->test(i)) collectValueAndSubvalues(i, ai, casualty); } } bool containsDirty(Bitset *b, AliasInfos *ai) { if (!b->disjoint(ai->leaksSet)) return true; if (b->test(AA_THISVALUE)) return true; for (int i = 0; i < currentMethodStatics->method->params()->arity(); i++) if (b->test(i + AA_FIRSTVALUE)) return true; return false; } // values should be NULL if it's not an aliasable type on the right side. void checkStaticsObjectAccessAssignment(AliasInfos *ai, Bitset *objectValues, Bitset *values) { currentMethodStatics->modifiesValues->un(objectValues); // if you get asigned to a dirty object's field, you get leaked! if (values != NULL && containsDirty(objectValues, ai)) { Bitset *casualty = new Bitset(ai->size); collectValues(ai, casualty, values); leak(ai, casualty); } } MethodStatics *lookupStatics(TreeNode *methodCall, TreeNode *md); llist *filterWaiters(TreeNode *m, llist *callBackList) { if (callBackList == NULL) return callBackList; if (callBackList->front()->waiter != m) { callBackList->tail() = filterWaiters(m, callBackList->tail()); return callBackList; } else return filterWaiters(m, callBackList->free()); } // will look up and set the methodStatics if not available MethodStatics *getMethodDeclStatics(TreeNode *methodDecl) { if (methodDecl->methodStatics() == NULL) { MethodStatics *ms = lookupStatics(methodDecl); if (ms == NULL) ms = fullMethodStatics(methodDecl); methodDecl->setMethodStatics(ms); if (isKnownSideEffectFree(methodDecl)) { MethodStatics *ms = methodDecl->methodStatics(); ms->modifiesValues = new Bitset(methodDecl->methodStatics()->numValues()); ms->leaksValues = ms->modifiesValues; } } // if it's not done, i'm pending a result (this one, in particular) if (methodDecl->methodStatics()->status != 2) { currentMethodStatics->status = 3; MethodWaiter *me = new MethodWaiter; me->waiter = currentMethodStatics->method; me->ms = methodDecl->methodStatics()->emptyCopy(); methodDecl->methodStatics()->callBackList = cons(me, filterWaiters(me->waiter, methodDecl->methodStatics()->callBackList)); } return methodDecl->methodStatics(); } void mergeOverriders(MethodStatics *ms, Decl *d) { MethodSet *overriders = d->overriders(); for (MethodSet::const_iterator method = overriders->begin(); method != overriders->end(); method++) { ms->merge(getMethodDeclStatics((*method)->source())); mergeOverriders(ms, *method); } } MethodStatics *getMethodCallStatics(TreeNode *methodCall) { TreeNode *methodDecl = methodCall->decl()->source(); MethodStatics *ms = getMethodDeclStatics(methodDecl)->emptyCopy(); // only method calls may be overridden if (isMethodCallNode(methodCall)) { mergeOverriders(ms, methodCall->decl()); } return ms; } Bitset *getObjectValues(AliasInfos *ai, TreeNode *t) { // the value of 'this' inside the method if (isMethodCallNode(t) && isOFAN(t->method())) return t->method()->object()->getValues(ai); else if (isAllocateNode(t)) return t->getValues(ai); else if (isConstructorCallNode(t)) return currentMethodStatics->myThisValueBitset(); return NULL; } // update the various method statics due to "procedure"CallNode t. void checkStaticsProcedureCall(AliasInfos *ai, TreeNode *t) { MethodStatics *ms = getMethodCallStatics(t); Bitset *objectValues = getObjectValues(ai, t); // since any value that clobbers another argument (or 'this') would be // considered leaked, we can restrict to leaked values... Bitset *Restrict = ms->leaksValues; Bitset *argsLeaked = getMatchedObjectFormalSubvalues(t, ai, Restrict, objectValues); if (Restrict->test(AA_EXTERNALVALUE)) argsLeaked->un(ai->leaksSet); // clobbers the modified arguments with the leaked arguments. technical // note: it is enough just to always clobber them with only the external // value, since we make the leaked values dirty anyway, but this is more // precise in the case where they don't clobber external values Bitset *modified = clobberMatchedObjectFormalSubvalues(t, argsLeaked, ai, ms->modifiesValues, objectValues); // leave residual info for use-def t->setModifiesValues(makeComparable(ai, copyBitset(modified))); if (aaSuperDebugOn) { cout << "He modifies values: "; printBitset(ms->modifiesValues, cout); cout << endl; cout << "...that's to us: "; printBitset(modified, cout); cout << endl; cout << "Leaked (to us): "; printBitset(argsLeaked, cout); cout << endl; } // if he modified ext, then also clobber the dirty values with the // leaked values -- but we can restrict to leaked+EXT instead of dirty // (see doc). if (ms->modifiesValues->test(AA_EXTERNALVALUE)) { for (int i = 0; i < ai->leaksSet->size(); i++) { if (ai->leaksSet->test(i)) clobberSubvalues(i, argsLeaked, modified, ai); } } currentMethodStatics->modifiesValues->un(modified); // if they leaked it, we leaked it leak(ai, argsLeaked); if (isMethodCallNode(t) && isAliasable(t->type())) { if (!ms->returnsValues->disjoint(ms->leaksValues)) { ai->setupValueInfo(currentMethodStatics->ASTValueMap[t], t->type()); leak(ai, currentMethodStatics->ASTValueMap[t]); } } } ////////////////////////// ::getValues and ::handleAssignment //////////////// // Be very careful about "aliasing" of the returned Bitset. // NOTE: a getValues on an AllocateNode does NOT clobbers its arguments. // see comments for methodcallNode Bitset *AllocateNode::getValues(AliasInfos *ai) { int value = currentMethodStatics->ASTValueMap[this]; ai->setupValueInfo(value, dtype()); // this never changes -- can be cached if (_abstractValues != NULL) return _abstractValues; else { Bitset *temp = new Bitset(ai->size); temp->set(value); setAbstractValues(temp); return temp; } } Bitset *AllocateArrayNode::getValues(AliasInfos *ai) { int value = currentMethodStatics->ASTValueMap[this]; ai->setupValueInfo(value, type()); // this never changes -- can be cached if (_abstractValues != NULL) return _abstractValues; Bitset *temp = new Bitset(ai->size); temp->set(value); setAbstractValues(temp); return temp; } Bitset *StringLitNode::getValues(AliasInfos *ai) { int value = currentMethodStatics->ASTValueMap[this]; ai->setupValueInfo(value, type()); // this never changes -- can be cached if (_abstractValues != NULL) return _abstractValues; Bitset *temp = new Bitset(ai->size); temp->set(value); setAbstractValues(temp); return temp; } Bitset *ArrayInitNode::getValues(AliasInfos *ai) { int value = currentMethodStatics->ASTValueMap[this]; ai->setupValueInfo(value, type()); // this never changes -- can be cached if (_abstractValues != NULL) return _abstractValues; Bitset *temp = new Bitset(ai->size); temp->set(value); setAbstractValues(temp); return temp; } // return remote values too. Bitset *IBroadcastNode::getValues(AliasInfos *ai) { Bitset *values = expr()->getValues(ai); return values; } Bitset *CastNode::getValues(AliasInfos *ai) { Bitset *values = opnd0()->getValues(ai); return values; } Bitset *ObjectNode::getValues(AliasInfos *ai) { // local variables MAY NOT have been initialized in Titanium. it // doesn't check. Bitset *result; Decl *decl = name()->decl(); if (isInMap(decl, ai->declToBitsetMap)) result = copyBitset(ai->declToBitsetMap[decl]); else { result = currentMethodStatics->myNullValueBitset(); } return result; } Bitset *ThisNode::getValues(AliasInfos *ai) { return currentMethodStatics->myThisValueBitset(); } Bitset *NullPntrNode::getValues(AliasInfos *ai) { return currentMethodStatics->myNullValueBitset(); } /* This is only needed because of templates producing weirdness on method parameter dtypes. */ Bitset *PrimitiveLitNode::getValues(AliasInfos *ai) { return currentMethodStatics->myNullValueBitset(); } Bitset *ObjectFieldAccessNode::getValues(AliasInfos *ai) { if (decl()->isStatic()) return currentMethodStatics->myExtValueBitset(); // NOTE: we have to take care of the case of a chain of immutables. // a.i1...ik.b. Hold your horses. // get the possible values for the object Bitset *bs = object()->getValues(ai); Bitset *result = new Bitset(bs->size()); // iterate over those possible values Decl *fieldDecl = simpName()->decl(); for (int i = 0; i < bs->size(); i++) { if (bs->test(i)) { assert(isInMap(i, ai->valueToValueInfoMap)); if (isInMap(fieldDecl, ai->valueToValueInfoMap[i]->fieldToBitsetMap)) result->un(ai->valueToValueInfoMap[i]->fieldToBitsetMap[fieldDecl]); else result->set(ai->valueToValueInfoMap[i]->unknownFieldValue); } } return result; } Bitset *TypeFieldAccessNode::getValues(AliasInfos *ai) { return currentMethodStatics->myExtValueBitset(); } // NOTE: a getValues on a MethodCallNode does NOT clobber its arguments. // This is because this would see it 2 times in an assign method call Bitset *MethodCallNode::getValues(AliasInfos *ai) { MethodStatics *ms = decl()->source()->methodStatics(); Bitset *objectValues = isOFAN(method()) ? method()->object()->getValues(ai) : NULL; Bitset *returnedValues = ms->returnsValues; Bitset *subValues = getMatchedObjectFormalSubvalues(this, ai, returnedValues, objectValues); if (aaSuperDebugOn) { cout << "He returns: "; printBitset (returnedValues, cout); cout << endl; cout << "That's to us: "; printBitset (subValues, cout); cout << endl; } if (returnedValues->test(AA_EXTERNALVALUE)) { subValues->set(AA_EXTERNALVALUE); subValues->un(ai->leaksSet); } // this sort of represents a possible value new'ed in the called method. // this is only for consistency and doesn't really mean anything. int value = currentMethodStatics->ASTValueMap[this]; ai->setupValueInfo(value, type()); subValues->set(value); // now filter out subValues that are unreasonable. if (type()->kind() != Common::VoidKind) { for (int i = 0; i < subValues->size(); i++) { if (subValues->test(i) && !type()->isCastableFrom(ai->valueToValueInfoMap[i]->valueType)) subValues->clear(i); } } return subValues; } Bitset *ArrayAccessNode::getValues(AliasInfos *ai) { Bitset *objectBitset = ai->lookupDecl(array()->name()->decl()); Bitset *temp = new Bitset(ai->size); for (int i = 0; i < objectBitset->size(); i++) { if (objectBitset->test(i)) { temp->un(ai->valueToValueInfoMap[i]->arrayValues); } } return temp; } bool ObjectNode::handleAssignment(AliasInfos *ai, Bitset* values) { Decl *decl = name()->decl(); ai->declToBitsetMap[decl] = copyBitset(values); return true; } bool ObjectFieldAccessNode::handleAssignment(AliasInfos *ai, Bitset* values) { // NOTE: we have to take care of the case of a chain of immutables. // a.i1...ik.b. Hold your horses. I think the lowered AST is still // separating out chains into temporaries. if (decl()->isStatic()) { checkStaticsObjectAccessAssignment(ai, currentMethodStatics->myExtValueBitset(), values); return true; } Bitset *bs = object()->getValues(ai); // do the static info's checking. notice we get our own values BEFORE // assignment for the purposes of checking for this stuff.. checkStaticsObjectAccessAssignment(ai, bs, values); // iterate over those possible values. if more than one, we need to // union instead of copy bool exactlyOne = false; int first = -1; Decl *fieldDecl = simpName()->decl(); for (int i = 0; i < bs->size(); i++) { if (bs->test(i)) { assert(isInMap(i, ai->valueToValueInfoMap)); if (first == -1) { first = i; exactlyOne = true; } else if (exactlyOne) exactlyOne = false; if (isInMap(fieldDecl, ai->valueToValueInfoMap[i]->fieldToBitsetMap)) ai->valueToValueInfoMap[i]->fieldToBitsetMap[fieldDecl]->un(values); else ai->valueToValueInfoMap[i]->fieldToBitsetMap[fieldDecl] = copyBitset(values); } } if (exactlyOne && first != AA_NULLVALUE && first != AA_EXTERNALVALUE) ai->valueToValueInfoMap[first]->fieldToBitsetMap[fieldDecl] = copyBitset(values); return true; } bool TypeFieldAccessNode::handleAssignment(AliasInfos *ai, Bitset* values) { checkStaticsObjectAccessAssignment(ai, currentMethodStatics->myExtValueBitset(), values); return true; } bool ArrayAccessNode::handleAssignment(AliasInfos *ai, Bitset* values) { Bitset *varValues = array()->getValues(ai); // do the static info's checking. notice we get our own values BEFORE // assignment for the purposes of checking for this stuff.. checkStaticsObjectAccessAssignment(ai, varValues, values); // every array value gets modified. in an array, we UNION, we never // delete values. for (int i = 0; i < varValues->size(); i++) { if (varValues->test(i)) { assert(isInMap(i, ai->valueToValueInfoMap)); ai->valueToValueInfoMap[i]->arrayValues->un(values); } } return true; } void AliasInfos::process(TreeNode *t) { if (isMethodCallNode(t) || isAllocateNode(t) || isConstructorCallNode(t)) checkStaticsProcedureCall(this, t); else if (isAssignNode(t)) processAssignment(t->child(0), t->child(1)); else if (isReturnNode(t)) { if (!isOmittedNode(t->expr()) && isAliasable(t->expr()->type())) { Bitset *bs = t->expr()->getValues(this); currentMethodStatics->returnsValues->un(bs); } } } bool AliasInfos::processAssignment(TreeNode *leftSide, TreeNode *rightSide) { // we check if it's an aliasable type. if it is we keep track of // aliasing, but even if it isn't, if it's an object/array/type field // access then we still need to check for side effects if (isAliasable(rightSide->type())) { Bitset *rightSideValues = rightSide->getValues(this); leftSide->handleAssignment(this, rightSideValues); return true; } else { Bitset *b = NULL; if (isTypeFAN(leftSide)) b = leftSide->getValues(this); else { if (leftSide->isArrayAccessNode()) b = leftSide->array()->getValues(this); else if (isOFAN(leftSide)) b = leftSide->object()->getValues(this); } if (b != NULL) checkStaticsObjectAccessAssignment(this, b, NULL); return true; } return true; } /////////////////////////// other stuff //////////////// Bitset *ExprNode::getAbstractValues() { /* // shouldn't be null because you should only use this after AA if (alias_anal && _abstractValues == NULL) { // this is put here because use-def treats immutables as aliasable // (and therefore bothers asking). it shouldn't. assert(type()->isImmutable()); } */ return _abstractValues; } void ExprNode::setAbstractValues(Bitset *b) { _abstractValues = b; } Bitset *TreeNode::getAbstractValues() { undefined("getAbstractValues"); return NULL; } void TreeNode::setAbstractValues(Bitset *b) { undefined("setAbstractValues"); } Bitset *MethodCallNode::modifiesValues() { return _modifiesValues; } Bitset *AllocateNode::modifiesValues() { return _modifiesValues; } void MethodCallNode::setModifiesValues(Bitset *b) { _modifiesValues = b; } void AllocateNode::setModifiesValues(Bitset *b) { _modifiesValues = b; } void TreeNode::setModifiesValues(Bitset *b) { undefined("setModifiesValues"); } Bitset *TreeNode::modifiesValues() { undefined("modifiesValues"); return NULL; } bool TreeNode::handleAssignment(AliasInfos *ai, Bitset* values) { undefined("handleAssignment"); return false; } Bitset *TreeNode::getValues(AliasInfos *ai) { undefined("getValues"); return NULL; }