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/frequencies/estimate-loop-probs-fn.sml
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/frequencies/estimate-loop-probs-fn.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1150 - (view) (download)

1 : jhr 1147 (* estimate-loop-probs-fn.sml
2 :     *
3 :     * COPYRIGHT (c) 2002 Bell Labs, Lucent Technologies.
4 :     *
5 :     * Given a CFG that may have some existing edge probabilities
6 :     * (represented as BRANCHPROB annotations) add probabilities
7 :     * based on the loop structure using the heuristics from Ball-Larus
8 :     * and Wu-Larus.
9 : jhr 1149 *
10 :     * TODO:
11 :     * generalize to switch edges
12 :     * Loop Header Heuristic
13 : jhr 1147 *)
14 :    
15 :     functor EstimateLoopProbsFn (
16 :     structure CFG : CONTROL_FLOW_GRAPH
17 :     ) : sig
18 :    
19 :     structure CFG : CONTROL_FLOW_GRAPH
20 :    
21 :     val estimate : CFG.cfg -> unit
22 :    
23 :     end = struct
24 :    
25 :     structure CFG = CFG
26 :     structure Dom = DominatorTree(DirectedGraph)
27 :     structure LP = LoopStructure(
28 :     structure GraphImpl = DirectedGraph
29 :     structure Dom = Dom)
30 :     structure An = Annotations
31 :     structure Prob = Probability
32 :    
33 : jhr 1149 (* flags *)
34 :     val disable = MLRiscControl.mkFlag (
35 :     "disable-loop-probabilities",
36 :     "when true, loop probability estimates are disabled")
37 :     val dumpCFG = MLRiscControl.mkFlag (
38 :     "dump-cfg-jump-chain-elim",
39 :     "when true, flow graph is shown after loop probability estimates")
40 :     val dumpStrm = MLRiscControl.debug_stream
41 :    
42 : jhr 1147 local
43 :     structure A = MLRiscAnnotations
44 :     val {get, set, ...} = A.BRANCH_PROB
45 :     in
46 :     fun getEdgeProb (_, _, CFG.EDGE{a, ...}) = get(!a)
47 :     fun setEdgeProb ((_, _, CFG.EDGE{a, ...}), p) = a := set(p, !a)
48 :     end
49 :    
50 : jhr 1149 (* probabilities *)
51 :     val probLBH = Prob.percent 88 (* Loob Branch Heuristic *)
52 :     val probLEH = Prob.percent 80 (* Loop Exit Heuristic *)
53 : jhr 1147 val prob50_50 = 50
54 :    
55 :     (* Compute loop structure information *)
56 :     fun computeLoopStructure cfg = let
57 :     val domTree = Dom.makeDominator cfg
58 :     val dominates = Dom.dominates domTree
59 : jhr 1149 val Graph.GRAPH{has_node, forall_nodes, ...} = LP.loop_structure domTree
60 : jhr 1147 in
61 :     { isLoopHeader = has_node,
62 : jhr 1149 forallLoops = forall_nodes
63 : jhr 1147 }
64 :     end
65 :    
66 : jhr 1149 fun sameEdge ((_, _, CFG.EDGE{a, ...}), (_, _, CFG.EDGE{a=a', ...})) = (a = a')
67 :    
68 : jhr 1147 (* add loop probabilities *)
69 : jhr 1149 fun doEstimate (cfg as Graph.GRAPH{out_edges, ...}) = let
70 :     val {isLoopHeader, forallLoops} = computeLoopStructure cfg
71 :     fun computeProbs (trueE, falseE, takenProb) = let
72 :     val {t, f} = (case (getEdgeProb trueE, getEdgeProb falseE)
73 : jhr 1147 of (NONE, NONE) =>
74 :     {t=takenProb, f=Prob.-(Prob.always, takenProb)}
75 :     | (SOME p, _) =>
76 :     Prob.combineProb2 {trueProb=p, takenProb=takenProb}
77 :     | (_, SOME p) =>
78 :     Prob.combineProb2 {
79 :     trueProb=Prob.-(Prob.always, p),
80 :     takenProb=takenProb
81 :     }
82 :     (* end case *))
83 :     in
84 : jhr 1149 setEdgeProb (trueE, t);
85 :     setEdgeProb (falseE, f)
86 : jhr 1147 end
87 : jhr 1149 fun doLoop (hdrId, LP.LOOP{backedges, exits, ...}) = let
88 :     (* apply the Loop Branch Heuristic to a back edge *)
89 :     fun doBackEdge (e as (src, _, _)) = (case out_edges src
90 :     of [e1, e2] => if sameEdge(e, e1)
91 :     then computeProbs (e1, e2, probLBH)
92 :     else computeProbs (e2, e1, probLBH)
93 :     | _ => ()
94 :     (* end case *))
95 : jhr 1150 (* apply the Loop Exit Heuristic to an exit edges; note that
96 :     * the probability is that the loop will NOT be exited.
97 :     *)
98 : jhr 1149 fun doExitEdge (e as (src, _, _)) = (case out_edges src
99 :     of [e1, e2] =>
100 :     if sameEdge(e, e1)
101 :     then if isLoopHeader (#2 e2)
102 :     then ()
103 : jhr 1150 (* e1 is exit edge, so e2 is taken branch *)
104 :     else computeProbs (e2, e1, probLEH)
105 : jhr 1149 else if isLoopHeader (#2 e1)
106 :     then ()
107 : jhr 1150 (* e2 is exit edge, so e1 is taken branch *)
108 :     else computeProbs (e1, e2, probLEH)
109 : jhr 1149 | _ => ()
110 :     (* end case *))
111 :     in
112 :     List.app doBackEdge backedges;
113 :     List.app doExitEdge exits
114 :     end
115 : jhr 1147 in
116 : jhr 1149 forallLoops doLoop
117 : jhr 1147 end
118 :    
119 : jhr 1149 fun estimate cfg = if !disable
120 :     then ()
121 :     else (
122 :     doEstimate cfg;
123 :     if !dumpCFG
124 :     then CFG.dump (
125 :     !MLRiscControl.debug_stream,
126 :     "after loop probability estimates", cfg)
127 :     else ())
128 :    
129 : jhr 1147 end

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