nsz Git - libfirm/blob - ir/ir/iredges_t.h

   1 /*
   2  * Project:     libFIRM
   3  * File name:   ir/ir/iredges_t.h
   4  * Purpose:     Everlasting outs -- private header.
   5  * Author:      Sebastian Hack
   6  * Created:     15.01.2005
   7  * CVS-ID:      $Id$
   8  * Copyright:   (c) 1998-2005 Universit�t Karlsruhe
   9  * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
  10  */
  11
  12 /**
  13  * everlasting outs.
  14  * @author Sebastian Hack
  15  * @date 15.1.2005
  16  */
  17
  18 #ifndef _FIRM_EDGES_T_H
  19 #define _FIRM_EDGES_T_H
  20
  21 #include "firm_config.h"
  22 #include "debug.h"
  23
  24 #include "set.h"
  25 #include "list.h"
  26
  27 #include "irnode_t.h"
  28 #include "irgraph_t.h"
  29
  30 #include "iredges.h"
  31
  32 #if FIRM_EDGES_INPLACE
  33
  34 #define DBG_EDGES  "edges"
  35
  36 /**
  37  * An edge.
  38  */
  39 struct _ir_edge_t {
  40   ir_node *src;           /**< The source node of the edge. */
  41   int pos;                /**< The position of the edge at @p src. */
  42   unsigned invalid : 1;   /**< edges that are removed are marked invalid. */
  43   unsigned present : 1;   /**< Used by the verifier. Don't rely on its content. */
  44   struct list_head list;  /**< The list head to queue all out edges at a node. */
  45 #ifdef DEBUG_libfirm
  46   long src_nr;            /**< The node number of the source node. */
  47 #endif
  48 };
  49
  50 /**
  51  * A block edge inherits from a normal edge.
  52  * They represent edges leading from a block to a control flow node
  53  * and are used to quickly find all control flow successors of
  54  * a block.
  55  */
  56 struct _ir_block_edge_t {
  57   struct _ir_edge_t edge;      /**< The inherited data. */
  58   struct list_head succ_list;  /**< List element listing all
  59                                  control flow edges to the
  60                                  successors of a block. */
  61 };
  62
  63 /** Accessor for private irn info. */
  64 #define _get_irn_edge_info(irn) ((irn_edge_info_t *) &(irn)->edge_info)
  65
  66 /** Accessor for private irg info. */
  67 #define _get_irg_edge_info(irg) ((irg_edge_info_t *) &(irg)->edge_info)
  68
  69 /**
  70  * Convenience macro to get the outs_head from a irn_edge_info_t
  71  * struct.
  72  */
  73 #define _get_irn_outs_head(irn) (&_get_irn_edge_info(irn)->outs_head)
  74
  75 /**
  76  * Convenience macro to get the succ_head from a block_attr
  77  * struct.
  78  */
  79 #define _get_block_succ_head(bl) (&((bl)->attr.block.succ_head))
  80
  81 /**
  82  * Get the first edge pointing to some node.
  83  * @note There is no order on out edges. First in this context only
  84  * means, that you get some starting point into the list of edges.
  85  * @param irn The node.
  86  * @return The first out edge that points to this node.
  87  */
  88 static INLINE const ir_edge_t *_get_irn_out_edge_first(const ir_node *irn)
  89 {
  90   struct list_head *head = _get_irn_outs_head(irn);
  91   return list_empty(head) ? NULL : list_entry(head->next, ir_edge_t, list);
  92 }
  93
  94 /**
  95  * Get the next edge in the out list of some node.
  96  * @param irn The node.
  97  * @param last The last out edge you have seen.
  98  * @return The next out edge in @p irn 's out list after @p last.
  99  */
 100 static INLINE const ir_edge_t *_get_irn_out_edge_next(const ir_node *irn, const ir_edge_t *last)
 101 {
 102   struct list_head *next = last->list.next;
 103   return next == _get_irn_outs_head(irn) ? NULL : list_entry(next, ir_edge_t, list);
 104 }
 105
 106 /**
 107  * Get the first successor edge of a block.
 108  * A successor edge is an edge originated from another block, pointing
 109  * to a mode_X node in the given block and is thus a control flow
 110  * successor edge.
 111  * @param irn The block.
 112  * @return The first successor edge of the block.
 113  */
 114 static INLINE const ir_edge_t *_get_block_succ_first(const ir_node *irn)
 115 {
 116   const struct list_head *head;
 117
 118   assert(is_Block(irn) && "Node must be a block here");
 119   head = _get_block_succ_head(irn);
 120   return (ir_edge_t *) (list_empty(head) ? NULL :
 121       list_entry(head->next, ir_block_edge_t, succ_list));
 122 }
 123
 124 /**
 125  * Get the next block successor edge.
 126  * @see See _get_block_succ_first() for details.
 127  * @param irn The block.
 128  * @param last The last edge.
 129  * @return The next edge, or NULL if there is no further.
 130  */
 131 static INLINE const ir_edge_t *_get_block_succ_next(const ir_node *irn, const ir_edge_t *last)
 132 {
 133   const ir_block_edge_t *block_edge;
 134   struct list_head *next;
 135
 136   assert(is_Block(irn) && "Node must be a block here");
 137   block_edge = (const ir_block_edge_t *) last;
 138   next = block_edge->succ_list.next;
 139   return (ir_edge_t *) (next == _get_block_succ_head(irn) ? NULL :
 140       list_entry(next, ir_block_edge_t, succ_list));
 141 }
 142
 143 /**
 144  * Get the source node of an edge.
 145  * @param edge The edge.
 146  * @return The source node of that edge.
 147  */
 148 static INLINE  ir_node *_get_edge_src_irn(const ir_edge_t *edge)
 149 {
 150   return edge ? edge->src : NULL;
 151 }
 152
 153 /**
 154  * Get the position of an edge.
 155  * @param edge.
 156  * @return The position in the in array of that edges source.
 157  */
 158 static INLINE int _get_edge_src_pos(const ir_edge_t *edge)
 159 {
 160   return edge ? edge->pos : -1;
 161 }
 162
 163 /**
 164  * Get the number of edges pointing to a node.
 165  * @param irn The node.
 166  * @return The number of edges pointing to this node.
 167  */
 168 static INLINE int _get_irn_n_edges(const ir_node *irn)
 169 {
 170 /* Perhaps out_count was buggy. This code does it more safely.
 171
 172         int res = 0;
 173         struct list_head *pos, *head = _get_irn_outs_head(irn);
 174         list_for_each(pos, head)
 175                 res++;
 176         return res;
 177 */
 178         return _get_irn_edge_info(irn)->out_count;
 179 }
 180
 181 static INLINE int _edges_activated(const ir_graph *irg)
 182 {
 183   return _get_irg_edge_info(irg)->activated;
 184 }
 185
 186 /**
 187  * Assure, that the edges information is present for a certain graph.
 188  * @param irg The graph.
 189  */
 190 static INLINE void _edges_assure(ir_graph *irg)
 191 {
 192         if(!_edges_activated(irg))
 193                 edges_activate(irg);
 194 }
 195
 196 void edges_reroute(ir_node *old, ir_node *nw, ir_graph *irg);
 197
 198 void edges_init_graph(ir_graph *irg);
 199
 200 /**
 201  * Notify of a edge change.
 202  * The edge from (src, pos) -> old_tgt is redirected to tgt
 203  */
 204 void edges_notify_edge(ir_node *src, int pos, ir_node *tgt, ir_node *old_tgt, ir_graph *irg);
 205
 206 /**
 207  * A node is deleted.
 208  */
 209 void edges_node_deleted(ir_node *old, ir_graph *irg);
 210
 211 void edges_invalidate(ir_node *irn, ir_graph *irg);
 212
 213 /**
 214  * Register additional memory in an edge.
 215  * This must be called before Firm is initialized.
 216  * @param  n Number of bytes you need.
 217  * @return A number you have to keep and to pass
 218  *         edges_get_private_data()
 219  *         to get a pointer to your data.
 220  */
 221 int edges_register_private_data(size_t n);
 222
 223 /**
 224  * Get a pointer to the private data you registered.
 225  * @param  edge The edge.
 226  * @param  ofs  The number, you obtained with
 227  *              edges_register_private_data().
 228  * @return A pointer to the private data.
 229  */
 230 static INLINE void *_get_edge_private_data(const ir_edge_t *edge, int ofs)
 231 {
 232         /* Get the size of the edge. */
 233         size_t size =
 234                 is_Block(edge->src) ? sizeof(ir_block_edge_t) : sizeof(ir_edge_t);
 235
 236         return (void *) ((char *) edge + size + ofs);
 237 }
 238
 239 /**
 240  * Initialize the out edges.
 241  * This must be called before firm is initialized.
 242  */
 243 extern void init_edges(void);
 244
 245 #define get_irn_out_edge_first(irn)      _get_irn_out_edge_first(irn)
 246 #define get_irn_out_edge_next(irn,last)  _get_irn_out_edge_next(irn, last)
 247 #define get_block_succ_first(irn)        _get_block_succ_first(irn)
 248 #define get_block_succ_next(irn,last)    _get_block_succ_next(irn, last)
 249 #define get_edge_src_irn(edge)           _get_edge_src_irn(edge)
 250 #define get_edge_src_pos(edge)           _get_edge_src_pos(edge)
 251 #define get_edge_private_data(edge,ofs)  _get_edge_private_data(edge,ofs)
 252 #define edges_activated(irg)             _edges_activated(irg)
 253 #define edges_assure(irg)                _edges_assure(irg)
 254
 255 #else
 256 /* new edges are disabled */
 257
 258 #define init_edges()
 259 #define edges_reroute(old, nw, irg)
 260 #define edges_init_graph(irg);
 261 #define edges_notify_edge(src, pos, tgt, old_tgt, irg)
 262 #define edges_node_deleted(old, irg)
 263 #define edges_invalidate(irn, irg)
 264 #define get_irn_out_edge_first(irn)       NULL
 265 #define get_irn_out_edge_next(irn,last)   NULL
 266 #define get_edge_src_irn(edge)            NULL
 267 #define get_edge_src_pos(edge)            -1
 268 #define get_edge_private_data(edge,ofs)   NULL
 269 #define edges_activated(irg)              0
 270 #define edges_assure(irg)
 271
 272 #endif /* FIRM_EDGES_INPLACE */
 273
 274 #endif /* _FIRM_EDGES_T_H */