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