type.c 56.2 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
/*
 * Project:     libFIRM
 * File name:   ir/tr/type.c
 * Purpose:     Representation of types.
 * Author:      Goetz Lindenmaier
 * Modified by:
 * Created:
 * CVS-ID:      $Id$
 * Copyright:   (c) 2001-2003 Universitt Karlsruhe
 * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
 */

Sebastian Felis's avatar
Sebastian Felis committed
13
/**
14
15
16
17
 *
 *   file type.c - implementation of the datastructure to hold
 *   type information.
 *  (C) 2001 by Universitaet Karlsruhe
18
 *  Goetz Lindenmaier
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
 *
 *  This module supplies a datastructure to represent all types
 *  known in the compiled program.  This includes types specified
 *  in the program as well as types defined by the language.  In the
 *  view of the intermediate representation there is no difference
 *  between these types.
 *
 *  There exist several kinds of types, arranged by the structure of
 *  the type.  A type is described by a set of attributes.  Some of
 *  these attributes are common to all types, others depend on the
 *  kind of the type.
 *
 *  Types are different from the modes defined in irmode:  Types are
 *  on the level of the programming language, modes at the level of
 *  the target processor.
 *
Sebastian Felis's avatar
Sebastian Felis committed
35
 * @see  type_t.h type tpop
36
 */
Boris Boesler's avatar
Boris Boesler committed
37

38
#ifdef HAVE_CONFIG_H
Michael Beck's avatar
Michael Beck committed
39
40
41
42
43
44
45
46
47
48
49
# include "config.h"
#endif

#ifdef HAVE_ALLOCA_H
#include <alloca.h>
#endif
#ifdef HAVE_MALLOC_H
#include <malloc.h>
#endif
#ifdef HAVE_STRING_H
# include <string.h>
50
51
#endif

52
53
# include <stdlib.h>
# include <stddef.h>
54

55
# include "type_t.h"
56

Michael Beck's avatar
Michael Beck committed
57
# include "xmalloc.h"
58
# include "irprog_t.h"
59
60
# include "ircons.h"
# include "tpop_t.h"
61
# include "typegmod.h"
62
# include "mangle.h"
63
64
65
# include "tv_t.h"

# include "array.h"
Christian Schäfer's avatar
Christian Schäfer committed
66
67

/*******************************************************************/
68
/** TYPE                                                          **/
Christian Schäfer's avatar
Christian Schäfer committed
69
70
/*******************************************************************/

71
72
type *firm_none_type;    type *get_none_type(void)    { return firm_none_type;    }
type *firm_unknown_type; type *get_unknown_type(void) { return firm_unknown_type; }
73
74


75
76
77
78
79
#ifdef DEBUG_libfirm
/** Returns a new, unique number to number nodes or the like. */
int get_irp_new_node_nr(void);
#endif

80
81
82
83
84
/* Suffixes added to types used for pass-by-value representations. */
static ident *value_params_suffix = NULL;
static ident *value_ress_suffix = NULL;

void init_type(void) {
85
86
87
88
  value_params_suffix = new_id_from_str(VALUE_PARAMS_SUFFIX);
  value_ress_suffix   = new_id_from_str(VALUE_RESS_SUFFIX);

  /* construct none and unknown type. */
89
90
91
92
93
94
95
96
  firm_none_type    = new_type(tpop_none,    mode_BAD, new_id_from_str("type_none"));
  set_type_size_bits(firm_none_type, 0);
  set_type_state (firm_none_type, layout_fixed);
  remove_irp_type(firm_none_type);
  firm_unknown_type = new_type(tpop_unknown, mode_ANY, new_id_from_str("type_unknown"));
  set_type_size_bits(firm_unknown_type, 0);
  set_type_state (firm_unknown_type, layout_fixed);
  remove_irp_type(firm_unknown_type);
97
98
}

99
unsigned long type_visited;
100

101
102
103
void (set_master_type_visited)(unsigned long val) { _set_master_type_visited(val); }
unsigned long (get_master_type_visited)(void)     { return _get_master_type_visited(); }
void (inc_master_type_visited)(void)              { _inc_master_type_visited(); }
Christian Schäfer's avatar
Christian Schäfer committed
104

105

106
type *
107
108
new_type(tp_op *type_op, ir_mode *mode, ident* name) {
  type *res;
109
  int node_size ;
Christian Schäfer's avatar
Christian Schäfer committed
110

111
  assert(type_op != type_id);
Michael Beck's avatar
Michael Beck committed
112
  assert(!id_contains_char(name, ' ') && "type name should not contain spaces");
113

114
  node_size = offsetof(type, attr) +  type_op->attr_size;
Michael Beck's avatar
Michael Beck committed
115
116
  res = xmalloc (node_size);
  memset(res, 0, node_size);
117
  add_irp_type(res);   /* Remember the new type global. */
Christian Schäfer's avatar
Christian Schäfer committed
118

Götz Lindenmaier's avatar
Götz Lindenmaier committed
119
  res->kind    = k_type;
120
  res->type_op = type_op;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
121
122
123
124
  res->mode    = mode;
  res->name    = name;
  res->state   = layout_undefined;
  res->size    = -1;
Michael Beck's avatar
Michael Beck committed
125
  res->align   = -1;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
126
127
  res->visit   = 0;
  res -> link  = NULL;
128
#ifdef DEBUG_libfirm
Götz Lindenmaier's avatar
Götz Lindenmaier committed
129
  res->nr      = get_irp_new_node_nr();
Florian Liekweg's avatar
Florian Liekweg committed
130
#endif /* defined DEBUG_libfirm */
Christian Schäfer's avatar
Christian Schäfer committed
131
132
133
134

  return res;
}

