Merge branch 'master' into regalloc-referenceregalloc-reference

9 files changed, 268 insertions, 13 deletions

diff --git a/ir/ana/irconsconfirm.c b/ir/ana/irconsconfirm.c
index 6f7ecc7..15d5e16 100644
--- a/ir/ana/irconsconfirm.c
+++ b/ir/ana/irconsconfirm.c
@@ -524,6 +524,240 @@ static void insert_Confirm(ir_node *node, void *data)
 	}
 }
 
+/**
+ * Look for Phis with Confirms/Consts on all their inputs. If
+ * possible, add a Confirm for their output.
+ *
+ * Only handles int modes.
+ */
+static void push_through_Phi(ir_node *phi, void *data)
+{
+	if (!is_Phi(phi) || !mode_is_int(get_irn_mode(phi))) {
+		return;
+	}
+
+	DB((dbg, LEVEL_3, "Trying to push confirms through %+F\n", phi));
+
+	ir_relation relation;
+	ir_node *bound;
+
+	ir_node *pred0 = get_Phi_pred(phi, 0);
+	if (is_Const(pred0)) {
+		relation = ir_relation_equal;
+		bound = pred0;
+	} else if (is_Confirm(pred0)) {
+		relation = get_Confirm_relation(pred0);
+		bound = get_Confirm_bound(pred0);
+
+		if ((relation & ir_relation_less_greater) == ir_relation_less_greater) {
+			DB((dbg, LEVEL_3, "Relation !=, giving up\n"));
+			return;
+		}
+	} else {
+		DB((dbg, LEVEL_3, "Pred 0 is unsuitable: %+F\n", pred0));
+		return;
+	}
+
+	DB((dbg, LEVEL_3, "Bound after pred 0: %s %+F\n", get_relation_string(relation), bound));
+
+	size_t n_preds = get_Phi_n_preds(phi);
+	for (size_t i = 1; i < n_preds; i++) {
+		ir_node *pred = get_Phi_pred(phi, i);
+
+		ir_node *new_bound;
+		ir_tarval *new_tv;
+		ir_relation new_relation;
+
+		if (is_Const(pred)) {
+			new_bound = pred;
+			new_tv = get_Const_tarval(pred);
+			new_relation = ir_relation_equal;
+			DB((dbg, LEVEL_3, "New bound %d: %s %+F\n", i, get_relation_string(new_relation), new_bound));
+
+		} else if (is_Confirm(pred)) {
+			new_relation = get_Confirm_relation(pred);
+			new_bound = get_Confirm_bound(pred);
+			DB((dbg, LEVEL_3, "New bound %d: %s %+F\n", i, get_relation_string(new_relation), new_bound));
+
+			if ((new_relation & ir_relation_less_greater) == ir_relation_less_greater) {
+				DB((dbg, LEVEL_3, "Relation !=, giving up\n"));
+				return;
+			}
+
+			if (!is_Const(new_bound)) {
+				if (new_bound != bound) {
+					DB((dbg, LEVEL_3, "New bound not constant and different\n", i, get_relation_string(new_relation), new_bound));
+					return;
+				}
+
+				// We have two confirms with the same bound.
+				// Even though it is not constant, we can merge the relations.
+				DB((dbg, LEVEL_3, "New bound not constant but same\n", i, get_relation_string(new_relation), new_bound));
+				relation |= new_relation;
+				DB((dbg, LEVEL_3, "Bound after pred %d: %s %+F\n", i, get_relation_string(relation), bound));
+				continue;
+			}
+
+			new_tv = get_Const_tarval(new_bound);
+		} else {
+			DB((dbg, LEVEL_3, "Pred %d is unsuitable: %+F\n", i, pred));
+			return;
+		}
+
+		if (!is_Const(bound)) {
+			DB((dbg, LEVEL_3, "Old bound %+F is not Const\n", bound));
+			return;
+		}
+		ir_tarval *bound_tv = get_Const_tarval(bound);
+
+		ir_relation new_cmp_bound = tarval_cmp(new_tv, bound_tv);
+		bool update;
+
+		switch (relation) {
+		case ir_relation_less:
+			update = new_cmp_bound & ir_relation_greater_equal;
+			goto update_less_or_less_equal;
+
+		case ir_relation_less_equal:
+			update = new_cmp_bound & ir_relation_greater;
+
+		update_less_or_less_equal:
+			if (update) {
+				bound = new_bound;
+
+				switch (new_relation) {
+				case ir_relation_less:
+				case ir_relation_less_equal:
+					relation = new_relation;
+					break;
+
+				case ir_relation_equal:
+					relation = ir_relation_less_equal;
+					break;
+
+				case ir_relation_greater_equal:
+				case ir_relation_greater:
+					DB((dbg, LEVEL_3, "%s u %s = T\n", get_relation_string(relation), get_relation_string(new_relation)));
+					return;
+
+				default:
+					panic("Unhandled new_relation %s\n", get_relation_string(new_relation));
+				}
+			}
+			break;
+
+		case ir_relation_greater:
+			update = new_cmp_bound & ir_relation_less_equal;
+			goto update_greater_or_greater_equal;
+
+		case ir_relation_greater_equal:
+			update = new_cmp_bound & ir_relation_less;
+
+		update_greater_or_greater_equal:
+			if (update) {
+				bound = new_bound;
+
+				switch (new_relation) {
+				case ir_relation_less:
+				case ir_relation_less_equal:
+					DB((dbg, LEVEL_3, "%s u %s = T\n", get_relation_string(relation), get_relation_string(new_relation)));
+					return;
+
+				case ir_relation_equal:
+					relation = ir_relation_greater_equal;
+					break;
+
+				case ir_relation_greater_equal:
+				case ir_relation_greater:
+					relation = new_relation;
+					break;
+
+				default:
+					panic("Unhandled new_relation %s\n", get_relation_string(new_relation));
+				}
+			}
+			break;
+
+
+		case ir_relation_equal:
+			switch (new_relation) {
+			case ir_relation_less:
+				if (new_cmp_bound & ir_relation_greater) {
+					relation = ir_relation_less;
+					bound = new_bound;
+				} else {
+					relation = ir_relation_less_equal;
+					// bound stays
+				}
+				break;
+
+			case ir_relation_less_equal:
+				if (new_cmp_bound & ir_relation_greater_equal) {
+					relation = ir_relation_less_equal;
+					bound = new_bound;
+				} else {
+					relation = ir_relation_less_equal;
+					// bound stays
+				}
+				break;
+
+			case ir_relation_equal:
+				// Special case: Don't lose information if the bounds are equal
+				if (new_cmp_bound & ir_relation_equal) {
+					// Nothing to do
+				} else if (new_cmp_bound & ir_relation_greater) {
+					relation = ir_relation_less_equal;
+					bound = new_bound;
+				} else {
+					relation = ir_relation_less_equal;
+					// bound stays
+				}
+				break;
+
+			case ir_relation_greater_equal:
+				if (new_cmp_bound & ir_relation_less_equal) {
+					relation = ir_relation_greater_equal;
+					bound = new_bound;
+				} else {
+					relation = ir_relation_greater_equal;
+					// bound stays
+				}
+				break;
+
+			case ir_relation_greater:
+				if (new_cmp_bound & ir_relation_less) {
+					relation = ir_relation_greater;
+					bound = new_bound;
+				} else {
+					relation = ir_relation_greater_equal;
+					// bound stays
+				}
+				break;
+
+			default:
+				panic("Unhandled new_relation %s\n", get_relation_string(new_relation));
+			}
+			break;
+
+		default:
+			panic("Unhandled relation %s\n", get_relation_string(relation));
+		}
+
+		DB((dbg, LEVEL_3, "Bound after pred %d: %s %+F\n", i, get_relation_string(relation), bound));
+	}
+
+	// If we get here, we have a valid bound that covers all of the Phi's preds.
+	// Confirm that bound for the Phi's users.
+	ir_node *phi_block = get_nodes_block(phi);
+	ir_node *confirm = new_r_Confirm(phi_block, phi, bound, relation);
+	edges_reroute_except(phi, confirm, confirm);
+
+	env_t *env = (env_t*) data;
+	env->num_confirms += 1;
+
+	DB((dbg, LEVEL_2, "Pushed confirms through %+F: new %+F\n", phi, confirm));
+}
+
 static void do_construct_confirms(ir_graph *irg, bool optimize)
 {
 	FIRM_DBG_REGISTER(dbg, "firm.ana.confirm");
@@ -550,6 +784,7 @@ static void do_construct_confirms(ir_graph *irg, bool optimize)
 		/* now, visit all blocks and add Confirms where possible */
 		irg_block_walk_graph(irg, insert_Confirm_in_block, NULL, &env);
 	}
