15.17/5.14 YES 15.19/5.15 proof of /export/starexec/sandbox2/benchmark/theBenchmark.c 15.19/5.15 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 15.19/5.15 15.19/5.15 15.19/5.15 Termination of the given C Problem could be proven: 15.19/5.15 15.19/5.15 (0) C Problem 15.19/5.15 (1) CToLLVMProof [EQUIVALENT, 161 ms] 15.19/5.15 (2) LLVM problem 15.19/5.15 (3) LLVMToTerminationGraphProof [EQUIVALENT, 2212 ms] 15.19/5.15 (4) LLVM Symbolic Execution Graph 15.19/5.15 (5) SymbolicExecutionGraphToSCCProof [SOUND, 0 ms] 15.19/5.15 (6) LLVM Symbolic Execution SCC 15.19/5.15 (7) SCC2IRS [SOUND, 72 ms] 15.19/5.15 (8) IntTRS 15.19/5.15 (9) IntTRSCompressionProof [EQUIVALENT, 0 ms] 15.19/5.15 (10) IntTRS 15.19/5.15 (11) PolynomialOrderProcessor [EQUIVALENT, 8 ms] 15.19/5.15 (12) YES 15.19/5.15 15.19/5.15 15.19/5.15 ---------------------------------------- 15.19/5.15 15.19/5.15 (0) 15.19/5.15 Obligation: 15.19/5.15 c file /export/starexec/sandbox2/benchmark/theBenchmark.c 15.19/5.15 ---------------------------------------- 15.19/5.15 15.19/5.15 (1) CToLLVMProof (EQUIVALENT) 15.19/5.15 Compiled c-file /export/starexec/sandbox2/benchmark/theBenchmark.c to LLVM. 15.19/5.15 ---------------------------------------- 15.19/5.15 15.19/5.15 (2) 15.19/5.15 Obligation: 15.19/5.15 LLVM Problem 15.19/5.15 15.19/5.15 Aliases: 15.19/5.15 15.19/5.15 Data layout: 15.19/5.15 15.19/5.15 "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" 15.19/5.15 15.19/5.15 Machine: 15.19/5.15 15.19/5.15 "x86_64-pc-linux-gnu" 15.19/5.15 15.19/5.15 Type definitions: 15.19/5.15 15.19/5.15 Global variables: 15.19/5.15 15.19/5.15 Function declarations and definitions: 15.19/5.15 15.19/5.15 *BasicFunctionTypename: "__VERIFIER_nondet_int" returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 15.19/5.15 *BasicFunctionTypename: "addition" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: (m i32, n i32) variableLength: false visibilityType: DEFAULT callingConvention: ccc 15.19/5.15 0: 15.19/5.15 %1 = alloca i32, align 4 15.19/5.15 %2 = alloca i32, align 4 15.19/5.15 %3 = alloca i32, align 4 15.19/5.15 store %m, %2 15.19/5.15 store %n, %3 15.19/5.15 %4 = load %3 15.19/5.15 %5 = icmp eq %4 0 15.19/5.15 br %5, %6, %8 15.19/5.15 6: 15.19/5.15 %7 = load %2 15.19/5.15 store %7, %1 15.19/5.15 br %26 15.19/5.15 8: 15.19/5.15 %9 = load %3 15.19/5.15 %10 = icmp sgt %9 0 15.19/5.15 br %10, %11, %17 15.19/5.15 11: 15.19/5.15 %12 = load %2 15.19/5.15 %13 = add %12 1 15.19/5.15 %14 = load %3 15.19/5.15 %15 = sub %14 1 15.19/5.15 %16 = call i32 @addition(i32 %13, i32 %15) 15.19/5.15 store %16, %1 15.19/5.15 br %26 15.19/5.15 17: 15.19/5.15 %18 = load %3 15.19/5.15 %19 = icmp slt %18 0 15.19/5.15 br %19, %20, %26 15.19/5.15 20: 15.19/5.15 %21 = load %2 15.19/5.15 %22 = sub %21 1 15.19/5.15 %23 = load %3 15.19/5.15 %24 = add %23 1 15.19/5.15 %25 = call i32 @addition(i32 %22, i32 %24) 15.19/5.15 store %25, %1 15.19/5.15 br %26 15.19/5.15 26: 15.19/5.15 %27 = load %1 15.19/5.15 ret %27 15.19/5.15 15.19/5.15 *BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 15.19/5.15 0: 15.19/5.15 %1 = alloca i32, align 4 15.19/5.15 %m = alloca i32, align 4 15.19/5.15 %n = alloca i32, align 4 15.19/5.15 %result = alloca i32, align 4 15.19/5.15 store 0, %1 15.19/5.15 %2 = call i32 @__VERIFIER_nondet_int() 15.19/5.15 store %2, %m 15.19/5.15 %3 = load %m 15.19/5.15 %4 = icmp sle %3 0 15.19/5.15 br %4, %5, %6 15.19/5.15 5: 15.19/5.15 store 0, %1 15.19/5.15 br %15 15.19/5.15 6: 15.19/5.15 %7 = call i32 @__VERIFIER_nondet_int() 15.19/5.15 store %7, %n 15.19/5.15 %8 = load %n 15.19/5.15 %9 = icmp sle %8 0 15.19/5.15 br %9, %10, %11 15.19/5.15 10: 15.19/5.15 store 0, %1 15.19/5.15 br %15 15.19/5.15 11: 15.19/5.15 %12 = load %m 15.19/5.15 %13 = load %n 15.19/5.15 %14 = call i32 @addition(i32 %12, i32 %13) 15.19/5.15 store %14, %result 15.19/5.15 br %15 15.19/5.15 15: 15.19/5.15 %16 = load %1 15.19/5.15 ret %16 15.19/5.15 15.19/5.15 15.19/5.15 Analyze Termination of all function calls matching the pattern: 15.19/5.15 main() 15.19/5.15 ---------------------------------------- 15.19/5.15 15.19/5.15 (3) LLVMToTerminationGraphProof (EQUIVALENT) 15.19/5.15 Constructed symbolic execution graph for LLVM program and proved memory safety. 15.19/5.15 ---------------------------------------- 15.19/5.15 15.19/5.15 (4) 15.19/5.15 Obligation: 15.19/5.15 SE Graph 15.19/5.15 ---------------------------------------- 15.19/5.15 15.19/5.15 (5) SymbolicExecutionGraphToSCCProof (SOUND) 15.19/5.15 Splitted symbolic execution graph to 1 SCC. 15.19/5.15 ---------------------------------------- 15.19/5.15 15.19/5.15 (6) 15.19/5.15 Obligation: 15.19/5.15 SCC 15.19/5.15 ---------------------------------------- 15.19/5.15 15.19/5.15 (7) SCC2IRS (SOUND) 15.19/5.15 Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 15.19/5.15 Generated rules. Obtained 19 rulesP rules: 15.19/5.15 f_260(v63, v64, v76, v65, v66, v67, v68, v69, v70, v71, v72, v77, 0, v74, v75, 3, 1, 4) -> f_261(v63, v64, v76, v78, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, 0, v74, v75, 3, 1, 4) :|: 1 <= v78 && v79 = 3 + v78 && 4 <= v79 15.19/5.15 f_261(v63, v64, v76, v78, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, 0, v74, v75, 3, 1, 4) -> f_262(v63, v64, v76, v78, v80, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, 0, v74, v75, 3, 1, 4) :|: 1 <= v80 && v81 = 3 + v80 && 4 <= v81 15.19/5.15 f_262(v63, v64, v76, v78, v80, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, 0, v74, v75, 3, 1, 4) -> f_263(v63, v64, v76, v78, v80, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, 0, v74, v75, 3, 1, 4) :|: TRUE 15.19/5.15 f_263(v63, v64, v76, v78, v80, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, 0, v74, v75, 3, 1, 4) -> f_264(v63, v64, v76, v78, v80, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, 0, v74, v75, 3, 1, 4) :|: TRUE 15.19/5.15 f_264(v63, v64, v76, v78, v80, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, 0, v74, v75, 3, 1, 4) -> f_265(v63, v64, v76, v78, v80, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, 0, v74, v75, 3, 1, 4) :|: 0 = 0 15.19/5.15 f_265(v63, v64, v76, v78, v80, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, 0, v74, v75, 3, 1, 4) -> f_267(v63, v64, v76, v78, v80, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, 0, v74, v75, 3, 1, 4) :|: v64 != 0 15.19/5.15 f_267(v63, v64, v76, v78, v80, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, 0, v74, v75, 3, 1, 4) -> f_269(v63, v64, v76, v78, v80, 0, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, v74, v75, 3, 1, 4) :|: 0 = 0 15.19/5.15 f_269(v63, v64, v76, v78, v80, 0, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, v74, v75, 3, 1, 4) -> f_271(v63, v64, v76, v78, v80, 0, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, v74, v75, 3, 1, 4) :|: TRUE 15.19/5.15 f_271(v63, v64, v76, v78, v80, 0, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, v74, v75, 3, 1, 4) -> f_273(v63, v64, v76, v78, v80, 0, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, v74, v75, 3, 1, 4) :|: 0 = 0 15.19/5.15 f_273(v63, v64, v76, v78, v80, 0, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, v74, v75, 3, 1, 4) -> f_275(v63, v64, v76, v78, v80, 0, 1, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, v74, v75, 3, 4) :|: 0 = 0 15.19/5.15 f_275(v63, v64, v76, v78, v80, 0, 1, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, v74, v75, 3, 4) -> f_277(v63, v64, v76, v78, v80, 0, 1, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, v74, v75, 3, 4) :|: TRUE 15.19/5.15 f_277(v63, v64, v76, v78, v80, 0, 1, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, v74, v75, 3, 4) -> f_279(v63, v64, v76, v78, v80, 0, 1, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, v74, v75, 3, 4) :|: 0 = 0 15.19/5.15 f_279(v63, v64, v76, v78, v80, 0, 1, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, v74, v75, 3, 4) -> f_281(v63, v64, v76, v78, v80, 0, 1, v102, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, v74, v75, 3, 4, 2) :|: v102 = 1 + v63 && 2 <= v102 15.19/5.15 f_281(v63, v64, v76, v78, v80, 0, 1, v102, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, v74, v75, 3, 4, 2) -> f_282(v63, v64, v76, v78, v80, 0, 1, v102, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, v74, v75, 3, 4, 2) :|: 0 = 0 15.19/5.15 f_282(v63, v64, v76, v78, v80, 0, 1, v102, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, v74, v75, 3, 4, 2) -> f_283(v63, v64, v76, v78, v80, 0, 1, v102, v103, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, v74, v75, 3, 4, 2) :|: 1 + v103 = v64 && 0 <= v103 15.19/5.15 f_283(v63, v64, v76, v78, v80, 0, 1, v102, v103, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, v74, v75, 3, 4, 2) -> f_284(v102, v103, v65, v66, v67, v68, v69, v70, v71, v72, v76, v77, v78, v79, v80, v81, 0, v74, v75, v63, v64, 1, 3, 4, 2) :|: 0 = 0 15.19/5.15 f_284(v102, v103, v65, v66, v67, v68, v69, v70, v71, v72, v76, v77, v78, v79, v80, v81, 0, v74, v75, v63, v64, 1, 3, 4, 2) -> f_285(v102, v103, v65, v66, v67, v68, v69, v70, v71, v72, v76, v77, v78, v79, v80, v81, 0, v74, v75, v63, v64, 3, 1, 4, 2) :|: TRUE 15.19/5.15 f_285(v102, v103, v65, v66, v67, v68, v69, v70, v71, v72, v76, v77, v78, v79, v80, v81, 0, v74, v75, v63, v64, 3, 1, 4, 2) -> f_259(v102, v103, v65, v66, v67, v68, v69, v70, v71, v72, 0, v74, v75, 3, 1, 4) :|: TRUE 15.19/5.15 f_259(v63, v64, v65, v66, v67, v68, v69, v70, v71, v72, 0, v74, v75, 3, 1, 4) -> f_260(v63, v64, v76, v65, v66, v67, v68, v69, v70, v71, v72, v77, 0, v74, v75, 3, 1, 4) :|: 1 <= v76 && v77 = 3 + v76 && 4 <= v77 15.19/5.15 Combined rules. Obtained 1 rulesP rules: 15.19/5.15 f_260(v63:0, 1 + v103:0, v76:0, v65:0, v66:0, v67:0, v68:0, v69:0, v70:0, v71:0, v72:0, v77:0, 0, v74:0, v75:0, 3, 1, 4) -> f_260(1 + v63:0, v103:0, v76:1, v65:0, v66:0, v67:0, v68:0, v69:0, v70:0, v71:0, v72:0, 3 + v76:1, 0, v74:0, v75:0, 3, 1, 4) :|: v80:0 > 0 && v78:0 > 0 && v103:0 > -1 && v63:0 > 0 && v76:1 > 0 15.19/5.15 Filtered unneeded arguments: 15.19/5.15 f_260(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) -> f_260(x1, x2) 15.19/5.15 Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules: 15.19/5.15 f_260(v63:0, sum~cons_1~v103:0) -> f_260(1 + v63:0, v103:0) :|: v103:0 > -1 && v63:0 > 0 && sum~cons_1~v103:0 = 1 + v103:0 15.19/5.15 15.19/5.15 ---------------------------------------- 15.19/5.15 15.19/5.15 (8) 15.19/5.15 Obligation: 15.19/5.15 Rules: 15.19/5.15 f_260(v63:0, sum~cons_1~v103:0) -> f_260(1 + v63:0, v103:0) :|: v103:0 > -1 && v63:0 > 0 && sum~cons_1~v103:0 = 1 + v103:0 15.19/5.15 15.19/5.15 ---------------------------------------- 15.19/5.15 15.19/5.15 (9) IntTRSCompressionProof (EQUIVALENT) 15.19/5.15 Compressed rules. 15.19/5.15 ---------------------------------------- 15.19/5.15 15.19/5.15 (10) 15.19/5.15 Obligation: 15.19/5.15 Rules: 15.19/5.15 f_260(v63:0:0, sum~cons_1~v103:0:0) -> f_260(1 + v63:0:0, v103:0:0) :|: v103:0:0 > -1 && v63:0:0 > 0 && sum~cons_1~v103:0:0 = 1 + v103:0:0 15.19/5.15 15.19/5.15 ---------------------------------------- 15.19/5.15 15.19/5.15 (11) PolynomialOrderProcessor (EQUIVALENT) 15.19/5.15 Found the following polynomial interpretation: 15.19/5.15 [f_260(x, x1)] = x1 15.19/5.15 15.19/5.15 The following rules are decreasing: 15.19/5.15 f_260(v63:0:0, sum~cons_1~v103:0:0) -> f_260(1 + v63:0:0, v103:0:0) :|: v103:0:0 > -1 && v63:0:0 > 0 && sum~cons_1~v103:0:0 = 1 + v103:0:0 15.19/5.15 The following rules are bounded: 15.19/5.15 f_260(v63:0:0, sum~cons_1~v103:0:0) -> f_260(1 + v63:0:0, v103:0:0) :|: v103:0:0 > -1 && v63:0:0 > 0 && sum~cons_1~v103:0:0 = 1 + v103:0:0 15.19/5.15 15.19/5.15 ---------------------------------------- 15.19/5.15 15.19/5.15 (12) 15.19/5.15 YES 15.19/5.19 EOF