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