cgana.c 24.5 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.
 */

/**
Michael Beck's avatar
Michael Beck committed
14
 * @file cgana.c
Florian Liekweg's avatar
Florian Liekweg committed
15
 * Intraprozedurale Analyse zur Abschtzung der Aufrufrelation. Es
16
17
18
 * 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
19
 */
20
21
22
#ifdef HAVE_CONFIG_H
# include <config.h>
#endif
23

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

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

Götz Lindenmaier's avatar
Götz Lindenmaier committed
35
#include "irflag_t.h"
Götz Lindenmaier's avatar
Götz Lindenmaier committed
36
#include "dbginfo_t.h"
Michael Beck's avatar
Michael Beck committed
37
#include "iropt_dbg.h"
Götz Lindenmaier's avatar
Götz Lindenmaier committed
38

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

43
44
#include "irdump.h"

Michael Beck's avatar
Michael Beck committed
45
46
#include "firmstat.h"

47
48
49
50
51
52
53
54
55
56
57
58
/* Eindeutige Adresse zur Markierung von besuchten Knoten und zur
 * Darstellung der unbekannten Methode. */
static void * MARK = &MARK;



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


static eset * entities = NULL;


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

83
84
85
/** 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) {
86
87
  entity *impl_meth = NULL;
  ir_node *addr = get_atomic_ent_value(inh_meth);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
88

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

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

98
  if (impl_meth && (get_entity_peculiarity(impl_meth) != peculiarity_existent)) {
99
100
101
102
103
104
    /*
      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;
105
106
107
108
  }
  return impl_meth? impl_meth : inh_meth;
}

109

110
111
112
113
114
115
116
117
118
119
120
121
122
123
/** 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) {
124
  int i;
125

126
  if (get_entity_peculiarity(method) == peculiarity_existent) {
Boris Boesler's avatar
Boris Boesler committed
127
128
    if ((get_entity_visibility(method) == visibility_external_allocated)
	&& (NULL == get_entity_irg(method))) {
129
130
131
      *open = true;
    } else {
      assert(get_entity_irg(method) != NULL);
132
      if (!eset_contains(set, method)) {
Florian Liekweg's avatar
Florian Liekweg committed
133
134
        eset_insert(set, method);
        ++(*size);
135
      }
136
137
    }
  }
138

139
  if (get_entity_peculiarity(method) == peculiarity_inherited) {
140
141
    entity *impl_ent = get_inherited_methods_implementation(method);
    assert(impl_ent && "no implementation for inherited entity");
142
    if (get_entity_visibility(impl_ent) == visibility_external_allocated) {
143
144
145
146
147
      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
148
149
        eset_insert(set, impl_ent);
        ++(*size);
150
151
152
      }
    }
  }
Michael Beck's avatar
Michael Beck committed
153
  /*- recursive descent -*/
154
  for (i = get_entity_n_overwrittenby(method) - 1; i >= 0; --i)
155
    collect_impls(get_entity_overwrittenby(method, i), set, size, open);
156
157
}

158

159
160
161
162
163
164
165
166
167
168
/** 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
 */
169
170
171
172
173
static entity ** get_impl_methods(entity * method) {
  eset * set = eset_create();
  int size = 0;
  entity ** arr;
  bool open = false;
174

175
  /* Collect all method entities that can be called here */
176
177
  collect_impls(method, set, &size, &open);

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

198
199
/** Analyse address computations.
 *
200
 *  - If the node is a SymConst(name) replace it by SymConst(ent) if possible.
201
202
 *  - If the node is a Sel:
 *    * If the pointer to the Sel comes directly from an Alloc node
203
 *      replace the Sel by a SymConst(ent).
204
205
206
207
208
 *
 *
 *  @param node The node to analyze
 *  @param ldname_map A map that mapps names of entities to the entities.
 */
209
static void sel_methods_walker(ir_node * node, pmap * ldname_map) {
210

211
  /* replace SymConst(name)-operations by SymConst(ent) */
212
  if (get_irn_op(node) == op_SymConst) {
Beyhan's avatar
Beyhan committed
213
214
    if (get_SymConst_kind(node) == symconst_addr_name) {
      pmap_entry * entry = pmap_find(ldname_map, (void *) get_SymConst_name(node));
215
      if (entry != NULL) { /* Method is declared in the compiled code */
216
217
218
219
	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));
Michael Beck's avatar
Michael Beck committed
220
221
222

	  DBG_OPT_CSTEVAL(node, new_node);

223
224
225
226
	  assert(get_entity_irg(ent));
	  DDMN(new_node);
	  exchange(node, new_node);
	}
227
228
      }
    }
