firm.c 27.9 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
 * Firm - Evaluator
 *
 * (C) 2005 Michael Beck    beck@ipd.info.uni-karlsruhe.de
 */
#define WIN32_LEAN_AND_MEAN
#include <windows.h>
#include <tchar.h>
#include <malloc.h>
#include <stdarg.h>

#include "config.h"

/* ugly, but I must include array.h WITHOUT NDEBUG */
#ifdef NDEBUG
#undef NDEBUG
#include "array_t.h"
#define NDEBUG
#else
20
#include "array_t.h"
21
22
23
24
25
26
27
28
29
30
#endif

#include "entity_t.h"
#include "irgraph_t.h"
#include "irnode_t.h"
#include "irmode_t.h"
#include "tv_t.h"
#include "irloop_t.h"
#include "irextbb_t.h"
#include "irprog_t.h"
31
#include "compound_path_t.h"
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include "tpop_t.h"
#include "strcalc.h"
#include "fltcalc.h"

#include "set.h"
#include "pset.h"
#include "pdeq.h"
#include "bitset.h"

#include "firmEvaluator.h"

/** get the address of a pointer */
#define ADD_ADR(p, off)  ((void *)((char *)(p) + (off)))

/** debug output */
47
48
static void debug(char *fmt, ...)
{
49
50
51
52
53
54
55
56
57
58
59
60
61
  va_list ap;
  char buf[1024];

  va_start(ap, fmt);
  vsprintf(buf, fmt, ap);

  OutputDebugString(buf);
  va_end(ap);
}  /* debug */

/**
 * return the size of a firm object
 */
62
63
int get_firm_object_size(firm_kind kind)
{
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
  switch (kind) {
  case k_entity:     /* an entity */
    return sizeof(ir_entity);
  case k_type:       /* a type */
    return sizeof(ir_type);
  case k_ir_graph:   /* an ir graph */
    return sizeof(ir_graph);
  case k_ir_node:    /* an ir node */
    return sizeof(ir_node);
  case k_ir_mode:    /* an ir mode */
    return sizeof(ir_mode);
  case k_ir_op:      /* an ir opcode */
    return sizeof(ir_op);
  case k_tarval:     /* a tarval */
    return sizeof(tarval);
  case k_ir_loop:    /* a loop */
    return sizeof(ir_loop);
  case k_ir_compound_graph_path: /* a compound graph path, see entity.h */
    return sizeof(compound_graph_path);
  case k_ir_extblk:  /* an extended block */
    return sizeof(ir_extblk);
  case k_ir_prog:    /* a program representation (irp) */
    return sizeof(ir_prog);
  default:
    return 0;
  }
}  /* get_firm_object_size */

/**
 * returns the string length of a string in debuggee space
 *
 * @return string length or negative value on error
 */
static int strlen_debuggee(DEBUGHELPER *pHelper, const void *address, size_t max)
{
  size_t i;
  char v;
  const char *p = address;

  for (i = 0; i < max; ++i) {
    if (copy_from_debuggee(p + i, pHelper, &v, sizeof(v)) != S_OK)
      return -1;

    if (! v)
      return i;
  }
  return i;
}  /* strlen_debuggee */

/**
 * Format an ident
 */
116
117
HRESULT format_ident(DEBUGHELPER *pHelper, const void *address, char *pResult, size_t max)
{
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
  set_entry *data = NULL;
  set_entry id;
  size_t len, slen;

  if (copy_from_debuggee(address, pHelper, &id, sizeof(id)) != S_OK)
    return E_FAIL;

  /* safety check */
  if (id.size < 1 || id.size > 256)
    return E_FAIL;

  slen = id.size + 1;
  len = offsetof(set_entry, dptr) + slen;

  data = alloca(len);

  if (copy_from_debuggee(address, pHelper, data, len) != S_OK)
    return E_FAIL;

  _tcsncpy(pResult, (const char *)data->dptr, max);
  return S_OK;
}  /* format_ident */

/**
 * Format a tp_op
 */
