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/frequencies/estimate-loop-probs-fn.sml
 [smlnj] / sml / trunk / src / MLRISC / frequencies / estimate-loop-probs-fn.sml

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

revision 1148, Fri Mar 15 21:38:57 2002 UTC revision 1149, Sat Mar 16 19:55:14 2002 UTC
# Line 6  Line 6
6   * (represented as BRANCHPROB annotations) add probabilities   * (represented as BRANCHPROB annotations) add probabilities
7   * based on the loop structure using the heuristics from Ball-Larus   * based on the loop structure using the heuristics from Ball-Larus
8   * and Wu-Larus.   * and Wu-Larus.
9     *
10     * TODO:
11     *      generalize to switch edges
13   *)   *)
14
15  functor EstimateLoopProbsFn (  functor EstimateLoopProbsFn (
# Line 26  Line 30
30      structure An = Annotations      structure An = Annotations
31      structure Prob = Probability      structure Prob = Probability
32
33      (* 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      local      local
43        structure A = MLRiscAnnotations        structure A = MLRiscAnnotations
44        val {get, set, ...} = A.BRANCH_PROB        val {get, set, ...} = A.BRANCH_PROB
# Line 34  Line 47
47      fun setEdgeProb ((_, _, CFG.EDGE{a, ...}), p) = a := set(p, !a)      fun setEdgeProb ((_, _, CFG.EDGE{a, ...}), p) = a := set(p, !a)
48      end      end
49
50    (* the "Loop branch heuristic" *)    (* probabilities *)
51      val probLBH = Prob.percent 88      val probLBH = Prob.percent 88       (* Loob Branch Heuristic *)
52        val probLEH = Prob.percent 80       (* Loop Exit Heuristic *)
53      val prob50_50 = 50      val prob50_50 = 50
54
55    (* Compute loop structure information *)    (* Compute loop structure information *)
56      fun computeLoopStructure cfg = let      fun computeLoopStructure cfg = let
57            val domTree = Dom.makeDominator cfg            val domTree = Dom.makeDominator cfg
58            val dominates = Dom.dominates domTree            val dominates = Dom.dominates domTree
59            val Graph.GRAPH{has_node, ...} = LP.loop_structure domTree            val Graph.GRAPH{has_node,  forall_nodes, ...} = LP.loop_structure domTree
60            in            in
62                isBackEdge =                forallLoops = forall_nodes
fn (src, dst, _) => has_node dst andalso dominates(dst, src)
63              }              }
64            end            end
65
66        fun sameEdge ((_, _, CFG.EDGE{a, ...}), (_, _, CFG.EDGE{a=a', ...})) = (a = a')
67
69      fun estimate (cfg as Graph.GRAPH{forall_nodes, out_edges, ...}) = let      fun doEstimate (cfg as Graph.GRAPH{out_edges, ...}) = let
70            val {isLoopHeader, isBackEdge} = computeLoopStructure cfg            val {isLoopHeader, forallLoops} = computeLoopStructure cfg
71            fun edgeProb [e1, e2] = let            fun computeProbs (trueE, falseE, takenProb) = let
72                  fun computeProbs (trueE, falseE, takenProb) = (                  val {t, f} = (case (getEdgeProb trueE, getEdgeProb falseE)
case (getEdgeProb trueE, getEdgeProb falseE)
73                         of (NONE, NONE) =>                         of (NONE, NONE) =>
74                              {t=takenProb, f=Prob.-(Prob.always, takenProb)}                              {t=takenProb, f=Prob.-(Prob.always, takenProb)}
75                          | (SOME p, _) =>                          | (SOME p, _) =>
# Line 67  Line 81
81                                }                                }
82                        (* end case *))                        (* end case *))
83                  in                  in
84                    case (isBackEdge e1, isBackEdge e2)                    setEdgeProb (trueE, t);
85                     of (true, false) => let                    setEdgeProb (falseE, f)
val {t, f} = computeProbs(e1, e2, probLBH)
in
setEdgeProb(e1, t);
setEdgeProb(e2, f)
end
| (false, true) => let
val {t, f} = computeProbs(e2, e1, probLBH)
in
setEdgeProb(e2, t);
setEdgeProb(e1, f)
86                          end                          end
87              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 *)                        (* end case *))
95                  (* apply the Loop Exit Heuristic to an exit edges *)
96                    fun doExitEdge (e as (src, _, _)) = (case out_edges src
97                           of [e1, e2] =>
98                                if sameEdge(e, e1)
99                                  then if isLoopHeader (#2 e2)
100                                    then ()
101                                    else computeProbs (e1, e2, probLEH)
102                                  else if isLoopHeader (#2 e1)
103                                    then ()
104                                    else computeProbs (e2, e1, probLEH)
105                            | _ => ()
106                          (* end case *))
107                    in
108                      List.app doBackEdge backedges;
109                      List.app doExitEdge exits
110                  end                  end
| edgeProb _ = ()
fun doBlock (id, CFG.BLOCK{kind=CFG.NORMAL, ...}) =
edgeProb (out_edges id)
| doBlock _ = ()
111            in            in
112              forall_nodes doBlock              forallLoops doLoop
113            end            end
114
115        fun estimate cfg = if !disable
116              then  ()
117              else (
118                doEstimate cfg;
119                if !dumpCFG
120                  then CFG.dump (
121                      !MLRiscControl.debug_stream,
122                      "after loop probability estimates", cfg)
123                  else ())
124
125    end    end

Legend:
 Removed from v.1148 changed lines Added in v.1149