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