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

   1 /*
   2  * Copyright (C) 1995-2007 University of Karlsruhe.  All right reserved.
   3  *
   4  * This file is part of libFirm.
   5  *
   6  * This file may be distributed and/or modified under the terms of the
   7  * GNU General Public License version 2 as published by the Free Software
   8  * Foundation and appearing in the file LICENSE.GPL included in the
   9  * packaging of this file.
  10  *
  11  * Licensees holding valid libFirm Professional Edition licenses may use
  12  * this file in accordance with the libFirm Commercial License.
  13  * Agreement provided with the Software.
  14  *
  15  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  16  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  17  * PURPOSE.
  18  */
  19
  20 /**
  21  * @file
  22  * @brief   Reassociation
  23  * @author  Michael Beck
  24  * @version $Id$
  25  */
  26 #ifdef HAVE_CONFIG_H
  27 #include "config.h"
  28 #endif
  29
  30 #include "iropt_t.h"
  31 #include "irnode_t.h"
  32 #include "irgraph_t.h"
  33 #include "irmode_t.h"
  34 #include "ircons_t.h"
  35 #include "irgmod.h"
  36 #include "iropt_dbg.h"
  37 #include "irflag_t.h"
  38 #include "irgwalk.h"
  39 #include "reassoc_t.h"
  40 #include "irhooks.h"
  41 #include "irloop.h"
  42 #include "pdeq.h"
  43 #include "debug.h"
  44
  45 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
  46
  47 typedef struct _walker_t {
  48         int   changes;        /**< set, if a reassociation take place */
  49         waitq *wq;            /**< a wait queue */
  50 } walker_t;
  51
  52 typedef enum {
  53         NO_CONSTANT   = 0,    /**< node is not constant */
  54         REAL_CONSTANT = 1,    /**< node is a Const that is suitable for constant folding */
  55         REGION_CONST  = 4     /**< node is a constant expression in the current context,
  56                                    use 4 here to simplify implementation of get_comm_Binop_ops() */
  57 } const_class_t;
  58
  59 /**
  60  * returns whether a node is constant ie is a constant or
  61  * is loop invariant (called region constant)
  62  *
  63  * @param n     the node to be checked for constant
  64  * @param block a block that might be in a loop
  65  */
  66 static const_class_t get_const_class(ir_node *n, ir_node *block)
  67 {
  68         ir_op *op = get_irn_op(n);
  69
  70         if (op == op_Const)
  71                 return REAL_CONSTANT;
  72
  73         /* although SymConst's are of course real constant, we cannot
  74            fold them, so handle them like region constants */
  75         if (op == op_SymConst)
  76                 return REGION_CONST;
  77
  78         /*
  79          * Beware: Bad nodes are always loop-invariant, but
  80          * cannot handled in later code, so filter them here.
  81          */
  82         if (! is_Bad(n) && is_loop_invariant(n, block))
  83                 return REGION_CONST;
  84
  85         return NO_CONSTANT;
  86 }  /* get_const_class */
  87
  88 /**
  89  * returns the operands of a commutative bin-op, if one operand is
  90  * a region constant, it is returned as the second one.
  91  *
  92  * Beware: Real constants must be returned with higher priority than
  93  * region constants, because they might be folded.
  94  */
  95 static void get_comm_Binop_ops(ir_node *binop, ir_node **a, ir_node **c)
  96 {
  97         ir_node *op_a = get_binop_left(binop);
  98         ir_node *op_b = get_binop_right(binop);
  99         ir_node *block = get_nodes_block(binop);
 100         int class_a = get_const_class(op_a, block);
 101         int class_b = get_const_class(op_b, block);
 102
 103         assert(is_op_commutative(get_irn_op(binop)));
 104
 105         switch (class_a + 2*class_b) {
 106         case REAL_CONSTANT + 2*REAL_CONSTANT:
 107                 /* if both are constants, one might be a
 108                  * pointer constant like NULL, return the other
 109                  */
 110                 if (mode_is_reference(get_irn_mode(op_a))) {
 111                         *a = op_a;
 112                         *c = op_b;
 113                 } else {
 114                         *a = op_b;
 115                         *c = op_a;
 116                 }
 117                 break;
 118         case REAL_CONSTANT + 2*NO_CONSTANT:
 119         case REAL_CONSTANT + 2*REGION_CONST:
 120         case REGION_CONST  + 2*NO_CONSTANT:
 121                 *a = op_b;
 122                 *c = op_a;
 123                 break;
 124         default:
 125                 *a = op_a;
 126                 *c = op_b;
 127                 break;
 128         }
 129 }  /* get_comm_Binop_ops */
 130
 131 /**
 132  * reassociate a Sub: x - c = (-c) + x
 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 => (-c) + x
 149          *
 150          * As there is NO real Minus in Firm it makes no sense to do this
 151          * for non-real constants yet.
 152          */
 153         if (get_const_class(right, block) == REAL_CONSTANT) {
 154                 ir_node *left  = get_Sub_left(n);
 155                 ir_mode *mode;
 156                 dbg_info *dbi;
 157                 ir_node *irn, *c;
 158
 159                 switch (get_const_class(left, block)) {
 160                 case REAL_CONSTANT:
 161                         irn = optimize_in_place(n);
 162                         if (irn != n) {
 163                                 exchange(n, irn);
 164                                 *in = irn;
 165                                 return 1;
 166                         }
 167                         return 0;
 168                 case NO_CONSTANT:
 169                         break;
 170                 default:
 171                         /* already constant, nothing to do */
 172                         return 0;
 173                 }
 174                 mode = get_irn_mode(n);
 175                 dbi  = get_irn_dbg_info(n);
 176
 177                 /* Beware of SubP(P, Is) */
 178                 c   = new_r_Const(current_ir_graph, block, rmode, get_mode_null(rmode));
 179                 irn = new_rd_Sub(dbi, current_ir_graph, block, c, right, rmode);
 180
 181                 irn = new_rd_Add(dbi, current_ir_graph, block, left, irn, get_irn_mode(n));
 182
 183                 DBG((dbg, LEVEL_5, "Applied: %n - %n => %n + (-%n)\n",
 184                         get_Sub_left(n), c, get_Sub_left(n), c));
 185
 186                 if(n == irn)
 187                         return 0;
 188
 189                 exchange(n, irn);
 190                 *in = irn;
 191
 192                 return 1;
 193         }
 194         return 0;
 195 }  /* reassoc_Sub */
 196
 197 /** Retrieve a mode from the operands. We need this, because
 198  * Add and Sub are allowed to operate on (P, Is)
 199  */
 200 static ir_mode *get_mode_from_ops(ir_node *op1, ir_node *op2)
 201 {
 202         ir_mode *m1, *m2;
 203
 204         m1 = get_irn_mode(op1);
 205         if (mode_is_reference(m1))
 206                 return m1;
 207
 208         m2 = get_irn_mode(op2);
 209         if (mode_is_reference(m2))
 210                 return m2;
 211
 212         assert(m1 == m2);
 213
 214         return m1;
 215 }  /* get_mode_from_ops */
 216
 217 /**
 218  * reassociate a commutative Binop
 219  *
 220  * BEWARE: this rule leads to a potential loop, if
 221  * two operands are region constants and the third is a
 222  * constant, so avoid this situation.
 223  */
 224 static int reassoc_commutative(ir_node **node)
 225 {
 226         ir_node *n     = *node;
 227         ir_op *op      = get_irn_op(n);
 228         ir_node *block = get_nodes_block(n);
 229         ir_node *t1, *c1;
 230
 231         get_comm_Binop_ops(n, &t1, &c1);
 232
 233         if (get_irn_op(t1) == op) {
 234                 ir_node *t2, *c2;
 235                 const_class_t c_c1, c_c2, c_t2;
 236
 237                 get_comm_Binop_ops(t1, &t2, &c2);
 238
 239                 /* do not optimize Bad nodes, will fail later */
 240                 if (is_Bad(t2))
 241                         return 0;
 242
 243                 c_c1 = get_const_class(c1, block);
 244                 c_c2 = get_const_class(c2, block);
 245                 c_t2 = get_const_class(t2, block);
 246
 247                 if ( ((c_c1 > NO_CONSTANT) & (c_t2 > NO_CONSTANT)) &&
 248                      ((((c_c1 ^ c_c2 ^ c_t2) & REGION_CONST) == 0) || ((c_c1 & c_c2 & c_t2) == REGION_CONST)) ) {
 249                         /* All three are constant and either all are constant expressions 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) => (c1 .OP. c2) .OP. x
 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 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[0] = optimize_node(new_ir_node(NULL, current_ir_graph, block, op, mode, 2, in));
 289                         in[1] = 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),
 296                              t2, c1, get_irn_opname(n), c2, get_irn_opname(n), t2));
 297                         /*
 298                          * In some rare cases it can really happen that we get the same node back.
 299                          * This might be happen in dead loops, were the Phi nodes are already gone away.
 300                          * 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 #define reassoc_Add  reassoc_commutative
 313 #define reassoc_And  reassoc_commutative
 314 #define reassoc_Or   reassoc_commutative
 315 #define reassoc_Eor  reassoc_commutative
 316
 317 /**
 318  * reassociate using distributive law for Mul and Add/Sub
 319  */
 320 static int reassoc_Mul(ir_node **node)
 321 {
 322         ir_node *n = *node;
 323         ir_node *add_sub, *c;
 324         ir_op *op;
 325
 326         if (reassoc_commutative(&n))
 327                 return 1;
 328
 329         get_comm_Binop_ops(n, &add_sub, &c);
 330         op = get_irn_op(add_sub);
 331
 332         /* handles rules R11, R12, R13, R14, R15, R16, R17, R18, R19, R20 */
 333         if (op == op_Add || op == op_Sub) {
 334                 ir_mode *mode = get_irn_mode(n);
 335                 ir_node *irn, *block, *t1, *t2, *in[2];
 336
 337                 block = get_nodes_block(n);
 338                 t1 = get_binop_left(add_sub);
 339                 t2 = get_binop_right(add_sub);
 340
 341                 /* we can only multiplication rules on integer arithmetic */
 342                 if (mode_is_int(get_irn_mode(t1)) && mode_is_int(get_irn_mode(t2))) {
 343                         in[0] = new_rd_Mul(NULL, current_ir_graph, block, c, t1, mode);
 344                         in[1] = new_rd_Mul(NULL, current_ir_graph, block, c, t2, mode);
 345
 346                         mode  = get_mode_from_ops(in[0], in[1]);
 347                         irn   = optimize_node(new_ir_node(NULL, current_ir_graph, block, op, mode, 2, in));
 348
 349                         /* In some cases it might happen that the new irn is equal the old one, for
 350                          * instance in:
 351                          * (x - 1) * y == x * y - y
 352                          * will be transformed back by simpler optimization
 353                          * We could switch simple optimizations off, but this only happens iff y
 354                          * is a loop-invariant expression and that it is not clear if the new form
 355                          * is better.
 356                          * So, we let the old one.
 357                          */
 358                         if (irn != n) {
 359                                 DBG((dbg, LEVEL_5, "Applied: (%n .%s. %n) %n %n => (%n %n %n) .%s. (%n %n %n)\n",
 360                                         t1, get_op_name(op), t2, n, c, t1, n, c, get_op_name(op), t2, n, c));
 361                                 exchange(n, irn);
 362                                 *node = irn;
 363
 364                                 return 1;
 365                         }
 366                 }
 367         }
 368         return 0;
 369 }  /* reassoc_Mul */
 370
 371 /**
 372  * The walker for the reassociation.
 373  */
 374 static void wq_walker(ir_node *n, void *env)
 375 {
 376         walker_t *wenv = env;
 377
 378         set_irn_link(n, NULL);
 379         if (is_no_Block(n)) {
 380                 ir_node *blk = get_nodes_block(n);
 381
 382                 if (is_Block_dead(blk) || get_Block_dom_depth(blk) < 0) {
 383                         /* We are in a dead block, do not optimize or we may fall into an endless
 384                            loop. We check this here instead of requiring that all dead blocks are removed
 385                            which or cf_opt do not guarantee yet. */
 386                         return;
 387                 }
 388                 waitq_put(wenv->wq, n);
 389                 set_irn_link(n, wenv->wq);
 390         }
 391 }  /* wq_walker */
 392
 393 /**
 394  * The walker for the reassociation.
 395  */
 396 static void do_reassociation(walker_t *wenv)
 397 {
 398         int i, res, changed;
 399         ir_node *n, *blk;
 400
 401
 402         while (! waitq_empty(wenv->wq)) {
 403                 n = waitq_get(wenv->wq);
 404                 set_irn_link(n, NULL);
 405
 406                 blk = get_nodes_block(n);
 407                 if (is_Block_dead(blk) || get_Block_dom_depth(blk) < 0) {
 408                         /* We are in a dead block, do not optimize or we may fall into an endless
 409                            loop. We check this here instead of requiring that all dead blocks are removed
 410                            which or cf_opt do not guarantee yet. */
 411                         continue;
 412                 }
 413
 414
 415                 hook_reassociate(1);
 416
 417                 /* reassociation must run until a fixpoint is reached. */
 418                 changed = 0;
 419                 do {
 420                         ir_op   *op    = get_irn_op(n);
 421                         ir_mode *mode  = get_irn_mode(n);
 422
 423                         res = 0;
 424
 425                         /* for FP these optimizations are only allowed if fp_strict_algebraic is disabled */
 426                         if (mode_is_float(mode) && get_irg_fp_model(current_ir_graph) & fp_strict_algebraic)
 427                                 break;
 428
 429                         if (op->ops.reassociate) {
 430                                 res = op->ops.reassociate(&n);
 431
 432                                 changed |= res;
 433                         }
 434                 } while (res == 1);
 435                 hook_reassociate(0);
 436
 437                 wenv->changes |= changed;
 438
 439                 if (changed) {
 440                         for (i = get_irn_arity(n) - 1; i >= 0; --i) {
 441                                 ir_node *pred = get_irn_n(n, i);
 442
 443                                 if (get_irn_link(pred) != wenv->wq) {
 444                                         waitq_put(wenv->wq, pred);
 445                                         set_irn_link(pred, wenv->wq);
 446                                 }
 447                         }
 448                 }
 449         }
 450 }  /* do_reassociation */
 451
 452 /*
 453  * do the reassociation
 454  */
 455 void optimize_reassociation(ir_graph *irg)
 456 {
 457         walker_t env;
 458         irg_loopinfo_state state;
 459
 460         assert(get_irg_phase_state(irg) != phase_building);
 461         assert(get_irg_pinned(irg) != op_pin_state_floats &&
 462                 "Reassociation needs pinned graph to work properly");
 463
 464         /* reassociation needs constant folding */
 465         if (!get_opt_reassociation() || !get_opt_constant_folding())
 466                 return;
 467
 468         /* we use dominance to detect dead blocks */
 469         assure_doms(irg);
 470
 471         /*
 472          * Calculate loop info, so we could identify loop-invariant
 473          * code and threat it like a constant.
 474          * We only need control flow loops here but can handle generic
 475          * INTRA info as well.
 476          */
 477         state = get_irg_loopinfo_state(irg);
 478         if ((state & loopinfo_inter) ||
 479                 (state & (loopinfo_constructed | loopinfo_valid)) != (loopinfo_constructed | loopinfo_valid))
 480                 construct_cf_backedges(irg);
 481
 482         env.changes = 0;
 483         env.wq      = new_waitq();
 484
 485         /* now we have collected enough information, optimize */
 486         irg_walk_graph(irg, NULL, wq_walker, &env);
 487         do_reassociation(&env);
 488
 489         /* Handle graph state */
 490         if (env.changes) {
 491                 set_irg_outs_inconsistent(irg);
 492                 set_irg_loopinfo_inconsistent(irg);
 493         }
 494
 495         del_waitq(env.wq);
 496 }  /* optimize_reassociation */
 497
 498 /* Sets the default reassociation operation for an ir_op_ops. */
 499 ir_op_ops *firm_set_default_reassoc(ir_opcode code, ir_op_ops *ops)
 500 {
 501 #define CASE(a) case iro_##a: ops->reassociate  = reassoc_##a; break
 502
 503         switch (code) {
 504         CASE(Mul);
 505         CASE(Add);
 506         CASE(Sub);
 507         CASE(And);
 508         CASE(Or);
 509         CASE(Eor);
 510         default:
 511                 /* leave NULL */;
 512         }
 513
 514         return ops;
 515 #undef CASE
 516 }  /* firm_set_default_reassoc */
 517
 518 /* initialize the reassociation by adding operations to some opcodes */
 519 void firm_init_reassociation(void)
 520 {
 521         FIRM_DBG_REGISTER(dbg, "firm.opt.reassoc");
 522 }  /* firm_init_reassociation */