combo.c

/*
 * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
 *
 * This file is part of libFirm.
 *
 * This file may be distributed and/or modified under the terms of the
 * GNU General Public License version 2 as published by the Free Software
 * Foundation and appearing in the file LICENSE.GPL included in the
 * packaging of this file.
 *
 * Licensees holding valid libFirm Professional Edition licenses may use
 * this file in accordance with the libFirm Commercial License.
 * Agreement provided with the Software.
 *
 * This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 * WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE.
 */

/**
 * @file
 * @brief   Cliff Click's Combined Analysis/Optimization
 * @author  Michael Beck
 * @version $Id$
 *
 * This is a slightly enhanced version of Cliff Clicks combo algorithm
 * - support for commutative nodes is added, Add(a,b) and Add(b,a) ARE congruent
 * - supports all Firm direct (by a data edge) identities except Mux
 *   (Mux can be a 2-input or 1-input identity, only 2-input is implemented yet)
 * - supports Confirm nodes (handle them like Copies but do NOT remove them)
 * - let Cmp nodes calculate Top like all othe data nodes: this would let
 *   Mux nodes to calculate Unknown instead of taking the true result
 * - let Cond(Top) always select FALSE/default: This is tricky. Nodes are only reavaluated
 *   IFF the predecessor changed its type. Because nodes are initialized with Top
 *   this never happens, let all Proj(Cond) be unreachable.
 *   We avoid this condition by the same way we work around Phi: whenever a Block
 *   node is placed on the list, place its Cond nodes (and because they are Tuple
 *   all its Proj-nodes either on the cprop list)
 *   Especially, this changes the meaning of Click's example:
 *
 *   int main() {
 *     int x;
 *
 *     if (x == 2)
 *       printf("x == 2\n");
 *     if (x == 3)
 *       printf("x == 3\n");
 *   }
 *
 *   Would print:
 *   x == 2
 *   x == 3
 *
 *   using Click's version while is silent with our.
 * - support for global congruences is implemented but not tested yet
 *
 * Note further that we use the terminology from Click's work here, which is different
 * in some cases from Firm terminology.  Especially, Click's type is a
 * Firm tarval/entity, nevertheless we call it type here for "maximum compatibility".
 */
#include "config.h"

#include <assert.h>

#include "iroptimize.h"
#include "irflag.h"
#include "ircons.h"
#include "list.h"
#include "set.h"
#include "pmap.h"
#include "obstack.h"
#include "irgraph_t.h"
#include "irnode_t.h"
#include "iropt_t.h"
#include "irgwalk.h"
#include "irop.h"
#include "irouts.h"
#include "irgmod.h"
#include "iropt_dbg.h"
#include "debug.h"
#include "array_t.h"
#include "error.h"
#include "irnodeset.h"

#include "tv_t.h"

#include "irprintf.h"
#include "irdump.h"

/* define this to check that all type translations are monotone */
#define VERIFY_MONOTONE

/* define this to check the consistency of partitions */
#define CHECK_PARTITIONS

typedef struct node_t            node_t;
typedef struct partition_t       partition_t;
typedef struct opcode_key_t      opcode_key_t;
typedef struct listmap_entry_t   listmap_entry_t;

/** The type of the compute function. */
typedef void (*compute_func)(node_t *node);

/**
 * An opcode map key.
 */
struct opcode_key_t {
	ir_opcode   code;   /**< The Firm opcode. */
	ir_mode     *mode;  /**< The mode of all nodes in the partition. */
	int         arity;  /**< The arity of this opcode (needed for Phi etc. */
	union {
		long      proj;   /**< For Proj nodes, its proj number */
		ir_entity *ent;   /**< For Sel Nodes, its entity */
		int       intVal; /**< For Conv/Div Nodes: strict/remainderless */
		unsigned  uintVal;/**< for Builtin: the kind */
		ir_node   *block; /**< for Block: itself */
		void      *ptr;   /**< generic pointer for hash/cmp */
	} u;
};

/**
 * An entry in the list_map.
 */
