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

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