cgana.c 25.1 KB
Newer Older
Götz Lindenmaier's avatar
Götz Lindenmaier committed
1
2
3
4
5
6
7
8
9
10
11
12
13
/*
 * Project:     libFIRM
 * File name:   ir/ana/cgana.c
 * Purpose:     Intraprozedural analyses to estimate the call graph.
 * Author:      Hubert Schmid
 * Modified by:
 * Created:     09.06.2002
 * CVS-ID:      $Id$
 * Copyright:   (c) 1999-2003 Universitt Karlsruhe
 * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
 */

/**
Florian Liekweg's avatar
Florian Liekweg committed
14
 * Intraprozedurale Analyse zur Abschtzung der Aufrufrelation. Es
15
16
17
 * wird eine Menge von freien Methoden und anschlieend die an den
 * Call-Operationen aufrufbaren Methoden bestimmt.
 *
Götz Lindenmaier's avatar
Götz Lindenmaier committed
18
 */
19
20
21
#ifdef HAVE_CONFIG_H
# include <config.h>
#endif
22

Götz Lindenmaier's avatar
Götz Lindenmaier committed
23
#include <stdlib.h>
24
#include "cgana.h"
Florian Liekweg's avatar
Florian Liekweg committed
25
#include "rta.h"
26

Götz Lindenmaier's avatar
Götz Lindenmaier committed
27
28
29
#include "irnode_t.h"
#include "irmode_t.h"
#include "irprog_t.h"
30
31
32
33
#include "irgwalk.h"
#include "ircons.h"
#include "irgmod.h"

Götz Lindenmaier's avatar
Götz Lindenmaier committed
34
#include "irflag_t.h"
Götz Lindenmaier's avatar
Götz Lindenmaier committed
35
36
#include "dbginfo_t.h"

Götz Lindenmaier's avatar
Götz Lindenmaier committed
37
38
39
#include "eset.h"
#include "pmap.h"
#include "array.h"
Götz Lindenmaier's avatar
Götz Lindenmaier committed
40

41
42
#include "irdump.h"

43
44
45
46
47
48
49
50
51
52
53
54
/* Eindeutige Adresse zur Markierung von besuchten Knoten und zur
 * Darstellung der unbekannten Methode. */
static void * MARK = &MARK;



/* --- sel methods ---------------------------------------------------------- */


static eset * entities = NULL;


55
/** Bestimmt die eindeutige Methode, die die Methode fr den
Götz Lindenmaier's avatar
Götz Lindenmaier committed
56
 *  bergebenen (dynamischen) Typ berschreibt. */
57
static entity * get_implementation(type * class, entity * method) {
58
  int i;
59
  if (get_entity_peculiarity(method) != peculiarity_description &&
60
      get_entity_owner(method) == class) {
61
62
63
64
    return method;
  }
  for (i = get_entity_n_overwrittenby(method) - 1; i >= 0; --i) {
    entity * e = get_entity_overwrittenby(method, i);
65
    if (get_entity_peculiarity(e) != peculiarity_description && get_entity_owner(e) == class) {
66
67
68
      return e;
    }
  }
69
  for (i = get_class_n_supertypes(class) - 1; i >= 0; --i) {
70
71
72
73
74
    entity * e = get_implementation(get_class_supertype(class, i), method);
    if (e) {
      return e;
    }
  }
Florian Liekweg's avatar
Florian Liekweg committed
75
  assert(0 && "implementation not found");
Till Riedel's avatar
Till Riedel committed
76
  return NULL;
77
78
}

79
80
81
/** Returns the entity that contains the implementation of the inherited
    entity if available, else returns the entity passed. */
static entity *get_inherited_methods_implementation(entity *inh_meth) {
82
83
  entity *impl_meth = NULL;
  ir_node *addr = get_atomic_ent_value(inh_meth);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
84

85
  assert(addr && "constant entity without value");
Götz Lindenmaier's avatar
Götz Lindenmaier committed
86

87
  if ((get_irn_op(addr) == op_SymConst) &&
Götz Lindenmaier's avatar
Götz Lindenmaier committed
88
      (get_SymConst_kind(addr) == symconst_addr_ent)) {
Beyhan's avatar
Beyhan committed
89
    impl_meth = get_SymConst_entity(addr);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
90
  } else {
Florian Liekweg's avatar
Florian Liekweg committed
91
    assert(0 && "Complex constant values not supported -- address of method should be straight constant!");
Götz Lindenmaier's avatar
Götz Lindenmaier committed
92
  }
Götz Lindenmaier's avatar
Götz Lindenmaier committed
93

94
  if (impl_meth && (get_entity_peculiarity(impl_meth) != peculiarity_existent)) {
95
96
97
98
99
100
    /*
      printf("this_meth: "); DDMEO(inh_meth);
      printf("impl meth: "); DDMEO(impl_meth);
      assert(!impl_meth || get_entity_peculiarity(impl_meth) == peculiarity_existent);
    */
    impl_meth = NULL;
101
102
103
104
  }
  return impl_meth? impl_meth : inh_meth;
}