struct listmap_entry_t {
	void            *id;    /**< The id. */
	node_t          *list;  /**< The associated list for this id. */
	listmap_entry_t *next;  /**< Link to the next entry in the map. */
};

/** We must map id's to lists. */
typedef struct listmap_t {
	set             *map;    /**< Map id's to listmap_entry_t's */
	listmap_entry_t *values; /**< List of all values in the map. */
} listmap_t;

/**
 * A lattice element. Because we handle constants and symbolic constants different, we
 * have to use this union.
 */
typedef union {
	tarval          *tv;
	symconst_symbol sym;
} lattice_elem_t;

/**
 * A node.
 */
struct node_t {
	ir_node         *node;          /**< The IR-node itself. */
	list_head       node_list;      /**< Double-linked list of leader/follower entries. */
	list_head       cprop_list;     /**< Double-linked partition.cprop list. */
	partition_t     *part;          /**< points to the partition this node belongs to */
	node_t          *next;          /**< Next node on local list (partition.touched, fallen). */
	node_t          *race_next;     /**< Next node on race list. */
	lattice_elem_t  type;           /**< The associated lattice element "type". */
	int             max_user_input; /**< Maximum input number of Def-Use edges. */
	int             next_edge;      /**< Index of the next Def-Use edge to use. */
	int             n_followers;    /**< Number of Follower in the outs set. */
	unsigned        on_touched:1;   /**< Set, if this node is on the partition.touched set. */
	unsigned        on_cprop:1;     /**< Set, if this node is on the partition.cprop list. */
	unsigned        on_fallen:1;    /**< Set, if this node is on the fallen list. */
	unsigned        is_follower:1;  /**< Set, if this node is a follower. */
	unsigned        flagged:2;      /**< 2 Bits, set if this node was visited by race 1 or 2. */
};

/**
 * A partition containing congruent nodes.
 */
struct partition_t {
	list_head         Leader;          /**< The head of partition Leader node list. */
	list_head         Follower;        /**< The head of partition Follower node list. */
	list_head         cprop;           /**< The head of partition.cprop list. */
	list_head         cprop_X;         /**< The head of partition.cprop (Cond nodes and its Projs) list. */
	partition_t       *wl_next;        /**< Next entry in the work list if any. */
	partition_t       *touched_next;   /**< Points to the next partition in the touched set. */
	partition_t       *cprop_next;     /**< Points to the next partition in the cprop list. */
	partition_t       *split_next;     /**< Points to the next partition in the list that must be split by split_by(). */
	node_t            *touched;        /**< The partition.touched set of this partition. */
	unsigned          n_leader;        /**< Number of entries in this partition.Leader. */
	unsigned          n_touched;       /**< Number of entries in the partition.touched. */
	int               max_user_inputs; /**< Maximum number of user inputs of all entries. */
	unsigned          on_worklist:1;   /**< Set, if this partition is in the work list. */
	unsigned          on_touched:1;    /**< Set, if this partition is on the touched set. */
	unsigned          on_cprop:1;      /**< Set, if this partition is on the cprop list. */
	unsigned          type_is_T_or_C:1;/**< Set, if all nodes in this partition have type Top or Constant. */
#ifdef DEBUG_libfirm
	partition_t       *dbg_next;       /**< Link all partitions for debugging */
	unsigned          nr;              /**< A unique number for (what-)mapping, >0. */
#endif
};

typedef struct environment_t {
	struct obstack  obst;           /**< obstack to allocate data structures. */
	partition_t     *worklist;      /**< The work list. */
	partition_t     *cprop;         /**< The constant propagation list. */
	partition_t     *touched;       /**< the touched set. */
	partition_t     *initial;       /**< The initial partition. */
	set             *opcode2id_map; /**< The opcodeMode->id map. */
	pmap            *type2id_map;   /**< The type->id map. */
	ir_node         **kept_memory;  /**< Array of memory nodes that must be kept. */
	int             end_idx;        /**< -1 for local and 0 for global congruences. */
	int             lambda_input;   /**< Captured argument for lambda_partition(). */
	unsigned        modified:1;     /**< Set, if the graph was modified. */
	unsigned        unopt_cf:1;     /**< If set, control flow is not optimized due to Unknown. */
	/* options driving the optimization */
	unsigned        commutative:1;  /**< Set, if commutation nodes should be handled specially. */
	unsigned        opt_unknown:1;  /**< Set, if non-strict programs should be optimized. */
#ifdef DEBUG_libfirm
	partition_t     *dbg_list;      /**< List of all partitions. */
#endif
} environment_t;

