@divFloor returns incorrect value

[brhamon]

I'm using zig version 0.3.0+d494a5f4. I'm really impressed with the compiler and the language, but I believe I have found a problem in @divFloor. The following test code should illustrate.

It appears that @divFloor will return the incorrect value for the case shown, using i32 integers on Windows 10 (Build 17134).

const std = @import("std");
const T = std.testing;

const ModResult = struct {
    quotient: i32,
    modulus: i32,
};

fn modulus(dividend: i32, divisor: i32) ModResult {
    return ModResult{
        .quotient = @divFloor(dividend, divisor),
        .modulus = @mod(dividend, divisor),
    };
}

test "modulus oops" {
    var mod = modulus(10, 12);
    T.expectEqual(i32(10), mod.modulus);
    T.expectEqual(i32(0), mod.quotient);
    mod = modulus(-14, 12);
    T.expectEqual(i32(10), mod.modulus);
    T.expectEqual(i32(-2), mod.quotient);
    mod = modulus(-2, 12);
    T.expectEqual(i32(10), mod.modulus);
    T.expectEqual(i32(-1), mod.quotient);
}

Here are my results:

$ zig version
0.3.0+d494a5f4

$ zig test src/mod.zig
Test 1/1 modulus oops...expected -1, found 0
C:\zig-windows-x86_64-0.3.0+d494a5f4\lib\zig\std\testing.zig:53:32: 0x7ff6f8571823 in std.testing.expectEqual (test.obj)
                std.debug.panic("expected {}, found {}", expected, actual);
                               ^
C:\code\zig\values\src\mod.zig:25:18: 0x7ff6f85715b9 in modulus oops (test.obj)
    T.expectEqual(i32(-1), mod.quotient);
                 ^
C:\zig-windows-x86_64-0.3.0+d494a5f4\lib\zig\std\special\test_runner.zig:13:25: 0x7ff6f8590674 in std.special.main (test.obj)
        if (test_fn.func()) |_| {
                        ^
C:\zig-windows-x86_64-0.3.0+d494a5f4\lib\zig\std\special\bootstrap.zig:51:40: 0x7ff6f859045a in ??? (test.obj)
    std.os.windows.ExitProcess(callMain());
                                       ^
???:?:?: 0x7ffc63593dc4 in ??? (???)


???:?:?: 0x7ffc64283691 in ??? (???)



Tests failed. Use the following command to reproduce the failure:
C:\code\zig\values\zig-cache\o\Bq0ttzIZqu8WBUw8Xq3iGVa4ALPsMfyKegio5jBSyovuFP9PfO8GzmVPmE0ng4BU\test.exe

The first five expectEqual statements passed, so the only issue appears to be with @divFloor when the numerator is in the range (-denominator, 0). I will pry into this with the debugger and see if I can find the root cause.

[andrewrk]

Thanks for the report.

I'll note that the zig compiler itself agrees with this bug report, because if you wrap the test in a comptime block, it passes:

const std = @import("std");
const T = std.testing;

const ModResult = struct {
    quotient: i32,
    modulus: i32,
};

fn modulus(dividend: i32, divisor: i32) ModResult {
    return ModResult{
        .quotient = @divFloor(dividend, divisor),
        .modulus = @mod(dividend, divisor),
    };
}

test "modulus oops" {
    comptime {
        var mod = modulus(10, 12);
        T.expectEqual(i32(10), mod.modulus);
        T.expectEqual(i32(0), mod.quotient);
        mod = modulus(-14, 12);
        T.expectEqual(i32(10), mod.modulus);
        T.expectEqual(i32(-2), mod.quotient);
        mod = modulus(-2, 12);
        T.expectEqual(i32(10), mod.modulus);
        T.expectEqual(i32(-1), mod.quotient);
    }
}

One way to debug this is to inspect the LLVM IR. To get small output we can simplify the input code:

export fn entry() void {
    var dividend: i32 = -2;
    var divisor: i32 = 12;
    var result = @divFloor(dividend, divisor);
}

const builtin = @import("builtin");
pub fn panic(msg: []const u8, error_return_trace: ?*builtin.StackTrace) noreturn {
    while (true) {}
}

and then build with ./zig build-obj test.zig --verbose-llvm-ir:

; ModuleID = 'test'
source_filename = "test"
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

%"[]u8" = type { i8*, i64 }
%builtin.StackTrace = type { i64, %"[]usize" }
%"[]usize" = type { i64*, i64 }

@0 = internal unnamed_addr constant [16 x i8] c"division by zero", align 1
@1 = internal unnamed_addr constant %"[]u8" { i8* getelementptr inbounds ([16 x i8], [16 x i8]* @0, i64 0, i64 0), i64 16 }, align 8
@2 = internal unnamed_addr constant [16 x i8] c"integer overflow", align 1
@3 = internal unnamed_addr constant %"[]u8" { i8* getelementptr inbounds ([16 x i8], [16 x i8]* @2, i64 0, i64 0), i64 16 }, align 8

; Function Attrs: nobuiltin noreturn nounwind
define internal fastcc void @panic(%"[]u8"* nonnull readonly align 8, %builtin.StackTrace* align 8) unnamed_addr #0 !dbg !8 {
Entry:
  %error_return_trace = alloca %builtin.StackTrace*, align 8
  call void @llvm.dbg.declare(metadata %"[]u8"* %0, metadata !33, metadata !DIExpression()), !dbg !36
  store %builtin.StackTrace* %1, %builtin.StackTrace** %error_return_trace, align 8
  call void @llvm.dbg.declare(metadata %builtin.StackTrace** %error_return_trace, metadata !34, metadata !DIExpression()), !dbg !37
  br label %WhileCond, !dbg !38

WhileCond:                                        ; preds = %WhileCond, %Entry
  br label %WhileCond, !dbg !38
}

