Implement variable length arrays

Variably modified types are required for C23.

Since QBE doesn't currently support saving and restoring the stack
pointer, a current limitation is that we can't reclaim stack space
from VLAs that go out of scope. This is potentially problematic for
VLAs appearing in a loop, but this case is uncommon enough that it
is silently ignored for now.

Implements: https://todo.sr.ht/~mcf/cproc/1
References: https://todo.sr.ht/~mcf/cproc/88
Co-authored-by: Michael Forney <mforney@mforney.org>

20 files changed, 571 insertions, 0 deletions

diff --git a/test/alignas-vla-strict.c b/test/alignas-vla-strict.c
new file mode 100644
index 0000000..0f5a326
--- /dev/null
+++ b/test/alignas-vla-strict.c
@@ -0,0 +1,5 @@
+int n = 43;
+int main(void) {
+	char alignas(64) a[n];
+	return (unsigned long)a % 64;
+}
diff --git a/test/alignas-vla-strict.qbe b/test/alignas-vla-strict.qbe
new file mode 100644
index 0000000..8fdc595
--- /dev/null
+++ b/test/alignas-vla-strict.qbe
@@ -0,0 +1,16 @@
+export data $n = align 4 { w 43, }
+export
+function w $main() {
+@start.1
+@body.2
+	%.1 =w loadw $n
+	%.2 =l extsw %.1
+	%.3 =l mul %.2, 1
+	%.4 =l add %.3, 48
+	%.5 =l alloc16 %.4
+	%.6 =l add %.5, 48
+	%.7 =l and %.6, 18446744073709551552
+	%.8 =l extsw 64
+	%.9 =l urem %.7, %.8
+	ret %.9
+}
diff --git a/test/builtin-vaarg-vm.c b/test/builtin-vaarg-vm.c
new file mode 100644
index 0000000..aee7216
--- /dev/null
+++ b/test/builtin-vaarg-vm.c
@@ -0,0 +1,16 @@
+int f(int i, ...) {
+	int r, c = 0;
+	__builtin_va_list ap;
+
+	__builtin_va_start(ap, i);
+	r = **__builtin_va_arg(ap, int (*)[++i]);
+	__builtin_va_end(ap);
+	return r + i;
+}
+
+int main(void) {
+	int a[3];
+
+	a[0] = 123;
+	return f(3, &a) != 127;
+}
diff --git a/test/builtin-vaarg-vm.qbe b/test/builtin-vaarg-vm.qbe
new file mode 100644
index 0000000..814e3d0
--- /dev/null
+++ b/test/builtin-vaarg-vm.qbe
@@ -0,0 +1,37 @@
+export
+function w $f(w %.1, ...) {
+@start.1
+	%.2 =l alloc4 4
+	storew %.1, %.2
+	%.3 =l alloc4 4
+	%.4 =l alloc4 4
+	%.5 =l alloc8 24
+@body.2
+	storew 0, %.4
+	vastart %.5
+	%.6 =w loadw %.2
+	%.7 =w add %.6, 1
+	storew %.7, %.2
+	%.8 =l extsw %.7
+	%.9 =l mul %.8, 4
+	%.10 =l vaarg %.5
+	%.11 =w loadw %.10
+	storew %.11, %.3
+	%.12 =w loadw %.3
+	%.13 =w loadw %.2
+	%.14 =w add %.12, %.13
+	ret %.14
+}
+export
+function w $main() {
+@start.3
+	%.1 =l alloc4 12
+@body.4
+	%.2 =l extsw 0
+	%.3 =l mul %.2, 4
+	%.4 =l add %.1, %.3
+	storew 123, %.4
+	%.5 =w call $f(w 3, ..., l %.1)
+	%.6 =w cnew %.5, 127
+	ret %.6
+}
diff --git a/test/cast-vm.c b/test/cast-vm.c
new file mode 100644
index 0000000..6901e73
--- /dev/null
+++ b/test/cast-vm.c
@@ -0,0 +1,6 @@
+int main(void) {
+	int l = 0;
+	(int (*)[++l])0;
+	(int (*(*)(void))[++l])0;
+	return l != 2;
+}
diff --git a/test/cast-vm.qbe b/test/cast-vm.qbe
new file mode 100644
index 0000000..2ca3f7d
--- /dev/null
+++ b/test/cast-vm.qbe
@@ -0,0 +1,22 @@
+export
+function w $main() {
+@start.1
+	%.1 =l alloc4 4
+@body.2
+	storew 0, %.1
+	%.2 =w loadw %.1
+	%.3 =w add %.2, 1
+	storew %.3, %.1
+	%.4 =l extsw %.3
+	%.5 =l mul %.4, 4
+	%.6 =l extsw 0
+	%.7 =w loadw %.1
+	%.8 =w add %.7, 1
+	storew %.8, %.1
+	%.9 =l extsw %.8
+	%.10 =l mul %.9, 4
+	%.11 =l extsw 0
+	%.12 =w loadw %.1
+	%.13 =w cnew %.12, 2
+	ret %.13
+}
diff --git a/test/compatible-vla-types.c b/test/compatible-vla-types.c
new file mode 100644
index 0000000..2f72dc5
--- /dev/null
+++ b/test/compatible-vla-types.c
@@ -0,0 +1,17 @@
+void f1(int n, int (*a)[n], int (*b)[*], int (*c)[3],
+	struct {
+		int x;
+		static_assert(__builtin_types_compatible_p(typeof(a), typeof(b)));
+		static_assert(__builtin_types_compatible_p(typeof(a), int (*)[3]));
+		static_assert(__builtin_types_compatible_p(typeof(b), int (*)[3]));
+		static_assert(__builtin_types_compatible_p(typeof(a), int (*)[]));
+		static_assert(__builtin_types_compatible_p(typeof(b), int (*)[]));
+	} s);
+void f2(void) {
+	int n = 12, m = 6 * 2;
+	static_assert(__builtin_types_compatible_p(int [n], int [12]));
+	static_assert(__builtin_types_compatible_p(int [], int [n]));
+	static_assert(__builtin_types_compatible_p(int [n], int [m]));
+	static_assert(__builtin_types_compatible_p(int [2][n], int [1 + 1][n]));
+	static_assert(!__builtin_types_compatible_p(int [4][n], int [5][n]));
+}
diff --git a/test/compatible-vla-types.qbe b/test/compatible-vla-types.qbe
new file mode 100644
index 0000000..330cd85
--- /dev/null
+++ b/test/compatible-vla-types.qbe
@@ -0,0 +1,11 @@
+export
+function $f2() {
+@start.1
+	%.1 =l alloc4 4
+	%.2 =l alloc4 4
+@body.2
+	storew 12, %.1
+	%.3 =w mul 6, 2
+	storew %.3, %.2
+	ret
+}
diff --git a/test/func-vla.c b/test/func-vla.c
new file mode 100644
index 0000000..6718c05
--- /dev/null
+++ b/test/func-vla.c
@@ -0,0 +1,8 @@
+int f(int n, long long (*a)[n]) {
+	return sizeof *a;
+}
+
+int main(void) {
+	long long a[5];
+	return f(5, &a) != sizeof a;
+}
diff --git a/test/func-vla.qbe b/test/func-vla.qbe
new file mode 100644
index 0000000..ac3cb9b
--- /dev/null
+++ b/test/func-vla.qbe
@@ -0,0 +1,24 @@
+export
+function w $f(w %.1, l %.3) {
+@start.1
+	%.2 =l alloc4 4
+	storew %.1, %.2
+	%.4 =w loadw %.2
+	%.5 =l extsw %.4
+	%.6 =l mul %.5, 8
+	%.7 =l alloc8 8
+	storel %.3, %.7
+@body.2
+	%.8 =l loadl %.7
+	ret %.6
+}
+export
+function w $main() {
+@start.3
+	%.1 =l alloc8 40
+@body.4
+	%.2 =w call $f(w 5, l %.1)
+	%.3 =l extsw %.2
+	%.4 =w cnel %.3, 40
+	ret %.4
+}
diff --git a/test/sizeof-vla.c b/test/sizeof-vla.c
new file mode 100644
index 0000000..16d6fa1
--- /dev/null
+++ b/test/sizeof-vla.c
@@ -0,0 +1,19 @@
+int c = 0;
+int main(void) {
+	int r = 0;
+	int l = 2;
+	int (*p)[l] = 0;
+	r += sizeof(c++, p) != sizeof(int (*)[]);       /* VM, but not VLA */
+	r += c != 0;
+	r += sizeof(*(c++, p)) != 2 * sizeof(int);      /* VLA */
+	r += c != 1;
+	r += sizeof(c++, *p) != sizeof(int *);          /* VLA decayed to pointer */
+	r += c != 1;
+	r += sizeof(int[++l]) != 3 * sizeof(int);       /* VLA */
+	r += l != 3;
+	r += sizeof(int[++l][1]) != sizeof(int[4][1]);  /* VLA */
+	r += l != 4;
+	r += sizeof(int[(c++, 5)]) != 5 * sizeof(int);  /* VLA */
+	r += c != 2;
+	return r;
+}
diff --git a/test/sizeof-vla.qbe b/test/sizeof-vla.qbe
new file mode 100644
index 0000000..44acda9
--- /dev/null
+++ b/test/sizeof-vla.qbe
@@ -0,0 +1,97 @@
+export data $c = align 4 { w 0, }
+export
+function w $main() {
+@start.1
+	%.1 =l alloc4 4
+	%.2 =l alloc4 4
+	%.6 =l alloc8 8
+@body.2
+	storew 0, %.1
+	storew 2, %.2
+	%.3 =w loadw %.2
+	%.4 =l extsw %.3
+	%.5 =l mul %.4, 4
+	%.7 =l extsw 0
+	storel %.7, %.6
+	%.8 =w loadw %.1
+	%.9 =w cnel 8, 8
+	%.10 =w add %.8, %.9
+	storew %.10, %.1
+	%.11 =w loadw %.1
+	%.12 =w loadw $c
+	%.13 =w cnew %.12, 0
+	%.14 =w add %.11, %.13
+	storew %.14, %.1
+	%.15 =w loadw %.1
+	%.16 =w loadw $c
+	%.17 =w add %.16, 1
+	storew %.17, $c
+	%.18 =l loadl %.6
+	%.19 =l extsw 2
+	%.20 =l mul %.19, 4
+	%.21 =w cnel %.5, %.20
+	%.22 =w add %.15, %.21
+	storew %.22, %.1
+	%.23 =w loadw %.1
+	%.24 =w loadw $c
+	%.25 =w cnew %.24, 1
+	%.26 =w add %.23, %.25
+	storew %.26, %.1
+	%.27 =w loadw %.1
+	%.28 =w cnel 8, 8
+	%.29 =w add %.27, %.28
+	storew %.29, %.1
+	%.30 =w loadw %.1
+	%.31 =w loadw $c
+	%.32 =w cnew %.31, 1
+	%.33 =w add %.30, %.32
+	storew %.33, %.1
+	%.34 =w loadw %.1
+	%.35 =w loadw %.2
+	%.36 =w add %.35, 1
+	storew %.36, %.2
+	%.37 =l extsw %.36
+	%.38 =l mul %.37, 4
+	%.39 =l extsw 3
+	%.40 =l mul %.39, 4
+	%.41 =w cnel %.38, %.40
+	%.42 =w add %.34, %.41
+	storew %.42, %.1
+	%.43 =w loadw %.1
+	%.44 =w loadw %.2
+	%.45 =w cnew %.44, 3
+	%.46 =w add %.43, %.45
+	storew %.46, %.1
+	%.47 =w loadw %.1
+	%.48 =w loadw %.2
+	%.49 =w add %.48, 1
+	storew %.49, %.2
+	%.50 =l extsw %.49
+	%.51 =l mul %.50, 4
+	%.52 =w cnel %.51, 16
+	%.53 =w add %.47, %.52
+	storew %.53, %.1
+	%.54 =w loadw %.1
+	%.55 =w loadw %.2
+	%.56 =w cnew %.55, 4
+	%.57 =w add %.54, %.56
+	storew %.57, %.1
+	%.58 =w loadw %.1
+	%.59 =w loadw $c
+	%.60 =w add %.59, 1
+	storew %.60, $c
+	%.61 =l extsw 5
+	%.62 =l mul %.61, 4
+	%.63 =l extsw 5
+	%.64 =l mul %.63, 4
+	%.65 =w cnel %.62, %.64
+	%.66 =w add %.58, %.65
+	storew %.66, %.1
+	%.67 =w loadw %.1
+	%.68 =w loadw $c
+	%.69 =w cnew %.68, 2
+	%.70 =w add %.67, %.69
+	storew %.70, %.1
+	%.71 =w loadw %.1
+	ret %.71
+}
diff --git a/test/typeof-vm.c b/test/typeof-vm.c
new file mode 100644
index 0000000..694a087
--- /dev/null
+++ b/test/typeof-vm.c
@@ -0,0 +1,49 @@
+int a[3] = {12, 34, 56};
+int b[3] = {'a', 'b', 'c'};
+int c = 0;
+int f(void) {
+	++c;
+	return 3;
+}
+int g(int n, ...) {
+	__builtin_va_list ap;
+	char (*p)[n] = 0;
+	int out = 1;
+
+	__builtin_va_start(ap, n);
+	__builtin_va_arg(ap, typeof(out--, p));
+	__builtin_va_end(ap);
+	return out;
+}
+int main(void) {
+	int r = 0;
+	int (*p)[f()] = 0;
+
+	r += c != 1;
+	typeof(c++, p) t1;            /* VM; evaluated */
+	r += c != 2;
+	typeof(p, c++) t2;            /* non-VM; not evaluated */
+	r += c != 2;
+	typeof(c++, **(p = &a)) t3;   /* non-VM; not evaluated */
+	r += c != 2;
+	r += p != 0;
+	typeof(*(p = (c++, &a))) t4;  /* VM, evaluated */
+	r += c != 3;
+	r += p != &a;
+	/*
+	while *(p = &b) has VM type, it is not the immediate operand
+	of typeof, so is converted from VLA to int pointer due to
+	the comma operator, so the typeof expression is not evaluated
+	*/
+	typeof(c++, *(p = &b)) t5;
+	r += c != 3;
+	r += p != &a;
+	(typeof(c++, p))0;
+	r += c != 4;
+	(typeof(c++, p)){0};
+	r += c != 5;
+	r += g(3, p);
+	typeof(typeof(c++, p)) t6;
+	r += c != 6;
+	return r;
+}
diff --git a/test/typeof-vm.qbe b/test/typeof-vm.qbe
new file mode 100644
index 0000000..c75de99
--- /dev/null
+++ b/test/typeof-vm.qbe
@@ -0,0 +1,148 @@
+export data $a = align 4 { w 12, w 34, w 56, }
+export data $b = align 4 { w 97, w 98, w 99, }
+export data $c = align 4 { w 0, }
+export
+function w $f() {
+@start.1
+@body.2
+	%.1 =w loadw $c
+	%.2 =w add %.1, 1
+	storew %.2, $c
+	ret 3
+}
+export
+function w $g(w %.1, ...) {
+@start.3
+	%.2 =l alloc4 4
+	storew %.1, %.2
+	%.3 =l alloc8 24
+	%.7 =l alloc8 8
+	%.9 =l alloc4 4
+@body.4
+	%.4 =w loadw %.2
+	%.5 =l extsw %.4
+	%.6 =l mul %.5, 1
+	%.8 =l extsw 0
+	storel %.8, %.7
+	storew 1, %.9
+	vastart %.3
+	%.10 =w loadw %.9
+	%.11 =w sub %.10, 1
+	storew %.11, %.9
+	%.12 =l loadl %.7
+	%.13 =l vaarg %.3
+	%.14 =w loadw %.9
+	ret %.14
+}
+export
+function w $main() {
+@start.5
+	%.1 =l alloc4 4
+	%.5 =l alloc8 8
+	%.14 =l alloc8 8
+	%.19 =l alloc4 4
+	%.24 =l alloc4 4
+	%.45 =l alloc8 8
+	%.65 =l alloc8 8
+	%.79 =l alloc8 8
+@body.6
+	storew 0, %.1
+	%.2 =w call $f()
+	%.3 =l extsw %.2
+	%.4 =l mul %.3, 4
+	%.6 =l extsw 0
+	storel %.6, %.5
+	%.7 =w loadw %.1
+	%.8 =w loadw $c
+	%.9 =w cnew %.8, 1
+	%.10 =w add %.7, %.9
+	storew %.10, %.1
+	%.11 =w loadw $c
+	%.12 =w add %.11, 1
+	storew %.12, $c
+	%.13 =l loadl %.5
+	%.15 =w loadw %.1
+	%.16 =w loadw $c
+	%.17 =w cnew %.16, 2
+	%.18 =w add %.15, %.17
+	storew %.18, %.1
+	%.20 =w loadw %.1
+	%.21 =w loadw $c
+	%.22 =w cnew %.21, 2
+	%.23 =w add %.20, %.22
+	storew %.23, %.1
+	%.25 =w loadw %.1
+	%.26 =w loadw $c
+	%.27 =w cnew %.26, 2
+	%.28 =w add %.25, %.27
+	storew %.28, %.1
+	%.29 =w loadw %.1
+	%.30 =l loadl %.5
+	%.31 =l extsw 0
+	%.32 =w cnel %.30, %.31
+	%.33 =w add %.29, %.32
+	storew %.33, %.1
+	%.34 =w loadw $c
+	%.35 =w add %.34, 1
+	storew %.35, $c
+	storel $a, %.5
+	%.36 =l alloc4 %.4
+	%.37 =w loadw %.1
+	%.38 =w loadw $c
+	%.39 =w cnew %.38, 3
+	%.40 =w add %.37, %.39
+	storew %.40, %.1
+	%.41 =w loadw %.1
+	%.42 =l loadl %.5
+	%.43 =w cnel %.42, $a
+	%.44 =w add %.41, %.43
+	storew %.44, %.1
+	%.46 =w loadw %.1
+	%.47 =w loadw $c
+	%.48 =w cnew %.47, 3
+	%.49 =w add %.46, %.48
+	storew %.49, %.1
+	%.50 =w loadw %.1
+	%.51 =l loadl %.5
+	%.52 =w cnel %.51, $a
+	%.53 =w add %.50, %.52
+	storew %.53, %.1
+	%.54 =w loadw $c
+	%.55 =w add %.54, 1
+	storew %.55, $c
+	%.56 =l loadl %.5
+	%.57 =l extsw 0
+	%.58 =w loadw %.1
+	%.59 =w loadw $c
+	%.60 =w cnew %.59, 4
+	%.61 =w add %.58, %.60
+	storew %.61, %.1
+	%.62 =w loadw $c
+	%.63 =w add %.62, 1
+	storew %.63, $c
+	%.64 =l loadl %.5
+	%.66 =l extsw 0
+	storel %.66, %.65
+	%.67 =l loadl %.65
+	%.68 =w loadw %.1
+	%.69 =w loadw $c
+	%.70 =w cnew %.69, 5
+	%.71 =w add %.68, %.70
+	storew %.71, %.1
+	%.72 =w loadw %.1
+	%.73 =l loadl %.5
+	%.74 =w call $g(w 3, ..., l %.73)
+	%.75 =w add %.72, %.74
+	storew %.75, %.1
+	%.76 =w loadw $c
+	%.77 =w add %.76, 1
+	storew %.77, $c
+	%.78 =l loadl %.5
+	%.80 =w loadw %.1
+	%.81 =w loadw $c
+	%.82 =w cnew %.81, 6
+	%.83 =w add %.80, %.82
+	storew %.83, %.1
+	%.84 =w loadw %.1
+	ret %.84
+}
diff --git a/test/vla-deref.c b/test/vla-deref.c
new file mode 100644
index 0000000..7a5cd20
--- /dev/null
+++ b/test/vla-deref.c
@@ -0,0 +1,4 @@
+int main(void) {
+	int l = 3;
+	char a[*&l];
+}
diff --git a/test/vla-deref.qbe b/test/vla-deref.qbe
new file mode 100644
index 0000000..f9da148
--- /dev/null
+++ b/test/vla-deref.qbe
@@ -0,0 +1,12 @@
+export
+function w $main() {
+@start.1
+	%.1 =l alloc4 4
+@body.2
+	storew 3, %.1
+	%.2 =w loadw %.1
+	%.3 =l extsw %.2
+	%.4 =l mul %.3, 1
+	%.5 =l alloc4 %.4
+	ret 0
+}
diff --git a/test/vla-nested.c b/test/vla-nested.c
new file mode 100644
index 0000000..176392e
--- /dev/null
+++ b/test/vla-nested.c
@@ -0,0 +1,13 @@
+int l;
+int f(int x) {
+	l += x;
+	return x;
+}
+int main(void) {
+	int r = 0;
+	int (*p[f(2)])[f(3)];
+	r += l != 5;
+	r += sizeof p != sizeof(int (*[2])[3]);
+	r += sizeof **p != sizeof(int[3]);
+	return r;
+}
diff --git a/test/vla-nested.qbe b/test/vla-nested.qbe
new file mode 100644
index 0000000..b01c24c
--- /dev/null
+++ b/test/vla-nested.qbe
@@ -0,0 +1,44 @@
+export
+function w $f(w %.1) {
+@start.1
+	%.2 =l alloc4 4
+	storew %.1, %.2
+@body.2
+	%.3 =w loadw $l
+	%.4 =w loadw %.2
+	%.5 =w add %.3, %.4
+	storew %.5, $l
+	%.6 =w loadw %.2
+	ret %.6
+}
+export
+function w $main() {
+@start.3
+	%.1 =l alloc4 4
+@body.4
+	storew 0, %.1
+	%.2 =w call $f(w 3)
+	%.3 =l extsw %.2
+	%.4 =l mul %.3, 4
+	%.5 =w call $f(w 2)
+	%.6 =l extsw %.5
+	%.7 =l mul %.6, 8
+	%.8 =l alloc8 %.7
+	%.9 =w loadw %.1
+	%.10 =w loadw $l
+	%.11 =w cnew %.10, 5
+	%.12 =w add %.9, %.11
+	storew %.12, %.1
+	%.13 =w loadw %.1
+	%.14 =w cnel %.7, 16
+	%.15 =w add %.13, %.14
+	storew %.15, %.1
+	%.16 =w loadw %.1
+	%.17 =l loadl %.8
+	%.18 =w cnel %.4, 12
+	%.19 =w add %.16, %.18
+	storew %.19, %.1
+	%.20 =w loadw %.1
+	ret %.20
+}
+export data $l = align 4 { z 4 }
diff --git a/test/vla.c b/test/vla.c
new file mode 100644
index 0000000..61f3dcf
--- /dev/null
+++ b/test/vla.c
@@ -0,0 +1,5 @@
+short g() { return 1; }
+long f(void) {
+    double a[10 + g()];
+    return sizeof(a);
+}
diff --git a/test/vla.qbe b/test/vla.qbe
new file mode 100644
index 0000000..6c4f6bc
--- /dev/null
+++ b/test/vla.qbe
@@ -0,0 +1,18 @@
+export
+function w $g() {
+@start.1
+@body.2
+	ret 1
+}
+export
+function l $f() {
+@start.3
+@body.4
+	%.1 =w call $g()
+	%.2 =w extsh %.1
+	%.3 =w add 10, %.2
+	%.4 =l extsw %.3
+	%.5 =l mul %.4, 8
+	%.6 =l alloc8 %.5
+	ret %.5
+}