cgana.c 25.3 KB
Newer Older
Götz Lindenmaier's avatar
Götz Lindenmaier committed
1
2
3
4
5
6
7
8
9
10
11
12
/*
 * 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.
 */

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
13
14
15
/** @file cgana.c
 *
 * Interprocedural analysis to estimate the calling relation.
16
 *
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
17
18
19
20
 * This analysis computes all entities representing methods that
 * can be called at a Call node.  Further it computes a set of
 * methods that are 'free', i.e., their adress is handled by
 * the program directly, or they are visible external.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
21
 */
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
22

23
#ifdef HAVE_CONFIG_H
Michael Beck's avatar
Michael Beck committed
24
25
26
27
28
# include "config.h"
#endif

#ifdef HAVE_STRING_H
# include <string.h>
29
#endif
30
31

#include "cgana.h"
Florian Liekweg's avatar
Florian Liekweg committed
32
#include "rta.h"
33

Michael Beck's avatar
Michael Beck committed
34
#include "xmalloc.h"
Götz Lindenmaier's avatar
Götz Lindenmaier committed
35
36
37
#include "irnode_t.h"
#include "irmode_t.h"
#include "irprog_t.h"
38
39
40
#include "irgwalk.h"
#include "ircons.h"
#include "irgmod.h"
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
41
#include "iropt.h"
42

Götz Lindenmaier's avatar
Götz Lindenmaier committed
43
#include "irflag_t.h"
Götz Lindenmaier's avatar
Götz Lindenmaier committed
44
#include "dbginfo_t.h"
Michael Beck's avatar
Michael Beck committed
45
#include "iropt_dbg.h"
Götz Lindenmaier's avatar
Götz Lindenmaier committed
46

Götz Lindenmaier's avatar
Götz Lindenmaier committed
47
48
49
#include "eset.h"
#include "pmap.h"
#include "array.h"
Götz Lindenmaier's avatar
Götz Lindenmaier committed
50

51
52
#include "irdump.h"

53
#include "irhooks.h"
Michael Beck's avatar
Michael Beck committed
54

55
56


Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
57
58
59
/* Eindeutige Adresse zur Markierung von besuchten Knoten und zur
 * Darstellung der unbekannten Methode. */
static void *MARK = &MARK;
60

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
61
static eset *entities = NULL;
62

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
63
64
65
/*--------------------------------------------------------------------------*/
/* The analysis                                                             */
/*--------------------------------------------------------------------------*/
66
67


Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
68
69
70
71
/*--------------------------------------------------------------------------*/
/* Initialize datastructures, remove unwanted constructs, optimize          */
/* call target computations.                                                */
/*--------------------------------------------------------------------------*/
72

73
/** Returns the entity that contains the implementation of the inherited
Götz Lindenmaier's avatar
Götz Lindenmaier committed
74
 *  entity if available, else returns the entity passed. */
75
static entity *get_inherited_methods_implementation(entity *inh_meth) {
76
77
  assert(get_atomic_ent_value(inh_meth) && "constant entity without value");
  assert((get_irn_op(get_atomic_ent_value(inh_meth)) == op_SymConst) &&
78
79
         (get_SymConst_kind(get_atomic_ent_value(inh_meth)) == symconst_addr_ent) &&
         "Complex constant values not supported -- address of method should be straight constant!");
80
81

  return get_SymConst_entity(get_atomic_ent_value(inh_meth));
82
83
}

84
85
86
87
88
89
90
91
92
93
94
95
96
97
/** 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) {
98
  int i;
Michael Beck's avatar
Michael Beck committed
99
100
  entity *impl;

101
102
103
  /* Only the assertions: */
  if (get_entity_peculiarity(method) == peculiarity_existent) {
    if ((get_entity_visibility(method) == visibility_external_allocated)
104
         && (NULL == get_entity_irg(method))) {
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
    } 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
122
     behavior: all unknown irgs are represented by the one and only
123
124
125
     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
126
     This would be better for an analysis: it could rule out more
127
     cases. */
Michael Beck's avatar
Michael Beck committed
128
  impl = method;
129
130
131
132
133
134
135
136
137
138
139
140
141
  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
142
  /*- recursive descent -*/
143
  for (i = get_entity_n_overwrittenby(method) - 1; i >= 0; --i)
144
    collect_impls(get_entity_overwrittenby(method, i), set, size, open);
145
146
}

