X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbeblocksched.c;h=f0896253f6143db2b77845d5305d7647f8639c5a;hb=8d07d17eb2ade0b6b4aef0ebd68d6af3cc368b06;hp=ee4669ac6deb128d25842f0b93d87bbcd2489cc1;hpb=31636543e37dbecfb9b33664a1eb981d01f71ab8;p=libfirm

diff --git a/ir/be/beblocksched.c b/ir/be/beblocksched.c
index ee4669ac6..f0896253f 100644
--- a/ir/be/beblocksched.c
+++ b/ir/be/beblocksched.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.
  *
@@ -23,6 +23,16 @@
  * @author      Matthias Braun, Christoph Mallon
  * @date        27.09.2006
  * @version     $Id$
+ *
+ * The goals of the greedy (and ILP) algorithm here works by assuming that
+ * we want to change as many jumps to fallthroughs as possible (executed jumps
+ * actually, we have to look at the execution frequencies). The algorithms
+ * do this by collecting execution frequencies of all branches (which is easily
+ * possible when all critical edges are split) then removes critical edges where
+ * possible as we don't need and want them anymore now. The algorithms then try
+ * to change as many edges to fallthroughs as possible, this is done by setting
+ * a next and prev pointers on blocks. The greedy algorithm sorts the edges by
+ * execution frequencies and tries to transform them to fallthroughs in this order
  */
 #ifdef HAVE_CONFIG_H
 #include "config.h"
@@ -49,9 +59,8 @@
 #include "bemodule.h"
 #include "be.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"
 
 #ifdef WITH_ILP
 #include <lpp/lpp.h>
@@ -134,12 +143,15 @@ static void collect_egde_frequency(ir_node *block, void *data)
 	entry->prev  = NULL;
 	set_irn_link(block, entry);
 
-	if (block == get_irg_start_block(env->irg))
-		return;
-
 	arity = get_Block_n_cfgpreds(block);
 
-	if (arity == 1) {
+	if (arity == 0) {
+		assert(block == get_irg_start_block(env->irg)
+				|| block == get_irg_end_block(env->irg));
+		/* must be the start block (or end-block for endless loops), nothing to
+		 * do here */
+		return;
+	} else if (arity == 1) {
 		edge.block            = block;
 		edge.pos              = 0;
 		edge.execfreq         = get_block_execfreq(env->execfreqs, block);
@@ -190,18 +202,19 @@ static void coalesce_blocks(blocksched_env_t *env)
 	for (i = 0; i < edge_count; ++i) {
 		const edge_t *edge  = &env->edges[i];
 		ir_node      *block = edge->block;
+		int           pos   = edge->pos;
 		ir_node      *pred_block;
 		blocksched_entry_t *entry, *pred_entry;
 
-		/* the block might have been removed already... */
-		if (is_Bad(get_Block_cfgpred(block, 0)))
-			continue;
-
 		/* only check edge with highest frequency */
 		if (! edge->highest_execfreq)
 			continue;
 
-		pred_block = get_Block_cfgpred_block(block, edge->pos);
+		/* the block might have been removed already... */
+		if (is_Bad(get_Block_cfgpred(block, 0)))
+			continue;
+
+		pred_block = get_Block_cfgpred_block(block, pos);
 		entry      = get_irn_link(block);
 		pred_entry = get_irn_link(pred_block);
 
@@ -223,6 +236,7 @@ static void coalesce_blocks(blocksched_env_t *env)
 	for (i = 0; i < edge_count; ++i) {
 		const edge_t *edge  = &env->edges[i];
 		ir_node      *block = edge->block;
+		int           pos   = edge->pos;
 		ir_node      *pred_block;
 		blocksched_entry_t *entry, *pred_entry;
 
@@ -230,7 +244,11 @@ static void coalesce_blocks(blocksched_env_t *env)
 		if (is_Bad(get_Block_cfgpred(block, 0)))
 			continue;
 
-		pred_block = get_Block_cfgpred_block(block, edge->pos);
+		/* we can't do fallthroughs in backedges */
+		if (is_backedge(block, pos))
+			continue;
+
+		pred_block = get_Block_cfgpred_block(block, pos);
 		entry      = get_irn_link(block);
 		pred_entry = get_irn_link(pred_block);
 
@@ -343,7 +361,7 @@ static blocksched_entry_t *finish_block_schedule(blocksched_env_t *env)
 	ir_node            *startblock = get_irg_start_block(irg);
 	blocksched_entry_t *entry      = get_irn_link(startblock);
 
-	set_using_visited(irg);
+	ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED);
 	inc_irg_visited(irg);
 
 	env->worklist = new_pdeq();
@@ -351,7 +369,7 @@ static blocksched_entry_t *finish_block_schedule(blocksched_env_t *env)
 	assert(pdeq_empty(env->worklist));
 	del_pdeq(env->worklist);
 
-	clear_using_visited(irg);
+	ir_free_resources(irg, IR_RESOURCE_IRN_VISITED);
 
 	return entry;
 }
@@ -694,8 +712,7 @@ static ir_node **create_extbb_block_schedule(ir_graph *irg, ir_exec_freq *execfr
 	list.end    = NULL;
 	list.n_blks = 0;
 
-	set_using_irn_link(irg);
-	set_using_visited(irg);
+	ir_reserve_resources(irg, IR_RESOURCE_IRN_VISITED | IR_RESOURCE_IRN_LINK);
 	inc_irg_block_visited(irg);
 
 	create_block_list(get_irg_start_block(irg), &list);
@@ -708,8 +725,7 @@ static ir_node **create_extbb_block_schedule(ir_graph *irg, ir_exec_freq *execfr
 		blk_list[i] = b;
 	}
 
-	clear_using_irn_link(irg);
-	clear_using_visited(irg);
+	ir_free_resources(irg, IR_RESOURCE_IRN_VISITED | IR_RESOURCE_IRN_LINK);
 
 	return blk_list;
 }