229
230
231
232
  }

  else if (get_irn_op(node) == op_Sel &&
	   is_method_type(get_entity_type(get_Sel_entity(node)))) {
233
    entity * ent = get_Sel_entity(node);
234
235

    /* Sel from Alloc: replace by constant */
236
    if (get_opt_optimize() && get_opt_dyn_meth_dispatch() &&
237
        (get_irn_op(skip_Proj(get_Sel_ptr(node))) == op_Alloc)) {
Götz Lindenmaier's avatar
Götz Lindenmaier committed
238
      ir_node *new_node;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
239
      entity *called_ent;
240
      /* We know which method will be called, no dispatch necessary. */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
241
      called_ent = resolve_ent_polymorphy(get_Alloc_type(skip_Proj(get_Sel_ptr(node))), ent);
242
      set_irg_current_block(current_ir_graph, get_nodes_block(node));
Götz Lindenmaier's avatar
Götz Lindenmaier committed
243
244
      /* called_ent may not be description: has no Address/Const to Call! */
      assert(get_entity_peculiarity(called_ent) != peculiarity_description);
Michael Beck's avatar
Michael Beck committed
245
246
247
248
      new_node = copy_const_value(get_atomic_ent_value(called_ent));

      DBG_OPT_POLY_ALLOC(node, new_node);
      exchange(node, new_node);
249
250
251
    }

    else {
252
      assert(get_entity_peculiarity(ent) != peculiarity_inherited);
253
      if (!eset_contains(entities, ent)) {
Florian Liekweg's avatar
Florian Liekweg committed
254
255
256
257
258
        /* 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);
259
260
      }
      if (get_entity_link(ent) == NULL) {
Florian Liekweg's avatar
Florian Liekweg committed
261
262
263
264
265
266
        /* 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) {
267
	  /* This is possible:  We call a method in a dead part of the program. */
Florian Liekweg's avatar
Florian Liekweg committed
268
        } else {
269
270
271
	  DDMN(node);
	  assert(0);  /* Why should this happen ??? */
          //exchange(node, new_Bad());
Florian Liekweg's avatar
Florian Liekweg committed
272
        }
273
      } else {
Florian Liekweg's avatar
Florian Liekweg committed
274
        entity ** arr = get_entity_link(ent);
275
276

#if 0
Florian Liekweg's avatar
Florian Liekweg committed
277
278
        int i;
        printf("\nCall site "); DDMN(node);
279
        printf("  in "); DDME(get_irg_entity(current_ir_graph));
Florian Liekweg's avatar
Florian Liekweg committed
280
281
282
283
284
285
        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");
286
287
#endif

Florian Liekweg's avatar
Florian Liekweg committed
288
289
290
        if (get_opt_optimize() && get_opt_dyn_meth_dispatch() &&
            (ARR_LEN(arr) == 1 && arr[0] != NULL)) {
          ir_node *new_node;
291
          /* Die Sel-Operation kann immer nur _einen_ Wert auf eine
Florian Liekweg's avatar
Florian Liekweg committed
292
293
294
           * interne Methode zurckgeben. Wir knnen daher die
           * Sel-Operation durch eine Const- bzw. SymConst-Operation
           * ersetzen. */
295
          set_irg_current_block(current_ir_graph, get_nodes_block(node));
296
297
          assert(get_entity_peculiarity(get_SymConst_entity(get_atomic_ent_value(arr[0]))) ==
	         peculiarity_existent);
Michael Beck's avatar
Michael Beck committed
298
299
          new_node = copy_const_value(get_atomic_ent_value(arr[0]));
          DBG_OPT_POLY(node, new_node);
Florian Liekweg's avatar
Florian Liekweg committed
300
301
          exchange (node, new_node);
        }
302
303
304
305
306
307
      }
    }
  }
}


