/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, 162 ms]
(2) LLVM problem
(3) LLVMToTerminationGraphProof [EQUIVALENT, 2573 ms]
(4) LLVM Symbolic Execution Graph
(5) SymbolicExecutionGraphToSCCProof [SOUND, 0 ms]
(6) LLVM Symbolic Execution SCC
(7) SCC2IRS [SOUND, 95 ms]
(8) IntTRS
(9) IntTRSCompressionProof [EQUIVALENT, 0 ms]
(10) IntTRS
(11) RankingReductionPairProof [EQUIVALENT, 23 ms]
(12) 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: "addition" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: (m i32, n i32) variableLength: false visibilityType: DEFAULT callingConvention: ccc
	0:
		%1 = alloca i32, align 4
		%2 = alloca i32, align 4
		%3 = alloca i32, align 4
		store %m, %2
		store %n, %3
		%4 = load %3
		%5 = icmp eq %4 0
		br %5, %6, %8
	6:
		%7 = load %2
		store %7, %1
		br %26
	8:
		%9 = load %3
		%10 = icmp sgt %9 0
		br %10, %11, %17
	11:
		%12 = load %2
		%13 = add %12 1
		%14 = load %3
		%15 = sub %14 1
		%16 = call i32 @addition(i32 %13, i32 %15)
		store %16, %1
		br %26
	17:
		%18 = load %3
		%19 = icmp slt %18 0
		br %19, %20, %26
	20:
		%21 = load %2
		%22 = sub %21 1
		%23 = load %3
		%24 = add %23 1
		%25 = call i32 @addition(i32 %22, i32 %24)
		store %25, %1
		br %26
	26:
		%27 = load %1
		ret %27

*BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc
	0:
		%1 = alloca i32, align 4
		%m = 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, %m
		%3 = load %m
		%4 = icmp sle %3 0
		br %4, %5, %6
	5:
		store 0, %1
		br %15
	6:
		%7 = call i32 @__VERIFIER_nondet_int()
		store %7, %n
		%8 = load %n
		%9 = icmp sle %8 0
		br %9, %10, %11
	10:
		store 0, %1
		br %15
	11:
		%12 = load %m
		%13 = load %n
		%14 = call i32 @addition(i32 %12, i32 %13)
		store %14, %result
		br %15
	15:
		%16 = load %1
		ret %16


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 19 rulesP rules:
f_260(v63, v64, v76, v65, v66, v67, v68, v69, v70, v71, v72, v77, 0, v74, v75, 3, 1, 4) -> f_261(v63, v64, v76, v78, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, 0, v74, v75, 3, 1, 4) :|: 1 <= v78 && v79 = 3 + v78 && 4 <= v79
f_261(v63, v64, v76, v78, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, 0, v74, v75, 3, 1, 4) -> f_262(v63, v64, v76, v78, v80, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, 0, v74, v75, 3, 1, 4) :|: 1 <= v80 && v81 = 3 + v80 && 4 <= v81
f_262(v63, v64, v76, v78, v80, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, 0, v74, v75, 3, 1, 4) -> f_263(v63, v64, v76, v78, v80, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, 0, v74, v75, 3, 1, 4) :|: TRUE
f_263(v63, v64, v76, v78, v80, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, 0, v74, v75, 3, 1, 4) -> f_264(v63, v64, v76, v78, v80, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, 0, v74, v75, 3, 1, 4) :|: TRUE
f_264(v63, v64, v76, v78, v80, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, 0, v74, v75, 3, 1, 4) -> f_265(v63, v64, v76, v78, v80, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, 0, v74, v75, 3, 1, 4) :|: 0 = 0
f_265(v63, v64, v76, v78, v80, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, 0, v74, v75, 3, 1, 4) -> f_267(v63, v64, v76, v78, v80, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, 0, v74, v75, 3, 1, 4) :|: v64 != 0
f_267(v63, v64, v76, v78, v80, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, 0, v74, v75, 3, 1, 4) -> f_269(v63, v64, v76, v78, v80, 0, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, v74, v75, 3, 1, 4) :|: 0 = 0
f_269(v63, v64, v76, v78, v80, 0, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, v74, v75, 3, 1, 4) -> f_271(v63, v64, v76, v78, v80, 0, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, v74, v75, 3, 1, 4) :|: TRUE
f_271(v63, v64, v76, v78, v80, 0, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, v74, v75, 3, 1, 4) -> f_273(v63, v64, v76, v78, v80, 0, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, v74, v75, 3, 1, 4) :|: 0 = 0
f_273(v63, v64, v76, v78, v80, 0, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, v74, v75, 3, 1, 4) -> f_275(v63, v64, v76, v78, v80, 0, 1, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, v74, v75, 3, 4) :|: 0 = 0
f_275(v63, v64, v76, v78, v80, 0, 1, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, v74, v75, 3, 4) -> f_277(v63, v64, v76, v78, v80, 0, 1, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, v74, v75, 3, 4) :|: TRUE
f_277(v63, v64, v76, v78, v80, 0, 1, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, v74, v75, 3, 4) -> f_279(v63, v64, v76, v78, v80, 0, 1, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, v74, v75, 3, 4) :|: 0 = 0
f_279(v63, v64, v76, v78, v80, 0, 1, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, v74, v75, 3, 4) -> f_281(v63, v64, v76, v78, v80, 0, 1, v102, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, v74, v75, 3, 4, 2) :|: v102 = 1 + v63 && 2 <= v102
f_281(v63, v64, v76, v78, v80, 0, 1, v102, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, v74, v75, 3, 4, 2) -> f_282(v63, v64, v76, v78, v80, 0, 1, v102, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, v74, v75, 3, 4, 2) :|: 0 = 0
f_282(v63, v64, v76, v78, v80, 0, 1, v102, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, v74, v75, 3, 4, 2) -> f_283(v63, v64, v76, v78, v80, 0, 1, v102, v103, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, v74, v75, 3, 4, 2) :|: 1 + v103 = v64 && 0 <= v103
f_283(v63, v64, v76, v78, v80, 0, 1, v102, v103, v65, v66, v67, v68, v69, v70, v71, v72, v77, v79, v81, v74, v75, 3, 4, 2) -> f_284(v102, v103, v65, v66, v67, v68, v69, v70, v71, v72, v76, v77, v78, v79, v80, v81, 0, v74, v75, v63, v64, 1, 3, 4, 2) :|: 0 = 0
f_284(v102, v103, v65, v66, v67, v68, v69, v70, v71, v72, v76, v77, v78, v79, v80, v81, 0, v74, v75, v63, v64, 1, 3, 4, 2) -> f_285(v102, v103, v65, v66, v67, v68, v69, v70, v71, v72, v76, v77, v78, v79, v80, v81, 0, v74, v75, v63, v64, 3, 1, 4, 2) :|: TRUE
f_285(v102, v103, v65, v66, v67, v68, v69, v70, v71, v72, v76, v77, v78, v79, v80, v81, 0, v74, v75, v63, v64, 3, 1, 4, 2) -> f_259(v102, v103, v65, v66, v67, v68, v69, v70, v71, v72, 0, v74, v75, 3, 1, 4) :|: TRUE
f_259(v63, v64, v65, v66, v67, v68, v69, v70, v71, v72, 0, v74, v75, 3, 1, 4) -> f_260(v63, v64, v76, v65, v66, v67, v68, v69, v70, v71, v72, v77, 0, v74, v75, 3, 1, 4) :|: 1 <= v76 && v77 = 3 + v76 && 4 <= v77
Combined rules. Obtained 1 rulesP rules:
f_260(v63:0, 1 + v103:0, v76:0, v65:0, v66:0, v67:0, v68:0, v69:0, v70:0, v71:0, v72:0, v77:0, 0, v74:0, v75:0, 3, 1, 4) -> f_260(1 + v63:0, v103:0, v76:1, v65:0, v66:0, v67:0, v68:0, v69:0, v70:0, v71:0, v72:0, 3 + v76:1, 0, v74:0, v75:0, 3, 1, 4) :|: v80:0 > 0 && v78:0 > 0 && v103:0 > -1 && v63:0 > 0 && v76:1 > 0
Filtered unneeded arguments:
   f_260(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) -> f_260(x1, x2)
Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules:
f_260(v63:0, sum~cons_1~v103:0) -> f_260(1 + v63:0, v103:0) :|: v103:0 > -1 && v63:0 > 0 && sum~cons_1~v103:0 = 1 + v103:0

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

(8)
Obligation:
Rules:
f_260(v63:0, sum~cons_1~v103:0) -> f_260(1 + v63:0, v103:0) :|: v103:0 > -1 && v63:0 > 0 && sum~cons_1~v103:0 = 1 + v103:0

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

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

(10)
Obligation:
Rules:
f_260(v63:0:0, sum~cons_1~v103:0:0) -> f_260(1 + v63:0:0, v103:0:0) :|: v103:0:0 > -1 && v63:0:0 > 0 && sum~cons_1~v103:0:0 = 1 + v103:0:0

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

(11) RankingReductionPairProof (EQUIVALENT)
Interpretation:
[ f_260 ] = f_260_2

The following rules are decreasing:
f_260(v63:0:0, sum~cons_1~v103:0:0) -> f_260(1 + v63:0:0, v103:0:0) :|: v103:0:0 > -1 && v63:0:0 > 0 && sum~cons_1~v103:0:0 = 1 + v103:0:0

The following rules are bounded:
f_260(v63:0:0, sum~cons_1~v103:0:0) -> f_260(1 + v63:0:0, v103:0:0) :|: v103:0:0 > -1 && v63:0:0 > 0 && sum~cons_1~v103:0:0 = 1 + v103:0:0


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

(12)
YES