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 /MLRISC/releases/release-110.64/IR/mlrisc-reshape-branches.sml
ViewVC logotype

Annotation of /MLRISC/releases/release-110.64/IR/mlrisc-reshape-branches.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 624 - (view) (download)
Original Path: sml/trunk/src/MLRISC/IR/mlrisc-reshape-branches.sml

1 : monnier 411 (*
2 :     * This module rearranges and eliminate branches in a problem to
3 :     * get better locality.
4 :     *
5 :     * -- Allen
6 :     *)
7 :    
8 : george 545 functor ReshapeBranches
9 :     ( structure IR : MLRISC_IR
10 :     structure InsnProps : INSN_PROPERTIES
11 :     sharing IR.I = InsnProps.I
12 :     ) : MLRISC_IR_OPTIMIZATION =
13 : monnier 245 struct
14 :    
15 :     structure IR = IR
16 :     structure CFG = IR.CFG
17 :     structure Dom = IR.Dom
18 :     structure Loop = IR.Loop
19 :     structure W = CFG.W
20 :     structure G = Graph
21 :     structure Util = IR.Util
22 :    
23 : george 545 type flowgraph = IR.IR
24 :    
25 : monnier 245 (*
26 :     * Restructure branches to in order to get better locality.
27 :     *)
28 : george 545 val name = "ReshapeBranches"
29 : monnier 245
30 : george 545 fun run IR =
31 : monnier 245 let val CFG as G.GRAPH cfg = IR
32 :     val Dom as G.GRAPH dom = IR.dom IR
33 :     val Loop as G.GRAPH loop = IR.loop IR
34 : monnier 429 val dominates = Dom.dominates Dom
35 : leunga 606 val labelOf = Util.labelOf CFG
36 : monnier 245 val changed = ref false
37 :    
38 :     exception GiveUp
39 :    
40 :     (* Check that a block does not have stupid pseudo ops that
41 :     * get in the way *)
42 :     fun no_pseudo_ops j =
43 :     let val CFG.BLOCK{data,...} = #node_info cfg j
44 :     in case !data of
45 :     [] => true
46 :     | _ => false
47 :     end
48 :    
49 :     (* Can block j has a new fallsthru entry? *)
50 :     fun can_fallsthru j =
51 :     case CFG.fallsThruFrom(CFG,j) of
52 :     NONE => no_pseudo_ops j
53 :     | SOME _ => false
54 :    
55 :     (* flip conditionals around *)
56 :     fun flip_cond should_flip (i,CFG.BLOCK{insns,...}) =
57 :     case (#out_edges cfg i,!insns) of
58 :     ([e1 as (_,j,CFG.EDGE{w=w1,k=k1 as CFG.BRANCH b1,a=a1}),
59 :     e2 as (_,k,CFG.EDGE{w=w2,k=k2 as CFG.BRANCH b2,a=a2})],
60 :     branch::rest) =>
61 : leunga 606 if j = k then (* targets are the same *)
62 :     let val a = ref(!a1 @ !a2)
63 :     in #set_out_edges cfg
64 :     (i, [(i,j,CFG.EDGE{w=ref(!w1 + !w2),k=CFG.JUMP,a=a})]);
65 :     insns := InsnProps.jump(labelOf j)::rest;
66 :     changed := true
67 :     end
68 :     else if should_flip(e1,e2) then
69 : george 545 let val branch' = InsnProps.negateConditional branch
70 : monnier 245 in if b1 andalso not(can_fallsthru j) orelse
71 :     b2 andalso not(can_fallsthru k) then
72 :     raise GiveUp
73 :     else ();
74 :     insns := branch'::rest;
75 :     CFG.removeEdge CFG e1;
76 :     CFG.removeEdge CFG e2;
77 :     #add_edge cfg (i,j,CFG.EDGE{w=w1,k=k2,a=a1});
78 :     #add_edge cfg (i,k,CFG.EDGE{w=w2,k=k1,a=a2});
79 :     Util.updateJumpLabel CFG i;
80 :     changed := true
81 :     end
82 :     else ()
83 :     | _ => ()
84 :    
85 : leunga 624 fun follow i =
86 :     let fun chase j =
87 :     case #out_edges cfg j of
88 :     [(_,k,_)] => if k = i then k else chase k
89 :     | _ => j
90 :     in chase i end
91 :    
92 : monnier 245 (* Falls thru case should be likely for forward branches. *)
93 :     fun should_flip_forward_branches(
94 :     (i,j,CFG.EDGE{w=w1,k=CFG.BRANCH b1,...}),
95 :     (_,k,CFG.EDGE{w=w2,k=CFG.BRANCH b2,...})) =
96 : leunga 624 (b1 andalso !w1 > !w2 andalso not(dominates(follow j,i)))
97 : monnier 245 orelse
98 : leunga 624 (b2 andalso !w2 > !w1 andalso not(dominates(follow k,i)))
99 : monnier 245 | should_flip_forward_branches _ = false
100 :    
101 :     (*
102 :     * Eliminate all fallsthru into a block j
103 :     *)
104 :     fun elim_fallsthru j =
105 :     let fun elim(e as (i,j,CFG.EDGE{k=CFG.BRANCH false,...})) =
106 :     flip_cond (fn _ => true) (i,#node_info cfg i)
107 :     | elim(e as (i,j,CFG.EDGE{k=CFG.FALLSTHRU,w,a,...})) =
108 :     let val i' as CFG.BLOCK{insns,...} = #node_info cfg i
109 : george 545 in insns := InsnProps.jump(
110 : monnier 245 CFG.defineLabel(#node_info cfg i))::(!insns);
111 :     CFG.removeEdge CFG e;
112 :     #add_edge cfg (i,j,CFG.EDGE{k=CFG.JUMP,a=a,w=w});
113 :     Util.updateJumpLabel CFG i;
114 :     changed := true
115 :     end
116 :     | elim _ = ()
117 :     in app elim (#in_edges cfg j)
118 :     end
119 :    
120 :     (*
121 :     * If a backedge is an unconditional jump,
122 :     * Try to eliminate it by changing it into a fallsthru.
123 :     *)
124 :     fun restructure_loop(_,Loop.LOOP{header,backedges=[],...}) = ()
125 :     | restructure_loop(_,Loop.LOOP{header,backedges=e::es,...}) =
126 :     if no_pseudo_ops header then
127 :     let fun find_best((e as (_,_,CFG.EDGE{w=w1,...}))::es,
128 :     best_e as (_,_,CFG.EDGE{w=w2,...})) =
129 : monnier 411 find_best(es,if !w1 > !w2 then e else best_e)
130 : monnier 245 | find_best([],best_e) = best_e
131 :     in case find_best(es,e) of
132 :     best_e as (i,j,CFG.EDGE{k=CFG.JUMP,w,a}) =>
133 :     if i <> header then
134 :     (let val _ = elim_fallsthru header
135 :     val _ = elim_fallsthru i
136 :     val CFG.BLOCK{insns,...} = #node_info cfg i
137 :     fun remove_jump(insns as jmp::rest) =
138 : george 545 if InsnProps.instrKind jmp = InsnProps.IK_JUMP then
139 : monnier 245 rest else insns
140 :     | remove_jump [] = []
141 :     in insns := remove_jump(!insns);
142 :     CFG.removeEdge CFG best_e;
143 :     #add_edge cfg (i,j,CFG.EDGE{k=CFG.FALLSTHRU,w=w,a=a});
144 :     changed := true
145 :     end handle _ => ())
146 :     else ()
147 :     | _ => ()
148 :     end
149 :     else ()
150 :    
151 :     (* Restructure conditionals branches *)
152 :     val restructure_conditionals =
153 :     flip_cond should_flip_forward_branches
154 :    
155 :     in #forall_nodes cfg (fn x => restructure_conditionals x handle _ => ());
156 :     #forall_nodes loop restructure_loop;
157 : george 545 if !changed then IR.changed IR else ();
158 : leunga 624 Util.mergeAllEdges IR;
159 : george 545 IR
160 : monnier 245 end
161 :    
162 :     end
163 :    

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