GaloisInc / crucible

Crucible is a library for symbolic simulation of imperative programs
677 stars 44 forks source link

`crucible-llvm`: support translating `long double`/`x86_fp80` values #810

Open RyanGlScott opened 3 years ago

RyanGlScott commented 3 years ago

The following program:

long double f(long double x) {
  return x;
}

int main() {
  return f(0);
}

Will trip up crux-llvm:

$ crux-llvm test.c 
[Crux] Using pointer width: 64 for file crux-build/crux~test.bc
[Crux] Simulating function main
[Crux] Attempting to prove verification conditions.
[Crux] *** debug executable: results/test/debug-6
[Crux] *** break on line: 6
[Crux] Found counterexample for verification goal
[Crux]   test.c:6:10: error: in main
[Crux]   unsupported LLVM value: ValFP80 (FP80_LongDouble 0 0) of type long double
[Crux] Goal status:
[Crux]   Total: 1
[Crux]   Proved: 0
[Crux]   Disproved: 1
[Crux]   Incomplete: 0
[Crux]   Unknown: 0
[Crux] Overall status: Invalid.

This is the LLVM bitcode produced by Clang 10.0.0:

``` $ cat crux-build/crux~test.ll ; ModuleID = 'crux-build/crux~test.bc' source_filename = "llvm-link" target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128" target triple = "x86_64-pc-linux-gnu" ; Function Attrs: norecurse nounwind readnone uwtable define dso_local x86_fp80 @f(x86_fp80 returned %0) local_unnamed_addr #0 !dbg !7 { call void @llvm.dbg.value(metadata x86_fp80 %0, metadata !12, metadata !DIExpression()), !dbg !13 ret x86_fp80 %0, !dbg !14 } ; Function Attrs: nounwind readnone speculatable willreturn declare void @llvm.dbg.value(metadata, metadata, metadata) #1 ; Function Attrs: norecurse nounwind readnone uwtable define dso_local i32 @main() local_unnamed_addr #0 !dbg !15 { %1 = call x86_fp80 @f(x86_fp80 0xK00000000000000000000), !dbg !19 %2 = fptosi x86_fp80 %1 to i32, !dbg !19 ret i32 %2, !dbg !20 } attributes #0 = { norecurse nounwind readnone uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "frame-pointer"="none" "less-precise-fpmad"="false" "min-legal-vector-width"="0" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="x86-64" "target-features"="+cx8,+fxsr,+mmx,+sse,+sse2,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" } attributes #1 = { nounwind readnone speculatable willreturn } !llvm.dbg.cu = !{!0} !llvm.ident = !{!3} !llvm.module.flags = !{!4, !5, !6} !0 = distinct !DICompileUnit(language: DW_LANG_C99, file: !1, producer: "clang version 10.0.0-4ubuntu1 ", isOptimized: true, runtimeVersion: 0, emissionKind: FullDebug, enums: !2, splitDebugInlining: false, nameTableKind: None) !1 = !DIFile(filename: "test.c", directory: "/home/rscott/Documents/Hacking/Haskell/sandbox/crucible/crux-llvm") !2 = !{} !3 = !{!"clang version 10.0.0-4ubuntu1 "} !4 = !{i32 7, !"Dwarf Version", i32 4} !5 = !{i32 2, !"Debug Info Version", i32 3} !6 = !{i32 1, !"wchar_size", i32 4} !7 = distinct !DISubprogram(name: "f", scope: !1, file: !1, line: 1, type: !8, scopeLine: 1, flags: DIFlagPrototyped | DIFlagAllCallsDescribed, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !11) !8 = !DISubroutineType(types: !9) !9 = !{!10, !10} !10 = !DIBasicType(name: "long double", size: 128, encoding: DW_ATE_float) !11 = !{!12} !12 = !DILocalVariable(name: "x", arg: 1, scope: !7, file: !1, line: 1, type: !10) !13 = !DILocation(line: 0, scope: !7) !14 = !DILocation(line: 2, column: 3, scope: !7) !15 = distinct !DISubprogram(name: "main", scope: !1, file: !1, line: 5, type: !16, scopeLine: 5, flags: DIFlagAllCallsDescribed, spFlags: DISPFlagDefinition | DISPFlagOptimized, unit: !0, retainedNodes: !2) !16 = !DISubroutineType(types: !17) !17 = !{!18} !18 = !DIBasicType(name: "int", size: 32, encoding: DW_ATE_signed) !19 = !DILocation(line: 6, column: 10, scope: !15) !20 = !DILocation(line: 6, column: 3, scope: !15) ```

I originally discovered this by way of SV-COMP's floats-esbmc-regression/digits_for.c benchmark program.

robdockins commented 3 years ago

I think the main issue here is that 80-bit X86 floats don't quite correspond to any IEEE-754 floating-point type. The libBF library might still be able to faithfully represent them, but it would require some pretty careful management. For symbolic values, they would still work fine for the "real" and "uninterpreted" modes, but I don't know that we could reasonably connect them to a bit-precise solver mode. Maybe we could play some games and fit them into some carefully-chosen IEEE format, but I'm not sure.