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

/**
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
88
89
90
91
92
93
  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
94
95
  entity *impl_meth = NULL;
  ir_node *addr = get_atomic_ent_value(inh_meth);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
96

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

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

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

120

121
122
123
124
125
126
127
128
129
130
131
132
133
134
/** 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) {
135
  int i;
136
#if 0
137
  if (get_entity_peculiarity(method) == peculiarity_existent) {
Boris Boesler's avatar
Boris Boesler committed
138
139
    if ((get_entity_visibility(method) == visibility_external_allocated)
	&& (NULL == get_entity_irg(method))) {
140
141
      /* We could also add these entities to the callees, but right now we
	 subsume them by unknown_entity. */
142
143
144
      *open = true;
    } else {
      assert(get_entity_irg(method) != NULL);
145
      if (!eset_contains(set, method)) {
Florian Liekweg's avatar
Florian Liekweg committed
146
147
        eset_insert(set, method);
        ++(*size);
148
      }
149
150
    }
  }
151

152
  if (get_entity_peculiarity(method) == peculiarity_inherited) {
153
    entity *impl_ent = get_inherited_methods_implementation(method);
154
    if (get_entity_visibility(impl_ent) == visibility_external_allocated) {
155
156
157
158
159
      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
160
161
        eset_insert(set, impl_ent);
        ++(*size);
162
163
164
      }
    }
  }
165
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
#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
207
  /*- recursive descent -*/
208
  for (i = get_entity_n_overwrittenby(method) - 1; i >= 0; --i)
209
    collect_impls(get_entity_overwrittenby(method, i), set, size, open);
210
211
}

212

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

229
  /* Collect all method entities that can be called here */
230
231
  collect_impls(method, set, &size, &open);

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

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

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

	  DBG_OPT_CSTEVAL(node, new_node);

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

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

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

Götz Lindenmaier's avatar
Götz Lindenmaier committed
299
300
      /* 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
301
302
303
304
      new_node = copy_const_value(get_atomic_ent_value(called_ent));

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

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

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


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

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

385
/*****************************************************************************/
386

387
/** Frees the allocated entity map */
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
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;
}


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

412
  assert(sel && get_irn_op(sel) == op_Sel);
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
  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;
  }
}

428
429
430
/**
 * Returns the number of possible called methods at a Sel node.
 */
431
432
433
434
static int get_Sel_n_methods(ir_node * sel) {
  return ARR_LEN(get_Sel_arr(sel));
}

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

460
  switch (get_irn_opcode(node)) {
461
462
463
464
465
466
  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) {
467
      if (get_irn_op(pred) == op_Tuple) {
468
        callee_ana_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, methods);
469
      } else {
470
        eset_insert(methods, MARK); /* free method -> unknown */
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
      }
    }
    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
496
  assert(mode_is_reference(get_irn_mode(node)) || is_Bad(node));
497
498
499
500
501
502
503
  /* rekursion verhindern */
  if (get_irn_link(node) == MARK) {
    /* already visited */
    return;
  }
  set_irn_link(node, MARK);

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

593
594
595
    } else
#endif
    {
596
597
598
599
600
601
602
      /* 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;
      }

603
604
605
606
607
608
609
610
      set_Call_callee_arr(call, ARR_LEN(arr), arr);
    }
    DEL_ARR_F(arr);
    eset_destroy(methods);
  }
}


611
612
613
614
615
616
617
618
619
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);
}


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



/* --- 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);
648
  switch (get_irn_opcode(node)) {
649
650
651
652
653
  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);
654
    if (get_irn_link(pred) != MARK && get_irn_op(pred) == op_Tuple) {
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
681
682
683
684
685
686
      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;
687

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

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

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

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

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

  sel_methods_init();
Götz Lindenmaier's avatar
Götz Lindenmaier committed
829
  free_meths = get_free_methods();
830
831
832
833
834
  callee_ana();
  sel_methods_dispose();

  /* Convert the flexible array to an array that can be handled
     by standard C. */
835
836
837
838
839
840
  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;

841
842
  DEL_ARR_F(free_meths);
}
843

Götz Lindenmaier's avatar
Götz Lindenmaier committed
844
845
846
847
848
849
850
851
852
853
854
855
856
857


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


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