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