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

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