12.27/4.62	YES
12.67/6.42	proof of /export/starexec/sandbox/benchmark/theBenchmark.c
12.67/6.42	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
12.67/6.42	
12.67/6.42	
12.67/6.42	Termination of the given C Problem could be proven:
12.67/6.42	
12.67/6.42	(0) C Problem
12.67/6.42	(1) CToLLVMProof [EQUIVALENT, 174 ms]
12.67/6.42	(2) LLVM problem
12.67/6.42	(3) LLVMToTerminationGraphProof [EQUIVALENT, 1188 ms]
12.67/6.42	(4) LLVM Symbolic Execution Graph
12.67/6.42	(5) SymbolicExecutionGraphToSCCProof [SOUND, 0 ms]
12.67/6.42	(6) LLVM Symbolic Execution SCC
12.67/6.42	(7) SCC2IRS [SOUND, 46 ms]
12.67/6.42	(8) IntTRS
12.67/6.42	(9) IRS2T2 [EQUIVALENT, 0 ms]
12.67/6.42	(10) T2IntSys
12.67/6.42	(11) T2 [EQUIVALENT, 1066 ms]
12.67/6.42	(12) YES
12.67/6.42	
12.67/6.42	
12.67/6.42	----------------------------------------
12.67/6.42	
12.67/6.42	(0)
12.67/6.42	Obligation:
12.67/6.42	c file /export/starexec/sandbox/benchmark/theBenchmark.c
12.67/6.42	----------------------------------------
12.67/6.42	
12.67/6.42	(1) CToLLVMProof (EQUIVALENT)
12.67/6.42	Compiled c-file /export/starexec/sandbox/benchmark/theBenchmark.c to LLVM.
12.67/6.42	----------------------------------------
12.67/6.42	
12.67/6.42	(2)
12.67/6.42	Obligation:
12.67/6.42	LLVM Problem
12.67/6.42	
12.67/6.42	Aliases:
12.67/6.42	
12.67/6.42	Data layout:
12.67/6.42	
12.67/6.42	"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"
12.67/6.42	
12.67/6.42	Machine:
12.67/6.42	
12.67/6.42	"x86_64-pc-linux-gnu"
12.67/6.42	
12.67/6.42	Type definitions:
12.67/6.42	
12.67/6.42	Global variables:
12.67/6.42	
12.67/6.42	Function declarations and definitions:
12.67/6.42	
12.67/6.42	*BasicFunctionTypename: "__VERIFIER_nondet_int" returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc
12.67/6.42	*BasicFunctionTypename: "test_fun" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: (x i32, y i32) variableLength: false visibilityType: DEFAULT callingConvention: ccc
12.67/6.42		0:
12.67/6.42			%1 = alloca i32, align 4
12.67/6.42			%2 = alloca i32, align 4
12.67/6.42			%c = alloca i32, align 4
12.67/6.42			store %x, %1
12.67/6.42			store %y, %2
12.67/6.42			store 0, %c
12.67/6.42			br %3
12.67/6.42		3:
12.67/6.42			%4 = load %1
12.67/6.42			%5 = load %2
12.67/6.42			%6 = icmp sgt %4 %5
12.67/6.42			br %6, %7, %12
12.67/6.42		7:
12.67/6.42			%8 = load %2
12.67/6.42			%9 = add %8 1
12.67/6.42			store %9, %2
12.67/6.42			%10 = load %c
12.67/6.42			%11 = add %10 1
12.67/6.42			store %11, %c
12.67/6.42			br %3
12.67/6.42		12:
12.67/6.42			%13 = load %c
12.67/6.42			ret %13
12.67/6.42	
12.67/6.42	*BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc
12.67/6.42		0:
12.67/6.42			%1 = alloca i32, align 4
12.67/6.42			store 0, %1
12.67/6.42			%2 = call i32 @__VERIFIER_nondet_int()
12.67/6.42			%3 = call i32 @__VERIFIER_nondet_int()
12.67/6.42			%4 = call i32 @test_fun(i32 %2, i32 %3)
12.67/6.42			ret %4
12.67/6.42	
12.67/6.42	
12.67/6.42	Analyze Termination of all function calls matching the pattern:
12.67/6.42	main()
12.67/6.42	----------------------------------------
12.67/6.42	
12.67/6.42	(3) LLVMToTerminationGraphProof (EQUIVALENT)
12.67/6.42	Constructed symbolic execution graph for LLVM program and proved memory safety.
12.67/6.42	----------------------------------------
12.67/6.42	
12.67/6.42	(4)
12.67/6.42	Obligation:
12.67/6.42	SE Graph
12.67/6.42	----------------------------------------
12.67/6.42	
12.67/6.42	(5) SymbolicExecutionGraphToSCCProof (SOUND)
12.67/6.42	Splitted symbolic execution graph to 1 SCC.
12.67/6.42	----------------------------------------
12.67/6.42	
12.67/6.42	(6)
12.67/6.42	Obligation:
12.67/6.42	SCC
12.67/6.42	----------------------------------------
12.67/6.42	
12.67/6.42	(7) SCC2IRS (SOUND)
12.67/6.42	Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 
12.67/6.42	Generated rules. Obtained 13 rulesP rules:
12.67/6.42	f_202(v97, v98, v99, v100, v101, v102, 1, v104, v105, v106, v107, v108, v109, v110, v111, 0, 3, 4) -> f_203(v97, v98, v99, v100, v101, v104, 1, v102, v105, v106, v107, v108, v109, v110, v111, 0, 3, 4) :|: 0 = 0
12.67/6.42	f_203(v97, v98, v99, v100, v101, v104, 1, v102, v105, v106, v107, v108, v109, v110, v111, 0, 3, 4) -> f_204(v97, v98, v99, v100, v101, v104, 1, v102, v105, v106, v107, v108, v109, v110, v111, 0, 3, 4) :|: v104 < v97
12.67/6.42	f_204(v97, v98, v99, v100, v101, v104, 1, v102, v105, v106, v107, v108, v109, v110, v111, 0, 3, 4) -> f_206(v97, v98, v99, v100, v101, v104, 1, v102, v105, v106, v107, v108, v109, v110, v111, 0, 3, 4) :|: 0 = 0
12.67/6.42	f_206(v97, v98, v99, v100, v101, v104, 1, v102, v105, v106, v107, v108, v109, v110, v111, 0, 3, 4) -> f_208(v97, v98, v99, v100, v101, v104, 1, v102, v105, v106, v107, v108, v109, v110, v111, 0, 3, 4) :|: TRUE
12.67/6.42	f_208(v97, v98, v99, v100, v101, v104, 1, v102, v105, v106, v107, v108, v109, v110, v111, 0, 3, 4) -> f_210(v97, v98, v99, v100, v101, v104, 1, v105, v106, v107, v108, v109, v110, v111, 0, 3, 4) :|: 0 = 0
12.67/6.42	f_210(v97, v98, v99, v100, v101, v104, 1, v105, v106, v107, v108, v109, v110, v111, 0, 3, 4) -> f_212(v97, v98, v99, v100, v101, v104, 1, v113, v105, v106, v107, v108, v109, v110, v111, 0, 3, 4) :|: v113 = 1 + v104
12.67/6.42	f_212(v97, v98, v99, v100, v101, v104, 1, v113, v105, v106, v107, v108, v109, v110, v111, 0, 3, 4) -> f_214(v97, v98, v99, v100, v101, v104, 1, v113, v105, v106, v107, v108, v109, v110, v111, 0, 3, 4) :|: TRUE
12.67/6.42	f_214(v97, v98, v99, v100, v101, v104, 1, v113, v105, v106, v107, v108, v109, v110, v111, 0, 3, 4) -> f_215(v97, v98, v99, v100, v101, v104, 1, v113, v106, v107, v108, v109, v110, v111, 0, 3, 4) :|: 0 = 0
12.67/6.42	f_215(v97, v98, v99, v100, v101, v104, 1, v113, v106, v107, v108, v109, v110, v111, 0, 3, 4) -> f_216(v97, v98, v99, v100, v101, v104, 1, v113, v106, v115, v107, v108, v109, v110, v111, 0, 3, 4, 2) :|: v115 = 1 + v106 && 2 <= v115
12.67/6.42	f_216(v97, v98, v99, v100, v101, v104, 1, v113, v106, v115, v107, v108, v109, v110, v111, 0, 3, 4, 2) -> f_217(v97, v98, v99, v100, v101, v104, 1, v113, v106, v115, v107, v108, v109, v110, v111, 0, 3, 4, 2) :|: TRUE
12.67/6.42	f_217(v97, v98, v99, v100, v101, v104, 1, v113, v106, v115, v107, v108, v109, v110, v111, 0, 3, 4, 2) -> f_218(v97, v98, v99, v100, v101, v104, 1, v113, v106, v115, v107, v108, v109, v110, v111, 0, 3, 4, 2) :|: TRUE
12.67/6.42	f_218(v97, v98, v99, v100, v101, v104, 1, v113, v106, v115, v107, v108, v109, v110, v111, 0, 3, 4, 2) -> f_201(v97, v98, v99, v100, v101, v104, 1, v113, v106, v115, v107, v108, v109, v110, v111, 0, 3, 4) :|: TRUE
12.67/6.42	f_201(v97, v98, v99, v100, v101, v102, 1, v104, v105, v106, v107, v108, v109, v110, v111, 0, 3, 4) -> f_202(v97, v98, v99, v100, v101, v102, 1, v104, v105, v106, v107, v108, v109, v110, v111, 0, 3, 4) :|: 0 = 0
12.67/6.42	Combined rules. Obtained 1 rulesP rules:
12.67/6.42	f_202(v97:0, v98:0, v99:0, v100:0, v101:0, v102:0, 1, v104:0, v105:0, v106:0, v107:0, v108:0, v109:0, v110:0, v111:0, 0, 3, 4) -> f_202(v97:0, v98:0, v99:0, v100:0, v101:0, v104:0, 1, 1 + v104:0, v106:0, 1 + v106:0, v107:0, v108:0, v109:0, v110:0, v111:0, 0, 3, 4) :|: v106:0 > 0 && v97:0 > v104:0
12.67/6.42	Filtered unneeded arguments:
12.67/6.42	   f_202(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) -> f_202(x1, x8, x10)
12.67/6.42	Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules:
12.67/6.42	f_202(v97:0, v104:0, v106:0) -> f_202(v97:0, 1 + v104:0, 1 + v106:0) :|: v106:0 > 0 && v97:0 > v104:0
12.67/6.42	
12.67/6.42	----------------------------------------
12.67/6.42	
12.67/6.42	(8)
12.67/6.42	Obligation:
12.67/6.42	Rules:
12.67/6.42	f_202(v97:0, v104:0, v106:0) -> f_202(v97:0, 1 + v104:0, 1 + v106:0) :|: v106:0 > 0 && v97:0 > v104:0
12.67/6.42	
12.67/6.42	----------------------------------------
12.67/6.42	
12.67/6.42	(9) IRS2T2 (EQUIVALENT)
12.67/6.42	Transformed input IRS into an integer transition system.Used the following mapping from defined symbols to location IDs:
12.67/6.42	
12.67/6.42	   (f_202_3,1)
12.67/6.42	
12.67/6.42	----------------------------------------
12.67/6.42	
12.67/6.42	(10)
12.67/6.42	Obligation:
12.67/6.42	START: 0;
12.67/6.42	
12.67/6.42	FROM: 0;
12.67/6.42	TO: 1;
12.67/6.42	
12.67/6.42	FROM: 1;
12.67/6.42	oldX0 := x0;
12.67/6.42	oldX1 := x1;
12.67/6.42	oldX2 := x2;
12.67/6.42	assume(oldX2 > 0 && oldX0 > oldX1);
12.67/6.42	x0 := oldX0;
12.67/6.42	x1 := 1 + oldX1;
12.67/6.42	x2 := 1 + oldX2;
12.67/6.42	TO: 1;
12.67/6.42	
12.67/6.42	
12.67/6.42	----------------------------------------
12.67/6.42	
12.67/6.42	(11) T2 (EQUIVALENT)
12.67/6.42	Initially, performed program simplifications using lexicographic rank functions:
12.67/6.42	 * Removed transitions 1, 3, 4 using the following rank functions:
12.67/6.42	    - Rank function 1:
12.67/6.42	      RF for loc. 5: 1+2*x0-2*x1
12.67/6.42	      RF for loc. 6: 2*x0-2*x1
12.67/6.42	      Bound for (chained) transitions 3: 2
12.67/6.42	    - Rank function 2:
12.67/6.42	      RF for loc. 5: 1+2*x0-2*x1
12.67/6.42	      RF for loc. 6: 2*x0-2*x1
12.67/6.42	      Bound for (chained) transitions 4: 2
12.67/6.42	    - Rank function 3:
12.67/6.42	      RF for loc. 5: 0
12.67/6.42	      RF for loc. 6: -1
12.67/6.42	      Bound for (chained) transitions 1: 0
12.67/6.42	
12.67/6.42	----------------------------------------
12.67/6.42	
12.67/6.42	(12)
12.67/6.42	YES
12.69/8.28	EOF