X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbespillslots.c;h=b854d611f15b9413eaa765597f51169696b3f03f;hb=b9d45e08e23bcf058fa8f2d9e18dd78e8cccd044;hp=e4d6e7f23da69a90300eaf3a9204a02f62442d54;hpb=f3b87a11616fafef1001352605c42d61cb4ceca4;p=libfirm

diff --git a/ir/be/bespillslots.c b/ir/be/bespillslots.c
index e4d6e7f23..b854d611f 100644
--- a/ir/be/bespillslots.c
+++ b/ir/be/bespillslots.c
@@ -25,6 +25,8 @@
 #include "bespillslots.h"
 #include "bechordal_t.h"
 #include "bejavacoal.h"
+#include "benodesets.h"
+#include "bestatevent.h"
 
 
 #define DBG_COALESCING		1
@@ -49,6 +51,7 @@ typedef struct _affinity_edge_t {
 
 typedef struct _ss_env_t {
 	struct obstack obst;
+	const arch_env_t *arch_env;
 	const be_chordal_env_t *chordal_env;
 	set *spills;
 	ir_node **reloads;
@@ -58,10 +61,11 @@ typedef struct _ss_env_t {
 
 /** Compare 2 affinity edges (used in quicksort) */
 static int cmp_affinity(const void *d1, const void *d2) {
-	const affinity_edge_t *e1 = d1;
-	const affinity_edge_t *e2 = d2;
+	const affinity_edge_t * const *e1 = d1;
+	const affinity_edge_t * const *e2 = d2;
 
-	return e1->affinity < e2->affinity ? -1 : 1;
+	// sort in descending order
+	return (*e1)->affinity < (*e2)->affinity ? 1 : -1;
 }
 
 static int cmp_spill(const void* d1, const void* d2, size_t size) {
@@ -72,7 +76,7 @@ static int cmp_spill(const void* d1, const void* d2, size_t size) {
 
 static spill_t *get_spill(ss_env_t *env, ir_node *node) {
 	spill_t spill, *res;
-	int hash = HASH_PTR(node);
+	int hash = nodeset_hash(node);
 
 	spill.spill = node;
 	res = set_find(env->spills, &spill, sizeof(spill), hash);
@@ -89,11 +93,33 @@ static spill_t *get_spill(ss_env_t *env, ir_node *node) {
  *                                      |_|
  */
 
-static spill_t *collect_spill(ss_env_t *env, ir_node *node, const arch_register_class_t *cls) {
+static ir_node *get_memory_edge(const ir_node *node) {
+	int i, arity;
+
+	arity = get_irn_arity(node);
+	for(i = arity - 1; i >= 0; --i) {
+		ir_node *arg = get_irn_n(node, i);
+		if(get_irn_mode(arg) == mode_M)
+			return arg;
+	}
+
+	return NULL;
+}
+
+static spill_t *collect_spill(ss_env_t *env, ir_node *node) {
+	const arch_env_t *arch_env = env->arch_env;
+	const arch_register_class_t *cls;
 	spill_t spill, *res;
-	int hash = HASH_PTR(node);
+	int hash = nodeset_hash(node);
 
-	assert(be_is_Spill(node));
+	assert(arch_irn_class_is(arch_env, node, spill));
+
+	if(be_is_Spill(node)) {
+		cls = arch_get_irn_reg_class(arch_env, node, be_pos_Spill_val);
+	} else {
+		// TODO add a way to detect the type of the spilled value
+		assert(0);
+	}
 
 	spill.spill = node;
 	res = set_find(env->spills, &spill, sizeof(spill), hash);
@@ -102,17 +128,15 @@ static spill_t *collect_spill(ss_env_t *env, ir_node *node, const arch_register_
 		spill.spillslot = set_count(env->spills);
 		spill.cls = cls;
 		res = set_insert(env->spills, &spill, sizeof(spill), hash);
-	} else {
-		assert(cls == res->cls);
 	}
 
 	return res;
 }
 
-static spill_t *collect_memphi(ss_env_t *env, ir_node *node, const arch_register_class_t *cls) {
+static spill_t *collect_memphi(ss_env_t *env, ir_node *node) {
 	int i, arity;
 	spill_t spill, *res;
-	int hash = HASH_PTR(node);
+	int hash = nodeset_hash(node);
 
 	assert(is_Phi(node));
 
@@ -123,7 +147,7 @@ static spill_t *collect_memphi(ss_env_t *env, ir_node *node, const arch_register
 	}
 
 	spill.spillslot = set_count(env->spills);
-	spill.cls = cls;
+	spill.cls = NULL;
 	res = set_insert(env->spills, &spill, sizeof(spill), hash);
 
 	// is 1 of the arguments a spill?
@@ -133,11 +157,17 @@ static spill_t *collect_memphi(ss_env_t *env, ir_node *node, const arch_register
 		spill_t* arg_spill;
 
 		if(be_is_Spill(arg)) {
-			arg_spill = collect_spill(env, arg, cls);
+			arg_spill = collect_spill(env, arg);
 		} else {
 			// if it wasn't a spill then it must be a Mem-Phi
 			assert(is_Phi(arg));
-			arg_spill = collect_memphi(env, arg, cls);
+			arg_spill = collect_memphi(env, arg);
+		}
+
+		if(res->cls == NULL) {
+			res->cls = arg_spill->cls;
+		} else {
+			assert(arg_spill->cls == NULL || res->cls == arg_spill->cls);
 		}
 
 		// add an affinity edge
@@ -157,17 +187,25 @@ static spill_t *collect_memphi(ss_env_t *env, ir_node *node, const arch_register
  */
 static void collect_spills_walker(ir_node *node, void *data) {
 	ss_env_t *env = data;
+	const arch_env_t *arch_env = env->arch_env;
+
+	// classify returns classification of the irn the proj is attached to
+	if(is_Proj(node))
+		return;
+
+	if(arch_irn_class_is(arch_env, node, reload)) {
+		ir_node *spillnode = get_memory_edge(node);
+		spill_t *spill;
 
-	if(be_is_Reload(node)) {
-		ir_node *spill = get_irn_n(node, be_pos_Reload_mem);
-		const arch_env_t *arch_env = env->chordal_env->birg->main_env->arch_env;
-		const arch_register_class_t *cls = arch_get_irn_reg_class(arch_env, node, -1);
+		assert(spillnode != NULL);
 
-		if(is_Phi(spill)) {
-			collect_memphi(env, spill, cls);
+		if(is_Phi(spillnode)) {
+			spill = collect_memphi(env, spillnode);
 		} else {
-			collect_spill(env, spill, cls);
+			spill = collect_spill(env, spillnode);
 		}
+
+		assert(!be_is_Reload(node) || spill->cls == arch_get_irn_reg_class(arch_env, node, -1));
 		ARR_APP1(ir_node*, env->reloads, node);
 	}
 }
@@ -382,7 +420,7 @@ static void do_greedy_coalescing(ss_env_t *env)
 		}
 	}
 
-	// assign spillslots
+	// assign spillslots to spills
 	for(i = 0; i < spillcount; ++i) {
 		spill_t *spill = spilllist[i];
 
@@ -489,7 +527,7 @@ static memperm_t *get_memperm(ss_env_t *env, ir_node *block) {
 	int hash;
 
 	entry.block = block;
-	hash = HASH_PTR(block);
+	hash = nodeset_hash(block);
 
 	res = set_find(env->memperms, &entry, sizeof(entry), hash);
 
@@ -506,6 +544,10 @@ static entity* create_stack_entity(ss_env_t *env, spill_slot_t *slot) {
 	ir_type* frame = get_irg_frame_type(env->chordal_env->irg);
 	entity* res = frame_alloc_area(frame, slot->size, slot->align, 0);
 
+	// adjust size of the entity type...
+	ir_type *enttype = get_entity_type(res);
+	set_type_size_bytes(enttype, slot->size);
+
 	slot->entity = res;
 
 	return res;
@@ -546,6 +588,7 @@ static void enlarge_spillslot(spill_slot_t *slot, int otheralign, int othersize)
  * reload nodes.
  */
 static void assign_spillslots(ss_env_t *env) {
+	const arch_env_t *arch_env = env->arch_env;
 	int i;
 	int spillcount;
 	spill_t *spill;
@@ -581,16 +624,16 @@ static void assign_spillslots(ss_env_t *env) {
 			create_stack_entity(env, slot);
 		}
 
-		if(be_is_Spill(node)) {
-			be_set_frame_entity(node, slot->entity);
-		} else {
+		if(is_Phi(node)) {
 			int i, arity;
+			ir_node *block = get_nodes_block(node);
 
 			// should be a PhiM
 			assert(is_Phi(node));
 
 			for(i = 0, arity = get_irn_arity(node); i < arity; ++i) {
 				ir_node *arg = get_irn_n(node, i);
+				ir_node *predblock = get_Block_cfgpred_block(block, i);
 				spill_t *argspill;
 				int argslotid;
 
@@ -606,7 +649,7 @@ static void assign_spillslots(ss_env_t *env) {
 						create_stack_entity(env, argslot);
 					}
 
-					memperm = get_memperm(env, get_nodes_block(arg));
+					memperm = get_memperm(env, predblock);
 
 					entry = obstack_alloc(&env->obst, sizeof(entry[0]));
 					entry->node = node;
@@ -618,18 +661,21 @@ static void assign_spillslots(ss_env_t *env) {
 					memperm->entries = entry;
 				}
 			}
+		} else {
+			assert(arch_irn_class_is(arch_env, node, spill));
+			arch_set_frame_entity(arch_env, node, slot->entity);
 		}
 	}
 
 	for(i = 0; i < ARR_LEN(env->reloads); ++i) {
-		const ir_node* reload = env->reloads[i];
-		ir_node* spillnode = get_irn_n(reload, be_pos_Reload_mem);
+		ir_node* reload = env->reloads[i];
+		ir_node* spillnode = get_memory_edge(reload);
 		spill_t *spill = get_spill(env, spillnode);
 		const spill_slot_t *slot = & spillslots[spill->spillslot];
 
 		assert(slot->entity != NULL);
 
-		be_set_frame_entity(reload, slot->entity);
+		arch_set_frame_entity(arch_env, reload, slot->entity);
 	}
 }
 
@@ -678,7 +724,8 @@ static void create_memperms(ss_env_t *env) {
 
 		// insert node into schedule
 		blockend = get_end_of_block_insertion_point(memperm->block);
-		sched_add_after(blockend, mempermnode);
+		sched_add_before(blockend, mempermnode);
+		be_stat_ev("mem_perm", memperm->entrycount);
 
 		for(entry = memperm->entries, i = 0; entry != NULL; entry = entry->next, ++i) {
 			ir_node *proj;
@@ -688,17 +735,37 @@ static void create_memperms(ss_env_t *env) {
 			be_set_MemPerm_out_entity(mempermnode, i, entry->out);
 			set_irg_current_block(env->chordal_env->irg, memperm->block);
 			proj = new_Proj(mempermnode, get_irn_mode(arg), i);
-			sched_add_after(blockend, proj);
+			sched_add_before(blockend, proj);
 
 			set_irn_n(entry->node, entry->pos, proj);
 		}
 	}
 }
 
-void be_coalesce_spillslots(const be_chordal_env_t *chordal_env) {
+static int count_spillslots(const ss_env_t *env) {
+	const spill_t *spill;
+	int spillcount = set_count(env->spills);
+	bitset_t *counted = bitset_alloca(spillcount);
+	int slotcount;
+
+	slotcount = 0;
+	for(spill = set_first(env->spills); spill != NULL;
+	    spill = set_next(env->spills)) {
+		int spillslot = spill->spillslot;
+		if(!bitset_is_set(counted, spillslot)) {
+			slotcount++;
+			bitset_set(counted, spillslot);
+		}
+	}
+
+	return slotcount;
+}
+
+void be_coalesce_spillslots(const be_chordal_env_t *chordal_env, int coalesce_spillslots) {
 	ss_env_t env;
 
 	obstack_init(&env.obst);
+	env.arch_env = chordal_env->birg->main_env->arch_env;
 	env.chordal_env = chordal_env;
 	env.spills = new_set(cmp_spill, 10);
 	env.reloads = NEW_ARR_F(ir_node*, 0);
@@ -710,7 +777,14 @@ void be_coalesce_spillslots(const be_chordal_env_t *chordal_env) {
 	/* Get initial spill slots */
 	irg_walk_graph(chordal_env->irg, NULL, collect_spills_walker, &env);
 
-	do_greedy_coalescing(&env);
+	be_stat_ev("spillslots", set_count(env.spills));
+
+	if(coalesce_spillslots) {
+		do_greedy_coalescing(&env);
+		if(be_stat_ev_is_active()) {
+			be_stat_ev("spillslots_after_coalescing", count_spillslots(&env));
+		}
+	}
 
 	assign_spillslots(&env);