nsz Git - libfirm/blob - ir/ana2/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:      $Id$
  11  * Copyright:   (c) 1999-2004 Universität Karlsruhe
  12  * Licence:     This file is protected by the 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 # ifndef TRUE
  33 #  define TRUE 1
  34 #  define FALSE 0
  35 # endif /* not defined TRUE */
  36
  37 # define BUF_SIZE 1024
  38
  39 # include "ecg.h"
  40 # include "typalise.h"
  41 # include "lset.h"
  42
  43 # include "gnu_ext.h"
  44
  45 # define HERE(msg)  fprintf (stdout, "%s:%i %s\n", __FUNCTION__, __LINE__, msg)
  46
  47 /*
  48   le flag
  49 */
  50 /* static int verbose     = 0; */
  51 static int do_typalise = 0;
  52
  53 /*
  54   globals
  55 */
  56
  57 /* Ids for the ctxs */
  58 static int ctx_id = 0;
  59 ctx_info_t *main_ctx = NULL;
  60
  61 /* mapping from method graphs (callR) to method graphs (lset_ts of callEds) */
  62 /* static pmap *calls; */
  63 static pmap *graph_infos;
  64
  65 /* linked list of all graph_infos: */
  66 static graph_info_t *graph_infos_list = NULL;
  67
  68 /* Counters for ecg_ecg and friends */
  69 static long _graphs = 0;
  70 static long _calls  = 0;
  71 static long _allocs = 0;
  72
  73 static int _depth = 0;
  74 static int _max_depth = 0;
  75
  76 static int _max_callEds = 0;
  77 static entity* _max_callEds_callR = NULL;
  78
  79 /* Protos */
  80 void set_main_ctx (ctx_info_t*);
  81
  82 /* ====================
  83    Alloc stuff
  84    ==================== */
  85 static void append_alloc (graph_info_t *ginfo, ir_node *alloc, type *tp)
  86 {
  87   alloc_info_t *ainfo = xmalloc (sizeof (alloc_info_t));
  88
  89   ainfo->graph = ginfo->graph;
  90   ainfo->alloc = alloc;
  91   ainfo->tp    = tp;
  92
  93   ainfo->prev = ginfo->allocs;
  94   ginfo->allocs = ainfo;
  95 }
  96
  97
  98 /* ====================
  99    CallEd stuff
 100    ==================== */
 101 /**
 102    Create a new call info struct from the given values.
 103 */
 104 static call_info_t *new_call_info (ir_node *call,
 105                                    callEd_info_t *callEds,
 106                                    call_info_t *prev)
 107 {
 108   call_info_t *cinfo = xmalloc (sizeof (call_info_t));
 109   cinfo->call = call;
 110   cinfo->callEds = callEds;
 111   cinfo->prev = prev;
 112
 113   return (cinfo);
 114 }
 115
 116 /**
 117    Append the given callEd to the given callEd info.
 118 */
 119 static callEd_info_t *append_callEd_info (callEd_info_t *ced, ir_graph *callEd)
 120 {
 121   callEd_info_t *nced = xmalloc (sizeof (callEd_info_t));
 122
 123   assert (NULL != callEd);
 124
 125   nced->callEd = callEd;
 126   nced->prev = ced;
 127
 128   return (nced);
 129 }
 130
 131 /**
 132    Append all callEd methods of the given (call) node to the given graph_info.
 133 */
 134 static void append_calls (graph_info_t *info, ir_node *call, lset_t *callEds)
 135 {
 136   ir_graph *callEd = NULL;
 137   call_info_t *cinfo = new_call_info (call, NULL, info->calls);
 138
 139   info->calls = cinfo;
 140
 141   /* enter */
 142   callEd = lset_first (callEds);
 143
 144   while (NULL != callEd) {
 145     cinfo->callEds = append_callEd_info (cinfo->callEds, callEd);
 146     callEd = lset_next(callEds);
 147   }
 148
 149 }
 150
 151 /**
 152    Append the (single) callEd to the given (call) node of the given graph_info.
 153 */
 154 static void append_call (graph_info_t *info, ir_node *call, ir_graph *callEd)
 155 {
 156   call_info_t *cinfo = new_call_info (call, NULL, info->calls);
 157
 158   info->calls = cinfo;
 159
 160   cinfo->callEds = append_callEd_info (cinfo->callEds, callEd);
 161 }
 162
 163 /**
 164    Given a method, find the firm graph that implements that method.
 165    Return NULL for abstract and native methods.
 166 */
 167 static ir_graph *_get_implementing_graph (entity *method)
 168 {
 169   ir_graph *graph = NULL;
 170
 171   /* What's up with the fenced out stuff in rta? */
 172   if (peculiarity_existent == get_entity_peculiarity (method)) {
 173     if (visibility_external_allocated == get_entity_visibility (method)) {
 174       /* Todo: native implementation */
 175
 176       return (NULL);
 177     } else {
 178       graph = get_entity_irg (get_SymConst_entity (get_atomic_ent_value (method)));
 179       assert (graph && "no graph");
 180
 181       return (graph);
 182     }
 183   } else if (0 && (peculiarity_description == get_entity_peculiarity (method))) {
 184     /* abstract --- can't find an implementation */
 185     graph = get_entity_irg (method);
 186     assert (!graph && "graph in abstract method");
 187
 188     return (NULL);
 189   } else if ((peculiarity_description == get_entity_peculiarity (method)) ||
 190              (peculiarity_inherited == get_entity_peculiarity (method))) {
 191     /* search UPWARDS */
 192     int i;
 193     int n_over = get_entity_n_overwrites (method);
 194
 195     assert (!graph);
 196
 197     for (i = 0; (NULL == graph) && (i < n_over); i ++) {
 198       entity *over = get_entity_overwrites (method, i);
 199
 200       graph = _get_implementing_graph (over);
 201     }
 202   } else {
 203     assert (0 && "invalid peculiarity");
 204   }
 205
 206
 207   return (graph);
 208 }
 209
 210 /**
 211    Collect all graphs of 'method' in the given set.
 212 */
 213 static void _collect_implementing_graphs (entity *method, lset_t *set)
 214 {
 215   /* search DOWN-wards in clazz hierarchy */
 216   int i;
 217   int n_over = get_entity_n_overwrittenby (method);
 218   ir_graph *graph = get_entity_irg (method);
 219
 220   if (NULL == graph) {
 221     graph = _get_implementing_graph (method);
 222   }
 223
 224   if (graph) {
 225     lset_insert (set, graph);
 226   }
 227
 228   for (i = 0; i < n_over; i ++) {
 229     entity *over = get_entity_overwrittenby (method, i);
 230
 231     _collect_implementing_graphs (over, set);
 232   }
 233 }
 234
 235
 236 /**
 237    Collect all graphs that could possibly be executed when 'method' is called.
 238 */
 239 static lset_t *get_implementing_graphs (entity *method, ir_node *select)
 240 {
 241   /* const char *name = get_entity_name (method); */
 242   /* fprintf (stdout, "%s (ent %s)\n", __FUNCTION__, name); */
 243
 244   int n_graphs;
 245   lset_t *set = lset_create ();
 246   {
 247     ir_graph *impl = _get_implementing_graph (method);
 248
 249     if (NULL != impl) {
 250       lset_insert (set, impl);
 251     } else {
 252       /* actually, abstract OR native */
 253     }
 254   }
 255
 256   _collect_implementing_graphs (method, set);
 257
 258   if (lset_empty (set)) {
 259     /* then it's a method which is only implemented natively, and we
 260        don' bother to analyse anything */
 261     return (set);
 262   }
 263
 264   /* void *tmp = lset_first (set); */
 265   n_graphs = lset_n_entries (set);
 266
 267
 268   if (visibility_external_allocated != get_entity_visibility (method)) {
 269     if (0 == n_graphs) {
 270       ir_graph *graph = get_irn_irg (select);
 271
 272       dump_ir_block_graph (graph, "-typealise");
 273
 274       /* fprintf (stdout, "no graphs for method %s\n", get_entity_name (method)); */
 275       assert (n_graphs && "no graphs for method");
 276     }
 277   }
 278   /* typalise select_in */
 279   if (do_typalise) {
 280     ir_node *select_in = get_Sel_ptr (select);
 281     typalise_t *ta = typalise (select_in);
 282     /* assert (ta && "typalise failed (go figure)"); */
 283
 284     /*
 285     fprintf (stdout, "typalyse res = ");
 286
 287     if (NULL != ta) {
 288       if (type_invalid == ta->kind) {
 289         fprintf (stdout, "invalid");
 290       } else if (type_exact == ta->kind) {
 291         const char *name = get_type_name (ta->res.type);
 292
 293         fprintf (stdout, "exact [");
 294         fprintf (stdout, "%s", name);
 295         fprintf (stdout, "]\n");
 296       } else if (type_types == ta->kind) {
 297         fprintf (stdout, "types [");
 298         fprintf (stdout, "...");
 299         fprintf (stdout, "]\n");
 300       } else if (type_type == ta->kind) {
 301         const char *name = get_type_name (ta->res.type);
 302         fprintf (stdout, "type [");
 303         fprintf (stdout, "%s", name);
 304         fprintf (stdout, "]\n");
 305       }
 306     } else {
 307       fprintf (stdout, "(null)\n");
 308     }
 309     */
 310
 311     if (1 != n_graphs) {
 312       int n_filtered_graphs;
 313
 314       set = filter_for_ta (set, ta);
 315       n_filtered_graphs = lset_n_entries (set);
 316
 317       /*
 318         fprintf (stdout, "%s: %02d %02d\n",
 319         __FUNCTION__,
 320         n_graphs,
 321         n_filtered_graphs,
 322         n_graphs - n_filtered_graphs);
 323       */
 324       n_graphs = n_filtered_graphs;
 325     }
 326
 327     if (visibility_external_allocated != get_entity_visibility (method)) {
 328       if (0 == n_graphs) {
 329         ir_graph *graph = get_irn_irg (select);
 330
 331         dump_ir_block_graph (graph, "-ecg");
 332         /* fprintf (stdout, "no graphs for method %s\n", get_entity_name (method)); */
 333         assert (n_graphs && "no graphs for method");
 334       }
 335     }
 336
 337   }
 338
 339   if (n_graphs > _max_callEds) {
 340     _max_callEds = n_graphs;
 341     _max_callEds_callR = method;
 342   }
 343
 344
 345   return (set);
 346 }
 347
 348 /**
 349    Determine whether a call is actually a call or if it is being
 350    abused for some b/d-ed reason.
 351 */
 352 static int call_is_call (ir_node *call, ir_node *ptr)
 353 {
 354   if (op_SymConst != get_irn_op (ptr)) {
 355     return (TRUE);
 356   } else if (get_SymConst_kind (ptr) != symconst_addr_name) {
 357     return (TRUE);
 358   }
 359
 360   return (FALSE);
 361 }
 362
 363 /**
 364    Action for the graph.
 365 */
 366 static void ecg_calls_act (ir_node *node, void *env)
 367 {
 368   ir_op *op = get_irn_op(node);
 369   graph_info_t *graph_info = (graph_info_t*) env;
 370
 371   if (op_Call == op) {         /* CALL */
 372     entity *ent = NULL;
 373     ir_node *ptr = get_Call_ptr (node);
 374
 375     if (!call_is_call (node, ptr)) {
 376       /*
 377       fprintf (stdout, "not a call: %s[%li]\n",
 378                get_op_name (get_irn_op (node)),
 379                get_irn_node_nr (node)); */
 380       return;
 381     }
 382
 383     /* CALL SEL */
 384     if (op_Sel == get_irn_op (ptr)) {
 385       lset_t *graphs;
 386       ent = get_Sel_entity (ptr);
 387       graphs = get_implementing_graphs (ent, ptr);
 388
 389       append_calls (graph_info, node, graphs);
 390     } else if (op_SymConst == get_irn_op (ptr)) {
 391       if (get_SymConst_kind (ptr) == symconst_addr_ent) {
 392         ir_graph *graph;
 393         ent = get_SymConst_entity (ptr);
 394         graph = get_entity_irg (ent);
 395
 396         if (graph) {
 397           append_call (graph_info, node, graph);
 398         } else {
 399           /* it's an externally allocated thingy */
 400         }
 401       } else if (get_SymConst_kind (ptr) == symconst_addr_name) {
 402         /* If this SymConst refers to a method the method is external_visible
 403            and therefore must be considered live anyways. */
 404         if (get_SymConst_name (ptr) != new_id_from_str ("iro_Catch")) {
 405           assert (ent && "couldn't determine entity of call to symConst");
 406         }
 407       } else {
 408         /* other symconst. */
 409         assert (0 && "This SymConst can not be an address for a method call.");
 410       }
 411
 412       /* STRANGE, no less ... */
 413     } else {
 414       DDMN (ptr);
 415       assert (0 && "Unexpected address expression");
 416     }
 417   } else if (op_Alloc == op) {
 418     type *tp = get_Alloc_type (node);
 419     /* const char *name = get_type_name (tp); */
 420
 421     append_alloc (graph_info, node, tp);
 422
 423     /* fprintf (stdout, "NEW \"%s\"\n", name); */
 424   }
 425 }
 426
 427 /**
 428    Collect called graphs for the given graph.
 429 */
 430 static void ecg_fill_graph_calls (ir_graph *graph)
 431 {
 432   graph_info_t *ginfo = xmalloc (sizeof (graph_info_t));
 433
 434   /* memset (ginfo, 0x00, sizeof (graph_info_t)); */
 435   assert (ginfo != graph_infos_list);
 436
 437   ginfo->graph       = graph;
 438   ginfo->calls       = NULL;
 439   ginfo->allocs      = NULL;
 440   ginfo->ctxs        = NULL;
 441   ginfo->n_ctxs      = 0;
 442   ginfo->ecg_seen    = 0;
 443   ginfo->allocs_seen = 0;
 444   ginfo->prev        = NULL;
 445
 446   /* link up into global list */
 447   ginfo->prev = graph_infos_list;
 448   graph_infos_list = ginfo;
 449
 450   assert (ginfo != ginfo->prev);
 451
 452   irg_walk_graph (graph, ecg_calls_act, NULL, ginfo);
 453
 454   pmap_insert (graph_infos, graph, ginfo);
 455 }
 456
 457 /**
 458    For each graph, collect called graphs, and enter them into calls.
 459 */
 460 static void ecg_fill_calls (void)
 461 {
 462   int i;
 463
 464   for (i = 0; i < get_irp_n_irgs (); i++) {
 465     ir_graph *graph = get_irp_irg (i);
 466
 467     ecg_fill_graph_calls (graph);
 468   }
 469 }
 470
 471 /**
 472    Allocate a new ctx for the given graph and the given enclosing ctx.
 473 */
 474 static ctx_info_t *new_ctx (ir_graph *graph, ir_node *call, ctx_info_t *enc)
 475 {
 476   ctx_info_t *res = xmalloc (sizeof (ctx_info_t));
 477
 478   res->graph = graph;
 479   res->call = call;
 480   res->enc = enc;
 481   res->id = ctx_id ++;
 482
 483   return (res);
 484 }
 485
 486
 487 /**
 488    Fill in the ctxs parts of the graph_infos
 489 */
 490 static void ecg_fill_ctxs_count (ir_graph *graph)
 491 {
 492   graph_info_t *ginfo = ecg_get_info (graph);
 493
 494   /* count how many ctxs we have per graph */
 495   if (0 == ginfo->ecg_seen) {
 496     call_info_t *cinfo = ginfo->calls;
 497
 498     ginfo->ecg_seen = 1;
 499
 500     while (NULL != cinfo) {
 501       callEd_info_t *ced = cinfo->callEds;
 502
 503       while (NULL != ced) {
 504         ir_graph *callEd_graph = ced->callEd;
 505
 506         /* first step: we have a new ctx */
 507         graph_info_t *callEd_info = ecg_get_info (callEd_graph);
 508         callEd_info->n_ctxs ++;
 509
 510         /* CallR graph -> CallEd_graph */
 511         ecg_fill_ctxs_count (callEd_graph);
 512
 513         ced = ced->prev;
 514       } /* end forall callEds (call) */
 515
 516       cinfo = cinfo->prev;
 517     } /* end forall (calls(graph)) */
 518
 519     ginfo->ecg_seen = 0;
 520   }
 521 }
 522
 523 static void ecg_fill_ctxs_alloc (void)
 524 {
 525   /* allocate the memory needed for the ctxts: */
 526   graph_info_t *ginfo = graph_infos_list;
 527
 528   while (NULL != ginfo) {
 529     ginfo->ctxs = xcalloc (ginfo->n_ctxs, sizeof (ctx_info_t *));
 530
 531     /*
 532       fprintf (stdout, "graph of \"%s\": n_ctxs = %i\n",
 533       get_entity_name (get_irg_entity (ginfo->graph)), ginfo->n_ctxs);
 534     */
 535     ginfo->n_ctxs = 0;
 536
 537     assert (ginfo != ginfo->prev);
 538     ginfo = ginfo->prev;
 539   }
 540 }
 541
 542 /**
 543    Fill in the ctxs parts of the graph_infos
 544 */
 545 static void ecg_fill_ctxs_write (ir_graph *graph, ctx_info_t *enc_ctx)
 546 {
 547   graph_info_t *ginfo = ecg_get_info (graph);
 548
 549   /* enter a new ctx for all callEds along the call edges of this graph */
 550   if (0 == ginfo->ecg_seen) {
 551     call_info_t *cinfo = ginfo->calls;
 552     ginfo->ecg_seen = 1;
 553
 554     while (NULL != cinfo) {
 555       callEd_info_t *ced = cinfo->callEds;
 556
 557       while (NULL != ced) {
 558         ctx_info_t *ctx = new_ctx (graph, cinfo->call, enc_ctx);
 559
 560         ir_graph *callEd_graph = ced->callEd;
 561
 562         /* write the ctx of this call into the callEd graph */
 563         graph_info_t *callEd_info = ecg_get_info (callEd_graph);
 564
 565         callEd_info->ctxs [callEd_info->n_ctxs] = ctx;
 566         callEd_info->n_ctxs ++;
 567
 568         /* CallR graph -> callEd_graph */
 569         ecg_fill_ctxs_write (callEd_graph, ctx);
 570
 571         ced = ced->prev;
 572       } /* end forall callEds (call) */
 573
 574       cinfo = cinfo->prev;
 575     } /* end forall (calls(graph)) */
 576
 577     ginfo->ecg_seen = 0;
 578   }
 579 }
 580
 581 /**
 582    Fill in the ctxs parts of the graph_infos
 583 */
 584 static void ecg_fill_ctxs (void)
 585 {
 586   ctx_info_t *main_ctx;
 587   ir_graph *main_irg;
 588   graph_info_t *ginfo;
 589
 590   ecg_fill_ctxs_count (get_irp_main_irg ());
 591   ecg_fill_ctxs_alloc ();
 592
 593   main_ctx = new_ctx (get_irp_main_irg (), NULL, NULL);
 594   main_irg = get_irp_main_irg ();
 595
 596   set_main_ctx (main_ctx);
 597
 598   /* Grrr, have to add this ctx manually to main.ginfo ... */
 599   ginfo = ecg_get_info (main_irg);
 600   ginfo->n_ctxs = 1;
 601   ginfo->ctxs = xcalloc (1, sizeof (ctx_info_t *));
 602   ginfo->ctxs [0] = main_ctx;
 603
 604   ecg_fill_ctxs_write (main_irg, main_ctx);
 605 }
 606
 607 /* ====================
 608    CTX stuff
 609    ==================== */
 610 /*
 611   Nicely print a ctx_info_t to the given output stream
 612 */
 613 void ecg_print_ctx (ctx_info_t *ctx, FILE *stream)
 614 {
 615   entity *ent = get_irg_entity(ctx->graph);
 616   ir_node *call = ctx->call;
 617   const char *ent_name = get_entity_name (ent);
 618   const char *own_name = get_type_name (get_entity_owner (ent));
 619
 620   fprintf (stream, "CTX[%i](%s.%s->%s[%li])",
 621            ctx->id, own_name, ent_name,
 622            get_op_name (get_irn_op (call)),
 623            get_irn_node_nr (call));
 624
 625   if (NULL != ctx->enc) {
 626     fprintf (stream, "->%i", ctx->enc->id);
 627   }
 628
 629   fprintf (stream, "\n");
 630 }
 631
 632 /*
 633   Get a ctx of the given graph info
 634 */
 635 ctx_info_t *get_ctx (graph_info_t *ginfo, int ctx_idx)
 636 {
 637   assert (ginfo->n_ctxs > ctx_idx);
 638
 639   return (ginfo->ctxs [ctx_idx]);
 640 }
 641
 642 /*
 643   Get the pseudo-ctx of 'main'
 644 */
 645 ctx_info_t *get_main_ctx ()
 646 {
 647   return (main_ctx);
 648 }
 649
 650 /*
 651   Set the pseudo-ctx of 'main'
 652 */
 653 void set_main_ctx (ctx_info_t *ctx)
 654 {
 655   main_ctx = ctx;
 656 }
 657
 658
 659 /* ====================
 660    ECG stuff
 661    ==================== */
 662
 663 /* ====================
 664    Iterator stuff
 665    ==================== */
 666 /*
 667    Iterate over all graphs
 668 */
 669 void ecg_iterate_graphs (graph_hnd_t *hnd, void *env)
 670 {
 671   graph_info_t *ginfo = graph_infos_list;
 672
 673   while (NULL != ginfo) {
 674     /* do not visit graphs that have 0 == ginfo->n_ctxs, since they
 675        are not called */
 676     if (0 != ginfo->n_ctxs) {
 677       hnd (ginfo, env);
 678     }
 679
 680     ginfo = ginfo->prev;
 681   }
 682 }
 683
 684
 685 /*
 686    Iterate of all allocs of a given graph info
 687 */
 688 void ecg_iterate_allocs (graph_info_t *ginfo, alloc_hnd_t *hnd, void *env)
 689 {
 690   alloc_info_t *ainfo = ginfo->allocs;
 691
 692   while (NULL != ainfo) {
 693     hnd (ainfo, env);
 694
 695     ainfo = ainfo->prev;
 696   }
 697 }
 698
 699
 700 /*
 701   Iterate over all calls of the given graph info
 702 */
 703 void ecg_iterate_calls  (graph_info_t *ginfo, call_hnd_t *hnd, void *env)
 704 {
 705   call_info_t *cinfo = ginfo->calls;
 706
 707   while (NULL != cinfo) {
 708     hnd (cinfo, env);
 709
 710     cinfo = cinfo->prev;
 711   }
 712 }
 713
 714
 715 /*
 716   Iterate over all callEds of the given call info
 717 */
 718 void ecg_iterate_callEds  (call_info_t *cinfo, callEd_hnd_t *hnd, void *env)
 719 {
 720   callEd_info_t *ced = cinfo->callEds;
 721
 722   while (NULL != ced) {
 723     hnd (ced, env);
 724
 725     ced = ced->prev;
 726   }
 727 }
 728
 729
 730 /*
 731   get the call infos for the given graph
 732 */
 733 graph_info_t *ecg_get_info (ir_graph *graph)
 734 {
 735   graph_info_t *ginfo = (graph_info_t*) pmap_get (graph_infos, graph);
 736
 737   assert (ginfo && "no info for graph");
 738
 739   return (ginfo);
 740 }
 741
 742 /*
 743   Get the Alloc Infos for the given graph
 744 */
 745 alloc_info_t *ecg_get_alloc_info (ir_graph *graph)
 746 {
 747   graph_info_t *ginfo = ecg_get_info (graph);
 748
 749   return (ginfo->allocs);
 750 }
 751
 752 /*
 753   Get the Call Info for the given call
 754 */
 755 callEd_info_t *ecg_get_callEd_info (ir_node *call)
 756 {
 757   ir_graph *graph = get_irn_irg (call);
 758   graph_info_t *ginfo = ecg_get_info (graph);
 759
 760   call_info_t *call_info = ginfo->calls;
 761
 762   while (NULL != call_info) {
 763     if (call == call_info->call) {
 764       return (call_info->callEds);
 765     }
 766
 767     call_info = call_info->prev;
 768   }
 769
 770   return (NULL);
 771 }
 772
 773
 774 /**
 775    Dump the given graph and it's calls and it's calls callEds to the given file.
 776 */
 777 static int ecg_ecg_graph (FILE *dot, ir_graph *graph)
 778 {
 779   int graph_no;
 780   call_info_t *cinfo;
 781   alloc_info_t *ainfo;
 782   const char *name = get_irg_entity (graph) ?
 783     get_entity_name (get_irg_entity (graph)) : "noEntity";
 784   const char *color =
 785     (get_entity_stickyness
 786      (get_irg_entity (graph)) == stickyness_sticky) ?
 787     "red" : "lightyellow";
 788
 789   /* graph_info_t *ginfo = (graph_info_t*) pmap_get (graph_infos, graph); */
 790   graph_info_t *ginfo = ecg_get_info (graph);
 791
 792   if (0 != ginfo->ecg_seen) {
 793     fprintf (dot, "\t/* recursive call to \"%s\" (%d) */\n",
 794              name, (int) ginfo->ecg_seen);
 795 # if 0
 796     fprintf (dot, "\t/* recursive call to \"%s\" (0x%08x) */\n",
 797              name, (int) graph);
 798 # endif /* 0 */
 799     return (ginfo->ecg_seen);
 800   }
 801
 802   assert (0L <= _graphs);
 803
 804   graph_no = _graphs ++;
 805   ginfo->ecg_seen = graph_no;
 806
 807   fprintf (dot, "\t/* Graph of \"%s.%s\" */\n",
 808            get_type_name (get_entity_owner (get_irg_entity (graph))),
 809            name);
 810   fprintf (dot, "\tgraph_%i [label=\"<HEAD>%s\\l%s\\l|<CTX>n_ctx = %i\\l\", color=\"%s\"];\n",
 811            graph_no,
 812            get_type_name (get_entity_owner (get_irg_entity (graph))),
 813            name,
 814            ginfo->n_ctxs,
 815            color);
 816   fprintf (dot, "\n");
 817
 818   if (visibility_external_allocated ==
 819       get_entity_visibility (get_irg_entity (graph))) {
 820     fprintf (dot, "\t/* graph \"%s\" is external */\n", name);
 821
 822     return (graph_no);
 823   }
 824
 825   cinfo = ginfo->calls;
 826   while (NULL != cinfo) {
 827     ir_node *call = cinfo->call;
 828     callEd_info_t *ced = cinfo->callEds;
 829     const int call_no = _calls ++;
 830     const char *call_color = (NULL == ced) ? "blue" :
 831       (NULL == ced->prev) ? "lightblue" : "blue3";
 832
 833     fprintf (dot, "\t/* Call %li */\n", get_irn_node_nr (call));
 834     fprintf (dot, "\tcall_%i [label=\"call\\[%li\\]\", color=\"%s\", shape=\"ellipse\"];\n",
 835              call_no, get_irn_node_nr (call), call_color);
 836     fprintf (dot, "\tgraph_%i -> call_%i [color=\"black\"];\n", graph_no, call_no);
 837
 838     while (NULL != ced) {
 839       ir_graph *callEd_graph = ced->callEd;
 840       const int callEd_no = ecg_ecg_graph (dot, callEd_graph);
 841       const char *callEd_name = get_irg_entity (callEd_graph) ?
 842         get_entity_name (get_irg_entity (callEd_graph)) : "noEntity";
 843       const char *direction = (callEd_no <= graph_no) ? "forward" : "forward";
 844       const char *callEd_color     = (callEd_no <= graph_no) ? "red" : "black";
 845
 846       fprintf (dot, "\t/* Call from graph \"%s\" to graph \"%s\" */\n",
 847                name,
 848                callEd_name);
 849       /* Check for recursive calls */
 850       /* if (callEd_no > graph_no) */ { /* do recursive calls (for now) */
 851         fprintf (dot, "\tcall_%i -> graph_%i:HEAD [color=\"%s\", dir=\"%s\"];\n",
 852                  call_no, callEd_no, callEd_color, direction);
 853       }
 854
 855       ced = ced->prev;
 856       /* ced = NULL; */
 857     } /* done all calEds (call) */
 858
 859     cinfo = cinfo->prev;
 860   } /* done all calls (graph) */
 861
 862   /* now the allocs */
 863   ainfo = ecg_get_alloc_info (graph);
 864   if (ainfo) {
 865     fprintf (dot, "\t/* now the allocs */\n");
 866   } else {
 867     fprintf (dot, "\t/* no allocs */\n");
 868   }
 869
 870   while (NULL != ainfo) {
 871     ir_node *alloc = ainfo->alloc;
 872     const char *name = get_type_name (ainfo->tp);
 873     const char *color = "red1";
 874
 875     _allocs ++;
 876     fprintf (dot, "\talloc_0x%08x_%i [label=\"%s\", color=\"%s\"];\n",
 877              (int) alloc, graph_no, name, color);
 878
 879     fprintf (dot, "\tgraph_%i -> alloc_0x%08x_%i;\n",
 880              graph_no, (int) alloc, graph_no);
 881
 882     ainfo = ainfo->prev;
 883   }
 884
 885   if (0 == ginfo->allocs_seen) {
 886     ginfo->allocs_seen = 1;
 887   }
 888
 889   /* write table of ctxs */
 890   {
 891     int i;
 892     const int max_ctxs = 30;
 893     const int n_ctxs = (ginfo->n_ctxs > max_ctxs) ? max_ctxs : ginfo->n_ctxs;
 894
 895     fprintf (dot, "\tctx_%i [label=\"<HEAD>", graph_no);
 896
 897     assert (ginfo->ctxs && "no ctx");
 898     for (i = 0; i < n_ctxs; i ++) {
 899       ctx_info_t *ctx_info = ginfo->ctxs [i];
 900
 901       if (NULL != ctx_info->enc) {
 902         fprintf (dot, "ctx_info \\[%i\\] = ctx\\[%i\\-\\>%i\\]\\l",
 903                  i,
 904                  ctx_info->id,
 905                  ctx_info->enc->id);
 906       } else {
 907         fprintf (dot, "ctx_info \\[%i\\] = ctx\\[%i\\]\\l",
 908                  i, ctx_info->id);
 909       }
 910
 911       if (i+1 != n_ctxs) {
 912         fprintf (dot, "|");
 913       }
 914     }
 915
 916     if (0 < ginfo->n_ctxs - max_ctxs) {
 917       fprintf (dot, "(%i more)\\l", ginfo->n_ctxs - max_ctxs);
 918     }
 919
 920     fprintf (dot, "\", color=\"green3\"];\n");
 921
 922     fprintf (dot,
 923              "\tgraph_%i:CTX -> ctx_%i:HEAD [label=\"ctx\", dir=\"none\", style=\"dotted\"];\n",
 924              graph_no, graph_no);
 925   }
 926
 927   fprintf (dot, "\t/* done with graph of \"%s\" */\n\n", name);
 928
 929   fflush (dot);
 930   ginfo->ecg_seen = 0;
 931
 932   return (graph_no);
 933 }
 934
 935 /**
 936    Count how many nodes the ECG will have
 937 */
 938 static char spaces [BUF_SIZE];
 939
 940 static void ecg_ecg_count (ir_graph *graph)
 941 {
 942   int graph_no;
 943   call_info_t *cinfo;
 944   graph_info_t *ginfo = (graph_info_t*) pmap_get (graph_infos, graph);
 945
 946   if (0 != ginfo->ecg_seen) {
 947     return;
 948   }
 949
 950   _depth ++;
 951   if (_depth > _max_depth) {
 952     _max_depth = _depth;
 953
 954     /*
 955       fprintf (stdout, "_max_depth = %i\n", _max_depth);
 956       fprintf (stdout, "\tn_graphs: %i\n", _graphs);
 957     */
 958   }
 959
 960   assert (0L <= _graphs);
 961
 962   /*
 963     if (0 == (_graphs % 1000000)) {
 964     fprintf (stdout, "\tn_graphs: %i\n", _graphs);
 965     fprintf (stdout, "_depth = %i\n", _depth);
 966     }
 967   */
 968
 969   graph_no = _graphs ++;
 970   ginfo->ecg_seen = graph_no;
 971
 972   fprintf (stdout, "%sMethod \"%s.%s\"\n",
 973            spaces + BUF_SIZE - _depth,
 974            get_type_name (get_entity_owner (get_irg_entity (graph))),
 975            get_entity_name (get_irg_entity (graph)));
 976
 977   cinfo = ginfo->calls;
 978   while (NULL != cinfo) {
 979
 980     callEd_info_t *ced = cinfo->callEds;
 981
 982     fprintf (stdout, "%sCall \"0x%08x\"\n",
 983              spaces + BUF_SIZE - _depth,
 984              (int) cinfo->call);
 985
 986     while (NULL != ced) {
 987       ir_graph *callEd_graph = ced->callEd;
 988
 989       fprintf (stdout, "%sCall Target \"%s.%s\"\n",
 990                spaces + BUF_SIZE - _depth,
 991                get_type_name (get_entity_owner (get_irg_entity (callEd_graph))),
 992                get_entity_name (get_irg_entity (callEd_graph)));
 993
 994       ecg_ecg_count (callEd_graph);
 995
 996       ced = ced->prev;
 997     } /* done all calEds (call) */
 998     cinfo = cinfo->prev;
 999   } /* done all calls (graph) */
1000
1001   ginfo->ecg_seen = 0;
1002   _depth --;
1003 }
1004
1005 /* ====================
1006    Public Interface
1007    ==================== */
1008
1009 /**
1010    Initialise our data structures.
1011 */
1012 void ecg_init (int typalise)
1013 {
1014   do_typalise = typalise;
1015
1016   if (typalise) {
1017     typalise_init ();
1018   }
1019
1020   graph_infos = pmap_create ();
1021
1022   ecg_fill_calls ();
1023   ecg_fill_ctxs ();
1024   ecg_ecg ();
1025 }
1026
1027 /**
1028    Clean up our mess.
1029 */
1030 void ecg_cleanup (void)
1031 {
1032   int i;
1033
1034   return;
1035
1036   for (i = 0; i < get_irp_n_irgs (); i++) {
1037     ir_graph *graph = get_irp_irg (i);
1038
1039     graph_info_t *info = pmap_get (graph_infos, graph);
1040     call_info_t *cinfo = info->calls;
1041
1042     while (NULL != cinfo) {
1043       callEd_info_t *ced = cinfo->callEds;
1044
1045       cinfo->call = NULL;
1046
1047       while (NULL != ced) {
1048         callEd_info_t *nced = ced->prev;
1049         free (ced);
1050         ced->prev = NULL;
1051         ced->callEd = NULL;
1052         ced = nced;
1053       }
1054
1055       cinfo->callEds = NULL;
1056
1057       free (cinfo);
1058       cinfo = cinfo->prev;
1059     }
1060
1061     free (info);
1062     pmap_insert (graph_infos, graph, NULL);
1063   }
1064
1065
1066   pmap_destroy (graph_infos);
1067
1068   /*  paranoia mode */
1069   graph_infos = NULL;
1070 }
1071
1072 /**
1073    Show what we have found.
1074 */
1075 void ecg_report ()
1076 {
1077   int i;
1078
1079   FILE *dot = fopen ("calls.dot", "w");
1080
1081   fprintf (dot, "digraph \"calls\" {\n");
1082   fprintf (dot, "\tgraph [rankdir=\"LR\", ordering=\"out\", size=\"11, 7\", rotate=\"90\", ratio=\"fill\"];\n");
1083   fprintf (dot, "\tnode [shape=\"record\", style=\"filled\"];\n");
1084   fprintf (dot, "\tedge [color=\"black\"];\n");
1085   fprintf (dot, "\n");
1086
1087   for (i = 0; i < get_irp_n_irgs (); i++) {
1088     ir_graph *graph = get_irp_irg (i);
1089     graph_info_t *ginfo = (graph_info_t*) pmap_get (graph_infos, graph);
1090
1091     if (0 != ginfo->n_ctxs) {
1092       call_info_t *cinfo;
1093       alloc_info_t *ainfo;
1094
1095       const char *name = get_irg_entity (graph) ?
1096         get_entity_name (get_irg_entity (graph)) : "noEntity";
1097
1098       const char *oname = get_type_name
1099         (get_entity_owner (get_irg_entity (graph)));
1100
1101       const char *color =
1102         (get_entity_stickyness
1103          (get_irg_entity (graph)) == stickyness_sticky) ?
1104         "red3" : "lightyellow";
1105
1106       fprintf (dot, "\t/* graph_0x%08x (\"%s\") */\n", (int) graph, name);
1107       fprintf (dot,
1108                "\tgraph_0x%08x [label=\"%s\\l%s\", color=\"%s\"];\n",
1109                (int) graph, oname, name, color);
1110       fprintf (dot, "\n");
1111
1112       cinfo = ginfo->calls;
1113       if (cinfo) {
1114         fprintf (dot, "\t/* now the calls */\n");
1115       } else {
1116         fprintf (dot, "\t/* no calls, nothing to see, move along! */\n");
1117       }
1118
1119       while (NULL != cinfo) {
1120         callEd_info_t *ced;
1121         ir_node *call = cinfo->call;
1122
1123         fprintf (dot, "\t/* call_0x%08x */\n", (int) call);
1124         fprintf (dot, "\tcall_0x%08x [label=\"call\\[%li\\]\", shape=\"ellipse\", color=\"lightblue\"];\n",
1125                  (int) call, get_irn_node_nr (call));
1126         fprintf (dot, "\tgraph_0x%08x -> call_0x%08x;\n",
1127                  (int) graph, (int) call);
1128
1129         ced = cinfo->callEds;
1130         while (NULL != ced) {
1131           fprintf (dot, "\tcall_0x%08x -> graph_0x%08x;\n",
1132                    (int) call, (int) ced->callEd);
1133           ced = ced->prev;
1134         }
1135         fprintf (dot, "\n");
1136
1137         cinfo = cinfo->prev;
1138       }
1139       fprintf (dot, "\n");
1140
1141       ainfo = ginfo->allocs;
1142       if (ainfo) {
1143         fprintf (dot, "\t/* now the allocs */\n");
1144       } else {
1145         fprintf (dot, "\t/* no allocs */\n");
1146       }
1147
1148       /* allocs */
1149       while (NULL != ainfo) {
1150         ir_node *alloc = ainfo->alloc;
1151         const char *name = get_type_name (ainfo->tp);
1152         const char *color = "red1";
1153
1154         fprintf (dot, "\talloc_0x%08x [label=\"%s\", color=\"%s\"];\n",
1155                  (int) alloc, name, color);
1156         fprintf (dot, "\tgraph_0x%08x -> alloc_0x%08x;\n",
1157                  (int) graph, (int) alloc);
1158
1159         ainfo = ainfo->prev;
1160       }
1161
1162       /* ctxs */
1163       {
1164         int i;
1165         const int max_ctxs = 30;
1166         const int n_ctxs = (ginfo->n_ctxs > max_ctxs) ? max_ctxs : ginfo->n_ctxs;
1167
1168         fprintf (dot, "\t/* now the ctxs */\n");
1169         fprintf (dot, "\tctx_0x%08x [label=\"<HEAD>", (int) graph);
1170
1171         assert (ginfo->ctxs && "no ctx");
1172         for (i = 0; i < n_ctxs; i ++) {
1173           ctx_info_t *ctx_info = ginfo->ctxs [i];
1174
1175           if (NULL != ctx_info->enc) {
1176             fprintf (dot, "ctx_info \\[%i\\] = ctx\\[%i\\-\\>%i\\]\\l",
1177                      i,
1178                      ctx_info->id,
1179                      ctx_info->enc->id);
1180           } else {
1181             fprintf (dot, "ctx_info \\[%i\\] = ctx\\[%i\\]\\l",
1182                      i, ctx_info->id);
1183           }
1184
1185           if (i+1 != n_ctxs) {
1186             fprintf (dot, "|");
1187           }
1188         }
1189
1190         if (0 < ginfo->n_ctxs - max_ctxs) {
1191           fprintf (dot, "(%i more)\\l", ginfo->n_ctxs - max_ctxs);
1192         }
1193
1194         fprintf (dot, "\", color=\"green3\"];\n");
1195
1196         fprintf (dot,
1197                  "\tgraph_0x%08x -> ctx_0x%08x:HEAD [label=\"ctx\", dir=\"none\", style=\"dotted\"];\n",
1198                  (int) graph, (int) graph);
1199       }
1200     } else {
1201       fprintf (dot, "\t/* graph is not called */\n");
1202     } /* end all graphs */
1203   }
1204   fprintf (dot, "}\n");
1205
1206   /*
1207     fprintf (stdout, " max_callEds: %i\n", _max_callEds);
1208     fprintf (stdout, " max_callEds_callR: \"%s\"\n",
1209     get_entity_name (_max_callEds_callR));
1210   */
1211   fclose (dot);
1212 }
1213
1214 /**
1215    Experimental:  Print the ecg
1216 */
1217 void ecg_ecg (void)
1218 {
1219   FILE *dot;
1220   ir_graph *main_graph = get_irp_main_irg ();
1221
1222   _graphs = 0;
1223   _calls  = 0;
1224
1225   /*
1226     memset (spaces, '.', BUF_SIZE);
1227     spaces [BUF_SIZE-1] = '\0';
1228
1229     ecg_ecg_count (main_graph);
1230     fprintf (stdout, "n_graphs: %i\n", _graphs);
1231     fprintf (stdout, "max_depth = %i\n", _max_depth);
1232   */
1233
1234   /* return; */
1235
1236   _graphs = 0;
1237   _calls  = 0;
1238
1239   dot = fopen ("ecg.dot", "w");
1240
1241   fprintf (dot, "digraph \"ecg\" {\n");
1242   fprintf (dot, "\tgraph [rankdir=\"LR\", ordering=\"out\", size=\"11, 7\", rotate=\"90\", ratio=\"fill\"];\n");
1243   fprintf (dot, "\tnode [shape=\"record\", style=\"filled\"];\n");
1244   fprintf (dot, "\tedge [color=\"black\"];\n");
1245   fprintf (dot, "\n");
1246   fprintf (dot, "\n");
1247
1248   /* ir_graph *main_graph = get_irp_main_irg (); */
1249   ecg_ecg_graph (dot, main_graph);
1250
1251   fprintf (dot, "\t/* Grand Total: */\n");
1252   fprintf (dot, "\t/* calls:  %i */\n", (int) _calls);
1253   fprintf (dot, "\t/* graphs: %i */\n", (int) _graphs);
1254   fprintf (dot, "\t/* allocs: %i */\n", (int) _allocs);
1255   fprintf (dot, "\t/* (sales tax not included) */\n");
1256
1257   fprintf (dot, "}\n");
1258
1259   fclose (dot);
1260 }
1261
1262 \f
1263
1264 /*
1265   $Log$
1266   Revision 1.19  2005/03/22 13:55:51  liekweg
1267   Need to initialise typalise now
1268
1269   Revision 1.18  2005/01/14 14:14:43  liekweg
1270   fix gnu extension
1271
1272   Revision 1.17  2005/01/14 13:34:25  liekweg
1273   Factor out call_info_t ctor; fix mallocs; fix initialisation
1274
1275   Revision 1.16  2005/01/10 17:26:34  liekweg
1276   fixup printfs, don't put environments on the stack
1277
1278   Revision 1.15  2004/12/23 15:40:03  beck
1279   used new xcalloc
1280
1281   Revision 1.14  2004/12/22 14:43:14  beck
1282   made allocations C-like
1283
1284   Revision 1.13  2004/12/21 14:21:16  beck
1285   removed C99 constructs
1286
1287   Revision 1.12  2004/12/20 17:34:34  liekweg
1288   fix recursion handling
1289
1290   Revision 1.11  2004/12/15 09:18:18  liekweg
1291   pto_name.c
1292
1293   Revision 1.10  2004/12/06 12:55:06  liekweg
1294   actually iterate
1295
1296   Revision 1.9  2004/12/02 16:17:50  beck
1297   fixed config.h include
1298
1299   Revision 1.8  2004/11/30 14:45:44  liekweg
1300   fix graph dumping, remove 'HERE's
1301
1302   Revision 1.7  2004/11/26 16:01:56  liekweg
1303   debugging annotations
1304
1305   Revision 1.6  2004/11/24 14:53:55  liekweg
1306   Bugfixes
1307
1308   Revision 1.5  2004/11/20 21:20:29  liekweg
1309   Added iterator functions
1310
1311   Revision 1.4  2004/11/18 16:36:37  liekweg
1312   Added unique ids for debugging, added access functions
1313
1314   Revision 1.3  2004/11/04 14:54:44  liekweg
1315   Nicer Colors
1316
1317   Revision 1.2  2004/10/21 11:09:37  liekweg
1318   Moved memwalk stuf into irmemwalk
1319   Moved lset stuff into lset
1320   Moved typalise stuff into typalise
1321
1322   Revision 1.1  2004/10/20 14:59:41  liekweg
1323   Added ana2, added ecg and pto
1324
1325   Revision 1.6  2004/10/18 12:47:19  liekweg
1326   minor fix
1327
1328   Revision 1.5  2004/10/14 11:31:28  liekweg
1329   SHUTUP_GCC
1330
1331   Revision 1.4  2004/10/12 11:02:01  liekweg
1332   wtf?
1333
1334 */