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