static HRESULT format_tp_op(DEBUGHELPER *pHelper, const void *addr, char *pResult, size_t max)
{
  tp_op op;

#define X(a)     case tpo_##a: _tcsncpy(pResult, #a, max); return S_OK
#define Y(a, b)  case tpo_##a: _tcsncpy(pResult, b, max); return S_OK

  if (copy_from_debuggee(addr, pHelper, &op, sizeof(op)) != S_OK)
    return E_FAIL;

  switch (op.code) {
  X(uninitialized);
  X(class);
  X(struct);
  X(method);
  X(union);
  X(array);
  Y(enumeration, "enum");
  Y(pointer, "ptr");
  Y(primitive, "prim");
  X(none);
  X(unknown);
  default:
    return E_FAIL;
  }
#undef X
#undef Y
}  /* format_tp_op */

/**
 * Checks whether a type is the global type
 *
 * @param type  the address of the type in debuggee's space
 */
178
179
static HRESULT is_global_type(DEBUGHELPER *pHelper, const void *type, int *flag)
{
180
181
182
183
184
185
186
187
188
189
190
191
192
  ir_type tp;

  *flag = 0;
  if (copy_from_debuggee(type, pHelper, &tp, sizeof(tp)) != S_OK)
    return E_FAIL;

  *flag = tp.flags & tf_global_type;
  return S_OK;
}  /* is_global_type */

/**
 * format an entity
 */
193
194
static HRESULT format_entity(DEBUGHELPER *pHelper, int nBase, const void *addr, char *pResult, size_t max, int top)
{
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
  ir_entity ent;
  ir_type owner;
  char name[256];
  int is_global;

  if (copy_from_debuggee(addr, pHelper, &ent, sizeof(ent)) != S_OK) {
    return E_FAIL;
  }
  if (is_global_type(pHelper, ent.owner, &is_global) != S_OK)
    return E_FAIL;

  *pResult = '\0';
  if (top)
    _tcsncpy(pResult, "ENT: ", max);

  if (! is_global) {
    if (copy_from_debuggee(ent.owner, pHelper, &owner, sizeof(owner)) != S_OK)
      return E_FAIL;
    if (format_ident(pHelper, (void *)owner.name, name, sizeof(name)) != S_OK)
      return E_FAIL;
    _tcsncat(pResult, name, max);
    _tcsncat(pResult, "::", max);
  }

  if (format_ident(pHelper, (void *)ent.name, name, sizeof(name)) != S_OK)
    return E_FAIL;
  _tcsncat(pResult, name, max);

  switch (nBase) {
  case 16:
    _snprintf(name, sizeof(name), " [0x%lx]", ent.nr);
    break;
  case 8:
    _snprintf(name, sizeof(name), " [0%lo]", ent.nr);
    break;
  default:
    _snprintf(name, sizeof(name), " [%ld]", ent.nr);
  }
  _tcsncat(pResult, name, max);

  return S_OK;
}  /* format_entity */

Michael Beck's avatar
Michael Beck committed
238
239
240
241
242
243
244
245
246
247
248
249
250
251
/**
 * format an ir_mode
 */
static HRESULT format_mode(DEBUGHELPER *pHelper, const void *addr, char *pResult, size_t max)
{
  ir_mode mode;

  if (copy_from_debuggee(addr, pHelper, &mode, sizeof(mode)) != S_OK)
    return E_FAIL;
  if (format_ident(pHelper, mode.name, pResult, max) != S_OK)
    return E_FAIL;
  return S_OK;
}  /* format_mode */

252
253
254
/**
 * format a type
 */
