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

SCM Repository

[smlnj] Diff of /sml/trunk/src/MLRISC/backpatch/spanDep.sml
ViewVC logotype

Diff of /sml/trunk/src/MLRISC/backpatch/spanDep.sml

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 999, Tue Nov 27 06:28:37 2001 UTC revision 1000, Wed Nov 28 14:50:42 2001 UTC
# Line 2  Line 2 
2   * This version of the span dependency resolution also fill delay slots   * This version of the span dependency resolution also fill delay slots
3   * using a few simple strategies.   * using a few simple strategies.
4   *   *
5     * Assumption: Instructions are 32bits.
6     *
7   * Allen   * Allen
8   *)   *)
9    
# Line 19  Line 21 
21       structure Placement : BLOCK_PLACEMENT       structure Placement : BLOCK_PLACEMENT
22                          where CFG = CFG                          where CFG = CFG
23       ) : BBSCHED =       ) : BBSCHED =
      (*  
        sharing Placement.CFG = CFG  
        sharing CFG.P = Emitter.P  
        sharing CFG.I = Jumps.I = DelaySlot.I = Props.I = Emitter.I)  
          : BBSCHED = *)  
24  struct  struct
25    
26    structure CFG = CFG    structure CFG = CFG
# Line 58  Line 55 
55        PSEUDO of P.pseudo_op        PSEUDO of P.pseudo_op
56      | LABEL  of Label.label      | LABEL  of Label.label
57      | CODE of Label.label * code list      | CODE of Label.label * code list
     | CLUSTER of {comp : compressed list}  
58    
59    val clusterList : compressed list ref = ref []    datatype cluster =  CLUSTER of {comp : compressed list}
60    
61      val clusterList : cluster list ref = ref []
62    val dataList : P.pseudo_op list ref = ref []    val dataList : P.pseudo_op list ref = ref []
63    fun cleanUp() = (clusterList := []; dataList := [])    fun cleanUp() = (clusterList := []; dataList := [])
64    
# Line 313  Line 311 
311    
312    
313    fun finish () = let    fun finish () = let
314      fun labels(PSEUDO pOp::rest, pos) =      fun labels(PSEUDO pOp::rest, loc) =
315            (P.adjustLabels(pOp, pos); labels(rest, pos+P.sizeOf(pOp,pos)))            (P.adjustLabels(pOp, loc); labels(rest, loc+P.sizeOf(pOp, loc)))
316        | labels(LABEL lab::rest, pos) =        | labels(LABEL lab::rest, loc) =
317           (Label.setAddr(lab,pos); labels(rest, pos))            (Label.setAddr(lab, loc); labels(rest, loc))
318        | labels(CODE(lab,code)::rest, pos) = let        | labels(CODE(lab,code)::rest, loc) = let
319            fun size(FIXED{size, ...}) = size            fun size(FIXED{size, ...}) = size
320              | size(SDI{size, ...}) = !size              | size(SDI{size, ...}) = !size
321              | size(BRANCH{insn,...}) = sizeList(insn,0)              | size(BRANCH{insn,...}) = sizeList(insn,0)
# Line 326  Line 324 
324                  sizeList(if !fillSlot then newInsns else oldInsns,0)                  sizeList(if !fillSlot then newInsns else oldInsns,0)
325            and sizeList([],n) = n            and sizeList([],n) = n
326              | sizeList(code::rest,n) = sizeList(rest,size code + n)              | sizeList(code::rest,n) = sizeList(rest,size code + n)
327          in  Label.setAddr(lab,pos+4);          in  Label.setAddr(lab,loc+4);
328              labels(rest, sizeList(code,pos))              labels(rest, sizeList(code,loc))
329          end          end
330        | labels(CLUSTER{comp, ...}::rest, pos) = labels(rest, labels(comp,pos))        | labels([], loc) = loc
331        | labels([], pos) = pos  
332        fun initLabels clusters =
333          List.foldl
334            (fn (CLUSTER{comp}, loc) => labels(comp, loc)) 0 clusters
335    
336    
337      val delaySlotSize = D.delaySlotSize      val delaySlotSize = D.delaySlotSize
338        (*
339           Suppose we have:
340    
341                u
342                jmp L1
343                nop
344            ...
345            L1: i
346                j
347                k
348    
349            I insert a fake label L2:
350    
351            L1: i
352            L2: j
353                k
354    
355            L2 is the label in CODE(label,code).
356    
357            If instruction u cannot be put into the delay slot of jmp L1 I try
358            to put i into the delay slot of L1.  This creates code like this:
359    
360                 u
361                 jmp L2
362                 i
363            ...
364            L1:  i
365            L2:  j
366                 k
367         -- Allen
368        *)
369        fun adjust(CLUSTER{comp, ...}, pos, changed) = let
370          fun scan(PSEUDO pOp::rest, pos, changed) = let
371                val chgd = P.adjustLabels(pOp, pos)
372              in scan(rest, pos+P.sizeOf(pOp,pos), changed orelse chgd)
373              end
374            | scan(LABEL lab::rest, pos, changed) =
375              if Label.addrOf(lab) = pos then scan(rest, pos, changed)
376              else (Label.setAddr(lab, pos); scan(rest, pos, true))
377            | scan(CODE(lab,code)::rest, pos, changed) = let
378                  val (newPos,changed) = doCode(code,pos,changed)
379                in
380                  if Label.addrOf(lab) = pos+4 then
381                      scan(rest, newPos, changed)
382                  else (Label.setAddr(lab, pos+4);  scan(rest, newPos, true))
383                end
384            | scan([], pos, changed) = (pos, changed)
385    
     fun adjust(CLUSTER{comp, ...}::cluster, pos, changed) =  
     let fun scan(PSEUDO pOp::rest, pos, changed) =  
               scan(rest, pos+P.sizeOf(pOp,pos), changed)  
           | scan(LABEL _::rest, pos, changed) = scan(rest, pos, changed)  
           | scan(CODE(_,code)::rest, pos, changed) =  
               let val (pos,changed) = doCode(code,pos,changed)  
               in  scan(rest,pos,changed) end  
           | scan([], pos, changed) = adjust(cluster, pos, changed)  
           | scan _ = error "scan"  
