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 545 - (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 : monnier 245 val changed = ref false
36 :    
37 :     exception GiveUp
38 :    
39 :     (* Check that a block does not have stupid pseudo ops that
40 :     * get in the way *)
41 :     fun no_pseudo_ops j =
42 :     let val CFG.BLOCK{data,...} = #node_info cfg j
43 :     in case !data of
44 :     [] => true
45 :     | _ => false
46 :     end
47 :    
48 :     (* Can block j has a new fallsthru entry? *)
49 :     fun can_fallsthru j =
50 :     case CFG.fallsThruFrom(CFG,j) of
51 :     NONE => no_pseudo_ops j
52 :     | SOME _ => false
53 :    
54 :     (* flip conditionals around *)
55 :     fun flip_cond should_flip (i,CFG.BLOCK{insns,...}) =
56 :     case (#out_edges cfg i,!insns) of
57 :     ([e1 as (_,j,CFG.EDGE{w=w1,k=k1 as CFG.BRANCH b1,a=a1}),
58 :     e2 as (_,k,CFG.EDGE{w=w2,k=k2 as CFG.BRANCH b2,a=a2})],
59 :     branch::rest) =>
60 :     if should_flip(e1,e2) then
61 : george 545 let val branch' = InsnProps.negateConditional branch
62 : monnier 245 in if b1 andalso not(can_fallsthru j) orelse
63 :     b2 andalso not(can_fallsthru k) then
64 :     raise GiveUp
65 :     else ();
66 :     insns := branch'::rest;
67 :     CFG.removeEdge CFG e1;
68 :     CFG.removeEdge CFG e2;
69 :     #add_edge cfg (i,j,CFG.EDGE{w=w1,k=k2,a=a1});
70 :     #add_edge cfg (i,k,CFG.EDGE{w=w2,k=k1,a=a2});
71 :     Util.updateJumpLabel CFG i;
72 :     changed := true
73 :     end
74 :     else ()
75 :     | _ => ()
76 :    
77 :     (* Falls thru case should be likely for forward branches. *)
78 :     fun should_flip_forward_branches(
79 :     (i,j,CFG.EDGE{w=w1,k=CFG.BRANCH b1,...}),
80 :     (_,k,CFG.EDGE{w=w2,k=CFG.BRANCH b2,...})) =
81 : monnier 411 (b1 andalso !w1 > !w2 andalso not(dominates(j,i)))
82 : monnier 245 orelse
83 : monnier 411 (b2 andalso !w2 > !w1 andalso not(dominates(k,i)))
84 : monnier 245 | should_flip_forward_branches _ = false
85 :    
86 :     (*
87 :     * Eliminate all fallsthru into a block j
88 :     *)
89 :     fun elim_fallsthru j =
90 :     let fun elim(e as (i,j,CFG.EDGE{k=CFG.BRANCH false,...})) =
91 :     flip_cond (fn _ => true) (i,#node_info cfg i)
92 :     | elim(e as (i,j,CFG.EDGE{k=CFG.FALLSTHRU,w,a,...})) =
93 :     let val i' as CFG.BLOCK{insns,...} = #node_info cfg i
94 : george 545 in insns := InsnProps.jump(
95 : monnier 245 CFG.defineLabel(#node_info cfg i))::(!insns);
96 :     CFG.removeEdge CFG e;
97 :     #add_edge cfg (i,j,CFG.EDGE{k=CFG.JUMP,a=a,w=w});
98 :     Util.updateJumpLabel CFG i;
99 :     changed := true
100 :     end
101 :     | elim _ = ()
102 :     in app elim (#in_edges cfg j)
103 :     end
104 :    
105 :     (*
106 :     * If a backedge is an unconditional jump,
107 :     * Try to eliminate it by changing it into a fallsthru.
108 :     *)
109 :     fun restructure_loop(_,Loop.LOOP{header,backedges=[],...}) = ()
110 :     | restructure_loop(_,Loop.LOOP{header,backedges=e::es,...}) =
111 :     if no_pseudo_ops header then
112 :     let fun find_best((e as (_,_,CFG.EDGE{w=w1,...}))::es,
113 :     best_e as (_,_,CFG.EDGE{w=w2,...})) =
114 : monnier 411 find_best(es,if !w1 > !w2 then e else best_e)
115 : monnier 245 | find_best([],best_e) = best_e
116 :     in case find_best(es,e) of
117 :     best_e as (i,j,CFG.EDGE{k=CFG.JUMP,w,a}) =>
118 :     if i <> header then
119 :     (let val _ = elim_fallsthru header
120 :     val _ = elim_fallsthru i
121 :     val CFG.BLOCK{insns,...} = #node_info cfg i
122 :     fun remove_jump(insns as jmp::rest) =
123 : george 545 if InsnProps.instrKind jmp = InsnProps.IK_JUMP then
124 : monnier 245 rest else insns
125 :     | remove_jump [] = []
126 :     in insns := remove_jump(!insns);
127 :     CFG.removeEdge CFG best_e;
128 :     #add_edge cfg (i,j,CFG.EDGE{k=CFG.FALLSTHRU,w=w,a=a});
129 :     changed := true
130 :     end handle _ => ())
131 :     else ()
132 :     | _ => ()
133 :     end
134 :     else ()
135 :    
136 :     (* Restructure conditionals branches *)
137 :     val restructure_conditionals =
138 :     flip_cond should_flip_forward_branches
139 :    
140 :     in #forall_nodes cfg (fn x => restructure_conditionals x handle _ => ());
141 :     #forall_nodes loop restructure_loop;
142 : george 545 if !changed then IR.changed IR else ();
143 :     IR
144 : monnier 245 end
145 :    
146 :     end
147 :    

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