308
/** Datenstruktur initialisieren. Zustzlich werden alle
309
310
 *  SymConst(name)-Operationen, die auf interne Methoden verweisen, durch
 *  SymConst(entity)-Operationen ersetzt. */
311
312
static void sel_methods_init(void) {
  int i;
313
314
  pmap * ldname_map = pmap_create();   /* Map entitiy names to entities: to replace SymConst(name) by SymConst(ent). */

315
316
317
  assert(entities == NULL);
  entities = eset_create();
  for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
318
    entity * ent = get_irg_entity(get_irp_irg(i));
319
320
    /* Nur extern sichtbare Methode knnen berhaupt mit SymConst
     * aufgerufen werden. */
321
    if (get_entity_visibility(ent) != visibility_local) {
322
323
324
      pmap_insert(ldname_map, (void *) get_entity_ld_ident(ent), ent);
    }
  }
325
  all_irg_walk((irg_walk_func *) sel_methods_walker, NULL, ldname_map);
326
327
328
  pmap_destroy(ldname_map);
}

329
/*****************************************************************************/
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353

/* 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;
354
  assert(sel && get_irn_op(sel) == op_Sel);
355
356
357
358
359
360
361
362
363
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
  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);

398
  switch (get_irn_opcode(node)) {
399
400
401
402
403
404
  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) {
405
      if (get_irn_op(pred) == op_Tuple) {
Florian Liekweg's avatar
Florian Liekweg committed
406
    callee_ana_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, methods);
407
      } else {
Florian Liekweg's avatar
Florian Liekweg committed
408
    eset_insert(methods, MARK); /* free method -> unknown */
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
      }
    }
    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
434
  assert(mode_is_reference(get_irn_mode(node)) || is_Bad(node));
435
436
437
438
439
440
441
  /* rekursion verhindern */
  if (get_irn_link(node) == MARK) {
    /* already visited */
    return;
  }
  set_irn_link(node, MARK);

442
  switch (get_irn_opcode(node)) {
443
  case iro_SymConst:
Beyhan's avatar
Beyhan committed
444
445
446
447
    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) {
448
449
	assert(get_entity_irg(ent));
	eset_insert(methods, ent);
Beyhan's avatar
Beyhan committed
450
      } else {
451
	eset_insert(methods, MARK); /* free method -> unknown */
Beyhan's avatar
Beyhan committed
452
453
454
455
456
457
      }
    } else {
      assert(get_SymConst_kind(node) == symconst_addr_name);
      /* externe Methode (wegen fix_symconst!) */
      eset_insert(methods, MARK); /* free method -> unknown */
    }
458
459
460
461
462
463
    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
464
        eset_insert(methods, ent);
465
      } else {
Florian Liekweg's avatar
Florian Liekweg committed
466
        eset_insert(methods, MARK);
467
468
469
470
471
472
473
474
475
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
      }
    }
    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) {
506
  if (get_irn_op(call) == op_Call) {
507
508
509
    eset * methods = eset_create();
    entity * ent;
    entity ** arr = NEW_ARR_F(entity *, 0);
510
    callee_ana_node(skip_Id(get_Call_ptr(call)), methods);
511
    if (eset_contains(methods, MARK)) { /* unknown method */
512
      ARR_APP1(entity *, arr, unknown_entity);
513
514
515
    }
    for (ent = eset_first(methods); ent; ent = eset_next(methods)) {
      if (ent != MARK) {
516
	ARR_APP1(entity *, arr, ent);
517
518
      }
    }
519
520
521
#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()) {
522
523
524
525
526
      /* 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
527
      ir_node *mem = get_Call_mem(call);
528
      turn_into_tuple (call, 5 /* pn_Call_max */);
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
529
530
531
532
      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() ?? */
533
      set_Tuple_pred(call, pn_Call_M_except        , new_Bad());
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
534

535
536
537
    } else
#endif
    {
538
539
540
541
542
543
544
      /* remove, what we repaired. */
      int i;
      for (i = 0; i < ARR_LEN(arr); ++i) {
	assert(arr[i]);
	//if (arr[i] == unknown_entity) arr[i] = NULL;
      }

545
546
547
548
549
550
551
552
      set_Call_callee_arr(call, ARR_LEN(arr), arr);
    }
    DEL_ARR_F(arr);
    eset_destroy(methods);
  }
}


