for review: fix a bug in livemap.m

[Zoltan Somogyi]

Fix a bug that broke Tom's implementation of a random number generator at -O6.
The bug appeared only if value numbering is run for a second time after most
other low-level optimizations have been repeated several times. The problem
was that the first invocation of value numbering introduces a temp variable,
and the second one deletes the assignment to the temp variable because an
if_val with a liveness annotation comes between this assignment and the
first use of the temp variable.

compiler/livemap.m:
	When an if_val is preceded by a livevals annotation,
	do not replace the current liveness with the contents
	of the annotation. Instead, just include the contents
	of the annotation in the current set of live lvals.

tests/hard_coded/rnd.{m,exp}:
	Tom's test case.

tests/hard_coded/Mmakefile:
	Always run Tom's test case at -O6.

Zoltan.

Index: livemap.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/livemap.m,v
retrieving revision 1.31
diff -u -u -r1.31 livemap.m
--- livemap.m	1998/01/13 10:12:31	1.31
+++ livemap.m	1998/02/17 03:16:42
@@ -145,7 +145,8 @@
 
 		set__delete(Livevals0, Lval, Livevals1),
 		opt_util__lval_access_rvals(Lval, Rvals),
-		livemap__make_live_in_rvals([Rval | Rvals], Livevals1, Livevals),
+		livemap__make_live_in_rvals([Rval | Rvals], Livevals1,
+			Livevals),
 		Livemap = Livemap0,
 		Instrs = Instrs0,
 		Ccode = Ccode0
