nsz Git - libfirm/blob - ir/opt/opt_osr.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   Operator Strength Reduction.
  23  * @date    12.5.2006
  24  * @author  Michael Beck
  25  * @version $Id$
  26  * @summary
  27  *  Implementation of the Operator Strength Reduction algorithm
  28  *  by Keith D. Cooper, L. Taylor Simpson, Christopher A. Vick.
  29  */
  30 #ifdef HAVE_CONFIG_H
  31 #include "config.h"
  32 #endif
  33
  34 #include "iroptimize.h"
  35 #include "irgraph.h"
  36 #include "ircons.h"
  37 #include "irop_t.h"
  38 #include "irloop.h"
  39 #include "irdom.h"
  40 #include "irgmod.h"
  41 #include "irflag_t.h"
  42 #include "irgwalk.h"
  43 #include "irouts.h"
  44 #include "debug.h"
  45 #include "obst.h"
  46 #include "set.h"
  47 #include "tv.h"
  48 #include "hashptr.h"
  49 #include "irtools.h"
  50 #include "irloop_t.h"
  51 #include "array.h"
  52 #include "firmstat.h"
  53 #include "xmalloc.h"
  54
  55 /** The debug handle. */
  56 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
  57
  58 /** A scc. */
  59 typedef struct scc {
  60         ir_node *head;          /**< the head of the list */
  61 } scc;
  62
  63 /** A node entry */
  64 typedef struct node_entry {
  65         unsigned DFSnum;    /**< the DFS number of this node */
  66         unsigned low;       /**< the low number of this node */
  67         ir_node  *header;   /**< the header of this node */
  68         int      in_stack;  /**< flag, set if the node is on the stack */
  69         ir_node  *next;     /**< link to the next node the the same scc */
  70         scc      *pscc;     /**< the scc of this node */
  71         unsigned POnum;     /**< the post order number for blocks */
  72 } node_entry;
  73
  74 /** The environment. */
  75 typedef struct iv_env {
  76         struct obstack obst;    /**< an obstack for allocations */
  77         ir_node  **stack;       /**< the node stack */
  78         int      tos;           /**< tos index */
  79         unsigned nextDFSnum;    /**< the current DFS number */
  80         unsigned POnum;         /**< current post order number */
  81         set      *quad_map;     /**< a map from (op, iv, rc) to node */
  82         set      *lftr_edges;   /**< the set of lftr edges */
  83         unsigned replaced;      /**< number of replaced ops */
  84         unsigned lftr_replaced; /**< number of applied linear function test replacements */
  85         unsigned flags;         /**< additional flags */
  86         /** Function called to process a SCC. */
  87         void (*process_scc)(scc *pscc, struct iv_env *env);
  88 } iv_env;
  89
  90 /**
  91  * An entry in the (op, node, node) -> node map.
  92  */
  93 typedef struct quadruple_t {
  94         ir_opcode code;  /**< the opcode of the reduced operation */
  95         ir_node   *op1;  /**< the first operand the reduced operation */
  96         ir_node   *op2;  /**< the second operand of the reduced operation */
  97
  98         ir_node   *res; /**< the reduced operation */
  99 } quadruple_t;
 100
 101 /**
 102  * A LFTR edge.
 103  */
 104 typedef struct LFTR_edge {
 105         ir_node   *src;   /**< the source node */
 106         ir_node   *dst;   /**< the destination node */
 107         ir_opcode code;   /**< the opcode that must be applied */
 108         ir_node   *rc;    /**< the region const that must be applied */
 109 } LFTR_edge;
 110
 111 /* forward */
 112 static ir_node *reduce(ir_node *orig, ir_node *iv, ir_node *rc, iv_env *env);
 113
 114 /**
 115  * Compare two LFTR edges.
 116  */
 117 static int LFTR_cmp(const void *e1, const void *e2, size_t size) {
 118         const LFTR_edge *l1 = e1;
 119         const LFTR_edge *l2 = e2;
 120
 121         return l1->src != l2->src;
 122 }
 123
 124 #if 0
 125 /**
 126  * Find a LFTR edge.
 127  */
 128 static LFTR_edge *LFTR_find(ir_node *src, iv_env *env) {
 129         LFTR_edge key;
 130
 131         key.src  = src;
 132
 133         return set_find(env->lftr_edges, &key, sizeof(key), HASH_PTR(src));
 134 }
 135 #endif
 136
 137 /**
 138  * Add a LFTR edge.
 139  */
 140 static void LFTR_add(ir_node *src, ir_node *dst, ir_opcode code, ir_node *rc, iv_env *env) {
 141         LFTR_edge key;
 142
 143         key.src  = src;
 144         key.dst  = dst;
 145         key.code = code;
 146         key.rc   = rc;
 147
 148         /*
 149          * There might be more than one edge here. This is rather bad
 150          * because we currently store only one.
 151          */
 152 //      assert(LFTR_find(src, env) == NULL);
 153         set_insert(env->lftr_edges, &key, sizeof(key), HASH_PTR(src));
 154 }
 155
 156 /**
 157  * Gets the node_entry of a node
 158  */
 159 static node_entry *get_irn_ne(ir_node *irn, iv_env *env) {
 160         node_entry *e = get_irn_link(irn);
 161
 162         if (! e) {
 163                 e = obstack_alloc(&env->obst, sizeof(*e));
 164                 memset(e, 0, sizeof(*e));
 165                 set_irn_link(irn, e);
 166         }
 167         return e;
 168 }
 169
 170 /**
 171  * Check if irn is an IV.
 172  *
 173  * @param irn  the node to check
 174  * @param env  the environment
 175  *
 176  * @returns the header if it is one, NULL else
 177  */
 178 static ir_node *is_iv(ir_node *irn, iv_env *env) {
 179         return get_irn_ne(irn, env)->header;
 180 }
 181
 182 /**
 183  * Check if irn is a region constant.
 184  * The block or irn must strictly dominate the header block.
 185  *
 186  * @param irn           the node to check
 187  * @param header_block  the header block of the induction variable
 188  */
 189 static int is_rc(ir_node *irn, ir_node *header_block) {
 190         ir_node *block = get_nodes_block(irn);
 191
 192         return (block != header_block) && block_dominates(block, header_block);
 193 }
 194
 195 /**
 196  * Set compare function for the quad set.
 197  */
 198 static int quad_cmp(const void *e1, const void *e2, size_t size) {
 199         const quadruple_t *c1 = e1;
 200         const quadruple_t *c2 = e2;
 201
 202         return c1->code != c2->code || c1->op1 != c2->op1 || c1->op2 != c2->op2;
 203 }
 204
 205 /**
 206  * Check if an reduced operation was already calculated.
 207  *
 208  * @param code  the opcode of the operation
 209  * @param op1   the first operand of the operation
 210  * @param op2   the second operand of the operation
 211  * @param env   the environment
 212  *
 213  * @return the already reduced node or NULL if this operation is not yet reduced
 214  */
 215 static ir_node *search(ir_opcode code, ir_node *op1, ir_node *op2, iv_env *env) {
 216         quadruple_t key, *entry;
 217
 218         key.code = code;
 219         key.op1 = op1;
 220         key.op2 = op2;
 221
 222         entry = set_find(env->quad_map, &key, sizeof(key),
 223                          (code * 9) ^ HASH_PTR(op1) ^HASH_PTR(op2));
 224         if (entry)
 225                 return entry->res;
 226         return NULL;
 227 }
 228
 229 /**
 230  * Add an reduced operation.
 231  *
 232  * @param code    the opcode of the operation
 233  * @param op1     the first operand of the operation
 234  * @param op2     the second operand of the operation
 235  * @param result  the result of the reduced operation
 236  * @param env     the environment
 237  */
 238 static void add(ir_opcode code, ir_node *op1, ir_node *op2, ir_node *result, iv_env *env) {
 239         quadruple_t key;
 240
 241         key.code = code;
 242         key.op1  = op1;
 243         key.op2  = op2;
 244         key.res  = result;
 245
 246         set_insert(env->quad_map, &key, sizeof(key),
 247                    (code * 9) ^ HASH_PTR(op1) ^HASH_PTR(op2));
 248 }
 249
 250 /**
 251  * Find a location where to place a bin-op whose operands are in
 252  * block1 and block2.
 253  *
 254  * @param block1  the block of the first operand
 255  * @param block2  the block of the second operand
 256  *
 257  * Note that we know here that such a place must exists. Moreover, this means
 258  * that either block1 dominates block2 or vice versa. So, just return
 259  * the "smaller" one.
 260  */
 261 static ir_node *find_location(ir_node *block1, ir_node *block2) {
 262         if (block_dominates(block1, block2))
 263                 return block2;
 264         assert(block_dominates(block2, block1));
 265         return block1;
 266 }
 267
 268 /**
 269  * Create a node that executes an op1 code op1 operation.
 270  *
 271  * @param code   the opcode to execute
 272  * @param db     debug info to add to the new node
 273  * @param op1    the first operand
 274  * @param op2    the second operand
 275  * @param mode   the mode of the new operation
 276  *
 277  * @return the newly created node
 278  */
 279 static ir_node *do_apply(ir_opcode code, dbg_info *db, ir_node *op1, ir_node *op2, ir_mode *mode) {
 280         ir_graph *irg = current_ir_graph;
 281         ir_node *result;
 282         ir_node *block = find_location(get_nodes_block(op1), get_nodes_block(op2));
 283
 284         switch (code) {
 285         case iro_Mul:
 286                 result = new_rd_Mul(db, irg, block, op1, op2, mode);
 287                 break;
 288         case iro_Add:
 289                 result = new_rd_Add(db, irg, block, op1, op2, mode);
 290                 break;
 291         case iro_Sub:
 292                 result = new_rd_Sub(db, irg, block, op1, op2, mode);
 293                 break;
 294         default:
 295                 assert(0);
 296                 result = NULL;
 297         }
 298         return result;
 299 }
 300
 301 /**
 302  * The Apply operation.
 303  *
 304  * @param orig   the node that represent the original operation and determines
 305  *               the opcode, debug-info and mode of a newly created one
 306  * @param op1    the first operand
 307  * @param op2    the second operand
 308  * @param env    the environment
 309  *
 310  * @return the newly created node
 311  */
 312 static ir_node *apply(ir_node *orig, ir_node *op1, ir_node *op2, iv_env *env) {
 313         ir_opcode code = get_irn_opcode(orig);
 314         ir_node *result = search(code, op1, op2, env);
 315
 316         if (! result) {
 317                 dbg_info *db = get_irn_dbg_info(orig);
 318                 ir_node *op1_header = get_irn_ne(op1, env)->header;
 319                 ir_node *op2_header = get_irn_ne(op2, env)->header;
 320
 321                 if (op1_header != NULL && is_rc(op2, op1_header)) {
 322                         result = reduce(orig, op1, op2, env);
 323                 }
 324                 else if (op2_header != NULL && is_rc(op1, op2_header)) {
 325                         result = reduce(orig, op2, op1, env);
 326                 }
 327                 else {
 328                         result = do_apply(code, db, op1, op2, get_irn_mode(orig));
 329                         get_irn_ne(result, env)->header = NULL;         }
 330         }
 331         return result;
 332 }
 333
 334 /**
 335  * The Reduce operation.
 336  *
 337  * @param orig   the node that represent the original operation and determines
 338  *               the opcode, debug-info and mode of a newly created one
 339  * @param iv     the induction variable
 340  * @param rc     the region constant
 341  * @param env    the environment
 342  *
 343  * @return the reduced node
 344  */
 345 static ir_node *reduce(ir_node *orig, ir_node *iv, ir_node *rc, iv_env *env) {
 346         ir_opcode code = get_irn_opcode(orig);
 347         ir_node *result = search(code, iv, rc, env);
 348
 349         if (! result) {
 350                 node_entry *e, *iv_e;
 351                 int i, n;
 352                 ir_mode *mode = get_irn_mode(orig);
 353
 354                 result = exact_copy(iv);
 355
 356                 /* Beware: we must always create a new nduction variable with the same mode
 357                    as the node we are replacing. Espicially this means the mode might be changed
 358                    from P to I and back. This is always possible, because we have only Phi, Add
 359                    and Sub nodes. */
 360                 set_irn_mode(result, mode);
 361                 add(code, iv, rc, result, env);
 362                 DB((dbg, LEVEL_3, "   Created new %+F for %+F (%s %+F)\n", result, iv,
 363                         get_irn_opname(orig), rc));
 364
 365                 iv_e = get_irn_ne(iv, env);
 366                 e    = get_irn_ne(result, env);
 367                 e->header = iv_e->header;
 368
 369                 /* create the LFTR edge */
 370                 LFTR_add(iv, result, code, rc, env);
 371
 372                 n = get_irn_arity(result);
 373                 for (i = 0; i < n; ++i) {
 374                         ir_node *o = get_irn_n(result, i);
 375
 376                         e = get_irn_ne(o, env);
 377                         if (e->header == iv_e->header)
 378                                 o = reduce(orig, o, rc, env);
 379                         else if (is_Phi(result))
 380                                 o = apply(orig, o, rc, env);
 381                         else {
 382                                 if (code == iro_Mul)
 383                                         o = apply(orig, o, rc, env);
 384                         }
 385                         set_irn_n(result, i, o);
 386                 }
 387         }
 388         else {
 389                 DB((dbg, LEVEL_3, "   Already Created %+F for %+F (%s %+F)\n", result, iv,
 390                         get_irn_opname(orig), rc));
 391         }
 392         return result;
 393 }
 394
 395 /**
 396  * The Replace operation.
 397  *
 398  * @param irn   the node that will be replaced
 399  * @param iv    the induction variable
 400  * @param rc    the region constant
 401  * @param env   the environment
 402  */
 403 static int replace(ir_node *irn, ir_node *iv, ir_node *rc, iv_env *env) {
 404         ir_node *result;
 405         ir_loop *iv_loop  = get_irn_loop(get_nodes_block(iv));
 406         ir_loop *irn_loop = get_irn_loop(get_nodes_block(irn));
 407
 408         /* only replace nodes that are in the same (or deeper loops) */
 409         if (get_loop_depth(irn_loop) >= get_loop_depth(iv_loop)) {
 410                 DB((dbg, LEVEL_2, "  Replacing %+F\n", irn));
 411
 412                 result = reduce(irn, iv, rc, env);
 413                 if (result != irn) {
 414                         node_entry *e, *iv_e;
 415
 416                         hook_strength_red(current_ir_graph, irn);
 417                         exchange(irn, result);
 418                         e = get_irn_ne(result, env);
 419                         iv_e = get_irn_ne(iv, env);
 420                         e->header = iv_e->header;
 421                 }
 422                 return 1;
 423         }
 424         return 0;
 425 }
 426
 427 /**
 428  * Check if a node can be replaced (+, -, *).
 429  *
 430  * @param irn   the node to check
 431  * @param env   the environment
 432  *
 433  * @return non-zero if irn should be Replace'd
 434  */
 435 static int check_replace(ir_node *irn, iv_env *env) {
 436         ir_node   *left, *right, *iv, *rc;
 437         ir_op     *op  = get_irn_op(irn);
 438         ir_opcode code = get_op_code(op);
 439         ir_node   *liv, *riv;
 440
 441         switch (code) {
 442         case iro_Mul:
 443         case iro_Add:
 444         case iro_Sub:
 445                 iv = rc = NULL;
 446
 447                 left  = get_binop_left(irn);
 448                 right = get_binop_right(irn);
 449
 450                 liv = is_iv(left, env);
 451                 riv = is_iv(right, env);
 452                 if (liv && is_rc(right, liv)) {
 453                         iv = left; rc = right;
 454                 }
 455                 else if (riv && is_op_commutative(op) &&
 456                                     is_rc(left, riv)) {
 457                         iv = right; rc = left;
 458                 }
 459
 460                 if (iv) {
 461                         if (code == iro_Mul && env->flags & osr_flag_ignore_x86_shift) {
 462                                 if (is_Const(rc)) {
 463                                         tarval *tv = get_Const_tarval(rc);
 464
 465                                         if (tarval_is_long(tv)) {
 466                                                 long value = get_tarval_long(tv);
 467
 468                                                 if (value == 2 || value == 4 || value == 8) {
 469                                                         /* do not reduce multiplications by 2, 4, 8 */
 470                                                         break;
 471                                                 }
 472                                         }
 473                                 }
 474                         }
 475
 476                         return replace(irn, iv, rc, env);
 477                 }
 478                 break;
 479         default:
 480                 break;
 481         }
 482         return 0;
 483 }
 484
 485 /**
 486  * Check which SCC's are induction variables.
 487  *
 488  * @param pscc  a SCC
 489  * @param env   the environment
 490  */
 491 static void classify_iv(scc *pscc, iv_env *env) {
 492         ir_node *irn, *next, *header = NULL;
 493         node_entry *b, *h = NULL;
 494         int j, only_phi, num_outside;
 495         ir_node *out_rc;
 496
 497         /* find the header block for this scc */
 498         for (irn = pscc->head; irn; irn = next) {
 499                 node_entry *e = get_irn_link(irn);
 500                 ir_node *block = get_nodes_block(irn);
 501
 502                 next = e->next;
 503                 b = get_irn_ne(block, env);
 504
 505                 if (header) {
 506                         if (h->POnum < b->POnum) {
 507                                 header = block;
 508                                 h      = b;
 509                         }
 510                 }
 511                 else {
 512                         header = block;
 513                         h      = b;
 514                 }
 515         }
 516
 517         /* check if this scc contains only Phi, Add or Sub nodes */
 518         only_phi    = 1;
 519         num_outside = 0;
 520         out_rc      = NULL;
 521         for (irn = pscc->head; irn; irn = next) {
 522                 node_entry *e = get_irn_ne(irn, env);
 523
 524                 next = e->next;
 525                 switch (get_irn_opcode(irn)) {
 526                 case iro_Add:
 527                 case iro_Sub:
 528                         only_phi = 0;
 529                         /* fall through */
 530                 case iro_Phi:
 531                         for (j = get_irn_arity(irn) - 1; j >= 0; --j) {
 532                                 ir_node *pred  = get_irn_n(irn, j);
 533                                 node_entry *pe = get_irn_ne(pred, env);
 534
 535                                 if (pe->pscc != e->pscc) {
 536                                         /* not in the same SCC, must be a region const */
 537                                         if (! is_rc(pred, header)) {
 538                                                 /* not an induction variable */
 539                                                 goto fail;
 540                                         }
 541                                         if (! out_rc) {
 542                                                 out_rc = pred;
 543                                                 ++num_outside;
 544                                         } else if (out_rc != pred) {
 545                                                 ++num_outside;
 546                                         }
 547                                 }
 548                         }
 549                         break;
 550                 default:
 551                         /* not an induction variable */
 552                         goto fail;
 553                 }
 554         }
 555         /* found an induction variable */
 556         DB((dbg, LEVEL_2, "  Found an induction variable:\n  "));
 557         if (only_phi && num_outside == 1) {
 558                 /* a phi cycle with only one real predecessor can be collapsed */
 559                 DB((dbg, LEVEL_2, "  Found an USELESS Phi cycle:\n  "));
 560
 561                 for (irn = pscc->head; irn; irn = next) {
 562                         node_entry *e = get_irn_ne(irn, env);
 563                         next = e->next;
 564                         e->header = NULL;
 565                         exchange(irn, out_rc);
 566                 }
 567                 ++env->replaced;
 568                 return;
 569         }
 570
 571         /* set the header for every node in this scc */
 572         for (irn = pscc->head; irn; irn = next) {
 573                 node_entry *e = get_irn_ne(irn, env);
 574                 e->header = header;
 575                 next = e->next;
 576                 DB((dbg, LEVEL_2, " %+F,", irn));
 577         }
 578         DB((dbg, LEVEL_2, "\n"));
 579         return;
 580
 581 fail:
 582         for (irn = pscc->head; irn; irn = next) {
 583                 node_entry *e = get_irn_ne(irn, env);
 584
 585                 next = e->next;
 586                 if (! check_replace(irn, env))
 587                         e->header = NULL;
 588         }
 589 }
 590
 591 /**
 592  * Process a SCC for the operator strength reduction.
 593  *
 594  * @param pscc  the SCC
 595  * @param env   the environment
 596  */
 597 static void process_scc(scc *pscc, iv_env *env) {
 598         ir_node *head = pscc->head;
 599         node_entry *e = get_irn_link(head);
 600
 601 #ifdef DEBUG_libfirm
 602         {
 603                 ir_node *irn, *next;
 604
 605                 DB((dbg, LEVEL_4, " SCC at %p:\n ", pscc));
 606                 for (irn = pscc->head; irn; irn = next) {
 607                         node_entry *e = get_irn_link(irn);
 608
 609                         next = e->next;
 610
 611                         DB((dbg, LEVEL_4, " %+F,", irn));
 612                 }
 613                 DB((dbg, LEVEL_4, "\n"));
 614         }
 615 #endif
 616
 617         if (e->next == NULL) {
 618                 /* this SCC has only a single member */
 619                 check_replace(head, env);
 620         } else {
 621                 classify_iv(pscc, env);
 622         }
 623 }
 624
 625 /**
 626  * If an SCC is a Phi only cycle, remove it.
 627  */
 628 static void remove_phi_cycle(scc *pscc, iv_env *env) {
 629         ir_node *irn, *next;
 630         int j;
 631         ir_node *out_rc;
 632
 633         /* check if this scc contains only Phi, Add or Sub nodes */
 634         out_rc      = NULL;
 635         for (irn = pscc->head; irn; irn = next) {
 636                 node_entry *e = get_irn_ne(irn, env);
 637
 638                 next = e->next;
 639                 if (! is_Phi(irn))
 640                         return;
 641
 642                 for (j = get_irn_arity(irn) - 1; j >= 0; --j) {
 643                         ir_node *pred  = get_irn_n(irn, j);
 644                         node_entry *pe = get_irn_ne(pred, env);
 645
 646                         if (pe->pscc != e->pscc) {
 647                                 /* not in the same SCC, must be the only input */
 648                                 if (! out_rc) {
 649                                         out_rc = pred;
 650                                 } else if (out_rc != pred) {
 651                                         return;
 652                                 }
 653                         }
 654                 }
 655         }
 656         /* found a Phi cycle */
 657         DB((dbg, LEVEL_2, "  Found an USELESS Phi cycle:\n  "));
 658
 659         for (irn = pscc->head; irn; irn = next) {
 660                 node_entry *e = get_irn_ne(irn, env);
 661                 next = e->next;
 662                 e->header = NULL;
 663                 exchange(irn, out_rc);
 664         }
 665         ++env->replaced;
 666 }
 667
 668 /**
 669  * Process a SCC for the Phi cycle removement.
 670  *
 671  * @param pscc  the SCC
 672  * @param env   the environment
 673  */
 674 static void process_phi_only_scc(scc *pscc, iv_env *env) {
 675         ir_node *head = pscc->head;
 676         node_entry *e = get_irn_link(head);
 677
 678 #ifdef DEBUG_libfirm
 679         {
 680                 ir_node *irn, *next;
 681
 682                 DB((dbg, LEVEL_4, " SCC at %p:\n ", pscc));
 683                 for (irn = pscc->head; irn; irn = next) {
 684                         node_entry *e = get_irn_link(irn);
 685
 686                         next = e->next;
 687
 688                         DB((dbg, LEVEL_4, " %+F,", irn));
 689                 }
 690                 DB((dbg, LEVEL_4, "\n"));
 691         }
 692 #endif
 693
 694         if (e->next != NULL)
 695                 remove_phi_cycle(pscc, env);
 696 }
 697
 698
 699 /**
 700  * Push a node onto the stack.
 701  *
 702  * @param env   the environment
 703  * @param n     the node to push
 704  */
 705 static void push(iv_env *env, ir_node *n) {
 706         node_entry *e;
 707
 708         if (env->tos == ARR_LEN(env->stack)) {
 709                 int nlen = ARR_LEN(env->stack) * 2;
 710                 ARR_RESIZE(ir_node *, env->stack, nlen);
 711         }
 712         env->stack[env->tos++] = n;
 713         e = get_irn_ne(n, env);
 714         e->in_stack = 1;
 715 }
 716
 717 /**
 718  * pop a node from the stack
 719  *
 720  * @param env   the environment
 721  *
 722  * @return  The topmost node
 723  */
 724 static ir_node *pop(iv_env *env)
 725 {
 726         ir_node *n = env->stack[--env->tos];
 727         node_entry *e = get_irn_ne(n, env);
 728
 729         e->in_stack = 0;
 730         return n;
 731 }
 732
 733 /**
 734  * Do Tarjan's SCC algorithm and drive OSR.
 735  *
 736  * @param irn  start at this node
 737  * @param env  the environment
 738  */
 739 static void dfs(ir_node *irn, iv_env *env)
 740 {
 741         int i, n;
 742         node_entry *node = get_irn_ne(irn, env);
 743
 744         mark_irn_visited(irn);
 745
 746         /* do not put blocks into the scc */
 747         if (is_Block(irn)) {
 748                 n = get_irn_arity(irn);
 749                 for (i = 0; i < n; ++i) {
 750                         ir_node *pred = get_irn_n(irn, i);
 751
 752                         if (irn_not_visited(pred))
 753                                 dfs(pred, env);
 754                 }
 755         }
 756         else {
 757                 ir_node *block = get_nodes_block(irn);
 758
 759                 node->DFSnum = env->nextDFSnum++;
 760                 node->low    = node->DFSnum;
 761                 push(env, irn);
 762
 763                 /* handle the block */
 764                 if (irn_not_visited(block))
 765                         dfs(block, env);
 766
 767                 n = get_irn_arity(irn);
 768                 for (i = 0; i < n; ++i) {
 769                         ir_node *pred = get_irn_n(irn, i);
 770                         node_entry *o = get_irn_ne(pred, env);
 771
 772                         if (irn_not_visited(pred)) {
 773                                 dfs(pred, env);
 774                                 node->low = MIN(node->low, o->low);
 775                         }
 776                         if (o->DFSnum < node->DFSnum && o->in_stack)
 777                                 node->low = MIN(o->DFSnum, node->low);
 778                 }
 779                 if (node->low == node->DFSnum) {
 780                         scc *pscc = obstack_alloc(&env->obst, sizeof(*pscc));
 781                         ir_node *x;
 782
 783                         pscc->head = NULL;
 784                         do {
 785                                 node_entry *e;
 786
 787                                 x = pop(env);
 788                                 e = get_irn_ne(x, env);
 789                                 e->pscc    = pscc;
 790                                 e->next    = pscc->head;
 791                                 pscc->head = x;
 792                         } while (x != irn);
 793
 794                         env->process_scc(pscc, env);
 795                 }
 796         }
 797 }
 798
 799 /**
 800  * Do the DFS by starting at the End node of a graph.
 801  *
 802  * @param irg  the graph to process
 803  * @param env  the environment
 804  */
 805 static void do_dfs(ir_graph *irg, iv_env *env) {
 806         ir_graph *rem = current_ir_graph;
 807         ir_node *end = get_irg_end(irg);
 808         int i, n;
 809
 810         current_ir_graph = irg;
 811         inc_irg_visited(irg);
 812
 813         /* visit all visible nodes */
 814         dfs(end, env);
 815
 816         /* visit the keep-alives */
 817         n = get_End_n_keepalives(end);
 818         for (i = 0; i < n; ++i) {
 819                 ir_node *ka = get_End_keepalive(end, i);
 820
 821                 if (irn_not_visited(ka))
 822                         dfs(ka, env);
 823         }
 824
 825         current_ir_graph = rem;
 826 }
 827
 828 /**
 829  * Post-block-walker: assign the post-order number.
 830  */
 831 static void assign_po(ir_node *block, void *ctx) {
 832         iv_env *env = ctx;
 833         node_entry *e = get_irn_ne(block, env);
 834
 835         e->POnum = env->POnum++;
 836 }
 837
 838 #if 0
 839 /**
 840  * Follows the LFTR edges and return the last node in the chain.
 841  *
 842  * @param irn  the node that should be followed
 843  * @param env  the IV environment
 844  *
 845  * @note
 846  * In the current implementation only the last edge is stored, so
 847  * only one chain exists. That's why we might miss some opportunities.
 848  */
 849 static ir_node *followEdges(ir_node *irn, iv_env *env) {
 850         for (;;) {
 851                 LFTR_edge *e = LFTR_find(irn, env);
 852                 if (e)
 853                         irn = e->dst;
 854                 else
 855                         return irn;
 856         }
 857 }
 858
 859 /**
 860  * Apply one LFTR edge operation.
 861  * Return NULL if the transformation cannot be done safely without
 862  * an Overflow.
 863  *
 864  * @param rc   the IV node that should be translated
 865  * @param e    the LFTR edge
 866  * @param env  the IV environment
 867  *
 868  * @return the translated region constant or NULL
 869  *         if the translation was not possible
 870  *
 871  * @note
 872  * In the current implementation only the last edge is stored, so
 873  * only one chain exists. That's why we might miss some opportunities.
 874  */
 875 static ir_node *applyOneEdge(ir_node *rc, LFTR_edge *e, iv_env *env) {
 876         if (env->flags & osr_flag_lftr_with_ov_check) {
 877                 tarval *tv_l, *tv_r, *tv;
 878                 tarval_int_overflow_mode_t ovmode;
 879
 880                 /* overflow can only be decided for Consts */
 881                 if (! is_Const(e->rc)) {
 882                         DB((dbg, LEVEL_4, " = UNKNOWN (%+F)", e->rc));
 883                         return NULL;
 884                 }
 885
 886                 tv_l = get_Const_tarval(rc);
 887                 tv_r = get_Const_tarval(e->rc);
 888
 889                 ovmode = tarval_get_integer_overflow_mode();
 890                 tarval_set_integer_overflow_mode(TV_OVERFLOW_BAD);
 891
 892                 switch (e->code) {
 893                 case iro_Mul:
 894                         tv = tarval_mul(tv_l, tv_r);
 895                         DB((dbg, LEVEL_4, " * %+F", tv_r));
 896                         break;
 897                 case iro_Add:
 898                         tv = tarval_add(tv_l, tv_r);
 899                         DB((dbg, LEVEL_4, " + %+F", tv_r));
 900                         break;
 901                 case iro_Sub:
 902                         tv = tarval_sub(tv_l, tv_r);
 903                         DB((dbg, LEVEL_4, " - %+F", tv_r));
 904                         break;
 905                 default:
 906                         assert(0);
 907                         tv = tarval_bad;
 908                 }
 909                 tarval_set_integer_overflow_mode(ovmode);
 910
 911                 if (tv == tarval_bad) {
 912                         DB((dbg, LEVEL_4, " = OVERFLOW"));
 913                         return NULL;
 914                 }
 915                 return new_r_Const(current_ir_graph, get_irn_n(rc, -1), get_tarval_mode(tv), tv);
 916         }
 917         return do_apply(e->code, NULL, rc, e->rc, get_irn_mode(rc));
 918 }
 919
 920 /**
 921  * Applies the operations represented by the LFTR edges to a
 922  * region constant and returns the value.
 923  * Return NULL if the transformation cannot be done safely without
 924  * an Overflow.
 925  *
 926  * @param iv   the IV node that starts the LFTR edge chain
 927  * @param rc   the region constant that should be translated
 928  * @param env  the IV environment
 929  *
 930  * @return the translated region constant or NULL
 931  *         if the translation was not possible
 932  */
 933 static ir_node *applyEdges(ir_node *iv, ir_node *rc, iv_env *env) {
 934         ir_node *irn = iv;
 935
 936         if (env->flags & osr_flag_lftr_with_ov_check) {
 937                 /* overflow can only be decided for Consts */
 938                 if (! is_Const(rc)) {
 939                         DB((dbg, LEVEL_4, " = UNKNOWN (%+F)\n", rc));
 940                         return NULL;
 941                 }
 942                 DB((dbg, LEVEL_4, "%+F", get_Const_tarval(rc)));
 943         }
 944
 945         for (irn = iv; rc;) {
 946                 LFTR_edge *e = LFTR_find(irn, env);
 947                 if (e) {
 948                         rc = applyOneEdge(rc, e, env);
 949                         irn = e->dst;
 950                 }
 951                 else
 952                         break;
 953         }
 954         DB((dbg, LEVEL_3, "\n"));
 955         return rc;
 956 }
 957
 958 /**
 959  * Walker, finds Cmp(iv, rc) or Cmp(rc, iv)
 960  * and tries to optimize them.
 961  */
 962 static void do_lftr(ir_node *cmp, void *ctx) {
 963         iv_env *env = ctx;
 964         ir_node *left, *right, *liv, *riv;
 965         ir_node *iv, *rc;
 966         ir_node *nleft = NULL, *nright = NULL;
 967
 968         if (get_irn_op(cmp) != op_Cmp)
 969                 return;
 970
 971         left  = get_Cmp_left(cmp);
 972         right = get_Cmp_right(cmp);
 973
 974         liv = is_iv(left, env);
 975         riv = is_iv(right, env);
 976         if (liv && is_rc(right, liv)) {
 977                 iv = left; rc = right;
 978
 979                 nright = applyEdges(iv, rc, env);
 980                 if (nright && nright != rc) {
 981                         nleft = followEdges(iv, env);
 982                 }
 983         }
 984         else if (riv && is_rc(left, riv)) {
 985                 iv = right; rc = left;
 986
 987                 nleft = applyEdges(iv, rc, env);
 988                 if (nleft && nleft != rc) {
 989                         nright = followEdges(iv, env);
 990                 }
 991         }
 992
 993         if (nleft && nright) {
 994                 DB((dbg, LEVEL_2, "  LFTR for %+F\n", cmp));
 995                 set_Cmp_left(cmp, nleft);
 996                 set_Cmp_right(cmp, nright);
 997                 ++env->lftr_replaced;
 998         }
 999 }
