nsz Git - libfirm/blob - ir/ana2/irmemwalk.c

   1 /* -*- c -*- */
   2
   3 /*
   4  * Copyright (C) 1995-2007 University of Karlsruhe.  All right reserved.
   5  *
   6  * This file is part of libFirm.
   7  *
   8  * This file may be distributed and/or modified under the terms of the
   9  * GNU General Public License version 2 as published by the Free Software
  10  * Foundation and appearing in the file LICENSE.GPL included in the
  11  * packaging of this file.
  12  *
  13  * Licensees holding valid libFirm Professional Edition licenses may use
  14  * this file in accordance with the libFirm Commercial License.
  15  * Agreement provided with the Software.
  16  *
  17  * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
  18  * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  19  * PURPOSE.
  20  */
  21
  22 /**
  23  * @file
  24  * @brief    walk along memory edges
  25  * @author   Florian
  26  * @date     Mon 18 Oct 2004
  27  * @version  $Id$
  28  * @summary
  29  *   Walk over a firm graph along its memory edges.
  30  *
  31  *   Any number of graphs can be visited at the same time, but no graph
  32  *   can be traversed more than once at any time.
  33  */
  34 # ifdef HAVE_CONFIG_H
  35 #  include "config.h"
  36 # endif
  37
  38 # include "irnode_t.h"
  39 # include "irgwalk.h"           /* for irg_walk_func */
  40 # include "irprog.h"            /* for get_irp_main_irg */
  41 # include "xmalloc.h"
  42 # include "gnu_ext.h"
  43
  44 # ifndef TRUE
  45 #  define TRUE 1
  46 #  define FALSE 0
  47 # endif /* not defined TRUE */
  48
  49 /*
  50    Data
  51 */
  52
  53 /** environment for a single memory walker */
  54 typedef struct walk_mem_env_str {
  55   ir_graph *graph;              /**< the graph we're visiting */
  56   unsigned long visited;        /**< 'visited' marker
  57                                  (unsigned long in case we walk more than 2^32 graphs) */
  58   irg_walk_func *pre;           /**< pre action */
  59   irg_walk_func *post;          /**< post action */
  60   void *env;                    /**< user-defined environment */
  61
  62   struct walk_mem_env_str *prev; /**< link up walking instances */
  63   /* what else? */
  64 } walk_mem_env_t;
  65
  66 /*
  67   Globals
  68 */
  69
  70 /* Link up walking instances */
  71 static walk_mem_env_t *walk_envs = NULL;
  72
  73 /*
  74   Walk over the firm nodes of a graph via the memory edges (only)
  75   starting from a node that has a memory input.
  76 */
  77 static void irg_walk_mem_node (ir_node *node,
  78                                walk_mem_env_t *walk_env)
  79 {
  80   const ir_opcode op = get_irn_opcode (node);
  81   ir_node *in = NULL;
  82
  83   if (get_irn_visited (node) >= walk_env->visited) {
  84     return;
  85   } else {
  86     set_irn_visited (node, walk_env->visited);
  87   }
  88
  89   if (op_NoMem == get_irn_op (node)) {
  90     /* We don't want to see it it if it's not memory */
  91     return;
  92   }
  93
  94   if (iro_Proj == op) {
  95     /* We don't want to see proj nodes at all --- skip over them */
  96     in = get_Proj_pred (node);
  97
  98     irg_walk_mem_node (in, walk_env);
  99
 100     return;
 101   }
 102
 103   /* execute the 'pre' function */
 104   if (NULL != walk_env->pre) {
 105     walk_env->pre (node, walk_env->env);
 106   }
 107
 108   switch (op) {
 109   case (iro_Start): {
 110   } break;
 111   case (iro_Load): {
 112     in = get_Load_mem (node);
 113
 114     irg_walk_mem_node (in, walk_env);
 115   } break;
 116   case (iro_Store): {
 117     in = get_Store_mem (node);
 118
 119     irg_walk_mem_node (in, walk_env);
 120   } break;
 121   case (iro_Alloc): {
 122     in = get_Alloc_mem (node);
 123
 124     irg_walk_mem_node (in, walk_env);
 125   } break;
 126   case (iro_Free): {
 127     in = get_Free_mem (node);
 128     /* WTF? */
 129     irg_walk_mem_node (in, walk_env);
 130   } break;
 131   case (iro_Raise): {
 132     in = get_Raise_mem (node);
 133
 134     irg_walk_mem_node (in, walk_env);
 135   } break;
 136   case (iro_Sel): {
 137     in = get_Sel_mem (node);
 138
 139     irg_walk_mem_node (in, walk_env);
 140   } break;
 141   case (iro_Call): {
 142     in = get_Call_mem (node);
 143
 144     irg_walk_mem_node (in, walk_env);
 145   } break;
 146   case (iro_Return): {
 147     in = get_Return_mem (node);
 148
 149     irg_walk_mem_node (in, walk_env);
 150   } break;
 151   case (iro_Phi): {
 152     int i;
 153     int n_ins = get_irn_arity (node);
 154
 155     for (i = 0; i < n_ins; i ++) {
 156       in = get_irn_n (node, i);
 157
 158       irg_walk_mem_node (in, walk_env);
 159     }
 160   } break;
 161   case (iro_Div): {
 162     in = get_Div_mem (node);
 163
 164     irg_walk_mem_node (in, walk_env);
 165   } break;
 166   case (iro_Quot): {
 167     in = get_Quot_mem (node);
 168
 169     irg_walk_mem_node (in, walk_env);
 170   } break;
 171   case (iro_Mod): {
 172     in = get_Mod_mem (node);
 173
 174     irg_walk_mem_node (in, walk_env);
 175   } break;
 176   case (iro_DivMod): {
 177     in = get_DivMod_mem (node);
 178
 179     irg_walk_mem_node (in, walk_env);
 180   } break;
 181   case (iro_Block): {
 182     /* End Block ONLY */
 183     int i;
 184     int n_ins = get_irn_arity (node);
 185
 186     for (i = 0; i < n_ins; i ++) {
 187       ir_node *ret = get_irn_n (node, i);
 188
 189       irg_walk_mem_node (ret, walk_env);
 190     }
 191   } break;
 192   default: {
 193     fprintf (stderr, "%s: not handled: node[%li].op = %s\n",
 194              __FUNCTION__,
 195              get_irn_node_nr (node),
 196              get_op_name (get_irn_op (node)));
 197
 198     assert (0 && "something not handled");
 199   }
 200   }
 201
 202   /* execute the 'post' function */
 203   if (NULL != walk_env->post) {
 204     walk_env->post (node, walk_env->env);
 205   }
 206 }
 207
 208 /*
 209    See whether the given graph is being visited right now.
 210    We can't be visiting a graph multiple times.
 211 */
 212 int get_irg_is_mem_visited (ir_graph *graph)
 213 {
 214   walk_mem_env_t *walk_env = walk_envs;
 215
 216   while (NULL != walk_env) {
 217     if (graph == walk_env->graph) {
 218       return (TRUE);
 219     }
 220
 221     walk_env = walk_env->prev;
 222   }
 223
 224   return (FALSE);
 225 }
 226
 227 /*
 228   Walk over the nodes of the given graph via the memory edges (only).
 229   Each graph can only be subject to this walk once at any given time.
 230 */
 231 void irg_walk_mem (ir_graph *graph,
 232                    irg_walk_func *pre, irg_walk_func *post,
 233                    void *env)
 234 {
 235   ir_node *end_block = get_irg_end_block (graph);
 236   walk_mem_env_t *walk_env = xmalloc (sizeof (walk_mem_env_t));
 237
 238   assert (! get_irg_is_mem_visited (graph));
 239
 240   walk_env->graph = graph;
 241   inc_irg_visited (walk_env->graph);
 242   walk_env->visited = get_irg_visited (graph);
 243
 244   walk_env->prev = walk_envs;
 245   walk_envs = walk_env;
 246
 247   walk_env->pre = pre;
 248   walk_env->post = post;
 249   walk_env->env  = env;
 250
 251   /* 'graph' is not actually being visited right now, so make sure it is reported that way */
 252   assert (get_irg_is_mem_visited (graph));
 253
 254   /*
 255     The ins of the end BLOCK are either 'return's (regular exits) or
 256     'ProjX'/'Raise's (exception exits).  We only walk over the
 257     'return' nodes, assuming that all memory-changing nodes are found
 258     from there on.
 259   */
 260   irg_walk_mem_node (end_block, walk_env);
 261   /*
 262     The end NODE sometimes has some more ins. not sure whether we need to walk them.
 263   */
 264
 265   /* allow only properly nested calls right now */
 266   assert (walk_envs == walk_env);
 267   walk_envs = walk_envs->prev;
 268
 269   free (walk_env);
 270
 271   assert (! get_irg_is_mem_visited (graph));
 272 }
 273
 274 \f
 275
 276 /*
 277   $Log$
 278   Revision 1.12  2007/01/16 15:45:42  beck
 279   renamed type opcode to ir_opcode
 280
 281   Revision 1.11  2005/01/26 12:20:20  beck
 282   gnu_ext.h included
 283
 284   Revision 1.10  2005/01/14 13:34:48  liekweg
 285   Don't cast malloc
 286
 287   Revision 1.9  2005/01/10 17:26:34  liekweg
 288   fixup printfs, don't put environments on the stack
 289
 290   Revision 1.8  2004/12/22 14:43:14  beck
 291   made allocations C-like
 292
 293   Revision 1.7  2004/12/21 14:25:35  beck
 294   removed C99 constructs
 295   make visit counter of same type as irn visit counter
 296
 297   Revision 1.6  2004/12/02 16:17:51  beck
 298   fixed config.h include
 299
 300   Revision 1.5  2004/11/19 10:35:20  liekweg
 301   also test for NoMem
 302
 303   Revision 1.4  2004/11/18 16:35:11  liekweg
 304   Do not touch Proj nodes at all
 305
 306   Revision 1.3  2004/11/04 14:57:12  liekweg
 307   fixed end block handling
 308
 309   Revision 1.2  2004/10/22 14:41:12  liekweg
 310   execute 'pre' for a change.  Also, add CVS log
 311
 312
 313 */