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/static-branch-prediction.sml
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/IR/static-branch-prediction.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 246 - (view) (download)

1 : monnier 245 functor StaticBranchPredictionFn(IR : MLRISC_IR) : STATIC_BRANCH_PREDICTION =
2 :     struct
3 :    
4 :     structure IR = IR
5 :     structure Loop = IR.Loop
6 :     structure CFG = IR.CFG
7 :     structure I = IR.I
8 :     structure G = Graph
9 :     structure W = CFG.W
10 :     structure S = BitSet
11 :     structure A = Array
12 :     structure H = HashArray
13 :    
14 :     infix ==
15 :    
16 :     val op + = W.+
17 :     val op - = W.-
18 :     val op div = W.div
19 :     val op == = W.==
20 :    
21 :     fun profile {loopMultiplier,branchProb} IR =
22 :     let val CFG as G.GRAPH cfg = IR
23 :     val L as G.GRAPH loop = IR.loop IR
24 :     val [ENTRY] = #entries cfg ()
25 :     val N = #capacity cfg ()
26 :     val marked = S.create N
27 :     val number_of_entries = length(#out_edges cfg ENTRY)
28 :     val entry_weight = W.scale(W.fromInt 100,number_of_entries)
29 :    
30 :     val likely_exits = H.array(N,[])
31 :     val exit_counts = H.array(N,0)
32 :     val entry_edges = A.tabulate(N,#in_edges cfg)
33 :     val header_of = A.array(N,ENTRY)
34 :     val TIMES = 20
35 :    
36 :     (* is an edge unlikely? *)
37 :     fun is_unlikely_edge (i,j,CFG.EDGE{k=CFG.BRANCH true,...}) =
38 :     branchProb(#node_info cfg i) = 0
39 :     | is_unlikely_edge _ = false
40 :    
41 :     fun is_exit_edge (e as (i,j,_)) =
42 :     List.exists (fn (i',j',_) => i = i' andalso j = j')
43 :     (H.sub(likely_exits,A.sub(header_of,i)))
44 :    
45 :     val sum = List.foldr (fn ((_,_,CFG.EDGE{w,...}),m) => !w + m) W.zero
46 :    
47 :     fun exit_weight_of i =
48 :     let val h = A.sub(header_of,i)
49 :     val CFG.BLOCK{freq=ref w, ...}= #node_info cfg h
50 :     in w div (loopMultiplier * H.sub(exit_counts,h))
51 :     end
52 :    
53 :     fun preprocess(header,Loop.LOOP{backedges,exits,loop_nodes,...}) =
54 :     let fun is_backedge (i,j,_) =
55 :     List.exists(fn (i',j',_) => i = i' andalso j = j') backedges
56 :     val real_exits = List.filter (fn e => not(is_unlikely_edge e)) exits
57 :     in H.update(likely_exits,header,real_exits);
58 :     H.update(exit_counts,header,length real_exits);
59 :     A.update(entry_edges,header,
60 :     List.filter (fn e => not(is_backedge e)) (#in_edges cfg header));
61 :     app (fn i => A.update(header_of,i,header)) (header::loop_nodes)
62 :     end
63 :    
64 :     fun propagate(0,_) = ()
65 :     | propagate(n,[]) = ()
66 :     | propagate(n,i::worklist) =
67 :     let val _ = S.reset(marked,i)
68 :     val CFG.BLOCK{freq,...} = #node_info cfg i
69 :     val old_weight = !freq
70 :     val new_weight = sum(A.sub(entry_edges,i))
71 :     val new_weight = if i = ENTRY then entry_weight
72 :     else if #has_node loop i then
73 :     W.scale(new_weight,loopMultiplier)
74 :     else new_weight
75 :     in if old_weight == new_weight then
76 :     propagate(n,worklist)
77 :     else (freq := new_weight;
78 :     propagate_edge_weight(#out_edges cfg i,new_weight,[]);
79 :     propagate'(n,#out_edges cfg i,worklist)
80 :     )
81 :     end
82 :    
83 :     and propagate'(n,[],worklist) = propagate(n,worklist)
84 :     | propagate'(n,(i,j,_)::es,worklist) =
85 :     if S.markAndTest(marked,j) then
86 :     propagate'(n,es,worklist)
87 :     else propagate'(Int.-(n,1),es,j::worklist)
88 :    
89 :     and propagate_edge_weight([],W,es') = process_non_exits(W,es')
90 :     | propagate_edge_weight((e as (i,_,CFG.EDGE{w,...}))::es,W,es') =
91 :     if is_exit_edge e then
92 :     let val exit_weight = exit_weight_of(A.sub(header_of,i))
93 :     in w := exit_weight;
94 :     propagate_edge_weight(es,W-exit_weight,es')
95 :     end
96 :     else
97 :     propagate_edge_weight(es,W,e::es')
98 :    
99 :     and process_non_exits(W,[]) = ()
100 :     | process_non_exits(W,[(_,_,CFG.EDGE{w,...})]) = w := W
101 :     | process_non_exits(W,es as
102 :     [(i,_,CFG.EDGE{w,k=CFG.BRANCH b,...}),
103 :     (_,_,CFG.EDGE{w=w',k=CFG.BRANCH _,...})]) =
104 :     let val (w_F,w_T) = if b then (w',w) else (w,w')
105 :     val p = branchProb(#node_info cfg i)
106 :     in w_F := W.scale(W,Int.-(100,p)) div 100;
107 :     w_T := W.scale(W,p) div 100
108 :     end
109 :     | process_non_exits(W,es) = divide_evenly(W,es)
110 :    
111 :     and divide_evenly(W,es) =
112 :     let val W' = W div (length es)
113 :     in app (fn (_,_,CFG.EDGE{w,...}) => w := W') es
114 :     end
115 :    
116 :     in
117 :     #forall_nodes loop preprocess;
118 :     propagate(TIMES * N, [ENTRY])
119 :     end
120 :    
121 :     end

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