Debian Codegraph @

_gen/gen-arm-sve.go

raw
1 // Copyright 2024, Klaus Post/Minio Inc. See LICENSE for details.
2
3 package main
4
5 import (
6 "bufio"
7 "bytes"
8 "fmt"
9 "log"
10 "os"
11 "regexp"
12 "slices"
13 "strconv"
14 "strings"
15
16 avxtwo2sve "github.com/fwessels/avxTwo2sve"
17 sve_as "github.com/fwessels/sve-as"
18 )
19
20 func patchLabel(line string) string {
21 return strings.ReplaceAll(line, "AvxTwo", "Sve")
22 }
23
24 func extractRoutine(filename, routine string) (lines []string, err error) {
25 file, err := os.Open(filename)
26 if err != nil {
27 return
28 }
29 defer file.Close()
30
31 // Create a scanner to read the file line by line
32 scanner := bufio.NewScanner(file)
33
34 // Iterate over each line
35 collect := false
36 for scanner.Scan() {
37 line := scanner.Text()
38 if strings.HasPrefix(line, routine) {
39 collect = true
40 }
41 if collect {
42 lines = append(lines, line)
43 }
44 if collect && strings.HasSuffix(line, "RET") {
45 collect = false
46 }
47 }
48
49 // Check for any errors that occurred during scanning
50 err = scanner.Err()
51 return
52 }
53
54 func addArmInitializations(instructions []string) (processed []string) {
55 for _, instr := range instructions {
56 processed = append(processed, instr)
57 if strings.HasPrefix(instr, "TEXT ·") {
58 sve := "ptrue p0.d"
59 opcode, err := sve_as.Assemble(sve)
60 if err != nil {
61 processed = append(processed, fmt.Sprintf(" WORD $0x00000000 // %-44s\n", sve))
62 } else {
63 processed = append(processed, fmt.Sprintf(" WORD $0x%08x // %-44s\n", opcode, sve))
64 }
65 }
66 }
67 return
68 }
69
70 // Expand #defines
71 func expandHashDefines(instructions []string) (processed []string) {
72 for _, instr := range instructions {
73 if strings.Contains(instr, "XOR3WAY") {
74 f := strings.Fields(instr)
75 if len(f) >= 3 {
76 dst := strings.ReplaceAll(f[len(f)-1], ")", "")
77 b := strings.ReplaceAll(f[len(f)-2], ",", "")
78 a := strings.ReplaceAll(f[len(f)-3], ",", "")
79
80 processed = append(processed, fmt.Sprintf("VPXOR %s, %s, %s", a, dst, dst))
81 processed = append(processed, fmt.Sprintf("VPXOR %s, %s, %s", b, dst, dst))
82 } else {
83 log.Fatalf("Not enough arguments for 'XOR3WAY' macro: %d", len(f))
84 }
85 } else if !strings.Contains(instr, "VZEROUPPER") {
86 processed = append(processed, instr)
87 }
88 }
89 return
90 }
91
92 func convertRoutine(asmBuf *bytes.Buffer, instructions []string) {
93
94 asmF := func(format string, args ...interface{}) {
95 (*asmBuf).WriteString(fmt.Sprintf(format, args...))
96 }
97
98 wordOpcode := regexp.MustCompile(`WORD \$0x[0-9a-f]{8}`)
99
100 for _, instr := range instructions {
101 instr = strings.TrimSpace(instr)
102 if instr == "" {
103 asmF("\n")
104 } else if strings.HasPrefix(instr, "TEXT ") { // function header
105 asmF("%s\n", patchLabel(instr))
106 } else if wordOpcode.MatchString(instr) { // arm code
107 asmF(" %s\n", instr)
108 } else if strings.HasPrefix(instr, "//") { // comment
109 asmF(" %s\n", instr)
110 } else if strings.HasSuffix(instr, ":") { // label
111 asmF("%s\n", patchLabel(instr))
112 } else {
113 sve, plan9, err := avxtwo2sve.AvxTwo2Sve(instr, patchLabel)
114 if err != nil {
115 panic(err)
116 } else if !plan9 {
117 opcode, err := sve_as.Assemble(sve)
118 if err != nil {
119 asmF(" WORD $0x00000000 // %-44s\n", sve)
120 } else {
121 asmF(" WORD $0x%08x // %-44s\n", opcode, sve)
122 }
123 } else {
124 asmF(" %s\n", sve)
125 }
126 }
127 }
128 }
129
130 // convert (R..*1) memory accesses into (R..*8) offsets
131 func patchScaledLoads(code string, outputs int, isXor bool) (patched []string) {
132
133 scaledMemOps := strings.Count(code, "*1)")
134 if scaledMemOps == 0 {
135 // in case of no scaled loads, exit out early
136 return strings.Split(code, "\n")
137 }
138
139 sanityCheck := outputs
140 if isXor {
141 sanityCheck *= 2 // need to load all values as well as store them
142 }
143 if scaledMemOps != sanityCheck {
144 panic("Couldn't find expected number of scaled memory ops")
145 }
146
147 scaledReg := ""
148 re := regexp.MustCompile(`R(\d+)\*1`)
149 if match := re.FindStringSubmatch(code); len(match) > 1 {
150 scaledReg = fmt.Sprintf("R%s", match[1])
151 } else {
152 panic("Failed to find register used for scaled memory ops")
153 }
154
155 const inputs = 10
156
157 scaledRegUses := strings.Count(code, scaledReg)
158 sanityCheck += inputs // needed to add start offset to input
159 sanityCheck += 1 // needed to load offset from stack
160 sanityCheck += 1 // needed to increment offset
161
162 if scaledRegUses != sanityCheck {
163 panic("Did not find expected number of uses of scaled register")
164 }
165
166 // Adjust all scaled loads
167 code = strings.ReplaceAll(code, fmt.Sprintf("(%s*1)", scaledReg), fmt.Sprintf("(%s*8)", scaledReg))
168
169 // Adjust increment at end of loop
170 reAdd := regexp.MustCompile(`ADDQ\s*\$(0x[0-9a-f]+),\s*` + scaledReg)
171 if match := reAdd.FindStringSubmatch(code); len(match) > 1 && match[1][:2] == "0x" {
172 if increment, err := strconv.ParseInt(match[1][2:], 16, 64); err == nil {
173 code = strings.ReplaceAll(code, fmt.Sprintf("0x%x, %s", increment, scaledReg), fmt.Sprintf("0x%02x, %s", increment>>3, scaledReg))
174 } else {
175 panic(err)
176 }
177 } else {
178 panic("Failed to find increment of offset")
179 }
180
181 // Add shift instruction during initialization after inputs have been adjusted
182 reShift := regexp.MustCompilePOSIX(fmt.Sprintf(`^[[:blank:]]+ADDQ[[:blank:]]+%s.*$`, scaledReg))
183 if matches := reShift.FindAllStringIndex(code, -1); len(matches) == inputs {
184 lastInpIncr := code[matches[inputs-1][0]:matches[inputs-1][1]]
185 shiftCorrection := strings.ReplaceAll(strings.Split(lastInpIncr, scaledReg)[0], "ADDQ", "SHRQ")
186 shiftCorrection += "$0x03, " + scaledReg
187 code = strings.ReplaceAll(code, lastInpIncr, lastInpIncr+"\n"+shiftCorrection)
188 } else {
189 fmt.Println(matches)
190 panic("Did not find expected number start offset corrections")
191 }
192
193 return strings.Split(code, "\n")
194 }
195
196 func fromAvx2ToSve() {
197 asmOut, goOut := &bytes.Buffer{}, &bytes.Buffer{}
198
199 goOut.WriteString(`// Code generated by command: go generate ` + os.Getenv("GOFILE") + `. DO NOT EDIT.` + "\n\n")
200 goOut.WriteString("//go:build !noasm && !appengine && !gccgo && !nopshufb\n\n")
201 goOut.WriteString("package reedsolomon\n\n")
202
203 const input = 10
204 const AVX2_CODE = "../galois_gen_amd64.s"
205
206 // Processing 64 bytes variants
207 for output := 1; output <= 3; output++ {
208 for op := ""; len(op) <= 3; op += "Xor" {
209 templName := fmt.Sprintf("mulAvxTwo_%dx%d_64%s", input, output, op)
210 funcDef := fmt.Sprintf("func %s(matrix []byte, in [][]byte, out [][]byte, start int, n int)", strings.ReplaceAll(templName, "AvxTwo", "Sve"))
211
212 // asm first
213 lines, err := extractRoutine(AVX2_CODE, fmt.Sprintf("TEXT ·%s(SB)", templName))
214 if err != nil {
215 log.Fatal(err)
216 }
217 lines = patchScaledLoads(strings.Join(lines, "\n"), output, strings.HasSuffix(templName, "Xor"))
218 lines = expandHashDefines(lines)
219
220 convertRoutine(asmOut, lines)
221
222 // add newline after RET
223 asmOut.WriteString("\n")
224
225 // golang declaration
226 goOut.WriteString(fmt.Sprintf("//go:noescape\n%s\n\n", funcDef))
227 }
228 }
229
230 // Processing 32 bytes variants
231 for output := 4; output <= 10; output++ {
232 for op := ""; len(op) <= 3; op += "Xor" {
233 templName := fmt.Sprintf("mulAvxTwo_%dx%d%s", input, output, op)
234 funcDef := fmt.Sprintf("func %s(matrix []byte, in [][]byte, out [][]byte, start int, n int)", strings.ReplaceAll(templName, "AvxTwo", "Sve"))
235
236 // asm first
237 lines, err := extractRoutine(AVX2_CODE, fmt.Sprintf("TEXT ·%s(SB)", templName))
238 if err != nil {
239 log.Fatal(err)
240 }
241 lines = patchScaledLoads(strings.Join(lines, "\n"), output, strings.HasSuffix(templName, "Xor"))
242 lines = expandHashDefines(lines)
243
244 // add additional initialization for SVE
245 // (for predicated loads and stores in
246 // case of register shortage)
247 lines = addArmInitializations(lines)
248
249 convertRoutine(asmOut, lines)
250
251 // add newline after RET
252 asmOut.WriteString("\n")
253
254 // golang declaration
255 goOut.WriteString(fmt.Sprintf("//go:noescape\n%s\n\n", funcDef))
256 }
257 }
258
259 if err := os.WriteFile("../galois_gen_arm64.s", asmOut.Bytes(), 0644); err != nil {
260 log.Fatal(err)
261 }
262 if err := os.WriteFile("../galois_gen_arm64.go", goOut.Bytes(), 0644); err != nil {
263 log.Fatal(err)
264 }
265 }
266
267 func insertEarlyExit(lines []string, funcName string, outputs int) (processed []string) {
268
269 const reg = "R16"
270 label := funcName + "_store"
271
272 reComment := regexp.MustCompile(fmt.Sprintf(`// Load and process \d* bytes from input (\d*) to %d outputs`, outputs))
273 reLoop := regexp.MustCompile(`^` + strings.ReplaceAll(label, "store", "loop") + `:`)
274 reStore := regexp.MustCompile(fmt.Sprintf(`// Store %d outputs`, outputs))
275
276 for _, line := range lines {
277 if matches := reLoop.FindAllStringSubmatch(line, -1); len(matches) == 1 {
278 lastline := processed[len(processed)-1]
279 processed = processed[:len(processed)-1]
280 processed = append(processed, "")
281 processed = append(processed, fmt.Sprintf(" // Load number of input shards"))
282 processed = append(processed, fmt.Sprintf(" MOVD in_len+32(FP), %s", reg))
283 processed = append(processed, lastline)
284 }
285
286 if matches := reComment.FindAllStringSubmatch(line, -1); len(matches) == 1 {
287 if inputs, err := strconv.Atoi(matches[0][1]); err != nil {
288 panic(err)
289 } else {
290 if inputs > 0 && inputs < 10 {
291 lastline := processed[len(processed)-1]
292 processed = processed[:len(processed)-1]
293 processed = append(processed, fmt.Sprintf(" // Check for early termination"))
294 processed = append(processed, fmt.Sprintf(" CMP $%d, %s", inputs, reg))
295 processed = append(processed, fmt.Sprintf(" BEQ %s", label))
296 processed = append(processed, lastline)
297 }
298 }
299 }
300
301 if matches := reStore.FindAllStringSubmatch(line, -1); len(matches) == 1 {
302 processed = append(processed, fmt.Sprintf("%s:", label))
303 }
304
305 processed = append(processed, line)
306 }
307 return
308 }
309
310 func addEarlyExit(arch string) {
311 const filename = "../galois_gen_arm64.s"
312 asmOut := &bytes.Buffer{}
313
314 asmOut.WriteString(`// Code generated by command: go generate ` + os.Getenv("GOFILE") + `. DO NOT EDIT.` + "\n\n")
315 asmOut.WriteString("//go:build !appengine && !noasm && !nogen && !nopshufb && gc\n\n")
316 asmOut.WriteString(`#include "textflag.h"` + "\n\n")
317
318 input := 10
319 for outputs := 1; outputs <= 3; outputs++ {
320 for op := ""; len(op) <= 3; op += "Xor" {
321 funcName := fmt.Sprintf("mul%s_%dx%d_64%s", arch, input, outputs, op)
322 funcDef := fmt.Sprintf("func %s(matrix []byte, in [][]byte, out [][]byte, start int, n int)", funcName)
323
324 lines, _ := extractRoutine(filename, fmt.Sprintf("TEXT ·%s(SB)", funcName))
325
326 // prepend output with commented out function definition and comment
327 asmOut.WriteString(fmt.Sprintf("// %s\n", funcDef))
328 asmOut.WriteString("// Requires: SVE\n")
329
330 lines = insertEarlyExit(lines, funcName, outputs)
331
332 asmOut.WriteString(strings.Join(lines, "\n"))
333 asmOut.WriteString("\n\n")
334 }
335 }
336
337 for outputs := 4; outputs <= 10; outputs++ {
338 for op := ""; len(op) <= 3; op += "Xor" {
339 funcName := fmt.Sprintf("mul%s_%dx%d%s", arch, input, outputs, op)
340 funcDef := fmt.Sprintf("func %s(matrix []byte, in [][]byte, out [][]byte, start int, n int)", funcName)
341
342 lines, _ := extractRoutine(filename, fmt.Sprintf("TEXT ·%s(SB)", funcName))
343
344 // prepend output with commented out function definition and comment
345 asmOut.WriteString(fmt.Sprintf("// %s\n", funcDef))
346 asmOut.WriteString("// Requires: SVE\n")
347
348 lines = insertEarlyExit(lines, funcName, outputs)
349 asmOut.WriteString(strings.Join(lines, "\n"))
350 asmOut.WriteString("\n\n")
351 }
352 }
353
354 if err := os.WriteFile("../galois_gen_arm64.s", asmOut.Bytes(), 0644); err != nil {
355 log.Fatal(err)
356 }
357 }
358
359 func genArmSve() {
360 fromAvx2ToSve()
361 addEarlyExit("Sve")
362 }
363
364 func assemble(sve string) string {
365 opcode, err := sve_as.Assemble(sve)
366 if err != nil {
367 return fmt.Sprintf(" WORD $0x00000000 // %s", sve)
368 } else {
369 return fmt.Sprintf(" WORD $0x%08x // %s", opcode, sve)
370 }
371 }
372
373 func addArmSveVectorLength() (addInits []string) {
374 const filename = "../galois_gen_arm64.s"
375 asmOut := &bytes.Buffer{}
376
377 file, err := os.Open(filename)
378 if err != nil {
379 return
380 }
381 defer file.Close()
382
383 // Create a scanner to read the file line by line
384 scanner := bufio.NewScanner(file)
385
386 routine := ""
387 addInits = make([]string, 0)
388
389 // Iterate over each line
390 for scanner.Scan() {
391 line := scanner.Text()
392
393 if strings.HasPrefix(line, "TEXT ·") {
394 routine = line
395 }
396
397 correctShift := func(shift, vl string) {
398 if strings.Contains(line, " // lsr ") && strings.HasSuffix(strings.TrimSpace(line), ", "+shift) {
399 instr := strings.Split(strings.TrimSpace(line), "// lsr ")[1]
400 args := strings.Split(instr, ", ")
401 if len(args) == 3 && args[0] == args[1] {
402 // keep the original right shift, but reverse the effect (so effectively
403 // clearing out the lower bits so we cannot do eg. "half loops" )
404 line += "\n"
405 line += assemble(fmt.Sprintf("lsl %s, %s, %s", args[0], args[1], shift)) + "\n"
406 line += assemble(fmt.Sprintf("rdvl x16, %s", vl)) + "\n"
407 line += assemble(fmt.Sprintf("udiv %s, %s, x16", args[0], args[1]))
408 }
409 }
410 }
411
412 correctShift("#6", "#2")
413 correctShift("#5", "#1")
414
415 if strings.Contains(line, " // add ") && strings.HasSuffix(strings.TrimSpace(line), "#64") {
416 instr := strings.Split(strings.TrimSpace(line), "// add ")[1]
417 args := strings.Split(instr, ", ")
418 if len(args) == 3 && args[0] == args[1] {
419 line = assemble(fmt.Sprintf("addvl %s, %s, #2", args[0], args[1]))
420 }
421 }
422
423 if strings.Contains(line, " // add ") && strings.HasSuffix(strings.TrimSpace(line), "#32") {
424 instr := strings.Split(strings.TrimSpace(line), "// add ")[1]
425 args := strings.Split(instr, ", ")
426 if len(args) == 3 && args[0] == args[1] {
427 line = assemble(fmt.Sprintf("addvl %s, %s, #1", args[0], args[1]))
428 }
429 }
430
431 if strings.Contains(line, " // add ") && strings.HasSuffix(strings.TrimSpace(line), "#4") {
432 // mark routine as needing initialization of register 17
433 addInits = append(addInits, routine)
434 line = assemble("add x15, x15, x17")
435 }
436
437 asmOut.WriteString(line + "\n")
438 }
439
440 // Check for any errors that occurred during scanning
441 if err = scanner.Err(); err != nil {
442 log.Fatal(err)
443 } else if err = os.WriteFile("../galois_gen_arm64.s", asmOut.Bytes(), 0644); err != nil {
444 log.Fatal(err)
445 }
446
447 return
448 }
449
450 func addArmSveInitializations(addInits []string) {
451
452 const filename = "../galois_gen_arm64.s"
453 asmOut := &bytes.Buffer{}
454
455 file, err := os.Open(filename)
456 if err != nil {
457 return
458 }
459 defer file.Close()
460
461 // Create a scanner to read the file line by line
462 scanner := bufio.NewScanner(file)
463 routine := ""
464 checkNextLine := false
465
466 // Iterate over each line
467 for scanner.Scan() {
468 line := scanner.Text()
469
470 if strings.HasPrefix(line, "TEXT ·") {
471 routine = line
472 }
473
474 if strings.Contains(line, "// Load number of input shards") {
475 checkNextLine = true
476 } else {
477 if checkNextLine {
478 idx := slices.IndexFunc(addInits, func(s string) bool { return s == routine })
479 if idx != -1 {
480 line += "\n"
481 line += assemble("rdvl x17, #1") + "\n"
482 line += assemble("lsr x17, x17, #3")
483 }
484 checkNextLine = false
485 }
486 }
487
488 asmOut.WriteString(line + "\n")
489 }
490
491 // Check for any errors that occurred during scanning
492 if err = scanner.Err(); err != nil {
493 log.Fatal(err)
494 } else if err = os.WriteFile("../galois_gen_arm64.s", asmOut.Bytes(), 0644); err != nil {
495 log.Fatal(err)
496 }
497 }
498
499 func genArmSveAllVl() {
500 addInits := addArmSveVectorLength()
501 addArmSveInitializations(addInits)
502 }