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