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
/*
 * 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


Michael Beck's avatar
Michael Beck committed
57
/* unambiguous address used as a mark. */
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
58
static void *MARK = &MARK;
59

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

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


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

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

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

83
/** Collect the entity representing the implementation of this
84
 *  method (not the same if inherited) and all entities for overwriting
85
86
87
88
89
90
91
92
93
94
95
 *  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
 */
96
static void collect_impls(ir_entity *method, eset *set, int *size, int *open) {
97
  int i;
98
  ir_entity *impl;
Michael Beck's avatar
Michael Beck committed
99

100
101
  /* Add the implementation to the set if it contains an irg, else
     remember that there are more methods called. */
Michael Beck's avatar
Michael Beck committed
102
  impl = method;
103
104
105
106
107
108
109
110
  if (get_entity_peculiarity(method) == peculiarity_inherited)
    impl = get_inherited_methods_implementation(method);

  if (get_entity_peculiarity(method) != peculiarity_description) {
    eset_insert(set, impl);
    ++(*size);
  }

Michael Beck's avatar
Michael Beck committed
111
  /*- recursive descent -*/
112
  for (i = get_entity_n_overwrittenby(method) - 1; i >= 0; --i)
113
    collect_impls(get_entity_overwrittenby(method, i), set, size, open);
114
115
}

116
117
118
119
120
121
122
123
124
125
/** 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
 */
126
static ir_entity ** get_impl_methods(ir_entity * method) {
127
128
  eset * set = eset_create();
  int size = 0;
129
  ir_entity ** arr;
130
  int open = 0;
131

132
  /* Collect all method entities that can be called here */
133
134
  collect_impls(method, set, &size, &open);

135
  /* Vorgaenger einfuegen. */
136
137
138
139
  if (size == 0 && !open) {
    /* keine implementierte berschriebene Methode */
    arr = NULL;
  } else if (open) {
140
141
    ir_entity * ent;
    arr = NEW_ARR_F(ir_entity *, size + 1);
142
143
144
    arr[0] = NULL;  /* Represents open method */
    for (ent = eset_first(set); size > 0; ent = eset_next(set), --size)
      arr[size] = ent;
145
  } else {
146
147
    ir_entity * ent;
    arr = NEW_ARR_F(ir_entity *, size);
148
149
    for (size -= 1, ent = eset_first(set); size >= 0; ent = eset_next(set), --size)
      arr[size] = ent;
150
151
152
153
154
  }
  eset_destroy(set);
  return arr;
}

Michael Beck's avatar
Michael Beck committed
155
/** Analyze address computations.
156
 *
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
157
 *  Compute for all Sel nodes the set of methods that can be selected.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
158
 *  For each entity we store the set of subentities in the link field.
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
159
160
161
162
 *
 *  Further do some optimizations:
 *  - Call standard optimizations for Sel nodes: this removes polymorphic
 *    calls.
163
 *  - If the node is a SymConst(name) replace it by SymConst(ent) if possible.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
164
165
 *    For this we precomputed a map name->entity.  Nowadays, we no more support
 *    this and assert.
166
 *  - If the node is a Sel:
Götz Lindenmaier's avatar
Götz Lindenmaier committed
167
168
169
170
 *    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,
 *    as here we walk the type graph.  In opt_polymorphy we only apply a local
 *    pattern.
171
172
 *
 *  @param node The node to analyze
173
 *  @param env  A map that maps names of entities to the entities.
174
 */
