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

   1 /*
   2  * Copyright (C) 1995-2011 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_graph *irg = get_irn_irg(node);
 164         ir_graph *rem = current_ir_graph;
 165
 166         current_ir_graph = irg;
 167         ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
 168         inc_irg_visited(irg);
 169         irg_walk_core(node, pre, post, env);
 170         ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
 171         current_ir_graph = rem;
 172 }
 173
 174 /*
 175  * walk over a graph
 176  */
 177 void irg_walk_graph(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env)
 178 {
 179         ir_graph * rem = current_ir_graph;
 180
 181         hook_irg_walk(irg, (generic_func *)pre, (generic_func *)post);
 182         current_ir_graph = irg;
 183         irg_walk(get_irg_end(irg), pre, post, env);
 184         irg->estimated_node_count = nodes_touched;
 185         current_ir_graph = rem;
 186 }
 187
 188 /* Executes irg_walk(end, pre, post, env) for all irgraphs in irprog.
 189    Sets current_ir_graph properly for each walk.  Conserves current
 190    current_ir_graph. */
 191 void all_irg_walk(irg_walk_func *pre, irg_walk_func *post, void *env)
 192 {
 193         size_t i, n;
 194         ir_graph *irg;
 195
 196         for (i = 0, n = get_irp_n_irgs(); i < n; i++) {
 197                 irg = get_irp_irg(i);
 198                 irg_walk_graph(irg, pre, post, env);
 199         }
 200 }
 201
 202 /***************************************************************************/
 203
 204 /**
 205  * specialized version of irg_walk_in_or_dep_2, called if only pre callback exists
 206  *
 207  * @return number of visited nodes
 208  */
 209 static unsigned irg_walk_in_or_dep_2_pre(ir_node *node, irg_walk_func *pre, void *env)
 210 {
 211         int i;
 212         unsigned cnt = 1;
 213         ir_graph *irg = get_irn_irg(node);
 214
 215         set_irn_visited(node, irg->visited);
 216
 217         pre(node, env);
 218
 219         if (node->op != op_Block) {
 220                 ir_node *pred = get_irn_n(node, -1);
 221                 if (pred->visited < irg->visited)
 222                         cnt += irg_walk_in_or_dep_2_pre(pred, pre, env);
 223         }
 224         for (i = get_irn_ins_or_deps(node) - 1; i >= 0; --i) {
 225                 ir_node *pred = get_irn_in_or_dep(node, i);
 226                 if (pred->visited < irg->visited)
 227                         cnt += irg_walk_in_or_dep_2_pre(pred, pre, env);
 228         }
 229         return cnt;
 230 }
 231
 232 /**
 233  * specialized version of irg_walk_in_or_dep_2, called if only post callback exists
 234  *
 235  * @return number of visited nodes
 236  */
 237 static unsigned irg_walk_in_or_dep_2_post(ir_node *node, irg_walk_func *post, void *env)
 238 {
 239         int i;
 240         unsigned cnt = 1;
 241         ir_graph *irg = get_irn_irg(node);
 242
 243         set_irn_visited(node, irg->visited);
 244
 245         if (node->op != op_Block) {
 246                 ir_node *pred = get_irn_n(node, -1);
 247                 if (pred->visited < irg->visited)
 248                         cnt += irg_walk_in_or_dep_2_post(pred, post, env);
 249         }
 250         for (i = get_irn_ins_or_deps(node) - 1; i >= 0; --i) {
 251                 ir_node *pred = get_irn_in_or_dep(node, i);
 252                 if (pred->visited < irg->visited)
 253                         cnt += irg_walk_in_or_dep_2_post(pred, post, env);
 254         }
 255
 256         post(node, env);
 257
 258         return cnt;
 259 }
 260
 261 /**
 262  * specialized version of irg_walk_in_or_dep_2, called if pre and post callbacks exist
 263  *
 264  * @return number of visited nodes
 265  */
 266 static unsigned irg_walk_in_or_dep_2_both(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env)
 267 {
 268         int i;
 269         unsigned cnt = 1;
 270         ir_graph *irg = get_irn_irg(node);
 271
 272         set_irn_visited(node, irg->visited);
 273
 274         pre(node, env);
 275
 276         if (node->op != op_Block) {
 277                 ir_node *pred = get_irn_n(node, -1);
 278                 if (pred->visited < irg->visited)
 279                         cnt += irg_walk_in_or_dep_2_both(pred, pre, post, env);
 280         }
 281         for (i = get_irn_ins_or_deps(node) - 1; i >= 0; --i) {
 282                 ir_node *pred = get_irn_in_or_dep(node, i);
 283                 if (pred->visited < irg->visited)
 284                         cnt += irg_walk_in_or_dep_2_both(pred, pre, post, env);
 285         }
 286
 287         post(node, env);
 288
 289         return cnt;
 290 }
 291
 292 /**
 293  * Intraprozedural graph walker. Follows dependency edges as well.
 294  *
 295  * @return number of visited nodes
 296  */
 297 static unsigned irg_walk_in_or_dep_2(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env)
 298 {
 299         if (irn_visited(node))
 300                 return 0;
 301
 302         if      (! post) return irg_walk_in_or_dep_2_pre (node, pre, env);
 303         else if (! pre)  return irg_walk_in_or_dep_2_post(node, post, env);
 304         else             return irg_walk_in_or_dep_2_both(node, pre, post, env);
 305 }
 306
 307 /*
 308  * Generic graph walker. Follows dependency edges as well.
 309  */
 310 void irg_walk_in_or_dep(ir_node *node, irg_walk_func *pre, irg_walk_func *post, void *env)
 311 {
 312         assert(is_ir_node(node));
 313
 314         ir_reserve_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED);
 315         inc_irg_visited(current_ir_graph);
 316         nodes_touched = irg_walk_in_or_dep_2(node, pre, post, env);
 317         ir_free_resources(current_ir_graph, IR_RESOURCE_IRN_VISITED);
 318 }
 319
 320 /*
 321  * Walk over a graph. Follow all edges (including dependencies)
 322  */
 323 void irg_walk_in_or_dep_graph(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env)
 324 {
 325         ir_graph * rem = current_ir_graph;
 326
 327         hook_irg_walk(irg, (generic_func *)pre, (generic_func *)post);
 328         current_ir_graph = irg;
 329         irg_walk_in_or_dep(get_irg_end(irg), pre, post, env);
 330         irg->estimated_node_count = nodes_touched;
 331         current_ir_graph = rem;
 332 }
 333
 334 /***************************************************************************/
 335
 336 /* Walks back from n until it finds a real cf op. */
 337 static ir_node *get_cf_op(ir_node *n)
 338 {
 339         while (!is_cfop(n) && !is_fragile_op(n) && !is_Bad(n)) {
 340                 n = skip_Id(n);
 341                 n = skip_Tuple(n);
 342                 n = skip_Proj(n);
 343         }
 344         return n;
 345 }
 346
 347 static void irg_block_walk_2(ir_node *node, irg_walk_func *pre,
 348                              irg_walk_func *post, void *env)
 349 {
 350         int i;
 351
 352         if (Block_block_visited(node))
 353                 return;
 354         mark_Block_block_visited(node);
 355
 356         if (pre)
 357                 pre(node, env);
 358
 359         for (i = get_Block_n_cfgpreds(node) - 1; i >= 0; --i) {
 360                 /* find the corresponding predecessor block. */
 361                 ir_node *pred = get_cf_op(get_Block_cfgpred(node, i));
 362                 pred = get_nodes_block(pred);
 363                 if (get_irn_opcode(pred) == iro_Block) {
 364                         /* recursion */
 365                         irg_block_walk_2(pred, pre, post, env);
 366                 } else {
 367                         assert(get_irn_opcode(pred) == iro_Bad);
 368                 }
 369         }
 370
 371         if (post)
 372                 post(node, env);
 373 }
 374
 375
 376 /* walks only over Block nodes in the graph.  Has its own visited
 377    flag, so that it can be interleaved with the other walker.         */
 378 void irg_block_walk(ir_node *node, irg_walk_func *pre, irg_walk_func *post,
 379                     void *env)
 380 {
 381         ir_graph *irg   = get_irn_irg(node);
 382         ir_node  *block = is_Block(node) ? node : get_nodes_block(node);
 383
 384         hook_irg_block_walk(irg, node, (generic_func *)pre, (generic_func *)post);
 385
 386         ir_reserve_resources(irg, IR_RESOURCE_BLOCK_VISITED);
 387         inc_irg_block_visited(irg);
 388         irg_block_walk_2(block, pre, post, env);
 389
 390         /* Some blocks might be only reachable through keep-alive edges */
 391         if (is_End(node)) {
 392                 int arity = get_irn_arity(node);
 393                 int i;
 394                 for (i = 0; i < arity; i++) {
 395                         ir_node *pred = get_irn_n(node, i);
 396                         if (!is_Block(pred))
 397                                 continue;
 398                         irg_block_walk_2(pred, pre, post, env);
 399                 }
 400         }
 401
 402         ir_free_resources(irg, IR_RESOURCE_BLOCK_VISITED);
 403 }
 404
 405 /*
 406  * walk over a graph block wise
 407  */
 408 void irg_block_walk_graph(ir_graph *irg, irg_walk_func *pre,
 409                           irg_walk_func *post, void *env)
 410 {
 411         ir_graph * rem = current_ir_graph;
 412         current_ir_graph = irg;
 413         irg_block_walk(get_irg_end(irg), pre, post, env);
 414         current_ir_graph = rem;
 415 }
 416
 417 /*
 418  * Additionally walk over all anchors. Do NOT increase the visit flag.
 419  */
 420 void irg_walk_anchors(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env)
 421 {
 422         ir_graph * rem = current_ir_graph;
 423         current_ir_graph = irg;
 424
 425         inc_irg_visited(irg);
 426         irg_walk_2(irg->anchor, pre, post, env);
 427
 428         current_ir_graph = rem;
 429 }
 430
 431 /********************************************************************/
 432
 433 typedef struct walk_env {
 434         irg_walk_func *pre;
 435         irg_walk_func *post;
 436         void *env;
 437 } walk_env;
 438
 439 static void walk_initializer(ir_initializer_t *initializer, walk_env *env)
 440 {
 441         switch (initializer->kind) {
 442     case IR_INITIALIZER_CONST:
 443                 irg_walk(initializer->consti.value, env->pre, env->post, env->env);
 444         return;
 445     case IR_INITIALIZER_TARVAL:
 446     case IR_INITIALIZER_NULL:
 447         return;
 448
 449     case IR_INITIALIZER_COMPOUND: {
 450         size_t i;
 451         for (i = 0; i < initializer->compound.n_initializers; ++i) {
 452             ir_initializer_t *subinitializer
 453                 = initializer->compound.initializers[i];
 454             walk_initializer(subinitializer, env);
 455         }
 456         return;
 457     }
 458         }
 459         panic("invalid initializer found");
 460 }
 461
 462 /**
 463  * Walk to all constant expressions in this entity.
 464  */
 465 static void walk_entity(ir_entity *ent, void *env)
 466 {
 467         walk_env *my_env = (walk_env *)env;
 468
 469         if (ent->initializer != NULL) {
 470                 walk_initializer(ent->initializer, my_env);
 471         } else if (entity_has_compound_ent_values(ent)) {
 472                 size_t i, n_vals = get_compound_ent_n_values(ent);
 473
 474                 for (i = 0; i < n_vals; i++)
 475                         irg_walk(get_compound_ent_value(ent, i), my_env->pre, my_env->post, my_env->env);
 476         }
 477 }
 478
 479 /* Walks over all code in const_code_irg. */
 480 void walk_const_code(irg_walk_func *pre, irg_walk_func *post, void *env)
 481 {
 482         walk_env my_env;
 483         ir_segment_t s;
 484         size_t i;
 485         size_t n_types;
 486
 487         ir_graph *rem = current_ir_graph;
 488         current_ir_graph = get_const_code_irg();
 489         inc_irg_visited(current_ir_graph);
 490
 491         my_env.pre = pre;
 492         my_env.post = post;
 493         my_env.env = env;
 494
 495         /* Walk all types that can contain constant entities.  */
 496         for (s = IR_SEGMENT_FIRST; s <= IR_SEGMENT_LAST; ++s)
 497                 walk_types_entities(get_segment_type(s), &walk_entity, &my_env);
 498         n_types = get_irp_n_types();
 499         for (i = 0; i < n_types; i++)
 500                 walk_types_entities(get_irp_type(i), &walk_entity, &my_env);
 501         for (i = 0; i < get_irp_n_irgs(); i++)
 502                 walk_types_entities(get_irg_frame_type(get_irp_irg(i)), &walk_entity, &my_env);
 503
 504         /* Walk constant array bounds. */
 505         for (i = 0; i < n_types; i++) {
 506                 ir_type *tp = get_irp_type(i);
 507                 if (is_Array_type(tp)) {
 508                         size_t j, n_dim = get_array_n_dimensions(tp);
 509                         for (j = 0; j < n_dim; j++) {
 510                                 ir_node *n = get_array_lower_bound(tp, j);
 511                                 if (n) irg_walk(n, pre, post, env);
 512                                 n = get_array_upper_bound(tp, j);
 513                                 if (n) irg_walk(n, pre, post, env);
 514                         }
 515                 }
 516         }
 517
 518         current_ir_graph = rem;
 519 }