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

156
  if (get_entity_peculiarity(method) == peculiarity_inherited) {
157
    entity *impl_ent = get_inherited_methods_implementation(method);
158
    if (get_entity_visibility(impl_ent) == visibility_external_allocated) {
159
160
161
162
163
      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
164
165
        eset_insert(set, impl_ent);
        ++(*size);
166
167
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
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
#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
     behaviour: all unknown irgs are represented by the one and only
     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.
     This would be better for an analyses: it could rule out more
     cases. */
  entity *impl = method;
  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
211
  /*- recursive descent -*/
212
  for (i = get_entity_n_overwrittenby(method) - 1; i >= 0; --i)
213
    collect_impls(get_entity_overwrittenby(method, i), set, size, open);
214
215
}

216

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

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

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

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

270
  /* replace SymConst(name)-operations by SymConst(ent) */
271
  if (get_irn_op(node) == op_SymConst) {
Beyhan's avatar
Beyhan committed
272
273
    if (get_SymConst_kind(node) == symconst_addr_name) {
      pmap_entry * entry = pmap_find(ldname_map, (void *) get_SymConst_name(node));
274
      if (entry != NULL) { /* Method is declared in the compiled code */
275
276
277
278
	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
279
280
281

	  DBG_OPT_CSTEVAL(node, new_node);

282
283
284
285
	  assert(get_entity_irg(ent));
	  DDMN(new_node);
	  exchange(node, new_node);
	}
286
287
      }
    }
288
289
290
  }
  else if (get_irn_op(node) == op_Sel &&
	   is_method_type(get_entity_type(get_Sel_entity(node)))) {
291
    entity * ent = get_Sel_entity(node);
292
293

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

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

Götz Lindenmaier's avatar
Götz Lindenmaier committed
303
304
      /* 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
305
306
307
308
      new_node = copy_const_value(get_atomic_ent_value(called_ent));

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

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

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


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

374
375
  assert(entities == NULL);
  entities = eset_create();
Götz Lindenmaier's avatar
Götz Lindenmaier committed
376
377
378
379
  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
380
     * aufgerufen werden. */
381
    if (get_entity_visibility(ent) != visibility_local) {
382
383
384
      pmap_insert(ldname_map, (void *) get_entity_ld_ident(ent), ent);
    }
  }
385
  all_irg_walk(sel_methods_walker, NULL, ldname_map);
386
387
388
  pmap_destroy(ldname_map);
}

389
/*****************************************************************************/
390

391
/** Frees the allocated entity map */
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
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;
}


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

416
  assert(sel && get_irn_op(sel) == op_Sel);
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
  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;
  }
}

432
433
434
/**
 * Returns the number of possible called methods at a Sel node.
 */
435
436
437
438
static int get_Sel_n_methods(ir_node * sel) {
  return ARR_LEN(get_Sel_arr(sel));
}

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

464
  switch (get_irn_opcode(node)) {
465
466
467
468
469
470
  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) {
471
      if (get_irn_op(pred) == op_Tuple) {
472
        callee_ana_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, methods);
473
      } else {
474
        eset_insert(methods, MARK); /* free method -> unknown */
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
      }
    }
    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
500
  assert(mode_is_reference(get_irn_mode(node)) || is_Bad(node));
501
502
503
504
505
506
507
  /* rekursion verhindern */
  if (get_irn_link(node) == MARK) {
    /* already visited */
    return;
  }
  set_irn_link(node, MARK);

508
  switch (get_irn_opcode(node)) {
509
  case iro_SymConst:
Beyhan's avatar
Beyhan committed
510
511
512
    if (get_SymConst_kind(node) == symconst_addr_ent) {
      entity * ent = get_SymConst_entity(node);
      assert(ent && is_method_type(get_entity_type(ent)));
513
      eset_insert(methods, ent);
Beyhan's avatar
Beyhan committed
514
515
516
517
518
    } else {
      assert(get_SymConst_kind(node) == symconst_addr_name);
      /* externe Methode (wegen fix_symconst!) */
      eset_insert(methods, MARK); /* free method -> unknown */
    }
519
520
521
522
523
524
    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
525
        eset_insert(methods, ent);
526
      } else {
Florian Liekweg's avatar
Florian Liekweg committed
527
        eset_insert(methods, MARK);
528
529
530
531
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
      }
    }
    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) {
567
  if (get_irn_op(call) == op_Call) {
568
569
570
    eset * methods = eset_create();
    entity * ent;
    entity ** arr = NEW_ARR_F(entity *, 0);
571
572
    assert(get_irn_op(get_Call_ptr(call)) != op_Id);
    callee_ana_node(get_Call_ptr(call), methods);
573
    if (eset_contains(methods, MARK)) { /* unknown method */
574
      ARR_APP1(entity *, arr, unknown_entity);
575
576
577
    }
    for (ent = eset_first(methods); ent; ent = eset_next(methods)) {
      if (ent != MARK) {
578
	ARR_APP1(entity *, arr, ent);
579
580
      }
    }
581
582
583
#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()) {
584
585
586
587
588
      /* 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
589
      ir_node *mem = get_Call_mem(call);
590
      turn_into_tuple (call, 5 /* pn_Call_max */);
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
591
592
593
594
      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() ?? */
595
      set_Tuple_pred(call, pn_Call_M_except        , new_Bad());
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
596

597
598
599
    } else
#endif
    {
600
601
602
603
604
605
606
      /* 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;
      }

607
608
609
610
611
612
613
614
      set_Call_callee_arr(call, ARR_LEN(arr), arr);
    }
    DEL_ARR_F(arr);
    eset_destroy(methods);
  }
}


615
616
617
618
619
620
621
622
623
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);
}


624
625
626
627
628
629
630
/* 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
631
632
633
  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);
634
  }
Götz Lindenmaier's avatar
Götz Lindenmaier committed
635
  set_irp_callee_info_state(irg_callee_info_consistent);
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
}



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

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

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

Götz Lindenmaier's avatar
Götz Lindenmaier committed
793
794
  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
795
796
797
798
    entity * ent = get_irg_entity(irg);
    /* insert "external visible" methods. */
    if (get_entity_visibility(ent) != visibility_local) {
      eset_insert(set, ent);
799
    }
Götz Lindenmaier's avatar
Götz Lindenmaier committed
800
801
802
    /* 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);
803
804
805
  }

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

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

  sel_methods_init();
Götz Lindenmaier's avatar
Götz Lindenmaier committed
833
  free_meths = get_free_methods();
834
835
836
837
838
  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
839
  p = (entity **)xmalloc(sizeof(*p) * ARR_LEN(free_meths));
840
841
842
843
844
  memcpy(p, free_meths, ARR_LEN(free_meths) * sizeof(*p));

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

845
846
  DEL_ARR_F(free_meths);
}
847

Götz Lindenmaier's avatar
Götz Lindenmaier committed
848
849
850
851
852
853
854
855
856
857
858
859
860
861


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


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