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

View of /sml/trunk/src/MLRISC/ra/risc-ra.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1003 - (download) (annotate)
Fri Dec 7 02:45:32 2001 UTC (17 years, 10 months ago) by george
File size: 13446 byte(s)
Changed the representation of instructions from being fully abstract
to being partially concrete. That is to say:

  from
	type instruction

  to
	type instr				(* machine instruction *)

	datatype instruction =
	    LIVE of {regs: C.cellset, spilled: C.cellset}
          | KILL of {regs: C.cellset, spilled: C.cellset}
          | COPYXXX of {k: CB.cellkind, dst: CB.cell list, src: CB.cell list}
          | ANNOTATION of {i: instruction, a: Annotations.annotation}
          | INSTR of instr

This makes the handling of certain special instructions that appear on
all architectures easier and uniform.

LIVE and KILL say that a list of registers are live or killed at the
program point where they appear. No spill code is generated when an
element of the 'regs' field is spilled, but the register is moved to
the 'spilled' (which is present, more for debugging than anything else).

LIVE replaces the (now deprecated) DEFFREG instruction on the alpha.
We used to generate:

	DEFFREG f1
	f1 := f2 + f3
        trapb

but now generate:

	f1 := f2 + f3
	trapb
	LIVE {regs=[f1,f2,f3], spilled=[]}

Furthermore, the DEFFREG (hack) required that all floating point instruction
use all registers mentioned in the instruction. Therefore f1 := f2 + f3,
defines f1 and uses [f1,f2,f3]! This hack is no longer required resulting
in a cleaner alpha implementation. (Hopefully, intel will not get rid of
this architecture).

COPYXXX is intended to replace the parallel COPY and FCOPY  available on
all the architectures. This will result in further simplification of the
register allocator that must be aware of them for coalescing purposes, and
will also simplify certain aspects of the machine description that provides
callbacks related to parallel copies.

ANNOTATION should be obvious, and now INSTR represents the honest to God
machine instruction set!

The <arch>/instructions/<arch>Instr.sml files define certain utility
functions for making porting easier -- essentially converting upper case
to lower case. All machine instructions (of type instr) are in upper case,
and the lower case form generates an MLRISC instruction. For example on
the alpha we have:

  datatype instr =
     LDA of {r:cell, b:cell, d:operand}
   | ...

  val lda : {r:cell, b:cell, d:operand} -> instruction
    ...

where lda is just (INSTR o LDA), etc.
(* 
 * This functor factors out the machine independent part of the register
 * allocator.  It performs integer and floating register allocation.
 * This works well for RISC machines; but not applicable to x86.
 *)