135
136
137
138
139
140
141
142
void        free_type(type *tp) {
  if ((get_type_tpop(tp) == tpop_none) || (get_type_tpop(tp) == tpop_unknown))
    return;
  /* Remove from list of all types */
  remove_irp_type(tp);
  /* Free the attributes of the type. */
  free_type_attrs(tp);
  /* Free entities automatically allocated with the type */
143
  if (is_Array_type(tp))
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
    free_entity(get_array_element_entity(tp));
  /* And now the type itself... */
  tp->kind = k_BAD;
  free(tp);
}

void free_type_entities(type *tp) {
  switch(get_type_tpop_code(tp)) {
  case tpo_class:       { free_class_entities(tp);       } break;
  case tpo_struct:      { free_struct_entities(tp);      } break;
  case tpo_method:      { free_method_entities(tp);      } break;
  case tpo_union:       { free_union_entities(tp);       } break;
  case tpo_array:       { free_array_entities(tp);       } break;
  case tpo_enumeration: { free_enumeration_entities(tp); } break;
  case tpo_pointer:     { free_pointer_entities(tp);     } break;
  case tpo_primitive:   { free_primitive_entities(tp);   } break;
  default: break;
  }
}

164
165
166
167
168
169
170
171
172
173
174
175
176
177
void free_type_attrs(type *tp) {
  switch(get_type_tpop_code(tp)) {
  case tpo_class:       { free_class_attrs(tp);       } break;
  case tpo_struct:      { free_struct_attrs(tp);      } break;
  case tpo_method:      { free_method_attrs(tp);      } break;
  case tpo_union:       { free_union_attrs(tp);       } break;
  case tpo_array:       { free_array_attrs(tp);       } break;
  case tpo_enumeration: { free_enumeration_attrs(tp); } break;
  case tpo_pointer:     { free_pointer_attrs(tp);     } break;
  case tpo_primitive:   { free_primitive_attrs(tp);   } break;
  default: break;
  }
}

178
/* set/get the link field */
Michael Beck's avatar
Michael Beck committed
179
void *(get_type_link)(const type *tp)
180
{
181
  return _get_type_link(tp);
182
183
}

184
void (set_type_link)(type *tp, void *l)
185
{
186
  _set_type_link(tp, l);
187
188
}

Michael Beck's avatar
Michael Beck committed
189
const tp_op *(get_type_tpop)(const type *tp) {
190
  return _get_type_tpop(tp);
Christian Schäfer's avatar
Christian Schäfer committed
191
192
}

Michael Beck's avatar
Michael Beck committed
193
ident *(get_type_tpop_nameid)(const type *tp) {
194
  return _get_type_tpop_nameid(tp);
Christian Schäfer's avatar
Christian Schäfer committed
195
}
196

Michael Beck's avatar
Michael Beck committed
197
const char* get_type_tpop_name(const type *tp) {
Götz Lindenmaier's avatar
a    
Götz Lindenmaier committed
198
  assert(tp && tp->kind == k_type);
199
  return get_id_str(tp->type_op->name);
200
}
201

Michael Beck's avatar
Michael Beck committed
202
tp_opcode (get_type_tpop_code)(const type *tp) {
203
  return _get_type_tpop_code(tp);
204
}
205

Michael Beck's avatar
Michael Beck committed
206
ir_mode *(get_type_mode)(const type *tp) {
207
  return _get_type_mode(tp);
208
}
209

210
void        set_type_mode(type *tp, ir_mode* m) {
Götz Lindenmaier's avatar
a    
Götz Lindenmaier committed
211
212
  assert(tp && tp->kind == k_type);

213
  assert(((tp->type_op != type_primitive)   || mode_is_data(m))     &&
Florian Liekweg's avatar
Florian Liekweg committed
214
215
     /* Modes of primitives must be data */
     ((tp->type_op != type_enumeration) || mode_is_int(m))      &&
Götz Lindenmaier's avatar
a    
Götz Lindenmaier committed
216
         /* Modes of enumerations must be integers */
Florian Liekweg's avatar
Florian Liekweg committed
217
218
     ((tp->type_op != type_pointer)     || mode_is_reference(m))   );
     /* Modes of pointers must be references. */
Götz Lindenmaier's avatar
a    
Götz Lindenmaier committed
219

220
221
  switch (get_type_tpop_code(tp)) {
  case tpo_primitive:
222
223
224
    /* For primitive size depends on the mode. */
    tp->size = get_mode_size_bits(m);
    tp->mode = m;
225
226
227
    break;
  case tpo_enumeration:
  case tpo_pointer:
228
229
230
    /* For pointer and enumeration size depends on the mode, but only byte size allowed. */
    assert((get_mode_size_bits(m) & 7) == 0 && "unorthodox modes not implemented");
    tp->size = get_mode_size_bits(m);
Götz Lindenmaier's avatar
a    
Götz Lindenmaier committed
231
    tp->mode = m;
232
233
234
235
236
    break;
  case tpo_struct:
  case tpo_class:
    /* for classes and structs we allow to set a mode if the layout is fixed AND the size matches */
    assert(get_type_state(tp) == layout_fixed &&
Florian Liekweg's avatar
Florian Liekweg committed
237
238
       tp->size == get_mode_size_bits(m) &&
       "mode don't match struct/class layout");
239
240
241
242
    tp->mode = m;
    break;
  default:
    assert(0 && "setting a mode is NOT allowed for this type");
Götz Lindenmaier's avatar
a    
Götz Lindenmaier committed
243
  }
244
}
245

Michael Beck's avatar
Michael Beck committed
246
ident *(get_type_ident)(const type *tp) {
247
  return _get_type_ident(tp);
248
}
249

250
void (set_type_ident)(type *tp, ident* id) {
251
  _set_type_ident(tp, id);
252
}
253

254
/* Outputs a unique number for this node */
255
256
257
258
259
260
261
long get_type_nr(const type *tp) {
  assert(tp);
#ifdef DEBUG_libfirm
  return tp->nr;
#else
  return (long)tp;
#endif
262
263
}