147
148
149
150
151
152
153
154
155
156
/** 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
 */
157
158
159
160
161
static entity ** get_impl_methods(entity * method) {
  eset * set = eset_create();
  int size = 0;
  entity ** arr;
  bool open = false;
162

163
  /* Collect all method entities that can be called here */
164
165
  collect_impls(method, set, &size, &open);

166
  /* Vorgaenger einfuegen. */
167
168
169
170
171
172
  if (size == 0 && !open) {
    /* keine implementierte berschriebene Methode */
    arr = NULL;
  } else if (open) {
    entity * ent;
    arr = NEW_ARR_F(entity *, size + 1);
173
174
175
    arr[0] = NULL;  /* Represents open method */
    for (ent = eset_first(set); size > 0; ent = eset_next(set), --size)
      arr[size] = ent;
176
177
178
  } else {
    entity * ent;
    arr = NEW_ARR_F(entity *, size);
179
180
    for (size -= 1, ent = eset_first(set); size >= 0; ent = eset_next(set), --size)
      arr[size] = ent;
181
182
183
184
185
  }
  eset_destroy(set);
  return arr;
}

Michael Beck's avatar
Michael Beck committed
186
/** Analyze address computations.
187
 *
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
188
189
190
191
192
 *  Compute for all Sel nodes the set of methods that can be selected.
 *
 *  Further do some optimizations:
 *  - Call standard optimizations for Sel nodes: this removes polymorphic
 *    calls.
193
 *  - If the node is a SymConst(name) replace it by SymConst(ent) if possible.
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
194
 *    For this we precomputed a map name->entity.
195
 *  - If the node is a Sel:
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
196
197
 *     If we found only a single method that can be called, replace the Sel
 *     by a SymConst.  This is more powerful than the analysis in opt_polymorphy,
198
 *     as here we walk the type graph.  In opt_polymorphy we only apply a local
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
199
 *     pattern.
200
201
 *
 *  @param node The node to analyze
202
 *  @param env  A map that maps names of entities to the entities.
203
 */
