Debian Codegraph @

internal/engine/wazevo/backend/compiler.go

raw
1 package backend
2
3 import (
4 "context"
5 "fmt"
6
7 "github.com/tetratelabs/wazero/internal/engine/wazevo/backend/regalloc"
8 "github.com/tetratelabs/wazero/internal/engine/wazevo/ssa"
9 "github.com/tetratelabs/wazero/internal/engine/wazevo/wazevoapi"
10 )
11
12 // NewCompiler returns a new Compiler that can generate a machine code.
13 func NewCompiler(ctx context.Context, mach Machine, builder ssa.Builder) Compiler {
14 return newCompiler(ctx, mach, builder)
15 }
16
17 func newCompiler(_ context.Context, mach Machine, builder ssa.Builder) *compiler {
18 argResultInts, argResultFloats := mach.ArgsResultsRegs()
19 c := &compiler{
20 mach: mach, ssaBuilder: builder,
21 nextVRegID: regalloc.VRegIDNonReservedBegin,
22 argResultInts: argResultInts,
23 argResultFloats: argResultFloats,
24 }
25 mach.SetCompiler(c)
26 return c
27 }
28
29 // Compiler is the backend of wazevo which takes ssa.Builder and Machine,
30 // use the information there to emit the final machine code.
31 type Compiler interface {
32 // SSABuilder returns the ssa.Builder used by this compiler.
33 SSABuilder() ssa.Builder
34
35 // Compile executes the following steps:
36 // 1. Lower()
37 // 2. RegAlloc()
38 // 3. Finalize()
39 // 4. Encode()
40 //
41 // Each step can be called individually for testing purpose, therefore they are exposed in this interface too.
42 //
43 // The returned byte slices are the machine code and the relocation information for the machine code.
44 // The caller is responsible for copying them immediately since the compiler may reuse the buffer.
45 Compile(ctx context.Context) (_ []byte, _ []RelocationInfo, _ error)
46
47 // Lower lowers the given ssa.Instruction to the machine-specific instructions.
48 Lower()
49
50 // RegAlloc performs the register allocation after Lower is called.
51 RegAlloc()
52
53 // Finalize performs the finalization of the compilation, including machine code emission.
54 // This must be called after RegAlloc.
55 Finalize(ctx context.Context) error
56
57 // Buf returns the buffer of the encoded machine code. This is only used for testing purpose.
58 Buf() []byte
59
60 BufPtr() *[]byte
61
62 // Format returns the debug string of the current state of the compiler.
63 Format() string
64
65 // Init initializes the internal state of the compiler for the next compilation.
66 Init()
67
68 // AllocateVReg allocates a new virtual register of the given type.
69 AllocateVReg(typ ssa.Type) regalloc.VReg
70
71 // ValueDefinition returns the definition of the given value.
72 ValueDefinition(ssa.Value) SSAValueDefinition
73
74 // VRegOf returns the virtual register of the given ssa.Value.
75 VRegOf(value ssa.Value) regalloc.VReg
76
77 // TypeOf returns the ssa.Type of the given virtual register.
78 TypeOf(regalloc.VReg) ssa.Type
79
80 // MatchInstr returns true if the given definition is from an instruction with the given opcode, the current group ID,
81 // and a refcount of 1. That means, the instruction can be merged/swapped within the current instruction group.
82 MatchInstr(def SSAValueDefinition, opcode ssa.Opcode) bool
83
84 // MatchInstrOneOf is the same as MatchInstr but for multiple opcodes. If it matches one of ssa.Opcode,
85 // this returns the opcode. Otherwise, this returns ssa.OpcodeInvalid.
86 //
87 // Note: caller should be careful to avoid excessive allocation on opcodes slice.
88 MatchInstrOneOf(def SSAValueDefinition, opcodes []ssa.Opcode) ssa.Opcode
89
90 // AddRelocationInfo appends the relocation information for the function reference at the current buffer offset.
91 AddRelocationInfo(funcRef ssa.FuncRef, isTailCall bool)
92
93 // AddSourceOffsetInfo appends the source offset information for the given offset.
94 AddSourceOffsetInfo(executableOffset int64, sourceOffset ssa.SourceOffset)
95
96 // SourceOffsetInfo returns the source offset information for the current buffer offset.
97 SourceOffsetInfo() []SourceOffsetInfo
98
99 // EmitByte appends a byte to the buffer. Used during the code emission.
100 EmitByte(b byte)
101
102 // Emit4Bytes appends 4 bytes to the buffer. Used during the code emission.
103 Emit4Bytes(b uint32)
104
105 // Emit8Bytes appends 8 bytes to the buffer. Used during the code emission.
106 Emit8Bytes(b uint64)
107
108 // GetFunctionABI returns the ABI information for the given signature.
109 GetFunctionABI(sig *ssa.Signature) *FunctionABI
110 }
111
112 // RelocationInfo represents the relocation information for a call instruction.
113 type RelocationInfo struct {
114 // Offset represents the offset from the beginning of the machine code of either a function or the entire module.
115 Offset int64
116 // Target is the target function of the call instruction.
117 FuncRef ssa.FuncRef
118 // IsTailCall indicates whether the call instruction is a tail call.
119 IsTailCall bool
120 }
121
122 // compiler implements Compiler.
123 type compiler struct {
124 mach Machine
125 currentGID ssa.InstructionGroupID
126 ssaBuilder ssa.Builder
127 // nextVRegID is the next virtual register ID to be allocated.
128 nextVRegID regalloc.VRegID
129 // ssaValueToVRegs maps ssa.ValueID to regalloc.VReg.
130 ssaValueToVRegs [] /* VRegID to */ regalloc.VReg
131 ssaValuesInfo []ssa.ValueInfo
132 // returnVRegs is the list of virtual registers that store the return values.
133 returnVRegs []regalloc.VReg
134 varEdges [][2]regalloc.VReg
135 varEdgeTypes []ssa.Type
136 constEdges []struct {
137 cInst *ssa.Instruction
138 dst regalloc.VReg
139 }
140 vRegSet []bool
141 vRegIDs []regalloc.VRegID
142 tempRegs []regalloc.VReg
143 tmpVals []ssa.Value
144 ssaTypeOfVRegID [] /* VRegID to */ ssa.Type
145 buf []byte
146 relocations []RelocationInfo
147 sourceOffsets []SourceOffsetInfo
148 // abis maps ssa.SignatureID to the ABI implementation.
149 abis []FunctionABI
150 argResultInts, argResultFloats []regalloc.RealReg
151 }
152
153 // SourceOffsetInfo is a data to associate the source offset with the executable offset.
154 type SourceOffsetInfo struct {
155 // SourceOffset is the source offset in the original source code.
156 SourceOffset ssa.SourceOffset
157 // ExecutableOffset is the offset in the compiled executable.
158 ExecutableOffset int64
159 }
160
161 // Compile implements Compiler.Compile.
162 func (c *compiler) Compile(ctx context.Context) ([]byte, []RelocationInfo, error) {
163 c.Lower()
164 if wazevoapi.PrintSSAToBackendIRLowering && wazevoapi.PrintEnabledIndex(ctx) {
165 fmt.Printf("[[[after lowering for %s ]]]%s\n", wazevoapi.GetCurrentFunctionName(ctx), c.Format())
166 }
167 if wazevoapi.DeterministicCompilationVerifierEnabled {
168 wazevoapi.VerifyOrSetDeterministicCompilationContextValue(ctx, "After lowering to ISA specific IR", c.Format())
169 }
170 c.RegAlloc()
171 if wazevoapi.PrintRegisterAllocated && wazevoapi.PrintEnabledIndex(ctx) {
172 fmt.Printf("[[[after regalloc for %s]]]%s\n", wazevoapi.GetCurrentFunctionName(ctx), c.Format())
173 }
174 if wazevoapi.DeterministicCompilationVerifierEnabled {
175 wazevoapi.VerifyOrSetDeterministicCompilationContextValue(ctx, "After Register Allocation", c.Format())
176 }
177 if err := c.Finalize(ctx); err != nil {
178 return nil, nil, err
179 }
180 if wazevoapi.PrintFinalizedMachineCode && wazevoapi.PrintEnabledIndex(ctx) {
181 fmt.Printf("[[[after finalize for %s]]]%s\n", wazevoapi.GetCurrentFunctionName(ctx), c.Format())
182 }
183 if wazevoapi.DeterministicCompilationVerifierEnabled {
184 wazevoapi.VerifyOrSetDeterministicCompilationContextValue(ctx, "After Finalization", c.Format())
185 }
186 return c.buf, c.relocations, nil
187 }
188
189 // RegAlloc implements Compiler.RegAlloc.
190 func (c *compiler) RegAlloc() {
191 c.mach.RegAlloc()
192 }
193
194 // Finalize implements Compiler.Finalize.
195 func (c *compiler) Finalize(ctx context.Context) error {
196 c.mach.PostRegAlloc()
197 return c.mach.Encode(ctx)
198 }
199
200 // setCurrentGroupID sets the current instruction group ID.
201 func (c *compiler) setCurrentGroupID(gid ssa.InstructionGroupID) {
202 c.currentGID = gid
203 }
204
205 // assignVirtualRegisters assigns a virtual register to each ssa.ValueID Valid in the ssa.Builder.
206 func (c *compiler) assignVirtualRegisters() {
207 builder := c.ssaBuilder
208 c.ssaValuesInfo = builder.ValuesInfo()
209
210 if diff := len(c.ssaValuesInfo) - len(c.ssaValueToVRegs); diff > 0 {
211 c.ssaValueToVRegs = append(c.ssaValueToVRegs, make([]regalloc.VReg, diff+1)...)
212 }
213
214 for blk := builder.BlockIteratorReversePostOrderBegin(); blk != nil; blk = builder.BlockIteratorReversePostOrderNext() {
215 // First we assign a virtual register to each parameter.
216 for i := 0; i < blk.Params(); i++ {
217 p := blk.Param(i)
218 pid := p.ID()
219 typ := p.Type()
220 vreg := c.AllocateVReg(typ)
221 c.ssaValueToVRegs[pid] = vreg
222 c.ssaTypeOfVRegID[vreg.ID()] = p.Type()
223 }
224
225 // Assigns each value to a virtual register produced by instructions.
226 for cur := blk.Root(); cur != nil; cur = cur.Next() {
227 r, rs := cur.Returns()
228 if r.Valid() {
229 id := r.ID()
230 ssaTyp := r.Type()
231 typ := r.Type()
232 vReg := c.AllocateVReg(typ)
233 c.ssaValueToVRegs[id] = vReg
234 c.ssaTypeOfVRegID[vReg.ID()] = ssaTyp
235 }
236 for _, r := range rs {
237 id := r.ID()
238 ssaTyp := r.Type()
239 vReg := c.AllocateVReg(ssaTyp)
240 c.ssaValueToVRegs[id] = vReg
241 c.ssaTypeOfVRegID[vReg.ID()] = ssaTyp
242 }
243 }
244 }
245
246 for i, retBlk := 0, builder.ReturnBlock(); i < retBlk.Params(); i++ {
247 typ := retBlk.Param(i).Type()
248 vReg := c.AllocateVReg(typ)
249 c.returnVRegs = append(c.returnVRegs, vReg)
250 c.ssaTypeOfVRegID[vReg.ID()] = typ
251 }
252 }
253
254 // AllocateVReg implements Compiler.AllocateVReg.
255 func (c *compiler) AllocateVReg(typ ssa.Type) regalloc.VReg {
256 regType := regalloc.RegTypeOf(typ)
257 r := regalloc.VReg(c.nextVRegID).SetRegType(regType)
258
259 id := r.ID()
260 if int(id) >= len(c.ssaTypeOfVRegID) {
261 c.ssaTypeOfVRegID = append(c.ssaTypeOfVRegID, make([]ssa.Type, id+1)...)
262 }
263 c.ssaTypeOfVRegID[id] = typ
264 c.nextVRegID++
265 return r
266 }
267
268 // Init implements Compiler.Init.
269 func (c *compiler) Init() {
270 c.currentGID = 0
271 c.nextVRegID = regalloc.VRegIDNonReservedBegin
272 c.returnVRegs = c.returnVRegs[:0]
273 c.mach.Reset()
274 c.varEdges = c.varEdges[:0]
275 c.constEdges = c.constEdges[:0]
276 c.buf = c.buf[:0]
277 c.sourceOffsets = c.sourceOffsets[:0]
278 c.relocations = c.relocations[:0]
279 }
280
281 // ValueDefinition implements Compiler.ValueDefinition.
282 func (c *compiler) ValueDefinition(value ssa.Value) SSAValueDefinition {
283 return SSAValueDefinition{
284 V: value,
285 Instr: c.ssaBuilder.InstructionOfValue(value),
286 RefCount: c.ssaValuesInfo[value.ID()].RefCount,
287 }
288 }
289
290 // VRegOf implements Compiler.VRegOf.
291 func (c *compiler) VRegOf(value ssa.Value) regalloc.VReg {
292 return c.ssaValueToVRegs[value.ID()]
293 }
294
295 // Format implements Compiler.Format.
296 func (c *compiler) Format() string {
297 return c.mach.Format()
298 }
299
300 // TypeOf implements Compiler.Format.
301 func (c *compiler) TypeOf(v regalloc.VReg) ssa.Type {
302 return c.ssaTypeOfVRegID[v.ID()]
303 }
304
305 // MatchInstr implements Compiler.MatchInstr.
306 func (c *compiler) MatchInstr(def SSAValueDefinition, opcode ssa.Opcode) bool {
307 instr := def.Instr
308 return def.IsFromInstr() &&
309 instr.Opcode() == opcode &&
310 instr.GroupID() == c.currentGID &&
311 def.RefCount < 2
312 }
313
314 // MatchInstrOneOf implements Compiler.MatchInstrOneOf.
315 func (c *compiler) MatchInstrOneOf(def SSAValueDefinition, opcodes []ssa.Opcode) ssa.Opcode {
316 instr := def.Instr
317 if !def.IsFromInstr() {
318 return ssa.OpcodeInvalid
319 }
320
321 if instr.GroupID() != c.currentGID {
322 return ssa.OpcodeInvalid
323 }
324
325 if def.RefCount >= 2 {
326 return ssa.OpcodeInvalid
327 }
328
329 opcode := instr.Opcode()
330 for _, op := range opcodes {
331 if opcode == op {
332 return opcode
333 }
334 }
335 return ssa.OpcodeInvalid
336 }
337
338 // SSABuilder implements Compiler .SSABuilder.
339 func (c *compiler) SSABuilder() ssa.Builder {
340 return c.ssaBuilder
341 }
342
343 // AddSourceOffsetInfo implements Compiler.AddSourceOffsetInfo.
344 func (c *compiler) AddSourceOffsetInfo(executableOffset int64, sourceOffset ssa.SourceOffset) {
345 c.sourceOffsets = append(c.sourceOffsets, SourceOffsetInfo{
346 SourceOffset: sourceOffset,
347 ExecutableOffset: executableOffset,
348 })
349 }
350
351 // SourceOffsetInfo implements Compiler.SourceOffsetInfo.
352 func (c *compiler) SourceOffsetInfo() []SourceOffsetInfo {
353 return c.sourceOffsets
354 }
355
356 // AddRelocationInfo implements Compiler.AddRelocationInfo.
357 func (c *compiler) AddRelocationInfo(funcRef ssa.FuncRef, isTailCall bool) {
358 c.relocations = append(c.relocations, RelocationInfo{
359 Offset: int64(len(c.buf)),
360 FuncRef: funcRef,
361 IsTailCall: isTailCall,
362 })
363 }
364
365 // Emit8Bytes implements Compiler.Emit8Bytes.
366 func (c *compiler) Emit8Bytes(b uint64) {
367 c.buf = append(c.buf, byte(b), byte(b>>8), byte(b>>16), byte(b>>24), byte(b>>32), byte(b>>40), byte(b>>48), byte(b>>56))
368 }
369
370 // Emit4Bytes implements Compiler.Emit4Bytes.
371 func (c *compiler) Emit4Bytes(b uint32) {
372 c.buf = append(c.buf, byte(b), byte(b>>8), byte(b>>16), byte(b>>24))
373 }
374
375 // EmitByte implements Compiler.EmitByte.
376 func (c *compiler) EmitByte(b byte) {
377 c.buf = append(c.buf, b)
378 }
379
380 // Buf implements Compiler.Buf.
381 func (c *compiler) Buf() []byte {
382 return c.buf
383 }
384
385 // BufPtr implements Compiler.BufPtr.
386 func (c *compiler) BufPtr() *[]byte {
387 return &c.buf
388 }
389
390 func (c *compiler) GetFunctionABI(sig *ssa.Signature) *FunctionABI {
391 if int(sig.ID) >= len(c.abis) {
392 c.abis = append(c.abis, make([]FunctionABI, int(sig.ID)+1)...)
393 }
394
395 abi := &c.abis[sig.ID]
396 if abi.Initialized {
397 return abi
398 }
399
400 abi.Init(sig, c.argResultInts, c.argResultFloats)
401 return abi
402 }