bug fix to frameopt

Zoltan Somogyi zs at cs.mu.oz.au
Thu Jul 17 11:31:27 AEST 1997
Previous message: diff: runtime/memory.c bug fix
Next message: [m-dev.] bug fix to frameopt
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Comments, anyone?

Zoltan.

cvs diff: Diffing .
cvs diff: Diffing bindist
cvs diff: Diffing boehm_gc
cvs diff: Diffing boehm_gc/Mac_files
cvs diff: Diffing boehm_gc/cord
cvs diff: Diffing boehm_gc/cord/private
cvs diff: Diffing boehm_gc/include
cvs diff: Diffing boehm_gc/include/private
cvs diff: Diffing bytecode
cvs diff: Diffing compiler
Index: compiler/frameopt.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/frameopt.m,v
retrieving revision 1.58
diff -u -r1.58 frameopt.m
--- frameopt.m	1997/07/16 06:22:58	1.58
+++ frameopt.m	1997/07/17 00:13:50
@@ -59,24 +59,28 @@
 %		detstackvar(N) = succip
 %	L1:
 %		...
+%		succip = detstackvar(N)
 %		finalization
 %		goto L1
 %
 % The advantage is that we don't destroy the stack frame just to set it up
-% again.
+% again. The restore of succip can be omitted if the procedure makes no calls,
+% since in that case succip must still contain the value it had when this
+% procedure was called.
 %
 % Since the second transformation is a bigger win, we prefer to use it
 % whenever both transformations are possible.
 %
-% NOTE: This module requires label optimisation to be turned on because
-% it cannot handle code sequences of the form
+% NOTE: This module cannot handle code sequences of the form
 %
 %	label1:
 %	label2:
 %
-% The "null block" between the labels makes frameopt choke.  This should
-% be handled by handle_options, but if you see an error of the form
-% "label in substitute_labels_instr", this is a possible cause.
+% Jump optimization converts any gotos to label1 to gotos to label2, making
+% label1 unused, and label optimization removes unused labels. (This works
+% for any number of labels in a sequence, not just two.) Therefore the
+% handle_options module turns on the jump and label optimizations whenever
+% frame optimization is turned on.
 
 %-----------------------------------------------------------------------------%
 
@@ -87,9 +91,6 @@
 :- import_module llds.
 :- import_module bool, list.
 
-	% Delay the construction of det stack frames as long as possible,
-	% in order to avoid the construction in as many cases as possible.
-	%
 	% The first bool output says whether we performed any modifications.
 	% If yes, then we also introduced some extra labels that should be
 	% deleted. The second says whether we introduced any jumps that
@@ -120,8 +121,9 @@
 		analyze_block_map(LabelSeq0, BlockMap1, BlockMap2, KeepFrame),
 		(
 			KeepFrame = yes(FirstLabel - SecondLabel),
+			find_any_calls(LabelSeq0, BlockMap2, AnyCalls),
 			keep_frame(LabelSeq0, BlockMap2,
-				FirstLabel, SecondLabel, BlockMap),
+				FirstLabel, SecondLabel, AnyCalls, BlockMap),
 			LabelSeq = LabelSeq0,
 			NewComment = comment("keeping stack frame") - "",
 			list__append(Comments0, [NewComment], Comments),
@@ -190,13 +192,15 @@
 						% setup or teardown. The bool
 						% says whether the code in the
 						% block needs a stack frame.
-			;	teardown(list(instruction)).
+			;	teardown(list(instruction), list(instruction)).
 						% This block contains stack
 						% teardown and goto code;
-						% the arg gives just the goto
-						% code (which should have a
-						% label instruction put before
-						% it if used).
+						% the two args give the instr
+						% that restores succip (if any)
+						% and the goto code (which must
+						% be a list because it may or
+						% mey not contain a liveness
+						% annotation).
 
 %-----------------------------------------------------------------------------%
 
@@ -295,7 +299,7 @@
 			LabelSeq = [Label | LabelSeq0]
 		;
 			frameopt__detstack_teardown(Instrs0, FrameSize,
-				Tail, Teardown, Goto, Remain)
+				Tail, Teardown, RestoreSuccip, Goto, Remain)
 		->
 			( Tail = [] ->
 				MaybeTailInfo = no,
@@ -305,7 +309,7 @@
 				TeardownLabel = Label,
 				TeardownInfo = block_info(TeardownLabel,
 					TeardownBlock, [], no,
-					teardown(Goto))
+					teardown(RestoreSuccip, Goto))
 			;
 				block_needs_frame(Tail, Needs),
 				TailInfo = block_info(Label, [Instr0 | Tail],
@@ -319,7 +323,7 @@
 				TeardownLabel = NewLabel,
 				TeardownInfo = block_info(TeardownLabel,
 					TeardownBlock, [], no,
-					teardown(Goto))
+					teardown(RestoreSuccip, Goto))
 			),
 			build_block_map(Remain, FrameSize, LabelSeq0,
 				BlockMap0, BlockMap1, ProcLabel, N1, N),
