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

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