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