+ return get_next_node(iter);
+}
+
+static void ifg_std_nodes_break(const void *self, void *iter)
+{
+ node_break(iter, 1);
+}
+
+typedef struct _adj_iter_t {
+ const be_chordal_env_t *env;
+ const ir_node *irn;
+ int reached_end;
+ pset *neighbours;
+} adj_iter_t;
+
+static void find_neighbour_walker(ir_node *block, void *data)
+{
+ adj_iter_t *it = data;
+ struct list_head *head = get_block_border_head(it->env, block);
+
+ border_t *b;
+ int has_started = 0;
+
+ if(!is_live_in(block, it->irn) && block != get_nodes_block(it->irn))
+ return;
+
+ foreach_border_head(head, b) {
+ ir_node *irn = b->irn;
+
+ if(irn == it->irn) {
+ if(b->is_def)
+ has_started = 1;
+ else
+ break; /* if we reached the end of the node's lifetime we can safely break */
+ }
+ else if(b->is_def) {
+ /* if any other node than the one in question starts living, add it to the set */
+ pset_insert_ptr(it->neighbours, irn);
+ }
+ else if(!has_started) {
+ /* we only delete, if the live range in question has not yet started */
+ pset_remove_ptr(it->neighbours, irn);
+ }
+
+ }
+}
+
+static void find_neighbours(const ifg_std_t *ifg, adj_iter_t *it, const ir_node *irn)
+{
+ it->env = ifg->env;
+ it->irn = irn;
+ it->neighbours = pset_new_ptr(16);
+ it->reached_end = 0;
+
+ dom_tree_walk(get_nodes_block(irn), find_neighbour_walker, NULL, it);
+}
+
+static INLINE void neighbours_break(adj_iter_t *it, int force)
+{
+ if((it->reached_end || force) && it->neighbours) {
+ del_pset(it->neighbours);
+ it->neighbours = NULL;
+ }
+}
+
+static ir_node *get_next_neighbour(adj_iter_t *it) {
+ ir_node *res = pset_next(it->neighbours);
+
+ it->reached_end = res == NULL;
+ neighbours_break(it, 0);
+
+ return res;
+}
+
+static ir_node *ifg_std_neighbours_begin(const void *self, void *iter, const ir_node *irn)
+{
+ adj_iter_t *it = iter;
+ find_neighbours(self, iter, irn);
+ return pset_first(it->neighbours);
+}
+
+static ir_node *ifg_std_neighbours_next(const void *self, void *iter)
+{
+ return get_next_neighbour(iter);
+}
+
+static void ifg_std_neighbours_break(const void *self, void *iter)
+{
+ neighbours_break(iter, 1);
+}
+
+typedef struct _cliques_iter_t {
+ struct obstack ob;
+ const be_chordal_env_t *cenv;
+ ir_node **buf;
+ ir_node **blocks;
+ int n_blocks, blk;
+ struct list_head *bor;
+ pset *living;
+} cliques_iter_t;
+
+static INLINE void free_clique_iter(cliques_iter_t *it) {
+ it->n_blocks = -1;
+ obstack_free(&it->ob, NULL);
+ del_pset(it->living);
+}
+
+static void get_blocks_dom_order(ir_node *blk, void *env) {
+ cliques_iter_t *it = env;
+ obstack_ptr_grow(&it->ob, blk);
+}
+
+#define pset_foreach(pset, irn) for(irn=pset_first(pset); irn; irn=pset_next(pset))
+
+
+/**
+ * NOTE: Be careful when changing this function!
+ * First understand the control flow of consecutive calls.
+ */
+static INLINE int get_next_clique(cliques_iter_t *it) {
+
+ /* continue in the block we left the last time */
+ for (; it->blk < it->n_blocks; it->blk++) {
+ int output_on_shrink = 0;
+ struct list_head *head = get_block_border_head(it->cenv, it->blocks[it->blk]);
+
+ /* on entry to a new block set the first border ... */
+ if (!it->bor)
+ it->bor = head->prev;
+
+ /* ... otherwise continue with the border we left the last time */
+ for (; it->bor != head; it->bor = it->bor->prev) {
+ border_t *b = list_entry(it->bor, border_t, list);
+
+ /* if its a definition irn starts living */
+ if (b->is_def) {
+ pset_insert_ptr(it->living, b->irn);
+ if (b->is_real)
+ output_on_shrink = 1;
+ } else
+
+ /* if its the last usage the irn dies */
+ {
+ /* before shrinking the set, return the current maximal clique */
+ if (output_on_shrink) {
+ int count = 0;
+ ir_node *irn;
+
+ /* fill the output buffer */
+ pset_foreach(it->living, irn)
+ it->buf[count++] = irn;
+
+ assert(count > 0 && "We have a 'last usage', so there must be sth. in it->living");
+
+ return count;
+ }
+
+ pset_remove_ptr(it->living, b->irn);
+ }
+ }
+
+ it->bor = NULL;
+ assert(0 == pset_count(it->living) && "Something has survived! (At the end of the block it->living must be empty)");
+ }
+
+ if (it->n_blocks != -1)
+ free_clique_iter(it);
+