Michael Beck's avatar
Michael Beck committed
264
const char* get_type_name(const type *tp) {
Götz Lindenmaier's avatar
a    
Götz Lindenmaier committed
265
  assert(tp && tp->kind == k_type);
266
  return (get_id_str(tp->name));
267
}
268

Michael Beck's avatar
Michael Beck committed
269
int (get_type_size_bytes)(const type *tp) {
270
  return _get_type_size_bytes(tp);
271
272
}

Michael Beck's avatar
Michael Beck committed
273
int (get_type_size_bits)(const type *tp) {
274
  return _get_type_size_bits(tp);
275
}
276
277

void
278
set_type_size_bits(type *tp, int size) {
Götz Lindenmaier's avatar
a    
Götz Lindenmaier committed
279
280
281
282
  assert(tp && tp->kind == k_type);
  /* For pointer enumeration and primitive size depends on the mode.
     Methods don't have a size. */
  if ((tp->type_op != type_pointer) && (tp->type_op != type_primitive) &&
283
284
285
286
      (tp->type_op != type_enumeration) && (tp->type_op != type_method)) {
    if (tp->type_op == type_primitive)
      tp->size = size;
    else {
287
288
      /* argh: we must allow to set negative values as "invalid size" */
      tp->size = (size >= 0) ? (size + 7) & ~7 : size;
289
290
291
292
293
294
295
296
      assert(tp->size == size && "setting a bit size is NOT allowed for this type");
    }
  }
}

void
set_type_size_bytes(type *tp, int size) {
  set_type_size_bits(tp, 8*size);
297
}
298

Michael Beck's avatar
Michael Beck committed
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
int get_type_alignment_bytes(type *tp) {
  int align = get_type_alignment_bits(tp);

  return align < 0 ? align : (align + 7) >> 3;
}

int get_type_alignment_bits(type *tp) {
  int align = 8;

  if (tp->align > 0)
    return tp->align;

  /* alignment NOT set calculate it "on demand" */
  if (tp->mode)
    align = get_mode_size_bits(tp->mode);
314
  else if (is_Array_type(tp))
Michael Beck's avatar
Michael Beck committed
315
316
317
318
319
320
321
322
323
324
325
326
327
    align = get_type_alignment_bits(get_array_element_type(tp));
  else if (is_compound_type(tp)) {
    int i, n = get_compound_n_members(tp);

    align = 0;
    for (i = 0; i < n; ++i) {
      type *t = get_entity_type(get_compound_member(tp, i));
      int   a = get_type_alignment_bits(t);

      if (a > align)
        align = a;
    }
  }
328
  else if (is_Method_type(tp))
Michael Beck's avatar
Michael Beck committed
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
    align = 0;

  /* write back */
  tp->align = align;

  return align;
}

void
set_type_alignment_bits(type *tp, int align) {
  assert(tp && tp->kind == k_type);
  /* Methods don't have an alignment. */
  if (tp->type_op != type_method) {
    tp->align = align;
  }
}

void
set_type_alignment_bytes(type *tp, int align) {
  set_type_size_bits(tp, 8*align);
}

Götz Lindenmaier's avatar
Götz Lindenmaier committed
351
352
353
354
355
356
357
358
359
360
361
362
/* Returns a human readable string for the enum entry. */
const char *get_type_state_name(type_state s) {
#define X(a)    case a: return #a;
  switch (s) {
    X(layout_undefined);
    X(layout_fixed);
  }
  return "<unknown>";
#undef X
}


Michael Beck's avatar
Michael Beck committed
363
type_state (get_type_state)(const type *tp) {
364
  return _get_type_state(tp);
365
366
367
368
}

void
set_type_state(type *tp, type_state state) {
Götz Lindenmaier's avatar
a    
Götz Lindenmaier committed
369
370
  assert(tp && tp->kind == k_type);

371
  if ((tp->type_op == type_pointer) || (tp->type_op == type_primitive) ||
Götz Lindenmaier's avatar
a    
Götz Lindenmaier committed
372
373
374
375
376
377
378
379
380
      (tp->type_op == type_method))
    return;

  /* Just a correctness check: */
  if (state == layout_fixed) {
    int i;
    switch (get_type_tpop_code(tp)) {
    case tpo_class:
      {
Florian Liekweg's avatar
Florian Liekweg committed
381
382
383
384
385
386
387
    assert(get_type_size_bits(tp) > -1);
    if (tp != get_glob_type()) {
      int n_mem = get_class_n_members(tp);
      for (i = 0; i < n_mem; i++) {
        if (get_entity_offset_bits(get_class_member(tp, i)) <= -1)
          { DDMT(tp); DDME(get_class_member(tp, i)); }
        assert(get_entity_offset_bits(get_class_member(tp, i)) > -1);
Till Riedel's avatar
Till Riedel committed
388
            /* TR ??
389
        assert(is_Method_type(get_entity_type(get_class_member(tp, i))) ||
Florian Liekweg's avatar
Florian Liekweg committed
390
           (get_entity_allocation(get_class_member(tp, i)) == allocation_automatic));
Till Riedel's avatar
Till Riedel committed
391
                   */
Florian Liekweg's avatar
Florian Liekweg committed
392
393
      }
    }
Götz Lindenmaier's avatar
a    
Götz Lindenmaier committed
394
395
396
      } break;
    case tpo_struct:
      {
Michael Beck's avatar
Michael Beck committed
397
398
399
400
401
        assert(get_type_size_bits(tp) > -1);
        for (i = 0; i < get_struct_n_members(tp); i++) {
          assert(get_entity_offset_bits(get_struct_member(tp, i)) > -1);
          assert((get_entity_allocation(get_struct_member(tp, i)) == allocation_automatic));
        }
Götz Lindenmaier's avatar
a    
Götz Lindenmaier committed
402
403
404
405
406
      } break;
    case tpo_union:
      { /* ?? */
      } break;
    case tpo_array:
407
      { /* ??
Michael Beck's avatar
Michael Beck committed
408
409
         Check order?
         Assure that only innermost dimension is dynamic? */
Götz Lindenmaier's avatar
a    
Götz Lindenmaier committed
410
411
412
      } break;
    case tpo_enumeration:
      {
Michael Beck's avatar
Michael Beck committed
413
414
415
        assert(get_type_mode != NULL);
        for (i = 0; i < get_enumeration_n_enums(tp); i++)
          assert(get_enumeration_enum(tp, i) != NULL);
Götz Lindenmaier's avatar
a    
Götz Lindenmaier committed
416
417
418
      } break;
    default: break;
    } /* switch (tp) */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
419
  }
Götz Lindenmaier's avatar
a    
Götz Lindenmaier committed
420
  tp->state = state;
421
422
}

