l4/pkg/valgrind/src/valgrind-3.6.0-svn/coregrind/m_debuginfo/tytypes.c

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