175
176
static void sel_methods_walker(ir_node * node, void *env) {
  pmap *ldname_map = env;
177
  ir_entity **arr;
178

Götz Lindenmaier's avatar
Götz Lindenmaier committed
179
  /* Call standard optimizations */
Michael Beck's avatar
Michael Beck committed
180
  if (is_Sel(node)) {
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
181
    ir_node *new_node = optimize_in_place(node);
182
183
    if (node != new_node)
      exchange(node, new_node);
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
184
185
  }

186
  /* replace SymConst(name)-operations by SymConst(ent) */
187
  if (get_irn_op(node) == op_SymConst) {
Beyhan's avatar
Beyhan committed
188
189
    if (get_SymConst_kind(node) == symconst_addr_name) {
      pmap_entry * entry = pmap_find(ldname_map, (void *) get_SymConst_name(node));
190
      if (entry != NULL) { /* Method is declared in the compiled code */
191
192
        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].");
193
194
      }
    }
195
196
  }
  else if (get_irn_op(node) == op_Sel &&
197
           is_Method_type(get_entity_type(get_Sel_entity(node)))) {
198
    ir_entity * ent = get_SymConst_entity(get_atomic_ent_value(get_Sel_entity(node)));
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
199
200
201
    assert(get_entity_peculiarity(ent) != peculiarity_inherited);

    if (!eset_contains(entities, ent)) {
202
203
204
      /* Entity not yet handled. Find all (internal or external)
       * implemented methods that overwrites this entity.
       * This set is stored in the entity link. */
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
205
206
      set_entity_link(ent, get_impl_methods(ent));
      eset_insert(entities, ent);
207
    }
208

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
209
    /* -- As an add on we get an optimization that removes polymorphic calls.
210
211
212
213
214
215
216
217
       This optimization is more powerful than that in transform_node_Sel().  -- */
    arr = get_entity_link(ent);
    if (arr == NULL) {
      /*
       * The Sel node never returns a pointer to a usable method.
       * We could not call it, but it may be description:
       * We call a method in a dead part of the program.
       */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
218
      assert (get_entity_peculiarity(ent) == peculiarity_description);
219
    }
220
    else if (get_opt_optimize() && get_opt_closed_world() && get_opt_dyn_meth_dispatch() &&
221
222
223
224
225
226
227
228
229
230
231
        (ARR_LEN(arr) == 1 && arr[0] != NULL)) {
      ir_node *new_node;

      /*
       * The Sel node returns only one possible method.
       * So we could replace the Sel node by a SymConst.
       * This method must exists.
       */
      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);
232
      new_node = copy_const_value(get_irn_dbg_info(node), get_atomic_ent_value(arr[0]));
233
234
      DBG_OPT_POLY(node, new_node);
      exchange(node, new_node);
235
236
237
238
    }
  }
}

Götz Lindenmaier's avatar
Götz Lindenmaier committed
239
240
241
/** Initialize auxiliary data structures.
 *
 *  Computes a set of entities that overwrite an entity and contain
242
 *  an implementation. The set is stored in the entity's link field.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
243
244
245
246
247
 *
 *  Further replaces Sel nodes where this set contains exactly one
 *  method by SymConst nodes.
 *  Finally asserts if there is a SymConst(name) if there could be a
 *  SymConst(ent). */
248
249
static void sel_methods_init(void) {
  int i;
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
250
  pmap * ldname_map = pmap_create();   /* Map entity names to entities: to replace
251
                                          SymConst(name) by SymConst(ent). */
252
253
  assert(entities == NULL);
  entities = eset_create();
Götz Lindenmaier's avatar
Götz Lindenmaier committed
254
  for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
255
    ir_entity * ent = get_irg_entity(get_irp_irg(i));
256
    /* only external visible methods are allowed to call by a SymConst_ptr_name */
257
    if (get_entity_visibility(ent) != visibility_local) {
258
259
260
      pmap_insert(ldname_map, (void *) get_entity_ld_ident(ent), ent);
    }
  }
Götz Lindenmaier's avatar
Götz Lindenmaier committed
261

262
  all_irg_walk(sel_methods_walker, NULL, ldname_map);
263
264
265
  pmap_destroy(ldname_map);
}

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
266
267
268
269
270
271
/*--------------------------------------------------------------------------*/
/* Find free methods.
 *
 * We expect that each entity has an array with all implementations in its
 * link field.                                                              */
/*--------------------------------------------------------------------------*/
272

273
274
275
/**
 * Returns an array of all methods that could be called at a Sel node.
 * This array contains every entry only once.
276
277
 *
 * @param sel  the Sel node
278
 */
279
280
281
282
static ir_entity ** get_Sel_arr(ir_node * sel) {
  static ir_entity ** NULL_ARRAY = NULL;
  ir_entity * ent;
  ir_entity ** arr;
283

Michael Beck's avatar
Michael Beck committed
284
  assert(is_Sel(sel));
285
  ent = get_Sel_entity(sel);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
286
287
  ent = get_inherited_methods_implementation(ent);

288
  assert(is_Method_type(get_entity_type(ent))); /* what else? */
289
290
291
292
293
294
295
  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) {
296
      NULL_ARRAY = NEW_ARR_F(ir_entity *, 0);
297
298
299
300
301
    }
    return NULL_ARRAY;
  }
}

