nsz Git - libfirm/blob - win32/firmEvaluator/firm.c

   1 /*
   2  * Firm - Evaluator
   3  *
   4  * (C) 2005 Michael Beck    beck@ipd.info.uni-karlsruhe.de
   5  */
   6 #define WIN32_LEAN_AND_MEAN
   7 #include <windows.h>
   8 #include <tchar.h>
   9 #include <malloc.h>
  10 #include <stdarg.h>
  11
  12 #include "config.h"
  13
  14 /* ugly, but I must include array.h WITHOUT NDEBUG */
  15 #ifdef NDEBUG
  16 #undef NDEBUG
  17 #include "array_t.h"
  18 #define NDEBUG
  19 #else
  20 #include "array_t.h"
  21 #endif
  22
  23 #include "entity_t.h"
  24 #include "irgraph_t.h"
  25 #include "irnode_t.h"
  26 #include "irmode_t.h"
  27 #include "tv_t.h"
  28 #include "irloop_t.h"
  29 #include "irprog_t.h"
  30 #include "compound_path_t.h"
  31 #include "tpop_t.h"
  32 #include "strcalc.h"
  33 #include "fltcalc.h"
  34
  35 #include "set.h"
  36 #include "pset.h"
  37 #include "pdeq.h"
  38 #include "bitset.h"
  39
  40 #include "firmEvaluator.h"
  41
  42 /** get the address of a pointer */
  43 #define ADD_ADR(p, off)  ((void *)((char *)(p) + (off)))
  44
  45 /** debug output */
  46 static void debug(char *fmt, ...)
  47 {
  48   va_list ap;
  49   char buf[1024];
  50
  51   va_start(ap, fmt);
  52   vsprintf(buf, fmt, ap);
  53
  54   OutputDebugString(buf);
  55   va_end(ap);
  56 }
  57
  58 /**
  59  * return the size of a firm object
  60  */
  61 int get_firm_object_size(firm_kind kind)
  62 {
  63   switch (kind) {
  64   case k_entity:     /* an entity */
  65     return sizeof(ir_entity);
  66   case k_type:       /* a type */
  67     return sizeof(ir_type);
  68   case k_ir_graph:   /* an ir graph */
  69     return sizeof(ir_graph);
  70   case k_ir_node:    /* an ir node */
  71     return sizeof(ir_node);
  72   case k_ir_mode:    /* an ir mode */
  73     return sizeof(ir_mode);
  74   case k_ir_op:      /* an ir opcode */
  75     return sizeof(ir_op);
  76   case k_tarval:     /* a tarval */
  77     return sizeof(tarval);
  78   case k_ir_loop:    /* a loop */
  79     return sizeof(ir_loop);
  80   case k_ir_prog:    /* a program representation (irp) */
  81     return sizeof(ir_prog);
  82   default:
  83     return 0;
  84   }
  85 }
  86
  87 /**
  88  * returns the string length of a string in debuggee space
  89  *
  90  * @return string length or negative value on error
  91  */
  92 static int strlen_debuggee(DEBUGHELPER *pHelper, const void *address, size_t max)
  93 {
  94   size_t i;
  95   char v;
  96   const char *p = address;
  97
  98   for (i = 0; i < max; ++i) {
  99     if (copy_from_debuggee(p + i, pHelper, &v, sizeof(v)) != S_OK)
 100       return -1;
 101
 102     if (! v)
 103       return i;
 104   }
 105   return i;
 106 }
 107
 108 /**
 109  * Format an ident
 110  */
 111 HRESULT format_ident(DEBUGHELPER *pHelper, const void *address, char *pResult, size_t max)
 112 {
 113   set_entry *data = NULL;
 114   set_entry id;
 115   size_t len, slen;
 116
 117   if (copy_from_debuggee(address, pHelper, &id, sizeof(id)) != S_OK)
 118     return E_FAIL;
 119
 120   /* safety check */
 121   if (id.size < 1 || id.size > 256)
 122     return E_FAIL;
 123
 124   slen = id.size + 1;
 125   len = offsetof(set_entry, dptr) + slen;
 126
 127   data = alloca(len);
 128
 129   if (copy_from_debuggee(address, pHelper, data, len) != S_OK)
 130     return E_FAIL;
 131
 132   _tcsncpy(pResult, (const char *)data->dptr, max);
 133   return S_OK;
 134 }
 135
 136 /**
 137  * Format a tp_op
 138  */
 139 static HRESULT format_tp_op(DEBUGHELPER *pHelper, const void *addr, char *pResult, size_t max)
 140 {
 141   tp_op op;
 142
 143 #define X(a)     case tpo_##a: _tcsncpy(pResult, #a, max); return S_OK
 144 #define Y(a, b)  case tpo_##a: _tcsncpy(pResult, b, max); return S_OK
 145
 146   if (copy_from_debuggee(addr, pHelper, &op, sizeof(op)) != S_OK)
 147     return E_FAIL;
 148
 149   switch (op.code) {
 150   X(uninitialized);
 151   X(class);
 152   X(struct);
 153   X(method);
 154   X(union);
 155   X(array);
 156   Y(enumeration, "enum");
 157   Y(pointer, "ptr");
 158   Y(primitive, "prim");
 159   X(none);
 160   X(unknown);
 161   default:
 162     return E_FAIL;
 163   }
 164 #undef X
 165 #undef Y
 166 }
 167
 168 /**
 169  * Checks whether a type is the global type
 170  *
 171  * @param type  the address of the type in debuggee's space
 172  */
 173 static HRESULT is_global_type(DEBUGHELPER *pHelper, const void *type, int *flag)
 174 {
 175   ir_type tp;
 176
 177   *flag = 0;
 178   if (copy_from_debuggee(type, pHelper, &tp, sizeof(tp)) != S_OK)
 179     return E_FAIL;
 180
 181   *flag = tp.flags & tf_global_type;
 182   return S_OK;
 183 }
 184
 185 /**
 186  * format an entity
 187  */
 188 static HRESULT format_entity(DEBUGHELPER *pHelper, int nBase, const void *addr, char *pResult, size_t max, int top)
 189 {
 190   ir_entity ent;
 191   ir_type owner;
 192   char name[256];
 193   int is_global;
 194
 195   if (copy_from_debuggee(addr, pHelper, &ent, sizeof(ent)) != S_OK) {
 196     return E_FAIL;
 197   }
 198   if (is_global_type(pHelper, ent.owner, &is_global) != S_OK)
 199     return E_FAIL;
 200
 201   *pResult = '\0';
 202   if (top)
 203     _tcsncpy(pResult, "ENT: ", max);
 204
 205   if (! is_global) {
 206     if (copy_from_debuggee(ent.owner, pHelper, &owner, sizeof(owner)) != S_OK)
 207       return E_FAIL;
 208     if (format_ident(pHelper, (void *)owner.name, name, sizeof(name)) != S_OK)
 209       return E_FAIL;
 210     _tcsncat(pResult, name, max);
 211     _tcsncat(pResult, "::", max);
 212   }
 213
 214   if (format_ident(pHelper, (void *)ent.name, name, sizeof(name)) != S_OK)
 215     return E_FAIL;
 216   _tcsncat(pResult, name, max);
 217
 218   switch (nBase) {
 219   case 16:
 220     _snprintf(name, sizeof(name), " [0x%lx]", ent.nr);
 221     break;
 222   case 8:
 223     _snprintf(name, sizeof(name), " [0%lo]", ent.nr);
 224     break;
 225   default:
 226     _snprintf(name, sizeof(name), " [%ld]", ent.nr);
 227   }
 228   _tcsncat(pResult, name, max);
 229
 230   return S_OK;
 231 }
 232
 233 /**
 234  * format an ir_mode
 235  */
 236 static HRESULT format_mode(DEBUGHELPER *pHelper, const void *addr, char *pResult, size_t max)
 237 {
 238   ir_mode mode;
 239
 240   if (copy_from_debuggee(addr, pHelper, &mode, sizeof(mode)) != S_OK)
 241     return E_FAIL;
 242   if (format_ident(pHelper, mode.name, pResult, max) != S_OK)
 243     return E_FAIL;
 244   return S_OK;
 245 }
 246
 247 /**
 248  * format a type
 249  */
 250 static HRESULT format_type(DEBUGHELPER *pHelper, int nBase, const void *addr, char *pResult, size_t max, int top)
 251 {
 252   ir_type tp;
 253   char name[256];
 254
 255   if (copy_from_debuggee(addr, pHelper, &tp, sizeof(tp)) != S_OK)
 256     return E_FAIL;
 257
 258   pResult[0] = '\0';
 259   if (top) {
 260     if (format_tp_op(pHelper, tp.type_op, pResult, max) != S_OK)
 261       return E_FAIL;
 262
 263     _tcsncat(pResult, " ", max);
 264   }
 265
 266   name[0] = '\0';
 267   if (tp.name) {
 268     if (format_ident(pHelper, tp.name, name, sizeof(name)) != S_OK)
 269       return E_FAIL;
 270   } else {
 271     if (format_mode(pHelper, tp.mode, name, sizeof(name)) != S_OK)
 272       return E_FAIL;
 273   }
 274
 275   _tcsncat(pResult, name, max);
 276   switch (nBase) {
 277   case 16:
 278     _snprintf(name, sizeof(name), " [0x%lx]", tp.nr);
 279     break;
 280   case 8:
 281     _snprintf(name, sizeof(name), " [0%lo]", tp.nr);
 282     break;
 283   default:
 284     _snprintf(name, sizeof(name), " [%ld]", tp.nr);
 285   }
 286   _tcsncat(pResult, name, max);
 287
 288   return S_OK;
 289 }
 290
 291 /**
 292  * format an irg
 293  */
 294 static HRESULT format_irg(DEBUGHELPER *pHelper, int nBase, const void *addr, char *pResult, size_t max, int top)
 295 {
 296   ir_graph irg;
 297   char name[256];
 298
 299   if (copy_from_debuggee(addr, pHelper, &irg, sizeof(irg)) != S_OK)
 300     return E_FAIL;
 301
 302   *pResult = '\0';
 303   if (top)
 304     _tcsncpy(pResult, "IRG: ", max);
 305
 306   if (irg.ent) {
 307     ir_entity ent;
 308     ir_type owner;
 309     int is_global;
 310
 311     if (copy_from_debuggee(irg.ent, pHelper, &ent, sizeof(ent)) != S_OK)
 312       return E_FAIL;
 313     if (is_global_type(pHelper, ent.owner, &is_global) != S_OK)
 314       return E_FAIL;
 315     if (! is_global) {
 316       if (copy_from_debuggee(ent.owner, pHelper, &owner, sizeof(owner)) != S_OK)
 317         return E_FAIL;
 318       if (format_ident(pHelper, (void *)owner.name, name, sizeof(name)) != S_OK)
 319         return E_FAIL;
 320       _tcsncat(pResult, name, max);
 321       _tcsncat(pResult, "::", max);
 322     }
 323     if (format_ident(pHelper, ent.name, name, sizeof(name)) != S_OK)
 324       return E_FAIL;
 325     _tcsncat(pResult, name, max);
 326   }
 327   else
 328     _tcsncat(pResult, "NULL", max);
 329
 330   switch (nBase) {
 331   case 16:
 332     _snprintf(name, sizeof(name), " [0x%lx, 0x%u nodes]", irg.graph_nr, irg.last_node_idx);
 333     break;
 334   case 8:
 335     _snprintf(name, sizeof(name), " [0%lo, 0%o nodes]", irg.graph_nr, irg.last_node_idx);
 336     break;
 337   default:
 338     _snprintf(name, sizeof(name), " [%ld, %u nodes]", irg.graph_nr, irg.last_node_idx);
 339   }
 340   _tcsncat(pResult, name, max);
 341   return S_OK;
 342 }
 343
 344 /**
 345  * format an ir_op
 346  */
 347 HRESULT format_op(DEBUGHELPER *pHelper, const void *addr, char *pResult, size_t max)
 348 {
 349   ir_op op;
 350
 351   if (copy_from_debuggee(addr, pHelper, &op, sizeof(op)) != S_OK)
 352     return E_FAIL;
 353   if (format_ident(pHelper, op.name, pResult, max) != S_OK)
 354     return E_FAIL;
 355   return S_OK;
 356 }
 357
 358 /** get a temporary string */
 359 #define get_string(str)                                         \
 360 do {                                                            \
 361   int len;                                                      \
 362   char *s;                                                      \
 363   if (str) {                                                    \
 364     len = strlen_debuggee(pHelper, str, 256);                   \
 365     if (len < 0)                                                \
 366       return E_FAIL;                                            \
 367     s = alloca(len + 1);                                        \
 368     if (copy_from_debuggee(str, pHelper, s, (DWORD)len) != S_OK) \
 369       return E_FAIL;                                            \
 370     s[len] = '\0';                                              \
 371     str = s;                                                    \
 372   }                                                             \
 373 } while (0)
 374
 375 /**
 376  * format a tarval
 377  */
 378 static HRESULT format_tarval(DEBUGHELPER *pHelper, int nBase, const void *addr, char *pResult, size_t max)
 379 {
 380   tarval tv;
 381   char *value;
 382   ir_mode mode;
 383   unsigned len;
 384   tarval_mode_info modinfo;
 385
 386   {
 387     static int initialized = 0;
 388
 389     if (! initialized) {
 390       /* from init_tarval_1() */
 391       init_strcalc(68);
 392       init_fltcalc(0);
 393
 394       initialized = 1;
 395     }
 396   }
 397
 398   if (copy_from_debuggee(addr, pHelper, &tv, sizeof(tv)) != S_OK)
 399     return E_FAIL;
 400
 401   /* ir_mode */
 402   if (tv.mode == NULL)
 403     return E_FAIL;
 404
 405   if (copy_from_debuggee(tv.mode, pHelper, &mode, sizeof(mode)) != S_OK)
 406     return E_FAIL;
 407
 408   tv.mode = &mode;
 409
 410   if (mode_is_int(&mode)) {
 411     switch (nBase) {
 412     case 16:
 413       modinfo.mode_output = TVO_HEX;
 414       modinfo.mode_prefix = "0x";
 415       modinfo.mode_suffix = "";
 416       break;
 417     case 8:
 418       modinfo.mode_output = TVO_OCTAL;
 419       modinfo.mode_prefix = "0";
 420       modinfo.mode_suffix = "";
 421       break;
 422     default:
 423       modinfo.mode_output = TVO_DECIMAL;
 424       modinfo.mode_prefix = "";
 425       modinfo.mode_suffix = "";
 426     }
 427   }
 428   else {
 429     if (mode.tv_priv) {
 430       if (copy_from_debuggee(mode.tv_priv, pHelper, &modinfo, sizeof(modinfo)) != S_OK)
 431         return E_FAIL;
 432
 433       get_string(modinfo.mode_prefix);
 434       get_string(modinfo.mode_suffix);
 435     }
 436   }
 437   mode.tv_priv = &modinfo;
 438
 439   len = tv.length;
 440   if (len) {
 441     if (len > 256)
 442       return E_FAIL;
 443
 444     value = alloca(len);
 445
 446     if (copy_from_debuggee(tv.value, pHelper, value, len) != S_OK)
 447       return E_FAIL;
 448
 449     tv.value = value;
 450
 451     tarval_snprintf(pResult, max, &tv);
 452   }
 453   else {
 454     /* might be a reserved tarval */
 455     int resid = PTR_TO_INT(tv.value);
 456
 457     switch (resid) {
 458     case resid_tarval_bad:
 459       _tcsncat(pResult, "BAD", max);
 460       break;
 461     case resid_tarval_undefined:
 462       _tcsncat(pResult, "UNDEF", max);
 463       break;
 464     case resid_tarval_b_false:
 465       _tcsncat(pResult, "FALSE", max);
 466       break;
 467     case resid_tarval_b_true:
 468       _tcsncat(pResult, "TRUE", max);
 469       break;
 470     default:
 471       /* try it */
 472       tarval_snprintf(pResult, max, &tv);
 473     }
 474   }
 475   return S_OK;
 476 }
 477
 478 /**
 479  * format an ir_node
 480  */
 481 static HRESULT format_node(DEBUGHELPER *pHelper, int nBase, const void *addr, char *pResult, size_t max, int top)
 482 {
 483   ir_node n;
 484   char name[256];
 485   ir_op op;
 486
 487   if (copy_from_debuggee(addr, pHelper, &n, sizeof(n)) != S_OK)
 488     return E_FAIL;
 489
 490   /* ir_op */
 491   if (format_op(pHelper, n.op, pResult, max) != S_OK)
 492     return E_FAIL;
 493
 494   /* ir_mode */
 495   if (format_mode(pHelper, n.mode, name, sizeof(name)) != S_OK)
 496     return E_FAIL;
 497   _tcsncat(pResult, name, max);
 498
 499   if (copy_from_debuggee(n.op, pHelper, &op, sizeof(op)) != S_OK)
 500     return E_FAIL;
 501
 502   /* show show node attributes */
 503   switch (op.code) {
 504   case iro_Const:
 505     if (format_tarval(pHelper, nBase, n.attr.con.tarval, name, sizeof(name)) != S_OK) {
 506       _tcsncat(pResult, "<???>", max);
 507     }
 508     else {
 509       _tcsncat(pResult, "<", max);
 510       _tcsncat(pResult, name, max);
 511       _tcsncat(pResult, ">", max);
 512     }
 513     break;
 514   case iro_SymConst:
 515     _tcsncat(pResult, "<", max);
 516     switch (n.attr.symc.kind) {
 517     case symconst_type_size:
 518       _tcsncat(pResult, "SIZE:", max);
 519       if (format_type(pHelper, nBase, n.attr.symc.sym.type_p, name, sizeof(name), 0) != S_OK)
 520         return E_FAIL;
 521       _tcsncat(pResult, name, max);
 522       break;
 523     case symconst_type_align:
 524       _tcsncat(pResult, "ALGN:", max);
 525       if (format_type(pHelper, nBase, n.attr.symc.sym.type_p, name, sizeof(name), 0) != S_OK)
 526         return E_FAIL;
 527       _tcsncat(pResult, name, max);
 528       break;
 529     case symconst_addr_ent:
 530       _tcsncat(pResult, "ENT:", max);
 531       if (format_entity(pHelper, nBase, n.attr.symc.sym.entity_p, name, sizeof(name), 0) != S_OK)
 532         return E_FAIL;
 533       _tcsncat(pResult, name, max);
 534       break;
 535     }
 536     _tcsncat(pResult, ">", max);
 537     break;
 538   case iro_Sel:
 539     _tcsncat(pResult, "<", max);
 540     if (format_entity(pHelper, nBase, n.attr.sel.entity, name, sizeof(name), 0) != S_OK)
 541       return E_FAIL;
 542     _tcsncat(pResult, name, max);
 543     _tcsncat(pResult, ">", max);
 544     break;
 545   case iro_Cast:
 546     _tcsncat(pResult, "<", max);
 547     if (format_type(pHelper, nBase, n.attr.cast.type, name, sizeof(name), 0) != S_OK)
 548       return E_FAIL;
 549     _tcsncat(pResult, name, max);
 550     _tcsncat(pResult, ">", max);
 551     break;
 552   case iro_Alloc:
 553     _tcsncat(pResult, "<", max);
 554     if (format_type(pHelper, nBase, n.attr.alloc.type, name, sizeof(name), 0) != S_OK)
 555       return E_FAIL;
 556     _tcsncat(pResult, name, max);
 557     _snprintf(name, sizeof(name), ", %s", n.attr.alloc.where == stack_alloc ? "stack" : "heap");
 558     _tcsncat(pResult, name, max);
 559     _tcsncat(pResult, ">", max);
 560     break;
 561   case iro_Free:
 562     _tcsncat(pResult, "<", max);
 563     if (format_type(pHelper, nBase, n.attr.free.type, name, sizeof(name), 0) != S_OK)
 564       return E_FAIL;
 565     _tcsncat(pResult, name, max);
 566     _snprintf(name, sizeof(name), ", %s", n.attr.free.where == stack_alloc ? "stack" : "heap");
 567     _tcsncat(pResult, name, max);
 568     _tcsncat(pResult, ">", max);
 569     break;
 570   case iro_CopyB:
 571     _tcsncat(pResult, "<", max);
 572     if (format_type(pHelper, nBase, n.attr.copyb.type, name, sizeof(name), 0) != S_OK)
 573       return E_FAIL;
 574     _tcsncat(pResult, name, max);
 575     _tcsncat(pResult, ">", max);
 576     break;
 577   }
 578
 579   switch (nBase) {
 580   case 16:
 581     _snprintf(name, sizeof(name), " [0x%lx:0x%x]", n.node_nr, n.node_idx);
 582     break;
 583   case 8:
 584     _snprintf(name, sizeof(name), " [0%lo:0%o]", n.node_nr, n.node_idx);
 585     break;
 586   default:
 587     _snprintf(name, sizeof(name), " [%ld:%u]", n.node_nr, n.node_idx);
 588   }
 589   _tcsncat(pResult, name, max);
 590
 591   return S_OK;
 592 }
 593
 594 /**
 595  * format a loop
 596  */
 597 static HRESULT format_loop(DEBUGHELPER *pHelper, const void *addr, char *pResult, size_t max)
 598 {
 599   ir_loop loop;
 600
 601   if (copy_from_debuggee(addr, pHelper, &loop, sizeof(loop)) != S_OK)
 602     return E_FAIL;
 603   return E_FAIL;
 604 }
 605
 606 /**
 607  * Get an array descriptor
 608  */
 609 static HRESULT get_array_desc(DEBUGHELPER *pHelper, const void *address, ir_arr_descr *desc)
 610 {
 611   address = ARR_DESCR(address);
 612   if (copy_from_debuggee(address, pHelper, desc, sizeof(*desc)) != S_OK)
 613     return E_FAIL;
 614
 615   return S_OK;
 616 }
 617
 618 /**
 619  * format a ir_prog
 620  */
 621 static HRESULT format_prog(DEBUGHELPER *pHelper, int nBase, const void *addr, char *pResult, size_t max)
 622 {
 623   ir_prog irp;
 624   ir_arr_descr graphs, types;
 625   char name[256];
 626
 627   if (copy_from_debuggee(addr, pHelper, &irp, sizeof(irp)) != S_OK)
 628     return E_FAIL;
 629   if (irp.graphs) {
 630     if (get_array_desc(pHelper, irp.graphs, &graphs) != S_OK)
 631       return E_FAIL;
 632
 633     irp.graphs = (ir_graph**)&graphs.v.elts;
 634   }
 635
 636   if (irp.types) {
 637     if (get_array_desc(pHelper, irp.types, &types) != S_OK)
 638       return E_FAIL;
 639
 640     irp.types = (ir_type**)&types.v.elts;
 641   }
 642
 643   switch (nBase) {
 644   case 16:
 645     _snprintf(name, sizeof(name), "0x%x graphs 0x%x types", ARR_LEN(irp.graphs), ARR_LEN(irp.types));
 646     break;
 647   case 8:
 648     _snprintf(name, sizeof(name), "0%o graphs 0%o types", ARR_LEN(irp.graphs), ARR_LEN(irp.types));
 649     break;
 650   default:
 651     _snprintf(name, sizeof(name), "%d graphs %d types", ARR_LEN(irp.graphs), ARR_LEN(irp.types));
 652   }
 653   _tcsncpy(pResult, name, max);
 654
 655   return S_OK;
 656 }
 657
 658 /*
 659  * Format an array descriptor
 660  */
 661 HRESULT format_arr_descr(DEBUGHELPER *pHelper, int nBase, const void *addr, char *pResult, size_t max)
 662 {
 663   ir_arr_descr desc;
 664   char name[256];
 665
 666   if (copy_from_debuggee(addr, pHelper, &desc, sizeof(desc)) != S_OK)
 667     return E_FAIL;
 668
 669   switch (desc.magic) {
 670   case ARR_D_MAGIC:
 671     _tcsncpy(pResult, "DynArr ", max); break;
 672   case ARR_A_MAGIC:
 673     _tcsncpy(pResult, "AutoArr ", max); break;
 674   case ARR_F_MAGIC:
 675     _tcsncpy(pResult, "FlexArr ", max); break;
 676   default:
 677     _tcsncpy(pResult, "UNKN ", max);
 678   }
 679
 680   switch (nBase) {
 681   case 16:
 682     _snprintf(name, sizeof(name), "nelts 0x%x", desc.nelts);
 683     break;
 684   case 8:
 685     _snprintf(name, sizeof(name), "nelts 0%o", desc.nelts);
 686     break;
 687   default:
 688     _snprintf(name, sizeof(name), "nelts %d", desc.nelts);
 689   }
 690   _tcsncat(pResult, name, max);
 691
 692   return S_OK;
 693 }
 694
 695 /*
 696  * format a firm object
 697  */
 698 HRESULT FormatFirmObject(DEBUGHELPER *pHelper, int nBase, firm_kind kind, const void *addr, char *pResult, size_t max)
 699 {
 700   switch (kind) {
 701   case k_entity:     /* an entity */
 702     return format_entity(pHelper, nBase, addr, pResult, max, 1);
 703   case k_type:       /* a type */
 704     return format_type(pHelper, nBase, addr, pResult, max, 1);
 705   case k_ir_graph:   /* an ir graph */
 706     return format_irg(pHelper, nBase, addr, pResult, max, 1);
 707   case k_ir_node:    /* an ir node */
 708     return format_node(pHelper, nBase, addr, pResult, max, 1);
 709   case k_ir_mode:    /* an ir mode */
 710     return format_mode(pHelper, addr, pResult, max);
 711   case k_ir_op:      /* an ir opcode */
 712     return format_op(pHelper, addr, pResult, max);
 713   case k_tarval:     /* a tarval */
 714     return format_tarval(pHelper, nBase, addr, pResult, max);
 715   case k_ir_loop:    /* a loop */
 716     return format_loop(pHelper, addr, pResult, max);
 717   case k_ir_prog:    /* a program representation (irp) */
 718     return format_prog(pHelper, nBase, addr, pResult, max);
 719   default:
 720     return E_FAIL;
 721   }
 722 }
 723
 724 #define SEGMENT_SIZE_SHIFT      8
 725 #define SEGMENT_SIZE            (1 << SEGMENT_SIZE_SHIFT)
 726 #define DIRECTORY_SIZE_SHIFT    8
 727 #define DIRECTORY_SIZE          (1 << DIRECTORY_SIZE_SHIFT)
 728 #define MAX_LOAD_FACTOR         4
 729
 730 typedef struct pset_element {
 731   struct pset_element *chain;   /**< for chaining Elements */
 732   pset_entry entry;
 733 } pset_Element, *pset_Segment;
 734
 735 /* not visible from outside */
 736 struct pset {
 737   unsigned p;              /**< Next bucket to be split */
 738   unsigned maxp;           /**< upper bound on p during expansion */
 739   unsigned nkey;           /**< current # keys */
 740   unsigned nseg;           /**< current # segments */
 741   pset_Segment *dir[DIRECTORY_SIZE];
 742   int (*cmp)();            /**< function comparing entries */
 743   unsigned iter_i, iter_j;
 744   pset_Element *iter_tail; /**< non-NULL while iterating over elts */
 745   pset_Element *free_list; /**< list of free Elements */
 746   struct obstack obst;     /**< obstack for allocation all data */
 747 };
 748
 749 typedef struct set_element {
 750   struct set_element *chain;    /**< for chaining Elements */
 751   set_entry entry;
 752 } set_Element, *set_Segment;
 753
 754 /* not visible from outside */
 755 struct set {
 756   unsigned p;              /**< Next bucket to be split */
 757   unsigned maxp;           /**< upper bound on p during expansion */
 758   unsigned nkey;           /**< current # keys */
 759   unsigned nseg;           /**< current # segments */
 760   set_Segment *dir[DIRECTORY_SIZE];
 761   int (*cmp)();            /**< function comparing entries */
 762   unsigned iter_i, iter_j;
 763   set_Element *iter_tail;  /**< non-NULL while iterating over elts */
 764   struct obstack obst;     /**< obstack for allocation all data */
 765 };
 766
 767 /**
 768  * Find the longest chain of a pset
 769  */
 770 static HRESULT find_longest_pset_chain(DEBUGHELPER *pHelper, pset *set,
 771                                        int *chains, int *lenght, size_t *size)
 772 {
 773   unsigned i, j;
 774   pset_Segment *seg, *curr;
 775   pset_Element elem;
 776   void *address;
 777   int len, nchains = 0, max_len = 0;
 778   size_t dyns = 0;
 779
 780   for (i = 0; i < set->nseg; ++i) {
 781     seg = set->dir[i];
 782
 783     dyns += sizeof(seg[j]) * SEGMENT_SIZE;
 784     for (j = 0; j < SEGMENT_SIZE; ++j) {
 785       if (copy_from_debuggee(&seg[j], pHelper, &curr, sizeof(curr)) != S_OK)
 786         return E_FAIL;
 787
 788       address = curr;
 789       if (address)
 790         ++nchains;
 791       for (len = 0; address != NULL; address = elem.chain) {
 792         if (copy_from_debuggee(address, pHelper, &elem, sizeof(elem)) != S_OK)
 793           return E_FAIL;
 794         dyns += sizeof(pset_Element);
 795         ++len;
 796       }
 797       if (len > max_len)
 798         max_len = len;
 799     }
 800   }
 801
 802   *chains = nchains;
 803   *lenght = max_len;
 804   *size   = dyns;
 805   return S_OK;
 806 }
 807
 808 /**
 809  * Find the longest chain of a set
 810  */
 811 static HRESULT find_longest_set_chain(DEBUGHELPER *pHelper, set *set,
 812                                       int *chains, int *lenght, size_t *size)
 813 {
 814   unsigned i, j;
 815   set_Segment *seg, *curr;
 816   set_Element elem;
 817   void *address;
 818   int len, nchains = 0, max_len = 0;
 819   size_t dyns = 0;
 820
 821   for (i = 0; i < set->nseg; ++i) {
 822     seg = set->dir[i];
 823
 824     dyns += sizeof(seg[j]) * SEGMENT_SIZE;
 825     for (j = 0; j < SEGMENT_SIZE; ++j) {
 826       if (copy_from_debuggee(&seg[j], pHelper, &curr, sizeof(curr)) != S_OK)
 827           return E_FAIL;
 828
 829       address = curr;
 830       if (address)
 831         ++nchains;
 832       for (len = 0; address != NULL; address = elem.chain) {
 833         if (copy_from_debuggee(address, pHelper, &elem, sizeof(elem)) != S_OK)
 834           return E_FAIL;
 835         dyns += offsetof(set_Element, entry.dptr) + elem.entry.size;
 836         ++len;
 837       }
 838       if (len > max_len)
 839         max_len = len;
 840     }
 841   }
 842
 843   *chains = nchains;
 844   *lenght = max_len;
 845   *size   = dyns;
 846   return S_OK;
 847 }
 848
 849 /*
 850  * Format a pset
 851  */
 852 HRESULT format_pset(DEBUGHELPER *pHelper, int nBase, const void *address, char *pResult, size_t max)
 853 {
 854   pset set;
 855   char name[256];
 856   int nchains, chain_len;
 857   size_t size;
 858
 859   if (copy_from_debuggee(address, pHelper, &set, sizeof(set)) != S_OK)
 860     return E_FAIL;
 861
 862   if (find_longest_pset_chain(pHelper, &set, &nchains, &chain_len, &size) != S_OK)
 863     return E_FAIL;
 864
 865   switch (nBase) {
 866   case 16:
 867     _snprintf(name, sizeof(name), "nkey 0x%x nseg 0x%x nchain 0x%x maxlen 0x%x size %u kB", set.nkey, set.nseg, nchains, chain_len, (size + 1023) >> 10);
 868     break;
 869   case 8:
 870     _snprintf(name, sizeof(name), "nkey 0%o nseg 0%o nchain 0%o maxlen 0%o size %u kB", set.nkey, set.nseg, nchains, chain_len, (size + 1023) >> 10);
 871     break;
 872   default:
 873     _snprintf(name, sizeof(name), "nkey %u nseg %d nchain %d maxlen %d size %u kB", set.nkey, set.nseg, nchains, chain_len, (size + 1023) >> 10);
 874   }
 875   _tcsncpy(pResult, name, max);
 876
 877   return S_OK;
 878 }
 879
 880 /*
 881  * Format a set
 882  */
 883 HRESULT format_set(DEBUGHELPER *pHelper, int nBase, const void *address, char *pResult, size_t max)
 884 {
 885   set set;
 886   char name[256];
 887   int nchains, chain_len;
 888   size_t size;
 889
 890   if (copy_from_debuggee(address, pHelper, &set, sizeof(set)) != S_OK)
 891     return E_FAIL;
 892
 893   if (find_longest_set_chain(pHelper, &set, &nchains, &chain_len, &size) != S_OK)
 894     return E_FAIL;
 895
 896   switch (nBase) {
 897   case 16:
 898     _snprintf(name, sizeof(name), "nkey 0x%x nseg 0x%x nchain 0x%x maxlen 0x%x size %u kB", set.nkey, set.nseg, nchains, chain_len, (size + 1023) >> 10);
 899     break;
 900   case 8:
 901     _snprintf(name, sizeof(name), "nkey 0%o nseg 0%o nchain 0%o maxlen 0%o size %u kB", set.nkey, set.nseg, nchains, chain_len, (size + 1023) >> 10);
 902     break;
 903   default:
 904     _snprintf(name, sizeof(name), "nkey %u nseg %d nchain %d maxlen %d size %u kB", set.nkey, set.nseg, nchains, chain_len, (size + 1023) >> 10);
 905   }
 906   _tcsncpy(pResult, name, max);
 907
 908   return S_OK;
 909 }
 910
 911 struct pdeq {
 912   unsigned magic;       /**< debug magic, only available in DEBUG builds */
 913   pdeq *l_end, *r_end;  /**< left and right ends of the queue */
 914   pdeq *l, *r;          /**< left and right neighbor */
 915   int n;                /**< number of elements in the current chunk */
 916   int p;                /**< the read/write pointer */
 917   const void *data[1];  /**< storage for elements */
 918 };
 919
 920 /** Returns the length of a double ended pointer list. */
 921 static int get_pdeq_len(DEBUGHELPER *pHelper, pdeq *dq)
 922 {
 923   int n;
 924   pdeq *q;
 925   pdeq pdeq;
 926
 927   n = 0;
 928   q = dq->l_end;
 929
 930   if (copy_from_debuggee(q, pHelper, &pdeq, sizeof(pdeq)) != S_OK)
 931     return -1;
 932   q = &pdeq;
 933
 934   for (;;) {
 935     n += q->n;
 936     q = q->r;
 937     if (! q)
 938       break;
 939
 940     if (copy_from_debuggee(q, pHelper, &pdeq, sizeof(pdeq)) != S_OK)
 941       return -1;
 942     q = &pdeq;
 943   };
 944
 945   return n;
 946 }
 947
 948 /*
 949  * Format a pdeq
 950  */
 951 HRESULT format_pdeq(DEBUGHELPER *pHelper, int nBase, const void *address, char *pResult, size_t max)
 952 {
 953   pdeq pdeq;
 954   char name[256];
 955   int len;
 956
 957   if (copy_from_debuggee(address, pHelper, &pdeq, sizeof(pdeq)) != S_OK)
 958     return E_FAIL;
 959
 960   len = get_pdeq_len(pHelper, &pdeq);
 961   if (len < 0)
 962     return E_FAIL;
 963
 964   switch (nBase) {
 965   case 16:
 966     _snprintf(name, sizeof(name), "pdeq 0x%x elem", len);
 967     break;
 968   case 8:
 969     _snprintf(name, sizeof(name), "pdeq 0%o elem", len);
 970     break;
 971   default:
 972     _snprintf(name, sizeof(name), "pdeq %d elem", len);
 973   }
 974   _tcsncpy(pResult, name, max);
 975
 976   return S_OK;
 977 }
 978
 979 /** show the first 2 units */
 980 static HRESULT fill_bits(DEBUGHELPER *pHelper, bitset_t *bs, char *pResult)
 981 {
 982   unsigned i, units = bs->size;
 983   int l = 0, o = 0, breaked = 0;
 984   unsigned j;
 985
 986   for (i = 0; i < units; ++i) {
 987     unsigned data;
 988
 989     if (copy_from_debuggee((void *)(&bs->data[i]), pHelper, &data, sizeof(data)) != S_OK)
 990       return E_FAIL;
 991
 992     for (j = 0; j < 32; ++j) {
 993       if (data & (1 << j)) {
 994         sprintf(pResult + l, "%d,", i * sizeof(data) * 8 + j);
 995         l += strlen(pResult + l);
 996         ++o;
 997         if (o >= 10) {
 998           breaked = 1;
 999           goto end;
1000         }
1001       }
1002     }
1003   }
1004 end:
1005   if (breaked) {
1006     sprintf(pResult + l, "...");
1007     l += 3;
1008   }
1009   sprintf(pResult + l, "}");
1010   return S_OK;
1011 }
1012
1013 /*
1014  * Format a bitset
1015  */
1016 HRESULT format_bitset(DEBUGHELPER *pHelper, int nBase, const void *address, char *pResult, size_t max)
1017 {
1018   bitset_t bs;
1019   char name[256];
1020   unsigned l;
1021
1022   if (copy_from_debuggee(address, pHelper, &bs, sizeof(bs)) != S_OK)
1023     return E_FAIL;
1024
1025   switch (nBase) {
1026   case 16:
1027     _snprintf(name, sizeof(name), "bitset{0x%x:", bs.size);
1028     break;
1029   case 8:
1030     _snprintf(name, sizeof(name), "bitset{0%o:", bs.size);
1031     break;
1032   default:
1033     _snprintf(name, sizeof(name), "bitset{%u:", bs.size);
1034   }
1035
1036   l = strlen(name);
1037   if (fill_bits(pHelper, &bs, &name[l]) != S_OK)
1038     return E_FAIL;
1039
1040
1041   _tcsncpy(pResult, name, max);
1042
1043   return S_OK;
1044 }