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