@@ -417,14 +421,15 @@
 	% We are looking for the teardown components in any order, since
 	% value numbering may change the original order. This is also the
 	% reason why we allow teardown instructions to be interleaved with
-	% instructions that do not access the stack.
+	% instructions that do not access the stack, and why some teardown
+	% instructions (e.g. the one that restores succip) may be missing.
 
 :- pred frameopt__detstack_teardown(list(instruction)::in, int::in,
-	list(instruction)::out, list(instruction)::out,
+	list(instruction)::out, list(instruction)::out, list(instruction)::out,
 	list(instruction)::out, list(instruction)::out) is semidet.
 
 frameopt__detstack_teardown([Instr0 | Instrs0], FrameSize,
-		Tail, Teardown, Goto, Remain) :-
+		Tail, Teardown, RestoreSuccip, Goto, Remain) :-
 	(
 		Instr0 = label(_) - _
 	->
@@ -432,26 +437,29 @@
 	;
 		frameopt__detstack_teardown_2([Instr0 | Instrs0], FrameSize,
 			[], [], [], [],
-			TailPrime, TeardownPrime, GotoPrime, RemainPrime)
+			TailPrime, TeardownPrime, RestoreSuccipPrime,
+			GotoPrime, RemainPrime)
 	->
 		Tail = TailPrime,
 		Teardown = TeardownPrime,
+		RestoreSuccip = RestoreSuccipPrime,
 		Goto = GotoPrime,
 		Remain = RemainPrime
 	;
 		frameopt__detstack_teardown(Instrs0, FrameSize,
-			Tail1, Teardown, Goto, Remain),
+			Tail1, Teardown, RestoreSuccip, Goto, Remain),
 		Tail = [Instr0 | Tail1]
 	).
 
 :- pred frameopt__detstack_teardown_2(list(instruction)::in, int::in,
 	list(instruction)::in, list(instruction)::in, list(instruction)::in,
 	list(instruction)::in, list(instruction)::out, list(instruction)::out,
-	list(instruction)::out, list(instruction)::out) is semidet.
+	list(instruction)::out, list(instruction)::out, list(instruction)::out)
+	is semidet.
 
 frameopt__detstack_teardown_2(Instrs0, FrameSize,
 		SeenSuccip0, SeenDecrsp0, SeenExtra0, SeenLivevals0,
-		Tail, Teardown, Goto, Remain) :-
+		Tail, Teardown, RestoreSuccip, Goto, Remain) :-
 	opt_util__skip_comments(Instrs0, Instrs1),
 	Instrs1 = [Instr1 | Instrs2],
 	Instr1 = Uinstr1 - _,
@@ -466,14 +474,16 @@
 			SeenSuccip1 = [Instr1],
 			frameopt__detstack_teardown_2(Instrs2, FrameSize,
 				SeenSuccip1, SeenDecrsp0, SeenExtra0,
-				SeenLivevals0, Tail, Teardown, Goto, Remain)
+				SeenLivevals0, Tail, Teardown,
+				RestoreSuccip, Goto, Remain)
 		;
 			opt_util__lval_refers_stackvars(Lval, no),
 			opt_util__rval_refers_stackvars(Rval, no),
 			list__append(SeenExtra0, [Instr1], SeenExtra1),
 			frameopt__detstack_teardown_2(Instrs2, FrameSize,
 				SeenSuccip0, SeenDecrsp0, SeenExtra1,
-				SeenLivevals0, Tail, Teardown, Goto, Remain)
+				SeenLivevals0, Tail, Teardown,
+				RestoreSuccip, Goto, Remain)
 		)
 	;
 		Uinstr1 = decr_sp(FrameSize),
