qbe_backend.go
Go
1package codegen
2
3import (
4 "bytes"
5 "fmt"
6 "strings"
7
8 "github.com/xplshn/gbc/pkg/ast"
9 "github.com/xplshn/gbc/pkg/config"
10 "github.com/xplshn/gbc/pkg/ir"
11 "modernc.org/libqbe"
12)
13
14type qbeBackend struct{
15 out *strings.Builder
16 prog *ir.Program
17 currentFn *ir.Func
18 structTypes map[string]bool
19 extCounter int
20}
21
22func NewQBEBackend() Backend { return &qbeBackend{structTypes: make(map[string]bool)} }
23
24func (b *qbeBackend) Generate(prog *ir.Program, cfg *config.Config) (*bytes.Buffer, error) {
25 qbeIR, err := b.GenerateIR(prog, cfg)
26 if err != nil { return nil, err }
27
28 var asmBuf bytes.Buffer
29 err = libqbe.Main(cfg.BackendTarget, "input.ssa", strings.NewReader(qbeIR), &asmBuf, nil)
30 if err != nil { return nil, fmt.Errorf("\n--- QBE Compilation Failed ---\nGenerated IR:\n%s\n\nlibqbe error: %w", qbeIR, err) }
31 return &asmBuf, nil
32}
33
34func (b *qbeBackend) GenerateIR(prog *ir.Program, cfg *config.Config) (string, error) {
35 var qbeIRBuilder strings.Builder
36 b.out = &qbeIRBuilder
37 b.prog = prog
38
39 b.gen()
40
41 return qbeIRBuilder.String(), nil
42}
43
44func (b *qbeBackend) gen() {
45 b.genStructTypes()
46
47 for _, g := range b.prog.Globals {
48 b.genGlobal(g)
49 }
50
51 if len(b.prog.Strings) > 0 {
52 b.out.WriteString("\n")
53 for s, label := range b.prog.Strings {
54 b.out.WriteString(fmt.Sprintf("data $%s = { ", label))
55
56 if len(s) == 0 {
57 b.out.WriteString("b 0 }\n")
58 continue
59 }
60
61 for i := 0; i < len(s); i++ {
62 if i > 0 { b.out.WriteString(", ") }
63 b.out.WriteString(fmt.Sprintf("b %d", s[i]))
64 }
65 b.out.WriteString(", b 0 }\n")
66 }
67 }
68
69 for _, fn := range b.prog.Funcs {
70 b.genFunc(fn)
71 }
72}
73
74func (b *qbeBackend) formatFieldType(t *ast.BxType) (string, bool) {
75 if t == nil { return b.formatType(ir.GetType(nil, b.prog.WordSize)), true }
76 switch t.Kind {
77 case ast.TYPE_STRUCT:
78 if t.Name != "" {
79 if _, defined := b.structTypes[t.Name]; defined { return ":" + t.Name, true }
80 }
81 return "", false
82 case ast.TYPE_POINTER, ast.TYPE_ARRAY: return b.formatType(ir.GetType(nil, b.prog.WordSize)), true
83 default: return b.formatType(ir.GetType(t, b.prog.WordSize)), true
84 }
85}
86
87func (b *qbeBackend) genStructTypes() {
88 allStructs := make(map[string]*ast.BxType)
89
90 var collect func(t *ast.BxType)
91 collect = func(t *ast.BxType) {
92 if t == nil {
93 return
94 }
95 if t.Kind == ast.TYPE_STRUCT {
96 if _, exists := allStructs[t.Name]; !exists && t.Name != "" {
97 allStructs[t.Name] = t
98 for _, f := range t.Fields {
99 collect(f.Data.(ast.VarDeclNode).Type)
100 }
101 }
102 } else if t.Kind == ast.TYPE_POINTER || t.Kind == ast.TYPE_ARRAY {
103 collect(t.Base)
104 }
105 }
106
107 for _, g := range b.prog.Globals {
108 collect(g.AstType)
109 }
110 for _, f := range b.prog.Funcs {
111 collect(f.AstReturnType)
112 if f.AstParams != nil {
113 for _, pNode := range f.AstParams {
114 if pNode.Type == ast.VarDecl {
115 collect(pNode.Data.(ast.VarDeclNode).Type)
116 }
117 }
118 } else if len(f.Params) > 0 && f.Name != "" {
119 if symNode := b.prog.FindFuncSymbol(f.Name); symNode != nil {
120 if decl, ok := symNode.Data.(ast.FuncDeclNode); ok {
121 for _, p := range decl.Params {
122 if p.Type == ast.VarDecl {
123 collect(p.Data.(ast.VarDeclNode).Type)
124 }
125 }
126 }
127 }
128 }
129 }
130
131 if len(allStructs) == 0 {
132 return
133 }
134
135 b.out.WriteString("\n")
136 definedCount := -1
137 for len(b.structTypes) < len(allStructs) && len(b.structTypes) != definedCount {
138 definedCount = len(b.structTypes)
139 for name, typ := range allStructs {
140 if b.structTypes[name] {
141 continue
142 }
143
144 var fieldTypes []string
145 canDefine := true
146 for _, field := range typ.Fields {
147 fType := field.Data.(ast.VarDeclNode).Type
148 typeStr, ok := b.formatFieldType(fType)
149 if !ok {
150 canDefine = false
151 break
152 }
153 fieldTypes = append(fieldTypes, typeStr)
154 }
155
156 if canDefine {
157 fmt.Fprintf(b.out, "type :%s = { %s }\n", name, strings.Join(fieldTypes, ", "))
158 b.structTypes[name] = true
159 }
160 }
161 }
162}
163
164func (b *qbeBackend) genGlobal(g *ir.Data) {
165 alignStr := ""
166 if g.Align > 0 {
167 alignStr = fmt.Sprintf("align %d ", g.Align)
168 }
169
170 fmt.Fprintf(b.out, "data $%s = %s{ ", g.Name, alignStr)
171 for i, item := range g.Items {
172 if item.Count > 0 {
173 size := int64(item.Count)
174 if item.Typ != ir.TypeB {
175 size *= ir.SizeOfType(item.Typ, b.prog.WordSize)
176 }
177 fmt.Fprintf(b.out, "z %d", size)
178 } else {
179 fmt.Fprintf(b.out, "%s %s", b.formatType(item.Typ), b.formatValue(item.Value))
180 }
181 if i < len(g.Items)-1 {
182 b.out.WriteString(", ")
183 }
184 }
185 b.out.WriteString(" }\n")
186}
187
188func (b *qbeBackend) genFunc(fn *ir.Func) {
189 b.currentFn = fn
190 var retTypeStr string
191 if fn.AstReturnType != nil && fn.AstReturnType.Kind == ast.TYPE_STRUCT {
192 retTypeStr = " :" + fn.AstReturnType.Name
193 } else {
194 retTypeStr = b.formatType(fn.ReturnType)
195 if retTypeStr != "" {
196 retTypeStr = " " + retTypeStr
197 }
198 }
199
200 fmt.Fprintf(b.out, "\nexport function%s $%s(", retTypeStr, fn.Name)
201
202 for i, p := range fn.Params {
203 paramType := p.Typ
204 if paramType == ir.TypeB || paramType == ir.TypeH {
205 paramType = ir.GetType(nil, b.prog.WordSize)
206 }
207 fmt.Fprintf(b.out, "%s %s", b.formatType(paramType), b.formatValue(p.Val))
208 if i < len(fn.Params)-1 {
209 b.out.WriteString(", ")
210 }
211 }
212
213 if fn.HasVarargs {
214 if len(fn.Params) > 0 {
215 b.out.WriteString(", ")
216 }
217 b.out.WriteString("...")
218 }
219 b.out.WriteString(") {\n")
220
221 for _, block := range fn.Blocks {
222 b.genBlock(block)
223 }
224
225 b.out.WriteString("}\n")
226}
227
228func (b *qbeBackend) genBlock(block *ir.BasicBlock) {
229 fmt.Fprintf(b.out, "@%s\n", block.Label.Name)
230 for _, instr := range block.Instructions {
231 b.genInstr(instr)
232 }
233}
234
235func (b *qbeBackend) genInstr(instr *ir.Instruction) {
236 if instr.Op == ir.OpCall {
237 b.out.WriteString("\t")
238 b.genCall(instr)
239 return
240 }
241
242 // Handle special case for byte arithmetic operations
243 isArithmetic := (instr.Op >= ir.OpAdd && instr.Op <= ir.OpShr) || (instr.Op >= ir.OpAddF && instr.Op <= ir.OpNegF)
244 if isArithmetic && (instr.Typ == ir.TypeB || instr.Typ == ir.TypeSB || instr.Typ == ir.TypeUB) {
245 // For byte arithmetic, generate as word arithmetic with appropriate conversions
246 b.genByteArithmetic(instr)
247 return
248 }
249
250 // Handle special case for float arithmetic operations requiring type conversion
251 isFloatArithmetic := instr.Op >= ir.OpAddF && instr.Op <= ir.OpRemF
252 if isFloatArithmetic && instr.Typ == ir.TypeD {
253 // For double precision float arithmetic, generate with appropriate conversions
254 b.genFloatArithmetic(instr)
255 return
256 }
257
258 b.out.WriteString("\t")
259 if instr.Result != nil {
260 resultType := instr.Typ
261 isComparison := instr.Op >= ir.OpCEq && instr.Op <= ir.OpCGe
262
263 if isComparison {
264 resultType = ir.GetType(nil, b.prog.WordSize)
265 }
266
267 // In QBE, temporaries can only have base types. On 64-bit systems, promote sub-word types to long (l)
268 if instr.Op == ir.OpLoad && b.isSubWordType(instr.Typ) {
269 resultType = ir.GetType(nil, b.prog.WordSize)
270 }
271
272 // For cast operations, ensure result types are base types
273 if instr.Op == ir.OpCast && b.isSubWordType(resultType) {
274 resultType = ir.GetType(nil, b.prog.WordSize)
275 }
276
277 fmt.Fprintf(b.out, "%s =%s ", b.formatValue(instr.Result), b.formatType(resultType))
278 }
279
280 opStr, _ := b.formatOp(instr)
281 b.out.WriteString(opStr)
282
283 if instr.Op == ir.OpPhi {
284 for i := 0; i < len(instr.Args); i += 2 {
285 fmt.Fprintf(b.out, " @%s %s", instr.Args[i].String(), b.formatValue(instr.Args[i+1]))
286 if i+2 < len(instr.Args) {
287 b.out.WriteString(",")
288 }
289 }
290 } else {
291 for i, arg := range instr.Args {
292 b.out.WriteString(" ")
293 if arg != nil {
294 b.out.WriteString(b.formatValue(arg))
295 }
296 if i < len(instr.Args)-1 {
297 b.out.WriteString(",")
298 }
299 }
300 }
301 b.out.WriteString("\n")
302}
303
304func (b *qbeBackend) genFloatArithmetic(instr *ir.Instruction) {
305 // For float arithmetic operations, handle operands appropriately
306 resultType := instr.Typ
307
308 // Build arguments - no extension needed if operands match result type
309 var args []string
310 for _, arg := range instr.Args {
311 if arg == nil {
312 args = append(args, "")
313 continue
314 }
315
316 if floatConst, ok := arg.(*ir.FloatConst); ok {
317 // Float constants can be directly used with the proper format
318 if resultType == ir.TypeD {
319 args = append(args, fmt.Sprintf("d_%f", floatConst.Value))
320 } else {
321 args = append(args, b.formatValue(arg))
322 }
323 } else {
324 // For temporaries, use directly - the type system ensures consistency
325 args = append(args, b.formatValue(arg))
326 }
327 }
328
329 // Generate the arithmetic instruction
330 b.out.WriteString("\t")
331 if instr.Result != nil {
332 fmt.Fprintf(b.out, "%s =%s ", b.formatValue(instr.Result), b.formatType(resultType))
333 }
334
335 opStr, _ := b.formatOp(instr)
336 b.out.WriteString(opStr)
337
338 for i, argStr := range args {
339 b.out.WriteString(" " + argStr)
340 if i < len(args)-1 {
341 b.out.WriteString(",")
342 }
343 }
344 b.out.WriteString("\n")
345}
346
347func (b *qbeBackend) genByteArithmetic(instr *ir.Instruction) {
348 // For byte arithmetic operations, we need to handle operand type conversion
349 // Generate intermediate temporaries with proper extensions when needed
350 resultType := ir.GetType(nil, b.prog.WordSize) // long on 64-bit
351
352 // Convert operands to the target type by generating extension instructions
353 var convertedArgs []string
354 for _, arg := range instr.Args {
355 if arg == nil {
356 convertedArgs = append(convertedArgs, "")
357 continue
358 }
359
360 if const_arg, ok := arg.(*ir.Const); ok {
361 // Constants can be directly used with the right value
362 convertedArgs = append(convertedArgs, fmt.Sprintf("%d", const_arg.Value))
363 } else {
364 // For temporaries, we need to generate an extension instruction
365 extTemp := fmt.Sprintf("%%ext_%d", b.extCounter)
366 b.extCounter++
367 // Generate extension instruction: extTemp =l extsw arg (word to long)
368 b.out.WriteString(fmt.Sprintf("\t%s =%s extsw %s\n",
369 extTemp, b.formatType(resultType), b.formatValue(arg)))
370 convertedArgs = append(convertedArgs, extTemp)
371 }
372 }
373
374 // Now generate the actual arithmetic instruction with converted operands
375 b.out.WriteString("\t")
376 if instr.Result != nil {
377 fmt.Fprintf(b.out, "%s =%s ", b.formatValue(instr.Result), b.formatType(resultType))
378 }
379
380 opStr, _ := b.formatOp(instr)
381 b.out.WriteString(opStr)
382
383 for i, argStr := range convertedArgs {
384 b.out.WriteString(" " + argStr)
385 if i < len(convertedArgs)-1 {
386 b.out.WriteString(",")
387 }
388 }
389 b.out.WriteString("\n")
390}
391
392// isSubWordType checks if a type needs promotion for QBE function calls
393func (b *qbeBackend) isSubWordType(t ir.Type) bool {
394 return t == ir.TypeB || t == ir.TypeSB || t == ir.TypeUB ||
395 t == ir.TypeH || t == ir.TypeSH || t == ir.TypeUH || t == ir.TypeW
396}
397
398func (b *qbeBackend) genCall(instr *ir.Instruction) {
399 callee := instr.Args[0]
400 calleeName := ""
401 if g, ok := callee.(*ir.Global); ok {
402 calleeName = g.Name
403 }
404
405 // Pre-generate all needed extension instructions
406 var processedArgs []struct {
407 value string
408 targetType ir.Type
409 }
410
411 for i, arg := range instr.Args[1:] {
412 argType := ir.GetType(nil, b.prog.WordSize)
413 if instr.ArgTypes != nil && i < len(instr.ArgTypes) {
414 argType = instr.ArgTypes[i]
415 }
416
417 argValue := b.formatValue(arg)
418 targetType := argType
419
420 // Promote sub-word types to target word size and generate extension if needed
421 if b.isSubWordType(argType) {
422 targetType = ir.GetType(nil, b.prog.WordSize)
423 if argType != targetType {
424 extTemp := fmt.Sprintf("%%ext_%d", b.extCounter)
425 b.extCounter++
426
427 // Select extension operation based on source type
428 var extOp string
429 switch argType {
430 case ir.TypeW: extOp = "extsw"
431 case ir.TypeUB: extOp = "extub"
432 case ir.TypeSB: extOp = "extsb"
433 case ir.TypeUH: extOp = "extuh"
434 case ir.TypeSH: extOp = "extsh"
435 default:
436 extOp = "extub" // Default for ambiguous b/h types
437 }
438
439 // Generate extension instruction before the call
440 fmt.Fprintf(b.out, "\t%s =%s %s %s\n", extTemp, b.formatType(targetType), extOp, argValue)
441 argValue = extTemp
442 }
443 }
444
445 processedArgs = append(processedArgs, struct {
446 value string
447 targetType ir.Type
448 }{argValue, targetType})
449 }
450
451 // Generate result assignment if needed
452 if instr.Result != nil {
453 var retTypeStr string
454 calledFunc := b.prog.FindFunc(calleeName)
455 if calledFunc != nil && calledFunc.AstReturnType != nil && calledFunc.AstReturnType.Kind == ast.TYPE_STRUCT {
456 retTypeStr = " :" + calledFunc.AstReturnType.Name
457 } else {
458 retTypeStr = b.formatType(instr.Typ)
459 }
460 fmt.Fprintf(b.out, "\t%s =%s ", b.formatValue(instr.Result), retTypeStr)
461 } else {
462 b.out.WriteString("\t")
463 }
464
465 // Generate call with processed arguments
466 fmt.Fprintf(b.out, "call %s(", b.formatValue(callee))
467 for i, arg := range processedArgs {
468 if i > 0 {
469 b.out.WriteString(", ")
470 }
471 fmt.Fprintf(b.out, "%s %s", b.formatType(arg.targetType), arg.value)
472 }
473 b.out.WriteString(")\n")
474}
475
476func (b *qbeBackend) formatValue(v ir.Value) string {
477 if v == nil {
478 return ""
479 }
480 switch val := v.(type) {
481 case *ir.Const: return fmt.Sprintf("%d", val.Value)
482 case *ir.FloatConst:
483 if val.Typ == ir.TypeS {
484 // For 32-bit floats, truncate to float32 precision first
485 float32Val := float32(val.Value)
486 return fmt.Sprintf("s_%f", float64(float32Val))
487 }
488 return fmt.Sprintf("%s_%f", b.formatType(val.Typ), val.Value)
489 case *ir.Global: return "$" + val.Name
490 case *ir.Temporary:
491 safeName := strings.NewReplacer(".", "_", "[", "_", "]", "_").Replace(val.Name)
492 if val.ID == -1 {
493 return "%" + safeName
494 }
495 if safeName != "" {
496 return fmt.Sprintf("%%.%s_%d", safeName, val.ID)
497 }
498 return fmt.Sprintf("%%t%d", val.ID)
499 case *ir.Label: return "@" + val.Name
500 default:
501 return ""
502 }
503}
504
505func (b *qbeBackend) formatType(t ir.Type) string {
506 switch t {
507 case ir.TypeB, ir.TypeSB, ir.TypeUB:
508 return "b"
509 case ir.TypeH, ir.TypeSH, ir.TypeUH:
510 return "h"
511 case ir.TypeW:
512 return "w"
513 case ir.TypeL:
514 return "l"
515 case ir.TypeS:
516 return "s"
517 case ir.TypeD:
518 return "d"
519 case ir.TypePtr:
520 return b.formatType(ir.GetType(nil, b.prog.WordSize))
521 default:
522 return ""
523 }
524}
525
526func (b *qbeBackend) getCmpInstType(argType ir.Type) string {
527 if b.isSubWordType(argType) {
528 return b.formatType(ir.GetType(nil, b.prog.WordSize))
529 }
530 return b.formatType(argType)
531}
532
533func (b *qbeBackend) formatOp(instr *ir.Instruction) (opStr string, isCall bool) {
534 typ := instr.Typ
535 argType := instr.OperandType
536 if argType == ir.TypeNone {
537 argType = instr.Typ
538 }
539
540 typeStr := b.formatType(typ)
541 argTypeStr := b.getCmpInstType(argType)
542
543 switch instr.Op {
544 case ir.OpAlloc:
545 if instr.Align <= 4 {
546 return "alloc4", false
547 }
548 if instr.Align <= 8 {
549 return "alloc8", false
550 }
551 return "alloc16", false
552 case ir.OpLoad:
553 switch typ {
554 case ir.TypeB:
555 return "loadub", false // ambiguous, default to unsigned
556 case ir.TypeSB:
557 return "loadsb", false // signed byte
558 case ir.TypeUB:
559 return "loadub", false // unsigned byte
560 case ir.TypeH:
561 return "loaduh", false // ambiguous, default to unsigned
562 case ir.TypeSH:
563 return "loadsh", false // signed half
564 case ir.TypeUH:
565 return "loaduh", false // unsigned half
566 case ir.TypePtr:
567 return "load" + b.formatType(ir.GetType(nil, b.prog.WordSize)), false
568 default:
569 return "load" + typeStr, false
570 }
571 case ir.OpStore:
572 return "store" + typeStr, false
573 case ir.OpBlit:
574 return "blit", false
575 case ir.OpAdd, ir.OpAddF:
576 return "add", false
577 case ir.OpSub, ir.OpSubF:
578 return "sub", false
579 case ir.OpMul, ir.OpMulF:
580 return "mul", false
581 case ir.OpDiv, ir.OpDivF:
582 return "div", false
583 case ir.OpRem, ir.OpRemF:
584 return "rem", false
585 case ir.OpAnd:
586 return "and", false
587 case ir.OpOr:
588 return "or", false
589 case ir.OpXor:
590 return "xor", false
591 case ir.OpShl:
592 return "shl", false
593 case ir.OpShr:
594 return "shr", false
595 case ir.OpNegF:
596 return "neg", false
597 case ir.OpCEq:
598 return "ceq" + argTypeStr, false
599 case ir.OpCNeq:
600 return "cne" + argTypeStr, false
601 case ir.OpCLt:
602 if argType == ir.TypeS || argType == ir.TypeD {
603 return "clt" + argTypeStr, false
604 }
605 return "cslt" + argTypeStr, false
606 case ir.OpCGt:
607 if argType == ir.TypeS || argType == ir.TypeD {
608 return "cgt" + argTypeStr, false
609 }
610 return "csgt" + argTypeStr, false
611 case ir.OpCLe:
612 if argType == ir.TypeS || argType == ir.TypeD {
613 return "cle" + argTypeStr, false
614 }
615 return "csle" + argTypeStr, false
616 case ir.OpCGe:
617 if argType == ir.TypeS || argType == ir.TypeD {
618 return "cge" + argTypeStr, false
619 }
620 return "csge" + argTypeStr, false
621 case ir.OpJmp:
622 return "jmp", false
623 case ir.OpJnz:
624 return "jnz", false
625 case ir.OpRet:
626 return "ret", false
627 case ir.OpCall:
628 return "call", true
629 case ir.OpPhi:
630 return "phi", false
631 case ir.OpSWToF:
632 return "swtof", false
633 case ir.OpSLToF:
634 return "sltof", false
635 case ir.OpFToF:
636 if typ == ir.TypeD {
637 return "exts", false
638 }
639 return "truncd", false
640 case ir.OpExtSB, ir.OpExtUB, ir.OpExtSH, ir.OpExtUH, ir.OpExtSW, ir.OpExtUW:
641 return "exts" + string(b.formatType(argType)[0]), false
642 case ir.OpFToSI:
643 return "ftosi", false
644 case ir.OpFToUI:
645 return "ftoui", false
646 case ir.OpCast:
647 return "copy", false
648 default:
649 return "unknown_op", false
650 }
651}