@@ -224,7 +225,12 @@
 		(
 			Found = yes,
 			% This if_val was put here by middle_rec.
-			Livevals3 = Livevals1
+			% We must make sure that the locations mentioned
+			% in the livevals annotation become live,
+			% since they will be needed at CodeAddr.
+			% The locations in Livevals0 may be needed
+			% in the fall-through continuation.
+			set__union(Livevals0, Livevals1, Livevals3)
 		;
 			Found = no,
 			livemap__make_live_in_rvals([Rval],
Index: Mmakefile
===================================================================
RCS file: /home/mercury1/repository/tests/hard_coded/Mmakefile,v
retrieving revision 1.16
diff -u -r1.16 Mmakefile
--- Mmakefile	1998/02/05 02:51:15	1.16
+++ Mmakefile	1998/02/17 06:08:41
@@ -57,6 +57,7 @@
 	remove_file \
 	reorder_di \
 	reverse_arith \
+	rnd \
 	string_alignment \
 	string_loop \
 	test_imported_no_tag \
@@ -72,6 +73,7 @@
 MCFLAGS-func_test	=	--infer-all
 MCFLAGS-ho_order	=	--optimize-higher-order
 MCFLAGS-no_fully_strict	=	--no-fully-strict
+MCFLAGS-rnd		=	-O6
 
 # In grade `none' with options `-O1 --opt-space' on kryten
 # (a sparc-sun-solaris2.5 system), mode_choice needs to be linked

New File: rnd.exp
===================================================================
7
90
14
83
68
41
16
58
66
97

New File: rnd.m
===================================================================
:- module rnd.

:- interface.

:- import_module io.

:- pred main(io__state, io__state).
:- mode main(di, uo) is det.

:- implementation.

:- import_module float, int, list.

main -->
	{ rnd__init(17, Rnd) },
	{ gen_nums(10, Rnd, [], Nums) },
	foldl((pred(Num::in, di, uo) is det -->
		print(Num), nl
	), Nums).

:- pred gen_nums(int, rnd, list(int), list(int)).
:- mode gen_nums(in, in, in, out) is det.

gen_nums(N, Rnd0, Acc0, Acc) :-
	( N =< 0 ->
		Acc = Acc0
	;
		irange(0, 100, Num, Rnd0, Rnd1),
		gen_nums(N-1, Rnd1, [Num|Acc0], Acc)
	).

%---------------------------------------------------------------------------%

:- pred rnd__init(int, rnd).
:- mode rnd__init(in, out) is det.

:- pred rnd(float, rnd, rnd).
:- mode rnd(out, in, out) is det.

:- pred irange(int, int, int, rnd, rnd).
:- mode irange(in, in, out, in, out) is det.

:- pred frange(float, float, float, rnd, rnd).
:- mode frange(in, in, out, in, out) is det.

:- pred shuffle(list(T), list(T), rnd, rnd).
:- mode shuffle(in, out, in, out) is det.

:- pred oneof(list(T), T, rnd, rnd).
:- mode oneof(in, out, in, out) is det.

%---------------------------------------------------------------------------%

:- import_module require.

irange(Min, Max, Val, R0, R) :-
	frange(rfloat(Min), rfloat(Max+1), FVal, R0, R),
	Val = rint(FVal).

frange(Min, Max, Val, R0, R) :-
	rnd(J, R0, R),
	Val = J*(Max - Min)+Min.

shuffle(Ins, Outs, R0, R) :-
	list__length(Ins, N),
	shuffle2(N, Ins, [], T0, R0, R1),
	shuffle2(N, T0, [], T1, R1, R2),
	shuffle2(N, T1, [], T2, R2, R3),
	shuffle2(N, T2, [], T3, R3, R4),
	shuffle2(N, T3, [], U, R4, R5),
	shuffle2(N, U, [], Outs, R5, R).

:- pred shuffle2(int, list(T), list(T), list(T), rnd, rnd).
:- mode shuffle2(in, in, in, out, in, out) is det.

shuffle2(N, Ins, Acc0, Acc, R0, R) :-
	( N > 0 ->
		irange(0, N-1, J, R0, R1),
		delnth(Ins, J, Rest, T),
		shuffle2(N-1, Rest, [T|Acc0], Acc, R1, R)
	;
		Acc = Acc0,
		R = R0
	).

:- pred delnth(list(T), int, list(T), T).
:- mode delnth(in, in, out, out) is det.

delnth([], _, _, _) :-
	error("delnth: no enough elems!").
delnth([X|Xs], N, Zs, Z) :-
	( N =< 0 ->
		Z = X,
		Zs = Xs
	;
		Zs = [X|Ys],
		delnth(Xs, N-1, Ys, Z)
	).

oneof(Things, Thing, R0, R) :-
	list__length(Things, Num),
	irange(0, Num-1, X, R0, R),
	list__index0_det(Things, X, Thing).

%---------------------------------------------------------------------------%

:- type vec
	---> vec(int, int, int, int, int, int, int, int, int, int).

:- type rnd
	---> rnd(
		vec,
		vec,
		int
	).

rnd__init(Seed, rnd(M1, M2, Seed)) :-
	SN = Seed /\ ((1 << 15) - 1),
	N  = Seed /\ ((1 << 30) - 1),
	M1a = vec(0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
	M2a = vec(0, 0, 0, 0, 0, 0, 0, 0, 0, 0),
	seed1(17, SN, N, M1a, M2a, M1b, M2b),
	set(M1b, 0, (M1b ** 0) /\ ((1 << 15) - 1), M1),
	set(M2b, 0, (M2b ** 0) /\ ((1 << 15) - 1), M2).

:- pred seed1(int, int, int, vec, vec, vec, vec).
:- mode seed1(in, in, in, in, in, out, out) is det.

seed1(N, SNum0, Num0, M1a, M2a, M1, M2) :-
	(N > 0 ->
		Num1 = 30903 * SNum0 + (Num0 >> 15),
		SNum1 = Num1 /\ ((1 << 15) - 1),
		( N >= 9 ->
			M2b = M2a,
			set(M1a, 17 - N, SNum1, M1b)
		;
			M1b = M1a,
			set(M2a, 8 - N, SNum1, M2b)
		),
		seed1(N-1, SNum1, Num1, M1b, M2b, M1, M2)
	;
		M1 = M1a,
		M2 = M2a
	).

rnd(Res, rnd(M1a, M2a, _Seed0), rnd(M1d, M2d, Seed1)) :-
	shift(M1a, M1b),
	shift(M2a, M2b),
	N1a = (M1b ** 0),
	N2a = (M2b ** 0),

	N1b = N1a + 1941 * (M1b ** 2) + 1860 * (M1b ** 3) + 1812 * (M1b ** 4)
		+ 1776 * (M1b ** 5) + 1492 * (M1b ** 6) + 1215 * (M1b ** 7)
		+ 1066 * (M1b ** 8) + 12013 * (M1b ** 9),

	N2b = N2a + 1111 * (M2b ** 2) + 2222 * (M2b ** 3) + 3333 * (M2b ** 4)
		+ 4444 * (M2b ** 5) + 5555 * (M2b ** 6) + 6666 * (M2b ** 7)
		+ 7777 * (M2b ** 8) + 9272 * (M2b ** 9),

	set(M1b, 0, (N1b >> 15) /\ ((1 << 15) - 1), M1c),
	set(M2b, 0, (N2b >> 15) /\ ((1 << 15) - 1), M2c),

	set(M1c, 1, N1b /\ ((1 << 15) - 1), M1d),
	set(M2c, 1, N2b /\ ((1 << 15) - 1), M2d),

	Seed1 = ((M1d ** 1) << 15) + (M2d ** 1),

	Res = rfloat(Seed1)/rfloat((1 << 30) - 1).

:- pred shift(vec, vec).
:- mode shift(in, out) is det.

shift(Vec0, Vec1) :-
	Vec0 = vec(A, B, C, D, E, F, G, H, I, _),
	Vec1 = vec(A, B, B, C, D, E, F, G, H, I).

:- func (vec ** int) = int.
:- mode ((in ** in) = out) is det.
:- mode ((in ** in(bound(0))) = out) is det.
:- mode ((in ** in(bound(1))) = out) is det.
:- mode ((in ** in(bound(2))) = out) is det.
:- mode ((in ** in(bound(3))) = out) is det.
:- mode ((in ** in(bound(4))) = out) is det.
:- mode ((in ** in(bound(5))) = out) is det.
:- mode ((in ** in(bound(6))) = out) is det.
:- mode ((in ** in(bound(7))) = out) is det.
:- mode ((in ** in(bound(8))) = out) is det.
:- mode ((in ** in(bound(9))) = out) is det.

( Vec ** Ind ) = Res :-
	Vec = vec(A, B, C, D, E, F, G, H, I, J),
	(
		( Ind = 0, Res0 = A
		; Ind = 1, Res0 = B
		; Ind = 2, Res0 = C
		; Ind = 3, Res0 = D
		; Ind = 4, Res0 = E
		; Ind = 5, Res0 = F
		; Ind = 6, Res0 = G
		; Ind = 7, Res0 = H
		; Ind = 8, Res0 = I
		; Ind = 9, Res0 = J
		)
	->
		Res = Res0
	;
		error("**: out of range")
	).

:- pred set(vec, int, int, vec).
:- mode set(in, in, in, out) is det.
:- mode set(in, in(bound(0)), in, out) is det.
:- mode set(in, in(bound(1)), in, out) is det.
:- mode set(in, in(bound(2)), in, out) is det.
:- mode set(in, in(bound(3)), in, out) is det.
:- mode set(in, in(bound(4)), in, out) is det.
:- mode set(in, in(bound(5)), in, out) is det.
:- mode set(in, in(bound(6)), in, out) is det.
:- mode set(in, in(bound(7)), in, out) is det.
:- mode set(in, in(bound(8)), in, out) is det.
:- mode set(in, in(bound(9)), in, out) is det.

set(Vec0, Ind, V, Vec) :-
	Vec0 = vec(A, B, C, D, E, F, G, H, I, J),
	(
		( Ind = 0, Vec1 = vec(V, B, C, D, E, F, G, H, I, J)
		; Ind = 1, Vec1 = vec(A, V, C, D, E, F, G, H, I, J)
		; Ind = 2, Vec1 = vec(A, B, V, D, E, F, G, H, I, J)
		; Ind = 3, Vec1 = vec(A, B, C, V, E, F, G, H, I, J)
		; Ind = 4, Vec1 = vec(A, B, C, D, V, F, G, H, I, J)
		; Ind = 5, Vec1 = vec(A, B, C, D, E, V, G, H, I, J)
		; Ind = 6, Vec1 = vec(A, B, C, D, E, F, V, H, I, J)
		; Ind = 7, Vec1 = vec(A, B, C, D, E, F, G, V, I, J)
		; Ind = 8, Vec1 = vec(A, B, C, D, E, F, G, H, V, J)
		; Ind = 9, Vec1 = vec(A, B, C, D, E, F, G, H, I, V)
		)
	->
		Vec = Vec1
	;
		error("set: out of range")
	).

:- func rfloat(int) = float.
:- pragma c_code(rfloat(I::in) = (F::out), "F = I;").

:- func rint(float) = int.
:- pragma c_code(rint(F::in) = (I::out), "I = F;").

:- pred for(int, int, pred(int, T, T), T, T).
:- mode for(in, in, pred(in, in, out) is det, in, out) is det.

for(Min, Max, Pred, Acc0, Acc) :-
	( Min =< Max ->
		call(Pred, Min, Acc0, Acc1),
		for(Min+1, Max, Pred, Acc1, Acc)
	;
		Acc = Acc0
	).