stage2: implement runtime array multiplication

Additionally:

 * Sema: fix array cat/mul not setting the sentinel value
   - This required an LLVM backend enhancement to the handling of the
     AIR instruction aggregate_init that likely needs to be
     propagated to the other backends.
 * Sema: report integer overflow of array concatenation in a proper
   compile error instead of crashing.
 * Sema: fix not using proper pointer address space for array cat/mul

1 files changed, 126 insertions, 72 deletions

diff --git a/src/Sema.zig b/src/Sema.zig
index 648174dcd1..38886cc78f 100644
--- a/src/Sema.zig
+++ b/src/Sema.zig
@@ -9264,10 +9264,8 @@ fn zirArrayCat(sema: *Sema, block: *Block, inst: Zir.Inst.Index) CompileError!Ai
     const lhs_src: LazySrcLoc = .{ .node_offset_bin_lhs = inst_data.src_node };
     const rhs_src: LazySrcLoc = .{ .node_offset_bin_rhs = inst_data.src_node };
 
-    const lhs_info = (try sema.getArrayCatInfo(block, lhs_src, lhs)) orelse
-        return sema.fail(block, lhs_src, "expected array, found '{}'", .{lhs_ty.fmt(sema.mod)});
-    const rhs_info = (try sema.getArrayCatInfo(block, rhs_src, rhs)) orelse
-        return sema.fail(block, rhs_src, "expected array, found '{}'", .{rhs_ty.fmt(sema.mod)});
+    const lhs_info = try sema.getArrayCatInfo(block, lhs_src, lhs);
+    const rhs_info = try sema.getArrayCatInfo(block, rhs_src, rhs);
 
     const resolved_elem_ty = t: {
         var trash_block = block.makeSubBlock();
@@ -9319,9 +9317,21 @@ fn zirArrayCat(sema: *Sema, block: *Block, inst: Zir.Inst.Index) CompileError!Ai
 
     const lhs_len = try sema.usizeCast(block, lhs_src, lhs_info.len);
     const rhs_len = try sema.usizeCast(block, lhs_src, rhs_info.len);
-    const result_len = lhs_len + rhs_len;
+    const result_len = std.math.add(usize, lhs_len, rhs_len) catch |err| switch (err) {
+        error.Overflow => return sema.fail(
+            block,
+            src,
+            "concatenating arrays of length {d} and {d} produces an array too large for this compiler implementation to handle",
+            .{ lhs_len, rhs_len },
+        ),
+    };
+
     const result_ty = try Type.array(sema.arena, result_len, res_sent_val, resolved_elem_ty, sema.mod);
-    const is_ref = lhs_ty.zigTypeTag() == .Pointer or rhs_ty.zigTypeTag() == .Pointer;
+    const ptr_addrspace = p: {
+        if (lhs_ty.zigTypeTag() == .Pointer) break :p lhs_ty.ptrAddressSpace();
+        if (rhs_ty.zigTypeTag() == .Pointer) break :p rhs_ty.ptrAddressSpace();
+        break :p null;
+    };
 
     const runtime_src = if (try sema.resolveDefinedValue(block, lhs_src, lhs)) |lhs_val| rs: {
         if (try sema.resolveDefinedValue(block, rhs_src, rhs)) |rhs_val| {
@@ -9348,22 +9358,21 @@ fn zirArrayCat(sema: *Sema, block: *Block, inst: Zir.Inst.Index) CompileError!Ai
                 element_vals[result_len] = sent_val;
             }
             const val = try Value.Tag.aggregate.create(sema.arena, element_vals);
-            return sema.addConstantMaybeRef(block, src, result_ty, val, is_ref);
+            return sema.addConstantMaybeRef(block, src, result_ty, val, ptr_addrspace != null);
         } else break :rs rhs_src;
     } else lhs_src;
 
     try sema.requireRuntimeBlock(block, runtime_src);
 
