16.03/5.47	YES
16.03/5.48	proof of /export/starexec/sandbox/benchmark/theBenchmark.c
16.03/5.48	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
16.03/5.48	
16.03/5.48	
16.03/5.48	Termination of the given C Problem could be proven:
16.03/5.48	
16.03/5.48	(0) C Problem
16.03/5.48	(1) CToLLVMProof [EQUIVALENT, 175 ms]
16.03/5.48	(2) LLVM problem
16.03/5.48	(3) LLVMToTerminationGraphProof [EQUIVALENT, 2091 ms]
16.03/5.48	(4) LLVM Symbolic Execution Graph
16.03/5.48	(5) SymbolicExecutionGraphToSCCProof [SOUND, 0 ms]
16.03/5.48	(6) LLVM Symbolic Execution SCC
16.03/5.48	(7) SCC2IRS [SOUND, 99 ms]
16.03/5.48	(8) IntTRS
16.03/5.48	(9) IntTRSCompressionProof [EQUIVALENT, 0 ms]
16.03/5.48	(10) IntTRS
16.03/5.48	(11) RankingReductionPairProof [EQUIVALENT, 26 ms]
16.03/5.48	(12) YES
16.03/5.48	
16.03/5.48	
16.03/5.48	----------------------------------------
16.03/5.48	
16.03/5.48	(0)
16.03/5.48	Obligation:
16.03/5.48	c file /export/starexec/sandbox/benchmark/theBenchmark.c
16.03/5.48	----------------------------------------
16.03/5.48	
16.03/5.48	(1) CToLLVMProof (EQUIVALENT)
16.03/5.48	Compiled c-file /export/starexec/sandbox/benchmark/theBenchmark.c to LLVM.
16.03/5.48	----------------------------------------
16.03/5.48	
16.03/5.48	(2)
16.03/5.48	Obligation:
16.03/5.48	LLVM Problem
16.03/5.48	
16.03/5.48	Aliases:
16.03/5.48	
16.03/5.48	Data layout:
16.03/5.48	
16.03/5.48	"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.03/5.48	
16.03/5.48	Machine:
16.03/5.48	
16.03/5.48	"x86_64-pc-linux-gnu"
16.03/5.48	
16.03/5.48	Type definitions:
16.03/5.48	
16.03/5.48	Global variables:
16.03/5.48	
16.03/5.48	Function declarations and definitions:
16.03/5.48	
16.03/5.48	*BasicFunctionTypename: "__VERIFIER_nondet_int" returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc
16.03/5.48	*BasicFunctionTypename: "test_fun" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: (x i32, y i32, r i32) variableLength: false visibilityType: DEFAULT callingConvention: ccc
16.03/5.48		0:
16.03/5.48			%1 = alloca i32, align 4
16.03/5.48			%2 = alloca i32, align 4
16.03/5.48			%3 = alloca i32, align 4
16.03/5.48			%x_ref = alloca *i32, align 8
16.03/5.48			%y_ref = alloca *i32, align 8
16.03/5.48			%r_ref = alloca *i32, align 8
16.03/5.48			store %x, %1
16.03/5.48			store %y, %2
16.03/5.48			store %r, %3
16.03/5.48			%4 = alloca i8, numElementsLit: 4
16.03/5.48			%5 = bitcast *i8 %4 to *i32
16.03/5.48			store %5, %x_ref
16.03/5.48			%6 = alloca i8, numElementsLit: 4
16.03/5.48			%7 = bitcast *i8 %6 to *i32
16.03/5.48			store %7, %y_ref
16.03/5.48			%8 = alloca i8, numElementsLit: 4
16.03/5.48			%9 = bitcast *i8 %8 to *i32
16.03/5.48			store %9, %r_ref
16.03/5.48			store 1, %3
16.03/5.48			%10 = load %1
16.03/5.48			%11 = load %x_ref
16.03/5.48			store %10, %11
16.03/5.48			%12 = load %2
16.03/5.48			%13 = load %y_ref
16.03/5.48			store %12, %13
16.03/5.48			%14 = load %3
16.03/5.48			%15 = load %r_ref
16.03/5.48			store %14, %15
16.03/5.48			br %16
16.03/5.48		16:
16.03/5.48			%17 = load %y_ref
16.03/5.48			%18 = load %17
16.03/5.48			%19 = icmp sgt %18 0
16.03/5.48			br %19, %20, %31
16.03/5.48		20:
16.03/5.48			%21 = load %r_ref
16.03/5.48			%22 = load %21
16.03/5.48			%23 = load %x_ref
16.03/5.48			%24 = load %23
16.03/5.48			%25 = mul %22 %24
16.03/5.48			%26 = load %r_ref
16.03/5.48			store %25, %26
16.03/5.48			%27 = load %y_ref
16.03/5.48			%28 = load %27
16.03/5.48			%29 = sub %28 1
16.03/5.48			%30 = load %y_ref
16.03/5.48			store %29, %30
16.03/5.48			br %16
16.03/5.48		31:
16.03/5.48			%32 = load %r_ref
16.03/5.48			%33 = load %32
16.03/5.48			ret %33
16.03/5.48	
16.03/5.48	*BasicFunctionTypename: "main" linkageType: EXTERNALLY_VISIBLE returnParam: i32 parameters: () variableLength: false visibilityType: DEFAULT callingConvention: ccc
16.03/5.48		0:
16.03/5.48			%1 = alloca i32, align 4
16.03/5.48			store 0, %1
16.03/5.48			%2 = call i32 @__VERIFIER_nondet_int()
16.03/5.48			%3 = call i32 @__VERIFIER_nondet_int()
16.03/5.48			%4 = call i32 @__VERIFIER_nondet_int()
16.03/5.48			%5 = call i32 @test_fun(i32 %2, i32 %3, i32 %4)
16.03/5.48			ret %5
16.03/5.48	
16.03/5.48	
16.03/5.48	Analyze Termination of all function calls matching the pattern:
16.03/5.48	main()
16.03/5.48	----------------------------------------
16.03/5.48	
16.03/5.48	(3) LLVMToTerminationGraphProof (EQUIVALENT)
16.03/5.48	Constructed symbolic execution graph for LLVM program and proved memory safety.
16.03/5.48	----------------------------------------
16.03/5.48	
16.03/5.48	(4)
16.03/5.48	Obligation:
16.03/5.48	SE Graph
16.03/5.48	----------------------------------------
16.03/5.48	
16.03/5.48	(5) SymbolicExecutionGraphToSCCProof (SOUND)
16.03/5.48	Splitted symbolic execution graph to 1 SCC.
16.03/5.48	----------------------------------------
16.03/5.48	
16.03/5.48	(6)
16.03/5.48	Obligation:
16.03/5.48	SCC
16.03/5.48	----------------------------------------
16.03/5.48	
16.03/5.48	(7) SCC2IRS (SOUND)
16.03/5.48	Transformed LLVM symbolic execution graph SCC into a rewrite problem. Log: 
16.03/5.48	Generated rules. Obtained 19 rulesP rules:
16.03/5.48	f_282(v72, v73, v74, v75, v76, v77, v78, v79, v80, v81, v82, v83, 1, v85, v86, v87, v88, v89, v90, v91, v92, v93, v94, v95, v96, v97, v98, v99, 0, 3, 7, 4, 8) -> f_283(v72, v73, v74, v75, v76, v77, v78, v79, v80, v81, v82, v83, 1, v88, v86, v87, v85, v89, v90, v91, v92, v93, v94, v95, v96, v97, v98, v99, 0, 3, 7, 4, 8) :|: 0 = 0
16.03/5.48	f_283(v72, v73, v74, v75, v76, v77, v78, v79, v80, v81, v82, v83, 1, v88, v86, v87, v85, v89, v90, v91, v92, v93, v94, v95, v96, v97, v98, v99, 0, 3, 7, 4, 8) -> f_284(v72, v73, v74, v75, v76, v77, v78, v79, v80, v81, v82, v83, 1, v88, v86, v87, v85, v89, v90, v91, v92, v93, v94, v95, v96, v97, v98, v99, 0, 3, 7, 2, 4, 8) :|: 0 < v88 && 2 <= v85 && 2 <= v73
16.03/5.48	f_284(v72, v73, v74, v75, v76, v77, v78, v79, v80, v81, v82, v83, 1, v88, v86, v87, v85, v89, v90, v91, v92, v93, v94, v95, v96, v97, v98, v99, 0, 3, 7, 2, 4, 8) -> f_286(v72, v73, v74, v75, v76, v77, v78, v79, v80, v81, v82, v83, 1, v88, v86, v87, v85, v89, v90, v91, v92, v93, v94, v95, v96, v97, v98, v99, 0, 3, 7, 2, 4, 8) :|: 0 = 0
16.03/5.48	f_286(v72, v73, v74, v75, v76, v77, v78, v79, v80, v81, v82, v83, 1, v88, v86, v87, v85, v89, v90, v91, v92, v93, v94, v95, v96, v97, v98, v99, 0, 3, 7, 2, 4, 8) -> f_288(v72, v73, v74, v75, v76, v77, v78, v79, v80, v81, v82, v83, 1, v88, v86, v87, v85, v89, v90, v91, v92, v93, v94, v95, v96, v97, v98, v99, 0, 3, 7, 2, 4, 8) :|: TRUE
16.03/5.48	f_288(v72, v73, v74, v75, v76, v77, v78, v79, v80, v81, v82, v83, 1, v88, v86, v87, v85, v89, v90, v91, v92, v93, v94, v95, v96, v97, v98, v99, 0, 3, 7, 2, 4, 8) -> f_290(v72, v73, v74, v75, v76, v77, v78, v79, v80, v81, v82, v83, 1, v88, v86, v87, v85, v89, v90, v91, v92, v93, v94, v95, v96, v97, v98, v99, 0, 3, 7, 2, 4, 8) :|: 0 = 0
16.03/5.48	f_290(v72, v73, v74, v75, v76, v77, v78, v79, v80, v81, v82, v83, 1, v88, v86, v87, v85, v89, v90, v91, v92, v93, v94, v95, v96, v97, v98, v99, 0, 3, 7, 2, 4, 8) -> f_292(v72, v73, v74, v75, v76, v77, v78, v79, v80, v81, v82, v83, 1, v88, v87, v85, v89, v90, v91, v92, v93, v94, v95, v96, v97, v98, v99, 0, 3, 7, 2, 4, 8) :|: 0 = 0
16.03/5.48	f_292(v72, v73, v74, v75, v76, v77, v78, v79, v80, v81, v82, v83, 1, v88, v87, v85, v89, v90, v91, v92, v93, v94, v95, v96, v97, v98, v99, 0, 3, 7, 2, 4, 8) -> f_294(v72, v73, v74, v75, v76, v77, v78, v79, v80, v81, v82, v83, 1, v88, v87, v85, v89, v90, v91, v92, v93, v94, v95, v96, v97, v98, v99, 0, 3, 7, 2, 4, 8) :|: 0 = 0
16.03/5.48	f_294(v72, v73, v74, v75, v76, v77, v78, v79, v80, v81, v82, v83, 1, v88, v87, v85, v89, v90, v91, v92, v93, v94, v95, v96, v97, v98, v99, 0, 3, 7, 2, 4, 8) -> f_296(v72, v73, v74, v75, v76, v77, v78, v79, v80, v81, v82, v83, 1, v88, v87, v85, v89, v90, v91, v92, v93, v94, v95, v96, v97, v98, v99, 0, 3, 7, 2, 4, 8) :|: 0 = 0
16.03/5.48	f_296(v72, v73, v74, v75, v76, v77, v78, v79, v80, v81, v82, v83, 1, v88, v87, v85, v89, v90, v91, v92, v93, v94, v95, v96, v97, v98, v99, 0, 3, 7, 2, 4, 8) -> f_297(v72, v73, v74, v75, v76, v77, v78, v79, v80, v81, v82, v83, 1, v88, v87, v101, v85, v89, v90, v91, v92, v93, v94, v95, v96, v97, v98, v99, 0, 3, 7, 2, 4, 8) :|: v101 = v87 * v72
16.03/5.48	f_297(v72, v73, v74, v75, v76, v77, v78, v79, v80, v81, v82, v83, 1, v88, v87, v101, v85, v89, v90, v91, v92, v93, v94, v95, v96, v97, v98, v99, 0, 3, 7, 2, 4, 8) -> f_298(v72, v73, v74, v75, v76, v77, v78, v79, v80, v81, v82, v83, 1, v88, v87, v101, v85, v89, v90, v91, v92, v93, v94, v95, v96, v97, v98, v99, 0, 3, 7, 2, 4, 8) :|: 0 = 0
16.03/5.48	f_298(v72, v73, v74, v75, v76, v77, v78, v79, v80, v81, v82, v83, 1, v88, v87, v101, v85, v89, v90, v91, v92, v93, v94, v95, v96, v97, v98, v99, 0, 3, 7, 2, 4, 8) -> f_299(v72, v73, v74, v75, v76, v77, v78, v79, v80, v81, v82, v83, 1, v88, v87, v101, v85, v89, v90, v91, v92, v93, v94, v95, v96, v97, v98, v99, 0, 3, 7, 2, 4, 8) :|: TRUE
16.03/5.48	f_299(v72, v73, v74, v75, v76, v77, v78, v79, v80, v81, v82, v83, 1, v88, v87, v101, v85, v89, v90, v91, v92, v93, v94, v95, v96, v97, v98, v99, 0, 3, 7, 2, 4, 8) -> f_300(v72, v73, v74, v75, v76, v77, v78, v79, v80, v81, v82, v83, 1, v88, v87, v101, v85, v89, v90, v91, v92, v93, v94, v95, v96, v97, v98, v99, 0, 3, 7, 2, 4, 8) :|: 0 = 0
16.03/5.48	f_300(v72, v73, v74, v75, v76, v77, v78, v79, v80, v81, v82, v83, 1, v88, v87, v101, v85, v89, v90, v91, v92, v93, v94, v95, v96, v97, v98, v99, 0, 3, 7, 2, 4, 8) -> f_301(v72, v73, v74, v75, v76, v77, v78, v79, v80, v81, v82, v83, 1, v88, v87, v101, v89, v90, v91, v92, v93, v94, v95, v96, v97, v98, v99, 0, 3, 7, 2, 4, 8) :|: 0 = 0
16.03/5.48	f_301(v72, v73, v74, v75, v76, v77, v78, v79, v80, v81, v82, v83, 1, v88, v87, v101, v89, v90, v91, v92, v93, v94, v95, v96, v97, v98, v99, 0, 3, 7, 2, 4, 8) -> f_302(v72, v73, v74, v75, v76, v77, v78, v79, v80, v81, v82, v83, 1, v88, v87, v101, v103, v89, v90, v91, v92, v93, v94, v95, v96, v97, v98, v99, 0, 3, 7, 2, 4, 8) :|: 1 + v103 = v88 && 0 <= v103
16.03/5.48	f_302(v72, v73, v74, v75, v76, v77, v78, v79, v80, v81, v82, v83, 1, v88, v87, v101, v103, v89, v90, v91, v92, v93, v94, v95, v96, v97, v98, v99, 0, 3, 7, 2, 4, 8) -> f_303(v72, v73, v74, v75, v76, v77, v78, v79, v80, v81, v82, v83, 1, v88, v87, v101, v103, v89, v90, v91, v92, v93, v94, v95, v96, v97, v98, v99, 0, 3, 7, 2, 4, 8) :|: 0 = 0
16.03/5.48	f_303(v72, v73, v74, v75, v76, v77, v78, v79, v80, v81, v82, v83, 1, v88, v87, v101, v103, v89, v90, v91, v92, v93, v94, v95, v96, v97, v98, v99, 0, 3, 7, 2, 4, 8) -> f_304(v72, v73, v74, v75, v76, v77, v78, v79, v80, v81, v82, v83, 1, v88, v87, v101, v103, v89, v90, v91, v92, v93, v94, v95, v96, v97, v98, v99, 0, 3, 7, 2, 4, 8) :|: TRUE
16.03/5.48	f_304(v72, v73, v74, v75, v76, v77, v78, v79, v80, v81, v82, v83, 1, v88, v87, v101, v103, v89, v90, v91, v92, v93, v94, v95, v96, v97, v98, v99, 0, 3, 7, 2, 4, 8) -> f_305(v72, v73, v74, v75, v76, v77, v78, v79, v80, v81, v82, v83, 1, v88, v87, v101, v103, v89, v90, v91, v92, v93, v94, v95, v96, v97, v98, v99, 0, 3, 7, 2, 4, 8) :|: TRUE
16.03/5.48	f_305(v72, v73, v74, v75, v76, v77, v78, v79, v80, v81, v82, v83, 1, v88, v87, v101, v103, v89, v90, v91, v92, v93, v94, v95, v96, v97, v98, v99, 0, 3, 7, 2, 4, 8) -> f_281(v72, v73, v74, v75, v76, v77, v78, v79, v80, v81, v82, v83, 1, v88, v87, v101, v103, v89, v90, v91, v92, v93, v94, v95, v96, v97, v98, v99, 0, 3, 7, 4, 8) :|: TRUE
16.03/5.48	f_281(v72, v73, v74, v75, v76, v77, v78, v79, v80, v81, v82, v83, 1, v85, v86, v87, v88, v89, v90, v91, v92, v93, v94, v95, v96, v97, v98, v99, 0, 3, 7, 4, 8) -> f_282(v72, v73, v74, v75, v76, v77, v78, v79, v80, v81, v82, v83, 1, v85, v86, v87, v88, v89, v90, v91, v92, v93, v94, v95, v96, v97, v98, v99, 0, 3, 7, 4, 8) :|: 0 = 0
16.03/5.48	Combined rules. Obtained 1 rulesP rules:
16.03/5.48	f_282(v72:0, v73:0, v74:0, v75:0, v76:0, v77:0, v78:0, v79:0, v80:0, v81:0, v82:0, v83:0, 1, v85:0, v86:0, v87:0, 1 + v103:0, v89:0, v90:0, v91:0, v92:0, v93:0, v94:0, v95:0, v96:0, v97:0, v98:0, v99:0, 0, 3, 7, 4, 8) -> f_282(v72:0, v73:0, v74:0, v75:0, v76:0, v77:0, v78:0, v79:0, v80:0, v81:0, v82:0, v83:0, 1, 1 + v103:0, v87:0, v87:0 * v72:0, v103:0, v89:0, v90:0, v91:0, v92:0, v93:0, v94:0, v95:0, v96:0, v97:0, v98:0, v99:0, 0, 3, 7, 4, 8) :|: v85:0 > 1 && v103:0 > -1 && v73:0 > 1
16.03/5.48	Filtered unneeded arguments:
16.03/5.48	   f_282(x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, x11, x12, x13, x14, x15, x16, x17, x18, x19, x20, x21, x22, x23, x24, x25, x26, x27, x28, x29, x30, x31, x32, x33) -> f_282(x2, x14, x17)
16.03/5.48	Removed division, modulo operations, cleaned up constraints. Obtained 1 rules.P rules:
16.03/5.48	f_282(v73:0, v85:0, sum~cons_1~v103:0) -> f_282(v73:0, 1 + v103:0, v103:0) :|: v103:0 > -1 && v73:0 > 1 && v85:0 > 1 && sum~cons_1~v103:0 = 1 + v103:0
16.03/5.48	
16.03/5.48	----------------------------------------
16.03/5.48	
16.03/5.48	(8)
16.03/5.48	Obligation:
16.03/5.48	Rules:
16.03/5.48	f_282(v73:0, v85:0, sum~cons_1~v103:0) -> f_282(v73:0, 1 + v103:0, v103:0) :|: v103:0 > -1 && v73:0 > 1 && v85:0 > 1 && sum~cons_1~v103:0 = 1 + v103:0
16.03/5.48	
16.03/5.48	----------------------------------------
16.03/5.48	
16.03/5.48	(9) IntTRSCompressionProof (EQUIVALENT)
16.03/5.48	Compressed rules.
16.03/5.48	----------------------------------------
16.03/5.48	
16.03/5.48	(10)
16.03/5.48	Obligation:
16.03/5.48	Rules:
16.03/5.48	f_282(v73:0:0, v85:0:0, sum~cons_1~v103:0:0) -> f_282(v73:0:0, 1 + v103:0:0, v103:0:0) :|: v103:0:0 > -1 && v73:0:0 > 1 && v85:0:0 > 1 && sum~cons_1~v103:0:0 = 1 + v103:0:0
16.03/5.48	
16.03/5.48	----------------------------------------
16.03/5.48	
16.03/5.48	(11) RankingReductionPairProof (EQUIVALENT)
16.03/5.48	Interpretation:
16.03/5.48	[ f_282 ] = f_282_3
16.03/5.48	
16.03/5.48	The following rules are decreasing:
16.03/5.48	f_282(v73:0:0, v85:0:0, sum~cons_1~v103:0:0) -> f_282(v73:0:0, 1 + v103:0:0, v103:0:0) :|: v103:0:0 > -1 && v73:0:0 > 1 && v85:0:0 > 1 && sum~cons_1~v103:0:0 = 1 + v103:0:0
16.03/5.48	
16.03/5.48	The following rules are bounded:
16.03/5.48	f_282(v73:0:0, v85:0:0, sum~cons_1~v103:0:0) -> f_282(v73:0:0, 1 + v103:0:0, v103:0:0) :|: v103:0:0 > -1 && v73:0:0 > 1 && v85:0:0 > 1 && sum~cons_1~v103:0:0 = 1 + v103:0:0
16.03/5.48	
16.03/5.48	
16.03/5.48	----------------------------------------
16.03/5.48	
16.03/5.48	(12)
16.03/5.48	YES
16.29/5.55	EOF