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