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/compiler/CodeGen/x86/x86CG.sml
ViewVC logotype

View of /sml/trunk/src/compiler/CodeGen/x86/x86CG.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 576 - (download) (annotate)
Fri Mar 10 07:27:16 2000 UTC (19 years, 5 months ago) by leunga
File size: 13649 byte(s)

More assembly output problems involving the indexed addressing mode
on the x86 have been found and corrected. Thanks to Fermin Reig for the
fix.

The interface and implementation of the register allocator have been changed
slightly to accommodate the possibility to skip the register allocation
phases completely and go directly to memory allocation.  This is needed
for C-- use.

This fix only affects the x86 assembly output.
(*
 * X86 specific backend.  This one uses the new RA8 scheme.
 *)
structure X86CG = 
  MachineGen
  ( structure I          = X86Instr
    structure F          = X86FlowGraph
    structure R          = X86CpsRegs
    structure CG         = Control.CG

    structure MachSpec   = X86Spec
    structure PseudoOps  = X86PseudoOps
    structure CpsRegs    = X86CpsRegs
    structure InsnProps  = X86Props
    structure Asm        = X86AsmEmitter
    structure Shuffle    = X86Shuffle

    val spill = CPSRegions.spill 
    val stack = CPSRegions.stack 
    val esp   = I.C.esp

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

    structure MLTreeComp=
       X86(structure X86Instr=X86Instr
           structure X86MLTree=X86MLTree
           structure ExtensionComp = SMLNJMLTreeExtComp
               (structure I = X86Instr
                structure T = X86MLTree
               )
           val tempMem=I.Displace{base=esp, disp=I.Immed 304, mem=stack}
           datatype arch = Pentium | PentiumPro | PentiumII | PentiumIII
           val arch = ref Pentium (* Lowest common denominator *)
          )

    structure X86Jumps = 
       X86Jumps(structure Instr=X86Instr
                structure AsmEmitter=X86AsmEmitter
                structure Shuffle=X86Shuffle
                structure MCEmitter=X86MCEmitter)
   
    structure BackPatch = 
       BackPatch(structure Jumps=X86Jumps
                 structure Emitter=X86MCEmitter
                 structure Props=InsnProps
                 structure Flowgraph=X86FlowGraph
                 structure Asm=X86AsmEmitter
                 structure CodeString=CodeString)

    structure PrintFlowGraph=
       PrintCluster(structure Flowgraph=X86FlowGraph
                    structure Asm = X86AsmEmitter)

    structure X86Spill = X86Spill(structure Instr=I structure Props=InsnProps)

    val toInt32 = Int32.fromInt
    fun cacheOffset r = I.Immed(toInt32(X86Runtime.vregStart + 
                                Word.toIntX(Word.<<(Word.fromInt(r-8),0w2))))

    val intSpillCnt = MLRiscControl.getCounter "ra-int-spills"
    val floatSpillCnt = MLRiscControl.getCounter "ra-float-spills"
    val intReloadCnt = MLRiscControl.getCounter "ra-int-reloads"
    val floatReloadCnt = MLRiscControl.getCounter "ra-float-reloads"
    val intRenameCnt = MLRiscControl.getCounter "ra-int-renames"
    val floatRenameCnt = MLRiscControl.getCounter "ra-float-renames"
    val x86CfgDebugFlg = MLRiscControl.getFlag "x86-cfg-debug"
(*
    val deadcode = MLRiscControl.getCounter "x86-dead-code"
    val deadblocks = MLRiscControl.getCounter "x86-dead-blocks"
 *)

    structure RA = 
    struct
      structure F = F

      (* For dead code elimination *)
      exception X86DeadCode
      val affectedBlocks = Intmap.new(32,X86DeadCode) : bool Intmap.intmap
      val deadRegs       = Intmap.new(32,X86DeadCode) : bool Intmap.intmap
      fun removeDeadCode(F.CLUSTER{blocks, ...}) =
      let val isDead = Intmap.mapWithDefault(deadRegs, false) 
          val isAffected = Intmap.mapWithDefault(affectedBlocks, false) 
          fun isDeadInstr(I.ANNOTATION{i, ...}) = isDeadInstr i 
            | isDeadInstr(I.MOVE{dst=I.Direct rd, ...}) = isDead rd
            | isDeadInstr(I.MOVE{dst=I.MemReg rd, ...}) = isDead rd
            | isDeadInstr(I.COPY{dst=[rd], ...}) = isDead rd
            | isDeadInstr _ = false
          fun scan [] = ()
            | scan(F.BBLOCK{blknum, insns, ...}::rest) =
              (if isAffected blknum then 
                  ((* deadblocks := !deadblocks + 1; *)
                   insns := elim(!insns, [])
                  ) else ();
               scan rest)
            | scan(_::rest) = scan rest
         and elim([], code) = rev code
           | elim(i::instrs, code) = 
            if isDeadInstr i then 
               ((* deadcode := !deadcode + 1; *) elim(instrs, code))
            else elim(instrs, i::code)
      in if Intmap.elems affectedBlocks > 0 then scan blocks else ()
      end

      (* This function finds out which pseudo memory registers are unused.
       * Those that are unused are made available for spilling.
       * The register allocator calls this function right before spilling 
       * a set of nodes.
       *)
      local 
         open RAGraph
      in  
         val firstSpill = ref true
         fun spillInit(GRAPH{nodes, ...}, I.C.GP) = 
             if !firstSpill then (* only do this once! *)
             let val lookup = Intmap.map nodes
                 fun find(r, free) =
                     if r >= 10 then (* note, %8 and %9 are reserved! *)
                        let val free = 
                                case lookup r of
                                  NODE{uses=ref [], defs=ref [], ...} => 
                                     cacheOffset r::free
                                | _ => free
                        in  find(r-1, free) end
                     else 
                        free
                 val free = find(31 (* X86Runtime.numVregs+8-1 *), [])
              in firstSpill := false;
                 X86StackSpills.setAvailableOffsets free
              end 
              else ()
            | spillInit(GRAPH{nodes, ...}, _) = ()
      end
 
      (* This is the generic register allocator *)
      structure Ra = 
        RegisterAllocator
         (ChowHennessySpillHeur)
         (MemoryRA             (* for memory coalescing *)
           (RADeadCodeElim     (* do the funky dead code elimination stuff *)
              (ClusterRA
                 (structure Flowgraph = F
                  structure Asm = X86AsmEmitter
                  structure InsnProps = InsnProps
                 )
              )
              (fun cellkind I.C.GP = true | cellkind _ = false
               val deadRegs = deadRegs
               val affectedBlocks = affectedBlocks
               val spillInit = spillInit
              )
           )
        )


      (* -------------------------------------------------------------------
       * Floating point stuff 
       * -------------------------------------------------------------------*)
      structure FR = GetReg(val nRegs=32 
                            val available=R.availF 
                            val first=32)

      val KF = length R.availF
  
      fun copyInstrF((rds as [_], rss as [_]), _) =
            [I.FCOPY{dst=rds, src=rss, tmp=NONE}]
        | copyInstrF((rds, rss), I.FCOPY{tmp, ...}) = 
            [I.FCOPY{dst=rds, src=rss, tmp=tmp}]
  
      fun getFregLoc loc = 
          I.Displace{base=esp, disp=X86StackSpills.getFregLoc loc, mem=spill}
  
      (* spill floating point *)
      fun spillF{instr, reg, spillLoc, kill, regmap, annotations} = 
          (floatSpillCnt := !floatSpillCnt + 1;
           X86Spill.fspill(instr, regmap, reg, getFregLoc spillLoc) 
          )
  
      fun spillFreg{src, reg, spillLoc, annotations} = 
         (floatSpillCnt := !floatSpillCnt + 1;
          [I.FLDL(I.FDirect(src)), I.FSTPL(getFregLoc spillLoc)]
         )

      fun spillFcopyTmp{copy=I.FCOPY{dst, src, ...}, spillLoc, annotations} =
          (floatSpillCnt := !floatSpillCnt + 1;
           I.FCOPY{dst=dst, src=src, tmp=SOME(getFregLoc spillLoc)}
          )

      (* rename floating point *)
      fun renameF{instr, fromSrc, toSrc, regmap} =
          (floatRenameCnt := !floatRenameCnt + 1;
           X86Spill.freload(instr, regmap, fromSrc, I.FDirect toSrc)
          )

      (* reload floating point *)
      fun reloadF{instr, reg, spillLoc, regmap, annotations} = 
          (floatReloadCnt := !floatReloadCnt + 1;
           X86Spill.freload(instr, regmap, reg, getFregLoc spillLoc)
          )

      fun reloadFreg{dst, reg, spillLoc, annotations} = 
          (floatReloadCnt := !floatReloadCnt + 1;
           [I.FLDL(getFregLoc spillLoc), I.FSTPL(I.FDirect dst)]
          )

      (* -------------------------------------------------------------------
       * Integer 8 stuff 
       * -------------------------------------------------------------------*)
      fun memToMemMove{dst, src} =
          let val tmp = I.C.newReg() 
          in  [I.MOVE{mvOp=I.MOVL,src=src,dst=I.Direct tmp},
               I.MOVE{mvOp=I.MOVL,src=I.Direct tmp,dst=dst}
              ]
          end

      fun copyInstrR((rds as [d], rss as [s]), _) =
          if d = s then [] else 
          (case (d >= 8 andalso d < 32, s >= 8 andalso s < 32) of
            (false, false) => [I.COPY{dst=rds, src=rss, tmp=NONE}]
          | (true, false) => [I.MOVE{mvOp=I.MOVL,src=I.Direct s,dst=I.MemReg d}]
          | (false, true) => [I.MOVE{mvOp=I.MOVL,src=I.MemReg s,dst=I.Direct d}]
          | (true, true) => memToMemMove{src=I.MemReg s, dst=I.MemReg d}
          )
        | copyInstrR((rds, rss), I.COPY{tmp, ...}) = 
           [I.COPY{dst=rds, src=rss, tmp=tmp}]
  
      val getRegLoc' = X86StackSpills.getRegLoc

      fun getRegLoc(spillLoc) = 
               (* Is it a memory register? *)
          if spillLoc >= 0 then I.MemReg spillLoc 
               (* No, logical spill locations... *)
          else I.Displace{base=esp, disp=getRegLoc' spillLoc, mem=spill}
          
  
      structure GR8 = GetReg(val nRegs=8 val available=X86CpsRegs.availR
                             val first=0)
   
      val K8 = length X86CpsRegs.availR
  
       (* register allocation for general purpose registers *)
      fun spillR8{instr, reg, spillLoc, kill, regmap, annotations} = 
          (intSpillCnt := !intSpillCnt + 1;
           X86Spill.spill(instr, regmap, reg, getRegLoc spillLoc)
          ) 

      fun spillReg{src, reg, spillLoc, annotations} = 
          let val _ = intSpillCnt := !intSpillCnt + 1;
              val dstLoc = getRegLoc spillLoc
              val isMemReg = src >= 8 andalso src < 32 
              val srcLoc = if isMemReg then I.MemReg src else I.Direct src
          in  if InsnProps.eqOpn(srcLoc, dstLoc) then []
              else if isMemReg then memToMemMove{dst=dstLoc, src=srcLoc}
              else [I.MOVE{mvOp=I.MOVL, src=srcLoc, dst=dstLoc}]
          end

      fun spillCopyTmp{copy=I.COPY{src, dst,...}, spillLoc, annotations} = 
          (intSpillCnt := !intSpillCnt + 1;
           I.COPY{dst=dst, src=src, tmp=SOME(getRegLoc spillLoc)}
          )
     
      fun renameR8{instr, fromSrc, toSrc, regmap} = 
          (intRenameCnt := !intRenameCnt + 1;
           X86Spill.reload(instr, regmap, fromSrc, I.Direct toSrc)
          )

      fun reloadR8{instr, reg, spillLoc, regmap, annotations} = 
          (intReloadCnt := !intReloadCnt + 1;
           X86Spill.reload(instr, regmap, reg, getRegLoc spillLoc)
          ) 

      fun reloadReg{dst, reg, spillLoc, annotations} = 
          let val _ = intReloadCnt := !intReloadCnt + 1
              val srcLoc = getRegLoc spillLoc
              val isMemReg = dst >= 8 andalso dst < 32 
              val dstLoc = if isMemReg then I.MemReg dst else I.Direct dst
          in  if InsnProps.eqOpn(srcLoc,dstLoc) then []
              else if isMemReg then memToMemMove{dst=dstLoc, src=srcLoc}
              else [I.MOVE{mvOp=I.MOVL, src=srcLoc, dst=dstLoc}]
          end

      fun spillInit () = 
        (firstSpill := true;
         Intmap.clear affectedBlocks; 
         Intmap.clear deadRegs;
         X86StackSpills.init(); FR.reset(); GR8.reset())

      (* Dedicated + available registers *)
      fun mark(a, l) = app (fn r => Array.update(a, r, true)) l

      val dedicatedR = Array.array(32,false)
      val dedicatedF = Array.array(64,false)
      val _ = mark(dedicatedR, R.dedicatedR)
      val _ = mark(dedicatedF, R.dedicatedF)
 
      fun ra(cluster as F.CLUSTER{regmap, ...}) = 
      let val printGraph = 
              if !x86CfgDebugFlg then 
                 PrintFlowGraph.printCluster(!CG.printFlowgraphStream)
              else fn msg => fn _ => () 
  
          val _ = spillInit()
  
          (* generic register allocator *)

          val cluster = Ra.ra
                         [ {spill     = spillR8,
                            spillSrc  = spillReg,
                            spillCopyTmp= spillCopyTmp,
                            reload    = reloadR8,
                            reloadDst = reloadReg,
                            renameSrc = renameR8,
                            copyInstr = copyInstrR,
                            K         = K8,
                            getreg    = GR8.getreg,
                            cellkind  = I.C.GP,   
                            dedicated = dedicatedR,
                            spillProh = [],
                            memRegs   = [(8,31)],
                            mode      = Ra.SPILL_PROPAGATION+Ra.SPILL_COLORING
                           },
                           {spill     = spillF,
                            spillSrc  = spillFreg,
                            spillCopyTmp= spillFcopyTmp,
                            reload    = reloadF,
                            reloadDst = reloadFreg,
                            renameSrc = renameF,
                            copyInstr = copyInstrF,
                            K         = KF,
                            getreg    = FR.getreg,
                            cellkind  = I.C.FP,   
                            dedicated = dedicatedF,
                            spillProh = [],
                            memRegs   = [],
                            mode      = Ra.SPILL_PROPAGATION
                           }] cluster
          val _ = removeDeadCode cluster
          val _ = printGraph "\t---After register allocation K=8---\n" cluster
      in  cluster
      end

    end (* RegAllocation *)

  ) 


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