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

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