Mercurial > hg > Members > tobaru > cbc > CbC_llvm

annotate docs/HistoricalNotes/2003-06-25-Reoptimizer1.txt @ 16:d405342cecb1

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
can eliminate tail call regardless of optimize level
author Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
date Tue, 24 Sep 2013 19:04:26 +0900
parents 9ad51c7bc036
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
3
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
1 Wed Jun 25 15:13:51 CDT 2003
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
2
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
3 First-level instrumentation
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
4 ---------------------------
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
5
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
6 We use opt to do Bytecode-to-bytecode instrumentation. Look at
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
7 back-edges and insert llvm_first_trigger() function call which takes
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
8 no arguments and no return value. This instrumentation is designed to
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
9 be easy to remove, for instance by writing a NOP over the function
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
10 call instruction.
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
11
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
12 Keep count of every call to llvm_first_trigger(), and maintain
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
13 counters in a map indexed by return address. If the trigger count
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
14 exceeds a threshold, we identify a hot loop and perform second-level
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
15 instrumentation on the hot loop region (the instructions between the
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
16 target of the back-edge and the branch that causes the back-edge). We
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
17 do not move code across basic-block boundaries.
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
18
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
19
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
20 Second-level instrumentation
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
21 ---------------------------
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
22
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
23 We remove the first-level instrumentation by overwriting the CALL to
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
24 llvm_first_trigger() with a NOP.
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
25
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
26 The reoptimizer maintains a map between machine-code basic blocks and
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
27 LLVM BasicBlock*s. We only keep track of paths that start at the
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
28 first machine-code basic block of the hot loop region.
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
29
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
30 How do we keep track of which edges to instrument, and which edges are
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
31 exits from the hot region? 3 step process.
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
32
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
33 1) Do a DFS from the first machine-code basic block of the hot loop
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
34 region and mark reachable edges.
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
35
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
36 2) Do a DFS from the last machine-code basic block of the hot loop
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
37 region IGNORING back edges, and mark the edges which are reachable in
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
38 1) and also in 2) (i.e., must be reachable from both the start BB and
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
39 the end BB of the hot region).
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
40
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
41 3) Mark BBs which end in edges that exit the hot region; we need to
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
42 instrument these differently.
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
43
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
44 Assume that there is 1 free register. On SPARC we use %g1, which LLC
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
45 has agreed not to use. Shift a 1 into it at the beginning. At every
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
46 edge which corresponds to a conditional branch, we shift 0 for not
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
47 taken and 1 for taken into a register. This uniquely numbers the paths
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
48 through the hot region. Silently fail if we need more than 64 bits.
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
49
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
50 At the end BB we call countPath and increment the counter based on %g1
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
51 and the return address of the countPath call. We keep track of the
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
52 number of iterations and the number of paths. We only run this
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
53 version 30 or 40 times.
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
54
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
55 Find the BBs that total 90% or more of execution, and aggregate them
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
56 together to form our trace. But we do not allow more than 5 paths; if
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
57 we have more than 5 we take the ones that are executed the most. We
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
58 verify our assumption that we picked a hot back-edge in first-level
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
59 instrumentation, by making sure that the number of times we took an
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
60 exit edge from the hot trace is less than 10% of the number of
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
61 iterations.
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
62
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
63 LLC has been taught to recognize llvm_first_trigger() calls and NOT
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
64 generate saves and restores of caller-saved registers around these
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
65 calls.
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
66
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
67
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
68 Phase behavior
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
69 --------------
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
70
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
71 We turn off llvm_first_trigger() calls with NOPs, but this would hide
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
72 phase behavior from us (when some funcs/traces stop being hot and
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
73 others become hot.)
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
74
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
75 We have a SIGALRM timer that counts time for us. Every time we get a
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
76 SIGALRM we look at our priority queue of locations where we have
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
77 removed llvm_first_trigger() calls. Each location is inserted along
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
78 with a time when we will next turn instrumentation back on for that
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
79 call site. If the time has arrived for a particular call site, we pop
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
80 that off the prio. queue and turn instrumentation back on for that
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
81 call site.
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
82
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
83
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
84 Generating traces
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
85 -----------------
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
86
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
87 When we finally generate an optimized trace we first copy the code
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
88 into the trace cache. This leaves us with 3 copies of the code: the
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
89 original code, the instrumented code, and the optimized trace. The
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
90 optimized trace does not have instrumentation. The original code and
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
91 the instrumented code are modified to have a branch to the trace
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
92 cache, where the optimized traces are kept.
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
93
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
94 We copy the code from the original to the instrumentation version
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
95 by tracing the LLVM-to-Machine code basic block map and then copying
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
96 each machine code basic block we think is in the hot region into the
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
97 trace cache. Then we instrument that code. The process is similar for
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
98 generating the final optimized trace; we copy the same basic blocks
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
99 because we might need to put in fixup code for exit BBs.
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
100
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
101 LLVM basic blocks are not typically used in the Reoptimizer except
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
102 for the mapping information.
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
103
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
104 We are restricted to using single instructions to branch between the
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
105 original code, trace, and instrumented code. So we have to keep the
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
106 code copies in memory near the original code (they can't be far enough
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
107 away that a single pc-relative branch would not work.) Malloc() or
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
108 data region space is too far away. this impacts the design of the
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
109 trace cache.
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
110
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
111 We use a dummy function that is full of a bunch of for loops which we
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
112 overwrite with trace-cache code. The trace manager keeps track of
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
113 whether or not we have enough space in the trace cache, etc.
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
114
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
115 The trace insertion routine takes an original start address, a vector
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
116 of machine instructions representing the trace, index of branches and
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
117 their corresponding absolute targets, and index of calls and their
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
118 corresponding absolute targets.
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
119
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
120 The trace insertion routine is responsible for inserting branches from
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
121 the beginning of the original code to the beginning of the optimized
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
122 trace. This is because at some point the trace cache may run out of
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
123 space and it may have to evict a trace, at which point the branch to
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
124 the trace would also have to be removed. It uses a round-robin
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
125 replacement policy; we have found that this is almost as good as LRU
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
126 and better than random (especially because of problems fitting the new
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
127 trace in.)
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
128
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
129 We cannot deal with discontiguous trace cache areas. The trace cache
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
130 is supposed to be cache-line-aligned, but it is not page-aligned.
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
131
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
132 We generate instrumentation traces and optimized traces into separate
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
133 trace caches. We keep the instrumented code around because you don't
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
134 want to delete a trace when you still might have to return to it
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
135 (i.e., return from a llvm_first_trigger() or countPath() call.)
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
136
9ad51c7bc036 1st commit. remove git dir and add all files.
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
137