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

   1 /**
   2  * Project:     libFIRM
   3  * File name:   ir/opt/opt_osr.
   4  * Purpose:     Operator Strength Reduction,
   5  *              Keith D. Cooper, L. Taylor Simpson, Christopher A. Vick
   6  * Author:      Michael Beck
   7  * Modified by:
   8  * Created:     12.5.2006
   9  * CVS-ID:      $Id$
  10  * Copyright:   (c) 2006 Universität Karlsruhe
  11  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  12  */
  13 #ifdef HAVE_CONFIG_H
  14 #include "config.h"
  15 #endif
  16
  17 #ifdef HAVE_MALLOC_H
  18 #include <malloc.h>
  19 #endif
  20 #ifdef HAVE_ALLOCA_H
  21 #include <alloca.h>
  22 #endif
  23
  24 #include "opt_osr.h"
  25 #include "irgraph.h"
  26 #include "ircons.h"
  27 #include "irop_t.h"
  28 #include "irloop.h"
  29 #include "irdom.h"
  30 #include "irgmod.h"
  31 #include "irflag_t.h"
  32 #include "irgwalk.h"
  33 #include "debug.h"
  34 #include "obst.h"
  35 #include "set.h"
  36 #include "tv.h"
  37 #include "hashptr.h"
  38 #include "irtools.h"
  39 #include "array.h"
  40
  41 /** The debug handle. */
  42 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
  43
  44 /** A scc. */
  45 typedef struct scc {
  46         ir_node *head;          /**< the head of the list */
  47 } scc;
  48
  49 /** A node entry */
  50 typedef struct node_entry {
  51         unsigned DFSnum;    /**< the DFS number of this node */
  52         unsigned low;       /**< the low number of this node */
  53         ir_node  *header;   /**< the header of this node */
  54         int      in_stack;  /**< flag, set if the node is on the stack */
  55         ir_node  *next;     /**< link to the next node the the same scc */
  56         scc      *pscc;     /**< the scc of this node */
  57         unsigned POnum;     /**< the post order number for blocks */
  58 } node_entry;
  59
  60 /** The environment. */
  61 typedef struct iv_env {
  62         struct obstack obst;    /**< an obstack for allocations */
  63         ir_node  **stack;       /**< the node stack */
  64         int      tos;           /**< tos index */
  65         unsigned nextDFSnum;    /**< the current DFS number */
  66         unsigned POnum;         /**< current post order number */
  67         set      *quad_map;     /**< a map from (op, iv, rc) to node */
  68         set      *lftr_edges;   /**< the set of lftr edges */
  69         unsigned replaced;      /**< number of replaced ops */
  70         unsigned lftr_replaced; /**< number of applied linear function test replacements */
  71         unsigned flags;         /**< additional flags */
  72 } iv_env;
  73
  74 /**
  75  * An entry in the (op, node, node) -> node map.
  76  */
  77 typedef struct quad_t {
  78         opcode  code;  /**< the opcode of the reduced operation */
  79         ir_node *op1;  /**< the first operand the reduced operation */
  80         ir_node *op2;  /**< the second operand of the reduced operation */
  81
  82         ir_node *res; /**< the reduced operation */
  83 } quad_t;
  84
  85 /**
  86  * A LFTR edge.
  87  */
  88 typedef struct LFTR_edge {
  89         ir_node *src;   /**< the source node */
  90         ir_node *dst;   /**< the destination node */
  91         opcode  code;   /**< the opcode that must be applied */
  92         ir_node *rc;    /**< the region const that must be applied */
  93 } LFTR_edge;
  94
  95 /* forward */
  96 static ir_node *reduce(ir_node *orig, ir_node *iv, ir_node *rc, iv_env *env);
  97
  98 /**
  99  * Compare two LFTR edges.
 100  */
 101 static int LFTR_cmp(const void *e1, const void *e2, size_t size) {
 102         const LFTR_edge *l1 = e1;
 103         const LFTR_edge *l2 = e2;
 104
 105         return l1->src != l2->src;
 106 }
 107
 108 /**
 109  * Find a LFTR edge.
 110  */
 111 static LFTR_edge *LFTR_find(ir_node *src, iv_env *env) {
 112         LFTR_edge key;
 113
 114         key.src  = src;
 115
 116         return set_find(env->lftr_edges, &key, sizeof(key), HASH_PTR(src));
 117 }
 118
 119 /**
 120  * Add a LFTR edge.
 121  */
 122 static void LFTR_add(ir_node *src, ir_node *dst, opcode code, ir_node *rc, iv_env *env) {
 123         LFTR_edge key;
 124
 125         key.src  = src;
 126         key.dst  = dst;
 127         key.code = code;
 128         key.rc   = rc;
 129
 130         assert(LFTR_find(src, env) == NULL);
 131         set_insert(env->lftr_edges, &key, sizeof(key), HASH_PTR(src));
 132 }
 133
 134 /**
 135  * Gets the node_entry of a node
 136  */
 137 static node_entry *get_irn_ne(ir_node *irn, iv_env *env) {
 138         node_entry *e = get_irn_link(irn);
 139
 140         if (! e) {
 141                 e = obstack_alloc(&env->obst, sizeof(*e));
 142                 memset(e, 0, sizeof(*e));
 143                 set_irn_link(irn, e);
 144         }
 145         return e;
 146 }
 147
 148 /**
 149  * Check if irn is an IV.
 150  *
 151  * @returns the header if it is one, NULL else
 152  */
 153 static ir_node *is_iv(ir_node *irn, iv_env *env) {
 154         return get_irn_ne(irn, env)->header;
 155 }
 156
 157 /**
 158  * Check if irn is a region constant.
 159  */
 160 static int is_rc(ir_node *irn, ir_node *header_block) {
 161         ir_node *block = get_nodes_block(irn);
 162
 163         return block_dominates(block, header_block);
 164 }
 165
 166 /**
 167  * Set compare function for the quad set.
 168  */
 169 static int quad_cmp(const void *e1, const void *e2, size_t size) {
 170         const quad_t *c1 = e1;
 171         const quad_t *c2 = e2;
 172
 173         return c1->code != c2->code || c1->op1 != c2->op1 || c1->op2 != c2->op2;
 174 }
 175
 176 /**
 177  * Check if an reduced operation was already calculated.
 178  */
 179 static ir_node *search(opcode code, ir_node *op1, ir_node *op2, iv_env *env) {
 180         quad_t key, *entry;
 181
 182         key.code = code;
 183         key.op1 = op2;
 184         key.op2 = op2;
 185
 186         entry = set_find(env->quad_map, &key, sizeof(key),
 187                          (code * 9) ^ HASH_PTR(op1) ^HASH_PTR(op2));
 188         if (entry)
 189                 return entry->res;
 190         return NULL;
 191 }
 192
 193 /**
 194  * Add an reduced operation was already calculated.
 195  */
 196 static void add(opcode code, ir_node *op1, ir_node *op2, ir_node *result, iv_env *env) {
 197         quad_t key;
 198
 199         key.code = code;
 200         key.op1  = op2;
 201         key.op2  = op2;
 202         key.res  = result;
 203
 204         set_insert(env->quad_map, &key, sizeof(key),
 205                    (code * 9) ^ HASH_PTR(op1) ^HASH_PTR(op2));
 206 }
 207
 208 /**
 209  * Find a location where to place a bin-op whose operands are in
 210  * block1 and block2.
 211  *
 212  * Note that we know here that such a place must exists. Moreover, this means
 213  * that either block1 dominates block2 or vice versa. So, just return
 214  * the "smaller" one.
 215  */
 216 static ir_node *find_location(ir_node *block1, ir_node *block2) {
 217         if (block_dominates(block1, block2))
 218                 return block1;
 219         assert(block_dominates(block2, block1));
 220         return block2;
 221 }
 222
 223 /**
 224  * create an op1 code op1 operation.
 225  */
 226 static ir_node *do_apply(opcode code, dbg_info *db, ir_node *op1, ir_node *op2, ir_mode *mode) {
 227         ir_graph *irg = current_ir_graph;
 228         ir_node *result;
 229         ir_node *block = find_location(get_nodes_block(op1), get_nodes_block(op2));
 230
 231         switch (code) {
 232         case iro_Mul:
 233                 result = new_rd_Mul(db, irg, block, op1, op2, mode);
 234                 break;
 235         case iro_Add:
 236                 result = new_rd_Add(db, irg, block, op1, op2, mode);
 237                 break;
 238         case iro_Sub:
 239                 result = new_rd_Sub(db, irg, block, op1, op2, mode);
 240                 break;
 241         default:
 242                 assert(0);
 243                 result = NULL;
 244         }
 245         return result;
 246 }
 247
 248 /**
 249  * The Apply operation.
 250  */
 251 static ir_node *apply(ir_node *orig, ir_node *op1, ir_node *op2, iv_env *env) {
 252         opcode code = get_irn_opcode(orig);
 253         ir_node *result = search(code, op1, op2, env);
 254
 255         if (! result) {
 256                 dbg_info *db = get_irn_dbg_info(orig);
 257                 ir_node *op1_header = get_irn_ne(op1, env)->header;
 258                 ir_node *op2_header = get_irn_ne(op2, env)->header;
 259
 260                 if (op1_header != NULL && is_rc(op2, op1_header)) {
 261                         result = reduce(orig, op1, op2, env);
 262                 }
 263                 else if (op2_header != NULL && is_rc(op1, op2_header)) {
 264                         result = reduce(orig, op2, op1, env);
 265                 }
 266                 else {
 267                         result = do_apply(code, db, op1, op2, get_irn_mode(orig));
 268                         get_irn_ne(result, env)->header = NULL;
 269                 }
 270         }
 271         return result;
 272 }
 273
 274 /**
 275  * The Reduce operation.
 276  */
 277 static ir_node *reduce(ir_node *orig, ir_node *iv, ir_node *rc, iv_env *env) {
 278         opcode code = get_irn_opcode(orig);
 279         ir_node *result = search(code, iv, rc, env);
 280
 281         if (! result) {
 282                 node_entry *e, *iv_e;
 283                 int i, n;
 284                 ir_mode *mode = get_irn_mode(orig);
 285
 286                 result = exact_copy(iv);
 287                 if (mode_is_reference(mode)) {
 288                         /* bad case: we replace a reference mode calculation.
 289                            assure that the new IV will be a reference one */
 290                         set_irn_mode(result, mode);
 291                 }
 292                 add(code, iv, rc, result, env);
 293                 DB((dbg, LEVEL_3, "   Created new %+F for %+F (%s %+F)\n", result, iv,
 294                         get_irn_opname(orig), rc));
 295
 296                 iv_e = get_irn_ne(iv, env);
 297                 e    = get_irn_ne(result, env);
 298                 e->header = iv_e->header;
 299
 300                 /* create the LFTR edge */
 301                 LFTR_add(iv, result, code, rc, env);
 302
 303                 n = get_irn_arity(result);
 304                 for (i = 0; i < n; ++i) {
 305                         ir_node *o = get_irn_n(result, i);
 306
 307                         e = get_irn_ne(o, env);
 308                         if (e->header == iv_e->header)
 309                                 o = reduce(orig, o, rc, env);
 310                         else if (is_Phi(result))
 311                                 o = apply(orig, o, rc, env);
 312                         else {
 313                                 switch (code) {
 314                                 case iro_Mul:
 315                                         o = apply(orig, o, rc, env);
 316                                         break;
 317                                 }
 318                         }
 319                         set_irn_n(result, i, o);
 320                 }
 321         }
 322         return result;
 323 }
 324
 325 /**
 326  * Do the replacement operation.
 327  *
 328  * @param irn   the node that will be replaced
 329  * @param iv    the induction variable
 330  * @param rc    the region constant
 331  * @param env   the environment
 332  */
 333 static void replace(ir_node *irn, ir_node *iv, ir_node *rc, iv_env *env) {
 334         ir_node *result;
 335
 336         DB((dbg, LEVEL_2, "  Replacing %+F\n", irn));
 337
 338         result = reduce(irn, iv, rc, env);
 339         if (result && result != irn) {
 340                 node_entry *e, *iv_e;
 341
 342                 exchange(irn, result);
 343                 e = get_irn_ne(result, env);
 344                 iv_e = get_irn_ne(iv, env);
 345                 e->header = iv_e->header;
 346         }
 347 }
 348
 349 /**
 350  * check if a node can be replaced.
 351  */
 352 static int check_replace(ir_node *irn, iv_env *env) {
 353         ir_node *left, *right, *iv, *rc;
 354         ir_op   *op  = get_irn_op(irn);
 355         opcode  code = get_op_code(op);
 356         ir_node *liv, *riv;
 357
 358         switch (code) {
 359         case iro_Mul:
 360         case iro_Add:
 361         case iro_Sub:
 362                 iv = rc = NULL;
 363
 364                 left  = get_binop_left(irn);
 365                 right = get_binop_right(irn);
 366
 367                 liv = is_iv(left, env);
 368                 riv = is_iv(right, env);
 369                 if (liv && is_rc(right, liv)) {
 370                         iv = left; rc = right;
 371                 }
 372                 else if (is_op_commutative(op) &&
 373                         riv && is_rc(left, riv)) {
 374                         iv = right; rc = left;
 375                 }
 376
 377                 if (iv) {
 378                         replace(irn, iv, rc, env);
 379                         ++env->replaced;
 380                         return 1;
 381                 }
 382                 break;
 383         }
 384         return 0;
 385 }
 386
 387 /**
 388  * check which SCC's are induction variables
 389  */
 390 static void classify_iv(scc *pscc, iv_env *env) {
 391         ir_node *irn, *next, *header = NULL;
 392         node_entry *h, *b;
 393         int j;
 394
 395         /* find the header block for this scc */
 396         for (irn = pscc->head; irn; irn = next) {
 397                 node_entry *e = get_irn_link(irn);
 398                 ir_node *block = get_nodes_block(irn);
 399
 400                 next = e->next;
 401                 b = get_irn_ne(block, env);
 402
 403                 if (header) {
 404                         if (h->POnum < b->POnum) {
 405                                 header = block;
 406                                 h      = b;
 407                         }
 408                 }
 409                 else {
 410                         header = block;
 411                         h      = b;
 412                 }
 413         }
 414
 415         /* check if this scc contains only Phi, Add or Sub nodes */
 416         for (irn = pscc->head; irn; irn = next) {
 417                 node_entry *e = get_irn_ne(irn, env);
 418
 419                 next = e->next;
 420                 switch (get_irn_opcode(irn)) {
 421                 case iro_Add:
 422                 case iro_Sub:
 423                 case iro_Phi:
 424                         for (j = get_irn_arity(irn) - 1; j >= 0; --j) {
 425                                 ir_node *pred  = get_irn_n(irn, j);
 426                                 node_entry *pe = get_irn_ne(pred, env);
 427
 428                                 if (pe->pscc != e->pscc) {
 429                                         /* not in the same SCC, must be a region const */
 430                                         if (! is_rc(pred, header)) {
 431                                                 /* not an induction variable */
 432                                                 goto fail;
 433                                         }
 434                                 }
 435                         }
 436                         break;
 437                 default:
 438                         /* not an induction variable */
 439                         goto fail;
 440                 }
 441         }
 442         /* found an induction variable */
 443         DB((dbg, LEVEL_2, "  Found an induction variable in %+F\n", pscc->head));
 444
 445         /* set the header for every node in this scc */
 446         for (irn = pscc->head; irn; irn = next) {
 447                 node_entry *e = get_irn_ne(irn, env);
 448                 e->header = header;
 449                 next = e->next;
 450         }
 451         return;
 452
 453 fail:
 454         for (irn = pscc->head; irn; irn = next) {
 455                 node_entry *e = get_irn_ne(irn, env);
 456
 457                 next = e->next;
 458                 if (! check_replace(irn, env))
 459                         e->header = NULL;
 460         }
 461 }
 462
 463 /**
 464  * Process a SCC given as a list.
 465  */
 466 static void process_scc(scc *pscc, iv_env *env) {
 467         ir_node *head = pscc->head;
 468         node_entry *e = get_irn_link(head);
 469
 470 #ifdef DEBUG_libfirm
 471         {
 472                 ir_node *irn, *next;
 473
 474                 DB((dbg, LEVEL_4, " SCC at %p:\n ", pscc));
 475                 for (irn = pscc->head; irn; irn = next) {
 476                         node_entry *e = get_irn_link(irn);
 477
 478                         next = e->next;
 479
 480                         DB((dbg, LEVEL_4, " %+F,", irn));
 481                 }
 482                 DB((dbg, LEVEL_4, "\n"));
 483         }
 484 #endif
 485
 486         if (e->next == NULL) {
 487                 /* this SCC has only a single member */
 488                 check_replace(head, env);
 489         }
 490         else {
 491                 classify_iv(pscc, env);
 492         }
 493 }
 494
 495 /**
 496  * Push a node onto the stack.
 497  */
 498 static void push(iv_env *env, ir_node *n) {
 499         node_entry *e;
 500
 501         if (env->tos == ARR_LEN(env->stack)) {
 502                 int nlen = ARR_LEN(env->stack) * 2;
 503                 ARR_RESIZE(ir_node *, env->stack, nlen);
 504         }
 505         env->stack[env->tos++] = n;
 506         e = get_irn_ne(n, env);
 507         e->in_stack = 1;
 508 }
 509
 510 /**
 511  * pop a node from the stack
 512  *
 513  * @return  The topmost node
 514  */
 515 static ir_node *pop(iv_env *env)
 516 {
 517   ir_node *n = env->stack[--env->tos];
 518   node_entry *e = get_irn_ne(n, env);
 519
 520   e->in_stack = 0;
 521   return n;
 522 }
 523
 524 /**
 525  * Do Tarjan's SCC algorithm and drive OSR
 526  *
 527  * @param irn  start at this node
 528  * @param env  the environment
 529  */
 530 static void dfs(ir_node *irn, iv_env *env)
 531 {
 532         int i, n;
 533         node_entry *node = get_irn_ne(irn, env);
 534
 535         mark_irn_visited(irn);
 536
 537         /* do not put blocks into the scc */
 538         if (is_Block(irn)) {
 539                 n = get_irn_arity(irn);
 540                 for (i = 0; i < n; ++i) {
 541                         ir_node *pred = get_irn_n(irn, i);
 542
 543                         if (irn_not_visited(pred))
 544                                 dfs(pred, env);
 545                 }
 546         }
 547         else {
 548                 ir_node *block = get_nodes_block(irn);
 549
 550                 node->DFSnum = env->nextDFSnum++;
 551                 node->low    = node->DFSnum;
 552                 push(env, irn);
 553
 554                 /* handle the block */
 555                 if (irn_not_visited(block))
 556                         dfs(block, env);
 557
 558                 n = get_irn_arity(irn);
 559                 for (i = 0; i < n; ++i) {
 560                         ir_node *pred = get_irn_n(irn, i);
 561                         node_entry *o = get_irn_ne(pred, env);
 562
 563                         if (irn_not_visited(pred)) {
 564                                 dfs(pred, env);
 565                                 node->low = MIN(node->low, o->low);
 566                         }
 567                         if (o->DFSnum < node->DFSnum && o->in_stack)
 568                                 node->low = MIN(o->DFSnum, node->low);
 569                 }
 570                 if (node->low == node->DFSnum) {
 571                         scc *pscc = obstack_alloc(&env->obst, sizeof(*pscc));
 572                         ir_node *x;
 573
 574                         pscc->head = NULL;
 575                         do {
 576                                 node_entry *e;
 577
 578                                 x = pop(env);
 579                                 e = get_irn_ne(x, env);
 580                                 e->pscc    = pscc;
 581                                 e->next    = pscc->head;
 582                                 pscc->head = x;
 583                         } while (x != irn);
 584
 585                         process_scc(pscc, env);
 586                 }
 587         }
 588 }
 589
 590 /**
 591  * Do the DFS by starting end the End node
 592  */
 593 static void do_dfs(ir_graph *irg, iv_env *env) {
 594         ir_graph *rem = current_ir_graph;
 595         ir_node *end = get_irg_end(irg);
 596         int i, n;
 597
 598         current_ir_graph = irg;
 599         inc_irg_visited(irg);
 600
 601         /* visit all visible nodes */
 602         dfs(end, env);
 603
 604         /* visit the keep-alives */
 605         n = get_End_n_keepalives(end);
 606         for (i = 0; i < n; ++i) {
 607                 ir_node *ka = get_End_keepalive(end, i);
 608
 609                 if (irn_not_visited(ka))
 610                         dfs(ka, env);
 611         }
 612
 613         current_ir_graph = rem;
 614 }
 615
 616 /**
 617  * Post-block-walker: assign the post-order number.
 618  */
 619 static void assign_po(ir_node *block, void *ctx) {
 620         iv_env *env = ctx;
 621         node_entry *e = get_irn_ne(block, env);
 622
 623         e->POnum = env->POnum++;
 624 }
 625
 626 /**
 627  * follows the LFTR edges and return the last node in the chain.
 628  *
 629  * @param irn  the node that should be followed
 630  * @param env  the IV environment
 631  */
 632 static ir_node *followEdges(ir_node *irn, iv_env *env) {
 633         for (;;) {
 634                 LFTR_edge *e = LFTR_find(irn, env);
 635                 if (e)
 636                         irn = e->dst;
 637                 else
 638                         return irn;
 639         }
 640 }
 641
 642 /**
 643  * Apply one LFTR edge operation.
 644  * Return NULL if the transformation cannot be done safely without
 645  * an Overflow.
 646  *
 647  * @param rc   the IV node that should be translated
 648  * @param e    the LFTR edge
 649  * @param env  the IV environment
 650  */
 651 static ir_node *applyOneEdge(ir_node *rc, LFTR_edge *e, iv_env *env) {
 652         if (env->flags & osr_flag_lftr_with_ov_check) {
 653                 tarval *tv_l, *tv_r, *tv;
 654                 tarval_int_overflow_mode_t ovmode;
 655
 656                 /* overflow can only be decided for Consts */
 657                 if (! is_Const(e->rc)) {
 658                         DB((dbg, LEVEL_4, " = UNKNOWN (%+F)", e->rc));
 659                         return NULL;
 660                 }
 661
 662                 tv_l = get_Const_tarval(rc);
 663                 tv_r = get_Const_tarval(e->rc);
 664
 665                 ovmode = tarval_get_integer_overflow_mode();
 666                 tarval_set_integer_overflow_mode(TV_OVERFLOW_BAD);
 667
 668                 switch (e->code) {
 669                 case iro_Mul:
 670                         tv = tarval_mul(tv_l, tv_r);
 671                         DB((dbg, LEVEL_4, " * %+F", tv_r));
 672                         break;
 673                 case iro_Add:
 674                         tv = tarval_add(tv_l, tv_r);
 675                         DB((dbg, LEVEL_4, " + %+F", tv_r));
 676                         break;
 677                 case iro_Sub:
 678                         tv = tarval_sub(tv_l, tv_r);
 679                         DB((dbg, LEVEL_4, " - %+F", tv_r));
 680                         break;
 681                 default:
 682                         assert(0);
 683                         tv = tarval_bad;
 684                 }
 685                 tarval_set_integer_overflow_mode(ovmode);
 686
 687                 if (tv == tarval_bad) {
 688                         DB((dbg, LEVEL_4, " = OVERFLOW"));
 689                         return NULL;
 690                 }
 691                 return new_r_Const(current_ir_graph, get_irn_n(rc, -1), get_tarval_mode(tv), tv);
 692         }
 693         return do_apply(e->code, NULL, rc, e->rc, get_irn_mode(rc));
 694 }
 695
 696 /**
 697  * Applies the operations represented by the LFTR edges to a
 698  * region constant and returns the value.
 699  * Return NULL if the transformation cannot be done safely without
 700  * an Overflow.
 701  *
 702  * @param iv   the IV node that starts the LFTR edge chain
 703  * @param rc   the region constant that should be translated
 704  * @param env  the IV environment
 705  */
 706 static ir_node *applyEdges(ir_node *iv, ir_node *rc, iv_env *env) {
 707         ir_node *irn = iv;
 708
 709         if (env->flags & osr_flag_lftr_with_ov_check) {
 710                 /* overflow can only be decided for Consts */
 711                 if (! is_Const(rc)) {
 712                         DB((dbg, LEVEL_4, " = UNKNOWN (%+F)\n", rc));
 713                         return NULL;
 714                 }
 715                 DB((dbg, LEVEL_4, "%+F", get_Const_tarval(rc)));
 716         }
 717
 718         for (irn = iv; rc;) {
 719                 LFTR_edge *e = LFTR_find(irn, env);
 720                 if (e) {
 721                         rc = applyOneEdge(rc, e, env);
 722                         irn = e->dst;
 723                 }
 724                 else
 725                         break;
 726         }
 727         DB((dbg, LEVEL_3, "\n"));
 728         return rc;
 729 }
 730
 731 /**
 732  * Walker; find Cmp(iv, rc) or Cmp(rc, iv)
 733  */
 734 static void do_lftr(ir_node *cmp, void *ctx) {
 735         iv_env *env = ctx;
 736         ir_node *left, *right, *liv, *riv;
 737         ir_node *iv, *rc;
 738         ir_node *nleft = NULL, *nright = NULL;
 739
 740         if (get_irn_op(cmp) != op_Cmp)
 741                 return;
 742
 743         left  = get_Cmp_left(cmp);
 744         right = get_Cmp_right(cmp);
 745
 746         liv = is_iv(left, env);
 747         riv = is_iv(right, env);
 748         if (liv && is_rc(right, liv)) {
 749                 iv = left; rc = right;
 750
 751                 nright = applyEdges(iv, rc, env);
 752                 if (nright) {
 753                         nleft = followEdges(iv, env);
 754                 }
 755         }
 756         else if (riv && is_rc(left, riv)) {
 757                 iv = right; rc = left;
 758
 759                 nleft = applyEdges(iv, rc, env);
 760                 if (nleft) {
 761                         nright = followEdges(iv, env);
 762                 }
 763         }
 764
 765         if (nleft && nright) {
 766                 DB((dbg, LEVEL_2, "  LFTR for %+F\n", cmp));
 767                 set_Cmp_left(cmp, nleft);
 768                 set_Cmp_right(cmp, nright);
 769                 ++env->lftr_replaced;
 770         }
 771 }
 772
 773 /**
 774  * do linear function test replacement.
 775  */
 776 static void lftr(ir_graph *irg, iv_env *env) {
 777         irg_walk_graph(irg, NULL, do_lftr, env);
 778 }
 779
 780 /* Performs Operator Strength Reduction for the passed graph. */
 781 void opt_osr(ir_graph *irg, unsigned flags) {
 782         iv_env env;
 783
 784         if (! get_opt_strength_red())
 785                 return;
 786
 787         FIRM_DBG_REGISTER(dbg, "firm.opt.osr");
 788 //      firm_dbg_set_mask(dbg, SET_LEVEL_3);
 789
 790         /* and dominance as well */
 791         assure_doms(irg);
 792
 793         DB((dbg, LEVEL_1, "Doing Operator Strength Reduction for %+F\n", irg));
 794
 795         obstack_init(&env.obst);
 796         env.stack         = NEW_ARR_F(ir_node *, 128);
 797         env.tos           = 0;
 798         env.nextDFSnum    = 0;
 799         env.POnum         = 0;
 800         env.quad_map      = new_set(quad_cmp, 64);
 801         env.lftr_edges    = new_set(LFTR_cmp, 64);
 802         env.replaced      = 0;
 803         env.lftr_replaced = 0;
 804         env.flags         = flags;
 805
 806         /* clear all links */
 807         irg_walk_graph(irg, NULL, firm_clear_link, NULL);
 808
 809         /* calculate the post order number */
 810         irg_block_walk_graph(irg, NULL, assign_po, &env);
 811
 812         /* calculate the SCC's and drive OSR */
 813         do_dfs(irg, &env);
 814
 815         if (env.replaced) {
 816                 /* try linear function test replacements */
 817                 lftr(irg, &env);
 818
 819                 set_irg_outs_inconsistent(irg);
 820                 set_irg_loopinfo_inconsistent(irg);
 821         }
 822         DB((dbg, LEVEL_1, "Replacements: %u + %u (lftr)\n\n", env.replaced, env.lftr_replaced));
 823
 824         del_set(env.lftr_edges);
 825         del_set(env.quad_map);
 826         DEL_ARR_F(env.stack);
 827         obstack_free(&env.obst, NULL);
 828 }