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