Michael Beck's avatar
Michael Beck committed
423
unsigned long (get_type_visited)(const type *tp) {
424
  return _get_type_visited(tp);
425
}
426

427
void (set_type_visited)(type *tp, unsigned long num) {
428
  _set_type_visited(tp, num);
429
}
430

431
/* Sets visited field in type to type_visited. */
432
void (mark_type_visited)(type *tp) {
433
  _mark_type_visited(tp);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
434
435
}

436
/* @@@ name clash with master flag
Michael Beck's avatar
Michael Beck committed
437
int (type_visited)(const type *tp) {
438
  return _type_visited(tp);
439
}*/
Götz Lindenmaier's avatar
Götz Lindenmaier committed
440

Michael Beck's avatar
Michael Beck committed
441
int (type_not_visited)(const type *tp) {
442
  return _type_not_visited(tp);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
443
444
}

Michael Beck's avatar
Michael Beck committed
445
int (is_type)(const void *thing) {
446
  return _is_type(thing);
447
}
448

Michael Beck's avatar
Michael Beck committed
449
450
/* Checks whether two types are structural equal.*/
int equal_type(type *typ1, type *typ2) {
451
452
453
454
  entity **m;
  type **t;
  int i, j;

Michael Beck's avatar
Michael Beck committed
455
  if (typ1 == typ2) return 1;
456
457

  if ((get_type_tpop_code(typ1) != get_type_tpop_code(typ2)) ||
458
      (get_type_ident(typ1) != get_type_ident(typ2)) ||
459
460
      (get_type_mode(typ1) != get_type_mode(typ2)) ||
      (get_type_state(typ1) != get_type_state(typ2)))
Michael Beck's avatar
Michael Beck committed
461
    return 0;
462
  if ((get_type_state(typ1) == layout_fixed) &&
463
      (get_type_size_bits(typ1) != get_type_size_bits(typ2)))
Michael Beck's avatar
Michael Beck committed
464
    return 0;
465
466
467

  switch(get_type_tpop_code(typ1)) {
  case tpo_class:       {
Michael Beck's avatar
Michael Beck committed
468
469
470
471
    if (get_class_n_members(typ1) != get_class_n_members(typ2)) return 0;
    if (get_class_n_subtypes(typ1) != get_class_n_subtypes(typ2)) return 0;
    if (get_class_n_supertypes(typ1) != get_class_n_supertypes(typ2)) return 0;
    if (get_class_peculiarity(typ1) != get_class_peculiarity(typ2)) return 0;
472
473
474
475
476
477
478
    /** Compare the members **/
    m = alloca(sizeof(entity *) * get_class_n_members(typ1));
    memset(m, 0, sizeof(entity *) * get_class_n_members(typ1));
    /* First sort the members of typ2 */
    for (i = 0; i < get_class_n_members(typ1); i++) {
      entity *e1 = get_class_member(typ1, i);
      for (j = 0; j < get_class_n_members(typ2); j++) {
Michael Beck's avatar
Michael Beck committed
479
480
481
        entity *e2 = get_class_member(typ2, j);
        if (get_entity_name(e1) == get_entity_name(e2))
          m[i] = e2;
482
483
484
485
      }
    }
    for (i = 0; i < get_class_n_members(typ1); i++) {
      if (!m[i]  ||  /* Found no counterpart */
Michael Beck's avatar
Michael Beck committed
486
          !equal_entity(get_class_member(typ1, i), m[i]))
Michael Beck's avatar
Michael Beck committed
487
        return 0;
488
489
490
491
492
493
494
495
    }
    /** Compare the supertypes **/
    t = alloca(sizeof(entity *) * get_class_n_supertypes(typ1));
    memset(t, 0, sizeof(entity *) * get_class_n_supertypes(typ1));
    /* First sort the supertypes of typ2 */
    for (i = 0; i < get_class_n_supertypes(typ1); i++) {
      type *t1 = get_class_supertype(typ1, i);
      for (j = 0; j < get_class_n_supertypes(typ2); j++) {
Michael Beck's avatar
Michael Beck committed
496
497
498
        type *t2 = get_class_supertype(typ2, j);
        if (get_type_ident(t2) == get_type_ident(t1))
          t[i] = t2;
499
500
501
502
      }
    }
    for (i = 0; i < get_class_n_supertypes(typ1); i++) {
      if (!t[i]  ||  /* Found no counterpart */
Michael Beck's avatar
Michael Beck committed
503
          get_class_supertype(typ1, i) != t[i])
Michael Beck's avatar
Michael Beck committed
504
        return 0;
505
506
507
    }
  } break;
  case tpo_struct:      {
Michael Beck's avatar
Michael Beck committed
508
    if (get_struct_n_members(typ1) != get_struct_n_members(typ2)) return 0;
509
510
511
512
513
514
    m = alloca(sizeof(entity *) * get_struct_n_members(typ1));
    memset(m, 0, sizeof(entity *) * get_struct_n_members(typ1));
    /* First sort the members of lt */
    for (i = 0; i < get_struct_n_members(typ1); i++) {
      entity *e1 = get_struct_member(typ1, i);
      for (j = 0; j < get_struct_n_members(typ2); j++) {
Michael Beck's avatar
Michael Beck committed
515
516
517
        entity *e2 = get_struct_member(typ2, j);
        if (get_entity_name(e1) == get_entity_name(e2))
          m[i] = e2;
518
519
520
521
      }
    }
    for (i = 0; i < get_struct_n_members(typ1); i++) {
      if (!m[i]  ||  /* Found no counterpart */
Michael Beck's avatar
Michael Beck committed
522
          !equal_entity(get_struct_member(typ1, i), m[i]))
Michael Beck's avatar
Michael Beck committed
523
        return 0;
524
525
526
    }
  } break;
  case tpo_method:      {
527
528
    int n_param1, n_param2;

Michael Beck's avatar
Michael Beck committed
529
530
    if (get_method_variadicity(typ1) != get_method_variadicity(typ2)) return 0;
    if (get_method_n_ress(typ1)      != get_method_n_ress(typ2)) return 0;
531
532
533
534
535
536
537
538
539
540

    if (get_method_variadicity(typ1) == variadicity_non_variadic) {
      n_param1 = get_method_n_params(typ1);
      n_param2 = get_method_n_params(typ2);
    }
    else {
      n_param1 = get_method_first_variadic_param_index(typ1);
      n_param2 = get_method_first_variadic_param_index(typ2);
    }

Michael Beck's avatar
Michael Beck committed
541
    if (n_param1 != n_param2) return 0;
542
543

    for (i = 0; i < n_param1; i++) {
544
      if (!equal_type(get_method_param_type(typ1, i), get_method_param_type(typ2, i)))
Michael Beck's avatar
Michael Beck committed
545
    return 0;
546
547
548
    }
    for (i = 0; i < get_method_n_ress(typ1); i++) {
      if (!equal_type(get_method_res_type(typ1, i), get_method_res_type(typ2, i)))
Michael Beck's avatar
Michael Beck committed
549
        return 0;
550
551
552
    }
  } break;
  case tpo_union:       {
Michael Beck's avatar
Michael Beck committed
553
    if (get_union_n_members(typ1) != get_union_n_members(typ2)) return 0;
554
555
556
557
558
559
    m = alloca(sizeof(entity *) * get_union_n_members(typ1));
    memset(m, 0, sizeof(entity *) * get_union_n_members(typ1));
    /* First sort the members of lt */
    for (i = 0; i < get_union_n_members(typ1); i++) {
      entity *e1 = get_union_member(typ1, i);
      for (j = 0; j < get_union_n_members(typ2); j++) {
Michael Beck's avatar
Michael Beck committed
560
561
562
        entity *e2 = get_union_member(typ2, j);
        if (get_entity_name(e1) == get_entity_name(e2))
          m[i] = e2;
563
564
565
566
      }
    }
    for (i = 0; i < get_union_n_members(typ1); i++) {
      if (!m[i]  ||  /* Found no counterpart */
Michael Beck's avatar
Michael Beck committed
567
          !equal_entity(get_union_member(typ1, i), m[i]))
Michael Beck's avatar
Michael Beck committed
568
        return 0;
569
570
571
572
    }
  } break;
  case tpo_array:       {
    if (get_array_n_dimensions(typ1) != get_array_n_dimensions(typ2))
Michael Beck's avatar
Michael Beck committed
573
      return 0;
574
    if (!equal_type(get_array_element_type(typ1), get_array_element_type(typ2)))
Michael Beck's avatar
Michael Beck committed
575
      return 0;
576
577
    for(i = 0; i < get_array_n_dimensions(typ1); i++) {
      if (get_array_lower_bound(typ1, i) != get_array_lower_bound(typ2, i) ||
Michael Beck's avatar
Michael Beck committed
578
          get_array_upper_bound(typ1, i) != get_array_upper_bound(typ2, i))
Michael Beck's avatar
Michael Beck committed
579
        return 0;
580
      if (get_array_order(typ1, i) != get_array_order(typ2, i))
Michael Beck's avatar
Michael Beck committed
581
        assert(0 && "type compare with different dimension orders not implemented");
582
583
584
585
586
587
588
    }
  } break;
  case tpo_enumeration: {
    assert(0 && "enumerations not implemented");
  } break;
  case tpo_pointer:     {
    if (get_pointer_points_to_type(typ1) != get_pointer_points_to_type(typ2))
Michael Beck's avatar
Michael Beck committed
589
      return 0;
590
591
592
593
594
  } break;
  case tpo_primitive:   {
  } break;
  default: break;
  }
Michael Beck's avatar
Michael Beck committed
595
  return 1;
596
597
}

