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

   1 /*
   2  * Copyright (C) 1995-2007 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 #ifdef HAVE_CONFIG_H
  28 #include "config.h"
  29 #endif
  30
  31 #include <assert.h>
  32
  33 #include "iroptimize.h"
  34 #include "obst.h"
  35 #include "irnode_t.h"
  36 #include "cdep.h"
  37 #include "ircons.h"
  38 #include "irdom.h"
  39 #include "irgmod.h"
  40 #include "irgopt.h"
  41 #include "irgwalk.h"
  42 #include "irtools.h"
  43 #include "array.h"
  44 #include "xmalloc.h"
  45
  46 // debug
  47 #include "irdump.h"
  48 #include "debug.h"
  49
  50 DEBUG_ONLY(firm_dbg_module_t *dbg);
  51
  52 /** allow every Psi to be created. */
  53 static int default_allow_ifconv(ir_node *sel, ir_node* phi_list, int i, int j)
  54 {
  55         (void) sel;
  56         (void) phi_list;
  57         (void) i;
  58         (void) j;
  59         return 1;
  60 }
  61
  62 /**
  63  * Default options.
  64  */
  65 static const opt_if_conv_info_t default_info = {
  66         0,    /* doesn't matter for Psi */
  67         default_allow_ifconv
  68 };
  69
  70 /**
  71  * Additional block info.
  72  */
  73 typedef struct block_info {
  74         ir_node *phi;   /**< head of the Phi list */
  75         int has_pinned; /**< set if the block contains instructions that cannot be moved */
  76 } block_info;
  77
  78 #define get_block_blockinfo(block) ((block_info *)get_irn_link(block))
  79
  80 /**
  81  * Returns non-zero if a Block can be emptied.
  82  */
  83 static int can_empty_block(ir_node *block)
  84 {
  85         return !get_block_blockinfo(block)->has_pinned;
  86 }
  87
  88
  89 static ir_node* walk_to_projx(ir_node* start, const ir_node* dependency)
  90 {
  91         int arity;
  92         int i;
  93
  94         /* No need to find the conditional block if this block cannot be emptied and
  95          * therefore not moved
  96          */
  97         if (!can_empty_block(start)) return NULL;
  98
  99         arity = get_irn_arity(start);
 100         for (i = 0; i < arity; ++i) {
 101                 ir_node* pred = get_irn_n(start, i);
 102                 ir_node* pred_block = get_nodes_block(pred);
 103
 104                 if (pred_block == dependency) {
 105                         if (is_Proj(pred)) {
 106                                 assert(get_irn_mode(pred) == mode_X);
 107                                 return pred;
 108                         }
 109                         return NULL;
 110                 }
 111
 112                 if (is_Proj(pred)) {
 113                         assert(get_irn_mode(pred) == mode_X);
 114                         return NULL;
 115                 }
 116
 117                 if (is_cdep_on(pred_block, dependency)) {
 118                         return walk_to_projx(pred_block, dependency);
 119                 }
 120         }
 121         return NULL;
 122 }
 123
 124
 125 /**
 126  * Copies the DAG starting at node to the ith predecessor block of src_block
 127  * -if the node isn't in the src_block, this is a nop and the node is returned
 128  * -if the node is a phi in the src_block, the ith predecessor of the phi is
 129  *   returned
 130  * otherwise returns the copy of the passed node
 131  */
 132 static ir_node* copy_to(ir_node* node, ir_node* src_block, int i)
 133 {
 134         ir_node* dst_block;
 135         ir_node* copy;
 136         int arity;
 137         int j;
 138
 139         if (get_nodes_block(node) != src_block) return node;
 140         if (get_irn_op(node) == op_Phi) return get_irn_n(node, i);
 141
 142         copy = exact_copy(node);
 143         dst_block = get_nodes_block(get_irn_n(src_block, i));
 144         set_nodes_block(copy, dst_block);
 145
 146         DB((dbg, LEVEL_1, "Copying node %+F to block %+F, copy is %+F\n",
 147                 node, dst_block, copy));
 148
 149         arity = get_irn_arity(node);
 150         for (j = 0; j < arity; ++j) {
 151                 set_irn_n(copy, j, copy_to(get_irn_n(node, j), src_block, i));
 152                 DB((dbg, LEVEL_2, "-- pred %d is %+F\n", j, get_irn_n(copy, j)));
 153         }
 154         return copy;
 155 }
 156
 157
 158 /**
 159  * Remove predecessors i and j from node and add predecessor new_pred
 160  */
 161 static void rewire(ir_node* node, int i, int j, ir_node* new_pred)
 162 {
 163         int arity = get_irn_arity(node);
 164         ir_node **ins;
 165         int k;
 166         int l;
 167
 168         NEW_ARR_A(ir_node *, ins, arity - 1);
 169
 170         l = 0;
 171         for (k = 0; k < i; ++k) ins[l++] = get_irn_n(node, k);
 172         for (++k; k < j; ++k) ins[l++] = get_irn_n(node, k);
 173         for (++k; k < arity; ++k) ins[l++] = get_irn_n(node, k);
 174         ins[l++] = new_pred;
 175         assert(l == arity - 1);
 176         set_irn_in(node, l, ins);
 177 }
 178
 179
 180 /**
 181  * Remove the jth predecessors from the ith predecessor of block and add it to block
 182  */
 183 static void split_block(ir_node* block, int i, int j)
 184 {
 185         ir_node* pred_block = get_nodes_block(get_irn_n(block, i));
 186         int arity = get_irn_arity(block);
 187         int new_pred_arity;
 188         ir_node* phi;
 189         ir_node **ins;
 190         ir_node **pred_ins;
 191         int k;
 192
 193         DB((dbg, LEVEL_1, "Splitting predecessor %d of predecessor %d of %+F\n", j, i, block));
 194
 195         NEW_ARR_A(ir_node*, ins, arity + 1);
 196
 197         for (phi = get_block_blockinfo(block)->phi; phi != NULL; phi = get_irn_link(phi)) {
 198                 ir_node* copy = copy_to(get_irn_n(phi, i), pred_block, j);
 199
 200                 for (k = 0; k < i; ++k) ins[k] = get_irn_n(phi, k);
 201                 ins[k++] = copy;
 202                 for (; k < arity; ++k) ins[k] = get_irn_n(phi, k);
 203                 ins[k] = get_irn_n(phi, i);
 204                 assert(k == arity);
 205                 set_irn_in(phi, arity + 1, ins);
 206         }
 207
 208         for (k = 0; k < i; ++k) ins[k] = get_irn_n(block, k);
 209         ins[k++] = get_irn_n(pred_block, j);
 210         for (; k < arity; ++k) ins[k] = get_irn_n(block, k);
 211         ins[k] = get_irn_n(block, i);
 212         assert(k == arity);
 213         set_irn_in(block, arity + 1, ins);
 214
 215         new_pred_arity = get_irn_arity(pred_block) - 1;
 216         NEW_ARR_A(ir_node*, pred_ins, new_pred_arity);
 217
 218         for (phi = get_block_blockinfo(pred_block)->phi; phi != NULL; phi = get_irn_link(phi)) {
 219                 for (k = 0; k < j; ++k) pred_ins[k] = get_irn_n(phi, k);
 220                 for (; k < new_pred_arity; ++k) pred_ins[k] = get_irn_n(phi, k + 1);
 221                 assert(k == new_pred_arity);
 222                 if (new_pred_arity > 1) {
 223                         set_irn_in(phi, new_pred_arity, pred_ins);
 224                 } else {
 225                         exchange(phi, pred_ins[0]);
 226                 }
 227         }
 228
 229         for (k = 0; k < j; ++k) pred_ins[k] = get_irn_n(pred_block, k);
 230         for (; k < new_pred_arity; ++k) pred_ins[k] = get_irn_n(pred_block, k + 1);
 231         assert(k == new_pred_arity);
 232         if (new_pred_arity > 1) {
 233                 set_irn_in(pred_block, new_pred_arity, pred_ins);
 234         } else {
 235                 exchange(pred_block, get_nodes_block(pred_ins[0]));
 236         }
 237 }
 238
 239
 240 static void prepare_path(ir_node* block, int i, const ir_node* dependency)
 241 {
 242         ir_node* pred = get_nodes_block(get_irn_n(block, i));
 243         int pred_arity;
 244         int j;
 245
 246         DB((dbg, LEVEL_1, "Preparing predecessor %d of %+F\n", i, block));
 247
 248         pred_arity = get_irn_arity(pred);
 249         for (j = 0; j < pred_arity; ++j) {
 250                 ir_node* pred_pred = get_nodes_block(get_irn_n(pred, j));
 251
 252                 if (is_cdep_on(pred_pred, dependency)) {
 253                         prepare_path(pred, j, dependency);
 254                         split_block(block, i, j);
 255                         break;
 256                 }
 257         }
 258 }
 259
 260
 261 static void if_conv_walker(ir_node* block, void* env)
 262 {
 263         int arity;
 264         int i;
 265         opt_if_conv_info_t *opt_info = env;
 266
 267         /* Bail out, if there are no Phis at all */
 268         if (get_block_blockinfo(block)->phi == NULL) return;
 269
 270 restart:
 271         arity = get_irn_arity(block);
 272         for (i = 0; i < arity; ++i) {
 273                 ir_node* pred;
 274                 cdep* cdep;
 275
 276                 pred = get_nodes_block(get_irn_n(block, i));
 277                 for (cdep = find_cdep(pred); cdep != NULL; cdep = cdep->next) {
 278                         const ir_node* dependency = cdep->node;
 279                         ir_node* projx0 = walk_to_projx(pred, dependency);
 280                         ir_node* cond;
 281                         int j;
 282
 283                         if (projx0 == NULL) continue;
 284
 285                         cond = get_Proj_pred(projx0);
 286                         if (get_irn_op(cond) != op_Cond) continue;
 287
 288                         /* We only handle boolean decisions, no switches */
 289                         if (get_irn_mode(get_Cond_selector(cond)) != mode_b) continue;
 290
 291                         for (j = i + 1; j < arity; ++j) {
 292                                 ir_node* projx1;
 293                                 ir_node* conds[1];
 294                                 ir_node* vals[2];
 295                                 ir_node* psi = NULL;
 296                                 ir_node* psi_block;
 297                                 ir_node* phi;
 298
 299                                 pred = get_nodes_block(get_irn_n(block, j));
 300
 301                                 if (!is_cdep_on(pred, dependency)) continue;
 302
 303                                 projx1 = walk_to_projx(pred, dependency);
 304
 305                                 if (projx1 == NULL) continue;
 306
 307                                 phi = get_block_blockinfo(block)->phi;
 308                                 if (!opt_info->allow_ifconv(get_Cond_selector(cond), phi, i, j)) continue;
 309
 310                                 DB((dbg, LEVEL_1, "Found Cond %+F with proj %+F and %+F\n",
 311                                         cond, projx0, projx1
 312                                 ));
 313
 314                                 prepare_path(block, i, dependency);
 315                                 prepare_path(block, j, dependency);
 316                                 arity = get_irn_arity(block);
 317
 318                                 conds[0] = get_Cond_selector(cond);
 319
 320                                 psi_block = get_nodes_block(cond);
 321                                 do {
 322                                         ir_node* val_i = get_irn_n(phi, i);
 323                                         ir_node* val_j = get_irn_n(phi, j);
 324
 325                                         if (val_i == val_j) {
 326                                                 psi = val_i;
 327                                                 DB((dbg, LEVEL_2,  "Generating no psi, because both values are equal\n"));
 328                                         } else {
 329                                                 /* Something is very fishy if two predecessors of a PhiM point into
 330                                                  * one block, but not at the same memory node
 331                                                  */
 332                                                 assert(get_irn_mode(phi) != mode_M);
 333                                                 if (get_Proj_proj(projx0) == pn_Cond_true) {
 334                                                         vals[0] = val_i;
 335                                                         vals[1] = val_j;
 336                                                 } else {
 337                                                         vals[0] = val_j;
 338                                                         vals[1] = val_i;
 339                                                 }
 340
 341                                                 psi = new_r_Psi(
 342                                                         current_ir_graph, psi_block, 1, conds, vals, get_irn_mode(phi)
 343                                                 );
 344                                                 DB((dbg, LEVEL_2, "Generating %+F for %+F\n", psi, phi));
 345                                         }
 346
 347                                         if (arity == 2) {
 348                                                 exchange(phi, psi);
 349                                         } else {
 350                                                 rewire(phi, i, j, psi);
 351                                         }
 352
 353                                         phi = get_irn_link(phi);
 354                                 } while (phi != NULL);
 355
 356                                 exchange(get_nodes_block(get_irn_n(block, i)), psi_block);
 357                                 exchange(get_nodes_block(get_irn_n(block, j)), psi_block);
 358
 359                                 if (arity == 2) {
 360 #if 1
 361                                         DB((dbg, LEVEL_1,  "Welding block %+F and %+F\n", block, psi_block));
 362                                         /* copy the block-info from the Psi-block to the block before merging */
 363                                         get_block_blockinfo(psi_block)->has_pinned |= get_block_blockinfo(block)->has_pinned;
 364                                         set_irn_link(block, get_irn_link(psi_block));
 365
 366                                         set_irn_in(block, get_irn_arity(psi_block), get_irn_in(psi_block) + 1);
 367                                         exchange_cdep(psi_block, block);
 368                                         exchange(psi_block, block);
 369 #else
 370                                         DB((dbg, LEVEL_1,  "Welding block %+F to %+F\n", block, psi_block));
 371                                         get_block_blockinfo(psi_block)->has_pinned |=   get_block_blockinfo(block)->has_pinned;
 372                                         exchange(block, psi_block);
 373 #endif
 374                                         return;
 375                                 } else {
 376                                         rewire(block, i, j, new_r_Jmp(current_ir_graph, psi_block));
 377                                         goto restart;
 378                                 }
 379                         }
 380                 }
 381         }
 382 }
 383
 384 /**
 385  * Block walker: add additional data
 386  */
 387 static void init_block_link(ir_node *block, void *env)
 388 {
 389         struct obstack *obst = env;
 390         block_info *bi = obstack_alloc(obst, sizeof(*bi));
 391
 392         bi->phi = NULL;
 393         bi->has_pinned = 0;
 394         set_irn_link(block, bi);
 395 }
 396
 397
 398 /**
 399  * Daisy-chain all phis in a block
 400  * If a non-movable node is encountered set the has_pinned flag
 401  */
 402 static void collect_phis(ir_node *node, void *env)
 403 {
 404         (void) env;
 405
 406         if (is_Phi(node)) {
 407                 ir_node *block = get_nodes_block(node);
 408                 block_info *bi = get_block_blockinfo(block);
 409
 410                 set_irn_link(node, bi->phi);
 411                 bi->phi = node;
 412         }
 413         else {
 414                 if (is_no_Block(node) && get_irn_pinned(node) == op_pin_state_pinned) {
 415                         /*
 416                          * Ignore control flow nodes, these will be removed.
 417                          * This ignores Raise. That is surely bad. FIXME.
 418                          */
 419                         if (! is_cfop(node)) {
 420                                 ir_node *block = get_nodes_block(node);
 421                                 block_info *bi = get_block_blockinfo(block);
 422
 423                                 DB((dbg, LEVEL_2, "Node %+F in block %+F is unmovable\n", node, block));
 424                                 bi->has_pinned = 1;
 425                         }
 426                 }
 427         }
 428 }
 429
 430
 431 /*
 432  * Transform multiple cascaded Psis into one Psi
 433  */
 434 static ir_node* fold_psi(ir_node* psi)
 435 {
 436         int arity = get_Psi_n_conds(psi);
 437         int new_arity = 0;
 438         int i;
 439         ir_node* n;
 440         ir_node** conds;
 441         ir_node** vals;
 442         int j;
 443         int k;
 444         int a;
 445         ir_node* new_psi;
 446
 447         for (i = 0; i < arity; ++i) {
 448                 n = get_Psi_val(psi, i);
 449                 if (get_irn_op(n) == op_Psi) {
 450                         new_arity += get_Psi_n_conds(n) + 1;
 451                 } else {
 452                         ++new_arity;
 453                 }
 454         }
 455         n = get_Psi_default(psi);
 456         if (get_irn_op(n) == op_Psi) {
 457                 new_arity += get_Psi_n_conds(n);
 458         }
 459
 460         if (arity == new_arity) return psi; // no attached Psis found
 461         DB((dbg, LEVEL_1, "Folding %+F from %d to %d conds\n", psi, arity, new_arity));
 462
 463         NEW_ARR_A(ir_node *, conds, new_arity);
 464         NEW_ARR_A(ir_node *, vals, new_arity + 1);
 465         j = 0;
 466         for (i = 0; i < arity; ++i) {
 467                 ir_node* c = get_Psi_cond(psi, i);
 468
 469                 n = get_Psi_val(psi, i);
 470                 if (get_irn_op(n) == op_Psi) {
 471                         a = get_Psi_n_conds(n);
 472                         for (k = 0; k < a; ++k) {
 473                                 conds[j] = new_r_And(
 474                                         current_ir_graph, get_nodes_block(psi),
 475                                         c, get_Psi_cond(n, k), mode_b
 476                                 );
 477                                 vals[j] = get_Psi_val(n, k);
 478                                 ++j;
 479                         }
 480                         conds[j] = c;
 481                         vals[j] = get_Psi_default(n);
 482                 } else {
 483                         conds[j] = c;
 484                         vals[j] = n;
 485                 }
 486                 ++j;
 487         }
 488         n = get_Psi_default(psi);
 489         if (get_irn_op(n) == op_Psi) {
 490                 a = get_Psi_n_conds(n);
 491                 for (k = 0; k < a; ++k) {
 492                         conds[j] = get_Psi_cond(n, k);
 493                         vals[j] = get_Psi_val(n, k);
 494                         ++j;
 495                 }
 496                 vals[j] = get_Psi_default(n);
 497         } else {
 498                 vals[j] = n;
 499         }
 500         assert(j == new_arity);
 501         new_psi = new_r_Psi(
 502                 current_ir_graph, get_nodes_block(psi),
 503                 new_arity, conds, vals, get_irn_mode(psi)
 504         );
 505         DB((dbg, LEVEL_1, "Folded %+F into new %+F\n", psi, new_psi));
 506         exchange(psi, new_psi);
 507         return new_psi;
 508 }
 509
 510
 511 /*
 512  * Merge consecutive psi inputs if the data inputs are the same
 513  */
 514 static ir_node* meld_psi(ir_node* psi)
 515 {
 516         int arity = get_Psi_n_conds(psi);
 517         int new_arity;
 518         ir_node** conds;
 519         ir_node** vals;
 520         ir_node* cond;
 521         ir_node* val;
 522         int i;
 523         int j;
 524         ir_node* new_psi;
 525
 526         new_arity = 1;
 527         val = get_Psi_val(psi, 0);
 528         DB((dbg, LEVEL_1, "Pred  0 of %+F is %+F\n", psi, val));
 529         for (i = 1; i < arity; ++i) {
 530                 ir_node* v = get_Psi_val(psi, i);
 531                 DB((dbg, LEVEL_1, "Pred %2d of %+F is %+F\n", i, psi, v));
 532                 if (val != v) {
 533                         val = v;
 534                         ++new_arity;
 535                 }
 536         }
 537         DB((dbg, LEVEL_1, "Default of %+F is %+F\n", psi, get_Psi_default(psi)));
 538         if (val == get_Psi_default(psi)) --new_arity;
 539
 540         DB((dbg, LEVEL_1, "Melding Psi %+F from %d conds to %d\n", psi, arity, new_arity));
 541
 542         if (new_arity == arity) return psi;
 543
 544         /* If all data inputs of the Psi are equal, exchange the Psi with that value */
 545         if (new_arity == 0) {
 546                 exchange(psi, val);
 547                 return val;
 548         }
 549
 550         NEW_ARR_A(ir_node *, conds, new_arity);
 551         NEW_ARR_A(ir_node *, vals, new_arity + 1);
 552         cond = get_Psi_cond(psi, 0);
 553         val = get_Psi_val(psi, 0);
 554         j = 0;
 555         for (i = 1; i < arity; ++i) {
 556                 ir_node* v = get_Psi_val(psi, i);
 557
 558                 if (v == val) {
 559                         cond = new_r_Or(
 560                                 current_ir_graph, get_nodes_block(psi),
 561                                 cond, get_Psi_cond(psi, i), mode_b
 562                         );
 563                 } else {
 564                         conds[j] = cond;
 565                         vals[j] = val;
 566                         ++j;
 567                         val = v;
 568                 }
 569         }
 570         if (val != get_Psi_default(psi)) {
 571                 conds[j] = cond;
 572                 vals[j] = val;
 573                 ++j;
 574         }
 575         vals[j] = get_Psi_default(psi);
 576         assert(j == new_arity);
 577         new_psi = new_r_Psi(
 578                 current_ir_graph, get_nodes_block(psi),
 579                 new_arity, conds, vals, get_irn_mode(psi)
 580         );
 581         DB((dbg, LEVEL_1, "Molded %+F into %+F\n", psi, new_psi));
 582         exchange(psi, new_psi);
 583         return new_psi;
 584 }
 585
 586
 587 /**
 588  * Split a Psi with multiple conditions into multiple Psis with one condtition
 589  * each
 590  */
 591 static ir_node* split_psi(ir_node* psi)
 592 {
 593         int arity = get_Psi_n_conds(psi);
 594         ir_mode* mode;
 595         ir_node* block;
 596         ir_node* rval;
 597         int i;
 598
 599         if (arity == 1) return psi;
 600
 601         mode = get_irn_mode(psi);
 602         block = get_nodes_block(psi);
 603         rval = get_Psi_default(psi);
 604         for (i = arity - 1; i >= 0; --i) {
 605                 ir_node* conds[1];
 606                 ir_node* vals[2];
 607
 608                 conds[0] = get_Psi_cond(psi, i);
 609                 vals[0] = get_Psi_val(psi, i);
 610                 vals[1] = rval;
 611                 rval = new_r_Psi(
 612                         current_ir_graph, block, 1, conds, vals, mode
 613                 );
 614         }
 615         exchange(psi, rval);
 616         return rval;
 617 }
 618
 619
 620 static void optimise_psis(ir_node* node, void* env)
 621 {
 622         (void) env;
 623
 624         if (get_irn_op(node) != op_Psi) return;
 625 #if 1
 626         node = fold_psi(node);
 627 #endif
 628 #if 1
 629         node = meld_psi(node);
 630 #endif
 631 #if 1
 632         node = split_psi(node);
 633 #endif
 634 }
 635
 636
 637 void opt_if_conv(ir_graph *irg, const opt_if_conv_info_t *params)
 638 {
 639         struct obstack obst;
 640         opt_if_conv_info_t p;
 641
 642         if (! get_opt_if_conversion())
 643                 return;
 644
 645         /* get the parameters */
 646         p = (params != NULL ? *params : default_info);
 647
 648         FIRM_DBG_REGISTER(dbg, "firm.opt.ifconv");
 649
 650         DB((dbg, LEVEL_1, "Running if-conversion on %+F\n", irg));
 651
 652         normalize_one_return(irg);
 653         remove_critical_cf_edges(irg);
 654
 655         compute_cdep(irg);
 656         assure_doms(irg);
 657
 658         obstack_init(&obst);
 659         irg_block_walk_graph(irg, init_block_link, NULL, &obst);
 660         irg_walk_graph(irg, collect_phis, NULL, NULL);
 661         irg_block_walk_graph(irg, NULL, if_conv_walker, &p);
 662
 663         local_optimize_graph(irg);
 664
 665         irg_walk_graph(irg, NULL, optimise_psis, NULL);
 666
 667         obstack_free(&obst, NULL);
 668
 669         free_dom(irg);
 670         free_cdep(irg);
 671 }