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 /** @file escape_ana.c
  14  *
  15  * escape analysis.
  16  */
  17
  18 #ifdef HAVE_CONFIG_H
  19 # include "config.h"
  20 #endif
  21
  22 #include "irgraph_t.h"
  23 #include "irnode_t.h"
  24 #include "irouts.h"
  25 #include "analyze_irg_args.h"
  26 #include "irgmod.h"
  27 #include "ircons.h"
  28 #include "escape_ana.h"
  29
  30 /**
  31  * walker environment
  32  */
  33 typedef struct _walk_env {
  34   ir_node *found_allocs;    /**< list of all found non-escaped allocs */
  35   ir_node *dead_allocs;     /**< list of all found dead alloc */
  36   unsigned nr_changed;      /**< number of changed allocs */
  37   unsigned nr_deads;        /**< number of dead allocs */
  38
  39   /* these fields are only used in the global escape analysis */
  40   ir_graph *irg;            /**< the irg for this environment */
  41   struct _walk_env *next;   /**< for linking environments */
  42
  43 } walk_env_t;
  44
  45 /**
  46  * determine if a value calculated by n "escape", ie
  47  * is stored somewhere we could not track
  48  */
  49 static int do_escape(ir_node *n) {
  50   int i, j, k;
  51
  52   /* should always be pointer mode or we made some mistake */
  53   assert(mode_is_reference(get_irn_mode(n)));
  54
  55   for (i = get_irn_n_outs(n) - 1; i >= 0; --i) {
  56     ir_node *succ = get_irn_out(n, i);
  57     ir_op *op     = get_irn_op(succ);
  58
  59     if (op == op_Store) {
  60       if (get_Store_value(succ) == n) {
  61         /*
  62          * We are storing n. As long as we do not further
  63          * evaluate things, the pointer 'escape' here
  64          */
  65         return 1;
  66       }
  67     }
  68     else if (op == op_Conv) {
  69       /*
  70        * Should not happen, but if it does we leave the pointer
  71        * path and do not track further
  72        */
  73       return 1;
  74     }
  75     else if (op == op_Call) { /* most complicated case */
  76       ir_node *ptr = get_Call_ptr(succ);
  77       entity *ent;
  78
  79       if (get_irn_op(ptr) == op_SymConst &&
  80           get_SymConst_kind(ptr) == symconst_addr_ent) {
  81         ent = get_SymConst_entity(ptr);
  82
  83         /* we know the called entity */
  84         for (j = get_Call_n_params(succ); j >= 0; --j) {
  85           if (get_Call_param(succ, j) == n) {
  86             /* n is the j'th param of the call */
  87             if (get_method_param_access(ent, j) & ptr_access_store)
  88               /* n is store in ent */
  89               return 1;
  90           }
  91         }
  92       }
  93       else {
  94         /* go through all possible callees */
  95         for (k = get_Call_n_callees(succ) - 1; k >= 0; --k) {
  96           ent = get_Call_callee(succ, k);
  97
  98           for (j = get_Call_n_params(succ); j >= 0; --j) {
  99             if (get_Call_param(succ, j) == n) {
 100               /* n is the j'th param of the call */
 101               if (get_method_param_access(ent, j) & ptr_access_store)
 102                 /* n is store in ent */
 103                 return 1;
 104             }
 105           }
 106         }
 107       }
 108     }
 109
 110     if (! mode_is_reference(get_irn_mode(succ)))
 111       continue;
 112
 113     if (do_escape(succ))
 114       return 1;
 115   }
 116   return 0;
 117 }
 118
 119 /**
 120  * walker: search for Alloc nodes and follow the usages
 121  */
 122 static void find_allocations(ir_node *alloc, void *ctx)
 123 {
 124   int i;
 125   ir_node *adr;
 126   walk_env_t *env = ctx;
 127
 128   if (get_irn_op(alloc) != op_Alloc)
 129     return;
 130
 131   /* we searching only for heap allocations */
 132   if (get_Alloc_where(alloc) != heap_alloc)
 133     return;
 134
 135   adr = NULL;
 136   for (i = get_irn_n_outs(alloc); i >= 0; --i) {
 137     ir_node *proj = get_irn_out(alloc, i);
 138
 139     if (get_Proj_proj(proj) == pn_Alloc_res) {
 140       adr = proj;
 141       break;
 142     }
 143   }
 144
 145   if (! adr) {
 146     /*
 147      * bad: no-one wants the result, should NOT happen but
 148      * if it does we could delete it.
 149      */
 150     set_irn_link(alloc, env->dead_allocs);
 151     env->dead_allocs = alloc;
 152
 153     return;
 154   }
 155
 156   if (! do_escape(adr)) {
 157     set_irn_link(alloc, env->found_allocs);
 158     env->found_allocs = alloc;
 159   }
 160 }
 161
 162 /**
 163  * do the necessary graph transformations
 164  */
 165 static void transform_allocs(ir_graph *irg, walk_env_t *env)
 166 {
 167   ir_node *alloc, *next, *mem, *sel;
 168   type *ftp;
 169   entity *ent;
 170   char name[32];
 171   unsigned nr = 0;
 172   dbg_info *dbg;
 173
 174   /* kill all dead allocs */
 175   for (alloc = env->dead_allocs; alloc; alloc = next) {
 176     next = get_irn_link(alloc);
 177
 178     mem = get_Alloc_mem(alloc);
 179     turn_into_tuple(alloc, pn_Alloc_max);
 180     set_Tuple_pred(alloc, pn_Alloc_M, mem);
 181     set_Tuple_pred(alloc, pn_Alloc_X_except, new_r_Bad(irg));
 182
 183     ++env->nr_deads;
 184   }
 185
 186   /* convert all non-escaped heap allocs into frame variables */
 187   ftp = get_irg_frame_type(irg);
 188   for (alloc = env->dead_allocs; alloc; alloc = next) {
 189     next = get_irn_link(alloc);
 190     dbg  = get_irn_dbg_info(alloc);
 191
 192     snprintf(name, sizeof(name), "_not_escaped_%u", nr++);
 193     ent = new_d_entity(ftp, new_id_from_str(name), get_Alloc_type(alloc), dbg);
 194
 195     sel = new_rd_simpleSel(dbg, irg, get_nodes_block(alloc),
 196       get_irg_no_mem(irg), get_irg_frame(irg), ent);
 197     mem = get_Alloc_mem(alloc);
 198
 199     turn_into_tuple(alloc, pn_Alloc_max);
 200     set_Tuple_pred(alloc, pn_Alloc_M, mem);
 201     set_Tuple_pred(alloc, pn_Alloc_X_except, new_r_Bad(irg));
 202     set_Tuple_pred(alloc, pn_Alloc_res, sel);
 203
 204     ++env->nr_changed;
 205   }
 206
 207   if (env->nr_changed | env->nr_deads) {
 208     set_irg_outs_inconsistent(irg);
 209
 210     if (env->nr_deads)
 211       set_irg_dom_inconsistent(irg);
 212   }
 213 }
 214
 215 /* Do simple and fast escape analysis for one graph. */
 216 void escape_enalysis_irg(ir_graph *irg)
 217 {
 218   walk_env_t env;
 219
 220   if (get_irg_callee_info_state(irg) != irg_callee_info_consistent) {
 221     /* no way yet to calculate this for one irg */
 222     assert(! "need callee info");
 223     return;
 224   }
 225
 226   if (get_irg_outs_state(irg) != outs_consistent)
 227     compute_irg_outs(irg);
 228
 229   env.found_allocs = NULL;
 230   env.dead_allocs  = NULL;
 231   env.nr_changed   = 0;
 232   env.nr_deads     = 0;
 233
 234   irg_walk_graph(irg, NULL, find_allocations, &env);
 235
 236   transform_allocs(irg, &env);
 237 }
 238
 239 /* Do simple and fast escape analysis for all graphs. */
 240 void escape_analysis(int run_scalar_replace)
 241 {
 242   ir_graph *irg;
 243   int i;
 244   struct obstack obst;
 245   walk_env_t *env, *elist;
 246
 247   if (get_irp_callee_info_state() != irg_callee_info_consistent) {
 248     assert(! "need callee info");
 249     return;
 250   }
 251
 252   /*
 253    * We treat memory for speed: we first collect all info in a
 254    * list of environments, than do the transformation.
 255    * Doing it this way, no analysis info gets invalid while we run
 256    * over graphs
 257    */
 258   obstack_init(&obst);
 259   elist = NULL;
 260
 261   env = obstack_alloc(&obst, sizeof(*env));
 262   env->found_allocs = NULL;
 263   env->dead_allocs  = NULL;
 264
 265   for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 266     irg = get_irp_irg(i);
 267
 268     if (get_irg_outs_state(irg) != outs_consistent)
 269       compute_irg_outs(irg);
 270
 271     irg_walk_graph(irg, NULL, find_allocations, &env);
 272
 273     if (env->found_allocs || env->dead_allocs) {
 274       env->nr_changed   = 0;
 275       env->nr_deads     = 0;
 276       env->irg          = irg;
 277       env->next         = elist;
 278
 279       elist = env;
 280
 281       env = obstack_alloc(&obst, sizeof(*env));
 282       env->found_allocs = NULL;
 283       env->dead_allocs  = NULL;
 284     }
 285   }
 286
 287   for (env = elist; env; env = env->next) {
 288     transform_allocs(env->irg, env);
 289   }
 290
 291   obstack_free(&obst, NULL);
 292 }