nsz Git - libfirm/blob - ir/ana/rta.c

   1 /* -*- c -*- */
   2
   3 /*
   4  * Project:     libFIRM
   5  * File name:   ir/ana/rta.c
   6  * Purpose:     Intraprozedural analyses to improve the call graph estimate.
   7  * Author:      Florian
   8  * Modified by:
   9  * Created:     09.06.2002
  10  * CVS-ID:      $$
  11  * Copyright:   (c) 1999-2004 Universität Karlsruhe
  12  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  13  */
  14
  15 /**
  16  * Intraprozedurale Analyse zur Abschätzung der Aufrufrelation. Es
  17  * die Menge der instantiierten Klassen bestimmt, und daraus existierende Methoden
  18  * bestimmt.
  19  */
  20
  21 #ifdef HAVE_CONFIG_H
  22 # include <config.h>
  23 #endif
  24
  25 #include "rta.h"
  26
  27 #include <stdlib.h>
  28 #include "cgana.h"              /* get_implementation */
  29
  30 #include "irnode_t.h"
  31 #include "irprog.h"
  32
  33 #include "eset.h"
  34 /* #include "pmap.h" */
  35 /* #include "array.h" */
  36 #include "irgwalk.h"
  37 /* #include "ircons.h" */
  38 /* #include "irgmod.h" */
  39 /* #include "irflag_t.h" */
  40
  41 /* #include "dbginfo_t.h" */
  42
  43 # define TRUE 1
  44 # define FALSE 0
  45
  46 /* base data */
  47 static eset *_live_classes   = NULL;
  48 static eset *_live_fields    = NULL;
  49 static eset *_called_methods = NULL;
  50
  51 /* cache computed results */
  52 static eset *_live_graphs    = NULL;
  53 static eset *_dead_graphs    = NULL;
  54
  55 /* now the meat */
  56
  57 static void rta_act (ir_node *node, void *env)
  58 {
  59   opcode op = get_irn_opcode (node);
  60
  61   if (iro_Call == op) {
  62     entity *ent = NULL;
  63
  64     ir_node *ptr = get_Call_ptr (node);
  65     // TODO: test:  ptr.op == Const
  66
  67     if (iro_Sel == get_irn_opcode (ptr)) {
  68       ent = get_Sel_entity (ptr);
  69     }
  70
  71     if (ent) {
  72       eset_insert (_called_methods, ent);
  73     }
  74   } else if (iro_Load  == op) {
  75     ir_node *ptr = get_Load_ptr (node);
  76     entity  *ent = NULL;
  77
  78     if (iro_Sel == get_irn_opcode (ptr)) {
  79       ent = get_Sel_entity (ptr);
  80     }
  81     if (ent) {
  82       eset_insert (_live_fields, ent);
  83     }
  84   } else  if (iro_Store == op) {
  85     ir_node *ptr = get_Store_ptr (node);
  86     entity  *ent = NULL;
  87
  88     if (iro_Sel == get_irn_opcode (ptr)) {
  89       ent = get_Sel_entity (ptr);
  90     }
  91     if (ent) {
  92       eset_insert (_live_fields, ent);
  93     }
  94   } else if (iro_Alloc == op) {
  95     type *type = get_Alloc_type (node);
  96     eset_insert (_live_classes, type);
  97   }
  98 }
  99
 100 static void rta_fill_graph (ir_graph* graph)
 101 {
 102   if (NULL != graph) {
 103     if (NULL != get_irg_end_block (graph)) {
 104       irg_walk (get_irg_end_block (graph), rta_act, NULL, NULL);
 105     }
 106   }
 107 }
 108
 109 static void rta_fill_all ()
 110 {
 111   int i;
 112   int old_ip_view = interprocedural_view;
 113
 114   interprocedural_view = 0;
 115   for (i = 0; i < get_irp_n_irgs(); i++) {
 116     rta_fill_graph (get_irp_irg (i));
 117   }
 118   interprocedural_view = old_ip_view;
 119 }
 120
 121 static int is_call_target (entity *method)
 122 {
 123   int is_target = FALSE;
 124   int i;
 125   int n_over;
 126
 127   /* The method could be the target of a polymorphic call if it is
 128      called or if it overrides a method that is called. */
 129
 130   if (eset_contains (_called_methods, method)) {
 131     return (TRUE);
 132   }
 133
 134   n_over = get_entity_n_overwrittenby (method);
 135   for (i = 0; !is_target && (i < n_over); i ++) {
 136     entity *over = get_entity_overwrittenby (method, i);
 137     is_target |= is_call_target (over);
 138   }
 139
 140   return (is_target);
 141 }
 142
 143
 144 static ir_graph *get_implementing_graph (entity *method)
 145 {
 146   ir_graph *graph = get_entity_irg (method);
 147
 148   if (NULL == graph) {
 149     int i;
 150     int n_over = get_entity_n_overwrites (method);
 151
 152     for (i = 0; (NULL == graph) && (i < n_over); i ++) {
 153       entity *over = get_entity_overwrites (method, i);
 154       graph = get_implementing_graph (over);
 155     }
 156   }
 157
 158   assert (graph && "no graph");
 159
 160   return (graph);
 161 }
 162
 163 static int has_live_call (entity *method, ir_graph *graph)
 164 {
 165   int has_call = FALSE;
 166   int i, n_over;
 167
 168   if (get_irg_ent (graph) != method) {
 169     return (FALSE);
 170   }
 171
 172   if (is_call_target (method)) {
 173     return (TRUE);
 174   }
 175
 176   n_over = get_entity_n_overwrittenby (method);
 177   for (i = 0; !has_call && (i < n_over); i ++) {
 178     entity *over = get_entity_overwrittenby(method, i);
 179     has_call |= has_live_call (over, graph);
 180   }
 181
 182   return (has_call);
 183 }
 184
 185 static int has_graph (type *clazz, ir_graph *graph)
 186 {
 187   int has_the_graph = FALSE;
 188   int i;
 189   int n_sub;
 190
 191   if (eset_contains (_live_classes, clazz)) {
 192     int n_meth = get_class_n_members (clazz);
 193
 194     for (i = 0; i < n_meth; i ++) {
 195       entity *member = get_class_member (clazz, i);
 196       if (is_method_type (get_entity_type (member))) {
 197         ir_graph *impl = get_entity_irg (member);
 198
 199         if (impl == graph) {
 200           return (TRUE);
 201         }
 202       } /* is_method */
 203     } /* all methods */
 204   } /* _live_classes.contains (clazz) */
 205
 206   n_sub = get_class_n_subtypes (clazz);
 207   for (i = 0; !has_the_graph && (i < n_sub); i ++) {
 208     type *sub = get_class_subtype (clazz, i);
 209
 210     has_the_graph |= has_graph (sub, graph);
 211   }
 212
 213   return (has_the_graph);
 214 }
 215
 216 static int has_live_class (entity *method, ir_graph *graph)
 217 {
 218   int has_class = FALSE;
 219   int i;
 220   int n_over;
 221   type *clazz;
 222
 223   if (get_implementing_graph (method) != graph) {
 224     return (FALSE);
 225   }
 226
 227   clazz = get_entity_owner (method);
 228   if (has_graph (clazz, graph)) {
 229     return (TRUE);
 230   }
 231
 232   n_over = get_entity_n_overwrittenby (method);
 233   for (i = 0; !has_class && (i < n_over); i ++) {
 234     entity *over = get_entity_overwrittenby (method, i);
 235     has_class |= has_live_class (over, graph);
 236   }
 237
 238   return (has_class);
 239 }
 240
 241 static int rta_check (ir_graph *graph)
 242 {
 243   return (rta_is_alive_graph (graph));
 244 }
 245
 246
 247 void rta_init ()
 248 {
 249   _live_classes   = eset_create ();
 250   _live_fields    = eset_create ();
 251   _called_methods = eset_create ();
 252
 253   _live_graphs = eset_create ();
 254   _dead_graphs = eset_create ();
 255
 256   /*
 257    * shold be:
 258    * rta_fill_queue ()
 259    */
 260   if (get_irp_main_irg ()) {
 261     eset_insert (_live_graphs, get_irp_main_irg ());
 262   }
 263
 264   rta_fill_all ();
 265 }
 266
 267 void rta_cleanup ()
 268 {
 269   int i;
 270   int n_live_graphs = 0;
 271   int n_graphs = get_irp_n_irgs();
 272
 273   for (i = 0; i < n_graphs; i++) {
 274     ir_graph *graph = get_irp_irg(i);
 275
 276     if (rta_check (graph)) {
 277       char *name = NULL;
 278
 279       n_live_graphs ++;
 280       name = get_entity_name (get_irg_ent (graph));
 281
 282       fprintf (stdout, "LIVE  %s\n", name);
 283     }
 284   }
 285
 286   fprintf (stdout, "RES   %s: %i graphs, %i live\n", __FUNCTION__, n_graphs, n_live_graphs);
 287
 288   if (_live_classes) {
 289     eset_destroy (_live_classes);
 290     _live_classes = NULL;
 291   }
 292
 293   if (_live_fields) {
 294     eset_destroy (_live_fields);
 295     _live_fields = NULL;
 296   }
 297
 298   if (_called_methods) {
 299     eset_destroy (_called_methods);
 300     _called_methods = NULL;
 301   }
 302
 303   if (_live_graphs) {
 304     eset_destroy (_live_graphs);
 305     _live_graphs = NULL;
 306   }
 307
 308   if (_dead_graphs) {
 309     eset_destroy (_dead_graphs);
 310     _dead_graphs = NULL;
 311   }
 312 }
 313
 314 int  rta_is_alive_class  (type   *clazz)
 315 {
 316   return (eset_contains (_live_classes, clazz));
 317 }
 318
 319 int  rta_is_alive_graph (ir_graph *graph)
 320 {
 321   if (eset_contains (_live_graphs, graph)) {
 322     return (TRUE);
 323   }
 324
 325   if (eset_contains (_dead_graphs, graph)) {
 326     return (FALSE);
 327   }
 328
 329   entity *meth = get_irg_ent (graph);
 330
 331   if (has_live_call (meth, graph) && has_live_class (meth, graph)) {
 332     eset_insert (_live_graphs, graph);
 333
 334     return (TRUE);
 335   } else {
 336     eset_insert (_dead_graphs, graph);
 337
 338     return (FALSE);
 339   }
 340 }
 341
 342 int  rta_is_alive_field  (entity *field)
 343 {
 344   return (eset_contains (_live_fields, field));
 345 }
 346
 347
 348
 349 /*
 350  * $Log$
 351  * Revision 1.3  2004/06/12 17:09:46  liekweg
 352  * RTA works, outedges breaks.  "Yay." --flo
 353  *
 354  * Revision 1.2  2004/06/11 18:25:39  liekweg
 355  * Added todo
 356  *
 357  * Revision 1.1  2004/06/11 18:24:18  liekweg
 358  * Added RTA --flo
 359  *
 360  */