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

   1 /* -*- c -*- */
   2
   3 /*
   4  * Project:     libFIRM
   5  * File name:   ir/ana/ecg.c
   6  * Purpose:     Extended Call Graph
   7  * Author:      Florian
   8  * Modified by:
   9  * Created:     14.09.2004
  10  * CVS-ID:      $$
  11  * Copyright:   (c) 1999-2004 Universität Karlsruhe
  12  * Licence:     This file is protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  13  */
  14
  15 #ifdef HAVE_CONFIG_H
  16 # include <config.h>
  17 #endif
  18
  19 /**
  20    Erweiterter Aufrufgraph.
  21  */
  22
  23 #include "irnode.h"
  24 #include "pmap.h"
  25 /* #include "eset.h" */
  26 #include "irgwalk.h"
  27 #include "irgmod.h"
  28 #include "irvrfy.h"
  29 #include "trvrfy.h"
  30 #include "xmalloc.h"
  31
  32 # define TRUE 1
  33 # define FALSE 0
  34
  35 # include "ecg.h"
  36
  37 /*
  38   data structures
  39 */
  40
  41 /* Lists, err, Sets */
  42 typedef struct lset_entry
  43 {
  44   void *data;
  45   struct lset_entry *next;
  46 } lset_entry_t;
  47
  48 typedef struct lset
  49 {
  50   lset_entry_t *first;
  51   lset_entry_t *last;           /* useful for lset_append */
  52   lset_entry_t *curs;           /* for lset_first/lset_next */
  53   int n_entries;
  54 } lset_t;
  55
  56
  57 typedef enum typalise_kind_enum {
  58   type_invalid = 0,             /* invalid (only set at deletion time) */
  59   type_exact = 1,               /* this and only this type (res.type) */
  60   type_types = 2,               /* these types (res.types) */
  61   type_type  = 3                /* this type and sub types (res.type) */
  62 } typalise_kind;
  63
  64 typedef struct typalise
  65 {
  66   typalise_kind kind;
  67   union
  68   {
  69     type *type;                 /* for kind == kind_exact and kind == kind_type */
  70     lset_t *types;              /* for kind == kind_types */
  71   } res;
  72   int id;
  73 } typalise_t;
  74
  75 /*
  76    le flag
  77 */
  78 static int verbose     = 0;
  79 static int do_typalise = 0;
  80
  81 /*
  82    globals
  83 */
  84
  85 /* mapping from method graphs (callR) to method graphs (lset_ts of callEds) */
  86 /* static pmap *calls; */
  87 static pmap *graph_infos;
  88
  89 /** Counters for ecg_ecg and friends */
  90 static long _graphs = 0;
  91 static long _calls  = 0;
  92
  93 static int _depth = 0;
  94 static int _max_depth = 0;
  95
  96 static int _max_callEds = 0;
  97 static entity* _max_callEds_callR = NULL;
  98
  99 static long ta_id = 0;
 100
 101 /* ====================
 102    Lists, err, Sets
 103  ==================== */
 104 /* create a new lset */
 105 static lset_t *lset_create ()
 106 {
 107   lset_t *lset = xmalloc (sizeof (lset_t));
 108
 109   return (lset);
 110 }
 111
 112 /* check whether the lset contains an entry for the given data */
 113 static int lset_contains (lset_t *lset, void *data)
 114 {
 115   lset_entry_t *entry = lset->first;
 116
 117   while (NULL != entry) {
 118     if (data == entry->data) {
 119       return (TRUE);
 120     }
 121
 122     entry = entry->next;
 123   }
 124
 125   return (FALSE);
 126 }
 127
 128 /* check whether the given lset is empty */
 129 static int lset_empty (lset_t *lset)
 130 {
 131   return (NULL == lset->first);
 132 }
 133
 134
 135 /* insert the data into the lset (unless there's an entry for it
 136    already) */
 137 static void lset_insert (lset_t *lset, void *data)
 138 {
 139   if (! lset_contains (lset, data)) {
 140     lset_entry_t *entry = xmalloc (sizeof (lset_entry_t));
 141     entry->data = data;
 142     entry->next = lset->first;
 143     lset->first = entry;
 144
 145     if (NULL == lset->last) {
 146       lset->last = entry;
 147     }
 148
 149     lset->n_entries ++;
 150   }
 151 }
 152
 153 /* insert all entries from src into tgt */
 154 static void lset_insert_all (lset_t *tgt, lset_t *src)
 155 {
 156   lset_entry_t *curs = src->first;
 157
 158   while (NULL != curs) {
 159     lset_insert (tgt, curs->data);
 160
 161     curs = curs->next;
 162   }
 163 }
 164
 165 /* append src to tgt. src is deallocated. */
 166 static void lset_append (lset_t *tgt, lset_t *src)
 167 {
 168   assert (! tgt->last->next);
 169
 170   tgt->last->next = src->first;
 171   tgt->last = src->last;
 172   tgt->n_entries += src->n_entries;
 173
 174   memset (src, 0x00, sizeof (lset_t));
 175   free (src);
 176 }
 177
 178 /* remove the entry for the given data element from the lset. return
 179    TRUE iff it was on the list in the first place, FALSE else */
 180 static int lset_remove (lset_t *lset, void *data)
 181 {
 182   lset_entry_t *entry = lset->first;
 183   lset_entry_t *prev = NULL;
 184
 185   while (NULL != entry) {
 186     if (data == entry->data) {
 187       /* ok, dike it out */
 188
 189       if (NULL == prev) { /* ok, it's lset->first that needs diking */
 190         lset->first = entry->next;
 191       } else {
 192         prev->next = entry->next;
 193       }
 194
 195       memset (entry, 0x00, sizeof (lset_entry_t));
 196       free (entry);
 197
 198       lset->n_entries --;
 199
 200       return (TRUE);
 201     }
 202
 203     prev = entry;
 204     entry = entry->next;
 205   }
 206
 207   return (FALSE);
 208 }
 209
 210 /* prepare the given lset for an iteration. return the first element. */
 211 static void *lset_first (lset_t *lset)
 212 {
 213   lset->curs = lset->first;
 214
 215   if (lset->first) {
 216     return (lset->first->data);
 217   } else {
 218     return (NULL);
 219   }
 220 }
 221
 222 /* after calling lset_first, get the next element, if applicable, or
 223    NULL */
 224 static void *lset_next (lset_t *lset)
 225 {
 226   lset->curs = lset->curs->next;
 227
 228   if (lset->curs) {
 229     return (lset->curs->data);
 230   } else {
 231     return (NULL);
 232   }
 233 }
 234
 235 /* say how many entries there are in the given lset */
 236 static int lset_n_entries (lset_t *lset)
 237 {
 238   return (lset->n_entries);
 239 }
 240
 241 /* deallocate the lset and all of its entries */
 242 static void lset_destroy (lset_t *lset)
 243 {
 244   lset_entry_t *curs = lset->first;
 245
 246   while (NULL != curs) {
 247     lset_entry_t *tmp = curs->next;
 248
 249     memset (curs, 0x00, sizeof (lset_entry_t));
 250     free (curs);
 251
 252     curs = tmp;
 253   }
 254
 255   memset (lset, 0x00, sizeof (lset_t));
 256   free (lset);
 257 }
 258
 259 /* ====================
 260   Typalize Ptr
 261  ==================== */
 262 /**
 263    Find out whether the given clazz uses the given implementation of a
 264    method.  Presumably, this is because clazz inherits the graph as
 265    the implementation for a method.
 266 */
 267 static int uses_graph (type *clazz, entity *meth, ir_graph *graph)
 268 {
 269   type *g_clazz = get_entity_owner (meth);
 270
 271   if (g_clazz == clazz) {
 272     return (TRUE);
 273   }
 274
 275   if (peculiarity_existent == get_entity_peculiarity (meth)) {
 276     ir_graph *g_graph = get_entity_irg (meth);
 277
 278     if (g_graph != graph) {
 279       return (FALSE);
 280     }
 281   }
 282
 283   /* else inherited or description */
 284   int use = FALSE;
 285   int i;
 286   int n_over = get_entity_n_overwrittenby (meth); /* DOWN-wards */
 287
 288   for (i = 0; (i < n_over) && (!use); i ++) {
 289     entity *over = get_entity_overwrittenby (meth, i);
 290
 291     use |= uses_graph (clazz, over, graph);
 292   }
 293
 294   return (use);
 295 }
 296
 297
 298 /**
 299    Find out whether otype is a subtype of stype.
 300    Return non-zero iff otype is a subtype of stype.
 301 */
 302 static int is_subtype (type *otype, type *stype)
 303 {
 304   int n_sub = get_class_n_subtypes (stype);
 305   int is_sub = FALSE;
 306   int i;
 307
 308   if (otype == stype) {
 309     return (TRUE);
 310   }
 311
 312   for (i = 0; (!is_sub) && (i < n_sub); i ++) {
 313     type *sub = get_class_subtype (stype, i);
 314
 315     is_sub |= is_subtype (otype, sub);
 316   }
 317
 318
 319   return (is_sub);
 320 }
 321
 322 /**
 323     Compute the closure of all subtypes of otype (including otype
 324     itself)
 325 */
 326 static void _collect_subtypes (type *otype, lset_t *set)
 327 {
 328   lset_insert (set, otype);
 329
 330   int n_sub = get_class_n_subtypes (otype);
 331   int i;
 332
 333   for (i = 0; i < n_sub; i ++) {
 334     type *sub = get_class_subtype (otype, i);
 335
 336     _collect_subtypes (sub, set);
 337   }
 338 }
 339
 340 static lset_t *subtype_closure (type *otype)
 341 {
 342   lset_t *set = lset_create ();
 343
 344   _collect_subtypes (otype, set);
 345
 346   return (set);
 347 }
 348
 349 /**
 350    Helper method for get_owner_types
 351 */
 352 static void _collect_owner_types (entity *method, ir_graph *graph, lset_t *tps)
 353 {
 354   /* search DOWNwards in clazz hierarchy */
 355
 356   if ((peculiarity_description == get_entity_peculiarity (method)) ||
 357       (peculiarity_inherited   == get_entity_peculiarity (method))) {
 358     lset_insert (tps, get_entity_owner (method));
 359   } else if (peculiarity_existent == get_entity_peculiarity (method)) {
 360     ir_graph *ex_graph = get_entity_irg (method);
 361
 362     if ((NULL == ex_graph) || (ex_graph == graph)) {
 363       /* wtf? they define the same graph again? well, whatever: */
 364       lset_insert (tps, get_entity_owner (method));
 365     } else {
 366       /* aha: they define a new graph. can't have that, so bail out */
 367       return;
 368     }
 369   }
 370
 371   int n_over = get_entity_n_overwrittenby (method);
 372   int i;
 373
 374   for (i = 0; i < n_over; i ++) {
 375     entity *ometh = get_entity_overwrittenby (method, i);
 376
 377     _collect_owner_types (ometh, graph, tps);
 378   }
 379 }
 380
 381
 382 /**
 383    Collect all classes that use the given implementation of a method.
 384 */
 385 static lset_t *get_owner_types (ir_graph *graph)
 386 {
 387   lset_t *tps = lset_create ();
 388   entity *meth = get_irg_entity (graph);
 389
 390   _collect_owner_types (meth, graph, tps);
 391
 392   return (tps);
 393 }
 394
 395
 396 /**
 397    Convenience funcs to create a typalise_t
 398 */
 399 static typalise_t *ta_exact (type *tp)
 400 {
 401   typalise_t *ta = (typalise_t*) xmalloc (sizeof (typalise_t));
 402   ta->kind = type_exact;
 403   ta->res.type = tp;
 404   ta->id = ta_id ++;
 405
 406   assert (is_class_type (tp));
 407
 408   return (ta);
 409 }
 410
 411 static typalise_t *ta_types (lset_t *set)
 412 {
 413   typalise_t *ta = (typalise_t*) xmalloc (sizeof (typalise_t));
 414   ta->kind = type_types;
 415   ta->res.types = set;
 416   ta->id = ta_id ++;
 417
 418   return (ta);
 419 }
 420
 421 static typalise_t *ta_type (type *tp)
 422 {
 423   typalise_t *ta = (typalise_t*) xmalloc (sizeof (typalise_t));
 424   ta->kind = type_type;
 425   ta->res.type = tp;
 426   ta->id = ta_id ++;
 427
 428   assert (is_class_type (tp));
 429
 430   return (ta);
 431 }
 432
 433 static void ta_delete (typalise_t *ta)
 434 {
 435   if (type_types == ta->kind) {
 436     lset_destroy (ta->res.types);
 437     ta->res.types = NULL;
 438   } else {
 439     ta->res.type = NULL;
 440   }
 441
 442   ta->kind = type_invalid;
 443
 444   free (ta);
 445 }
 446
 447 /**
 448     Join 'one' and 'two'; both args are deallocated, result is freshly
 449     allocated.
 450 */
 451 static typalise_t *ta_join (typalise_t *one, typalise_t *two)
 452 {
 453   typalise_t *res = NULL;
 454
 455   switch (one->kind) {
 456   case (type_exact): {
 457     switch (two->kind) {
 458     case (type_exact): {
 459       if (one->res.type == two->res.type) {
 460         res = one;
 461       } else {
 462         lset_t *set = lset_create ();
 463         lset_insert (set, one->res.type);
 464         lset_insert (set, two->res.type);
 465         res = ta_types (set);
 466
 467         ta_delete (one);
 468       }
 469
 470       ta_delete (two);
 471     } break;
 472     case (type_types): {
 473       lset_insert (two->res.types, one->res.type);
 474       ta_delete (one);
 475
 476       res = two;
 477     } break;
 478     case (type_type): {
 479       if (is_subtype (one->res.type, two->res.type)) {
 480         ta_delete (one);
 481         res = two;
 482       } else {
 483         lset_t *closure = subtype_closure (two->res.type);
 484         lset_insert (closure, one->res.type);
 485
 486         ta_delete (two);
 487
 488         res = one;
 489       }
 490     } break;
 491     }
 492   } break;
 493   case (type_types): {
 494     switch (two->kind) {
 495     case (type_exact): {
 496       res = ta_join (two, one);
 497     } break;
 498     case (type_types): {
 499       lset_insert_all (one->res.types, two->res.types);
 500       ta_delete (two);
 501
 502       res = one;
 503     } break;
 504     case (type_type): {
 505       lset_t *closure = subtype_closure (two->res.type);
 506       lset_append (one->res.types, closure);
 507
 508       ta_delete (two);
 509
 510       res = one;
 511     } break;
 512     }
 513   } break;
 514   case (type_type): {
 515     switch (two->kind) {
 516     case (type_exact): {
 517       res = ta_join (two, one);
 518     } break;
 519     case (type_types): {
 520       res = ta_join (two, one);
 521     } break;
 522     case (type_type): {
 523       type *one_type = one->res.type;
 524       type *two_type = two->res.type;
 525
 526       if (is_subtype (one_type, two_type)) {
 527         ta_delete (one);
 528         res = two;
 529       } else if (is_subtype (two_type, one_type)) {
 530         ta_delete (two);
 531         res = one;
 532       } else {
 533         lset_t *one_closure = subtype_closure (one->res.type);
 534         lset_t *two_closure = subtype_closure (two->res.type);
 535
 536         lset_append (one_closure, two_closure);
 537
 538         ta_delete (two);
 539         ta_delete (one);
 540
 541         res = ta_types (one_closure);
 542       }
 543     } break;
 544     }
 545   } break;
 546   }
 547
 548   assert (res && "no result");
 549
 550   return (res);
 551 }
 552
 553
 554 static const char *ta_name (typalise_t *ta)
 555 {
 556 # define BUF_SIZE 1024
 557   static char buf [BUF_SIZE];
 558
 559   int len = sprintf (buf, "[%d] ", ta->id);
 560
 561   switch (ta->kind) {
 562   case (type_exact): {
 563     len += sprintf (buf+len, "only ");
 564     strncat (buf, get_type_name (ta->res.type), BUF_SIZE);
 565   } break;
 566   case (type_types): {
 567     len += sprintf (buf+len, "one_of ");
 568
 569     type *iter = lset_first (ta->res.types);
 570
 571     int size = BUF_SIZE - len - 1;
 572     while ((NULL != iter) && (0 < size)) {
 573       char *dest = strncat (buf, get_type_name (iter), size);
 574       size = (dest - buf);
 575
 576       iter = lset_next (ta->res.types);
 577     }
 578   } break;
 579   case (type_type): {
 580     len += sprintf (buf+len, "poly ");
 581     strncat (buf, get_type_name (ta->res.type), BUF_SIZE);
 582   } break;
 583   }
 584
 585   return (buf);
 586 # undef BUF_SIZE
 587 }
 588
 589 /**
 590    Check whether the given typalise_t includes the given type.
 591 */
 592 static int ta_supports (typalise_t *ta, ir_graph *graph)
 593 {
 594   switch (ta->kind) {
 595   case (type_exact): {
 596     int res = FALSE;
 597     lset_t *tps = get_owner_types (graph);
 598
 599     if (lset_contains (tps, ta->res.type)) {
 600       res = TRUE;
 601     }
 602
 603     lset_destroy (tps);
 604
 605     return (res);
 606   }
 607   case (type_type): {
 608     entity *meth = get_irg_entity (graph);
 609     type *tp = get_entity_owner (meth);
 610     int res = is_subtype (tp, ta->res.type);
 611
 612     if (res) {
 613       return (TRUE);
 614     } else {
 615       res = uses_graph (ta->res.type, meth, graph);
 616     }
 617
 618     return (res);
 619   }
 620   case (type_types): {
 621     type *tp = get_entity_owner (get_irg_entity (graph));
 622
 623     return (lset_contains (ta->res.types, tp));
 624   }
 625   }
 626
 627   assert (0 && "invalid ta");
 628 }
 629
 630
 631 /**
 632    Given a set of graphs and a typalise_t,  return the method(s) in
 633    the set that are supported by the typalise_t.  Also, deallocates
 634    the given set.
 635 */
 636 static lset_t *filter_for_ta (lset_t *set, typalise_t *ta)
 637 {
 638   lset_t *res = lset_create ();
 639   ir_graph *curs = (ir_graph*) lset_first (set);
 640
 641   while (NULL != curs) {
 642     if (ta_supports (ta, curs)) {
 643       lset_insert (res, curs);
 644     }
 645
 646     curs = lset_next (set);
 647   }
 648
 649   lset_destroy (set);
 650
 651   return (res);
 652 }
 653
 654
 655 /**
 656    Return a list containing all types of 'set' which are a subtype of 'type'.
 657 */
 658 static lset_t *filter_for_type (lset_t *set, type *stype)
 659 {
 660   type *curs = (type*) lset_first (set);
 661   lset_t *lset = lset_create ();
 662
 663   while (NULL != curs) {
 664     if (is_subtype (curs, stype)) {
 665       lset_insert (lset, curs);
 666     }
 667
 668     curs = lset_next (set);
 669   }
 670
 671   return (lset);
 672 }
 673
 674 /**
 675     Find an approximation to the given node's value's types
 676 */
 677 static typalise_t *typalise (ir_node*);
 678
 679 /**
 680     Find an approximation to the given proj node's value's types
 681 */
 682 static typalise_t *typalise_proj (ir_node *proj)
 683 {
 684   typalise_t *res = NULL;
 685   ir_node *proj_in = get_Proj_pred (proj);
 686
 687   if (iro_Proj  == get_irn_opcode (proj_in)) {
 688     /* fprintf (stdout, "\tProj (Proj)\n"); */
 689
 690     proj_in = get_Proj_pred (proj_in);
 691     if (iro_Start == get_irn_opcode (proj_in)) {
 692       long n = get_Proj_proj (proj);
 693       if (1 == n) {
 694         /* yay proj this */
 695         ir_graph *graph = get_irn_irg (proj);
 696         entity   *meth  = get_irg_entity (graph);
 697         type     *tp    = get_entity_owner (meth);
 698
 699         /* res = ta_exact (tp); */
 700         res = ta_type (tp);     /* TODO */
 701       } else {
 702         /* ugh proj arg */
 703         /* hey, even 'filtering' this NULL by the select of the actual
 704            call is probably as "precise" as anything: */
 705         return (NULL);
 706       }
 707     } else if (iro_Call == get_irn_opcode (proj_in)) {
 708       /* call result ... 'whatever' */
 709       ir_node *call_ptr = get_Call_ptr (proj_in);
 710
 711       res = typalise (call_ptr);
 712     } else {
 713       fprintf (stdout, "\n Proj(Proj(%s)) not handled\n",
 714                get_op_name (get_irn_op (proj_in)));
 715       assert (0);
 716     }
 717   } else {
 718     opcode op = get_irn_opcode (proj_in);
 719     if ((iro_Load != op) && (iro_Alloc != op) && (iro_Call != op)) {
 720       fprintf (stdout, "\n Proj(%s) not handled\n",
 721                get_op_name (get_irn_op (proj_in)));
 722       assert (0);
 723     }
 724     res = typalise (proj_in);      /* everything else */
 725     /* Proj(Load), Proj(New), Proj(Call) */
 726   }
 727
 728   return (res);
 729 }
 730
 731
 732 /**
 733    For the given ptr, do a quick check about what (class) types may be
 734    brought along on it.
 735 */
 736 static typalise_t *typalise (ir_node *node)
 737 {
 738   opcode op = get_irn_opcode (node);
 739   typalise_t *res = NULL;
 740
 741   switch (op) {
 742   case (iro_Cast): {
 743     typalise_t *ta = NULL;
 744     type *tp = get_Cast_type (node);
 745
 746     if (is_pointer_type (tp)) {
 747       tp = get_pointer_points_to_type (tp);
 748     }
 749     assert (is_class_type (tp));
 750
 751     ta = typalise (get_Cast_op (node));
 752
 753     if (NULL == ta) {           /* no type found */
 754       ta = ta_type (tp);
 755     } else if (type_exact == ta->kind) { /* one type found */
 756       /* nothing (maybe check cast? */
 757     } else if (type_type == ta->kind) { /* some types found */
 758       if (is_subtype (tp, ta->res.type)) {
 759         ta->res.type = tp;     /* assume cast is correct */
 760       } else {
 761         /* should assert (is_subtype (ta->res.type, tp)) */
 762       }
 763     } else if (type_types == ta->kind) {
 764       lset_t *ftp = filter_for_type (ta->res.types, tp);
 765       lset_destroy (ta->res.types);
 766       ta->res.types = ftp;
 767     }
 768
 769     res = ta;
 770   } break;
 771
 772   case (iro_Proj): {
 773     res = typalise_proj (node);
 774   } break;
 775
 776   case (iro_Load): {
 777     /* presumably it's call(load(ptr)) we're analyzing. */
 778     ir_node *load_ptr = get_Load_ptr (node);
 779
 780     res = typalise (load_ptr);
 781   } break;
 782
 783   case (iro_Sel): {
 784     /* FILTER */
 785     /* it's call(sel(ptr)) or load(sel(ptr)) */
 786     entity *ent = get_Sel_entity (node);
 787     type *tp = get_entity_type (ent);
 788
 789     if (is_method_type (tp)) {
 790       tp = get_entity_type (ent);
 791       tp = get_method_res_type (tp, 0);
 792
 793       if (is_pointer_type (tp)) {
 794         tp = get_pointer_points_to_type (tp);
 795       }
 796
 797       res = ta_type (tp);
 798     } else if (is_class_type (tp)) {
 799       tp = get_entity_type (ent);
 800
 801       if (is_pointer_type (tp)) {
 802         tp = get_pointer_points_to_type (tp);
 803       }
 804
 805       res = ta_type (tp);
 806     } else if (is_pointer_type (tp)) {
 807       tp = get_pointer_points_to_type (tp);
 808       res = ta_type (tp);
 809     } else {
 810       assert (0 && "select not handled");
 811     }
 812   } break;
 813
 814   case (iro_Phi): {
 815     int n_ins = get_irn_arity (node);
 816     int i;
 817     ir_node *phi_in = NULL;
 818     typalise_t *ta = NULL;
 819     /* assert (0 && "Do we ever get here?"); */ /* apparently, we do. */
 820
 821     for (i = 0; i < n_ins; i ++) {
 822       phi_in = get_irn_n (node, i);
 823       ta = (NULL == ta) ? typalise (phi_in) : ta_join (ta, typalise (phi_in));
 824     }
 825
 826     res = ta;
 827   } break;
 828
 829   case (iro_Alloc): {
 830     type *type = get_Alloc_type (node);
 831     res = ta_exact (type);
 832   } break;
 833
 834   case (iro_Call): {
 835     /* presumably call(sel(proj(call))) */
 836     ir_node *ptr = get_Call_ptr (node);
 837     entity *meth = NULL;
 838     if (iro_Sel == get_irn_opcode (ptr)) {
 839       meth = get_Sel_entity (ptr);
 840     } else if (iro_SymConst == get_irn_opcode (ptr)) {
 841       if (get_SymConst_kind(ptr) == symconst_addr_ent) {
 842         meth = get_SymConst_entity (ptr);
 843       } else {
 844         meth = NULL;            /* WTF? */
 845       }
 846     }
 847
 848     if (NULL != meth) {
 849       type *tp = get_method_res_type ((type*) meth, 0);
 850       res = ta_type (tp);
 851     } else {
 852       /* could be anything */
 853       /* fprintf (stdout, "meth=(null)"); */
 854       res = NULL;
 855     }
 856
 857     fprintf (stdout, "]\n");
 858
 859   } break;
 860
 861   case (iro_SymConst): {
 862     if (get_SymConst_kind(node) == symconst_type_tag) {
 863       type *tp = get_SymConst_type (node);
 864
 865       res = ta_type (tp);
 866     } else if (get_SymConst_kind (node) == symconst_addr_ent) {
 867       entity *ent = get_SymConst_entity (node);
 868       type *tp = get_entity_type (ent);
 869       tp = get_pointer_points_to_type (tp);
 870       assert (is_class_type (tp));
 871
 872       res = ta_type (tp);       /* can't use ta_exact */
 873     } else {
 874       fprintf (stdout, "can't handle SymConst %s?\n",
 875                get_op_name (get_irn_op (node)));
 876       res = NULL;
 877     }
 878   } break;
 879
 880   /* template:
 881      case (iro_Cast): {}
 882      break;
 883   */
 884
 885   default: {
 886     fprintf (stdout, "what's with %s?\n", get_op_name (get_irn_op (node)));
 887     assert (0);
 888   } break;
 889   }
 890
 891   return (res);
 892 }
 893
 894
 895 /* ====================
 896   CallEd stuff
 897   ==================== */
 898 /**
 899    Append the given callEd to the given callEd info.
 900 */
 901 static callEd_info_t *append_callEd_info (callEd_info_t *ced, ir_graph *callEd)
 902 {
 903   callEd_info_t *nced = (callEd_info_t*) xmalloc (sizeof (sizeof (callEd_info_t)));
 904
 905   nced->callEd = callEd;
 906   nced->prev = ced;
 907
 908   return (nced);
 909 }
 910
 911 /**
 912    Append all callEd methods of the given (call) node to the given graph_info.
 913 */
 914 static void append_calls (graph_info_t *info, ir_node *call, lset_t *callEds)
 915 {
 916   int n_callEds = 0;
 917
 918   call_info_t *cinfo = (call_info_t*) xmalloc (sizeof (call_info_t));
 919
 920   /* setup */
 921   cinfo->call = call;
 922   cinfo->prev = info->calls;
 923   info->calls = cinfo;
 924   cinfo->callEds = NULL;
 925
 926   /* enter */
 927   ir_graph *callEd = lset_first (callEds);
 928   while (callEd) {
 929     cinfo->callEds = append_callEd_info (cinfo->callEds, callEd);
 930
 931     callEd = lset_next (callEds);
 932   }
 933 }
 934
 935 /**
 936    Append the (single) callEd to the given (call) node of the given graph_info.
 937 */
 938 static void append_call (graph_info_t *info, ir_node *call, ir_graph *callEd)
 939 {
 940   call_info_t *cinfo = (call_info_t*) xmalloc (sizeof (call_info_t));
 941
 942   cinfo->call = call;
 943   cinfo->prev = info->calls;
 944   info->calls = cinfo;
 945
 946   cinfo->callEds = append_callEd_info (cinfo->callEds, callEd);
 947 }
 948
 949 /**
 950    Given a method, find the firm graph that implements that method.
 951    Return NULL for abstract and native methods.
 952 */
 953 static ir_graph *_get_implementing_graph (entity *method)
 954 {
 955   ir_graph *graph = NULL;
 956
 957   /* What's up with the fenced out stuff in rta? */
 958   if (peculiarity_existent == get_entity_peculiarity (method)) {
 959     if (visibility_external_allocated == get_entity_visibility (method)) {
 960       /* Todo: native implementation */
 961
 962       return (NULL);
 963     } else {
 964       graph = get_entity_irg (get_SymConst_entity (get_atomic_ent_value (method)));
 965       assert (graph && "no graph");
 966
 967       return (graph);
 968     }
 969   } else if (0 && (peculiarity_description == get_entity_peculiarity (method))) {
 970     /* abstract --- can't find an implementation */
 971     graph = get_entity_irg (method);
 972     assert (!graph && "graph in abstract method");
 973
 974     return (NULL);
 975   } else if ((peculiarity_description == get_entity_peculiarity (method)) ||
 976              (peculiarity_inherited == get_entity_peculiarity (method))) {
 977     /* search UPWARDS */
 978     int i;
 979     int n_over = get_entity_n_overwrites (method);
 980
 981     assert (!graph);
 982
 983     for (i = 0; (NULL == graph) && (i < n_over); i ++) {
 984       entity *over = get_entity_overwrites (method, i);
 985
 986       graph = _get_implementing_graph (over);
 987     }
 988   } else {
 989     assert (0 && "invalid peculiarity");
 990   }
 991
 992
 993   return (graph);
 994 }
 995
 996 /**
 997    Collect all graphs of 'method' in the given set.
 998 */
 999 static void _collect_implementing_graphs (entity *method, lset_t *set)
