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* pred0;
 274                 cdep* cdep;
 275
 276                 pred0 = get_nodes_block(get_irn_n(block, i));
 277                 for (cdep = find_cdep(pred0); cdep != NULL; cdep = cdep->next) {
 278                         const ir_node* dependency = cdep->node;
 279                         ir_node* projx0 = walk_to_projx(pred0, 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                                 ir_node* pred1;
 299
 300                                 pred1 = get_nodes_block(get_irn_n(block, j));
 301
 302                                 if (!is_cdep_on(pred1, dependency)) continue;
 303
 304                                 projx1 = walk_to_projx(pred1, dependency);
 305
 306                                 if (projx1 == NULL) continue;
 307
 308                                 phi = get_block_blockinfo(block)->phi;
 309                                 if (!opt_info->allow_ifconv(get_Cond_selector(cond), phi, i, j)) continue;
 310
 311                                 DB((dbg, LEVEL_1, "Found Cond %+F with proj %+F and %+F\n",
 312                                         cond, projx0, projx1
 313                                 ));
 314
 315                                 prepare_path(block, i, dependency);
 316                                 prepare_path(block, j, dependency);
 317                                 arity = get_irn_arity(block);
 318
 319                                 conds[0] = get_Cond_selector(cond);
 320
 321                                 psi_block = get_nodes_block(cond);
 322                                 do {
 323                                         ir_node* val_i = get_irn_n(phi, i);
 324                                         ir_node* val_j = get_irn_n(phi, j);
 325
 326                                         if (val_i == val_j) {
 327                                                 psi = val_i;
 328                                                 DB((dbg, LEVEL_2,  "Generating no psi, because both values are equal\n"));
 329                                         } else {
 330                                                 /* Something is very fishy if two predecessors of a PhiM point into
 331                                                  * one block, but not at the same memory node
 332                                                  */
 333                                                 assert(get_irn_mode(phi) != mode_M);
 334                                                 if (get_Proj_proj(projx0) == pn_Cond_true) {
 335                                                         vals[0] = val_i;
 336                                                         vals[1] = val_j;
 337                                                 } else {
 338                                                         vals[0] = val_j;
 339                                                         vals[1] = val_i;
 340                                                 }
 341
 342                                                 psi = new_r_Psi(
 343                                                         current_ir_graph, psi_block, 1, conds, vals, get_irn_mode(phi)
 344                                                 );
 345                                                 DB((dbg, LEVEL_2, "Generating %+F for %+F\n", psi, phi));
 346                                         }
 347
 348                                         if (arity == 2) {
 349                                                 exchange(phi, psi);
 350                                         } else {
 351                                                 rewire(phi, i, j, psi);
 352                                         }
 353
 354                                         phi = get_irn_link(phi);
 355                                 } while (phi != NULL);
 356
 357                                 exchange(get_nodes_block(get_irn_n(block, i)), psi_block);
 358                                 exchange(get_nodes_block(get_irn_n(block, j)), psi_block);
 359
 360                                 if (arity == 2) {
 361 #if 1
 362                                         DB((dbg, LEVEL_1,  "Welding block %+F and %+F\n", block, psi_block));
 363                                         /* copy the block-info from the Psi-block to the block before merging */
 364                                         get_block_blockinfo(psi_block)->has_pinned |= get_block_blockinfo(block)->has_pinned;
 365                                         set_irn_link(block, get_irn_link(psi_block));
 366
 367                                         set_irn_in(block, get_irn_arity(psi_block), get_irn_in(psi_block) + 1);
 368                                         exchange_cdep(psi_block, block);
 369                                         exchange(psi_block, block);
 370 #else
 371                                         DB((dbg, LEVEL_1,  "Welding block %+F to %+F\n", block, psi_block));
 372                                         get_block_blockinfo(psi_block)->has_pinned |=   get_block_blockinfo(block)->has_pinned;
 373                                         exchange(block, psi_block);
 374 #endif
 375                                         return;
 376                                 } else {
 377                                         rewire(block, i, j, new_r_Jmp(current_ir_graph, psi_block));
 378                                         goto restart;
 379                                 }
 380                         }
 381                 }
 382         }
 383 }
 384
 385 /**
 386  * Block walker: add additional data
 387  */
 388 static void init_block_link(ir_node *block, void *env)
 389 {
 390         struct obstack *obst = env;
 391         block_info *bi = obstack_alloc(obst, sizeof(*bi));
 392
 393         bi->phi = NULL;
 394         bi->has_pinned = 0;
 395         set_irn_link(block, bi);
 396 }
 397
 398
 399 /**
 400  * Daisy-chain all phis in a block
 401  * If a non-movable node is encountered set the has_pinned flag
 402  */
 403 static void collect_phis(ir_node *node, void *env)
 404 {
 405         (void) env;
 406
 407         if (is_Phi(node)) {
 408                 ir_node *block = get_nodes_block(node);
 409                 block_info *bi = get_block_blockinfo(block);
 410
 411                 set_irn_link(node, bi->phi);
 412                 bi->phi = node;
 413         }
 414         else {
 415                 if (is_no_Block(node) && get_irn_pinned(node) == op_pin_state_pinned) {
 416                         /*
 417                          * Ignore control flow nodes, these will be removed.
 418                          * This ignores Raise. That is surely bad. FIXME.
 419                          */
 420                         if (! is_cfop(node)) {
 421                                 ir_node *block = get_nodes_block(node);
 422                                 block_info *bi = get_block_blockinfo(block);
 423
 424                                 DB((dbg, LEVEL_2, "Node %+F in block %+F is unmovable\n", node, block));
 425                                 bi->has_pinned = 1;
 426                         }
 427                 }
 428         }
 429 }
 430
 431
 432 /*
 433  * Transform multiple cascaded Psis into one Psi
 434  */
 435 static ir_node* fold_psi(ir_node* psi)
 436 {
 437         int arity = get_Psi_n_conds(psi);
 438         int new_arity = 0;
 439         int i;
 440         ir_node* n;
 441         ir_node** conds;
 442         ir_node** vals;
 443         int j;
 444         int k;
 445         int a;
 446         ir_node* new_psi;
 447
 448         for (i = 0; i < arity; ++i) {
 449                 n = get_Psi_val(psi, i);
 450                 if (get_irn_op(n) == op_Psi) {
 451                         new_arity += get_Psi_n_conds(n) + 1;
 452                 } else {
 453                         ++new_arity;
 454                 }
 455         }
 456         n = get_Psi_default(psi);
 457         if (get_irn_op(n) == op_Psi) {
 458                 new_arity += get_Psi_n_conds(n);
 459         }
 460
 461         if (arity == new_arity) return psi; // no attached Psis found
 462         DB((dbg, LEVEL_1, "Folding %+F from %d to %d conds\n", psi, arity, new_arity));
 463
 464         NEW_ARR_A(ir_node *, conds, new_arity);
 465         NEW_ARR_A(ir_node *, vals, new_arity + 1);
 466         j = 0;
 467         for (i = 0; i < arity; ++i) {
 468                 ir_node* c = get_Psi_cond(psi, i);
 469
 470                 n = get_Psi_val(psi, i);
 471                 if (get_irn_op(n) == op_Psi) {
 472                         a = get_Psi_n_conds(n);
 473                         for (k = 0; k < a; ++k) {
 474                                 conds[j] = new_r_And(
 475                                         current_ir_graph, get_nodes_block(psi),
 476                                         c, get_Psi_cond(n, k), mode_b
 477                                 );
 478                                 vals[j] = get_Psi_val(n, k);
 479                                 ++j;
 480                         }
 481                         conds[j] = c;
 482                         vals[j] = get_Psi_default(n);
 483                 } else {
 484                         conds[j] = c;
 485                         vals[j] = n;
 486                 }
 487                 ++j;
 488         }
 489         n = get_Psi_default(psi);
 490         if (get_irn_op(n) == op_Psi) {
 491                 a = get_Psi_n_conds(n);
 492                 for (k = 0; k < a; ++k) {
 493                         conds[j] = get_Psi_cond(n, k);
 494                         vals[j] = get_Psi_val(n, k);
 495                         ++j;
 496                 }
 497                 vals[j] = get_Psi_default(n);
 498         } else {
 499                 vals[j] = n;
 500         }
 501         assert(j == new_arity);
 502         new_psi = new_r_Psi(
 503                 current_ir_graph, get_nodes_block(psi),
 504                 new_arity, conds, vals, get_irn_mode(psi)
 505         );
 506         DB((dbg, LEVEL_1, "Folded %+F into new %+F\n", psi, new_psi));
 507         exchange(psi, new_psi);
 508         return new_psi;
 509 }
 510
 511
 512 /*
 513  * Merge consecutive psi inputs if the data inputs are the same
 514  */
 515 static ir_node* meld_psi(ir_node* psi)
 516 {
 517         int arity = get_Psi_n_conds(psi);
 518         int new_arity;
 519         ir_node** conds;
 520         ir_node** vals;
 521         ir_node* cond;
 522         ir_node* val;
 523         int i;
 524         int j;
 525         ir_node* new_psi;
 526
 527         new_arity = 1;
 528         val = get_Psi_val(psi, 0);
 529         DB((dbg, LEVEL_1, "Pred  0 of %+F is %+F\n", psi, val));
 530         for (i = 1; i < arity; ++i) {
 531                 ir_node* v = get_Psi_val(psi, i);
 532                 DB((dbg, LEVEL_1, "Pred %2d of %+F is %+F\n", i, psi, v));
 533                 if (val != v) {
 534                         val = v;
 535                         ++new_arity;
 536                 }
 537         }
 538         DB((dbg, LEVEL_1, "Default of %+F is %+F\n", psi, get_Psi_default(psi)));
 539         if (val == get_Psi_default(psi)) --new_arity;
 540
 541         DB((dbg, LEVEL_1, "Melding Psi %+F from %d conds to %d\n", psi, arity, new_arity));
 542
 543         if (new_arity == arity) return psi;
 544
 545         /* If all data inputs of the Psi are equal, exchange the Psi with that value */
 546         if (new_arity == 0) {
 547                 exchange(psi, val);
 548                 return val;
 549         }
 550
 551         NEW_ARR_A(ir_node *, conds, new_arity);
 552         NEW_ARR_A(ir_node *, vals, new_arity + 1);
 553         cond = get_Psi_cond(psi, 0);
 554         val = get_Psi_val(psi, 0);
 555         j = 0;
 556         for (i = 1; i < arity; ++i) {
 557                 ir_node* v = get_Psi_val(psi, i);
 558
 559                 if (v == val) {
 560                         cond = new_r_Or(
 561                                 current_ir_graph, get_nodes_block(psi),
 562                                 cond, get_Psi_cond(psi, i), mode_b
 563                         );
 564                 } else {
 565                         conds[j] = cond;
 566                         vals[j] = val;
 567                         ++j;
 568                         val = v;
 569                 }
 570         }
 571         if (val != get_Psi_default(psi)) {
 572                 conds[j] = cond;
 573                 vals[j] = val;
 574                 ++j;
 575         }
 576         vals[j] = get_Psi_default(psi);
 577         assert(j == new_arity);
 578         new_psi = new_r_Psi(
 579                 current_ir_graph, get_nodes_block(psi),
 580                 new_arity, conds, vals, get_irn_mode(psi)
 581         );
 582         DB((dbg, LEVEL_1, "Molded %+F into %+F\n", psi, new_psi));
 583         exchange(psi, new_psi);
 584         return new_psi;
 585 }
 586
 587
 588 /**
 589  * Split a Psi with multiple conditions into multiple Psis with one condtition
 590  * each
 591  */
 592 static ir_node* split_psi(ir_node* psi)
 593 {
 594         int arity = get_Psi_n_conds(psi);
 595         ir_mode* mode;
 596         ir_node* block;
 597         ir_node* rval;
 598         int i;
 599
 600         if (arity == 1) return psi;
 601
 602         mode  = get_irn_mode(psi);
 603         block = get_nodes_block(psi);
 604         rval  = get_Psi_default(psi);
 605         for (i = arity - 1; i >= 0; --i) {
 606                 ir_node* conds[1];
 607                 ir_node* vals[2];
 608
 609                 conds[0] = get_Psi_cond(psi, i);
 610                 vals[0]  = get_Psi_val(psi, i);
 611                 vals[1]  = rval;
 612                 rval     = new_r_Psi(
 613                         current_ir_graph, block, 1, conds, vals, mode
 614                 );
 615         }
 616         exchange(psi, rval);
 617         return rval;
 618 }
 619
 620
 621 static void optimise_psis(ir_node* node, void* env)
 622 {
 623         (void) env;
 624
 625         if (get_irn_op(node) != op_Psi) return;
 626 #if 1
 627         node = fold_psi(node);
 628 #endif
 629 #if 1
 630         node = meld_psi(node);
 631 #endif
 632 #if 1
 633         node = split_psi(node);
 634 #endif
 635 }
 636
 637
 638 void opt_if_conv(ir_graph *irg, const opt_if_conv_info_t *params)
 639 {
 640         struct obstack obst;
 641         opt_if_conv_info_t p;
 642
 643         if (! get_opt_if_conversion())
 644                 return;
 645
 646         /* get the parameters */
 647         p = (params != NULL ? *params : default_info);
 648
 649         FIRM_DBG_REGISTER(dbg, "firm.opt.ifconv");
 650
 651         DB((dbg, LEVEL_1, "Running if-conversion on %+F\n", irg));
 652
 653         normalize_one_return(irg);
 654         remove_critical_cf_edges(irg);
 655
 656         compute_cdep(irg);
 657         assure_doms(irg);
 658
 659         obstack_init(&obst);
 660         irg_block_walk_graph(irg, init_block_link, NULL, &obst);
 661         irg_walk_graph(irg, collect_phis, NULL, NULL);
 662         irg_block_walk_graph(irg, NULL, if_conv_walker, &p);
 663
 664         local_optimize_graph(irg);
 665
 666         irg_walk_graph(irg, NULL, optimise_psis, NULL);
 667
 668         obstack_free(&obst, NULL);
 669
 670         free_dom(irg);
 671         free_cdep(irg);
 672 }