9.04/3.38 YES 9.26/3.43 proof of /export/starexec/sandbox/benchmark/theBenchmark.c 9.26/3.43 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 9.26/3.43 9.26/3.43 9.26/3.43 Termination of the given C Problem could be proven: 9.26/3.43 9.26/3.43 (0) C Problem 9.26/3.43 (1) CToLLVMProof [EQUIVALENT, 174 ms] 9.26/3.43 (2) LLVM problem 9.26/3.43 (3) LLVMToTerminationGraphProof [EQUIVALENT, 686 ms] 9.26/3.43 (4) LLVM Symbolic Execution Graph 9.26/3.43 (5) SymbolicExecutionGraphToSCCProof [SOUND, 0 ms] 9.26/3.43 (6) LLVM Symbolic Execution SCC 9.26/3.43 (7) SCC2IRS [SOUND, 74 ms] 9.26/3.43 (8) IntTRS 9.26/3.43 (9) IntTRSCompressionProof [EQUIVALENT, 0 ms] 9.26/3.43 (10) IntTRS 9.26/3.43 (11) RankingReductionPairProof [EQUIVALENT, 29 ms] 9.26/3.43 (12) YES 9.26/3.43 9.26/3.43 9.26/3.43 ---------------------------------------- 9.26/3.43 9.26/3.43 (0) 9.26/3.43 Obligation: 9.26/3.43 c file /export/starexec/sandbox/benchmark/theBenchmark.c 9.26/3.43 ---------------------------------------- 9.26/3.43 9.26/3.43 (1) CToLLVMProof (EQUIVALENT) 9.26/3.43 Compiled c-file /export/starexec/sandbox/benchmark/theBenchmark.c to LLVM. 9.26/3.43 ---------------------------------------- 9.26/3.43 9.26/3.43 (2) 9.26/3.43 Obligation: 9.26/3.43 LLVM Problem 9.26/3.43 9.26/3.43 Aliases: 9.26/3.43 9.26/3.43 Data layout: 9.26/3.43 9.26/3.43 "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" 9.26/3.43 9.26/3.43 Machine: 9.26/3.43 9.26/3.43 "x86_64-pc-linux-gnu" 9.26/3.43 9.26/3.43 Type definitions: 9.26/3.43 9.26/3.43 Global variables: 9.26/3.43 9.26/3.43 Function declarations and definitions: 9.26/3.43 9.26/3.43 *BasicFunctionTypename: "__VERIFIER_nondet_int" returnParam: i32 parameters: () variableLength: true visibilityType: DEFAULT callingConvention: ccc 9.26/3.43 *BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 9.26/3.43 0: 9.26/3.43 %1 = alloca i32, align 4 9.26/3.43 %x = alloca i32, align 4 9.26/3.43 %old_x = alloca i32, align 4 9.26/3.43 store 0, %1 9.26/3.43 %2 = call i32 (...)* @__VERIFIER_nondet_int() 9.26/3.43 store %2, %x 9.26/3.43 br %3 9.26/3.43 3: 9.26/3.43 %4 = load %x 9.26/3.43 %5 = icmp sgt %4 0 9.26/3.43 br %5, %6, %9 9.26/3.43 6: 9.26/3.43 %7 = load %x 9.26/3.43 %8 = icmp slt %7 100 9.26/3.43 br %9 9.26/3.43 9: 9.26/3.43 %10 = phi [0, %3], [%8, %6] 9.26/3.43 br %10, %11, %21 9.26/3.43 11: 9.26/3.43 %12 = load %x 9.26/3.43 store %12, %old_x 9.26/3.43 %13 = call i32 (...)* @__VERIFIER_nondet_int() 9.26/3.43 store %13, %x 9.26/3.43 %14 = load %x 9.26/3.43 %15 = load %old_x 9.26/3.43 %16 = mul 2 %15 9.26/3.43 %17 = add %16 10 9.26/3.43 %18 = icmp slt %14 %17 9.26/3.43 br %18, %19, %20 9.26/3.43 19: 9.26/3.43 br %21 9.26/3.43 20: 9.26/3.43 br %3 9.26/3.43 21: 9.26/3.43 ret 0 9.26/3.43 9.26/3.43 9.26/3.43 Analyze Termination of all function calls matching the pattern: 9.26/3.43 main() 9.26/3.43 ---------------------------------------- 9.26/3.43 9.26/3.43 (3) LLVMToTerminationGraphProof (EQUIVALENT) 9.26/3.43 Constructed symbolic execution graph for LLVM program and proved memory safety. 9.26/3.43 ---------------------------------------- 9.26/3.43 9.26/3.43 (4) 9.26/3.43 Obligation: 9.26/3.43 SE Graph 9.26/3.43 ---------------------------------------- 9.26/3.43 9.26/3.43 (5) SymbolicExecutionGraphToSCCProof (SOUND) 9.26/3.43 Splitted symbolic execution graph to 1 SCC. 9.26/3.43 ---------------------------------------- 9.26/3.43 9.26/3.43 (6) 9.26/3.43 Obligation: 9.26/3.43 SCC 9.26/3.43 ---------------------------------------- 9.26/3.43 9.26/3.43 (7) SCC2IRS (SOUND) 9.26/3.43 Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 9.26/3.43 Generated rules. Obtained 21 rulesP rules: 9.26/3.43 f_157(v75, v76, v77, v78, v81, 1, v79, v82, v83, 0, v85, v86, v87, 3, 2, 10, 99, 12, 198, 208, 4) -> f_158(v75, v76, v77, v78, v81, 1, v79, v82, v83, 0, v85, v86, v87, 3, 2, 10, 99, 12, 198, 208, 4) :|: 0 = 0 9.26/3.43 f_158(v75, v76, v77, v78, v81, 1, v79, v82, v83, 0, v85, v86, v87, 3, 2, 10, 99, 12, 198, 208, 4) -> f_159(v75, v76, v77, v78, v81, 1, v79, v82, v83, 0, v85, v86, v87, 3, 2, 10, 99, 12, 198, 208, 4) :|: TRUE 9.26/3.43 f_159(v75, v76, v77, v78, v81, 1, v79, v82, v83, 0, v85, v86, v87, 3, 2, 10, 99, 12, 198, 208, 4) -> f_160(v75, v76, v77, v78, v81, 1, v79, v82, v83, 0, v85, v86, v87, 3, 2, 10, 99, 12, 198, 208, 4) :|: 0 = 0 9.26/3.43 f_160(v75, v76, v77, v78, v81, 1, v79, v82, v83, 0, v85, v86, v87, 3, 2, 10, 99, 12, 198, 208, 4) -> f_161(v75, v76, v77, v78, v81, 1, v79, v82, v83, 0, v85, v86, v87, 3, 2, 10, 99, 44, 12, 88, 98, 4) :|: v81 < 100 && v83 <= 98 && 2 <= v82 && v82 <= 88 && 1 <= v79 && v79 <= 44 9.26/3.43 f_161(v75, v76, v77, v78, v81, 1, v79, v82, v83, 0, v85, v86, v87, 3, 2, 10, 99, 44, 12, 88, 98, 4) -> f_163(v75, v76, v77, v78, v81, 1, v79, v82, v83, 0, v85, v86, v87, 3, 2, 10, 99, 44, 12, 88, 98, 4) :|: 0 = 0 9.26/3.43 f_163(v75, v76, v77, v78, v81, 1, v79, v82, v83, 0, v85, v86, v87, 3, 2, 10, 99, 44, 12, 88, 98, 4) -> f_165(v75, v76, v77, v78, v81, 1, v79, v82, v83, 0, v85, v86, v87, 3, 2, 10, 99, 44, 12, 88, 98, 4) :|: 0 = 0 9.26/3.43 f_165(v75, v76, v77, v78, v81, 1, v79, v82, v83, 0, v85, v86, v87, 3, 2, 10, 99, 44, 12, 88, 98, 4) -> f_167(v75, v76, v77, v78, v81, 1, v79, v82, v83, 0, v85, v86, v87, 3, 2, 10, 99, 44, 12, 88, 98, 4) :|: TRUE 9.26/3.43 f_167(v75, v76, v77, v78, v81, 1, v79, v82, v83, 0, v85, v86, v87, 3, 2, 10, 99, 44, 12, 88, 98, 4) -> f_169(v75, v76, v77, v78, v81, 1, v79, v82, v83, 0, v85, v86, v87, 3, 2, 10, 99, 44, 12, 88, 98, 4) :|: 0 = 0 9.26/3.43 f_169(v75, v76, v77, v78, v81, 1, v79, v82, v83, 0, v85, v86, v87, 3, 2, 10, 99, 44, 12, 88, 98, 4) -> f_170(v75, v76, v77, v78, v81, 1, v79, v82, v83, 0, v85, v86, v87, 3, 2, 10, 99, 44, 12, 88, 98, 4) :|: TRUE 9.26/3.43 f_170(v75, v76, v77, v78, v81, 1, v79, v82, v83, 0, v85, v86, v87, 3, 2, 10, 99, 44, 12, 88, 98, 4) -> f_171(v75, v76, v77, v78, v81, 1, v115, v79, v82, v83, 0, v85, v86, v87, 3, 2, 10, 99, 44, 12, 88, 98, 4) :|: TRUE 9.26/3.43 f_171(v75, v76, v77, v78, v81, 1, v115, v79, v82, v83, 0, v85, v86, v87, 3, 2, 10, 99, 44, 12, 88, 98, 4) -> f_172(v75, v76, v77, v78, v81, 1, v115, v79, v82, v83, 0, v85, v86, v87, 3, 2, 10, 99, 44, 12, 88, 98, 4) :|: TRUE 9.26/3.43 f_172(v75, v76, v77, v78, v81, 1, v115, v79, v82, v83, 0, v85, v86, v87, 3, 2, 10, 99, 44, 12, 88, 98, 4) -> f_173(v75, v76, v77, v78, v81, 1, v115, v79, v82, v83, 0, v85, v86, v87, 3, 2, 10, 99, 44, 12, 88, 98, 4) :|: 0 = 0 9.26/3.43 f_173(v75, v76, v77, v78, v81, 1, v115, v79, v82, v83, 0, v85, v86, v87, 3, 2, 10, 99, 44, 12, 88, 98, 4) -> f_174(v75, v76, v77, v78, v81, 1, v115, v82, v83, 0, v85, v86, v87, 3, 10, 99, 12, 2, 88, 98, 4) :|: 0 = 0 9.26/3.43 f_174(v75, v76, v77, v78, v81, 1, v115, v82, v83, 0, v85, v86, v87, 3, 10, 99, 12, 2, 88, 98, 4) -> f_175(v75, v76, v77, v78, v81, 1, v115, v117, v83, 0, v85, v86, v87, 3, 2, 99, 12, 98, 4, 24, 198) :|: v117 = 2 * v81 && 24 <= v117 && v117 <= 198 9.26/3.43 f_175(v75, v76, v77, v78, v81, 1, v115, v117, v83, 0, v85, v86, v87, 3, 2, 99, 12, 98, 4, 24, 198) -> f_176(v75, v76, v77, v78, v81, 1, v115, v117, v118, 0, v85, v86, v87, 3, 2, 10, 99, 12, 4, 24, 198, 34, 208) :|: v118 = 10 + v117 && 34 <= v118 && v118 <= 208 9.26/3.43 f_176(v75, v76, v77, v78, v81, 1, v115, v117, v118, 0, v85, v86, v87, 3, 2, 10, 99, 12, 4, 24, 198, 34, 208) -> f_178(v75, v76, v77, v78, v81, 1, v115, v117, v118, 0, v85, v86, v87, 3, 2, 10, 99, 12, 4, 34, 24, 198, 208) :|: v118 <= v115 && 34 <= v115 9.26/3.43 f_178(v75, v76, v77, v78, v81, 1, v115, v117, v118, 0, v85, v86, v87, 3, 2, 10, 99, 12, 4, 34, 24, 198, 208) -> f_180(v75, v76, v77, v78, v81, 1, v115, v117, v118, 0, v85, v86, v87, 3, 2, 10, 99, 12, 4, 34, 24, 198, 208) :|: 0 = 0 9.26/3.43 f_180(v75, v76, v77, v78, v81, 1, v115, v117, v118, 0, v85, v86, v87, 3, 2, 10, 99, 12, 4, 34, 24, 198, 208) -> f_182(v75, v76, v77, v78, v81, 1, v115, v117, v118, 0, v85, v86, v87, 3, 2, 10, 99, 12, 4, 34, 24, 198, 208) :|: TRUE 9.26/3.43 f_182(v75, v76, v77, v78, v81, 1, v115, v117, v118, 0, v85, v86, v87, 3, 2, 10, 99, 12, 4, 34, 24, 198, 208) -> f_184(v75, v76, v77, v78, v81, 1, v115, v117, v118, 0, v85, v86, v87, 3, 2, 10, 99, 12, 4, 34, 24, 198, 208) :|: TRUE 9.26/3.43 f_184(v75, v76, v77, v78, v81, 1, v115, v117, v118, 0, v85, v86, v87, 3, 2, 10, 99, 12, 4, 34, 24, 198, 208) -> f_156(v75, v76, v77, v78, v81, 1, v115, v117, v118, 0, v85, v86, v87, 3, 2, 10, 99, 12, 198, 208, 4) :|: TRUE 9.26/3.43 f_156(v75, v76, v77, v78, v79, 1, v81, v82, v83, 0, v85, v86, v87, 3, 2, 10, 99, 12, 198, 208, 4) -> f_157(v75, v76, v77, v78, v81, 1, v79, v82, v83, 0, v85, v86, v87, 3, 2, 10, 99, 12, 198, 208, 4) :|: 0 = 0 9.26/3.43 Combined rules. Obtained 1 rulesP rules: 9.26/3.43 f_157(v75:0, v76:0, v77:0, v78:0, v81:0, 1, v79:0, v82:0, v83:0, 0, v85:0, v86:0, v87:0, 3, 2, 10, 99, 12, 198, 208, 4) -> f_157(v75:0, v76:0, v77:0, v78:0, v115:0, 1, v81:0, 2 * v81:0, 10 + 2 * v81:0, 0, v85:0, v86:0, v87:0, 3, 2, 10, 99, 12, 198, 208, 4) :|: v83:0 < 99 && v81:0 < 100 && v82:0 > 1 && v82:0 < 89 && v79:0 > 0 && v79:0 < 45 && 23 < 2 * v81:0 && 2 * v81:0 < 199 && v115:0 >= 10 + 2 * v81:0 && v115:0 > 33 9.26/3.43 Filtered unneeded arguments: 9.26/3.43 f_157(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19, x20, x21) -> f_157(x5, x7, x8, x9) 9.26/3.43 Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules: 9.26/3.43 f_157(v81:0, v79:0, v82:0, v83:0) -> f_157(v115:0, v81:0, 2 * v81:0, 10 + 2 * v81:0) :|: v81:0 < 100 && v83:0 < 99 && v82:0 > 1 && v82:0 < 89 && v79:0 > 0 && v79:0 < 45 && 23 < 2 * v81:0 && 2 * v81:0 < 199 && v115:0 > 33 && v115:0 >= 10 + 2 * v81:0 9.26/3.43 9.26/3.43 ---------------------------------------- 9.26/3.43 9.26/3.43 (8) 9.26/3.43 Obligation: 9.26/3.43 Rules: 9.26/3.43 f_157(v81:0, v79:0, v82:0, v83:0) -> f_157(v115:0, v81:0, 2 * v81:0, 10 + 2 * v81:0) :|: v81:0 < 100 && v83:0 < 99 && v82:0 > 1 && v82:0 < 89 && v79:0 > 0 && v79:0 < 45 && 23 < 2 * v81:0 && 2 * v81:0 < 199 && v115:0 > 33 && v115:0 >= 10 + 2 * v81:0 9.26/3.43 9.26/3.43 ---------------------------------------- 9.26/3.43 9.26/3.43 (9) IntTRSCompressionProof (EQUIVALENT) 9.26/3.43 Compressed rules. 9.26/3.43 ---------------------------------------- 9.26/3.43 9.26/3.43 (10) 9.26/3.43 Obligation: 9.26/3.43 Rules: 9.26/3.43 f_157(v81:0:0, v79:0:0, v82:0:0, v83:0:0) -> f_157(v115:0:0, v81:0:0, 2 * v81:0:0, 10 + 2 * v81:0:0) :|: v115:0:0 > 33 && v115:0:0 >= 10 + 2 * v81:0:0 && 2 * v81:0:0 < 199 && 23 < 2 * v81:0:0 && v79:0:0 < 45 && v79:0:0 > 0 && v82:0:0 < 89 && v82:0:0 > 1 && v83:0:0 < 99 && v81:0:0 < 100 9.26/3.43 9.26/3.43 ---------------------------------------- 9.26/3.43 9.26/3.43 (11) RankingReductionPairProof (EQUIVALENT) 9.26/3.43 Interpretation: 9.26/3.43 [ f_157 ] = -1/11*f_157_1 + 1/11*f_157_2 9.26/3.43 9.26/3.43 The following rules are decreasing: 9.26/3.43 f_157(v81:0:0, v79:0:0, v82:0:0, v83:0:0) -> f_157(v115:0:0, v81:0:0, 2 * v81:0:0, 10 + 2 * v81:0:0) :|: v115:0:0 > 33 && v115:0:0 >= 10 + 2 * v81:0:0 && 2 * v81:0:0 < 199 && 23 < 2 * v81:0:0 && v79:0:0 < 45 && v79:0:0 > 0 && v82:0:0 < 89 && v82:0:0 > 1 && v83:0:0 < 99 && v81:0:0 < 100 9.26/3.43 9.26/3.43 The following rules are bounded: 9.26/3.43 f_157(v81:0:0, v79:0:0, v82:0:0, v83:0:0) -> f_157(v115:0:0, v81:0:0, 2 * v81:0:0, 10 + 2 * v81:0:0) :|: v115:0:0 > 33 && v115:0:0 >= 10 + 2 * v81:0:0 && 2 * v81:0:0 < 199 && 23 < 2 * v81:0:0 && v79:0:0 < 45 && v79:0:0 > 0 && v82:0:0 < 89 && v82:0:0 > 1 && v83:0:0 < 99 && v81:0:0 < 100 9.26/3.43 9.26/3.43 9.26/3.43 ---------------------------------------- 9.26/3.43 9.26/3.43 (12) 9.26/3.43 YES 9.26/3.46 EOF