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