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   while (NULL != ginfo) {
 444     ginfo->ctxs = (ctx_info_t **) xmalloc (ginfo->n_ctxs * sizeof (ctx_info_t*));
 445
 446     /*
 447       fprintf (stdout, "graph of \"%s\": n_ctxs = %i\n",
 448       get_entity_name (get_irg_entity (ginfo->graph)), ginfo->n_ctxs);
 449     */
 450     ginfo->n_ctxs = 0;
 451
 452     assert (ginfo != ginfo->prev);
 453     ginfo = ginfo->prev;
 454   }
 455 }
 456
 457 /**
 458    Fill in the ctxs parts of the graph_infos
 459 */
 460 static void ecg_fill_ctxs_write (ir_graph *graph, ctx_info_t *enc_ctx)
 461 {
 462   graph_info_t *ginfo = ecg_get_info (graph);
 463
 464   /* enter a new ctx for all callEds along the call edges of this graph */
 465   if (0 == ginfo->ecg_seen) {
 466     ginfo->ecg_seen = 1;
 467     call_info_t *cinfo = ginfo->calls;
 468
 469     while (NULL != cinfo) {
 470       callEd_info_t *ced = cinfo->callEds;
 471
 472       while (NULL != ced) {
 473         ctx_info_t *ctx = new_ctx (graph, cinfo->call, enc_ctx);
 474
 475         ir_graph *callEd_graph = ced->callEd;
 476
 477         /* write the ctx of this call into the callEd graph */
 478         graph_info_t *callEd_info = ecg_get_info (callEd_graph);
 479
 480         callEd_info->ctxs [callEd_info->n_ctxs] = ctx;
 481         callEd_info->n_ctxs ++;
 482
 483         /* Calling graph -> callEd_graph */
 484         ecg_fill_ctxs_write (callEd_graph, ctx);
 485
 486         ced = ced->prev;
 487       } /* end forall callEds (call) */
 488
 489       cinfo = cinfo->prev;
 490     } /* end forall (calls(graph)) */
 491
 492     ginfo->ecg_seen = 0;
 493   }
 494 }
 495
 496 /**
 497    Fill in the ctxs parts of the graph_infos
 498 */
 499 static void ecg_fill_ctxs (void)
 500 {
 501   ecg_fill_ctxs_count (get_irp_main_irg ());
 502   ecg_fill_ctxs_alloc ();
 503
 504   ctx_info_t *main_ctx = new_ctx (get_irp_main_irg (), NULL, NULL);
 505   ir_graph *main_irg = get_irp_main_irg ();
 506
 507   set_main_ctx (main_ctx);
 508
 509   /* Grrr, have to add this ctx manually to main.ginfo ... */
 510   graph_info_t *ginfo = ecg_get_info (main_irg);
 511   ginfo->n_ctxs = 1;
 512   ginfo->ctxs = (ctx_info_t **) xmalloc (1 * sizeof (ctx_info_t*));
 513   ginfo->ctxs [0] = main_ctx;
 514
 515   ecg_fill_ctxs_write (main_irg, main_ctx);
 516 }
 517
 518 /* ====================
 519    CTX stuff
 520    ==================== */
 521 /*
 522   Nicely print a ctx_info_t to the given output stream
 523 */
 524 void ecg_print_ctx (ctx_info_t *ctx, FILE *stream)
 525 {
 526   entity *ent = get_irg_ent (ctx->graph);
 527   ir_node *call = ctx->call;
 528   const char *ent_name = (char*) get_entity_name (ent);
 529   const char *own_name = (char*) get_type_name (get_entity_owner (ent));
 530
 531   fprintf (stream, "CTX[%i](%s.%s->%s[%li])",
 532            ctx->id, own_name, ent_name,
 533            get_op_name (get_irn_op (call)),
 534            get_irn_node_nr (call));
 535
 536   if (NULL != ctx->enc) {
 537     fprintf (stream, "->%i", ctx->enc->id);
 538   }
 539
 540   fprintf (stream, "\n");
 541 }
 542
 543 /*
 544   Get a ctx of the given graph info
 545 */
 546 ctx_info_t *get_ctx (graph_info_t *ginfo, int ctx_idx)
 547 {
 548   assert (ginfo->n_ctxs > ctx_idx);
 549
 550   return (ginfo->ctxs [ctx_idx]);
 551 }
 552
 553 /*
 554   Get the pseudo-ctx of 'main'
 555 */
 556 ctx_info_t *get_main_ctx ()
 557 {
 558   return (main_ctx);
 559 }
 560
 561 /*
 562   Set the pseudo-ctx of 'main'
 563 */
 564 void set_main_ctx (ctx_info_t *ctx)
 565 {
 566   main_ctx = ctx;
 567 }
 568
 569
 570 /* ====================
 571    ECG stuff
 572    ==================== */
 573
 574 /* ====================
 575    Iterator stuff
 576    ==================== */
 577 /*
 578    Iterate over all graphs
 579 */
 580 void ecg_iterate_graphs (graph_hnd_t *hnd, void *env)
 581 {
 582   graph_info_t *ginfo = graph_infos_list;
 583
 584   while (NULL != ginfo) {
 585     /* do not visit graphs that have 0 == ginfo->n_ctxs, since they
 586        are not called */
 587     if (0 != ginfo->n_ctxs) {
 588       hnd (ginfo, env);
 589     }
 590
 591     ginfo = ginfo->prev;
 592   }
 593 }
 594
 595
 596 /*
 597    Iterate of all allocs of a given graph info
 598 */
 599 void ecg_iterate_allocs (graph_info_t *ginfo, alloc_hnd_t *hnd, void *env)
 600 {
 601   alloc_info_t *ainfo = ginfo->allocs;
 602
 603   while (NULL != ainfo) {
 604     hnd (ainfo, env);
 605
 606     ainfo = ainfo->prev;
 607   }
 608 }
 609
 610
 611 /*
 612   Iterate over all calls of the given graph info
 613 */
 614 void ecg_iterate_calls  (graph_info_t *ginfo, call_hnd_t *hnd, void *env)
 615 {
 616   call_info_t *cinfo = ginfo->calls;
 617
 618   while (NULL != cinfo) {
 619     hnd (cinfo, env);
 620
 621     cinfo = cinfo->prev;
 622   }
 623 }
 624
 625
 626 /*
 627   Iterate over all callEds of the given call info
 628 */
 629 void ecg_iterate_callEds  (call_info_t *cinfo, callEd_hnd_t *hnd, void *env)
 630 {
 631   callEd_info_t *ced = cinfo->callEds;
 632
 633   while (NULL != ced) {
 634     hnd (ced, env);
 635
 636     ced = ced->prev;
 637   }
 638 }
 639
 640
 641 /*
 642   get the call infos for the given graph
 643 */
 644 graph_info_t *ecg_get_info (ir_graph *graph)
 645 {
 646   graph_info_t *ginfo = (graph_info_t*) pmap_get (graph_infos, graph);
 647
 648   assert (ginfo && "no info for graph");
 649
 650   return (ginfo);
 651 }
 652
 653 /*
 654   Get the Alloc Infos for the given graph
 655 */
 656 alloc_info_t *ecg_get_alloc_info (ir_graph *graph)
 657 {
 658   graph_info_t *ginfo = ecg_get_info (graph);
 659
 660   return (ginfo->allocs);
 661 }
 662
 663 /*
 664   Get the Call Info for the given call
 665 */
 666 callEd_info_t *ecg_get_callEd_info (ir_node *call)
 667 {
 668   ir_graph *graph = get_irn_irg (call);
 669   graph_info_t *ginfo = ecg_get_info (graph);
 670
 671   call_info_t *call_info = ginfo->calls;
 672
 673   while (NULL != call_info) {
 674     if (call == call_info->call) {
 675       return (call_info->callEds);
 676     }
 677
 678     call_info = call_info->prev;
 679   }
 680
 681   return (NULL);
 682 }
 683
 684
 685 /**
 686    Dump the given graph and it's calls and it's calls callEds to the given file.
 687 */
 688 static int ecg_ecg_graph (FILE *dot, ir_graph *graph)
 689 {
 690   const char *name = get_irg_entity (graph) ?
 691     get_entity_name (get_irg_entity (graph)) : "noEntity";
 692   const char *color =
 693     (get_entity_stickyness
 694      (get_irg_entity (graph)) == stickyness_sticky) ?
 695     "red" : "lightyellow";
 696
 697   /* graph_info_t *ginfo = (graph_info_t*) pmap_get (graph_infos, graph); */
 698   graph_info_t *ginfo = ecg_get_info (graph);
 699
 700   if (0 != ginfo->ecg_seen) {
 701     fprintf (dot, "\t/* recursive call to \"%s\" (%d) */\n",
 702              name, (int) ginfo->ecg_seen);
 703 # if 0
 704     fprintf (dot, "\t/* recursive call to \"%s\" (0x%08x) */\n",
 705              name, (int) graph);
 706 # endif /* 0 */
 707     return (ginfo->ecg_seen);
 708   }
 709
 710   assert (0L <= _graphs);
 711
 712   const int graph_no = _graphs ++;
 713   ginfo->ecg_seen = graph_no;
 714
 715   fprintf (dot, "\t/* Graph of \"%s.%s\" */\n",
 716            get_type_name (get_entity_owner (get_irg_entity (graph))),
 717            name);
 718   fprintf (dot, "\tgraph_%i [label=\"<HEAD>%s\\l%s\\l|<CTX>n_ctx = %i\\l\", color=\"%s\"];\n",
 719            graph_no,
 720            get_type_name (get_entity_owner (get_irg_entity (graph))),
 721            name,
 722            ginfo->n_ctxs,
 723            color);
 724   fprintf (dot, "\n");
 725
 726   if (visibility_external_allocated ==
 727       get_entity_visibility (get_irg_entity (graph))) {
 728     fprintf (dot, "\t/* graph \"%s\" is external */\n", name);
 729
 730     return (graph_no);
 731   }
 732
 733   call_info_t *cinfo = ginfo->calls;
 734   while (NULL != cinfo) {
 735     ir_node *call = cinfo->call;
 736     callEd_info_t *ced = cinfo->callEds;
 737     const int call_no = _calls ++;
 738     const char *call_color = (NULL == ced) ? "blue" :
 739       (NULL == ced->prev) ? "lightblue" : "blue3";
 740
 741     fprintf (dot, "\t/* Call %li */\n", get_irn_node_nr (call));
 742     fprintf (dot, "\tcall_%i [label=\"call\\[%li\\]\", color=\"%s\", shape=\"ellipse\"];\n",
 743              call_no, get_irn_node_nr (call), call_color);
 744     fprintf (dot, "\tgraph_%i -> call_%i [color=\"black\"];\n", graph_no, call_no);
 745
 746     while (NULL != ced) {
 747       ir_graph *callEd_graph = ced->callEd;
 748       const int callEd_no = ecg_ecg_graph (dot, callEd_graph);
 749       const char *callEd_name = get_irg_entity (callEd_graph) ?
 750         get_entity_name (get_irg_entity (callEd_graph)) : "noEntity";
 751       const char *direction = (callEd_no <= graph_no) ? "forward" : "forward";
 752       const char *callEd_color     = (callEd_no <= graph_no) ? "red" : "black";
 753
 754       fprintf (dot, "\t/* Call from graph \"%s\" to graph \"%s\" */\n",
 755                name,
 756                callEd_name);
 757       /* Check for recursive calls */
 758       /* if (callEd_no > graph_no) */ { /* do recursive calls (for now) */
 759         fprintf (dot, "\tcall_%i -> graph_%i:HEAD [color=\"%s\", dir=\"%s\"];\n",
 760                  call_no, callEd_no, callEd_color, direction);
 761       }
 762
 763       ced = ced->prev;
 764       /* ced = NULL; */
 765     } /* done all calEds (call) */
 766
 767     cinfo = cinfo->prev;
 768   } /* done all calls (graph) */
 769
 770   /* now the allocs */
 771   alloc_info_t *ainfo = ecg_get_alloc_info (graph);
 772   if (ainfo) {
 773     fprintf (dot, "\t/* now the allocs */\n");
 774   } else {
 775     fprintf (dot, "\t/* no allocs */\n");
 776   }
 777
 778   while (NULL != ainfo) {
 779     ir_node *alloc = ainfo->alloc;
 780     const char *name = get_type_name (ainfo->tp);
 781     const char *color = "red1";
 782
 783     _allocs ++;
 784     fprintf (dot, "\talloc_0x%08x_%i [label=\"%s\", color=\"%s\"];\n",
 785              (int) alloc, graph_no, name, color);
 786
 787     fprintf (dot, "\tgraph_%i -> alloc_0x%08x_%i;\n",
 788              graph_no, (int) alloc, graph_no);
 789
 790     ainfo = ainfo->prev;
 791   }
 792
 793   if (0 == ginfo->allocs_seen) {
 794     ginfo->allocs_seen = 1;
 795   }
 796
 797   /* write table of ctxs */
 798   {
 799     fprintf (dot, "\tctx_%i [label=\"<HEAD>", graph_no);
 800
 801     int i;
 802     const int max_ctxs = 30;
 803     const int n_ctxs = (ginfo->n_ctxs > max_ctxs) ? max_ctxs : ginfo->n_ctxs;
 804
 805     assert (ginfo->ctxs && "no ctx");
 806     for (i = 0; i < n_ctxs; i ++) {
 807       ctx_info_t *ctx_info = ginfo->ctxs [i];
 808
 809       if (NULL != ctx_info->enc) {
 810         fprintf (dot, "ctx_info \\[%i\\] = ctx\\[%i\\-\\>%i\\]\\l",
 811                  i,
 812                  ctx_info->id,
 813                  ctx_info->enc->id);
 814       } else {
 815         fprintf (dot, "ctx_info \\[%i\\] = ctx\\[%i\\]\\l",
 816                  i, ctx_info->id);
 817       }
 818
 819       if (i+1 != n_ctxs) {
 820         fprintf (dot, "|");
 821       }
 822     }
 823
 824     if (0 < ginfo->n_ctxs - max_ctxs) {
 825       fprintf (dot, "(%i more)\\l", ginfo->n_ctxs - max_ctxs);
 826     }
 827
 828     fprintf (dot, "\", color=\"green3\"];\n");
 829
 830     fprintf (dot,
 831              "\tgraph_%i:CTX -> ctx_%i:HEAD [label=\"ctx\", dir=\"none\", style=\"dotted\"];\n",
 832              graph_no, graph_no);
 833   }
 834
 835   fprintf (dot, "\t/* done with graph of \"%s\" */\n\n", name);
 836
 837   fflush (dot);
 838   ginfo->ecg_seen = 0;
 839
 840   return (graph_no);
 841 }
 842
 843 /**
 844    Count how many nodes the ECG will have
 845 */
 846 static char spaces [BUF_SIZE];
 847
 848 static void ecg_ecg_count (ir_graph *graph)
 849 {
 850   graph_info_t *ginfo = (graph_info_t*) pmap_get (graph_infos, graph);
 851
 852   if (0 != ginfo->ecg_seen) {
 853     return;
 854   }
 855
 856   _depth ++;
 857   if (_depth > _max_depth) {
 858     _max_depth = _depth;
 859
 860     /*
 861       fprintf (stdout, "_max_depth = %i\n", _max_depth);
 862       fprintf (stdout, "\tn_graphs: %i\n", _graphs);
 863     */
 864   }
 865
 866   assert (0L <= _graphs);
 867
 868   /*
 869     if (0 == (_graphs % 1000000)) {
 870     fprintf (stdout, "\tn_graphs: %i\n", _graphs);
 871     fprintf (stdout, "_depth = %i\n", _depth);
 872     }
 873   */
 874
 875   const int graph_no = _graphs ++;
 876   ginfo->ecg_seen = graph_no;
 877
 878   fprintf (stdout, "%sMethod \"%s.%s\"\n",
 879            spaces + BUF_SIZE - _depth,
 880            get_type_name (get_entity_owner (get_irg_entity (graph))),
 881            get_entity_name (get_irg_entity (graph)));
 882
 883   call_info_t *cinfo = ginfo->calls;
 884   while (NULL != cinfo) {
 885
 886     callEd_info_t *ced = cinfo->callEds;
 887
 888     fprintf (stdout, "%sCall \"0x%08x\"\n",
 889              spaces + BUF_SIZE - _depth,
 890              (int) cinfo->call);
 891
 892     while (NULL != ced) {
 893       ir_graph *callEd_graph = ced->callEd;
 894
 895       fprintf (stdout, "%sCall Target \"%s.%s\"\n",
 896                spaces + BUF_SIZE - _depth,
 897                get_type_name (get_entity_owner (get_irg_entity (callEd_graph))),
 898                get_entity_name (get_irg_entity (callEd_graph)));
 899
 900       ecg_ecg_count (callEd_graph);
 901
 902       ced = ced->prev;
 903     } /* done all calEds (call) */
 904     cinfo = cinfo->prev;
 905   } /* done all calls (graph) */
 906
 907   ginfo->ecg_seen = 0;
 908   _depth --;
 909 }
 910
 911 /* ====================
 912    Public Interface
 913    ==================== */
 914
 915 /**
 916    Initialise our data structures.
 917 */
 918 void ecg_init (int typalise)
 919 {
 920   do_typalise = typalise;
 921
 922   graph_infos = pmap_create ();
 923
 924   ecg_fill_calls ();
 925   ecg_fill_ctxs ();
 926   ecg_ecg ();
 927 }
 928
 929 /**
 930    Clean up our mess.
 931 */
 932 void ecg_cleanup ()
 933 {
 934   return;
 935
 936   int i;
 937
 938   for (i = 0; i < get_irp_n_irgs (); i++) {
 939     ir_graph *graph = get_irp_irg (i);
 940
 941     graph_info_t *info = pmap_get (graph_infos, graph);
 942     call_info_t *cinfo = info->calls;
 943
 944     while (NULL != cinfo) {
 945       cinfo->call = NULL;
 946
 947       callEd_info_t *ced = cinfo->callEds;
 948
 949       while (NULL != ced) {
 950         callEd_info_t *nced = ced->prev;
 951         free (ced);
 952         ced->prev = NULL;
 953         ced->callEd = NULL;
 954         ced = nced;
 955       }
 956
 957       cinfo->callEds = NULL;
 958
 959       free (cinfo);
 960       cinfo = cinfo->prev;
 961     }
 962
 963     free (info);
 964     pmap_insert (graph_infos, graph, NULL);
 965   }
 966
 967
 968   pmap_destroy (graph_infos);
 969
 970   /*  paranoia mode */
 971   graph_infos = NULL;
 972 }
 973
 974 /**
 975    Show what we have found.
 976 */
 977 void ecg_report ()
 978 {
 979   int i;
 980
 981   FILE *dot = fopen ("calls.dot", "w");
 982
 983   fprintf (dot, "digraph \"calls\" {\n");
 984   fprintf (dot, "\tgraph [rankdir=\"LR\", ordering=\"out\"];\n");
 985   fprintf (dot, "\tnode [shape = \"record\", style = \"filled\"];\n");
 986   fprintf (dot, "\tedge [color = \"black\"];\n");
 987   fprintf (dot, "\n");
 988   fprintf (dot, "\tsize = \"11, 7\";\n");
 989   fprintf (dot, "\trotate = \"90\";\n");
 990   fprintf (dot, "\tratio = \"fill\";\n");
 991   fprintf (dot, "\n");
 992
 993   for (i = 0; i < get_irp_n_irgs (); i++) {
 994     ir_graph *graph = get_irp_irg (i);
 995     graph_info_t *info = (graph_info_t*) pmap_get (graph_infos, graph);
 996
 997     const char *name = get_irg_entity (graph) ?
 998       get_entity_name (get_irg_entity (graph)) : "noEntity";
 999
1000     const char *oname = get_type_name
1001       (get_entity_owner (get_irg_entity (graph)));
1002
1003     const char *color =
1004       (get_entity_stickyness
1005        (get_irg_entity (graph)) == stickyness_sticky) ?
1006       "red3" : "lightyellow";
1007
1008     fprintf (dot, "\t/* graph_0x%08x (\"%s\") */\n", (int) graph, name);
1009     fprintf (dot,
1010              "\tgraph_0x%08x [label=\"%s\\l%s\", color=\"%s\"];\n",
1011              (int) graph, oname, name, color);
1012     fprintf (dot, "\n");
1013
1014     call_info_t *cinfo = info->calls;
1015     if (cinfo) {
1016       fprintf (dot, "\t/* now the calls */\n");
1017     } else {
1018       fprintf (dot, "\t/* no calls, nothing to see, move along! */\n");
1019     }
1020
1021     while (NULL != cinfo) {
1022       ir_node *call = cinfo->call;
1023
1024       fprintf (dot, "\t/* call_0x%08x */\n", (int) call);
1025       fprintf (dot, "\tcall_0x%08x [label=\"call\\[%li\\]\\l0x%08x\"];\n",
1026                (int) call, get_irn_node_nr (call), (int) call);
1027       fprintf (dot, "\tgraph_0x%08x -> call_0x%08x;\n",
1028                (int) graph, (int) call);
1029
1030       callEd_info_t *ced = cinfo->callEds;
1031       while (NULL != ced) {
1032         fprintf (dot, "\tcall_0x%08x -> graph_0x%08x;\n",
1033                  (int) call, (int) ced->callEd);
1034         ced = ced->prev;
1035       }
1036       fprintf (dot, "\n");
1037
1038       cinfo = cinfo->prev;
1039     }
1040     fprintf (dot, "\n");
1041
1042     alloc_info_t *ainfo = info->allocs;
1043     if (ainfo) {
1044       fprintf (dot, "\t/* now the allocs */\n");
1045     } else {
1046       fprintf (dot, "\t/* no allocs */\n");
1047     }
1048
1049
1050     while (NULL != ainfo) {
1051       ir_node *alloc = ainfo->alloc;
1052       const char *name = get_type_name (ainfo->tp);
1053       const char *color = "green3";
1054
1055       fprintf (dot, "\talloc_0x%08x [label=\"%s\", color=\"%s\"];\n",
1056                (int) alloc, name, color);
1057       fprintf (dot, "\tgraph_0x%08x -> alloc_0x%08x;\n",
1058                (int) graph, (int) alloc);
1059
1060       ainfo = ainfo->prev;
1061     }
1062   }
1063   fprintf (dot, "}\n");
1064
1065   /*
1066     fprintf (stdout, " max_callEds: %i\n", _max_callEds);
1067     fprintf (stdout, " max_callEds_callR: \"%s\"\n",
1068     get_entity_name (_max_callEds_callR));
1069   */
1070   fclose (dot);
1071 }
1072
1073 /**
1074    Experimental:  Print the ecg
1075 */
1076 void ecg_ecg ()
1077 {
1078   _graphs = 0;
1079   _calls  = 0;
1080
1081   ir_graph *main_graph = get_irp_main_irg ();
1082
1083   /*
1084     memset (spaces, '.', BUF_SIZE);
1085     spaces [BUF_SIZE-1] = '\0';
1086
1087     ecg_ecg_count (main_graph);
1088     fprintf (stdout, "n_graphs: %i\n", _graphs);
1089     fprintf (stdout, "max_depth = %i\n", _max_depth);
1090   */
1091
1092   /* return; */
1093
1094   _graphs = 0;
1095   _calls  = 0;
1096
1097   FILE *dot = fopen ("ecg.dot", "w");
1098
1099   fprintf (dot, "digraph \"ecg\" {\n");
1100   fprintf (dot, "\tnode [shape = \"record\", style = \"filled\"];\n");
1101   fprintf (dot, "\tedge [color = \"black\"];\n");
1102   fprintf (dot, "\n");
1103   fprintf (dot, "\tsize = \"11, 7\";\n");
1104   fprintf (dot, "\trotate = \"90\";\n");
1105   fprintf (dot, "\tratio = \"fill\";\n");
1106   fprintf (dot, "\trankdir = \"LR\";\n");
1107   fprintf (dot, "\n");
1108
1109   /* ir_graph *main_graph = get_irp_main_irg (); */
1110   ecg_ecg_graph (dot, main_graph);
1111
1112   fprintf (dot, "\t/* Grand Total: */\n");
1113   fprintf (dot, "\t/* calls:  %i */\n", (int) _calls);
1114   fprintf (dot, "\t/* graphs: %i */\n", (int) _graphs);
1115   fprintf (dot, "\t/* allocs: %i */\n", (int) _allocs);
1116   fprintf (dot, "\t/* (sales tax not included) */\n");
1117
1118   fprintf (dot, "}\n");
1119
1120   fclose (dot);
1121 }
1122
1123 \f
1124
1125 /*
1126   $Log$
1127   Revision 1.10  2004/12/06 12:55:06  liekweg
1128   actually iterate
1129
1130   Revision 1.9  2004/12/02 16:17:50  beck
1131   fixed config.h include
1132
1133   Revision 1.8  2004/11/30 14:45:44  liekweg
1134   fix graph dumping, remove 'HERE's
1135
1136   Revision 1.7  2004/11/26 16:01:56  liekweg
1137   debugging annotations
1138
1139   Revision 1.6  2004/11/24 14:53:55  liekweg
1140   Bugfixes
1141
1142   Revision 1.5  2004/11/20 21:20:29  liekweg
1143   Added iterator functions
1144
1145   Revision 1.4  2004/11/18 16:36:37  liekweg
1146   Added unique ids for debugging, added access functions
1147
1148   Revision 1.3  2004/11/04 14:54:44  liekweg
1149   Nicer Colors
1150
1151   Revision 1.2  2004/10/21 11:09:37  liekweg
1152   Moved memwalk stuf into irmemwalk
1153   Moved lset stuff into lset
1154   Moved typalise stuff into typalise
1155
1156   Revision 1.1  2004/10/20 14:59:41  liekweg
1157   Added ana2, added ecg and pto
1158
1159   Revision 1.6  2004/10/18 12:47:19  liekweg
1160   minor fix
1161
1162   Revision 1.5  2004/10/14 11:31:28  liekweg
1163   SHUTUP_GCC
1164
1165   Revision 1.4  2004/10/12 11:02:01  liekweg
1166   wtf?
1167
1168 */