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