/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, 179 ms]
(2) LLVM problem
(3) LLVMToTerminationGraphProof [EQUIVALENT, 1797 ms]
(4) LLVM Symbolic Execution Graph
(5) SymbolicExecutionGraphToSCCProof [SOUND, 0 ms]
(6) AND
    (7) LLVM Symbolic Execution SCC
        (8) SCC2IRS [SOUND, 53 ms]
        (9) IntTRS
        (10) IntTRSCompressionProof [EQUIVALENT, 0 ms]
        (11) IntTRS
        (12) RankingReductionPairProof [EQUIVALENT, 27 ms]
        (13) YES
    (14) LLVM Symbolic Execution SCC
        (15) SCC2IRS [SOUND, 23 ms]
        (16) IntTRS
        (17) IntTRSCompressionProof [EQUIVALENT, 0 ms]
        (18) IntTRS
        (19) RankingReductionPairProof [EQUIVALENT, 4 ms]
        (20) 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
		%i = alloca i32, align 4
		%c = alloca i32, align 4
		store 0, %1
		store 0, %i
		store 0, %c
		br %2
	2:
		%3 = load %i
		%4 = icmp slt %3 20
		br %4, %5, %14
	5:
		%6 = load %i
		%7 = add %6 1
		store %7, %i
		%8 = load %i
		%9 = icmp sle %8 10
		br %9, %10, %11
	10:
		br %2
	11:
		%12 = load %c
		%13 = add %12 1
		store %13, %c
		br %2
	14:
		%15 = load %c
		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 2 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 15 rulesP rules:
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
Combined rules. Obtained 1 rulesP rules:
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
Filtered unneeded arguments:
   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)
Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules:
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

----------------------------------------

(9)
Obligation:
Rules:
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

----------------------------------------

(10) IntTRSCompressionProof (EQUIVALENT)
Compressed rules.
----------------------------------------

(11)
Obligation:
Rules:
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

----------------------------------------

(12) RankingReductionPairProof (EQUIVALENT)
Interpretation:
[ f_250 ] = -1*f_250_1

The following rules are decreasing:
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

The following rules are bounded:
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


----------------------------------------

(13)
YES

----------------------------------------

(14)
Obligation:
SCC
----------------------------------------

(15) SCC2IRS (SOUND)
Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 
Generated rules. Obtained 12 rulesP rules:
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
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
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
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
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
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
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
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
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
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
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
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
Combined rules. Obtained 1 rulesP rules:
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
Filtered unneeded arguments:
   f_152(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14) -> f_152(x4)
Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules:
f_152(v60:0) -> f_152(1 + v60:0) :|: v60:0 < 11 && v60:0 < 10 && v60:0 > 0

----------------------------------------

(16)
Obligation:
Rules:
f_152(v60:0) -> f_152(1 + v60:0) :|: v60:0 < 11 && v60:0 < 10 && v60:0 > 0

----------------------------------------

(17) IntTRSCompressionProof (EQUIVALENT)
Compressed rules.
----------------------------------------

(18)
Obligation:
Rules:
f_152(v60:0:0) -> f_152(1 + v60:0:0) :|: v60:0:0 < 11 && v60:0:0 < 10 && v60:0:0 > 0

----------------------------------------

(19) RankingReductionPairProof (EQUIVALENT)
Interpretation:
[ f_152 ] = -1*f_152_1

The following rules are decreasing:
f_152(v60:0:0) -> f_152(1 + v60:0:0) :|: v60:0:0 < 11 && v60:0:0 < 10 && v60:0:0 > 0

The following rules are bounded:
f_152(v60:0:0) -> f_152(1 + v60:0:0) :|: v60:0:0 < 11 && v60:0:0 < 10 && v60:0:0 > 0


----------------------------------------

(20)
YES