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
ViewVC logotype

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

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

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
12     *      Loop Header Heuristic
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
61              { isLoopHeader = has_node,              { isLoopHeader = has_node,
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    
68    (* add loop probabilities *)    (* add loop probabilities *)
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

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