204
205
static void sel_methods_walker(ir_node * node, void *env) {
  pmap *ldname_map = env;
206

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
207
208
209
210
211
  if (get_irn_op(node) == op_Sel) {
    ir_node *new_node = optimize_in_place(node);
    if (node != new_node) exchange(node, new_node);
  }

212
  /* replace SymConst(name)-operations by SymConst(ent) */
213
  if (get_irn_op(node) == op_SymConst) {
Beyhan's avatar
Beyhan committed
214
215
    if (get_SymConst_kind(node) == symconst_addr_name) {
      pmap_entry * entry = pmap_find(ldname_map, (void *) get_SymConst_name(node));
216
      if (entry != NULL) { /* Method is declared in the compiled code */
217
218
        assert(0 && "There should not be a SymConst[addr_name] addressing a method with an implementation"
                    "in this compilation unit.  Use a SymConst[addr_ent].");
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
219
#if 0
220
221
222
223
224
225
        /* the following code would handle that case, but it should not
         * happen anymore, so we add the above assertion
         */
        entity * ent = entry->value;
        if (get_opt_normalize() &&
            (get_entity_visibility(ent) != visibility_external_allocated)) { /* Meth. is defined */
Michael Beck's avatar
Michael Beck committed
226
227
          ir_node *new_node;

228
229
          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
230

231
          DBG_OPT_CSTEVAL(node, new_node);
Michael Beck's avatar
Michael Beck committed
232

233
234
235
236
          assert(get_entity_irg(ent));
          DDMN(new_node);
          exchange(node, new_node);
        }
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
237
#endif
238
239
      }
    }
240
241
  }
  else if (get_irn_op(node) == op_Sel &&
242
           is_Method_type(get_entity_type(get_Sel_entity(node)))) {
243
    entity * ent = get_Sel_entity(node);
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
244
245
246
247
248
249
250
251
    assert(get_entity_peculiarity(ent) != peculiarity_inherited);

    if (!eset_contains(entities, ent)) {
      /* 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);
252
    }
253

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
254
255
256
257
258
259
260
    /* -- As an add on we get an optimization that removes polymorphic calls.
       This optimization is more powerful than that in transform_node_Sel.  -- */
    if (get_entity_link(ent) == NULL) {
      /* 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
261
         fuer die es keine Implementierung gibt. */
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
262
      if (get_entity_peculiarity(ent) == peculiarity_description) {
263
        /* This is possible:  We call a method in a dead part of the program. */
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
264
      } else {
265
266
267
        DDMN(node);
        assert(0);  /* Why should this happen ??? */
        //exchange(node, new_Bad());
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
268
269
270
271
      }
    } else {
      entity ** arr = get_entity_link(ent);
      if (get_opt_optimize() && get_opt_dyn_meth_dispatch() &&
272
273
274
275
276
277
278
279
280
281
282
283
          (ARR_LEN(arr) == 1 && arr[0] != NULL)) {
        ir_node *new_node;
        /* Die Sel-Operation kann immer nur _einen_ Wert auf eine
         * interne Methode zurckgeben. Wir knnen daher die
         * Sel-Operation durch eine Const- bzw. SymConst-Operation
         * ersetzen. */
        set_irg_current_block(current_ir_graph, get_nodes_block(node));
        assert(get_entity_peculiarity(get_SymConst_entity(get_atomic_ent_value(arr[0]))) ==
               peculiarity_existent);
        new_node = copy_const_value(get_atomic_ent_value(arr[0]));
        DBG_OPT_POLY(node, new_node);
        exchange (node, new_node);
284
285
286
287
288
      }
    }
  }
}

289
/** Datenstruktur initialisieren. Zustzlich werden alle
290
291
 *  SymConst(name)-Operationen, die auf interne Methoden verweisen, durch
 *  SymConst(entity)-Operationen ersetzt. */
292
293
static void sel_methods_init(void) {
  int i;
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
294
  pmap * ldname_map = pmap_create();   /* Map entity names to entities: to replace
295
                                          SymConst(name) by SymConst(ent). */
296
297
  assert(entities == NULL);
  entities = eset_create();
Götz Lindenmaier's avatar
Götz Lindenmaier committed
298
  for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
299
300
    entity * ent = get_irg_entity(get_irp_irg(i));
    /* Nur extern sichtbare Methoden knnen berhaupt mit SymConst_ptr_name
301
     * aufgerufen werden. */
302
    if (get_entity_visibility(ent) != visibility_local) {
303
304
305
      pmap_insert(ldname_map, (void *) get_entity_ld_ident(ent), ent);
    }
  }
306
  all_irg_walk(sel_methods_walker, NULL, ldname_map);
307
308
309
  pmap_destroy(ldname_map);
}

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
310
311
312
313
314
315
/*--------------------------------------------------------------------------*/
/* Find free methods.
 *
 * We expect that each entity has an array with all implementations in its
 * link field.                                                              */
/*--------------------------------------------------------------------------*/
316

317
318
319
320
/**
 * Returns an array of all methods that could be called at a Sel node.
 * This array contains every entry only once.
 */
321
322
323
324
static entity ** get_Sel_arr(ir_node * sel) {
  static entity ** NULL_ARRAY = NULL;
  entity * ent;
  entity ** arr;
325

326
  assert(sel && get_irn_op(sel) == op_Sel);
327
  ent = get_Sel_entity(sel);
328
  assert(is_Method_type(get_entity_type(ent))); /* what else? */
329
330
331
332
333
334
335
336
337
338
339
340
341
  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;
  }
}

342
343
344
/**
 * Returns the number of possible called methods at a Sel node.
 */
345
346
347
348
static int get_Sel_n_methods(ir_node * sel) {
  return ARR_LEN(get_Sel_arr(sel));
}

349
350
351
/**
 * Returns the ith possible called method entity at a Sel node.
 */
352
353
354
355
356
357
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];
}

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
358
static void free_mark(ir_node * node, eset * set);
359

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
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);
  switch (get_irn_opcode(node)) {
  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);
    if (get_irn_link(pred) != MARK && get_irn_op(pred) == op_Tuple) {
      free_mark_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, set);
    } else {
      /* nothing: da in "free_ana_walker" behandelt. */
    }
    break;
  }
380

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
381
382
383
  case iro_Tuple:
    free_mark(get_Tuple_pred(node, n), set);
    break;