255
256
static HRESULT format_type(DEBUGHELPER *pHelper, int nBase, const void *addr, char *pResult, size_t max, int top)
{
257
258
259
260
261
262
263
264
265
266
267
268
269
270
  ir_type tp;
  char name[256];

  if (copy_from_debuggee(addr, pHelper, &tp, sizeof(tp)) != S_OK)
    return E_FAIL;

  pResult[0] = '\0';
  if (top) {
    if (format_tp_op(pHelper, tp.type_op, pResult, max) != S_OK)
      return E_FAIL;

    _tcsncat(pResult, " ", max);
  }

Michael Beck's avatar
Michael Beck committed
271
272
273
274
275
276
277
278
  name[0] = '\0';
  if (tp.name) {
    if (format_ident(pHelper, tp.name, name, sizeof(name)) != S_OK)
      return E_FAIL;
  } else {
    if (format_mode(pHelper, tp.mode, name, sizeof(name)) != S_OK)
      return E_FAIL;
  }
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298

  _tcsncat(pResult, name, max);
  switch (nBase) {
  case 16:
    _snprintf(name, sizeof(name), " [0x%lx]", tp.nr);
    break;
  case 8:
    _snprintf(name, sizeof(name), " [0%lo]", tp.nr);
    break;
  default:
    _snprintf(name, sizeof(name), " [%ld]", tp.nr);
  }
  _tcsncat(pResult, name, max);

  return S_OK;
}  /* format_type */

/**
 * format an irg
 */
299
300
static HRESULT format_irg(DEBUGHELPER *pHelper, int nBase, const void *addr, char *pResult, size_t max, int top)
{
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
  ir_graph irg;
  char name[256];

  if (copy_from_debuggee(addr, pHelper, &irg, sizeof(irg)) != S_OK)
    return E_FAIL;

  *pResult = '\0';
  if (top)
    _tcsncpy(pResult, "IRG: ", max);

  if (irg.ent) {
    ir_entity ent;
    ir_type owner;
    int is_global;

    if (copy_from_debuggee(irg.ent, pHelper, &ent, sizeof(ent)) != S_OK)
      return E_FAIL;
    if (is_global_type(pHelper, ent.owner, &is_global) != S_OK)
      return E_FAIL;
    if (! is_global) {
      if (copy_from_debuggee(ent.owner, pHelper, &owner, sizeof(owner)) != S_OK)
        return E_FAIL;
      if (format_ident(pHelper, (void *)owner.name, name, sizeof(name)) != S_OK)
        return E_FAIL;
      _tcsncat(pResult, name, max);
      _tcsncat(pResult, "::", max);
    }
    if (format_ident(pHelper, ent.name, name, sizeof(name)) != S_OK)
      return E_FAIL;
    _tcsncat(pResult, name, max);
  }
  else
    _tcsncat(pResult, "NULL", max);

  switch (nBase) {
  case 16:
    _snprintf(name, sizeof(name), " [0x%lx, 0x%u nodes]", irg.graph_nr, irg.last_node_idx);
    break;
  case 8:
    _snprintf(name, sizeof(name), " [0%lo, 0%o nodes]", irg.graph_nr, irg.last_node_idx);
    break;
  default:
    _snprintf(name, sizeof(name), " [%ld, %u nodes]", irg.graph_nr, irg.last_node_idx);
  }
  _tcsncat(pResult, name, max);
  return S_OK;
}  /* format_irg */

/**
 * format an ir_op
 */
352
353
HRESULT format_op(DEBUGHELPER *pHelper, const void *addr, char *pResult, size_t max)
{
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
  ir_op op;

  if (copy_from_debuggee(addr, pHelper, &op, sizeof(op)) != S_OK)
    return E_FAIL;
  if (format_ident(pHelper, op.name, pResult, max) != S_OK)
    return E_FAIL;
  return S_OK;
}  /* format_op */

/** get a temporary string */
#define get_string(str)                                         \
do {                                                            \
  int len;                                                      \
  char *s;                                                      \
  if (str) {                                                    \
    len = strlen_debuggee(pHelper, str, 256);                   \
    if (len < 0)                                                \
      return E_FAIL;                                            \
    s = alloca(len + 1);                                        \
    if (copy_from_debuggee(str, pHelper, s, (DWORD)len) != S_OK) \
      return E_FAIL;                                            \
    s[len] = '\0';                                              \
    str = s;                                                    \
  }                                                             \
378
} while (0)
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485

/**
 * format a tarval
 */