-    if (is_ref) {
-        const target = sema.mod.getTarget();
+    if (ptr_addrspace) |ptr_as| {
         const alloc_ty = try Type.ptr(sema.arena, sema.mod, .{
             .pointee_type = result_ty,
-            .@"addrspace" = target_util.defaultAddressSpace(target, .local),
+            .@"addrspace" = ptr_as,
         });
         const alloc = try block.addTy(.alloc, alloc_ty);
         const elem_ptr_ty = try Type.ptr(sema.arena, sema.mod, .{
             .pointee_type = resolved_elem_ty,
-            .@"addrspace" = target_util.defaultAddressSpace(target, .local),
+            .@"addrspace" = ptr_as,
         });
 
         var elem_i: usize = 0;
@@ -9380,6 +9389,12 @@ fn zirArrayCat(sema: *Sema, block: *Block, inst: Zir.Inst.Index) CompileError!Ai
             const init = try sema.elemVal(block, rhs_src, rhs, rhs_index, src);
             try sema.storePtr2(block, src, elem_ptr, src, init, rhs_src, .store);
         }
+        if (res_sent_val) |sent_val| {
+            const elem_index = try sema.addIntUnsigned(Type.usize, result_len);
+            const elem_ptr = try block.addPtrElemPtr(alloc, elem_index, elem_ptr_ty);
+            const init = try sema.addConstant(lhs_info.elem_type, sent_val);
+            try sema.storePtr2(block, src, elem_ptr, src, init, lhs_src, .store);
+        }
 
         return alloc;
     }
@@ -9402,30 +9417,35 @@ fn zirArrayCat(sema: *Sema, block: *Block, inst: Zir.Inst.Index) CompileError!Ai
     return block.addAggregateInit(result_ty, element_refs);
 }
 