384

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
  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;

  if (get_irn_link(node) == MARK) {
    return; /* already visited */
  }
  set_irn_link(node, MARK);
  switch (get_irn_opcode(node)) {
  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) {
        eset_insert(set, get_Sel_method(node, i));
      }
    }
    break;
  }
  case iro_SymConst:
    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 */
    }
    break;

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


Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
static void free_ana_walker(ir_node * node, eset * set) {
  int i;
  if (get_irn_link(node) == MARK) {
    /* bereits in einem Zyklus besucht. */
    return;
  }
  switch (get_irn_opcode(node)) {
  /* 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);
      if (mode_is_reference(get_irn_mode(pred))) {
        free_mark(pred, set);
      }
    }
    break;
  /* other nodes: Alle anderen Knoten nehmen wir als Verrter an, bis
   * jemand das Gegenteil implementiert. */
  default:
    set_irn_link(node, MARK);
    for (i = get_irn_arity(node) - 1; i >= 0; --i) {
      ir_node * pred = get_irn_n(node, i);
      if (mode_is_reference(get_irn_mode(pred))) {
        free_mark(pred, set);
      }
    }
    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(name)-Operationen mssen in passende SymConst(ent)-Operationen
 * umgewandelt worden sein, d.h. SymConst-Operationen verweisen immer
 * auf eine echt externe Methode. */
static entity ** get_free_methods(void)
{
  eset * set = eset_create();
  int i;
  entity ** arr = NEW_ARR_F(entity *, 0);
  entity * ent;

  for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
    ir_graph * irg = get_irp_irg(i);
    entity * ent = get_irg_entity(irg);
    /* insert "external visible" methods. */
    if (get_entity_visibility(ent) != visibility_local) {
      eset_insert(set, ent);
    }
    /* 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);
  }

  /* insert sticky methods, too */
  for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
    entity * ent = get_irg_entity(get_irp_irg(i));
    /* insert "external visible" methods. */
    if (get_entity_stickyness (ent) == stickyness_sticky) {
      eset_insert(set, ent);
    }
  }

  /* Hauptprogramm ist auch dann frei, wenn es nicht "external
   * visible" ist. */
  if (get_irp_main_irg()) {
    eset_insert(set, get_irg_entity(get_irp_main_irg()));
  }
  /* Wandle Menge in Feld um.  Effizienter. */
  for (ent = eset_first(set); ent; ent = eset_next(set)) {
    ARR_APP1(entity *, arr, ent);
  }
  eset_destroy(set);

  return arr;
}

/*--------------------------------------------------------------------------*/
/* Callee analysis.                                                         */
/*--------------------------------------------------------------------------*/

static void callee_ana_node(ir_node * node, eset * methods);
547
548
549
550
551
552
553
554
555

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

556
  switch (get_irn_opcode(node)) {
557
558
559
560
561
562
  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) {
563
      if (get_irn_op(pred) == op_Tuple) {
564
        callee_ana_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, methods);
565
      } else {
566
        eset_insert(methods, MARK); /* free method -> unknown */
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
      }
    }
    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
592
  assert(mode_is_reference(get_irn_mode(node)) || is_Bad(node));
593
594
595
596
597
598
599
  /* rekursion verhindern */
  if (get_irn_link(node) == MARK) {
    /* already visited */
    return;
  }
  set_irn_link(node, MARK);

600
  switch (get_irn_opcode(node)) {
601
  case iro_SymConst:
Beyhan's avatar
Beyhan committed
602
603
    if (get_SymConst_kind(node) == symconst_addr_ent) {
      entity * ent = get_SymConst_entity(node);
604
      assert(ent && is_Method_type(get_entity_type(ent)));
605
      eset_insert(methods, ent);
Beyhan's avatar
Beyhan committed
606
607
608
609
610
    } else {
      assert(get_SymConst_kind(node) == symconst_addr_name);
      /* externe Methode (wegen fix_symconst!) */
      eset_insert(methods, MARK); /* free method -> unknown */
    }
611
612
613
614
615
616
    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
617
        eset_insert(methods, ent);
618
      } else {
Florian Liekweg's avatar
Florian Liekweg committed
619
        eset_insert(methods, MARK);
620
621
622
623
624
625
626
627
628
629
630
631
632
633
      }
    }
    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
