28.91/10.96 YES 30.03/10.97 proof of /export/starexec/sandbox/benchmark/theBenchmark.c 30.03/10.97 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 30.03/10.97 30.03/10.97 30.03/10.97 Termination of the given C Problem could be proven: 30.03/10.97 30.03/10.97 (0) C Problem 30.03/10.97 (1) CToLLVMProof [EQUIVALENT, 173 ms] 30.03/10.97 (2) LLVM problem 30.03/10.97 (3) LLVMToTerminationGraphProof [EQUIVALENT, 8376 ms] 30.03/10.97 (4) LLVM Symbolic Execution Graph 30.03/10.97 (5) SymbolicExecutionGraphToSCCProof [SOUND, 0 ms] 30.03/10.97 (6) LLVM Symbolic Execution SCC 30.03/10.97 (7) SCC2IRS [SOUND, 93 ms] 30.03/10.97 (8) IntTRS 30.03/10.97 (9) IntTRSCompressionProof [EQUIVALENT, 0 ms] 30.03/10.97 (10) IntTRS 30.03/10.97 (11) RankingReductionPairProof [EQUIVALENT, 15 ms] 30.03/10.97 (12) YES 30.03/10.97 30.03/10.97 30.03/10.97 ---------------------------------------- 30.03/10.97 30.03/10.97 (0) 30.03/10.97 Obligation: 30.03/10.97 c file /export/starexec/sandbox/benchmark/theBenchmark.c 30.03/10.97 ---------------------------------------- 30.03/10.97 30.03/10.97 (1) CToLLVMProof (EQUIVALENT) 30.03/10.97 Compiled c-file /export/starexec/sandbox/benchmark/theBenchmark.c to LLVM. 30.03/10.97 ---------------------------------------- 30.03/10.97 30.03/10.97 (2) 30.03/10.97 Obligation: 30.03/10.97 LLVM Problem 30.03/10.97 30.03/10.97 Aliases: 30.03/10.97 30.03/10.97 Data layout: 30.03/10.97 30.03/10.97 "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" 30.03/10.98 30.03/10.98 Machine: 30.03/10.98 30.03/10.98 "x86_64-pc-linux-gnu" 30.03/10.98 30.03/10.98 Type definitions: 30.03/10.98 30.03/10.98 Global variables: 30.03/10.98 30.03/10.98 Function declarations and definitions: 30.03/10.98 30.03/10.98 *BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 30.03/10.98 0: 30.03/10.98 %1 = alloca i32, align 4 30.03/10.98 %i = alloca *i32, align 8 30.03/10.98 %j = alloca *i32, align 8 30.03/10.98 store 0, %1 30.03/10.98 %2 = alloca i8, numElementsLit: 4 30.03/10.98 %3 = bitcast *i8 %2 to *i32 30.03/10.98 store %3, %i 30.03/10.98 %4 = alloca i8, numElementsLit: 4 30.03/10.98 %5 = bitcast *i8 %4 to *i32 30.03/10.98 store %5, %j 30.03/10.98 %6 = load %j 30.03/10.98 store 1, %6 30.03/10.98 %7 = load %i 30.03/10.98 store 10000, %7 30.03/10.98 br %8 30.03/10.98 8: 30.03/10.98 %9 = load %i 30.03/10.98 %10 = load %9 30.03/10.98 %11 = load %j 30.03/10.98 %12 = load %11 30.03/10.98 %13 = sub %10 %12 30.03/10.98 %14 = icmp sge %13 1 30.03/10.98 br %14, %15, %23 30.03/10.98 15: 30.03/10.98 %16 = load %j 30.03/10.98 %17 = load %16 30.03/10.98 %18 = add %17 1 30.03/10.98 store %18, %16 30.03/10.98 br %19 30.03/10.98 19: 30.03/10.98 %20 = load %i 30.03/10.98 %21 = load %20 30.03/10.98 %22 = add %21 -1 30.03/10.98 store %22, %20 30.03/10.98 br %8 30.03/10.98 23: 30.03/10.98 %24 = load %1 30.03/10.98 ret %24 30.03/10.98 30.03/10.98 30.03/10.98 Analyze Termination of all function calls matching the pattern: 30.03/10.98 main() 30.03/10.98 ---------------------------------------- 30.03/10.98 30.03/10.98 (3) LLVMToTerminationGraphProof (EQUIVALENT) 30.03/10.98 Constructed symbolic execution graph for LLVM program and proved memory safety. 30.03/10.98 ---------------------------------------- 30.03/10.98 30.03/10.98 (4) 30.03/10.98 Obligation: 30.03/10.98 SE Graph 30.03/10.98 ---------------------------------------- 30.03/10.98 30.03/10.98 (5) SymbolicExecutionGraphToSCCProof (SOUND) 30.03/10.98 Splitted symbolic execution graph to 1 SCC. 30.03/10.98 ---------------------------------------- 30.03/10.98 30.03/10.98 (6) 30.03/10.98 Obligation: 30.03/10.98 SCC 30.03/10.98 ---------------------------------------- 30.03/10.98 30.03/10.98 (7) SCC2IRS (SOUND) 30.03/10.98 Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 30.03/10.98 Generated rules. Obtained 19 rulesP rules: 30.03/10.98 f_260(v123, v124, v125, v126, v127, v128, v129, v130, 1, v132, v133, v134, v135, v136, v137, v138, 0, 3, 7, 2, 10000, 9999, 4, 8) -> f_261(v123, v124, v125, v126, v127, v133, v129, v130, 1, v132, v128, v134, v135, v136, v137, v138, 0, 3, 7, 2, 10000, 9999, 4, 8) :|: 0 = 0 30.03/10.98 f_261(v123, v124, v125, v126, v127, v133, v129, v130, 1, v132, v128, v134, v135, v136, v137, v138, 0, 3, 7, 2, 10000, 9999, 4, 8) -> f_262(v123, v124, v125, v126, v127, v133, v129, v130, 1, v132, v128, v134, v135, v136, v137, v138, 0, 3, 7, 2, 10000, 9999, 4, 8) :|: 0 = 0 30.03/10.98 f_262(v123, v124, v125, v126, v127, v133, v129, v130, 1, v132, v128, v134, v135, v136, v137, v138, 0, 3, 7, 2, 10000, 9999, 4, 8) -> f_263(v123, v124, v125, v126, v127, v133, v132, v130, 1, v129, v128, v134, v135, v136, v137, v138, 0, 3, 7, 2, 10000, 9999, 4, 8) :|: 0 = 0 30.03/10.98 f_263(v123, v124, v125, v126, v127, v133, v132, v130, 1, v129, v128, v134, v135, v136, v137, v138, 0, 3, 7, 2, 10000, 9999, 4, 8) -> f_264(v123, v124, v125, v126, v127, v133, v132, v140, 1, v129, v128, v134, v135, v136, v137, v138, 0, 3, 7, 2, 10000, 9999, 4, 8, 9997) :|: v140 + v132 = v133 && 0 <= 9999 + v140 && v140 <= 9997 30.03/10.98 f_264(v123, v124, v125, v126, v127, v133, v132, v140, 1, v129, v128, v134, v135, v136, v137, v138, 0, 3, 7, 2, 10000, 9999, 4, 8, 9997) -> f_265(v123, v124, v125, v126, v127, v133, v132, v140, 1, v129, v128, v134, v135, v136, v137, v138, 0, 3, 7, 4, 10000, 9997, 2, 9998, 9999, 8) :|: 1 <= v140 && v132 <= 9998 && 3 <= v133 && v129 <= 9997 && 4 <= v128 30.03/10.98 f_265(v123, v124, v125, v126, v127, v133, v132, v140, 1, v129, v128, v134, v135, v136, v137, v138, 0, 3, 7, 4, 10000, 9997, 2, 9998, 9999, 8) -> f_267(v123, v124, v125, v126, v127, v133, v132, v140, 1, v129, v128, v134, v135, v136, v137, v138, 0, 3, 7, 4, 10000, 9997, 2, 9998, 9999, 8) :|: 0 = 0 30.03/10.98 f_267(v123, v124, v125, v126, v127, v133, v132, v140, 1, v129, v128, v134, v135, v136, v137, v138, 0, 3, 7, 4, 10000, 9997, 2, 9998, 9999, 8) -> f_269(v123, v124, v125, v126, v127, v133, v132, v140, 1, v129, v128, v134, v135, v136, v137, v138, 0, 3, 7, 4, 10000, 9997, 2, 9998, 9999, 8) :|: TRUE 30.03/10.98 f_269(v123, v124, v125, v126, v127, v133, v132, v140, 1, v129, v128, v134, v135, v136, v137, v138, 0, 3, 7, 4, 10000, 9997, 2, 9998, 9999, 8) -> f_271(v123, v124, v125, v126, v127, v133, v132, v140, 1, v129, v128, v134, v135, v136, v137, v138, 0, 3, 7, 4, 10000, 9997, 2, 9998, 9999, 8) :|: 0 = 0 30.03/10.98 f_271(v123, v124, v125, v126, v127, v133, v132, v140, 1, v129, v128, v134, v135, v136, v137, v138, 0, 3, 7, 4, 10000, 9997, 2, 9998, 9999, 8) -> f_273(v123, v124, v125, v126, v127, v133, v132, v140, 1, v128, v134, v135, v136, v137, v138, 0, 3, 7, 4, 10000, 2, 9998, 9999, 8, 9997) :|: 0 = 0 30.03/10.98 f_273(v123, v124, v125, v126, v127, v133, v132, v140, 1, v128, v134, v135, v136, v137, v138, 0, 3, 7, 4, 10000, 2, 9998, 9999, 8, 9997) -> f_274(v123, v124, v125, v126, v127, v133, v132, v140, 1, v141, v128, v134, v135, v136, v137, v138, 0, 3, 7, 4, 10000, 2, 9998, 9999, 8, 9997) :|: v141 = 1 + v132 && 3 <= v141 && v141 <= 9999 30.03/10.98 f_274(v123, v124, v125, v126, v127, v133, v132, v140, 1, v141, v128, v134, v135, v136, v137, v138, 0, 3, 7, 4, 10000, 2, 9998, 9999, 8, 9997) -> f_275(v123, v124, v125, v126, v127, v133, v132, v140, 1, v141, v128, v134, v135, v136, v137, v138, 0, 3, 7, 4, 10000, 2, 9998, 9999, 8, 9997) :|: TRUE 30.03/10.98 f_275(v123, v124, v125, v126, v127, v133, v132, v140, 1, v141, v128, v134, v135, v136, v137, v138, 0, 3, 7, 4, 10000, 2, 9998, 9999, 8, 9997) -> f_276(v123, v124, v125, v126, v127, v133, v132, v140, 1, v141, v128, v134, v135, v136, v137, v138, 0, 3, 7, 4, 10000, 2, 9998, 9999, 8, 9997) :|: TRUE 30.03/10.98 f_276(v123, v124, v125, v126, v127, v133, v132, v140, 1, v141, v128, v134, v135, v136, v137, v138, 0, 3, 7, 4, 10000, 2, 9998, 9999, 8, 9997) -> f_277(v123, v124, v125, v126, v127, v133, v132, v140, 1, v141, v128, v134, v135, v136, v137, v138, 0, 3, 7, 4, 10000, 2, 9998, 9999, 8, 9997) :|: 0 = 0 30.03/10.98 f_277(v123, v124, v125, v126, v127, v133, v132, v140, 1, v141, v128, v134, v135, v136, v137, v138, 0, 3, 7, 4, 10000, 2, 9998, 9999, 8, 9997) -> f_278(v123, v124, v125, v126, v127, v133, v132, v140, 1, v141, v134, v135, v136, v137, v138, 0, 3, 7, 2, 9998, 9999, 4, 8, 9997) :|: 0 = 0 30.03/10.98 f_278(v123, v124, v125, v126, v127, v133, v132, v140, 1, v141, v134, v135, v136, v137, v138, 0, 3, 7, 2, 9998, 9999, 4, 8, 9997) -> f_279(v123, v124, v125, v126, v127, v133, v132, v140, 1, v141, v143, v134, v135, v136, v137, v138, 0, 3, 7, 2, 9998, 9999, 4, 8, 9997) :|: 1 + v143 = v133 && 2 <= v143 && v143 <= 9998 30.03/10.98 f_279(v123, v124, v125, v126, v127, v133, v132, v140, 1, v141, v143, v134, v135, v136, v137, v138, 0, 3, 7, 2, 9998, 9999, 4, 8, 9997) -> f_280(v123, v124, v125, v126, v127, v133, v132, v140, 1, v141, v143, v134, v135, v136, v137, v138, 0, 3, 7, 2, 9998, 9999, 4, 8, 9997) :|: TRUE 30.03/10.98 f_280(v123, v124, v125, v126, v127, v133, v132, v140, 1, v141, v143, v134, v135, v136, v137, v138, 0, 3, 7, 2, 9998, 9999, 4, 8, 9997) -> f_281(v123, v124, v125, v126, v127, v133, v132, v140, 1, v141, v143, v134, v135, v136, v137, v138, 0, 3, 7, 2, 9998, 9999, 4, 8, 9997) :|: TRUE 30.03/10.98 f_281(v123, v124, v125, v126, v127, v133, v132, v140, 1, v141, v143, v134, v135, v136, v137, v138, 0, 3, 7, 2, 9998, 9999, 4, 8, 9997) -> f_259(v123, v124, v125, v126, v127, v133, v132, v140, 1, v141, v143, v134, v135, v136, v137, v138, 0, 3, 7, 2, 10000, 9999, 4, 8) :|: TRUE 30.03/10.98 f_259(v123, v124, v125, v126, v127, v128, v129, v130, 1, v132, v133, v134, v135, v136, v137, v138, 0, 3, 7, 2, 10000, 9999, 4, 8) -> f_260(v123, v124, v125, v126, v127, v128, v129, v130, 1, v132, v133, v134, v135, v136, v137, v138, 0, 3, 7, 2, 10000, 9999, 4, 8) :|: 0 = 0 30.03/10.98 Combined rules. Obtained 1 rulesP rules: 30.03/10.98 f_260(v123:0, v124:0, v125:0, v126:0, v127:0, v128:0, v129:0, v130:0, 1, v132:0, 1 + v143:0, v134:0, v135:0, v136:0, v137:0, v138:0, 0, 3, 7, 2, 10000, 9999, 4, 8) -> f_260(v123:0, v124:0, v125:0, v126:0, v127:0, 1 + v143:0, v132:0, v140:0, 1, 1 + v132:0, v143:0, v134:0, v135:0, v136:0, v137:0, v138:0, 0, 3, 7, 2, 10000, 9999, 4, 8) :|: v140:0 > 0 && v132:0 < 9999 && v143:0 > 1 && v140:0 + v132:0 = 1 + v143:0 && v129:0 < 9998 && v140:0 < 9998 && v128:0 > 3 && v132:0 > 1 && v143:0 < 9999 30.03/10.98 Filtered unneeded arguments: 30.03/10.98 f_260(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19, x20, x21, x22, x23, x24) -> f_260(x6, x7, x10, x11) 30.03/10.98 Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules: 30.03/10.98 f_260(v128:0, v129:0, v132:0, sum~cons_1~v143:0) -> f_260(1 + v143:0, v132:0, 1 + v132:0, v143:0) :|: v143:0 > 1 && v132:0 < 9999 && v129:0 < 9998 && v128:0 > 3 && v143:0 < 9999 && v132:0 > 1 && sum~cons_1~v143:0 = 1 + v143:0 30.03/10.98 30.03/10.98 ---------------------------------------- 30.03/10.98 30.03/10.98 (8) 30.03/10.98 Obligation: 30.03/10.98 Rules: 30.03/10.98 f_260(v128:0, v129:0, v132:0, sum~cons_1~v143:0) -> f_260(1 + v143:0, v132:0, 1 + v132:0, v143:0) :|: v143:0 > 1 && v132:0 < 9999 && v129:0 < 9998 && v128:0 > 3 && v143:0 < 9999 && v132:0 > 1 && sum~cons_1~v143:0 = 1 + v143:0 30.03/10.98 30.03/10.98 ---------------------------------------- 30.03/10.98 30.03/10.98 (9) IntTRSCompressionProof (EQUIVALENT) 30.03/10.98 Compressed rules. 30.03/10.98 ---------------------------------------- 30.03/10.98 30.03/10.98 (10) 30.03/10.98 Obligation: 30.03/10.98 Rules: 30.03/10.98 f_260(v128:0:0, v129:0:0, v132:0:0, sum~cons_1~v143:0:0) -> f_260(1 + v143:0:0, v132:0:0, 1 + v132:0:0, v143:0:0) :|: v143:0:0 < 9999 && v132:0:0 > 1 && v128:0:0 > 3 && v129:0:0 < 9998 && v132:0:0 < 9999 && v143:0:0 > 1 && sum~cons_1~v143:0:0 = 1 + v143:0:0 30.03/10.98 30.03/10.98 ---------------------------------------- 30.03/10.98 30.03/10.98 (11) RankingReductionPairProof (EQUIVALENT) 30.03/10.98 Interpretation: 30.03/10.98 [ f_260 ] = f_260_4 30.03/10.98 30.03/10.98 The following rules are decreasing: 30.03/10.98 f_260(v128:0:0, v129:0:0, v132:0:0, sum~cons_1~v143:0:0) -> f_260(1 + v143:0:0, v132:0:0, 1 + v132:0:0, v143:0:0) :|: v143:0:0 < 9999 && v132:0:0 > 1 && v128:0:0 > 3 && v129:0:0 < 9998 && v132:0:0 < 9999 && v143:0:0 > 1 && sum~cons_1~v143:0:0 = 1 + v143:0:0 30.03/10.98 30.03/10.98 The following rules are bounded: 30.03/10.98 f_260(v128:0:0, v129:0:0, v132:0:0, sum~cons_1~v143:0:0) -> f_260(1 + v143:0:0, v132:0:0, 1 + v132:0:0, v143:0:0) :|: v143:0:0 < 9999 && v132:0:0 > 1 && v128:0:0 > 3 && v129:0:0 < 9998 && v132:0:0 < 9999 && v143:0:0 > 1 && sum~cons_1~v143:0:0 = 1 + v143:0:0 30.03/10.98 30.03/10.98 30.03/10.98 ---------------------------------------- 30.03/10.98 30.03/10.98 (12) 30.03/10.98 YES 30.09/11.01 EOF