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 "irgwalk.h"           /* for irg_walk_func */
  28 # include "irprog.h"            /* for get_irp_main_irg */
  29 # include "xmalloc.h"
  30
  31 # ifndef TRUE
  32 #  define TRUE 1
  33 #  define FALSE 0
  34 # endif /* not defined TRUE */
  35
  36 /*
  37    Data
  38 */
  39
  40 /* environment for a single memory walker */
  41 typedef struct walk_mem_env_str {
  42   ir_graph *graph;              /* the graph we're visiting */
  43   int visited;                  /* 'visited' marker */
  44   irg_walk_func *pre;           /* pre action */
  45   irg_walk_func *post;          /* post action */
  46   void *env;                    /* user-defined environment */
  47
  48   struct walk_mem_env_str *prev; /* link up walking instances */
  49   /* what else? */
  50 } walk_mem_env_t;
  51
  52 /*
  53   Globals
  54 */
  55
  56 /* Link up walking instances */
  57 static walk_mem_env_t *walk_envs = NULL;
  58
  59 /*
  60   Walk over the firm nodes of a graph via the memory edges (only)
  61   starting from a node that has a memory input.
  62 */
  63 static void irg_walk_mem_node (ir_node *node,
  64                                walk_mem_env_t *walk_env)
  65 {
  66   const opcode op = get_irn_opcode (node);
  67   ir_node *in = NULL;
  68
  69   if (get_irn_visited (node) >= walk_env->visited) {
  70     return;
  71   } else {
  72     set_irn_visited (node, walk_env->visited);
  73   }
  74
  75   if (op_NoMem == get_irn_op (node)) {
  76     /* We don't want to see it it if it's not memory */
  77     return;
  78   }
  79
  80   if (iro_Proj == op) {
  81     /* We don't want to see proj nodes at all --- skip over them */
  82     in = get_Proj_pred (node);
  83
  84     irg_walk_mem_node (in, walk_env);
  85
  86     return;
  87   }
  88
  89   /* execute the 'pre' function */
  90   if (NULL != walk_env->pre) {
  91     walk_env->pre (node, walk_env->env);
  92   }
  93
  94   switch (op) {
  95   case (iro_Start): {
  96   } break;
  97   case (iro_Load): {
  98     in = get_Load_mem (node);
  99
 100     irg_walk_mem_node (in, walk_env);
 101   } break;
 102   case (iro_Store): {
 103     in = get_Store_mem (node);
 104
 105     irg_walk_mem_node (in, walk_env);
 106   } break;
 107   case (iro_Alloc): {
 108     in = get_Alloc_mem (node);
 109
 110     irg_walk_mem_node (in, walk_env);
 111   } break;
 112   case (iro_Free): {
 113     in = get_Free_mem (node);
 114     /* WTF? */
 115     irg_walk_mem_node (in, walk_env);
 116   } break;
 117   case (iro_Raise): {
 118     in = get_Raise_mem (node);
 119
 120     irg_walk_mem_node (in, walk_env);
 121   } break;
 122   case (iro_Sel): {
 123     in = get_Sel_mem (node);
 124
 125     irg_walk_mem_node (in, walk_env);
 126   } break;
 127   case (iro_Call): {
 128     in = get_Call_mem (node);
 129
 130     irg_walk_mem_node (in, walk_env);
 131   } break;
 132   case (iro_Return): {
 133     in = get_Return_mem (node);
 134
 135     irg_walk_mem_node (in, walk_env);
 136   } break;
 137   case (iro_Phi): {
 138     int i;
 139     int n_ins = get_irn_arity (node);
 140
 141     for (i = 0; i < n_ins; i ++) {
 142       in = get_irn_n (node, i);
 143
 144       irg_walk_mem_node (in, walk_env);
 145     }
 146   } break;
 147   case (iro_Div): {
 148     in = get_Div_mem (node);
 149
 150     irg_walk_mem_node (in, walk_env);
 151   } break;
 152   case (iro_Quot): {
 153     in = get_Quot_mem (node);
 154
 155     irg_walk_mem_node (in, walk_env);
 156   } break;
 157   case (iro_Mod): {
 158     in = get_Mod_mem (node);
 159
 160     irg_walk_mem_node (in, walk_env);
 161   } break;
 162   case (iro_DivMod): {
 163     in = get_DivMod_mem (node);
 164
 165     irg_walk_mem_node (in, walk_env);
 166   } break;
 167   case (iro_Block): {
 168     /* End Block ONLY */
 169     int i;
 170     int n_ins = get_irn_arity (node);
 171
 172     for (i = 0; i < n_ins; i ++) {
 173       ir_node *ret = get_irn_n (node, i);
 174
 175       irg_walk_mem_node (ret, walk_env);
 176     }
 177   } break;
 178   default: {
 179     fprintf (stderr, "%s: not handled: node[%li].op = %s\n",
 180              __FUNCTION__,
 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.5  2004/11/19 10:35:20  liekweg
 265   also test for NoMem
 266
 267   Revision 1.4  2004/11/18 16:35:11  liekweg
 268   Do not touch Proj nodes at all
 269
 270   Revision 1.3  2004/11/04 14:57:12  liekweg
 271   fixed end block handling
 272
 273   Revision 1.2  2004/10/22 14:41:12  liekweg
 274   execute 'pre' for a change.  Also, add CVS log
 275
 276
 277 */