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 "xmalloc.h"
  29
  30 # ifndef TRUE
  31 #  define TRUE 1
  32 #  define FALSE 0
  33 # endif /* not defined TRUE */
  34
  35 /*
  36    Data
  37 */
  38
  39 /* environment for a single memory walker */
  40 typedef struct walk_mem_env_str {
  41   ir_graph *graph;              /* the graph we're visiting */
  42   int visited;                  /* 'visited' marker */
  43   irg_walk_func *pre;           /* pre action */
  44   irg_walk_func *post;          /* post action */
  45   void *env;                    /* user-defined environment */
  46
  47   struct walk_mem_env_str *prev; /* link up walking instances */
  48   /* what else? */
  49 } walk_mem_env_t;
  50
  51 /*
  52   Globals
  53 */
  54
  55 /* Link up walking instances */
  56 static walk_mem_env_t *walk_envs = NULL;
  57
  58 /*
  59   Walk over the firm nodes of a graph via the memory edges (only)
  60   starting from a node that has a memory input.
  61 */
  62 static void irg_walk_mem_node (ir_node *node,
  63                                walk_mem_env_t *walk_env)
  64 {
  65   const opcode op = get_irn_opcode (node);
  66   ir_node *in = NULL;
  67
  68   if (get_irn_visited (node) >= walk_env->visited) {
  69     return;
  70   } else {
  71     set_irn_visited (node, walk_env->visited);
  72   }
  73
  74   if (NULL != walk_env->pre) {
  75     walk_env->pre (node, walk_env->env);
  76   }
  77
  78   switch (op) {
  79   case (iro_Start): {
  80   } break;
  81   case (iro_Load): {
  82     in = get_Load_mem (node);
  83
  84     irg_walk_mem_node (in, walk_env);
  85   } break;
  86   case (iro_Store): {
  87     in = get_Store_mem (node);
  88
  89     irg_walk_mem_node (in, walk_env);
  90   } break;
  91   case (iro_Alloc): {
  92     in = get_Alloc_mem (node);
  93
  94     irg_walk_mem_node (in, walk_env);
  95   } break;
  96   case (iro_Free): {
  97     in = get_Free_mem (node);
  98     /* WTF? */
  99     irg_walk_mem_node (in, walk_env);
 100   } break;
 101   case (iro_Raise): {
 102     in = get_Raise_mem (node);
 103
 104     irg_walk_mem_node (in, walk_env);
 105   } break;
 106   case (iro_Sel): {
 107     in = get_Sel_mem (node);
 108
 109     irg_walk_mem_node (in, walk_env);
 110   } break;
 111   case (iro_Call): {
 112     in = get_Call_mem (node);
 113
 114     irg_walk_mem_node (in, walk_env);
 115   } break;
 116   case (iro_Return): {
 117     in = get_Return_mem (node);
 118
 119     irg_walk_mem_node (in, walk_env);
 120   } break;
 121   case (iro_Proj): {
 122     in = get_Proj_pred (node);
 123
 124     irg_walk_mem_node (in, walk_env);
 125   } break;
 126   case (iro_Phi): {
 127     int i;
 128     int n_ins = get_irn_arity (node);
 129
 130     for (i = 0; i < n_ins; i ++) {
 131       in = get_irn_n (node, i);
 132
 133       irg_walk_mem_node (in, walk_env);
 134     }
 135   } break;
 136   case (iro_Div): {
 137     in = get_Div_mem (node);
 138
 139     irg_walk_mem_node (in, walk_env);
 140   } break;
 141   case (iro_Quot): {
 142     in = get_Quot_mem (node);
 143
 144     irg_walk_mem_node (in, walk_env);
 145   } break;
 146   case (iro_Mod): {
 147     in = get_Mod_mem (node);
 148
 149     irg_walk_mem_node (in, walk_env);
 150   } break;
 151   case (iro_DivMod): {
 152     in = get_DivMod_mem (node);
 153
 154     irg_walk_mem_node (in, walk_env);
 155   } break;
 156   default: {
 157     assert (0 && "something not handled");
 158   }
 159   }
 160
 161   if (NULL != walk_env->post) {
 162     walk_env->post (node, walk_env->env);
 163   }
 164 }
 165
 166 /*
 167    See whether the given graph is being visited right now.
 168    We can't be visiting a graph multiple times.
 169 */
 170 int get_irg_is_mem_visited (ir_graph *graph)
 171 {
 172   walk_mem_env_t *walk_env = walk_envs;
 173
 174   while (NULL != walk_env) {
 175     if (graph == walk_env->graph) {
 176       return (TRUE);
 177     }
 178
 179     walk_env = walk_env->prev;
 180   }
 181
 182   return (FALSE);
 183 }
 184
 185 /*
 186   Walk over the nodes of the given graph via the memory edges (only).
 187   Each graph can only be subject to this walk once at any given time.
 188 */
 189 void irg_walk_mem (ir_graph *graph,
 190                    irg_walk_func *pre, irg_walk_func *post,
 191                    void *env)
 192 {
 193   int i;
 194   ir_node *ret = NULL;
 195   ir_node *end = get_irg_end_block (graph);
 196   int n_ins;
 197   walk_mem_env_t *walk_env = (walk_mem_env_t*) xmalloc (sizeof (walk_mem_env_t));
 198
 199   assert (! get_irg_is_mem_visited (graph));
 200
 201   walk_env->graph = graph;
 202   inc_irg_visited (walk_env->graph);
 203   walk_env->visited = get_irg_visited (graph);
 204
 205   walk_env->prev = walk_envs;
 206   walk_envs = walk_env;
 207
 208   walk_env->pre = pre;
 209   walk_env->post = post;
 210   walk_env->env  = env;
 211
 212   /* 'graph' is not actually being visited right now, but it should be reported that way */
 213   assert (get_irg_is_mem_visited (graph));
 214
 215   /* all return nodes */
 216   n_ins = get_irn_arity (end);
 217   for (i = 0; i < n_ins; i ++) {
 218     ret = get_irn_n (end, i);
 219
 220     irg_walk_mem_node (ret, walk_env);
 221   }
 222
 223   /*
 224     The end NODE sometimes has some more ins. not sure whether we need to walk them.
 225   */
 226
 227   /* allow only properly nested calls right now */
 228   assert (walk_envs == walk_env);
 229   walk_envs = walk_envs->prev;
 230
 231   free (walk_env);
 232
 233   assert (! get_irg_is_mem_visited (graph));
 234 }
 235
 236 \f
 237
 238 /*
 239   $Log$
 240   Revision 1.2  2004/10/22 14:41:12  liekweg
 241   execute 'pre' for a change.  Also, add CVS log
 242
 243
 244 */