16.75/5.44	YES
16.75/5.45	proof of /export/starexec/sandbox/benchmark/theBenchmark.c
16.75/5.45	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
16.75/5.45	
16.75/5.45	
16.75/5.45	Termination of the given C Problem could be proven:
16.75/5.45	
16.75/5.45	(0) C Problem
16.75/5.45	(1) CToLLVMProof [EQUIVALENT, 173 ms]
16.75/5.45	(2) LLVM problem
16.75/5.45	(3) LLVMToTerminationGraphProof [EQUIVALENT, 1609 ms]
16.75/5.45	(4) LLVM Symbolic Execution Graph
16.75/5.45	(5) SymbolicExecutionGraphToSCCProof [SOUND, 0 ms]
16.75/5.45	(6) LLVM Symbolic Execution SCC
16.75/5.45	(7) SCC2IRS [SOUND, 42 ms]
16.75/5.45	(8) IntTRS
16.75/5.45	(9) IntTRSCompressionProof [EQUIVALENT, 0 ms]
16.75/5.45	(10) IntTRS
16.75/5.45	(11) TerminationGraphProcessor [EQUIVALENT, 3 ms]
16.75/5.45	(12) IntTRS
16.75/5.45	(13) IntTRSCompressionProof [EQUIVALENT, 0 ms]
16.75/5.45	(14) IntTRS
16.75/5.45	(15) RankingReductionPairProof [EQUIVALENT, 9 ms]
16.75/5.45	(16) YES
16.75/5.45	
16.75/5.45	
16.75/5.45	----------------------------------------
16.75/5.45	
16.75/5.45	(0)
16.75/5.45	Obligation:
16.75/5.45	c file /export/starexec/sandbox/benchmark/theBenchmark.c
16.75/5.45	----------------------------------------
16.75/5.45	
16.75/5.45	(1) CToLLVMProof (EQUIVALENT)
16.75/5.45	Compiled c-file /export/starexec/sandbox/benchmark/theBenchmark.c to LLVM.
16.75/5.45	----------------------------------------
16.75/5.45	
16.75/5.45	(2)
16.75/5.45	Obligation:
16.75/5.45	LLVM Problem
16.75/5.45	
16.75/5.45	Aliases:
16.75/5.45	
16.75/5.45	Data layout:
16.75/5.45	
16.75/5.45	"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.75/5.45	
16.75/5.45	Machine:
16.75/5.45	
16.75/5.45	"x86_64-pc-linux-gnu"
16.75/5.45	
16.75/5.45	Type definitions:
16.75/5.45	
16.75/5.45	Global variables:
16.75/5.45	
16.75/5.45	Function declarations and definitions:
16.75/5.45	
16.75/5.45	*BasicFunctionTypename: "__VERIFIER_nondet_int" returnParam: i32 parameters: () variableLength: true visibilityType: DEFAULT callingConvention: ccc
16.75/5.45	*BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc
16.75/5.45		0:
16.75/5.45			%1 = alloca i32, align 4
16.75/5.45			%x = alloca i32, align 4
16.75/5.45			%y = alloca i32, align 4
16.75/5.45			%z = alloca i32, align 4
16.75/5.45			store 0, %1
16.75/5.45			%2 = call i32 (...)* @__VERIFIER_nondet_int()
16.75/5.45			store %2, %x
16.75/5.45			%3 = call i32 (...)* @__VERIFIER_nondet_int()
16.75/5.45			store %3, %y
16.75/5.45			%4 = call i32 (...)* @__VERIFIER_nondet_int()
16.75/5.45			store %4, %z
16.75/5.45			br %5
16.75/5.45		5:
16.75/5.45			%6 = load %x
16.75/5.45			%7 = load %y
16.75/5.45			%8 = sub %6 %7
16.75/5.45			%9 = icmp sgt %8 0
16.75/5.45			br %9, %10, %18
16.75/5.45		10:
16.75/5.45			%11 = load %x
16.75/5.45			%12 = sub 0 %11
16.75/5.45			%13 = load %y
16.75/5.45			%14 = add %12 %13
16.75/5.45			store %14, %x
16.75/5.45			%15 = load %z
16.75/5.45			store %15, %y
16.75/5.45			%16 = load %z
16.75/5.45			%17 = add %16 1
16.75/5.45			store %17, %z
16.75/5.45			br %5
16.75/5.45		18:
16.75/5.45			ret 0
16.75/5.45	
16.75/5.45	
16.75/5.45	Analyze Termination of all function calls matching the pattern:
16.75/5.45	main()
16.75/5.45	----------------------------------------
16.75/5.45	
16.75/5.45	(3) LLVMToTerminationGraphProof (EQUIVALENT)
16.75/5.45	Constructed symbolic execution graph for LLVM program and proved memory safety.
16.75/5.45	----------------------------------------
16.75/5.45	
16.75/5.45	(4)
16.75/5.45	Obligation:
16.75/5.45	SE Graph
16.75/5.45	----------------------------------------
16.75/5.45	
16.75/5.45	(5) SymbolicExecutionGraphToSCCProof (SOUND)
16.75/5.45	Splitted symbolic execution graph to 1 SCC.
16.75/5.45	----------------------------------------
16.75/5.45	
16.75/5.45	(6)
16.75/5.45	Obligation:
16.75/5.45	SCC
16.75/5.45	----------------------------------------
16.75/5.45	
16.75/5.45	(7) SCC2IRS (SOUND)
16.75/5.45	Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 
16.75/5.45	Generated rules. Obtained 18 rulesP rules:
16.75/5.45	f_165(v56, v57, v58, v59, v60, v61, v62, v68, v64, v65, 1, v63, v67, v69, v70, v71, v72, v73, v74, 0, 3, 4) -> f_166(v56, v57, v58, v59, v60, v61, v62, v68, v69, v65, 1, v63, v67, v64, v70, v71, v72, v73, v74, 0, 3, 4) :|: 0 = 0
16.75/5.45	f_166(v56, v57, v58, v59, v60, v61, v62, v68, v69, v65, 1, v63, v67, v64, v70, v71, v72, v73, v74, 0, 3, 4) -> f_167(v56, v57, v58, v59, v60, v61, v62, v68, v69, v76, 1, v63, v67, v64, v70, v71, v72, v73, v74, 0, 3, 4) :|: v76 + v69 = v68
16.75/5.45	f_167(v56, v57, v58, v59, v60, v61, v62, v68, v69, v76, 1, v63, v67, v64, v70, v71, v72, v73, v74, 0, 3, 4) -> f_168(v56, v57, v58, v59, v60, v61, v62, v68, v69, v76, 1, v63, v67, v64, v70, v71, v72, v73, v74, 0, 3, 4) :|: 0 < v76
16.75/5.45	f_168(v56, v57, v58, v59, v60, v61, v62, v68, v69, v76, 1, v63, v67, v64, v70, v71, v72, v73, v74, 0, 3, 4) -> f_170(v56, v57, v58, v59, v60, v61, v62, v68, v69, v76, 1, v63, v67, v64, v70, v71, v72, v73, v74, 0, 3, 4) :|: 0 = 0
16.75/5.45	f_170(v56, v57, v58, v59, v60, v61, v62, v68, v69, v76, 1, v63, v67, v64, v70, v71, v72, v73, v74, 0, 3, 4) -> f_172(v56, v57, v58, v59, v60, v61, v62, v68, v69, v76, 1, v63, v67, v64, v70, v71, v72, v73, v74, 0, 3, 4) :|: TRUE
16.75/5.45	f_172(v56, v57, v58, v59, v60, v61, v62, v68, v69, v76, 1, v63, v67, v64, v70, v71, v72, v73, v74, 0, 3, 4) -> f_174(v56, v57, v58, v59, v60, v61, v62, v68, v69, v76, 1, v67, v64, v70, v71, v72, v73, v74, 0, 3, 4) :|: 0 = 0
16.75/5.45	f_174(v56, v57, v58, v59, v60, v61, v62, v68, v69, v76, 1, v67, v64, v70, v71, v72, v73, v74, 0, 3, 4) -> f_175(v56, v57, v58, v59, v60, v61, v62, v68, v69, v76, 1, v77, v64, v70, v71, v72, v73, v74, 0, 3, 4) :|: v77 + v68 = 0
16.75/5.45	f_175(v56, v57, v58, v59, v60, v61, v62, v68, v69, v76, 1, v77, v64, v70, v71, v72, v73, v74, 0, 3, 4) -> f_176(v56, v57, v58, v59, v60, v61, v62, v68, v69, v76, 1, v77, v70, v71, v72, v73, v74, 0, 3, 4) :|: 0 = 0
16.75/5.45	f_176(v56, v57, v58, v59, v60, v61, v62, v68, v69, v76, 1, v77, v70, v71, v72, v73, v74, 0, 3, 4) -> f_177(v56, v57, v58, v59, v60, v61, v62, v68, v69, v76, 1, v77, v78, v70, v71, v72, v73, v74, 0, 3, 4) :|: v78 = v77 + v69
16.75/5.45	f_177(v56, v57, v58, v59, v60, v61, v62, v68, v69, v76, 1, v77, v78, v70, v71, v72, v73, v74, 0, 3, 4) -> f_178(v56, v57, v58, v59, v60, v61, v62, v68, v69, v76, 1, v77, v78, v70, v71, v72, v73, v74, 0, 3, 4) :|: TRUE
16.75/5.45	f_178(v56, v57, v58, v59, v60, v61, v62, v68, v69, v76, 1, v77, v78, v70, v71, v72, v73, v74, 0, 3, 4) -> f_179(v56, v57, v58, v59, v60, v61, v62, v68, v69, v76, 1, v77, v78, v70, v71, v72, v73, v74, 0, 3, 4) :|: 0 = 0
16.75/5.45	f_179(v56, v57, v58, v59, v60, v61, v62, v68, v69, v76, 1, v77, v78, v70, v71, v72, v73, v74, 0, 3, 4) -> f_180(v56, v57, v58, v59, v60, v61, v62, v68, v69, v76, 1, v77, v78, v70, v71, v72, v73, v74, 0, 3, 4) :|: TRUE
16.75/5.45	f_180(v56, v57, v58, v59, v60, v61, v62, v68, v69, v76, 1, v77, v78, v70, v71, v72, v73, v74, 0, 3, 4) -> f_181(v56, v57, v58, v59, v60, v61, v62, v68, v69, v76, 1, v77, v78, v70, v71, v72, v73, v74, 0, 3, 4) :|: 0 = 0
16.75/5.45	f_181(v56, v57, v58, v59, v60, v61, v62, v68, v69, v76, 1, v77, v78, v70, v71, v72, v73, v74, 0, 3, 4) -> f_182(v56, v57, v58, v59, v60, v61, v62, v68, v69, v76, 1, v77, v78, v70, v81, v71, v72, v73, v74, 0, 3, 4) :|: v81 = 1 + v70
16.75/5.45	f_182(v56, v57, v58, v59, v60, v61, v62, v68, v69, v76, 1, v77, v78, v70, v81, v71, v72, v73, v74, 0, 3, 4) -> f_183(v56, v57, v58, v59, v60, v61, v62, v68, v69, v76, 1, v77, v78, v70, v81, v71, v72, v73, v74, 0, 3, 4) :|: TRUE
16.75/5.45	f_183(v56, v57, v58, v59, v60, v61, v62, v68, v69, v76, 1, v77, v78, v70, v81, v71, v72, v73, v74, 0, 3, 4) -> f_184(v56, v57, v58, v59, v60, v61, v62, v68, v69, v76, 1, v77, v78, v70, v81, v71, v72, v73, v74, 0, 3, 4) :|: TRUE
16.75/5.45	f_184(v56, v57, v58, v59, v60, v61, v62, v68, v69, v76, 1, v77, v78, v70, v81, v71, v72, v73, v74, 0, 3, 4) -> f_164(v56, v57, v58, v59, v60, v61, v62, v68, v69, v76, 1, v77, v78, v70, v81, v71, v72, v73, v74, 0, 3, 4) :|: TRUE
16.75/5.45	f_164(v56, v57, v58, v59, v60, v61, v62, v63, v64, v65, 1, v67, v68, v69, v70, v71, v72, v73, v74, 0, 3, 4) -> f_165(v56, v57, v58, v59, v60, v61, v62, v68, v64, v65, 1, v63, v67, v69, v70, v71, v72, v73, v74, 0, 3, 4) :|: 0 = 0
16.75/5.45	Combined rules. Obtained 1 rulesP rules:
16.75/5.45	f_165(v56:0, v57:0, v58:0, v59:0, v60:0, v61:0, v62:0, v76:0 + v69:0, v64:0, v65:0, 1, v63:0, v67:0, v69:0, v70:0, v71:0, v72:0, v73:0, v74:0, 0, 3, 4) -> f_165(v56:0, v57:0, v58:0, v59:0, v60:0, v61:0, v62:0, v77:0 + v69:0, v69:0, v76:0, 1, v76:0 + v69:0, v77:0, v70:0, 1 + v70:0, v71:0, v72:0, v73:0, v74:0, 0, 3, 4) :|: v77:0 + (v76:0 + v69:0) = 0 && v76:0 > 0
16.75/5.45	Filtered unneeded arguments:
16.75/5.45	   f_165(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19, x20, x21, x22) -> f_165(x8, x14, x15)
16.75/5.45	Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules:
16.75/5.45	f_165(sum~v76:0~v69:0, v69:0, v70:0) -> f_165(v77:0 + v69:0, v70:0, 1 + v70:0) :|: v77:0 + (v76:0 + v69:0) = 0 && v76:0 > 0 && sum~v76:0~v69:0 = v76:0 + v69:0
16.75/5.45	
16.75/5.45	----------------------------------------
16.75/5.45	
16.75/5.45	(8)
16.75/5.45	Obligation:
16.75/5.45	Rules:
16.75/5.45	f_165(sum~v76:0~v69:0, v69:0, v70:0) -> f_165(v77:0 + v69:0, v70:0, 1 + v70:0) :|: v77:0 + (v76:0 + v69:0) = 0 && v76:0 > 0 && sum~v76:0~v69:0 = v76:0 + v69:0
16.75/5.45	
16.75/5.45	----------------------------------------
16.75/5.45	
16.75/5.45	(9) IntTRSCompressionProof (EQUIVALENT)
16.75/5.45	Compressed rules.
16.75/5.45	----------------------------------------
16.75/5.45	
16.75/5.45	(10)
16.75/5.45	Obligation:
16.75/5.45	Rules:
16.75/5.45	f_165(sum~v76:0:0~v69:0:0, v69:0:0, v70:0:0) -> f_165(v77:0:0 + v69:0:0, v70:0:0, 1 + v70:0:0) :|: v77:0:0 + (v76:0:0 + v69:0:0) = 0 && v76:0:0 > 0 && sum~v76:0:0~v69:0:0 = v76:0:0 + v69:0:0
16.75/5.45	
16.75/5.45	----------------------------------------
16.75/5.45	
16.75/5.45	(11) TerminationGraphProcessor (EQUIVALENT)
16.75/5.45	Constructed the termination graph and obtained one non-trivial SCC.
16.75/5.45	
16.75/5.45	f_165(sum~v76:0:0~v69:0:0, v69:0:0, v70:0:0) -> f_165(v77:0:0 + v69:0:0, v70:0:0, 1 + v70:0:0) :|: v77:0:0 + (v76:0:0 + v69:0:0) = 0 && v76:0:0 > 0 && sum~v76:0:0~v69:0:0 = v76:0:0 + v69:0:0
16.75/5.45	has been transformed into
16.75/5.45	f_165(sum~v76:0:0~v69:0:0, v69:0:0, v70:0:0) -> f_165(v77:0:0 + v69:0:0, v70:0:0, 1 + v70:0:0) :|: v77:0:0 + (v76:0:0 + v69:0:0) = 0 && v76:0:0 > 0 && sum~v76:0:0~v69:0:0 = v76:0:0 + v69:0:0.
16.75/5.45	
16.75/5.45	
16.75/5.45	f_165(sum~v76:0:0~v69:0:0, v69:0:0, v70:0:0) -> f_165(v77:0:0 + v69:0:0, v70:0:0, 1 + v70:0:0) :|: v77:0:0 + (v76:0:0 + v69:0:0) = 0 && v76:0:0 > 0 && sum~v76:0:0~v69:0:0 = v76:0:0 + v69:0:0 and 
16.75/5.45	f_165(sum~v76:0:0~v69:0:0, v69:0:0, v70:0:0) -> f_165(v77:0:0 + v69:0:0, v70:0:0, 1 + v70:0:0) :|: v77:0:0 + (v76:0:0 + v69:0:0) = 0 && v76:0:0 > 0 && sum~v76:0:0~v69:0:0 = v76:0:0 + v69:0:0
16.75/5.45	have been merged into the new rule
16.75/5.45	f_165(x25, x26, x27) -> f_165(x28 + x27, 1 + x27, 1 + (1 + x27)) :|: x29 + (x30 + x26) = 0 && x30 > 0 && x25 = x30 + x26 && (x28 + (x31 + x27) = 0 && x31 > 0 && x29 + x26 = x31 + x27)
16.75/5.45	
16.75/5.45	
16.75/5.45	----------------------------------------
16.75/5.45	
16.75/5.45	(12)
16.75/5.45	Obligation:
16.75/5.45	Rules:
16.75/5.45	f_165(x32, x33, x34) -> f_165(x35 + x34, 1 + x34, 2 + x34) :|: TRUE && x36 + x37 + x33 = 0 && x37 >= 1 && x32 + -1 * x37 + -1 * x33 = 0 && x35 + x38 + x34 = 0 && x38 >= 1 && x36 + x33 + -1 * x38 + -1 * x34 = 0
16.75/5.45	
16.75/5.45	----------------------------------------
16.75/5.45	
16.75/5.45	(13) IntTRSCompressionProof (EQUIVALENT)
16.75/5.45	Compressed rules.
16.75/5.45	----------------------------------------
16.75/5.45	
16.75/5.45	(14)
16.75/5.45	Obligation:
16.75/5.45	Rules:
16.75/5.45	f_165(x32:0, x33:0, x34:0) -> f_165(x35:0 + x34:0, 1 + x34:0, 2 + x34:0) :|: x38:0 > 0 && x36:0 + x33:0 + -1 * x38:0 + -1 * x34:0 = 0 && x35:0 + x38:0 + x34:0 = 0 && x32:0 + -1 * x37:0 + -1 * x33:0 = 0 && x36:0 + x37:0 + x33:0 = 0 && x37:0 > 0
16.75/5.45	
16.75/5.45	----------------------------------------
16.75/5.45	
16.75/5.45	(15) RankingReductionPairProof (EQUIVALENT)
16.75/5.45	Interpretation:
16.75/5.45	[ f_165 ] = -1/2*f_165_3
16.75/5.45	
16.75/5.45	The following rules are decreasing:
16.75/5.45	f_165(x32:0, x33:0, x34:0) -> f_165(x35:0 + x34:0, 1 + x34:0, 2 + x34:0) :|: x38:0 > 0 && x36:0 + x33:0 + -1 * x38:0 + -1 * x34:0 = 0 && x35:0 + x38:0 + x34:0 = 0 && x32:0 + -1 * x37:0 + -1 * x33:0 = 0 && x36:0 + x37:0 + x33:0 = 0 && x37:0 > 0
16.75/5.45	
16.75/5.45	The following rules are bounded:
16.75/5.45	f_165(x32:0, x33:0, x34:0) -> f_165(x35:0 + x34:0, 1 + x34:0, 2 + x34:0) :|: x38:0 > 0 && x36:0 + x33:0 + -1 * x38:0 + -1 * x34:0 = 0 && x35:0 + x38:0 + x34:0 = 0 && x32:0 + -1 * x37:0 + -1 * x33:0 = 0 && x36:0 + x37:0 + x33:0 = 0 && x37:0 > 0
16.75/5.45	
16.75/5.45	
16.75/5.45	----------------------------------------
16.75/5.45	
16.75/5.45	(16)
16.75/5.45	YES
16.83/5.51	EOF