+#include "bemodule.h"
+
+DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
+
+#define LV_STD_SIZE 64
+
+/* if defined, use binary search for already live nodes, else linear */
+#define LV_USE_BINARY_SEARCH
+#undef LV_INTESIVE_CHECKS
+
+void be_live_chk_compare(be_lv_t *lv, lv_chk_t *lvc);
+
+/**
+ * Filter out some nodes for which we never need liveness.
+ *
+ * @param irn the node t check
+ * @return 0 if no liveness info is needed, 1 else
+ */
+static inline int is_liveness_node(const ir_node *irn)
+{
+ switch (get_irn_opcode(irn)) {
+ case iro_Block:
+ case iro_Bad:
+ case iro_End:
+ case iro_Anchor:
+ case iro_NoMem:
+ return 0;
+ default:
+ return 1;
+ }
+}
+
+int (be_lv_next_irn)(const struct _be_lv_t *lv, const ir_node *bl, unsigned flags, int i)
+{
+ return _be_lv_next_irn(lv, bl, flags, i);
+}
+
+const ir_node * (be_lv_get_irn)(const struct _be_lv_t *lv, const ir_node *bl, int i)
+{
+ return _be_lv_get_irn(lv, bl, i);
+}
+
+int (be_is_live_in)(const be_lv_t *lv, const ir_node *block, const ir_node *irn)
+{
+ return _be_is_live_xxx(lv, block, irn, be_lv_state_in);
+}
+
+int (be_is_live_out)(const be_lv_t *lv, const ir_node *block, const ir_node *irn)
+{
+ 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;
+
+ 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 linearly 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;
+ struct _be_lv_info_node_t *res = NULL;
+
+ stat_ev_tim_push();
+ 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 *rec = &irn_live[pos + 1].u.node;
+
+ /* Check, if the irn is in deed in the array. */
+ if(rec->idx == idx)
+ res = rec;
+ }
+ stat_ev_tim_pop("be_lv_get");
+
+ return res;
+}