634
635
636
637
638
  case iro_Mux:
    callee_ana_node(get_Mux_false(node), methods);
    callee_ana_node(get_Mux_true(node), methods);
    break;

639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
  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) {
664
  if (get_irn_op(call) == op_Call) {
665
666
667
    eset * methods = eset_create();
    entity * ent;
    entity ** arr = NEW_ARR_F(entity *, 0);
668
669
    assert(get_irn_op(get_Call_ptr(call)) != op_Id);
    callee_ana_node(get_Call_ptr(call), methods);
670
    if (eset_contains(methods, MARK)) { /* unknown method */
671
      ARR_APP1(entity *, arr, unknown_entity);
672
673
674
    }
    for (ent = eset_first(methods); ent; ent = eset_next(methods)) {
      if (ent != MARK) {
675
        ARR_APP1(entity *, arr, ent);
676
677
      }
    }
678
#if 0  /* This generates Bad nodes when we don't want it.
679
          Call it with a check for valid cgana information in local_optimize. */
680
    if (ARR_LEN(arr) == 0 && get_opt_optimize() && get_opt_dyn_meth_dispatch()) {
681
682
683
684
685
      /* 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
686
      ir_node *mem = get_Call_mem(call);
687
      turn_into_tuple (call, 5 /* pn_Call_max */);
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
688
689
690
691
      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() ?? */
692
      set_Tuple_pred(call, pn_Call_M_except        , new_Bad());
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
693

694
695
696
    } else
#endif
    {
697
698
699
      /* remove, what we repaired. */
      int i;
      for (i = 0; i < ARR_LEN(arr); ++i) {
700
        assert(arr[i]);
701
702
      }

703
704
705
706
707
708
709
710
      set_Call_callee_arr(call, ARR_LEN(arr), arr);
    }
    DEL_ARR_F(arr);
    eset_destroy(methods);
  }
}


711
712
713
714
715
716
717
718
719
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);
}


720
721
722
723
724
725
726
/* 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
727
728
729
  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);
730
  }
Götz Lindenmaier's avatar
Götz Lindenmaier committed
731
  set_irp_callee_info_state(irg_callee_info_consistent);
732
733
}

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
734
735
736
/*--------------------------------------------------------------------------*/
/* Cleanup after analyses.                                                  */
/*--------------------------------------------------------------------------*/
737

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
738
739
740
741
742
743
744
745
/** Frees intermediate data structures. */
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);
746
    }
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
747
    set_entity_link(ent, NULL);
748
  }
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
749
750
  eset_destroy(entities);
  entities = NULL;
751
752
}

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
753
754
755
/*--------------------------------------------------------------------------*/
/* Freeing the callee arrays.                                               */
/*--------------------------------------------------------------------------*/
756

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
757
758
759
static void destruct_walker(ir_node * node, void * env) {
  if (get_irn_op(node) == op_Call) {
    remove_Call_callee_arr(node);
760
761
762
  }
}

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
763
764
765
/*--------------------------------------------------------------------------*/
/* Main drivers.                                                            */
/*--------------------------------------------------------------------------*/
766

Götz Lindenmaier's avatar
Götz Lindenmaier committed
767
void cgana(int *length, entity ***free_methods) {
768
  entity ** free_meths, **p;
769
770

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

  /* Convert the flexible array to an array that can be handled
     by standard C. */
Michael Beck's avatar
Michael Beck committed
777
  p = xmalloc(sizeof(*p) * ARR_LEN(free_meths));
778
779
780
781
782
  memcpy(p, free_meths, ARR_LEN(free_meths) * sizeof(*p));

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

783
784
  DEL_ARR_F(free_meths);
}
785

Götz Lindenmaier's avatar
Götz Lindenmaier committed
786
787
788
789
790
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);
}

791
/* Optimize the address expressions passed to call nodes.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
792
793
794
795
796
797
798
 *
 * 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.
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
799
 * - Sel nodes, for which no method exists at all are replaced by Bad
Götz Lindenmaier's avatar
Götz Lindenmaier committed
800
801
802
803
804
 *   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.
 */
805
806
807
808
void opt_call_addrs(void) {
  sel_methods_init();
  sel_methods_dispose();
}