/** Type of the what function. */
typedef void *(*what_func)(const node_t *node, environment_t *env);

#define get_irn_node(irn)         ((node_t *)get_irn_link(irn))
#define set_irn_node(irn, node)   set_irn_link(irn, node)

/* we do NOT use tarval_unreachable here, instead we use Top for this purpose */
#undef tarval_unreachable
#define tarval_unreachable tarval_top


/** The debug module handle. */
DEBUG_ONLY(static firm_dbg_module_t *dbg;)

/** The what reason. */
DEBUG_ONLY(static const char *what_reason;)

/** Next partition number. */
DEBUG_ONLY(static unsigned part_nr = 0);

/** The tarval returned by Unknown nodes: set to either tarval_bad OR tarval_top. */
static tarval *tarval_UNKNOWN;

/* forward */
static node_t *identity(node_t *node);

#ifdef CHECK_PARTITIONS
/**
 * Check a partition.
 */
static void check_partition(const partition_t *T) {
	node_t   *node;
	unsigned n = 0;

	list_for_each_entry(node_t, node, &T->Leader, node_list) {
		assert(node->is_follower == 0);
		assert(node->flagged == 0);
		assert(node->part == T);
		++n;
	}
	assert(n == T->n_leader);

	list_for_each_entry(node_t, node, &T->Follower, node_list) {
		assert(node->is_follower == 1);
		assert(node->flagged == 0);
		assert(node->part == T);
	}
}  /* check_partition */

/**
 * check that all leader nodes in the partition have the same opcode.
 */
static void check_opcode(const partition_t *Z) {
	node_t       *node;
	opcode_key_t key;
	int          first = 1;

	list_for_each_entry(node_t, node, &Z->Leader, node_list) {
		ir_node *irn = node->node;

		if (first) {
			key.code   = get_irn_opcode(irn);
			key.mode   = get_irn_mode(irn);
			key.arity  = get_irn_arity(irn);
			key.u.proj = 0;
			key.u.ent  = NULL;

			switch (get_irn_opcode(irn)) {
			case iro_Proj:
				key.u.proj = get_Proj_proj(irn);
				break;
			case iro_Sel:
				key.u.ent = get_Sel_entity(irn);
				break;
			case iro_Conv:
				key.u.intVal = get_Conv_strict(irn);
				break;
			case iro_Div:
				key.u.intVal = is_Div_remainderless(irn);
				break;
			case iro_Block:
				key.u.block = irn;
				break;
			case iro_Load:
				key.mode = get_Load_mode(irn);
				break;
			case iro_Builtin:
				key.u.intVal = get_Builtin_kind(irn);
				break;
			default:
				break;
			}
			first = 0;
		} else {
			assert((unsigned)key.code  == get_irn_opcode(irn));
			assert(key.mode  == get_irn_mode(irn));
			assert(key.arity == get_irn_arity(irn));

			switch (get_irn_opcode(irn)) {
			case iro_Proj:
				assert(key.u.proj == get_Proj_proj(irn));
				break;
			case iro_Sel:
				assert(key.u.ent == get_Sel_entity(irn));
				break;
			case iro_Conv:
				assert(key.u.intVal == get_Conv_strict(irn));
				break;
			case iro_Div:
				assert(key.u.intVal == is_Div_remainderless(irn));
				break;
			case iro_Block:
				assert(key.u.block == irn);
				break;
			case iro_Load:
				assert(key.mode == get_Load_mode(irn));
				break;
			case iro_Builtin:
				assert(key.u.intVal == (int) get_Builtin_kind(irn));
				break;
			default:
				break;
			}
		}
	}
}  /* check_opcode */

