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

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