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_ctx.h"
  28
  29 # include "irnode.h"
  30 # include "irprog.h"
  31 # include "xmalloc.h"
  32 # include "irmemwalk.h"
  33
  34 # include "pto_debug.h"
  35 # include "pto_init.h"
  36
  37 # include "ecg.h"
  38
  39 /* Local Defines: */
  40
  41 /* Local Data Types: */
  42 typedef struct pto_env_str {
  43   int dummy;
  44 } pto_env_t;
  45
  46
  47 /* Local Variables: */
  48
  49 /* Debug only: */
  50 char *spaces = NULL;
  51
  52 /* Local Prototypes: */
  53 static void pto_graph (ir_graph*);
  54 static void pto_call (ir_graph*, ir_node*, pto_env_t*);
  55
  56 /* ===================================================
  57    Local Implementation:
  58    =================================================== */
  59
  60 /* Propagation of PTO values */
  61 static pto_t *get_pto_proj (ir_node *proj)
  62 {
  63   ir_node *proj_in = get_Proj_pred (proj);
  64   const long proj_proj = get_Proj_proj (proj);
  65   const opcode in_op = get_irn_opcode (proj_in);
  66   pto_t *in_pto = NULL;
  67   pto_t *proj_pto = get_node_pto (proj);
  68
  69   switch (in_op) {
  70   case (iro_Start):             /* ProjT (Start) */
  71     assert (0 && "pto from ProjT(Start) requested");
  72
  73     return (NULL);
  74   case (iro_Proj):              /* ProjT (Start), ProjT (Call) */
  75     assert ((pn_Start_T_args == proj_proj) ||
  76             (pn_Call_T_result == proj_proj));
  77     ir_node *proj_in_in = get_Proj_pred (proj_in);
  78     const opcode in_in_op = get_irn_opcode (proj_in_in);
  79
  80     switch (in_in_op) {
  81     case (iro_Start):           /* ProjArg (ProjT (Start)) */
  82       /* then the pto value must have been set to the node */
  83       assert (proj_pto);
  84
  85       return (proj_pto);
  86     case (iro_Call):            /* ProjV (ProjT (Call)) */
  87       if (NULL != proj_pto) {
  88         return (proj_pto);
  89       } else {
  90         in_pto = get_node_pto (proj_in);
  91         set_node_pto (proj, in_pto);
  92
  93         return (in_pto);
  94       }
  95     default: assert (0 && "Proj(Proj(?))");
  96     }
  97     /* done with case (in_op == iro_Proj) */
  98
  99   case (iro_Load):              /* ProjV (Load) */
 100     assert (pn_Load_res == proj_proj);
 101     /* FALLTHROUGH */
 102   case (iro_Call):              /* ProjT (Call) */
 103     /* FALLTHROUGH */
 104   case (iro_Alloc):             /* ProjV (Alloc) */
 105     if (NULL != proj_pto) {
 106       return (proj_pto);
 107     } else {
 108       in_pto = get_alloc_pto (proj_in);
 109       assert (in_pto);
 110
 111       set_node_pto (proj, in_pto);
 112       return (in_pto);
 113     }
 114   default:
 115     fprintf (stderr, "%s: not handled: proj (%s[%li])\n",
 116              __FUNCTION__,
 117              get_op_name (get_irn_op (proj_in)),
 118              get_irn_node_nr (proj_in));
 119     assert (0 && "Proj(?)");
 120   }
 121
 122 }
 123
 124 static pto_t *get_pto_phi (ir_node *phi)
 125 {
 126   return (NULL);
 127 }
 128
 129 static pto_t *get_pto_ret (ir_node *ret)
 130 {
 131   pto_t *pto = get_node_pto (ret);
 132
 133   if (NULL == pto) {
 134     ir_node *in = get_Return_res (ret, 0);
 135
 136     pto = get_node_pto (in);
 137     set_node_pto (ret, pto);
 138   }
 139
 140   return (pto);
 141 }
 142
 143
 144 /* Dispatch to propagate PTO values */
 145 static pto_t *get_pto (ir_node *node)
 146 {
 147   const opcode op = get_irn_opcode (node);
 148
 149   switch (op) {
 150   case (iro_Cast):   return (get_pto (get_Cast_op (node)));
 151   case (iro_Proj):   return (get_pto_proj (node));
 152   case (iro_Phi):    return (get_pto_phi (node));
 153   case (iro_Return): return (get_pto_ret (node));
 154
 155   default:
 156     /* stopgap measure */
 157     fprintf (stderr, "%s: not handled: node[%li].op = %s\n",
 158              __FUNCTION__,
 159              get_irn_node_nr (node),
 160              get_op_name (get_irn_op (node)));
 161     assert (0 && "something not handled");
 162
 163   }
 164 }
 165
 166
 167 /* Actions for the nodes: */
 168 static void pto_load (ir_node *load, pto_env_t *pto_env)
 169 {
 170   /* perform load */
 171   DBGPRINT (0, (stdout, "%s (%s[%li])\n", __FUNCTION__, OPNAME (load), OPNUM (load)));
 172 }
 173
 174 static void pto_store (ir_node *store, pto_env_t *pto_env)
 175 {
 176   /* perform store */
 177   DBGPRINT (0, (stdout, "%s (%s[%li])\n", __FUNCTION__,
 178                 OPNAME (store), OPNUM (store)));
 179 }
 180
 181 static void pto_method (ir_node *call, pto_env_t *pto_env)
 182 {
 183   DBGPRINT (0, (stdout, "%s:%i (%s[%li])\n",
 184                 __FUNCTION__, __LINE__, OPNAME (call), OPNUM (call)));
 185
 186   callEd_info_t *callEd_info = ecg_get_callEd_info (call);
 187
 188   int i = 0;
 189   while (NULL != callEd_info) {
 190     DBGPRINT (0, (stdout, "%s:%i (%s[%li]), graph %i\n",
 191                   __FUNCTION__, __LINE__, OPNAME (call), OPNUM (call), i ++));
 192
 193     pto_call (callEd_info->callEd, call, pto_env);
 194
 195     callEd_info = callEd_info->prev;
 196   }
 197 }
 198
 199
 200 /* Continue PTO for one of the graphs called at a Call */
 201 static void pto_call (ir_graph *graph, ir_node *call, pto_env_t *pto_env)
 202 {
 203   /* perform call */
 204   DBGPRINT (0, (stdout, "%s:%i (%s[%li])\n",
 205                 __FUNCTION__, __LINE__, OPNAME (call), OPNUM (call)));
 206
 207   /* only for debugging stuff: */
 208   entity *ent = get_irg_entity (graph);
 209   const char *ent_name = (char*) get_entity_name (ent);
 210   const char *own_name = (char*) get_type_name (get_entity_owner (ent));
 211
 212   if (! get_irg_is_mem_visited (graph)) {
 213     graph_info_t *ginfo = ecg_get_info (graph);
 214
 215     /* Save CTX */
 216     int ctx_idx = find_ctx_idx (call, ginfo, get_curr_ctx ());
 217     ctx_info_t *call_ctx = get_ctx (ginfo, ctx_idx);
 218     ctx_info_t *old_ctx = set_curr_ctx (call_ctx);
 219     DBGPRINT (1, (stdout, "%s>CTX: ", -- spaces));
 220     DBGEXE (1, ecg_print_ctx (call_ctx, stdout));
 221
 222     /* Todo: Compute Arguments */
 223
 224     /* Initialise Alloc Names and Node values */
 225     pto_reset_graph_pto (graph, ctx_idx);
 226
 227     /* Visit/Iterate Graph */
 228     pto_graph (graph);
 229
 230     /* Restore CTX */
 231     set_curr_ctx (old_ctx);
 232
 233     DBGPRINT (1, (stdout, "%s<CTX: ", spaces ++));
 234     DBGEXE (1, ecg_print_ctx (call_ctx, stdout));
 235
 236     /* Don't need to reset alloc names unless we handle recursion here  */
 237
 238
 239     /* Get Return Value from Graph */
 240   } else {
 241     DBGPRINT (0, (stdout, "%s: recursion into \"%s.%s\"\n",
 242                   __FUNCTION__, own_name, ent_name));
 243   }
 244
 245   /* Todo: Set 'Unknown' Value as Return Value when the graph is not
 246      known */
 247 }
 248
 249 static void pto_raise (ir_node *raise, pto_env_t *pto_env)
 250 {
 251   /* perform raise */
 252   DBGPRINT (0, (stdout, "%s (%s[%li])\n", __FUNCTION__,
 253                 OPNAME (raise), OPNUM (raise)));
 254 }
 255
 256 static void pto_end_block (ir_node *end_block, pto_env_t *pto_env)
 257 {
 258   /* perform end block */
 259   DBGPRINT (0, (stdout, "%s (%s[%li])\n", __FUNCTION__,
 260                 OPNAME (end_block), OPNUM (end_block)));
 261 }
 262
 263 /* Perform the appropriate action on the given node */
 264 static void pto_node_node (ir_node *node, pto_env_t *pto_env)
 265 {
 266   const opcode op = get_irn_opcode (node);
 267
 268   switch (op) {
 269   case (iro_Start): /* nothing */ break;
 270   case (iro_Load):
 271     pto_load (node, pto_env);
 272     break;
 273
 274   case (iro_Store):
 275     pto_store (node, pto_env);
 276     break;
 277
 278   case (iro_Call):
 279     pto_method (node, pto_env);
 280     break;
 281
 282   case (iro_Raise):
 283     pto_raise (node, pto_env);
 284     break;
 285
 286   case (iro_Return):
 287     /* nothing to do */
 288     break;
 289
 290   case (iro_Alloc):
 291     /* nothing to do */
 292     break;
 293
 294   case (iro_Block):
 295     pto_end_block (node, pto_env);
 296     break;
 297
 298   case (iro_Phi):
 299     /* must be a PhiM */
 300     assert (mode_M == get_irn_mode (node));
 301     /* nothing to do */
 302     break;
 303
 304     /* uninteresting stuff: */
 305   case (iro_Div):
 306   case (iro_Quot):
 307   case (iro_Mod):
 308   case (iro_DivMod): /* nothing to do */ break;
 309
 310   default:
 311     /* stopgap measure */
 312     fprintf (stderr, "%s: not handled: node[%li].op = %s\n",
 313              __FUNCTION__,
 314              get_irn_node_nr (node),
 315              get_op_name (get_irn_op (node)));
 316     assert (0 && "something not handled");
 317   }
 318
 319
 320
 321 }
 322
 323
 324 /* Callback function to execute in pre-order */
 325 static void pto_node_pre (ir_node *node, void *env)
 326 {
 327   /* nothing */
 328 }
 329
 330 /* Callback function to execute in post-order */
 331 static void pto_node_post (ir_node *node, void *env)
 332 {
 333   pto_env_t *pto_env = (pto_env_t*) env;
 334
 335   pto_node_node (node, pto_env);
 336 }
 337
 338 /* Perform a single pass over the given graph */
 339 static void pto_graph_pass (ir_graph *graph, void *pto_env)
 340 {
 341   entity *ent = get_irg_entity (graph);
 342   const char *ent_name = (char*) get_entity_name (ent);
 343   const char *own_name = (char*) get_type_name (get_entity_owner (ent));
 344   HERE3 ("start", own_name, ent_name);
 345
 346   irg_walk_mem (graph, pto_node_pre, pto_node_post, pto_env);
 347
 348   HERE3 ("end  ", own_name, ent_name);
 349 }
 350
 351
 352 /* Main loop: Initialise and iterate over the given graph */
 353 static void pto_graph (ir_graph *graph)
 354 {
 355   pto_env_t *pto_env = xmalloc (sizeof (pto_env_t));
 356   HERE ("start");
 357
 358   /* todo (here): iterate, obey 'changed' attribute */
 359   pto_graph_pass (graph, pto_env);
 360
 361   memset (pto_env, 0x00, sizeof (pto_env_t));
 362   free (pto_env);
 363   HERE ("end");
 364 }
 365
 366 /* "Fake" the arguments to the main method */
 367 static void fake_main_args (ir_graph *graph)
 368 {
 369   HERE ("start");
 370   /* todo: fake the arguments to the main method */
 371
 372   HERE ("end");
 373 }
 374
 375 /* Helper to pto_init */
 376 static void pto_init_graph_wrapper (graph_info_t *ginfo, void *__unused)
 377 {
 378   ir_graph *graph = ginfo->graph;
 379
 380   pto_init_graph (graph);
 381 }
 382
 383
 384 /* ===================================================
 385    Exported Implementation:
 386    =================================================== */
 387 /* Set the PTO value for the given non-alloc node */
 388 void set_node_pto (ir_node *node, pto_t *pto)
 389 {
 390   assert (iro_Alloc != get_irn_opcode (node));
 391
 392   set_irn_link (node, (void*) pto);
 393 }
 394
 395 /*Get the PTO value for the given non-alloc node */
 396 pto_t *get_node_pto (ir_node *node)
 397 {
 398   assert (iro_Alloc != get_irn_opcode (node));
 399
 400   return ((pto_t*) get_irn_link (node));
 401 }
 402
 403 /* Set the PTO value for the given alloc node */
 404 void set_alloc_pto (ir_node *alloc, alloc_pto_t *alloc_pto)
 405 {
 406   assert (iro_Alloc == get_irn_opcode (alloc));
 407
 408   set_irn_link (alloc, (void*) alloc_pto);
 409 }
 410
 411 /*Get the current PTO value for the given alloc node */
 412 pto_t *get_alloc_pto (ir_node *alloc)
 413 {
 414   alloc_pto_t *alloc_pto = (alloc_pto_t*) get_irn_link (alloc);
 415
 416   assert (iro_Alloc == get_irn_opcode (alloc));
 417
 418   return (alloc_pto -> curr_pto);
 419 }
 420
 421 /* Initialise the module (not in pto_init.c because it's the entry to pto) */
 422 void pto_init ()
 423 {
 424   HERE ("start");
 425   ecg_init (1);
 426
 427   /* todo: initialise globals etc */
 428   pto_init_type_names ();
 429
 430   /* todo: allocate ctx-sens names for allocs and set ... etc etc */
 431   pto_init_type_names ();
 432
 433   ecg_iterate_graphs (pto_init_graph_wrapper, NULL);
 434
 435   spaces = (char*) xmalloc (512 * sizeof (char));
 436   memset (spaces, ' ', 512);
 437   spaces += 511;
 438   *spaces = '\0';
 439
 440   /* initialise for the CTX-sensitive ecg-traversal */
 441   set_curr_ctx (get_main_ctx ());
 442   HERE ("end");
 443 }
 444
 445 void pto_run (int dbg_lvl)
 446 {
 447   HERE ("start");
 448   set_dbg_lvl (dbg_lvl);
 449
 450   ir_graph *graph = get_irp_main_irg ();
 451   fake_main_args (graph);
 452
 453   /* todo: clear entity/type links */
 454
 455   DBGPRINT (0, (stdout, "START PTO\n"));
 456   DBGPRINT (0, (stdout, "START GRAPH (0x%08x) of \"%s.%s\"\n",
 457                 (int) graph,
 458                 get_type_name (get_entity_owner (get_irg_entity (graph))),
 459                 get_entity_name (get_irg_entity (graph))));
 460
 461   /* do we need some kind of environment here? */
 462   pto_graph (graph);
 463
 464   DBGPRINT (0, (stdout, "END   PTO\n"));
 465   HERE ("end");
 466 }
 467
 468 void pto_cleanup ()
 469 {
 470   HERE ("start");
 471   /* todo: clean up our own mess */
 472   spaces -= 511;                /* hope that all changes to spaces are
 473                                    properly nested */
 474   memset (spaces, 0x00, 512);
 475   free (spaces);
 476
 477   /* clean up ecg infos */
 478   ecg_cleanup ();
 479   HERE ("end");
 480 }
 481
 482 \f
 483 /*
 484   $Log$
 485   Revision 1.2  2004/11/20 21:21:56  liekweg
 486   Finalise initialisation
 487
 488   Revision 1.1  2004/11/18 16:37:34  liekweg
 489   rewritten
 490
 491
 492 */