cgana.c 26.9 KB
Newer Older
Götz Lindenmaier's avatar
Götz Lindenmaier committed
1
/*
Matthias Braun's avatar
Matthias Braun committed
2
3
4
 * Copyrigth (C) 1995-2007 University of Karlsruhe.  All right reserved.
 *
 * This file is part of libFirm.
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
5
 *
Matthias Braun's avatar
Matthias Braun committed
6
7
8
9
 * This file may be distributed and/or modified under the terms of the
 * GNU General Public License version 2 as published by the Free Software
 * Foundation and appearing in the file LICENSE.GPL included in the
 * packaging of this file.
10
 *
Matthias Braun's avatar
Matthias Braun committed
11
12
13
14
15
16
17
 * Licensees holding valid libFirm Professional Edition licenses may use
 * this file in accordance with the libFirm Commercial License.
 * Agreement provided with the Software.
 *
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
18
 */
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
19

Matthias Braun's avatar
Matthias Braun committed
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/**
 * @file
 * @brief      Intraprozedural analyses to estimate the call graph.
 * @author     Hubert Schmid
 * @date       09.06.2002
 * @version    $Id$
 * @summary
 *  Interprocedural analysis to estimate the calling relation.
 *
 *  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.
 */
34
#ifdef HAVE_CONFIG_H
Michael Beck's avatar
Michael Beck committed
35
36
37
38
39
# include "config.h"
#endif

#ifdef HAVE_STRING_H
# include <string.h>
40
#endif
41
42

#include "cgana.h"
Florian Liekweg's avatar
Florian Liekweg committed
43
#include "rta.h"
44

Michael Beck's avatar
Michael Beck committed
45
#include "xmalloc.h"
Götz Lindenmaier's avatar
Götz Lindenmaier committed
46
47
48
#include "irnode_t.h"
#include "irmode_t.h"
#include "irprog_t.h"
49
50
51
#include "irgwalk.h"
#include "ircons.h"
#include "irgmod.h"
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
52
#include "iropt.h"
53

Götz Lindenmaier's avatar
Götz Lindenmaier committed
54
#include "irflag_t.h"
Götz Lindenmaier's avatar
Götz Lindenmaier committed
55
#include "dbginfo_t.h"
Michael Beck's avatar
Michael Beck committed
56
#include "iropt_dbg.h"
Götz Lindenmaier's avatar
Götz Lindenmaier committed
57

Götz Lindenmaier's avatar
Götz Lindenmaier committed
58
59
60
#include "eset.h"
#include "pmap.h"
#include "array.h"
Götz Lindenmaier's avatar
Götz Lindenmaier committed
61

62
63
#include "irdump.h"

64
#include "irhooks.h"
Michael Beck's avatar
Michael Beck committed
65

66
67


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

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

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
73
74
75
/*--------------------------------------------------------------------------*/
/* The analysis                                                             */
/*--------------------------------------------------------------------------*/
76
77


Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
78
79
80
81
/*--------------------------------------------------------------------------*/
/* Initialize datastructures, remove unwanted constructs, optimize          */
/* call target computations.                                                */
/*--------------------------------------------------------------------------*/
82

83
/** Returns the entity that contains the implementation of the inherited
Götz Lindenmaier's avatar
Götz Lindenmaier committed
84
 *  entity if available, else returns the entity passed. */
85
static ir_entity *get_inherited_methods_implementation(ir_entity *inh_meth) {
86
87
  assert(get_atomic_ent_value(inh_meth) && "constant entity without value");
  assert((get_irn_op(get_atomic_ent_value(inh_meth)) == op_SymConst) &&
88
89
         (get_SymConst_kind(get_atomic_ent_value(inh_meth)) == symconst_addr_ent) &&
         "Complex constant values not supported -- address of method should be straight constant!");
90
91

  return get_SymConst_entity(get_atomic_ent_value(inh_meth));
92
93
}

