nsz Git - libfirm/blob - ir/ir/irgwalk.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   Functions for traversing ir graphs
  23  * @author  Boris Boesler, Goetz Lindenmaier, Michael Beck
  24  * @version $Id$
  25  * @brief
  26  *  traverse an ir graph
  27  *  - execute the pre function before recursion
  28  *  - execute the post function after recursion
  29  */
  30 #include "config.h"
  31
  32 #include <stdlib.h>
  33
  34 #include "irnode_t.h"
  35 #include "irgraph_t.h"
  36 #include "irprog.h"
  37 #include "irgwalk.h"
  38 #include "irhooks.h"
  39 #include "entity_t.h"
  40
  41 #include "error.h"
  42 #include "pset_new.h"
  43 #include "array.h"
  44
  45 /**
  46  * specialized version of irg_walk_2, called if only pre callback exists
  47  *
  48  * @return number of visited nodes
  49  */
  50 static unsigned irg_walk_2_pre(ir_node *node, irg_walk_func *pre, void *env)
  51 {
  52         int i;
  53         unsigned cnt = 1;
  54         ir_graph *irg = get_irn_irg(node);
  55
  56         set_irn_visited(node, irg->visited);
  57
  58         pre(node, env);
  59
  60         if (node->op != op_Block) {
  61                 ir_node *pred = get_irn_n(node, -1);
  62                 if (pred->visited < irg->visited)
  63                         cnt += irg_walk_2_pre(pred, pre, env);
  64         }
  65         for (i = get_irn_arity(node) - 1; i >= 0; --i) {
  66                 ir_node *pred = get_irn_n(node, i);
  67                 if (pred->visited < irg->visited)
  68                         cnt += irg_walk_2_pre(pred, pre, env);
  69         }
  70         return cnt;
  71 }
  72
  73 /**
  74  * specialized version of irg_walk_2, called if only post callback exists
  75  *
  76  * @return number of visited nodes
  77  */
  78 static unsigned irg_walk_2_post(ir_node *node, irg_walk_func *post, void *env)
  79 {
  80         int i;
  81         unsigned cnt = 1;
  82         ir_graph *irg = get_irn_irg(node);
  83
  84         set_irn_visited(node, irg->visited);
  85
  86         if (node->op != op_Block) {
  87                 ir_node *pred = get_irn_n(node, -1);
  88                 if (pred->visited < irg->visited)
  89                         cnt += irg_walk_2_post(pred, post, env);
  90         }
  91         for (i = get_irn_arity(node) - 1; i >= 0; --i) {
  92                 ir_node *pred = get_irn_n(node, i);
  93                 if (pred->visited < irg->visited)
  94                         cnt += irg_walk_2_post(pred, post, env);
  95         }
  96
  97         post(node, env);
  98
  99         return cnt;
 100 }
 101
 102 /**
 103  * specialized version of irg_walk_2, called if pre and post callbacks exist
 104  *
 105  * @return number of visited nodes
 106  */
 107 static unsigned irg_walk_2_both(ir_node *node, irg_walk_func *pre,
 108                                 irg_walk_func *post, void *env)
 109 {
 110         int i;
 111         unsigned cnt = 1;
 112         ir_graph *irg = get_irn_irg(node);
 113
 114         set_irn_visited(node, irg->visited);
 115
 116         pre(node, env);
 117
 118         if (node->op != op_Block) {
 119                 ir_node *pred = get_irn_n(node, -1);
 120                 if (pred->visited < irg->visited)
 121                         cnt += irg_walk_2_both(pred, pre, post, env);
 122         }
 123         for (i = get_irn_arity(node) - 1; i >= 0; --i) {
 124                 ir_node *pred = get_irn_n(node, i);
 125                 if (pred->visited < irg->visited)
 126                         cnt += irg_walk_2_both(pred, pre, post, env);
 127         }
 128
 129         post(node, env);
 130
 131         return cnt;
 132 }
 133
 134 /**
 135  * Intraprozedural graph walker.
 136  *
 137  * @return number of visited nodes
 138  */
 139 unsigned irg_walk_2(ir_node *node, irg_walk_func *pre, irg_walk_func *post,
 140                     void *env)
 141 {
 142         if (irn_visited(node))
 143                 return 0;
 144
 145         if      (!post) return irg_walk_2_pre (node, pre, env);
 146         else if (!pre)  return irg_walk_2_post(node, post, env);
 147         else            return irg_walk_2_both(node, pre, post, env);
 148 }
 149
 150 /* a counter */
 151 static unsigned nodes_touched = 0;
 152
 153 void irg_walk_core(ir_node *node, irg_walk_func *pre, irg_walk_func *post,
 154                    void *env)
 155 {
 156         assert(is_ir_node(node));
 157         nodes_touched = irg_walk_2(node, pre, post, env);
 158 }
 159
 160 void irg_walk(ir_node *node, irg_walk_func *pre, irg_walk_func *post,
 161               void *env)
 162 {
 163         ir_reserve_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED);
 164         inc_irg_visited(current_ir_graph);
 165         assert(current_ir_graph == get_irn_irg(node));
 166         irg_walk_core(node, pre, post, env);
 167         ir_free_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED);
 168 }
 169
 170 /*
 171  * walk over a graph
 172  */
 173 void irg_walk_graph(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env)
 174 {
 175         ir_graph * rem = current_ir_graph;
 176
 177         hook_irg_walk(irg, (generic_func *)pre, (generic_func *)post);
 178         current_ir_graph = irg;
 179         irg_walk(get_irg_end(irg), pre, post, env);
 180         irg->estimated_node_count = nodes_touched;
 181         current_ir_graph = rem;
 182 }
 183
 184 /* Executes irg_walk(end, pre, post, env) for all irgraphs in irprog.
 185    Sets current_ir_graph properly for each walk.  Conserves current
 186    current_ir_graph. */
 187 void all_irg_walk(irg_walk_func *pre, irg_walk_func *post, void *env)
 188 {
 189         int i, n;
 190         ir_graph *irg;
 191
 192         for (i = 0, n = get_irp_n_irgs(); i < n; i++) {
 193                 irg = get_irp_irg(i);
 194                 irg_walk_graph(irg, pre, post, env);
 195         }
 196 }
 197
 198 /***************************************************************************/
 199
 200 /**
 201  * specialized version of irg_walk_in_or_dep_2, called if only pre callback exists
 202  *
 203  * @return number of visited nodes
 204  */
 205 static unsigned irg_walk_in_or_dep_2_pre(ir_node *node, irg_walk_func *pre, void *env)
 206 {
 207         int i;
 208         unsigned cnt = 1;
 209         ir_graph *irg = get_irn_irg(node);
 210
 211         set_irn_visited(node, irg->visited);
 212
 213         pre(node, env);
 214
 215         if (node->op != op_Block) {
 216                 ir_node *pred = get_irn_n(node, -1);
 217                 if (pred->visited < irg->visited)
 218                         cnt += irg_walk_in_or_dep_2_pre(pred, pre, env);
 219         }
 220         for (i = get_irn_ins_or_deps(node) - 1; i >= 0; --i) {
 221                 ir_node *pred = get_irn_in_or_dep(node, i);
 222                 if (pred->visited < irg->visited)
 223                         cnt += irg_walk_in_or_dep_2_pre(pred, pre, env);
 224         }
 225         return cnt;
 226 }
 227
 228 /**
 229  * specialized version of irg_walk_in_or_dep_2, called if only post callback exists
 230  *
 231  * @return number of visited nodes
 232  */
 233 static unsigned irg_walk_in_or_dep_2_post(ir_node *node, irg_walk_func *post, void *env)
 234 {
 235         int i;
 236         unsigned cnt = 1;
 237         ir_graph *irg = get_irn_irg(node);
 238
 239         set_irn_visited(node, irg->visited);
 240
 241         if (node->op != op_Block) {
 242                 ir_node *pred = get_irn_n(node, -1);
 243                 if (pred->visited < irg->visited)
 244                         cnt += irg_walk_in_or_dep_2_post(pred, post, env);
 245         }
 246         for (i = get_irn_ins_or_deps(node) - 1; i >= 0; --i) {
 247                 ir_node *pred = get_irn_in_or_dep(node, i);
 248                 if (pred->visited < irg->visited)
 249                         cnt += irg_walk_in_or_dep_2_post(pred, post, env);
 250         }
 251
 252         post(node, env);
 253
 254         return cnt;
 255 }
 256
 257 /**
 258  * specialized version of irg_walk_in_or_dep_2, called if pre and post callbacks exist
 259  *
 260  * @return number of visited nodes
 261  */
 262 static unsigned irg_walk_in_or_dep_2_both(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env)
 263 {
 264         int i;
 265         unsigned cnt = 1;
 266         ir_graph *irg = get_irn_irg(node);
 267
 268         set_irn_visited(node, irg->visited);
 269
 270         pre(node, env);
 271
 272         if (node->op != op_Block) {
 273                 ir_node *pred = get_irn_n(node, -1);
 274                 if (pred->visited < irg->visited)
 275                         cnt += irg_walk_in_or_dep_2_both(pred, pre, post, env);
 276         }
 277         for (i = get_irn_ins_or_deps(node) - 1; i >= 0; --i) {
 278                 ir_node *pred = get_irn_in_or_dep(node, i);
 279                 if (pred->visited < irg->visited)
 280                         cnt += irg_walk_in_or_dep_2_both(pred, pre, post, env);
 281         }
 282
 283         post(node, env);
 284
 285         return cnt;
 286 }
 287
 288 /**
 289  * Intraprozedural graph walker. Follows dependency edges as well.
 290  *
 291  * @return number of visited nodes
 292  */
 293 static unsigned irg_walk_in_or_dep_2(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env)
 294 {
 295         if (irn_visited(node))
 296                 return 0;
 297
 298         if      (! post) return irg_walk_in_or_dep_2_pre (node, pre, env);
 299         else if (! pre)  return irg_walk_in_or_dep_2_post(node, post, env);
 300         else             return irg_walk_in_or_dep_2_both(node, pre, post, env);
 301 }
 302
 303 /*
 304  * Generic graph walker. Follows dependency edges as well.
 305  */
 306 void irg_walk_in_or_dep(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env)
 307 {
 308         assert(is_ir_node(node));
 309
 310         ir_reserve_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED);
 311         inc_irg_visited(current_ir_graph);
 312         nodes_touched = irg_walk_in_or_dep_2(node, pre, post, env);
 313         ir_free_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED);
 314 }
 315
 316 /*
 317  * Walk over a graph. Follow all edges (including dependencies)
 318  */
 319 void irg_walk_in_or_dep_graph(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env)
 320 {
 321         ir_graph * rem = current_ir_graph;
 322
 323         hook_irg_walk(irg, (generic_func *)pre, (generic_func *)post);
 324         current_ir_graph = irg;
 325         irg_walk_in_or_dep(get_irg_end(irg), pre, post, env);
 326         irg->estimated_node_count = nodes_touched;
 327         current_ir_graph = rem;
 328 }
 329
 330 /***************************************************************************/
 331
 332 /* Walks back from n until it finds a real cf op. */
 333 static ir_node *get_cf_op(ir_node *n)
 334 {
 335         while (!is_cfop(n) && !is_fragile_op(n) && !is_Bad(n)) {
 336                 n = skip_Id(n);
 337                 n = skip_Tuple(n);
 338                 n = skip_Proj(n);
 339         }
 340         return n;
 341 }
 342
 343 static void irg_block_walk_2(ir_node *node, irg_walk_func *pre,
 344                              irg_walk_func *post, void *env)
 345 {
 346         int i;
 347
 348         if (Block_block_visited(node))
 349                 return;
 350         mark_Block_block_visited(node);
 351
 352         if (pre)
 353                 pre(node, env);
 354
 355         for (i = get_Block_n_cfgpreds(node) - 1; i >= 0; --i) {
 356                 /* find the corresponding predecessor block. */
 357                 ir_node *pred = get_cf_op(get_Block_cfgpred(node, i));
 358                 pred = get_nodes_block(pred);
 359                 if (get_irn_opcode(pred) == iro_Block) {
 360                         /* recursion */
 361                         irg_block_walk_2(pred, pre, post, env);
 362                 } else {
 363                         assert(get_irn_opcode(pred) == iro_Bad);
 364                 }
 365         }
 366
 367         if (post)
 368                 post(node, env);
 369 }
 370
 371
 372 /* walks only over Block nodes in the graph.  Has it's own visited
 373    flag, so that it can be interleaved with the other walker.         */
 374 void irg_block_walk(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env)
 375 {
 376         ir_graph *irg = get_irn_irg(node);
 377         ir_node *block, *pred;
 378         int i;
 379
 380         hook_irg_block_walk(irg, node, (generic_func *)pre, (generic_func *)post);
 381
 382         assert(node);
 383         ir_reserve_resources(irg, IR_RESOURCE_BLOCK_VISITED);
 384         inc_irg_block_visited(irg);
 385         block = is_Block(node) ? node : get_nodes_block(node);
 386         assert(is_Block(block));
 387         irg_block_walk_2(block, pre, post, env);
 388
 389         /* keepalive: the endless loops ... */
 390         if (is_End(node)) {
 391                 int arity = get_irn_arity(node);
 392                 for (i = 0; i < arity; i++) {
 393                         pred = get_irn_n(node, i);
 394                         if (!is_Block(pred)) {
 395                                 pred = get_nodes_block(pred);
 396                                 if (!is_Block(pred)) {
 397                                         /* if rare cases a kept node might have a bad block input */
 398                                         continue;
 399                                 }
 400                         }
 401                         /* Sometimes the blocks died, but are still reachable through kept nodes.
 402                          * Make sure the algorithms that try to remove these reach them. */
 403                         irg_block_walk_2(pred, pre, post, env);
 404                 }
 405         }
 406
 407         ir_free_resources(irg, IR_RESOURCE_BLOCK_VISITED);
 408 }
 409
 410 /*
 411  * walk over a graph block wise
 412  */
 413 void irg_block_walk_graph(ir_graph *irg, irg_walk_func *pre,
 414                           irg_walk_func *post, void *env)
 415 {
 416         ir_graph * rem = current_ir_graph;
 417         current_ir_graph = irg;
 418         irg_block_walk(get_irg_end(irg), pre, post, env);
 419         current_ir_graph = rem;
 420 }
 421
 422 /*
 423  * Additionally walk over all anchors. Do NOT increase the visit flag.
 424  */
 425 void irg_walk_anchors(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env)
 426 {
 427         ir_graph * rem = current_ir_graph;
 428         current_ir_graph = irg;
 429
 430         inc_irg_visited(irg);
 431         irg_walk_2(irg->anchor, pre, post, env);
 432
 433         current_ir_graph = rem;
 434 }
 435
 436 /********************************************************************/
 437
 438 typedef struct walk_env {
 439         irg_walk_func *pre;
 440         irg_walk_func *post;
 441         void *env;
 442 } walk_env;
 443
 444 static void walk_initializer(ir_initializer_t *initializer, walk_env *env)
 445 {
 446         switch (initializer->kind) {
 447     case IR_INITIALIZER_CONST:
 448                 irg_walk(initializer->consti.value, env->pre, env->post, env->env);
 449         return;
 450     case IR_INITIALIZER_TARVAL:
 451     case IR_INITIALIZER_NULL:
 452         return;
 453
 454     case IR_INITIALIZER_COMPOUND: {
 455         size_t i;
 456         for (i = 0; i < initializer->compound.n_initializers; ++i) {
 457             ir_initializer_t *subinitializer
 458                 = initializer->compound.initializers[i];
 459             walk_initializer(subinitializer, env);
 460         }
 461         return;
 462     }
 463         }
 464         panic("invalid initializer found");
 465 }
 466
 467 /**
 468  * Walk to all constant expressions in this entity.
 469  */
 470 static void walk_entity(ir_entity *ent, void *env)
 471 {
 472         walk_env *my_env = (walk_env *)env;
 473
 474         if (ent->initializer != NULL) {
 475                 walk_initializer(ent->initializer, my_env);
 476         } else if (entity_has_compound_ent_values(ent)) {
 477                 int i, n_vals = get_compound_ent_n_values(ent);
 478
 479                 for (i = 0; i < n_vals; i++)
 480                         irg_walk(get_compound_ent_value(ent, i), my_env->pre, my_env->post, my_env->env);
 481         }
 482 }
 483
 484 /* Walks over all code in const_code_irg. */
 485 void walk_const_code(irg_walk_func *pre, irg_walk_func *post, void *env)
 486 {
 487         int i, j, n_types;
 488         walk_env my_env;
 489         ir_segment_t s;
 490
 491         ir_graph *rem = current_ir_graph;
 492         current_ir_graph = get_const_code_irg();
 493         inc_irg_visited(current_ir_graph);
 494
 495         my_env.pre = pre;
 496         my_env.post = post;
 497         my_env.env = env;
 498
 499         /* Walk all types that can contain constant entities.  */
 500         for (s = IR_SEGMENT_FIRST; s <= IR_SEGMENT_LAST; s++)
 501                 walk_types_entities(get_segment_type(s), &walk_entity, &my_env);
 502         n_types = get_irp_n_types();
 503         for (i = 0; i < n_types; i++)
 504                 walk_types_entities(get_irp_type(i), &walk_entity, &my_env);
 505         for (i = 0; i < get_irp_n_irgs(); i++)
 506                 walk_types_entities(get_irg_frame_type(get_irp_irg(i)), &walk_entity, &my_env);
 507
 508         /* Walk constant array bounds. */
 509         for (i = 0; i < n_types; i++) {
 510                 ir_type *tp = get_irp_type(i);
 511                 if (is_Array_type(tp)) {
 512                         int n_dim = get_array_n_dimensions(tp);
 513                         for (j = 0; j < n_dim; j++) {
 514                                 ir_node *n = get_array_lower_bound(tp, j);
 515                                 if (n) irg_walk(n, pre, post, env);
 516                                 n = get_array_upper_bound(tp, j);
 517                                 if (n) irg_walk(n, pre, post, env);
 518                         }
 519                 }
 520         }
 521
 522         current_ir_graph = rem;
 523 }