fix parallel moves

6 files changed, 81 insertions, 12 deletions

diff --git a/include/qbt/abi.h b/include/qbt/abi.h
index 6776cae..e0c32ac 100644
--- a/include/qbt/abi.h
+++ b/include/qbt/abi.h
@@ -131,7 +131,7 @@ enum {
 	RA21,
 	RA22,
 	RA23,
-	RA24,
+	RTMP0,
 	RT7,
 	RT8,
 	RT9,
@@ -149,7 +149,7 @@ enum {
 	RT21,
 	RT22,
 	RT23,
-	RT24,
+	RTMP1,
 	RS7,
 	RS8,
 	RS9,
@@ -167,7 +167,7 @@ enum {
 	RS21,
 	RS22,
 	RS23,
-	RS24,
+	RTMP2,
 };
 
 #define FOREACH_REG(M) \
diff --git a/include/qbt/nodes.h b/include/qbt/nodes.h
index 49cb11a..f51a32f 100644
--- a/include/qbt/nodes.h
+++ b/include/qbt/nodes.h
@@ -357,4 +357,6 @@ static inline void insn_insert(struct blk *b, struct insn i, size_t pos)
 	vec_insert(&b->insns, &i, pos);
 }
 
+bool return_blk(struct blk *b);
+
 #endif /* NODES_H */
diff --git a/src/abi.c b/src/abi.c
index a91743c..f1ff877 100644
--- a/src/abi.c
+++ b/src/abi.c
@@ -5,7 +5,7 @@
 static const int64_t ar_map[] = {
 	RA0, RA1, RA2, RA3, RA4, RA5, RA6, RA7, RA8, RA9,
 	RA10, RA11, RA12, RA13, RA14, RA15, RA16, RA17, RA18, RA19,
-	RA20, RA21, RA22, RA23, RA24
+	RA20, RA21, RA22, RA23
 };
 
 static struct val nth_ar(int64_t nth)
diff --git a/src/asm.c b/src/asm.c
index 4674c99..e6267b3 100644
--- a/src/asm.c
+++ b/src/asm.c
@@ -398,16 +398,79 @@ static void output_branch(struct blk *b, struct fn *f, FILE *o)
 	}
 }
 
+enum move_status {
+	TO_MOVE,
+	BEING_MOVED,
+	MOVED,
+};
+
+static void move_one(struct vec *params, struct vec *args, struct vec *status, size_t pi, FILE *o)
+{
+	struct val p = blk_param_at(*params, pi);
+	struct val a = blk_param_at(*args, pi);
+
+	if (same_val(p, a))
+		return;
+
+	vect_at(enum move_status, *status, pi) = BEING_MOVED;
+	foreach_blk_param(ai, *args) {
+		struct val a = blk_param_at(*args, ai);
+		/* moving argument to p would clobber another argument */
+		if (!same_val(a, p))
+			continue;
+
+		enum move_status s = vect_at(enum move_status, *status, ai);
+		switch (s) {
+		case TO_MOVE: {
+			move_one(params, args, status, ai, o);
+			break;
+		}
+
+		case BEING_MOVED: {
+			/* use temporary register to shuffle arguments around */
+			struct val tmp = reg_val(RTMP0);
+			struct insn i = insn_create(MOVE, NOTYPE, tmp, a, noclass(), 0);
+			output_move(i, o);
+			blk_param_at(*args, ai) = tmp;
+			break;
+		}
+
+		case MOVED:
+			break;
+
+		default:
+			abort();
+		}
+	}
+
+	struct insn i = insn_create(MOVE, NOTYPE, p, a, noclass(), 0);
+	output_move(i, o);
+	vect_at(enum move_status, *status, pi) = MOVED;
+}
+
 static void output_moves(struct vec *params, struct vec *args, FILE *o)
 {
+	/* this is taken from lightening, which took it from
+	 *
+	 * Tilting at Windmills with Coq: Formal Verification
+	 * of a Compilation Algorithm for Parallel Moves
+	 *  by Rideau et al
+	 */
 	/* move arguments to parameters */
 	assert(vec_len(params) == vec_len(args));
+
+	struct vec status = vec_create(sizeof(enum move_status));
 	foreach_blk_param(pi, *params) {
-		struct val p = blk_param_at(*params, pi);
-		struct val a = blk_param_at(*args, pi);
-		struct insn i = insn_create(MOVE, NOTYPE, p, a, noclass(), 0);
-		output_move(i, o);
+		enum move_status s = TO_MOVE;
+		vec_append(&status, &s);
 	}
+
+	foreach_blk_param(pi, *params) {
+		if (vect_at(enum move_status, status, pi) == TO_MOVE)
+			move_one(params, args, &status, pi, o);
+	}
+
+	vec_destroy(&status);
 }
 
 void output(struct fn *f, FILE *o)
diff --git a/src/parser.y b/src/parser.y
index 609c777..b4c0035 100644
--- a/src/parser.y
+++ b/src/parser.y
@@ -521,8 +521,8 @@ call
 	  }
 
 proc_ret
-	: id {
-		INSADD(RETARG, NOTYPE, noclass(), IDTOVAL($[id]), imm_val(parser->idx++, I27), 0);
+	: arg {
+		INSADD(RETARG, NOTYPE, noclass(), $[arg], imm_val(parser->idx++, I27), 0);
 	}
 
 proc_rets
diff --git a/src/ssa.c b/src/ssa.c
index 997f078..4283dae 100644
--- a/src/ssa.c
+++ b/src/ssa.c
@@ -41,6 +41,11 @@ static void build_params(struct blk *b, int visited)
 
 	b->visited++;
 
+	if (return_blk(b)) {
+		b->s1 = NULL;
+		b->s2 = NULL;
+	}
+
 	if (b->s1)
 		build_params(b->s1, visited);
 
@@ -102,7 +107,7 @@ static void build_params(struct blk *b, int visited)
 		if (p.class == NOCLASS)
 			continue;
 
-		if (has_val(&forward, p))
+		if (has_val(&required, p))
 			continue;
 
 		add_val(&required, p);
@@ -216,7 +221,6 @@ static size_t rename_temps(struct blk *b, size_t i)
 	}
 
 	vec_destroy(&rmap);
-
 	return i;
 }