; Function Attrs: nounwind readnone speculatable
declare void @llvm.dbg.declare(metadata, metadata, metadata) #1

; Function Attrs: nobuiltin nounwind
define void @entry() #2 !dbg !41 {
Entry:
  %dividend = alloca i32, align 4
  %divisor = alloca i32, align 4
  %result = alloca i32, align 4
  store i32 -2, i32* %dividend, align 4, !dbg !52
  call void @llvm.dbg.declare(metadata i32* %dividend, metadata !45, metadata !DIExpression()), !dbg !52
  store i32 12, i32* %divisor, align 4, !dbg !53
  call void @llvm.dbg.declare(metadata i32* %divisor, metadata !48, metadata !DIExpression()), !dbg !53
  %0 = load i32, i32* %dividend, align 4, !dbg !54
  %1 = load i32, i32* %divisor, align 4, !dbg !55
  %2 = icmp eq i32 %1, 0, !dbg !56
  br i1 %2, label %DivZeroFail, label %DivZeroOk, !dbg !56

DivZeroOk:                                        ; preds = %Entry
  %3 = icmp eq i32 %0, -2147483648, !dbg !56
  %4 = icmp eq i32 %1, -1, !dbg !56
  %5 = and i1 %3, %4, !dbg !56
  br i1 %5, label %DivOverflowFail, label %DivOverflowOk, !dbg !56

DivZeroFail:                                      ; preds = %Entry
  tail call fastcc void @panic(%"[]u8"* @1, %builtin.StackTrace* null), !dbg !56
  unreachable, !dbg !56

DivOverflowOk:                                    ; preds = %DivZeroOk
  %6 = sdiv i32 %0, %1, !dbg !56
  %7 = icmp sge i32 %6, 0, !dbg !56
  %8 = mul nsw i32 %6, %1, !dbg !56
  %9 = icmp eq i32 %8, %0, !dbg !56
  %10 = or i1 %9, %7, !dbg !56
  %11 = sub nsw i32 %6, 1, !dbg !56
  %12 = select i1 %10, i32 %6, i32 %11, !dbg !56
  store i32 %12, i32* %result, align 4, !dbg !57
  call void @llvm.dbg.declare(metadata i32* %result, metadata !50, metadata !DIExpression()), !dbg !57
  ret void, !dbg !58