302
303
/**
 * Returns the number of possible called methods at a Sel node.
304
305
 *
 * @param sel  the Sel node
306
 */
307
308
309
310
static int get_Sel_n_methods(ir_node * sel) {
  return ARR_LEN(get_Sel_arr(sel));
}

311
312
313
/**
 * Returns the ith possible called method entity at a Sel node.
 */
314
315
static ir_entity * get_Sel_method(ir_node * sel, int pos) {
  ir_entity ** arr = get_Sel_arr(sel);
316
317
318
319
  assert(pos >= 0 && pos < ARR_LEN(arr));
  return arr[pos];
}

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

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
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;
  }
342

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
343
344
345
  case iro_Tuple:
    free_mark(get_Tuple_pred(node, n), set);
    break;
346

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
347
348
349
350
351
352
353
  case iro_Id:
    free_mark_proj(get_Id_pred(node), n, set);
    break;

  case iro_Start:
  case iro_Alloc:
  case iro_Load:
354
    /* nothing: Die Operationen werden in free_ana_walker() selbst
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
355
356
357
358
359
360
361
362
363
364
     * behandelt. */
    break;

  default:
    assert(0 && "unexpected opcode or opcode not implemented");
    break;
  }
  set_irn_link(node, NULL);
}

365
/**
Michael Beck's avatar
Michael Beck committed
366
367
368
369
370
371
372
 * Called for predecessors nodes of "interesting" ones.
 * Interesting ones include all nodes that can somehow make
 * a method visible.
 *
 * If a method (or a set of methods in case of polymorph calls) gets visible,
 * add it to the set of 'free' methods
 *
373
374
375
376
 * @param node  the current visited node
 * @param set   the set of all free methods
 */
