From 45651cea8d93020a7f92855232c6d6b42aeba85d Mon Sep 17 00:00:00 2001
From: Wolfgang Bumiller <wolfgang.linux@bumiller.com>
Date: Tue, 1 May 2012 12:40:37 +0200
Subject: [PATCH] Implementation of liferange overlap test

---
 ir.c | 54 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 ir.h |  2 ++
 2 files changed, 56 insertions(+)

diff --git a/ir.c b/ir.c
index 720efc9..cbfe304 100644
--- a/ir.c
+++ b/ir.c
@@ -558,6 +558,60 @@ bool ir_value_life_merge(ir_value *self, size_t s)
     return ir_value_life_insert(self, i, new_entry);
 }
 
+bool ir_values_overlap(ir_value *a, ir_value *b)
+{
+    /* For any life entry in A see if it overlaps with
+     * any life entry in B.
+     * Note that the life entries are orderes, so we can make a
+     * more efficient algorithm there than naively translating the
+     * statement above.
+     */
+
+    ir_life_entry_t *la, *lb, *enda, *endb;
+
+    /* first of all, if either has no life range, they cannot clash */
+    if (!a->life_count || !b->life_count)
+        return false;
+
+    la = a->life;
+    lb = b->life;
+    enda = la + a->life_count;
+    endb = lb + b->life_count;
+    while (true)
+    {
+        /* check if the entries overlap, for that,
+         * both must start before the other one ends.
+         */
+        if (la->start <= lb->end &&
+            lb->start <= la->end)
+        {
+            return true;
+        }
+
+        /* entries are ordered
+         * one entry is earlier than the other
+         * that earlier entry will be moved forward
+         */
+        if (la->end < lb->end)
+        {
+            /* order: A B, move A forward
+             * check if we hit the end with A
+             */
+            if (++la == enda)
+                break;
+        }
+        else if (lb->end < la->end)
+        {
+            /* order: B A, move B forward
+             * check if we hit the end with B
+             */
+            if (++lb == endb)
+                break;
+        }
+    }
+    return false;
+}
+
 /***********************************************************************
  *IR main operations
  */
diff --git a/ir.h b/ir.h
index 7d77d29..cbddf71 100644
--- a/ir.h
+++ b/ir.h
@@ -83,6 +83,8 @@ MEM_VECTOR_PROTO(ir_value, ir_life_entry_t, life);
 bool ir_value_life_merge(ir_value*, size_t);
 /* check if a value lives at a specific point */
 bool ir_value_lives(ir_value*, size_t);
+/* check if the life-range of 2 values overlaps */
+bool ir_values_overlap(ir_value*, ir_value*);
 
 void ir_value_dump(ir_value*, int (*oprintf)(const char*,...));
 void ir_value_dump_life(ir_value *self, int (*oprintf)(const char*,...));
-- 
2.39.2