+ return _be_is_live_xxx(lv, block, irn, be_lv_state_out);
+}
+
+int (be_is_live_end)(const be_lv_t *lv, const ir_node *block, const ir_node *irn)
+{
+ return _be_is_live_xxx(lv, block, irn, be_lv_state_end);
+}
+
+
+#ifdef LV_USE_BINARY_SEARCH
+static INLINE unsigned _be_liveness_bsearch(struct _be_lv_info_t *arr, unsigned idx)
+{
+ struct _be_lv_info_t *payload = arr + 1;
+
+ unsigned n = arr[0].u.head.n_members;
+ unsigned res = 0;
+ int lo = 0;
+ int hi = n;
+
+ if(n == 0)
+ return 0;
+
+#if 0
+ if(idx < payload[0].u.node.idx)
+ return 0;
+
+ if(idx > payload[n - 1].u.node.idx)
+ return n - 1;
+#endif
+
+ /* start a binary search for the requested node. */
+ while(lo < hi) {
+ int md = lo + ((hi - lo) >> 1);
+ unsigned md_idx = payload[md].u.node.idx;
+
+ if(idx > md_idx)
+ lo = md + 1;
+ else if(idx < md_idx)
+ hi = md;
+ else {
+ res = md;
+ assert(payload[res].u.node.idx == idx);
+ break;
+ }
+
+ res = lo;
+ }
+
+#ifdef LV_INTESIVE_CHECKS
+ {
+ unsigned i;
+ for(i = res; i < n; ++i)
+ assert(payload[i].u.node.idx >= idx);
+
+ for(i = 0; i < res; ++i)
+ assert(payload[i].u.node.idx < idx);
+ }
+#endif
+
+ return res;
+}
+
+#else
+
+/**
+ * This function searches linearily for the node in the array.
+ */
+static INLINE unsigned _be_liveness_bsearch(struct _be_lv_info_t *arr, unsigned idx) {
+ unsigned n = arr[0].u.head.n_members;
+ unsigned i;
+
+ for(i = 0; i < n; ++i) {
+ if(arr[i + 1].u.node.idx == idx)
+ return i;
+ }
+
+ return i;
+}
+#endif
+
+struct _be_lv_info_node_t *be_lv_get(const struct _be_lv_t *li, const ir_node *bl, const ir_node *irn)
+{
+ struct _be_lv_info_t *irn_live = phase_get_irn_data(&li->ph, bl);
+
+ if(irn_live) {
+ unsigned idx = get_irn_idx(irn);
+
+ /* Get the position of the index in the array. */
+ int pos = _be_liveness_bsearch(irn_live, idx);
+
+ /* Get the record in question. 1 must be added, since the first record contains information about the array and must be skipped. */
+ struct _be_lv_info_node_t *res = &irn_live[pos + 1].u.node;
+
+ /* Check, if the irn is in deed in the array. */
+ if(res->idx == idx)
+ return res;
+ }
+
+ return NULL;
+}
+
+static struct _be_lv_info_node_t *be_lv_get_or_set(struct _be_lv_t *li, ir_node *bl, ir_node *irn)
+{
+ struct _be_lv_info_t *irn_live = phase_get_or_set_irn_data(&li->ph, bl);
+
+ unsigned idx = get_irn_idx(irn);
+
+ /* Get the position of the index in the array. */
+ unsigned pos = _be_liveness_bsearch(irn_live, idx);
+
+ /* Get the record in question. 1 must be added, since the first record contains information about the array and must be skipped. */
+ struct _be_lv_info_node_t *res = &irn_live[pos + 1].u.node;
+
+ /* Check, if the irn is in deed in the array. */
+ if(res->idx != idx) {
+ struct _be_lv_info_t *payload;
+ unsigned n_members = irn_live[0].u.head.n_members;
+ unsigned n_size = irn_live[0].u.head.n_size;
+ unsigned i;
+
+ if(n_members == n_size - 1) {
+ unsigned new_size = 2 * n_size * sizeof(irn_live[0]);
+ struct _be_lv_info_t *nw = phase_alloc(&li->ph, new_size);
+ memcpy(nw, irn_live, new_size);
+ nw[0].u.head.n_size = new_size;
+ irn_live = nw;
+ phase_set_irn_data(&li->ph, irn, nw);
+ }
+
+ payload = &irn_live[1];
+ for(i = n_members; i > pos; --i) {
+ payload[i] = payload[i - 1];
+ }
+
+ ++irn_live[0].u.head.n_members;
+
+ res = &payload[pos].u.node;
+ res->idx = idx;
+ res->flags = 0;
+ }
+
+#ifdef LV_INTESIVE_CHECKS
+ {
+ unsigned i;
+ unsigned n = irn_live[0].u.head.n_members;
+ unsigned last = 0;
+ struct _be_lv_info_t *payload = &irn_live[1];
+
+ for(i = 0; i < n; ++i) {
+ assert(payload[i].u.node.idx >= last);
+ last = payload[i].u.node.idx;
+ }
+ }
+#endif
+
+ return res;
+}
+
+/**
+ * Removes a node from the list of live variables of a block.
+ * @return 1 if the node was live at that block, 0 if not.
+ */
+static int be_lv_remove(struct _be_lv_t *li, ir_node *bl, ir_node *irn)
+{
+ struct _be_lv_info_t *irn_live = phase_get_irn_data(&li->ph, bl);
+
+ if(irn_live) {
+ unsigned n = irn_live[0].u.head.n_members;
+ unsigned idx = get_irn_idx(irn);
+ unsigned pos = _be_liveness_bsearch(irn_live, idx);
+ struct _be_lv_info_t *payload = irn_live + 1;
+ struct _be_lv_info_node_t *res = &payload[pos].u.node;
+
+ /* The node is in deed in the block's array. Let's remove it. */
+ if(res->idx == idx) {
+ unsigned i;
+
+ for(i = pos + 1; i < n; ++i)
+ payload[i - 1] = payload[i];
+
+ payload[n - 1].u.node.idx = 0;
+ payload[n - 1].u.node.flags = 0;
+
+ --irn_live[0].u.head.n_members;
+ DBG((li->dbg, LEVEL_3, "\tdeleting %+F from %+F at pos %d\n", irn, bl, pos));
+ return 1;
+ }
+ }
+
+ return 0;
+}
+
+static void register_node(be_lv_t *lv, const ir_node *irn)
+{
+ unsigned idx = get_irn_idx(irn);
+ if(idx >= bitset_size(lv->nodes)) {
+ bitset_t *nw = bitset_malloc(2 * idx);
+ bitset_copy(nw, lv->nodes);
+ bitset_free(lv->nodes);
+ lv->nodes = nw;
+ }
+
+ bitset_set(lv->nodes, idx);
+}
+
+/**
+ * Mark a node as live-in in a block.
+ */
+static INLINE void mark_live_in(be_lv_t *lv, ir_node *block, ir_node *irn)
+{
+ struct _be_lv_info_node_t *n = be_lv_get_or_set(lv, block, irn);
+ DBG((lv->dbg, LEVEL_2, "marking %+F live in at %+F\n", irn, block));
+ n->flags |= be_lv_state_in;
+ register_node(lv, irn);
+}
+
+/**
+ * Mark a node as live-out in a block.
+ */
+static INLINE void mark_live_out(be_lv_t *lv, ir_node *block, ir_node *irn)
+{
+ struct _be_lv_info_node_t *n = be_lv_get_or_set(lv, block, irn);
+ DBG((lv->dbg, LEVEL_2, "marking %+F live out at %+F\n", irn, block));
+ n->flags |= be_lv_state_out | be_lv_state_end;
+ register_node(lv, irn);
+}
+
+/**
+ * Mark a node as live-end in a block.
+ */
+static INLINE void mark_live_end(be_lv_t *lv, ir_node *block, ir_node *irn)
+{
+ struct _be_lv_info_node_t *n = be_lv_get_or_set(lv, block, irn);
+ DBG((lv->dbg, LEVEL_2, "marking %+F live end at %+F\n", irn, block));
+ n->flags |= be_lv_state_end;
+ register_node(lv, irn);