@@ -481,19 +491,20 @@
 		SeenDecrsp1 = [Instr1],
 		frameopt__detstack_teardown_2(Instrs2, FrameSize,
 			SeenSuccip0, SeenDecrsp1, SeenExtra0, SeenLivevals0,
-			Tail, Teardown, Goto, Remain)
+			Tail, Teardown, RestoreSuccip, Goto, Remain)
 	;
 		Uinstr1 = livevals(_),
 		SeenLivevals0 = [],
 		SeenLivevals1 = [Instr1],
 		frameopt__detstack_teardown_2(Instrs2, FrameSize,
 			SeenSuccip0, SeenDecrsp0, SeenExtra0, SeenLivevals1,
-			Tail, Teardown, Goto, Remain)
+			Tail, Teardown, RestoreSuccip, Goto, Remain)
 	;
 		Uinstr1 = goto(_),
 		SeenDecrsp0 = [_],
 		list__append(SeenSuccip0, SeenDecrsp0, Teardown),
 		Tail = SeenExtra0,
+		RestoreSuccip = SeenSuccip0,
 		list__append(SeenLivevals0, [Instr1], Goto),
 		Remain = Instrs2
 	).
@@ -672,6 +683,23 @@
 %-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%
 
+:- pred find_any_calls(list(label)::in, block_map::in, bool::out) is det.
+
+find_any_calls([], _BlockMap, no).
+find_any_calls([Label | Labels], BlockMap, AnyCalls) :-
+	map__lookup(BlockMap, Label, BlockInfo),
+	BlockInfo = block_info(_, Instrs, _, _, _),
+	(
+		list__member(Instr, Instrs),
+		Instr = call(_, _, _, _) - _
+	->
+		AnyCalls = yes
+	;
+		find_any_calls(Labels, BlockMap, AnyCalls)
+	).
+
+%-----------------------------------------------------------------------------%
+
 	% Transform the given block sequence to effect the optimization
 	% of keeping the stack frame for recursive tail calls once it has
 	% been set up by the initial entry to the procedure.
@@ -680,38 +708,45 @@
 	% should replace it in tailcalls that avoid the stack teardown.
 
 :- pred keep_frame(list(label)::in, block_map::in, label::in, label::in,
-	block_map::out) is det.
+	bool::in, block_map::out) is det.
 
-keep_frame([], BlockMap, _FirstLabel, _SecondLabel, BlockMap).
-keep_frame([Label | Labels], BlockMap0, FirstLabel, SecondLabel, BlockMap) :-
+keep_frame([], BlockMap, _FirstLabel, _SecondLabel, _AnyCalls, BlockMap).
+keep_frame([Label | Labels], BlockMap0, FirstLabel, SecondLabel, AnyCalls,
+		BlockMap) :-
 	map__lookup(BlockMap0, Label, BlockInfo0),
 	(
-		BlockInfo0 = block_info(Label, Instrs0, [_], no,
-			teardown(Instrs1)),
-		pick_last(Instrs0, _NonLastInstrs, LastInstr),
-		LastInstr = goto(label(GotoLabel)) - Comment,
+		BlockInfo0 = block_info(Label, OrigInstrs, [_], no,
+			teardown(RestoreSuccip, BareInstrs)),
+		pick_last(OrigInstrs, _NonLastOrigInstrs, LastOrigInstr),
+		LastOrigInstr = goto(label(GotoLabel)) - Comment,
 		same_label_ref(FirstLabel, GotoLabel)
 	->
 		(
-			Instrs0 = [Instr0 | _],
-			Instr0 = label(_) - _
+			OrigInstrs = [OrigInstr0 | _],
+			OrigInstr0 = label(_) - _
 		->
-			NewLabelInstr = Instr0
+			NewLabelInstr = OrigInstr0
 		;
 			error("block does not begin with label")
 		),
-		pick_last(Instrs1, NonLastInstrs, _LastInstr),
+		pick_last(BareInstrs, NonLastBareInstrs, _LastBareInstr),
 		string__append(Comment, " (keeping frame)", NewComment),
 		NewGoto = goto(label(SecondLabel)) - NewComment,
-		list__append([NewLabelInstr | NonLastInstrs], [NewGoto],
-			Instrs),
+		NewFrontInstrs = [NewLabelInstr | NonLastBareInstrs],
+		( AnyCalls = yes ->
+			list__append(RestoreSuccip, [NewGoto], NewBackInstrs)
+		;
+			NewBackInstrs = [NewGoto]
+		),
+		list__append(NewFrontInstrs, NewBackInstrs, Instrs),
 		BlockInfo = block_info(Label, Instrs, [SecondLabel], no,
 			ordinary(yes)),
 		map__det_update(BlockMap0, Label, BlockInfo, BlockMap1)
 	;
 		BlockMap1 = BlockMap0
 	),
