/export/starexec/sandbox2/solver/bin/starexec_run_c /export/starexec/sandbox2/benchmark/theBenchmark.c /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox2/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, 179 ms] (2) LLVM problem (3) LLVMToTerminationGraphProof [EQUIVALENT, 2980 ms] (4) LLVM Symbolic Execution Graph (5) SymbolicExecutionGraphToSCCProof [SOUND, 0 ms] (6) LLVM Symbolic Execution SCC (7) SCC2IRS [SOUND, 168 ms] (8) IntTRS (9) TerminationGraphProcessor [EQUIVALENT, 34 ms] (10) IntTRS (11) IntTRSCompressionProof [EQUIVALENT, 0 ms] (12) IntTRS (13) PolynomialOrderProcessor [EQUIVALENT, 5 ms] (14) YES ---------------------------------------- (0) Obligation: c file /export/starexec/sandbox2/benchmark/theBenchmark.c ---------------------------------------- (1) CToLLVMProof (EQUIVALENT) Compiled c-file /export/starexec/sandbox2/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 %mod = 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 %20 6: %7 = load %n %8 = call i32 @isOdd(i32 %7) store %8, %result %9 = load %n %10 = srem %9 2 store %10, %mod %11 = load %result %12 = icmp slt %11 0 br %12, %17, %13 13: %14 = load %result %15 = load %mod %16 = icmp eq %14 %15 br %16, %17, %18 17: store 0, %1 br %20 18: br %19 19: Unnamed Call-Instruction = call BasicVoidType (...)* @__VERIFIER_error() noreturn unreachable 20: %21 = load %1 ret %21 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_326(v67, v78, v68, v69, v70, v71, v72, v73, v74, v75, v79, 0, v77, 3, 1, 4) -> f_327(v67, v78, v80, v68, v69, v70, v71, v72, v73, v74, v75, v79, v81, 0, v77, 3, 1, 4) :|: 1 <= v80 && v81 = 3 + v80 && 4 <= v81 f_327(v67, v78, v80, v68, v69, v70, v71, v72, v73, v74, v75, v79, v81, 0, v77, 3, 1, 4) -> f_328(v67, v78, v80, v68, v69, v70, v71, v72, v73, v74, v75, v79, v81, 0, v77, 3, 1, 4) :|: TRUE f_328(v67, v78, v80, v68, v69, v70, v71, v72, v73, v74, v75, v79, v81, 0, v77, 3, 1, 4) -> f_329(v67, v78, v80, v68, v69, v70, v71, v72, v73, v74, v75, v79, v81, 0, v77, 3, 1, 4) :|: 0 = 0 f_329(v67, v78, v80, v68, v69, v70, v71, v72, v73, v74, v75, v79, v81, 0, v77, 3, 1, 4) -> f_331(v67, v78, v80, v68, v69, v70, v71, v72, v73, v74, v75, v79, v81, 0, v77, 3, 1, 4) :|: v67 != 0 f_331(v67, v78, v80, v68, v69, v70, v71, v72, v73, v74, v75, v79, v81, 0, v77, 3, 1, 4) -> f_333(v67, v78, v80, 0, v68, v69, v70, v71, v72, v73, v74, v75, v79, v81, v77, 3, 1, 4) :|: 0 = 0 f_333(v67, v78, v80, 0, v68, v69, v70, v71, v72, v73, v74, v75, v79, v81, v77, 3, 1, 4) -> f_335(v67, v78, v80, 0, v68, v69, v70, v71, v72, v73, v74, v75, v79, v81, v77, 3, 1, 4) :|: TRUE f_335(v67, v78, v80, 0, v68, v69, v70, v71, v72, v73, v74, v75, v79, v81, v77, 3, 1, 4) -> f_337(v67, v78, v80, 0, v68, v69, v70, v71, v72, v73, v74, v75, v79, v81, v77, 3, 1, 4) :|: 0 = 0 f_337(v67, v78, v80, 0, v68, v69, v70, v71, v72, v73, v74, v75, v79, v81, v77, 3, 1, 4) -> f_340(v67, v78, v80, 0, v68, v69, v70, v71, v72, v73, v74, v75, v79, v81, v77, 3, 2, 1, 4) :|: v67 != 1 && 2 <= v67 f_340(v67, v78, v80, 0, v68, v69, v70, v71, v72, v73, v74, v75, v79, v81, v77, 3, 2, 1, 4) -> f_343(v67, v78, v80, 0, v68, v69, v70, v71, v72, v73, v74, v75, v79, v81, v77, 3, 2, 1, 4) :|: 0 = 0 f_343(v67, v78, v80, 0, v68, v69, v70, v71, v72, v73, v74, v75, v79, v81, v77, 3, 2, 1, 4) -> f_346(v67, v78, v80, 0, v68, v69, v70, v71, v72, v73, v74, v75, v79, v81, v77, 3, 2, 1, 4) :|: TRUE f_346(v67, v78, v80, 0, v68, v69, v70, v71, v72, v73, v74, v75, v79, v81, v77, 3, 2, 1, 4) -> f_349(v67, v78, v80, 0, v68, v69, v70, v71, v72, v73, v74, v75, v79, v81, v77, 3, 2, 1, 4) :|: 0 = 0 f_349(v67, v78, v80, 0, v68, v69, v70, v71, v72, v73, v74, v75, v79, v81, v77, 3, 2, 1, 4) -> f_352(v67, v78, v80, 0, v96, v68, v69, v70, v71, v72, v73, v74, v75, v79, v81, v77, 3, 1, 2, 4) :|: 1 + v96 = v67 && 1 <= v96 f_352(v67, v78, v80, 0, v96, v68, v69, v70, v71, v72, v73, v74, v75, v79, v81, v77, 3, 1, 2, 4) -> f_355(v96, v68, v69, v70, v71, v72, v73, v74, v75, v78, v79, v80, v81, 0, v77, v67, 3, 1, 2, 4) :|: 0 = 0 f_355(v96, v68, v69, v70, v71, v72, v73, v74, v75, v78, v79, v80, v81, 0, v77, v67, 3, 1, 2, 4) -> f_358(v96, v68, v69, v70, v71, v72, v73, v74, v75, v78, v79, v80, v81, 0, v77, v67, 3, 1, 2, 4) :|: TRUE f_358(v96, v68, v69, v70, v71, v72, v73, v74, v75, v78, v79, v80, v81, 0, v77, v67, 3, 1, 2, 4) -> f_363(v96, v110, v68, v69, v70, v71, v72, v73, v74, v75, v78, v79, v80, v81, v111, 0, v77, v67, 3, 1, 2, 4) :|: 1 <= v110 && v111 = 3 + v110 && 4 <= v111 f_363(v96, v110, v68, v69, v70, v71, v72, v73, v74, v75, v78, v79, v80, v81, v111, 0, v77, v67, 3, 1, 2, 4) -> f_366(v96, v110, v112, v68, v69, v70, v71, v72, v73, v74, v75, v78, v79, v80, v81, v111, v113, 0, v77, v67, 3, 1, 2, 4) :|: 1 <= v112 && v113 = 3 + v112 && 4 <= v113 f_366(v96, v110, v112, v68, v69, v70, v71, v72, v73, v74, v75, v78, v79, v80, v81, v111, v113, 0, v77, v67, 3, 1, 2, 4) -> f_369(v96, v110, v112, v68, v69, v70, v71, v72, v73, v74, v75, v78, v79, v80, v81, v111, v113, 0, v77, v67, 3, 1, 2, 4) :|: TRUE f_369(v96, v110, v112, v68, v69, v70, v71, v72, v73, v74, v75, v78, v79, v80, v81, v111, v113, 0, v77, v67, 3, 1, 2, 4) -> f_372(v96, v110, v112, v68, v69, v70, v71, v72, v73, v74, v75, v78, v79, v80, v81, v111, v113, 0, v77, v67, 3, 1, 2, 4) :|: 0 = 0 f_372(v96, v110, v112, v68, v69, v70, v71, v72, v73, v74, v75, v78, v79, v80, v81, v111, v113, 0, v77, v67, 3, 1, 2, 4) -> f_375(v96, v110, v112, 0, v68, v69, v70, v71, v72, v73, v74, v75, v78, v79, v80, v81, v111, v113, v77, v67, 3, 1, 2, 4) :|: 0 = 0 f_375(v96, v110, v112, 0, v68, v69, v70, v71, v72, v73, v74, v75, v78, v79, v80, v81, v111, v113, v77, v67, 3, 1, 2, 4) -> f_378(v96, v110, v112, 0, v68, v69, v70, v71, v72, v73, v74, v75, v78, v79, v80, v81, v111, v113, v77, v67, 3, 1, 2, 4) :|: TRUE f_378(v96, v110, v112, 0, v68, v69, v70, v71, v72, v73, v74, v75, v78, v79, v80, v81, v111, v113, v77, v67, 3, 1, 2, 4) -> f_381(v96, v110, v112, 0, v68, v69, v70, v71, v72, v73, v74, v75, v78, v79, v80, v81, v111, v113, v77, v67, 3, 1, 2, 4) :|: 0 = 0 f_381(v96, v110, v112, 0, v68, v69, v70, v71, v72, v73, v74, v75, v78, v79, v80, v81, v111, v113, v77, v67, 3, 1, 2, 4) -> f_385(v96, v110, v112, 0, v68, v69, v70, v71, v72, v73, v74, v75, v78, v79, v80, v81, v111, v113, v77, v67, 3, 1, 4, 2) :|: v96 != 1 && 2 <= v96 && 3 <= v67 f_385(v96, v110, v112, 0, v68, v69, v70, v71, v72, v73, v74, v75, v78, v79, v80, v81, v111, v113, v77, v67, 3, 1, 4, 2) -> f_389(v96, v110, v112, 0, v68, v69, v70, v71, v72, v73, v74, v75, v78, v79, v80, v81, v111, v113, v77, v67, 3, 1, 4, 2) :|: 0 = 0 f_389(v96, v110, v112, 0, v68, v69, v70, v71, v72, v73, v74, v75, v78, v79, v80, v81, v111, v113, v77, v67, 3, 1, 4, 2) -> f_393(v96, v110, v112, 0, v68, v69, v70, v71, v72, v73, v74, v75, v78, v79, v80, v81, v111, v113, v77, v67, 3, 1, 4, 2) :|: TRUE f_393(v96, v110, v112, 0, v68, v69, v70, v71, v72, v73, v74, v75, v78, v79, v80, v81, v111, v113, v77, v67, 3, 1, 4, 2) -> f_396(v96, v110, v112, 0, v68, v69, v70, v71, v72, v73, v74, v75, v78, v79, v80, v81, v111, v113, v77, v67, 3, 1, 4, 2) :|: 0 = 0 f_396(v96, v110, v112, 0, v68, v69, v70, v71, v72, v73, v74, v75, v78, v79, v80, v81, v111, v113, v77, v67, 3, 1, 4, 2) -> f_399(v96, v110, v112, 0, v123, v68, v69, v70, v71, v72, v73, v74, v75, v78, v79, v80, v81, v111, v113, v77, v67, 3, 1, 4, 2) :|: 1 + v123 = v96 && 1 <= v123 f_399(v96, v110, v112, 0, v123, v68, v69, v70, v71, v72, v73, v74, v75, v78, v79, v80, v81, v111, v113, v77, v67, 3, 1, 4, 2) -> f_402(v123, v68, v69, v70, v71, v72, v73, v74, v75, v78, v79, v80, v81, v110, v111, v112, v113, 0, v77, v67, v96, 3, 1, 4, 2) :|: 0 = 0 f_402(v123, v68, v69, v70, v71, v72, v73, v74, v75, v78, v79, v80, v81, v110, v111, v112, v113, 0, v77, v67, v96, 3, 1, 4, 2) -> f_405(v123, v68, v69, v70, v71, v72, v73, v74, v75, v78, v79, v80, v81, v110, v111, v112, v113, 0, v77, v67, v96, 3, 1, 4, 2) :|: TRUE f_405(v123, v68, v69, v70, v71, v72, v73, v74, v75, v78, v79, v80, v81, v110, v111, v112, v113, 0, v77, v67, v96, 3, 1, 4, 2) -> f_324(v123, v68, v69, v70, v71, v72, v73, v74, v75, 0, v77, 3, 1, 4) :|: TRUE f_324(v67, v68, v69, v70, v71, v72, v73, v74, v75, 0, v77, 3, 1, 4) -> f_326(v67, v78, v68, v69, v70, v71, v72, v73, v74, v75, v79, 0, v77, 3, 1, 4) :|: 1 <= v78 && v79 = 3 + v78 && 4 <= v79 Combined rules. Obtained 2 rulesP rules: f_326(1 + (1 + v123:0), v78:0, v68:0, v69:0, v70:0, v71:0, v72:0, v73:0, v74:0, v75:0, v79:0, 0, v77:0, 3, 1, 4) -> f_326(v123:0, v78:1, v68:0, v69:0, v70:0, v71:0, v72:0, v73:0, v74:0, v75:0, 3 + v78:1, 0, v77:0, 3, 1, 4) :|: v123:0 > 0 && v80:0 > 0 && v123:0 < -2 && v110:0 > 0 && v112:0 > 0 && v78:1 > 0 f_326(1 + (1 + v123:0), v78:0, v68:0, v69:0, v70:0, v71:0, v72:0, v73:0, v74:0, v75:0, v79:0, 0, v77:0, 3, 1, 4) -> f_326(v123:0, v78:1, v68:0, v69:0, v70:0, v71:0, v72:0, v73:0, v74:0, v75:0, 3 + v78:1, 0, v77:0, 3, 1, 4) :|: v123:0 > 0 && v80:0 > 0 && v110:0 > 0 && v112:0 > 0 && v78:1 > 0 Filtered unneeded arguments: f_326(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16) -> f_326(x1) Removed division, modulo operations, cleaned up constraints. Obtained 2 rules.P rules: f_326(sum~cons_1~sum~cons_1~v123:0) -> f_326(v123:0) :|: v123:0 > 0 && v123:0 < -2 && sum~cons_1~sum~cons_1~v123:0 = 1 + (1 + v123:0) f_326(sum~cons_1~sum~cons_1~v123:0) -> f_326(v123:0) :|: v123:0 > 0 && sum~cons_1~sum~cons_1~v123:0 = 1 + (1 + v123:0) ---------------------------------------- (8) Obligation: Rules: f_326(sum~cons_1~sum~cons_1~v123:0) -> f_326(v123:0) :|: v123:0 > 0 && v123:0 < -2 && sum~cons_1~sum~cons_1~v123:0 = 1 + (1 + v123:0) f_326(x) -> f_326(x1) :|: x1 > 0 && x = 1 + (1 + x1) ---------------------------------------- (9) TerminationGraphProcessor (EQUIVALENT) Constructed the termination graph and obtained one non-trivial SCC. ---------------------------------------- (10) Obligation: Rules: f_326(x) -> f_326(x1) :|: x1 > 0 && x = 1 + (1 + x1) ---------------------------------------- (11) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (12) Obligation: Rules: f_326(sum~cons_1~sum~cons_1~x1:0) -> f_326(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_326(x)] = x The following rules are decreasing: f_326(sum~cons_1~sum~cons_1~x1:0) -> f_326(x1:0) :|: x1:0 > 0 && sum~cons_1~sum~cons_1~x1:0 = 1 + (1 + x1:0) The following rules are bounded: f_326(sum~cons_1~sum~cons_1~x1:0) -> f_326(x1:0) :|: x1:0 > 0 && sum~cons_1~sum~cons_1~x1:0 = 1 + (1 + x1:0) ---------------------------------------- (14) YES