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