DivOverflowFail:                                  ; preds = %DivZeroOk
  tail call fastcc void @panic(%"[]u8"* @3, %builtin.StackTrace* null), !dbg !56
  unreachable, !dbg !56
}

attributes #0 = { nobuiltin noreturn nounwind "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" }
attributes #1 = { nounwind readnone speculatable }
attributes #2 = { nobuiltin nounwind "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" }

!llvm.module.flags = !{!0}
!llvm.dbg.cu = !{!1}

!0 = !{i32 2, !"Debug Info Version", i32 3}
!1 = distinct !DICompileUnit(language: DW_LANG_C99, file: !2, producer: "zig 0.3.0", isOptimized: false, runtimeVersion: 0, emissionKind: FullDebug, enums: !3)
!2 = !DIFile(filename: "test", directory: ".")
!3 = !{!4}
!4 = !DICompositeType(tag: DW_TAG_enumeration_type, name: "anyerror", baseType: !5, size: 16, align: 16, elements: !6)
!5 = !DIBasicType(name: "u16", size: 16, encoding: DW_ATE_unsigned)
!6 = !{!7}
!7 = !DIEnumerator(name: "(none)", value: 0)
!8 = distinct !DISubprogram(name: "panic", scope: !9, file: !9, line: 8, type: !10, scopeLine: 8, flags: DIFlagStaticMember, spFlags: DISPFlagLocalToUnit | DISPFlagDefinition, unit: !1, retainedNodes: !32)
!9 = !DIFile(filename: "test.zig", directory: "/home/andy/downloads/zig/build")
!10 = !DISubroutineType(types: !11)
!11 = !{!12, !13, !21}
!12 = !DIBasicType(name: "void", encoding: DW_ATE_unsigned)
!13 = !DIDerivedType(tag: DW_TAG_pointer_type, name: "*[]const u8", baseType: !14, size: 64, align: 64)
!14 = !DICompositeType(tag: DW_TAG_structure_type, name: "[]u8", size: 128, align: 64, elements: !15)
!15 = !{!16, !19}
!16 = !DIDerivedType(tag: DW_TAG_member, name: "ptr", scope: !14, baseType: !17, size: 64, align: 64)
!17 = !DIDerivedType(tag: DW_TAG_pointer_type, name: "*u8", baseType: !18, size: 64, align: 64)
!18 = !DIBasicType(name: "u8", size: 8, encoding: DW_ATE_unsigned_char)
!19 = !DIDerivedType(tag: DW_TAG_member, name: "len", scope: !14, baseType: !20, size: 64, align: 64, offset: 64)
!20 = !DIBasicType(name: "usize", size: 64, encoding: DW_ATE_unsigned)
!21 = !DIDerivedType(tag: DW_TAG_pointer_type, name: "*builtin.StackTrace", baseType: !22, size: 64, align: 64)
!22 = !DICompositeType(tag: DW_TAG_structure_type, name: "builtin.StackTrace", scope: !23, file: !23, line: 1, size: 192, align: 192, elements: !24)
!23 = !DIFile(filename: "builtin.zig", directory: "/home/andy/.local/share/zig/stage1/builtin/0mPg7dcdbGiI_WeJIw9TIOJTbnKQ0RGGgw636R7ctlnPEIalCy2JiUnpeTCdjuP_")
!24 = !{!25, !26}
!25 = !DIDerivedType(tag: DW_TAG_member, name: "index", scope: !22, file: !23, line: 2, baseType: !20, size: 64, align: 64)
!26 = !DIDerivedType(tag: DW_TAG_member, name: "instruction_addresses", scope: !22, file: !23, line: 3, baseType: !27, size: 128, align: 128, offset: 64)
!27 = !DICompositeType(tag: DW_TAG_structure_type, name: "[]usize", size: 128, align: 64, elements: !28)
!28 = !{!29, !31}
!29 = !DIDerivedType(tag: DW_TAG_member, name: "ptr", scope: !27, baseType: !30, size: 64, align: 64)
!30 = !DIDerivedType(tag: DW_TAG_pointer_type, name: "*usize", baseType: !20, size: 64, align: 64)
!31 = !DIDerivedType(tag: DW_TAG_member, name: "len", scope: !27, baseType: !20, size: 64, align: 64, offset: 64)
!32 = !{!33, !34}
!33 = !DILocalVariable(name: "msg", arg: 1, scope: !8, file: !9, line: 8, type: !14)
!34 = !DILocalVariable(name: "error_return_trace", arg: 2, scope: !35, file: !9, line: 8, type: !21)
!35 = distinct !DILexicalBlock(scope: !8, file: !9, line: 8, column: 14)
!36 = !DILocation(line: 8, column: 14, scope: !8)
!37 = !DILocation(line: 8, column: 31, scope: !35)
!38 = !DILocation(line: 9, column: 5, scope: !39)
!39 = distinct !DILexicalBlock(scope: !40, file: !9, line: 8, column: 82)
!40 = distinct !DILexicalBlock(scope: !35, file: !9, line: 8, column: 31)
!41 = distinct !DISubprogram(name: "entry", scope: !9, file: !9, type: !42, flags: DIFlagStaticMember, spFlags: DISPFlagDefinition, unit: !1, retainedNodes: !44)
!42 = !DISubroutineType(types: !43)
!43 = !{!12}
!44 = !{!45, !48, !50}
!45 = !DILocalVariable(name: "dividend", scope: !46, file: !9, line: 2, type: !47)
!46 = distinct !DILexicalBlock(scope: !41, file: !9, line: 1, column: 24)
!47 = !DIBasicType(name: "i32", size: 32, encoding: DW_ATE_signed)
!48 = !DILocalVariable(name: "divisor", scope: !49, file: !9, line: 3, type: !47)
!49 = distinct !DILexicalBlock(scope: !46, file: !9, line: 2, column: 5)
!50 = !DILocalVariable(name: "result", scope: !51, file: !9, line: 4, type: !47)
!51 = distinct !DILexicalBlock(scope: !49, file: !9, line: 3, column: 5)
!52 = !DILocation(line: 2, column: 5, scope: !46)
!53 = !DILocation(line: 3, column: 5, scope: !49)
!54 = !DILocation(line: 4, column: 28, scope: !51)
!55 = !DILocation(line: 4, column: 38, scope: !51)
!56 = !DILocation(line: 4, column: 18, scope: !51)
!57 = !DILocation(line: 4, column: 5, scope: !51)
!58 = !DILocation(line: 1, column: 24, scope: !41)