1000
1001 /**
1002  * do linear function test replacement.
1003  *
1004  * @param irg   the graph that should be optimized
1005  * @param env   the IV environment
1006  */
1007 static void lftr(ir_graph *irg, iv_env *env) {
1008         irg_walk_graph(irg, NULL, do_lftr, env);
1009 }
1010 #endif
1011
1012 /**
1013  * Pre-walker: set all node links to NULL and fix the
1014  * block of Proj nodes.
1015  */
1016 static void clear_and_fix(ir_node *irn, void *env)
1017 {
1018         set_irn_link(irn, NULL);
1019
1020         if (is_Proj(irn)) {
1021                 ir_node *pred = get_Proj_pred(irn);
1022                 set_irn_n(irn, -1, get_irn_n(pred, -1));
1023         }
1024 }
1025
1026 /* Performs Operator Strength Reduction for the passed graph. */
1027 void opt_osr(ir_graph *irg, unsigned flags) {
1028         iv_env   env;
1029         ir_graph *rem;
1030
1031         if (! get_opt_strength_red()) {
1032                 /* only kill Phi cycles  */
1033                 remove_phi_cycles(irg);
1034                 return;
1035         }
1036
1037         rem = current_ir_graph;
1038         current_ir_graph = irg;
1039
1040         FIRM_DBG_REGISTER(dbg, "firm.opt.osr");
1041
1042         DB((dbg, LEVEL_1, "Doing Operator Strength Reduction for %+F\n", irg));
1043
1044         obstack_init(&env.obst);
1045         env.stack         = NEW_ARR_F(ir_node *, 128);
1046         env.tos           = 0;
1047         env.nextDFSnum    = 0;
1048         env.POnum         = 0;
1049         env.quad_map      = new_set(quad_cmp, 64);
1050         env.lftr_edges    = new_set(LFTR_cmp, 64);
1051         env.replaced      = 0;
1052         env.lftr_replaced = 0;
1053         env.flags         = flags;
1054         env.process_scc   = process_scc;
1055
1056         /* Clear all links and move Proj nodes into the
1057            the same block as it's predecessors.
1058            This can improve the placement of new nodes.
1059          */
1060         irg_walk_graph(irg, NULL, clear_and_fix, NULL);
1061
1062         /* we need dominance */
1063         assure_doms(irg);
1064         assure_irg_outs(irg);
1065
1066         /* calculate the post order number for blocks. */
1067         irg_out_block_walk(get_irg_start_block(irg), NULL, assign_po, &env);
1068
1069         /* calculate the SCC's and drive OSR. */
1070         do_dfs(irg, &env);
1071
1072         if (env.replaced) {
1073                 /* try linear function test replacements */
1074                 //lftr(irg, &env);
1075
1076                 set_irg_outs_inconsistent(irg);
1077                 DB((dbg, LEVEL_1, "Replacements: %u + %u (lftr)\n\n", env.replaced, env.lftr_replaced));
1078         }
1079
1080         del_set(env.lftr_edges);
1081         del_set(env.quad_map);
1082         DEL_ARR_F(env.stack);
1083         obstack_free(&env.obst, NULL);
1084
1085         current_ir_graph = rem;
1086 }
1087
1088 /* Remove any Phi cycles with only one real input. */
1089 void remove_phi_cycles(ir_graph *irg) {
1090         iv_env   env;
1091         ir_graph *rem;
1092
1093         rem = current_ir_graph;
1094         current_ir_graph = irg;
1095
1096         FIRM_DBG_REGISTER(dbg, "firm.opt.remove_phi");
1097
1098         DB((dbg, LEVEL_1, "Doing Phi cycle removement for %+F\n", irg));
1099
1100         obstack_init(&env.obst);
1101         env.stack         = NEW_ARR_F(ir_node *, 128);
1102         env.tos           = 0;
1103         env.nextDFSnum    = 0;
1104         env.POnum         = 0;
1105         env.quad_map      = NULL;
1106         env.lftr_edges    = NULL;
1107         env.replaced      = 0;
1108         env.lftr_replaced = 0;
1109         env.flags         = 0;
1110         env.process_scc   = process_phi_only_scc;
1111
1112         /* Clear all links and move Proj nodes into the
1113            the same block as it's predecessors.
1114            This can improve the placement of new nodes.
1115          */
1116         irg_walk_graph(irg, NULL, clear_and_fix, NULL);
1117
1118         /* we need dominance */
1119         assure_irg_outs(irg);
1120
1121         /* calculate the post order number for blocks. */
1122         irg_out_block_walk(get_irg_start_block(irg), NULL, assign_po, &env);
1123
1124         /* calculate the SCC's and drive OSR. */
1125         do_dfs(irg, &env);
1126
1127         if (env.replaced) {
1128                 set_irg_outs_inconsistent(irg);
1129                 DB((dbg, LEVEL_1, "remove_phi_cycles: %u Cycles removed\n\n", env.replaced));
1130         }
1131
1132         DEL_ARR_F(env.stack);
1133         obstack_free(&env.obst, NULL);
1134
1135         current_ir_graph = rem;
1136 }