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

SCM Repository

[smlnj] Annotation of /sml/trunk/src/MLRISC/scheduling/bbScheduler.sml
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/scheduling/bbScheduler.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 775 - (view) (download)

1 : leunga 695 (*
2 :     * This is a very light weight, not very extensible, basic block scheduler.
3 :     * When you don't want to pay the price of all the global scheduling
4 :     * stuff.
5 :     *)
6 :     functor BBScheduler
7 :     (structure InsnProps : INSN_PROPERTIES
8 :     structure SchedProps : SCHEDULING_PROPERTIES
9 :     structure Rank : SCHEDULING_RANKS
10 :     where type edge = int
11 :     structure Viewer : BASIC_BLOCK_SCHEDULER_DDG_VIEWER
12 :     sharing Rank.DDG = Viewer.DDG
13 :     sharing Rank.DDG.I = InsnProps.I = SchedProps.I = Viewer.I
14 :     val prepass : bool
15 :     ) : BASIC_BLOCK_SCHEDULER =
16 :     struct
17 :     structure I = InsnProps.I
18 :     structure C = I.C
19 :     structure DDG = Rank.DDG
20 :     structure SchedProps = DDG.SchedProps
21 :     structure PQ = PriorityQueue
22 :     structure A = Array
23 :     structure DA = DynArray
24 :     structure G = Graph
25 :     structure Build =
26 :     BasicBlockSchedulerDDGBuilder
27 :     (structure DDG = DDG
28 :     structure InsnProps = InsnProps
29 :     structure SchedProps = SchedProps
30 :     )
31 :    
32 :     val view_ddg = MLRiscControl.getFlag "view-ddg"
33 :     val view_IR = MLRiscControl.getFlag "view-IR"
34 :    
35 :     val debug = MLRiscControl.getFlag "debug-scheduling"
36 :     val dump = MLRiscControl.getFlag "dump-test-block"
37 :     val id = MLRiscControl.getCounter "block-id"
38 :     val block = MLRiscControl.getInt "test-block"
39 :    
40 :     fun error msg = MLRiscErrorMsg.error("BBScheduler.",msg)
41 :    
42 : leunga 775 fun schedule {cpu} =
43 : leunga 695 let val cpu_info as
44 :     SchedProps.CPU_INFO
45 :     {newTable,findSlot,pipeline,insert,defUse,...} =
46 :     SchedProps.info{backward=true, cpu=SchedProps.cpu cpu}
47 : leunga 775 val split = SchedProps.splitCopies
48 : leunga 695
49 :     fun sched insns =
50 :     let val insns' = if prepass then
51 :     List.foldr List.revAppend [] (map split insns)
52 :     else insns
53 :     val N = length insns'
54 :     in if N <= 3 then insns else schedInsns'(N, insns')
55 :     end
56 :    
57 :     and schedInsns'(N, insns) =
58 :     (id := !id + 1;
59 :     if !debug andalso !id <> !block then insns else
60 :     let val _ = if !dump then dumpInsns("Before",insns) else ();
61 :     val insns = schedInsns(N, insns)
62 :     in if !debug then print("BLOCK "^Int.toString (!id)^"\n") else ();
63 :     if !dump then dumpInsns("After",insns) else ();
64 :     insns
65 :     end
66 :     )
67 :    
68 :     and dumpInsns(title, insns) =
69 :     (print(title^" BLOCK "^Int.toString (!id)^"\n");
70 :     app (fn i =>
71 :     let val (d,u) = defUse i
72 :     val d = map #1 d
73 : leunga 775 fun pr rs = app (fn r => print(C.toString r)) rs
74 :     in print(Viewer.toString i^"\n");
75 : leunga 695 (* print "defs="; pr d;
76 :     print " uses="; pr u;
77 :     print "\n" *) ()
78 :     end) (rev insns)
79 :     )
80 :     and schedInsns(N, insns) =
81 :     let val DDG as G.GRAPH ddg = DDG.newDDG(N)
82 :     val {succ, pred, nodes} = DDG.internalInfo DDG
83 : leunga 775 val _ = Build.buildDDG{ddg=DDG,cpu_info=cpu_info} insns
84 : leunga 695 val _ = if !view_IR andalso !view_ddg
85 : leunga 775 then Viewer.view DDG else ()
86 : leunga 695 val rank = Rank.rank DDG
87 :     val issueTimes = A.array(N,0)
88 :     val outDeg = A.array(N,0)
89 :     val instructions = DA.array(N, [])
90 :     val ready = PQ.create rank
91 :    
92 :     fun init (i,i') =
93 :     let val n = length(A.sub(succ,i))
94 :     in if n = 0 then PQ.insert ready (i,i')
95 :     else A.update(outDeg,i,n)
96 :     end
97 :    
98 :     fun updatePred(i) =
99 :     let fun process (j,i,latency) =
100 :     let val c = A.sub(outDeg,j)
101 :     in if c = 1 then PQ.insert ready (j,#node_info ddg j)
102 :     else A.update(outDeg,j,c-1)
103 :     end
104 :     in app process (A.sub(pred,i)) end
105 :    
106 :     fun findASlot(rt,i,i') =
107 :     let fun latest([],t) = t
108 :     | latest((i,j,latency)::es,t) =
109 :     latest(es,Int.min(t,A.sub(issueTimes,j)-latency-1))
110 :     val t = latest(A.sub(succ,i),0)
111 :     val p = pipeline i'
112 :     val t' = findSlot(rt,t,p)
113 :     in insert(rt,t',p);
114 :     DA.update(instructions,~t,i'::DA.sub(instructions,~t));
115 :     t'
116 :     end
117 :    
118 :     fun sched(rt) =
119 :     let val (i,i') = PQ.deleteMin ready
120 :     val t = findASlot(rt,i,i')
121 : leunga 775 in (*print("["^Int.toString t^"]"^Viewer.toString i'^"\n");*)
122 : leunga 695 A.update(issueTimes,i,t);
123 :     updatePred(i);
124 :     sched(rt)
125 :     end
126 :    
127 :     val _ = #forall_nodes ddg init
128 :     val rt = newTable(length insns)
129 :     val _ = sched(rt) handle PQ.EmptyPriorityQueue => ()
130 :    
131 :     fun linearize table =
132 :     DA.foldr (fn (instrs,l) => List.revAppend(instrs,l)) [] table
133 :    
134 :     in linearize instructions
135 :     end
136 :     in sched
137 :     end
138 :    
139 :     end

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