1000 {
1001   /* search DOWN-wards in clazz hierarchy */
1002   int i;
1003   int n_over = get_entity_n_overwrittenby (method);
1004   ir_graph *graph = get_entity_irg (method);
1005
1006   if (NULL == graph) {
1007     graph = _get_implementing_graph (method);
1008   }
1009
1010   if (graph) {
1011     lset_insert (set, graph);
1012   }
1013
1014   for (i = 0; i < n_over; i ++) {
1015     entity *over = get_entity_overwrittenby (method, i);
1016
1017     _collect_implementing_graphs (over, set);
1018   }
1019 }
1020
1021
1022 /**
1023    Collect all graphs that could possibly be executed when 'method' is called.
1024 */
1025 static lset_t *get_implementing_graphs (entity *method, ir_node *select)
1026 {
1027   lset_t *set = lset_create ();
1028   {
1029     ir_graph *impl = _get_implementing_graph (method);
1030
1031     if (NULL != impl) {
1032       lset_insert (set, impl);
1033     } else {
1034       /* actually, abstract OR native */
1035     }
1036   }
1037
1038   _collect_implementing_graphs (method, set);
1039
1040   if (lset_empty (set)) {
1041     /* then it's a method which is only implemented natively, and we
1042        don' bother to analyse anything */
1043     return (set);
1044   }
1045
1046   void *tmp = lset_first (set);
1047   int n_graphs = lset_n_entries (set);
1048
1049   /* typalise select_in */
1050   if (do_typalise) {
1051     ir_node *select_in = get_Sel_ptr (select);
1052     typalise_t *ta = typalise (select_in);
1053     assert (ta && "typalise failed (go figure)");
1054
1055     const char *res = ta_name (ta);
1056
1057     /* fprintf (stdout, "typalyse res = %s\n", res); */
1058
1059     if (1 != n_graphs) {
1060       set = filter_for_ta (set, ta);
1061
1062       int n_filtered_graphs = lset_n_entries (set);
1063
1064       fprintf (stdout, "%s: %02d %02d\n",
1065                __FUNCTION__,
1066                n_graphs,
1067                n_filtered_graphs,
1068                n_graphs - n_filtered_graphs);
1069       n_graphs = n_filtered_graphs;
1070     }
1071   }
1072
1073   if (n_graphs > _max_callEds) {
1074     _max_callEds = n_graphs;
1075     _max_callEds_callR = method;
1076   }
1077
1078
1079   if (visibility_external_allocated != get_entity_visibility (method)) {
1080     if (0 == n_graphs) {
1081       /* fprintf (stdout, "no graphs for method %s\n", get_entity_name (method)); */
1082       assert (n_graphs && "no graphs for method");
1083     }
1084   }
1085
1086   return (set);
1087 }
1088
1089 /**
1090    Action for the graph.
1091 */
1092 static void ecg_calls_act (ir_node *node, void *env)
1093 {
1094   opcode op = get_irn_opcode (node);
1095
1096   if (iro_Call == op) {         /* CALL */
1097     graph_info_t *graph_info = (graph_info_t*) env;
1098
1099     entity *ent = NULL;
1100     ir_node *ptr = get_Call_ptr (node);
1101
1102     /* CALL SEL */
1103     if (iro_Sel == get_irn_opcode (ptr)) {
1104       ent = get_Sel_entity (ptr);
1105       lset_t *graphs = get_implementing_graphs (ent, ptr);
1106
1107       append_calls (graph_info, node, graphs);
1108     } else if (iro_SymConst == get_irn_opcode (ptr)) {
1109       if (get_SymConst_kind(ptr) == symconst_addr_ent) {
1110         ent = get_SymConst_entity (ptr);
1111         ir_graph *graph = get_entity_irg (ent);
1112
1113         if (graph) {
1114           append_call (graph_info, node, graph);
1115         } else {
1116           /* it's an externally allocated thingy */
1117         }
1118       } else if (get_SymConst_kind(ptr) == symconst_addr_name) {
1119         /* If this SymConst refers to a method the method is external_visible
1120            and therefore must be considered live anyways. */
1121         if (get_SymConst_name(ptr) != new_id_from_str("iro_Catch")) {
1122           assert (ent && "couldn't determine entity of call to symConst");
1123         }
1124       } else {
1125         /* other symconst. */
1126         assert (0 && "This SymConst can not be an address for a method call.");
1127       }
1128
1129       /* STRANGE, no less ... */
1130     } else {
1131       DDMN(ptr);
1132       assert(0 && "Unexpected address expression");
1133     }
1134   }
1135 }
1136
1137 /**
1138    Collect called graphs for the given graph.
1139 */
1140 static void ecg_fill_graph_calls (ir_graph *graph)
1141 {
1142   graph_info_t *graph_info = (graph_info_t*) xmalloc (sizeof (graph_info_t));
1143
1144   graph_info->graph = graph;
1145   graph_info->calls = NULL;
1146   graph_info->ecg_seen = 0;
1147
1148   entity *method  = get_irg_entity (graph);
1149   type   *clazz   = get_entity_owner (method);
1150
1151   irg_walk_graph (graph, ecg_calls_act, NULL, graph_info);
1152
1153   pmap_insert (graph_infos, graph, graph_info);
1154 }
1155
1156 /**
1157    For each graph, collect called graphs, and enter them into calls.
1158 */
1159 static void ecg_fill_calls ()
1160 {
1161   int i;
1162
1163   for (i = 0; i < get_irp_n_irgs (); i++) {
1164     ir_graph *graph = get_irp_irg (i);
1165
1166     ecg_fill_graph_calls (graph);
1167   }
1168 }
1169
1170 /* ====================
1171   ECG stuff
1172   ==================== */
1173
1174 /*
1175   get the call infos for the given graph
1176 */
1177 graph_info_t *ecg_get_info (ir_graph *graph)
1178 {
1179   graph_info_t *ginfo = (graph_info_t*) pmap_get (graph_infos, graph);
1180
1181   assert (ginfo && "no info for graph");
1182
1183   return (ginfo);
1184 }
1185
1186
1187
1188 /**
1189    Dump the given graph and it's calls and it's calls callEds to the given file.
1190 */
1191 static int ecg_ecg_graph (FILE *dot, ir_graph *graph)
1192 {
1193   const char *name = get_irg_entity (graph) ?
1194     get_entity_name (get_irg_entity (graph)) : "noEntity";
1195   const char *color =
1196     (get_entity_stickyness
1197      (get_irg_entity (graph)) == stickyness_sticky) ?
1198     "blue" : "red";
1199
1200   graph_info_t *ginfo = (graph_info_t*) pmap_get (graph_infos, graph);
1201
1202   if (0 != ginfo->ecg_seen) {
1203     fprintf (dot, "\t/* recursive call to \"%s\" (0x%08x) */\n", name, graph);
1204
1205     return (ginfo->ecg_seen);
1206   }
1207
1208   assert (0L <= _graphs);
1209
1210   const int graph_no = _graphs ++;
1211   ginfo->ecg_seen = graph_no;
1212
1213   fprintf (dot, "\t/* Graph of \"%s\" */\n", name);
1214   fprintf (dot, "\tgraph_%i [label=\"%s\", color=\"%s\"];\n", graph_no, name, color);
1215   fprintf (dot, "\n");
1216
1217   if (visibility_external_allocated ==
1218       get_entity_visibility (get_irg_entity (graph))) {
1219     fprintf (dot, "\t/* graph \"%s\" is external */\n", name);
1220
1221     return (graph_no);
1222   }
1223
1224   call_info_t *cinfo = ginfo->calls;
1225   while (NULL != cinfo) {
1226     ir_node *call = cinfo->call;
1227     callEd_info_t *ced = cinfo->callEds;
1228     const int call_no = _calls ++;
1229
1230     fprintf (dot, "\t/* Call 0x%08x */\n", call);
1231     fprintf (dot, "\tcall_%i [label=\"call\\l0x%08x\"];\n",
1232              call_no, call);
1233     fprintf (dot, "\tgraph_%i -> call_%i;\n", graph_no, call_no);
1234
1235     while (NULL != ced) {
1236       ir_graph *callEd_graph = ced->callEd;
1237       const int callEd_no = ecg_ecg_graph (dot, callEd_graph);
1238       const char *callEd_name = get_irg_entity (callEd_graph) ?
1239         get_entity_name (get_irg_entity (callEd_graph)) : "noEntity";
1240       const char *direction = (callEd_no <= graph_no) ? "back" : "forward";
1241       const char *callEd_color     = (callEd_no <= graph_no) ? "red" : "black";
1242
1243       fprintf (dot, "\t/* Call to graph \"%s\" */\n", callEd_name);
1244       /* Todo: Check for recursive calls */
1245       /* if (callEd_no > graph_no) */ { /* do do recursive calls (for now) */
1246       fprintf (dot, "\tcall_%i -> graph_%i [color=\"%s\", dir=\"%s\"];\n",
1247                call_no, callEd_no, callEd_color, direction);
1248       }
1249
1250       ced = ced->prev;
1251       /* ced = NULL; */
1252     } /* done all calEds(call) */
1253
1254     cinfo = cinfo->prev;
1255   } /* done all calls(graph) */
1256
1257   fprintf (dot, "\t/* done with graph of \"%s\" */\n\n", name);
1258
1259   fflush (dot);
1260   ginfo->ecg_seen = 0;
1261
1262   return (graph_no);
1263 }
1264
1265 /**
1266    Count how many nodes the ECG will have
1267 */
1268 static void ecg_ecg_count (ir_graph *graph)
1269 {
1270   graph_info_t *ginfo = (graph_info_t*) pmap_get (graph_infos, graph);
1271
1272   if (0 != ginfo->ecg_seen) {
1273     return;
1274   }
1275
1276   _depth ++;
1277   if (_depth > _max_depth) {
1278     _max_depth = _depth;
1279
1280     fprintf (stdout, "_max_depth = %i\n", _max_depth);
1281     fprintf (stdout, "\tn_graphs: %i\n", _graphs);
1282   }
1283
1284   assert (0L <= _graphs);
1285
1286   if (!(_graphs % 1000000)) {
1287     fprintf (stdout, "\tn_graphs: %i\n", _graphs);
1288     fprintf (stdout, "_depth = %i\n", _depth);
1289   }
1290
1291   const int graph_no = _graphs ++;
1292   ginfo->ecg_seen = graph_no;
1293
1294   call_info_t *cinfo = ginfo->calls;
1295   while (NULL != cinfo) {
1296
1297     callEd_info_t *ced = cinfo->callEds;
1298     while (NULL != ced) {
1299       ir_graph *callEd_graph = ced->callEd;
1300
1301       ecg_ecg_count (callEd_graph);
1302
1303       ced = ced->prev;
1304     } /* done all calEds(call) */
1305     cinfo = cinfo->prev;
1306   } /* done all calls(graph) */
1307
1308   ginfo->ecg_seen = 0;
1309   _depth --;
1310 }
1311
1312 /* ====================
1313   Public Interface
1314   ==================== */
1315
1316 /**
1317    Initialise our data structures.
1318 */
1319 void ecg_init (int typalise)
1320 {
1321   do_typalise = typalise;
1322
1323   graph_infos = pmap_create ();
1324
1325   ecg_fill_calls ();
1326 }
1327
1328 /**
1329    Clean up our mess.
1330 */
1331 void ecg_cleanup ()
1332 {
1333   int i;
1334
1335   for (i = 0; i < get_irp_n_irgs (); i++) {
1336     ir_graph *graph = get_irp_irg (i);
1337
1338     graph_info_t *info = pmap_get (graph_infos, graph);
1339     call_info_t *cinfo = info->calls;
1340
1341     while (NULL != cinfo) {
1342       free (cinfo->callEds);
1343       cinfo->call = NULL;
1344
1345       callEd_info_t *ced = cinfo->callEds;
1346
1347       while (NULL != ced) {
1348         callEd_info_t *nced = ced->prev;
1349         free (ced);
1350         ced->prev = NULL;
1351         ced->callEd = NULL;
1352         ced = nced;
1353       }
1354
1355       /* Todo: delete callEds */
1356       cinfo->callEds = NULL;
1357
1358       free (cinfo);
1359       cinfo = cinfo->prev;
1360     }
1361
1362     free (info);
1363     pmap_insert (graph_infos, graph, NULL);
1364   }
1365
1366
1367   pmap_destroy (graph_infos);
1368
1369   /* BEGIN mild paranoia mode */
1370   graph_infos = NULL;
1371   /* END mild paranoia mode */
1372 }
1373
1374 /**
1375    Show what we have found.
1376 */
1377 void ecg_report ()
1378 {
1379   int i;
1380
1381   FILE *dot = fopen ("calls.dot", "w");
1382
1383   fprintf (dot, "digraph \"calls\" {\n");
1384   fprintf (dot, "\tnode [shape = \"record\", style = \"filled\"];\n");
1385   fprintf (dot, "\tedge [color = \"black\"];\n");
1386   fprintf (dot, "\n");
1387   fprintf (dot, "\tsize = \"11, 7\";\n");
1388   fprintf (dot, "\trotate = \"90\";\n");
1389   fprintf (dot, "\tratio = \"fill\";\n");
1390   fprintf (dot, "\trankdir = \"LR\";\n");
1391   fprintf (dot, "\n");
1392
1393   for (i = 0; i < get_irp_n_irgs (); i++) {
1394     ir_graph *graph = get_irp_irg (i);
1395     graph_info_t *info = (graph_info_t*) pmap_get (graph_infos, graph);
1396
1397     const char *name = get_irg_entity (graph) ?
1398       get_entity_name (get_irg_entity (graph)) : "noEntity";
1399
1400     const char *oname = get_type_name
1401       (get_entity_owner (get_irg_entity (graph)));
1402
1403     const char *color =
1404       (get_entity_stickyness
1405        (get_irg_entity (graph)) == stickyness_sticky) ?
1406       "red" : "blue";
1407
1408     fprintf (dot, "\t/* graph_0x%08x (\"%s\") */\n", graph, name);
1409     fprintf (dot,
1410              "\tgraph_0x%08x [label=\"%s\\l%s\", color=\"%s\"];\n",
1411              graph, oname, name, color);
1412     fprintf (dot, "\n");
1413     fprintf (dot, "\t/* now the calls */\n");
1414
1415     call_info_t *cinfo = info->calls;
1416     while (NULL != cinfo) {
1417       ir_node *call = cinfo->call;
1418       int i;
1419
1420       fprintf (dot, "\t/* call_0x%08x */\n", call);
1421       fprintf (dot, "\tcall_0x%08x [label=\"call\\l0x%08x\"];\n", call, call);
1422       fprintf (dot, "\tgraph_0x%08x -> call_0x%08x;\n", graph, call);
1423
1424       callEd_info_t *ced = cinfo->callEds;
1425       while (NULL != ced) {
1426         fprintf (dot, "\tcall_0x%08x -> graph_0x%08x;\n", call, ced->callEd);
1427         ced = ced->prev;
1428       }
1429       fprintf (dot, "\n");
1430
1431       cinfo = cinfo->prev;
1432     }
1433     fprintf (dot, "\n");
1434   }
1435   fprintf (dot, "}\n");
1436
1437   fprintf (stdout, " max_callEds: %i\n", _max_callEds);
1438   fprintf (stdout, " max_callEds_callR: \"%s\"\n",
1439            get_entity_name (_max_callEds_callR));
1440
1441   fclose (dot);
1442
1443   ecg_ecg ();
1444 }
1445
1446 /**
1447    Experimental:  Print the ecg
1448 */
1449 void ecg_ecg ()
1450 {
1451   _graphs = 0;
1452   _calls  = 0;
1453
1454   ir_graph *main_graph = get_irp_main_irg ();
1455
1456   /*
1457   ecg_ecg_count (main_graph);
1458   fprintf (stdout, "n_graphs: %i\n", _graphs);
1459   fprintf (stdout, "max_depth = %i\n", _max_depth);
1460
1461   return;
1462
1463   _graphs = 0;
1464   _calls  = 0;
1465   */
1466
1467   FILE *dot = fopen ("ecg.dot", "w");
1468
1469   fprintf (dot, "digraph \"ecg\" {\n");
1470   fprintf (dot, "\tnode [shape = \"record\", style = \"filled\"];\n");
1471   fprintf (dot, "\tedge [color = \"black\"];\n");
1472   fprintf (dot, "\n");
1473   fprintf (dot, "\tsize = \"11, 7\";\n");
1474   fprintf (dot, "\trotate = \"90\";\n");
1475   fprintf (dot, "\tratio = \"fill\";\n");
1476   fprintf (dot, "\trankdir = \"LR\";\n");
1477   fprintf (dot, "\n");
1478
1479   /* ir_graph *main_graph = get_irp_main_irg (); */
1480   ecg_ecg_graph (dot, main_graph);
1481
1482   fprintf (dot, "\t/* Grand Total: */\n");
1483   fprintf (dot, "\t/* calls:  %i */\n", _calls);
1484   fprintf (dot, "\t/* graphs: %i */\n", _graphs);
1485   fprintf (dot, "\t/* (sales tax not included) */\n");
1486
1487   fprintf (dot, "}\n");
1488
1489   fclose (dot);
1490 }