/*
- * Copyright (C) 1995-2007 University of Karlsruhe. All right reserved.
+ * Copyright (C) 1995-2008 University of Karlsruhe. All right reserved.
*
* This file is part of libFirm.
*
*/
/**
- * @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
#include <stdlib.h>
-#include "benodesets.h"
#include "list.h"
#include "irnode_t.h"
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);
+ ir_nodeset_t live;
+ 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;
+ ir_nodeset_init(&live);
- 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 */
{
if (b->is_def)
{
create_node(ifg, b->irn); /* add the node to the array of all nodes of this ifg implementation */
- nodeset_insert(live, b->irn);
+ ir_nodeset_insert(&live, b->irn);
if (b->is_real) /* this is a new node */
{
- foreach_nodeset(live, live_irn)
+ ir_nodeset_iterator_t iter;
+
+ foreach_ir_nodeset(&live, live_irn, iter)
{
if (b->irn != live_irn) /* add a as a neighbour to b and vice versa */
add_edge(ifg, b->irn, live_irn);
}
else /* b->irn is now dead */
{
- if (nodeset_find(live, b->irn))
- nodeset_remove(live, b->irn);
+ ir_nodeset_remove(&live, b->irn);
}
}
- if (live)
- del_nodeset(live);
+ ir_nodeset_destroy(&live);
}
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;
}
be_ifg_t *be_ifg_list_new(const be_chordal_env_t *env)
{
- ifg_list_t *ifg = xmalloc(sizeof(*ifg));
- adj_head_t **adj_heads_array = xmalloc(env->irg->last_node_idx * sizeof(adj_heads_array[0]));
+ ifg_list_t *ifg = XMALLOC(ifg_list_t);
+ adj_head_t **adj_heads_array = XMALLOCNZ(adj_head_t*, env->irg->last_node_idx);
ifg->impl = &ifg_list_impl;
ifg->env = env;
- memset(adj_heads_array, 0, env->irg->last_node_idx * sizeof(adj_heads_array[0]));
ifg->adj_heads = adj_heads_array;
obstack_init(&ifg->obst);
projects / libfirm / blobdiff