From 6f2933b9dd830b276ddf99bedcef41d7b70b9f42 Mon Sep 17 00:00:00 2001
From: Michael Beck <beck@ipd.info.uni-karlsruhe.de>
Date: Thu, 19 Jun 2008 12:16:38 +0000
Subject: [PATCH] - reduce complexity of remove_End_keepalive() - add a comment
 that set_End_keepalives() may have high complexity costs in Backend

[r20174]
---
 include/libfirm/irnode.h | 10 ++++++++--
 ir/ir/irnode.c           | 43 ++++++++++++++++++++++++++--------------
 2 files changed, 36 insertions(+), 17 deletions(-)

diff --git a/include/libfirm/irnode.h b/include/libfirm/irnode.h
index 662228aa8..0ea6a9f87 100644
--- a/include/libfirm/irnode.h
+++ b/include/libfirm/irnode.h
@@ -427,9 +427,15 @@ ir_node *get_End_keepalive(const ir_node *end, int pos);
 void add_End_keepalive(ir_node *end, ir_node *ka);
 /** Set the Keep alive node at position pos. */
 void set_End_keepalive(ir_node *end, int pos, ir_node *ka);
-/** Set new keep-alives. */
+
+/**
+ * Set new keep-alives.
+ * Beware: This might be an expensive operation if dynamic edges are enabled,
+ * so avoid it in the backend.
+ */
 void set_End_keepalives(ir_node *end, int n, ir_node *in[]);
-/** Set new keep-alives from old keep-alives, skipping irn. */
+
+/** Remove irn from the keep-alive set. */
 void remove_End_keepalive(ir_node *end, ir_node *irn);
 
 /** Some parts of the End node are allocated separately -- their memory
diff --git a/ir/ir/irnode.c b/ir/ir/irnode.c
index 6fa35b1f3..66eb23634 100644
--- a/ir/ir/irnode.c
+++ b/ir/ir/irnode.c
@@ -927,22 +927,35 @@ void set_End_keepalives(ir_node *end, int n, ir_node *in[]) {
 
 /* Set new keep-alives from old keep-alives, skipping irn */
 void remove_End_keepalive(ir_node *end, ir_node *irn) {
-	int     n = get_End_n_keepalives(end);
-	ir_node **in;
-	int     i, idx;
-
-	NEW_ARR_A(ir_node *, in, n);
-
-	for (idx = i = 0; i < n; ++i) {
-		ir_node *old_ka = get_End_keepalive(end, i);
-
-		/* skip irn */
-		if (old_ka != irn)
-			in[idx++] = old_ka;
+	int      n = get_End_n_keepalives(end);
+	int      i, idx;
+	ir_graph *irg;
+
+	idx = -1;
+	for (i = n -1; i >= 0; --i) {
+		ir_node *old_ka = end->in[1 + END_KEEPALIVE_OFFSET + i];
+
+		/* find irn */
+		if (old_ka == irn) {
+			idx = i;
+			goto found;
+		}
 	}
-
-	/* set new keep-alives */
-	set_End_keepalives(end, idx, in);
+	return;
+found:
+	irg = get_irn_irg(end);
+
+	/* remove the edge */
+	edges_notify_edge(end, idx, NULL, irn, irg);
+
+	if (idx != n - 1) {
+		/* exchange with the last one */
+		ir_node *old = end->in[1 + END_KEEPALIVE_OFFSET + n - 1];
+		edges_notify_edge(end, n - 1, NULL, old, irg);
+		end->in[1 + END_KEEPALIVE_OFFSET + idx] = old;
+		edges_notify_edge(end, idx, old, NULL, irg);
+	}
+	ARR_RESIZE(ir_node *, end->in, (n - 1) + 1 + END_KEEPALIVE_OFFSET);
 }
 
 void
-- 
2.20.1