/home/travis/build/MoarVM/MoarVM/src/spesh/graph.h
Line | Count | Source |
1 | 21.8k | #define MVMPhiNodeCacheSize 48 |
2 | 669k | #define MVMPhiNodeCacheSparseBegin 32 |
3 | | |
4 | | /* Top level of a spesh graph, representing a particular static frame (and |
5 | | * potentially having others inlined into it). */ |
6 | | struct MVMSpeshGraph { |
7 | | /* The static frame this is the spesh graph for. */ |
8 | | MVMStaticFrame *sf; |
9 | | |
10 | | /* The callsite this spesh graph has been tailored to. */ |
11 | | MVMCallsite *cs; |
12 | | |
13 | | /* The bytecode we're building the graph out of. */ |
14 | | MVMuint8 *bytecode; |
15 | | |
16 | | /* Exception handler map for that bytecode. */ |
17 | | MVMFrameHandler *handlers; |
18 | | |
19 | | /* The size of the bytecode we're building the graph out of. */ |
20 | | MVMuint32 bytecode_size; |
21 | | |
22 | | /* Number of exception handlers. */ |
23 | | MVMuint32 num_handlers; |
24 | | |
25 | | /* The entry basic block. */ |
26 | | MVMSpeshBB *entry; |
27 | | |
28 | | /* Gathered facts about each version of a local (top-level array is per |
29 | | * local, then array hanging off it is per version). */ |
30 | | MVMSpeshFacts **facts; |
31 | | |
32 | | /* Number of fact entries per local. */ |
33 | | MVMuint16 *fact_counts; |
34 | | |
35 | | /* Argument guards added. */ |
36 | | MVMSpeshGuard *arg_guards; |
37 | | |
38 | | /* Number of argument guards we have. */ |
39 | | MVMint32 num_arg_guards; |
40 | | |
41 | | /* Log-based guards added. */ |
42 | | MVMSpeshLogGuard *log_guards; |
43 | | |
44 | | /* Number of log-based guards we have. */ |
45 | | MVMint32 num_log_guards; |
46 | | |
47 | | /* Region allocator for spesh nodes */ |
48 | | MVMRegionAlloc region_alloc; |
49 | | |
50 | | /* Values placed in spesh slots. */ |
51 | | MVMCollectable **spesh_slots; |
52 | | |
53 | | /* Number of spesh slots we have used and allocated. */ |
54 | | MVMint32 num_spesh_slots; |
55 | | MVMint32 alloc_spesh_slots; |
56 | | |
57 | | /* De-opt indexes, as pairs of integers. The first integer, set when we |
58 | | * build the graph, is the return address in the original bytecode. The |
59 | | * code-gen phase for the specialized bytecode will fill in the second |
60 | | * integers afterwards, which are the return address in the specialized |
61 | | * bytecode. */ |
62 | | MVMint32 *deopt_addrs; |
63 | | MVMint32 num_deopt_addrs; |
64 | | MVMint32 alloc_deopt_addrs; |
65 | | |
66 | | /* Table of information about inlines, laid out in order of nesting |
67 | | * depth. Thus, going through the table in order and finding when we |
68 | | * are within the bounds will show up each call frame that needs to |
69 | | * be created in deopt. */ |
70 | | MVMSpeshInline *inlines; |
71 | | MVMint32 num_inlines; |
72 | | |
73 | | /* Logging slots, along with the number of them. */ |
74 | | MVMint32 num_log_slots; |
75 | | MVMCollectable **log_slots; |
76 | | |
77 | | /* Number of basic blocks we have. */ |
78 | | MVMint32 num_bbs; |
79 | | |
80 | | /* The list of local types (only set up if we do inlines). */ |
81 | | MVMuint16 *local_types; |
82 | | |
83 | | /* The list of lexical types (only set up if we do inlines). */ |
84 | | MVMuint16 *lexical_types; |
85 | | |
86 | | /* The total number of locals, accounting for any inlining done and |
87 | | * added temporaries. */ |
88 | | MVMuint16 num_locals; |
89 | | |
90 | | /* The total number of lexicals, accounting for any inlining done. */ |
91 | | MVMuint16 num_lexicals; |
92 | | |
93 | | /* Temporary local registers added to aid transformations, along with a |
94 | | * count of the number we have and have allocated space for so far. */ |
95 | | MVMuint16 num_temps; |
96 | | MVMuint16 alloc_temps; |
97 | | MVMSpeshTemporary *temps; |
98 | | |
99 | | /* We need to create new MVMOpInfo structs for each number of |
100 | | * arguments a PHI node can take. We cache them here, so that we |
101 | | * allocate fewer of them across our spesh alloc blocks. |
102 | | */ |
103 | | MVMOpInfo *phi_infos; |
104 | | |
105 | | /* If this graph was formed from a spesh candidate rather than an |
106 | | * original static frame, the candidate will be stored here. */ |
107 | | MVMSpeshCandidate *cand; |
108 | | }; |
109 | | |
110 | | /* A temporary register, added to support transformations. */ |
111 | | struct MVMSpeshTemporary { |
112 | | /* The number of the local along with the current SSA index. */ |
113 | | MVMuint16 orig; |
114 | | MVMuint16 i; |
115 | | |
116 | | /* What kind of register is it? */ |
117 | | MVMuint16 kind; |
118 | | |
119 | | /* Is it currently in use? */ |
120 | | MVMuint16 in_use; |
121 | | }; |
122 | | |
123 | | /* A basic block in the graph (sequences of instructions where control will |
124 | | * always enter at the start and leave at the end). */ |
125 | | struct MVMSpeshBB { |
126 | | /* Head/tail of doubly linked list of instructions. */ |
127 | | MVMSpeshIns *first_ins; |
128 | | MVMSpeshIns *last_ins; |
129 | | |
130 | | /* Basic blocks we may go to after this one. */ |
131 | | MVMSpeshBB **succ; |
132 | | |
133 | | /* Basic blocks that we may arrive into this one from. */ |
134 | | MVMSpeshBB **pred; |
135 | | |
136 | | /* Children in the dominator tree. */ |
137 | | MVMSpeshBB **children; |
138 | | |
139 | | /* Dominance frontier set. */ |
140 | | MVMSpeshBB **df; |
141 | | |
142 | | /* Counts for the above, grouped together to avoid alignment holes. */ |
143 | | MVMuint16 num_succ; |
144 | | MVMuint16 num_pred; |
145 | | MVMuint16 num_children; |
146 | | MVMuint16 num_df; |
147 | | |
148 | | /* The next basic block in original linear code order. */ |
149 | | MVMSpeshBB *linear_next; |
150 | | |
151 | | /* Index (just an ascending integer along the linear_next chain), used as |
152 | | * the block identifier in dominance computation and for debug output. */ |
153 | | MVMint32 idx; |
154 | | |
155 | | /* The block's reverse post-order index, assinged when computing |
156 | | * dominance. */ |
157 | | MVMint32 rpo_idx; |
158 | | |
159 | | /* We cache the instruction pointer of the very first instruction so that |
160 | | * we can output a line number for every BB */ |
161 | | MVMuint32 initial_pc; |
162 | | |
163 | | /* Is this block an inlining of another one? */ |
164 | | MVMint32 inlined; |
165 | | }; |
166 | | |
167 | | /* The SSA phi instruction. */ |
168 | 20.1M | #define MVM_SSA_PHI 32767 |
169 | | |
170 | | /* An instruction in the spesh graph. */ |
171 | | struct MVMSpeshIns { |
172 | | /* Instruction information. */ |
173 | | const MVMOpInfo *info; |
174 | | |
175 | | /* Operand information. */ |
176 | | MVMSpeshOperand *operands; |
177 | | |
178 | | /* Previous and next instructions, within a basic block boundary. */ |
179 | | MVMSpeshIns *prev; |
180 | | MVMSpeshIns *next; |
181 | | |
182 | | /* Any annotations on the instruction. */ |
183 | | MVMSpeshAnn *annotations; |
184 | | }; |
185 | | |
186 | | /* Union type of operands in a spesh instruction; the op info and phase of the |
187 | | * optimizer we're in determines which of these we look at. */ |
188 | | union MVMSpeshOperand { |
189 | | MVMint64 lit_i64; |
190 | | MVMint32 lit_i32; |
191 | | MVMint16 lit_i16; |
192 | | MVMint8 lit_i8; |
193 | | MVMnum64 lit_n64; |
194 | | MVMnum32 lit_n32; |
195 | | MVMuint32 lit_str_idx; |
196 | | MVMuint16 callsite_idx; |
197 | | MVMuint16 coderef_idx; |
198 | | MVMuint32 ins_offset; |
199 | | MVMSpeshBB *ins_bb; |
200 | | struct { |
201 | | MVMuint16 idx; |
202 | | MVMuint16 outers; |
203 | | } lex; |
204 | | struct { |
205 | | MVMint32 i; /* SSA-computed version. */ |
206 | | MVMuint16 orig; /* Original register number. */ |
207 | | } reg; |
208 | | }; |
209 | | |
210 | | /* Annotations base. */ |
211 | | struct MVMSpeshAnn { |
212 | | /* The next annotation in the chain, if any. */ |
213 | | MVMSpeshAnn *next; |
214 | | |
215 | | /* The type of annotation we have. */ |
216 | | MVMint32 type; |
217 | | |
218 | | /* Data (meaning depends on type). */ |
219 | | union { |
220 | | MVMint32 frame_handler_index; |
221 | | MVMint32 deopt_idx; |
222 | | MVMint32 inline_idx; |
223 | | } data; |
224 | | }; |
225 | | |
226 | | /* Annotation types. */ |
227 | 90.9k | #define MVM_SPESH_ANN_FH_START 1 |
228 | 122k | #define MVM_SPESH_ANN_FH_END 2 |
229 | 200k | #define MVM_SPESH_ANN_FH_GOTO 3 |
230 | 534k | #define MVM_SPESH_ANN_DEOPT_ONE_INS 4 |
231 | 248k | #define MVM_SPESH_ANN_DEOPT_ALL_INS 5 |
232 | 19.3k | #define MVM_SPESH_ANN_INLINE_START 6 |
233 | 100k | #define MVM_SPESH_ANN_INLINE_END 7 |
234 | 18.4k | #define MVM_SPESH_ANN_DEOPT_INLINE 8 |
235 | 21.4k | #define MVM_SPESH_ANN_DEOPT_OSR 9 |
236 | | |
237 | | /* Functions to create/destroy the spesh graph. */ |
238 | | MVMSpeshGraph * MVM_spesh_graph_create(MVMThreadContext *tc, MVMStaticFrame *sf, |
239 | | MVMuint32 cfg_only, MVMuint32 insert_object_nulls); |
240 | | MVMSpeshGraph * MVM_spesh_graph_create_from_cand(MVMThreadContext *tc, MVMStaticFrame *sf, |
241 | | MVMSpeshCandidate *cand, MVMuint32 cfg_only); |
242 | | MVMSpeshBB * MVM_spesh_graph_linear_prev(MVMThreadContext *tc, MVMSpeshGraph *g, MVMSpeshBB *search); |
243 | | void MVM_spesh_graph_mark(MVMThreadContext *tc, MVMSpeshGraph *g, MVMGCWorklist *worklist); |
244 | | void MVM_spesh_graph_destroy(MVMThreadContext *tc, MVMSpeshGraph *g); |
245 | | MVM_PUBLIC void * MVM_spesh_alloc(MVMThreadContext *tc, MVMSpeshGraph *g, size_t bytes); |
246 | | MVMOpInfo *get_phi(MVMThreadContext *tc, MVMSpeshGraph *g, MVMuint32 nrargs); |