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