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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 775 - (view) (download)

1 : leunga 695 (*
2 :     * Build a DDG from a basic block
3 :     *)
4 :     functor BasicBlockSchedulerDDGBuilder
5 :     (structure DDG : SCHEDULER_DDG
6 :     structure InsnProps : INSN_PROPERTIES
7 :     sharing DDG.I = InsnProps.I
8 :     ) : BASIC_BLOCK_SCHEDULER_DDG_BUILDER =
9 :     struct
10 :    
11 :     structure DDG = DDG
12 :     structure I = DDG.I
13 :     structure C = I.C
14 :     structure SchedProps = DDG.SchedProps
15 : leunga 775 structure H = C.ColorTable
16 : leunga 695 structure G = Graph
17 :    
18 :     type architecture = string
19 :     type ddg = (I.instruction,DDG.latency) DDG.ddg
20 :    
21 :     fun error msg = MLRiscErrorMsg.error("BasicBlockSchedulerDDGBuilder",msg)
22 :    
23 :     val COPY_LATENCY = 0
24 : leunga 775
25 :     exception NotThere
26 :    
27 : leunga 695 (*
28 :     * Build a DAG from a list of instructions (in reverse order)
29 :     * This is just a simple def/use analysis.
30 :     *)
31 : leunga 775 fun buildDDG{cpu_info,ddg=G.GRAPH ddg} =
32 : leunga 695 let val SchedProps.CPU_INFO{defUse,...} = cpu_info
33 :     fun buildDAG insns =
34 : leunga 775 let val defMap = H.mkTable(31,NotThere)
35 :     val useMap = H.mkTable(31,NotThere)
36 :     val findUse = H.find useMap
37 :     val findDef = H.find defMap
38 :     val rmvUse = H.remove useMap
39 :     val rmvDef = H.remove defMap
40 :     fun lookupUse r = case findUse r of NONE => [] | SOME x => x
41 :     fun lookupDef r = case findDef r of NONE => [] | SOME x => x
42 :     val insertUse = H.insert useMap
43 :     val insertDef = H.insert defMap
44 :    
45 : leunga 695 fun flowDep i (r,latency) =
46 : leunga 775 app (fn j => #add_edge ddg (i,j,latency)) (lookupUse r)
47 : leunga 695 fun outputDep i (r,_) =
48 : leunga 775 app (fn j => #add_edge ddg (i,j,~1)) (lookupDef r)
49 : leunga 695 fun antiDep i r =
50 : leunga 775 app (fn j => #add_edge ddg (i,j,~1)) (lookupDef r)
51 : leunga 695 fun ctrlDep i j = #add_edge ddg (i,j,~1)
52 : leunga 775 fun addDefs n (r,l) = (rmvUse r; insertDef(r, [n]))
53 :     fun addUses n r = insertUse(r,n::lookupUse r)
54 : leunga 695
55 :     fun copyDstSrc i' =
56 :     let val (dst, src) = InsnProps.moveDstSrc i'
57 :     fun coalesce(d::ds, s::ss, dst, src) =
58 : leunga 775 if C.sameColor(d,s) then coalesce(ds, ss, dst, src)
59 :     else coalesce(ds, ss, (d,COPY_LATENCY)::dst, s::src)
60 : leunga 695 | coalesce([], [], dst, src) = (dst, src)
61 :     | coalesce _ = error "coalesce"
62 :    
63 :     val (dst, src) = coalesce(dst, src, [], [])
64 :     val dst = case InsnProps.moveTmpR i' of
65 :     NONE => dst
66 : leunga 775 | SOME tmp => (tmp,~1)::dst
67 : leunga 695 in (dst, src) end
68 :    
69 :     fun scan(i,[],branches,succs) = ()
70 :     | scan(i,i'::insns,branches,succs) =
71 :     let val _ = #add_node ddg (i,i') (* create node *)
72 :     val kind = InsnProps.instrKind i'
73 :     val (defs,uses) =
74 :     case kind of
75 :     InsnProps.IK_COPY => copyDstSrc i'
76 : leunga 775 | _ => defUse i'
77 : leunga 695 val _ = #add_node ddg (i,i')
78 :     val _ = app (flowDep i) defs
79 :     val _ = app (outputDep i) defs
80 :     val _ = app (antiDep i) uses
81 :     val _ = app (ctrlDep i) branches
82 :     val _ = app (addDefs i) defs
83 :     val _ = app (addUses i) uses
84 :     val branches =
85 :     case kind of
86 :     InsnProps.IK_JUMP => [i]
87 :     | InsnProps.IK_CALL => (app (ctrlDep i) succs; [i])
88 :     | _ => branches
89 :     in scan(i+1,insns,branches,i::succs)
90 :     end
91 :     in scan(0,insns,[],[])
92 :     end
93 :     in buildDAG
94 :     end
95 :    
96 :     end

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