/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, 175 ms] (2) LLVM problem (3) LLVMToTerminationGraphProof [EQUIVALENT, 2649 ms] (4) LLVM Symbolic Execution Graph (5) SymbolicExecutionGraphToSCCProof [SOUND, 0 ms] (6) LLVM Symbolic Execution SCC (7) SCC2IRS [SOUND, 114 ms] (8) IntTRS (9) TerminationGraphProcessor [EQUIVALENT, 30 ms] (10) IntTRS (11) IntTRSCompressionProof [EQUIVALENT, 0 ms] (12) IntTRS (13) PolynomialOrderProcessor [EQUIVALENT, 8 ms] (14) 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: false visibilityType: DEFAULT callingConvention: ccc *BasicFunctionTypename: "__VERIFIER_error" returnParam: BasicVoidType parameters: () variableLength: true visibilityType: DEFAULT callingConvention: ccc *BasicFunctionTypename: "isOdd" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: (n i32) variableLength: false visibilityType: DEFAULT callingConvention: ccc 0: %1 = alloca i32, align 4 %2 = alloca i32, align 4 store %n, %2 %3 = load %2 %4 = icmp eq %3 0 br %4, %5, %6 5: store 0, %1 br %14 6: %7 = load %2 %8 = icmp eq %7 1 br %8, %9, %10 9: store 1, %1 br %14 10: %11 = load %2 %12 = sub %11 1 %13 = call i32 @isEven(i32 %12) store %13, %1 br %14 14: %15 = load %1 ret %15 *BasicFunctionTypename: "isEven" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: (n i32) variableLength: false visibilityType: DEFAULT callingConvention: ccc 0: %1 = alloca i32, align 4 %2 = alloca i32, align 4 store %n, %2 %3 = load %2 %4 = icmp eq %3 0 br %4, %5, %6 5: store 1, %1 br %14 6: %7 = load %2 %8 = icmp eq %7 1 br %8, %9, %10 9: store 0, %1 br %14 10: %11 = load %2 %12 = sub %11 1 %13 = call i32 @isOdd(i32 %12) store %13, %1 br %14 14: %15 = load %1 ret %15 *BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 0: %1 = alloca i32, align 4 %n = alloca i32, align 4 %result = alloca i32, align 4 store 0, %1 %2 = call i32 @__VERIFIER_nondet_int() store %2, %n %3 = load %n %4 = icmp slt %3 0 br %4, %5, %6 5: store 0, %1 br %14 6: %7 = load %n %8 = call i32 @isOdd(i32 %7) store %8, %result %9 = load %result %10 = icmp sge %9 0 br %10, %11, %12 11: store 0, %1 br %14 12: br %13 13: Unnamed Call-Instruction = call BasicVoidType (...)* @__VERIFIER_error() noreturn unreachable 14: %15 = load %1 ret %15 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 30 rulesP rules: f_287(v58, v67, v59, v60, v61, v62, v63, v64, v68, 0, v66, 3, 1, 4) -> f_288(v58, v67, v69, v59, v60, v61, v62, v63, v64, v68, v70, 0, v66, 3, 1, 4) :|: 1 <= v69 && v70 = 3 + v69 && 4 <= v70 f_288(v58, v67, v69, v59, v60, v61, v62, v63, v64, v68, v70, 0, v66, 3, 1, 4) -> f_289(v58, v67, v69, v59, v60, v61, v62, v63, v64, v68, v70, 0, v66, 3, 1, 4) :|: TRUE f_289(v58, v67, v69, v59, v60, v61, v62, v63, v64, v68, v70, 0, v66, 3, 1, 4) -> f_290(v58, v67, v69, v59, v60, v61, v62, v63, v64, v68, v70, 0, v66, 3, 1, 4) :|: 0 = 0 f_290(v58, v67, v69, v59, v60, v61, v62, v63, v64, v68, v70, 0, v66, 3, 1, 4) -> f_292(v58, v67, v69, v59, v60, v61, v62, v63, v64, v68, v70, 0, v66, 3, 1, 4) :|: v58 != 0 f_292(v58, v67, v69, v59, v60, v61, v62, v63, v64, v68, v70, 0, v66, 3, 1, 4) -> f_294(v58, v67, v69, 0, v59, v60, v61, v62, v63, v64, v68, v70, v66, 3, 1, 4) :|: 0 = 0 f_294(v58, v67, v69, 0, v59, v60, v61, v62, v63, v64, v68, v70, v66, 3, 1, 4) -> f_296(v58, v67, v69, 0, v59, v60, v61, v62, v63, v64, v68, v70, v66, 3, 1, 4) :|: TRUE f_296(v58, v67, v69, 0, v59, v60, v61, v62, v63, v64, v68, v70, v66, 3, 1, 4) -> f_298(v58, v67, v69, 0, v59, v60, v61, v62, v63, v64, v68, v70, v66, 3, 1, 4) :|: 0 = 0 f_298(v58, v67, v69, 0, v59, v60, v61, v62, v63, v64, v68, v70, v66, 3, 1, 4) -> f_301(v58, v67, v69, 0, v59, v60, v61, v62, v63, v64, v68, v70, v66, 3, 2, 1, 4) :|: v58 != 1 && 2 <= v58 f_301(v58, v67, v69, 0, v59, v60, v61, v62, v63, v64, v68, v70, v66, 3, 2, 1, 4) -> f_304(v58, v67, v69, 0, v59, v60, v61, v62, v63, v64, v68, v70, v66, 3, 2, 1, 4) :|: 0 = 0 f_304(v58, v67, v69, 0, v59, v60, v61, v62, v63, v64, v68, v70, v66, 3, 2, 1, 4) -> f_307(v58, v67, v69, 0, v59, v60, v61, v62, v63, v64, v68, v70, v66, 3, 2, 1, 4) :|: TRUE f_307(v58, v67, v69, 0, v59, v60, v61, v62, v63, v64, v68, v70, v66, 3, 2, 1, 4) -> f_310(v58, v67, v69, 0, v59, v60, v61, v62, v63, v64, v68, v70, v66, 3, 2, 1, 4) :|: 0 = 0 f_310(v58, v67, v69, 0, v59, v60, v61, v62, v63, v64, v68, v70, v66, 3, 2, 1, 4) -> f_313(v58, v67, v69, 0, v83, v59, v60, v61, v62, v63, v64, v68, v70, v66, 3, 1, 2, 4) :|: 1 + v83 = v58 && 1 <= v83 f_313(v58, v67, v69, 0, v83, v59, v60, v61, v62, v63, v64, v68, v70, v66, 3, 1, 2, 4) -> f_316(v83, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, 0, v66, v58, 3, 1, 2, 4) :|: 0 = 0 f_316(v83, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, 0, v66, v58, 3, 1, 2, 4) -> f_319(v83, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, 0, v66, v58, 3, 1, 2, 4) :|: TRUE f_319(v83, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, 0, v66, v58, 3, 1, 2, 4) -> f_324(v83, v95, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, 0, v66, v58, 3, 1, 2, 4) :|: 1 <= v95 && v96 = 3 + v95 && 4 <= v96 f_324(v83, v95, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, 0, v66, v58, 3, 1, 2, 4) -> f_327(v83, v95, v97, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, v98, 0, v66, v58, 3, 1, 2, 4) :|: 1 <= v97 && v98 = 3 + v97 && 4 <= v98 f_327(v83, v95, v97, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, v98, 0, v66, v58, 3, 1, 2, 4) -> f_330(v83, v95, v97, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, v98, 0, v66, v58, 3, 1, 2, 4) :|: TRUE f_330(v83, v95, v97, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, v98, 0, v66, v58, 3, 1, 2, 4) -> f_332(v83, v95, v97, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, v98, 0, v66, v58, 3, 1, 2, 4) :|: 0 = 0 f_332(v83, v95, v97, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, v98, 0, v66, v58, 3, 1, 2, 4) -> f_334(v83, v95, v97, 0, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, v98, v66, v58, 3, 1, 2, 4) :|: 0 = 0 f_334(v83, v95, v97, 0, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, v98, v66, v58, 3, 1, 2, 4) -> f_336(v83, v95, v97, 0, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, v98, v66, v58, 3, 1, 2, 4) :|: TRUE f_336(v83, v95, v97, 0, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, v98, v66, v58, 3, 1, 2, 4) -> f_338(v83, v95, v97, 0, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, v98, v66, v58, 3, 1, 2, 4) :|: 0 = 0 f_338(v83, v95, v97, 0, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, v98, v66, v58, 3, 1, 2, 4) -> f_340(v83, v95, v97, 0, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, v98, v66, v58, 3, 1, 4, 2) :|: v83 != 1 && 2 <= v83 && 3 <= v58 f_340(v83, v95, v97, 0, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, v98, v66, v58, 3, 1, 4, 2) -> f_342(v83, v95, v97, 0, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, v98, v66, v58, 3, 1, 4, 2) :|: 0 = 0 f_342(v83, v95, v97, 0, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, v98, v66, v58, 3, 1, 4, 2) -> f_344(v83, v95, v97, 0, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, v98, v66, v58, 3, 1, 4, 2) :|: TRUE f_344(v83, v95, v97, 0, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, v98, v66, v58, 3, 1, 4, 2) -> f_346(v83, v95, v97, 0, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, v98, v66, v58, 3, 1, 4, 2) :|: 0 = 0 f_346(v83, v95, v97, 0, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, v98, v66, v58, 3, 1, 4, 2) -> f_348(v83, v95, v97, 0, v106, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, v98, v66, v58, 3, 1, 4, 2) :|: 1 + v106 = v83 && 1 <= v106 f_348(v83, v95, v97, 0, v106, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, v98, v66, v58, 3, 1, 4, 2) -> f_350(v106, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v95, v96, v97, v98, 0, v66, v58, v83, 3, 1, 4, 2) :|: 0 = 0 f_350(v106, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v95, v96, v97, v98, 0, v66, v58, v83, 3, 1, 4, 2) -> f_352(v106, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v95, v96, v97, v98, 0, v66, v58, v83, 3, 1, 4, 2) :|: TRUE f_352(v106, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v95, v96, v97, v98, 0, v66, v58, v83, 3, 1, 4, 2) -> f_285(v106, v59, v60, v61, v62, v63, v64, 0, v66, 3, 1, 4) :|: TRUE f_285(v58, v59, v60, v61, v62, v63, v64, 0, v66, 3, 1, 4) -> f_287(v58, v67, v59, v60, v61, v62, v63, v64, v68, 0, v66, 3, 1, 4) :|: 1 <= v67 && v68 = 3 + v67 && 4 <= v68 Combined rules. Obtained 2 rulesP rules: f_287(1 + (1 + v106:0), v67:0, v59:0, v60:0, v61:0, v62:0, v63:0, v64:0, v68:0, 0, v66:0, 3, 1, 4) -> f_287(v106:0, v67:1, v59:0, v60:0, v61:0, v62:0, v63:0, v64:0, 3 + v67:1, 0, v66:0, 3, 1, 4) :|: v106:0 > 0 && v69:0 > 0 && v106:0 < -2 && v95:0 > 0 && v97:0 > 0 && v67:1 > 0 f_287(1 + (1 + v106:0), v67:0, v59:0, v60:0, v61:0, v62:0, v63:0, v64:0, v68:0, 0, v66:0, 3, 1, 4) -> f_287(v106:0, v67:1, v59:0, v60:0, v61:0, v62:0, v63:0, v64:0, 3 + v67:1, 0, v66:0, 3, 1, 4) :|: v106:0 > 0 && v69:0 > 0 && v95:0 > 0 && v97:0 > 0 && v67:1 > 0 Filtered unneeded arguments: f_287(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14) -> f_287(x1) Removed division, modulo operations, cleaned up constraints. Obtained 2 rules.P rules: f_287(sum~cons_1~sum~cons_1~v106:0) -> f_287(v106:0) :|: v106:0 > 0 && v106:0 < -2 && sum~cons_1~sum~cons_1~v106:0 = 1 + (1 + v106:0) f_287(sum~cons_1~sum~cons_1~v106:0) -> f_287(v106:0) :|: v106:0 > 0 && sum~cons_1~sum~cons_1~v106:0 = 1 + (1 + v106:0) ---------------------------------------- (8) Obligation: Rules: f_287(sum~cons_1~sum~cons_1~v106:0) -> f_287(v106:0) :|: v106:0 > 0 && v106:0 < -2 && sum~cons_1~sum~cons_1~v106:0 = 1 + (1 + v106:0) f_287(x) -> f_287(x1) :|: x1 > 0 && x = 1 + (1 + x1) ---------------------------------------- (9) TerminationGraphProcessor (EQUIVALENT) Constructed the termination graph and obtained one non-trivial SCC. ---------------------------------------- (10) Obligation: Rules: f_287(x) -> f_287(x1) :|: x1 > 0 && x = 1 + (1 + x1) ---------------------------------------- (11) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (12) Obligation: Rules: f_287(sum~cons_1~sum~cons_1~x1:0) -> f_287(x1:0) :|: x1:0 > 0 && sum~cons_1~sum~cons_1~x1:0 = 1 + (1 + x1:0) ---------------------------------------- (13) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [f_287(x)] = x The following rules are decreasing: f_287(sum~cons_1~sum~cons_1~x1:0) -> f_287(x1:0) :|: x1:0 > 0 && sum~cons_1~sum~cons_1~x1:0 = 1 + (1 + x1:0) The following rules are bounded: f_287(sum~cons_1~sum~cons_1~x1:0) -> f_287(x1:0) :|: x1:0 > 0 && sum~cons_1~sum~cons_1~x1:0 = 1 + (1 + x1:0) ---------------------------------------- (14) YES