Diff of /sml/trunk/src/MLRISC/x86/mltree/x86-fp.sml

Parent Directory | Revision Log | Patch

	revision 909, Fri Aug 24 17:48:53 2001 UTC	revision 925, Fri Sep 14 15:26:29 2001 UTC
#	Line 1	Line 1
1	(*	(* x86-fp.sml
2		*
3		* COPYRIGHT (c) 2001 Bell Labs, Lucent Technologies
4		*
5	* This phase takes a cluster with pseudo x86 fp instructions, performs	* This phase takes a cluster with pseudo x86 fp instructions, performs
6	* liveness analysis to determine their live ranges, and rewrite the	* liveness analysis to determine their live ranges, and rewrite the
7	* program into the correct stack based code.	* program into the correct stack based code.
#	Line 56	Line 59
59	val debug = false        (* set this to true to debug this module	val debug = false        (* set this to true to debug this module
60	* set this to false for production use.	* set this to false for production use.
61	*)	*)
62	val debugLiveness = false (* debug liveness analysis *)	val debugLiveness = true (* debug liveness analysis *)
63	val debugDead = false     (* debug dead code removal *)	val debugDead = false     (* debug dead code removal *)
64	val sanityCheck = false	val sanityCheck = true
65	in	in
66	functor X86FP	functor X86FP
67	(structure X86Instr  : X86INSTR	(structure X86Instr  : X86INSTR
68	structure X86Props  : INSN_PROPERTIES where I = X86Instr	structure X86Props  : INSN_PROPERTIES where I = X86Instr
69	structure Flowgraph : CONTROL_FLOW_GRAPH where I = X86Instr	structure Flowgraph : CONTROL_FLOW_GRAPH where I = X86Instr
70	structure Liveness  : LIVENESS where CFG.I = X86Instr	structure Liveness  : LIVENESS where CFG = Flowgraph
71	structure Asm       : INSTRUCTION_EMITTER where I = X86Instr and P = Flowgraph.P	structure Asm       : INSTRUCTION_EMITTER where I = X86Instr and P = Flowgraph.P
72	) : CFG_OPTIMIZATION =	) : CFG_OPTIMIZATION =
73	struct	struct
74	structure CFG = Flowgraph	structure CFG = Flowgraph
75		structure G  = Graph
76	structure I  = X86Instr	structure I  = X86Instr
77	structure T  = I.T	structure T  = I.T
78	structure P  = X86Props	structure P  = X86Props
#	Line 79	Line 83
83	structure An = Annotations	structure An = Annotations
84	structure CB = CellsBasis	structure CB = CellsBasis
85	structure SL = CB.SortedCells	structure SL = CB.SortedCells
86		structure HT = IntHashTable
87
88	type flowgraph = CFG.cfg	type flowgraph = CFG.cfg
89	type an = An.annotations	type an = An.annotations
#	Line 99	Line 104
104	fun x + y = Word.toIntX(Word.+(Word.fromInt x, Word.fromInt y))	fun x + y = Word.toIntX(Word.+(Word.fromInt x, Word.fromInt y))
105	fun x - y = Word.toIntX(Word.-(Word.fromInt x, Word.fromInt y))	fun x - y = Word.toIntX(Word.-(Word.fromInt x, Word.fromInt y))
106
107		fun celllistToCellset l = List.foldr CB.CellSet.add CB.CellSet.empty l
108		fun celllistToString l = CB.CellSet.toString(celllistToCellset l)
109
110		(* Annotation to mark split edges *)
111		exception TargetMovedTo of G.node_id
112
113	(*-----------------------------------------------------------------------	(*-----------------------------------------------------------------------
114	* Primitive instruction handling routines	* Primitive instruction handling routines
115	*-----------------------------------------------------------------------*)	*-----------------------------------------------------------------------*)
#	Line 154	Line 165
165	List.foldr (fn (r,"") => fregToString r |	List.foldr (fn (r,"") => fregToString r |
166	(r,s) => fregToString r^" "^s) "" s	(r,s) => fregToString r^" "^s) "" s
167
168	(*   fun blknumOf(F.BBLOCK{blknum, ...}) = blknum *)	fun blknumOf(CFG.BLOCK{id, ...}) = id
169
170	(*-----------------------------------------------------------------------	(*-----------------------------------------------------------------------
171	* A stack datatype that mimics the x86 floating point stack	* A stack datatype that mimics the x86 floating point stack
#	Line 390	Line 401
401	*     When necessary, split critical edges.	*     When necessary, split critical edges.
402	*  5. Sacrifice a goat to make sure things don't go wrong.	*  5. Sacrifice a goat to make sure things don't go wrong.
403	*-----------------------------------------------------------------------*)	*-----------------------------------------------------------------------*)
404	fun run _ = error "not implemented "	fun run(Cfg as G.GRAPH cfg) =
405	(*	let
406	fun run(cluster as F.CLUSTER{blocks, blkCounter, ...}) =	val numberOfBlks = #capacity cfg ()
407	let val getCell = C.getCellsByKind CB.FP (*extract the fp component of cellset*)	val ENTRY        = List.hd (#entries cfg ())
408		val EXIT         = List.hd (#exits cfg ())
409
410		val getCell = C.getCellsByKind CB.FP
411		(*extract the fp component of cellset*)
412
413	val stTable = A.tabulate(8, fn n => I.ST(C.ST n))	val stTable = A.tabulate(8, fn n => I.ST(C.ST n))
414
#	Line 434	Line 449
449	* P.S. I'm glad I didn't throw away the code liveness code.	* P.S. I'm glad I didn't throw away the code liveness code.
450	*------------------------------------------------------------------*)	*------------------------------------------------------------------*)
451	val defUse = P.defUse CB.FP   (* def/use properties *)	val defUse = P.defUse CB.FP   (* def/use properties *)
452	val _ = Liveness.liveness{defUse=defUse,	val {liveIn=liveInTable, liveOut=liveOutTable} = Liveness.liveness {
453	updateCell=C.updateCellsByKind CB.FP,	defUse=defUse,
454	getCell=getCell,	(* updateCell=C.updateCellsByKind CB.FP, *)
455	blocks=blocks	getCell=getCell
456	}	} Cfg
457	(*------------------------------------------------------------------	(*------------------------------------------------------------------
458	* Scan the instructions compute the last uses and dead definitions	* Scan the instructions compute the last uses and dead definitions
459	* at each program point.  Ideally we can do this during the code	* at each program point.  Ideally we can do this during the code
#	Line 464	Line 479
479	else ()	else ()
480	in  scan(instrs, live, (last,dead)::lastUse)	in  scan(instrs, live, (last,dead)::lastUse)
481	end	end
482	val liveOutSet = SL.uniq(getCell (!liveOut))	val liveOutSet = SL.uniq liveOut
483	val _ =	val _ =
484	if debug andalso debugLiveness then	if debug andalso debugLiveness then
485	print("LiveOut("^i2s blknum^") = "^	print("LiveOut("^i2s blknum^") = "^
#	Line 482	Line 497
497	val useTbl      = A.array(n,~1) (* table for marking uses *)	val useTbl      = A.array(n,~1) (* table for marking uses *)
498
499	(* %fp register bindings before and after a basic block *)	(* %fp register bindings before and after a basic block *)
500	val bindingsIn   = A.array(!blkCounter, NONE)	val bindingsIn   = A.array(numberOfBlks, NONE)
501	val bindingsOut  = A.array(!blkCounter, NONE)	val bindingsOut  = A.array(numberOfBlks, NONE)
502	val stampCounter = ref ~4096	val stampCounter = ref ~4096
503
504	(* Edges that need splitting *)	(* Edges that need splitting *)
#	Line 497	Line 512
512	* Code for handling bindings between basic block	* Code for handling bindings between basic block
513	*------------------------------------------------------------------*)	*------------------------------------------------------------------*)
514
515	fun splitEdge(targetId, source, target) =	fun splitEdge(title, source, target, e) =
516	(if debug andalso !traceOn then	(if debug andalso !traceOn then
517	pr("SPLITTING "^i2s(blknumOf source)^"->"^	pr(title^" SPLITTING "^i2s source^"->"^ i2s target^"\n")
	i2s(blknumOf target)^"\n")
518	else ();	else ();
519	addEdgesToSplit(targetId,	addEdgesToSplit(target,(source,target,e)::lookupEdgesToSplit target)
	(source,target)::lookupEdgesToSplit targetId)
520	)	)
521
522	(* Given a cellset, return a sorted and unique	(* Given a cellset, return a sorted and unique
523	* list of elements with all non-physical registers removed	* list of elements with all non-physical registers removed
524	*)	*)
525	fun removeNonPhysical cellSet =	fun removeNonPhysical celllist =
526	let fun loop([], S) = SL.return(SL.uniq S)	let fun loop([], S) = SL.return(SL.uniq S)
527	| loop(f::fs, S) =	| loop(f::fs, S) =
528	let val fx = CB.registerNum f	let val fx = CB.registerNum f
529	in  loop(fs,if fx <= 7 then f::S else S)	in  loop(fs,if fx <= 7 then f::S else S)
530	end	end
531	in  loop(getCell(!cellSet), [])	in  loop(celllist, [])
532	end	end
533
534	(* Given a sorted and unique list of registers,	(* Given a sorted and unique list of registers,
#	Line 681	Line 694
694	(*------------------------------------------------------------------	(*------------------------------------------------------------------
695	* Magic for inserting shuffle code at the end of a basic block	* Magic for inserting shuffle code at the end of a basic block
696	*------------------------------------------------------------------*)	*------------------------------------------------------------------*)
697	fun shuffleOut(stackOut, insns, b, block, succ, liveOut) =	fun shuffleOut(stackOut, insns, b, block, liveOut) =
698	let val liveOut = removeNonPhysical liveOut	let
699		val liveOut = removeNonPhysical(liveOut)
700
701	(* Generate code that remove unnecessary values *)	(* Generate code that remove unnecessary values *)
702	val code = removeDeadValues(stackOut, liveOut, [])	val code = removeDeadValues(stackOut, liveOut, [])
#	Line 708	Line 722
722	* from the edge with the highest frequency.	* from the edge with the highest frequency.
723	*)	*)
724	fun find([], _, id, best) = (id, best)	fun find([], _, id, best) = (id, best)
725	| find((F.BBLOCK{blknum, insns, ...},freq)::edges,	| find((_, target, _)::edges, highestFreq, id, best) =
726	highestFreq, id, best) =	let val CFG.BLOCK{freq, ...} = #node_info cfg target
727	if blknum = b+1 then (blknum, A.sub(bindingsIn, blknum))	in  if target = b+1 then (target, A.sub(bindingsIn, target))
728	else (case A.sub(bindingsIn, blknum) of	else (case A.sub(bindingsIn, target) of
729	NONE => find(edges, highestFreq, id, best)	NONE => find(edges, highestFreq, id, best)
730	| this as SOME stack =>	| this as SOME stack =>
731	if highestFreq < !freq then	if highestFreq < !freq then
732	find(edges, !freq, blknum, this)	find(edges, !freq, target, this)
733	else	else
734	find(edges, highestFreq, id, best)	find(edges, highestFreq, id, best)
735	)	)
736	| find(_::edges, highestFreq, id, best) =	end
	find(edges, highestFreq, id, best)
737
738	fun splitAllEdgesExcept([], succBlock) = ()	(*
739	| splitAllEdgesExcept((next as F.BBLOCK{blknum, ...},_)::edges,	* Split all edges source->target except omitThis.
740	succBlock) =	*)
741	(if blknum <> succBlock andalso blknum <= b	fun splitAllEdgesExcept([], omitThis) = ()
742	then splitEdge(blknum,block,next) else ();	| splitAllEdgesExcept((source,target,e)::edges, omitThis) =
743	splitAllEdgesExcept(edges, succBlock)	if target = EXIT then error "can't split exit edge!"
744	)	else
745	| splitAllEdgesExcept((F.EXIT _,_)::_, _) =	(if target <> omitThis andalso
746	error "can't split exit edge!"	target <= b andalso          (* XXX *)
747	| splitAllEdgesExcept(_::edges, succBlock) =	target <> ENTRY
748	splitAllEdgesExcept(edges, succBlock)	then splitEdge("ShuffleOut",source,target,e) else ();
749		splitAllEdgesExcept(edges, omitThis)
750		)
751
	in  case !succ of
	[]             => matchLiveOut()
	| [(F.EXIT _,_)] => matchLiveOut()
	| succ =>
752	(* Just one successor;	(* Just one successor;
753	* try to match the bindings of the successor if it exist.	* try to match the bindings of the successor if it exist.
754	*)	*)
755		fun matchIt succ =
756	let val (succBlock, target) = find(succ, ~1, ~1, NONE)	let val (succBlock, target) = find(succ, ~1, ~1, NONE)
757	in  splitAllEdgesExcept(succ, succBlock);	in  splitAllEdgesExcept(succ, succBlock);
758	case target of	case target of
759	SOME stackIn => match(stackOut, stackIn)	SOME stackIn => match(stackOut, stackIn)
760	| NONE => done(stackOut,insns,code)	| NONE => done(stackOut,insns,code)
761	end	end
762
763		in  case #out_edges cfg b of
764		[] => matchLiveOut()
765		| succ as [(_,target,_)] =>
766		if target = EXIT then matchLiveOut()
767		else matchIt succ
768		| succ => matchIt succ
769	end (* shuffleOut *)	end (* shuffleOut *)
770
771	(*------------------------------------------------------------------	(*------------------------------------------------------------------
772	* Compute the initial fp stack bindings for basic block b.	* Compute the initial fp stack bindings for basic block b.
773	*------------------------------------------------------------------*)	*------------------------------------------------------------------*)
774	fun shuffleIn(b, block, pred, liveIn) =	fun shuffleIn(b, block, liveIn) =
775	let val liveInSet = removeNonPhysical liveIn	let
776		val liveInSet = removeNonPhysical liveIn
777
778	(* With multiple predecessors, find out which one we	(* With multiple predecessors, find out which one we
779	* should connect to.   Choose the one from the block that	* should connect to.   Choose the one from the block that
#	Line 761	Line 781
781	* from the edge with the highest frequency.	* from the edge with the highest frequency.
782	*)	*)
783	fun find([], _, best) = best	fun find([], _, best) = best
784	| find((F.BBLOCK{blknum, insns, ...},freq)::edges,	| find((source, _, _)::edges, highestFreq, best) =
785	highestFreq, best) =	let val CFG.BLOCK{freq, data, ...} = #node_info cfg source
786	(case A.sub(bindingsOut, blknum) of	in  case A.sub(bindingsOut, source) of
787	NONE => find(edges, highestFreq, best)	NONE => find(edges, highestFreq, best)
788	| this as SOME stack =>	| this as SOME stack =>
789	if blknum = b-1 then (* falls into b *)	if source = b-1 andalso List.null(!data)
790		then (* falls into b *)
791	this	this
792	else if highestFreq < !freq then	else if highestFreq < !freq then
793	find(edges, !freq, this)	find(edges, !freq, this)
794	else	else
795	find(edges, highestFreq, best)	find(edges, highestFreq, best)
796	)	end
	| find(_::edges, highestFreq, best) =
	find(edges, highestFreq, best)
797
798	fun splitAllDoneEdges [] = ()	fun splitAllDoneEdges [] = ()
799	| splitAllDoneEdges	| splitAllDoneEdges ((source, target, e)::edges) =
800	((prev as F.BBLOCK{blknum, ...},_)::edges) =	(if source < b andalso
801	(if blknum < b	source <> ENTRY andalso
802	then splitEdge(b,prev,block) else ();	source <> EXIT
803		then splitEdge("ShuffleIn", source, target, e) else ();
804	splitAllDoneEdges edges	splitAllDoneEdges edges
805	)	)
	| splitAllDoneEdges(_::edges) = splitAllDoneEdges edges
806
807	(* The initial stack bindings are determined by the live set.	(* The initial stack bindings are determined by the live set.
808	* No compensation code is needed.	* No compensation code is needed.
#	Line 793	Line 812
812	case liveInSet of	case liveInSet of
813	[] => ST.stack0	[] => ST.stack0
814	| _  =>	| _  =>
815	(pr("liveIn="^CB.CellSet.toString (!liveIn)^"\n");	(pr("liveIn="^celllistToString liveIn^"\n");
816	newStack liveInSet	newStack liveInSet
817	)	)
818	val stackOut = ST.copy stackIn	val stackOut = ST.copy stackIn
819	in  (stackIn, stackOut, [])	in  (stackIn, stackOut, [])
820	end	end
821
822		val pred = #in_edges cfg b
823
824	val (stackIn, stackOut, code) =	val (stackIn, stackOut, code) =
825	case find(!pred, ~1, NONE) of	case find(pred, ~1, NONE) of
826	NONE => (splitAllDoneEdges(!pred); fromLiveIn())	NONE => (splitAllDoneEdges(pred); fromLiveIn())
827	| SOME stackIn' =>	| SOME stackIn' =>
828	(case !pred of	(case pred of
829	[_] => (* one predecessor *)	[_] => (* one predecessor *)
830	(* Use the bindings as from the previous block	(* Use the bindings as from the previous block
831	* We first have to deallocate all unused values.	* We first have to deallocate all unused values.
#	Line 813	Line 834
834	(* Clean the stack of unused entries *)	(* Clean the stack of unused entries *)
835	val code = removeDeadValues(stackOut, liveInSet, [])	val code = removeDeadValues(stackOut, liveInSet, [])
836	in  (stackIn', stackOut, code) end	in  (stackIn', stackOut, code) end
837	|  _ => (* more than one predecessors *)	|  pred => (* more than one predecessors *)
838	let val stackIn = ST.copy stackIn'	let val stackIn = ST.copy stackIn'
839	val code = removeDeadValues(stackIn, liveInSet, [])	val code = removeDeadValues(stackIn, liveInSet, [])
840	val stackOut = ST.copy stackIn	val stackOut = ST.copy stackIn
#	Line 822	Line 843
843	*)	*)
844	case code of	case code of
845	[] => ()	[] => ()
846	|  _  => splitAllDoneEdges(!pred);	|  _  => splitAllDoneEdges(pred);
847	(stackIn, stackOut, [])	(stackIn, stackOut, [])
848	end	end
849	)	)
#	Line 834	Line 855
855	(*------------------------------------------------------------------	(*------------------------------------------------------------------
856	* Code for patching up critical edges.	* Code for patching up critical edges.
857	* The trick is finding a good place to insert the critical edges.	* The trick is finding a good place to insert the critical edges.
858	* The cluster representation is very hard to work with.	* Let's call an edge x->y that requires compensation
859		* code c to be inserted an candidate edge.  We write this as x->y(c)
860		*
861		* Here are the heuristics that we use to improve the final code:
862		*
863		*    1. Given two candidate edges a->x(c1) and b->x(c2) where c1=c2
864		*       then we can merge the two copies of compensation code.
865		*       This is quite common.  This generalizes to any number of edges.
866		*
867		*    2. Given two candidate edges a->x(c1) and b->x(c2) and where
868		*       c1 and c2 are pops, we can partially share c1 and c2.
869		*       Currently, I think I only recognize this case when
870		*       x has no fp registers live-in.
871		*
872		*    3. Given two candidate edges a->x(c1) and b->x(c2),
873		*       if a->x has a higher frequency then put the compensation
874		*       code in front of x (so that it falls through into x)
875		*       whenever possible.
876		*
877		* As you can see, the voodoo is strong here.
878		*
879		* The routine has two main phases:
880		*    1. Determine the compensation code by applying the heuristics
881		*       above.
882		*    2. Then insert them and rebuild the cfg by renaming all block
883		*       ids.  This is currently necessary to keep the layout order
884		*       consistent with the order of the id.
885	*------------------------------------------------------------------*)	*------------------------------------------------------------------*)
886	fun repairCriticalEdges	fun repairCriticalEdges(Cfg as G.GRAPH cfg) =
	(cluster as F.CLUSTER{blocks, entry, exit, annotations,
	blkCounter}) =
887	let (* Data structure for recording critical edge splitting info *)	let (* Data structure for recording critical edge splitting info *)
888	datatype compensationCode =	datatype compensationCode =
889	NEWEDGE of	NEWEDGE of
890	{label:L.label,          (* label of new block *)	{label:L.label,          (* label of new block *)
891	preds:F.block list ref, (* predecessors *)	entries:CFG.edge list ref,   (* edges going into this code *)
892	code:I.instruction list,(* code *)	code:I.instruction list,(* code *)
893	comment:an	comment:an
894	}	}
#	Line 867	Line 912
912	fun lookupRepairCode' b =	fun lookupRepairCode' b =
913	getOpt(IntHashTable.find repairCodeTable' b,[])	getOpt(IntHashTable.find repairCodeTable' b,[])
914
915	(* Mapping from block id -> labels *)	(* Does the given block falls thru from the previous block?
916	val labelTable  = IntHashTable.mkTable(32, Nothing)	* If the previous block is ENTRY then also consider this to be true
917	val addLabel    = IntHashTable.insert labelTable	*)
918	fun lookupLabel b = getOpt(IntHashTable.find labelTable b, [])	fun isFallsThru b =
919		case #in_edges cfg b of
920	(* Scan code and insert labels *)	[(b',_,_)] => (case CFG.fallsThruTo(Cfg,b') of
921	fun insertLabels([], []) = ()	SOME b'' => b'' = b
922	| insertLabels(labels, []) = error "orphan labels"	| NONE => b' = ENTRY
923	| insertLabels(labels, F.LABEL l::blocks) =	)
924	insertLabels(l::labels, blocks)	| _ => false
	| insertLabels(labels, (b as F.BBLOCK{blknum,...})::blocks) =
	(addLabel(blknum, labels); insertLabels([], blocks))
	| insertLabels(_, _::blocks) = insertLabels([], blocks)
	(* skip labels to pseudo ops *)
	val _ = insertLabels([], blocks)
	(* Does the block falls thru from the previous block? *)
	fun isFallsThru(F.BBLOCK{pred, blknum=j, ...}) =
	let fun loop((F.BBLOCK{blknum=i,...},_)::rest) =
	i+1 = j orelse loop rest
	| loop((F.ENTRY _,_)::_) = true
	| loop(_) = false
	in  loop(!pred)
	end
	| isFallsThru _ = false
925
926	(* Create jump instruction to a block *)	(* Create jump instruction to a block *)
927	fun jump(F.BBLOCK{blknum,...}) =	fun jump(CFG.BLOCK{labels, ...}) =
928	(case lookupLabel blknum of	(case !labels of
929	[]   => error "no label to target of critical edge!"	[]   => error "no label to target of critical edge!"
930	| l::_ => P.jump l	| l::_ => P.jump l
931	)	)
	| jump _ = error "jump"
932
933	(*	(*
934	* Special case: target block has stack depth of 0.	* Special case: target block has stack depth of 0.
#	Line 909	Line 937
937	* all the critical edges.	* all the critical edges.
938	*)	*)
939	fun genPoppingCode(_, []) = ()	fun genPoppingCode(_, []) = ()
940	| genPoppingCode(targetId, edges as (_,target)::_) =	| genPoppingCode(targetBlk, edges as (_,target,_)::_) =
941	let val preds =	let val entries =
942	map (fn (source, _) =>	map (fn edge as (source, _, _) =>
943	let val sourceId = blknumOf source	let val n  = ST.depth(valOf(A.sub(bindingsOut,source)))
944	val SOME stackOut = A.sub(bindingsOut,sourceId)	in  (n, edge) end
	val n  = ST.depth stackOut
	in  (n, source) end
945	) edges	) edges
946
947	(* Ordered by increasing stack height *)	(* Ordered by increasing stack height *)
948	val preds =	val entries =
949	ListMergeSort.sort (fn ((n,_),(m,_)) => n > m) preds	ListMergeSort.sort (fn ((n,_),(m,_)) => n > m) entries
950
951	val relocate = isFallsThru target	val relocate = isFallsThru target
952
#	Line 929	Line 956
956	fun makeCode(popCount, rest) =	fun makeCode(popCount, rest) =
957	let val code = pop(popCount, [])	let val code = pop(popCount, [])
958	in  case rest of	in  case rest of
959	[] => if relocate then jump target::code	[] => if relocate then
960		jump(#node_info cfg target)::code
961	else code	else code
962	| _  => code	| _  => code
963	end	end
#	Line 938	Line 966
966	* have to pop the same number of elements	* have to pop the same number of elements
967	*)	*)
968	fun gen([], h, code) = code	fun gen([], h, code) = code
969	| gen((n,b)::rest, _, []) =	| gen((n,e)::rest, _, []) =
970	gen(rest, n,	gen(rest, n,
971	[NEWEDGE{label=L.newLabel "",preds=ref [b],	[NEWEDGE{label=L.anon(),
972	code=makeCode(n,rest), comment=cleanup}])	entries=ref [e],
973	| gen((n,b)::rest, h, all as (NEWEDGE{preds, ...}::_)) =	code=makeCode(n,rest),
974		comment=cleanup
975		}
976		])
977		| gen((n,e)::rest, h, all as (NEWEDGE{entries, ...}::_)) =
978	gen(rest,h,	gen(rest,h,
979	if n = h then	if n = h then
980	(preds := b :: !preds; all)	(entries := e :: !entries; all)
981	else	else
982	NEWEDGE{label=L.newLabel "", preds=ref [b],	NEWEDGE{label=L.anon(),
983		entries=ref [e],
984	code=makeCode(n-h,rest),	code=makeCode(n-h,rest),
985	comment=cleanup}::all	comment=cleanup
986		}::all
987	)	)
988	val repairCode = gen(preds, 0, [])	val repairCode = gen(entries, 0, [])
989	in  (if relocate then addRepairCode' else addRepairCode)	in  (if relocate then addRepairCode' else addRepairCode)
990	(targetId, repairCode)	(target, repairCode)
991	end	end
992
993	(* The general case:	(* The general case:
994	*   Remove dead values, then	*   Remove dead values, then
995	*   Shuffle.	*   Shuffle.
996	*)	*)
997	fun genRepairCode(targetId, stackIn, edges) =	fun genRepairCode(target, targetBlk, stackIn, edges) =
998	let val repairList = ref []	let val repairList = ref []
999	val repairCount = ref 0	val repairCount = ref 0
1000	val SOME stackIn = A.sub(bindingsIn, targetId)	val SOME stackIn = A.sub(bindingsIn, target)
1001	fun repair(source, target) =	fun repair(edge as (source, _, _)) =
1002	let val F.BBLOCK{blknum=sourceId, ...} = source	let val SOME stackOut' = A.sub(bindingsOut, source)
	val SOME stackOut' = A.sub(bindingsOut, sourceId)
1003	fun createNewRepairEdge() =	fun createNewRepairEdge() =
1004	let val stackOut = ST.copy stackOut'	let val stackOut = ST.copy stackOut'
1005	val F.BBLOCK{liveIn, ...} = target	val liveIn = IntHashTable.lookup liveInTable target
1006	val liveInSet = removeNonPhysical liveIn	val liveInSet = removeNonPhysical liveIn
1007	val _ =	val _ =
1008	if debug then	if debug then
1009	pr("LiveIn = "^	pr("LiveIn = "^celllistToString liveIn^"\n")
	CB.CellSet.toString (!liveIn)^
	"\n")
1010	else ()	else ()
1011
1012	(* deallocate unused values *)	(* deallocate unused values *)
#	Line 985	Line 1016
1016	fun addNewEdge() =	fun addNewEdge() =
1017	let (* Do we need to relocate this block? *)	let (* Do we need to relocate this block? *)
1018	val relocate = !repairCount > 0 orelse	val relocate = !repairCount > 0 orelse
1019	isFallsThru target andalso	isFallsThru target
1020	sourceId + 1 <> targetId	andalso source + 1 <> target
1021
1022	(* add a jump to the target block *)	(* add a jump to the target block *)
1023	val code = if relocate then jump target::code	val code = if relocate then jump targetBlk::code
1024	else code	else code
1025
1026	val repairCode =	val repairCode =
1027	NEWEDGE{label=L.newLabel "",	NEWEDGE{label=L.anon(),
1028	preds=ref [source],	entries=ref [edge],
1029	code=code, comment=critical}	code=code,
1030		comment=critical
1031		}
1032	in  repairCount := !repairCount + 1;	in  repairCount := !repairCount + 1;
1033	repairList := (repairCode, stackOut')	repairList := (repairCode, stackOut')
1034	:: !repairList;	:: !repairList;
1035	if relocate then	if relocate then
1036	addRepairCode'(targetId,	addRepairCode'(target,
1037	repairCode::lookupRepairCode' targetId)	repairCode::lookupRepairCode' target)
1038	else	else
1039	addRepairCode(targetId,	addRepairCode(target,
1040	repairCode::lookupRepairCode targetId)	repairCode::lookupRepairCode target)
1041		end
1042		in  case #out_edges cfg source of
1043		[(_,j,_)] =>
1044		if j = target then (*insert code at predecessor*)
1045		let val CFG.BLOCK{insns,...} =
1046		#node_info cfg source
1047		in  insns := insertAtEnd(!insns, code)
1048	end	end
	in  case source of
	F.BBLOCK{succ=ref [(F.BBLOCK{blknum=j,...},_)],
	insns, ...} =>
	if j = targetId then (*insert code at predecessor*)
	insns := insertAtEnd(!insns, code)
1049	else	else
1050	addNewEdge()	addNewEdge()
1051	| _ => addNewEdge()	| _ => addNewEdge()
1052	end	end
1053
1054	fun shareRepairEdge [] = false	fun shareRepairEdge [] = false
1055	| shareRepairEdge((NEWEDGE{preds,...},stackOut'')::rest) =	| shareRepairEdge
1056		((NEWEDGE{entries,...},stackOut'')::rest) =
1057	if ST.equal(stackOut'', stackOut') then	if ST.equal(stackOut'', stackOut') then
1058	(preds := source :: !preds; true)	(entries := edge :: !entries; true)
1059	else shareRepairEdge rest	else shareRepairEdge rest
1060
1061	in  if shareRepairEdge(!repairList) then ()	in  if shareRepairEdge(!repairList) then ()
#	Line 1029	Line 1065
1065	end	end
1066
1067	(*	(*
1068	* Code to split critical edges entering block targetId	* Code to split critical edges entering block target
1069	*)	*)
1070	fun split(targetId, edges) =	fun split(target, edges) =
1071	let val SOME stackIn = A.sub(bindingsIn,targetId)	let val SOME stackIn = A.sub(bindingsIn,target)
1072	fun log(source, target) =	fun log(s, t, e) =
1073	let val s = blknumOf source	let val SOME stackOut = A.sub(bindingsOut,s)
	val t = blknumOf target
	val SOME stackOut = A.sub(bindingsOut,s)
1074	in  pr("SPLIT "^i2s s^"->"^i2s t^" "^	in  pr("SPLIT "^i2s s^"->"^i2s t^" "^
1075	ST.stackToString stackOut^"->"^	ST.stackToString stackOut^"->"^
1076	ST.stackToString stackIn^"\n")	ST.stackToString stackIn^"\n")
1077	end	end
1078	val _ = if debug andalso !traceOn then app log edges else ()	val _ = if debug andalso !traceOn then app log edges else ()
1079	in  if ST.depth stackIn = 0 then genPoppingCode(targetId, edges)	val targetBlk = #node_info cfg target
1080	else genRepairCode(targetId, stackIn, edges)	in  if ST.depth stackIn = 0 then genPoppingCode(targetBlk,edges)
1081		else genRepairCode(target, targetBlk, stackIn, edges)
1082	end	end
1083
1084	(* Renumber all the blocks and insert compensation code at the
1085		(*
1086		* Create a new empty cfg with the same graph info as the old one.
1087		*)
1088		val Cfg' as G.GRAPH cfg' = CFG.cfg (#graph_info cfg)
1089
1090		(*
1091		* Renumber all the blocks and insert compensation code at the
1092	* right places.	* right places.
1093	*)	*)
1094	fun renumberBlocks() =	fun renumberBlocks() =
1095	let val labelTbl = IntHashTable.mkTable(32, Nothing)	let (* Mapping from label to new node ids *)
1096	val addLabel = IntHashTable.insert labelTbl	val labelMap = HashTable.mkTable (L.hash,L.same) (32, Nothing)
1097	fun insertLabel(L.Label{id, ...},block) = addLabel(id, block)	val mapLabelToId = HashTable.insert labelMap
1098
1099	val entries = ref []	(* Mapping from old id to new id *)
1100	val exits   = ref []	val idMap = IntHashTable.mkTable (32, Nothing)
1101		val mapOldIdToNewId = IntHashTable.insert idMap
1102	(* retarget the branch of block *)	val oldIdToNewId = IntHashTable.lookup idMap
1103	fun retarget(I.JMP(I.ImmedLabel(T.LABEL _), [_])::rest, l) =
1104	I.JMP(I.ImmedLabel(T.LABEL l), [l])::rest	(* Retarget a jump instruction to label l *)
1105	| retarget(I.JCC{cond,opnd=I.ImmedLabel(T.LABEL _)}::rest,l)=	fun retargetJump(I.JMP(I.ImmedLabel(T.LABEL _), [_]), l) =
1106	I.JCC{cond=cond,opnd=I.ImmedLabel(T.LABEL l)}::rest	I.JMP(I.ImmedLabel(T.LABEL l), [l])
1107	| retarget(_,l) = error "retarget"	| retargetJump(I.JCC{cond,opnd=I.ImmedLabel(T.LABEL _)},l)=
1108		I.JCC{cond=cond,opnd=I.ImmedLabel(T.LABEL l)}
1109	(* Translate repair code to actual block *)	| retargetJump(I.ANNOTATION{i,a},l) =
1110	fun transRepair(n, [], blocks) = (n, blocks)	I.ANNOTATION{i=retargetJump(i,l),a=a}
1111	| transRepair(n, NEWEDGE{label, preds, code, comment}::rest,	| retargetJump(_,l) = error "retargetJump"
1112	blocks) =
1113	let val blocks = F.LABEL label::blocks	(*
1114	val this = F.BBLOCK{blknum=n, freq=ref 0,	* Given a candidate edge, generate compensation code.
1115	pred=ref [],	*)
1116	succ=ref [],	fun transRepair(n, []) = n
1117	annotations=ref comment,	| transRepair(n, NEWEDGE{label,entries,code,comment}::rest) =
1118	liveIn=ref C.empty,	let val this =
1119	liveOut=ref C.empty,	CFG.BLOCK{id=n,
1120	insns=ref code}	kind=CFG.NORMAL,
1121	fun retargetBlock(F.BBLOCK{insns, ...}) =	freq=ref 0, (* XXX Wrong frequency! *)
1122	insns := retarget(!insns, label)	data=ref [],
1123	| retargetBlock _ = ()	labels=ref [label],
1124		insns=ref code,
1125		annotations=ref comment
1126		}
1127
1128		(*
1129		* Update the instructions to predecessors of this edge.
1130		*)
1131		fun retarget(CFG.BLOCK{kind=CFG.START,...}) = ()
1132		| retarget(CFG.BLOCK{insns as ref(jmp::rest), ...}) =
1133		insns := retargetJump(jmp, label)::rest
1134		| retarget _ = error "retarget"
1135
1136		fun retargetEntries(pred,_,CFG.EDGE{a,...}) =
1137		(retarget(#node_info cfg pred);
1138		a := TargetMovedTo n :: !a
1139		)
1140
1141	in  if debug andalso !traceOn then	in  if debug andalso !traceOn then
1142	pr("Inserting critical edge at block "^i2s n^" "^	pr("Inserting critical edge at block "^i2s n^" "^
1143	L.nameOf label^"\n")	L.toString label^"\n")
1144	else ();	else ();
1145	insertLabel(label, this);	#add_node cfg' (n, this);  (* insert block *)
1146	app retargetBlock (!preds);	mapLabelToId(label, n);
1147	transRepair(n+1, rest, this::blocks)	app retargetEntries (!entries);
1148		transRepair(n+1, rest)
1149	end	end
1150
1151	fun renumber(n, [], pseudoOps, repairCode', blocks) =	(*
1152	let val (n, blocks) = transRepair(n, repairCode', blocks)	* Renumber all the blocks and insert repair code.
1153	val blocks      = pseudoOps @ blocks	*)
1154	in  (n, rev blocks)	fun renumber(n, [], repairCode') =  transRepair(n, repairCode')
1155	end	| renumber(n, (blknum, block as
1156	| renumber(n, (block as	CFG.BLOCK{kind,annotations,insns,freq,
1157	F.BBLOCK{blknum,annotations,insns,freq,	data, labels, ...})::rest,
1158	pred,succ,liveIn,liveOut,...})::rest,	repairCode') =
	pseudoOps, repairCode', blocks) =
1159	let (* If we have outstanding repair code and this is	let (* If we have outstanding repair code and this is
1160	* NOT a fallsthru entry, then insert them here.	* NOT a fallsthru entry, then insert them here.
1161	*)	*)
1162	val (n, blocks, repairCode') =	val (n, repairCode') =
1163	case repairCode' of	case repairCode' of
1164	[] => (n, blocks, [])	[] => (n, [])
1165	| _  => if isFallsThru block then	| _  => if isFallsThru blknum then
1166	(n, blocks, repairCode')	(n, repairCode')
1167	else	else
1168	let val (n, blocks) =	(transRepair(n, repairCode'), [])
	transRepair(n, repairCode', blocks)
	in (n, blocks, [])
	end
1169
1170	(*  Insert non-relocatable repair code *)	(*  Insert non-relocatable repair code *)
1171	val repairCode = lookupRepairCode blknum	val repairCode = lookupRepairCode blknum
1172	val (n, blocks) = transRepair(n, repairCode, blocks)	val n = transRepair(n, repairCode)
1173
1174	(*  Create this block *)	(*  Create this block *)
1175	val this = F.BBLOCK{blknum=n,annotations=annotations,	val this = CFG.BLOCK{id=n,
1176	freq=freq, insns=insns,	kind=kind,
1177	pred=ref [], succ=ref [],	freq=freq,
1178	liveIn=liveIn,liveOut=liveOut	data=data,
1179		labels=labels,
1180		insns=insns,
1181		annotations=annotations
1182	}	}
1183
1184	(*  Insert new relocatable repair code *)	(*  Insert new relocatable repair code *)
1185	val repairCode' = repairCode' @	val repairCode' = repairCode' @
1186	lookupRepairCode' blknum	lookupRepairCode' blknum
1187
1188	(*  Insert labels *)	(*  Insert labels that map to this block *)
1189	fun insertLabels((p as F.LABEL l)::ps) =	val _ = app (fn l => mapLabelToId(l, n)) (!labels)
1190	(insertLabel(l, this); insertLabels ps)
1191	| insertLabels(p::ps) = insertLabels ps	(*  Insert block *)
1192	| insertLabels [] = blocks	val _ = #add_node cfg' (n, this)
1193		val _ = mapOldIdToNewId(blknum, n)
1194	val _ = insertLabels pseudoOps
1195		in  case kind of
1196	val blocks = this::pseudoOps @ blocks	CFG.START => #set_entries cfg' [n]
1197		|  CFG.STOP  => #set_exits cfg' [n]
1198	fun addEntry((F.ENTRY _,w)::_) =	|  _         => ();
1199	entries := (this,w):: !entries	renumber(n+1, rest, repairCode')
1200	| addEntry(_::es) = addEntry es	end
1201	| addEntry [] = ()
1202	fun addExit((F.EXIT _,w)::_) =	(* Do all the blocks *)
1203	exits := (this,w) :: !exits	val n = renumber(0, #nodes cfg (), [])
1204	| addExit(_::es) = addExit es
1205	| addExit [] = ()	val [newExit] = #exits cfg' ()
1206
1207	in  addEntry(!pred); (* check if this is an entry *)	(*
1208	addExit(!succ);  (* check if this ia an exit *)	* Given a label, finds out which block it targets.
1209	renumber(n+1, rest, [], repairCode', blocks)	* If not found then it means the block is escaping.
1210	end	*)
1211	| renumber(n, p::rest, pseudoOps, repairCode', blocks) =	val findLabel = HashTable.find labelMap
1212	renumber(n, rest, p::pseudoOps, repairCode', blocks)	fun labelToBlockId l = getOpt(findLabel l, newExit)
1213
1214	val (n, blocks) = renumber(0, blocks, [], [], [])	fun hasJump x =
1215		let val CFG.BLOCK{insns, ...} = #node_info cfg' x
	(* New entry and exits *)
	val F.ENTRY{freq=entryFreq, ...} = entry
	val newEntry = F.ENTRY{blknum=n, freq=entryFreq, succ=entries}
	val n        = n+1
	val F.EXIT{freq=exitFreq, ...} = exit
	val newExit  = F.EXIT{blknum=n, freq=exitFreq, pred=exits}
	val n        = n+1
	val lookupLabel = IntHashTable.find labelTbl
	val lookupLabel =
	fn l => case lookupLabel l of
	SOME b => b
	| NONE   => newExit
	fun addPred b (F.BBLOCK{pred, ...},w) = pred := (b,w) :: !pred
	| addPred b (F.EXIT{pred, ...},w) = pred := (b,w) :: !pred
	| addPred _ _ = error "addPred"
	fun adjustSucc(
	(blk as F.BBLOCK{blknum,insns,succ,pred,...})::rest) =
	let fun follows(F.LABEL _::rest) = follows rest
	| follows((b as F.BBLOCK _)::rest) = (b, ref 0)
	| follows [] = (newExit, ref 0)
	fun succBlocks([], succ) = succ
	| succBlocks(P.ESCAPES::targets, succ) =
	succBlocks(targets, (newExit, ref 0)::succ)
	| succBlocks(P.FALLTHROUGH::targets, succ) =
	succBlocks(targets, follows rest::succ)
	| succBlocks(P.LABELLED(L.Label{id,...})::targets,
	succ) =
	succBlocks(targets, (lookupLabel id, ref 0)::succ)
	fun fallsThru rest = [follows rest]
1216	in  case !insns of	in  case !insns of
1217	[] => succ := fallsThru rest	[] => false
1218		| jmp::_ => P.instrKind jmp = P.IK_JUMP
1219		end
1220
1221		(*
1222		* Now rebuild all the old edges.
1223		* For each edge, makes sure the target hasn't been moved.
1224		*)
1225		fun renameEdge(x, y, e as CFG.EDGE{a,k,w,...}) =
1226		let val x = oldIdToNewId x
1227		val (z, e) =
1228		case !a of
1229		TargetMovedTo z::an =>
1230		let val e =
1231		case k of
1232		(CFG.FALLSTHRU | CFG.BRANCH false) =>
1233		if hasJump x then
1234		CFG.EDGE{a=a, w=w, k=CFG.JUMP}
1235		else e
1236		| _ => e
1237		in  a := an;   (* remove the marker *)
1238		(z, e)
1239		end
1240		|   _ => (oldIdToNewId y, e)
1241		in  #add_edge cfg' (x,z,e)
1242		end
1243
1244		val _ = #forall_edges cfg renameEdge
1245
1246		(*
1247		* Now add new edges x->y where x is a new compensation block
1248		*)
1249		fun addNewEdge(NEWEDGE{label, code, entries, ...}) =
1250		let val x = labelToBlockId label
1251		val (y, k) =
1252		case code of
1253		[] => (x + 1, CFG.FALLSTHRU) (* next block *)
1254	| jmp::_ =>	| jmp::_ =>
1255	case P.instrKind jmp of	if P.instrKind jmp = P.IK_JUMP then
1256	P.IK_JUMP =>	(case P.branchTargets jmp of
1257	succ := succBlocks(P.branchTargets jmp,[])	[P.LABELLED l] => (labelToBlockId l, CFG.JUMP)
1258	| _ => succ := fallsThru rest;	| _ => error "addNewEdge where is the target?"
1259	app (addPred blk) (!succ);	)
1260	adjustSucc rest	else
1261	end	(x + 1, CFG.FALLSTHRU)
1262	| adjustSucc(_::rest) = adjustSucc rest	(* compute weight *)
1263	| adjustSucc [] = ()	val w = List.foldr (fn ((_,_,CFG.EDGE{w,...}),n) => !w+n)
1264		0 (!entries)
1265	val _ = adjustSucc blocks	in  #add_edge cfg' (x, y, CFG.EDGE{a=ref [], w=ref w, k=k})
	val _ = app (addPred entry) (!entries)
	in  F.CLUSTER{blkCounter=ref n,
	annotations=annotations,
	blocks=blocks,
	entry=newEntry,
	exit=newExit
	}
1266	end	end
1267
1268	in  insertLabels([], blocks);	val addNewEdges = app addNewEdge
1269	IntHashTable.appi split edgesToSplit;	val _ = IntHashTable.app addNewEdges repairCodeTable
1270	renumberBlocks()	val _ = IntHashTable.app addNewEdges repairCodeTable'
1271
1272		in  Cfg'
1273	end	end
1274
1275		in  IntHashTable.appi split edgesToSplit;
1276		renumberBlocks()
1277		end
1278
1279	(*------------------------------------------------------------------	(*------------------------------------------------------------------
1280	* Process all blocks	* Process all blocks which are not the entry or the exit
1281	*------------------------------------------------------------------*)	*------------------------------------------------------------------*)
1282	fun rewriteAllBlocks	val stamp = ref 0
1283	(stamp,	fun rewriteAllBlocks (_, CFG.BLOCK{kind=CFG.START, ...}) = ()
1284	(block as F.BBLOCK{blknum, insns, liveIn, liveOut,	| rewriteAllBlocks (_, CFG.BLOCK{kind=CFG.STOP, ...}) = ()
1285	annotations, pred, succ, ...})::rest) =	| rewriteAllBlocks
1286	let val stamp = rewrite(stamp, blknum, block,	(blknum, block as CFG.BLOCK{insns, labels, annotations, ...}) =
1287		let val _ =
1288		if debug andalso !debugOn then
1289		app (fn l => pr(L.toString l^":\n")) (!labels)
1290		else ();
1291		val liveIn  = HT.lookup liveInTable blknum
1292		val liveOut = HT.lookup liveOutTable blknum
1293		val st = rewrite(!stamp, blknum, block,
1294	insns, liveIn, liveOut,	insns, liveIn, liveOut,
1295	pred, succ, annotations)	annotations)
1296	in  rewriteAllBlocks(stamp+1, rest)	in  stamp := st (* update stamp *)
1297	end	end
	| rewriteAllBlocks(stamp, F.LABEL l::rest) =
	(if debug andalso !debugOn then pr(Label.nameOf l^":\n") else ();
	rewriteAllBlocks(stamp, rest)
	)
	| rewriteAllBlocks(stamp, _::rest) = rewriteAllBlocks(stamp, rest)
	| rewriteAllBlocks(stamp, []) = ()
1298
1299	(*------------------------------------------------------------------	(*------------------------------------------------------------------
1300	* Translate code within a basic block.	* Translate code within a basic block.
#	Line 1241	Line 1302
1302	* uses.	* uses.
1303	*------------------------------------------------------------------*)	*------------------------------------------------------------------*)
1304	and rewrite(stamp, blknum, block, insns, liveIn, liveOut,	and rewrite(stamp, blknum, block, insns, liveIn, liveOut,
1305	pred, succ, annotations) =	annotations) =
1306	let val (stackIn, stack, code) = shuffleIn(blknum, block, pred, liveIn)	let val (stackIn, stack, code) = shuffleIn(blknum, block, liveIn)
1307
1308	(* Dump instructions when encountering a bug *)	(* Dump instructions when encountering a bug *)
1309	fun bug msg =	fun bug msg =
#	Line 1823	Line 1884
1884	(* Dump the initial code *)	(* Dump the initial code *)
1885	val _ = if debug andalso !debugOn then	val _ = if debug andalso !debugOn then
1886	(pr("-------- block "^i2s blknum^" ----"^	(pr("-------- block "^i2s blknum^" ----"^
1887	CB.CellSet.toString (!liveIn)^" "^	celllistToString liveIn^" "^
1888	ST.stackToString stackIn^"\n");	ST.stackToString stackIn^"\n");
1889	dump (!insns)	dump (!insns);
1890		pr("succ=");
1891		app (fn b => pr(i2s b^" ")) (#succ cfg blknum);
1892		pr("\n")
1893	)	)
1894	else ()	else ()
1895
#	Line 1836	Line 1900
1900	val (stamp, insns') = loop(stamp, rev(!insns), lastUse, code)	val (stamp, insns') = loop(stamp, rev(!insns), lastUse, code)
1901
1902	(* Insert shuffle code at the end if necessary *)	(* Insert shuffle code at the end if necessary *)
1903	val insns' = shuffleOut(stack, insns', blknum, block, succ, liveOut)	val insns' = shuffleOut(stack, insns', blknum, block, liveOut)
1904
1905	(* Dump translation *)	(* Dump translation *)
1906	val _ = if debug andalso !debugOn then	val _ = if debug andalso !debugOn then
1907	(pr("-------- translation "^i2s blknum^"----"^	(pr("-------- translation "^i2s blknum^"----"^
1908	CB.CellSet.toString (!liveIn)^" "^	celllistToString liveIn^" "^
1909	ST.stackToString stackIn^"\n");	ST.stackToString stackIn^"\n");
1910	dump insns';	dump insns';
1911	pr("-------- done "^i2s blknum^"----"^	pr("-------- done "^i2s blknum^"----"^
1912	CB.CellSet.toString (!liveOut)^" "^	celllistToString liveOut^" "^
1913	ST.stackToString stack^"\n")	ST.stackToString stack^"\n")
1914	)	)
1915	else ()	else ()
#	Line 1860	Line 1924
1924	end (* process *)	end (* process *)
1925
1926	in  (* Translate all blocks *)	in  (* Translate all blocks *)
1927	rewriteAllBlocks(C.firstPseudo, blocks);	stamp := C.firstPseudo;
1928		#forall_nodes cfg rewriteAllBlocks;
1929	(* If we found critical edges, then we have to split them... *)	(* If we found critical edges, then we have to split them... *)
1930	if IntHashTable.numItems edgesToSplit = 0 then cluster	if IntHashTable.numItems edgesToSplit = 0 then Cfg
1931	else repairCriticalEdges(cluster)	else repairCriticalEdges(Cfg)
1932	end	end
	*)
1933	end (* functor *)	end (* functor *)
1934
1935	end (* local *)	end (* local *)

---

Colored Diff Long Colored Diff Unidiff Context Diff Side by Side

Legend: Removed from v.909   changed lines   Added in v.925

---

root@smlnj-gforge.cs.uchicago.edu	ViewVC Help
Powered by ViewVC 1.0.0