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

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