-	keep_frame(Labels, BlockMap1, FirstLabel, SecondLabel, BlockMap).
+	keep_frame(Labels, BlockMap1, FirstLabel, SecondLabel, AnyCalls,
+		BlockMap).
 
 :- pred pick_last(list(T)::in, list(T)::out, T::out) is det.
 
@@ -868,7 +903,7 @@
 			queue__put(Queue0, Label, Queue1)
 		)
 	;
-		BlockType = teardown(_),
+		BlockType = teardown(_, _),
 		Queue1 = Queue0
 	),
 	rev_map_side_labels(SideLabels, Label, RevMap0, RevMap1),
@@ -1031,7 +1066,7 @@
 				Labels, BlockMap, ParMap, FallIntoParallel)
 		)
 	;
-		Type = teardown(_),
+		Type = teardown(_, _),
 		process_frame_delay(Labels0, BlockMap0,
 			ParMap0, FallIntoParallel0, FramedLabels,
 			FrameSize, Msg, ProcLabel, N0,
@@ -1094,7 +1129,7 @@
 				N2 = N1
 			)
 		;
-			FallThroughType = teardown(_),
+			FallThroughType = teardown(_, _),
 			MaybeFallThrough = yes(FallThrough),
 			BlockMap1 = BlockMap0,
 			set__insert(FallIntoParallel0,
@@ -1153,7 +1188,7 @@
 		N1 = N0,
 		ParMap1 = ParMap0
 	;
-		Type = teardown(_),
+		Type = teardown(_, _),
 		mark_parallel(Label0, Label, ProcLabel, N0, N1,
 			ParMap0, ParMap1)
 	),
@@ -1288,7 +1323,7 @@
 		;
 			error("block with parallel has fall through")
 		),
-		( Type = teardown(Replacement0) ->
+		( Type = teardown(_, Replacement0) ->
 			LabelInstr = label(ParallelLabel)
 				- "non-teardown parallel",
 			Replacement = [LabelInstr | Replacement0],
Index: compiler/handle_options.m
===================================================================
RCS file: /home/mercury1/repository/mercury/compiler/handle_options.m,v
retrieving revision 1.24
diff -u -r1.24 handle_options.m
--- handle_options.m	1997/07/16 06:22:59	1.24
+++ handle_options.m	1997/07/17 00:09:47
@@ -293,10 +293,11 @@
 		[]
 	),
 	
-	% --optimize-frames implies --optimize-labels
+	% --optimize-frames requires --optimize-labels and --optimize-jumps
 	globals__io_lookup_bool_option(optimize_frames, OptFrames),
 	( { OptFrames = yes } ->
-		globals__io_set_option(optimize_labels, bool(yes))
+		globals__io_set_option(optimize_labels, bool(yes)),
+		globals__io_set_option(optimize_jumps, bool(yes))
 	;
 		[]
 	).
cvs diff: Diffing compiler/notes
cvs diff: Diffing doc
cvs diff: Diffing extras
cvs diff: Diffing extras/cgi
cvs diff: Diffing extras/complex_numbers
cvs diff: Diffing extras/complex_numbers/samples
cvs diff: Diffing extras/complex_numbers/tests
cvs diff: Diffing library
cvs diff: Diffing lp_solve
cvs diff: Diffing lp_solve/lp_examples
cvs diff: Diffing profiler
cvs diff: Diffing runtime
cvs diff: Diffing runtime/machdeps
cvs diff: Diffing samples
cvs diff: Diffing samples/c_interface
cvs diff: Diffing samples/c_interface/c_calls_mercury
cvs diff: Diffing samples/c_interface/cplusplus_calls_mercury
cvs diff: Diffing samples/c_interface/mercury_calls_c
cvs diff: Diffing samples/c_interface/mercury_calls_cplusplus
cvs diff: Diffing samples/diff
cvs diff: Diffing scripts
cvs diff: Diffing tests
cvs diff: Diffing tests/benchmarks
cvs diff: Diffing tests/general
cvs diff: Diffing tests/hard_coded
cvs diff: Diffing tests/invalid
cvs diff: Diffing tests/misc_tests
cvs diff: Diffing tests/valid
cvs diff: Diffing tests/warnings
cvs diff: Diffing tools
cvs diff: Diffing trial
cvs diff: Diffing util
Previous message: diff: runtime/memory.c bug fix
Next message: [m-dev.] bug fix to frameopt
Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
More information about the developers mailing list