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

   1 /* -*- c -*- */
   2
   3 /*
   4    Project:     libFIRM
   5    File name:   ir/ana/pto_comp.c
   6    Purpose:     Main Implementation of PTO
   7    Author:      Florian
   8    Modified by:
   9    Created:     Sat Nov 13 19:35:27 CET 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   pto_comp: Main Implementation of PTO
  21 */
  22
  23 # include <string.h>            /* for memset */
  24
  25 # include "pto_comp.h"
  26 # include "pto_util.h"
  27 # include "pto_name.h"
  28 # include "pto_ctx.h"
  29 # include "pto_mod.h"
  30
  31 # include "irnode_t.h"
  32 # include "irprog.h"
  33 # include "xmalloc.h"
  34 # include "irmemwalk.h"
  35
  36 # include "pto_debug.h"
  37 # include "pto_init.h"
  38
  39 # include "ecg.h"
  40
  41 /* Local Defines: */
  42
  43 /* Local Data Types: */
  44 typedef struct pto_env_str {
  45   int ctx_idx;
  46   int change;
  47 } pto_env_t;
  48
  49
  50 /* Local Variables: */
  51
  52 /* Debug only: */
  53 char *spaces = NULL;
  54
  55 /* Local Prototypes: */
  56 static pto_t *get_pto (ir_node*, pto_env_t*);
  57 static void pto_call (ir_graph*, ir_node*, pto_env_t*);
  58 static void pto_raise (ir_node*, pto_env_t*);
  59 static void pto_load (ir_node*, pto_env_t*);
  60 static void pto_store (ir_node*, pto_env_t*);
  61 static void pto_method (ir_node*, pto_env_t*);
  62 static void pto_end_block (ir_node*, pto_env_t*);
  63
  64 /* ===================================================
  65    Local Implementation:
  66    =================================================== */
  67 /* Transfer the actual arguments to the formal arguments */
  68 static void set_graph_args (ir_graph *graph, ir_node *call, pto_env_t *env)
  69 {
  70   assert (iro_Call == get_irn_opcode (call));
  71
  72   type *meth = get_entity_type (get_irg_entity (graph));
  73   ir_node **args = find_irg_args (graph);
  74   int n_args = get_Call_n_params (call);
  75   int i;
  76
  77   for (i = 0; i < n_args; i ++) {
  78     if (NULL != args [i]) {
  79       if (mode_P == get_type_mode (get_method_param_type (meth, i))) {
  80         ir_node *call_arg = get_Call_param (call, i);
  81         pto_t *pto = get_pto (call_arg, env);
  82         assert (pto);
  83         set_node_pto (args [i], pto);
  84
  85         DBGPRINT (1, (stdout, "%s: arg [%i]: %s[%li] -> %s[%li] (%i)\n",
  86                       __FUNCTION__,
  87                       i,
  88                       OPNAME (call_arg), OPNUM (call_arg),
  89                       OPNAME (args [i]), OPNUM (args [i]),
  90                       pto->values->id));
  91       }
  92     }
  93   }
  94 }
  95
  96 /* Transfer the graph's result to the call */
  97 static int set_graph_result (ir_graph *graph, ir_node *call)
  98 {
  99   type *tp = get_entity_type (get_irg_entity (graph));
 100   int change = FALSE;
 101
 102   if (0 == get_method_n_ress (tp)) {
 103     return (change);
 104   }
 105
 106   tp = get_method_res_type (tp, 0);
 107
 108   if (mode_P != get_type_mode (tp)) {
 109     set_node_pto (call, NULL);
 110
 111     return (change);
 112   }
 113
 114   ir_node *end_block = get_irg_end_block (graph);
 115   pto_t *ret_pto = get_node_pto (end_block);
 116
 117   pto_t *call_pto = get_node_pto (call);
 118
 119   assert (call_pto);
 120
 121   change |= qset_insert_all (call_pto->values, ret_pto->values);
 122
 123   return (change);
 124 }
 125
 126 /* Propagation of PTO values */
 127 static pto_t *get_pto_proj (ir_node *proj, pto_env_t *env)
 128 {
 129   ir_node *proj_in = get_Proj_pred (proj);
 130   const long proj_proj = get_Proj_proj (proj);
 131   const opcode in_op = get_irn_opcode (proj_in);
 132   pto_t *in_pto = NULL;
 133   pto_t *proj_pto = NULL; /* get_node_pto (proj); */
 134
 135   ir_node *proj_in_in = NULL;
 136
 137   switch (in_op) {
 138   case (iro_Start):             /* ProjT (Start) */
 139     assert (0 && "pto from ProjT(Start) requested");
 140
 141     return (NULL);
 142   case (iro_Proj):              /* ProjT (Start), ProjT (Call) */
 143     proj_in_in = get_Proj_pred (proj_in);
 144     const opcode in_in_op = get_irn_opcode (proj_in_in);
 145     const long proj_in_proj = get_Proj_proj (proj_in);
 146
 147     assert ((pn_Start_T_args == proj_in_proj) ||
 148             (pn_Call_T_result == proj_in_proj));
 149
 150     switch (in_in_op) {
 151     case (iro_Start):           /* ProjArg (ProjT (Start)) */
 152       /* then the pto value must have been set to the node */
 153       proj_pto = get_node_pto (proj);
 154       assert (proj_pto);
 155
 156       return (proj_pto);
 157     case (iro_Call):            /* ProjV (ProjT (Call)) */
 158       if (NULL != proj_pto) {
 159         return (proj_pto);
 160       } else {
 161         in_pto = get_pto (proj_in, env);
 162         set_node_pto (proj, in_pto);
 163
 164         assert (in_pto);
 165
 166         return (in_pto);
 167       }
 168     default: assert (0 && "Proj(Proj(?))");
 169     }
 170     /* done with case (in_op == iro_Proj) */
 171
 172   case (iro_Load):              /* ProjV (Load) */
 173     assert (pn_Load_res == proj_proj);
 174     /* FALLTHROUGH */
 175   case (iro_Call):              /* ProjT (Call) */
 176     /* FALLTHROUGH */
 177   case (iro_Alloc):             /* ProjV (Alloc) */
 178     if (NULL != proj_pto) {
 179       return (proj_pto);
 180     } else {
 181       in_pto = get_pto (proj_in, env);
 182       assert (in_pto);
 183
 184       set_node_pto (proj, in_pto);
 185       return (in_pto);
 186     }
 187   default:
 188     fprintf (stderr, "%s: not handled: proj (%s[%li])\n",
 189              __FUNCTION__,
 190              get_op_name (get_irn_op (proj_in)),
 191              get_irn_node_nr (proj_in));
 192     assert (0 && "Proj(?)");
 193   }
 194
 195 }
 196
 197 static pto_t *get_pto_phi (ir_node *phi, pto_env_t *env)
 198 {
 199   assert (mode_P == get_irn_mode (phi));
 200
 201   pto_t *pto = get_node_pto (phi);
 202   int change = FALSE;
 203
 204   assert (pto);                 /* must be initialised */
 205
 206   int n_ins = get_irn_arity (phi);
 207   int i;
 208
 209   for (i = 0; i < n_ins; i ++) {
 210     ir_node *in = get_irn_n (phi, i);
 211     pto_t *in_pto = get_pto (in, env);
 212
 213     assert (in_pto);
 214
 215     change |= qset_insert_all (pto->values, in_pto->values);
 216   }
 217
 218   env->change |= change;
 219
 220   return (pto);
 221 }
 222
 223 static pto_t *get_pto_sel (ir_node *sel, pto_env_t *env)
 224 {
 225   pto_t *pto = NULL; /* get_node_pto (sel); */
 226
 227   if (NULL == pto) {
 228     ir_node *in = get_Sel_ptr (sel);
 229
 230     pto = get_pto (in, env);
 231     set_node_pto (sel, pto);
 232   }
 233
 234   return (pto);
 235 }
 236
 237 static pto_t *get_pto_ret (ir_node *ret, pto_env_t *env)
 238 {
 239   pto_t *pto = NULL; /* get_node_pto (ret); */
 240
 241   if (NULL == pto) {
 242     ir_node *in = get_Return_res (ret, 0);
 243
 244     pto = get_pto (in, env);
 245     set_node_pto (ret, pto);
 246   }
 247
 248   assert (pto);
 249
 250   return (pto);
 251 }
 252
 253
 254 /* Dispatch to propagate PTO values */
 255 static pto_t *get_pto (ir_node *node, pto_env_t *env)
 256 {
 257   const opcode op = get_irn_opcode (node);
 258
 259   DBGPRINT (2, (stdout, "%s (%s[%li])\n", __FUNCTION__,
 260                 OPNAME (node), OPNUM (node)));
 261
 262   switch (op) {
 263   case (iro_Cast):   return (get_pto (get_Cast_op (node), env));
 264   case (iro_Proj):   return (get_pto_proj  (node, env));
 265   case (iro_Phi):    return (get_pto_phi   (node, env));
 266   case (iro_Sel):    return (get_pto_sel   (node, env));
 267   case (iro_Alloc):  return (get_alloc_pto (node));
 268   case (iro_Return): return (get_pto_ret   (node, env));
 269
 270   case (iro_Call):              /* FALLTHROUGH */
 271   case (iro_Load):              /* FALLTHROUGH */
 272   case (iro_Const):             /* FALLTHROUGH */
 273   case (iro_SymConst):{
 274     pto_t *pto = get_node_pto (node);
 275
 276     assert (pto);
 277     return (pto);
 278   }
 279   default:
 280     /* stopgap measure */
 281     fprintf (stderr, "%s: not handled: node[%li].op = %s\n",
 282              __FUNCTION__,
 283              get_irn_node_nr (node),
 284              get_op_name (get_irn_op (node)));
 285     assert (0 && "something not handled");
 286
 287   }
 288 }
 289
 290
 291 /* Actions for the nodes: */
 292 static void pto_load (ir_node *load, pto_env_t *pto_env)
 293 {
 294   /* perform load */
 295   DBGPRINT (2, (stdout, "%s (%s[%li]): pto = %p\n", __FUNCTION__,
 296                 OPNAME (load), OPNUM (load), (void*) get_node_pto (load)));
 297
 298   ir_node *ptr = get_Load_ptr (load);
 299
 300   if (is_dummy_load_ptr (ptr)) {
 301     return;
 302   }
 303
 304   /* TODO: ONLY LOAD IFF LOAD.ENT.MODE == MODE_P */
 305
 306   entity *ent = get_ptr_ent (ptr);
 307
 308   if (mode_P == get_type_mode (get_entity_type (ent))) {
 309
 310     pto_t *ptr_pto = get_pto (ptr, pto_env);
 311
 312     HERE ("ptr");
 313
 314     assert (ptr_pto);
 315
 316     DBGPRINT (1, (stdout, "%s (%s[%li]): ptr = %p\n", __FUNCTION__,
 317                   OPNAME (ptr), OPNUM (ptr), (void*) ptr_pto));
 318
 319     pto_env->change |= mod_load (load, ent, ptr_pto);
 320   }
 321 }
 322
 323 static void pto_store (ir_node *store, pto_env_t *pto_env)
 324 {
 325   /* perform store */
 326   DBGPRINT (2, (stdout, "%s (%s[%li]) (no pto)\n", __FUNCTION__,
 327                 OPNAME (store), OPNUM (store)));
 328
 329   ir_node *ptr = get_Store_ptr (store);
 330   ir_node *val = get_Store_value (store);
 331
 332   if (mode_P != get_irn_mode (val)) {
 333     return;
 334   }
 335
 336   entity *ent = get_ptr_ent (ptr);
 337
 338   pto_t *ptr_pto = get_pto (ptr, pto_env);
 339   pto_t *val_pto = get_pto (val, pto_env);
 340
 341   assert (ptr_pto);
 342   assert (val_pto);
 343
 344   DBGPRINT (2, (stdout, "%s (%s[%li]): ptr_pto = %p\n", __FUNCTION__,
 345                 OPNAME (ptr), OPNUM (ptr), (void*) ptr_pto));
 346   DBGPRINT (2, (stdout, "%s (%s[%li]): val_pto = %p\n", __FUNCTION__,
 347                 OPNAME (val), OPNUM (val), (void*) val_pto));
 348
 349   pto_env->change |= mod_store (store, ent, ptr_pto, val_pto);
 350 }
 351
 352 static void pto_method (ir_node *call, pto_env_t *pto_env)
 353 {
 354   DBGPRINT (2, (stdout, "%s:%i (%s[%li]): pto = %p\n",
 355                 __FUNCTION__, __LINE__, OPNAME (call), OPNUM (call),
 356                 (void*) get_node_pto (call)));
 357
 358   callEd_info_t *callEd_info = ecg_get_callEd_info (call);
 359
 360   if (NULL == callEd_info) {
 361     DBGPRINT (2, (stdout, "%s:%i (%s[%li]), no graph\n",
 362                   __FUNCTION__, __LINE__, OPNAME (call), OPNUM (call)));
 363   }
 364
 365   int i = 0;
 366   while (NULL != callEd_info) {
 367     DBGPRINT (2, (stdout, "%s:%i (%s[%li]), graph %i\n",
 368                   __FUNCTION__, __LINE__, OPNAME (call), OPNUM (call), i ++));
 369
 370     pto_call (callEd_info->callEd, call, pto_env);
 371
 372     callEd_info = callEd_info->prev;
 373   }
 374 }
 375
 376 /* Perform the appropriate action on the given node */
 377 static void pto_node_node (ir_node *node, pto_env_t *pto_env)
 378 {
 379   DBGPRINT (1, (stdout, "%s (%s[%li])\n", __FUNCTION__,
 380                 OPNAME (node), OPNUM (node)));
 381
 382   const opcode op = get_irn_opcode (node);
 383
 384   switch (op) {
 385   case (iro_Start): /* nothing */ break;
 386   case (iro_Load):
 387     pto_load (node, pto_env);
 388     break;
 389
 390   case (iro_Store):
 391     pto_store (node, pto_env);
 392     break;
 393
 394   case (iro_Call):
 395     pto_method (node, pto_env);
 396     break;
 397
 398   case (iro_Raise):
 399     pto_raise (node, pto_env);
 400     break;
 401
 402   case (iro_Return):
 403     /* nothing to do */
 404     break;
 405
 406   case (iro_Alloc):
 407     /* nothing to do */
 408     break;
 409
 410   case (iro_Block):
 411     pto_end_block (node, pto_env);
 412     break;
 413
 414   case (iro_Phi):
 415     /* must be a PhiM */
 416     assert (mode_M == get_irn_mode (node));
 417     /* nothing to do */
 418     break;
 419
 420     /* uninteresting stuff: */
 421   case (iro_Div):
 422   case (iro_Quot):
 423   case (iro_Mod):
 424   case (iro_DivMod): /* nothing to do */ break;
 425
 426   default:
 427     /* stopgap measure */
 428     fprintf (stderr, "%s: not handled: node[%li].op = %s\n",
 429              __FUNCTION__,
 430              get_irn_node_nr (node),
 431              get_op_name (get_irn_op (node)));
 432     assert (0 && "something not handled");
 433   }
 434 }
 435
 436
 437 /* Callback function to execute in pre-order */
 438 static void pto_node_pre (ir_node *node, void *env)
 439 {
 440   /* nothing */
 441 }
 442
 443 /* Callback function to execute in post-order */
 444 static void pto_node_post (ir_node *node, void *env)
 445 {
 446   pto_env_t *pto_env = (pto_env_t*) env;
 447
 448   pto_node_node (node, pto_env);
 449 }
 450
 451 /* Perform a single pass over the given graph */
 452 static void pto_graph_pass (ir_graph *graph, void *pto_env)
 453 {
 454   entity *ent = get_irg_entity (graph);
 455   const char *ent_name = (char*) get_entity_name (ent);
 456   const char *own_name = (char*) get_type_name (get_entity_owner (ent));
 457   HERE3 ("start", own_name, ent_name);
 458
 459   irg_walk_mem (graph, pto_node_pre, pto_node_post, pto_env);
 460
 461   HERE3 ("end  ", own_name, ent_name);
 462 }
 463
 464 /* Continue PTO for one of the graphs called at a Call */
 465 static void pto_call (ir_graph *graph, ir_node *call, pto_env_t *pto_env)
 466 {
 467   int change = FALSE;
 468
 469   /* perform call */
 470   DBGPRINT (1, (stdout, "%s:%i (%s[%li])\n",
 471                 __FUNCTION__, __LINE__, OPNAME (call), OPNUM (call)));
 472
 473   /* only for debugging stuff: */
 474   entity *ent = get_irg_entity (graph);
 475   const char *ent_name = (char*) get_entity_name (ent);
 476   const char *own_name = (char*) get_type_name (get_entity_owner (ent));
 477
 478   if (! get_irg_is_mem_visited (graph)) {
 479     graph_info_t *ginfo = ecg_get_info (graph);
 480
 481     /* Save CTX */
 482     int ctx_idx = find_ctx_idx (call, ginfo, get_curr_ctx ());
 483     ctx_info_t *call_ctx = get_ctx (ginfo, ctx_idx);
 484     ctx_info_t *old_ctx = set_curr_ctx (call_ctx);
 485     DBGPRINT (3, (stdout, "%s>CTX: ", -- spaces));
 486     DBGEXE (3, ecg_print_ctx (call_ctx, stdout));
 487
 488     /* Initialise Alloc Names and Node values */
 489     pto_reset_graph_pto (graph, ctx_idx);
 490
 491     /* Compute Arguments */
 492     set_graph_args (graph, call, pto_env);
 493
 494     /* Visit/Iterate Graph */
 495     pto_graph (graph, ctx_idx);
 496
 497     /* Restore CTX */
 498     set_curr_ctx (old_ctx);
 499
 500     change |= set_graph_result (graph, call);
 501
 502     DBGPRINT (3, (stdout, "%s<CTX: ", spaces ++));
 503     DBGEXE (3, ecg_print_ctx (call_ctx, stdout));
 504
 505     /* Don't need to reset alloc names unless we handle recursion here  */
 506
 507
 508     /* Get Return Value from Graph */
 509   } else {
 510     DBGPRINT (2, (stdout, "%s: recursion into \"%s.%s\"\n",
 511                   __FUNCTION__, own_name, ent_name));
 512   }
 513
 514   /* Todo: Set 'Unknown' Value as Return Value when the graph is not
 515      known */
 516
 517   pto_env->change |= change;
 518 }
 519
 520 static void pto_raise (ir_node *raise, pto_env_t *pto_env)
 521 {
 522   /* perform raise */
 523   DBGPRINT (2, (stdout, "%s (%s[%li]): pto = %p\n", __FUNCTION__,
 524                 OPNAME (raise), OPNUM (raise), (void*) get_node_pto (raise)));
 525 }
 526
 527 static void pto_end_block (ir_node *end_block, pto_env_t *pto_env)
 528 {
 529   /* perform end block */
 530   type *tp = get_entity_type (get_irg_entity (get_irn_irg (end_block)));
 531
 532   if (0 == get_method_n_ress (tp)) {
 533     return;
 534   }
 535
 536   tp = get_method_res_type (tp, 0);
 537
 538   if (mode_P != get_type_mode (tp)) {
 539     return;
 540   }
 541
 542   DBGPRINT (2, (stdout, "%s (%s[%li]): pto = %p\n", __FUNCTION__,
 543                 OPNAME (end_block), OPNUM (end_block),
 544                 (void*) get_node_pto (end_block)));
 545
 546   pto_t *end_pto = get_node_pto (end_block);
 547
 548   assert (end_pto);
 549
 550   int n_ins = get_irn_arity (end_block);
 551   int i;
 552   for (i = 0; i < n_ins; i ++) {
 553     ir_node *in = get_irn_n (end_block, i);
 554
 555     if (iro_Return == get_irn_opcode (in)) {
 556       pto_t *in_pto = get_pto (in, pto_env);
 557
 558       pto_env->change |= qset_insert_all (end_pto->values, in_pto->values);
 559     }
 560   }
 561 }
 562
 563 /* ===================================================
 564    Exported Implementation:
 565    =================================================== */
 566 /* Main loop: Initialise and iterate over the given graph */
 567 void pto_graph (ir_graph *graph, int ctx_idx)
 568 {
 569   /* Also exported, since we need it in 'pto.c' */
 570   pto_env_t *pto_env = xmalloc (sizeof (pto_env_t));
 571   pto_env->ctx_idx = ctx_idx;
 572   pto_env->change = TRUE;
 573
 574   /* HERE ("start"); */
 575
 576   DBGPRINT (2, (stdout, "%s: start for ctx %i\n",
 577                 __FUNCTION__,
 578                 ctx_idx));
 579
 580   /* todo (here): iterate, obey 'changed' attribute */
 581   int run = 0;
 582   while (0 != pto_env->change) {
 583     run ++;
 584     pto_env->change = FALSE;
 585     pto_graph_pass (graph, pto_env);
 586   }
 587
 588   DBGPRINT (1, (stdout, "%s: %i runs on \"%s.%s\"\n",
 589                 __FUNCTION__,
 590                 run,
 591                 get_type_name (get_entity_owner (get_irg_entity (graph))),
 592                 get_entity_name (get_irg_entity (graph))));
 593
 594
 595   memset (pto_env, 0x00, sizeof (pto_env_t));
 596   free (pto_env);
 597   /* HERE ("end"); */
 598 }
 599
 600 /* Set the PTO value for the given non-alloc node */
 601 void set_node_pto (ir_node *node, pto_t *pto)
 602 {
 603   assert (iro_Alloc != get_irn_opcode (node));
 604
 605   set_irn_link (node, (void*) pto);
 606 }
 607
 608 /*Get the PTO value for the given non-alloc node */
 609 pto_t *get_node_pto (ir_node *node)
 610 {
 611   assert (iro_Alloc != get_irn_opcode (node));
 612
 613   return ((pto_t*) get_irn_link (node));
 614 }
 615
 616 /* Set the PTO value for the given alloc node */
 617 void set_alloc_pto (ir_node *alloc, alloc_pto_t *alloc_pto)
 618 {
 619   assert (iro_Alloc == get_irn_opcode (alloc));
 620
 621   assert (alloc_pto);
 622
 623   set_irn_link (alloc, (void*) alloc_pto);
 624 }
 625
 626 /*Get the current PTO value for the given alloc node */
 627 pto_t *get_alloc_pto (ir_node *alloc)
 628 {
 629   alloc_pto_t *alloc_pto = (alloc_pto_t*) get_irn_link (alloc);
 630
 631   assert (iro_Alloc == get_irn_opcode (alloc));
 632
 633   assert (alloc_pto -> curr_pto);
 634
 635   return (alloc_pto -> curr_pto);
 636 }
 637
 638 \f
 639 /*
 640   $Log$
 641   Revision 1.8  2004/12/15 09:18:18  liekweg
 642   pto_name.c
 643
 644   Revision 1.7  2004/12/06 12:55:06  liekweg
 645   actually iterate
 646
 647   Revision 1.6  2004/12/02 16:17:51  beck
 648   fixed config.h include
 649
 650   Revision 1.5  2004/11/30 14:47:54  liekweg
 651   fix initialisation; do correct iteration
 652
 653   Revision 1.4  2004/11/26 15:59:40  liekweg
 654   verify pto_{load,store}
 655
 656   Revision 1.3  2004/11/24 14:53:55  liekweg
 657   Bugfixes
 658
 659   Revision 1.2  2004/11/20 21:21:56  liekweg
 660   Finalise initialisation
 661
 662   Revision 1.1  2004/11/18 16:37:34  liekweg
 663   rewritten
 664
 665
 666 */