cgana.c 26.4 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"

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

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
  }
  else if (get_irn_op(node) == op_Sel &&
294
	   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
  ent = get_Sel_entity(sel);
422
  assert(is_Method_type(get_entity_type(ent))); /* what else? */
423
424
425
426
427
428
429
430
431
432
433
434
435
  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
    if (get_SymConst_kind(node) == symconst_addr_ent) {
      entity * ent = get_SymConst_entity(node);
516
      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
      }
    }
    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;

Michael Beck's avatar
Michael Beck committed
546
547
548
549
550
  case iro_Mux:
    callee_ana_node(get_Mux_false(node), methods);
    callee_ana_node(get_Mux_true(node), methods);
    break;

551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
  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) {
576
  if (get_irn_op(call) == op_Call) {
577
578
579
    eset * methods = eset_create();
    entity * ent;
    entity ** arr = NEW_ARR_F(entity *, 0);
580
581
    assert(get_irn_op(get_Call_ptr(call)) != op_Id);
    callee_ana_node(get_Call_ptr(call), methods);
582
    if (eset_contains(methods, MARK)) { /* unknown method */
583
      ARR_APP1(entity *, arr, unknown_entity);
584
585
586
    }
    for (ent = eset_first(methods); ent; ent = eset_next(methods)) {
      if (ent != MARK) {
587
	ARR_APP1(entity *, arr, ent);
588
589
      }
    }
590
591
592
#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()) {
593
594
595
596
597
      /* 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
598
      ir_node *mem = get_Call_mem(call);
599
      turn_into_tuple (call, 5 /* pn_Call_max */);
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
600
601
602
603
      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() ?? */
604
      set_Tuple_pred(call, pn_Call_M_except        , new_Bad());
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
605

606
607
608
    } else
#endif
    {
609
610
611
612
613
614
615
      /* 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;
      }

616
617
618
619
620
621
622
623
      set_Call_callee_arr(call, ARR_LEN(arr), arr);
    }
    DEL_ARR_F(arr);
    eset_destroy(methods);
  }
}


624
625
626
627
628
629
630
631
632
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);
}


633
634
635
636
637
638
639
/* 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
640
641
642
  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);
643
  }
Götz Lindenmaier's avatar
Götz Lindenmaier committed
644
  set_irp_callee_info_state(irg_callee_info_consistent);
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
}



/* --- 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);
661
  switch (get_irn_opcode(node)) {
662
663
664
665
666
  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);
667
    if (get_irn_link(pred) != MARK && get_irn_op(pred) == op_Tuple) {
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
695
696
697
698
699
      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;
700

701
702
703
704
  if (get_irn_link(node) == MARK) {
    return; /* already visited */
  }
  set_irn_link(node, MARK);
705
  switch (get_irn_opcode(node)) {
706
707
  case iro_Sel: {
    entity * ent = get_Sel_entity(node);
708
    if (is_Method_type(get_entity_type(ent))) {
709
      for (i = get_Sel_n_methods(node) - 1; i >= 0; --i) {
710
        eset_insert(set, get_Sel_method(node, i));
711
712
713
714
715
      }
    }
    break;
  }
  case iro_SymConst:
Beyhan's avatar
Beyhan committed
716
717
    if (get_SymConst_kind(node) == symconst_addr_ent) {
      entity * ent = get_SymConst_entity(node);
718
      if (is_Method_type(get_entity_type(ent))) {
Beyhan's avatar
Beyhan committed
719
720
721
722
723
724
        eset_insert(set, ent);
      }
    } else {
      assert(get_SymConst_kind(node) == symconst_addr_name);
      /* nothing: SymConst points to extern method */
    }
725
    break;
726

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

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);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
804
805
806
807
    entity * ent = get_irg_entity(irg);
    /* insert "external visible" methods. */
    if (get_entity_visibility(ent) != visibility_local) {
      eset_insert(set, ent);
808
    }
Götz Lindenmaier's avatar
Götz Lindenmaier committed
809
810
811
    /* 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);
812
813
814
  }

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

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

  sel_methods_init();
Götz Lindenmaier's avatar
Götz Lindenmaier committed
842
  free_meths = get_free_methods();
843
844
845
846
847
  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
848
  p = xmalloc(sizeof(*p) * ARR_LEN(free_meths));
849
850
851
852
853
  memcpy(p, free_meths, ARR_LEN(free_meths) * sizeof(*p));

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

854
855
  DEL_ARR_F(free_meths);
}
856

Götz Lindenmaier's avatar
Götz Lindenmaier committed
857
858
859
860
861
862
863
864
865
866
867
868
869
870


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


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