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