94
/** Collect the entity representing the implementation of this
95
 *  method (not the same if inherited) and all entities for overwriting
96
97
98
99
100
101
102
103
104
105
106
 *  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
 */
107
static void collect_impls(ir_entity *method, eset *set, int *size, int *open) {
108
  int i;
109
  ir_entity *impl;
Michael Beck's avatar
Michael Beck committed
110

111
112
  /* 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
113
  impl = method;
114
115
116
117
118
119
120
121
  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
122
  /*- recursive descent -*/
123
  for (i = get_entity_n_overwrittenby(method) - 1; i >= 0; --i)
124
    collect_impls(get_entity_overwrittenby(method, i), set, size, open);
125
126
}

127
128
129
130
131
132
133
134
135
136
/** Alle Methoden bestimmen, die die übergebene Methode überschreiben
 *  (und implementieren). In der zurückgegebenen Reihung kommt jede
 *  Methode nur einmal vor. Der Wert 'NULL' steht für unbekannte
 *  (externe) Methoden. Die zurückgegebene Reihung muß vom Aufrufer
 *  wieder freigegeben werden (siehe "DEL_ARR_F"). Gibt es überhaupt
 *  keine Methoden, die "method" überschreiben, so gibt die Methode
 *  "NULL" zurück.
 *
 *  @param method
 */
137
static ir_entity ** get_impl_methods(ir_entity * method) {
138
139
  eset * set = eset_create();
  int size = 0;
140
  ir_entity ** arr;
141
  int open = 0;
142

143
  /* Collect all method entities that can be called here */
144
145
  collect_impls(method, set, &size, &open);

146
  /* Vorgaenger einfuegen. */
147
148
149
150
  if (size == 0 && !open) {
    /* keine implementierte überschriebene Methode */
    arr = NULL;
  } else if (open) {
151
152
    ir_entity * ent;
    arr = NEW_ARR_F(ir_entity *, size + 1);
153
154
155
    arr[0] = NULL;  /* Represents open method */
    for (ent = eset_first(set); size > 0; ent = eset_next(set), --size)
      arr[size] = ent;
156
  } else {
157
158
    ir_entity * ent;
    arr = NEW_ARR_F(ir_entity *, size);
159
160
    for (size -= 1, ent = eset_first(set); size >= 0; ent = eset_next(set), --size)
      arr[size] = ent;
161
162
163
164
165
  }
  eset_destroy(set);
  return arr;
}

Michael Beck's avatar
Michael Beck committed
166
/** Analyze address computations.
167
 *
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
168
 *  Compute for all Sel nodes the set of methods that can be selected.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
169
 *  For each entity we store the set of subentities in the link field.
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
170
171
172
173
 *
 *  Further do some optimizations:
 *  - Call standard optimizations for Sel nodes: this removes polymorphic
 *    calls.
174
 *  - If the node is a SymConst(name) replace it by SymConst(ent) if possible.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
175
176
 *    For this we precomputed a map name->entity.  Nowadays, we no more support
 *    this and assert.
177
 *  - If the node is a Sel:
Götz Lindenmaier's avatar
Götz Lindenmaier committed
178
179
180
181
 *    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.
182
183
 *
 *  @param node The node to analyze
184
 *  @param env  A map that maps names of entities to the entities.
185
 */