553
554
555
556
557
558
559
560
561
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);
}


562
563
564
565
566
567
568
569
/* 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) {
570
    irg_walk_graph(get_irp_irg(i), callee_walker, remove_Tuples, NULL);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
571
    set_irg_callee_info_state(get_irp_irg(i), irg_callee_info_consistent);
572
  }
Götz Lindenmaier's avatar
Götz Lindenmaier committed
573
  set_irp_callee_info_state(irg_callee_info_consistent);
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
}



/* --- 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);
590
  switch (get_irn_opcode(node)) {
591
592
593
594
595
  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);
596
    if (get_irn_link(pred) != MARK && get_irn_op(pred) == op_Tuple) {
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
626
627
628
      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;
629
//  assert(mode_is_reference(get_irn_mode(node)));
630
631
632
633
  if (get_irn_link(node) == MARK) {
    return; /* already visited */
  }
  set_irn_link(node, MARK);
634
  switch (get_irn_opcode(node)) {
635
636
637
638
  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
639
    eset_insert(set, get_Sel_method(node, i));
640
641
642
643
644
      }
    }
    break;
  }
  case iro_SymConst:
Beyhan's avatar
Beyhan committed
645
646
647
648
649
650
651
652
653
    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 */
    }
654
    break;
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
  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;
  }
681
  switch (get_irn_opcode(node)) {
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
  /* 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);
698
      if (mode_is_reference(get_irn_mode(pred))) {
Michael Beck's avatar
Michael Beck committed
699
        free_mark(pred, set);
700
701
702
703
704
705
706
      }
    }
    break;
  /* other nodes: Alle anderen Knoten nehmen wir als Verrter an, bis
   * jemand das Gegenteil implementiert. */
  default:
    set_irn_link(node, MARK);
707
    for (i = get_irn_arity(node) - 1; i >= 0; --i) {
708
      ir_node * pred = get_irn_n(node, i);
709
      if (mode_is_reference(get_irn_mode(pred))) {
Michael Beck's avatar
Michael Beck committed
710
        free_mark(pred, set);
711
712
713
714
715
716
717
718
719
720
721
722
723
      }
    }
    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
724
static entity ** get_free_methods(void)
725
{
726
727
728
729
  eset * set = eset_create();
  int i;
  entity ** arr = NEW_ARR_F(entity *, 0);
  entity * ent;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
730

Götz Lindenmaier's avatar
Götz Lindenmaier committed
731
732
733
734
735
736
  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);
737
    }
Götz Lindenmaier's avatar
Götz Lindenmaier committed
738
739
740
    /* 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);
741
742
743
  }

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

Götz Lindenmaier's avatar
Götz Lindenmaier committed
753
  /* Hauptprogramm ist auch dann frei, wenn es nicht "external
754
   * visible" ist. */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
755
  if (get_irp_main_irg()) {
756
    eset_insert(set, get_irg_entity(get_irp_main_irg()));
Boris Boesler's avatar
Boris Boesler committed
757
  }
Götz Lindenmaier's avatar
Götz Lindenmaier committed
758
  /* Wandle Menge in Feld um.  Effizienter. */
759
760
761
762
763
764
765
766
  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
767
void cgana(int *length, entity ***free_methods) {
768
  entity ** free_meths, **p;
769
770

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

  /* Convert the flexible array to an array that can be handled
     by standard C. */
777
778
779
780
781
782
  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;

783
784
  DEL_ARR_F(free_meths);
}
785

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


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);
}


800
/* Optimize the address expressions passed to call nodes.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
801
802
803
804
805
806
807
808
809
810
811
812
813
 *
 * 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.
 */
814
815
816
817
818
819
820
821
822
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) {
823
    entity * ent = get_irg_entity(get_irp_irg(i));
824
825
826
827
828
829
    /* 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);
    }
  }
830
  all_irg_walk((irg_walk_func *) sel_methods_walker, NULL, ldname_map);
831
832
833
  pmap_destroy(ldname_map);
#endif
}