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