dfa.cpp

Go to the documentation of this file.
00001 /*
00002  * Copyright (C) 2004-2006, Mike Van Emmerik
00003  *
00004  * See the file "LICENSE.TERMS" for information on usage and
00005  * redistribution of this file, and for a DISCLAIMER OF ALL WARRANTIES.
00006  *
00007  */
00008 
00009 /*==============================================================================
00010  * FILE:       dfa.cpp
00011  * OVERVIEW:   Implementation of class Type functions related to solving type analysis in an iterative, data-flow-based
00012  *              manner
00013  *============================================================================*/
00014 
00015 /*
00016  * $Revision: 1.74 $    // 1.30.2.11
00017  *
00018  * 24 Sep 04 - Mike: Created
00019  * 25 Aug 05 - Mike: Switch from Mycroft style "pointer to alpha plus integer equals pointer to another alpha" to
00020  *                      Van Emmerik style "result is void*" for sigma and delta functions
00021  */
00022 
00023 #include "gc.h"
00024 #include "type.h"
00025 #include "boomerang.h"
00026 #include "signature.h"
00027 #include "exp.h"
00028 #include "prog.h"
00029 #include "util.h"
00030 #include "visitor.h"
00031 #include "log.h"
00032 #include "proc.h"
00033 #include <sstream>
00034 #if defined(_MSC_VER) && _MSC_VER >= 1400
00035 #pragma warning(disable:4996)       // Warnings about e.g. _strdup deprecated in VS 2005
00036 #endif
00037 
00038 static int nextUnionNumber = 0;
00039 
00040 #ifndef max
00041 int max(int a, int b) {     // Faster to write than to find the #include for
00042     return a>b ? a : b;
00043 }
00044 #endif
00045 
00046 #define DFA_ITER_LIMIT 20
00047 
00048 // m[idx*K1 + K2]; leave idx wild
00049 static Exp* scaledArrayPat = Location::memOf(
00050     new Binary(opPlus,
00051         new Binary(opMult,
00052             new Terminal(opWild),
00053             new Terminal(opWildIntConst)),
00054         new Terminal(opWildIntConst)));
00055 // idx + K; leave idx wild
00056 static Exp* unscaledArrayPat = new Binary(opPlus,
00057         new Terminal(opWild),
00058         new Terminal(opWildIntConst));
00059 
00060 // The purpose of this funciton and others like it is to establish safe static roots for garbage collection purposes
00061 // This is particularly important for OS X where it is known that the collector can't see global variables, but it is
00062 // suspected that this is actually important for other architectures as well
00063 void init_dfa() {
00064 #ifndef NO_GARBAGE_COLLECTOR
00065     static Exp** gc_pointers = (Exp**) GC_MALLOC_UNCOLLECTABLE(2*sizeof(Exp*));
00066     gc_pointers[0] = scaledArrayPat;
00067     gc_pointers[1] = unscaledArrayPat;
00068 #endif
00069 }
00070 
00071 
00072 static int progress = 0;
00073 void UserProc::dfaTypeAnalysis() {
00074     Boomerang::get()->alert_decompile_debug_point(this, "before dfa type analysis");
00075 
00076     // First use the type information from the signature. Sometimes needed to split variables (e.g. argc as a
00077     // int and char* in sparc/switch_gcc)
00078     bool ch = signature->dfaTypeAnalysis(cfg);
00079     StatementList stmts;
00080     getStatements(stmts);
00081     StatementList::iterator it;
00082     int iter;
00083     for (iter = 1; iter <= DFA_ITER_LIMIT; iter++) {
00084         ch = false;
00085         for (it = stmts.begin(); it != stmts.end(); it++) {
00086             if (++progress >= 2000) {
00087                 progress = 0;
00088                 std::cerr << "t" << std::flush;
00089             }
00090             bool thisCh = false;
00091             (*it)->dfaTypeAnalysis(thisCh);
00092             if (thisCh) {
00093                 ch = true;
00094                 if (DEBUG_TA)
00095                     LOG << " caused change: " << *it << "\n";
00096             }
00097         }
00098         if (!ch)
00099             // No more changes: round robin algorithm terminates
00100             break;
00101     }
00102     if (ch)
00103         LOG << "### WARNING: iteration limit exceeded for dfaTypeAnalysis of procedure " << getName() << " ###\n";
00104 
00105     if (DEBUG_TA) {
00106         LOG << "\n ### results for data flow based type analysis for " << getName() << " ###\n";
00107         LOG << iter << " iterations\n";
00108         for (it = stmts.begin(); it != stmts.end(); it++) {
00109             Statement* s = *it;
00110             LOG << s << "\n";           // Print the statement; has dest type
00111             // Now print type for each constant in this Statement
00112             std::list<Const*> lc;
00113             std::list<Const*>::iterator cc;
00114             s->findConstants(lc);
00115             if (lc.size()) {
00116                 LOG << "       ";
00117                 for (cc = lc.begin(); cc != lc.end(); cc++)
00118                     LOG << (*cc)->getType()->getCtype() << " " << *cc << "  ";
00119                 LOG << "\n";
00120             }
00121             // If s is a call, also display its return types
00122             if (s->isCall()) {
00123                 CallStatement* call = (CallStatement*)s;
00124                 ReturnStatement* rs = call->getCalleeReturn();
00125                 if (rs == NULL) continue;
00126                 UseCollector* uc = call->getUseCollector();
00127                 ReturnStatement::iterator rr;
00128                 bool first = true;
00129                 for (rr = rs->begin(); rr != rs->end(); ++rr) {
00130                     // Intersect the callee's returns with the live locations at the call, i.e. make sure that they
00131                     // exist in *uc
00132                     Exp* lhs = ((Assignment*)*rr)->getLeft();
00133                     if (!uc->exists(lhs))
00134                         continue;               // Intersection fails
00135                     if (first)
00136                         LOG << "       returns: ";
00137                     else
00138                         LOG << ", ";
00139                     LOG << ((Assignment*)*rr)->getType()->getCtype() << " " << ((Assignment*)*rr)->getLeft();
00140                 }
00141                 LOG << "\n";
00142             }
00143         }
00144         LOG << "\n ### end results for Data flow based Type Analysis for " << getName() << " ###\n\n";
00145     }
00146 
00147     // Now use the type information gathered
00148 #if 0
00149     Boomerang::get()->alert_decompile_debug_point(this, "before mapping locals from dfa type analysis");
00150     if (DEBUG_TA)
00151         LOG << " ### mapping expressions to local variables for " << getName() << " ###\n";
00152     for (it = stmts.begin(); it != stmts.end(); it++) {
00153         Statement* s = *it;
00154         s->dfaMapLocals();
00155     }
00156     if (DEBUG_TA)
00157         LOG << " ### end mapping expressions to local variables for " << getName() << " ###\n";
00158 #endif
00159 
00160     Boomerang::get()->alert_decompile_debug_point(this, "before other uses of dfa type analysis");
00161 
00162     Prog* prog = getProg();
00163     for (it = stmts.begin(); it != stmts.end(); it++) {
00164         Statement* s = *it;
00165 
00166         // 1) constants
00167         std::list<Const*>lc;
00168         s->findConstants(lc);
00169         std::list<Const*>::iterator cc;
00170         for (cc = lc.begin(); cc != lc.end(); cc++) {
00171             Const* con = (Const*)*cc;
00172             Type* t = con->getType();
00173             int val = con->getInt();
00174             if (t && t->resolvesToPointer()) {
00175                 PointerType* pt = t->asPointer();
00176                 Type* baseType = pt->getPointsTo();
00177                 if (baseType->resolvesToChar()) {
00178                     // Convert to a string  MVE: check for read-only?
00179                     // Also, distinguish between pointer to one char, and ptr to many?
00180                     char* str = prog->getStringConstant(val, true);
00181                     if (str) {
00182                         // Make a string
00183                         con->setStr(str);
00184                         con->setOper(opStrConst);
00185                     }
00186                 } else if (baseType->resolvesToInteger() || baseType->resolvesToFloat() || baseType->resolvesToSize()) {
00187                     ADDRESS addr = (ADDRESS) con->getInt();
00188                     prog->globalUsed(addr, baseType);
00189                     const char *gloName = prog->getGlobalName(addr);
00190                     if (gloName) {
00191                         ADDRESS r = addr - prog->getGlobalAddr((char*)gloName);
00192                         Exp *ne;
00193                         if (r) {
00194                             Location *g = Location::global(strdup(gloName), this);
00195                             ne = Location::memOf(
00196                                 new Binary(opPlus,
00197                                     new Unary(opAddrOf, g),
00198                                     new Const(r)), this);
00199                         } else {
00200                             Type *ty = prog->getGlobalType((char*)gloName);
00201                             if (s->isAssign() && ((Assign*)s)->getType()) {
00202                                 int bits = ((Assign*)s)->getType()->getSize();
00203                                 if (ty == NULL || ty->getSize() == 0)
00204                                     prog->setGlobalType((char*)gloName, new IntegerType(bits));
00205                             }
00206                             Location *g = Location::global(strdup(gloName), this);
00207                             if (ty && ty->resolvesToArray()) 
00208                                 ne = new Binary(opArrayIndex, g, new Const(0));
00209                             else 
00210                                 ne = g;
00211                         }
00212                         Exp* memof = Location::memOf(con);
00213                         s->searchAndReplace(memof->clone(), ne);
00214                     }
00215                 } else if (baseType->resolvesToArray()) {
00216                     // We have found a constant in s which has type pointer to array of alpha. We can't get the parent
00217                     // of con, but we can find it with the pattern unscaledArrayPat.
00218                     std::list<Exp*> result;
00219                     s->searchAll(unscaledArrayPat, result);
00220                     for (std::list<Exp*>::iterator rr = result.begin(); rr != result.end(); rr++) {
00221                         // idx + K
00222                         Const* constK = (Const*)((Binary*)*rr)->getSubExp2();
00223                         // Note: keep searching till we find the pattern with this constant, since other constants may
00224                         // not be used as pointer to array type.
00225                         if (constK != con) continue;
00226                         ADDRESS K = (ADDRESS)constK->getInt();
00227                         Exp* idx = ((Binary*)*rr)->getSubExp1();
00228                         Exp* arr = new Unary(opAddrOf,
00229                             new Binary(opArrayIndex,
00230                                 Location::global(prog->getGlobalName(K), this),
00231                                 idx));
00232                         // Beware of changing expressions in implicit assignments... map can become invalid
00233                         bool isImplicit = s->isImplicit();
00234                         if (isImplicit)
00235                             cfg->removeImplicitAssign(((ImplicitAssign*)s)->getLeft());
00236                         s->searchAndReplace(unscaledArrayPat, arr);
00237                         // s will likely have an m[a[array]], so simplify
00238                         s->simplifyAddr();
00239                         if (isImplicit)
00240                             // Replace the implicit assignment entry. Note that s' lhs has changed
00241                             cfg->findImplicitAssign(((ImplicitAssign*)s)->getLeft());
00242                         // Ensure that the global is declared
00243                         // Ugh... I think that arrays and pointers to arrays are muddled!
00244                         prog->globalUsed(K, baseType);
00245                     }
00246                 }
00247             } else if (t->resolvesToFloat()) {
00248                 if (con->isIntConst()) {
00249                     // Reinterpret as a float (and convert to double)
00250                     //con->setFlt(reinterpret_cast<float>(con->getInt()));
00251                     int tmp = con->getInt();
00252                     con->setFlt(*(float*)&tmp);     // Reinterpret to float, then cast to double
00253                     con->setOper(opFltConst);
00254                     con->setType(new FloatType(64));
00255                 }
00256                 // MVE: more work if double?
00257             } else /* if (t->resolvesToArray()) */ {
00258                 prog->globalUsed(val, t);
00259             }
00260         }
00261 
00262         // 2) Search for the scaled array pattern and replace it with an array use m[idx*K1 + K2]
00263         std::list<Exp*> result;
00264         s->searchAll(scaledArrayPat, result);
00265         for (std::list<Exp*>::iterator rr = result.begin(); rr != result.end(); rr++) {
00266             //Type* ty = s->getTypeFor(*rr);
00267             // FIXME: should check that we use with array type...
00268             // Find idx and K2
00269             Exp* t = ((Unary*)(*rr)->getSubExp1());     // idx*K1 + K2
00270             Exp* l = ((Binary*)t)->getSubExp1();        // idx*K1
00271             Exp* r = ((Binary*)t)->getSubExp2();        // K2
00272             ADDRESS K2 = (ADDRESS)((Const*)r)->getInt();
00273             Exp* idx = ((Binary*)l)->getSubExp1();
00274             // Replace with the array expression
00275             const char* nam = prog->getGlobalName(K2);
00276             if (nam == NULL)
00277                 nam = prog->newGlobalName(K2);
00278             Exp* arr = new Binary(opArrayIndex,         // 
00279                 Location::global(nam, this),
00280                 idx);
00281             if (s->searchAndReplace(scaledArrayPat, arr)) {
00282                 if (s->isImplicit())
00283                     // Register an array of appropriate type
00284                     prog->globalUsed(K2, new ArrayType(((ImplicitAssign*)s)->getType()));
00285             }
00286         }
00287 
00288         // 3) Check implicit assigns for parameter and global types.
00289         if (s->isImplicit()) {
00290             Exp* lhs = ((ImplicitAssign*)s)->getLeft();
00291             Type* iType = ((ImplicitAssign*)s)->getType();
00292             // Note: parameters are not explicit any more
00293             //if (lhs->isParam()) { // }
00294             bool allZero;
00295             Exp* slhs = lhs->clone()->removeSubscripts(allZero);
00296             int i = signature->findParam(slhs);
00297             if (i != -1)
00298                 setParamType(i, iType);
00299             else if (lhs->isMemOf()) {
00300                 Exp* sub = ((Location*)lhs)->getSubExp1();
00301                 if (sub->isIntConst()) {
00302                     // We have a m[K] := -
00303                     int K = ((Const*)sub)->getInt();
00304                     prog->globalUsed(K, iType);
00305                 }
00306             } else if (lhs->isGlobal()) {
00307                 char* gname = ((Const*)((Location*)lhs)->getSubExp1())->getStr();
00308                 prog->setGlobalType(gname, iType);
00309             }
00310         }
00311 
00312         // 4) Add the locals (soon globals as well) to the localTable, to sort out the overlaps
00313         if (s->isTyping()) {
00314             Exp* addrExp = NULL;
00315             Type* typeExp = NULL;
00316             if (s->isAssignment()) {
00317                 Exp* lhs = ((Assignment*)s)->getLeft();
00318                 if (lhs->isMemOf()) {
00319                     addrExp = ((Location*)lhs)->getSubExp1();
00320                     typeExp = ((Assignment*)s)->getType();
00321                 }
00322             }
00323             else {
00324                 // Assume an implicit reference
00325                 addrExp = ((ImpRefStatement*)s)->getAddressExp();
00326                 if (addrExp->isTypedExp() && ((TypedExp*)addrExp)->getType()->resolvesToPointer())
00327                     addrExp = ((Unary*)addrExp)->getSubExp1();
00328                 typeExp = ((ImpRefStatement*)s)->getType();
00329                 // typeExp should be a pointer expression, or a union of pointer types
00330                 if (typeExp->resolvesToUnion())
00331                     typeExp = typeExp->asUnion()->dereferenceUnion();
00332                 else {
00333                     assert(typeExp->resolvesToPointer());
00334                     typeExp = typeExp->asPointer()->getPointsTo();
00335                 }
00336             }
00337             if (addrExp && signature->isAddrOfStackLocal(prog, addrExp)) {
00338                 int addr = 0;
00339                 if (addrExp->getArity() == 2 && signature->isOpCompatStackLocal(addrExp->getOper())) {
00340                     Const* K = (Const*) ((Binary*)addrExp)->getSubExp2();
00341                     if (K->isConst()) {
00342                         addr = K->getInt();
00343                         if (addrExp->getOper() == opMinus)
00344                             addr = -addr;
00345                     }
00346                 }
00347                 LOG << "in proc " << getName() << " adding addrExp " << addrExp << " to local table\n";
00348                 Type * ty = ((TypingStatement*)s)->getType();
00349                 localTable.addItem(addr, lookupSym(Location::memOf(addrExp), ty), typeExp);
00350             }
00351         }
00352     }
00353 
00354 
00355     if (VERBOSE) {
00356         LOG << "### after application of dfa type analysis for " << getName() << " ###\n";
00357         printToLog();
00358         LOG << "### end application of dfa type analysis for " << getName() << " ###\n";
00359     }
00360 
00361     Boomerang::get()->alert_decompile_debug_point(this, "after dfa type analysis");
00362 }
00363 
00364 // This is the core of the data-flow-based type analysis algorithm: implementing the meet operator.
00365 // In classic lattice-based terms, the TOP type is void; there is no BOTTOM type since we handle overconstraints with
00366 // unions.
00367 // Consider various pieces of knowledge about the types. There could be:
00368 // a) void: no information. Void meet x = x.
00369 // b) size only: find a size large enough to contain the two types.
00370 // c) broad type only, e.g. floating point
00371 // d) signedness, no size
00372 // e) size, no signedness
00373 // f) broad type, size, and (for integer broad type), signedness
00374 
00375 // ch set true if any change
00376 
00377 Type* VoidType::meetWith(Type* other, bool& ch, bool bHighestPtr) {
00378     // void meet x = x
00379     ch |= !other->resolvesToVoid();
00380     return other->clone();
00381 }
00382 
00383 Type* FuncType::meetWith(Type* other, bool& ch, bool bHighestPtr) {
00384     if (other->resolvesToVoid()) return this;
00385     if (*this == *other) return this;       // NOTE: at present, compares names as well as types and num parameters
00386     return createUnion(other, ch, bHighestPtr);
00387 }
00388 
00389 Type* IntegerType::meetWith(Type* other, bool& ch, bool bHighestPtr) {
00390     if (other->resolvesToVoid()) return this;
00391     if (other->resolvesToInteger()) {
00392         IntegerType* otherInt = other->asInteger();
00393         // Signedness
00394         int oldSignedness = signedness;
00395         if (otherInt->signedness > 0)
00396             signedness++;
00397         else if (otherInt->signedness < 0)
00398             signedness--;
00399         ch |= (signedness > 0 != oldSignedness > 0);        // Changed from signed to not necessarily signed
00400         ch |= (signedness < 0 != oldSignedness < 0);        // Changed from unsigned to not necessarily unsigned
00401         // Size. Assume 0 indicates unknown size
00402         unsigned oldSize = size;
00403         size = max(size, otherInt->size);
00404         ch |= (size != oldSize);
00405         return this;
00406     }
00407     if (other->resolvesToSize()) {
00408         if (size == 0) {        // Doubt this will ever happen
00409             size = ((SizeType*)other)->getSize();
00410             return this;
00411         }
00412         if (size == ((SizeType*)other)->getSize()) return this;
00413         LOG << "integer size " << size << " meet with SizeType size " << ((SizeType*)other)->getSize() << "!\n";
00414         unsigned oldSize = size;
00415         size = max(size, ((SizeType*)other)->getSize());
00416         ch = size != oldSize;
00417         return this;
00418     }
00419     return createUnion(other, ch, bHighestPtr);
00420 }
00421 
00422 Type* FloatType::meetWith(Type* other, bool& ch, bool bHighestPtr) {
00423     if (other->resolvesToVoid()) return this;
00424     if (other->resolvesToFloat()) {
00425         FloatType* otherFlt = other->asFloat();
00426         unsigned oldSize = size;
00427         size = max(size, otherFlt->size);
00428         ch |= size != oldSize;
00429         return this;
00430     }
00431     if (other->resolvesToSize()) {
00432         unsigned otherSize = other->getSize();
00433         ch |= size != otherSize;
00434         size = max(size, otherSize);
00435         return this;
00436     }
00437     return createUnion(other, ch, bHighestPtr);
00438 }
00439 
00440 Type* BooleanType::meetWith(Type* other, bool& ch, bool bHighestPtr) {
00441     if (other->resolvesToVoid()) return this;
00442     if (other->resolvesToBoolean())
00443         return this;
00444     return createUnion(other, ch, bHighestPtr);
00445 }
00446 
00447 Type* CharType::meetWith(Type* other, bool& ch, bool bHighestPtr) {
00448     if (other->resolvesToVoid()) return this;
00449     if (other->resolvesToChar()) return this;
00450     // Also allow char to merge with integer
00451     if (other->resolvesToInteger()) {
00452         ch = true;
00453         return other->clone();
00454     }
00455     if (other->resolvesToSize() && ((SizeType*)other)->getSize() == 8)
00456         return this;
00457     return createUnion(other, ch, bHighestPtr);
00458 }
00459 
00460 Type* PointerType::meetWith(Type* other, bool& ch, bool bHighestPtr) {
00461     if (other->resolvesToVoid()) return this;
00462     if (other->resolvesToSize() && ((SizeType*)other)->getSize() == STD_SIZE) return this;
00463     if (other->resolvesToPointer()) {
00464         PointerType* otherPtr = other->asPointer();
00465         if (pointsToAlpha() && !otherPtr->pointsToAlpha()) {
00466             setPointsTo(otherPtr->getPointsTo());
00467             ch = true;
00468         } else {
00469             // We have a meeting of two pointers.
00470             Type* thisBase = points_to;
00471             Type* otherBase = otherPtr->points_to;
00472             if (bHighestPtr) {
00473                 // We want the greatest type of thisBase and otherBase
00474                 if (thisBase->isSubTypeOrEqual(otherBase))
00475                     return other->clone();
00476                 if (otherBase->isSubTypeOrEqual(thisBase))
00477                     return this;
00478                 // There may be another type that is a superset of this and other; for now return void*
00479                 return new PointerType(new VoidType);
00480             }
00481             // See if the base types will meet
00482             if (otherBase->resolvesToPointer()) {
00483 if (thisBase->resolvesToPointer() && thisBase->asPointer()->getPointsTo() == thisBase)
00484   std::cerr << "HACK! BAD POINTER 1\n";
00485 if (otherBase->resolvesToPointer() && otherBase->asPointer()->getPointsTo() == otherBase)
00486   std::cerr << "HACK! BAD POINTER 2\n";
00487 if (thisBase == otherBase)  // Note: compare pointers
00488   return this;              // Crude attempt to prevent stack overflow
00489                 if (*thisBase == *otherBase)
00490                     return this;
00491                 if (pointerDepth() == otherPtr->pointerDepth()) {
00492                     Type* fType = getFinalPointsTo();
00493                     if (fType->resolvesToVoid()) return other->clone();
00494                     Type* ofType = otherPtr->getFinalPointsTo();
00495                     if (ofType->resolvesToVoid()) return this;
00496                     if (*fType == *ofType) return this;
00497                 }
00498             }
00499             if (thisBase->isCompatibleWith(otherBase)) {
00500                 points_to = points_to->meetWith(otherBase, ch, bHighestPtr);
00501                 return this;
00502             }
00503             // The bases did not meet successfully. Union the pointers.
00504             return createUnion(other, ch, bHighestPtr);
00505         }
00506         return this;
00507     }
00508     // Would be good to understand class hierarchys, so we know if a* is the same as b* when b is a subclass of a
00509     return createUnion(other, ch, bHighestPtr);
00510 }
00511 
00512 Type* ArrayType::meetWith(Type* other, bool& ch, bool bHighestPtr) {
00513     if (other->resolvesToVoid()) return this;
00514     if (other->resolvesToArray()) {
00515         ArrayType* otherArr = other->asArray();
00516         Type* newBase = base_type->clone()->meetWith(otherArr->base_type, ch, bHighestPtr);
00517         if (*newBase != *base_type) {
00518             ch = true;
00519             // base_type = newBase;     // No: call setBaseType to adjust length
00520             setBaseType(newBase);
00521         }
00522         if (other->asArray()->getLength() < getLength()) {
00523             this->setLength(other->asArray()->getLength());
00524         }
00525         return this;
00526     }
00527     if (*base_type == *other)
00528         return this;
00529     // Needs work?
00530     return createUnion(other, ch, bHighestPtr);
00531 }
00532 
00533 Type* NamedType::meetWith(Type* other, bool& ch, bool bHighestPtr) {
00534     Type * rt = resolvesTo();
00535     if (rt) {
00536         Type* ret = rt->meetWith(other, ch, bHighestPtr);
00537         if (ret == rt)
00538             return this;            // Retain the named type, much better than some compound type
00539         return ret;                 // Otherwise, whatever the result is
00540     }
00541     if (other->resolvesToVoid()) return this;
00542     if (*this == *other) return this;
00543     return createUnion(other, ch, bHighestPtr);
00544 }
00545 
00546 Type* CompoundType::meetWith(Type* other, bool& ch, bool bHighestPtr) {
00547     if (other->resolvesToVoid()) return this;
00548     if (!other->resolvesToCompound()) {
00549         if (types[0]->isCompatibleWith(other))
00550             // struct meet first element = struct
00551             return this;
00552         return createUnion(other, ch, bHighestPtr);
00553     }
00554     CompoundType* otherCmp = other->asCompound();
00555     if (otherCmp->isSuperStructOf(this)) {
00556         // The other structure has a superset of my struct's offsets. Preserve the names etc of the bigger struct.
00557         ch = true;
00558         return other;
00559     }
00560     if (isSubStructOf(otherCmp)) {
00561         // This is a superstruct of other
00562         ch = true;
00563         return this;
00564     }
00565     if (*this == *other) return this;
00566     // Not compatible structs. Create a union of both complete structs.
00567     // NOTE: may be possible to take advantage of some overlaps of the two structures some day.
00568     return createUnion(other, ch, bHighestPtr);
00569 }
00570 
00571 #define PRINT_UNION 0                                   // Set to 1 to debug unions to stderr
00572 #ifdef PRINT_UNION
00573 unsigned unionCount = 0;
00574 #endif
00575 
00576 Type* UnionType::meetWith(Type* other, bool& ch, bool bHighestPtr) {
00577     if (other->resolvesToVoid()) return this;
00578     std::list<UnionElement>::iterator it;
00579     if (other->resolvesToUnion()) {
00580         if (this == other)              // Note: pointer comparison
00581             return this;                // Avoid infinite recursion
00582         ch = true;
00583         UnionType* otherUnion = (UnionType*)other;
00584         // Always return this, never other, (even if other is larger than this) because otherwise iterators can become
00585         // invalid below
00586         for (it = otherUnion->li.begin(); it != otherUnion->li.end(); it++) {
00587             meetWith(it->type, ch, bHighestPtr);
00588             return this;
00589         }
00590     }
00591 
00592     // Other is a non union type
00593     if (other->resolvesToPointer() && other->asPointer()->getPointsTo() == this) {
00594         LOG << "WARNING! attempt to union " << getCtype() << " with pointer to self!\n";
00595         return this;
00596     }
00597     for (it = li.begin(); it != li.end(); it++) {
00598         Type* curr = it->type->clone();
00599         if (curr->isCompatibleWith(other)) {
00600             it->type = curr->meetWith(other, ch, bHighestPtr);
00601             return this;
00602         }
00603     }
00604 
00605     // Other is not compatible with any of my component types. Add a new type
00606     char name[20];
00607 #if PRINT_UNION                                         // Set above
00608     if (unionCount == 999)                              // Adjust the count to catch the one you want
00609         std::cerr << "createUnion breakpokint\n";       // Note: you need two breakpoints (also in Type::createUnion)
00610     std::cerr << "  " << ++unionCount << " Created union from " << getCtype() << " and " << other->getCtype();
00611 #endif
00612     sprintf(name, "x%d", ++nextUnionNumber);
00613     addType(other->clone(), name);
00614 #if PRINT_UNION
00615     std::cerr << ", result is " << getCtype() << "\n";
00616 #endif
00617     ch = true;
00618     return this;
00619 }
00620 
00621 Type* SizeType::meetWith(Type* other, bool& ch, bool bHighestPtr) {
00622     if (other->resolvesToVoid()) return this;
00623     if (other->resolvesToSize()) {
00624         if (((SizeType*)other)->size != size) {
00625             LOG << "size " << size << " meet with size " << ((SizeType*)other)->size << "!\n";
00626             unsigned oldSize = size;
00627             size = max(size, ((SizeType*)other)->size);
00628             ch = size != oldSize;
00629         }
00630         return this;
00631     }
00632     ch = true;
00633     if (other->resolvesToInteger() || other->resolvesToFloat() || other->resolvesToPointer()) {
00634         if (other->getSize() == 0) {
00635             other->setSize(size);
00636             return other->clone();
00637         }
00638         if (other->getSize() == size)
00639             return other->clone();
00640 LOG << "WARNING: size " << size << " meet with " << other->getCtype() << "; allowing temporarily\n";
00641 return other->clone();
00642     }
00643     return createUnion(other, ch, bHighestPtr);
00644 }
00645 
00646 Type* UpperType::meetWith(Type* other, bool& ch, bool bHighestPtr) {
00647     if (other->resolvesToVoid()) return this;
00648     if (other->resolvesToUpper()) {
00649         UpperType* otherUpp = other->asUpper();
00650         Type* newBase = base_type->clone()->meetWith(otherUpp->base_type, ch, bHighestPtr);
00651         if (*newBase != *base_type) {
00652             ch = true;
00653             base_type = newBase;
00654         }
00655         return this;
00656     }
00657     // Needs work?
00658     return createUnion(other, ch, bHighestPtr);
00659 }
00660 
00661 Type* LowerType::meetWith(Type* other, bool& ch, bool bHighestPtr) {
00662     if (other->resolvesToVoid()) return this;
00663     if (other->resolvesToUpper()) {
00664         LowerType* otherLow = other->asLower();
00665         Type* newBase = base_type->clone()->meetWith(otherLow->base_type, ch, bHighestPtr);
00666         if (*newBase != *base_type) {
00667             ch = true;
00668             base_type = newBase;
00669         }
00670         return this;
00671     }
00672     // Needs work?
00673     return createUnion(other, ch, bHighestPtr);
00674 }
00675 
00676 Type* Statement::meetWithFor(Type* ty, Exp* e, bool& ch) {
00677     bool thisCh = false;
00678     Type* newType = getTypeFor(e)->meetWith(ty, thisCh);
00679     if (thisCh) {
00680         ch = true;
00681         setTypeFor(e, newType->clone());
00682     }
00683     return newType;
00684 }
00685 
00686 Type* Type::createUnion(Type* other, bool& ch, bool bHighestPtr /* = false */) {
00687 
00688     assert(!resolvesToUnion());                                     // `this' should not be a UnionType
00689     if (other->resolvesToUnion())
00690         return other->meetWith(this, ch, bHighestPtr)->clone();     // Put all the hard union logic in one place
00691     // Check for anytype meet compound with anytype as first element
00692     if (other->resolvesToCompound()) {
00693         CompoundType* otherComp = other->asCompound();
00694         Type* firstType = otherComp->getType((unsigned)0);
00695         if (firstType->isCompatibleWith(this))
00696             // struct meet first element = struct
00697             return other->clone();
00698     }
00699     // Check for anytype meet array of anytype
00700     if (other->resolvesToArray()) {
00701         ArrayType* otherArr = other->asArray();
00702         Type* elemTy = otherArr->getBaseType();
00703         if (elemTy->isCompatibleWith(this))
00704             // array meet element = array
00705             return other->clone();
00706     }
00707 
00708     char name[20];
00709 #if PRINT_UNION
00710     if (unionCount == 999)                              // Adjust the count to catch the one you want
00711         std::cerr << "createUnion breakpokint\n";       // Note: you need two breakpoints (also in UnionType::meetWith)
00712 #endif
00713     sprintf(name, "x%d", ++nextUnionNumber);
00714     UnionType* u = new UnionType;
00715     u->addType(this->clone(), name);
00716     sprintf(name, "x%d", ++nextUnionNumber);
00717     u->addType(other->clone(), name);
00718     ch = true;
00719 #if PRINT_UNION
00720     std::cerr << "  " << ++unionCount << " Created union from " << getCtype() << " and " << other->getCtype() <<
00721         ", result is " << u->getCtype() << "\n";
00722 #endif
00723     return u;
00724 }
00725 
00726 
00727 void CallStatement::dfaTypeAnalysis(bool& ch) {
00728     // Iterate through the arguments
00729     StatementList::iterator aa;
00730     int n = 0;
00731     for (aa = arguments.begin(); aa != arguments.end(); ++aa, ++n) {
00732         if (procDest && procDest->getSignature()->getParamBoundMax(n) && ((Assign*)*aa)->getRight()->isIntConst()) {
00733             Assign *a = (Assign*)*aa;
00734             std::string boundmax = procDest->getSignature()->getParamBoundMax(n);
00735             assert(a->getType()->resolvesToInteger());
00736             StatementList::iterator aat;
00737             int nt = 0;
00738             for (aat = arguments.begin(); aat != arguments.end(); ++aat, ++nt)
00739                 if (boundmax == procDest->getSignature()->getParamName(nt)) {
00740                     Type *tyt = ((Assign*)*aat)->getType();
00741                     if (tyt->resolvesToPointer() && tyt->asPointer()->getPointsTo()->resolvesToArray() && tyt->asPointer()->getPointsTo()->asArray()->isUnbounded())
00742                         tyt->asPointer()->getPointsTo()->asArray()->setLength(((Const*)a->getRight())->getInt());
00743                     break;
00744                 }
00745         }
00746         // The below will ascend type, meet type with that of arg, and descend type. Note that the type of the assign
00747         // will already be that of the signature, if this is a library call, from updateArguments()
00748         ((Assign*)*aa)->dfaTypeAnalysis(ch);
00749     }
00750     // The destination is a pointer to a function with this function's signature (if any)
00751     if (pDest) {
00752         if (signature)
00753             pDest->descendType(new FuncType(signature), ch, this);
00754         else if (procDest)
00755             pDest->descendType(new FuncType(procDest->getSignature()), ch, this);
00756     }
00757 }
00758 
00759 void ReturnStatement::dfaTypeAnalysis(bool& ch) {
00760     StatementList::iterator mm, rr;
00761     for (mm = modifieds.begin(); mm != modifieds.end(); ++mm) {
00762         ((Assign*)*mm)->dfaTypeAnalysis(ch);
00763     }
00764     for (rr = returns.begin(); rr != returns.end(); ++rr) {
00765         ((Assign*)*rr)->dfaTypeAnalysis(ch);
00766     }
00767 }
00768 
00769 // For x0 := phi(x1, x2, ...) want
00770 // Tx0 := Tx0 meet (Tx1 meet Tx2 meet ...)
00771 // Tx1 := Tx1 meet Tx0
00772 // Tx2 := Tx2 meet Tx0
00773 // ...
00774 void PhiAssign::dfaTypeAnalysis(bool& ch) {
00775     iterator it = defVec.begin();
00776     while (it->e == NULL && it != defVec.end())
00777         ++it;
00778     assert(it != defVec.end());
00779     Type* meetOfArgs = it->def->getTypeFor(lhs);
00780     for (++it; it != defVec.end(); it++) {
00781         if (it->e == NULL) continue;
00782         assert(it->def);
00783         Type* typeOfDef = it->def->getTypeFor(it->e);
00784         meetOfArgs = meetOfArgs->meetWith(typeOfDef, ch);
00785     }
00786     type = type->meetWith(meetOfArgs, ch);
00787     for (it = defVec.begin(); it != defVec.end(); it++) {
00788         if (it->e == NULL) continue;
00789         it->def->meetWithFor(type, it->e, ch);
00790     }
00791     Assignment::dfaTypeAnalysis(ch);            // Handle the LHS
00792 }
00793 
00794 void Assign::dfaTypeAnalysis(bool& ch) {
00795     Type* tr = rhs->ascendType();
00796     type = type->meetWith(tr, ch, true);    // Note: bHighestPtr is set true, since the lhs could have a greater type
00797                                             // (more possibilities) than the rhs. Example: pEmployee = pManager.
00798     rhs->descendType(type, ch, this);       // This will effect rhs = rhs MEET lhs
00799     Assignment::dfaTypeAnalysis(ch);        // Handle the LHS wrt m[] operands
00800 }
00801 
00802 void Assignment::dfaTypeAnalysis(bool& ch) {
00803     Signature* sig = proc->getSignature();
00804     // Don't do this for the common case of an ordinary local, since it generates hundreds of implicit references,
00805     // without any new type information
00806     if (lhs->isMemOf() && !sig->isStackLocal(proc->getProg(), lhs)) {
00807         Exp* addr = ((Unary*)lhs)->getSubExp1();
00808         // Meet the assignment type with *(type of the address)
00809         Type* addrType = addr->ascendType();
00810         Type* memofType;
00811         if (addrType->resolvesToPointer())
00812             memofType = addrType->asPointer()->getPointsTo();
00813         else
00814             memofType = new VoidType;
00815         type = type->meetWith(memofType, ch);
00816         // Push down the fact that the memof operand is a pointer to the assignment type
00817         addrType = new PointerType(type);
00818         addr->descendType(addrType, ch, this);
00819     }
00820 }
00821 
00822 void BranchStatement::dfaTypeAnalysis(bool& ch) {
00823     if (pCond)
00824         pCond->descendType(new BooleanType(), ch, this);
00825     // Not fully implemented yet?
00826 }
00827 
00828 void ImplicitAssign::dfaTypeAnalysis(bool& ch) {
00829     Assignment::dfaTypeAnalysis(ch);
00830 }
00831 
00832 void BoolAssign::dfaTypeAnalysis(bool& ch) {
00833     // Not properly implemented yet
00834     Assignment::dfaTypeAnalysis(ch);
00835 }
00836 
00837 // Special operators for handling addition and subtraction in a data flow based type analysis
00838 //                  ta=
00839 //  tb=     alpha*  int     pi
00840 // beta*    bottom  void*   void*
00841 // int      void*   int     pi
00842 // pi       void*   pi      pi
00843 Type* sigmaSum(Type* ta, Type* tb) {
00844     bool ch;
00845     if (ta->resolvesToPointer()) {
00846         if (tb->resolvesToPointer())
00847             return ta->createUnion(tb, ch);
00848         return new PointerType(new VoidType);
00849     }
00850     if (ta->resolvesToInteger()) {
00851         if (tb->resolvesToPointer())
00852             return new PointerType(new VoidType);
00853         return tb->clone();
00854     }
00855     if (tb->resolvesToPointer())
00856         return new PointerType(new VoidType);
00857     return ta->clone();
00858 }
00859 
00860 
00861 //                  tc=
00862 //  to=     beta*   int     pi
00863 // alpha*   int     bottom  int
00864 // int      void*   int     pi
00865 // pi       pi      pi      pi
00866 Type* sigmaAddend(Type* tc, Type* to) {
00867     bool ch;
00868     if (tc->resolvesToPointer()) {
00869         if (to->resolvesToPointer())
00870             return new IntegerType;
00871         if (to->resolvesToInteger())
00872             return new PointerType(new VoidType);
00873         return to->clone();
00874     }
00875     if (tc->resolvesToInteger()) {
00876         if (to->resolvesToPointer())
00877             return tc->createUnion(to, ch);
00878         return to->clone();
00879     }
00880     if (to->resolvesToPointer())
00881         return new IntegerType;
00882     return tc->clone();
00883 }
00884 
00885 //                  tc=
00886 //  tb=     beta*   int     pi
00887 // alpha*   bottom  void*   void*
00888 // int      void*   int     pi
00889 // pi       void*   int     pi
00890 Type* deltaMinuend(Type* tc, Type* tb) {
00891     bool ch;
00892     if (tc->resolvesToPointer()) {
00893         if (tb->resolvesToPointer())
00894             return tc->createUnion(tb, ch);
00895         return new PointerType(new VoidType);
00896     }
00897     if (tc->resolvesToInteger()) {
00898         if (tb->resolvesToPointer())
00899             return new PointerType(new VoidType);
00900         return tc->clone();
00901     }
00902     if (tb->resolvesToPointer())
00903         return new PointerType(new VoidType);
00904     return tc->clone();
00905 }
00906 
00907 //                  tc=
00908 //  ta=     beta*   int     pi
00909 // alpha*   int     void*   pi
00910 // int      bottom  int     int
00911 // pi       int     pi      pi
00912 Type* deltaSubtrahend(Type* tc, Type* ta) {
00913     bool ch;
00914     if (tc->resolvesToPointer()) {
00915         if (ta->resolvesToPointer())
00916             return new IntegerType;
00917         if (ta->resolvesToInteger())
00918             return tc->createUnion(ta, ch);
00919         return new IntegerType;
00920     }
00921     if (tc->resolvesToInteger())
00922         if (ta->resolvesToPointer())
00923             return new PointerType(new VoidType);
00924         return ta->clone();
00925     if (ta->resolvesToPointer())
00926         return tc->clone();
00927     return ta->clone();
00928 }
00929 
00930 //                  ta=
00931 //  tb=     alpha*  int     pi
00932 // beta*    int     bottom  int
00933 // int      void*   int     pi
00934 // pi       pi      int     pi
00935 Type* deltaDifference(Type* ta, Type* tb) {
00936     bool ch;
00937     if (ta->resolvesToPointer()) {
00938         if (tb->resolvesToPointer())
00939             return new IntegerType;
00940         if (tb->resolvesToInteger())
00941             return new PointerType(new VoidType);
00942         return tb->clone();
00943     }
00944     if (ta->resolvesToInteger()) {
00945         if (tb->resolvesToPointer())
00946             return ta->createUnion(tb, ch);
00947         return new IntegerType;
00948     }
00949     if (tb->resolvesToPointer())
00950         return new IntegerType;
00951     return ta->clone();
00952 }
00953 
00954 //  //  //  //  //  //  //  //  //  //  //
00955 //                                      //
00956 //  ascendType: draw type information   //
00957 //      up the expression tree          //
00958 //                                      //
00959 //  //  //  //  //  //  //  //  //  //  //
00960 
00961 Type* Binary::ascendType() {
00962     if (op == opFlagCall) return new VoidType;
00963     Type* ta = subExp1->ascendType();
00964     Type* tb = subExp2->ascendType();
00965     switch (op) {
00966         case opPlus:
00967             return sigmaSum(ta, tb);
00968             // Do I need to check here for Array* promotion? I think checking in descendType is enough
00969         case opMinus:
00970             return deltaDifference(ta, tb);
00971         case opMult: case opDiv:
00972             return new IntegerType(ta->getSize(), -1);
00973         case opMults: case opDivs: case opShiftRA:
00974             return new IntegerType(ta->getSize(), +1);
00975         case opBitAnd: case opBitOr: case opBitXor: case opShiftR: case opShiftL:
00976             return new IntegerType(ta->getSize(), 0);
00977         case opLess:    case opGtr:     case opLessEq:      case opGtrEq:
00978         case opLessUns: case opGtrUns:  case opLessEqUns:   case opGtrEqUns:
00979             return new BooleanType();
00980         default:
00981             // Many more cases to implement
00982             return new VoidType;
00983     }
00984 }
00985 
00986 // Constants and subscripted locations are at the leaves of the expression tree. Just return their stored types.
00987 Type* RefExp::ascendType() {
00988     if (def == NULL) {
00989         std::cerr << "Warning! Null reference in " << this << "\n";
00990         return new VoidType;
00991     }
00992     return def->getTypeFor(subExp1);
00993 }
00994 Type* Const::ascendType() {
00995     if (type->resolvesToVoid()) {
00996         switch (op) {
00997             case opIntConst:
00998 // could be anything, Boolean, Character, we could be bit fiddling pointers for all we know - trentw
00999 #if 0
01000                 if (u.i != 0 && (u.i < 0x1000 && u.i > -0x100))
01001                     // Assume that small nonzero integer constants are of integer type (can't be pointers)
01002                     // But note that you can't say anything about sign; these are bit patterns, not HLL constants
01003                     // (e.g. all ones could be signed -1 or unsigned 0xFFFFFFFF)
01004                     type = new IntegerType(STD_SIZE, 0);
01005 #endif
01006                 break;
01007             case opLongConst:
01008                 type = new IntegerType(STD_SIZE*2, 0);
01009                 break;
01010             case opFltConst:
01011                 type = new FloatType(64);
01012                 break;
01013             case opStrConst:
01014                 type = new PointerType(new CharType);
01015                 break;
01016             case opFuncConst:
01017                 type = new FuncType;        // More needed here?
01018                 break;
01019             default:
01020                 assert(0);                  // Bad Const
01021         }
01022     }
01023     return type;
01024 }
01025 // Can also find various terminals at the leaves of an expression tree
01026 Type* Terminal::ascendType() {
01027     switch (op) {
01028         case opPC:
01029             return new IntegerType(STD_SIZE, -1);
01030         case opCF: case opZF:
01031             return new BooleanType;
01032         case opDefineAll:
01033             return new VoidType;
01034         case opFlags:
01035             return new IntegerType(STD_SIZE, -1);
01036         default:
01037             std::cerr << "ascendType() for terminal " << this << " not implemented!\n";
01038             return new VoidType;
01039     }
01040 }
01041 
01042 Type* Unary::ascendType() {
01043     Type* ta = subExp1->ascendType();
01044     switch (op) {
01045         case opMemOf:
01046             if (ta->resolvesToPointer())
01047                 return ta->asPointer()->getPointsTo();
01048             else
01049                 return new VoidType();      // NOT SURE! Really should be bottom
01050             break;
01051         case opAddrOf:
01052             return new PointerType(ta);
01053             break;
01054         default:
01055             break;
01056     }
01057     return new VoidType;
01058 }
01059 
01060 Type* Ternary::ascendType() {
01061     switch (op) {
01062         case opFsize:
01063             return new FloatType(((Const*)subExp2)->getInt());
01064         case opZfill: case opSgnEx: {
01065             int toSize = ((Const*)subExp2)->getInt();
01066             return Type::newIntegerLikeType(toSize, op==opZfill ? -1 : 1);
01067         }
01068 
01069         default:
01070             break;
01071     }
01072     return new VoidType;
01073 }
01074 
01075 Type* TypedExp::ascendType() {
01076     return type;
01077 }
01078 
01079 
01080 //  //  //  //  //  //  //  //  //  //  //
01081 //                                      //
01082 //  descendType: push type information  //
01083 //      down the expression tree        //
01084 //                                      //
01085 //  //  //  //  //  //  //  //  //  //  //
01086 
01087 void Binary::descendType(Type* parentType, bool& ch, Statement* s) {
01088     if (op == opFlagCall) return;
01089     Type* ta = subExp1->ascendType();
01090     Type* tb = subExp2->ascendType();
01091     Type* nt;                           // "New" type for certain operators
01092     // The following is an idea of Mike's that is not yet implemented well. It is designed to handle the situation
01093     // where the only reference to a local is where its address is taken. In the current implementation, it incorrectly
01094     // triggers with every ordinary local reference, causing esp to appear used in the final program
01095 #if 0
01096     Signature* sig = s->getProc()->getSignature();
01097     Prog* prog = s->getProc()->getProg();
01098     if (parentType->resolvesToPointer() && !parentType->asPointer()->getPointsTo()->resolvesToVoid() &&
01099             sig->isAddrOfStackLocal(prog, this)) {
01100         // This is the address of some local. What I used to do is to make an implicit assignment for the local, and
01101         // try to meet with the real assignment later. But this had some problems. Now, make an implicit *reference*
01102         // to the specified address; this should eventually meet with the main assignment(s).
01103         s->getProc()->setImplicitRef(s, this, parentType);
01104     }
01105 #endif
01106     switch (op) {
01107         case opPlus:
01108             ta = ta->meetWith(sigmaAddend(parentType, tb), ch);
01109             subExp1->descendType(ta, ch, s);
01110             tb = tb->meetWith(sigmaAddend(parentType, ta), ch);
01111             subExp2->descendType(tb, ch, s);
01112             break;
01113         case opMinus:
01114             ta = ta->meetWith(deltaMinuend(parentType, tb), ch);
01115             subExp1->descendType(ta, ch, s);
01116             tb = tb->meetWith(deltaSubtrahend(parentType, ta), ch);
01117             subExp2->descendType(tb, ch, s);
01118             break;
01119         case opGtrUns:  case opLessUns:
01120         case opGtrEqUns:case opLessEqUns: {
01121             nt = new IntegerType(ta->getSize(), -1);            // Used as unsigned
01122             ta = ta->meetWith(nt, ch);
01123             tb = tb->meetWith(nt, ch);
01124             subExp1->descendType(ta, ch, s);
01125             subExp2->descendType(tb, ch, s);
01126             break;
01127         }
01128         case opGtr: case opLess:
01129         case opGtrEq:case opLessEq: {
01130             nt = new IntegerType(ta->getSize(), +1);            // Used as signed
01131             ta = ta->meetWith(nt, ch);
01132             tb = tb->meetWith(nt, ch);
01133             subExp1->descendType(ta, ch, s);
01134             subExp2->descendType(tb, ch, s);
01135             break;
01136         }
01137         case opBitAnd: case opBitOr: case opBitXor: case opShiftR: case opShiftL:
01138         case opMults: case opDivs: case opShiftRA:
01139         case opMult: case opDiv: {
01140             int signedness;
01141             switch (op) {
01142                 case opBitAnd: case opBitOr: case opBitXor: case opShiftR: case opShiftL:
01143                     signedness = 0; break;
01144                 case opMults: case opDivs: case opShiftRA:
01145                     signedness = 1; break;
01146                 case opMult: case opDiv:
01147                     signedness = -1; break;
01148                 default:
01149                     signedness = 0; break;      // Unknown signedness
01150             }
01151 
01152             int parentSize = parentType->getSize();
01153             ta = ta->meetWith(new IntegerType(parentSize, signedness), ch);
01154             subExp1->descendType(ta, ch, s);
01155             if (op == opShiftL || op == opShiftR || op == opShiftRA)
01156                 // These operators are not symmetric; doesn't force a signedness on the second operand
01157                 // FIXME: should there be a gentle bias twowards unsigned? Generally, you can't shift by negative
01158                 // amounts.
01159                 signedness = 0;
01160             tb = tb->meetWith(new IntegerType(parentSize, signedness), ch);
01161             subExp2->descendType(tb, ch, s);
01162             break;
01163         }
01164         default:
01165             // Many more cases to implement
01166             break;
01167     }
01168 }
01169 
01170 void RefExp::descendType(Type* parentType, bool& ch, Statement* s) {
01171     Type* newType = def->meetWithFor(parentType, subExp1, ch);
01172     // In case subExp1 is a m[...]
01173     subExp1->descendType(newType, ch, s);
01174 }
01175 
01176 void Const::descendType(Type* parentType, bool& ch, Statement* s) {
01177     bool thisCh;
01178     type = type->meetWith(parentType, thisCh);
01179     ch |= thisCh;
01180     if (thisCh) {
01181         // May need to change the representation
01182         if (type->resolvesToFloat()) {
01183             if (op == opIntConst) {
01184                 op = opFltConst;
01185                 type = new FloatType(64);
01186                 float f = *(float*)&u.i;
01187                 u.d = (double)f;
01188             }
01189             else if (op == opLongConst) {
01190                 op = opFltConst;
01191                 type = new FloatType(64);
01192                 double d = *(double*)&u.ll;
01193                 u.d = d;
01194             }
01195         }
01196         // May be other cases
01197     }
01198 }
01199 
01200 void Unary::descendType(Type* parentType, bool& ch, Statement* s) {
01201     switch (op) {
01202         case opMemOf:
01203             // Check for m[x*K1 + K2]: array with base K2 and stride K1
01204             if (subExp1->getOper() == opPlus &&
01205                     ((Binary*)subExp1)->getSubExp1()->getOper() == opMult &&
01206                     ((Binary*)subExp1)->getSubExp2()->isIntConst() &&
01207                     ((Binary*)((Binary*)subExp1)->getSubExp1())->getSubExp2()->isIntConst()) {
01208                 Exp* leftOfPlus = ((Binary*)subExp1)->getSubExp1();
01209                 // We would expect the stride to be the same size as the base type
01210                 unsigned stride =  ((Const*)((Binary*)leftOfPlus)->getSubExp2())->getInt();
01211                 if (DEBUG_TA && stride*8 != parentType->getSize())
01212                     LOG << "type WARNING: apparent array reference at " << this << " has stride " << stride*8 <<
01213                         " bits, but parent type " << parentType->getCtype() << " has size " <<
01214                         parentType->getSize() << "\n";
01215                 // The index is integer type
01216                 Exp* x = ((Binary*)leftOfPlus)->getSubExp1();
01217                 x->descendType(new IntegerType(parentType->getSize(), 0), ch, s);
01218                 // K2 is of type <array of parentType>
01219                 Const* constK2 = (Const*)((Binary*)subExp1)->getSubExp2();
01220                 ADDRESS intK2 = (ADDRESS)constK2->getInt();
01221                 Prog* prog = s->getProc()->getProg();
01222                 constK2->descendType(prog->makeArrayType(intK2, parentType), ch, s);
01223             }
01224             else if (subExp1->getOper() == opPlus &&
01225                     ((Binary*)subExp1)->getSubExp1()->isSubscript() &&
01226                     ((RefExp*)((Binary*)subExp1)->getSubExp1())->isLocation() &&
01227                     ((Binary*)subExp1)->getSubExp2()->isIntConst()) {
01228                 // m[l1 + K]
01229                 Location* l1 = (Location*)((RefExp*)((Binary*)subExp1)->getSubExp1());
01230                 Type* l1Type = l1->ascendType();
01231                 int K = ((Const*)((Binary*)subExp1)->getSubExp2())->getInt();
01232                 if (l1Type->resolvesToPointer()) {
01233                     // This is a struct reference m[ptr + K]; ptr points to the struct and K is an offset into it
01234                     // First find out if we already have struct information
01235                     if (l1Type->asPointer()->resolvesToCompound()) {
01236                         CompoundType* ct = l1Type->asPointer()->asCompound();
01237                         if (ct->isGeneric())
01238                             ct->updateGenericMember(K, parentType, ch);
01239                         else
01240                             // would like to force a simplify here; I guess it will happen soon enough
01241                             ;
01242                     } else {
01243                         // Need to create a generic stuct with a least one member at offset K
01244                         CompoundType* ct = new CompoundType(true);
01245                         ct->updateGenericMember(K, parentType, ch);
01246                     }
01247                 }
01248                 else {
01249                     // K must be the pointer, so this is a global array
01250                     // FIXME: finish this case
01251                 }
01252             // FIXME: many other cases
01253             }
01254             else
01255                 subExp1->descendType(new PointerType(parentType), ch, s);
01256             break;
01257         case opAddrOf:
01258             if (parentType->resolvesToPointer())
01259                 subExp1->descendType(parentType->asPointer()->getPointsTo(), ch, s);
01260             break;
01261         case opGlobal: {
01262             Prog* prog = s->getProc()->getProg();
01263             char* name = ((Const*)subExp1)->getStr();
01264             Type* ty = prog->getGlobalType(name);
01265             ty = ty->meetWith(parentType, ch);
01266             prog->setGlobalType(name, ty);
01267             break;
01268         }
01269         default:
01270             break;
01271     }
01272 }
01273 
01274 void Ternary::descendType(Type* parentType, bool& ch, Statement* s) {
01275     switch (op) {
01276         case opFsize:
01277             subExp3->descendType(new FloatType(((Const*)subExp1)->getInt()), ch, s);
01278             break;
01279         case opZfill: case opSgnEx: {
01280             int fromSize = ((Const*)subExp1)->getInt();
01281             Type* fromType;
01282             fromType = Type::newIntegerLikeType(fromSize, op == opZfill ? -1 : 1);
01283             subExp3->descendType(fromType, ch, s);
01284             break;
01285         }
01286 
01287         default:
01288             break;
01289     }
01290 }
01291 
01292 void TypedExp::descendType(Type* parentType, bool& ch, Statement* s) {
01293 }
01294 
01295 void Terminal::descendType(Type* parentType, bool& ch, Statement* s) {
01296 }
01297 
01298 bool Signature::dfaTypeAnalysis(Cfg* cfg) {
01299     bool ch = false;
01300     std::vector<Parameter*>::iterator it;
01301     for (it = params.begin(); it != params.end(); it++) {
01302         // Parameters should be defined in an implicit assignment
01303         Statement* def = cfg->findImplicitParamAssign(*it);
01304         if (def) {          // But sometimes they are not used, and hence have no implicit definition
01305             bool thisCh = false;
01306             def->meetWithFor((*it)->getType(), (*it)->getExp(), thisCh);
01307             if (thisCh) {
01308                 ch = true;
01309                 if (DEBUG_TA)
01310                     LOG << "  sig caused change: " << (*it)->getType()->getCtype() << " " << (*it)->getName() << "\n";
01311             }
01312         }
01313     }
01314     return ch;
01315 }
01316 
01317 
01318 // Note: to prevent infinite recursion, CompoundType, ArrayType, and UnionType implement this function as a delegation
01319 // to isCompatible()
01320 bool Type::isCompatibleWith(Type* other, bool all /* = false */) {
01321     if (other->resolvesToCompound() ||
01322         other->resolvesToArray() ||
01323         other->resolvesToUnion())
01324             return other->isCompatible(this, all);
01325     return isCompatible(other, all);
01326 }
01327 
01328 bool VoidType::isCompatible(Type* other, bool all) {
01329     return true;        // Void is compatible with any type
01330 }
01331 
01332 bool SizeType::isCompatible(Type* other, bool all) {
01333     if (other->resolvesToVoid()) return true;
01334     unsigned otherSize = other->getSize();
01335     if (other->resolvesToFunc()) return false;
01336     // FIXME: why is there a test for size 0 here?
01337     if (otherSize == size || otherSize == 0) return true;
01338     if (other->resolvesToUnion()) return other->isCompatibleWith(this);
01339     if (other->resolvesToArray()) return isCompatibleWith(((ArrayType*)other)->getBaseType());
01340     //return false;
01341     // For now, size32 and double will be considered compatible (helps test/pentium/global2)
01342 return true;
01343 }
01344 
01345 bool IntegerType::isCompatible(Type* other, bool all) {
01346     if (other->resolvesToVoid()) return true;
01347     if (other->resolvesToInteger()) return true;
01348     if (other->resolvesToChar()) return true;
01349     if (other->resolvesToUnion()) return other->isCompatibleWith(this);
01350     if (other->resolvesToSize() && ((SizeType*)other)->getSize() == size) return true;
01351     return false;
01352 }
01353 
01354 bool FloatType::isCompatible(Type* other, bool all) {
01355     if (other->resolvesToVoid()) return true;
01356     if (other->resolvesToFloat()) return true;
01357     if (other->resolvesToUnion()) return other->isCompatibleWith(this);
01358     if (other->resolvesToArray()) return isCompatibleWith(((ArrayType*)other)->getBaseType());
01359     if (other->resolvesToSize() && ((SizeType*)other)->getSize() == size) return true;
01360     return false;
01361 }
01362 
01363 bool CharType::isCompatible(Type* other, bool all) {
01364     if (other->resolvesToVoid()) return true;
01365     if (other->resolvesToChar()) return true;
01366     if (other->resolvesToInteger()) return true;
01367     if (other->resolvesToSize() && ((SizeType*)other)->getSize() == 8) return true;
01368     if (other->resolvesToUnion()) return other->isCompatibleWith(this);
01369     if (other->resolvesToArray()) return isCompatibleWith(((ArrayType*)other)->getBaseType());
01370     return false;
01371 }
01372 
01373 bool BooleanType::isCompatible(Type* other, bool all) {
01374     if (other->resolvesToVoid()) return true;
01375     if (other->resolvesToBoolean()) return true;
01376     if (other->resolvesToUnion()) return other->isCompatibleWith(this);
01377     if (other->resolvesToSize() && ((SizeType*)other)->getSize() == 1) return true;
01378     return false;
01379 }
01380 
01381 bool FuncType::isCompatible(Type* other, bool all) {
01382     assert(signature);
01383     if (other->resolvesToVoid()) return true;
01384     if (*this == *other) return true;       // MVE: should not compare names!
01385     if (other->resolvesToUnion()) return other->isCompatibleWith(this);
01386     if (other->resolvesToSize() && ((SizeType*)other)->getSize() == STD_SIZE) return true;  
01387     if (other->resolvesToFunc()) {
01388         assert(other->asFunc()->signature);
01389         if (*other->asFunc()->signature == *signature) return true;
01390     }
01391     return false;
01392 }
01393 
01394 bool PointerType::isCompatible(Type* other, bool all) {
01395     if (other->resolvesToVoid()) return true;
01396     if (other->resolvesToUnion()) return other->isCompatibleWith(this);
01397     if (other->resolvesToSize() && ((SizeType*)other)->getSize() == STD_SIZE) return true;
01398     if (!other->resolvesToPointer()) return false;
01399     return points_to->isCompatibleWith(other->asPointer()->points_to);
01400 }
01401 
01402 bool NamedType::isCompatible(Type* other, bool all) {
01403     if (other->isNamed() && name == ((NamedType*)other)->getName())
01404         return true;
01405     Type* resTo = resolvesTo();
01406     if (resTo)
01407         return resolvesTo()->isCompatibleWith(other);
01408     if (other->resolvesToVoid()) return true;
01409     return (*this == *other);
01410 }
01411 
01412 bool ArrayType::isCompatible(Type* other, bool all) {
01413     if (other->resolvesToVoid()) return true;
01414     if (other->resolvesToArray() && base_type->isCompatibleWith(other->asArray()->base_type)) return true;
01415     if (other->resolvesToUnion()) return other->isCompatibleWith(this);
01416     if (!all && base_type->isCompatibleWith(other)) return true;        // An array of x is compatible with x
01417     return false;
01418 }
01419 
01420 bool UnionType::isCompatible(Type* other, bool all) {
01421     if (other->resolvesToVoid()) return true;
01422     std::list<UnionElement>::iterator it;
01423     if (other->resolvesToUnion()) {
01424         if (this == other)              // Note: pointer comparison
01425             return true;                // Avoid infinite recursion
01426         UnionType* otherUnion = (UnionType*)other;
01427         // Unions are compatible if one is a subset of the other
01428         if (li.size() < otherUnion->li.size()) {
01429             for (it = li.begin(); it != li.end(); it++)
01430                 if (!otherUnion->isCompatible(it->type, all)) return false;
01431         }
01432         else {
01433             for (it = otherUnion->li.begin(); it != otherUnion->li.end(); it++)
01434                 if (!isCompatible(it->type, all)) return false;
01435         }
01436         return true;
01437     }
01438     // Other is not a UnionType
01439     for (it = li.begin(); it != li.end(); it++)
01440         if (other->isCompatibleWith(it->type), all) return true;
01441     return false;
01442 }
01443 
01444 bool CompoundType::isCompatible(Type* other, bool all) {
01445     if (other->resolvesToVoid()) return true;
01446     if (other->resolvesToUnion()) return other->isCompatibleWith(this);
01447     if (!other->resolvesToCompound())
01448         // Used to always return false here. But in fact, a struct is compatible with its first member (if all is false)
01449         return !all && types[0]->isCompatibleWith(other);
01450     CompoundType* otherComp = other->asCompound();
01451     int n = otherComp->getNumTypes();
01452     if (n != (int)types.size()) return false;       // Is a subcompound compatible with a supercompound?
01453     for (int i=0; i < n; i++)
01454         if (!types[i]->isCompatibleWith(otherComp->types[i])) return false;
01455     return true;
01456 }
01457 
01458 bool UpperType::isCompatible(Type* other, bool all) {
01459     if (other->resolvesToVoid()) return true;
01460     if (other->resolvesToUpper() && base_type->isCompatibleWith(other->asUpper()->base_type)) return true;
01461     if (other->resolvesToUnion()) return other->isCompatibleWith(this);
01462     return false;
01463 }
01464 
01465 bool LowerType::isCompatible(Type* other, bool all) {
01466     if (other->resolvesToVoid()) return true;
01467     if (other->resolvesToLower() && base_type->isCompatibleWith(other->asLower()->base_type)) return true;
01468     if (other->resolvesToUnion()) return other->isCompatibleWith(this);
01469     return false;
01470 }
01471 
01472 bool Type::isSubTypeOrEqual(Type* other) {
01473     if (resolvesToVoid()) return true;
01474     if (*this == *other) return true;
01475     if (this->resolvesToCompound() && other->resolvesToCompound())
01476         return this->asCompound()->isSubStructOf(other);
01477     // Not really sure here
01478     return false;
01479 }
01480 
01481 Type* Type::dereference() {
01482     if (resolvesToPointer())
01483         return asPointer()->getPointsTo();
01484     if (resolvesToUnion())
01485         return asUnion()->dereferenceUnion();
01486     return new VoidType();          // Can't dereference this type. Note: should probably be bottom
01487 }
01488 
01489 // Dereference this union. If it is a union of pointers, return a union of the dereferenced items. Else return VoidType
01490 // (note: should probably be bottom)
01491 Type* UnionType::dereferenceUnion() {
01492     UnionType* ret = new UnionType;
01493     char name[20];
01494     std::list<UnionElement>::iterator it;
01495     for (it = li.begin(); it != li.end(); it++) {
01496         Type* elem = it->type->dereference();
01497         if (elem->resolvesToVoid())
01498             return elem;            // Return void for the whole thing
01499         sprintf(name, "x%d", ++nextUnionNumber);
01500         ret->addType(elem->clone(), name);
01501     }
01502     return ret;
01503 }
01504 

Generated on Tue Sep 19 21:18:19 2006 for Boomerang by  doxygen 1.4.6