static HRESULT format_tarval(DEBUGHELPER *pHelper, int nBase, const void *addr, char *pResult, size_t max)
{
  tarval tv;
  char *value;
  ir_mode mode;
  unsigned len;
  tarval_mode_info modinfo;

  {
    static int initialized = 0;

    if (! initialized) {
      /* from init_tarval_1() */
      init_strcalc(68);
      init_fltcalc(0);

      initialized = 1;
    }
  }

  if (copy_from_debuggee(addr, pHelper, &tv, sizeof(tv)) != S_OK)
    return E_FAIL;

  /* ir_mode */
  if (tv.mode == NULL)
    return E_FAIL;

  if (copy_from_debuggee(tv.mode, pHelper, &mode, sizeof(mode)) != S_OK)
    return E_FAIL;

  tv.mode = &mode;

  if (mode_is_int(&mode)) {
    switch (nBase) {
    case 16:
      modinfo.mode_output = TVO_HEX;
      modinfo.mode_prefix = "0x";
      modinfo.mode_suffix = "";
      break;
    case 8:
      modinfo.mode_output = TVO_OCTAL;
      modinfo.mode_prefix = "0";
      modinfo.mode_suffix = "";
      break;
    default:
      modinfo.mode_output = TVO_DECIMAL;
      modinfo.mode_prefix = "";
      modinfo.mode_suffix = "";
    }
  }
  else {
    if (mode.tv_priv) {
      if (copy_from_debuggee(mode.tv_priv, pHelper, &modinfo, sizeof(modinfo)) != S_OK)
        return E_FAIL;

      get_string(modinfo.mode_prefix);
      get_string(modinfo.mode_suffix);
    }
  }
  mode.tv_priv = &modinfo;

  len = tv.length;
  if (len) {
    if (len > 256)
      return E_FAIL;

    value = alloca(len);

    if (copy_from_debuggee(tv.value, pHelper, value, len) != S_OK)
      return E_FAIL;

    tv.value = value;

    tarval_snprintf(pResult, max, &tv);
  }
  else {
    /* might be a reserved tarval */
    int resid = PTR_TO_INT(tv.value);

    switch (resid) {
    case resid_tarval_bad:
      _tcsncat(pResult, "BAD", max);
      break;
    case resid_tarval_undefined:
      _tcsncat(pResult, "UNDEF", max);
      break;
    case resid_tarval_b_false:
      _tcsncat(pResult, "FALSE", max);
      break;
    case resid_tarval_b_true:
      _tcsncat(pResult, "TRUE", max);
      break;
    default:
      /* try it */
      tarval_snprintf(pResult, max, &tv);
    }
  }
  return S_OK;
}  /* format_tarval */

/**
 * format an ir_node
 */
