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/ir-moved/compute-freq2.sml
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/ir-moved/compute-freq2.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 545 - (view) (download)

1 : monnier 467 (*
2 :     * This module computes frequencies when given branch probabilities.
3 :     * The last module still didn't work on irreducible flowgraphs!
4 :     * I'm rewriting it using a completely different algorithm.
5 :     *
6 :     * -- Allen
7 :     *)
8 :    
9 : george 545 functor ComputeFrequencies2
10 : monnier 467 (structure DerivedGraph : DERIVED_GRAPH
11 :     structure Freq : FREQ
12 :     ) : COMPUTE_FREQUENCIES2 =
13 :     struct
14 :    
15 :     structure Derived = DerivedGraph
16 :     structure W = Freq
17 :     structure G = Graph
18 :     structure A = Array
19 :     structure HT = HashTable
20 :    
21 :     val op div = W.div
22 :     val SOME inf = W.maxInt
23 :    
24 :     fun compute_frequencies
25 :     {cfg=G.GRAPH cfg,derived as G.GRAPH dg,
26 :     loopMultiplier,nodeFreq,edgeFreq,branchProb,isTakenBranch} =
27 :     let val ENTRY = case #entries cfg () of
28 :     [ENTRY] => ENTRY
29 :     | _ => raise Graph.NotSingleEntry
30 :     val N = #capacity cfg ()
31 :    
32 :     fun hash(i,j,_) = Word.<<(Word.fromInt i,0w16) + Word.fromInt j
33 : george 545 fun equal((a:int,b:int,_),(c,d,_)) = a = c andalso b = d
34 : monnier 467 exception NotThere
35 :     val edgeProbs = HT.mkTable (hash,equal) (10,NotThere)
36 :     val addProb = HT.insert edgeProbs
37 :     val getProb = HT.lookup edgeProbs
38 :    
39 :     fun computeEdgeProb(n,n') =
40 :     let fun divide_evenly(edges) =
41 :     let val W' = 100 div (length edges)
42 :     fun loop([],w) = ()
43 :     | loop([e],w) = addProb(e,w)
44 :     | loop(e::es,w) = (addProb(e,W'); loop(es,w-W'))
45 :     in loop(edges,100) end
46 :     val edges = #out_edges cfg n
47 :     in if n = ENTRY then divide_evenly edges else
48 :     case edges of
49 :     [] => ()
50 :     | [e] => addProb(e,100)
51 :     | [e1,e2] =>
52 :     let val prob = branchProb n'
53 :     val prob = if isTakenBranch e1 then prob else 100 - prob
54 :     in addProb(e1,prob);
55 :     addProb(e2,100-prob)
56 :     end
57 :     | es => divide_evenly es
58 :     end
59 :    
60 :     (* Initialize the set of edge probabilities *)
61 :     val _ = #forall_nodes cfg computeEdgeProb
62 :    
63 :     val visited = A.array(N,~1)
64 :    
65 :     fun process(scc as stamp::_,_) =
66 :     let val _ = app (fn b => A.update(visited,b,stamp)) scc
67 :     fun collect([],inFreq,isLoop) = (inFreq,isLoop)
68 :     | collect(n::ns,inFreq,isLoop) =
69 :     let fun loop([],inFreq,isLoop) = (inFreq,isLoop)
70 :     | loop((i,j,e)::es,inFreq,isLoop) =
71 :     if A.sub(visited,i) = stamp
72 :     then loop(es,inFreq,true)
73 :     else loop(es,inFreq +
74 :     !(nodeFreq(#node_info cfg i)) * getProb e,
75 :     isLoop)
76 :     val (inFreq,isLoop) = loop(#in_edges dg n,inFreq,isLoop)
77 :     in collect(ns,inFreq,isLoop) end
78 :     val (freq,isLoop) = collect(scc,0,false)
79 :     val freq = if stamp = ENTRY then
80 :     W.*(W.fromInt 100,length(#out_edges cfg ENTRY))
81 :     else if isLoop then freq * loopMultiplier div 100
82 :     else freq div 100
83 :     in app (fn b => nodeFreq(#node_info cfg b) := freq) scc
84 :     end
85 :    
86 :     in GraphSCC.strong_components (ReversedGraphView.rev_view derived)
87 :     process ();
88 :     HT.appi (fn ((i,_,e),w) =>
89 :     edgeFreq e := (w * !(nodeFreq(#node_info cfg i))) div 100)
90 :     edgeProbs
91 :     end handle Overflow => ()
92 :    
93 :     end

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