functor RISC_RA
  (structure I         : INSTRUCTIONS
   structure Asm       : INSTRUCTION_EMITTER
   			where I = I 
   structure Flowgraph : CONTROL_FLOW_GRAPH 
   			where I = I
		          and P = Asm.S.P
   structure InsnProps : INSN_PROPERTIES
   			where I = I
   structure Rewrite   : REWRITE_INSTRUCTIONS
   			where I = I

      (* Spilling heuristics determines which node should be spilled.
       * You can use Chaitin, ChowHenessey, or one of your own.
       *)
   structure SpillHeur : RA_SPILL_HEURISTICS

      (* The Spill module figures out the strategies for inserting
       * spill code.  You can use RASpill, or RASpillWithRenaming,
       * or write your own if you are feeling adventurous.
       *)
   structure Spill : RA_SPILL where I = I
          
   val architecture : string

   (* Is this a pure instruction *)
   val pure : I.instruction -> bool

   (* Called before RA begins *)
   val beginRA : unit -> unit

   structure Int :
   sig

      val avail     : CellsBasis.cell list (* list of available registers *)
      val dedicated : CellsBasis.cell list (* list of registers that are dedicated *)

      (* This functions is used to create copy instructions.
       * Given dst/src lists, return a new copy instruction with the same
       * temporary as the old one.
       *)
      val copy : (CellsBasis.cell list * CellsBasis.cell list) * I.instruction -> 
                     I.instruction

      (* This function is used to spill the temporary used in the copy
       * onto some stack offset.
       *)
      val spillCopyTmp : Annotations.annotations ref * I.instruction * 
                         RAGraph.spillLoc -> I.instruction

      (* This function is used to spill a register onto some stack offset 
       *)
      val spillInstr : {an:Annotations.annotations ref, src:CellsBasis.cell,
			spilledCell:CellsBasis.cell, spillLoc:RAGraph.spillLoc} 
	               -> I.instruction list

      (*
       * This function is used to reload a register from some stack offset
       *)
      val reloadInstr : {an:Annotations.annotations ref, dst:CellsBasis.cell,
			 spilledCell:CellsBasis.cell, spillLoc:RAGraph.spillLoc}
	                -> I.instruction list

      (* Mode for RA optimizations *)
      val mode : RAGraph.mode
   end

   structure Float :
   sig

      val avail     : CellsBasis.cell list (* list of available registers *)
      val dedicated : CellsBasis.cell list (* list of registers that are dedicated *)

      (* This functions is used to create copy instructions.
       * Given dst/src lists, return a new copy instruction with the same
       * temporary as the old one.
       *)
      val copy : (CellsBasis.cell list * CellsBasis.cell list) * I.instruction -> 
                     I.instruction

      (* This function is used to spill the temporary used in the copy
       * onto some stack offset.
       *)
      val spillCopyTmp : Annotations.annotations ref * I.instruction * 
                         RAGraph.spillLoc -> I.instruction

      (* This function is used to spill a register onto some stack offset 
       * The 
       *)
      val spillInstr : Annotations.annotations ref * CellsBasis.cell * 
                       RAGraph.spillLoc -> I.instruction list
      (*
       * This function is used to reload a register from some stack offset,
       * and concatenate the reload code with the given instruction list.
       *)
      val reloadInstr : Annotations.annotations ref * CellsBasis.cell * 
                        RAGraph.spillLoc -> I.instruction list

      (* Mode for RA optimizations *)
      val mode : RAGraph.mode
   end
  ) : CFG_OPTIMIZATION =
