predecode.gno
5.90 Kb · 267 lines
1package riscv
2
3// Predecode: the image is turned into fields once, at load, and the dispatch
4// loop only indexes arrays.
5//
6// Two measurements forced this shape, both in switchcost_test.gno:
7//
8// - The GnoVM scans switch cases in source order. Reaching case 47 of a
9// 48-case switch costs 13,358 gas against 292 for case 0, a measured 278
10// gas per case skipped. So the internal opcodes below are ordered by how
11// often compiled code actually executes them, and that ordering is a
12// performance decision, not a stylistic one. Do not sort this list.
13// - An elementary operation costs on the order of 280 gas. Fetching four
14// bytes and reassembling them is fourteen of those, on every instruction,
15// forever. Doing it once per word instead is the single largest saving
16// available to an interpreter here.
17//
18// The decoders in decode.gno are used verbatim below rather than inlined,
19// because predecode runs once per word in the image and not once per executed
20// instruction. That is the point: the expensive, readable code moved off the
21// hot path instead of being duplicated onto it.
22
23// Internal opcodes, ordered by expected dynamic frequency in compiled code.
24// The first dozen are what a loop nest and a function prologue are made of.
25const (
26 iADDI uint8 = iota
27 iLW
28 iSW
29 iADD
30 iBNE
31 iBEQ
32 iJAL
33 iJALR
34 iLUI
35 iSLLI
36 iSRLI
37 iANDI
38 iSUB
39 iORI
40 iXORI
41 iBLT
42 iBGE
43 iBLTU
44 iBGEU
45 iSRAI
46 iSLL
47 iSRL
48 iSRA
49 iAND
50 iOR
51 iXOR
52 iLBU
53 iLB
54 iLH
55 iLHU
56 iSB
57 iSH
58 iAUIPC
59 iSLT
60 iSLTU
61 iSLTI
62 iSLTIU
63 iMUL
64 iMULH
65 iMULHSU
66 iMULHU
67 iDIV
68 iDIVU
69 iREM
70 iREMU
71 iECALL
72 iEBREAK
73 iFENCE
74 iILLEGAL
75)
76
77// code is an image with its fields already pulled apart. Parallel arrays, not
78// a slice of structs: an arm reads three or four fields, and paying for the
79// ones it does not read is the cost this whole file exists to avoid.
80type code struct {
81 base uint32 // the address word 0 sits at
82 words uint32 // how many instructions the text segment holds
83 end uint32 // base + 4*words, the first address past the text
84 op []uint8
85 rd []uint8
86 rs1 []uint8
87 rs2 []uint8
88 imm []uint32
89}
90
91// predecode walks an image and records, for every word, what it is and what
92// its operands are. A word that is not an instruction becomes iILLEGAL and
93// traps only if it is ever executed, which is what keeps a constant pool in
94// the middle of a text segment legal.
95func predecode(base uint32, img []byte) *code {
96 n := uint32(len(img) / 4)
97 c := &code{
98 base: base,
99 words: n,
100 end: base + n*4,
101 op: make([]uint8, n),
102 rd: make([]uint8, n),
103 rs1: make([]uint8, n),
104 rs2: make([]uint8, n),
105 imm: make([]uint32, n),
106 }
107 for i := uint32(0); i < n; i++ {
108 j := i * 4
109 inst := uint32(img[j]) | uint32(img[j+1])<<8 |
110 uint32(img[j+2])<<16 | uint32(img[j+3])<<24
111 op, imm := decodeWord(inst)
112 c.op[i] = op
113 c.imm[i] = imm
114 // The three register selectors are in the same place in every format
115 // that has them, and are harmless in the formats that do not, so they
116 // are taken unconditionally and spelled out: this loop already costs
117 // more than executing the instruction does.
118 c.rd[i] = uint8((inst >> 7) & 0x1F)
119 c.rs1[i] = uint8((inst >> 15) & 0x1F)
120 c.rs2[i] = uint8((inst >> 20) & 0x1F)
121 }
122 return c
123}
124
125// decodeWord returns both the internal opcode and the immediate, in one pass.
126//
127// They were two functions once, and splitting them cost 22 case labels: the
128// second switch had to ask all over again which format the instruction was, and
129// the GnoVM scans case labels one at a time. Deciding both in the arm that
130// already knows the answer took predecode from 31.4k gas per word to 19.6k.
131//
132// The immediate decoders are still called rather than inlined. This runs once
133// per word in the image, not once per executed instruction, and sign extension
134// is the subtle part of RV32 decoding: it belongs in one place, spelled out,
135// with decode_test.gno round-tripping it against the assembler.
136func decodeWord(inst uint32) (uint8, uint32) {
137 f3 := funct3(inst)
138 switch opcode(inst) {
139 case opImm:
140 imm := immI(inst)
141 switch f3 {
142 case 0x0:
143 return iADDI, imm
144 case 0x1:
145 return iSLLI, imm
146 case 0x2:
147 return iSLTI, imm
148 case 0x3:
149 return iSLTIU, imm
150 case 0x4:
151 return iXORI, imm
152 case 0x5:
153 if funct7(inst) == 0x20 {
154 return iSRAI, imm
155 }
156 return iSRLI, imm
157 case 0x6:
158 return iORI, imm
159 case 0x7:
160 return iANDI, imm
161 }
162 case opLoad:
163 imm := immI(inst)
164 switch f3 {
165 case 0x0:
166 return iLB, imm
167 case 0x1:
168 return iLH, imm
169 case 0x2:
170 return iLW, imm
171 case 0x4:
172 return iLBU, imm
173 case 0x5:
174 return iLHU, imm
175 }
176 case opStore:
177 imm := immS(inst)
178 switch f3 {
179 case 0x0:
180 return iSB, imm
181 case 0x1:
182 return iSH, imm
183 case 0x2:
184 return iSW, imm
185 }
186 case opReg:
187 f7 := funct7(inst)
188 if f7 == 0x01 {
189 switch f3 {
190 case 0x0:
191 return iMUL, 0
192 case 0x1:
193 return iMULH, 0
194 case 0x2:
195 return iMULHSU, 0
196 case 0x3:
197 return iMULHU, 0
198 case 0x4:
199 return iDIV, 0
200 case 0x5:
201 return iDIVU, 0
202 case 0x6:
203 return iREM, 0
204 case 0x7:
205 return iREMU, 0
206 }
207 }
208 switch f3 {
209 case 0x0:
210 if f7 == 0x20 {
211 return iSUB, 0
212 }
213 return iADD, 0
214 case 0x1:
215 return iSLL, 0
216 case 0x2:
217 return iSLT, 0
218 case 0x3:
219 return iSLTU, 0
220 case 0x4:
221 return iXOR, 0
222 case 0x5:
223 if f7 == 0x20 {
224 return iSRA, 0
225 }
226 return iSRL, 0
227 case 0x6:
228 return iOR, 0
229 case 0x7:
230 return iAND, 0
231 }
232 case opBranch:
233 imm := immB(inst)
234 switch f3 {
235 case 0x0:
236 return iBEQ, imm
237 case 0x1:
238 return iBNE, imm
239 case 0x4:
240 return iBLT, imm
241 case 0x5:
242 return iBGE, imm
243 case 0x6:
244 return iBLTU, imm
245 case 0x7:
246 return iBGEU, imm
247 }
248 case opLUI:
249 return iLUI, immU(inst)
250 case opAUIPC:
251 return iAUIPC, immU(inst)
252 case opJAL:
253 return iJAL, immJ(inst)
254 case opJALR:
255 if f3 == 0x0 {
256 return iJALR, immI(inst)
257 }
258 case opFence:
259 return iFENCE, 0
260 case opSystem:
261 if immI(inst) == 0 {
262 return iECALL, 0
263 }
264 return iEBREAK, 0
265 }
266 return iILLEGAL, 0
267}
