16.88/5.73	YES
16.88/5.74	proof of /export/starexec/sandbox/benchmark/theBenchmark.c
16.88/5.74	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
16.88/5.74	
16.88/5.74	
16.88/5.74	Termination of the given C Problem could be proven:
16.88/5.74	
16.88/5.74	(0) C Problem
16.88/5.74	(1) CToLLVMProof [EQUIVALENT, 175 ms]
16.88/5.74	(2) LLVM problem
16.88/5.74	(3) LLVMToTerminationGraphProof [EQUIVALENT, 2167 ms]
16.88/5.74	(4) LLVM Symbolic Execution Graph
16.88/5.74	(5) SymbolicExecutionGraphToSCCProof [SOUND, 0 ms]
16.88/5.74	(6) LLVM Symbolic Execution SCC
16.88/5.74	(7) SCC2IRS [SOUND, 77 ms]
16.88/5.74	(8) IntTRS
16.88/5.74	(9) IRS2T2 [EQUIVALENT, 0 ms]
16.88/5.74	(10) T2IntSys
16.88/5.74	(11) T2 [EQUIVALENT, 996 ms]
16.88/5.74	(12) YES
16.88/5.74	
16.88/5.74	
16.88/5.74	----------------------------------------
16.88/5.74	
16.88/5.74	(0)
16.88/5.74	Obligation:
16.88/5.74	c file /export/starexec/sandbox/benchmark/theBenchmark.c
16.88/5.74	----------------------------------------
16.88/5.74	
16.88/5.74	(1) CToLLVMProof (EQUIVALENT)
16.88/5.74	Compiled c-file /export/starexec/sandbox/benchmark/theBenchmark.c to LLVM.
16.88/5.74	----------------------------------------
16.88/5.74	
16.88/5.74	(2)
16.88/5.74	Obligation:
16.88/5.74	LLVM Problem
16.88/5.74	
16.88/5.74	Aliases:
16.88/5.74	
16.88/5.74	Data layout:
16.88/5.74	
16.88/5.74	"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"
16.88/5.74	
16.88/5.74	Machine:
16.88/5.74	
16.88/5.74	"x86_64-pc-linux-gnu"
16.88/5.74	
16.88/5.74	Type definitions:
16.88/5.74	
16.88/5.74	Global variables:
16.88/5.74	
16.88/5.74	Function declarations and definitions:
16.88/5.74	
16.88/5.74	*BasicFunctionTypename: "__VERIFIER_nondet_int" returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc
16.88/5.74	*BasicFunctionTypename: "__VERIFIER_error" returnParam: BasicVoidType parameters: () variableLength: true visibilityType: DEFAULT callingConvention: ccc
16.88/5.74	*BasicFunctionTypename: "isOdd" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: (n i32) variableLength: false visibilityType: DEFAULT callingConvention: ccc
16.88/5.74		0:
16.88/5.74			%1 = alloca i32, align 4
16.88/5.74			%2 = alloca i32, align 4
16.88/5.74			store %n, %2
16.88/5.74			%3 = load %2
16.88/5.74			%4 = icmp eq %3 0
16.88/5.74			br %4, %5, %6
16.88/5.74		5:
16.88/5.74			store 0, %1
16.88/5.74			br %14
16.88/5.74		6:
16.88/5.74			%7 = load %2
16.88/5.74			%8 = icmp eq %7 1
16.88/5.74			br %8, %9, %10
16.88/5.74		9:
16.88/5.74			store 1, %1
16.88/5.74			br %14
16.88/5.74		10:
16.88/5.74			%11 = load %2
16.88/5.74			%12 = sub %11 1
16.88/5.74			%13 = call i32 @isEven(i32 %12)
16.88/5.74			store %13, %1
16.88/5.74			br %14
16.88/5.74		14:
16.88/5.74			%15 = load %1
16.88/5.74			ret %15
16.88/5.74	
16.88/5.74	*BasicFunctionTypename: "isEven" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: (n i32) variableLength: false visibilityType: DEFAULT callingConvention: ccc
16.88/5.74		0:
16.88/5.74			%1 = alloca i32, align 4
16.88/5.74			%2 = alloca i32, align 4
16.88/5.74			store %n, %2
16.88/5.74			%3 = load %2
16.88/5.74			%4 = icmp eq %3 0
16.88/5.74			br %4, %5, %6
16.88/5.74		5:
16.88/5.74			store 1, %1
16.88/5.74			br %14
16.88/5.74		6:
16.88/5.74			%7 = load %2
16.88/5.74			%8 = icmp eq %7 1
16.88/5.74			br %8, %9, %10
16.88/5.74		9:
16.88/5.74			store 0, %1
16.88/5.74			br %14
16.88/5.74		10:
16.88/5.74			%11 = load %2
16.88/5.74			%12 = sub %11 1
16.88/5.74			%13 = call i32 @isOdd(i32 %12)
16.88/5.74			store %13, %1
16.88/5.74			br %14
16.88/5.74		14:
16.88/5.74			%15 = load %1
16.88/5.74			ret %15
16.88/5.74	
16.88/5.74	*BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc
16.88/5.74		0:
16.88/5.74			%1 = alloca i32, align 4
16.88/5.74			%n = alloca i32, align 4
16.88/5.74			%result = alloca i32, align 4
16.88/5.74			store 0, %1
16.88/5.74			%2 = call i32 @__VERIFIER_nondet_int()
16.88/5.74			store %2, %n
16.88/5.74			%3 = load %n
16.88/5.74			%4 = icmp slt %3 0
16.88/5.74			br %4, %5, %6
16.88/5.74		5:
16.88/5.74			store 0, %1
16.88/5.74			br %14
16.88/5.74		6:
16.88/5.74			%7 = load %n
16.88/5.74			%8 = call i32 @isOdd(i32 %7)
16.88/5.74			store %8, %result
16.88/5.74			%9 = load %result
16.88/5.74			%10 = icmp sge %9 0
16.88/5.74			br %10, %11, %12
16.88/5.74		11:
16.88/5.74			store 0, %1
16.88/5.74			br %14
16.88/5.74		12:
16.88/5.74			br %13
16.88/5.74		13:
16.88/5.74			Unnamed Call-Instruction = call BasicVoidType (...)* @__VERIFIER_error() noreturn
16.88/5.74			unreachable
16.88/5.74		14:
16.88/5.74			%15 = load %1
16.88/5.74			ret %15
16.88/5.74	
16.88/5.74	
16.88/5.74	Analyze Termination of all function calls matching the pattern:
16.88/5.74	main()
16.88/5.74	----------------------------------------
16.88/5.74	
16.88/5.74	(3) LLVMToTerminationGraphProof (EQUIVALENT)
16.88/5.74	Constructed symbolic execution graph for LLVM program and proved memory safety.
16.88/5.74	----------------------------------------
16.88/5.74	
16.88/5.74	(4)
16.88/5.74	Obligation:
16.88/5.74	SE Graph
16.88/5.74	----------------------------------------
16.88/5.74	
16.88/5.74	(5) SymbolicExecutionGraphToSCCProof (SOUND)
16.88/5.74	Splitted symbolic execution graph to 1 SCC.
16.88/5.74	----------------------------------------
16.88/5.74	
16.88/5.74	(6)
16.88/5.74	Obligation:
16.88/5.74	SCC
16.88/5.74	----------------------------------------
16.88/5.74	
16.88/5.74	(7) SCC2IRS (SOUND)
16.88/5.74	Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 
16.88/5.74	Generated rules. Obtained 30 rulesP rules:
16.88/5.74	f_287(v58, v67, v59, v60, v61, v62, v63, v64, v68, 0, v66, 3, 1, 4) -> f_288(v58, v67, v69, v59, v60, v61, v62, v63, v64, v68, v70, 0, v66, 3, 1, 4) :|: 1 <= v69 && v70 = 3 + v69 && 4 <= v70
16.88/5.74	f_288(v58, v67, v69, v59, v60, v61, v62, v63, v64, v68, v70, 0, v66, 3, 1, 4) -> f_289(v58, v67, v69, v59, v60, v61, v62, v63, v64, v68, v70, 0, v66, 3, 1, 4) :|: TRUE
16.88/5.74	f_289(v58, v67, v69, v59, v60, v61, v62, v63, v64, v68, v70, 0, v66, 3, 1, 4) -> f_290(v58, v67, v69, v59, v60, v61, v62, v63, v64, v68, v70, 0, v66, 3, 1, 4) :|: 0 = 0
16.88/5.74	f_290(v58, v67, v69, v59, v60, v61, v62, v63, v64, v68, v70, 0, v66, 3, 1, 4) -> f_292(v58, v67, v69, v59, v60, v61, v62, v63, v64, v68, v70, 0, v66, 3, 1, 4) :|: v58 != 0
16.88/5.74	f_292(v58, v67, v69, v59, v60, v61, v62, v63, v64, v68, v70, 0, v66, 3, 1, 4) -> f_294(v58, v67, v69, 0, v59, v60, v61, v62, v63, v64, v68, v70, v66, 3, 1, 4) :|: 0 = 0
16.88/5.74	f_294(v58, v67, v69, 0, v59, v60, v61, v62, v63, v64, v68, v70, v66, 3, 1, 4) -> f_296(v58, v67, v69, 0, v59, v60, v61, v62, v63, v64, v68, v70, v66, 3, 1, 4) :|: TRUE
16.88/5.74	f_296(v58, v67, v69, 0, v59, v60, v61, v62, v63, v64, v68, v70, v66, 3, 1, 4) -> f_298(v58, v67, v69, 0, v59, v60, v61, v62, v63, v64, v68, v70, v66, 3, 1, 4) :|: 0 = 0
16.88/5.74	f_298(v58, v67, v69, 0, v59, v60, v61, v62, v63, v64, v68, v70, v66, 3, 1, 4) -> f_301(v58, v67, v69, 0, v59, v60, v61, v62, v63, v64, v68, v70, v66, 3, 2, 1, 4) :|: v58 != 1 && 2 <= v58
16.88/5.74	f_301(v58, v67, v69, 0, v59, v60, v61, v62, v63, v64, v68, v70, v66, 3, 2, 1, 4) -> f_304(v58, v67, v69, 0, v59, v60, v61, v62, v63, v64, v68, v70, v66, 3, 2, 1, 4) :|: 0 = 0
16.88/5.74	f_304(v58, v67, v69, 0, v59, v60, v61, v62, v63, v64, v68, v70, v66, 3, 2, 1, 4) -> f_307(v58, v67, v69, 0, v59, v60, v61, v62, v63, v64, v68, v70, v66, 3, 2, 1, 4) :|: TRUE
16.88/5.74	f_307(v58, v67, v69, 0, v59, v60, v61, v62, v63, v64, v68, v70, v66, 3, 2, 1, 4) -> f_310(v58, v67, v69, 0, v59, v60, v61, v62, v63, v64, v68, v70, v66, 3, 2, 1, 4) :|: 0 = 0
16.88/5.74	f_310(v58, v67, v69, 0, v59, v60, v61, v62, v63, v64, v68, v70, v66, 3, 2, 1, 4) -> f_313(v58, v67, v69, 0, v83, v59, v60, v61, v62, v63, v64, v68, v70, v66, 3, 1, 2, 4) :|: 1 + v83 = v58 && 1 <= v83
16.88/5.74	f_313(v58, v67, v69, 0, v83, v59, v60, v61, v62, v63, v64, v68, v70, v66, 3, 1, 2, 4) -> f_316(v83, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, 0, v66, v58, 3, 1, 2, 4) :|: 0 = 0
16.88/5.74	f_316(v83, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, 0, v66, v58, 3, 1, 2, 4) -> f_319(v83, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, 0, v66, v58, 3, 1, 2, 4) :|: TRUE
16.88/5.74	f_319(v83, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, 0, v66, v58, 3, 1, 2, 4) -> f_324(v83, v95, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, 0, v66, v58, 3, 1, 2, 4) :|: 1 <= v95 && v96 = 3 + v95 && 4 <= v96
16.88/5.74	f_324(v83, v95, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, 0, v66, v58, 3, 1, 2, 4) -> f_327(v83, v95, v97, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, v98, 0, v66, v58, 3, 1, 2, 4) :|: 1 <= v97 && v98 = 3 + v97 && 4 <= v98
16.88/5.74	f_327(v83, v95, v97, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, v98, 0, v66, v58, 3, 1, 2, 4) -> f_330(v83, v95, v97, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, v98, 0, v66, v58, 3, 1, 2, 4) :|: TRUE
16.88/5.74	f_330(v83, v95, v97, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, v98, 0, v66, v58, 3, 1, 2, 4) -> f_332(v83, v95, v97, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, v98, 0, v66, v58, 3, 1, 2, 4) :|: 0 = 0
16.88/5.74	f_332(v83, v95, v97, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, v98, 0, v66, v58, 3, 1, 2, 4) -> f_334(v83, v95, v97, 0, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, v98, v66, v58, 3, 1, 2, 4) :|: 0 = 0
16.88/5.74	f_334(v83, v95, v97, 0, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, v98, v66, v58, 3, 1, 2, 4) -> f_336(v83, v95, v97, 0, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, v98, v66, v58, 3, 1, 2, 4) :|: TRUE
16.88/5.74	f_336(v83, v95, v97, 0, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, v98, v66, v58, 3, 1, 2, 4) -> f_338(v83, v95, v97, 0, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, v98, v66, v58, 3, 1, 2, 4) :|: 0 = 0
16.88/5.74	f_338(v83, v95, v97, 0, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, v98, v66, v58, 3, 1, 2, 4) -> f_340(v83, v95, v97, 0, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, v98, v66, v58, 3, 1, 4, 2) :|: v83 != 1 && 2 <= v83 && 3 <= v58
16.88/5.74	f_340(v83, v95, v97, 0, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, v98, v66, v58, 3, 1, 4, 2) -> f_342(v83, v95, v97, 0, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, v98, v66, v58, 3, 1, 4, 2) :|: 0 = 0
16.88/5.74	f_342(v83, v95, v97, 0, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, v98, v66, v58, 3, 1, 4, 2) -> f_344(v83, v95, v97, 0, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, v98, v66, v58, 3, 1, 4, 2) :|: TRUE
16.88/5.74	f_344(v83, v95, v97, 0, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, v98, v66, v58, 3, 1, 4, 2) -> f_346(v83, v95, v97, 0, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, v98, v66, v58, 3, 1, 4, 2) :|: 0 = 0
16.88/5.74	f_346(v83, v95, v97, 0, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, v98, v66, v58, 3, 1, 4, 2) -> f_348(v83, v95, v97, 0, v106, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, v98, v66, v58, 3, 1, 4, 2) :|: 1 + v106 = v83 && 1 <= v106
16.88/5.74	f_348(v83, v95, v97, 0, v106, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v96, v98, v66, v58, 3, 1, 4, 2) -> f_350(v106, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v95, v96, v97, v98, 0, v66, v58, v83, 3, 1, 4, 2) :|: 0 = 0
16.88/5.74	f_350(v106, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v95, v96, v97, v98, 0, v66, v58, v83, 3, 1, 4, 2) -> f_352(v106, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v95, v96, v97, v98, 0, v66, v58, v83, 3, 1, 4, 2) :|: TRUE
16.88/5.74	f_352(v106, v59, v60, v61, v62, v63, v64, v67, v68, v69, v70, v95, v96, v97, v98, 0, v66, v58, v83, 3, 1, 4, 2) -> f_285(v106, v59, v60, v61, v62, v63, v64, 0, v66, 3, 1, 4) :|: TRUE
16.88/5.74	f_285(v58, v59, v60, v61, v62, v63, v64, 0, v66, 3, 1, 4) -> f_287(v58, v67, v59, v60, v61, v62, v63, v64, v68, 0, v66, 3, 1, 4) :|: 1 <= v67 && v68 = 3 + v67 && 4 <= v68
16.88/5.74	Combined rules. Obtained 2 rulesP rules:
16.88/5.74	f_287(1 + (1 + v106:0), v67:0, v59:0, v60:0, v61:0, v62:0, v63:0, v64:0, v68:0, 0, v66:0, 3, 1, 4) -> f_287(v106:0, v67:1, v59:0, v60:0, v61:0, v62:0, v63:0, v64:0, 3 + v67:1, 0, v66:0, 3, 1, 4) :|: v106:0 > 0 && v69:0 > 0 && v106:0 < -2 && v95:0 > 0 && v97:0 > 0 && v67:1 > 0
16.88/5.74	f_287(1 + (1 + v106:0), v67:0, v59:0, v60:0, v61:0, v62:0, v63:0, v64:0, v68:0, 0, v66:0, 3, 1, 4) -> f_287(v106:0, v67:1, v59:0, v60:0, v61:0, v62:0, v63:0, v64:0, 3 + v67:1, 0, v66:0, 3, 1, 4) :|: v106:0 > 0 && v69:0 > 0 && v95:0 > 0 && v97:0 > 0 && v67:1 > 0
16.88/5.74	Filtered unneeded arguments:
16.88/5.74	   f_287(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14) -> f_287(x1)
16.88/5.74	Removed division, modulo operations, cleaned up constraints. Obtained 2 rules.P rules:
16.88/5.74	f_287(sum~cons_1~sum~cons_1~v106:0) -> f_287(v106:0) :|: v106:0 > 0 && v106:0 < -2 && sum~cons_1~sum~cons_1~v106:0 = 1 + (1 + v106:0)
16.88/5.74	f_287(sum~cons_1~sum~cons_1~v106:0) -> f_287(v106:0) :|: v106:0 > 0 && sum~cons_1~sum~cons_1~v106:0 = 1 + (1 + v106:0)
16.88/5.74	
16.88/5.74	----------------------------------------
16.88/5.74	
16.88/5.74	(8)
16.88/5.74	Obligation:
16.88/5.74	Rules:
16.88/5.74	f_287(sum~cons_1~sum~cons_1~v106:0) -> f_287(v106:0) :|: v106:0 > 0 && v106:0 < -2 && sum~cons_1~sum~cons_1~v106:0 = 1 + (1 + v106:0)
16.88/5.74	f_287(x) -> f_287(x1) :|: x1 > 0 && x = 1 + (1 + x1)
16.88/5.74	
16.88/5.74	----------------------------------------
16.88/5.74	
16.88/5.74	(9) IRS2T2 (EQUIVALENT)
16.88/5.74	Transformed input IRS into an integer transition system.Used the following mapping from defined symbols to location IDs:
16.88/5.74	
16.88/5.74	   (f_287_1,1)
16.88/5.74	
16.88/5.74	----------------------------------------
16.88/5.74	
16.88/5.74	(10)
16.88/5.74	Obligation:
16.88/5.74	START: 0;
16.88/5.74	
16.88/5.74	FROM: 0;
16.88/5.74	TO: 1;
16.88/5.74	
16.88/5.74	FROM: 1;
16.88/5.74	oldX0 := x0;
16.88/5.74	oldX1 := oldX0 - 2;
16.88/5.74	assume(oldX1 > 0 && oldX1 < -2 && oldX0 = 1 + (1 + oldX1));
16.88/5.74	x0 := oldX0 - 2;
16.88/5.74	TO: 1;
16.88/5.74	
16.88/5.74	FROM: 1;
16.88/5.74	oldX0 := x0;
16.88/5.74	oldX1 := oldX0 - 2;
16.88/5.74	assume(oldX1 > 0 && oldX0 = 1 + (1 + oldX1));
16.88/5.74	x0 := oldX0 - 2;
16.88/5.74	TO: 1;
16.88/5.74	
16.88/5.74	
16.88/5.74	----------------------------------------
16.88/5.74	
16.88/5.74	(11) T2 (EQUIVALENT)
16.88/5.74	Initially, performed program simplifications using lexicographic rank functions:
16.88/5.74	 * Removed transitions 1, 4, 5 using the following rank functions:
16.88/5.74	    - Rank function 1:
16.88/5.74	      RF for loc. 5: 1+x0
16.88/5.74	      RF for loc. 6: x0
16.88/5.74	      Bound for (chained) transitions 4: 3
16.88/5.74	      Bound for (chained) transitions 5: 3
16.88/5.74	    - Rank function 2:
16.88/5.74	      RF for loc. 5: 0
16.88/5.74	      RF for loc. 6: -1
16.88/5.74	      Bound for (chained) transitions 1: 0
16.88/5.74	
16.88/5.74	----------------------------------------
16.88/5.74	
16.88/5.74	(12)
16.88/5.74	YES
16.98/8.96	EOF