486
487
static HRESULT format_node(DEBUGHELPER *pHelper, int nBase, const void *addr, char *pResult, size_t max, int top)
{
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
  ir_node n;
  char name[256];
  ir_op op;

  if (copy_from_debuggee(addr, pHelper, &n, sizeof(n)) != S_OK)
    return E_FAIL;

  /* ir_op */
  if (format_op(pHelper, n.op, pResult, max) != S_OK)
    return E_FAIL;

  /* ir_mode */
  if (format_mode(pHelper, n.mode, name, sizeof(name)) != S_OK)
    return E_FAIL;
  _tcsncat(pResult, name, max);

  if (copy_from_debuggee(n.op, pHelper, &op, sizeof(op)) != S_OK)
    return E_FAIL;

  /* show show node attributes */
  switch (op.code) {
  case iro_Const:
Michael Beck's avatar
Michael Beck committed
510
    if (format_tarval(pHelper, nBase, n.attr.con.tarval, name, sizeof(name)) != S_OK) {
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
      _tcsncat(pResult, "<???>", max);
    }
    else {
      _tcsncat(pResult, "<", max);
      _tcsncat(pResult, name, max);
      _tcsncat(pResult, ">", max);
    }
    break;
  case iro_SymConst:
    _tcsncat(pResult, "<", max);
    switch (n.attr.symc.kind) {
    case symconst_type_size:
      _tcsncat(pResult, "SIZE:", max);
      if (format_type(pHelper, nBase, n.attr.symc.sym.type_p, name, sizeof(name), 0) != S_OK)
        return E_FAIL;
      _tcsncat(pResult, name, max);
      break;
    case symconst_type_align:
      _tcsncat(pResult, "ALGN:", max);
      if (format_type(pHelper, nBase, n.attr.symc.sym.type_p, name, sizeof(name), 0) != S_OK)
        return E_FAIL;
      _tcsncat(pResult, name, max);
      break;
    case symconst_addr_ent:
      _tcsncat(pResult, "ENT:", max);
      if (format_entity(pHelper, nBase, n.attr.symc.sym.entity_p, name, sizeof(name), 0) != S_OK)
        return E_FAIL;
      _tcsncat(pResult, name, max);
      break;
    }
    _tcsncat(pResult, ">", max);
    break;
  case iro_Sel:
    _tcsncat(pResult, "<", max);
545
    if (format_entity(pHelper, nBase, n.attr.sel.entity, name, sizeof(name), 0) != S_OK)
546
547
548
549
550
551
      return E_FAIL;
    _tcsncat(pResult, name, max);
    _tcsncat(pResult, ">", max);
    break;
  case iro_Cast:
    _tcsncat(pResult, "<", max);
552
    if (format_type(pHelper, nBase, n.attr.cast.type, name, sizeof(name), 0) != S_OK)
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
      return E_FAIL;
    _tcsncat(pResult, name, max);
    _tcsncat(pResult, ">", max);
    break;
  case iro_Alloc:
    _tcsncat(pResult, "<", max);
    if (format_type(pHelper, nBase, n.attr.alloc.type, name, sizeof(name), 0) != S_OK)
      return E_FAIL;
    _tcsncat(pResult, name, max);
    _snprintf(name, sizeof(name), ", %s", n.attr.alloc.where == stack_alloc ? "stack" : "heap");
    _tcsncat(pResult, name, max);
    _tcsncat(pResult, ">", max);
    break;
  case iro_Free:
    _tcsncat(pResult, "<", max);
    if (format_type(pHelper, nBase, n.attr.free.type, name, sizeof(name), 0) != S_OK)
      return E_FAIL;
    _tcsncat(pResult, name, max);
    _snprintf(name, sizeof(name), ", %s", n.attr.free.where == stack_alloc ? "stack" : "heap");
    _tcsncat(pResult, name, max);
    _tcsncat(pResult, ">", max);
    break;
  case iro_CopyB:
    _tcsncat(pResult, "<", max);
577
    if (format_type(pHelper, nBase, n.attr.copyb.type, name, sizeof(name), 0) != S_OK)
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
      return E_FAIL;
    _tcsncat(pResult, name, max);
    _tcsncat(pResult, ">", max);
    break;
  }

  switch (nBase) {
  case 16:
    _snprintf(name, sizeof(name), " [0x%lx:0x%x]", n.node_nr, n.node_idx);
    break;
  case 8:
    _snprintf(name, sizeof(name), " [0%lo:0%o]", n.node_nr, n.node_idx);
    break;
  default:
    _snprintf(name, sizeof(name), " [%ld:%u]", n.node_nr, n.node_idx);
  }
  _tcsncat(pResult, name, max);

  return S_OK;
}  /* format_node */

/**
 * format a loop
 */
static HRESULT format_loop(DEBUGHELPER *pHelper, const void *addr, char *pResult, size_t max)
{
  ir_loop loop;

  if (copy_from_debuggee(addr, pHelper, &loop, sizeof(loop)) != S_OK)
    return E_FAIL;
  return E_FAIL;
}  /* format_loop */

/**
 * Get an array descriptor
 */
static HRESULT get_array_desc(DEBUGHELPER *pHelper, const void *address, ir_arr_descr *desc)
{
  address = ARR_DESCR(address);
  if (copy_from_debuggee(address, pHelper, desc, sizeof(*desc)) != S_OK)
    return E_FAIL;

  return S_OK;
}  /* get_array_desc */

/**
 * format an extended block
 */