+	irg_walk_graph(irg, push_through_Phi, NULL, &env);
 
 	DB((dbg, LEVEL_1, "# Confirms inserted : %u\n", env.num_confirms));
 	DB((dbg, LEVEL_1, "# Const replacements: %u\n", env.num_consts));
diff --git a/ir/be/amd64/amd64_emitter.c b/ir/be/amd64/amd64_emitter.c
index 920fbe7..fdbdf8e 100644
--- a/ir/be/amd64/amd64_emitter.c
+++ b/ir/be/amd64/amd64_emitter.c
@@ -256,8 +256,8 @@ static void amd64_emit_am(const ir_node *const node, bool indirect_star)
 		const arch_register_t *reg2 = arch_get_irn_register_in(node, 2);
 		emit_register_mode(reg2, attr->base.size);
 		be_emit_cstring(", ");
-		// fallthrough
 	}
+	// fallthrough
 	case AMD64_OP_REG_REG: {
 		const arch_register_t *reg1 = arch_get_irn_register_in(node, 1);
 		emit_register_mode(reg1, attr->base.size);
diff --git a/ir/be/becopyilp2.c b/ir/be/becopyilp2.c
index 9c8889d..9e55c38 100644
--- a/ir/be/becopyilp2.c
+++ b/ir/be/becopyilp2.c
@@ -436,13 +436,13 @@ static void extend_path(ilp_env_t *ienv, deq_t *path, const ir_node *irn)
 		curr_path[i++] = n;
 	}
 