105

106
107
108
109
110
111
112
113
114
115
116
117
118
119
/** Collect the entity representing the implementation of this
 *  entity (not the same if inherited) and all entities for overwriting
 *  implementations in "set".
 *  If the implementation of the method is not included in the
 *  compilation unit "open" is set to true.
 *  A recursive descend in the overwritten relation.
 *  Cycle-free, therefore must terminate.
 *
 * @param method
 * @param set      A set of entities.
 * @param size     Number of entities in set.
 * @param open
 */
static void collect_impls(entity *method, eset *set, int *size, bool *open) {
120
  int i;
121

122
123
  if (get_entity_peculiarity(method) == peculiarity_existent) {
    if (get_entity_visibility(method) == visibility_external_allocated) {
124
125
126
127
      assert(get_entity_irg(method) == NULL);
      *open = true;
    } else {
      assert(get_entity_irg(method) != NULL);
128
      if (!eset_contains(set, method)) {
Florian Liekweg's avatar
Florian Liekweg committed
129
130
        eset_insert(set, method);
        ++(*size);
131
      }
132
133
    }
  }
134

135
  if (get_entity_peculiarity(method) == peculiarity_inherited) {
136
137
    entity *impl_ent = get_inherited_methods_implementation(method);
    assert(impl_ent && "no implementation for inherited entity");
138
    if (get_entity_visibility(impl_ent) == visibility_external_allocated) {
139
140
141
142
143
      assert(get_entity_irg(impl_ent) == NULL);
      *open = true;
    } else {
      assert(get_entity_irg(impl_ent) != NULL);
      if (!eset_contains(set, impl_ent)) {
Florian Liekweg's avatar
Florian Liekweg committed
144
145
        eset_insert(set, impl_ent);
        ++(*size);
146
147
148
      }
    }
  }
149
  /** recursive descent **/
150
  for (i = get_entity_n_overwrittenby(method) - 1; i >= 0; --i)
151
    collect_impls(get_entity_overwrittenby(method, i), set, size, open);
152
153
}

154

155
156
157
158
159
160
161
162
163
164
/** Alle Methoden bestimmen, die die bergebene Methode berschreiben
 *  (und implementieren). In der zurckgegebenen Reihung kommt jede
 *  Methode nur einmal vor. Der Wert 'NULL' steht fr unbekannte
 *  (externe) Methoden. Die zurckgegebene Reihung mu vom Aufrufer
 *  wieder freigegeben werden (siehe "DEL_ARR_F"). Gibt es berhaupt
 *  keine Methoden, die "method" berschreiben, so gibt die Methode
 *  "NULL" zurck.
 *
 *  @param method
 */
165
166
167
168
169
static entity ** get_impl_methods(entity * method) {
  eset * set = eset_create();
  int size = 0;
  entity ** arr;
  bool open = false;
170

171
  /* Collect all method entities that can be called here */
172
173
  collect_impls(method, set, &size, &open);

174
  /* Vorgaenger einfuegen. */
175
176
177
178
179
180
  if (size == 0 && !open) {
    /* keine implementierte berschriebene Methode */
    arr = NULL;
  } else if (open) {
    entity * ent;
    arr = NEW_ARR_F(entity *, size + 1);
181
182
183
    arr[0] = NULL;  /* Represents open method */
    for (ent = eset_first(set); size > 0; ent = eset_next(set), --size)
      arr[size] = ent;
184
185
186
  } else {
    entity * ent;
    arr = NEW_ARR_F(entity *, size);
187
188
    for (size -= 1, ent = eset_first(set); size >= 0; ent = eset_next(set), --size)
      arr[size] = ent;
189
190
191
192
193
194
  }
  eset_destroy(set);
  return arr;
}


Götz Lindenmaier's avatar
Götz Lindenmaier committed
195
196
197
/* debug makros used in sel_methods_walker */
#define SIZ(x)    sizeof(x)/sizeof((x)[0])

