*/
/**
- * @file beifg_list.c
- * @date 18.11.2005
- * @author Sebastian Hack
- *
- * Copyright (C) 2005 Universitaet Karlsruhe
- * Released under the GPL
+ * @file
+ * @brief List based implementation of chordal interference graphs.
+ * @author Sebastian Hack
+ * @date 18.11.2005
+ * @version $Id$
*/
-
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif
typedef struct _adj_head_t adj_head_t;
typedef struct _ifg_list_t {
- const be_ifg_impl_t *impl;
+ const be_ifg_impl_t *impl;
const be_chordal_env_t *env;
- struct obstack obst;
- adj_head_t **adj_heads;
+ struct obstack obst;
+ adj_head_t **adj_heads;
} ifg_list_t;
typedef struct _adj_element_t adj_element_t;
struct _adj_element_t {
adj_element_t *next_adj_element;
- ir_node *neighbour;
+ ir_node *neighbour;
};
struct _adj_head_t {
- ir_node *irn; /* the node you search neighbours for */
+ ir_node *irn; /* the node you search neighbours for */
adj_element_t *first_adj_element;
- int degree;
+ int degree;
};
typedef struct _nodes_iter_t {
const ifg_list_t *ifg;
- unsigned int curr_node_idx;
+ unsigned int curr_node_idx;
} nodes_iter_t;
typedef struct _adj_iter_t {
const ifg_list_t *ifg;
- adj_element_t *curr_adj_element;
+ adj_element_t *curr_adj_element;
} adj_iter_t;
/* PRIVATE FUNCTIONS */
-static void create_node (ifg_list_t *ifg, ir_node *irn) /* add node to the array of all nodes in this ifg implementation, if the node isn't already in the ifg */
+/* add node to the array of all nodes in this ifg implementation, if the node isn't already in the ifg */
+static void create_node(ifg_list_t *ifg, ir_node *irn)
{
adj_head_t *adj_head = NULL;
return element;
}
-static void add_edge(ifg_list_t *ifg, ir_node *node_a, ir_node *node_b) /* write the information about the edge between a and b */
+/* write the information about the edge between a and b */
+static void add_edge(ifg_list_t *ifg, ir_node *node_a, ir_node *node_b)
{
- adj_head_t *adj_head = NULL;
+ adj_head_t *adj_head = NULL;
adj_element_t *curr_element = NULL;
- adj_element_t *new_element = NULL;
+ adj_element_t *new_element = NULL;
adj_head = ifg->adj_heads[node_a->node_idx]; /* find the neighbours list of a */
}
}
-static void find_neighbour_walker(ir_node *bl, void *data) /* find all adjacent nodes in the irg */
+/* find all adjacent nodes in the irg */
+static void find_neighbour_walker(ir_node *bl, void *data)
{
- ifg_list_t *ifg = data;
- struct list_head *head = get_block_border_head(ifg->env, bl);
+ ifg_list_t *ifg = data;
+ struct list_head *head = get_block_border_head(ifg->env, bl);
+ nodeset *live = new_nodeset(ifg->env->cls->n_regs);
+ ir_node *live_irn = NULL;
+ border_t *b = NULL;
- nodeset *live = new_nodeset(ifg->env->cls->n_regs);
- ir_node *live_irn = NULL;
- border_t *b = NULL;
-
- assert (is_Block(bl) && "There is no block to work on");
+ assert(is_Block(bl) && "There is no block to work on");
foreach_border_head(head, b) /* follow the borders of each block */
{
static ir_node *get_first_node(const ifg_list_t *ifg, nodes_iter_t *it)
{
- ir_node *res = NULL;
- adj_head_t *adj_head= NULL;
- int curr_idx = -1;
+ ir_node *res = NULL;
+ adj_head_t *adj_head = NULL;
+ int curr_idx = -1;
it->ifg = ifg;
it->curr_node_idx = 0;
static ir_node *get_next_node(nodes_iter_t *it)
{
- const ifg_list_t *ifg = it->ifg;
- ir_node *res = NULL;
- adj_head_t *adj_head= NULL;
- unsigned int curr_idx = it->curr_node_idx;
+ const ifg_list_t *ifg = it->ifg;
+ ir_node *res = NULL;
+ adj_head_t *adj_head = NULL;
+ unsigned int curr_idx = it->curr_node_idx;
while (adj_head == NULL && curr_idx < it->ifg->env->irg->last_node_idx - 1)
{
static ir_node *get_first_neighbour(const ifg_list_t *ifg, adj_iter_t *it, const ir_node *curr_irn)
{
- ir_node *res = NULL;
+ ir_node *res = NULL;
adj_head_t *adj_head = NULL;
adj_head = ifg->adj_heads[curr_irn->node_idx];
- assert (adj_head && "There is no entry for this node");
+ assert(adj_head && "There is no entry for this node");
it->curr_adj_element = NULL;
it->ifg = ifg;
static ir_node *get_next_neighbour(adj_iter_t *it)
{
- ir_node *res = NULL;
+ ir_node *res = NULL;
adj_element_t *element = it->curr_adj_element;
if (element->next_adj_element) /* return next neighbour */
static int ifg_list_connected(const void *self, const ir_node *a, const ir_node *b)
{
- const ifg_list_t *ifg = self;
- int res = -1;
- adj_head_t *adj_head = NULL;
- adj_element_t *curr_element = NULL;
+ const ifg_list_t *ifg = self;
+ int res = -1;
+ adj_head_t *adj_head = NULL;
+ adj_element_t *curr_element = NULL;
/* first try: find b in the neigbours of a */
adj_head = ifg->adj_heads[a->node_idx];
assert(adj_head && "There is no entry for the node a");
curr_element = adj_head->first_adj_element;
- if(curr_element)
+ if (curr_element)
{
while (curr_element->neighbour != b && curr_element->next_adj_element)
{
assert(adj_head && "There is no entry for the node b");
curr_element = adj_head->first_adj_element;
- if(curr_element)
+ if (curr_element)
{
while (curr_element->neighbour != a && curr_element->next_adj_element)
{
static ir_node *ifg_list_nodes_next(const void *self, void *iter)
{
+ (void) self;
return get_next_node(iter);
}
static void ifg_list_nodes_break(const void *self, void *iter)
{
nodes_iter_t *it = iter;
+ (void) self;
it->curr_node_idx = 0;
it->ifg = NULL;
}
static ir_node *ifg_list_neighbours_next(const void *self, void *iter)
{
+ (void) self;
return get_next_neighbour(iter);
}
static void ifg_list_neighbours_break(const void *self, void *iter)
{
adj_iter_t *it= iter;
+ (void) self;
it->curr_adj_element = NULL;
it->ifg = NULL;
}