struct

   structure CFG = Flowgraph
   structure I   = CFG.I
   structure P   = InsnProps
   structure C   = I.C
   structure G   = RAGraph

   val name = "RISC_RA"

   (* Counters for register allocation *)
   val intSpillsCnt = MLRiscControl.getCounter "ra-int-spills"
   val intReloadsCnt = MLRiscControl.getCounter "ra-int-reloads"
   val intRenamesCnt = MLRiscControl.getCounter "ra-int-renames"
   val floatSpillsCnt = MLRiscControl.getCounter "ra-float-spills"
   val floatReloadsCnt = MLRiscControl.getCounter "ra-float-reloads"
   val floatRenamesCnt = MLRiscControl.getCounter "ra-float-renames"

   fun error msg = MLRiscErrorMsg.error("RISC RA "^architecture,msg)

   (*
    * Make arithmetic non-overflow trapping.
    * This makes sure that if we happen to run the compiler for a long
    * period of time overflowing counters will not crash the compiler. 
    *)
   fun x + y = Word.toIntX(Word.+(Word.fromInt x, Word.fromInt y))
   fun x - y = Word.toIntX(Word.-(Word.fromInt x, Word.fromInt y))

   (* GetReg specialized to integer and floating point registers *)
   fun isDedicated (len, arr, others) r = 
     (r < len andalso Array.sub(arr, r)) orelse List.exists (fn d => r = d) others

   fun mark(arr, _, [], others) = others
     | mark(arr, len, r::rs, others) = let
	 val r = CellsBasis.registerId r
       in
	 if r >= len then mark(arr, len, rs, r::others)
	 else (Array.update(arr, r, true); mark(arr, len, rs, others))
       end

   fun annotate([], i) = i
     | annotate(a::an, i) = annotate(an, I.ANNOTATION{a=a, i=i})



   local
       val {low,high} = C.cellRange CellsBasis.GP
       val arr = Array.array(high+1,false)
       val others = mark(arr, high+1, Int.dedicated, [])
   in
       structure GR = GetReg(val first=low val nRegs=high-low+1 
                             val available=map CellsBasis.registerId Int.avail)
       val dedicatedR : int -> bool = isDedicated (high+1, arr, others)
   end
   local 
      val {low,high} = C.cellRange CellsBasis.FP
      val arr = Array.array(high+1,false)
      val others = mark(arr, high+1, Float.dedicated, [])
   in
      structure FR = GetReg(val first=low val nRegs=high-low+1 
                            val available=map CellsBasis.registerId Float.avail)
      val dedicatedF : int -> bool = isDedicated(high+1, arr, others)
   end

   fun spillR{annotations, kill=true, reg, spillLoc, instr} = 
         if pure instr then {code=[], proh=[], newReg=NONE}
         else spillR{annotations=annotations,kill=false,
                     spillLoc=spillLoc,
                     reg=reg,instr=instr}
     | spillR{annotations, kill, reg, spillLoc, instr} = let
	 fun annotate([], i) = i
	   | annotate(a::an, i) = annotate(an, I.ANNOTATION{a=a, i=i})

	 (* preserve annotation on instruction *)
	 fun spill(instrAn, I.ANNOTATION{a, i}) = spill(a::instrAn, i)
	   | spill(instrAn, I.KILL{regs, spilled}) = 
	      {code=
	         [annotate
		   (instrAn, 
		    I.KILL {regs=C.rmvReg(reg, regs), 
			    spilled=C.addReg(reg, spilled)})],
	        proh = [], 
		newReg=NONE}
	   | spill(instrAn, I.LIVE _) = error "spillR: LIVE"
	   | spill(_, I.COPYXXX _) = error "spillR: not supported"
	   | spill(instrAn, I.INSTR _) = let
	       val _   = intSpillsCnt := !intSpillsCnt + 1
               val newR = C.newReg()
    	       val instr' = Rewrite.rewriteDef(instr, reg, newR)
	     in  {code=
		    annotate(instrAn, instr')::
		      Int.spillInstr
			  {an=annotations,src=newR, 
			   spilledCell=reg,spillLoc=spillLoc},
		  proh=[newR], 
		  newReg=SOME newR}
	     end
        in spill([], instr)
        end


   fun spillReg{annotations,src,reg,spillLoc} =
       (intSpillsCnt := !intSpillsCnt + 1;
        Int.spillInstr{an=annotations,src=src,spilledCell=reg,
		       spillLoc=spillLoc}
       )

   fun spillTmp{annotations,reg,copy,spillLoc} =
       (intSpillsCnt := !intSpillsCnt + 1;
        Int.spillCopyTmp(annotations,copy,spillLoc)
       )

   (* Spill floating point register *)
   fun spillF{annotations, kill=true, reg, spillLoc, instr} = 
         if pure instr then {code=[], proh=[], newReg=NONE}
         else spillF {annotations=annotations,kill=false,
                      spillLoc=spillLoc, reg=reg,instr=instr}
     | spillF{annotations, kill, reg, spillLoc, instr} = let
	 (* preserve annotation on instruction *)
	 fun spill(instrAn, I.ANNOTATION{a, i}) = spill(a::instrAn, i)
	   | spill(instrAn, I.KILL{regs, spilled}) = 
	      {code=
  	         [annotate
		   (instrAn, 
		    I.KILL {regs=C.rmvFreg(reg, regs), 
			    spilled=C.addFreg(reg, spilled)})],
	        proh = [], 
		newReg=NONE}
	   | spill(instrAn, I.LIVE _) = error "spillF: LIVE"
	   | spill(_, I.COPYXXX _) = error "spillF: COPY not supported"
	   | spill(instrAn, I.INSTR _) = let
	       val _   = floatSpillsCnt := !floatSpillsCnt + 1
               val newR = C.newFreg()
    	       val instr' = Rewrite.frewriteDef(instr, reg, newR)
	     in  {code=
		    annotate(instrAn, instr')::
		      Float.spillInstr(annotations,newR,spillLoc), 
		  proh=[newR], 
		  newReg=SOME newR}
	     end
        in spill([], instr)
        end

   fun spillFreg{annotations,reg,src,spillLoc} = 
       (floatSpillsCnt := !floatSpillsCnt + 1;
        Float.spillInstr(annotations,src,spillLoc)
       )

   fun spillFtmp{annotations,reg,copy,spillLoc} = 
       (floatSpillsCnt := !floatSpillsCnt + 1;
        Float.spillCopyTmp(annotations,copy,spillLoc) 
       )

   (* Rename integer register *)
   fun renameR{fromSrc,toSrc,instr} = 
       let val _   = intRenamesCnt := !intRenamesCnt + 1
           val instr' = Rewrite.rewriteUse(instr, fromSrc, toSrc)
       in {code=[instr'], proh=[], newReg=SOME toSrc}
       end

   (* Reload integer register *)
   fun reloadR{annotations, reg, spillLoc, instr} = let
     fun reload(instrAn, I.ANNOTATION{a, i}) = reload(a::instrAn, i)
       | reload(instrAn, I.LIVE{regs, spilled}) = 
	  {code=[I.LIVE{regs=C.rmvReg(reg, regs), spilled=C.addReg(reg, spilled)}],
	   proh=[],
	   newReg=NONE}
       | reload(_, I.KILL _) = error "reloadR: KILL"
       | reload(instrAn, instr as I.INSTR _) = let
	   val _   = intReloadsCnt := !intReloadsCnt + 1
           val newR = C.newReg()
           val instr' = annotate(instrAn, Rewrite.rewriteUse(instr, reg, newR))
         in {code=Int.reloadInstr{an=annotations,dst=newR,spilledCell=reg,
				spillLoc=spillLoc} @ [instr'], 
             proh=[newR], newReg=SOME newR}
         end
   in reload([], instr)
   end

   fun reloadReg{annotations,reg,dst,spillLoc} = 
       (intReloadsCnt := !intReloadsCnt + 1;
        Int.reloadInstr{an=annotations,dst=dst,spilledCell=reg,
			spillLoc=spillLoc}
       )
                   
   (* Rename floating point register *)
   fun renameF{fromSrc,toSrc,instr} =
       let val _ = floatRenamesCnt := !floatRenamesCnt + 1
           val instr' = Rewrite.frewriteUse(instr, fromSrc, toSrc)
       in  {code=[instr'], proh=[], newReg=SOME toSrc}
       end

   (* Reload floating point register *)
   fun reloadF{annotations,reg,spillLoc,instr} = let
     fun reload(instrAn, I.ANNOTATION{a,i}) = reload(a::instrAn, i)
       | reload(instrAn, I.LIVE{regs, spilled}) = 
	  {code=[I.LIVE{regs=C.rmvFreg(reg, regs), spilled=C.addFreg(reg, spilled)}],
	   proh=[],
	   newReg=NONE}
       | reload(_, I.KILL _) = error "reloadF: KILL"
       | reload(instrAn, instr as I.INSTR _) = let
           val _ = floatReloadsCnt := !floatReloadsCnt + 1
           val newR = C.newFreg()
           val instr' = annotate(instrAn, Rewrite.frewriteUse(instr, reg, newR))
         in  {code=Float.reloadInstr(annotations,newR,spillLoc) @ [instr'], 
              proh=[newR], newReg=SOME newR}
         end
   in reload([], instr)
   end

   fun reloadFreg{annotations,reg,dst,spillLoc} =
       (floatReloadsCnt := !floatReloadsCnt + 1;
        Float.reloadInstr(annotations,dst,spillLoc) 
       )

   (* The generic register allocator *)
   structure Ra =
      RegisterAllocator
        (SpillHeur) 
        (* (ChowHennessySpillHeur) *)
        (ClusterRA 
          (structure Flowgraph = CFG
           structure Asm = Asm
           structure InsnProps = InsnProps
           structure Spill = Spill
          )
        )

   val KR = length Int.avail
   val KF = length Float.avail

   val params =
       [  { cellkind     = CellsBasis.GP,
            getreg       = GR.getreg,
            spill        = spillR,
            spillSrc     = spillReg,
            spillCopyTmp = spillTmp,
            reload       = reloadR,
            reloadDst    = reloadReg,
            renameSrc    = renameR,
            K            = KR,
            dedicated    = dedicatedR,
            copyInstr    = fn i => [Int.copy i],
            spillProh    = [],
            memRegs      = [],
            mode         = Int.mode
          } : Ra.raClient,
          { cellkind     = CellsBasis.FP,
            getreg       = FR.getreg,
            spill        = spillF,
            spillSrc     = spillFreg,
            spillCopyTmp = spillFtmp,
            reload       = reloadF,
            reloadDst    = reloadFreg,
            renameSrc    = renameF,
            K            = KF,
            dedicated    = dedicatedF,
            copyInstr    = fn i => [Float.copy i],
            spillProh    = [],
            memRegs      = [],
            mode         = Float.mode
          } : Ra.raClient
       ] : Ra.raClient list
  
   fun run cluster =
      (beginRA();
       GR.reset();
       FR.reset();
       Ra.ra params cluster
      )

end


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