186
187
static void sel_methods_walker(ir_node * node, void *env) {
  pmap *ldname_map = env;
188
  ir_entity **arr;
189

Götz Lindenmaier's avatar
Götz Lindenmaier committed
190
  /* Call standard optimizations */
Michael Beck's avatar
Michael Beck committed
191
  if (is_Sel(node)) {
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
192
    ir_node *new_node = optimize_in_place(node);
193
194
    if (node != new_node)
      exchange(node, new_node);
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
195
196
  }

197
  /* replace SymConst(name)-operations by SymConst(ent) */
198
  if (get_irn_op(node) == op_SymConst) {
Beyhan's avatar
Beyhan committed
199
200
    if (get_SymConst_kind(node) == symconst_addr_name) {
      pmap_entry * entry = pmap_find(ldname_map, (void *) get_SymConst_name(node));
201
      if (entry != NULL) { /* Method is declared in the compiled code */
202
203
        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].");
204
205
      }
    }
206
207
  }
  else if (get_irn_op(node) == op_Sel &&
208
           is_Method_type(get_entity_type(get_Sel_entity(node)))) {
209
    ir_entity * ent = get_SymConst_entity(get_atomic_ent_value(get_Sel_entity(node)));
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
210
211
212
    assert(get_entity_peculiarity(ent) != peculiarity_inherited);

    if (!eset_contains(entities, ent)) {
213
214
215
      /* 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
216
217
      set_entity_link(ent, get_impl_methods(ent));
      eset_insert(entities, ent);
218
    }
219

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
220
    /* -- As an add on we get an optimization that removes polymorphic calls.
221
222
223
224
225
226
227
228
       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
229
      assert (get_entity_peculiarity(ent) == peculiarity_description);
230
    }
231
    else if (get_opt_optimize() && get_opt_closed_world() && get_opt_dyn_meth_dispatch() &&
232
233
234
235
236
237
238
239
240
241
242
        (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);
243
      new_node = copy_const_value(get_irn_dbg_info(node), get_atomic_ent_value(arr[0]));
244
245
      DBG_OPT_POLY(node, new_node);
      exchange(node, new_node);
246
247
248
249
    }
  }
}

Götz Lindenmaier's avatar
Götz Lindenmaier committed
250
251
252
/** Initialize auxiliary data structures.
 *
 *  Computes a set of entities that overwrite an entity and contain
253
 *  an implementation. The set is stored in the entity's link field.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
254
255
256
257
258
 *
 *  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). */
259
260
static void sel_methods_init(void) {
  int i;
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
261
  pmap * ldname_map = pmap_create();   /* Map entity names to entities: to replace
262
                                          SymConst(name) by SymConst(ent). */
263
264
  assert(entities == NULL);
  entities = eset_create();
Götz Lindenmaier's avatar
Götz Lindenmaier committed
265
  for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
266
    ir_entity * ent = get_irg_entity(get_irp_irg(i));
267
    /* only external visible methods are allowed to call by a SymConst_ptr_name */
268
    if (get_entity_visibility(ent) != visibility_local) {
269
270
271
      pmap_insert(ldname_map, (void *) get_entity_ld_ident(ent), ent);
    }
  }
Götz Lindenmaier's avatar
Götz Lindenmaier committed
272

273
  all_irg_walk(sel_methods_walker, NULL, ldname_map);
274
275
276
  pmap_destroy(ldname_map);
}

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
277
278
279
280
281
282
/*--------------------------------------------------------------------------*/
/* Find free methods.
 *
 * We expect that each entity has an array with all implementations in its
 * link field.                                                              */
/*--------------------------------------------------------------------------*/
283

284
285
286
/**
 * Returns an array of all methods that could be called at a Sel node.
 * This array contains every entry only once.
287
288
 *
 * @param sel  the Sel node
289
 */
290
291
292
293
static ir_entity ** get_Sel_arr(ir_node * sel) {
  static ir_entity ** NULL_ARRAY = NULL;
  ir_entity * ent;
  ir_entity ** arr;
294

Michael Beck's avatar
Michael Beck committed
295
  assert(is_Sel(sel));
296
  ent = get_Sel_entity(sel);
Götz Lindenmaier's avatar
Götz Lindenmaier committed
297
298
  ent = get_inherited_methods_implementation(ent);

299
  assert(is_Method_type(get_entity_type(ent))); /* what else? */
300
301
302
303
304
305
306
  arr = get_entity_link(ent);
  if (arr) {
    return arr;
  } else {
    /* "NULL" zeigt an, dass keine Implementierung existiert. Dies
     * kann für polymorphe (abstrakte) Methoden passieren. */
    if (!NULL_ARRAY) {
307
      NULL_ARRAY = NEW_ARR_F(ir_entity *, 0);
308
309
310
311
312
    }
    return NULL_ARRAY;
  }
}

313
314
/**
 * Returns the number of possible called methods at a Sel node.
315
316
 *
 * @param sel  the Sel node
317
 */
318
319
320
321
static int get_Sel_n_methods(ir_node * sel) {
  return ARR_LEN(get_Sel_arr(sel));
}

322
323
324
/**
 * Returns the ith possible called method entity at a Sel node.
 */
325
326
static ir_entity * get_Sel_method(ir_node * sel, int pos) {
  ir_entity ** arr = get_Sel_arr(sel);
327
328
329
330
  assert(pos >= 0 && pos < ARR_LEN(arr));
  return arr[pos];
}

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

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
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;
  }
