type.cpp

Go to the documentation of this file.
00001 /*
00002  * Copyright (C) 1998-2001, The University of Queensland
00003  * Copyright (C) 2001, Sun Microsystems, Inc
00004  * Copyright (C) 2002, Trent Waddington
00005  *
00006  * See the file "LICENSE.TERMS" for information on usage and
00007  * redistribution of this file, and for a DISCLAIMER OF ALL
00008  * WARRANTIES.
00009  *
00010  */
00011 
00012 /*==============================================================================
00013  * FILE:       type.cpp
00014  * OVERVIEW:   Implementation of the Type class: low level type information
00015  *============================================================================*/
00016 
00017 /*
00018  * $Revision: 1.70 $    // 1.44.2.1
00019  *
00020  * 28 Apr 02 - Mike: getTempType() returns a Type* now
00021  * 26 Aug 03 - Mike: Fixed operator< (had to re-introduce an enum... ugh)
00022  * 17 Jul 04 - Mike: Fixed some functions that were returning the buffers
00023  *             of std::strings allocated on the stack (affected Windows)
00024  * 23 Jul 04 - Mike: Implement SizeType
00025  */
00026 
00027 #include <assert.h>
00028 
00029 #include "types.h"
00030 #include "type.h"
00031 #include "util.h"
00032 #include "exp.h"
00033 #include "cfg.h"
00034 #include "proc.h"
00035 #include "signature.h"
00036 #include "boomerang.h"
00037 #include "log.h"
00038 #if defined(_MSC_VER) && _MSC_VER >= 1400
00039 #pragma warning(disable:4996)       // Warnings about e.g. _strdup deprecated in VS 2005
00040 #endif
00041 
00042 extern char debug_buffer[];      // For prints functions
00043 
00044 bool Type::isCString()
00045 {
00046     if (!resolvesToPointer())
00047         return false;
00048     Type *p = asPointer()->getPointsTo();
00049     if (p->resolvesToChar())
00050         return true;
00051     if (!p->resolvesToArray())
00052         return false;
00053     p = p->asArray()->getBaseType();
00054     return p->resolvesToChar();
00055 }
00056 
00057 /*==============================================================================
00058  * FUNCTION:        Type::Type
00059  * OVERVIEW:        Default constructor
00060  * PARAMETERS:      <none>
00061  * RETURNS:         <Not applicable>
00062  *============================================================================*/
00063 Type::Type(eType id) : id(id) {
00064 }
00065 
00066 VoidType::VoidType() : Type(eVoid) {
00067 }
00068 
00069 FuncType::FuncType(Signature *sig) : Type(eFunc), signature(sig) {
00070 }
00071 
00072 IntegerType::IntegerType(int sz, int sign) : Type(eInteger), size(sz), signedness(sign) {
00073 }
00074 
00075 FloatType::FloatType(int sz) : Type(eFloat), size(sz) {
00076 }
00077 
00078 BooleanType::BooleanType() : Type(eBoolean) {
00079 }
00080 
00081 CharType::CharType() : Type(eChar) {
00082 }
00083 
00084 void PointerType::setPointsTo(Type* p) {
00085     if (p == this) {                    // Note: comparing pointers
00086         points_to = new VoidType();     // Can't point to self; impossible to compare, print, etc
00087         if (VERBOSE)
00088             LOG << "Warning: attempted to create pointer to self: " << (unsigned)this << "\n";
00089     } else
00090         points_to = p;
00091 }
00092 
00093 PointerType::PointerType(Type *p) : Type(ePointer) {
00094     setPointsTo(p);
00095 }
00096 ArrayType::ArrayType(Type *p, unsigned length) : Type(eArray), base_type(p), length(length)
00097 {
00098 }
00099 
00100 // we actually want unbounded arrays to still work correctly when
00101 // computing aliases.. as such, we give them a very large bound
00102 // and hope that no-one tries to alias beyond them
00103 #define NO_BOUND 9999999
00104 
00105 ArrayType::ArrayType(Type *p) : Type(eArray), base_type(p), length(NO_BOUND)
00106 {
00107 }
00108 
00109 bool ArrayType::isUnbounded() const {
00110     return length == NO_BOUND;
00111 }
00112 
00113 void ArrayType::setBaseType(Type* b) {
00114     // MVE: not sure if this is always the right thing to do
00115     if (length != NO_BOUND) {
00116         unsigned baseSize = base_type->getSize()/8; // Old base size (one element) in bytes
00117         if (baseSize == 0) baseSize = 1;            // Count void as size 1
00118         baseSize *= length;                         // Old base size (length elements) in bytes
00119         unsigned newSize = b->getSize()/8;
00120         if (newSize == 0) newSize = 1;
00121         length = baseSize / newSize;                // Preserve same byte size for array
00122     }
00123     base_type = b;
00124 }
00125         
00126 
00127 NamedType::NamedType(const char *name) : Type(eNamed), name(name)
00128 {
00129 }
00130 
00131 CompoundType::CompoundType(bool generic /* = false */) : Type(eCompound), nextGenericMemberNum(1), generic(generic)
00132 {
00133 }
00134 
00135 UnionType::UnionType() : Type(eUnion)
00136 {
00137 }
00138 
00139 /*==============================================================================
00140  * FUNCTION:        Type::~Type
00141  * OVERVIEW:        Virtual destructor
00142  * PARAMETERS:      <none>
00143  * RETURNS:         <Not applicable>
00144  *============================================================================*/
00145 Type::~Type() { }
00146 VoidType::~VoidType() { }
00147 FuncType::~FuncType() { }
00148 IntegerType::~IntegerType() { }
00149 FloatType::~FloatType() { }
00150 BooleanType::~BooleanType() { }
00151 CharType::~CharType() { }
00152 PointerType::~PointerType() {
00153     // delete points_to;        // Easier for test code (which doesn't use garbage collection)
00154 }
00155 ArrayType::~ArrayType() {
00156     // delete base_type;
00157 }
00158 NamedType::~NamedType() { }
00159 CompoundType::~CompoundType() { }
00160 UnionType::~UnionType() { }
00161 
00162 /*==============================================================================
00163  * FUNCTION:        *Type::clone
00164  * OVERVIEW:        Deep copy of this type
00165  * PARAMETERS:      <none>
00166  * RETURNS:         Copy of the type
00167  *============================================================================*/
00168 Type *IntegerType::clone() const
00169 {
00170     IntegerType *t = new IntegerType(size, signedness);
00171     return t;
00172 }
00173 
00174 Type *FloatType::clone() const
00175 {
00176     FloatType *t = new FloatType(size);
00177     return t;
00178 }
00179 
00180 Type *BooleanType::clone() const
00181 {
00182     BooleanType *t = new BooleanType();
00183     return t;
00184 }
00185 
00186 Type *CharType::clone() const
00187 {
00188     CharType *t = new CharType();
00189     return t;
00190 }
00191 
00192 Type *VoidType::clone() const
00193 {
00194     VoidType *t = new VoidType();
00195     return t;
00196 }
00197 
00198 Type *FuncType::clone() const
00199 {
00200     FuncType *t = new FuncType(signature);
00201     return t;
00202 }
00203 
00204 Type *PointerType::clone() const
00205 {
00206     PointerType *t = new PointerType(points_to->clone());
00207     return t;
00208 }
00209 
00210 Type *ArrayType::clone() const
00211 {
00212     ArrayType *t = new ArrayType(base_type->clone(), length);
00213     return t;
00214 }
00215 
00216 Type *NamedType::clone() const
00217 {
00218     NamedType *t = new NamedType(name.c_str());
00219     return t;
00220 }
00221 
00222 Type *CompoundType::clone() const
00223 {
00224     CompoundType *t = new CompoundType();
00225     for (unsigned i = 0; i < types.size(); i++)
00226         t->addType(types[i]->clone(), names[i].c_str());
00227     return t;
00228 }
00229 
00230 Type *UnionType::clone() const {
00231     UnionType *u = new UnionType();
00232     std::list<UnionElement>::const_iterator it;
00233     for (it = li.begin(); it != li.end(); it++)
00234         u->addType(it->type, it->name.c_str());
00235     return u;
00236 }
00237 
00238 Type *SizeType::clone() const
00239 {
00240     SizeType *t = new SizeType(size);
00241     return t;
00242 }
00243 
00244 Type* UpperType::clone() const
00245 {
00246     UpperType* t = new UpperType(base_type->clone());
00247     return t;
00248 }
00249 
00250 Type* LowerType::clone() const
00251 {
00252     LowerType* t = new LowerType(base_type->clone());
00253     return t;
00254 }
00255 
00256 
00257 /*==============================================================================
00258  * FUNCTION:        *Type::getSize
00259  * OVERVIEW:        Get the size of this type
00260  * PARAMETERS:      <none>
00261  * RETURNS:         Size of the type (in bits)
00262  *============================================================================*/
00263 unsigned IntegerType::getSize() const { return size; }
00264 unsigned      FloatType::getSize() const { return size; }
00265 unsigned BooleanType::getSize() const { return 1; }
00266 unsigned       CharType::getSize() const { return 8; }
00267 unsigned       VoidType::getSize() const { return 0; }
00268 unsigned       FuncType::getSize() const { return 0; /* always nagged me */ }
00269 unsigned PointerType::getSize() const {
00270     //points_to->getSize(); // yes, it was a good idea at the time
00271     return STD_SIZE;
00272 }
00273 unsigned ArrayType::getSize() const {
00274     return base_type->getSize() * length;
00275 }
00276 unsigned NamedType::getSize() const {
00277     Type *ty = resolvesTo();
00278     if (ty)
00279         return ty->getSize();
00280     if (VERBOSE)
00281         LOG << "WARNING: Unknown size for named type " << name.c_str() << "\n";
00282     return 0; // don't know
00283 }
00284 unsigned CompoundType::getSize() const {
00285     int n = 0;
00286     for (unsigned i = 0; i < types.size(); i++)
00287         // NOTE: this assumes no padding... perhaps explicit padding will be needed
00288         n += types[i]->getSize();
00289     return n;
00290 }
00291 unsigned UnionType::getSize() const {
00292     int max = 0;
00293     std::list<UnionElement>::const_iterator it;
00294     for (it = li.begin(); it != li.end(); it++) {
00295         int sz = it->type->getSize();
00296         if (sz > max) max = sz;
00297     }
00298     return max;
00299 }
00300 unsigned SizeType::getSize() const { return size; }
00301 
00302 
00303 
00304 Type *CompoundType::getType(const char *nam)
00305 {
00306     for (unsigned i = 0; i < types.size(); i++)
00307         if (names[i] == nam)
00308             return types[i];
00309     return NULL;
00310 }
00311 
00312 // Note: n is a BIT offset
00313 Type *CompoundType::getTypeAtOffset(unsigned n)
00314 {
00315     unsigned offset = 0;
00316     for (unsigned i = 0; i < types.size(); i++) {
00317         if (offset <= n && n < offset + types[i]->getSize())
00318             return types[i];
00319         offset += types[i]->getSize();
00320     }
00321     return NULL;
00322 }
00323 
00324 // Note: n is a BIT offset
00325 void CompoundType::setTypeAtOffset(unsigned n, Type* ty) {
00326     unsigned offset = 0;
00327     for (unsigned i = 0; i < types.size(); i++) {
00328         if (offset <= n && n < offset + types[i]->getSize()) {
00329             unsigned oldsz = types[i]->getSize();
00330             types[i] = ty;
00331             if (ty->getSize() < oldsz) {
00332                 types.push_back(types[types.size()-1]);
00333                 names.push_back(names[names.size()-1]);
00334                 for (unsigned n = types.size() - 1; n > i; n--) {
00335                     types[n] = types[n-1];
00336                     names[n] = names[n-1];
00337                 }
00338                 types[i+1] = new SizeType(oldsz - ty->getSize());
00339                 names[i+1] = "pad";
00340             }
00341             return;
00342         }
00343         offset += types[i]->getSize();
00344     }
00345 }
00346 
00347 void CompoundType::setNameAtOffset(unsigned n, const char *nam)
00348 {
00349     unsigned offset = 0;
00350     for (unsigned i = 0; i < types.size(); i++) {
00351         if (offset <= n && n < offset + types[i]->getSize()) {
00352             names[i] = nam;
00353             return;
00354         }
00355         offset += types[i]->getSize();
00356     }
00357 }
00358 
00359 
00360 const char *CompoundType::getNameAtOffset(unsigned n)
00361 {
00362     unsigned offset = 0;
00363     for (unsigned i = 0; i < types.size(); i++) {
00364         //if (offset >= n && n < offset + types[i]->getSize())
00365         if (offset <= n && n < offset + types[i]->getSize())
00366             //return getName(offset == n ? i : i - 1);
00367             return names[i].c_str();
00368         offset += types[i]->getSize();
00369     }
00370     return NULL;
00371 }
00372 
00373 unsigned CompoundType::getOffsetTo(unsigned n)
00374 {
00375     unsigned offset = 0;
00376     for (unsigned i = 0; i < n; i++) {
00377         offset += types[i]->getSize();
00378     }
00379     return offset;
00380 }
00381 
00382 unsigned CompoundType::getOffsetTo(const char *member)
00383 {
00384     unsigned offset = 0;
00385     for (unsigned i = 0; i < types.size(); i++) {
00386         if (names[i] == member)
00387             return offset;
00388         offset += types[i]->getSize();
00389     }
00390     return (unsigned)-1;
00391 }
00392 
00393 unsigned CompoundType::getOffsetRemainder(unsigned n)
00394 {
00395     unsigned r = n;
00396     unsigned offset = 0;
00397     for (unsigned i = 0; i < types.size(); i++) {
00398         offset += types[i]->getSize();
00399         if (offset > n)
00400             break;
00401         r -= types[i]->getSize();
00402     }
00403     return r;
00404 }
00405 
00406 /*==============================================================================
00407  * FUNCTION:        Type::parseType
00408  * OVERVIEW:        static Constructor from string
00409  * PARAMETERS:      str: string to parse
00410  * RETURNS:         <Not applicable>
00411  *============================================================================*/
00412 Type *Type::parseType(const char *str)
00413 {
00414     return NULL;
00415 }
00416 
00417 /*==============================================================================
00418  * FUNCTION:        *Type::operator==
00419  * OVERVIEW:        Equality comparsion.
00420  * PARAMETERS:      other - Type being compared to
00421  * RETURNS:         this == other
00422  *============================================================================*/
00423 bool IntegerType::operator==(const Type& other) const {
00424     IntegerType& otherInt = (IntegerType&) other;
00425     return other.isInteger() && 
00426         // Note: zero size matches any other size (wild, or unknown, size)
00427         (size == 0 || otherInt.size == 0 || size == otherInt.size) &&
00428         // Note: actual value of signedness is disregarded, just whether less than, equal to, or greater than 0
00429         ( signedness < 0    && otherInt.signedness < 0 ||
00430           signedness == 0   && otherInt.signedness == 0 ||
00431           signedness > 0    && otherInt.signedness > 0);
00432 }
00433 
00434 bool FloatType::operator==(const Type& other) const {
00435     return other.isFloat() && 
00436       (size == 0 || ((FloatType&)other).size == 0 || 
00437       (size == ((FloatType&)other).size));
00438 }
00439 
00440 bool BooleanType::operator==(const Type& other) const {
00441     return other.isBoolean();
00442 }
00443 
00444 bool CharType::operator==(const Type& other) const {
00445     return other.isChar();
00446 }
00447 
00448 bool VoidType::operator==(const Type& other) const {
00449     return other.isVoid();
00450 }
00451 
00452 bool FuncType::operator==(const Type& other) const {
00453     if (!other.isFunc()) return false;
00454     // Note: some functions don't have a signature (e.g. indirect calls that have not yet been successfully analysed)
00455     if (signature == NULL) return ((FuncType&)other).signature == NULL;
00456     return *signature == *((FuncType&)other).signature;
00457 }
00458 
00459 static int pointerCompareNest = 0;
00460 bool PointerType::operator==(const Type& other) const {
00461 //  return other.isPointer() && (*points_to == *((PointerType&)other).points_to);
00462     if (!other.isPointer()) return false;
00463     if (++pointerCompareNest >= 20) {
00464         std::cerr << "PointerType operator== nesting depth exceeded!\n";
00465         return true;
00466     }
00467     bool ret = (*points_to == *((PointerType&)other).points_to);
00468     pointerCompareNest--;
00469     return ret;
00470 }
00471 
00472 bool ArrayType::operator==(const Type& other) const {
00473     return other.isArray() && *base_type == *((ArrayType&)other).base_type &&
00474            ((ArrayType&)other).length == length;
00475 }
00476 
00477 bool NamedType::operator==(const Type& other) const {
00478     return other.isNamed() && (name == ((NamedType&)other).name);
00479 }
00480 
00481 bool CompoundType::operator==(const Type& other) const {
00482     const CompoundType &cother = (CompoundType&)other;
00483     if (other.isCompound() && cother.types.size() == types.size()) {
00484         for (unsigned i = 0; i < types.size(); i++)
00485             if (!(*types[i] == *cother.types[i]))
00486                 return false;
00487         return true;
00488     }
00489     return false;
00490 }
00491 
00492 bool UnionType::operator==(const Type& other) const {
00493     const UnionType &uother = (UnionType&)other;
00494     std::list<UnionElement>::const_iterator it1, it2;
00495     if (other.isUnion() && uother.li.size() == li.size()) {
00496         for (it1 = li.begin(), it2 = uother.li.begin(); it1 != li.end(); it1++, it2++)
00497             if (!(*it1->type == *it2->type))
00498                 return false;
00499         return true;
00500     }
00501     return false;
00502 }
00503 
00504 bool SizeType::operator==(const Type& other) const {
00505     return other.isSize() && (size == ((SizeType&)other).size);
00506 }
00507 bool UpperType::operator==(const Type& other) const {
00508     return other.isUpper() && *base_type == *((UpperType&)other).base_type;
00509 }
00510 
00511 bool LowerType::operator==(const Type& other) const {
00512     return other.isLower() && *base_type == *((LowerType&)other).base_type;
00513 }
00514 
00515 
00516 /*==============================================================================
00517  * FUNCTION:        Type::operator!=
00518  * OVERVIEW:        Inequality comparsion.
00519  * PARAMETERS:      other - Type being compared to
00520  * RETURNS:         this == other
00521  *============================================================================*/
00522 bool Type::operator!=(const Type& other) const
00523 {
00524     return !(*this == other);
00525 }
00526 
00527 /*==============================================================================
00528  * FUNCTION:        *Type::operator-=
00529  * OVERVIEW:        Equality operator, ignoring sign. True if equal in broad
00530  *                    type and size, but not necessarily sign
00531  *                    Considers all float types > 64 bits to be the same
00532  * PARAMETERS:      other - Type being compared to
00533  * RETURNS:         this == other (ignoring sign)
00534  *============================================================================
00535 bool IntegerType::operator-=(const Type& other) const
00536 {
00537     if (!other.isInteger()) return false;
00538     return size == ((IntegerType&)other).size;
00539 }
00540 
00541 bool FloatType::operator-=(const Type& other) const
00542 {
00543     if (!other.isFloat()) return false;
00544     if (size > 64 && ((FloatType&)other).size > 64)
00545     return true;
00546     return size == ((FloatType&)other).size;
00547 }
00548 
00549 */
00550 /*==============================================================================
00551  * FUNCTION:        *Type::operator<
00552  * OVERVIEW:        Defines an ordering between Type's
00553  *                    (and hence sets etc of Exp* using lessExpStar).
00554  * PARAMETERS:      other - Type being compared to
00555  * RETURNS:         this is less than other
00556  *============================================================================*/
00557 bool IntegerType::operator<(const Type& other) const {
00558     if (id < other.getId()) return true;
00559     if (id > other.getId()) return false;
00560     if (size < ((IntegerType&)other).size) return true;
00561     if (size > ((IntegerType&)other).size) return false;
00562     return (signedness < ((IntegerType&)other).signedness);
00563 }
00564 
00565 bool FloatType::operator<(const Type& other) const {
00566     if (id < other.getId()) return true;
00567     if (id > other.getId()) return false;
00568     return (size < ((FloatType&)other).size);
00569 }
00570 
00571 bool VoidType::operator<(const Type& other) const {
00572     return id < other.getId();
00573 }
00574 
00575 bool FuncType::operator<(const Type& other) const {
00576     if (id < other.getId()) return true;
00577     if (id > other.getId()) return false;
00578     // FIXME: Need to compare signatures
00579     return true;
00580 }
00581 
00582 bool BooleanType::operator<(const Type& other) const {
00583     if (id < other.getId()) return true;
00584     if (id > other.getId()) return false;
00585     return true;
00586 }
00587 
00588 bool CharType::operator<(const Type& other) const {
00589     return id < other.getId();
00590 }
00591 
00592 bool PointerType::operator<(const Type& other) const {
00593     if (id < other.getId()) return true;
00594     if (id > other.getId()) return false;
00595     return (*points_to < *((PointerType&)other).points_to);
00596 }
00597 
00598 bool ArrayType::operator<(const Type& other) const {
00599     if (id < other.getId()) return true;
00600     if (id > other.getId()) return false;
00601     return (*base_type < *((ArrayType&)other).base_type);
00602 }
00603 
00604 bool NamedType::operator<(const Type& other) const {
00605     if (id < other.getId()) return true;
00606     if (id > other.getId()) return false;
00607     return (name < ((NamedType&)other).name);
00608 }
00609 
00610 bool CompoundType::operator<(const Type& other) const {
00611     if (id < other.getId()) return true;
00612     if (id > other.getId()) return false;
00613     return getSize() < other.getSize();     // This won't separate structs of the same size!! MVE
00614 }
00615 
00616 bool UnionType::operator<(const Type& other) const {
00617     if (id < other.getId()) return true;
00618     if (id > other.getId()) return false;
00619     return getNumTypes() < ((const UnionType&)other).getNumTypes();
00620 }
00621 
00622 bool SizeType::operator<(const Type& other) const {
00623     if (id < other.getId()) return true;
00624     if (id > other.getId()) return false;
00625     return (size < ((SizeType&)other).size);
00626 }
00627 
00628 bool UpperType::operator<(const Type& other) const {
00629     if (id < other.getId()) return true;
00630     if (id > other.getId()) return false;
00631     return (*base_type < *((UpperType&)other).base_type);
00632 }
00633 
00634 bool LowerType::operator<(const Type& other) const {
00635     if (id < other.getId()) return true;
00636     if (id > other.getId()) return false;
00637     return (*base_type < *((LowerType&)other).base_type);
00638 }
00639 
00640 /*==============================================================================
00641  * FUNCTION:        *Type::match
00642  * OVERVIEW:        Match operation.
00643  * PARAMETERS:      pattern - Type to match
00644  * RETURNS:         Exp list of bindings if match or NULL
00645  *============================================================================*/
00646 Exp *Type::match(Type *pattern)
00647 {
00648     if (pattern->isNamed()) {
00649         LOG << "type match: " << this->getCtype() << " to " << pattern->getCtype() << "\n";
00650         return new Binary(opList, 
00651             new Binary(opEquals, 
00652                 new Unary(opVar,
00653                     new Const((char*)pattern->asNamed()->getName())), 
00654                 new TypeVal(this->clone())), 
00655             new Terminal(opNil));
00656     }
00657     return NULL;
00658 }
00659 
00660 Exp *IntegerType::match(Type *pattern)
00661 {
00662     return Type::match(pattern);
00663 }
00664 
00665 Exp *FloatType::match(Type *pattern)
00666 {
00667     return Type::match(pattern);
00668 }
00669 
00670 Exp *BooleanType::match(Type *pattern)
00671 {
00672     return Type::match(pattern);
00673 }
00674 
00675 Exp *CharType::match(Type *pattern)
00676 {
00677     return Type::match(pattern);
00678 }
00679 
00680 Exp *VoidType::match(Type *pattern)
00681 {
00682     return Type::match(pattern);
00683 }
00684 
00685 Exp *FuncType::match(Type *pattern)
00686 {
00687     return Type::match(pattern);
00688 }
00689 
00690 Exp *PointerType::match(Type *pattern)
00691 {
00692     if (pattern->isPointer()) {
00693         LOG << "got pointer match: " << this->getCtype() << " to " << pattern->getCtype() << "\n";
00694         return points_to->match(pattern->asPointer()->getPointsTo());
00695     }
00696     return Type::match(pattern);
00697 }
00698 
00699 Exp *ArrayType::match(Type *pattern)
00700 {
00701     if (pattern->isArray())
00702         return base_type->match(pattern);
00703     return Type::match(pattern);
00704 }
00705 
00706 Exp *NamedType::match(Type *pattern)
00707 {
00708     return Type::match(pattern);
00709 }
00710 
00711 Exp *CompoundType::match(Type *pattern)
00712 {
00713     return Type::match(pattern);
00714 }
00715 
00716 Exp *UnionType::match(Type *pattern)
00717 {
00718     return Type::match(pattern);
00719 }
00720 
00721 
00722 /*==============================================================================
00723  * FUNCTION:        *Type::getCtype
00724  * OVERVIEW:        Return a string representing this type
00725  * PARAMETERS:      final: if true, this is final output
00726  * RETURNS:         Pointer to a constant string of char
00727  *============================================================================*/
00728 const char *VoidType::getCtype(bool final) const { return "void"; }
00729 
00730 const char *FuncType::getCtype(bool final) const {
00731     if (signature == NULL)
00732     return "void (void)"; 
00733     std::string s; 
00734     if (signature->getNumReturns() == 0)
00735         s += "void";
00736     else 
00737         s += signature->getReturnType(0)->getCtype(final);
00738     s += " (";
00739     for (unsigned i = 0; i < signature->getNumParams(); i++) {
00740        if (i != 0) s += ", ";
00741        s += signature->getParamType(i)->getCtype(final); 
00742     }
00743     s += ")";
00744     return strdup(s.c_str());
00745 }
00746 
00747 // As above, but split into the return and parameter parts
00748 void FuncType::getReturnAndParam(const char*& ret, const char*& param) {
00749     if (signature == NULL) {
00750         ret = "void";
00751         param = "(void)";
00752         return;
00753     }
00754     if (signature->getNumReturns() == 0)
00755         ret = "void";
00756     else 
00757         ret = signature->getReturnType(0)->getCtype();
00758     std::string s; 
00759     s += " (";
00760     for (unsigned i = 0; i < signature->getNumParams(); i++) {
00761        if (i != 0) s += ", ";
00762        s += signature->getParamType(i)->getCtype(); 
00763     }
00764     s += ")";
00765     param = strdup(s.c_str());
00766 }
00767 
00768 const char *IntegerType::getCtype(bool final) const {
00769     if (signedness >= 0) {
00770         std::string s;
00771         if (!final && signedness == 0)
00772             s = "/*signed?*/";
00773         switch(size) {
00774             case 32: s += "int"; break;
00775             case 16: s += "short"; break;
00776             case  8: s += "char"; break;
00777             case  1: s += "bool"; break;
00778             case 64: s += "long long"; break;
00779             default: 
00780                 if (!final) s += "?";   // To indicate invalid/unknown size
00781                 s += "int";
00782         }
00783         return strdup(s.c_str());
00784     } else {
00785         switch (size) {
00786             case 32: return "unsigned int"; break;
00787             case 16: return "unsigned short"; break;
00788             case  8: return "unsigned char"; break;
00789             case  1: return "bool"; break;
00790             case 64: return "unsigned long long"; break;
00791             default: if (final) return "unsigned int"; 
00792                 else return "?unsigned int";
00793         }
00794     }
00795 }
00796 
00797 const char *FloatType::getCtype(bool final) const {
00798     switch (size) {
00799         case 32: return "float"; break;
00800         case 64: return "double"; break;
00801         default: return "double"; break;
00802     }
00803 }
00804 
00805 const char *BooleanType::getCtype(bool final) const { return "bool"; }
00806 
00807 const char *CharType::getCtype(bool final) const { return "char"; }
00808 
00809 const char *PointerType::getCtype(bool final) const {
00810      std::string s = points_to->getCtype(final);
00811      if (points_to->isPointer())
00812         s += "*";
00813      else
00814         s += " *";
00815      return strdup(s.c_str()); // memory..
00816 }
00817 
00818 const char *ArrayType::getCtype(bool final) const {
00819     std::string s = base_type->getCtype(final);
00820     std::ostringstream ost;
00821     if (isUnbounded())
00822         ost << "[]";
00823     else
00824         ost << "[" << length << "]";
00825     s += ost.str().c_str();
00826     return strdup(s.c_str()); // memory..
00827 }
00828 
00829 const char *NamedType::getCtype(bool final) const { return name.c_str(); }
00830 
00831 const char *CompoundType::getCtype(bool final) const {
00832     std::string &tmp = *(new std::string("struct { "));
00833     for (unsigned i = 0; i < types.size(); i++) {
00834         tmp += types[i]->getCtype(final);
00835         if (names[i] != "") {
00836             tmp += " ";
00837             tmp += names[i];
00838         }
00839         tmp += "; ";
00840     }
00841     tmp += "}";
00842     return strdup(tmp.c_str());
00843 }
00844 
00845 const char *UnionType::getCtype(bool final) const {
00846     std::string &tmp = *(new std::string("union { "));
00847     std::list<UnionElement>::const_iterator it;
00848     for (it = li.begin(); it != li.end(); it++) {
00849         tmp += it->type->getCtype(final);
00850         if (it->name != "") {
00851             tmp += " ";
00852             tmp += it->name;
00853         }
00854         tmp += "; ";
00855     }
00856     tmp += "}";
00857     return strdup(tmp.c_str());
00858 }
00859 
00860 const char* SizeType::getCtype(bool final) const {
00861     // Emit a comment and the size
00862     std::ostringstream ost;
00863     ost << "__size" << std::dec << size;
00864     return strdup(ost.str().c_str());
00865 }
00866 
00867 const char* UpperType::getCtype(bool final) const {
00868     std::ostringstream ost;
00869     ost << "/*upper*/(" << base_type << ")";
00870     return strdup(ost.str().c_str());
00871 }
00872 const char* LowerType::getCtype(bool final) const {
00873     std::ostringstream ost;
00874     ost << "/*lower*/(" << base_type << ")";
00875     return strdup(ost.str().c_str());
00876 }
00877     
00878 const char* Type::prints() {
00879     return getCtype(false);         // For debugging
00880 }
00881 
00882 void Type::dump() {
00883     std::cerr << getCtype(false);   // For debugging
00884 }
00885 
00886 std::map<std::string, Type*> Type::namedTypes;
00887 
00888 // named type accessors
00889 void Type::addNamedType(const char *name, Type *type)
00890 {
00891     if (namedTypes.find(name) != namedTypes.end()) {
00892         if (!(*type == *namedTypes[name])) {
00893             //LOG << "addNamedType: name " << name << " type " << type->getCtype() << " != " <<
00894             //  namedTypes[name]->getCtype() << "\n";// << std::flush;
00895             //LOGTAIL;
00896             std::cerr << "Warning: Type::addNamedType: Redefinition of type " << name << "\n";
00897             std::cerr << " type     = " << type->prints() << "\n";
00898             std::cerr << " previous = " << namedTypes[name]->prints() << "\n";
00899             *type == *namedTypes[name];
00900         }
00901     } else {
00902         // check if it is:
00903         // typedef int a;
00904         // typedef a b;
00905         // we then need to define b as int
00906         // we create clones to keep the GC happy
00907         if (namedTypes.find(type->getCtype()) != namedTypes.end()) {
00908             namedTypes[name] = namedTypes[type->getCtype()]->clone();
00909         } else {
00910             namedTypes[name] = type->clone();
00911         }
00912     }
00913 }
00914 
00915 Type *Type::getNamedType(const char *name)
00916 {
00917     if (namedTypes.find(name) != namedTypes.end())
00918         return namedTypes[name];
00919     return NULL;
00920 }
00921 
00922 void Type::dumpNames() {
00923     std::map<std::string, Type*>::iterator it;
00924     for (it = namedTypes.begin(); it != namedTypes.end(); ++it)
00925         std::cerr << it->first << " -> " << it->second->getCtype() << "\n";
00926 }
00927 
00928 /*==============================================================================
00929  * FUNCTION:    getTempType
00930  * OVERVIEW:    Given the name of a temporary variable, return its Type
00931  * NOTE:        Caller must delete result
00932  * PARAMETERS:  name: reference to a string (e.g. "tmp", "tmpd")
00933  * RETURNS:     Ptr to a new Type object
00934  *============================================================================*/
00935 Type* Type::getTempType(const std::string& name)
00936 {
00937     Type* ty;
00938     char ctype = ' ';
00939     if (name.size() > 3) ctype = name[3];
00940     switch (ctype) {
00941         // They are all int32, except for a few specials
00942         case 'f': ty = new FloatType(32); break;
00943         case 'd': ty = new FloatType(64); break;
00944         case 'F': ty = new FloatType(80); break;
00945         case 'D': ty = new FloatType(128); break;
00946         case 'l': ty = new IntegerType(64); break;
00947         case 'h': ty = new IntegerType(16); break;
00948         case 'b': ty = new IntegerType(8); break;
00949         default:  ty = new IntegerType(32); break;
00950     }
00951     return ty;
00952 }
00953 
00954 
00955 /*==============================================================================
00956  * FUNCTION:    *Type::getTempName
00957  * OVERVIEW:    Return a minimal temporary name for this type. It'd be even
00958  *              nicer to return a unique name, but we don't know scope at
00959  *              this point, and even so we could still clash with a user-defined
00960  *              name later on :(
00961  * PARAMETERS:  
00962  * RETURNS:     a string
00963  *============================================================================*/
00964 std::string IntegerType::getTempName() const
00965 {
00966     switch( size ) {
00967         case 1:  /* Treat as a tmpb */
00968         case 8:  return std::string("tmpb");
00969         case 16: return std::string("tmph");
00970         case 32: return std::string("tmpi");
00971         case 64: return std::string("tmpl");
00972     }
00973     return std::string("tmp");
00974 }
00975 
00976 std::string FloatType::getTempName() const
00977 {
00978     switch( size ) {
00979         case 32: return std::string("tmpf");
00980         case 64: return std::string("tmpd");
00981         case 80: return std::string("tmpF");
00982         case 128:return std::string("tmpD");
00983     }
00984     return std::string("tmp");
00985 }
00986 
00987 std::string Type::getTempName() const
00988 {
00989     return std::string("tmp"); // what else can we do? (besides panic)
00990 }
00991 
00992 int NamedType::nextAlpha = 0;
00993 NamedType* NamedType::getAlpha() {
00994     std::ostringstream ost;
00995     ost << "alpha" << nextAlpha++;
00996     return new NamedType(strdup(ost.str().c_str()));
00997 }
00998 
00999 PointerType* PointerType::newPtrAlpha() {
01000     return new PointerType(NamedType::getAlpha());
01001 }
01002 
01003 // Note: alpha is therefore a "reserved name" for types
01004 bool PointerType::pointsToAlpha() {
01005     // void* counts as alpha* (and may replace it soon)
01006     if (points_to->isVoid()) return true;
01007     if (!points_to->isNamed()) return false;
01008     return strncmp(((NamedType*)points_to)->getName(), "alpha", 5) == 0;
01009 }
01010 
01011 int PointerType::pointerDepth() {
01012     int d = 1;
01013     Type* pt = points_to;
01014     while (pt->isPointer()) {
01015         pt = pt->asPointer()->getPointsTo();
01016         d++;
01017     }
01018     return d;
01019 }
01020 
01021 Type* PointerType::getFinalPointsTo() {
01022     Type* pt = points_to;
01023     while (pt->isPointer()) {
01024         pt = pt->asPointer()->getPointsTo();
01025     }
01026     return pt;
01027 }
01028 
01029 Type *NamedType::resolvesTo() const
01030 {
01031     Type *ty = getNamedType(name.c_str());
01032     if (ty && ty->isNamed())
01033         return ((NamedType*)ty)->resolvesTo();
01034     return ty;
01035 }
01036 
01037 void ArrayType::fixBaseType(Type *b)
01038 {
01039     if (base_type == NULL)
01040         base_type = b;
01041     else {
01042         assert(base_type->isArray());
01043         base_type->asArray()->fixBaseType(b);
01044     }
01045 }
01046 
01047 #define AS_TYPE(x) \
01048 x##Type *Type::as##x() \
01049 {                       \
01050     Type *ty = this;    \
01051     if (isNamed())      \
01052         ty = ((NamedType*)ty)->resolvesTo();    \
01053     x##Type *res = dynamic_cast<x##Type*>(ty);  \
01054     assert(res);        \
01055     return res;         \
01056 }
01057 
01058 AS_TYPE(Void)
01059 AS_TYPE(Func)
01060 AS_TYPE(Boolean)
01061 AS_TYPE(Char)
01062 AS_TYPE(Integer)
01063 AS_TYPE(Float)
01064 AS_TYPE(Pointer)
01065 AS_TYPE(Array)
01066 AS_TYPE(Compound)
01067 AS_TYPE(Size);
01068 AS_TYPE(Union)
01069 AS_TYPE(Upper)
01070 AS_TYPE(Lower)
01071 // Note: don't want to call this->resolve() for this case, since then we (probably) won't have a NamedType and the
01072 // assert will fail
01073 NamedType *Type::asNamed()
01074 {
01075     Type *ty = this;
01076     NamedType *res = dynamic_cast<NamedType*>(ty);
01077     assert(res);
01078     return res;
01079 }
01080 
01081 
01082 
01083 #define RESOLVES_TO_TYPE(x)     \
01084 bool Type::resolvesTo##x()  \
01085 {                           \
01086     Type *ty = this;        \
01087     if (ty->isNamed())      \
01088         ty = ((NamedType*)ty)->resolvesTo(); \
01089     return ty && ty->is##x(); \
01090 }
01091 
01092 RESOLVES_TO_TYPE(Void)
01093 RESOLVES_TO_TYPE(Func)
01094 RESOLVES_TO_TYPE(Boolean)
01095 RESOLVES_TO_TYPE(Char)
01096 RESOLVES_TO_TYPE(Integer)
01097 RESOLVES_TO_TYPE(Float)
01098 RESOLVES_TO_TYPE(Pointer)
01099 RESOLVES_TO_TYPE(Array)
01100 RESOLVES_TO_TYPE(Compound)
01101 RESOLVES_TO_TYPE(Union)
01102 RESOLVES_TO_TYPE(Size)
01103 RESOLVES_TO_TYPE(Upper)
01104 RESOLVES_TO_TYPE(Lower)
01105 
01106 bool Type::isPointerToAlpha() {
01107     return isPointer() && asPointer()->pointsToAlpha();
01108 }
01109 
01110 void Type::starPrint(std::ostream& os) {
01111     os << "*" << this << "*";
01112 }
01113 
01114 // A crude shortcut representation of a type
01115 std::ostream& operator<<(std::ostream& os, Type* t) {
01116     if (t == NULL) return os << '0';
01117     switch (t->getId()) {
01118         case eInteger: {
01119             int sg = ((IntegerType*)t)->getSignedness();
01120             // 'j' for either i or u, don't know which
01121             os << (sg == 0 ? 'j' : sg>0 ? 'i' : 'u');
01122             os << std::dec << t->asInteger()->getSize();
01123             break;
01124         }
01125         case eFloat:    os << 'f'; os << std::dec << t->asFloat()->getSize(); break;
01126         case ePointer:  os << t->asPointer()->getPointsTo() << '*'; break;
01127         case eSize:     os << std::dec << t->getSize(); break;
01128         case eChar:     os << 'c'; break;
01129         case eVoid:     os << 'v'; break;
01130         case eBoolean:  os << 'b'; break;
01131         case eCompound: os << "struct"; break; 
01132         case eUnion:    os << "union"; break;
01133         //case eUnion:  os << t->getCtype(); break;
01134         case eFunc:     os << "func"; break;
01135         case eArray:    os << '[' << t->asArray()->getBaseType(); if (!t->asArray()->isUnbounded()) os << ", " << t->asArray()->getLength(); os << ']'; break;
01136         case eNamed:    os << t->asNamed()->getName(); break;
01137         case eUpper:    os << "U(" << t->asUpper()->getBaseType() << ')'; break;
01138         case eLower:    os << "L(" << t->asLower()->getBaseType() << ')'; break;
01139     }
01140     return os;
01141 }
01142 
01143 // FIXME: aren't mergeWith and meetWith really the same thing?
01144 // Merge this IntegerType with another
01145 Type* IntegerType::mergeWith(Type* other) {
01146     if (*this == *other) return this;
01147     if (!other->isInteger()) return NULL;       // Can you merge with a pointer?
01148     IntegerType* oth = (IntegerType*)other;
01149     IntegerType* ret = (IntegerType*)this->clone();
01150     if (size == 0) ret->setSize(oth->getSize());
01151     if (signedness == 0) ret->setSigned(oth->getSignedness());
01152     return ret;
01153 }
01154 
01155 // Merge this SizeType with another type
01156 Type* SizeType::mergeWith(Type* other) {
01157     Type* ret = other->clone();
01158     ret->setSize(size);
01159     return ret;
01160 }
01161 
01162 Type* UpperType::mergeWith(Type* other) {
01163     // FIXME: TBC
01164     return this;
01165 }
01166 
01167 Type* LowerType::mergeWith(Type* other) {
01168     // FIXME: TBC
01169     return this;
01170 }
01171 
01172 // Return true if this is a superstructure of other, i.e. we have the same types at the same offsets as other
01173 bool CompoundType::isSuperStructOf(Type* other) {
01174     if (!other->isCompound()) return false;
01175     CompoundType* otherCmp = other->asCompound();
01176     unsigned n = otherCmp->types.size();
01177     if (n > types.size()) return false;
01178     for (unsigned i=0; i < n; i++)
01179         if (otherCmp->types[i] != types[i]) return false;
01180     return true;
01181 }
01182 
01183 // Return true if this is a substructure of other, i.e. other has the same types at the same offsets as this
01184 bool CompoundType::isSubStructOf(Type* other) {
01185     if (!other->isCompound()) return false;
01186     CompoundType* otherCmp = other->asCompound();
01187     unsigned n = types.size();
01188     if (n > otherCmp->types.size()) return false;
01189     for (unsigned i=0; i < n; i++)
01190         if (otherCmp->types[i] != types[i]) return false;
01191     return true;
01192 }
01193 
01194 // Return true if this type is already in the union. Note: linear search, but number of types is usually small
01195 bool UnionType::findType(Type* ty) {
01196     std::list<UnionElement>::iterator it;
01197     for (it = li.begin(); it != li.end(); it++) {
01198         if (*it->type == *ty)
01199             return true;
01200     }
01201     return false;
01202 }
01203 
01204 void UpperType::setSize(int size) {
01205     // Does this make sense?
01206     assert(0);
01207 }
01208 
01209 void LowerType::setSize(int size) {
01210     // Does this make sense?
01211     assert(0);
01212 }
01213 
01214 Type* Type::newIntegerLikeType(int size, int signedness) {
01215     if (size == 1)
01216         return new BooleanType();
01217     if (size == 8 && signedness >= 0)
01218         return new CharType();
01219     return new IntegerType(size, signedness);
01220 }
01221 
01222 // Find the entry that overlaps with addr. If none, return end(). We have to use upper_bound and decrement the iterator,
01223 // because we might want an entry that starts earlier than addr yet still overlaps it
01224 DataIntervalMap::iterator DataIntervalMap::find_it(ADDRESS addr) {
01225     iterator it = dimap.upper_bound(addr);  // Find the first item strictly greater than addr
01226     if (it == dimap.begin())
01227         return dimap.end();                 // None <= this address, so no overlap possible
01228     it--;                                   // If any item overlaps, it is this one
01229     if (it->first <= addr && it->first+it->second.size > addr)
01230         // This is the one that overlaps with addr
01231         return it;
01232     return dimap.end();
01233 }
01234 
01235 DataIntervalEntry* DataIntervalMap::find(ADDRESS addr) {
01236     iterator it = find_it(addr);
01237     if (it == dimap.end())
01238         return NULL;
01239     return &*it;
01240 }
01241 
01242 bool DataIntervalMap::isClear(ADDRESS addr, unsigned size) {
01243     iterator it = dimap.upper_bound(addr+size-1);   // Find the first item strictly greater than address of last byte
01244     if (it == dimap.begin())
01245         return true;                        // None <= this address, so no overlap possible
01246     it--;                                   // If any item overlaps, it is this one
01247     // Make sure the previous item ends before this one will start
01248     ADDRESS end;
01249     if (it->first + it->second.size < it->first)
01250         // overflow
01251         end = 0xFFFFFFFF;       // Overflow
01252     else
01253         end = it->first + it->second.size;
01254     if (end <= addr)
01255         return true;
01256     if (it->second.type->isArray() && it->second.type->asArray()->isUnbounded()) {
01257         it->second.size = addr - it->first;
01258         LOG << "shrinking size of unbound array to " << it->second.size << " bytes\n";
01259         return true;
01260     }
01261     return false;
01262 }
01263 
01264 // With the forced parameter: are we forcing the name, the type, or always both?
01265 void DataIntervalMap::addItem(ADDRESS addr, char* name, Type* ty, bool forced /* = false */) {
01266     if (name == NULL)
01267         name = "<noname>";
01268     DataIntervalEntry* pdie = find(addr);
01269     if (pdie == NULL) {
01270         // Check that this new item is compatible with any items it overlaps with, and insert it
01271         replaceComponents(addr, name, ty, forced);
01272         return;
01273     }
01274     // There are two basic cases, and an error if the two data types weave
01275     if (pdie->first < addr) {
01276         // The existing entry comes first. Make sure it ends last (possibly equal last)
01277         if (pdie->first + pdie->second.size < addr+ty->getSize()/8) {
01278             LOG << "TYPE ERROR: attempt to insert item " << name << " at " << addr << " of type " <<
01279                 ty->getCtype() << " which weaves after " << pdie->second.name << " at " << pdie->first <<
01280                 " of type " << pdie->second.type->getCtype() << "\n";
01281             return;
01282         }
01283         enterComponent(pdie, addr, name, ty, forced);
01284     } else if (pdie->first == addr) {
01285         // Could go either way, depending on where the data items end
01286         unsigned endOfCurrent = pdie->first + pdie->second.size;
01287         unsigned endOfNew = addr+ty->getSize()/8;
01288         if (endOfCurrent < endOfNew)
01289             replaceComponents(addr, name, ty, forced);
01290         else if (endOfCurrent == endOfNew)
01291             checkMatching(pdie, addr, name, ty, forced);        // Size match; check that new type matches old
01292         else
01293             enterComponent(pdie, addr, name, ty, forced);
01294     } else {
01295         // Old starts after new; check it also ends first
01296         if (pdie->first + pdie->second.size > addr+ty->getSize()/8) {
01297             LOG << "TYPE ERROR: attempt to insert item " << name << " at " << addr << " of type " <<
01298                 ty->getCtype() << " which weaves before " << pdie->second.name << " at " << pdie->first <<
01299                 " of type " << pdie->second.type->getCtype() << "\n";
01300             return;
01301         }
01302         replaceComponents(addr, name, ty, forced);
01303     }
01304 }
01305 
01306 // We are entering an item that already exists in a larger type. Check for compatibility, meet if necessary.
01307 void DataIntervalMap::enterComponent(DataIntervalEntry* pdie, ADDRESS addr, char* name, Type* ty, bool forced) {
01308     if (pdie->second.type->resolvesToCompound()) {
01309         unsigned bitOffset = (addr - pdie->first)*8;
01310         Type* memberType = pdie->second.type->asCompound()->getTypeAtOffset(bitOffset);
01311         if (memberType->isCompatibleWith(ty)) {
01312             bool ch;
01313             memberType = memberType->meetWith(ty, ch);
01314             pdie->second.type->asCompound()->setTypeAtOffset(bitOffset, memberType);
01315         } else
01316             LOG << "TYPE ERROR: At address " << addr << " type " << ty->getCtype() << " is not compatible with "
01317                 "existing structure member type " << memberType->getCtype() << "\n";
01318     }
01319     else if (pdie->second.type->resolvesToArray()) {
01320         Type* memberType = pdie->second.type->asArray()->getBaseType();
01321         if (memberType->isCompatibleWith(ty)) {
01322             bool ch;
01323             memberType = memberType->meetWith(ty, ch);
01324             pdie->second.type->asArray()->setBaseType(memberType);
01325         } else
01326             LOG << "TYPE ERROR: At address " << addr << " type " << ty->getCtype() << " is not compatible with "
01327                 "existing array member type " << memberType->getCtype() << "\n";
01328     } else
01329         LOG << "TYPE ERROR: Existing type at address " << pdie->first << " is not structure or array type\n";
01330 }
01331 
01332 // We are entering a struct or array that overlaps existing components. Check for compatibility, and move the
01333 // components out of the way, meeting if necessary
01334 void DataIntervalMap::replaceComponents(ADDRESS addr, char* name, Type* ty, bool forced) {
01335     iterator it;
01336     unsigned pastLast = addr + ty->getSize()/8;     // This is the byte address just past the type to be inserted
01337     // First check that the new entry will be compatible with everything it will overlap
01338     if (ty->resolvesToCompound()) {
01339         iterator it1 = dimap.lower_bound(addr);         // Iterator to the first overlapping item (could be end(), but
01340                                                         // if so, it2 will also be end())
01341         iterator it2 = dimap.upper_bound(pastLast-1);   // Iterator to the first item that starts too late
01342         for (it = it1; it != it2; ++it) {
01343             unsigned bitOffset = (it->first - addr) * 8;
01344             Type* memberType = ty->asCompound()->getTypeAtOffset(bitOffset);
01345             if (memberType->isCompatibleWith(it->second.type, true)) {
01346                 bool ch;
01347                 memberType = it->second.type->meetWith(memberType, ch);
01348                 ty->asCompound()->setTypeAtOffset(bitOffset, memberType);
01349             } else {
01350                 LOG << "TYPE ERROR: At address " << addr << " struct type " << ty->getCtype() << " is not compatible "
01351                     "with existing type " << it->second.type->getCtype() << "\n";
01352                 return;
01353             }
01354         }
01355     } else if (ty->resolvesToArray()) {
01356         Type* memberType = ty->asArray()->getBaseType();
01357         iterator it1 = dimap.lower_bound(addr);
01358         iterator it2 = dimap.upper_bound(pastLast-1);
01359         for (it = it1; it != it2; ++it) {
01360             if (memberType->isCompatibleWith(it->second.type, true)) {
01361                 bool ch;
01362                 memberType = memberType->meetWith(it->second.type, ch);
01363                 ty->asArray()->setBaseType(memberType);
01364             } else {
01365                 LOG << "TYPE ERROR: At address " << addr << " array type " << ty->getCtype() << " is not compatible "
01366                     "with existing type " << it->second.type->getCtype() << "\n";
01367                 return;
01368             }
01369         }
01370     } else {
01371         // Just make sure it doesn't overlap anything
01372         if (!isClear(addr, (ty->getSize()+7)/8)) {
01373             LOG << "TYPE ERROR: at address " << addr << ", overlapping type " << ty->getCtype() << " does not resolve "
01374                 "to compound or array\n";
01375             return;
01376         }
01377     }
01378 
01379     // The compound or array type is compatible. Remove the items that it will overlap with
01380     iterator it1 = dimap.lower_bound(addr);
01381     iterator it2 = dimap.upper_bound(pastLast-1);
01382 
01383     // Check for existing locals that need to be updated
01384     if (ty->resolvesToCompound() || ty->resolvesToArray()) {
01385         Exp* rsp = Location::regOf(proc->getSignature()->getStackRegister());
01386         RefExp* rsp0 = new RefExp(rsp, proc->getCFG()->findTheImplicitAssign(rsp)); // sp{0}
01387         for (it = it1; it != it2; ++it) {
01388             // Check if there is an existing local here
01389             Exp* locl = Location::memOf(
01390                 new Binary(opPlus,
01391                     rsp0->clone(),
01392                     new Const(it->first)));
01393             locl->simplifyArith();                      // Convert m[sp{0} + -4] to m[sp{0} - 4]
01394             Type* elemTy;
01395             int bitOffset = (it->first - addr) / 8;
01396             if (ty->resolvesToCompound())
01397                 elemTy = ty->asCompound()->getTypeAtOffset(bitOffset);
01398             else
01399                 elemTy = ty->asArray()->getBaseType();
01400             char* locName = proc->findLocal(locl, elemTy);
01401             if (locName && ty->resolvesToCompound()) {
01402                 CompoundType* c = ty->asCompound();
01403                 // want s.m where s is the new compound object and m is the member at offset bitOffset
01404                 char* memName = (char*)c->getNameAtOffset(bitOffset);
01405                 Exp* s = Location::memOf(
01406                     new Binary(opPlus,
01407                         rsp0->clone(),
01408                         new Const(addr)));
01409                 s->simplifyArith();
01410                 Exp* memberExp = new Binary(opMemberAccess,
01411                     s,
01412                     new Const(memName));
01413                 proc->mapSymbolTo(locl, memberExp);
01414             } else {
01415                 // FIXME: to be completed
01416             }
01417         }
01418     }
01419 
01420     for (it = it1; it != it2 && it != dimap.end();  )
01421         // I believe that it is a conforming extension for map::erase() to return the iterator, but it is not portable
01422         // to use it. In particular, gcc considers using the return value as an error
01423         // The postincrement operator seems to be the definitive way to do this
01424         dimap.erase(it++);
01425 
01426     DataInterval* pdi = &dimap[addr];               // Finally add the new entry
01427     pdi->size = ty->getBytes();
01428     pdi->name = name;
01429     pdi->type = ty;
01430 }
01431 
01432 void DataIntervalMap::checkMatching(DataIntervalEntry* pdie, ADDRESS addr, char* name, Type* ty, bool forced) {
01433     if (pdie->second.type->isCompatibleWith(ty)) {
01434         // Just merge the types and exit
01435         bool ch;
01436         pdie->second.type = pdie->second.type->meetWith(ty, ch);
01437         return;
01438     }
01439     LOG << "TYPE DIFFERENCE (could be OK): At address " << addr << " existing type " << pdie->second.type->getCtype() <<
01440          " but added type " << ty->getCtype() << "\n";
01441 }
01442 
01443 void DataIntervalMap::deleteItem(ADDRESS addr) {
01444     iterator it = dimap.find(addr);
01445     if (it == dimap.end())
01446         return;
01447     dimap.erase(it);
01448 }
01449 
01450 void DataIntervalMap::dump() {
01451     std::cerr << prints();
01452 }
01453 
01454 char* DataIntervalMap::prints() {
01455     iterator it;
01456     std::ostringstream ost;
01457     for (it = dimap.begin(); it != dimap.end(); ++it)
01458         ost << std::hex << "0x" << it->first << std::dec << " " << it->second.name << " " << it->second.type->getCtype()
01459             << "\n";
01460     strncpy(debug_buffer, ost.str().c_str(), DEBUG_BUFSIZE-1);
01461     debug_buffer[DEBUG_BUFSIZE-1] = '\0';
01462     return debug_buffer;
01463 }
01464 
01465 ComplexTypeCompList& Type::compForAddress(ADDRESS addr, DataIntervalMap& dim) {
01466     DataIntervalEntry* pdie = dim.find(addr);
01467     ComplexTypeCompList* res = new ComplexTypeCompList;
01468     if (pdie == NULL) return *res;
01469     ADDRESS startCurrent = pdie->first;
01470     Type* curType = pdie->second.type;
01471     while (startCurrent < addr) {
01472         unsigned bitOffset = (addr - startCurrent) * 8;
01473         if (curType->isCompound()) {
01474             CompoundType* compCurType = curType->asCompound();
01475             unsigned rem = compCurType->getOffsetRemainder(bitOffset);
01476             startCurrent = addr - (rem/8);
01477             ComplexTypeComp ctc;
01478             ctc.isArray = false;
01479             ctc.u.memberName = strdup(compCurType->getNameAtOffset(bitOffset));
01480             res->push_back(ctc);
01481             curType = compCurType->getTypeAtOffset(bitOffset);
01482         } else if (curType->isArray()) {
01483             curType = curType->asArray()->getBaseType();
01484             unsigned baseSize = curType->getSize();
01485             unsigned index = bitOffset / baseSize;
01486             startCurrent += index * baseSize/8;
01487             ComplexTypeComp ctc;
01488             ctc.isArray = true;
01489             ctc.u.index = index;
01490             res->push_back(ctc);
01491         } else {
01492             LOG << "TYPE ERROR: no struct or array at byte address " << addr << "\n";
01493             return *res;
01494         }
01495     }
01496     return *res;
01497 }
01498 
01499 void UnionType::addType(Type *n, const char *str) {
01500     if (n->isUnion()) {
01501         UnionType* utp = (UnionType*)n;
01502         // Note: need to check for name clashes eventually
01503         li.insert(li.end(), utp->li.begin(), utp->li.end());
01504     } else {
01505         if (n->isPointer() && n->asPointer()->getPointsTo() == this) {      // Note: pointer comparison
01506             n = new PointerType(new VoidType);
01507             if (VERBOSE)
01508                 LOG << "Warning: attempt to union with pointer to self!\n";
01509         }
01510         UnionElement ue;
01511         ue.type = n;
01512         ue.name = str;
01513         li.push_back(ue);
01514     }
01515 }
01516 
01517 // Update this compound to use the fact that offset off has type ty
01518 void CompoundType::updateGenericMember(int off, Type* ty, bool& ch) {
01519     assert(generic);
01520     Type* existingType = getTypeAtOffset(off);
01521     if (existingType) {
01522         existingType = existingType->meetWith(ty, ch);
01523     } else {
01524         std::ostringstream ost;
01525         ost << "member" << std::dec << nextGenericMemberNum++;
01526         setTypeAtOffset(off*8, ty);
01527         setNameAtOffset(off*8, ost.str().c_str());
01528     }
01529 }
01530 
01531 
01532 #if USING_MEMO
01533 class FuncTypeMemo : public Memo {
01534 public:
01535     FuncTypeMemo(int m) : Memo(m) { }
01536     Signature *signature;
01537 };
01538 
01539 Memo *FuncType::makeMemo(int mId)
01540 {
01541     FuncTypeMemo *m = new FuncTypeMemo(mId);
01542     m->signature = signature;
01543 
01544     signature->takeMemo(mId);
01545     return m;
01546 }
01547 
01548 void FuncType::readMemo(Memo *mm, bool dec)
01549 {
01550     FuncTypeMemo *m = dynamic_cast<FuncTypeMemo*>(mm);
01551     signature = m->signature;
01552 
01553     //signature->restoreMemo(m->mId, dec);
01554 }
01555 
01556 class IntegerTypeMemo : public Memo {
01557 public:
01558     IntegerTypeMemo(int m) : Memo(m) { }
01559     int size;
01560     int signedness;
01561 };
01562 
01563 Memo *IntegerType::makeMemo(int mId)
01564 {
01565     IntegerTypeMemo *m = new IntegerTypeMemo(mId);
01566     m->size = size;
01567     m->signedness = signedness;
01568     return m;
01569 }
01570 
01571 void IntegerType::readMemo(Memo *mm, bool dec)
01572 {
01573     IntegerTypeMemo *m = dynamic_cast<IntegerTypeMemo*>(mm);
01574     size = m->size;
01575     signedness = m->signedness;
01576 }
01577 
01578 class FloatTypeMemo : public Memo {
01579 public:
01580     FloatTypeMemo(int m) : Memo(m) { }
01581     int size;
01582 };
01583 
01584 Memo *FloatType::makeMemo(int mId)
01585 {
01586     FloatTypeMemo *m = new FloatTypeMemo(mId);
01587     m->size = size;
01588     return m;
01589 }
01590 
01591 void FloatType::readMemo(Memo *mm, bool dec)
01592 {
01593     FloatTypeMemo *m = dynamic_cast<FloatTypeMemo*>(mm);
01594     size = m->size;
01595 }
01596 
01597 class PointerTypeMemo : public Memo {
01598 public:
01599     PointerTypeMemo(int m) : Memo(m) { }
01600     Type *points_to;
01601 };
01602 
01603 Memo *PointerType::makeMemo(int mId)
01604 {
01605     PointerTypeMemo *m = new PointerTypeMemo(mId);
01606     m->points_to = points_to;
01607 
01608     points_to->takeMemo(mId);
01609 
01610     return m;
01611 }
01612 
01613 void PointerType::readMemo(Memo *mm, bool dec)
01614 {
01615     PointerTypeMemo *m = dynamic_cast<PointerTypeMemo*>(mm);
01616     points_to = m->points_to;
01617 
01618     points_to->restoreMemo(m->mId, dec);
01619 }
01620 
01621 class ArrayTypeMemo : public Memo {
01622 public:
01623     ArrayTypeMemo(int m) : Memo(m) { }
01624     Type *base_type;
01625     unsigned length;
01626 };
01627 
01628 Memo *ArrayType::makeMemo(int mId)
01629 {
01630     ArrayTypeMemo *m = new ArrayTypeMemo(mId);
01631     m->base_type = base_type;
01632     m->length = length;
01633 
01634     base_type->takeMemo(mId);
01635 
01636     return m;
01637 }
01638 
01639 void ArrayType::readMemo(Memo *mm, bool dec)
01640 {
01641     ArrayTypeMemo *m = dynamic_cast<ArrayTypeMemo*>(mm);
01642     length = m->length;
01643     base_type = m->base_type;
01644 
01645     base_type->restoreMemo(m->mId, dec);
01646 }
01647 
01648 class NamedTypeMemo : public Memo {
01649 public:
01650     NamedTypeMemo(int m) : Memo(m) { }
01651     std::string name;
01652     int nextAlpha;
01653 };
01654 
01655 Memo *NamedType::makeMemo(int mId)
01656 {
01657     NamedTypeMemo *m = new NamedTypeMemo(mId);
01658     m->name = name;
01659     m->nextAlpha = nextAlpha;
01660     return m;
01661 }
01662 
01663 void NamedType::readMemo(Memo *mm, bool dec)
01664 {
01665     NamedTypeMemo *m = dynamic_cast<NamedTypeMemo*>(mm);
01666     name = m->name;
01667     nextAlpha = m->nextAlpha;
01668 }
01669 
01670 class CompoundTypeMemo : public Memo {
01671 public:
01672     CompoundTypeMemo(int m) : Memo(m) { }
01673     std::vector<Type*> types;
01674     std::vector<std::string> names;
01675 };
01676 
01677 Memo *CompoundType::makeMemo(int mId)
01678 {
01679     CompoundTypeMemo *m = new CompoundTypeMemo(mId);
01680     m->types = types;
01681     m->names = names;
01682 
01683     for (std::vector<Type*>::iterator it = types.begin(); it != types.end(); it++)
01684         (*it)->takeMemo(mId);
01685     return m;
01686 }
01687 
01688 void CompoundType::readMemo(Memo *mm, bool dec)
01689 {
01690     CompoundTypeMemo *m = dynamic_cast<CompoundTypeMemo*>(mm);
01691     types = m->types;
01692     names = m->names;
01693 
01694     for (std::vector<Type*>::iterator it = types.begin(); it != types.end(); it++)
01695         (*it)->restoreMemo(m->mId, dec);
01696 }
01697 
01698 class UnionTypeMemo : public Memo {
01699 public:
01700     UnionTypeMemo(int m) : Memo(m) { }
01701     std::list<UnionElement> li;
01702 };
01703 
01704 Memo *UnionType::makeMemo(int mId)
01705 {
01706     UnionTypeMemo *m = new UnionTypeMemo(mId);
01707     m->li = li;
01708 
01709     for (std::list<UnionElement>::iterator it = li.begin(); it != li.end(); it++)
01710         it->type->takeMemo(mId);        // Is this right? What about the names? MVE
01711     return m;
01712 }
01713 
01714 void UnionType::readMemo(Memo *mm, bool dec)
01715 {
01716     UnionTypeMemo *m = dynamic_cast<UnionTypeMemo*>(mm);
01717     li = m->li;
01718 
01719     for (std::list<UnionElement>::iterator it = li.begin(); it != li.end(); it++)
01720         it->type->restoreMemo(m->mId, dec);
01721 }
01722 
01723 // Don't insert new functions here! (Unles memo related.) Inside #if USING_MEMO!
01724 
01725 #endif          // #if USING_MEMO

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