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