X-Git-Url: http://nsz.repo.hu/git/?a=blobdiff_plain;f=ir%2Fbe%2Fia32%2Fia32_optimize.c;h=df2c3082b1dcf35863ff7c1b7308a180d1fdb124;hb=eee248543bd61ec5c3f6aaaa23b9b0cff042fb71;hp=1e3649def6be4115a405acc2947775fcc07bcd63;hpb=259349e35f3e732c703fc3817deacc58d71ffe8c;p=libfirm

diff --git a/ir/be/ia32/ia32_optimize.c b/ir/be/ia32/ia32_optimize.c
index 1e3649def..df2c3082b 100644
--- a/ir/be/ia32/ia32_optimize.c
+++ b/ir/be/ia32/ia32_optimize.c
@@ -1,3 +1,13 @@
+/**
+ * Project:     libFIRM
+ * File name:   ir/be/ia32/ia32_optimize.c
+ * Purpose:     Implements several optimizations for IA32
+ * Author:      Christian Wuerdig
+ * CVS-ID:      $Id$
+ * Copyright:   (c) 2006 Universität Karlsruhe
+ * Licence:     This file protected by GPL -  GNU GENERAL PUBLIC LICENSE.
+ */
+
 #ifdef HAVE_CONFIG_H
 #include "config.h"
 #endif
@@ -9,6 +19,9 @@
 #include "iredges.h"
 #include "tv.h"
 #include "irgmod.h"
+#include "irgwalk.h"
+#include "height.h"
+#include "irbitset.h"
 
 #include "../be_t.h"
 #include "../beabi.h"
@@ -20,11 +33,20 @@
 #include "gen_ia32_regalloc_if.h"     /* the generated interface (register type and class defenitions) */
 #include "ia32_transform.h"
 #include "ia32_dbg_stat.h"
+#include "ia32_util.h"
+
+typedef enum {
+	IA32_AM_CAND_NONE  = 0,
+	IA32_AM_CAND_LEFT  = 1,
+	IA32_AM_CAND_RIGHT = 2,
+	IA32_AM_CAND_BOTH  = 3
+} ia32_am_cand_t;
 
 #undef is_NoMem
 #define is_NoMem(irn) (get_irn_op(irn) == op_NoMem)
 
 typedef int is_op_func_t(const ir_node *n);
+typedef ir_node *load_func_t(dbg_info *db, ir_graph *irg, ir_node *block, ir_node *base, ir_node *index, ir_node *mem);
 
 /**
  * checks if a node represents the NOREG value
@@ -65,8 +87,6 @@ static ident *unique_id(const char *tag)
 	return new_id_from_str(str);
 }
 
-
-
 /**
  * Transforms a SymConst.
  *
@@ -77,22 +97,24 @@ static ident *unique_id(const char *tag)
  * @return the created ia32 Const node
  */
 static ir_node *gen_SymConst(ia32_transform_env_t *env) {
-	ir_node  *cnst;
 	dbg_info *dbg   = env->dbg;
 	ir_mode  *mode  = env->mode;
 	ir_graph *irg   = env->irg;
 	ir_node  *block = env->block;
+	ir_node  *cnst;
 
 	if (mode_is_float(mode)) {
+		FP_USED(env->cg);
 		if (USE_SSE2(env->cg))
-			cnst = new_rd_ia32_fConst(dbg, irg, block, mode);
+			cnst = new_rd_ia32_xConst(dbg, irg, block, get_irg_no_mem(irg), mode);
 		else
-			cnst = new_rd_ia32_vfConst(dbg, irg, block, mode);
-	}
-	else {
-		cnst = new_rd_ia32_Const(dbg, irg, block, mode);
+			cnst = new_rd_ia32_vfConst(dbg, irg, block, get_irg_no_mem(irg), mode);
 	}
+	else
+		cnst = new_rd_ia32_Const(dbg, irg, block, get_irg_no_mem(irg), mode);
+
 	set_ia32_Const_attr(cnst, env->irn);
+
 	return cnst;
 }
 
@@ -131,7 +153,7 @@ static entity *get_entity_for_tv(ia32_code_gen_t *cg, ir_node *cnst)
 		if (tp == firm_unknown_type)
 			tp = get_prim_type(cg->isa->types, mode);
 
-		res = new_entity(get_glob_type(), unique_id("ia32FloatCnst_%u"), tp);
+		res = new_entity(get_glob_type(), unique_id(".LC%u"), tp);
 
 		set_entity_ld_ident(res, get_entity_ident(res));
 		set_entity_visibility(res, visibility_local);
@@ -162,7 +184,7 @@ static entity *get_entity_for_tv(ia32_code_gen_t *cg, ir_node *cnst)
  * @return the created ia32 Const node
  */
 static ir_node *gen_Const(ia32_transform_env_t *env) {
-	ir_node *cnst;
+	ir_node *cnst, *load;
 	symconst_symbol sym;
 	ir_graph *irg   = env->irg;
 	ir_node  *block = env->block;
@@ -182,87 +204,109 @@ static ir_node *gen_Const(ia32_transform_env_t *env) {
 		}
 		sym.entity_p = get_entity_for_tv(env->cg, node);
 
-		cnst = new_rd_SymConst(dbg, irg, block, sym, symconst_addr_ent);
-		env->irn = cnst;
-		cnst = gen_SymConst(env);
+
+		cnst      = new_rd_SymConst(dbg, irg, block, sym, symconst_addr_ent);
+		load      = new_r_Load(irg, block, get_irg_no_mem(irg), cnst, mode);
+		load      = new_r_Proj(irg, block, load, mode, pn_Load_res);
+		env->irn  = cnst;
+		env->mode = mode_P;
+		cnst      = gen_SymConst(env);
+		set_Load_ptr(get_Proj_pred(load), cnst);
+		cnst      = load;
 	}
 	else {
-		cnst = new_rd_ia32_Const(dbg, irg, block, get_irn_mode(node));
+		cnst = new_rd_ia32_Const(dbg, irg, block, get_irg_no_mem(irg), get_irn_mode(node));
 		set_ia32_Const_attr(cnst, node);
 	}
 	return cnst;
 }
 
-
-
 /**
  * Transforms (all) Const's into ia32_Const and places them in the
  * block where they are used (or in the cfg-pred Block in case of Phi's).
  * Additionally all reference nodes are changed into mode_Is nodes.
+ * NOTE: irn must be a firm constant!
  */
