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

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