static void check_all_partitions(environment_t *env) {
#ifdef DEBUG_libfirm
	partition_t *P;
	node_t      *node;

	for (P = env->dbg_list; P != NULL; P = P->dbg_next) {
		check_partition(P);
		if (! P->type_is_T_or_C)
			check_opcode(P);
		list_for_each_entry(node_t, node, &P->Follower, node_list) {
			node_t *leader = identity(node);

			assert(leader != node && leader->part == node->part);
		}
	}
#endif
}

/**
 * Check list.
 */
static void do_check_list(const node_t *list, int ofs, const partition_t *Z) {
	const node_t *e;

#define NEXT(e)  *((const node_t **)((char *)(e) + (ofs)))
	for (e = list; e != NULL; e = NEXT(e)) {
		assert(e->part == Z);
	}
#undef NEXT
}  /* ido_check_list */

/**
 * Check a local list.
 */
static void check_list(const node_t *list, const partition_t *Z) {
	do_check_list(list, offsetof(node_t, next), Z);
}  /* check_list */

#else
#define check_partition(T)
#define check_list(list, Z)
#define check_all_partitions(env)
#endif /* CHECK_PARTITIONS */

#ifdef DEBUG_libfirm
static inline lattice_elem_t get_partition_type(const partition_t *X);

/**
 * Dump partition to output.
 */
static void dump_partition(const char *msg, const partition_t *part) {
	const node_t   *node;
	int            first = 1;
	lattice_elem_t type = get_partition_type(part);

	DB((dbg, LEVEL_2, "%s part%u%s (%u, %+F) {\n  ",
		msg, part->nr, part->type_is_T_or_C ? "*" : "",
		part->n_leader, type));
	list_for_each_entry(node_t, node, &part->Leader, node_list) {
		DB((dbg, LEVEL_2, "%s%+F", first ? "" : ", ", node->node));
		first = 0;
	}
	if (! list_empty(&part->Follower)) {
		DB((dbg, LEVEL_2, "\n---\n  "));
		first = 1;
		list_for_each_entry(node_t, node, &part->Follower, node_list) {
			DB((dbg, LEVEL_2, "%s%+F", first ? "" : ", ", node->node));
			first = 0;
		}
	}
	DB((dbg, LEVEL_2, "\n}\n"));
}  /* dump_partition */

/**
 * Dumps a list.
 */
static void do_dump_list(const char *msg, const node_t *node, int ofs) {
	const node_t *p;
	int          first = 1;

#define GET_LINK(p, ofs)  *((const node_t **)((char *)(p) + (ofs)))

	DB((dbg, LEVEL_3, "%s = {\n  ", msg));
	for (p = node; p != NULL; p = GET_LINK(p, ofs)) {
		DB((dbg, LEVEL_3, "%s%+F", first ? "" : ", ", p->node));
		first = 0;
	}
	DB((dbg, LEVEL_3, "\n}\n"));

#undef GET_LINK
}  /* do_dump_list */

/**
 * Dumps a race list.
 */
static void dump_race_list(const char *msg, const node_t *list) {
	do_dump_list(msg, list, offsetof(node_t, race_next));
}  /* dump_race_list */

/**
 * Dumps a local list.
 */
static void dump_list(const char *msg, const node_t *list) {
	do_dump_list(msg, list, offsetof(node_t, next));
}  /* dump_list */

/**
 * Dump all partitions.
 */
static void dump_all_partitions(const environment_t *env) {
	const partition_t *P;

	DB((dbg, LEVEL_2, "All partitions\n===============\n"));
	for (P = env->dbg_list; P != NULL; P = P->dbg_next)
		dump_partition("", P);
}  /* dump_all_partitions */

/**
 * Sump a split list.
 */