353

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
354
355
356
  case iro_Tuple:
    free_mark(get_Tuple_pred(node, n), set);
    break;
357

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
358
359
360
361
362
363
364
  case iro_Id:
    free_mark_proj(get_Id_pred(node), n, set);
    break;

  case iro_Start:
  case iro_Alloc:
  case iro_Load:
365
    /* nothing: Die Operationen werden in free_ana_walker() selbst
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
366
367
368
369
370
371
372
373
374
375
     * behandelt. */
    break;

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

376
/**
Michael Beck's avatar
Michael Beck committed
377
378
379
380
381
382
383
 * 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
 *
384
385
386
387
 * @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
388
389
  int i;

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

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

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
395
396
  switch (get_irn_opcode(node)) {
  case iro_Sel: {
397
    ir_entity * ent = get_Sel_entity(node);
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
398
399
400
401
402
403
404
405
406
    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) {
407
      ir_entity * ent = get_SymConst_entity(node);
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
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
      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);
}
434

435
/**
Michael Beck's avatar
Michael Beck committed
436
 * post-walker. Find method addresses.
437
438
439
 */
static void free_ana_walker(ir_node *node, void *env) {
  eset *set = env;
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
440
  int i;
441

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
442
  if (get_irn_link(node) == MARK) {
443
    /* already visited */
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
    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 natürlich kein
   * Verräter ist. */
  case iro_Call:
    set_irn_link(node, MARK);
461
462
    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
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
      if (mode_is_reference(get_irn_mode(pred))) {
        free_mark(pred, set);
      }
    }
    break;
  /* other nodes: Alle anderen Knoten nehmen wir als Verräter 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);
}

483
484
/**
 * Add all method addresses in global initializers to the set.
485
486
487
488
489
490
491
492
 *
 * @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.
493
 */
494
static void add_method_address(ir_entity *ent, eset *set)
495
496
{
  ir_node *n;
497
  ir_type *tp;
498
499
500
501
502
503
504
505
506
  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);

507
508
    /* ignore methods: these of course reference it's address */
    if (is_Method_type(tp))
Michael Beck's avatar
Michael Beck committed
509
      return;
510
511
512
513
514
515
516

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

517
518
        if (is_Method_type(get_entity_type(ent)))
          eset_insert(set, ent);
519
520
521
522
523
524
525
526
527
528
      }
    }
  }
  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) {
529
          ir_entity *ent = get_SymConst_entity(n);
530

531
532
          if (is_Method_type(get_entity_type(ent)))
            eset_insert(set, ent);
533
534
535
536
537
538
        }
      }
    }
  }
}

