16.54/5.68	YES
16.54/5.69	proof of /export/starexec/sandbox2/benchmark/theBenchmark.c
16.54/5.69	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
16.54/5.69	
16.54/5.69	
16.54/5.69	Termination of the given C Problem could be proven:
16.54/5.69	
16.54/5.69	(0) C Problem
16.54/5.69	(1) CToLLVMProof [EQUIVALENT, 176 ms]
16.54/5.69	(2) LLVM problem
16.54/5.69	(3) LLVMToTerminationGraphProof [EQUIVALENT, 2795 ms]
16.54/5.69	(4) LLVM Symbolic Execution Graph
16.54/5.69	(5) SymbolicExecutionGraphToSCCProof [SOUND, 0 ms]
16.54/5.69	(6) LLVM Symbolic Execution SCC
16.54/5.69	(7) SCC2IRS [SOUND, 69 ms]
16.54/5.69	(8) IntTRS
16.54/5.69	(9) IntTRSCompressionProof [EQUIVALENT, 0 ms]
16.54/5.69	(10) IntTRS
16.54/5.69	(11) PolynomialOrderProcessor [EQUIVALENT, 15 ms]
16.54/5.69	(12) YES
16.54/5.69	
16.54/5.69	
16.54/5.69	----------------------------------------
16.54/5.69	
16.54/5.69	(0)
16.54/5.69	Obligation:
16.54/5.69	c file /export/starexec/sandbox2/benchmark/theBenchmark.c
16.54/5.69	----------------------------------------
16.54/5.69	
16.54/5.69	(1) CToLLVMProof (EQUIVALENT)
16.54/5.69	Compiled c-file /export/starexec/sandbox2/benchmark/theBenchmark.c to LLVM.
16.54/5.69	----------------------------------------
16.54/5.69	
16.54/5.69	(2)
16.54/5.69	Obligation:
16.54/5.69	LLVM Problem
16.54/5.69	
16.54/5.69	Aliases:
16.54/5.69	
16.54/5.69	Data layout:
16.54/5.69	
16.54/5.69	"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.54/5.69	
16.54/5.69	Machine:
16.54/5.69	
16.54/5.69	"x86_64-pc-linux-gnu"
16.54/5.69	
16.54/5.69	Type definitions:
16.54/5.69	
16.54/5.69	Global variables:
16.54/5.69	
16.54/5.69	Function declarations and definitions:
16.54/5.69	
16.54/5.69	*BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc
16.54/5.69		0:
16.54/5.69			%1 = alloca i32, align 4
16.54/5.69			%j = alloca i32, align 4
16.54/5.69			%i = alloca i32, align 4
16.54/5.69			store 0, %1
16.54/5.69			store 1, %j
16.54/5.69			store 10000, %i
16.54/5.69			br %2
16.54/5.69		2:
16.54/5.69			%3 = load %i
16.54/5.69			%4 = load %j
16.54/5.69			%5 = sub %3 %4
16.54/5.69			%6 = icmp sge %5 1
16.54/5.69			br %6, %7, %13
16.54/5.69		7:
16.54/5.69			%8 = load %j
16.54/5.69			%9 = add %8 1
16.54/5.69			store %9, %j
16.54/5.69			br %10
16.54/5.69		10:
16.54/5.69			%11 = load %i
16.54/5.69			%12 = add %11 -1
16.54/5.69			store %12, %i
16.54/5.69			br %2
16.54/5.69		13:
16.54/5.69			%14 = load %1
16.54/5.69			ret %14
16.54/5.69	
16.54/5.69	
16.54/5.69	Analyze Termination of all function calls matching the pattern:
16.54/5.69	main()
16.54/5.69	----------------------------------------
16.54/5.69	
16.54/5.69	(3) LLVMToTerminationGraphProof (EQUIVALENT)
16.54/5.69	Constructed symbolic execution graph for LLVM program and proved memory safety.
16.54/5.69	----------------------------------------
16.54/5.69	
16.54/5.69	(4)
16.54/5.69	Obligation:
16.54/5.69	SE Graph
16.54/5.69	----------------------------------------
16.54/5.69	
16.54/5.69	(5) SymbolicExecutionGraphToSCCProof (SOUND)
16.54/5.69	Splitted symbolic execution graph to 1 SCC.
16.54/5.69	----------------------------------------
16.54/5.69	
16.54/5.69	(6)
16.54/5.69	Obligation:
16.54/5.69	SCC
16.54/5.69	----------------------------------------
16.54/5.69	
16.54/5.69	(7) SCC2IRS (SOUND)
16.54/5.69	Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 
16.54/5.69	Generated rules. Obtained 15 rulesP rules:
16.54/5.69	f_150(v61, v62, v63, v69, v65, v66, 1, v68, v64, v70, v71, v72, 0, 3, 2, 10000, 9999, 4) -> f_151(v61, v62, v63, v69, v68, v66, 1, v65, v64, v70, v71, v72, 0, 3, 2, 10000, 9999, 4) :|: 0 = 0
16.54/5.69	f_151(v61, v62, v63, v69, v68, v66, 1, v65, v64, v70, v71, v72, 0, 3, 2, 10000, 9999, 4) -> f_152(v61, v62, v63, v69, v68, v74, 1, v65, v64, v70, v71, v72, 0, 3, 2, 10000, 9999, 4, 9997) :|: v74 + v68 = v69 && 0 <= 9999 + v74 && v74 <= 9997
16.54/5.69	f_152(v61, v62, v63, v69, v68, v74, 1, v65, v64, v70, v71, v72, 0, 3, 2, 10000, 9999, 4, 9997) -> f_153(v61, v62, v63, v69, v68, v74, 1, v65, v64, v70, v71, v72, 0, 3, 4, 10000, 9997, 2, 9998, 9999) :|: 1 <= v74 && v68 <= 9998 && 3 <= v69 && v65 <= 9997 && 4 <= v64
16.54/5.69	f_153(v61, v62, v63, v69, v68, v74, 1, v65, v64, v70, v71, v72, 0, 3, 4, 10000, 9997, 2, 9998, 9999) -> f_155(v61, v62, v63, v69, v68, v74, 1, v65, v64, v70, v71, v72, 0, 3, 4, 10000, 9997, 2, 9998, 9999) :|: 0 = 0
16.54/5.69	f_155(v61, v62, v63, v69, v68, v74, 1, v65, v64, v70, v71, v72, 0, 3, 4, 10000, 9997, 2, 9998, 9999) -> f_157(v61, v62, v63, v69, v68, v74, 1, v65, v64, v70, v71, v72, 0, 3, 4, 10000, 9997, 2, 9998, 9999) :|: TRUE
16.54/5.69	f_157(v61, v62, v63, v69, v68, v74, 1, v65, v64, v70, v71, v72, 0, 3, 4, 10000, 9997, 2, 9998, 9999) -> f_159(v61, v62, v63, v69, v68, v74, 1, v64, v70, v71, v72, 0, 3, 4, 10000, 2, 9998, 9999, 9997) :|: 0 = 0
16.54/5.69	f_159(v61, v62, v63, v69, v68, v74, 1, v64, v70, v71, v72, 0, 3, 4, 10000, 2, 9998, 9999, 9997) -> f_161(v61, v62, v63, v69, v68, v74, 1, v75, v64, v70, v71, v72, 0, 3, 4, 10000, 2, 9998, 9999, 9997) :|: v75 = 1 + v68 && 3 <= v75 && v75 <= 9999
16.54/5.69	f_161(v61, v62, v63, v69, v68, v74, 1, v75, v64, v70, v71, v72, 0, 3, 4, 10000, 2, 9998, 9999, 9997) -> f_162(v61, v62, v63, v69, v68, v74, 1, v75, v64, v70, v71, v72, 0, 3, 4, 10000, 2, 9998, 9999, 9997) :|: TRUE
16.54/5.69	f_162(v61, v62, v63, v69, v68, v74, 1, v75, v64, v70, v71, v72, 0, 3, 4, 10000, 2, 9998, 9999, 9997) -> f_163(v61, v62, v63, v69, v68, v74, 1, v75, v64, v70, v71, v72, 0, 3, 4, 10000, 2, 9998, 9999, 9997) :|: TRUE
16.54/5.69	f_163(v61, v62, v63, v69, v68, v74, 1, v75, v64, v70, v71, v72, 0, 3, 4, 10000, 2, 9998, 9999, 9997) -> f_164(v61, v62, v63, v69, v68, v74, 1, v75, v70, v71, v72, 0, 3, 2, 9998, 9999, 4, 9997) :|: 0 = 0
16.54/5.69	f_164(v61, v62, v63, v69, v68, v74, 1, v75, v70, v71, v72, 0, 3, 2, 9998, 9999, 4, 9997) -> f_165(v61, v62, v63, v69, v68, v74, 1, v75, v77, v70, v71, v72, 0, 3, 2, 9998, 9999, 4, 9997) :|: 1 + v77 = v69 && 2 <= v77 && v77 <= 9998
16.54/5.69	f_165(v61, v62, v63, v69, v68, v74, 1, v75, v77, v70, v71, v72, 0, 3, 2, 9998, 9999, 4, 9997) -> f_166(v61, v62, v63, v69, v68, v74, 1, v75, v77, v70, v71, v72, 0, 3, 2, 9998, 9999, 4, 9997) :|: TRUE
16.54/5.69	f_166(v61, v62, v63, v69, v68, v74, 1, v75, v77, v70, v71, v72, 0, 3, 2, 9998, 9999, 4, 9997) -> f_167(v61, v62, v63, v69, v68, v74, 1, v75, v77, v70, v71, v72, 0, 3, 2, 9998, 9999, 4, 9997) :|: TRUE
16.54/5.69	f_167(v61, v62, v63, v69, v68, v74, 1, v75, v77, v70, v71, v72, 0, 3, 2, 9998, 9999, 4, 9997) -> f_149(v61, v62, v63, v69, v68, v74, 1, v75, v77, v70, v71, v72, 0, 3, 2, 10000, 9999, 4) :|: TRUE
16.54/5.69	f_149(v61, v62, v63, v64, v65, v66, 1, v68, v69, v70, v71, v72, 0, 3, 2, 10000, 9999, 4) -> f_150(v61, v62, v63, v69, v65, v66, 1, v68, v64, v70, v71, v72, 0, 3, 2, 10000, 9999, 4) :|: 0 = 0
16.54/5.69	Combined rules. Obtained 1 rulesP rules:
16.54/5.69	f_150(v61:0, v62:0, v63:0, 1 + v77:0, v65:0, v66:0, 1, v68:0, v64:0, v70:0, v71:0, v72:0, 0, 3, 2, 10000, 9999, 4) -> f_150(v61:0, v62:0, v63:0, v77:0, v68:0, v74:0, 1, 1 + v68:0, 1 + v77:0, v70:0, v71:0, v72:0, 0, 3, 2, 10000, 9999, 4) :|: v74:0 > 0 && v68:0 < 9999 && v77:0 > 1 && v74:0 + v68:0 = 1 + v77:0 && v65:0 < 9998 && v74:0 < 9998 && v64:0 > 3 && v68:0 > 1 && v77:0 < 9999
16.54/5.69	Filtered unneeded arguments:
16.54/5.69	   f_150(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18) -> f_150(x4, x5, x8, x9)
16.54/5.69	Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules:
16.54/5.69	f_150(sum~cons_1~v77:0, v65:0, v68:0, v64:0) -> f_150(v77:0, v68:0, 1 + v68:0, 1 + v77:0) :|: v77:0 > 1 && v68:0 < 9999 && v65:0 < 9998 && v64:0 > 3 && v77:0 < 9999 && v68:0 > 1 && sum~cons_1~v77:0 = 1 + v77:0
16.54/5.69	
16.54/5.69	----------------------------------------
16.54/5.69	
16.54/5.69	(8)
16.54/5.69	Obligation:
16.54/5.69	Rules:
16.54/5.69	f_150(sum~cons_1~v77:0, v65:0, v68:0, v64:0) -> f_150(v77:0, v68:0, 1 + v68:0, 1 + v77:0) :|: v77:0 > 1 && v68:0 < 9999 && v65:0 < 9998 && v64:0 > 3 && v77:0 < 9999 && v68:0 > 1 && sum~cons_1~v77:0 = 1 + v77:0
16.54/5.69	
16.54/5.69	----------------------------------------
16.54/5.69	
16.54/5.69	(9) IntTRSCompressionProof (EQUIVALENT)
16.54/5.69	Compressed rules.
16.54/5.69	----------------------------------------
16.54/5.69	
16.54/5.69	(10)
16.54/5.69	Obligation:
16.54/5.69	Rules:
16.54/5.69	f_150(sum~cons_1~v77:0:0, v65:0:0, v68:0:0, v64:0:0) -> f_150(v77:0:0, v68:0:0, 1 + v68:0:0, 1 + v77:0:0) :|: v77:0:0 < 9999 && v68:0:0 > 1 && v64:0:0 > 3 && v65:0:0 < 9998 && v68:0:0 < 9999 && v77:0:0 > 1 && sum~cons_1~v77:0:0 = 1 + v77:0:0
16.54/5.69	
16.54/5.69	----------------------------------------
16.54/5.69	
16.54/5.69	(11) PolynomialOrderProcessor (EQUIVALENT)
16.54/5.69	Found the following polynomial interpretation:
16.54/5.69	[f_150(x, x1, x2, x3)] = x
16.54/5.69	
16.54/5.69	The following rules are decreasing:
16.54/5.69	f_150(sum~cons_1~v77:0:0, v65:0:0, v68:0:0, v64:0:0) -> f_150(v77:0:0, v68:0:0, 1 + v68:0:0, 1 + v77:0:0) :|: v77:0:0 < 9999 && v68:0:0 > 1 && v64:0:0 > 3 && v65:0:0 < 9998 && v68:0:0 < 9999 && v77:0:0 > 1 && sum~cons_1~v77:0:0 = 1 + v77:0:0
16.54/5.69	The following rules are bounded:
16.54/5.69	f_150(sum~cons_1~v77:0:0, v65:0:0, v68:0:0, v64:0:0) -> f_150(v77:0:0, v68:0:0, 1 + v68:0:0, 1 + v77:0:0) :|: v77:0:0 < 9999 && v68:0:0 > 1 && v64:0:0 > 3 && v65:0:0 < 9998 && v68:0:0 < 9999 && v77:0:0 > 1 && sum~cons_1~v77:0:0 = 1 + v77:0:0
16.54/5.69	
16.54/5.69	----------------------------------------
16.54/5.69	
16.54/5.69	(12)
16.54/5.69	YES
16.89/5.74	EOF