nsz Git - libfirm/blob - ir/ana2/ecg.c

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