cgana.c 26.3 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
#ifdef HAVE_CONFIG_H
Michael Beck's avatar
Michael Beck committed
21
22
23
24
25
# include "config.h"
#endif

#ifdef HAVE_STRING_H
# include <string.h>
26
#endif
27
28

#include "cgana.h"
Florian Liekweg's avatar
Florian Liekweg committed
29
#include "rta.h"
30

Michael Beck's avatar
Michael Beck committed
31
#include "xmalloc.h"
Götz Lindenmaier's avatar
Götz Lindenmaier committed
32
33
34
#include "irnode_t.h"
#include "irmode_t.h"
#include "irprog_t.h"
35
36
37
38
#include "irgwalk.h"
#include "ircons.h"
#include "irgmod.h"

Götz Lindenmaier's avatar
Götz Lindenmaier committed
39
#include "irflag_t.h"
Götz Lindenmaier's avatar
Götz Lindenmaier committed
40
#include "dbginfo_t.h"
Michael Beck's avatar
Michael Beck committed
41
#include "iropt_dbg.h"
Götz Lindenmaier's avatar
Götz Lindenmaier committed
42

Götz Lindenmaier's avatar
Götz Lindenmaier committed
43
44
45
#include "eset.h"
#include "pmap.h"
#include "array.h"
Götz Lindenmaier's avatar
Götz Lindenmaier committed
46

47
48
#include "irdump.h"

Michael Beck's avatar
Michael Beck committed
49
50
#include "firmstat.h"

51
52
53
54
55
56
57
58
59
60
61
62
/* Eindeutige Adresse zur Markierung von besuchten Knoten und zur
 * Darstellung der unbekannten Methode. */
static void * MARK = &MARK;



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


static eset * entities = NULL;


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

87
88
89
/** 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) {
90
91
92
93
94
95
96
97
  assert(get_atomic_ent_value(inh_meth) && "constant entity without value");
  assert((get_irn_op(get_atomic_ent_value(inh_meth)) == op_SymConst) &&
	 (get_SymConst_kind(get_atomic_ent_value(inh_meth)) == symconst_addr_ent) &&
	 "Complex constant values not supported -- address of method should be straight constant!");

  return get_SymConst_entity(get_atomic_ent_value(inh_meth));

#if 0  // this stuff is outdated, I think. GL 10.11.04
98
99
  entity *impl_meth = NULL;
  ir_node *addr = get_atomic_ent_value(inh_meth);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
100

101
  assert(get_atomic_ent_value(inh_meth) && "constant entity without value");
Götz Lindenmaier's avatar
Götz Lindenmaier committed
102

103
  if ((get_irn_op(addr) == op_SymConst) &&
Götz Lindenmaier's avatar
Götz Lindenmaier committed
104
      (get_SymConst_kind(addr) == symconst_addr_ent)) {
Beyhan's avatar
Beyhan committed
105
    impl_meth = get_SymConst_entity(addr);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
106
  } else {
Florian Liekweg's avatar
Florian Liekweg committed
107
    assert(0 && "Complex constant values not supported -- address of method should be straight constant!");
Götz Lindenmaier's avatar
Götz Lindenmaier committed
108
  }
Götz Lindenmaier's avatar
Götz Lindenmaier committed
109

110
  if (impl_meth && (get_entity_peculiarity(impl_meth) != peculiarity_existent)) {
111
112
113
114
115
    /*
      printf("this_meth: "); DDMEO(inh_meth);
      printf("impl meth: "); DDMEO(impl_meth);
      assert(!impl_meth || get_entity_peculiarity(impl_meth) == peculiarity_existent);
    */
116
    assert(0);
117
    impl_meth = NULL;
118
  }
119
  assert((impl_meth || inh_meth) && "no implementation for inherited entity");
120
  return impl_meth? impl_meth : inh_meth;
121
#endif
122
123
}

124