Michael Beck's avatar
Michael Beck committed
598
599
/* Checks whether two types are structural comparable. */
int smaller_type (type *st, type *lt) {
600
601
602
  entity **m;
  int i, j;

Michael Beck's avatar
Michael Beck committed
603
  if (st == lt) return 1;
604
605

  if (get_type_tpop_code(st) != get_type_tpop_code(lt))
Michael Beck's avatar
Michael Beck committed
606
    return 0;
607
608
609
610
611
612

  switch(get_type_tpop_code(st)) {
  case tpo_class:       {
    return is_subclass_of(st, lt);
  } break;
  case tpo_struct:      {
Michael Beck's avatar
Michael Beck committed
613
    if (get_struct_n_members(st) != get_struct_n_members(lt)) return 0;
614
615
616
617
618
619
    m = alloca(sizeof(entity *) * get_struct_n_members(st));
    memset(m, 0, sizeof(entity *) * get_struct_n_members(st));
    /* First sort the members of lt */
    for (i = 0; i < get_struct_n_members(st); i++) {
      entity *se = get_struct_member(st, i);
      for (j = 0; j < get_struct_n_members(lt); j++) {
Florian Liekweg's avatar
Florian Liekweg committed
620
621
622
    entity *le = get_struct_member(lt, j);
    if (get_entity_name(le) == get_entity_name(se))
      m[i] = le;
623
624
625
626
      }
    }
    for (i = 0; i < get_struct_n_members(st); i++) {
      if (!m[i]  ||  /* Found no counterpart */
Michael Beck's avatar
Michael Beck committed
627
628
          !smaller_type(get_entity_type(get_struct_member(st, i)),
                get_entity_type(m[i])))
Michael Beck's avatar
Michael Beck committed
629
        return 0;
630
631
632
    }
  } break;
  case tpo_method:      {
Michael Beck's avatar
Michael Beck committed
633
634
635
636
    /** FIXME: is this still 1? */
    if (get_method_variadicity(st) != get_method_variadicity(lt)) return 0;
    if (get_method_n_params(st) != get_method_n_params(lt)) return 0;
    if (get_method_n_ress(st) != get_method_n_ress(lt)) return 0;
637
638
    for (i = 0; i < get_method_n_params(st); i++) {
      if (!smaller_type(get_method_param_type(st, i), get_method_param_type(lt, i)))
Michael Beck's avatar
Michael Beck committed
639
        return 0;
640
641
642
    }
    for (i = 0; i < get_method_n_ress(st); i++) {
      if (!smaller_type(get_method_res_type(st, i), get_method_res_type(lt, i)))
Michael Beck's avatar
Michael Beck committed
643
        return 0;
644
645
646
    }
  } break;
  case tpo_union:       {
Michael Beck's avatar
Michael Beck committed
647
    if (get_union_n_members(st) != get_union_n_members(lt)) return 0;
648
649
650
651
652
653
    m = alloca(sizeof(entity *) * get_union_n_members(st));
    memset(m, 0, sizeof(entity *) * get_union_n_members(st));
    /* First sort the members of lt */
    for (i = 0; i < get_union_n_members(st); i++) {
      entity *se = get_union_member(st, i);
      for (j = 0; j < get_union_n_members(lt); j++) {
Michael Beck's avatar
Michael Beck committed
654
655
656
657
        entity *le = get_union_member(lt, j);
        if (get_entity_name(le) == get_entity_name(se))
          m[i] = le;
          }
658
659
660
    }
    for (i = 0; i < get_union_n_members(st); i++) {
      if (!m[i]  ||  /* Found no counterpart */
Michael Beck's avatar
Michael Beck committed
661
662
          !smaller_type(get_entity_type(get_union_member(st, i)),
                get_entity_type(m[i])))
Michael Beck's avatar
Michael Beck committed
663
        return 0;
664
665
666
667
668
    }
  } break;
  case tpo_array:       {
    type *set, *let;  /* small/large elt. type */
    if (get_array_n_dimensions(st) != get_array_n_dimensions(lt))
Michael Beck's avatar
Michael Beck committed
669
      return 0;
670
671
672
673
    set = get_array_element_type(st);
    let = get_array_element_type(lt);
    if (set != let) {
      /* If the elt types are different, set must be convertible
Michael Beck's avatar
Michael Beck committed
674
675
676
         to let, and they must have the same size so that address
         computations work out.  To have a size the layout must
         be fixed. */
677
      if ((get_type_state(set) != layout_fixed) ||
Michael Beck's avatar
Michael Beck committed
678
          (get_type_state(let) != layout_fixed))
Michael Beck's avatar
Michael Beck committed
679
        return 0;
680
      if (!smaller_type(set, let) ||
Michael Beck's avatar
Michael Beck committed
681
          get_type_size_bits(set) != get_type_size_bits(let))
Michael Beck's avatar
Michael Beck committed
682
        return 0;
683
684
685
    }
    for(i = 0; i < get_array_n_dimensions(st); i++) {
      if (get_array_lower_bound(lt, i))
Michael Beck's avatar
Michael Beck committed
686
        if(get_array_lower_bound(st, i) != get_array_lower_bound(lt, i))
Michael Beck's avatar
Michael Beck committed
687
          return 0;
688
      if (get_array_upper_bound(lt, i))
Michael Beck's avatar
Michael Beck committed
689
        if(get_array_upper_bound(st, i) != get_array_upper_bound(lt, i))
Michael Beck's avatar
Michael Beck committed
690
          return 0;
691
692
693
694
695
696
697
    }
  } break;
  case tpo_enumeration: {
    assert(0 && "enumerations not implemented");
  } break;
  case tpo_pointer:     {
    if (!smaller_type(get_pointer_points_to_type(st),
Florian Liekweg's avatar
Florian Liekweg committed
698
              get_pointer_points_to_type(lt)))
Michael Beck's avatar
Michael Beck committed
699
      return 0;
700
701
702
  } break;
  case tpo_primitive:   {
    if (!smaller_mode(get_type_mode(st), get_type_mode(lt)))
Michael Beck's avatar
Michael Beck committed
703
      return 0;
704
705
706
  } break;
  default: break;
  }
Michael Beck's avatar
Michael Beck committed
707
  return 1;
708
709
}

