Home | History | Annotate | Download | only in m_debuginfo
      1 
      2 /*--------------------------------------------------------------------*/
      3 /*--- Representation of source level types.              tytypes.c ---*/
      4 /*--------------------------------------------------------------------*/
      5 
      6 /*
      7    This file is part of Valgrind, a dynamic binary instrumentation
      8    framework.
      9 
     10    Copyright (C) 2008-2012 OpenWorks LLP
     11       info (at) open-works.co.uk
     12 
     13    This program is free software; you can redistribute it and/or
     14    modify it under the terms of the GNU General Public License as
     15    published by the Free Software Foundation; either version 2 of the
     16    License, or (at your option) any later version.
     17 
     18    This program is distributed in the hope that it will be useful, but
     19    WITHOUT ANY WARRANTY; without even the implied warranty of
     20    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
     21    General Public License for more details.
     22 
     23    You should have received a copy of the GNU General Public License
     24    along with this program; if not, write to the Free Software
     25    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
     26    02111-1307, USA.
     27 
     28    The GNU General Public License is contained in the file COPYING.
     29 
     30    Neither the names of the U.S. Department of Energy nor the
     31    University of California nor the names of its contributors may be
     32    used to endorse or promote products derived from this software
     33    without prior written permission.
     34 */
     35 
     36 #include "pub_core_basics.h"
     37 #include "pub_core_debuginfo.h"
     38 #include "pub_core_libcassert.h"
     39 #include "pub_core_libcbase.h"
     40 #include "pub_core_libcprint.h"
     41 #include "pub_core_xarray.h"   /* to keep priv_tytypes.h happy */
     42 
     43 #include "priv_misc.h"         /* dinfo_zalloc/free/strdup */
     44 #include "priv_d3basics.h"     /* ML_(evaluate_Dwarf3_Expr) et al */
     45 #include "priv_tytypes.h"      /* self */
     46 
     47 
     48 /* Does this TyEnt denote a type, as opposed to some other kind of
     49    thing? */
     50 
     51 Bool ML_(TyEnt__is_type)( TyEnt* te )
     52 {
     53    switch (te->tag) {
     54       case Te_EMPTY: case Te_INDIR: case Te_UNKNOWN:
     55       case Te_Atom:  case Te_Field: case Te_Bound:
     56          return False;
     57       case Te_TyBase:   case Te_TyPtr:     case Te_TyRef:
     58       case Te_TyPtrMbr: case Te_TyRvalRef: case Te_TyTyDef:
     59       case Te_TyStOrUn: case Te_TyEnum:    case Te_TyArray:
     60       case Te_TyFn:     case Te_TyQual:    case Te_TyVoid:
     61          return True;
     62       default:
     63          vg_assert(0);
     64    }
     65 }
     66 
     67 
     68 /* Print a TyEnt, debug-style. */
     69 
     70 static void pp_XArray_of_cuOffs ( XArray* xa )
     71 {
     72    Word i;
     73    VG_(printf)("{");
     74    for (i = 0; i < VG_(sizeXA)(xa); i++) {
     75       UWord cuOff = *(UWord*)VG_(indexXA)(xa, i);
     76       VG_(printf)("0x%05lx", cuOff);
     77       if (i+1 < VG_(sizeXA)(xa))
     78          VG_(printf)(",");
     79    }
     80    VG_(printf)("}");
     81 }
     82 
     83 void ML_(pp_TyEnt)( TyEnt* te )
     84 {
     85    VG_(printf)("0x%05lx  ", te->cuOff);
     86    switch (te->tag) {
     87       case Te_EMPTY:
     88          VG_(printf)("EMPTY");
     89          break;
     90       case Te_INDIR:
     91          VG_(printf)("INDIR(0x%05lx)", te->Te.INDIR.indR);
     92          break;
     93       case Te_UNKNOWN:
     94          VG_(printf)("UNKNOWN");
     95          break;
     96       case Te_Atom:
     97          VG_(printf)("Te_Atom(%s%lld,\"%s\")",
     98                      te->Te.Atom.valueKnown ? "" : "unknown:",
     99                      te->Te.Atom.value, te->Te.Atom.name);
    100          break;
    101       case Te_Field:
    102          if (te->Te.Field.nLoc == -1)
    103             VG_(printf)("Te_Field(ty=0x%05lx,pos.offset=%ld,\"%s\")",
    104                         te->Te.Field.typeR, te->Te.Field.pos.offset,
    105                         te->Te.Field.name ? te->Te.Field.name : (UChar*)"");
    106          else
    107             VG_(printf)("Te_Field(ty=0x%05lx,nLoc=%lu,pos.loc=%p,\"%s\")",
    108                         te->Te.Field.typeR, te->Te.Field.nLoc,
    109                         te->Te.Field.pos.loc,
    110                         te->Te.Field.name ? te->Te.Field.name : (UChar*)"");
    111          break;
    112       case Te_Bound:
    113          VG_(printf)("Te_Bound[");
    114          if (te->Te.Bound.knownL)
    115             VG_(printf)("%lld", te->Te.Bound.boundL);
    116          else
    117             VG_(printf)("??");
    118          VG_(printf)(",");
    119          if (te->Te.Bound.knownU)
    120             VG_(printf)("%lld", te->Te.Bound.boundU);
    121          else
    122             VG_(printf)("??");
    123          VG_(printf)("]");
    124          break;
    125       case Te_TyBase:
    126          VG_(printf)("Te_TyBase(%d,%c,\"%s\")",
    127                      te->Te.TyBase.szB, te->Te.TyBase.enc,
    128                      te->Te.TyBase.name ? te->Te.TyBase.name
    129                                         : (UChar*)"(null)" );
    130          break;
    131       case Te_TyPtr:
    132          VG_(printf)("Te_TyPtr(%d,0x%05lx)", te->Te.TyPorR.szB,
    133                      te->Te.TyPorR.typeR);
    134          break;
    135       case Te_TyRef:
    136          VG_(printf)("Te_TyRef(%d,0x%05lx)", te->Te.TyPorR.szB,
    137                      te->Te.TyPorR.typeR);
    138          break;
    139       case Te_TyPtrMbr:
    140          VG_(printf)("Te_TyMbr(%d,0x%05lx)", te->Te.TyPorR.szB,
    141                      te->Te.TyPorR.typeR);
    142          break;
    143       case Te_TyRvalRef:
    144          VG_(printf)("Te_TyRvalRef(%d,0x%05lx)", te->Te.TyPorR.szB,
    145                      te->Te.TyPorR.typeR);
    146          break;
    147       case Te_TyTyDef:
    148          VG_(printf)("Te_TyTyDef(0x%05lx,\"%s\")",
    149                      te->Te.TyTyDef.typeR,
    150                      te->Te.TyTyDef.name ? te->Te.TyTyDef.name
    151                                          : (UChar*)"" );
    152          break;
    153       case Te_TyStOrUn:
    154          if (te->Te.TyStOrUn.complete) {
    155             VG_(printf)("Te_TyStOrUn(%ld,%c,%p,\"%s\")",
    156                         te->Te.TyStOrUn.szB,
    157                         te->Te.TyStOrUn.isStruct ? 'S' : 'U',
    158                         te->Te.TyStOrUn.fieldRs,
    159                         te->Te.TyStOrUn.name ? te->Te.TyStOrUn.name
    160                                              : (UChar*)"" );
    161             if (te->Te.TyStOrUn.fieldRs)
    162                pp_XArray_of_cuOffs( te->Te.TyStOrUn.fieldRs );
    163          } else {
    164             VG_(printf)("Te_TyStOrUn(INCOMPLETE,\"%s\")",
    165                         te->Te.TyStOrUn.name);
    166          }
    167          break;
    168       case Te_TyEnum:
    169          VG_(printf)("Te_TyEnum(%d,%p,\"%s\")",
    170                      te->Te.TyEnum.szB, te->Te.TyEnum.atomRs,
    171                      te->Te.TyEnum.name ? te->Te.TyEnum.name
    172                                         : (UChar*)"" );
    173          if (te->Te.TyEnum.atomRs)
    174             pp_XArray_of_cuOffs( te->Te.TyEnum.atomRs );
    175          break;
    176       case Te_TyArray:
    177          VG_(printf)("Te_TyArray(0x%05lx,%p)",
    178                      te->Te.TyArray.typeR, te->Te.TyArray.boundRs);
    179          if (te->Te.TyArray.boundRs)
    180             pp_XArray_of_cuOffs( te->Te.TyArray.boundRs );
    181          break;
    182       case Te_TyFn:
    183          VG_(printf)("Te_TyFn");
    184          break;
    185       case Te_TyQual:
    186          VG_(printf)("Te_TyQual(%c,0x%05lx)", te->Te.TyQual.qual,
    187                      te->Te.TyQual.typeR);
    188          break;
    189       case Te_TyVoid:
    190          VG_(printf)("Te_TyVoid%s",
    191                      te->Te.TyVoid.isFake ? "(fake)" : "");
    192          break;
    193       default:
    194          vg_assert(0);
    195    }
    196 }
    197 
    198 
    199 /* Print a whole XArray of TyEnts, debug-style */
    200 
    201 void ML_(pp_TyEnts)( XArray* tyents, HChar* who )
    202 {
    203    Word i, n;
    204    VG_(printf)("------ %s ------\n", who);
    205    n = VG_(sizeXA)( tyents );
    206    for (i = 0; i < n; i++) {
    207       TyEnt* tyent = (TyEnt*)VG_(indexXA)( tyents, i );
    208       VG_(printf)("   [%5ld]  ", i);
    209       ML_(pp_TyEnt)( tyent );
    210       VG_(printf)("\n");
    211    }
    212 }
    213 
    214 
    215 /* Print a TyEnt, C style, chasing stuff as necessary. */
    216 
    217 static void pp_TyBound_C_ishly ( XArray* tyents, UWord cuOff )
    218 {
    219    TyEnt* ent = ML_(TyEnts__index_by_cuOff)( tyents, NULL, cuOff );
    220    if (!ent) {
    221       VG_(printf)("**bounds-have-invalid-cuOff**");
    222       return;
    223    }
    224    vg_assert(ent->tag == Te_Bound);
    225    if (ent->Te.Bound.knownL && ent->Te.Bound.knownU
    226        && ent->Te.Bound.boundL == 0) {
    227       VG_(printf)("[%lld]", 1 + ent->Te.Bound.boundU);
    228    }
    229    else
    230    if (ent->Te.Bound.knownL && (!ent->Te.Bound.knownU)
    231        && ent->Te.Bound.boundL == 0) {
    232       VG_(printf)("[]");
    233    }
    234    else
    235       ML_(pp_TyEnt)( ent );
    236 }
    237 
    238 void ML_(pp_TyEnt_C_ishly)( XArray* /* of TyEnt */ tyents,
    239                             UWord cuOff )
    240 {
    241    TyEnt* ent = ML_(TyEnts__index_by_cuOff)( tyents, NULL, cuOff );
    242    if (!ent) {
    243       VG_(printf)("**type-has-invalid-cuOff**");
    244       return;
    245    }
    246    switch (ent->tag) {
    247       case Te_TyBase:
    248          if (!ent->Te.TyBase.name) goto unhandled;
    249          VG_(printf)("%s", ent->Te.TyBase.name);
    250          break;
    251       case Te_TyPtr:
    252          ML_(pp_TyEnt_C_ishly)(tyents, ent->Te.TyPorR.typeR);
    253          VG_(printf)("*");
    254          break;
    255       case Te_TyRef:
    256          ML_(pp_TyEnt_C_ishly)(tyents, ent->Te.TyPorR.typeR);
    257          VG_(printf)("&");
    258          break;
    259       case Te_TyPtrMbr:
    260          ML_(pp_TyEnt_C_ishly)(tyents, ent->Te.TyPorR.typeR);
    261          VG_(printf)("*");
    262          break;
    263       case Te_TyRvalRef:
    264          ML_(pp_TyEnt_C_ishly)(tyents, ent->Te.TyPorR.typeR);
    265          VG_(printf)("&&");
    266          break;
    267       case Te_TyEnum:
    268          if (!ent->Te.TyEnum.name) goto unhandled;
    269          VG_(printf)("enum %s", ent->Te.TyEnum.name);
    270          break;
    271       case Te_TyStOrUn:
    272          VG_(printf)("%s %s",
    273                      ent->Te.TyStOrUn.isStruct ? "struct" : "union",
    274                      ent->Te.TyStOrUn.name ? ent->Te.TyStOrUn.name
    275                                            : (UChar*)"<anonymous>" );
    276          break;
    277       case Te_TyArray:
    278          ML_(pp_TyEnt_C_ishly)(tyents, ent->Te.TyArray.typeR);
    279          if (ent->Te.TyArray.boundRs) {
    280             Word    w;
    281             XArray* xa = ent->Te.TyArray.boundRs;
    282             for (w = 0; w < VG_(sizeXA)(xa); w++) {
    283                pp_TyBound_C_ishly( tyents, *(UWord*)VG_(indexXA)(xa, w) );
    284             }
    285          } else {
    286             VG_(printf)("%s", "[??]");
    287          }
    288          break;
    289       case Te_TyTyDef:
    290          if (!ent->Te.TyTyDef.name) goto unhandled;
    291          VG_(printf)("%s", ent->Te.TyTyDef.name);
    292          break;
    293       case Te_TyFn:
    294          VG_(printf)("%s", "<function_type>");
    295          break;
    296       case Te_TyQual:
    297          switch (ent->Te.TyQual.qual) {
    298             case 'C': VG_(printf)("const "); break;
    299             case 'V': VG_(printf)("volatile "); break;
    300             default: goto unhandled;
    301          }
    302          ML_(pp_TyEnt_C_ishly)(tyents, ent->Te.TyQual.typeR);
    303          break;
    304       case Te_TyVoid:
    305          VG_(printf)("%svoid",
    306                      ent->Te.TyVoid.isFake ? "fake" : "");
    307          break;
    308       case Te_UNKNOWN:
    309          ML_(pp_TyEnt)(ent);
    310          break;
    311       default:
    312          goto unhandled;
    313    }
    314    return;
    315 
    316   unhandled:
    317    VG_(printf)("pp_TyEnt_C_ishly:unhandled: ");
    318    ML_(pp_TyEnt)(ent);
    319    vg_assert(0);
    320 }
    321 
    322 
    323 /* 'ents' is an XArray of TyEnts, sorted by their .cuOff fields.  Find
    324    the entry which has .cuOff field as specified.  Returns NULL if not
    325    found.  Asserts if more than one entry has the specified .cuOff
    326    value. */
    327 
    328 void ML_(TyEntIndexCache__invalidate) ( TyEntIndexCache* cache )
    329 {
    330    Word i;
    331    for (i = 0; i < N_TYENT_INDEX_CACHE; i++) {
    332       cache->ce[i].cuOff0 = 0;    /* not actually necessary */
    333       cache->ce[i].ent0   = NULL; /* "invalid entry" */
    334       cache->ce[i].cuOff1 = 0;    /* not actually necessary */
    335       cache->ce[i].ent1   = NULL; /* "invalid entry" */
    336    }
    337 }
    338 
    339 TyEnt* ML_(TyEnts__index_by_cuOff) ( XArray* /* of TyEnt */ ents,
    340                                      TyEntIndexCache* cache,
    341                                      UWord cuOff_to_find )
    342 {
    343    Bool  found;
    344    Word  first, last;
    345    TyEnt key, *res;
    346 
    347    /* crude stats, aggregated over all caches */
    348    static UWord cacheQs = 0 - 1;
    349    static UWord cacheHits = 0;
    350 
    351    if (0 && 0 == (cacheQs & 0xFFFF))
    352       VG_(printf)("cache: %'lu queries, %'lu misses\n",
    353                   cacheQs, cacheQs - cacheHits);
    354 
    355    if (LIKELY(cache != NULL)) {
    356       UWord h = cuOff_to_find % (UWord)N_TYENT_INDEX_CACHE;
    357       cacheQs++;
    358       // dude, like, way 0, dude.
    359       if (cache->ce[h].cuOff0 == cuOff_to_find && cache->ce[h].ent0 != NULL) {
    360          // dude, way 0 is a total hit!
    361          cacheHits++;
    362          return cache->ce[h].ent0;
    363       }
    364       // dude, check out way 1, dude.
    365       if (cache->ce[h].cuOff1 == cuOff_to_find && cache->ce[h].ent1 != NULL) {
    366          // way 1 hit
    367          UWord  tc;
    368          TyEnt* te;
    369          cacheHits++;
    370          // dude, way 1 is the new way 0.  move with the times, dude.
    371          tc = cache->ce[h].cuOff0;
    372          te = cache->ce[h].ent0;
    373          cache->ce[h].cuOff0 = cache->ce[h].cuOff1;
    374          cache->ce[h].ent0   = cache->ce[h].ent1;
    375          cache->ce[h].cuOff1 = tc;
    376          cache->ce[h].ent1   = te;
    377          return cache->ce[h].ent0;
    378       }
    379    }
    380 
    381    /* We'll have to do it the hard way */
    382    key.cuOff = cuOff_to_find;
    383    key.tag   = Te_EMPTY;
    384    found = VG_(lookupXA)( ents, &key, &first, &last );
    385    //found = VG_(lookupXA_UNBOXED)( ents, cuOff_to_find, &first, &last,
    386    //                               offsetof(TyEnt,cuOff) );
    387    if (!found)
    388       return NULL;
    389    /* If this fails, the array is invalid in the sense that there is
    390       more than one entry with .cuOff == cuOff_to_find. */
    391    vg_assert(first == last);
    392    res = (TyEnt*)VG_(indexXA)( ents, first );
    393 
    394    if (LIKELY(cache != NULL) && LIKELY(res != NULL)) {
    395       /* this is a bit stupid, computing this twice.  Oh well.
    396          Perhaps some magic gcc transformation will common them up.
    397          re "res != NULL", since .ent of NULL denotes 'invalid entry',
    398          we can't cache the result when res == NULL. */
    399       UWord h = cuOff_to_find % (UWord)N_TYENT_INDEX_CACHE;
    400       cache->ce[h].cuOff1 = cache->ce[h].cuOff0;
    401       cache->ce[h].ent1   = cache->ce[h].ent0;
    402       cache->ce[h].cuOff0 = cuOff_to_find;
    403       cache->ce[h].ent0   = res;
    404    }
    405 
    406    return res;
    407 }
    408 
    409 
    410 /* Generates a total ordering on TyEnts based only on their .cuOff
    411    fields. */
    412 
    413 Word ML_(TyEnt__cmp_by_cuOff_only) ( TyEnt* te1, TyEnt* te2 )
    414 {
    415    if (te1->cuOff < te2->cuOff) return -1;
    416    if (te1->cuOff > te2->cuOff) return 1;
    417    return 0;
    418 }
    419 
    420 
    421 /* Generates a total ordering on TyEnts based on everything except
    422    their .cuOff fields. */
    423 static inline Word UWord__cmp ( UWord a, UWord b ) {
    424    if (a < b) return -1;
    425    if (a > b) return 1;
    426    return 0;
    427 }
    428 static inline Word Long__cmp ( Long a, Long b ) {
    429    if (a < b) return -1;
    430    if (a > b) return 1;
    431    return 0;
    432 }
    433 static inline Word Bool__cmp ( Bool a, Bool b ) {
    434    vg_assert( ((UWord)a) <= 1 );
    435    vg_assert( ((UWord)b) <= 1 );
    436    if (a < b) return -1;
    437    if (a > b) return 1;
    438    return 0;
    439 }
    440 static inline Word UChar__cmp ( UChar a, UChar b ) {
    441    if (a < b) return -1;
    442    if (a > b) return 1;
    443    return 0;
    444 }
    445 static inline Word Int__cmp ( Int a, Int b ) {
    446    if (a < b) return -1;
    447    if (a > b) return 1;
    448    return 0;
    449 }
    450 static Word XArray_of_UWord__cmp ( XArray* a, XArray* b ) {
    451    Word i, r;
    452    Word aN = VG_(sizeXA)( a );
    453    Word bN = VG_(sizeXA)( b );
    454    if (aN < bN) return -1;
    455    if (aN > bN) return 1;
    456    for (i = 0; i < aN; i++) {
    457       r = UWord__cmp( *(UWord*)VG_(indexXA)( a, i ),
    458                       *(UWord*)VG_(indexXA)( b, i ) );
    459       if (r != 0) return r;
    460    }
    461    return 0;
    462 }
    463 static Word Bytevector__cmp ( UChar* a, UChar* b, Word n ) {
    464    Word i, r;
    465    vg_assert(n >= 0);
    466    for (i = 0; i < n; i++) {
    467       r = UChar__cmp( a[i], b[i] );
    468       if (r != 0) return r;
    469    }
    470    return 0;
    471 }
    472 static Word Asciiz__cmp ( UChar* a, UChar* b ) {
    473    /* A wrapper around strcmp that handles NULL strings safely. */
    474    if (a == NULL && b == NULL) return 0;
    475    if (a == NULL && b != NULL) return -1;
    476    if (a != NULL && b == NULL) return 1;
    477    return VG_(strcmp)(a, b);
    478 }
    479 
    480 Word ML_(TyEnt__cmp_by_all_except_cuOff) ( TyEnt* te1, TyEnt* te2 )
    481 {
    482    Word r;
    483    if (te1->tag < te2->tag) return -1;
    484    if (te1->tag > te2->tag) return 1;
    485    switch (te1->tag) {
    486    case Te_EMPTY:
    487       return 0;
    488    case Te_INDIR:
    489       r = UWord__cmp(te1->Te.INDIR.indR, te2->Te.INDIR.indR);
    490       return r;
    491    case Te_Atom:
    492       r = Bool__cmp(te1->Te.Atom.valueKnown, te2->Te.Atom.valueKnown);
    493       if (r != 0) return r;
    494       r = Long__cmp(te1->Te.Atom.value, te2->Te.Atom.value);
    495       if (r != 0) return r;
    496       r = Asciiz__cmp(te1->Te.Atom.name, te2->Te.Atom.name);
    497       return r;
    498    case Te_Field:
    499       r = Bool__cmp(te1->Te.Field.isStruct, te2->Te.Field.isStruct);
    500       if (r != 0) return r;
    501       r = UWord__cmp(te1->Te.Field.typeR, te2->Te.Field.typeR);
    502       if (r != 0) return r;
    503       r = Asciiz__cmp(te1->Te.Field.name, te2->Te.Field.name);
    504       if (r != 0) return r;
    505       r = UWord__cmp(te1->Te.Field.nLoc, te2->Te.Field.nLoc);
    506       if (r != 0) return r;
    507       if (te1->Te.Field.nLoc == -1)
    508          r = Long__cmp(te1->Te.Field.pos.offset, te2->Te.Field.pos.offset);
    509       else
    510          r = Bytevector__cmp(te1->Te.Field.pos.loc, te2->Te.Field.pos.loc,
    511                              te1->Te.Field.nLoc);
    512       return r;
    513    case Te_Bound:
    514       r = Bool__cmp(te1->Te.Bound.knownL, te2->Te.Bound.knownL);
    515       if (r != 0) return r;
    516       r = Bool__cmp(te1->Te.Bound.knownU, te2->Te.Bound.knownU);
    517       if (r != 0) return r;
    518       r = Long__cmp(te1->Te.Bound.boundL, te2->Te.Bound.boundL);
    519       if (r != 0) return r;
    520       r = Long__cmp(te1->Te.Bound.boundU, te2->Te.Bound.boundU);
    521       return r;
    522    case Te_TyBase:
    523       r = UChar__cmp(te1->Te.TyBase.enc, te2->Te.TyBase.enc);
    524       if (r != 0) return r;
    525       r = Int__cmp(te1->Te.TyBase.szB, te2->Te.TyBase.szB);
    526       if (r != 0) return r;
    527       r = Asciiz__cmp(te1->Te.TyBase.name, te2->Te.TyBase.name);
    528       return r;
    529    case Te_TyPtr:
    530    case Te_TyRef:
    531    case Te_TyPtrMbr:
    532    case Te_TyRvalRef:
    533       r = Int__cmp(te1->Te.TyPorR.szB, te2->Te.TyPorR.szB);
    534       if (r != 0) return r;
    535       r = UWord__cmp(te1->Te.TyPorR.typeR, te2->Te.TyPorR.typeR);
    536       return r;
    537    case Te_TyTyDef:
    538       r = UWord__cmp(te1->Te.TyTyDef.typeR, te2->Te.TyTyDef.typeR);
    539       if (r != 0) return r;
    540       r = Asciiz__cmp(te1->Te.TyTyDef.name, te2->Te.TyTyDef.name);
    541       return r;
    542    case Te_TyStOrUn:
    543       r = Bool__cmp(te1->Te.TyStOrUn.isStruct, te2->Te.TyStOrUn.isStruct);
    544       if (r != 0) return r;
    545       r = Bool__cmp(te1->Te.TyStOrUn.complete, te2->Te.TyStOrUn.complete);
    546       if (r != 0) return r;
    547       r = UWord__cmp(te1->Te.TyStOrUn.szB, te2->Te.TyStOrUn.szB);
    548       if (r != 0) return r;
    549       r = Asciiz__cmp(te1->Te.TyStOrUn.name, te2->Te.TyStOrUn.name);
    550       if (r != 0) return r;
    551       r = XArray_of_UWord__cmp(te1->Te.TyStOrUn.fieldRs,
    552                                te2->Te.TyStOrUn.fieldRs);
    553       return r;
    554    case Te_TyEnum:
    555       r = Int__cmp(te1->Te.TyEnum.szB, te2->Te.TyEnum.szB);
    556       if (r != 0) return r;
    557       r = Asciiz__cmp(te1->Te.TyEnum.name, te2->Te.TyEnum.name);
    558       if (r != 0) return r;
    559       r = XArray_of_UWord__cmp(te1->Te.TyEnum.atomRs, te2->Te.TyEnum.atomRs);
    560       return r;
    561    case Te_TyArray:
    562       r = UWord__cmp(te1->Te.TyArray.typeR, te2->Te.TyArray.typeR);
    563       if (r != 0) return r;
    564       r = XArray_of_UWord__cmp(te1->Te.TyArray.boundRs,
    565                                te2->Te.TyArray.boundRs);
    566       return r;
    567    case Te_TyFn:
    568       return 0;
    569    case Te_TyQual:
    570       r = UWord__cmp(te1->Te.TyQual.typeR, te2->Te.TyQual.typeR);
    571       if (r != 0) return r;
    572       r = UChar__cmp(te1->Te.TyQual.qual, te2->Te.TyQual.qual);
    573       return r;
    574    case Te_TyVoid:
    575       r = Bool__cmp(te1->Te.TyVoid.isFake, te2->Te.TyVoid.isFake);
    576       return r;
    577    default:
    578       vg_assert(0);
    579    }
    580 }
    581 
    582 
    583 /* Free up all directly or indirectly heap-allocated stuff attached to
    584    this TyEnt, and set its tag to Te_EMPTY.  The .cuOff field is
    585    unchanged. */
    586 
    587 void ML_(TyEnt__make_EMPTY) ( TyEnt* te )
    588 {
    589    UWord saved_cuOff;
    590    /* First, free up any fields in mallocville. */
    591    switch (te->tag) {
    592       case Te_EMPTY:
    593          break;
    594       case Te_INDIR:
    595          break;
    596       case Te_UNKNOWN:
    597          break;
    598       case Te_Atom:
    599          if (te->Te.Atom.name) ML_(dinfo_free)(te->Te.Atom.name);
    600          break;
    601       case Te_Field:
    602          if (te->Te.Field.name) ML_(dinfo_free)(te->Te.Field.name);
    603          if (te->Te.Field.nLoc > 0 && te->Te.Field.pos.loc)
    604             ML_(dinfo_free)(te->Te.Field.pos.loc);
    605          break;
    606       case Te_Bound:
    607          break;
    608       case Te_TyBase:
    609          if (te->Te.TyBase.name) ML_(dinfo_free)(te->Te.TyBase.name);
    610          break;
    611       case Te_TyPtr:
    612       case Te_TyRef:
    613       case Te_TyPtrMbr:
    614       case Te_TyRvalRef:
    615          break;
    616       case Te_TyTyDef:
    617          if (te->Te.TyTyDef.name) ML_(dinfo_free)(te->Te.TyTyDef.name);
    618          break;
    619       case Te_TyStOrUn:
    620          if (te->Te.TyStOrUn.name) ML_(dinfo_free)(te->Te.TyStOrUn.name);
    621          if (te->Te.TyStOrUn.fieldRs) VG_(deleteXA)(te->Te.TyStOrUn.fieldRs);
    622          break;
    623       case Te_TyEnum:
    624          if (te->Te.TyEnum.name) ML_(dinfo_free)(te->Te.TyEnum.name);
    625          if (te->Te.TyEnum.atomRs) VG_(deleteXA)(te->Te.TyEnum.atomRs);
    626          break;
    627       case Te_TyArray:
    628          if (te->Te.TyArray.boundRs) VG_(deleteXA)(te->Te.TyArray.boundRs);
    629          break;
    630       case Te_TyFn:
    631          break;
    632       case Te_TyQual:
    633          break;
    634       case Te_TyVoid:
    635          break;
    636       default:
    637          vg_assert(0);
    638    }
    639    /* Now clear it out and set to Te_EMPTY. */
    640    saved_cuOff = te->cuOff;
    641    VG_(memset)(te, 0, sizeof(*te));
    642    te->cuOff = saved_cuOff;
    643    te->tag = Te_EMPTY;
    644 }
    645 
    646 
    647 /* How big is this type?  If .b in the returned struct is False, the
    648    size is unknown. */
    649 
    650 static MaybeULong mk_MaybeULong_Nothing ( void ) {
    651    MaybeULong mul;
    652    mul.ul = 0;
    653    mul.b  = False;
    654    return mul;
    655 }
    656 static MaybeULong mk_MaybeULong_Just ( ULong ul ) {
    657    MaybeULong mul;
    658    mul.ul = ul;
    659    mul.b  = True;
    660    return mul;
    661 }
    662 static MaybeULong mul_MaybeULong ( MaybeULong mul1, MaybeULong mul2 ) {
    663    if (!mul1.b) { vg_assert(mul1.ul == 0); return mul1; }
    664    if (!mul2.b) { vg_assert(mul2.ul == 0); return mul2; }
    665    mul1.ul *= mul2.ul;
    666    return mul1;
    667 }
    668 
    669 MaybeULong ML_(sizeOfType)( XArray* /* of TyEnt */ tyents,
    670                             UWord cuOff )
    671 {
    672    Word       i;
    673    MaybeULong eszB;
    674    TyEnt*     ent = ML_(TyEnts__index_by_cuOff)(tyents, NULL, cuOff);
    675    TyEnt*     ent2;
    676    vg_assert(ent);
    677    vg_assert(ML_(TyEnt__is_type)(ent));
    678    switch (ent->tag) {
    679       case Te_TyBase:
    680          vg_assert(ent->Te.TyBase.szB > 0);
    681          return mk_MaybeULong_Just( ent->Te.TyBase.szB );
    682       case Te_TyQual:
    683          return ML_(sizeOfType)( tyents, ent->Te.TyQual.typeR );
    684       case Te_TyTyDef:
    685          ent2 = ML_(TyEnts__index_by_cuOff)(tyents, NULL,
    686                                             ent->Te.TyTyDef.typeR);
    687          vg_assert(ent2);
    688          if (ent2->tag == Te_UNKNOWN)
    689             return mk_MaybeULong_Nothing(); /*UNKNOWN*/
    690          return ML_(sizeOfType)( tyents, ent->Te.TyTyDef.typeR );
    691       case Te_TyPtr:
    692       case Te_TyRef:
    693       case Te_TyPtrMbr:
    694       case Te_TyRvalRef:
    695          vg_assert(ent->Te.TyPorR.szB == 4 || ent->Te.TyPorR.szB == 8);
    696          return mk_MaybeULong_Just( ent->Te.TyPorR.szB );
    697       case Te_TyStOrUn:
    698          return ent->Te.TyStOrUn.complete
    699                    ? mk_MaybeULong_Just( ent->Te.TyStOrUn.szB )
    700                    : mk_MaybeULong_Nothing();
    701       case Te_TyEnum:
    702          return mk_MaybeULong_Just( ent->Te.TyEnum.szB );
    703       case Te_TyArray:
    704          ent2 = ML_(TyEnts__index_by_cuOff)(tyents, NULL,
    705                                             ent->Te.TyArray.typeR);
    706          vg_assert(ent2);
    707          if (ent2->tag == Te_UNKNOWN)
    708             return mk_MaybeULong_Nothing(); /*UNKNOWN*/
    709          eszB = ML_(sizeOfType)( tyents, ent->Te.TyArray.typeR );
    710          for (i = 0; i < VG_(sizeXA)( ent->Te.TyArray.boundRs ); i++) {
    711             UWord bo_cuOff
    712                = *(UWord*)VG_(indexXA)(ent->Te.TyArray.boundRs, i);
    713             TyEnt* bo
    714               = ML_(TyEnts__index_by_cuOff)( tyents, NULL, bo_cuOff );
    715             vg_assert(bo);
    716             vg_assert(bo->tag == Te_Bound);
    717             if (!(bo->Te.Bound.knownL && bo->Te.Bound.knownU))
    718                return mk_MaybeULong_Nothing(); /*UNKNOWN*/
    719             eszB = mul_MaybeULong(
    720                       eszB,
    721                       mk_MaybeULong_Just( (ULong)(bo->Te.Bound.boundU
    722                                                   - bo->Te.Bound.boundL + 1) ));
    723          }
    724          return eszB;
    725       case Te_TyVoid:
    726          return mk_MaybeULong_Nothing(); /*UNKNOWN*/
    727       default:
    728          VG_(printf)("ML_(sizeOfType): unhandled: ");
    729          ML_(pp_TyEnt)(ent);
    730          VG_(printf)("\n");
    731          vg_assert(0);
    732    }
    733 }
    734 
    735 
    736 /* Describe where in the type 'offset' falls.  Caller must
    737    deallocate the resulting XArray. */
    738 
    739 static void copy_UWord_into_XA ( XArray* /* of UChar */ xa,
    740                                  UWord uw ) {
    741    UChar buf[32];
    742    VG_(memset)(buf, 0, sizeof(buf));
    743    VG_(sprintf)(buf, "%lu", uw);
    744    VG_(addBytesToXA)( xa, buf, VG_(strlen)(buf));
    745 }
    746 
    747 XArray* /*UChar*/ ML_(describe_type)( /*OUT*/PtrdiffT* residual_offset,
    748                                       XArray* /* of TyEnt */ tyents,
    749                                       UWord ty_cuOff,
    750                                       PtrdiffT offset )
    751 {
    752    TyEnt*  ty;
    753    XArray* xa = VG_(newXA)( ML_(dinfo_zalloc), "di.tytypes.dt.1",
    754                             ML_(dinfo_free),
    755                             sizeof(UChar) );
    756    vg_assert(xa);
    757 
    758    ty = ML_(TyEnts__index_by_cuOff)(tyents, NULL, ty_cuOff);
    759 
    760    while (True) {
    761       vg_assert(ty);
    762       vg_assert(ML_(TyEnt__is_type)(ty));
    763 
    764       switch (ty->tag) {
    765 
    766          /* These are all atomic types; there is nothing useful we can
    767             do. */
    768          case Te_TyEnum:
    769          case Te_TyFn:
    770          case Te_TyVoid:
    771          case Te_TyPtr:
    772          case Te_TyRef:
    773          case Te_TyPtrMbr:
    774          case Te_TyRvalRef:
    775          case Te_TyBase:
    776             goto done;
    777 
    778          case Te_TyStOrUn: {
    779             Word       i;
    780             GXResult   res;
    781             MaybeULong mul;
    782             XArray*    fieldRs;
    783             UWord      fieldR;
    784             TyEnt*     field = NULL;
    785             PtrdiffT   offMin = 0, offMax1 = 0;
    786             if (!ty->Te.TyStOrUn.isStruct) goto done;
    787             fieldRs = ty->Te.TyStOrUn.fieldRs;
    788             if ((!fieldRs) || VG_(sizeXA)(fieldRs) == 0) goto done;
    789             for (i = 0; i < VG_(sizeXA)( fieldRs ); i++ ) {
    790                fieldR = *(UWord*)VG_(indexXA)( fieldRs, i );
    791                field = ML_(TyEnts__index_by_cuOff)(tyents, NULL, fieldR);
    792                vg_assert(field);
    793                vg_assert(field->tag == Te_Field);
    794                vg_assert(field->Te.Field.nLoc < 0
    795                          || (field->Te.Field.nLoc > 0
    796                              && field->Te.Field.pos.loc));
    797                if (field->Te.Field.nLoc == -1) {
    798                   res.kind = GXR_Addr;
    799                   res.word = field->Te.Field.pos.offset;
    800                } else {
    801                   /* Re data_bias in this call, we should really send in
    802                      a legitimate value.  But the expression is expected
    803                      to be a constant expression, evaluation of which
    804                      will not need to use DW_OP_addr and hence we can
    805                      avoid the trouble of plumbing the data bias through
    806                      to this point (if, indeed, it has any meaning; from
    807                      which DebugInfo would we take the data bias? */
    808                    res =  ML_(evaluate_Dwarf3_Expr)(
    809                           field->Te.Field.pos.loc, field->Te.Field.nLoc,
    810                           NULL/*fbGX*/, NULL/*RegSummary*/,
    811                           0/*data_bias*/,
    812                           True/*push_initial_zero*/);
    813                   if (0) {
    814                      VG_(printf)("QQQ ");
    815                      ML_(pp_GXResult)(res);
    816                      VG_(printf)("\n");
    817                   }
    818                }
    819                if (res.kind != GXR_Addr)
    820                   continue;
    821                mul = ML_(sizeOfType)( tyents, field->Te.Field.typeR );
    822                if (mul.b != True)
    823                   goto done; /* size of field is unknown (?!) */
    824                offMin  = res.word;
    825                offMax1 = offMin + (PtrdiffT)mul.ul;
    826                if (offMin == offMax1)
    827                   continue;
    828                vg_assert(offMin < offMax1);
    829                if (offset >= offMin && offset < offMax1)
    830                   break;
    831             }
    832             /* Did we find a suitable field? */
    833             vg_assert(i >= 0 && i <= VG_(sizeXA)( fieldRs ));
    834             if (i == VG_(sizeXA)( fieldRs ))
    835                goto done; /* No.  Give up. */
    836             /* Yes.  'field' is it. */
    837             vg_assert(field);
    838             if (!field->Te.Field.name) goto done;
    839             VG_(addBytesToXA)( xa, ".", 1 );
    840             VG_(addBytesToXA)( xa, field->Te.Field.name,
    841                                VG_(strlen)(field->Te.Field.name) );
    842             offset -= offMin;
    843             ty = ML_(TyEnts__index_by_cuOff)(tyents, NULL,
    844                                              field->Te.Field.typeR );
    845             tl_assert(ty);
    846             if (ty->tag == Te_UNKNOWN) goto done;
    847             /* keep going; look inside the field. */
    848             break;
    849          }
    850 
    851          case Te_TyArray: {
    852             MaybeULong mul;
    853             UWord      size, eszB, ix;
    854             UWord      boundR;
    855             TyEnt*     elemTy;
    856             TyEnt*     bound;
    857             /* Just deal with the simple, common C-case: 1-D array,
    858                zero based, known size. */
    859             elemTy = ML_(TyEnts__index_by_cuOff)(tyents, NULL,
    860                                                  ty->Te.TyArray.typeR);
    861             vg_assert(elemTy);
    862             if (elemTy->tag == Te_UNKNOWN) goto done;
    863             vg_assert(ML_(TyEnt__is_type)(elemTy));
    864             if (!ty->Te.TyArray.boundRs)
    865                goto done;
    866             if (VG_(sizeXA)( ty->Te.TyArray.boundRs ) != 1) goto done;
    867             boundR = *(UWord*)VG_(indexXA)( ty->Te.TyArray.boundRs, 0 );
    868             bound = ML_(TyEnts__index_by_cuOff)(tyents, NULL, boundR);
    869             vg_assert(bound);
    870             vg_assert(bound->tag == Te_Bound);
    871             if (!(bound->Te.Bound.knownL && bound->Te.Bound.knownU
    872                   && bound->Te.Bound.boundL == 0
    873                   && bound->Te.Bound.boundU >= bound->Te.Bound.boundL))
    874                goto done;
    875             size = bound->Te.Bound.boundU - bound->Te.Bound.boundL + 1;
    876             vg_assert(size >= 1);
    877             mul = ML_(sizeOfType)( tyents, ty->Te.TyArray.typeR );
    878             if (mul.b != True)
    879                goto done; /* size of element type not known */
    880             eszB = mul.ul;
    881             if (eszB == 0) goto done;
    882             ix = offset / eszB;
    883             VG_(addBytesToXA)( xa, "[", 1 );
    884             copy_UWord_into_XA( xa, ix );
    885             VG_(addBytesToXA)( xa, "]", 1 );
    886             ty = elemTy;
    887             offset -= ix * eszB;
    888             /* keep going; look inside the array element. */
    889             break;
    890          }
    891 
    892          case Te_TyQual: {
    893             ty = ML_(TyEnts__index_by_cuOff)(tyents, NULL,
    894                                              ty->Te.TyQual.typeR);
    895             tl_assert(ty);
    896             if (ty->tag == Te_UNKNOWN) goto done;
    897             break;
    898          }
    899 
    900          case Te_TyTyDef: {
    901             ty = ML_(TyEnts__index_by_cuOff)(tyents, NULL,
    902                                              ty->Te.TyTyDef.typeR);
    903             tl_assert(ty);
    904             if (ty->tag == Te_UNKNOWN) goto done;
    905             break;
    906          }
    907 
    908          default: {
    909             VG_(printf)("ML_(describe_type): unhandled: ");
    910             ML_(pp_TyEnt)(ty);
    911             VG_(printf)("\n");
    912             vg_assert(0);
    913          }
    914 
    915       }
    916    }
    917 
    918   done:
    919    *residual_offset = offset;
    920    VG_(addBytesToXA)( xa, "\0", 1 );
    921    return xa;
    922 }
    923 
    924 /*--------------------------------------------------------------------*/
    925 /*--- end                                                tytypes.c ---*/
    926 /*--------------------------------------------------------------------*/
    927