125
126
127
128
129
130
131
132
133
134
135
136
137
138
/** 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) {
139
  int i;
Michael Beck's avatar
Michael Beck committed
140
141
  entity *impl;

142
#if 0
143
  if (get_entity_peculiarity(method) == peculiarity_existent) {
Boris Boesler's avatar
Boris Boesler committed
144
145
    if ((get_entity_visibility(method) == visibility_external_allocated)
	&& (NULL == get_entity_irg(method))) {
146
147
      /* We could also add these entities to the callees, but right now we
	 subsume them by unknown_entity. */
148
149
150
      *open = true;
    } else {
      assert(get_entity_irg(method) != NULL);
151
      if (!eset_contains(set, method)) {
Florian Liekweg's avatar
Florian Liekweg committed
152
153
        eset_insert(set, method);
        ++(*size);
154
      }
155
156
    }
  }
157

158
  if (get_entity_peculiarity(method) == peculiarity_inherited) {
159
    entity *impl_ent = get_inherited_methods_implementation(method);
160
    if (get_entity_visibility(impl_ent) == visibility_external_allocated) {
161
162
163
164
165
      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
166
167
        eset_insert(set, impl_ent);
        ++(*size);
168
169
170
      }
    }
  }
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
#endif
  /* Only the assertions: */
  if (get_entity_peculiarity(method) == peculiarity_existent) {
    if ((get_entity_visibility(method) == visibility_external_allocated)
	&& (NULL == get_entity_irg(method))) {
    } else {
      assert(get_entity_irg(method) != NULL);
    }
  }
  if (get_entity_peculiarity(method) == peculiarity_inherited) {
    entity *impl_ent = get_inherited_methods_implementation(method);
    if (get_entity_visibility(impl_ent) == visibility_external_allocated) {
      assert(get_entity_irg(impl_ent) == NULL);
    } else {
      assert(get_entity_irg(impl_ent) != NULL);
    }
  }

  /* Add the implementation to the set if it contains an irg, else
     remember that there are more methods called. */
  /* @@@ We could also add unknown_entity, or the entities with the
     unknown irgs.  The first case would result in the exact same
Michael Beck's avatar
Michael Beck committed
193
     behavior: all unknown irgs are represented by the one and only
194
195
196
     unknown entity. If we add all entities, we known the number of
     entities possibly called, and whether there are real unknown
     entities, i.e, such not represented in the type description.
Michael Beck's avatar
Michael Beck committed
197
     This would be better for an analysis: it could rule out more
198
     cases. */
Michael Beck's avatar
Michael Beck committed
199
  impl = method;
200
201
202
203
204
205
206
207
208
209
210
211
212
  if (get_entity_peculiarity(method) == peculiarity_inherited)
    impl = get_inherited_methods_implementation(method);

  if (get_entity_peculiarity(method) != peculiarity_description) {
    //if (get_entity_irg(impl)) {
    eset_insert(set, impl);
    ++(*size);
      //} else {
      /* GL: better: eset_insert(set, unknown_entity); */
      //*open = true;
      //}
  }

Michael Beck's avatar
Michael Beck committed
213
  /*- recursive descent -*/
214
  for (i = get_entity_n_overwrittenby(method) - 1; i >= 0; --i)
215
    collect_impls(get_entity_overwrittenby(method, i), set, size, open);
216
217
}

218

219
220
221
222
223
224
225
226
227
228
/** 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
 */
229
230
231
232
233
static entity ** get_impl_methods(entity * method) {
  eset * set = eset_create();
  int size = 0;
  entity ** arr;
  bool open = false;
234

235
  /* Collect all method entities that can be called here */
236
237
  collect_impls(method, set, &size, &open);

238
  /* Vorgaenger einfuegen. */
239
240
241
242
243
244
  if (size == 0 && !open) {
    /* keine implementierte berschriebene Methode */
    arr = NULL;
  } else if (open) {
    entity * ent;
    arr = NEW_ARR_F(entity *, size + 1);
245
246
247
    arr[0] = NULL;  /* Represents open method */
    for (ent = eset_first(set); size > 0; ent = eset_next(set), --size)
      arr[size] = ent;
248
249
250
  } else {
    entity * ent;
    arr = NEW_ARR_F(entity *, size);
251
252
    for (size -= 1, ent = eset_first(set); size >= 0; ent = eset_next(set), --size)
      arr[size] = ent;
253
254
255
256
257
  }
  eset_destroy(set);
  return arr;
}

