nsz Git - libfirm/blob - ir/opt/reassoc.c

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