X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbera.c;h=2178ec7e57d6ba609e581f6a249667f4a9635f7e;hb=b9d45e08e23bcf058fa8f2d9e18dd78e8cccd044;hp=e7ebb3b9265fd49e23ee940b545489c81d5ec6f0;hpb=7d592b466364d846c375a7069537a98c47352702;p=libfirm

diff --git a/ir/be/bera.c b/ir/be/bera.c
index e7ebb3b92..2178ec7e5 100644
--- a/ir/be/bera.c
+++ b/ir/be/bera.c
@@ -14,116 +14,94 @@
 #include "irmode.h"
 #include "irdom.h"
 
-#include "bera_t.h"
+#include "beutil.h"
 #include "besched_t.h"
 #include "belive_t.h"
 
-FIRM_IMPL1(is_allocatable_irn, int, const ir_node *)
-
-size_t ra_irn_data_offset = 0;
-size_t ra_irg_data_offset = 0;
-
-void be_ra_init(void)
+static sched_timestep_t get_time_step(const ir_node *irn)
 {
-	ra_irn_data_offset = register_additional_node_data(sizeof(ra_info_t));
-	ra_irg_data_offset = register_additional_graph_data(sizeof(void *));
+	if(is_Phi(irn))
+		return 0;
+
+	return sched_get_time_step(irn);
 }
 
-static INLINE int values_interfere_dom(const ir_node *a, const ir_node *b)
+int value_dominates(const ir_node *a, const ir_node *b)
 {
-	const ir_node *b1 = get_nodes_block(a);
-	const ir_node *b2 = get_nodes_block(b);
-	int lo_a, lo_b;
-
-	assert(block_dominates(b1, b2));
+	int res = 0;
+	const ir_node *ba = get_block(a);
+	const ir_node *bb = get_block(b);
 
 	/*
-	 * if the two blocks are not equal, a and b can only interfere if a is
-	 * live in at b2.
+	 * a and b are not in the same block,
+	 * so dominance is determined by the dominance of the blocks.
 	 */
-	if(b1 != b2 && !is_live_in(b2, a))
-		return 0;
-
-	lo_a = is_live_end(b2, a);
-	lo_b = is_live_end(b2, b);
+	if(ba != bb) {
+		res = block_dominates(ba, bb);
 
 	/*
-	 * If the two blocks are the same and one value is live out and the
-	 * definition of the other is after the definition ov the live out
-	 * value, they interfere.
+	 * Dominance is determined by the time steps of the schedule.
 	 */
-	if(b1 == b2) {
-		int pos_a = sched_get_time_step(a);
-		int pos_b = sched_get_time_step(b);
-
-		if((pos_a < pos_b && lo_a) || (pos_b < pos_a && lo_b))
-			return 1;
+	} else {
+		sched_timestep_t as = get_time_step(a);
+		sched_timestep_t bs = get_time_step(b);
+		res = as <= bs;
 	}
 
-	/*
-	 * Now it is left to check, if the sequence from the last use of 'b'
-	 * (or the end of the block b2, if b is live out)
-	 * to the def of 'b' contains a use and NOT the def of 'a'. Then they
-	 * also interfere
-	 */
-	{
-		const ir_node *irn;
-
-		/* Initialize the liveness. */
-		int a_live = lo_a;
-		int b_live = lo_b;
-
-		/* Go from the end of block b2 and try to detect the liveness. */
-		sched_foreach_reverse(b2, irn) {
-			int i, n;
-
-			/*
-			 * If the definition of 'a' was found 'a' and 'b' interfere, if
-			 * 'b' is live here.
-			 */
-			if(irn == a)
-				return b_live;
-
-			/* Same goes for 'b'. */
-			if(irn == b)
-				return a_live;
-
-			/* If 'a' is not yet live, search for a use. */
-			if(!a_live) {
-				for(i = 0, n = get_irn_arity(irn); i < n; ++i)
-					if(get_irn_n(irn, i) == a) {
-						a_live = 1;
-						break;
-				}
-			}
-
-			/* Same for 'b' */
-			if(!b_live) {
-				for(i = 0, n = get_irn_arity(irn); i < n; ++i)
-					if(get_irn_n(irn, i) == b) {
-						b_live = 1;
-						break;
-					}
-			}
+	return res;
+}
 
+/**
+ * Check, if two values interfere.
+ * @param a The first value.
+ * @param b The second value.
+ * @return 1, if a and b interfere, 0 if not.
+ */
+int values_interfere(const be_lv_t *lv, const ir_node *a, const ir_node *b)
+{
+	int a2b = value_dominates(a, b);
+	int b2a = value_dominates(b, a);
+
+	/* If there is no dominance relation, they do not interfere. */
+	if((a2b | b2a) > 0) {
+		const ir_edge_t *edge;
+		ir_node *bb;
+
+		/*
+		 * Adjust a and b so, that a dominates b if
+		 * a dominates b or vice versa.
+		 */
+		if(b2a) {
+			const ir_node *t = a;
+			a = b;
+			b = t;
 		}
-	}
-
-	assert(0 && "You may never reach this place");
 
-	/* This is never reached */
-	return 0;
-}
+		bb = get_nodes_block(b);
 
-int values_interfere(const ir_node *a, const ir_node *b)
-{
-	const ir_node *b1 = get_nodes_block(a);
-	const ir_node *b2 = get_nodes_block(b);
+		/*
+		 * If a is live end in b's block it is
+		 * live at b's definition (a dominates b)
+		 */
+		if(be_is_live_end(lv, bb, a))
+			return 1;
 
-	if(block_dominates(b1, b2))
-		return values_interfere_dom(a, b);
-	else if(block_dominates(b2, b1))
-		return values_interfere_dom(b, a);
-	else
-		return 0;
+		/*
+		 * Look at all usages of a.
+		 * If there's one usage of a in the block of b, then
+		 * we check, if this use is dominated by b, if that's true
+		 * a and b interfere. Note that b must strictly dominate the user,
+		 * since if b is the last user of in the block, b and a do not
+		 * interfere.
+		 * Uses of a not in b's block can be disobeyed, because the
+		 * check for a being live at the end of b's block is already
+		 * performed.
+		 */
+		foreach_out_edge(a, edge) {
+			const ir_node *user = get_edge_src_irn(edge);
+			if(get_nodes_block(user) == bb && !is_Phi(user) && b != user && value_dominates(b, user))
+				return 1;
+		}
+  }
+  return 0;
 }