static void dump_split_list(const partition_t *list) {
	const partition_t *p;

	DB((dbg, LEVEL_2, "Split by %s produced = {\n", what_reason));
	for (p = list; p != NULL; p = p->split_next)
		DB((dbg, LEVEL_2, "part%u, ", p->nr));
	DB((dbg, LEVEL_2, "\n}\n"));
}  /* dump_split_list */

/**
 * Dump partition and type for a node.
 */
static int dump_partition_hook(FILE *F, ir_node *n, ir_node *local) {
	ir_node *irn = local != NULL ? local : n;
	node_t *node = get_irn_node(irn);

	ir_fprintf(F, "info2 : \"partition %u type %+F\"\n", node->part->nr, node->type);
	return 1;
}  /* dump_partition_hook */

#else
#define dump_partition(msg, part)
#define dump_race_list(msg, list)
#define dump_list(msg, list)
#define dump_all_partitions(env)
#define dump_split_list(list)
#endif

#if defined(VERIFY_MONOTONE) && defined (DEBUG_libfirm)
/**
 * Verify that a type transition is monotone
 */
static void verify_type(const lattice_elem_t old_type, node_t *node) {
	if (old_type.tv == node->type.tv) {
		/* no change */
		return;
	}
	if (old_type.tv == tarval_top) {
		/* from Top down-to is always allowed */
		return;
	}
	if (node->type.tv == tarval_bottom || node->type.tv == tarval_reachable) {
		/* bottom reached */
		return;
	}
	panic("combo: wrong translation from %+F to %+F on node %+F", old_type, node->type, node->node);
}  /* verify_type */

#else
#define verify_type(old_type, node)
#endif

/**
 * Compare two pointer values of a listmap.
 */
static int listmap_cmp_ptr(const void *elt, const void *key, size_t size) {
	const listmap_entry_t *e1 = elt;
	const listmap_entry_t *e2 = key;

	(void) size;
	return e1->id != e2->id;
}  /* listmap_cmp_ptr */

/**
 * Initializes a listmap.
 *
 * @param map  the listmap
 */
static void listmap_init(listmap_t *map) {
	map->map    = new_set(listmap_cmp_ptr, 16);
	map->values = NULL;
}  /* listmap_init */

/**
 * Terminates a listmap.
 *
 * @param map  the listmap
 */
static void listmap_term(listmap_t *map) {
	del_set(map->map);
}  /* listmap_term */

/**
 * Return the associated listmap entry for a given id.
 *
 * @param map  the listmap
 * @param id   the id to search for
 *
 * @return the associated listmap entry for the given id
 */
static listmap_entry_t *listmap_find(listmap_t *map, void *id) {
	listmap_entry_t key, *entry;

	key.id   = id;
	key.list = NULL;
	key.next = NULL;
	entry = set_insert(map->map, &key, sizeof(key), HASH_PTR(id));

	if (entry->list == NULL) {
		/* a new entry, put into the list */
		entry->next = map->values;
		map->values = entry;
	}
	return entry;
}  /* listmap_find */

/**
 * Calculate the hash value for an opcode map entry.
 *
 * @param entry  an opcode map entry
 *
 * @return a hash value for the given opcode map entry
 */
static unsigned opcode_hash(const opcode_key_t *entry) {
	return (entry->mode - (ir_mode *)0) * 9 + entry->code + entry->u.proj * 3 + HASH_PTR(entry->u.ptr) + entry->arity;
}  /* opcode_hash */

/**
 * Compare two entries in the opcode map.
 */
static int cmp_opcode(const void *elt, const void *key, size_t size) {
	const opcode_key_t *o1 = elt;
	const opcode_key_t *o2 = key;

	(void) size;
	return o1->code != o2->code || o1->mode != o2->mode ||
	       o1->arity != o2->arity ||
	       o1->u.proj != o2->u.proj ||
	       o1->u.intVal != o2->u.intVal || /* this already checks uIntVal */
	       o1->u.ptr != o2->u.ptr;
}  /* cmp_opcode */

/**
 * Compare two Def-Use edges for input position.
 */
