12.21/4.96	YES
12.40/5.33	proof of /export/starexec/sandbox/benchmark/theBenchmark.c
12.40/5.33	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
12.40/5.33	
12.40/5.33	
12.40/5.33	Termination of the given C Problem could be proven:
12.40/5.33	
12.40/5.33	(0) C Problem
12.40/5.33	(1) CToLLVMProof [EQUIVALENT, 175 ms]
12.40/5.33	(2) LLVM problem
12.40/5.33	(3) LLVMToTerminationGraphProof [EQUIVALENT, 1393 ms]
12.40/5.33	(4) LLVM Symbolic Execution Graph
12.40/5.33	(5) SymbolicExecutionGraphToSCCProof [SOUND, 0 ms]
12.40/5.33	(6) LLVM Symbolic Execution SCC
12.40/5.33	(7) SCC2IRS [SOUND, 64 ms]
12.40/5.33	(8) IntTRS
12.40/5.33	(9) IRS2T2 [EQUIVALENT, 4 ms]
12.40/5.33	(10) T2IntSys
12.40/5.33	(11) T2 [EQUIVALENT, 1124 ms]
12.40/5.33	(12) YES
12.40/5.33	
12.40/5.33	
12.40/5.33	----------------------------------------
12.40/5.33	
12.40/5.33	(0)
12.40/5.33	Obligation:
12.40/5.33	c file /export/starexec/sandbox/benchmark/theBenchmark.c
12.40/5.33	----------------------------------------
12.40/5.33	
12.40/5.33	(1) CToLLVMProof (EQUIVALENT)
12.40/5.33	Compiled c-file /export/starexec/sandbox/benchmark/theBenchmark.c to LLVM.
12.40/5.33	----------------------------------------
12.40/5.33	
12.40/5.33	(2)
12.40/5.33	Obligation:
12.40/5.33	LLVM Problem
12.40/5.33	
12.40/5.33	Aliases:
12.40/5.33	
12.40/5.33	Data layout:
12.40/5.33	
12.40/5.33	"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.40/5.33	
12.40/5.33	Machine:
12.40/5.33	
12.40/5.33	"x86_64-pc-linux-gnu"
12.40/5.33	
12.40/5.33	Type definitions:
12.40/5.33	
12.40/5.33	Global variables:
12.40/5.33	
12.40/5.33	Function declarations and definitions:
12.40/5.33	
12.40/5.33	*BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc
12.40/5.33		0:
12.40/5.33			%1 = alloca i32, align 4
12.40/5.33			%i = alloca *i32, align 8
12.40/5.33			%c = alloca *i32, align 8
12.40/5.33			store 0, %1
12.40/5.33			%2 = alloca i8, numElementsLit: 4
12.40/5.33			%3 = bitcast *i8 %2 to *i32
12.40/5.33			store %3, %i
12.40/5.33			%4 = alloca i8, numElementsLit: 4
12.40/5.33			%5 = bitcast *i8 %4 to *i32
12.40/5.33			store %5, %c
12.40/5.33			%6 = load %i
12.40/5.33			store 0, %6
12.40/5.33			%7 = load %c
12.40/5.33			store 0, %7
12.40/5.33			br %8
12.40/5.33		8:
12.40/5.33			%9 = load %i
12.40/5.33			%10 = load %9
12.40/5.33			%11 = icmp sgt %10 10
12.40/5.33			br %11, %12, %13
12.40/5.33		12:
12.40/5.33			br %20
12.40/5.33		13:
12.40/5.33			%14 = load %i
12.40/5.33			%15 = load %14
12.40/5.33			%16 = add %15 1
12.40/5.33			store %16, %14
12.40/5.33			%17 = load %c
12.40/5.33			%18 = load %17
12.40/5.33			%19 = add %18 1
12.40/5.33			store %19, %17
12.40/5.33			br %8
12.40/5.33		20:
12.40/5.33			%21 = load %c
12.40/5.33			%22 = load %21
12.40/5.33			ret %22
12.40/5.33	
12.40/5.33	
12.40/5.33	Analyze Termination of all function calls matching the pattern:
12.40/5.33	main()
12.40/5.33	----------------------------------------
12.40/5.33	
12.40/5.33	(3) LLVMToTerminationGraphProof (EQUIVALENT)
12.40/5.33	Constructed symbolic execution graph for LLVM program and proved memory safety.
12.40/5.33	----------------------------------------
12.40/5.33	
12.40/5.33	(4)
12.40/5.33	Obligation:
12.40/5.33	SE Graph
12.40/5.33	----------------------------------------
12.40/5.33	
12.40/5.33	(5) SymbolicExecutionGraphToSCCProof (SOUND)
12.40/5.33	Splitted symbolic execution graph to 1 SCC.
12.40/5.33	----------------------------------------
12.40/5.33	
12.40/5.33	(6)
12.40/5.33	Obligation:
12.40/5.33	SCC
12.40/5.33	----------------------------------------
12.40/5.33	
12.40/5.33	(7) SCC2IRS (SOUND)
12.40/5.33	Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 
12.40/5.33	Generated rules. Obtained 15 rulesP rules:
12.40/5.33	f_232(v93, v94, v95, v96, v97, v98, 0, v100, v101, v102, v103, v104, v105, 3, 7, 1, 4, 8) -> f_233(v93, v94, v95, v96, v97, v100, 0, v98, v101, v102, v103, v104, v105, 3, 7, 1, 4, 8) :|: 0 = 0
12.40/5.33	f_233(v93, v94, v95, v96, v97, v100, 0, v98, v101, v102, v103, v104, v105, 3, 7, 1, 4, 8) -> f_235(v93, v94, v95, v96, v97, v100, 0, v98, v101, v102, v103, v104, v105, 3, 7, 1, 9, 10, 4, 8) :|: v100 <= 10 && v98 <= 9
12.40/5.33	f_235(v93, v94, v95, v96, v97, v100, 0, v98, v101, v102, v103, v104, v105, 3, 7, 1, 9, 10, 4, 8) -> f_237(v93, v94, v95, v96, v97, v100, 0, v98, v101, v102, v103, v104, v105, 3, 7, 1, 9, 10, 4, 8) :|: 0 = 0
12.40/5.33	f_237(v93, v94, v95, v96, v97, v100, 0, v98, v101, v102, v103, v104, v105, 3, 7, 1, 9, 10, 4, 8) -> f_239(v93, v94, v95, v96, v97, v100, 0, v98, v101, v102, v103, v104, v105, 3, 7, 1, 9, 10, 4, 8) :|: TRUE
12.40/5.33	f_239(v93, v94, v95, v96, v97, v100, 0, v98, v101, v102, v103, v104, v105, 3, 7, 1, 9, 10, 4, 8) -> f_241(v93, v94, v95, v96, v97, v100, 0, v98, v101, v102, v103, v104, v105, 3, 7, 1, 9, 10, 4, 8) :|: 0 = 0
12.40/5.33	f_241(v93, v94, v95, v96, v97, v100, 0, v98, v101, v102, v103, v104, v105, 3, 7, 1, 9, 10, 4, 8) -> f_243(v93, v94, v95, v96, v97, v100, 0, v98, v101, v102, v103, v104, v105, 3, 7, 1, 9, 10, 4, 8) :|: 0 = 0
12.40/5.33	f_243(v93, v94, v95, v96, v97, v100, 0, v98, v101, v102, v103, v104, v105, 3, 7, 1, 9, 10, 4, 8) -> f_245(v93, v94, v95, v96, v97, v100, 0, v106, v98, v101, v102, v103, v104, v105, 3, 7, 1, 9, 10, 4, 8, 2, 11) :|: v106 = 1 + v100 && 2 <= v106 && v106 <= 11
12.40/5.33	f_245(v93, v94, v95, v96, v97, v100, 0, v106, v98, v101, v102, v103, v104, v105, 3, 7, 1, 9, 10, 4, 8, 2, 11) -> f_246(v93, v94, v95, v96, v97, v100, 0, v106, v98, v101, v102, v103, v104, v105, 3, 7, 1, 9, 10, 4, 8, 2, 11) :|: TRUE
12.40/5.33	f_246(v93, v94, v95, v96, v97, v100, 0, v106, v98, v101, v102, v103, v104, v105, 3, 7, 1, 9, 10, 4, 8, 2, 11) -> f_247(v93, v94, v95, v96, v97, v100, 0, v106, v98, v101, v102, v103, v104, v105, 3, 7, 1, 9, 10, 4, 8, 2, 11) :|: 0 = 0
12.40/5.33	f_247(v93, v94, v95, v96, v97, v100, 0, v106, v98, v101, v102, v103, v104, v105, 3, 7, 1, 9, 10, 4, 8, 2, 11) -> f_248(v93, v94, v95, v96, v97, v100, 0, v106, v101, v102, v103, v104, v105, 3, 7, 1, 10, 4, 8, 2, 11) :|: 0 = 0
12.40/5.33	f_248(v93, v94, v95, v96, v97, v100, 0, v106, v101, v102, v103, v104, v105, 3, 7, 1, 10, 4, 8, 2, 11) -> f_249(v93, v94, v95, v96, v97, v100, 0, v106, v101, v102, v103, v104, v105, 3, 7, 1, 10, 4, 8, 2, 11) :|: v106 = 1 + v100
12.40/5.33	f_249(v93, v94, v95, v96, v97, v100, 0, v106, v101, v102, v103, v104, v105, 3, 7, 1, 10, 4, 8, 2, 11) -> f_250(v93, v94, v95, v96, v97, v100, 0, v106, v101, v102, v103, v104, v105, 3, 7, 1, 10, 4, 8, 2, 11) :|: TRUE
12.40/5.33	f_250(v93, v94, v95, v96, v97, v100, 0, v106, v101, v102, v103, v104, v105, 3, 7, 1, 10, 4, 8, 2, 11) -> f_251(v93, v94, v95, v96, v97, v100, 0, v106, v101, v102, v103, v104, v105, 3, 7, 1, 10, 4, 8, 2, 11) :|: TRUE
12.40/5.33	f_251(v93, v94, v95, v96, v97, v100, 0, v106, v101, v102, v103, v104, v105, 3, 7, 1, 10, 4, 8, 2, 11) -> f_231(v93, v94, v95, v96, v97, v100, 0, v106, v101, v102, v103, v104, v105, 3, 7, 1, 4, 8) :|: TRUE
12.40/5.33	f_231(v93, v94, v95, v96, v97, v98, 0, v100, v101, v102, v103, v104, v105, 3, 7, 1, 4, 8) -> f_232(v93, v94, v95, v96, v97, v98, 0, v100, v101, v102, v103, v104, v105, 3, 7, 1, 4, 8) :|: 0 = 0
12.40/5.33	Combined rules. Obtained 1 rulesP rules:
12.40/5.33	f_232(v93:0, v94:0, v95:0, v96:0, v97:0, v98:0, 0, v100:0, v101:0, v102:0, v103:0, v104:0, v105:0, 3, 7, 1, 4, 8) -> f_232(v93:0, v94:0, v95:0, v96:0, v97:0, v100:0, 0, 1 + v100:0, v101:0, v102:0, v103:0, v104:0, v105:0, 3, 7, 1, 4, 8) :|: v98:0 < 10 && v100:0 < 11 && v100:0 > 0
12.40/5.33	Filtered unneeded arguments:
12.40/5.33	   f_232(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) -> f_232(x6, x8)
12.40/5.33	Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules:
12.40/5.33	f_232(v98:0, v100:0) -> f_232(v100:0, 1 + v100:0) :|: v100:0 < 11 && v100:0 > 0 && v98:0 < 10
12.40/5.33	
12.40/5.33	----------------------------------------
12.40/5.33	
12.40/5.33	(8)
12.40/5.33	Obligation:
12.40/5.33	Rules:
12.40/5.33	f_232(v98:0, v100:0) -> f_232(v100:0, 1 + v100:0) :|: v100:0 < 11 && v100:0 > 0 && v98:0 < 10
12.40/5.33	
12.40/5.33	----------------------------------------
12.40/5.33	
12.40/5.33	(9) IRS2T2 (EQUIVALENT)
12.40/5.33	Transformed input IRS into an integer transition system.Used the following mapping from defined symbols to location IDs:
12.40/5.33	
12.40/5.33	   (f_232_2,1)
12.40/5.33	
12.40/5.33	----------------------------------------
12.40/5.33	
12.40/5.33	(10)
12.40/5.33	Obligation:
12.40/5.33	START: 0;
12.40/5.33	
12.40/5.33	FROM: 0;
12.40/5.33	TO: 1;
12.40/5.33	
12.40/5.33	FROM: 1;
12.40/5.33	oldX0 := x0;
12.40/5.33	oldX1 := x1;
12.40/5.33	assume(oldX1 < 11 && oldX1 > 0 && oldX0 < 10);
12.40/5.33	x0 := oldX1;
12.40/5.33	x1 := 1 + oldX1;
12.40/5.33	TO: 1;
12.40/5.33	
12.40/5.33	
12.40/5.33	----------------------------------------
12.40/5.33	
12.40/5.33	(11) T2 (EQUIVALENT)
12.40/5.33	Initially, performed program simplifications using lexicographic rank functions:
12.40/5.33	 * Removed transitions 1, 3, 4 using the following rank functions:
12.40/5.33	    - Rank function 1:
12.40/5.33	      RF for loc. 5: 1-2*x1
12.40/5.33	      RF for loc. 6: -2*x1
12.40/5.33	      Bound for (chained) transitions 3: -20
12.40/5.33	      Bound for (chained) transitions 4: -20
12.40/5.33	    - Rank function 2:
12.40/5.33	      RF for loc. 5: 0
12.40/5.33	      RF for loc. 6: -1
12.40/5.33	      Bound for (chained) transitions 1: 0
12.40/5.33	
12.40/5.33	----------------------------------------
12.40/5.33	
12.40/5.33	(12)
12.40/5.33	YES
12.43/5.44	EOF