Michael Beck's avatar
Michael Beck committed
539
540
541
542
543
/**
 * returns a list of 'free' methods, i.e., the methods that can be called
 * from external or via function pointers.
 *
 * Die Datenstrukturen für sel-Methoden (sel_methods) muß vor dem
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
544
545
546
 * Aufruf von "get_free_methods" aufgebaut sein. Die (internen)
 * SymConst(name)-Operationen müssen in passende SymConst(ent)-Operationen
 * umgewandelt worden sein, d.h. SymConst-Operationen verweisen immer
Michael Beck's avatar
Michael Beck committed
547
548
 * auf eine echt externe Methode.
 */
549
static ir_entity ** get_free_methods(void)
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
550
{
551
  eset *free_set = eset_create();
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
552
  int i;
553
554
  ir_entity **arr = NEW_ARR_F(ir_entity *, 0);
  ir_entity *ent;
555
  ir_graph *irg;
556
  ir_type *glob;
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
557
558

  for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
559
560
    irg = get_irp_irg(i);
    ent = get_irg_entity(irg);
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
561
562
    /* insert "external visible" methods. */
    if (get_entity_visibility(ent) != visibility_local) {
563
      eset_insert(free_set, ent);
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
564
565
566
    }
    /* Finde alle Methoden die in dieser Methode extern sichtbar werden,
       z.B. da die Adresse einer Methode abgespeichert wird. */
567
    irg_walk_graph(irg, NULL, free_ana_walker, free_set);
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
568
569
570
571
  }

  /* insert sticky methods, too */
  for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
572
    ent = get_irg_entity(get_irp_irg(i));
573
    /* insert "sticky" methods. */
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
574
    if (get_entity_stickyness (ent) == stickyness_sticky) {
575
      eset_insert(free_set, ent);
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
576
577
578
    }
  }

Michael Beck's avatar
Michael Beck committed
579
  /* insert all methods the initializes global variables */
580
581
582
583
584
585
  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
586

587
  /* the main program is even then "free", if it's not external visible. */
588
589
590
  irg = get_irp_main_irg();
  if (irg)
    eset_insert(free_set, get_irg_entity(irg));
591
592

  /* Finally, transform the set into an array. */
593
  for (ent = eset_first(free_set); ent; ent = eset_next(free_set)) {
594
    ARR_APP1(ir_entity *, arr, ent);
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
595
  }
596
  eset_destroy(free_set);
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
597
598
599
600
601
602
603
604
605

  return arr;
}

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

static void callee_ana_node(ir_node * node, eset * methods);
606
607
608
609
610
611
612
613
614

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

