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