386          and doCode([],pos,changed) = (pos,changed)          and doCode([],pos,changed) = (pos,changed)
387            | doCode(code::rest,pos,changed) =            | doCode(code::rest,pos,changed) =
388              case code of              case code of
# Line 370  Line 410 
410                         pos,changed)                         pos,changed)
411      in  scan(comp, pos, changed)      in  scan(comp, pos, changed)
412      end      end
413        | adjust(PSEUDO pOp::rest, pos, changed) =  
414            adjust(rest, pos+P.sizeOf(pOp, pos), changed)      fun adjustLabels clusters = let
415        | adjust(_::_, _, _) = error "adjust"        fun f (cl, (pos, chgd)) = adjust(cl, pos, chgd)
416        | adjust([], _, changed) = changed      in List.foldl f (0, false) clusters
417        end
418      fun fixpoint zl = let  
419        val size = labels(zl, 0)      fun fixpoint zl i = let
420      in if adjust(zl, 0, false) then fixpoint zl else size        val (size, changed) =  adjustLabels zl
421        in if changed then fixpoint zl (i+1) else size
422      end      end
423    
424      val E.S.STREAM{defineLabel,pseudoOp,emit,beginCluster,...} =      val E.S.STREAM{defineLabel,pseudoOp,emit,beginCluster,...} =
425          E.makeStream []          E.makeStream []
426      fun emitCluster(CLUSTER{comp},loc) = let      fun emitCluster(CLUSTER{comp},loc) = let
427            val emitInstrs = app emit            val emitInstrs = app emit
428          fun nops 0 = ()
429            | nops n = if n < 0 then error "nops" else (emit(Props.nop()); nops(n-4))
430    
431            fun process(PSEUDO pOp,loc) = (pseudoOp pOp; loc+P.sizeOf(pOp,loc))            fun process(PSEUDO pOp,loc) = (pseudoOp pOp; loc+P.sizeOf(pOp,loc))
432              | process(LABEL lab,loc) = (defineLabel lab; loc)          | process(LABEL lab,loc) = let
433              | process(CODE(_,code),loc) = let              val addr = Label.addrOf lab
434              in
435                if addr = loc then (defineLabel lab; loc)
436                else if addr > loc then (nops(addr-loc); defineLabel lab; addr)
437                else error "label"
438              end
439            | process(CODE(lab,code),loc) = let
440                  fun e(FIXED{insns, size, ...},loc) = (emitInstrs insns; loc+size)                  fun e(FIXED{insns, size, ...},loc) = (emitInstrs insns; loc+size)
441                    | e(SDI{size, insn},loc) =                    | e(SDI{size, insn},loc) =
442                        (emitInstrs(J.expand(insn, !size, loc)); !size + loc)                        (emitInstrs(J.expand(insn, !size, loc)); !size + loc)
# Line 394  Line 444 
444                    | e(DELAYSLOT{insn,...},loc) = foldl e loc insn                    | e(DELAYSLOT{insn,...},loc) = foldl e loc insn
445                    | e(CANDIDATE{newInsns,oldInsns,fillSlot,...},loc) =                    | e(CANDIDATE{newInsns,oldInsns,fillSlot,...},loc) =
446                        foldl e loc (if !fillSlot then newInsns else oldInsns)                        foldl e loc (if !fillSlot then newInsns else oldInsns)
447                in foldl e loc code            in
448                  foldl e loc code
449                end                end
             | process _ = error "process"  
450          in foldl process loc comp          in foldl process loc comp
451          end          end
       | emitCluster(PSEUDO pOp, loc) = (pseudoOp pOp; loc+P.sizeOf(pOp, loc))  
       | emitCluster _ = error "emitCluster"  
452    
453      (* The dataList is in reverse order, and the entries in each      (* The dataList is in reverse order and the clusters are in reverse *)
454       * are also in reverse      fun dataCluster([], acc) = CLUSTER{comp=acc}
455       *)        | dataCluster(d::dl, acc) = dataCluster(dl, PSEUDO d::acc)
456      val compressed = rev (map PSEUDO (!dataList) @ !clusterList) before cleanUp()      val compressed =
457          rev (dataCluster(!dataList, []) :: !clusterList) before cleanUp()
458    in    in
459       beginCluster(fixpoint(compressed));       initLabels(compressed);
460         beginCluster(fixpoint compressed 0);
461       foldl emitCluster 0 compressed;       foldl emitCluster 0 compressed;
462       ()       ()
463    end (*finish*)    end (*finish*)

Legend:
Removed from v.999  
changed lines
  Added in v.1000

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