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

Diff of /sml/trunk/src/MLRISC/ra/getreg.sml

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

revision 410, Fri Sep 3 00:25:03 1999 UTC revision 411, Fri Sep 3 00:25:03 1999 UTC
# Line 5  Line 5 
5   *)   *)
6    
7  (** A simple round robin register allocator **)  (** A simple round robin register allocator **)
8  signature GETREG =  functor GetReg(val first : int  (* start from ``first'' *)
9      sig                 val nRegs : int  (* n registers *)
         exception GetReg  
         val getreg : {pref:int list, proh:int list} -> int  
         val reset : unit -> unit  
     end  
   
   
 functor GetReg(val nRegs : int  
10                 val available : int list) : GETREG =                 val available : int list) : GETREG =
11  struct  struct
12    exception GetReg    exception GetReg
13    val allRegs = Array.array(nRegs,false)    val size = first+nRegs
14      val allRegs = Array.array(size,false)
15    fun restore regs =    val preferred = Array.array(size,~1)
16          app(fn r => Array.update(allRegs,r,true)) regs  
17      val lastReg = ref first
18    fun prohibit regs =  
19          app(fn r => Array.update(allRegs,r,false)) regs    fun reset () = (lastReg := first; Array.modify(fn _ => ~1) preferred)
20    
21    fun find n = let    val _ = app (fn r => Array.update(allRegs,r,true)) available
22        fun search n = if Array.sub(allRegs,n) then n else search(n+1)  
23      in    fun getreg{pref,stamp,proh} =
24          (if Array.sub(allRegs,n) then n else find (n+1))    let (* use preferred registers whenever possible *)
25               handle _ => search 0        fun checkPreferred [] = find(!lastReg)
26            | checkPreferred(r::rs) =
27               if Array.sub(proh,r) <> stamp andalso
28                  Array.sub(allRegs,r) then r
29               else checkPreferred rs
30    
31          (* if not, use the round robin scheme to look for a register *)
32          and find(start) =
33              let val limit = Array.length allRegs
34                  fun search r =
35                  if Array.sub(proh,r) <> stamp andalso
36                     Array.sub(allRegs,r) then r
37                  else let val r = r+1
38                           val r = if r >= limit then first else r
39                       in  if r = start then raise GetReg
40                           else search r
41      end      end
42                  val found = search(start)
43                  val next = found + 1
44                  val next = if next >= limit then first else next
45              in  lastReg := next;
46                  found
47              end
48      in  checkPreferred pref end
49    
50    val lastReg = ref 0    fun getpair{pref,stamp,proh} =
51      let (* if not, use the round robin scheme to look for a register *)
52    fun reset () = lastReg:=0        fun find(start) =
53              let val limit = Array.length allRegs
54    val _ = restore available                fun search r =
55                  if Array.sub(proh,r) <> stamp andalso
56    fun checkPreferred [] = NONE                   Array.sub(proh,r+1) <> stamp andalso
57      | checkPreferred(x::xs) =                   Array.sub(allRegs,r) andalso
58          if Array.sub(allRegs,x) then SOME x else checkPreferred xs                   Array.sub(allRegs,r+1) then r
59                  else let val r = r+2
60    fun getreg{pref,proh} = let                         val r = if r >= limit then first else r
61        val _ = prohibit proh                     in  if r = start then raise GetReg
62      in                         else search r
         case checkPreferred pref  
         of NONE => let  
              val found =  
                find(!lastReg) handle _ => (restore proh; raise GetReg)  
            in  
              found before (lastReg := (found+1)mod nRegs;  
                            restore proh)  
63             end             end
64           | SOME found => found before restore proh                val found = search(start)
65                  val next = found + 2
66                  val next = if next >= limit then first else next
67              in  lastReg := next;
68                  found
69      end      end
70      in  find(!lastReg) end
71    
72  end  end
73    
74    
75    
76    
 (*  
  * $Log: getreg.sml,v $  
  * Revision 1.1.1.1  1998/04/08 18:39:02  george  
  * Version 110.5  
  *  
  *)  

Legend:
Removed from v.410  
changed lines
  Added in v.411

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