615
  switch (get_irn_opcode(node)) {
616
617
618
619
620
621
  case iro_Proj: {
    /* proj_proj: in einem "sinnvollen" Graphen kommt jetzt ein
     * op_Tuple oder ein Knoten, der eine "freie Methode"
     * zurückgibt. */
    ir_node * pred = get_Proj_pred(node);
    if (get_irn_link(pred) != MARK) {
622
      if (get_irn_op(pred) == op_Tuple) {
623
        callee_ana_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, methods);
624
      } else {
625
        eset_insert(methods, MARK); /* free method -> unknown */
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
      }
    }
    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
647
/**
Michael Beck's avatar
Michael Beck committed
648
 * Analyse a Call address.
Michael Beck's avatar
Michael Beck committed
649
 *
Michael Beck's avatar
Michael Beck committed
650
651
 * @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
652
 */
Michael Beck's avatar
Michael Beck committed
653
static void callee_ana_node(ir_node *node, eset *methods) {
654
655
  int i;

Michael Beck's avatar
fixed:    
Michael Beck committed
656
  assert(mode_is_reference(get_irn_mode(node)) || is_Bad(node));
Michael Beck's avatar
Michael Beck committed
657
  /* Beware of recursion */
658
659
660
661
662
663
  if (get_irn_link(node) == MARK) {
    /* already visited */
    return;
  }
  set_irn_link(node, MARK);

664
  switch (get_irn_opcode(node)) {
665
666
667
668
669
  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;
670
  case iro_SymConst:
Beyhan's avatar
Beyhan committed
671
    if (get_SymConst_kind(node) == symconst_addr_ent) {
672
      ir_entity *ent = get_SymConst_entity(node);
673
      assert(ent && is_Method_type(get_entity_type(ent)));
674
      eset_insert(methods, ent);
Beyhan's avatar
Beyhan committed
675
676
677
678
679
    } else {
      assert(get_SymConst_kind(node) == symconst_addr_name);
      /* externe Methode (wegen fix_symconst!) */
      eset_insert(methods, MARK); /* free method -> unknown */
    }
680
681
682
683
    break;
  case iro_Sel:
    /* polymorphe Methode */
    for (i = get_Sel_n_methods(node) - 1; i >= 0; --i) {
684
      ir_entity * ent = get_Sel_method(node, i);
685
      if (ent) {
Florian Liekweg's avatar
Florian Liekweg committed
686
        eset_insert(methods, ent);
687
      } else {
Florian Liekweg's avatar
Florian Liekweg committed
688
        eset_insert(methods, MARK);
689
690
691
692
693
694
695
696
      }
    }
    break;

  case iro_Bad:
    /* nothing */
    break;

Michael Beck's avatar
Michael Beck committed
697
  case iro_Phi:
698
699
700
701
702
    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
703
704
705
706
707
  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
708
709
710
711
712
713
714
  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;

715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
  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
738
739
740
741
/**
 * Walker: Analyses every call node and calculates an array of possible
 * callees for that call.
 */
742
static void callee_walker(ir_node * call, void * env) {
Michael Beck's avatar
Michael Beck committed
743
  if (is_Call(call)) {
744
    eset * methods = eset_create();
745
746
    ir_entity * ent;
    ir_entity ** arr = NEW_ARR_F(ir_entity *, 0);
747
748
    assert(get_irn_op(get_Call_ptr(call)) != op_Id);
    callee_ana_node(get_Call_ptr(call), methods);
749
    if (eset_contains(methods, MARK)) { /* unknown method */
750
      ARR_APP1(ir_entity *, arr, unknown_entity);
751
752
753
    }
    for (ent = eset_first(methods); ent; ent = eset_next(methods)) {
      if (ent != MARK) {
754
        ARR_APP1(ir_entity *, arr, ent);
755
756
      }
    }
757
#if 0  /* This generates Bad nodes when we don't want it.
758
          Call it with a check for valid cgana information in local_optimize. */
759
    if (ARR_LEN(arr) == 0 && get_opt_optimize() && get_opt_closed_world() && get_opt_dyn_meth_dispatch()) {
760
761
762
763
764
      /* Kann vorkommen, wenn der Vorgänger beispielsweise eine
       * Sel-Operation war, die keine Methoden zurückgeben
       * 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
765
      ir_node *mem = get_Call_mem(call);
766
      turn_into_tuple (call, 5 /* pn_Call_max */);
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
767
768
769
770
      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() ?? */
771
      set_Tuple_pred(call, pn_Call_M_except        , new_Bad());
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
772

773
774
775
    } else
#endif
    {
776
777
778
779
780
781
782
      set_Call_callee_arr(call, ARR_LEN(arr), arr);
    }
    DEL_ARR_F(arr);
    eset_destroy(methods);
  }
}

Michael Beck's avatar
Michael Beck committed
783
784
785
786
787
788
/**
 * Walker: Removes all tuple.
 */
static void remove_Tuples(ir_node *proj, void *env) {
  ir_node *nn;
  if (! is_Proj(proj)) return;
789

Michael Beck's avatar
Michael Beck committed
790
791
  nn = skip_Tuple(proj);
  if (nn != proj) exchange(proj, nn);
792
793
794
}


795
796
797
798
799
800
801
/* Bestimmt für jede Call-Operation die Menge der aufrufbaren Methode
 * und speichert das Ergebnis in der Call-Operation. (siehe
 * "set_Call_callee"). "sel_methods" wird für den Aufbau benötigt und
 * muss bereits aufgebaut sein. */
static void callee_ana(void) {
  int i;
  /* Alle Graphen analysieren. */
Götz Lindenmaier's avatar
Götz Lindenmaier committed
802
  for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
803
804
805
    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);
806
  }
Götz Lindenmaier's avatar
Götz Lindenmaier committed
807
  set_irp_callee_info_state(irg_callee_info_consistent);
808
809
}

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
810
811
812
/*--------------------------------------------------------------------------*/
/* Cleanup after analyses.                                                  */
/*--------------------------------------------------------------------------*/
813

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
814
815
/** Frees intermediate data structures. */
static void sel_methods_dispose(void) {
816
  ir_entity * ent;
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
817
818
  assert(entities);
  for (ent = eset_first(entities); ent; ent = eset_next(entities)) {
819
    ir_entity ** arr = get_entity_link(ent);
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
820
821
    if (arr) {
      DEL_ARR_F(arr);
822
    }
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
823
    set_entity_link(ent, NULL);
824
  }
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
825
826
  eset_destroy(entities);
  entities = NULL;
827
828
}

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
829
830
831
/*--------------------------------------------------------------------------*/
/* Freeing the callee arrays.                                               */
/*--------------------------------------------------------------------------*/
832

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
833
static void destruct_walker(ir_node * node, void * env) {
Michael Beck's avatar
Michael Beck committed
834
  if (is_Call(node)) {
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
835
    remove_Call_callee_arr(node);
836
837
838
  }
}

Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
839
840
841
/*--------------------------------------------------------------------------*/
/* Main drivers.                                                            */
/*--------------------------------------------------------------------------*/
842