static void free_mark(ir_node *node, eset * set) {
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
377
378
  int i;

Michael Beck's avatar
Michael Beck committed
379
  if (get_irn_link(node) == MARK)
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
380
    return; /* already visited */
Michael Beck's avatar
Michael Beck committed
381

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
382
  set_irn_link(node, MARK);
383

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
384
385
  switch (get_irn_opcode(node)) {
  case iro_Sel: {
386
    ir_entity * ent = get_Sel_entity(node);
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
387
388
389
390
391
392
393
394
395
    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) {
396
      ir_entity * ent = get_SymConst_entity(node);
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
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
      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);
}
423

424
/**
Michael Beck's avatar
Michael Beck committed
425
 * post-walker. Find method addresses.
426
427
428
 */
static void free_ana_walker(ir_node *node, void *env) {
  eset *set = env;
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
429
  int i;
430

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
431
  if (get_irn_link(node) == MARK) {
432
    /* already visited */
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
    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);
450
451
    for (i = get_Call_n_params(node) - 1; i >= 0; --i) {
      ir_node *pred = get_Call_param(node, i);
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
      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);
}

472
473
/**
 * Add all method addresses in global initializers to the set.
474
475
476
477
478
479
480
481
 *
 * @note
 * We do NOT check the type here, just it it's an entity address.
 * The reason for this is code like:
 *
 * void *p = function;
 *
 * which is sometimes used to anchor functions.
482
 */
483
static void add_method_address(ir_entity *ent, eset *set)
484
485
{
  ir_node *n;
486
  ir_type *tp;
487
488
489
490
491
492
493
494
495
  int i;

  /* do not check uninitialized values */
  if (get_entity_variability(ent) == variability_uninitialized)
    return;

  if (is_atomic_entity(ent)) {
    tp = get_entity_type(ent);

496
497
    /* ignore methods: these of course reference it's address */
    if (is_Method_type(tp))
Michael Beck's avatar
Michael Beck committed
498
      return;
499
500
501
502
503
504
505

    /* let's check if it's the address of a function */
    n = get_atomic_ent_value(ent);
    if (get_irn_op(n) == op_SymConst) {
      if (get_SymConst_kind(n) == symconst_addr_ent) {
        ent = get_SymConst_entity(n);

506
507
        if (is_Method_type(get_entity_type(ent)))
          eset_insert(set, ent);
508
509
510
511
512
513
514
515
516
517
      }
    }
  }
  else {
    for (i = get_compound_ent_n_values(ent) - 1; i >= 0; --i) {
      n = get_compound_ent_value(ent, i);

      /* let's check if it's the address of a function */
      if (get_irn_op(n) == op_SymConst) {
        if (get_SymConst_kind(n) == symconst_addr_ent) {
518
          ir_entity *ent = get_SymConst_entity(n);
519

520
521
          if (is_Method_type(get_entity_type(ent)))
            eset_insert(set, ent);
522
523
524
525
526
527
        }
      }
    }
  }
}

Michael Beck's avatar
Michael Beck committed
528
529
530
531
532
/**
 * returns a list of 'free' methods, i.e., the methods that can be called
 * from external or via function pointers.
 *
 * Die Datenstrukturen fr sel-Methoden (sel_methods) mu vor dem
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
533
534
535
 * 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
Michael Beck's avatar
Michael Beck committed
536
537
 * auf eine echt externe Methode.
 */
538
static ir_entity ** get_free_methods(void)
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
539
{
540
  eset *free_set = eset_create();
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
541
  int i;
542
543
  ir_entity **arr = NEW_ARR_F(ir_entity *, 0);
  ir_entity *ent;
544
  ir_graph *irg;
545
  ir_type *glob;
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
546
547

  for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
548
549
    irg = get_irp_irg(i);
    ent = get_irg_entity(irg);
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
550
551
    /* insert "external visible" methods. */
    if (get_entity_visibility(ent) != visibility_local) {
552
      eset_insert(free_set, ent);
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
553
554
555
    }
    /* Finde alle Methoden die in dieser Methode extern sichtbar werden,
       z.B. da die Adresse einer Methode abgespeichert wird. */
556
    irg_walk_graph(irg, NULL, free_ana_walker, free_set);
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
557
558
559
560
  }

  /* insert sticky methods, too */
  for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
561
    ent = get_irg_entity(get_irp_irg(i));
562
    /* insert "sticky" methods. */
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
563
    if (get_entity_stickyness (ent) == stickyness_sticky) {
564
      eset_insert(free_set, ent);
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
565
566
567
    }
  }

Michael Beck's avatar
Michael Beck committed
568
  /* insert all methods the initializes global variables */
569
570
571
572
573
574
  glob = get_glob_type();
  for (i = get_class_n_members(glob) - 1; i >= 0; --i) {
    ent = get_class_member(glob, i);

    add_method_address(ent, free_set);
  }
Michael Beck's avatar
Michael Beck committed
575

576
  /* the main program is even then "free", if it's not external visible. */
577
578
579
  irg = get_irp_main_irg();
  if (irg)
    eset_insert(free_set, get_irg_entity(irg));
580
581

  /* Finally, transform the set into an array. */
582
  for (ent = eset_first(free_set); ent; ent = eset_next(free_set)) {
583
    ARR_APP1(ir_entity *, arr, ent);
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
584
  }
585
  eset_destroy(free_set);
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
586
587
588
589
590
591
592
593
594

  return arr;
}

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

static void callee_ana_node(ir_node * node, eset * methods);
595
596
597
598
599
600
601
602
603

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

604
  switch (get_irn_opcode(node)) {
605
606
607
608
609
610
  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) {
611
      if (get_irn_op(pred) == op_Tuple) {
612
        callee_ana_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, methods);
613
      } else {
614
        eset_insert(methods, MARK); /* free method -> unknown */
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
      }
    }
    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);
}

Michael Beck's avatar
Michael Beck committed
636
/**
Michael Beck's avatar
Michael Beck committed
637
 * Analyse a Call address.
Michael Beck's avatar
Michael Beck committed
638
 *
Michael Beck's avatar
Michael Beck committed
639
640
 * @param node     the node representing the call address
 * @param methods  after call contains the set of all possibly called entities
Michael Beck's avatar
Michael Beck committed
641
 */