198
#define DBG_OPT_NORMALIZE                                                      \
Florian Liekweg's avatar
Florian Liekweg committed
199
      __dbg_info_merge_pair(new_node, node, dbg_const_eval)
200
201
#define DBG_OPT_POLY_ALLOC                                                     \
  do {                                                                         \
Florian Liekweg's avatar
Florian Liekweg committed
202
203
204
205
    ir_node *ons[2];                                                       \
    ons[0] = node;                                                         \
    ons[1] = skip_Proj(get_Sel_ptr(node));                                 \
    __dbg_info_merge_sets(&new_node, 1, ons, SIZ(ons), dbg_rem_poly_call); \
Götz Lindenmaier's avatar
Götz Lindenmaier committed
206
     } while(0)
207
#define DBG_OPT_POLY                                                           \
Florian Liekweg's avatar
Florian Liekweg committed
208
      __dbg_info_merge_pair(new_node, node, dbg_rem_poly_call)
Götz Lindenmaier's avatar
Götz Lindenmaier committed
209
210


211
212
213

/** Analyse address computations.
 *
214
 *  - If the node is a SymConst(name) replace it by SymConst(ent) if possible.
215
216
 *  - If the node is a Sel:
 *    * If the pointer to the Sel comes directly from an Alloc node
217
 *      replace the Sel by a SymConst(ent).
218
219
220
221
222
 *
 *
 *  @param node The node to analyze
 *  @param ldname_map A map that mapps names of entities to the entities.
 */
223
static void sel_methods_walker(ir_node * node, pmap * ldname_map) {
224

225
  /* replace SymConst(name)-operations by SymConst(ent) */
226
  if (get_irn_op(node) == op_SymConst) {
Beyhan's avatar
Beyhan committed
227
228
    if (get_SymConst_kind(node) == symconst_addr_name) {
      pmap_entry * entry = pmap_find(ldname_map, (void *) get_SymConst_name(node));
229
      if (entry != NULL) { /* Method is declared in the compiled code */
230
231
232
233
234
235
236
237
238
	entity * ent = entry->value;
	if (get_opt_normalize() && (get_entity_visibility(ent) != visibility_external_allocated)) { /* Meth. is defined */
	  set_irg_current_block(current_ir_graph, get_nodes_block(node));
	  ir_node *new_node = copy_const_value(get_atomic_ent_value(ent));
	                                                                             DBG_OPT_NORMALIZE;
	  assert(get_entity_irg(ent));
	  DDMN(new_node);
	  exchange(node, new_node);
	}
239
240
      }
    }
241
242
243
244
  }

  else if (get_irn_op(node) == op_Sel &&
	   is_method_type(get_entity_type(get_Sel_entity(node)))) {
245
    entity * ent = get_Sel_entity(node);
246
247

    /* Sel from Alloc: replace by constant */
248
    if (get_opt_optimize() && get_opt_dyn_meth_dispatch() &&
249
        (get_irn_op(skip_Proj(get_Sel_ptr(node))) == op_Alloc)) {
Götz Lindenmaier's avatar
Götz Lindenmaier committed
250
      ir_node *new_node;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
251
      entity *called_ent;
252
      /* We know which method will be called, no dispatch necessary. */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
253
      called_ent = resolve_ent_polymorphy(get_Alloc_type(skip_Proj(get_Sel_ptr(node))), ent);
254
      set_irg_current_block(current_ir_graph, get_nodes_block(node));
Götz Lindenmaier's avatar
Götz Lindenmaier committed
255
256
257
      /* called_ent may not be description: has no Address/Const to Call! */
      assert(get_entity_peculiarity(called_ent) != peculiarity_description);
      new_node = copy_const_value(get_atomic_ent_value(called_ent));       DBG_OPT_POLY_ALLOC;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
258
      exchange (node, new_node);
259
260
261
    }

    else {
262
      assert(get_entity_peculiarity(ent) != peculiarity_inherited);
263
      if (!eset_contains(entities, ent)) {
Florian Liekweg's avatar
Florian Liekweg committed
264
265
266
267
268
        /* Entity noch nicht behandelt. Alle (intern oder extern)
         * implementierten Methoden suchen, die diese Entity
         * berschreiben. Die Menge an entity.link speichern. */
        set_entity_link(ent, get_impl_methods(ent));
        eset_insert(entities, ent);
269
270
      }
      if (get_entity_link(ent) == NULL) {
Florian Liekweg's avatar
Florian Liekweg committed
271
272
273
274
275
276
        /* Die Sel-Operation kann nie einen Zeiger auf eine aufrufbare
         * Methode zurckgeben. Damit ist sie insbesondere nicht
         * ausfhrbar und nicht erreichbar. */
        /* Gib eine Warnung aus wenn die Entitaet eine Beschreibung ist
           fuer die es keine Implementierung gibt. */
        if (get_entity_peculiarity(ent) == peculiarity_description) {
277
	  /* This is possible:  We call a method in a dead part of the program. */
Florian Liekweg's avatar
Florian Liekweg committed
278
        } else {
279
280
281
	  DDMN(node);
	  assert(0);  /* Why should this happen ??? */
          //exchange(node, new_Bad());
Florian Liekweg's avatar
Florian Liekweg committed
282
        }
283
      } else {
Florian Liekweg's avatar
Florian Liekweg committed
284
        entity ** arr = get_entity_link(ent);
285
286

#if 0
Florian Liekweg's avatar
Florian Liekweg committed
287
288
        int i;
        printf("\nCall site "); DDMN(node);
289
        printf("  in "); DDME(get_irg_entity(current_ir_graph));
Florian Liekweg's avatar
Florian Liekweg committed
290
291
292
293
294
295
        printf("  can call:\n");
        for (i = 0; i < ARR_LEN(arr); i++) {
          printf("   - "); DDME(arr[i]);
          printf("     with owner "); DDMT(get_entity_owner(arr[i]));
        }
        printf("\n");
296
297
#endif

Florian Liekweg's avatar
Florian Liekweg committed
298
299
300
        if (get_opt_optimize() && get_opt_dyn_meth_dispatch() &&
            (ARR_LEN(arr) == 1 && arr[0] != NULL)) {
          ir_node *new_node;
301
          /* Die Sel-Operation kann immer nur _einen_ Wert auf eine
Florian Liekweg's avatar
Florian Liekweg committed
302
303
304
           * interne Methode zurckgeben. Wir knnen daher die
           * Sel-Operation durch eine Const- bzw. SymConst-Operation
           * ersetzen. */
305
          set_irg_current_block(current_ir_graph, get_nodes_block(node));
306
307
          assert(get_entity_peculiarity(get_SymConst_entity(get_atomic_ent_value(arr[0]))) ==
	         peculiarity_existent);
Florian Liekweg's avatar
Florian Liekweg committed
308
309
310
          new_node = copy_const_value(get_atomic_ent_value(arr[0]));         DBG_OPT_POLY;
          exchange (node, new_node);
        }
311
312
313
314
315
316
      }
    }
  }
}