710
711
712
/*-----------------------------------------------------------------*/
/* TYPE_CLASS                                                      */
/*-----------------------------------------------------------------*/
Christian Schäfer's avatar
Christian Schäfer committed
713

714
/* create a new class type */
715
type   *new_type_class (ident *name) {
716
  type *res;
Christian Schäfer's avatar
Christian Schäfer committed
717

718
  res = new_type(type_class, NULL, name);
Christian Schäfer's avatar
Christian Schäfer committed
719

Beyhan's avatar
Beyhan committed
720
721
722
  res->attr.ca.members     = NEW_ARR_F (entity *, 0);
  res->attr.ca.subtypes    = NEW_ARR_F (type *, 0);
  res->attr.ca.supertypes  = NEW_ARR_F (type *, 0);
723
724
  res->attr.ca.peculiarity = peculiarity_existent;
  res->attr.ca.dfn         = 0;
Christian Schäfer's avatar
Christian Schäfer committed
725
726
727

  return res;
}
728
729
730
731
732
type   *new_d_type_class (ident *name, dbg_info* db) {
  type *res = new_type_class (name);
  set_type_dbg_info(res, db);
  return res;
}
733

734
void free_class_entities(type *clss) {
735
736
737
738
739
740
  int i;
  assert(clss && (clss->type_op == type_class));
  for (i = get_class_n_members(clss)-1; i >= 0; --i)
    free_entity(get_class_member(clss, i));
}

