stage2: more division support

AIR:
 * div is renamed to div_trunc.
 * Add div_float, div_floor, div_exact.
   - Implemented in Sema and LLVM codegen. C backend has a stub.

Improvements to std.math.big.Int:
 * Add `eqZero` function to `Mutable`.
 * Fix incorrect results for `divFloor`.

Compiler-rt:
 * Add muloti4 to the stage2 section.

5 files changed, 105 insertions, 8 deletions

diff --git a/src/codegen/c.zig b/src/codegen/c.zig
index 9050499fce..aa1ece7ba3 100644
--- a/src/codegen/c.zig
+++ b/src/codegen/c.zig
@@ -976,7 +976,8 @@ fn genBody(f: *Function, body: []const Air.Inst.Index) error{ AnalysisFail, OutO
             .mul           => try airBinOp (f, inst, " * "),
             // TODO use a different strategy for div that communicates to the optimizer
             // that wrapping is UB.
-            .div           => try airBinOp( f, inst, " / "),
+            .div_float, .div_exact, .div_trunc => try airBinOp( f, inst, " / "),
+            .div_floor                         => try airBinOp( f, inst, " divfloor "),
             .rem           => try airBinOp( f, inst, " % "),
             .mod           => try airBinOp( f, inst, " mod "), // TODO implement modulus division
 
diff --git a/src/codegen/llvm.zig b/src/codegen/llvm.zig
index a607b7a753..4fc4e866ba 100644
--- a/src/codegen/llvm.zig
+++ b/src/codegen/llvm.zig
@@ -1667,7 +1667,10 @@ pub const FuncGen = struct {
                 .mul       => try self.airMul(inst),
                 .mulwrap   => try self.airMulWrap(inst),
                 .mul_sat   => try self.airMulSat(inst),
-                .div       => try self.airDiv(inst),
+                .div_float => try self.airDivFloat(inst),
+                .div_trunc => try self.airDivTrunc(inst),
+                .div_floor => try self.airDivFloor(inst),
+                .div_exact => try self.airDivExact(inst),
                 .rem       => try self.airRem(inst),
                 .mod       => try self.airMod(inst),
                 .ptr_add   => try self.airPtrAdd(inst),
@@ -2830,20 +2833,81 @@ pub const FuncGen = struct {
         return self.builder.buildUMulFixSat(lhs, rhs, "");
     }
 
-    fn airDiv(self: *FuncGen, inst: Air.Inst.Index) !?*const llvm.Value {
-        if (self.liveness.isUnused(inst))
-            return null;
+    fn airDivFloat(self: *FuncGen, inst: Air.Inst.Index) !?*const llvm.Value {
+        if (self.liveness.isUnused(inst)) return null;
+
+        const bin_op = self.air.instructions.items(.data)[inst].bin_op;
+        const lhs = try self.resolveInst(bin_op.lhs);
+        const rhs = try self.resolveInst(bin_op.rhs);
+
+        return self.builder.buildFDiv(lhs, rhs, "");
+    }
+
+    fn airDivTrunc(self: *FuncGen, inst: Air.Inst.Index) !?*const llvm.Value {
+        if (self.liveness.isUnused(inst)) return null;
 
         const bin_op = self.air.instructions.items(.data)[inst].bin_op;
         const lhs = try self.resolveInst(bin_op.lhs);
         const rhs = try self.resolveInst(bin_op.rhs);
         const inst_ty = self.air.typeOfIndex(inst);
 
-        if (inst_ty.isRuntimeFloat()) return self.builder.buildFDiv(lhs, rhs, "");
+        if (inst_ty.isRuntimeFloat()) {
+            const result_llvm_ty = try self.dg.llvmType(inst_ty);
+            const zero = result_llvm_ty.constNull();
+            const result = self.builder.buildFDiv(lhs, rhs, "");
+            const ceiled = try self.callCeil(result, inst_ty);
+            const floored = try self.callFloor(result, inst_ty);
+            const ltz = self.builder.buildFCmp(.OLT, lhs, zero, "");
+            return self.builder.buildSelect(ltz, ceiled, floored, "");
+        }
         if (inst_ty.isSignedInt()) return self.builder.buildSDiv(lhs, rhs, "");
         return self.builder.buildUDiv(lhs, rhs, "");
     }
 
+    fn airDivFloor(self: *FuncGen, inst: Air.Inst.Index) !?*const llvm.Value {
+        if (self.liveness.isUnused(inst)) return null;
+
+        const bin_op = self.air.instructions.items(.data)[inst].bin_op;
+        const lhs = try self.resolveInst(bin_op.lhs);
+        const rhs = try self.resolveInst(bin_op.rhs);
+        const inst_ty = self.air.typeOfIndex(inst);
+
+        if (inst_ty.isRuntimeFloat()) {
+            const result = self.builder.buildFDiv(lhs, rhs, "");
+            return try self.callFloor(result, inst_ty);
+        }
+        if (inst_ty.isSignedInt()) {
+            // const d = @divTrunc(a, b);
+            // const r = @rem(a, b);
+            // return if (r == 0) d else d - ((a < 0) ^ (b < 0));
+            const result_llvm_ty = try self.dg.llvmType(inst_ty);
+            const zero = result_llvm_ty.constNull();
+            const div_trunc = self.builder.buildSDiv(lhs, rhs, "");
+            const rem = self.builder.buildSRem(lhs, rhs, "");
+            const rem_eq_0 = self.builder.buildICmp(.EQ, rem, zero, "");
+            const a_lt_0 = self.builder.buildICmp(.SLT, lhs, zero, "");
+            const b_lt_0 = self.builder.buildICmp(.SLT, rhs, zero, "");
+            const a_b_xor = self.builder.buildXor(a_lt_0, b_lt_0, "");
+            const a_b_xor_ext = self.builder.buildZExt(a_b_xor, div_trunc.typeOf(), "");
+            const d_sub_xor = self.builder.buildSub(div_trunc, a_b_xor_ext, "");
+            return self.builder.buildSelect(rem_eq_0, div_trunc, d_sub_xor, "");
+        }
+        return self.builder.buildUDiv(lhs, rhs, "");
+    }
+
+    fn airDivExact(self: *FuncGen, inst: Air.Inst.Index) !?*const llvm.Value {
+        if (self.liveness.isUnused(inst)) return null;
+
+        const bin_op = self.air.instructions.items(.data)[inst].bin_op;
+        const lhs = try self.resolveInst(bin_op.lhs);
+        const rhs = try self.resolveInst(bin_op.rhs);
+        const inst_ty = self.air.typeOfIndex(inst);
+
+        if (inst_ty.isRuntimeFloat()) return self.builder.buildFDiv(lhs, rhs, "");
+        if (inst_ty.isSignedInt()) return self.builder.buildExactSDiv(lhs, rhs, "");
+        return self.builder.buildExactUDiv(lhs, rhs, "");
+    }
+
     fn airRem(self: *FuncGen, inst: Air.Inst.Index) !?*const llvm.Value {
         if (self.liveness.isUnused(inst)) return null;
 
@@ -3546,6 +3610,33 @@ pub const FuncGen = struct {
         }
     }
 
+    fn callFloor(self: *FuncGen, arg: *const llvm.Value, ty: Type) !*const llvm.Value {
+        return self.callFloatUnary(arg, ty, "floor");
+    }
+
+    fn callCeil(self: *FuncGen, arg: *const llvm.Value, ty: Type) !*const llvm.Value {
+        return self.callFloatUnary(arg, ty, "ceil");
+    }
+
+    fn callFloatUnary(self: *FuncGen, arg: *const llvm.Value, ty: Type, name: []const u8) !*const llvm.Value {
+        const target = self.dg.module.getTarget();
+
+        var fn_name_buf: [100]u8 = undefined;
+        const llvm_fn_name = std.fmt.bufPrintZ(&fn_name_buf, "llvm.{s}.f{d}", .{
+            name, ty.floatBits(target),
+        }) catch unreachable;
+
+        const llvm_fn = self.dg.object.llvm_module.getNamedFunction(llvm_fn_name) orelse blk: {
+            const operand_llvm_ty = try self.dg.llvmType(ty);
+            const param_types = [_]*const llvm.Type{operand_llvm_ty};
+            const fn_type = llvm.functionType(operand_llvm_ty, &param_types, param_types.len, .False);
+            break :blk self.dg.object.llvm_module.addFunction(llvm_fn_name, fn_type);
+        };
+
+        const args: [1]*const llvm.Value = .{arg};
+        return self.builder.buildCall(llvm_fn, &args, args.len, .C, .Auto, "");
+    }
+
     fn fieldPtr(
         self: *FuncGen,
         inst: Air.Inst.Index,
diff --git a/src/codegen/llvm/bindings.zig b/src/codegen/llvm/bindings.zig
index 297450a032..9a62fa791f 100644
--- a/src/codegen/llvm/bindings.zig
+++ b/src/codegen/llvm/bindings.zig
@@ -756,6 +756,12 @@ pub const Builder = opaque {
 
     pub const buildSMin = ZigLLVMBuildSMin;
     extern fn ZigLLVMBuildSMin(builder: *const Builder, LHS: *const Value, RHS: *const Value, name: [*:0]const u8) *const Value;
+
+    pub const buildExactUDiv = LLVMBuildExactUDiv;
+    extern fn LLVMBuildExactUDiv(*const Builder, LHS: *const Value, RHS: *const Value, Name: [*:0]const u8) *const Value;
+
+    pub const buildExactSDiv = LLVMBuildExactSDiv;
+    extern fn LLVMBuildExactSDiv(*const Builder, LHS: *const Value, RHS: *const Value, Name: [*:0]const u8) *const Value;
 };
 
 pub const IntPredicate = enum(c_uint) {
diff --git a/src/codegen/spirv.zig b/src/codegen/spirv.zig
index 25a1d228e0..da2fa66fee 100644
--- a/src/codegen/spirv.zig
+++ b/src/codegen/spirv.zig
@@ -669,7 +669,6 @@ pub const DeclGen = struct {
             .add, .addwrap => try self.airArithOp(inst, .{.OpFAdd, .OpIAdd, .OpIAdd}),
             .sub, .subwrap => try self.airArithOp(inst, .{.OpFSub, .OpISub, .OpISub}),
             .mul, .mulwrap => try self.airArithOp(inst, .{.OpFMul, .OpIMul, .OpIMul}),
-            .div           => try self.airArithOp(inst, .{.OpFDiv, .OpSDiv, .OpUDiv}),
 
             .bit_and  => try self.airBinOpSimple(inst, .OpBitwiseAnd),
             .bit_or   => try self.airBinOpSimple(inst, .OpBitwiseOr),
diff --git a/src/codegen/wasm.zig b/src/codegen/wasm.zig
index f0d9e43439..75e6a1d78e 100644
--- a/src/codegen/wasm.zig
+++ b/src/codegen/wasm.zig
@@ -822,7 +822,7 @@ pub const Context = struct {
             .subwrap => self.airWrapBinOp(inst, .sub),
             .mul => self.airBinOp(inst, .mul),
             .mulwrap => self.airWrapBinOp(inst, .mul),
-            .div => self.airBinOp(inst, .div),
+            .div_trunc => self.airBinOp(inst, .div),
             .bit_and => self.airBinOp(inst, .@"and"),
             .bit_or => self.airBinOp(inst, .@"or"),
             .bool_and => self.airBinOp(inst, .@"and"),