Michael Beck's avatar
Michael Beck committed
642
static void callee_ana_node(ir_node *node, eset *methods) {
643
644
  int i;

Michael Beck's avatar
fixed:    
Michael Beck committed
645
  assert(mode_is_reference(get_irn_mode(node)) || is_Bad(node));
Michael Beck's avatar
Michael Beck committed
646
  /* Beware of recursion */
647
648
649
650
651
652
  if (get_irn_link(node) == MARK) {
    /* already visited */
    return;
  }
  set_irn_link(node, MARK);

653
  switch (get_irn_opcode(node)) {
654
655
656
657
658
  case iro_Const:
    /* A direct address call. We tread this as an external
       call and ignore it completely. */
    eset_insert(methods, MARK); /* free method -> unknown */
    break;
659
  case iro_SymConst:
Beyhan's avatar
Beyhan committed
660
    if (get_SymConst_kind(node) == symconst_addr_ent) {
661
      ir_entity *ent = get_SymConst_entity(node);
662
      assert(ent && is_Method_type(get_entity_type(ent)));
663
      eset_insert(methods, ent);
Beyhan's avatar
Beyhan committed
664
665
666
667
668
    } else {
      assert(get_SymConst_kind(node) == symconst_addr_name);
      /* externe Methode (wegen fix_symconst!) */
      eset_insert(methods, MARK); /* free method -> unknown */
    }
669
670
671
672
    break;
  case iro_Sel:
    /* polymorphe Methode */
    for (i = get_Sel_n_methods(node) - 1; i >= 0; --i) {
673
      ir_entity * ent = get_Sel_method(node, i);
674
      if (ent) {
Florian Liekweg's avatar
Florian Liekweg committed
675
        eset_insert(methods, ent);
676
      } else {
Florian Liekweg's avatar
Florian Liekweg committed
677
        eset_insert(methods, MARK);
678
679
680
681
682
683
684
685
      }
    }
    break;

  case iro_Bad:
    /* nothing */
    break;

Michael Beck's avatar
Michael Beck committed
686
  case iro_Phi:
687
688
689
690
691
    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
692
693
694
695
696
  case iro_Mux:
    callee_ana_node(get_Mux_false(node), methods);
    callee_ana_node(get_Mux_true(node), methods);
    break;

Michael Beck's avatar
Michael Beck committed
697
698
699
700
701
702
703
  case iro_Psi:
    for (i = get_Psi_n_conds(node) - 1; i >= 0; --i) {
      callee_ana_node(get_Psi_val(node, i), methods);
    }
    callee_ana_node(get_Psi_default(node), methods);
    break;

704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
  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);
}

Michael Beck's avatar
Michael Beck committed
727
728
729
730
/**
 * Walker: Analyses every call node and calculates an array of possible
 * callees for that call.
 */
731
static void callee_walker(ir_node * call, void * env) {
Michael Beck's avatar
Michael Beck committed
732
  if (is_Call(call)) {
733
    eset * methods = eset_create();
734
735
    ir_entity * ent;
    ir_entity ** arr = NEW_ARR_F(ir_entity *, 0);
736
737
    assert(get_irn_op(get_Call_ptr(call)) != op_Id);
    callee_ana_node(get_Call_ptr(call), methods);
738
    if (eset_contains(methods, MARK)) { /* unknown method */
739
      ARR_APP1(ir_entity *, arr, unknown_entity);
740
741
742
    }
    for (ent = eset_first(methods); ent; ent = eset_next(methods)) {
      if (ent != MARK) {
743
        ARR_APP1(ir_entity *, arr, ent);
744
745
      }
    }
746
#if 0  /* This generates Bad nodes when we don't want it.
747
          Call it with a check for valid cgana information in local_optimize. */
748
    if (ARR_LEN(arr) == 0 && get_opt_optimize() && get_opt_closed_world() && get_opt_dyn_meth_dispatch()) {
749
750
751
752
753
      /* 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
754
      ir_node *mem = get_Call_mem(call);
755
      turn_into_tuple (call, 5 /* pn_Call_max */);
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
756
757
758
759
      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() ?? */
760
      set_Tuple_pred(call, pn_Call_M_except        , new_Bad());
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
761

762
763
764
    } else
#endif
    {
765
766
767
768
769
770
771
      set_Call_callee_arr(call, ARR_LEN(arr), arr);
    }
    DEL_ARR_F(arr);
    eset_destroy(methods);
  }
}