741
void free_class_attrs(type *clss) {
742
743
744
745
746
  assert(clss && (clss->type_op == type_class));
  DEL_ARR_F(clss->attr.ca.members);
  DEL_ARR_F(clss->attr.ca.subtypes);
  DEL_ARR_F(clss->attr.ca.supertypes);
}
747

748
749
750
751
/* manipulate private fields of class type  */
void    add_class_member   (type *clss, entity *member) {
  assert(clss && (clss->type_op == type_class));
  ARR_APP1 (entity *, clss->attr.ca.members, member);
Christian Schäfer's avatar
Christian Schäfer committed
752
}
753

Michael Beck's avatar
Michael Beck committed
754
int     (get_class_n_members) (const type *clss) {
755
  return _get_class_n_members(clss);
Christian Schäfer's avatar
Christian Schäfer committed
756
}
757

Götz Lindenmaier's avatar
Götz Lindenmaier committed
758
759
760
761
762
763
764
765
int     get_class_member_index(type *clss, entity *mem) {
  int i;
  assert(clss && (clss->type_op == type_class));
  for (i = 0; i < get_class_n_members(clss); i++)
    if (get_class_member(clss, i) == mem)
      return i;
  return -1;
}
766

Michael Beck's avatar
Michael Beck committed
767
entity *(get_class_member)   (const type *clss, int pos) {
768
  return _get_class_member(clss, pos);
769
}
770

Götz Lindenmaier's avatar
Götz Lindenmaier committed
771
772
773
774
775
776
777
778
779
780
781
entity *get_class_member_by_name(type *clss, ident *name) {
  int i, n_mem;
  assert(clss && (clss->type_op == type_class));
  n_mem = get_class_n_members(clss);
  for (i = 0; i < n_mem; ++i) {
    entity *mem = get_class_member(clss, i);
    if (get_entity_ident(mem) == name) return mem;
  }
  return NULL;
}

782
783
void    set_class_member   (type *clss, entity *member, int pos) {
  assert(clss && (clss->type_op == type_class));
784
  assert(pos >= 0 && pos < get_class_n_members(clss));
Beyhan's avatar
Beyhan committed
785
  clss->attr.ca.members[pos] = member;
786
}
Götz Lindenmaier's avatar
a    
Götz Lindenmaier committed
787
788
789
790
void    set_class_members  (type *clss, entity **members, int arity) {
  int i;
  assert(clss && (clss->type_op == type_class));
  DEL_ARR_F(clss->attr.ca.members);
Beyhan's avatar
Beyhan committed
791
  clss->attr.ca.members    = NEW_ARR_F (entity *, 0);
Götz Lindenmaier's avatar
a    
Götz Lindenmaier committed
792
793
794
795
796
  for (i = 0; i < arity; i++) {
    set_entity_owner(members[i], clss);
    ARR_APP1 (entity *, clss->attr.ca.members, members[i]);
  }
}
797
798
799
void    remove_class_member(type *clss, entity *member) {
  int i;
  assert(clss && (clss->type_op == type_class));
Beyhan's avatar
Beyhan committed
800
  for (i = 0; i < (ARR_LEN (clss->attr.ca.members)); i++) {
801
802
    if (clss->attr.ca.members[i] == member) {
      for(; i < (ARR_LEN (clss->attr.ca.members)) - 1; i++)
Florian Liekweg's avatar
Florian Liekweg committed
803
    clss->attr.ca.members[i] = clss->attr.ca.members[i + 1];
804
      ARR_SETLEN(entity*, clss->attr.ca.members, ARR_LEN(clss->attr.ca.members) - 1);
805
806
      break;
    }
807
  }
808
}
809

810
void    add_class_subtype   (type *clss, type *subtype) {
Götz Lindenmaier's avatar
Götz Lindenmaier committed
811
  int i;
812
813
  assert(clss && (clss->type_op == type_class));
  ARR_APP1 (type *, clss->attr.ca.subtypes, subtype);
814
  for (i = 0; i < get_class_n_supertypes(subtype); i++)
Boris Boesler's avatar
Boris Boesler committed
815
    if (get_class_supertype(subtype, i) == clss)
Götz Lindenmaier's avatar
Götz Lindenmaier committed
816
817
      /* Class already registered */
      return;
818
  ARR_APP1 (type *, subtype->attr.ca.supertypes, clss);
819
}
Michael Beck's avatar
Michael Beck committed
820
int     get_class_n_subtypes (const type *clss) {
821
  assert(clss && (clss->type_op == type_class));
Beyhan's avatar
Beyhan committed
822
  return (ARR_LEN (clss->attr.ca.subtypes));
823
824
825
}
type   *get_class_subtype   (type *clss, int pos) {
  assert(clss && (clss->type_op == type_class));
826
  assert(pos >= 0 && pos < get_class_n_subtypes(clss));
Beyhan's avatar
Beyhan committed
827
  return clss->attr.ca.subtypes[pos] = skip_tid(clss->attr.ca.subtypes[pos]);
828
}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
829
830
831
832
833
834
835
836
int     get_class_subtype_index(type *clss, const type *subclass) {
  int i, n_subtypes = get_class_n_subtypes(clss);
  assert(is_Class_type(subclass));
  for (i = 0; i < n_subtypes; ++i) {
    if (get_class_subtype(clss, i) == subclass) return i;
  }
  return -1;
}
837
838
void    set_class_subtype   (type *clss, type *subtype, int pos) {
  assert(clss && (clss->type_op == type_class));
839
  assert(pos >= 0 && pos < get_class_n_subtypes(clss));
Beyhan's avatar
Beyhan committed
840
  clss->attr.ca.subtypes[pos] = subtype;
841
}
842
843
844
void    remove_class_subtype(type *clss, type *subtype) {
  int i;
  assert(clss && (clss->type_op == type_class));
Beyhan's avatar
Beyhan committed
845
  for (i = 0; i < (ARR_LEN (clss->attr.ca.subtypes)); i++)
846
847
    if (clss->attr.ca.subtypes[i] == subtype) {
      for(; i < (ARR_LEN (clss->attr.ca.subtypes))-1; i++)
Florian Liekweg's avatar
Florian Liekweg committed
848
    clss->attr.ca.subtypes[i] = clss->attr.ca.subtypes[i+1];
849
      ARR_SETLEN(entity*, clss->attr.ca.subtypes, ARR_LEN(clss->attr.ca.subtypes) - 1);
850
851
852
      break;
    }
}
853

