nsz Git - libfirm/blob - ir/opt/escape_ana.c

   1 /*
   2  * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /*
  21  * Project:     libFIRM
  22  * File name:   ir/opt/escape_ana.c
  23  * Purpose:     escape analysis and optimization
  24  * Author:      Michael Beck
  25  * Modified by:
  26  * Created:     03.11.2005
  27  * CVS-ID:      $Id$
  28  * Copyright:   (c) 1999-2005 Universität Karlsruhe
  29  */
  30
  31 /**
  32  * @file escape_ana.c
  33  *
  34  * A fast and simple Escape analysis.
  35  */
  36 #ifdef HAVE_CONFIG_H
  37 # include "config.h"
  38 #endif
  39
  40 #include "iroptimize.h"
  41
  42 #include "irgraph_t.h"
  43 #include "irnode_t.h"
  44 #include "type_t.h"
  45 #include "irgwalk.h"
  46 #include "irouts.h"
  47 #include "analyze_irg_args.h"
  48 #include "irgmod.h"
  49 #include "ircons.h"
  50 #include "irprintf.h"
  51 #include "debug.h"
  52
  53 /**
  54  * walker environment
  55  */
  56 typedef struct _walk_env {
  57   ir_node *found_allocs;            /**< list of all found non-escaped allocs */
  58   ir_node *dead_allocs;             /**< list of all found dead alloc */
  59   check_alloc_entity_func callback; /**< callback that checks a given entity for allocation */
  60   unsigned nr_removed;              /**< number of removed allocs (placed of frame) */
  61   unsigned nr_changed;              /**< number of changed allocs (allocated on stack now) */
  62   unsigned nr_deads;                /**< number of dead allocs */
  63
  64   /* these fields are only used in the global escape analysis */
  65   ir_graph *irg;                    /**< the irg for this environment */
  66   struct _walk_env *next;           /**< for linking environments */
  67
  68 } walk_env_t;
  69
  70 /** debug handle */
  71 DEBUG_ONLY(firm_dbg_module_t *dbgHandle;)
  72
  73 /**
  74  * checks whether a Raise leaves a method
  75  */
  76 static int is_method_leaving_raise(ir_node *raise)
  77 {
  78   int i;
  79   ir_node *proj = NULL;
  80   ir_node *n;
  81
  82   for (i = get_irn_n_outs(raise) - 1; i >= 0; --i) {
  83     ir_node *succ = get_irn_out(raise, i);
  84
  85     /* there should be only one ProjX node */
  86     if (get_Proj_proj(succ) == pn_Raise_X) {
  87       proj = succ;
  88       break;
  89     }
  90   }
  91
  92   if (! proj) {
  93     /* Hmm: no ProjX from a Raise? This should be a verification
  94      * error. For now we just assert and return.
  95      */
  96     assert(! "No ProjX after Raise found");
  97     return 1;
  98   }
  99
 100   if (get_irn_n_outs(proj) != 1) {
 101     /* Hmm: more than one user of ProjX: This is a verification
 102      * error.
 103      */
 104     assert(! "More than one user of ProjX");
 105     return 1;
 106   }
 107
 108   n = get_irn_out(proj, 0);
 109   assert(is_Block(n) && "Argh: user of ProjX is no block");
 110
 111   if (n == get_irg_end_block(get_irn_irg(n)))
 112     return 1;
 113
 114   /* ok, we get here so the raise will not leave the function */
 115   return 0;
 116 }
 117
 118 /**
 119  * returns an Alloc node if the node adr Select
 120  * from one
 121  */
 122 static ir_node *is_depend_alloc(ir_node *adr) {
 123   ir_node *alloc;
 124
 125   if (!is_Sel(adr))
 126     return NULL;
 127
 128   /* should be a simple Sel */
 129   if (get_Sel_n_indexs(adr) != 0)
 130     return NULL;
 131
 132   alloc = skip_Proj(get_Sel_ptr(adr));
 133   if (!is_Alloc(alloc))
 134     return NULL;
 135
 136   /* hmm, we depend on this Alloc */
 137   ir_printf("depend alloc %+F\n", alloc);
 138
 139   return NULL;
 140 }
 141
 142 /**
 143  * determine if a value calculated by n "escape", ie
 144  * is stored somewhere we could not track
 145  */
 146 static int can_escape(ir_node *n) {
 147   int i, j, k;
 148
 149   /* should always be pointer mode or we made some mistake */
 150   assert(mode_is_reference(get_irn_mode(n)));
 151
 152   for (i = get_irn_n_outs(n) - 1; i >= 0; --i) {
 153     ir_node *succ = get_irn_out(n, i);
 154
 155     switch (get_irn_opcode(succ)) {
 156     case iro_Store:
 157       if (get_Store_value(succ) == n) {
 158         ir_node *adr = get_Store_ptr(succ);
 159
 160         /*
 161          * if this Alloc depends on another one,
 162          * we can enqueue it
 163          */
 164         if (is_depend_alloc(adr))
 165           break;
 166
 167         /*
 168          * We are storing n. As long as we do not further
 169          * evaluate things, the pointer 'escape' here
 170          */
 171         return 1;
 172       }
 173       break;
 174
 175     case iro_Conv:
 176       /*
 177        * Should not happen, but if it does we leave the pointer
 178        * path and do not track further
 179        */
 180       return 1;
 181
 182     case iro_Call: { /* most complicated case */
 183       ir_node *ptr = get_Call_ptr(succ);
 184       ir_entity *ent;
 185
 186       if (is_SymConst_addr_ent(ptr)) {
 187         ent = get_SymConst_entity(ptr);
 188
 189         /* we know the called entity */
 190         for (j = get_Call_n_params(succ) - 1; j >= 0; --j) {
 191           if (get_Call_param(succ, j) == n) {
 192             /* n is the j'th param of the call */
 193             if (get_method_param_access(ent, j) & ptr_access_store)
 194               /* n is store in ent */
 195               return 1;
 196           }
 197         }
 198       }
 199       else if (is_Sel(ptr)) {
 200         /* go through all possible callees */
 201         for (k = get_Call_n_callees(succ) - 1; k >= 0; --k) {
 202           ent = get_Call_callee(succ, k);
 203
 204           if (ent == unknown_entity) {
 205             /* we don't know what will be called, a possible escape */
 206             return 1;
 207           }
 208
 209           for (j = get_Call_n_params(succ) - 1; j >= 0; --j) {
 210             if (get_Call_param(succ, j) == n) {
 211               /* n is the j'th param of the call */
 212               if (get_method_param_access(ent, j) & ptr_access_store)
 213                 /* n is store in ent */
 214                 return 1;
 215             }
 216           }
 217         }
 218       }
 219       else /* we don't know want will called */
 220         return 1;
 221
 222       break;
 223     }
 224
 225     case iro_Return:
 226       /* Bad: the allocate object is returned */
 227       return 1;
 228
 229     case iro_Raise:
 230       /* Hmm: if we do NOT leave the method, it's local */
 231       if (is_method_leaving_raise(succ))
 232         return 1;
 233       break;
 234
 235     case iro_Tuple: {
 236       ir_node *proj;
 237
 238       /* Bad: trace the tuple backwards */
 239       for (j = get_irn_arity(succ) - 1; j >= 0; --j)
 240         if (get_irn_n(succ, j) == n)
 241           break;
 242
 243       assert(j >= 0);
 244
 245
 246       for (k = get_irn_n_outs(succ); k >= 0; --k) {
 247         proj = get_irn_out(succ, k);
 248
 249         if (get_Proj_proj(proj) == j) {
 250           /* we found the right Proj */
 251           succ = proj;
 252           break;
 253         }
 254       }
 255
 256       /*
 257        * If we haven't found the right Proj, succ is still
 258        * the Tuple and the search will end here.
 259        */
 260       break;
 261     }
 262
 263     default:
 264       break;
 265
 266     }
 267
 268     if (! mode_is_reference(get_irn_mode(succ)))
 269       continue;
 270
 271     if (can_escape(succ))
 272       return 1;
 273   }
 274   return 0;
 275 }
 276
 277 /**
 278  * walker: search for Alloc nodes and follow the usages
 279  */
 280 static void find_allocations(ir_node *alloc, void *ctx)
 281 {
 282   int i;
 283   ir_node *adr;
 284   walk_env_t *env = ctx;
 285
 286   if (! is_Alloc(alloc))
 287     return;
 288
 289   /* we searching only for heap allocations */
 290   if (get_Alloc_where(alloc) != heap_alloc)
 291     return;
 292
 293   adr = NULL;
 294   for (i = get_irn_n_outs(alloc) - 1; i >= 0; --i) {
 295     ir_node *proj = get_irn_out(alloc, i);
 296
 297     if (get_Proj_proj(proj) == pn_Alloc_res) {
 298       adr = proj;
 299       break;
 300     }
 301   }
 302
 303   if (! adr) {
 304     /*
 305      * bad: no-one wants the result, should NOT happen but
 306      * if it does we could delete it.
 307      */
 308     set_irn_link(alloc, env->dead_allocs);
 309     env->dead_allocs = alloc;
 310
 311     return;
 312   }
 313
 314   if (! can_escape(adr)) {
 315     set_irn_link(alloc, env->found_allocs);
 316     env->found_allocs = alloc;
 317   }
 318 }
 319
 320 /**
 321  * walker: search for allocation Call nodes and follow the usages
 322  */
 323 static void find_allocation_calls(ir_node *call, void *ctx)
 324 {
 325   int        i;
 326   ir_node    *adr;
 327   ir_entity  *ent;
 328   walk_env_t *env = ctx;
 329
 330   if (! is_Call(call))
 331     return;
 332   adr = get_Call_ptr(call);
 333   if (! is_SymConst_addr_ent(adr))
 334     return;
 335   ent = get_SymConst_entity(adr);
 336   if (! env->callback(ent))
 337     return;
 338
 339   adr = NULL;
 340   for (i = get_irn_n_outs(call) - 1; i >= 0; --i) {
 341     ir_node *res_proj = get_irn_out(call, i);
 342
 343     if (get_Proj_proj(res_proj) == pn_Call_T_result) {
 344       for (i = get_irn_n_outs(res_proj) - 1; i >= 0; --i) {
 345         ir_node *proj = get_irn_out(res_proj, i);
 346
 347         if (get_Proj_proj(proj) == 0) {
 348           /* found first result */
 349           adr = proj;
 350           break;
 351         }
 352       }
 353       break;
 354     }
 355   }
 356
 357   if (! adr) {
 358     /*
 359      * bad: no-one wants the result, should NOT happen but
 360      * if it does we could delete it.
 361      */
 362     set_irn_link(call, env->dead_allocs);
 363     env->dead_allocs = call;
 364
 365     return;
 366   }
 367
 368   if (! can_escape(adr)) {
 369     set_irn_link(call, env->found_allocs);
 370     env->found_allocs = call;
 371   }
 372 }
 373
 374 /**
 375  * Do the necessary graph transformations to transform
 376  * Alloc nodes.
 377  */
 378 static void transform_allocs(ir_graph *irg, walk_env_t *env)
 379 {
 380   ir_node *alloc, *next, *mem, *sel, *size, *blk;
 381   ir_type *ftp, *atp, *tp;
 382   ir_entity *ent;
 383   char name[128];
 384   unsigned nr = 0;
 385   dbg_info *dbg;
 386
 387   /* kill all dead allocs */
 388   for (alloc = env->dead_allocs; alloc; alloc = next) {
 389     next = get_irn_link(alloc);
 390
 391     DBG((dbgHandle, LEVEL_1, "%+F allocation of %+F unused, deleted.\n", irg, alloc));
 392
 393     mem = get_Alloc_mem(alloc);
 394         blk = get_nodes_block(alloc);
 395     turn_into_tuple(alloc, pn_Alloc_max);
 396     set_Tuple_pred(alloc, pn_Alloc_M, mem);
 397     set_Tuple_pred(alloc, pn_Alloc_X_regular, new_r_Jmp(irg, blk));
 398     set_Tuple_pred(alloc, pn_Alloc_X_except, new_r_Bad(irg));
 399
 400     ++env->nr_deads;
 401   }
 402
 403   /* convert all non-escaped heap allocs into frame variables */
 404   ftp = get_irg_frame_type(irg);
 405   for (alloc = env->found_allocs; alloc; alloc = next) {
 406     next = get_irn_link(alloc);
 407     size = get_Alloc_size(alloc);
 408     atp  = get_Alloc_type(alloc);
 409
 410     tp = NULL;
 411     if (is_SymConst(size) && get_SymConst_kind(size) == symconst_type_size)  {
 412       /* if the size is a type size and the types matched */
 413       assert(atp == get_SymConst_type(size));
 414       tp = atp;
 415     }
 416     else if (is_Const(size)) {
 417       tarval *tv = get_Const_tarval(size);
 418
 419       if (tv != tarval_bad && tarval_is_long(tv) &&
 420           get_type_state(atp) == layout_fixed &&
 421           (unsigned)get_tarval_long(tv) == get_type_size_bytes(atp)) {
 422         /* a already lowered type size */
 423         tp = atp;
 424       }
 425     }
 426
 427     if (tp && tp != firm_unknown_type) {
 428       /* we could determine the type, so we could place it on the frame */
 429       dbg  = get_irn_dbg_info(alloc);
 430       blk  = get_nodes_block(alloc);
 431
 432       DBG((dbgHandle, LEVEL_DEFAULT, "%+F allocation of %+F type %+F placed on frame\n", irg, alloc, tp));
 433
 434       snprintf(name, sizeof(name), "%s_NE_%u", get_entity_name(get_irg_entity(irg)), nr++);
 435       name[sizeof(name) - 1] = '\0';
 436       ent = new_d_entity(ftp, new_id_from_str(name), get_Alloc_type(alloc), dbg);
 437
 438       sel = new_rd_simpleSel(dbg, irg, get_nodes_block(alloc),
 439         get_irg_no_mem(irg), get_irg_frame(irg), ent);
 440       mem = get_Alloc_mem(alloc);
 441
 442       turn_into_tuple(alloc, pn_Alloc_max);
 443       set_Tuple_pred(alloc, pn_Alloc_M, mem);
 444           set_Tuple_pred(alloc, pn_Alloc_X_regular, new_r_Jmp(irg, blk));
 445       set_Tuple_pred(alloc, pn_Alloc_X_except, new_r_Bad(irg));
 446       set_Tuple_pred(alloc, pn_Alloc_res, sel);
 447
 448       ++env->nr_removed;
 449     }
 450     else {
 451       /*
 452        * We could not determine the type or it is variable size.
 453        * At least, we could place it on the stack
 454        */
 455       DBG((dbgHandle, LEVEL_DEFAULT, "%+F allocation of %+F type %+F placed on stack\n", irg, alloc));
 456       set_Alloc_where(alloc, stack_alloc);
 457
 458       ++env->nr_changed;
 459     }
 460   }
 461
 462   /* if allocs were removed somehow */
 463   if (env->nr_removed | env->nr_deads) {
 464     set_irg_outs_inconsistent(irg);
 465
 466     if (env->nr_deads) {
 467       /* exception control flow might have been changed */
 468       set_irg_doms_inconsistent(irg);
 469     }
 470   }
 471 }
 472
 473 /**
 474  * Do the necessary graph transformations to transform
 475  * Call nodes.
 476  */
 477 static void transform_alloc_calls(ir_graph *irg, walk_env_t *env)
 478 {
 479   ir_node *call, *next, *mem, *blk;
 480   ir_type *ftp;
 481
 482   /* kill all dead allocs */
 483   for (call = env->dead_allocs; call; call = next) {
 484     next = get_irn_link(call);
 485
 486     DBG((dbgHandle, LEVEL_1, "%+F allocation of %+F unused, deleted.\n", irg, call));
 487
 488     mem = get_Call_mem(call);
 489         blk = get_nodes_block(call);
 490     turn_into_tuple(call, pn_Call_max);
 491     set_Tuple_pred(call, pn_Call_M_regular, mem);
 492         set_Tuple_pred(call, pn_Call_X_regular, new_r_Jmp(irg, blk));
 493     set_Tuple_pred(call, pn_Call_X_except, new_r_Bad(irg));
 494     set_Tuple_pred(call, pn_Call_T_result, new_r_Bad(irg));
 495     set_Tuple_pred(call, pn_Call_M_except, mem);
 496     set_Tuple_pred(call, pn_Call_P_value_res_base, new_r_Bad(irg));
 497
 498     ++env->nr_deads;
 499   }
 500
 501   /* convert all non-escaped heap allocs into frame variables */
 502   ftp = get_irg_frame_type(irg);
 503   for (call = env->found_allocs; call; call = next) {
 504     next = get_irn_link(call);
 505   }
 506 }
 507
 508
 509 /* Do simple and fast escape analysis for one graph. */
 510 void escape_enalysis_irg(ir_graph *irg, check_alloc_entity_func callback)
 511 {
 512   walk_env_t env;
 513
 514   if (get_irg_callee_info_state(irg) != irg_callee_info_consistent) {
 515     /* no way yet to calculate this for one irg */
 516     assert(! "need callee info");
 517     return;
 518   }
 519
 520   if (get_irg_outs_state(irg) != outs_consistent)
 521     compute_irg_outs(irg);
 522
 523   env.found_allocs = NULL;
 524   env.dead_allocs  = NULL;
 525   env.callback     = callback;
 526   env.nr_removed   = 0;
 527   env.nr_changed   = 0;
 528   env.nr_deads     = 0;
 529
 530   if (callback) {
 531     /* search for Calls */
 532     irg_walk_graph(irg, NULL, find_allocation_calls, &env);
 533     transform_alloc_calls(irg, &env);
 534   } else {
 535     /* search for Alloc nodes */
 536     irg_walk_graph(irg, NULL, find_allocations, &env);
 537     transform_allocs(irg, &env);
 538   }
 539 }
 540
 541 /* Do simple and fast escape analysis for all graphs. */
 542 void escape_analysis(int run_scalar_replace, check_alloc_entity_func callback)
 543 {
 544   ir_graph *irg;
 545   int i;
 546   struct obstack obst;
 547   walk_env_t *env, *elist;
 548   (void) run_scalar_replace;
 549
 550   if (get_irp_callee_info_state() != irg_callee_info_consistent) {
 551     assert(! "need callee info");
 552     return;
 553   }
 554
 555   FIRM_DBG_REGISTER(dbgHandle, "firm.opt.escape_ana");
 556
 557   /*
 558    * We treat memory for speed: we first collect all info in a
 559    * list of environments, than do the transformation.
 560    * Doing it this way, no analysis info gets invalid while we run
 561    * over graphs
 562    */
 563   obstack_init(&obst);
 564   elist = NULL;
 565
 566   env = obstack_alloc(&obst, sizeof(*env));
 567   env->found_allocs = NULL;
 568   env->dead_allocs  = NULL;
 569   env->callback     = callback;
 570
 571   for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 572     irg = get_irp_irg(i);
 573
 574     assure_irg_outs(irg);
 575
 576     if (callback) {
 577       /* search for Calls */
 578       irg_walk_graph(irg, NULL, find_allocation_calls, env);
 579     } else {
 580       /* search for Alloc nodes */
 581       irg_walk_graph(irg, NULL, find_allocations, env);
 582     }
 583
 584     if (env->found_allocs || env->dead_allocs) {
 585       env->nr_removed   = 0;
 586       env->nr_deads     = 0;
 587       env->irg          = irg;
 588       env->next         = elist;
 589
 590       elist = env;
 591
 592       env = obstack_alloc(&obst, sizeof(*env));
 593       env->found_allocs = NULL;
 594       env->dead_allocs  = NULL;
 595       env->callback     = callback;
 596     }
 597   }
 598
 599   if (callback) {
 600     for (env = elist; env; env = env->next) {
 601       transform_alloc_calls(env->irg, env);
 602     }
 603   } else {
 604     for (env = elist; env; env = env->next) {
 605       transform_allocs(env->irg, env);
 606     }
 607   }
 608
 609   obstack_free(&obst, NULL);
 610 }