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