854
void    add_class_supertype   (type *clss, type *supertype) {
Götz Lindenmaier's avatar
Götz Lindenmaier committed
855
  int i;
856
  assert(clss && (clss->type_op == type_class));
857
  assert(supertype && (supertype -> type_op == type_class));
858
  ARR_APP1 (type *, clss->attr.ca.supertypes, supertype);
859
  for (i = 0; i < get_class_n_subtypes(supertype); i++)
Boris Boesler's avatar
Boris Boesler committed
860
    if (get_class_subtype(supertype, i) == clss)
Götz Lindenmaier's avatar
Götz Lindenmaier committed
861
862
      /* Class already registered */
      return;
863
  ARR_APP1 (type *, supertype->attr.ca.subtypes, clss);
864
}
Michael Beck's avatar
Michael Beck committed
865
int     get_class_n_supertypes (const type *clss) {
866
  assert(clss && (clss->type_op == type_class));
Beyhan's avatar
Beyhan committed
867
  return (ARR_LEN (clss->attr.ca.supertypes));
868
}
Götz Lindenmaier's avatar
Götz Lindenmaier committed
869
int get_class_supertype_index(type *clss, type *super_clss) {
Götz Lindenmaier's avatar
Götz Lindenmaier committed
870
  int i, n_supertypes = get_class_n_supertypes(clss);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
871
  assert(super_clss && (super_clss->type_op == type_class));
Götz Lindenmaier's avatar
Götz Lindenmaier committed
872
  for (i = 0; i < n_supertypes; i++)
Götz Lindenmaier's avatar
Götz Lindenmaier committed
873
874
875
876
    if (get_class_supertype(clss, i) == super_clss)
      return i;
  return -1;
}
877
878
type   *get_class_supertype   (type *clss, int pos) {
  assert(clss && (clss->type_op == type_class));
879
  assert(pos >= 0 && pos < get_class_n_supertypes(clss));
Beyhan's avatar
Beyhan committed
880
  return clss->attr.ca.supertypes[pos] = skip_tid(clss->attr.ca.supertypes[pos]);
881
882
883
}
void    set_class_supertype   (type *clss, type *supertype, int pos) {
  assert(clss && (clss->type_op == type_class));
884
  assert(pos >= 0 && pos < get_class_n_supertypes(clss));
Beyhan's avatar
Beyhan committed
885
  clss->attr.ca.supertypes[pos] = supertype;
886
}
887
888
889
void    remove_class_supertype(type *clss, type *supertype) {
  int i;
  assert(clss && (clss->type_op == type_class));
Beyhan's avatar
Beyhan committed
890
  for (i = 0; i < (ARR_LEN (clss->attr.ca.supertypes)); i++)
891
892
    if (clss->attr.ca.supertypes[i] == supertype) {
      for(; i < (ARR_LEN (clss->attr.ca.supertypes))-1; i++)
Florian Liekweg's avatar
Florian Liekweg committed
893
    clss->attr.ca.supertypes[i] = clss->attr.ca.supertypes[i+1];
894
      ARR_SETLEN(entity*, clss->attr.ca.supertypes, ARR_LEN(clss->attr.ca.supertypes) - 1);
895
896
897
      break;
    }
}
898

Michael Beck's avatar
Michael Beck committed
899
const char *get_peculiarity_string(peculiarity p) {
Götz Lindenmaier's avatar
Götz Lindenmaier committed
900
#define X(a)    case a: return #a
Michael Beck's avatar
Michael Beck committed
901
  switch (p) {
Götz Lindenmaier's avatar
Götz Lindenmaier committed
902
903
904
    X(peculiarity_description);
    X(peculiarity_inherited);
    X(peculiarity_existent);
Michael Beck's avatar
Michael Beck committed
905
  }
Götz Lindenmaier's avatar
Götz Lindenmaier committed
906
907
#undef X
  return "invalid peculiarity";
Götz Lindenmaier's avatar
Götz Lindenmaier committed
908
909
}

Michael Beck's avatar
Michael Beck committed
910
peculiarity get_class_peculiarity (const type *clss) {
911
912
913
  assert(clss && (clss->type_op == type_class));
  return clss->attr.ca.peculiarity;
}
Michael Beck's avatar
Michael Beck committed
914

915
void        set_class_peculiarity (type *clss, peculiarity pec) {
916
  assert(clss && (clss->type_op == type_class));
917
  assert(pec != peculiarity_inherited);  /* There is no inheritance of types in libFirm. */
918
919
920
  clss->attr.ca.peculiarity = pec;
}

921
922
923
924
925
void set_class_dfn (type *clss, int dfn)
{
  clss->attr.ca.dfn        = dfn;
}