626
627
static HRESULT format_extblk(DEBUGHELPER *pHelper, int nBase, const void *addr, char *pResult, size_t max)
{
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
  ir_extblk extbb;
  ir_arr_descr blocks;
  ir_node *blks = NULL;
  char name[256];
  int len;

  if (copy_from_debuggee(addr, pHelper, &extbb, sizeof(extbb)) != S_OK)
    return E_FAIL;
  if (extbb.blks == NULL)
    return E_FAIL;

  if (get_array_desc(pHelper, extbb.blks, &blocks) != S_OK)
    return E_FAIL;

  len = ARR_LEN(&blocks.v.elts);

  if (len > 0) {
    if (copy_from_debuggee(extbb.blks, pHelper, &blks, sizeof(blks)) != S_OK)
      return E_FAIL;
  }

  if (blks) {
    switch (nBase) {
    case 16:
      _snprintf(name, sizeof(name), "0x%x 0x%x blocks", blks->node_nr, len);
      break;
    case 8:
      _snprintf(name, sizeof(name), "0%o 0%o blocks", blks->node_nr, len);
      break;
    default:
      _snprintf(name, sizeof(name), "%d %d blocks", blks->node_nr, len);
    }
    _tcsncpy(pResult, name, max);
  }
  else
    _tcsncpy(pResult, "<EMPTY>", max);
  return S_OK;
}  /* format_extblk */


/**
 * format a ir_prog
 */
static HRESULT format_prog(DEBUGHELPER *pHelper, int nBase, const void *addr, char *pResult, size_t max)
{
  ir_prog irp;
  ir_arr_descr graphs, types;
  char name[256];

  if (copy_from_debuggee(addr, pHelper, &irp, sizeof(irp)) != S_OK)
    return E_FAIL;
  if (irp.graphs) {
    if (get_array_desc(pHelper, irp.graphs, &graphs) != S_OK)
      return E_FAIL;

    irp.graphs = (ir_graph**)&graphs.v.elts;
  }

  if (irp.types) {
    if (get_array_desc(pHelper, irp.types, &types) != S_OK)
      return E_FAIL;

    irp.types = (ir_type**)&types.v.elts;
  }

  switch (nBase) {
  case 16:
    _snprintf(name, sizeof(name), "0x%x graphs 0x%x types", ARR_LEN(irp.graphs), ARR_LEN(irp.types));
    break;
  case 8:
    _snprintf(name, sizeof(name), "0%o graphs 0%o types", ARR_LEN(irp.graphs), ARR_LEN(irp.types));
    break;
  default:
    _snprintf(name, sizeof(name), "%d graphs %d types", ARR_LEN(irp.graphs), ARR_LEN(irp.types));
  }
  _tcsncpy(pResult, name, max);

  return S_OK;
}  /* format_prog */

/*
 * Format an array descriptor
 */
HRESULT format_arr_descr(DEBUGHELPER *pHelper, int nBase, const void *addr, char *pResult, size_t max)
{
  ir_arr_descr desc;
  char name[256];

  if (copy_from_debuggee(addr, pHelper, &desc, sizeof(desc)) != S_OK)
    return E_FAIL;

  switch (desc.magic) {
  case ARR_D_MAGIC:
    _tcsncpy(pResult, "DynArr ", max); break;
  case ARR_A_MAGIC:
    _tcsncpy(pResult, "AutoArr ", max); break;
  case ARR_F_MAGIC:
    _tcsncpy(pResult, "FlexArr ", max); break;
  default:
    _tcsncpy(pResult, "UNKN ", max);
  }

  switch (nBase) {
  case 16:
    _snprintf(name, sizeof(name), "nelts 0x%x", desc.nelts);
    break;
  case 8:
    _snprintf(name, sizeof(name), "nelts 0%o", desc.nelts);
    break;
  default:
    _snprintf(name, sizeof(name), "nelts %d", desc.nelts);
  }
  _tcsncat(pResult, name, max);

  return S_OK;
}  /* format_arr_descr */

/*
 * format a firm object
 */
