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

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