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

   1 /*
   2  * Copyright (C) 1995-2008 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 #include "config.h"
  37
  38 #include "iroptimize.h"
  39
  40 #include "irgraph_t.h"
  41 #include "irnode_t.h"
  42 #include "type_t.h"
  43 #include "irgwalk.h"
  44 #include "irouts.h"
  45 #include "analyze_irg_args.h"
  46 #include "irgmod.h"
  47 #include "ircons.h"
  48 #include "irprintf.h"
  49 #include "debug.h"
  50 #include "error.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   check_alloc_entity_func callback; /**< callback that checks a given entity for allocation */
  59   unsigned nr_removed;              /**< number of removed allocs (placed of frame) */
  60   unsigned nr_changed;              /**< number of changed allocs (allocated on stack now) */
  61   unsigned nr_deads;                /**< number of dead allocs */
  62
  63   /* these fields are only used in the global escape analysis */
  64   ir_graph *irg;                    /**< the irg for this environment */
  65   struct walk_env *next;           /**< for linking environments */
  66
  67 } walk_env_t;
  68
  69 /** debug handle */
  70 DEBUG_ONLY(firm_dbg_module_t *dbgHandle;)
  71
  72 /**
  73  * checks whether a Raise leaves a method
  74  */
  75 static int is_method_leaving_raise(ir_node *raise)
  76 {
  77   int i;
  78   ir_node *proj = NULL;
  79   ir_node *n;
  80
  81   for (i = get_irn_n_outs(raise) - 1; i >= 0; --i) {
  82     ir_node *succ = get_irn_out(raise, i);
  83
  84     /* there should be only one ProjX node */
  85     if (get_Proj_proj(succ) == pn_Raise_X) {
  86       proj = succ;
  87       break;
  88     }
  89   }
  90
  91   if (! proj) {
  92     /* Hmm: no ProjX from a Raise? This should be a verification
  93      * error. For now we just assert and return.
  94      */
  95     panic("No ProjX after Raise found");
  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     panic("More than one user of ProjX");
 103   }
 104
 105   n = get_irn_out(proj, 0);
 106   assert(is_Block(n) && "Argh: user of ProjX is no block");
 107
 108   if (n == get_irg_end_block(get_irn_irg(n)))
 109     return 1;
 110
 111   /* ok, we get here so the raise will not leave the function */
 112   return 0;
 113 }
 114
 115 /**
 116  * returns an Alloc node if the node adr Select
 117  * from one
 118  */
 119 static ir_node *is_depend_alloc(ir_node *adr)
 120 {
 121   ir_node *alloc;
 122
 123   if (!is_Sel(adr))
 124     return NULL;
 125
 126   /* should be a simple Sel */
 127   if (get_Sel_n_indexs(adr) != 0)
 128     return NULL;
 129
 130   alloc = skip_Proj(get_Sel_ptr(adr));
 131   if (!is_Alloc(alloc))
 132     return NULL;
 133
 134   /* hmm, we depend on this Alloc */
 135   ir_printf("depend alloc %+F\n", alloc);
 136
 137   return NULL;
 138 }
 139
 140 /**
 141  * determine if a value calculated by n "escape", ie
 142  * is stored somewhere we could not track
 143  */
 144 static int can_escape(ir_node *n)
 145 {
 146   int i, j, k;
 147
 148   /* should always be pointer mode or we made some mistake */
 149   assert(mode_is_reference(get_irn_mode(n)));
 150
 151   for (i = get_irn_n_outs(n) - 1; i >= 0; --i) {
 152     ir_node *succ = get_irn_out(n, i);
 153
 154     switch (get_irn_opcode(succ)) {
 155     case iro_Store:
 156       if (get_Store_value(succ) == n) {
 157         ir_node *adr = get_Store_ptr(succ);
 158
 159         /*
 160          * if this Alloc depends on another one,
 161          * we can enqueue it
 162          */
 163         if (is_depend_alloc(adr))
 164           break;
 165
 166         /*
 167          * We are storing n. As long as we do not further
 168          * evaluate things, the pointer 'escape' here
 169          */
 170         return 1;
 171       }
 172       break;
 173
 174     case iro_Conv:
 175       /*
 176        * Should not happen, but if it does we leave the pointer
 177        * path and do not track further
 178        */
 179       return 1;
 180
 181     case iro_Call: { /* most complicated case */
 182       ir_node *ptr = get_Call_ptr(succ);
 183       ir_entity *ent;
 184
 185       if (is_SymConst_addr_ent(ptr)) {
 186         ent = get_SymConst_entity(ptr);
 187
 188         /* we know the called entity */
 189         for (j = get_Call_n_params(succ) - 1; j >= 0; --j) {
 190           if (get_Call_param(succ, j) == n) {
 191             /* n is the j'th param of the call */
 192             if (get_method_param_access(ent, j) & ptr_access_store)
 193               /* n is store in ent */
 194               return 1;
 195           }
 196         }
 197       }
 198       else if (is_Sel(ptr)) {
 199         /* go through all possible callees */
 200         for (k = get_Call_n_callees(succ) - 1; k >= 0; --k) {
 201           ent = get_Call_callee(succ, k);
 202
 203           if (ent == unknown_entity) {
 204             /* we don't know what will be called, a possible escape */
 205             return 1;
 206           }
 207
 208           for (j = get_Call_n_params(succ) - 1; j >= 0; --j) {
 209             if (get_Call_param(succ, j) == n) {
 210               /* n is the j'th param of the call */
 211               if (get_method_param_access(ent, j) & ptr_access_store)
 212                 /* n is store in ent */
 213                 return 1;
 214             }
 215           }
 216         }
 217       }
 218       else /* we don't know want will called */
 219         return 1;
 220
 221       break;
 222     }
 223
 224     case iro_Return:
 225       /* Bad: the allocate object is returned */
 226       return 1;
 227
 228     case iro_Raise:
 229       /* Hmm: if we do NOT leave the method, it's local */
 230       if (is_method_leaving_raise(succ))
 231         return 1;
 232       break;
 233
 234     case iro_Tuple: {
 235       ir_node *proj;
 236
 237       /* Bad: trace the tuple backwards */
 238       for (j = get_irn_arity(succ) - 1; j >= 0; --j)
 239         if (get_irn_n(succ, j) == n)
 240           break;
 241
 242       assert(j >= 0);
 243
 244
 245       for (k = get_irn_n_outs(succ); k >= 0; --k) {
 246         proj = get_irn_out(succ, k);
 247
 248         if (get_Proj_proj(proj) == j) {
 249           /* we found the right Proj */
 250           succ = proj;
 251           break;
 252         }
 253       }
 254
 255       /*
 256        * If we haven't found the right Proj, succ is still
 257        * the Tuple and the search will end here.
 258        */
 259       break;
 260     }
 261
 262     default:
 263       break;
 264
 265     }
 266
 267     if (! mode_is_reference(get_irn_mode(succ)))
 268       continue;
 269
 270     if (can_escape(succ))
 271       return 1;
 272   }
 273   return 0;
 274 }
 275
 276 /**
 277  * walker: search for Alloc nodes and follow the usages
 278  */
 279 static void find_allocations(ir_node *alloc, void *ctx)
 280 {
 281   walk_env_t *env = (walk_env_t*)ctx;
 282   int i;
 283   ir_node *adr;
 284
 285   if (! is_Alloc(alloc))
 286     return;
 287
 288   /* we searching only for heap allocations */
 289   if (get_Alloc_where(alloc) != heap_alloc)
 290     return;
 291
 292   adr = NULL;
 293   for (i = get_irn_n_outs(alloc) - 1; i >= 0; --i) {
 294     ir_node *proj = get_irn_out(alloc, i);
 295
 296     if (get_Proj_proj(proj) == pn_Alloc_res) {
 297       adr = proj;
 298       break;
 299     }
 300   }
 301
 302   if (! adr) {
 303     /*
 304      * bad: no-one wants the result, should NOT happen but
 305      * if it does we could delete it.
 306      */
 307     set_irn_link(alloc, env->dead_allocs);
 308     env->dead_allocs = alloc;
 309
 310     return;
 311   }
 312
 313   if (! can_escape(adr)) {
 314     set_irn_link(alloc, env->found_allocs);
 315     env->found_allocs = alloc;
 316   }
 317 }
 318
 319 /**
 320  * walker: search for allocation Call nodes and follow the usages
 321  */
 322 static void find_allocation_calls(ir_node *call, void *ctx)
 323 {
 324   walk_env_t *env = (walk_env_t*)ctx;
 325   int        i;
 326   ir_node    *adr;
 327   ir_entity  *ent;
 328
 329   if (! is_Call(call))
 330     return;
 331   adr = get_Call_ptr(call);
 332   if (! is_SymConst_addr_ent(adr))
 333     return;
 334   ent = get_SymConst_entity(adr);
 335   if (! env->callback(ent))
 336     return;
 337
 338   adr = NULL;
 339   for (i = get_irn_n_outs(call) - 1; i >= 0; --i) {
 340     ir_node *res_proj = get_irn_out(call, i);
 341
 342     if (get_Proj_proj(res_proj) == pn_Call_T_result) {
 343       for (i = get_irn_n_outs(res_proj) - 1; i >= 0; --i) {
 344         ir_node *proj = get_irn_out(res_proj, i);
 345
 346         if (get_Proj_proj(proj) == 0) {
 347           /* found first result */
 348           adr = proj;
 349           break;
 350         }
 351       }
 352       break;
 353     }
 354   }
 355
 356   if (! adr) {
 357     /*
 358      * bad: no-one wants the result, should NOT happen but
 359      * if it does we could delete it.
 360      */
 361     set_irn_link(call, env->dead_allocs);
 362     env->dead_allocs = call;
 363
 364     return;
 365   }
 366
 367   if (! can_escape(adr)) {
 368     set_irn_link(call, env->found_allocs);
 369     env->found_allocs = call;
 370   }
 371 }
 372
 373 /**
 374  * Do the necessary graph transformations to transform
 375  * Alloc nodes.
 376  */
 377 static void transform_allocs(ir_graph *irg, walk_env_t *env)
 378 {
 379   ir_node *alloc, *next, *mem, *sel, *size, *blk;
 380   ir_type *ftp, *atp, *tp;
 381   ir_entity *ent;
 382   char name[128];
 383   unsigned nr = 0;
 384   dbg_info *dbg;
 385
 386   /* kill all dead allocs */
 387   for (alloc = env->dead_allocs; alloc; alloc = next) {
 388     next = (ir_node*)get_irn_link(alloc);
 389
 390     DBG((dbgHandle, LEVEL_1, "%+F allocation of %+F unused, deleted.\n", irg, alloc));
 391
 392     mem = get_Alloc_mem(alloc);
 393         blk = get_nodes_block(alloc);
 394     turn_into_tuple(alloc, pn_Alloc_max);
 395     set_Tuple_pred(alloc, pn_Alloc_M, mem);
 396     set_Tuple_pred(alloc, pn_Alloc_X_regular, new_r_Jmp(blk));
 397     set_Tuple_pred(alloc, pn_Alloc_X_except, new_r_Bad(irg));
 398
 399     ++env->nr_deads;
 400   }
 401
 402   /* convert all non-escaped heap allocs into frame variables */
 403   ftp = get_irg_frame_type(irg);
 404   for (alloc = env->found_allocs; alloc; alloc = next) {
 405     next = (ir_node*)get_irn_link(alloc);
 406     size = get_Alloc_count(alloc);
 407     atp  = get_Alloc_type(alloc);
 408
 409     tp = NULL;
 410     if (is_SymConst(size) && get_SymConst_kind(size) == symconst_type_size)  {
 411       /* if the size is a type size and the types matched */
 412       assert(atp == get_SymConst_type(size));
 413       tp = atp;
 414     } else if (is_Const(size)) {
 415       ir_tarval *tv = get_Const_tarval(size);
 416
 417       if (tv != tarval_bad && tarval_is_long(tv) &&
 418           get_type_state(atp) == layout_fixed &&
 419           (unsigned)get_tarval_long(tv) == get_type_size_bytes(atp)) {
 420         /* a already lowered type size */
 421         tp = atp;
 422       }
 423     }
 424
 425     if (tp && tp != firm_unknown_type) {
 426       /* we could determine the type, so we could place it on the frame */
 427       dbg  = get_irn_dbg_info(alloc);
 428       blk  = get_nodes_block(alloc);
 429
 430       DBG((dbgHandle, LEVEL_DEFAULT, "%+F allocation of %+F type %+F placed on frame\n", irg, alloc, tp));
 431
 432       snprintf(name, sizeof(name), "%s_NE_%u", get_entity_name(get_irg_entity(irg)), nr++);
 433       name[sizeof(name) - 1] = '\0';
 434       ent = new_d_entity(ftp, new_id_from_str(name), get_Alloc_type(alloc), dbg);
 435
 436       sel = new_rd_simpleSel(dbg, get_nodes_block(alloc), get_irg_no_mem(irg), get_irg_frame(irg), ent);
 437       mem = get_Alloc_mem(alloc);
 438
 439       turn_into_tuple(alloc, pn_Alloc_max);
 440       set_Tuple_pred(alloc, pn_Alloc_M, mem);
 441           set_Tuple_pred(alloc, pn_Alloc_X_regular, new_r_Jmp(blk));
 442       set_Tuple_pred(alloc, pn_Alloc_X_except, new_r_Bad(irg));
 443       set_Tuple_pred(alloc, pn_Alloc_res, sel);
 444
 445       ++env->nr_removed;
 446     }
 447     else {
 448       /*
 449        * We could not determine the type or it is variable size.
 450        * At least, we could place it on the stack
 451        */
 452       DBG((dbgHandle, LEVEL_DEFAULT, "%+F allocation of %+F type %+F placed on stack\n", irg, alloc));
 453       set_Alloc_where(alloc, stack_alloc);
 454
 455       ++env->nr_changed;
 456     }
 457   }
 458
 459   /* if allocs were removed somehow */
 460   if (env->nr_removed | env->nr_deads) {
 461     set_irg_outs_inconsistent(irg);
 462
 463     if (env->nr_deads) {
 464       /* exception control flow might have been changed */
 465       set_irg_doms_inconsistent(irg);
 466     }
 467   }
 468 }
 469
 470 /**
 471  * Do the necessary graph transformations to transform
 472  * Call nodes.
 473  */
 474 static void transform_alloc_calls(ir_graph *irg, walk_env_t *env)
 475 {
 476   ir_node *call, *next, *mem, *blk;
 477   ir_type *ftp;
 478
 479   /* kill all dead allocs */
 480   for (call = env->dead_allocs; call; call = next) {
 481     next = (ir_node*)get_irn_link(call);
 482
 483     DBG((dbgHandle, LEVEL_1, "%+F allocation of %+F unused, deleted.\n", irg, call));
 484
 485     mem = get_Call_mem(call);
 486         blk = get_nodes_block(call);
 487     turn_into_tuple(call, pn_Call_max);
 488     set_Tuple_pred(call, pn_Call_M,                mem);
 489         set_Tuple_pred(call, pn_Call_X_regular,        new_r_Jmp(blk));
 490     set_Tuple_pred(call, pn_Call_X_except,         new_r_Bad(irg));
 491     set_Tuple_pred(call, pn_Call_T_result,         new_r_Bad(irg));
 492     set_Tuple_pred(call, pn_Call_P_value_res_base, new_r_Bad(irg));
 493
 494     ++env->nr_deads;
 495   }
 496
 497   /* convert all non-escaped heap allocs into frame variables */
 498   ftp = get_irg_frame_type(irg);
 499   for (call = env->found_allocs; call; call = next) {
 500     next = (ir_node*)get_irn_link(call);
 501   }
 502 }
 503
 504
 505 /* Do simple and fast escape analysis for one graph. */
 506 void escape_enalysis_irg(ir_graph *irg, check_alloc_entity_func callback)
 507 {
 508   walk_env_t env;
 509
 510   if (get_irg_callee_info_state(irg) != irg_callee_info_consistent) {
 511     /* no way yet to calculate this for one irg */
 512     assert(! "need callee info");
 513     return;
 514   }
 515
 516   if (get_irg_outs_state(irg) != outs_consistent)
 517     compute_irg_outs(irg);
 518
 519   env.found_allocs = NULL;
 520   env.dead_allocs  = NULL;
 521   env.callback     = callback;
 522   env.nr_removed   = 0;
 523   env.nr_changed   = 0;
 524   env.nr_deads     = 0;
 525
 526   if (callback) {
 527     /* search for Calls */
 528     irg_walk_graph(irg, NULL, find_allocation_calls, &env);
 529     transform_alloc_calls(irg, &env);
 530   } else {
 531     /* search for Alloc nodes */
 532     irg_walk_graph(irg, NULL, find_allocations, &env);
 533     transform_allocs(irg, &env);
 534   }
 535 }
 536
 537 /* Do simple and fast escape analysis for all graphs. */
 538 void escape_analysis(int run_scalar_replace, check_alloc_entity_func callback)
 539 {
 540   ir_graph *irg;
 541   int i;
 542   struct obstack obst;
 543   walk_env_t *env, *elist;
 544   (void) run_scalar_replace;
 545
 546   if (get_irp_callee_info_state() != irg_callee_info_consistent) {
 547     assert(! "need callee info");
 548     return;
 549   }
 550
 551   FIRM_DBG_REGISTER(dbgHandle, "firm.opt.escape_ana");
 552
 553   /*
 554    * We treat memory for speed: we first collect all info in a
 555    * list of environments, than do the transformation.
 556    * Doing it this way, no analysis info gets invalid while we run
 557    * over graphs
 558    */
 559   obstack_init(&obst);
 560   elist = NULL;
 561
 562   env = OALLOC(&obst, walk_env_t);
 563   env->found_allocs = NULL;
 564   env->dead_allocs  = NULL;
 565   env->callback     = callback;
 566
 567   for (i = get_irp_n_irgs() - 1; i >= 0; --i) {
 568     irg = get_irp_irg(i);
 569
 570     assure_irg_outs(irg);
 571
 572     if (callback) {
 573       /* search for Calls */
 574       irg_walk_graph(irg, NULL, find_allocation_calls, env);
 575     } else {
 576       /* search for Alloc nodes */
 577       irg_walk_graph(irg, NULL, find_allocations, env);
 578     }
 579
 580     if (env->found_allocs || env->dead_allocs) {
 581       env->nr_removed   = 0;
 582       env->nr_deads     = 0;
 583       env->irg          = irg;
 584       env->next         = elist;
 585
 586       elist = env;
 587
 588       env = OALLOC(&obst, walk_env_t);
 589       env->found_allocs = NULL;
 590       env->dead_allocs  = NULL;
 591       env->callback     = callback;
 592     }
 593   }
 594
 595   if (callback) {
 596     for (env = elist; env; env = env->next) {
 597       transform_alloc_calls(env->irg, env);
 598     }
 599   } else {
 600     for (env = elist; env; env = env->next) {
 601       transform_allocs(env->irg, env);
 602     }
 603   }
 604
 605   obstack_free(&obst, NULL);
 606 }