/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, 178 ms] (2) LLVM problem (3) LLVMToTerminationGraphProof [EQUIVALENT, 1003 ms] (4) LLVM Symbolic Execution Graph (5) SymbolicExecutionGraphToSCCProof [SOUND, 0 ms] (6) AND (7) LLVM Symbolic Execution SCC (8) SCC2IRS [SOUND, 26 ms] (9) IntTRS (10) IntTRSCompressionProof [EQUIVALENT, 0 ms] (11) IntTRS (12) PolynomialOrderProcessor [EQUIVALENT, 13 ms] (13) YES (14) LLVM Symbolic Execution SCC (15) SCC2IRS [SOUND, 61 ms] (16) IntTRS (17) IRS2T2 [EQUIVALENT, 0 ms] (18) T2IntSys (19) T2 [EQUIVALENT, 1082 ms] (20) YES (21) LLVM Symbolic Execution SCC (22) SCC2IRS [SOUND, 36 ms] (23) IntTRS (24) IRS2T2 [EQUIVALENT, 0 ms] (25) T2IntSys (26) T2 [EQUIVALENT, 312 ms] (27) 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: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 0: %1 = alloca i32, align 4 %x = alloca i32, align 4 %y = alloca i32, align 4 store 0, %1 %2 = call i32 @__VERIFIER_nondet_int() store %2, %x %3 = call i32 @__VERIFIER_nondet_int() store %3, %y br %4 4: %5 = load %x %6 = icmp sge %5 0 br %6, %7, %10 7: %8 = load %x %9 = sub %8 1 store %9, %x br %17 10: %11 = load %y %12 = icmp slt %11 0 br %12, %13, %14 13: br %18 14: %15 = load %y %16 = sub %15 1 store %16, %y br %17 17: br %4 18: 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 3 SCCs. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: SCC ---------------------------------------- (8) SCC2IRS (SOUND) Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: Generated rules. Obtained 13 rulesP rules: f_263(v345, v346, v347, v348, v349, -1, 0, v352, v353, v354, v355, v356, 3, 1, 4) -> f_264(v345, v346, v347, v348, v349, -1, 0, v352, v353, v354, v355, v356, 3, 1, 4) :|: 0 = 0 f_264(v345, v346, v347, v348, v349, -1, 0, v352, v353, v354, v355, v356, 3, 1, 4) -> f_265(v345, v346, v347, v348, v349, -1, 0, v352, v353, v354, v355, v356, 3, 1, 4) :|: 0 = 0 f_265(v345, v346, v347, v348, v349, -1, 0, v352, v353, v354, v355, v356, 3, 1, 4) -> f_266(v345, v346, v347, v348, v349, -1, 0, v352, v353, v354, v355, v356, 3, 1, 4) :|: TRUE f_266(v345, v346, v347, v348, v349, -1, 0, v352, v353, v354, v355, v356, 3, 1, 4) -> f_267(v345, v346, v347, v348, v349, -1, 0, v353, v352, v354, v355, v356, 3, 1, 4) :|: 0 = 0 f_267(v345, v346, v347, v348, v349, -1, 0, v353, v352, v354, v355, v356, 3, 1, 4) -> f_269(v345, v346, v347, v348, v349, -1, 0, v353, v352, v354, v355, v356, 3, 1, 4) :|: 0 <= v353 && 1 <= v352 && 1 <= v349 f_269(v345, v346, v347, v348, v349, -1, 0, v353, v352, v354, v355, v356, 3, 1, 4) -> f_271(v345, v346, v347, v348, v349, -1, 0, v353, v352, v354, v355, v356, 3, 1, 4) :|: 0 = 0 f_271(v345, v346, v347, v348, v349, -1, 0, v353, v352, v354, v355, v356, 3, 1, 4) -> f_273(v345, v346, v347, v348, v349, -1, 0, v353, v352, v354, v355, v356, 3, 1, 4) :|: TRUE f_273(v345, v346, v347, v348, v349, -1, 0, v353, v352, v354, v355, v356, 3, 1, 4) -> f_275(v345, v346, v347, v348, v349, -1, 0, v353, v354, v355, v356, 3, 1, 4) :|: 0 = 0 f_275(v345, v346, v347, v348, v349, -1, 0, v353, v354, v355, v356, 3, 1, 4) -> f_276(v345, v346, v347, v348, v349, -1, 0, v353, v400, v354, v355, v356, 3, 1, 4) :|: 1 + v400 = v353 && 0 <= 1 + v400 f_276(v345, v346, v347, v348, v349, -1, 0, v353, v400, v354, v355, v356, 3, 1, 4) -> f_277(v345, v346, v347, v348, v349, -1, 0, v353, v400, v354, v355, v356, 3, 1, 4) :|: TRUE f_277(v345, v346, v347, v348, v349, -1, 0, v353, v400, v354, v355, v356, 3, 1, 4) -> f_278(v345, v346, v347, v348, v349, -1, 0, v353, v400, v354, v355, v356, 3, 1, 4) :|: TRUE f_278(v345, v346, v347, v348, v349, -1, 0, v353, v400, v354, v355, v356, 3, 1, 4) -> f_262(v345, v346, v347, v348, v349, -1, 0, v353, v400, v354, v355, v356, 3, 1, 4) :|: TRUE f_262(v345, v346, v347, v348, v349, -1, 0, v352, v353, v354, v355, v356, 3, 1, 4) -> f_263(v345, v346, v347, v348, v349, -1, 0, v352, v353, v354, v355, v356, 3, 1, 4) :|: TRUE Combined rules. Obtained 1 rulesP rules: f_263(v345:0, v346:0, v347:0, v348:0, v349:0, -1, 0, v352:0, 1 + v400:0, v354:0, v355:0, v356:0, 3, 1, 4) -> f_263(v345:0, v346:0, v347:0, v348:0, v349:0, -1, 0, 1 + v400:0, v400:0, v354:0, v355:0, v356:0, 3, 1, 4) :|: v352:0 > 0 && v400:0 > -2 && v349:0 > 0 Filtered unneeded arguments: f_263(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15) -> f_263(x5, x8, x9) Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules: f_263(v349:0, v352:0, sum~cons_1~v400:0) -> f_263(v349:0, 1 + v400:0, v400:0) :|: v400:0 > -2 && v349:0 > 0 && v352:0 > 0 && sum~cons_1~v400:0 = 1 + v400:0 ---------------------------------------- (9) Obligation: Rules: f_263(v349:0, v352:0, sum~cons_1~v400:0) -> f_263(v349:0, 1 + v400:0, v400:0) :|: v400:0 > -2 && v349:0 > 0 && v352:0 > 0 && sum~cons_1~v400:0 = 1 + v400:0 ---------------------------------------- (10) IntTRSCompressionProof (EQUIVALENT) Compressed rules. ---------------------------------------- (11) Obligation: Rules: f_263(v349:0:0, v352:0:0, sum~cons_1~v400:0:0) -> f_263(v349:0:0, 1 + v400:0:0, v400:0:0) :|: v400:0:0 > -2 && v349:0:0 > 0 && v352:0:0 > 0 && sum~cons_1~v400:0:0 = 1 + v400:0:0 ---------------------------------------- (12) PolynomialOrderProcessor (EQUIVALENT) Found the following polynomial interpretation: [f_263(x, x1, x2)] = x2 The following rules are decreasing: f_263(v349:0:0, v352:0:0, sum~cons_1~v400:0:0) -> f_263(v349:0:0, 1 + v400:0:0, v400:0:0) :|: v400:0:0 > -2 && v349:0:0 > 0 && v352:0:0 > 0 && sum~cons_1~v400:0:0 = 1 + v400:0:0 The following rules are bounded: f_263(v349:0:0, v352:0:0, sum~cons_1~v400:0:0) -> f_263(v349:0:0, 1 + v400:0:0, v400:0:0) :|: v400:0:0 > -2 && v349:0:0 > 0 && v352:0:0 > 0 && sum~cons_1~v400:0:0 = 1 + v400:0:0 ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: SCC ---------------------------------------- (15) SCC2IRS (SOUND) Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: Generated rules. Obtained 13 rulesP rules: f_211(v123, v124, v125, v126, v127, 0, v129, v130, v131, v132, v133, 3, 1, 4) -> f_213(v123, v124, v125, v126, v127, 0, v129, v130, v131, v132, v133, 3, 1, 4) :|: 0 = 0 f_213(v123, v124, v125, v126, v127, 0, v129, v130, v131, v132, v133, 3, 1, 4) -> f_215(v123, v124, v125, v126, v127, 0, v129, v130, v131, v132, v133, 3, 1, 4) :|: 0 = 0 f_215(v123, v124, v125, v126, v127, 0, v129, v130, v131, v132, v133, 3, 1, 4) -> f_217(v123, v124, v125, v126, v127, 0, v129, v130, v131, v132, v133, 3, 1, 4) :|: TRUE f_217(v123, v124, v125, v126, v127, 0, v129, v130, v131, v132, v133, 3, 1, 4) -> f_219(v123, v124, v125, v126, v127, 0, v130, v129, v131, v132, v133, 3, 1, 4) :|: 0 = 0 f_219(v123, v124, v125, v126, v127, 0, v130, v129, v131, v132, v133, 3, 1, 4) -> f_222(v123, v124, v125, v126, v127, 0, v130, v129, v131, v132, v133, 3, 1, 4) :|: 0 <= v130 && 1 <= v129 && 1 <= v127 f_222(v123, v124, v125, v126, v127, 0, v130, v129, v131, v132, v133, 3, 1, 4) -> f_225(v123, v124, v125, v126, v127, 0, v130, v129, v131, v132, v133, 3, 1, 4) :|: 0 = 0 f_225(v123, v124, v125, v126, v127, 0, v130, v129, v131, v132, v133, 3, 1, 4) -> f_228(v123, v124, v125, v126, v127, 0, v130, v129, v131, v132, v133, 3, 1, 4) :|: TRUE f_228(v123, v124, v125, v126, v127, 0, v130, v129, v131, v132, v133, 3, 1, 4) -> f_232(v123, v124, v125, v126, v127, 0, v130, v131, v132, v133, 3, 1, 4) :|: 0 = 0 f_232(v123, v124, v125, v126, v127, 0, v130, v131, v132, v133, 3, 1, 4) -> f_235(v123, v124, v125, v126, v127, 0, v130, v203, v131, v132, v133, 3, 1, 4) :|: 1 + v203 = v130 && 0 <= 1 + v203 f_235(v123, v124, v125, v126, v127, 0, v130, v203, v131, v132, v133, 3, 1, 4) -> f_238(v123, v124, v125, v126, v127, 0, v130, v203, v131, v132, v133, 3, 1, 4) :|: TRUE f_238(v123, v124, v125, v126, v127, 0, v130, v203, v131, v132, v133, 3, 1, 4) -> f_241(v123, v124, v125, v126, v127, 0, v130, v203, v131, v132, v133, 3, 1, 4) :|: TRUE f_241(v123, v124, v125, v126, v127, 0, v130, v203, v131, v132, v133, 3, 1, 4) -> f_209(v123, v124, v125, v126, v127, 0, v130, v203, v131, v132, v133, 3, 1, 4) :|: TRUE f_209(v123, v124, v125, v126, v127, 0, v129, v130, v131, v132, v133, 3, 1, 4) -> f_211(v123, v124, v125, v126, v127, 0, v129, v130, v131, v132, v133, 3, 1, 4) :|: TRUE Combined rules. Obtained 1 rulesP rules: f_211(v123:0, v124:0, v125:0, v126:0, v127:0, 0, v129:0, 1 + v203:0, v131:0, v132:0, v133:0, 3, 1, 4) -> f_211(v123:0, v124:0, v125:0, v126:0, v127:0, 0, 1 + v203:0, v203:0, v131:0, v132:0, v133:0, 3, 1, 4) :|: v129:0 > 0 && v203:0 > -2 && v127:0 > 0 Filtered unneeded arguments: f_211(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14) -> f_211(x5, x7, x8) Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules: f_211(v127:0, v129:0, sum~cons_1~v203:0) -> f_211(v127:0, 1 + v203:0, v203:0) :|: v203:0 > -2 && v127:0 > 0 && v129:0 > 0 && sum~cons_1~v203:0 = 1 + v203:0 ---------------------------------------- (16) Obligation: Rules: f_211(v127:0, v129:0, sum~cons_1~v203:0) -> f_211(v127:0, 1 + v203:0, v203:0) :|: v203:0 > -2 && v127:0 > 0 && v129:0 > 0 && sum~cons_1~v203:0 = 1 + v203:0 ---------------------------------------- (17) IRS2T2 (EQUIVALENT) Transformed input IRS into an integer transition system.Used the following mapping from defined symbols to location IDs: (f_211_3,1) ---------------------------------------- (18) Obligation: START: 0; FROM: 0; TO: 1; FROM: 1; oldX0 := x0; oldX1 := x1; oldX2 := x2; oldX3 := oldX2 - 1; assume(oldX3 > -2 && oldX0 > 0 && oldX1 > 0 && oldX2 = 1 + oldX3); x0 := oldX0; x1 := 1 + oldX3; x2 := oldX2 - 1; TO: 1; ---------------------------------------- (19) T2 (EQUIVALENT) Initially, performed program simplifications using lexicographic rank functions: * Removed transitions 1, 3, 4 using the following rank functions: - Rank function 1: RF for loc. 5: 1+2*x2 RF for loc. 6: 2*x2 Bound for (chained) transitions 4: 0 - Rank function 2: RF for loc. 5: 1+2*x2 RF for loc. 6: 2*x2 Bound for (chained) transitions 3: 0 - Rank function 3: RF for loc. 5: 1 RF for loc. 6: 0 Bound for (chained) transitions 1: 1 ---------------------------------------- (20) YES ---------------------------------------- (21) Obligation: SCC ---------------------------------------- (22) SCC2IRS (SOUND) Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: Generated rules. Obtained 10 rulesP rules: f_175(v68, v69, v70, v71, v72, v75, 1, v73, v76, v77, v78, 0, 3, 4) -> f_177(v68, v69, v70, v71, v72, v75, 1, v73, v76, v77, v78, 0, 3, 4) :|: 0 <= v75 && 1 <= v73 && 1 <= v71 f_177(v68, v69, v70, v71, v72, v75, 1, v73, v76, v77, v78, 0, 3, 4) -> f_180(v68, v69, v70, v71, v72, v75, 1, v73, v76, v77, v78, 0, 3, 4) :|: 0 = 0 f_180(v68, v69, v70, v71, v72, v75, 1, v73, v76, v77, v78, 0, 3, 4) -> f_184(v68, v69, v70, v71, v72, v75, 1, v73, v76, v77, v78, 0, 3, 4) :|: TRUE f_184(v68, v69, v70, v71, v72, v75, 1, v73, v76, v77, v78, 0, 3, 4) -> f_188(v68, v69, v70, v71, v72, v75, 1, v76, v77, v78, 0, 3, 4) :|: 0 = 0 f_188(v68, v69, v70, v71, v72, v75, 1, v76, v77, v78, 0, 3, 4) -> f_192(v68, v69, v70, v71, v72, v75, 1, v89, v76, v77, v78, 0, 3, 4) :|: 1 + v89 = v75 && 0 <= 1 + v89 f_192(v68, v69, v70, v71, v72, v75, 1, v89, v76, v77, v78, 0, 3, 4) -> f_197(v68, v69, v70, v71, v72, v75, 1, v89, v76, v77, v78, 0, 3, 4) :|: TRUE f_197(v68, v69, v70, v71, v72, v75, 1, v89, v76, v77, v78, 0, 3, 4) -> f_201(v68, v69, v70, v71, v72, v75, 1, v89, v76, v77, v78, 0, 3, 4) :|: TRUE f_201(v68, v69, v70, v71, v72, v75, 1, v89, v76, v77, v78, 0, 3, 4) -> f_205(v68, v69, v70, v71, v72, v75, 1, v89, v76, v77, v78, 0, 3, 4) :|: TRUE f_205(v68, v69, v70, v71, v72, v75, 1, v89, v76, v77, v78, 0, 3, 4) -> f_173(v68, v69, v70, v71, v72, v75, 1, v89, v76, v77, v78, 0, 3, 4) :|: TRUE f_173(v68, v69, v70, v71, v72, v73, 1, v75, v76, v77, v78, 0, 3, 4) -> f_175(v68, v69, v70, v71, v72, v75, 1, v73, v76, v77, v78, 0, 3, 4) :|: 0 = 0 Combined rules. Obtained 1 rulesP rules: f_175(v68:0, v69:0, v70:0, v71:0, v72:0, 1 + v89:0, 1, v73:0, v76:0, v77:0, v78:0, 0, 3, 4) -> f_175(v68:0, v69:0, v70:0, v71:0, v72:0, v89:0, 1, 1 + v89:0, v76:0, v77:0, v78:0, 0, 3, 4) :|: v73:0 > 0 && v89:0 > -2 && v71:0 > 0 Filtered unneeded arguments: f_175(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14) -> f_175(x4, x6, x8) Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules: f_175(v71:0, sum~cons_1~v89:0, v73:0) -> f_175(v71:0, v89:0, 1 + v89:0) :|: v89:0 > -2 && v71:0 > 0 && v73:0 > 0 && sum~cons_1~v89:0 = 1 + v89:0 ---------------------------------------- (23) Obligation: Rules: f_175(v71:0, sum~cons_1~v89:0, v73:0) -> f_175(v71:0, v89:0, 1 + v89:0) :|: v89:0 > -2 && v71:0 > 0 && v73:0 > 0 && sum~cons_1~v89:0 = 1 + v89:0 ---------------------------------------- (24) IRS2T2 (EQUIVALENT) Transformed input IRS into an integer transition system.Used the following mapping from defined symbols to location IDs: (f_175_3,1) ---------------------------------------- (25) Obligation: START: 0; FROM: 0; TO: 1; FROM: 1; oldX0 := x0; oldX1 := x1; oldX2 := x2; oldX3 := oldX1 - 1; assume(oldX3 > -2 && oldX0 > 0 && oldX2 > 0 && oldX1 = 1 + oldX3); x0 := oldX0; x1 := oldX1 - 1; x2 := 1 + oldX3; TO: 1; ---------------------------------------- (26) T2 (EQUIVALENT) Initially, performed program simplifications using lexicographic rank functions: * Removed transitions 1, 3, 4 using the following rank functions: - Rank function 1: RF for loc. 5: 1+2*x1 RF for loc. 6: 2*x1 Bound for (chained) transitions 4: 0 - Rank function 2: RF for loc. 5: 1+2*x1 RF for loc. 6: 2*x1 Bound for (chained) transitions 3: 0 - Rank function 3: RF for loc. 5: 1 RF for loc. 6: 0 Bound for (chained) transitions 1: 1 ---------------------------------------- (27) YES