nsz Git - libfirm/blob - ir/be/bechordal_t.h

   1
   2 /**
   3  * Internal datastructures for the chordal register allocator.
   4  * @author Sebastian Hack
   5  * @date 25.1.2005
   6  */
   7
   8 #ifndef _BECHORDAL_T_H
   9 #define _BECHORDAL_T_H
  10
  11 #include <stdlib.h>
  12
  13 #include "bitset.h"
  14 #include "list.h"
  15 #include "obst.h"
  16 #include "pset.h"
  17 #include "pmap.h"
  18 #include "set.h"
  19
  20 #include "irnode.h"
  21 #include "irgraph.h"
  22
  23 #include "be_t.h"
  24 #include "bearch.h"
  25
  26 /** Defines an invalid register index. */
  27 #define NO_COLOR (-1)
  28
  29 #define BUILD_GRAPH
  30
  31 #define DBG_CHORDAL "firm.be.ra.chordal"
  32
  33 /**
  34  * A liveness interval border.
  35  */
  36 typedef struct _border_t {
  37         unsigned magic;                                                         /**< A magic number for checking. */
  38         struct list_head list;                          /**< list head for queuing. */
  39         struct _border_t *other_end;    /**< The other end of the border. */
  40         ir_node *irn;                                                 /**< The node. */
  41         unsigned step;                                                          /**< The number equal to the interval border. */
  42         unsigned pressure;                                              /**< The pressure at this interval border.
  43                                                                                                                                         (The border itself is counting). */
  44         unsigned is_def : 1;                                    /**< Does this border denote a use or a def. */
  45         unsigned is_real : 1;                                   /**< Is the def/use real? Or is it just inserted
  46                                                                                                                                         at block beginnings or ends to ensure that inside
  47                                                                                                                                         a block, each value has one begin and one end. */
  48 } border_t;
  49
  50 /**
  51  * Environment for each of the chordal register allocator phases
  52  */
  53 struct _be_chordal_env_t {
  54         struct obstack obst;    /**< An obstack for temporary storage. */
  55         const be_main_session_env_t *session_env; /**< The current session. */
  56         pmap *border_heads;   /**< Maps blocks to border heads. */
  57
  58 #ifdef BUILD_GRAPH
  59         set *nodes;                                             /**< The interference graph nodes. */
  60         set *edges;                                             /**< The interference graph edges. */
  61 #endif
  62
  63         bitset_t *live;                         /**< A liveness bitset. */
  64         bitset_t *colors;                       /**< The color mask. */
  65         bitset_t *in_colors;    /**< Colors used by live in values. */
  66         int colors_n;                                   /**< The number of colors. */
  67         const arch_register_class_t *cls;   /**< The current register class. */
  68         void *data;           /**< Some pointer, to which different
  69                           phases can attach data to. */
  70 };
  71
  72 typedef struct _be_chordal_env_t be_chordal_env_t;
  73
  74 static INLINE struct list_head *_get_block_border_head(const be_chordal_env_t *inf, ir_node *bl) {
  75   return pmap_get(inf->border_heads, bl);
  76 }
  77
  78 #define get_block_border_head(info, bl)     _get_block_border_head(info, bl)
  79
  80 int nodes_interfere(const be_chordal_env_t *env, const ir_node *a, const ir_node *b);
  81
  82 #ifdef BUILD_GRAPH
  83 typedef struct _if_node_t {
  84         int nnr;
  85         pset *neighb;
  86 } if_node_t;
  87
  88 typedef struct _if_edge_t {
  89         int src, tgt;
  90 } if_edge_t;
  91
  92 set *be_ra_get_ifg_edges(const be_chordal_env_t *env);
  93 set *be_ra_get_ifg_nodes(const be_chordal_env_t *env);
  94
  95 int ifg_has_edge(const be_chordal_env_t *env, const if_node_t *n1, const if_node_t* n2);
  96
  97 #define ifn_get_degree(ifnode) pset_count(ifnode->neighb)
  98 #define foreach_neighb(ifnode, curr) \
  99                         for(curr=pset_first(ifnode->neighb); curr; curr=pset_next(ifnode->neighb))
 100 #endif
 101
 102 extern void be_ra_chordal_spill(be_chordal_env_t *env);
 103
 104 /**
 105  * Allocate registers for an ir graph.
 106  * @param irg The graph.
 107  * @return Some internal data to be freed with be_ra_chordal_done().
 108  */
 109 be_chordal_env_t *be_ra_chordal(
 110     const be_main_session_env_t *env,
 111     const arch_register_class_t *cls);
 112
 113 /**
 114  * Check current register allocation for correctness.
 115  * Interfering nodes have different colors
 116  * Register constraints
 117  * O(n^2)
 118  */
 119 void be_ra_chordal_check(be_chordal_env_t *chordal_env);
 120
 121 /**
 122  * Free data from the chordal register allocation.
 123  * @param irg The graph.
 124  */
 125 void be_ra_chordal_done(be_chordal_env_t *info);
 126
 127 /**
 128  * Init some things for the chordal register allocator.
 129  * This must be called before Firm is inited.
 130  */
 131 void be_ra_chordal_init(void);
 132
 133 /**
 134  * Check the register pressure in a graph.
 135  * @param env The sesion env.
 136  * @param cls The register class to consider.
 137  */
 138 void be_check_pressure(const be_main_session_env_t *env, const arch_register_class_t *cls);
 139
 140
 141 #endif /* _BECHORDAL_T_H */