317
/** Datenstruktur initialisieren. Zustzlich werden alle
318
319
 *  SymConst(name)-Operationen, die auf interne Methoden verweisen, durch
 *  SymConst(entity)-Operationen ersetzt. */
320
321
static void sel_methods_init(void) {
  int i;
322
323
  pmap * ldname_map = pmap_create();   /* Map entitiy names to entities: to replace SymConst(name) by SymConst(ent). */

324
325
326
  assert(entities == NULL);
  entities = eset_create();
  for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
327
    entity * ent = get_irg_entity(get_irp_irg(i));
328
329
    /* Nur extern sichtbare Methode knnen berhaupt mit SymConst
     * aufgerufen werden. */
330
    if (get_entity_visibility(ent) != visibility_local) {
331
332
333
      pmap_insert(ldname_map, (void *) get_entity_ld_ident(ent), ent);
    }
  }
334
  all_irg_walk((irg_walk_func *) sel_methods_walker, NULL, ldname_map);
335
336
337
  pmap_destroy(ldname_map);
}

338
/*****************************************************************************/
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362

/* Datenstruktur freigeben. */
static void sel_methods_dispose(void) {
  entity * ent;
  assert(entities);
  for (ent = eset_first(entities); ent; ent = eset_next(entities)) {
    entity ** arr = get_entity_link(ent);
    if (arr) {
      DEL_ARR_F(arr);
    }
    set_entity_link(ent, NULL);
  }
  eset_destroy(entities);
  entities = NULL;
}


/* Gibt die Menge aller Methoden zurck, die an diesem Sel-Knoten
 * zurckgegeben werden knnen. Die Liste enthlt keine doppelten
 * Eintrge. */
