14.09/4.83 YES 14.09/4.84 proof of /export/starexec/sandbox2/benchmark/theBenchmark.c 14.09/4.84 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 14.09/4.84 14.09/4.84 14.09/4.84 Termination of the given C Problem could be proven: 14.09/4.84 14.09/4.84 (0) C Problem 14.09/4.84 (1) CToLLVMProof [EQUIVALENT, 175 ms] 14.09/4.84 (2) LLVM problem 14.09/4.84 (3) LLVMToTerminationGraphProof [EQUIVALENT, 1602 ms] 14.09/4.84 (4) LLVM Symbolic Execution Graph 14.09/4.84 (5) SymbolicExecutionGraphToSCCProof [SOUND, 0 ms] 14.09/4.84 (6) LLVM Symbolic Execution SCC 14.09/4.84 (7) SCC2IRS [SOUND, 87 ms] 14.09/4.84 (8) IntTRS 14.09/4.84 (9) RankingReductionPairProof [EQUIVALENT, 22 ms] 14.09/4.84 (10) YES 14.09/4.84 14.09/4.84 14.09/4.84 ---------------------------------------- 14.09/4.84 14.09/4.84 (0) 14.09/4.84 Obligation: 14.09/4.84 c file /export/starexec/sandbox2/benchmark/theBenchmark.c 14.09/4.84 ---------------------------------------- 14.09/4.84 14.09/4.84 (1) CToLLVMProof (EQUIVALENT) 14.09/4.84 Compiled c-file /export/starexec/sandbox2/benchmark/theBenchmark.c to LLVM. 14.09/4.84 ---------------------------------------- 14.09/4.84 14.09/4.84 (2) 14.09/4.84 Obligation: 14.09/4.84 LLVM Problem 14.09/4.84 14.09/4.84 Aliases: 14.09/4.84 14.09/4.84 Data layout: 14.09/4.84 14.09/4.84 "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.09/4.84 14.09/4.84 Machine: 14.09/4.84 14.09/4.84 "x86_64-pc-linux-gnu" 14.09/4.84 14.09/4.84 Type definitions: 14.09/4.84 14.09/4.84 Global variables: 14.09/4.84 14.09/4.84 Function declarations and definitions: 14.09/4.84 14.09/4.84 *BasicFunctionTypename: "__VERIFIER_nondet_int" returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 14.09/4.84 *BasicFunctionTypename: "test_fun" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: (x i32, y i32) variableLength: false visibilityType: DEFAULT callingConvention: ccc 14.09/4.84 0: 14.09/4.84 %1 = alloca i32, align 4 14.09/4.84 %2 = alloca i32, align 4 14.09/4.84 %c = alloca i32, align 4 14.09/4.84 store %x, %1 14.09/4.84 store %y, %2 14.09/4.84 store 0, %c 14.09/4.84 br %3 14.09/4.84 3: 14.09/4.84 %4 = load %1 14.09/4.84 %5 = load %2 14.09/4.84 %6 = icmp sgt %4 %5 14.09/4.84 br %6, %7, %14 14.09/4.84 7: 14.09/4.84 %8 = load %1 14.09/4.84 %9 = add %8 1 14.09/4.84 store %9, %1 14.09/4.84 %10 = load %2 14.09/4.84 %11 = add %10 2 14.09/4.84 store %11, %2 14.09/4.84 %12 = load %c 14.09/4.84 %13 = add %12 1 14.09/4.84 store %13, %c 14.09/4.84 br %3 14.09/4.84 14: 14.09/4.84 %15 = load %c 14.09/4.84 ret %15 14.09/4.84 14.09/4.84 *BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 14.09/4.84 0: 14.09/4.84 %1 = alloca i32, align 4 14.09/4.84 store 0, %1 14.09/4.84 %2 = call i32 @__VERIFIER_nondet_int() 14.09/4.84 %3 = call i32 @__VERIFIER_nondet_int() 14.09/4.84 %4 = call i32 @test_fun(i32 %2, i32 %3) 14.09/4.84 ret %4 14.09/4.84 14.09/4.84 14.09/4.84 Analyze Termination of all function calls matching the pattern: 14.09/4.84 main() 14.09/4.84 ---------------------------------------- 14.09/4.84 14.09/4.84 (3) LLVMToTerminationGraphProof (EQUIVALENT) 14.09/4.84 Constructed symbolic execution graph for LLVM program and proved memory safety. 14.09/4.84 ---------------------------------------- 14.09/4.84 14.09/4.84 (4) 14.09/4.84 Obligation: 14.09/4.84 SE Graph 14.09/4.84 ---------------------------------------- 14.09/4.84 14.09/4.84 (5) SymbolicExecutionGraphToSCCProof (SOUND) 14.09/4.84 Splitted symbolic execution graph to 1 SCC. 14.09/4.84 ---------------------------------------- 14.09/4.84 14.09/4.84 (6) 14.09/4.84 Obligation: 14.09/4.84 SCC 14.09/4.84 ---------------------------------------- 14.09/4.84 14.09/4.84 (7) SCC2IRS (SOUND) 14.09/4.84 Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 14.09/4.84 Generated rules. Obtained 16 rulesP rules: 14.09/4.84 f_229(v117, v118, v119, v120, v121, v125, v123, 1, v122, v126, v127, v128, v129, v130, v131, v132, v133, 0, 3, 2, 4) -> f_230(v117, v118, v119, v120, v121, v125, v126, 1, v122, v123, v127, v128, v129, v130, v131, v132, v133, 0, 3, 2, 4) :|: 0 = 0 14.09/4.84 f_230(v117, v118, v119, v120, v121, v125, v126, 1, v122, v123, v127, v128, v129, v130, v131, v132, v133, 0, 3, 2, 4) -> f_231(v117, v118, v119, v120, v121, v125, v126, 1, v122, v123, v127, v128, v129, v130, v131, v132, v133, 0, 3, 2, 4) :|: v126 < v125 14.09/4.84 f_231(v117, v118, v119, v120, v121, v125, v126, 1, v122, v123, v127, v128, v129, v130, v131, v132, v133, 0, 3, 2, 4) -> f_233(v117, v118, v119, v120, v121, v125, v126, 1, v122, v123, v127, v128, v129, v130, v131, v132, v133, 0, 3, 2, 4) :|: 0 = 0 14.09/4.84 f_233(v117, v118, v119, v120, v121, v125, v126, 1, v122, v123, v127, v128, v129, v130, v131, v132, v133, 0, 3, 2, 4) -> f_235(v117, v118, v119, v120, v121, v125, v126, 1, v122, v123, v127, v128, v129, v130, v131, v132, v133, 0, 3, 2, 4) :|: TRUE 14.09/4.84 f_235(v117, v118, v119, v120, v121, v125, v126, 1, v122, v123, v127, v128, v129, v130, v131, v132, v133, 0, 3, 2, 4) -> f_237(v117, v118, v119, v120, v121, v125, v126, 1, v123, v127, v128, v129, v130, v131, v132, v133, 0, 3, 2, 4) :|: 0 = 0 14.09/4.84 f_237(v117, v118, v119, v120, v121, v125, v126, 1, v123, v127, v128, v129, v130, v131, v132, v133, 0, 3, 2, 4) -> f_239(v117, v118, v119, v120, v121, v125, v126, 1, v135, v123, v127, v128, v129, v130, v131, v132, v133, 0, 3, 2, 4) :|: v135 = 1 + v125 14.09/4.84 f_239(v117, v118, v119, v120, v121, v125, v126, 1, v135, v123, v127, v128, v129, v130, v131, v132, v133, 0, 3, 2, 4) -> f_241(v117, v118, v119, v120, v121, v125, v126, 1, v135, v123, v127, v128, v129, v130, v131, v132, v133, 0, 3, 2, 4) :|: TRUE 14.09/4.84 f_241(v117, v118, v119, v120, v121, v125, v126, 1, v135, v123, v127, v128, v129, v130, v131, v132, v133, 0, 3, 2, 4) -> f_242(v117, v118, v119, v120, v121, v125, v126, 1, v135, v127, v128, v129, v130, v131, v132, v133, 0, 3, 4) :|: 0 = 0 14.09/4.84 f_242(v117, v118, v119, v120, v121, v125, v126, 1, v135, v127, v128, v129, v130, v131, v132, v133, 0, 3, 4) -> f_243(v117, v118, v119, v120, v121, v125, v126, 1, v135, v137, v127, v128, v129, v130, v131, v132, v133, 0, 3, 2, 4) :|: v137 = 2 + v126 14.09/4.84 f_243(v117, v118, v119, v120, v121, v125, v126, 1, v135, v137, v127, v128, v129, v130, v131, v132, v133, 0, 3, 2, 4) -> f_244(v117, v118, v119, v120, v121, v125, v126, 1, v135, v137, v127, v128, v129, v130, v131, v132, v133, 0, 3, 2, 4) :|: TRUE 14.09/4.84 f_244(v117, v118, v119, v120, v121, v125, v126, 1, v135, v137, v127, v128, v129, v130, v131, v132, v133, 0, 3, 2, 4) -> f_245(v117, v118, v119, v120, v121, v125, v126, 1, v135, v137, v128, v129, v130, v131, v132, v133, 0, 3, 2, 4) :|: 0 = 0 14.09/4.84 f_245(v117, v118, v119, v120, v121, v125, v126, 1, v135, v137, v128, v129, v130, v131, v132, v133, 0, 3, 2, 4) -> f_246(v117, v118, v119, v120, v121, v125, v126, 1, v135, v137, v128, v139, v129, v130, v131, v132, v133, 0, 3, 2, 4) :|: v139 = 1 + v128 && 2 <= v139 14.09/4.84 f_246(v117, v118, v119, v120, v121, v125, v126, 1, v135, v137, v128, v139, v129, v130, v131, v132, v133, 0, 3, 2, 4) -> f_247(v117, v118, v119, v120, v121, v125, v126, 1, v135, v137, v128, v139, v129, v130, v131, v132, v133, 0, 3, 2, 4) :|: TRUE 14.09/4.84 f_247(v117, v118, v119, v120, v121, v125, v126, 1, v135, v137, v128, v139, v129, v130, v131, v132, v133, 0, 3, 2, 4) -> f_248(v117, v118, v119, v120, v121, v125, v126, 1, v135, v137, v128, v139, v129, v130, v131, v132, v133, 0, 3, 2, 4) :|: TRUE 14.09/4.84 f_248(v117, v118, v119, v120, v121, v125, v126, 1, v135, v137, v128, v139, v129, v130, v131, v132, v133, 0, 3, 2, 4) -> f_228(v117, v118, v119, v120, v121, v125, v126, 1, v135, v137, v128, v139, v129, v130, v131, v132, v133, 0, 3, 2, 4) :|: TRUE 14.09/4.84 f_228(v117, v118, v119, v120, v121, v122, v123, 1, v125, v126, v127, v128, v129, v130, v131, v132, v133, 0, 3, 2, 4) -> f_229(v117, v118, v119, v120, v121, v125, v123, 1, v122, v126, v127, v128, v129, v130, v131, v132, v133, 0, 3, 2, 4) :|: 0 = 0 14.09/4.84 Combined rules. Obtained 1 rulesP rules: 14.09/4.84 f_229(v117:0, v118:0, v119:0, v120:0, v121:0, v125:0, v123:0, 1, v122:0, v126:0, v127:0, v128:0, v129:0, v130:0, v131:0, v132:0, v133:0, 0, 3, 2, 4) -> f_229(v117:0, v118:0, v119:0, v120:0, v121:0, 1 + v125:0, v126:0, 1, v125:0, 2 + v126:0, v128:0, 1 + v128:0, v129:0, v130:0, v131:0, v132:0, v133:0, 0, 3, 2, 4) :|: v128:0 > 0 && v126:0 < v125:0 14.09/4.84 Filtered unneeded arguments: 14.09/4.84 f_229(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19, x20, x21) -> f_229(x6, x10, x12) 14.09/4.84 Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules: 14.09/4.84 f_229(v125:0, v126:0, v128:0) -> f_229(1 + v125:0, 2 + v126:0, 1 + v128:0) :|: v128:0 > 0 && v126:0 < v125:0 14.09/4.84 14.09/4.84 ---------------------------------------- 14.09/4.84 14.09/4.84 (8) 14.09/4.84 Obligation: 14.09/4.84 Rules: 14.09/4.84 f_229(v125:0, v126:0, v128:0) -> f_229(1 + v125:0, 2 + v126:0, 1 + v128:0) :|: v128:0 > 0 && v126:0 < v125:0 14.09/4.84 14.09/4.84 ---------------------------------------- 14.09/4.84 14.09/4.84 (9) RankingReductionPairProof (EQUIVALENT) 14.09/4.84 Interpretation: 14.09/4.84 [ f_229 ] = -1*f_229_2 + f_229_1 14.09/4.84 14.09/4.84 The following rules are decreasing: 14.09/4.84 f_229(v125:0, v126:0, v128:0) -> f_229(1 + v125:0, 2 + v126:0, 1 + v128:0) :|: v128:0 > 0 && v126:0 < v125:0 14.09/4.84 14.09/4.84 The following rules are bounded: 14.09/4.84 f_229(v125:0, v126:0, v128:0) -> f_229(1 + v125:0, 2 + v126:0, 1 + v128:0) :|: v128:0 > 0 && v126:0 < v125:0 14.09/4.84 14.09/4.84 14.09/4.84 ---------------------------------------- 14.09/4.84 14.09/4.84 (10) 14.09/4.84 YES 14.49/5.00 EOF