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