static entity ** get_Sel_arr(ir_node * sel) {
  static entity ** NULL_ARRAY = NULL;
  entity * ent;
  entity ** arr;
363
  assert(sel && get_irn_op(sel) == op_Sel);
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
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
  ent = get_Sel_entity(sel);
  assert(is_method_type(get_entity_type(ent))); /* what else? */
  arr = get_entity_link(ent);
  if (arr) {
    return arr;
  } else {
    /* "NULL" zeigt an, dass keine Implementierung existiert. Dies
     * kann fr polymorphe (abstrakte) Methoden passieren. */
    if (!NULL_ARRAY) {
      NULL_ARRAY = NEW_ARR_F(entity *, 0);
    }
    return NULL_ARRAY;
  }
}


static int get_Sel_n_methods(ir_node * sel) {
  return ARR_LEN(get_Sel_arr(sel));
}


static entity * get_Sel_method(ir_node * sel, int pos) {
  entity ** arr = get_Sel_arr(sel);
  assert(pos >= 0 && pos < ARR_LEN(arr));
  return arr[pos];
}



/* --- callee analysis ------------------------------------------------------ */


static void callee_ana_node(ir_node * node, eset * methods);


static void callee_ana_proj(ir_node * node, long n, eset * methods) {
  assert(get_irn_mode(node) == mode_T);
  if (get_irn_link(node) == MARK) {
    /* already visited */
    return;
  }
  set_irn_link(node, MARK);

407
  switch (get_irn_opcode(node)) {
408
409
410
411
412
413
  case iro_Proj: {
    /* proj_proj: in einem "sinnvollen" Graphen kommt jetzt ein
     * op_Tuple oder ein Knoten, der eine "freie Methode"
     * zurckgibt. */
    ir_node * pred = get_Proj_pred(node);
    if (get_irn_link(pred) != MARK) {
414
      if (get_irn_op(pred) == op_Tuple) {
Florian Liekweg's avatar
Florian Liekweg committed
415
    callee_ana_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, methods);
416
      } else {
Florian Liekweg's avatar
Florian Liekweg committed
417
    eset_insert(methods, MARK); /* free method -> unknown */
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
      }
    }
    break;
  }

  case iro_Tuple:
    callee_ana_node(get_Tuple_pred(node, n), methods);
    break;

  case iro_Id:
    callee_ana_proj(get_Id_pred(node), n, methods);
    break;

  default:
    eset_insert(methods, MARK); /* free method -> unknown */
    break;
  }

  set_irn_link(node, NULL);
}


static void callee_ana_node(ir_node * node, eset * methods) {
  int i;

Michael Beck's avatar
fixed:    
Michael Beck committed
443
  assert(mode_is_reference(get_irn_mode(node)) || is_Bad(node));
444
445
446
447
448
449
450
  /* rekursion verhindern */
  if (get_irn_link(node) == MARK) {
    /* already visited */
    return;
  }
  set_irn_link(node, MARK);

451
  switch (get_irn_opcode(node)) {
452
  case iro_SymConst:
Beyhan's avatar
Beyhan committed
453
454
455
456
    if (get_SymConst_kind(node) == symconst_addr_ent) {
      entity * ent = get_SymConst_entity(node);
      assert(ent && is_method_type(get_entity_type(ent)));
      if (get_entity_visibility(ent) != visibility_external_allocated) {
457
458
	assert(get_entity_irg(ent));
	eset_insert(methods, ent);
Beyhan's avatar
Beyhan committed
459
      } else {
460
	eset_insert(methods, MARK); /* free method -> unknown */
Beyhan's avatar
Beyhan committed
461
462
463
464
465
466
      }
    } else {
      assert(get_SymConst_kind(node) == symconst_addr_name);
      /* externe Methode (wegen fix_symconst!) */
      eset_insert(methods, MARK); /* free method -> unknown */
    }
467
468
469
470
471
472
    break;
  case iro_Sel:
    /* polymorphe Methode */
    for (i = get_Sel_n_methods(node) - 1; i >= 0; --i) {
      entity * ent = get_Sel_method(node, i);
      if (ent) {
Florian Liekweg's avatar
Florian Liekweg committed
473
        eset_insert(methods, ent);
474
      } else {
Florian Liekweg's avatar
Florian Liekweg committed
475
        eset_insert(methods, MARK);
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
      }
    }
    break;

  case iro_Bad:
    /* nothing */
    break;

  case iro_Phi: /* Vereinigung */
    for (i = get_Phi_n_preds(node) - 1; i >= 0; --i) {
      callee_ana_node(get_Phi_pred(node, i), methods);
    }
    break;

  case iro_Id:
    callee_ana_node(get_Id_pred(node), methods);
    break;

  case iro_Proj:
    callee_ana_proj(get_Proj_pred(node), get_Proj_proj(node), methods);
    break;

  case iro_Add:
  case iro_Sub:
  case iro_Conv:
    /* extern */
    eset_insert(methods, MARK); /* free method -> unknown */
    break;

  default:
    assert(0 && "invalid opcode or opcode not implemented");
    break;
  }

  set_irn_link(node, NULL);
}