-	for (int i = 1; i < len; ++i) {
+	for (int i = 1; i < len - 1; ++i) {
 		if (be_values_interfere(irn, curr_path[i]))
 			goto end;
 	}
 
 	/* check for terminating interference */
-	if (be_values_interfere(irn, curr_path[0])) {
+	if (len > 1 && be_values_interfere(irn, curr_path[0])) {
 		/* One node is not a path. */
 		/* And a path of length 2 is covered by a clique star constraint. */
 		if (len > 2) {
diff --git a/ir/ir/irargs.c b/ir/ir/irargs.c
index 0bf2f87..024ddb8 100644
--- a/ir/ir/irargs.c
+++ b/ir/ir/irargs.c
@@ -138,7 +138,7 @@ static int firm_emit(lc_appendable_t *app, const lc_arg_occ_t *occ,
 	}
 	case k_type: {
 		ir_type *type = (ir_type*)X;
-		char type_name[256];
+		char type_name[255];
 		ir_print_type(type_name, sizeof(type_name), type);
 		tp_opcode opcode = get_type_opcode(type);
 		snprintf(buf, sizeof(buf), "%s%s:%s", A("type"),
@@ -170,7 +170,7 @@ static int firm_emit(lc_appendable_t *app, const lc_arg_occ_t *occ,
 			break;
 		default:
 			if (is_Const(node)) {
-				char tv_buf[256];
+				char tv_buf[253];
 				ir_tarval *tv = get_Const_tarval(node);
 				if (tv)
 					tarval_snprintf(tv_buf, sizeof(tv_buf), tv);
diff --git a/ir/opt/irgopt.c b/ir/opt/irgopt.c
index cf88a02..7f9e71b 100644
--- a/ir/opt/irgopt.c
+++ b/ir/opt/irgopt.c
@@ -105,6 +105,12 @@ static void find_unreachable_blocks(ir_node *block, void *env)
 	if (get_Block_dom_depth(block) >= 0)
 		return;
 
+#ifdef DEBUG_libfirm
+	if (block == get_irg_end_block(get_irn_irg(block))) {
+		panic("Control flow does not reach the end block.");
+	}
+#endif
+
 	deq_t *waitq = (deq_t *)env;
 	foreach_block_succ(block, edge) {
 		ir_node *succ_block = get_edge_src_irn(edge);
diff --git a/scripts/gen_ir.py b/scripts/gen_ir.py
index 16127cf..6ce0adb 100755
--- a/scripts/gen_ir.py
+++ b/scripts/gen_ir.py
@@ -1,4 +1,4 @@
-#!/usr/bin/env python
+#!/usr/bin/env python3
 #
 # This file is part of libFirm.
 # Copyright (C) 2012 Karlsruhe Institute of Technology.
@@ -8,9 +8,24 @@ sys.dont_write_bytecode = True
 import argparse
 from jinja2 import Environment
 import filters
-import imp
 import jinjautil
 
+# Since python3, importing an arbitrary file became somewhat more involved. This piece of code is from "spack" at
+# https://github.com/epfl-scitas/spack/blob/releases/humagne/lib/spack/llnl/util/lang.py
+# and licensed under Apache-2.0.
+def load_module_from_file(module_name, module_path):
+    if sys.version_info[0] == 3 and sys.version_info[1] >= 5:
+        import importlib.util
+        spec = importlib.util.spec_from_file_location(module_name, module_path)
+        module = importlib.util.module_from_spec(spec)
+        spec.loader.exec_module(module)
+    else:
+        import importlib.machinery
+        loader = importlib.machinery.SourceFileLoader(module_name, module_path)
+        module = loader.load_module()
+
+    return module
+
 
 def main(argv):
     description = 'Generate code/docu from node specification'
@@ -38,9 +53,9 @@ def main(argv):
     loader.includedirs += config.includedirs
 
     # Load specfile
-    imp.load_source('spec', config.specfile)
+    load_module_from_file('spec', config.specfile)
     for num, extrafile in enumerate(config.extra):
-        imp.load_source('extra%s' % (num,), extrafile)
+        load_module_from_file('extra%s' % (num,), extrafile)
 
     env = Environment(loader=loader, keep_trailing_newline=True)
     env.globals.update(jinjautil.exports)
diff --git a/scripts/irops.py b/scripts/irops.py
index 8d65ad7..b9ca48c 100644
--- a/scripts/irops.py
+++ b/scripts/irops.py
@@ -1,7 +1,6 @@
 from jinjautil import export_filter, export
 from jinja2._compat import string_types
 from filters import arguments
-import imp
 import sys
 
 
diff --git a/scripts/jinja2/environment.py b/scripts/jinja2/environment.py
index 06156b8..feb6df3 100644
--- a/scripts/jinja2/environment.py
+++ b/scripts/jinja2/environment.py
@@ -637,9 +637,9 @@ class Environment(object):
                 warn(Warning('py_compile has no effect on pypy or Python 3'))
                 py_compile = False
             else:
-                import imp
+                import importlib.util
                 import marshal
-                py_header = imp.get_magic() + \
+                py_header = importlib.util.MAGIC_NUMBER + \
                     u'\xff\xff\xff\xff'.encode('iso-8859-15')
 
                 # Python 3.3 added a source filesize to the header
diff --git a/support/statev_sql.py b/support/statev_sql.py
index 666b4c5..0e2c85a 100755
--- a/support/statev_sql.py
+++ b/support/statev_sql.py
@@ -1,4 +1,4 @@
-#! /usr/bin/env python
+#! /usr/bin/env python3
 #
 # This file is part of libFirm.
 # Copyright (C) 2012 Karlsruhe Institute of Technology.