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