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