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

   1 /*
   2  * This file is part of libFirm.
   3  * Copyright (C) 2012 University of Karlsruhe.
   4  */
   5
   6 /**
   7  * @file
   8  * @brief   Operator Strength Reduction.
   9  * @date    12.5.2006
  10  * @author  Michael Beck
  11  * @brief
  12  *  Implementation of the Operator Strength Reduction algorithm
  13  *  by Keith D. Cooper, L. Taylor Simpson, Christopher A. Vick.
  14  *  Extended version.
  15  */
  16 #include "config.h"
  17
  18 #include "adt/pdeq.h"
  19 #include "iroptimize.h"
  20 #include "irgraph.h"
  21 #include "ircons.h"
  22 #include "irop_t.h"
  23 #include "irdom.h"
  24 #include "irgmod.h"
  25 #include "irflag_t.h"
  26 #include "irgwalk.h"
  27 #include "irouts.h"
  28 #include "iredges.h"
  29 #include "debug.h"
  30 #include "obst.h"
  31 #include "set.h"
  32 #include "tv.h"
  33 #include "hashptr.h"
  34 #include "util.h"
  35 #include "irtools.h"
  36 #include "irloop_t.h"
  37 #include "array.h"
  38 #include "firmstat_t.h"
  39 #include "error.h"
  40 #include "irpass_t.h"
  41
  42 /** The debug handle. */
  43 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
  44
  45 /** A scc. */
  46 typedef struct scc {
  47         ir_node   *head; /**< the head of the list */
  48         ir_tarval *init; /**< the init value iff only one exists. */
  49         ir_tarval *incr; /**< the induction variable increment if only a single const exists. */
  50         unsigned   code; /**< == iro_Add if +incr, iro_Sub if -incr, 0 if not analysed, iro_Bad else */
  51 } scc;
  52
  53 /** A node entry */
  54 typedef struct node_entry {
  55         unsigned DFSnum;    /**< the DFS number of this node */
  56         unsigned low;       /**< the low number of this node */
  57         ir_node  *header;   /**< the header of this node */
  58         int      in_stack;  /**< flag, set if the node is on the stack */
  59         ir_node  *next;     /**< link to the next node the the same scc */
  60         scc      *pscc;     /**< the scc of this node */
  61         unsigned POnum;     /**< the post order number for blocks */
  62 } node_entry;
  63
  64 /** The environment. */
  65 typedef struct iv_env {
  66         struct obstack obst;    /**< an obstack for allocations */
  67         ir_node  **stack;       /**< the node stack */
  68         size_t   tos;           /**< tos index */
  69         unsigned nextDFSnum;    /**< the current DFS number */
  70         unsigned POnum;         /**< current post order number */
  71         set      *quad_map;     /**< a map from (op, iv, rc) to node */
  72         set      *lftr_edges;   /**< the set of lftr edges */
  73         unsigned replaced;      /**< number of replaced ops */
  74         unsigned lftr_replaced; /**< number of applied linear function test replacements */
  75         unsigned osr_flags;     /**< additional flags steering the transformation */
  76         unsigned need_postpass; /**< set, if a post pass is needed to fix Add and Sub nodes */
  77         /** Function called to process a SCC. */
  78         void (*process_scc)(scc *pscc, struct iv_env *env);
  79 } iv_env;
  80
  81 /**
  82  * An entry in the (op, node, node) -> node map.
  83  */
  84 typedef struct quadruple_t {
  85         unsigned   code; /**< the opcode of the reduced operation */
  86         ir_node   *op1;  /**< the first operand the reduced operation */
  87         ir_node   *op2;  /**< the second operand of the reduced operation */
  88
  89         ir_node   *res; /**< the reduced operation */
  90 } quadruple_t;
  91
  92 /**
  93  * A LFTR edge.
  94  */
  95 typedef struct LFTR_edge {
  96         ir_node   *src;   /**< the source node */
  97         ir_node   *dst;   /**< the destination node */
  98         unsigned  code;   /**< the opcode that must be applied */
  99         ir_node   *rc;    /**< the region const that must be applied */
 100 } LFTR_edge;
 101
 102 /* forward */
 103 static ir_node *reduce(ir_node *orig, ir_node *iv, ir_node *rc, iv_env *env);
 104
 105 /**
 106  * Compare two LFTR edges.
 107  */
 108 static int LFTR_cmp(const void *e1, const void *e2, size_t size)
 109 {
 110         const LFTR_edge *l1 = (const LFTR_edge*)e1;
 111         const LFTR_edge *l2 = (const LFTR_edge*)e2;
 112         (void) size;
 113
 114         return l1->src != l2->src;
 115 }
 116
 117 /**
 118  * Find a LFTR edge.
 119  *
 120  * @param src  the source node of the transition
 121  */
 122 static LFTR_edge *LFTR_find(ir_node *src, iv_env *env)
 123 {
 124         LFTR_edge key;
 125
 126         key.src  = src;
 127
 128         return set_find(LFTR_edge, env->lftr_edges, &key, sizeof(key), hash_ptr(src));
 129 }
 130
 131 /**
 132  * Add a LFTR edge.
 133  *
 134  * @param src   the source node of the edge
 135  * @param dst   the destination node of the edge
 136  * @param code  the opcode of the transformed transition
 137  * @param rc    the region const used in the transition
 138  * @param env   the environment
 139  */
 140 static void LFTR_add(ir_node *src, ir_node *dst, unsigned code, ir_node *rc, iv_env *env)
 141 {
 142         LFTR_edge key;
 143
 144         key.src  = src;
 145         key.dst  = dst;
 146         key.code = code;
 147         key.rc   = rc;
 148
 149         /*
 150          * There might be more than one edge here. This is rather bad
 151          * because we currently store only one.
 152          */
 153         (void)set_insert(LFTR_edge, env->lftr_edges, &key, sizeof(key), hash_ptr(src));
 154 }
 155
 156 /**
 157  * Gets the node_entry of a node.
 158  *
 159  * @param irn  the node
 160  * @param env  the environment
 161  */
 162 static node_entry *get_irn_ne(ir_node *irn, iv_env *env)
 163 {
 164         node_entry *e = (node_entry*)get_irn_link(irn);
 165
 166         if (e == NULL) {
 167                 e = OALLOCZ(&env->obst, node_entry);
 168                 set_irn_link(irn, e);
 169         }
 170         return e;
 171 }
 172
 173 /**
 174  * Gets the scc from an induction variable.
 175  *
 176  * @param iv   any node of the induction variable
 177  * @param env  the environment
 178  */
 179 static scc *get_iv_scc(ir_node *iv, iv_env *env)
 180 {
 181         node_entry *e = get_irn_ne(iv, env);
 182         return e->pscc;
 183 }
 184
 185 /**
 186  * Check if irn is an IV.
 187  *
 188  * @param irn  the node to check
 189  * @param env  the environment
 190  *
 191  * @returns the header if it is one, NULL else
 192  */
 193 static ir_node *is_iv(ir_node *irn, iv_env *env)
 194 {
 195         return get_irn_ne(irn, env)->header;
 196 }
 197
 198 /**
 199  * Check if irn is a region constant.
 200  * The block or irn must strictly dominate the header block.
 201  *
 202  * @param irn           the node to check
 203  * @param header_block  the header block of the induction variable
 204  */
 205 static int is_rc(ir_node *irn, ir_node *header_block)
 206 {
 207         ir_node *block = get_nodes_block(irn);
 208
 209         return (block != header_block) && block_dominates(block, header_block);
 210 }
 211
 212 /**
 213  * Set compare function for the quad set.
 214  */
 215 static int quad_cmp(const void *e1, const void *e2, size_t size)
 216 {
 217         const quadruple_t *c1 = (const quadruple_t*)e1;
 218         const quadruple_t *c2 = (const quadruple_t*)e2;
 219         (void) size;
 220
 221         return c1->code != c2->code || c1->op1 != c2->op1 || c1->op2 != c2->op2;
 222 }
 223
 224 /**
 225  * Check if an reduced operation was already calculated.
 226  *
 227  * @param code  the opcode of the operation
 228  * @param op1   the first operand of the operation
 229  * @param op2   the second operand of the operation
 230  * @param env   the environment
 231  *
 232  * @return the already reduced node or NULL if this operation is not yet reduced
 233  */
 234 static ir_node *search(unsigned code, ir_node *op1, ir_node *op2, iv_env *env)
 235 {
 236         quadruple_t key, *entry;
 237
 238         key.code = code;
 239         key.op1 = op1;
 240         key.op2 = op2;
 241
 242         entry = set_find(quadruple_t, env->quad_map, &key, sizeof(key), (code * 9) ^ hash_ptr(op1) ^ hash_ptr(op2));
 243         if (entry)
 244                 return entry->res;
 245         return NULL;
 246 }
 247
 248 /**
 249  * Add an reduced operation.
 250  *
 251  * @param code    the opcode of the operation
 252  * @param op1     the first operand of the operation
 253  * @param op2     the second operand of the operation
 254  * @param result  the result of the reduced operation
 255  * @param env     the environment
 256  */
 257 static void add(unsigned code, ir_node *op1, ir_node *op2, ir_node *result, iv_env *env)
 258 {
 259         quadruple_t key;
 260
 261         key.code = code;
 262         key.op1  = op1;
 263         key.op2  = op2;
 264         key.res  = result;
 265
 266         (void)set_insert(quadruple_t, env->quad_map, &key, sizeof(key), (code * 9) ^ hash_ptr(op1) ^ hash_ptr(op2));
 267 }
 268
 269 /**
 270  * Find a location where to place a bin-op whose operands are in
 271  * block1 and block2.
 272  *
 273  * @param block1  the block of the first operand
 274  * @param block2  the block of the second operand
 275  *
 276  * Note that we know here that such a place must exists. Moreover, this means
 277  * that either block1 dominates block2 or vice versa. So, just return
 278  * the "smaller" one.
 279  */
 280 static ir_node *find_location(ir_node *block1, ir_node *block2)
 281 {
 282         if (block_dominates(block1, block2))
 283                 return block2;
 284         assert(block_dominates(block2, block1));
 285         return block1;
 286 }
 287
 288 /**
 289  * Create a node that executes an op1 code op1 operation.
 290  *
 291  * @param code   the opcode to execute
 292  * @param db     debug info to add to the new node
 293  * @param op1    the first operand
 294  * @param op2    the second operand
 295  * @param mode   the mode of the new operation
 296  *
 297  * @return the newly created node
 298  */
 299 static ir_node *do_apply(unsigned code, dbg_info *db, ir_node *op1, ir_node *op2, ir_mode *mode)
 300 {
 301         ir_node *result;
 302         ir_node *block = find_location(get_nodes_block(op1), get_nodes_block(op2));
 303
 304         switch (code) {
 305         case iro_Mul:
 306                 result = new_rd_Mul(db, block, op1, op2, mode);
 307                 break;
 308         case iro_Add:
 309                 result = new_rd_Add(db, block, op1, op2, mode);
 310                 break;
 311         case iro_Sub:
 312                 result = new_rd_Sub(db, block, op1, op2, mode);
 313                 break;
 314         default:
 315                 panic("Unsupported opcode");
 316         }
 317         return result;
 318 }
 319
 320 /**
 321  * The Apply operation.
 322  *
 323  * @param orig   the node that represent the original operation and determines
 324  *               the opcode, debug-info and mode of a newly created one
 325  * @param op1    the first operand
 326  * @param op2    the second operand
 327  * @param env    the environment
 328  *
 329  * @return the newly created node
 330  */
 331 static ir_node *apply(ir_node *header, ir_node *orig, ir_node *op1, ir_node *op2, iv_env *env)
 332 {
 333         unsigned code = get_irn_opcode(orig);
 334         ir_node *result = search(code, op1, op2, env);
 335
 336         if (result == NULL) {
 337                 dbg_info *db = get_irn_dbg_info(orig);
 338                 ir_node *op1_header = get_irn_ne(op1, env)->header;
 339                 ir_node *op2_header = get_irn_ne(op2, env)->header;
 340
 341                 if (op1_header == header && is_rc(op2, op1_header)) {
 342                         result = reduce(orig, op1, op2, env);
 343                 }
 344                 else if (op2_header == header && is_rc(op1, op2_header)) {
 345                         result = reduce(orig, op2, op1, env);
 346                 }
 347                 else {
 348                         result = do_apply(code, db, op1, op2, get_irn_mode(orig));
 349                         get_irn_ne(result, env)->header = NULL;
 350                 }
 351         }
 352         return result;
 353 }
 354
 355 /**
 356  * The Reduce operation.
 357  *
 358  * @param orig   the node that represent the original operation and determines
 359  *               the opcode, debug-info and mode of a newly created one
 360  * @param iv     the induction variable
 361  * @param rc     the region constant
 362  * @param env    the environment
 363  *
 364  * @return the reduced node
 365  */
 366 static ir_node *reduce(ir_node *orig, ir_node *iv, ir_node *rc, iv_env *env)
 367 {
 368         unsigned code = get_irn_opcode(orig);
 369         ir_node *result = search(code, iv, rc, env);
 370
 371         /* check if we have already done this operation on the iv */
 372         if (result == NULL) {
 373                 node_entry *e, *iv_e;
 374                 int i;
 375                 ir_mode *mode = get_irn_mode(orig);
 376
 377                 result = exact_copy(iv);
 378
 379                 if (get_irn_mode(result) != mode) {
 380                         /*
 381                          * Beware: we must always create a new induction variable with the same mode
 382                          * as the node we are replacing. Especially this means the mode might be changed
 383                          * from P to I and back. This is always possible, because we have only Phi, Add
 384                          * and Sub nodes.
 385                          * However, this might lead to AddIs(Iu,Is) which we must fix. The best way to do this
 386                          * seems to be a post-pass, or we might end with useless Conv's.
 387                          */
 388                         set_irn_mode(result, mode);
 389                         env->need_postpass = 1;
 390                 }
 391                 add(code, iv, rc, result, env);
 392                 DB((dbg, LEVEL_3, "   Created new %+F for %+F (%s %+F)\n", result, iv,
 393                         get_irn_opname(orig), rc));
 394
 395                 iv_e = get_irn_ne(iv, env);
 396                 e    = get_irn_ne(result, env);
 397                 e->header = iv_e->header;
 398
 399                 /* create the LFTR edge */
 400                 LFTR_add(iv, result, code, rc, env);
 401
 402                 for (i = get_irn_arity(result) - 1; i >= 0; --i) {
 403                         ir_node *o = get_irn_n(result, i);
 404
 405                         e = get_irn_ne(o, env);
 406                         if (e->header == iv_e->header)
 407                                 o = reduce(orig, o, rc, env);
 408                         else if (is_Phi(result) || code == iro_Mul)
 409                                 o = apply(iv_e->header, orig, o, rc, env);
 410                         set_irn_n(result, i, o);
 411                 }
 412         } else {
 413                 DB((dbg, LEVEL_3, "   Already Created %+F for %+F (%s %+F)\n", result, iv,
 414                         get_irn_opname(orig), rc));
 415         }
 416         return result;
 417 }
 418
 419 /**
 420  * Update the scc for a newly created IV.
 421  */
 422 static void update_scc(ir_node *iv, node_entry *e, iv_env *env)
 423 {
 424         scc     *pscc   = e->pscc;
 425         ir_node *header = e->header;
 426         waitq    *wq = new_waitq();
 427
 428         DB((dbg, LEVEL_2, "  Creating SCC for new an induction variable:\n  "));
 429         pscc->head = NULL;
 430         waitq_put(wq, iv);
 431         do {
 432                 ir_node    *irn = (ir_node*)waitq_get(wq);
 433                 node_entry *ne  = get_irn_ne(irn, env);
 434                 int        i;
 435
 436                 ne->pscc   = pscc;
 437                 ne->next   = pscc->head;
 438                 pscc->head = irn;
 439                 DB((dbg, LEVEL_2, " %+F,", irn));
 440
 441                 for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
 442                         ir_node    *pred = get_irn_n(irn, i);
 443                         node_entry *pe   = get_irn_ne(pred, env);
 444
 445                         if (pe->header == header && pe->pscc == NULL) {
 446                                 /* set the pscc here to ensure that the node is NOT enqueued another time */
 447                                 pe->pscc = pscc;
 448                                 waitq_put(wq, pred);
 449                         }
 450                 }
 451         } while (! waitq_empty(wq));
 452         del_waitq(wq);
 453         DB((dbg, LEVEL_2, "\n"));
 454 }
 455
 456 /**
 457  * The Replace operation. We found a node representing iv (+,-,*) rc
 458  * that can be removed by replacing the induction variable iv by a new
 459  * one that 'applies' the operation 'irn'.
 460  *
 461  * @param irn   the node that will be replaced
 462  * @param iv    the induction variable
 463  * @param rc    the region constant
 464  * @param env   the environment
 465  */
 466 static int replace(ir_node *irn, ir_node *iv, ir_node *rc, iv_env *env)
 467 {
 468         ir_node *result;
 469
 470         DB((dbg, LEVEL_2, "  Replacing %+F\n", irn));
 471
 472         result = reduce(irn, iv, rc, env);
 473         if (result != irn) {
 474                 node_entry *e;
 475
 476                 hook_strength_red(get_irn_irg(irn), irn);
 477                 exchange(irn, result);
 478                 e = get_irn_ne(result, env);
 479                 if (e->pscc == NULL) {
 480                         e->pscc = OALLOCZ(&env->obst, scc);
 481                         update_scc(result, e, env);
 482                 }
 483                 ++env->replaced;
 484                 return 1;
 485         }
 486         return 0;
 487 }
 488
 489 /**
 490  * Check if an IV represents a counter with constant limits.
 491  *
 492  * @param iv    any node of the induction variable
 493  * @param env   the environment
 494  */
 495 static int is_counter_iv(ir_node *iv, iv_env *env)
 496 {
 497         node_entry *e         = get_irn_ne(iv, env);
 498         scc        *pscc      = e->pscc;
 499         ir_node    *have_init = NULL;
 500         ir_node    *have_incr = NULL;
 501         ir_opcode  code       = iro_Bad;
 502         ir_node    *irn;
 503
 504         if (pscc->code != 0) {
 505                 /* already analysed */
 506                 return pscc->code != iro_Bad;
 507         }
 508
 509         pscc->code = iro_Bad;
 510         for (irn = pscc->head; irn != NULL; irn = e->next) {
 511                 if (is_Add(irn)) {
 512                         if (have_incr != NULL)
 513                                 return 0;
 514
 515                         have_incr = get_Add_right(irn);
 516                         if (! is_Const(have_incr)) {
 517                                 have_incr = get_Add_left(irn);
 518                                 if (! is_Const(have_incr))
 519                                         return 0;
 520                         }
 521                         code = iro_Add;
 522                 } else if (is_Sub(irn)) {
 523                         if (have_incr != NULL)
 524                                 return 0;
 525
 526                         have_incr = get_Sub_right(irn);
 527                         if (! is_Const(have_incr))
 528                                 return 0;
 529                         code = iro_Sub;
 530                 } else if (is_Phi(irn)) {
 531                         int i;
 532
 533                         for (i = get_Phi_n_preds(irn) - 1; i >= 0; --i) {
 534                                 ir_node    *pred = get_Phi_pred(irn, i);
 535                                 node_entry *ne   = get_irn_ne(pred, env);
 536
 537                                 if (ne->header == e->header)
 538                                         continue;
 539                                 if (have_init != NULL)
 540                                         return 0;
 541                                 have_init = pred;
 542                                 if (! is_Const(pred))
 543                                         return 0;
 544                         }
 545                 } else
 546                         return 0;
 547                 e = get_irn_ne(irn, env);
 548         }
 549         pscc->init = get_Const_tarval(have_init);
 550         pscc->incr = get_Const_tarval(have_incr);
 551         pscc->code = code;
 552         return code != iro_Bad;
 553 }
 554
 555 /**
 556  * Check the users of an induction variable for register pressure.
 557  *
 558  * @param iv    any node of the induction variable
 559  * @param env   the environment
 560  *
 561  * @return non-zero if the register pressure is estimated
 562  *         to not increase, zero else
 563  */
 564 static int check_users_for_reg_pressure(ir_node *iv, iv_env *env)
 565 {
 566         ir_node    *irn;
 567         ir_node    *have_user = NULL;
 568         ir_node    *have_cmp  = NULL;
 569         node_entry *e         = get_irn_ne(iv, env);
 570         scc        *pscc      = e->pscc;
 571
 572         for (irn = pscc->head; irn != NULL; irn = e->next) {
 573                 foreach_out_edge(irn, edge) {
 574                         ir_node    *user = get_edge_src_irn(edge);
 575                         node_entry *ne = get_irn_ne(user, env);
 576
 577                         if (e->header == ne->header) {
 578                                 /* found user from the same IV */
 579                                 continue;
 580                         }
 581                         if (is_Cmp(user)) {
 582                                 if (have_cmp != NULL) {
 583                                         /* more than one cmp, for now end here */
 584                                         return 0;
 585                                 }
 586                                 have_cmp = user;
 587                         } else {
 588                                 /* user is a real user of the IV */
 589                                 if (have_user != NULL) {
 590                                         /* found the second user */
 591                                         return 0;
 592                                 }
 593                                 have_user = user;
 594                         }
 595                 }
 596                 e = get_irn_ne(irn, env);
 597         }
 598
 599         if (have_user == NULL) {
 600                 /* no user, ignore */
 601                 return 1;
 602         }
 603
 604         if (have_cmp == NULL) {
 605                 /* fine, only one user, try to reduce */
 606                 return 1;
 607         }
 608         /*
 609          * We found one user AND at least one cmp.
 610          * We should check here if we can transform the Cmp.
 611          *
 612          * For now our capabilities for doing linear function test
 613          * are limited, so check if the iv has the right form: Only ONE
 614          * Phi, only one Add/Sub with a Const.
 615          */
 616         if (! is_counter_iv(iv, env))
 617                 return 0;
 618
 619         /*
 620          * Ok, we have only one increment AND it is a Const, we might be able
 621          * to do a linear function test replacement, so go on.
 622          */
 623         return 1;
 624 }
 625
 626 /**
 627  * Check if a node can be replaced (+, -, *).
 628  *
 629  * @param irn   the node to check
 630  * @param env   the environment
 631  *
 632  * @return non-zero if irn should be Replace'd
 633  */
 634 static int check_replace(ir_node *irn, iv_env *env)
 635 {
 636         ir_node   *left, *right, *iv, *rc;
 637         ir_op     *op  = get_irn_op(irn);
 638         unsigned  code = get_op_code(op);
 639         ir_node   *liv, *riv;
 640
 641         switch (code) {
 642         case iro_Mul:
 643         case iro_Add:
 644         case iro_Sub:
 645                 iv = rc = NULL;
 646
 647                 left  = get_binop_left(irn);
 648                 right = get_binop_right(irn);
 649
 650                 liv = is_iv(left, env);
 651                 riv = is_iv(right, env);
 652                 if (liv && is_rc(right, liv)) {
 653                         iv = left; rc = right;
 654                 }
 655                 else if (riv && is_op_commutative(op) &&
 656                                     is_rc(left, riv)) {
 657                         iv = right; rc = left;
 658                 }
 659
 660                 if (iv) {
 661                         if (env->osr_flags & osr_flag_keep_reg_pressure) {
 662                                 if (! check_users_for_reg_pressure(iv, env))
 663                                         return 0;
 664                         }
 665                         return replace(irn, iv, rc, env);
 666                 }
 667                 break;
 668         default:
 669                 break;
 670         }
 671         return 0;
 672 }
 673
 674 /**
 675  * Check which SCC's are induction variables.
 676  *
 677  * @param pscc  a SCC
 678  * @param env   the environment
 679  */
 680 static void classify_iv(scc *pscc, iv_env *env)
 681 {
 682         ir_node *irn, *next, *header = NULL;
 683         node_entry *b, *h = NULL;
 684         int j, only_phi, num_outside;
 685         ir_node *out_rc;
 686
 687         /* find the header block for this scc */
 688         for (irn = pscc->head; irn; irn = next) {
 689                 node_entry *e = (node_entry*)get_irn_link(irn);
 690                 ir_node *block = get_nodes_block(irn);
 691
 692                 next = e->next;
 693                 b = get_irn_ne(block, env);
 694
 695                 if (header) {
 696                         if (h->POnum < b->POnum) {
 697                                 header = block;
 698                                 h      = b;
 699                         }
 700                 }
 701                 else {
 702                         header = block;
 703                         h      = b;
 704                 }
 705         }
 706
 707         /* check if this scc contains only Phi, Add or Sub nodes */
 708         only_phi    = 1;
 709         num_outside = 0;
 710         out_rc      = NULL;
 711         for (irn = pscc->head; irn; irn = next) {
 712                 node_entry *e = get_irn_ne(irn, env);
 713
 714                 next = e->next;
 715                 switch (get_irn_opcode(irn)) {
 716                 case iro_Sub:
 717                         only_phi = 0;
 718                         {
 719                                 ir_node    *left        = get_Sub_left(irn);
 720                                 node_entry *left_entry  = get_irn_ne(left, env);
 721                                 ir_node    *right       = get_Sub_right(irn);
 722                                 node_entry *right_entry = get_irn_ne(right, env);
 723
 724                                 if (left_entry->pscc != e->pscc ||
 725                                     (right_entry->pscc != e->pscc && !is_rc(right, header))) {
 726                                         /*
 727                                          * Not an induction variable.
 728                                          * Region constant are only allowed on right hand side.
 729                                          */
 730                                         goto fail;
 731                                 }
 732                         }
 733                         break;
 734
 735                 case iro_Add:
 736                         only_phi = 0;
 737                         /* fall through */
 738                 case iro_Phi:
 739                         for (j = get_irn_arity(irn) - 1; j >= 0; --j) {
 740                                 ir_node *pred  = get_irn_n(irn, j);
 741                                 node_entry *pe = get_irn_ne(pred, env);
 742
 743                                 if (pe->pscc != e->pscc) {
 744                                         /* not in the same SCC, must be a region const */
 745                                         if (! is_rc(pred, header)) {
 746                                                 /* not an induction variable */
 747                                                 goto fail;
 748                                         }
 749                                         if (! out_rc) {
 750                                                 out_rc = pred;
 751                                                 ++num_outside;
 752                                         } else if (out_rc != pred) {
 753                                                 ++num_outside;
 754                                         }
 755                                 }
 756                         }
 757                         break;
 758                 default:
 759                         /* not an induction variable */
 760                         goto fail;
 761                 }
 762         }
 763         /* found an induction variable */
 764         DB((dbg, LEVEL_2, "  Found an induction variable:\n  "));
 765         if (only_phi && num_outside == 1) {
 766                 /* a phi cycle with only one real predecessor can be collapsed */
 767                 DB((dbg, LEVEL_2, "  Found an USELESS Phi cycle:\n  "));
 768
 769                 for (irn = pscc->head; irn; irn = next) {
 770                         node_entry *e = get_irn_ne(irn, env);
 771                         next = e->next;
 772                         e->header = NULL;
 773                         exchange(irn, out_rc);
 774                 }
 775                 ++env->replaced;
 776                 return;
 777         }
 778
 779         /* set the header for every node in this scc */
 780         for (irn = pscc->head; irn; irn = next) {
 781                 node_entry *e = get_irn_ne(irn, env);
 782                 e->header = header;
 783                 next = e->next;
 784                 DB((dbg, LEVEL_2, " %+F,", irn));
 785         }
 786         DB((dbg, LEVEL_2, "\n"));
 787         return;
 788
 789 fail:
 790         for (irn = pscc->head; irn; irn = next) {
 791                 node_entry *e = get_irn_ne(irn, env);
 792
 793                 next = e->next;
 794                 e->header = NULL;
 795         }
 796 }
 797
 798 /**
 799  * Process an SCC for the operator strength reduction.
 800  *
 801  * @param pscc  the SCC
 802  * @param env   the environment
 803  */
 804 static void process_scc(scc *pscc, iv_env *env)
 805 {
 806         ir_node *head = pscc->head;
 807         node_entry *e = (node_entry*)get_irn_link(head);
 808
 809 #ifdef DEBUG_libfirm
 810         {
 811                 ir_node *irn, *next;
 812
 813                 DB((dbg, LEVEL_4, " SCC at %p:\n ", pscc));
 814                 for (irn = pscc->head; irn != NULL; irn = next) {
 815                         node_entry *e = (node_entry*)get_irn_link(irn);
 816
 817                         next = e->next;
 818
 819                         DB((dbg, LEVEL_4, " %+F,", irn));
 820                 }
 821                 DB((dbg, LEVEL_4, "\n"));
 822         }
 823 #endif
 824
 825         if (e->next == NULL) {
 826                 /* this SCC has only a single member */
 827                 check_replace(head, env);
 828         } else {
 829                 classify_iv(pscc, env);
 830         }
 831 }
 832
 833 /**
 834  * If an SCC is a Phi only cycle, remove it.
 835  *
 836  * @param pscc  an SCC that consists of Phi nodes only
 837  * @param env   the environment
 838  */
 839 static void remove_phi_cycle(scc *pscc, iv_env *env)
 840 {
 841         ir_node *irn, *next;
 842         int j;
 843         ir_node *out_rc;
 844
 845         /* check if this scc contains only Phi nodes */
 846         out_rc      = NULL;
 847         for (irn = pscc->head; irn; irn = next) {
 848                 node_entry *e = get_irn_ne(irn, env);
 849
 850                 next = e->next;
 851                 if (! is_Phi(irn))
 852                         return;
 853
 854                 for (j = get_irn_arity(irn) - 1; j >= 0; --j) {
 855                         ir_node *pred  = get_irn_n(irn, j);
 856                         node_entry *pe = get_irn_ne(pred, env);
 857
 858                         if (pe->pscc != e->pscc) {
 859                                 /* not in the same SCC, must be the only input */
 860                                 if (! out_rc) {
 861                                         out_rc = pred;
 862                                 } else if (out_rc != pred) {
 863                                         return;
 864                                 }
 865                         }
 866                 }
 867         }
 868         /* found a Phi cycle */
 869         DB((dbg, LEVEL_2, "  Found an USELESS Phi cycle:\n  "));
 870
 871         for (irn = pscc->head; irn; irn = next) {
 872                 node_entry *e = get_irn_ne(irn, env);
 873                 next = e->next;
 874                 e->header = NULL;
 875                 exchange(irn, out_rc);
 876         }
 877         ++env->replaced;
 878 }
 879
 880 /**
 881  * Process a SCC for the Phi cycle remove.
 882  *
 883  * @param pscc  the SCC
 884  * @param env   the environment
 885  */
 886 static void process_phi_only_scc(scc *pscc, iv_env *env)
 887 {
 888         ir_node *head = pscc->head;
 889         node_entry *e = (node_entry*)get_irn_link(head);
 890
 891 #ifdef DEBUG_libfirm
 892         {
 893                 ir_node *irn, *next;
 894
 895                 DB((dbg, LEVEL_4, " SCC at %p:\n ", pscc));
 896                 for (irn = pscc->head; irn; irn = next) {
 897                         node_entry *e = (node_entry*)get_irn_link(irn);
 898
 899                         next = e->next;
 900
 901                         DB((dbg, LEVEL_4, " %+F,", irn));
 902                 }
 903                 DB((dbg, LEVEL_4, "\n"));
 904         }
 905 #endif
 906
 907         if (e->next != NULL)
 908                 remove_phi_cycle(pscc, env);
 909 }
 910
 911
 912 /**
 913  * Push a node onto the stack.
 914  *
 915  * @param env   the environment
 916  * @param n     the node to push
 917  */
 918 static void push(iv_env *env, ir_node *n)
 919 {
 920         node_entry *e;
 921
 922         if (env->tos == ARR_LEN(env->stack)) {
 923                 size_t nlen = ARR_LEN(env->stack) * 2;
 924                 ARR_RESIZE(ir_node *, env->stack, nlen);
 925         }
 926         env->stack[env->tos++] = n;
 927         e = get_irn_ne(n, env);
 928         e->in_stack = 1;
 929 }
 930
 931 /**
 932  * Pop a node from the stack.
 933  *
 934  * @param env   the environment
 935  *
 936  * @return  The topmost node
 937  */
 938 static ir_node *pop(iv_env *env)
 939 {
 940         ir_node *n = env->stack[--env->tos];
 941         node_entry *e = get_irn_ne(n, env);
 942
 943         e->in_stack = 0;
 944         return n;
 945 }
 946
 947 /**
 948  * Do Tarjan's SCC algorithm and drive OSR.
 949  *
 950  * @param irn  start at this node
 951  * @param env  the environment
 952  */
 953 static void dfs(ir_node *irn, iv_env *env)
 954 {
 955         int i, n;
 956         node_entry *node = get_irn_ne(irn, env);
 957
 958         mark_irn_visited(irn);
 959
 960         /* do not put blocks into the scc */
 961         if (is_Block(irn)) {
 962                 n = get_irn_arity(irn);
 963                 for (i = 0; i < n; ++i) {
 964                         ir_node *pred = get_irn_n(irn, i);
 965
 966                         if (!irn_visited(pred))
 967                                 dfs(pred, env);
 968                 }
 969         } else {
 970                 ir_node *block = get_nodes_block(irn);
 971
 972                 node->DFSnum = env->nextDFSnum++;
 973                 node->low    = node->DFSnum;
 974                 push(env, irn);
 975
 976                 /* handle the block */
 977                 if (!irn_visited(block))
 978                         dfs(block, env);
 979
 980                 n = get_irn_arity(irn);
 981                 for (i = 0; i < n; ++i) {
 982                         ir_node *pred = get_irn_n(irn, i);
 983                         node_entry *o = get_irn_ne(pred, env);
 984
 985                         if (!irn_visited(pred)) {
 986                                 dfs(pred, env);
 987                                 node->low = MIN(node->low, o->low);
 988                         }
 989                         if (o->DFSnum < node->DFSnum && o->in_stack)
 990                                 node->low = MIN(o->DFSnum, node->low);
 991                 }
 992                 if (node->low == node->DFSnum) {
 993                         scc *pscc = OALLOCZ(&env->obst, scc);
 994                         ir_node *x;
 995
 996                         do {
 997                                 node_entry *e;
 998
 999                                 x = pop(env);
1000                                 e = get_irn_ne(x, env);
1001                                 e->pscc    = pscc;
1002                                 e->next    = pscc->head;
1003                                 pscc->head = x;
1004                         } while (x != irn);
1005
1006                         env->process_scc(pscc, env);
1007                 }
1008         }
1009 }
1010
1011 /**
1012  * Do the DFS by starting at the End node of a graph.
1013  *
1014  * @param irg  the graph to process
1015  * @param env  the environment
1016  */
1017 static void do_dfs(ir_graph *irg, iv_env *env)
1018 {
1019         ir_node  *end = get_irg_end(irg);
1020         int i;
1021
1022         ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
1023
1024         inc_irg_visited(irg);
1025
1026         /* visit all visible nodes */
1027         dfs(end, env);
1028
1029         /* visit the keep-alives */
1030         for (i = get_End_n_keepalives(end) - 1; i >= 0; --i) {
1031                 ir_node *ka = get_End_keepalive(end, i);
1032
1033                 if (!irn_visited(ka))
1034                         dfs(ka, env);
1035         }
1036
1037         ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
1038 }
1039
1040 /**
1041  * Post-block-walker: assign the post-order number.
1042  */
1043 static void assign_po(ir_node *block, void *ctx)
1044 {
1045         iv_env *env = (iv_env*)ctx;
1046         node_entry *e = get_irn_ne(block, env);
1047
1048         e->POnum = env->POnum++;
1049 }
1050
1051 /**
1052  * Apply one LFTR edge operation.
1053  * Return NULL if the transformation cannot be done safely without
1054  * an Overflow.
1055  *
1056  * @param iv   the induction variable
1057  * @param rc   the constant that should be translated
1058  * @param e    the LFTR edge
1059  * @param env  the IV environment
1060  *
1061  * @return the translated region constant or NULL
1062  *         if the translation was not possible
1063  *
1064  * @note
1065  * In the current implementation only the last edge is stored, so
1066  * only one chain exists. That's why we might miss some opportunities.
1067  */
1068 static ir_node *applyOneEdge(ir_node *iv, ir_node *rc, LFTR_edge *e, iv_env *env)
1069 {
1070         if (env->osr_flags & osr_flag_lftr_with_ov_check) {
1071                 ir_tarval *tv_l, *tv_r, *tv, *tv_init, *tv_incr, *tv_end;
1072                 tarval_int_overflow_mode_t ovmode;
1073                 scc *pscc;
1074                 ir_graph *irg;
1075
1076                 if (! is_counter_iv(iv, env)) {
1077                         DB((dbg, LEVEL_4, " not counter IV"));
1078                         return NULL;
1079                 }
1080
1081                 /* overflow can only be decided for Consts */
1082                 if (! is_Const(e->rc)) {
1083                         if (e->code == iro_Add && mode_is_reference(get_irn_mode(e->rc))) {
1084                                 /* However we allow ONE Pointer Add, as pointer arithmetic with wrap
1085                                    around is undefined anyway */
1086                                 return do_apply(e->code, NULL, rc, e->rc, get_irn_mode(e->rc));
1087                         }
1088                         DB((dbg, LEVEL_4, " = UNKNOWN (%+F)", e->rc));
1089                         return NULL;
1090                 }
1091
1092                 tv_l = get_Const_tarval(rc);
1093                 tv_r = get_Const_tarval(e->rc);
1094
1095                 ovmode = tarval_get_integer_overflow_mode();
1096                 tarval_set_integer_overflow_mode(TV_OVERFLOW_BAD);
1097
1098                 pscc    = get_iv_scc(iv, env);
1099                 tv_incr = pscc->incr;
1100                 tv_init = pscc->init;
1101
1102                 /*
1103                  * Check that no overflow occurs:
1104                  * init must be transformed without overflow
1105                  * the new rc must be transformed without overflow
1106                  * rc +/- incr must be possible without overflow
1107                  */
1108                 switch (e->code) {
1109                 case iro_Mul:
1110                         tv      = tarval_mul(tv_l, tv_r);
1111                         tv_init = tarval_mul(tv_init, tv_r);
1112                         tv_incr = tarval_mul(tv_incr, tv_r);
1113                         DB((dbg, LEVEL_4, " * %+F", tv_r));
1114                         break;
1115                 case iro_Add:
1116                         tv      = tarval_add(tv_l, tv_r);
1117                         tv_init = tarval_add(tv_init, tv_r);
1118                         DB((dbg, LEVEL_4, " + %+F", tv_r));
1119                         break;
1120                 case iro_Sub:
1121                         tv      = tarval_sub(tv_l, tv_r, NULL);
1122                         tv_init = tarval_sub(tv_init, tv_r, NULL);
1123                         DB((dbg, LEVEL_4, " - %+F", tv_r));
1124                         break;
1125                 default:
1126                         panic("Unsupported opcode");
1127                 }
1128
1129                 if (tv == tarval_bad || tv_init == tarval_bad) {
1130                         tarval_set_integer_overflow_mode(ovmode);
1131                         DB((dbg, LEVEL_4, " = OVERFLOW"));
1132                         return NULL;
1133                 }
1134
1135                 if (pscc->code == iro_Add) {
1136                         tv_end = tarval_add(tv, tv_incr);
1137                 } else {
1138                         assert(pscc->code == iro_Sub);
1139                         tv_end = tarval_sub(tv, tv_incr, NULL);
1140                 }
1141
1142                 tarval_set_integer_overflow_mode(ovmode);
1143
1144                 if (tv_end == tarval_bad) {
1145                         DB((dbg, LEVEL_4, " = OVERFLOW"));
1146                         return NULL;
1147                 }
1148                 irg = get_irn_irg(iv);
1149                 return new_r_Const(irg, tv);
1150         }
1151         return do_apply(e->code, NULL, rc, e->rc, get_irn_mode(e->dst));
1152 }
1153
1154 /**
1155  * Applies the operations represented by the LFTR edges to a
1156  * region constant and returns the value.
1157  * Return NULL if the transformation cannot be done safely without
1158  * an Overflow.
1159  *
1160  * @param pIV  points to the IV node that starts the LFTR edge chain
1161  *             after translation points to the new IV
1162  * @param rc   the region constant that should be translated
1163  * @param env  the IV environment
1164  *
1165  * @return the translated region constant or NULL
1166  *         if the translation was not possible
1167  */
1168 static ir_node *applyEdges(ir_node **pIV, ir_node *rc, iv_env *env)
1169 {
1170         ir_node *iv = *pIV;
1171         if (env->osr_flags & osr_flag_lftr_with_ov_check) {
1172                 /* overflow can only be decided for Consts */
1173                 if (! is_counter_iv(iv, env)) {
1174                         DB((dbg, LEVEL_4, "not counter IV\n", rc));
1175                         return NULL;
1176                 }
1177                 if (! is_Const(rc)) {
1178                         DB((dbg, LEVEL_4, " = UNKNOWN (%+F)\n", rc));
1179                         return NULL;
1180                 }
1181                 DB((dbg, LEVEL_4, "%+F", get_Const_tarval(rc)));
1182         }
1183
1184         for (; rc;) {
1185                 LFTR_edge *e = LFTR_find(iv, env);
1186                 if (e != NULL) {
1187                         rc = applyOneEdge(iv, rc, e, env);
1188                         iv = e->dst;
1189                 } else
1190                         break;
1191         }
1192         DB((dbg, LEVEL_3, "\n"));
1193         *pIV = iv;
1194         return rc;
1195 }
1196
1197 /**
1198  * Walker, finds Cmp(iv, rc) or Cmp(rc, iv)
1199  * and tries to optimize them.
1200  */
1201 static void do_lftr(ir_node *cmp, void *ctx)
1202 {
1203         iv_env *env = (iv_env*)ctx;
1204         ir_node *left, *right, *liv, *riv;
1205         ir_node *iv, *rc;
1206         ir_node *nleft = NULL, *nright = NULL;
1207
1208         if (!is_Cmp(cmp))
1209                 return;
1210
1211         left  = get_Cmp_left(cmp);
1212         right = get_Cmp_right(cmp);
1213
1214         liv = is_iv(left, env);
1215         riv = is_iv(right, env);
1216         if (liv && is_rc(right, liv)) {
1217                 iv = left; rc = right;
1218
1219                 nright = applyEdges(&iv, rc, env);
1220                 nleft  = iv;
1221         }
1222         else if (riv && is_rc(left, riv)) {
1223                 iv = right; rc = left;
1224
1225                 nleft  = applyEdges(&iv, rc, env);
1226                 nright = iv;
1227         }
1228
1229         if (nleft && nright) {
1230                 DB((dbg, LEVEL_2, "  LFTR for %+F\n", cmp));
1231                 set_Cmp_left(cmp, nleft);
1232                 set_Cmp_right(cmp, nright);
1233                 ++env->lftr_replaced;
1234         }
1235 }
1236
1237 /**
1238  * do linear function test replacement.
1239  *
1240  * @param irg   the graph that should be optimized
1241  * @param env   the IV environment
1242  */
1243 static void lftr(ir_graph *irg, iv_env *env)
1244 {
1245         irg_walk_graph(irg, NULL, do_lftr, env);
1246 }
1247
1248 /* Remove any Phi cycles with only one real input. */
1249 void remove_phi_cycles(ir_graph *irg)
1250 {
1251         iv_env env;
1252
1253         assure_irg_properties(irg,
1254                 IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE
1255                 | IR_GRAPH_PROPERTY_CONSISTENT_OUTS
1256                 | IR_GRAPH_PROPERTY_CONSISTENT_OUT_EDGES);
1257
1258         FIRM_DBG_REGISTER(dbg, "firm.opt.remove_phi");
1259
1260         DB((dbg, LEVEL_1, "Doing Phi cycle removement for %+F\n", irg));
1261
1262         obstack_init(&env.obst);
1263         env.stack         = NEW_ARR_F(ir_node *, 128);
1264         env.tos           = 0;
1265         env.nextDFSnum    = 0;
1266         env.POnum         = 0;
1267         env.quad_map      = NULL;
1268         env.lftr_edges    = NULL;
1269         env.replaced      = 0;
1270         env.lftr_replaced = 0;
1271         env.osr_flags     = 0;
1272         env.need_postpass = 0;
1273         env.process_scc   = process_phi_only_scc;
1274
1275         /* Clear all links and move Proj nodes into the
1276          * the same block as their predecessors.
1277          * This can improve the placement of new nodes.
1278          */
1279         irg_walk_graph(irg, NULL, firm_clear_link, NULL);
1280
1281         /* calculate the post order number for blocks. */
1282         irg_out_block_walk(get_irg_start_block(irg), NULL, assign_po, &env);
1283
1284         /* calculate the SCC's and drive OSR. */
1285         ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
1286         do_dfs(irg, &env);
1287         ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
1288
1289         if (env.replaced) {
1290                 DB((dbg, LEVEL_1, "remove_phi_cycles: %u Cycles removed\n\n",
1291                     env.replaced));
1292         }
1293
1294         DEL_ARR_F(env.stack);
1295         obstack_free(&env.obst, NULL);
1296
1297         confirm_irg_properties(irg, IR_GRAPH_PROPERTIES_CONTROL_FLOW);
1298 }
1299
1300 ir_graph_pass_t *remove_phi_cycles_pass(const char *name)
1301 {
1302         return def_graph_pass(name ? name : "remove_phi_cycles", remove_phi_cycles);
1303 }
1304
1305 /**
1306  * Post-walker: fix Add and Sub nodes that where results of I<->P conversions.
1307  */
1308 static void fix_adds_and_subs(ir_node *irn, void *ctx)
1309 {
1310         (void) ctx;
1311
1312         if (is_Add(irn)) {
1313                 ir_mode *mode = get_irn_mode(irn);
1314
1315                 if (mode_is_int(mode)) {
1316                         ir_node *pred;
1317
1318                         pred = get_Add_left(irn);
1319                         if (get_irn_mode(pred) != mode) {
1320                                 ir_node *block = get_nodes_block(pred);
1321
1322                                 pred = new_r_Conv(block, pred, mode);
1323                                 set_Add_left(irn, pred);
1324                         }
1325                         pred = get_Add_right(irn);
1326                         if (get_irn_mode(pred) != mode) {
1327                                 ir_node *block = get_nodes_block(pred);
1328
1329                                 pred = new_r_Conv(block, pred, mode);
1330                                 set_Add_right(irn, pred);
1331                         }
1332                 }
1333         } else if (is_Sub(irn)) {
1334                 ir_mode *mode = get_irn_mode(irn);
1335
1336                 if (mode_is_int(mode)) {
1337                         ir_node *left   = get_Sub_left(irn);
1338                         ir_node *right  = get_Sub_right(irn);
1339                         ir_mode *l_mode = get_irn_mode(left);
1340                         ir_mode *r_mode = get_irn_mode(right);
1341
1342                         if (mode_is_int(l_mode) && mode_is_int(r_mode)) {
1343                                 if (l_mode != mode) {
1344                                         ir_node *block = get_nodes_block(left);
1345
1346                                         left = new_r_Conv(block, left, mode);
1347                                         set_Sub_left(irn, left);
1348                                 }
1349                                 if (r_mode != mode) {
1350                                         ir_node *block = get_nodes_block(right);
1351
1352                                         right = new_r_Conv(block, right, mode);
1353                                         set_Sub_right(irn, right);
1354                                 }
1355                         }
1356                 } else if (mode_is_reference(mode)) {
1357                         ir_node *left   = get_Sub_left(irn);
1358                         ir_node *right  = get_Sub_right(irn);
1359                         ir_mode *l_mode = get_irn_mode(left);
1360                         ir_mode *r_mode = get_irn_mode(right);
1361                         if (mode_is_int(l_mode)) {
1362                                 /* Usually, Sub(I*,P) is an error, hence the verifier rejects it.
1363                                  * However, it is correct in this case, so add Conv to make verifier happy. */
1364                                 ir_node *block = get_nodes_block(right);
1365                                 ir_node *lconv = new_r_Conv(block, left, r_mode);
1366                                 assert(mode_is_reference(r_mode));
1367                                 set_Sub_left(irn, lconv);
1368                         }
1369                 }
1370         }
1371 }
1372
1373 /* Performs Operator Strength Reduction for the passed graph. */
1374 void opt_osr(ir_graph *irg, unsigned flags)
1375 {
1376         iv_env env;
1377
1378         FIRM_DBG_REGISTER(dbg, "firm.opt.osr");
1379
1380         assure_irg_properties(irg,
1381                 IR_GRAPH_PROPERTY_CONSISTENT_DOMINANCE
1382                 | IR_GRAPH_PROPERTY_CONSISTENT_OUTS
1383                 | IR_GRAPH_PROPERTY_CONSISTENT_OUT_EDGES);
1384
1385         DB((dbg, LEVEL_1, "Doing Operator Strength Reduction for %+F\n", irg));
1386
1387         obstack_init(&env.obst);
1388         env.stack         = NEW_ARR_F(ir_node *, 128);
1389         env.tos           = 0;
1390         env.nextDFSnum    = 0;
1391         env.POnum         = 0;
1392         env.quad_map      = new_set(quad_cmp, 64);
1393         env.lftr_edges    = new_set(LFTR_cmp, 64);
1394         env.replaced      = 0;
1395         env.lftr_replaced = 0;
1396         env.osr_flags     = flags;
1397         env.need_postpass = 0;
1398         env.process_scc   = process_scc;
1399
1400         /* Clear all links and move Proj nodes into the
1401          * the same block as its predecessors.
1402          * This can improve the placement of new nodes.
1403          */
1404         irg_walk_graph(irg, NULL, firm_clear_link, NULL);
1405
1406         irg_block_edges_walk(get_irg_start_block(irg), NULL, assign_po, &env);
1407
1408         /* calculate the SCC's and drive OSR. */
1409         ir_reserve_resources(irg, IR_RESOURCE_IRN_LINK);
1410         do_dfs(irg, &env);
1411
1412         if (env.replaced) {
1413                 if (env.need_postpass)
1414                         irg_walk_graph(irg, NULL, fix_adds_and_subs, &env);
1415
1416                 /* try linear function test replacements */
1417                 lftr(irg, &env);
1418                 (void)lftr;
1419
1420                 DB((dbg, LEVEL_1, "Replacements: %u + %u (lftr)\n\n", env.replaced, env.lftr_replaced));
1421         }
1422         ir_free_resources(irg, IR_RESOURCE_IRN_LINK);
1423
1424         del_set(env.lftr_edges);
1425         del_set(env.quad_map);
1426         DEL_ARR_F(env.stack);
1427         obstack_free(&env.obst, NULL);
1428
1429         confirm_irg_properties(irg, IR_GRAPH_PROPERTIES_NONE);
1430 }
1431
1432 typedef struct pass_t {
1433         ir_graph_pass_t pass;
1434         unsigned        flags;
1435 } pass_t;
1436
1437 /**
1438 * Wrapper for running opt_osr() as an ir_graph pass.
1439 */
1440 static int pass_wrapper(ir_graph *irg, void *context)
1441 {
1442         pass_t *pass = (pass_t*)context;
1443         opt_osr(irg, pass->flags);
1444         return 0;
1445 }
1446
1447 ir_graph_pass_t *opt_osr_pass(const char *name, unsigned flags)
1448 {
1449         pass_t *pass = XMALLOCZ(pass_t);
1450
1451         pass->flags = flags;
1452         return def_graph_pass_constructor(
1453                 &pass->pass, name ? name : "osr", pass_wrapper);
1454 }