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/backpatch/backpatch.sml
ViewVC logotype

View of /sml/trunk/src/MLRISC/backpatch/backpatch.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1124 - (download) (annotate)
Thu Mar 7 19:49:22 2002 UTC (19 years, 6 months ago) by george
File size: 5256 byte(s)
Tested the weighted block placement optimization on all architectures
(except the hppa) using AMPL to generate the block and edge frequencies.
Changes were required in the machine properties to correctly
categorize trap instructions. There is an MLRISC flag
"weighted-block-placement" that can be used to enable weighted block
placement, but this will be ineffective without block/edge
frequencies (coming soon).
(* bbsched2.sml
 *
 * COPYRIGHT (c) 1996 Bell Laboratories.
 *
 *)

(** bbsched2.sml - invoke scheduling after span dependent resolution **)

functor BBSched2
    (structure Emitter : INSTRUCTION_EMITTER
     structure CFG     : CONTROL_FLOW_GRAPH
			where I = Emitter.I
		          and P = Emitter.S.P
     structure Jumps   : SDI_JUMPS
     			where I = CFG.I
     structure Props   : INSN_PROPERTIES
			where I = CFG.I
    ) = 
struct

  structure CFG = CFG
  structure G = Graph
  structure I = CFG.I
  structure C = I.C
  structure E = Emitter
  structure J = Jumps
  structure P = CFG.P

  structure DefaultPlacement = DefaultBlockPlacement(CFG)
  structure WeightedPlacement = 
     WeightedBlockPlacementFn(structure CFG = CFG structure InsnProps = Props)

  val placementFlag = MLRiscControl.getFlag "weighted-block-placement"
  val blockPlacement = 
      if !placementFlag then WeightedPlacement.blockPlacement
      else DefaultPlacement.blockPlacement

  fun error msg = MLRiscErrorMsg.error("BBSched",msg)

  datatype code =
      SDI of {size : int ref,		(* variable sized *)
	      insn : I.instruction}
    | FIXED of {size: int,		(* size of fixed instructions *)
		insns: I.instruction list}
   
  datatype compressed = 
      PSEUDO of P.pseudo_op
    | LABEL  of Label.label
    | CODE of  code list

  datatype cluster = CLUSTER of compressed list

  val clusterList : cluster list ref = ref []
  val dataList : P.pseudo_op list ref = ref []
  fun cleanUp() = (clusterList := []; dataList := [])

  fun bbsched(cfg as G.GRAPH{graph_info=CFG.INFO{data, ...}, ...}) = let
    val blocks = map #2 (blockPlacement cfg)
    
    fun compress [] = []
      | compress(CFG.BLOCK{align, labels, insns, ...} :: rest) = let
          fun alignIt(chunks) = 
	    (case !align of NONE => chunks | SOME p => PSEUDO(p)::chunks)

	  fun mkCode(0, [], [], code) = code
	    | mkCode(size, insns, [], code) = FIXED{size=size, insns=insns}:: code
	    | mkCode(size, insns, instr::instrs, code) = let
		val s = J.minSize instr
	      in
		if J.isSdi instr then let
		    val sdi = SDI{size=ref s, insn=instr}
		  in
		    if size = 0 then 
		      mkCode(0, [], instrs, sdi::code)
		    else 
		      mkCode(0, [], instrs, 
			     sdi::FIXED{size=size, insns=insns}::code)
		  end
		else mkCode(size+s, instr::insns, instrs, code)
	      end
	in
	  alignIt
	    (map LABEL (!labels) @ 
	       CODE(mkCode(0, [], !insns, [])) :: compress rest)
	end
  in
    clusterList:=CLUSTER(compress blocks):: (!clusterList);
    dataList := !data @ !dataList
  end



  fun finish() = let
    fun labels(PSEUDO pOp::rest, pos, chgd) = 
          (P.adjustLabels(pOp, pos); labels(rest, pos+P.sizeOf(pOp,pos), chgd))
      | labels(LABEL lab::rest, pos, chgd) = 
	 if Label.addrOf(lab) = pos then labels(rest, pos, chgd)
	 else (Label.setAddr(lab, pos); labels(rest, pos, true))
      | labels(CODE code::rest, pos, chgd) = let
 	  fun doCode(FIXED{size, ...}::rest, pos, changed) = 
	        doCode(rest, pos+size, changed)
	    | doCode(SDI{size, insn}::rest, pos, changed) = let
	  	val newSize = J.sdiSize(insn, Label.addrOf, pos)
 	      in
		  if newSize <= !size then doCode(rest, !size + pos, changed)
		  else (size:=newSize; doCode(rest, newSize+pos, true))
	       end
	    | doCode([], pos, changed) = labels(rest, pos, changed)
        in doCode(code, pos, chgd)
	end
      | labels([], pos,chgd) = (pos, chgd)

    fun clusterLabels clusters = let
      fun f (CLUSTER cl, (pos, chgd)) = labels(cl, pos, chgd)
    in List.foldl f (0, false) clusters
    end

    fun fixpoint zl = let 
      val (size, changed) = clusterLabels zl
    in if changed then fixpoint zl else size
    end

    val Emitter.S.STREAM{emit,defineLabel,beginCluster,pseudoOp,...} = 
            Emitter.makeStream []

    fun emitCluster(CLUSTER(comp),loc) = let
	  fun process(PSEUDO pOp,loc) = (pseudoOp pOp; loc + P.sizeOf(pOp,loc))
	    | process(LABEL lab,loc) = (defineLabel lab; loc)
	    | process(CODE code,loc) = let
		fun emitInstrs insns = app emit insns
		fun e(FIXED{insns, size,...},loc) = (emitInstrs insns; loc+size)
		  | e(SDI{size, insn},loc) = 
		       (emitInstrs(J.expand(insn, !size, loc)); !size + loc)
	      in foldl e loc code
	      end
	in foldl process loc comp
	end

    fun initLabels(clusters) = let
      fun init(PSEUDO(p)::rest, loc) = 
	   (P.adjustLabels(p, loc); init(rest, loc + P.sizeOf(p, loc)))
	| init(LABEL lab::rest, loc) = (Label.setAddr(lab,loc); init(rest, loc))
	| init(CODE code::rest, loc) = let
 	   fun size(FIXED{size, ...}) = size
	     | size(SDI{size, ...}) = !size
          in
	    init(rest, List.foldl (fn (c, b) => size(c) + b) loc code)
          end
        | init([], loc) = loc

    in
      List.foldl 
        (fn (CLUSTER(cl), loc) => init(cl, loc)) 0 clusters
    end

    (* The dataList is in reverse order and the clusters are in reverse *)
    fun dataCluster([], acc) = CLUSTER(acc)
      | dataCluster(d::dl, acc) = dataCluster(dl, PSEUDO d::acc)
    val compressed = 
      rev (dataCluster(!dataList, []) :: !clusterList) before cleanUp()
  in
    initLabels(compressed);
    beginCluster(fixpoint (compressed));
    foldl emitCluster 0 compressed; 
    ()
  end (*finish*)
end (* bbsched2 *)



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