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