static int cmp_def_use_edge(const void *a, const void *b) {
	const ir_def_use_edge *ea = a;
	const ir_def_use_edge *eb = b;

	/* no overrun, because range is [-1, MAXINT] */
	return ea->pos - eb->pos;
}  /* cmp_def_use_edge */

/**
 * We need the Def-Use edges sorted.
 */
static void sort_irn_outs(node_t *node) {
	ir_node *irn = node->node;
	int n_outs = get_irn_n_outs(irn);

	if (n_outs > 1) {
		qsort(&irn->out[1], n_outs, sizeof(irn->out[0]), cmp_def_use_edge);
	}
	node->max_user_input = irn->out[n_outs].pos;
}  /* sort_irn_outs */

/**
 * Return the type of a node.
 *
 * @param irn  an IR-node
 *
 * @return the associated type of this node
 */
static inline lattice_elem_t get_node_type(const ir_node *irn) {
	return get_irn_node(irn)->type;
}  /* get_node_type */

/**
 * Return the tarval of a node.
 *
 * @param irn  an IR-node
 *
 * @return the associated type of this node
 */
static inline tarval *get_node_tarval(const ir_node *irn) {
	lattice_elem_t type = get_node_type(irn);

	if (is_tarval(type.tv))
		return type.tv;
	return tarval_bottom;
}  /* get_node_type */

/**
 * Add a partition to the worklist.
 */
static inline void add_to_worklist(partition_t *X, environment_t *env) {
	assert(X->on_worklist == 0);
	DB((dbg, LEVEL_2, "Adding part%d to worklist\n", X->nr));
	X->wl_next     = env->worklist;
	X->on_worklist = 1;
	env->worklist  = X;
}  /* add_to_worklist */

/**
 * Create a new empty partition.
 *
 * @param env   the environment
 *
 * @return a newly allocated partition
 */
static inline partition_t *new_partition(environment_t *env) {
	partition_t *part = obstack_alloc(&env->obst, sizeof(*part));

	INIT_LIST_HEAD(&part->Leader);
	INIT_LIST_HEAD(&part->Follower);
	INIT_LIST_HEAD(&part->cprop);
	INIT_LIST_HEAD(&part->cprop_X);
	part->wl_next         = NULL;
	part->touched_next    = NULL;
	part->cprop_next      = NULL;
	part->split_next      = NULL;
	part->touched         = NULL;
	part->n_leader        = 0;
	part->n_touched       = 0;
	part->max_user_inputs = 0;
	part->on_worklist     = 0;
	part->on_touched      = 0;
	part->on_cprop        = 0;
	part->type_is_T_or_C  = 0;
#ifdef DEBUG_libfirm
	part->dbg_next        = env->dbg_list;
	env->dbg_list         = part;
	part->nr              = part_nr++;
#endif

	return part;
}  /* new_partition */

/**
 * Get the first node from a partition.
 */
static inline node_t *get_first_node(const partition_t *X) {
	return list_entry(X->Leader.next, node_t, node_list);
}  /* get_first_node */

/**
 * Return the type of a partition (assuming partition is non-empty and
 * all elements have the same type).
 *
 * @param X  a partition
 *
 * @return the type of the first element of the partition
 */
static inline lattice_elem_t get_partition_type(const partition_t *X) {
	const node_t *first = get_first_node(X);
	return first->type;
}  /* get_partition_type */

/**
 * Creates a partition node for the given IR-node and place it
 * into the given partition.
 *
 * @param irn   an IR-node
 * @param part  a partition to place the node in
 * @param env   the environment
 *
 * @return the created node
 */
static node_t *create_partition_node(ir_node *irn, partition_t *part, environment_t *env) {
	/* create a partition node and place it in the partition */
	node_t *node = obstack_alloc(&env->obst, sizeof(*node));

	INIT_LIST_HEAD(&node->node_list);
	INIT_LIST_HEAD(&node->cprop_list);
	node->node           = irn;
	node->part           = part;
	node->next           = NULL;
	node->race_next      = NULL;
	node->type.tv        = tarval_top;
	node->max_user_input = 0;
	node->next_edge      = 0;
	node->n_followers    = 0;
	node->on_touched     = 0;
	node->on_cprop       = 0;
	node->on_fallen      = 0;
	node->is_follower    = 0;
	node->flagged        = 0;
	set_irn_node(irn, node);

	list_add_tail(&node->node_list, &part->Leader);
	++part->n_leader;

	return node;
}  /* create_partition_node */

