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