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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 976 - (download) (annotate)
Wed Nov 14 14:54:03 2001 UTC (19 years, 11 months ago) by george
File size: 6795 byte(s)
  Fix for a backpatching bug reported by Allen.

  Because the boundary between short and long span-dependent
  instructions is +/- 128, there are an astounding number of
  span-dependent instructions whose size is over estimated.

  Allen came up with the idea of letting the size of span
  dependent instructions be non-monotonic, for a maxIter
  number of times, after which the size must be monotonically
  increasing.

  This table shows the number of span-dependent instructions
  whose size was over-estimated as a function of maxIter, for the
  file Parse/parse/ml.grm.sml:

     maxIter		# of instructions:
 	10			687
 	20			438
 	30			198
        40			  0

  In compiling the compiler, there is no significant difference in
  compilation speed between maxIter=10 and maxIter=40. Actually,
  my measurements showed that maxIter=40 was a tad faster than
  maxIter=10! Also 96% of the  files in the compiler reach a fix
  point within 13 iterations, so fixing maxIter at 40, while high,
  is okay.
(* vlBackPatch.sml -- variable length back patching. 
 *
 * Copyright 1999 by Bell Laboratories 
 *)

(* NOTE on maxIter:
 * 
 * maxIter -- is the number of times a span-dependent instruction
 *	is allowed to expand in a non-monotonic way. 
 *
 * This table shows the number of span-dependent instructions
 * whose size was over-estimated as a function of maxIter, for the
 * file Parse/parse/ml.grm.sml:
 *
 *    maxIter		# of instructions:
 *	10			687
 *	20			438
 *	30			198
 *      40			  0
 *
 * In compiling the compiler, there is no significant difference in
 * compilation speed between maxIter=10 and maxIter=40. 
 * Indeed 96% of the  files in the compiler reach a fix point within
 * 13 iterations.
 *)
signature MC_EMIT = sig
  structure I : INSTRUCTIONS

  val emitInstr : I.instruction -> Word8Vector.vector
end

  
functor BackPatch
  (structure CodeString : CODE_STRING
   structure Jumps      : SDI_JUMPS 
   structure Props      : INSN_PROPERTIES 
                        where I = Jumps.I
   structure Emitter    : MC_EMIT
                        where I = Props.I
   structure CFG        : CONTROL_FLOW_GRAPH
                        where I = Emitter.I
   structure Asm        : INSTRUCTION_EMITTER
                        where I = CFG.I
   structure Placement  : BLOCK_PLACEMENT
                        where CFG = CFG)  : BBSCHED = 
