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