static void callee_walker(ir_node * call, void * env) {
515
  if (get_irn_op(call) == op_Call) {
516
517
518
    eset * methods = eset_create();
    entity * ent;
    entity ** arr = NEW_ARR_F(entity *, 0);
519
    callee_ana_node(skip_Id(get_Call_ptr(call)), methods);
520
521
522
523
524
    if (eset_contains(methods, MARK)) { /* unknown method */
      ARR_APP1(entity *, arr, NULL);
    }
    for (ent = eset_first(methods); ent; ent = eset_next(methods)) {
      if (ent != MARK) {
525
	ARR_APP1(entity *, arr, ent);
526
527
      }
    }
528
529
530
#if 0  /* This generates Bad nodes when we don't want it.
	  Call it with a check for valid cgana information in local_optimize. */
    if (ARR_LEN(arr) == 0 && get_opt_optimize() && get_opt_dyn_meth_dispatch()) {
531
532
533
534
535
      /* Kann vorkommen, wenn der Vorgnger beispielsweise eine
       * Sel-Operation war, die keine Methoden zurckgeben
       * konnte. Wir ersetzen die Call-Operation ebenfalls durch
       * eine Bad-Operation. Die Verlinkung muss wiederhergestellt
       * werden! */
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
536
      ir_node *mem = get_Call_mem(call);
537
      turn_into_tuple (call, 5 /* pn_Call_max */);
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
538
539
540
541
      set_Tuple_pred(call, pn_Call_M_regular       , mem);
      set_Tuple_pred(call, pn_Call_T_result        , new_Bad());
      set_Tuple_pred(call, pn_Call_P_value_res_base, new_Bad());
      set_Tuple_pred(call, pn_Call_X_except        , new_Bad());  /* new_Jmp() ?? new_Raise() ?? */
542
      set_Tuple_pred(call, pn_Call_M_except        , new_Bad());
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
543

544
545
546
    } else
#endif
    {
547
548
549
550
551
552
553
554
      set_Call_callee_arr(call, ARR_LEN(arr), arr);
    }
    DEL_ARR_F(arr);
    eset_destroy(methods);
  }
}


555
556
557
558
559
560
561
562
563
static void remove_Tuples(ir_node * proj, void * env) {
  ir_node *new;
  if (get_irn_opcode(proj) != iro_Proj) return;

  new = skip_Tuple(proj);
  if (new != proj) exchange(proj, new);
}


564
565
566
567
568
569
570
571
/* Bestimmt fr jede Call-Operation die Menge der aufrufbaren Methode
 * und speichert das Ergebnis in der Call-Operation. (siehe
 * "set_Call_callee"). "sel_methods" wird fr den Aufbau bentigt und
 * muss bereits aufgebaut sein. */
static void callee_ana(void) {
  int i;
  /* Alle Graphen analysieren. */
  for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
572
    irg_walk_graph(get_irp_irg(i), callee_walker, remove_Tuples, NULL);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
573
    set_irg_callee_info_state(get_irp_irg(i), irg_callee_info_consistent);
574
  }
Götz Lindenmaier's avatar
Götz Lindenmaier committed
575
  set_irp_callee_info_state(irg_callee_info_consistent);
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
}



/* --- free method analysis ------------------------------------------------- */


static void free_mark(ir_node * node, eset * set);

static void free_mark_proj(ir_node * node, long n, eset * set) {
  assert(get_irn_mode(node) == mode_T);
  if (get_irn_link(node) == MARK) {
    /* already visited */
    return;
  }
  set_irn_link(node, MARK);
592
  switch (get_irn_opcode(node)) {
593
594
595
596
597
  case iro_Proj: {
    /* proj_proj: in einem "sinnvollen" Graphen kommt jetzt ein
     * op_Tuple oder ein Knoten, der in "free_ana_walker" behandelt
     * wird. */
    ir_node * pred = get_Proj_pred(node);
598
    if (get_irn_link(pred) != MARK && get_irn_op(pred) == op_Tuple) {
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
626
627
628
629
630
      free_mark_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, set);
    } else {
      /* nothing: da in "free_ana_walker" behandelt. */
    }
    break;
  }

  case iro_Tuple:
    free_mark(get_Tuple_pred(node, n), set);
    break;

  case iro_Id:
    free_mark_proj(get_Id_pred(node), n, set);
    break;

  case iro_Start:
  case iro_Alloc:
  case iro_Load:
    /* nothing: Die Operationen werden in "free_ana_walker" selbst
     * behandelt. */
    break;

  default:
    assert(0 && "unexpected opcode or opcode not implemented");
    break;
  }
  set_irn_link(node, NULL);
}


