X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fbepeephole.c;h=ae296f48d5ca715ae3a2dad71ecb19e9b2215222;hb=c6571686bfbfb3c87ae24ae1dc568e685d6cd49a;hp=a4d3550b77240651d909c177c4e001c56f064d16;hpb=1ff0c1f0262a9fe76ba513eeae2c5e514e3bcabe;p=libfirm

diff --git a/ir/be/bepeephole.c b/ir/be/bepeephole.c
index a4d3550b7..ae296f48d 100644
--- a/ir/be/bepeephole.c
+++ b/ir/be/bepeephole.c
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 1995-2007 University of Karlsruhe.  All right reserved.
+ * Copyright (C) 1995-2011 University of Karlsruhe.  All right reserved.
  *
  * This file is part of libFirm.
  *
@@ -21,86 +21,79 @@
  * @file
  * @brief       Peephole optimisation framework keeps track of which registers contain which values
  * @author      Matthias Braun
- * @version     $Id$
  */
-#ifdef HAVE_CONFIG_H
 #include "config.h"
-#endif
 
+#include "array_t.h"
 #include "bepeephole.h"
 
 #include "iredges_t.h"
 #include "irgwalk.h"
 #include "irprintf.h"
+#include "ircons.h"
+#include "irgmod.h"
+#include "heights.h"
 #include "error.h"
 
-#include "beirg_t.h"
+#include "beirg.h"
 #include "belive_t.h"
-#include "bearch_t.h"
-#include "besched_t.h"
+#include "bearch.h"
+#include "beintlive_t.h"
+#include "benode.h"
+#include "besched.h"
+#include "bemodule.h"
+
+DEBUG_ONLY(static firm_dbg_module_t *dbg = NULL;)
 
 static const arch_env_t *arch_env;
 static be_lv_t          *lv;
 static ir_node          *current_node;
