X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;ds=sidebyside;f=ir%2Fbe%2Fbespillbelady2.c;h=5377e760439a86b56270b80c9dff0d1f9a6e0b02;hb=38249b0311df91904bb3a566a770efe650f40efc;hp=3cb41262a21740eab246cb2cb839cd49ffc3fe2c;hpb=f3282c497ba4a6b4981d828fa19a902adb8fd7bb;p=libfirm

diff --git a/ir/be/bespillbelady2.c b/ir/be/bespillbelady2.c
index 3cb41262a..5377e7604 100644
--- a/ir/be/bespillbelady2.c
+++ b/ir/be/bespillbelady2.c
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 1995-2007 University of Karlsruhe.  All right reserved.
+ * Copyright (C) 1995-2008 University of Karlsruhe.  All right reserved.
  *
  * This file is part of libFirm.
  *
@@ -32,9 +32,7 @@
  *   capacity of the blocks to let global variables live through
  *   them.
  */
-#ifdef HAVE_CONFIG_H
 #include "config.h"
-#endif
 
 #include <math.h>
 #include <limits.h>
@@ -54,7 +52,6 @@
 #include "irprintf.h"
 #include "execfreq.h"
 #include "dfs_t.h"
-#include "xmalloc.h"
 
 #include "beutil.h"
 #include "bearch_t.h"
@@ -69,9 +66,8 @@
 #include "bemodule.h"
 #include "bespill.h"
 
-#include <libcore/lc_opts.h>
-#include <libcore/lc_opts_enum.h>
-#include <libcore/lc_timing.h>
+#include "lc_opts.h"
+#include "lc_opts_enum.h"
 
 #define DBG_SPILL     1
 #define DBG_WSETS     2
@@ -128,15 +124,16 @@ typedef struct _belady_env_t {
 	be_lv_t *lv;
 	ir_exec_freq *ef;
 
-	ir_node **blocks;   /**< Array of all blocks. */
-	int n_blocks;       /**< Number of blocks in the graph. */
-	int n_regs;			/**< number of regs in this reg-class */
-	workset_t *ws;		/**< the main workset used while processing a block. ob-allocated */
-	ir_node *instr;		/**< current instruction */
-	int instr_nr;     	/**< current instruction number (relative to block start) */
+	ir_node **blocks;            /**< Array of all blocks. */
+	int n_blocks;                /**< Number of blocks in the graph. */
+	int n_regs;			         /**< number of regs in this reg-class */
+	workset_t *ws;		         /**< the main workset used while processing a block. ob-allocated */
+	ir_node *instr;		         /**< current instruction */
+	int instr_nr;     	         /**< current instruction number (relative to block start) */
 
-	spill_env_t *senv;	/**< see bespill.h */
-	bitset_t *spilled;  /**< bitset to keep all the irns which have already been spilled. */
+	spill_env_t *senv;	         /**< see bespill.h */
+	bitset_t *spilled;           /**< bitset to keep all the irns which have already been spilled. */
+	ir_nodeset_t *extra_spilled; /** All nodes for which a special spill location has been computed. */
 } belady_env_t;
 
 
@@ -147,7 +144,7 @@ static int loc_compare(const void *a, const void *b)
 	return (p->time > q->time) - (p->time < q->time);
 }
 