static void free_mark(ir_node * node, eset * set) {
  int i;
631
//  assert(mode_is_reference(get_irn_mode(node)));
632
633
634
635
  if (get_irn_link(node) == MARK) {
    return; /* already visited */
  }
  set_irn_link(node, MARK);
636
  switch (get_irn_opcode(node)) {
637
638
639
640
  case iro_Sel: {
    entity * ent = get_Sel_entity(node);
    if (is_method_type(get_entity_type(ent))) {
      for (i = get_Sel_n_methods(node) - 1; i >= 0; --i) {
Florian Liekweg's avatar
Florian Liekweg committed
641
    eset_insert(set, get_Sel_method(node, i));
642
643
644
645
646
      }
    }
    break;
  }
  case iro_SymConst:
Beyhan's avatar
Beyhan committed
647
648
649
650
651
652
653
654
655
    if (get_SymConst_kind(node) == symconst_addr_ent) {
      entity * ent = get_SymConst_entity(node);
      if (is_method_type(get_entity_type(ent))) {
        eset_insert(set, ent);
      }
    } else {
      assert(get_SymConst_kind(node) == symconst_addr_name);
      /* nothing: SymConst points to extern method */
    }
656
    break;
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
  case iro_Phi:
    for (i = get_Phi_n_preds(node) - 1; i >= 0; --i) {
      free_mark(get_Phi_pred(node, i), set);
    }
    break;
  case iro_Id:
    free_mark(get_Id_pred(node), set);
    break;
  case iro_Proj:
    free_mark_proj(get_Proj_pred(node), get_Proj_proj(node), set);
    break;
  default:
    /* nothing: Wird unten behandelt! */
    break;
  }
  set_irn_link(node, NULL);
}


static void free_ana_walker(ir_node * node, eset * set) {
  int i;
  if (get_irn_link(node) == MARK) {
    /* bereits in einem Zyklus besucht. */
    return;
  }
683
  switch (get_irn_opcode(node)) {
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
  /* special nodes */
  case iro_Sel:
  case iro_SymConst:
  case iro_Const:
  case iro_Phi:
  case iro_Id:
  case iro_Proj:
  case iro_Tuple:
    /* nothing */
    break;
  /* Sonderbehandlung, da der Funktionszeigereingang natrlich kein
   * Verrter ist. */
  case iro_Call:
    set_irn_link(node, MARK);
    for (i = get_Call_arity(node) - 1; i >= 0; --i) {
      ir_node * pred = get_Call_param(node, i);
700
      if (mode_is_reference(get_irn_mode(pred))) {
701
    free_mark(pred, set);
702
703
704
705
706
707
708
      }
    }
    break;
  /* other nodes: Alle anderen Knoten nehmen wir als Verrter an, bis
   * jemand das Gegenteil implementiert. */
  default:
    set_irn_link(node, MARK);
709
    for (i = get_irn_arity(node) - 1; i >= 0; --i) {
710
      ir_node * pred = get_irn_n(node, i);
711
      if (mode_is_reference(get_irn_mode(pred))) {
712
    free_mark(pred, set);
713
714
715
716
717
718
719
720
721
722
723
724
725
      }
    }
    break;
  }
  set_irn_link(node, NULL);
}


/* Die Datenstrukturen fr sel-Methoden (sel_methods) mu vor dem
 * Aufruf von "get_free_methods" aufgebaut sein. Die (internen)
 * SymConst-Operationen mssen in passende Const-Operationen
 * umgewandelt worden sein, d.h. SymConst-Operationen verweisen immer
 * auf eine echt externe Methode.  */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
