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