Michael Beck's avatar
Michael Beck committed
258
/** Analyze address computations.
259
 *
260
 *  - If the node is a SymConst(name) replace it by SymConst(ent) if possible.
261
262
 *  - If the node is a Sel:
 *    * If the pointer to the Sel comes directly from an Alloc node
263
 *      replace the Sel by a SymConst(ent).
264
265
266
 *
 *
 *  @param node The node to analyze
267
 *  @param env  A map that maps names of entities to the entities.
268
 */
269
270
static void sel_methods_walker(ir_node * node, void *env) {
  pmap *ldname_map = env;
271

272
  /* replace SymConst(name)-operations by SymConst(ent) */
273
  if (get_irn_op(node) == op_SymConst) {
Beyhan's avatar
Beyhan committed
274
275
    if (get_SymConst_kind(node) == symconst_addr_name) {
      pmap_entry * entry = pmap_find(ldname_map, (void *) get_SymConst_name(node));
276
      if (entry != NULL) { /* Method is declared in the compiled code */
Michael Beck's avatar
Michael Beck committed
277
278
279
280
281
282
	    entity * ent = entry->value;
	    if (get_opt_normalize() && (get_entity_visibility(ent) != visibility_external_allocated)) { /* Meth. is defined */
          ir_node *new_node;

	      set_irg_current_block(current_ir_graph, get_nodes_block(node));
	      new_node = copy_const_value(get_atomic_ent_value(ent));
Michael Beck's avatar
Michael Beck committed
283

Michael Beck's avatar
Michael Beck committed
284
	      DBG_OPT_CSTEVAL(node, new_node);
Michael Beck's avatar
Michael Beck committed
285

Michael Beck's avatar
Michael Beck committed
286
287
288
289
	      assert(get_entity_irg(ent));
	      DDMN(new_node);
	      exchange(node, new_node);
	    }
290
291
      }
    }
292
293
294
  }
  else if (get_irn_op(node) == op_Sel &&
	   is_method_type(get_entity_type(get_Sel_entity(node)))) {
295
    entity * ent = get_Sel_entity(node);
296
297

    /* Sel from Alloc: replace by constant */
298
    if (get_opt_optimize() && get_opt_dyn_meth_dispatch() &&
299
        (get_irn_op(skip_Proj(get_Sel_ptr(node))) == op_Alloc)) {
Götz Lindenmaier's avatar
Götz Lindenmaier committed
300
      ir_node *new_node;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
301
      entity *called_ent;
302

303
      /* We know which method will be called, no dispatch necessary. */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
304
      called_ent = resolve_ent_polymorphy(get_Alloc_type(skip_Proj(get_Sel_ptr(node))), ent);
305
      set_irg_current_block(current_ir_graph, get_nodes_block(node));
306

Götz Lindenmaier's avatar
Götz Lindenmaier committed
307
308
      /* 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
309
310
311
312
      new_node = copy_const_value(get_atomic_ent_value(called_ent));

      DBG_OPT_POLY_ALLOC(node, new_node);
      exchange(node, new_node);
313
314
    }
    else {
315
      assert(get_entity_peculiarity(ent) != peculiarity_inherited);
316
      if (!eset_contains(entities, ent)) {
Florian Liekweg's avatar
Florian Liekweg committed
317
318
319
320
321
        /* 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);
322
323
      }
      if (get_entity_link(ent) == NULL) {
Florian Liekweg's avatar
Florian Liekweg committed
324
325
326
327
328
329
        /* 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) {
Michael Beck's avatar
Michael Beck committed
330
          /* This is possible:  We call a method in a dead part of the program. */
Florian Liekweg's avatar
Florian Liekweg committed
331
        } else {
Michael Beck's avatar
Michael Beck committed
332
333
	      DDMN(node);
	      assert(0);  /* Why should this happen ??? */
334
          //exchange(node, new_Bad());
Florian Liekweg's avatar
Florian Liekweg committed
335
        }
336
      } else {
Florian Liekweg's avatar
Florian Liekweg committed
337
        entity ** arr = get_entity_link(ent);
338
339

#if 0
Florian Liekweg's avatar
Florian Liekweg committed
340
341
        int i;
        printf("\nCall site "); DDMN(node);
342
        printf("  in "); DDME(get_irg_entity(current_ir_graph));
Florian Liekweg's avatar
Florian Liekweg committed
343
344
345
346
347
348
        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");
349
350
#endif

Florian Liekweg's avatar
Florian Liekweg committed
351
352
353
        if (get_opt_optimize() && get_opt_dyn_meth_dispatch() &&
            (ARR_LEN(arr) == 1 && arr[0] != NULL)) {
          ir_node *new_node;
354
          /* Die Sel-Operation kann immer nur _einen_ Wert auf eine
Florian Liekweg's avatar
Florian Liekweg committed
355
356
357
           * interne Methode zurckgeben. Wir knnen daher die
           * Sel-Operation durch eine Const- bzw. SymConst-Operation
           * ersetzen. */
358
          set_irg_current_block(current_ir_graph, get_nodes_block(node));
359
360
          assert(get_entity_peculiarity(get_SymConst_entity(get_atomic_ent_value(arr[0]))) ==
	         peculiarity_existent);
Michael Beck's avatar
Michael Beck committed
361
362
          new_node = copy_const_value(get_atomic_ent_value(arr[0]));
          DBG_OPT_POLY(node, new_node);
Florian Liekweg's avatar
Florian Liekweg committed
363
364
          exchange (node, new_node);
        }
365
366
367
368
369
370
      }
    }
  }
}


