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->prev) ? "lightblue" : "blue3";
 739
 740     fprintf (dot, "\t/* Call %li */\n", get_irn_node_nr (call));
 741     fprintf (dot, "\tcall_%i [label=\"call\\[%li\\]\", color=\"%s\", shape=\"ellipse\"];\n",
 742              call_no, get_irn_node_nr (call), call_color);
 743     fprintf (dot, "\tgraph_%i -> call_%i [color=\"black\"];\n", graph_no, call_no);
 744
 745     while (NULL != ced) {
 746       ir_graph *callEd_graph = ced->callEd;
 747       const int callEd_no = ecg_ecg_graph (dot, callEd_graph);
 748       const char *callEd_name = get_irg_entity (callEd_graph) ?
 749         get_entity_name (get_irg_entity (callEd_graph)) : "noEntity";
 750       const char *direction = (callEd_no <= graph_no) ? "forward" : "forward";
 751       const char *callEd_color     = (callEd_no <= graph_no) ? "red" : "black";
 752
 753       fprintf (dot, "\t/* Call from graph \"%s\" to graph \"%s\" */\n",
 754                name,
 755                callEd_name);
 756       /* Check for recursive calls */
 757       /* if (callEd_no > graph_no) */ { /* do recursive calls (for now) */
 758         fprintf (dot, "\tcall_%i -> graph_%i:HEAD [color=\"%s\", dir=\"%s\"];\n",
 759                  call_no, callEd_no, callEd_color, direction);
 760       }
 761
 762       ced = ced->prev;
 763       /* ced = NULL; */
 764     } /* done all calEds (call) */
 765
 766     cinfo = cinfo->prev;
 767   } /* done all calls (graph) */
 768
 769   /* now the allocs */
 770   alloc_info_t *ainfo = ecg_get_alloc_info (graph);
 771   if (ainfo) {
 772     fprintf (dot, "\t/* now the allocs */\n");
 773   } else {
 774     fprintf (dot, "\t/* no allocs */\n");
 775   }
 776
 777   while (NULL != ainfo) {
 778     ir_node *alloc = ainfo->alloc;
 779     const char *name = get_type_name (ainfo->tp);
 780     const char *color = "red1";
 781
 782     _allocs ++;
 783     fprintf (dot, "\talloc_0x%08x_%i [label=\"%s\", color=\"%s\"];\n",
 784              (int) alloc, graph_no, name, color);
 785
 786     fprintf (dot, "\tgraph_%i -> alloc_0x%08x_%i;\n",
 787              graph_no, (int) alloc, graph_no);
 788
 789     ainfo = ainfo->prev;
 790   }
 791
 792   if (0 == ginfo->allocs_seen) {
 793     ginfo->allocs_seen = 1;
 794   }
 795
 796   /* write table of ctxs */
 797   {
 798     fprintf (dot, "\tctx_%i [label=\"<HEAD>", graph_no);
 799
 800     int i;
 801     const int max_ctxs = 30;
 802     const int n_ctxs = (ginfo->n_ctxs > max_ctxs) ? max_ctxs : ginfo->n_ctxs;
 803
 804     assert (ginfo->ctxs && "no ctx");
 805     for (i = 0; i < n_ctxs; i ++) {
 806       ctx_info_t *ctx_info = ginfo->ctxs [i];
 807
 808       if (NULL != ctx_info->enc) {
 809         fprintf (dot, "ctx_info \\[%i\\] = ctx\\[%i\\-\\>%i\\]\\l",
 810                  i,
 811                  ctx_info->id,
 812                  ctx_info->enc->id);
 813       } else {
 814         fprintf (dot, "ctx_info \\[%i\\] = ctx\\[%i\\]\\l",
 815                  i, ctx_info->id);
 816       }
 817
 818       if (i+1 != n_ctxs) {
 819         fprintf (dot, "|");
 820       }
 821     }
 822
 823     if (0 < ginfo->n_ctxs - max_ctxs) {
 824       fprintf (dot, "(%i more)\\l", ginfo->n_ctxs - max_ctxs);
 825     }
 826
 827     fprintf (dot, "\", color=\"green3\"];\n");
 828
 829     fprintf (dot,
 830              "\tgraph_%i:CTX -> ctx_%i:HEAD [label=\"ctx\", dir=\"none\", style=\"dotted\"];\n",
 831              graph_no, graph_no);
 832   }
 833
 834   fprintf (dot, "\t/* done with graph of \"%s\" */\n\n", name);
 835
 836   fflush (dot);
 837   ginfo->ecg_seen = 0;
 838
 839   return (graph_no);
 840 }
 841
 842 /**
 843    Count how many nodes the ECG will have
 844 */
 845 static char spaces [BUF_SIZE];
 846
 847 static void ecg_ecg_count (ir_graph *graph)
 848 {
 849   graph_info_t *ginfo = (graph_info_t*) pmap_get (graph_infos, graph);
 850
 851   if (0 != ginfo->ecg_seen) {
 852     return;
 853   }
 854
 855   _depth ++;
 856   if (_depth > _max_depth) {
 857     _max_depth = _depth;
 858
 859     /*
 860       fprintf (stdout, "_max_depth = %i\n", _max_depth);
 861       fprintf (stdout, "\tn_graphs: %i\n", _graphs);
 862     */
 863   }
 864
 865   assert (0L <= _graphs);
 866
 867   /*
 868     if (0 == (_graphs % 1000000)) {
 869     fprintf (stdout, "\tn_graphs: %i\n", _graphs);
 870     fprintf (stdout, "_depth = %i\n", _depth);
 871     }
 872   */
 873
 874   const int graph_no = _graphs ++;
 875   ginfo->ecg_seen = graph_no;
 876
 877   fprintf (stdout, "%sMethod \"%s.%s\"\n",
 878            spaces + BUF_SIZE - _depth,
 879            get_type_name (get_entity_owner (get_irg_entity (graph))),
 880            get_entity_name (get_irg_entity (graph)));
 881
 882   call_info_t *cinfo = ginfo->calls;
 883   while (NULL != cinfo) {
 884
 885     callEd_info_t *ced = cinfo->callEds;
 886
 887     fprintf (stdout, "%sCall \"0x%08x\"\n",
 888              spaces + BUF_SIZE - _depth,
 889              (int) cinfo->call);
 890
 891     while (NULL != ced) {
 892       ir_graph *callEd_graph = ced->callEd;
 893
 894       fprintf (stdout, "%sCall Target \"%s.%s\"\n",
 895                spaces + BUF_SIZE - _depth,
 896                get_type_name (get_entity_owner (get_irg_entity (callEd_graph))),
 897                get_entity_name (get_irg_entity (callEd_graph)));
 898
 899       ecg_ecg_count (callEd_graph);
 900
 901       ced = ced->prev;
 902     } /* done all calEds (call) */
 903     cinfo = cinfo->prev;
 904   } /* done all calls (graph) */
 905
 906   ginfo->ecg_seen = 0;
 907   _depth --;
 908 }
 909
 910 /* ====================
 911    Public Interface
 912    ==================== */
 913
 914 /**
 915    Initialise our data structures.
 916 */
 917 void ecg_init (int typalise)
 918 {
 919   do_typalise = typalise;
 920
 921   graph_infos = pmap_create ();
 922
 923   ecg_fill_calls ();
 924   ecg_fill_ctxs ();
 925   ecg_ecg ();
 926 }
 927
 928 /**
 929    Clean up our mess.
 930 */
 931 void ecg_cleanup ()
 932 {
 933   return;
 934
 935   int i;
 936
 937   for (i = 0; i < get_irp_n_irgs (); i++) {
 938     ir_graph *graph = get_irp_irg (i);
 939
 940     graph_info_t *info = pmap_get (graph_infos, graph);
 941     call_info_t *cinfo = info->calls;
 942
 943     while (NULL != cinfo) {
 944       cinfo->call = NULL;
 945
 946       callEd_info_t *ced = cinfo->callEds;
 947
 948       while (NULL != ced) {
 949         callEd_info_t *nced = ced->prev;
 950         free (ced);
 951         ced->prev = NULL;
 952         ced->callEd = NULL;
 953         ced = nced;
 954       }
 955
 956       cinfo->callEds = NULL;
 957
 958       free (cinfo);
 959       cinfo = cinfo->prev;
 960     }
 961
 962     free (info);
 963     pmap_insert (graph_infos, graph, NULL);
 964   }
 965
 966
 967   pmap_destroy (graph_infos);
 968
 969   /*  paranoia mode */
 970   graph_infos = NULL;
 971 }
 972
 973 /**
 974    Show what we have found.
 975 */
 976 void ecg_report ()
 977 {
 978   int i;
 979
 980   FILE *dot = fopen ("calls.dot", "w");
 981
 982   fprintf (dot, "digraph \"calls\" {\n");
 983   fprintf (dot, "\tgraph [rankdir=\"LR\", ordering=\"out\"];\n");
 984   fprintf (dot, "\tnode [shape = \"record\", style = \"filled\"];\n");
 985   fprintf (dot, "\tedge [color = \"black\"];\n");
 986   fprintf (dot, "\n");
 987   fprintf (dot, "\tsize = \"11, 7\";\n");
 988   fprintf (dot, "\trotate = \"90\";\n");
 989   fprintf (dot, "\tratio = \"fill\";\n");
 990   fprintf (dot, "\n");
 991
 992   for (i = 0; i < get_irp_n_irgs (); i++) {
 993     ir_graph *graph = get_irp_irg (i);
 994     graph_info_t *info = (graph_info_t*) pmap_get (graph_infos, graph);
 995
 996     const char *name = get_irg_entity (graph) ?
 997       get_entity_name (get_irg_entity (graph)) : "noEntity";
 998
 999     const char *oname = get_type_name
1000       (get_entity_owner (get_irg_entity (graph)));
1001
1002     const char *color =
1003       (get_entity_stickyness
1004        (get_irg_entity (graph)) == stickyness_sticky) ?
1005       "red3" : "lightyellow";
1006
1007     fprintf (dot, "\t/* graph_0x%08x (\"%s\") */\n", (int) graph, name);
1008     fprintf (dot,
1009              "\tgraph_0x%08x [label=\"%s\\l%s\", color=\"%s\"];\n",
1010              (int) graph, oname, name, color);
1011     fprintf (dot, "\n");
1012
1013     call_info_t *cinfo = info->calls;
1014     if (cinfo) {
1015       fprintf (dot, "\t/* now the calls */\n");
1016     } else {
1017       fprintf (dot, "\t/* no calls, nothing to see, move along! */\n");
1018     }
1019
1020     while (NULL != cinfo) {
1021       ir_node *call = cinfo->call;
1022
1023       fprintf (dot, "\t/* call_0x%08x */\n", (int) call);
1024       fprintf (dot, "\tcall_0x%08x [label=\"call\\[%li\\]\\l0x%08x\"];\n",
1025                (int) call, get_irn_node_nr (call), (int) call);
1026       fprintf (dot, "\tgraph_0x%08x -> call_0x%08x;\n",
1027                (int) graph, (int) call);
1028
1029       callEd_info_t *ced = cinfo->callEds;
1030       while (NULL != ced) {
1031         fprintf (dot, "\tcall_0x%08x -> graph_0x%08x;\n",
1032                  (int) call, (int) ced->callEd);
1033         ced = ced->prev;
1034       }
1035       fprintf (dot, "\n");
1036
1037       cinfo = cinfo->prev;
1038     }
1039     fprintf (dot, "\n");
1040
1041     alloc_info_t *ainfo = info->allocs;
1042     if (ainfo) {
1043       fprintf (dot, "\t/* now the allocs */\n");
1044     } else {
1045       fprintf (dot, "\t/* no allocs */\n");
1046     }
1047
1048
1049     while (NULL != ainfo) {
1050       ir_node *alloc = ainfo->alloc;
1051       const char *name = get_type_name (ainfo->tp);
1052       const char *color = "green3";
1053
1054       fprintf (dot, "\talloc_0x%08x [label=\"%s\", color=\"%s\"];\n",
1055                (int) alloc, name, color);
1056       fprintf (dot, "\tgraph_0x%08x -> alloc_0x%08x;\n",
1057                (int) graph, (int) alloc);
1058
1059       ainfo = ainfo->prev;
1060     }
1061   }
1062   fprintf (dot, "}\n");
1063
1064   /*
1065     fprintf (stdout, " max_callEds: %i\n", _max_callEds);
1066     fprintf (stdout, " max_callEds_callR: \"%s\"\n",
1067     get_entity_name (_max_callEds_callR));
1068   */
1069   fclose (dot);
1070 }
1071
1072 /**
1073    Experimental:  Print the ecg
1074 */
1075 void ecg_ecg ()
1076 {
1077   _graphs = 0;
1078   _calls  = 0;
1079
1080   ir_graph *main_graph = get_irp_main_irg ();
1081
1082   /*
1083     memset (spaces, '.', BUF_SIZE);
1084     spaces [BUF_SIZE-1] = '\0';
1085
1086     ecg_ecg_count (main_graph);
1087     fprintf (stdout, "n_graphs: %i\n", _graphs);
1088     fprintf (stdout, "max_depth = %i\n", _max_depth);
1089   */
1090
1091   /* return; */
1092
1093   _graphs = 0;
1094   _calls  = 0;
1095
1096   FILE *dot = fopen ("ecg.dot", "w");
1097
1098   fprintf (dot, "digraph \"ecg\" {\n");
1099   fprintf (dot, "\tnode [shape = \"record\", style = \"filled\"];\n");
1100   fprintf (dot, "\tedge [color = \"black\"];\n");
1101   fprintf (dot, "\n");
1102   fprintf (dot, "\tsize = \"11, 7\";\n");
1103   fprintf (dot, "\trotate = \"90\";\n");
1104   fprintf (dot, "\tratio = \"fill\";\n");
1105   fprintf (dot, "\trankdir = \"LR\";\n");
1106   fprintf (dot, "\n");
1107
1108   /* ir_graph *main_graph = get_irp_main_irg (); */
1109   ecg_ecg_graph (dot, main_graph);
1110
1111   fprintf (dot, "\t/* Grand Total: */\n");
1112   fprintf (dot, "\t/* calls:  %i */\n", (int) _calls);
1113   fprintf (dot, "\t/* graphs: %i */\n", (int) _graphs);
1114   fprintf (dot, "\t/* allocs: %i */\n", (int) _allocs);
1115   fprintf (dot, "\t/* (sales tax not included) */\n");
1116
1117   fprintf (dot, "}\n");
1118
1119   fclose (dot);
1120 }
1121
1122 \f
1123
1124 /*
1125   $Log$
1126   Revision 1.8  2004/11/30 14:45:44  liekweg
1127   fix graph dumping, remove 'HERE's
1128
1129   Revision 1.7  2004/11/26 16:01:56  liekweg
1130   debugging annotations
1131
1132   Revision 1.6  2004/11/24 14:53:55  liekweg
1133   Bugfixes
1134
1135   Revision 1.5  2004/11/20 21:20:29  liekweg
1136   Added iterator functions
1137
1138   Revision 1.4  2004/11/18 16:36:37  liekweg
1139   Added unique ids for debugging, added access functions
1140
1141   Revision 1.3  2004/11/04 14:54:44  liekweg
1142   Nicer Colors
1143
1144   Revision 1.2  2004/10/21 11:09:37  liekweg
1145   Moved memwalk stuf into irmemwalk
1146   Moved lset stuff into lset
1147   Moved typalise stuff into typalise
1148
1149   Revision 1.1  2004/10/20 14:59:41  liekweg
1150   Added ana2, added ecg and pto
1151
1152   Revision 1.6  2004/10/18 12:47:19  liekweg
1153   minor fix
1154
1155   Revision 1.5  2004/10/14 11:31:28  liekweg
1156   SHUTUP_GCC
1157
1158   Revision 1.4  2004/10/12 11:02:01  liekweg
1159   wtf?
1160
1161 */