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) return irg_walk_in_or_dep_2_pre (node, pre, env);
 256         else if (! pre)  return irg_walk_in_or_dep_2_post(node, post, env);
 257         else             return 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_Id(n);
 285                 n = skip_Tuple(n);
 286                 n = skip_Proj(n);
 287         }
 288         return n;
 289 }
 290
 291 static void irg_block_walk_2(ir_node *node, irg_walk_func *pre,
 292                              irg_walk_func *post, void *env)
 293 {
 294         int i;
 295
 296         if (Block_block_visited(node))
 297                 return;
 298         mark_Block_block_visited(node);
 299
 300         if (pre)
 301                 pre(node, env);
 302
 303         for (i = get_Block_n_cfgpreds(node) - 1; i >= 0; --i) {
 304                 /* find the corresponding predecessor block. */
 305                 ir_node *pred = get_cf_op(get_Block_cfgpred(node, i));
 306                 pred = get_nodes_block(pred);
 307                 if (get_irn_opcode(pred) == iro_Block) {
 308                         /* recursion */
 309                         irg_block_walk_2(pred, pre, post, env);
 310                 } else {
 311                         assert(get_irn_opcode(pred) == iro_Bad);
 312                 }
 313         }
 314
 315         if (post)
 316                 post(node, env);
 317 }
 318
 319 void irg_block_walk(ir_node *node, irg_walk_func *pre, irg_walk_func *post,
 320                     void *env)
 321 {
 322         ir_graph *irg   = get_irn_irg(node);
 323         ir_node  *block = is_Block(node) ? node : get_nodes_block(node);
 324
 325         hook_irg_block_walk(irg, node, (generic_func *)pre, (generic_func *)post);
 326
 327         ir_reserve_resources(irg, IR_RESOURCE_BLOCK_VISITED);
 328         inc_irg_block_visited(irg);
 329         irg_block_walk_2(block, pre, post, env);
 330
 331         /* Some blocks might be only reachable through keep-alive edges */
 332         if (is_End(node)) {
 333                 int arity = get_irn_arity(node);
 334                 int i;
 335                 for (i = 0; i < arity; i++) {
 336                         ir_node *pred = get_irn_n(node, i);
 337                         if (!is_Block(pred))
 338                                 continue;
 339                         irg_block_walk_2(pred, pre, post, env);
 340                 }
 341         }
 342
 343         ir_free_resources(irg, IR_RESOURCE_BLOCK_VISITED);
 344 }
 345
 346 void irg_block_walk_graph(ir_graph *irg, irg_walk_func *pre,
 347                           irg_walk_func *post, void *env)
 348 {
 349         ir_graph * rem = current_ir_graph;
 350         current_ir_graph = irg;
 351         irg_block_walk(get_irg_end(irg), pre, post, env);
 352         current_ir_graph = rem;
 353 }
 354
 355 void irg_walk_anchors(ir_graph *irg, irg_walk_func *pre, irg_walk_func *post, void *env)
 356 {
 357         ir_graph * rem = current_ir_graph;
 358         current_ir_graph = irg;
 359
 360         ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
 361         inc_irg_visited(irg);
 362         irg_walk_2(irg->anchor, pre, post, env);
 363         ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
 364
 365         current_ir_graph = rem;
 366 }
 367
 368 typedef struct walk_env {
 369         irg_walk_func *pre;
 370         irg_walk_func *post;
 371         void *env;
 372 } walk_env;
 373
 374 static void walk_initializer(ir_initializer_t *initializer, walk_env *env)
 375 {
 376         switch (initializer->kind) {
 377     case IR_INITIALIZER_CONST:
 378                 irg_walk(initializer->consti.value, env->pre, env->post, env->env);
 379         return;
 380     case IR_INITIALIZER_TARVAL:
 381     case IR_INITIALIZER_NULL:
 382         return;
 383
 384     case IR_INITIALIZER_COMPOUND: {
 385         size_t i;
 386         for (i = 0; i < initializer->compound.n_initializers; ++i) {
 387             ir_initializer_t *subinitializer
 388                 = initializer->compound.initializers[i];
 389             walk_initializer(subinitializer, env);
 390         }
 391         return;
 392     }
 393         }
 394         panic("invalid initializer found");
 395 }
 396
 397 /**
 398  * Walk to all constant expressions in this entity.
 399  */
 400 static void walk_entity(ir_entity *ent, void *env)
 401 {
 402         walk_env *my_env = (walk_env *)env;
 403
 404         if (ent->initializer != NULL) {
 405                 walk_initializer(ent->initializer, my_env);
 406         }
 407 }
 408
 409 void walk_const_code(irg_walk_func *pre, irg_walk_func *post, void *env)
 410 {
 411         walk_env my_env;
 412         ir_segment_t s;
 413         size_t i;
 414         size_t n_types;
 415
 416         ir_graph *rem = current_ir_graph;
 417         current_ir_graph = get_const_code_irg();
 418         inc_irg_visited(current_ir_graph);
 419
 420         my_env.pre = pre;
 421         my_env.post = post;
 422         my_env.env = env;
 423
 424         /* Walk all types that can contain constant entities.  */
 425         for (s = IR_SEGMENT_FIRST; s <= IR_SEGMENT_LAST; ++s)
 426                 walk_types_entities(get_segment_type(s), &walk_entity, &my_env);
 427         n_types = get_irp_n_types();
 428         for (i = 0; i < n_types; i++)
 429                 walk_types_entities(get_irp_type(i), &walk_entity, &my_env);
 430         for (i = 0; i < get_irp_n_irgs(); i++)
 431                 walk_types_entities(get_irg_frame_type(get_irp_irg(i)), &walk_entity, &my_env);
 432
 433         /* Walk constant array bounds. */
 434         for (i = 0; i < n_types; i++) {
 435                 ir_type *tp = get_irp_type(i);
 436                 if (is_Array_type(tp)) {
 437                         size_t j, n_dim = get_array_n_dimensions(tp);
 438                         for (j = 0; j < n_dim; j++) {
 439                                 ir_node *n = get_array_lower_bound(tp, j);
 440                                 if (n) irg_walk(n, pre, post, env);
 441                                 n = get_array_upper_bound(tp, j);
 442                                 if (n) irg_walk(n, pre, post, env);
 443                         }
 444                 }
 445         }
 446
 447         current_ir_graph = rem;
 448 }