14.35/4.78 YES 14.35/4.79 proof of /export/starexec/sandbox/benchmark/theBenchmark.c 14.35/4.79 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 14.35/4.79 14.35/4.79 14.35/4.79 Termination of the given C Problem could be proven: 14.35/4.79 14.35/4.79 (0) C Problem 14.35/4.79 (1) CToLLVMProof [EQUIVALENT, 170 ms] 14.35/4.79 (2) LLVM problem 14.35/4.79 (3) LLVMToTerminationGraphProof [EQUIVALENT, 1399 ms] 14.35/4.79 (4) LLVM Symbolic Execution Graph 14.35/4.79 (5) SymbolicExecutionGraphToSCCProof [SOUND, 0 ms] 14.35/4.79 (6) AND 14.35/4.79 (7) LLVM Symbolic Execution SCC 14.35/4.79 (8) SCC2IRS [SOUND, 53 ms] 14.35/4.79 (9) IntTRS 14.35/4.79 (10) IntTRSCompressionProof [EQUIVALENT, 0 ms] 14.35/4.79 (11) IntTRS 14.35/4.79 (12) RankingReductionPairProof [EQUIVALENT, 26 ms] 14.35/4.79 (13) YES 14.35/4.79 (14) LLVM Symbolic Execution SCC 14.35/4.79 (15) SCC2IRS [SOUND, 66 ms] 14.35/4.79 (16) IntTRS 14.35/4.79 (17) IntTRSCompressionProof [EQUIVALENT, 0 ms] 14.35/4.79 (18) IntTRS 14.35/4.79 (19) RankingReductionPairProof [EQUIVALENT, 4 ms] 14.35/4.79 (20) YES 14.35/4.79 14.35/4.79 14.35/4.79 ---------------------------------------- 14.35/4.79 14.35/4.79 (0) 14.35/4.79 Obligation: 14.35/4.79 c file /export/starexec/sandbox/benchmark/theBenchmark.c 14.35/4.79 ---------------------------------------- 14.35/4.79 14.35/4.79 (1) CToLLVMProof (EQUIVALENT) 14.35/4.79 Compiled c-file /export/starexec/sandbox/benchmark/theBenchmark.c to LLVM. 14.35/4.79 ---------------------------------------- 14.35/4.79 14.35/4.79 (2) 14.35/4.79 Obligation: 14.35/4.79 LLVM Problem 14.35/4.79 14.35/4.79 Aliases: 14.35/4.79 14.35/4.79 Data layout: 14.35/4.79 14.35/4.79 "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" 14.35/4.79 14.35/4.79 Machine: 14.35/4.79 14.35/4.79 "x86_64-pc-linux-gnu" 14.35/4.79 14.35/4.79 Type definitions: 14.35/4.79 14.35/4.79 Global variables: 14.35/4.79 14.35/4.79 Function declarations and definitions: 14.35/4.79 14.35/4.79 *BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc 14.35/4.79 0: 14.35/4.79 %1 = alloca i32, align 4 14.35/4.79 %i = alloca i32, align 4 14.35/4.79 %c = alloca i32, align 4 14.35/4.79 store 0, %1 14.35/4.79 store 0, %i 14.35/4.79 store 0, %c 14.35/4.79 br %2 14.35/4.79 2: 14.35/4.79 %3 = load %i 14.35/4.79 %4 = icmp slt %3 20 14.35/4.79 br %4, %5, %14 14.35/4.79 5: 14.35/4.79 %6 = load %i 14.35/4.79 %7 = add %6 1 14.35/4.79 store %7, %i 14.35/4.79 %8 = load %i 14.35/4.79 %9 = icmp sle %8 10 14.35/4.79 br %9, %10, %11 14.35/4.79 10: 14.35/4.79 br %2 14.35/4.79 11: 14.35/4.79 %12 = load %c 14.35/4.79 %13 = add %12 1 14.35/4.79 store %13, %c 14.35/4.79 br %2 14.35/4.79 14: 14.35/4.79 %15 = load %c 14.35/4.79 ret %15 14.35/4.79 14.35/4.79 14.35/4.79 Analyze Termination of all function calls matching the pattern: 14.35/4.79 main() 14.35/4.79 ---------------------------------------- 14.35/4.79 14.35/4.79 (3) LLVMToTerminationGraphProof (EQUIVALENT) 14.35/4.79 Constructed symbolic execution graph for LLVM program and proved memory safety. 14.35/4.79 ---------------------------------------- 14.35/4.79 14.35/4.79 (4) 14.35/4.79 Obligation: 14.35/4.79 SE Graph 14.35/4.79 ---------------------------------------- 14.35/4.79 14.35/4.79 (5) SymbolicExecutionGraphToSCCProof (SOUND) 14.35/4.79 Splitted symbolic execution graph to 2 SCCs. 14.35/4.79 ---------------------------------------- 14.35/4.79 14.35/4.79 (6) 14.35/4.79 Complex Obligation (AND) 14.35/4.79 14.35/4.79 ---------------------------------------- 14.35/4.79 14.35/4.79 (7) 14.35/4.79 Obligation: 14.35/4.79 SCC 14.35/4.79 ---------------------------------------- 14.35/4.79 14.35/4.79 (8) SCC2IRS (SOUND) 14.35/4.79 Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 14.35/4.79 Generated rules. Obtained 15 rulesP rules: 14.35/4.79 f_250(v214, v215, v216, v219, 1, v217, 0, v221, v222, v223, v224, v225, 3, 10, 19, 11, 20, 9, 4) -> f_251(v214, v215, v216, v219, 1, v217, 0, v221, v222, v223, v224, v225, 3, 10, 18, 11, 19, 8, 9, 4) :|: v219 < 20 && v217 <= 18 && v221 <= 8 && v222 <= 9 14.35/4.79 f_251(v214, v215, v216, v219, 1, v217, 0, v221, v222, v223, v224, v225, 3, 10, 18, 11, 19, 8, 9, 4) -> f_253(v214, v215, v216, v219, 1, v217, 0, v221, v222, v223, v224, v225, 3, 10, 18, 11, 19, 8, 9, 4) :|: 0 = 0 14.35/4.79 f_253(v214, v215, v216, v219, 1, v217, 0, v221, v222, v223, v224, v225, 3, 10, 18, 11, 19, 8, 9, 4) -> f_255(v214, v215, v216, v219, 1, v217, 0, v221, v222, v223, v224, v225, 3, 10, 18, 11, 19, 8, 9, 4) :|: TRUE 14.35/4.79 f_255(v214, v215, v216, v219, 1, v217, 0, v221, v222, v223, v224, v225, 3, 10, 18, 11, 19, 8, 9, 4) -> f_257(v214, v215, v216, v219, 1, 0, v221, v222, v223, v224, v225, 3, 11, 19, 8, 9, 4) :|: 0 = 0 14.35/4.79 f_257(v214, v215, v216, v219, 1, 0, v221, v222, v223, v224, v225, 3, 11, 19, 8, 9, 4) -> f_259(v214, v215, v216, v219, 1, v229, 0, v221, v222, v223, v224, v225, 3, 11, 19, 8, 9, 4, 12, 20) :|: v229 = 1 + v219 && 12 <= v229 && v229 <= 20 14.35/4.79 f_259(v214, v215, v216, v219, 1, v229, 0, v221, v222, v223, v224, v225, 3, 11, 19, 8, 9, 4, 12, 20) -> f_260(v214, v215, v216, v219, 1, v229, 0, v221, v222, v223, v224, v225, 3, 11, 19, 8, 9, 4, 12, 20) :|: TRUE 14.35/4.79 f_260(v214, v215, v216, v219, 1, v229, 0, v221, v222, v223, v224, v225, 3, 11, 19, 8, 9, 4, 12, 20) -> f_261(v214, v215, v216, v219, 1, v229, 0, v221, v222, v223, v224, v225, 3, 11, 19, 8, 9, 4, 12, 20) :|: 0 = 0 14.35/4.79 f_261(v214, v215, v216, v219, 1, v229, 0, v221, v222, v223, v224, v225, 3, 11, 19, 8, 9, 4, 12, 20) -> f_262(v214, v215, v216, v219, 1, v229, 0, v221, v222, v223, v224, v225, 3, 11, 19, 8, 9, 4, 12, 20) :|: 0 = 0 14.35/4.79 f_262(v214, v215, v216, v219, 1, v229, 0, v221, v222, v223, v224, v225, 3, 11, 19, 8, 9, 4, 12, 20) -> f_263(v214, v215, v216, v219, 1, v229, 0, v221, v222, v223, v224, v225, 3, 11, 19, 8, 9, 4, 12, 20) :|: TRUE 14.35/4.79 f_263(v214, v215, v216, v219, 1, v229, 0, v221, v222, v223, v224, v225, 3, 11, 19, 8, 9, 4, 12, 20) -> f_264(v214, v215, v216, v219, 1, v229, 0, v222, v223, v224, v225, 3, 10, 11, 19, 9, 4, 12, 20) :|: 0 = 0 14.35/4.79 f_264(v214, v215, v216, v219, 1, v229, 0, v222, v223, v224, v225, 3, 10, 11, 19, 9, 4, 12, 20) -> f_265(v214, v215, v216, v219, 1, v229, 0, v222, v234, v223, v224, v225, 3, 10, 11, 19, 9, 4, 12, 20, 2) :|: v234 = 1 + v222 && 2 <= v234 && v234 <= 10 14.35/4.79 f_265(v214, v215, v216, v219, 1, v229, 0, v222, v234, v223, v224, v225, 3, 10, 11, 19, 9, 4, 12, 20, 2) -> f_266(v214, v215, v216, v219, 1, v229, 0, v222, v234, v223, v224, v225, 3, 10, 11, 19, 9, 4, 12, 20, 2) :|: TRUE 14.35/4.79 f_266(v214, v215, v216, v219, 1, v229, 0, v222, v234, v223, v224, v225, 3, 10, 11, 19, 9, 4, 12, 20, 2) -> f_267(v214, v215, v216, v219, 1, v229, 0, v222, v234, v223, v224, v225, 3, 10, 11, 19, 9, 4, 12, 20, 2) :|: TRUE 14.35/4.79 f_267(v214, v215, v216, v219, 1, v229, 0, v222, v234, v223, v224, v225, 3, 10, 11, 19, 9, 4, 12, 20, 2) -> f_249(v214, v215, v216, v219, 1, v229, 0, v222, v234, v223, v224, v225, 3, 10, 19, 11, 20, 9, 4) :|: TRUE 14.35/4.79 f_249(v214, v215, v216, v217, 1, v219, 0, v221, v222, v223, v224, v225, 3, 10, 19, 11, 20, 9, 4) -> f_250(v214, v215, v216, v219, 1, v217, 0, v221, v222, v223, v224, v225, 3, 10, 19, 11, 20, 9, 4) :|: 0 = 0 14.35/4.79 Combined rules. Obtained 1 rulesP rules: 14.35/4.79 f_250(v214:0, v215:0, v216:0, v219:0, 1, v217:0, 0, v221:0, v222:0, v223:0, v224:0, v225:0, 3, 10, 19, 11, 20, 9, 4) -> f_250(v214:0, v215:0, v216:0, 1 + v219:0, 1, v219:0, 0, v222:0, 1 + v222:0, v223:0, v224:0, v225:0, 3, 10, 19, 11, 20, 9, 4) :|: v217:0 < 19 && v219:0 < 20 && v221:0 < 9 && v222:0 < 10 && v219:0 > 10 && v222:0 > 0 14.35/4.79 Filtered unneeded arguments: 14.35/4.79 f_250(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19) -> f_250(x4, x6, x8, x9) 14.35/4.79 Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules: 14.35/4.79 f_250(v219:0, v217:0, v221:0, v222:0) -> f_250(1 + v219:0, v219:0, v222:0, 1 + v222:0) :|: v219:0 < 20 && v217:0 < 19 && v221:0 < 9 && v222:0 < 10 && v222:0 > 0 && v219:0 > 10 14.35/4.79 14.35/4.79 ---------------------------------------- 14.35/4.79 14.35/4.79 (9) 14.35/4.79 Obligation: 14.35/4.79 Rules: 14.35/4.79 f_250(v219:0, v217:0, v221:0, v222:0) -> f_250(1 + v219:0, v219:0, v222:0, 1 + v222:0) :|: v219:0 < 20 && v217:0 < 19 && v221:0 < 9 && v222:0 < 10 && v222:0 > 0 && v219:0 > 10 14.35/4.79 14.35/4.79 ---------------------------------------- 14.35/4.79 14.35/4.79 (10) IntTRSCompressionProof (EQUIVALENT) 14.35/4.79 Compressed rules. 14.35/4.79 ---------------------------------------- 14.35/4.79 14.35/4.79 (11) 14.35/4.79 Obligation: 14.35/4.79 Rules: 14.35/4.79 f_250(v219:0:0, v217:0:0, v221:0:0, v222:0:0) -> f_250(1 + v219:0:0, v219:0:0, v222:0:0, 1 + v222:0:0) :|: v222:0:0 > 0 && v219:0:0 > 10 && v222:0:0 < 10 && v221:0:0 < 9 && v217:0:0 < 19 && v219:0:0 < 20 14.35/4.79 14.35/4.79 ---------------------------------------- 14.35/4.79 14.35/4.79 (12) RankingReductionPairProof (EQUIVALENT) 14.35/4.79 Interpretation: 14.35/4.79 [ f_250 ] = -1*f_250_1 14.35/4.79 14.35/4.79 The following rules are decreasing: 14.35/4.79 f_250(v219:0:0, v217:0:0, v221:0:0, v222:0:0) -> f_250(1 + v219:0:0, v219:0:0, v222:0:0, 1 + v222:0:0) :|: v222:0:0 > 0 && v219:0:0 > 10 && v222:0:0 < 10 && v221:0:0 < 9 && v217:0:0 < 19 && v219:0:0 < 20 14.35/4.79 14.35/4.79 The following rules are bounded: 14.35/4.79 f_250(v219:0:0, v217:0:0, v221:0:0, v222:0:0) -> f_250(1 + v219:0:0, v219:0:0, v222:0:0, 1 + v222:0:0) :|: v222:0:0 > 0 && v219:0:0 > 10 && v222:0:0 < 10 && v221:0:0 < 9 && v217:0:0 < 19 && v219:0:0 < 20 14.35/4.79 14.35/4.79 14.35/4.79 ---------------------------------------- 14.35/4.79 14.35/4.79 (13) 14.35/4.79 YES 14.35/4.79 14.35/4.79 ---------------------------------------- 14.35/4.79 14.35/4.79 (14) 14.35/4.79 Obligation: 14.35/4.79 SCC 14.35/4.79 ---------------------------------------- 14.35/4.79 14.35/4.79 (15) SCC2IRS (SOUND) 14.35/4.79 Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 14.35/4.79 Generated rules. Obtained 12 rulesP rules: 14.35/4.79 f_152(v55, v56, v57, v60, 1, v58, v61, v62, v63, 0, 3, 9, 10, 4) -> f_153(v55, v56, v57, v60, 1, v58, v61, v62, v63, 0, 3, 9, 10, 4) :|: 0 = 0 14.35/4.79 f_153(v55, v56, v57, v60, 1, v58, v61, v62, v63, 0, 3, 9, 10, 4) -> f_154(v55, v56, v57, v60, 1, v58, v61, v62, v63, 0, 3, 9, 10, 4) :|: TRUE 14.35/4.79 f_154(v55, v56, v57, v60, 1, v58, v61, v62, v63, 0, 3, 9, 10, 4) -> f_155(v55, v56, v57, v60, 1, v61, v62, v63, 0, 3, 10, 4) :|: 0 = 0 14.35/4.79 f_155(v55, v56, v57, v60, 1, v61, v62, v63, 0, 3, 10, 4) -> f_156(v55, v56, v57, v60, 1, v65, v61, v62, v63, 0, 3, 10, 4, 2, 11) :|: v65 = 1 + v60 && 2 <= v65 && v65 <= 11 14.35/4.79 f_156(v55, v56, v57, v60, 1, v65, v61, v62, v63, 0, 3, 10, 4, 2, 11) -> f_157(v55, v56, v57, v60, 1, v65, v61, v62, v63, 0, 3, 10, 4, 2, 11) :|: TRUE 14.35/4.79 f_157(v55, v56, v57, v60, 1, v65, v61, v62, v63, 0, 3, 10, 4, 2, 11) -> f_158(v55, v56, v57, v60, 1, v65, v61, v62, v63, 0, 3, 10, 4, 2, 11) :|: 0 = 0 14.35/4.79 f_158(v55, v56, v57, v60, 1, v65, v61, v62, v63, 0, 3, 10, 4, 2, 11) -> f_159(v55, v56, v57, v60, 1, v65, v61, v62, v63, 0, 3, 9, 4, 2, 10) :|: v65 <= 10 && v60 <= 9 14.35/4.79 f_159(v55, v56, v57, v60, 1, v65, v61, v62, v63, 0, 3, 9, 4, 2, 10) -> f_161(v55, v56, v57, v60, 1, v65, v61, v62, v63, 0, 3, 9, 4, 2, 10) :|: 0 = 0 14.35/4.79 f_161(v55, v56, v57, v60, 1, v65, v61, v62, v63, 0, 3, 9, 4, 2, 10) -> f_163(v55, v56, v57, v60, 1, v65, v61, v62, v63, 0, 3, 9, 4, 2, 10) :|: TRUE 14.35/4.79 f_163(v55, v56, v57, v60, 1, v65, v61, v62, v63, 0, 3, 9, 4, 2, 10) -> f_165(v55, v56, v57, v60, 1, v65, v61, v62, v63, 0, 3, 9, 4, 2, 10) :|: TRUE 14.35/4.79 f_165(v55, v56, v57, v60, 1, v65, v61, v62, v63, 0, 3, 9, 4, 2, 10) -> f_151(v55, v56, v57, v60, 1, v65, v61, v62, v63, 0, 3, 9, 10, 4) :|: TRUE 14.35/4.79 f_151(v55, v56, v57, v58, 1, v60, v61, v62, v63, 0, 3, 9, 10, 4) -> f_152(v55, v56, v57, v60, 1, v58, v61, v62, v63, 0, 3, 9, 10, 4) :|: 0 = 0 14.35/4.79 Combined rules. Obtained 1 rulesP rules: 14.35/4.79 f_152(v55:0, v56:0, v57:0, v60:0, 1, v58:0, v61:0, v62:0, v63:0, 0, 3, 9, 10, 4) -> f_152(v55:0, v56:0, v57:0, 1 + v60:0, 1, v60:0, v61:0, v62:0, v63:0, 0, 3, 9, 10, 4) :|: v60:0 > 0 && v60:0 < 11 && v60:0 < 10 14.35/4.79 Filtered unneeded arguments: 14.35/4.79 f_152(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14) -> f_152(x4) 14.35/4.79 Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules: 14.35/4.79 f_152(v60:0) -> f_152(1 + v60:0) :|: v60:0 < 11 && v60:0 < 10 && v60:0 > 0 14.35/4.79 14.35/4.79 ---------------------------------------- 14.35/4.79 14.35/4.79 (16) 14.35/4.79 Obligation: 14.35/4.79 Rules: 14.35/4.79 f_152(v60:0) -> f_152(1 + v60:0) :|: v60:0 < 11 && v60:0 < 10 && v60:0 > 0 14.35/4.79 14.35/4.79 ---------------------------------------- 14.35/4.79 14.35/4.79 (17) IntTRSCompressionProof (EQUIVALENT) 14.35/4.79 Compressed rules. 14.35/4.79 ---------------------------------------- 14.35/4.79 14.35/4.79 (18) 14.35/4.79 Obligation: 14.35/4.79 Rules: 14.35/4.79 f_152(v60:0:0) -> f_152(1 + v60:0:0) :|: v60:0:0 < 11 && v60:0:0 < 10 && v60:0:0 > 0 14.35/4.79 14.35/4.79 ---------------------------------------- 14.35/4.79 14.35/4.79 (19) RankingReductionPairProof (EQUIVALENT) 14.35/4.79 Interpretation: 14.35/4.79 [ f_152 ] = -1*f_152_1 14.35/4.79 14.35/4.79 The following rules are decreasing: 14.35/4.79 f_152(v60:0:0) -> f_152(1 + v60:0:0) :|: v60:0:0 < 11 && v60:0:0 < 10 && v60:0:0 > 0 14.35/4.79 14.35/4.79 The following rules are bounded: 14.35/4.79 f_152(v60:0:0) -> f_152(1 + v60:0:0) :|: v60:0:0 < 11 && v60:0:0 < 10 && v60:0:0 > 0 14.35/4.79 14.35/4.79 14.35/4.79 ---------------------------------------- 14.35/4.79 14.35/4.79 (20) 14.35/4.79 YES 14.55/6.88 EOF