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