nsz Git - libfirm/blob - ir/ir/irgwalk_blk.c

   1 /*
   2  * This file is part of libFirm.
   3  * Copyright (C) 2012 University of Karlsruhe.
   4  */
   5
   6 /**
   7  * @file
   8  * @brief   Blockwise walker implementation
   9  * @author  Michael Beck
  10  */
  11 #include "config.h"
  12
  13 #include "irnode_t.h"
  14 #include "irgraph_t.h"
  15 #include "irgwalk.h"
  16 #include "pset.h"
  17 #include "irhooks.h"
  18 #include "array.h"
  19 #include "hashptr.h"
  20 #include "ircons.h"
  21
  22 #define _get_walk_arity(env, node) \
  23         ((env)->follow_deps ? get_irn_ins_or_deps((node)) : get_irn_arity((node)))
  24 #define _get_walk_irn_n(env, node, pos) \
  25         ((env)->follow_deps ? get_irn_in_or_dep((node), (pos)) : get_irn_n((node), (pos)))
  26
  27 /**
  28  * Metadata for block walker
  29  */
  30 typedef struct blk_collect_data_t {
  31         struct obstack obst;            /**< obstack to allocate objects on */
  32         pset           *blk_map;        /**< Hash map: Block -> List */
  33         ir_node        **blk_list;      /**< the Block list */
  34         unsigned       follow_deps : 1; /**< follow dependency edges */
  35 } blk_collect_data_t;
  36
  37 /**
  38  * An entry for a block in the blk_map
  39  */
  40 typedef struct block_entry_t {
  41         ir_node *block;       /**< the block */
  42         ir_node **phi_list;   /**< the list of Phi instruction */
  43         ir_node **df_list;    /**< the list of data flow instruction */
  44         ir_node **cf_list;    /**< the list of control flow instructions */
  45         ir_node **entry_list; /**< list of all block entries */
  46 } block_entry_t;
  47
  48 /**
  49  * compare two block_entries
  50  */
  51 static int addr_cmp(const void *elt, const void *key)
  52 {
  53         const block_entry_t *e1 = (const block_entry_t*)elt;
  54         const block_entry_t *e2 = (const block_entry_t*)key;
  55
  56         return e1->block != e2->block;
  57 }
  58
  59 /**
  60  * Returns the associates block_entry_t for an block
  61  */
  62 static block_entry_t *block_find_entry(ir_node *block, blk_collect_data_t *ctx)
  63 {
  64         block_entry_t key;
  65         block_entry_t *elem;
  66
  67         key.block = block;
  68         elem = (block_entry_t*)pset_find(ctx->blk_map, &key, hash_ptr(block));
  69         if (elem)
  70                 return elem;
  71
  72         elem = OALLOC(&ctx->obst, block_entry_t);
  73
  74         elem->block      = block;
  75         elem->phi_list   = NEW_ARR_F(ir_node *, 0);
  76         elem->df_list    = NEW_ARR_F(ir_node *, 0);
  77         elem->cf_list    = NEW_ARR_F(ir_node *, 0);
  78         elem->entry_list = NEW_ARR_F(ir_node *, 0);
  79
  80         return (block_entry_t*)pset_insert(ctx->blk_map, elem, hash_ptr(block));
  81 }
  82
  83 /**
  84  * Traverse a block in pre order.
  85  */
  86 static void traverse_block_pre(ir_node *block, block_entry_t *entry, irg_walk_func *pre, void *env)
  87 {
  88         size_t j;
  89
  90         for (j = ARR_LEN(entry->cf_list); j > 0;) {
  91                 ir_node *node = entry->cf_list[--j];
  92                 pre(node, env);
  93         }
  94
  95         for (j = ARR_LEN(entry->df_list); j > 0;) {
  96                 ir_node *node = entry->df_list[--j];
  97                 pre(node, env);
  98         }
  99
 100         for (j = ARR_LEN(entry->phi_list); j > 0;) {
 101                 ir_node *node = entry->phi_list[--j];
 102                 pre(node, env);
 103         }
 104
 105         pre(block, env);
 106 }
 107
 108 /**
 109  * Traverse a block in post order.
 110  */
 111 static void traverse_block_post(ir_node *block, block_entry_t *entry,
 112                                 irg_walk_func *post, void *env)
 113 {
 114         size_t j, n;
 115
 116         post(block, env);
 117
 118         for (j = 0, n = ARR_LEN(entry->phi_list); j < n; ++j) {
 119                 ir_node *node = entry->phi_list[j];
 120                 post(node, env);
 121         }
 122
 123         for (j = 0, n = ARR_LEN(entry->df_list); j < n; ++j) {
 124                 ir_node *node = entry->df_list[j];
 125                 post(node, env);
 126         }
 127
 128         for (j = 0, n = ARR_LEN(entry->cf_list); j < n; ++j) {
 129                 ir_node *node = entry->cf_list[j];
 130                 post(node, env);
 131         }
 132 }
 133
 134 /**
 135  * traverse the pre order only, from End to Start
 136  */
 137 static void traverse_pre(blk_collect_data_t *blks, irg_walk_func *pre, void *env)
 138 {
 139         size_t i;
 140
 141         for (i = ARR_LEN(blks->blk_list); i > 0;) {
 142                 ir_node       *block = blks->blk_list[--i];
 143                 block_entry_t *entry = block_find_entry(block, blks);
 144
 145                 traverse_block_pre(block, entry, pre, env);
 146
 147                 DEL_ARR_F(entry->entry_list);
 148                 DEL_ARR_F(entry->phi_list);
 149                 DEL_ARR_F(entry->df_list);
 150                 DEL_ARR_F(entry->cf_list);
 151         }
 152 }
 153
 154 /**
 155  * traverse the post order only, from Start to End
 156  */
 157 static void traverse_post(blk_collect_data_t *blks, irg_walk_func *post, void *env)
 158 {
 159         size_t i, k;
 160
 161         for (i = 0, k = ARR_LEN(blks->blk_list); i < k; ++i) {
 162                 ir_node       *block = blks->blk_list[i];
 163                 block_entry_t *entry = block_find_entry(block, blks);
 164
 165                 traverse_block_post(block, entry, post, env);
 166
 167                 DEL_ARR_F(entry->entry_list);
 168                 DEL_ARR_F(entry->phi_list);
 169                 DEL_ARR_F(entry->df_list);
 170                 DEL_ARR_F(entry->cf_list);
 171         }
 172 }
 173
 174 /**
 175  * traverse both
 176  */
 177 static void traverse_both(blk_collect_data_t *blks, irg_walk_func *pre, irg_walk_func *post, void *env)
 178 {
 179         size_t i;
 180
 181         for (i = ARR_LEN(blks->blk_list); i > 0;) {
 182                 ir_node       *block = blks->blk_list[--i];
 183                 block_entry_t *entry = block_find_entry(block, blks);
 184
 185                 traverse_block_pre(block, entry, pre, env);
 186         }
 187
 188         /* second step */
 189         traverse_post(blks, post, env);
 190 }
 191
 192 /**
 193  * Do the traversal.
 194  */
 195 static void traverse_blocks(blk_collect_data_t *blks, irg_walk_func *pre, irg_walk_func *post, void *env)
 196 {
 197         if      (!post) traverse_pre (blks, pre, env);
 198         else if (!pre)  traverse_post(blks, post, env);
 199         else            traverse_both(blks, pre, post, env);
 200 }
 201
 202 typedef struct dom_traversal_t {
 203         blk_collect_data_t *blks;
 204         irg_walk_func      *pre;
 205         irg_walk_func      *post;
 206         void               *env;
 207 } dom_traversal_t;
 208
 209 /**
 210  * Dom block walker. Visit all nodes in pre oder.
 211  */
 212 static void dom_block_visit_pre(ir_node *block, void *env)
 213 {
 214         dom_traversal_t *ctx   = (dom_traversal_t*)env;
 215         block_entry_t   *entry = block_find_entry(block, ctx->blks);
 216
 217         traverse_block_pre(block, entry, ctx->pre, ctx->env);
 218 }
 219
 220 /**
 221  * Dom block walker. Visit all nodes in post oder.
 222  */
 223 static void dom_block_visit_post(ir_node *block, void *env)
 224 {
 225         dom_traversal_t *ctx   = (dom_traversal_t*)env;
 226         block_entry_t   *entry = block_find_entry(block, ctx->blks);
 227
 228         traverse_block_post(block, entry, ctx->post, ctx->env);
 229 }
 230
 231 /**
 232  * Dom block walker. Visit all nodes in pre oder, than in post order.
 233  */
 234 static void dom_block_visit_both(ir_node *block, void *env)
 235 {
 236         dom_traversal_t *ctx   = (dom_traversal_t*)env;
 237         block_entry_t   *entry = block_find_entry(block, ctx->blks);
 238
 239         traverse_block_pre(block, entry, ctx->pre, ctx->env);
 240         traverse_block_post(block, entry, ctx->post, ctx->env);
 241 }
 242
 243 /**
 244  * Do the traversal in the dominator tree in top-down order.
 245  */
 246 static void traverse_dom_blocks_top_down(blk_collect_data_t* blks, irg_walk_func *pre, irg_walk_func *post, void *env)
 247 {
 248         dom_traversal_t ctx;
 249
 250         ctx.blks = blks;
 251         ctx.pre  = pre;
 252         ctx.post = post;
 253         ctx.env  = env;
 254
 255         if (pre != NULL && post != NULL)
 256                 dom_tree_walk_irg(current_ir_graph, dom_block_visit_both, NULL, &ctx);
 257         else if (pre != NULL)
 258                 dom_tree_walk_irg(current_ir_graph, dom_block_visit_pre, NULL, &ctx);
 259         else if (post != NULL)
 260                 dom_tree_walk_irg(current_ir_graph, dom_block_visit_post, NULL, &ctx);
 261 }
 262
 263 /**
 264  * walks over the graph and collects all blocks and all block entries
 265  */
 266 static void collect_walk(ir_node *node, blk_collect_data_t *env)
 267 {
 268         int           i, is_phi;
 269         block_entry_t *entry;
 270         ir_node       *block;
 271
 272         mark_irn_visited(node);
 273
 274         if (is_Block(node)) {
 275                 /* predecessors of a block are control flow nodes */
 276                 for (i = _get_walk_arity(env, node) - 1; i >= 0; --i) {
 277                         ir_node *pred = _get_walk_irn_n(env, node, i);
 278                         ir_node *blk  = get_nodes_block(pred);
 279
 280                         if (!irn_visited(pred)) {
 281                                 collect_walk(pred, env);
 282
 283                                 /* control flow predecessors are always block inputs */
 284                                 entry = block_find_entry(blk, env);
 285                                 ARR_APP1(ir_node *, entry->entry_list, pred);
 286                         }
 287                 }
 288
 289                 /* it's a block, put it into the block list */
 290                 if (node == get_irg_end_block(current_ir_graph)) {
 291                         /* Put the end block always last. If we don't do it here,
 292                          * it might be placed elsewhere if the graph contains
 293                          * endless loops.
 294                          */
 295                 } else {
 296                         ARR_APP1(ir_node *, env->blk_list, node);
 297                 }
 298         }
 299         else {
 300                 block = get_nodes_block(node);
 301
 302                 if (!irn_visited(block))
 303                         collect_walk(block, env);
 304
 305                 is_phi = is_Phi(node);
 306                 for (i = _get_walk_arity(env, node) - 1; i >= 0; --i) {
 307                         ir_node *pred = _get_walk_irn_n(env, node, i);
 308
 309                         if (!irn_visited(pred)) {
 310                                 collect_walk(pred, env);
 311
 312                                 /* BEWARE: predecessors of End nodes might be blocks */
 313                                 if (!is_Block(pred)) {
 314                                         ir_node *blk  = get_nodes_block(pred);
 315
 316                                         /*
 317                                          * Note that Phi predecessors are always block entries
 318                                          * because Phi edges are always "outside" a block
 319                                          */
 320                                         if (block != blk || is_phi) {
 321                                                 entry = block_find_entry(blk, env);
 322                                                 ARR_APP1(ir_node *, entry->entry_list, pred);
 323                                         }
 324                                 }
 325                         }
 326                 }
 327         }
 328 }
 329
 330 /**
 331  * walks over the nodes of a block
 332  * and collects them into the right list
 333  */
 334 static void collect_blks_lists(ir_node *node, ir_node *block,
 335                                block_entry_t *entry, blk_collect_data_t *env)
 336 {
 337         int i;
 338
 339         mark_irn_visited(node);
 340
 341         /*
 342          * Do not descent into Phi predecessors, these are always
 343          * outside the current block because Phi edges are always
 344          * "outside".
 345          */
 346         if (! is_Phi(node)) {
 347                 for (i = _get_walk_arity(env, node) - 1; i >= 0; --i) {
 348                         ir_node *pred = _get_walk_irn_n(env, node, i);
 349
 350                         /* BEWARE: predecessors of End nodes might be blocks */
 351                         if (!is_Block(pred)) {
 352                                 ir_node *blk  = get_nodes_block(pred);
 353
 354                                 if (!irn_visited(pred)) {
 355                                         if (block != blk)
 356                                                 continue;
 357                                         collect_blks_lists(pred, block, entry, env);
 358                                 }
 359                         }
 360                 }
 361         } else {
 362                 ARR_APP1(ir_node *, entry->phi_list, node);
 363                 return;
 364         }
 365
 366         if (get_irn_mode(node) == mode_X) {
 367                 ARR_APP1(ir_node *, entry->cf_list, node);
 368         } else {
 369                 ARR_APP1(ir_node *, entry->df_list, node);
 370         }
 371 }
 372
 373 /**
 374  * walk over the graph and collect all lists
 375  */
 376 static void collect_lists(blk_collect_data_t *env)
 377 {
 378         size_t          i, j;
 379         ir_node         *block, *node;
 380         block_entry_t   *entry;
 381
 382         inc_irg_visited(current_ir_graph);
 383
 384         for (i = ARR_LEN(env->blk_list); i > 0;) {
 385                 block = env->blk_list[--i];
 386                 entry = block_find_entry(block, env);
 387
 388                 for (j = ARR_LEN(entry->entry_list); j > 0;) {
 389                         node = entry->entry_list[--j];
 390
 391                         /* a entry might already be visited due to Phi loops */
 392                         if (node->visited < current_ir_graph->visited)
 393                                 collect_blks_lists(node, block, entry, env);
 394                 }
 395         }
 396 }
 397
 398 /**
 399  * Intra procedural graph walker over blocks.
 400  */
 401 static void do_irg_walk_blk(ir_graph *irg, irg_walk_func *pre,
 402         irg_walk_func *post, void *env, unsigned follow_deps,
 403         void (*traverse)(blk_collect_data_t* blks, irg_walk_func *pre, irg_walk_func *post, void *env))
 404 {
 405         ir_node            *end_node = get_irg_end(irg);
 406         ir_node            *end_blk = get_irg_end_block(irg);
 407         blk_collect_data_t blks;
 408         block_entry_t      *entry;
 409
 410         obstack_init(&blks.obst);
 411         blks.blk_map     = new_pset(addr_cmp, 1);
 412         blks.blk_list    = NEW_ARR_F(ir_node *, 0);
 413         blks.follow_deps = follow_deps != 0;
 414
 415         /* first step: traverse the graph and fill the lists */
 416         ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
 417         inc_irg_visited(irg);
 418         collect_walk(end_node, &blks);
 419
 420         /* add the end block */
 421         ARR_APP1(ir_node *, blks.blk_list, end_blk);
 422
 423         /* and the end node */
 424         entry = block_find_entry(end_blk, &blks);
 425         ARR_APP1(ir_node *, entry->entry_list, end_node);
 426
 427         collect_lists(&blks);
 428
 429         /* second step: traverse the list */
 430         traverse(&blks, pre, post, env);
 431
 432         DEL_ARR_F(blks.blk_list);
 433         del_pset(blks.blk_map);
 434         obstack_free(&blks.obst, NULL);
 435
 436         ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
 437 }
 438
 439 void irg_walk_blkwise_graph(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env)
 440 {
 441         ir_graph * rem = current_ir_graph;
 442
 443         hook_irg_walk_blkwise(irg, (generic_func *)pre, (generic_func *)post);
 444         current_ir_graph = irg;
 445         do_irg_walk_blk(irg, pre, post, env, 0, traverse_blocks);
 446         current_ir_graph = rem;
 447 }
 448
 449 void irg_walk_in_or_dep_blkwise_graph(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env)
 450 {
 451         ir_graph * rem = current_ir_graph;
 452
 453         hook_irg_walk_blkwise(irg, (generic_func *)pre, (generic_func *)post);
 454         current_ir_graph = irg;
 455         do_irg_walk_blk(irg, pre, post, env, 1, traverse_blocks);
 456         current_ir_graph = rem;
 457 }
 458
 459 void irg_walk_blkwise_dom_top_down(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env)
 460 {
 461         ir_graph * rem = current_ir_graph;
 462
 463         hook_irg_walk_blkwise(irg, (generic_func *)pre, (generic_func *)post);
 464         current_ir_graph = irg;
 465         do_irg_walk_blk(irg, pre, post, env, 0, traverse_dom_blocks_top_down);
 466         current_ir_graph = rem;
 467 }