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

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