struct 
  structure I   = Jumps.I
  structure C   = I.C
  structure CFG = CFG
  structure P   = CFG.P
  structure G   = Graph
  structure W8V = Word8Vector

  datatype desc =
      BYTES of W8V.vector * desc 
    | PSEUDO of P.pseudo_op  * desc
    | SDI of I.instruction * int ref * desc
    | LABEL of Label.label * desc
    | NIL

  datatype cluster = CLUSTER of {cluster: desc}

  val maxIter = MLRiscControl.getInt "variable-length-backpatch-iterations"
  val _ = maxIter := 40
 
  fun error msg = MLRiscErrorMsg.error("vlBackPatch",msg)

  val clusters = ref ([] : cluster list)

  fun cleanUp() = clusters := []

  val Asm.S.STREAM{emit,...} = Asm.makeStream []

  fun bbsched(cfg as G.GRAPH graph) = let
    val blocks = map #2 (Placement.blockPlacement cfg)
    fun bytes([], p) = p
      | bytes([s], p) = BYTES(s, p)
      | bytes(s, p) = BYTES(W8V.concat s, p)

    fun f(CFG.BLOCK{data, labels, insns, ...}::rest) = let
         fun instrs([], b) = bytes(rev b, f rest)
           | instrs(i::rest, b) = 
             if Jumps.isSdi i then 
               bytes(rev b, SDI(i, ref(Jumps.minSize i), instrs(rest, [])))
             else
               instrs(rest, Emitter.emitInstr(i)::b)
         fun doLabels(lab::rest) = LABEL(lab, doLabels rest)
           | doLabels [] = instrs(rev(!insns), [])
         fun pseudo(CFG.PSEUDO pOp :: rest) = PSEUDO(pOp, pseudo rest)
           | pseudo(CFG.LABEL lab :: rest) =  LABEL(lab, pseudo rest)
           | pseudo [] = doLabels(!labels)

        in pseudo(!data)
        end 
      | f [] = NIL
  in 
    clusters := 
      CLUSTER{cluster=f blocks}:: !clusters
  end

  
  fun finish() = let
    val iter = ref 0 (* iteration count *)
    fun labels (BYTES(s,rest), pos, chgd) = labels(rest, pos+W8V.length s, chgd)
      | labels (SDI(instr, r as ref size, rest), pos, chgd) = 
          let val s = Jumps.sdiSize(instr, Label.addrOf, pos)
              (* Allow contraction in the first two passes;
               * after which only allows expansion to ensure termination.
               *)
          in 
	      if (!iter <= !maxIter andalso s <> size) orelse s > size then
		  (r := s; labels(rest, pos + s, true))
	      else labels(rest, pos + size, chgd)
          end
      | labels (LABEL(l,rest), pos, changed) = 
        if Label.addrOf(l) = pos then labels(rest, pos, changed)
        else (Label.setAddr(l, pos); labels(rest, pos, true))
      | labels (PSEUDO(pOp, rest), pos, chgd) = let
          val oldSz = P.sizeOf(pOp, pos)
          val newSz = (P.adjustLabels(pOp, pos); P.sizeOf(pOp, pos))
        in labels(rest, pos + newSz, chgd orelse newSz<>oldSz)
        end
      | labels (NIL, pos, chgd) = (pos, chgd)

    fun clusterLabels clusters = let
      fun f (CLUSTER{cluster, ...}, (pos,chgd)) = labels(cluster, pos, chgd) 
    in List.foldl f (0, false) clusters
    end
      
    val nop = Props.nop()

    val loc = ref 0

    fun output v = 
      W8V.app (fn v => (CodeString.update(!loc, v); loc:= !loc+1)) v


    fun chunk(pos, []) = ()
      | chunk(pos, CLUSTER{cluster}::rest) = let
          fun outputInstr i = output (Emitter.emitInstr(nop))
          fun nops 0 = ()
            | nops n = (outputInstr(nop); nops(n-1))
          fun f(pos, BYTES(s,r)) = (output s; f(pos+W8V.length s,r))
            | f(pos, SDI(instr, ref size, r)) = let
                val emitInstrs = map (fn i => Emitter.emitInstr(i))
                val instrs = emitInstrs (Jumps.expand(instr, size, pos))
                val sum = List.foldl (fn (a,b) => (W8V.length a + b)) 0
                val n = size - sum instrs
              in
                (*
                 if n > 0 then 
                   (print ("\t\t\t Inserting " ^ Int.toString n ^ "nops\n");
                    emit instr)
                 else (); 
                *)
                app output instrs;
		nops(n);
                f(pos+size, r)
              end
            | f(pos, LABEL(lab, rest)) = 
                if pos = Label.addrOf lab then f(pos,rest)
                else error "chunk: LABEL"
            | f(pos, PSEUDO(pOp, rest)) = let
                val s : Word8.word list ref = ref []
              in
                P.emitValue{pOp=pOp, loc=pos, 
                            emit=(fn w => s :=  w :: (!s))};
                output(W8V.fromList(rev(!s)));
                f(pos + P.sizeOf(pOp, pos), rest)
              end
            | f(pos, NIL) = chunk(pos, rest)

        in f(pos, cluster)
        end

    fun fix clusters = let
      val (pos, changed) = clusterLabels clusters
    in 
      if changed then (iter := !iter + 1; fix clusters) else pos
    end

    (* 
     * Initialize labels so that they have 
     * some reasonable value to begin with.
     *)
    fun initLabels (clusters) = let
      fun init(BYTES(bytes, rest), loc) = init(rest, loc + W8V.length bytes)
	| init(PSEUDO(pOp, rest), loc) = 
	    (P.adjustLabels(pOp, loc); init(rest, loc + P.sizeOf(pOp, loc)))
	| init(SDI(sdi, size, rest), loc) = init(rest, loc + !size)
	| init(LABEL(lab, rest), loc) = 
	    (Label.setAddr(lab, loc); init(rest, loc))
	| init(NIL, loc) = loc
    in 
      List.foldl
	(fn (CLUSTER{cluster, ...}, loc) => init(cluster, loc)) 0 clusters
    end

    val clusters = rev(!clusters) before clusters := []
  in
    initLabels(clusters);
    CodeString.init(fix clusters);
    loc := 0; chunk(0, clusters) 
  end (* finish *)

end (* functor BackPatch *)


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