-static INLINE void workset_print(const workset_t *w)
+static inline void workset_print(const workset_t *w)
 {
 	int i;
 
@@ -159,7 +156,7 @@ static INLINE void workset_print(const workset_t *w)
 /**
  * Alloc a new workset on obstack @p ob with maximum size @p max
  */
-static INLINE workset_t *new_workset(belady_env_t *env, struct obstack *ob) {
+static inline workset_t *new_workset(belady_env_t *env, struct obstack *ob) {
 	workset_t *res;
 	size_t size = sizeof(*res) + (env->n_regs)*sizeof(res->vals[0]);
 	res = obstack_alloc(ob, size);
@@ -170,7 +167,7 @@ static INLINE workset_t *new_workset(belady_env_t *env, struct obstack *ob) {
 /**
  * Alloc a new instance on obstack and make it equal to @param ws
  */
-static INLINE workset_t *workset_clone(belady_env_t *env, struct obstack *ob, workset_t *ws) {
+static inline workset_t *workset_clone(belady_env_t *env, struct obstack *ob, workset_t *ws) {
 	workset_t *res;
 	size_t size = sizeof(*res) + (env->n_regs)*sizeof(res->vals[0]);
 	res = obstack_alloc(ob, size);
@@ -182,7 +179,7 @@ static INLINE workset_t *workset_clone(belady_env_t *env, struct obstack *ob, wo
  * Do NOT alloc anything. Make @param tgt equal to @param src.
  * returns @param tgt for convenience
  */
-static INLINE workset_t *workset_copy(belady_env_t *env, workset_t *tgt, workset_t *src) {
+static inline workset_t *workset_copy(belady_env_t *env, workset_t *tgt, workset_t *src) {
 	size_t size = sizeof(*src) + (env->n_regs)*sizeof(src->vals[0]);
 	memcpy(tgt, src, size);
 	return tgt;
@@ -193,7 +190,7 @@ static INLINE workset_t *workset_copy(belady_env_t *env, workset_t *tgt, workset
  * @param count locations given at memory @param locs.
  * Set the length of @param ws to count.
  */
-static INLINE void workset_bulk_fill(workset_t *workset, int count, const loc_t *locs) {
+static inline void workset_bulk_fill(workset_t *workset, int count, const loc_t *locs) {
 	workset->len = count;
 	memcpy(&(workset->vals[0]), locs, count * sizeof(locs[0]));
 }
@@ -202,10 +199,10 @@ static INLINE void workset_bulk_fill(workset_t *workset, int count, const loc_t
  * Inserts the value @p val into the workset, iff it is not
  * already contained. The workset must not be full.
  */
-static INLINE void workset_insert(belady_env_t *env, workset_t *ws, ir_node *val) {
+static inline void workset_insert(belady_env_t *env, workset_t *ws, ir_node *val) {
 	int i;
 	/* check for current regclass */
-	if (!arch_irn_consider_in_reg_alloc(env->arch, env->cls, val)) {
+	if (!arch_irn_consider_in_reg_alloc(env->cls, val)) {
 		// DBG((dbg, DBG_WORKSET, "Skipped %+F\n", val));
 		return;
 	}
@@ -223,14 +220,14 @@ static INLINE void workset_insert(belady_env_t *env, workset_t *ws, ir_node *val
 /**
  * Removes all entries from this workset
  */
-static INLINE void workset_clear(workset_t *ws) {
+static inline void workset_clear(workset_t *ws) {
 	ws->len = 0;
 }
 
 /**
  * Removes the value @p val from the workset if present.
  */
-static INLINE void workset_remove(workset_t *ws, ir_node *val) {
+static inline void workset_remove(workset_t *ws, ir_node *val) {
 	int i;
 	for(i=0; i<ws->len; ++i) {
 		if (ws->vals[i].irn == val) {
@@ -240,7 +237,7 @@ static INLINE void workset_remove(workset_t *ws, ir_node *val) {
 	}
 }
 
-static INLINE int workset_get_index(const workset_t *ws, const ir_node *val) {
+static inline int workset_get_index(const workset_t *ws, const ir_node *val) {
 	int i;
 	for(i=0; i<ws->len; ++i) {
 		if (ws->vals[i].irn == val)
@@ -296,7 +293,7 @@ typedef struct _block_info_t {
 
 } block_info_t;
 
-static INLINE void *new_block_info(belady_env_t *bel, int id)
+static inline void *new_block_info(belady_env_t *bel, int id)
 {
 	ir_node      *bl  = bel->blocks[id];
 	block_info_t *res = obstack_alloc(&bel->ob, sizeof(*res));
@@ -307,7 +304,7 @@ static INLINE void *new_block_info(belady_env_t *bel, int id)
 	res->bl  = bl;
 	res->id  = id;
 	res->exec_freq    = get_block_execfreq(bel->ef, bl);
-	res->reload_cost  = bel->arch->isa->reload_cost * res->exec_freq;
+	res->reload_cost  = bel->arch->reload_cost * res->exec_freq;
 	res->free_at_jump = bel->n_regs;
 	INIT_LIST_HEAD(&res->br_head);
 	set_irn_link(bl, res);
@@ -317,7 +314,7 @@ static INLINE void *new_block_info(belady_env_t *bel, int id)
 #define get_block_info(block)        ((block_info_t *)get_irn_link(block))
 #define set_block_info(block, info)  set_irn_link(block, info)
 
-static INLINE ir_node *block_info_get_last_ins(block_info_t *bi)
+static inline ir_node *block_info_get_last_ins(block_info_t *bi)
 {
 	if (!bi->last_ins)
 		bi->last_ins = be_get_end_of_block_insertion_point(bi->bl);
@@ -336,7 +333,7 @@ typedef struct _next_use_t {
 								 or NULL. */
 } next_use_t;
 
-static void *next_use_init(ir_phase *phase, ir_node *irn, void *old)
+static void *next_use_init(ir_phase *phase, const ir_node *irn, void *old)
 {
 	(void) phase;
 	(void) irn;
@@ -379,7 +376,7 @@ static void build_next_uses(block_info_t *bi)
 
 #define get_current_use(bi, irn) 	 phase_get_irn_data(&(bi)->next_uses, (irn))
 
-static INLINE void advance_current_use(block_info_t *bi, const ir_node *irn)
+static inline void advance_current_use(block_info_t *bi, const ir_node *irn)
 {
 	next_use_t *use = get_current_use(bi, irn);
 
@@ -434,7 +431,7 @@ struct _bring_in_t {
 	block_info_t *bi;          /**< The block to which bring in should happen. */
 	int pressure_so_far;       /**< The maximal pressure till the first use of irn in bl. */
 	ir_node *first_use;        /**< The first user of irn in bl. */
-	sched_timestep_t use_step; /**< Schedule sttep of the first use. */
+	sched_timestep_t use_step; /**< Schedule step of the first use. */
 
 	int is_remat : 1;          /**< Is rematerializable. */
 	int sect_pressure;         /**< Offset to maximum pressure in block. */
@@ -443,7 +440,7 @@ struct _bring_in_t {
 	bring_in_t *sect_head;
 };
 
-static INLINE bring_in_t *new_bring_in(block_info_t *bi, ir_node *irn, const next_use_t *use)
+static inline bring_in_t *new_bring_in(block_info_t *bi, ir_node *irn, const next_use_t *use)
 {
 	bring_in_t *br    = obstack_alloc(&bi->bel->ob, sizeof(br[0]));
 
@@ -499,16 +496,16 @@ static int bring_in_cmp(const void *a, const void *b)
 	return (fq > fp) - (fq < fp);
 }
 
-static INLINE unsigned get_curr_distance(block_info_t *bi, const ir_node *irn, int is_usage)
+static inline unsigned get_curr_distance(block_info_t *bi, const ir_node *irn, int is_usage)
 {
 	belady_env_t *env          = bi->bel;
 	sched_timestep_t curr_step = sched_get_time_step(env->instr);
 	next_use_t *use            = get_current_use(bi, irn);
-	int flags                  = arch_irn_get_flags(env->arch, irn);
+	int flags                  = arch_irn_get_flags(irn);
 
 	assert(!(flags & arch_irn_flags_ignore));
 
-	/* We have to keep nonspillable nodes in the workingset */
+	/* We have to keep non-spillable nodes in the working set */
 	if(flags & arch_irn_flags_dont_spill)
 		return 0;
 
@@ -533,7 +530,7 @@ static INLINE unsigned get_curr_distance(block_info_t *bi, const ir_node *irn, i
 	return be_is_live_end(env->lv, bi->bl, irn) ? LIVE_END : DEAD;
 }
 
-static INLINE int is_local_phi(const ir_node *bl, const ir_node *irn)
+static inline int is_local_phi(const ir_node *bl, const ir_node *irn)
 {
 	return is_Phi(irn) && get_nodes_block(irn) == bl;
 }
@@ -546,10 +543,10 @@ static INLINE int is_local_phi(const ir_node *bl, const ir_node *irn)
  * @param irn  The node in question.
  * @return     1, if node is something transported into @p bl, 0 if not.
  * @note       The function will only give correct answers in the case
- *             where @p irn is unsed in the block @p bl which is always
+ *             where @p irn is unused in the block @p bl which is always
  *             the case in our usage scenario.
  */
-static INLINE int is_transport_in(const ir_node *bl, const ir_node *irn)
+static inline int is_transport_in(const ir_node *bl, const ir_node *irn)
 {
 	return get_nodes_block(irn) != bl || is_Phi(irn);
 }
@@ -682,7 +679,7 @@ static void belady(belady_env_t *env, int id) {
 		int i, arity;
 		assert(workset_get_length(env->ws) <= env->n_regs && "Too much values in workset!");
 
-		/* projs are handled with the tuple value.
+		/* Projs are handled with the tuple value.
 		 * Phis are no real instr (see insert_starters())
 		 * instr_nr does not increase */
 		if (is_Proj(irn) || is_Phi(irn))
@@ -722,7 +719,7 @@ static void belady(belady_env_t *env, int id) {
 
 		/* allocate all values _defined_ by this instruction */
 		workset_clear(new_vals);
-		if (get_irn_mode(irn) == mode_T) { /* special handling for tuples and projs */
+		if (get_irn_mode(irn) == mode_T) { /* special handling for Tuples and Projs */
 			const ir_edge_t *edge;
 
 			foreach_out_edge(irn, edge) {
@@ -738,7 +735,7 @@ static void belady(belady_env_t *env, int id) {
 		if (is_op_forking(get_irn_op(env->instr))) {
 			for (i = get_irn_arity(env->instr) - 1; i >= 0; --i) {
 				ir_node *op = get_irn_n(env->instr, i);
-				block_info->free_at_jump -= arch_irn_consider_in_reg_alloc(env->arch, env->cls, op);
+				block_info->free_at_jump -= arch_irn_consider_in_reg_alloc(env->cls, op);
 			}
 		}
 
@@ -818,14 +815,14 @@ typedef struct {
 	irn_action_t  *ia_top;
 } rollback_info_t;
 
-static INLINE block_state_t *get_block_state(global_end_state_t *ges, const block_info_t *bi)
+static inline block_state_t *get_block_state(global_end_state_t *ges, const block_info_t *bi)
 {
 	int id = bi->id;
 	assert(!ver_is_younger(ges->bs_tops_vers[id], ges->version));
 	return ver_is_older(ges->bs_tops_vers[id], ges->version) ? NULL : ges->bs_tops[bi->id];
 }
 
-static INLINE const workset_t *get_end_state(global_end_state_t *ges, block_info_t *bi)
+static inline const workset_t *get_end_state(global_end_state_t *ges, block_info_t *bi)
 {
 	block_state_t *bs = get_block_state(ges, bi);
 	return bs ? bs->end_state : bi->ws_end;
@@ -867,7 +864,7 @@ static irn_action_t *new_irn_action(global_end_state_t *ges, ir_node *irn, const
 	return ia;
 }
 
-static INLINE rollback_info_t trans_begin(global_end_state_t *ges)
+static inline rollback_info_t trans_begin(global_end_state_t *ges)
 {
 	rollback_info_t rb;
 	rb.obst_level = obstack_base(&ges->obst);
@@ -876,7 +873,7 @@ static INLINE rollback_info_t trans_begin(global_end_state_t *ges)
 	return rb;
 }
 
-static INLINE void trans_rollback(global_end_state_t *ges, rollback_info_t *rb)
+static inline void trans_rollback(global_end_state_t *ges, rollback_info_t *rb)
 {
 	block_state_t *bs;
 
@@ -996,7 +993,7 @@ static double can_make_available_at_end(global_end_state_t *ges, ir_node *bl, ir
 
 		/*
 		 * finally there is some room. we can at least reload the value.
-		 * but we will try to let ot live through anyhow.
+		 * but we will try to let or live through anyhow.
 		 */
 		if (slot >= 0) {
 			irn_action_t *vs    = new_irn_action(ges, irn, bi->bl);
@@ -1067,7 +1064,6 @@ static double can_bring_in(global_end_state_t *ges, ir_node *bl, ir_node *irn, d
 
 	if (is_transport_in(bl, irn)) {
 		int i, n           = get_irn_arity(bl);
-		ir_node **nodes    = alloca(get_irn_arity(bl) * sizeof(nodes[0]));
 		rollback_info_t rb = trans_begin(ges);
 
 		glob_costs = 0.0;
@@ -1077,10 +1073,10 @@ static double can_bring_in(global_end_state_t *ges, ir_node *bl, ir_node *irn, d
 			double c;
 
 			/*
-			 * there might by unknwons as operands of phis in that case
+			 * there might by Unknowns as operands of Phis in that case
 			 * we set the costs to zero, since they won't get spilled.
 			 */
-			if (arch_irn_consider_in_reg_alloc(env->arch, env->cls, op))
+			if (arch_irn_consider_in_reg_alloc(env->cls, op))
 				c = can_make_available_at_end(ges, pr, op, limit - glob_costs, level + 1);
 			else
 				c = 0.0;
@@ -1235,7 +1231,7 @@ static void optimize_variable(global_end_state_t *ges, bring_in_t *br)
 	// assert(!is_local_phi(bl, irn) || !bitset_contains_irn(ges->succ_phis, irn));
 
 	/*
-	 * if we cannot bring the value to the use, let's see ifit would be worthwhile
+	 * if we cannot bring the value to the use, let's see if it would be worthwhile
 	 * to bring the value to the beginning of the block to have a better spill
 	 * location.
 	 *
@@ -1272,7 +1268,7 @@ static void optimize_variable(global_end_state_t *ges, bring_in_t *br)
 		 *
 		 * If the second is larger than the first,
 		 * we have to increment the total block pressure and hence
-		 * save the old pressure to restire it in case of failing to
+		 * save the old pressure to restore it in case of failing to
 		 * bring the variable into the block in a register.
 		 */
 		trans = trans_begin(ges);
@@ -1294,7 +1290,7 @@ static void optimize_variable(global_end_state_t *ges, bring_in_t *br)
 		 *
 		 * following actions can be taken:
 		 * a) commit changes
-		 * b) mark phi as succeded if node was phi
+		 * b) mark phi as succeeded if node was phi
 		 * c) insert reload at use location
 		 * d) give a spill location hint
 		 *
@@ -1328,14 +1324,15 @@ static void optimize_variable(global_end_state_t *ges, bring_in_t *br)
 				DBG((dbg, DBG_GLOBAL, "\t-> use blocked. local reload: %+F, try spill at: %+F\n",
 							br->first_use, better_spill_loc));
 				be_add_reload(env->senv, irn, br->first_use, env->cls, 1);
-				be_add_spill(env->senv, irn, sched_next(better_spill_loc));
+				be_add_spill(env->senv, irn, better_spill_loc);
+				ir_nodeset_insert(env->extra_spilled, irn);
 			}
 
 			/*
-			 * go from the last bring in use to the first and add all the variabled
+			 * go from the last bring in use to the first and add all the variables
 			 * which additionally live through the block to their pressure.
 			 * at the point were the actually treated use is, we have to increase
-			 * the pressure by one more as the nrought in value starts to count.
+			 * the pressure by one more as the brought in value starts to count.
 			 * Finally, adjust the front pressure as well.
 			 */
 			pressure_inc = 0;
@@ -1399,8 +1396,10 @@ static bring_in_t **determine_global_order(belady_env_t *env)
 
 static void global_assign(belady_env_t *env)
 {
+	ir_nodeset_iterator_t iter;
 	global_end_state_t ges;
 	bring_in_t **br;
+	ir_node *irn;
 	int i, j;
 
 	/*
@@ -1428,7 +1427,7 @@ static void global_assign(belady_env_t *env)
 			workset_set_version(bi->ws_end, j, ver_youngest);
 	}
 
-	/* determine ordeer and optimize them */
+	/* determine order and optimize them */
 	for (br = determine_global_order(env); *br; ++br)
 		optimize_variable(&ges, *br);
 
@@ -1444,11 +1443,15 @@ static void global_assign(belady_env_t *env)
 			if (!is_Phi(irn))
 				break;
 
-			if (arch_irn_consider_in_reg_alloc(env->arch, env->cls, irn)
+			if (arch_irn_consider_in_reg_alloc(env->cls, irn)
 					&& !bitset_contains_irn(ges.succ_phis, irn))
 				be_spill_phi(env->senv, irn);
 		}
 	}
+
+	/* check dominance for specially spilled nodes. */
+	foreach_ir_nodeset (env->extra_spilled, irn, iter)
+		make_spill_locations_dominate_irn(env->senv, irn);
 }
 
 static void collect_blocks(ir_node *bl, void *data)
@@ -1491,6 +1494,7 @@ void be_spill_belady(be_irg_t *birg, const arch_register_class_t *cls)
 	env.senv       = be_new_spill_env(birg);
 	env.ef         = be_get_birg_exec_freq(birg);
 	env.spilled    = bitset_irg_obstack_alloc(&env.ob, irg);
+	env.extra_spilled = ir_nodeset_new(64);
 	env.n_blocks   = 0;
 
 	irg_block_walk_graph(irg, NULL, collect_blocks, &env);
@@ -1509,11 +1513,21 @@ void be_spill_belady(be_irg_t *birg, const arch_register_class_t *cls)
 
 	global_assign(&env);
 
+	/* check dominance for specially spilled nodes. */
+	{
+		ir_nodeset_iterator_t iter;
+		ir_node *irn;
+
+		foreach_ir_nodeset (env.extra_spilled, irn, iter)
+			make_spill_locations_dominate_irn(env.senv, irn);
+	}
+
 	/* Insert spill/reload nodes into the graph and fix usages */
 	be_insert_spills_reloads(env.senv);
 
 	/* clean up */
 	be_delete_spill_env(env.senv);
+	ir_nodeset_del(env.extra_spilled);
 
 	obstack_free(&env.ob, NULL);
 }