Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] View of /sml/trunk/src/MLRISC/instructions/shuffle.sml
ViewVC logotype

View of /sml/trunk/src/MLRISC/instructions/shuffle.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1009 - (download) (annotate)
Wed Jan 9 19:44:22 2002 UTC (17 years, 7 months ago) by george
File size: 2195 byte(s)
	Removed the native COPY and FCOPY instructions
	from all the architectures and replaced it with the
	explicit COPY instruction from the previous commit.

	It is now possible to simplify many of the optimizations
	modules that manipulate copies. This has not been
	done in this change.
(* shuffle.sml -- implements the parallel copy instruction as a sequence
 *		of moves. 
 *
 * COPYRIGHT (c) 1996 Bell Laboratories.
 *
 *)


functor Shuffle(I : INSTRUCTIONS) :
  sig
    val shuffle : 
      {mvInstr : {dst:I.ea, src:I.ea} -> I.instruction list,
       ea : CellsBasis.cell -> I.ea} 
      ->
	{tmp : I.ea option,
	 dst : CellsBasis.cell list,
	 src : CellsBasis.cell list} 
	-> I.instruction list
  end = 
struct
  structure C = I.C

  datatype obj = TEMP | CELL of CellsBasis.cell

  fun equal (r1, r2) = CellsBasis.sameColor(r1,r2)

  fun equalObj (TEMP, TEMP) = true
    | equalObj (CELL u, CELL v) = equal(u, v)
    | equalObj _ = false

  fun shuffle{mvInstr, ea} {tmp, dst, src} = let
    fun mv{dst, src, instrs} = List.revAppend(mvInstr{dst=dst,src=src}, instrs)

    fun opnd dst = case dst of 
                     TEMP     => Option.valOf tmp 
                   | CELL dst => ea dst

    (* perform unconstrained moves *)
    fun loop((p as (rd,rs))::rest, changed, used, done, instrs) = 
	if List.exists (fn r => equalObj(r, rd)) used then
	   loop(rest, changed, used, p::done, instrs)
	else loop(rest, true, used, done,
                  mv{dst=opnd rd, src=opnd rs, instrs=instrs})
      | loop([], changed, _, done, instrs) = (changed, done, instrs)

    fun cycle([], instrs) = instrs
      | cycle(moves, instrs) =
	(case loop(moves, false, map #2 moves, [], instrs)
	  of (_, [], instrs) => instrs
	   | (true, acc, instrs) => cycle(acc, instrs)
	   | (false, (rd,rs)::acc, instrs) => let
	       fun rename(p as (a,b)) =
                   if equalObj(rd, b) then (a, TEMP) else p
	       val acc' = (rd, rs) :: map rename acc
	       val instrs' = mv{dst=Option.valOf tmp, src=opnd rd, instrs=instrs}
	       val (_, acc'', instrs'') = 
		 loop(acc', false, map #2 acc', [], instrs')
	     in cycle(acc'', instrs'')
	     end
	 (*esac*))

    (* remove moves that have been coalesced. *)
    fun rmvCoalesced(rd::rds, rs::rss, mvs) = 
        if equal(rd, rs) then rmvCoalesced(rds, rss, mvs)
        else rmvCoalesced(rds, rss, (CELL rd, CELL rs)::mvs)
      | rmvCoalesced([], [], mvs) = mvs
  in rev (cycle (rmvCoalesced(dst, src, []), []))
  end
end


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