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