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

   1 /*
   2  * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief    Code Placement.  Pins all floating nodes to a block where they
  23  *           will be executed only if needed.
  24  * @author   Christian Schaefer, Goetz Lindenmaier, Sebastian Felis,
  25  *           Michael Beck
  26  * @version  $Id$
  27  */
  28 #ifdef HAVE_CONFIG_H
  29 # include "config.h"
  30 #endif
  31
  32 #include "adt/pdeq.h"
  33 #include "irnode_t.h"
  34 #include "irouts.h"
  35 #include "irgopt.h"
  36
  37 /**
  38  * Returns non-zero, is a block is not reachable from Start.
  39  *
  40  * @param block  the block to test
  41  */
  42 static int
  43 is_Block_unreachable(ir_node *block) {
  44         return is_Block_dead(block) || get_Block_dom_depth(block) < 0;
  45 }
  46
  47 /**
  48  * Find the earliest correct block for node n.  --- Place n into the
  49  * same Block as its dominance-deepest Input.
  50  *
  51  * We have to avoid calls to get_nodes_block() here
  52  * because the graph is floating.
  53  *
  54  * move_out_of_loops() expects that place_floats_early() have placed
  55  * all "living" nodes into a living block. That's why we must
  56  * move nodes in dead block with "live" successors into a valid
  57  * block.
  58  * We move them just into the same block as it's successor (or
  59  * in case of a Phi into the effective use block). For Phi successors,
  60  * this may still be a dead block, but then there is no real use, as
  61  * the control flow will be dead later.
  62  *
  63  * @param n         the node to be placed
  64  * @param worklist  a worklist, predecessors of non-floating nodes are placed here
  65  */
  66 static void
  67 place_floats_early(ir_node *n, waitq *worklist) {
  68         int i, irn_arity;
  69
  70         /* we must not run into an infinite loop */
  71         assert(irn_not_visited(n));
  72         mark_irn_visited(n);
  73
  74         /* Place floating nodes. */
  75         if (get_irn_pinned(n) == op_pin_state_floats) {
  76                 ir_node *curr_block = get_nodes_block(n);
  77                 int in_dead_block   = is_Block_unreachable(curr_block);
  78                 int depth           = 0;
  79                 ir_node *b          = NULL;   /* The block to place this node in */
  80
  81                 assert(is_no_Block(n));
  82
  83                 if (is_irn_start_block_placed(n)) {
  84                         /* These nodes will not be placed by the loop below. */
  85                         b = get_irg_start_block(current_ir_graph);
  86                         depth = 1;
  87                 }
  88
  89                 /* find the block for this node. */
  90                 irn_arity = get_irn_arity(n);
  91                 for (i = 0; i < irn_arity; i++) {
  92                         ir_node *pred = get_irn_n(n, i);
  93                         ir_node *pred_block;
  94
  95                         if ((irn_not_visited(pred))
  96                             && (get_irn_pinned(pred) == op_pin_state_floats)) {
  97
  98                                 /*
  99                                  * If the current node is NOT in a dead block, but one of its
 100                                  * predecessors is, we must move the predecessor to a live block.
 101                                  * Such thing can happen, if global CSE chose a node from a dead block.
 102                                  * We move it simply to our block.
 103                                  * Note that neither Phi nor End nodes are floating, so we don't
 104                                  * need to handle them here.
 105                                  */
 106                                 if (! in_dead_block) {
 107                                         if (get_irn_pinned(pred) == op_pin_state_floats &&
 108                                                 is_Block_unreachable(get_nodes_block(pred)))
 109                                                 set_nodes_block(pred, curr_block);
 110                                 }
 111                                 place_floats_early(pred, worklist);
 112                         }
 113
 114                         /*
 115                          * A node in the Bad block must stay in the bad block,
 116                          * so don't compute a new block for it.
 117                          */
 118                         if (in_dead_block)
 119                                 continue;
 120
 121                         /* Because all loops contain at least one op_pin_state_pinned node, now all
 122                            our inputs are either op_pin_state_pinned or place_early() has already
 123                            been finished on them.  We do not have any unfinished inputs!  */
 124                         pred_block = get_nodes_block(pred);
 125                         if ((!is_Block_dead(pred_block)) &&
 126                                 (get_Block_dom_depth(pred_block) > depth)) {
 127                                 b = pred_block;
 128                                 depth = get_Block_dom_depth(pred_block);
 129                         }
 130                         /* Avoid that the node is placed in the Start block */
 131                         if (depth == 1 &&
 132                                         get_Block_dom_depth(get_nodes_block(n)) > 1 &&
 133                                         get_irg_phase_state(current_ir_graph) != phase_backend) {
 134                                 b = get_Block_cfg_out(get_irg_start_block(current_ir_graph), 0);
 135                                 assert(b != get_irg_start_block(current_ir_graph));
 136                                 depth = 2;
 137                         }
 138                 }
 139                 if (b)
 140                         set_nodes_block(n, b);
 141         }
 142
 143         /*
 144          * Add predecessors of non floating nodes and non-floating predecessors
 145          * of floating nodes to worklist and fix their blocks if the are in dead block.
 146          */
 147         irn_arity = get_irn_arity(n);
 148
 149         if (is_End(n)) {
 150                 /*
 151                  * Simplest case: End node. Predecessors are keep-alives,
 152                  * no need to move out of dead block.
 153                  */
 154                 for (i = -1; i < irn_arity; ++i) {
 155                         ir_node *pred = get_irn_n(n, i);
 156                         if (irn_not_visited(pred))
 157                                 waitq_put(worklist, pred);
 158                 }
 159         } else if (is_Block(n)) {
 160                 /*
 161                  * Blocks: Predecessors are control flow, no need to move
 162                  * them out of dead block.
 163                  */
 164                 for (i = irn_arity - 1; i >= 0; --i) {
 165                         ir_node *pred = get_irn_n(n, i);
 166                         if (irn_not_visited(pred))
 167                                 waitq_put(worklist, pred);
 168                 }
 169         } else if (is_Phi(n)) {
 170                 ir_node *pred;
 171                 ir_node *curr_block = get_nodes_block(n);
 172                 int in_dead_block   = is_Block_unreachable(curr_block);
 173
 174                 /*
 175                  * Phi nodes: move nodes from dead blocks into the effective use
 176                  * of the Phi-input if the Phi is not in a bad block.
 177                  */
 178                 pred = get_nodes_block(n);
 179                 if (irn_not_visited(pred))
 180                         waitq_put(worklist, pred);
 181
 182                 for (i = irn_arity - 1; i >= 0; --i) {
 183                         ir_node *pred = get_irn_n(n, i);
 184
 185                         if (irn_not_visited(pred)) {
 186                                 if (! in_dead_block &&
 187                                         get_irn_pinned(pred) == op_pin_state_floats &&
 188                                         is_Block_unreachable(get_nodes_block(pred))) {
 189                                         set_nodes_block(pred, get_Block_cfgpred_block(curr_block, i));
 190                                 }
 191                                 waitq_put(worklist, pred);
 192                         }
 193                 }
 194         } else {
 195                 ir_node *pred;
 196                 ir_node *curr_block = get_nodes_block(n);
 197                 int in_dead_block   = is_Block_unreachable(curr_block);
 198
 199                 /*
 200                  * All other nodes: move nodes from dead blocks into the same block.
 201                  */
 202                 pred = get_nodes_block(n);
 203                 if (irn_not_visited(pred))
 204                         waitq_put(worklist, pred);
 205
 206                 for (i = irn_arity - 1; i >= 0; --i) {
 207                         ir_node *pred = get_irn_n(n, i);
 208
 209                         if (irn_not_visited(pred)) {
 210                                 if (! in_dead_block &&
 211                                         get_irn_pinned(pred) == op_pin_state_floats &&
 212                                         is_Block_unreachable(get_nodes_block(pred))) {
 213                                         set_nodes_block(pred, curr_block);
 214                                 }
 215                                 waitq_put(worklist, pred);
 216                         }
 217                 }
 218         }
 219 }
 220
 221 /**
 222  * Floating nodes form subgraphs that begin at nodes as Const, Load,
 223  * Start, Call and that end at op_pin_state_pinned nodes as Store, Call.  Place_early
 224  * places all floating nodes reachable from its argument through floating
 225  * nodes and adds all beginnings at op_pin_state_pinned nodes to the worklist.
 226  *
 227  * @param worklist   a worklist, used for the algorithm, empty on in/output
 228  */
 229 static void place_early(waitq *worklist) {
 230         assert(worklist);
 231         inc_irg_visited(current_ir_graph);
 232
 233         /* this inits the worklist */
 234         place_floats_early(get_irg_end(current_ir_graph), worklist);
 235
 236         /* Work the content of the worklist. */
 237         while (!waitq_empty(worklist)) {
 238                 ir_node *n = waitq_get(worklist);
 239                 if (irn_not_visited(n))
 240                         place_floats_early(n, worklist);
 241         }
 242
 243         set_irg_outs_inconsistent(current_ir_graph);
 244         set_irg_pinned(current_ir_graph, op_pin_state_pinned);
 245 }
 246
 247 /**
 248  * Compute the deepest common ancestor of block and dca.
 249  */
 250 static ir_node *calc_dca(ir_node *dca, ir_node *block) {
 251         assert(block);
 252
 253         /* we do not want to place nodes in dead blocks */
 254         if (is_Block_dead(block))
 255                 return dca;
 256
 257         /* We found a first legal placement. */
 258         if (!dca) return block;
 259
 260         /* Find a placement that is dominates both, dca and block. */
 261         while (get_Block_dom_depth(block) > get_Block_dom_depth(dca))
 262                 block = get_Block_idom(block);
 263
 264         while (get_Block_dom_depth(dca) > get_Block_dom_depth(block)) {
 265                 dca = get_Block_idom(dca);
 266         }
 267
 268         while (block != dca) {
 269                 block = get_Block_idom(block); dca = get_Block_idom(dca);
 270         }
 271
 272         return dca;
 273 }
 274
 275 /** Deepest common dominance ancestor of DCA and CONSUMER of PRODUCER.
 276  * I.e., DCA is the block where we might place PRODUCER.
 277  * A data flow edge points from producer to consumer.
 278  */
 279 static ir_node *consumer_dom_dca(ir_node *dca, ir_node *consumer, ir_node *producer)
 280 {
 281         /* Compute the last block into which we can place a node so that it is
 282            before consumer. */
 283         if (is_Phi(consumer)) {
 284                 /* our consumer is a Phi-node, the effective use is in all those
 285                    blocks through which the Phi-node reaches producer */
 286                 ir_node *phi_block = get_nodes_block(consumer);
 287                 int      arity     = get_irn_arity(consumer);
 288                 int      i;
 289
 290                 for (i = 0;  i < arity; i++) {
 291                         if (get_Phi_pred(consumer, i) == producer) {
 292                                 ir_node *new_block = get_Block_cfgpred_block(phi_block, i);
 293
 294                                 if (!is_Block_unreachable(new_block))
 295                                         dca = calc_dca(dca, new_block);
 296                         }
 297                 }
 298         } else {
 299                 dca = calc_dca(dca, get_nodes_block(consumer));
 300         }
 301
 302         return dca;
 303 }
 304
 305 /* FIXME: the name clashes here with the function from ana/field_temperature.c
 306  * please rename. */
 307 static INLINE int get_irn_loop_depth(ir_node *n) {
 308         return get_loop_depth(get_irn_loop(n));
 309 }
 310
 311 /**
 312  * Move n to a block with less loop depth than it's current block. The
 313  * new block must be dominated by early.
 314  *
 315  * @param n      the node that should be moved
 316  * @param early  the earliest block we can n move to
 317  */
 318 static void move_out_of_loops(ir_node *n, ir_node *early) {
 319         ir_node *best, *dca;
 320         assert(n && early);
 321
 322
 323         /* Find the region deepest in the dominator tree dominating
 324            dca with the least loop nesting depth, but still dominated
 325            by our early placement. */
 326         dca = get_nodes_block(n);
 327
 328         best = dca;
 329         while (dca != early) {
 330                 dca = get_Block_idom(dca);
 331                 if (!dca || is_Bad(dca)) break; /* may be Bad if not reachable from Start */
 332                 if (get_irn_loop_depth(dca) < get_irn_loop_depth(best)) {
 333                         best = dca;
 334                 }
 335         }
 336         if (best != get_nodes_block(n)) {
 337                 /* debug output
 338                 printf("Moving out of loop: "); DDMN(n);
 339                 printf(" Outermost block: "); DDMN(early);
 340                 printf(" Best block: "); DDMN(best);
 341                 printf(" Innermost block: "); DDMN(get_nodes_block(n));
 342                 */
 343                 set_nodes_block(n, best);
 344         }
 345 }
 346
 347 /* deepest common ancestor in the dominator tree of all nodes'
 348    blocks depending on us; our final placement has to dominate DCA. */
 349 static ir_node *get_deepest_common_ancestor(ir_node *node, ir_node *dca)
 350 {
 351         int i;
 352
 353         for (i = get_irn_n_outs(node) - 1; i >= 0; --i) {
 354                 ir_node *succ = get_irn_out(node, i);
 355
 356                 if (is_End(succ)) {
 357                         /*
 358                          * This consumer is the End node, a keep alive edge.
 359                          * This is not a real consumer, so we ignore it
 360                          */
 361                         continue;
 362                 }
 363
 364                 if (is_Proj(succ)) {
 365                         dca = get_deepest_common_ancestor(succ, dca);
 366                 } else {
 367                         /* ignore if succ is in dead code */
 368                         ir_node *succ_blk = get_nodes_block(succ);
 369                         if (is_Block_unreachable(succ_blk))
 370                                 continue;
 371                         dca = consumer_dom_dca(dca, succ, node);
 372                 }
 373         }
 374
 375         return dca;
 376 }
 377
 378 static void set_projs_block(ir_node *node, ir_node *block)
 379 {
 380         int i;
 381
 382         for (i = get_irn_n_outs(node) - 1; i >= 0; --i) {
 383                 ir_node *succ = get_irn_out(node, i);
 384
 385                 assert(is_Proj(succ));
 386
 387                 if(get_irn_mode(succ) == mode_T) {
 388                         set_projs_block(succ, block);
 389                 }
 390                 set_nodes_block(succ, block);
 391         }
 392 }
 393
 394 /**
 395  * Find the latest legal block for N and place N into the
 396  * `optimal' Block between the latest and earliest legal block.
 397  * The `optimal' block is the dominance-deepest block of those
 398  * with the least loop-nesting-depth.  This places N out of as many
 399  * loops as possible and then makes it as control dependent as
 400  * possible.
 401  *
 402  * @param n         the node to be placed
 403  * @param worklist  a worklist, all successors of non-floating nodes are
 404  *                  placed here
 405  */
 406 static void place_floats_late(ir_node *n, pdeq *worklist) {
 407         int i, n_outs;
 408         ir_node *early_blk;
 409
 410         assert(irn_not_visited(n)); /* no multiple placement */
 411
 412         mark_irn_visited(n);
 413
 414         /* no need to place block nodes, control nodes are already placed. */
 415         if (!is_Block(n) &&
 416             (!is_cfop(n)) &&
 417             (get_irn_mode(n) != mode_X)) {
 418                 /* Remember the early_blk placement of this block to move it
 419                    out of loop no further than the early_blk placement. */
 420                 early_blk = get_nodes_block(n);
 421
 422                 /*
 423                  * BEWARE: Here we also get code, that is live, but
 424                  * was in a dead block.  If the node is life, but because
 425                  * of CSE in a dead block, we still might need it.
 426                  */
 427
 428                 /* Assure that our users are all placed, except the Phi-nodes.
 429                 --- Each data flow cycle contains at least one Phi-node.  We
 430                     have to break the `user has to be placed before the
 431                     producer' dependence cycle and the Phi-nodes are the
 432                     place to do so, because we need to base our placement on the
 433                     final region of our users, which is OK with Phi-nodes, as they
 434                     are op_pin_state_pinned, and they never have to be placed after a
 435                     producer of one of their inputs in the same block anyway. */
 436                 for (i = get_irn_n_outs(n) - 1; i >= 0; --i) {
 437                         ir_node *succ = get_irn_out(n, i);
 438                         if (irn_not_visited(succ) && !is_Phi(succ))
 439                                 place_floats_late(succ, worklist);
 440                 }
 441
 442                 if (! is_Block_dead(early_blk)) {
 443                         /* do only move things that where not dead */
 444                         ir_op *op = get_irn_op(n);
 445
 446                         /* We have to determine the final block of this node... except for
 447                            constants and Projs */
 448                         if ((get_irn_pinned(n) == op_pin_state_floats) &&
 449                             (op != op_Const)    &&
 450                             (op != op_SymConst) &&
 451                             (op != op_Proj))
 452                         {
 453                                 /* deepest common ancestor in the dominator tree of all nodes'
 454                                    blocks depending on us; our final placement has to dominate
 455                                    DCA. */
 456                                 ir_node *dca = get_deepest_common_ancestor(n, NULL);
 457                                 if (dca != NULL) {
 458                                         set_nodes_block(n, dca);
 459                                         move_out_of_loops(n, early_blk);
 460                                         if (get_irn_mode(n) == mode_T) {
 461                                                 set_projs_block(n, get_nodes_block(n));
 462                                         }
 463                                 }
 464                         }
 465                 }
 466         }
 467
 468         /* Add successors of all non-floating nodes on list. (Those of floating
 469            nodes are placed already and therefore are marked.)  */
 470         n_outs = get_irn_n_outs(n);
 471         for (i = 0; i < n_outs; i++) {
 472                 ir_node *succ = get_irn_out(n, i);
 473                 if (irn_not_visited(get_irn_out(n, i))) {
 474                         pdeq_putr(worklist, succ);
 475                 }
 476         }
 477 }
 478
 479 /**
 480  * Place floating nodes on the given worklist as late as possible using
 481  * the dominance tree.
 482  *
 483  * @param worklist   the worklist containing the nodes to place
 484  */
 485 static void place_late(waitq *worklist) {
 486         assert(worklist);
 487         inc_irg_visited(current_ir_graph);
 488
 489         /* This fills the worklist initially. */
 490         place_floats_late(get_irg_start_block(current_ir_graph), worklist);
 491
 492         /* And now empty the worklist again... */
 493         while (!waitq_empty(worklist)) {
 494                 ir_node *n = waitq_get(worklist);
 495                 if (irn_not_visited(n))
 496                         place_floats_late(n, worklist);
 497         }
 498 }
 499
 500 /* Code Placement. */
 501 void place_code(ir_graph *irg) {
 502         waitq *worklist;
 503         ir_graph *rem = current_ir_graph;
 504
 505         current_ir_graph = irg;
 506
 507         /* Handle graph state */
 508         assert(get_irg_phase_state(irg) != phase_building);
 509         assure_doms(irg);
 510
 511         if (1 || get_irg_loopinfo_state(irg) != loopinfo_consistent) {
 512                 free_loop_information(irg);
 513                 construct_cf_backedges(irg);
 514         }
 515
 516         /* Place all floating nodes as early as possible. This guarantees
 517          a legal code placement. */
 518         worklist = new_waitq();
 519         place_early(worklist);
 520
 521         /* place_early() invalidates the outs, place_late needs them. */
 522         compute_irg_outs(irg);
 523
 524         /* Now move the nodes down in the dominator tree. This reduces the
 525            unnecessary executions of the node. */
 526         place_late(worklist);
 527
 528         set_irg_outs_inconsistent(current_ir_graph);
 529         set_irg_loopinfo_inconsistent(current_ir_graph);
 530         del_waitq(worklist);
 531         current_ir_graph = rem;
 532 }