726
static entity ** get_free_methods(void)
727
{
728
729
730
731
  eset * set = eset_create();
  int i;
  entity ** arr = NEW_ARR_F(entity *, 0);
  entity * ent;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
732

Götz Lindenmaier's avatar
Götz Lindenmaier committed
733
734
735
736
737
738
  for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
    ir_graph * irg = get_irp_irg(i);
    entity * ent = get_irg_entity(irg);
    /* insert "external visible" methods. */
    if (get_entity_visibility(ent) != visibility_local) {
      eset_insert(set, ent);
739
    }
Götz Lindenmaier's avatar
Götz Lindenmaier committed
740
741
742
    /* Finde alle Methoden die in dieser Methode extern sichtbar werden,
       z.B. da die Adresse einer Methode abgespeichert wird. */
    irg_walk_graph(irg, NULL, (irg_walk_func *) free_ana_walker, set);
743
744
745
  }

  /* insert sticky methods, too */
746
747
  for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
    ir_graph * irg = get_irp_irg(i);
748
    entity * ent = get_irg_entity(irg);
749
    /* insert "external visible" methods. */
750
    if (get_entity_stickyness (ent) == stickyness_sticky) {
751
752
753
      eset_insert(set, ent);
    }
  }
754

Götz Lindenmaier's avatar
Götz Lindenmaier committed
755
  /* Hauptprogramm ist auch dann frei, wenn es nicht "external
756
   * visible" ist. */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
757
  if (get_irp_main_irg()) {
758
    eset_insert(set, get_irg_entity(get_irp_main_irg()));
Boris Boesler's avatar
Boris Boesler committed
759
  }
Götz Lindenmaier's avatar
Götz Lindenmaier committed
760
  /* Wandle Menge in Feld um.  Effizienter. */
761
762
763
764
765
766
767
768
  for (ent = eset_first(set); ent; ent = eset_next(set)) {
    ARR_APP1(entity *, arr, ent);
  }
  eset_destroy(set);

  return arr;
}

Götz Lindenmaier's avatar
Götz Lindenmaier committed
769
void cgana(int *length, entity ***free_methods) {
770
  entity ** free_meths, **p;
771
772

  sel_methods_init();
Götz Lindenmaier's avatar
Götz Lindenmaier committed
773
  free_meths = get_free_methods();
774
775
776
777
778
  callee_ana();
  sel_methods_dispose();

  /* Convert the flexible array to an array that can be handled
     by standard C. */
779
780
781
782
783
784
  p = (entity **)malloc(sizeof(*p) * ARR_LEN(free_meths));
  memcpy(p, free_meths, ARR_LEN(free_meths) * sizeof(*p));

  *length       = ARR_LEN(free_meths);
  *free_methods = p;

785
786
  DEL_ARR_F(free_meths);
}
787

Götz Lindenmaier's avatar
Götz Lindenmaier committed
788
789
790
791
792
793
794
795
796
797
798
799
800
801


static void destruct_walker(ir_node * node, void * env) {
  if (get_irn_op(node) == op_Call) {
    remove_Call_callee_arr(node);
  }
}

void free_callee_info(ir_graph *irg) {
  irg_walk_graph(irg, destruct_walker, NULL, NULL);
  set_irg_callee_info_state(irg, irg_callee_info_none);
}


802
/* Optimize the address expressions passed to call nodes.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
803
804
805
806
807
808
809
810
811
812
813
814
815
 *
 * This optimization performs the following transformations for
 * all ir graphs:
 * - All SymConst operations that refer to intern methods are replaced
 *   by Const operations refering to the corresponding entity.
 * - Sel nodes, that select entities that are not overwritten are
 *   replaced by Const nodes refering to the selected entity.
 * - Sel nodes, for witch no method exists at all are replaced by Bad
 *   nodes.
 * - Sel nodes with a pointer input that is an Alloc node are replaced
 *   by Const nodes refering to the entity that implements the method in
 *   the type given by the Alloc node.
 */
816
817
818
819
820
821
822
823
824
void opt_call_addrs(void) {
  sel_methods_init();
  sel_methods_dispose();
#if 0
  int i;
  pmap * ldname_map = pmap_create();
  assert(entities == NULL);
  entities = eset_create();
  for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
825
    entity * ent = get_irg_entity(get_irp_irg(i));
826
827
828
829
830
831
    /* Nur extern sichtbare Methoden knnen berhaupt mit SymConst
     * aufgerufen werden. */
    if (get_entity_visibility(ent) != local) {
      pmap_insert(ldname_map, (void *) get_entity_ld_ident(ent), ent);
    }
  }
832
  all_irg_walk((irg_walk_func *) sel_methods_walker, NULL, ldname_map);
833
834
835
  pmap_destroy(ldname_map);
#endif
}