nsz Git - libfirm/blob - ir/ana/irouts.c

   1 /*
   2  * This file is part of libFirm.
   3  * Copyright (C) 2012 University of Karlsruhe.
   4  */
   5
   6 /**
   7  * @file
   8  * @brief    Compute and access out edges (also called def-use edges).
   9  * @author   Goetz Lindenmaier, Michael Beck
  10  * @date     1.2002
  11  */
  12 #include "config.h"
  13
  14 #include <string.h>
  15
  16 #include "xmalloc.h"
  17 #include "irouts.h"
  18 #include "irnode_t.h"
  19 #include "irgraph_t.h"
  20 #include "irprog_t.h"
  21 #include "irgwalk.h"
  22 #include "util.h"
  23 #include "irprintf.h"
  24 #include "error.h"
  25 #include "ircons.h"
  26
  27 unsigned get_irn_n_outs(const ir_node *node)
  28 {
  29         return node->o.out->n_edges;
  30 }
  31
  32 ir_node *get_irn_out(const ir_node *def, unsigned pos)
  33 {
  34         assert(pos < get_irn_n_outs(def));
  35         return def->o.out->edges[pos].use;
  36 }
  37
  38 ir_node *get_irn_out_ex(const ir_node *def, unsigned pos, int *in_pos)
  39 {
  40         assert(pos < get_irn_n_outs(def));
  41         *in_pos = def->o.out->edges[pos].pos;
  42         return def->o.out->edges[pos].use;
  43 }
  44
  45 void set_irn_out(ir_node *def, unsigned pos, ir_node *use, int in_pos)
  46 {
  47         assert(use != NULL);
  48         assert(pos < get_irn_n_outs(def));
  49         def->o.out->edges[pos].use = use;
  50         def->o.out->edges[pos].pos = in_pos;
  51 }
  52
  53 unsigned get_Block_n_cfg_outs(const ir_node *bl)
  54 {
  55         assert(is_Block(bl));
  56         unsigned n_cfg_outs = 0;
  57         for (unsigned i = 0; i < get_irn_n_outs(bl); ++i) {
  58                 const ir_node *succ = get_irn_out(bl, i);
  59                 if (get_irn_mode(succ) != mode_X)
  60                         continue;
  61                 if (is_End(succ) || is_Bad(succ))
  62                         continue;
  63                 n_cfg_outs += get_irn_n_outs(succ);
  64         }
  65         return n_cfg_outs;
  66 }
  67
  68 unsigned get_Block_n_cfg_outs_ka(const ir_node *bl)
  69 {
  70         assert(is_Block(bl));
  71         unsigned n_cfg_outs = 0;
  72         for (unsigned i = 0; i < get_irn_n_outs(bl); ++i) {
  73                 const ir_node *succ = get_irn_out(bl, i);
  74                 if (get_irn_mode(succ) != mode_X)
  75                         continue;
  76                 if (is_Bad(succ))
  77                         continue;
  78                 if (is_End(succ)) {
  79                         ir_node *end_bl = get_nodes_block(succ);
  80                         if (end_bl == bl)
  81                                 continue;
  82                         ++n_cfg_outs;
  83                         continue;
  84                 }
  85                 n_cfg_outs += get_irn_n_outs(succ);
  86         }
  87         return n_cfg_outs;
  88 }
  89
  90 ir_node *get_Block_cfg_out(const ir_node *bl, unsigned pos)
  91 {
  92         assert(is_Block(bl));
  93         for (unsigned i = 0; i < get_irn_n_outs(bl); ++i) {
  94                 const ir_node *succ = get_irn_out(bl, i);
  95                 if (get_irn_mode(succ) != mode_X)
  96                         continue;
  97                 if (is_End(succ) || is_Bad(succ))
  98                         continue;
  99
 100                 unsigned n_outs = get_irn_n_outs(succ);
 101                 if (pos < n_outs)
 102                         return get_irn_out(succ, pos);
 103                 else
 104                         pos -= n_outs;
 105         }
 106         return NULL;
 107 }
 108
 109 ir_node *get_Block_cfg_out_ka(const ir_node *bl, unsigned pos)
 110 {
 111         assert(is_Block(bl));
 112         for (unsigned i = 0; i < get_irn_n_outs(bl); ++i) {
 113                 const ir_node *succ = get_irn_out(bl, i);
 114                 if (get_irn_mode(succ) != mode_X)
 115                         continue;
 116                 if (is_Bad(succ))
 117                         continue;
 118
 119                 if (is_End(succ)) {
 120                         ir_node *end_bl = get_nodes_block(succ);
 121                         if (end_bl == bl) {
 122                                 /* ignore End if we are in the Endblock */
 123                                 continue;
 124                         }
 125                         if (pos == 0) {
 126                                 /* handle keep-alive here: return the Endblock instead of the End node */
 127                                 return end_bl;
 128                         } else {
 129                                 --pos;
 130                                 continue;
 131                         }
 132                 }
 133                 unsigned n_outs = get_irn_n_outs(succ);
 134                 if (pos < n_outs)
 135                         return get_irn_out(succ, pos);
 136                 else
 137                         pos -= n_outs;
 138         }
 139         return NULL;
 140 }
 141
 142 static void irg_out_walk_2(ir_node *node, irg_walk_func *pre,
 143                            irg_walk_func *post, void *env)
 144 {
 145         assert(get_irn_visited(node) < get_irg_visited(current_ir_graph));
 146
 147         set_irn_visited(node, get_irg_visited(current_ir_graph));
 148
 149         if (pre) pre(node, env);
 150
 151         int n = get_irn_n_outs(node);
 152         for (int i = 0; i < n; ++i) {
 153                 ir_node *succ = get_irn_out(node, i);
 154                 if (get_irn_visited(succ) < get_irg_visited(current_ir_graph))
 155                         irg_out_walk_2(succ, pre, post, env);
 156         }
 157
 158         if (post) post(node, env);
 159 }
 160
 161 void irg_out_walk(ir_node *node, irg_walk_func *pre, irg_walk_func *post,
 162                   void *env)
 163 {
 164         assert(node);
 165         ir_graph *irg = get_irn_irg(node);
 166         if (irg_has_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_OUTS)) {
 167                 inc_irg_visited(irg);
 168                 irg_out_walk_2(node, pre, post, env);
 169         }
 170 }
 171
 172 static void irg_out_block_walk2(ir_node *bl, irg_walk_func *pre,
 173                                 irg_walk_func *post, void *env)
 174 {
 175         if (Block_block_visited(bl))
 176                 return;
 177
 178         mark_Block_block_visited(bl);
 179
 180         if (pre)
 181                 pre(bl, env);
 182
 183         int n = get_Block_n_cfg_outs(bl);
 184         for (int i = 0; i < n; ++i) {
 185                 /* find the corresponding predecessor block. */
 186                 ir_node *pred = get_Block_cfg_out(bl, i);
 187                 /* recursion */
 188                 irg_out_block_walk2(pred, pre, post, env);
 189         }
 190
 191         if (post)
 192                 post(bl, env);
 193 }
 194
 195 void irg_out_block_walk(ir_node *node, irg_walk_func *pre, irg_walk_func *post,
 196                         void *env)
 197 {
 198         ir_graph *irg = get_irn_irg(node);
 199         assert(is_Block(node) || (get_irn_mode(node) == mode_X));
 200
 201         ir_graph *rem = current_ir_graph;
 202         current_ir_graph = irg;
 203
 204         inc_irg_block_visited(irg);
 205
 206         if (get_irn_mode(node) == mode_X) {
 207                 int n = get_irn_n_outs(node);
 208                 for (int i = 0; i < n; ++i) {
 209                         ir_node *succ = get_irn_out(node, i);
 210                         irg_out_block_walk2(succ, pre, post, env);
 211                 }
 212         } else {
 213                 irg_out_block_walk2(node, pre, post, env);
 214         }
 215
 216         current_ir_graph = rem;
 217 }
 218
 219 /*--------------------------------------------------------------------*/
 220 /** Building and Removing the out datastructure                      **/
 221 /**                                                                  **/
 222 /** The outs of a graph are allocated in a single, large array.      **/
 223 /** This allows to allocate and deallocate the memory for the outs   **/
 224 /** on demand.  The large array is separated into many small ones    **/
 225 /** for each node.  Only a single field to reference the out array   **/
 226 /** is stored in each node and a field referencing the large out     **/
 227 /** array in irgraph.  The 0 field of each out array contains the    **/
 228 /** size of this array.  This saves memory in the irnodes themselves.**/
 229 /** The construction does two passes over the graph.  The first pass **/
 230 /** counts the overall number of outs and the outs of each node.  It **/
 231 /** stores the outs of each node in the out reference of the node.   **/
 232 /** Then the large array is allocated.  The second iteration chops   **/
 233 /** the large array into smaller parts, sets the out edges and       **/
 234 /** recounts the out edges.                                          **/
 235 /** Removes Tuple nodes!                                             **/
 236 /*--------------------------------------------------------------------*/
 237
 238
 239 /** Returns the amount of out edges for not yet visited successors. */
 240 static void count_outs_node(ir_node *n)
 241 {
 242         if (irn_visited_else_mark(n))
 243                 return;
 244
 245         /* initialize our counter */
 246         n->o.n_outs = 0;
 247
 248         int start     = is_Block(n) ? 0 : -1;
 249         int irn_arity = get_irn_arity(n);
 250         for (int i = start; i < irn_arity; ++i) {
 251                 ir_node *def = get_irn_n(n, i);
 252                 /* optimize Tuples */
 253                 ir_node *skipped = skip_Tuple(def);
 254                 if (skipped != def)
 255                         set_irn_n(n, i, skipped);
 256
 257                 count_outs_node(skipped);
 258                 ++skipped->o.n_outs;
 259         }
 260 }
 261
 262
 263 /** Returns the amount of out edges for not yet visited successors.
 264  *  This version handles some special nodes like irg_frame, irg_args etc. */
 265 static void count_outs(ir_graph *irg)
 266 {
 267         inc_irg_visited(irg);
 268         count_outs_node(get_irg_end(irg));
 269         for (int i = anchor_first; i <= anchor_last; ++i) {
 270                 ir_node *n = get_irg_anchor(irg, i);
 271                 if (irn_visited_else_mark(n))
 272                         continue;
 273                 n->o.n_outs = 0;
 274         }
 275 }
 276
 277 static void set_out_edges_node(ir_node *node, struct obstack *obst)
 278 {
 279         if (irn_visited_else_mark(node))
 280                 return;
 281
 282         /* Allocate my array */
 283         unsigned n_outs = node->o.n_outs;
 284         node->o.out          = OALLOCF(obst, ir_def_use_edges, edges, n_outs);
 285         node->o.out->n_edges = 0;
 286
 287         /* add def->use edges from my predecessors to me */
 288         int start     = is_Block(node) ? 0 : -1;
 289         int irn_arity = get_irn_arity(node);
 290         for (int i = start; i < irn_arity; ++i) {
 291                 ir_node *def = get_irn_n(node, i);
 292
 293                 /* recurse, ensures that out array of pred is already allocated */
 294                 set_out_edges_node(def, obst);
 295
 296                 /* Remember this Def-Use edge */
 297                 unsigned pos = def->o.out->n_edges++;
 298                 def->o.out->edges[pos].use = node;
 299                 def->o.out->edges[pos].pos = i;
 300         }
 301 }
 302
 303 static void set_out_edges(ir_graph *irg)
 304 {
 305         struct obstack *obst = &irg->out_obst;
 306
 307         obstack_init(obst);
 308         irg->out_obst_allocated = true;
 309
 310         inc_irg_visited(irg);
 311         set_out_edges_node(get_irg_end(irg), obst);
 312         for (int i = anchor_first; i <= anchor_last; ++i) {
 313                 ir_node *n = get_irg_anchor(irg, i);
 314                 if (irn_visited_else_mark(n))
 315                         continue;
 316                 n->o.out          = OALLOCF(obst, ir_def_use_edges, edges, 0);
 317                 n->o.out->n_edges = 0;
 318         }
 319 }
 320
 321 void compute_irg_outs(ir_graph *irg)
 322 {
 323         free_irg_outs(irg);
 324
 325         /* This first iteration counts the overall number of out edges and the
 326            number of out edges for each node. */
 327         count_outs(irg);
 328
 329         /* The second iteration splits the irg->outs array into smaller arrays
 330            for each node and writes the back edges into this array. */
 331         set_out_edges(irg);
 332
 333         add_irg_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_OUTS
 334                               | IR_GRAPH_PROPERTY_NO_TUPLES);
 335 }
 336
 337 void assure_irg_outs(ir_graph *irg)
 338 {
 339         if (!irg_has_properties(irg, IR_GRAPH_PROPERTY_CONSISTENT_OUTS))
 340                 compute_irg_outs(irg);
 341 }
 342
 343 #ifdef DEBUG_libfirm
 344 /** Clear the outs of a node */
 345 static void reset_outs(ir_node *node, void *unused)
 346 {
 347         (void) unused;
 348         node->o.out = NULL;
 349 }
 350 #endif
 351
 352 void free_irg_outs(ir_graph *irg)
 353 {
 354         if (irg->out_obst_allocated) {
 355                 obstack_free(&irg->out_obst, NULL);
 356                 irg->out_obst_allocated = false;
 357         }
 358
 359 #ifdef DEBUG_libfirm
 360         /* when debugging, *always* reset all nodes' outs!  irg->outs might
 361            have been lying to us */
 362         irg_walk_graph (irg, reset_outs, NULL, NULL);
 363 #endif
 364 }