1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
(*
* This module performs static branch prediction using heuristics
* similar to Ball and Larus'
*
* -- Allen
*)
functor StaticBranchPrediction
(structure IR : MLRISC_IR
structure InsnProps : INSN_PROPERTIES
structure FreqProps : FREQUENCY_PROPERTIES
sharing IR.I = FreqProps.I = InsnProps.I
val loopMultiplier : int
) : MLRISC_IR_OPTIMIZATION =
struct
structure IR = IR
structure CFG = IR.CFG
structure CompFreq = ComputeFrequencies(structure Loop = IR.Loop
structure Freq = CFG.W)
type flowgraph = IR.IR
val name = "StaticBranchPrediction"
fun run IR =
let fun branchProb(CFG.BLOCK{insns,...}) =
case !insns of
[] => 100 (* the fallsthru edge is always taken *)
| jmp::_ =>
(case InsnProps.instrKind jmp of
InsnProps.IK_JUMP => FreqProps.branchProb jmp
| _ => 100 (* the fallsthru edge is always taken *)
)
fun nodeFreq(CFG.BLOCK{freq,...}) = freq
fun edgeFreq(CFG.EDGE{w,...}) = w
(* is this a conditional branch and is it in the taken direction? *)
fun isTakenBranch(_,_,CFG.EDGE{k=CFG.BRANCH b,...}) = b
| isTakenBranch _ = false
in CompFreq.compute_frequencies
{ cfg = IR,
loop = IR.loop IR,
loopMultiplier = loopMultiplier,
nodeFreq = nodeFreq,
edgeFreq = edgeFreq,
branchProb = branchProb,
isTakenBranch = isTakenBranch
};
IR
end
end
|
