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

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