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