HRESULT FormatFirmObject(DEBUGHELPER *pHelper, int nBase, firm_kind kind, const void *addr, char *pResult, size_t max)
{
  switch (kind) {
  case k_entity:     /* an entity */
    return format_entity(pHelper, nBase, addr, pResult, max, 1);
  case k_type:       /* a type */
    return format_type(pHelper, nBase, addr, pResult, max, 1);
  case k_ir_graph:   /* an ir graph */
    return format_irg(pHelper, nBase, addr, pResult, max, 1);
  case k_ir_node:    /* an ir node */
    return format_node(pHelper, nBase, addr, pResult, max, 1);
  case k_ir_mode:    /* an ir mode */
    return format_mode(pHelper, addr, pResult, max);
  case k_ir_op:      /* an ir opcode */
    return format_op(pHelper, addr, pResult, max);
  case k_tarval:     /* a tarval */
    return format_tarval(pHelper, nBase, addr, pResult, max);
  case k_ir_loop:    /* a loop */
    return format_loop(pHelper, addr, pResult, max);
  case k_ir_compound_graph_path: /* a compound graph path, see entity.h */
    return E_FAIL;
  case k_ir_extblk:  /* an extended block */
    return format_extblk(pHelper, nBase, addr, pResult, max);
  case k_ir_prog:    /* a program representation (irp) */
    return format_prog(pHelper, nBase, addr, pResult, max);
  default:
    return E_FAIL;
  }
}  /* FormatFirmObject */

#define SEGMENT_SIZE_SHIFT	8
#define SEGMENT_SIZE		(1 << SEGMENT_SIZE_SHIFT)
#define DIRECTORY_SIZE_SHIFT	8
#define DIRECTORY_SIZE		(1 << DIRECTORY_SIZE_SHIFT)
#define MAX_LOAD_FACTOR		4

typedef struct pset_element {
  struct pset_element *chain;	/**< for chaining Elements */
  pset_entry entry;
} pset_Element, *pset_Segment;

/* not visible from outside */
struct pset {
  unsigned p;              /**< Next bucket to be split */
  unsigned maxp;           /**< upper bound on p during expansion */
  unsigned nkey;           /**< current # keys */
  unsigned nseg;           /**< current # segments */
  pset_Segment *dir[DIRECTORY_SIZE];
  int (*cmp)();            /**< function comparing entries */
  unsigned iter_i, iter_j;
  pset_Element *iter_tail; /**< non-NULL while iterating over elts */
  pset_Element *free_list; /**< list of free Elements */
  struct obstack obst;     /**< obstack for allocation all data */
};

typedef struct set_element {
  struct set_element *chain;	/**< for chaining Elements */
  set_entry entry;
} set_Element, *set_Segment;

/* not visible from outside */
struct set {
  unsigned p;              /**< Next bucket to be split */
  unsigned maxp;           /**< upper bound on p during expansion */
  unsigned nkey;           /**< current # keys */
  unsigned nseg;           /**< current # segments */
  set_Segment *dir[DIRECTORY_SIZE];
  int (*cmp)();            /**< function comparing entries */
  unsigned iter_i, iter_j;
  set_Element *iter_tail;  /**< non-NULL while iterating over elts */
  struct obstack obst;     /**< obstack for allocation all data */
};

/**
 * Find the longest chain of a pset
 */
static HRESULT find_longest_pset_chain(DEBUGHELPER *pHelper, pset *set,
825
826
                                       int *chains, int *lenght, size_t *size)
{
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
  unsigned i, j;
  pset_Segment *seg, *curr;
  pset_Element elem;
  void *address;
  int len, nchains = 0, max_len = 0;
  size_t dyns = 0;

  for (i = 0; i < set->nseg; ++i) {
    seg = set->dir[i];

    dyns += sizeof(seg[j]) * SEGMENT_SIZE;
    for (j = 0; j < SEGMENT_SIZE; ++j) {
      if (copy_from_debuggee(&seg[j], pHelper, &curr, sizeof(curr)) != S_OK)
        return E_FAIL;

      address = curr;
      if (address)
        ++nchains;
      for (len = 0; address != NULL; address = elem.chain) {
        if (copy_from_debuggee(address, pHelper, &elem, sizeof(elem)) != S_OK)
          return E_FAIL;
        dyns += sizeof(pset_Element);
        ++len;
      }
      if (len > max_len)
        max_len = len;
    }
  }

  *chains = nchains;
  *lenght = max_len;
  *size   = dyns;
  return S_OK;
}  /* find_longest_pset_chain */

