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/mlrisc-branch-chaining.sml
ViewVC logotype

Annotation of /sml/trunk/src/MLRISC/IR/mlrisc-branch-chaining.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 657 - (view) (download)

1 : leunga 591 (*
2 :     * This module performs branches chaining
3 :     *
4 :     * -- Allen
5 :     *)
6 :    
7 :     functor BranchChaining
8 :     (structure IR : MLRISC_IR
9 :     structure InsnProps : INSN_PROPERTIES
10 :     sharing IR.I = InsnProps.I
11 :     ) : MLRISC_IR_OPTIMIZATION =
12 :     struct
13 :    
14 :     structure IR = IR
15 :     structure CFG = IR.CFG
16 :     structure G = Graph
17 :     structure Util = IR.Util
18 :     structure A = Array
19 :    
20 :     type flowgraph = IR.IR
21 :    
22 :     val name = "BranchChaining"
23 :    
24 : leunga 657 fun error msg = MLRiscErrorMsg.error("BranchChaining",msg)
25 :    
26 :     val branchChainingCount = MLRiscControl.getCounter "branch-chaining-count"
27 :    
28 : leunga 591 fun run (IR as G.GRAPH cfg : IR.IR) =
29 :     let exception NoTarget
30 :     val N = #capacity cfg ()
31 :    
32 :     (* Performs branch chaining *)
33 :     val branchMap = Intmap.new(13, NoTarget) : G.node_id Intmap.intmap
34 :     val addBranch = Intmap.add branchMap
35 :     val lookupBranch = Intmap.map branchMap
36 :    
37 :     val visited = A.array(N, ~1)
38 :     val stamp = ref 0
39 :    
40 :     val changed = ref false
41 :    
42 : leunga 657 val regmap = CFG.regmap IR
43 :     val lookup = IR.I.C.lookup regmap
44 :    
45 :     fun isTrivialCopy(instr) =
46 :     let fun isTrivial([], []) = true
47 :     | isTrivial(d::ds, s::ss) =
48 :     lookup d = lookup s andalso isTrivial(ds,ss)
49 :     | isTrivial _ = error "isTrivialCopy"
50 :     val (dst, src) = InsnProps.moveDstSrc instr
51 :     in isTrivial(dst, src)
52 :     end
53 :    
54 :     fun isNop(instr) =
55 :     case InsnProps.instrKind instr of
56 :     InsnProps.IK_NOP => true
57 :     | InsnProps.IK_COPY => isTrivialCopy(instr)
58 :     | _ => false
59 :    
60 :     fun isAllNop [] = true
61 :     | isAllNop (i::is) = isNop i andalso isAllNop is
62 :    
63 : leunga 591 (* Given a blockId, finds out which block it really branches to
64 :     * eventually. The visited array is to prevent looping in programs
65 :     * with self-loops. If NO_BRANCH_CHAINING is set on a jump, we also
66 :     * terminate there.
67 :     *)
68 :     fun chase blockId =
69 :     let val st = !stamp
70 :     val _ = stamp := !stamp + 1;
71 :     fun follow blockId =
72 :     lookupBranch blockId
73 :     handle NoTarget =>
74 :     if A.sub(visited,blockId) = st then blockId
75 :     else
76 :     (A.update(visited, blockId, st);
77 :     case #node_info cfg blockId of
78 : leunga 657 CFG.BLOCK{insns=ref [], ...} =>
79 :     (* falls thru to next *)
80 : leunga 591 (case #out_edges cfg blockId of
81 :     [(_,next,CFG.EDGE{k=CFG.FALLSTHRU, ...})] =>
82 :     follow next
83 :     | _ => blockId (* terminates here *)
84 :     )
85 : leunga 657 | CFG.BLOCK{insns=ref(insns as jmp::rest), ...} =>
86 :     (* may be a jump *)
87 : leunga 591 let val (_, a) = InsnProps.getAnnotations jmp
88 :     in if #contains MLRiscAnnotations.NO_BRANCH_CHAINING a then
89 :     blockId (* no branch chaining! *)
90 :     else
91 :     (case #out_edges cfg blockId of
92 : leunga 657 [(_,next,CFG.EDGE{k=CFG.JUMP, ...})] =>
93 :     if isAllNop rest then follow next
94 :     else blockId (* terminates here *)
95 :     | [(_,next,CFG.EDGE{k=CFG.FALLSTHRU, ...})] =>
96 :     if isAllNop insns then follow next
97 :     else blockId (* terminates here *)
98 : leunga 591 | _ => blockId (* terminates here *)
99 :     )
100 :     end
101 :     )
102 :     val targetBlockId = follow blockId
103 :     in addBranch(blockId, targetBlockId);
104 : leunga 657 if blockId <> targetBlockId then
105 :     ((* print "BRANCHING CHAINING\n"; *)
106 :     branchChainingCount := !branchChainingCount + 1;
107 :     changed := true)
108 :     else ();
109 : leunga 591 targetBlockId
110 :     end
111 :    
112 :     fun branchChaining(i,CFG.BLOCK{insns=ref [], ...}) = ()
113 :     | branchChaining(i,CFG.BLOCK{insns=ref(jmp::_), ...}) =
114 :     if InsnProps.instrKind jmp = InsnProps.IK_JUMP then
115 :     let fun get(i,j,e as CFG.EDGE{k=CFG.JUMP,...}) = (i,chase j,e)
116 :     | get(i,j,e as CFG.EDGE{k=CFG.BRANCH true,...}) = (i,chase j,e)
117 :     | get(i,j,e as CFG.EDGE{k=CFG.SWITCH _,...}) = (i,chase j,e)
118 :     | get e = e
119 : leunga 657 val out_edges = #out_edges cfg i
120 :     in case out_edges of
121 :     ([_] | [_,_]) =>
122 :     let val edges = map get out_edges
123 :     in #set_out_edges cfg (i,edges);
124 :     Util.updateJumpLabel IR i
125 :     end
126 :     | _ => () (* Can't do branch chaining on multiway jumps yet! *)
127 : leunga 591 end
128 :     else ()
129 :    
130 :     in #forall_nodes cfg branchChaining;
131 :     if !changed then (Util.removeUnreachableCode IR; IR.changed IR) else ();
132 :     IR
133 :     end
134 :    
135 :     end
136 :    

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