3 * Internal datastructures for the chordal register allocator.
4 * @author Sebastian Hack
26 /** Defines an invalid register index. */
31 #define DBG_CHORDAL "firm.be.ra.chordal"
34 * A liveness interval border.
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. */
51 * Environment for each of the chordal register allocator phases
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. */
59 set *nodes; /**< The interference graph nodes. */
60 set *edges; /**< The interference graph edges. */
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. */
72 typedef struct _be_chordal_env_t be_chordal_env_t;
74 static INLINE struct list_head *
75 _get_block_border_head(const be_chordal_env_t *inf, ir_node *bl)
77 return pmap_get(inf->border_heads, bl);
80 #define get_block_border_head(info, bl) _get_block_border_head(info, bl)
82 int nodes_interfere(const be_chordal_env_t *env, const ir_node *a, const ir_node *b);
85 typedef struct _if_node_t {
90 typedef struct _if_edge_t {
94 set *be_ra_get_ifg_edges(const be_chordal_env_t *env);
95 set *be_ra_get_ifg_nodes(const be_chordal_env_t *env);
96 int ifg_has_edge(const be_chordal_env_t *env, const if_node_t *n1, const if_node_t* n2);
98 #define ifn_get_degree(ifnode) pset_count(ifnode->neighb)
99 #define foreach_neighb(ifnode, curr) \
100 for(curr=pset_first(ifnode->neighb); curr; curr=pset_next(ifnode->neighb))
103 extern void be_ra_chordal_spill(be_chordal_env_t *env);
106 * Allocate registers for an ir graph.
107 * @param irg The graph.
108 * @return Some internal data to be freed with be_ra_chordal_done().
110 be_chordal_env_t *be_ra_chordal(
111 const be_main_session_env_t *env,
112 const arch_register_class_t *cls);
115 * Check current register allocation for correctness.
116 * Interfering nodes have different colors
117 * Register constraints
120 void be_ra_chordal_check(be_chordal_env_t *chordal_env);
123 * Free data from the chordal register allocation.
124 * @param irg The graph.
126 void be_ra_chordal_done(be_chordal_env_t *info);
129 * Init some things for the chordal register allocator.
130 * This must be called before Firm is inited.
132 void be_ra_chordal_init(void);
135 * Check the register pressure in a graph.
136 * @param env The sesion env.
137 * @param cls The register class to consider.
139 void be_check_pressure(const be_main_session_env_t *env, const arch_register_class_t *cls);
142 #endif /* _BECHORDAL_T_H */