/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, 3296 ms] (4) LLVM Symbolic Execution Graph (5) SymbolicExecutionGraphToSCCProof [SOUND, 0 ms] (6) LLVM Symbolic Execution SCC (7) SCC2IRS [SOUND, 73 ms] (8) IntTRS (9) IntTRSCompressionProof [EQUIVALENT, 0 ms] (10) IntTRS (11) PolynomialOrderProcessor [EQUIVALENT, 14 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: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 0: %1 = alloca i32, align 4 %j = alloca i32, align 4 %i = alloca i32, align 4 store 0, %1 store 1, %j store 10000, %i br %2 2: %3 = load %i %4 = load %j %5 = sub %3 %4 %6 = icmp sge %5 1 br %6, %7, %13 7: %8 = load %j %9 = add %8 1 store %9, %j br %10 10: %11 = load %i %12 = add %11 -1 store %12, %i br %2 13: %14 = load %1 ret %14 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 15 rulesP rules: f_150(v61, v62, v63, v69, v65, v66, 1, v68, v64, v70, v71, v72, 0, 3, 2, 10000, 9999, 4) -> f_151(v61, v62, v63, v69, v68, v66, 1, v65, v64, v70, v71, v72, 0, 3, 2, 10000, 9999, 4) :|: 0 = 0 f_151(v61, v62, v63, v69, v68, v66, 1, v65, v64, v70, v71, v72, 0, 3, 2, 10000, 9999, 4) -> f_152(v61, v62, v63, v69, v68, v74, 1, v65, v64, v70, v71, v72, 0, 3, 2, 10000, 9999, 4, 9997) :|: v74 + v68 = v69 && 0 <= 9999 + v74 && v74 <= 9997 f_152(v61, v62, v63, v69, v68, v74, 1, v65, v64, v70, v71, v72, 0, 3, 2, 10000, 9999, 4, 9997) -> f_153(v61, v62, v63, v69, v68, v74, 1, v65, v64, v70, v71, v72, 0, 3, 4, 10000, 9997, 2, 9998, 9999) :|: 1 <= v74 && v68 <= 9998 && 3 <= v69 && v65 <= 9997 && 4 <= v64 f_153(v61, v62, v63, v69, v68, v74, 1, v65, v64, v70, v71, v72, 0, 3, 4, 10000, 9997, 2, 9998, 9999) -> f_155(v61, v62, v63, v69, v68, v74, 1, v65, v64, v70, v71, v72, 0, 3, 4, 10000, 9997, 2, 9998, 9999) :|: 0 = 0 f_155(v61, v62, v63, v69, v68, v74, 1, v65, v64, v70, v71, v72, 0, 3, 4, 10000, 9997, 2, 9998, 9999) -> f_157(v61, v62, v63, v69, v68, v74, 1, v65, v64, v70, v71, v72, 0, 3, 4, 10000, 9997, 2, 9998, 9999) :|: TRUE f_157(v61, v62, v63, v69, v68, v74, 1, v65, v64, v70, v71, v72, 0, 3, 4, 10000, 9997, 2, 9998, 9999) -> f_159(v61, v62, v63, v69, v68, v74, 1, v64, v70, v71, v72, 0, 3, 4, 10000, 2, 9998, 9999, 9997) :|: 0 = 0 f_159(v61, v62, v63, v69, v68, v74, 1, v64, v70, v71, v72, 0, 3, 4, 10000, 2, 9998, 9999, 9997) -> f_161(v61, v62, v63, v69, v68, v74, 1, v75, v64, v70, v71, v72, 0, 3, 4, 10000, 2, 9998, 9999, 9997) :|: v75 = 1 + v68 && 3 <= v75 && v75 <= 9999 f_161(v61, v62, v63, v69, v68, v74, 1, v75, v64, v70, v71, v72, 0, 3, 4, 10000, 2, 9998, 9999, 9997) -> f_162(v61, v62, v63, v69, v68, v74, 1, v75, v64, v70, v71, v72, 0, 3, 4, 10000, 2, 9998, 9999, 9997) :|: TRUE f_162(v61, v62, v63, v69, v68, v74, 1, v75, v64, v70, v71, v72, 0, 3, 4, 10000, 2, 9998, 9999, 9997) -> f_163(v61, v62, v63, v69, v68, v74, 1, v75, v64, v70, v71, v72, 0, 3, 4, 10000, 2, 9998, 9999, 9997) :|: TRUE f_163(v61, v62, v63, v69, v68, v74, 1, v75, v64, v70, v71, v72, 0, 3, 4, 10000, 2, 9998, 9999, 9997) -> f_164(v61, v62, v63, v69, v68, v74, 1, v75, v70, v71, v72, 0, 3, 2, 9998, 9999, 4, 9997) :|: 0 = 0 f_164(v61, v62, v63, v69, v68, v74, 1, v75, v70, v71, v72, 0, 3, 2, 9998, 9999, 4, 9997) -> f_165(v61, v62, v63, v69, v68, v74, 1, v75, v77, v70, v71, v72, 0, 3, 2, 9998, 9999, 4, 9997) :|: 1 + v77 = v69 && 2 <= v77 && v77 <= 9998 f_165(v61, v62, v63, v69, v68, v74, 1, v75, v77, v70, v71, v72, 0, 3, 2, 9998, 9999, 4, 9997) -> f_166(v61, v62, v63, v69, v68, v74, 1, v75, v77, v70, v71, v72, 0, 3, 2, 9998, 9999, 4, 9997) :|: TRUE f_166(v61, v62, v63, v69, v68, v74, 1, v75, v77, v70, v71, v72, 0, 3, 2, 9998, 9999, 4, 9997) -> f_167(v61, v62, v63, v69, v68, v74, 1, v75, v77, v70, v71, v72, 0, 3, 2, 9998, 9999, 4, 9997) :|: TRUE f_167(v61, v62, v63, v69, v68, v74, 1, v75, v77, v70, v71, v72, 0, 3, 2, 9998, 9999, 4, 9997) -> f_149(v61, v62, v63, v69, v68, v74, 1, v75, v77, v70, v71, v72, 0, 3, 2, 10000, 9999, 4) :|: TRUE f_149(v61, v62, v63, v64, v65, v66, 1, v68, v69, v70, v71, v72, 0, 3, 2, 10000, 9999, 4) -> f_150(v61, v62, v63, v69, v65, v66, 1, v68, v64, v70, v71, v72, 0, 3, 2, 10000, 9999, 4) :|: 0 = 0 Combined rules. Obtained 1 rulesP rules: f_150(v61:0, v62:0, v63:0, 1 + v77:0, v65:0, v66:0, 1, v68:0, v64:0, v70:0, v71:0, v72:0, 0, 3, 2, 10000, 9999, 4) -> f_150(v61:0, v62:0, v63:0, v77:0, v68:0, v74:0, 1, 1 + v68:0, 1 + v77:0, v70:0, v71:0, v72:0, 0, 3, 2, 10000, 9999, 4) :|: v74:0 > 0 && v68:0 < 9999 && v77:0 > 1 && v74:0 + v68:0 = 1 + v77:0 && v65:0 < 9998 && v74:0 < 9998 && v64:0 > 3 && v68:0 > 1 && v77:0 < 9999 Filtered unneeded arguments: f_150(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) -> f_150(x4, x5, x8, x9) Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules: f_150(sum~cons_1~v77:0, v65:0, v68:0, v64:0) -> f_150(v77:0, v68:0, 1 + v68:0, 1 + v77:0) :|: v77:0 > 1 && v68:0 < 9999 && v65:0 < 9998 && v64:0 > 3 && v77:0 < 9999 && v68:0 > 1 && sum~cons_1~v77:0 = 1 + v77:0 ---------------------------------------- (8) Obligation: Rules: f_150(sum~cons_1~v77:0, v65:0, v68:0, v64:0) -> f_150(v77:0, v68:0, 1 + v68:0, 1 + v77:0) :|: v77:0 > 1 && v68:0 < 9999 && v65:0 < 9998 && v64:0 > 3 && v77:0 < 9999 && v68:0 > 1 && sum~cons_1~v77:0 = 1 + v77:0 ---------------------------------------- (9) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (10) Obligation: Rules: f_150(sum~cons_1~v77:0:0, v65:0:0, v68:0:0, v64:0:0) -> f_150(v77:0:0, v68:0:0, 1 + v68:0:0, 1 + v77:0:0) :|: v77:0:0 < 9999 && v68:0:0 > 1 && v64:0:0 > 3 && v65:0:0 < 9998 && v68:0:0 < 9999 && v77:0:0 > 1 && sum~cons_1~v77:0:0 = 1 + v77:0:0 ---------------------------------------- (11) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [f_150(x, x1, x2, x3)] = x The following rules are decreasing: f_150(sum~cons_1~v77:0:0, v65:0:0, v68:0:0, v64:0:0) -> f_150(v77:0:0, v68:0:0, 1 + v68:0:0, 1 + v77:0:0) :|: v77:0:0 < 9999 && v68:0:0 > 1 && v64:0:0 > 3 && v65:0:0 < 9998 && v68:0:0 < 9999 && v77:0:0 > 1 && sum~cons_1~v77:0:0 = 1 + v77:0:0 The following rules are bounded: f_150(sum~cons_1~v77:0:0, v65:0:0, v68:0:0, v64:0:0) -> f_150(v77:0:0, v68:0:0, 1 + v68:0:0, 1 + v77:0:0) :|: v77:0:0 < 9999 && v68:0:0 > 1 && v64:0:0 > 3 && v65:0:0 < 9998 && v68:0:0 < 9999 && v77:0:0 > 1 && sum~cons_1~v77:0:0 = 1 + v77:0:0 ---------------------------------------- (12) YES