/**
 * Pre-Walker, initialize all Nodes' type to U or top and place
 * all nodes into the TOP partition.
 */
static void create_initial_partitions(ir_node *irn, void *ctx) {
	environment_t *env  = ctx;
	partition_t   *part = env->initial;
	node_t        *node;

	node = create_partition_node(irn, part, env);
	sort_irn_outs(node);
	if (node->max_user_input > part->max_user_inputs)
		part->max_user_inputs = node->max_user_input;

	if (is_Block(irn)) {
		set_Block_phis(irn, NULL);
	}
}  /* create_initial_partitions */

/**
 * Post-Walker, collect  all Block-Phi lists, set Cond.
 */
static void init_block_phis(ir_node *irn, void *ctx) {
	(void) ctx;

	if (is_Phi(irn)) {
		add_Block_phi(get_nodes_block(irn), irn);
	}
}  /* init_block_phis */

/**
 * Add a node to the entry.partition.touched set and
 * node->partition to the touched set if not already there.
 *
 * @param y    a node
 * @param env  the environment
 */
static inline void add_to_touched(node_t *y, environment_t *env) {
	if (y->on_touched == 0) {
		partition_t *part = y->part;

		y->next       = part->touched;
		part->touched = y;
		y->on_touched = 1;
		++part->n_touched;

		if (part->on_touched == 0) {
			part->touched_next = env->touched;
			env->touched       = part;
			part->on_touched   = 1;
		}

		check_list(part->touched, part);
	}
}  /* add_to_touched */

/**
 * Place a node on the cprop list.
 *
 * @param y    the node
 * @param env  the environment
 */
static void add_to_cprop(node_t *y, environment_t *env) {
	ir_node *irn;

	/* Add y to y.partition.cprop. */
	if (y->on_cprop == 0) {
		partition_t *Y = y->part;
		ir_node *irn   = y->node;

		/* place Conds and all its Projs on the cprop_X list */
		if (is_Cond(skip_Proj(irn)))
			list_add_tail(&y->cprop_list, &Y->cprop_X);
		else
			list_add_tail(&y->cprop_list, &Y->cprop);
		y->on_cprop   = 1;

		DB((dbg, LEVEL_3, "Add %+F to part%u.cprop\n", y->node, Y->nr));

		/* place its partition on the cprop list */
		if (Y->on_cprop == 0) {
			Y->cprop_next = env->cprop;
			env->cprop    = Y;
			Y->on_cprop   = 1;
		}
	}
	irn = y->node;
	if (get_irn_mode(irn) == mode_T) {
		/* mode_T nodes always produce tarval_bottom, so we must explicitly
		   add it's Proj's to get constant evaluation to work */
		int i;

		for (i = get_irn_n_outs(irn) - 1; i >= 0; --i) {
			node_t *proj = get_irn_node(get_irn_out(irn, i));

			add_to_cprop(proj, env);
		}
	} else if (is_Block(irn)) {
		/* Due to the way we handle Phi's, we must place all Phis of a block on the list
		 * if someone placed the block. The Block is only placed if the reachability
		 * changes, and this must be re-evaluated in compute_Phi(). */
		ir_node *phi;
		for (phi = get_Block_phis(irn); phi != NULL; phi = get_Phi_next(phi)) {
			node_t *p = get_irn_node(phi);
			add_to_cprop(p, env);
		}
	}
}  /* add_to_cprop */

/**
 * Update the worklist: If Z is on worklist then add Z' to worklist.
 * Else add the smaller of Z and Z' to worklist.
 *
 * @param Z        the Z partition
 * @param Z_prime  the Z' partition, a previous part of Z
 * @param env      the environment
 */
