+/**
+ * Creates a new node set.
+ */
+static node_set *new_node_set(void) {
+ return new_pset(identities_cmp, 8);
+}
+
+/**
+ * Deletes a node set.
+ */
+static void del_node_set(node_set *set) {
+ del_pset(set);
+}
+
+/**
+ * Add a node to the set.
+ */
+static ir_node *node_add(node_set *set, ir_node *node) {
+ return identify_remember(set, node);
+}
+
+/**
+ * Remove a node from a node set.
+ */
+static void node_set_remove(node_set *set, ir_node *node) {
+ pset_remove(set, node, ir_node_hash(node));
+}
+
+/**
+ * Return the number of entries in a node set.
+ */
+static int node_set_count(node_set *set) {
+ return pset_count(set);
+}
+
+/** computes dst = dst \/ src for node sets */
+static void node_union(node_set *dst, node_set *src)
+{
+ ir_node *entry;
+ node_set_foreach(entry, src)
+ node_add(dst, entry);
+}
+
+/**
+ * Lookup a node in a node set.
+ */
+static ir_node *node_lookup(node_set *set, ir_node *n)
+{
+ return pset_find(set, n, ir_node_hash(n));
+}
+
+
+/* ---------- Functions for Value sets ---------- */
+
+#define value_set_foreach(v, s) for ((v) = set_first(s); (v); (v) = set_next(s))
+
+/**
+ * calculate a hash value for a value represented by a node
+ */
+static unsigned value_hash(ir_node *value) {
+ return ir_node_hash(value);
+}
+
+/**
+ * Compare two value entries.
+ */
+static int value_cmp(const void *elt, const void *key, size_t size)
+{
+ const value_entry *e1 = elt;
+ const value_entry *e2 = key;
+
+ return identities_cmp(e1->value, e2->value);
+}
+
+/** Create a new value set. */
+static value_set *new_value_set(void) {
+ return new_set(value_cmp, 8);
+}
+
+/** Deletes a value set. */
+static void del_value_set(value_set *set) {
+ del_set(set);
+}
+
+/**
+ * Add a node node representing the value value to the set.
+ */
+static value_entry *value_add(value_set *set, ir_node *node, ir_node *value)
+{
+ value_entry key;
+ key.node = node;
+ key.value = value;
+ return set_insert(set, &key, sizeof(key), value_hash(value));
+}
+
+/** computes dst = dst \/ src for value sets */
+static void value_union(value_set *dst, value_set *src)
+{
+ value_entry *entry;
+ value_set_foreach(entry, src)
+ value_add(dst, entry->node, entry->value);
+}
+
+/** computes dst = dst \/ (value_set)src for value sets */
+static void value_union_nodes(value_set *dst, node_set *src)
+{
+ ir_node *n;
+ node_set_foreach(n, src)
+ value_add(dst, n, n);
+}
+
+/**
+ * Lookup a value in a value set.
+ */
+static ir_node *value_lookup(value_set *value_set, ir_node *n)
+{
+ value_entry key, *e;
+
+ key.value = n;
+ e = set_find(value_set, &key, sizeof(key), value_hash(n));
+ return e ? e->node : NULL;
+}
+
+/**
+ * Add or replace a value in a set by an node computing the same
+ * value in a dominator block.
+ *
+ * @return non-zero if a replacement took place
+ */
+static int value_add_or_replace(value_set *set, ir_node *node, ir_node *value)
+{
+ value_entry *e = value_add(set, node, value);
+
+ if (e->node != node) {
+ /* node must dominate old one here */
+ assert(block_dominates(get_nodes_block(node), get_nodes_block(e->node)));
+
+ e->node = node;
+ return 1;
+ }
+ return 0;
+}