14.64/4.81 YES 14.64/4.82 proof of /export/starexec/sandbox/benchmark/theBenchmark.c 14.64/4.82 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 14.64/4.82 14.64/4.82 14.64/4.82 Termination of the given C Problem could be proven: 14.64/4.82 14.64/4.82 (0) C Problem 14.64/4.82 (1) CToLLVMProof [EQUIVALENT, 167 ms] 14.64/4.82 (2) LLVM problem 14.64/4.82 (3) LLVMToTerminationGraphProof [EQUIVALENT, 883 ms] 14.64/4.82 (4) LLVM Symbolic Execution Graph 14.64/4.82 (5) SymbolicExecutionGraphToSCCProof [SOUND, 0 ms] 14.64/4.82 (6) AND 14.64/4.82 (7) LLVM Symbolic Execution SCC 14.64/4.82 (8) SCC2IRS [SOUND, 25 ms] 14.64/4.82 (9) IntTRS 14.64/4.82 (10) IntTRSCompressionProof [EQUIVALENT, 0 ms] 14.64/4.82 (11) IntTRS 14.64/4.82 (12) RankingReductionPairProof [EQUIVALENT, 26 ms] 14.64/4.82 (13) YES 14.64/4.82 (14) LLVM Symbolic Execution SCC 14.64/4.82 (15) SCC2IRS [SOUND, 30 ms] 14.64/4.82 (16) IntTRS 14.64/4.82 (17) IntTRSCompressionProof [EQUIVALENT, 0 ms] 14.64/4.82 (18) IntTRS 14.64/4.82 (19) PolynomialOrderProcessor [EQUIVALENT, 0 ms] 14.64/4.82 (20) YES 14.64/4.82 14.64/4.82 14.64/4.82 ---------------------------------------- 14.64/4.82 14.64/4.82 (0) 14.64/4.82 Obligation: 14.64/4.82 c file /export/starexec/sandbox/benchmark/theBenchmark.c 14.64/4.82 ---------------------------------------- 14.64/4.82 14.64/4.82 (1) CToLLVMProof (EQUIVALENT) 14.64/4.82 Compiled c-file /export/starexec/sandbox/benchmark/theBenchmark.c to LLVM. 14.64/4.82 ---------------------------------------- 14.64/4.82 14.64/4.82 (2) 14.64/4.82 Obligation: 14.64/4.82 LLVM Problem 14.64/4.82 14.64/4.82 Aliases: 14.64/4.82 14.64/4.82 Data layout: 14.64/4.82 14.64/4.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" 14.64/4.82 14.64/4.82 Machine: 14.64/4.82 14.64/4.82 "x86_64-pc-linux-gnu" 14.64/4.82 14.64/4.82 Type definitions: 14.64/4.82 14.64/4.82 Global variables: 14.64/4.82 14.64/4.82 Function declarations and definitions: 14.64/4.82 14.64/4.82 *BasicFunctionTypename: "__VERIFIER_nondet_int" returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 14.64/4.82 *BasicFunctionTypename: "test_fun" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: (x i32, y i32) variableLength: false visibilityType: DEFAULT callingConvention: ccc 14.64/4.82 0: 14.64/4.82 %1 = alloca i32, align 4 14.64/4.82 %2 = alloca i32, align 4 14.64/4.82 store %x, %1 14.64/4.82 store %y, %2 14.64/4.82 br %3 14.64/4.82 3: 14.64/4.82 %4 = load %1 14.64/4.82 %5 = icmp sgt %4 0 14.64/4.82 br %5, %6, %9 14.64/4.82 6: 14.64/4.82 %7 = load %2 14.64/4.82 %8 = icmp sgt %7 0 14.64/4.82 br %9 14.64/4.82 9: 14.64/4.82 %10 = phi [0, %3], [%8, %6] 14.64/4.82 br %10, %11, %32 14.64/4.82 11: 14.64/4.82 %12 = load %1 14.64/4.82 %13 = load %2 14.64/4.82 %14 = icmp sgt %12 %13 14.64/4.82 br %14, %15, %23 14.64/4.82 15: 14.64/4.82 br %16 14.64/4.82 16: 14.64/4.82 %17 = load %1 14.64/4.82 %18 = icmp sgt %17 0 14.64/4.82 br %18, %19, %22 14.64/4.82 19: 14.64/4.82 %20 = load %1 14.64/4.82 %21 = sub %20 1 14.64/4.82 store %21, %1 14.64/4.82 br %16 14.64/4.82 22: 14.64/4.82 br %31 14.64/4.82 23: 14.64/4.82 br %24 14.64/4.82 24: 14.64/4.82 %25 = load %2 14.64/4.82 %26 = icmp sgt %25 0 14.64/4.82 br %26, %27, %30 14.64/4.82 27: 14.64/4.82 %28 = load %2 14.64/4.82 %29 = sub %28 1 14.64/4.82 store %29, %2 14.64/4.82 br %24 14.64/4.82 30: 14.64/4.82 br %31 14.64/4.82 31: 14.64/4.82 br %3 14.64/4.82 32: 14.64/4.82 %33 = load %1 14.64/4.82 %34 = load %2 14.64/4.82 %35 = add %33 %34 14.64/4.82 ret %35 14.64/4.82 14.64/4.82 *BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 14.64/4.82 0: 14.64/4.82 %1 = alloca i32, align 4 14.64/4.82 store 0, %1 14.64/4.82 %2 = call i32 @__VERIFIER_nondet_int() 14.64/4.82 %3 = call i32 @__VERIFIER_nondet_int() 14.64/4.82 %4 = call i32 @test_fun(i32 %2, i32 %3) 14.64/4.82 ret %4 14.64/4.82 14.64/4.82 14.64/4.82 Analyze Termination of all function calls matching the pattern: 14.64/4.82 main() 14.64/4.82 ---------------------------------------- 14.64/4.82 14.64/4.82 (3) LLVMToTerminationGraphProof (EQUIVALENT) 14.64/4.82 Constructed symbolic execution graph for LLVM program and proved memory safety. 14.64/4.82 ---------------------------------------- 14.64/4.82 14.64/4.82 (4) 14.64/4.82 Obligation: 14.64/4.82 SE Graph 14.64/4.82 ---------------------------------------- 14.64/4.82 14.64/4.82 (5) SymbolicExecutionGraphToSCCProof (SOUND) 14.64/4.82 Splitted symbolic execution graph to 2 SCCs. 14.64/4.82 ---------------------------------------- 14.64/4.82 14.64/4.82 (6) 14.64/4.82 Complex Obligation (AND) 14.64/4.82 14.64/4.82 ---------------------------------------- 14.64/4.82 14.64/4.82 (7) 14.64/4.82 Obligation: 14.64/4.82 SCC 14.64/4.82 ---------------------------------------- 14.64/4.82 14.64/4.82 (8) SCC2IRS (SOUND) 14.64/4.82 Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 14.64/4.82 Generated rules. Obtained 9 rulesP rules: 14.64/4.82 f_258(v62, v63, v64, v65, 1, 0, v69, v68, v70, v71, v72, v73, 3, 4) -> f_261(v62, v63, v64, v65, 1, 0, v69, v68, v70, v71, v72, v73, 3, 2, 4) :|: 0 < v69 && 2 <= v68 && 2 <= v63 14.64/4.82 f_261(v62, v63, v64, v65, 1, 0, v69, v68, v70, v71, v72, v73, 3, 2, 4) -> f_265(v62, v63, v64, v65, 1, 0, v69, v68, v70, v71, v72, v73, 3, 2, 4) :|: 0 = 0 14.64/4.82 f_265(v62, v63, v64, v65, 1, 0, v69, v68, v70, v71, v72, v73, 3, 2, 4) -> f_269(v62, v63, v64, v65, 1, 0, v69, v68, v70, v71, v72, v73, 3, 2, 4) :|: TRUE 14.64/4.82 f_269(v62, v63, v64, v65, 1, 0, v69, v68, v70, v71, v72, v73, 3, 2, 4) -> f_273(v62, v63, v64, v65, 1, 0, v69, v70, v71, v72, v73, 3, 2, 4) :|: 0 = 0 14.64/4.82 f_273(v62, v63, v64, v65, 1, 0, v69, v70, v71, v72, v73, 3, 2, 4) -> f_277(v62, v63, v64, v65, 1, 0, v69, v76, v70, v71, v72, v73, 3, 2, 4) :|: 1 + v76 = v69 && 0 <= v76 14.64/4.82 f_277(v62, v63, v64, v65, 1, 0, v69, v76, v70, v71, v72, v73, 3, 2, 4) -> f_281(v62, v63, v64, v65, 1, 0, v69, v76, v70, v71, v72, v73, 3, 2, 4) :|: TRUE 14.64/4.82 f_281(v62, v63, v64, v65, 1, 0, v69, v76, v70, v71, v72, v73, 3, 2, 4) -> f_284(v62, v63, v64, v65, 1, 0, v69, v76, v70, v71, v72, v73, 3, 2, 4) :|: TRUE 14.64/4.82 f_284(v62, v63, v64, v65, 1, 0, v69, v76, v70, v71, v72, v73, 3, 2, 4) -> f_255(v62, v63, v64, v65, 1, 0, v69, v76, v70, v71, v72, v73, 3, 4) :|: TRUE 14.64/4.82 f_255(v62, v63, v64, v65, 1, 0, v68, v69, v70, v71, v72, v73, 3, 4) -> f_258(v62, v63, v64, v65, 1, 0, v69, v68, v70, v71, v72, v73, 3, 4) :|: 0 = 0 14.64/4.82 Combined rules. Obtained 1 rulesP rules: 14.64/4.82 f_258(v62:0, v63:0, v64:0, v65:0, 1, 0, 1 + v76:0, v68:0, v70:0, v71:0, v72:0, v73:0, 3, 4) -> f_258(v62:0, v63:0, v64:0, v65:0, 1, 0, v76:0, 1 + v76:0, v70:0, v71:0, v72:0, v73:0, 3, 4) :|: v68:0 > 1 && v76:0 > -1 && v63:0 > 1 14.64/4.82 Filtered unneeded arguments: 14.64/4.82 f_258(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14) -> f_258(x2, x7, x8) 14.64/4.82 Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules: 14.64/4.82 f_258(v63:0, sum~cons_1~v76:0, v68:0) -> f_258(v63:0, v76:0, 1 + v76:0) :|: v76:0 > -1 && v63:0 > 1 && v68:0 > 1 && sum~cons_1~v76:0 = 1 + v76:0 14.64/4.82 14.64/4.82 ---------------------------------------- 14.64/4.82 14.64/4.82 (9) 14.64/4.82 Obligation: 14.64/4.82 Rules: 14.64/4.82 f_258(v63:0, sum~cons_1~v76:0, v68:0) -> f_258(v63:0, v76:0, 1 + v76:0) :|: v76:0 > -1 && v63:0 > 1 && v68:0 > 1 && sum~cons_1~v76:0 = 1 + v76:0 14.64/4.82 14.64/4.82 ---------------------------------------- 14.64/4.82 14.64/4.82 (10) IntTRSCompressionProof (EQUIVALENT) 14.64/4.82 Compressed rules. 14.64/4.82 ---------------------------------------- 14.64/4.82 14.64/4.82 (11) 14.64/4.82 Obligation: 14.64/4.82 Rules: 14.64/4.82 f_258(v63:0:0, sum~cons_1~v76:0:0, v68:0:0) -> f_258(v63:0:0, v76:0:0, 1 + v76:0:0) :|: v76:0:0 > -1 && v63:0:0 > 1 && v68:0:0 > 1 && sum~cons_1~v76:0:0 = 1 + v76:0:0 14.64/4.82 14.64/4.82 ---------------------------------------- 14.64/4.82 14.64/4.82 (12) RankingReductionPairProof (EQUIVALENT) 14.64/4.82 Interpretation: 14.64/4.82 [ f_258 ] = f_258_2 14.64/4.82 14.64/4.82 The following rules are decreasing: 14.64/4.82 f_258(v63:0:0, sum~cons_1~v76:0:0, v68:0:0) -> f_258(v63:0:0, v76:0:0, 1 + v76:0:0) :|: v76:0:0 > -1 && v63:0:0 > 1 && v68:0:0 > 1 && sum~cons_1~v76:0:0 = 1 + v76:0:0 14.64/4.82 14.64/4.82 The following rules are bounded: 14.64/4.82 f_258(v63:0:0, sum~cons_1~v76:0:0, v68:0:0) -> f_258(v63:0:0, v76:0:0, 1 + v76:0:0) :|: v76:0:0 > -1 && v63:0:0 > 1 && v68:0:0 > 1 && sum~cons_1~v76:0:0 = 1 + v76:0:0 14.64/4.82 14.64/4.82 14.64/4.82 ---------------------------------------- 14.64/4.82 14.64/4.82 (13) 14.64/4.82 YES 14.64/4.82 14.64/4.82 ---------------------------------------- 14.64/4.82 14.64/4.82 (14) 14.64/4.82 Obligation: 14.64/4.82 SCC 14.64/4.82 ---------------------------------------- 14.64/4.82 14.64/4.82 (15) SCC2IRS (SOUND) 14.64/4.82 Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 14.64/4.82 Generated rules. Obtained 9 rulesP rules: 14.64/4.82 f_253(v49, v50, v51, v52, 1, v55, v54, v56, v57, v58, v59, 0, 3, 2, 4) -> f_256(v49, v50, v51, v52, 1, v55, v54, v56, v57, v58, v59, 0, 3, 2, 4) :|: 0 < v55 && 2 <= v54 14.64/4.82 f_256(v49, v50, v51, v52, 1, v55, v54, v56, v57, v58, v59, 0, 3, 2, 4) -> f_259(v49, v50, v51, v52, 1, v55, v54, v56, v57, v58, v59, 0, 3, 2, 4) :|: 0 = 0 14.64/4.82 f_259(v49, v50, v51, v52, 1, v55, v54, v56, v57, v58, v59, 0, 3, 2, 4) -> f_263(v49, v50, v51, v52, 1, v55, v54, v56, v57, v58, v59, 0, 3, 2, 4) :|: TRUE 14.64/4.82 f_263(v49, v50, v51, v52, 1, v55, v54, v56, v57, v58, v59, 0, 3, 2, 4) -> f_267(v49, v50, v51, v52, 1, v55, v56, v57, v58, v59, 0, 3, 2, 4) :|: 0 = 0 14.64/4.82 f_267(v49, v50, v51, v52, 1, v55, v56, v57, v58, v59, 0, 3, 2, 4) -> f_271(v49, v50, v51, v52, 1, v55, v74, v56, v57, v58, v59, 0, 3, 2, 4) :|: 1 + v74 = v55 && 0 <= v74 14.64/4.82 f_271(v49, v50, v51, v52, 1, v55, v74, v56, v57, v58, v59, 0, 3, 2, 4) -> f_275(v49, v50, v51, v52, 1, v55, v74, v56, v57, v58, v59, 0, 3, 2, 4) :|: TRUE 14.64/4.82 f_275(v49, v50, v51, v52, 1, v55, v74, v56, v57, v58, v59, 0, 3, 2, 4) -> f_279(v49, v50, v51, v52, 1, v55, v74, v56, v57, v58, v59, 0, 3, 2, 4) :|: TRUE 14.64/4.82 f_279(v49, v50, v51, v52, 1, v55, v74, v56, v57, v58, v59, 0, 3, 2, 4) -> f_250(v49, v50, v51, v52, 1, v55, v74, v56, v57, v58, v59, 0, 3, 2, 4) :|: TRUE 14.64/4.82 f_250(v49, v50, v51, v52, 1, v54, v55, v56, v57, v58, v59, 0, 3, 2, 4) -> f_253(v49, v50, v51, v52, 1, v55, v54, v56, v57, v58, v59, 0, 3, 2, 4) :|: 0 = 0 14.64/4.82 Combined rules. Obtained 1 rulesP rules: 14.64/4.82 f_253(v49:0, v50:0, v51:0, v52:0, 1, 1 + v74:0, v54:0, v56:0, v57:0, v58:0, v59:0, 0, 3, 2, 4) -> f_253(v49:0, v50:0, v51:0, v52:0, 1, v74:0, 1 + v74:0, v56:0, v57:0, v58:0, v59:0, 0, 3, 2, 4) :|: v54:0 > 1 && v74:0 > -1 14.64/4.82 Filtered unneeded arguments: 14.64/4.82 f_253(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15) -> f_253(x6, x7) 14.64/4.82 Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules: 14.64/4.82 f_253(sum~cons_1~v74:0, v54:0) -> f_253(v74:0, 1 + v74:0) :|: v54:0 > 1 && v74:0 > -1 && sum~cons_1~v74:0 = 1 + v74:0 14.64/4.82 14.64/4.82 ---------------------------------------- 14.64/4.82 14.64/4.82 (16) 14.64/4.82 Obligation: 14.64/4.82 Rules: 14.64/4.82 f_253(sum~cons_1~v74:0, v54:0) -> f_253(v74:0, 1 + v74:0) :|: v54:0 > 1 && v74:0 > -1 && sum~cons_1~v74:0 = 1 + v74:0 14.64/4.82 14.64/4.82 ---------------------------------------- 14.64/4.82 14.64/4.82 (17) IntTRSCompressionProof (EQUIVALENT) 14.64/4.82 Compressed rules. 14.64/4.82 ---------------------------------------- 14.64/4.82 14.64/4.82 (18) 14.64/4.82 Obligation: 14.64/4.82 Rules: 14.64/4.82 f_253(sum~cons_1~v74:0:0, v54:0:0) -> f_253(v74:0:0, 1 + v74:0:0) :|: v54:0:0 > 1 && v74:0:0 > -1 && sum~cons_1~v74:0:0 = 1 + v74:0:0 14.64/4.82 14.64/4.82 ---------------------------------------- 14.64/4.82 14.64/4.82 (19) PolynomialOrderProcessor (EQUIVALENT) 14.64/4.82 Found the following polynomial interpretation: 14.64/4.82 [f_253(x, x1)] = x 14.64/4.82 14.64/4.82 The following rules are decreasing: 14.64/4.82 f_253(sum~cons_1~v74:0:0, v54:0:0) -> f_253(v74:0:0, 1 + v74:0:0) :|: v54:0:0 > 1 && v74:0:0 > -1 && sum~cons_1~v74:0:0 = 1 + v74:0:0 14.64/4.82 The following rules are bounded: 14.64/4.82 f_253(sum~cons_1~v74:0:0, v54:0:0) -> f_253(v74:0:0, 1 + v74:0:0) :|: v54:0:0 > 1 && v74:0:0 > -1 && sum~cons_1~v74:0:0 = 1 + v74:0:0 14.64/4.82 14.64/4.82 ---------------------------------------- 14.64/4.82 14.64/4.82 (20) 14.64/4.82 YES 14.64/4.86 EOF