371
/** Datenstruktur initialisieren. Zustzlich werden alle
372
373
 *  SymConst(name)-Operationen, die auf interne Methoden verweisen, durch
 *  SymConst(entity)-Operationen ersetzt. */
374
375
static void sel_methods_init(void) {
  int i;
376
  pmap * ldname_map = pmap_create();   /* Map entity names to entities: to replace SymConst(name) by SymConst(ent). */
377

378
379
  assert(entities == NULL);
  entities = eset_create();
Götz Lindenmaier's avatar
Götz Lindenmaier committed
380
381
382
383
  for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
    ir_graph *irg = get_irp_irg(i);
    entity * ent = get_irg_entity(irg);
    /* Nur extern sichtbare Methoden knnen berhaupt mit SymConst
384
     * aufgerufen werden. */
385
    if (get_entity_visibility(ent) != visibility_local) {
386
387
388
      pmap_insert(ldname_map, (void *) get_entity_ld_ident(ent), ent);
    }
  }
389
  all_irg_walk(sel_methods_walker, NULL, ldname_map);
390
391
392
  pmap_destroy(ldname_map);
}

393
/*****************************************************************************/
394

395
/** Frees the allocated entity map */
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
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;
}


411
412
413
414
/**
 * Returns an array of all methods that could be called at a Sel node.
 * This array contains every entry only once.
 */
415
416
417
418
static entity ** get_Sel_arr(ir_node * sel) {
  static entity ** NULL_ARRAY = NULL;
  entity * ent;
  entity ** arr;
419

420
  assert(sel && get_irn_op(sel) == op_Sel);
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
  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;
  }
}

436
437
438
/**
 * Returns the number of possible called methods at a Sel node.
 */
439
440
441
442
static int get_Sel_n_methods(ir_node * sel) {
  return ARR_LEN(get_Sel_arr(sel));
}