static void update_worklist(partition_t *Z, partition_t *Z_prime, environment_t *env) {
	if (Z->on_worklist || Z_prime->n_leader < Z->n_leader) {
		add_to_worklist(Z_prime, env);
	} else {
		add_to_worklist(Z, env);
	}
}  /* update_worklist */

/**
 * Make all inputs to x no longer be F.def_use edges.
 *
 * @param x  the node
 */
static void move_edges_to_leader(node_t *x) {
	ir_node     *irn = x->node;
	int         i, j, k;

	for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
		node_t  *pred = get_irn_node(get_irn_n(irn, i));
		ir_node *p;
		int     n;

		p = pred->node;
		n = get_irn_n_outs(p);
		for (j = 1; j <= pred->n_followers; ++j) {
			if (p->out[j].pos == i && p->out[j].use == irn) {
				/* found a follower edge to x, move it to the Leader */
				ir_def_use_edge edge = p->out[j];

				/* remove this edge from the Follower set */
				p->out[j] = p->out[pred->n_followers];
				--pred->n_followers;

				/* sort it into the leader set */
				for (k = pred->n_followers + 2; k <= n; ++k) {
					if (p->out[k].pos >= edge.pos)
						break;
					p->out[k - 1] = p->out[k];
				}
				/* place the new edge here */
				p->out[k - 1] = edge;

				/* edge found and moved */
				break;
			}
		}
	}
}  /* move_edges_to_leader */

/**
 * Split a partition that has NO followers by a local list.
 *
 * @param Z    partition to split
 * @param g    a (non-empty) node list
 * @param env  the environment
 *
 * @return  a new partition containing the nodes of g
 */
static partition_t *split_no_followers(partition_t *Z, node_t *g, environment_t *env) {
	partition_t *Z_prime;
	node_t      *node;
	unsigned    n = 0;
	int         max_input;

	dump_partition("Splitting ", Z);
	dump_list("by list ", g);

	assert(g != NULL);

	/* Remove g from Z. */
	for (node = g; node != NULL; node = node->next) {
		assert(node->part == Z);
		list_del(&node->node_list);
		++n;
	}
	assert(n < Z->n_leader);
	Z->n_leader -= n;

	/* Move g to a new partition, Z'. */
	Z_prime = new_partition(env);
	max_input = 0;
	for (node = g; node != NULL; node = node->next) {
		list_add_tail(&node->node_list, &Z_prime->Leader);
		node->part = Z_prime;
		if (node->max_user_input > max_input)
			max_input = node->max_user_input;
	}
	Z_prime->max_user_inputs = max_input;
	Z_prime->n_leader        = n;

	check_partition(Z);
	check_partition(Z_prime);

	/* for now, copy the type info tag, it will be adjusted in split_by(). */
	Z_prime->type_is_T_or_C = Z->type_is_T_or_C;

	update_worklist(Z, Z_prime, env);

	dump_partition("Now ", Z);
	dump_partition("Created new ", Z_prime);
	return Z_prime;
}  /* split_no_followers */

/**
 * Make the Follower -> Leader transition for a node.
 *
 * @param n  the node
 */
static void follower_to_leader(node_t *n) {
	assert(n->is_follower == 1);

	DB((dbg, LEVEL_2, "%+F make the follower -> leader transition\n", n->node));
	n->is_follower = 0;
	move_edges_to_leader(n);
	list_del(&n->node_list);
	list_add_tail(&n->node_list, &n->part->Leader);
	++n->part->n_leader;
}  /* follower_to_leader */

/**
 * The environment for one race step.
 */
typedef struct step_env {
	node_t   *initial;    /**< The initial node list. */
	node_t   *unwalked;   /**< The unwalked node list. */
	node_t   *walked;     /**< The walked node list. */
	int      index;       /**< Next index of Follower use_def edge. */
	unsigned side;        /**< side number. */
} step_env;

/**
 * Return non-zero, if a input is a real follower
 *
 * @param irn    the node to check
 * @param input  number of the input
 */
static int is_real_follower(const ir_node *irn, int input) {
	node_t *pred;