-fn getArrayCatInfo(sema: *Sema, block: *Block, src: LazySrcLoc, inst: Air.Inst.Ref) !?Type.ArrayInfo {
-    const t = sema.typeOf(inst);
-    return switch (t.zigTypeTag()) {
-        .Array => t.arrayInfo(),
-        .Pointer => blk: {
-            const ptrinfo = t.ptrInfo().data;
-            switch (ptrinfo.size) {
+fn getArrayCatInfo(sema: *Sema, block: *Block, src: LazySrcLoc, operand: Air.Inst.Ref) !Type.ArrayInfo {
+    const operand_ty = sema.typeOf(operand);
+    switch (operand_ty.zigTypeTag()) {
+        .Array => return operand_ty.arrayInfo(),
+        .Pointer => {
+            const ptr_info = operand_ty.ptrInfo().data;
+            switch (ptr_info.size) {
+                // TODO: in the Many case here this should only work if the type
+                // has a sentinel, and this code should compute the length based
+                // on the sentinel value.
                 .Slice, .Many => {
-                    const val = try sema.resolveConstValue(block, src, inst);
+                    const val = try sema.resolveConstValue(block, src, operand);
                     return Type.ArrayInfo{
-                        .elem_type = t.childType(),
-                        .sentinel = t.sentinel(),
+                        .elem_type = ptr_info.pointee_type,
+                        .sentinel = ptr_info.sentinel,
                         .len = val.sliceLen(sema.mod),
                     };
                 },
                 .One => {
-                    if (ptrinfo.pointee_type.zigTypeTag() != .Array) return null;
-                    break :blk ptrinfo.pointee_type.arrayInfo();
+                    if (ptr_info.pointee_type.zigTypeTag() == .Array) {
+                        return ptr_info.pointee_type.arrayInfo();
+                    }
                 },
-                .C => return null,
+                .C => {},
             }
         },
-        else => null,
-    };
+        else => {},
+    }
+    return sema.fail(block, src, "expected indexable; found '{}'", .{operand_ty.fmt(sema.mod)});
 }
 
 fn analyzeTupleMul(
@@ -9514,65 +9534,99 @@ fn zirArrayMul(sema: *Sema, block: *Block, inst: Zir.Inst.Index) CompileError!Ai
         return sema.analyzeTupleMul(block, inst_data.src_node, lhs, factor);
     }
 
-    const mulinfo = (try sema.getArrayCatInfo(block, lhs_src, lhs)) orelse
-        return sema.fail(block, lhs_src, "expected array, found '{}'", .{lhs_ty.fmt(sema.mod)});
+    const lhs_info = try sema.getArrayCatInfo(block, lhs_src, lhs);
 
-    const final_len_u64 = std.math.mul(u64, mulinfo.len, factor) catch
+    const result_len_u64 = std.math.mul(u64, lhs_info.len, factor) catch
         return sema.fail(block, rhs_src, "operation results in overflow", .{});
+    const result_len = try sema.usizeCast(block, src, result_len_u64);
 
-    if (try sema.resolveDefinedValue(block, lhs_src, lhs)) |lhs_val| {
-        const final_len = try sema.usizeCast(block, src, final_len_u64);
-        const final_len_including_sent = final_len + @boolToInt(mulinfo.sentinel != null);
-        const lhs_len = try sema.usizeCast(block, lhs_src, mulinfo.len);
+    const result_ty = try Type.array(sema.arena, result_len, lhs_info.sentinel, lhs_info.elem_type, sema.mod);
 
-        const is_single_ptr = lhs_ty.zigTypeTag() == .Pointer and !lhs_ty.isSlice();
-        const lhs_sub_val = if (is_single_ptr) (try sema.pointerDeref(block, lhs_src, lhs_val, lhs_ty)).? else lhs_val;
+    const ptr_addrspace = if (lhs_ty.zigTypeTag() == .Pointer) lhs_ty.ptrAddressSpace() else null;
+    const lhs_len = try sema.usizeCast(block, lhs_src, lhs_info.len);
 
-        var anon_decl = try block.startAnonDecl(src);
-        defer anon_decl.deinit();
+    if (try sema.resolveDefinedValue(block, lhs_src, lhs)) |lhs_val| {
+        const final_len_including_sent = result_len + @boolToInt(lhs_info.sentinel != null);
 
-        const final_ty = if (mulinfo.sentinel) |sent|
-            try Type.Tag.array_sentinel.create(anon_decl.arena(), .{
-                .len = final_len,
-                .elem_type = try mulinfo.elem_type.copy(anon_decl.arena()),
-                .sentinel = try sent.copy(anon_decl.arena()),
-            })
+        const lhs_sub_val = if (lhs_ty.isSinglePointer())
+            (try sema.pointerDeref(block, lhs_src, lhs_val, lhs_ty)).?
         else
-            try Type.Tag.array.create(anon_decl.arena(), .{
-                .len = final_len,
-                .elem_type = try mulinfo.elem_type.copy(anon_decl.arena()),
-            });
-        const buf = try anon_decl.arena().alloc(Value, final_len_including_sent);
-
-        // Optimization for the common pattern of a single element repeated N times, such
-        // as zero-filling a byte array.
-        const val = if (lhs_len == 1) blk: {
-            const elem_val = try lhs_sub_val.elemValue(sema.mod, sema.arena, 0);
-            const copied_val = try elem_val.copy(anon_decl.arena());
-            break :blk try Value.Tag.repeated.create(anon_decl.arena(), copied_val);
-        } else blk: {
-            // the actual loop
-            var i: usize = 0;
-            while (i < factor) : (i += 1) {
-                var j: usize = 0;
-                while (j < lhs_len) : (j += 1) {
-                    const val = try lhs_sub_val.elemValue(sema.mod, sema.arena, j);
-                    buf[lhs_len * i + j] = try val.copy(anon_decl.arena());
+            lhs_val;
+
+        const val = v: {
+            // Optimization for the common pattern of a single element repeated N times, such
+            // as zero-filling a byte array.
+            if (lhs_len == 1) {
+                const elem_val = try lhs_sub_val.elemValue(sema.mod, sema.arena, 0);
+                break :v try Value.Tag.repeated.create(sema.arena, elem_val);
+            }
+
+            const element_vals = try sema.arena.alloc(Value, final_len_including_sent);
+            var elem_i: usize = 0;
+            while (elem_i < result_len) {
+                var lhs_i: usize = 0;
+                while (lhs_i < lhs_len) : (lhs_i += 1) {
+                    const elem_val = try lhs_sub_val.elemValue(sema.mod, sema.arena, lhs_i);
+                    element_vals[elem_i] = elem_val;
+                    elem_i += 1;
                 }
             }
-            if (mulinfo.sentinel) |sent| {
-                buf[final_len] = try sent.copy(anon_decl.arena());
+            if (lhs_info.sentinel) |sent_val| {
+                element_vals[result_len] = sent_val;
             }
-            break :blk try Value.Tag.aggregate.create(anon_decl.arena(), buf);
+            break :v try Value.Tag.aggregate.create(sema.arena, element_vals);
         };
-        const decl = try anon_decl.finish(final_ty, val, 0);
-        if (lhs_ty.zigTypeTag() == .Pointer) {
-            return sema.analyzeDeclRef(decl);
-        } else {
-            return sema.analyzeDeclVal(block, .unneeded, decl);
+        return sema.addConstantMaybeRef(block, src, result_ty, val, ptr_addrspace != null);
+    }
+
+    try sema.requireRuntimeBlock(block, lhs_src);
+
+    if (ptr_addrspace) |ptr_as| {
+        const alloc_ty = try Type.ptr(sema.arena, sema.mod, .{
+            .pointee_type = result_ty,
+            .@"addrspace" = ptr_as,
+        });
+        const alloc = try block.addTy(.alloc, alloc_ty);
+        const elem_ptr_ty = try Type.ptr(sema.arena, sema.mod, .{
+            .pointee_type = lhs_info.elem_type,
+            .@"addrspace" = ptr_as,
+        });
+
+        var elem_i: usize = 0;
+        while (elem_i < result_len) {
+            var lhs_i: usize = 0;
+            while (lhs_i < lhs_len) : (lhs_i += 1) {
+                const elem_index = try sema.addIntUnsigned(Type.usize, elem_i);
+                elem_i += 1;
+                const lhs_index = try sema.addIntUnsigned(Type.usize, lhs_i);
+                const elem_ptr = try block.addPtrElemPtr(alloc, elem_index, elem_ptr_ty);
+                const init = try sema.elemVal(block, lhs_src, lhs, lhs_index, src);
+                try sema.storePtr2(block, src, elem_ptr, src, init, lhs_src, .store);
+            }
+        }
+        if (lhs_info.sentinel) |sent_val| {
+            const elem_index = try sema.addIntUnsigned(Type.usize, result_len);
+            const elem_ptr = try block.addPtrElemPtr(alloc, elem_index, elem_ptr_ty);
+            const init = try sema.addConstant(lhs_info.elem_type, sent_val);
+            try sema.storePtr2(block, src, elem_ptr, src, init, lhs_src, .store);
+        }
+
+        return alloc;
+    }
+
+    const element_refs = try sema.arena.alloc(Air.Inst.Ref, result_len);
+    var elem_i: usize = 0;
+    while (elem_i < result_len) {
+        var lhs_i: usize = 0;
+        while (lhs_i < lhs_len) : (lhs_i += 1) {
+            const lhs_index = try sema.addIntUnsigned(Type.usize, lhs_i);
+            const init = try sema.elemVal(block, lhs_src, lhs, lhs_index, src);
+            element_refs[elem_i] = init;
+            elem_i += 1;
         }
     }
-    return sema.fail(block, lhs_src, "TODO runtime array_mul", .{});
+
+    return block.addAggregateInit(result_ty, element_refs);
 }
 
 fn zirNegate(sema: *Sema, block: *Block, inst: Zir.Inst.Index) CompileError!Air.Inst.Ref {