The language reference is here: http://llvm.org/docs/LangRef.html

This code is generated here:

zig/src/codegen.cpp

Lines 2564 to 2582 in aa794eb

	{
	if (!type_entry->data.integral.is_signed) {
	return LLVMBuildUDiv(g->builder, val1, val2, "");
	}
	// const result = @divTrunc(a, b);
	// if (result >= 0 or result * b == a)
	// return result;
	// else
	// return result - 1;
	LLVMValueRef result = LLVMBuildSDiv(g->builder, val1, val2, "");
	LLVMValueRef is_pos = LLVMBuildICmp(g->builder, LLVMIntSGE, result, zero, "");
	LLVMValueRef orig_num = LLVMBuildNSWMul(g->builder, result, val2, "");
	LLVMValueRef orig_ok = LLVMBuildICmp(g->builder, LLVMIntEQ, orig_num, val1, "");
	LLVMValueRef ok_bit = LLVMBuildOr(g->builder, orig_ok, is_pos, "");
	LLVMValueRef one = LLVMConstInt(type_entry->type_ref, 1, true);
	LLVMValueRef result_minus_1 = LLVMBuildNSWSub(g->builder, result, one, "");
	return LLVMBuildSelect(g->builder, ok_bit, result, result_minus_1, "");
	}

[brhamon]

I wish I could read LLVM (I will follow the links and try to get up to speed); however, I can see a problem in the algorithm, expressed in the commented zig code in lines 2568-2572.

I had some code (written in C) to do this, so I ported it. One of the objectives I had when I wrote the original C was to avoid repeating the "expensive" IDIV operations, so that is why I wanted a function to return both.