443
444
445
/**
 * Returns the ith possible called method entity at a Sel node.
 */
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
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);

468
  switch (get_irn_opcode(node)) {
469
470
471
472
473
474
  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) {
475
      if (get_irn_op(pred) == op_Tuple) {
476
        callee_ana_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, methods);
477
      } else {
478
        eset_insert(methods, MARK); /* free method -> unknown */
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
      }
    }
    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
504
  assert(mode_is_reference(get_irn_mode(node)) || is_Bad(node));
505
506
507
508
509
510
511
  /* rekursion verhindern */
  if (get_irn_link(node) == MARK) {
    /* already visited */
    return;
  }
  set_irn_link(node, MARK);

512
  switch (get_irn_opcode(node)) {
513
  case iro_SymConst:
Beyhan's avatar
Beyhan committed
514
515
516
    if (get_SymConst_kind(node) == symconst_addr_ent) {
      entity * ent = get_SymConst_entity(node);
      assert(ent && is_method_type(get_entity_type(ent)));
517
      eset_insert(methods, ent);
Beyhan's avatar
Beyhan committed
518
519
520
521
522
    } else {
      assert(get_SymConst_kind(node) == symconst_addr_name);
      /* externe Methode (wegen fix_symconst!) */
      eset_insert(methods, MARK); /* free method -> unknown */
    }
523
524
525
526
527
528
    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
529
        eset_insert(methods, ent);
530
      } else {
Florian Liekweg's avatar
Florian Liekweg committed
531
        eset_insert(methods, MARK);
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
      }
    }
    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) {
571
  if (get_irn_op(call) == op_Call) {
572
573
574
    eset * methods = eset_create();
    entity * ent;
    entity ** arr = NEW_ARR_F(entity *, 0);
575
576
    assert(get_irn_op(get_Call_ptr(call)) != op_Id);
    callee_ana_node(get_Call_ptr(call), methods);
577
    if (eset_contains(methods, MARK)) { /* unknown method */
578
      ARR_APP1(entity *, arr, unknown_entity);
579
580
581
    }
    for (ent = eset_first(methods); ent; ent = eset_next(methods)) {
      if (ent != MARK) {
582
	ARR_APP1(entity *, arr, ent);
583
584
      }
    }
585
586
587
#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()) {
588
589
590
591
592
      /* 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
593
      ir_node *mem = get_Call_mem(call);
594
      turn_into_tuple (call, 5 /* pn_Call_max */);
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
595
596
597
598
      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() ?? */
599
      set_Tuple_pred(call, pn_Call_M_except        , new_Bad());
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
600

601
602
603
    } else
#endif
    {
604
605
606
607
608
609
610
      /* 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;
      }

611
612
613
614
615
616
617
618
      set_Call_callee_arr(call, ARR_LEN(arr), arr);
    }
    DEL_ARR_F(arr);
    eset_destroy(methods);
  }
}


619
620
621
622
623
624
625
626
627
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);
}


628
629
630
631
632
633
634
/* 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. */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
635
636
637
  for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
    irg_walk_graph(get_irp_irg(i), callee_walker, remove_Tuples, NULL);
    set_irg_callee_info_state(get_irp_irg(i), irg_callee_info_consistent);
638
  }
Götz Lindenmaier's avatar
Götz Lindenmaier committed
639
  set_irp_callee_info_state(irg_callee_info_consistent);
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
}



/* --- 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);
656
  switch (get_irn_opcode(node)) {
657
658
659
660
661
  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);
662
    if (get_irn_link(pred) != MARK && get_irn_op(pred) == op_Tuple) {
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
      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;
695

696
697
698
699
  if (get_irn_link(node) == MARK) {
    return; /* already visited */
  }
  set_irn_link(node, MARK);
