19.47/5.81 NO 20.40/6.20 proof of /export/starexec/sandbox/benchmark/theBenchmark.c 20.40/6.20 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 20.40/6.20 20.40/6.20 20.40/6.20 Termination of the given C Problem could be disproven: 20.40/6.20 20.40/6.20 (0) C Problem 20.40/6.20 (1) CToLLVMProof [EQUIVALENT, 139 ms] 20.40/6.20 (2) LLVM problem 20.40/6.20 (3) LLVMToTerminationGraphProof [EQUIVALENT, 566 ms] 20.40/6.20 (4) LLVM Symbolic Execution Graph 20.40/6.20 (5) LLVMNonterminationProof [COMPLETE, 746 ms] 20.40/6.20 (6) NO 20.40/6.20 20.40/6.20 20.40/6.20 ---------------------------------------- 20.40/6.20 20.40/6.20 (0) 20.40/6.20 Obligation: 20.40/6.20 c file /export/starexec/sandbox/benchmark/theBenchmark.c 20.40/6.20 ---------------------------------------- 20.40/6.20 20.40/6.20 (1) CToLLVMProof (EQUIVALENT) 20.40/6.20 Compiled c-file /export/starexec/sandbox/benchmark/theBenchmark.c to LLVM. 20.40/6.20 ---------------------------------------- 20.40/6.20 20.40/6.20 (2) 20.40/6.20 Obligation: 20.40/6.20 LLVM Problem 20.40/6.20 20.40/6.20 Aliases: 20.40/6.20 20.40/6.20 Data layout: 20.40/6.20 20.40/6.20 "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" 20.40/6.20 20.40/6.20 Machine: 20.40/6.20 20.40/6.20 "x86_64-pc-linux-gnu" 20.40/6.20 20.40/6.20 Type definitions: 20.40/6.20 20.40/6.20 Global variables: 20.40/6.20 20.40/6.20 Function declarations and definitions: 20.40/6.20 20.40/6.20 *BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 20.40/6.20 0: 20.40/6.20 %1 = alloca i32, align 4 20.40/6.20 %i = alloca i32, align 4 20.40/6.20 %j = alloca i32, align 4 20.40/6.20 %k = alloca i32, align 4 20.40/6.20 %l = alloca i32, align 4 20.40/6.20 %m = alloca i32, align 4 20.40/6.20 %a = alloca i32, align 4 20.40/6.20 %b = alloca i32, align 4 20.40/6.20 store 0, %1 20.40/6.20 store 0, %i 20.40/6.20 br %2 20.40/6.20 2: 20.40/6.20 %3 = load %i 20.40/6.20 %4 = icmp slt %3 100 20.40/6.20 br %4, %5, %58 20.40/6.20 5: 20.40/6.20 %6 = load %i 20.40/6.20 %7 = add %6 2 20.40/6.20 store %7, %a 20.40/6.20 store 0, %j 20.40/6.20 br %8 20.40/6.20 8: 20.40/6.20 %9 = load %j 20.40/6.20 %10 = load %a 20.40/6.20 %11 = icmp slt %9 %10 20.40/6.20 br %11, %12, %55 20.40/6.20 12: 20.40/6.20 %13 = load %i 20.40/6.20 %14 = load %j 20.40/6.20 %15 = add %13 %14 20.40/6.20 %16 = add %15 3 20.40/6.20 store %16, %k 20.40/6.20 br %17 20.40/6.20 17: 20.40/6.20 %18 = load %k 20.40/6.20 %19 = icmp sge %18 0 20.40/6.20 br %19, %20, %52 20.40/6.20 20: 20.40/6.20 %21 = load %i 20.40/6.20 %22 = load %j 20.40/6.20 %23 = add %21 %22 20.40/6.20 %24 = load %k 20.40/6.20 %25 = add %23 %24 20.40/6.20 %26 = add %25 4 20.40/6.20 store %26, %b 20.40/6.20 store 0, %l 20.40/6.20 br %27 20.40/6.20 27: 20.40/6.20 %28 = load %l 20.40/6.20 %29 = load %b 20.40/6.20 %30 = icmp slt %28 %29 20.40/6.20 br %30, %31, %49 20.40/6.20 31: 20.40/6.20 %32 = load %i 20.40/6.20 %33 = load %j 20.40/6.20 %34 = add %32 %33 20.40/6.20 %35 = load %k 20.40/6.20 %36 = add %34 %35 20.40/6.20 %37 = load %l 20.40/6.20 %38 = add %36 %37 20.40/6.20 %39 = add %38 1000 20.40/6.20 store %39, %m 20.40/6.20 br %40 20.40/6.20 40: 20.40/6.20 %41 = load %m 20.40/6.20 %42 = icmp sge %41 0 20.40/6.20 br %42, %43, %46 20.40/6.20 43: 20.40/6.20 %44 = load %m 20.40/6.20 %45 = sub %44 0 20.40/6.20 store %45, %m 20.40/6.20 br %40 20.40/6.20 46: 20.40/6.20 %47 = load %l 20.40/6.20 %48 = add %47 1 20.40/6.20 store %48, %l 20.40/6.20 br %27 20.40/6.20 49: 20.40/6.20 %50 = load %k 20.40/6.20 %51 = sub %50 1 20.40/6.20 store %51, %k 20.40/6.20 br %17 20.40/6.20 52: 20.40/6.20 %53 = load %j 20.40/6.20 %54 = add %53 1 20.40/6.20 store %54, %j 20.40/6.20 br %8 20.40/6.20 55: 20.40/6.20 %56 = load %i 20.40/6.20 %57 = add %56 1 20.40/6.20 store %57, %i 20.40/6.20 br %2 20.40/6.20 58: 20.40/6.20 ret 0 20.40/6.20 20.40/6.20 20.40/6.20 Analyze Termination of all function calls matching the pattern: 20.40/6.20 main() 20.40/6.20 ---------------------------------------- 20.40/6.20 20.40/6.20 (3) LLVMToTerminationGraphProof (EQUIVALENT) 20.40/6.20 Constructed symbolic execution graph for LLVM program and proved memory safety. 20.40/6.20 ---------------------------------------- 20.40/6.20 20.40/6.20 (4) 20.40/6.20 Obligation: 20.40/6.20 SE Graph 20.40/6.20 ---------------------------------------- 20.40/6.20 20.40/6.20 (5) LLVMNonterminationProof (COMPLETE) 20.40/6.20 Proved nontermination with the following witness: 20.40/6.20 20.40/6.20 State #239 with references set to {}. 20.40/6.20 Nondeterministic instruction %1 = alloca i32, align 4 in node #239 yields value 17. 20.40/6.20 Nondeterministic instruction %i = alloca i32, align 4 in node #240 yields value 21. 20.40/6.20 Nondeterministic instruction %j = alloca i32, align 4 in node #241 yields value 1. 20.40/6.20 Nondeterministic instruction %k = alloca i32, align 4 in node #242 yields value 13. 20.40/6.20 Nondeterministic instruction %l = alloca i32, align 4 in node #243 yields value 29. 20.40/6.20 Nondeterministic instruction %m = alloca i32, align 4 in node #244 yields value 5. 20.40/6.20 Nondeterministic instruction %a = alloca i32, align 4 in node #245 yields value 25. 20.40/6.20 Nondeterministic instruction %b = alloca i32, align 4 in node #246 yields value 9. 20.40/6.20 20.40/6.20 ---------------------------------------- 20.40/6.20 20.40/6.20 (6) 20.40/6.20 NO 20.47/7.77 EOF