/**
 * Find the longest chain of a set
 */
static HRESULT find_longest_set_chain(DEBUGHELPER *pHelper, set *set,
866
867
                                      int *chains, int *lenght, size_t *size)
{
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
  unsigned i, j;
  set_Segment *seg, *curr;
  set_Element elem;
  void *address;
  int len, nchains = 0, max_len = 0;
  size_t dyns = 0;

  for (i = 0; i < set->nseg; ++i) {
    seg = set->dir[i];

    dyns += sizeof(seg[j]) * SEGMENT_SIZE;
    for (j = 0; j < SEGMENT_SIZE; ++j) {
      if (copy_from_debuggee(&seg[j], pHelper, &curr, sizeof(curr)) != S_OK)
          return E_FAIL;

      address = curr;
      if (address)
        ++nchains;
      for (len = 0; address != NULL; address = elem.chain) {
        if (copy_from_debuggee(address, pHelper, &elem, sizeof(elem)) != S_OK)
          return E_FAIL;
        dyns += offsetof(set_Element, entry.dptr) + elem.entry.size;
        ++len;
      }
      if (len > max_len)
        max_len = len;
    }
  }

  *chains = nchains;
  *lenght = max_len;
  *size   = dyns;
  return S_OK;
}  /* find_longest_set_chain */

/*
 * Format a pset
 */
HRESULT format_pset(DEBUGHELPER *pHelper, int nBase, const void *address, char *pResult, size_t max)
{
  pset set;
  char name[256];
  int nchains, chain_len;
  size_t size;

  if (copy_from_debuggee(address, pHelper, &set, sizeof(set)) != S_OK)
    return E_FAIL;

  if (find_longest_pset_chain(pHelper, &set, &nchains, &chain_len, &size) != S_OK)
    return E_FAIL;

  switch (nBase) {
  case 16:
    _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);
    break;
  case 8:
    _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);
    break;
  default:
    _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);
  }
  _tcsncpy(pResult, name, max);

  return S_OK;
}  /* format_pset */

/*
 * Format a set
 */
HRESULT format_set(DEBUGHELPER *pHelper, int nBase, const void *address, char *pResult, size_t max)
{
  set set;
  char name[256];
  int nchains, chain_len;
  size_t size;

  if (copy_from_debuggee(address, pHelper, &set, sizeof(set)) != S_OK)
    return E_FAIL;

  if (find_longest_set_chain(pHelper, &set, &nchains, &chain_len, &size) != S_OK)
    return E_FAIL;

  switch (nBase) {
  case 16:
    _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);
    break;
  case 8:
    _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);
    break;
  default:
    _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);
  }
  _tcsncpy(pResult, name, max);

  return S_OK;
}  /* format_set */

struct pdeq {
  unsigned magic;       /**< debug magic, only available in DEBUG builds */
  pdeq *l_end, *r_end;  /**< left and right ends of the queue */
  pdeq *l, *r;          /**< left and right neighbor */
  int n;                /**< number of elements in the current chunk */
  int p;                /**< the read/write pointer */
  const void *data[1];  /**< storage for elements */
};

/** Returns the length of a double ended pointer list. */
static int get_pdeq_len(DEBUGHELPER *pHelper, pdeq *dq)
{
  int n;
  pdeq *q;
  pdeq pdeq;

  n = 0;
  q = dq->l_end;

  if (copy_from_debuggee(q, pHelper, &pdeq, sizeof(pdeq)) != S_OK)
    return -1;
  q = &pdeq;

  for (;;) {
    n += q->n;
    q = q->r;
    if (! q)
      break;

    if (copy_from_debuggee(q, pHelper, &pdeq, sizeof(pdeq)) != S_OK)
      return -1;
    q = &pdeq;
  };

  return n;
}  /* get_pdeq_len */
For faster browsing, not all history is shown. View entire blame