843
844
void cgana(int *length, ir_entity ***free_methods) {
  ir_entity ** free_meths, **p;
845

Götz Lindenmaier's avatar
Götz Lindenmaier committed
846
  /* Optimize Sel/SymConst nodes and compute all methods that implement an entity. */
847
  sel_methods_init();
Götz Lindenmaier's avatar
Götz Lindenmaier committed
848
  free_meths = get_free_methods();
849
850
851
852
853
  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
854
  p = xmalloc(sizeof(*p) * ARR_LEN(free_meths));
855
856
857
858
859
  memcpy(p, free_meths, ARR_LEN(free_meths) * sizeof(*p));

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

860
861
  DEL_ARR_F(free_meths);
}
862

Götz Lindenmaier's avatar
Götz Lindenmaier committed
863
864
865
866
867
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
868
void free_irp_callee_info(void) {
Michael Beck's avatar
Michael Beck committed
869
870
  int i;
  for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
Götz Lindenmaier's avatar
Götz Lindenmaier committed
871
872
873
874
    free_callee_info(get_irp_irg(i));
  }
}

875
/* Optimize the address expressions passed to call nodes.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
876
877
878
879
 *
 * 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
880
 *   by Const operations referring to the corresponding entity.
Götz Lindenmaier's avatar
Götz Lindenmaier committed
881
 * - Sel nodes, that select entities that are not overwritten are
Michael Beck's avatar
Michael Beck committed
882
 *   replaced by Const nodes referring to the selected entity.
Götz Lindenmaier's avatar
bugfix    
Götz Lindenmaier committed
883
 * - Sel nodes, for which no method exists at all are replaced by Bad
Götz Lindenmaier's avatar
Götz Lindenmaier committed
884
885
 *   nodes.
 * - Sel nodes with a pointer input that is an Alloc node are replaced
Michael Beck's avatar
Michael Beck committed
886
 *   by Const nodes referring to the entity that implements the method in
Götz Lindenmaier's avatar
Götz Lindenmaier committed
887
888
 *   the type given by the Alloc node.
 */
889
890
891
892
void opt_call_addrs(void) {
  sel_methods_init();
  sel_methods_dispose();
}