1 /* -------------------------------------------------------------------
3 * -------------------------------------------------------------------
4 * Intraprozedurale Analyse zur Abschätzung der Aufrulrelation. Es
5 * wird eine Menge von freien Methoden und anschließend die an den
6 * Call-Operationen aufrufbaren Methoden bestimmt.
8 * Erstellt: Hubert Schmid, 09.06.2002
9 * ---------------------------------------------------------------- */
25 /* Eindeutige Adresse zur Markierung von besuchten Knoten und zur
26 * Darstellung der unbekannten Methode. */
27 static void * MARK = &MARK;
31 /* --- sel methods ---------------------------------------------------------- */
34 static eset * entities = NULL;
37 /* Bestimmt die eindeutige Methode, die die Methode für den
38 * übergebenene (dynamischen) Typ überschreibt. */
39 static entity * get_implementation(type * class, entity * method) {
41 if (get_entity_peculiarity(method) != description &&
42 get_entity_owner(method) == class) {
45 for (i = get_entity_n_overwrittenby(method) - 1; i >= 0; --i) {
46 entity * e = get_entity_overwrittenby(method, i);
47 if (get_entity_peculiarity(e) != description && get_entity_owner(e) == class) {
51 for (i = get_class_n_supertypes(class) - 1; i >= 0; --i) {
52 entity * e = get_implementation(get_class_supertype(class, i), method);
57 assert(0 && "implemenation not found");
60 /* Returns the entity that contains the implementation of the inherited
61 entity if available, else returns the entity passed. */
62 entity *get_inherited_methods_implementation(entity *inh_meth) {
63 entity *impl_meth = NULL;
64 ir_node *addr = get_atomic_ent_value(inh_meth);
65 assert(addr && "constant entity without value");
67 if (get_irn_op(addr) == op_Const) {
68 impl_meth = get_tv_entity(get_Const_tarval(addr));
71 assert(!impl_meth || get_entity_peculiarity(impl_meth) == existent);
72 return impl_meth? impl_meth : inh_meth;
76 /* Collect the entity representing the implementation of this
77 entity (not the same if inherited) and all entities for overwriting
78 implementations in "set".
79 If the implementation of the method is not included in the
80 compilation unit "open" is set to true.
81 A recursive descend in the overwritten relation.
82 Cycle-free, therefore must terminate. */
83 void collect_impls(entity *method, eset *set, int *size, bool *open) {
85 if (get_entity_peculiarity(method) == existent) {
86 if (get_entity_visibility(method) == external_allocated) {
87 assert(get_entity_irg(method) == NULL);
90 assert(get_entity_irg(method) != NULL);
91 if (!eset_contains(set, method)) {
92 eset_insert(set, method);
97 if (get_entity_peculiarity(method) == inherited) {
98 entity *impl_ent = get_inherited_methods_implementation(method);
99 assert(impl_ent && "no implementation for inherited entity");
100 if (get_entity_visibility(impl_ent) == external_allocated) {
101 assert(get_entity_irg(impl_ent) == NULL);
104 assert(get_entity_irg(impl_ent) != NULL);
105 if (!eset_contains(set, impl_ent)) {
106 eset_insert(set, impl_ent);
111 /** recursive descend **/
112 for (i = get_entity_n_overwrittenby(method) - 1; i >= 0; --i)
113 collect_impls(get_entity_overwrittenby(method, i), set, size, open);
117 /* Alle Methoden bestimmen, die die übergebene Methode überschreiben
118 * (und implementieren). In der zurückgegebenen Reihung kommt jede
119 * Methode nur einmal vor. Der Wert 'NULL' steht für unbekannte
120 * (externe) Methoden. Die zurückgegebene Reihung muß vom Aufrufer
121 * wieder freigegeben werden (siehe "DEL_ARR_F"). Gibt es überhaupt
122 * keine Methoden, die die "method" überschreiben, so gibt die Methode
124 static entity ** get_impl_methods(entity * method) {
125 eset * set = eset_create();
130 /** Collect all method entities that can be called here **/
131 collect_impls(method, set, &size, &open);
134 Vorgaenger einfuegen. **/
135 if (size == 0 && !open) {
136 /* keine implementierte überschriebene Methode */
140 arr = NEW_ARR_F(entity *, size + 1);
141 arr[0] = NULL; /* Represents open method */
142 for (ent = eset_first(set); size > 0; ent = eset_next(set), --size)
146 arr = NEW_ARR_F(entity *, size);
147 for (size -= 1, ent = eset_first(set); size >= 0; ent = eset_next(set), --size)
155 static void sel_methods_walker(ir_node * node, pmap * ldname_map) {
156 if (get_irn_op(node) == op_SymConst) {
157 /* Wenn möglich SymConst-Operation durch Const-Operation
159 if (get_SymConst_kind(node) == linkage_ptr_info) {
160 pmap_entry * entry = pmap_find(ldname_map, (void *) get_SymConst_ptrinfo(node));
161 if (entry != NULL) { /* Method is declared in the compiled code */
162 entity * ent = entry->value;
163 if (get_entity_visibility(ent) != external_allocated) { /* Meth. is defined */
164 assert(get_entity_irg(ent));
165 set_irg_current_block(current_ir_graph, get_nodes_Block(node));
166 exchange(node, new_d_Const(get_irn_dbg_info(node),
167 mode_P, tarval_P_from_entity(ent)));
171 } else if (get_irn_op(node) == op_Sel &&
172 is_method_type(get_entity_type(get_Sel_entity(node)))) {
173 entity * ent = get_Sel_entity(node);
174 if (get_irn_op(skip_Proj(get_Sel_ptr(node))) == op_Alloc) {
175 /* We know which method will be called, no dispatch necessary. */
176 assert(get_entity_peculiarity(ent) != description);
177 set_irg_current_block(current_ir_graph, get_nodes_Block(node));
178 exchange (node, copy_const_value(get_atomic_ent_value(ent)));
180 assert(get_entity_peculiarity(ent) != inherited);
181 if (!eset_contains(entities, ent)) {
182 /* Entity noch nicht behandelt. Alle (intern oder extern)
183 * implementierten Methoden suchen, die diese Entity
184 * überschreiben. Die Menge an entity.link speichern. */
185 set_entity_link(ent, get_impl_methods(ent));
186 eset_insert(entities, ent);
188 if (get_entity_link(ent) == NULL) {
189 /* Die Sel-Operation kann nie einen Zeiger auf eine aufrufbare
190 * Methode zurückgeben. Damit ist sie insbesondere nicht
191 * ausführbar und nicht erreichbar. */
192 /* Gib eine Warnung aus wenn die Entitaet eine Beschreibung ist
193 fuer die es keine Implementierung gibt. */
194 if (get_entity_peculiarity(ent) == description) {
195 /* @@@ GL Methode um Fehler anzuzeigen aufrufen! */
196 xprintf("WARNING: Calling method description %I in method %I which has "
197 "no implementation!\n", get_entity_ident(ent),
198 get_entity_ident(get_irg_ent(current_ir_graph)));
200 exchange(node, new_Bad());
203 entity ** arr = get_entity_link(ent);
207 printf("\nCall site "); DDMN(node);
208 printf(" in "); DDME(get_irg_ent(current_ir_graph));
209 printf(" can call:\n");
210 for (i = 0; i < ARR_LEN(arr); i++) {
211 printf(" - "); DDME(arr[i]);
212 printf(" with owner "); DDMT(get_entity_owner(arr[i]));
217 if (ARR_LEN(arr) == 1 && arr[0] != NULL) {
218 /* Die Sel-Operation kann immer nur einen Wert auf eine
219 * interne Methode zurückgeben. Wir können daher die
220 * Sel-Operation durch eine Const- bzw. SymConst-Operation
222 set_irg_current_block(current_ir_graph, get_nodes_Block(node));
223 exchange (node, copy_const_value(get_atomic_ent_value(arr[0])));
231 /* Datenstruktur initialisieren. Zusätzlich werden alle
232 * SymConst-Operationen, die auf interne Methoden verweisen, durch
233 * Const-Operationen ersetzt. */
234 static void sel_methods_init(void) {
236 pmap * ldname_map = pmap_create();
237 assert(entities == NULL);
238 entities = eset_create();
239 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
240 entity * ent = get_irg_ent(get_irp_irg(i));
241 /* Nur extern sichtbare Methode können überhaupt mit SymConst
242 * aufgerufen werden. */
243 if (get_entity_visibility(ent) != local) {
244 pmap_insert(ldname_map, (void *) get_entity_ld_ident(ent), ent);
247 all_irg_walk((irg_walk_func *) sel_methods_walker, NULL, ldname_map);
248 pmap_destroy(ldname_map);
251 /*****************************************************************************/
253 /* Datenstruktur freigeben. */
254 static void sel_methods_dispose(void) {
257 for (ent = eset_first(entities); ent; ent = eset_next(entities)) {
258 entity ** arr = get_entity_link(ent);
262 set_entity_link(ent, NULL);
264 eset_destroy(entities);
269 /* Gibt die Menge aller Methoden zurück, die an diesem Sel-Knoten
270 * zurückgegeben werden können. Die Liste enthält keine doppelten
272 static entity ** get_Sel_arr(ir_node * sel) {
273 static entity ** NULL_ARRAY = NULL;
276 assert(sel && get_irn_op(sel) == op_Sel);
277 ent = get_Sel_entity(sel);
278 assert(is_method_type(get_entity_type(ent))); /* what else? */
279 arr = get_entity_link(ent);
283 /* "NULL" zeigt an, dass keine Implementierung existiert. Dies
284 * kann für polymorphe (abstrakte) Methoden passieren. */
286 NULL_ARRAY = NEW_ARR_F(entity *, 0);
293 static int get_Sel_n_methods(ir_node * sel) {
294 return ARR_LEN(get_Sel_arr(sel));
298 static entity * get_Sel_method(ir_node * sel, int pos) {
299 entity ** arr = get_Sel_arr(sel);
300 assert(pos >= 0 && pos < ARR_LEN(arr));
306 /* --- callee analysis ------------------------------------------------------ */
309 static void callee_ana_node(ir_node * node, eset * methods);
312 static void callee_ana_proj(ir_node * node, long n, eset * methods) {
313 assert(get_irn_mode(node) == mode_T);
314 if (get_irn_link(node) == MARK) {
315 /* already visited */
318 set_irn_link(node, MARK);
320 switch (get_irn_opcode(node)) {
322 /* proj_proj: in einem "sinnvollen" Graphen kommt jetzt ein
323 * op_Tuple oder ein Knoten, der eine "freie Methode"
325 ir_node * pred = get_Proj_pred(node);
326 if (get_irn_link(pred) != MARK) {
327 if (get_irn_op(pred) == op_Tuple) {
328 callee_ana_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, methods);
330 eset_insert(methods, MARK); /* free method -> unknown */
337 callee_ana_node(get_Tuple_pred(node, n), methods);
341 callee_ana_proj(get_Id_pred(node), n, methods);
345 eset_insert(methods, MARK); /* free method -> unknown */
349 set_irn_link(node, NULL);
353 static void callee_ana_node(ir_node * node, eset * methods) {
356 assert((get_irn_mode(node) == mode_P) || is_Bad(node));
357 /* rekursion verhindern */
358 if (get_irn_link(node) == MARK) {
359 /* already visited */
362 set_irn_link(node, MARK);
364 switch (get_irn_opcode(node)) {
366 /* externe Methode (wegen fix_symconst!) */
367 eset_insert(methods, MARK); /* free method -> unknown */
371 /* interne Methode */
372 entity * ent = get_Const_tarval(node)->u.P.ent;
373 assert(ent && is_method_type(get_entity_type(ent)));
374 if (get_entity_visibility(ent) != external_allocated) {
375 assert(get_entity_irg(ent));
376 eset_insert(methods, ent);
378 eset_insert(methods, MARK); /* free method -> unknown */
384 /* polymorphe Methode */
385 for (i = get_Sel_n_methods(node) - 1; i >= 0; --i) {
386 entity * ent = get_Sel_method(node, i);
388 eset_insert(methods, ent);
390 eset_insert(methods, MARK);
399 case iro_Phi: /* Vereinigung */
400 for (i = get_Phi_n_preds(node) - 1; i >= 0; --i) {
401 callee_ana_node(get_Phi_pred(node, i), methods);
406 callee_ana_node(get_Id_pred(node), methods);
410 callee_ana_proj(get_Proj_pred(node), get_Proj_proj(node), methods);
417 eset_insert(methods, MARK); /* free method -> unknown */
421 assert(0 && "invalid opcode or opcode not implemented");
425 set_irn_link(node, NULL);
429 static void callee_walker(ir_node * call, void * env) {
430 if (get_irn_op(call) == op_Call) {
431 eset * methods = eset_create();
433 entity ** arr = NEW_ARR_F(entity *, 0);
434 callee_ana_node(skip_nop(get_Call_ptr(call)), methods);
435 if (eset_contains(methods, MARK)) { /* unknown method */
436 ARR_APP1(entity *, arr, NULL);
438 for (ent = eset_first(methods); ent; ent = eset_next(methods)) {
440 ARR_APP1(entity *, arr, ent);
443 if (ARR_LEN(arr) == 0) {
444 /* Kann vorkommen, wenn der Vorgänger beispielsweise eine
445 * Sel-Operation war, die keine Methoden zurückgeben
446 * konnte. Wir ersetzen die Call-Operation ebenfalls durch
447 * eine Bad-Operation. Die Verlinkung muss wiederhergestellt
449 exchange(call, new_Bad());
451 set_Call_callee_arr(call, ARR_LEN(arr), arr);
454 eset_destroy(methods);
459 /* Bestimmt für jede Call-Operation die Menge der aufrufbaren Methode
460 * und speichert das Ergebnis in der Call-Operation. (siehe
461 * "set_Call_callee"). "sel_methods" wird für den Aufbau benötigt und
462 * muss bereits aufgebaut sein. */
463 static void callee_ana(void) {
465 /* Alle Graphen analysieren. */
466 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
467 irg_walk_graph(get_irp_irg(i), callee_walker, NULL, NULL);
473 /* --- free method analysis ------------------------------------------------- */
476 static void free_mark(ir_node * node, eset * set);
478 static void free_mark_proj(ir_node * node, long n, eset * set) {
479 assert(get_irn_mode(node) == mode_T);
480 if (get_irn_link(node) == MARK) {
481 /* already visited */
484 set_irn_link(node, MARK);
485 switch (get_irn_opcode(node)) {
487 /* proj_proj: in einem "sinnvollen" Graphen kommt jetzt ein
488 * op_Tuple oder ein Knoten, der in "free_ana_walker" behandelt
490 ir_node * pred = get_Proj_pred(node);
491 if (get_irn_link(pred) != MARK && get_irn_op(pred) == op_Tuple) {
492 free_mark_proj(get_Tuple_pred(pred, get_Proj_proj(node)), n, set);
494 /* nothing: da in "free_ana_walker" behandelt. */
500 free_mark(get_Tuple_pred(node, n), set);
504 free_mark_proj(get_Id_pred(node), n, set);
510 /* nothing: Die Operationen werden in "free_ana_walker" selbst
515 assert(0 && "unexpected opcode or opcode not implemented");
518 set_irn_link(node, NULL);
522 static void free_mark(ir_node * node, eset * set) {
524 assert(get_irn_mode(node) == mode_P);
525 if (get_irn_link(node) == MARK) {
526 return; /* already visited */
528 set_irn_link(node, MARK);
529 switch (get_irn_opcode(node)) {
531 entity * ent = get_Sel_entity(node);
532 if (is_method_type(get_entity_type(ent))) {
533 for (i = get_Sel_n_methods(node) - 1; i >= 0; --i) {
534 eset_insert(set, get_Sel_method(node, i));
540 /* nothing: SymConst points to extern method */
543 tarval * val = get_Const_tarval(node);
544 entity * ent = val->u.P.ent;
545 if (ent != NULL && is_method_type(get_entity_type(ent))) {
546 eset_insert(set, ent);
551 for (i = get_Phi_n_preds(node) - 1; i >= 0; --i) {
552 free_mark(get_Phi_pred(node, i), set);
556 free_mark(get_Id_pred(node), set);
559 free_mark_proj(get_Proj_pred(node), get_Proj_proj(node), set);
562 /* nothing: Wird unten behandelt! */
565 set_irn_link(node, NULL);
569 static void free_ana_walker(ir_node * node, eset * set) {
571 if (get_irn_link(node) == MARK) {
572 /* bereits in einem Zyklus besucht. */
575 switch (get_irn_opcode(node)) {
586 /* Sonderbehandlung, da der Funktionszeigereingang natürlich kein
589 set_irn_link(node, MARK);
590 for (i = get_Call_arity(node) - 1; i >= 0; --i) {
591 ir_node * pred = get_Call_param(node, i);
592 if (get_irn_mode(pred) == mode_P) {
593 free_mark(pred, set);
597 /* other nodes: Alle anderen Knoten nehmen wir als Verräter an, bis
598 * jemand das Gegenteil implementiert. */
600 set_irn_link(node, MARK);
601 for (i = get_irn_arity(node) - 1; i >= 0; --i) {
602 ir_node * pred = get_irn_n(node, i);
603 if (get_irn_mode(pred) == mode_P) {
604 free_mark(pred, set);
609 set_irn_link(node, NULL);
613 /* Die Datenstrukturen für sel-Methoden (sel_methods) muß vor dem
614 * Aufruf von "get_free_methods" aufgebaut sein. Die (internen)
615 * SymConst-Operationen müssen in passende Const-Operationen
616 * umgewandelt worden sein, d.h. SymConst-Operationen verweisen immer
617 * auf eine echt externe Methode. */
618 static entity ** get_free_methods(void) {
619 eset * set = eset_create();
621 entity ** arr = NEW_ARR_F(entity *, 0);
623 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
624 ir_graph * irg = get_irp_irg(i);
625 entity * ent = get_irg_ent(irg);
626 /* insert "external visible" methods. */
627 if (get_entity_visibility(ent) != local) {
628 eset_insert(set, ent);
630 irg_walk_graph(irg, NULL, (irg_walk_func *) free_ana_walker, set);
632 /* Hauptprogramm ist auch frei, auch wenn es nicht "external
634 if(get_irp_main_irg()) {
635 eset_insert(set, get_irg_ent(get_irp_main_irg()));
637 for (ent = eset_first(set); ent; ent = eset_next(set)) {
638 ARR_APP1(entity *, arr, ent);
645 void cgana(int *length, entity ***free_methods) {
646 entity ** free_meths;
650 free_meths = get_free_methods();
652 sel_methods_dispose();
654 /* Convert the flexible array to an array that can be handled
656 *length = ARR_LEN(free_meths);
657 *free_methods = (entity **)malloc(sizeof(entity *) * (*length));
658 for (i = 0; i < (*length); i++) (*free_methods)[i] = free_meths[i];
659 DEL_ARR_F(free_meths);
662 /* Optimize the address expressions passed to call nodes.
663 * Alle SymConst-Operationen, die auf interne Methoden verweisen,
664 * werden durch Const-Operationen ersetzt.
665 * Sel Knoten deren entitaeten nicht ueberschrieben werden, werden
666 * durch Const ersetzt.
667 * Sel Knoten, fuer die keine Implementierung existiert, werden
668 * durch Bad ersetzt. */
669 void opt_call_addrs(void) {
671 sel_methods_dispose();
674 pmap * ldname_map = pmap_create();
675 assert(entities == NULL);
676 entities = eset_create();
677 for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
678 entity * ent = get_irg_ent(get_irp_irg(i));
679 /* Nur extern sichtbare Methoden können überhaupt mit SymConst
680 * aufgerufen werden. */
681 if (get_entity_visibility(ent) != local) {
682 pmap_insert(ldname_map, (void *) get_entity_ld_ident(ent), ent);
685 all_irg_walk((irg_walk_func *) sel_methods_walker, NULL, ldname_map);
686 pmap_destroy(ldname_map);