/export/starexec/sandbox/solver/bin/starexec_run_c /export/starexec/sandbox/benchmark/theBenchmark.c /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox/benchmark/theBenchmark.c # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Termination of the given C Problem could be proven: (0) C Problem (1) CToLLVMProof [EQUIVALENT, 178 ms] (2) LLVM problem (3) LLVMToTerminationGraphProof [EQUIVALENT, 789 ms] (4) LLVM Symbolic Execution Graph (5) SymbolicExecutionGraphToSCCProof [SOUND, 0 ms] (6) LLVM Symbolic Execution SCC (7) SCC2IRS [SOUND, 75 ms] (8) IntTRS (9) IntTRSCompressionProof [EQUIVALENT, 0 ms] (10) IntTRS (11) RankingReductionPairProof [EQUIVALENT, 21 ms] (12) YES ---------------------------------------- (0) Obligation: c file /export/starexec/sandbox/benchmark/theBenchmark.c ---------------------------------------- (1) CToLLVMProof (EQUIVALENT) Compiled c-file /export/starexec/sandbox/benchmark/theBenchmark.c to LLVM. ---------------------------------------- (2) Obligation: LLVM Problem Aliases: Data layout: "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" Machine: "x86_64-pc-linux-gnu" Type definitions: Global variables: Function declarations and definitions: *BasicFunctionTypename: "__VERIFIER_nondet_int" returnParam: i32 parameters: () variableLength: true visibilityType: DEFAULT callingConvention: ccc *BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 0: %1 = alloca i32, align 4 %x = alloca i32, align 4 %old_x = alloca i32, align 4 store 0, %1 %2 = call i32 (...)* @__VERIFIER_nondet_int() store %2, %x br %3 3: %4 = load %x %5 = icmp sgt %4 0 br %5, %6, %9 6: %7 = load %x %8 = icmp slt %7 100 br %9 9: %10 = phi [0, %3], [%8, %6] br %10, %11, %21 11: %12 = load %x store %12, %old_x %13 = call i32 (...)* @__VERIFIER_nondet_int() store %13, %x %14 = load %x %15 = load %old_x %16 = mul 2 %15 %17 = add %16 10 %18 = icmp slt %14 %17 br %18, %19, %20 19: br %21 20: br %3 21: ret 0 Analyze Termination of all function calls matching the pattern: main() ---------------------------------------- (3) LLVMToTerminationGraphProof (EQUIVALENT) Constructed symbolic execution graph for LLVM program and proved memory safety. ---------------------------------------- (4) Obligation: SE Graph ---------------------------------------- (5) SymbolicExecutionGraphToSCCProof (SOUND) Splitted symbolic execution graph to 1 SCC. ---------------------------------------- (6) Obligation: SCC ---------------------------------------- (7) SCC2IRS (SOUND) Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: Generated rules. Obtained 21 rulesP rules: 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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 Combined rules. Obtained 1 rulesP rules: 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 Filtered unneeded arguments: 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) Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules: 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 ---------------------------------------- (8) Obligation: Rules: 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) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (10) Obligation: Rules: 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 ---------------------------------------- (11) RankingReductionPairProof (EQUIVALENT) Interpretation: [ f_157 ] = -1/11*f_157_1 + 1/11*f_157_2 The following rules are decreasing: 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 The following rules are bounded: 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 ---------------------------------------- (12) YES