700
  switch (get_irn_opcode(node)) {
701
702
703
704
  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
705
    eset_insert(set, get_Sel_method(node, i));
706
707
708
709
710
      }
    }
    break;
  }
  case iro_SymConst:
Beyhan's avatar
Beyhan committed
711
712
713
714
715
716
717
718
719
    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 */
    }
720
    break;
721

722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
  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;
  }
747
  switch (get_irn_opcode(node)) {
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
  /* 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);
764
      if (mode_is_reference(get_irn_mode(pred))) {
Michael Beck's avatar
Michael Beck committed
765
        free_mark(pred, set);
766
767
768
769
770
771
772
      }
    }
    break;
  /* other nodes: Alle anderen Knoten nehmen wir als Verrter an, bis
   * jemand das Gegenteil implementiert. */
  default:
    set_irn_link(node, MARK);
773
    for (i = get_irn_arity(node) - 1; i >= 0; --i) {
774
      ir_node * pred = get_irn_n(node, i);
775
      if (mode_is_reference(get_irn_mode(pred))) {
Michael Beck's avatar
Michael Beck committed
776
        free_mark(pred, set);
777
778
779
780
781
782
783
784
785
786
787
788
789
      }
    }
    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
790
static entity ** get_free_methods(void)
791
{
792
793
794
795
  eset * set = eset_create();
  int i;
  entity ** arr = NEW_ARR_F(entity *, 0);
  entity * ent;
Götz Lindenmaier's avatar
Götz Lindenmaier committed
796

Götz Lindenmaier's avatar
Götz Lindenmaier committed
797
798
  for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
    ir_graph * irg = get_irp_irg(i);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
799
800
801
802
    entity * ent = get_irg_entity(irg);
    /* insert "external visible" methods. */
    if (get_entity_visibility(ent) != visibility_local) {
      eset_insert(set, ent);
803
    }
Götz Lindenmaier's avatar
Götz Lindenmaier committed
804
805
806
    /* 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);
807
808
809
  }

  /* insert sticky methods, too */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
810
811
  for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
    ir_graph * irg = get_irp_irg(i);
812
    entity * ent = get_irg_entity(irg);
813
    /* insert "external visible" methods. */
814
    if (get_entity_stickyness (ent) == stickyness_sticky) {
815
816
817
      eset_insert(set, ent);
    }
  }
818

Götz Lindenmaier's avatar
Götz Lindenmaier committed
819
  /* Hauptprogramm ist auch dann frei, wenn es nicht "external
820
   * visible" ist. */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
821
  if (get_irp_main_irg()) {
822
    eset_insert(set, get_irg_entity(get_irp_main_irg()));
Boris Boesler's avatar
Boris Boesler committed
823
  }
Götz Lindenmaier's avatar
Götz Lindenmaier committed
824
  /* Wandle Menge in Feld um.  Effizienter. */
825
826
827
828
829
830
831
832
  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
833
void cgana(int *length, entity ***free_methods) {
834
  entity ** free_meths, **p;
835
836

  sel_methods_init();
Götz Lindenmaier's avatar
Götz Lindenmaier committed
837
  free_meths = get_free_methods();
838
839
840
841
842
  callee_ana();
  sel_methods_dispose();

  /* Convert the flexible array to an array that can be handled
     by standard C. */
Michael Beck's avatar
Michael Beck committed
843
  p = (entity **)xmalloc(sizeof(*p) * ARR_LEN(free_meths));
844
845
846
847
848
  memcpy(p, free_meths, ARR_LEN(free_meths) * sizeof(*p));

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

849
850
  DEL_ARR_F(free_meths);
}
851

Götz Lindenmaier's avatar
Götz Lindenmaier committed
852
853
854
855
856
857
858
859
860
861
862
863
864
865


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


866
/* Optimize the address expressions passed to call nodes.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
867
868
869
870
871
872
873
874
875
876
877
878
879
 *
 * 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.
 */
880
881
882
883
void opt_call_addrs(void) {
  sel_methods_init();
  sel_methods_dispose();
}