9.80/3.81 YES 9.80/3.82 proof of /export/starexec/sandbox/benchmark/theBenchmark.c 9.80/3.82 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 9.80/3.82 9.80/3.82 9.80/3.82 Termination of the given C Problem could be proven: 9.80/3.82 9.80/3.82 (0) C Problem 9.80/3.82 (1) CToLLVMProof [EQUIVALENT, 169 ms] 9.80/3.82 (2) LLVM problem 9.80/3.82 (3) LLVMToTerminationGraphProof [EQUIVALENT, 2081 ms] 9.80/3.82 (4) LLVM Symbolic Execution Graph 9.80/3.82 (5) SymbolicExecutionGraphToLassoProof [EQUIVALENT, 0 ms] 9.80/3.82 (6) TRUE 9.80/3.82 9.80/3.82 9.80/3.82 ---------------------------------------- 9.80/3.82 9.80/3.82 (0) 9.80/3.82 Obligation: 9.80/3.82 c file /export/starexec/sandbox/benchmark/theBenchmark.c 9.80/3.82 ---------------------------------------- 9.80/3.82 9.80/3.82 (1) CToLLVMProof (EQUIVALENT) 9.80/3.82 Compiled c-file /export/starexec/sandbox/benchmark/theBenchmark.c to LLVM. 9.80/3.82 ---------------------------------------- 9.80/3.82 9.80/3.82 (2) 9.80/3.82 Obligation: 9.80/3.82 LLVM Problem 9.80/3.82 9.80/3.82 Aliases: 9.80/3.82 9.80/3.82 Data layout: 9.80/3.82 9.80/3.82 "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" 9.80/3.82 9.80/3.82 Machine: 9.80/3.82 9.80/3.82 "x86_64-pc-linux-gnu" 9.80/3.82 9.80/3.82 Type definitions: 9.80/3.82 9.80/3.82 Global variables: 9.80/3.82 9.80/3.82 Function declarations and definitions: 9.80/3.82 9.80/3.82 *BasicFunctionTypename: "__VERIFIER_nondet_int" returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 9.80/3.82 *BasicFunctionTypename: "f" linkageType: EXTERNALLY_VISIBLE returnParam: BasicVoidType parameters: (d i32) variableLength: false visibilityType: DEFAULT callingConvention: ccc 9.80/3.82 0: 9.80/3.82 %1 = alloca i32, align 4 9.80/3.82 %d_ref = alloca *i32, align 8 9.80/3.82 %x = alloca *i32, align 8 9.80/3.82 %y = alloca *i32, align 8 9.80/3.82 %k = alloca *i32, align 8 9.80/3.82 %z = alloca *i32, align 8 9.80/3.82 store %d, %1 9.80/3.82 %2 = alloca i8, numElementsLit: 4 9.80/3.82 %3 = bitcast *i8 %2 to *i32 9.80/3.82 store %3, %d_ref 9.80/3.82 %4 = alloca i8, numElementsLit: 4 9.80/3.82 %5 = bitcast *i8 %4 to *i32 9.80/3.82 store %5, %x 9.80/3.82 %6 = alloca i8, numElementsLit: 4 9.80/3.82 %7 = bitcast *i8 %6 to *i32 9.80/3.82 store %7, %y 9.80/3.82 %8 = alloca i8, numElementsLit: 4 9.80/3.82 %9 = bitcast *i8 %8 to *i32 9.80/3.82 store %9, %k 9.80/3.82 %10 = alloca i8, numElementsLit: 4 9.80/3.82 %11 = bitcast *i8 %10 to *i32 9.80/3.82 store %11, %z 9.80/3.82 %12 = load %1 9.80/3.82 %13 = load %d_ref 9.80/3.82 store %12, %13 9.80/3.82 %14 = load %x 9.80/3.82 store 1, %14 9.80/3.82 %15 = load %y 9.80/3.82 store 1, %15 9.80/3.82 %16 = load %k 9.80/3.82 store 1, %16 9.80/3.82 %17 = load %z 9.80/3.82 store 1, %17 9.80/3.82 %18 = load %k 9.80/3.82 %19 = load %18 9.80/3.82 %20 = icmp sgt %19 1073741823 9.80/3.82 br %20, %21, %22 9.80/3.82 21: 9.80/3.82 br %72 9.80/3.82 22: 9.80/3.82 br %23 9.80/3.82 23: 9.80/3.82 br %24 9.80/3.82 24: 9.80/3.82 %25 = load %z 9.80/3.82 %26 = load %25 9.80/3.82 %27 = load %k 9.80/3.82 %28 = load %27 9.80/3.82 %29 = icmp slt %26 %28 9.80/3.82 br %29, %30, %35 9.80/3.82 30: 9.80/3.82 %31 = load %z 9.80/3.82 %32 = load %31 9.80/3.82 %33 = mul 2 %32 9.80/3.82 %34 = load %z 9.80/3.82 store %33, %34 9.80/3.82 br %24 9.80/3.82 35: 9.80/3.82 br %36 9.80/3.82 36: 9.80/3.82 br %37 9.80/3.82 37: 9.80/3.82 %38 = load %x 9.80/3.82 %39 = load %38 9.80/3.82 %40 = icmp sgt %39 0 9.80/3.82 br %40, %41, %45 9.80/3.82 41: 9.80/3.82 %42 = load %y 9.80/3.82 %43 = load %42 9.80/3.82 %44 = icmp sgt %43 0 9.80/3.82 br %45 9.80/3.82 45: 9.80/3.82 %46 = phi [0, %37], [%44, %41] 9.80/3.82 br %46, %47, %72 9.80/3.82 47: 9.80/3.82 %48 = call i32 @__VERIFIER_nondet_int() 9.80/3.82 %49 = icmp ne %48 0 9.80/3.82 br %49, %50, %64 9.80/3.82 50: 9.80/3.82 br %51 9.80/3.82 51: 9.80/3.82 %52 = load %x 9.80/3.82 %53 = load %52 9.80/3.82 %54 = load %d_ref 9.80/3.82 %55 = load %54 9.80/3.82 %56 = sub %53 %55 9.80/3.82 %57 = load %x 9.80/3.82 store %56, %57 9.80/3.82 %58 = call i32 @__VERIFIER_nondet_int() 9.80/3.82 %59 = load %y 9.80/3.82 store %58, %59 9.80/3.82 %60 = load %z 9.80/3.82 %61 = load %60 9.80/3.82 %62 = sub %61 1 9.80/3.82 %63 = load %z 9.80/3.82 store %62, %63 9.80/3.82 br %71 9.80/3.82 64: 9.80/3.82 %65 = load %y 9.80/3.82 %66 = load %65 9.80/3.82 %67 = load %d_ref 9.80/3.82 %68 = load %67 9.80/3.82 %69 = sub %66 %68 9.80/3.82 %70 = load %y 9.80/3.82 store %69, %70 9.80/3.82 br %71 9.80/3.82 71: 9.80/3.82 br %37 9.80/3.82 72: 9.80/3.82 ret void 9.80/3.82 9.80/3.82 *BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 9.80/3.82 0: 9.80/3.82 %1 = alloca i32, align 4 9.80/3.82 store 0, %1 9.80/3.82 %2 = call i32 @__VERIFIER_nondet_int() 9.80/3.82 %3 = icmp ne %2 0 9.80/3.82 br %3, %4, %5 9.80/3.82 4: 9.80/3.82 Unnamed Call-Instruction = call BasicVoidType @f(i32 1) 9.80/3.82 br %6 9.80/3.82 5: 9.80/3.82 Unnamed Call-Instruction = call BasicVoidType @f(i32 2) 9.80/3.82 br %6 9.80/3.82 6: 9.80/3.82 %7 = load %1 9.80/3.82 ret %7 9.80/3.82 9.80/3.82 9.80/3.82 Analyze Termination of all function calls matching the pattern: 9.80/3.82 main() 9.80/3.82 ---------------------------------------- 9.80/3.82 9.80/3.82 (3) LLVMToTerminationGraphProof (EQUIVALENT) 9.80/3.82 Constructed symbolic execution graph for LLVM program and proved memory safety. 9.80/3.82 ---------------------------------------- 9.80/3.82 9.80/3.82 (4) 9.80/3.82 Obligation: 9.80/3.82 SE Graph 9.80/3.82 ---------------------------------------- 9.80/3.82 9.80/3.82 (5) SymbolicExecutionGraphToLassoProof (EQUIVALENT) 9.80/3.82 Converted SEGraph to 0 independent lassos. 9.80/3.82 ---------------------------------------- 9.80/3.82 9.80/3.82 (6) 9.80/3.82 TRUE 9.97/3.87 EOF