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