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 "irop_t.h"
  27 #include "irloop.h"
  28 #include "irdom.h"
  29 #include "irflag_t.h"
  30 #include "irgwalk.h"
  31 #include "debug.h"
  32 #include "obst.h"
  33 #include "irtools.h"
  34 #include "array.h"
  35
  36 /** The debug handle. */
  37 DEBUG_ONLY(static firm_dbg_module_t *dbg;)
  38
  39 /* Use the link field to mark IV's */
  40 #define MARK_LOOP_IV(loop)   set_loop_link((loop), (loop))
  41 #define UNMARK_LOOP_IV(loop) set_loop_link((loop), NULL)
  42 #define IS_LOOP_IV(loop)     (get_loop_link(loop) != NULL)
  43
  44 /** A scc. */
  45 typedef struct scc {
  46         ir_node *head;          /**< the head of the list */
  47         ir_node *header;        /**< the header block of this scc */
  48         int     is_iv;      /**< true, if this scc is an IV */
  49 } scc;
  50
  51 /** A node entry */
  52 typedef struct node_entry {
  53         unsigned DFSnum;    /**< the DFS number of this node */
  54         unsigned low;       /**< the low number of this node */
  55         ir_node  *header;   /**< the header of this node */
  56         int      in_stack;  /**< flag, set if the node is on the stack */
  57         ir_node  *next;     /**< link to the next node the the same scc */
  58         scc      *pscc;     /**< the scc of this node */
  59         unsigned POnum;     /**< the post order number for blocks */
  60 } node_entry;
  61
  62 /** The environment. */
  63 typedef struct iv_env {
  64         node_entry *entries;   /**< the node entry array */
  65         struct obstack obst;   /**< an obstack for allocations */
  66         ir_node  **stack;      /**< the node stack */
  67         int      tos;          /**< tos index */
  68         unsigned nextDFSnum;   /**< the current DFS number */
  69         unsigned replaced;     /**< number of replaced ops */
  70         unsigned POnum;        /**< current post order number */
  71 } iv_env;
  72
  73 /**
  74  * Check if irn is an IV.
  75  */
  76 static scc *is_iv(ir_node *irn, iv_env *env) {
  77         int idx = get_irn_idx(irn);
  78         node_entry *e = &env->entries[idx];
  79
  80         return e->pscc && e->pscc->is_iv ? e->pscc : NULL;
  81 }
  82
  83 /**
  84  * Check if irn is a region constant.
  85  */
  86 static int is_rc(ir_node *irn, ir_node *header_block) {
  87         ir_node *block = get_nodes_block(irn);
  88
  89         return block_dominates(block, header_block);
  90 }
  91
  92 /**
  93  * Do the replacement operation.
  94  *
  95  * @param irn   the node that will be replaced
  96  * @param iv    the induction variable
  97  * @param rc    the region constant
  98  * @param env   the environment
  99  */
 100 static void replace(ir_node *irn, ir_node *iv, ir_node *rc, iv_env *env) {
 101         DB((dbg, LEVEL_2, "  Replacing %+F\n", irn));
 102 }
 103
 104 /**
 105  * check if a node can be replaced
 106  */
 107 static void check_replace(ir_node *irn, iv_env *env) {
 108         ir_node *left, *right, *iv, *rc;
 109         ir_op   *op  = get_irn_op(irn);
 110         opcode  code = get_op_code(op);
 111         scc     *liv, *riv;
 112
 113         switch (code) {
 114         case iro_Mul:
 115         case iro_Add:
 116         case iro_Sub:
 117                 iv = rc = NULL;
 118
 119                 left  = get_binop_left(irn);
 120                 right = get_binop_right(irn);
 121
 122                 liv = is_iv(left, env);
 123                 riv = is_iv(right, env);
 124                 if (liv && is_rc(right, liv->header)) {
 125                         iv = left; rc = right;
 126                 }
 127                 else if (is_op_commutative(op) &&
 128                         riv && is_rc(left, riv->header)) {
 129                         iv = right; rc = left;
 130                 }
 131
 132                 if (iv) {
 133                         replace(irn, iv, rc, env);
 134                         ++env->replaced;
 135                 }
 136                 break;
 137         }
 138 }
 139
 140 /**
 141  * check which SCC's are induction variables
 142  */
 143 static void classify_iv(scc *pscc, iv_env *env) {
 144         ir_node *irn, *next, *header = NULL;
 145         node_entry *h, *b;
 146         int j;
 147
 148         /* find the header block for this scc */
 149         for (irn = pscc->head; irn; irn = next) {
 150                 node_entry *e = get_irn_link(irn);
 151                 ir_node *block = get_nodes_block(irn);
 152
 153                 next = e->next;
 154                 b = &env->entries[get_irn_idx(block)];
 155
 156                 if (header) {
 157                         if (h->POnum < b->POnum) {
 158                                 header = block;
 159                                 h      = b;
 160                         }
 161                 }
 162                 else {
 163                         header = block;
 164                         h      = b;
 165                 }
 166         }
 167         pscc->header = header;
 168
 169         for (irn = pscc->head; irn; irn = next) {
 170                 node_entry *e = get_irn_link(irn);
 171
 172                 next = e->next;
 173                 switch (get_irn_opcode(irn)) {
 174                 case iro_Add:
 175                 case iro_Sub:
 176                 case iro_Phi:
 177                         for (j = get_irn_arity(irn) - 1; j >= 0; --j) {
 178                                 ir_node *pred = get_irn_n(irn, j);
 179                                 node_entry *pe = &env->entries[get_irn_idx(pred)];
 180
 181                                 if (pe->pscc != e->pscc) {
 182                                         /* not in the same SCC, must be a region const */
 183                                         if (! is_rc(pred, header)) {
 184                                                 /* not an induction variable */
 185                                                 goto fail;
 186                                         }
 187                                 }
 188                         }
 189                         break;
 190                 default:
 191                         /* not an induction variable */
 192                         goto fail;
 193                 }
 194         }
 195         /* found an induction variable */
 196         DB((dbg, LEVEL_2, "  Found an induction variable in %+F\n", pscc->head));
 197         pscc->is_iv = 1;
 198         return;
 199
 200 fail:
 201         for (irn = pscc->head; irn; irn = next) {
 202                 node_entry *e = get_irn_link(irn);
 203
 204                 next = e->next;
 205                 check_replace(irn, env);
 206         }
 207 }
 208
 209 /**
 210  * Do the replacement: We must do this as an additional step because
 211  * of our loop-tree structure.
 212  */
 213 static void find_replacement(ir_loop *loop, iv_env *env) {
 214         int i, n;
 215
 216         if (! IS_LOOP_IV(loop)) {
 217                 /* do replacements */
 218                 n = get_loop_n_nodes(loop);
 219                 for (i = 0; i < n; ++i) {
 220                         ir_node *irn = get_loop_node(loop, i);
 221                         ir_node *left, *right, *iv, *rc;
 222                         opcode code = get_irn_opcode(irn);
 223
 224                         switch (code) {
 225                         case iro_Mul:
 226                         case iro_Add:
 227                         case iro_Sub:
 228                                 iv = rc = NULL;
 229
 230                                 left  = get_binop_left(irn);
 231                                 right = get_binop_right(irn);
 232
 233                                 if (is_iv(left, env) && is_rc(right, left)) {
 234                                         iv = left; rc = right;
 235                                 }
 236                                 else if (code != iro_Sub &&
 237                                         is_iv(right, env) && is_rc(left, right)) {
 238                                         iv = right; rc = left;
 239                                 }
 240
 241                                 if (iv) {
 242                                         replace(irn, iv, rc, env);
 243                                         ++env->replaced;
 244                                 }
 245                                 break;
 246                         }
 247                 }
 248         }
 249         n = get_loop_n_sons(loop);
 250         for (i = 0; i < n; ++i) {
 251                 ir_loop *child = get_loop_son(loop, i);
 252                 find_replacement(child, env);
 253         }
 254 }
 255
 256 /**
 257  * Process a SCC given as a list.
 258  */
 259 static void process_scc(scc *pscc, iv_env *env) {
 260         ir_node *head = pscc->head;
 261         node_entry *e = get_irn_link(head);
 262
 263         pscc->is_iv = 0;
 264
 265 #ifdef DEBUG_libfirm
 266         {
 267                 ir_node *irn, *next;
 268
 269                 DB((dbg, LEVEL_3, " SCC at %p:\n ", pscc));
 270                 for (irn = pscc->head; irn; irn = next) {
 271                         node_entry *e = get_irn_link(irn);
 272
 273                         next = e->next;
 274
 275                         DB((dbg, LEVEL_3, " %+F,", irn));
 276                 }
 277                 DB((dbg, LEVEL_3, "\n"));
 278         }
 279 #endif
 280
 281         if (e->next == NULL) {
 282                 /* this SCC has only a single member */
 283                 check_replace(head, env);
 284         }
 285         else {
 286                 classify_iv(pscc, env);
 287         }
 288 }
 289
 290 /**
 291  * Push a node onto the stack.
 292  */
 293 static void push(iv_env *env, ir_node *n) {
 294         if (env->tos == ARR_LEN(env->stack)) {
 295                 int nlen = ARR_LEN(env->stack) * 2;
 296                 ARR_RESIZE(ir_node *, env->stack, nlen);
 297         }
 298         env->stack[env->tos++] = n;
 299         env->entries[get_irn_idx(n)].in_stack = 1;
 300 }
 301
 302 /**
 303  * pop a node from the stack
 304  *
 305  * @return  The topmost node
 306  */
 307 static ir_node *pop(iv_env *env)
 308 {
 309   ir_node *n = env->stack[--env->tos];
 310   env->entries[get_irn_idx(n)].in_stack = 0;
 311   return n;
 312 }
 313
 314 static void dfs(ir_node *irn, iv_env *env)
 315 {
 316         int i, n;
 317         node_entry *node = &env->entries[get_irn_idx(irn)];
 318
 319         mark_irn_visited(irn);
 320
 321         /* do not put blocks into the scc */
 322         if (is_Block(irn)) {
 323                 n = get_irn_arity(irn);
 324                 for (i = 0; i < n; ++i) {
 325                         ir_node *pred = get_irn_n(irn, i);
 326
 327                         if (irn_not_visited(pred))
 328                                 dfs(pred, env);
 329                 }
 330         }
 331         else {
 332                 ir_node *block = get_nodes_block(irn);
 333
 334                 node->DFSnum = env->nextDFSnum++;
 335                 node->low    = node->DFSnum;
 336                 push(env, irn);
 337
 338                 /* handle the block */
 339                 if (irn_not_visited(block))
 340                         dfs(block, env);
 341
 342                 n = get_irn_arity(irn);
 343                 for (i = 0; i < n; ++i) {
 344                         ir_node *pred = get_irn_n(irn, i);
 345                         node_entry *o = &env->entries[get_irn_idx(pred)];
 346
 347                         if (irn_not_visited(pred)) {
 348                                 dfs(pred, env);
 349                                 node->low = MIN(node->low, o->low);
 350                         }
 351                         if (o->DFSnum < node->DFSnum && o->in_stack)
 352                                 node->low = MIN(o->DFSnum, node->low);
 353                 }
 354                 if (node->low == node->DFSnum) {
 355                         scc *pscc = obstack_alloc(&env->obst, sizeof(*pscc));
 356                         ir_node *x;
 357
 358                         pscc->head = NULL;
 359                         do {
 360                                 node_entry *e;
 361
 362                                 x = pop(env);
 363                                 e = &env->entries[get_irn_idx(x)];
 364                                 e->pscc    = pscc;
 365                                 e->next    = pscc->head;
 366                                 pscc->head = x;
 367
 368                                 /* link the node entry for easier access */
 369                                 set_irn_link(x, e);
 370                         } while (x != irn);
 371
 372                         process_scc(pscc, env);
 373                 }
 374         }
 375 }
 376
 377 /**
 378  * Do the DFS by starting end the End node
 379  */
 380 static void do_dfs(ir_graph *irg, iv_env *env) {
 381         ir_graph *rem = current_ir_graph;
 382         ir_node *end = get_irg_end(irg);
 383         int i, n;
 384
 385         current_ir_graph = irg;
 386         inc_irg_visited(irg);
 387
 388         /* visit all visible nodes */
 389         dfs(end, env);
 390
 391         /* visit the keep-alives */
 392         n = get_End_n_keepalives(end);
 393         for (i = 0; i < n; ++i) {
 394                 ir_node *ka = get_End_keepalive(end, i);
 395
 396                 if (irn_not_visited(ka))
 397                         dfs(ka, env);
 398         }
 399         current_ir_graph = rem;
 400 }
 401
 402 /**
 403  * Post-block-walker: assign the post-order number.
 404  */
 405 static void assign_po(ir_node *block, void *ctx) {
 406         iv_env *env = ctx;
 407         int idx = get_irn_idx(block);
 408
 409         env->entries[idx].POnum = env->POnum++;
 410 }
 411
 412 /* Performs Operator Strength Reduction for the passed graph. */
 413 void opt_osr(ir_graph *irg) {
 414         iv_env env;
 415
 416         if (! get_opt_strength_red())
 417                 return;
 418
 419         FIRM_DBG_REGISTER(dbg, "firm.opt.osr");
 420         firm_dbg_set_mask(dbg, SET_LEVEL_2);
 421
 422         /* and dominance as well */
 423         assure_doms(irg);
 424
 425         DB((dbg, LEVEL_1, "Doing Operator Strength Reduction for %+F\n", irg));
 426
 427         env.entries    = NEW_ARR_F(node_entry, get_irg_last_idx(irg));
 428         memset(env.entries, 0, get_irg_last_idx(irg));
 429
 430         obstack_init(&env.obst);
 431         env.stack      = NEW_ARR_F(ir_node *, 128);
 432         env.tos        = 0;
 433         env.nextDFSnum = 0;
 434         env.replaced   = 0;
 435         env.POnum      = 0;
 436
 437         /* calculate the post order number */
 438         irg_block_walk_graph(irg, NULL, assign_po, &env);
 439
 440         do_dfs(irg, &env);
 441
 442         if (env.replaced) {
 443                 set_irg_outs_inconsistent(irg);
 444                 set_irg_loopinfo_inconsistent(irg);
 445         }
 446         DB((dbg, LEVEL_1, "Replacements: %u\n\n", env.replaced));
 447
 448         DEL_ARR_F(env.stack);
 449         obstack_free(&env.obst, NULL);
 450         DEL_ARR_F(env.entries);
 451 }