Also, I needed to handle cases where the denominator is negative also; and it appears to be a non-requirement for @divFloor @divTrunc @mod and @rem; so the end result could end up being much simpler.

const std = @import("std");
const T = std.testing;

const ModResult = struct {
    quotient: i32,
    modulus: i32,
};

pub fn signFlag(val: i32) u1 {
    if (val < 0) {
        return 1;
    } else {
        return 0;
    }
}

pub fn abs(val: i32) i32 {
    if (val < 0) {
        return -val;
    } else {
        return val;
    }
}

fn modulus(dividend: i32, divisor: i32) ModResult {
    const s_divisor = signFlag(divisor);
    const abs_divisor = abs(divisor);
    var m: i32 = @rem(abs(dividend), abs_divisor);
    var d = dividend;
    if (m != 0 and signFlag(dividend) ^ s_divisor != 0) {
        d -= divisor;
        m = abs_divisor - m;
    }
    return ModResult{
        .quotient = @divTrunc(d, divisor),
        .modulus = switch (s_divisor) { 1 => -m, 0 => m },
    };
}

test "modulus oops" {
    var mod = modulus(10, 12);
    T.expectEqual(i32(10), mod.modulus);
    T.expectEqual(i32(0), mod.quotient);
    mod = modulus(-14, 12);
    T.expectEqual(i32(10), mod.modulus);
    T.expectEqual(i32(-2), mod.quotient);
    mod = modulus(-2, 12);
    T.expectEqual(i32(10), mod.modulus);
    T.expectEqual(i32(-1), mod.quotient);
}

and my results:

$ zig test src/mod.zig
Test 1/1 modulus oops...OK
All tests passed.

[andrewrk]

, I needed to handle cases where the denominator is negative also; and it appears to be a non-requirement for @divFloor @divTrunc @mod and @rem;

Note that @mod and @rem disallow 0 and negative denominators, however @divFloor and @divTrunc do allow negative denominators.

One of the objectives I had when I wrote the original C was to avoid repeating the "expensive" IDIV operations, so that is why I wanted a function to return both.

Last time I looked into this, the optimizer was able to turn separate division and modulus operations into a single hardware instruction. I haven't tried for @divFloor and @mod yet, however.

Thank you for the fixed logic. Were you intending to open a pull request, or is it ok if I push a fix with the new logic? By the way, do any of those operations depend on twos complement wraparound?

[brhamon]

Is the @mod and @rem restriction against negative denominators a platform-specific restriction? I ask because I'm using them in this way now, and my tests are passing on x86_64.

Optimizers are magic to mere mortals like myself, but I have seen them collapse the two IDIV operations in my code down to one, so I believe you!

I haven't attempted to make an actual LLVM code fix yet, but I am planning to do so.

In the meantime, I just pushed my Gregorian date code to github.com/brhamon/zigdate. I used my modulus code for now, and added a more thorough (although not exhaustive) test. I plan to add more features soon, and make it a module... as soon as I can figure out how to do that. This is primarily a learning exercise for me.

Thanks for the amazing work so far. I think you're really onto something with this zig thing.

[andrewrk]

Is the @mod and @rem restriction against negative denominators a platform-specific restriction?

I'm not sure I understand your question. The reasoning behind disallowing negative denominators in the Zig language is that there's not really a good use case for having them, and there's not really a good mathematical definition of what should happen. So by restricting the allowed input, we can have better code generated and catch more bugs.

[brhamon]

in github.com/brhamon/zigdate, I've generalized and added test cases for truncatedDiv, flooredDiv and euclideanDiv; and have unit tests for all three. I plan to use generics to use this implementation to handle all bit widths of signed integers. (For unsigned bit width integers, all three types of division operate exactly as truncatedDiv.) I'll make that change shortly.

In that code, I ran into an issue with inline for in which zig produced a segfault. I may open another issue for that; although I'm still not certain it's a compiler bug. It could be operator error.

[brhamon]

I agree, it's probably a math library feature, not a compiler feature, to deliver @mod and @Rem which support negative divisors.

[andrewrk]

If zig segfaults, it's always a compiler bug.