nsz Git - libfirm/blob - ir/opt/ifconv.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    ir/opt/ifconv.c
  22  * @brief   If conversion
  23  * @author  Christoph Mallon
  24  * @version $Id$
  25  */
  26
  27 #include "config.h"
  28
  29 #include <assert.h>
  30 #include "iroptimize.h"
  31 #include "obst.h"
  32 #include "irnode_t.h"
  33 #include "cdep.h"
  34 #include "ircons.h"
  35 #include "irgmod.h"
  36 #include "irgopt.h"
  37 #include "irgwalk.h"
  38 #include "irtools.h"
  39 #include "array_t.h"
  40 #include "irpass_t.h"
  41
  42 // debug
  43 #include "irdump.h"
  44 #include "debug.h"
  45
  46 /**
  47  * Environment for if-conversion.
  48  */
  49 typedef struct walker_env {
  50         const ir_settings_if_conv_t *params; /**< Conversion parameter. */
  51         int                         changed; /**< Set if the graph was changed. */
  52 } walker_env;
  53
  54 DEBUG_ONLY(static firm_dbg_module_t *dbg);
  55
  56 /**
  57  * Default callback for Mux creation: allows every Mux to be created.
  58  */
  59 static int default_allow_ifconv(ir_node *sel, ir_node* phi_list, int i, int j)
  60 {
  61         (void) sel;
  62         (void) phi_list;
  63         (void) i;
  64         (void) j;
  65         return 1;
  66 }
  67
  68 /**
  69  * Default options.
  70  */
  71 static const ir_settings_if_conv_t default_info = {
  72         0,    /* doesn't matter for Mux */
  73         default_allow_ifconv
  74 };
  75
  76 /**
  77  * Returns non-zero if a Block can be emptied.
  78  *
  79  * @param block  the block
  80  */
  81 static int can_empty_block(ir_node *block) {
  82         return get_Block_mark(block) == 0;
  83 }
  84
  85 /**
  86  * Find the ProjX node leading from block dependency to block start.
  87  *
  88  * @param start       a block that is control depended on dependency
  89  * @param dependency  the block that decides whether start is executed
  90  *
  91  * @return a ProjX node that represent the decision control flow or
  92  *         NULL is start is not dependent at all or a block on the way
  93  *         cannot be emptied
  94  */
  95 static ir_node* walk_to_projx(ir_node* start, const ir_node* dependency)
  96 {
  97         int arity;
  98         int i;
  99
 100         /* No need to find the conditional block if this block cannot be emptied and
 101          * therefore not moved */
 102         if (!can_empty_block(start)) return NULL;
 103
 104         arity = get_irn_arity(start);
 105         for (i = 0; i < arity; ++i) {
 106                 ir_node* pred = get_irn_n(start, i);
 107                 ir_node* pred_block = get_nodes_block(skip_Proj(pred));
 108
 109                 if (pred_block == dependency) {
 110                         if (is_Proj(pred)) {
 111                                 assert(get_irn_mode(pred) == mode_X);
 112                                 /* we found it */
 113                                 return pred;
 114                         }
 115                         /* Not a Proj? Should not happen. */
 116                         return NULL;
 117                 }
 118
 119                 if (is_Proj(pred)) {
 120                         assert(get_irn_mode(pred) == mode_X);
 121                         /* another Proj but not from the control block */
 122                         return NULL;
 123                 }
 124
 125                 if (is_cdep_on(pred_block, dependency)) {
 126                         return walk_to_projx(pred_block, dependency);
 127                 }
 128         }
 129         return NULL;
 130 }
 131
 132
 133 /**
 134  * Recursively copies the DAG starting at node to the i-th predecessor
 135  * block of src_block
 136  * - if node isn't in the src_block, recursion ends and node is returned
 137  * - if node is a Phi in the src_block, the i-th predecessor of this Phi is
 138  *   returned and recursion ends
 139  * otherwise returns a copy of the passed node created in the i-th predecessor of
 140  * src_block.
 141  *
 142  * @param node       a root of a DAG
 143  * @param src_block  the block of the DAG
 144  * @param i          the position of the predecessor the DAG
 145  *                   is moved to
 146  *
 147  * @return  the root of the copied DAG
 148  */
 149 static ir_node* copy_to(ir_node* node, ir_node* src_block, int i)
 150 {
 151         ir_node* dst_block;
 152         ir_node* copy;
 153         int j;
 154
 155         if (get_nodes_block(node) != src_block) {
 156                 /* already outside src_block, do not copy */
 157                 return node;
 158         }
 159         if (is_Phi(node)) {
 160                 /* move through the Phi to the i-th predecessor */
 161                 return get_irn_n(node, i);
 162         }
 163
 164         /* else really need a copy */
 165         copy = exact_copy(node);
 166         dst_block = get_nodes_block(get_irn_n(src_block, i));
 167         set_nodes_block(copy, dst_block);
 168
 169         DB((dbg, LEVEL_1, "Copying node %+F to block %+F, copy is %+F\n",
 170                 node, dst_block, copy));
 171
 172         /* move recursively all predecessors */
 173         for (j = get_irn_arity(node) - 1; j >= 0; --j) {
 174                 set_irn_n(copy, j, copy_to(get_irn_n(node, j), src_block, i));
 175                 DB((dbg, LEVEL_2, "-- pred %d is %+F\n", j, get_irn_n(copy, j)));
 176         }
 177         return copy;
 178 }
 179
 180
 181 /**
 182  * Remove predecessors i and j (i < j) from a node and
 183  * add an additional predecessor new_pred.
 184  *
 185  * @param node      the node whose inputs are changed
 186  * @param i         the first index to remove
 187  * @param j         the second index to remove
 188  * @param new_pred  a node that is added as a new input to node
 189  */
 190 static void rewire(ir_node* node, int i, int j, ir_node* new_pred)
 191 {
 192         int arity = get_irn_arity(node);
 193         ir_node **ins;
 194         int k;
 195         int l;
 196
 197         NEW_ARR_A(ir_node *, ins, arity - 1);
 198
 199         l = 0;
 200         for (k = 0; k < i;     ++k) ins[l++] = get_irn_n(node, k);
 201         for (++k;   k < j;     ++k) ins[l++] = get_irn_n(node, k);
 202         for (++k;   k < arity; ++k) ins[l++] = get_irn_n(node, k);
 203         ins[l++] = new_pred;
 204         assert(l == arity - 1);
 205         set_irn_in(node, l, ins);
 206 }
 207
 208
 209 /**
 210  * Remove the j-th predecessors from the i-th predecessor of block and add it to block
 211  */
 212 static void split_block(ir_node* block, int i, int j)
 213 {
 214         ir_node* pred_block = get_nodes_block(get_irn_n(block, i));
 215         int arity = get_irn_arity(block);
 216         int new_pred_arity;
 217         ir_node *phi, *next;
 218         ir_node **ins;
 219         ir_node **pred_ins;
 220         int k;
 221
 222         DB((dbg, LEVEL_1, "Splitting predecessor %d of predecessor %d of %+F\n", j, i, block));
 223
 224         NEW_ARR_A(ir_node*, ins, arity + 1);
 225
 226         for (phi = get_Block_phis(block); phi != NULL; phi = get_Phi_next(phi)) {
 227                 ir_node* copy = copy_to(get_irn_n(phi, i), pred_block, j);
 228
 229                 for (k = 0; k < i; ++k) ins[k] = get_irn_n(phi, k);
 230                 ins[k++] = copy;
 231                 for (; k < arity; ++k) ins[k] = get_irn_n(phi, k);
 232                 ins[k] = get_irn_n(phi, i);
 233                 assert(k == arity);
 234                 set_irn_in(phi, arity + 1, ins);
 235         }
 236
 237         for (k = 0; k < i; ++k) ins[k] = get_irn_n(block, k);
 238         ins[k++] = get_irn_n(pred_block, j);
 239         for (; k < arity; ++k) ins[k] = get_irn_n(block, k);
 240         ins[k] = get_irn_n(block, i);
 241         assert(k == arity);
 242         set_irn_in(block, arity + 1, ins);
 243
 244         new_pred_arity = get_irn_arity(pred_block) - 1;
 245         NEW_ARR_A(ir_node*, pred_ins, new_pred_arity);
 246
 247         for (phi = get_Block_phis(pred_block); phi != NULL; phi = next) {
 248                 for (k = 0; k < j; ++k) pred_ins[k] = get_irn_n(phi, k);
 249                 for (; k < new_pred_arity; ++k) pred_ins[k] = get_irn_n(phi, k + 1);
 250                 assert(k == new_pred_arity);
 251                 next = get_Phi_next(phi);
 252                 if (new_pred_arity > 1) {
 253                         set_irn_in(phi, new_pred_arity, pred_ins);
 254                 } else {
 255                         exchange(phi, pred_ins[0]);
 256                 }
 257         }
 258
 259         for (k = 0; k < j; ++k) pred_ins[k] = get_irn_n(pred_block, k);
 260         for (; k < new_pred_arity; ++k) pred_ins[k] = get_irn_n(pred_block, k + 1);
 261         assert(k == new_pred_arity);
 262         if (new_pred_arity > 1) {
 263                 set_irn_in(pred_block, new_pred_arity, pred_ins);
 264         } else {
 265                 exchange(pred_block, get_nodes_block(pred_ins[0]));
 266         }
 267 }
 268
 269
 270 static void prepare_path(ir_node* block, int i, const ir_node* dependency)
 271 {
 272         ir_node* pred = get_nodes_block(get_irn_n(block, i));
 273         int pred_arity;
 274         int j;
 275
 276         DB((dbg, LEVEL_1, "Preparing predecessor %d of %+F\n", i, block));
 277
 278         pred_arity = get_irn_arity(pred);
 279         for (j = 0; j < pred_arity; ++j) {
 280                 ir_node* pred_pred = get_nodes_block(get_irn_n(pred, j));
 281
 282                 if (is_cdep_on(pred_pred, dependency)) {
 283                         prepare_path(pred, j, dependency);
 284                         split_block(block, i, j);
 285                         break;
 286                 }
 287         }
 288 }
 289
 290 /**
 291  * Block walker: Search for diamonds and do the if conversion.
 292  */
 293 static void if_conv_walker(ir_node *block, void *ctx)
 294 {
 295         walker_env *env = ctx;
 296         int arity;
 297         int i;
 298
 299         /* Bail out, if there are no Phis at all */
 300         if (get_Block_phis(block) == NULL) return;
 301
 302 restart:
 303         arity = get_irn_arity(block);
 304         for (i = 0; i < arity; ++i) {
 305                 ir_node* pred0;
 306                 ir_cdep* cdep;
 307
 308                 pred0 = get_Block_cfgpred_block(block, i);
 309                 for (cdep = find_cdep(pred0); cdep != NULL; cdep = cdep->next) {
 310                         const ir_node* dependency = cdep->node;
 311                         ir_node* projx0 = walk_to_projx(pred0, dependency);
 312                         ir_node* cond;
 313                         int j;
 314
 315                         if (projx0 == NULL) continue;
 316
 317                         cond = get_Proj_pred(projx0);
 318                         if (! is_Cond(cond))
 319                                 continue;
 320
 321                         /* We only handle boolean decisions, no switches */
 322                         if (get_irn_mode(get_Cond_selector(cond)) != mode_b) continue;
 323
 324                         for (j = i + 1; j < arity; ++j) {
 325                                 ir_node* projx1;
 326                                 ir_node* sel;
 327                                 ir_node* mux_block;
 328                                 ir_node* phi;
 329                                 ir_node* pred1;
 330                                 dbg_info* cond_dbg;
 331
 332                                 pred1 = get_Block_cfgpred_block(block, j);
 333
 334                                 if (!is_cdep_on(pred1, dependency)) continue;
 335
 336                                 projx1 = walk_to_projx(pred1, dependency);
 337
 338                                 if (projx1 == NULL) continue;
 339
 340                                 phi = get_Block_phis(block);
 341                                 if (!env->params->allow_ifconv(get_Cond_selector(cond), phi, i, j))
 342                                         continue;
 343
 344                                 DB((dbg, LEVEL_1, "Found Cond %+F with proj %+F and %+F\n",
 345                                         cond, projx0, projx1
 346                                 ));
 347
 348                                 env->changed = 1;
 349                                 prepare_path(block, i, dependency);
 350                                 prepare_path(block, j, dependency);
 351                                 arity = get_irn_arity(block);
 352
 353                                 sel = get_Cond_selector(cond);
 354
 355                                 mux_block = get_nodes_block(cond);
 356                                 cond_dbg = get_irn_dbg_info(cond);
 357                                 do {
 358                                         ir_node* val_i = get_irn_n(phi, i);
 359                                         ir_node* val_j = get_irn_n(phi, j);
 360                                         ir_node* mux;
 361                                         ir_node* next_phi;
 362
 363                                         if (val_i == val_j) {
 364                                                 mux = val_i;
 365                                                 DB((dbg, LEVEL_2,  "Generating no Mux, because both values are equal\n"));
 366                                         } else {
 367                                                 ir_node *t, *f;
 368
 369                                                 /* Something is very fishy if two predecessors of a PhiM point into
 370                                                  * one block, but not at the same memory node
 371                                                  */
 372                                                 assert(get_irn_mode(phi) != mode_M);
 373                                                 if (get_Proj_proj(projx0) == pn_Cond_true) {
 374                                                         t = val_i;
 375                                                         f = val_j;
 376                                                 } else {
 377                                                         t = val_j;
 378                                                         f = val_i;
 379                                                 }
 380
 381                                                 mux = new_rd_Mux(cond_dbg, mux_block, sel, f, t, get_irn_mode(phi));
 382                                                 DB((dbg, LEVEL_2, "Generating %+F for %+F\n", mux, phi));
 383                                         }
 384
 385                                         next_phi = get_Phi_next(phi);
 386
 387                                         if (arity == 2) {
 388                                                 exchange(phi, mux);
 389                                         } else {
 390                                                 rewire(phi, i, j, mux);
 391                                         }
 392                                         phi = next_phi;
 393                                 } while (phi != NULL);
 394
 395                                 exchange(get_nodes_block(get_irn_n(block, i)), mux_block);
 396                                 exchange(get_nodes_block(get_irn_n(block, j)), mux_block);
 397
 398                                 if (arity == 2) {
 399                                         unsigned mark;
 400 #if 1
 401                                         DB((dbg, LEVEL_1,  "Welding block %+F and %+F\n", block, mux_block));
 402                                         /* copy the block-info from the Mux-block to the block before merging */
 403
 404                                         mark =  get_Block_mark(mux_block) | get_Block_mark(block);
 405                                         set_Block_mark(block, mark);
 406                                         set_Block_phis(block, get_Block_phis(mux_block));
 407
 408                                         set_irn_in(block, get_irn_arity(mux_block), get_irn_in(mux_block) + 1);
 409                                         exchange_cdep(mux_block, block);
 410                                         exchange(mux_block, block);
 411 #else
 412                                         DB((dbg, LEVEL_1,  "Welding block %+F to %+F\n", block, mux_block));
 413                                         mark =  get_Block_mark(mux_block) | get_Block_mark(block);
 414                                         /* mark both block just to be sure, should be enough to mark mux_block */
 415                                         set_Block_mark(mux_block, mark);
 416                                         exchange(block, mux_block);
 417 #endif
 418                                         return;
 419                                 } else {
 420                                         rewire(block, i, j, new_r_Jmp(mux_block));
 421                                         goto restart;
 422                                 }
 423                         }
 424                 }
 425         }
 426 }
 427
 428 /**
 429  * Block walker: clear block marks and Phi lists.
 430  */
 431 static void init_block_link(ir_node *block, void *env)
 432 {
 433         (void)env;
 434         set_Block_mark(block, 0);
 435         set_Block_phis(block, NULL);
 436 }
 437
 438
 439 /**
 440  * Daisy-chain all Phis in a block.
 441  * If a non-movable node is encountered set the has_pinned flag in its block.
 442  */
 443 static void collect_phis(ir_node *node, void *env) {
 444         (void) env;
 445
 446         if (is_Phi(node)) {
 447                 ir_node *block = get_nodes_block(node);
 448
 449                 add_Block_phi(block, node);
 450         } else {
 451                 if (is_no_Block(node) && get_irn_pinned(node) == op_pin_state_pinned) {
 452                         /*
 453                          * Ignore control flow nodes (except Raise), these will be removed.
 454                          */
 455                         if (!is_cfop(node) && !is_Raise(node)) {
 456                                 ir_node *block = get_nodes_block(node);
 457
 458                                 DB((dbg, LEVEL_2, "Node %+F in block %+F is unmovable\n", node, block));
 459                                 set_Block_mark(block, 1);
 460                         }
 461                 }
 462         }
 463 }
 464
 465 void opt_if_conv(ir_graph *irg, const ir_settings_if_conv_t *params)
 466 {
 467         walker_env env;
 468
 469         /* get the parameters */
 470         env.params  = (params != NULL ? params : &default_info);
 471         env.changed = 0;
 472
 473         FIRM_DBG_REGISTER(dbg, "firm.opt.ifconv");
 474
 475         DB((dbg, LEVEL_1, "Running if-conversion on %+F\n", irg));
 476
 477         normalize_one_return(irg);
 478         remove_critical_cf_edges(irg);
 479
 480         compute_cdep(irg);
 481
 482         ir_reserve_resources(irg, IR_RESOURCE_BLOCK_MARK | IR_RESOURCE_PHI_LIST);
 483
 484         irg_block_walk_graph(irg, init_block_link, NULL, NULL);
 485         irg_walk_graph(irg, collect_phis, NULL, NULL);
 486         irg_block_walk_graph(irg, NULL, if_conv_walker, &env);
 487
 488         ir_free_resources(irg, IR_RESOURCE_BLOCK_MARK | IR_RESOURCE_PHI_LIST);
 489
 490         if (env.changed) {
 491                 local_optimize_graph(irg);
 492
 493                 /* graph has changed, invalidate analysis info */
 494                 set_irg_outs_inconsistent(irg);
 495                 set_irg_extblk_inconsistent(irg);
 496                 set_irg_loopinfo_inconsistent(irg);
 497                 set_irg_doms_inconsistent(irg);
 498         }
 499
 500         free_cdep(irg);
 501 }
 502
 503 struct pass_t {
 504         ir_graph_pass_t             pass;
 505         const ir_settings_if_conv_t *params;
 506 };
 507
 508 /**
 509  * Wrapper for running opt_if_conv() as an ir_graph pass.
 510  */
 511 static int pass_wrapper(ir_graph *irg, void *context) {
 512         struct pass_t *pass = context;
 513         opt_if_conv(irg, pass->params);
 514         return 0;
 515 }  /* pass_wrapper */
 516
 517 ir_graph_pass_t *opt_if_conv_pass(
 518         const char *name, int verify, int dump, const ir_settings_if_conv_t *params)
 519 {
 520         struct pass_t *pass = xmalloc(sizeof(*pass));
 521
 522         pass->pass.kind       = k_ir_prog_pass;
 523         pass->pass.run_on_irg = pass_wrapper;
 524         pass->pass.context    = pass;
 525         pass->pass.name       = name;
 526         pass->pass.verify     = verify != 0;
 527         pass->pass.dump       = dump != 0;
 528
 529         pass->params = params;
 530
 531         INIT_LIST_HEAD(&pass->pass.list);
 532
 533         return &pass->pass;
 534 }