5.02/2.20 YES 5.02/2.21 proof of /export/starexec/sandbox/benchmark/theBenchmark.c 5.02/2.21 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.02/2.21 5.02/2.21 5.02/2.21 Termination of the given C Problem could be proven: 5.02/2.21 5.02/2.21 (0) C Problem 5.02/2.21 (1) CToLLVMProof [EQUIVALENT, 169 ms] 5.02/2.21 (2) LLVM problem 5.02/2.21 (3) LLVMToTerminationGraphProof [EQUIVALENT, 379 ms] 5.02/2.21 (4) LLVM Symbolic Execution Graph 5.02/2.21 (5) SymbolicExecutionGraphToLassoProof [EQUIVALENT, 3 ms] 5.02/2.21 (6) TRUE 5.02/2.21 5.02/2.21 5.02/2.21 ---------------------------------------- 5.02/2.21 5.02/2.21 (0) 5.02/2.21 Obligation: 5.02/2.21 c file /export/starexec/sandbox/benchmark/theBenchmark.c 5.02/2.21 ---------------------------------------- 5.02/2.21 5.02/2.21 (1) CToLLVMProof (EQUIVALENT) 5.02/2.21 Compiled c-file /export/starexec/sandbox/benchmark/theBenchmark.c to LLVM. 5.02/2.21 ---------------------------------------- 5.02/2.21 5.02/2.21 (2) 5.02/2.21 Obligation: 5.02/2.21 LLVM Problem 5.02/2.21 5.02/2.21 Aliases: 5.02/2.21 5.02/2.21 Data layout: 5.02/2.21 5.02/2.21 "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128" 5.02/2.21 5.02/2.21 Machine: 5.02/2.21 5.02/2.21 "x86_64-pc-linux-gnu" 5.02/2.21 5.02/2.21 Type definitions: 5.02/2.21 5.02/2.21 Global variables: 5.02/2.21 5.02/2.21 Function declarations and definitions: 5.02/2.21 5.02/2.21 *BasicFunctionTypename: "__VERIFIER_nondet_int" returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 5.02/2.21 *BasicFunctionTypename: "test_fun" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: (x i32, y i32) variableLength: false visibilityType: DEFAULT callingConvention: ccc 5.02/2.21 0: 5.02/2.21 %1 = alloca i32, align 4 5.02/2.21 %2 = alloca i32, align 4 5.02/2.21 %3 = alloca i32, align 4 5.02/2.21 %c = alloca i32, align 4 5.02/2.21 store %x, %2 5.02/2.21 store %y, %3 5.02/2.21 store 0, %c 5.02/2.21 %4 = load %2 5.02/2.21 %5 = icmp sle %4 0 5.02/2.21 br %5, %9, %6 5.02/2.21 6: 5.02/2.21 %7 = load %3 5.02/2.21 %8 = icmp sle %7 0 5.02/2.21 br %8, %9, %13 5.02/2.21 9: 5.02/2.21 %10 = load %2 5.02/2.21 %11 = load %3 5.02/2.21 %12 = add %10 %11 5.02/2.21 store %12, %1 5.02/2.21 br %37 5.02/2.21 13: 5.02/2.21 br %14 5.02/2.21 14: 5.02/2.21 %15 = load %2 5.02/2.21 %16 = icmp eq %15 0 5.02/2.21 %17 = xor %16 1 5.02/2.21 br %17, %18, %35 5.02/2.21 18: 5.02/2.21 %19 = load %2 5.02/2.21 %20 = load %3 5.02/2.21 %21 = icmp sgt %19 %20 5.02/2.21 br %21, %22, %24 5.02/2.21 22: 5.02/2.21 %23 = load %3 5.02/2.21 store %23, %2 5.02/2.21 br %32 5.02/2.21 24: 5.02/2.21 %25 = load %2 5.02/2.21 %26 = icmp sle %25 0 5.02/2.21 br %26, %27, %29 5.02/2.21 27: 5.02/2.21 %28 = load %2 5.02/2.21 store %28, %1 5.02/2.21 br %37 5.02/2.21 29: 5.02/2.21 %30 = load %2 5.02/2.21 %31 = sub %30 1 5.02/2.21 store %31, %2 5.02/2.21 br %32 5.02/2.21 32: 5.02/2.21 %33 = load %c 5.02/2.21 %34 = add %33 1 5.02/2.21 store %34, %c 5.02/2.21 br %14 5.02/2.21 35: 5.02/2.21 %36 = load %c 5.02/2.21 store %36, %1 5.02/2.21 br %37 5.02/2.21 37: 5.02/2.21 %38 = load %1 5.02/2.21 ret %38 5.02/2.21 5.02/2.21 *BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 5.02/2.21 0: 5.02/2.21 %1 = alloca i32, align 4 5.02/2.21 store 0, %1 5.02/2.21 %2 = call i32 @__VERIFIER_nondet_int() 5.02/2.21 %3 = call i32 @__VERIFIER_nondet_int() 5.02/2.21 %4 = call i32 @test_fun(i32 %2, i32 %3) 5.02/2.21 ret %4 5.02/2.21 5.02/2.21 5.02/2.21 Analyze Termination of all function calls matching the pattern: 5.02/2.21 main() 5.02/2.21 ---------------------------------------- 5.02/2.21 5.02/2.21 (3) LLVMToTerminationGraphProof (EQUIVALENT) 5.02/2.21 Constructed symbolic execution graph for LLVM program and proved memory safety. 5.02/2.21 ---------------------------------------- 5.02/2.21 5.02/2.21 (4) 5.02/2.21 Obligation: 5.02/2.21 SE Graph 5.02/2.21 ---------------------------------------- 5.02/2.21 5.02/2.21 (5) SymbolicExecutionGraphToLassoProof (EQUIVALENT) 5.02/2.21 Converted SEGraph to 0 independent lassos. 5.02/2.21 ---------------------------------------- 5.02/2.21 5.02/2.21 (6) 5.02/2.21 TRUE 5.25/2.25 EOF