-void ia32_place_consts_set_modes(ir_node *irn, void *env) {
-	ia32_code_gen_t      *cg = env;
-	ia32_transform_env_t  tenv;
-	ir_mode              *mode;
-	ir_node              *pred, *cnst;
-	int                   i;
-	opcode                opc;
+static void ia32_transform_const(ir_node *irn, void *env) {
+	ia32_code_gen_t      *cg   = env;
+	ir_node              *cnst = NULL;
+	ia32_transform_env_t tenv;
+
+	tenv.cg   = cg;
+	tenv.irg  = cg->irg;
+	tenv.mode = get_irn_mode(irn);
+	tenv.dbg  = get_irn_dbg_info(irn);
+	tenv.irn  = irn;
+	DEBUG_ONLY(tenv.mod = cg->mod;)
+
+	/* place const either in the smallest dominator of all its users or the original block */
+	if (cg->opt & IA32_OPT_PLACECNST)
+		tenv.block = node_users_smallest_common_dominator(irn, 1);
+	else
+		tenv.block = get_nodes_block(irn);
 
-	if (is_Block(irn))
-		return;
+	switch (get_irn_opcode(irn)) {
+		case iro_Const:
+			cnst = gen_Const(&tenv);
+			break;
+		case iro_SymConst:
+			cnst = gen_SymConst(&tenv);
+			break;
+		default:
+			assert(0 && "Wrong usage of ia32_transform_const!");
+	}
 
-	mode = get_irn_mode(irn);
+	assert(cnst && "Could not create ia32 Const");
 
-	/* transform all reference nodes into mode_Is nodes */
-	if (mode_is_reference(mode)) {
-		mode = mode_Is;
-		set_irn_mode(irn, mode);
-	}
+	/* set the new ia32 const */
+	exchange(irn, cnst);
+}
 
-	tenv.block    = get_nodes_block(irn);
-	tenv.cg       = cg;
-	tenv.irg      = cg->irg;
-	DEBUG_ONLY(tenv.mod      = cg->mod;)
-
-	/* Loop over all predecessors and check for Sym/Const nodes */
-	for (i = get_irn_arity(irn) - 1; i >= 0; --i) {
-		pred      = get_irn_n(irn, i);
-		cnst      = NULL;
-		opc       = get_irn_opcode(pred);
-		tenv.irn  = pred;
-		tenv.mode = get_irn_mode(pred);
-		tenv.dbg  = get_irn_dbg_info(pred);
-
-		/* If it's a Phi, then we need to create the */
-		/* new Const in it's predecessor block       */
-		if (is_Phi(irn)) {
-			tenv.block = get_Block_cfgpred_block(get_nodes_block(irn), i);
-		}
+/**
+ * Transform all firm consts and assure, we visit each const only once.
+ */
+static void ia32_place_consts_walker(ir_node *irn, void *env) {
+	ia32_code_gen_t *cg = env;
 
-		/* put the const into the block where the original const was */
-		if (! cg->opt.placecnst) {
-			tenv.block = get_nodes_block(pred);
-		}
+	if(!is_Const(irn) && !is_SymConst(irn))
+		return;
 
-		switch (opc) {
-			case iro_Const:
-				cnst = gen_Const(&tenv);
-				break;
-			case iro_SymConst:
-				cnst = gen_SymConst(&tenv);
-				break;
-			default:
-				break;
-		}
+	ia32_transform_const(irn, cg);
+}
 
-		/* if we found a const, then set it */
-		if (cnst) {
-			set_irn_n(irn, i, cnst);
-		}
+/**
+ * Replace reference modes with mode_Iu and preserve store value modes.
+ */
+static void ia32_set_modes(ir_node *irn, void *env) {
+	if (is_Block(irn))
+		return;
+
+	/* transform all reference nodes into mode_Iu nodes */
+	if (mode_is_reference(get_irn_mode(irn))) {
+		set_irn_mode(irn, mode_Iu);
 	}
 }
 
+/**
+ * Walks over the graph, transforms all firm consts into ia32 consts
+ * and places them into the "best" block.
+ * @param cg  The ia32 codegenerator object
+ */
+static void ia32_transform_all_firm_consts(ia32_code_gen_t *cg) {
+	irg_walk_graph(cg->irg, NULL, ia32_place_consts_walker, cg);
+}
 
+/* Place all consts and change pointer arithmetics into unsigned integer arithmetics. */
+void ia32_pre_transform_phase(ia32_code_gen_t *cg) {
+	/*
+		We need to transform the consts twice:
+		- the psi condition tree transformer needs existing constants to be ia32 constants
+		- the psi condition tree transformer inserts new firm constants which need to be transformed
+	*/
+	ia32_transform_all_firm_consts(cg);
+	irg_walk_graph(cg->irg, ia32_set_modes, ia32_transform_psi_cond_tree, cg);
+	ia32_transform_all_firm_consts(cg);
+}
 
 /********************************************************************************************************
  *  _____                _           _         ____        _   _           _          _   _
@@ -371,7 +415,7 @@ static int is_CondJmp_replacement(ir_node *cand, ir_node *irn) {
 	int same_args = 1;
 
 	for (i = 0; i < n; i++) {
-		if (get_irn_n(cand, i) == get_irn_n(irn, i)) {
+		if (get_irn_n(cand, i) != get_irn_n(irn, i)) {
 			same_args = 0;
 			break;
 		}
@@ -395,8 +439,9 @@ static void ia32_optimize_CondJmp(ir_node *irn, ia32_code_gen_t *cg) {
 
 	if (replace) {
 		DBG((cg->mod, LEVEL_1, "replacing %+F by ", irn));
+		DBG_OPT_CJMP(irn);
 
-		set_irn_op(irn, op_ia32_CJmp);
+		set_irn_op(irn, op_ia32_CJmpAM);
 
 		DB((cg->mod, LEVEL_1, "%+F\n", irn));
 	}
@@ -406,38 +451,62 @@ static void ia32_optimize_CondJmp(ir_node *irn, ia32_code_gen_t *cg) {
  * Creates a Push from Store(IncSP(gp_reg_size))
  */
 static void ia32_create_Push(ir_node *irn, ia32_code_gen_t *cg) {
-	ir_node *sp  = get_irn_n(irn, 0);
-	ir_node *val, *next, *push, *bl, *proj_M, *proj_res, *old_proj_M;
+	ir_node  *sp  = get_irn_n(irn, 0);
+	ir_graph *irg = cg->irg;
+	ir_node *val, *next, *push, *bl, *proj_M, *proj_res, *old_proj_M, *mem;
 	const ir_edge_t *edge;
+	heights_t *h;
 
-	if (get_ia32_am_offs(irn) || !be_is_IncSP(sp))
+	/* do not create push if store has already an offset assigned or base is not a IncSP */
+	if (get_ia32_am_offs(irn) || ! be_is_IncSP(sp))
 		return;
 
+	/* do not create push if index is not NOREG */
 	if (arch_get_irn_register(cg->arch_env, get_irn_n(irn, 1)) !=
 		&ia32_gp_regs[REG_GP_NOREG])
 		return;
 
+	/* do not create push for floating point */
 	val = get_irn_n(irn, 2);
 	if (mode_is_float(get_irn_mode(val)))
 		return;
 
-	if (be_get_IncSP_direction(sp) != be_stack_dir_expand ||
-		be_get_IncSP_offset(sp) != get_mode_size_bytes(ia32_reg_classes[CLASS_ia32_gp].mode))
+	/* do not create push if IncSp doesn't expand stack or expand size is different from register size */
+	if (be_get_IncSP_offset(sp) != get_mode_size_bytes(ia32_reg_classes[CLASS_ia32_gp].mode))
 		return;
 
+	/* do not create push, if there is a path (inside the block) from the push value to IncSP */
+	h = heights_new(cg->irg);
+	if (get_nodes_block(val) == get_nodes_block(sp) &&
+		heights_reachable_in_block(h, val, sp))
+	{
+		heights_free(h);
+		return;
+	}
+	heights_free(h);
+
 	/* ok, translate into Push */
-	edge = get_irn_out_edge_first(irn);
+	edge       = get_irn_out_edge_first(irn);
 	old_proj_M = get_edge_src_irn(edge);
+	bl         = get_nodes_block(irn);
 
 	next = sched_next(irn);
 	sched_remove(irn);
 	sched_remove(sp);
 
-	bl   = get_nodes_block(irn);
-	push = new_rd_ia32_Push(NULL, current_ir_graph, bl,
-		be_get_IncSP_pred(sp), val, be_get_IncSP_mem(sp), mode_T);
-	proj_res = new_r_Proj(current_ir_graph, bl, push, get_irn_mode(sp), 0);
-	proj_M   = new_r_Proj(current_ir_graph, bl, push, mode_M, 1);
+	/*
+		build memory input:
+		if the IncSP points to NoMem -> just use the memory input from store
+		if IncSP points to somewhere else -> sync memory of IncSP and Store
+	*/
+	mem  = get_irn_n(irn, 3);
+	push = new_rd_ia32_Push(NULL, irg, bl, be_get_IncSP_pred(sp), val, mem);
+	proj_res = new_r_Proj(irg, bl, push, get_irn_mode(sp), pn_ia32_Push_stack);
+	proj_M   = new_r_Proj(irg, bl, push, mode_M, pn_ia32_Push_M);
+
+	/* copy a possible constant from the store */
+	set_ia32_id_cnst(push, get_ia32_id_cnst(irn));
+	set_ia32_immop_type(push, get_ia32_immop_type(irn));
 
 	/* the push must have SP out register */
 	arch_set_irn_register(cg->arch_env, push, arch_get_irn_register(cg->arch_env, sp));
@@ -452,65 +521,9 @@ static void ia32_create_Push(ir_node *irn, ia32_code_gen_t *cg) {
  * Creates a Pop from IncSP(Load(sp))
  */
 static void ia32_create_Pop(ir_node *irn, ia32_code_gen_t *cg) {
-	ir_node *old_proj_M = be_get_IncSP_mem(irn);
-	ir_node *load = skip_Proj(old_proj_M);
-	ir_node *old_proj_res = NULL;
-	ir_node *bl, *pop, *next, *proj_res, *proj_sp, *proj_M;
-	const ir_edge_t *edge;
-	const arch_register_t *reg, *sp;
-
-	if (! is_ia32_Load(load) || get_ia32_am_offs(load))
-		return;
-
-	if (arch_get_irn_register(cg->arch_env, get_irn_n(load, 1)) !=
-		&ia32_gp_regs[REG_GP_NOREG])
-		return;
-	if (arch_get_irn_register(cg->arch_env, get_irn_n(load, 0)) != cg->isa->sp)
-		return;
-
-	/* ok, translate into pop */
-	foreach_out_edge(load, edge) {
-		ir_node *succ = get_edge_src_irn(edge);
-		if (succ != old_proj_M) {
-			old_proj_res = succ;
-			break;
-		}
-	}
-	if (! old_proj_res) {
-		assert(0);
-		return; /* should not happen */
-	}
-
-	bl = get_nodes_block(load);
-
-	/* IncSP is typically scheduled after the load, so remove it first */
-	sched_remove(irn);
-	next = sched_next(old_proj_res);
-	sched_remove(old_proj_res);
-	sched_remove(load);
-
-	reg = arch_get_irn_register(cg->arch_env, load);
-	sp  = arch_get_irn_register(cg->arch_env, irn);
-
-	pop      = new_rd_ia32_Pop(NULL, current_ir_graph, bl, get_irn_n(irn, 0), get_irn_n(load, 2), mode_T);
-	proj_res = new_r_Proj(current_ir_graph, bl, pop, get_irn_mode(old_proj_res), 0);
-	proj_sp  = new_r_Proj(current_ir_graph, bl, pop, get_irn_mode(irn), 1);
-	proj_M   = new_r_Proj(current_ir_graph, bl, pop, mode_M, 2);
-
-	exchange(old_proj_M, proj_M);
-	exchange(old_proj_res, proj_res);
-	exchange(irn, proj_sp);
-
-	arch_set_irn_register(cg->arch_env, proj_res, reg);
-	arch_set_irn_register(cg->arch_env, proj_sp, sp);
-
-	sched_add_before(next, proj_sp);
-	sched_add_before(proj_sp, proj_res);
-	sched_add_before(proj_res,pop);
+	/* TODO */
 }
 
-/**
-
 /**
  * Tries to optimize two following IncSP.
  */
@@ -520,23 +533,13 @@ static void ia32_optimize_IncSP(ir_node *irn, ia32_code_gen_t *cg) {
 
 	if (be_is_IncSP(prev) && real_uses == 1) {
 		/* first IncSP has only one IncSP user, kill the first one */
-		unsigned       prev_offs = be_get_IncSP_offset(prev);
-		be_stack_dir_t prev_dir  = be_get_IncSP_direction(prev);
-		unsigned       curr_offs = be_get_IncSP_offset(irn);
-		be_stack_dir_t curr_dir  = be_get_IncSP_direction(irn);
+		int prev_offs = be_get_IncSP_offset(prev);
+		int curr_offs = be_get_IncSP_offset(irn);
 
-		int new_ofs = prev_offs * (prev_dir == be_stack_dir_expand ? -1 : +1) +
-			            curr_offs * (curr_dir == be_stack_dir_expand ? -1 : +1);
+		be_set_IncSP_offset(prev, prev_offs + curr_offs);
 
-		if (new_ofs < 0) {
-			new_ofs  = -new_ofs;
-			curr_dir = be_stack_dir_expand;
-		}
-		else
-			curr_dir = be_stack_dir_shrink;
-		be_set_IncSP_offset(prev, 0);
-		be_set_IncSP_offset(irn, (unsigned)new_ofs);
-		be_set_IncSP_direction(irn, curr_dir);
+		/* Omit the optimized IncSP */
+		be_set_IncSP_pred(irn, be_get_IncSP_pred(prev));
 	}
 }
 
@@ -546,12 +549,18 @@ static void ia32_optimize_IncSP(ir_node *irn, ia32_code_gen_t *cg) {
 void ia32_peephole_optimization(ir_node *irn, void *env) {
 	ia32_code_gen_t *cg = env;
 
-	if (is_ia32_TestJmp(irn))
-		ia32_optimize_TestJmp(irn, cg);
-	else if (is_ia32_CondJmp(irn))
-		ia32_optimize_CondJmp(irn, cg);
+	/* AMD CPUs want explicit compare before conditional jump  */
+	if (! ARCH_AMD(cg->opt_arch)) {
+		if (is_ia32_TestJmp(irn))
+			ia32_optimize_TestJmp(irn, cg);
+		else if (is_ia32_CondJmp(irn))
+			ia32_optimize_CondJmp(irn, cg);
+	}
+	/* seems to be buggy when using Pushes */
 	else if (be_is_IncSP(irn))
 		ia32_optimize_IncSP(irn, cg);
+	else if (is_ia32_Store(irn))
+		ia32_create_Push(irn, cg);
 }
 
 
@@ -566,6 +575,11 @@ void ia32_peephole_optimization(ir_node *irn, void *env) {
  *
  ******************************************************************/
 
+typedef struct {
+	ia32_code_gen_t *cg;
+	heights_t       *h;
+} ia32_am_opt_env_t;
+
 static int node_is_ia32_comm(const ir_node *irn) {
 	return is_ia32_irn(irn) ? is_ia32_commutative(irn) : 0;
 }
@@ -581,48 +595,6 @@ static int ia32_get_irn_n_edges(const ir_node *irn) {
 	return cnt;
 }
 
-/**
- * Returns the first mode_M Proj connected to irn.
- */
-static ir_node *get_mem_proj(const ir_node *irn) {
-	const ir_edge_t *edge;
-	ir_node         *src;
-
-	assert(get_irn_mode(irn) == mode_T && "expected mode_T node");
-
-	foreach_out_edge(irn, edge) {
-		src = get_edge_src_irn(edge);
-
-		assert(is_Proj(src) && "Proj expected");
-
-		if (get_irn_mode(src) == mode_M)
-			return src;
-	}
-
-	return NULL;
-}
-
-/**
- * Returns the first Proj with mode != mode_M connected to irn.
- */
-static ir_node *get_res_proj(const ir_node *irn) {
-	const ir_edge_t *edge;
-	ir_node         *src;
-
-	assert(get_irn_mode(irn) == mode_T && "expected mode_T node");
-
-	foreach_out_edge(irn, edge) {
-		src = get_edge_src_irn(edge);
-
-		assert(is_Proj(src) && "Proj expected");
-
-		if (get_irn_mode(src) != mode_M)
-			return src;
-	}
-
-	return NULL;
-}
-
 /**
  * Determines if pred is a Proj and if is_op_func returns true for it's predecessor.
  *
@@ -660,47 +632,130 @@ static int pred_is_specific_nodeblock(const ir_node *bl, const ir_node *pred,
 	return 0;
 }
 
-
-
 /**
- * Checks if irn is a candidate for address calculation or address mode.
+ * Checks if irn is a candidate for address calculation.
  *
- * address calculation (AC):
  * - none of the operand must be a Load  within the same block OR
  * - all Loads must have more than one user                    OR
  * - the irn has a frame entity (it's a former FrameAddr)
  *
+ * @param block   The block the Loads must/mustnot be in
+ * @param irn     The irn to check
+ * return 1 if irn is a candidate, 0 otherwise
+ */
+static int is_addr_candidate(const ir_node *block, const ir_node *irn) {
+	ir_node *in, *left, *right;
+	int      n, is_cand = 1;
+
+	left  = get_irn_n(irn, 2);
+	right = get_irn_n(irn, 3);
+
+	in = left;
+
+	if (pred_is_specific_nodeblock(block, in, is_ia32_Ld)) {
+		n         = ia32_get_irn_n_edges(in);
+		is_cand   = (n == 1) ? 0 : is_cand;  /* load with only one user: don't create LEA */
+	}
+
+	in = right;
+
+	if (pred_is_specific_nodeblock(block, in, is_ia32_Ld)) {
+		n         = ia32_get_irn_n_edges(in);
+		is_cand   = (n == 1) ? 0 : is_cand;  /* load with only one user: don't create LEA */
+	}
+
+	is_cand = get_ia32_frame_ent(irn) ? 1 : is_cand;
+
+	return is_cand;
+}
+
+/**
+ * Checks if irn is a candidate for address mode.
+ *
  * address mode (AM):
  * - at least one operand has to be a Load within the same block AND
  * - the load must not have other users than the irn             AND
  * - the irn must not have a frame entity set
  *
- * @param block       The block the Loads must/not be in
+ * @param cg          The ia32 code generator
+ * @param h           The height information of the irg
+ * @param block       The block the Loads must/mustnot be in
  * @param irn         The irn to check
- * @param check_addr  1 if to check for address calculation, 0 otherwise
- * return 1 if irn is a candidate for AC or AM, 0 otherwise
+ * return 0 if irn is no candidate, 1 if left load can be used, 2 if right one, 3 for both
  */
-static int is_candidate(const ir_node *block, const ir_node *irn, int check_addr) {
-	ir_node *in;
-	int      n, is_cand = check_addr;
+static ia32_am_cand_t is_am_candidate(ia32_code_gen_t *cg, heights_t *h, const ir_node *block, ir_node *irn) {
+	ir_node *in, *load, *other, *left, *right;
+	int      n, is_cand = 0, cand;
 
-	in = get_irn_n(irn, 2);
+	if (is_ia32_Ld(irn) || is_ia32_St(irn) || is_ia32_Store8Bit(irn) || is_ia32_vfild(irn) || is_ia32_vfist(irn) ||
+		is_ia32_GetST0(irn) || is_ia32_SetST0(irn) || is_ia32_xStoreSimple(irn))
+		return 0;
+
+	left  = get_irn_n(irn, 2);
+	right = get_irn_n(irn, 3);
+
+	in = left;
 
 	if (pred_is_specific_nodeblock(block, in, is_ia32_Ld)) {
 		n         = ia32_get_irn_n_edges(in);
-		is_cand   = check_addr ? (n == 1 ? 0 : is_cand) : (n == 1 ? 1 : is_cand);
+		is_cand   = (n == 1) ? 1 : is_cand;  /* load with more than one user: no AM */
+
+		load  = get_Proj_pred(in);
+		other = right;
+
+		/* 8bit Loads are not supported, they cannot be used with every register */
+		if (get_mode_size_bits(get_ia32_ls_mode(load)) < 16)
+			is_cand = 0;
+
+		/* If there is a data dependency of other irn from load: cannot use AM */
+		if (is_cand && get_nodes_block(other) == block) {
+			other   = skip_Proj(other);
+			is_cand = heights_reachable_in_block(h, other, load) ? 0 : is_cand;
+			/* this could happen in loops */
+			is_cand = heights_reachable_in_block(h, load, irn) ? 0 : is_cand;
+		}
 	}
 
-	in = get_irn_n(irn, 3);
+	cand    = is_cand ? IA32_AM_CAND_LEFT : IA32_AM_CAND_NONE;
+	in      = right;
+	is_cand = 0;
 
 	if (pred_is_specific_nodeblock(block, in, is_ia32_Ld)) {
 		n         = ia32_get_irn_n_edges(in);
-		is_cand   = check_addr ? (n == 1 ? 0 : is_cand) : (n == 1 ? 1 : is_cand);
+		is_cand   = (n == 1) ? 1 : is_cand;  /* load with more than one user: no AM */
+
+		load  = get_Proj_pred(in);
+		other = left;
+
+		/* 8bit Loads are not supported, they cannot be used with every register */
+		if (get_mode_size_bits(get_ia32_ls_mode(load)) < 16)
+			is_cand = 0;
+
+		/* If there is a data dependency of other irn from load: cannot use load */
+		if (is_cand && get_nodes_block(other) == block) {
+			other   = skip_Proj(other);
+			is_cand = heights_reachable_in_block(h, other, load) ? 0 : is_cand;
+			/* this could happen in loops */
+			is_cand = heights_reachable_in_block(h, load, irn) ? 0 : is_cand;
+		}
 	}
 
-	is_cand = get_ia32_frame_ent(irn) ? (check_addr ? 1 : 0) : is_cand;
+	cand = is_cand ? (cand | IA32_AM_CAND_RIGHT) : cand;
 
-	return is_cand;
+	/* check some special cases */
+	if (USE_SSE2(cg) && is_ia32_Conv_I2FP(irn)) {
+		/* SSE Conv I -> FP cvtsi2s(s|d) can only load 32 bit values */
+		if (get_mode_size_bits(get_ia32_tgt_mode(irn)) != 32)
+			cand = IA32_AM_CAND_NONE;
+	}
+	else if (is_ia32_Conv_I2I(irn)) {
+		/* we cannot load an N bit value and implicitly convert it into an M bit value if N > M */
+		if (get_mode_size_bits(get_ia32_src_mode(irn)) > get_mode_size_bits(get_ia32_tgt_mode(irn)))
+			cand = IA32_AM_CAND_NONE;
+	}
+
+	/* if the irn has a frame entity: we do not use address mode */
+	return get_ia32_frame_ent(irn) ? IA32_AM_CAND_NONE : cand;
 }
 
 /**
@@ -752,8 +807,6 @@ typedef enum _ia32_take_lea_attr {
 static int do_new_lea(ir_node *irn, ir_node *base, ir_node *index, ir_node *lea,
 		int have_am_sc, ia32_code_gen_t *cg)
 {
-	ir_node *lea_base = get_irn_n(lea, 0);
-	ir_node *lea_idx  = get_irn_n(lea, 1);
 	entity  *irn_ent  = get_ia32_frame_ent(irn);
 	entity  *lea_ent  = get_ia32_frame_ent(lea);
 	int      ret_val  = 0;
@@ -843,6 +896,34 @@ static int do_new_lea(ir_node *irn, ir_node *base, ir_node *index, ir_node *lea,
 	return ret_val;
 }
 
+/**
+ * Adds res before irn into schedule if irn was scheduled.
+ * @param irn  The schedule point
+ * @param res  The node to be scheduled
+ */
+static INLINE void try_add_to_sched(ir_node *irn, ir_node *res) {
+	if (sched_is_scheduled(irn))
+		sched_add_before(irn, res);
+}
+
+/**
+ * Removes irn from schedule if it was scheduled. If irn is a mode_T node
+ * all it's Projs are removed as well.
+ * @param irn  The irn to be removed from schedule
+ */
+static INLINE void try_remove_from_sched(ir_node *irn) {
+	if (sched_is_scheduled(irn)) {
+		if (get_irn_mode(irn) == mode_T) {
+			const ir_edge_t *edge;
+			foreach_out_edge(irn, edge) {
+				ir_node *proj = get_edge_src_irn(edge);
+				if (sched_is_scheduled(proj))
+					sched_remove(proj);
+			}
+		}
+		sched_remove(irn);
+	}
+}
 
 /**
  * Folds Add or Sub to LEA if possible
@@ -867,6 +948,7 @@ static ir_node *fold_addr(ia32_code_gen_t *cg, ir_node *irn, ir_node *noreg) {
 	entity     *lea_ent    = NULL;
 	ir_node    *left, *right, *temp;
 	ir_node    *base, *index;
+	int consumed_left_shift;
 	ia32_am_flavour_t am_flav;
 	DEBUG_ONLY(firm_dbg_module_t *mod = cg->mod;)
 
@@ -929,12 +1011,7 @@ static ir_node *fold_addr(ia32_code_gen_t *cg, ir_node *irn, ir_node *noreg) {
 	}
 
 	/* determine the operand which needs to be checked */
-	if (be_is_NoReg(cg, right)) {
-		temp = left;
-	}
-	else {
-		temp = right;
-	}
+	temp = be_is_NoReg(cg, right) ? left : right;
 
 	/* check if right operand is AMConst (LEA with ia32_am_O)  */
 	/* but we can only eat it up if there is no other symconst */
@@ -948,12 +1025,18 @@ static ir_node *fold_addr(ia32_code_gen_t *cg, ir_node *irn, ir_node *noreg) {
 		have_am_sc = 1;
 		dolea      = 1;
 		lea_o      = temp;
+
+		if (temp == base)
+			base = noreg;
+		else if (temp == right)
+			right = noreg;
 	}
 
 	if (isadd) {
 		/* default for add -> make right operand to index */
-		index = right;
-		dolea = 1;
+		index               = right;
+		dolea               = 1;
+		consumed_left_shift = -1;
 
 		DBG((mod, LEVEL_1, "\tgot LEA candidate with index %+F\n", index));
 
@@ -961,6 +1044,7 @@ static ir_node *fold_addr(ia32_code_gen_t *cg, ir_node *irn, ir_node *noreg) {
 		temp = left;
 		if (is_ia32_Lea(left)) {
 			temp = right;
+			consumed_left_shift = 0;
 		}
 
 		/* check for SHL 1,2,3 */
@@ -972,7 +1056,8 @@ static ir_node *fold_addr(ia32_code_gen_t *cg, ir_node *irn, ir_node *noreg) {
 				scale = get_tarval_long(get_ia32_Immop_tarval(temp));
 
 				if (scale <= 3) {
-					index = get_irn_n(temp, 2);
+					index               = get_irn_n(temp, 2);
+					consumed_left_shift = consumed_left_shift < 0 ? 1 : 0;
 
 					DBG((mod, LEVEL_1, "\tgot scaled index %+F\n", index));
 				}
@@ -989,11 +1074,9 @@ static ir_node *fold_addr(ia32_code_gen_t *cg, ir_node *irn, ir_node *noreg) {
 			if (left == right) {
 				base = noreg;
 			}
-			else if (! is_ia32_Lea(left) && (index != right)) {
-				/* index != right -> we found a good Shl           */
-				/* left  != LEA   -> this Shl was the left operand */
-				/* -> base is right operand                        */
-				base = right;
+			else if (consumed_left_shift == 1) {
+				/* -> base is right operand  */
+				base = (right == lea_o) ? noreg : right;
 			}
 		}
 	}
@@ -1087,7 +1170,7 @@ static ir_node *fold_addr(ia32_code_gen_t *cg, ir_node *irn, ir_node *noreg) {
 
 		am_flav = ia32_am_N;
 		/* determine new am flavour */
-		if (offs || offs_cnst || offs_lea) {
+		if (offs || offs_cnst || offs_lea || have_am_sc) {
 			am_flav |= ia32_O;
 		}
 		if (! be_is_NoReg(cg, base)) {
@@ -1108,25 +1191,46 @@ static ir_node *fold_addr(ia32_code_gen_t *cg, ir_node *irn, ir_node *noreg) {
 		DBG((mod, LEVEL_1, "\tLEA [%+F + %+F * %d + %s]\n", base, index, scale, get_ia32_am_offs(res)));
 
 		/* we will exchange it, report here before the Proj is created */
-		if (shift && lea && lea_o)
+		if (shift && lea && lea_o) {
+			try_remove_from_sched(shift);
+			try_remove_from_sched(lea);
+			try_remove_from_sched(lea_o);
 			DBG_OPT_LEA4(irn, lea_o, lea, shift, res);
-		else if (shift && lea)
+		}
+		else if (shift && lea) {
+			try_remove_from_sched(shift);
+			try_remove_from_sched(lea);
 			DBG_OPT_LEA3(irn, lea, shift, res);
-		else if (shift && lea_o)
+		}
+		else if (shift && lea_o) {
+			try_remove_from_sched(shift);
+			try_remove_from_sched(lea_o);
 			DBG_OPT_LEA3(irn, lea_o, shift, res);
-		else if (lea && lea_o)
+		}
+		else if (lea && lea_o) {
+			try_remove_from_sched(lea);
+			try_remove_from_sched(lea_o);
 			DBG_OPT_LEA3(irn, lea_o, lea, res);
-		else if (shift)
+		}
+		else if (shift) {
+			try_remove_from_sched(shift);
 			DBG_OPT_LEA2(irn, shift, res);
-		else if (lea)
+		}
+		else if (lea) {
+			try_remove_from_sched(lea);
 			DBG_OPT_LEA2(irn, lea, res);
-		else if (lea_o)
+		}
+		else if (lea_o) {
+			try_remove_from_sched(lea_o);
 			DBG_OPT_LEA2(irn, lea_o, res);
+		}
 		else
 			DBG_OPT_LEA1(irn, res);
 
 		/* get the result Proj of the Add/Sub */
-		irn = get_res_proj(irn);
+		try_add_to_sched(irn, res);
+		try_remove_from_sched(irn);
+		irn = ia32_get_res_proj(irn);
 
 		assert(irn && "Couldn't find result proj");
 
@@ -1170,6 +1274,8 @@ static void merge_loadstore_lea(ir_node *irn, ir_node *lea) {
 	set_irn_n(irn, 0, get_irn_n(lea, 0));
 	set_irn_n(irn, 1, get_irn_n(lea, 1));
 
+	try_remove_from_sched(lea);
+
 	/* clear remat flag */
 	set_ia32_flags(irn, get_ia32_flags(irn) & ~arch_irn_flags_rematerializable);
 
@@ -1181,32 +1287,33 @@ static void merge_loadstore_lea(ir_node *irn, ir_node *lea) {
 }
 
 /**
- * Optimizes a pattern around irn to address mode if possible.
+ * Sets new_right index of irn to right and new_left index to left.
+ * Also exchange left and right
  */
-void ia32_optimize_am(ir_node *irn, void *env) {
-	ia32_code_gen_t   *cg   = env;
-	ir_node           *res  = irn;
-	dbg_info          *dbg;
-	ir_mode           *mode;
-	ir_node           *block, *noreg_gp, *noreg_fp;
-	ir_node           *left, *right, *temp;
-	ir_node           *store, *load, *mem_proj;
-	ir_node           *succ, *addr_b, *addr_i;
-	int                check_am_src = 0;
-	DEBUG_ONLY(firm_dbg_module_t *mod = cg->mod;)
+static void exchange_left_right(ir_node *irn, ir_node **left, ir_node **right, int new_left, int new_right) {
+	ir_node *temp;
 
-	if (! is_ia32_irn(irn))
-		return;
+	set_irn_n(irn, new_right, *right);
+	set_irn_n(irn, new_left, *left);
 
-	dbg      = get_irn_dbg_info(irn);
-	mode     = get_irn_mode(irn);
-	block    = get_nodes_block(irn);
-	noreg_gp = ia32_new_NoReg_gp(cg);
-	noreg_fp = ia32_new_NoReg_fp(cg);
+	temp   = *left;
+	*left  = *right;
+	*right = temp;
 
-	DBG((mod, LEVEL_1, "checking for AM\n"));
+	/* this is only needed for Compares, but currently ALL nodes
+	 * have this attribute :-) */
+	set_ia32_pncode(irn, get_inversed_pnc(get_ia32_pncode(irn)));
+}
 
-	/* 1st part: check for address calculations and transform the into Lea */
+/**
+ * Performs address calculation optimization (create LEAs if possible)
+ */
+static void optimize_lea(ir_node *irn, void *env) {
+	ia32_code_gen_t *cg  = env;
+	ir_node         *block, *noreg_gp, *left, *right;
+
+	if (! is_ia32_irn(irn))
+		return;
 
 	/* Following cases can occur:                                  */
 	/* - Sub (l, imm) -> LEA [base - offset]                       */
@@ -1218,25 +1325,77 @@ void ia32_optimize_am(ir_node *irn, void *env) {
 	/*              with scale > 1 iff l/r == shl (1,2,3)          */
 
 	if (is_ia32_Sub(irn) || is_ia32_Add(irn)) {
-		left  = get_irn_n(irn, 2);
-		right = get_irn_n(irn, 3);
+		left     = get_irn_n(irn, 2);
+		right    = get_irn_n(irn, 3);
+		block    = get_nodes_block(irn);
+		noreg_gp = ia32_new_NoReg_gp(cg);
 
 	    /* Do not try to create a LEA if one of the operands is a Load. */
 		/* check is irn is a candidate for address calculation */
-		if (is_candidate(block, irn, 1)) {
-			DBG((mod, LEVEL_1, "\tfound address calculation candidate %+F ... ", irn));
+		if (is_addr_candidate(block, irn)) {
+			ir_node *res;
+
+			DBG((cg->mod, LEVEL_1, "\tfound address calculation candidate %+F ... ", irn));
 			res = fold_addr(cg, irn, noreg_gp);
 
-			if (res == irn)
-				DB((mod, LEVEL_1, "transformed into %+F\n", res));
+			if (res != irn)
+				DB((cg->mod, LEVEL_1, "transformed into %+F\n", res));
 			else
-				DB((mod, LEVEL_1, "not transformed\n"));
+				DB((cg->mod, LEVEL_1, "not transformed\n"));
 		}
 	}
+	else if (is_ia32_Ld(irn) || is_ia32_St(irn) || is_ia32_Store8Bit(irn)) {
+		/* - Load  -> LEA into Load  } TODO: If the LEA is used by more than one Load/Store */
+		/* - Store -> LEA into Store }       it might be better to keep the LEA             */
+		left = get_irn_n(irn, 0);
+
+		if (is_ia32_Lea(left)) {
+			const ir_edge_t *edge, *ne;
+			ir_node *src;
+
+			/* merge all Loads/Stores connected to this LEA with the LEA */
+			foreach_out_edge_safe(left, edge, ne) {
+				src = get_edge_src_irn(edge);
+
+				if (src && (get_edge_src_pos(edge) == 0) && (is_ia32_Ld(src) || is_ia32_St(src) || is_ia32_Store8Bit(src))) {
+					DBG((cg->mod, LEVEL_1, "\nmerging %+F into %+F\n", left, irn));
+					if (! is_ia32_got_lea(src))
+						merge_loadstore_lea(src, left);
+					set_ia32_got_lea(src);
+				}
+			}
+		}
+	}
+}
+
+
+/**
+ * Checks for address mode patterns and performs the
+ * necessary transformations.
+ * This function is called by a walker.
+ */
+static void optimize_am(ir_node *irn, void *env) {
+	ia32_am_opt_env_t *am_opt_env = env;
+	ia32_code_gen_t   *cg         = am_opt_env->cg;
+	heights_t         *h          = am_opt_env->h;
+	ir_node           *block, *noreg_gp, *noreg_fp;
+	ir_node           *left, *right;
+	ir_node           *store, *load, *mem_proj;
+	ir_node           *succ, *addr_b, *addr_i;
+	int               check_am_src          = 0;
+	int               need_exchange_on_fail = 0;
+	DEBUG_ONLY(firm_dbg_module_t *mod = cg->mod;)
+
+	if (! is_ia32_irn(irn) || is_ia32_Ld(irn) || is_ia32_St(irn) || is_ia32_Store8Bit(irn))
+		return;
 
-	/* 2nd part: fold following patterns:                                               */
-	/* - Load  -> LEA into Load  } TODO: If the LEA is used by more than one Load/Store */
-	/* - Store -> LEA into Store }       it might be better to keep the LEA             */
+	block    = get_nodes_block(irn);
+	noreg_gp = ia32_new_NoReg_gp(cg);
+	noreg_fp = ia32_new_NoReg_fp(cg);
+
+	DBG((mod, LEVEL_1, "checking for AM\n"));
+
+	/* fold following patterns:                                                         */
 	/* - op -> Load into AMop with am_Source                                            */
 	/*   conditions:                                                                    */
 	/*     - op is am_Source capable AND                                                */
@@ -1250,239 +1409,271 @@ void ia32_optimize_am(ir_node *irn, void *env) {
 	/*     - the Load and Store are in the same block AND                               */
 	/*     - nobody else uses the result of the op                                      */
 
-	if ((res == irn) && (get_ia32_am_support(irn) != ia32_am_None) && !is_ia32_Lea(irn)) {
-		/* 1st: check for Load/Store -> LEA   */
-		if (is_ia32_Ld(irn) || is_ia32_St(irn) || is_ia32_Store8Bit(irn)) {
-			left = get_irn_n(irn, 0);
+	if ((get_ia32_am_support(irn) != ia32_am_None) && ! is_ia32_Lea(irn)) {
+		ia32_am_cand_t cand      = is_am_candidate(cg, h, block, irn);
+		ia32_am_cand_t orig_cand = cand;
 
-			if (is_ia32_Lea(left)) {
-				const ir_edge_t *edge, *ne;
-				ir_node *src;
+		/* cand == 1: load is left;   cand == 2: load is right; */
 
-				/* merge all Loads/Stores connected to this LEA with the LEA */
-				foreach_out_edge_safe(left, edge, ne) {
-					src = get_edge_src_irn(edge);
+		if (cand == IA32_AM_CAND_NONE)
+			return;
 
-					if (src && (is_ia32_Ld(src) || is_ia32_St(src) || is_ia32_Store8Bit(src))) {
-						DBG((mod, LEVEL_1, "\nmerging %+F into %+F\n", left, irn));
-						merge_loadstore_lea(src, left);
-					}
-				}
-			}
+		DBG((mod, LEVEL_1, "\tfound address mode candidate %+F ... ", irn));
+
+		left  = get_irn_n(irn, 2);
+		if (get_irn_arity(irn) == 4) {
+			/* it's an "unary" operation */
+			right = left;
+		}
+		else {
+			right = get_irn_n(irn, 3);
 		}
-		/* check if the node is an address mode candidate */
-		else if (is_candidate(block, irn, 0)) {
-			DBG((mod, LEVEL_1, "\tfound address mode candidate %+F ... ", irn));
-
-			left  = get_irn_n(irn, 2);
-			if (get_irn_arity(irn) == 4) {
-				/* it's an "unary" operation */
-				right = left;
-			}
-			else {
-				right = get_irn_n(irn, 3);
-			}
 
-			/* normalize commutative ops */
-			if (node_is_ia32_comm(irn)) {
-				/* Assure that right operand is always a Load if there is one    */
-				/* because non-commutative ops can only use Dest AM if the right */
-				/* operand is a load, so we only need to check right operand.    */
-				if (pred_is_specific_nodeblock(block, left, is_ia32_Ld))
-				{
-					set_irn_n(irn, 2, right);
-					set_irn_n(irn, 3, left);
-
-					temp  = left;
-					left  = right;
-					right = temp;
-				}
-			}
+		/* normalize commutative ops */
+		if (node_is_ia32_comm(irn) && (cand == IA32_AM_CAND_RIGHT)) {
+
+			/* Assure that left operand is always a Load if there is one    */
+			/* because non-commutative ops can only use Dest AM if the left */
+			/* operand is a load, so we only need to check left operand.    */
 
-			/* check for Store -> op -> Load */
+			exchange_left_right(irn, &left, &right, 3, 2);
+			need_exchange_on_fail = 1;
 
-			/* Store -> op -> Load optimization is only possible if supported by op */
-			/* and if right operand is a Load                                       */
-			if ((get_ia32_am_support(irn) & ia32_am_Dest) &&
-				 pred_is_specific_nodeblock(block, right, is_ia32_Ld))
-			{
+			/* now: load is right */
+			cand = IA32_AM_CAND_LEFT;
+		}
 
-				/* An address mode capable op always has a result Proj.                  */
-				/* If this Proj is used by more than one other node, we don't need to    */
-				/* check further, otherwise we check for Store and remember the address, */
-				/* the Store points to. */
+		/* check for Store -> op -> Load */
 
-				succ = get_res_proj(irn);
-				assert(succ && "Couldn't find result proj");
+		/* Store -> op -> Load optimization is only possible if supported by op */
+		/* and if right operand is a Load                                       */
+		if ((get_ia32_am_support(irn) & ia32_am_Dest) && (cand & IA32_AM_CAND_LEFT))
+		{
+			/* An address mode capable op always has a result Proj.                  */
+			/* If this Proj is used by more than one other node, we don't need to    */
+			/* check further, otherwise we check for Store and remember the address, */
+			/* the Store points to. */
+
+			succ = ia32_get_res_proj(irn);
+			assert(succ && "Couldn't find result proj");
+
+			addr_b = NULL;
+			addr_i = NULL;
+			store  = NULL;
+
+			/* now check for users and Store */
+			if (ia32_get_irn_n_edges(succ) == 1) {
+				succ = get_edge_src_irn(get_irn_out_edge_first(succ));
+
+				if (is_ia32_xStore(succ) || is_ia32_Store(succ)) {
+					store  = succ;
+					addr_b = get_irn_n(store, 0);
+					addr_i = get_irn_n(store, 1);
+				}
+			}
 
-				addr_b = NULL;
-				addr_i = NULL;
-				store  = NULL;
+			if (store) {
+				/* we found a Store as single user: Now check for Load */
 
-				/* now check for users and Store */
-				if (ia32_get_irn_n_edges(succ) == 1) {
-					succ = get_edge_src_irn(get_irn_out_edge_first(succ));
+				/* skip the Proj for easier access */
+				load = is_Proj(right) ? (is_ia32_Load(get_Proj_pred(right)) ? get_Proj_pred(right) : NULL) : NULL;
 
-					if (is_ia32_fStore(succ) || is_ia32_Store(succ)) {
-						store  = succ;
-						addr_b = get_irn_n(store, 0);
-						addr_i = get_irn_n(store, 1);
+				/* Extra check for commutative ops with two Loads */
+				/* -> put the interesting Load left               */
+				if (load && node_is_ia32_comm(irn) && (cand == IA32_AM_CAND_BOTH)) {
+					if (load_store_addr_is_equal(load, store, addr_b, addr_i)) {
+						/* We exchange left and right, so it's easier to kill     */
+						/* the correct Load later and to handle unary operations. */
+						exchange_left_right(irn, &left, &right, 3, 2);
+						need_exchange_on_fail ^= 1;
 					}
 				}
 
-				if (store) {
-					/* we found a Store as single user: Now check for Load */
-
-					/* Extra check for commutative ops with two Loads */
-					/* -> put the interesting Load right              */
-					if (node_is_ia32_comm(irn) &&
-						pred_is_specific_nodeblock(block, left, is_ia32_Ld))
-					{
-						if ((addr_b == get_irn_n(get_Proj_pred(left), 0)) &&
-							(addr_i == get_irn_n(get_Proj_pred(left), 1)))
-						{
-							/* We exchange left and right, so it's easier to kill     */
-							/* the correct Load later and to handle unary operations. */
-							set_irn_n(irn, 2, right);
-							set_irn_n(irn, 3, left);
-
-							temp  = left;
-							left  = right;
-							right = temp;
-						}
+				/* skip the Proj for easier access */
+				load = get_Proj_pred(left);
+
+				/* Compare Load and Store address */
+				if (load_store_addr_is_equal(load, store, addr_b, addr_i)) {
+					/* Left Load is from same address, so we can */
+					/* disconnect the Load and Store here        */
+
+					/* set new base, index and attributes */
+					set_irn_n(irn, 0, addr_b);
+					set_irn_n(irn, 1, addr_i);
+					add_ia32_am_offs(irn, get_ia32_am_offs(load));
+					set_ia32_am_scale(irn, get_ia32_am_scale(load));
+					set_ia32_am_flavour(irn, get_ia32_am_flavour(load));
+					set_ia32_op_type(irn, ia32_AddrModeD);
+					set_ia32_frame_ent(irn, get_ia32_frame_ent(load));
+					set_ia32_ls_mode(irn, get_ia32_ls_mode(load));
+
+					set_ia32_am_sc(irn, get_ia32_am_sc(load));
+					if (is_ia32_am_sc_sign(load))
+						set_ia32_am_sc_sign(irn);
+
+					if (is_ia32_use_frame(load))
+						set_ia32_use_frame(irn);
+
+					/* connect to Load memory and disconnect Load */
+					if (get_irn_arity(irn) == 5) {
+						/* binary AMop */
+						set_irn_n(irn, 4, get_irn_n(load, 2));
+						set_irn_n(irn, 2, noreg_gp);
+					}
+					else {
+						/* unary AMop */
+						set_irn_n(irn, 3, get_irn_n(load, 2));
+						set_irn_n(irn, 2, noreg_gp);
 					}
 
-					/* skip the Proj for easier access */
-					load = get_Proj_pred(right);
+					/* connect the memory Proj of the Store to the op */
+					mem_proj = ia32_get_proj_for_mode(store, mode_M);
+					set_Proj_pred(mem_proj, irn);
+					set_Proj_proj(mem_proj, 1);
 
-					/* Compare Load and Store address */
-					if (load_store_addr_is_equal(load, store, addr_b, addr_i)) {
-						/* Right Load is from same address, so we can */
-						/* disconnect the Load and Store here        */
-
-						/* set new base, index and attributes */
-						set_irn_n(irn, 0, addr_b);
-						set_irn_n(irn, 1, addr_i);
-						add_ia32_am_offs(irn, get_ia32_am_offs(load));
-						set_ia32_am_scale(irn, get_ia32_am_scale(load));
-						set_ia32_am_flavour(irn, get_ia32_am_flavour(load));
-						set_ia32_op_type(irn, ia32_AddrModeD);
-						set_ia32_frame_ent(irn, get_ia32_frame_ent(load));
-						set_ia32_ls_mode(irn, get_ia32_ls_mode(load));
-
-						set_ia32_am_sc(irn, get_ia32_am_sc(load));
-						if (is_ia32_am_sc_sign(load))
-							set_ia32_am_sc_sign(irn);
-
-						if (is_ia32_use_frame(load))
-							set_ia32_use_frame(irn);
-
-						/* connect to Load memory and disconnect Load */
-						if (get_irn_arity(irn) == 5) {
-							/* binary AMop */
-							set_irn_n(irn, 4, get_irn_n(load, 2));
-							set_irn_n(irn, 3, noreg_gp);
-						}
-						else {
-							/* unary AMop */
-							set_irn_n(irn, 3, get_irn_n(load, 2));
-							set_irn_n(irn, 2, noreg_gp);
-						}
-
-						/* connect the memory Proj of the Store to the op */
-						mem_proj = get_mem_proj(store);
-						set_Proj_pred(mem_proj, irn);
-						set_Proj_proj(mem_proj, 1);
-
-						/* clear remat flag */
-						set_ia32_flags(irn, get_ia32_flags(irn) & ~arch_irn_flags_rematerializable);
-
-						DBG_OPT_AM_D(load, store, irn);
-
-						DB((mod, LEVEL_1, "merged with %+F and %+F into dest AM\n", load, store));
-					}
-				} /* if (store) */
-				else if (get_ia32_am_support(irn) & ia32_am_Source) {
-					/* There was no store, check if we still can optimize for source address mode */
-					check_am_src = 1;
+					/* clear remat flag */
+					set_ia32_flags(irn, get_ia32_flags(irn) & ~arch_irn_flags_rematerializable);
+
+					try_remove_from_sched(load);
+					try_remove_from_sched(store);
+					DBG_OPT_AM_D(load, store, irn);
+
+					DB((mod, LEVEL_1, "merged with %+F and %+F into dest AM\n", load, store));
+
+					need_exchange_on_fail = 0;
 				}
-			} /* if (support AM Dest) */
+			} /* if (store) */
 			else if (get_ia32_am_support(irn) & ia32_am_Source) {
-				/* op doesn't support am AM Dest -> check for AM Source */
+				/* There was no store, check if we still can optimize for source address mode */
 				check_am_src = 1;
 			}
+		} /* if (support AM Dest) */
+		else if (get_ia32_am_support(irn) & ia32_am_Source) {
+			/* op doesn't support am AM Dest -> check for AM Source */
+			check_am_src = 1;
+		}
 
-			/* normalize commutative ops */
-			if (node_is_ia32_comm(irn)) {
-				/* Assure that left operand is always a Load if there is one */
-				/* because non-commutative ops can only use Source AM if the */
-				/* left operand is a Load, so we only need to check the left */
-				/* operand afterwards.                                       */
-				if (pred_is_specific_nodeblock(block, right, is_ia32_Ld))	{
-					set_irn_n(irn, 2, right);
-					set_irn_n(irn, 3, left);
-
-					temp  = left;
-					left  = right;
-					right = temp;
-				}
-			}
+		/* was exchanged but optimize failed: exchange back */
+		if (need_exchange_on_fail) {
+			exchange_left_right(irn, &left, &right, 3, 2);
+			cand = orig_cand;
+		}
 
-			/* optimize op -> Load iff Load is only used by this op   */
-			/* and left operand is a Load which only used by this irn */
-			if (check_am_src                                        &&
-				pred_is_specific_nodeblock(block, left, is_ia32_Ld) &&
-				(ia32_get_irn_n_edges(left) == 1))
-			{
-				left = get_Proj_pred(left);
-
-				addr_b = get_irn_n(left, 0);
-				addr_i = get_irn_n(left, 1);
-
-				/* set new base, index and attributes */
-				set_irn_n(irn, 0, addr_b);
-				set_irn_n(irn, 1, addr_i);
-				add_ia32_am_offs(irn, get_ia32_am_offs(left));
-				set_ia32_am_scale(irn, get_ia32_am_scale(left));
-				set_ia32_am_flavour(irn, get_ia32_am_flavour(left));
-				set_ia32_op_type(irn, ia32_AddrModeS);
-				set_ia32_frame_ent(irn, get_ia32_frame_ent(left));
-				set_ia32_ls_mode(irn, get_ia32_ls_mode(left));
-
-				set_ia32_am_sc(irn, get_ia32_am_sc(left));
-				if (is_ia32_am_sc_sign(left))
-					set_ia32_am_sc_sign(irn);
-
-				/* clear remat flag */
-				set_ia32_flags(irn, get_ia32_flags(irn) & ~arch_irn_flags_rematerializable);
-
-				if (is_ia32_use_frame(left))
-					set_ia32_use_frame(irn);
-
-				/* connect to Load memory */
-				if (get_irn_arity(irn) == 5) {
-					/* binary AMop */
-					set_irn_n(irn, 4, get_irn_n(left, 2));
-				}
-				else {
-					/* unary AMop */
-					set_irn_n(irn, 3, get_irn_n(left, 2));
-				}
+		need_exchange_on_fail = 0;
 
-				/* disconnect from Load */
-				set_irn_n(irn, 2, noreg_gp);
+		/* normalize commutative ops */
+		if (check_am_src && node_is_ia32_comm(irn) && (cand == IA32_AM_CAND_LEFT)) {
 
-				DBG_OPT_AM_S(left, irn);
+			/* Assure that right operand is always a Load if there is one  */
+			/* because non-commutative ops can only use Source AM if the   */
+			/* right operand is a Load, so we only need to check the right */
+			/* operand afterwards.                                         */
 
-				/* If Load has a memory Proj, connect it to the op */
-				mem_proj = get_mem_proj(left);
-				if (mem_proj) {
-					set_Proj_pred(mem_proj, irn);
-					set_Proj_proj(mem_proj, 1);
-				}
+			exchange_left_right(irn, &left, &right, 3, 2);
+			need_exchange_on_fail = 1;
 
-				DB((mod, LEVEL_1, "merged with %+F into source AM\n", left));
+			/* now: load is left */
+			cand = IA32_AM_CAND_RIGHT;
+		}
+
+		/* optimize op -> Load iff Load is only used by this op    */
+		/* and right operand is a Load which only used by this irn */
+		if (check_am_src                &&
+			(cand & IA32_AM_CAND_RIGHT) &&
+			(get_irn_arity(irn) == 5)   &&
+			(ia32_get_irn_n_edges(right) == 1))
+		{
+			right = get_Proj_pred(right);
+
+			addr_b = get_irn_n(right, 0);
+			addr_i = get_irn_n(right, 1);
+
+			/* set new base, index and attributes */
+			set_irn_n(irn, 0, addr_b);
+			set_irn_n(irn, 1, addr_i);
+			add_ia32_am_offs(irn, get_ia32_am_offs(right));
+			set_ia32_am_scale(irn, get_ia32_am_scale(right));
+			set_ia32_am_flavour(irn, get_ia32_am_flavour(right));
+			set_ia32_op_type(irn, ia32_AddrModeS);
+			set_ia32_frame_ent(irn, get_ia32_frame_ent(right));
+			set_ia32_ls_mode(irn, get_ia32_ls_mode(right));
+
+			set_ia32_am_sc(irn, get_ia32_am_sc(right));
+			if (is_ia32_am_sc_sign(right))
+				set_ia32_am_sc_sign(irn);
+
+			/* clear remat flag */
+			set_ia32_flags(irn, get_ia32_flags(irn) & ~arch_irn_flags_rematerializable);
+
+			if (is_ia32_use_frame(right))
+				set_ia32_use_frame(irn);
+
+			/* connect to Load memory */
+			set_irn_n(irn, 4, get_irn_n(right, 2));
+
+			/* this is only needed for Compares, but currently ALL nodes
+			 * have this attribute :-) */
+			set_ia32_pncode(irn, get_inversed_pnc(get_ia32_pncode(irn)));
+
+			/* disconnect from Load */
+			set_irn_n(irn, 3, noreg_gp);
+
+			DBG_OPT_AM_S(right, irn);
+
+			/* If Load has a memory Proj, connect it to the op */
+			mem_proj = ia32_get_proj_for_mode(right, mode_M);
+			if (mem_proj) {
+				set_Proj_pred(mem_proj, irn);
+				set_Proj_proj(mem_proj, 1);
 			}
+
+			try_remove_from_sched(right);
+
+			DB((mod, LEVEL_1, "merged with %+F into source AM\n", right));
+		}
+		else {
+			/* was exchanged but optimize failed: exchange back */
+			if (need_exchange_on_fail)
+				exchange_left_right(irn, &left, &right, 3, 2);
 		}
 	}
 }
+
+/**
+ * Performs address mode optimization.
+ */
+void ia32_optimize_addressmode(ia32_code_gen_t *cg) {
+	/* if we are supposed to do AM or LEA optimization: recalculate edges */
+	if (cg->opt & (IA32_OPT_DOAM | IA32_OPT_LEA)) {
+		edges_deactivate(cg->irg);
+		edges_activate(cg->irg);
+	}
+	else {
+		/* no optimizations at all */
+		return;
+	}
+
+	/* beware: we cannot optimize LEA and AM in one run because */
+	/*         LEA optimization adds new nodes to the irg which */
+	/*         invalidates the phase data                       */
+
+	if (cg->opt & IA32_OPT_LEA) {
+		irg_walk_blkwise_graph(cg->irg, NULL, optimize_lea, cg);
+	}
+
+	if (cg->dump)
+		be_dump(cg->irg, "-lea", dump_ir_block_graph_sched);
+
+	if (cg->opt & IA32_OPT_DOAM) {
+		/* we need height information for am optimization */
+		heights_t *h = heights_new(cg->irg);
+		ia32_am_opt_env_t env;
+
+		env.cg = cg;
+		env.h  = h;
+
+		irg_walk_blkwise_graph(cg->irg, NULL, optimize_am, &env);
+
+		heights_free(h);
+	}
+}