11.06/4.04 YES 11.45/4.06 proof of /export/starexec/sandbox2/benchmark/theBenchmark.c 11.45/4.06 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 11.45/4.06 11.45/4.06 11.45/4.06 Termination of the given C Problem could be proven: 11.45/4.06 11.45/4.06 (0) C Problem 11.45/4.06 (1) CToLLVMProof [EQUIVALENT, 175 ms] 11.45/4.06 (2) LLVM problem 11.45/4.06 (3) LLVMToTerminationGraphProof [EQUIVALENT, 1583 ms] 11.45/4.06 (4) LLVM Symbolic Execution Graph 11.45/4.06 (5) SymbolicExecutionGraphToSCCProof [SOUND, 0 ms] 11.45/4.06 (6) LLVM Symbolic Execution SCC 11.45/4.06 (7) SCC2IRS [SOUND, 60 ms] 11.45/4.06 (8) IntTRS 11.45/4.06 (9) IntTRSCompressionProof [EQUIVALENT, 0 ms] 11.45/4.06 (10) IntTRS 11.45/4.06 (11) PolynomialOrderProcessor [EQUIVALENT, 9 ms] 11.45/4.06 (12) YES 11.45/4.06 11.45/4.06 11.45/4.06 ---------------------------------------- 11.45/4.06 11.45/4.06 (0) 11.45/4.06 Obligation: 11.45/4.06 c file /export/starexec/sandbox2/benchmark/theBenchmark.c 11.45/4.06 ---------------------------------------- 11.45/4.06 11.45/4.06 (1) CToLLVMProof (EQUIVALENT) 11.45/4.06 Compiled c-file /export/starexec/sandbox2/benchmark/theBenchmark.c to LLVM. 11.45/4.06 ---------------------------------------- 11.45/4.06 11.45/4.06 (2) 11.45/4.06 Obligation: 11.45/4.06 LLVM Problem 11.45/4.06 11.45/4.06 Aliases: 11.45/4.06 11.45/4.06 Data layout: 11.45/4.06 11.45/4.06 "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" 11.45/4.07 11.45/4.07 Machine: 11.45/4.07 11.45/4.07 "x86_64-pc-linux-gnu" 11.45/4.07 11.45/4.07 Type definitions: 11.45/4.07 11.45/4.07 Global variables: 11.45/4.07 11.45/4.07 Function declarations and definitions: 11.45/4.07 11.45/4.07 *BasicFunctionTypename: "__VERIFIER_nondet_int" returnParam: i32 parameters: () variableLength: true visibilityType: DEFAULT callingConvention: ccc 11.45/4.07 *BasicFunctionTypename: "rec1" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: (i i32) variableLength: false visibilityType: DEFAULT callingConvention: ccc 11.45/4.07 0: 11.45/4.07 %1 = alloca i32, align 4 11.45/4.07 %2 = alloca i32, align 4 11.45/4.07 store %i, %2 11.45/4.07 %3 = load %2 11.45/4.07 %4 = icmp sle %3 0 11.45/4.07 br %4, %5, %6 11.45/4.07 5: 11.45/4.07 store 0, %1 11.45/4.07 br %14 11.45/4.07 6: 11.45/4.07 %7 = load %2 11.45/4.07 %8 = sub %7 2 11.45/4.07 %9 = call i32 @rec1(i32 %8) 11.45/4.07 %10 = sub %9 1 11.45/4.07 %11 = call i32 @rec1(i32 %10) 11.45/4.07 %12 = call i32 @rec1(i32 %11) 11.45/4.07 %13 = add %12 1 11.45/4.07 store %13, %1 11.45/4.07 br %14 11.45/4.07 14: 11.45/4.07 %15 = load %1 11.45/4.07 ret %15 11.45/4.07 11.45/4.07 *BasicFunctionTypename: "rec2" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: (j i32) variableLength: false visibilityType: DEFAULT callingConvention: ccc 11.45/4.07 0: 11.45/4.07 %1 = alloca i32, align 4 11.45/4.07 %2 = alloca i32, align 4 11.45/4.07 store %j, %2 11.45/4.07 %3 = load %2 11.45/4.07 %4 = icmp sle %3 0 11.45/4.07 br %4, %5, %6 11.45/4.07 5: 11.45/4.07 store 0, %1 11.45/4.07 br %12 11.45/4.07 6: 11.45/4.07 %7 = load %2 11.45/4.07 %8 = sub %7 1 11.45/4.07 %9 = call i32 @rec2(i32 %8) 11.45/4.07 %10 = call i32 @rec1(i32 %9) 11.45/4.07 %11 = sub %10 1 11.45/4.07 store %11, %1 11.45/4.07 br %12 11.45/4.07 12: 11.45/4.07 %13 = load %1 11.45/4.07 ret %13 11.45/4.07 11.45/4.07 *BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 11.45/4.07 0: 11.45/4.07 %1 = alloca i32, align 4 11.45/4.07 %x = alloca i32, align 4 11.45/4.07 store 0, %1 11.45/4.07 %2 = call i32 (...)* @__VERIFIER_nondet_int() 11.45/4.07 store %2, %x 11.45/4.07 %3 = load %x 11.45/4.07 %4 = call i32 @rec2(i32 %3) 11.45/4.07 %5 = load %1 11.45/4.07 ret %5 11.45/4.07 11.45/4.07 11.45/4.07 Analyze Termination of all function calls matching the pattern: 11.45/4.07 main() 11.45/4.07 ---------------------------------------- 11.45/4.07 11.45/4.07 (3) LLVMToTerminationGraphProof (EQUIVALENT) 11.45/4.07 Constructed symbolic execution graph for LLVM program and proved memory safety. 11.45/4.07 ---------------------------------------- 11.45/4.07 11.45/4.07 (4) 11.45/4.07 Obligation: 11.45/4.07 SE Graph 11.45/4.07 ---------------------------------------- 11.45/4.07 11.45/4.07 (5) SymbolicExecutionGraphToSCCProof (SOUND) 11.45/4.07 Splitted symbolic execution graph to 1 SCC. 11.45/4.07 ---------------------------------------- 11.45/4.07 11.45/4.07 (6) 11.45/4.07 Obligation: 11.45/4.07 SCC 11.45/4.07 ---------------------------------------- 11.45/4.07 11.45/4.07 (7) SCC2IRS (SOUND) 11.45/4.07 Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 11.45/4.07 Generated rules. Obtained 12 rulesP rules: 11.45/4.07 f_191(v45, v52, v46, v47, v48, v49, v53, 0, v51, 3, 1, 4) -> f_192(v45, v52, v54, v46, v47, v48, v49, v53, v55, 0, v51, 3, 1, 4) :|: 1 <= v54 && v55 = 3 + v54 && 4 <= v55 11.45/4.07 f_192(v45, v52, v54, v46, v47, v48, v49, v53, v55, 0, v51, 3, 1, 4) -> f_193(v45, v52, v54, v46, v47, v48, v49, v53, v55, 0, v51, 3, 1, 4) :|: TRUE 11.45/4.07 f_193(v45, v52, v54, v46, v47, v48, v49, v53, v55, 0, v51, 3, 1, 4) -> f_194(v45, v52, v54, v46, v47, v48, v49, v53, v55, 0, v51, 3, 1, 4) :|: 0 = 0 11.45/4.07 f_194(v45, v52, v54, v46, v47, v48, v49, v53, v55, 0, v51, 3, 1, 4) -> f_196(v45, v52, v54, v46, v47, v48, v49, v53, v55, 0, v51, 3, 1, 4) :|: 0 < v45 && 1 <= v51 11.45/4.07 f_196(v45, v52, v54, v46, v47, v48, v49, v53, v55, 0, v51, 3, 1, 4) -> f_198(v45, v52, v54, 0, v46, v47, v48, v49, v53, v55, v51, 3, 1, 4) :|: 0 = 0 11.45/4.07 f_198(v45, v52, v54, 0, v46, v47, v48, v49, v53, v55, v51, 3, 1, 4) -> f_200(v45, v52, v54, 0, v46, v47, v48, v49, v53, v55, v51, 3, 1, 4) :|: TRUE 11.45/4.07 f_200(v45, v52, v54, 0, v46, v47, v48, v49, v53, v55, v51, 3, 1, 4) -> f_202(v45, v52, v54, 0, v46, v47, v48, v49, v53, v55, v51, 3, 1, 4) :|: 0 = 0 11.45/4.07 f_202(v45, v52, v54, 0, v46, v47, v48, v49, v53, v55, v51, 3, 1, 4) -> f_204(v45, v52, v54, 0, v57, v46, v47, v48, v49, v53, v55, v51, 3, 1, 4) :|: 1 + v57 = v45 && 0 <= v57 11.45/4.07 f_204(v45, v52, v54, 0, v57, v46, v47, v48, v49, v53, v55, v51, 3, 1, 4) -> f_206(v57, v46, v47, v48, v49, v52, v53, v54, v55, 0, v51, v45, 3, 1, 4) :|: 0 = 0 11.45/4.07 f_206(v57, v46, v47, v48, v49, v52, v53, v54, v55, 0, v51, v45, 3, 1, 4) -> f_208(v57, v46, v47, v48, v49, v52, v53, v54, v55, 0, v51, v45, 3, 1, 4) :|: TRUE 11.45/4.07 f_208(v57, v46, v47, v48, v49, v52, v53, v54, v55, 0, v51, v45, 3, 1, 4) -> f_189(v57, v46, v47, v48, v49, 0, v51, 3, 1, 4) :|: TRUE 11.45/4.07 f_189(v45, v46, v47, v48, v49, 0, v51, 3, 1, 4) -> f_191(v45, v52, v46, v47, v48, v49, v53, 0, v51, 3, 1, 4) :|: 1 <= v52 && v53 = 3 + v52 && 4 <= v53 11.45/4.07 Combined rules. Obtained 1 rulesP rules: 11.45/4.07 f_191(1 + v57:0, v52:0, v46:0, v47:0, v48:0, v49:0, v53:0, 0, v51:0, 3, 1, 4) -> f_191(v57:0, v52:1, v46:0, v47:0, v48:0, v49:0, 3 + v52:1, 0, v51:0, 3, 1, 4) :|: v54:0 > 0 && v51:0 > 0 && v57:0 > -1 && v52:1 > 0 11.45/4.07 Filtered unneeded arguments: 11.45/4.07 f_191(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12) -> f_191(x1, x9) 11.45/4.07 Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules: 11.45/4.07 f_191(sum~cons_1~v57:0, v51:0) -> f_191(v57:0, v51:0) :|: v51:0 > 0 && v57:0 > -1 && sum~cons_1~v57:0 = 1 + v57:0 11.45/4.07 11.45/4.07 ---------------------------------------- 11.45/4.07 11.45/4.07 (8) 11.45/4.07 Obligation: 11.45/4.07 Rules: 11.45/4.07 f_191(sum~cons_1~v57:0, v51:0) -> f_191(v57:0, v51:0) :|: v51:0 > 0 && v57:0 > -1 && sum~cons_1~v57:0 = 1 + v57:0 11.45/4.07 11.45/4.07 ---------------------------------------- 11.45/4.07 11.45/4.07 (9) IntTRSCompressionProof (EQUIVALENT) 11.45/4.07 Compressed rules. 11.45/4.07 ---------------------------------------- 11.45/4.07 11.45/4.07 (10) 11.45/4.07 Obligation: 11.45/4.07 Rules: 11.45/4.07 f_191(sum~cons_1~v57:0:0, v51:0:0) -> f_191(v57:0:0, v51:0:0) :|: v51:0:0 > 0 && v57:0:0 > -1 && sum~cons_1~v57:0:0 = 1 + v57:0:0 11.45/4.07 11.45/4.07 ---------------------------------------- 11.45/4.07 11.45/4.07 (11) PolynomialOrderProcessor (EQUIVALENT) 11.45/4.07 Found the following polynomial interpretation: 11.45/4.07 [f_191(x, x1)] = x 11.45/4.07 11.45/4.07 The following rules are decreasing: 11.45/4.07 f_191(sum~cons_1~v57:0:0, v51:0:0) -> f_191(v57:0:0, v51:0:0) :|: v51:0:0 > 0 && v57:0:0 > -1 && sum~cons_1~v57:0:0 = 1 + v57:0:0 11.45/4.07 The following rules are bounded: 11.45/4.07 f_191(sum~cons_1~v57:0:0, v51:0:0) -> f_191(v57:0:0, v51:0:0) :|: v51:0:0 > 0 && v57:0:0 > -1 && sum~cons_1~v57:0:0 = 1 + v57:0:0 11.45/4.07 11.45/4.07 ---------------------------------------- 11.45/4.07 11.45/4.07 (12) 11.45/4.07 YES 11.66/4.14 EOF