-ir_node               ***register_values;
+ir_node                **register_values;
 
 static void clear_reg_value(ir_node *node)
 {
-	const arch_register_t       *reg;
-	const arch_register_class_t *cls;
-	unsigned                     reg_idx;
-	unsigned                     cls_idx;
+	const arch_register_t *reg;
+	unsigned               reg_idx;
 
-	if(!mode_is_data(get_irn_mode(node)))
+	if (!mode_is_data(get_irn_mode(node)))
 		return;
 
-	reg     = arch_get_irn_register(arch_env, node);
-	if(reg == NULL) {
-		panic("No register assigned at %+F\n", node);
+	reg = arch_get_irn_register(node);
+	if (reg == NULL) {
+		panic("No register assigned at %+F", node);
 	}
-	if(arch_register_type_is(reg, virtual))
+	if (reg->type & arch_register_type_virtual)
 		return;
-	cls     = arch_register_get_class(reg);
-	reg_idx = arch_register_get_index(reg);
-	cls_idx = arch_register_class_index(cls);
+	reg_idx = reg->global_index;
 
-	//assert(register_values[cls_idx][reg_idx] != NULL);
-	register_values[cls_idx][reg_idx] = NULL;
+	DB((dbg, LEVEL_1, "Clear Register %s\n", reg->name));
+	register_values[reg_idx] = NULL;
 }
 
 static void set_reg_value(ir_node *node)
 {
-	const arch_register_t       *reg;
-	const arch_register_class_t *cls;
-	unsigned                     reg_idx;
-	unsigned                     cls_idx;
+	const arch_register_t *reg;
+	unsigned               reg_idx;
 
-	if(!mode_is_data(get_irn_mode(node)))
+	if (!mode_is_data(get_irn_mode(node)))
 		return;
 
-	reg = arch_get_irn_register(arch_env, node);
-	if(reg == NULL) {
-		panic("No register assigned at %+F\n", node);
+	reg = arch_get_irn_register(node);
+	if (reg == NULL) {
+		panic("No register assigned at %+F", node);
 	}
-	if(arch_register_type_is(reg, virtual))
+	if (reg->type & arch_register_type_virtual)
 		return;
-	cls     = arch_register_get_class(reg);
-	reg_idx = arch_register_get_index(reg);
-	cls_idx = arch_register_class_index(cls);
-
-#ifdef DEBUG_libfirm
-	{
-		ir_node *old_value = register_values[cls_idx][reg_idx];
-		assert(old_value == NULL || old_value == node);
-	}
-#endif
-	register_values[cls_idx][reg_idx] = node;
+	reg_idx = reg->global_index;
+
+	DB((dbg, LEVEL_1, "Set Register %s: %+F\n", reg->name, node));
+	register_values[reg_idx] = node;
 }
 
 static void clear_defs(ir_node *node)
 {
 	/* clear values defined */
-	if(get_irn_mode(node) == mode_T) {
+	if (get_irn_mode(node) == mode_T) {
 		const ir_edge_t *edge;
 		foreach_out_edge(node, edge) {
 			ir_node *proj = get_edge_src_irn(edge);
@@ -117,119 +110,239 @@ static void set_uses(ir_node *node)
 
 	/* set values used */
 	arity = get_irn_arity(node);
-	for(i = 0; i < arity; ++i) {
+	for (i = 0; i < arity; ++i) {
 		ir_node *in = get_irn_n(node, i);
 		set_reg_value(in);
 	}
 }
 
-void be_peephole_node_replaced(const ir_node *old_node, ir_node *new_node)
+void be_peephole_new_node(ir_node * nw)
 {
-	const arch_register_t       *reg;
-	const arch_register_class_t *cls;
-	unsigned                     reg_idx;
-	unsigned                     cls_idx;
+	be_liveness_introduce(lv, nw);
+}
 
-	be_liveness_remove(lv, old_node);
-	be_liveness_introduce(lv, new_node);
+/**
+ * must be called from peephole optimisations before a node will be killed
+ * and its users will be redirected to new_node.
+ * so bepeephole can update its internal state.
+ *
+ * Note: killing a node and rewiring is only allowed if new_node produces
+ * the same registers as old_node.
+ */
+static void be_peephole_before_exchange(const ir_node *old_node,
+                                        ir_node *new_node)
+{
+	const arch_register_t *reg;
+	unsigned               reg_idx;
+	bool                   old_is_current = false;
+
+	DB((dbg, LEVEL_1, "About to exchange and kill %+F with %+F\n", old_node, new_node));
+
+	assert(sched_is_scheduled(skip_Proj_const(old_node)));
+	assert(sched_is_scheduled(skip_Proj(new_node)));
 
-	if(old_node == current_node)
-		current_node = new_node;
+	if (current_node == old_node) {
+		old_is_current = true;
 
-	if(!mode_is_data(get_irn_mode(old_node)))
+		/* next node to be processed will be killed. Its scheduling predecessor
+		 * must be processed next. */
+		current_node = sched_next(current_node);
+		assert (!is_Bad(current_node));
+
+		/* we can't handle liveness updates correctly when exchange current node
+		 * with something behind it */
+		assert(value_dominates(skip_Proj(new_node), skip_Proj_const(old_node)));
+	}
+
+	if (!mode_is_data(get_irn_mode(old_node)))
 		return;
 
-	reg = arch_get_irn_register(arch_env, old_node);
-	if(reg == NULL) {
-		panic("No register assigned at %+F\n", old_node);
+	reg = arch_get_irn_register(old_node);
+	if (reg == NULL) {
+		panic("No register assigned at %+F", old_node);
 	}
-	cls     = arch_register_get_class(reg);
-	reg_idx = arch_register_get_index(reg);
-	cls_idx = arch_register_class_index(cls);
+	assert(reg == arch_get_irn_register(new_node) &&
+	      "KILLING a node and replacing by different register is not allowed");
 
-	if(register_values[cls_idx][reg_idx] == old_node) {
-		register_values[cls_idx][reg_idx] = new_node;
+	reg_idx = reg->global_index;
+	if (register_values[reg_idx] == old_node || old_is_current) {
+		register_values[reg_idx] = new_node;
 	}
+
+	be_liveness_remove(lv, old_node);
 }
 
+void be_peephole_exchange(ir_node *old, ir_node *nw)
+{
+	be_peephole_before_exchange(old, nw);
+	sched_remove(old);
+	exchange(old, nw);
+	be_peephole_new_node(nw);
+}
+
+/**
+ * block-walker: run peephole optimization on the given block.
+ */
 static void process_block(ir_node *block, void *data)
 {
-	arch_isa_t *isa = arch_env->isa;
-	unsigned n_classes;
-	unsigned i;
 	int l;
 	(void) data;
 
 	/* construct initial register assignment */
-	n_classes = arch_isa_get_n_reg_class(isa);
-	for(i = 0; i < n_classes; ++i) {
-		const arch_register_class_t *cls    = arch_isa_get_reg_class(isa, i);
-		unsigned                     n_regs = arch_register_class_n_regs(cls);
-		memset(register_values[i], 0, sizeof(ir_node*) * n_regs);
-	}
+	memset(register_values, 0, sizeof(ir_node*) * arch_env->n_registers);
 
-	assert(lv->nodes && "live sets must be computed");
+	assert(lv->sets_valid && "live sets must be computed");
+	DB((dbg, LEVEL_1, "\nProcessing block %+F (from end)\n", block));
 	be_lv_foreach(lv, block, be_lv_state_end, l) {
 		ir_node *node = be_lv_get_irn(lv, block, l);
 		set_reg_value(node);
 	}
+	DB((dbg, LEVEL_1, "\nstart processing\n"));
 
 	/* walk the block from last insn to the first */
 	current_node = sched_last(block);
-	for( ; !sched_is_begin(current_node);
+	for ( ; !sched_is_begin(current_node);
 			current_node = sched_prev(current_node)) {
 		ir_op             *op;
-		ir_node           *last;
-		peephole_opt_func  func;
+		peephole_opt_func  peephole_node;
 
-		if(is_Phi(current_node))
+		assert(!is_Bad(current_node));
+		if (is_Phi(current_node))
 			break;
 
 		clear_defs(current_node);
 		set_uses(current_node);
 
-		op   = get_irn_op(current_node);
-		func = (peephole_opt_func) op->ops.generic;
-		if(func == NULL)
+		op            = get_irn_op(current_node);
+		peephole_node = (peephole_opt_func)op->ops.generic;
+		if (peephole_node == NULL)
 			continue;
 
-		last = current_node;
-		func(current_node);
-		/* was the current node replaced? */
-		if(current_node != last) {
-			set_uses(current_node);
+		DB((dbg, LEVEL_2, "optimize %+F\n", current_node));
+		peephole_node(current_node);
+		assert(!is_Bad(current_node));
+	}
+}
+
+/**
+ * Check whether the node has only one user.  Explicitly ignore the anchor.
+ */
+bool be_has_only_one_user(ir_node *node)
+{
+	int              n = get_irn_n_edges(node);
+	int              n_users;
+	const ir_edge_t *edge;
+
+	if (n <= 1)
+		return 1;
+
+	n_users = 0;
+	foreach_out_edge(node, edge) {
+		ir_node *src = get_edge_src_irn(edge);
+		/* ignore anchor and keep-alive edges */
+		if (is_Anchor(src) || is_End(src))
+			continue;
+		n_users++;
+	}
+
+	return n_users == 1;
+}
+
+bool be_can_move_before(ir_heights_t *heights, const ir_node *node,
+                        const ir_node *before)
+{
+	int      node_arity = get_irn_arity(node);
+	ir_node *schedpoint = sched_next(node);
+
+	while (schedpoint != before) {
+		int      i;
+		unsigned n_outs = arch_get_irn_n_outs(schedpoint);
+
+		/* the node must not use our computed values */
+		if (heights_reachable_in_block(heights, schedpoint, node))
+			return false;
+
+		/* the node must not overwrite registers of our inputs */
+		for (i = 0; i < node_arity; ++i) {
+			ir_node                   *in  = get_irn_n(node, i);
+			const arch_register_t     *reg = arch_get_irn_register(in);
+			const arch_register_req_t *in_req
+				= arch_get_irn_register_req_in(node, i);
+			unsigned                   o;
+			if (reg == NULL)
+				continue;
+			for (o = 0; o < n_outs; ++o) {
+				const arch_register_t *outreg
+					= arch_get_irn_register_out(schedpoint, o);
+				const arch_register_req_t *outreq
+					= arch_get_irn_register_req_out(schedpoint, o);
+				if (outreg == NULL)
+					continue;
+				if (outreg->global_index >= reg->global_index
+					&& outreg->global_index
+					   < (unsigned)reg->global_index + in_req->width)
+					return false;
+				if (reg->global_index >= outreg->global_index
+					&& reg->global_index
+					   < (unsigned)outreg->global_index + outreq->width)
+					return false;
+			}
 		}
+
+		schedpoint = sched_next(schedpoint);
 	}
+	return true;
 }
 
-void be_peephole_opt(be_irg_t *birg)
+/*
+ * Tries to optimize a beIncSP node with its previous IncSP node.
+ * Must be run from a be_peephole_opt() context.
+ */
+ir_node *be_peephole_IncSP_IncSP(ir_node *node)
 {
-	arch_isa_t *isa;
-	ir_graph   *irg = be_get_birg_irg(birg);
-	unsigned n_classes;
-	unsigned i;
+	int      pred_offs;
+	int      curr_offs;
+	int      offs;
+	ir_node *pred = be_get_IncSP_pred(node);
 
+	if (!be_is_IncSP(pred))
+		return node;
+
+	if (!be_has_only_one_user(pred))
+		return node;
+
+	pred_offs = be_get_IncSP_offset(pred);
+	curr_offs = be_get_IncSP_offset(node);
+	offs = curr_offs + pred_offs;
+
+	/* add node offset to pred and remove our IncSP */
+	be_set_IncSP_offset(pred, offs);
+
+	be_peephole_exchange(node, pred);
+	return pred;
+}
+
+void be_peephole_opt(ir_graph *irg)
+{
+#if 0
 	/* we sometimes find BadE nodes in float apps like optest_float.c or
 	 * kahansum.c for example... */
-	be_liveness_invalidate(birg->lv);
-	be_liveness_assure_sets(be_assure_liveness(birg));
-
-	arch_env = be_get_birg_arch_env(birg);
-	lv       = be_get_birg_liveness(birg);
-	isa      = arch_env->isa;
-
-	n_classes = arch_isa_get_n_reg_class(isa);
-	register_values = alloca(sizeof(register_values[0]) * n_classes);
-	for(i = 0; i < n_classes; ++i) {
-		const arch_register_class_t *cls    = arch_isa_get_reg_class(isa, i);
-		unsigned                     n_regs = arch_register_class_n_regs(cls);
-		register_values[i] = alloca(sizeof(ir_node*) * n_regs);
-	}
+	be_invalidate_live_sets(irg);
+#endif
+	be_assure_live_sets(irg);
+
+	arch_env = be_get_irg_arch_env(irg);
+	lv       = be_get_irg_liveness(irg);
+
+	register_values = XMALLOCN(ir_node*, arch_env->n_registers);
 
 	irg_block_walk_graph(irg, process_block, NULL, NULL);
+
+	xfree(register_values);
 }
 
-void be_peephole_init(void)
+BE_REGISTER_MODULE_CONSTRUCTOR(be_init_peephole)
+void be_init_peephole(void)
 {
-	clear_irp_opcodes_generic_func();
+	FIRM_DBG_REGISTER(dbg, "firm.be.peephole");
 }