Michael Beck's avatar
Michael Beck committed
772
773
774
775
776
777
/**
 * Walker: Removes all tuple.
 */
static void remove_Tuples(ir_node *proj, void *env) {
  ir_node *nn;
  if (! is_Proj(proj)) return;
778

Michael Beck's avatar
Michael Beck committed
779
780
  nn = skip_Tuple(proj);
  if (nn != proj) exchange(proj, nn);
781
782
783
}


784
785
786
787
788
789
790
/* 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
791
  for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
792
793
794
    ir_graph *irg = get_irp_irg(i);
    irg_walk_graph(irg, callee_walker, remove_Tuples, NULL);
    set_irg_callee_info_state(irg, irg_callee_info_consistent);
795
  }
Götz Lindenmaier's avatar
Götz Lindenmaier committed
796
  set_irp_callee_info_state(irg_callee_info_consistent);
797
798
}

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
799
800
801
/*--------------------------------------------------------------------------*/
/* Cleanup after analyses.                                                  */
/*--------------------------------------------------------------------------*/
802

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
803
804
/** Frees intermediate data structures. */
static void sel_methods_dispose(void) {
805
  ir_entity * ent;
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
806
807
  assert(entities);
  for (ent = eset_first(entities); ent; ent = eset_next(entities)) {
808
    ir_entity ** arr = get_entity_link(ent);
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
809
810
    if (arr) {
      DEL_ARR_F(arr);
811
    }
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
812
    set_entity_link(ent, NULL);
813
  }
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
814
815
  eset_destroy(entities);
  entities = NULL;
816
817
}

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
818
819
820
/*--------------------------------------------------------------------------*/
/* Freeing the callee arrays.                                               */
/*--------------------------------------------------------------------------*/
821

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
822
static void destruct_walker(ir_node * node, void * env) {
Michael Beck's avatar
Michael Beck committed
823
  if (is_Call(node)) {
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
824
    remove_Call_callee_arr(node);
825
826
827
  }
}

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
828
829
830
/*--------------------------------------------------------------------------*/
/* Main drivers.                                                            */
/*--------------------------------------------------------------------------*/
831

832
833
void cgana(int *length, ir_entity ***free_methods) {
  ir_entity ** free_meths, **p;
834

Götz Lindenmaier's avatar
Götz Lindenmaier committed
835
  /* Optimize Sel/SymConst nodes and compute all methods that implement an entity. */
836
  sel_methods_init();
Götz Lindenmaier's avatar
Götz Lindenmaier committed
837
  free_meths = get_free_methods();
838
839
840
841
842
  callee_ana();
  sel_methods_dispose();

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

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

849
850
  DEL_ARR_F(free_meths);
}
851

Götz Lindenmaier's avatar
Götz Lindenmaier committed
852
853
854
855
856
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);
}

Götz Lindenmaier's avatar
Götz Lindenmaier committed
857
void free_irp_callee_info(void) {
Michael Beck's avatar
Michael Beck committed
858
859
  int i;
  for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
Götz Lindenmaier's avatar
Götz Lindenmaier committed
860
861
862
863
    free_callee_info(get_irp_irg(i));
  }
}

864
/* Optimize the address expressions passed to call nodes.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
865
866
867
868
 *
 * This optimization performs the following transformations for
 * all ir graphs:
 * - All SymConst operations that refer to intern methods are replaced
Michael Beck's avatar
Michael Beck committed
869
 *   by Const operations referring to the corresponding entity.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
870
 * - Sel nodes, that select entities that are not overwritten are
Michael Beck's avatar
Michael Beck committed
871
 *   replaced by Const nodes referring to the selected entity.
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
872
 * - Sel nodes, for which no method exists at all are replaced by Bad
Götz Lindenmaier's avatar
Götz Lindenmaier committed
873
874
 *   nodes.
 * - Sel nodes with a pointer input that is an Alloc node are replaced
Michael Beck's avatar
Michael Beck committed
875
 *   by Const nodes referring to the entity that implements the method in
Götz Lindenmaier's avatar
Götz Lindenmaier committed
876
877
 *   the type given by the Alloc node.
 */
878
879
880
881
void opt_call_addrs(void) {
  sel_methods_init();
  sel_methods_dispose();
}