nsz Git - libfirm/blob - ir/opt/reassoc.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
  22  * @brief   Reassociation
  23  * @author  Michael Beck
  24  * @version $Id$
  25  */
  26 #include "config.h"
  27
  28 #include "iropt_t.h"
  29 #include "irnode_t.h"
  30 #include "irgraph_t.h"
  31 #include "irmode_t.h"
  32 #include "ircons_t.h"
  33 #include "irgmod.h"
  34 #include "iropt_dbg.h"
  35 #include "irflag_t.h"
  36 #include "irgwalk.h"
  37 #include "irouts.h"
  38 #include "reassoc_t.h"
  39 #include "irhooks.h"
  40 #include "irloop.h"
  41 #include "pdeq.h"
  42 #include "debug.h"
  43
  44 //#define NEW_REASSOC
  45
  46 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
  47
  48 typedef struct _walker_t {
  49         int   changes;        /**< set, if a reassociation take place */
  50         waitq *wq;            /**< a wait queue */
  51 } walker_t;
  52
  53 typedef enum {
  54         NO_CONSTANT   = 0,    /**< node is not constant */
  55         REAL_CONSTANT = 1,    /**< node is a Const that is suitable for constant folding */
  56         REGION_CONST  = 4     /**< node is a constant expression in the current context,
  57                                    use 4 here to simplify implementation of get_comm_Binop_ops() */
  58 } const_class_t;
  59
  60 /**
  61  * returns whether a node is constant ie is a constant or
  62  * is loop invariant (called region constant)
  63  *
  64  * @param n     the node to be checked for constant
  65  * @param block a block that might be in a loop
  66  */
  67 static const_class_t get_const_class(const ir_node *n, const ir_node *block)
  68 {
  69         if (is_Const(n))
  70                 return REAL_CONSTANT;
  71
  72         /* constant nodes which can't be folded are region constants */
  73         if (is_irn_constlike(n))
  74                 return REGION_CONST;
  75
  76         /*
  77          * Beware: Bad nodes are always loop-invariant, but
  78          * cannot handled in later code, so filter them here.
  79          */
  80         if (! is_Bad(n) && is_loop_invariant(n, block))
  81                 return REGION_CONST;
  82
  83         return NO_CONSTANT;
  84 }  /* get_const_class */
  85
  86 /**
  87  * returns the operands of a commutative bin-op, if one operand is
  88  * a region constant, it is returned as the second one.
  89  *
  90  * Beware: Real constants must be returned with higher priority than
  91  * region constants, because they might be folded.
  92  */
  93 static void get_comm_Binop_ops(ir_node *binop, ir_node **a, ir_node **c)
  94 {
  95         ir_node *op_a = get_binop_left(binop);
  96         ir_node *op_b = get_binop_right(binop);
  97         ir_node *block = get_nodes_block(binop);
  98         int class_a = get_const_class(op_a, block);
  99         int class_b = get_const_class(op_b, block);
 100
 101         assert(is_op_commutative(get_irn_op(binop)));
 102
 103         switch (class_a + 2*class_b) {
 104         case REAL_CONSTANT + 2*REAL_CONSTANT:
 105                 /* if both are constants, one might be a
 106                  * pointer constant like NULL, return the other
 107                  */
 108                 if (mode_is_reference(get_irn_mode(op_a))) {
 109                         *a = op_a;
 110                         *c = op_b;
 111                 } else {
 112                         *a = op_b;
 113                         *c = op_a;
 114                 }
 115                 break;
 116         case REAL_CONSTANT + 2*NO_CONSTANT:
 117         case REAL_CONSTANT + 2*REGION_CONST:
 118         case REGION_CONST  + 2*NO_CONSTANT:
 119                 *a = op_b;
 120                 *c = op_a;
 121                 break;
 122         default:
 123                 *a = op_a;
 124                 *c = op_b;
 125                 break;
 126         }
 127 }  /* get_comm_Binop_ops */
 128
 129 /**
 130  * reassociate a Sub: x - c = x + (-c)
 131  */
 132 static int reassoc_Sub(ir_node **in)
 133 {
 134         ir_node *n = *in;
 135         ir_node *right = get_Sub_right(n);
 136         ir_mode *rmode = get_irn_mode(right);
 137         ir_node *block;
 138
 139         /* cannot handle SubIs(P, P) */
 140         if (mode_is_reference(rmode))
 141                 return 0;
 142
 143         block = get_nodes_block(n);
 144
 145         /* handles rule R6:
 146          * convert x - c => x + (-c)
 147          */
 148         if (get_const_class(right, block) == REAL_CONSTANT) {
 149                 ir_node *left  = get_Sub_left(n);
 150                 ir_mode *mode;
 151                 dbg_info *dbi;
 152                 ir_node *irn;
 153
 154                 switch (get_const_class(left, block)) {
 155                 case REAL_CONSTANT:
 156                         irn = optimize_in_place(n);
 157                         if (irn != n) {
 158                                 exchange(n, irn);
 159                                 *in = irn;
 160                                 return 1;
 161                         }
 162                         return 0;
 163                 case NO_CONSTANT:
 164                         break;
 165                 default:
 166                         /* already constant, nothing to do */
 167                         return 0;
 168                 }
 169
 170                 mode = get_irn_mode(n);
 171                 dbi  = get_irn_dbg_info(n);
 172
 173                 /* Beware of SubP(P, Is) */
 174                 irn = new_rd_Minus(dbi, current_ir_graph, block, right, rmode);
 175                 irn = new_rd_Add(dbi, current_ir_graph, block, left, irn, mode);
 176
 177                 DBG((dbg, LEVEL_5, "Applied: %n - %n => %n + (-%n)\n",
 178                         get_Sub_left(n), right, get_Sub_left(n), right));
 179
 180                 if (n == irn)
 181                         return 0;
 182
 183                 exchange(n, irn);
 184                 *in = irn;
 185
 186                 return 1;
 187         }
 188         return 0;
 189 }  /* reassoc_Sub */
 190
 191 /** Retrieve a mode from the operands. We need this, because
 192  * Add and Sub are allowed to operate on (P, Is)
 193  */
 194 static ir_mode *get_mode_from_ops(ir_node *op1, ir_node *op2)
 195 {
 196         ir_mode *m1, *m2;
 197
 198         m1 = get_irn_mode(op1);
 199         if (mode_is_reference(m1))
 200                 return m1;
 201
 202         m2 = get_irn_mode(op2);
 203         if (mode_is_reference(m2))
 204                 return m2;
 205
 206         assert(m1 == m2);
 207
 208         return m1;
 209 }  /* get_mode_from_ops */
 210
 211 #ifndef NEW_REASSOC
 212
 213 /**
 214  * reassociate a commutative Binop
 215  *
 216  * BEWARE: this rule leads to a potential loop, if
 217  * two operands are region constants and the third is a
 218  * constant, so avoid this situation.
 219  */
 220 static int reassoc_commutative(ir_node **node)
 221 {
 222         ir_node *n     = *node;
 223         ir_op *op      = get_irn_op(n);
 224         ir_node *block = get_nodes_block(n);
 225         ir_node *t1, *c1;
 226
 227         get_comm_Binop_ops(n, &t1, &c1);
 228
 229         if (get_irn_op(t1) == op) {
 230                 ir_node *t2, *c2;
 231                 const_class_t c_c1, c_c2, c_t2;
 232
 233                 get_comm_Binop_ops(t1, &t2, &c2);
 234
 235                 /* do not optimize Bad nodes, will fail later */
 236                 if (is_Bad(t2))
 237                         return 0;
 238
 239                 c_c1 = get_const_class(c1, block);
 240                 c_c2 = get_const_class(c2, block);
 241                 c_t2 = get_const_class(t2, block);
 242
 243                 if ( ((c_c1 > NO_CONSTANT) & (c_t2 > NO_CONSTANT)) &&
 244                      ((((c_c1 ^ c_c2 ^ c_t2) & REGION_CONST) == 0) || ((c_c1 & c_c2 & c_t2) == REGION_CONST)) ) {
 245                         /* All three are constant and either all are constant expressions
 246                          * or two of them are:
 247                          * then applying this rule would lead into a cycle
 248                          *
 249                          * Note that if t2 is a constant so is c2 hence we save one test.
 250                          */
 251                         return 0;
 252                 }
 253
 254                 if ((c_c1 != NO_CONSTANT) /* & (c_c2 != NO_CONSTANT) */) {
 255                         /* handles rules R7, R8, R9, R10:
 256                          * convert c1 .OP. (c2 .OP. x) => x .OP. (c1 .OP. c2)
 257                          */
 258                         ir_node *irn, *in[2];
 259                         ir_mode *mode, *mode_c1 = get_irn_mode(c1), *mode_c2 = get_irn_mode(c2);
 260
 261                         /* It might happen, that c1 and c2 have different modes, for
 262                          * instance Is and Iu.
 263                          * Handle this here.
 264                          */
 265                         if (mode_c1 != mode_c2) {
 266                                 if (mode_is_int(mode_c1) && mode_is_int(mode_c2)) {
 267                                         /* get the bigger one */
 268                                         if (get_mode_size_bits(mode_c1) > get_mode_size_bits(mode_c2))
 269                                                 c2 = new_r_Conv(current_ir_graph, block, c2, mode_c1);
 270                                         else if (get_mode_size_bits(mode_c1) < get_mode_size_bits(mode_c2))
 271                                                 c1 = new_r_Conv(current_ir_graph, block, c1, mode_c2);
 272                                         else {
 273                                                 /* Try to cast the real const */
 274                                                 if (c_c1 == REAL_CONSTANT)
 275                                                         c1 = new_r_Conv(current_ir_graph, block, c1, mode_c2);
 276                                                 else
 277                                                         c2 = new_r_Conv(current_ir_graph, block, c2, mode_c1);
 278                                         }
 279                                 }
 280                         }
 281
 282                         in[0] = c1;
 283                         in[1] = c2;
 284
 285                         mode  = get_mode_from_ops(in[0], in[1]);
 286                         in[1] = optimize_node(new_ir_node(NULL, current_ir_graph, block, op, mode, 2, in));
 287                         in[0] = t2;
 288
 289                         mode = get_mode_from_ops(in[0], in[1]);
 290                         irn   = optimize_node(new_ir_node(NULL, current_ir_graph, block, op, mode, 2, in));
 291
 292                         DBG((dbg, LEVEL_5, "Applied: %n .%s. (%n .%s. %n) => %n .%s. (%n .%s. %n)\n",
 293                              c1, get_irn_opname(n), c2, get_irn_opname(n), t2,
 294                              t2, get_irn_opname(n), c1, get_irn_opname(n), c2));
 295                         /*
 296                          * In some rare cases it can really happen that we get the same
 297                          * node back. This might be happen in dead loops, were the Phi
 298                          * nodes are already gone away. So check this.
 299                          */
 300                         if (n != irn) {
 301                                 exchange(n, irn);
 302                                 *node = irn;
 303                                 return 1;
 304                         }
 305                 }
 306         }
 307         return 0;
 308 }  /* reassoc_commutative */
 309
 310 #else
 311
 312 static ir_op          *commutative_op;
 313 static ir_node        *commutative_block;
 314 static struct obstack  commutative_args;
 315
 316 static void collect_args(ir_node *node)
 317 {
 318         ir_node *left  = get_binop_left(node);
 319         ir_node *right = get_binop_right(node);
 320
 321         if (get_irn_op(left) == commutative_op
 322                         && (!get_irn_outs_computed(left) || get_irn_n_outs(left) == 1)) {
 323                 collect_args(left);
 324         } else {
 325                 obstack_ptr_grow(&commutative_args, left);
 326         }
 327
 328         if (get_irn_op(right) == commutative_op
 329                         && (!get_irn_outs_computed(right) || get_irn_n_outs(right) == 1)) {
 330                 collect_args(right);
 331         } else {
 332                 obstack_ptr_grow(&commutative_args, right);
 333         }
 334
 335 #ifndef NDEBUG
 336         {
 337                 ir_mode *mode = get_irn_mode(node);
 338                 if (is_Add(node) && mode_is_reference(mode)) {
 339                         assert(get_irn_mode(left) == mode || get_irn_mode(right) == mode);
 340                 } else {
 341                         assert(get_irn_mode(left) == mode);
 342                         assert(get_irn_mode(right) == mode);
 343                 }
 344         }
 345 #endif
 346 }
 347
 348 static int compare_nodes(const ir_node *node1, const ir_node *node2)
 349 {
 350         const_class_t class1 = get_const_class(node1, commutative_block);
 351         const_class_t class2 = get_const_class(node2, commutative_block);
 352
 353         if (class1 == class2)
 354                 return 0;
 355         // return get_irn_idx(node1) - get_irn_idx(node2);
 356
 357         if (class1 < class2)
 358                 return -1;
 359
 360         assert(class1 > class2);
 361         return 1;
 362 }
 363
 364 static int compare_node_ptr(const void *e1, const void *e2)
 365 {
 366         const ir_node *node1  = *((const ir_node *const*) e1);
 367         const ir_node *node2  = *((const ir_node *const*) e2);
 368         return compare_nodes(node1, node2);
 369 }
 370
 371 static int reassoc_commutative(ir_node **n)
 372 {
 373         int       i;
 374         int       n_args;
 375         ir_node  *last;
 376         ir_node **args;
 377         ir_mode  *mode;
 378         ir_node  *node = *n;
 379
 380         commutative_op    = get_irn_op(node);
 381         commutative_block = get_nodes_block(node);
 382
 383         /* collect all nodes with same op type */
 384         collect_args(node);
 385
 386         n_args = obstack_object_size(&commutative_args) / sizeof(ir_node*);
 387         args   = obstack_finish(&commutative_args);
 388
 389         /* shortcut: in most cases there's nothing to do */
 390         if (n_args == 2 && compare_nodes(args[0], args[1]) <= 0) {
 391                 obstack_free(&commutative_args, args);
 392                 return 0;
 393         }
 394
 395         /* sort the arguments */
 396         qsort(args, n_args, sizeof(ir_node*), compare_node_ptr);
 397
 398         /* build new tree */
 399         last = args[n_args-1];
 400         mode = get_irn_mode(last);
 401         for (i = n_args-2; i >= 0; --i) {
 402                 ir_mode *mode_right;
 403                 ir_node *new_node;
 404                 ir_node *in[2];
 405
 406                 in[0] = last;
 407                 in[1] = args[i];
 408
 409                 /* AddP violates the assumption that all modes in args are equal...
 410                  * we need some hacks to cope with this */
 411                 mode_right = get_irn_mode(in[1]);
 412                 if (mode_is_reference(mode_right)) {
 413                         assert(is_Add(node) && mode_is_reference(get_irn_mode(node)));
 414                         mode = get_irn_mode(in[1]);
 415                 }
 416                 if (mode_right != mode) {
 417                         assert(is_Add(node) && mode_is_reference(get_irn_mode(node)));
 418                         in[1] = new_r_Conv(current_ir_graph, commutative_block,in[1], mode);
 419                 }
 420
 421                 /* TODO: produce useful debug info! */
 422                 new_node = new_ir_node(NULL, current_ir_graph, commutative_block,
 423                                        commutative_op, mode, 2, in);
 424                 new_node = optimize_node(new_node);
 425                 last     = new_node;
 426         }
 427
 428         /* CSE often returns the old node again, only exchange if needed */
 429         if (last != node) {
 430                 exchange(node, last);
 431                 *n = last;
 432                 return 1;
 433         }
 434         return 0;
 435 }
 436
 437 #endif
 438
 439 #define reassoc_Add  reassoc_commutative
 440 #define reassoc_And  reassoc_commutative
 441 #define reassoc_Or   reassoc_commutative
 442 #define reassoc_Eor  reassoc_commutative
 443
 444 /**
 445  * Reassociate using commutative law for Mul and distributive law for Mul and Add/Sub:
 446  */
 447 static int reassoc_Mul(ir_node **node)
 448 {
 449         ir_node *n = *node;
 450         ir_node *add_sub, *c;
 451         ir_op *op;
 452
 453         if (reassoc_commutative(&n))
 454                 return 1;
 455
 456         get_comm_Binop_ops(n, &add_sub, &c);
 457         op = get_irn_op(add_sub);
 458
 459         /* handles rules R11, R12, R13, R14, R15, R16, R17, R18, R19, R20 */
 460         if (op == op_Add || op == op_Sub) {
 461                 ir_mode *mode = get_irn_mode(n);
 462                 ir_node *irn, *block, *t1, *t2, *in[2];
 463
 464                 block = get_nodes_block(n);
 465                 t1 = get_binop_left(add_sub);
 466                 t2 = get_binop_right(add_sub);
 467
 468                 /* we can only multiplication rules on integer arithmetic */
 469                 if (mode_is_int(get_irn_mode(t1)) && mode_is_int(get_irn_mode(t2))) {
 470                         in[0] = new_rd_Mul(NULL, current_ir_graph, block, c, t1, mode);
 471                         in[1] = new_rd_Mul(NULL, current_ir_graph, block, c, t2, mode);
 472
 473                         irn   = optimize_node(new_ir_node(NULL, current_ir_graph, block, op, mode, 2, in));
 474
 475                         /* In some cases it might happen that the new irn is equal the old one, for
 476                          * instance in:
 477                          * (x - 1) * y == x * y - y
 478                          * will be transformed back by simpler optimization
 479                          * We could switch simple optimizations off, but this only happens iff y
 480                          * is a loop-invariant expression and that it is not clear if the new form
 481                          * is better.
 482                          * So, we let the old one.
 483                          */
 484                         if (irn != n) {
 485                                 DBG((dbg, LEVEL_5, "Applied: (%n .%s. %n) %n %n => (%n %n %n) .%s. (%n %n %n)\n",
 486                                         t1, get_op_name(op), t2, n, c, t1, n, c, get_op_name(op), t2, n, c));
 487                                 exchange(n, irn);
 488                                 *node = irn;
 489
 490                                 return 1;
 491                         }
 492                 }
 493         }
 494         return 0;
 495 }  /* reassoc_Mul */
 496
 497 /**
 498  * Reassociate Shl. We transform Shl(x, const) into Mul's if possible.
 499  */
 500 static int reassoc_Shl(ir_node **node) {
 501         ir_node *n = *node;
 502         ir_node *c = get_Shl_right(n);
 503         ir_node *x, *blk, *irn;
 504         ir_mode *mode;
 505         tarval *tv;
 506
 507         if (! is_Const(c))
 508                 return 0;
 509
 510         x = get_Shl_left(n);
 511         mode = get_irn_mode(x);
 512
 513         tv = get_mode_one(mode);
 514         tv = tarval_shl(tv, get_Const_tarval(c));
 515
 516         if (tv == tarval_bad)
 517                 return 0;
 518
 519         blk = get_nodes_block(n);
 520         c   = new_r_Const(current_ir_graph, blk, mode, tv);
 521         irn = new_rd_Mul(get_irn_dbg_info(n), current_ir_graph, blk, x, c, mode);
 522
 523         if (irn != n) {
 524                 exchange(n, irn);
 525                 *node = irn;
 526                 return 1;
 527         }
 528         return 0;
 529 }  /* reassoc_Shl */
 530
 531 /**
 532  * The walker for the reassociation.
 533  */
 534 static void wq_walker(ir_node *n, void *env)
 535 {
 536         walker_t *wenv = env;
 537
 538         set_irn_link(n, NULL);
 539         if (is_no_Block(n)) {
 540                 ir_node *blk = get_nodes_block(n);
 541
 542                 if (is_Block_dead(blk) || get_Block_dom_depth(blk) < 0) {
 543                         /* We are in a dead block, do not optimize or we may fall into an endless
 544                            loop. We check this here instead of requiring that all dead blocks are removed
 545                            which or cf_opt do not guarantee yet. */
 546                         return;
 547                 }
 548                 waitq_put(wenv->wq, n);
 549                 set_irn_link(n, wenv->wq);
 550         }
 551 }  /* wq_walker */
 552
 553 /**
 554  * The walker for the reassociation.
 555  */
 556 static void do_reassociation(walker_t *wenv)
 557 {
 558         int i, res, changed;
 559         ir_node *n, *blk;
 560
 561         while (! waitq_empty(wenv->wq)) {
 562                 n = waitq_get(wenv->wq);
 563                 set_irn_link(n, NULL);
 564
 565                 blk = get_nodes_block(n);
 566                 if (is_Block_dead(blk) || get_Block_dom_depth(blk) < 0) {
 567                         /* We are in a dead block, do not optimize or we may fall into an endless
 568                            loop. We check this here instead of requiring that all dead blocks are removed
 569                            which or cf_opt do not guarantee yet. */
 570                         continue;
 571                 }
 572
 573
 574                 hook_reassociate(1);
 575
 576                 /* reassociation must run until a fixpoint is reached. */
 577                 changed = 0;
 578                 do {
 579                         ir_op   *op    = get_irn_op(n);
 580                         ir_mode *mode  = get_irn_mode(n);
 581
 582                         res = 0;
 583
 584                         /* for FP these optimizations are only allowed if fp_strict_algebraic is disabled */
 585                         if (mode_is_float(mode) && get_irg_fp_model(current_ir_graph) & fp_strict_algebraic)
 586                                 break;
 587
 588                         if (op->ops.reassociate) {
 589                                 res = op->ops.reassociate(&n);
 590
 591                                 changed |= res;
 592                         }
 593                 } while (res == 1);
 594                 hook_reassociate(0);
 595
 596                 wenv->changes |= changed;
 597
 598                 if (changed) {
 599                         for (i = get_irn_arity(n) - 1; i >= 0; --i) {
 600                                 ir_node *pred = get_irn_n(n, i);
 601
 602                                 if (get_irn_link(pred) != wenv->wq) {
 603                                         waitq_put(wenv->wq, pred);
 604                                         set_irn_link(pred, wenv->wq);
 605                                 }
 606                         }
 607                 }
 608         }
 609 }  /* do_reassociation */
 610
 611 /**
 612  * Returns the earliest were a,b are available.
 613  * Note that we know that a, b both dominate
 614  * the block of the previous operation, so one must dominate the other.
 615  *
 616  * If the earliest block is the start block, return curr_blk instead
 617  */
 618 static ir_node *earliest_block(ir_node *a, ir_node *b, ir_node *curr_blk) {
 619         ir_node *blk_a = get_nodes_block(a);
 620         ir_node *blk_b = get_nodes_block(b);
 621         ir_node *res;
 622
 623         /* if blk_a != blk_b, one must dominate the other */
 624         if (block_dominates(blk_a, blk_b))
 625                 res = blk_b;
 626         else
 627                 res = blk_a;
 628         if (res == get_irg_start_block(current_ir_graph))
 629                 return curr_blk;
 630         return res;
 631 }  /* earliest_block */
 632
 633 /**
 634  * Checks whether a node is a Constant expression.
 635  * The following trees are constant expressions:
 636  *
 637  * Const, SymConst, Const + SymConst
 638  *
 639  * Handling SymConsts as const might be not a good idea for all
 640  * architectures ...
 641  */
 642 static int is_constant_expr(ir_node *irn) {
 643         ir_op *op;
 644
 645         switch (get_irn_opcode(irn)) {
 646         case iro_Const:
 647         case iro_SymConst:
 648                 return 1;
 649         case iro_Add:
 650                 op = get_irn_op(get_Add_left(irn));
 651                 if (op != op_Const && op != op_SymConst)
 652                         return 0;
 653                 op = get_irn_op(get_Add_right(irn));
 654                 if (op != op_Const && op != op_SymConst)
 655                         return 0;
 656                 return 1;
 657         default:
 658                 return 0;
 659         }
 660 }  /* is_constant_expr */
 661
 662 /**
 663  * Apply distributive Law for Mul and Add/Sub
 664  */
 665 static int reverse_rule_distributive(ir_node **node) {
 666         ir_node *n = *node;
 667         ir_node *left  = get_binop_left(n);
 668         ir_node *right = get_binop_right(n);
 669         ir_node *x, *blk, *curr_blk;
 670         ir_node *a, *b, *irn;
 671         ir_op *op;
 672         ir_mode *mode;
 673         dbg_info *dbg;
 674
 675         op = get_irn_op(left);
 676         if (op != get_irn_op(right))
 677                 return 0;
 678
 679         if (op == op_Shl) {
 680                 x = get_Shl_right(left);
 681
 682                 if (x == get_Shl_right(right)) {
 683                         /* (a << x) +/- (b << x) ==> (a +/- b) << x */
 684                         a = get_Shl_left(left);
 685                         b = get_Shl_left(right);
 686                         goto transform;
 687                 }
 688         } else if (op == op_Mul) {
 689                 x = get_Mul_left(left);
 690
 691                 if (x == get_Mul_left(right)) {
 692                         /* (x * a) +/- (x * b) ==> (a +/- b) * x */
 693                         a = get_Mul_right(left);
 694                         b = get_Mul_right(right);
 695                         goto transform;
 696                 } else if (x == get_Mul_right(right)) {
 697                         /* (x * a) +/- (b * x) ==> (a +/- b) * x */
 698                         a = get_Mul_right(left);
 699                         b = get_Mul_left(right);
 700                         goto transform;
 701                 }
 702
 703                 x = get_Mul_right(left);
 704
 705                 if (x == get_Mul_right(right)) {
 706                         /* (a * x) +/- (b * x) ==> (a +/- b) * x */
 707                         a = get_Mul_left(left);
 708                         b = get_Mul_left(right);
 709                         goto transform;
 710                 } else if (x == get_Mul_left(right)) {
 711                         /* (a * x) +/- (x * b) ==> (a +/- b) * x */
 712                         a = get_Mul_left(left);
 713                         b = get_Mul_right(right);
 714                         goto transform;
 715                 }
 716         }
 717         return 0;
 718
 719 transform:
 720         curr_blk = get_nodes_block(n);
 721
 722         blk = earliest_block(a, b, curr_blk);
 723
 724         dbg  = get_irn_dbg_info(n);
 725         mode = get_irn_mode(n);
 726
 727         if (is_Add(n))
 728                 irn = new_rd_Add(dbg, current_ir_graph, blk, a, b, mode);
 729         else
 730                 irn = new_rd_Sub(dbg, current_ir_graph, blk, a, b, mode);
 731
 732         blk  = earliest_block(irn, x, curr_blk);
 733
 734         if (op == op_Mul)
 735                 irn = new_rd_Mul(dbg, current_ir_graph, blk, irn, x, mode);
 736         else
 737                 irn = new_rd_Shl(dbg, current_ir_graph, blk, irn, x, mode);
 738
 739         exchange(n, irn);
 740         *node = irn;
 741         return 1;
 742 }  /* reverse_rule_distributive */
 743
 744 /**
 745  * Move Constants towards the root.
 746  */
 747 static int move_consts_up(ir_node **node) {
 748         ir_node *n = *node;
 749         ir_op *op;
 750         ir_node *l, *r, *a, *b, *c, *blk, *irn, *in[2];
 751         ir_mode *mode, *ma, *mb;
 752         dbg_info *dbg;
 753
 754         l = get_binop_left(n);
 755         r = get_binop_right(n);
 756
 757         /* check if one is already a constant expression */
 758         if (is_constant_expr(l) || is_constant_expr(r))
 759                 return 0;
 760
 761         dbg = get_irn_dbg_info(n);
 762         op = get_irn_op(n);
 763         if (get_irn_op(l) == op) {
 764                 /* (a .op. b) .op. r */
 765                 a = get_binop_left(l);
 766                 b = get_binop_right(l);
 767
 768                 if (is_constant_expr(a)) {
 769                         /* (C .op. b) .op. r ==> (r .op. b) .op. C */
 770                         c = a;
 771                         a = r;
 772                         blk = get_nodes_block(l);
 773                         dbg = dbg == get_irn_dbg_info(l) ? dbg : NULL;
 774                         goto transform;
 775                 } else if (is_constant_expr(b)) {
 776                         /* (a .op. C) .op. r ==> (a .op. r) .op. C */
 777                         c = b;
 778                         b = r;
 779                         blk = get_nodes_block(l);
 780                         dbg = dbg == get_irn_dbg_info(l) ? dbg : NULL;
 781                         goto transform;
 782                 }
 783         } else if (get_irn_op(r) == op) {
 784                 /* l .op. (a .op. b) */
 785                 a = get_binop_left(r);
 786                 b = get_binop_right(r);
 787
 788                 if (is_constant_expr(a)) {
 789                         /* l .op. (C .op. b) ==> (l .op. b) .op. C */
 790                         c = a;
 791                         a = l;
 792                         blk = get_nodes_block(r);
 793                         dbg = dbg == get_irn_dbg_info(r) ? dbg : NULL;
 794                         goto transform;
 795                 } else if (is_constant_expr(b)) {
 796                         /* l .op. (a .op. C) ==> (a .op. l) .op. C */
 797                         c = b;
 798                         b = l;
 799                         blk = get_nodes_block(r);
 800                         dbg = dbg == get_irn_dbg_info(r) ? dbg : NULL;
 801                         goto transform;
 802                 }
 803         }
 804         return 0;
 805
 806 transform:
 807         /* In some cases a and b might be both of different integer mode, and c a SymConst.
 808          * in that case we could either
 809          * 1.) cast into unsigned mode
 810          * 2.) ignore
 811          * we implement the second here
 812          */
 813         ma = get_irn_mode(a);
 814         mb = get_irn_mode(b);
 815         if (ma != mb && mode_is_int(ma) && mode_is_int(mb))
 816                 return 0;
 817
 818         /* check if (a .op. b) can be calculated in the same block is the old instruction */
 819         if (! block_dominates(get_nodes_block(a), blk))
 820                 return 0;
 821         if (! block_dominates(get_nodes_block(b), blk))
 822                 return 0;
 823         /* ok */
 824         in[0] = a;
 825         in[1] = b;
 826
 827         mode = get_mode_from_ops(a, b);
 828         in[0] = irn = optimize_node(new_ir_node(dbg, current_ir_graph, blk, op, mode, 2, in));
 829
 830         /* beware: optimize_node might have changed the opcode, check again */
 831         if (is_Add(irn) || is_Sub(irn)) {
 832                 reverse_rule_distributive(&in[0]);
 833         }
 834         in[1] = c;
 835
 836         mode = get_mode_from_ops(in[0], in[1]);
 837         irn = optimize_node(new_ir_node(dbg, current_ir_graph, blk, op, mode, 2, in));
 838
 839         exchange(n, irn);
 840         *node = irn;
 841         return 1;
 842 }  /* move_consts_up */
 843
 844 /**
 845  * Apply the rules in reverse order, removing code that was not collapsed
 846  */
 847 static void reverse_rules(ir_node *node, void *env) {
 848         walker_t *wenv = env;
 849         ir_mode *mode = get_irn_mode(node);
 850         int res;
 851
 852         /* for FP these optimizations are only allowed if fp_strict_algebraic is disabled */
 853         if (mode_is_float(mode) && get_irg_fp_model(current_ir_graph) & fp_strict_algebraic)
 854                 return;
 855
 856         do {
 857                 ir_op *op = get_irn_op(node);
 858
 859                 res = 0;
 860                 if (is_op_commutative(op)) {
 861                         wenv->changes |= res = move_consts_up(&node);
 862                 }
 863                 /* beware: move_consts_up might have changed the opcode, check again */
 864                 if (is_Add(node) || is_Sub(node)) {
 865                         wenv->changes |= res = reverse_rule_distributive(&node);
 866                 }
 867         } while (res);
 868 }
 869
 870 /*
 871  * do the reassociation
 872  */
 873 int optimize_reassociation(ir_graph *irg)
 874 {
 875         walker_t env;
 876         irg_loopinfo_state state;
 877         ir_graph *rem;
 878
 879         assert(get_irg_phase_state(irg) != phase_building);
 880         assert(get_irg_pinned(irg) != op_pin_state_floats &&
 881                 "Reassociation needs pinned graph to work properly");
 882
 883         rem = current_ir_graph;
 884         current_ir_graph = irg;
 885
 886         /* we use dominance to detect dead blocks */
 887         assure_doms(irg);
 888
 889 #ifdef NEW_REASSOC
 890         assure_irg_outs(irg);
 891         obstack_init(&commutative_args);
 892 #endif
 893
 894         /*
 895          * Calculate loop info, so we could identify loop-invariant
 896          * code and threat it like a constant.
 897          * We only need control flow loops here but can handle generic
 898          * INTRA info as well.
 899          */
 900         state = get_irg_loopinfo_state(irg);
 901         if ((state & loopinfo_inter) ||
 902                 (state & (loopinfo_constructed | loopinfo_valid)) != (loopinfo_constructed | loopinfo_valid))
 903                 construct_cf_backedges(irg);
 904
 905         env.changes = 0;
 906         env.wq      = new_waitq();
 907
 908         /* disable some optimizations while reassoc is running to prevent endless loops */
 909         set_reassoc_running(1);
 910         {
 911                 /* now we have collected enough information, optimize */
 912                 irg_walk_graph(irg, NULL, wq_walker, &env);
 913                 do_reassociation(&env);
 914
 915                 /* reverse those rules that do not result in collapsed constants */
 916                 irg_walk_graph(irg, NULL, reverse_rules, &env);
 917         }
 918         set_reassoc_running(0);
 919
 920         /* Handle graph state */
 921         if (env.changes) {
 922                 set_irg_outs_inconsistent(irg);
 923                 set_irg_loopinfo_inconsistent(irg);
 924         }
 925
 926 #ifdef NEW_REASSOC
 927         obstack_free(&commutative_args, NULL);
 928 #endif
 929
 930         del_waitq(env.wq);
 931         current_ir_graph = rem;
 932         return env.changes;
 933 }  /* optimize_reassociation */
 934
 935 /* Sets the default reassociation operation for an ir_op_ops. */
 936 ir_op_ops *firm_set_default_reassoc(ir_opcode code, ir_op_ops *ops)
 937 {
 938 #define CASE(a) case iro_##a: ops->reassociate  = reassoc_##a; break
 939
 940         switch (code) {
 941         CASE(Mul);
 942         CASE(Add);
 943         CASE(Sub);
 944         CASE(And);
 945         CASE(Or);
 946         CASE(Eor);
 947         CASE(Shl);
 948         default:
 949                 /* leave NULL */;
 950         }
 951
 952         return ops;
 953 #undef CASE
 954 }  /* firm_set_default_reassoc */
 955
 956 /* initialize the reassociation by adding operations to some opcodes */
 957 void firm_init_reassociation(void)
 958 {
 959         FIRM_DBG_REGISTER(dbg, "firm.opt.reassoc");
 960 }  /* firm_init_reassociation */